When and How Does Known Class Help Discover Unknown Ones? Provable Understanding Through Spectral Analysis

Yiyou Sun, Zhenmei Shi, Yingyu Liang, Yixuan Li
Proceedings of the 40th International Conference on Machine Learning, PMLR 202:33014-33043, 2023.

Abstract

Novel Class Discovery (NCD) aims at inferring novel classes in an unlabeled set by leveraging prior knowledge from a labeled set with known classes. Despite its importance, there is a lack of theoretical foundations for NCD. This paper bridges the gap by providing an analytical framework to formalize and investigate when and how known classes can help discover novel classes. Tailored to the NCD problem, we introduce a graph-theoretic representation that can be learned by a novel NCD Spectral Contrastive Loss (NSCL). Minimizing this objective is equivalent to factorizing the graph’s adjacency matrix, which allows us to derive a provable error bound and provide the sufficient and necessary condition for NCD. Empirically, NSCL can match or outperform several strong baselines on common benchmark datasets, which is appealing for practical usage while enjoying theoretical guarantees.

Cite this Paper

BibTeX
@InProceedings{pmlr-v202-sun23i, title = {When and How Does Known Class Help Discover Unknown Ones? {P}rovable Understanding Through Spectral Analysis}, author = {Sun, Yiyou and Shi, Zhenmei and Liang, Yingyu and Li, Yixuan}, booktitle = {Proceedings of the 40th International Conference on Machine Learning}, pages = {33014--33043}, year = {2023}, editor = {Krause, Andreas and Brunskill, Emma and Cho, Kyunghyun and Engelhardt, Barbara and Sabato, Sivan and Scarlett, Jonathan}, volume = {202}, series = {Proceedings of Machine Learning Research}, month = {23--29 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v202/sun23i/sun23i.pdf}, url = {https://proceedings.mlr.press/v202/sun23i.html}, abstract = {Novel Class Discovery (NCD) aims at inferring novel classes in an unlabeled set by leveraging prior knowledge from a labeled set with known classes. Despite its importance, there is a lack of theoretical foundations for NCD. This paper bridges the gap by providing an analytical framework to formalize and investigate when and how known classes can help discover novel classes. Tailored to the NCD problem, we introduce a graph-theoretic representation that can be learned by a novel NCD Spectral Contrastive Loss (NSCL). Minimizing this objective is equivalent to factorizing the graph’s adjacency matrix, which allows us to derive a provable error bound and provide the sufficient and necessary condition for NCD. Empirically, NSCL can match or outperform several strong baselines on common benchmark datasets, which is appealing for practical usage while enjoying theoretical guarantees.} }
Endnote
%0 Conference Paper %T When and How Does Known Class Help Discover Unknown Ones? Provable Understanding Through Spectral Analysis %A Yiyou Sun %A Zhenmei Shi %A Yingyu Liang %A Yixuan Li %B Proceedings of the 40th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2023 %E Andreas Krause %E Emma Brunskill %E Kyunghyun Cho %E Barbara Engelhardt %E Sivan Sabato %E Jonathan Scarlett %F pmlr-v202-sun23i %I PMLR %P 33014--33043 %U https://proceedings.mlr.press/v202/sun23i.html %V 202 %X Novel Class Discovery (NCD) aims at inferring novel classes in an unlabeled set by leveraging prior knowledge from a labeled set with known classes. Despite its importance, there is a lack of theoretical foundations for NCD. This paper bridges the gap by providing an analytical framework to formalize and investigate when and how known classes can help discover novel classes. Tailored to the NCD problem, we introduce a graph-theoretic representation that can be learned by a novel NCD Spectral Contrastive Loss (NSCL). Minimizing this objective is equivalent to factorizing the graph’s adjacency matrix, which allows us to derive a provable error bound and provide the sufficient and necessary condition for NCD. Empirically, NSCL can match or outperform several strong baselines on common benchmark datasets, which is appealing for practical usage while enjoying theoretical guarantees.
APA
Sun, Y., Shi, Z., Liang, Y. & Li, Y.. (2023). When and How Does Known Class Help Discover Unknown Ones? Provable Understanding Through Spectral Analysis. Proceedings of the 40th International Conference on Machine Learning, in Proceedings of Machine Learning Research 202:33014-33043 Available from https://proceedings.mlr.press/v202/sun23i.html.

Related Material