Informaniac

London Machine Learning Meetup ... and joining a startup.

2011-12-06T14:47:00.000Z

Three months ago I decided to end my employment at Microsoft. I had a great time, met loads of interesting people and will definitely miss being in the Cambridge research lab (as well as the occasional trip to Seattle).

Next up I am joining a startup company called Rangespan. I met the founders of Rangespan at Silicon Milkroundabout in April this year. When I got talking to them it was immediately obvious there was a hell of a lot of machine learning to be done there.

Rangespan is essentially an e-commerce platform which is organizing a marketplace for suppliers to sell products to big retailers. On one hand Rangespan is trying to build the biggest catalog in the world. We're doing some by fusing many different information sources (supplier feeds, manufacturer feeds, crowdsourced data, crawled data). The three big learning problems in this space are:

Matching: out of millions of product descriptions (semi-structured & textual), how do you recognize which descriptions talk about the same product? Record linkage is the keyword here, but making it work at large scale and under very small precision and recall margins is a challenge.
Reconcilliation: when you have 100 different descriptions of a product, and you want to construct the best possible description of the product, how do you do that? I think the speech recognition and machine translation community has a few neat tricks up their sleeve to be applied here: in the abstract if we think of each of the 100 descriptions as the output of a noisy channel with the unknown ground truth description as the input, the challenge is to invent a prior and model for the noisy channel. Machine learning baby!
Information extraction: the data we are gathering is only semi-structured and most often marketing text. The question now becomes: how do we figure out form a USB stick description that the product has a "4GB" capacity. How do we figure out that "4GB" is the same as "four gigabytes" etc etc. There's loads of great work on information extraction which we can build on; the good news is that our domain is restricted (physical goods) the bad news is that the domain is quite large (1000's of categories, 1000's of attributes).

Besides the catalog, Rangespan is also building an order pipeline component. One crucial component of that pipeline is the system that assigns retailer's orders to suppliers. The idea here is that for each product we have a pretty good view of the supply curve (what suppliers sells how many items at what price). We also have a pretty good view of the demand curve: by aggregating many different retailers we can predict what the demand for a product will be. This allows us to make very quantitative decisions about how to choose the price for that product to optimize metrics like user experience etc. In this area a mix of statistics (time series analysis), decision theory, econometrics and optimization are crucial ingredients ... together with a ton of data ofcourse.

If this all sounds like music to your ears, then let us know. We're hiring!

Joining a startup also meant I am now working in London. One of the coolest things I discovered about being in London is the great number of meetups people are organizing. From MongoDB office hours (thank you for all the help 10gen!) to the Hadoop and Big Data meetups. Although big data is crucial at Rangespan, we think clever algorithms (as in machine learning) are as crucial to building successful insights from data. As such we are kicking off the Machine Learning Meetup as of January 2012. We'll put some fun talks together with the London machine learning community and probably do some study groups on the Stanford online learning courses.

If you live closeby and haven't yet signed up, you can find all meetup details here.

Who Killed Prolog

2011-08-29T09:13:00.001+01:00

