Learn to Categorize or Categorize to Learn? Self-Coding for Generalized Category Discovery
Authors: Sarah Rastegar
Hazel Doughty
Cees G. M. Snoek
Venue: NeurIPS 2023 poster (2023)
Keywords: Generalized category discovery
Open world learning
Open-set recognition

Abstract: In the quest for unveiling novel categories at test time, we confront the inherent limitations of traditional supervised recognition models that are restricted by a predefined category set. While strides have been made in the realms of self-supervised and open-world learning towards test-time category discovery, a crucial yet often overlooked question persists: what exactly delineates a category? In this paper, we conceptualize a category through the lens of optimization, viewing it as an optimal solution to a well-defined problem. Harnessing this unique conceptualization, we propose a novel, efficient and self-supervised method capable of discovering previously unknown categories at test time. A salient feature of our approach is the assignment of minimum length category codes to individual data instances, which encapsulates the implicit category hierarchy prevalent in real-world datasets. This mechanism affords us enhanced control over category granularity, thereby equipping our model to handle fine-grained categories adeptly. Experimental evaluations, bolstered by state-of-the-art benchmark comparisons, testify to the efficacy of our solution in managing unknown categories at test time. Furthermore, we fortify our proposition with a theoretical foundation, providing proof of its optimality. Our code is available at: https://github.com/SarahRastegar/InfoSieve.

Learn to Categorize or Categorize to Learn?
Self-Coding for Generalized Category Discovery
Sarah Rastegar, Hazel Doughty; Cees G. M. Snoek University of Amsterdam
Abstract
In the quest for unveiling novel categories test time, confront the inherent limitations of traditional supervised recognition models that are restricted by a pre- defined category set. While strides have been made in the realms of self-supervised and open-weneee open-world world learning towards test-time category discovery, a crucial yet often overlooked question persists: what exactly delineates a category? In this paper, conceptualize a category through the lens of optimization, viewing it as an optimal solution to well-defined problem. Harnessing this unique conceptualization, we propose novel, efficient and self-supervised method capable discovering previously unknown categories at test time. A salient feature of our approach is the assignment minimum length category codes to individual data instances, which encapsulates the implicit category hierarchy prevalent in real-world datasets. This mechanism affords us enhanced control over category granularity, thereby equip- ping our model to handle fine-grained categories adeptly. Experimental evaluations, bolstered by state-of of-the-art benchmark comparisons, testify to the efficacy of our solution in managing unknown categories at test time. Furthermore, we fortify our proposition with a theoretical foundation, providing proof of its optimality. Our code is available at: hhtpp:://e/ tectps://githne /htbbttt...t//////////// com Bttp//Saaaaaattgarraaaaaa wwt.aaaattttarr/ffSSiiieeee Infoa//iefffeee
Introduction
The human brain intuitively classifies objects into distinct cat- egories, a process so intrinsic that its complexity is often over- looked. However, translating this seemingly innate understand- ing of categorization into the realm of machine learning opens a veritable Pandora's 's box differing interpretations for what constitutes category? 112) Prior to training machine learn- ing models for categorization tasks, indispensable to first demystify this concept of category.
Figure 1: What is the correct cat- egory? Photo of a flying fox fruit bat. This image can be categorized as bat, bird, mammal, flying bat, and other categories. How should we define which answer is correct? This paper uses self-supervision to learn an implicit category code tree that reveals different levels of gran- ularity in the data.
In the realm of conventional supervised learning 7 each category is represented by arbitrary codes, with the expectation that machines produce corresponding codes upon encountering objects from the same category. Despite its widespread use, this approach harbors several pitfalls: it suffers from label inconsistency, overlooks category hierarchies, and, as the main topic of this paper, struggles with open- open-world recognition.
Pitfall I: Label Inconsistency. Assessing model's 's perfor- mance becomes problematic when category assignments are subject to noise g or exhibit arbitrary variation across different datasets. For example, if zoologist identifies the bird in Figure [ as flying fox fruit bat, it is not due misunderstanding of what constitutes bird dog. Rather, signifies more nuanced understanding of these categories. However, conventional machine learning
Currently at Leiden University
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Roos
The implicit binary tree our model finds to address samples. Each leaf in the tree indicates a specific sample, and each node indicates the set of its descendants' samples. For instance, the node associated with '11...11' is the set of all birds with red beaks, while its parent is the set of all birds with red parts in their upper body.
Figure 2:
models may penalize such refined categorizations they deviate from the pre-defined ground-truth labels. This work addresses this limitation by assigning category codes to individual samples. These codes not only prevent ver-dependence on specific labels but also facilitate encoding similarities across distinct categories, paving the way for more robust and nuanced categorization.
Pitfall I: Category Hierarchies. prevalent encoding method, such as one-hot target vectors, falls short when addressing category hierarchies. While we, as humans, intuitively distinguish the categories of plane and dog more disparate than and dog, our representations within the model fail to convey this nuanced difference. effectively disregarding the shared semantics between the categories of cat and dog. While some explorations into a category hierarchy for image classification have been undertaken [T0H44) these studies hinge on an externally imposed hierarchy. thus limiting their adaptability and universality. This paper proposes model to impose these implicit hierarchies in the form of binary trees into their learned representation. For instance, Figure[]shows that we can address each sample in the dataset with path from the root of this implicit tree, hence associating a category code to it. We show theoretically that under a set of conditions, all samples in a category have common prefix, which delineates category membership.
supervupeee approach that enables the
Pitfall H:: Open World Recognition. The final problem we consider the encounter with the open world [15)17]. When a model exposed to novel category, the vague definition of category makes it hard to deduce what will be an unseen new category. While open-set recognition models 12-22 can still evade this dilemma by rejecting new categories, Novel Class Discovery (33-26 or Generalized Category Discovery [2731] can not ignore the fundamental flaw of a lack of definition for a category. This problem is heightened when categories are fine-gre lne-grained 32 or follow long-tailed distribution (3
In this paper, we confront these challenges by reframing the concept of category as the solution an optimization problem. We argue that categories serve to describe input data and that there is not singular correct category but sequence of descriptions that span different levels of abstraction. We demonstrate that considering categorization as search for a sequence of category codes not only provides more flexibility when dealing with novel categories but also. by leveraging sequences, allows us to modulate the granularity of categorization, proving especially beneficial for fine-grained novel categories. Subsequently, we illustrate how to construct framework capable of efficiently approximating this solution. Our key contributions are as follows:
Theoretical. We conceptualize a category as a solution an optimization problem. We then demonstrate how to fine-tune this optimization framework such that its mathematical solutions align with the human-accepted notion of categories. Furthermore, under a set of well-defined constraints, we establish that our method theoretically yields an optimal solution.
Methodological. Based on the theory we developed, we propose a practical method for tackling the generalized category discovery problem, which is also robust to different category granularities. Experimental. We empirically show that our method outperforms state-of-the-art generalized category discovery and adapted novel class discovery methods on fine-grained datasets while performing consistently well on coarse-grained datasets.
Before detailing our contributions, we first provide some background category discovery to better contextualize our work.

---

2 Background
The Generalized Category Discovery problem introduced by Vaze et al. [27] tries to categorize a set of images during inference, which can be from the known categories seen during training or novel categories. Formally, we only have access to V/s or seen categories during training time, while we aim to categorize samples from novel categories or Div during test time. For the Novel Class Discovery problem, it is assumed that \'s n = However, this assumption could be unrealistic for real-world data. So Vaze et 2 proposed to use instead the more realistic Generalized Category Discovery assumption in which the model can encounter both seen and unseen categories during test time. In short, for the Generalized Category Discovery problem, we have Y's C Du-
One major conundrum with both Generalized Category Discovery and Novel Category Discovery is that the definition of the category has remained undetermined. This complication can be overlooked when the granularity of categories at test time is similar to training time. However, for more realistic applications where test data may have different granularity from training data or categories may follow a long-tailed distribution, the definition of category becomes crucial. To this end, in the next section, we formulate categories as a way to abstract information in the input data.
3 An Information Theory Approach to Category Coding
To convert a subjective concept as a category to formal definition, we must first consider why categorization happens in the first place. There are many theories regarding this phenomenon in human [38 40] and even animal brains 41 43 One theory is categorization was a survival necessity that the human brain developed to retrieve data as fast and as accurately as possible [44. Studies have shown that there could be trade-off between retrieval speed and accuracy of prediction in the brain [5)47]] Meanwhile, other studies have shown that the more frequent categories can be recognized in shorter time, with more time needed to recognize fine-grained nested subcategories [48] 49]. These studies might suggest shorter required neural pulses for higher hierarchy levels. Inspired by these studies, we propose categorization as optimization problem with analogous goals to the human brain. We hypothesize that we can do the category assignment to encode objects hierarchically to retrieve them accurately and quickly as possible.
Notation and Definitions. Let us first formalize our notation and definitions. We denote the input random variable with X and the category random variable with C. The category code random variable, which we define as the embedding sequence of input X is denoted by ='=2î ............... 2i. in which superscript shows the ith sample, while subscript I, shows the digit position in the code sequence. In addition, 1 [(X; Z) indicates the mutual information between random variables X and Z [50] 511 which measures the amount of information we can obtain for one random variable by observing the other one. Since category codes are sequences, algorithmic information theory is most suitable for addressing the problem. We denote the algorithmic mutual information for sequences x and z with laig : z), which specifies how much information about sequence x we can obtain by observing sequence Both Shannon and algorithmic
memaatiinnthoory-... based estimators useful for hicrarchical clustering (56), suggesting we may benefit from this quality to simulate the implicit category hierarchy. A more in-depth discussion can be found in the supplemental.
3.1 Maximizing the Algorithmic Mutual Information
Let's consider data space D=(X",C) C : E (1,...N) where Xs are inputs and Cs are the corresponding category labels.
Lemma For each category and for X with Ci=c, we can find a binary decision tree Te that starting from its root, reaches each X by following the decision tree path. Based on this path, we assign code -(xt)) ..chs to each X to uniquely define and retrieve it from the tree, M is the length of the binary code assigned to the sample.
Proof of Lemma Dis provided in the supplemental. Based on this lemma, we can find a forest with categories e as the roots and samples X's as their leaves. We apply the same logic to find a super decision tree T that has all these category roots as its leaves. If we define the path code of category e in this super tree by pfc)= ... P where K is the length of the path to the category e; we find the path to each X in the supertree by concatenating its category path code with its code in the category decision tree. So for each input X" with category e we define an address code as g g2 ... 9K in which =p for j < K and = for j > K. Meanwhile, since all X's are the descendants
3

---

