ai on your ipod shuffle

AI on your iPod Shuffle

I was browsing Beyond Satire, a site run by Ellen Spertus (one of my

summer colleagues on the orkut team), and I happened to hit a link

about something called the Martin Shuffle. It turned out to be a name

for a way to find a particular song using the "shuffle" and "next"

features of the iPod shuffle. I read the article and was both

intrigued and amused because it tried to apply some randomized

mathematical analysis on iPod Shuffle usage; namely, the writer was

analyzing what the optimal policy would be for finding a particular

song on the iPod shuffle and how long that would take.

Two elements in the article caught my attention. One, on the right

side of the page, there was an image of the Randomized Algorithms

textbook that was used in Karger's 6.856 class, a class that I took,

enjoyed, thought was consuming my life and causing endless pain, and

subsequently dropped. Second, the analysis used the concept of Markov

Decision Processes (MDP), a term that I vaguely remembered from

Kaelbling's 6.825 class (Techniques in AI).

Quite frankly, this was one of the coolest AI/mathematical/algorithm

articles that I've read in some time. For a while, my impression of AI

has been that it was too heavyweight and abstract for solving

real-world decision problems. AI papers that I've read, AI problem

sets that I've done, and AI lectures that I've attended typically

dealt with toy problems rather than the more complicated ones that we

encounter in real life. Moreover, I had not really built a real-world

application that used a major AI technique (we're discounting search

in this discussion).

What suprised me the most was that the analysis was elegant and that

the author actually provided short Python code to implement a value

iteration algorithm for solving MDPs. The code was lightweight,

nothing substantial that would've even taken me, a novice in the world

of Python, to write. More importantly, it was concrete where the

lectures that I had on MDPs were abstract. In short, I was amazed and

inspired that the author could take something that I thought to be

abstract, i.e. MDPs, and apply it to a fun but still real question. If

only 6.825 had used fun examples like this instead of robots trying to

vacuum dust from rooms or avoiding monsters, I might actually have

found the material more interesting.

It was clear that the article was written by someone with a nerdy

sense of humor. Upon checking the URL, I realized that the article was

written by none other than Peter Norvig - the author of Artificial

Intelligence: A Modern Approach (AIMA) and the Director of Web Search

Quality at Google. From skimming his website, I saw that he actually

had other pieces of Python code doing practical, lightweight, and

intelligible AI. From reading the article, I'm actually inspired to

bust out my copy of AIMA, relearn some AI techniques that I had

previously thought to be of mainly theoretical value, and see what

other neat questions AI can answer.