pwc-archive/papers-with-abstracts huggingface dataset:
Efficient Solution of Boolean Satisfiability Problems with Digital MemComputing
Authors: S. R. B. Bearden, Y. R. Pei, M. Di Ventra
Date: 2020-11-12 00:00:00
Tasks: Numerical Integration

Boolean satisfiability is a propositional logic problem of interest in multiple fields, e.g., physics, mathematics, and computer science. Beyond a field of research, instances of the SAT problem, as it is known, require efficient solution methods in a variety of applications. It is the decision problem of determining whether a Boolean formula has a satisfying assignment, believed to require exponentially growing time for an algorithm to solve for the worst-case instances. Yet, the efficient solution of many classes of Boolean formulae eludes even the most successful algorithms, not only for the worst-case scenarios, but also for typical-case instances. Here, we introduce a memory-assisted physical system (a digital memcomputing machine) that, when its non-linear ordinary differential equations are integrated numerically, shows evidence for polynomially-bounded scalability while solving "hard" planted-solution instances of SAT, known to require exponential time to solve in the typical case for both complete and incomplete algorithms. Furthermore, we analytically demonstrate that the physical system can efficiently solve the SAT problem in continuous time, without the need to introduce chaos or an exponentially growing energy. The efficiency of the simulations is related to the collective dynamical properties of the original physical system that persist in the numerical integration to robustly guide the solution search even in the presence of numerical errors. We anticipate our results to broaden research directions in physics-inspired computing paradigms ranging from theory to application, from simulation to hardware implementation.
Implicit bias of any algorithm: bounding bias via margin
Authors: Elvis Dohmatob
Date: 2020-11-12 00:00:00

Consider $n$ points $x_1,\ldots,x_n$ in finite-dimensional euclidean space, each having one of two colors. Suppose there exists a separating hyperplane (identified with its unit normal vector $w)$ for the points, i.e a hyperplane such that points of same color lie on the same side of the hyperplane. We measure the quality of such a hyperplane by its margin $\gamma(w)$, defined as minimum distance between any of the points $x_i$ and the hyperplane. In this paper, we prove that the margin function $\gamma$ satisfies a nonsmooth Kurdyka-Lojasiewicz inequality with exponent $1/2$. This result has far-reaching consequences. For example, let $\gamma^{opt}$ be the maximum possible margin for the problem and let $w^{opt}$ be the parameter for the hyperplane which attains this value. Given any other separating hyperplane with parameter $w$, let $d(w):=\|w-w^{opt}\|$ be the euclidean distance between $w$ and $w^{opt}$, also called the bias of $w$. From the previous KL-inequality, we deduce that $(\gamma^{opt}-\gamma(w)) / R \le d(w) \le 2\sqrt{(\gamma^{opt}-\gamma(w))/\gamma^{opt}}$, where $R:=\max_i \|x_i\|$ is the maximum distance of the points $x_i$ from the origin. Consequently, for any optimization algorithm (gradient-descent or not), the bias of the iterates converges at least as fast as the square-root of the rate of their convergence of the margin. Thus, our work provides a generic tool for analyzing the implicit bias of any algorithm in terms of its margin, in situations where a specialized analysis might not be available: it is sufficient to establish a good rate for converge of the margin, a task which is usually much easier.
Focal points and their implications for Möbius Transforms and Dempster-Shafer Theory
Authors: Maxime Chaveroche, Franck Davoine, Véronique Cherfaoui
Date: 2020-11-12 00:00:00

