Affinity Weighted Embedding
Authors: Jason Weston, Ron Weiss, Hector Yee
ICLR 2013

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.

arXiv:1301.4171v1  [cs.IR]  17 Jan 2013
Afﬁnity Weighted Embedding
Jason Weston
Google Inc.,
New York, NY , USA.
jweston@google.com
Ron Weiss
Google Inc.,
New York, NY , USA.
ronw@google.com
Hector Yee
Google Inc.,
San Bruno, CA, USA.
hyee@google.com
Abstract
Supervised (linear) embedding models like Wsabie [5] and PS I [1] have proven
successful at ranking, recommendation and annotation task s. However, despite
being scalable to large datasets they do not take full advant age of the extra data
due to their linear nature, and typically underﬁt. We propose a new class of models
which aim to provide improved performance while retaining many of the beneﬁts
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.
1 (Supervised) Linear Embedding Models
Standard linear embedding models are of the form:
f(x, y ) = x⊤U⊤V y =
∑
ij
xiU⊤
i Vj yj .
where x are the input features and y is a possible label (in the annotation case), document (in th e
information retrieval case) or item (in the recommendation case). These models are used in both
supervised and unsupervised settings. In the supervised ra nking case, they have proved successful
in many of the tasks described above, e.g. the Wsabie algorithm [5, 4, 6] which approximately opti-
mizes precision at the top of the ranked list has proven useful for annotation and recommendation.
These methods scale well to large data and are simple to imple ment and use. However, as they
contain no nonlinearities (other than in the feature repres entation in x and y) they can be limited in
their ability to ﬁt large complex datasets, and in our experience typically underﬁt.
2 Afﬁnity Weighted Embedding Models
In this work we propose the following generalized embedding model:
f(x, y ) =
∑
ij
Gij (x, y ) xiU⊤
i Vj yj.
where G is a function, built from a previous learning step, that meas ures the afﬁnity between two
points. Given a pair x, y and feature indices i and j, G returns a scalar. Large values of the scalar
indicate a high degree of match. Different methods of learni ng (or choosing) G lead to different
variants of our proposed approach:
1
• Gij (x, y ) = G(x, y ). In this case each feature index pair i, j returns the same scalar so the
model reduces to:
f(x, y ) = G(x, y ) x⊤U⊤V y.
• Gij (x, y ) = Gij . In this case the returned scalar for i, j is the same independent of the
input vector x and label y, i.e. it is a reweighting of the feature pairs. This gives themodel:
f(x, y ) =
∑
ij
Gij xiU⊤
i Vj yj .
This is likely only useful in large sparse feature spaces, e. g. if Gij represents the weight
of a word-pair in an information retrieval task or an item-pa ir in a recommendation task.
Further, it is possible that Gij could take a particular form, e.g. it is represented as a low
rank matrix Gij = g⊤
i gj. In that case we have the model f(x, y ) = ∑
ij g⊤
i gjxiU⊤
i Vj yj.
While it may be possible to learn the parameters of G jointly with U and V here we advocate an
iterative approach:
1. Train a standard embedding model: f(x, y ) = x⊤U⊤V y .
2. Build G using the representation learnt in (1).
3. Train a weighted model: f(x, y ) = ∑
ij Gij (x, y ) xi ¯U⊤
i ¯Vj yj .
4. Possibly repeat the procedure further: build ¯G from (3). (So far we have not tried this).
Note that the training algorithm used for (3) is the same as for (1) – we only change the model.
In the following, we will focus on the Gij (x, y ) = G(x, y ) case (where we only weight examples,
not features) and a particular choice of G1:
G(x, y ) =
m∑
i=1
exp(− λx||Ux − Uxi||2) exp(− λy||y − yi||2) (1)
where x and y are the sets of vectors from the training set.
G is built using the embedding U learnt in step (1), and is then used to build a new embedding
model in step (3). Due to the iterative nature of the steps we c an compute G for all examples
in parallel using a MapReduce framework, and store the train ing set necessary for step (3), thus
making learning straight-forward. To decrease storage, in stead of computing a smooth G as above
we can clip (sparsify) G by taking only the top n nearest neighbors to Ux, and set the rest to 0.
Further we take λy suitably large such that exp(− λy||y − yi||2) either gives 1 for yi = y or 0
otherwise2. In summary, then, for each training example, we simply have to ﬁnd the ( n = 20 in
our experiments) nearest neighboring examples in the embedding space, and then we reweight their
labels using eq. 1. (All other labels would then receive a wei ght of zero, although one could also
add a constant bias to guarantee those labels can receive non-zero ﬁnal scores.)
3 Experiments
So far, we have conducted two preliminary experiments on Mag natagatune (annotating music with
text tags) and ImageNet (annotation images with labels). Ws abie has been applied to both tasks
previously [4, 5].
On Magnatagatune we used MFCC features for both Wsabie and our method, similar to those used in
[4]. For both models we used an embedding dimension of 100. Ou r method improved over Wsabie
marginally as shown in Table 1. We speculate that this improv ement is small due to the small size
1Although perhaps G(x, y ) =
∑ m
i=1 exp(− λx||Ux − Uxi||2) exp(− λy||V y − V yi||2) would be more
natural. Further we could also considerGorig (x, y ) =
∑ m
i=1 exp(− λx||x− xi||2) exp(− λy||y− yi||2) which
does not make use of the embedding in step (1) at all. This would likely perform poorly when the input features
are too sparse, which would be the point of improving the representation by learning it with U and V .
2This is useful in the label annotation or item ranking settings, but would not be a good idea in an information
retrieval setting.
2
Table 1: Magnatagatune Results
Algorithm Prec@1 Prec@3
k-Nearest Neighbor 39.4% 28.6%
k-Nearest Neighbor (Wsabie space) 45.2% 31.9%
Wsabie 48.7% 37.5%
Afﬁnity Weighted Embedding 52.7% 39.2%
Table 2: ImageNet Results (Fall 2011, 21k labels)
Algorithm Prec@1
Wsabie (KPCA features) 9.2%
k-Nearest Neighbor (Wsabie space) 13.7%
Afﬁnity Weighted Embedding 16.4%
Convolutional Net [2] 15.6% (NOTE: on a different train/test split)
of the dataset (only 16,000 training examples, 104 input dimensions for the MFCCs and 160 unique
tags). We believe our method will be more useful on larger tasks.
On the ImageNet task (Fall 2011, 10M examples, 474 KPCA features and 21k classes) the improve-
ment over Wsabie is much larger, shown in Table 2. We used simi lar KPCA features as in [5] for
both Wsabie and our method. We use an embedding dimension of 1 28 for both. We also compare
to nearest neighbor in the embedding space. For our method, w e used the max instead of the sum
in eq. (1) as it gave better results. Our method is competitive with the convolutional neural network
model of [2] (note, this is on a different train/test split). However, we believe the method of [3]
would likely perform better again if applied in the same setting.
4 Conclusions
In conclusion, by incorporating a learnt reweighting funct ion G into supervised linear embedding
we can increase the capacity of the model leading to improved results. One issue however is that
the cost of reducing underﬁtting by using G is that it both increases the storage and computational
requirements of the model. One avenue we have begun exploring in that regard is to use approximate
methods in order to compute G.
References
[1] B. Bai, J. Weston, D. Grangier, R. Collobert, K. Sadamasa , Y . Qi, C. Cortes, and M. Mohri. Polynomial
semantic indexing. In NIPS, 2009.
[2] J. Dean, G. Corrado, R. Monga, K. Chen, M. Devin, Q. Le, M. M ao, A. Senior, P. Tucker, K. Yang, et al.
Large scale distributed deep networks. In Advances in Neural Information Processing Systems 25 , pages
1232–1240, 2012.
[3] A. Krizhevsky, I. Sutskever, and G. Hinton. Imagenet cla ssiﬁcation with deep convolutional neural net-
works. In Advances in Neural Information Processing Systems 25, pages 1106–1114, 2012.
[4] J. Weston, S. Bengio, and P. Hamel. Large-scale music ann otation and retrieval: Learning to rank in joint
semantic spaces. In Journal of New Music Research, 2012.
[5] J. Weston, S. Bengio, and N. Usunier. Wsabie: Scaling up t o large vocabulary image annotation. In Intl.
Joint Conf. Artiﬁcial Intelligence, (IJCAI), pages 2764–2770, 2011.
[6] J. Weston, C. Wang, R. Weiss, and A. Berenzeig. Latent col laborative retrieval. ICML, 2012.
3


Peer review:
[Review]:
Affinity Weighted Embedding

Paper summary

This paper extends supervised embedding models by combining them multiplicatively,
i.e. f'(x,y) = G(x,y) f(x,y).
It considers two types of model, dot product in the *embedding* space and kernel density in the *embedding* space, where the kernel in the embedding space is restricted to
k((x,y),(x','y)) = k(x-x')k(y-y').
It proposes an iterative algorithm which alternates f and G parameter updates.

Review Summary

The paper is clear and reads well. The proposed solution is novel. Combining local kernels and linear kernel in different embedding space could leverage the best characteristic for each of them (locality for non-linear, easier training for linear). The experiments are convincing. I would suggest adding the results for G alone.

Review Details

Step (2), i.e. local kernel, is interesting on its own. Could you report its result? The optimization problem seems harder than step (1), could you quantify how much the pretraining with step (1) helps step (2)?  A last related question, how do you initialize the parameters for step (3)?