On approximating weighted sums with exponentially many terms

DOI10.1016/j.jcss.2004.01.006zbMath1074.68050OpenAlexW2137361561MaRDI QIDQ1880781

Lin Li, Deepak Chawla, Stephen D. Scott

Publication date: 1 October 2004

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://digitalcommons.unl.edu/cgi/viewcontent.cgi?article=1007&context=csetechreports

zbMATH Keywords

BoostingWinnowPerceptronDNF learningMarkov chain Monte Carlo approximationMultiplicative weight updatesWeighted Majority

Mathematics Subject Classification ID

Computational learning theory (68Q32) Learning and adaptive systems in artificial intelligence (68T05) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10)

Related Items

Annealing stochastic approximation Monte Carlo algorithm for neural network training, Improved MCMC sampling methods for estimating weighted sums in Winnow with application to DNF learning

Uses Software

• UCI-ml
• AdaBoost.MH
• C4.5

Cites Work

• Unnamed Item
• Unnamed Item
• Optimization by Simulated Annealing
• Random generation of combinatorial structures from a uniform distribution
• The Perceptron algorithm versus Winnow: linear versus logarithmic mistake bounds when few input variables are relevant
• The weighted majority algorithm
• Simple learning algorithms using divide and conquer
• A decision-theoretic generalization of on-line learning and an application to boosting
• Efficient learning with virtual threshold gates
• Solving the multiple instance problem with axis-parallel rectangles.
• Multiple-instance learning of real-valued geometric patterns
• Boosting the margin: a new explanation for the effectiveness of voting methods
• Predicting nearly as well as the best pruning of a planar decision graph.
• More efficient PAC-learning of DNF with membership queries under the uniform distribution
• An efficient extension to mixture techniques for prediction and decision trees
• Improved boosting algorithms using confidence-rated predictions
• Weakly learning DNF and characterizing statistical query learning using Fourier analysis
• A Mildly Exponential Time Algorithm for Approximating the Number of Solutions to a Multidimensional Knapsack Problem
• Improved Bounds for Mixing Rates of Markov Chains and Multicommodity Flow
• How to use expert advice
• Random Walks on Truncated Cubes and Sampling 0-1 Knapsack Solutions
• Equation of State Calculations by Fast Computing Machines
• Agnostic learning of geometric patterns