Linear classifiers are nearly optimal when hidden variables have diverse effects

DOI10.1007/S10994-011-5262-7MaRDI QIDQ420914zbMATH OpenOpenAlexFDO

Authors Nader H. Bshouty, Philip M. Long

Publication date 23 May 2012

Published in Machine Learning (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10994-011-5262-7

zbMATH Keywords

Bayes optimal rulehidden variableslearning theorylinear classification

Mathematics Subject Classification ID

Classification and discrimination; cluster analysis (statistical aspects) (62H30) Learning and adaptive systems in artificial intelligence (68T05)

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.

Recommendations

• Linear concepts and hidden variables
• On the Difficulty of Designing Good Classifiers
• Some theory for Fisher's linear discriminant function, `naive Bayes', and some alternatives when there are many more variables than observations
• When a Constant Classifier is as Good as Any Linear Classifier
• scientific article; zbMATH DE number 1759563

Cites work

• 10.1162/jmlr.2003.3.4-5.993
• Balls and bins: A study in negative dependence
• BoosTexter: A boosting-based system for text categorization
• Classification using hierarchical Naïve Bayes models
• Convergence of stochastic processes
• Convexity, Classification, and Risk Bounds
• Every linear threshold function has a low-weight approximator
• Evolutionary trees can be learned in polynomial time in the two-state general Markov model
• Hierarchical latent class models for cluster analysis
• scientific article; zbMATH DE number 437558 (Why is no real title available?)
• scientific article; zbMATH DE number 1833421 (Why is no real title available?)
• scientific article; zbMATH DE number 893887 (Why is no real title available?)
• scientific article; zbMATH DE number 3366301 (Why is no real title available?)
• Latent semantic indexing: A probabilistic analysis
• Linear classifiers are nearly optimal when hidden variables have diverse effects
• On the optimality of the simple Bayesian classifier under zero-one loss
• Pattern classification.
• Pegasos: primal estimated sub-gradient solver for SVM
• Probability Inequalities for Sums of Bounded Random Variables
• Probably almost Bayes decisions
• Some theory for Fisher's linear discriminant function, `naive Bayes', and some alternatives when there are many more variables than observations
• Statistical behavior and consistency of classification methods based on convex risk minimization.
• Unsupervised learning by probabilistic latent semantic analysis

Cited in

(6)

• Scrutinizing XAI using linear ground-truth data with suppressor variables
• Masking effects on linear regression in multi-class classification
• When a Constant Classifier is as Good as Any Linear Classifier
• Linear classifiers are nearly optimal when hidden variables have diverse effects
• scientific article; zbMATH DE number 2084376 (Why is no real title available?)
• scientific article; zbMATH DE number 1759563 (Why is no real title available?)

Describes a project that uses

Uses Software

• Pegasos
• BoosTexter

This page was built for publication: Linear classifiers are nearly optimal when hidden variables have diverse effects

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