Affinity Weighted Embedding

Jason Weston, Ron Weiss, Hector Yee

Introduction

In the realm of recommendation systems and large-scale image annotation, supervised linear embedding models like Wsabie and PSI have become industry standards. Their popularity stems from their incredible speed and ability to scale seamlessly to millions of items. These models operate by mapping features ($x$) and labels ($y$) into a shared low-dimensional space, where a simple dot product determines their match.

However, this simplicity comes with a significant drawback: they frequently underfit. Because the learned relationships are strictly linear, these models struggle to capture the nuanced, complex patterns inherent in massive, real-world datasets. Essentially, standard linear models lack the capacity required for the big data era.

To address this, researchers have developed Affinity Weighted Embedding (AWE). AWE is a novel method designed to boost the performance of linear embedding models by introducing non-linearity. By iteratively reweighting training examples based on their "affinity" (or similarity) to others in a learned embedding space, the model gains the capacity to fit complex datasets like ImageNet far better than standard linear approaches, all while retaining its crucial scalability.

Methodology: The Affinity Function

The core innovation of AWE is the introduction of an Affinity Function ($G$) into the standard embedding formula. Instead of relying on a simple linear match, the model's prediction function becomes:

$$f(x, y) = \sum_{ij} G_{ij}(x, y) x_i U^\top_i V_j y_j$$

To learn this effectively, the authors propose a clever iterative training approach:

  1. Initial Pass: Train a standard linear embedding model (such as Wsabie) to establish a baseline representation of the data.
  2. Build Affinity: Utilize the embeddings generated in Step 1 to calculate how "close" training examples are to one another. If a new input $x$ is highly similar to a cluster of training points in the embedding space, the function $G$ assigns it a higher weight. The authors specifically use a Gaussian-style kernel to measure this affinity.
  3. Weighted Training: Train a new model where the features and labels are reweighted by this affinity function.

In essence, the model uses its first "guess" at the data's structure to create a map, and then uses that map to focus its learning much more precisely during the second round. This makes the model behave somewhat like a "soft" version of a $k$-nearest neighbor classifier embedded within a neural framework.

Key Insights

  • Non-linearity via Reweighting: The breakthrough realization is that deep, highly complex architectures are not strictly necessary to achieve non-linearity. By reweighting inputs based on a previous iteration, AWE creates a locally adaptive model that can "bend" to fit the data much better than a rigid straight line.
  • Leveraging the "Map": Linear models are surprisingly adept at finding the general "neighborhood" of a data point. AWE exploits this strength by using the linear model to locate neighbors, and then letting the second-pass model learn the specific, fine-grained nuances of that neighborhood.
  • Parallelism is Key: Because the affinity weights ($G$) can be pre-calculated after the first pass, the second pass can be trained in parallel using distributed frameworks like MapReduce. This ensures the method remains viable for massive, Google-scale datasets.

Datasets and Key Results

The authors evaluated their approach on two distinct tasks to test both capacity and scalability:

  1. Magnatagatune: A music annotation dataset (approx. 16,000 examples) where the goal is to tag songs with text (e.g., "guitar," "classical").
  2. ImageNet (Fall 2011): A massive image classification dataset featuring 10 million examples and 21,000 distinct classes, serving as the primary "stress test."

The experimental results demonstrated that the benefits of AWE scale dramatically with the size of the data.

Performance on Magnatagatune (Small Data)

On the smaller dataset, AWE showed a solid, albeit marginal, improvement over the baselines.

Results on Magnatagatune dataset

As shown above, AWE improved Precision@1 from 48.7% (standard Wsabie) to 52.7%, successfully outperforming both standard $k$-Nearest Neighbor and the baseline linear embedding.

Performance on ImageNet (Large Data)

The performance jump was substantially more significant on the massive ImageNet dataset.

Results on ImageNet dataset

Standard Wsabie achieved a 9.2% Precision@1, whereas AWE reached 16.4%. Notably, at the time of the study, AWE was highly competitive with early Convolutional Neural Networks (which achieved 15.6%, though on a slightly different train/test split). While more advanced deep learning architectures (like AlexNet) would soon set higher benchmarks, AWE proved that massive gains could be extracted from linear models.

Limitations and Future Work

The primary drawback of AWE is its computational and storage overhead. Calculating the affinity function requires performing nearest-neighbor searches in the embedding space for every single training example, which is computationally expensive. Furthermore, storing these calculated weights increases the memory footprint of the training process.

The authors suggest that future work should focus on approximate methods for computing the affinity function $G$ to mitigate these costs. They also note the potential for further iterations (e.g., building a third model based on the second), though it remains to be seen if subsequent passes yield diminishing returns.

Summary updated

Abstract

Supervised (linear) embedding models like Wsabie and PSI have proven successful at ranking, recommendation and annotation tasks. However, despite being scalable to large datasets they do not take full advantage of the extra data due to their linear nature, and typically underfit. We propose a new class of models which aim to provide improved performance while retaining many of the benefits of the existing class of embedding models. Our new approach works by iteratively learning a linear embedding model where the next iteration's features and labels are reweighted as a function of the previous iteration. We describe several variants of the family, and give some initial results.
BibTeX
@inproceedings{weston2014affinity,
  author = {Jason Weston and Ron Weiss and Hector Yee},
  title = {{Affinity Weighted Embedding}},
  booktitle = {International Conference on Machine Learning},
  year = {2014},
}
Figure