Linear classifiers are nearly optimal when hidden variables have diverse effects
type: Item
instance of: scholarly article
title: Linear classifiers are nearly optimal when hidden variables have diverse effects
zbMATH Open document ID: 1267.68175
author: Nader H. Bshouty
author: Philip M. Long
published in: Machine Learning
publication date: 2012-05-23T00:00:00Z
review text: In this paper the authors focus on showing that a linear classifier can provide a good approximation even if the optimal classifier is much more complex. To prove this hypothesis, they analyze a classification problem in which data is generated by a two-tiered random process. Concretely, they prove that, if the hidden variables have non-eligible effects on many observed variables, a linear classifier accurately approximates the error rate of the optimal classifier (Bayes). Moreover, the hinge loss of the linear classifier is not much more than the Bayes error rate.
reviewed by: Florin Gorunescu
Mathematics Subject Classification ID: 68T05
Mathematics Subject Classification ID: 62H30
zbMATH DE Number: 6037842
zbMATH Keywords: learning theory
zbMATH Keywords: Bayes optimal rule
zbMATH Keywords: linear classification
zbMATH Keywords: hidden variables
describes a project that uses: Pegasos
describes a project that uses: BoosTexter
MaRDI profile type: Publication
full work available at URL: s10994-011-5262-7
OpenAlex ID: W2066953979
cites work: Probably almost Bayes decisions
cites work: Convexity, Classification, and Risk Bounds
cites work: Some theory for Fisher's linear discriminant function, `naive Bayes', and some alternatives when there are many more variables than observations
cites work: 10.1162/jmlr.2003.3.4-5.993
cites work: Evolutionary trees can be learned in polynomial time in the two-state general Markov model
cites work: Q4881152
cites work: On the optimality of the simple Bayesian classifier under zero-one loss
cites work: Balls and bins: A study in negative dependence
cites work: Pattern classification.
cites work: Probability Inequalities for Sums of Bounded Random Variables
cites work: Unsupervised learning by probabilistic latent semantic analysis
cites work: Classification using hierarchical Naïve Bayes models
cites work: Q5639147
cites work: Latent semantic indexing: A probabilistic analysis
cites work: Q4780802
cites work: Convergence of stochastic processes
cites work: BoosTexter: A boosting-based system for text categorization
cites work: Q3140437
cites work: Every linear threshold function has a low-weight approximator
cites work: Pegasos: primal estimated sub-gradient solver for SVM
cites work: Q3093200
cites work: Statistical behavior and consistency of classification methods based on convex risk minimization.
DOI: 10.1007/S10994-011-5262-7
description: scientific article; zbMATH DE number 6037842