An algorithm to sort "Top" Comments


Preface: This example is a (greatly modified) excerpt from the open-source book Bayesian Methods for Hackers, currently being developed on Github ;)

Why is sorting from "best" to "worst" so difficult?

Consider ratings on online products: how often do you trust an average 5-star rating if there is only 1 reviewer? 2 reviewers? 3 reviewers? We implicitly understand that with such few reviewers that the average rating is not a good reflection of the true value of the product.

This has created flaws in how we sort items. Many people have realized that sorting online search results by their rating, whether the objects be books, videos, or online comments, return poor results. Often the seemingly top videos or comments have perfect ratings only from a few enthusiastic fans, and truly more quality videos or comments are hidden in later pages with falsely-substandard ratings of around 4.8. How can we correct this?

Consider the popular site Reddit (purposefully did not link to the website as you would never come back). The site hosts links to stories or images, and a very popular part of the site are the comments associated with each link. Redditors can vote up or down on each comment (called upvotes and downvotes). Reddit, by default, will sort comments by Top, that is, the best comments. How would you determine which comments are the best? There are a number of ways to achieve this:

  1. Popularity: A comment is considered good if it has many upvotes. A problem with this model is to consider a comment with hundreds of upvotes, but thousands of downvotes. While being very popular, the comment is likely more controversial than best.
  2. Difference: Using the difference of upvotes and downvotes. This solves the above problem, but fails when we consider the temporal nature of comments. Comments can be posted many hours after the original link submission. The difference method will bias the Top comments to be the oldest comments, which have accumulated more upvotes than newer comments, but are not necessarily the best.
  3. Time adjusted: Consider using Difference divided by the age of the comment. This creates a rate, something like difference per second, or per minute. An immediate counter example is, if we use per second, a 1 second old comment with 1 upvote would be better than a 100 second old comment with 99 upvotes. One can avoid this by only considering at least $t$ second old comments. But what is a good $t$ value? Does this mean no comment younger than $t$ is good? We end up comparing unstable quantities with stable quantities (young vs. old comments).
  4. Ratio: Rank comments by the ratio of upvotes to total number of votes (upvotes plus downvotes). This solves the temporal issue, such that new comments who score well can be considered Top just as likely as older comments, provided they have many upvotes to total votes. The problem here is that a comment with a single upvote (ratio = 1.0) will beat a comment with 999 upvotes and 1 downvote (ratio = 0.999), but clearly the latter comment is more likely to be better.

I used the phrase more likely for good reason. It is possible that the former comment, with a single upvote, is in fact a better comment than the later with 999 upvotes. The hesitation to agree with this is because we have not seen the other 999 potential votes the former comment might get. Perhaps it will achieve an additional 999 upvotes and 0 downvotes and be considered better than the latter, though not likely.

What we really want is an estimate of the true upvote ratio. Note that the true upvote ratio is not the same as the observed upvote ratio: the true upvote ratio is hidden, and we only observe upvotes vs. downvotes (one can think of the true upvote ratio as "what is the underlying probability someone gives this comment a upvote, versus a downvote"). So the 999 upvote/1 downvote comment probably has a true upvote ratio close to 1, which we can assert with confidence thanks to the Law of Large Numbers, but on the other hand we are much less certain about the true upvote ratio of the comment with only a single upvote. Sounds like a Bayesian problem to me.

What is our prior distribution though? (Prior? If you are unfamiliar with Bayesian methods, you should totally read the book, or check out this quick intro). One way to determine a prior on the upvote ratio is that look at the historical distribution of upvote ratios. This can be accomplished by scrapping Reddit's comments and determining a distribution. There are a few problems with this idea though:

  1. Skewed data: The vast majority of comments have very few votes, hence there will be many comments with ratios near the extremes of 1.0 and 0, effectively skewing our distribution to the extremes.
  2. Biased data: Reddit is composed of different subpages, called subreddits. Two examples are r/aww, which posts pics of cute animals, and r/politics. It is very likely that the user behaviour towards comments of these two subreddits are very different: visitors are likely friendly and affectionate in the former, and would therefore upvote comments more, compared to the latter, where comments are likely to be controversial and disagreed upon. Therefore not all comments are the same.

In light of these, I think it is better to use a Uniform prior for the true upvote ratio.

Below is an image that was trending Reddit last weekend. We have scrapped all the comments, plus their upvotes and downvotes. Editor's Note: The book, Bayesian Methods for Hackers, scrapes Reddit in real-time, and returns the currently most popular image + comments.

Title of submission: 
The Golden Tortoise Beatle. 
http://i.imgur.com/6F7JytV.jpg
Some Comments (out of 69 total) 
-----------
"That's badass as fuck"
upvotes/downvotes:  [34  4]

"What kind of dog is this? "
upvotes/downvotes:  [407  39]

"http://i.imgur.com/8dMVsoQ.jpg"
upvotes/downvotes:  [2 0]

"I'm ready for the perpetual downvotes into extreme negative karma, but it's "beetle""
upvotes/downvotes:  [13  2]

For a given true upvote ratio $p$ and $N$ total votes, the number of upvotes will look like a Binomial random variable with parameters $p$ and $N$. (This is because of the equiviliance between upvote ratio and probability of upvoting versus downvoting, out of $N$ possible votes/trials). We create a function that performs Bayesian inference on $p$, for a particular comment's upvote/downvote pair. We are going to use PyMC to determine the posterior distribution of the true upvote ratio for each comment:

import pymc as mc

