R-SVM+: Robust Learning with Privileged Information

1 Introduction

Great advances in machine learning have been inspired by the deeper investigation into the learning process of human beings [Shen et al., 2014; Wang et al., 2018]. Conventional supervised methods utilize the priori knowledge to help us understand the world. Based on a set of examples and their corresponding labels, traditional supervised methods can train a classification model, and then use it to classify unknown test examples. However, in practice, there often exists some auxiliary information associated with an example except for its label. This auxiliary information can be widely found in human teaching and learning process. For example, the teacher plays an important role to provide students with helpful comments, comparisons, and explanations to improve students' performance. Inspired by this fact, Vapnik and Vashist [Vapnik and Vashist, 2009] introduced the paradigm of learning using privileged information (LUPI) that focuses on improving the learning with the auxiliary information which is supplied by a teacher about examples at the training stage. Since this auxiliary information will not be available at the test stage, it is referred to as privileged information.

∗Corresponding author: Bo Du.

As one of the most popular classifiers, support vector machine (SVM) was first upgraded in the paradigm of learning using privileged information (LUPI) [Vapnik and Vashist, 2009], and the new method is called SVM+. The main idea of SVM+ is to define a linear or nonlinear correcting (slack) function in the privileged feature space to estimate the slack variables in the standard SVM method using privileged information. Recently, an increasing attention has been attracted on the LUPI paradigm [Vapnik and Izmailov, 2015; Motiian et al., 2016; Zhou et al., 2016; Yang et al., 2017], and some SVM+-based algorithms have been proposed and applied for various applications. Beyond L-2 SVM, privileged information is also introduced into an L-1 regularized SVM to reduce time consumption on tuning model parameters [Niu et al., 2012]. Considering privileged label information in the multi-label learning problems, a privileged multi-label learning (PrML) method explores and exploits the connections between different examples' labels and is extended into domain adaptation [You et al., 2017]. Moreover, there are also multi-task multi-class SVM+ [Ji et al., 2012], structural SVM+ [Feyereisl et al., 2014], and the rank transfer method [Sharmanska et al., 2013]. Various optimization techniques to solve SVM+ have been studied recently, such as MATSVM+, CVX-SVM+, and L2-loss SVM+ [Li et al., 2016]. In [Li et al., 2016], two new algorithms are proposed to efficiently solve linear SVM+ and kernel SVM+ which uses the L2-loss based on the ρ-SVM formulation, respectively.

These methods have largely advanced the developments on LUPI. However, their successes are usually achieved in the circumstance that training and test data are deemed to be clean and the teacher always makes correct judgement. In practice, we can well design the training set under our demands, but it is difficult and even impossible to tell what test data will be. Existing methods lack clear strategies to address potential noises in the data, and thus their practical performances will be seriously deteriorated. In addition, existing methods in LUPI used to consider that teacher's comments are always accurate. But if there exist noises in the data, teacher may not be guaranteed to make correct judgements any more, which will then influence the student performance as a result.

In this paper, we derive a novel Robust SVM+ (R-SVM+) algorithm based on a rigorous theoretical analysis. Considering perturbations over both example feature data and privileged feature data, we study the lower bound of these perturbations that will mislead the model to make wrong judgements. A novel regularization function adapted from this lower bound is introduced to upgrade a variant form of SVM+. In this way, the capability of the learned model to tolerate perturbations over the data will be enhanced - that is to say the robustness of the model will be strengthened. The objective function of R-SVM+ is transformed into a quadratic programming problem, which can be efficiently optimized using off-the-shelf solvers. Experimental results demonstrate the necessity of researching robust SVM+ and the effectiveness of the proposed algorithm.

2 Preliminary of LUPI

The LUPI paradigm considers a set of training examples where privileged information is additionally supplied,

where xi ∈ Rd and x∗i ∈ Rd∗ are the i-th example feature (EF) vector and its corresponding privileged feature (PF) vector, yi ∈ {+1,-1} is the ground-truth label of the i-th training example pair (xi, x∗i ), and n is the number of training example pairs.

The first approach proposed in the LUPI paradigm is called SVM+ [Vapnik and Vashist, 2009], which tries to measure the misclassification loss of training example with a correcting function learned from privileged information. The objective function of SVM+ can be formulated as follows:

where w and w∗ are the weight vectors, b and b∗ are the bias terms, C is the a non-negative parameter which balances the loss term and the regularizer, the term ρ2 〈w∗ ,w∗ 〉 in Eq. (1) aims to restrict the capacity of the correcting function space, ρ > 0 is the trade-off parameter, the functions φ(·) and ψ(·) are two feature mappings induced by the kernels on example features and privileged features, respectively, and 〈a, e〉 denotes the inner product between two vectors a and e.

