Locality Sensitive Discriminant Analysis

1 Introduction

Many real-world classification tasks involve large numbers of overlapping categories. Prominent examples include the International Patent Classification scheme (approx. 69,000 patent groups), the Open Directory project (approx. 590,000 categories for Web pages), and the Gene Ontology (approx. 17,000 terms to describe gene products). In most cases, instances are assigned to more than one category, since categories are rarely mutually exclusive. This leads to large scale multi-label classification problems. The categories are typically organized in hierarchies or taxonomies, most commonly by introducing superordinate concepts and by relating categories via 'is-a' relationships. Multiply connected taxonomies are not uncommon in this context.

We believe that taxonomies encode valuable domain knowledge which learning methods should be able to capitalize on, in particular since the number of training examples for individual classes may be very small when dealing with tens of thousands or more classes. The potential loss of valuable information by ignoring class hierarchies has been pointed out before and has led to a number of approaches that employ different ways to exploit hierarchies [McCallum et al., 1998; Wang et al., 1999; Dumais and Chen, 2000].

In this paper, we present an approach for systematically incorporating domain knowledge about the relationships between categories into the Perceptron learning and SVM classification architecture. The rest of the paper is organized as follows. Section 2 introduces two ways of representing taxonomy knowledge. First, derive pairwise similarities between categories based on their relative locations in the taxonomy in order to tie learning across categories. Second, adapt the standard 0/1 loss function to weigh misclassification errors in accordance with the taxonomy structure. In Section 3 we formulate the hierarchical learning problem in terms of a joint large margin problem, for which we derive an efficient training algorithm. In Section 4 we propose a hierarchical Perceptron algorithm that exploits taxonomies in a similar fashion. Section 5 examines related work. Section 6 presents experimental results which show the two new hierarchical algorithms bring significant improvements on all metrics. Conclusions and future work are discussed in Section 7.

2 Utilizing Known Taxonomies

2.1 Problem Setting

We assume the patterns such as documents are represented as vectors, x ∈ X ⊆ Rd, which can be mapped to a higher dimensional feature space as φ(x). We denote the set of categories by Y = {1, . . . , q}, a category by y ∈ Y, and a label set by Y ∈ P(Y) where P(Y) is the power set of Y. A taxonomy is a directed acyclic graph (V,E) with nodes V ⊇ Y such that the set of terminal nodes equals Y, formally Y = {y ∈ V : ∄v ∈ V, (y, v) ∈ E}. Note that we do not assume that a taxonomy is singly connected (tree or forest), but allow for converging nodes. In some cases one wants to express that items belong to a super-category, but to none of the terminal categories in Y, we suggest to model this by formally adding one terminal node to each inner node, representing a "miscellaneous" category; this avoids the problem of partial paths.

In multi-label learning, we aim at finding a mapping f : X → P(Y), based on a sample of training pairs {(xi, Yi), i = 1, . . . , n} ⊆ X × P(Y). A popular approach as suggested, for instance by [Schapire and Singer, 2000], is to actually learn a ranking function over the categories for each pattern, g : X → Sq, where Sq is the set of permutations of ranks 1 to q. In order to get a unique subset of labels, one then needs address the additional question on how to select the number of categories a pattern should be assigned to.

It is common to define the ranking function g implicitly via a scoring function F : X × Y → R, such that g(x)(y) < g(x)(y′ ) whenever F (x, y) > F (x, y′ ), i.e. categories with higher F-values appear earlier in the ranking (for ease of presentation we ignore ties). Notation g(y) is used when clear from context.

2.2 Class Attributes

Following [Cai and Hofmann, 2004] we suggest to use scoring functions F that are linear in some joint feature representation Φ of inputs and categories, namely F(x, y;w) ≡ 〈w, Φ(x, y)〉, where w is a weight vector. Following [Tsochantardis et al., 2004; Cai and Hofmann, 2004] Φ will be chosen to be of the form Λ(y) ⊗ φ(x), where Λ(y) = (λ1(y), . . . , λs(y))T ∈ Rs refers to an attribute vector representing categories and ⊗ is the Kronecker product. One can interpret w in terms of a stacked vector of individual weight vectors, i.e. w = (wT 1 , . . . ,wT s )T , leading to the additive decomposition F (x, y; w) = ∑sr=1 λr (y)〈wr , x〉. The general idea is that the notion of class attributes will allow generalization to take place across (similar) categories and not just across training examples belonging to the same category. In the absence of such information, one can set s = q and define λr(y) = δry which leads to F(x, y) = 〈wy, x〉.

