pwc-archive/papers-with-abstracts huggingface dataset:
Quantum process tomography with unknown single-preparation input states
Authors: Yannick Deville, Alain Deville
Date: 2019-09-18 00:00:00

Quantum Process Tomography (QPT) methods aim at identifying, i.e. estimating, a given quantum process. QPT is a major quantum information processing tool, since it especially allows one to characterize the actual behavior of quantum gates, which are the building blocks of quantum computers. However, usual QPT procedures are complicated, since they set several constraints on the quantum states used as inputs of the process to be characterized. In this paper, we extend QPT so as to avoid two such constraints. On the one hand, usual QPT methods requires one to know, hence to precisely control (i.e. prepare), the specific quantum states used as inputs of the considered quantum process, which is cumbersome. We therefore propose a Blind, or unsupervised, extension of QPT (i.e. BQPT), which means that this approach uses input quantum states whose values are unknown and arbitrary, except that they are requested to meet some general known properties (and this approach exploits the output states of the considered quantum process). On the other hand, usual QPT methods require one to be able to prepare many copies of the same (known) input state, which is constraining. On the contrary, we propose "single-preparation methods", i.e. methods which can operate with only one instance of each considered input state. These two new concepts are here illustrated with practical BQPT methods which are numerically validated, in the case when: i) random pure states are used as inputs and their required properties are especially related to the statistical independence of the random variables that define them, ii) the considered quantum process is based on cylindrical-symmetry Heisenberg spin coupling. These concepts may be extended to a much wider class of processes and to BQPT methods based on other input quantum state properties.
Learnability Can Be Independent of ZFC Axioms: Explanations and Implications
Authors: William Taylor
Date: 2019-09-16 00:00:00

In Ben-David et al.'s "Learnability Can Be Undecidable," they prove an independence result in theoretical machine learning. In particular, they define a new type of learnability, called Estimating The Maximum (EMX) learnability. They argue that this type of learnability fits in with other notions such as PAC learnability, Vapnik's statistical learning setting, and other general learning settings. However, using some set-theoretic techniques, they show that some learning problems in the EMX setting are independent of ZFC. Specifically they prove that ZFC cannot prove or disprove EMX learnability of the finite subsets on the [0,1] interval. Moreover, the way they prove it shows that there can be no characteristic dimension for EMX; and, hence, for general learning settings. Here, I will explain their findings, discuss some limitations on those findings, and offer some suggestions about how to excise that undecidability. Parts 2-3 will explain the results of the paper, part 4-5 will discuss some limitations and next steps, and I will conclude in part 6.
Persistence B-Spline Grids: Stable Vector Representation of Persistence Diagrams Based on Data Fitting
Authors: Zhetong Dong, Hongwei Lin, Chi Zhou
Date: 2019-09-17 00:00:00
Tasks: Topological Data Analysis

Many attempts have been made in recent decades to integrate machine learning (ML) and topological data analysis. A prominent problem in applying persistent homology to ML tasks is finding a vector representation of a persistence diagram (PD), which is a summary diagram for representing topological features. From the perspective of data fitting, a stable vector representation, namely, persistence B-spline grid (PBSG), is proposed based on the efficient technique of progressive-iterative approximation for least-squares B-spline function fitting. We theoretically prove that the PBSG method is stable with respect to the metric of 1-Wasserstein distance defined on the PD space. The proposed method was tested on a synthetic data set, data sets of randomly generated PDs, data of a dynamical system, and 3D CAD models, showing its effectiveness and efficiency
Deep neural network solution of the electronic Schrödinger equation
Authors: Jan Hermann, Zeno Schätzle, Frank Noé
Date: 2019-09-16 00:00:00
Tasks: valid

