Thread by @bramcohen

And now for an explanation of how some classification algorithms work and an honest question (thread)

For classifying data like was used in the Netflix prize you have a big problem: There are lots of people and lots of movies, and the number of overlapping movie ratings different people gave is very small

In data science parlance the data is sparse and high dimensional. This makes it not very useful for guessing if a particular person would like a particular movie.

A trick for getting this under control is to map people and movies onto points on a square. You can find good positions iteratively: For each person who didn't like a movie, nudge their points farther apart, for ones who liked it, move them together.

Repeat this process until things stabilize. This reduces the high dimensional data down to two dimensions and allows you to apply a normal distance function to guess whether a person will like a movie. It's a good idea, but can be improved on.

Consider what happens if what you really have is three clusters plus noise. If you put them in a square then there are a few possible configurations they could wind up in: two in adjacent corners and one in the middle of the opposite edge, or \

put into three separate corners. In the first case one pair of groups will seem closer than the others, in the second one will seem farther than the others. There will always be an odd one out and which direction it is and even which it is will \

be entirely an arbitrary accident of your starting position. Obviously this isn't ideal: if there are three equidistant groups, it should say they're equidistant.

The obvious problem is the corners. They're different from the rest of the space and make it non-homogeneous. If you make the space toroidal (wrapping around the sides) the situation is probably improved.

What exactly happens with three on toroidal is an interesting question, but it's possible to do better so let's skip to the improvement

The better approach is to map to points on the surface of a sphere with the distance between two points counted as the angle lines from them to the center make.

The math for this is simple and elegant and has to do with the cosine of the angle between two unit vectors being their dot product. You can search for those terms for details, for now you can trust me that it's elegant

If you apply the test of the true grouping being three clusters this is now much improved: They'll get equally spaced about an equatorial line and be equidistant from each other. Four will go to corners of a tetrahedron and again work well

Six is more awkward though: They'll go to the centers of the faces of a cube and each group will seem to be closer to four of the others than the fifth, which is maximally distant from

Now for my honest question: Why not use a projective plane? For those who don't know, which is probably almost everyone reading this, a projective plane can be implemented by glueing opposite points on a sphere to each other

So the angle between two points is either x or 180-x, whichever is smaller. This space has some funky properties: If you were to be in it and go in a straight line until you returned to where you started your handedness relative to the rest of the world would

be the opposite of what you started with. But we're just talking about points here which don't have handedness so it doesn't matter.

Our equidistant cases now seem much better. Three groups go to orthogonal face centers of a cube and not only are they equidistant but adding the third group doesn't force the other two to move around.

Six groups is much improved. They'll go to the corners of an icosahedron and be equidistant.

Five groups is a bit awkward in all cases and I'm not sure exactly what it does but if you go to a 4-projective plane instead of a 2-projective plane they all wind up exactly orthogonal. It doesn't seem to work that well no matter how many dimensions of regular sphere you use

As you go up in number of dimensions the complexity of geometry it can handle goes up rapidly but you'll always get funny artifacts when the number of them is greater than the kissing number of that number of dimensions

Of course going up in number of dimensions also tends to make everything look equidistant from everything else and make the classifier's predictions not very useful in practice.

If anybody knows whether the projective plane approach is already widely used, known to have issues, or a promising idea I'd like to hear about it!

Somehow Twitter munged the threading of this and it's a bit of a tree rather than a list. Oops. Deleting the out of order tweets and moving them to the end now

Four groups go to the four corners of a cube and are all equidistant. Like with the face centers they come in opposite pairs so on a projective plane the number of them is halved: three faces instead of six, four corners instead of eight