9 ms·

Armchair analysis of his algorithm after watching his TED talk: a version of LSA that uses PageRank instead of a straight SVD to calculate rankings. LSA[1] has

Armchair analysis of his algorithm after watching his TED talk: a version of LSA that uses PageRank instead of a straight SVD to calculate rankings. LSA[1] has been around since the 80s and is used in many applications from GRE testing to Apple's junk mail filtering[2]. It's used a lot since the patent expired, it's relatively good and can be computed quickly. Of course, a lot of text-retrieval research has happened in the past few decades, one of my favorites being LDA[3] which relies on a much more sound statistical basis than finding lower-dimensional representations of term-document vectors. Unfortunately LDA's model is not directly computable and answers must be determined via Monte-Carlo methods. As for 'indepdendence,' his terminology gets a little confused here. At first I thought he was talking about the 'bag-of-words' assumption that most large-scale language models have. These effectively ignore grammar (other than stemming) in order to efficiently determine the 'gist' of a document without its intricacies. However, his videos imply he is talking about word-sense disambiguation[4], which is certainly known about and was the crux of LSA in the first place. If he is talking about lifting the bag-of-words assumption, there has been some interesting work going on, such as [5] (disclaimer: I am a coauthor on that paper). If you're interested in this stuff, I highly recommend trying out the LSA demo server at [6] (it can get swamped sometimes so don't kill it) and David Blei's LDA implementation at [7]. The LDA-C inputs and parameters are a little obtuse when you first look at it, and I don't have my notes on how to use it at the moment but if you play around with it it should make sense. This kid is crazy smart, and I hope he gets exposed to a lot of really cool research since he can obviously pull off a lot at a young age. Best of luck to him. [1] http://en.wikipedia.org/wiki/Latent_semantic_analysis http://en.wikipedia.org/wiki/Latent_semantic_analysis [2] http://developer.apple.com/library/mac/#samplecode/LSMSmartCategorizer/Introduction/Intro.html http://developer.apple.com/library/mac/#samplecode/LSMSmartC... [3] http://en.wikipedia.org/wiki/Latent_Dirichlet_allocation http://en.wikipedia.org/wiki/Latent_Dirichlet_allocation [4] http://en.wikipedia.org/wiki/Word-sense_disambiguation http://en.wikipedia.org/wiki/Word-sense_disambiguation [5] http://aclweb.org/anthology-new/D/D12/D12-1020.pdf http://aclweb.org/anthology-new/D/D12/D12-1020.pdf [6] http://lsa.colorado.edu/ http://lsa.colorado.edu/ [7] http://www.cs.princeton.edu/~blei/lda-c/ http://www.cs.princeton.edu/~blei/lda-c/

mikkom 14y ago
LSA patent has expired? Thanks for info, I didn't know that.
bambax 14y ago
This kind of comment is what I come to HN for, so thank you. I use OpenCalais to compute keywords for texts; where does it stand vs. [6] and LSA in general?
- riffraff 14y ago
  on a related note, I've been told once that OpenCalais actually uses a rule-based system, does anyone know if that's true?
- Dn_Ab 14y ago
  At their scale I doubt they are using LSA or anything of similar complexity. My guess would be something like tf-idf coupled with any thing from naive bayes to logic programming for entity recognition. Final output would likely use some hand curated rules on how to combine the above with infromation from curated databases like dbepida. ________________ There is this thing called random projection based on the observation that in high dimensions, most direction are nearly orthogonal to each other. This is a wonderful observation because it allows us to write stupendously simple (and fast) algorithms that give good results for mathematically sound reasons. I strongly suggest anyone who is interested in LSA but wants something scalable, simpler to write and faster to look into Random Indexing.
Dn_Ab 14y ago
While all these techniques are related and LSI is a good model for what he is doing, I think his thought process is spiritually closer to PageRank. Although I don't think he merely adapted the page rank algorithm. Based on his emphasis on markov chains and his diagrams, I think his algorithm works by building a markov chain from word co-ocurrances. Then when the user searches, it uses the words from the highest incoming edges to keywords to disambiguate word meaning and cluster tweets. I would argue based on his justification by random walks that given enough time and study he would have ended up with LDA and not LSA.

mikkom 14y ago

LSA patent has expired? Thanks for info, I didn't know that.

bambax 14y ago

This kind of comment is what I come to HN for, so thank you. I use OpenCalais to compute keywords for texts; where does it stand vs. [6] and LSA in general?

riffraff 14y ago
on a related note, I've been told once that OpenCalais actually uses a rule-based system, does anyone know if that's true?
Dn_Ab 14y ago
At their scale I doubt they are using LSA or anything of similar complexity. My guess would be something like tf-idf coupled with any thing from naive bayes to logic programming for entity recognition. Final output would likely use some hand curated rules on how to combine the above with infromation from curated databases like dbepida. ________________ There is this thing called random projection based on the observation that in high dimensions, most direction are nearly orthogonal to each other. This is a wonderful observation because it allows us to write stupendously simple (and fast) algorithms that give good results for mathematically sound reasons. I strongly suggest anyone who is interested in LSA but wants something scalable, simpler to write and faster to look into Random Indexing.

Dn_Ab 14y ago

While all these techniques are related and LSI is a good model for what he is doing, I think his thought process is spiritually closer to PageRank. Although I don't think he merely adapted the page rank algorithm. Based on his emphasis on markov chains and his diagrams, I think his algorithm works by building a markov chain from word co-ocurrances. Then when the user searches, it uses the words from the highest incoming edges to keywords to disambiguate word meaning and cluster tweets. I would argue based on his justification by random walks that given enough time and study he would have ended up with LDA and not LSA.