Musings about machine learning and other things

A matlab code for minimizing a multivariate function whose partial derivatives are available by Carl Rasmussen is downloadable from here . The routine looks pretty efficient, at least on the classical Rosenbrock function.

The following compressibility concept is introduced by Harnik and Naor in their recent paper : Given a function $f$ over some domain, a compression algorithm for $f$ should efficiently compress an input $x$ in a way that will preserve the information needed to compute $f(x)$. Note that if $f$ is available (and efficiently computable) then compression is trivial as then $y=f(x)$ will serve the purpose of the compact representation of $x$. Actually, the concept was originally studied in the framework of NP decision problems where unless $P=NP$ $f$ is not efficiently computable, hence the trivial solution is not available. I am wondering if this compressibility notion could be used in learning theory or function approximation? Consider e.g. classification problems so that the output of $f$ is $\{0,1\}$. In order to prevent the trivial solution we may require that $x$ be compressed to some $y$ such that for some fixed (efficiently computable) function $g$, $f(g(y))=f(x)$. We do not requir...

I added the following two lines to the header section of the template of this page: <script type="text/javascript" src="http://www.maths.nottingham.ac.uk/personal/drw/LaTeXMathML.js"> </script> Suddenly, I can type (almost) anything in latex, e.g. \$a_n\$ becomes $a_n$. Fancy! (If you do not see anything fancy then either Javascript is disabled in your browser or you are using Internet Explorer without MathML support. In the latter case you may want to download MathPlayer by DesignScience.) Many thanks for Peter Jipsen the folks who developed ASCIIMathML , which serves as the basis of LaTeXMathML by Douglas R. Woodall . Examples showing what is possible with LatexMathML can be found here . This is an indispensable tool! The nice thing is that MathML is scaleable: $E=m c^2$

The paper can be found here . The authors are Stephen Boyd , Persi Diaconis and Lin Xiao. I have found the paper while looking at the papers by Perso Diaconis , a notable mathematician and magician. The paper talks about exactly what the title suggests: You are given a finite graph and you can set up a random walk on this graph by determining the transition probabilities between vertices that are connected by an edge. The walk must be symmetric so that the uniform distribution is a stationary distribution of this walk. Assuming that the associated Markov chain is irreducible and symmetric, the state distribution will converge to the uniform. The task is to maximize the rate of convergence of this. The solution is the Fastest Mixing Markov Chain on the graph (FMMC). The authors show that this is a convex optimization problem and give a polynomial algorithm (based on semidefinite programming) to find the solution. A subgradient method is given that can be more effective for larger graphs...

I found the paper posted by Marcus Hutter on arxiv quite interesting. The paper is about model (or rather predictor) selection. The idea is a familiar one, but the details appear to be novel: You want to find a model which yields small loss on the dataset available, while yielding a larger loss on most other datasets. Classification : The simplest case is when we consider supervised learning and the target set is finite. Then you can count the number of target label variations such that the predictor's loss is smaller than its loss when the true targets are used. This idea sounds very similar to the way Rademacher complexity works, see e.g. the paper of Lugosi and Wegkamp, where a localized version of Rademacher complexity is investigated. Regression : For continuous targets you can use a grid with an increasing resolution (assume that the range of targets is bounded) and count the number of gridpoints such that the predictor's loss is less than its loss on the true dataset. ...

I am struggling with organizing the notes I make after lectures or after reading a paper. Hence I will experiment with this fancy way of keeping track of my thoughts. Of course, I will be happy to receive feedback from the occasional readers. We will see how well it goes!