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:

  • You can group data into groups, so that with one click of a button all the points representing '2's (or '8's or '0's) get turned off or on. This makes it easy to hunt down outliers.
  • You can associate labels with each points, and turn them off easily.
  • You can make movies (animated gifs or mpegs) of you moving through the data. Very nice for conferences and showing off on webpages.
  • You can associate each point with a picture.

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)

Older MPEGs, with non-colored digits: 1024 x 768 (27Mb), 800 x 600 (19Mb)

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.

Navigation

  • Rotation (around the origin) : left click (and hold!) the mouse and move. Once you release the mouse button, the rotation continues with the speed at which you were moving the mouse before you let go.
  • Stopping motion: click once with the mouse.
  • Zooming: Right click (and hold!) the mouse and move up and down. (If you have a Mac with a one-button mouse, press the option key as you click that button.)
  • Translation. Press f. Left click (and hold if necessary - you'll get the hang of it) and move. When happy, stop the motion and press o. You're back in the 'orbit' mode that enables you to do 'everything' else except translation.
  • There are buttons near the top labelled "g1=digit_1",..., "g10=digit_0". Turn them off and on to turn the corresponding points off/on.

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.)