uncovering Shared Structures in Multiclass Classification

Introduction

In their paper Uncovering Shared Structures in Multiclass Classification, the authors Amit et al. wrote about how hidden structure can be utilized to improve the accuracy in multiclass classification. This notion is often called learning-to-learn or interclass transfer (Thrun, 1996).

The uncovering of such hidden structure was accomplished by a mechanism that learns the underlying characteristics that are shared between the target classes. The benefits of finding such common characteristics was demonstrated in the context of large margin multiclass linear classifiers.

Accurate classification of an instance when there is a large number of target classes is a major challenge in many areas such as object recognition, face identification, textual topic classification, and phoneme recognition.

Usually, when there is a large number of classes, the classes are strongly related to each other and have some underlying common characteristics. As a simple example, even though there are many different kinds of mammals, many of them share common characteristics such as having a striped texture. If such true underlying characteristics that are common to the many different classes can be found, then the effective complexity of the multiclass problem can be significantly reduced.

Simultaneously learning the underlying structure shared by classes is a challenging optimization task. The usual goal of past heuristics was to extract powerful non-linear hidden characteristics. However, this goal was usually not convex, and it often resulted in local minima. In this paper, the authors instead modeled the shared characteristics between classes as linear transformations of the input space, so their model was a linear mapping of the shared features of classes that was followed by a multiclass linear classifier. Their model was not only learned in a convex manner, it also significantly improved the accuracy of multiclass linear classifiers.

Formulation

The ultimate goal of multiclass classification is to learn a mapping [math]\displaystyle{ \,H : \mathcal{X} \mapsto \mathcal{Y} }[/math] from instances in [math]\displaystyle{ \,\mathcal{X} }[/math] to labels in [math]\displaystyle{ \,\mathcal{Y} = \{1, \dots , k\} }[/math].

In this paper, the authors considered a linear classifiers over [math]\displaystyle{ \,\mathcal{X} = R^{n} }[/math] that are parametrized by a vector of weights [math]\displaystyle{ \,W_y \in R^{n} }[/math] for each class [math]\displaystyle{ \,y \in \mathcal{Y} }[/math]. These linear models were of the form:

[math]\displaystyle{ \,H_W(x) = \arg\max_{y \in \mathcal{Y}} W_{y}^{t} x \;\;\; (1) }[/math]

Since the authors' goal was to obtain a classifier [math]\displaystyle{ \,W }[/math] that is better at classifying new instances by being able to extract characteristics that are shared among classes, they modeled each common characteristic [math]\displaystyle{ \,r }[/math] as a linear function of the input vectors [math]\displaystyle{ \,x }[/math], denoted [math]\displaystyle{ \,F_r^{t} (x) }[/math]. In this way, the activation of each class [math]\displaystyle{ \,y }[/math] is a linear function [math]\displaystyle{ \,G_y^{t}(F^t x) }[/math] of vectors of common characteristics among classes [math]\displaystyle{ \,F^t x }[/math] rather than being a linear function of the input vectors [math]\displaystyle{ \,x }[/math].

The model in the paper substitutes the weight matrix [math]\displaystyle{ \,W \in \mathbb{R}^{n\times k} }[/math] by [math]\displaystyle{ \,W = FG }[/math], where [math]\displaystyle{ \,F \in \mathbb{R}^{n\times p} }[/math] is a weight matrix whose columns define the [math]\displaystyle{ \,p }[/math] common characteristics among classes, and [math]\displaystyle{ \,G \in \mathbb{R}^{p\times k} }[/math] whose columns predict the classes from on the [math]\displaystyle{ \,p }[/math] common characteristics, as follows:

[math]\displaystyle{ H_{G,F}(x) = \arg\max_{y \in \mathcal{Y}}G_y^{t} (F^t x) = \arg\max_{y \in \mathcal{Y}}(FG)_y^{t} x \;\;\; (2) }[/math]

The authors have showed that regularizing the decomposition [math]\displaystyle{ \,FG }[/math] instead of the Frobenius norm of the weight matrix [math]\displaystyle{ \,W }[/math] can make the resulting model better at generalizing to new instances.

