Unsupervised Learning of the Set of Local Maxima

Lior Wolf, Sagie Benaim, Tomer Galanti

Overview

This paper introduces a novel unsupervised learning framework based on a compelling intuition: observed data points are rarely just random samples. Instead, they are often the "best" versions of themselves—local maxima—shaped by unknown constraints and optimization processes. By co-training a set indicator and a value comparator, the proposed model outperforms state-of-the-art one-class classifiers and naturally learns to disentangle class membership from signal quality.

The Problem: Data as Optimized Artifacts

In traditional unsupervised learning or one-class classification, models typically try to draw a boundary that encapsulates "normal" data. However, the authors argue this ignores a fundamental truth about the world. The entities we observe—whether they are biological genes, architectural designs, or even neural network weights—are frequently the result of an optimization process. We rarely see the "failed" or "low-value" versions because they have already been filtered out by evolution, physical constraints, or loss functions.

The challenge lies in the fact that we do not know the underlying "value function" or the "constraints" that produced the data. Standard methods that treat data as a simple distribution often require high model complexity to capture these nuances. This paper asks a fundamental question: Can we improve unsupervised learning by explicitly modeling data as the local maxima of an unknown function?

Methodology: Co-training an Indicator and a Comparator

The authors propose learning two distinct but collaborative functions to model these local maxima:

  1. The Indicator ($c$): A binary classifier that determines if a point satisfies the underlying constraints (i.e., does it belong to the valid set?).
  2. The Comparator ($h$): Instead of learning a raw, potentially unstable value function $v$, the model learns a comparator function. Given two nearby points, $h$ predicts which one has a higher value.

To train these functions without explicit labels, the authors employ a "hard negative" generation strategy using two adversarial generators, $G_c$ and $G_h$:

  • $G_c$ attempts to find points that the classifier $c$ accepts as valid, but the comparator $h$ deems inferior to the real data.
  • $G_h$ searches for points that are very close to the real data but have higher predicted values, forcing $h$ to recognize the training samples as the true local peaks.

This co-training setup is reminiscent of Generative Adversarial Networks (GANs). However, instead of a zero-sum game, the networks work collaboratively to carve out the manifold where the data lives and identify the "peaks" of quality on that manifold.

Key Insights

  • Disentangling "What" vs. "How Good": The separation of $c$ and $h$ naturally disentangles class identity from quality. In experiments, $c$ became a strong class detector, while $h$ became incredibly sensitive to image noise and blur—despite never being explicitly trained to detect noise.
  • Efficiency of Local Maxima: The authors mathematically demonstrate that modeling a set as the local maxima of a function can be computationally "cheaper" (requiring fewer hidden neurons) than attempting to model the exact same set using a standard classifier.
  • Unsupervised Discovery of Biological Signals: When applied to mRNA expression levels from The Cancer Genome Atlas (TCGA), the learned comparator $h$ showed a significant correlation with patient survival rates. The model essentially "discovered" that certain gene expressions were "less fit" (further from the local maxima), which translated to shorter longevity in patients—all without seeing a single survival label during training.

Key Results

The model was rigorously evaluated across several domains, including image classification (MNIST, CIFAR-10, GTSRB) and biological data.

Anomaly Detection on Standard Benchmarks On MNIST and CIFAR-10, the indicator $c$ consistently outperformed Deep SVDD and other baselines in one-class classification tasks. For instance, it achieved a 99.1% AUC on the MNIST digit '0'.

Anomaly detection performance on MNIST and CIFAR-10.

Robustness and Real-World Data (GTSRB) On the German Traffic Sign Recognition Benchmark (GTSRB), the method achieved an average AUC of 86.1% for multiclass anomaly detection, significantly higher than the 69.4% achieved by the Deep SVDD baseline. Furthermore, the comparator $h$ proved far superior to standard classifiers at distinguishing original images from those with added Gaussian noise, proving it successfully captured the "local peak" nature of clean data.

Performance on GTSRB dataset across multiclass and noisy settings.

Limitations and Future Work

While the results are compelling, the authors note a few areas for further exploration:

  • Training Complexity: The system requires training four separate networks ($c, h, G_c, G_h$), making it potentially more sensitive to hyperparameters than simpler one-class methods.
  • Monotonic Ambiguity: Because the model learns a comparator $h$ rather than an absolute value function $v$, the underlying value is only recovered up to an unknown monotonic transformation.

Future Applications: The authors suggest this framework could be revolutionary for fields like unsupervised drug design. By training the model on a library of known effective drugs, the indicator $c$ could filter out toxic or unstable molecules, while the comparator $h$ could serve as an optimization score to "hill-climb" toward even more effective molecular structures.

Summary updated

Abstract

This paper describes a new form of unsupervised learning, whose input is a set of unlabeled points that are assumed to be local maxima of an unknown value function $v$ in an unknown subset of the vector space. Two functions are learned: (i) a set indicator $c$, which is a binary classifier, and (ii) a comparator function $h$ that given two nearby samples, predicts which sample has the higher value of the unknown function $v$. Loss terms are used to ensure that all training samples $\vx$ are a local maxima of $v$, according to $h$ and satisfy $c(\vx)=1$. Therefore, $c$ and $h$ provide training signals to each other: a point $\vx'$ in the vicinity of $\vx$ satisfies $c(\vx)=-1$ or is deemed by $h$ to be lower in value than $\vx$. We present an algorithm, show an example where it is more efficient to use local maxima as an indicator function than to employ conventional classification, and derive a suitable generalization bound. Our experiments show that the method is able to outperform one-class classification algorithms in the task of anomaly detection and also provide an additional signal that is extracted in a completely unsupervised way.
BibTeX
@inproceedings{wolf2019unsupervised,
  author = {Lior Wolf and Sagie Benaim and Tomer Galanti},
  title = {{Unsupervised Learning of the Set of Local Maxima}},
  booktitle = {International Conference on Learning Representations},
  year = {2019},
  url = {https://openreview.net/forum?id=_pv7EykoZ84s},
}
Figure