Discrete Binary Coding based Label Distribution Learning

1 Introduction

Learning with label ambiguity has attracted considerable attention in recent years, because it lays the foundation for many important fields, including machine learning, computer vision and data mining. Single-label learning (SLL) and multi-label learning (MLL) are two prevailing learning paradigms for solving the problem of label ambiguity. However, SLL and MLL only can model the ambiguity of "what describes the instance", but fail to model the more general ambiguity of "how to describe the instance" [Xing et al., 2016]. To solve this problem, Geng (2016) proposed label distribution learning (LDL), which assumes that an instance is labeled by a label distribution over all labels. Each element of the label distribution is named the description degree. For example, dyx is the description degree of y to the instance x. Without loss of generality, LDL assumes that dyx ∈ [0, 1] and ∑y dyx = 1. Different from SLL and MLL, LDL aims at learning a group of projection functions from an instance to its label distribution.

∗Corresponding author.

Many LDL methods have already been proposed. Some representative works include IIS-LDL [Geng et al., 2013], conditional probability neural network (CPNN) [Geng et al., 2013], label distribution support vector regressor (LDSVR) [Geng and Hou, 2015], BFGS-LDL [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], deep label distribution learning (DLDL) [Gao et al., 2017], structural label distribution learning (SLDL)[Ren and Geng, 2017] and label distribution forests (LDLFs) [Shen et al., 2017]. However, the training time complexity of most methods is high. How to design a LDL algorithm to achieve good accuracy performance with low training time complexity is still a challenging problem.

To address the above-mentioned problem, Geng (2016) put forward a LDL approach named AA-kNN, which is an adaptation algorithm of k-Nearest Neighbor (k-NN). Although AA-kNN does not need a training process, its testing process (linear search) usually cost much time. Wang and Geng (2018) proposed a scalable LDL algorithm called BC-LDL, which uses the binary coding techniques to deal with the large-scale LDL problem. Compared with AA-kNN, the testing time cost of BC-LDL can be greatly reduced, because the similarity of two instances can be efficiently measured via XOR operations. However, BC-LDL suffers two drawbacks. Firstly, the discrete constraints are discarded to simplify the optimization, and the binary codes of training instances are approximately obtained by quantization. The errors caused by quantization may lead to low-quality binary codes. Secondly, BC-LDL adopts an iterative optimization strategy in the training phase, and the iteration number is equal to the code length. BC-LDL requires relatively long binary codes (i.e., over 64 bits) to achieve acceptable accuracy. Therefore, the training phase of BC-LDL is still time-consuming.

Recently, the discrete binary coding techniques have attracted increasing interest and many discrete optimization based hashing methods have been proposed. The desirable binary codes can be generated by these discrete methods, because the binary codes of training instances are directly learned without any quantization loss during the optimization procedure. Since supervised discrete hashing methods take the useful label information into consideration when learning binary codes and hash functions, they usually yield higher accuracy than unsupervised ones. Representative supervised discrete hashing methods include supervised discrete hashing (SDH) [Shen et al., 2015], column sampling based discrete supervised hashing (COSDISH) [Kang et al., 2016], asymmetric discrete graph hashing (ADGH) [Shi et al., 2017], fast supervised discrete hashing (FSDH) [Gui et al., 2018] , fast scalable supervised hashing (FSSH) [Luo et al., 2018a], scalable supervised discrete hashing (SSDH) [Luo et al., 2018b] etc. However, most of them may suffer some drawbacks when using the pair-wise similarity matrix (denoted as Sn×n ) in the training phase. For example, COSDISH and ADGH only use some points of S for training. FSSH and SSDH embed S into a small-size matrix in the pre-processing phase, but the complexity of this pre-processing phase is O(n2 ).

The motivations of this paper are three-fold: (1) addressing the issue of quantization loss in BC-LDL; (2) designing a linear discrete hashing algorithm with all the points of S utilized for instances labeled by a label distribution; (3) proposing an efficient LDL approach based on this discrete algorithm.

In this paper, we take an initial attempt to apply the discrete hashing techniques to large-scale LDL and further present a scalable LDL method, named Discrete Binary Coding based Label Distribution Learning (DBC-LDL). Different from the previous discrete hashing methods, the binary coding part of DBC-LDL is specially designed for instances labeled by a label distribution. The main contributions of this work are briefly summarized as follows:

• A novel supervised discrete binary coding method is proposed for instances annotated by a label distribution. In our algorithm, we consider both the pair-wise similarities of different training instances and the original label distributions, leading to high-quality binary codes. Moreover, the similarity matrix S is avoided directly utilizing during the optimization procedure. The time and storage cost of our method can be reduced significantly.
• An iterative optimization strategy is proposed to learn the binary codes for training instances and the binary coding functions. The global non-convex optimization problem can be decomposed into several tractable subproblems, and each variable has a closed-form solution.
• Integrating discrete binary coding and ANN search into a joint framework, a scalable LDL approach is proposed to deal with the large-scale LDL. Compared with BCLDL, the desirable binary codes of training instances can be directly learned in the training phase, thus the quantization errors are avoided in DBC-LDL.
• Extensive experiments are conducted on five benchmark datasets to evaluate the proposed DBC-LDL. Experimental results verify the effectiveness of our approach.

