Blog moved

I have finally moved my blog to a new platform. The address blog.mikiobraun.de and the feedburner RSS feed stay the same, so hopefully nothing should change for you.

The Open Source Process and Research

(Cross posted on mloss.org)

I think there is more to be learned from the open source software development process than just publishing the code from your papers. So far, we’ve mostly focused on making the software side more similar to publishing scientific papers, for example, through creating a special open source software track at JMLR.

However, there is more to be learned from the open source software development process:

• “Release early, release often” Open source software is not only about making your software available for others to reuse, but it is also about getting in touch with potential users as early as possible, as closely as possible.

Contrast this with the typical publication process in science where there lie months between your first idea, the submission of the paper, its publication, and the reactions through follow-up and response papers.

• Self-organization collaboration One nice thing about open source software is that you can often find an already sufficiently good solution for some part of your problem. This allows you to focus on the part which is really new. If existing solutions look sufficiently mature and their projects healthy, you might even end up relying on others for part of your project, which is really interesting given that you don’t even know these people or have ever talked to them. But if the project is healthy, there is a good chance that they will do their best to help you out, because they want to have users for their own project.

Again, contrast this with how you usually work in science, where it’s much more common to collaborate with people from your group or people within the same project only. Even if there were someone working on something which would be immensely useful for you, you wouldn’t know till months later when their work is finally published. The effect is that there is lots of duplicate work, research results from different groups don’t usually interact easily, and much potential for collaboration and synergy is wasted.

While there are certainly reasons while these two areas are different, I think there are ways to make research more interactive and open. And while probably most people aren’t willing to switch to open notebook science, I think there are a few things which you can try out now:

• Communicate to people through your blog, or by Twitter or Facebook, and let them know what you’re working on, even before you have polished and published it. And if you don’t feel comfortable to disclose everything, how about some preliminary plots or performance numbers? To see how others are using social networks to communicate about their research, have a look at the machine learning twibe, or my (entirely non-authoritative) list of machine learning twitterers, or lists of machine learning people others have compiled, or another list of machine learning related blogs.

• Release your software as early as possible, and make use of available infrastructure like blogs, mailing lists, issue trackers, or wikis. There are almost infinitely many options to go about this, either using some site like github, sourceforge, kenai, launchpad, savannah, or by setting up a private repository, for example using trac, or just a bare subversion repository. It doesn’t have to be that complicated, though. You can even just put a git repository on your static homepage and have people pull from there. And of course, register your project with mloss, such that others can find it and stay up to date on releases.

• Turn your research project into a software project to create something others can readily reuse. This means making your software usable for others, interface it with existing software, and also, start reusing existing software as well. It doesn’t have to be large if it’s useful. Have a look at mloss for a huge list of already existing machine learning related software projects.

jblas release 1.0

Update: I released jblas-1.0.1 which also works on processors which only support SSE2 (e.g. older Athlon64 processors). Go to jblas.org and check it out!

I’ve just release jblas 1.0. For those of you who don’t know yet, jblas is a matrix library for Java which is based on the BLAS and LAPACK routines, currently using ATLAS and lapack-lite, for maximum performance.

I’m using jblas myself for most of my research together with a wrapper in jruby which I plan to release pretty soon as well.

In any case, here are the most important new features of release 1.0

• Default jar file now contains all the libraries for Windows, Linux, and Mac OS X. Both 32 and 64 bit are supported (although right now, the 64 bit version for Windows is still missing. I’ll take care of that after the holidays). The libraries are built for the Core2 platform which in my experience gives the best combined performance on Intel and AMD processors (The Hammer or AMDk10h settings give slightly better performance on AMD, but inferior performance on the Intel platform).

• New LAPACK functions GEEV (generalized Eigenvalues), GETRF (LU factorization), POTRF (Cholesky factorization) in NativeBlas.

• Decompose class providing high-level access to LU and Cholesky factorization.

• Improved support for standard Java framework: Matrix classes are serializable, matrix classes provide read-only AbstractList views for elements, rows, and vectors.

• Permutation class for random permutations and subsets.

The new jar file also comes with a little command line tool for checking the installation and running a small benchmark. If you run java -server -jar jblas-1.0.jar on my machine (Linux, 32 bit, Core 2 Duo @ 2Ghz), you get

Simple benchmark for jblas

Running sanity benchmarks.

checking vector addition... ok
-- org.jblas CONFIG BLAS native library not found in path. Copying native library from the archive. Consider installing the library somewhere in the path (for Windows: PATH, for Linux: LD_LIBRARY_PATH).
-- org.jblas CONFIG Loading libjblas.so from /lib/static/Linux/i386/libjblas.so.
checking matrix multiplication... ok
checking existence of dsyev...... ok
checking XERBLA... ok
Sanity checks passed.

Each benchmark will take about 5 seconds...

Running benchmark "Java matrix multiplication, double precision".
n = 10   :  424.4 MFLOPS (1061118 iterations in 5.0 seconds)
n = 100  : 1272.6 MFLOPS (3182 iterations in 5.0 seconds)
n = 1000 :  928.5 MFLOPS (3 iterations in 6.5 seconds)

Running benchmark "Java matrix multiplication, single precision".
n = 10   :  445.0 MFLOPS (1112397 iterations in 5.0 seconds)
n = 100  : 1273.0 MFLOPS (3183 iterations in 5.0 seconds)
n = 1000 : 1330.9 MFLOPS (4 iterations in 6.0 seconds)

Running benchmark "ATLAS matrix multiplication, double precision".
n = 10   :  428.2 MFLOPS (1070428 iterations in 5.0 seconds)
n = 100  : 3293.9 MFLOPS (8235 iterations in 5.0 seconds)
n = 1000 : 5383.2 MFLOPS (14 iterations in 5.2 seconds)

Running benchmark "ATLAS matrix multiplication, single precision".
n = 10   :  465.2 MFLOPS (1162905 iterations in 5.0 seconds)
n = 100  : 5997.3 MFLOPS (14994 iterations in 5.0 seconds)
n = 1000 : 9186.6 MFLOPS (23 iterations in 5.0 seconds)

Resources:

• web page
• downloads
• API Documentations
• mailing list
• github project
• mloss page

Twitter's new Retweet Feature

