Today I'm posting about keyword extraction with Lexical Chains - it's something that I first looked into during college but which has resurfaced recently and I used it for a couple of projects. The original paper I read is a couple of years old, it's called "Efficient text summarization using lexical chains" and was written by Gregory Silber and Kathleen McCoy in 2000. A link to the text can be found here.
You may wonder why you would want to generate keywords of text in first place. Some sample use cases are listed below:
* generate tag-clouds (for richer UI experience)
* relate content to keyword-based advertising
* identify key-search terms for indexing
Traditionally, people use Term Frequence / Inverse Document Frequency (TF/IDF) for this task, which works fairly well for many applications. TF/IDF gives a weight for each term within a given document based on the frequency of the term relative to the document and to the number of documents globally that contain the word (e.g. how often does the term "dog" appear in an article X and how many articles contain the word dog). However, this isn't really the best solution (arguably, LCs aren't the best solution either), my reasoning for that is, often you'll have noisy data - different documents might have a different vocabulary (e.g. people using slang) - so you might end up with really useless data. Also, if you have very expressive authors of the textual content, they'll rarely use the same word twice but will often use a myriad of synonyms. That isn't really picked up by TF/IDF and this is really the strength of Lexical Chains.
Lexical chains are chains of words that share some relationship and co-occur, mostly limited to a document or paragraph. Let's say for example you have the following text:
"Today we drove our new car, a convertible to the lake. We just added another vehicle to the collection at our vacation home - we bought a new boat!". (random rich person)
The nouns of this text fragment are "car", "convertible", "lake", "vehicle", "collection", "vacation_home", "boat". My mental parser has identified that this text is about vehicles, but how can this be extracted algorithmically? The answer is with a taxonomy. Wordnet is one such example, it organizes words or concepts according to their relationship with one another. The included graphic shows what the 'type-of' relationship in wordnet looks like. You can see that Vehicle has two children, "car" & "boat" (siblings) and "car" has a child (hyponym) "convertible". This is the basis for Lexical Chains.
Lexical Chains are usually constructed of nouns and possibly of verbs - though let's focus on nouns. This means, you'll need to use some sort of Part-of-Speech tagger to determine the likelihood of a given word being a noun, which is computationally expensive in comparison with TF/IDF. The part of speech tagger will assign each word a tag, (often Penn Treebank tags are used,
http://www.cis.upenn.edu/~treebank/), we'll disregard everything that's not a noun.
Here is the algorithm in pseudo-code:
Allocate a hashtable HT
For each noun n in document D get all P (Synonyms, Hypernyms, Hyponyms, Sibling) of n from Wornet
found = false
For each p in P
If HT contains LC(p)
append n to LC(p) and increment LC(p).score by (1 if rel(n,p) == synonym, 0.7 if rel(n,p) hypernym or hyponym, 0.5 if rel(n,p) sibling)
found = true
If ! found
create new LC(n) and set LC(n).score = 1
For HT compute MEAN and STDEV based on each LC(x).score
return all LC in HT where LC.score > (MEAN + X * STDEV)
As you can see, once you have setup a Taxonomy, e.g. Wordnet and the preprocessing setup, this algorithm is very simple to implement. I've done it with Wordnet but i've done experiments using Wikipedia as a Taxonomy and using a simplified scoring that was just based on a radial search (since you don't have the nature of the relationship in Wikipedia).
In a previous startup I worked in (HeadCase), we used a similar approach to generate tag-clouds. In my opinion, it works best in conversational text such as IM, comment-chains on websites, etc.
