Painite teaser

It seemed like "What the heck is a Ycombinator" struck a chord with people. In retrospect, I probably should have done less rambling. So after a silence of a week, I'll get to the point. Here's a little teaser of what I've been working on over the holidays.

require 'painite'

p_es = Prob::EventSpace.new do |es| 
  es << Prob::RandVar.new("cancer") do |pdf|
    pdf["cancer = :sick"] = 0.01
    pdf["cancer = :healthy"] = 0.99
  end
  es << Prob::RandVar.new("test | cancer") do |pdf|
    pdf["test = :pos | cancer = :sick"] = 0.8
    pdf["test = :neg | cancer = :sick"] = 0.2
    pdf["test = :pos | cancer = :healthy"] = 0.096
    pdf["test = :neg | cancer = :healthy"] = 0.904
  end
end

p_es["cancer = :sick | test = :pos"] # => 0.8 * 0.01 / (0.8 * 0.01 + 0.096 * 0.99) 

It's still not quite complete, as it's harder than I expected to generalize it. The interface is still a little bit in flux, but I hope to nail it down soon.

Is preloading child tables always a good idea?

Optimization isn't something you should do too early on, but I think a little house cleaning every so often to make sure your pages aren't ridiculously slow is healthy. With any optimization task, you'd want to benchmark the results and see if there's an actual gain. The very basic tool for benchmarking is the ordinary script/performance/benchmark. The easiest to find analysis tools is the rails_analyzer gem. The last time I used rails analyzer, it wasn't that easy to use. The command line arguments seemed arcane. But its bench tool, which can benchmark controllers as opposed to just object models, is fairly easy to use.

Using the bookmarking example from before, let's say you have something like:

class SceneController < ApplicationController
  def list
    @books = Book.find_books
  end
end

class Book < ActiveRecord::Base
  def self.find_books
    find(:all, :include => [:bookmarks], 
               :conditions => ["books.created_on > ?", 6.month.ago])
  end

  def bookmarked_by?(user)
    self.bookmarks.select { |bm| bm.owner_id == user.id }.empty? ? false : true
  end
end

In the listing of books, one would display whether it's actually bookmarked by a user or not. Normally, without the :include, the listing would make repeated queries to the DB every time it displayed a book list element, since it will use bookmarked_by?(user_id) to determine if a user bookmarked the book. So instead of just 1 query, it would make n + 1 queries.

Preloading child tables isn't necessarily wise all the time. It really depends on what you intend to do with the data after you fetch it. As the Agile rails book warns, preloading all that data will take time. If you look at your log files, you'll see that it's a significant amount.

If you're only going to load a limited number of these book list elements on a single page at a time, it actually might make sense to forgo preloading of child tables, and just use a find() instead of a select.

class SceneController < ApplicationController
  def list
    @books = Book.find_books
  end
end

class Book < ActiveRecord::Base
  def self.find_books
    find(:all, :conditions => ["created_on > ?", 6.month.ago], 
         :limit => 20, :order => "created_on desc")
  end

  def bookmarked_by?(user)
    Bookmark.find(:first, 
                  :conditions => ["book_id = ? and owner_id = ?", id, user.id]) ? true : false
  end
end

And if you're going to display counts of arrays, but all means, use counter caching. It's easy to do (as long as you follow instructions!), for most situations.

Intuitively, if you want to display over a certain n number of book list elements, it makes more sense to use :include and select it. However, I wanted to point out that when you make decisions like this, you'll always want to measure the load times, because you earn what you measure.

Also, use the right number of runs. Too short number of a number of times you run a function, the more variation you'll have in your benchmarks. Let's say that you get two numbers for two different methods.

$ bench -u http://localhost:3000/method1 -r 50 -c 5
50....45....40....35....30....25....20....15....10....5....
Total time: 240.383527755737
Average time: 4.80767055511475

$ bench -u http://localhost:3000/method2 -r 50 -c 5
50....45....40....35....30....25....20....15....10....5....
Total time: 156.147093772888
Average time: 3.12294187545776

So it's obvious that method2 is better right? Well, not necessarily. While benchmarks only show averages, you'll need to pay attention to standard deviations. The bigger the standard deviation, the more runs you'll need to figure out the average load time, and the number of decimal points you can trust. That way, you can figure out whether the difference in load times is statistically significant or not.

That way, you can ascertain whether the optimization you made were worth the trouble or not. tip!

Expoential backoff, mofo!

I noticed that facebook doesn't check my blog's RSS feed at a regular interval. I hadn't blogged in a while on my other blog, and facebook stopped checking it. It was only just now that it imported 4 posts at once. It can only mean that they're doing one of two things.

1) They're so overloaded, that they import peoples' blog RSS when they get around to it, and can spare some cycles.

