Multi-Class Learning using Unlabeled Samples: Theory and Algorithm

1 Introduction

Multi-class classification is an import task in machine learning, with numerous applications such as text categorization, image annotation, etc. Estimating the generalization performance of algorithms is useful for understanding the factors that influence their behavior, as well as suggesting ways to improve them. Many works have studied generalization ability of supervised multi-class classification, but there are still a lot of statistical challenges in the semi-supervised case.

To study the generalization ability of multi-class classification algorithms, researchers have developed useful tools to measure the richness of the hypothesis space, including dataindependent measures and data-dependent measures. Dataindependent measures, such as VC-dimension [Allwein et al., 2000] and Natarajan dimension [Daniely et al., 2015], typically provide conservative multi-class bounds. As one of the most successful data-dependent complexity measures, the Rademacher complexity was first introduced into the multiclass setting in [Koltchinskii et al., 2001] and further studied in [Cortes et al., 2013; Maximov and Reshetova, 2016]. The convergence rates of multi-class classification bounds using Rademacher complexity are O(K/√n) at best, where K and n are the number of classes and the size of labeled samples, respectively. A delicate error bound which exhibits logarithmic dependence on the class size was proposed in [Lei et al., 2015]. While the global Rademacher complexity captures the complexity of the entire class, the local Rademacher complexity is used to choose a favorable subset from the hypothesis space [Bartlett et al., 2005], always leading better statistical properties. The state-of-the-art error bound of kernelbased multi-class classification was established in [Li et al., 2018] by using the local Rademacher complexity.

∗Corresponding author

In this paper, we derive a novel data-dependent generalization error bound for multi-class classification in linear space by using the notion of the local Rademacher complexity and additional unlabeled samples. The convergence rate of the bound is O(K/√n+u + 1/n), where u is the number of unlabeled samples, which is much faster than the rate of common bounds O(K/√n). Further, motived by the statistical analysis, we devise an efficient multi-class classification algorithm by combining the local Rademacher complexity and unlabeled samples. Our approach improves both computational efficiency and statistical guarantee. Computational gains come from linear multi-class estimator and stochastic gradient descent algorithm on the primal form. Statistical gains lie in a smaller hypothesis space by using the local Rademacher complexity and unlabeled samples. Experiential learning reveals our approach outperforms other linear multiclass algorithms with or without unlabeled data.

1.1 RelatedWork

By using the local Rademacher complexity, a sharper multiclass error bound with fast rate O( log2 K/n) was reached in [Li et al., 2018]. But it focused on supervised settings and kernel-based estimators which limits its applications in realworld datasets. For partially labeled data in multi-class settings, much progress has been accomplished in algorithmic front, but there are still a lot of challenges in theoretical front. Theoretical results for semi-supervised learning mainly consider the binary case, such as generalization analysis based on the global Rademacher complexity [Balcan and Blum, 2010; Oneto et al., 2011] and based on the local Rademacher complexity [Oneto et al., 2015]. In semi-supervised margin-based multi-class learning, the global Rademacher complexity for multi-class classifier trained with a two-step semi-supervised model is exploited in [Maximov et al., 2018], of which the convergence rate is O(√K/n + K√K/u). In this work, we derive a much shaper generalization bound for multi-class classification with fast rate O(K/√n + u + 1/n), by using the local Rademacher complexity and unlabeled samples.

2 ProblemDefinition

In a standard semi-supervised learning setting, a set of labeled samples Dl = {(x1, y1), · · · , (xn, yn)} are i.i.d. sampled from distribution µ over X × Y and unlabeled ones Du = {x1, · · · , xu} are i.i.d. drawn according to the marginal distribution µX of µ over X , typically n ≪ u. Further, we consider multi-class classification with K ≥ 2 categories, where xi ∈ Rd and yi ∈ {1, 2, · · · ,K}.

2.1 MaximumMarginMulti-Class Classification

To evaluate the probability of x belonging to each category, we wish to learn a scoring rule from the hypothesis space H

where h ∈ H,W ∈ Rd×K and x ∈ Rd , thus h is a vectorvalued function with mapping X → RK . The predictor uses the following mapping to predict labels

where h(x, y) = [WT x]y means the y-th value in vector WT x. For any hypothesis h ∈ H, the margin of a labeled example (x, y) is defined as

