I'll take "The Humans" for $1,000,000, Alex. (The obligatory Watson post.)

Full disclosure: I worked one day a week for a year on improving Watson's speech synthesis.  While I think the voice added flair and personality to the exhibition, everyone knows that question-answering is what Watson is all about. And I didn't have any hand in that.

Wednesday marked the end of the three day exhibition Jeopardy! match between Watson, IBM's question answering system, Ken Jennings and Brad Rutter.  Watson decisively beat the human competitors.

There is no shortage of commentary on the implications of Watson's victory.   One of my favorite pieces was by Ken Jennings himself.  He's played more games of Jeopardy! than anyone else, and describes the experience in a very measured way.

One of his observations sticks out: "I expected Watson's bag of cognitive tricks to be fairly shallow, but I felt an uneasy sense of familiarity as its programmers briefed us before the big match: The computer's techniques for unraveling Jeopardy! clues sounded just like mine."

 It is in this that Watson represents a step forward for Artificial Intelligence.

There is a human exceptionalism that most people have when discussing "intelligence".  This exceptionalism leads to a dismissal of the success of Deep Blue's defeat of Kasparov as computation not intelligence.  It leads to descriptions of Watson as a "big database".  The same exceptionalism leads to the Turing Test as the final arbiter of intelligence.

Prediction: No machine will ever pass the Turing Test.

The test is explicitly defined to defend the exceptionalism of human intelligence.  It all but explicitly says, "humans are intelligent. To be intelligent, you must be indistinguishable from a human."

Before this test is passed, machines will continue to perform tasks which we consider to demonstrate intelligence better than humans can.  Chess: done.  Quiz shows: done. Mathematical theorem proving: done.  What's next? Perfect SAT scores. Perfect GRE scores?  Writing a five paragraph essay?  All conceivable in the next, say, five years.  Performing basic research and writing an accepted peer-reviewed publication of its findings.  Certainly further off, but not inconceivable.  But none of these systems would pass the Turing Test; people would still ask, "can it make me coffee?" or "can it tell me why Ronnie and Sam are still together?"  And yet, progress in artificial intelligence will be undeterred.

Ray Kurzweil's prediction of a self-aware system will almost certainly predate one that can convince us that it is human.  Despite its ability to describe its "thought" process, and outperform humans on tasks that were formerly considered representative behavior, there will be those that won't consider this system "intelligent" until it passes the Turing Test.

Watson's success comes from some very impressive machine learning and natural language processing, not only in its ability to generate answers quickly, but in its collection of knowledge.  The individual ml and nlp components used in Watson may individually be incremental improvements on previously existing approaches.  Yet this doesn't mean that Watson is itself an incremental milestone.  Watson bested a human at a task that we believed, until Wednesday night, required intelligence.  But more impressively, it won in a way that was similar (in spirit if not in hardware) to the way humans play Jeopardy!

Requisite CYA: As always, this post doesn't represent anyone's views other than my own.

P == NP. The battle rages on.

Last summer, Vinay Deolalikar claimed to have proved that P!=NP.  This kicked up some terrific math and computer science dust, and a lot of people got excited, myself included.  But this wasn't exactly a surprising result...most people suspect that P != NP after all, but a proof has been elusive.

Well, evening out the playing field, Vladimir Romanov claims to have come up with a polynomial time algorithm for 3-SAT -- one of the foundational NP-hard problems. Here's the paper describing the work.  But what's more...there's source code for it.  If he's right, then P==NP.

I fully expect that people will be picking this work apart pretty rigorously over the next few weeks, months and years.  But if it holds up, it's a really big deal.  Much bigger than P!=NP, most specifically because it implies that large factorization can be solved in polynomial time, which means all of our encryption is broken.

AuToBI Version 1.1

I've made enough improvements to AuToBI to consider the toolkit a milestone more mature.

In addition to some uninteresting bug fixes, and refactoring, the version 1.1 is made up by 3 significant changes.  As ever, the AuToBI homepage includes milestone releases, and the project itself is hosted on github.

1) Package restructuring.

The internal structure makes more sense now.  Classes are divided into 'core', 'feature extractors', 'classifiers', 'feature sets', 'io' and 'utilities'.  With over 100 classes, the code had outgrown a flat package structure.  Unfortunately this restructuring changed the serialization signatures of class names.  This means that old models won't work with the version 1.1 release.  But I have new models trained on the Boston Directions Corpus and Boston Radio News Corpus which will be available from the AuToBI homepage shortly.