Via HackerNews comes the article "Who Killed Prolog". The article wonders why logic programming languages have fallen behind object-oriented, imperative and functional programming languages (my favourite functional programming language F# has just entered the TIOBE programming languages top-20).

The hypothesis of the article is that when a Japanse research project called the fifth generation computer system was ended, Prolog, it's main programming language went down with it.

This reminded me of my undergraduate class in declarative languages in 2003. It started with our professor saying that there is a big cover up in the computer industry: "NASA, Microsoft, Google, HP and many other companies are using Prolog in their core products but they don't want to admit it." Instant classic!

PQL–A Probabilistic Query Language

2011-05-12T13:05:00.000+01:00

At MSR and Bing, when we do machine learning on smaller datasets (say anything below 100GB) we often use relational databases and SQL. Throw in a little bit of Excel and R and you’ve got yourself a very powerful platform for exploratory data analysis.

After the exploratory phase, we often build statistical models (adPredictor, TrueSkill, Matchbox, …) to discover more complex structures in the data. Infer.Net helps us prototype these graphical models, but unfortunately it forces you to work in a mode where you first create a binary that performs inference, suck out all data to your machine, run inference locally and then write all inference results back to the DB. My local machine is way slower than the machines which run our DB or our local compute cluster so ideally I’d like to have a platform which computes “close” to the data.

The Probabilistic Query Language (or PQL) is a language/tool which I designed two years ago, during an internship with Ralf Herbrich and Thore Graepel, where we had the following goals in mind:

Allow for rapid prototyping of graphical models in a relational environment
The focus should be on specifying models, not algorithms
It should enable large scale execution and bring the computation to the data, rather than the data to the computation

Using SQL Server, DryadLinq (Map-Reduce for .NET) and Infer.Net I built a prototype of PQL and tested it on some frequently used models at Microsoft. In this post I want to introduce the PQL language and give a few examples of graphical models in PQL.

Let’s start with a very simple example where we have a DB with a table containing people’s info and a table with records describing doctor visits for those people. Assume the following relational schema

We assume that people have an unknown weight and when they go to the doctor, she measures this weight. Depending on the time of day (after a heavy lunch), this estimate could be off a bit. A statistical model to capture these assumption is to introduce a random variable for the weight for each person in the People table, put a prior on this variable and connect it with the observations in the DrVisits table. So how do we write such a model in PQL?

PQL is very much like SQL but with two extra keywords: AUGMENT and FACTOR. AUGMENT allows us to add random variables to the DB schema. In the example above we would write

People = AUGMENT DB.People ADD weight FLOAT

This essentially defines a “plate” in graphical model speak: for each row in the People table, a random variable over the real numbers called weight is defined.

The FACTOR keyword in PQL allows to introduce factors between random variables as well as any other variables in the DB schema. FACTOR follows the relational SQL syntax to specify exactly how to connect variables. To specify a normal prior on the weight variable we could write

FACTOR Normal(p.weight | 75.0,25.0) FROM People p

This introduces a normal factor for each row in the People table (the FROM People p part). The final component of our program connects the random variable with observations. In this case, we use the familiar SQL JOIN syntax to specify how to connect rows from the People table to the rows in the DrVisits table. In PQL we write

FACTOR Normal(v.weight | p.weight, 1.0)
FROM People p
JOIN DrVisit v ON p.id = v.personid

Except for the first line this is exactly SQL; instead of doing a query, the FACTOR statement describes the “probabilistic augmentation” of the DB schema”.

For the example above, this is it, the PQL program contains five lines of code and can be sent to the DB. It will run inference by performing EP or variational Bayesian inference. The inference itself can be run either within the database (this was implemented by Tina Palla who was an intern with us) or on the DryadLinq cluster.

Another example of PQL is the program to describe the TrueSkill ranking system. In this example we assume two-player games stored using a table of players (called Players) and a table of game outcomes (called PlayerGames). Each game played generates two rows in the PlayerGames table: one for the winner and the loser (with a score) column specifying who is the winner and who is the loser. The PQL program for TrueSkill is written below

Players = AUGMENT DB.Players ADD skill FLOAT;
PlayerGames = AUGMENT DB.PlayerGames ADD performance FLOAT;

FACTOR Normal(p.skill | 25.0, 20.0) FROM Players p;

FACTOR Normal(pg.performance | p.skill, 0.1)
FROM PlayerGames pg
JOIN Players p ON pg.player_id = p.player_id;

FACTOR IsGreater(pgb.performance, pga.performance)
   FROM PlayerGames pga
   JOIN PlayerGames pgb ON pga.game_id = pgb.game_id
   WHERE pga.player_id < pgb.player_id AND pga.score = 0;

FACTOR IsGreater(pga.performance, pgb.performance)
   FROM PlayerGames pga
   JOIN PlayerGames pgb ON pga.game_id = pgb.game_id
   WHERE pga.player_id < pgb.player_id AND pga.score = 2;

There are a lot of features in PQL I haven’t covered in this blog post (like using random variables in a WHERE clause to create mixture models) but I wanted to give you a flavour of what we’ve been working on so far.

While working on PQL I learned a lot about the state of the art in probabilistic databases and statistical relational learning. I think compared to this academic work, PQL does not add many theoretical contributions; our goal is to design a tool which takes statistical relational learning out of the laboratory into the hands of data mining practicioners.

Math.Net Numerics

2011-05-01T20:23:00.001+01:00

I’ve been a fan of doing numerical computation on the .NET platform for a very long time. This interest landed me an internship at Microsoft Research with Don Syme’s team in 2007 where we investigated F# suitability for scientific computing. After the internship, I joined the open source community helping out with writing a kick-ass numerical library for the .NET platform.

Today, I am quite proud to announce that we are releasing the final beta of our open source project: Math.Net Numerics. Moreover, with this announcement, we are also kicking off a competition to find the fastest implementation of matrix multiplication in purely managed code. The winner of this competition will receive 1500$ and we will integrate his code into our open source codebase. I’m excited to see some creative coding in the next few weeks!

BBC 4 podcasts

2011-04-26T09:55:00.001+01:00

I just discovered some really good podcasts from BBC 4 which I think some people here might enjoy.

A Brief History of Mathematics: a discussion about some great mathematicians …
In Our Time: very general, one-hour discussions with a few experts. I really enjoyed the episode on “Random & Pseudorandom” from January 13.

ggplot2 and Subway

2011-04-20T08:17:00.001+01:00

The following article caught my eye a few weeks ago: Subway Set to Overtake McD's in Omnipresence. As I am trying to learn a little bit of ggplot2 (and loving it so far!) I thought it would be fun to try and create some visuals to go with this claim.

I used one of Microsoft’s restaurant datasets and do a simple substring match on “subway”, returning the latitude and longitude. Using the following lines of ggplot and R code

states <- data.frame(map("state", plot=FALSE)[c("x","y")])
colnames(states) <- c("Lon","Lat")
ggplot(states, aes(x=Lon, y=Lat)) + geom_path() 
                + geom_point(alpha=0.6,size=0.3,data=subway)

we get a cool picture showing all of the metropolitan areas of the United States.

If you click on the image to zoom in you will be able to discern major highways as well. Subway is literally everywhere.

ECML–PKDD 2010 Highlights

2010-10-12T00:30:00.001+01:00

The city of Barcelona just hosted ECML/PKDD this year and I had the opportunity to go down and check out the latest and greatest mostly from the European machine learning community. My personal highlights

The conference for me started with a good tutorial by Francis Bach and Guillaume Obozinsky. They gave an overview of sparsity: in particular various different methods using l1 regularization to induce sparsity.

The first invited speaker was Hod Lipson from Cornell (and as far as I know one of the few people in our field who has given a TED talk). The main portion of Hod’s talk was about his work on symbolic regression. The idea is the following: consider the following dataset

We can apply our favourite regression method, say a spline, to these points and perform accurate interpolation, perhaps even some extrapolation if we chose the right model. The regression function would not give us much insight into why data could be looking like this? In symbolic regression, the idea is that we try to come up with a symbolic formula which interpolates the data. In the picture above, the formula that generated the data was EXP(-x)*SIN(PI()*x)+RANDBETWEEN(-0.001,0.001) (in Excel). Hod and his graduate students have built a very cool (and free!) app called Eureqa which uses a genetic programming methodology to find a good symbolic expression for a specific dataset. Hod showed us how his software can recover the Hamiltonian and Lagrangian from the measurements of a double pendulum. Absolutely amazing!

Another noteworthy invited speaker was Jurgen Schmidhuber. He tried to convince us that we need to extend the reinforcement learning paradigm. The idea would be that instead of an agent trying to optimize the amount of long term reward he gets from a teacher, he would also try to collect “internal reward”. The internal reward is defined as follows: as the agent learns, he is building a better model of the world. Another way to look at this learning is that the agent just knows how to “compress” better. The reduction in representation he gets from learning from a particular impression is what Jurgen calls the “internal reward”. In other words, it is the difference between the number of bits needed to represent your internal model before and after an impression.

E.g. you listen to a new catchy son: Jurgen says that you think it’s catchy because you’ve never heard anything like this before, it is surprising and hence helps you learn a great deal. This in turn means you’ve just upgraded the “compression algorithm” in your brain and the amount of improvement is now reflected in you experiencing “internal reward”. Listening to a song you’ve heard a million times before doesn’t help compressing at all; hence, no internal reward.

I really like the idea about this internal reward a lot, and as far as I understand it would be very easy to test. Unfortunately, I did not see any convincing experiments so allow me to be sceptical …

The main conference was cool and I’ve met some interesting people working on things like probabilistic logic, a topic I desperately need to learn more about. Gjergji gave a talk about our work on crowdsourcing (more details in a separate post). Some things I marked for looking into are:

Sebastian Riedel, Limin Yao and Andrew McCallum – “Modeling Relations and Their Mentions Without Labeled Text”: this paper is about how to improve information extraction methods which bootstrap from existing knowledge bases using constraint driven learning techniques.
Wanner Meert, Nima Taghipour & Hendrik Blockeel – “First Order Bayes Ball”: a paper on how to use the Bayes ball algorithm to figure out which nodes not to ground before running lifted inference.
Daniel Hernández-Lobato, José Miguel Hernández Lobato, Thibault Helleputte, Pierre Dupont – “Expectation Propagation for Bayesian Multi-task Feature Selection”: a paper on how to run EP for spike and slab models.
Edith Law, Burr Settles, and Tom Mitchell – “Learning to Tag from Open Vocabulary Labels”: a nice paper on how to deal with tags: they use topic models to do dimensionality reduction on free text tags and then use that in a maximum entropy predictor to tag new music.

I enjoyed most of the industry day as well: I found it quite amusing that the Microsoft folks essentially gave all Bing secrets away in one afternoon: Rakesh Agarwal mentioned the secret sauce behind Bing’s ranker (neural net) whereas Thore Graepel explained the magic behind the advertisements selection mechanism (probit regression). Videos of these talks should be on videolectures.net soon.

One last rant: the proceedings are published by Springer who ask me to pay for the proceedings?!?! I’m still trying to figure out what value they’ve added to our camera-ready we sent them a few months ago …

From Undirected Grad to Informaniac

2010-09-14T10:22:00.001+01:00

What drives a man to change the name of his blog? A trademark dispute? A mid-life crisis? None of those actually!

After three amazing years, I am exchanging the amazing machine learning group for an exciting new adventure with Microsoft FUSE Labs. As I am writing this, my laptop is crunching away at the last few experiments to be included in my thesis while a printed version of my thesis text is awaiting final editing.

It has been an interesting few months as I was debating moving into a post doc or evaluating all the amazing opportunities that were available in industry: in the end I decided to join FUSE Labs as an applied researcher. FUSE Labs is an incubation lab at Microsoft that sits in between Microsoft Research and the product groups. My new job allows me to collaborate with people (in or outside of Microsoft) on research while giving me the freedom to also spend time building working prototypes and demo’s. As far as I am concerned: the perfect mix of science and engineering.

Although I will soon be a graduate student no more, I don’t want this blog to die but rather take it to the next level. The foreseeable future will involve more experiments on machine learning, data mining and information processing and I should be able to report much of this to everyone who cares to listen!

welcome to www.informaniac.net and stay tuned …

Rebooting the CS Publication Process

2010-06-22T07:10:00.001+01:00

Dan Wallach makes suggestions for revolutionizing the CS publication process in this 13 page report. I really like this stuff and can only hope things start moving sooner rather than later in this area.

On the time of reviewing, a recent paper I really enjoyed is Novel Tools To Streamline the Conference Review Process: Experiences from SIGKDD'09 by a Bristol/MSR collaboration. For me the most interesting part of the paper was a probabilistic graphical model which collaboratively learns how to calibrate reviewers. Calibration here means that we’d like to understand how different reviewers have different thresholds for giving a paper 1/2/3/4/5 star reviews. The generative model proposed in the paper can easily be implemented in Infer.NET and although it is perhaps to early to make decisions based on the method, it could certainly help PC’s in making their decisions.

Microsoft Research PhD Scholarships

2010-04-24T10:48:00.001+01:00

A new round of Microsoft Research PhD scholarships is being organized. I’ve enjoyed being on the scholarship for the past two years: it’s been a great opportunity to meet new researchers at Microsoft and other students at the PhD event organized by MSR Cambridge.

For all you upcoming machine learning rock-stars out there: talk to your advisors, they will have to apply for you but you can probably help them a bit!

Popularizing Machine Learning

2010-04-08T23:16:00.001+01:00

Three weeks ago I gave a presentation on probabilistic modelling to an audience of data mining practitioners. These people know about machine learning, they use it every day, but their main concern is to analyze data: real data!

The experience taught me a valuable lesson which I hadn’t come across by interacting with the academic community: Probabilistic models are hard. Even for people that are very close to the machine learning community (data mining), probabilistic models are a very different (new?) way of thinking.

The whole idea of building a generative story for your data and then using Bayes rule to “invert” the model given some dataset has become second nature to me. Nonetheless, I (we?) shouldn’t forget that it took statistics a long time to think about modelling in this sense. Hence I now understand realize that for outsiders the framework of probabilistic modelling is a highly non-trivial concept to grasp.

In this context I am obliged to share a blog post by Jeff Moser. I have never seen such a great explanation of a non-trivial probabilistic model that is deployed in very large scale on XBox Live: “Computing Your Skill”, a description of the TrueSkill ranking model. Very very well done Jeff!

Machine Learning Summer School Video’s Online

2009-11-02T13:24:00.001Z

For the people who missed the Machine Learning Summer School here in Cambridge this year, the video’s are now available at videolectures.net! My personal favorites: David MacKay’s Information Theory, David Blei’s Topic Models, Iain Murray’s Markov Chain Monte Carlo and Tom Minka’s Approximate Inference. Enjoy …

Statistics Fail

2009-10-19T09:23:00.000+01:00

From (probably) the dumbest man on earth [link].

The Elements of Statistical Learning

2009-10-14T22:09:00.001+01:00

The Elements of Statistical Learning is an absolute classic for anyone wanting to do statistics/machine learning/data mining. I read that the second edition was out and debating whether I should spend the money on this new edition. Via John Cook I learned that the book is out on pdf (from their website). DOUBLE WIN: a) I’ve already paid once and get the upgrade for free, b) I know have a way to electronically search the book.

I also found out today that Koller and Friedman have just released their much anticipated book Probabilistic Graphical Models from MIT press. At a lengthy 1208 pages, this should provide enough reading for a few nights!

Is Bayesian Statistics Easier?

2009-10-11T17:26:00.002+01:00

Many people have debated the merits of Bayesian statistics versus Frequentist statistics: very recently there was this discussion in Bayesian Analysis by Gelman. It’s a fascinating discussion and I’m just learning to ins and outs of different arguments myself.

