Binary Coding based Label Distribution Learning

1 Introduction

Learning with ambiguity plays a fundamental role in many areas including machine learning, computer vision, data mining and so on. Although different varieties of learning paradigms have been proposed for learning with ambiguity, label distribution learning (LDL) has become one of the latest approaches to this goal because it can perform better than other paradigms in some real applications [Geng et al., 2013; Zhou et al., 2016; Xing et al., 2016; Yang et al., 2016; Gao et al., 2017]. Generally speaking, LDL assumes that an instance x is labeled by a real number dyx to every possible label y, representing the degree to which the corresponding y describes x. Thus, dyx is named the description degree of y to the instance x. The vector consisting of the description degrees of all the labels is called label distribution because it is similar to probability distribution. Label distribution can not only model the ambiguity of "what describes the instance", but also deal with the more general ambiguity of "how to describe the instance" [Xing et al., 2016]. Without loss of generality, LDL assumes that dyx ∈ [0, 1] and ∑y dyx = 1. Different from other learning paradigms, single-label learning (SLL) and multi-label learning (MLL) for example, the main purpose of LDL is to learn a group of mapping functions from the instance to its label distribution.

∗Corresponding author.

In recent years, a collection of LDL algorithms have been proposed. The representative methods include IISLDL [Geng et al., 2013], conditional probability neural network (CPNN) [Geng et al., 2013], label distribution support vector regressor (LDSVR) [Geng and Hou, 2015], BFGSLDL [Geng, 2016], PT-Bayes [Geng, 2016], PT-SVM [Geng, 2016], AA-BP [Geng, 2016], LDLogitBoost [Xing et al., 2016], AOSO-LDLogitBoost [Xing et al., 2016], sparsity conditional energy label distribution learning (SCE-LDL) [Yang et al., 2016], deep label distribution learning (DLDL) [Gao et al., 2017] and so on. However, most of them suffer from one key limitation: as the size of training set increases, the training time grows rapidly.

To avoid the high training time consumption, Geng (2016) proposed a method known as AA-kNN, which is an adaptation algorithm of k-Nearest Neighbor (k-NN) to solve the LDL problem. Compared with other LDL algorithms, the advantage of AA-kNN is that it does not need a training process. However, AA-kNN suffers from two drawbacks. Firstly, its performance heavily depends on the quality of the original features it uses, which are usually extracted in an unsupervised way. Thus, when the high quality features cannot be obtained, it may lead to poor performance. Secondly, when the size of dataset is large and the dimension of real-valued feature is high, the testing phase (linear search) will cost a great deal of time. Therefore, like most of other LDL methods, AA-kNN is not applicable to large-scale LDL.

To address the above-mentioned problems, we employ the binary coding/hashing techniques to tackle the task of largescale LDL, which is widely used for approximate nearest neighbor (ANN) search [Indyk and Motwani, 1998]. The purpose of hashing is to transform high-dimensional original features into compact binary codes. Since the representations of instances are compressed as short binary codes, the time and memory cost of searching process can be significantly reduced.

Existing hashing methods can be roughly categorized into two groups, i.e., unsupervised hashing and supervised (including semi-supervised) hashing. As label information is useful for generating more discriminative hash codes, supervised hashing methods can often achieve better performance. Existing representative supervised hashing algorithms include sequential projection learning for hashing (SPLH) [Wang et al., 2010], supervised hashing with kernels (KSH) [Liu et al., 2012], two-step hashing (TSH) [Lin et al., 2013], FastHash [Lin et al., 2014], supervised discrete hashing (SDH) [Shen et al., 2015], column sampling based discrete supervised hashing (COSDISH) [Kang et al., 2016], supervised quantization (SQ) [Wang et al., 2016]. However, most existing supervised hashing methods are developed for the instances labeled by a logic label or some logic labels. They cannot directly integrate the label distribution information into the binary coding procedure. Thus, it is not much appropriate to extend most existing supervised hashing methods to deal with LDL problem.

