Progressive Label Propagation for Semi-Supervised Multi-Dimensional Classification

1 Introduction

In supervised learning, one traditional task is to learn a model under the supervision of one single class variable, e.g., multiclass classification. However, the simplifying assumption does not fit well in many real-world applications because some objects with rich semantics should be classified along different dimensions. For instance, a piece of song can be classified from emotion dimension (with possible labels happy, sad, cathartic, etc.), from the scenario dimension (with possible labels walk, wedding, nightclub, etc.), and from the language dimension (with possible labels English, Chinese, Spanish, etc.). To build classification models for such kind of problems, the multi-dimensional classification (MDC) framework [Read et al., 2014a; Cambu´ı et al., 2021] is a more natural solution which associates multiple class variables to the object. Here, each class variable corresponds to one specific class space which is used to characterize the object's semantics from one dimension. In fact, the needs of learning from objects with multi-dimensional semantics widely exist in diverse application scenarios, such as text mining [Shatkay et al., 2008], computer vision [Lian et al., 2020], bioinformatics [Borchani et al., 2013].

∗Corresponding author

The MDC problem can be solved via learning a multi-class classifier for each dimension. However, this independent decomposition strategy ignores the dependencies among different class spaces, which might lead to performance degeneration. Thus, most existing approaches aim at modeling the class dependencies in either explicit ways [Bielza et al., 2011; Read et al., 2014b; Arias et al., 2016] or implicit ways [Zhang et al., 2022]. It is worth noting that a common assumption for these works is that there are enough labeled MDC samples available for model induction, while it is rather costly to annotate the semantics of objects from several dimensions. To reduce the labeling cost, this paper investigates the feasibility of learning from a few labeled MDC samples with the help of a large number of unlabeled data, which formalizes the framework semi-supervised multi-dimensional classification (SSMDC). As a mixture of MDC and semi-supervised learning, both class dependencies and unlabeled data should be carefully utilized when designing SSMDC approaches.

In this paper, we propose a novel approach named PLAP (i.e., Progressive LAbel Propagation) to solve the SSMDC problem. Specifically, to utilize the unlabeled data, PLAP propagates the labeling information from labeled samples to unlabeled data via constructing a weighted directed graph. To utilize the class dependencies, PLAP progressively deals with each class space where the current propagation procedure will be initialized by the previous propagation results. To evaluate PLAP's effectiveness, we construct SSMDC testbed with ten real-world MDC data sets and compare PLAP with its degenerated version which deals with each class space independently via label propagation as well as six state-of-the-art MDC approaches which only use labeled MDC samples to induce supervised models. Experimental results clearly show that PLAP achieves superior performance against both its degenerated version and existing MDC approaches. To the best of our knowledge, this paper makes the first attempt towards studying the MDC problem in data utilization level and is different from existing works which are in method design level.

The rest of this paper is organized as follows. Firstly, the related works on MDC are briefly discussed in Section 2. Then, the technical details of the proposed PLAP approach are presented in Section 3. After that, the experimental results of comparative studies are reported in Section 4. Finally, we conclude this paper in Section 5.

2 RelatedWork

Multi-class classification (MCC) and multi-label classification (MLC) are the two most related frameworks to MDC. Specifically, MCC can be regarded as a special case of MDC where the number of dimensions is one (i.e., single dimensional classification), while MLC [Zhang and Zhou, 2014; Gibaja and Ventura, 2015; Liu et al., 2022] can also be regarded as a special case of MDC where the number of class labels in each dimension is two. Conceptually, both MCC and MLC assume one homogeneous class space while MDC assumes multiple heterogeneous class spaces in output space. Compared with MCC, MLC no longer restricts single relevant label for each instance to model ambiguous objects in a better way, while MDC employs multiple class spaces to model the multi-dimensional semantics of objects more conveniently.

