4 ms·

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

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-understand-language.html http://googleblog.blogspot.com/2010/01/helping-computers-und... [1] http://www.borrett.id.au/computing/petals-bg.htm http://www.borrett.id.au/computing/petals-bg.htm

syllogism 16y 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.
- nostrademons 16y 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.)
  - nvoorhies 16y ago
    Most sane programming language syntaxes are confined to a subset of CFGs, usually LALR, which is nice and easy to generate fast parsers for. To parse any CFG you have to fall back to strategies like CKY that have worst case behaviors that are way worse than linear, like CKY or GLR or what have you. But yeah, context sensitive stuff can be way worse. Unless new evidence has surfaced in the years since I finished a degree in linguistics, there's only a couple of pieces of evidence for language constructions in natural languages that can't be generated by a context free grammar, like a Adv1Adv2Adv3Adj1Adj2Adj3 construction in Zürich dialectical German (where Adv = adverb and Adj=adjective, and numbers represent which adverb modifies which adjective).
JeffJenkins 16y 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.

syllogism 16y 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.

nostrademons 16y 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.)
- nvoorhies 16y ago
  Most sane programming language syntaxes are confined to a subset of CFGs, usually LALR, which is nice and easy to generate fast parsers for. To parse any CFG you have to fall back to strategies like CKY that have worst case behaviors that are way worse than linear, like CKY or GLR or what have you. But yeah, context sensitive stuff can be way worse. Unless new evidence has surfaced in the years since I finished a degree in linguistics, there's only a couple of pieces of evidence for language constructions in natural languages that can't be generated by a context free grammar, like a Adv1Adv2Adv3Adj1Adj2Adj3 construction in Zürich dialectical German (where Adv = adverb and Adj=adjective, and numbers represent which adverb modifies which adjective).

JeffJenkins 16y 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.