Computational Advertising class @ Stanford

Since I have decided to dabble into the problem of ad serving, I have been looking at this class at Stanford trying to get a sense of what is out there currently in the real world, and what are the lines of thought of researchers in the field. Here's the link if you are interested.

A brief detour

For those of you who might have stumbled upon my blog previously, you would probably remember me as a PhD student in Machine Learning in California. I have decided to take a detour from my PhD program for a stint as a Software Engineer. I am working in California, primarily focusing in applying Machine Learning in building high value scalable products for users, and with a goal in distributing them at a massive scale.

At the moment, I have decided to delve into the problem of Ad Serving. All of us engineers in this area are basically working on the problem of how to connect advertisers, publishers, and users in a manner that is profitable for all involved, and to do all that in an efficient manner.

How are our algorithms surviving in the stock market?

With the current high volatility of stock prices, I wonder how algorithms predicting stock prices are surviving. The ups and downs over the last few days have been pretty significant, and the robustness of algorithmic predictions, in general, is something that I am curious about. From a machine learning perspective, I am interested in knowing how such techniques are surviving in the current harsh world of stock market.

Anybody has any ideas on this matter?

Interesting TED talk on how algorithms are creeping into our lives

My post on "Prelude to postings again" has been over a month old. In the spirit of blogging, here is an interesting TED talk on how algorithms are becoming a part of our daily life. People in data mining might find this talk especially attractive.

Revisiting decomposition

This a brief revisit to the idea of problem decomposition as in one of my previous posts on dual decomposition.

If you have taken a graduate level class on Bayesian Networks, or even an undergraduate class in Artificial Intelligence, then you probably remember the famous "Alarm Problem" below as a first introduction to Bayesian Networks.

A difficulty arises in working with such networks as one tries to work with the joint probability distribution, $P(B,E,A,J,M)$, where the alphabets stand for the first letter of the

variables depicted in the network above. But the elegant property of Bayesian Networks is that the joint distribution factors multiplicatively into a number of smaller distributions, which are governed by only the relationship between a node and its parents.

For our example network, the joint distribution factors as follows:

\[ P(B,E,A,J,M) = P(J|A)P(M|A)P(A|B,E)P(B)P(E) \] which makes inference much easier to perform because of involvement of the small probability distributions.

It is amazing how the idea of decomposition pervades from relatively basic ideas in Computer Science (such as Merge Sort) to advanced techniques such as Bayesian Networks. I was trying to explain this to the undergraduate class I am a Teaching Assistant for while we were delving into Bayesian Networks for the first time. Just thought I would write a note to myself in my blog, reminding myself of the elegance of the decomposition approach to problem solving.

Topic Modeling to film scripts!

This came up during a paper discussion today in our seminar on "Statistical Models for Activity Recognition", and I wonder if someone has any ideas? Does anybody know about any work in applying topic modeling ideas (such as Latent Dirichlet Allocation (LDA) models) to film or tv scripts? I would be interested if anyone can give me pointers to such work.

Manifold Learning vs Manifold Embedding

These thoughts stem from the ambiguity that I think persists in differentiating learning vs embedding when it comes to thinking about manifold data. Any comments are welcome.

Whenever one mentions "manifold learning" in machine learning, a number of algorithms tend to pop in ones head (assuming one is familiar with this particular area in machine learning) such as Isomap, Locally Linear Embedding (LLE), Multidimensional Scaling (MDS), t-SNE, and of course, Principal Component Analysis (PCA). Generally we associate manifold learning to techniques that essentially embed very high dimensional data onto a low dimensional space (usually 2D) for purposes of visualization.

As far as I understand, these techniques generally try to build a geodesic distance map of neighborhoods for each point, and based on the distribution of such distances, construct an embedding function that maps these high dimensional points to a low dimensional space that respects these distance distributions. I am grossly simplifying the theme, but each technique builds the distribution of distances of the high dimensional points in its own way (often using an optimization formulation).

