Visualizing the perfomance of Laplacian Eigenmaps on MNIST Digits
by Dinoj Surendran
Shameless plug: This demo was one of 50 semifinalists in the NSF's 2004 Science and Engineering Visualization Challenge. Specifically, one of nine semifinalists in the Interactive Media category. It didnt get any further, but I'm happy :)
Download : digits.zip. Runs on Windows and Linux, and on GeoWalls.
Download: pca_lap_usps.zip. USPS digits, seen using the first three dimensions of Principal Components Analysis and Laplacian Eigenmaps. When it starts, both are turned on - use the buttons to turn on one at a time.
How does the post office handle millions of letters every day? If humans had to look at each envelope, the answer would be "Not very well". What actually happens is that machines try reading the addresses on each envelope, and only hand them over to human readers if they fail to do so.
To do this, the machines must perform several tasks. One of them is Optical Character Recognition (OCR); on seeing a character, the machine must work out what it is. For instance, it should be able to work out that the digit to the left is a 4. A harder task is working out that the digit to the right is an 8 and not a 9.
OCR is a long-standing and important problem. This means that there are standard data sets that algorithms can be tested on. A popular one is the MNIST database of handwritten digits. The 4 and 8 above are from it.
Misha Belkin and Partha Niyogi have been working on a dimensionality reduction algorithm based on the Laplacian of a special graph defined on the digit pictures. You could say it does what the Principal Components Analysis algorithm does, only much better. (Btw, thanks to Misha for providing the results of his algorithm applied to the MNIST data set, and showing me how to get the digit pictures within Matlab. And pushing me to do this!)
For the purposes of visualization, it suffices to say that each digit in the MNIST data set is represented by a point in a high-dimensional space (R784) and the Laplacian algorithm maps it to a point in low-dimensional space (R3). Standard visualization tools allow you to plot these points in 3-space with all points for the same digit colored the same way, like this:
You can spin this around, zoom in and out, and so on. Partiview does this much better and faster than Matlab does, so you can easily explore the data in real-time.
That's nice, but with Partiview, it's just the start. You can also do the following:
The last point is especially important. In the case of digits, we have a natural picture - the original handwritten digits. For instance, below is a close-up shot (with colors turned off) of the clusters of 4s, 7s and 9s, which are at the end of the top arm in the above picture.
MPEG: 1024x768 (36Mb)
Animated gif of picture below : 500x340 (1.7Mb, ... note: IE on Windows doesnt like this animated gif).
What immediately jumps out at you with Partiview's visualization is that the 9's are between the 4's and 7's, and why this is so. This shows something which the researchers had not noticed before, and they can modify the way their algorithm is used accordingly.
How to get this data running on your machine
Download digits.zip, and unzip it. In Windows, click on digits.bat; in Linux, type "chmod +x digits.csh; ./digits.csh". If you have any trouble, read the file README.txt also provided in the zip archive.
To learn more about using Partiview, check out the Partiview Users Guide by Brian Abbott. For a more developer-oriented manual, check out the Partiview Manual by Peter Teuben and Stuart Levy. (Stuart is Partiview's creator.)