The remainder of this paper is organized as follows. In Section 2, the details of the DBC-LDL algorithm are presented. In Section 3, we report the experimental results on five public datasets, followed by the conclusion in Section 4.

2 The ProposedMethod

2.1 Notations and ProblemDefinition

Suppose that X = [x1, x2, · · · , xn] ∈ Rm×n is the feature space, and Y = {y1, y2, · · · , yc} is the complete set of labels. c denotes the number of the labels. Here, we use dyx to represent the description degree of the label y ∈ Y to the instance x ∈ X. Z = {(x1, d1), (x2, d2, ), · · · , (xn, dn)} denotes the training set, where xi ∈ Rm×1 is a training instance, and di = [dy1 xi ; dy2 xi ; · · · ; dyc xi ] is the corresponding label distribution of xi. n is the number of training instances. Without loss of generality, we consider that the instances are zerocentered, i.e., ∑ni=1 xi = 0. Table 1 shows the important notations used in this paper.

In this paper, the target of DBC-LDL is to learn the binary codes for training instances and binary coding functions for future instances. Then, the same ANN search strategy as that in [Wang and Geng, 2018] is adopted to generate label distributions for future instances. The binary coding function h(x) is defined as follows:

where P ∈ Rl×m is the projection matrix, and e ∈ Rl×1 is the bias vector. Here, l represents the length of binary codes.

2.2 Pair-wise SimilarityMatrix

For most existing supervised discrete hashing approaches [Kang et al., 2016; Shi et al., 2017; Li et al., 2017; Luo et al., 2018a; 2018b; Jiang et al., 2018], the semantic similarity of two instances can be obtained via modeling the label consistency between them. However, it is not appropriate to apply this idea to LDL, because an instance is labeled by a distribution consisting of some real numbers in LDL, rather than annotated by a binary label vector.

In this paper, we employ the adjusted cosine similarity (ACS) metric [Sarwar et al., 2001; Wang and Geng, 2018] to build the similarity matrix S ∈ [-1, 1]n×n . Suppose there are two instances xi and xj from the training set, the similarity between them is defined as follows:

where "·" represents the inner product between two vectors, || · ||2 represents the L2 norm of a vector, ϵ is the mean of all the label distributions, andDi∗ = di-ϵ ||di-ϵ||2 .

Thus, the pair-wise similarity matrix can be explicitly calculated by S = DT D. We can find that the complexity of both storage and computational time to construct this similarity matrix is O(n2 ). Fortunately, the high storage and time cost can be avoided in DBC-LDL, because the similarity matrix will not be directly used in the optimization phase.

2.3 Graph Term

Graph based supervised hashing methods aim at transforming the high-dimensional original features into compact binary codes with semantic similarities between different instances best maintained. Similar to some existing graph based hashing algorithms [Weiss et al., 2009; Liu et al., 2011; 2014], the graph term is defined as follows:

where B ∈ {-1, 1}l×n is the binary code matrix.

Actually, the element of the similarity matrix S is a constant, and bTi bi = l(∀i). Eq. (3) can be rewritten as follows:

where tr(·) denotes the trace operator.

The above graph term is defined on the directly learned binary codes B. However, the binary codes of testing instances are generated by using binary coding functions (i.e., quantization). For training instances, we expect B and the binary codes generated by quantization are as similar as possible. This is because it can help testing instances to reduce the latent quantization loss. Thus, we put the constraints of semantic similarity preserving on B and (PX + E), and further reformulate the graph term by adding a new constraint as:

(5) where E = [e, e, · · · , e] ∈ Rl×n , X = [X; 1n] and P = [P , e]. α is a tradeoff parameter.

2.4 Label Distribution Embedding Term

To further improve the quality of the learned binary codes, the original label distributions are taken into consideration when constructing the objective function. By assuming an explicit projection from label distributions to binary codes, we can define the following optimization problem:

where D ∈ Rc×n is the label distributions matrix, and W ∈ Rl×c is the corresponding mapping matrix.

2.5 Overall Objective Function

The overall objective function, consisting of the graph term in (5), the label distribution embedding term in (6) and an additional regularization term, is written as follows:

where the regularization termR(·) = || · ||2F is introduced to resist overfitting. α, β, γ are balance parameters.

2.6 Optimization

