# A Deep Learning-Based Approach for Multi-Label Emotion Classification in Tweets
## 2 Related Works
### Problem Transformation Methods  
Let \(X=\{x_{1},x_{2},\ldots x_{n}\}\) be the set of all instances and \(Y=\{y_{1},y_{2},\ldots,y_{m}\}\) be the set of all labels. We can define the set of data:  
\[D=\{(x_{i},\hat{Y}_{i})|x_{i}\in X\text{ and }\hat{Y}_{i}\subseteq Y\text{ is the set of labels associated with }x_{i}\} \tag{1}\]  
In this expression, \(D\) is called a supervised multi-label dataset.  
The task of multi-label classification is challenging because the number of label sets grows exponentially as the number of class labels increases. One common strategy to address this issue is to transform the problem into a traditional classification problem. The idea is to simplify the learning process by exploiting label correlations. Based on the order of the correlations, we can group the existing transformation methods into three approaches [17; 18], namely first-order approaches, second-order approaches, and high-order approaches.  
First-order approaches decompose the problem into some independent binary classification problems. In this case, one binary classifier is learned for each possible class, ignoring the co-existence of other labels. Thus, the number of independent binary classifiers needed is equal to the number of labels. For each multi-label training example \((x_{i},\hat{Y}_{i})\in D\), \(y_{k}\in Y\), we construct a binary classification training set, \(D_{k}\) as the following: \(x_{i}\) will be regarded as one positive example if \(y_{k}\in\hat{Y}_{i}\) and one negative example otherwise. In the first case, we will get a training example in the form \((x_{i},1)\in D_{k}\), which will be \((x_{i},0)\in D_{k}\) in the second case. Thus, for all labels \(\{y_{1},y_{2},\ldots,y_{m}\}\in Y\), \(m\) training sets \(\{D_{1},D_{2},\ldots,D_{m}\}\) are constructed. Based on that, for each training set \(D_{k}\), one binary classifier can be learned with popular learning techniques such as AdaBoost [19], k-nearest neighbor [20], decision trees, random forests [21; 22], etc. The main advantage of first-order approaches is their conceptual simplicity and high efficiency. However, these approaches can be less effective due to their ignorance of label correlations.  
Second-order approaches try to address the lack of modeling label correlations by exploiting pairwise relationships between the labels. One way to consider pairwise relationships is to train one binary classifier for each _pair_ of labels [23]. Although second-order approaches perform well in several domains, they are more complicated than the first-order approaches in terms of the number of classifiers. Their complexity is quadratic, as the number of classifiers needed is \(\binom{m}{2}\). Moreover, in real-world applications, label correlations could be more complex and go beyond second-order.  
High-order approaches tackle the multi-label learning problem by exploring high-order relationships among the labels. This can be fulfilled by assuming linear combinations [24], a nonlinear mapping [25; 26], or a shared subspace over the whole label space [27]. Although high-order approaches have stronger correlation-modeling capabilities than their first-order and second-order counterparts, these approaches are computationally demanding and less scalable.  
Our transformation mechanism, shown in Section 3.1, is a simple as the first-order approaches and can model, implicitly, high-order relationships among the labels if some requirements, detailed in Section 3.1, are fulfilled. It requires only one binary classifier, and the number of training examples grows polynomially in terms of the number of instances and the number of labels. If the number of training examples in the multi-label training dataset is \(n\) and the number of the labels is \(m\), then the number of the training examples in the transformed binary training set is \(n\times m\).