Improved MCMC sampling methods for estimating weighted sums in Winnow with application to DNF learning

DOI10.1007/s10994-008-5063-9zbMath1470.68189MaRDI QIDQ1009287

Stephen D. Scott, Qingping Tao

Publication date: 31 March 2009

Published in: Machine Learning (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10994-008-5063-9

zbMATH Keywords

Markov chain Monte Carlo; Winnow; DNF

Mathematics Subject Classification ID

65C05: Monte Carlo methods

68T05: Learning and adaptive systems in artificial intelligence

Uses Software

• UCI-ml
• C4.5

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Tracking the best disjunction
• The weighted majority algorithm
• Solving the multiple instance problem with axis-parallel rectangles.
• More efficient PAC-learning of DNF with membership queries under the uniform distribution
• On approximating weighted sums with exponentially many terms
• Learning DNF in time \(2^{\widetilde O(n^{1/3})}\)
• General and efficient multisplitting of numerical attributes
• Improved boosting algorithms using confidence-rated predictions
• Weakly learning DNF and characterizing statistical query learning using Fourier analysis
• Stochastic Relaxation, Gibbs Distributions, and the Bayesian Restoration of Images
• Miscellanea. Peskun's theorem and a modified discrete-state Gibbs sampler
• Agnostic learning of geometric patterns