2) Implemented reference counting for Feature maintenance.

The feature extraction process allows a user to specify the features they want without explicitly going through all the intermediate steps to extract them.  For example, extracting the mean speaker normalized pitch from the second half of a word requires pitch to be extracted, speaker normalization parameters to be calculated or retrieved, the pitch to be normalized, the second half of the word to be identified, and finally the mean calculated.  In AuToBI each of these steps are treated as features that are required by the feature extraction of the user-desired feature.  In version 1.0, AuToBI was able to identify which features were required, but never recognized when a feature wasn't needed any longer.  Version 1.1 includes functionality that maintains a reference count for each feature based on how many features that still need to be extracted are going to need it -- speaker normalization parameters may be required by many requested features.  This allows for tidier memory management, which should, in turn, allow AuToBI to operate on more material.

3) Reduced storage for acoustic contours.

In version 1.0 pitch and intensity contours were stored as lists of time-value pairs -- a storage class containing 2 doubles.  Assuming 10ms samples, and 16bytes per sample, this is about 1600bytes per second.  Not unacceptably inefficient, but definitely could be improved.  The other approach would be to only store values, and let the time of each point be specified by a start time (t0) and step size (dt).  This allows storage with 8bytes per sample plus 16bytes for the parameters.  The problem with this approach is that pitch points are invalid when there is no periodic material detected.  The time-value pair approach handled this simply and easily.  The new solution uses an array of one-bit booleans for each sample in the contour, describing whether it was a 'valid' point or not.  If the rate of periodic to aperiodic material is  less than 32:1, the new approach will reduce the memory requirements.  (As I'm writing this, I realize that this ratio could be explicitly tested during pitch extraction, selecting the most efficient storage solution at runtime.  Keep an eye out in a new release.)

The changes are mostly inside baseball kind of things, but possibly useful for AuToBI users who get their hands dirty in the code -- whoever you are.   For everyone else, the most obvious changes you'll notice is that version 1.0 models don't work any more, and a speedup of ~6%.

Personal Paper Writing Month - Recap

Well, no one wanted to join with me for Paper Writing Month, so I can only report on my own progress for November.

I got one full draft written, and the experiments for two others are more or less done running.

I can point out a number of factors that kept me from being more productive, none of which make me disappointed in myself. In all say this was a good exercise, and one I'll do again.  Maybe next time, I can find a buddy or two to join with me on it.

Now that I've written four (now five) sentences including a first-person personal pronoun, here's some more general thoughts about research.

Alex and Aki at Ideas in Food have a blog post about about Creativity in the Kitchen.  They loosely break this down into Inspiration, Flexibility, Motivation, Adaptation and Refinement.  Both these top-level categories and the specifics they address apply almost as well to creativity in research.  So check it out and cross-pollenate a little.

Cross-validation with one model

This is essentially a repost of Rob J Hyndman's blog post on the relevance of cross-validation for statisticians.


Within this very nice piece, Rob drops this bomb of mathematical knowledge:

It is not necessary to actually fit  separate models when computing the CV statistic for linear models.

Say what?


Here is a broader excerpt and the method itself (after the jump). 

Semantically Related Term Challenge

Joseph Turian over at MetaOptimize.com has posted a fun NLP challenge.

The task is to identify semantically related words from a shared corpus.

So you're thinking, sure, no problem.  I'll look for common concurrences.  Maybe I'll start with some seed pairs and do some bootstrapping.   Or you do LSA, if you're into that sort of thing.

But here's the rub, there are a few million documents, so you've got to get clever if you're going to use LSA (cause that would require SVD of an impossibly large and sparse matrix).

As if that weren't challenging enough, these "documents" are only a word or two long, so the concurrences you find are going to be pretty sparse.

So, that's it.  Have at it.

National Novel Writing Month

November is National Novel Writing Month. In past years, I've known two or three people who have set out to write a complete novel within the month.  To all of those writers who push out 100,000 words in a month, you have a huge gold star in my book.

Now, I don't quite have the motivation, creativity or time to try to dig a novel out of my head, but I'm going to put a spin on it.  This November will be Personal Paper Writing Month.

If anyone out there reads this, and wants to join me in the effort, I'll post semi-regular updates about our progress.  If I'm all alone out in this...well, so be it. You can still keep tabs on how it's going here though.