pwc-archive/papers-with-abstracts huggingface dataset:
Recursed is not Recursive: A Jarring Result
Authors: Erik Demaine, Justin Kopinsky, Jayson Lynch
Date: 2020-02-12 00:00:00

Recursed is a 2D puzzle platform video game featuring treasure chests that, when jumped into, instantiate a room that can later be exited (similar to function calls), optionally generating a jar that returns back to that room (similar to continuations). We prove that Recursed is RE-complete and thus undecidable (not recursive) by a reduction from the Post Correspondence Problem. Our reduction is "practical": the reduction from PCP results in fully playable levels that abide by all constraints governing levels (including the 15x20 room size) designed for the main game. Our reduction is also "efficient": a Turing machine can be simulated by a Recursed level whose size is linear in the encoding size of the Turing machine and whose solution length is polynomial in the running time of the Turing machine.
Over-the-Air Adversarial Flickering Attacks against Video Recognition Networks
Authors: Roi Pony, Itay Naeh, Shie Mannor
Date: 2020-02-12 00:00:00
Proceeding: CVPR 2021 1
Tasks: Action Classification, Classification, General Classification, image-classification, Image Classification, Optical Flow Estimation, Video Classification, Video Recognition

Deep neural networks for video classification, just like image classification networks, may be subjected to adversarial manipulation. The main difference between image classifiers and video classifiers is that the latter usually use temporal information contained within the video. In this work we present a manipulation scheme for fooling video classifiers by introducing a flickering temporal perturbation that in some cases may be unnoticeable by human observers and is implementable in the real world. After demonstrating the manipulation of action classification of single videos, we generalize the procedure to make universal adversarial perturbation, achieving high fooling ratio. In addition, we generalize the universal perturbation and produce a temporal-invariant perturbation, which can be applied to the video without synchronizing the perturbation to the input. The attack was implemented on several target models and the transferability of the attack was demonstrated. These properties allow us to bridge the gap between simulated environment and real-world application, as will be demonstrated in this paper for the first time for an over-the-air flickering attack.
Parameterizing Branch-and-Bound Search Trees to Learn Branching Policies
Authors: Giulia Zarpellon, Jason Jo, Andrea Lodi, Yoshua Bengio
Date: 2020-02-12 00:00:00
Tasks: Imitation Learning

Branch and Bound (B&B) is the exact tree search method typically used to solve Mixed-Integer Linear Programming problems (MILPs). Learning branching policies for MILP has become an active research area, with most works proposing to imitate the strong branching rule and specialize it to distinct classes of problems. We aim instead at learning a policy that generalizes across heterogeneous MILPs: our main hypothesis is that parameterizing the state of the B&B search tree can aid this type of generalization. We propose a novel imitation learning framework, and introduce new input features and architectures to represent branching. Experiments on MILP benchmark instances clearly show the advantages of incorporating an explicit parameterization of the state of the search tree to modulate the branching decisions, in terms of both higher accuracy and smaller B&B trees. The resulting policies significantly outperform the current state-of-the-art method for "learning to branch" by effectively allowing generalization to generic unseen instances.
Analysis of Dutch Master Paintings with Convolutional Neural Networks
Authors: Steven J. Frank, Andrea M. Frank
Date: 2020-02-12 00:00:00
Tasks: General Classification

Trained on the works of an artist under study and visually comparable works of other artists, convolutional neural networks can identify forgeries and provide attributions. They can also assign classification probabilities within a painting, revealing mixed authorship and identifying regions painted by different hands.
Development of modeling and control strategies for an approximated Gaussian process
Authors: Shisheng Cui, Chia-Jung Chang
Date: 2020-02-12 00:00:00
Tasks: Computational Efficiency