Twitter has been rolling out the new retweet feature to some users. If you're one of them, you'll have a new button saying "Retweet" below each tweet, and also have notifications about who retweeted you (using this new feature, I'd guess).


A lot of people are already complaining that the use of the feature is too limited, mainly because it doesn't allow you to add a comment to a retweet by putting some text before the actual retweet like this:


Actually, I think the critics are right, the comments are a useful feature, and hopefully, twitter will add it rather quickly.

One of the nice things about the retweet feature is that you can actually see who has been retweeting you. But even when you're not one of the beta testers, you can get that information pretty easily from twimpact. Just type in your name in the search bar, or go directly to http://twimpact.com/user/yourname, and you will have a list of all your retweeted messaged with a list of who retweeted you, at least back till June 2009.
For example, here is my (pretty pathetic) list:


And before you complain, we know that not all retweets make it in there, but this is mostly due to the fact that twitter's search infrastructure is eventually consistent, at best.

Some Benchmark Data Sets

Sören Sonnenburg recently brought my attention to a few possibly lesser known benchmark data sets. Of course, benchmark data sets are always a double-sided sword: On the one hand, they are a great way to test and compare your learning algorithms, but on the other hand you’re usually not really solving any real problems anymore.

So you probably already know the UCI repository, or the DELVE repository. Here are a few links to probably lesser known benchmark data sets:

Generic Benchmarking

• IDA dataset repository (a.k.a. “the Gunnar Benchmark Data Set”)
• libsvm datasets
• Datasets from cervisia.org
• KDD datasets
• Pascal Large Scale Challenge

Multiple Kernel Learning

• MKL interpretable datasets
• Multiple Kernel Learning repository

Bioinformatics

• Human Promoter recognition
• Splice site prediction (several organisms)
• Alternative splicing

Image Processing

• Caltech 101
• Caltech 256
• Other caltech image

Machine Learning Feed Updates II

I’ve added a few more research blogs.

Taken from Mark Reid’s kith:

• aicoder by Neal Richter
• vetta project by Shane Legg
• natural language processing blog by Hal Daume III
• Justin Domke’s Weblog
• Data Mining: Text Mining, Visualization and Social Media by Matthew Hurst

More additions:

• Machine Learning for Computer Security by my colleague Konrad Rieck
• oliviergrisel.name by Olivier Grisel (although he said he wanted to update everything about it in a long time)
• Statistical Modeling, Causal Inference, and Social Science by Andrew Gelman (quite high volume, by the way)
• mloss.org Community blog blog for mloss.org on ML software and open source
• AI and Social Science by Brendan O’Connor

I should probably collect all the entries somewhere… .

Again, in case you missed it, the feeds can be found in this post.

Machine Learning Feed (Update)

I’ve set up two more (sub-)feeds now, one for blogs by ML researchers, and one for the papers. You can also have the full feed if you want. The reason for this split is that the preprint and journal feeds have a much higher volume and will drown the actual blog posts.

So here are all your Machine Learning Feed options:

Feed	Google Reader	Feedburner
Full	Atom Feed Web View	http://feeds.feedburner.com/mlfeed
Only blogs	Atom Feed Web View	http://feeds.feedburner.com/mlfeed-blogs
Only Papers	Atom Feed Web View	http://feeds.feedburner.com/mlfeed-papers

Again, if you have any suggestions/comments, please let me know. I think it would be great if we could collect all the interesting people from our community.

In that spirit, I’ve added mlsec.org, a blog on machine learning and computer security by my colleague Konrad Rieck.

Machine Learning Feeds and Twitterers

I’ve collected some information about machine learning people on twitter and machine learning blog’s.

Twitter

• Mark Reid has put together a nice list of ML twitterers.
• There exists a machine learning twibe, and a machine learning tlist.

Blogs

A few days ago, I thought that it would be very nice to have some kind of blog aggregator like planet debian for machine learning. After some poking around I found that the easiest way to aggregate and publish RSS feeds is actually through Google reader. Here is the resulting machine learning feed. Feel free to subscribe to it!

Here is what is currently in there:

People/Websites/Companies:

• Induction ex machina by Mark Reid.
• Machine Learning (Theory) by John Langford.
• i2pi by Joshua Reich.
• Radford Neal’s blog (not updated in a while.)
• Marginally Interesting by myself (although it’s been a while since I last blogged about core-ML ;))
• David R. MacIver’s blog.
• Machine Learning, etc. by Yaroslav Bulatov.
• Dataspora Blog by Dataspora LLC
• Data Wrangling by Pete Skomoroch.

Journals/Paper feeds:

• Journal of Machine Learning Research
• arXiv feed for Computer Science, Learning (cs.LG)
• arXiv feed for Statistics, Machine Learning (stat.ML)

If you have a suggestion of feeds to add, or want your feed removed for some reason, please let me know!

Update: I've set up two different feeds. You can either have the original Google reader feed, or the feedburner feed. The latter has more compact summaries, while the former might have a nicer web view.

More updates:I've put up different feeds for only blogs and only papers.

What's Wrong With Ruby Module Functions

I’m currently rewriting most of my JRuby/Java based machine learning toolbox, which I’m using for my research work, and stumbled upon a little Ruby “feature”: At least the way I see it, Ruby is a bit unbalanced with its scoping rules which make modules less useful as namespaces for organizing functions.

Every now and then, you will find that a certain functionality is best exposed as a set of functions, instead of a set of objects. Even Java has accepted this and provides the import static directive since 1.5. For example, consider a module which provides all kinds of mathematical special functions like Bessel functions or the like.

The way Ruby supports module functions is through the module_function statement. For example,

module MoreMath
  module_function

  def bessel(alpha, x)
    ...
  end
end

Then you can both call it via MoreMath.bessel(a, x) and also after you have included it in your workspace, or your class, etc.

Now, interestingly (and probably also annoyingly), you don’t see the function from any class defined in the module:

module MoreMath
  ... # same as above

  CONSTANT = 5.43132

  class SomeClass
    def do_compute
      x = bessel(1, 1) # <- won't work!
      y = CONSTANT + 3 # <- will work!
      ...
    end
  end
end

On the other hand, constants are visible (as shown with the CONSTANT above). In order to make bessel visible in SomeClass, you have to include the module in which the class is defined in the class:

module MoreMath
  ...
  
  class SomeClass
    include MoreMath
    ... # now you can use bessel()
  end
end

