24.131.80.19: fix link

2013-02-13T21:03:23Z

fix link

New page

'''Similarity learning''' is one type of a supervised [[machine learning]] task in [[artificial intelligence]]. It is closely related to [[regression (machine learning)|regression]] and [[classification in machine learning|classification]], but the goal is to learn from examples a function that measure how similar or related two objects are. It has applications in [[ranking]] and in [[recommendation systems]].

== Learning setup ==

There are three common setups for similarity and metric distance learning.

* ''[[Regression (machine learning)|Regression]] similarity learning''. In this setup, pairs of objects are given <math> (x_i^1, x_i^2) </math> together with a measure of their similarity <math> y_i \in R </math>. The goal is to learn a function that approximates <math> f(x_i^1, x_i^2) \sim y_i </math> for every new labeled triplet example <math>(x_i^1, x_i^2, y_i)</math>. This is typically achieved by minimizing a regularized loss <math> min_W \sum_i loss(w;x_i^1, x_i^2,y_i) + reg(w)</math>.
* ''[[Classification in machine learning|Classification]] similarity learning''. Given are pairs of similar objects <math>(x_i, x_i^+) </math> and non similar objects <math>(x_i, x_i^-)</math>. An equivalent formulation is that every pair <math>(x_i^1, x_i^2)</math> is given together with a binary label <math>y_i \in \{0,1\}</math> that determines if the two objects are similar or not. The goal is again to learn a classifier that can decide if a new pair of objects is similar or not.
* ''Ranking similarity learning''. Given are triplets of objects <math>(x_i, x_i^+, x_i^-)</math> whose relative similarity obey a predefined order: <math>x_i</math> is known to be more similar to <math>x_i^+</math> than to <math>x_i^-</math>. The goal is to learn a function <math>f</math> such that for any new triplet of objects <math>(x, x^+, x^-)</math>, it obeys <math>f(x, x^+) > f(x, x^-)</math>. This setup assumes a weaker form of supervision than in regression, because instead of providing an exact measure of similarity, one only has to provide the relative order of similarity. For this reason, ranking-based similarity learning is easier to apply in real large scale applications.<ref>{{cite journal|last=Chechik|first=Gal|coauthors=V. Sharma, U. Shalit, S. Bengio|title=Large Scale Online Learning of Image Similarity Through Ranking|journal=Journal of Machine Learning research|year=2010|volume=11|pages=1109–1135|url=http://www.jmlr.org/papers/volume11/chechik10a/chechik10a.pdf}}</ref>

A common approach for learning similarity, is to model the similarity function as a [[bilinear form]]. For example, in the case of ranking similarity learning, one aims to learn a matrix W that parametrizes the similarity function <math> f_W(x, z) = x^T W z </math>.

== Metric learning ==

Similarity learning is closely related to ''distance metric learning''. Metric learning is the task of learning a distance function over objects. A [[Metric (mathematics)|metric]] or [[distance function]] has to obey three axioms: [[non-negative|non-negativity]], [[symmetry]] and [[subadditivity]] / triangle inequality.

When the objects <math>x_i</math> are vectors in <math>R^d</math>, then any positive definite matrix <math>W>0</math> defines a distance function of the space of x through the bilinear form <math>f(x_1, x_2) = x_1^T W x_2</math>. Some well known approaches for metric learning include [[Large margin nearest neighbor]] <ref name=LMNN>{{cite journal|last=Weinberger|first=K.Q.|coauthors=Blitzer J. C., Saul L. K.|title=Distance Metric Learning for Large Margin Nearest Neighbor Classification|journal=Advances in Neural Information Processing Systems 18 (NIPS)|year=2006|pages=1473–1480|url=http://books.nips.cc/papers/files/nips18/NIPS2005_0265.pdf}}</ref>
, Information theoretic metric learning (ITML).<ref name=ITML>{{cite journal | last=Davis | first=J.V. | coauthors = Kulis B., Jain P., Sra s., Dhillon I.S. | title=Information-theoretic metric learning | journal=International conference in machine learning | year=2007 | pages=209–216 | url=http://www.cs.utexas.edu/users/pjain/itml/}}</ref>

In [[statistics]], the [[covariance]] matrix of the data is sometimes used to define a distance metric called [[Mahalanobis distance]].

== Applications ==
Similarity learning is used in information retrieval for learning to rank, and in [[recommendation systems]]. Also, many machine learning approaches rely on some metric. This include unsupervised learning such as [[clustering (machine learning)|clustering]], which groups together close or similar objects. It also includes supervised approaches like [[K-nearest neighbor algorithm]] which rely on labels of nearby objects to decide on the label of a new object. Metric learning has been proposed as a preprocessing step for many of these approaches
<ref name=XING>{{cite journal|last=Xing|first=E.P.|title=Distance Metric Learning, with Application to Clustering with Side-information | coauthors= Ng A.Y. Jordan MI. Jordan Russell S.| journal=Advances in Neural Information Processing Systems 15 | year=2002| pages = 505––512 | publisher = MIT Press}}</ref>

== Further reading ==
For further information on this topic, see the survey on metric and similarity learning by Bellet et al. <ref name=survey>{{cite arXiv |author=A. Bellet, A. Habrard, M. Sebban |eprint=1306.6709 |class=cs.LG |title=A Survey on Metric Learning for Feature Vectors and Structured Data |year=2013}}</ref>

== References ==
{{reflist}}

[[Category:Machine learning]]

Affine term structure model - Revision history

24.131.80.19: fix link