of root e in the Te tree, we know there is one encoding to address all samples, in which samples of the same category share similar prefix. Now consider a model that provides the binary code x² =-= ... 2z for data input X with category c, let's define valid encoding in Definition
Definition A valid encoding for input space X and category space C is defined as an encoding that uniquely identifess every X E X. At the same time, for each category E C, it ensures that there is sequence that is shared among all members of this category but no member out of the category.
As mentioned before, if the learned tree for this encoding is isomorph to the underlying tree T, we will have the necessary conditions that Theorem provides.
Theorem For learned binary code z' address input X', uniquely, the decision tree of this encoding is isomorph to underlying tree T, we will have the following necessary conditions:
1. Tatg x) 2 Tatg (7: x))
VE, ā is a valid encoding for x Vž, E is valid encoding for
2. Luty (z c) Lutg (2 c)
Proof of Theorem is provided in the supplemental. Optimizing for these two measures provides an encoding that satisfies the necessary conditions. However, from the halting Theorem [57] this optimization generally not computable 58
Theorem T Clarification.
The first part of Theorem [ states that if there is an implicit hierarchy tree, then for any category tree that is isomorph to this implicit tree, the algorithmic mutual information between each sample and its binary code generated by the tree will be maximal for the optimal tree. Hence, maximizing this mutual information is necessary condition for finding the optimal tree. This is equivalent to finding a tree that generates the shortest-length binary code to address each sample uniquely. The second part of Theorem [ states that for the optimal tree, the algorithmic mutual information between each sample category and its binary code will be maximum. Hence, again, maximizing this mutual information is necessary condition for finding the optimal tree. This is equivalent to finding tree that generates the shortest-length binary code to address each category uniquely. This means that since the tree should be a valid tree, the prefix to the unique address of every category sample e should be the shortest-length binary code while not being the prefix of any sample from other categories.
Shannon Mutual Information Approximation. We can approximate these requirements using Shannon mutual information instead if we consider specific set of criteria. First, since Shannon entropy does not consider the relationship between separate bits or zjs, we convert each sequence to an equivalent random variable number by considering its binary digit representation. To this end, we consider z'=Σ"
m zi which is a number between O and 1. To replace the first item of Theorem 1 by its equivalent Shannon mutual information, we must also ensure that z has the minimum length. For the moment, let's ss assume we know this length by the function 1(x))=4, Hence instead of Z',
k= 24
we consider its truncated form Z Ekm #t. defined as follows:
This term, which we call the address loss function, is zt.
Lude
1 N
Σ 1(xi )
8.l. Z
and Vk. = E 1).
2
We can approximate this optimization with contrastive loss. However, there are two requirements that we must consider, First, we have to obtain the optimal code length 4, and second, we have to ensure zft binary. In the following sections, we illustrate how we can satisfy these requirements.
3.2 Category Code Length Minimization
To find the optimal code lengths I in Equation we have to minimize the total length of the latent code. We call this loss Lengthh which we define as Lienthh N ΣN 4, However, since the I; are in the subseripts of Equation [] we can not use the conventional optimization tools to optimize this length. To circumvent this problem, we define binary mask sequence m m'-mimnš m.j to simulate the subscript property of 4, Consider a masked version of z'=2f ... #2. which we will denote as - ... L in which for 1 < k < L., we define = The goal is to minimize the number of ones sequence m² while forcing them to be at the beginning of the sequence. One way to ensure this is to consider the sequence m n'=(m]]) 2 (m)22)(m3))) ... (mi and minimize its Lp Norm for p 1.

---

This will ensure the requirements because adding one extra bit has an equivalent loss of all previous bits. In the supplemental, we provide a more rigorous explanation.
N
Liength
2 N
lpp
(2)
X
We extract the mask from the input X i.e., m m'= Mask(aa Mask digits should also be binary, so need to satisfy their binary constraints, which will address next.
Satisfying Binary Constraints. Previous optimizations are constrained to two conditions, Code Constraint: Vzj. 2k 0 or 2 = 1 and Mask Constraint: Vmi, mi 0 mi 1. We formulate each constraint in an equivalent Lagrangian function to make sure they are satisfied. For the binary code constraint consider fode( )=)))==))(1
=0, which is only zero if 2 =0 2 =1. Similarly, =0. To ensure these constraints are
for the binary mask constraint, we have f fmus (m (m)))) satisfied, optimize them with the Lagrangian function of the overall loss.
Aligning Category Codes using Supervision Signals The second item in Theorem I shows the necessary condition for maximizing mutual information with category. If we replace algorithmic mutual information with its Shannon cousin, will have:
3.3
N
Lca
Σ 1=0
I(c);
s.t.
Zj.
and Ak, ot. E (0.
N
2
Subject to satisfying the binary constraints. Note that the optimal lengths might differ for optimizing information based on categories or input. However, here we consider the same length for both scenarios for simplicity.
Overall Loss. Putting all these losses and constraints together, we will reach the constrained loss:
Cconstrained Lade + &lenghh + CCC s.t. 4k, foode (2t) 0, Vk, i fmask (mm,) 0. (4)
Note that when we do not have the supervision signals, we can consider y=0 and extract cate- gories in unsupervised manner. In the supplemental, we have shown how to maximize this function based on the Lagrange multiplier. we indicate Lende cord Σ == El (zi)² = and
Laaak_cond EN Elem (m - m The final loss will be:
Liimal = Latr + &Lenngh + LCa + (Cenle comd + J&
(5)
Note that for satisfying binary constraints, we can adopt other approaches. For instance, we can omit the requirement for this hyperparameter by using binary neural networks and an STE (straight- estimator) (62). Another approach would be to benefit from Boltzmann machines
[63 to have
binary code. Having defined our theoretical objective, we are now ready to make it operational.
InfoSieve: Self-supervised Code Extraction
In this section, using the equations from Section we devise a framework to extract category codes. Note that as Theorem indicates, when we train the model to extract the category codes instead of the categories themselves, we make the model learn the underlying category tree. The model must ensure that in its implicit category tree, there node for each category whose descendants share the same category while there are non-descendants of this node with the same category.
Input
Code Generatur
Cu oads
Less
Loedeecooll
Feature Extractor
Categorizer
Crank_coed
Ce
Code
Musker
lough
Figure 3: InfoSieve framework. Fea- ture Extractor extracts an embedding by minimizing contrastive loss Lc The Code Generator uses these input embed- dings find category codes. The Code Masker simultaneously learns masks that minimize the code length with Linngth Fi- nally, truncated category codes are used minimize a contrastive loss for cate- gory codes while also predicting the seen categories by minimizing Leat-
The overall framework of our model, named InfoSieve, depicted in Figure 3 We first extract an embedding using the contrastive loss used by (77] Then our Code Generator uses this embedding to generate binary codes, while our Code Masker learns a mask based on these embeddings to minimize the code length. Ultimately, the Categorizer uses this truncated code to discer ground- truth categories. In the next sections, we explain each component in more detail.
5

---

4.1 Contrastive Learning of Code and Input
One of the advantages of contrastive learning is to find a representation that maximizes the mutual information with the input [64]. For input X let's show the hidden representation learning with Z', which is learned contrastively by minimizing the InfoNCE loss. Van den Oord et al. [64] showed that minimizing InfoNCE loss increases a lower bound for mutual information. Hence, contrastive learning with the InfoNCE loss can be a suitable choice for minimizing the Ludr in Equation [T, We will use this to our advantage on two different levels. Let's consider that Z' has dimension d. and each latent variable 2j, can take up n different values. The complexity of the feature space for this latent variable would be (n*)), then as we show in supplcmental, the number of structurally different binary trees for this feature space will be O(4"). So minimizing n and d will be the most effective way to limit the number of possible binary trees. Since our model and the amount of training data bounded, we must minimize the possible search space while providing reasonable performance. At the same time, the imput feature space X' with N possible values and dimension D has (NV)) possible states. To cover it completely, we can not arbitrarily decrease d and n. Note that for a nearly continuous function N - oc, the probability of a random discrete tree fully covering this space would be near zero. To make the best of both worlds, we consider different levels of complexity of latent variables, each focusing on one of these goals.
Minimizing Contrastive Loss on the Inputs. Similar 277 we use this unsupervised contrastive loss to maximize the mutual information between input X and the extracted latent embedding Z Akin to 27 we also benefit from the supervised contrastive learning signal for the members of particular category. Let's assume that the number of categories in the entire dataset is C. Different members of a category can be seen as different views of that category, analogous to unsupervised contrastive loss. Hence, they combine these unsupervised contrastive loss or L in and its supervised counterpart, L with coefficient X, which we call Am in a following manner:
Lc.in = (1 CC + Xin CC
(6)
For covering the input space, X the loss function from Equation is more suited if we consider both input and latent features approximately continuous. We have shown this loss by Lc in Figure 3
Minimizing Contrastive Loss on the Codes. In order to also facilitate finding the binary tree, we map the latent feature extracted from the previous section to binary code with minimum length. Hence we effectively decrease n to while actively minimizing d. Furthermore, we extract a code by making the value of each bit in this code correspond to its sequential position in binary number, ie., each digit has twice the value of the digit immediately to its right. This ensures the model treats this code as a binary tree coding with its root in the first digit. We consider unsupervised contrastive learning for raw binary digits _odd: and supervised variants of this loss for the extracted code, which we will show by and coder the total contrastive loss for the binary embedding is defined
(7) In summary, the loss from Equation 6 finds a tree compatible with the input, while the loss from Equation 7 learns an implicit tree in compliance with categories. Then we consider Ladr as their combination:
Lc = (1 Acode) + Acode
Lute aL + Bauc
(8)
4.2 Minimizing Code Length
As discussed in Section 4.1 we need to decrease the feature space complexity by using minimum length codes to reduce the search space for finding the implicit category binary tree. In addition, using Shannon's mutual information an approximate substitute for algorithmic mutual information necessitates minimizing the sequence length. We must simultancously learn category codes and their optimal length. Since each of these optimizations depends the optimal solution of the other one, we use two different blocks to solve them at the same time.
Code Generator Block. In Figure the Code Generator block uses the extracted embeddings to generate binary category codes. At this stage, we consider a fixed length for these binary codes. The output of this stage is used for unsupervised contrastive learning the codes in Equation 7 We also use Leode_ cond to enforce the digits of the codes to be a decent approximation of binary values.
Code Masker Block. For this block, we use the Cmask cond to ensure the binary constraint of the outputs. In addition, to control the length of the code or, in other words, the sequence of is at the beginning, we use Liength in Equation

---

Table I: Ablation study on the effectiveness of each loss function. Accuracy score on the CUB dataset is reported. This table indicates each component's ' preference for novel known categories. In the first row of the table, differences in results compared with [27] can be attributed to specific implementation details, which are elaborated in section B.2 in the supplemental.
Cc
LC code
Lende cond
Liength
mask conn
Caa
All
Known
Novel
X
X
X
66.8
78.1
61.1
X
X
X
X
67.7
75.7
63.7
X
X
X
68.5
77.5
64.0
J
/
J
X
X
68.4
76.1
64.5
/
V
X
67.8
78.7
62.3
/
X
X
X
X
V
68.2
76.4
64.1
V
69.4
77.9
65.2
4.3 Aligning Codes using Supervision Signals
In the final block of the framework, we convert category codes from the Code Generator to a binary number based on the digit positions in the sequence. To truncate this code, we do a Hadamard multiplication for this number by the mask generated by the Code Masker. We use these truncated codes for supervised contrastive learning on the codes. Finally, we feed these codes to the Catgorizer block to predict the labels directly. We believe relying solely contrastive supervision prevents the model from benefiting from learning discriminative features early on to speed up training.
Experiments
5.1 Experimental Setup
Eight Datasets. We evaluate our model on three coarse-grained datasets CIFAR10/100
655
and
ImageNet-100 (66] and four fine-grained datasets: CUB-200 (67, Aircraft 688 SCars 69 and
Oxford-Pet [70]. Finally, we use the challenging Herbarium 19 [71 dataset, which is fine-grat grained and long-tailed. To acquire the train and test splits, we follow 227 We subsample the training dataset in ratio of 50% of known categories at the train and all samples of unknown categories. For all
datasets except CIFAR I00, we consider 50% of the categories as known categories training time. For CIFAR 100, 80% of the categories are known during training time, as in 277. A summary of dataset statistics and their train test splits is shown in the supplemental.
Implementation Details. Following [27] we use ViT-B/16 as our backbone, which is pre-trained by DINO 772 on unlabelled ImageNet 1K [4] Unless otherwise specified, use 200 epochs and batch size of 128 for training. We present the complete implementation details in the supplemental. Our code is available at: httts:://ttthhiie http:///......aaaaaaaarrrrreeeie
Evaluation Metrics We use semi-supervised k-means proposed by [27] to cluster the predicted embeddings. Then, the Hungarian algorithm [73) solves the optimal assignment of emerged clusters to their ground truth labels. We report the accuracy of the model's predictions on All, Known, and Novel categories. Accuracy on All is calculated using the whole unlabelled train set, consisting of known and unknown categories. For Known, we only consider the samples with labels known during training. Finally, for Novel, consider samples from the unlabelled categories at train time.
5.2 Ablative studies
We investigate each model's component contribution to the overall performance of the model and the effect of each hyperparameter. Further ablations can be found in the supplemental.
Effect of Each Component. We first examine the effect of each component using the CUB dataset.
A fine-grained dataset like CUB requires the model to distinguish between the semantic nuances of each category. Table T shows the effect of each loss component for the CUB dataset. As we can see from this table, fc_code and Liength have the most positive effect on novel categories while affecting known categories negatively. Utilizing Lende_cond to enforce binary constraints on the embedding enhances performance for both novel and known categories. Conversely, applying Lmask cond boosts performance for known categories while detrimentally impacting novel categories. This is aligned with Theorem [ and the definition of the category because these losses have opposite goals. As discussed, minimizing the search space helps the model find the implicit category tree faster. Lc code and Liength try to achieve this by mapping the information to smaller feature space, while condition
7

---

Table 2: Hyperparameter anlysis. This table indicates the effect on the accuracy score of each hyperparameter on the CUB dataset for novel or known categories.
(a) Effect Code Constraint Coefficient
(b) Effeet Mask Constraint Coefficient
Code Constraint Coef
All
Known
Novel
Mask Constraint Coef
All
Known
Novel
< 0.01
69.4
77.9
65.2
j 0.01
69.4
77.9
65.2
) 0.1
69.1
76.1
65.6
P 0.1
67.2
74,1
63.8
69.9
76.1
66.8
P =
69.3
76.0
65.9
(= 2
69.5
75.5
66.5
J =
70.6
79.3
66.3
(c) Effect of Code Contrastive Coeflicient
(d) Effect of Code Length Coefficient
Code Contrastive Coef
Known
Novel
Code Cut Length Coef
All
Known
Novel
0.01
68.6
77.0
64.5
8 0.01
69,4
77.0
65.6
B 0.1
69.9
76.3
66.7
8 0.1
69.4
77.9
65.2
1
69.4
77.9
65.2
8 1
68.8
75.8
65.2
B 2
68.6
77.9
64.0
8
69.8
76.9
66.2
losses solve this by pruning and discarding unnecessary information. Finally, Lear on its has a destructive effect on known categories. One reason for this is the small size of the CUB dataset, which makes the model overfit on labeled data. However, when all losses are combined, their synergic effect helps perform well for both known and novel categories.
5.3 Hyperparameter Analysis
Our model has a few hyperparameters: code binary constraint (O), mask binary constraint (μ), code contrastive (3), code length (8). and code mapping (1)). We examine the effect of cach hyperpa- rameter on the model's performance on the CUB dataset. Our default values for the hyperparam- eters are: code constraint coeff ç=0.01, mask constraint coeff 4=0.01, code contrastive coeff 3=1, code mapping coeff 000001 and code length coeff 8=0.1.
Code Binary Constraint. This hyperparameter is introduced to satisfy the binary requirement of the code. Since we use tanh to create the binary vector, the coefficient only determines how fast the method satisfies the conditions. When codes 0 and 1 are stabilized, the hyperparameter effect will be diminished. However, we noticed that more significant coefficients somewhat affect the known accuracy. The effect of this hyperparameter for the CUB dataset is shown in (a). We can see that the method robust to the choice of this hyperparameter.
For the mask constraint pyperarrameter we start from an all-one mask in our Lagrange multiplier approach. A more significant constraint translates a longer category code. A higher coefficient is more useful since it better imposes the binary condition for the mask. The effect of different values of this hyperparameter for the CUB datasets shown in Table (b).
Mask Binary Constraint.
Code Contrastive. This loss maintains information about the input. From Table (c), we observe that minimizing the information for a fine-grained dataset like CUB will lead to better performance.
Code Length. Table () reports our results for different values of code length hyperparameter. Since the code length is penalized exponentially, the code length hyperparameter's effeet is not comparable to the exponential growth; hence, in the end, the model is not sensitive to this hyperparameter' 's value.
Code Mapping. Since current evaluation metrics rely on predefined categories, our category codes must mapped to this scenario. This loss is not essential part of the self- coding that our model learns, but accelerates model training. The effect of this hyperparameter is shown in Table 3
Table 3: Effect of Code Mapping. Accuracy scores on the CUB dataset for novel and known categories.
CUB
Overall Parameter Analysis One reason the model is not very sensitive to different hyperparameters is that our model consists of three separate parts: Code masker, Code Gener- ator, and Categorizer. The only hyperparameters that affect all of these three parts directly are B. the code contrastive coefficient, and ò, the code length coefficient. Hence, these hyperparameters affect our model's performance more.
Code
All
Known
Novel
? = 0.01
69.4
77.9
65.2
0.1
68.4
75.7
64.8
1
68.8
75.7
65.3
7 2
68.9
77.5
64.6

---

Table 4: Comparison fine-grained image recognition datasets. Accuracy score for the first three methods is reported from [27] and for ORCA from [28]. Bold and underlined numbers, respectively, show the best and second-best accuracies. Our method has superior performance for the three experimental settings (All, Known, and Novel). This table shows that our method is especially well suited to fine-gras lineigrinedd settings.
CUB-200
FGVC-Aireraft
Stanford-Cars
Oxford-IIIT Pet
Herbarium- 19
Method
All
Known Novel
All
Known Novel
All
Known Novel
All
Known Novel
All
Known Novel
k-mcans
74
34.3
38,9
32.1
12.9
12.9
12.8
12.8
10.6
13.8
77.1
70.1
80.7
13.0
12.2
13.4
RankStats
75
33.3
51.6
24.2
26.9
36.4
22.2
28.3
61.8
12.1
27.9
55.8
12.8
UNO+ 76
35.1
49.0
28.1
40.3
56.4
32.2
35.5
70.5
18.6
28.3
53.7
14.7
ORCA
36.3
43.8
32.6
31.6
32.0
31.9
42.2
26,9
24.6
26.5
23.7
GCD 27
51.3
56.6
48.7
45.0
41.1
46.9
39.0
57.6
29.9
80.2
85.1
77.6
35.4
51.0
27.0
XCon 32
52.1
54.3
51.0
47.7
44.4
49.4
40.5
58.8
31.7
86.7
91.5
84.1
PrompiCAL
28
62.9
64.4
62.1
52.2
52.2
52.3
50.2
70.1
40.6
DCCL 29
63.5
60.8
64.9
43.1
55.7
36.2
88.1
88.2
88.0
SimGCD
31
60.3
65.6
$7.7
54.2
59.1
51.8
53.8
71.9
45.0
44.0
58.0
36.4
GPC 78
52.0
55.5
47.5
43.3
40.7
44.8
38.2
58.9
27.4
InfoSieve
69.4 77.9
65.2
56.3
63.7
52.5
|55.7
74.8
46.4
191.8
92.6
91.3
41.0
55.4
33.2
Table 5: Comparison on coarse-grained image recognition datasets. Accuracy for the first three methods from 27 and for ORCA from 28). Bold and underlined numbers, respectively, show the best and second- best accuracies. While our method does not reach state-of-the-art for coarse-gre gaase-grained settings, it has consistent performance for all three experimental settings (All, Known, Novel).
CIFAR-10
CIEAR-100
ImageNet-100
Method
All
Known
Novel
All
Known
Novel
All
Known
Novel
k-means
74
83.6
85.7
82.5
52.0
52.2
50.8
72.7
75.5
71.3
RankStats+
75
46.8
19.2
60.5
58.2
77.6
19.3
37.1
61.6
24.8
UNO+ 76
68.6
98.3
53.8
69.5
80.6
47.2
70.3
95.0
57.9
ORCA 77
96.9
95.1
97.8
74.2
82.1
67.2
79.2
93.2
72.1
GCD 27
91.5
97.9
88.2
73.0
76.2
66.5
74.1
89.8
66.3
XCon 32
96.0
97.3
95.4
74.2
81.2
60.3
77.6
93.5
69.7
PrompiCAL 28
97.9
96.6
98.5
81.2
84.2
75.3
83.1
92.7
78.3
DCCL 29
96.3
96.5
96.9
75.3
76.8
70.2
80.5
90.5
76.2
SimGCD 311
97.1
95.1
98.1
80.1
81.2
77.8
83.0
93.1
77.9
GPC 78
90.6
97.6
87.0
75.4
84.6
60.1
75.3
93.4
66.7
InfoSieve
94.8
97.7
93.4
78.3
82.2
70.5
80.5
93.8
73.8
5.4 Comparison with State-of-the-Art
Fine-grained Image Classification. Fine-grained image datasets are more realistic approach the real world. In coarse coarse-grained datasets, the model can use other visual cues to guess about the novelty of a category; fine-grained datasets require that the model distinguish subtle category-specifte details, Jummaiiss our model's performance on the fine-grained datasets. As we can see from this table, our model has more robust and consistent results compared to other methods for fine-grained datasets. Herbarium 19, long-tailed dataset, raises the stakes by having different frequencies for different categories, which detrimental to most clustering approaches because of the extremely unbalanced cluster size. As Table our model can distinguish different categories even from a few examples and is robust to frequency imbalance.
Coarse- ceese-grained Image Classification. Our method is well suited for datasets with more categories and fine distinctions. Nevertheless, we also evaluate our model on three coarse-grained datasets, namely CIFAR 10 and 100 (55 and ImageNet- 100 [66]. TableeJcompprrs our results against of-t--oftthe-rr generalized category discovery methods. As we can see from this table, our method performs consistently well on both known and novel datasets. For instance, while UNO+ shows the highest accuracy on the Known categories of CIFAR- 10, this is at the expense of performance degradation on the Novel categories. The same observations can be seen on ImageNet- Table 3 shows that our method consistently performs competitively for both novel and known categories. Based on our theory, the smaller CIFAR 10/100 and ImageNet- 100 improvement is predictable. For CIFAR 10, the depth of the implicit tree is 4; hence, the number of implicit possible binary trees with this limited depth is smaller, meaning finding good approximation for the implicit category tree can be achieved by other models. However, as the depth of this tree increases, our model can still find the aforementioned tree; hence, we see more improvement for fine-graince data.

---

5.5 Qulitative results
In supplemental, we explain how to extract the implicit tree that is learned by our model. For instance, Figure 2 shows this extracted tree structure on the CUB dataset. We see that our method can extract some hierarchical structure in the data. In the leaves of this tree, we have "yellow sparrows," instances which are the descendants of a more abstract "sparrow" node; or in the path '00...1, we have a "blackbirds" node, which can encompass multiple blackbird species as its children nodes.
Related Works
Novel Category Discovery can be traced back to Han et al. 779. where knowledge from labeled data used to infer the unknown categories. Following this work, Zhong et al. [80] solidified
the novel class discovery as new specific problem. The main goal of novel class discovery is
to transfer the implicit category structure from the known categories to infer unknown categories
124 26
[75 76, 8T 82 99] Prior to the novel class discovery, the problem of encountering
new classes at the test time was investigated by open-set recognition [16 20 [00]. However, the strategy of dealing with these new categories is different. In the open-set scenario, the model rejects the samples from novel categories, while novel class discovery aims benefit from the vast knowledge of the unknown realm and infer the categories. However, the novel class discovery has a limiting assumption that test data only consists of novel categories. For a more realistic setting, Generalized Category Discovery considers both known and old categories at test time.
Generalised Category Discovery recently has been introduced by [27] and concurrently under the name Open-world semi-supervised learning by [77]. In this scenario, while the model should not lose its grasp on known categories, it must discover novel ones at test time. This adds extra challenge because when we adapt the novel class discovery methods to this scenario, they are biased to either novel or known categories and miss the other group. There has been a recent surge of interest in generalized category discovery [18] 78 [01] In this work, instead of viewing categories as an end, we investigated the fundamental question of how conceptualize the category itself.
Decision Tree Distillation, The benefits of the hierarchical nature of categories have been investigated previously. Xiao [II and Frosst and Hinton 112 used decision in order make the categorization interpretable. Adaptive neural trees proposed by [113] assimilate representation learning its edges. Ji et al. [114] use attention binary neural tree distinguish fine-grained categories by attending to the nuances of these categories. However, these methods need an explicit tree structure. In this work, we let the network extract this implicit tree its own. This way, our model is also suitable when an explicit tree structure does not exist.
For more comprehensive related work, see the supplemental.
7 Conclusion
This paper seeks to address the often neglected question of defining a category. While the concept of category is readily accepted as given in the exploration of novel categories and open-world settings. the inherent subjectivity of the term poses a challenge when optimizing deep networks, which are fundamentally mathematical frameworks. To circumvent this issue, we put forth a mathematical solution to extract category codes, replacing the simplistic one-hot categorical encoding. Further, we introduce a novel framework capable of uncovering unknown categories during inference and iteratively updating its environmental representation based newly acquired knowledge. These category codes also prove beneficial handling fine-grained categorization, where attention to nuanced differences between categories is paramount. By illuminating the limitations of the subjective notion of category and recasting them within a mathematical framework, we hope to catalyze the development of less human- -ependent models.
8 Limitations
Despite the endeavors made in this work, there are several notable limitations. Foremost is our assumption of an implicit hierarchical tree underlying categorization. Furthermore, our optimization solution may not align perfectly with the actual implicit hierarchy, as it only satisfies the necessary conditions outlined discovery literature, we operate under the assumption that we have access to unlabeled data from unknown categories during training. This assumption, while convenient for model development, may not always hold true in real-world applications.
Theorem [ Lastly, akin to other approaches
the generalized category
10

---

Acknowledgments and Disclosure of Funding
This work is part of the project Real-Time Video Surveillance Search with project number 18038, which is (partly) financed by the Dutch Research Council (NWO) domain Applied and Engineering/ Sciences (TTW). Special thanks to Dr. Dennis Koelma and Dr. Efstratios Gavves for their valuable insights about conceptualizing the category to alleviate generalized category discovery.
References
[1] William Croft and D Alan Cruse. Cognitive linguistics, Cambridge University Press, 2004.
[2] George Lakoff. Women, fire, and dangerous things: What categories reveal about the mind. University of Chicago press, 2008.
[3] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition.
In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 2016.
[4] Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. Imagenet classification with deep convolutional neural networks. Communications of the ACM, 60(6):84-90, 2017.
[5] Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. Proceedings of the International Conference on Learning Representations, 2015.
[6] Gao Huang, Zhuang Liu, Laurens Van Der Maaten, and Kilian Weinberger. Densely connected convolutional networks. Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 4700-4708, 2017.
[7] Christian Szegedy. Wei Liu. Yangqing Jia, Pierre Sermanet, Scott Reed, Dragomir Anguelov, Dumitru Erhan, Vincent Vanhoucke, and Andrew Rabinovich. Going deeper with convolutions. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 1-9, 2015.
[8] Hwanjun Song, Minscok Kim, Dongmin Park, Yooju Shin, and Jac-Gi Lec. Learning from noisy labels with deep neural networks: A survey. IEEE Transactions on Neural Nenworks and Learning Systems, 2022.
[9] Jiangfan Han, Ping Luo, and Xiaogang Wang. Deep self-learning from noisy labels. In Proceedings of the JEEE/CVF international Conference on Computer Vision, pages 5138 0148,,11,2200 2019.
[10] Zhicheng Yan. Hao Zhang, Robinson Piramuthu, Vignesh Jagadeesh, Dennis DeCoste, Wei Di, and Yizhou Yu. Hd-cnn: hierarchical deep convolutional neural networks for large scale visual recognition. In Proceedings of the IEEF International Conference on Computer Vision, pages 2740-2748, 2015.
[11] Tianshui Chen, Wenxi Wu, Yuefang Gao, Le Dong, Xiaonan I Luo, and Liang Lin. Fine-grained represen- tation learning and recognition by exploiting hierarchical semantic embedding. In Proceedings of the ACM International Conference Multimedia, pages 2023-2031, 2018.
[12] Pascal Mettes, Mina Ghadimi Atigh, Martin Resser,Resse,, Jeffrey Gu, and Screna Yeung. Hyperbolic deep learning in computer vision: A survey, arXiv preprint arXiv:2305.066 0.010 2023.
[13] Mina Ghadimi Atigh, Julian Schoep, Erman Acar, Nanne Van Noord, and Pascal Mettes. Hyperbolic image segmentation. In Proceedings of the IEEF/CVF Conference on Computer Vision and Pattern Recognition, pages 4453-4462, 2022.
[14] Fangfei Lin, Bing Bai, Kun Bai. Yazhou Ren, Peng Zhao, and Zenglin Xu. Contrastive multi-view hyperbolic hierarchical clustering. In Proceedings the Thirty-First International Joint Conference on Artifiiial Intelligence, 2022.
[15] Mohammadreza Salchi, Hossein Mirzaci, Dan Hendrycks, Yixuan Li, Mohammad Hosscin Rohban, and Mohammad Sabokrou. A unified survey on anomaly, novelty, open-set, and out of-distribution detection: Solutions and future challenges. Transactions of Muchine Learning Research, 2022.
[16] Abhijit Bendale and Terrance Boult. Towards open world recognition. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 1893-1902, 2015.
[17] Abhijit Bendale and Terrance E Boult. Towards open deep networks. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 1563-1572, 2016.
[18] Walter J Scheirer, Lalit P Jain, and Terrance E Boult. Probability models for open set recognition. IEEE Transactions Pattern Analysis and Machine Intelligence, 36( 36(11):23111 1)23172223 2014.
[19] Pau Panareda Busto and Juergen Gall. Open set domain adaptation. In Proceedings of the IEEE International Conference Computer Vision, pages 754-763. 201.7 2017.
[20] Walter J Scheirer, Anderson de Rezende Rocha, Archana Sapkota, and Terrance E Boult. Toward open set recognition. IEEE Transactions Pattern Analysis and Machine Intelligence, 3577:1757-1772 2012.
11

---

[21] Kai Katsumata, Duc Minh Vo. and Hideki Nakayama. Ossgan: Open-set semi semi-supervised image generation. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. 2022.
[22] Jiaming Han, Yuqiang Ren, Jian Ding, Xingjia Pan, Ke Yan, and Guin Xia. Expanding low-density latent regions for open-set object detection. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 9591-9600, 2022.
[23] Colin Troisemaine, Vincent Lemaire, Stéphane Gosselin, Alexandre Ceiffers-Masson Joachim Flocon- Cholet, and Sandrine Vaton. Novel class discovery; an introduction and key concepts. arXiv preprint arXiv:2300. /2028, 2023.
[24] Yuyang Zhao, Zhun Zhong, Nicu Sebe, and Gim Hee Lee. Novel class discovery in semantic segmentation. In Proceedings of the IEEF/CVF Conference on Computer Vision and Pottern Recognition, 2022.
[25] Muli Yang, Yuchua Zhu, Jiaping Yu, Aming Wu, and Cheng Deng. Divide and conquer: Compositional experts for generalized novel class discovery. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 14268-14277, 2022.
[26] KJ Joseph, Sujoy Paul, Gaurav Aggarwal, Soma Biswas, Piyush Rai, Kai Han, and Vineeth N Balasubra- manian. Novel class discovery without forgetting. In European Conference on Computer Vision, pages 570 586. Springer, 2022.
[27] Sagar Vaze, Kai Han. Andrea Vedaldi, and Andrew Zisserman. Generalized category discovery. In Proceedings the IEEE/CVF Conference on Computer Vision and Pottern Recognition, 2022.
[28] Sheng Zhang, Salman Khan, Zhiqiang Shen, Muzammal Naseer, Guangyi Chen, and Fahad Khan. Prompteal: Contrastive affinity learning via auxiliary prompts for generalized novel category discovery. Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, 2023.
[29] Nan Pu, Zhun Zhong, and Nieu Sebe. Dynamic conceptional contrastive learning for generalized category discovery. Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, 2023.
[30] Florent Chiaroni, Jose Dolz, Ziko Imtiaz Masud, Amar Mitiche, and Ismail Ben Ayed. Parametric information maximization for generalized category discovery. arXiv preprint arXiv:2212.00334, 2022.
[31] Xin Wen, Bingchen Zhao, and Xiaojuan Qi. Parametric classification for generalized category discovery: A baseline study. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 16590-16600, 2023.
[32] Yixin Fei, Zhongkai Zhao, Siwei Yang, and Bingchen Zhao, Xcon: Learning with experts for fine-grained category discovery. In British Machine Vision Conference, 2022.
[33] Wenbin An, Feng Tian, Ping Chen, Siliang Tang, Qinghua Zheng, and Qian Ying Wang. Fine-grained category discovery under coarse coarse-grained supervision with hicrarchical weighted confrcootr learning. In Proceedings of the Conference on Empirical Methods in Natural Language Processing, 2022.
[34] Yifan Zhang, Bingyi Kang, Bryan Hooi, Shuicheng Yan, and Jiashi Feng. Deep long-tailed learning: A survey. IERE Transactions on Pattern Analysis and Machine Intelligence, 2023.
[35] Yingjun Du, Jiayi Shen, Xiantong Zhen, and Cees GM Snock. Superdisco: Super-class discovery improves visual recognition for the long-tail. Proceedings of the IEEF/CVF Conference on Computer Vision and Pattern Recognition, 2023.
[36] Yingxiao Du and Jianxin Wu. No one left behind: Improving the worst categories in long-tailed learning. Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, 2023.
[37] Sumyeong Ahn, Jongwoo Ko, and Se- le-Young Yun. Cuda: Curriculum of data augmentation for long-tailed recognition. In Proceedings of the International Conference on Learning Representations, 2023.
[38] Haley A Vlach. How we categorize objects is related to how we remember them: The shape bias as a memory bias. Journal of Experimental Child Psychology, 152:12 1020--00222 2016.
[39] Thomas J Palmeri and Isabel Gauthier. Visual object understanding. Nature Reviews Neuroscience, 5(4):
291 291-303, 2004.
[40] Alec Scharff, John Palmer, and Cathleen M Moore. Evidence of fixed capacity in visual object categoriza- tion. Psychonomic bulletin & review, 18:713-721, 2011.
[41] Sandra Reinert, Mark Hübener, Tobias Bonhoeffer, and Pieter M Goltstein. Mouse prefrontal cortex represents learned rules for categorization. Nature, 593(7859):411 417, 2021.
[42] Pieter M Goltstein, Sandra Reinert, Tobias Bonhoeffer, and Mark Hübener. Mouse visual cortex areas represent perceptual and semantic features of learned visual categories. Nature Neuroscience, 24(10): 2021.
12

---

[43] Nakul Yadav, Chelsea Noble, James E Niemeyer, Andrea Terceros, Jonathan Victor, Conor Liston, and Priyamvada Rajasethupathy. Prefrontal feature representations drive memory recall. Nature, 608(7921): 153-160, 2022.
[44] Eun Jin Sim and Markus Kiefer. Category-rclated brain activity natural categorics is associated with the retrieval of visual features: Evidence from repetition effects during visual and functional judgments. Cognitive Brain Research, 24(2)260-273, 2005.
[45] Glyn W Humphreys and Emer ME Forde. Hierarchies, similarity, and interactivity in object recognition: rccogittoon.catteoryy.oo 453 2001.
neuropsychological deficits. Behavioral and Brain Sciences, 24(3):
[46] Sander Van de Crays, Kris Evers, Ruth Van der Hallen, Lien Van Eylen, Bart Bocts, Lee De-Wit, and Johan Wagemans. Precise minds uncertain worlds: predictive coding in autism. Psychological Review, (4)(6)6 2014.
[47] Hermann Haken, Brain dynamicx: synchronization and activity patterns in pulse-coupled neural nets with delays and noise. Springer Science & Business Media, 2006.
[48] Edward Smith, Edward J Shoben, and Lance Rips. Structure and process semantic memory: featural model for semantic decisions. Psychological Review, 81(3):214, 1974.
[49] James DiCarlo, Davide Zoccolan, and Nicole Rust. How does the brain solve visual object recognition? Neuron, 73())415-434, 2012.
[50] Thomas M Cover. Elements of information theory. John Wiley & Sons, 1999.
[51] Claude E Shannon. A mathematical theory of communication. The Bell system technical journal, 27(3): 379-423, 1948.
[52] Naftali Tishby, Fernando C Pereira, and William Bialek. The information bottleneck method. arXiv preprint physics/0040057. 2000.
[53] Mehdi Aghagolzadeh, Hamid Soltanian-Zadch, B Araabi, and Ali Aghagolzadch. A hicrarchical clustering based mutual information maximization. In IEEE International Conference Image Processing, volume 1, pages 1-277, 2007.
[54] Ming Li, Jonathan H Badger, Xin Chen, Sam Kwong, Paul Kearney and Haoyong Zhang, An information- based sequence distance and its application whole mitochondrial genome phylogeny. Bioinformatics, 17(2):149- 154, 2001.
[55] Ming Li, Xin Chen, Xin Li, Bin Ma, and Paul MB Vitányi. The similarity metrie. IEEE Transactions on Information Theory, 50( 12):325--3264, 2004.
[56] Alexander Kraskov, Harald Stöghauer, and Peter Grassherger. Estimating mutual information. Physical review E, 69(6)066118. 2004.
[57] Alan Mathison Turing et al. On computable numbers, with an application to the entscheidungsproblem.. J. of Math, 58(345-363):5, 1936.
[58] Paul MB Vitányi. How incomputable is kolmogorov complexity? Entropy, 22(4):408, 2020.
[59] Ray Solomonoff. formal theory of inductive inference, part Information and Control, 7(1):1-22, 1964.
[60] Ray J Solomonoff. formal theory of inductive inference, part ii Information and control, 7(2):224-254 1964.
[61] Andrei Kolmogorov. Three approaches to the quantitative definition of information. Problems of Information Transmission, 1(1):177, 1965.
[62] Yoshua Bengio, Nicholas Léonard, and Aaron Courville. Estimating or propagating gradients through stochastic neurons for conditional computation. arXiv preprint arXiv:1308.5 2013.
[63] Geoffrey E Hinton. practical guide training restricted bolızmann machines. In Neural Networks:
Tricks of the Trade: Second Edition, pages 599-619 Springer, 2012.
[64] Aaron den Oord, Yazhe Li, and Oriol Vinyals. Representation learning with contrastive predictive coding. arXiv preprint arXiv: /807 03748, 2018.
[65] Alex Krizhevsky, Geoffrey Hinton, et al. Leamingg multiple layers of features from tiny images. 2009.
[66] Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large-scale hierarchical image database. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages
2009.
[67] Catherine Wah, Steve Branson, Peter Welinder, Pietro Perona, and Serge Belongie. The caltech-ucsd birds-200-201 dataset. 2011.
13

---

[68] Subhransu Maji, Esa Rahtu, Juho Kannala. Matthew Blaschko, and Andrea Vedaldi. Fine-grained visual classification of aircraft. arXiv preprint arXiv:1306.5151. 2013.
[69] Jonathan Krause. Michael Stark, Jia Deng, and Li Fei-Fei. 3d object representations for fnn-ggriied categorization. In Proceedings of the IEEE International Conference on Computer Vision Workshops, pages 554 561, 2013.
[70] Omkar M Parkhi, Andrea Vedaldi, Andrew Zisserman, and CV Jawahar. Cats and dogs. In Proceedings of the IEEE Conference on Computer Vision and Puttern Recognition, pages 3498-3503 IEEE, 2012.
[71] Kiat Chuan Tan, Yulong Liu, Barbara Ambrose, Melissa Tulig. and Serge Belongie. The herbarium challenge 2019 dataset. arXiv preprint (.XX:v:9966.0377 2019.
[72] Mathilde Caron, Hugo Touvron, Ishan Misra, Hervé Jégou, Julien Mairal, Piotr Bojanowski, and Armand Joulin. Emerging properties in self-supervised vision transformers. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 9650-9660, 2021.
[73] MB Wright. Speeding up the Hungarian algorithm. Computers & Operations Research, 17(1):95-96,
1990.
[74] David Arthur and Sergei Vassilvitskii. K-means++ the advantages of careful seeding. In Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, pages 1027-1035, 2007.
[75] Kai Han, Sylvestre-Alvise Rehuffi, Schastien Ehrhardt, Andrea Vedaldi, and Andrew Zisserman. Auto- matically discovering and learning new visual categories with ranking statisties. Proceedings of the International Conference on Learning Representations, 2020.
[76] Enrico Fini, Enver Sangineto, Stéphane Lathuilière, Zhun Zhong, Moin Nabi, and Elisa Ricci. unified objective for novel class discovery. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 9284-9297 9292, 2021.
[77] Kaidi Cao, Maria Brbic, and Jure Leskovec. Open-world semi-supervised learning. In Proceedings of the International Conference on Learning Representations, 2022.
[78] Bingchen Zhao, Xin Wen, and Kai Han. Learning supervisd gaussian mixture models for general- ized category discnvery. In Proceedings of the IEEF/CVF International Conference on Computer Vision, 2023.
[79] Kai Han, Andrea Vedaldi, and Andrew Zisserman. Learning to discower novel visual categories via deep transfer clustering. In Proceedings of the IEEE/CVF International Conference Computer Vision, pages 8401-8409, 2019.
[80] Zhun Zhong, Enrico Fini, Subhankar Roy, Zhiming Luo, Elisa Ricci, and Nicu Sebe. Neighborhood contrastive learning for novel class discovery. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 10867-10875, 2021.
[81] Junyuan Xie, Ross Girshick, and Ali Farhadi. Unsupervised deep embedding for clustering analysis. In International Conference on Machine Learning, pages 478 487, PMLR, 2016.
[82] Bingchen Zhao and Kai Han. Novel visual category discovery with dual ranking statisties and mutual knowledge distillation. Advances in Neural Information Processing Systems, 34:22982 14422992-22994, 2021.
[83] Zhun Zhong, Linchao Zhu, Zhiming Luo, Shaozi Li. Yi Yang, and Nicu Sebe. Openmix: Reviving known knowledge for discovering novel visual categories in open world. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 9462-9470, 2021.
[84] Subhankar Roy, Mingxuan Liu, Zhun Zhong, Nicu Sebe, and Elisa Ricci. Class-incremente novel class discovery. In European Conference on Computer Vision, pages 317-333 333.. Springer, 2022.
[85] Mamshad Nayeem Rizve, Navid Kardan, and Mubarak Shah. Towards realistic semi-supervised learning. European Conference on Computer Vision, pages 437-455. Springer, 2022.
[86] Wenbin Li, Zhichen Fan, Jing Huo, and Yang Gao. Modeling inter-class and intra-class constraints in novel class discovery. In Proceedings of the IEFF/CVE Conference on Computer Vision and Pateern Recognition, pages 3449-3458, 2023.
[87] Muli Yang, Liancheng Wang, Cheng Deng, and Hanwang Zhang, Bootstrap your own prior: Towards distribution-agnosiic novel class discovery. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 3459-3468, 2023.
[88] Luigi Riz, Cristiano Saltori, Elisa Ricci, and Fabio Poiesi. Novel class discovery for 3d point cloud semantic segmentation. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 9393 9402, 2023.
[89] Peiyan Gu, Chuyu Zhang, Ruijie Xu, and Xuming He. Class-relation knowledge distillation for novel class discovery. In Proceedings of the International Conference Learning Representations, 2023.
14

---

[90] Yiyou Sun, Zhenmei Shi, Yingyu Liang, and Yixuan Li. When and how does known class help discover unknown ones? provable understanding through spectral analysis. In International Conference on Muchine Learning. PMLR, 2023.
[91] Zhang Chuyu, Xu Ruijie, and He Xuming. Novel class discovery for long-tailed recognition. arXiv preprint arXiv:2308. 02989, 2023.
[92] Colin Troisemaine, Joachim Flocon-Cholet, Stéphane Gosselin, Alexandre Ceiffers-Masson Sandrine Vaton, and Vincent Lemaire. An interactive interface for novel class discovery in tabular data, arXiv preprint arXiv:2306. 0023300..9991 /2919, 2023.
[93] Ziyun Li, Jona Otholt, Ben Dai, Di Hu, Christoph Meinel, and Haojin Yang. Supervised knowledge may hurt novel class discovery performance. arXiv preprint arXiv:2306.03648, 2023.
[94] Jiaming Liu, Yangqiming Wang, Tongze Zhang. Yulu Fan, Qinli Yang, and Junming Shao. Open-world semi sumi-sueeeised novel class discovery. arXiv preprint arXiv:2305. 2023.
[95] Hanang Chi, Feng Liu, Bo Han, Wenjing Yang, Long Lan, Tongliang I Liu, Gang Niu, Mingyuan Zhou, and Masashi Sugiyama. Meta discovery: Learning to discover novel classes given very limited data. In Proceedings of the International Conference on Learning Representations. 2022.
[96] Xinwei Zhang, Jianwen Jiang, Yutong Feng, Zhi-Fan Wu, Xibin Zhao, Hai Wan, Mingqian Tang. Rong Jin, and Yue Gao. Grow and merge: A unified framework for continuous categories discovery. In Advances in Neural Information Processing Systems, 2022.
[97] Qing Yu, Daiki Ikami, Go Irie, and Kiyoharu Aizawa. Self-labeling framework for novel category discovery over domains. In Proceedings of the AAAI Conference on Artificial Intelligence, 2022.
[98] KJ Joseph. Sujoy Paul, Gaurav Aggarwal, Soma Biswas, Piyush Rai, Kai Han, and Vineeth Balasubra- manian. Spacing loss for discovering novel categories. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 3761-3766, 2022.
[99] Ziyun Li, Jona Otholt, Ben Dai, Christoph Meinel, Haojin Yang, et al. A closer look at novel class discovery from the labeled set. arXiv preprint 22X00:2000.09120, 2022.
[100] Sagar Vaze, Kai Han, Andrea Vedaldi, and Andrew Zisserman. Open-set recognition: A good closed-set classifier all you need. Proceedings of the International Conference on Learning Representations, 2022.
[101] Shaozhe Hao, Kai Han, and Kwan- Yee K Wong. Cipr:
An efficient framework with cross-instance positive relations for generalized category discovery. arXiv preprint arXiv:2304.066: 06928, 2023.
[102] Ruoyi Du, Dongliang Chang. Kongming Liang, Timothy Hospedales, Yi-Zhe Song, and Zhanyu Ma. On-the-fly fly category discovery. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 11691-11700 11700, 2023.
[103] Jianhong Bai. Zuozhu Liu, Hualiang Wang. Ruizhe Chen, Lianrui Mu, Xiaomeng Li. Joey Tianyi Zhou, Yang Feng, Jian Wu, and Haoji Hu. Towards distribution agnostic generalized category discovery. In Advances in Neural Information Processing Systems, 2023.
[104] Sagar Vaze, Andrea Vedaldi. and Andrew Zisserman. Improving category discovery when no representa- tion rules them all. Advances in Neural Information Processing Systems, 2023.
[105] Bingchen Zhao and Oisin Mac Aodha. Incremental generalized category discovery. In Proceedings of the IEEE/CVF International Conference on Computer Vision, 2023.
[106] Florent Chiaroni, Jose Dolz. Ziko Imtiaz Masud, Amar Mitiche, and Ismail Ben Ayed. Parametric infor- mation maximization for generalized category discovery. In Proceedings of the IEFF/CVF International Conference on Computer Vision, pages 1729-1739, 2023.
[107] Yanan Wu, Zhixiang Chi, Yang Wang, and Songhe Feng. Metaged: Learning to continually learn in generalized category discovery. In Proceedings of the IEEE/CVF International Conference Computer Vision, pages 1665-1665, 2023.
[108] Hyungmin Kim, Sungho Suh, Daehwan Kim, Daun Jeong, Hansang Cho, and Junmo Kim. Proxy anchor- unsupervised learning for continuous generalized category discovery. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 16688-16697) 2023.
[109] Wenbin An, Feng Tian, Qinghua Zheng, Wei Ding, DianYing Wang, and Ping Chen. Generalized category discovery with decoupled prototypical network. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 37, 2023.
[110] Sagar Vaze, Andrea Vedaldi, and Andrew Zisserman. No representation rules them all in category discovery. Advances in Neural Information Processing Systems 37, 2023.
[111] Han Xiao. Ndt: neual decision tree towards fully functioned neural graph. arXiv preprint 1012:477.. 2017.
15

---

[112] Nicholas Frosst and Geoffrey Hinton. Distilling neural network into soft decision tree. arXiv preprint arX1v:1711.0988, 2017.
[113] Ryutaro Tanno, Kai Arulkumaran, Daniel Alexander, Antonio Criminisi, and Aditya Nori. Adaptive neural trees. In International Conference on Machine Learning, pages 6166 6175. PMLR, 2019.
[114] Ruyi Ji, Longyin Wen. Libo Zhang. Dawei Du, Yanjun Wu, Chen Zhao, Xianglong Liu, and Feiyue Huang. Attention convolutional binary neural tree for fine-grained visual categorization. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 10468-10477, 2020.
[115] Steven Evans and Daniel Lanoue. Recovering a tree from the lengths of subtrees spanned by randomly chosen sequence of leaves. Advances Applied Mathematics, 96:39 75, 2018.
[116] Peter D Grünwald, Paul MB Vitányi. al. Algorithmic information theory. Handbook of the Philosophy of Information, pages 281 1-300, 2008.
[117] Aladin Virmaux and Kevin Scaman. Lipschitz regularity of deep neural networks: analysis and efficient estimation. Advances in Neural Information Processing Systems, 31, 2018.
[118] Dan Hendrycks and Kevin Gimpel. Gaussian error linear units (gelus). arXiv preprint arXiv:1606.08411
2016.
[119] Poojan Oza and Vishal M Patel. C2ae: Class conditioned auto-encoder for open-set recognition. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 2307-2316. 2019.
[120] Ryota Yoshihashi, Wen Shao, Rei Kawakami, Shaodi You, Makoto lida, and Takeshi Naemura. Classfication-rcoosttutiiooo learning for open-set recognition. Proceedings of the IEEE/CVF Confer- ence on Computer Vision and Pattern Recognition, pages 4016 4025, 2019.
[121] Guangyao Chen, Peixi Peng. Xiangqian Wang. and Yonghong Tian. Adversarial reciprocal points learning for open set recognition. IEEE Transactions on Pattern Analysis and Machine Intelligence, 44(11); 8065-8081, 2021.
[122] Guangyao Chen, Limeng Qiao, Yemin Shi, Peixi Peng, Jia Li, Tiejun Huang, Shiliang Pu, and Yonghong Tian. Learning open set network with discriminative reciprocal points. European Conference on Computer Vision, pages 507-522. Springer, 2020.
[123] Yu Shu, Yemin Shi, Yaowei Wang. Tiejun Huang, and Yonghong Tian. P-odn: Prototype-based open deep network for open recognition. Scientific reports, 10(1):7146, 2020.
[124] ZongYuan Yuan Ge, Sergey Demyanov, Zetao Chen, and Rahil Gamavi. Generative openmax for multi-class open set classification. arXiv preprint arXiv:1707.00 10t::00770748, 2017.
[125] Shu Kong and Deva Ramanan. Opengan: Open-set recognition via open data generation. Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 813-822, 2021.
[126] Lawrence Neal, Matthew Olson, Xiaoli Fern, Weng-Keed Wong. and Fuxin Li. Open learning with counterfactual images. European Conference on Computer Vision, pages 613-628, 2018.
[127] Zhongqi Yue, Tan Wang. Qianru Sun, Xian-Sheng Hua, and Hanwang Zhang. Counterfactual zero-shot and open-set visual recognition. In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition, pages 15404-155 15404-1444,, 2021.
16

---

A Theory
A.1 Notation and Definitions
Let us first formalize notation and definition for the rest of the section. Some definitions might overlap with the notations in the main paper. However, we repeat them here for ease of access.
Probabilistic Notations. We denote the input random variable with X and the category random variable with C. The category code random variable, which we define as the embedding sequence of input X is denoted by 2' = ... = in which superscript shows the ith sample, while subscript shows the digit position in the code sequence.
Coding Notations. Let C' be a countable set, we use C* to show all possible finite sequences using the members of this set. For instance: {0, 1 {e, 0, 1, 00, 01, 10, 11,... } in which e empty word. The length of each sequence z, which we show with ((z), equals the number of digits present in that sequence. For instance, for the sequence [(01010)
Shannon Information Theory Notations. We denote the Shannon entropy or entropy of the random variable X with (X). It measures the randomness of values of X when we only have knowledge about its distribution P. It also measures the minimum number of bits required on average to transmit encode the values drawn from this probability distribution [50, (T). The conditional entropy of a random variable X given random variable Z is shown by H (X Z), which states the amount of randomness we expect to see from X after observing Z. In addition, I ((x; Z) indicates the mutual information between random variables X and Z [50] [S], which measures the amount of information we can obtain for one random variable by observing the other one. Note that contrary to H mutual information is symmetric.
Algorithmic Information Theory Notations. Similar to Shannon's 's information theory, Kolmogorov Complexity or Algorithmic Information [heory[59661 measures the shortest length to describe an object. Their difference is that Shannon's information considers that the objects be described by the characteristic of the source that produces them, but Kolmogorov Complexity considers that the description of each object in isolation can be used describe it with minimum length. For example, a binary string consisting of one thousand zeros might be assigned a code based on the underlying distribution has been drawn from. However, Kolmogorov Complexity shows that we can encode this particular observation by transforming a description such as "print 0 for 1000 times". The analogon entropy is called complexity (x)). which specifies the minimum length of a sequence that can specify output for particular system. We denote the algorithmic mutual information for sequences x and z with [atg(X z), which specifies how much information about sequence x we can obtain by observing sequence
A.2 Maximizing the Algorithmic Mutual Information
Let's consider data space D=(X', Cf : E {1,...N]} where Xs are inputs and Cs are the corresponding category labels.
Lemma For each category and for X3 with C²=c, we can find binary decision tree Te that starting from its root, reaches each X' by following the decision tree path. Based on this path, we ..-c's to each X² uniquely define and retrieve it from the tree.
assign code )
Proof of Lemma 2 Since the number of examples in the dataset is finite, we can enumerate samples of category e with any arbitrary coding. We then can replace these enumerations with their binary equivalent codes. We start from root, and every time we encounter 1 in digits of these codes, we add right child node, and for 0, we add a left child node. We then continue from the child node until we reach the code's 's end. Since the number of samples with category is limited, this process should terminate, On the other hand, since the binary codes for different samples are different, these paths unique, and by the time we traverse path from the root to leaf node, we can identify the unique sample corresponding to that node. D
As mentioned in the main paper, using this Lemma, we can find at least one supertree T for the whole data space that addresses all samples which samples of the same category share a similar prefix. We can define model that provides the binary code x y/= 2f, for data input X with category e based on the path takes these eligible trees. We define these path encoding functions valid encoding defined in Definition
17

---

Definition 2 A valid encoding for input space X' and category space C is defined as an encoding that uniquely identifies every X E X. At the same time, for each category E C. it ensures that there is sequence that is shared among all members of this category but member out of the category.
Since there is no condition on how to create these trees and their subtrees, many candidate trees can address the whole data space while preserving similar prefix for the members of each category.
However, based our inspirations for how the brain does categorization, underlying tree T has a minimum average length path from the root to each node. In other words, each sample æ has the shortest description code to describe that data point while maintaining its validity. If we use a model to learn this encoding, the optimal model tree should be isomorph to the underlying tree T,
assume the ground truth
Lemma 3 For a learned binary code z' to address input X', uniquely, if the decision tree of this encoding is optimal, it is isomorph to the underlying tree T.
Proof of Lemma 3, Since the underlying tree has the minimum Kolmogorov complexity for each sample, we can extract the optimal lengths of each sample by traversing the tree. Evans and Lanoue [155] showed that a tree can be recovered from the sequence of lengths of the paths from the root to leaves the level of isomorphism. Based on our assumption about the underlying tree T, the optimal tree can not have a shorter length for any sample codes than the underlying tree. On the other hand, having longer codes contradicts its optimality. Hence the optimal tree should have similar path lengths to the underlying ground truth tree. Therefore, it is isomorphic to the underlying tree. O
Since the optimal tree with the valid encoding ă is isomorph the underlying tree, will have the necessary conditions that Theorem | provides.
Theorem For learned binary code z' to address input x'. uniquely, if the decision tree of this encoding is isomorph to underlying tree T, we will have the following necessary conditions:
1. Lolg(Z x) 2 Lalg(2 (Z: x)
Vž, ž is valid encoding for x
2. Tagg(: c) 2 Tulg(2 c)
V2, & is a valid encoding for x
Proof of Theorem
Part one: From the way T has been constructed, we know that K(x[T) I K(xTT) in which T is an arbitrary tree. From the complexity and mutual information properties, we also have Inte(z : x) K K(x) K(x|z) [16). Since é and have isomorph tree structures, then K(3) = K(z).
hence: lag (z x)) 2 Tagg(7 2)).
Part two: In any tree that is a valid encoding. all samples category should be the descendants of that node. Thus, the path length to corresponding nodes should be similar in both trees. Otherwise, the length of the path to all samples of this category will not be optimal. We can use the same logic and deduce that the subtree with the category nodes as its leaves would be isomorph for both embeddings. Let's 's denote the path from the root to category nodes with z, and from the category node to its corresponding samples with Zμ. If we assume these two paths can be considered independent, we will have K (x) = K (Z,zt)) = K(x.) + K (z..). which indicates that minimizing K (x) in the tree implies that K ((c) also should be minimized. By applying the same logic part one, we can deduce that (Z e) (Z c).
A.2.1 Shannon Mutual Information Approximation
Optimization in Theorem T is generally not computable (8.61.. However, We can approximate these requirements using Shannon mutual information instead. Let's consider two functions f and g.
such that both are {0, 1}* + R. For these functions, f & g means that there exists a constant K, such that/ f S g + c, when both f < and & hold, then f = 116].
Theorem 2 [116] Let P be a computable probability distribution on (0, x (0. Then:
- K(P) Σ
p(z, 2) Lag (x: 2) I(X; Z) + 22(P)
(9)
2
18

---

This theorem states that the expected value of algorithmic mutual information is close to its proba- bilistic counterpart. This means that if we maximize the Shannon information, we also approximately maximize the algorithmic information and vice versa.
Since Shannon entropy does not consider the inner regularity of the symbols it codes, make each sequence meaningful from a probabilistic perspective, we convert each sequence to an equivalent random variable number by considering its binary digit representation. To this end, consider
m zj Z'= >>=>= k 2 which is number between 0 and 1. Note that we can recover the sequence from the value of this random variable. Since the differences in the first bits affect the number more, for different error thresholds, Shannon's information will focus the initial bits more. In dealing with real-world data, the first bits encoding of a category sequence are more valuable than later ones due to the hierarchical nature of categories. Furthermore, with this tweak, we equip Shannon's 's model with a knowledge of different positions of digits in a sequence. To replace the first item of Theorem ! by its equivalent Shannon mutual information, must also ensure that has the minimum length. For the moment, let's assume we know this length by the function [(X")=l,. Instead of Z', we can
consider its truncated form Z = Σk=1 ze. This term, which we call the address loss function, defined as follows:
Cadr
Σ 1(x: s.t. Z
2k 2
and Vk. 2 E (0,
(10)
We can approximate this optimization with reconstruction or contrastive loss.
A.2.2 Approximation with Reconstruction Loss
Let's approximate the maximization of the mutual information by minimizing the LMSE of the reconstruction from the code Suppose that D(X) is the decoder function, and it is Lipschitz continuous function, which a valid assumption for most deep networks with conventional activation functions 117.
We can find upper bound for LMSE using Lemma B
Lemma Suppose that D(X) is a Lipschitz continuous function with Lipschitz constant K, then we will have the following upper bound for LMSE:
(MSE(X)
1 SK N 2=
Σ 2-21
Proof of Lemma Let's consider the LMSE loss for the reconstruction X from the code Z We denote reconstruction from the truncated category code Zi, with Xi,
N
CMSE = N
X
x 1|
we expand this loss, we will have the following:
LMSE(X) (X)
Σ
D(Z x 1
D
N
- - 1
2
k=
Let's assume the optimal model can reconstruct X using the entire code length 2 i.e. X D # Now let's replace this in the equation:
24
LarsE(X)
أ=ル
19

---

Given that ((X is a Lipschitz continuous function with the Lipschitz constant K, then we will have the following:
4
(MSE(X) S
|| k=0
N
1=0
N
k
2
2
||
N
1=0
2
2-2
N
Lemma 3 indicates that to minimize the upper bound on LMSE. we should aim for codes with maximum length, which can also be seen intuitively. The more length of latent code preserve, the more accurate the reconstruction would be. This is in direct contrast with the length minimization of the algorithmic mutual information. So, the tradeoff between these two objectives defines the optimal final length of the category codes.
A.2.3 Approximation with Contrastive Loss
One of the advantages of contrastive learning is find representation that maximizes the mutual information with the input [64]. More precisely, if for input X we show the hidden representation learning Z', that is learned contrastively by minimizing the InfoNCE loss, [64] showed that the following lower bound on mutual information exists:
T(x;; Z 2 log(N) LN-
(11)
Here, LN is the InfoNCE loss, and N indicates the sample size consisting of one positive and N 1 negative samples. Equation shows that contrastive learning with the InfoNCE loss can be a suitable choice for minimizing the Lade in Equation TO We will this levels. Let's consider that Z' has dimension d, and each latent variable =f. can take up n different values. The complexity of the feature space for this latent variable would be O(n)), then the number of structurally different binary trees for this feature space would be OCC,,), in which C2 is the ith Catalan number, which asymptotically grows as (44)). Hence the number of possible binary taxonomies for the categories will be ((4""), So minimizing and, lesser degree, d, will be the most effective way to limit the number of possible binary trees. Since our model and the amount of training data is bounded, we must minimize the possible search space while still providing reasonable performance. On the other hand, the input feature space X with possible values and dimension D has O(N") possible states, and to cover it completely, we can not arbitrarily decrease d and Note that for a nearly continuous function N - xc, the probability of a random discrete tree to fully covering this space would be near zero.
advantage on two different
A.3 Category Code Length Minimization
In the main paper, we indicate the code length loss Liength. which we define Liength 1V Σi= 4.- To minimize this loss, define binary mask sequence m m mn, simulate the subscript property of 4,. We discussed minimizing the L, Norm for the weighted version of the mask, which denote with m² (mm)2)))mm2))) ... (m 2"). This will ensure the requirements because adding one extra bit has an equivalent loss of all previous bits.
N
Liength PJ
m
Ip.
(12)
N
1=0
Lemma 4 Consider the weighted mask m= 2-) (m222) ... 24) where mys are 0 or 1. Con- sider the norm in llp where p 2 1, the rightmost digit contributes more the norm than the entire left sequence.
20

---

Proof of Lemma 4 Let's consider the loss function for mask iñ-(m12) 2 (0mm11")2223) (mz2?) ... (mL22) and let's denote the rightmost index, with k, for simplicity we consider the m Ipp-
m 20
Σ
(m 2 (m&2* +
2
j=U
jmk-1
given that my 0, Vj k and my = 1, we will have:
R 1
(m)21)² + 2 +0
==
now let's compare the two subparts of the right-hand side with each other:
2 2
E m S > (21p)
2kp
Hence Length tries to minimize the position of the rightmost 1, simulating the cutting length subscript.
A.3.1 Satisfying Binary Constraints.
In the main paper, we stated that we have two conditions, Code Constraint: 2/ or a =1 and Mask Constraint Vm,, m 0 m = We formulate each constraint equivalent Lagrangian function to make sure they are satisfied. For the binary code constraint we consider (=))==))==z2))) constraint, we have fauaa (1-))))))
=00 which only zero if =0=0 or 11-1.. Similarly, for the binary mask To ensure these constraints are satisfied, we optimize them with the Lagrangian function of the overall loss. Consider the Lagrangian function for Lutal.
L(Cosial: 77, 14) Leotal + T/Coodeccond + JLLmask
This lagrangian function ensures that constraints are satisfied for 1j > +oo and - +.c. Note that our method uses tanh activation function which has been mapped between and 1, to produce my and zg, so the conditions are always greater or equal to zero. For an unbounded output, we can consider the squared version of constraint functions to ensure that constraints will be satisfied. This shows how we reach the final unconstrained loss function in the paper.
B
Experiments B.1
Dataset Details
To acquire the train and test splits, we follow (27)
We subsample the training dataset in ratio of 50% of known categories at the train and all samples of unknown categories. For all datasets except CIFARI00, we consider 50% of categories known categories at training time. For CIFARI00 as in 80% of the categories are known during training time. A summary of dataset statistics and their
27
train test splits is shown in Table
CIFAR10/100 are coarse-grained datasets consisting of general categories such as car, ship, airplane, truck, horse, deer, cat, dog, frog and bird.
ImageNet-100 subset of 100 categories from the coarse-grained ImageNet [66] dataset.
CUB or the Caltech-UCSS Birds-200-2011 (CUB-200-2011) 167 is one of the most used datasets for fine-grained image recognition. contains different bird species, which should be distinguished by relying on subtle details.
FGVC-Aireraft Fine-Graid Grained Visual Classification of Aireraft [68] dataset is another fine fine-grained dataset, which, instead of animals, relies on airplanes. This might be challenging for image recognition models since, in this dataset, structure changes with design.
SCars or Stanford Cars [69] is fine-grained dataset of different brands of cars. This challenging since the same brand of cars can look different from different angles with different colors.
21

---

Table 6: Statistics of datasets and their data splits for the generalized category discovery task. The first three datasets are coarse-gen coarse-grained image classification datasets, while the next four are fine-grained datasets. The Herbarium19 dataset both finegraineed and long-tailed.
Labelled
Unlabelled
Dataset
#Images
#Categories
#Images
#Categories
CIFAR-10 65
12.5K
5
37.5K
10
CIFAR-100 66
20.0K
80
30.0K
100
ImageNet-100 666
31.9K
50
95.3K
100
CUB-200 667
1.5K
100
4.5K
200
SCars 699
2.0K
98
6.
196
Aircraft 66
3.4K
50
6.6K
100
Oxford-PP
0.9K
19
2.7K
37
Herbarium
8.9K
341
25.4K
683
Oxford-Pet 70 is fine-grained dataset of different species of cats and dogs. This is challenging since the amount of data is very limited in this dataset, which makes it prone to overfitting.
Herbarium 19 77] is botanical research dataset about different types of plants. Due to its long-tailed alongside fine- tne-grained nature, it is a challenging dataset for discovering novel categories.
B.2 Implementation details
In this section, we provide our implementation details for each block separately. As mentioned in the main paper, the final loss function that we use to train the model is:
Lanal Lude 5Liength + nLCat + Geoodecoood + J.Lmusk cond
(13)
In which the loss Lads is:
Lade aa + _CC_cooe-
(14)
In this formula, Lc is the loss function that 27 suggested, use the same hyperparameters as their defaults for this loss. Hence, we only expand on LC_codee code:
Ladr = aLc in + B(( C" + Acale Ce codde)
(15)
In the scope of our experimentation, it was assumed by default that a=1 and = The code generation process introduces certain noise level, potentially leading to confusion in the model, particularly in fine-gre tne-ggrined data. To mitigate this, we integrated smoothing hyperparameter within our contrastive learning framework, aiming balance the noise impact and avert excessive confidence in the generated code, for datasets such as CUB and Pet, the smoothing factor was set at 1, whereas for SCars, Aircraft, and Herb datasets, was adjusted 0.1. contrast, we did not apply smoothing for generic datasets like CIFAR 10/100 and ImageNet, where label noise is less significant.
Furthermore, in dealing with fine- greingr data, we opted fine-tune the final DINO model. This approach differs from our strategy for generic datasets, where only the last block underwent fine-tuning. Additionally, we employed semi-supervised k-means every epoch derive pseudo-labels from unlabeled data. These pseudo-labete were then used in our supervised contrastive learning process as a supervisory signal. is important note that in supervised contrastive learning, the primary requirement is that paired samples belong to the same class, allowing us to disregard discrepancies between novel class pseudo-labels and their actual ground truth values. Furthermore, instead of cosine similarity for contrastive learning, we adopt Euclidean distance, better approximation for the category problem. Finally, for balanced datasets, we use the balanced version of k-means for remi-supervised k-means.
blocks of the
22

---

Code Generator. To create this block, we use fully connected network with GeLU activation functions [T88]. Then, we apply a tanh activation function tanh(ar) in which a is a hyperparameter showing the model's s age. We expect that as the model's i age increases or, in other words, in later epochs, the model will be more decisive because of sharper transitions from to Hence, we will have a stronger binary dichotomy for code values. Also, since contrastive learning makes the different samples as far as possible, this causes a problem for the Code Generator because the feature space will not smoothly transition from different samples of the same category, especially for fine-grained datasets. To alleviate this problem, we use a label smoothing hyperparameter in the contrastive objective to help make feature space smoother, which will require a smaller tree for encoding. Since the model should distinguish Os for the mask from Os of the code, we do not adjust the code generator to 0 and 1s and consider the 1 and values in practice.
Code Masker. The Code Masker block is a fully connected network with tanh activation functions at the end, which are adjusted to be O and 1s. We also consider the aging hyperparameter for the tanh activation function in the masking block. In the beginning, since codes are not learned, masking the embedding space might hamper its learning ability. To solve this, we start masker with all one's me's entries and gradually decrease it with epochs. Hence, the activation function that is applied to the masker would be tanh(x + ) in which is the aging parameter. In practice, we observed that norm one is stable enough in this loss function while also truncating codes at reasonable length. Since Linngth grows exponentially with code length, it will mask most of the code. For fine-grained datasets, this could be detrimental for very similar categories. To alleviate this problem, instead of using 2 as a positional base, we decrease it with each epoch to 2 Napess So, at the end of training, the values of all positions are the same. This allows the model to encode more levels to the tree. Since we start with the base 2, we are constructing the tree with a focus on nodes near the root at the start and the leaves at the end of training.
Categorizer. We use a fully connected network for this block and train it with the one-hot encoding of the labeled samples. This module receives the truncated codes to predict the labeled data. This module cannot categorize labeled data if the masker truncates too much information. Hence, it creates error signals that prevent the masker from truncating too much. This part of the network is arbitrary, and we showed in ablations that we can ignore this module without supervision signals.
B.3 Further Ablations
Feature Space Visualization. Figure 4 iillustrates the tSNE visualizations for different embedding extracted from our model. While our model's features form separate clusters, our label embedding. which is the raw code feature before binarization, makes these clusters distinctive. After that, binary embedding enhances this separation while condensing the cluster by making samples of clusters closer to each other, which is evident for the bird cluster shown in yellow. Because of its 0 or 1 nature, semantic similarity will affect the binary embedding more than visual similarity. Finally, our code embedding, which assigns positional values to the extracted binary embedding, shows indirectly that to have the most efficient code, our model should span the code space as much as possible, which explains the porous nature of these clusters.
B.4 Extracting the Implicit Tree from the Model
Suppose that the generated feature vector by the network for sample X is 2022 T. where k is the dimension of the code embedding or, equivalently, the depth of our implicit hierarchy tree. Using appropriate activation functions, we can assume that v, is binary. The unsupervised contrastive loss forces the model to make the associated code to each sample unique. So if X' is not equivalent to X. For the
X or one of its augmentations, its code 26011 ... 2' will differ from the code assigned supervised contrastive loss, instead of considering the code, we consider a sequence by assigning different positional values to each bit so the code xg41 T. can be considered as the binary number 0.ro21 ... Zz. Then, the supervised contrastive loss aims to minimize the difference between these assigned binary numbers. This means our model learns to use the first digits for discriminative information while pushing the specific information about each sample to the last digits. Then, our masker learns to minimize the number of discriminative digits. Our Theorem states that, finally, the embedded tree that the model learns this way is a good approximation of the optimal tree. Ultimately, our model generates a code for each sample, and we consider each code as a binary tree traverse from the root to the leaf. Hence, the codes delineate our tree's structure and binary classification that
23

---

arplane
arplane
bard
shipe
ships
Druck
(a) Feature Embedding
Label Embedding
arplane
airlann
crr
Bird
berd
cat
cat
doer
deer
dog
horse
(c) Binary Embedding
(d) Code Embedding
Figure t-SNE plot for different embeddings in our model. (a) Feature embedding. The embedding after the projection head which is used by contrastive loss to maximize the representation information. (b) Label embedding. The embedding after generating code features used by unsupervised contrastive loss for codes. (c) Binary embedding. The embedding by converting code features to binary sequence using tanh activation functions and binary conditions. final truncated code which is generated by assigning positional values to the binary sequence and truncating the produced code using the masker network.
(d) Code embedding. The
happens at each node. Since our approach enables the model to use the initial bits for supervised contrastive learning and the last bits for unsupervised contrastive learning, we can benefit from their synergic advantages while preventing them from interfering with each other.
C Related Works
C.1 Open Set Recognition
The first sparks of the requirement for models that handle real-world data were introduced by Scheirer et al. [20] and following works of [16] 18). The first application of deep networks to address this problem was presented by OpenMax [17] The main goal for open-set recognition is to distinguish known categories from each other while rejecting samples from novel categories. Hence many open-set methods rely on simulating this notion of otherness, either through large reconstruction errors [119 [20] distance from set of prototypes [I] [23] or by distinguishing the adversarially generated samples [27]. One of the shortcomings of open set recognition is that all new classes will be discarded.
C.2 Novel Class Discovery
To overcome open set recognition shortcomings, novel class discovery aims to benefit from the vast knowledge of the unknown realm and infer the categories. can be traced back to 77),, where they used the knowledge from labeled data to infer the unknown categories. Following this work, [80] solidified the novel class discovery as a new specific problem. The main goal of novel class discovery is to transfer the implicit category structure from the known categories to infer unknown categories [9]. Despite this, the novel class discovery has a limiting assumption that test data only consists of novel categories.
24 26 75 76
24

---

C.3 Generalized Category Discovery
For more realistic setting. Generalized Category Discovery considers both known and old categories at the test time. This nascent problem was introduced by [27] and concurrently under the name open-world semi-supervised learning by [77] In this scenario, while the model should not lose its grasp on old categories, it must discover novel categories in test time. This adds an extra challenge because when we adapt the novel class discovery methods this scenario, they try to be biased to either novel or old categories and miss the other group. There has been a recent surge of interest in generalized category discovery [1 78 10T In this work, instead of viewing categories as an end, we investigated the fundamental question of how to conceptualize category itself.
C.4 Binary Tree Distillation
Benefiting from the hierarchical nature of categories has been investigated previously. Xiao |
and Frosst and Hinton [112] used a decision tree in order to make the categorization interpretable and as series of decisions. Adaptive neural trees proposed by [13] assimilate representation learning to its edges. Ji et al. [114] use attention binary neural tree to distinguish fine-grained categories by
attending the nuances of these categories. However, these methods need explicit tree structure.
In this work, we let the network extract this implicit tree its own. This way, our model is also suitable when an explicit tree structure does not exist.
25


Reviews:
[{"review_id": "L5zXczfaxi", "reviewer": "Reviewer_xjo1", "summary": "This paper tackles the problem of generalized category discovery (GCD) by reframing the concept of a category with an implicit category code tree, which addresses three problems of conventional supervised learning, namely category hierarchies, label inconsistency, and open-world recognition. The contributions of this paper are: (1) conceptualizing a category with a theoretically optimal solution; (2) proposing a practical GCD method based on the theory; (3) achieving the state-of-the-art GCD performance on both generic and fine-grained scenarios.", "questions": "Please see the weaknesses above.\n\nIn addition, should the “Z^i” in line 215 be “z^i”? Because “Z^i” is a number according to line 150?", "limitations": "yes", "rating": 5, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "(1) The inspiration for modeling category hierarchies by encoding a category with a binary tree is reasonable.\n\n(2) The theoretical derivation of the optimization loss is adequate and helps readers understand the subsequent model design.", "weaknesses": "(1) The experimental demonstration of how binary code works is missing. For example, the authors can simply compare the codes of “dog”, “cat”, and “car” to see how the number of digits differs in the codes. It is crucial to verify the category hierarchies and label consistency, which are the core problems to solve claimed in the paper.\n\n(2) The performance improvement on generic datasets is limited. CIFAR10 performance lags behind ORCA and CIFAR100 performance gains only 0.2.\n\n(3) The paper's ablation study in Table 2 raises concern. In the first row, the model solely uses the visual features to compute the loss, i.e., the original GCD [1] approach. In Table 3 CIFAR10 section, the results provided from the original GCD paper are used. If we compare the results from both Table 2 and Table 3 by evaluating them using Semi-supervised K-means (SS-KMeans [1]), both InfoSieve and GCD approaches gain an increase in accuracy for the known class, while for the novel class, only InfoSieve gains an increase, while GCD gets the worst accuracy results. This paper shows that the GCD + generic K-Means is better than GCD + SS-KMeans, which is inconsistent with what the GCD paper claimed. An investigation should be conducted to address this inconsistency.\n\nMinor: Missing notation definitions such as \"M\" and \"K\" in the main paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "***We thank the reviewer for finding our inspiration and theoretical derivation reasonable and adequate. We use the points raised by the reviewer for better clarification of our theory and implementation details. The binary tree visualization and discussing the fine-grained vs. generic dataset performance will be a valuable addition to our paper.*** \n\n**Demonstration of binary codes.** The attached pdf shows how the binary codes work for the CUB dataset. We see that our method can extract some hierarchical structure in the data. In the leaves of this tree, we have “yellow sparrows,” which are the descendants of a more general “sparrow” node. Or, for instance, in the path ‘00...1’, we have “black birds” node, which can encompass multiple black bird species.\n\n **Limited improvement on CIFAR 10.** This is due to the limited number of categories in CIFAR 10. Our method is well suited for datasets with more categories and fine distinctions.  \nBased on our theory, the improvement in CIFAR10/100 is predictable. For CIFAR 10, the depth of the implicit tree is 4; hence the number of implicit possible binary trees with this limited depth is smaller, meaning finding a good approximation for the implicit category tree can be achieved by other models. However, as the depth of this tree increases, our model can still find the aforementioned tree. This, in particular, is suitable for fine-grained data. For instance, the following table shows our results on fine-grained datasets:\n|**Dataset** |||CUB|||Aircraft|||Herb|||SCars|||Pet|| \n|----------------------|----------------------|----------|----------|----------|----------|----------|----------|----------|----------|----------|----------|----------|----------|----------|----------|----------| \n|**Method**|Venue|All|Known|Novel|All|Known|Novel|All |Known|Novel|All|Known|Novel|All|Known|Novel| \n|k-means|ACM'07|34.3|38.9|32.1|12.9|12.9|12.8|13.0|12.2|13.4 |12.8|10.6|13.8|77.1|70.1|80.7|\n|RankStats+|TPAMI'21|33.3|51.6|24.2|26.9| 36.4| 22.2|27.9|55.8|12.8 |28.3|61.8|12.1|-|-|-|\n|UNO+|ICCV'21|35.1|49.0|28.1|40.3|56.4| 32.2|28.3|53.7|14.7|35.5|70.5|18.6|-|-|-|\n|ORCA|ICLR'22|36.3|43.8|32.6|31.6|32.0|31.4|24.6|26.5|23.7|31.9|42.2|26.9|-|-|-|\n|GCD|CVPR'22|51.3|56.6|48.7|45.0|41.1|46.9|35.4|51.0|27.0|39.0|57.6|29.9|80.2|85.1|77.6|\n|XCon [a]|BMVC'22|52.1|54.3|51.0|47.7|44.4|49.4|-|-|-|40.5|58.8|31.7|86.7 |91.5|84.1\n|PromptCAL[b]|CVPR'23|62.9|64.4|62.1|52.2|52.2|52.3|-|-|-|50.2|70.1|40.6|-|-|-|\nDCCL [c]|CVPR'23|63.5|60.8|**64.9**|-|-|-|-|-|-|43.1|55.7|36.2|88.1|88.2|88.0|\n|SimGCD [d]|ICCV'23|60.3|65.6|57.7|54.2|59.1|51.8|**44.0**|58.0|**36.4**|53.8|**71.9**|45.0|-|-|-|\n|GPC [e]|ICCV'23|52.0|55.5|47.5| 43.3|40.7|44.8|-|-|-|38.2|58.9|27.4|-|-|-|\n|InfoSieve||**70.9**|**83.5**|64.3|**60.6**|**69.1**|**56.4**|40.3|**59.0**|30.2|**63.6**|61.0|**64.9**|**90.7**|**95.2**|**88.4**|      \n\nNevertheless, we made a few minor changes to the implementation of our method and reported the new results on CIFAR10 and CIFAR100 (also ImageNet for 50 epochs due to the time limit). Namely, we use tanh instead of the sigmoid activation functions for a more symmetric 0 and 1 code distribution, start with a bias of 1 for the masker to make the masker network start from considering all code bits at the beginning of training, and use a label smoothing hyperparameter for preventing the network from being too strict in its code predictions. Based on these changes, our results are as follows and will be added to the main paper.\n|**Dataset**|||CIFAR|10||CIFAR|100||Imagenet|100|\n|----------------------|----------------------|----------|----------|----------|----------|----------|----------|----------|----------|----------|\n|**Method**|Venue|All|Known|Novel|All|Known|Novel|All|Known|Novel|\n|k-means|ACM'07|83.6|85.7|82.5|52.0|52.2|50.8|72.7|75.5|71.3|\n|RankStats+|TPAMI'21|46.8|19.2|60.5|58.2|77.6|19.3|37.1|61.6|24.8|\n|UNO+|ICCV'21|68.6|**98.3**| 53.8|69.5|80.6|47.2|70.3|**95.0**|57.9|\n|ORCA|ICLR'22|96.9|95.1|97.8|74.2|82.1|67.2|79.2|93.2|72.1|\n|GCD|CVPR'22|91.5|97.9|88.2|73.0|76.2|66.5|74.1|89.8|66.3|\n|XCon [a]|BMVC'22|96.0|97.3|95.4|74.2|81.2|60.3|77.6|93.5|69.7|\n|PromptCAL [b]|CVPR'23|**97.9**|96.6|**98.5**|**81.2**|**84.2**|75.3|**83.1**|92.7|**78.3**|\n|DCCL [c]|CVPR'23|96.3|96.5|96.9|75.3|76.8|70.2|80.5|90.5|76.2|\n|SimGCD [d] |ICCV'23|97.1|95.1|98.1|80.1|81.2|**77.8**|83.0|93.1|77.9|\n|GPC [e] |ICCV'23|90.6|97.6|87.0|75.4|84.6|60.1|75.3|93.4|66.7|\n|InfoSieve||96.8|96.4|96.9|77.8|80.5|72.4|78.8|90.3|73.1|\n\n**GCD results.** The difference between the first row of Table 2 and the GCD results reported is the number of blocks finetuned in the ViT, GCD freezes the weights of ViT-B-16 for 11 blocks and finetunes only the final block. Like DCCL, we freeze the weights of 10 blocks and finetune the final two blocks, because our model requires more tunable parameters to optimize our objective function. When freezing 11 and finetuning the last block of ViT (similar to GCD) for our method, we obtain 95.4% for known categories and 91.0% for novel categories on CIFAR10 dataset. This is still an improvement over the 88.2% obtained by GCD for novel categories. In the paper, we will add the number of blocks fine-tuned to our implementation details.  \n\n**Missing notation definitions.** $M$ is the length of the binary code assigned to a sample $X^i$. $K$ is the length of the path to a category code $c$. We will update lemma $1$ to explain these symbols explicitly.  \n\n**$Z^i$ clarification.** We can consider $Z^i$, as the mapping of sequence $z^i$ with length $d$, so the $Z^i$ is a number in this line. We will make it explicit in the text. "}, {"review_id": "Qw8nQsDRNf", "reviewer": "Reviewer_ApGA", "summary": "This paper questions a foundation problem that underpins the generalized class discovery (GCD): what defines a category. To this end, the authors proposed a self-learning-based method that solves GCD by modeling the implicit category hierarchy in the data. The proposed method allows control over category granularity and is thus good at fine-grained recognition datasets. The extensive experiments and theoretical analysis have demonstrated the effectiveness of the proposed method.", "questions": "No questions.\n\n--- Post rebuttal ---\n\nThank the authors for the detailed rebuttal response, which addressed my main concerns, and thus I keep my positive rating unchanged.", "limitations": "The limitations are carefully discussed in the paper.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The writing is satisfying. The paper is easy-to-follow.\n- The motivation is decent.\n- The proposed method is novel and proved effective.\n- Also the related works are adequately discussed.", "weaknesses": "- The compared methods are no longer state-of-the-art. Also, due to the explicit assumption of a hierarchical structure, the proposed method is not always the best on all datasets, especially the generic ones.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "***We thank the reviewer for finding our proposed method novel and effective and our motivation decent. We also agree that a strong theoretical approach will be more applicable if it is accompanied by strong empirical results. Hence here, we provide the empirical results that the reviewer has mentioned.***\n\n**Recent state-of-the-art methods.** Here, we add a comparison to several recent works, Xcon [a], PromptCAL [b], DCCL[c], SimGCD [d], and GPC [e], over fine-grained data. By making a few minor changes to the implementation of our method, we outperform all of these works on CUB-200, FGCV-Aircraft, Herbarium-19, Stanford-Cars, and Oxford-IIIT Pet. Namely, we use tanh instead of the sigmoid activation functions for a more symmetric 0 and 1 code distribution, use a bias of 1 for the masker to make the masker network start from considering all code bits at the beginning of training, alternate the training of coder and masker to separate their effect as suggested by reviewer Sjrc and use a label smoothing hyperparameter for preventing the network from being too strict in its code predictions. Based on these changes, our results are as follows and will be added to the main paper.\n|**Dataset** |||CUB|||Aircraft|||Herb|||SCars|||Pet|| \n|----------------------|----------------------|----------|----------|----------|----------|----------|----------|----------|----------|----------|----------|----------|----------|----------|----------|----------| \n|**Method** |Venue|All | Known  | Novel |  All | Known  | Novel|All | Known  | Novel|All | Known  | Novel|All | Known  | Novel|\n|k-means|ACM'07|34.3|38.9|32.1|12.9|12.9|12.8|13.0|12.2|13.4 |12.8|10.6|13.8|77.1|70.1|80.7|\n|RankStats+|TPAMI'21|33.3|51.6|24.2|26.9| 36.4| 22.2|27.9|55.8|12.8 |28.3|61.8|12.1|-|-|-|\n|UNO+|ICCV'21|35.1|49.0|28.1|40.3| 56.4| 32.2|28.3|53.7|14.7|35.5|70.5|18.6|-|-|\t-|\n|ORCA|ICLR'22|36.3|43.8|32.6|31.6|32.0|31.4|24.6|26.5|23.7|31.9|42.2|26.9|\t-|-|- |\n|GCD|CVPR'22|51.3|56.6|48.7|45.0\t|41.1|46.9|35.4|51.0|27.0|39.0|57.6|29.9|\t80.2\t|85.1|77.6|\n|XCon [a]|BMVC'22|52.1|54.3|51.0|47.7|44.4|49.4|-|-|-|40.5|58.8|31.7|86.7 |91.5|84.1\n|PromptCAL[b]|CVPR'23|62.9|64.4|62.1|52.2|52.2|52.3|-|-|-|50.2|70.1|40.6|-|-|-|\nDCCL [c] |CVPR'23|63.5|60.8|**64.9**|-|-|-|-|-|-|43.1|55.7|36.2|88.1|88.2|88.0|\n|SimGCD [d]|ICCV'23|60.3|65.6|57.7|54.2|59.1|51.8|**44.0**| 58.0|**36.4**|53.8|**71.9**|45.0|-|-|-|\n|GPC [e] |ICCV'23|52.0|55.5|47.5| 43.3|40.7|44.8|-|-|-| 38.2| 58.9|27.4|-|-|-|\n|InfoSieve |  | **70.9** | **83.5** |64.3|**60.6**| **69.1**| **56.4**| 40.3 |**59.0**| 30.2|**63.6**| 61.0 |**64.9**|**90.7**|**95.2**|**88.4**|     \n\nBased on our theory, the improvement in CIFAR10/100 and ImageNet-100 is predictable. For CIFAR 10, the depth of the implicit tree is 4, and for CIFAR 100, it will be 7; hence the number of implicit possible binary trees with this limited depth is smaller, meaning finding a good approximation for the implicit category tree can be achieved by other models. However, as the depth of this tree increases, our model can still find the aforementioned tree. This, in particular, is suitable for real-world scenarios where the number of categories can be huge, or categories are long-tailed like Herbarium_19, fine-grained like CUB, Aircraft, and Stanford Cars, partially labeled or have noisy labels. Nevertheless, we repeated experiments with the aforementioned changes and reported the new results on CIFAR10 and CIFAR100 (also ImageNet for 50 out 200 epochs due to the time limit). Based on these changes, our results are as follows and will be added to the main paper. \n|**Dataset**|||CIFAR|10||CIFAR|100||Imagenet|100|\n|----------------------|----------------------|----------|----------|----------|----------|----------|----------|----------|----------|----------|\n|**Method**|Venue  | All | Known  | Novel |  All | Known  | Novel|All | Known  | Novel|\n|k-means |ACM'07| 83.6 | 85.7 | 82.5 | 52.0 | 52.2  | 50.8|72.7|75.5|71.3|\n|RankStats+|TPAMI'21| 46.8 | 19.2 | 60.5| 58.2|77.6 | 19.3|37.1|61.6|24.8|\n|UNO+ |ICCV'21| 68.6 | **98.3** | 53.8 | 69.5 | 80.6  | 47.2|70.3|**95.0**\t|57.9 |\n|ORCA |ICLR'22| 96.9 | 95.1| 97.8 |74.2 |82.1| 67.2|79.2\t|93.2|72.1|\n|GCD|CVPR'22| 91.5 | 97.9 | 88.2 |73.0 |76.2| 66.5|74.1 | 89.8|66.3|\n|XCon [a]|BMVC'22 |96.0|97.3|95.4|74.2|81.2|60.3|77.6| 93.5 |69.7|\n|PromptCAL [b] |CVPR'23| **97.9** | 96.6 | **98.5**|**81.2**|**84.2**| 75.3|**83.1**|92.7|**78.3** |\n|DCCL [c]|CVPR'23| 96.3 | 96.5 | 96.9 | 75.3 | 76.8  | 70.2|80.5|90.5|76.2|\n|SimGCD [d] |ICCV'23 |97.1 | 95.1 | 98.1 | 80.1 | 81.2 | **77.8**|83.0|93.1|77.9|\n|GPC [e] |ICCV'23|90.6| 97.6| 87.0| 75.4 |84.6| 60.1|75.3| 93.4 | 66.7|\n|InfoSieve| | 96.8 |96.4 |96.9| 77.8 | 80.5 | 72.4|78.8 | 90.3 |73.1|\n\nAlthough our method is not always the best, it performs consistently well. While our model on fine-grained datasets outperforms most recent SoTAs, our model's performance on the generic datasets has not been compromised. "}, {"review_id": "4MXwtGNaX2", "reviewer": "Reviewer_Sjrc", "summary": "The paper conceptualize a category through the lens of optimization, viewing it as an optimal solution to a well-defined problem. The author propose a novel, efficient and self-supervised method capable of discovering previously unknown categories at test time.", "questions": "1、In the Table. 3 and Table. 4, the performance gap between the method and sota methods to be quite significant. Can you analyze the possible reasons for this?\n2、I am very interested in your implict binary tree and category encoding. Could you show it using a visualization?\n", "limitations": " Authors adequately addressed the limitations .", "rating": 7, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1、The paper aims to tackle an important problem of how to better represent categories in deep learning models. The mathematical solution and novel framework proposed by the authors offer intriguing insights into addressing this issue;\n2、The paper is well-structured, with a reasonable experimental design and demonstrates the effectiveness of the proposed method on multiple datasets.\n", "weaknesses": "1、It is worth noting that the proposed method might require more empirical studies to validate its generalizability across different scenarios and tasks. How does this model perform on the common ImageNet-100 dataset?\n2、I agree that there are quite a few loss functions presented in this paper. Although the authors provide detailed explanations for each loss, it might be somewhat challenging to unify so many losses within a single system. So adapting this model for multi-stage training could be a viable approach to address the complexity if handling multiple losses.\n3、The improvement on the commonly used CIFAR dataset is relative weak.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "***We thank the reviewer for finding the category definition an important problem, our framework novel, and our experimental design effective. We also agree that a theoretical foundation requires adequate empirical studies. Hence here we address the points raised by the reviewer to enrich our paper with more in-depth analysis and better visualizations.***\n\n**Limited improvement on CIFAR 10 and experiments on ImageNet100.** This is due to the limited number of categories in CIFAR 10. Our method is well suited for datasets with more categories and fine distinctions.  \nBased on our theory, the improvement in CIFAR10/100 is predictable. For CIFAR 10, the depth of the implicit tree is 4, and for CIFAR 100, it will be 7; hence the number of implicit possible binary trees with this limited depth is smaller, meaning finding a good approximation for the implicit category tree can be achieved by other models. However, as the depth of this tree increases, our model can still find the aforementioned tree. This, in particular, is suitable for real-world scenarios where the number of categories can be huge, or categories are long-tailed like Herbarium_19, fine-grained like CUB, Aircraft, and Stanford Cars, partially labeled or have noisy labels. Nevertheless, we made a few minor changes to the implementation of our method and reported the new results on both generic and fine-grained datasets. Namely, we use tanh instead of the sigmoid activation functions for a more symmetric 0 and 1 code distribution, start with a bias of 1 for the masker to make the masker network start from considering all code bits at the beginning of training, and use a label smoothing hyperparameter for preventing the network from being too strict in its code predictions. Based on these changes, we see in the following table that our method is well-suited to fine-grained datasets. \n|**Dataset** |||CUB|||Aircraft|||Herb|||SCars|||Pet|| \n|----------------------|----------------------|----------|----------|----------|----------|----------|----------|----------|----------|----------|----------|----------|----------|----------|----------|----------| \n|**Method** |Venue|All | Known  | Novel |  All | Known  | Novel|All | Known  | Novel|All | Known  | Novel|All | Known  | Novel|\n|k-means|ACM'07|34.3|38.9|32.1|12.9|12.9|12.8|13.0|12.2|13.4 |12.8|10.6|13.8|77.1|70.1|80.7|\n|RankStats+|TPAMI'21|33.3|51.6|24.2|26.9| 36.4| 22.2|27.9|55.8|12.8 |28.3|61.8|12.1|-|-|-|\n|UNO+|ICCV'21|35.1|49.0|28.1|40.3| 56.4| 32.2|28.3|53.7|14.7|35.5|70.5|18.6|-|-|\t-|\n|ORCA|ICLR'22|36.3|43.8|32.6|31.6|32.0|31.4|24.6|26.5|23.7|31.9|42.2|26.9|\t-|-|- |\n|GCD|CVPR'22|51.3|56.6|48.7|45.0\t|41.1|46.9|35.4|51.0|27.0|39.0|57.6|29.9|\t80.2\t|85.1|77.6|\n|XCon [a]|BMVC'22|52.1|54.3|51.0|47.7|44.4|49.4|-|-|-|40.5|58.8|31.7|86.7 |91.5|84.1\n|PromptCAL[b]|CVPR'23|62.9|64.4|62.1|52.2|52.2|52.3|-|-|-|50.2|70.1|40.6|-|-|-|\nDCCL [c] |CVPR'23|63.5|60.8|**64.9**|-|-|-|-|-|-|43.1|55.7|36.2|88.1|88.2|88.0|\n|SimGCD [d]|ICCV'23|60.3|65.6|57.7|54.2|59.1|51.8|**44.0**| 58.0|**36.4**|53.8|**71.9**|45.0|-|-|-|\n|GPC [e] |ICCV'23|52.0|55.5|47.5| 43.3|40.7|44.8|-|-|-| 38.2| 58.9|27.4|-|-|-|\n|InfoSieve |  | **70.9** | **83.5** |64.3|**60.6**| **69.1**| **56.4**| 40.3 |**59.0**| 30.2|**63.6**| 61.0 |**64.9**|**90.7**|**95.2**|**88.4**|      \n\nThe new results on CIFAR10 and CIFAR100 (also ImageNet for 50 instead of 200 epochs due to the time limit) are as follows and will be added to the main paper. \n|**Dataset**|||CIFAR|10||CIFAR|100||Imagenet|100|\n|----------------------|----------------------|----------|----------|----------|----------|----------|----------|----------|----------|----------|\n|**Method**|Venue  | All | Known  | Novel |  All | Known  | Novel|All | Known  | Novel|\n|k-means |ACM'07| 83.6 | 85.7 | 82.5 | 52.0 | 52.2  | 50.8|72.7|75.5|71.3|\n|RankStats+|TPAMI'21 | 46.8 | 19.2 | 60.5| 58.2 | 77.6 | 19.3|37.1|61.6|24.8|\n|UNO+ |ICCV'21| 68.6 | **98.3** | 53.8 | 69.5 | 80.6  | 47.2|70.3|**95.0**\t|57.9 |\n|ORCA |ICLR'22| 96.9 | 95.1 | 97.8 | 74.2 | 82.1  | 67.2|79.2\t|93.2|72.1|\n|GCD|CVPR'22   | 91.5 | 97.9 | 88.2 | 73.0 | 76.2  | 66.5|74.1 | 89.8|66.3|\n|XCon [a]|BMVC'22 |96.0|97.3|95.4|74.2|81.2|60.3|77.6| 93.5 |69.7|\n|PromptCAL [b] |CVPR'23| **97.9** | 96.6 | **98.5**|**81.2**| **84.2**| 75.3|**83.1**|92.7|**78.3** |\n|DCCL [c]|CVPR'23| 96.3 | 96.5 | 96.9 | 75.3 | 76.8  | 70.2|80.5|90.5|76.2|\n|SimGCD [d] |ICCV'23 |97.1 | 95.1 | 98.1 | 80.1 | 81.2 | **77.8**|83.0|93.1|\t77.9|\n|GPC [e] |ICCV'23|90.6| 97.6| 87.0| 75.4 |84.6| 60.1|75.3| 93.4 | 66.7|\n|InfoSieve| | 96.8 |96.4 |96.9| 77.8 | 80.5 | 72.4|78.8 | 90.3 |73.1|\n\n**Large performance gap for fine-grained datasets** We acknowledge the gap with the GCD paper. However, we'd like to emphasize that this gap has been closed by recent advances in state-of-the-art (SotA) methods, which we demonstrate in the table below. Like these new SotA methods, our method uses a richer set of supervision signals and tunable parameters. This approach accelerates the formation of supervised clusters and significantly increases the gap between the GCD paper over known categories.\n\n**Demonstration of binary codes** To demonstrate how the binary codes work, we provide a visualization in the attached pdf. Specifically, we include several sections of the binary tree our method obtains for the CUB dataset. We see that our method is able to extract some hierarchical structure in the data. As we can see in the leaves of this tree, we have “yellow sparrows” while they are the descendants of a more general “sparrow” node. Or for instance the path ‘00...1’ we have “black birds” node which can encompass multiple species of birds that are black. "}, {"review_id": "abWfG1J7Gb", "reviewer": "Reviewer_GHXK", "summary": "This paper introduces a novel perspective on categorization, framing it as an optimization problem with the goal of finding optimal solutions. The authors propose a self-supervised approach that can identify new categories during testing. They achieve this by assigning concise category codes to individual data instances, which effectively captures the inherent hierarchical structure found in real-world datasets.", "questions": "1. About the experiment setting, transductive or instructive?  the test set is included or excluded in the training process?\n2. How to compute mutual information, MINE[1]?\n\n\n[1]MINE: Mutual Information Neural Estimation\n", "limitations": "1. Complex Hyperparameter Tuning: The model's complexity with five hyperparameters in the loss functions makes tuning challenging. An automated tuning method might streamline this process.\n2. Missing Ablation Studies: The absence of ablation studies limits understanding of individual hyperparameters' impact on performance. This analysis would contribute to model optimization.\n3. Incomplete Comparison: The paper lacks comparison with some recent methods. Incorporating them can provide a more comprehensive evaluation.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The paper conceptualizes a category as a solution to an optimization problem, which is novel.\n2. The paper is well-written, easy to follow\n3. The proposed method is novel\n\n", "weaknesses": "1. The method is too complicated, with 5 hyperparameters in the overall loss functions, which is hard to tune, is it possible to make it automatically?\n2. Some ablation studies are missing, I am curious about the effect on every hyperparameter in the loss function, how sensitive are they to the performance?\n3. Some recent methods of comparison are missing.\n* [1] PromptCAL: Contrastive Affinity Learning via Auxiliary Prompts for Generalized Novel Category Discovery (CVPR 2023)\n* [2] Modeling Inter-Class and Intra-Class Constraints in Novel Class Discovery (CVPR 2023)\n* [3] Generalized Category Discovery with Decoupled Prototypical Network (AAAI 2023)\n* [4] Supervised Knowledge May Hurt Novel Class Discovery Performance (TMLR 2023)\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "***We thank the reviewer for finding our method and theory novel. We will use the provided references to enrich our paper both in related works and experimental analysis. Automatic hyperparameter tuning is an intriguing future work, we also provided the updated results vs. SoTA methods for stronger empirical proof.***\n\n**Complex Hyperparameter Tuning.** Since this paper tries to show that concept of learning categories as an arbitrary number can be detrimental to supervision, we suggested defining an optimization for extracting this inherent information from the data itself. The method proposed in the paper is one approach to this optimization. For instance, two condition losses can be replaced by using binary vectors from scratch. The main losses for the paper are length minimization and information maximization losses. Thus, only these hyperparameters are specific to our theory; other hyperparameters can differ based on how this optimization problem is approximated. Adopting an automatic hyperparameter tuning method can help make models more autonomous and interesting in future work.  \n\n**Additional Ablation Studies** We investigate the effect of $\\lambda_{code}$ in Table 2 of the supplementary. The attached pdf also depicts the t-SNE visualization of CIFAR10 instances for different features generated by our model. As can be seen in the figures, while our model’s features form separate clusters, our label embedding makes these clusters distinctive from each other.  Binary embedding enhances this separation while condensing the cluster by making samples of clusters closer to each other, which is evident for the yellow or bird cluster.  This is due to the fact that binary embedding, because of its 0 or 1 nature, will be affected by semantic similarity more than visual similarity. Finally, our code embedding shows indirectly that to have the most efficient code, our model should span the code space as much as possible, which explains the porous nature of these clusters. We will add the effects of different hyperparameters on these clusters to our paper. \n\n**Comparison with Sota** We made a few minor changes to the implementation, including using tanh instead of sigmoid activation functions for a more symmetric 0 and 1 code distribution, using a bias of 1 for masker to make the masker network start from considering all code bits at the beginning of training and finally using a label smoothing hyperparameter for preventing the network from being too strict in its code predictions. Our results based on these changes are in the table below with a comparison to recent Sota methods. We compare against recent GCD methods in the following table; we leave comparisons with methods with a different problem as NCD like [2,4] or different data like intent classification in [3] for future work. \n|**Dataset** |||CUB|||Aircraft|||Herb|||SCars|||Pet|| \n|----------------------|----------------------|----------|----------|----------|----------|----------|----------|----------|----------|----------|----------|----------|----------|----------|----------|----------| \n|**Method** |Venue|All | Known  | Novel |  All | Known  | Novel|All | Known  | Novel|All | Known  | Novel|All | Known  | Novel| \n|k-means|ACM'07|34.3|38.9|32.1|12.9|12.9|12.8|13.0|12.2|13.4 |12.8|10.6|13.8|77.1|70.1|80.7| \n|RankStats+|TPAMI'21|33.3|51.6|24.2|26.9| 36.4| 22.2|27.9|55.8|12.8 |28.3|61.8|12.1|-|-|-| \n|UNO+|ICCV'21|35.1|49.0|28.1|40.3| 56.4| 32.2|28.3|53.7|14.7|35.5|70.5|18.6|-|-|\t-| \n|ORCA|ICLR'22|36.3|43.8|32.6|31.6|32.0|31.4|24.6|26.5|23.7|31.9|42.2|26.9|\t-|-|- | \n|GCD|CVPR'22|51.3|56.6|48.7|45.0\t|41.1|46.9|35.4|51.0|27.0|39.0|57.6|29.9|\t80.2\t|85.1|77.6| \n|XCon [a]|BMVC'22|52.1|54.3|51.0|47.7|44.4|49.4|-|-|-|40.5|58.8|31.7|86.7 |91.5|84.1 \n|PromptCAL[b]|CVPR'23|62.9|64.4|62.1|52.2|52.2|52.3|-|-|-|50.2|70.1|40.6|-|-|-| \n|DCCL [c] |CVPR'23|63.5|60.8|**64.9**|-|-|-|-|-|-|43.1|55.7|36.2|88.1|88.2|88.0| \n|SimGCD [d]|ICCV'23|60.3|65.6|57.7|54.2|59.1|51.8|**44.0**| 58.0|**36.4**|53.8|**71.9**|45.0|-|-|-| \n|GPC [e] |ICCV'23|52.0|55.5|47.5| 43.3|40.7|44.8|-|-|-| 38.2| 58.9|27.4|-|-|-| \n|InfoSieve |  | **70.9** | **83.5** |64.3|**60.6**| **69.1**| **56.4**| 40.3 |**59.0**| 30.2|**63.6**| 61.0 |**64.9**|**90.7**|**95.2**|**88.4**|\n\n[a] Fei, Yixin, et al. \"Xcon: Learning with experts for fine-grained category discovery.\" 33rd British Machine Vision Conference. BMVA Press 2022. \n\n[b] Zhang, Sheng, et al. \"Promptcal: Contrastive affinity learning via auxiliary prompts for generalized novel category discovery.\" Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. 2023. \n\n[c] Pu, Nan, Zhun Zhong, and Nicu Sebe. \"Dynamic Conceptional Contrastive Learning for Generalized Category Discovery.\" Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. 2023. \n\n[d] Wen, Xin, Bingchen Zhao, and Xiaojuan Qi. \"A Simple Parametric Classification Baseline for Generalized Category Discovery.\" Proceedings of the IEEE/CVF International Conference on Computer Vision. (2022). \n\n[e] Zhao, Bingchen, Xin Wen, and Kai Han. \"Learning Semi-supervised Gaussian Mixture Models for Generalized Category Discovery.\" Proceedings of the IEEE/CVF International Conference on Computer Vision. (2023). \n\n**Transductive or instructive.** We use the same experimental setup as GCD and DCCL, which is transductive. We have a disjoint validation set to determine the best hyperparameters and best model. \n\n**Mutual information computation.** As mentioned in the supplemental sections 1.2.2 and 1.2.3, we can consider the reconstruction loss or contrastive loss to approximately maximize mutual information. We use contrastive loss since we base our approach on the GCD framework. Using MINE to optimize this mutual information aligns well with our theory, but it is computationally expensive in practice. However, estimating mutual information of code and categories can be feasible."}]

Author rebuttal:
We thank all reviewers for their insightful feedback, and we appreciate that the reviewers found our paper theoretically and methodologically novel. There were a few shared questions about our paper, both in terms of comparing against the recently published state-of-the-art and visualizing our method of implicit tree extraction. To this end, we add a comparison to several recent works, Xcon [a], PromptCAL [b], DCCL [c], SimGCD [d], and GPC [e]. Furthermore, the attached PDF shows a demonstration of how our model extracts an implicit category tree for samples of the CUB-200 dataset.

[a] Fei, Yixin, et al. "Xcon: Learning with experts for fine-grained category discovery." 33rd British Machine Vision Conference. BMVA Press 2022.  

[b] Zhang, Sheng, et al. "Promptcal: Contrastive affinity learning via auxiliary prompts for generalized novel category discovery." Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. 2023.  

[c] Pu, Nan, Zhun Zhong, and Nicu Sebe. "Dynamic Conceptional Contrastive Learning for Generalized Category Discovery." Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. 2023.  

[d] Wen, Xin, Bingchen Zhao, and Xiaojuan Qi. "A Simple Parametric Classification Baseline for Generalized Category Discovery." Proceedings of the IEEE/CVF International Conference on Computer Vision. (2022).  

[e] Zhao, Bingchen, Xin Wen, and Kai Han. "Learning Semi-supervised Gaussian Mixture Models for Generalized Category Discovery." Proceedings of the IEEE/CVF International Conference on Computer Vision. (2023).  

Meta-review: This paper tackles the generalized category discovery (GCD) problem, proposing an interesting perspective of learning an implicit category code tree. A key advantages of this is supporting category hierarchies and label noise, hence moving more towards open-world situations. The paper formulates this as an optimization problem and shows theoretical motivation for the solution, resulting in a practical algorithm (InfoSieve). Results are shown across a range of datasets, with especially strong performance on more fine-grained datasets with category hierarchies. 

  The reviewers appreciated the interesting problem formulation, theoretical justification, and novelty of the method. They shared a number of concerns, however, including 1) an understanding of how binary codes actually show label consistency and hierarchies, 2) limited performance on smaller datasets with less rich categories (CIFAR-10), 3) more up-to-date comparison to state-of-art, and 4) the need for a large number of losses/hyper-parameters. The authors provided a strong rebuttal, including a number of different experiments on fine-grained datasets, improved results with a few slight modifications, and hyper-parameter sensitivity analysis. After the rebuttal, most of the reviewers were satisfied and kept or increased to positive scores. 

  After reviewing the paper, reviews, and rebuttal, I recommend acceptance. One of the interesting and unique aspects of this work is its focus on a more structured, hierarchical understanding of categories in the novel category discovery setting, which will hopefully foster additional methods with this perspective.
Decision: Accept (poster)