By introducing Lagrange multipliers αi ≥ 0 and βi ≥ 0, i = 1, . . . , n, we can arrive at the dual form of SVM+,

(2)

subject to constraints ∑ni=1 (αi +βi -C) = 0, ∑ni=1 αiyi = 0, αi ≥ 0, and βi ≥ 0, i = 1, . . . , n, and where k(xi, xj) = 〈φ(xi), φ(xj)〉 and k∗ (x∗i , x∗j ) = 〈ψ(x∗i ), ψ(x∗j )〉 are kernels in example feature and privileged feature spaces, respectively. After solving the dual optimization problem, two weight vectors can be reconstructed as w = ∑ni=1 αiyiφ(xi) and w∗ = 1ρ ∑ni=1 (αi + βi - C)ψ(x∗i ).

3 Robust SVM+

According to the constraint of Eq. (1), we can define two functions f (x) and g(x∗ ), where f (x) = 1-y[〈w, φ(x)〉+b] denotes a hinge loss of the decision function ℏ = 〈w, φ(x)〉+ b on the example (x, y) and g(x∗ ) = 〈w∗ , ψ(x∗ )〉 + b∗ denotes a loss of the correcting function on the privileged data x∗ . And f(x) and g(x∗ ) under the framework of SVM+ are

In the SVM+ method, the constraint yi[〈w, φ(xi)〉 + b] ≥ 1 - [〈w∗ , ψ(x∗i )〉 + b∗ ] in Eq. (1) can be written as Eq. (4). The inequality in Eq. (4) will be satisfied if x and x∗ are good enough for model training and a small loss f(x) in the decision space can be achieved. It is the basic assumption of LUPI that if a small loss in the correcting space can be obtained, then a small loss in the decision space should also be achieved [Pechyony and Vapnik, 2010],

However, in practice there may be some noises over x and x∗ sometimes. If perturbations caused by noises over examples are large enough, the inequality will not hold, which will then influence the correct decisions of the model on examples. In response to this circumstance, we propose to learn a Robust SVM+ (R-SVM+) algorithm, which has a stronger capability to tolerate perturbations over the data caused by noises. We assume there are some perturbations τx ∈ Rd and τx∗ ∈ Rd∗ over the ideal observations x and x∗ , respectively, i.e., x + τx and x∗ + τx∗ , which are large enough to make the following inequality satisfied,

Our purpose is to study what properties τx and τx∗ should have if Eq. (5) holds. Therefore, in the following, we proceed to show that these perturbations τx and τx∗ actually have the lower bounds based on a rigorous theoretical analysis. According to the theorem of calculus, we have

If the perturbations are serious enough, according to Eq. (5) and Eq. (6), the following inequality is satisfied,

where τ = [τx; τx∗] ∈ Rd+d∗ , ϖ(t, τx, τx∗) = [∇f(x + tτx); -∇g(x∗ +tτx∗ )] ∈ Rd+d∗ and we have applied H¨older inequality in the last step that the q-norm is dual to the pnorm, where p and q satisfy 1p + 1q = 1.

Hence, given g(x∗ ) ≥ f(x), we have the minimal perturbations τ that is required to reverse the decision of the SVM+ classifier,

Eq. (7) indicates the lower bound over the perturbations to bring in the undesirable error in Eq. (5). In order to obtain a more robust classifier, we consider maximizing the lower bound (i.e., the right of Eq. (7)). As a result, the new model will have more tolerances over the perturbations, and will thus be more robust. And this is the main idea of our proposed R-SVM+ algorithm. That is to say, we wants ∫ 1 0 ‖ϖ(t, τx, τx∗)‖qdt to be small as well as g(x∗ ) - f(x) to be large. Therefore, the new objective function of our proposed R-SVM+ have two components: 1) For f(x) ≤ g(x∗ )+ϵ, ϵ should be minimized; 2) minimizing the value of function Ψ(t, τx, τx∗ ) = ∫ 1 0 ‖ϖ(t, τx, τx∗)‖qdt.

3.1 Minimizing ϵ

First, we consider minimizing ϵ under the framework of SVM+. We replace the constraints f(xi) ≤ g(x∗i ), i = 1, . . . , n in the original SVM+ objective function with the constraints f(xi) ≤ g(x∗i ) + ϵi, where ϵi ≥ 0, i = 1, . . . , n. Then the optimization problem of this variant form of the SVM+ problem can be transformed into,

