6 ms·

Latent Dirichlet Allocation Surprisingly Well Correlated w/ Google Rankings

58 points by randfish 16y ago

nkurz 16y ago
This is a good layman's introduction to modern search techniques, but to someone not in the SEO field it feels like a very strange inversion of priorities. To me, like most people, the surprise is how effective techniques like LDA[1] can be in characterizing a document, but the 'surprise' in the article is that LDA correlates to Google search order better than a more simplistic model. To a technologically savvy but naive outsider, this might seem obvious: shouldn't pages that rank highly in Google have strong topic-based correlation to pages that the user wants to see? But from the SEO perspective, I guess the conclusion would be that your page is more likely to be ranked highly if it includes all the trappings of other high ranked pages, with, you know, like synonyms and stuff. At a certain point, one has to start thinking, wouldn't it be simpler to make a page that people actually want to find? Are there good examples of actually useful pages that Google doesn't do a good job of ranking? I occasionally find myself lately getting frustrated with Google about ignoring my rarer search terms, but generally I find the good pages are at the top if they exist at all. [1] LDA is Latent Dirichlet Allocation, which is very similar to Latent Semantic Analysis, which in turn is very similar to Principle Component Analysis and Singular Value Decomposition. So it's possible you've already heard of the concept, but coming from another angle in another field.
- nl 16y ago
  I though it was kind of odd they did LDA rather than something more broadly used (eg LSA). But I've never really looked at LDA, and Wikipedia says: Compared to standard latent semantic analysis which stems from linear algebra and downsizes the occurrence tables (usually via a singular value decomposition), probabilistic latent semantic analysis is based on a mixture decomposition derived from a latent class model. This results in a more principled approach which has a solid foundation in statistics. so maybe they made the right choice. (Not that I see what "solid foundation in statistics" really means in this context)
  - equark 16y ago
    It means there is a likelihood function.
  - cdavid 16y ago
    LSA is relatively similar in some abstract sense to the published pagerank algorithm. LDA is more powerful, in the sense that it can account for more complex relationships (but may be less accurate with large number of data - I have really no idea how those would scale and compare at google-like size).
    - nl 16y ago
      Can you explain this some more? My understanding of LDA is that it gives you document scores against queries based on the topics extracted using the LDA algorithm on the text in the page. Pagerank, on the other hand scores based on external pointers (ie, references) but doesn't have anything to do with the text on the page.
      - noelwelsh 16y ago
        It's the abstract sense that is important. Pagerank is a dimensionality reduction technique. It finds the first eigenvector of the transition matrix. Eigenvectors = PCA. LSI is basically PCA, but applied to the document-term matrix. LDA is a dimensionality reduction technique that makes use of more information.
        nl 16y ago
        Oh, I see. I thought you were talking about some functional similarities, not the mathematical similarities.
  - yread 16y ago
    For some applications Dirichlet mixtures are even better. I used this tool, which I can recommend, for deriving the parameters of the mixtures http://chasen.org/~daiti-m/dist/dm/ http://chasen.org/~daiti-m/dist/dm/
- nodata 16y ago
  > Are there good examples of actually useful pages that Google doesn't do a good job of ranking? Yes. Reviews by actual people. A long, long time ago (last year I think) I used to use google blogsearch to get at the "other side" of hardware reviews: what people who are not being paid to review hardware think of a specific piece of hardware. Doesn't work any more. There's almost nothing but spam. It's hopeless.
  - nkurz 16y ago
    I agree. There are definitely cases where spam has displaced good results. Although poorly phrased, I guess I was asking a different question: apart from intentional attempts to game the system, are there cases where pages one wants to see are consistently ranked after pages one does not? Which is to say, are there improvements that could be made to Google's ranking algorithms beyond making it more spam resistant?
nl 16y ago
This is news? Seriously???? They have found a correlation between a set of words related to a topic you are searching for and how highly a search engine ranks that page? Well duh! Did anyone really think search engines did a keyword search and then applied Pagerank/HITS (http://en.wikipedia.org/wiki/HITS_algorithm http://en.wikipedia.org/wiki/HITS_algorithm) or whatever? That would give dreadful results. If you really want to understand this, I recommend Building a Vector Space Search Engine in Perl http://perl.about.com/b/2007/05/24/building-a-vector-space-search-engine-in-perl.htm http://perl.about.com/b/2007/05/24/building-a-vector-space-s... I build the vector space classifier in http://classifier4j.sf.net http://classifier4j.sf.net based almost entirely on that article, even though I don't know Perl. It's very readable, and gives you a great understanding.
- iamwil 16y ago
  http://www.perl.com/pub/2003/02/19/engine.html http://www.perl.com/pub/2003/02/19/engine.html Actual link
- will_critchlow 16y ago
  The news isn't that there is a correlation but that there is such a strong correlation. There are a bunch of specific techniques Google could be using and it looks likely that this is close to what they actually use. They also use a lot of other ranking factors beyond just the words on the page so seeing such a high correlation from a "bag of words" model is pretty interesting (to me at least).
  - nl 16y ago
    (Thanks for the reply) Did you test non-LDA methods? Because to me it looked like a correlation between a set of related words and ranking for a topic related to those words. Without testing non LDA methods I can't see what you've proved.
    - will_critchlow 16y ago
      Yes. The chart in the post shows how low the correlation is for tf-idf. I believe the original also showed similarly poor results for LSI etc.
moultano 16y ago
All good ranking functions are pretty correlated. There are many ways for a ranking to be bad, and few ways for it to be good.
mark_l_watson 16y ago
I sometimes use LDA (using Hadoop and Mahout) and it is not an inexpensive calculation for large document sets). I wonder what the costs are for using this large scale.
madridorama 16y ago
I'm sorry but this is overthinking something that is relatively simple to understand