The MDC problem can be solved by decomposing it into multiple independent MCC problems, one per dimension, which is usually termed as binary relevance (BR). However, BR doesn't consider potential class dependencies which should be utilized for model induction. According to the different ways of modeling class dependencies, existing works can be roughly categorized into explicitly and implicitly modeling methods. The first category aims at explicitly modeling class dependencies with some structures. Representative approaches include the family of multi-dimensional Bayesian classifiers which assume directed acyclic graph over class spaces [Gil-Begue et al., 2021], the family of classifier chains which learn a chain of classifiers where the labeling information for preceding classifiers on the chain will be used as features for subsequent classifiers [Zaragoza et al., 2011; Jia and Zhang, 2022a], the family of two-level methods which consider low-order and high-order dependencies in the frst and second level respectively [Arias et al., 2016; Jia and Zhang, 2020b; Jia and Zhang, 2021a].

The second category aims at implicitly modeling class dependencies via manipulating either feature or output space. For manipulating feature space, KRAM generates kNNaugmented features to enrich the original feature space which can facilitate subsequent model induction [Jia and Zhang, 2020a], and the following works LEFA [Wang et al., 2020] and SFAM [Jia and Zhang, 2022b] respectively improve the generation and utilization of augmented features. For manipulating output space, MLKT [Ma and Chen, 2018] and SLEM [Jia and Zhang, 2021b] transform the original categorical output space into a binary and real-valued one and then induce the predictive model in their transformed label space.

All the above approaches work by assuming enough labeled MDC samples available for model induction. However, it is rather costly to collect labeled MDC samples which have to be annotated from different dimensions. Semi-supervised learning [van Engelen and Hoos, 2020] aims at learning supervised models with a few labeled samples as well as a large number of unlabeled data and then reducing the need of labeled samples. To utilize unlabeled data, label propagation [Zhou et al., 2003] is one of commonly-used techniques which aims at making similar instances have similar labeling information. In the next section, we will present the technical details of the proposed PLAP approach which learns from a few labeled MDC samples as well as a large number of unlabeled data via progressive label propagation.

3 The PLAP Approach

Let X = Rd be the d-dimensional input (feature) space and Y = C1 × C2 × · · · × Cq be the output space which corresponds to the Cartesian product of q class spaces. Here, each class space Cj consists of Kj class labels, i.e., Cj = {cj1 , cj2 , . . . , cjKj } (1 ≤ j ≤ q). Given a set of labeled MDC samples Dl = {(xi, yi) | 1 ≤ i ≤ L}, for each labeled MDC sample (xi, yi), yi = [yi1, yi2, . . . , yiq]⊤ ∈ Y is the groundtruth class vector of xi ∈ X where yij ∈ Cj corresponds to xi's class label in the j-th dimension. Furthermore, given a set of unlabeled samples Du = {xj | L+1 ≤ j ≤ L+U}, the task of SSMDC is to induce a predictive model f : X ↦→ Y from D = Dl ∪Du. Generally, it is assumed that L ≪ U and we further denote N = L + U for convenience.

To propagate the labeling information from labeled samples Dl to unlabeled data Du, PLAP constructs a weighted directed graph G = (V, E). Here, the vertex set V corresponds to the instances in Dl ∪Du, i.e., V = {x1, . . . , xL, . . . , xN}, while the edge set E corresponds to the affinity matrix W ∈ RN×N defined based on the Gaussian function:

where Wij is the (i, j)-th item of W and σ is the bandwidth parameter of Gaussian function. Based on W, PLAP further constructs the propagation matrix S = D- 12WD- 12 where D = diag(d1, d2, . . . , dN) is a diagonal matrix with di = ∑Nj=1 Wij . With the propagation matrix S, PLAP conducts label propagation procedure via the following iterative equation [Zhou et al., 2003]:

Here, Y is the initial label matrix, F(t) is the propagated label matrix in the t-th round (t ∈ {1, 2, . . .}), and α ∈ (0, 1) is a hyper-parameter to be specified for balancing the importance of SF(t) and Y. Besides, F(0) is usually initialized as Y for the first iteration. In this paper, PLAP progressively deals with each class space, the definitions of Y and the corresponding F are different for different class spaces.

To consider the first class space C1, the current Y ∈ {0, 1}N×K1 is set as follows:

