Forever Learning

There are two types of people in this world:

1. Those who can extrapolate from incomplete data.

[ Via @professorkitteh. Original source unknown. ]

Daring Fireball quotes some interesting research findings related to what Barry Schwartz dubbed The Paradox Of Choice.

About 60% of the people stopped when we had 24 jams on display and then at the times when we had 6 different flavors of jam out on display only 40% of the people actually stopped, so more people were clearly attracted to the larger varieties of options, but then when it came down to buying, so the second thing we looked at is in what case were people more likely to buy a jar of jam.

What we found was that of the people who stopped when there were 24 different flavors of jam out on display only 3% of them actually bought a jar of jam whereas of the people who stopped when there were 6 different flavors of jam 30% of them actually bought a jar of jam.  So, if you do the math, people were actually 6 times more likely to buy a jar of jam if they had encountered 6 than if they encountered 24, so what we learned from this study was that while people were more attracted to having more options, that’s what sort of got them in the door or got them to think about jam, when it came to choosing time they were actually less likely to make a choice if they had more to choose from than if they had fewer to choose from.

A fascinating psychological effect with clear implications for display advertising, but there is a lesson here for online marketeers and analysts as well.

In this study, fewer people stopped when there was less choice, but more people actually bought something. If we were only measuring the former (i.e. attention), and not the latter (i.e. sales), we would be led to think more choice would be about 50% more effective at bringing in customers. And boy, would we be wrong!

Metrics matter; especially when you are using a system which can automatically optimize your process in order to maximize those metrics.

Don’t get yourself in a jam; remember this next time you decide to measure click acceptance instead of actual sales to drive your online marketing effort. Clickthrough rates are useful as a measure by proxy, but they can be misleading.

A few weeks ago, I showed a colleague* my little visual demo of my favorite algorithm for estimating the number Pi. His immediate response was so obvious I am almost ashamed it did not occur to me before he mentioned it.

“RTD could do that!”

Turns out, he is of course right. Although Oracle Real-Time Decisions was certainly not designed for the task, it does a pretty good job of predicting Pi, given the right inputs and some mathemagic.

To reiterate, the idea behind the original algorithm is that we throw a bunch (well actually quite a lot) of darts at a square board (uniformly distributed, of course). We then count the number of darts that land in the largest circle we can fit in this square. The ratio between the darts in the circle and the total number of darts thrown, multiplied by four happens to approximate Pi for reasons explained in an earlier post.

The key thing to understand when using RTD to implement this algorithm is that the ratio described above also represents the odds that a single dart will land in the circle. More easily put, the number of darts that land in the circle divided by the total number of darts thrown equals the chance of a dart landing in the circle. If we can predict the odds of hitting the circle we can predict Pi; and RTD is pretty good at making predictions.

The Setup.

I’ll run through the RTD setup briefly. If you’re interested in a more detailed explanation how I did this, feel free to drop me a line.

RTD can only predict the likelihoods related to choices, so we’ll need a couple of those. For this experiment, we’ll pretend we have a choice of landing the dart inside or outside the circle. We’ll then diligently record whichever of those two happened to be the case each time we throw a dart so that RTD will learn to predict how likely either outcome is.

[ You can click on the screenshots below for a closer look. ]

The "In Circle" choice

As you can see, I’ve already included the likelihood as a choice attribute to be returned to the calling application. This attribute will be populated by a model aptly named Pi.

The "Pi" model

The Pi model could hardly be simpler. It will predict the likelihood of mutually exclusive choices (hence the checkbox at the bottom of the configuration) from the choice group Choices.

Note that Pi is configured as a simple so-called Choice Model, not the more common Choice Event Model. The latter, more complex model is more frequently used in practice, because it allows RTD to predict multi-step likelihoods (customer clicked an add, then put the product in his or her shopping basket, then proceeded to checkout, then completed the payment) for positive as well as negative events (e.g. the customer actively declines the offer).

We’ll use a client application similar to the one used in the earlier Pi experiments to simulate the throwing of darts. This application will also show the predicted value of Pi. For this client to tell RTD about darts thrown and RTD to respond with the predicted value we will use a single advisor. The RTD server will generate a web service based on this configuration.

The "Get Prediction" advisor request

Each request to this advisor will tell RTD about a single dart thrown. The Dart Was In Circle boolean input parameter seems pretty self-explanatory. To process this input and feed the model we will need some simple logic.

