Fast Multi-label Learning

1 Introduction

Multi-label classification [Prabhu and Varma, 2014; Yen et al., 2016; Liu et al., 2019; Gong et al., 2020], in which each instance can belong to multiple labels simultaneously, has significantly attracted the attention of researchers as a result of its wide range of applications, which range from document classification and automatic image annotation to video annotation. For example, when classifying documents, one may need to classify them into different groups, such as Science, Finance and Sports. In automatic image annotation, one needs to automatically predict relevant keywords, such as beach, sky and tree, to describe a natural scene image.

A popular strategy in multi-label learning is binary relevance (BR)[Tsoumakas et al., 2010], which independently trains a linear regression model for each label independently. Recently, some sophisticated models are developed to improve the performance of BR. For example, embedding approaches [Hsu et al., 2009; Chen and Lin, 2012; Yu et al., 2014; Liu and Tsang, 2017; Liu et al., 2017] have become popular techniques. Even though embedding methods improve the prediction performance of BR to some extent, their training process usually involves a complex quadratic or semidefinite programming problem, as in [Zhang and Schneider, 2012], or their model may involve an NP-hard problem, as in [Yu et al., 2014] and [Bhatia et al., 2015]. Thus, these kinds of methods are prohibitive on large-scale applications. Much of the literature, such as [Luaces et al., 2012], [Madjarov et al., 2012] and [Taha and Tiun, 2016], has already shown that BR with appropriate base learner is usually good enough for some applications, such as document classification [Taha and Tiun, 2016]. Unfortunately, BR runs slowly due to its linear dependence on the size of the input data. The question is how to overcome these computational obstacles yet obtain comparable results with BR.

To address the above problem, we provide a simple stochastic sketch strategy for multi-label classification. In particular, we carefully construct a small sketch of the full data set, and then use that sketch as a surrogate to perform fast optimization. This paper first introduces stochastic σsubgaussian sketch, and then proposes the construction of a sketch matrix based on Walsh-Hadamard matrix to reduce the expensive matrix multiplications of σ-subgaussian sketch. From an algorithmic perspective, we provide provable guarantees that our proposed methods are approximately as good as the exact solution of BR. From a statistical learning perspective, we provide the generalization error bound of multilabel classification using our proposed stochastic sketch model.

Experiments on various real-world data sets demonstrate the superiority of the proposed methods. The results verify our theoretical findings. We organize this paper as follows. The second section introduces our proposed stochastic sketch for multi-label classification. The third section provides the provable guarantees for our algorithm from both algorithmic and statistical learning perspectives, and experimental results are presented in the fourth section. The last section provides our conclusions.

2 Stochastic Sketch for Multi-label Classification

Assume that x(i) ∈ Rp×1 is a real vector representing an input (instance), and y(i) ∈ {0, 1}q×1 is a real vector representing the corresponding output (i ∈ {1 . . . n}). n denotes the number of training samples. The input matrix is X ∈ Rn×p and the output matrix is Y ∈ {0, 1}n×q . 〈·, ·〉 and In×n represent the inner product and the n×n identity matrix, respectively. We denote the transpose of the vector/matrix by the superscript ′ and the logarithms to base 2 by log. Let || · ||2 and || · ||F represent the l2 norm and Frobenius norm, respectively. Let V ∈ Rp×q be the regressors and N(0, 1) denote the standard Gaussian distribution.

A simple linear regression model for BR [Tsoumakas et al., 2010] learns the matrix V through the following formulation:

Assuming that n > p and n > q, the computational complexity for this problem is O(npq + np2 ) [Golub and Loan, 1996]. The computational cost of an exact solution for problem 1 will be prohibitive on large-scale settings. To solve this problem, we construct a small sketch of the full data set by stochastic projection methods, and then use that sketch as a surrogate to perform fast optimization for problem 1. Specifically, we define a sketch matrix S ∈ Rm×n and S ̸= 0, where m < n is the projection dimension and 0 is the zero matrix with all the zero entries. The input matrix X and output matrix Y are approximated by their sketched matrix SX and SY , respectively. We aim to solve the following sketched problem of problem 1.

Motivated by [Weinberger and Saul, 2009; Kulis, 2013; Bhatia et al., 2015], we use a k-nearest neighbor (kNN) classifier in the embedding space for prediction, instead of using an expensive decoding process [Zhang and Schneider, 2012]. Next, we introduce two kinds of stochastic sketch methods.