[New and updated results were published in Nature Chemistry, doi:10.1038/s41557-020-0544-y.] The electronic Schr\"odinger equation describes fundamental properties of molecules and materials, but can only be solved analytically for the hydrogen atom. The numerically exact full configuration-interaction method is exponentially expensive in the number of electrons. Quantum Monte Carlo is a possible way out: it scales well to large molecules, can be parallelized, and its accuracy has, as yet, only been limited by the flexibility of the used wave function ansatz. Here we propose PauliNet, a deep-learning wave function ansatz that achieves nearly exact solutions of the electronic Schr\"odinger equation. PauliNet has a multireference Hartree-Fock solution built in as a baseline, incorporates the physics of valid wave functions, and is trained using variational quantum Monte Carlo (VMC). PauliNet outperforms comparable state-of-the-art VMC ansatzes for atoms, diatomic molecules and a strongly-correlated hydrogen chain by a margin and is yet computationally efficient. We anticipate that thanks to the favourable scaling with system size, this method may become a new leading method for highly accurate electronic-strucutre calculations on medium-sized molecular systems.
Learning from Bandit Feedback: An Overview of the State-of-the-art
Authors: Olivier Jeunen, Dmytro Mykhaylov, David Rohde, Flavian vasile, Alexandre Gilotte, Martin Bompaire
Date: 2019-09-18 00:00:00
Tasks: counterfactual, Recommendation Systems

In machine learning we often try to optimise a decision rule that would have worked well over a historical dataset; this is the so called empirical risk minimisation principle. In the context of learning from recommender system logs, applying this principle becomes a problem because we do not have available the reward of decisions we did not do. In order to handle this "bandit-feedback" setting, several Counterfactual Risk Minimisation (CRM) methods have been proposed in recent years, that attempt to estimate the performance of different policies on historical data. Through importance sampling and various variance reduction techniques, these methods allow more robust learning and inference than classical approaches. It is difficult to accurately estimate the performance of policies that frequently perform actions that were infrequently done in the past and a number of different types of estimators have been proposed. In this paper, we review several methods, based on different off-policy estimators, for learning from bandit feedback. We discuss key differences and commonalities among existing approaches, and compare their empirical performance on the RecoGym simulation environment. To the best of our knowledge, this work is the first comparison study for bandit algorithms in a recommender system setting.
Exploring Bit-Slice Sparsity in Deep Neural Networks for Efficient ReRAM-Based Deployment
Authors: Jingyang Zhang, Huanrui Yang, Fan Chen, Yitu Wang, Hai Li
Date: 2019-09-18 00:00:00

Emerging resistive random-access memory (ReRAM) has recently been intensively investigated to accelerate the processing of deep neural networks (DNNs). Due to the in-situ computation capability, analog ReRAM crossbars yield significant throughput improvement and energy reduction compared to traditional digital methods. However, the power hungry analog-to-digital converters (ADCs) prevent the practical deployment of ReRAM-based DNN accelerators on end devices with limited chip area and power budget. We observe that due to the limited bit-density of ReRAM cells, DNN weights are bit sliced and correspondingly stored on multiple ReRAM bitlines. The accumulated current on bitlines resulted by weights directly dictates the overhead of ADCs. As such, bitwise weight sparsity rather than the sparsity of the full weight, is desirable for efficient ReRAM deployment. In this work, we propose bit-slice L1, the first algorithm to induce bit-slice sparsity during the training of dynamic fixed-point DNNs. Experiment results show that our approach achieves 2x sparsity improvement compared to previous algorithms. The resulting sparsity allows the ADC resolution to be reduced to 1-bit of the most significant bit-slice and down to 3-bit for the others bits, which significantly speeds up processing and reduces power and area overhead.
Bias In, Bias Out? Evaluating the Folk Wisdom
Authors: Ashesh Rambachan, Jonathan Roth
Date: 2019-09-18 00:00:00

We evaluate the folk wisdom that algorithmic decision rules trained on data produced by biased human decision-makers necessarily reflect this bias. We consider a setting where training labels are only generated if a biased decision-maker takes a particular action, and so "biased" training data arise due to discriminatory selection into the training data. In our baseline model, the more biased the decision-maker is against a group, the more the algorithmic decision rule favors that group. We refer to this phenomenon as "bias reversal." We then clarify the conditions that give rise to bias reversal. Whether a prediction algorithm reverses or inherits bias depends critically on how the decision-maker affects the training data as well as the label used in training. We illustrate our main theoretical results in a simulation study applied to the New York City Stop, Question and Frisk dataset.
Measure Contribution of Participants in Federated Learning
Authors: Guan Wang, Charlie Xiaoqian Dang, Ziye Zhou
Date: 2019-09-17 00:00:00
Tasks: BIG-bench Machine Learning, Feature Importance, Federated Learning