First, I want to point people to this (short) but very insightful article by Tony O’Hagan. There are many ways of looking at the difference between Bayesian and Frequentist methods and this article makes one particular (a bit philosophical) viewpoint very clear.

I’m certainly not knowledgeable enough to take a stand in this debate but one thing I do have a strong opinion about: Bayesian methods are much easier to understand! In most statistics 101 classes we are taught a bit of point estimation (e.g. estimating a mean, a variance) which I think is understandable, but then people get into hypothesis testing and suddenly have to reason about following statements: (quoting Wikipedia here): “Assuming that the null hypothesis is true, what is the probability of observing a value for the test statistic that is at least as extreme as the value that was actually observed?”. I certainly find this a really complicated notion to reason about. The Bayesian alternative would say something like: “What is the probability of generating the observed value for this particular model”. It is the same kind of statements as “What is the probability of generating a five from a fair dice”. I honestly think statistics would be a lot more understandable (and hence I think enjoyable) if we were teaching Bayesian statistics before getting into more advanced frequentist methods. I really wonder whether there are schools out there where the undergrad stats curriculum is based on the Bayesian approach?

EDIT - I fixed the link to O'Hagan's article.

Dirichlet Distributions and Entropy

2009-10-03T21:20:00.001+01:00

In between all the Netflix excitement I managed to read a paper that was mentioned by David Blei during his machine learning summer school talk: Entropy and Inference, Revisited by Ilya Nemenman, Fariel Shafee and William Bialek from NIPS 2002. This paper discusses some issues that arise when learning Dirichlet distributions. Since Dirichlet distributions are so common, I think these results should be more widely known.

[Given that I’ve been reading a lot of natural language processing papers where Dirichlet distributions are quite common, I’m surprised I haven’t run into this work before.]

First a little bit of introduction on Dirichlet distributions. The Dirichlet distribution is a “distribution over distribution”; in other words: a draw from a Dirichlet distribution is a vector of positive real numbers that sum up to one. The Dirichlet distribution is parameterized by a vector of positive real numbers which captures the mean and variance of the Dirichlet distribution. It is often very natural to work with a slightly constrained Dirichlet distribution called the symmetric Dirichlet distribution: in this case the vector of parameters to the Dirichlet are all the same number. This implies that the mean of the Dirichlet is a uniform distribution and the variance is captured by the magnitude for the vector of parameters. Let us denote with beta the parameter of the symmetric Dirichlet. Then, when \beta is small, samples from the Dirichlet will have high variance while with beta large, samples from the Dirichlet will have small variance. The plot below illustrates this idea for a Dirichlet with 1000 dimensions: the top plot has very small beta and hence a draw from this Dirichlet has only a few nonzero entries (hence high variance) while the Dirichlet with beta = 1, all entries of the sample have roughly the same magnitude (about 0.001).

Another way to approach the effect of beta is to look at the entropy of a sample from the Dirichlet distribution, denoted by S in the images below. The entropy of a Dirichlet draw is high when beta is large. More in particular, it is upper bounded by ln(D) where D is the dimensionality of the Dirichlet when beta approaches infinity and the Dirichlet distribution will approach a singular distribution at completely uniform discrete distribution. When beta approaches 0, a draw from a Dirichlet distribution approaches a delta peak on a random entry which is a distribution with entropy 1. The key problem the authors want to address is that when learning an unknown distribution, if we use a Dirichlet prior, beta pretty much fixes the allowed shapes while we might not have a good reason a priori to believe that what we want to learn is going to look like either one of these distributions.

The way the authors try to give insight into this problem is by computing the entropy of a random draw of a Dirichlet distribution. In equations, if we denote with S the entropy, it will be a random variable with distribution

Computing the full distribution is hard but the authors give a method to compute its mean and variance. The following picture shows the mean and variance of the entropy for draws of a Dirichlet distributions. A bit of notation: K is the dimensionality of the Dirichlet distribution, Xi is the mean entropy (as a function of beta) and sigma is the variance of the entropy as a function of beta.

As you can see from this plot, the entropy of Dirichlet draws is extremely peaked for even moderately large K. The authors give a detailed analysis of what this implies but the main take-away message is this: as you change beta, the entropy of the implied Dirichlet draws varies smoothly, however, because the variance of the entropy is very peaked, the a priori choice of beta almost completely fixes the entropy.

This is problematic as it means that unless our distribution is sampled almost completely, the estimate of the entropy is dominated by the choice of our prior beta. So how can we fix this? The authors suggest a scheme which I don’t completely understand but boils down to a mixture of Dirichlet distributions by specifying a prior distribution on beta as well.

This mixture idea ties in with something we did in our EMNLP 09 paper: when we were training our part-of-speech tagger we had to choose a prior for the distribution which specifies what words are generated for a particular part-of-speech tag. We know that we have part-of-speech tag classes that generate very few words (e.g. determiners, attributes, …) and a few classes that generate a lot of words (e.g. nouns, adjectives, …). At first, we chose a simple Dirichlet distribution (with fixed beta) as our prior and although the results were reasonable, we did run into the effect explained above: if we set beta to be large, we got very few states in the iHMM where each state outputs a lot of words. This is good to capture nouns and verbs but not good for other classes. Conversely, when we chose a small beta we got a lot of states in the iHMM each generating only a few words. Our next idea was to put a Gamma prior on beta; this helped a bit, but still assumed that there is only one value of beta (or one type of entropy distribution) which we want to learn. This is again unreasonable in the context of natural language. Finally, we chose to put a Dirichlet process prior on beta (with a Gamma base measure). This essentially allows different states in the iHMM to have different beta’s (but we only expect to see a few discrete beta’s).

“Entropy and Inference, Revisited” is one of those papers with a lot of intuitive explanations; hopefully it helps you make the right choice for priors in your next paper as well.

Stats Clinic

2009-09-30T11:36:00.003+01:00

We are starting a new machine learning related initiative in Cambridge: the walk-in Stats Clinic. The goal of our consulting service is to help applied researchers with their questions in statistics or machine learning. Starting October 21 from 16:30-18:00, we will be in meeting room 5 at the Centre for Mathematical Sciences every other week.

May All Your Wishes Come True

2009-09-20T17:32:00.001+01:00

I am trying to catch up with a stack of 109 papers which are on my “To Read” list. Today I read a very enjoyable paper called May all your wishes come true: A study of wishes and how to recognize them by some of my former UW-Madison friends and colleagues Andrew B. Goldberg, Nathanael Fillmore, David Andrzejewski, Zhiting Xu, Bryan Gibson and Xiaojin Zhu.

The story is as follows: in 2007, the Times Square Alliance asked people to send their wished to a Virtual Wishing Wall website with the promise to print these wishes on confetti and drop it from the sky at midnight December 31, 2007. The UW-Madison people got a hold of this corpus of wishes and did some statistical analysis.

A few highlights:

wishes follow Zipf’s law
topic wise, US people wish more for religion
topic wise, non-US people wish more for love, peace and travel
scope wise, US people wish to their country and family more frequently
scope wise, non-US people wish to the world more frequently

After the statistical analysis, the authors wanted to come up with a classifier that could detect wishes. Their approach consists of extracting wish templates in an unsupervised fashion. The idea is quite clever (and I believe more widely applicable): people often wished for “world peace” and “I wish for world peace”, or “health and happiness” and “I wish for health and happiness”. In other words, there is quite a bit of redundancy in how the wish is expressed. By matching similar wishes, the authors extract the “redundant” part and assume it is a template.

Matching wishes can be done as follows: you create a bipartite graph and loop over all wishes, if a wish contains another wish (“I wish for world peace” contains “world peace”), you create a content node on the left with the content part (e.g. “world peace”), a template part on the right with the redundancy (e.g. “I wish for”) and you connect these with a directed edge from the content to template node. When you’re done you loop over all template nodes and see whether any of them contain content words. If so, you introduce an edge from the template node to the content node. Finally, you score template nodes by their indegree – outdegree. I will refer you to table 4 to see that the results by this relatively simple algorithm are quite good.

The reason I believe this is more widely applicable is that we can imagine using this technique for extracting templates from web queries. People often query for facts: e.g. kids of Michael Jackson. Using the algorithm from this paper, we might be able to extract the most common templates which in turn would give us a good indication of what kind of answers search engines should be trying to answer. Just an idea …

AI Bugs

2009-09-16T22:33:00.001+01:00

I thought this was a very funny set of AI bloopers …

ACL 09 & EMNLP 09

2009-08-19T23:06:00.000+01:00

ACL-IJCNLP 2009 and EMNLP 2009 have just finished here in Singapore. As an outsider to the field I had a hard time following many talks but nonetheless enjoyed the conference. The highlight for me was the talk by Richard Sproat who wondered whether there exists a statistical test to check if a series of symbol sequences is actually a language? If this test would exist, we could use it to decide whether the set of symbols known as the Indus Valey Script is actually a language. Very fascinating stuff: I immediately bought “Lost Languages” by Andrew Robinson to learn more about the history of deciphering dead languages.

The paper had some very cool papers; the first one I really liked was Bayesian Unsupervised Word Segmentation with Nested Pitman-Yor Language Modeling by Daichi Mochihashi et al. They build on the work of Yee Whye Teh and Sharon Goldwater who showed that Kneser-Ney language modelling is really an approximate version of a hierarchical Pitman-Yor based language model (HPYLM). The HPYLM starts from a unigram model over a fixed dictionary and hence doesn’t accommodate for out of vocabulary words. Daichi et al extended the HPYLM so that the base distribution is now an character infinity-gram that is itself an HPYLM (over characters). They call this model the nested HPYLM or NPYLM. There is no need for a vocabulary of words in the NPYLM, rather, the HPYLM base distribution is a distribution over arbitrary long strings. In addition the model will perform automatic word segmentation. The results are really promising: from their paper, consider the following unsegmented English text

