Peekaboo

Some time ago I wrote about a structured learning project I have been working on for some time, called pystruct . After not working on it for some time, I think it has come quite a long way the last couple of weeks as I picked up work on structured SVMs again. So here is a quick update on what you can do with it. To the best of my knowledge this is the only tool with ready-to-use functionality to learn structural SVMs (or max-margin CRFs) on loopy graphs - even though this is pretty standard in the (computer vision) literature.

Recently we added another method for kernel approximation, the Nyström method, to scikit-learn , which will be featured in the upcoming 0.13 release. Kernel-approximations were my first somewhat bigger contribution to scikit-learn and I have been thinking about them for a while. To dive into kernel approximations, first recall the kernel-trick .

I just pushed an update for my structured SVM in Python. This contains a bugfix in the dual formulation  and a subgradient descent version of the structured SVM.

[EDIT: If you are reading this now, have a look at pystruct.github.io . The project matured quit a bit in the meantime.]  Today I pushed some of my code to github that I use for experimenting with CRF learning. This goes along the lines of my recent posts on graphcut and I hope to post a full CRF learning framework for semantic image segmentation soon. This is a pretty standard setup in computer vision, but I really haven't found much code online. Actually I haven't found any code to learn loopy CRFs, so I hope my simple implementation can help to get a better understanding of these methods. It certainly helped me ;)

I just pushed some of my structured learning code to github and hope that some people might find it useful. Before describing my code here, I wanted to give a basic intro into structured prediction. I hope I can at least convey some intuition for this vast research area. So here goes... What is structured learning and prediction? Structured prediction is a generalization of the standard paradigms of supervised learning, classification and regression. All of these can be thought of finding a function that minimizes some loss over a training set. The differences are in the kind of functions that are used and the losses. In classification, the target domain are discrete class labels, and the loss is usually the 0-1 loss, i.e. counting the misclassifications. In regression, the target domain is the real numbers, and the loss is usually mean squared error. In structured prediction, both the target domain and the loss are more or less arbitrary. This means the goal is not to predict ...

There is apparently a "new" trend in computer vision that I seem to have missed. It's explicit feature maps . So what is this about? We all know and love the kernel trick: have some vector representation X of your data and some algorithm (like SVMs) that rely only on dot products in the input space. Replace the dot products by some positive definite kernel and by Mercer's Theorem there is some Hilbert space of functions Y and some mapping phi: X -> Y such that your kernelized algorithm works as if you mapped your input to phi. This extremely powerfull method is now used everywhere, most of all for SVMs. But it has several significant drawbacks in this case: Training using a non-linear kernel is a lot slower [O(n^3)] than training a linear SVM [O(n)]. Kernel SVMs take a lot of memory to store, since they are "non-parametric" in a sense. In addition to the Lagrange-Multipliers alpha, all the support vectors have to be stored. Recall is painfully...

I was just reading the paper in the title ( pdf ), which Alexei Efros talked about at CVML. It's from this years ICCV. The basic idea of the paper is to do object detection by training a linear SVM on hog features for each positive example. I thought the idea was pretty cool and wanted to write something about it... and then I saw there is already a post by the first author, Tomasz Malisiewicz, in his own blog . He also discusses some of his (matlab :( ) code for non-maximum suppression. So check out his blog for more details on this cool paper :)

Some tips and facts that I took from the summer school. They are pretty random but may be usefull for pactitioners of vision. Many may seem obvious - but I just didn't see it before ... Gist doesn't work on cropped or rotated images. Since it does a kind of whole image template matching, this is pretty clear. And maybe it shouldn't - the scene layout is changed after all. For doing BoW Cordelia Schmid suggests (and I guess uses) 6x6 patches and a pyramid with scale factor 1.2. Scaling is done by Gaussian convolution. Ponce uses 10x10 patches to do sparse coding. If you combine multiple features using MKL or by just adding up kernels (which is the same as concatenating features), normalize each feature by it's variance and then search for a joint gamma. This heuristic get's you out of doing grid search over a huge space! Cordelia Schmid thinks that "clever clusters" don't help much in doing BoW. She thinks it's more important to work ...

[update] This post is a bit old, but many people still seem interested. So just a short update: Nowadays I would use Python and scikit-learn to do this. Here is an example of how to do cross-validation for SVMs in scikit-learn. Scikit-learn even downloads MNIST for you. [/update] MNIST is, for better or worse, one of the standard benchmarks for machine learning and is also widely used in then neural networks community as a toy vision problem. Just for the unlikely case that anyone is not familiar with it: It is a dataset of handwritten digits, 0-9, in black on white background. It looks something like this: There are 60000 training and 10000 test images, each 28x28 gray scale. There are roughly the same number of examples of each category in the test and training datasets. I used it in some papers myself even though there are some reasons why it is a little weird. Some not-so-obvious (or maybe they are) facts are: - The images actually contain a 20x20 patch of digi...