I’m very happy to announce that my latest paper just came out at the Journal of Machine Learning research. Actually, it is the second half of work which developed out of my Ph.D. thesis. The other paper came out almost two years go, which tells you a bit about how long reviews can take if you’re unlucky.
Anyway, from a theoretical point of view, the first paper studies eigenvalues of the kernel matrix while the second one studies eigenvectors, and both derive approximation bounds between the eigenvalues and the eigenvalues you’d get as the number of training points tends to infinity. These bounds have the important property that they scale with the eigenvalue under consideration. You don’t have one bound for all eigenvalues, but instead a bound which becomes smaller as the eigenvalue becomes smaller. This means that you won’t have the same bound on eigenvalues of the order of $10^3$ and $10^{-6}$, but actually, the error will be much smaller on the smaller eigenvalue. If you run numerical simulations, you will immediately see this, but actually proving this was a bit harder.
What this practically means is a different story, and I personally
think it is actually quite interesting (of course :)): If you have
some learning problem (a supervised one), and you take a kernel and
start to train you support vector machine, then these results tell you
that even if the kernel feature space might be very high-dimensional,
the important information is contained in a low-dimensional subspace,
which also happens to be spanned by the leading kernel PCA components.
In other words, when you choose the right kernel, you can do a PCA in feature space, and just consider a space spanned by the directions having largest variance. In essence, if you choose the correct kernel, you are dealing with a learning problem in a finite-dimensional space, which also explains why these methods work so well.
The “old” story was that you’re using hypothesis classes which have finite VC dimension, and then everything’s fine. This is still true, of course, but these new results also show why you can expect low-complexity hypothesis classes to work at all: Because a good kernel transforms the data such that the important information is contained in a low-complexity subspace of the feature space.
So I hope I could make you a bit interested in the paper. I’m trying to put together a bit more of an overview on my home page, so make sure to check that out as well in a week from now.
Well, I decided not to blog about Google Chrome. We can’t all be non-conformists, right?
I mean, It’s Only A Browser™, after all.
Then again, I wonder how fast that V8 Javascript machine really is… .
If you’re still interested in an not entirely glorifying post, you might want to check out the post by JRuby’s Charles Nutter.
And now excuse me while I go shopping.
One of the projects I’m currently working on is a fast linear algebra matrix library for Java. I know that there already exist some alternatives, but I usually found that they were either no longer actively maintained or their performance was much slower than what, for example, matlab would give you.
So in principle, all I wanted is a matrix library which directly interfaces with some fast BLAS or LAPACK library, for example ATLAS, but hides all of the Fortran greatness behind a nice object-oriented wrapper. Turns out that something like that does not seem to exist, so we started to work on our own little library called jBLAS which is going to be released soon.
Anyway, while working on that library, I got a bit worried about the performance of the stuff I’m doing in Java. These are mainly element-wise operations like multiplying all elements of a matrix with the corresponding elements of another matrix.
Since we’re interfacing to C (actually Fortran) code a lot, all of the
matrix data is stored in direct buffers, in particular
java.nio.DoubleBuffer,
and I wondered how their put and get access methods compared to array
access and of course to C. So I wrote a little program in eclipse
which did just that and compared the outcome with what I got in C, and
to my suprise, Java was very much on par, and the performance
differences between accessing arrays and direct buffers was very
small.
But when I tried to repeat the results at home, I got very different numbers, both for arrays and for direct buffers, which suddenly took five times longer than arrays. At first I suspected that the different processor maker was the issue, but after some more tweaking I found out that again to my great surprise, the issue was the compiler.
It turns out that the eclipse compiler ecj is much better at compiling my benchmark than Sun’s own javac. To see this for yourself, here is my benchmark:
import java.nio.*;
class TicToc {
private long savedTime;
public void tic(String msg) {
System.out.print(msg);
System.out.flush();
saveTime();
}
public void tic(String fmt, Object... args) {
System.out.printf(fmt, args);
saveTime();
}
private void saveTime() {
savedTime = System.currentTimeMillis();
}
public void toc() {
long elapsedTime = System.currentTimeMillis() - savedTime;
System.out.printf(" (%.3fs)\n", elapsedTime / 1000.0);
}
}
public class Main {
private static void copyArray(int size, int iters) {
double[] source = new double[size];
double[] target = new double[size];
for (int i = 0; i < iters; i++)
for (int j = 0; j < size; j++)
target[j] = source[j];
}
private static DoubleBuffer createBuffer(int size, ByteOrder bo) {
return ByteBuffer.allocateDirect(Double.SIZE / Byte.SIZE * size)
.order(bo).asDoubleBuffer();
}
private static void copyDoubleBuffer(int size, int iters, ByteOrder bo) {
DoubleBuffer source = createBuffer(size, bo);
DoubleBuffer target = createBuffer(size, bo);
for (int i = 0; i < iters; i++)
for (int j = 0; j < size; j++)
target.put(j, source.get(j));
}
public static void main(String[] args) {
TicToc t = new TicToc();
final int SIZE = 1000;
final int ITERS = 1000000;
t.tic("copying array of size %d %d times...", SIZE, ITERS);
copyArray(SIZE, ITERS);
t.toc();
t.tic("copying DoubleBuffer of size %d %d times... (LITTLE_ENDIAN)", SIZE, ITERS);
copyDoubleBuffer(SIZE, ITERS, ByteOrder.LITTLE_ENDIAN);
t.toc();
}
}So let’s compare the run-times of these programs using the latest Java JDK 6 update 7 and the stand-alone eclipse compiler 3.4.
Then, I compile the source with
javac Main.javaand run it with java -cp . Main:
copying array of size 1000 1000000 times... (2.978s)
copying DoubleBuffer of size 1000 1000000 times... (LITTLE_ENDIAN) (4.291s)
Now the same with the eclipse compiler: I compile it with
java -jar ..path_to_jar../ecj-3.4.jar -1.6 Main.javaand get the following results:
copying array of size 1000 1000000 times... (0.547s)
copying DoubleBuffer of size 1000 1000000 times... (LITTLE_ENDIAN) (0.633s)
Note that both files only differ in the bytecode, but the eclipse compiler manages to produce code which is about 6 times faster, and which is only slightly slower for the direct buffer.
I’ll have to look into this quite some more, but if this is true, this is pretty amazing!