Fast Ranking Algorithm: Astonishing Paper by Raykar, Duraiswami, and Krishnapuram

The July 08 (Vol. 30, #7) IEEE Transactions on Pattern Analysis and Machine Intelligence has an incredible paper by Raykar, Duraiswami, and Krishnapuram. A Fast Algorithm for Learning a Ranking Function from Large-Scale Data Sets appears to be a game-changer for an incredibly important problem in machine learning. Basically, they use a “fast multipole method” developed for computational physics to rapidly estimate (to arbitrary precision) the conjugate gradient of an error function. (In other words, they tweak the parameters and “get a little better” the next time through the training data.)

The precise calculation of the conjugate gradient is O(m^2). This estimation algorithm is O(m)! (That’s an exclamation point, not a factorial!)

On a first reading, I don’t grok how the crucial transform necessarily moves towards an error minimum, but the algorithm looks (surprisingly) easy to implement and their benchmark results are jaw-dropping. Of course, others will have to implement it and analyze it for applicability across different types of data sets, but this is one of the most impressive algorithmic claims I’ve seen in years.

Once upon a time, I had the great fortune to write a column for a magazine on artificial intelligence and could justify spending huge amounts of time implementing AI algorithms (well, I think I was paid $450 per month for my column, so I’m not really sure that “justified” 80 hours of programming, but I was young). Man, would I love to see how this algorithm works for training a neural network…

Chess Champ Banned for Bluetooth-in-the-Ear During a Tournament

According to InformationWeek, Umakant Sharma, seeded 2nd in a tournament in New Delhi, was caught with a Bluetooth headset stitched into a cap that he wore “pulled down over his ears” during competition. According to the All India Chess Federation, accomplices fed him moves from a chess program. He’s been banned by FIDE for 10 years.

This reminds me of something I’ve discussed before — during Gary Kasparov’s famous 1997 battle with Deep Blue, he demanded that the program’s code be escrowed because Kasparov was of the belief that no computer could generate such play and that a human or humans must be feeding the machine moves. That response — an expert in his domain asserting that computer behavior “must be from a human” — always struck me as more important than the ability of the computer to ultimately grind down the world’s best chess player. The response was the first, and to date, closest thing to a triumph in the Turing test.

I have to admit it also reminds me of my own scandalous behavior in 3rd grade, when as a Cub Scout I made a pinewood derby car into which I could slip a fishing weight after the official weighing. I was caught because my car didn’t just win the race, it ran down the ramp about twice as fast as anything else (objects of different mass might fall in a vacuum at equal speed; objects with wire axles running through a wood block, not so much). Needless to say, that was the end of my time in scouting. (Although, to be fair, they actually wanted to have some kind of disciplinary thing and then let me continue. Somehow I never made it over to the Brennan’s house for that meeting.)

Cooperative Models For Neither Free-Beer Nor Free-Speech Software

The Netflix optimization challenge exemplifies a situation for which there should be a solution, but which I’ve not seen a good answer. Namely: for-profit but initially ad-hoc cooperation. For instance, let’s just say that I made the case that a Pandora-like “Movie Genome Project” was the key to winning the prize. And let’s say that you are sitting on top of a data-mining algorithm that you think will work great in conjunction with such a database. And let’s say that there are 5 people who, reading this, think “Well, I might not be able to contribute an algorithm, but for a piece of $1M, I’d be willing to ‘genotype’ some movies.”

The problem is: how do we go about working with each other? In the Open Source world, one can prototype a project by throwing it against the wall and seeing if it sticks: if people contribute or show interest, one can make a judgment about continuing or discontinuing the project. This works because all work, whether prototype or production, is given the same (free) value. However, if there’s money at stake, one cannot begin prototyping until “what if we win?” is sorted out. Even more importantly, the payoff percentages seem to necessarily be predetermined even though the relative contributions of all parties to the task won’t be known until after-the-fact.

I wonder if some derivative of a fairness-ensuring “cake cutting” algorithm can be applied to the problem.

Posted in AI

Genetic Algorithm For Kernel Tuning

Scott Swigart points to this article that gives a non-technical overview of the use of genetic algorithms to determine the optimal tuning characteristics of one’s Linux Kernel. This ought to work: many years ago I wrote a genetic algorithm that tuned the optimization parameters of one’s C++ compiler and it worked perfectly (well, who knows if it worked perfectly, but it did create better runtime performance than one would generally get from naive optimization options).

Posted in AI

Fascinating: Language Exposure Must Be Live, Not Recorded

Infants exposed to a Mandarin-speaking adult for less than 5 hours (25-minute sessions over 4 weeks) were “able to distinguish phonetic elements of that language.” Very impressive. But infants exposed to a similar amount of speech delivered over DVD could not. Fascinating. General-audience article here (via The Old New Thing)

My guess is that there’s a difference-in-kind to the type of attention that infants pay humans to the type of attention they pay brightly flickering screens. It would be interesting to see the effect of exposure to, say, a guy in a big purple talking dinosaur suit. Or is the key ingredient perhaps, non-verbal facial communication (eyes and so forth)?

I guess I can avoid “Offtopic” by slotting this under “AI”…

Posted in AI

Drools (Java-based inference engine) ported to .NET

Drools.NET is a port of the Drools library to .NET. I have a bg, big architectural decision coming up for a client and I am debating about whether to tackle the issue with an inference engine or a scripting language. So I’ve been looking at Drools pretty closely. It’s okay. I wouldn’t put it in the same league as ILog JRules, but the price is right and it seems to have momentum.

In the .NET front, I’ve been told there’s a Rete-based inference engine inside BizTalk (?), but I never followed up on that. Another tool is mTuitive’s xPert Authoring Environment. More to check out….

Compress Wikipedia, Win 20,000 Euros

 

Brilliant! The Hutter Prize for Lossless Compression (http://www.hutter1.net/prize.htm) takes as its challenge the task of compressing 100MB of Wikipedia text into the pre-competition best of ~17MB. The idea is that a chunk of Wikipedia text that big has characteristics relevant to compression that go beyond statistical analysis (i.e., “meaning”). The deliverable must be entirely self-contained, but it can be near 17MB in size in order to get in the money, so that’s a lot of space for generative code (there are no restrictions on runtime speed or memory consumption).

Posted in AI

Makers of NaturallySpeaking Raising Expectations for Voice Recognition

NaturallySpeaking 9, coming out in August, claims to dramatically reduce the time it takes to model your voice, achieving the best-possible recognition soon after opening the box.

For some people, that best-possible recognition is said to be 99%. Maybe. I’ve probably gone throught the “voice training” process a dozen or more times over the years. Not only have I never achieved 99%, I’ve never achieved anything usable.

There are several factors: one is that “tethered to your computer, wearing a noise-cancelling headset, and watching the dictation in realtime,” is not appealing to me. The second is that when you make a typo you are off by a coupe letters and then you get back on track. When a voice-reco system fails, the error mode is a parlor-game chain of semi-homonyms “wrecks a beach” == “recognize speech”.

I’m ever optimistic, though. As a writer, I’d love to be able to do significant amounts of work using a digital recorder (PDA, smartphone, what-have-you) on the beach. I’ve even thought of trying out those lost-cost (human) transcription services. Maybe I’ll give that a shot this National Novel Writing Month.

Posted in AI

Genetic Algorithms Outperform Humans In…

The Catalogue of Variable Frequency and Single-Resistance-Controlled Oscillators Employing A Single Differential Difference Complementary Current Conveyor which I imagine is self-explanatory to electrical engineers. Silver went to Multiobjective Genetic Algorithms for Multiscaling Excited-State Direct Dynamics in Photochemistry. Bronze prizes went to two things that I could actually understand:  A multi-population genetic algorithm for robust and fast ellipse detection  and Using Evolution to Learn How to Perform Interest Point Detection .

Posted in AI