It is worth noting that Jiang and Li (2015) put forward the scalable graph hashing (SGH) method, which exploits a feature transformation technique to approximate the whole graph. The time complexity of SGH is O(n), because the pairwise similarity graph matrix is avoided explicitly computing. Although the performance of SGH is promising, the binary codes are learned in an unsupervised manner and the supervised information is not fully considered.

Inspired by AA-kNN and SGH, a scalable LDL framework, termed Binary Coding based Label Distribution Learning (BC-LDL), is put forward to solve the large-scale LDL problem. The main contributions of this paper are briefly listed as follows:

• We propose a novel supervised binary coding method for the instances labeled by the label distributions. Because we consider the correlations between the instances based on their semantic label distributions, highly discriminative binary codes can be generated by the proposed method.
• Combining binary coding and ANN search together, we further propose a scalable LDL framework for efficiently solving the large-scale LDL problem. Compared with other NN-based LDL methods (e.g., AA-kNN), the time cost of the testing phase can be greatly reduced, because the similarity of two instances can be rapidly measured by calculating the Hamming distance between two groups of binary codes via XOR operations.
• Experimental results on five real-world datasets demonstrate that the proposed BC-LDL is competitive with the state-of-the-art LDL methods.

The rest of this paper is organized as follows. Firstly, the details of the proposed BC-LDL method are presented. Secondly, the experimental results on five public datasets are reported. Finally, the conclusion is given.

2 BC-LDL

2.1 ProblemFormulation

Let X = [x1; x2; · · · ; xn] ∈ Rn×m denote the input space, Y = {y1, y2, · · · , yc} denote the complete set of labels, and dyx denote the description degree of the label y ∈ Y to the instance x ∈ X. c is the number of the labels. dyx needs to satisfy two constrains, i.e., dyx ∈ [0, 1] and ∑y dyx = 1. Without loss of generality, let X be normalized to have zero mean. Suppose that we have a training set Z = {(x1, d1), (x2, d2, ), · · · , (xn, dn)}, where n is the number of instances, xi ∈ R1×m, and di = [dy1 xi , dy2 xi , · · · , dyc xi ] is the corresponding label distribution of the instance xi.

Different from most existing LDL methods, BC-LDL does not learn a group of mapping functions from x ∈ R1×m to d ∈ R1×c directly. BC-LDL aims at learning a group of binary coding functions based on the training set Z, i.e., h(x): R1×m -→ {-1, 1}1×l , where l is the length of binary codes. Then, the ANN search strategy is employed to generate the label distributions for the testing instances. In this paper, h(x) is defined as follows:

where sign(·) denotes the element-wise sign function, which returns 1 if the element is a positive number and returns -1 otherwise. W ∈ Rm×l is the mapping matrix, and e ∈ R1×l is the bias vector.

2.2 Binary Coding

Similar to some existing supervised hashing methods [Liu et al., 2012; Zhang and Li, 2014; Lin et al., 2014; Kang et al., 2016], we expect to approximate the similarity matrix S by the generated binary codes of training instances. Thus, we have the following objective function:

where B is the binary code matrix, and || · ||F denotes the Frobenius norm.

The analytical form of the objective function is:

2.3 SimilarityMatrix Construction

As aforementioned, each instance is labeled by a distribution over all labels in LDL, rather than labeled by a logic label or some logic labels. Thus, we cannot construct the similarity matrix by modeling the label consistency between instances, which is used in many supervised hashing algorithms [Wang et al., 2010; Liu et al., 2012; Lin et al., 2013; Zhu and Gao, 2017]. Furthermore, we think a real number within the range of -1 and 1 is more appropriate to represent the similarity between two instances than a logic number (i.e., -1 or 1) in LDL, because the former is more discriminative.

Based on the above considerations, we adopt the adjusted cosine similarity (ACS) metric [Sarwar et al., 2001] to construct the similarity matrix S ∈ [-1, 1]n×n . Given an instance pair (xi, xj) from the training set, the semantic affinity of this instance pair is defined as follows:

where "·" denotes the inner product of two vectors, || · ||2 denotes the L2 norm of the vector, µ is the mean of the label distributions of all the training instances, andDi∗ = di-µ ||di-µ||2 .