Dempster-Shafer Theory (DST) generalizes Bayesian probability theory, offering useful additional information, but suffers from a much higher computational burden. A lot of work has been done to reduce the time complexity of information fusion with Dempster's rule, which is a pointwise multiplication of two zeta transforms, and optimal general algorithms have been found to get the complete definition of these transforms. Yet, it is shown in this paper that the zeta transform and its inverse, the M\"obius transform, can be exactly simplified, fitting the quantity of information contained in belief functions. Beyond that, this simplification actually works for any function on any partially ordered set. It relies on a new notion that we call focal point and that constitutes the smallest domain on which both the zeta and M\"obius transforms can be defined. We demonstrate the interest of these general results for DST, not only for the reduction in complexity of most transformations between belief representations and their fusion, but also for theoretical purposes. Indeed, we provide a new generalization of the conjunctive decomposition of evidence and formulas uncovering how each decomposition weight is tied to the corresponding mass function.
Self-supervised reinforcement learning for speaker localisation with the iCub humanoid robot
Authors: Jonas Gonzalez-Billandon, Lukas Grasse, Matthew Tata, Alessandra Sciutti, Francesco Rea
Date: 2020-11-12 00:00:00
Tasks: Automatic Speech Recognition, Automatic Speech Recognition (ASR), reinforcement-learning, Reinforcement Learning (RL), speech-recognition, Speech Recognition

In the future robots will interact more and more with humans and will have to communicate naturally and efficiently. Automatic speech recognition systems (ASR) will play an important role in creating natural interactions and making robots better companions. Humans excel in speech recognition in noisy environments and are able to filter out noise. Looking at a person's face is one of the mechanisms that humans rely on when it comes to filtering speech in such noisy environments. Having a robot that can look toward a speaker could benefit ASR performance in challenging environments. To this aims, we propose a self-supervised reinforcement learning-based framework inspired by the early development of humans to allow the robot to autonomously create a dataset that is later used to learn to localize speakers with a deep learning network.
Shared Prior Learning of Energy-Based Models for Image Reconstruction
Authors: Thomas Pinetz, Erich Kobler, Thomas Pock, Alexander Effland
Date: 2020-11-12 00:00:00
Tasks: Image Reconstruction

We propose a novel learning-based framework for image reconstruction particularly designed for training without ground truth data, which has three major building blocks: energy-based learning, a patch-based Wasserstein loss functional, and shared prior learning. In energy-based learning, the parameters of an energy functional composed of a learned data fidelity term and a data-driven regularizer are computed in a mean-field optimal control problem. In the absence of ground truth data, we change the loss functional to a patch-based Wasserstein functional, in which local statistics of the output images are compared to uncorrupted reference patches. Finally, in shared prior learning, both aforementioned optimal control problems are optimized simultaneously with shared learned parameters of the regularizer to further enhance unsupervised image reconstruction. We derive several time discretization schemes of the gradient flow and verify their consistency in terms of Mosco convergence. In numerous numerical experiments, we demonstrate that the proposed method generates state-of-the-art results for various image reconstruction applications--even if no ground truth images are available for training.
Image analysis for Alzheimer's disease prediction: Embracing pathological hallmarks for model architecture design
Authors: Sarah C. Brüningk, Felix Hensel, Catherine R. Jutzeler, Bastian Rieck
Date: 2020-11-12 00:00:00
Tasks: Disease Prediction

Alzheimer's disease (AD) is associated with local (e.g. brain tissue atrophy) and global brain changes (loss of cerebral connectivity), which can be detected by high-resolution structural magnetic resonance imaging. Conventionally, these changes and their relation to AD are investigated independently. Here, we introduce a novel, highly-scalable approach that simultaneously captures $\textit{local}$ and $\textit{global}$ changes in the diseased brain. It is based on a neural network architecture that combines patch-based, high-resolution 3D-CNNs with global topological features, evaluating multi-scale brain tissue connectivity. Our local-global approach reached competitive results with an average precision score of $0.95\pm0.03$ for the classification of cognitively normal subjects and AD patients (prevalence $\approx 55\%$).
Treatment Allocation with Strategic Agents
Authors: Evan Munro
Date: 2020-11-12 00:00:00
Tasks: Bayesian Optimization, Marketing

