I’ve updated the Processing moviemaker library. Implemented more codecs and I think I fixed the Intel Mac bugs (but no way to tell since I don’t have one.) Hopefully nothing else broke in the process. Anyone reading this on an intel mac or windows machine, please test and let me know, thanks! Oh, and documentation coming soon!
A first pass at my Neural Networks in processing tutorial is ready for public consumption. So, before you go and consume a turkey, consume this link. And let me know if it makes any sense at all. . .? The examples are still trivial — Linear classification, Solving XOR — but I hope to develop some more advanced pattern recognition examples soon!
Is it a penguin? A tooth? A surfer from the future? Whatever it is, this announcement sure does make me happy. Read more about it at Create Digital Motion, one of my new favorite blogs!
So after a fierce battle with my own neurons, I am ready to release part II of my Processing series: “Neural Network! Huah! What is it good for? (Sing it again, now.)”
This example implements a multi-layered neural network that learns via “back propogation.” It’s specifically trained to solve XOR. In other words, there are two inputs and the desired result is input1 XOR input2.
0,1 –> 1
1,0 –> 1
0,0 –> 0
1,1 –> 0
The structure looks something like this:
However, I think there might be a flaw in my back propogation learning algorithm. For whatever reason, with the above neural structure, I can only successfully train my network (starting with random connection weights between -1 and 1) approximately 60% of the time. For the other 40%, the network gets stuck and can’t find the proper solution. If I add two more neurons to the hidden layer, like so. . .
. . . it trains flawlessly, finding a reasonable solution space after a few thousand training iterations 100% of the time (or at least as far as I can reasonably test.) What am I missing?
Anyway, a more involved tutorial about the theory, concepts, algorithms, and code behind neural networks is forthcoming. . . at some point. . . after I invent that machine that makes time that is . .
If you are downloading the source, note that the code for the nn.jar package is contained in /xor/code/src/nn. Because I’m using a large number of classes in the design of the network, I didn’t want to restrict myself to Processing tabs. Update (2/08/10): New download link: http://www.shiffman.net/teaching/nature/nn/
Long overdue, I’ve started working on a series of examples that implement neural networks. First up is the simplest, a little Perceptron that learns whether points live on one side of a line (in Cartesian space) or the other.
y = x*0.9-0.2
In this example, the perceptron is trained via an array of known point objects (with known answers), and the resulting “guess” line is displayed in real-time. I made the learning constant rather low so that one can see the slow progression of changing weights. I’ve been spending some quality time with Artifical Intelligence, by George Luger. It’s a wonderful book, and even better, it’s free for download online!
All the code is in the link, but here’s a quick peek at the meat of the matter: a function inside the Perceptron class that adjusts weights according to 3 input values and their corresponding “known” output. (Note if the perceptron’s guess output produces the desired result, the weights are not changed.)
A more involved write-up will arrive online at some point. . .
// Function to train the Perceptron // Weights are adjusted based on "desired" answer void train(float[] vals, int desired) { // Sum all the weights float sum = 0; for (int i = 0; i < weights.length; i++) { sum += vals[i]*weights[i]; } // The result is the sign of the sum int result = 1; // Start with 1 if (sum < 0) result = -1; // If less than zero, change to -1 // Compute factor to change weight // (DESIRED - RESULT): note this can only be 0, -2, or 2 // Multiply by learning constant float weightChange = c*(desired - result); // Adjust weights based on weightChange * input for (int i = 0; i < weights.length; i++) { weights[i] += weightChange * vals[i]; } }
For related work, check out Aaron Steed’s site.
Thanks to an idea from students in my icm class (see Catherine’s “greedy game-animated sprite”), I developed a Processing library that grabs values from Apple’s sudden motion sensor. The library is a JNI implementation of Unimotion by Lincoln Ramsay. It hasn’t been tested on an intel mac, so let me know if it works for people!
The above video is a brief demo of it in action. . . Now, what to use it for?!?!?
I’ve been meaning to add something to processing hacks for quite some time now. This morning, I needed a basic function to wrap text in Processing so came up with this snippet.
// Function to return an ArrayList of Strings // (maybe redo to just make simple array?) // Arguments: String to be wrapped, maximum width in pixels of line ArrayList wordWrap(String s, int maxWidth) { // Make an empty ArrayList ArrayList a = new ArrayList(); float w = 0; // Accumulate width of chars int i = 0; // Count through chars int rememberSpace = 0; // Remember where the last space was // As long as we are not at the end of the String while (i < s.length()) { // Current char char c = s.charAt(i); w += textWidth(c); // accumulate width if (c == ' ') rememberSpace = i; // Are we a blank space? if (w > maxWidth) { // Have we reached the end of a line? String sub = s.substring(0,rememberSpace); // Make a substring // Chop off space at beginning if (sub.length() > 0 && sub.charAt(0) == ' ') { sub = sub.substring(1,sub.length()); } // Add substring to the list a.add(sub); // Reset everything s = s.substring(rememberSpace,s.length()); i = 0; w = 0; } else { i++; // Keep going! } } // Take care of the last remaining line if (s.length() > 0 && s.charAt(0) == ' ') { s = s.substring(1,s.length()); } a.add(s); return a; }
This is a quick visualization of data from the netflix prize. A vertical bar is drawn for every customer rating a movie. Ratings go from 1 to 5 stars (represented top to bottom.) Note how “Alien” (on the left) received many ratings of 4 and 5 stars, but “Predator” (on the right) mostly received ratings of 4 stars. This depicts approximately 50,000 customer ratings.
Netflix recently released 100 million movie rating records as part of a contest to improve its movie recommendation system.
The problem:
I know how I rated a whole bunch of movies. I know how everyone else has rated a whole bunch of movies. For any given movie that I have not yet rated (but others have), predict how I would rate it based on my and everyone else’s rating history. Netflix uses the root mean squared error (RMSE) to evaluate results. In other words, let’s guess that I would give the movie Purple Rain a rating of 5, when in reality, I would only rate it a 4. And let’s also guess that I would rate Singin’ in the Rain a 3.5 when my true rating is a 5. Here’s how we would calculate the RMSE:
Purple Rain Prediction Error: 5 - 4 = 1 Singin' in the Rain Prediction Error: 3.5 - 5 = -1.5 Squaring each error: 1*1 = 1, -1.5*-1.5 = 2.25 Add the squares of all errors together = 3.25 MSE = Sum of Squares divided by Total Guesses = 3.25 / 2 = 1.625 RMSE = square root of MSE = sqrt(1.625) = 1.275
Let’s take a simple algorithm to solve the problem: for any user rating any movie, predict a future rating as the global average rating for that movie. This algorithm produces an RMSE of 1.05, not too shabby. The RSME for Netflix’s Cinematch system (which presumably employs collaborative filtering techniques) is around 0.95, a mere 10% improvement. The problem is indeed a difficult one. Netflix will award a one million dollar prize to anyone who can improve the system by an additional 10%.
I submitted my first prediction file today, mostly as a test, nowhere near the leaderboard, with the following algorithm:
A customer C will rating a movie M based on the following function:
rating(C,M) = 0.5 * (the global netflix average rating for movie M) + 0.5 * (the customer’s average rating)
My RMSE?
Your prediction file submitted 2006-10-10 21:31:56 has been decompressed and processed.
The computed RMSE for the quiz subset was 1.0147.
More to come. . .