where σ > 0 is a tradeoff parameter. Similar variant of Eq. (8) has been discussed in [Vapnik and Vashist, 2009] as well, while in this paper we try to make the value g(x∗ ) - f(x) large to enhance the robustness according to Eq. (7). In order to minimize ϵ, the value of σ should be relatively larger compared with C, to reinforce the effect of the smooth function term ∑ni=1 ϵi on the solution. For simplicity, we let σ = σ′C, where σ′ > 1. By introducing Lagrange multipliers αi ≥ 0, βi ≥ 0 and ηi ≥ 0, where i = 1, . . . , n, the Lagrangian is constructed as

We set the derivatives of the Lagrangian function with respect to w, w∗ , b, b∗ , ϵ to zeros, and then the Karush-Kuhn-Tucker (KKT) conditions can be obtained. Accordingly, the dual problem of Eq. (8) can be rewritten as,

subject to constraints ∑ni=1 (αi +βi -C) = 0, ∑ni=1 αiyi = 0, 0 ≤ αi ≤ σ′C, and βi ≥ 0, where i = 1, . . . , n. We denote α ◦ y as the element-wise product between vectors α = [α1, . . . , αn]T ∈ Rn and y = [y1, . . . , yn]T ∈ Rn , β = [β1, . . . , βn]T ∈ Rn , 1 = [1, . . . , 1]T ∈ Rn , and C = [C, . . . ,C]T ∈ Rn . The dual problem can be further reformulated as

subject to constraints 1T(α + β - C) = 0, yTα = 0, 0 ≤ αi ≤ σ′C, and βi ≥ 0, i = 1, . . . , n. K ∈ Rn×n is the kernel matrix based on example features whose each element being Kij = k(xi, xj) and K∗ is the kernel matrix based on privileged features whose each element being K∗ ij = k∗ (x∗i , x∗j ) ∈ Rn×n .

3.2 Minimizing Ψ(t, τx, τx∗)

To minimize Ψ(t, τx, τx∗ ) = ∫ 1 0 ‖ϖ(t, τx, τx∗)‖qdt, we can first define the upper bound of perturbations over some fixed range Ωp(x, ℓ) = {z ∈ Rd |‖x - z‖p ≤ ℓ}. In this way, we ensure that the upper bound of τx and τx∗ is at most ℓ by making assertions of perturbations τx, τx∗ ∈ Ωp(0, ℓ). We further define z = x + tτx and z∗ = x∗ + tτ ∗ , 0 < t ≤ 1. In the following, we discuss the case where p = q = 2 for simplicity, and other cases will be studied in our future work. Then the inequality holds

Thus, our problem can be further transformed into minimizing the value of the upper bound, i.e., the right side of Eq. (10). Naturally, we consider using a surrogate Θ(f, g) of the quantity of right side of Eq. (10) for regularization. According to Eq. (3), we can obtain ∇f(x) = -y ∑ni=1 αiyi∇xk(xi, x) and ∇g(x∗ ) = 1ρ ∑ni=1 (αi +βi -C)∇x∗k(x∗i , x∗ ). Here we use the Gaussian kernel k(xi, xj) = e-γ‖xi-xj‖22 and we set γ = 1/D in the experiment, where D is the mean of distances among examples in the training set. And a novel regularization function Θ(f, g) is defined as follows,

3.3 Objective Function of R-SVM+

The objective of the proposed R-SVM+ algorithm aims to solve a maximization problem in Eq. (9) and a minimization problem in Eq. (12) at the same time. Therefore, we arrive at the objective function of R-SVM+ which is a minimization problem,

subject to 1T(α + β - C) = 0, yTα = 0, 0 ≤ αi ≤ σ′C, and βi ≥ 0, i = 1, . . . , n. And λ is a trade-off parameter to control the effect of the proposed regularization term. Eq. (13) can be reformulated with a simple calculation,

(14) We further define two matrices A = K + 2λ n ∑ns=1 Hs and B = K∗ + 2λ nρ ∑ns=1 H∗ s . And we let µ = [αT, βT]T ∈ R2n , v = [(1 + 1ρ BC)T, ( 1ρ BC)T]T ∈ R2n , and M = [A◦ (yyT) + 1ρ B 1ρ B 1ρ B 1ρ B ] ∈ R2n×2n . Finally, the optimiza-

tion problem of R-SVM+ can be rewritten as,

Eq. (15) is a typical quadratic programming problem [Gould and Toint, 2004; Coleman and Li, 1996], which can be efficiently solved by off-the-shelf quadratic programming solvers.

