2016/05/17 by Anna Choromanska, Choromanska, Anna, Krzysztof Choromański +3
Computer Science · #Adversarial Robustness in Machine Learning #FOS: Computer and information sciences #Imbalanced Data Classification Techniques #Machine Learning (cs.LG) #Machine Learning and Algorithms #Machine Learning and Data Classification
paper · pdf · doi:10.48550/arxiv.1605.05223
openalex publication_date 2016/05/17 · openalex created_date 2022/10/01 · openalex updated_date 2026/07/28
We analyze the performance of the top-down multiclass classification\nalgorithm for decision tree learning called LOMtree, recently proposed in the\nliterature Choromanska and Langford (2014) for solving efficiently\nclassification problems with very large number of classes. The algorithm online\noptimizes the objective function which simultaneously controls the depth of the\ntree and its statistical accuracy. We prove important properties of this\nobjective and explore its connection to three well-known entropy-based decision\ntree objectives, i.e. Shannon entropy, Gini-entropy and its modified version,\nfor which instead online optimization schemes were not yet developed. We show,\nvia boosting-type guarantees, that maximizing the considered objective leads\nalso to the reduction of all of these entropy-based objectives. The bounds we\nobtain critically depend on the strong-concavity properties of the\nentropy-based criteria, where the mildest dependence on the number of classes\n(only logarithmic) corresponds to the Shannon entropy.\n