Connectionists: Software available: Kernel multiple logistic regression. Incomplete Cholesky decomp. Updating Cholesky factor

[Matthias Seeger]

Dear colleagues, I have made available some software at
http://www.kyb.tuebingen.mpg.de/bs/people/seeger [follow "Software"]
which I hope will be of use to Machine Learning and Statistics
practitioners. The code is for Matlab (MEX)
and is made available under the GNU public license. It makes use of the
BLAS, LAPACK (contained in
Matlab), and LINPACK whenever possible. I wrote it under Linux and did not
test it under any other
system.

1) Kernel Multiple Logistic Regression

Efficient implementation for MAP approximation to multi-class Gaussian
process (aka kernel) model. Runs
in O(n^2 C) (n datapoints, C classes) with full kernel matrices, or in O(n d
C), d<<n, if rank-d approximations
to kernel matrices are used (see "Incomplete Cholesky" below). Very easy to
extend to your favourite kernel.
No provision for fitting kernel and other hyperparameters in the moment.

Details are in:
http://www.kyb.tuebingen.mpg.de/bs/people/seeger/papers/kerlogregr.pdf

2) Incomplete Cholesky Decomposition for Dense (Kernel) Matrices

Simple automatic way of getting a low-rank approximation to a kernel matrix,
has been used quite a bit
in Machine Learning recently. Comes with two popular kernels, and it is very
easy to extend it to your
favourite kernel. Use it f.ex. to run multi-class kernel logistic regression
(1) in time linear in number of
datapoints and number of classes.

3) Updating Cholesky Decomposition for Simple Changes of System Matrix

Computing, maintaining, and updating inverses using the
Sherman-Morrison-Woodbury formula are
bombshells in that properties of numerical stability are very poor. You can
usually use the
Cholesky decomposition just as well. Here is useful code for
updating/downdating a factor for simple
changes of the matrix (rank 1, permutation).

Check out
http://www.kyb.tuebingen.mpg.de/bs/people/seeger/papers/cholupdate.pdf for
how this works.


Enjoy! Note that I cannot answer any queries about problems of
compiling/using/extending this code,
whatsoever.
--
Matthias Seeger Tel.: ++49-7071-601583
Max Planck Institute for Biological Cybernetics
http://www.kyb.tuebingen.mpg.de/bs/people/seeger
P.O. Box: 21 69, 72012 Tuebingen, Germany