4 ms·

Google probably use a tweaked version of the Viterbi Algorithm ( http://en.wikipedia.org/wiki/Viterbi_algorithm http://en.wikipedia.org/wiki/Viterbi_algorithm )

by user24 16y ago

Google probably use a tweaked version of the Viterbi Algorithm ( http://en.wikipedia.org/wiki/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 16y 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)
- robryan 16y 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.
  - GFischer 16y ago
    Thanks for pointing out that paper ('The Unreasonable Effectiveness of Data'): http://www.scribd.com/doc/13863110/The-Unreasonable-Effectiveness-of-Data http://www.scribd.com/doc/13863110/The-Unreasonable-Effectiv...
- user24 16y ago
  "good at implementing" would include building for scale, wouldn't it?
willcannings 16y 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.
syllogism 16y 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.
- user24 16y 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)
  - syllogism 16y ago
    As I'd define things, if you're using something for query refinement, then it's part of your IR system. How would you use POS tagging for query refinement though? You can hardly expect to POS tag the user's query, since it's unlikely to be a sentence. I suspect we have some miscommunication here.
robryan 16y 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.
- user24 16y 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.

by user24 16y ago

plq 16y 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)

robryan 16y 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.
- GFischer 16y ago
  Thanks for pointing out that paper ('The Unreasonable Effectiveness of Data'): http://www.scribd.com/doc/13863110/The-Unreasonable-Effectiveness-of-Data http://www.scribd.com/doc/13863110/The-Unreasonable-Effectiv...
user24 16y ago
"good at implementing" would include building for scale, wouldn't it?

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

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

user24 16y 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)
- syllogism 16y ago
  As I'd define things, if you're using something for query refinement, then it's part of your IR system. How would you use POS tagging for query refinement though? You can hardly expect to POS tag the user's query, since it's unlikely to be a sentence. I suspect we have some miscommunication here.

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

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