where Yia is the (i, a)-th item of Y. In other words, Yia is set to 1 only for labeled sample xi (i.e., 1 ≤ i ≤ L) if its class label w.r.t. C1 is c1a (i.e., yi1 = c1a ) and 0 otherwise. With Y, we can obtain the final F ∈ RN×K1 via iterating Eq.(2) until convergence. Let Fia denote the (i, a)-th item of F, the class label ˆ yi1 of unlabeled sample xi (L + 1 ≤ i ≤ N) w.r.t. C1 can be obtained via the following rule:

Then, to consider the second class space C2 and model the dependencies among C1 and C2, we deal with the first two class spaces as an entirety. Moreover, the previous predictions w.r.t. C1 for unlabeled samples will also be used to determine the current Y in Eq.(2). Specifically, let ϕ2(a1, a2) be some injective function from the Cartesian product {1, 2, . . . ,K1} × {1, 2, . . . ,K2} to natural numbers {1, 2, . . . ,K1 × K2} and we denote K12 = K1 × K2 for convenience. To determine the current Y ∈ {0, 1}N×K12 , consider the two cases as follows:

1. For labeled sample xi (1 ≤ i ≤ L):

where CL2i ≜ (yi1 = c1a1 )∧(yi2 = c2a2 ). In other words, the corresponding item Yiϕ2(a1,a2) for labeled sample xi is directly determined by its class labels yi1 and yi2 w.r.t. C1 and C2.

1. For unlabeled sample xi (L + 1 ≤ i ≤ N), the class label w.r.t. C1 has already been predicted in the previous label propagation step while the class label w.r.t. C2 is to be determined. Let N(xi) be xi's k nearest neighbors identified in labeled samples Dl, and n2ia2 be the number of samples with class label c2a2 w.r.t. C2 in N(xi), it is easy to know that ∑K2 a2=1 n2ia2 = k. Suppose xi is predicted as c1ˆa1 w.r.t. C1, we set Y as:

where CU2i ≜ (a1 = ˆa1) and 1 ≤ a2 ≤ K2.

To facilitate understanding, here is an example:

Example 1. Suppose that the output space of D is Y = C1 × C2 where C1 = {c11 , c12 }, C2 = {c21 , c22 , c23 }. Given the MDC data set D = {(x1, y1), (x2, y2), (x3, y3)}∪{x4, x5}, where y1 = [c11 , c22 ]⊤, y2 = [c12 , c23 ]⊤ and y3 = [c11 , c21 ]⊤. Let k = 2 and suppose N(x4) = {x2, x3}, N(x5) = {x1, x3}, then n241 = 1, n242 = 0, n243 = 1 because there is respectively one sample with c21 (i.e., x3) and c23 (i.e., x2) w.r.t. C2 in N(x4), and n251 = 1, n252 = 1, n253 = 0 because there is respectively one sample with c21 (i.e., x3) and c22 (i.e., x1) w.r.t. C2 in N(x5). Moreover, suppose the predicted class labels w.r.t. C1 in the previous label propagation step for unlabeled samples x4, x5 are ˆ y41 = c11 , ˆ y51 = c12 , given the injective function ϕ2(a1, a2) = 3 × (a1 - 1) + a2, Y is set as:

Here, in the 1st row, Y12 = 1 because y1 = [c11 , c22 ]⊤ and ϕ2(1, 2) = 3 × (1 - 1) + 2 = 2. In the 2nd row, Y26 = 1 because y2 = [c12 , c23 ]⊤ and ϕ2(2, 3) = 3×(2-1)+3 = 6. In the 3rd row, Y31 = 1 because y3 = [c11 , c21 ]⊤ and ϕ2(1, 1) = 1×(1-1)+1 = 1; In the 4th row, given ˆ y41 = c11 (i.e., a1 =

1), Y41 = n241 k = 12 because ϕ2(1, 1) = 1, Y42 = n242 k = 0 because ϕ2(1, 2) = 2, Y43 = n243 k = 12 because ϕ2(1, 3) = 3; In the 5th row, given ˆ y51 = c12 (i.e., a1 = 2), Y51 = n251 k = 12 because ϕ2(2, 1) = 4, Y52 = n252 k = 12 because ϕ2(2, 2) = 5, Y53 = n253 k = 0 because ϕ2(2, 3) = 6.

