On Maximum Margin Hierarchical Multilabel Classification

We present work in progress towards maximum margin hierarchical classification where the objects are allowed to belong to more than one category at a time. The classification hierarchy is represented as a Markov network equipped with an exponential family defined on the edges. We present a variation of the maximum margin multilabel learning framework, suited to the hierarchical classification task and allows efficient implementation via gradient-based methods. We compare the behaviour of the proposed method to the recently introduced hierarchical regularized least squares classifier as well as two SVM variants in Reuter’s news article classification. Often in hierarchical classification, the object to be classified is assumed to belong to exactly one (leaf) node in the hierarchy (c.f. . Following , in this paper we consider the more general case where a single object can be classified into several categories in the hierarchy, to be specific, the multilabel is a union of partial paths in the hierarchy. For example, a news article about David and Victoria Beckham could belong to partial paths sport, football and entertainment, music but might not belong to any leaf categories such as champions league or jazz. In our setting the training data ((xi,y(xi))) m i=1 consists of pairs (x,y) of vector x ∈ R and a multilabel y ∈ {+1,−1} consisting of k microlabels. As the model class we use the exponential family P (y|x) ∝ ∏ e∈E exp ( w e φe(x,ye) ) = exp ( wφ(x,y) ) (1) defined on the edges of a Markov networkG = (V,E), where node j ∈ V corresponds to the j’th component of the multilabel and the edges e = (j, j′) ∈ E correspond ∗Corresponding author. to the classification hierarchy given as input. By ye = (yj , y′ j) we denote the restriction of the multilabel y = (y1, . . . , yk) to the edge e = (j, j′). The edgefeature vector φe, in turn, is a concatenation of ’class-sensitive’ feature vectors φe (x,ye) = Jye = uKφ(x), where J·K denotes an indicator function (c.f. ), and we is the weight vector for edge e. The vector φ(x) could be a bag of words—as in the experiments reported here—or any other feature representation of the document x. Also, note that although the same feature vector φ(x) is duplicated for each edge and edge-labeling, in the weight vector w = (we e )e∈E,ue we still have a separate weights to represent importance differences of a given feature in different contexts. There are many ways to define loss functions for hierarchical classification setting (c.f [?, ?, ?, 1]). Zero-one loss `0/1(y,u) = Jy 6= uK is not very well suited to the task as it ignores the severity of the discrepancy between y and u. Symmetric difference loss `∆(y,u) = ∑ jJyi 6= uiK does not suffer from this deficiency. However, it fails to take the dependency structure of the microlabels into account. A more appealling choice is the hierarchical loss function of . It penalizes the first mistake along a path, `PATH(y,u) = ∑ j cjJyj 6= uj & yk = uk∀k ∈ anc(j)K, where the coefficients croot = 1, cj = cpa(j)/|sibl(j)| down-weight mistakes made deeper in the hierarchy. Here we denoted by anc(j) an ancestor, by pa(j) the immediate parent, and by sibl(j) the set of siblings of node j. In this paper, we consider a simplified version of `PATH , namely