2.1 Stochastic σ-Subgaussian Sketch

The entries of a sketch matrix can be simply defined as i.i.d random variables from certain distributions, such as Gaussian distribution and Bernoulli distribution. [Matousek, 2008] has already shown that each of these distributions is a special case of Subgaussian distribution, which is defined as follows:

Definition 1 (σ-Subgaussian). A row si ∈ Rn of the sketch matrix S is σ-Subgaussian, if it has zero mean and for any vector ζ ∈ Rn and ϵ ≥ 0, we have

Clearly, a vector with i.i.d standard Gaussian entries or Bernoulli entries is 1-Subgaussian. We refer any matrix S ∈ Rm×n to a Subgaussian sketch if its rows are zero mean, 1-Subgaussian, and with the covariance matrix cov(si) = In×n. A Subgaussian sketch is straightforward to construct. However, given the Subgaussian sketch S ∈ Rm×n , the cost of computing SX and SY is O(npm) and O(nqm), respectively. Next, we introduce the following technique to reduce this time complexity.

2.2 StochasticWalsh-Hadamard Sketch

Inspired by [Ailon and Chazelle, 2009], we propose to construct the sketch matrix based on Walsh-Hadamard matrix to reduce the expensive matrix multiplications of Subgaussian sketch. Formally, a stochastic Walsh-Hadamard sketch matrix S ∈ Rm×n is obtained with i.i.d. rows of the form:

where {e1, · · · , em} is a random subset of m rows uniformly sampled from In×n, R ∈ Rn×n is a random diagonal matrix whose entries are i.i.d. Rademacher variables and H ∈ Rn×n constitutes a Walsh-Hadamard matrix defined as:

where B(i) and B(j) represent the binary expression with τbit of i and j (assume 2τ = n).

Then, we can employ fast Walsh-Hadamard transform [Fino and Algazi, 1976] to perform SX and SY in O(np log m) and O(nq log m).

3 Main Results

Since we address problem 2 rather than directly solving problem 1, which has great advantages for fast optimization, it is interesting to ask the question: what is the relationship between problem 2 and problem 1? Let V ∗ and ˆ V be the optimal solutions of problem 1 and problem 2. We define f(V ∗ ) = ||XV ∗ - Y ||2F and g( ˆ V ) = ||SX ˆ V - SY ||2F . We will prove that we can choose an appropriate m such that the two optimal objectives f(V ∗ ) and g(ˆ V ) are approximately the same. This means that we can speed up the computation of problem 1, without sacrificing too much accuracy. Furthermore, we provide the generalization error bound of the multilabel classification problem using our proposed stochastic sketch model. To measure the quality of approximation, we first define the δ-optimality approximation as follows:

Definition 2 (δ-Optimality Approximation). Given δ ∈ (0, 1), ˆ V is a δ-optimality approximation solution, if

According to the properties of Matrix norm, we have g( ˆ V ) ≤ ||S||F f ( ˆ V ), so g( ˆ V ) is proportional to f( ˆ V ). Therefore, the closeness of g(ˆ V ) and f(V ∗ ) implies the closeness of f( ˆ V ) and f(V ∗ ).

3.1 σ-Subgaussian Sketch Guarantee

We first introduce the tangent cone, which is used by [Rockafellar and Wets, 2004]:

Definition 3 (Tangent Cone). Given a set C ⊆ Rp and x∗ ∈ C, the tangent cone of C at x∗ is defined as K = clconv{r ∈ Rp |r = t(x - x∗ ) for some t ≥ 0 and x ∈ C}, where clconv denotes the closed convex hull.

The tangent cone arises naturally in the convex optimality conditions: any r ∈ K defines a feasible direction at the optimal x∗ , and optimality means that it is impossible to decrease the objective function by moving in directions belonging to the tangent cone. Then, we introduce the Gaussian width, which is an important complexity measure used by [Gordon, 1985]:

Definition 4 (Gaussian Width). Given a closed set Y ⊆ Rn , the Gaussian width of Y, denoted by ω(Y), is defined as:

where g ∼ N(0, In×n).

This complexity measure plays an important role in learning theory and statistics [Koltchinskii and Panchenko, 2000]. Let Sn-1 = {z ∈ Rn |||z||2 = 1} be the Euclidean sphere. XK represents the linearly transformed cone: {Xr ∈ Rn |r ∈ K}, and we use Gaussian width to measure the width of the intersection of XK and Sn-1 . This paper defines Y = XK ∩ Sn-1 . We state the following theorem for guaranteeing the σ-Subgaussian sketch:

