检索结果-内蒙古大学图书馆

Model-Agnostic Confidence Intervals for Feature Importance: A Fast and Powerful Approach Using Minipatch Ensembles

学校读者我要写书评

暂无评论

arXiv 2022年

作者： Gan, Luqin Zheng, Lili Allen, Genevera I. Department of Statistics Rice University HoustonTX United States Department of Electrical and Computer Engineering Rice University HoustonTX United States Departments of Electrical and Computer Engineering Statistics and Computer Science Rice University HoustonTX United States Jan and Dan Duncan Neurological Research Institute Baylor College of Medicine HoustonTX United States

To promote new scientific discoveries from complex data sets, feature importance inference has been a long-standing statistical problem. Instead of testing for parameters that are only interpretable for specific models, there has been increasing interest in model-agnostic methods, often in the form of feature occlusion or leave-one-covariate-out (LOCO) inference. Existing approaches often make distributional assumptions, which can be difficult to verify in practice, or require model refitting and data splitting, which are computationally intensive and lead to losses in power. In this work, we develop a novel, mostly model-agnostic and distribution-free inference framework for feature importance that is computationally efficient and statistically powerful. Our approach is fast as we avoid model refitting by leveraging a form of random observation and feature subsampling called minipatch ensembles;this approach also improves statistical power by avoiding data splitting. Our framework can be applied on tabular data and with any machine learning algorithm, together with minipatch ensembles, for regression and classification tasks. Despite the dependencies induced by using minipatch ensembles, we show that our approach provides asymptotic coverage for the feature importance score of any model under mild assumptions. Finally, our same procedure can also be leveraged to provide valid confidence intervals for predictions, hence providing fast, simultaneous quantification of the uncertainty of both predictions and feature importance. We validate our intervals on a series of synthetic and real data examples, including non-linear settings, showing that our approach detects the correct important features and exhibits many computational and statistical advantages over existing methods. © 2022, CC BY-NC-SA.

关键词： learning algorithms

A Characterization of List Learnability

学校读者我要写书评

暂无评论

arXiv 2022年

作者： Charikar, Moses Pabbaraju, Chirag Stanford University United States

A classical result in learning theory shows the equivalence of PAC learnability of binary hypothesis classes and the finiteness of VC dimension. Extending this to the multiclass setting was an open problem, which was settled in a recent breakthrough result characterizing multiclass PAC learnability via the DS dimension introduced earlier by Daniely and Shalev-Shwartz. In this work we consider list PAC learning where the goal is to output a list of k predictions. List learning algorithms have been developed in several settings before and indeed, list learning played an important role in the recent characterization of multiclass learnability. In this work we ask: when is it possible to k-list learn a hypothesis class? We completely characterize k-list learnability in terms of a generalization of DS dimension that we call the k-DS dimension. Generalizing the recent characterization of multiclass learnability, we show that a hypothesis class is k-list learnable if and only if the k-DS dimension is finite. © 2022, CC BY.

关键词： learning algorithms

Robust Neural Particle Identification Models

学校读者我要写书评

暂无评论

arXiv 2022年

作者： Temirkhanov, Aziz Ryzhikov, Artem Derkach, Denis Hushchyn, Mikhail Kazeev, Nikita Mokhnenko, Sergei HSE University 20 Myasnitskaya st. Moscow101000 Russia

The volume of data processed by the Large Hadron Collider experiments demands sophisticated selection rules typically based on machine learning algorithms. One of the shortcomings of these approaches is their profound sensitivity to the biases in training samples. In the case of particle identification (PID), this might lead to degradation of the efficiency for some decays not present in the training dataset due to differences in input kinematic distributions. In this talk, we propose a method based on the Common Specific Decomposition that takes into account individual decays and possible misshapes in the training data by disentangling common and decay specific components of the input feature set. We show that the proposed approach reduces the rate of efficiency degradation for the PID algorithms for the decays reconstructed in the LHCb detector. © 2022, CC BY.

