

![0_image_0.png](0_image_0.png)

tend to cancel out and the power of the relevant classifiers will then increase. We therefore speculate that it would be very hard to consistently beat all-pairs decompositions with very large number of classes. Nevertheless,a desirable property of a decomposition scheme is *scalability***, which allows for efficient handling of** large number of classes (and datasets). For example, one can hypothesize useful authorship determination applications, which need to determine between thousands or even millions of authors. While balanced hierarchical decomposition will be able to scale up to these dimensions, the O(k 2**) complexity of the all-pairs**
method would probably start to form a computational bottleneck.

## References

Antos et al.][1999]LowerAntosDG99 Antos, A., Devroye, L., & Gyorfi, L. (1999). Lower bounds for bayes error estimation. *Pattern Analysis and Machine Intelligence*, 21**, 643–645.**
Burrows][1987]Burrows87 Burrows, J. (1987). Word patterns and story shapes: The statistical analysis of narative style. *Literary and Linguistic Computing*, 2**, 61–70.**
Cover and Thomas][1991]CoverT91 Cover, T., &
Thomas, J. (1991). *Elements of information theory*. John Wiley & Sons, Inc.
Dekel and Singer][2002]DekelS02 Dekel, O., & Singer, Y. (2002). Multiclass learning by probabilistic embedding. *Neural Information Processing Systems*
(NIPS).

Dietterich and Bakiri][1995]DietterichB95 Dietterich, T., & Bakiri, G. (1995). Solving multiclass learning problems via error-correcting output codes. *Journal* of Artificial Intelligence Research, 2**, 263–286.**
El-Yaniv et al.][1997]ElYanivFT97 El-Yaniv, R., Fine, S., & Tishby, N. (1997). Agnostic classification of markovian sequences. *Neural Information Processing Systems (NIPS)*.

Friedman][1996]Friedman96 Friedman, J. (1996). *Another approach to polychotomous classification*
(Technical Report). Stanford University.

Friedman and Singer][1998]friedman99efficient Friedman, N., & Singer, Y. (1998). Efficient bayesian parameter estimation in large discrete domains.

F¨urnkranz][2002]Furnkranz02 F¨urnkranz, J. (2002).

Round robin classification. Journal of Machine Learning Research, 2**, 721–747.**
Griths and Tenenbaum][2002]griths-using Griths, T.,
& Tenenbaum, J. (2002). Using vocabulary knowledge in bayesian multinomial estimation.

Gutman][1989]Gutman89 Gutman, M. (1989).

Asymptotically optimal classification for multiple tests with empirically observed statistics. *IEEE* Trans. on Information Theory, 35**, 401–408.**
Har-Peled et al.][2002]HarpeledRZ02 Har-Peled, S.,
Roth, D., & Zimak, D. (2002). Constraint classification for multiclass classification and ranking. *Neural* Information Processing Systems (NIPS).

Lehmann][1959]Lehmann59 Lehmann, E. (1959).

Testin statistical hypotheses**. John Wiley & Sons.**
Lin][1991]Lin91 Lin, J. (1991). Divergence measures based on the shannon entropy. IEEE Transactions on Information Theory, 37**, 145–151.**
McAllester and Schapire][2000]llester00convergence McAllester, D., & Schapire, R. E. (2000). On the convergence rate of good-Turing estimators. *Proc.*
13th Annu. Conference on Comput. Learning Theory **(pp. 1–6). Morgan Kaufmann, San Francisco.**
Mitchell][1999]mitchell99machine Mitchell, T. (1999).

Machine learning and data mining. *Communications of the ACM*, 42, 30–36.