Behind the Scenes: Twitter, Part 2 - Lessons from email

A disclaimer: I’m not a credentialed statistician or expert on this topic. My apologies for any errors in explanation; they are indavertent.
The idea behind Bayesian filtering is that there is a probability that a given message is spam based on the presence of a specific word or phrase.
If you have a set of messages that are spam and non-spam, you can easily compute the probability for a single word – take the number of messages that have the word and are spam and divide it by the total number of messages that have the word:

In most cases, no single word is going to be a very effective predictor, and so the real value comes in combining the probabilities for a great many words. I’ll skip the mathematical explanation, but the bottom line is that by taking a mapping of words to emails that are known to be spam or not, you can compute a likelihood that a given new message is spam. If the probability is greater than a threshold, that email is flagged as spam.
This is all relatively simple, and for a reasonable set of words and messages you can do it by hand. There are refinements to deal with rare words, phrases, etc., but the basic theory is straightforward.

Building a classifer

Let’s take a look at the actual steps involved with building a classifier for our Twitter problem. Since it’s the toolchain I’m most familiar with, I’ll refer to steps taken using R, but you can do this in virtually any language.
Our starting point is a dataframe called “tweets” that contains the content of the tweet and whether or not it needed an immediate reply, which is the classification we’re trying to make. There are other attributes that might improve our classifier, but for now we’ll scope the problem down to the simplest form possible.
After some cleaning, we’re left with a sample of just over 6,500 tweets since we switched to our internally built tool, of which 12.3% received an immediate reply.

> str(tweets)
'data.frame':    6539 obs. of  2 variables:
 $ body     : chr  "Some advice from Jeff Bezos http://buff.ly/RNue6l" "http://37signals.com/svn/posts/3289-some-advice-from-jeff-bezos" "Mutual Mobile: Interaction Designer http://jobs.37signals.com/jobs/11965?utm_source=twitterfeed&utm_medium=twitter" "via @37Signals: Hi my name is Sam Brown - I’m the artist behind Explodingdog. Jason invited me to do some draw... htt"| __truncated__ ...
 $ replied  : logi  FALSE FALSE FALSE FALSE FALSE FALSE ...

Even before building any models, we can poke at data and find a few interesting things about the portion of tweets that needed an immediate reply given the presence of a given phrase:

Word	Portion requiring immediate reply
All tweets	12.3%
“svn”	0.2%
“job”	0.5%
“support”	17.3%
“highrise”	20.8%
“campfire”	26.9%
“help”	35.4%
“basecamp”	49.5%

This isn’t earth shattering—this is exactly what you’d expect, and is the basis for the rudimentary classification we initially used.
With our data loaded and cleaned, we’ll get started building a model. First, we’ll split our total sample in two to get a “training” and a “test” set. We don’t want to include all of our data in the “training” of the model (computing the probabilities of a reply given the presence of a given word), because then we don’t have an objective way to evaluate the performance of it.

The simplest model to start

I always like to start by building a very simple model – it helps to clarify the problem in your mind without worrying about any specifics of anything advanced, and with no expectation of accuracy. In this case, one very simple model is to predict whether or not a tweet needs a reply based only on the overall probability that one does – in other words, randomly pick 12.3% of tweets as needing an immediate reply. If you do this, you end up with a matrix of predicted vs. actual that looks like:

	actual
predicted	FALSE	TRUE
FALSE	2878	374
TRUE	402	51

Here, we got the correct prediction in 2,929 cases and the wrong outcome in 776 cases; overall, we correctly classified the outcome about 79% of the time. If you run this a thousand times, you’ll get slightly different predictions, but they’ll be centered in this neighborhood.
This isn’t very good, for two reasons:

1. As gross accuracy goes, it’s not that great—we could have built an even simpler model that always predicted that a message won’t require an immediate reply, because most (about 88%) don’t.
2. We classified 374 messages that actually did need an immediate response as not needing one, which in practice means that those people wouldn’t get a response as quickly as we’d like. That’s a pretty terrible hit rate—only 12% of tweets needing a reply got one immediately. This is the real accuracy measure we care about, and this model did pretty terribly on that regard.

Building a real model

To build our real model, we’ll start by cleaning and constructing a dataset that can be analyzed using the “tm” text mining package for R. We’ll construct a corpus of the tweet bodies and perform some light manipulations – stripping whitespace and converting everything to lower case, removing stop words , and stemming. Then, we’ll construct a “document term matrix”, which is a mapping of which documents have which words.