关键词： learning algorithms

Vision-and-Language Navigation: A Survey of Tasks, Methods, and Future Directions

学校读者我要写书评

暂无评论

arXiv 2022年

作者： Gu, Jing Stefani, Eliana Wu, Qi Thomason, Jesse Wang, Xin Eric University of California Santa Cruz United States The University of Adelaide Australia University of Southern California United States

A long-term goal of AI research is to build intelligent agents that can communicate with humans in natural language, perceive the environment, and perform real-world tasks. Vision- and-Language Navigation (VLN) is a fundamental and interdisciplinary research topic towards this goal, and receives increasing attention from natural language processing, computer vision, robotics, and machine learning communities. In this paper, we review contemporary studies in the emerging field of VLN, covering tasks, evaluation metrics, methods, etc. Through structured analysis of current progress and challenges, we highlight the limitations of current VLN and opportunities for future work. This paper serves as a thorough reference for the VLN research community. Copyright © 2022, The Authors. All rights reserved.

关键词： learning algorithms

Strategic Representation

学校读者我要写书评

暂无评论

arXiv 2022年

作者： Nair, Vineet Ghalme, Ganesh Talgam-Cohen, Inbal Rosenfeld, Nir Technion Israel Institute of Technology Haifa Israel Indian Institute of Technology Hyderabad India

Humans have come to rely on machines for reducing excessive information to manageable representations. But this reliance can be abused—strategic machines might craft representations that manipulate their users. How can a user make good choices based on strategic representations? We formalize this as a learning problem, and pursue algorithms for decision-making that are robust to manipulation. In our main setting of interest, the system represents attributes of an item to the user, who then decides whether or not to consume. We model this interaction through the lens of strategic classification (Hardt et al. 2016), reversed: the user, who learns, plays first;and the system, which responds, plays second. The system must respond with representations that reveal ‘nothing but the truth’ but need not reveal the entire truth. Thus, the user faces the problem of learning set functions under strategic subset selection, which presents distinct algorithmic and statistical challenges. Our main result is a learning algorithm that minimizes error despite strategic representations, and our theoretical analysis sheds light on the trade-off between learning effort and susceptibility to manipulation. © 2022, CC BY.

关键词： learning algorithms

ARTIFICIAL INTELLIGENCE AND SPONTANEOUS COLLUSION

学校读者我要写书评

暂无评论

arXiv 2022年

作者： Banchio, Martino Mantegazza, Giacomo Google Research United States Stanford GSB United States 1600 Amphitheatre Parkway Mountain ViewCA94043 United States 655 Knight Way StanfordCA94305 United States

We develop a tractable model for studying strategic interactions between learning algorithms. We uncover a mechanism responsible for the emergence of algorithmic collusion. We observe that algorithms periodically coordinate on actions that are more profitable than static Nash equilibria. This novel collusive channel relies on an endogenous statistical linkage in the algorithms’ estimates which we call spontaneous coupling. The model’s parameters predict whether the statistical linkage will appear, and what market structures facilitate algorithmic collusion. We show that spontaneous coupling can sustain collusion in prices and market shares, complementing experimental findings in the literature. Finally, we apply our results to design algorithmic markets. Copyright © 2022, The Authors. All rights reserved.

关键词： learning algorithms

ONLINE DECENTRALIZED FRANK-WOLFE: FROM THEORETICAL BOUND TO APPLICATIONS IN SMART-BUILDING

学校读者我要写书评

暂无评论

arXiv 2022年

作者： Mitra, Angan Thang, Nguyen Kim Nguyen, Tuan-Anh Trystram, Denis Youssef, Paul Qarnot Computing University Grenoble-Alpes France IBISC University of Evry University Paris-Saclay France LIG INRIA Grenoble INP University Grenoble-Alpes France