The h misclassifies example (x, y) if ρh(x, y) ≤ 0, thus the expected risk incurred from using h for prediction is L(h) := Eµ[1ρ(x,y)≤0], where 1t≤0 is the 0-1 loss. Since 0-1 loss is noncontinuous thus hard to deal with, we consider the popular hinge loss ℓ(ρh(x, y)) = |1-ρh(x, y)|+ which upper bounds the 0-1 loss and its smooth extension the square hinge loss ℓ(ρh(x, y)) = (1 - ρh(x, y))2+.

Let the expected loss be L(ℓ) = Eµ[ℓ(ρh(x, y))] and empirical loss be ̂L(ℓ) = 1n ∑ni=1 ℓ(ρh(x, y)) with respect to h. The loss space associated with H is defined as bellow

In theoretical analysis, we use two standard assumptions:

(1) Any ℓ(ρh(x, y)) is continuous and bounded in [0, 1], satisfied by normalized h(x).

(2) ℓ is L-Lipschitz continuous, such that

Note that both hinge loss and square hinge loss satisfy the above two assumptions.

Remark 1. Although the estimator is defined in linear space, it can be extended into reproducing kernel Hilbert space by feature mapping φ(·), i.e., κ(x, x′ ) = 〈φ(x), φ(x′ )〉 where κ : X × X → R be a Mercer kernel with φ being the associated feature mapping.

2.2 Definitions

Before theoretical analysis, we introduce some definitions.

Definition 1. Consider a local normalized loss space Lr

where L[(αℓ)2 ] = Eµ[ℓ2 (ρh(x, y))]. And the corresponding hypothesis space is defined as

Definition 2. The empirical Rademacher complexity of loss space Lr on labeled data and all data are

where σ1, σ2, · · · , σn+u are {±1}-valued independent Rademacher random variables with probability P(σi = +1) = P(σi = -1) = 1/2. Their deterministic counterparts are Rn(Lr) = Eµ ̂Rn(Lr) and R(Lr) = Eµ ̂R(Lr).

Definition 3. The empirical local Rademacher complexity of hypothesis space Hr on all data is defined as

where σ1, σ2, · · · , σn+u are {±1}-valued independent Rademacher random variables with probability P(σi = +1) = P(σi = -1) = 1/2. The expected counterpart on all data is R(Hr) = Eµ ̂R(Hr).

Remark 2. For i ∈ {1, · · · , n}, labels of y◦ i corresponds to labels in Dl. For i ∈ {n+ 1, · · · , n+u}, y◦ i are pseudolabeled, as a consequence ̂R(Hr) actually is not computable.

3 Shaper Generalization Error Bound

In this section, we present a shaper generalization error bound for multi-class classification by using the local Rademacher complexity and unlabeled data and consider the supervised case in Corollary 1. Proof details are deferred in Section 7.

Theorem 1. For any ℓ ∈ Lr : X × Y → [0, 1], ∀k > 1, ‖W‖ ≤ 1 and ∀ δ ∈ (0, 1), the following holds with probability at least 1- δ,

where c1 = (3 + 4k) log(1/δ), c2 = 32kθ and c3 = 64kL, λj(W) is the j largest singular value of matrixW.

Note that the bound partially depend on ∑j>θ λj(W) which represents the tail sum of singular values, while the global Rademacher complexity bounds depend on the trace. The convergence rate of above bound presented in Theorem 1 is O(1/n) or O(K∑j>θ λj(W)/√n+u), much faster than common rate O(K/√n). When there is no unlabeled data, namely u = 0, the result in Corollary 1 reduces to the state-of-the-art multi-class bound [Li et al., 2018].

Corollary 1. For any ℓ ∈ Lr : X × Y → [0, 1], ∀k > 1, ‖W‖ ≤ 1 and ∀δ ∈ (0, 1), with probability at least 1 - δ,

where c1 = (3 + 4k) log(1/δ), c2 = 32kθ and c3 = 64kL.

3.1 Comparison with Other Bounds

VC dimension Bound

VC-dimension is a general distribution free complexity measure in statistical learning. VC-dimension was applied to generalization analysis in multi-class area [Allwein et al., 2000] and a data-independent bound is derived: L(ℓ) ≤ ̂L(ℓ) +O(√V logK/√n), where V is the VC-dimension.

Rademacher Complexity Bounds

In terms of the global Rademacher complexity, a data dependent margin-based multi-class classification bound was proposed in [Koltchinskii and Panchenko, 2002], of which the convergence rate is O(K2 /√n). Moreover, the bound was improved to O(K/√n) in [Maximov and Reshetova, 2016]. Lei et al. stated a bound reducing the dependence on the class size [Lei et al., 2015], that is O((logK)/√n). The global Rademacher complexity multi-class bounds were extended into semi-supervised case in [Maximov et al., 2018], of which the convergence rate is O(√K/n +K√K/u).

