Multi-Label Open Set Recognition

Authors: yi-bo  wang
jun-yi  hang
min-ling  zhang
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 13:52:23

Abstract: In multi-label learning, each training instance is associated with multiple labels simultaneously. Traditional multi-label learning studies primarily focus on closed set scenario, i.e. the class label set of test data is identical to those used in training phase. Nevertheless, in numerous real-world scenarios, the environment is open and dynamic where unknown labels may emerge gradually during testing. In this paper, the problem of multi-label open set recognition (MLOSR) is investigated, which poses significant challenges in classifying and recognizing instances with unknown labels in multi-label setting. To enable open set multi-label prediction, a novel approach named SLAN is proposed by leveraging sub-labeling information enriched by structural information in the feature space. Accordingly, unknown labels are recognized by differentiating the sub-labeling information from holistic supervision. Experimental results on various datasets validate the effectiveness of the proposed approach in dealing with the MLOSR problem.

Main paper: 
 introduction: 
 Multi-label Learning (MLL) deals with the problem where an instance can be associated with multiple labels simultaneously [37, 19] . As a practical machine learning paradigm, multi-label learning has been widely applied in various real-world applications, such as image annotation [30] , text categorization [26] , information retrieval [12] . Traditional multi-label learning studies focus on closed set scenario. That is, they assume that the class label set of test data is identical to that in the training set [37, 8, 21] . However, in many real-world scenarios, this assumption rarely holds because the environment is open and dynamic [29] . In addition to the extant label knowledge at training phase, the unknown labels may emerge gradually with the data streams during the testing phase. For example, in Figure 1 , the test image is annotated with several relevant labels, some of which are unseen in the training set. The classification task becomes much more challenging because the label correlation between known and unknown labels may degrade the performance of the predictive model. Furthermore, due to the presence of unknown labels in the class label set of test data, these test data are hardly employed in subsequent learning processes, such as incremental learning [15] .Motivated by the potential applications, we formalize a novel framework named multi-label open set recognition (MLOSR), whose goal is to learn a multi-label model that can correctly classify known labels for the unseen instance and recognize unknown labels within its relevant label set. This can be regarded as a special weakly supervised learning. In MLOSR, the most challenging part is to recognize the unknown labels associated with instances. Since we do not have any prior knowledge of unknown labels and they almost always co-occur with some known labels, it is very difficult to separate instances with unknown labels from those with the known labels only. The test image is associated with a variety of relevant labels. Among the set of relevant labels, "cloud", "car", "ship", "building", "tree" and "sky" are known labels seen in the training set, while "sea", "mountain" and "trestle bridge" are unknown labels emerging in the testing phase.Open set recognition (OSR) is a paradigm previously proposed in [24] and is formalized as a riskminimizing constrained functional optimization problem. OSR describes a scenario where new classes unseen in training occur in testing, thus classifiers must be able to properly identify seen samples while rejecting unseen ones [9] . [24] proposes a 1-vs-Set machine to minimize open set risk by sculpting a decision space from the marginal distances of binary SVM. OSR problem is further studied via algorithm adaptation [1, 16] , statistical extreme value theory (EVT) [25, 32] , margin distribution [23] or hierarchical Dirichlet process [10] . These existing works are based on the fact that each instance owns one ground-truth label for multi-class cases. Thus, they cannot be used to directly solve the MLOSR problem, due to the multiple ground-truth labels in MLL.To address MLOSR problem, we propose a tailored algorithm named SLAN, i.e. Sub-Labeling informAtion reconstructioN for multi-label open set recognition. The basic strategy of SLAN is to enrich the sub-labeling information in the sub-label space by leveraging the structural information in the feature space and differentiating it from the labeling information from holistic supervision. Specifically, the underlying structure of feature space is characterized by the sparse reconstruction relationships among training instances. After that, the reconstruction information is utilized to guide the enrichment of sub-labeling information. Then, a unified optimization framework is presented to simultaneously facilitate open set recognizer and multi-label classifier induced with alternating optimization. Our empirical study on datasets from diverse domains demonstrates the effectiveness of the proposed approach.The rest of the paper is organized as follows. We present a brief review of related works. Then we formulate the problem and propose the algorithm. Next, experimental results are reported, followed by the conclusion. 