Theorem 1. Let S ∈ Rm×n be a stochastic σ-Subgaussian

sketch matrix, c1 and c2 be universal constants. Given any δ ∈ (0, 1) and m = O(( c1 δ )2ω2 (Y)), then with probability at least 1 - 6qe- c2mδ2 σ4 , ˆ V is a δ-optimality approximation solution.

The proof sketch of this theorem can be found in the Appendix.

Remark. Theorem 1 guarantees that the stochastic σSubgaussian sketch method is able to construct a small sketch of the full data set for the fast optimization of problem 1, while preserving the δ-optimality of the solution.

3.2 Walsh-Hadamard Sketch Guarantee

We generalize the concept of Gaussian width to two additional measures, S-Gaussian width and Rademacher width:

Definition 5 (S-Gaussian Width). Given a closed set Y ⊆ Rn and a stochastic sketch matrix S ∈ Rm×n , the SGaussian width of Y, denoted by ωS(Y), is defined as:

where g ∼ N(0, Im×m).

Definition 6 (Rademacher Width). Given a closed set Y ⊆ Rn , the Rademacher width of Y, denoted by Υ(Y), is defined as:

where ϖ ∈ {±1}n is an i.i.d. vector of Rademacher variables.

Next, we still define Y = XK∩Sn-1 and state the following theorem for guaranteeing the Walsh-Hadamard sketch:

Theorem 2. Let S ∈ Rm×n be a stochastic WalshHadamard sketch matrix, c1, c2 and c3 be universal constants. Given any δ ∈ (0, 1) and m = O(( c1 δ )2 (Υ(Y) + √6log(n))2ω2S (Y)), then with probability at least 1 - 6q( c2 (mn)2 + c2e- c3mδ2 Υ(Y)2+log(nm) ), ˆ V is a δ-optimality approximation solution.

Remark. An additional term (Υ(Y) + √6log(n))2 appears in the sketch size, so the required sketch size for the Walsh-Hadamard sketch is larger than that required for the σ-Subgaussian sketch. However, the potentially larger sketch size is offset by the much lower cost of matrix multiplications via the stochastic Walsh-Hadamard sketch matrix. Theorem 2 guarantees that the stochastic Walsh-Hadamard sketch method is also able to construct a small sketch of the full data set for the fast optimization of problem 1, while preserving the δ-optimality of the solution.

3.3 Generalization Error Bound

This subsection provides the generalization error bound of the multi-label classification problem using our proposed two stochastic sketch models. Because our results can be applied to two models, we simply call our stochastic sketch models SS. Assume our model is characterized by a distribution D on the space of inputs and labels X × {0, 1}q , where X ⊆ Rp . Let a sample {(x(j) , y(j) )} be drawn i.i.d. from the distribution D, where y(j) ∈ {0, 1}q (j ∈ {1, . . . , n}) are the ground truth label vectors. Assume n samples D = {(x(1) , y(1) ), · · · , (x(n) , y(n) )} are drawn i.i.d. n times from the distribution D, which is denoted by D ∼ Dn . For two inputs x(z) , x(j) in X, we define d(x(z) , x(j) ) = ||x(z) - x(j) ||2 as the Euclidean metric in the original input space and dpro(x(z) , x(j) ) = ‖ˆ V ′x(z) - ˆ V ′x(j) ‖2 as the metric in the embedding input space. Let hDknni (x) represent the prediction of the i-th label for input x using our model SSkNN, which is trained on D. The performance of SS-kNN: (hDknn1 (·), · · · , hDknnq (·)) : X → {0, 1}q is then measured in terms of its generalization error, which is its expected loss on a new example (x, y) drawn according to D:

where yi means the i-th label and ℓ(yi, hDknni (x)) represents the loss function for the i-th label. We define the loss function as follows for the analysis.

For the i-th label, we define the function as follows:

The Bayes optimal classifier b∗ for the i-th label is defined as

Before deriving our results, we first present several important definitions and theorems.

Definition 7 (Covering Numbers, [Shawe-Taylor et al., 1998]). Let (X, d) be a metric space, A be a subset of X and ε > 0. A set B ⊆ X is an ε-cover for A, if for every a ∈ A, there exists b ∈ B such that d(a, b) < ε. The εcovering number of A, N(ε, A, d), is the minimal cardinality of an ε-cover for A (if there is no such finite cover then it is defined as ∞).