Local Rademacher Complexity Bounds

As we all know, the local Rademacher complexity was firstly presented in binary settings and obtained shaper error bounds [Bartlett et al., 2005]. Furthermore, it was extended into multi-class learning in [Li et al., 2018] and derived a sharper data dependent bound only using labeled data.

In this paper, we propose a novel local Rademacher complexity bound for multi-class learning using both labeled and unlabeled samples in Theorem 1. When there is no unlabeled samples available, we derive Corollary 1, achieving similar bounds as [Li et al., 2018]. (1) In common case, we observe that the bound shown in Theorem 1 is at most of order O(K/√n + u + 1/n), while convergence rate of others is usually at O(K/√n), such that faster convergence rate is obtained in the common case. (2) In the special case that the singular values decrease exponentially, the convergence rate is O((c1 + c2) log2 K/n) in [Li et al., 2018], while it is O(c1/n) in Theorem 1, thus much smaller constant on is derived in the special case. Therefore, the proposed linear multi-class approach improves current multi-class bounds with faster convergence rate or smaller constant. Table 1 reports statistical properties of related approaches and ours.

4 Algorithms

4.1 Previous Works

Consider a similarity matrix S on entire n + u examples and the weight Sij represents the similarity between xi and xj, for example, kernel weights Sij = exp(-‖xi - xj‖2 /σ2 ). Motivated by continuity assumption that similar points share same label, the cost function for multi-class classification is

where X ∈ Rd×(n+u) , graph Laplacian L = D - S and D is a diagonal matrix with Dii = ∑n+u j=1 Sij.

To make use of unlabeled samples, some novel algorithms are developed for multi-class learning in semi-supervised settings. Liu and Chang proposed transductive semi-supervised multi-class learning by minimizing cost function E(h) to propagate labels [Liu and Chang, 2009]. Instead of transductive learning, manifold regularization is introduced into semi-supervised multi-class learning, which minimizes the cost function together with empirical error and the penalty of estimator complexity [Li and Guo, 2015; Li et al., 2017b].

4.2 Optimization

Theoretical analysis demonstrates that both the smaller tail sum of singular values ∑j>θ λj(W) and the number of unlabeled samples can improve generalization performance. Therefore, instead of traditional regularized empirical risk minimization, we consider minimizing the combination of the empirical loss, the penalty term on estimator complexity, the local Rademacher complexity and Laplacian regularization term in the following form

where ℓ(h(xi), yi) = |1-(h(xi, yi)-maxy′ ̸=yi h(xi, y′ ))|+, λj(W) denotes the j-th largest singular value of W ∈ Rd×K , and τA, τI and τS are regularization parameters. τI can be set zero when there is no unlabeled data available.

Similar to the minimization of matrix trace, minimization of the tail sum of singular values is also nonconvex, thus the optimization problem in Eq. (1) is nonconvex. But minimizing the sum of a part of singular values is quite different from minimizing the sum of all singular values. Generalized SVT algorithms with two-step updating were designed [Lu et al., 2015; Xu et al., 2016] to minimize the sum of a part of singular values. Based on generalized SVT methods, we devise a proximal stochastic sub-gradient singular value thresholding multi-class learning framework, named PS3VT which is shown in Algorithm 1. The algorithm PS3VT updates W twice in each iteration, firstly updating W according to firstorder sub-gradient of terms except for the tail sum of singular values, and then updating W with a closed form solution given by singular value thresholding (SVT).

4.3 SVT with Proximal Gradient

For the sake of simplification, we rewrite optimization (1) as

In each iteration, to obtain a tight surrogate of Eq. (2), we keep τS ∑j>θ λj(W) while relaxing g(W) only, that leads

where 1µ actually is the step size to update gradients.

Proposition 1 (Theorem 6 of [Xu et al., 2016]). Let Q ∈ Rd×K with rank r and its SVD decomposition is Q = UΣVT , where U ∈ Rd×r and V ∈ RK×r have orthogonal columns, Σ is diagonal. Then,

is given by Dθ τ = UΣθτ VT , where Σθτ is diagonal with

4.4 Sub-Gradient