4 Experiments

In order to evaluate the robustness of our proposed R-SVM+ algorithm, we carry out experiments on three real-world datasets for digit classification, face pose classification and human activity recognition tasks, respectively.

4.1 Experimental Setting

Datasets

The experiments are executed on three real-world datasets, including the MNIST+ dataset [Vapnik and Vashist, 2009], the RGB-D Face dataset [Hg et al., 2012], and the Human Activity Recognition dataset [Anguita et al., 2013]. The MNIST+

dataset is used for the digit classification task that classifies two digits "5" and "8". It contains 2943 images of "5" and 3025 images of "8" from the MNIST database [LeCun et al., 1998]. A holistic (poetic) description [Vapnik and Vashist, 2009] for each image is translated into a 21-dimensional feature vector as privileged information. All the images of two digits in the MNIST+ dataset are resized into 10×10 pixels. The 100-dimensional vector of raw pixels is used as the example feature data for each image. The RGB-D Face dataset [Hg et al., 2012] contains color and corresponding depth images of faces of 31 people in different face poses and expressions taken by a Kinect sensor. The depth images are used as privileged information. For each person, the image of each face pose is taken repeatedly for 3 times, which results in 31 × 3 RGB-depth image pairs for each pose. The face pose recognition task is performed on this dataset. The Human Activity Recognition dataset [Anguita et al., 2013] contains 10299 instances of 30 people performing six activities (i.e., walking, walking upstairs, walking downstairs, sitting, standing, and laying) by wearing a smart phone on the waist. Each example for each activity is described by 561 dimensional features drawn from accelerometer, gyroscope, gravity signals and so on.

Implementation Details

For the MNIST+ dataset, it is randomly split into a training set of 100 images, a test set of 1866 images, and a validation set of 4002 [Vapnik and Vashist, 2009]. In the experiment, we randomly select 80 examples and their corresponding holistic descriptions from the training set as training examples for 10 times and classify the images on the test set.

For the RGB-D Face dataset, due to the small number of images per face pose, we merge the poses into four groups: looking up, looking forward, looking down and having facial expressions. Then we train a binary classifier on each pair of groups. We randomly split 40% color and corresponding depth image pairs per class for training, 30% image pairs per class for testing, and the rest 30% for validation for 10 times.

We crop each image into the same fixed size of 150×150 and convert each color image into a gray image. Then for each image, it is divided into 100 non-overlapping subregions in 15×15 and for each subregion we extract the LBP feature. By concatenating the LBP features derived from all subregions, PCA is then performed to obtain a 150-dimensional compact representation.

For the Human Activity Recognition dataset, we use the first 200-dimensional features which come from the accelerometer and gyroscope 3-axial raw signals and their separation into body and gravity acceleration signals as example features. The remaining 361-dimensional features that come from signals obtained by some post-processing such as a Fast Fourier Transform (FFT) and the magnitude calculated using the Euclidean norm, are used as privileged features. We train one binary classifier on each pair of groups in the experiment. For training we use 200 examples from the desired class and 200 examples randomly drawn from the rest of examples from the remaining classes. And 600 examples randomly selected from the desired class and the rest of classes respectively are used for testing. The remaining examples from the desired class and the same number of examples from the rest of classes are used as the validation examples.

For each dataset, we add white Gaussian noise to examples in the validation set and test set with a specific signal-to-noise ratio (SNR). The classification results in experiments are averaged over 10 independent trials.

4.2 ComparedMethods

For all the datasets, we evaluate performances of the proposed R-SVM+ algoirthm compared with the standard support vector machine (SVM), the robust SVM based on the rescaled hinge loss function (RSVM-RHHQ) [Xu et al., 2016], SVM+ [Vapnik and Vashist, 2009], and L2-SVM+ [Li et al., 2016] methods.

For all the methods, the regularization parameter C are selected from 10{-2,1,0,1,2} and the Gaussian kernel is used.

For SVM+, L2-SVM+ and the proposed R-SVM+, we set the parameter of Gaussian kernel γ = 1D where D is the mean of distances among examples in the training set according to [Li et al., 2016]. While for SVM and RSVM-RHHQ, γ is selected from 10{-3,-2,-1,0,1,2,3} , since significantly better performances can be achieved. For RSVM-RHHQ, the scaling constant η is varied in range of {0.01, 0.1, 0.5, 1, 2, 3, 10, 100}. For SVM+-based methods, the trade-off parameter ρ is selected from 10{-2,-1,0,1,2} . For the proposed R-SVM+, we also vary the parameter σ′ in range of {5, 10, 50, 100} and λ in range of 10{-5,-4,...,0,1} . The best parameters for all methods are determined with a joint cross validation model selection strategy on the validation set.