Okay, maybe there is something fundamental which I haven’t yet grasped about Ruby, but for me this feels just wrong. The whole point of lexical scoping is that you don’t have to be explicit about what scope is active, but you can see it from the nesting structure of the code. To me it also seems like lexical scoping has been hacked into Ruby for constants (because otherwise you couldn’t probably even see other classes defined in the same module, which would be even more painful), and someone just forgot module functions. I think part of the problem is that modules also double as mixins which doesn’t, well, mix well.

By the way, another “feature” is that module functions aren’t treated properly when you include a module in another. Including a module only works with the instance functions which means that you cannot invoke the function making the module explicit:

module EvenMoreMath
  include MoreMath
end

EvenMoreMath.bessel(alpha, x) # <- doesn't work, because
                              # include only copies
                              # instance methods, not
                              # MoreMath.bessel

For me, the cleanest way out is to collect all modules in a sub-module with a generic short name like Fcts, then you can at least access the functions without having to fully qualify the module (which works, again because module names are constants, and the lexcial scoping works for modules):

module MoreMath
  module Fcts
    module_function

    def bessel(alpha, x)
        ...
    end
  end
  
  class SomeClass
    def do_compute
      x = Fcts::bessel(1, 1) # <- okay now
    end
  end
end

include MoreMath::Fcts

bessel(1, 1) # also ok now.

In summary, although I really like Ruby, I think the module scoping rules are broken as they are and using modules as namespaces for functions isn’t really working.

LG X130 Mini-Review

I recently bought a netbook LG X130, and since I couldn’t find much information about it on the internet (apart from “reviews” which were actually just a rephrasing of the original press release), I thought I’ll write down my first impressions.

The netbook closed.

The netbook opened. Note that this is the maximum opening angle.

Featurewise it is pretty much what everyone else is offering right now: Intel Atom N270 @ 1.6 Ghz, 160GB hard disk, 1GB of RAM, Intel 945 Express graphics chipset, Windows XP SP 3, ethernet (10/100), wireless, bluetooth, a few usb ports, cardreader (SD and Memory Stick) and built-in webcam (1.3 megapixels, but just as blurry, noisy and having weird colors as anything else).

The actual selling point (apart form its rather aggressive price tag of 349€ here in Germany) is the battery. It is a 9-cell model claimed to run for “up to 12 hours”. And to put this out first: while 12 hours might be quite unrealistic, you can really get a solid 9 hours out of it with typical use (editing, watching videos, internet), which is really quite amazing and puts the device close to smartphones in terms of how often you have to recharge.

What most brochures don't show: X130 with 9-cell battery pack.

The 9-cell battery pack totals 81 Wh.

What most brochures or pictures don’t tell you, though, is that this stamina comes at a price, namely a really huge battery pack. The battery back not only extends to the back, but also down, meaning that the netbook doesn’t lie flat on the table but is actually tilted. The angle is very close to what you get with ordinary keyboards (without the little stubs extended), so the usability is ok. However, if you expect to be able to stack the netbook between other books, you’ll be disappointed. The netbook also weighs about 1.4 kg with batteries, and a bit less than 1 kg without, which is still quite light, but maybe not as much as you would expect when you see the netbook on display in a store without the batteries.

The tilt of the keyboard is comparable to a normal keyboard.

Another unpleasant surprise was that the screen does not tilt back 180 degress, but more like three fourths of that. The pictures show what this looks like. This restriction is usually not a problem, only when the netbook is really close to my body (for example, on your lap), I sometimes would like to extend it even further back.

