On the Difficulty of Designing Good Classifiers

DOI10.1137/S009753979630814XMaRDI QIDQ4507352zbMATH OpenOpenAlexFDO

Authors Vincent Mirelli, Michelangelo Grigni, Christos Papadimitriou

Publication date 18 October 2000

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/s009753979630814x

zbMATH Keywords

hardness of approximationlinear decision treeparameterized complexity

Mathematics Subject Classification ID

Classification and discrimination; cluster analysis (statistical aspects) (62H30) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• On a minimum linear classification problem
• On a minimum linear classification problem
• On the approximability of minimizing nonzero variables or unsatisfied relations in linear systems
• Minimizing the error of linear separators on linearly inseparable data
• Lower bounds on learning decision lists and trees

Cited in

(12)

• On the approximability of minimizing nonzero variables or unsatisfied relations in linear systems
• Decision tree classification with bounded number of errors
• On the combinatorics of the 2-class classification problem
• Cellular tree classifiers
• Linear classifiers are nearly optimal when hidden variables have diverse effects
• Minimizing the error of linear separators on linearly inseparable data
• scientific article; zbMATH DE number 1759553 (Why is no real title available?)
• Separability of point sets by \(k\)-level linear classification trees
• Point probe decision trees for geometric concept classes
• On a minimum linear classification problem
• On the difficulty of designing good classifiers
• Geometric problems in machine learning

This page was built for publication: On the Difficulty of Designing Good Classifiers

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