2) They've implemented something like Ethernet's exponential back off when contention happens on the wire.

To me, #2 makes sense. RSS is known for its bandwidth hogging nature, since readers keep pinging the feed. I wrote about adaptive polling before, and it shouldn't be too hard. Based on a recent history of when someone posts on their blog, you can make pretty good predictions as to when they're going to blog next. Therefore, you can check the blog's RSS feed based on that, rather than wasting bandwidth. An easy way is to use a Bayesian classifier to do this.

Naive Bayesian Classifier Hashed and Slashed

I know, I've been bad at posting over the course of the week, where readers would be more likely to be reading this stuff at work. But I have been busy myself too...mostly thinking about non-technical stuff.

Well, some weeks ago, I spent some time looking at Bayseian Probabilities. I learned it way back in high school, though I never gave it much thought. Then I stumbled on it again in college in my ECE courses, and nearly failed the class. And then I took it again in grad school, and though I did well enough in the class, I still felt weak in probability.

This time, when implementing a bayesian classfifier, I learned in and outs of a seemingly simple naive bayesian classifier, and I learned how to spell 'bayesian'. That 'e' after the 'y' gets me every time.

Anyway, I was looking at Paul Graham's famous a plan for spam, and I couldn't figure out where he got that last formula. Kinda mad at myself for not seeing it earlier, cuz, it really is pretty simple. Anyway, it took me a while, but I worked it out. Turns out I learned more when I implemented it...or rather, I would have learned it had I concentrated the first two times.

We know Bayes Theorem is as follows:

(1) P(a,b) = P(a|b) * P(b) = P(b|a) * P(a)

With some algebra of the above we can also derive

(2) P(a|b) = P(b|a) * P(a) / P(b)

But also note that if we take (1), and put a given 'd' behind it, it'd hold true if the probabily on the other side also had a given 'd' behind it. If you draw out the Venn Diagrams, you'll see this is true.

(3) P(a,b|d) = P(a|b,d) * P(b|d) = P(b|a,d) * P(a|d)

We also have the Total Probability Rule, which says that the total probability is made up of its parts. If you apply bayes rule, in (1), you'll see that it's true.

(4) P(b) = P(b|a) * P(a) + P(b|a') * P(a')

So this means that Baye's rule in (2) can be rewritten with (4) as:

(5) P(a|b) = P(b|a) * P(a) / (P(b|a) * P(a) + P(b|a') * P(a'))

We also need the Probability Chain Rule. It says that the joint probability of a, b, and c can be rewritten as the following due to equation (1), applied over and over again:

(6) P(a,b,c) = P(a,b|c) * P(c) = P(a|b) * P(b|c) * P(c)

And lastly, the Independence Rule, which makes the bayesian classifier naive:

(7) P(a,b) = P(a|b) * P(b) => P(a) * P(b) iff "a" indp. from "b"

Now, we can solve for what's the probability of spam given these joint probability of words, where each word is considered an orthogonal and independent dimension?

P(s|f0, f1) = P(f0, f1|s) * P(s) / 
(1)                P(f0, f1)
            = P(f0, f1|s) * P(s) / 
(4)           (P(f0, f1|s) * P(s) + P(f0, f1|s') * P(s'))
            = P(f0|f1,s) * P(f1|s) * P(s) / 
(6)           (P(f0|f1,s) * P(f1|s) * P(s) + P(f0|f1,s') * P(f1|s') * P(s')
            = P(f0|s) * P(f1|s) * P(s) / 
(6)           (P(f0|s) * P(f1|s) * P(s) + P(f0|s') * P(f1|s') * P(s')
           ~= P(f0|s)*..*P(fn|s) * P(s) / 
(7)           (P(f0|s)*..*P(fn|s) * P(s) + P(f0|s')*..*P(fn|s') * P(s'))
           ~= P(f0|s)*..*P(fn|s) / 
              (P(f0|s)*..*P(fn|s) + P(f0|s')*..*P(fn|s'))

The last step needs a little explaining. all the P(s) and P(s') drop out of the equation when we're doing a classifier, since for any piece of evidence, f0...fn, the P(s), the probability of spam occurring, is alway the same across any classification. Since P(s) is constant, and P(s') is (1 - P(s)), it is also constant. Therefore, when we are comparing the values to determine if it belong in the spam or ham category, we can get rid of constants.

The actual hard part about bayesian classifiers is how to estimate the underlying probability distribution. If you've never seen a piece of evidence in training, you're going to say the probability of it occurring is zero, which isn't correct if the evidence shows up during classification. There's various techniques for dealing with this, mostly under the term 'smoothing'. I won't describe the various techniques here, but that should be enough to get you started.