Federated Machine Learning (FML) creates an ecosystem for multiple parties to collaborate on building models while protecting data privacy for the participants. A measure of the contribution for each party in FML enables fair credits allocation. In this paper we develop simple but powerful techniques to fairly calculate the contributions of multiple parties in FML, in the context of both horizontal FML and vertical FML. For Horizontal FML we use deletion method to calculate the grouped instance influence. For Vertical FML we use Shapley Values to calculate the grouped feature importance. Our methods open the door for research in model contribution and credit allocation in the context of federated machine learning.
Defending against Machine Learning based Inference Attacks via Adversarial Examples: Opportunities and Challenges
Authors: Jinyuan Jia, Neil Zhenqiang Gong
Date: 2019-09-17 00:00:00
Tasks: BIG-bench Machine Learning, Inference Attack

As machine learning (ML) becomes more and more powerful and easily accessible, attackers increasingly leverage ML to perform automated large-scale inference attacks in various domains. In such an ML-equipped inference attack, an attacker has access to some data (called public data) of an individual, a software, or a system; and the attacker uses an ML classifier to automatically infer their private data. Inference attacks pose severe privacy and security threats to individuals and systems. Inference attacks are successful because private data are statistically correlated with public data, and ML classifiers can capture such statistical correlations. In this chapter, we discuss the opportunities and challenges of defending against ML-equipped inference attacks via adversarial examples. Our key observation is that attackers rely on ML classifiers in inference attacks. The adversarial machine learning community has demonstrated that ML classifiers have various vulnerabilities. Therefore, we can turn the vulnerabilities of ML into defenses against inference attacks. For example, ML classifiers are vulnerable to adversarial examples, which add carefully crafted noise to normal examples such that an ML classifier makes predictions for the examples as we desire. To defend against inference attacks, we can add carefully crafted noise into the public data to turn them into adversarial examples, such that attackers' classifiers make incorrect predictions for the private data. However, existing methods to construct adversarial examples are insufficient because they did not consider the unique challenges and requirements for the crafted noise at defending against inference attacks. In this chapter, we take defending against inference attacks in online social networks as an example to illustrate the opportunities and challenges.
k-Relevance Vectors: Considering Relevancy Beside Nearness
Authors: Sara Hosseinzadeh Kassani, Farhood Rismanchian, Peyman Hosseinzadeh Kassani
Date: 2019-09-18 00:00:00
Tasks: Classification, General Classification

This study combines two different learning paradigms, k-nearest neighbor (k-NN) rule, as memory-based learning paradigm and relevance vector machines (RVM), as statistical learning paradigm. This combination is performed in kernel space and is called k-relevance vector (k-RV). The purpose is to improve the performance of k-NN rule. The proposed model significantly prunes irrelevant attributes. We also introduced a new parameter, responsible for early stopping of iterations in RVM. We show that the new parameter improves the classification accuracy of k-RV. Intensive experiments are conducted on several classification datasets from University of California Irvine (UCI) repository and two real datasets from computer vision domain. The performance of k-RV is highly competitive compared to a few state-of-the-arts in terms of classification accuracy.
Transfer Learning with Dynamic Distribution Adaptation
Authors: Jindong Wang, Yiqiang Chen, Wenjie Feng, Han Yu, Meiyu Huang, Qiang Yang
Date: 2019-09-17 00:00:00
Tasks: Domain Adaptation, image-classification, Image Classification, Sentiment Analysis, Transfer Learning