related work: 
 The task of multi-label learning has been extensively studied in recent years [37, 19] . Generally, the major challenge for multi-label learning is its huge output space which is exponential to the number of class labels. Therefore, exploiting label correlations has been adopted as a common strategy to facilitate the learning process. Roughly speaking, extant approaches can be grouped into three categories based on the order of correlations, i.e. first-order approaches, second-order approaches and high-order approaches. First-order approaches tackle multi-label learning problem in a label-by-label manner [2, 33] . Second-order approaches exploit pairwise interactions among class labels [7, 3] . High-order approaches exploit relationships among a subset of or all class labels [22, 14] .OSR is critical for the tasks where incomplete knowledge exists at training time, and unknown classes can be submitted to an algorithm during the testing phase, requiring the classifiers to classify the seen classes and deal with unseen ones. According to [9] , traditional machine learning methods are adapted to OSR scenario. For instance, SVM-based models add extra constraints on the score space in [24, 4] ; A collective decision-based model implemented by hierarchical Dirichlet process is proposed in [10] ; and distance-based models [1, 16] are developed by modifying existing classifiers, such as nearest class mean classifier and nearest neighbor classifier. Some other approaches focus on the EVT [17] . [25] combines the EVT for score calibration with two separated compact abating probability SVMs, where the first SVM is used as a conditioner and the second SVM fitted yields the posterior estimate. [32] transforms the OSR problem into a set of hypothesis testing problems by modeling the tail part of reconstruction error distribution via EVT. [23] formulates the extreme value machine with distributional information, which can be interpreted by EVT. There are also some methods trying to incorporate few-shot learning into OSR [5] .MLOSR can be regarded as a combination of MLL and OSR. Thus, a straightforward approach is to generate a independent recognizer besides the multi-label classifier. However, as unknown labels may co-occur with known labels, it is difficult to separate instances with unknown labels from instances with known labels only, which leads to OSR approaches that could not be applied in MLOSR problems.Streaming multi-label learning (SMLL) [31] is similar to our MLOSR problem but differs in the setting of unknown labels. It aims to derive a unified model by taking care of the continually emerging new unknown labels on the training data. [31] trains a linear classifier for new labels with the linear hypotheses between labels and classifiers. [28] proposes a novel DNN-based framework to model the emerging new labels depending on high-order representations. [29] presents probabilistic streaming label tree to incorporate new labels, which capture hierarchical correlations among labels. Compared to SMLL, MLOSR is much more challenging in recognizing unknown labels as the unknown labels only emerge in testing phase. In the next section, the first attempt towards MLOSR is introduced.3 The SLAN Approach 