With the Y determined by Eq.(5) and Eq.(6), we can also obtain the corresponding F ∈ RN×K12 via iterating Eq.(2) until convergence. For unlabeled sample xi (L+1 ≤ i ≤ N), its class labels w.r.t. C1 and C2 can be determined via the following rule:

where ϕ-1 2 (·) is the corresponding inverse function of ϕ2(·, ·). Furthermore, we can generalize above propagation procedure to the j-th class space (j ≥ 2). Specifically, we deal with the first three class spaces as an entirety and define injective function ϕj(a1, . . . , aj) which maps the Cartesian product {1, 2, . . . ,K1}×. . .×{1, 2, . . . ,Kj} to natural numbers {1, 2, . . . ,K1 × . . . ×Kj}. To determine the corresponding Y, Eq.(5) will be generalized as follows:

where CLji ≜ (yi1 = c1a1 ) ∧ . . . ∧ (yij = cjaj ). Eq.(6) will be generalized as follows:

where CUji ≜ (a1 = ˆa1) ∧ . . . ∧ (aj-1 = ˆaj-1). njiaj denotes the number of samples with class label cjaj w.r.t. Cj in N(xi) and xi is respectively predicted as c1ˆa1 , . . . , cj-1 ˆaj-1 w.r.t. C1, . . . , Cj-1 in the previous label propagation step. For unlabeled sample xi (L + 1 ≤ i ≤ N), its class labels w.r.t. C1, . . . , Cj can be determined with the help of the inverse function of ϕj(a1, . . . , aj) like Eq.(7).

(a) Hamming Score

(b) Exact Match

(c) Sub-Exact Match

4 Experiments

4.1 Experimental Setting

Data Sets

