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

• URL: http://arxiv.org/abs/2308.05017v1
• Date: Wed, 9 Aug 2023 15:27:21 GMT
• Title: When and How Does Known Class Help Discover Unknown Ones? Provable Understanding Through Spectral Analysis
• Authors: Yiyou Sun, Zhenmei Shi, Yingyu Liang, Yixuan Li
• Abstract summary: Novel Class Discovery (NCD) aims at inferring novel classes in an unlabeled set by leveraging prior knowledge from a labeled set with known classes. This paper bridges the gap by providing an analytical framework to formalize and investigate when and how known classes can help discover novel classes.
• Score: 35.57142091571271
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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.

Related papers

• LSEnet: Lorentz Structural Entropy Neural Network for Deep Graph Clustering [59.89626219328127]
  Graph clustering is a fundamental problem in machine learning. Deep learning methods achieve the state-of-the-art results in recent years, but they still cannot work without predefined cluster numbers. We propose to address this problem from a fresh perspective of graph information theory.
  arXiv  Detail & Related papers  (2024-05-20T05:46:41Z)
• A Practical Approach to Novel Class Discovery in Tabular Data [38.41548083078336]
  Novel Class Discovery (NCD) is a problem of extracting knowledge from a labeled set of known classes to accurately partition an unlabeled set of novel classes. In this work, we propose to tune the hyper parameters of NCD methods by adapting the $k$-fold cross-validation process and hiding some of the known classes in each fold. We find that the latent space of this method can be used to reliably estimate the number of novel classes.
  arXiv  Detail & Related papers  (2023-11-09T15:24:44Z)
• A Graph-Theoretic Framework for Understanding Open-World Semi-Supervised Learning [33.05104609131764]
  Open-world semi-supervised learning aims at inferring both known and novel classes in unlabeled data. This paper formalizes a graph-theoretic framework tailored for the open-world setting. Our graph-theoretic framework illuminates practical algorithms and provides guarantees.
  arXiv  Detail & Related papers  (2023-11-06T21:15:09Z)
• Benign Overfitting in Deep Neural Networks under Lazy Training [72.28294823115502]
  We show that when the data distribution is well-separated, DNNs can achieve Bayes-optimal test error for classification. Our results indicate that interpolating with smoother functions leads to better generalization.
  arXiv  Detail & Related papers  (2023-05-30T19:37:44Z)
• NEV-NCD: Negative Learning, Entropy, and Variance regularization based novel action categories discovery [23.17093125627668]
  Novel Categories Discovery (NCD) facilitates learning from a partially annotated label space. We propose a novel single-stage joint optimization-based NCD method, Negative learning, Entropy, and Variance regularization NCD. We demonstrate the efficacy of NEV-NCD in previously unexplored NCD applications of video action recognition.
  arXiv  Detail & Related papers  (2023-04-14T19:20:26Z)
• Large-scale Pre-trained Models are Surprisingly Strong in Incremental Novel Class Discovery [76.63807209414789]
  We challenge the status quo in class-iNCD and propose a learning paradigm where class discovery occurs continuously and truly unsupervisedly. We propose simple baselines, composed of a frozen PTM backbone and a learnable linear classifier, that are not only simple to implement but also resilient under longer learning scenarios.
  arXiv  Detail & Related papers  (2023-03-28T13:47:16Z)
• Parametric Classification for Generalized Category Discovery: A Baseline Study [70.73212959385387]
  Generalized Category Discovery (GCD) aims to discover novel categories in unlabelled datasets using knowledge learned from labelled samples. We investigate the failure of parametric classifiers, verify the effectiveness of previous design choices when high-quality supervision is available, and identify unreliable pseudo-labels as a key problem. We propose a simple yet effective parametric classification method that benefits from entropy regularisation, achieves state-of-the-art performance on multiple GCD benchmarks and shows strong robustness to unknown class numbers.
  arXiv  Detail & Related papers  (2022-11-21T18:47:11Z)
• Learning to Detect Critical Nodes in Sparse Graphs via Feature Importance Awareness [53.351863569314794]
  The critical node problem (CNP) aims to find a set of critical nodes from a network whose deletion maximally degrades the pairwise connectivity of the residual network. This work proposes a feature importance-aware graph attention network for node representation. It combines it with dueling double deep Q-network to create an end-to-end algorithm to solve CNP for the first time.
  arXiv  Detail & Related papers  (2021-12-03T14:23:05Z)
• On the Tractability of Neural Causal Inference [19.417231973682366]
  sum-product network (SPN) offers linear time complexity. neural causal models (NCM) recently gained traction, demanding a tighter integration of causality for machine learning. We prove that SPN-based causal inference is generally tractable, opposed to standard-based NCM.
  arXiv  Detail & Related papers  (2021-10-22T20:38:01Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.