problem formulation: 
 Formally, let X = R d denote the d-dimensional input space and Y = {l 1 , l 2 , . . . , l q } denote the label space including q class labels. Each multi-label instance can be denoted as (x i , Y i ), where x i ∈ X is its feature vector and Y i ⊆ Y is the set of relevant labels associated with x i . Here, a q-dimensional indicator vector y i = [y i1 , y i2 , ... EQUATIONwhere λ r is a regularization constant.To characterize the underlying manifold structure of feature space, a weighted directed graph G = (V, E, S) is constructed over the set of training instances, whereV = {x i | 0 ≤ i ≤ m} corresponds to the set of vertices and E = {(x i , x j ) | s ij ̸ = 0, 1 ≤ i ̸ = j ≤ m}corresponds to the set of edges from x i to x j with nonzero weight.Furthermore, S = [s ij ] m×m corresponds to the weight matrix encoding the relationships among all training instances. Conceptually, the weight value s ij reflects relative importance of x i in reconstructing x j . Thus, by implementing global sparse reconstruction, the weight matrix S is instantiated by solving the following optimization problem:min S ||XS -X|| 2 F + µ 0 ||S|| 1 s.t. s ii = 0, ∀1 ≤ i ≤ m (2)Here, the first term controls the linear reconstruction error via squared Frobenius norm while the second term controls the sparsity of reconstruction via ℓ 1 norm. The relative importance is balanced by the trade-off parameter µ 0 . Then, the constrained optimization problem in Eq.( 2) can be solved via a standard ADMM (Alternating Direction Method of Multiplier) procedure [11] .According to the manifold assumption, the structural relationship specified in the feature space should also be preserved in the entire label space to enrich labeling information originally encoding in the indicator vector y i [13, 38] . That is, y i can be transformed into a numerical labeling vector z i = [z i1 , z i2 , . . . , z iq ] ⊤ under holistic supervision which encodes richer semantics for predictive model induction.However, this assumption might be suboptimal in the entire label space. Considering one specific labell k ∈ Y, let f k i = [f k i1 , . . . , f k i,k-1 , f k i,k+1 , . . . , f k iq ]⊤ represent the enriched sub-labeling information of x i . With the manifold assumption, the structural information would be maintained in the sub-label space Y\{l k }. Then, instances with l k can be reconstructed via the instances without l k as well as the enriched sub-labeling information. Nevertheless, these reconstructed instances can not be assigned with l k since there's not enough positive labeling information w.r.t. l k . That is, the sub-labeling information is differentiated from labeling information with holistic supervision. Thus, in open set scenario, if l k is specified as an unknown class label, such difference can be employed as a criterion for one specific instance to distinguish whether it is associated with an unknown class label.f k i , denoted by F k = [f k 1 , . . . , f k m ] ∈ R (q-1)×m and all z i , denoted by Z = [z 1 , . . . , z m ] ∈ R q×m .The enriched sub-labeling information is generated via leveraging the structural information encoded in S by solving the following optimization problem:EQUATIONHere, δ k i is a indicator variable, where δ k i = 1 if l k is not associated with x i ; otherwise δ k i = 0. P k is a (q -1) × q projection matrix to align z i with f k i without regard to l k , which removes the k-th row of the identity matrix. The first term supervises the labeling information from the holistic aspect. The second term conveys the manifold structure specified in the feature space to the sub-label space. The third term minimizes the labeling information difference between sub-label space and entire label space to differentiate instances with or without such unknown class label, which implicitly reduces the open space risk.During the testing phase, for an unseen instance x * , the reconstruction coefficients w.r.t. l k is identified by resorting to the ADMM technique over the training set. After that, the enriched sublabeling information f k * of x * is determined via the second term of Eq.(3). Thereafter, whether unknown labels are associated with x * is determined by the following recognizer G via ensemble majority voting:EQUATIONwhereg k (x * ) = -1 if ||f k * -P k z * || 2 2 > ρ k ; otherwise g k (x * ) = 1.ρ k is the threshold, and can be chosen so that 100×τ % instances with l k in training set satisfy||f k i -P k z i || 2 2 > ρ k .The labeling information z * under holistic supervision is generated by the following MLL classifier.Similar to the existing strategy in previous OSR algorithms, instead of training the classifier independently, we perform open set recognizer and multi-label classifier induced simultaneously. Then, the sub-labeling information can be optimized by considering both the manifold assumption and model outputs. Furthermore, considering the label correlation between known and unknown labels, such jointly optimization procedure with recognizer can facilitate the classifier more robust. We denote W ∈ R q×d and b ∈ R q as a multi-label classifier and adopt the squared Frobenius norm as the regularization term to control the model complexity:min W ,b m i=1 1 2 ||Wx i + b -z i || 2 2 + µ 1 2 ||W|| 2 F (5) Let B k = [b k pi ] (q-1)×m denote the indicator matrix with b k pi = δ k i .Then, the objective function of the unified framework is shown as follows:min W,b,Z, F1,...,Fq q k=1 ( β 2 ||F k S -F k || 2 F + α 2 ||B k • (P k Z -F k )|| 2 F ) + 1 2 ||Z -(WX + b1 ⊤ n )|| 2 F + γ 2 ||Z -Y|| 2 F + µ 1 2 ||W|| 2 F (6)Here, The first two terms control the open space risk and remaining terms control the empirical risk.Update Z With fixed F 1 , . . . , F q , W and b, the optimization problem Eq.( 6) can be stated as follows:EQUATION)The above optimization problem can be solved by updating Z with gradient descent. The gradient of the objective function w.r.t. Z isEQUATIONUpdate F 1 , . . . , F q With Z, W and b fixed, the optimization problem Eq.( 6) can be stated as follows:min F k β 2 ||F k S -F k || 2 F + α 2 ||B k • (P k Z -F k )|| 2 F (9)Similarly, gradient descent is employed, and the gradient w.r.t. F k is:EQUATIONwhereT = (S -I m×m )(S -I m×m ) ⊤ .Update W and b While Z and F 1 , . . . , F q are fixed, the optimization problem (4) can be stated as follows:EQUATIONHere, E = [e 1 , . . . , e m ] ∈ R q×m , where e i = z i -(Wx i + b). To achieve better performance of the predictive model, a kernel extension is further facilitated for the general nonlinear case. Let Φ = [ϕ(x 1 ), . . . , ϕ(x m )] ∈ R h×m , where ϕ(•) : R d → R h corresponds to the feature mapping that maps the feature space to some higher dimensional Hilbert space with h dimensions. Then, the Lagrangian function of this problem can be formulated as: Update Z according to Eq.( 7); 7:EQUATIONUpdate F k according to Eq.( 9); 8:Update W and b according to Eq.( 11); 9: until convergence or maximum number of iterations being reached 10: return Y * and G(x * ) according to Eq.( 14) and Eq.( 4).where A = [a ki ] ∈ R q×m stores the Lagrange multipliers. According to the KKT conditions, we can obtain:EQUATIONwhereH = 1 µ1 K + I m×m and K = Φ ⊤ Φ with its element k ij = κ(x i , x j ) = ϕ(x i ) ⊤ ϕ(x j) based on the chosen kernel function κ(•, •). Then, by incorporating the specified kernel function, the modeling output is denoted by 1 µ1 AK + b1 ⊤ m . Furthermore, given an unseen instance x * ∈ X , its relevant label set is predicted as:EQUATIONThe pseudo-code of SLAN is summarized in Algorithm 1. Given the multi-label training set, a weighted graph is constructed to characterize the manifold structure of feature space (Step 1). After that, the alternative optimization strategy is adopted to optimize open set recognizer and multi-label classifier simultaneously (Step 2-9). Finally, the relevant label set of the unseen instance is predicted and the recognition result is generated based on the learned model (Step 10). imbalance, any class label with rare appearance or with overly-high imbalance ratio is excluded from the label space following previous settings [34] .For a given dataset, we randomly select 50% labels as known labels and the remaining labels as unknown labels with different label batch sizes. Then, we sample 60% instances without unknown labels to form training set while the remaining instances are treated as test data. The sampling procedure is repeated ten times, and the mean metric value as well as standard deviation for each label batch are reported.To evaluate the performance of multi-label classifiers, we utilize five widely-used multi-label evaluation metrics [37] , including Ranking loss, One-error, Coverage, Average precision and Macroaveraging AUC. In addition, F-measure is employed to evaluate the performance of recognizers.To validate the effectiveness of the proposed SLAN approach in multi-label learning, four multi-label learning approaches are used for comparative studies.• LIFT [35] : A multi-label learning approach, which induces classifiers with the label-specific features generated via conducting clustering analysis for each class label. [parameter configuration: r = 0.1] • MUENLPLR [39] : A SVM-based dynamic multi-label learning approach which trains a set of linear classifiers by minimizing misclassification loss and pairwise ranking loss. [parameter configuration:C 1 = 1, C 2 = 1]• SENCE [27] : A multi-label learning approach based on label-specific features generated by mixture-based clustering ensemble. [parameter configuration: r= 0.4].• LIMIC [21] : A multi-semantics multi-label metric learning approach coupled with ML-LNN [36] which learns one global and multiple label-specific local metrics simultaneously.[parameter configuration:λ 1 = 1, λ 2 = 100, γ = 2, K = 10].With the first attempt towards solving the MLOSR problem, there is no method can be directly applied. Thus, we compare the proposed SLAN approach with existing anomaly detection approaches.• OC-SVM [20] : A SVM-based approach which constructs a hyper-sphere surrounding all instances from known labels.• IFOREST [18] : An unsupervised forest-based anomaly detection approach which employs average path length over all trees as the anomaly score.• MUENLFOREST [39] : A forest-based dynamic multi-label learning approach which utilizes clustering process in each nodes by considering the feature space and the label patterns.[parameter configuration: q = 5, ψ = 256, g = 100, e m = 9].For the proposed SLAN approach, trade-off parameters are set as α = 0.1, β = 0.1, γ = 10, µ 1 = 0.1, τ = 0.8. µ 0 is fixed to be 0.1. The sensitivity analysis of parameter configurations is conducted in Subsection 4.3. A Linux server equipped with Intel Xeon CPU (48 cores @ 2.67GHz) and 256GB memory is used for supporting the experiments. 
experimental results: 
 The detailed experimental results in terms of Ranking loss and F-measure are reported in Table 2 -3. Due to the page limit, the results on other metrics are shown in the Appendix. Meanwhile, pairwise t-test [6] is conducted to demonstrate whether the performance of SLAN is statistically superior/inferior to the comparing approaches on each data set. The resulting win/tie/loss counts are summarized in the supplementary material.Based on the reported experimental results, the following observations can be made:• Compared with the performance on close set instances (#label = 0), the performance of all comparing approaches on open set instances degrades. Nonetheless, across all multi-label evaluation metrics, SLAN achieves superior or at least comparable performance against the comparing approaches in 91.7% cases. However, the predictive values might be suboptimal as MUENLPLR is trained without considering open space risk. • In the multi-label setting, instances with unknown labels may share the same dense region of instances with known labels, which makes multi-class anomaly detection approaches tend to reject instances with unknown labels. That is why since MUENLPLR is under multi-label setting, it still inferior to IFOREST and OC-SVM.In this section, we study the sensitivity analysis of trade-off parameters α, β, γ, µ 1 , τ shown in Algorithm 1. Figure 2 illustrates how the performance of SLAN changes with varying parameter configurations on data set enron. As shown in Figure 2 , SLAN achieves relatively stable performance on multi-label metrics and somewhat sensitive on F-measure. In this paper, trade-off parameters are set as α = 0.1, β = 0.1, γ = 10, µ 1 = 0.1, τ = 0.8, which can be employed as the default parameter setting.  
conclusion: 
 The major contributions of our work are two-fold:  
 
 Appendix:  


Decision: This paper was reviewed by three experts in the field and received "Weak Accept", "Accept" and "Borderline Accept" as the ratings. The reviewers agreed that the proposed multi-label open set recognition framework introduces a new direction for multi-label learning research, the experimental analysis is comprehensive with encouraging results, and that the paper is well-written and easy to follow. 

The reviewers raised concerns about the robustness of the proposed method, which was addressed convincingly by the authors in the rebuttal. The authors also conducted experiments to study the interactions between different parameter combinations, in response to a comment from one of the reviewers. Concerns were also raised about the parameter sensitivity analysis, which was also addressed convincingly by the authors in the rebuttal.  

The reviewers, in general, have a positive opinion about the paper and its contributions. Based on the reviewers' feedback, the decision is to recommend the paper for acceptance to NeurIPS 2024. The reviewers have provided some valuable comments, such as the theoretical analyses of the proposed method, its computational efficiency when dealing with datasets with a large number of labels and designing multi-label open set recognition algorithms with deep learning models. The authors are encouraged to address these in the final version of their paper. The authors are also encouraged to make their code publicly available for better reproducibility. We congratulate the authors on the acceptance of their paper!

Reviews: review: paper_summary: paper_summary: The abstract discusses multi-label learning where instances can have multiple labels simultaneously. Traditional approaches assume a closed set scenario where test data labels are predefined during training. However, in real-world situations, new labels can emerge during testing, creating an open and dynamic environment. The paper explores Multi-Label Open Set Recognition (MLOSR), which tackles the challenge of recognizing instances with unknown labels in multi-label settings. The proposed approach, SLAN, utilizes sub-labeling information enriched by structural features in the data space to predict unknown labels. Experimental results across different datasets demonstrate the effectiveness of SLAN in addressing the MLOSR problem.
strength_weakness: strength_weakness: Generalization Ability: The SLAN algorithm may have limited generalization ability when dealing with extremely multi-label datasets, restricting its application in broader scenarios.
Feature Representation Limitations: Operating within the multi-label learning framework, SLAN might be constrained by less informative or discriminative feature representations.
Computational Resources: While the paper mentions the computational resources for the experiments, it does not elaborate on the computational efficiency and scalability of the algorithm, which may impact its application to large-scale datasets.
Theoretical Foundation: The paper does not provide theoretical results or proofs, which might reduce the depth of understanding of the algorithm's performance.
Access to Code and Datasets: Although the datasets are public, the paper states that the code will be released after acceptance, which may temporarily limit the reproducibility of the results.
questions: questions: How does the SLAN algorithm perform on datasets with highly imbalanced label distributions?
Does the parameter sensitivity analysis mentioned in the paper consider the characteristics of different types of datasets?
How adaptable and efficient is the SLAN algorithm for real-time or dynamically changing data streams in practical applications?
Does the paper consider the interpretability of the algorithm, i.e., how to explain the predictive results of SLAN?
For future work, are the authors planning to combine the SLAN algorithm with deep learning models to enhance the quality of feature representation and the performance of the algorithm?
limitations: limitations: Yes
paper_summary: paper_summary: This article introduces a new problem in multi-label open set recognition (MLOSR) and proposes a novel approach named Sub-Labeling Information Reconstruction for MLOSR (SLAN). SLAN utilizes sub-labeling information enriched by structural details in the feature space. Experimental results across various datasets demonstrate its effectiveness in addressing this new challenge of MLOSR.
strength_weakness: strength_weakness: 1. In the Parameter Sensitivity Analysis section, there is some explanation regarding the experimental parameter settings, but it primarily involves varying each parameter individually without further elaboration on their combined effects or interactions. It would be beneficial to include more extensive experimental analysis that considers the interactions between different parameter combinations.
2. The paper asserts that OC-SVM, IFOREST, and MUENLFOREST do not exhibit performance on par with SLAN. It would be advantageous to provide further elaboration on why the parameters of these comparison methods, particularly MUENLFOREST, are configured as they are.  
3. Is there any insight into how SLAN performs differently compared to other methods on different datasets? Could this difference be related to dataset characteristics and distributions?
questions: questions: 1. There is concern regarding the robustness of the method. How stable is its performance when errors or irrelevant labels appear in the dataset?
limitations: limitations: NA
paper_summary: paper_summary: This paper addresses the problem of classifying instances with unknown labels in a multi-label setting (multi-label open set recognition). A
novel approach named SLAN is proposed which leverages sub-labeling information, and unknown labels are recognized by differentiating the sub-labeling information from holistic supervision. The effectiveness of the proposed method is validated on different benchmarks.
strength_weakness: strength_weakness: - The paper introduces the MLOSR problem, which is novel, but it may overlap with existing tasks like zero-shot multi-label classification and open-vocabulary multi-label classification.

- This paper has limited baselines for comparison. While the paper includes comparisons with several multi-label learning and anomaly detection approaches, it should also compare with state-of-the-art methods specifically designed for zero-shot and open-vocabulary multi-label classification.

- The proposed SLAN approach need to solve multiple optimization problems, which may not scale well to large datasets.
questions: questions: - There are existing tasks with similar settings. For example, in image tasks, there are zero-shot multi-label classification, and open vocabulary multi-label classification. What's the difference between the proposed task and these tasks? Is the setting more applicable?

- It would be better if the paper can include state-of-the-art methods for zero-shot and open-vocabulary multi-label classification in the experimental comparison.

- It would be better to include a flowchart outlining the key step in the proposed approach, which can improve the clarity and make it easier to follow.
limitations: limitations: The limitation and societal impact is addressed.

Comments: title: Thanks
Looking forward to your feedback
Looking forward to your feedback
Looking forward to your feedback
comment: Thank you again for the valuable comments. We will check the manuscript again and add the discussion in the revised version.
The author has addressed most of my concerns and the score is updated.
Dear Reviewer zY3w, thanks for your thoughtful comments. Following your suggestions, we conducted additional experiments regarding parameter sensitivity analysis across different datasets. We would appreciate your thoughts on our response. Please let us know if there is anything else we can do to address your comments.
Dear Reviewer wpso, thanks for your thoughtful comments. We believe we have addressed your concerns in our response, including clarifying the difference between the proposed task and zero-shot multi-label classification/open vocabulary multi-label classification, and providing a flowchart for the proposed approach. We would appreciate your thoughts on our response. If you have any remaining or further questions for us to address, we are keen to take the opportunity to do so before the discussion period closes. Thank you!
Dear Reviewer vnjs, thanks for your thoughtful comments. We believe we have addressed your concerns in our response. We would appreciate your thoughts on our response. Please let us know if there are any further suggestions on how we can improve to address your comments effectively.