4.3 Performance Comparison

Table 1 summarizes the classification results of the proposed R-SVM+ algorithm and compared methods, using 80 clean training EF and PF examples, and noisy validation and test examples polluted by Gaussian noises with different SNRs of 4, 6, 8, 10 and 15. And we also report the classification results when validation and test examples are clean. As we can see, the performances of all the methods are significantly affected by varying SNR. Generally, the proposed R-SVM+ algorithm shows bigger superiority than all the compared methods especially when SNR is smaller. Since the distribution of noisy test data could be largely different from that of training data when SNR is small, the advantage of classical SVM+ over SVM is not preserved. When SNR is relatively large (i.e., SNR=15) or examples are clean, SVM+ and L2-SVM+ methods obviously outperform SVM and RSVM-RHHQ. While R-SVM+ achieves obviously better than SVM-based methods in all cases. This demonstrates the proposed R-SVM+ is a robust and effective SVM+-based algorithm against noises.

We also discuss the influences of different components of R-SVM+ on the classification results on the MNIST+ dataset, as an example. Figure 1 (a) shows the performances of RSVM+ if we separately consider minimizing ϵ (referred as RSVM+ without Ψ) and minimizing the value of Ψ(t, τx, τx∗ ) (referred as R-SVM+ without ϵ). We can find that in general the introduction of Ψ(t, τx, τx∗) obviously plays a more important role on the performance of R-SVM+ when SNR is small. While when SNR is relatively large, the introduction of ϵ will boost the accuracy to some extent. And R-SVM+ achieves the best performance by simultaneously considering both components in all cases.

In order to further evaluate the robustness of the proposed R-SVM+ algorithm compared with other SVM+-based methods when PF examples are noisy, we add Gaussian noises to the PF training examples with SNRs of 4, 6, 8, 10, and 15 on the MNIST+ dataset, as an example. As shown in Figure 1 (b), R-SVM+ obviously outperforms SVM+ and L2SVM+ with varying SNR in general. In detail, R-SVM+ obtains gains in accuracy of +3.1%, +3.9%, +3.6%, +2.6% and +1.2% over SVM+, and gains in accuracy of +4.1%, +4.4%, +3.0%, +3.5% and +2.0% over L2-SVM+ when SNR is equal to 4, 6, 8, 10, and 15, respectively. This is because R-SVM+ also considers maximizing the lower bound of potential perturbations over PF examples and has more tolerances over these noisy examples, thus strengthening the robustness of the R-SVM+ algorithm.

Table 2 shows the performance of different methods on the RGB-D Face dataset when Gaussian noises with an SNR of 8 are added in the validation and test examples. Generally, we can observe that SVM+ and L2-SVM+ methods are superior to the SVM-based methods in almost all the 6 cases due to the use of depth images as privileged information. In particular, the proposed R-SVM+ algorithm shows its advantage over SVM+ and L2-SVM+ in all the 6 cases, especially in the forth and fifth cases.

Table 3 reports the classification results of the proposed RSVM+ algorithm and compared methods on the Human Activity Recognition dataset whose validation and test examples are added with Gaussian noises with an SNR of 4. From the results shown in Table 3, we can see that R-SVM+ outperforms other methods in 5 out of 6 cases. In particular, RSVM+ obtains obviously better accuracies than SVM, SVM+ and L2-SVM+ in the "Sitting" and "Standing" cases. This demonstrates the effectiveness and robustness of R-SVM+ against noises. And RSVM-RHHQ also performs obviously better than SVM because of its robust strategy based on SVM. In general, SVM+-based methods get better results than SVM because of the use of privileged information.

5 Conclusion

In this paper, we propose a Robust SVM+ (R-SVM+) algorithm to construct a more robust classifier in the LUPI paradigm for the potential noises in the data. Based on a rigorous theoretical analysis, the lower bound of perturbations of noises that will mislead the model to make incorrect decisions has been evaluated. Accordingly, R-SVM+ can be learned by introducing a novel regularization function into a slack form of SVM+. The effectiveness of the proposed RSVM+ algorithm and the necessity of studying robust SVM+ methods in the LUPI paradigm are demonstrated by experiments on real-world datasets.

Acknowledgments

This work was supported by National Natural Science Foundation of China under grants U1536204, 61471274, and 61711530239, and Australian Research Council Projects: FL-170100117, DE-180101438, DP-180103424, and LP150100671.