lastly,shepicturedtoherselfhowthissamelittlesisterofhersw
ould,intheafter-time,beherselfagrownwoman;andhowshe
wouldkeep,throughallherriperyears,thesimpleandlovingh
eartofherchildhood:andhowshewouldgatheraboutherothe
rlittlechildren,andmaketheireyesbrightandeagerwithmany
astrangetale,perhapsevenwiththedreamofwonderlandoo
ngago:andhowshewouldfeelwithalltheirsimplesorrows,an
dndapleasureinalltheirsimplejoys,rememberingherownc
hild-life,andthehappysummerdays. […]

When the NPYLM is trained on this data, the following is found

last ly , she pictured to herself how this same little sis-
ter of her s would , inthe after - time , be herself agrown woman ; and how she would keep , through allher ripery ears , the simple and loving heart of her child hood : and how she would gather about her other little children ,and make theireyes bright and eager with many a strange tale , perhaps even with the dream of wonderland of longago : and how she would feel with all their simple sorrow s , and a pleasure in all their simple joys , remember ing her own child - life , and thehappy summerday s .

A note on the implementation of Hierarchical Dirichlet Processes by Phil Blunsom et al. In this paper the authors discuss how previous approximate inference schemes to the HDP collapsed Gibbs sampler can turn out to be quite bad. In this paper they propose a more efficient and exact algorithm for a collapsed Gibbs sampler for the HDP.

A few other papers I really enjoyed:

Minimized Models for Unsupervised Part-of-Speech Tagging by Sujith Ravi et al.
Polylingual Topic Models by David Mimno et al.
Graphical Models over Multiple Strings by Markus Dreyer and Jason Eisner
Bayesian Learning of a Tree Substitution Grammar by Matt Post and Daniel Gildea

To R or not to R

2009-08-12T04:14:00.000+01:00

At the moment 90% of the research in our lab is done using Matlab. Some of us have tried Python but were dissapointed by how hard it was to get decent (read: native) numerical routines on par with Matlab. I've been developing on the .NET platform with a little bit of Java development (for Amazon's Elastic Map-Reduce) on the side. We've had a few discussions in our lab recently about switching to R for our machine learning research. A decision hasn't been made and we're wondering what the larger machine learning community thinks about this issue. Here's a list of pros and cons that I've come up with

Pros:

great support for statistical functions
great support from the statistical community
good (if not better) plotting that Matlab
reasonable fast (check out Dave's benchmarking)
free (very important!) if we want to run a job on 100 machines (e.g. in the cloud), I believe currently you need a matlab licence for each one

Cons:

pre-historic interface, doesn't compare to modern IDE's
debugging doesn't seem up to Matlab standards
not much support in machine learning community (?)
learning curve

The jury is still out on this one ... I really wonder how many machine learners out there already use R?

AIStats is coming to Europe

2009-08-07T16:28:00.001+01:00

That’s right, the conference that only happened every two years in the US is now going to be switching between the US and Europe on an annual basis. The conference website is up and running here.

Parallel Random Number Generators

2009-06-11T09:02:00.002+01:00

We recently got a paper accepted in EMNLP where we elaborate on a point that was touched upon in Mark Johnson’s “Why doesn’t EM find good HMM POS-taggers?”: if we are going to do completely unsupervised POS-tagging, how can non-parametric Bayesian methods help us? There were two parts to our paper: extending the iHMM to be able to handle a medium sized text corpus and an evaluation of the results to see how the iHMM states correspond to POS tags. I’ll blog about our findings later but one thing that came up during this research was the following: because of the size (1,000,000 datapoints) of the corpus (Wall Street Journal of Penn Treebank) we used, we wanted to parallelize the forward-filtering backward-sampling (FFBS) part of the inference. Because all the sentences are independent given the transition matrix and output parameters, we can easily run the FFBS in parallel.

One thing I started thinking about is the following: imagine I run on a machine with 4 cores and I start a thread for each core to process a chunk of the data. Since the FFBS is a sampling algorithm, each of these 4 threads needs to access a random number generator (RNG). I know of two ways to go about this:

We use one RNG and access it from the 4 threads. Since the RNG’s I use are stateful, we need to lock them when we query them from a number so it’s internal state doesn’t get messed up. Locking an RNG can incur a large overhead and easily becomes the bottleneck of the parallelization.
Use one RNG for each thread. How do we initialize them though? I use the .NET System.Random RNG which uses a time dependent random seed. I don’t think this is a good idea because of the resolution of this time dependent seed is to coarse, and my 4 threads start almost at the same time, they might all end up using the same seed. An alternative is to initialize a global RNG to produce the seeds for the thread local RNG’s.

The second alternative in (2) is what we used but it does worry me a little bit: how can I know that the streams of random numbers in different threads are going to be ‘good enough’ (whatever that means). As a non-expert on RNG’s I’d like to know whether I’m going to get into trouble with these kinds of approaches. Matlab has a way to generate 3 statistically independent streams using the same RNG with the same seed. This seems like a step in the right direction, but it doesn’t solve my quad core problem, let alone when we run our algorithm on many more cores in Amazon Elastic Map Reduce …

Any creative solutions out there?

Machine Learning Summer School Application Process Opens

2009-05-06T16:09:00.003+01:00

Just to let all of you know that the application process for the summer school has opened. More info here. The deadline for applications is June 1. The list of confirmed speakers is pretty a-ma-zing if you ask me.

Hopefully I get to meet some of you in September!

The Unreasonable Effectiveness of Data

2009-03-27T07:54:00.001Z

Alon Halevy, Peter Norvig, and Fernando Pereira (from the Google) just wrote an intriguing article called the unreasonable effectiveness of data in IEEE Intelligent Systems. They argue a few points: 1) use more data to increase the performance of our learning algorithms, don’t make your models to complex; 2) the semantic web is not the right approach, it’s too expensive to “label” the web with its semantics, we need to learn it. However for an non-parametric Bayes person this is what got me very excited:

So, follow the data. Choose a representation that can use unsupervised learning on unlabeled data, which is so much more plentiful than labeled data. Represent all the data with a nonparametric model rather than trying to summarize it with a parametric model, because with very large data sources, the data holds a lot of detail.

Machine Learning Summer School in Cambridge!

2008-12-12T16:32:00.001Z

The machine learning summer school 2009 will be organized in Cambridge (UK) from August 29 to September 10, 2009. On this website we will soon be posting the list of speakers, the application procedure and the other practical information.

See you in Cambridge!

Inference in Infinite Capacity Models

2008-10-04T22:19:00.001+01:00

Through the work we've done on nonparametric Bayesian (NPBayes) time series models, I've been thinking a lot about how we can improve inference in infinite capacity models. One observation is that we don't want to throw away all the knowledge and experience we've built up in doing deterministic inference for finite models.

Expectation propagation (EP), belief propagation (BP) and variational Bayes (VB) are three deterministic inference techniques which have proven to be useful in many different scenarios. People have tried to apply these to NPBayes with mixed success:

Minka & Ghahramani applied EP to do inference in DP mixtures; as far as I understand their work, their are a few annoyances: a) the approximation can depend heavily on the order in which one processes the data points; b) the posterior distribution ends up having a cluster centre for each data point and these centres don't necessarily (and it their experiments never) fall on top of each other. This is weird as the whole point of the DP is to make sure that there is only a small number of cluster centres. I can imagine there are other ways to apply EP to DP mixtures but so far this endeavour hasn't drastically changed the business of inference for NPBayes.
There have been a few approaches (Blei, Kurihara, ...) to apply VB to DP mixtures and related models. The inference is quite elegant and quite a few applications have shows that VB inference is competitive with Gibbs sampling. VB has advantages such as returning a lower bound on the marginal likelihood which are hard to get using sampling methods. As far as I am concerned, the disadvantage of VB is that the math can become a bit hairy.
I am not aware of any BP inference for NPBayes. I'd love to hear if anyone has tried this?

What I've been thinking about lately is something completely different. Our work on the beam sampler has shown that if one uses a slice sampler in the appropriate way, one can adaptively slice up an infinite model into a finite model and use deterministic inference methods on a finite graphical model. The beam sampler is essentially a combination of this slice sampling idea with belief propagation (more in particular, the forward-backward algorithm). The scope of this technique is broader than the iHMM though: we applied this technique to the iFHMM and one can also imagine this scheme to work on infinite state Bayesian networks (ISBN). In the ISBN context we would introduce a slice for every infinite dimensional distribution and switch between sampling the slice variables and deterministic inference in the finite Bayesian network. The disadvantage of the slice sampler is that one ends up with samples and for many applications it is not clear how to combine them.

After a suggestion by Radford Neal I also looked into a different scheme to adaptively truncate the iHMM. The algorithm is an adaptation of the embedded HMM sampling scheme for nonlinear dynamical systems. Imagine we draw the trellis for the infinite dimensional state space of an iHMM:

The horizontal ... denote that there are T time steps in the iHMM, the vertical ... denote that there are a possible infinite number of state the iHMM can be in. The grayed out nodes denote a initial state sequence assignment (we are going to sample here). Note that I haven't draw all the possible transition arrows, in general there is a nonzero transition from every node at time t-1 to time t.

