LASS: A Simple Assignment Model with Laplacian Smoothing

Miguel Á. Carreira-Perpiñán, Weiran Wang

Abstract

We consider the problem of learning soft assignments of $N$ items to $K$ categories given two sources of information: an item-category similarity matrix, which encourages items to be assigned to categories they are similar to (and to not be assigned to categories they are dissimilar to), and an item-item similarity matrix, which encourages similar items to have similar assignments. We propose a simple quadratic programming model that captures this intuition. We give necessary conditions for its solution to be unique, define an out-of-sample mapping, and derive a simple, effective training algorithm based on the alternating direction method of multipliers. The model predicts reasonable assignments from even a few similarity values, and can be seen as a generalization of semisupervised learning. It is particularly useful when items naturally belong to multiple categories, as for example when annotating documents with keywords or pictures with tags, with partially tagged items, or when the categories have complex interrelations (e.g. hierarchical) that are unknown.

Introduction

In machine learning, assigning items to categories often involves balancing two distinct types of information: "expert" knowledge, such as specific tags or labels, and "crowd" knowledge, which is the inherent structure of the data suggesting that similar items should share similar labels. Traditional semi-supervised learning (SSL) methods often treat categories independently and fail to ensure that assignments form valid probability distributions.

The Laplacian Assignment (LASS) model, introduced by Miguel Á. Carreira-Perpiñán and Weiran Wang, addresses these shortcomings. LASS provides a framework for "soft assignments" (probabilistic labeling) that respects both individual affinities and the global geometry of the dataset, making it ideal for multi-label tasks with partial or negative supervision.

The LASS Model

LASS is formulated as a convex Quadratic Program (QP) that minimizes a cost function composed of two primary terms:

  1. The Linear Term (Expert Wisdom): Utilizing an item-category similarity matrix $G$, this term encourages assignments to categories with high affinity and penalizes assignments to those with negative affinity. Telling the model what an item isn't is often as powerful as telling it what it is.
  2. The Laplacian Term (Crowd Wisdom): Using a Graph Laplacian $L$ derived from item-item similarities, this term acts as a smoother, ensuring that items close in feature space receive similar assignments.

Crucially, LASS enforces simplex constraints. For every item, the assignments across all $K$ categories must be non-negative and sum to exactly 1. This coupling of categories ensures the output is a valid probability distribution, a feature often missing in standard SSL graph-based propagation.

Optimization via ADMM

To handle large-scale datasets, the authors employ the Alternating Direction Method of Multipliers (ADMM). This algorithm decomposes the optimization into two efficient steps:

  • Solving a sparse linear system (accelerated by Cholesky factorization).
  • Projecting the results onto the probability simplex.

This approach is computationally efficient and scales linearly with the number of items and categories, making it practical for real-world applications.

Experimental Evaluation

The model was tested across three diverse domains: MNIST (single-label handwritten digits), 20-Newsgroups (multi-topic document assignment), and the ESP Game (image tagging with extremely sparse labels).

Example image from the ESP Game dataset illustrating the challenge of partial tagging.

In datasets like the ESP Game, supervision is frequently incomplete; a user might tag an image with "dog" but omit "grass" or "outdoor." LASS excels here by using the data's manifold structure to "fill in" missing labels based on the assignments of similar images.

Key Results

LASS consistently outperformed traditional SSL and Support Vector Machines (SVMs), particularly in scenarios with limited labeled data.

Classification error vs. number of labeled items for MNIST and other datasets.

As shown in the performance plots, LASS (represented by the red line) achieves lower classification error rates as the number of labeled samples ($N_l$) increases, maintaining a competitive edge even with very few labels. The ADMM solver also proved highly efficient, solving problems with 10,000 items in under a minute on a standard PC.

Conclusion

LASS offers a robust and efficient way to perform soft assignments by unifying expert affinities with Laplacian smoothing. Its ability to handle negative labels and ensure valid probability outputs makes it a significant improvement over standard semi-supervised techniques. Future work includes extending the model to handle tensor data and incorporating explicit category-category relationships to further refine the assignment process.

Summary updated

Abstract

We consider the problem of learning soft assignments of N items to K categories given two sources of information: an item-category similarity matrix, which encourages items to be assigned to categories they are similar to (and to not be assigned to categories they are dissimilar to), and an item-item similarity matrix, which encourages similar items to have similar assignments. We propose a simple quadratic programming model that captures this intuition. We give necessary conditions for its solution to be unique, define an out-of-sample mapping, and derive a simple, effective training algorithm based on the alternating direction method of multipliers. The model predicts reasonable assignments from even a few similarity values, and can be seen as a generalization of semisupervised learning. It is particularly useful when items naturally belong to multiple categories, as for example when annotating documents with keywords or pictures with tags, with partially tagged items, or when the categories have complex interrelations (e.g. hierarchical) that are unknown.
BibTeX
@inproceedings{carreiraperpinan2014lass,
  author = {Miguel Á. Carreira-Perpiñán and Weiran Wang},
  title = {{LASS: A Simple Assignment Model with Laplacian Smoothing}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2014},
  url = {https://openreview.net/forum?id=SybGT1b_-r},
}
Figure