On the learnability of discrete distributions

DOI10.1145/195058.195155zbMath1345.68252OpenAlexW2095374884MaRDI QIDQ2817618

Yishay Mansour, Robert E. Schapire, Ronitt Rubinfeld, Dana Ron, Michael Kearns, Linda M. Sellie

Publication date: 1 September 2016

Published in: Proceedings of the twenty-sixth annual ACM symposium on Theory of computing - STOC '94 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/195058.195155

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05)

Related Items (33)

PAC learning of probability distributions over a discrete domain. ⋮ Sampling Correctors ⋮ Learning distributions by their density levels: A paradigm for learning without a teacher ⋮ Efficient learning of typical finite automata from random walks ⋮ Inclusion-exclusion: exact and approximate ⋮ Relative entropy and envy-free allocation ⋮ Knowing what doesn't matter: exploiting the omission of irrelevant data ⋮ The minimax learning rates of normal and Ising undirected graphical models ⋮ A spectral algorithm for learning hidden Markov models ⋮ Separating populations with wide data: a spectral analysis ⋮ Statistical estimation of ergodic Markov chain kernel over discrete state space ⋮ Separating Populations with Wide Data: A Spectral Analysis ⋮ Spectral learning of weighted automata. A forward-backward perspective ⋮ Adaptively learning probabilistic deterministic automata from data streams ⋮ \textsc{PAutomaC}: a probabilistic automata and hidden Markov models learning competition ⋮ A comparison of collapsed Bayesian methods for probabilistic finite automata ⋮ Robust Estimators in High-Dimensions Without the Computational Intractability ⋮ PAC-learnability of probabilistic deterministic finite state automata in terms of variation distance ⋮ Application of a Generalization of Russo's Formula to Learning from Multiple Random Oracles ⋮ The power of amnesia: Learning probabilistic automata with variable memory length ⋮ Learning nonsingular phylogenies and hidden Markov models ⋮ Links between probabilistic automata and hidden Markov models: probability distributions, learning models and induction algorithms ⋮ Natural language grammar induction with a generative constituent-context model ⋮ Equivalences between learning of data and probability distributions, and their applications ⋮ On the learnability and usage of acyclic probabilistic finite automata ⋮ Approximate minimization of weighted tree automata ⋮ Cryptography with constant input locality ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Learning fixed-dimension linear thresholds from fragmented data ⋮ Learning Poisson binomial distributions ⋮ Population recovery and partial identification

This page was built for publication: On the learnability of discrete distributions