Update for structured SVM in Python

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.



The new version now has some options to be really verbose, track the slacks and constraints of all examples and measure the primal objective.

Also, quite handy for approximate inference, it complains when the slack of the "most violated constraint" is smaller than the slacks of the previous constraints.

The code is not as pretty as it could be but I'm still hacking at it all day.
I hope it is still usable.

A quick word about the bug that I fixed:
In the usual SVM, all the dual variables alpha are constraint to be within
0 < alpha < C. In the structural SVM, several dual variables correspond to the same example and share a common slack variable. Therefore, the sum of all alpha that correspond to a single example is bound by C.
Took me 3 days to find :-/

A good read on subgradient methods for structured prediction is "(Online) Subgradient Methods for Structured Prediction" by Ratliff et. al.

I found the learning rate to be a bit hard to tune, though. I guess this method is a gain better for many examples. Please note that I implemented a batch version, not an online version. Though this is trivial to change.

Any comments would be very welcome :)

Comments

  1. UnknownJune 17, 2012 at 11:54 PM

    > Therefore, the sum of all alpha that correspond to a single example is bound by C.

    Don’t you implement the 1-slack variant?

    ReplyDelete
  2. Andreas MuellerJune 17, 2012 at 11:55 PM

    No, I use one slack per example. This is the standard version from the original paper.

    ReplyDelete
  3. Andreas MuellerJune 18, 2012 at 12:02 AM

    To elaborate: I am not very interested in the optimization problem itself. I want to learn in a setting with approximate inference, where the inference is potentially much, much more expensive than the SVM optimization. As I said in my last post, I even start the SVM optimization completely anew in each iteration. That doesn't really matter that much.
    The idea was more to have a flexible, easy to understand system. This is in no way an approach to be faster than the established software.

    ReplyDelete

Post a Comment

Popular posts from this blog

Machine Learning Cheat Sheet (for scikit-learn)

Image
As you hopefully have heard, we at scikit-learn are doing a user survey (which is still open by the way). One of the requests there was to provide some sort of flow chart on how to do machine learning. As this is clearly impossible, I went to work straight away. This is the result: [edit2] clarification: With ensemble classifiers and ensemble regressors I mean random forests , extremely randomized trees, gradient boosted trees , and the soon-to-be-come weight boosted trees (adaboost). [/edit2] Needless to say, this sheet is completely authoritative.
Read more

A Wordcloud in Python

Image
Last week I was at Pycon DE , the German Python conference. After hacking on scikit-learn a lot last week, I decided to to something different on my way back, that I had planned for quite a while: doing a wordl -like word cloud . I know, word clouds are a bit out of style but I kind of like them any way. My motivation to think about word clouds was that I thought these could be combined with topic-models to give somewhat more interesting visualizations. So I looked around to find a nice open-source implementation of word-clouds ... only to find none. (This has been a while, maybe it has changed since). While I was bored in the train last week, I came up with this code . A little today-themed taste:
Read more

MNIST for ever....

Image
[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...
Read more

Python things you never need: Empty lambda functions

Ever wanted to create an empty Python function in-line? No? Me neither. But my coworker does... We found the answer: <pre> x = lambda : None </pre> If you ever needed this, please tell me ;) [Edit] Apparently some people do need it :) Btw, most people seem to try Most people try lambda: pass first. But you have to remember, the thing at the right side of the colon is the return value of the function, not the body! So an expression is needed, not a statement. [\Edit]
Read more