Keyboard layout is more or less standard. (And not as curved as it seems... That's only the pincushion distortion of my camera)

Apart from these two points, the netbook is very nice. It is sturdily built, the design is acceptable (although not really that cool, IMHO). The keyboard layout is ok, at least they have put the Control key right in the corner. I had to get used a bit to the “Home” and “End” key being located next to the cursor keys, separate from the page up and page down keys.

Another nice addition is the wireless card. It is based on the ralink chip rt3090 which supports the new “n” flavor with a maximum speed of 150MBit/s (if you’re router supports it, of course). The downside is that the support for it in Linux is not really there, ubuntu 9.04 does not recognize the card. There exist some drivers on the ralink page, but I haven’t yet tried that one out. There exists support for ralink chips in the most recent Linux kernels, but it seems this is for older ralink chipsets only.

I was quite surprise with how fast the system feels and how little energy it consumes (although this certainly holds for all current netbooks). You can run Google Earth full screen (which means 1024 * 600) with an estimated frame rate from 3 to 15 fps which is really quite nice. Even under load, I could only measure about 15W on the wall, more like 6W under light load. That’s about half of what most motherboards consume when they’re turned off… .

So in summary, a very nice netbook with great battery life, but also a quite bulky battery pack.

Pros

• On par with all the other company’s offerings.
• “802.1n” wireless up to 150 MBit/s.
• 9-12 hours of battery life.
• LG didn’t install too much crap, mostly minor tools like customized battery viewer, and Open Office.
• Subjectively, screen very bright at maximum.

Cons

• Battery extends in almost every direction, quite heavy.
• Screen doesn’t tilt back a full 180 degrees.
• Reflective screen.
• No out-of-the-box drivers for the wireless under Linux right now. Update: Linux 2.6.32 ships with drivers for the RT3090 chip in the "staging" section. I managed to get it running with ubuntu 9.10 netbook remix. If I find time, I'll summarize the steps.

Twimpact Work In Progress

Twimpact has been running smoothly in its small niche of the internet, and we're currently trying to improve the way retweets are crawled and analyzed. The problem is that people often add some comment to the end of the original message, and also edit the original message such that it's not that straightforward to really know whether you have a new tweet or not.

There are also some more bugs, which will be fixed soon. For example, apparently, we weren't handling underscores in user names correctly such that "RT @nfl_games" became a retweet of the user "nfl" with the message "games", which has been retweeted more than 1800 times.

We currently also don't filter out users who retweet a tweet repeatedly or who retweet their own tweets, leading to all kinds of retweet bots and retweet-spam networks being high up in our retweet trends. While that may not be so informative, it is still interesting to see what kind of business ideas people come up with around the twitter platform.

For example, dannywhitehouse apparently has a service called twitter-bomb which I guess does all kinds of nasty things which are certainly not covered by twitter's Terms of Service, but who still managed to amass more than thirteen thousand followers.

In any, case we'll be rolling out the improvements soon, maybe this week, so stay tuned! The only problem we'll run into is that we have to reprocess all the tweets already in our database 8-O

Twimpact!

For the last one and a half months, Matthias Jugel and I have been working on a site which computes impact scores for twitter users based on how often their tweets become retweeted.

The project was really lots of fun so far. The first time we got the thing up and running was around the time of the Iranian elections and suddenly seeing all those tweets in real-time gave a feeling of directly tapping into the twitterverse.

The winner twimpact wise is clearly mashable with a twimpact score of 89 right now and over ten thousand retweeted messages. Other top users include: news cites like breakingnews, cnnbrk, and smashingmag, or celebrities with many, many followers like aplusk (Ashton Kutcher), or iamdiddy (Puff Diddy).

On the entry page you can see a live view of what has been retweeted most in the last hour. It's quite interesting to see what is popping up there. For example, surprisingly, there are many competitions of the form "retweet this and win a laptop" like this one which has been retweeted over 1300 times. Another kind of retweet is the inspirational message from users like deepak_chopra which people like to pass on. But apart from that you have of course current news, interesting links and so on. These are mostly technology and web related, which reflects the user base of twitter quite well, I think.

So go ahead and compute your twimpact score, or just sit back and look at what people are currently retweeting.

Threads, Exceptions, Net::HTTP, Timeouts and JRuby

I recently had some fun debugging a little application of mine written in JRuby which crawls the twitter search API looking for specific tweets. The problem was, every now and again, the crawler would hang even if I set appropriate timeouts. The crawler consisted of two threads, one periodically issuing a search to twitter, and another one writing the results into the database.

The first surprise to me was that in Ruby, by default, if there is an exception in a thread, the thread silently dies, not even issuing an error message. Only after you joined the thread, you get the error message. You can set Thread.abort_on_exception = true which completely kills your application, however. This meant that what appeared to be missed timeouts could just as well be uncaught exceptions.

So when working with multithreaded applications, enclosing the whole thread in a begin .. rescue Exception => e ... end is important if you want to get noticed about errors at all.

But still, the thread would misteriously die without properly handling the timeout. Some digging deeper revealed an old bug report and an interesting article about Ruby and timeouts in general which seemed to imply that timeouts might not always work, in particular if system calls are involved. It was unsure, though, whether the situation is the same for JRuby which uses native threads instead of Green threads (simulated threads by doing explicit time-slicing in the interpreter).

So I started to read the JRuby sources, to understand where and how timeouts are implemented in Net::HTTP. Which lead to my next surprise: Net::HTTP completely handles timeouts through the Timeout module, not on a socket level. It does not use the possibilities to set timeouts on reads or writes but encapsulates all the significant portions of code in Timeout::timeout { ... } calls. I also found a nice old post by Charles Nutter (a.k.a. headius) explaining the implementation in depth.

I guess based on that post, JRuby has started to implement Timeout again in Java (source). And some first tests revealed that this timeout plays well within Net::HTTP, but my crawler was still hanging every once and again.

Finally, I found the last missing piece of information: From the sources, it seems that JRuby's implementation of the Timeout module raises the Timeout::ExitException when the timeout happened. However, that is a ruby 1.9 feature, in ruby 1.8, the exception was named Timeout::Error. So basically, I was catching the wrong exception, in fact not catching it at all, thereby killing the thread (silently). Interestingly, some more testing showed that if JRuby raises a Timeout::Error if you use the Timeout module yourself, but raises a Timeout::ExitException when you're using Net::HTTP.

In the end, I just enclose the whole HTTP request section with a Timeout::timeout of my own, catching both Timeout::Error and Timeout::ExitException and finally everything was running robustly.

So in summary

• Uncaught exceptions silently kill threads in ruby.
  
• Net::HTTP does it's own timeouts through the Timeout module.
  
• Somtimes, JRuby raises Timeout::ExitException, not Timeout::Error. Will be fixed in JRuby 1.4 (see below)
  

I guess I should post a bug report on the latter... .

Update: I submitted a bug report, and it's already fixed! Those jruby people are really incredibly fast!

Machine Learning Twibe

Twibes is some new twitter-related website which manages topic-related groups of people and collects tweets based on up to three tags.

Since apparently nobody did so far, I set up a twibe on machine learning. Follow the link and click on "Join" on the right and side to join.

Currently, the group is picking up tweets with either "machine learning", "#machlearn", or "#machine-learning" in them. Anyone got an idea how to improve the tags?

Some Benchmark Numbers for jblas

The last few days I've been putting together a benchmarking tool for jblas which I'll hope to release to the public as soon as I've figured out how to best package that beast.

It compares my own matrix library, jblas against the Matrix Toolbox for Java, Colt, as well as simple implementations in C and Java, and, of course, ATLAS.

All experiments were run on my Laptop which sports an Intel Core 2 CPU (T7200) with 2GHz. Maybe the most remarkable feature of this CPU (and many other Intel CPUs as well) is the rather large 2nd level cache of 4MB which will come in handy as we'll see below.

Some more information on the plots: C+ATLAS amounts to taking C for vector addition and ATLAS for matrix vector and matrix matrix multiplication. Shown is the number of theoretical floating point operations. For example, adding two vectors with n elements requires n additions, multiplying a matrix with n squared elements requires 2n^2 additions and multiplications. Now I know that there exist matrix multiplication algorithm which require less than cubic number of operations, but I've just sticked to the "naive" number of operations as that is what ATLAS implements, as far as I know.

Vector Addition

In vector addition the task is simply to add all elements of one vector to all elements of the other vector (in-place). What is interesting about vector addition is that there is really little you can do to optimize the flow of information: You just have to go through the whole vector once. Basically, all methods are on par, with the exception of Colt and ATLAS (!!). No idea what they did wrong, though.

You can also very nicely see the L1 and L2 cache edges resulting in the two steps. On CPUs with smaller L2 cache (like, for example, most AMD CPUs), the shoulder is much less pronounced.

Matrix-Vector Multiplication

Matrix-vector multiplication can be thought of as adding up the columns of a matrix given the weights of the vector. Similar to vector addition, you basically have to go through the whole data once, there is little you can do about it. However, if you are clever, you can make at least sure that the input and output vectors stay in cache which leads to a better throughput.

Here, ATLAS is faster than the naive implementations by roughly 50%. jblas also uses a naive implementation. The reason is that Java needs to copy an array when you pass it to native code, and since you basically have to go through the matrix once, you loose more time copying the matrix than simply doing the computation in Java itself.

Matrix-Matrix Multiplication

In matrix-matrix multiplication the ratio of memory movements to operations is so good that you can practically reach the theoretical maximum throughput on modern memory architectures - if you arrange your operations accordingly. ATLAS really outshines the other implementations here, getting to almost two (double precision!) floating point operations per clock cycle.

Luckily, copying the n squared many floats can be asymptotically neglected compared to the n cube many operations meaning that it pays of to use ATLAS from Java. The performance of jblas is very close to ATLAS, and becomes even closer for large matrices.

Summary

On the buttom line, I'm glad that jblas is pretty fast, certainly faster than Colt and on par with MTJ except for matrix-matrix multiplication. I should add that I used the Java-only versions of Colt and MTJ. It should be possible to optionally link against the ATLAS versions, although Colt does not integrate these methods as well as jblas, and I'm not sure whether MTJ does that.

Also, in my opinion jblas is easier to use because it only uses one matrix type, not distinct types for vectors and matrices. I've tried that at first, too, but then often ended up in situations where a computation results in a row or column vector which I then had to artificially cast to a vector so that I could go on.

Of course, MTJ and Colt are currently more feature rich, supporting, for example, sparse matrices or banded storage schemes, but if you want to have something simple which performs well right now, why not take jblas ;)