Definition 8 (Doubling Dimension, [Krauthgamer and Lee, 2004]). Let (X , d) be a metric space, and let ¯λ be the smallest value such that every ball in X can be covered by ¯λ balls of half the radius. The doubling dimension of X is defined as : ddim(X ) = log2(¯λ).

Theorem 3 ([Krauthgamer and Lee, 2004]). Let (X, d) be a metric space. The diameter of X is defined as diam(X) = sup x,x′∈X d(x, x′ ). The ε-covering number of X, N(ε, X, d), is bounded by:

We provide the following generalization error bound for SS-1NN:

Theorem 4. Given a metric space (X, dpro), assume function ν i : X → [0, 1] is Lipschitz with constant L with respect to the sup-norm for each label. Suppose X has a finite doubling dimension: ddim(X) = D < ∞ and diam(X) = 1. Let D = {(x(1) , y(1) ), · · · , (x(n) , y(n) )} and (x, y) be drawn i.i.d. from the distribution D. Then, we have

Inspired by Theorem 19.5 in [Shalev-Shwartz and BenDavid, 2014], we derive the following lemma for SS-kNN:

Lemma 1. Given metric space (X, dpro), assume function ν i : X → {0, 1} is Lipschitz with constant L with respect to the sup-norm for each label. Suppose X has a finite doubling dimension: ddim(X) = D < ∞ and diam(X) = 1. Let D = {(x(1) , y(1) ), · · · , (x(n) , y(n) )} and (x, y) be drawn i.i.d. from the distribution D. Then, we have

The following corollary reveals important statistical properties of SS-1NN and SS-kNN.

Corollary 1. As n goes to infinity, the error of the SS-1NN and SS-kNN converges to the sum of twice the Bayes error and 1+√8/k times Bayes error over the labels, respectively.

4 Experiment

4.1 Data Sets and Baselines

We abbreviate our proposed stochastic σ-Subgaussian sketch and stochastic Walsh-Hadamard sketch to SS+GAU and SS+WH, respectively. In the experiment, we set the entries in the σ-Subgaussian sketch matrix as i.i.d standard Gaussian entries. This section evaluates the performance of the proposed methods on four data sets: corel5k, nus(vlad), nus(bow) and rcv1x. The statistics of these data sets are presented in website 1 . We compare SS+GAU and SS+WH with several state-of-the-art methods, as follows.

• BR [Tsoumakas et al., 2010]: We implement two base classifiers for BR. The first uses linear classification/regression package LIBLINEAR [Fan et al., 2008] with l2-regularized square hinge loss as the base classifier. We simply call this baseline BR+LIB. The second uses kNN as the base classifier. We simply call this baseline BR+kNN and count the kNN search time as the training time.
• FastXML [Prabhu and Varma, 2014]: An advanced treebased multi-label classifier.
• SLEEC [Bhatia et al., 2015]: A state-of-the-art embedding method, which is based on sparse local embeddings

1 http://mulan.sourceforge.net

for large-scale multi-label classification. We use solvers of FastXML and SLEEC provided by the respective authors with default parameters.

Following the similar settings in [Zhang and Zhou, 2007] and [Bhatia et al., 2015], we set k = 10 for the kNN search in all kNN based methods. The sketch size m is chosen in a range of {64, 128, 256, 512, 1024}. Following [Chen and Lin, 2012], [Zhang and Schneider, 2012] and [Guo and Schuurmans, 2013], we consider the Hamming Loss and ExampleF1 measures to evaluate the prediction performance of all the methods. The smaller the value of the Hamming Loss, the better the performance, while the larger the value of ExampleF1, the better the performance.

4.2 Results

Figure 1 shows that with the increasing sketch size, the training time of SS+GAU and SS+WH rise, while the prediction performance of SS+GAU and SS+WH becomes better. The results verify our theoretical analysis. The Hamming Loss, Example-F1 and training time comparisons of various methods on corel5k, nus(vlad), nus(bow) and rcv1x data sets are shown in Table 1, Table 2 and Table 3, respectively. From Tables 1, 2 and 3, we can see that:

• BR and SLEEC usually achieve better results, which is consistent with the empirical results in [Bhatia et al., 2015] and [Taha and Tiun, 2016]. However, SLEEC is the slowest method compared to other baselines.
• Because we perform the optimization only on a small sketch of the full data set, our proposed methods are significantly faster than BR and state-of-the-art embedding approaches. Moreover, we can maintain competitive prediction performance by setting an appropriate

