Regret Bounds for Hierarchical Classification with Linear-Threshold Functions
Lists
Only you see this
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.
BibTeX
@inproceedings{cesabianchi2004regret,
author = {Nicolò Cesa-Bianchi and Alex Conconi and Claudio Gentile},
title = {{Regret Bounds for Hierarchical Classification with Linear-Threshold Functions}},
booktitle = {Conference on Learning Theory},
year = {2004},
doi = {10.1007/978-3-540-27819-1\_7},
}Loading related content...