Building hierarchical class structures for extreme multi-class learning

Class hierarchical structures play a significant role in large and complex tasks of machine learning. Existing studies on the construction of such structures follow a two-stage strategy. The category similarities are first computed with a certain assumption, and the group partition algorithm is then performed with some hyper-parameters to control the shape of class hierarchy. Despite their effectiveness in many cases, these methods suffer from two problems: (1) optimizing the two-stage objective to obtain the structure is sub-optimal; (2) hyper-parameters make the search space too large to find the optimal structure efficiently. In this paper, we propose a unified and dynamic framework to address these problems, which can: (1) jointly optimize the category similarity and group partition; (2) obtain the class hierarchical structure dynamically without any hyper-parameters. The framework replaces the traditional category similarity with the sample similarity, and constrains samples from the same atomic category partitioned to the same super-category. We theoretically prove that, within our framework, the sample similarity is equivalent to the category similarity and can balance the partitions in terms of the number of samples. Further, we design a modularity-based partition optimization algorithm that can automatically determine the number of partitions on each level. Extensive experimental results on multiple image classification datasets show that the hierarchical structure constructed by the proposed method achieves better accuracy and efficiency compared to existing methods. Additionally, the hierarchy obtained by the proposed method can benefit long-tail learning scenarios due to the balanced partition on samples.