Many could be better than all: A novel instance-oriented algorithm for Multi-modal Multi-label problem
Yi Zhang Cheng Zeng Hao Cheng Chongjun Wang Lei Zhang
cs.LG cs.MM stat.ML




𝐱
ŁL








Yi Zhang,  Cheng Zeng,  Hao Cheng, Chongjun Wang,  Lei Zhang^*^*Corresponding author
National Key Laboratory for Novel Software Technology at Nanjing University 


Nanjing University, Nanjing 210023, China 

{mg1733091, njuzengc, chengh}@smail.nju.edu.cn, {chjwang, zhangl}@nju.edu.cn

Many could be better than all: A novel instance-oriented algorithm for Multi-modal Multi-label problem
    [
    today
======================================================================================================






With the emergence of diverse data collection techniques, objects in real applications can be represented as multi-modal features. What's more, objects may have multiple semantic meanings. Multi-modal and Multi-label <cit.> (MMML) problem becomes a universal phenomenon. The quality of data collected from different channels are inconsistent and some of them may not benefit for prediction. In real life, not all the modalities are needed for prediction. As a result, we propose a novel instance-oriented Multi-modal Classifier Chains (MCC) algorithm for MMML problem, which can make convince prediction with partial modalities. MCC extracts different modalities for different instances in the testing phase. Extensive experiments are performed on one real-world herbs dataset and two public datasets to validate our proposed algorithm, which reveals that it may be better to extract many instead of all of the modalities at hand. 



multi-modal, multi-label, extraction cost




§ INTRODUCTION



In many natural scenarios, objects might be complicated with multi-modal features and have multiple semantic meanings simultaneously. 

For one thing, data is collected from diverse channels and exhibits heterogeneous properties: each of these domains present different views of the same object, where each modality can have its own individual representation space and semantic meanings. Such forms of data are known as multi-modal data. In a multi-modal setting, different modalities are with various extraction cost. Previous researches, i.e., dimensionality reduction methods, generally assume that all the multi-modal features of test instances have been already extracted without considering the extraction cost. While in practical applications, there is no aforehand multi-modal features prepared, modality extraction need to be performed in the testing phase at first. While for the complex multi-modal data collection nowadays, the heavy computation burden of feature extraction for different modalities has become the dominant factor that hurts the efficiency.

For another, real-world objects might have multiple semantic meanings. To account for the multiple semantic meanings that one real-world object might have, one direct solution is to assign a set of proper labels to the object to explicitly express its semantics. In multi-label learning, each object is associated with a set of labels instead of a single label. Previous researches, i.e., classifier chains algorithm is a high-order approach considering the relationship among labels, but it is affected by the ordering specified by predicted labels. 

To address all the above challenges, this paper introduces a novel algorithm called Multi-modal Classifier Chains (MCC) inspired by Long Short-Term Memory (LSTM) <cit.><cit.>. Information of previous selected modalities can be considered as storing in memory cell. The deep-learning framework simultaneously generates next modality of features and conducts the classification according to the input raw signals in a data-driven way, which could avoid some biases from feature engineering and reduce the mismatch between feature extraction and classifier. 
The main contributions are:
 

  * We propose a novel MCC algorithm considering not only interrelation among different modalities, but also relationship among different labels.

  * MCC algorithm utilizes multi-modal information under budget, which shows that MCC can make a convince prediction with less average modality extraction cost.

The remainder of this paper is organized as follows. Section 2 introduces related work. Section 3 presents the proposed MCC model. In section 4, empirical evaluations are given to show the superiority of MCC. Finally, section 5 presents conclusion and future work.



§ RELATED WORK

In this section, we briefly present state-of-the-art methods in multi-modal and multi-label <cit.> fields. As for modality extraction in multi-modal learning, it is closely related to feature extraction <cit.>. Therefore, we briefly review some related work on these two aspects in this section. 

Multi-label learning is a fundamental problem in machine leaning with a wide range of applications. In multi-label learning, each instance is associated with multiple interdependent labels. Binary Relevance (BR) <cit.> algorithm is the most simple and efficient solution of multi-label algorithms. However, the effectiveness of the resulting approaches might be suboptimal due to the ignorance of label correlations. To tackle this problem, Classifier Chains (CC) <cit.> was proposed as a high-order approach to consider correlations between labels. It is obviously that the performance of CC is seriously affected by the training order of labels. To account for the effect of ordering, Ensembles of Classifiers Chains (ECC) <cit.> is an ensemble framework of CC, which can be built with n random permutation instead of inducing one classifier chain. Entropy Chain Classifier (ETCC) <cit.> extends CC by calculating the contribution between two labels using information entropy theory while Latent Dirichlet Allocation Multi-Label (LDAML) <cit.> exploiting global correlations among labels. LDAML mainly solve the problem of large portion of single label instance in some special multi-label datasets. Due to high dimensionality of data , dimensionality reduction <cit.> or feature extraction should be taken into consideration. 

Originally, feature selection and dimensionality reduction are generally used for reducing the cost of feature extraction. <cit.> proposed regularized multilinear regression and selection for automatically selecting a set of features while optimizing prediction for high-dimensional data. Feature selection algorithms do not alter the original representation of the variables, but merely select part of them. Most of existing multi-label feature selection algorithms either boil down to solving multiple single-label feature selection problems or directly make use of imperfect labels. Therefore, they may not be able to find discriminative features that are shared by multiple labels. To reduce the negative effects of imperfect label information in finding label correlations, <cit.> decomposes the multi-label information into a low-dimensional space and then employs the reduced space to steer the feature selection process. Furthermore, we always extract multiple features rather than single feature for classification, several adaptive decision methods for multi-modal feature extraction are proposed <cit.> <cit.>. To further reduce the number of features for testing, <cit.> proposes a novel Discriminative Modal Pursuit (DMP) approach. 

In this paper, taking both multi-label learning and feature extraction into consideration, we propose MCC model with an end-to-end approach <cit.> for MMML problem, which is inspired by adaptive decision methods. 

Different from previous feature selection or dimensionality reduction methods, MCC extracts different modalities for different instances and different labels. Consequently, when presented with an unseen instance, we would extract the most informative and cost-effective modalities for it. Empirical study shows the efficiency and effectiveness of MCC, which can achieve better classification performance with less average modalities.



§ METHODOLOGY

This section first summarizes some formal symbols and definitions used throughout this paper, and then introduces the formulation of the proposed MCC model. An overview of our MCC algorithm is shown in Fig.<ref>.



 §.§ Notation

In the following, bold character denotes vector (e.g., X).

The task of this paper is to learn a function ℎ: 𝒳→ 2^𝒴 from a training dataset with N data samples 𝒟={( X_i,  Y_i)}_i=1^N. 
The i-th instance ( X_i,  Y_i) contains a feature vector X_i∈𝒳 and a label vector Y_i∈𝒴.

X_i = [X_i^1, X_i^2, …, X_i^P] ∈ℝ^d_1+d_2+…+d_P is a combination of all modalities and d_m is the dimensionality of features in m-th modality. Y_i = [y_i^1, y_i^2, …, y_i^L] ∈{-1, 1}^L denotes the label vector of X_i.
P is the number of modalities and L is the number of labels.

Moreover, we define c = {c_1, c_2, …, c_P} to represent the extraction cost of P modalities. 
Modality extraction sequence of X_i is denoted as S_i={S_i^1, S_i^2, …, S_i^m}, m ∈{1, 2, …, P}, m≤ P, where S_i^m∈{1, 2, …, P} represents m-th modality of features to extract of X_i and satisfies the following condition:  ∀ m, n (m ≠ n) ∈{1, 2, …, P}, S_i^m≠ S_i^n. It is noteworthy that different instances not only correspond to different extraction sequences but also may have different length of modalities of features extraction sequence.
Furthermore, we define some notations used for testing phase.
Suppose there is a testing dataset with M data samples 𝒯 = {( X_i,  Y_i)}_i=1^M.
We denote predicted labels of 𝒯 as Z ={ Z_i}_i=1^M, in which Z_i=(z_i^1, z_i^2, …, z_i^L) represents all predicted labels of X_i in 𝒯 and Z^j = (z_1^j, z_2^j, …, z_M^j)^T represents j-th predicted labels of all testing dataset.



 §.§ MCC algorithm

On one hand, MMML is related to multi-label learning and here we extend Classifier Chains to deal with it. On the other hand, each binary classification problem in Classifier Chains can be transferred into multi-modal problem and this procedure aims at making a convince prediction with less average modality extraction cost.









  §.§.§ Classifier Chains

Considering correlation among labels, we extend Classifier Chains to deal with Multi-modal and Multi-label problem. Classifier Chains algorithm transforms the multi-label learning problem into a chain of binary classification problems, where subsequent binary classifiers in the chain is built upon the predictions of preceding ones <cit.>, thus to consider the full relativity of the label hereby. 
The greatest challenge to CC is how to form a recurrence relation chain τ. In this paper, we propose a heuristic Gini index based Classifier Chains algorithm to specify τ. 

First of all, we split the multi-label dataset into several single-label datasets, i.e, for j-th label in {y^1, y^2, …, y^L}, we rebuild dataset 𝒟_j = {( X_i, y_i^j)}_i=1^N as j-th dataset of single-label. Secondly, we calculate Gini index <cit.> of each rebuilt single-label dataset 𝒟_j, (j=1, 2, …, L). 


    Gini(𝒟_j) = ∑_k=1^|𝒴|∑_k≠ k'p_kp_k' = 1 - ∑_k=1^|𝒴|p_k^2

where p_k represents the probability of randomly choosing two samples with same labels, p_k' represents the probability of randomly choosing two samples with different labels and |𝒴| represents number of labels in 𝒟_j.

And then we get predicted label chain τ = {τ_i}_i=1^L, composed of indexes of sorted {Gini(𝒟_i)}_i=1^L which is sorted in descending order. For L class labels {y^1, y^2, …, y^L}, we are supposed to split the label set one by one according to τ and then train L binary classifiers. 

For the j-th label y^τ_j, (j = 1, 2, …, L) in the ordered list τ, a corresponding binary training dataset is reconstructed by appending a set of labels preceding y_i^τ_j to each instance X_i: 

    𝒟_τ_j={([ X_i,xd_i^τ_j], y_i^τ_j)}_i=1^N

where xd_i^τ_j = (y_i^τ_1, …, y_i^τ_j-1) represents the binary assignment of those labels preceding y_i^τ_j on X_i (specifically xd_i, τ_1 = ∅) and [ X_i,xd_i^τ_j] represents concatenating vector X_i and xd_i^τ_j.  
We denote c_l as extraction cost of xd_i^τ_j. 
If j > 1, we combine the new set xd_i^τ_j as a new modality in 𝒟_τ_j. Moreover, each instance in 𝒟_τ_j is composed of P+1 modalities of features and extraction cost needs to be updated by appending c_l to c. 
We denote the new extraction cost as c' and c'=[c, c_l].

Meanwhile, a corresponding binary testing dataset is constructed by appending each instance with its relevance to those labels preceding y^τ_j: 

    𝒯_τ_j={([ X_i,xt_i^τ_j], y_i^τ_j)}_i=1^M

where xt_i^τ_j = (z_i^τ_1, …, z_i^τ_j-1) represents the binary assignment of those labels preceding z_i^τ_j on X_i (specifically xt_i^τ_1 = ∅) and [ X_i,xt_i^τ_j] represents concatenating vector X_i and xt_i^τ_j. 
We denote c_l as extraction cost of xt_i^τ_j, which is the same as extraction cost of xd_i^τ_j.
If j>1, each instance in 𝒯_τ_j is composed of P+1 modalities of features and one label y_i^τ_j.

After that, we propose an efficient Multi-modal Classifier Chains (MCC) algorithm, which will be introduced in the following paragraph. By passing a combination of training dataset 𝒟_τ_j and extraction cost c' as parameters of MCC, we get Z^τ_j. The final predicted labels of 𝒯 is the concatenation of Z^τ_j, (j=1, 2, …, L), i.e., Z = ( Z^τ_1,  Z^τ_2, …,  Z^τ_L)




  §.§.§ Multi-modal Classifier Chains

In order to induce a binary classifier 𝑓_𝑙: 𝒳×{-1, 1} with less average modality extraction cost and better performance in MCC, we design Multi-modal Classifier Chains (MCC) algorithm which is inspired by LSTM. 
MCC extracts modalities of features one by one until it's able to make a confident prediction. MCC algorithm extracts different modalities sequence with different length for difference instances, while previous feature extraction method extract all modalities of features and use the same features for all instances.

MCC adopts LSTM network to convert the variable X'_i∈𝒳 into a set of hidden representations H_i^t = [ h_i^1,  h_i^2, …,  h_i^t], h_i^t∈ℝ^h. Here, X̂_i^S_i^t = [X̂_i^1,…,X̂_i^m, …,X̂_i^P] is an adaptation of X_i. In the t-th step, the modality to be extracted is denoted as S_i^t. If m = S_i^t, X̂_i^m=  X_i^S_i^t, 0  otherwise.

 For example, if S_i^t = 3, X̂_i^3 = [ 0,  0,  X_i^3, …,  0].

Similar to peephole LSTM, MCC has three gates as well as two states:

forget gate layer, input gate layer, cell state layer, output gate layer, hidden state layer, listed as follows:

f_t = σ([ W_fc,  W_fh,  W_fx][ C_t-1,  h_t-1,X̂_t]^T +  b_f)

i_t = σ([ W_ic,  W_ih,  W_ix][ C_t-1,  h_t-1,X̂_t]^T+  b_i)

C_t =  f_t· C_t-1 +  i_t· tanh([ W_ch,  W_cx][ h_t-1,X̂_t]^T +  b_C)

o_t = σ ([ W_oc,  W_oh,  W_ox][ C_t,  h_t-1,X̂_t]^T +  b_o)

h_t =  o_t· tanh( C_t)

Different from LSTM, MCC adds two full connections to predict current label and next modality to be extracted. For one thing, there is a full connection between hidden layer and label prediction layer, with weight vector Ŵ_l. For another, there is a full connection between hidden layer and modality prediction layer, with weight vector Ŵ_m. Moreover, bias vector are denoted as b_l and b_m respectively.



  * Label prediction layer: This layer predicts label according to a nonlinear softmax function 𝑓l^j(.). 

    𝑓l^j( H_i^t) = σ( H_i^tŴ_l +  b_l)



  * Modality prediction layer: This layer predicts next modality according to a linear function fm^j(.) and selects maximum as next modality to be extracted.

    𝑓m^j( H_i^t) =  H_i^tŴ_m +  b_m




We use ℱL=[fl^1, fl^2, …, fl^L] and ℱM=[fm^1, fm^2, …, fm^L] to denote the label prediction function set and modality prediction function set respectively.

Next, we design loss function composed of loss term and regularization term for producing optimum and faster results. Above all, we design loss of instance X̂_i with S_i^t modality as follows.

    L_i^t = L_l(𝑓l^j( H_i^t), y_i) + L_m(𝑓m^j( H_i^t), X̂_i^t)

Here we adopt log loss for label prediction loss function L_l and hinge loss for modality prediction loss function L_m, where modality prediction is measured by distances to K Nearest Neighbors <cit.>.

Meanwhile, we add Ridge Regression (L2 norm) to the overall loss function.

    Ω_i^t = ||Ŵ_m||^2+||Ŵ_l||^2+ || c ·𝑓m^j( H_i^t)||

where ||.|| represents L2 norm and c represents extraction cost of each modality.

The loss term is the sum of loss in all instances at t-th step. The overall loss function is as follows.

    L_t = ∑_i^N(L_i^t + λ·Ω_i^t)

where λ=0.1 is trade-off between loss and regularization.

In order to optimize the aforementioned loss function L_t, we adopt a novel pre-dimension learning rate method for gradient descent called AdaDelta <cit.>. Here, we denote all the parameters in Eq.<ref> as W = [Ŵ_m,Ŵ_l, λ].

At t-th step, we start by computing gradient g_t = ∂ L_t/∂ W_t and accumulating decaying average of the squared gradients:

    E[ g^2]_t = ρ E[ g^2]_t-1+(1-ρ) g_t^2

where ρ is a decay constant and ρ = 0.95.



The resulting parameter update is then: 

    W_t = -√(E[( W)^2]_t-1+ϵ)/√(E[ g^2]_t+ϵ) g_t

where ϵ is a constant and ϵ = 1e^-8.

And then, we accumulate update:

    E[ W^2]_t = ρ E[ W^2]_t-1+(1-ρ) W_t^2


The pseudo-code of MCC is summarized in Algorithm <ref>. N_b denotes batch size of training phase. N_iter represents maximum number of iterations. C_th represents the threshold of cost. A_th represents the threshold of accuracy of the predicted label. ĉ_i^t denotes the sum of extraction cost and a_i^t denotes accuracy of current predicted label.




§ EXPERIMENT




 §.§ Dataset Description

We manually collect one real-world Herbs dataset and adapt two publicly available datasets including Emotions <cit.> and Scene <cit.>. As for Herbs, there are 5 modalities with explicit modal partitions: channel tropism, symptom, function, dosage and flavor. As for Emotions and Scene, we divide the features into different modalities according to information entropy gain. The details are summarized in Table <ref>. 



 §.§ Experimental Settings

All the experiments are running on a machine with 3.2GHz Inter Core i7 processor and 64GB main memory.

We compare MCC with four multi-label algorithms: BR, CC, ECC, MLKNN<cit.> and one state-of-the-art multi-modal algorithm: DMP<cit.>. 
For multi-label learner, all modalities of a dataset are concatenated together as a single modal input. For multi-modal method, we treat each label independently.

F-measure is one of the most popular metrics for evaluation of binary classification<cit.>.


To have a fair comparison, we employ three widely adopted standard metrics, i.e., Micro-average, Hamming-Loss, Subset-Accuracy<cit.>. In addition, we use Cost-average to measure the average modality extraction cost.  

For the sake of convenience in the regularization function computation, extraction cost of each modality is set to 1.0 in the experiment. Furthermore, we set the cost of new modality (predicted labels) to 0.1 to demonstrate its superiority compared with DMP. 



 §.§ Experimental Results

For all these algorithms, we report the best results of the optimal parameters in terms of classification performance. Meanwhile, we perform 10-fold cross validation (CV) and take the average value of the results in the end. 

For one thing, table <ref> shows the experimental results of our proposed MCC algorithm as well as other five comparing algorithms. 



It is obvious that MCC outperforms the other five algorithms on all metrics. 
For another, as shown in table <ref>, MCC uses less average modality extraction cost than DMP, while other four multi-label algorithms use all the modalities.





§ CONCLUSION

Complex objects, i.e., the articles, the images, etc can always be represented with multi-modal and multi-label information.
However, the quality of modalities extracted from various channels are inconsistent. 
Using data from all modalities is not a wise decision.
In this paper, we propose a novel Multi-modal Classifier Chains (MCC) algorithm to improve supplements categorization prediction for MMML problem. 
Experiments in one real-world dataset and two public datasets validate the effectiveness of our algorithm. MCC makes great use of modalities, which can make a convince prediction with many instead of all modalities.
Consequently, MCC reduces modality extraction cost, but it has the limitation of time-consuming compared with other algorithms.
In the future work, how to improve extraction parallelism is a very interesting work.



§ ACKNOWLEDGEMENT

This paper is supported by the National Key Research and Development Program of China (Grant No. 2016YFB1001102), the National Natural Science Foundation of China (Grant No. 61876080), the Collaborative Innovation Center of Novel Software Technology and Industrialization at Nanjing University.





IEEEbib