Science and the Market Metaphor

John Langford had an interesting post on what he calls the "adversial viewpoint" on academia. Basically, the argument is that under this viewpoint, you assume that scientists in academia compete over a fixed set of resources (research money, positions, students) and that therefore all the other scientists are your adversaries. He suspects that this might be one of the reasons behind the decline in reviewing quality at conferences such at NIPS he has observed in the following years.

John argues that the adversarial viewpoint might make sense, but it is actually bad for science, because scientists are more focused on rejecting other papers, projects or ideas, instead of being open for new developments.

I'm not sure whether the variable quality of NIPS reviews is really due to the enormous popularity of the NIPS conference and the load this puts on the program committee and the reviewers, or if it is because people are actively destructive about their peers work.

But I think this leads to an interesting question about the environment in which academia exists, why it is like it is and how it could be changed to lead to different viewpoints. Because if it really is a zero sum game, then it is not surprising that those who want to play the game successfully adopt an adversarial viewpoint.

A Simplified History of Public Funding for Scientific Research

I'm really not an expert in history of science, but I guess it's not completely wrong to say that the way science is embedded and supported by society has changed dramatically in the 20th century. Beginning with the industrialization and in particular during World War II it became apparent that having a productive scientific community is absolutely vital, both to the overall growth of your economy, but also for national security. For example, the National Science Foundation was created specifically after World War II with that goal in mind.