The Gaussian process (GP) model, which has been extensively applied as priors of functions, has demonstrated excellent performance. The specification of a large number of parameters affects the computational efficiency and the feasibility of implementation of a control strategy. We propose a linear model to approximate GPs; this model expands the GP model by a series of basis functions. Several examples and simulation studies are presented to demonstrate the advantages of the proposed method. A control strategy is provided with the proposed linear model.
Component Analysis for Visual Question Answering Architectures
Authors: Camila Kolling, Jônatas Wehrmann, Rodrigo C. Barros
Date: 2020-02-12 00:00:00
Tasks: Question Answering, Representation Learning, Visual Question Answering, Visual Question Answering (VQA)

Recent research advances in Computer Vision and Natural Language Processing have introduced novel tasks that are paving the way for solving AI-complete problems. One of those tasks is called Visual Question Answering (VQA). A VQA system must take an image and a free-form, open-ended natural language question about the image, and produce a natural language answer as the output. Such a task has drawn great attention from the scientific community, which generated a plethora of approaches that aim to improve the VQA predictive accuracy. Most of them comprise three major components: (i) independent representation learning of images and questions; (ii) feature fusion so the model can use information from both sources to answer visual questions; and (iii) the generation of the correct answer in natural language. With so many approaches being recently introduced, it became unclear the real contribution of each component for the ultimate performance of the model. The main goal of this paper is to provide a comprehensive analysis regarding the impact of each component in VQA models. Our extensive set of experiments cover both visual and textual elements, as well as the combination of these representations in form of fusion and attention mechanisms. Our major contribution is to identify core components for training VQA models so as to maximize their predictive performance.
dtControl: Decision Tree Learning Algorithms for Controller Representation
Authors: Pranav Ashok, Mathias Jackermeier, Pushpak Jagtap, Jan Křetínský, Maximilian Weininger, Majid Zamani
Date: 2020-02-12 00:00:00

Decision tree learning is a popular classification technique most commonly used in machine learning applications. Recent work has shown that decision trees can be used to represent provably-correct controllers concisely. Compared to representations using lookup tables or binary decision diagrams, decision trees are smaller and more explainable. We present dtControl, an easily extensible tool for representing memoryless controllers as decision trees. We give a comprehensive evaluation of various decision tree learning algorithms applied to 10 case studies arising out of correct-by-construction controller synthesis. These algorithms include two new techniques, one for using arbitrary linear binary classifiers in the decision tree learning, and one novel approach for determinizing controllers during the decision tree construction. In particular the latter turns out to be extremely efficient, yielding decision trees with a single-digit number of decision nodes on 5 of the case studies.
Regret Bounds for Noise-Free Kernel-Based Bandits
Authors: Sattar Vakili
Date: 2020-02-12 00:00:00
Tasks: Bayesian Optimisation

Kernel-based bandit is an extensively studied black-box optimization problem, in which the objective function is assumed to live in a known reproducing kernel Hilbert space. While nearly optimal regret bounds (up to logarithmic factors) are established in the noisy setting, surprisingly, less is known about the noise-free setting (when the exact values of the underlying function is accessible without observation noise). We discuss several upper bounds on regret; none of which seem order optimal, and provide a conjecture on the order optimal regret bound.
Compressive Learning of Generative Networks
Authors: Vincent Schellekens, Laurent Jacques
Date: 2020-02-12 00:00:00

Generative networks implicitly approximate complex densities from their sampling with impressive accuracy. However, because of the enormous scale of modern datasets, this training process is often computationally expensive. We cast generative network training into the recent framework of compressive learning: we reduce the computational burden of large-scale datasets by first harshly compressing them in a single pass as a single sketch vector. We then propose a cost function, which approximates the Maximum Mean Discrepancy metric, but requires only this sketch, which makes it time- and memory-efficient to optimize.
Using Automated Theorem Provers for Mistake Diagnosis in the Didactics of Mathematics
Authors: Merlin Carl
Date: 2020-02-12 00:00:00