According to Eq. (3) and hinge loss is non-smooth, we need to solve the sub-gradient of g(W). It is similar to solve the SVM optimization problem in the primal, which has been solved by Pegasos algorithm [Shalev-Shwartz et al., 2011]. We also consider sub-gradient descend method in PS3VT. The sub-gradient of hinge loss in Eq. (2) is

Bacause gradient descend (GD) and stochastic gradient descend (SGD) are suitable for different situations, we explore them individually. In each iteration, for GD the gradient updates on the entire dataset

Algorithm 1 Proximal Stochastic Sub-gradient Singular Value Thresholding (PS3VT)

Output: W

Compute Laplacian matrix L.

Choose sample xit ∈ Dl uniformly at random. Compute sub-gradient ∇g(Wt ) sample xti ,

Compute SVD decomposition

Update Wt+1 using Proposition 1

NormalizeWt+1 by

end for

For SGD, the gradient updates on a random sample x′

Applying Proposition 1, the update of Wt in equation (3) becomes Wt+1 = Dθ τ (Q) where

and τ = τS µ . The updates combine gradient descent and SVT.

4.5 Time Complexity

The time complexity of each iteration consists of two parts: sub-gradient and SVT in each iteration:

Sub-Gradient

Laplacian regularization related termXLXT is computed before iterations, and the computing XLXT W needs O(d2K). Time complexity is O(d2K) for SGD and O(ndK + d2K) for GD in each iteration.

Singular Values Thresholding (SVT)

In this part, SVD decomposition determines the time complexity, which is O( min(d2K, dK2 )) for both SGD and GD.

In each iteration, update of matrix W follows above two steps, of which time complexity is determined by updating sub-gradient for SGD it is O(d2K) and for GD it is O(ndK+d2K). It is apparent that for the time complexity of GD in each iteration is associated with labeled sample size n, which is unfeasible when dealing with large datasets. While SGD update gradients on a random sample in each iteration with early stopping [Camoriano et al., 2016], thus it is more suitable for large scale dataset. The total time complexity of SGD is O(d2Kt), where t is the number of iterations.

4.6 Connections with Other Algorithms

PS3VT is a generalized multi-class learning framework, of which different parameters settings specialize PS3VT to other multi-class classification algorithms. Let τA > 0 and hinge loss in terms of multi-class maximum margin. Connections with other algorithms are reported in Table 2.

1. When both of τI and τI are zeros, the form is maxmargin multi-class problem studied in [Koltchinskii et al., 2001], which constitutes a strong baseline.
2. When τI = 0 and τS > 0, the local Rademacher complexity was applied on multi-class area, which was firstly introduced into kernel-based multi-class learning [Li et al., 2018], while ours in linear space.
3. When τI > 0 and τS = 0, the problem becomes semisupervised multi-class learning, studied in [Li et al., 2015].

5 Experiments

In this section, we study the empirical behavior of our proposed algorithm PS3VT with several experiments in terms of test error, the convergence and relation between error rate and rate of labeled data. For each dataset, we compute the adjacency matrix S by 10-NN graph with similarity Sij = e-‖xi-xj‖2 /σ2 , where σ = ∑n+u i=1 ‖xi -xj‖/(n+u). Laplacian graph is defined as L = D - W, where D is the diagonal matrix with Dii = ∑n+u j=1 Sij. For fair comparison, before a method runs on any dataset, we employ 5-folds cross validation to obtain the optimal parameter set by grid search over candidate sets complexity parameter τA ∈ {10-15 , 10-14 , · · · , 10-6 }, unlabeled samples parameter τI ∈ {0, 10-15 , 10-14 , · · · , 10-6 }, local Rademacher complexity parameter τS ∈ {0, 10-10 , 10-9 , · · · , 10-1 }, step size 1µ ∈ {101 , 102 , · · · , 105 } and tail parameter θ ∈ {0.5, 0.6, · · · , 0.9} × min(|K|, |d|). Experiment 2 and Experiment 3 run on a randomly selected dataset to compare the convergences and influence of unlabeled samples.

Note that, in the algorithm, we use cross-validation to tune those regularization parameters, which significantly influences the empirical performance of methods but also cause a large computational burden. Beyond cross-validation, we consider more efficient model selection tools [Li et al., 2017a; Liu et al., 2017; Liu et al., 2019] to tune parameters in future.

5.1 Comparison of Test Error

We run PS3VT and the compared methods on 15 multi-class datasets and report the results in Table 3. Labeled and unlabeled samples are given by stratified random sampling from train data that 30% as labeled samples and the rest as unlabeled ones. To obtain stable results, we run methods on each dataset 30 times with randomly partition such that 70% data for training and 30% data for testing. Further, those multiple test errors allow the estimation of the statistical significance of difference among methods. The statistical significance in Table 3 refers to 95% level of significance under t-test.