require(tm)
train_corpus <- Corpus(VectorSource(training$body))
train_corpus <- tm_map(train_corpus, stripWhitespace)
train_corpus <- tm_map(train_corpus, tolower)
train_corpus <- tm_map(train_corpus, stemDocument, "english", stemmer="Rstem")
train_dtm <- DocumentTermMatrix(train_corpus)

With stopwords removed, the list of frequent terms begins to resemble the vocabulary of things that are talked about related to 37signals:

findFreqTerms(train_dtm, 150)

• ”...”
• ”@jasonfried”
• “advice”
• “apple”
• “basecamp”
• “bezos”
• “competing”
• “creep”
• “design”
• “easy”
• “fried”
• “goal”
• “hiring”
• “http://37signals.com/svn/posts/*”
• etc

The presence of ”...” in the frequent terms list above might seem a little confusing. It makes more sense when you take a look at some of the original tweet bodies – many services that automatically tweet from RSS feeds or retweets shorten the content and use ellipses to indicate that there is more content that’s not included. Though often you remove punctuation in this sort of analysis, I’ve left these in our dataset. I have a hunch they’ll be important—most people who are manually writing tweets and need help immediately aren’t using ellipses.
For simplicity, we’re also only going to consider the probabilities for single words; you could build a similar model using bigrams (two word phrases) or longer, but for these purposes, we’ll focus on the simple case.
The document term matrix we’ve ended up with is what’s known as “sparse” – we have about 5,800 unique terms spread across 3,000 or so “documents” (tweets), but most tweets don’t have most words. If you imagine a grid of tweets on one axis and terms on the other, just one tenth of one percent of the 19 million possible combinations are filled in.
The “long tail” of terms that were used once usually adds significant computational complexity without much improvement in predictive accuracy, so we’ll prune those off our matrix:

train_dtm <- removeSparseTerms(train_dtm, 0.99)

This dramatically drops the size of our matrix—from 19 million combinations to around 300,000. This also means that we’re dropping from 5,800 terms to just the 100 or so that occur most frequently (a later re-running of the model with larger numbers of words didn’t meaningfully impact the accuracy compared to the 100-word version, but did have a 50x impact on runtime).
With all of our data preparation done, we can build the actual model. It’s not terribly hard to implement Naive Bayes from scratch in any programming language, and I’d encourage you to do just that – it’s a good exercise in both programming and probability. Practically, there’s no business value in reimplementing algorithms, so I usually use someone else’s hard work, in this case through the ‘e1071’ package.

require(e1071)
# Create a matrix from the document term matrix and normalize to examine only the presence or absence of a word, not the frequency.
norm_train <- inspect(train_dtm)
norm_train <- norm_train > 0
# Convert to a dataframe and vectorize
train_df <- as.data.frame(norm_train)
for(i in 1:length(train_df)) {
  train_df[,i] <- as.factor(train_df[,i])
}

# Build the model - compute the probabilities of each term
model <- naiveBayes(train_df, as.factor(training$replied), laplace=1)
# Make prediction on the held-back test/evaluation dataset
pred <- predict(model, test_df)
#Compare prediction and actual
table(pred, evaluation$replied)

When done, we end up with a comparison of prediction vs. actual again:

	actual
predicted	FALSE	TRUE
FALSE	2898	30
TRUE	400	402

Overall, this model gets about 89% of predictions correct – somewhat better than our naive model (about 79%), a model that always picks ‘no immediate response needed’ (about 88%), and better than our keyword based approach (about 65% gross accuracy).
More significantly, it has a false positive rate of about 7% (7 out of every hundred tweets that do require an immediate response will be categorized as not needing one), compared to 88% for our naive model.
Compared to our original methodology of prioritizing just based on keywords, we’ve raised the portion of non-urgent tweets we’re filtering out from 60% to nearly 90%, which dramatically lowers the volume of potentially high priority tweets to review.

What’s next?

This is about the result I expected from the time invested (a couple hours, including trying a range of variations not shown here) – it beats both our original implementation and our naive implementation on most of the measures we care about.
In the third and final part of this series, I’ll talk about what we did with the results of this model and how it impacted the business on a practical level.