Learn to Categorize or Categorize to Learn? Self-Coding for Generalized Category Discovery

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.

Paper

Similar papers

Peer review

Reviewer GHXK5/10 · confidence 3/52023-07-03

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.

Strengths

1. The paper conceptualizes a category as a solution to an optimization problem, which is novel. 2. The paper is well-written, easy to follow 3. The proposed method is novel

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? 2. 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? 3. Some recent methods of comparison are missing. * [1] PromptCAL: Contrastive Affinity Learning via Auxiliary Prompts for Generalized Novel Category Discovery (CVPR 2023) * [2] Modeling Inter-Class and Intra-Class Constraints in Novel Class Discovery (CVPR 2023) * [3] Generalized Category Discovery with Decoupled Prototypical Network (AAAI 2023) * [4] Supervised Knowledge May Hurt Novel Class Discovery Performance (TMLR 2023)

Questions

1. About the experiment setting, transductive or instructive? the test set is included or excluded in the training process? 2. How to compute mutual information, MINE[1]? [1]MINE: Mutual Information Neural Estimation

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

2 fair

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. 2. Missing Ablation Studies: The absence of ablation studies limits understanding of individual hyperparameters' impact on performance. This analysis would contribute to model optimization. 3. Incomplete Comparison: The paper lacks comparison with some recent methods. Incorporating them can provide a more comprehensive evaluation.

Reviewer Sjrc7/10 · confidence 5/52023-07-06

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.

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; 2、The paper is well-structured, with a reasonable experimental design and demonstrates the effectiveness of the proposed method on multiple datasets.

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? 2、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. 3、The improvement on the commonly used CIFAR dataset is relative weak.

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? 2、I am very interested in your implict binary tree and category encoding. Could you show it using a visualization?

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

5: You are absolutely certain about your assessment. You are very familiar with the related work and checked the math/other details carefully.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

Authors adequately addressed the limitations .

Reviewer ApGA6/10 · confidence 3/52023-07-09

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.

Strengths

- The writing is satisfying. The paper is easy-to-follow. - The motivation is decent. - The proposed method is novel and proved effective. - 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.

Questions

No questions. --- Post rebuttal --- Thank the authors for the detailed rebuttal response, which addressed my main concerns, and thus I keep my positive rating unchanged.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

The limitations are carefully discussed in the paper.

Reviewer xjo15/10 · confidence 5/52023-07-11

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.

Strengths