The embedded HMM sampler works as follows: for each time step, we create a pool of states which we want to include in the deterministic inference which we will run later. In the image below, I denote the states in the pool by shading them with light gray. The size of this pool will be a parameter which we can choose later (in the picture below it is 2).

We can choose how to draw the pools but one must make sure that the states from the previous sample (see picture above) are certainly included in the pool; it is also desirable to not spend too much computation on selecting the pool of states.

One iteration of a sampler consists of sampling the pool states and then running the forward-filtering backward-sampling algorithm in a finite graphical model that only uses pool states. If you go through the math you will find that you'll have to slightly modify the dynamic program to make this work. I will post a short technical report with some mathematical details on my web page soon.

The embedded HMM sampler shares many of the properties of the slice sampler but differs in one major respect: with the slice sampler one has little control over how much computation one will spend on one iteration. The reason is that between iterations the size of the finite model we consider grows or shrinks according to the sampled slice variables. In the embedded HMM however, we explicitly control the size of the finite model we want to do inference over. The flip side is that if we choose the pools in the embedded HMM sampler to be small we will likely increase the mixing time of the sampler.

Nonetheless the basic idea is the same as for the beam sampler: you choose a finite subset of the NPBayes graphical model and then run any deterministic inference algorithm that will get you a sample form the finite subset.

The message I want to get across here is that if we want to do inference in infinite capacity models while at the same time leveraging a powerful deterministic inference algorithm for finite models we can do so by combining a method that truncates the infinite model (say using slice sampling or the embedded HMM sampler) and then applying the deterministic inference scheme on a finite graphical model. I am eager to play around with Infer.NET and see if it will be possible to do use this idea to automatically generate inference algorithms for infinite capacity models.

NIPS 2008 Accepted Papers Out!

2008-09-26T15:04:00.001+01:00

Hot from the presses, the full list of NIPS 2008 accepted papers are out. I quickly browsed through the papers and can say I am looking forward to these:

Cognitive Science

Analyzing human feature learning as nonparametric Bayesian inference, J. Austerweil, T. Griffiths
Depression: an RL formulation and a behavioural test, Q. Huys, j. vogelstein, P. Dayan
Modeling human function learning with Gaussian processes, T. Griffiths, C. Lucas, J. Williams, M. Kalish
Modeling the effects of memory on human online sentence processing with particle filters, R. Levy, F. Reali, T. Griffiths

Neuroscience

Characterizing neural dependencies with Poisson copula models, P. Berkes, F. Wood, J. Pillow
Dependent Dirichlet Process Spike Sorting, J. Gasthaus, F. Wood, D. Gorur, Y. Teh

Machine Learning

Gates, T. Minka, J. Winn: the next big thing in graphical models?
Non-stationary dynamic Bayesian networks, J. Robinson, A. Hartemink
Nonparametric Bayesian Learning of Switching Linear Dynamical Systems, E. Fox, E. Sudderth, M. Jordan, A. Willsky: some of which we've seen at the NPBayes 2008 workshop
The Mondrian Process, D. Roy, Y. Teh: some of which we've seen at the NPBayes 2008 workshop

Graduate School in Cambridge

2008-09-21T15:12:00.001+01:00

Someone mails me to ask what it is like to do a PhD in machine learning in Cambridge. With my first year of graduate school behind me I have a thing or two to say about the program here. So to all aspiring Cambridge graduate students: listen up!

Overall I think Cambridge is an amazing place to be. It's like Disneyland for academics. There is so much stuff going on that every day I am disappointed about which talks I had to miss because there was another one going on at the same time. There are so many machine learning people around that I haven't even met them all. The ones I meet frequently with are

Needless to say there is plenty of opportunity to talk to people about machine learning. Each group has different accents and if you're interested in applying you might want to evaluate what kind of machine learning you want to do first. If pure machine learning or neuroscience is your thing, you'd probably fit in well with David's or our group. If you are more into applications the other engineering or computer lab groups would be a better fit. If learning theory is your thing, you'll also find people in the computer lab that do this kind of stuff. If you're more into theory the statistics laboratory would probably suit you well. Finally, if you don't mind a 45 minute train ride to London you will find yourself having access to the Gatsby unit, the UCL machine learning guys and probably many others I haven't met (Imperial College, ... ?)

Life in Cambridge is good too; the colleges will provide you with a place to stay, friendly people to have dinner with, social events and tons of sports to choose from. Cambridge is also very friendly towards foreigners and I've noticed that in grad school probably more than 70% of the people are internationals.