There is increasing interest in allocating treatments based on observed individual characteristics: examples include targeted marketing, individualized credit offers, and heterogeneous pricing. Treatment personalization introduces incentives for individuals to modify their behavior to obtain a better treatment. Strategic behavior shifts the joint distribution of covariates and potential outcomes. The optimal rule without strategic behavior allocates treatments only to those with a positive Conditional Average Treatment Effect. With strategic behavior, we show that the optimal rule can involve randomization, allocating treatments with less than 100% probability even to those who respond positively on average to the treatment. We propose a sequential experiment based on Bayesian Optimization that converges to the optimal treatment rule without parametric assumptions on individual strategic behavior.
Inference-only sub-character decomposition improves translation of unseen logographic characters
Authors: Danielle Saunders, Weston Feely, Bill Byrne
Date: 2020-11-12 00:00:00
Proceeding: AACL (WAT) 2020 12
Tasks: Machine Translation, NMT, Translation

Neural Machine Translation (NMT) on logographic source languages struggles when translating `unseen' characters, which never appear in the training data. One possible approach to this problem uses sub-character decomposition for training and test sentences. However, this approach involves complete retraining, and its effectiveness for unseen character translation to non-logographic languages has not been fully explored. We investigate existing ideograph-based sub-character decomposition approaches for Chinese-to-English and Japanese-to-English NMT, for both high-resource and low-resource domains. For each language pair and domain we construct a test set where all source sentences contain at least one unseen logographic character. We find that complete sub-character decomposition often harms unseen character translation, and gives inconsistent results generally. We offer a simple alternative based on decomposition before inference for unseen characters only. Our approach allows flexible application, achieving translation adequacy improvements and requiring no additional models or training.
Reinforcement Learning with Videos: Combining Offline Observations with Interaction
Authors: Karl Schmeckpeper, Oleh Rybkin, Kostas Daniilidis, Sergey Levine, Chelsea Finn
Date: 2020-11-12 00:00:00
Tasks: reinforcement-learning, Reinforcement Learning, Reinforcement Learning (RL)

Reinforcement learning is a powerful framework for robots to acquire skills from experience, but often requires a substantial amount of online data collection. As a result, it is difficult to collect sufficiently diverse experiences that are needed for robots to generalize broadly. Videos of humans, on the other hand, are a readily available source of broad and interesting experiences. In this paper, we consider the question: can we perform reinforcement learning directly on experience collected by humans? This problem is particularly difficult, as such videos are not annotated with actions and exhibit substantial visual domain shift relative to the robot's embodiment. To address these challenges, we propose a framework for reinforcement learning with videos (RLV). RLV learns a policy and value function using experience collected by humans in combination with data collected by robots. In our experiments, we find that RLV is able to leverage such videos to learn challenging vision-based skills with less than half as many samples as RL methods that learn from scratch.
Ridge Rider: Finding Diverse Solutions by Following Eigenvectors of the Hessian
Authors: Jack Parker-Holder, Luke Metz, Cinjon Resnick, Hengyuan Hu, Adam Lerer, Alistair Letcher, Alex Peysakhovich, Aldo Pacchiano, Jakob Foerster
Date: 2020-11-12 00:00:00
Proceeding: NeurIPS 2020 12
Tasks: BIG-bench Machine Learning

Over the last decade, a single algorithm has changed many facets of our lives - Stochastic Gradient Descent (SGD). In the era of ever decreasing loss functions, SGD and its various offspring have become the go-to optimization tool in machine learning and are a key component of the success of deep neural networks (DNNs). While SGD is guaranteed to converge to a local optimum (under loose assumptions), in some cases it may matter which local optimum is found, and this is often context-dependent. Examples frequently arise in machine learning, from shape-versus-texture-features to ensemble methods and zero-shot coordination. In these settings, there are desired solutions which SGD on 'standard' loss functions will not find, since it instead converges to the 'easy' solutions. In this paper, we present a different approach. Rather than following the gradient, which corresponds to a locally greedy direction, we instead follow the eigenvectors of the Hessian, which we call "ridges". By iteratively following and branching amongst the ridges, we effectively span the loss surface to find qualitatively different solutions. We show both theoretically and experimentally that our method, called Ridge Rider (RR), offers a promising direction for a variety of challenging problems.
An Interpretable End-to-end Fine-tuning Approach for Long Clinical Text
Authors: Kexin Huang, Sankeerth Garapati, Alexander S. Rich
Date: 2020-11-12 00:00:00
Tasks: text-classification, Text Classification

Unstructured clinical text in EHRs contains crucial information for applications including decision support, trial matching, and retrospective research. Recent work has applied BERT-based models to clinical information extraction and text classification, given these models' state-of-the-art performance in other NLP domains. However, BERT is difficult to apply to clinical notes because it doesn't scale well to long sequences of text. In this work, we propose a novel fine-tuning approach called SnipBERT. Instead of using entire notes, SnipBERT identifies crucial snippets and then feeds them into a truncated BERT-based model in a hierarchical manner. Empirically, SnipBERT not only has significant predictive performance gain across three tasks but also provides improved interpretability, as the model can identify key pieces of text that led to its prediction.
Quality4.0 -- Transparent product quality supervision in the age of Industry 4.0
Authors: Jens Brandenburger, Christoph Schirm, Josef Melcher, Edgar Hancke, Marco Vannucci, Valentina Colla, Silvia Cateni, Rami Sellami, Sébastien Dupont, Annick Majchrowski, Asier Arteaga
Date: 2020-11-12 00:00:00
Tasks: BIG-bench Machine Learning

Progressive digitalization is changing the game of many industrial sectors. Focus-ing on product quality the main profitability driver of this so-called Industry 4.0 will be the horizontal integration of information over the complete supply chain. Therefore, the European RFCS project 'Quality4.0' aims in developing an adap-tive platform, which releases decisions on product quality and provides tailored information of high reliability that can be individually exchanged with customers. In this context Machine Learning will be used to detect outliers in the quality data. This paper discusses the intermediate project results and the concepts developed so far for this horizontal integration of quality information.
Fit2Form: 3D Generative Model for Robot Gripper Form Design
Authors: Huy Ha, Shubham Agrawal, Shuran Song
Date: 2020-11-12 00:00:00
Tasks: Form

The 3D shape of a robot's end-effector plays a critical role in determining it's functionality and overall performance. Many industrial applications rely on task-specific gripper designs to ensure the system's robustness and accuracy. However, the process of manual hardware design is both costly and time-consuming, and the quality of the resulting design is dependent on the engineer's experience and domain expertise, which can easily be out-dated or inaccurate. The goal of this work is to use machine learning algorithms to automate the design of task-specific gripper fingers. We propose Fit2Form, a 3D generative design framework that generates pairs of finger shapes to maximize design objectives (i.e., grasp success, stability, and robustness) for target grasp objects. We model the design objectives by training a Fitness network to predict their values for pairs of gripper fingers and their corresponding grasp objects. This Fitness network then provides supervision to a 3D Generative network that produces a pair of 3D finger geometries for the target grasp object. Our experiments demonstrate that the proposed 3D generative design framework generates parallel jaw gripper finger shapes that achieve more stable and robust grasps compared to other general-purpose and task-specific gripper design algorithms. Video can be found at https://youtu.be/utKHP3qb1bg.
Distributed Sparse SGD with Majority Voting
Authors: Kerem Ozfatura, Emre Ozfatura, Deniz Gunduz
Date: 2020-11-12 00:00:00

Distributed learning, particularly variants of distributed stochastic gradient descent (DSGD), are widely employed to speed up training by leveraging computational resources of several workers. However, in practise, communication delay becomes a bottleneck due to the significant amount of information that needs to be exchanged between the workers and the parameter server. One of the most efficient strategies to mitigate the communication bottleneck is top-K sparsification. However, top-K sparsification requires additional communication load to represent the sparsity pattern, and the mismatch between the sparsity patterns of the workers prevents exploitation of efficient communication protocols. To address these issues, we introduce a novel majority voting based sparse communication strategy, in which the workers first seek a consensus on the structure of the sparse representation. This strategy provides a significant reduction in the communication load and allows using the same sparsity level in both communication directions. Through extensive simulations on the CIFAR-10 dataset, we show that it is possible to achieve up to x4000 compression without any loss in the test accuracy.
Content-based Image Retrieval and the Semantic Gap in the Deep Learning Era
Authors: Björn Barz, Joachim Denzler
Date: 2020-11-12 00:00:00
Tasks: Content-Based Image Retrieval, Image Retrieval, Retrieval, World Knowledge

Content-based image retrieval has seen astonishing progress over the past decade, especially for the task of retrieving images of the same object that is depicted in the query image. This scenario is called instance or object retrieval and requires matching fine-grained visual patterns between images. Semantics, however, do not play a crucial role. This brings rise to the question: Do the recent advances in instance retrieval transfer to more generic image retrieval scenarios? To answer this question, we first provide a brief overview of the most relevant milestones of instance retrieval. We then apply them to a semantic image retrieval task and find that they perform inferior to much less sophisticated and more generic methods in a setting that requires image understanding. Following this, we review existing approaches to closing this so-called semantic gap by integrating prior world knowledge. We conclude that the key problem for the further advancement of semantic image retrieval lies in the lack of a standardized task definition and an appropriate benchmark dataset.
Natural Language Processing to Detect Cognitive Concerns in Electronic Health Records Using Deep Learning
Authors: Zhuoqiao Hong, Colin G. Magdamo, Yi-han Sheu, Prathamesh Mohite, Ayush Noori, Elissa M. Ye, Wendong Ge, Haoqi Sun, Laura Brenner, Gregory Robbins, Shibani Mukerji, Sahar Zafar, Nicole Benson, Lidia Moura, John Hsu, Bradley T. Hyman, Michael B. Westover, Deborah Blacker, Sudeshna Das
Date: 2020-11-12 00:00:00

Dementia is under-recognized in the community, under-diagnosed by healthcare professionals, and under-coded in claims data. Information on cognitive dysfunction, however, is often found in unstructured clinician notes within medical records but manual review by experts is time consuming and often prone to errors. Automated mining of these notes presents a potential opportunity to label patients with cognitive concerns who could benefit from an evaluation or be referred to specialist care. In order to identify patients with cognitive concerns in electronic medical records, we applied natural language processing (NLP) algorithms and compared model performance to a baseline model that used structured diagnosis codes and medication data only. An attention-based deep learning model outperformed the baseline model and other simpler models.
Fairness and Robustness in Invariant Learning: A Case Study in Toxicity Classification
Authors: Robert Adragna, Elliot Creager, David Madras, Richard Zemel
Date: 2020-11-12 00:00:00
Tasks: BIG-bench Machine Learning, Causal Discovery, Domain Generalization, Fairness, General Classification

Robustness is of central importance in machine learning and has given rise to the fields of domain generalization and invariant learning, which are concerned with improving performance on a test distribution distinct from but related to the training distribution. In light of recent work suggesting an intimate connection between fairness and robustness, we investigate whether algorithms from robust ML can be used to improve the fairness of classifiers that are trained on biased data and tested on unbiased data. We apply Invariant Risk Minimization (IRM), a domain generalization algorithm that employs a causal discovery inspired method to find robust predictors, to the task of fairly predicting the toxicity of internet comments. We show that IRM achieves better out-of-distribution accuracy and fairness than Empirical Risk Minimization (ERM) methods, and analyze both the difficulties that arise when applying IRM in practice and the conditions under which IRM will likely be effective in this scenario. We hope that this work will inspire further studies of how robust machine learning methods relate to algorithmic fairness.