A Graph-Theoretic Framework for Understanding Open-World Semi-Supervised Learning (2023-11-06T00:00:00.000000Z)

TL;DR

This paper formalizes a graph-theoretic framework tailored for the open-world setting, where the clustering can be theoretically characterized by graph factorization, and applies the algorithm called Spectral Open-world Representation Learning (SORL), which can match or outperform several strong baselines on common benchmark datasets.

Abstract

Open-world semi-supervised learning aims at inferring both known and novel classes in unlabeled data, by harnessing prior knowledge from a labeled set with known classes. Despite its importance, there is a lack of theoretical foundations for this problem. This paper bridges the gap by formalizing a graph-theoretic framework tailored for the open-world setting, where the clustering can be theoretically characterized by graph factorization. Our graph-theoretic framework illuminates practical algorithms and provides guarantees. In particular, based on our graph formulation, we apply the algorithm called Spectral Open-world Representation Learning (SORL), and show that minimizing our loss is equivalent to performing spectral decomposition on the graph. Such equivalence allows us to derive a provable error bound on the clustering performance for both known and novel classes, and analyze rigorously when labeled data helps. Empirically, SORL can match or outperform several strong baselines on common benchmark datasets, which is appealing for practical usage while enjoying theoretical guarantees.

Authors

Yiyou Sun

2 papers

Zhenmei Shi

1 papers

Yixuan Li

1 papers

TL;DR

Abstract

Authors

References86 items

Dream the Impossible: Outlier Imagination with Diffusion Models

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

OpenOOD v1.5: Enhanced Benchmark for Out-of-Distribution Detection

Feed Two Birds with One Scone: Exploiting Wild Data for Both Out-of-Distribution Generalization and Detection

Dynamic Conceptional Contrastive Learning for Generalized Category Discovery

Non-Parametric Outlier Synthesis

The Trade-off between Universality and Label Efficiency of Representations from Contrastive Learning

PromptCAL: Contrastive Affinity Learning via Auxiliary Prompts for Generalized Novel Category Discovery

OpenCon: Open-world Contrastive Learning

OpenLDN: Learning to Discover Novel Classes for Open-World Semi-Supervised Learning

Contrastive and Non-Contrastive Self-Supervised Learning Recover Global and Local Spectral Embedding Methods

Beyond Separability: Analyzing the Linear Transferability of Contrastive Representations to Related Subpopulations

Connect, Not Collapse: Explaining Contrastive Learning for Unsupervised Domain Adaptation

Class-Aware Contrastive Semi-Supervised Learning

Generalized Category Discovery

A Unified Objective for Novel Class Discovery

Trash to Treasure: Harvesting OOD Data with Cross-Modal Matching for Open-Set Semi-Supervised Learning

Novel Visual Category Discovery with Dual Ranking Statistics and Mutual Knowledge Distillation

OpenCoS: Contrastive Semi-supervised Learning for Handling Open-set Unlabeled Data

Provable Guarantees for Self-Supervised Deep Learning with Spectral Contrastive Loss

Neighborhood Contrastive Learning for Novel Class Discovery

OpenMatch: Open-set Consistency Regularization for Semi-supervised Learning with Outliers

VICReg: Variance-Invariance-Covariance Regularization for Self-Supervised Learning

Barlow Twins: Self-Supervised Learning via Redundancy Reduction

Open-World Semi-Supervised Learning

Exploring Simple Siamese Representation Learning

Contrastive learning, multi-view redundancy, and linear models

Predicting What You Already Know Helps: Provable Self-Supervised Learning

Multi-Task Curriculum Framework for Open-Set Semi-Supervised Learning

Safe Deep Semi-Supervised Learning for Unseen-Class Unlabeled Data

Unsupervised Learning of Visual Features by Contrasting Cluster Assignments

Understanding Contrastive Representation Learning through Alignment and Uniformity on the Hypersphere

Supervised Contrastive Learning

Semi-Supervised Learning under Class Distribution Mismatch

Conditional Gaussian Distribution Learning for Open Set Recognition

Contrastive estimation reveals topic posterior information to linear models

A Simple Framework for Contrastive Learning of Visual Representations

FixMatch: Simplifying Semi-Supervised Learning with Consistency and Confidence

Momentum Contrast for Unsupervised Visual Representation Learning

Learning to Discover Novel Visual Categories via Deep Transfer Clustering

Semi-Supervised Learning with Scarce Annotations

S4L: Self-Supervised Semi-Supervised Learning

First-order Perturbation Theory for Eigenvalues and Eigenvectors

A Theoretical Analysis of Contrastive Unsupervised Representation Learning

Multi-class Classification without Multi-class Labels

UMAP: Uniform Manifold Approximation and Projection

Representation Learning with Contrastive Predictive Coding

SpectralNet: Spectral Clustering using Deep Neural Networks

Learning to cluster in order to Transfer across domains and tasks

CLEVR: A Diagnostic Dataset for Compositional Language and Elementary Visual Reasoning

Temporal Ensembling for Semi-Supervised Learning

Regularization With Stochastic Transformations and Perturbations for Deep Semi-Supervised Learning

Deep Residual Learning for Image Recognition

Impact of regularization on spectral clustering

Multi-way spectral partitioning and higher-order cheeger inequalities

Large Graph Construction for Scalable Semi-Supervised Learning

Semi-Supervised Learning in Gigantic Image Collections

Prototype vector machine for large scale semi-supervised learning

Graph construction and b-matching for semi-supervised learning

Unlabeled data: Now it helps, now it doesn't

The asymptotics of semi-supervised learning in discriminative probabilistic models

Statistical Analysis of Semi-Supervised Regression

A tutorial on spectral clustering

Label Propagation through Linear Neighborhoods

Generalization Error Bounds in Semi-supervised Classification Under the Cluster Assumption

Combining Graph Laplacians for Semi-Supervised Learning

A PAC-Style Model for Learning from Labeled and Unlabeled Data

Semi-supervised Learning on Directed Graphs

Combining active learning and semi-supervised learning using Gaussian fields and harmonic functions

Learning from labeled and unlabeled data with label propagation

Spectral partitioning of random graphs

Learning from Labeled and Unlabeled Data using Graph Mincuts

On Spectral Clustering: Analysis and an algorithm

On clusterings-good, bad and spectral

Normalized cuts and image segmentation

The Hungarian method for the assignment problem