Then we can obtain the similarity matrix S = DDT . In fact, if we construct the similarity matrix directly, it will lead to the high time complexity and memory requirement. Therefore, we need to avoid the construction of similarity matrix S in our algorithm. In the following subsection, we will describe how to achieve it in detail.

2.4 Optimization

There is a matrix variable W and a vector variable e in our original objective function. Actually, if we denote X = [X, 1n] and W = [W; e], we can omit e and obtain the following form with only a matrix variable W :

The objective function in (5) is hard to be solved directly due to the existence of sign function. A common solution is to adopt the spectral relaxation trick [Weiss et al., 2009] and impose orthogonality constraints, i.e., W T XT XW = In. Here, In denotes a n × n identity matrix. Then, the optimization problem can be easily transferred into a generalized eigenvalue problem. However, it has been verified that non-orthogonal mapping functions can perform better than orthogonal ones in some real applications [Wang et al., 2010; Zhang and Li, 2014]. Thus, we apply a sequential learning strategy to learn the binary coding functions without imposing orthogonality constraints [Liu et al., 2012; Zhang and Li, 2014; Jiang and Li, 2015].

Suppose that we have learned the mapping functions w1,w2, · · · ,wt-1, we need to learn the next mapping function wt. We define a residual matrix Rt as follows:

Following the objective function in (5), the corresponding optimization problem to learn wt can be defined as:

The main idea of this sequential learning strategy is to reconstruct the similarity matrix by the learned binary codes and learn a new mapping function to correct the errors made by the previous ones [Wang et al., 2012; Zhang and Li, 2014].

By some algebraic calculation, we further rewrite the objective function in (7) as:

where At = sign(Xwt), and tr(·) denotes the trace operator.

Thus, the objective function in (7) can be reformulated as:

The objective function in (9) is still hard to be solved directly due to the existence of sign function. Here we use a widely-adopted approximate representation of sign function [Wang et al., 2010; 2012], i.e., sign(a) ≈ a, to handle it. We rewrite it as follows:max

where the orthogonality constraint is set to avoid the trivial solution.

It is easy to see that the optimization problem in (10) is an eigensystem problem and the eigenvector of XT RtX corresponding to its largest eigenvalue (λmax) is the approximate solution wt:

We define Gt = XT RtX, then we can obtain:

where Ai = sign(Xwi). According to the equation (12), we can find that the construction of similarity matrix S is avoided during the optimization procedure. It considerably boosts the scalability of our algorithm.

2.5 Label Distribution Generation

Our BC-LDL adopts a two-step strategy to learn the label distributions for the testing instances. In the first step, BC-LDL generates the binary codes for a new testing instance ˜x according to the equation (1): ˜b = sign(˜xW + e). In the second step, ANN search is conducted to find the k nearest training instances represented by binary codes in the Hamming space. Then, the mean of the label distributions of all the searched training instances is calculated as the learned label distribution.

Algorithm 1 BC-LDL: Train Algorithm

• 1: Input: Feature matrix X; Adjusted label distributions matrix D; Code length l.
• 2: Output: Projection matrixW; Bias vector e.
• 3: X ← [X, 1n].
• 4: G0 ← (XT D)(XT D)T .
• 5: G1 ← lG0.
• 6: for t = 1, · · · , l do
• 7: Solve the following eigensystem problem Gtwt = λmaxwt;
• 8: Obtain the mapping vector wt corresponding to the largest eigenvalue λmax;
• 9: Z ← [XT sign(Xwt)][XT sign(Xwt)]T ;
• 10: Gt+1 ←Gt -Z;
• 11: end for
• 12: W ← [w1,w2, · · · ,wl].
• 13: W ←W(1 : end-1, :); e ←W(end, :).

Algorithm 2 BC-LDL: Test Algorithm

• 1: Input: Test instance ˜x; No. of nearest neighbors k.
• 2: Output: Label distribution ˜ d.
• 3: ˜b ← sign(˜xW +e).
• 4: Nk ← the k nearest neighbors of ˜b in the Hamming space.
• 5: ˜ d ← the mean of the label distributions of the instances ∈ Nk.