sketch size. The empirical results illustrate our theoretical studies.

5 Conclusion

This paper carefully constructs stochastic σ-Subgaussian sketch and Walsh-Hadamard sketch for multi-label classification. From an algorithmic perspective, we show that we can obtain answers that are approximately as good as the exact answer for BR. From a statistical learning perspective, we also provide the generalization error bound of multi-label classification using our proposed stochastic sketch model. Lastly, our empirical studies corroborate our theoretical findings, and demonstrate the superiority of the proposed methods.

Acknowledgments

The author would like to thank all the anonymous reviewers for their useful comments.

A The Proof Sketch of Theorem 1

We first present the following lemma, which is derived from [Mendelson et al., 2007].

Lemma 2. Let S ∈ Rm×n be a stochastic σ-Subgaussian sketch matrix. Then there are universal constants c1 and c2 such that for any subset Y ⊆ Sn-1 , any u ∈ Sn-1 and δ ∈ (0, 1), we have

with probability at least 1 - e- c2mδ2 σ4 , and we have

with probability at least 1 - 3e- c2mδ2 σ4 , where S = S′S - In×n.

Proof. (of Theorem1). We first show that ˆ V is a δ-optimality approximation solution from the right hand. Let V ∗ 1 , · · · , V ∗ q , ˆ V1, · · · , ˆ Vq and Y1, · · · , Yq be q columns of matrix V ∗ , ˆ V and Y , respectively. Then ||XV ∗ -Y ||2F and ||SX ˆ V -SY ||2F can be decomposed to ||XV ∗ -Y ||2F = ∑qi=1 ||XV ∗ i -Yi||22 and ||SX ˆ V -SY ||2F = ∑qi=1 ||SXˆ Vi - SYi||22 . Next, we study the relationship between ||XV ∗ i -Yi||22 and ||SXˆ Vi -SYi||22 . We define M = ˆ Vi-V ∗ i . According toDefinition 3, we know that M belongs to the tangent cone of C at V ∗ i .

Because V ∗ i ∈ argminr∈Rp ||Xr-Yi||22 , we have ||XV ∗ i - Yi||22 ≤ ||X ˆ Vi-Yi||22 = ||XV ∗ i -Yi||22+2〈XV ∗ i -Yi,XM〉+ ||XM||22 . Consequently, we obtain:

As ˆ Vi ∈ argminr∈Rp ||SXr - SYi||22 , we have ||SXV ∗ i - SYi||22 ≥ ||SXˆ Vi - SYi||22 = ||SXV ∗ i - SYi||22 + 2〈SXV ∗ i -SYi, SXM〉+||SXM||22 . Consequently, we obtain ||SXM||22 ≤ -2〈SXV ∗ i -SYi, SXM〉 ≤ 2||SXV ∗ i - SYi||2||SXM||2 and

We derive the following:

By using Lemma 2, with probability at least 1 - 4e- c2mδ2 σ4 , we have

where Y = XK ∩ Sn-1 . Given γ > 0, we have 2||XV ∗ i - Yi||2||XM||2 ≤ γ||XV ∗ i - Yi||22 + 1/γ||XM||22 . For the sake of clarity, we define ψ = 1 + 5c1 √m ω(Y) + 3δ and ϕ = 1+ c1 √m ω(Y) + δ, and then substitute them to the above

expression, with probability at least 1 - 4e- c2mδ2 σ4 , we have

Clearly, we have ω( XV ∗ i -Yi ||XV ∗ i -Yi||2 ) ≤ ω(Y). By using Lemma

By using Lemma 2, with probability at least 1 - e- c2mδ2 σ4 , we have ||SXM||22 = ||XM||22 + 〈XM,SXM〉 ≥ ||XM||22 (1 - c1 √m ω(Y) - δ) = ||XM||22 (2 - ϕ). By using Eq.(13), with probability at least 1 - e- c2mδ2 σ4 , we have

Eq.(14), Eq.(15) and Eq.(16) imply that, with probability at least 1 - 6e- c2mδ2 σ4 , we have

By setting γ = 4, with probability at least 1 - 6e- c2mδ2 σ4 , we have

Eq.(18) implies that, with probability at least 1-6qe- c2mδ2 σ4 , we have