Metric learning with linear methods
I read this paper a while ago, which sets out the problem of linear metric learning nicely but then proceeds to solve it in a way I personally thought unnecessarily indirect. It seemed to me that there was a neat analytical solution, so I thought I’d have a go. It turned out to be quite straightforward.
where \(A\) is a \(p \times p\) matrix. That is, let’s find a transformation \(A\) which makes the sum of squared difference between \(i\) and \(j\) similar, regardless of whether its calculated in terms of \(x\) or \(y\) . Call this act of changing our feature vectors to better match our responses, “metric learning”. It is interesting because many algorithms implicitly rely on similarity between feature vectors (e.g. Kernel methods, kNN), so they can be improved by making the distance metric more relevant to the problem at hand.
Let \(K\) be an \(m \times p^2\) matrix where each row the Kronecker product of a pair of vectors \((x_i-x_j) \otimes (x_i-x_j)\) , and let \(z\) be the vector containing the corresponding \((y_i - y_j)^\top(y_i - y_j)\) value, then it turns out we can solve \(K \vec{B} \approx z\) for \(\vec{B}\) in the usual least squares way, and then reshape \(\vec{B}\) back to \(B\) .