2.6 Summary and Analysis

We summarize the proposed BC-LDL method in Algorithm 1 and Algorithm 2.

In the training phase, the time complexity of BC-LDL includes two aspects, i.e., the initialization procedure and the sequential learning procedure. Firstly, initialization of G0 will cost O(cn(m+1)+c(m+1)2 ). Secondly, the time cost of the sequential learning procedure is O(l((m+1)3 +(m+ 1)n + (m+ 1)2 )). The training time complexity of BC-LDL is linear to n, because c, l,m is usually much less than n.

In the testing phase, the time cost of generating the binary codes for a testing instance is O(lm) and searching the k nearest training instances is O(kn). Hence, the testing time complexity is O(lm+ kn) in total.

We can see that when the size of training set is large, the testing phase will cost much time. An effective solution for this problem is that we can construct a hash table to store the mean of the label distributions of these training instances with the same binary codes. Then, the mean is used as the predicted label distribution for a testing instance that have the same binary codes. The time cost of constructing a hash table is O(2ln) and predicting the label distribution for a testing instance will cost O(lm+ l2l ). We set l = 8 in this paper, and thus 2l ≪ n. Altogether, the training time complexity is still O(n). This method is named as BCTable.

3 Experiment

In this section, we evaluate the proposed algorithms on five different datasets: s-BU 3DFE (scores-Binghamton University 3D Facial Expression) [Zhou et al., 2015], COPM (Crowd Opinion Prediction on Movies) [Geng and Hou, 2015], Twitter LDL [Yang et al., 2017], Ren-CECps [Quan and Ren,

2010] and MORPH [Ricanek and Tesafaye, 2006]. Due to the space limitation, here we only present the brief statistics of these evaluated datasets in Table 1. All the experiments are carried on a PC with Intel (R) Core (TM) CPU i5-6300@2.30GHz and 12GB RAM.

3.1 Experimental Settings

To validate the proposed methods, we comprehensively compare them with several baselines. These algorithms include four specialized algorithms IIS-LDL, BFGS-LDL, CPNN, LDSVR, and one adaptation algorithm AA-kNN.

As suggested in [Geng, 2016], six measures are employed to evaluate the accuracy performance of all the methods. Among them, Chebyshev, Clark, Canberra, Kullback-Leibler (K-L), measure the distance between two distributions, thus they are the smaller the better. Cosine and Intersection are used to measure the similarity between two distributions, so they are the larger the better.

The parameters of all the methods used in the experiments are carefully tuned and the best results of baseline methods are reported. On s-BU 3DFE, k in BC-LDL is set to 20 and code length is set to 32 bits. The maximum iteration steps in BFGS-LDL is 300 and IIS-LDL is 100. k for AA-kNN is set to 20. On COPM, k in BC-LDL is 30 and code length is 128 bits. The maximum iteration steps in BFGS-LDL is 100 and IIS-LDL is 20. k in AA-kNN is 10. On Twitter LDL, k in BC-LDL is set to 10 and code length is 256 bits. The maximum iteration steps in BFGS-LDL is 300 and IIS-LDL is 50. k in AA-kNN is 10. On Ren-CECps, k in BC-LDL is 20 and code length is set to 64 bits. The maximum iteration steps in BFGS-LDL is 200 and IIS-LDL is 100. k in AAkNN is set to 20. On MORPH, k in BC-LDL is set to 50 and code length is 256 bits. The maximum iteration steps in BFGS-LDL is 100 and IIS-LDL is 20. k in AA-kNN is set to 10. On the five datasets, the insensitivity parameter ε of LDSVR is set to 0.1 and the number of hidden-layer neurons of CPNN is set to 50.

All the results are averaged over 10-fold cross validation in terms of both accuracy and time cost.

3.2 Experimental Results

Table 2-6 report the results of our methods and other baselines on the five evaluated datasets. When we evaluate the performance of a LDL algorithm, its accuracy performance and efficiency performance are equally important. Hence, three different rank metrics are adopted to evaluate the performance of all the algorithms in our experiments, i.e., Accuracy Rank (Acc. Rank), Time Rank and Average Rank (Avg. Rank), which can reflect the accuracy, efficiency and comprehensive performance of these algorithms, respectively. 1 Furthermore, the ranks of six measure values are also given in the parentheses right after the corresponding measure values, and the average value of these six ranks is denoted as Acc. Rank. Note that Avg. Rank of an algorithm is the average value between its Acc. Rank and Time Rank.

