30 ideas sort of related to NLP

Over the past year or so, as I was trying to learn more about machine learning, one related topic I haven't gotten to is natural language processing (NLP). I've also had Matthew Russell's Mining the Social Web sitting unread on my bookshelf for a while. Even though it's a bit outdated at this point with references to Google Buzz (looks like there is an updated edition available though) I think it will be good for picking up some NLP basics. It's been described as a successor to Collective Intelligence, which I thought was a fantastic book, so I'm really been looking forward to having the time to finally get through it. This post is going to be lnotes of what I learn as I learn it.

• Even though lexical diversity (unique tokens / total number of tokens) and term frequency distributions are simple, they are still important and useful to start with
• The Natural Language Toolkit (NLTK) is a popular Python module for NLP
• Microformats and HTML 5's microdata are ways of decorating markup to expose structured information
• CouchDB can be used to build up indexes on data and perform frequency analysis through MapReduce operations
• Add Lucene to enable full-text searching of CouchDB documents
• I've known Redis as a key-value store or cache, but it's also known as a data structure server because it can contain lists, sets, hashes, etc.
• When analyzing a graph (like Twitter followers), a graph database can help by providing common operations like clique detection or breadth-first search
• There are many visualization tools besides matplotlib and Graphviz available from Python like Ubigraph, Protovis, and SIMILE Timeline
• Edit distance (aka Levenshtein distance) is a measure of how many changes it would take to convert one string to another 
• n-gram similarity is a measure of common n-grams between samples
• Jaccard index measures the similarity of two sets (|A ∩  B| / |A ∪ B|)
• Calculating the distance between every pair for clustering a large n can be impossible (I think the book could have gone into more detail here and mentioned an alternative approach like what I wrote about at Locality Sensitive Hashing) but k-means clustering at O(kn) can approximate well
• Two visualizations I recognized but didn't know by name: Dorling Cartograms and dendrograms
• New (to me) visualization for trees: radial trees and sunburst visualizations
• Natural language frequency analysis follows Zipf's Law (a power law and long tail distribution) meaning a word's frequency is inversely proportional to its rank in the frequency table 
• TF-IDF is one of the fundamental information retrieval techniques for retrieving documents from a corpus (I wrote about it at tf-idf)
• A common way to find similar documents is cosine similarity where the vectors are TF-IDF weights
• Document similarities can be visualized with arc and matrix diagrams
• Much information is gained when you can look at multiple tokens at a time, like bi-grams (2-grams)
• Collocations are sequences of words that occur together often
• Contingency tables are data structures for expressing frequencies associated with the terms of a bi-gram
• Dice's coefficient, likelihood ratio, chi-square, and Student's t-score, in addition to Jaccard index, are all statistical approaches that can be used for discovering collocations
• Stemming and lemmatization
• Stop-words
• A typical NLTK NLP pipeline is:
• end of sentence (EOS) detection
• tokenization
• part-of-speech tagging
• chunking - assembling compound tokens for logical concepts
• extraction - tagging chunks as named entities
• Filtering out sentences containing frequently occurring words appearing near each other is a basic way to summarize documents
• Extracting entities from documents can address some of the shortcomings of the bag-of-words approach TF-IDF (like homographs and different capitalizations), which n-grams don't completely solve
• Use the F1 score to measure accuracy against manually tagged documents
• Facebook's Open Graph Protocol enables you to turn any web page into a social graph by injecting RDFa metadata into the page
• The semantic web, if realized through standards like RDF and OWL, would be a domain-agnostic way to enable machines to understand and use web information

Bipartite Graphs and Google Adwords

Continuing my series of posts relating to the Coursera Mining Massive Datasets class, this post summarizes the chapter on Google AdWords. I liked how the professors showed it to be related to matching in a bipartite graph--something that I learned about in a university graph theory class but without such a practical context as web advertising. I think that too often happens, at least in my experience. I've taken a lot of math classes (and done well in them), but I still don't feel like I had much practice applying what I learned to real-world problems.

To be clear, AdWords is for advertisers and AdSense is for website owners. Google provides an explanation in The difference between AdWords and AdSense. Today I'm focusing on how AdWords works.

The "adwords" model matches web searches with advertisements. Advertisers bid to be shown in response to certain search queries. If a user clicks on one of the ads shown to them then the advertiser will pay. Of course, the most relevant ads are clicked more often than less attractive ads, so the challenge is displaying the ads with the highest bids that are most likely to be clicked, while staying within an advertisers budget. This is a problem that traditional newspapers and magazines don't really have. They can only target specific niches of people (like people who buy Golf Digest), but web advertisers can target individuals (like people searching for a specific brand of golf clubs).

Google knows the click-through rate, or the percentage of the time an ad is clicked when it is displayed. It knows how much of an advertiser's budget has been spent. Google also knows what people have searched for in the past, but it doesn't know for sure what people are going to search for in the future. The "adwords" problem therefore needs a greedy algorithm because all you can do is make the best choice for each search and hope it results in the best overall outcome.

A simplified version of this "adwords" problem can be modeled as maximal matching in bipartite graphs. A matching is a subset of edges where no vertex is an end of two or more edges. A perfect matching contains every vertex and a maximal matching is the largest possible matching for the graph. In this case one side of the graph is search queries, the other side is ads, and the edges are who the ads could be shown to. The maximal matching is the best way to display the ads. The simplifying assumptions are that one ad is shown, all advertisers have the same budget, click-through rates are the same, and bids are either 0 or 1.

The obvious greedy algorithm for matching will consider edges in the order they are given. An edge is part of the matching if neither end is connected to an edge already added to the matching. The competitive ratio is defined as the ratio between the worst online algorithm and the best offline algorithm. The offline solution is the optimal solution because all information about the problem is known in advance. For our bipartite matching solution the ratio is only 0.5, that is it will always find at least half as many matches as what is optimal.

It is possible to do better. The more realistic BALANCE algorithm considers the highest bidder and the highest remaining budget. By doing so it results in a competitive ratio of 0.63 which is the highest possible for an online algorithm.

UPDATE:

Bipartite matching implementations can be found in NetworkX and SciPy.

Resources
http://infolab.stanford.edu/~ullman/mmds/ch8.pdf