The authors' goal was to simultaneously learn the common characteristics among classes ([math]\displaystyle{ \,F }[/math]) and the class weights ([math]\displaystyle{ \,G }[/math]). In addition to regularizing [math]\displaystyle{ \,||G||_F }[/math], they also [math]\displaystyle{ \,||F||_F^{2} }[/math], which led to the following learning rule

[math]\displaystyle{ \underset{F,G}{\min} \;\; \frac{1}{2} ||F||_F^{2} + \frac{1}{2} ||G||_F^{2} + C \sum_{i=1}^{m} l(FG;(x_i,y_i)) \;\;\; (3) }[/math]

The number of characteristics shared by classes ([math]\displaystyle{ \,p }[/math]) is not limited because, as seen in [math]\displaystyle{ \,(3) }[/math], the regularization uses the norms rather than the dimensionalities of F and G.

The optimization problem in [math]\displaystyle{ \,(3) }[/math] is not convex. However, instead of learning [math]\displaystyle{ \,F }[/math] and [math]\displaystyle{ \,G }[/math], the authors considered the trace-norm of [math]\displaystyle{ \,W }[/math], which is [math]\displaystyle{ \,||W||_{\Sigma} = \underset{FG = W} {\min} \;\; \frac{1}{2} (||F||_F^{2} + ||G||_F^{2}) }[/math], and they re-expressed the optimization problem in [math]\displaystyle{ \,(3) }[/math] as a convex optimization problem that finds [math]\displaystyle{ \,W }[/math], as follows:

[math]\displaystyle{ \underset{W}{\min} \;\; ||W||_{\Sigma} + C \sum_{i=1}^{m} l(W;(x_i,y_i)) \;\;\; (4) }[/math]

The optimization problem in [math]\displaystyle{ \,(4) }[/math] could then be formulated as a semi-definite program(SDP) and be easily solved.

Dualization and Kernelization

Taking into consideration the advantages of large-margin methods, the authors obtained the dual form and then the kernelized form of [math]\displaystyle{ \,(4) }[/math].