As far as I am concerned, there are two big turn-offs in Cambridge. The first is the application process itself. The whole thing is completely outdated and you will find yourself being accepted by a professor in February but only getting official letters about it in June or so. The whole process is slow and when you get all your US offers mid April you will find yourself completely in the dark with respect to your Cambridge status. I also found funding much more fragmented than in the US; a lot of people who get funding offers a few weeks before the academic year starts (we're talking September here). The other thing is graduate level classes: Cambridge does not have graduate level classes at the level that a big American university will organize them. Given my interest in machine learning I've been to a couple of statistics classes in the part III maths program which I found to be comparable to the lower level graduate classes in the US. So my advice for anyone who hasn't taken any graduate level machine learning classes is to first go to the US for a one or two years Master program or check out the programs at UCL or Edinburgh and then apply to Cambridge.

The Infinite Hidden Markov Model

2008-07-29T22:37:00.000+01:00

I am at ICML two weeks ago I presented some of our work on the infinite hidden Markov model (also known as iHMM or HDP-HMM). Together with a result from Emily Fox, I believe we have come full circle and it is time for a little summary.

Hidden Markov models (HMM) have been the workhorse of the discrete time, discrete state time series community for over 40 years. We have seen applications in speech, robotics, natural language processing, vision, ... Sometimes, domain knowledge can be used to choose the dimensionality of the latent state space, but very frequently there is no reason to prefer one dimension over the other. Moreover, maybe we explicitly want to model the uncertainty in the dimensionality of the latent state space! Hence, variational Bayes, BIC or other model selection techniques do not apply and one option is to turn to infinite capacity models.

In 2002, Matt Beal, Zoubin Ghahramani and Carl Rasmussen introduced a first version of an infinite capacity model which they called the iHMM. Their proposal is a procedure based on a two level hierarchy of urns which generates a potentially infinite transition matrix. Although it is an extremely elegant proposal, it turned out to be pretty hard to come up with a correct and efficient sampling scheme to learn this model. The model has three parameters: one to control the number of states, one to control the sparsity of the transition matrix and one to control the self transition probability.

Then, in 2006, Yee Whye Teh, Mike Jordan, Matt Beal and Dave Blei introduced the Hierarchical Dirichlet Process (HDP). The HDP is a very natural prior for building hierarchies of clusters: in other words, cluster datapoints in different groups so that clusters are shared between groups. Although the HDP is technically a bit complex, it is theoretically well founded and in the 2006 paper a relatively efficient Gibbs sampling scheme was introduced. In the same 2006 paper, an infinite capacity hidden Markov model was built on top of the HDP. This model is very close to the original iHMM but only had two parameters: the self transition control was left out. This is unfortunate as for many applications of HMM's (changepoint detection) we know a priori that the Markov model is going to stay in the same state. Finally, this "version 2.0" of the iHMM still only used a Gibbs sampling scheme for inference. This is unfortunate as we have come to understand that Gibbs sampling can perform poorly in time series models.

Enter ICML 2008: the first iHMM related result was a paper by Emily Fox, Erik Sudderth, Michael Jordan, and Alan Willsky called "An HDP-HMM for Systems with State Persistence". In this paper, the "version 2.0" iHMM model was extended to include the self transition parameter again. As you can read in their paper, this makes a very big difference: combined with some other neat ideas they were able to present some impressive performance on speaker diarization. Next, was our (Jurgen Van Gael, Yunus Saatci, Yee Whye Teh, and Zoubin Ghahramani) paper called "Beam Sampling for the Infinite Hidden Markov Model". The main idea in our work is to use a slice sampling scheme to adaptively truncate the infinite model to a finite model. This then allows us to run a dynamic program and resample the whole state sequence at once. Although we've only presented the beam sampler in the context of the iHMM, the technique is applicable to most nonparametric constructions I know of. One thing that I hope will happen is that someone will try to use the slice sampling technique to cut up nonparametric models into finite models, and use our best inference machinery (variational, BP, EP, ...) to perform inference in the finite model. This would allow us to leverage all the knowledge we've built up for finite graphical models and use them in the nonparametric setting.

Stepping back and taking a bird's eye view on things: I think that after the four iHMM papers, I think we now have a strong platform to start using the iHMM as a building block in more complicated models. At the NPBayes workshop we've already seen some cool results by Emily who uses the iHMM to switch between different auto-regressive processes and linear dynamic systems. Another trivial extension which we've implemented is to create an IO-iHMM: condition the iHMM on a certain input sequence. Finale and I are currently experimenting with this setup for learning infinite POMDP's; more about that in a future post. I've been promised that more interesting extensions are in the making ... let's see what NIPS brings!

As I have to write up a first year report (Cambridge's idea of a thesis proposal), I have been thinking very hard about a short, self contained and easy explanation of the iHMM. A description of the model so everyone can use and implement it without having to work through the whole HDP formalism. I will definitely post the outcome on my webpage early September. At least one cool spin-off has come out of this report: based on a suggestion by Radford Neil, we've come up with a different dynamic programming based sampling scheme based on the embedded HMM. As it is more incremental work, I will probably only describe it in my first year report and this blog so stay tuned ...

The Last Lecture

2008-07-26T18:48:00.001+01:00

I had never heard of Randy Pausch before until reading this post. His "Last Lecture" is amazing ... this is a great man with an inspiring message!

NPBayes workshop at ICML

2008-07-10T10:23:00.001+01:00

Yesterday, between ICML and UAI there was the nonparametric Bayes (NPBayes) workshop organized by Yee Whye Teh, Romain Thibaux, Athanasios Kottas, Zoubin Ghahramani & Michael Jordan. The program was packed with a lot of very interesting talks which for your convenience were recorded and will be put online at videolectures.net soon.

Just after lunch, there was a panel discussion on software for NPBayes. I thought much of the discussion also applied to graphical models in general. The main contenders for general software are (with main pros and cons):

the Hierarchical Bayes Compiler by fellow blogger Hal Daume III. Pros: software is freely available, continuing development, quite a large feature set (including NPBayes components) and a group of active users to show that it actually works. Cons: the language itself is more limited than some of its contenders.
Church by Noah Goodman, Vikash Mansighka, Dan Roy, Keith Bonawitz & Josh Tenenbaum. Pros: very flexible language. Cons: no software available yet.
A proposal by Max Welling: Max and one of his students are working on a library for fast inference and are planning to add a graphical UI to design graphical models visually.
Infer.NET by Microsoft Research Cambridge. Pros: integrates with many programming languages through .NET, a great variety of inference algorithms. Cons: no free software available yet (a release is scheduled for later this year).

The workshop ended with a panel discussion on the future and prospects of NPBayes. Here are some of the questions and answers I can remember of the top of my head

David Sontag: we've seen many Markov chain algorithms and some mean field for NPBayes. What are the prospects of using different inference algorithms? More specifically, the marginal polytope has taught us that belief propagation, Kikuchi approximations, etc ... give us approximations that have a different flavour than mean field methods. Answers:

I think everyone agreed that there is a lot of room to explore these algorithms.

Myself: how should we position infinite capacity models compared to finite capacity models: is the main motivation to be able to model uncertainty in the model capacity or are there other reasons to strongly favour NPBayes? Answers:

Eric Xing: NPBayes is also interesting because you are solving one problem while for model selection you have to solve many problems at once.
David Blei: NPBayes also makes it easier to define prior distributions over combinatorial objects.

Vikash Mansighka: asked about the role of consistency of infinite capacity models: aka. how much should we care about exchangeability and such. A long discussion followed from which I just recall that the statisticians in the panel all agreed that this is crucial and one should really spend time proving these properties.

Finally, the panel was asked how they see the future of NPBayes, some answers:

Zoubin Ghahramani: believes we will see applications of NPBayes on very large problems,
Yee Whye Teh: believes we will see more interesting use of optimization in NPBayes,
Lawrence Carin: thinks we will have priors adapted to our custom applications, not just use the few building blocks (DP, IBP, ...) we have now,
David Blei: believes we will see nonparametric distributions over more complicated combinatorial distributions.

Testing Markov Chain Monte Carlo Methods

2008-07-02T14:10:00.001+01:00

The projects I was involved in this year all used Markov Chain Monte Carlo (MCMC) methods for inference. MCMC methods are nice because they are so widely applicable. However, I often find them much harder to debug than variational methods. When coding up a new MCMC algorithm I use the following "procedure" to debug my code:

Fix parameters in the model and generate a lot of data. Initialise the sampler with all hidden variables set to the values used to generate the data. Run the sampler and check that it doesn't move too much. It is crucial to generate a lot of data so there is little uncertainty in the parameters and there is little reason for the sampler to move around. This test is really to check that if the inference algorithm is working, it should recognize that it has found a solution.
Fix parameters in the model and generate a lot of data. Initialise the sampler with random hidden variables. Run the sampler and check that it discovers the parameters you used to generate the data. Again, this would work if there is enough data so there is little uncertainty in the posterior distribution of the parameters. This test is to check the search abilities of the inference algorithm.
Finally, I apply the model and algorithm to real data. At this point, I will probably dig up Bayesian Data Analysis and use more principled ways to assess convergence.

In variational methods one can check that a lower bound increases between iterations; if it doesn't, something is wrong. Are there similar kind of checks for sampling algorithms? Do people have some good suggestions for debugging MCMC methods?

Machine Learning for Bug Discovery

2008-06-30T20:44:00.001+01:00

One of the reasons I have this blog is to talk about some of my own research. I intend to give some more background on things that haven't made it into a paper, put some more experiments or references online, answer questions people have about my work, ... I hope that by putting these discussions online, I can catch the attention of Google's indexer and this information is available for anyone who might ever work on similar things.

Today we (Finale Doshi and I) want to talk about a small side project of ours. Early this year we ran into a pretty cool project at the University of Wisconsin - Madison called the Cooperative Bug Isolation (CBI) project. In a nutshell, this project aims to find software bugs by first instrumenting the source code with little probes. These probes count when certain events - such as the execution of a particular line of code - occur. The CBI software collects these probe counts, and remembers whether the program exited successfully or whether the program crashed. For example: imagine we wrote the following program:

function foo()
a = read_line()
if a < 10 then
print "smaller than 10"
a = 10 / a - a
else
print "at least 10"
return a

Although this program is completely trivial, it has a potential division by zero. The CBI software will take a piece of source code as above and add some probes: say the bold italic ones below:

function foo()
a = read_line()
log( a == 0, probe_1)
if a < 10 then
print "smaller than 10"
a = 10 / a - a
log( a == 0, probe_2)
else
print "at least 10"
log( a == 0, probe_3)
return a

Note that there is a whole science to what probes are useful and where to put them, but the main point is that each probe is a counter, which gets augmented every time its first argument is true. As we mentioned above, when a program executes,various probes get augmented and at the end of the execution, the counts are stored in a file in addition to a flag that says whether the program exited gracefully or whether it crashed. Let's suppose that foo() is called several times in a larger program. After running that program a couple of times, we might get data that looks like this:

Run	Probe 1	Probe 2	Probe 3	Exit Flag
1	0	1	2	Good
2	1	2	2	Fail
3	0	5	1	Good

The CBI project has collected thousands of traces for different open source projects. The goal now is to mine these huge datasets to discover bugs in the source code. Although there are many ways of going about it, one way is to make the following assumption: if we run a program, we are executing a sequence of complex but fairly atomic "usage patterns". For example, imagine we are executing a web browser: when we press the homepage button a series of functions gets executed (and the corresponding counters are augmented). However, when we press the back button a different (but maybe overlapping) sequence of functions will be executed. We call these sequences "usage patterns".

In this paper, some Programming Language and Machine Learning people in Madison (David Andrzejewski, Anne Mulhern, Ben Liblit, and Jerry Zhu) developed a statistical model (called DeltaLDA) based on Latent Dirichlet Allocation to learn two sets of usage patterns at the same time: one set of "good" usage patterns which both successful and failed runs use, and an extra set of "bad" usage patterns which only occur in failed runs. After learning the DeltaLDA model, one can go back and look at the bad usage patterns and see which counters are expressed. Since the counters in bad usage patters correlate with programs crashing, these could then be indicative of actual bugs in the source code. It turns out that it is a reasonable idea; read the DeltaLDA paper for details on how it performs in practice.

When we decided to work with this dataset, one obvious extension of the DeltaLDA model was to try and make the whole thing non-parametric. In the original DeltaLDA paper, one has to specify the number of usage patterns beforehand. We think this is unrealistic and allowing the number of usage patterns to adapt according to the data seems to be the right way to go. So we developed a model called the DeltaHDP which is exactly this: a non-parametric extension of DeltaLDA using the Hierarchical Dirichlet Process framework. On some of the smaller datasets which we tried, we found that the DeltaHDP behaved exactly as one would expect: it finds similar usage patterns as DeltaLDA but you don't have to specify the number of usage patterns beforehand. One other nice thing about the DeltaHDP is that the Gibbs sampler, which is fairly straightforward to implement, performs well.

Another unrealistic artifact of both the LDA/HDP type models is that the corresponding generative model does not correspond to the usage pattern story above. LDA/HDP define each run of a program to be a mixture of usage patterns while we really want each run to be an integer combination of usage patterns. The reason is that we believe that each time a usage pattern is executed, it augments the counter more or less deterministically - counters do not randomly fail to increment. In the end, we came up with a model based on the Indian Buffet Process. Check out our poster for more information on the model. It turned out the inference was a little nightmare and we never found a good sampling mechanism which could scale to very large datasets. However, the results on smaller datasets suggested that the model was OK and we got similar results as the DeltaHDP. In addition, the IBP returns more information: it can tell you exactly how many times specific usage patterns were executed whereas the DeltaHDP only returns the ratio that each usage pattern was executed.

In the end it was a fun project. We enjoyed working on this data, had a lot of fun coming up with the models and we learned a lot about non-parametric methods. Unfortunately, both Finale and I have different priorities and we think the cooperative bug isolation project deserves 100% of one's attention to make progress on using statistical models for bug isolation. However, we think CBI is a great project, and we will be more than happy to give some more background on our models and answer questions about our experiences.

The Singularity

2008-06-08T09:38:00.001+01:00

Although I consider myself a machine learning researcher, I have to say I got all excited about this field because of its relation with Artificial Intelligence. (I consider machine learning to be more about solving "small" practical problems like information retrieval, machine translation, biological data analysis ... whilst AI is the grand search for making machines actually understand the world, I consider AI more about giving machines a deeper semantic understanding of the world.

This post is about a group of enthusiasts called singularitarians whom on one hand I admire but on the other hand approach with skepticism. Singularitarians are people who believe that (soon?) there will be technological breakthrough's enabling the creation of smarter-than-human intelligence. The point in time at which this will occur is called the singularity. What I think is great about this movement is that there are singularitarians who try design architectures that make strong AI possible. This is absolutely fantastic and it is sad that there are so little opportunities in the academic world for this kind of blue sky research. The reason I am skeptical at points is that a lot of singularity talk ignores the software side of things: there is much ado about peripheral issues and little research that gives us insight into how a conscious machine should work. E.g., Ray Kurzweil (a brilliant thinker by the way!) wrote a book about how available computing power will soon match the brain's computational power but hardly gives any insight on what to do with so much hardware.

IEEE Spectrum has a special issue on the singularity with articles by both singularitarians and skeptics. A highly enjoyable read!

Gold's Theorem

2008-05-28T21:32:00.001+01:00

After seeing this amazing talk by Josh Tenenbaum on videolectures.net, I started reading up on some very cool stuff at the intersection of machine learning and cognitive science. This brought me to read on Gold's theorem and the poverty of the stimulus. Very roughly, Gold's theorem says that any learner (be it a child or a computer) cannot "learn" a language by only acquiring sentences from the language she has to learn. Some people use this theorem to make the following argument: a toddler will only hear sentences from the language she is learning, she never gets to hear "wrong" (as in not in the language) sentences. Hence, since by Gold's theorem this toddler cannot learn the language, it must be innate: language abilities must be wired into our brains in some way. Gold's Theorem and Cognitive Science, by Kent Johnson is a very enjoyable read for more background on Gold's theorem and how it applies to the question of language acquisition.

Johnson's paper mentions something that I had never thought about: according to Morgan, a child acquires language after hearing about 4 million sentences. Now think about how many sentences we have access to to train our NLP algorithms on. This is orders of magnitude more than a person ever gets to hear and yet I would say we are far from building a computer system that can manipulate language as accurate as humans. From a Bayesian perspective, this could translate into assuming children having a really good prior which they start from when learning language. If the Bayesian way is the right way to look at this question, I really wonder how humans acquire this prior: how much is wired up in our brains, how much is it influenced by our sensory system, ...?

ICML & UAI 2008 Accepted Papers

2008-05-06T14:38:00.002+01:00

The accepted papers for ICML 2008 and UAI 2008 are online!

As one of my own papers got accepted, I am preparing a post with some more background information and maybe some extra plots and pictures.

Machine Learning lecture series on videolecture.net

2008-03-06T18:23:00.001Z

Our machine learning group organizes a series called the Advanced Tutorial Lecture Series on Machine Learning where we get to see some amazing researchers talk about recent developments in Machine Learning. Karsten, a postdoc in our group has been so kind to film all lectures and slowly but surely these videos are finding their way onto videolectures.net.

Currently on videolectures.net are videos on:

Applications of Group Theory to Machine Learning by Risi Kondor; this math heavy lecture was cool in that Risi explained how tools from abstract algebra and harmonic analysis can be used in Machine Learning too,
Spectral Clustering by Arik Azran; our local spectral methods expert shared his insight into how spectral methods work.

Coming up soon is a lecture by David MacKay on error correcting codes and how they can be decoded using local message passing algorithms. David is a very good speaker and his lecture is certainly in my top 5 of excellent machine learning talks.

If pigs can whistle, then horses can fly ... or ... De Finetti's Theorem

2008-03-03T14:53:00.005Z

We talked about the concept of exchangeability a few weeks ago. I presented three urn models, two of which defined exchangeable probability distributions. The main idea I wanted to convey using the first and second urn models was that exchangeability is not just independence: urn model 2 does not look exchangeable at first sight but some simple algebra convinced us that it is.

Today I want to continue this discussion with a theorem that is strongly related to exchangeability called De Finetti's theorem. The theorem goes as follows: say we have an infinite sequence of binary random variables (say the color of the balls in our urn model) and this sequence is exchangeably, then there exists a probability distribution for such that
.
In other words, if our sequence of random variables is exchangeable, than it really is a sample from a mixture model with mixture distribution .

This kind of theorem reminds me of a quote I once heard in a complexity theory talk: if pigs can whistle, then horses can fly. What do I mean by this? Assuming that a set of random variables is exchangeably doesn't sounds like a very big assumption: e.g. if you plan to cluster something like the MNIST digit recognition dataset, there is nothing a priori that distinguishes one image from another; aka. you could assume they are exchangeable. However, once you make the exchangeability assumption, De Finetti's theoremy suddenly says that really your datapoints are part of a hierarchicaly Bayesian model. In other words: by making the relatively innocent exchangeability assumption, De Finetti's theorem imposes the graphical model structure upon you. A weak assumption implies a rather strong consequence.

There is a catch however: the theorem does not specify what kind of random variable is, nor what its distribution function is. As a matter of fact, could be an infinitely large random variable (which would lead us into the realm of nonparametric Bayesian models such as the Dirichlet Process, but that's for another time). For simple models such as urn model 2 we can compute the distribution though: turns out to be a Beta distributed random variable.

All in all, De Finetti's theorem is an interesting theorem but it is not clear to me of how much practical value it is. There are many extensions and modifications of the theorem; for more information check

Machine Learning Summer School 2008

2008-01-27T11:41:00.000Z

Perfect: the website for the next machine learning summer school is up and running. It will be organized on Porquerolles Island, right of the coast of France. The confirmed speaker list is still a work in progress but looks promising already:

Shai Ben-David (University of Waterloo) "Theoretical Foundations of Clustering"
Stephane Canu (INSA de Rouen) "Introduction to Kernel Methods"
Manuel Davy (INRIA) "Parametric and Non-parametric Bayesian Learning"
Pierre Del Moral (Universite de Bordeaux) "On the Foundations and the Applications of i-MCMC Methods"
Isabelle Guyon (ClopiNet)
Yann LeCun (New York university) "Supervised and Unsupervised Learning with Energy-Based Models"
Rich Sutton (University of Alberta) "Reinforcement Learning and Knowledge Representation"
Patrick Wolfe (Harvard University) "Overcomplete Representations with Incomplete Data: Learning Bayesian Models for Sparsity"

I'll definitely try to apply and hope for the best!

The Elastic Compute Cloud (Amazon EC2)

2008-01-19T22:35:00.000Z

Today I ran into this interesting offering from Amazon called the elastic compute cloud. The idea is that you create an image that consists of your application, libraries and data and load it up to Amazon. They will run the application for you and charge you for the computing resources that you've consumed. I was a little suprised to see how cheap it actually is: 0.10$ for every hour that you run a process that consumes not more than 1.7 GB of memory, 160 GB storage; an extra 0.10$ per gigabyte you transfer into their service and an extra 0.18$ per gigabyte you transfer out of their service.

I think this is going to be a very useful platform for machine learning research. EC2 means that large scale map-reduce isn't just for Google anymore. Although I haven't tried it myself, creating the EC2 images should be straightforward as it is based on Xen virtualization; the virtualization platform out of our very own Cambridge computer lab.
I wonder why anyone would want to spend time and money on maintaining their own cluster when there is this cheap alternative available? As soon as I get the chance, I will run an experiment on Amazon EC2 and report on the experience.

PS Data Wrangling has some good posts on how to use Amazon EC2.

Silicon Minds

2008-01-13T10:19:00.000Z

The guys at Microsoft Research announced a very exciting competition: the silicon minds challenge. The goal of the competition is to foster novel ideas in the area of game AI.

Many years ago I wrote a computer game called De Profundis where I was in charge (among other things) of the game AI. Moving on to become an AI researcher it is interesting to reminisce and draw some connections.

On one hand, the game AI field is the perfect arena to try out new ideas for AI researchers. For AI researchers working on agents, planning and human interaction (speech, NLP) I could imagine it would be extremely valueable to interact with MMORPG's (Massive Multiplayer Online Role Playing Games). I don't know whether anyone in the research community has ever done this before, but having an unlimited source of humans to interact with seems like quite the experimental setup. This also applies to virtual worlds like second life ofcourse. AI Research has contributed to the game AI field ofcourse, so let me highlight two recent projects:

The university of Alberta games group: these guys do some amazing work on several kinds of games. As far as I understand it, most of their efforst are focussed on games where the mathematics are in some sense understood: chess, poker, ... What I mean by the mathematics are understood is that with infinite computational capabilities, we would be able to solve these games. The U of A group also do some work on AI for real time strategy games (e.g. Age of Empires). A mathematical analysis of these games is much harder (if possible at all). The AI necessary for these games is much closer to what I would think of as strong AI.
The Applied Games Group at Microsoft research: the organizers of the silicon minds challenge have developed a few innovations for game AI themselves. Their machine learning approach to inferring gamer skills (know as TrueSkill) is used by the XBox Live service. They have also enhanced Forza Motorsport with a reinforcement learning agent that learns to drive from observing human drivers.

Unfortunately, the game AI field has very special requirements that prohibit the use of many innovations from the research community. First and foremost, game AI are supposed to make games more fun. More sophisticated agents do not necessarily mean more fun: one can spend a large amount of time making opponents (in first person shooters or racing games) smarter, but if that means the player always looses, he or she might not enjoy the game that much. Also, games are big business, and game engineers want to understand the behavior of their agents. It is unacceptable to release an agent out in the open which in the middle of a battle starts to act weird. Hence, game engineers often limit the intelligence of agents to (pre-historic ?!?) methods such as rule based systems and (heuristic) search because they can understand the behavior and debug it more easily. (It would be unfair to forget to give credit to the people that have applied reinforcement learning and neural networks to games; afaik mostly in the areas of racing games.) To get a rough idea about what is hot-or-not in the game AI field, take a look at AI Wisdom.

One could say, who cares what technique to use: rules and search work incredibly well! Very true. In my humble opinion, the AI/machine learning community has sometimes over-focussed on new algorithms and models and too little on building intelligent solutions. Although in fields like robotics, biology and vision, our machine learning tools have had a huge impact, I think there are many fields where the AI community does not have a good understanding on how to integrate all our tools to make a large working system. Hence, silicon minds looks like a promising challenge and I am very excited to see what people come up with.

UCI Website Revamped

2008-01-07T19:23:00.000Z

First of all, happy new 2008 to all readers!

UCI hosts a famous collection of datasets at the UCI Machine Learning Repository. Recently, they have completely updated their webpage and are starting to offer new datasets. This is a great service to the machine learning community, but I would like to see us take this one step further: we should match this repository of datasets with a repository of algorithms. This would not only allow us to compare algorithms, but also get a lot of intuition about the nature of the datasets: a well-understood algorithm that does great on - say - digit classification but performs really poorly on the Wisconsin breast cancer dataset teaches us something about the nature of the data. A recent JMLR paper* calling for more open source machine learning software, mentions a project at the university of Toronto called Delve that meant to do exactly this. Unfortunately, the project seems to be dead as of 2003 or so.

* The Need for Open Source Software in Machine Learning - Sören Sonnenburg, Mikio L. Braun, Cheng Soon Ong, Samy Bengio, Leon Bottou, Geoffrey Holmes, Yann LeCun, Klaus-Robert Müller, Fernando Pereira, Carl Edward Rasmussen, Gunnar Rätsch, Bernhard Schölkopf, Alexander Smola, Pascal Vincent, Jason Weston, Robert Williamson; Journal of Machine Learning Research; 8(Oct):2443--2466, 2007.

What is ... Exchangeability?

2007-12-22T22:49:00.000Z

Talking about exchangeability, a friend once commented that exchangeability is "too simple too understand". On one hand, it is true that the statement of exchangeability (see below) sounds somewhat trivial, I found that I had absolutely no intuition as to why it is important for machine learning. So after some reading, I present my take on the concept of exchangeability.

What is Exchangeability?

Scenario 1. Imagine we have an urn with r red balls and b blue balls. We draw 3 balls from the urn as follows: we pick a random ball, write down its color and put it back in the urn before drawing a new ball. We introduce 3 random variables: A, B, C which denote the color of the first, second and third ball. It is not hard to see that p(A=r, B=b, C=b) = p(A=b, B=r, C=b); in other words, we can exchange the values of the random variables without changing the joint probability. Intuitively, the reason we can exchange the observations is that our random variables are IID (independent and identically distributed).

Scenario 2. We again pick 3 balls from an urn with r red and b blue balls. We still pick a random ball and note its color, but we put two balls of that color back in the urn. It may not be obvious that the sequence A=r, B=b, C = b has the same probability as the sequence A=b, B=b, C=r since the individual probabilities of picking the red ball first or last are completely different: r/[r+b] when it is the first ball versus r/[r+b+2] when it is the last ball (since two blue balls were added in the mean time). Writing down the equations makes it clear that the two sequence are equi-probable

It is trivial to generalize this expression to longer sequences. Again, it doesn't matter in what order we pick the balls, the only thing that matter is how many red and how many blue balls we pick. This is reflected in the formula in the sense that denominator of the probability of a sequence only depends on how long the sequence is. The nominator part only needs to know how many balls of each color there are. In our example: it only needs to know that there is a first and second blue ball (contributing b * (b+1) to the nominator) and a first red ball (contributing a).

Scenario 3. Both examples above were exchangeable since reordering the values of the random variables didn't change the probability. Let us consider a similar setup where exchangeability does not apply anymore. We again use the urn scheme with r red balls and b blue balls. However, now when we pick a red ball we note its color and simply put it back, but when we pick a blue ball we note its color and put two back. It is easy to see that we cannot exchange the value of the random variables anymore since

while

I think the following definition of exchangeability now becomes much more intuitive; we say a set of n random variables Y is exchangeable under a distribution p iff for any permutation pi of the integers 1..n

Properties of Exchangeability

Let us now briefly discuss some consequences of exchangeability as it will allow us to see why it is such an important concept. First, we compute the marginal probability of the second draw p(B = r) under the different scenarios. Under scenario 1 this is trivial, just before the second draw the content of our urn is exactly as it was when we started: hence p(B=r) = r/(r+b). Under scenario 2, after some simple algebra we find that p(B=r) = p(A=b, B=r) + p(A=r, B=r) = r/(r+b). Now here is the exciting part: we shouldn't have done all the algebra; if we are convinced that the random variables are exchangeable under the distribution of scenario 2, we could have acted as if we were computing the marginal probability for the first draw. Formally, since p(A=b,B=r) = p(A=r, B=b) and substituting this in the expression for p(B=r), we could have marginalized out the B=b part. This property - changing the order around - is incredibly useful when computing probabilities.

More abstractly, here is one way to think of exchangeable sequences. In scenario 2, if a friend just drew a ball from the urn, didn't show it to us and put one extra ball back in the urn, this is not going to make a difference as to the probability of our next draw. However, in scenario 3 above, whether someone drew a ball before us is very important: it drastically changes the probabilities for our next draw. I think this is a very important distinction that sets exchangeable and non-exchangeable distributions appart.

Although exchangeability and IID variables look very similar they are not exactly the same. From scenario one above, it is easy to see that IID random variables are exchangeable. The converse is not true: in scenario 2, p(A=b, B=r) is not equal to p(A=b) p(B=r) and thus the random variables are not independently distributed.

Exchangeability and Machine Learning

Exchangeable distributions are very common in machine learning. The most famous modelling assumption for text processing is just exchangeability: the bag of words model. This modelling assumption states that the probability of a text document depends only on word counts and not on word order. This is exactly the same model as scenario 1 above except that instead of red and blue balls, we now have words from a fixed vocabulary. Is this a realistic assumption one may ask? It certainly is not! We don't expect natural language to be exchangeable: the probability of using the word "States" should certainly be dependent on the word in front of it (a.k.a. higher if that word is "United"). But who cares, the bag of words assumption works incredibly well ...

There are many other exchangeable distributions in common use for machine learning: the Dirichlet Process and its Chinese Restaurant Process equivalent are exchangeable distributions, the Indian Buffet Process is an exchangeable distribution on binary matrices. Non-exchangeable distribution are also common: many Markov models (e.g. Hidden Markov Models) aren't exchangeable.

I hope this little overview of exchangeability was useful. I left one improtant concept out of our discussion so far: De Finetti's theorem. This is a very important theorem that applies to exchangeable sequences and I will discuss the theorem in a future post.

Machine Learning News

2007-12-17T21:22:00.000Z

From Machine Learning (Theory); a new machine learning mailing list has been created here.

Wanted: PostDocs

2007-12-13T21:22:00.000Z

... in our very own Cambridge group. More info here.

F# and the Task Parallel Library

2007-12-07T21:17:00.000Z

In a previous post I discussed how F# asynchronous workflows can be used for parallelizing computations. More specifically, I chose to work with the standard matrix multiplication algorithm as it illustrates the point of how easy it is with F# to take some existing (embarrassingly parallelizable) code and actually parallelizing it. Although F# asynchronous workflows can be used for parallelization, they are really designed for helping with asynchronous I/O for reactive programs.

Enter the Microsoft Parallel Extenions for .NET 3.5. This is a very exciting new technology that is specifically tailored to please developers who are keen to learn how to use the quad-core machines they are sitting at. In other words, the parallel extensions are a new concurrency library which, to my best knowledge, is well suited for parallizing scientific applications. Although I haven't played around with features like PLinq, I did look a bit into the task parallel library (TPL) component of the parallel extensions. The TPL library makes our life easier by providing sophisticated algorithms for dynamic work distribution. In the following example I used the Parallel.For class to parallelize the matrix multiplication algorithm from my previous blog post.


let PFXMultiply (A: float[,]) (B: float[,]) =
let n = Array2.length1 A
let C = Array2.create n n 0.0
let RowTask i =
  for j=0 to n-1 do
  for k=0 to n-1 do
   C.[i,j] <- C.[i,j] + A.[i,k] * B.[k,j]
  ()
Parallel.For(0, (n-1), new Action(RowTask))
C

As you can see, there is not much to to it. You just create the method which you want to execute in parallel (RowTask in our case) and pass it to the Action class which creates a delegate for you and passes it along to the TPL.

Here are the results when running the parallel matrix multiply for a 1000 by 1000 matrix on my quad core 2.4GHz machine: non-parallel version: 19.2 seconds, async version: 5.6 seconds, TPL version: 5.2 seconds. Feel free to download this file to play with it yourself.

Stay tuned for more neat (machine learning) applications of the TPL.

Hello, World!

2007-12-06T19:58:00.000Z

Welcome to my blog; I am planning to post discussions on machine learning, functional programming (F#) and how it can be used in machine learning, fields related to machine learning such as numerical optimization, statistics, ...

Stay tuned.