New ExpectationMaximization Algorithms
 
AutoBayes can already derive fairly sophisticated EM (ExpectationMaximization)
algorithms for new userspecified statistical models. In addition to standard
textbook examples such as the EM algorithm for mixtures of Gaussians,
AutoBayes was able to reproduce four researchlevel EM algorithms, i.e.
EM algorithms appearing in research papers in recent years, such as a
nested EM algorithm where the Mstep itself is solved with an EM algorithm.
(Gray, Fischer, Schumann and Buntine, Automatic Derivation of
Statistical Algorithms: The EM Family and Beyond [pdf], [ps] NIPS 2002.)
Next steps.
I started to extend the capabilities of the system with several other
algorithmic schemas, including particle filterlike algorithms,
kmeanslike algorithms, and basic kdtreebased algorithms. However,
most of these are in a partial state of completion for the moment. Wray
has done at least one variational method and had been thinking about
expectationpropagation, last I heard.
An impending collaboration with
Ashish Agarwal may provide a basis for this system in category theory.


AutoBayes:
Automatic Derivation of Algorithms
 
Q: "Okay, I want to use stateoftheart, computationallyefficient
algorithms for my statistical model (either for learning/estimating it
or using it to predict)  but do I have to become an expert in the
latest algorithms or numerical methods to do that? No one has
published a paper or released software applying the most advanced
existing computational methods for exactly my statistical model." A:
It is possible to automatically apply an algorithmic
principle to a new statistical model to derive an algorithm for
it. The resulting specialized algorithm may or may not have existed
before.
In recent years, research in parametric learning methods has seen the
emergence of a handful of general algorithmic principles, such as the
EM algorithm, which can be applied in many different model contexts
and combined with other algorithmic patterns, or 'schemas', to obtain
a rich family of parametric learning methods. Many current or recent
researchlevel learning methods are in fact applications of such known
algorithm recipes to different model distributions and model
structures. The process of deriving such algorithms can in fact be
automated. The AutoBayes system takes a highlevel statistical
model specification given by the user, represents it internally as a
graphical model, then uses symbolic transformation techniques based on
computer algebra and schemabased theorem proving to derive an
efficient specialized algorithm for learning that model, and finally generates
executable C or Matlab code implementing that algorithm. AutoBayes
is the only existing system with these capabilities, to my knowledge,
for deriving novel algorithms in machine learning or in any domain.
The AutoBayes Project
was begun by Wray Buntine
in 1995 and is led by Bernd Fischer and
Johann Schumann
of NASA Ames. I joined the project in 2001 with the goal of pushing
AutoBayes to the point of becoming a serious tool for the machine
learning research community. We made a push of progress in 2001 but
currently things are stalled.

