When Close Isn’t Good Enough

Tuesday, May 31, 2011
By Sharad Goel

So close, yet so far

For a lot of engineering problems, “almost right” isn’t good enough. Remember the Mars Climate Orbiter? Traveling through space for nearly a year, and covering 700 million kilometers, the Orbiter disintegrated after entering the Martian atmosphere at an altitude just one-hundred kilometers lower than planned. That’s like a $100 million dart exploding when you miss the bullseye by less than the width of a human hair. A less dramatic — though more common — failure is the embarrassing auto-correct. After countless convenient corrections, there is inevitably a mistake that calls into question the overall utility of the system. For one contributor to this blog, that moment occurred when the intended “wild beasts” was publicly disseminated as “wild breasts” — on the bright side, that “correction” did seem to increase interest in the text.

Good AI together with good UI is substantially better than either alone:
AI + UI  >> max(AI, UI).

The stark difference in many real-world applications between 99% and 100% correct poses major challenges for fully automated approaches to problem solving. Consider for instance web search engines: amazing engineering feats, and testaments to the power of artificial intelligence. Yet despite incorporating some of the most sophisticated algorithms in computer science, Google’s “I’m feeling lucky” button is still aptly named: When the highest ranked search result is the most relevant, luck has often played a significant role. Why, then, have AI systems proven to be so useful? The answer, I believe, is that well-designed user interfaces have let humans complete the last one-percent, facilitating the conversion of an “almost right solution” — but one that is ultimately unusable on its own — into an answer that is actually useful. In the case of web search, simply allowing users to easily parse and select from ten summarized results dramatically increases the value of the AI. Good AI together with good UI is substantially better than either alone: AI + UI  >> max(AI, UI).

A few months ago, musician and Messy Matters illustrator Kelly Savage was creating orchestral parts from copies of 19th century music scores, a time-honored tradition among classical musicians wherein one physically cuts apart each line of music (with scissors!) and then tapes together the corresponding instrument lines. In this way the violinists, for example, need only look at their own music, instead of that of all the players. (In case you’re wondering, pre-made parts are generally not available for lesser-known compositions, or when they are, often cost more than the typical musician’s value for time). Creating parts is a tedious, repetitive, and unfulfilling task — a situation that begs for automation. The problem, however, is that there is very little tolerance for mistakes. Optical music recognition, even when it correctly identifies and digitizes 90% of the notes, still leaves insidious mistakes in its wake that must be manually corrected, erasing much of the time-saving benefit. Ending Brahm’s Violin Concerto in D Major on a C is really not acceptable. Like in the examples above, AI is tantalizingly close to solving the problem but fails to deliver that last, critical few percent.

To address this part-making predicament, Kelly and I built Partifi, a tool that solves 90% of the problem algorithmically, but which also makes it easy for users to complete that last 10% themselves. Given a score, AI[1] is first used to identify line breaks. Users can then reposition, add, or delete the computer-generated lines via a simple UI. Once the segments have been adjusted, users start tagging each line with the appropriate part name (e.g., “violin”, “viola”, etc.); here AI is used to infer the tagging pattern to label the remaining lines. Ultimately, this straightforward combination of AI and UI reduces the average time to create parts from hours to minutes.

partifi.org

The holy grail of artificial intelligence is a fully independent computer system as good as — or even better than — humans at general problem solving. On that road from Watson to singularity, I believe intelligent user interfaces will play an increasingly important role, softening the blow of AI errors and turning “close” into “correct”.

N.B. Partifi is freely available at partifi.org. It’s still in the early stages of development, so your feedback would be much appreciated. Thanks to Tami Morse for helping us work out the kinks.

Bonus Puzzle

Two players sit down at a chess table with a large pile of identical pawns. Each player alternates placing a pawn on one of the 64 squares, and the last player to place a pawn wins. Since there are an even number of squares, the second player is guaranteed victory. Not so interesting. But now suppose the players are allowed to place the pawns anywhere on the board, not just on the 64 squares. Is there a winning strategy for the first player?

Addendum

Congratulations to Arthur Breitman for solving the puzzle. Here’s his solution:

The first player should place a pawn dead in the center. After that, place a pawn which is center-symmetric with the opponent’s last move. It’s always possible because the board remains symmetric at all times, and the center-symmetric position can’t overlap because the disc in the center has been taken already.

Footnotes

[1] Roughly, we compute the darkness of each row of pixels, breaking at rows that are local minima. It has been quipped that artificial intelligence concerns problems that we do not yet know how to solve properly by computer. Even under a more expansive definition, however, the simplicity of our approach admittedly pushes the boundary of what legitimately passes for AI.

Illustration by Kelly Savage

Tags: , ,

  • http://www.cs.berkeley.edu/~kevin/ Kevin Canini

    Regarding the bonus puzzle, I heard this one many years ago, but using a big round table instead of a chessboard, and quarters instead of pawns. The solution I was given requires the ability to make extremely precise measurements of the table and the coins.

  • http://dreev.es dreeves

    (I just temporarily censored a comment that was too much of a spoiler for the puzzle. Most of our puzzles here are variants of things we’ve heard before. We just try to make them ungooglable (and add twists). So no spoiling it by mapping it back to a potentially googlable form!)

    [I uncensored it now that we got a solution.]

  • Arthur B.

    The first player should place a pawn dead in the center, after that, place a pawn which is center symmetric with the opponent’s last move, it’s always possible because the board remains symmetric at all time, and the center symmetric position can’t overlap because the disc in the center has been taken already.

  • http://www.levreyzin.com Lev Reyzin

    Another puzzle is why the strategy above doesn’t work for Go.

  • Pingback: AI Where A Stands for Almost « Alicia Morga's Blog

  • Pingback: To Break From Routine Is Human | Beeminder Blog