Naturally, if it was that important, the government had to take control and set up ways to maximize the scientific productivity (because it had to make sure that the tax payer's money is used well). While in historic times, scientists were selected by personal preferences and paid by some rulers to work at their court, managing science and setting up the rules of the games more and more became a responsibility of politicians.

Applying the Market Metaphor to Science

The problem was of course that science had never been organized on this level, in particular not by non-scientists. The question basically was: How can we maximize the scientific output from a fixed amount of resources. I think this is a very important question, and I'm certain the optimal answer hasn't been found yet. Looking at how science is organized today, it seems that they resorted to transplanting a well known metaphor, that of a free market, where scientific ideas and research plans compete over grant money, slots in publications, and positions.

You can find this idea in many different aspects. For example, a grant call is like a customer expressing a certain need, and then companies (that is, scientists) can compete for that money and the one who offers the best research for that money will get it. I'm not saying that this is not a good way to select who to fund, but grant calls are used as a device to control the direction in which science progresses, and the question is whether this ensures the overall progress of science.

Another example is the way in which the scientific output is measured by citation counts. A scientists (=company) produces a scientific publication (=goods). Such publications are then put on show in journals (=stores) where other scientists can cite them (=buy them). The productivity of a scientist is then measured by the amount of goods sold where the quality of the store factors into the price paid by other scientists.

Science is not Economy

I'm not saying that this system does not work at all, but science and scientific research in particular have properties which conflict with the economic setup.

For one, as in art, there is an independent notion of quality for scientific work which is somewhat independent from whether it competes well in the market. For example, it might be a brilliant piece of work, but there is only very little intersection with what other people are working on right now. Or it is not what the funding agencies are focusing on right now. I think every scientist has at least once experienced the conflict between what he considers good scientific work and what he has to do to get grant money. Or put even differently, if everyone would just play the game (publish papers, get grant money, basically secure his position in the field), would that alone ensure scientific progress?

Moreover, what gets published in journals is mainly managed through the peer reviewing processes. Translated to economy, this means that your competitors have a lot of say in whether your products will actually see the market. Assume that before Apple sells its new laptops, the store will first ask Microsoft, Dell, and HP what they think of the laptops? It is clear that it's hard to do differently in science, because the you need a lot of expertise to judge whether a paper is worth publishing, which cannot be done by the store owner alone, but still, this setup introduces a lot of interaction not present in a truly free market.

In science, significant progress often comes from sidetracks. While most people are working on extending and applying a certain scheme, now approaches are often found elsewhere and take some time before they can enter the mainstream. However, a mass market (and given the number of scientists today, it certainly is a mass market) tends to produce products for the masses, and it is unclear whether a remote idea could really get enough support to work.

Science as a whole is progressing, I guess, but I believe it partly is because people manage to play the game and do the research which matters to them at the same time.

A Way Out?

I have to disappoint you right away, because I do not know the solution. But I think actually seeing the difference between a free market and science is important, and I hope it will make you think.

Others have been more brave in this respect. For example, people have thought about how to allocate money in a way which prevents us to just feed the "mass market" and also allow small independent research projects. Lee Smolin suggests an alternative way to distributed grant money in his book "The Trouble with physics". Siegfried Bär in his book Forschen auf Deutsch (Research in German) also suggests how to improve the way research money is distributed in German. I won't go into detail here, but both researchers think that the whole proposal writing business just takes up too much time, and the process should become much more flexible such that more researchers have time to actually do research, and also on the topics they are interested in. Part of the money should even be spent on ideas which really don't seem that relevant (but to scientists which have otherwise proven not to be crackpots).

If you in principle agree that citation count is a good measure of scientific progress, and you believe in the market, then the problem remains that the scientific publication culture is different from a real market because your competitors can veto that the customers see your product at all. The question boils down to how to improve the reviewing process. Marcus Hutter has archived an email discussion from 2001 on his homepage on what alternatives there are to the existing review process. John Langford suggests to also use preprint servers like the arxiv to get a time-stamp for your work, since you cannot be sure when you will manage to get it published.

I think people have naturally been thinking about improving the review process because in the age of the Internet, this is actually something we as scientists can actively control (as opposed to controlling funding policies). The whole system already depends on unpaid volunteers, so we should have enough manpower to run any other system as well if it gets enough support.

I'd like to repeat the idea of Geoffrey Hinton from the above email discussion. He proposed a system where people put endorsements for papers on their homepages, together with a trust network you define for yourself. You register other scientists whose opinions you trust when it comes to which papers are worth reading. In 2001, the setup was personal websites and a tool, but nowadays, you would certainly turn this into some Web2.0 application. citeulike seems to go in that direction, although the focus is currently more on organizing what papers you have read.

In essence, the goal is to make the path from company to customer much shorter, and in particular, to lessen the impact of your competition on whether your customer can buy your products, that is, cite your papers, or not.

Conclusion

So in summary, I think the framework within academia lives is not altogether bad, but there is always room for improvement. Currently, the market metaphor is often applied blindly without taking account the peculiarities of scientific research, or the scientific community as a whole. The perception that academia is basically a zero-sum game as voiced by John Langford is directly based on the idea that science is a competition over fixed resources. As I have pointed out, the main difference is that science is also a bit like art to the extent that it has it's own internal notion of quality and soundness which cannot be easily grasped or measured in terms of economic concepts. If we could manage to integrate these different aspects of science we might be eventually able to find better ways to run academia.

Update (Jan 30, 2009): I found an interesting blog post by Michael Nielsen. His basic argument is that we not only need new ways of exchanging, archiving, and searching existing knowledge, but also a radical change of culture, potentially backed by new online tools. For example, he argues that it would be highly advantageous if scientists could easily post problems they are stuck on and quickly find other scientists who are experts on those problems. However, people might only be willing to do this if such contributions would be tracked the same way peer-reviewed publications are.

Interestingly, I see some parallels between these ideas and the way we have been setting up mloss.org and the Open Source Software Track at JMLR. We have provided both the tool, and a means to make publishing open source software accountable under the old metrics - peer-reviewed publications.

On NIPS 2008

Although I came home from last year's NIPS conference more than three weeks ago, I haven't yet found time to summarize my impressions. I've found that it's always like this, first there is the jet-lag, then there is Christmas, New Year.

But maybe it's not just the closeness to the holiday season, I think it's also that NIPS is so content-rich that you really need some time to digest all that information.

Banquet Talk and Mini-Symposia

This year, in particular, because they have managed to cram in even more session into the program. They used to have some invited high-level talk during the banquet in previous years, but this year the organizers have chosen to put two technical talks and virtually 20 poster spot lights during the banquet. Actually, I'm not that sure whether this decision was wise as I and most of my colleagues felt that dinner and technical talks don't go well together. Maybe it was also my jet-lag, as I arrived on Monday afternoon, not on Sunday like some people.

The second addition where the mini-symposia on Thursday afternoon, conflicting with the earlier buses to Whistler. I attended the computational photography mini-symposium and found it very entertaining. The organizers have managed to put together a nice mix of introductory and overview talks. For example, Steve Seitz from the University of Washington had a nice talk on how to reconstruct tourist sites in Rome from pictures collected from flickr. Based on these 3d reconstruction you could go on a virtual tour of famous monuments, or compute closest paths based on where pictures were taken.

So if I had anything to say, I'd suggest to keep the mini-symposia, but replace the technical talks during the banquet by the invited talk as in previous years.

Presentations

With over 250 presentations, it's really hard to pick out the most interesting ones, and as the pre-proceedings aren't out yet (or at least not that I'm aware of), it's also hard to collect some pointers here.

There was an interesting invited talk by Pascal Van Hentenryck on Online Stochastic Combinatorial Optimization. The quintessence of his approach to optimization in stochastic environments was that often, the reaction of the environment does not depend on you the action you take, so you can build a pretty reliable model for the environment and the optimize against that.

Yves Grandvalet had a paper "Support Vector Machines with a Reject Option", which proposes a formulation of a support vector machine which can also opt to say "I don't know which class this is".

John Langford had a paper which was already a preprint at arxiv.org on sparse online learning which basically has the option to truncate certain weights if the become too small.

Every now and then there was an interesting poster with nobody attending it. For example, Patrice Bertail had a poster on "Bootstrapping the ROC Curve" which looked interesting and highly technical, but we could find nobody. At some point I started to discuss the poster with a colleague, but we had to move away from the poster after people started to cluster around us as if one of us were actually Patrice.

Michalis Titsias had an extension of Gaussian Processes in his paper "Efficient Sampling for Gaussian Process Inference using Control Variables" to the case where the model is not just additive random noise but actually depends non-linearly on the function where the Gaussian process is on. It looked pretty complicated, but it might be good to know that such a thing exists.

There were many more interesting papers, of course, but let me just list one more: "Adaptive Forward-Backward Greedy Algorithm for Sparse Learning with Linear Models" by Tong Zhang seemed like a simple method which combines feature addition with removal steps and comes with a proof (of course). I guess similar schemes exist in dozens, but this one seemed quite interesting to try out.

The question I always try to answer is whether there are some big new developments. A few years ago, everybody suddenly seemed to do Dirichlet processes and some variant of eating place. Last year (as I have been told), everybody was into deep networks. But often, I found it very hard, and this year was also one of those. Definitely no deep learning, maybe some multiple kernel learning. There were a few papers on which try to include some sort of feature extraction or construction into the learning process in a principled manner, but such approaches are (necessarily?) often quite application specific.

I also began to wonder whether a multi-track setup wouldn't be better for NIPS. This question has been discussed every now and then, always in favor of keeping the conference single-track. I think one should keep in mind that what unites machine learning as a community are new methods, because the applications are quite divers, and often very specific. For a bioinformatics guy, a talk on computer vision might not be very interesting, unless there is some generic method which is application-agnostic to a certain degree.

It seems that currently, most of the generic methods are sufficiently well researched, and people now start to think about how to incorporate automatic learning of features and preprocessing into their methods. As I said above, such methods are often a bit ad-hoc and application specific. I'm not saying that this is bad. I think one first has to try out some simple things before you can find more abstract principles which might be more widely applicable.

So maybe having a multi-track NIPS would mean that you can listen more selectively to talks which are relevant to your area of research and the list of talks wouldn't appear to be somewhat arbitrary. On the other hand, you might become even more unaware of what other people are doing. Of course, I don't know the answer, but my feeling was that NIPS is slowly approaching a size and density of presentations that something has to change to optimize the information flow between presenters and attendees.

Workshops

I've heard that some people come to NIPS only for the workshops, and I have to admit that I really like them a lot, too. Sessions are more focused topic-wise, and the smaller size of the audience invites some real interaction. Whereas I sometimes get the impression that the main conference is mostly for big-shots to meet over coffee-breaks and during poster sessions, it's in the conferences where they participate in the discussion.

We had our own workshop on machine learning and open source software which I have summarized elsewhere.

I attended the multiple kernel learning workshop which really was very interesting, because most of the speakers concluded that in most cases, multiple kernel learning does not work significantly better than a uniform average of kernels. For example, William Stafford Noble reported that he had a paper with multiple kernel learning for the Bioinformatics journal, and only afterwards decided to check whether unoptimized weights would have worked as well. He was quite surprised when the differences where statistically insignificant and concluded that he wouldn't have written the paper in that way had he known the results before.

Francis Bach also gave a very entertaining talk where he presented Olivier Chapelle's work, who couldn't attend. He did a very good job, including comments like "So on the y-axis we have the relative duality gap - I have no idea what that is", and raising his hand after his talk to have the first question.

All in all, I think this workshop was quite interesting and exiting and also important for the whole field of multiple kernel learning, basically, to see that it doesn't just work, and to try to understand better when it doesn't give the improvements hoped for and why.

Finally, many workshops were taped by videolectures.net. I've collected the links here:

• Learning from Multiple Sources
  
• Kernel Learning - Automatic Selection of Optimal Kernels
  
• Algebraic and Combinatorial Methods in Machine Learning
  
• Structured Input - Structured Output
  
• Machine Learning Open Source Software
  
• Machine Learning in Computational Biology
  
• Causality: Objectives and Assessment
  
• New Challenges in Theoretical Machine Learning: Learning with Data-dependent Concept Spaces
  
• Optimization for Machine Learning
  
• Beyond Search: Computational Intelligence for the Web
  

On my way to NIPS 2008

Next week is the annual NIPS conference in Vancouver. In case you don't know, it's one of the most important annual conferences in the area of machine learning. It's actually its 22nd installment, and while the full title (Neural Information Processing Systems) hits at the beginnings of the fields with artificial neural networks, such methods cover only a small percentage of the presented papers nowadays.

Together with Soeren Sonnenburg and Cheng Soon Ong we have organized a workshop on machine learning open source software. I'm pretty excited about our program, I only fear that our decision to drop the coffee breaks in favor of a few additional talks will backfire severly. But we'll see.

I plan to use my twitter account this year to cover the workshop, so if you're interested, make sure to have a look. Most importantly, I will cover our workshop so that you can see how far we are behind schedule. ;)

By the way, the picture above shows the swimming gas station. It mostly services seaplanes, and you have a very nice view of it from the top floor of the hotel where the NIPS conference takes place.

Java Integration in JRuby

Update: See also the updated entry in the JRuby wiki here.

JRuby has some very nice features to make accessing Java easy, but unfortunately, documentation about these features is a bit hard to come by. Existing documentation is sometimes a bit out-dated, or doesn't cover all features. The ultimate documentation is of course the source code itself, in particular rspec code to be found in spec/java_integration in the jruby-trunk, but reading source code is maybe not the first choice for everybody when trying to learn a new feature.

Fortunately, Java integration in JRuby is actually pretty good and useful. JRuby does quite a few tricks to make Java classes feel more Ruby-like, for example, by translating between javaNamingSchemes and ruby_naming_schemes, or by automagically converting blocks to implementations of the appropriate Java interfaces, to the effect that you can pass a block to a Java method whenever it expects a Runnable, for example.

I personally think there is great potential in this kind of bilingual development approach which uses Java for all the computationally expensive details and Ruby for the dynamic high-level plumbing. Compared with the Ruby/C alternative, probably based on tools like Swig for the plumbing, JRuby/Java is much easier and cleaner. For example, you can easily deal with Java exceptions on the Ruby side, and even if you don't you get a call stack with Ruby and Java classes happily mixed when an error occurs.

So I hope that the following is both helpful and correct enough to be of use for others.

The Basics

The first thing to do is to require 'java'. I'm not sure if this is strictly necessary as many things also work without that, but I guess it's safe to do this for the future.

The first question is of course how to access Java classes.

There seem to be several different alternatives for naming a Java class. The most "ruby-esque" way looks like this: java.lang.System becomes Java::JavaLang::System. The prefix is always Java::, followed by the package names with dots turned into CamlCase notation and finally, the class itself.

If the top-level package is java, javax, com, or org, you can also access it just like in Java, for example, by typing java.lang.System. If you want to have this functionality for your own packages as well, because they start (for example) with edu, you can use the following code taken from path-to-jruby-installation/site_ruby/1.8/builtin/javasupport/core_ext/kernel.rb:

def edu
  JavaUtilities.get_package_module_dot_format('edu')    
end

Or, which is even simpler

def edu
  Java::Edu
end

Java's primitive types can be found directly in the Java module: For example, long is Java::long (but not java.long). Actually, I cannot think of too much you could do with these objects. But you need them when you want to create primitive arrays. For example, Java::long[10].new creates a new array of long integer values.

Loading jar-files

If you want to access classes beyond Java's own runtime, you have to load the jar file in JRuby. One way to do this is to explicitly require the jar-file. You can supply a full path, or you can just pass the jar file which is then searched according to the RUBYLIB environment variable.

Alternatively, you can put the jar-file into your CLASSPATH. Then, you can directly access your classes without an explicit require.

Calling Java Methods

You can then access the methods just as in Java, for example

java.lang.System.currentTimeMillis

but JRuby also provides transformed method names to make them more similar to Ruby naming conventions. The typical CamelCase is converted to underscores. The call above can therefore also be written as

java.lang.System.current_time_millis

Moreover, JRuby maps the bean conventions as follows

obj.getSomething()        becomes   obj.something
obj.setSomething(x)       becomes   obj.something = x
obj.isSomething()         becomes   obj.something?

When accessing methods, or constants, you have to follow the usual Ruby conventions. That is, constants have to be accessed by Class::Constant (for example, JFrame::EXIT_ON_CLOSE), and it seems you cannot access member variables of objects in Ruby outside of the object's methods, even if it is declared public in Java.

For each java object there are number of methods defined, but most of them aren't documented anywhere. I think the more useful ones are java_class (because the plain class only returns some JRuby-side proxy object) and java_kind_of?, which I assume is like instanceof for Java objects.

Conversion of Parameters

When calling a Java method, JRuby goes through some pain of mapping JRuby types to Java types. For example, if necessary, a Fixnums is also converted to a double, and so on. If this fails and JRuby does not find a corresponding method, it prints an error message along the lines of "no foo with arguments matching [class org.jrub.RubyObject] on object #<Java::...>". Actually, I think JRuby could be a bit more helpful here and tell you what class the ruby object was. In any case, when this happens it means that the types you wanted to pass couldn't be converted.

JRuby does not automatically try to convert arrays to Java arrays. You have to use the to_java method for that. By default, this constructs Object[] arrays. if you want to construct arrays with a given primitive type, you pass an argument to to_java which can either be a symbol like :long or :double, or a class. For example,

[1,2,3].to_java              becomes an Object[]
[1,2,3].to_java :long        becomes long[]
[1,2,3].to_java(Java::long)  same thing

Importing Classes and Including Packages

Typing the full name quickly gets old, so you can import classes into modules, and at the top-level.

You might run into slight difficulties with how to name a class. These functions actually expect a string, but you can also pass the Java-style fully qualified class name (that is, with package), if the package starts with java, javax, or one of the other default package names. However, currently (at least as of 1.1.5) it seems that you cannot use the Java::... notation if the top-level package isn't one of those for which you could have used the Java-style name anyway. So I guess it's save to go with the strings in that cases.

This means that you can do

import java.lang.String

but not

import Java::EduSomeuniversity::SomeClass

Instead, you should type

import 'edu.someuniversity.SomeClass'

or do the "def edu; Java::Edu; end" hack and then "import edu.someunversity...".

While you can import classes into modules and at top-level, you can include whole packages into classes or modules. For example,

module E
  include_package javax.swing
end

Makes all of Swing available in E and also as, for example, E::JFrame. At least it used to be like this, currently (in 1.1.5) E::JFrame gives an odd "wrong number of arguments (1 for 0)" error... .

Currently, there is no way to import whole packages at the top-level (or at least none I'm aware of). Taking the short-cut through a module and then including the module at top-level currently also doesn't work. You have to access the class first through the module before you can use it a top-level.

Implementing Java Interfaces and Adding Syntactic Sugar to Java Classes in Ruby

Classes are always open in Ruby. This means that you can add methods later just be re-opening the class again with a class Name ... end statement. This is a nice way to add, for example, syntactic sugar to your Java classes like operators, or other methods like each to make your classes behave more Ruby-like.

Of course, these additions are only on the Ruby side, and not visible from the Java side. You have to remember that Java is a statically typed language and these run-time additions aren't visible. Still I found this feature to be tremendously useful for making Java classes more usable on the JRuby side.

What is possible, though, is to implement a Java interface with a JRuby class and pass that new class back to Java. The preferred way to do this is by including the interface in the class definition:

class MyLittleThread
  include java.lang.Runnable
  
  def run
    10.times { puts "hello!"; sleep 1 }
  end
end

Then you can start this thread with

java.lang.Thread.new(MyLittleThread.new).run

If the interface has only a single method, you can even pass a block which then gets automatically converted:

java.lang.Thread.new { 10.times { puts "hello!"; sleep 1} }.start

I think this was not possible in earlier versions, but you can also subclass a Java class and pass it back to Java code expecting the super class. This is actually pretty cool, as it means that you can freely intertwine Ruby and Java code.

Collections, Regexs, and so on.

JRuby already adds some syntactic sugar on the JRuby side for Java collections, regular expressions and so on, to make them more Ruby-like. For example, Enumerable is mixed in into java.util.Collection. In addition, JRuby also defines some additional methods like <<, or +. For all the details, have a look at the files in JRUBY_DIR/lib/ruby/site_ruby/1.8/builtin/java/.

Exceptions

There isn't much to say here, only that it's possible to catch Java exceptions using Ruby's begin ... rescue ... end construction.

Summary

We've seen that there are some very nice features in the JRuby/Java integration, namely coercing some basic types, automatic conversion between Java and JRuby naming schemes, automatic translation of Bean patterns. You can even implement Java interfaces, providing callbacks to Java code in JRuby code.

Some things are maybe missing (or I haven't figured them out yet) like a way to import whole packages at the top-level. Sometimes I wished that the conversion between Ruby and Java objects would also be more configurable. But given the enormous speed at which JRuby is progressing, I'm sure that these oddities will be smoothed out soon.

On Relevant Dimensions in Kernel Feature Spaces

I finally found some time to write a short overview article about our latest JMLR paper. It discusses some interesting insights into the dimensionality of your data in a kernel feature space when you only consider the information relevant to your supervised learning problem. The paper also presents a method for estimating this dimensionality for a given kernel and data set.

The overview also contains a few lines of matlab code with which you can have a look at the discussed effect yourself. It all boils down to pictures like these:



What you see here is the contribution of individual kernel PCA components to the Y samples, divided by the smooth part (red), and the noise (blue), on a toy data set, of course. Kernel PCA components are sorted by decreasing variance. What you can see is that the smooth part is contained in the leading kernel PCA components, while the later components only contain information relevant for the noise. This means that even in infinite-dimensional feature spaces, the actual information is contained in a low-dimensional feature space.

If you are looking for more information, have a look at the overview article, the paper, or a video lecture I gave together with Klaus-Robert Müller in Eindhoven last year. There is also some software available.