Research On Key Problems Of Multi-label Learning

With the development of science and technology, more and more real-world applications involve multi-label problems, such as text categorization, image annotation, gene functional analysis and so on. In contrast with traditional single-label (binary or multiclass) problems, an instance is allowed to be associated with several labels simultaneously in multi-label problems, which yields correlations among labels. The goal of multi-label learning is to assign all appropriate labels to a new instance in multi-label problems. Due to the existence of label correlations, multi-label learning is much more complex than traditional single-label learning. More and more researchers devote themselves to multi-label learning. Now multi-label learning has been a hot research field in machine learning and pattern recognition.Although there has been great progress in multi-label learning, it still faces several challenges, such as unsatisfactory classification performance of existing multi-label classification algorithms, high dimensionality of label space, high dimensionality of feature space, etc.. Therefore, multi-label classification, label space dimensionality reduction (LSDR) and multi-label feature space dimensionality reduction (FSDR) are three key research points of multi-label learning. Multi-label classification methods aim to improve the classification performance. By reducing the label space to use label correlations, LSDR methods aim to improve the classification performance and reduce the time cost at the same time. To combat the curse of high dimensionality in multi-label learning, multi-label FSDR methods aim to obtain better instance representation by projecting original instances into a lower-dimensional feature space. This thesis focuses on these three points with our main works listed as follows:1. In the light of the clustered relationship among labels, a new multi-label classification method, termed Clustered Intrinsic Label Correlations (CILC), is proposed. It assumes that the weight vector of each label consists of a common component and a label-specific component. The former is shared by all labels, handling the background information of instances, while the latter is owned by one label, handling the label-specific information of instances. The intrinsic label correlations among labels are deemed to be the relationship among label-specific components. CILC extends Support Vector Machines with the above weight vector structure for each label, and enforces a regularization term about clustered assumption on label-specific components to utilize clustered relationship. By relaxing the orthogonal constraint, the non-convex optimization problem becomes a jointly-convex semi-definite programming problem, and we provide an optimization method using block coordinate descent based on alternate optimization. Experimental results verify its superiority to compared methods.2. Existing multi-label classification methods use the same instance representation for the training of all labels, which may be suboptimal. This thesis proposes a new multi-label classification method, termed Multi-label Learning with Discriminative Features for each Label (ML-DFL), which constructs label-specific instance representation for each label according to its instance distribution. ML-DFL transforms a multi-label classification problem into several binary classification sub-problems using one-versus-all strategy, one sub-problem for each label. For each sub-problem, the closely located structures between positive and negative instances are very important for building an effective classification model. To extract these structures, this thesis also proposes a new spectral clustering method, called Spectral Instance Alignment (SIA). ML-DFL constructs a new instance representation for each label using the clustering results of SIA, which is more aware of its instance distribution. Then a binary classification model is trained using the new instance representation for each label. Experimental results validate the effectiveness of ML-DFL.3. In order to utilize instances better in the process of LSDR, this thesis proposes a new LSDR method, termed Dependence Maximization based Label space dimensionality Reduction (DMLR). Its objective function consists of two parts:encoding loss and dependence loss. Encoding loss measures the information loss of compressing label matrix using Principal Component Analysis (PCA) in the label compression procedure. After LSDR, we obtain code vectors from label vectors. Since it needs to train a regression model from feature space to code vector space later, dependence loss plays a very important role in LSDR methods. Dependence loss measures the loss between instances and the obtained code vectors. For the first time, a dependence loss is derived from Hilbert-Schmidt Independence Criterion (HSIC) to make better use of the relationship between instances and code vectors. Moreover, we discuss the influence of two different instance kernel matrices on the proposed method, which are based on global structures and local latent structures respectively. Experimental results show that the proposed method not only reduces the training and testing time drastically, but also improves the classification performance effectively. The proposed method is able to achieve better classification performance with the instance kernel matrix using local latent structures than global structures at the similar training and testing time cost.4. To combat the outliers among instances and label vectors, this thesis proposes a new LSDR method based on l2.1-norm, termed Robust Label Compression (RLC). Due to the problem of data acquisition devices, there usually exist outliers among instances. The outliers among label vectors refer to those label vectors that are not in accordance with the main label relationship used in the LSDR method. The objective function of RLC consists of two losses:encoding loss and dependence loss. Encoding loss measures the information loss of compressing label matrix using PCA in the label compression procedure. Dependence loss measures the loss of linear regression information from instances to code vectors. RLC uses l2.1-norm for both encoding loss and dependence loss in the objective function to make the results more robust to these outliers. The derived optimization problem is non-smooth and this thesis proposes an effective optimization method for RLC, termed transformed alternative optimization, whose convergence analysis is also provided. Experimental results show that RLC is able to improve the classification performance and reduce the training and testing time. Moreover, experiments on data sets with contaminated labels show that compared with other LSDR methods, RLC is more robust.5. Existing multi-label FSDR methods do not exploit local latent structures which have been shown very important in traditional FSDR methods. Therefore, this thesis proposes a new multi-label FSDR method, called Multi-label Local Discriminative Embedding (MLDE). It gives higher weight to those instances of more information and overcomes over-counting problem of multi-label learning using non-symmetric label correlation matrix, which is more consistent with reality. By constructing two sets of graphs, it analyzes and exploits local latent structures to achieve better intraclass compactness and interclass separability. A set of orthogonal vectors are obtained by enforcing an orthogonal constraint on the derived optimization problem. Experimental results show that compared with related multi-label FSDR methods, the projection results of MLDE are more reasonable and discriminative, thus yielding higher classification accuracy.