The Diproche system, an automated proof checker for natural language proofs specifically adapted to the context of exercises for beginner's students similar to the Naproche system by Koepke, Schr\"oder, Cramer and others, uses a modification of an automated theorem prover which uses common formal fallacies intead of sound deduction rules for mistake diagnosis. We briefly describe the concept of such an `Anti-ATP' and explain the basic techniques used in its implementation.
Results on the algebraic matroid of the determinantal variety
Authors: Manolis C. Tsakiris
Date: 2020-02-12 00:00:00
Tasks: Matrix Completion

We make progress towards characterizing the algebraic matroid of the determinantal variety defined by the minors of fixed size of a matrix of variables. Our main result is a novel family of base sets of the matroid, which characterizes the matroid in special cases. Our approach relies on the combinatorial notion of relaxed supports of linkage matching fields that we introduce, our interpretation of the problem of completing a matrix of bounded rank from a subset of its entries as a linear section problem on the Grassmannian, and a connection that we draw with a class of local coordinates on the Grassmannian described by Sturmfels and Zelevinsky in 1993.
Efficient Structure-preserving Support Tensor Train Machine
Authors: Kirandeep Kour, Sergey Dolgov, Martin Stoll, Peter Benner
Date: 2020-02-12 00:00:00
Tasks: Classification

An increasing amount of collected data are high-dimensional multi-way arrays (tensors), and it is crucial for efficient learning algorithms to exploit this tensorial structure as much as possible. The ever-present curse of dimensionality for high dimensional data and the loss of structure when vectorizing the data motivates the use of tailored low-rank tensor classification methods. In the presence of small amounts of training data, kernel methods offer an attractive choice as they provide the possibility for a nonlinear decision boundary. We develop the Tensor Train Multi-way Multi-level Kernel (TT-MMK), which combines the simplicity of the Canonical Polyadic decomposition, the classification power of the Dual Structure-preserving Support Vector Machine, and the reliability of the Tensor Train (TT) approximation. We show by experiments that the TT-MMK method is usually more reliable computationally, less sensitive to tuning parameters, and gives higher prediction accuracy in the SVM classification when benchmarked against other state-of-the-art techniques.
Structure-Property Maps with Kernel Principal Covariates Regression
Authors: Benjamin A. Helfrecht, Rose K. Cersonsky, Guillaume Fraux, Michele Ceriotti
Date: 2020-02-12 00:00:00
Tasks: regression

Data analyses based on linear methods constitute the simplest, most robust, and transparent approaches to the automatic processing of large amounts of data for building supervised or unsupervised machine learning models. Principal covariates regression (PCovR) is an underappreciated method that interpolates between principal component analysis and linear regression, and can be used to conveniently reveal structure-property relations in terms of simple-to-interpret, low-dimensional maps. Here we provide a pedagogic overview of these data analysis schemes, including the use of the kernel trick to introduce an element of non-linearity, while maintaining most of the convenience and the simplicity of linear approaches. We then introduce a kernelized version of PCovR and a sparsified extension, and demonstrate the performance of this approach in revealing and predicting structure-property relations in chemistry and materials science, showing a variety of examples including elemental carbon, porous silicate frameworks, organic molecules, amino acid conformers, and molecular materials.
AlignNet: A Unifying Approach to Audio-Visual Alignment
Authors: Jianren Wang, Zhaoyuan Fang, Hang Zhao
Date: 2020-02-12 00:00:00

We present AlignNet, a model that synchronizes videos with reference audios under non-uniform and irregular misalignments. AlignNet learns the end-to-end dense correspondence between each frame of a video and an audio. Our method is designed according to simple and well-established principles: attention, pyramidal processing, warping, and affinity function. Together with the model, we release a dancing dataset Dance50 for training and evaluation. Qualitative, quantitative and subjective evaluation results on dance-music alignment and speech-lip alignment demonstrate that our method far outperforms the state-of-the-art methods. Project video and code are available at https://jianrenw.github.io/AlignNet.
A Bayesian Approach to Conversational Recommendation Systems
Authors: Francesca Mangili, Denis Broggini, Alessandro Antonucci, Marco Alberti, Lorenzo Cimasoni
Date: 2020-02-12 00:00:00
Tasks: Conversational Recommendation, Recommendation Systems