Transfer learning aims to learn robust classifiers for the target domain by leveraging knowledge from a source domain. Since the source and the target domains are usually from different distributions, existing methods mainly focus on adapting the cross-domain marginal or conditional distributions. However, in real applications, the marginal and conditional distributions usually have different contributions to the domain discrepancy. Existing methods fail to quantitatively evaluate the different importance of these two distributions, which will result in unsatisfactory transfer performance. In this paper, we propose a novel concept called Dynamic Distribution Adaptation (DDA), which is capable of quantitatively evaluating the relative importance of each distribution. DDA can be easily incorporated into the framework of structural risk minimization to solve transfer learning problems. On the basis of DDA, we propose two novel learning algorithms: (1) Manifold Dynamic Distribution Adaptation (MDDA) for traditional transfer learning, and (2) Dynamic Distribution Adaptation Network (DDAN) for deep transfer learning. Extensive experiments demonstrate that MDDA and DDAN significantly improve the transfer learning performance and setup a strong baseline over the latest deep and adversarial methods on digits recognition, sentiment analysis, and image classification. More importantly, it is shown that marginal and conditional distributions have different contributions to the domain divergence, and our DDA is able to provide good quantitative evaluation of their relative importance which leads to better performance. We believe this observation can be helpful for future research in transfer learning.
No-Regret Learning in Unknown Games with Correlated Payoffs
Authors: Pier Giuseppe Sessa, Ilija Bogunovic, Maryam Kamgarpour, Andreas Krause
Date: 2019-09-18 00:00:00
Proceeding: NeurIPS 2019 12
Tasks: Gaussian Processes, Movie Recommendation

We consider the problem of learning to play a repeated multi-agent game with an unknown reward function. Single player online learning algorithms attain strong regret bounds when provided with full information feedback, which unfortunately is unavailable in many real-world scenarios. Bandit feedback alone, i.e., observing outcomes only for the selected action, yields substantially worse performance. In this paper, we consider a natural model where, besides a noisy measurement of the obtained reward, the player can also observe the opponents' actions. This feedback model, together with a regularity assumption on the reward function, allows us to exploit the correlations among different game outcomes by means of Gaussian processes (GPs). We propose a novel confidence-bound based bandit algorithm GP-MW, which utilizes the GP model for the reward function and runs a multiplicative weight (MW) method. We obtain novel kernel-dependent regret bounds that are comparable to the known bounds in the full information setting, while substantially improving upon the existing bandit results. We experimentally demonstrate the effectiveness of GP-MW in random matrix games, as well as real-world problems of traffic routing and movie recommendation. In our experiments, GP-MW consistently outperforms several baselines, while its performance is often comparable to methods that have access to full information feedback.
Learning Discrepancy Models From Experimental Data
Authors: Kadierdan Kaheman, Eurika Kaiser, Benjamin Strom, J. Nathan Kutz, Steven L. Brunton
Date: 2019-09-18 00:00:00
Tasks: Friction

First principles modeling of physical systems has led to significant technological advances across all branches of science. For nonlinear systems, however, small modeling errors can lead to significant deviations from the true, measured behavior. Even in mechanical systems, where the equations are assumed to be well-known, there are often model discrepancies corresponding to nonlinear friction, wind resistance, etc. Discovering models for these discrepancies remains an open challenge for many complex systems. In this work, we use the sparse identification of nonlinear dynamics (SINDy) algorithm to discover a model for the discrepancy between a simplified model and measurement data. In particular, we assume that the model mismatch can be sparsely represented in a library of candidate model terms. We demonstrate the efficacy of our approach on several examples including experimental data from a double pendulum on a cart. We further design and implement a feed-forward controller in simulations, showing improvement with a discrepancy model.
Fine-Tuning Language Models from Human Preferences
Authors: Daniel M. Ziegler, Nisan Stiennon, Jeffrey Wu, Tom B. Brown, Alec Radford, Dario Amodei, Paul Christiano, Geoffrey Irving
Date: 2019-09-18 00:00:00
Tasks: Descriptive, Language Modelling, Reinforcement Learning, Reinforcement Learning (RL)

