How Google understands language like a 10-year-old

http://www.sfgate.com/cgi-bin/article.cgi?f=/c/a/2010/10/18/BUJ61FTF9I.DTL

by gibsonf1 • 16 years ago

43 36 16 years ago

cryptoz2• 16 years ago

I remember laughing at people (in the late '90s) who tried to search the Internet with English-language queries: how do i cook pancakes without butter vs pancakes +"no butter"

Anyway, these days I'd obviously be wrong. I'm so impressed with the strides Google has taken to NLP, and I am fully expecting them to beat everyone to Strong AI. And why not? They know that the better they are, the better their advertising revenue will be. And they know that once they get there, even if ads are no longer profitable having the world's only AI will be incomprehensibly popular.

My one problem with this article is the last line:

"They're still not approaching the conversations you'd have as a teenager."

Google hasn't yet approached "the conversations" you'd have with a 5 year old. While Google may understand a 5-year old's conversation, it certainly couldn't participate it in and reply back to the kid.

donaq• 16 years ago

While Google may understand a 5-year old's conversation, it certainly couldn't participate it in and reply back to the kid

I would argue that it sort of does. Only instead of a normal kid, it's a mute kid that can only reply to you by passing you back documents it thinks you're asking for.

metageek4• 16 years ago

A 5-year-old librarian.

nostrademons2• 16 years ago

It can actually do simple facts now:

http://www.google.com/search?q=what+is+the+height+of+the+emp...

http://www.google.com/search?q=what+is+the+boiling+point+of+...

DisposaBoy• 16 years ago

> I remember laughing at people (in the late '90s) who tried to search the Internet with English-language queries: how do i cook pancakes without butter vs pancakes +"no butter"

Are you sure it's only the technological advance that's responsible for that? I've always written search terms like that because I figured the search engine isn't some ai that's answering my question. Instead it's a program searching a database of sorts and by searching for what I think other might have searched for I'm able to get similar results.

user244• 16 years ago

Google probably use a tweaked version of the Viterbi Algorithm ( http://en.wikipedia.org/wiki/Viterbi_algorithm ) to perform POS tagging. It's really not that hard if you have a tagged corpus.

People always seem to look at google as though they're doing some special secret magic, but in fact they're really just implementing fairly well-known CS algorithms. They just do it exceptionally well.

plq• 16 years ago

i don't think it's the fact that they are good at implementing algorithms. they're rather good at running those algorithms at exceptionally high scale. (once implemented, viterbi decoding is viterbi decoding, after all)

robryan3• 16 years ago

It's the scale of data available for training to, there is a Google Research paper call 'The Unreasonable Effectiveness of Data' talking about how even in the noisy medium that is the internet there is a lot to be gained from that level of data.

Also a paper from someone at Google on brute force paraphrase acquisition using billions of sentences combined with some relatively simple rules.

user244• 16 years ago

"good at implementing" would include building for scale, wouldn't it?

willcannings• 16 years ago

I think it's better to say that they do it exceptionally well with scale. Most algorithms are conceptually simple (once you understand them), but to make them efficient on the sort of scale Google does is sometimes hard.

That said, I don't think tagging for them would be very simple like you say. For a start they're dealing with multiple languages, probably many languages without any human annotated training corpora. Even for the languages with training data, web pages are difficult to tag & parse because they often contain very 'slack' grammar and domain specific/slang words. The standard English training corpus is the Penn Treebank (Wall Street Journal text), can you imagine trying to read and understand youtube comments if all you'd ever read was the WSJ? Even tagging search queries would be difficult because they're not even sentence fragments you could use viterbi with, they're often just words strung together without any grammar construct at all so you can't rely on the tag order you know from your corpus to help you tag a query.

So I'm very impressed that they're doing any tagging at all, on the scale they're doing it at, and with presumably decent enough results for it to be useful.

syllogism3• 16 years ago

I'm skeptical of that. So far things like POS tagging have not demonstrated any benefit in academic information retrieval results, to my knowledge. Granted this is an "absence of evidence" argument, and maybe that shouldn't be taken too seriously. Academic IR is a funny business, because nobody who wants to change the world or is deeply intellectually curious goes into it. They go work for Google/Yahoo/MS, who can tell them in a day all the things they'd discover ten years for now.

But still, all the obvious ways to use POS tagging for IR have been tried, and don't work. POS is only just marginally useful in machine translation at the moment!

This isn't that surprising when you think about it. What POS tags provide is a small clue about grammatical structure. So you're either setting off down that path and trying to understand a sentence as a tree, or you're going to understand a sentence as a sequence of words. Syntax is hard, and most word-word dependencies are between adjacent words.

There's a local maximum at "just use the words", and POS tags don't take you far enough to get past it for many tasks.

user244• 16 years ago

who says they're using POS tagging to perform the IR? I've only ever seen it used as a query refinement tool.

I agree, the bag of words / vector space model approach is (from what I've read) hard to beat, especially for a one-size-fits-all tool like google where you can assume nothing about the domain. (Unless they're switching approaches depending on the domain, which would be fascinating)

robryan3• 16 years ago

I've dabbled a little bit in POS for my thesis, I'm assuming that statistical Markov Model type methods are outpreforming rule based methods in the state of the art now?

Experimented with the Brill POS tagger, which I think is a little old now.

user244• 16 years ago

> statistical Markov Model type methods are outperforming rule based methods

I can't speak for the state-of-the-art, but that's certainly what I was taught last year. I studied both computational linguistics and IR -two very different approaches to the same problem. IR seemed to be getting much further in terms of real-world results than linguistic approaches. Although linguistic approaches may seem to offer greater potential.

jorleif2• 16 years ago

It's a bit strange to compare Google's language understanding to that of a human, since Google does not really understand language, as much as is able to return documents that are about the same thing as the person writing a query intends. Surely, a two-year old understands negation just fine, while Google does not.

Google's understanding of language is similar to that of a savant who has been imprisoned since birth and has been tied to a bench in front of a screen showing texts of the web. He can't read in the sense that he could pronounce words, but he recognizes familiar patterns of symbols. He does not know what "pancakes" are, but he knows that the word is often seen with the word "butter". It's amazing how much can be done in this way, but it is quite different from how humans understand.

tkahn6• 16 years ago

As it relates to the Turing test, this is called the Chinese Room example/argument.

http://en.wikipedia.org/wiki/Chinese_room

JabavuAdams• 16 years ago

> Surely, a two-year old understands negation just fine, while Google does not

Nope. As I read the article, I thought "Cool! it has trouble with negation, just like my 2 year old." A few months ago, it was obvious that if I said "Don't do X", she'd just match on "X", and do the thing. E.g. "Don't poke your eyes" => pokes eyes.

She's starting to get the hang of it now, but I can see how confusing it is for her.

EDIT>

Also, babies can understand a lot before they're able to compose language. E.g. "bring me your shoes" ... brings shoes. "Give that to Mommy." ... gives thing to Mom.

It's all about the FedEx quests, initially.

metageek4• 16 years ago

Also, babies can understand a lot before they're able to compose language.

My son told his first joke before he could form sentences. He was about 10 months old; I was getting him dressed, lying on the changing table. "OK, give me your hand." He lifted up one hand so I could put it into the sleeve. "And now your other hand." He got this sly grin and lifted his foot.

moxiemk1• 16 years ago

>> Google does not really understand language

I used to believe, like you do, that the ability to parse and make decisions based on input was not the same thing as understanding.

Then, I wrote a chess bot for a CS lab. The thing plays better than me, better than it's peers. My partner, who was good at chess (or at least very literate in it) could identify what strategies it was going for. We had a visualization of what moves it was considering, and you could see that it was essentially playing chess by swinging a baseball bat around and seeing what looked nice.

Does the chessbot "understand" chess? It sure seems like it. We like to think humans are special, and have some kind of unique understanding that computers can't, but I think it's only us lying to ourselves.

robryan3• 16 years ago

In a way, when a chess master thinks about a position, they can see many many moves ahead, in an innate feeling kind of way about what is a good and bad position. I think you could say that a human is better at aggressive pruning using better common sense whereas a computer can be just as good, it has to examine the billion or more positions though.

brosephius• 16 years ago

I dunno, for me "understanding" something implies an ability to reason about your reasoning. a rule-based AI can't do that, and even if interesting patterns emerge, it's still deterministic.

jorleif2• 16 years ago

Nice point, but that was not what I was getting at. The chess bot can see the whole chess field and "knows" how the pieces moves. The difference with google, is that google does not see the meanings of the words (or the entities that the words refer to), just the words. I don't mean to say that humans are special when it comes to language, just that humans have a lot of information (world knowledge) about words that google cannot pick up just by looking at the words themselves. If we manage to capture that information, then I think a computer can also understand language.

jakevoytko• 16 years ago

I found this article wanting. It seems like they took an official Google Blog post from January [0] and stripped out all of the interesting information.

I have a more specific question about Google Search that I'd like to see answered. To what extent do they model specific languages, versus training classifiers? Are they really grokking sentences or sentence fragments, or do they have enough training data to fake it, like Bill Gates in "Petals Around the Rose" [1]?

[0] http://googleblog.blogspot.com/2010/01/helping-computers-und...

[1] http://www.borrett.id.au/computing/petals-bg.htm

syllogism3• 16 years ago

Yeah, it's really a jumble of ideas. I'm a postdoc doing research on syntactic parsing, and I'm very sure that Google doesn't currently use a syntactic parser. Parsers are currently either too inefficient or too inaccurate to use at web scale --- even for Google.

The problem is that natural languages are at least context-free, and no algorithm exists (can exist?) to parse context-free languages in less than polynomial time, with respect to the length of the sentence. You can approximate by parsing with probabilistic finite-state machines, but they get led down blind alleys and can't backtrack, so they're inaccurate. Let me know if you'd like me to elaborate on this with examples (or you can Wiki "garden path sentence" and probably imagine the problem).

I'm also sure they're not doing supervised word sense disambiguation. That's in a poor state too, and imho isn't even a good idea. The whole concept of having someone list out the "senses" of a word is misguided, because it's totally unclear how fine-grained you should be. And then you need at least a couple of hundred labelled examples for every word...

Most of the examples they give are best explained by dimensionality reduction techniques, which have been popular in information retrieval for some time. Google have undoubtedly invented some secret sauce, but they've also just got orders of magnitude more data and processing power.

nostrademons2• 16 years ago

Don't you mean context-sensitive? A context-free grammar can be parsed pretty easily with a stack machine, and most programming languages are context-free. C and C++ are even context-sensitive, but the context-sensitivity is mostly limited to typedefs, and so doesn't tend to blow up parse times beyond reason. (Well, many would consider C++'s compile time to be unreasonable, but this is largely because of #include, which is another issue.)

JeffJenkins• 16 years ago

Petals Around the Rose was really interesting. I couldn't figure it out until I read the line from Bill Gate's program, at which point I got it almost instantly. I don't really understand why since I already knew the name of the game, and that the name was relevant.

I do have a long history of over-analysing simple mathematical games, though.

jcroberts• 16 years ago

The article wasn't very useful compared to blog posts by google itself, but the discussions on what google can "understand" always reminds me of this:

http://www.fun-images.com/thumbs/25-my-fucking-keysbig.jpg

metageek4• 16 years ago

The search engine has also begun to understand which words are synonyms for others.

I was delighted the day I noticed it knew that "regexp" and "regex" were synonyms for "regular expression".

mickdarling• 16 years ago

So in the 15 years they started using statistical methods for understanding language, googles ability to understand language is at about an 8 year olds level. So it is learning about half as fast as a human child. Not bad and an excellent opportunity to predict it's growth rate for the future.

If this is a linear learning curve, in another 15 years it should just start to be able to 'understand' the nuances of Shakespeare and Ulysses among others.

How Google understands language like a 10-year-old

Related Stories