How are we going to translate the taxonomy information into attributes for categories? The idea is to treat the nodes in the taxonomy as properties. Formally, we define

where tv ≥ 0 is the attribute value for node v. In the simplest case, tv can be set to a constant, like 1. We denote by anc(y) the set of ancestor nodes of y in the taxonomy including y itself (for notational convenience). This leads to an intuitive decomposition of the scoring function F into contributions from all nodes along the paths from a root node to a specific terminal node.

2.3 Loss Functions

A standard loss function for the multi-label case is to use the symmetric difference between the predicted and the actual label set, i.e. to count the number of correct categories missed plus the number of incorrect categories that have been assigned, △0(Y, ˆ Y ) ≡ |Y ⊖ ˆ Y |.

Yet, in many applications, the actual loss of a predicted label set relative to the true set of category labels will depend on the relationship between the categories. As a motivation we consider the generic setting of routing items based on their membership at nodes in the taxonomy. For instance, in a news routing setting, readers may sign-up for specific topics by selecting an appropriate node, which can either be a terminal node in the taxonomy (e.g. the category "Soccer") or an inner node (e.g. the super-category "Sports"). Note that while we assume that all items can be assigned to terminal nodes of the taxonomy only, customers may prefer to sign-up for many categories en bloc by selecting an appropriate super-category.

We assume that there is some relative sign-up volume sv ≥ 0 for each node as well as costs c- of missing a relevant item and c+ for assigning an irrelevant item. For any label set Y , define anc(Y ) ≡ {v ∈ V : ∃y ∈ Y, v ∈ anc(y)}. Now we can quantify the loss in the following manner:

Note that only nodes in the symmetric difference anc(Y ) ⊖ anc( ˆ Y ) contribute to the loss. In the following we will simplify the presentation by assuming that c= c+ = 1. Then, by further setting sv = 1 (∀v ∈ V) one gets △(Y, ˆ Y ) = |anc(Y ) ⊖ anc( ˆ Y )|. Intuitively, this means that one colors all nodes that are on a path to a node in Y with one color, say blue, and all nodes on paths to nodes in ˆ Y with another color, say yellow. Nodes that have both colors (blue+yellow=green) are correct, blue nodes are the ones that have been missed and yellow nodes are the ones that have been incorrectly selected; both types of mistakes contribute to the loss proportional to their volume.

During training, this loss function is difficult to deal with directly, since it involves sets of labels. Rather, we would like to work with pairwise contributions, e.g. involving terms

In singly connected taxonomies Eq. (3) is equivalent to the length of the (undirected) shortest path connecting the nodes y and y′ , suggested by [Wang et al., 1999]. In order to relate the two, we state the following proposition.

Proposition 1. For any Y, ˆ Y ⊆ Y satisfying Y ̸⊆ ˆ Y and ˆ Y ̸⊆ Y ,

For learning with ranking functions g, we translate this into

We look at every pair of categories where an incorrect category comes before a correct category in the order defined by g and count the symmetric difference of the respective ancestor sets as the corresponding loss.

3 Hierarchical Support Vector Machines

3.1 Multi-label Classification

We generalize the multiclass SVM formulation of [Crammer and Singer, 2001] to a multi-label formulation similar to that in [Elisseff and Weston, 2001]. For a given set of correct categories Yi we denote the complement by ¯ Yi = Y - Yi . Then following [Elisseff and Weston, 2001] we approximate the separation margin of w with respect to the i-th example as

Our formulation aims at maximizing the margin over the whole training set, i.e. maxw:‖w‖=1 mini γi(w). This is equivalent to minimizing the norm of the weight vector w while constraining all (functional) margins to be greater than or equal to 1. A generalized soft-margin SVM formulation can be obtained by introducing slack variables ξi's. The penalty is scaled proportional to the loss associated with the violation of the respective category ordering, a mechanism suggested before (cf. [Tsochantardis et al., 2004; Cai and Hofmann, 2004]). Putting these ideas together yields the convex quadratic program (QP)

where δΦi(y, ¯ y) ≡ Φ(xi, y) - Φ(xi, ¯ y).