Advisor logic

This is all that is needed to allow RTD to build a model that can predict the likelihoods for the darts landing inside or outside the circle.

[ Of course we also need so performance goal and decisions to allow the advisor request to return the two choices created, but we're not really interested in that here. As long as the request returns the In Circle choice and its Likelihood attribute we're happy. I'll leave this part of the configuration as an exercise for the reader. ]

The Result.

It takes RTD a while (about a thousand darts or so) to come up with a prediction at all. But when it does, it is pretty much spot on.

The prediction RTD makes seems to be less sensitive to fluctuations resulting from the randomized input. At times, RTD’s guess was even closer to the actual number Pi than the value calculated mathematical function I’d used in previous experiments (and of course, I couldn’t resist taking a screenshot when it was).

Results

RTD not only good for 986% ROI, but also for predicting Pi.

And this cake is no lie.

[* I forget who exactly suggested this. Either Alan, Simon or Tim. ]

It seems that my little rant against the apparent lack of scientific rigor and the use of data to analyse performance in the world of advertising is nothing new. Scientific Advertising, written in 1923 by advertising icon Claude C. Hopkins, lays out a convincing argument in favor of the use of an empirical and results-oriented approach in all marketing.

The bottom line of this argument is the same as the true bottom line for every company. It’s all about the money.

Scientific advertising is impossible without [knowing your results]. So is safe advertising. So is maximum profit.

Groping in the dark in this field has probably cost enough money to pay the national debt. That is what has filled the advertising graveyards. That is what has discouraged thousands who could profit in this field. And the dawn of knowledge is what is bringing a new day in the advertising world.

Hopkins pioneered the use of keyed coupons to track the success of different campaigns and ads. He believed that the only purpose of advertising was to sell more products and that the effects of such efforts should be measurable and those responsible be held accountable. New ideas and concepts should be tried in a small, controlled and safe setting so that their (monetary) results could be measured and analyzed.

Only when a new approach proved to be successful in a number of trails could it be trusted to be applied at larger scale. Take this passage from his autobiography My Life in Advertising.

How have I been able to win from this situation so many great successes? Simply because I made so many mistakes in a small way, and learned something from each. I made no mistake twice. Every once in a while I developed some great advertising principle. That endured.

The technology of the time allowed Hopkins et al. to try new things and make mistakes only on a per town basis. Results had to be analyzed manually and each iteration required significant effort and some investment. Still, what knowledge could be gleaned from these relatively small scale ventures proved key to Hopkins’ success in advertising.

Judging by his own accounts it never occurred to Hopkins that different ads would have different results for different towns or different people. He was simply empirically searching for the perfect ad; one town at a time. Once found, this super ad would be unleashed upon the entire nation.

In that light, Oracle Real-Time Decisions (RTD) is like the traditional scientific advertising method on steroids. Not only does it apply the concepts of empirically testing success and failing in small doses and learns from those mistakes automatically; it is also able to segment the respondents into an seemingly infinite number of sub-groups and find a super ad for each.

Computing Science has taken Scientific Advertising to the next level; and you cannot afford not to follow.

[As a side note, I think it important to realize that Scientific Advertising was written before Edward Bernays took his uncle's ideas and used them to revolutionize the field of advertising. Thanks to Hopkins's scientific and empirical approach most of the facts and results cited still hold water, but some of the explanations and conclusions he puts forward are terribly outdated. If you want to know more, I can highly recommend Adam Curtis's award-winning 2002 documentary for the BBC, The Century of Self.]

Okay. So maybe I was jumping to conclusions a little early in the game.

After I posted my own modified version of Peter Norvig‘s Sudoku Solver, Peter and I had some brief discussion about my results and conclusions. I had only compared the performance of the two algorithms based on the ninety-five difficult puzzles provided by Peter, but he was not convinced. So I set out to make a more rigorous analysis of the relative strengths of our approaches using the method for generating random puzzles included in the original code. The results were a little unexpected, but not very surprising.

Fair game.

To make this a fair competition, I made some slight modifications.

Firstly, I had to ensure that both algorithms were solving the exact same random puzzles. Otherwise one algorithm might, simply by virtue of some serious bad luck, end up with more difficult puzzles. This is especially important since Peter’s experiments showed that long execution times (difficult puzzles) are rare but have an extreme impact; a few puzzles taking more than a minute to solve.

Secondly, I modified the code so that it uses the timeit module for measuring execution times. This allowed me to measure execution times more precisely.

More pudding.

Overnight, one million random puzzles were attempted by the two competing algorithms (999.925 were actually solved). Peter’s original algorithm required an average of 0.007 seconds per puzzle (142 puzzles per second) with a maximum execution time of 91.06 seconds. For the same puzzles, my modified version required an average of 0.008 seconds per puzzle (124 puzzles per second) with a maximum execution time of merely 5.75 seconds.

Both these averages are far lower than those for the ninety-five difficult puzzles attempted earlier, but the maxima are orders of magnitude higher. This seems to indicate that most of these random puzzles are easier to solve; save for a few extreme puzzles. This is in line with Peter’s earlier findings.

Sudoku algorith execution times

The original algorithm solves these random puzzles about fourteen percent quicker on average, but the distribution of execution times is more spread out; as is evident from the much larger standard deviation and higher maximum.

Mea culpa. But not for maxima.

Based on these findings I have to admit I was wrong. My modified algorithm does not solve every Sudoku puzzle faster, as the title of my previous post implied. When solving many, randomly generated puzzles the original is slightly faster on average.

But when the task at hand involves more difficult Sudoku puzzles, or when you are operating under strict time constraints (i.e. you want more certainty about the maximum time required to solve a single puzzle), my money is still on the modified version. The exact puzzle that required the original algorithm 91.06 seconds to solve took the modified version a mere 0.0079870224 seconds. I’d say that is an improvement.

There’s a tool for every job.

When we were discussing how Peter had generated the graphs he used in his article, I remarked (tongue-in-cheek) that copying and pasting execution times into a spreadsheet sounded a lot like brute-force manual labour to me. I think his response summarizes this whole exercise for me quite well.

Yes, but sometimes a little brute force is easier than figuring out how to do an elegant solution.

It seems to me now that sometimes a little brute force is not only easier, but that it can be faster than a more elegant solution as well. Many thanks to Peter for posing questions and pushing me to dig a little deeper.

Sir, I stand corrected!

Peter Norvig‘s excellent essay Solving Every Sudoku Puzzle is a fascinating read, and I would highly recommend you read it (or at least scan it briefly) before you read the rest of this post.

Playing by the rules.

The program discussed in the article is able to solve every Sudoku puzzle by repeatedly applying two simple rules.

1. If a square has only one possible value, then eliminate that value from the square’s peers.
2. If a unit has only one possible place for a value, then put the value there.

These rules will make a lot of sense to anyone who has ever tried his or her hand at a Sudoku puzzle. In essence, they describe the most basic rules of the game. But there are puzzles that cannot be solved using these rules alone. When Peter’s program gets stuck (i.e. it cannot make any more progress based on these rules alone) it will apply a technique commonly known as ‘making an educated guess’.

As one who has dabbled in solving Sudoku’s puzzles before, I knew that Peter would probably have to resort to brute-force guesswork at some point. Some difficult puzzles simply require the human player or computer program to try different options and see if they result in a contradiction. Peter prefers to call this strategy ‘searching’, but that does not make the idea more compelling to me; or more efficient, for that matter. However, even though the puristic mathematician in me would like to solve every puzzle in a deterministic way, I have to concede that in some cases a little brute-force, applied at the right time and place, can arguably be quite elegant and actually improve performance.

I just think Peter is bringing out the Big Guns too early in the game.

When I built a Sudoku Solver some years ago, my aim was to build a program that could help a player identify possible next moves. This meant that the program should be able to give a reason for each of the values it assigned. At the time, for me, “I checked all the possible alternatives and they didn’t work” was not an acceptable explanation. So I spent most of my time searching for rules that I could use to deterministically find the solution to a puzzle.

[Like so many of my projects, I never got around to actually polishing the Sudoku UI and making the software useable to anyone but myself. Once the program was capable of solving most of the puzzles I could find, I lost interest and moved on.]

I found that I could reduce most of the rules I came up with (and rules I found in Sudoku guide books) to two simple rules.

1. If a square has only one possible value, then eliminate that value from the square’s peers.
2. If a unit has only N possible places for values d1 to dN, then those are the only options in those places.

Rule 2 for N = 2

The first rule is identical to the first rule Peter uses; and when N is equal to one, the second rule is identical to Peter’s rule number two. But this more elaborate rule also works for other values of N.

For example when N is two (see image). If there are only two places where the values one and nine are possible in a unit (the box in the lower left), then those values will have to be placed in those places (top and bottom middle column). As a consequence, even though we do not know which value goes in which place, we do know that other values (in the image six is the value to note) will not be possible, since placing them there would mean that either one or nine could not be placed in the unit at all. In the example image shown, this means we can be certain that six goes in the top left corner of the lower left box, because the only other option for six, the cell one to the right, is already occupied with either one or nine.

Wrestling the Python.

I wanted to see if my generalized rule number two could improve the (already impressive) performance of Peter’s program. I’d never worked with Python before, but that was no object. Peter’s programming and article are so clear it was relatively simple to adapt the logic to implement the generalized rule number two for the case where N = 2.

[My implementation is probably a bit crude. I'm open to suggestions. Never too old to learn.]

First, I needed to alter the assign method so it can handle multiple possible values.

def assign(values, s, d):
    """Eliminate all the other values (except those in d) from values[s] and propagate.
    Return values, except return False if a contradiction is detected."""
    other_values = values[s]
    for e in d: other_values = other_values.replace(e, '')
    if all(eliminate(values, s, d2) for d2 in other_values):
        return values
    else:
        return False

Then, I added a condition to the eliminate method that checks for instances of rule two where N = 2.

        ## (2b) If a unit u is reduced to only N places for values d1 to dN, then
        ## those are the only valid options for those places.
        ## The following logic only works for N = 2, which is good enough for many
        ## sudoku puzzles and already improves performance over the original code.
        elif len(dplaces) == 2:
            # d can only be in two places in unit; find companion number
            for e in values[dplaces[0]]:
                if e != d and e in values[dplaces[1]]:
                    # ensure the companion number can also only be in two places
                    eplaces = [s for s in u if e in values[s]]
                    if len(eplaces) == 2:
                        # these two numbers are the only options for these two places
                        if not (assign(values, dplaces[0], d+e) and assign(values, dplaces[1], d+e)):
                            return False

That’s all there was to it. The adjusted program is able to solve all the same puzzles as the original, but should resort to educated guessing less often. The question is whether my crude implementation of this generalized rule will result in better performance. It is quite possible that checking for the additional deterministic constraint requires more computations on average than the existing brute-force approach, resulting in worse performance overall (despite the fact that it results in less guesswork).

Proof of the pudding.

I tested the two versions of the program on the 95 difficult puzzles used by Peter in his article. On my old MacBook, the original program reported requiring an average time of 0.04 seconds (27 Hz) and a maximum time of 0.18 seconds to solve these puzzles. The adjusted program was just under twice as fast on average with a time of 0.02 seconds (43 Hz). The maximum time improved more dramatically and proved more than twice as fast with a maximum time of 0.07 seconds.

I interpret these results to mean that the additional rule has a more pronounced effect on the time required to solve the difficult puzzles than on simple puzzles. Difficult puzzles that required quite some guesswork before can now be solved more easily, because of the additional rule. Simple puzzles are less affected. The average thus drops as a result of the significant reduction of the maximum time.

Reducing the need for brute-force searching improved performance. Still, there are puzzles that cannot be solved using this generalized rule. I’d be interested to see if anyone can come up with any additional (or more general) rules that would eliminate the need for guesswork altogether (or alternatively, prove that this cannot be done).

Update (januari 29th): Peter Norvig has kindly allowed me to share the modified version of his program. You can preview the code and download the source here. Thanks Peter!

Update (februari 5th): Okay. So maybe I was jumping to conclusions a little early in the game. Mea culpa.

Hmmm. Pie.

In a previous post I’ve explained how we can estimate the number Pi using Monte Carlo Methods (basically throwing darts at a circle). I personally think this method is quite elegant, but it is not particularly efficient. It might take a very, very, very long time for it to converge to anything close to the actual number. Still, pretty awesome.

This week I’ve compiled a simple, interactive and more visual example using the jQuery library and SVG graphics. You can find it here. Let me know what you think.

Update (april 2nd 2011): Code for this project is now available on Github.

You might not realize it, but your brain is running some pretty wonky legacy code. Stuff that worked fine back in the day, but is not very well suited for the challenges of modern life. Let me give you an example.

Leonard Mlodinow writes in The Drunkard’s Walk:

Which is greater: the number of six-letter English words having n as their fifth letter or the number of six-letter English words ending in ing? Most people choose the group of words ending in ing. Why? Because words ending in ing are easier to think of than generic six-letter words having n as their fifth letter.

If you have no difficulty coming up with six-letter English words that have an n as their fifth letter, then you’ve probably been playing too much Words with Friends (I am certainly guilty as charged on that count). Anyway, Mlodinow continues:

But you don’t have to survey the Oxford English Dictionary—or even know how to count—to prove that guess wrong: the group of six-letter words having n as their fifth letter includes all six-letter words ending in ing.

Just like the “Linda is a bank teller” example, one answer encompasses the whole of the other answer.

[Note that Mlodinow implicitly (and correctly) assumes that there exist six-letter English words that have an n as their fifth letter but do not end in ing. Otherwise the two groups would have been equal in size.]

Mlodinow explains why we guessed wrong:

Psychologists call that type of mistake the availability bias because in reconstructing the past, we give unwarranted importance to memories that are most vivid and hence most available for retrieval.

In other words: if it’s easy to think of an example, we assume it’s pretty probable.

Good approximation heuristic for a caveman, maybe not so great for modern man. A coccyx in the brain.

In his book The Science of Fear author Daniel Gardner talks about this availability bias (he calls it the ‘example rule’ and Kahneman and Tversky called it the ‘availability heuristic’, but they all mean the same thing) in the context of (perceived) security.

But car crashed aren’t like terrorist hijackings. They aren’t covered live on CNN. They aren’t discussed endlessly by pundits. They don’t inpsire Hollywood movies and television shows. They aren’t fodder for campaigning politicians.

As a consequence of all this public attention, we have no trouble at all thinking of examples of terrorism. Conversely, we have more difficulty thinking of examples of car crashes. Our prehistoric wetware falsely intuits that the former is more likely than the latter; even when we know this to be untrue.

Caveman fears ending with a bang more than the end of the road, because bangs make better stories.

I think it’s about time for a patch. Caveman needs an upgrade. Until then, please be wary of the bugs in your brain.

[Just so you know, the word 'coccyx' is worth a whopping 4+1+4+4+3+8 = 24 points (excluding bonuses) in Words with Friends. However, as there are only two c's available in each game, you would need both c's and a joker (or two jokers and a c) in order to be able to play it for twenty points (sixteen with double jokers).]

I started a blog because I wanted to improve my writing skills; and thought I had something to say. You, as a reader can help me figure out how I am doing by rating each post (preferably after you’ve actually read it) on a five star scale.

To give you some guidance I’ve compiled a summary of how I interpret each star rating.

1. Fail.
2. tl;dr.
3. I like turtles! (meh)
4. Orly? Om nom nom!
5. Double Rainbow / Over 9000!!!1111one

Please take the time to consider how you feel about my past and future posts and use the star ratings to let me know. Thanks!

Also, feel free to come up with your own interpretation of the five star scale and share it in the comments.

I love reading. I love reading about statistics. I love reading about psychology. But most of all, I love reading quite a few books about statistics and psychology. I might just be a little weird, but statistics and psychology do make up a large part of my job.

One study that fascinates me is Extension versus intuitive reasoning: The conjunction fallacy in probability judgment by Daniel Kahneman and Amos Tversky (and I am not the only one, this study appears in many books by different authors and Kahneman was rewarded the Nobel Memorial Prize in Economics for his efforts in 2002). In this study they asked participants (among other things) the following question.

Linda is 31 years old, single, outspoken, and very bright. She majored in philosophy. As a student, she was deeply concerned with issues of discrimination and social justice, and also participated in anti-nuclear demonstrations.
Which is more probable?

1. Linda is a bank teller.
2. Linda is a bank teller and is active in the feminist movement.

If you are like the vast majority (~85%) of the participants, you feel the second option is more probable. You will also, like that same vast majority, be wrong. Wikipedia does a pretty good job explaining why this is a conjunction fallacy. How can A + B be more probable than just A (and possibly B, but perhaps not B)? Kahneman and Tversky found that this effect does not occur when the questions seem unrelated to what the participants already knew about Linda.

The perceived probability, it seems, depends on how well the answer fits in our internalized story of Linda, not logic or statistics. A good story is viewed as more likely than a poorly framed fact. This is important, if your job is helping people make decisions based on numbers and statistics.

What do you think is more likely: that you understand the implications of this study or that you understand the implications of this study because I’ve provided you with a vivid (and self-referential) example of its application?

[do you see what I did there?]