First Meal of 2015 (Guide to French Toast)
I’m not really a breakfast person. Growing up in Cyprus, breakfast is typically a frappe and some figs in the summer. That’s why, whenever I have to make breakfast, I resort to my secret weapon, the…
Being Truly Asynchronous With Tornado
In the past few days I’ve had the chance to play a bit with Tornado, a non-blocking web server for Python similar to node.js. Tornado works by using something like epoll or whatever I/O event notification exists in the system. Tornado is single threaded and works like a fancy while (True) loop. As a consequence, whenever we do some blocking I/O (e.g. database call) the web server cannot process other requests. While that may not be a big deal on very low traffic sites or if your I/O subsystem is extremely fast, it starts becoming an issue as your traffic grows or if you’re hosted on something like Amazon AWS; notorious for its slow and inconsistent disk I/O performance. The biggest problems that I encountered with Tornado are: 1) the lack of robust asynchronous libraries for things like DB access and 2) Python’s own awkwardness when dealing with async code. NodeJS programmers don’t have any of these problems because the community writes software with async in mind and Javascript as a language offers anonymous blocks which make callback style code tolerable. The purpose of this post is to encourage Python programmers using Tornado to pay attention to their blocking calls or if they don’t need any of the features that Tornado offers, stick to a WSGI server such as uwsgi or gunicorn.…
The Hashing Trick
If you are doing any sort of classification with thousands of features (as is common in text classification) and need to update your Bag of Words models online, then you’ll find this rather simple technique very handy. At some point while developing Sidelines, we were using LDA to cluster tens of thousands of articles in topics (this is no longer the case however). After extracting the text we would: 1) Remove stop words, 2) Construct a dictionary to map each word to a unique id, frequency tuple and 3) Prune that dictionary to remove very rarely used and very often used words. The biggest problem we faced was running out of memory as we’d have to make a pass over all our data to construct this dictionary. Even if we tried to segment our corpus and split them into different machines, keeping these huge dictionaries in memory was a pain, while swapping to disk was extremely slow.…
Making Sense Out of Naive Bayes Probability Estimates
Most introductory textbooks on supervised learning algorithms examine the algorithm from a single classification point of view, meaning we only need to decide if an item belongs to a certain class or not. Multi-class classification, an instance of the same problem is typically done by training multiple such binary classifiers for each pair of classes. There are various improvements over these techniques, but very few papers examine how to get meaningful probability estimates out of a learning algorithm. At Sidelines, we use the probability output of some of our classifiers to predict how relevant a sports news article is to a specific team. We then use that input as part of our ranking algorithm. For example, this article is mostly about the Boston Celtics and it should rank high in a Celtics feed, but Mavericks’ fans would also be somewhat interested although it should not rank as high in their feed. To get good probability estimates though, some offline experimentation is needed. An untuned instance of Naive Bayes would tend to give estimates either near 0 or near 1 with very few articles inbetween. I’m speculating that this is because of the large number of words very frequently repeated in all documents. Mizil and Caruana examine methods to tune a variety of algorithms in their 2005 paper “Predicting Good Probabilities With Supervised Learning”. The authors test two calibration methods, Platt Scaling and Isotonic Regression for SVMs, Logistic Regression, Decision Trees, KNN, Naive Bayes, etc. They conclude that a) Platt Scaling works best when the calibration set is small and works best with max margin algorithms such as SVMs, b) Isotonic Regression usually outperforms Platt Scaling when the calibration set is large and it is the calibration method of choice for Naive Bayes. How to use Isotonic Regression for calibration is described in detail by Zadrozny and Elkan in “Transforming Classifier Scores into Accurate Multiclass Probability Estimates”. Same paper also goes into detail about the multiclass case but we’ll leave that for another time. Here is the methodology one can use to calibrate NB:…
String searching using Aho-Corasick
At Sidelines, we frequently need to quickly identify which athletes a news article may be talking about. Most of the time, a number of machine learning classifiers make sure that the article gets correctly labeled, but sometimes we need to run the title or even the entire text of the article against our database of athlete names. Using pre-compiled regular expressions does not scale (we have thousands of athletes and staff names in our database) and running each keyword against the target text would be too slow.…
Power of k random choices
This is one of my favorite results of all times. A really simple neat trick that any developer can use in a variety of situations without really having to understand how it works. Think of the following hypothetical: you have a bunch of bins and a bunch of balls and you want to load up the bins as evenly as possible. If the bins and the balls were of same size, a round-robin strategy would work well. If they were not, you’d expect that just putting a ball in a bin at random would work well, however here we propose a different scheme that will perform better. Pick two bins at random and put the ball in the least loaded bin.…