When and How Does Known Class Help Discover Unknown Ones? Provable Understanding Through Spectral Analysis
When and How Does Known Class Help Discover Unknown Ones? Provable Understanding Through Spectral Analysis
复制标题
DOI：
10.48550/arxiv.2308.05017
复制
发表时间：
2023-08
期刊：
影响因子：
--
通讯作者：
Yiyou Sun;Zhenmei Shi;Yingyu Liang;Yixuan Li
中科院分区：
文献类型：
--
作者：
Yiyou Sun;Zhenmei Shi;Yingyu Liang;Yixuan Li
新类别发现（NCD）旨在通过利用来自具有已知类别的标记集的先验知识来推断未标记集中的新类别。尽管它很重要，但NCD缺乏理论基础。本文通过提供一个分析框架来弥补这一差距，该框架用于形式化和研究已知类别何时以及如何有助于发现新类别。针对NCD问题，我们引入了一种图论表示，它可以通过一种新的NCD谱对比损失（NSCL）来学习。最小化这个目标等同于对图的邻接矩阵进行分解，这使我们能够推导出一个可证明的误差界限，并为NCD提供充分必要条件。在实验上，NSCL在常见的基准数据集上能够匹配或优于几个强大的基线，这在具有理论保证的同时对于实际应用很有吸引力。
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.