(1) The inspiration for modeling category hierarchies by encoding a category with a binary tree is reasonable. (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. (2) The performance improvement on generic datasets is limited. CIFAR10 performance lags behind ORCA and CIFAR100 performance gains only 0.2. (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. Minor: Missing notation definitions such as "M" and "K" in the main paper.

Questions

Please see the weaknesses above. In addition, should the “Z^i” in line 215 be “z^i”? Because “Z^i” is a number according to line 150?

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

5: You are absolutely certain about your assessment. You are very familiar with the related work and checked the math/other details carefully.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

yes

Reviewer Sjrc2023-08-15

Response

Thank you for providing a rebuttal response, it has majorly addressed my concerns. The demonstration is excellent and I will keep my current score.

Authorsrebuttal2023-08-16

We are pleased to hear that our responses have addressed your concerns. We sincerely thank the reviewer for the thorough examination and invaluable suggestions that have contributed to the enhancement of our paper. We are committed to revising the paper to incorporate the new experimental results. We would greatly appreciate any additional feedback to further refine and enrich our paper. Thank you once again for your insightful comments.

Reviewer GHXK2023-08-16

Reply to rebuttal

I read the paper again and checked all reviewers' comments and the author's reply. And I keep my score.

Authorsrebuttal2023-08-16

We sincerely appreciate the time and effort you invested in your comprehensive review and your valuable suggestions, especially regarding the additional ablation studies and comparisons with recent state-of-the-art works. We have diligently revised our paper to incorporate these new experimental results. Should there be any further points of enhancement that could potentially lead to a positive reevaluation of our paper, we would greatly appreciate your guidance. Your constructive feedback is instrumental in elevating the quality of our work, and we are truly thankful for it.

Reviewer GHXK2023-08-18

Reply to author

Thank you for your response. However, the issues of over-parameterization and incomplete ablation studies still leave me unconvinced. And I'm still not clear enough on how you perform binary classification. I also may have misunderstood on Theorem 1. Could you provide me with a more detailed explanation? I am happy to discuss with you.

Authorsrebuttal2023-08-21

***We thank the reviewer for engagement and offering us the opportunity for further clarification.*** **Parameter ablation:** We agree that our model has a few hyperparameters, but let’s expand on these parameters: code binary constraint, mask binary constraint, code contrastive, code length, code mapping. We examine the effect of each hyperparameter on overall performance of the model on CIFAR10 and CUB datasets. Due to time constraints, we report the results for 20 epochs on CUB and 100 epochs on CIFAR10. Our default values for the hyperparameters are: code constraint coeff$=10$, mask constraint coeff$=10$, code contrastive coeff $\beta=1$, code mapping coeff $\gamma=1$ and code length coeff $\delta=0.1$. **Code binary constraint:** This hyperparameter is introduced to satisfy the binary requirement of the code. By using binary neural networks and an STE (straight-through estimator) [i], we can simply omit the requirement for this hyperparameter. Another approach would be to benefit from Boltzmann machines [ii] to have a binary code. The following table reports the results for different hyperparameters for this binary code condition. Note that since we use tanh to create the binary vector, the coefficient only determines how fast the method makes the conditions met, and when 0 and 1 are stabilized, the hyperparameter effect will be diminished. However, we noticed that bigger coefficients affect the known accuracy to some degree. |**Dataset**||CUB|| |----------------------|----------|----------|----------| |Code constraint coeff|All |Known|Novel| |1|67.9|82.4|60.7| |10|68.0|82.3|60.9| |100|68.3|81.4|61.8| |1000|67.3|80.2|60.9| **Mask binary constraint:** For the mask constraint hyperparameter, again we can use a binary equivalent like binary neural network or Boltzmann machine. In our Lagrange multiplier approach, we start from an all-one mask, hence a bigger constraint translates to a bigger code length for categories. Since smaller or longer than required category lengths are both detrimental to the performance, a middle coefficient is more useful. |**Dataset**||CUB|| |----------------------|----------|----------|----------| |Mask constraint coeff|All|Known|Novel| |1|69.9|81.9|63.9| |10|68.0|82.3|60.9| |100|71.3|80.3|66.8| |1000|68.6|81.6|62.1| **Code contrastive:** This loss is the loss that maintains information about the input. From the following table we observe that for a fine-grained dataset like CUB, minimizing the information will lead to a better performance, however for a generic dataset like CIFAR10, maintaining some information about the input itself can be beneficial especially for novel categories. |**Dataset**||CUB|||CIFAR|10| |----------------------|----------|----------|----------|----------|----------|----------| |$\beta$|All|Known|Novel|All |Known |Novel| |0.01|70.2|83.6|63.5|94.1|96.8|92.7| |0.1|66.4|79.8|59.7|94.7|96.8|93.6| |1|68.0|82.3|60.9|95.8|96.8|95.2| |2|67.7|80.5|61.3|95.4|96.8|94.8| **Code length:** Here we report our results for different code length hyperparameters, note that since the code length is penalized exponentially, the code length effect is not comparable to the exponential growth. However from this table it can be seen that the shorter code lengths (higher code length penalty), translates to a better novel category identification. Also note that since CIFAR 10 is a generic dataset, some extra information can actually help the model to distinguish categories from each other, while for the CUB dataset, it is better to omit the extra information. |**Dataset**||CUB|||CIFAR|10| |----------------------|----------|----------|----------|----------|----------|----------| |$\delta$|All| Known|Novel|All|Known|Novel| |0.01|66.5|79.2|60.2|94.8|96.7|93.8| |0.1|68.0|82.3|60.9|95.8|96.8|95.2| |1|70.1|82.1|64.1|94.8|96.8|93.9| |2|69.1|80.6|63.4|95.3|96.8|94.6| **Code mapping:** Since current evaluation metrics rely on hit-and-miss accuracy, our category codes must be mapped to this scenario. This loss is not an essential part of the self-coding that our model learns, but it accelerates the model’s training. |**Dataset**||CUB|||CIFAR|10| |----------------------|----------|----------|----------|----------|----------|----------| |$\gamma$|All|Known|Novel|All|Known| Novel| |0.01|69.3|82.1|62.9|95.0|96.8|94.1| |0.1|68.3|80.2 |62.4|94.9|96.6 |94.0| |1|68.0| 82.3|60.9|95.8|96.8|95.2| |2|68.6| 80.3 |62.7|95.4|96.8|94.6| One reason the model is not very sensitive to different hyperparameters is that our model consists of three separate parts: Code masker, Code Generator and Categorizer. The only hyperparameters that affect all of these three parts directly are $\beta$, the code contrastive coefficient, and $\delta$, the code length coefficient. This is why these hyperparameters have a much more pronounced effect on our model’s performance. We will include the ablation and discussion on the effect of the hyperparameters on our model in the updated manuscript.

Authorsrebuttal2023-08-21

[i] Bengio, Yoshua, Nicholas Léonard, and Aaron Courville. "Estimating or propagating gradients through stochastic neurons for conditional computation." arXiv preprint arXiv:1308.3432 (2013). [ii] Hinton, Geoffrey E. "A practical guide to training restricted Boltzmann machines." Neural Networks: Tricks of the Trade: Second Edition. Berlin, Heidelberg: Springer Berlin Heidelberg, 2012. 599-619.

Authorsrebuttal2023-08-21

**Theorem 1 clarification:** The first part of theorem 1 states that if there is an implicit hierarchy tree, then for any category tree which is isomorph to this implicit tree, the algorithmic mutual information between each sample and its binary code generated by the tree will be maximum for the optimal tree. Hence maximizing this mutual information is a 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 1 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 a necessary condition for finding the optimal tree. This is equivalent to finding a 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 sample of category $c$ should be the shortest-length binary code, while this shared prefix is not the prefix of any sample from other categories. We will update the manuscript to make this clearer. **Binary classification:** Suppose that the generated feature vector by the network for sample $X$ is $x_0x_1\cdots x_k$, where $k$ is the dimension of the network or equivalently the depth of our implicit hierarchy tree. Using appropriate activation functions, we can assume that $x_i$s are 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$ or one of its augmentations, its code $x'_0x'_1\cdots x'_k$ will differ from the code assigned to $X$. For the supervised contrastive loss, instead of considering the code, we consider a sequence by assigning different positional values to each bit so the code $x_0x_1\cdots x_k$ can be considered as binary number $(0.x_0x_1\cdots x_k)_2$. 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. In the end, 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 happens at each node. The effectivity of this tree structure extraction is evident on a dataset like CUB, where the discriminative aspects of images can be more nuanced than the augmentation of the images. 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. We will further clarify the binary classification in the updated manuscript.

Reviewer GHXK2023-08-22

Reply to author

Thank you for your response. I'm pleased to see that you have addressed my concerns, and I'm inclined to vote for the acceptance of your manuscript.

Authorsrebuttal2023-08-22

We are grateful for your insightful feedback. We believe that the added ablation studies and hyperparameter analyses have indeed enhanced our work, and we owe this improvement to your thorough and constructive suggestions. Thank you.

Reviewer ApGA2023-08-16

Thanks the authors for the detailed experiemental results and analysis. My main concerns are mostly addressed. I keep my rating for now before discussion with other reviewers.

Authorsrebuttal2023-08-16

We are pleased to learn that we have successfully addressed your concerns. We extend our gratitude for your insightful suggestions, particularly regarding comparisons with the recent state of the art. In our endeavor to continually elevate the quality of our research, we have revised the paper, incorporating new experimental results spanning 5 fine-grained datasets and 3 generic datasets. Should you identify any additional areas for refinement or have insights that could further enhance the quality of our work, your guidance would be immensely valuable. We are thankful for your positive assessment and we remain committed to benefiting from your constructive feedback to continue elevating our paper.

Program Chairsdecision2023-09-21

Decision

Accept (poster)

© 2026 NYSGPT2525 LLC