def posterior_upvote_ratio( upvotes, downvotes, samples = 20000):
    N = upvotes + downvotes
    upvote_ratio = mc.Uniform( "upvote_ratio", 0, 1 )
    observations = mc.Binomial( "obs",  N, upvote_ratio, value = upvotes, observed = True)
    
    model = mc.Model( [upvote_ratio, observations ]) 
    map_ = mc.MAP(model).fit()
    mcmc = mc.MCMC(model)
    
    mcmc.sample(samples, samples/4)
    
    return mcmc.trace("upvote_ratio")[:]

Below are the resulting posterior distributions.

Some distributions are very tight, others have very long tails (relatively speaking), expressing our uncertainity with what the true upvote ratio might be.

Sorting!

We have been ignoring the goal of this exercise: how do we sort the comments from best to worst? Of course, we cannot sort distributions, we must sort scalar numbers. There are many ways to distill a distribution down to a scalar: expressing the distribution through its expected value, or mean, is one way. Choosing the mean bad choice though. This is because the mean does not take into account the uncertainity of distributions.

I suggest using the 95% least plausible value, defined as the value such that there is only a 5% chance the true parameter is lower (think of the lower bound on the 95% credible region). Below are the posterior distributions with the 95% least-plausible value plotted:

The best comments, according to our procedure, are the comments that are most-likely to score a high percentage of upvotes. Visually those are the comments with the 95% least plausible value close to 1.

Why is sorting based on this quantity a good idea? By ordering by the 95% least plausible value, we are being the most conservative with what we think is best. That is, even in the worst case scenario, when we have severely overestimated the upvote ratio, we can be sure the best comments are still on top. Under this ordering, we impose the following very natural properties:

  1. given two comments with the same observed upvote ratio, we will assign the comment with more votes as better (since we are more confident it has a higher ratio).
  2. given two comments with the same number of votes, we still assign the comment with more upvotes as better

But this is too slow for real-time!

I agree, computing the posterior of every comment takes a long time, and by the time you have computed it, likely the data has changed. I delay the mathematics to the appendix, but I suggest using the following formula to compute the lower bound very fast.

$$ \frac{a}{a + b} - 1.65\sqrt{ \frac{ab}{ (a+b)^2(a + b +1 ) } }$$

where \begin{align} & a = 1 + u \\ & b = 1 + d \\ \end{align}

$u$ is the number of upvotes, and $d$ is the number of downvotes. The formula is a shortcut in Bayesian inference, which will be further explained in Chapter 6 when we discuss priors in more detail.

Approximate lower bounds:
[ 0.83190291  0.87696185  0.85967479  0.82587042  0.78000822  0.80326236
  0.85773646  0.82101369  0.74537828  0.76867393  0.73158407  0.72491057
  0.75202517  0.70806405  0.6530083   0.66278557  0.60091591  0.6530083
  0.60091591  0.60091591  0.6530083   0.60091591  0.60091591  0.60091591
  0.60091591  0.67526961  0.67526961  0.5997376   0.53055613  0.53055613
  0.53055613  0.60091591  0.53055613  0.53055613  0.53055613  0.53055613
  0.53055613  0.5772799   0.535       0.43047887  0.43047887  0.43047887
  0.43047887  0.43047887  0.43047887  0.43047887  0.43047887  0.43047887
  0.43047887  0.43047887  0.43047887  0.43047887  0.43047887  0.43047887
  0.43047887  0.43047887  0.43047887  0.43047887  0.43047887  0.43047887
  0.43047887  0.43047887  0.43047887  0.43047887  0.43047887  0.45074913
  0.45074913  0.45074913  0.45074913]

Sorted according to approximate lower bounds:

405 44 What kind of dog is this? 
-------------
222 26 [I posted this a while back, if you are interested.](http://thewonderfulwild.blogspot.co.uk/2013/01/golden-tortoise-beetle.html)
-------------
16 0 If you look really carefully you can actually see 4 tiny elephants... 
-------------
1248 224 [Other views](http://imgur.com/a/PLRl0). 

Edit: just now realizing I spelled "beetle" wrong in the title. Awesome. 
-------------
116 16 http://en.wikipedia.org/wiki/The_Gold-Bug

This short story by Poe was one of my favorites as a kid.  I was so excited when I learned that there really was a gold beetle.

tl;dr Go read this book by Edgar Allen Poe
-------------
101 14 The 1% bug.
-------------
80 12 [First thing I thought of] (http://www.retrogameage.com/wp-content/gallery/aladdin/aladdin-u-079.png)
-------------
27 3 It always amazes me how beautiful nature can be. Such cool patterns and colors.
-------------
44 7 Seriously, what kind of evolutionary advantages are there to looking like a golden tortoise? Especially when you're a beetle? Nature, you crazy.
-------------
32 5 I recognize that as the 5th Beatle.
-------------
35 6 That's badass as fuck
-------------
21 3 It would be nice if you gave credit to the original source and photographer Chime Tsetan: http://www.projectnoah.org/spottings/7201707
-------------
7 0 That's a fancy fuckin' exoskeleton you've got there for just spending all your time hanging out on plants and shit, Mr. Golden Tortoise Beetle. Go out and have some adventures while you're all dressed up.
-------------
11 1 I remember the first time the first time I saw this in person being really surprised when it moved. I had never (until now) seen or heard about this bug. I saw this in India...Do you know where these bugs are from and why they are so rare?
-------------
13 2 OMFG A SHINY , THROW A MASTERBALL NOW NOW NOW NOW NOW NOW

-------------
13 2 I'm ready for the perpetual downvotes into extreme negative karma, but it's "beetle"
-------------
9 1 Give it to a bug collector for a rupee bag upgrade
-------------
5 0 Wow, I have never wanted this bad to almost maybe see a bug in person... From far away....


^wearing ^a ^protective ^suit


^^and ^^disinfectant 
-------------
5 0 It's like a trippy take on the [Great A'tuin](http://www.lspace.org/books/whos-who/atuin.html)
-------------
5 0 I'd actually feel a little bad crushing it.
-------------
4 0 These things are pretty rare/cool but if you can manage to catch one, the Quidditch game is over and your team gets 150 points.
-------------
4 0 I wonder why they call it that.
-------------
4 0 this is like that beetle from that really weird point and click kid's game about insects with that strange kid and there's like a dog and a barn, can't remember the details but it was a thing back in the day



it's been found, here's a link if you want to relive it: http://www.youtube.com/watch?v=NpeO491QOEs
-------------
4 0 Came here for absurd amounts of bad puns involving the Beatles. Was really disappointed. Then uplifted because of it. 

Then sad again, because my life kind of sucks.
-------------
4 0 I could really use a Golden Thief Bug Card...
-------------
4 0 [This is a great find! I heard that if you catch one on Booster Hill, you can trade it in at Seaside Town for a Frog Coin!](http://www.youtube.com/watch?v=Q0Pemr2pM-o&feature=player_detailpage#t=21s)
-------------
4 0 This photo is from a great app/organization called Project Noah. http://www.projectnoah.org/spottings/7201707
-------------
4 0 I think there's something on your contact lens...
-------------
12 3 That's gorgeous!  Where was this picture taken?
-------------
21 8 Still more talented than Ringo.
-------------
13 5 Holy Crap, the golden snitch from harry potter is real?
-------------
3 0 What's that transparent lid? That's the amazing part which makes the little thing looks not real...
-------------
3 0 Once you find 23 more you should take them to Agitha.
-------------
3 0 What's that clear stuff around it then?

-------------
3 0 I never thought I would see a bug and think I browsing r/aww
-------------
3 0 life is amazing...
-------------
3 0 And this will definitely be reposted on [r/lounge](http://www.reddit.com/r/lounge)
-------------
3 0 I think i saw one of these on Gintama 
-------------
3 0 This is Aspidimorpha sanctaecrucis (aka Golden Tortoise Beetle), spotted in southern India by chimetsetan. Info: http://www.projectnoah.org/spottings/7201707
-------------
4 1 That's some Zelda shit right there.
-------------
4 1 looks like reddit gold
-------------
4 1 Will you accept your payment in beetles?
-------------
4 1 thats a funny looking "beatle"
-------------
2 0 I found the poo-colored cousin of these in my invertebrate zoology class. Here's what it looked like http://richardpeters.typepad.com/.a/6a0120a7aae27b970b015432749d57970c-800wi 
-------------
2 0 More pictures and info here:  http://entomology.ifas.ufl.edu/creatures/veg/potato/golden_tortoise_beetle.htm
-------------
2 0 What an unfortunate, beautiful evolution. 

I'm surprised it's still around being that so many animals fucking *love* shiny things. 

-------------
2 0 I want to make buttons out of them!
-------------
2 0 Any good evolutionary explanations for its appearance? Where are these native to?
-------------
2 0 There is an intelligent designer....and he's FABULOUS 
-------------
2 0 Golden Tortoise - I just had a flash back to The Dark Tower Series - S.King... I'm sure if you read it you will remember
-------------
2 0 My God. Incredible. What a wondrous world we have. 
-------------
2 0 Beautiful, isn't it? 
-------------
2 0 Can it actually fly with those wings? Nature, you cray.
-------------
2 0 Absolutely wonderful 
-------------
2 0 How much is it worth?  
-------------
2 0 This insect is awesome. 
-------------
2 0 That is awesome
-------------
2 0 That is the most beautiful bug I have ever seen

Appendix

Derivation of sorting comments formula

Basically what we are doing is using a Beta prior (with parameters $a=1, b=1$, which is a uniform distribution), and using a Binomial likelihood with observations $u, N = u+d$. This means our posterior is a Beta distribution with parameters $a' = 1 + u, b' = 1 + (N - u) = 1+d$. We then need to find the value, $x$, such that 0.05 probability is less than $x$. This is usually done by inverting the CDF, but the CDF of the beta, for integer parameters, is known but is a large sum [3].

We instead using a Normal approximation. The mean of the Beta is $\mu = a'/(a'+b')$ and the variance is

$$\sigma^2 = \frac{a'b'}{ (a' + b')^2(a'+b'+1) }$$

Hence we solve the following equation for $x$ and have an approximate lower bound.

$$ 0.05 = \Phi\left( \frac{(x - \mu)}{\sigma}\right) $$

References

  1. Probabilistic Programming and Bayesian Methods for Hackers. 163rd . 2013. eBook. .
  2. Patil, A., D. Huard and C.J. Fonnesbeck. 2010. PyMC: Bayesian Stochastic Modelling in Python. Journal of Statistical Software, 35(4), pp. 1-81


Other articles to enjoy:

Follow me on Twitter at cmrn_dp


All Blog Articles

DataOrigami Launch

June 24th, 2014

I'm proud to announce my latest project, dataorigami.net! Why are you still here, go check it out!

continue reading...


Feature Space

May 22th, 2014

Feature space refers to the $n$-dimensions where your variables live (not including a target variable, if it is present). The term is used often in ML literature because a task in ML is *feature extraction*, hence we view all variables as features. For example, consider the data set with:

continue reading...


Generating exponential survival data

March 02th, 2014

TLDR: Suppose we interested in generating exponential survival times with scale parameter $\lambda$, and having $\alpha$ probability of censorship ( $0 < \alpha < 1$. This is actually, at least from what I tried, a non-trivial problem. Here's the algorithm, and below I'll go through what doesn't work to:

continue reading...


Deriving formulas for the expected sample size needed in A/B tests

December 27th, 2013

Often an estimate of the number of samples need in an A/B test is asked. Now I've sat down and tried to work out a formula (being disatisfied with other formulas' missing derivations). The below derivation starts off with Bayesian A/B, but uses frequentist methods to derive a single estimate (God help an individual interested in a posterior sample size distribution!)

continue reading...


lifelines: survival analysis in Python

December 19th, 2013

The lifelines library provides a powerful tool to data analysts and statisticians looking for methods to solve a common problem:

How do I predict durations?

This question seems very vague and abstract, but thats only because we can be so general in this space. Some more specific questions lifelines will help you solve are:

continue reading...


Evolutionary Group Theory

October 03th, 2013

We construct a dynamical population whose individuals are assigned elements from an algebraic group \(G\) and subject them to sexual reproduction. We investigate the relationship between the dynamical system and the underlying group and present three dynamical properties equivalent to the standard group properties.

continue reading...


Videos about the Bayesian Methods for Hackers project

August 25th, 2013

  1. New York Tech Meetup, July 2013: This one is about 2/3 the way through, under the header "Hack of the month"

    Available via MLB Media player
  2. PyData Boston, July 2013: Slides available here

    Video available here.
continue reading...


Warrior Dash 2013

August 03th, 2013

Warrior dash data, just like last year: continue reading...


The Next Steps

June 16th, 2013

June has been an exciting month. The opensource book Bayesian Methods for Hackers I am working on blew up earlier this month, propelling it into Github's stratosphere. This is both a good and bad thing: good as it exposes more people to the project, hence more collaborators; bad because it is showing off an incomplete project -- a large fear is that advanced data specialists disparage in favour of more mature works the work to beginner dataists.

continue reading...


NSA Honeypot

June 08th, 2013

Let's perform an experiment.

continue reading...


21st Century Problems

May 16th, 2013

The technological challenges, and achievements, of the 20th century brought society enormous progress. Technologies like nuclear power, airplanes & automobiles, the digital computer, radio, internet and imaging technologies to name only a handful. Each of these technologies had disrupted the system, and each can be argued to be Black Swans (à la Nassim Taleb). In fact, for each technology, one could find a company killed by it, and a company that made its billions from it.

continue reading...


ML Counterexamples Pt.2 - Regression Post-PCA

April 26th, 2013

Principle Component Analysis (PCA), also known as Singular Value Decomposition, is one of the most popular tools in the data scientist's toolbox, and it deserves to be there. The following are just a handful of the uses of PCA:

  • data visualization
  • remove noise
  • find noise (useful in finance)
  • clustering
  • reduce dataset dimension before regression/classification, with minimal negative effect
continue reading...


Machine Learning Counterexamples Pt.1

April 24th, 2013

This will the first of a series of articles on some useful counterexamples in machine learning. What is a machine learning counterexample? I am perhaps using the term counterexample loosely, but in this context a counterexample is a hidden gotcha or otherwise a deviation from intuition.

Suppose you have a data matrix $X$, which has been normalized and demeaned (as appropriate for linear models). A response vector $Y$, also standardized, is regressed on $X$ using your favourite library and the following coefficients, $\beta$, are returned:

continue reading...


Multi-Armed Bandits

April 06th, 2013

Suppose you are faced with $N$ slot machines (colourfully called multi-armed bandits). Each bandit has an unknown probability of distributing a prize (assume for now the prizes are the same for each bandit, only the probabilities differ). Some bandits are very generous, others not so much. Of course, you don't know what these probabilities are. By only choosing one bandit per round, our task is devise a strategy to maximize our winnings.

continue reading...


Cover for Bayesian Methods for Hackers

March 25th, 2013

The very kind Stef Gibson created an amazing cover for my open source book Bayesian Methods for Hackers. View it below:

continue reading...


An algorithm to sort "Top" Comments

March 10th, 2013

Consider ratings on online products: how often do you trust an average 5-star rating if there is only 1 reviewer? 2 reviewers? 3 reviewers? We implicitly understand that with such few reviewers that the average rating is not a good reflection of the true value of the product.

This has created flaws in how we sort items. Many people have realized that sorting online search results by their rating, whether the objects be books, videos, or online comments, return poor results.

continue reading...


How to solve the Price is Right's Showdown

February 05th, 2013

Preface: This example is a (greatly modified) excerpt from the book Probabilistic Programming and Bayesian Methods for Hackers in Python, currently being developed on Github ;)

How to solve* the Showdown on the Price is Right

*I use the term loosely and irresponsibly.

It is incredibly surprising how wild some bids can be on The Price is Right's final game, The Showcase. If you are unfamiliar with how it is played (really?), here's a quick synopsis:

continue reading...


My favourite part of The Extended Phenotype

February 02th, 2013

To quote directly from the book, by Richard Dawkins:

continue reading...


The awesome power of Bayesian Methods - Part II - Optimizing Loss Functions

January 10th, 2013

Hi again, this article will really show off the flexibility of Bayesian analysis. Recall, Bayesian inference is basically being interested in the new random variables, $\Theta$, distributed by $$ P( \Theta | X ) \propto L( X | \Theta )P(\Theta )$$ where $X$ is observed data, $L(X | \Theta )$ is the likelihood function and P(\Theta) is the prior distribution for $\Theta$. Normally, computing the closed-form formula for the left-hand side of the above equation is difficult, so I say screw closed-forms. If we can sample from $P( \Theta | X )$ accurately, then we can do as much, possibly more, than if we just had the closed-form. For example, by drawing samples from $P( \Theta | X )$, we can estimate the distribution to arbitrary accuracy. Or find expected values for easily using Monte Carlo. Or maximize functions. Or...well I'll get into it.

continue reading...


Interior Design with Machine Learning

January 04th, 2013

While designing my new apartment, I found a very cool use of machine learning. Yes, that's right, you can use machine learning in interior design. As crazy as it sounds, it is completely legitimate.

continue reading...


The awesome power of Bayesian Methods - What they didn't teach you in grad school. Part I

December 27th, 2012

For all the things we learned in grad school, Bayesian methods was something that was skimmed over. Strange too, as we learned all the computationally machinery necessary, but we were never actually shown the power of these methods. Let's start our explanation with an example where the Bayesian analysis clearly simply is more correct (in the sense of getting the right answer).

continue reading...


How to bootstrap your way out of biased estimates

December 06th, 2012

Bootstrapping is like getting a free lunch, low variance and low bias, by exploiting the Law of Large numbers. Here's how to do it:

continue reading...


High-dimensional outlier detection using statistics

November 27th, 2012

I stumbled upon a really cool idea of detecting outliers. Classically, one can plot the data and visually find outliers. but this is not possible in higher-dimensions. A better approach to finding outliers is to consider the distance of each point to some central location. Data points that are unreasonably far away are considered outliers and are dealt with.

continue reading...


A more sensible omnivore.

November 17th, 2012

My girlfriend, who is a vegetarian, and I often discuss the merits and dismerits of being a vegetarian. Though I am not a vegetarian (though I did experiment with veganism and holistic diets during some One Week Ofs), very much agree that eating as much meat as we do is not optimal.

Producing an ounce of meat requires a surprising amount of energy, whereas it's return energy is very small. We really only eat meat for its taste. It is strange how often we, the human omnivores, require meat in a meal, less it's not a real meal (and we do this three times a day). And unfortunately, a whole culture eating this way is not sustainable.

I have often thought about a life without meat,

continue reading...


Kaggle Data Science Solution: Predicting US Census Return Rates

November 01th, 2012

The past month two classmates and I have been attacking a new Kaggle contest, Predicting US Census mail return rates. Basically, we were given large amounts of data about block groups, the second smallest unit of division in the US census, and asked to predict what fraction of individuals from the block group would mail back their 2010 census form.

continue reading...


Visualizing clusters of stocks

October 14th, 2012

One troubling aspect of an estimated covariance matrix is that it always overestimates the true covariance. For example, if two random variables are independent the covariance estimate for the two variables is always non-zero. It will converge to 0, yes, but it may take a really long time.

What's worse is that the covariance matrix does not understand causality. Consider the certainly common situation below:

continue reading...


Twitter Pyschopathy

October 08th, 2012

Released earlier was the research paper about predicting psychopathy using Twitter behaviour. Read the paper here.

continue reading...


UWaterloo Subway Map

September 22th, 2012

I think my thing with subway maps is getting weird. I just created a fictional University of Waterloo subway map using my subway.js library.

continue reading...


Sampling from a Conditional Markov Chain

September 15th, 2012

My last project involving the artificial creation of "human-generated" passwords required me to sample from a Markov Chain. This is not very difficult, and I'll outline the sampling algorithm below. For the setup, suppose you have a transition probability matrix $M$ and an initial probability vector $\mathbf{v}$. The element $(i,j)$ of $M$ is the probability of the next state being $j$ given that the current state is $i$. The initial probability vector element $i$ is the probability that the first state is $i$. If you have these quantities, then to sample from a realized Markov process is simple:

continue reading...


Modeling password creation

September 14th, 2012

Creating a password is an embarrassingly difficult task. A password needs to be both memorable and unique enough not to be guessed. The former criterion prevents using randomly generated passwords (try remembering 9st6Uqfe4Z for Gmail, rAEOZmePfT for Facebook, etc.), and the latter is the reason why passwords exist in the first place. So the task falls on humans to create their own passwords and carefully balance these two criteria. This has been, and still is, a bad idea.

continue reading...


Eurotrip & Python

August 13th, 2012

Later this month, my lovely girlfriend and I are travelling to Amsterdam, Berlin and Kiel. The first half of the trip we will be exploring the tourist and nontourist areas of Amsterdam and Berlin. I'm very excited as I get to spend time drinking and relaxing with my girlfriend. But then...

continue reading...


Turn your Android phone into a SMS-based Command Line

August 11th, 2012

One of my biggest pet peeves is not having my phone with me. This often occurs if the phone is charging and I need to leave, or I have forgotten it somewhere, or it is lost, or etc. I've created a partial solution.

continue reading...


Least Squares Regression with L1 Penalty

July 31th, 2012

I want to discuss, and exhibit, a really cool idea in machine learning, optimization and statistics. It's a simple idea: adding a constraint to an optimization problem, specifically a constraint on the sum, can have huge impacts on your interpretation, robustness and sanity. I must first introduce the family of functions we will be discussing.

The family of L-norm penalty functions, $L_p:R^d \rightarrow R$, is defined: $$ L_p( x ) = || x ||_p = \left( \sum_{i=1}^d |x_i|^p \right) ^{1/p} \;\: p>0 $$ For $p=2$, this is the familar Euclidean distance. The most often used in machine learning literature are the

continue reading...


Warrior Dash Data

July 25th, 2012

Last Sunday I competed in a pretty epic competition: The Warrior Dash. It's 5k of, well honestly, it's 5k of mostly hills and trail running. Plus spread throughout are some pretty fun obstacles. With only five training workouts un...

continue reading...


Subway.js

July 17th, 2012

The javascript code that creates and controls the subway map above is available on GitHub. You can build your own using the pretty self-explanatory code + README document. Imagine using the code in a school project or advertising...

continue reading...


Kernelized and Supervised Principle Component Analysis

July 13th, 2012

Sorry the title is a bit of a mouthful. Everyone in statistics has heard of Principle Components Analysis ( PCA ). The idea is so simple, and a personal favourite of mine, so I'll detail it here.

continue reading...


Python Android Scripts

July 05th, 2012

I am having a blast messing around with my new Android phone. It has Python! Currently I am playing with the sensors on the phone. Built-in is a light sensor, accelerometer, and an

continue reading...


Predicting Psychopathy using Twitter Data

July 03th, 2012

The goal of this Kaggle contest was to predict an individuals psychopathic rating using information from their Twitter profile. I was given the already processed data and psychopathic scores. This was the first Kaggle competition I entered, and certainly not the last! If you'll excuse me, I must begin my technical remarks on my solution:

continue reading...


CamDP++

July 03th, 2012

Camdp.com is my latest attempt to digitize myself. I tried to map the subway lines to mimic my life and work, with each subway line representing a train of thought. I hope you enjoy the continue reading...


Data Science FAQ

July 02th, 2012

What is data science? What is an example of a data set? What are some of the goals of data science? What are some examples of data science in action? continue reading...


(All Blog Articles).filter( Science )

Feature Space

May 22th, 2014

Feature space refers to the $n$-dimensions where your variables live (not including a target variable, if it is present). The term is used often in ML literature because a task in ML is *feature extraction*, hence we view all variables as features. For example, consider the data set with:

continue...


Generating exponential survival data

March 02th, 2014

TLDR: Suppose we interested in generating exponential survival times with scale parameter $\lambda$, and having $\alpha$ probability of censorship ( $0 < \alpha < 1$. This is actually, at least from what I tried, a non-trivial problem. Here's the algorithm, and below I'll go through what doesn't work to:

continue...


Deriving formulas for the expected sample size needed in A/B tests

December 27th, 2013

Often an estimate of the number of samples need in an A/B test is asked. Now I've sat down and tried to work out a formula (being disatisfied with other formulas' missing derivations). The below derivation starts off with Bayesian A/B, but uses frequentist methods to derive a single estimate (God help an individual interested in a posterior sample size distribution!)

continue...


lifelines: survival analysis in Python

December 19th, 2013

The lifelines library provides a powerful tool to data analysts and statisticians looking for methods to solve a common problem:

How do I predict durations?

This question seems very vague and abstract, but thats only because we can be so general in this space. Some more specific questions lifelines will help you solve are:

continue...


Evolutionary Group Theory

October 03th, 2013

We construct a dynamical population whose individuals are assigned elements from an algebraic group \(G\) and subject them to sexual reproduction. We investigate the relationship between the dynamical system and the underlying group and present three dynamical properties equivalent to the standard group properties.

continue...


21st Century Problems

May 16th, 2013

The technological challenges, and achievements, of the 20th century brought society enormous progress. Technologies like nuclear power, airplanes & automobiles, the digital computer, radio, internet and imaging technologies to name only a handful. Each of these technologies had disrupted the system, and each can be argued to be Black Swans (à la Nassim Taleb). In fact, for each technology, one could find a company killed by it, and a company that made its billions from it.

continue...


ML Counterexamples Pt.2 - Regression Post-PCA

April 26th, 2013

Principle Component Analysis (PCA), also known as Singular Value Decomposition, is one of the most popular tools in the data scientist's toolbox, and it deserves to be there. The following are just a handful of the uses of PCA:

  • data visualization
  • remove noise
  • find noise (useful in finance)
  • clustering
  • reduce dataset dimension before regression/classification, with minimal negative effect
continue...


Machine Learning Counterexamples Pt.1

April 24th, 2013

This will the first of a series of articles on some useful counterexamples in machine learning. What is a machine learning counterexample? I am perhaps using the term counterexample loosely, but in this context a counterexample is a hidden gotcha or otherwise a deviation from intuition.

Suppose you have a data matrix $X$, which has been normalized and demeaned (as appropriate for linear models). A response vector $Y$, also standardized, is regressed on $X$ using your favourite library and the following coefficients, $\beta$, are returned:

continue...


Multi-Armed Bandits

April 06th, 2013

Suppose you are faced with $N$ slot machines (colourfully called multi-armed bandits). Each bandit has an unknown probability of distributing a prize (assume for now the prizes are the same for each bandit, only the probabilities differ). Some bandits are very generous, others not so much. Of course, you don't know what these probabilities are. By only choosing one bandit per round, our task is devise a strategy to maximize our winnings.

continue...


An algorithm to sort "Top" Comments

March 10th, 2013

Consider ratings on online products: how often do you trust an average 5-star rating if there is only 1 reviewer? 2 reviewers? 3 reviewers? We implicitly understand that with such few reviewers that the average rating is not a good reflection of the true value of the product.

This has created flaws in how we sort items. Many people have realized that sorting online search results by their rating, whether the objects be books, videos, or online comments, return poor results.

continue...


My favourite part of The Extended Phenotype

February 02th, 2013

To quote directly from the book, by Richard Dawkins:

continue...


N is never large.

January 15th, 2013

continue...


The awesome power of Bayesian Methods - Part II - Optimizing Loss Functions

January 10th, 2013

Hi again, this article will really show off the flexibility of Bayesian analysis. Recall, Bayesian inference is basically being interested in the new random variables, $\Theta$, distributed by $$ P( \Theta | X ) \propto L( X | \Theta )P(\Theta )$$ where $X$ is observed data, $L(X | \Theta )$ is the likelihood function and P(\Theta) is the prior distribution for $\Theta$. Normally, computing the closed-form formula for the left-hand side of the above equation is difficult, so I say screw closed-forms. If we can sample from $P( \Theta | X )$ accurately, then we can do as much, possibly more, than if we just had the closed-form. For example, by drawing samples from $P( \Theta | X )$, we can estimate the distribution to arbitrary accuracy. Or find expected values for easily using Monte Carlo. Or maximize functions. Or...well I'll get into it.

continue...


The awesome power of Bayesian Methods - What they didn't teach you in grad school. Part I

December 27th, 2012

For all the things we learned in grad school, Bayesian methods was something that was skimmed over. Strange too, as we learned all the computationally machinery necessary, but we were never actually shown the power of these methods. Let's start our explanation with an example where the Bayesian analysis clearly simply is more correct (in the sense of getting the right answer).

continue...


How to bootstrap your way out of biased estimates

December 06th, 2012

Bootstrapping is like getting a free lunch, low variance and low bias, by exploiting the Law of Large numbers. Here's how to do it:

continue...


High-dimensional outlier detection using statistics

November 27th, 2012

I stumbled upon a really cool idea of detecting outliers. Classically, one can plot the data and visually find outliers. but this is not possible in higher-dimensions. A better approach to finding outliers is to consider the distance of each point to some central location. Data points that are unreasonably far away are considered outliers and are dealt with.

continue...


Visualizing clusters of stocks

October 14th, 2012

One troubling aspect of an estimated covariance matrix is that it always overestimates the true covariance. For example, if two random variables are independent the covariance estimate for the two variables is always non-zero. It will converge to 0, yes, but it may take a really long time.

What's worse is that the covariance matrix does not understand causality. Consider the certainly common situation below:

continue...


Twitter Pyschopathy

October 08th, 2012

Released earlier was the research paper about predicting psychopathy using Twitter behaviour. Read the paper here.

continue...


Sampling from a Conditional Markov Chain

September 15th, 2012

My last project involving the artificial creation of "human-generated" passwords required me to sample from a Markov Chain. This is not very difficult, and I'll outline the sampling algorithm below. For the setup, suppose you have a transition probability matrix $M$ and an initial probability vector $\mathbf{v}$. The element $(i,j)$ of $M$ is the probability of the next state being $j$ given that the current state is $i$. The initial probability vector element $i$ is the probability that the first state is $i$. If you have these quantities, then to sample from a realized Markov process is simple:

continue...


Least Squares Regression with L1 Penalty

July 31th, 2012

I want to discuss, and exhibit, a really cool idea in machine learning, optimization and statistics. It's a simple idea: adding a constraint to an optimization problem, specifically a constraint on the sum, can have huge impacts on your interpretation, robustness and sanity. I must first introduce the family of functions we will be discussing.

The family of L-norm penalty functions, $L_p:R^d \rightarrow R$, is defined: $$ L_p( x ) = || x ||_p = \left( \sum_{i=1}^d |x_i|^p \right) ^{1/p} \;\: p>0 $$ For $p=2$, this is the familar Euclidean distance. The most often used in machine learning literature are the

continue...


Kernelized and Supervised Principle Component Analysis

July 13th, 2012

Sorry the title is a bit of a mouthful. Everyone in statistics has heard of Principle Components Analysis ( PCA ). The idea is so simple, and a personal favourite of mine, so I'll detail it here.

continue...


Predicting Psychopathy using Twitter Data

July 03th, 2012

The goal of this Kaggle contest was to predict an individuals psychopathic rating using information from their Twitter profile. I was given the already processed data and psychopathic scores. This was the first Kaggle competition I entered, and certainly not the last! If you'll excuse me, I must begin my technical remarks on my solution:

continue...


Data Science FAQ

July 02th, 2012

What is data science? What is an example of a data set? What are some of the goals of data science? What are some examples of data science in action? continue...


(All Blog Articles).filter( Coding )

lifelines: survival analysis in Python

December 19th, 2013

The lifelines library provides a powerful tool to data analysts and statisticians looking for methods to solve a common problem:

How do I predict durations?

This question seems very vague and abstract, but thats only because we can be so general in this space. Some more specific questions lifelines will help you solve are:

continue...


An algorithm to sort "Top" Comments

March 10th, 2013

Consider ratings on online products: how often do you trust an average 5-star rating if there is only 1 reviewer? 2 reviewers? 3 reviewers? We implicitly understand that with such few reviewers that the average rating is not a good reflection of the true value of the product.

This has created flaws in how we sort items. Many people have realized that sorting online search results by their rating, whether the objects be books, videos, or online comments, return poor results.

continue...


How to solve the Price is Right's Showdown

February 05th, 2013

Preface: This example is a (greatly modified) excerpt from the book Probabilistic Programming and Bayesian Methods for Hackers in Python, currently being developed on Github ;)

How to solve* the Showdown on the Price is Right

*I use the term loosely and irresponsibly.

It is incredibly surprising how wild some bids can be on The Price is Right's final game, The Showcase. If you are unfamiliar with how it is played (really?), here's a quick synopsis:

continue...


Kaggle Data Science Solution: Predicting US Census Return Rates

November 01th, 2012

The past month two classmates and I have been attacking a new Kaggle contest, Predicting US Census mail return rates. Basically, we were given large amounts of data about block groups, the second smallest unit of division in the US census, and asked to predict what fraction of individuals from the block group would mail back their 2010 census form.

continue...


Visualizing clusters of stocks

October 14th, 2012

One troubling aspect of an estimated covariance matrix is that it always overestimates the true covariance. For example, if two random variables are independent the covariance estimate for the two variables is always non-zero. It will converge to 0, yes, but it may take a really long time.

What's worse is that the covariance matrix does not understand causality. Consider the certainly common situation below:

continue...


UWaterloo Subway Map

September 22th, 2012

I think my thing with subway maps is getting weird. I just created a fictional University of Waterloo subway map using my subway.js library.

continue...


Modeling password creation

September 14th, 2012

Creating a password is an embarrassingly difficult task. A password needs to be both memorable and unique enough not to be guessed. The former criterion prevents using randomly generated passwords (try remembering 9st6Uqfe4Z for Gmail, rAEOZmePfT for Facebook, etc.), and the latter is the reason why passwords exist in the first place. So the task falls on humans to create their own passwords and carefully balance these two criteria. This has been, and still is, a bad idea.

continue...


Eurotrip & Python

August 13th, 2012

Later this month, my lovely girlfriend and I are travelling to Amsterdam, Berlin and Kiel. The first half of the trip we will be exploring the tourist and nontourist areas of Amsterdam and Berlin. I'm very excited as I get to spend time drinking and relaxing with my girlfriend. But then...

continue...


Turn your Android phone into a SMS-based Command Line

August 11th, 2012

One of my biggest pet peeves is not having my phone with me. This often occurs if the phone is charging and I need to leave, or I have forgotten it somewhere, or it is lost, or etc. I've created a partial solution.

continue...


Subway.js

July 17th, 2012

The javascript code that creates and controls the subway map above is available on GitHub. You can build your own using the pretty self-explanatory code + README document. Imagine using the code in a school project or advertising...

continue...


Python Android Scripts

July 05th, 2012

I am having a blast messing around with my new Android phone. It has Python! Currently I am playing with the sensors on the phone. Built-in is a light sensor, accelerometer, and an

continue...


Predicting Psychopathy using Twitter Data

July 03th, 2012

The goal of this Kaggle contest was to predict an individuals psychopathic rating using information from their Twitter profile. I was given the already processed data and psychopathic scores. This was the first Kaggle competition I entered, and certainly not the last! If you'll excuse me, I must begin my technical remarks on my solution:

continue...


(All Blog Articles).filter( Awesome Stuff )

DataOrigami Launch

June 24th, 2014

I'm proud to announce my latest project, dataorigami.net! Why are you still here, go check it out!

continue...


Videos about the Bayesian Methods for Hackers project

August 25th, 2013

  1. New York Tech Meetup, July 2013: This one is about 2/3 the way through, under the header "Hack of the month"

    Available via MLB Media player
  2. PyData Boston, July 2013: Slides available here

    Video available here.
continue...


Warrior Dash 2013

August 03th, 2013

Warrior dash data, just like last year: continue...


The Next Steps

June 16th, 2013

June has been an exciting month. The opensource book Bayesian Methods for Hackers I am working on blew up earlier this month, propelling it into Github's stratosphere. This is both a good and bad thing: good as it exposes more people to the project, hence more collaborators; bad because it is showing off an incomplete project -- a large fear is that advanced data specialists disparage in favour of more mature works the work to beginner dataists.

continue...


NSA Honeypot

June 08th, 2013

Let's perform an experiment.

continue...


21st Century Problems

May 16th, 2013

The technological challenges, and achievements, of the 20th century brought society enormous progress. Technologies like nuclear power, airplanes & automobiles, the digital computer, radio, internet and imaging technologies to name only a handful. Each of these technologies had disrupted the system, and each can be argued to be Black Swans (à la Nassim Taleb). In fact, for each technology, one could find a company killed by it, and a company that made its billions from it.

continue...


Cover for Bayesian Methods for Hackers

March 25th, 2013

The very kind Stef Gibson created an amazing cover for my open source book Bayesian Methods for Hackers. View it below:

continue...


My favourite part of The Extended Phenotype

February 02th, 2013

To quote directly from the book, by Richard Dawkins:

continue...


Interior Design with Machine Learning

January 04th, 2013

While designing my new apartment, I found a very cool use of machine learning. Yes, that's right, you can use machine learning in interior design. As crazy as it sounds, it is completely legitimate.

continue...


A more sensible omnivore.

November 17th, 2012

My girlfriend, who is a vegetarian, and I often discuss the merits and dismerits of being a vegetarian. Though I am not a vegetarian (though I did experiment with veganism and holistic diets during some One Week Ofs), very much agree that eating as much meat as we do is not optimal.

Producing an ounce of meat requires a surprising amount of energy, whereas it's return energy is very small. We really only eat meat for its taste. It is strange how often we, the human omnivores, require meat in a meal, less it's not a real meal (and we do this three times a day). And unfortunately, a whole culture eating this way is not sustainable.

I have often thought about a life without meat,

continue...


UWaterloo Subway Map

September 22th, 2012

I think my thing with subway maps is getting weird. I just created a fictional University of Waterloo subway map using my subway.js library.

continue...


Modeling password creation

September 14th, 2012

Creating a password is an embarrassingly difficult task. A password needs to be both memorable and unique enough not to be guessed. The former criterion prevents using randomly generated passwords (try remembering 9st6Uqfe4Z for Gmail, rAEOZmePfT for Facebook, etc.), and the latter is the reason why passwords exist in the first place. So the task falls on humans to create their own passwords and carefully balance these two criteria. This has been, and still is, a bad idea.

continue...


Eurotrip & Python

August 13th, 2012

Later this month, my lovely girlfriend and I are travelling to Amsterdam, Berlin and Kiel. The first half of the trip we will be exploring the tourist and nontourist areas of Amsterdam and Berlin. I'm very excited as I get to spend time drinking and relaxing with my girlfriend. But then...

continue...


Warrior Dash Data

July 25th, 2012

Last Sunday I competed in a pretty epic competition: The Warrior Dash. It's 5k of, well honestly, it's 5k of mostly hills and trail running. Plus spread throughout are some pretty fun obstacles. With only five training workouts un...

continue...


Subway.js

July 17th, 2012

The javascript code that creates and controls the subway map above is available on GitHub. You can build your own using the pretty self-explanatory code + README document. Imagine using the code in a school project or advertising...

continue...


CamDP++

July 03th, 2012

Camdp.com is my latest attempt to digitize myself. I tried to map the subway lines to mimic my life and work, with each subway line representing a train of thought. I hope you enjoy the continue...