The optimization problem stated in (7) is hard to be directly solved due to its non-convexity with three matrix variables B, P , W. In this paper, we use an iterative strategy to solve this optimization problem, and each variable can obtain a closedform solution according to this strategy. The detailed optimization procedure is presented below.

Step 1: Fix B, W, let ∂Θ ∂P = 0, then obtain:

where Im is a m × m identity matrix.

Step 2: Fix B, P, let ∂Θ ∂W = 0, then obtain:

Step 3: Fix P , W, then obtain the following problem: min

It is easy to see that tr(BBT ), tr((P X)(P X)T ) and tr((WD)(WD)T ) are constants in (10). Thus, the above optimization problem can be reformulated as follows:

Finally, a closed-form solution of B can be obtained:

It can be seen that the time complexity of XS in Eq. (8) and (12) is O(mn2 ). However, XS = (XDT )D, and the time complexity of the latter is only O(cmn). By doing so, all the pair-wise similarities can be utilized, and the consumption of storage and time can be reduced remarkably in our algorithm. The whole optimization algorithm is summarized in Algorithm 1. T is set to 10 in this paper.

2.7 Label Distribution Generation

Inspired by BC-LDL [Wang and Geng, 2018], the proposed DBC-LDL employs the same strategy to generate a label distribution for a future instance. Specifically, the binary codes of a future instance can be generated via the binary coding function in Eq. (1). Then, we use the ANN search strategy to find k nearest training instances in the Hamming space. Benefit from the fast XOR operations, this search procedure is quite efficient. Finally, the mean of the label distributions of these training instances is computed as the predicted label distribution for this future instance.

Algorithm 1 DBC-LDL

• 1: Input: Feature matrix X; label distributions matrix D; Adjusted label distributions matrix D; Code length l.
• 2: Output: Projection matrix P; Bias vector e; Binary codes matrix B.
• 3: X ← [X; 1n].
• 4: Initialize B, P, W by randomization.
• 5: repeat
• 6: Fix B, W, update P by Eq. (8);
• 7: Fix B, P, updateW by Eq. (9);
• 8: Fix P, W, update B by Eq. (12);
• 9: until convergence or reaching the maxiter T
• 10: P ←P(:, 1 : end-1); e ←P(:, end).

2.8 Complexity Analysis

In this subsection, we discuss the time complexity of DBCLDL. DBC-LDL adopts an iterative optimization strategy to learn variables, where each iteration contains three main steps. The time cost of updating P , W , and B is O(cmn+lmn+ nm2 + m3 ), O(cln + nc2 + lc2 + c3 ), and O(cmn + lmn + cln), respectively. Therefore, the whole time complexity is O((cmn + lmn + nm2 + m3 + cln + nc2 + lc2 + c3 )t), where t is the number of iterations. Since c,m ≪ n, the training time complexity of DBC-LDL is linear to n.

3 Experiment

We conduct our experiments on five real-world datasets, namely M 2 B (Multi-Modality Beauty) [Nguyen et al., 2012], s-BU 3DFE (scores-Binghamton University 3D Facial Expression) [Zhou et al., 2015], Twitter LDL [Yang et al., 2017], Flickr LDL [Yang et al., 2017], and Ren-CECps [Quan and Ren, 2010], to evaluate our algorithm in terms of both accuracy and efficiency.

M 2 B and s-BU 3DFE are two regular-scale image datasets. The application task of the former is the facial beauty sense and the task of the latter is the facial expression recognition. Twitter LDL and Flickr LDL are two large-scale image datasets. The application task of them is the visual sentiment distributions prediction. Ren-CECps is a large-scale text dataset, and its application task is the text emotion distributions prediction. Due to the page limitation, here we only show statistics of the five real-world datasets in Table 2.

All the experiments are implemented using Matlab on a standard PC with a 2.30GHz Intel CPU and 12GB memory.

3.1 Baselines Evaluation and Protocols

In this paper, the baselines contain one adaptation algorithm AA-kNN, and five representative specialized LDL algorithms, i.e., IIS-LDL, BFGS-LDL, CPNN, LDSVR and BC-LDL. For the proposed DBC-LDL, we empirically set the parameter α = 104 , β = 104 and γ = 10-2 . The code length in DBC-LDL and BC-LDL is same (i.e., 128 bits) for making a fair comparison, and k in DBC-LDL, BC-LDL and AA-kNN is chosen from {10, 20, · · · , 50}. For the other baselines, we set the corresponding parameters by following the authors' suggestions. All the results are averaged over 10-fold cross validation in terms of both accuracy and time cost.

According to the suggestion in [Geng, 2016], six prevailing metrics are adopted to evaluate the accuracy performance of different algorithms, including Chebyshev distance (Cheb), Clark distance (Clark), Canberra metric (Canber), KullbackLeibler divergence (K-L), cosine coefficient (Cosine) and intersection similarity (Intersec). Since the first four are used to measure the distance between two distributions, they are the smaller the better. The last two are similarity metrics, so they are the larger the better.