Reward learning enables the application of reinforcement learning (RL) to tasks where reward is defined by human judgment, building a model of reward by asking humans questions. Most work on reward learning has used simulated environments, but complex information about values is often expressed in natural language, and we believe reward learning for language is a key to making RL practical and safe for real-world tasks. In this paper, we build on advances in generative pretraining of language models to apply reward learning to four natural language tasks: continuing text with positive sentiment or physically descriptive language, and summarization tasks on the TL;DR and CNN/Daily Mail datasets. For stylistic continuation we achieve good results with only 5,000 comparisons evaluated by humans. For summarization, models trained with 60,000 comparisons copy whole sentences from the input but skip irrelevant preamble; this leads to reasonable ROUGE scores and very good performance according to our human labelers, but may be exploiting the fact that labelers rely on simple heuristics.
Sample Efficient Policy Gradient Methods with Recursive Variance Reduction
Authors: Pan Xu, Felicia Gao, Quanquan Gu
Date: 2019-09-18 00:00:00
Proceeding: ICLR 2020 1
Tasks: Policy Gradient Methods, reinforcement-learning, Reinforcement Learning, Reinforcement Learning (RL)

Improving the sample efficiency in reinforcement learning has been a long-standing research problem. In this work, we aim to reduce the sample complexity of existing policy gradient methods. We propose a novel policy gradient algorithm called SRVR-PG, which only requires $O(1/\epsilon^{3/2})$ episodes to find an $\epsilon$-approximate stationary point of the nonconcave performance function $J(\boldsymbol{\theta})$ (i.e., $\boldsymbol{\theta}$ such that $\|\nabla J(\boldsymbol{\theta})\|_2^2\leq\epsilon$). This sample complexity improves the existing result $O(1/\epsilon^{5/3})$ for stochastic variance reduced policy gradient algorithms by a factor of $O(1/\epsilon^{1/6})$. In addition, we also propose a variant of SRVR-PG with parameter exploration, which explores the initial policy parameter from a prior probability distribution. We conduct numerical experiments on classic control problems in reinforcement learning to validate the performance of our proposed algorithms.
Neural Population Coding for Effective Temporal Classification
Authors: Zihan Pan, Jibin Wu, Yansong Chua, Malu Zhang, Haizhou Li
Date: 2019-09-12 00:00:00
Tasks: Classification, General Classification

Neural encoding plays an important role in faithfully describing the temporally rich patterns, whose instances include human speech and environmental sounds. For tasks that involve classifying such spatio-temporal patterns with the Spiking Neural Networks (SNNs), how these patterns are encoded directly influence the difficulty of the task. In this paper, we compare several existing temporal and population coding schemes and evaluate them on both speech (TIDIGITS) and sound (RWCP) datasets. We show that, with population neural codings, the encoded patterns are linearly separable using the Support Vector Machine (SVM). We note that the population neural codings effectively project the temporal information onto the spatial domain, thus improving linear separability in the spatial dimension, achieving an accuracy of 95\% and 100\% for TIDIGITS and RWCP datasets classified using the SVM, respectively. This observation suggests that an effective neural coding scheme greatly simplifies the classification problem such that a simple linear classifier would suffice. The above datasets are then classified using the Tempotron, an SNN-based classifier. SNN classification results agree with the SVM findings that population neural codings help to improve classification accuracy. Hence, other than the learning algorithm, effective neural encoding is just as important as an SNN designed to recognize spatio-temporal patterns. It is an often neglected but powerful abstraction that deserves further study.
Generating Local Search Neighborhood with Synthesized Logic Programs
Authors: Mateusz Ślażyński, Salvador Abreu, Grzegorz J. Nalepa
Date: 2019-09-18 00:00:00
Tasks: Traveling Salesman Problem

Local Search meta-heuristics have been proven a viable approach to solve difficult optimization problems. Their performance depends strongly on the search space landscape, as defined by a cost function and the selected neighborhood operators. In this paper we present a logic programming based framework, named Noodle, designed to generate bespoke Local Search neighborhoods tailored to specific discrete optimization problems. The proposed system consists of a domain specific language, which is inspired by logic programming, as well as a genetic programming solver, based on the grammar evolution algorithm. We complement the description with a preliminary experimental evaluation, where we synthesize efficient neighborhood operators for the traveling salesman problem, some of which reproduce well-known results.