Comment by wickedchicken | Hacker News Reader

Comment by wickedchicken | Hacker News Reader

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

[2] http://developer.apple.com/library/mac/#samplecode/LSMSmartC...

[3] http://en.wikipedia.org/wiki/Latent_Dirichlet_allocation

[4] http://en.wikipedia.org/wiki/Word-sense_disambiguation

[5] http://aclweb.org/anthology-new/D/D12/D12-1020.pdf

[6] http://lsa.colorado.edu/

[7] http://www.cs.princeton.edu/~blei/lda-c/

From what I have understood by watching his TED talk, the algorithm he designed seems very similar to papers published in the NLP field recently [1] [2] [3]. I find it quite elegant, and I agree that the kid is really smart.

The idea behind those algorithms is to build a graph on words, using WordNet, or a corpus such as Wikipedia. Edges are added between words which are semantically close, or which often appear in the same documents. Then, to compare two words (or two bags of words), you compute the limiting distributions of the two random walks starting at each of the words. Those random walks will more explore nodes which are close to the starting nodes, and so, similar words will have similar random walks.

[1] Hughes, T. and Ramage, D. 2007. Lexical semantic relatedness with random graph walks ( http://acl.ldc.upenn.edu/D/D07/D07-1061.pdf )

[2] Ramage, D. and Rafferty, A.N. and Manning, C.D. 2009. Random walks for text semantic similarity ( http://nlp.stanford.edu/pubs/wordwalk-textgraphs09.pdf )

[3] Yeh, E. and Ramage, D. and Manning, C.D. and Agirre, E. and Soroa, A.. 2009. WikiWalk: random walks on Wikipedia for semantic relatedness ( http://nlp.stanford.edu/pubs/wikiwalk-textgraphs09.pdf )

[Update] Added the third reference.

You are correct. My algorithm is conceptually rather similar to a number of ones recently published. The work closest to mine in the literatures is [1], by Lafferty and Zhai at CMU in 2001.

That said, my method is somewhat different than these in the way that it explicitly treats unlinked documents as distributions over a graph of words and the theoretical framework (based on a theoretical process for document generation) employed to derive it.

[1] http://www.iro.umontreal.ca/~nie/IFT6255/lafferty-zhai.pdf

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?

on a related note, I've been told once that OpenCalais actually uses a rule-based system, does anyone know if that's true?

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.

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.

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

With respect to LDA, there is a new paper on arxiv, Two SVDs Suffice: Spectral decompositions for probabilistic topic modeling and latent Dirichlet allocation [1].

[1] http://arxiv.org/abs/1204.6703

The results look really similar to what used to be google wonder wheel. You start with one word, and it would show you a graph of other related words/phrases.

Reply on news.ycombinator.com