3.2 Experimental Results

The detailed experimental results of the proposed DBC-LDL and other comparing algorithms on the five evaluated datasets are reported in Table 3. To show the accuracy, efficiency and comprehensive performance of these approaches, three rank measurements are introduced, including Accuracy Rank (Acc. Rank), Time Rank and Average Rank (Avg. Rank). Moreover, the ranks of six evaluation metric values are presented in the parentheses right after the corresponding measure values. The average value of these six ranks is denoted as Acc. Rank. In addition, Avg. Rank is the average value between Acc. Rank and Time Rank, which can effectively reflect the comprehensive performance of an algorithm.

From Table 3, it can be seen that DBC-LDL achieves the best accuracy performance on four datasets, and achieves the second best performance on other datasets. Moreover, DBCLDL can yield the best efficiency performance and comprehensive performance on all the evaluated datasets. Note that the results of LDSVR on Ren-CECps are not reported due to the high memory consumption. Overall, we have the following five observations based on the experimental results:

• On the five evaluated datasets, DBC-LDL ranks 1st in 63.3% cases and ranks 2st in 13.3% cases across all the distance and similarity metrics, which can demonstrate its superiority.
• Compared with BC-LDL, DBC-LDL can yield the better accuracy performance on four datasets (i.e., M 2 B, sBU 3DFE, Twitter LDL and Flickr LDL) and the same accuracy performance on Ren-CECps. The better performance of DBC-LDL can be attributed to its ability to learn good binary codes for training instances by a discrete optimization strategy without quantization loss.
• AA-kNN achieves the desirable accuracy performance on Twitter LDL and Flickr LDL, which is also observed in [Wang and Geng, 2018]. This is because that the highquality features of these datasets are extracted via VGGNet [Simonyan and Zisserman, 2014]. AA-kNN can

obtain the accurate search results by using these highquality features.

• Compared with IIS-LDL, BFGS-LDL can achieve higher accuracy results with the lower training time cost on most datasets. The training time of LDSVR growing rapidly with the size of datasets increasing, because its time complexity is O(n2 ).
• Benefit from the efficient optimization strategy and the fast binary code based ANN search approach, the total time cost of DBC-LDL is lowest on all the evaluated datasets, which verifies the efficiency of our method.

3.3 Parameter Analysis

There are three parameters in our objective function, including α, β and γ. Due to the limitation of space, we only report the Cheb and Intersec results and use them to study the performance variation with respect to the different parameter values of α, β and γ. The results of other metrics are similar. The experiments are conducted by varying the value of one parameter while fixing the other two to the settings mentioned in Subsection 3.1. Here, we vary α in the range of {10-2 , 10-1 , · · · , 105 }, β in the range of {0, 1, · · · , 106 } and γ in the range of {10-4 , 10-3 , · · · , 103 }. Figure 1 shows the results on the testing dataset (i.e., s-BU 3DFE). We can find that our method can achieve satisfactory results, when α ∈ [103 , 104 ], β ∈ [104 , 105 ] and γ ∈ [10-2 , 10-1 ].

3.4 Convergency Analysis

In this part, we evaluate the convergence of the proposed DBC-LDL. Figure 2 plots the convergence curve of the objective function during training on Ren-CECps. It can be observed that our method can successfully converge within 10 iterations and the value of the objective function decrease slowly after 4 iterations. The time consumption for optimization of DBC-LDL is not expensive, because it can converge quite fast.

3.5 Binary Code Length Analysis

In this subsection, we study the accuracy performance of our method regarding different code lengths. Table 4 summarizes the evaluation results on s-BU 3DFE and Ren-CECps. We can learn that DBC-LDL achieves better accuracy performance with longer binary codes. It means that more useful information can be preserved by DBC-LDL when learning longer binary codes.

4 Conclusion

In this paper, we have presented a novel LDL method (DBCLDL) to tackle the task of large-scale LDL. In DBC-LDL, the pair-wise semantic similarities and original label distributions are taken into consideration for learning precise binary codes. Moreover, an efficiently discrete optimization strategy is proposed to learn binary codes directly for training instances. In addition, a binary code based ANN search method is employed to predict label distributions for testing instances. Experimental results on five benchmark LDL datasets show that DBC-LDL outperforms several state-of-the-art LDL approaches. The binary coding part of DBC-LDL is an one-step method. In future work, we plan to develop a two-step discrete method to solve the large-scale LDL problem.

Acknowledgments

This research was supported by the National Key Research & Development Plan of China (No. 2017YFB1002801), the National Science Foundation of China (61622203), the Collaborative Innovation Center of Novel Software Technology and Industrialization, and the Collaborative Innovation Center of Wireless Communications Technology.