This formulation is similar to the one used in [Schapire and Singer, 2000] and generalizes the ranking-based multi-label SVM formulation of [Elisseff and Weston, 2001]. Following [Crammer and Singer, 2001] we have not included bias terms for categories. The efforts are put into correctly ordering each pair of positive/negative labels. We can use a size prediction mechanism such as the one in [Elisseff and Weston, 2001] to convert the category ranking into an actual multi-label classification.

The dual QP of (6) becomes

-

Herein one can simply replace the inner products by corresponding kernel functions. It is straightforward to observe that 1n ∑i ξi yields an upper bound on the training loss of the resulting classifier measured by △ in the following sense. Define the maximum loss as

The maximal loss over a set of examples is defined as

Proposition 2. Denote by ( ˆw, ˆ ξ) a feasible solution of the QP in (6). Then 1n ∑ni=1 ˆ ξi is an upper bound on the empirical maximal loss △x(F(; ˆw), {xi, Yi}ni=1 ).

Algorithm 1 Hierarchical Multilabel SVM

• 1: inputs: training data {xi, Yi}ni=1 , tolerance ϵ ≥ 0
• 2: initialize Si = ∅, αiy¯ y = 0, ∀ i, y ∈ Yi, ¯ y ∈ ¯ Yi .
• 3: repeat
• 4: select ˆi = argmaxni=1 ψi
• 5: select (ˆ y, ˆ¯ y) = argmaxy∈Yˆi ,¯ y∈ ¯ Yˆi Gˆiy ¯ y
• 6: expand working set: Sˆi = Sˆi ∪ {(ˆ y, ˆ¯ y)}
• 7: solve QP over subspace {αˆiy¯ y : (y, ¯ y) ∈ Sˆi }
• 8: reduce working set: Sˆi = Sˆi - {(y, ¯ y) : αˆiy¯ y = 0}
• 9: until ψˆi ≤ ϵ

Note that to minimize (an upper bound on) the loss in Eq. (4), we could simply assign one slack variable ξiy¯ y for every triplet of instance, positive label, and negative label. This leads to a dual program similar to Eq. (7) except the second set of constraints become αiy ¯ y △(y, ¯ y) ≤ C ∀i, y ∈ Y, ¯ y ∈ ¯ Y . We have yet to explore this direction.

3.2 Optimization Algorithm

The derived QP can be very large. We therefore employ an efficient optimization algorithm that is inspired by the SMO algorithm [Platt, 1999] and that performs a sequence of subspace ascents on the dual, using the smallest possible subsets of variables that are not coupled with the remaining variables through constraints. Our algorithm successively optimizes over subspaces spanned by {αiy¯ y : y ∈ Yi, ¯ y ∈ ¯ Yi} for some selected instance i. Moreover an additional variable selection is performed within each subspace. This strategy is also known as column generation [Demiriz et al., 2002]. Define

where ζi = C - ∑y∈Yi , ¯ y∈ ¯ Yi αiy ¯ y △(y, ¯ y) . Define ψi ≡ li - ui. By derivation similar to that in [Cai and Hofmann, 2004], it can be shown that ψi = 0 (∀i) is the necessary and sufficient condition for a feasible solution to be optimal. Hence the score ψi is used for selecting subspaces. Giy¯ y is also used to select new variables to expand the active set of each subspace. The resulting algorithm is depicted in Algorithm 1.

More details on convergence and sparseness of a more general class of algorithms can be found in [Tsochantardis et al., 2004].

4 Hierarchical Perceptron

Although SVM is competitive in generating high-quality classifiers, it can be computationally expensive. The Perceptron algorithm [Rosenblatt, 1958] is known for its simplicity

Algorithm 2 Hierarchical Minover Perceptron algorithm

1: inputs: training data {xi, Yi}ni=1 , desired margin c. 2: Initialize αiy¯ y = 0, ∀ i, y ∈ Yi, ¯ y ∈ ¯ Yi 3: repeat 4: (ˆi, ˆ y, ˆ¯ y) = argmini,y∈Yi,¯ y∈ ¯ Yi 〈w(α), δΦi(y, ¯ y)〉 5: if 〈w(α), δΦˆi (ˆ y, ˆ¯ y)〉 > c then 6: terminate with a satisfactory solution 7: else 8: αˆiˆ y ˆ¯ y ← αˆiˆ y ˆ¯ y + △(ˆ y, ˆ¯ y) 9: end if

