0
$\begingroup$

I'm trying to learn ML, and have been reading Machine Learning Projects for .NET Developers by Mathias Brandewinder (I'm a C# developer by day, so this appealed to me). He uses the digit data available from Kaggle.

As a first stab at a metric to measure the "distance" between two images, he just sums up the absolute difference between corresponding pixels.

He then suggests improving this by using the Euclidian distance, ie the square root of the sum of squared differences, like you'd use to find the distance between two points in n-space.

This gave an improvement in the accuracy of his code, but I don't understand why. He's not interested in the actual "distance" between pairs of images, just in comparing distances, so he can choose the smallest.

Well, if you have an image to categorise, whose pixels are (x1,x2,...,xn), and you have two known images, with pixels (p1,p2,...,pn) and (q1,q2,...,qn), then if |x1-p1| < |x1-q1|, etc, then surely (x1-p1)^2 < (x2-q1)^2. If so, then whichever sum is smaller by the absolute method is also going to be smaller by the Euclidian method.

Don't know if I explained that clearly, but my basic question is, why is summing the squares of the differences going to give a better comparison than summing the absolute differences? Seems to me like it should give the same comparison, albeit with different actual distances.

Anyone able to explain?

$\endgroup$
2
$\begingroup$

I think your 1-dimension based intuition is misleading you here. L2 norm is bounded by L1 norm, but that doesn't mean the closest point is the same. You can see this already in 2-dimension:

enter image description here

Green and red points (in this 2 pixel image space) are same distance from the black image at the center in terms of L1 distance, but green is closer than red in terms of the L2 distance.

The error surface of L2 is better for naive optimization schemes, since it is differentiable. However, L1 is preferred for learning sparse solutions.

$\endgroup$
  • $\begingroup$ That's brilliant! Thanks so much for the excellent explanation. $\endgroup$ – Avrohom Yisroel Aug 23 '15 at 21:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.