On Flat versus Hierarchical Classification in Large-Scale Taxonomies
We study in this paper flat and hierarchical classification strategies in the context of large-scale taxonomies. To this end, we first propose a multiclass, hierarchical data dependent bound on the generalization error of classifiers deployed in large-scale taxonomies. This bound provides an explanation to several empirical results reported in the literature, related to the performance of flat and hierarchical classifiers. We then introduce another type of bound targeting the approximation error of a family of classifiers, and derive from it features used in a meta-classifier to decide which nodes to prune (or flatten) in a large-scale taxonomy. We finally illustrate the theoretical developments through several experiments conducted on two widely used taxonomies.
Summary ======= This paper proposes a 
      bound on the generalization error of hierarchical multi-classifiers for 
      large-scale taxonomies. Such bound provides a justification of empirical 
      results of flat and hierarchical classifiers. The paper also proposes a 
      bound on the approximation error of a family of classifiers. This is used 
      to define a node-classifier for pruning large-scale taxonomy and thus 
      improving the overall accuracy. Some experiments illustrate the findings 
      of the proposed theory on two well-known taxonomies. Evaluation 
      ======== The paper is well written and presented. It 
      contains interesting technical content, which appears to be sound. In 
      general the paper is of high quality. However, this reviewer sees 
      two limitations of the proposed methods: 1. Considering 
      hierarchical classification as the task of only classifying the leaf nodes 
      is rather limitative for two reasons: a. In real cases, category 
      nodes can contain documents that do not belong to any of their children. 
      This is very common as, when new documents of new types have to be 
      classified, there is no specific child node to accommodate them. Thus the 
      best choice is to assign them to the father nodes. b. This 
      reviewer is not so sure that there is an actual debate on using flat and 
      hierarchical models in the setting proposed by the authors (i.e., only 
      leaf classification). Indeed, when working in the authors' setting, the 
      flat model seems superior. In contrast, top-down methods may get 
      better accuracy when classification is also carried out in the internal 
      nodes. For example, the following paper clearly shows that the top-down 
      method is more accurate than the flat one in such setting: 
      Alessandro Moschitti, Qi Ju, Richard Johansson: Modeling Topic 
      Dependencies in Hierarchical Text Categorization. ACL 2012: 759-767. 
      In this respect a close comparison with other methods, e.g., the 
      one above, those cited by the authors (e.g., Gopal et al.) and the 
      following Zhou, D., Xiao, L., Wu, M.: Hierarchical classification 
      via orthogonal transfer. ICML11. would be appreciated. 2. 
      The proposed bounds do not look very strict: the Rademacher complexity 
      term is a rough approximation and does not consider feature 
      distribution/relevance, which has a major impact in text categorization. 
      For example, in Reuters 21578, there are very rare categories. They 
      may contain about 0.1% of the entire training data, i.e., about 10 
      documents but, for them, systems can reach accuracy of about 90%, larger 
      than for other more populated categories. This suggests that the data 
      imbalance of categories is an important factor but it is not enough. For 
      example, also category ambiguity (how much a category is similar to 
      others) should be considered. After the authors' response 
      ==================== In addition to the reviewer comments, the 
      concepts expressed in the authors' answer should be included in the final 
      version of the paper. Moreover, the authors' answer does not 
      completely solve all the reviewer's doubts, thus the authors should inform 
      the reader about the possible theory's flaws.