1 We don't report the experimental results of LDSVR because it would cause out of memory issue

From Table 2-6, we can find that BC-LDL achieves the best accuracy performance on two datasets (i.e., s-BU 3DFE and Ren-CECps), and achieves the second best performance on other datasets. Compared with other baselines, BC-LDL and BCTable can achieve better efficiency performance on the five evaluated datasets. Moreover, BC-LDL achieves the best comprehensive performance on the five datasets. The comprehensive performance of BC-LDL on the five evaluated datasets demonstrates its effectiveness and efficiency.

The experimental results on s-BU 3DFE are reported in Table 2. We can see that our BC-LDL method outperforms other baseline methods, which demonstrates its superiority. Table 3 reports the experimental results on COPM. Here, we have a different observation: LDSVR achieves the better accuracy performance than BC-LDL. A reasonable explanation is that the application of the kernel trick makes LDSVR solve the LDL problem with the high-dimension features more effectively. Table 4 reports the experimental results on TwitterLDL. We can find that AA-kNN achieves the best accuracy performance. The desirable results of AA-kNN can be attributed to the high-quality original features, which are extracted by VGGNet [Simonyan and Zisserman, 2014]. Table 5 reports the experimental results on Ren-CECps. Once again, BC-LDL yields better experimental results than other baseline algorithms. Furthermore, it is worth noting that the total time consumption of BCTable is least and its results are comparable to most LDL methods. The experimental results on MORPH are reported in Table 6. Although AA-kNN achieves the better accuracy performance, its time consumption of testing phase is much more than that of our methods.

To further demonstrate the efficiency of our algorithms, we also report the time ratio of the fastest compared method to our methods. The results are reported in Table 7. We can find that our algorithms are much faster than other baseline algorithms, especially on the large-scale datasets (i.e., RenCECps and MORPH).

3.3 Analysis on Binary Code Length

In this part, we study the evaluation results variation with respect to different code lengths on the five evaluated datasets. The code length is set to {16, 32, · · · , 256} in actual experiments. Due to the space limitation, we only present the K-L and Intersection results. The results of other measures are similar. The evaluation results are reported in Figure 1-2. We have two observations. Firstly, longer binary codes can lead to better results on the medium-scale dataset (i.e., Twitter LDL) and the large-scale datasets (i.e., Ren-CECps and MORPH). However, when the code length exceeds 128 bits, the performance of BC-LDL tends to converge. It proves that BC-LDL can achieve acceptable results with reasonably short binary codes, that is crucial in large-scale LDL. Secondly, as the code length increases, the performance improvement on s-BU 3DFE and COPM is not significant. When the code length exceeds 64 bits, the performance of BC-LDL

even degrades to some extent. A possible reason for this phenomenon is that the size of these two datasets is small, and thus they cannot provide more useful information for longer binary codes.

4 Conclusion

In this paper, we have proposed a scalable LDL algorithm called BC-LDL, for dealing with the large-scale LDL problem. In BC-LDL, the label distribution information is integrated into the binary coding procedure for generating highquality binary codes. Moreover, ANN search is conducted to find the training instances that have binary codes with a small Hamming distance from a testing instance, which can be efficiently computed via XOR operations. Then, the mean of the label distributions of all the neighboring instances is calculated as the predicted label distribution. Experimental results on five real-world datasets have demonstrated that BC-LDL is competitive with several state-of-the-art LDL methods.

Acknowledgments

This research was supported by the National Key Research & Development Plan of China (No. 2017YFB1002801), the National Science Foundation of China (61622203), the Jiangsu Natural Science Funds for Distinguished Young Scholar

(BK20140022), the Collaborative Innovation Center of Novel Software Technology and Industrialization, and the Collaborative Innovation Center of Wireless Communications Technology.