• 10: until maximal number of iterations are performed

and speed. In this section, we propose a hierarchical Perceptron algorithm 2 using the minimum-overlap (Minover) learning rule [Krauth and M´ezard, 1987].

The Minover Perceptron uses the instance that violates the desired margin the worst to update the separating hyperplane. We can also deal with the instances sequentially, as in a truly online fashion. Using the minimum overlap selection rule effectively speeds up the convergence and yields sparser solutions.

If using taxonomy-based class attribute scheme in Eq. (1) with tv = 1, the simple update rule in step 8 of Algorithm 2 can be decomposed into

Only the weight vectors of those nodes that are predecessors of y or ¯ y but not both will be updated. Other nodes are left intact. This strategy is also used in [Dekel et al., 2004] for online multiclass classification. The more severe the loss is incurred, the more dramatic the update will be. Moreover step 8 not only updates the scoring functions of the two classes in question, but also spread the impact to other classes sharing affected ancestors with them.

5 RelatedWork

Many approaches for hierarchical classification use a decision tree like architecture, associating with each inner node of the taxonomy a classifier that learns to discriminate between the children [Dumais and Chen, 2000; Cesa-Bianchi et al., 2005]. While this offers advantages in terms of modularity, the local optimization of (partial) classifiers at every inner node is unable to reflect a more global objective.

[Cesa-Bianchi et al., 2005] introduces a loss function, called the H-loss, specifically designed to deal with the case of partial and overlapping paths in tree-structured taxonomies. [Cesa-Bianchi et al., 2006] has proposed B-SVM, which also uses the H-loss and uses a decoding scheme that explicitly computes the Bayes-optimal label assignment based on the H-loss and certain conditional independence assumptions about label paths. The loss function we proposed in Eq. (2) exploits the taxonomy in a different way fromHloss, partly because we always convert partial path categories to complete path ones. Our loss function is inspired by real applications like routing and subscription to a taxonomy. So misclassifications are penalized along all ancestors that miss relevant patterns or include irrelevant ones. In H-loss, however, if punishment already occurs to a node, its descendents are not penalized again. In addition, our loss function works with arbitrary taxonomy, not just trees.

[Rousu et al., 2005] applies the Maximum-MarginMarkov Networks [Taskar et al., 2003] to hierarchical classification where the taxonomy is regarded as Markov Networks. They propose a simplified version of H-loss that decomposes into contributions of edges so as to marginalize the exponentialsized problem into a polynomial one. In our methods, learning occurs on taxonomy nodes instead of edges. We view the taxonomy as a dependency graph of "is-a" relation.

[Cai and Hofmann, 2004] proposes a hierarchical SVM that decomposes discriminant functions into contributions from different levels of the hierarchy, the same way as this work. Compared to [Cai and Hofmann, 2004], which was restricted to multiclass classification, however, we deal with the additional challenge posed by overlapping categories, i.e. the multi-label problem, for which we employ the category ranking approach proposed in [Schapire and Singer, 2000].

In summary, our major contributions are: 1) Formulate multilabel classification as a global joint learning problem that can take taxonomy information into account. 2) Exploit taxonomy by directly encoding structure in the scoring function used to rank categories 3) Propose a novel taxonomybased loss function between overlapping categories that is motivated by real applications. 4) Derive a sparse optimization algorithm to efficiently solve the joint SVM formulation. Compared to multiclass classification, sparseness is even more important now that there are more constraints and hence more dual variables. 5) Present a hierarchical Perceptron algorithm that takes advantage of the proposed methods of encoding known taxonomies.

6 Experiments

6.1 Experimental Setup

In this section we compare our hierarchical approaches against their flat counterparts on WIPO-alpha, a data set comprising patent documents.

Taxonomy-derived attributes are employed in the hierarchical approaches. For comparison purpose, tv in Eq. (1) is set to 1/√depth where depth ≡ maxy |{anc(y)}|, so that maxy ‖Λ(y)‖ = 1 for either the flat or the hierarchical models. In the experiments, hierarchical loss equals half the value in Eq. (3) for historical reason. The hierarchical learning employs this hierarchical loss while the flat one employs the 0-1 loss. We used a linear kernel and set C = 1. Each instance is normalized to have 2-norm of 1. In most experiments, the test performance is evaluated by cross-validation and then macroaveraging across folds.