In this paper, we use ten real-world MDC data sets for experimental studies where Table 1 summarizes their basic characteristics, including the number of examples (#Exam.), the number of class spaces (#Dim.), and the number of features (#Feat.). For each data set, we randomly sample 40, 50 and 60 examples to form the labeled data set Dl while the remaining examples are used to form the unlabeled data set Du. The sampling procedure is repeated ten times, and the mean metric values as well as standard deviations are recorded.

Evaluation Metrics

In this paper, we consider three commonly used metrics for performance evaluation, namely hamming score (a.k.a. global accuracy [Bielza et al., 2011]), exact match (a.k.a. example accuracy [Read et al., 2014a]) and sub-exact match [Jia and Zhang, 2020a]. Given the test set S = {(xi, yi) | 1 ≤ i ≤ p} and the MDC model f to be evaluated, the definitions of these three evaluation metrics are given as follows:

1. Hamming Score:

(a) Hamming Score

(b) Exact Match

(c) Sub-Exact Match

2. Exact Match:

3. Sub-Exact Match:

Here, r(i) = ∑qj=1 �yij = ˆ yij� denotes the number of class spaces which are predicted correctly, yij and ˆ yij denote the ground-truth and predicted label w.r.t. the j-th class space for the i-th test sample, �π� returns 1 if π holds and 0 otherwise.

Compared Approaches

As the first attempt towards solving the SSMDC problem, there are not existing SSMDC works to be used as comparing approaches. Thus, we mainly compare the proposed PLAP approach with existing MDC approaches. In this paper, a total of six well-established MDC approaches are used, including BR, CC, SLEM, KRAMd, KRAMc, MDKNN. Specifically, BR solves the MDC problem via learning a multi-class classifier for each dimension. CC [Jia and Zhang, 2022a] solves the MDC problem via learning a chain of multi-class classifiers, one per dimension. SLEM [Jia and Zhang, 2021b] transforms the MDC problem into a multi-output regression problem via spare label encoding. Both KRAMd and KRAMc [Jia and Zhang, 2020a] consider class dependencies via kNN feature

(a) Hamming Score

(b) Exact Match

(c) Sub-Exact Match

augmentation, where the former only generates discrete kNN statistics while the latter further generates continuous kNN statistics. MDKNN [Jia and Zhang, 2021a] solves the MDC problem via instance-based learning techniques where class dependencies are considered in a two-level strategy. Moreover, we further compare the proposed PLAP approach with its own degenerated version (denoted as PLAPd) which independently deals with each class space the same as PLAP deals with the first class space.

Note that the six MDC approaches train their models only over labeled MDC samples Dl while PLAP and PLAPd train their models over both labeled MDC samples Dl and unlabeled data Du. For the six MDC approaches, the suggested parameters in their respective literature are used. For PLAP and PLAPd, the bandwidth parameter in Eq.(1) is fixed as 50, the trade-off parameter α in Eq.(2) is fixed as 0.99, and the number of nearest neighbors k in Eq.(6) is fixed as 7.

4.2 Experimental Results

The detailed experimental results are reported in Tables 2-4. Moreover, pairwise t-test [Demˇsar, 2006] at 0.05 significance level is conducted to show whether PLAP achieves significantly superior/inferior performance against other comparing approaches on each data set. Accordingly, the resulting win/tie/loss counts are summarized in Table 5.

According to the reported experimental results, we can make the following observations:

• With 40, 50 and 60 labeled samples, PLAP respectively achieves superior or at least comparable performance against the seven comparing approaches in 203, 203 and 204 cases across all the 210 configurations (10 data sets × 3 metrics × 7 comparing approaches).
• PLAPd independently deals with each dimension via label propagation. It is shown that PLAP achieves superior or at least comparable performance against PLAPd in 91.1% cases which clearly validates the benefits of modeling class dependencies in PLAP.
• BR, CC, SLEM, KRAMd, KRAMc and MDKNN train their models only over labeled MDC samples Dl. It is worth noting that PLAP achieves superior or at least comparable performance against these six approaches in
• 98.9%, 98.9%, 92.2%, 92.2% and 100.0% cases, respectively. These experimental results clearly validate the benefits of utilizing unlabeled data in PLAP.
• For WQpla., WQani., WQ and BeLaE, it is shown that PLAP usually achieves comparable performance against PLAPd. Possible reason is that the class dependencies in these MDC tasks are very weak. For example, there are 989 distinct class combinations appearing within the 1060 examples for WQ which also supports our conjecture to some extent.

4.3 Parameter Sensitivity Analysis

In the progressive label propagation procedure, for the current class space (except for the first one), PLAP utilizes the propagation results for previous class spaces to initialize the value of Y for unlabeled samples. Specifically, PLAP estimates the probability of several possible items in Y which are filtered by the predicted labels in previous label propagation via k nearest neighbors.

Figure 1 shows how the performance of PLAP fluctuates with different values of k. It is shown that PLAP achieves relatively stable performance when the value of k increases from 5 to 10. In this paper, the value of k is moderately set to 7 which can be used as the default parameter setting.

5 Conclusion

The major contributions of our work are two-fold: 1) Different from existing MDC works which aim at designing novel MDC approaches by assuming that enough labeled samples are available, we investigated the SSMDC problem which aims at utilizing unlabeled data to help induce MDC models with a few labeled samples and then labeling costs can be reduced. 2) We proposed a SSMDC approach named PLAP which can utilize both class dependencies and unlabeled data via progressive label propagation. Experiments clearly validate the effectiveness of the proposed PLAP approach.

PLAP works in the transductive learning schema where the test samples are exactly the unlabeled samples (i.e., closedworld assumption). In the future, it is interesting to further design SSMDC approaches working under open-world assumption [Zhou, 2022; Parmar et al., 2023] where the test samples are completely unavailable to model training.

Acknowledgements

The authors wish to thank the anonymous reviewers for their helpful comments and suggestions. This work was supported by the National Science Foundation of China (62225602). We thank the Big Data Center of Southeast University for providing the facility support on the numerical calculations in this paper.