We present a conversational recommendation system based on a Bayesian approach. A probability mass function over the items is updated after any interaction with the user, with information-theoretic criteria optimally shaping the interaction and deciding when the conversation should be terminated and the most probable item consequently recommended. Dedicated elicitation techniques for the prior probabilities of the parameters modeling the interactions are derived from basic structural judgements. Such prior information can be combined with historical data to discriminate items with different recommendation histories. A case study based on the application of this approach to \emph{stagend.com}, an online platform for booking entertainers, is finally discussed together with an empirical analysis showing the advantages in terms of recommendation quality and efficiency.
Learning to Compare for Better Training and Evaluation of Open Domain Natural Language Generation Models
Authors: Wangchunshu Zhou, Ke Xu
Date: 2020-02-12 00:00:00
Tasks: Natural Language Understanding, Response Generation, Story Generation, Text Generation

Automated evaluation of open domain natural language generation (NLG) models remains a challenge and widely used metrics such as BLEU and Perplexity can be misleading in some cases. In our paper, we propose to evaluate natural language generation models by learning to compare a pair of generated sentences by fine-tuning BERT, which has been shown to have good natural language understanding ability. We also propose to evaluate the model-level quality of NLG models with sample-level comparison results with skill rating system. While able to be trained in a fully self-supervised fashion, our model can be further fine-tuned with a little amount of human preference annotation to better imitate human judgment. In addition to evaluating trained models, we propose to apply our model as a performance indicator during training for better hyperparameter tuning and early-stopping. We evaluate our approach on both story generation and chit-chat dialogue response generation. Experimental results show that our model correlates better with human preference compared with previous automated evaluation approaches. Training with the proposed metric yields better performance in human evaluation, which further demonstrates the effectiveness of the proposed model.
Quantum Boosting
Authors: Srinivasan Arunachalam, Reevu Maity
Date: 2020-02-12 00:00:00
Proceeding: ICML 2020 1

Suppose we have a weak learning algorithm $\mathcal{A}$ for a Boolean-valued problem: $\mathcal{A}$ produces hypotheses whose bias $\gamma$ is small, only slightly better than random guessing (this could, for instance, be due to implementing $\mathcal{A}$ on a noisy device), can we boost the performance of $\mathcal{A}$ so that $\mathcal{A}$'s output is correct on $2/3$ of the inputs? Boosting is a technique that converts a weak and inaccurate machine learning algorithm into a strong accurate learning algorithm. The AdaBoost algorithm by Freund and Schapire (for which they were awarded the G\"odel prize in 2003) is one of the widely used boosting algorithms, with many applications in theory and practice. Suppose we have a $\gamma$-weak learner for a Boolean concept class $C$ that takes time $R(C)$, then the time complexity of AdaBoost scales as $VC(C)\cdot poly(R(C), 1/\gamma)$, where $VC(C)$ is the $VC$-dimension of $C$. In this paper, we show how quantum techniques can improve the time complexity of classical AdaBoost. To this end, suppose we have a $\gamma$-weak quantum learner for a Boolean concept class $C$ that takes time $Q(C)$, we introduce a quantum boosting algorithm whose complexity scales as $\sqrt{VC(C)}\cdot poly(Q(C),1/\gamma);$ thereby achieving a quadratic quantum improvement over classical AdaBoost in terms of $VC(C)$.
Detect and Correct Bias in Multi-Site Neuroimaging Datasets
Authors: Christian Wachinger, Anna Rieckmann, Sebastian Pölsterl
Date: 2020-02-12 00:00:00