The measures we used include one-accuracy, average precision, ranking loss, maximal loss, and parent one-accuracy. The first three are standard metrics for multilabel classification problem [Schapire and Singer, 2000; Elisseff and Weston, 2001]. One-accuracy (acc) measures the empirical probability of the top-ranked label being relevant to the document. Average precision (prec) measures the quality of label rankings. Precision is calculated at each position where a positive label occurred, as if all the labels ranked higher than it including itself are predicted as relevant. These precision values are then averaged to obtain average precision. Ranking loss (rloss) measures the average fraction of positive label and negative label pairs that are misordered. These metrics are described in details in [Schapire and Singer, 2000].

Maximal loss, denoted by △x, was introduced in Eq. (10). It is measured by the hierarchical loss function. We also evaluate parent one-accuracy (pacc), which measures the oneaccuracy at the category's parent nodes level.

6.2 Experiments onWIPO-alpha Collection

WIPO-alpha collection comprises patent documents released by the World Intellectual Property Organization (WIPO) 1 . which are classified into IPC categories. IPC is a 4-level hierarchy consisting of sections, classes, subclasses, and groups. The categories in our experiments refer to main groups which are all leaves at the same depth in the hierarchy. Each document is labeled with one primary category as well as any number of secondary categories. Both types of categories are used to form a multi-label corpus. We have performed independent experiments on taxonomies under the 8 top-level sections.

1 www.wipo.int/ibis/datasets

Document parsing was performed with the Lemur toolkit 2 . Stop words are removed. Stemming is not performed. Word counts from title and claim fields are used as document features. Table 1 summarizes the SVM performance across the sections. The hierarchical SVM significantly outperforms the flat SVM in terms of △x-loss, ranking loss and parent accuracy in each individual setting. This can be attributed not only to the fact that the hierarchical approach explicitly optimizes an upper bound on the △x-loss, but also to the specific hierarchical form of the discriminant function. Moreover, hierarchical SVM often produces higher classification accuracy and average precision with gains being more moderate. To see if the improvement is statistically significant, we conducted 10-fold cross-validation on section E and then paired permutation test. The achieved level of significance is less than 0.08 for one accuracy, and less than 0.005 for the other four measures.

Figure 1 depicts the performance of Perceptron algorithm with the same setting. We allow Perceptron to run until convergence. It takes significantly less time than SVM but reaches lower performance. We observe the hierarchical Perceptron performs better in all cases.

In addition we randomly sampled 3 documents from each flat Perceptron ranking loss (%)

2 www.lemurproject.org

flat Perceptron parent one accuracy (%)

Figure 3: Flat and hierarchical Perceptron on subsampled data.

category to simulate the situation where data are only available in small quantities. The results in Table 2 show that the hierarchical SVM outperforms the flat SVM in all cases. The relative gains are somewhat higher than for the complete training set. Fig 2 demonstrates how the performance gains vary with the size of training data. We observe that hierarchical SVM excels in all runs. The gains appear to be slightly larger when the training set is sparser, except for one accuracy.

Figure 3 compares flat and hierarchical Perceptron with the same subsampling setting as above. Each 3-fold cross validation on a random subset of documents under one section constitutes one sample in the figure, with each section contributing 3 samples. We observe the hierarchical approach helps with one accuracy most times. It always significantly improves average precision, ranking loss and parent accuracy.

7 Conclusions

In this paper a hierarchical loss function has been derived from real applications. We have proposed a large margin architecture for hierarchical multilabel categorization. It extends the strengths of Support Vector Machine classification to take advantage of information about class relationships encoded in a taxonomy. The parameters of the model are fitted by optimizing a joint objective. A variable selection algorithm has been presented to efficiently deal with the resulting quadratic program. We have also proposed a hierarchical Perceptron algorithm that couples the discriminant functions according to the given hierarchy and employs the hierarchical loss in its updating rule. Our experiments show the proposed hierarchical methods significantly outperform the flat methods. Although they aim at reducing the hierarchical loss, the taxonomy-based approaches improve other measures such as one accuracy and average precision. Future work includes more directly working with the hierarchical loss we proposed and comparing our methods with other hierarchical methods.