# Hierarchical Multiclass Decompositions With Application To Authorship Determination

Ran El-Yaniv rani@cs.technion.ac.il Department of Computer Science, Technion - Israel Institute of Technology Noam Etzion-Rosenberg noam@babylon.com Babylon Ltd. 10 Hataasia St., Or-Yehuda, Israel

## Abstract

This paper is mainly concerned with the question of how to decompose multiclass classification problems into binary subproblems. We extend known Jensen-Shannon bounds on the Bayes risk of binary problems to hierarchical multiclass problems and use these bounds to develop a heuristic procedure for constructing hierarchical multiclass decomposition for multinomials. We test our method and compare it to the well known
"all-pairs" decomposition. Our tests are performed using a new authorship determination benchmark test of machine learning authors. The new method consistently outperforms the all-pairs decomposition when the number of classes is small and breaks even on larger multiclass problems. Using both methods, the classification accuracy we achieve, using an SVM over a feature set consisting of both high frequency single tokens and high frequency token-pairs, appears to be exceptionally high compared to known results in authorship determination.

## 1. Introduction

In this paper we consider the problem of decomposing multiclass classification problems into binary ones.

While binary classification is quite well explored, the question of multiclass classification is still rather open and recently attracted considerable attention of both machine learning theorists and practitioners. A number of general decomposition schemes have emerged, including 'error-correcting output coding' (?; ?**), the**
more general 'probabilistic embedding' (?) and 'constraint classification' (?**). Nevertheless, practitioners**
are still mainly using the infamous 'one-vs-rest' decomposition whereby an individual binary "soft" (or confidence-rated) classifier is trained to distinguish between each class and the union of the other classes and then, for classifying an unseen instance, all classifiers are applied and the winner classifier, with the largest confidence for one of the classes, determines the classification. Another less commonly known method is the so called 'all-pairs' (or 'one-vs-one') decomposition proposed by (?**). In this method we train one**
binary classifier for each pair of classes. To classify a new instance we run a majority vote among all binary classifiers. The nice property of the "all-pairs" method is that it generates the easiest and most natural binary problems of all known methods. The weakness of this method is that there may be irrelevant binary classifiers which participate in the vote. A number of papers provide evidences that 'all-pairs' decompositions are powerful and efficient and in particular, they outperform the 'one-vs-rest' method; see e.g. (?).

For the most part, known decomposition methods including all those mentioned above are "flat". In this paper we focus on *hierarchical* **decompositions. The**
incentive to decompose a multiclass problem as a hierarchy is natural and can have at the outset general advantages which are both statistical and computational.

Considering a multiclass problem with k **classes, the**
idea is to learn a full binary tree1 **of classes, where each**
node is associated with a subset of the k **classes as fol-**1In a full binary tree each node is either a leaf or has two children.