But the terminology "manifold learning" seems somewhat misleading to me. The purpose of the aforementioned techniques is more like manifold embedding; though such embedding techniques are also effective in building a recognition system, for example, I cannot fully accept the usage of "manifold learning" in describing these broad class of techniques.

Learning a manifold should entail something different. For very high dimensional data, the number of modes of variability in the data is usually far less than the number of dimensions. In other words, if one can quantify the modes of variability of the data, then one has a parametrized model that captures or describes the very high dimensional data. The learning portion is to answer the question of how one learns these variabilities. Obviously, in learning to capture these variabilities from very high dimensional data one is likely to resort to one of the many embedding techniques to make learning more tractable. Once the variabilities are learned, it can be used to embed high dimensional data into a low dimensional manifold! Being able to compactly describe a manifold might be also advantageous for classification.

In my mind, there appears to be a demarcation between the learning and the embedding views. I have not seen much work from this "learning to describe manifold" perspective. But this alternate view of manifolds might have some interesting application potential, very likely in computer vision.

Dual decomposition: a recurrent theme?

Some thoughts on the idea of decomposition; any comments or discussions are welcome.

The concept of dual decomposition for inference in graphical models, particularly MRFs, is based on an insight that resounds in almost all aspects of problem solving in computer science. The insight is the ability to decompose a very hard problem into smaller, independent problems that are solvable, and then combine these solutions in a clever way to get a solution to the original problem. The elegance of this approach is that it can be used to solve inference problems with discrete variables that result in a difficult combinatorial optimization problem.

If we think back to one of our favorite sorting algorithms (at least my favorite), mergesort, the idea of "decomposition" pervades this elegant sorting algorithm. Instead of trying to sort a large array of size $N$, break the problem up into smaller sorting problems (the divide approach), solve each of these subproblems by recursively breaking into smaller and smaller subproblems, and then combining cleverly all these solutions (the conquer approach) to the small problems to get a solution to the original sorting problem. Of course, the dual decomposition idea for inference in graphical models has its own details, but essentially one can think of it as a form of "divide and conquer".

There are many great references that I can suggest if you are interested in dual decomposition ideas for inference in graphical models. It is quite amazing that the idea of "decomposition" has not only given us efficient sorting, but has lent itself in developing very strong inference mechanisms to address difficult combinatorial optimization problems.

Epilogue: I am including a few references that give a broad overview of graphical models and the dual decomposition framework. The article by Wainwright et al. titled "Graphical Models, Exponential Families, and Variational Inference" is worth looking at. I would recommend reading the first few chapters of David Sontag's PhD thesis. Sontag, Globerson, and Jaakkola have a book chapter titled "Introduction to Dual Decomposition for Inference" that might also be of interest. Komodakis et al. have a recent PAMI article titled "MRF Energy Minimization and Beyond via Dual Decomposition" which is also a good place to look. Another recent work worth looking is by Yarkony, Ihler and Fowlkes titled "Planar Cycle Covering Graphs". All these papers have a fair bit of mathematics.

Kernel trick: feature, matrix, feature

Here is an idea for a kernel trick that might come in handy later at some point. It seems best to transfer it to this blog, instead of simply keeping it in paper, so that at a later time I can do a quick search. Here is the summary of the trick (apologies if the notation is confusing).

Suppose we have some data $x_1,x_2,\ldots,x_n$. Assume $\Psi \in \mathbb{R}^{D \times D}$. We want to write a kernel version for the form
\[ \Phi(a)^T \Psi \Phi(b) \] where $\Phi$ is a non-linear feature map for an arbitrary data point $a$.
Let $\Psi = \sum_{ij} \alpha_{ij} \Phi(x_i)\Phi(x_j)^T$. The kernel trick is as follows:
\[
\begin{align}
\Phi(a)^T \Psi \Phi(b) &= \Phi(a)^T \sum_{ij} \alpha_{ij} \Phi(x_i)\Phi(x_j)^T \Phi(b)\\
&= \sum_{ij} \alpha_{ij} \Phi(a)^T \Phi(x_i)\Phi(x_j)^T \Phi(b)\\
&= \sum_{ij} \alpha_{ij} K(a,x_i)K(x_j,b)
\end{align}
\]
This is part of a derivation to kernelize an optimization formulation. There is also an assumption here about the $\Psi$, that is, it lies in the span of our data.

