SEAL: Simultaneous Label Hierarchy Exploration And Learning
Authors: Zhiquan Tan
Zihao Wang
Yifan Zhang
Venue: Accepted by TMLR ()

Abstract: Label hierarchy is an important source of external knowledge that can enhance classification performance. However, most existing methods rely on predefined label hierarchies that may not match the data distribution. To address this issue, we propose Simultaneous label hierarchy Exploration And Learning (SEAL), a new framework that explores the label hierarchy by augmenting the observed labels with latent labels that follow a prior hierarchical structure. Our approach uses a 1-Wasserstein metric over the tree metric space as an objective function, which enables us to simultaneously learn a data-driven label hierarchy and perform (semi-)supervised learning. We evaluate our method on several standard benchmarks and show that it achieves improved results in semi-supervised image classification scenarios.

Published in Transactions on Machine Learning Research (07/2024)
SEAL: Simultaneous Label Hierarchy Exploration And Learning
Zhiquan Tan"
tonag @mails wasmmmllliinguuaeee...
Deportment of Mathematical Sciences Tsinghua University
Zihao Wang"
zwanggeBes...ss..tk
Deportment CSE
HKUST
Yifan Zhang*
zhangyif21 Cmails Isinguua edu.cn
1118 Tsinghua University
Reviewed on OpenReview: https: openreview. net/
net/ forum? id- JZVGDTNA55
Abstract
Label hierarchy is an important source of external knowledge that can enhance classifica- tion performance. However, most existing methods rely on predefined label hierarchics that may not match the data distribution. To address this issue, we propose Simultaneous label hierarchy Exploration And Learning (SEAL), new framework that explores the label hi- erarchy by augmenting the observed labels with latent labels that follow a prior hierarchical structure. Our approach uses 1-Wasserstcin metric over the tree metric space an ob- jective function, which enables us to simultaneously learn dala-driven label hierarchy and perform (semi- Jupperisde learning. We evaluate our method on several standard bench- marks and show that achioves improved results in somi-supervised image classification scenarios.
1 Introduction
Labels play crucial role machine learning. They provide the supervision signal for learning models from annotated data. However, obtaining label annotations is often costly and time-consuming, which motivates the study of semi-supervised learning that leverages both labeled and unlabeled data (Chen et al., 2020; Assran et al., 2021; Wang et al., 2021a). A common technique for semi-supervised learning is also related to the label, specifically, using (pseudo=)labels (Berthelot et al., 2019b; Sohn et al., 2020; Gong et al., 2021). Unlabeled data is augmented in different ways (Xie et al., 2020), and pseudo labels are then generated from model predictions for different augmentations of the same data. The model updated by enforcing the consistency of pseudo labels across augmentations. This technique is known as "consistency regularization" (Rasmus et al., 2015b).
Labels are also imporlant for understanding data, as they link real-world observations with abstract seman- tics. It has been shown that exploiting hierarchical structures of label semantics can enhance the performance of supervised and semi-supervised learning. These structures can be obtained from external sources such as decision trees (Wan et al., 2020) and knowledge graphs (Miller, 1998; Speer et al., 2017). Once the la- bel hierarchy is available, models can be trained by either (1) predicting hierarchical semantic embeddings jointly with labels (Deng et al., 2010; 2012; Barz & Denzler, 2019; Liu et al., 2020; Wang et al., 2021b; Karthik et al., 2021; Nassar et al., 2021) or (2) optimizing hicrarchical objective functions that incorporate
"Equal contribution

---

Published in Transactions on Machine Learning Research (07 2024)
Pseudo-label
Weakly Augmented
dog
dog 12
Backbone Model
Cross Entropy
P2
SEAL Regularizatio
Strongly Augmented
Extend Latent Label
cat dog
Pseudo-laber Prediction
Figure 1: An illustration of the SEAL framework. After getting the prodicted probability of weakly aug- mented image observed labels, the model shall use any pseudo-labeling techniques to give it a pseudo-label. Then the cross entropy loss between the pseudo label and predicted probability on the image will comprise part of the SEAL regularization. Given a (soft) tree hierarchy can introduce the latent labels. Extending the predicted probability on strong-augmented image and pseudo label to total labels will give a SEAL regularization loss which is another part of the SEAL regularization. Note that the backbone model and the SEAL regularization model (label hierarchies) can be updated via gradient descent simulta- ncously.
label relations (Bertinetto et al., 2020; Bilal et al., 2017; Garnot & Landrieu, 2020; Garg et al., 2022b). Alternatively, the structure can also be incorporated into the model architecture itself (Kontschieder et al., 2015; Wu et al., 2016; Wan et al., 2020; Chang et al., 2021; Garg et. al., 2022a).
Although predefined label hierarchies are frequently used in the existing literature, they cannot always match the actual data distribution. However, not much effort has been made to derive the label hicrarchy from a data-driven perspective. To address this issue, we propose Simultaneous label hierarchy Exploration And Learning (SEAL), which achieves goals by incorporating additional regularization term.
The first goal of SEAL is to identify the data-driven label hierarchy. This goal differs from hierarchical clustering, which discovers hierarchical structures from data that do not align with labels. SEAL expands the label set by adding unobserved latent labels to the observed labol set. The data-driven label hicrarchy is modeled by combining the predefined hierarchical structure latent labels with the optimizable assignment between observed and latent labels. The observation that inspires this approach is that the labels are typically subset of concepts in larger knowledge graph (Miller, 1998).
The second goal of SEAL is to improve the classification performance of state-of-the-art methods. To accomplish this goal, we propose new regularization term that uses the model predictions and the label annotations on the observed label set to encourage agreement on both observed and latent label set. The confidence on lotent labels is estimated by simulating the Markov chain based on the label hicrarchy between observed and latent labels. This regularization term can be added all existing approaches because of the universality of comparing the prediction and labels on the observed label set. A diagram of SEAL is shown in Figure 1.
SEAL's soundness and effectiveness are validated theoretically and empirically. The regularization term can be interpreted as a relaxation of the tree Wasserstein metric (Le et al., 2019), and it can be used for optimization. Empirical evaluation demonstrates that adding the SEAL framework consistently and significantly improves the classification performance on supervised learning and various semi-supervised learning methods (Sohn al., 2020; Zhang et al., 2021; Wang et al., 2022a). SEAL also achieved new state-of -att--ofthheart for semi-supervised learning on standard datasets. Additionally, our case study shows that the alignment between observed and latent labels also yields meaningful label hierarchy.
2

---

Published in Transactions on Machine Learning Research (07 (07/2024)
2
Background
In this section, we introduce the notations used throughout this paper first and then define the Tree- Wasserstein distance, which we use to define label hierarchy metrics in Section 3.
2.1 Notations
We consider supervised learning, where D = (( wi) is the labeled training set. Here, æ; is an image, and is the corresponding (class) label in a set O, where 1O = K. Without further justification, is the categorical label, and 6y is the onc-hot label. Our goal is to learn a backbone model fo parameterized by 0, which maps each image æ; to a probability over O. We denote the predicted probability vector image x as fo()) and define the pseudo label æ as = argmax, f(x))",, = argmax, Pr(j]æ), where ej is the coordinate vector. The objective of supervised learning is to make the ground truth label y and pseudo label consistent.
We also consider semi-supervised learning, where an additional unlabeled dataset D is provided. During training, we define the relative ratio as the number of unlabeled data to labeled data in a mini-batch. Following RandAngment (Cubuk et al., 2020), we shall define weak augmentation PwAug(2)) and strong augmentation (ar) These two augmentations are probability distributions of the views of derived by argumentation while keeping the same pscudo label, the terms weak and strong describe the distortion density. Moreover, x' and x" denote the argument data and y' denotes the pseudo-label.
2.2 Tree- iiee-rasserstein distance
The Tree- Wasserstein distance (Le al., 2019) is a 1-Wasserstein metric (Peyré et al., 2019) on tree metric space (X, w)) where X' is the node set of directed rooted tree, E is the (weighted) edge set, and (We)eEE denotes the weights of edges e E E. The tree metric dx between any two nodes of tree is defined the length of the shortest path between them. Given node X, let [(v) be the set of nodes in the subtree of X whose root node is v. For each weighted edge e E E, we denote the deeper (away from the root) level endpoints of weighted edge e as Ve- Then, the Tree- Wasserstein metric can be computed in closed form, as shown in Theorem 1.
Theorem (Tree-Wassenn Wasserstein distance (Le et al., 2019)) Given two probability measures Jr, sup- ported on directed rooted tree X, and choosing the ground metric as tree metric dx, then the Wasserstein-L distance under Definition 4 can be reformulated as follows:
Wax (p,
Σ We (T - (( CE
(1)
3 The SEAL framework
We propose a novel framework called Simultaneous label hierarchy Exploration and Learning (SEAL), which is motivated by probabilistic models that leverage latent structures to improve classification performance. In the SEAL framework, we introduce lalent labels that are aligned with observed labels to capture the data-driven label hierarchy.
3.1 Why latent structure?
Let consider classifier that predicts the probability of an image belonging whether an image belongs to the "apple" or "paint" class. Although the two classes may seem unrelated, they may share some hidden structures, such as the colors "red" and "green". Knowing the conditional probabilities of colors given each class, we can calculate the probability of an image being red given its probability of belonging to the "apple" class. Suppose we know the conditional probabilities Pr(red] apple) 0.9, Pr(green) apple) 0.1, Pr( paintt) 0.5, and Pr(green/paint) 0.5. In this scenario, if the classifier assigns probability of 0.8 for an image being apple, the question arises as to what is the probability that this image is red. By
Example 1
3

---

Published in Transactions on Machine Learning Research (07 (022)
latent labels (red, green)
red
green
observed labels (apple, paint)
0.8
0.9
0.2 X-0.5
apple
paint
0.2
Figure 2: An illustrative example
applying the law of probabilily, the onswer is 0.8 0.9 0.2 x 0.5 0.82. For pictorial understanding, please see Figure 2.
3.2 Latent structure and SEAL regularization
The Example 1 illustrates that considering latent variables, such as color in this case, can provide more information to the classifier, leading to better performance. the context image classification, these latent variables can represent various factors, such as textures, shapes, and semantic meanings. However, identifying these latent variables and modeling their relationships with observed variables is not always straightforward, which is the focus of the SEAL framework.
Then we formally present the following definitions below. The set of labels O in the dataset is denoted observed label set. The set of latent labels L is denoted as latent label set. We call O L total label set. Let |0| = K and || N be the sizes of observed and total label alphabets. The relationship between observed and latent labels are described by (directed) graphs. Specifically, let A₁E (NN-K))(N-B) be the adjacency malrix for latent labels The adjacency matrix A for C O characterizes the latent structure, assume the latent labels have index orders less than observed labels in the adjacency matrix, will have
and A₂E R(N-K)*K be the connection matrix between and O.
A A2 0 )
(2)
It assumed that no connection exists inside O. SEAL is targeted to discover the hicrarchical structure of labels, therefore, additional assumptions are imposed on matrix A. The key assumption of A follows the following thcorem.
Theorem (Taakozawa et al., 2021)) Suppose a directed graph G having a total of nodes, which we denote as (V1, ..., uy). If the adjacency matria A E (0,1) NxN of this gruph salisfies the following conditions:
1. A is strictly upper triangular matrir.
AT (0.1. ...1....111.
then G is directed rooted tree with in the root and NN is all-one vector.
4

---

Published in Transactions on Machine Learning Research (07/2024)
The hierarchical structure of observed labels is then described by the graph defined by A, satisfying conditions in Theorem 2.
We introduce a weight matrix a = [aarlarr E R(N-K)x that describes the connection from E L to r E O to further quantify how much an observed label contributes to a latent label. SEAL extension is then defined by a five-tuple (O, C, A1, A2; a). We note that a should be related the A₂ and its specific formulation will be detailed in the following parts. Then, we are able extend the model's prediction on the observed label set O to the total label set.
Definition 1 (Total prediction and total target) Let p be probability veclor on O and pr be the prob- ability of the label r O, vector on total label set O OUUR L is
[Pr [a(p)s (rroo CsrPr
i
(3)
if
where s E O.L. Given a sample of imput and (pseudo-Nabel (x, (x,y), we note that the pr could derived by both the model prediction fo fo(x), the one-hot label oμ, or the pseudo-label by. Moreover, g(fo(x)) is the total prediction while ((0)) denoted as the total target.
We note that q is not the probability in any case, since it extends the original probability p over O by further considering the aggregations over L. However, it is also sufficient to define objective functions to minimize the differences between total prediction and total target, which is SEAL regularization.
Definition 2 (SEAL regularization) Given imput x, target y, model fo, and SEAL extension A1, the SEAL regularization is defined as ((f((x), = D(a(fa(z)), where D is distance function.
In this paper, we consider SEAL regularization where D the weighted & metric:
((fo(z),6,) D(g(fo(z))) = Σ w.llo(fo(z)))= - [g(8,)1=l
(4)
SEOUC
where w, is the weight for each observed or latent label.
We have presented the basic framework of SEAL, then we detail how SEAL is used to explore label hierarchy and improve learning in the next parts.
3.3 Label Hierarchy Exploration with SEAL
In this section, we explore the label hicrarchy under the SEAL extension (O, A1, A2, a). To achieve this, we first specify L, A1, A2, and a, which breakdowns into two tasks. The first task is to specify L and A₁ to define the prior structure inside C, while the second task is to specify how a and A2 are related to defining how the structure is optimized.
Task (a): Prior Structure Specification. To specify the prior structure inside L, we choose A₁ to be binary tree trees derived from prior knowledge such as part of knowledge graph decision tree. This choice of A₁ allows us to control the prior structure of the label hicrarchy and incorporate prior domain knowledge. Additionally, we can use the hierarchical structure of A to guide the training of the model to improve performance.
Task (b): Structure Optimization Specification. To specify how a and A2 are related to defining how the structure is optimized, we note that and Ag both reflect how the structure interacts with the model and data. Specifically, we compute from A₂ from the Markov chain on trees. This choice of a emphasizes more on the prediction of the model while A, emphasizes more on the interpretation of the label hierarchy.
In summary, by specifying C, A₁, Ag, and a, we can explore the label hicrarchy under the SEAL extension (0, C, A2, a). This approach allows us to incorporate prior domain knowledge and guide the training of the model to improve performance while also providing framework for interpreting the label hierarchy.
5

---

Published in Transactions on Machine Learning Research (07 (07/2024)
Random Walk Construction of We observe that the matrix A satisfies the conditions in Theorem 2, and can be viewed as Markov transition matrix on L CUO that follows the top-down direction over a tree. Therefore, the probability of a random walk from node E L to a node r E O can be computed by simulating the Markov chain. We define aar to be the probability of random walks starting from s and ending at r, which can be interpreted as the probability that node r contained the subtree of node 8. Specifically, we have:
Σ
A
[I
A)
(5)
where I the identity matrix.
Morcover, we can further simplify the above equation by noting that (I-A)- can be procomputed. Specif- ically, we have: (I (I-
A1)-
0 (1)
I
This construction of a is based on the Markov chain on trees and has been applied in other applications such as document distance (Takezawa et al., 2021) and hicrarchical node clustering (Zügner et al., 2021). However, is the first time that this construction has been used train a deep neural network.
Optimizing SEAL regularization Once is defined explicitly through A2, the expression of SEAL regularization & is also well defined. It simplifics to
o(fo(z), = = (I- A1) A2 (fo(z)- - -8,))
I (I- (1-A111
(6)
where H denotes taking the element-wise absolute value. We set = 1x for simplicity.
One could jointly optimize and A₂ (or a). Particular attention should be paid to A since is discrete and required to satisfy the conditions in Theorem 2, making the optimization very hard. In this paper, we relax A2 E (0, (LNN-N)x to Agoft [0, 1a(1 One could employ projected gradient descent on each column of Agoh to ensure those conditions. More investigation on optimization can be found in Section 6.4.
For clarity, we denote the SEAL regularization (o) 6y), where the suffix O denotes the parameters defining latent hierarchy.
Interpreting SEAL results After Agoft is optimized, we can reconstruct A to interpret the explored label hicrarchy. Specifically
(A2) = { if = arg max ((A otherwise
(7)
Then the matrix A is derived after optimization.
3.4 Learning with SEAL
We have already defined SEAL regularization based on the model output fo(#)) and the larget y. Then it is natural to apply SEAL regularization to various learning scenarios.
We consider the learning process in typical mini-batch setting. Given batch of samples B C D, we consider the averaged summation & of SEAL regularization & over the batch.
(0, O B) = B
Σ
)e(fo(x),6g)
(8)
(x.y)EB
We note that o, could be the one-hot labels of the labeled data pseudo-labels unlabeled data.

---

Published in Transactions on Machine Learning Research (07 (224))
3.4.1 Semi- supervised learning with SEAL
Consider a general scheme (Gong et al., 2021) that unifies many prior semi-supervised algorithms. For the n + 1-th iteration, the model parameter derived based on supervised loss (( and a consistency regularization term V 0.))..) Specifically
Out1 +- arg min
(9)
where 6n denotes the model parameters at the n-th iteration and y is the loss balancing coefficient.
Adding SEAL to semi-supervised learning is no more than applying SEAL regularization an additional consistency regularization term apart from the initial (0; (0), which will be described below.
Usually speaking, the computation (0;; 8n) is conducted over a batch of unlabcled data B C D For cach sample a B"; the computation follows the following process:
Pseudo-label prediction on weak augmentation Computing the prediction of weakly- augmented image x' E (wAug(æ) with model fo, in the last iteration, which will be used to generate pseudo-labels in the next steps.
2. Strong augmentation For the input data we sample strong argumentation x" E (a)
3. Selection Some selection processes are applied to select the samples and assign them meaningful aaeudo-labels y's. This results in new pseudo-labeled dataset 3" == ((x",/))
Consistency regularization minimizes the differences between the prodiction by the model and the pscudo- label v', for example, prior works usually merely use the cross entropy as (0;0,))
T (O,0..)
1
Σ
(x"),
(10)
D"
(a"
B"
Adding SEAL regularization is simply adding another term Φ(0, @0 0, B²). Then, we obtain the updating rule of semi-supervised learning with SEAL:
0.+1 t arg min (0) +7 [V(0000)+
(11)
Many existing approaches (Sohn et al., 2020; Zhang et al., 2021; Wang et al., 2022a) fit into this paradigm. So SEAL can be applied easily to such approaches.
Summary for SEAL We have demonstrated how to plugin SEAL with supervised and semi-supervised learning equations (16) and (11), respectively. The key observation that SEAL regularization can be applied long there is an objective function between model prediction f(xx) and larget y.
4 Theoretical analysis of SEAL regularization
We find equation (6) has similar structure to that of Tree- Wree-Wasserttein distance, we shall first extend the definition of Pre-Wassernttin distance.
We shall first rewrite the Tree- Wasserstein distance's s summation using the node as indices. Note the lower endpoint of each edge has a one-to-one correspondence with each node, thus we can see the weight each edge as the weight of each node. Denote the tree as X' and leaf nodes as Meaf. We can rewrite the expression of Tree- Wasserstein distance into Wax (p,v) Ewex wy ((((e)) v(I(v))). When a and are supported only the leaf set, can rewrite [(v) using the ancestor-child relationship. That is,
Wax (1,
Σ wel Σ (m(x)-v(z)) is ancestor of x/- IEEuaa
(12)
7

---

Published in Transactions on Machine Learning Research (07 (07/2024)
If a directed graph has its adjacency matrix A satistying the conditions in Theorem 2 except relaxing the hard constraint {0, 1} to [0, we shall call it soft tree. Recall the subtree probabilistic interpretation of a in 3.3, we can define relaxed Sree-Waserrstein distance (RTW) as below.
Definition 3 (Relaxed Tree- Wasserstein distance) Assume X' is soft tree and denote the leaf nodes Kleaf. For any two probability meosures supported Kyeaf. The relaxed tree Wasserstein distance Wyelon V) is given as follows:
Waeter
Σ VEd xE
Σ We
Oux (1(x) u(x)))
(13)
If we let Heat be the set of observed labels O and X' be total labels OUL. We can then show the connection between the relaxed tree Wasserstein distance and the weighted total classification error given by equation (6).
Theorem The weighted total classification loss described by Eqn. (6) under Agoft coincides with Wyetow (fo(2)).g))
Proof 1 Please see Appendiz A.4.3.
5 Applying SEAL to semi- semi-supervised learning
6 Implementation details
6.0.1 Implementation of SEAL
Defining SEAL extension (0, C, A1, a2. For fair comparison and injecting no prior knowledge, A and Agoft are both randomly initialized. For CIFAR10 and STI-10, K = 10 and N = 21. For CIFAR100, K = -10 and N = 130. The experiments on large-scale datasets like ImageNet will be left as future work as they involve complex data-parallel mechanisms and may be difficult to perform the optimization of the algorithm. More ablations and details can be found in Section 6.4.1 and Appendix A.2.
Combining SEAL with other learning methods. The default setting of SEAL for semi-supervised learning is adopted from the same configuration and hyper-parameters used in FixMatch (Sohn et al., 2020). SEAL (Curriculum) adopts the curriculum pseudo-labeling technique and hyper-parameters used in FlexMatch (Zhang et al., 2021). SEAL (Debiased) adopts the debiasing trick and dyper-parameten used in DebiasPI. (Wang et al., 2022a). Note in experiments we only conduct SEAL Debiased on CIFAR 10 as the initial paper DebiasPL (Wang et al., 2022a) did not conduct experiments on CIFAR 100 and STL-10.
Optimizing with SEAL regularization. Specifically, we use (batch) stochastic gradient descent (SGD) optimizer with momentum of 0.9. We set the learning rate scheduler the cosine decay scheduler, where the learning rate 3 can be expressed as B Bocos 10.5) 5). Here, Po is the initial learning rate set to 0.03, is the current optimization slep, and S is the total number of optimization steps set to 220 We set the batch size of the labeled training data to 64, and the ratio of unlabeled training data to labeled data is set to 7. We set the threshold to 0.95, and the weak and strong augmentation functions used in our experiments are based on Augmentt (Cubuk et al., 2020). We use WideResNet-255 as the backbone model for our experiments. Also, SEAL improves standard supervised learning, details can be found A Appendix A.5.
6.1 Baselines
The baselines we consider in our experiments are those prior works similar to FixMatch, such as II-Model (Laine & Aila, 2016), Pscudo Label (Lee et al., 2013), Mean Teacher (Tarvainen Valpola, 2017), MixMatch (Berthelot al., 2019b), ReMixMatch (Berthelot al., 2019a), VAT (Miyato et al., 2018), UDA (Xie al., 2020), FlexMatch (Zhang et al., 2021)anm DebiasPI. (Wang al., 2022a). However, find that our proposed
8

---

Published in Transactions on Machine Learning Research (07/2024)
method SEAL is lightweight yet effective and outperforms all of these baselines all three datasets in nearly all settings.
Table 1: Error rates (100% accuracy) on CIFAR-10. bold means the best.
Dataset
CIFAR-10
# Label
40
250
II Model (Rasmus et al., 2015a)
1.734
46.24:1.29
Pseudo Label (Lee et al., 2013)
74.61 #0.26
46.19=2.20
VAT (Miyato al., 2018)
74.66+2.12
41.03:+1.79
Mean'Teacher (Tarvainen & Valpola, 2017)
7..09
37 303.30
MixMatch (Berthelot al., 2019b)
36.19:6.48
13.63=20.5
ReMixMatch (Berthelot et al., 2019a)
9.88=1.03
6.30=t0.05
UDA (Xie al., 2020)
10.62
5.16=40.66
FixMatch (Sohn et al., 2020)
7.47=0:28
5.07:20.05
Dash (Xu et al., 2021)
8.93=3.11
5.16220.23
MPL (Pham al., 2021)
6.93=0.17
5.76:20.2
FlexMatch (Zhang et al., 2021)
=.97
4.98
DebiasPI. (Wang al., 2022a)
5.40+ 1.30
5.60# 0.10
SEAL
6.29
4.43
SEAL (Curriculum)
4.90 0.09
4.92 0.04
SEAL (Debiased)
4.66 0.07
4.41 0.18
Table 2: Error rates (100% accuracy) CIFAR-10, CIFAR-100, and STL-10 dataset of state-of-the- methods for semi-supervised learning. bold means the best.
Dataset
CIFAR-100
STL-10
# Label
400
2500
40
250
Model (Rasmus al., 2015a)
80.96
58.8010.66
74.3110085
55.13
Pseudo Label (Lee et al., 2013)
87. 87.45+00.55
57.7 40.22
74.68=t0.9
55.45=2.43
VAT (Miyato et al., 2018)
85.20
46.8440.77
74.74
56.42=1197
Meahheacher (Tarvainen & Valpola, 2017)
81.11+1.44 1.44
45.17+
71.72+1.44
56.49-2.75
MixMatch (Berthelot et al., 2019b)
67.59
30.7610.44
54..93.1096
34.52200312
UDA (Xie et al., 2020)
46,39 d: 1.59
27. 27.23
37.4218.44
9.72
Dash (Xu al., 2021)
44.82+0.96
27.15++0.22
34.5244.30
MPL (Pham et al., 2021)
46.26 1.84
27.71=t011
35.76:24.83
9.90=20.66
FixMatch (Sohn et al., 2020)
46.42
28 10.03
35.97
9.8111.04
FlexMatch (Zhang et al., 2021)
39.9411.62
26.49:10.20
29.15:14.166
8.23
SEAL
484.84
26.99 40.23
33.27
9.77
SEAL (Curriculum)
39.73+1.68
26.39
16.15-2.60
7.92
6.2 Findings
SEAL is lightweight and effective. SEAL is easy to implement and with the aid of SEAL and its variants, we can achieve state-of-art results on all three datasets under all label amount settings. Results can be found in Tables 1 and 2.
The fewer labeled data, the more significant improvements. Interestingly, observe that the fewer labeled data available, the more significant gains we can achieve using SEAL. For instance, CIFAR10, we obtain a remarkable 7.52 accuracy gain with only 40 labeled data, while we only see a 0.64 accuracy gain with 250 labeled data. This finding highlights the effectiveness of our proposed method in situations where labeled data is scarce.
SEAL can be boosted by various techniques. Moreover, we demonstrate that our proposed method be further enhanced by incorporating various existing semi-supervised learning techniques, such

---

Published in Transactions on Machine Learning Research (07 (27/2
Curriculum Pseudo Label (Zhang al., 2021) and Debiased Pseudo Label (Wang al., 2022a), into SEAL framework with minimal effort. This implies that any future work on improving the quality of pseudo labels can be easily adapted into our SEAL framework.
1
rehicle
2
frog
4
5
horso
9
10
plane
bird
truck
Figure 3: A hierarchy of posterior tree structure
Meaningful posterior tree structure. We present a learned tree structure in Figure 3. We can find semantically close classes indeed close the tree. For example, animals cat, dog, and deer all child nodes of node 5.
6.3
Ablation Studies
In this section, we locus on analyzing the influence of different parameters on the performance of our proposed method, SEAL (Debiased), using the CIFAR10 dataset with only 40 labeled samples.
6.3.1
Different regularizer
0.95
0.94
0.93
accurayy
0.92
0.91
0.90
0.89
0.88
0.000
0.002
0.004
0.006
0.088
0.10
Figure 4: The influence of different hyper-parameter
Lastly, we explore the impact of the regularizer on classification accuracy by experimenting with different À values, including the case of = 0 to illustrate the necessity of the regularizer. As shown in Figure 4, when À approaches 0.003, the accuracy increases, while it decreases as À deviates from 0.003. Therefore, we conclude that the optimal value of À is around 0.003. We note that the accuracy drops significantly when À is too large, which may be attributed to the imbalance in loss scale.
6.4 Different updating rule for the adjacency matrix
Efficient updating of the soft adjacency matrix Ag is essential in the experiments. Two popular approaches have been used for updating A2. One approach is to consider each column of Ag the realization of softmax
10

---

Published in Transactions on Machine Learning Research (07/2024)
mapping. The other approach is to use projected gradient descent (PGD) to update the matrix, projecting each column onto the probability simplex. The classification accuracies of both methods are summarized in Table 3.
Table 3: Different methods for updating adjacency matrix
Update Method CIFAR10-40 labels
PGD
95.34
Softmax
86.46
It evident that PGD has a significant advantage over the softmax mapping-basse basudd approach. This obser- valion also reported in (Zügner el al., 2021). The poor performance of the softmax-based approach may be attributed to bad initialization, where the optimization is trapped by bad starting point.
6.4.1 Different tree structure
Table 4: Classification under different tree structure
Tree Name
Acc. on CIFAR10 (40 labels)
Without Tree
94.60
Trivial Tree
95.18
Random Tree
95.34
NBDT (Wan et al., 2020) Tree
95.39
Next, examine how the choice of tree structure affects the results. We compare three different trees: trivial tree with all 10 classes as leaf nodes besides one root node, randomly generated depth-4 tree with 21 nodes, and the NBDT tree proposed in (Wan et al., 2020), which has a well-designed hierarchy as shown in Figure 5. We use the adjacency matrix of the internal nodes induced subtree as the adjacency matrix A in our method for each tree.
The results of the classification accuracies under these different trees are presented Table 4. As we can see from the table, using tree structures consistently improves the classification accuracies compared to the vanilla cases. It is worth noting that the NBDT tree, which is carefully designed, achieves the highest accuracy, while our randomly generated tree performs better than the other cases.
deer
lace
mimmal
canrivene
chordaee
bird frog
whole
vertebrute
vehicle car muck
vehicle
aleplanc ship
creft
Figure 5: The hierarchy of NBDT Tree
11

---

Published in Transactions on Machine Learning Research (07/ (274))
7 Related Work
7.1
Semi-supervised Learning
Most cxisting methods for consistency regularization aim to improve the quality of the pscudo labels gener- ated from unlabeled data. For example, SimPLE (Hu et al., 2021) introduces a paired loss that minimizes the statistical distance between confident and similar pseudo labels. Dash (Xu et al., 2021) and Flex- Match (Zhang et al., 2021) propose dynamic and adaptive strategies for filtering out unrcliable pscudo labels during training. MaxMatch (Li et al., 2022) proposes a worst-case consistency regularization technique that minimizes the maximum inconsistency between original unlabeled sample and its multiple augmentations with theoretical guarantees. A notable exception is SemCo (Nassar et al., 2021), which leverages external label semantics to prevent the deterioration of pseudo-label quality for visually similar classes in a co-training framework.
Though proposed in different techniques, all these methods rely on a fixed objective function to define the consistency, which usually the cross-entropy over the label space. Our work differs from these methods by proposing novel way to extend the cross-entropy with latent labels and hierarchical structures. Therefore, our method can complement cxisting methods whenever cross-cntropy is used.
7.2 Label hierarchies
Label relationships are essential prior knowledge for improving model performance, and can be represented by semantic structures among labels. One prominent form of label structure is the label hierarchy (Garnot & Landrieu, 2020), which can be obtained from external sources like decision trees (Wan et al., 2020) and knowledge graphs (Miller, 1998; Speer et al., 2017). This information can be leveraged to train models as semantic embeddings (Deng et al., 2010; 2012; Barz & Denzler, 2019; Liu et al., 2020; Wang el al., 2021b; Karthik et al., 2021; Nassar et al., 2021) or objective functions (Bertinetto et al., 2020; Bilal et al., 2017; Garnot & Landrieu, 2020; Garg et al., 2022b). Additionally, the hierarchical information can also be incorporated as part of the model structure (Kontschieder al., 2015; Wu et al., 2016; Wan al., 2020; Chang et al., 2021; Garg et al., 2022a).
Pre-defined label hierarchies are widely acknowledged space in classification. This has been extensively discussed in the literature. The label hierarchy information can be used to improve the model training process, such as by embedding the hierarchical labels to maximize the similarity between the latent embedding of the input image and the embedding et al., 2010; Deng et al., 2012; Frome et al., 2013). This idea has been generalized to various embedding spaces (Barz& & Denzler, 2019; Liu et al., 2020; Garnot & Landrieu, 2020) and the joint learning scheme where image embeddings and label embeddings are both optimized (Wu et al., 2016; Chang et al., 2021). Additionally, hierarchical structures
essential source of prior knowledge for the label
its label (Bengio
also be explicitly used to make the training process hierarchical- aware (Deng et al., 2010; Bilal et al., 2017; Bertinetto et al., 2020; Karthik et al., 2021; Garg et al., 2022a;b). However, existing work typically treats the hierarchical label structure as prior knowledge. In contrast, our approach leverages the posterior latent label structures given the presence labcled and unlabeled samples.
8 Conclusion and Future Work
In this paper, we propose a framework SEAL to jointly train the model of high performances and the label structure of significance. The SEAL framework is flexible to be adapted to various learning schemes, and can even incorporate the prior structure given by the external knowledge and the information given by the data. Experinental results support the effectiveness of the SEAL framework. Theoretical understanding of SEAL via optimal transport theory is also discussed. Future works may include incorporating more complex prior knowledge applying the SEAL framework to self-supervised learning.
12

---

Published in Transactions on Machine Learning Research (07/ 2224))
References
Mahmoud Assran, Mathilde Caron, Ishan Misra, Piotr Bojanowski, Armand Joulin, Nicolas Ballas, and Michael Rabbat. Semi-supervised learning of visual features by con-maaaattr predicting view as- signments with support samples. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pp. 4443-8422 2021.
Björn Barz and Joachim Denzler. Hierarchy-based image embeddings for semantic image retrieval. In 2019
TEFE Winter Conference on Applications of Computer Vision (WACV), pp. (38-647, TEFE, 2019.
Samy Bengio, Jason Weston, and David Grangier. Label embedding trees for large multi-class tasks. Advances in Neural Information Processing Systems, 23, 2010.
Christian Berg, Jens Peter Reus Christensen, and Paul Ressel. Harmonic analysis on semigroups: theory of posilive definite and related functions, volume 100. Springer, 1984.
David Berthelot, Nicholas Carlini, Ekin D Cubuk, Alex Kurakin, Kibyuk Sohn, Han Zhang, and Colin Raffel. Remixmatch: Semi-supervised learning with distribution alignment and augmentation anchoring. arXiv preprint 1rXfv:1911.09985, 2019a.
David Berthelot, Nicholas Carlini, Tan Goodfellow, Nicolas Papernot, Avital Oliver, and Colin A Raffel. Mixmatch: A holistic approach semi-supervised lcarning. Advances neural information processing systems, 32, 2019b.
Luca Bertinctto, Romain Mueller, Konstantinos Tertikas, Sina Samangooci, and Nicholas A Lord. Mak- ing better mistakes:
Leveraging class hierarchies with deep networks. In Proceedings of the IEEE/CV /BE Conference Computer Vision and Pattern Recognition, pp. 12506-12515, 2020.
Alsallakh Bilal, Amin Jourabloo, Mao Ye, Xiaoming Liu, and Liu Ren. Do convolutional neural networks learn class hierarchy? IEEE transactions on visualization and computer graphics, 24(1):152-185 1121522-222221 2017.
Dongliang Chang, Kaiyue Pang, Yixiao Zheng, Zhanyu Ma, Yi-Zhe Song, and Jun Guo. Your" flamingo" is my' bird': Fine-grained, not. In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition, pp. 11476-11485, 2021.
Hao Chen, Ran Tao, Yue Fan, Yidong Wang, Jindong Wang, Bernt Schiele, Xing Xie, Bhiksha Raj, and Marios Savvides. Softmatch: Addressing the quantity-quality trade-off in semi-supervised learning. Inter- national Conference on Learning Representations (ICLR), 2023.
Ting Chen, Simon Kornblith, Kevin Swersky, Mohammad Norouzi, and Geoffrey E. Hinton. Big self- supervised models are strong semi-supervised learners. Advances in neural information processing systems, 33:22243 22255, 2020.
Adam Coates, Andrew Ng, and Honglak Lec. An analysis of lingle-layer networks in unsupervised feature learning. In Proceedings of the fourleenth international conference on artificial intelligence and statislics, pp. 215-222222 223. JMLR Workshop and Conference Proceedings, 2011.
Ekin D Cubuk, Barret Zoph, Jonathon Shlens, and Quoc V Le. Randaugment: Practical automated data augmentation with a reduced search space. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition workshops, pp. 702-703, 2020.
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large-scale hierarchical image database. In 2009 IEEE conference on computer vision and pottern recognition, pp. 248-255, Icee, 2009.
Jia Deng, Alexander C Borg, Kai Li, and Li Fei-Fei. What does classifying more than 10,000 image categories tell us? In European conference on computer vision, pp. 71-84. Springer, 2010.
Jia Deng, Jonathan Krauso, Alexander C Berg, and Li Fei-Fei. Hedging your bets: Optimizing accuracy- specificity trade-offs in large scale visual recognition. In 2012 IEEE Conference on Computer Vision and Pattern Recognition, pp.
TEFE, 2012.
13

---

Published in Transactions on Machine Learning Research (07/2024)
Andrea Frome, Greg S Corrado, Jon Shlens, Samy Bengio, Jeff Dean, Marc' Aurelio Ranzato, and Tomas Mikolov. Devise: A deep visual-semantic embedding model. Advances in neural information processing systems, 26, 2013.
Ashima Garg, Shaurya Bagga, Yashvardhan Singh, and Saket Anand. Hiermatch: Leveraging label hier- archies for improving semi-supervised learning. In Proceedings of the IEEE/CVE Winter Conference Ayplicalions of Compuler Vision, pp. 1015 1024, 2022a.
Ashima Garg, Depanshu Sani, and Saket Anand. Learning hicrarchy aware features for reducing mistake severily. arviv preprint Xrx::22207 12646, 2022b.
Vivien Sainte Fare Garnot and Loic Landrieu. Leveraging class hierarchies with metric-guided protolype learning. arXiv preprint arXiv:2007.030 03044, 2020.
Chengyue Gong, Dilin Wang, and Qiang Liu. Alphamatch: Improving consistency for semi-supervised learning with alpha-divergence. In Proccedings of the IEEE/CVF Conference on Computer Vision and Pallern Recognition, pp. 13683 13692, 2021.
Zijian Hu, Zhengyu Yang, Xucfeng Hu, and Ram Nevatia. Simple: similar pscudo label exploitation for semi- supervised classification. In Proceedings of the IEEE/CVE Conference on Computer Vision and Pattern Recognition, pp. 15099-15108, 2021.
Pranav Jeevan and Amit Sethi. Vision xformers: Efficient attention for image classification. arXiv preprint arXi::2107.0223) 2021.
Shyamgopal Karthik, Ameya Prabhu, Puneet K Dokania, and Vineet Gandhi. No cost likelihood manipula- tion at test time for making better mistakes in deep networks. arXiv preprint or arXiv:2104.00795, 2021.
Peter Kontschieder, Madalina Fiterau, Antonio Criminisi, and Samuel Rota Bulo. Deep neural decision forests. In Proceedings of the IEEE international conference on computer vision, pp. 1467-1475, 2015.
Alex Krizhevsky, Geoffrey Hinton, al. Learning multiple layers of features from tiny images. Citeseer, 2009.
Samuli Laine and Timo Aila. Temporal ensembling for semi-supervised learning. ar preprint arXiv:1610. 02242, 2016.
Tam Le, Makoto Yamada, Kenji Fukumizu, and Marco Cuturi. Tree-sliced variants of wasserstein distances. Advances in neural information processing systems, 32, 2019.
Dong-Hyun Lee et al. Pseudo-label: The simple and efficient semi-supervised learning method for deep neural networks. In Workshop challenges in representation learning, 1CML, volume pp. 896, 2013.
Muyang Li, Runze Wu, Haoyu Liu, Jun Yu, Xun Yang, Bo Han, and Tongliang Liu. Instant: Semi-supervised learning with instanco-dependent thresholds. Advances Neural Information Processing Systems, 36, 2024.
Yangbangyan Jiang Xiaodan Li, Yuefeng Chen, Yuan Hc, Qianqian Xu, Zhiyong Yang, Xiaochun Cao, and Qingming Huang. Maxmatch: Semi-supervised learning with worst-case consistency. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2022.
Shaoteng Liu, Jingjing Chen, Liangming Pan, Chong Wah Ngo, Tat-Seng Chua, and Yu- Gang Jiang. Hy- perbolic visual embedding learning for zero-shot recognition. In Proceedings of the IEEE/CVF conference on computer vision and pottern recognition, pp.
2020.
George A Miller. WordNet: An electronic lexical database. MIT press, 1998.
Takeru Miyato, Shin-ichi Macda, Masanori Koyama, and Shin Ishii. Virtual adversarial training: a regular- ization method for supervised and semi-supervised learning. IEEE transactions on pattern analysis and machine intelligence, 41(8):1979 1993, 2018.
14

---

Published in Transactions on Machine Learning Research (07/2024)
Islam Nassar, Samitha Herath, Ehsan Abbasnejad, Wray Buntine, and Gholamreza Haffari. All labels are not created equal: Enhancing semi-supervision via label grouping and co-training. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pottern Recognition, pp. 7241 7250, 2021.
Gabriel Peyré, Marco Cuturi, et al. Computational optimal transport: With applications to data science. Foundations and Trends@ in Machine Learning, 11(3-6):355-607 2019.
Hieu Pham, Zihang Dai, Qizhe Xie, and Quoc V Le. Meta pseudo labels. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognation, pp. 11557-11568, 2021.
Antti Rasmus, Mathias Berglund, Mikko Honkala, Harri Valpola, and Tapani Raiko. Semi-supervised learn- ing with ladder networks. Advances in Newral Information Processing Systems, 28:3546 3554, 2015a.
Antti Rasmus, Harri Valpola, Mikko Honkala, Mathias Berglund, and Tapani Raiko. Semi-supervised learn- ing with ladder network. ArXiv, abs/1107.00e
2015b.
Kihyuk Sohn, David Berthelot, Nicholas Carlini, Zizhao Zhang, Han Zhang, Colin A Raffel, Ekin Dogus Cubuk, Alexcy Kurakin, and Chun-Liang Li. Fixmatch: Simplifying semi-supervised learning with con- sistency and confidence. Advances in neural information processing systems, 33:596-600 608, 2020.
Robyn Speer, Joshua Chin, and Catherine Havasi. Conceptnet 5.5: An open multilingual graph of general knowledge. In Thirty-first AAAI conference artificial intelligence, 2017.
Yuki Takezawa, Ryoma Sato, and Makoto Yamada. Supervised tree- trss-sssnnnnncin distance. In International Conference on Machine Learning, pp. 10086 10095. PMLR, 2021.
Antti Tarvainen and Harri Valpola. Mcan teachers are better role models: Weight-averaged consistency targets improve semi-supervised deep learning results. Advances in newral information processing systems, 30, 2017.
Alvin Wan, Lisa Dunlap, Daniel Ho, Jihan Yin, Scott Lee, Henry Jin, Suzanne Petryk, Sarah Adel Bargal, and Joseph E Gonzalez. Nbdt: neural-backed decision trees. arXiv preprint arXiv:2004000221, 2020.
Xudong Wang, Long Lian, and Stella X Yu. Data-centric semi-supervised arXiv:2110.00 03.000 2021a.
learning. ar preprinl
Xudong Wang, Zhirong Wu, Long Lian, and Stella X Yu. Debiased learning from naturally imbalanced pseudo-labels. In Proceedings of the IEEE/CVE Conference on Computer Vision and Pattern Recognition, pp. 14647 14657, 2022a.
Yidong Wang, Hao Chen, Qiang Heng, Wenxin Hou, Marios Savvides, Takahiro Shinozaki, Bhiksha Raj, Zhen Wu, and Jindong Wang. Freematch: Sclf-adaptive thresholding for semi-supervised learning. arXiv preprinl ar Xiv: 07246, 2022b.
Yu Wang, Zhou Wang, Qinghua Hu, Yucan Zhou, and Honglei Su. Hicrarchical semantic risk minimization for large-scale classification. IEEE Transactions on Cybernetics, 2021b.
Hui Wu, Michele Merler, Rosario Uceda-Sosa, and John Smith. Learning to make better mistakes: Semantics-aware visual food recognition. In Proceedings of the 24th ACM international conference on Multimedia, pp. 172-176, 2016.
Qizhe Xie, Zihang Dai, Eduard Hovy, Thang Luong, and Quoe Le. Unsupervised data augmentation for consistency training. Advances in Neural Information Processing Systems, 33:6256 6268, 2020.
Yi Xu, Lei Shang, Jinxing Ye, Qi Qian, Yu-Feng Li, Baigui Sun, Hao Li, and Rong Jin. Dash: Semi- supervised learning with dynamic thresholding. In International Conference on Machine Learning, pp. 11525 11536. PMLR, 2021.
Bowen Zhang, Yidong Wang, Wenxin Hou, Hao Wu, Jindong Wang, Manabu Okumura, and Takahiro Shinozaki. Flexmatch: Boosting semi-supervised learning with curriculum pseudo labeling. Advances in 2021.
Neural Information Processing Systems,
15

---

Published in Transactions on Machine Learning Research (07/2024)
Daniel Zügner, Bertrand Charpentier, Morgane Ayle, Sascha Geringer, and Stephan Günnemann. End-to-end learning of probabilistic hierarchies on graphs. In International Conference on Learning Represenlations, 2021.
16

---

Published in Transactions on Machine Learning Research (07 (07/2024)
A Appendix
A.1 Comparision with more advanced methods
We will present more comparisons with more recently introduced methods like FreeMatch (Wang et al., 2022b), SoftMatch (Chen et al., 2023), and InstanT (Li al., 2024). We add our SEAL regularization the existing method FreeMatch. In Table 5, we can see our method shows improvements upon bascline Match and also behaves good even considering the other two methods SoftMatch and Instan'T, showing the effectiveness of our method.
Table Error rates compared with more advanced algorithms.
CIFAR1O labels
CIFAR10 250 labels
CIFAR100 400 labels
CIFAR100 2500 labels
FrecMatch
4.88
37.98
26.47
SoftMatch
4.91
4.82
37.10
26.66
Instan'T
5.17
5.28
46.06
32.91
FreeMatch + SEAL
4.8
4.71
37.12
26
A.2 More ablation studies
A.2.1
Different threshold
0.53
&CUrSy
0.51
0.950
0949
0.91
0.2
0.3
0.4
0.5
0.6
0.7
0.98
0.9
Figure 6: Varying different threshold for pseudo labeling
We first investigate the impact of threshold choice on the accuracy of our method. We experiment with five different values of and plot the results in Figure 6. As shown in the figure, the accuracy increases 7 approaches 0.95, and decreases when 5 deviates from 0.95. This suggests that choosing threshold of 0.95 yields the best performance.
A.2.2 Convergence Speedup
Figure displays the Top-1 accuracy of CIFAR100-2500 labels, showcasing that with the aid of SEAL,, convergence becomes faster and more stable. With the addition of SEAL, the model consistently outperforms the initial training process in all epochs.
A.2.3 Computation overhead of introducing SEAL
We investigate the additional computation time required when applying SEAL to our method. Table shows the results of these experiments, which were conducted using an Nvidia GeForee RTX 2080 Ti. We observe that the computation of SEAL incurs only a marginal increase in the computation time, demonstrating its efficiency in practice.
17

---

Published in Transactions on Machine Learning Research (07 (07/202) 2024)
60
Te-t Accunity
20
Ramatch SEAL
100
200
300
400
500
Epech
Figure 7: Top-1 accuracy CIFAR100 dataset (2500 labels)
Table 6:
Computation Time epoch
Update Method Computation Time (Minutes)
with SEAL
7.11
without SEAL
7.10
A.3 Datasets
We evaluate our proposed method on three popular datasets, namely CIFARIO, CIFARI00, and STL-10.
CIFAR10 and CIFAR100. CIFAR10 (Krizhevsky al., 2009) contains 60,000 colored images in 10 different classes, where each image has size of 32 x 32 pixels. The training set consists of 50,000 labeled images and the test set consists of 10,000 labeled images. Similarly, CIFAR100 (Krizhevsky et al., 2009) contains 100 different classes with the same image size and similar number of images.
STL-10. STL-10 (Coates et al., 2011) is a semi-supervised benchmark that contains 10 classes. is adapted from Imag et al., 2009) and contains 500 labeled training samples and 800 labeled testing samples per class. Additionally, has 10,000 unlabeled images, some of which are not from the labeled classes.
Following the standard semi-supervised learning setting to sample, we sample the labeled images equally and randomly from all classes. To ensure statistical significance, we conduct experiments among seeds and calculate the mean and standard deviation of the results.
A.4 More Theoretical Results
A.4.1 A result about determining the structure of tree based on predictions
We will discuss how retrieve the latent structure matrix A based on the total predictions total labels OUL.
Theorem Recall that is defined by equation (5) and the total prediction operation q is given by definition 1 and A is predefined by tree's 's's adjacency matrix. Assume there are K samples x; (1 K) that make [fe(x))... (f((xk)) a full rank matrix. Then given the total prediction matriz (g(fo(zz)), (t on these samples, we can recover the matrir A.
Proof 2 From definition 1, the model-predicted probabilities are part of the total prediction matrix Q (ffo(())), ... (xff((x))) and we can obtain [fo(=1),..- fo(xx)), From equation (5), have (I A A,F Q therefore A₂ (I AF- Thus can recover the matria A.
18

---

Published in Transactions on Machine Learning Research (07 (024)
A.4.2 Optimal Transport
Definition 4 (Wasserstein-1 distance) Consider two probability distribution: a ~ ,4, and y ~ V. The Wasserslein-1 distance belween ys and u can defoned as:
min I c(x, y) dx,
W (H,
xEll(p))) Xxxx
where X is the space that μ and supported on, c).,-) is a cost function defined on the cortesian space
X X, and II (), is the set of all possible couplings of p and and is a joint distribution salisfying fx π (z, y) dy (x) and Sx π (z, y) dæ (z).
A.4.3 The Relation between SEAL and RTW
Note that we assume no correlation between real labels, thus the vector constructed by Pr(rly) as r-th component is exactly 6g.
As the nodes in OU C are exactly all the total labels, and those in O are all the observed labels. Comparing equations (6) and (13) yields the result. For convenience, we consider the entire tree metric space as X. Then it is easy to see that X' = = L, and Aeat O are the leaf nodes of the tree.
A.4.4 Basic Property of RTW
Here we will present some theoretical properties of relaxed Tree- Wasserstein distance next to illustrate why it is good metric defined trees.
Theorem Wax (...) defines a metric on the probability space. Furthermore, when A is the (hard) adjacency matrir of a tree, the relazed tree Wasserstein distance exactly the tree Wasserstein distance.
Proof 3
The positive definiteness and symmetry of Wirler is clear from its definition. Then we show it satisfies the triangular inequality. For any probability measures X, and v on Kreaf-
velax () + Wrrle (H,v)
Σ W TE
Σ
Our (A(x) - u(x))
IEXinn
+
Σ We Σ Nixt
Oex (1(2²) - v(x))
vE
2
Σ We
(A(x) - v(z)))
veX
W (2,
(14)
Note that when X is hard tree, have ly is the ancestor of x Que- Then from equations (12) and (13), know that RTW is exactly the tree Wasserstein distance in this degenerate case.
Theorem The relaxed tree Wasserstein distance is negative definite kernel.
Proof 4 Please see Appendiz A.4.5.
A.4.5 Kernel Property of RTW
Definition 5 (Bery al,, 1984) A function k. M M R negative definite if for Vn 2 Ya,, ; M and Vo; Th such that In C = 0, use have Ees (c,, (.), $ 0.
19

---

Published in Transactions on Machine Learning Research (07/2024)
Table
ViN best knn classification
initial feature
smooth feature
SEAL feature
prob space hard treedis
0.6725
0.6818
0.6831
0.8094
Table 8:
ResNet18 best knn classification
initial feature
smooth feature
SEAL feature
prob space hard treedis
0.9542
0.9551
0.9572
0.9574
We shall prove that RTW is negative definite kernel on the tree leaf Wasserstein space M = P(( We define a mapping & where
(xx)= = (I A1) A1) A2 )z.
(15)
Note k,)) I ((x.)) (1r;))l1- Since the definition of negative definiteness only related to the value of k. can transform the problem of considering & only. Note k is only weighted 4 distance between D, from the separability of I norm and (Le et al., 2019)'s Lemma A.2, it is clear that RIW is negative definite.
A.5 A Closer Look at the Supervised Settings
In this section, we shall show the performance of SEAL regularization on two backbones, One is a backbone with fower parameters, another is the standard ResNet 18 backbone.
Consider a supervised learning objective L(0) over batch, such as Cross-Entropy (CE) to train the neural network 0, One could derive the SEAL regularized objective as
L(0,0)
B Σ CE((o(z), (
(#.8)EB
[(0)) + (0 B)
(16)
Optimizing C(,, () jointly trains the neural network fo and the latent hierarchy defined by e.
A.5.1 ViN backbone
We train Vision Nystromformer (ViN) (Jeevan & Sethi, 2021) with optimizer AdamW for 60 epochs and get classification accuracy 66.65%, apply the same configuration to label smoothing will give an accuracy of 68.02%. SEAL regularization boosts the accuracy of initial ViN from 66.65% to 68.52% within epochs.
We are also interested in t-SNE visualization the Iearned backbone feature, Figure 9a is the initial ViN feature, and Figure 9b ViN with label smoothing 0.1, Figure 9c the learned ViN feature with SEAL regularization. Figure 9d is slightly different, and we use the learned relaxed Tree- Wasserstein distance probability space as the similarity metric.
As for the k-nearest neighbors (kNN) lask, we choose the best k for each subtask respectively. We summarize the result in Table Note relaxed Tree- Wasserstein distance a well-defined metric, so we also calculate the relaxed Tree- Wasserstein distance on probability space to do the knn task. The tree we used is plotted in Fig. 8a. The tree shows some semantic relations between classes, as semantic closer classes have smaller tree distances.
20

---

Published in Transactions on Machine Learning Research (07 (274))
A.5.2 ResNet18 backbone
Inspired by paper NBDT, on CIFARIO we train 200 epochs, and the origin (trained by cross-entropy loss) accuracy 95.42%. With label smoothing, the accuracy is 95.54%, while with SEAL regularization, the accuracy is 95.75%. In the above experiments, we train the first 180 epochs using the same loss as the initial and turn the loss to label smoothing RTW respectively.
We are also interested in t-SNE visualization of the learned backbone feature, Figure 10a is the initial VIN feature, and Figure 10b VIN with label smoothing a = 0.1, Figure 10c is the SEAL boosted VIN feature. Figure 10d is slightly different, and we use the learned tree distance on probability space as the similarity crileria.
As for the k-nearest neighbors (kNN) task, we summarize the result Table 8. Note relaxed Treee Wasserstein distance is well-defined metric, also calculate the relaxed Tree- Wasserstein distance probability space to do the knn task. The tree used is plotted in Figure 8b. The tree shows some semantic relations between classes, as semantic closer classes have smaller relaxed Tree- SeseWasssrstnnn distances.
Note that in the original paper NBDT, the initial accuracy is 94.97%, and their method gets 94.82%. Their initial accuracy slightly lower than ours may be due to the number of epochs they run being smaller.
10
10
(a) ViN Tree
(b) ResNet Tree
Figure 8: Comparison of ViN Tree and Res.Ne Tree
21

---

Published in Transactions on Machine Learning Research (07 (07/202) 2024)
nutomobii
Le
cAt CEETT
doer
-00
-40
(a) t-SNE visualization of the initial feature of VIN (b) t-SNE visualization of the learned feature of ViN backbone model.
backbone model with label smoothing.
20
75.
31-
automel
B
Truck
-50
-60
-100
-25
(d) t-SNE visualization of the learned probability of ViN (c) 4-SNE visualization the learned feature of ViN model with SEAL regularization. The similarity metric backbone model with SEAL regularization.
is defined by relaxed Tree-Wassent Wasserstiin distance.
Figure 9: Comparison of I-SNE visualizations of features and probabilities learned by the ViN model with different regularization methods. (a) shows the initial feature of the ViN backbone model. (b) shows the Iearned feature with label smoothing. (c) shows the learned feature with SEAL regularization. (d) shows the learned probability with SEAL regularization using relaxed Tree- Wasserstein distance as similarity metric.
22

---

Published in Transactions on Machine Learning Research (07 (07/202) 2024)
20-
argiate
dog
0-
-00
skpp Vuct
lerse
Mtip
truck
60
-02
-90
(a) I-SNE visualization of the initial feature ResNet18 (b) t-SNE visualization of the learned feature of ResNet backbone model
backbone model with label smoothing
202
arprane
ferse:
Jkip
BTOK
-35
-62
-75
300
(c) I-SNE visualization learned feature ResNet18 backbone model with SEAL regularization
(d) L-SNE visualization of learned probability of ResNet18 backbone model with SEAL regularization. Similarity metric defined by relaxed Tree- Wasserstein distance.
Figure 10: Visualizations of ResNet18 backbone model features with different regularization methods.
23


Reviews:
[{"review_id": "MVIbunhPYj", "reviewer": "Reviewer_7Wd7", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n1) Important Question: Label hierarchy is important in the study of SSL, however, existing method encourages the latent label to match to a predefined distribution, which isn't reasonable. The paper addresses this crucial question, which contributes to SSL society.\n\n2) Simple Method: The idea is straightforward to understand and the proposed method is simple, enhancing its accessibility and implementation.\n\n3) Theoretical Grounding: The paper provides a solid theoretical foundation for the proposed method.\n\n4) Good Results with FixMatch: Experimental results on CIFAR and STL-10 datasets demonstrate promising improvements when integrate the technique into FixMatch.\n\nWeaknesses:\n\n1) Scaling up Experiments: It is recommended to conduct experiments on larger-scale datasets, such as ImageNet, to further validate the effectiveness and generalization of the proposed method.\n\n2) Integrate with other SOTA Methods: It is recommended to conduct experiments with other recent state of the art methods (Such as FreeMatch) to prove the effectiveness of the proposed method.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper introduces a regularization technique that improves existing semi-supervised learning (SSL) methods by encouraging consistency between the latent labels of two augmented views of the same example. The proposed method can be seamlessly integrated into existing SSL techniques as a performance booster. Experimental results demonstrate the effectiveness of applying this technique.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1) More Experiments: See Weaknesses above.\n2) Improving the Coverage of Related Works: It appears that the related work sections of this paper does not thoroughly cover some of the most recent research in this field. Specifically, recent works on optimizing the pseudo-label thresholds such as FreeMatch [1] or InstanT [2] should be involved during discussion, and SOTA baselines such as FreeMatch [1] or SoftMatch [3] should be added for comparisons. \n\n\n[1] \"FreeMatch: Self-adaptive Thresholding for Semi-supervised Learning.\" ICLR 2023.\n[2] \"InstanT: Semi-supervised Learning with Instance-dependent Thresholds.\" NeurIPS 2023.\n[3]  \"SoftMatch: Addressing the Quantity-Quality Tradeoff in Semi-supervised Learning.\" ICLR 2023.", "broader_impact_concerns": "Nil", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "gR9RkVu59Y", "reviewer": "Reviewer_Hgok", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- This paper is mostly well written and easy to follow. The notation is clear.\n- The proposed method was derived from a reasonable formulation of the label hierarchy.\n- The proposed method was shown to be effective with limited labeled data.\n- The proposed method can be incorporated with existing semi-supervised learning techniques.\n\nWeaknesses:\n- The theoretical understanding of the proposed method is relatively weak. The meaning and theoretical implications of Theorem 3 were not discussed. In my opinion, this result does not tell us why, when, and how the proposed method works. For better understanding, the author may consider the identifiability of the latent variables.\n- It is unclear how the number of latent variables is determined. The author stated that for CIFAR-10 and STL-10, $N = 21$, and for CIFAR-100, $N = 130$, which seems arbitrary. It is possible that the number may significantly affect the classification performance, depending on the dataset.\n- The interpretability of latent variables may also be an issue. The author showed a learned hierarchy for CIFAR-10 in Figure 3, where there are only 10 classes. In my opinion, the label hierarchy would be more useful when the number of classes is large. Perhaps the author could show the learned label hierarchy for the CIFAR-100 dataset, or conduct experiments on ImageNet and compare the learned hierarchy with the predefined WordNet hierarchy.\n- The author claimed that the improved classification performance is due to the learned label hierarchy. However, the evidence is rather weak. The author only used classification accuracy as an evaluation metric. It might be more convincing if the author could do more analysis on the learned hierarchy.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies the hierarchy of labels in supervised/semi-supervised classification and introduces a framework that simultaneously learns latent labels and observed labels.\nThe proposed method, SEAL, uses a form of 1-Wasserstein metric over rooted trees and learns a data-driven label hierarchy.\nSEAL was evaluated on image classification datasets CIFAR-10, CIFAR-100, and STL-10 and showed improved classification accuracy, especially when the labeled data is limited.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- The \"label alphabet\" may not be a widely-accepted term. Please explain its meaning or provide a reference.\n- Section 2.1: $x_i$ bold.\n- What is a \"_trivial_ binary tree\"?\n- The \"random walk\" part was unclear to me.\n- Section 6.0.1", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "h8j9hY614V", "reviewer": "Reviewer_Y6jp", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths：\n\nThe paper introduces a novel framework that effectively combines the exploration of latent labels with the learning process. SEAL learns a data-driven label hierarchy rather than relying on predefined hierarchies that may not accurately reflect the data's structure.\n\nWeaknesses:\n\nThe use of hierarchical information to aid classification is intuitively appealing. However, the motivational example provided in the manuscript (Example 1) seems inappropriate for illustrating this concept. Typically, hierarchical structures (like colors) should support the classification of broader categories (such as apples and paint), not the other way around. \n\nThe paper employs a complex system of notations that makes understanding the presented SEAL framework hard. For instance, the dimensions of matrices A1 and A2 in Equation 2 seem to differ, raising questions about how they combine to form the adjacency matrix A. The use of symbols such as $\\mu$ varies across Equations 1 and 3. There is confusion between $\\phi$ and $\\Psi$. The manuscript requires significant polishing in terms of structure and clarity of expression.\n\nThe primary contribution of the paper is the SEAL regularization, which the authors claim \"SEAL can be boosted by various techniques\". However, the experimental section does not fully substantiate this claim. The experimental setup should ideally showcase the SEAL regularization's benefits by integrating it into existing semi-supervised learning methods or replacing conventional regularization approaches, such as consistency regularization. This approach would more effectively highlight SEAL's advantages and its potential to enhance SOTA. The experiments seem to incorporate SEAL as a plug-in regularization term in only two methods, and there is an absence of SEAL (Debiased) in Table 2.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper introduces a novel framework named SEAL, which aims to enhance classification performance by exploring and learning from label hierarchies. SEAL incorporates latent labels into the learning process, which are not directly observed but inferred from the data, thereby capturing a more nuanced understanding of the underlying data structure. This approach utilizes a 1-Wasserstein metric over the tree metric space, enabling the simultaneous learning of a data-driven label hierarchy and the performance of semi-supervised learning tasks. The authors demonstrate through extensive evaluations that SEAL improves classification accuracy.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please see above", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: Currently, there are still some remaining important concerns. Specifically, Reviewer Y6jp still has remaining concerns about the presentation. Reviewer 7wd7 has concerns about missing large-scale experiments such as ImageNet, and the authors have also promised to provide results ASAP. I hope the authors can make use of this opportunity to improve this paper further by addressing these concerns.
Decision: Accept (poster)