The desire to train complex machine learning algorithms and to increase the statistical power in association studies drives neuroimaging research to use ever-larger datasets. The most obvious way to increase sample size is by pooling scans from independent studies. However, simple pooling is often ill-advised as selection, measurement, and confounding biases may creep in and yield spurious correlations. In this work, we combine 35,320 magnetic resonance images of the brain from 17 studies to examine bias in neuroimaging. In the first experiment, Name That Dataset, we provide empirical evidence for the presence of bias by showing that scans can be correctly assigned to their respective dataset with 71.5% accuracy. Given such evidence, we take a closer look at confounding bias, which is often viewed as the main shortcoming in observational studies. In practice, we neither know all potential confounders nor do we have data on them. Hence, we model confounders as unknown, latent variables. Kolmogorov complexity is then used to decide whether the confounded or the causal model provides the simplest factorization of the graphical model. Finally, we present methods for dataset harmonization and study their ability to remove bias in imaging features. In particular, we propose an extension of the recently introduced ComBat algorithm to control for global variation across image features, inspired by adjusting for population stratification in genetics. Our results demonstrate that harmonization can reduce dataset-specific information in image features. Further, confounding bias can be reduced and even turned into a causal relationship. However, harmonziation also requires caution as it can easily remove relevant subject-specific information. Code is available at https://github.com/ai-med/Dataset-Bias.
Intra-Camera Supervised Person Re-Identification
Authors: Xiangping Zhu, Xiatian Zhu, Minxian Li, Pietro Morerio, Vittorio Murino, Shaogang Gong
Date: 2020-02-12 00:00:00
Tasks: Person Re-Identification

Existing person re-identification (re-id) methods mostly exploit a large set of cross-camera identity labelled training data. This requires a tedious data collection and annotation process, leading to poor scalability in practical re-id applications. On the other hand unsupervised re-id methods do not need identity label information, but they usually suffer from much inferior and insufficient model performance. To overcome these fundamental limitations, we propose a novel person re-identification paradigm based on an idea of independent per-camera identity annotation. This eliminates the most time-consuming and tedious inter-camera identity labelling process, significantly reducing the amount of human annotation efforts. Consequently, it gives rise to a more scalable and more feasible setting, which we call Intra-Camera Supervised (ICS) person re-id, for which we formulate a Multi-tAsk mulTi-labEl (MATE) deep learning method. Specifically, MATE is designed for self-discovering the cross-camera identity correspondence in a per-camera multi-task inference framework. Extensive experiments demonstrate the cost-effectiveness superiority of our method over the alternative approaches on three large person re-id datasets. For example, MATE yields 88.7% rank-1 score on Market-1501 in the proposed ICS person re-id setting, significantly outperforming unsupervised learning models and closely approaching conventional fully supervised learning competitors.
Constructing a Highlight Classifier with an Attention Based LSTM Neural Network
Authors: Michael Kuehne, Marius Radu
Date: 2020-02-12 00:00:00

Data is being produced in larger quantities than ever before in human history. It's only natural to expect a rise in demand for technology that aids humans in sifting through and analyzing this inexhaustible supply of information. This need exists in the market research industry, where large amounts of consumer research data is collected through video recordings. At present, the standard method for analyzing video data is human labor. Market researchers manually review the vast majority of consumer research video in order to identify relevant portions - highlights. The industry state of the art turnaround ratio is 2.2 - for every hour of video content 2.2 hours of manpower are required. In this study we present a novel approach for NLP-based highlight identification and extraction based on a supervised learning model that aides market researchers in sifting through their data. Our approach hinges on a manually curated user-generated highlight clips constructed from long and short-form video data. The problem is best suited for an NLP approach due to the availability of video transcription. We evaluate multiple classes of models, from gradient boosting to recurrent neural networks, comparing their performance in extraction and identification of highlights. The best performing models are then evaluated using four sampling methods designed to analyze documents much larger than the maximum input length of the classifiers. We report very high performances for the standalone classifiers, ROC AUC scores in the range 0.93-0.94, but observe a significant drop in effectiveness when evaluated on large documents. Based on our results we suggest combinations of models/sampling algorithms for various use cases.