58 points by randfish 16y ago

nkurz 16y ago

This is a good layman's introduction to modern search techniques, but to someone not in the SEO field it feels like a very strange inversion of priorities. To me, like most people, the surprise is how effective techniques like LDA[1] can be in characterizing a document, but the 'surprise' in the article is that LDA correlates to Google search order better than a more simplistic model. To a technologically savvy but naive outsider, this might seem obvious: shouldn't pages that rank highly in Google have strong topic-based correlation to pages that the user wants to see? But from the SEO perspective, I guess the conclusion would be that your page is more likely to be ranked highly if it includes all the trappings of other high ranked pages, with, you know, like synonyms and stuff. At a certain point, one has to start thinking, wouldn't it be simpler to make a page that people actually want to find? Are there good examples of actually useful pages that Google doesn't do a good job of ranking? I occasionally find myself lately getting frustrated with Google about ignoring my rarer search terms, but generally I find the good pages are at the top if they exist at all. [1] LDA is Latent Dirichlet Allocation, which is very similar to Latent Semantic Analysis, which in turn is very similar to Principle Component Analysis and Singular Value Decomposition. So it's possible you've already heard of the concept, but coming from another angle in another field.

nl 16y ago
I though it was kind of odd they did LDA rather than something more broadly used (eg LSA). But I've never really looked at LDA, and Wikipedia says: Compared to standard latent semantic analysis which stems from linear algebra and downsizes the occurrence tables (usually via a singular value decomposition), probabilistic latent semantic analysis is based on a mixture decomposition derived from a latent class model. This results in a more principled approach which has a solid foundation in statistics. so maybe they made the right choice. (Not that I see what "solid foundation in statistics" really means in this context)
- equark 16y ago
  It means there is a likelihood function.
- cdavid 16y ago
  LSA is relatively similar in some abstract sense to the published pagerank algorithm. LDA is more powerful, in the sense that it can account for more complex relationships (but may be less accurate with large number of data - I have really no idea how those would scale and compare at google-like size).
  - nl 16y ago
    Can you explain this some more? My understanding of LDA is that it gives you document scores against queries based on the topics extracted using the LDA algorithm on the text in the page. Pagerank, on the other hand scores based on external pointers (ie, references) but doesn't have anything to do with the text on the page.
    - noelwelsh 16y ago
      It's the abstract sense that is important. Pagerank is a dimensionality reduction technique. It finds the first eigenvector of the transition matrix. Eigenvectors = PCA. LSI is basically PCA, but applied to the document-term matrix. LDA is a dimensionality reduction technique that makes use of more information.
      - nl 16y ago
        Oh, I see. I thought you were talking about some functional similarities, not the mathematical similarities.
- yread 16y ago
  For some applications Dirichlet mixtures are even better. I used this tool, which I can recommend, for deriving the parameters of the mixtures http://chasen.org/~daiti-m/dist/dm/ http://chasen.org/~daiti-m/dist/dm/
nodata 16y ago
> Are there good examples of actually useful pages that Google doesn't do a good job of ranking? Yes. Reviews by actual people. A long, long time ago (last year I think) I used to use google blogsearch to get at the "other side" of hardware reviews: what people who are not being paid to review hardware think of a specific piece of hardware. Doesn't work any more. There's almost nothing but spam. It's hopeless.
- nkurz 16y ago
  I agree. There are definitely cases where spam has displaced good results. Although poorly phrased, I guess I was asking a different question: apart from intentional attempts to game the system, are there cases where pages one wants to see are consistently ranked after pages one does not? Which is to say, are there improvements that could be made to Google's ranking algorithms beyond making it more spam resistant?

nl 16y ago

This is news? Seriously???? They have found a correlation between a set of words related to a topic you are searching for and how highly a search engine ranks that page? Well duh! Did anyone really think search engines did a keyword search and then applied Pagerank/HITS (http://en.wikipedia.org/wiki/HITS_algorithm http://en.wikipedia.org/wiki/HITS_algorithm) or whatever? That would give dreadful results. If you really want to understand this, I recommend Building a Vector Space Search Engine in Perl http://perl.about.com/b/2007/05/24/building-a-vector-space-search-engine-in-perl.htm http://perl.about.com/b/2007/05/24/building-a-vector-space-s... I build the vector space classifier in http://classifier4j.sf.net http://classifier4j.sf.net based almost entirely on that article, even though I don't know Perl. It's very readable, and gives you a great understanding.

iamwil 16y ago
http://www.perl.com/pub/2003/02/19/engine.html http://www.perl.com/pub/2003/02/19/engine.html Actual link
will_critchlow 16y ago
The news isn't that there is a correlation but that there is such a strong correlation. There are a bunch of specific techniques Google could be using and it looks likely that this is close to what they actually use. They also use a lot of other ranking factors beyond just the words on the page so seeing such a high correlation from a "bag of words" model is pretty interesting (to me at least).
- nl 16y ago
  (Thanks for the reply) Did you test non-LDA methods? Because to me it looked like a correlation between a set of related words and ranking for a topic related to those words. Without testing non LDA methods I can't see what you've proved.
  - will_critchlow 16y ago
    Yes. The chart in the post shows how low the correlation is for tf-idf. I believe the original also showed similarly poor results for LSI etc.

moultano 16y ago

All good ranking functions are pretty correlated. There are many ways for a ranking to be bad, and few ways for it to be good.

mark_l_watson 16y ago

I sometimes use LDA (using Hadoop and Mahout) and it is not an inexpensive calculation for large document sets). I wonder what the costs are for using this large scale.

madridorama 16y ago

I'm sorry but this is overthinking something that is relatively simple to understand