On the learnability of discrete distributions

DOI10.1145/195058.195155zbMATH Open1345.68252OpenAlexW2095374884MaRDI QIDQ2817618FDOQ2817618

Authors: Michael Kearns, Yishay Mansour, Dana Ron, Ronitt Rubinfeld, Robert E. Schapire, Linda 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

Recommendations

• PAC learning of probability distributions over a discrete domain.
• scientific article; zbMATH DE number 67636
• Learning Poisson binomial distributions
• Learning from satisfying assignments
• Efficient distribution-free learning of probabilistic concepts

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05)

Cited In (42)

• Learning fixed-dimension linear thresholds from fragmented data
• Population recovery and partial identification
• Title not available (Why is that?)
• Inclusion-exclusion: exact and approximate
• PAC-learnability of probabilistic deterministic finite state automata in terms of variation distance
• Equivalences between learning of data and probability distributions, and their applications
• Title not available (Why is that?)
• Maximum selection and sorting with adversarial comparators
• Separating Populations with Wide Data: A Spectral Analysis
• Learning Poisson binomial distributions
• Application of a generalization of Russo's formula to learning from multiple random oracles
• Knowing what doesn't matter: exploiting the omission of irrelevant data
• On the learnability and usage of acyclic probabilistic finite automata
• A spectral algorithm for learning hidden Markov models
• Efficient distribution-free learning of probabilistic concepts
• Learnability with respect to fixed distributions
• Separating populations with wide data: a spectral analysis
• Natural language grammar induction with a generative constituent-context model
• Learning Structure Illuminates Black Boxes – An Introduction to Estimation of Distribution Algorithms
• Private data release via learning thresholds
• Probably Approximate Learning over Classes of Distributions
• Sampling correctors
• The minimax learning rates of normal and Ising undirected graphical models
• Learning distributions by their density levels: A paradigm for learning without a teacher
• The power of amnesia: Learning probabilistic automata with variable memory length
• Cryptography with constant input locality
• \textsc{PAutomaC}: a probabilistic automata and hidden Markov models learning competition
• A comparison of collapsed Bayesian methods for probabilistic finite automata
• Adaptively learning probabilistic deterministic automata from data streams
• Spectral learning of weighted automata. A forward-backward perspective
• Statistical estimation of ergodic Markov chain kernel over discrete state space
• Links between probabilistic automata and hidden Markov models: probability distributions, learning models and induction algorithms
• Relative entropy and envy-free allocation
• On the complexity of computational problems regarding distributions
• Robust Estimators in High-Dimensions Without the Computational Intractability
• Learning Mixtures of Product Distributions over Discrete Domains
• Approximate minimization of weighted tree automata
• Learning discrete distributions from untrusted batches
• Learning nonsingular phylogenies and hidden Markov models
• PAC learning of probability distributions over a discrete domain.
• Efficient learning of typical finite automata from random walks
• Instance optimal learning of discrete distributions

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2817618)