Using Lagrange duality (more detailed available here, they obtained the dual of [math]\displaystyle{ \,(4) }[/math], as follows:

[math]\displaystyle{ \, max \;\; \underset{i} \Sigma (-Q_{i_{y_i}}) \;\;\; s.t. \;\;\; \forall_{i,j \ne y_i} \;\; Q_{ij} \ge 0, \;\;\; \forall_i \;\; (-Q_{i_{y_i}}) = \underset{j \ne y_i} \Sigma Q_{ij} \le c, \;\;\; ||XQ||_2 \le 1 \;\;\; (5) }[/math]

In [math]\displaystyle{ \,(5) }[/math], [math]\displaystyle{ \,Q \in \mathbb{R}^{m\times k} }[/math] is the dual Lagrange variable and [math]\displaystyle{ \,||XQ||_2 }[/math] is the spectral norm (the maximal singular value) of [math]\displaystyle{ \,XQ }[/math]. [math]\displaystyle{ \,(5) }[/math] can also be written as a semi-definite program.

The authors re-expressed the spectral norm constraint in (5), which was [math]\displaystyle{ \,||XQ||_2 \le 1 }[/math], as [math]\displaystyle{ \,||Q^t(X^tX)Q||_2 \le 1. }[/math], and re-expressed [math]\displaystyle{ \,(5) }[/math] as:

[math]\displaystyle{ \, max \;\; \underset{i} \Sigma (-Q_{i_{y_i}}) \;\;\; s.t. \;\;\; \forall_{i,j \ne y_i} \;\; Q_{ij} \ge 0, \;\;\; \forall_i \;\; (-Q_{i_{y_i}}) = \underset{j \ne y_i} \Sigma Q_{ij} \le c, \;\;\; ||Q^tKQ||_2 \le 1 \;\;\; (6) }[/math]

In [math]\displaystyle{ \,(6) }[/math], [math]\displaystyle{ \,K = X^tX }[/math] is the Gram matrix. [math]\displaystyle{ \,(6) }[/math] is a convex problem on [math]\displaystyle{ \,Q }[/math] that involves a semidefinite constraint (the spectral-norm constraint) on [math]\displaystyle{ \,Q^tKQ }[/math] that does not depend on the size of the training set, but rather on the number of classes [math]\displaystyle{ \,k }[/math].

Using [math]\displaystyle{ \,(6) }[/math] and Theorem 1 that is given below (the proof is in the paper listed in Reference), the authors were able to find the optimum weight matrix [math]\displaystyle{ \,W }[/math] in terms of the dual optimum [math]\displaystyle{ \,Q }[/math], and they were thus able to use the kernel mechanism for prediction of new instances.

Theorem 1 (Representer Theorem):

Let [math]\displaystyle{ \,Q }[/math] be the optimum of [math]\displaystyle{ \,(6) }[/math] and [math]\displaystyle{ \,V }[/math] be the matrix of eigenvectors of [math]\displaystyle{ \,Q^'KQ }[/math], then for some diagonal [math]\displaystyle{ \,D \in \mathbb{R}^{k\times k} }[/math], the matrix [math]\displaystyle{ \,W = X(QV^tDV) }[/math] is an optimum of [math]\displaystyle{ \,(5) }[/math], with [math]\displaystyle{ \,||W||_{\Sigma} = \Sigma_r |D_{rr}| }[/math].

By substituting [math]\displaystyle{ \,W = XQV^tDV }[/math] into [math]\displaystyle{ \,(5) }[/math], the first term becomes [math]\displaystyle{ \,\Sigma_r |D_{rr}| }[/math], while the second term is piecewise linear in [math]\displaystyle{ \,KQV^tDV }[/math]. Therefore, we can easily solve a simple linear program (LP) in the [math]\displaystyle{ \,k }[/math] unknown entries on the diagonal of [math]\displaystyle{ \,D }[/math] to find [math]\displaystyle{ \,D }[/math] and hence find [math]\displaystyle{ \,W }[/math]. It should be noted that the number of variables in this LP depends only on the number of classes ([math]\displaystyle{ \,k }[/math]), and that the entire procedure of solving [math]\displaystyle{ \,(6) }[/math] which consists of extracting [math]\displaystyle{ \,V }[/math] and then finding [math]\displaystyle{ \,D }[/math] and thus [math]\displaystyle{ \,W }[/math] uses only the Gram matrix ([math]\displaystyle{ \,K }[/math]).

Learning a Latent Feature Representation

As mentioned above, learning [math]\displaystyle{ \,F }[/math] can be interpreted as learning a latent feature space [math]\displaystyle{ \,F^tX }[/math], which is useful for prediction. Because [math]\displaystyle{ \,F }[/math] is learned jointly over all classes, it effectively transfers knowledge between the classes.

The authors considered [math]\displaystyle{ \,k }[/math] binary classification tasks, and used [math]\displaystyle{ \,W_j }[/math] as a linear predictor for the [math]\displaystyle{ \,j }[/math]th task. Using an SVM to learn each class independently, they came up with the following learning rule:

[math]\displaystyle{ \underset{W}{\min} \;\; \underset{j}\Sigma (\frac{1}{2} ||W_i||^2 + Cl_j(W_j)) = \underset{W}{\min} \frac{1}{2} ||W||_F^2 + C \underset{j}\Sigma l_j(W_j) \;\;\; (7) }[/math], where [math]\displaystyle{ \,l_j(W_j) }[/math] is the total (hinge) loss of [math]\displaystyle{ \,W_j }[/math] on the training examples for task [math]\displaystyle{ \,j }[/math].

Replacing the Frobenius norm with the trace norm ([math]\displaystyle{ \, \underset{W}{\min} ||W||_{\Sigma} + C \underset{j} \Sigma l_j(W_j) }[/math]) corresponds to learning a feature representation [math]\displaystyle{ \,\phi(x) = F^tx }[/math] that allows good, low-norm prediction for all [math]\displaystyle{ \,k }[/math] tasks. After such a feature representation is learned, a new task can be learned directly using the feature vectors [math]\displaystyle{ \,F^tx }[/math] using standard SVM machinery, taking advantage of the transferred knowledge from the other, previously-learned, tasks.