The design of decentralized learning algorithms is important in the fast-growing world in which data are distributed over participants with limited local computation resources and communication. In this direction, we propose an online algorithm minimizing non-convex loss functions aggregated from individual data/models distributed over a network. We provide the theoretical performance guarantee of our algorithm and demonstrate its utility on a real life smart building. © 2022, CC BY.

关键词： learning algorithms

Hard-disk computer simulations - a historic perspective

学校读者我要写书评

暂无评论

arXiv 2022年

作者： Li, Botao Nishikawa, Yoshihiko Höllmer, Philipp Carillo, Louis Maggs, A.C. Krauth, Werner Laboratoire de Physique de l’Ecole normale supérieure ENS Université PSL CNRS Sorbonne Université Université de Paris Cité Paris France Graduate School of Information Sciences Tohoku University Sendai980-8579 Japan Physikalisches Institut Bethe Center for Theoretical Physics University of Bonn Nussallee 12 Bonn53115 Germany CNRS Gulliver ESPCI Paris Université PSL 10 rue Vauquelin Paris75005 France

We discuss historic pressure computations for the hard-disk model performed since 1953, and compare them to results that we obtain with a powerful event-chain Monte Carlo and a massively parallel Metropolis algorithm. Like other simple models in the sciences, such as the Drosophila model of biology, the hard-disk model has needed monumental effort to be understood. In particular, we argue that the difficulty of estimating the pressure has not been fully realized in the decades-long controversy over the hard-disk phase-transition scenario. We present the physics of the hard-disk model, the definition of the pressure and its unbiased estimators, several of which are new. We further treat different sampling algorithms and crucial criteria for bounding mixing times in the absence of analytical predictions. Our definite results for the pressure, for up to one million disks, may serve as benchmarks for future sampling algorithms. A synopsis of hard-disk pressure data as well as different versions of the sampling algorithms and pressure estimators are made available in an open-source repository. © 2022, CC BY.

关键词： learning algorithms

Analyzing Robustness of Angluin’s L∗ Algorithm in Presence of Noise

学校读者我要写书评

暂无评论

arXiv 2022年

作者： Khmelnitsky, Igor Haddad, Serge Ye, Lina Barbot, Benoît Bollig, Benedikt Leucker, Martin Neider, Daniel Roy, Rajarshi Université Paris-Saclay CNRS ENS Paris-Saclay INRIA LMF France Université Paris-Saclay CNRS ENS Paris-Saclay CentraleSupélec LMF France Université Paris-Est Créteil France Université Paris-Saclay CNRS ENS Paris-Saclay LMF France Institute for Software Engineering and Programming Languages Universität zu Lübeck Germany Carl von Ossietzky University of Oldenburg Germany Max Planck Institute for Software Systems Kaiserslautern Germany

Angluin’s L∗ algorithm learns the minimal (complete) deterministic finite automaton (DFA) of a regular language using membership and equivalence queries. Its probabilistic approximatively correct (PAC) version substitutes an equivalence query by a large enough set of random membership queries to get a high level confidence to the answer. Thus it can be applied to any kind of (also non-regular) device and may be viewed as an algorithm for synthesizing an automaton abstracting the behavior of the device based on observations. Here we are interested on how Angluin’s PAC learning algorithm behaves for devices which are obtained from a DFA by introducing some noise. More precisely we study whether Angluin’s algorithm reduces the noise and produces a DFA closer to the original one than the noisy device. We propose several ways to introduce the noise: (1) the noisy device inverts the classification of words w.r.t. the DFA with a small probability, (2) the noisy device modifies with a small probability the letters of the word before asking its classification w.r.t. the DFA, and (3) the noisy device combines the classification of a word w.r.t. the DFA and its classification w.r.t. a counter automaton. Our experiments were performed on several hundred DFAs. Our main contributions, bluntly stated, consist in showing that: (1) Angluin’s algorithm behaves well whenever the noisy device is produced by a random process, (2) but poorly with a structured noise, and, that (3) almost surely randomness yields systems with non-recursively enumerable languages. © 2022, CC BY.

关键词： learning algorithms