2021/02/16 by Assaf Ben-Yishai, Ben-Yishai, Assaf, Or Ordentlich +1
Computer Science · Decision Sciences · #Advanced Bandit Algorithms Research #Data Stream Mining Techniques #FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT) #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Spam and Phishing Detection #Statistics Theory (math.ST)
paper · pdf · doi:10.48550/arxiv.2102.08184
openalex publication_date 2021/02/16 · openalex created_date 2022/07/25 · openalex updated_date 2026/07/28
The construction of multiclass classifiers from binary elements is studied in\nthis paper, and performance is quantified by the regret, defined with respect\nto the Bayes optimal log-loss. We discuss two known methods. The first is one\nvs. all (OVA), for which we prove that the multiclass regret is upper bounded\nby the sum of binary regrets of the constituent classifiers. The second is\nhierarchical classification, based on a binary tree. For this method we prove\nthat the multiclass regret is exactly a weighted sum of constituent binary\nregrets where the weighing is determined by the tree structure.\n We also introduce a leverage-hierarchical classification method, which\npotentially yields smaller log-loss and regret. The advantages of these\nclassification methods are demonstrated by simulation on both synthetic and\nreal-life datasets.\n