On the Difficulty of Designing Good Classifiers

DOI10.1137/S009753979630814XMaRDI QIDQ4507352zbMATHOpenAlexFDO

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

parameterized complexityhardness of approximationlinear decision tree

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)

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