Regret Bounds for Hierarchical Classification with Linear-Threshold Functions
Abstract
We study the problem of classifying data in a given taxonomy when classifications associated with multiple and/or partial paths are allowed. We introduce an incremental algorithm using a linear-threshold classifier at each node of the taxonomy. These classifiers are trained and evaluated in a hierarchical top-down fashion. We then define a hierachical and parametric data model and prove a bound on the probability that our algorithm guesses the wrong multilabel for a random instance compared to the same probability when the true model parameters are known. Our bound decreases exponentially with the number of training examples and depends in a detailed way on the interaction between the process parameters and the taxonomy structure. Preliminary experiments on real-world data provide support to our theoretical results.
Cite
Text
Cesa-Bianchi et al. "Regret Bounds for Hierarchical Classification with Linear-Threshold Functions." Annual Conference on Computational Learning Theory, 2004. doi:10.1007/978-3-540-27819-1_7Markdown
[Cesa-Bianchi et al. "Regret Bounds for Hierarchical Classification with Linear-Threshold Functions." Annual Conference on Computational Learning Theory, 2004.](https://mlanthology.org/colt/2004/cesabianchi2004colt-regret/) doi:10.1007/978-3-540-27819-1_7BibTeX
@inproceedings{cesabianchi2004colt-regret,
title = {{Regret Bounds for Hierarchical Classification with Linear-Threshold Functions}},
author = {Cesa-Bianchi, Nicolò and Conconi, Alex and Gentile, Claudio},
booktitle = {Annual Conference on Computational Learning Theory},
year = {2004},
pages = {93-108},
doi = {10.1007/978-3-540-27819-1_7},
url = {https://mlanthology.org/colt/2004/cesabianchi2004colt-regret/}
}