New blog for machine learners/data miners

Alex Smola has started writing a blog, Adventures in Data Land. I have looked at a few entries, and I already like what he is doing. He is sharing tips and tricks that machine learners and data miners would love to have in their repertoire. I hope he also shares his ideas on some machine learning problems that, in his opinion, are the most challenging. Thanks Alex.

CVPR 2010

I am in San Francisco right now for CVPR 2010. I was planning on writing up something on some of the interesting papers that I have seen here, but the conference has been keeping me extremely busy. Maybe I will write something up once I leave for home tomorrow afternoon. To summarize my experiences so far, CVPR started out not that exciting but in the last two to three days I have seen some excellent work. I am looking forward to this afternoon session on sparse coding.

How machine learners go for lunch?

This is how my friend, a machine learner, uncertain about where to go and get lunch from decided to settle the problem:

"...random walk on campus, with a bias towards the food courts."

Another computer vision paper

Here is the paper that we are discussing this week at our computer vision seminar. This is work by Kolmogorov, Vicente and Rother on jointly optimizing segmentation and image appearance models using a MAP-MRF formulation.

Computer vision papers

Here are two computer vision papers you might find interesting:

• S Gould, T Gao, and D Kollar. Region-based Segmentation and Object Detection. NIPS 2009.
• C Gu, J Lim, P Arbelaez, and J Malik. Recognition using regions. CVPR 2009.

We are looking at these two papers in our computer vision reading seminar this week.

"Write Blog"

I have to apologize for not being regular. It has been really long since the last time I wrote; things have been pretty busy, with research projects, full load of classes, grading, and all the usuals of being a graduate student. I have been able to attend a number of great machine learning talks as well, which I was planning to write something about, but just never got around to doing that.

I think I really need to put 'write blog' in my calendar.

Lifted first order and first order languages

I spent a week or two exploring first order and lifted first order languages. The idea is very simple; express models in first order, and the system creates the necessary graphical models to perform inference. From a machine learning perspective, this is a very useful idea. Since graphical models are not always in the repertoire of machine learners, this kind of first order language specification of probabilistic models will be advantageous. I think the eventual goal is to have such a system as a library to a standard programming platform, where the complexity of graphical models is abstracted away in the form of a blackbox.

Transfer learning and kernel based multitask learning

I have a number of papers on transfer learning that I have started looking through for one of my research projects. Transfer learning is a machine learning technique where the basic idea is to learn multiple related tasks simultaneously, rather than learn each task independently. Previous work have shown that this works better, especially for predictive performance, compared to independent, single task learning. For my problem, I am interested in using multitask learning techniques based on natural extensions of kernel based methods for single task learning, such as the Support Vector Machines (SVMs).

Convex optimization reading group

I am now part of a reading group on convex optimization. We are going through the amazing optimization book by Professor Boyd.

Compressive sensing, again

I am currently reading a paper titled 'Random projections of smooth manifolds' by Baraniuk and Wakin. From a machine learning point of view, this paper is very interesting since it deals with dimensionality reduction, a very useful technique in machine learning research. The other great aspect of this paper is its close relation to compressive sensing (cs) ideas, a topic that I have been excited about for a while.

Graph theory and probabilistic inference

Graphical models and probabilistic inference have become an intimate part of current machine learning research. I came across a paper by Professor Michael Jordan that gives a great introduction to probabilistic inference techniques based on graphs. Here is a link to the paper.