The results in Table 3 show: (1) Our method outperforms the others almost on all datasets except iris and satimage. (2) The classical linear margin-based multi-class classification in [Koltchinskii et al., 2001] was defeated by other methods on all datasets. (3) Only combining the local Rademacher complexity or unlabeled samples can still obtain better empirical performance than the primal Linear-MC.

5.2 Comparison of Convergence

We explore the convergence of all methods on pendigits, under the same parameters setting and data partition in the above Experiment. The left of Figure 1 reports average test errors various on iterations on pendigits, showing our proposed PS3VT reaches a lower error rate than others, LRC-MC and SS-MC give better convergence than Linear-MC as well. The convergence speeds of all methods stay at the same level.

5.3 Influence of the Rate of Labeled Samples

The right of Figure 1 demonstrates the influence of the number of labeled samples. As the growth of the number of labeled samples, test errors of all methods decrease. PS3VT outperforms the others and get similar results with LRC-MC when all training data are labeled. Linear-MC is worse than the others and gets similar results with SS-MC when all training data are labeled. SS-MC gives better test errors than LRCMC when the rate of labeled data is small, but the performance of LRC-MC has an advantage over which of SS-MC when the rate of labeled data is larger than 60%.

6 Conclusion

Motivated by the idea of taking advantage of unlabeled samples and local Rademacher complexity, we study the generalization behavior of multi-class classification. We combine linear multi-class estimator with the local Rademacher complexity and unlabeled samples, achieving a shaper multiclass generalization error bound with faster convergence rate or smaller constants. Driven by theoretical analysis, we propose a nonconvex optimization problem and design an efficient stochastic gradient descent algorithm to solve it. Further, our theoretical analysis and algorithm can be improved by Random Feature and extended to multi-label learning.

7 Proof

Theorem 2. For any ℓ ∈ Lr : X × Y → [0, 1], consider a sub-root function ψ(r) with fixed point r∗ and such that ∀r > r∗ , KLR(Hr) ≤ ψ(r), then ∀ℓ ∈ Lr and ∀k > 1, with probability at least 1 - δ

where c1 = (3 + 4k) log(1/δ), c4 = 32k.

Proof. Since ℓ is L-Lipschitz continuous, exploiting the contraction inequality [Koltchinskii, 2011] and applying Lemma 1 in [Maximov and Reshetova, 2016], we have

So we have R(Lr) ≤ KLR(Hr). According Lemma A.6 in [Oneto et al., 2015], we have Rn(Lr) = R(Lr).

With Rn(Lr) ≤ KLR(Hr) ≤ ψ(r) and Theorem 3.3 in [Bartlett et al., 2005] with α = 1, we complete the proof.

Theorem 3. Let W = UΣV be SVD decomposition of W,U and V are unitary matrices with size of d × d and K × K respectively, and Σ is a d × K matrix with singular values {λj} on the diagonal in descending order. Assume ‖W‖ ≤ 1, such that the local Rademacher complexity R(Hr) over all examples is upper bounded by

Proof. Let Eµ‖xTi xi‖ ≤K√r/Lby normalization. According to Definition 1 that L(ℓ2 ) ≤ r, let

So subset space of hypothesis Hr is satisfied L(ℓ2 ) ≤ r when Eµ‖WT W‖ ≤ √r KL . By proof in Theorem 5 of [Xu et al., 2016] with Eµ‖WT W‖ ≤ √r KL , we complete the proof.

Proof of Theorem 1. Applying Theorem 3 we have

That is KLR(Hr) ≤ A√r + B when we set

Properties of sub-root function also show that ψ(r) ≤ r where r > r∗ , thus there is KLR(Hr) ≤ r.

Based on KLR(Hr) ≤ A√r + B and KLR(Hr) ≤ r, we consider choose r∗ by solution of A√r + B = r, such that

Applying the above into Theorem 2, we finish the proof.

Acknowledgments

This work is supported in part by the National Natural Science Foundation of China (No.61703396, No.61673293), the Youth Innovation Promotion Association CAS, the National Key Research and Development Program of China (No.2018YFC0823104, No.2016YFB1000604), the Science and Technology Project of Beijing (No.Z181100002718004) and the Excellent Talent Introduction of Institute of Information Engineering of CAS (Y7Z0111107).