%-------------Publications-of-Marcus-Hutter-2010--------------%
%-------------Publications-of-Marcus-Hutter-2009--------------%
@InProceedings{Hutter:09mdltvp,
author = "Marcus Hutter",
title = "Discrete {MDL} Predicts in Total Variation",
booktitle = "Advances in Neural Information Processing Systems 23 ({NIPS'09})",
xvolume = "??",
pages = "817--825",
_editor = "Y. Bengio and D. Schuurmans and J. Lafferty and C. K. I. Williams and A. Culotta",
xpublisher = "??",
xaddress = "??",
_month = dec,
year = "2009",
bibtex = "http://www.hutter1.net/official/bib.htm#mdltvp",
url = "http://arxiv.org/abs/0909.4588",
pdf = "http://www.hutter1.net/ai/mdltvp.pdf",
ps = "http://www.hutter1.net/ai/mdltvp.ps",
latex = "http://www.hutter1.net/ai/mdltvp.tex",
slides = "http://www.hutter1.net/ai/smdltvp.pdf",
project = "http://www.hutter1.net/official/projects.htm#mdl",
xdoi = "",
xissn = "",
keywords = "minimum description length; countable model class;
total variation distance; sequence prediction;
discriminative learning; reinforcement learning.",
abstract = "The Minimum Description Length (MDL) principle selects the model
that has the shortest code for data plus model. We show that for a
countable class of models, MDL predictions are close to the true
distribution in a strong sense. The result is completely general. No
independence, ergodicity, stationarity, identifiability, or other
assumption on the model class need to be made. More formally, we
show that for any countable class of models, the distributions
selected by MDL (or MAP) asymptotically predict (merge
with) the true measure in the class in total variation distance.
Implications for non-i.i.d. domains like time-series forecasting,
discriminative learning, and reinforcement learning are discussed.",
znote = "Acceptance rate: 263/1105 = 24\%",
}
@InProceedings{Hutter:09wheel,
author = "M. Hutter and N. Brewer",
_author = "Marcus Hutter and Nathan Brewer",
title = "Matching 2-D Ellipses to 3-D Circles with Application to Vehicle Pose Estimation",
booktitle = "Proc. 24th Conf. on Image and Vision Computing New Zealand ({IVCNZ'09})",
pages = "153--158",
_editor = "Donald Bailey",
publisher = "IEEE Xplore",
address = "Wellington, New Zealand",
_month = nov,
year = "2009",
bibtex = "http://www.hutter1.net/official/bib.htm#wheel",
url = "http://arxiv.org/abs/0912.3589",
pdf = "http://www.hutter1.net/ai/wheel.pdf",
latex = "http://www.hutter1.net/ai/wheel.zip",
slides = "http://www.hutter1.net/ai/swheel.pdf",
project = "http://www.hutter1.net/official/projects.htm#icar",
doi = "10.1109/IVCNZ.2009.5378421",
issn = "2151-2205",
keywords = "computer vision; image recognition/processing; ellipse detection; 3d models;
2d-ellipse to 3d-circle matching; single image pose identification;
wheel detection; 3d vehicle models.",
abstract = "Finding the three-dimensional representation of all or a part of a
scene from a single two dimensional image is a challenging task. In
this paper we propose a method for identifying the pose and location
of objects with circular protrusions in three dimensions from a
single image and a 3d representation or model of the object of
interest. To do this, we present a method for identifying ellipses
and their properties quickly and reliably with a novel technique
that exploits intensity differences between objects and a geometric
technique for matching an ellipse in 2d to a circle in 3d.
We apply these techniques to the specific problem of determining the
pose and location of vehicles, particularly cars, from a single
image. We have achieved excellent pose recovery performance on
artificially generated car images and show promising results on real
vehicle images. We also make use of the ellipse detection method to
identify car wheels from images, with a very high successful match
rate.",
znote = "Acceptance rate: 79/142 = 56\%",
}
@Article{Hutter:09mbpcrcode,
author = "Paola M.V. Rancoita and Marcus Hutter,
title = "mBPCR: A Package for DNA Copy Number Profile Estimation",
journal = "BioConductor -- Open Source Software for BioInformatics",
number = "0.99",
pages = "1--25",
_month = oct,
year = "2009",
bibtex = "http://www.hutter1.net/official/bib.htm#mbpcrcode",
url = "http://www.bioconductor.org/packages/devel/bioc/html/mBPCR.html",
pdf = "http://www.hutter1.net/ai/mbpcrcode.pdf",
project = "http://www.hutter1.net/official/projects.htm#big",
code = "http://www.hutter1.net/ai/mbpcrcode.tar.gz",
keywords = "Bayesian regression, exact polynomial algorithm, piecewise constant function,
mBPCR, DNA copy number estimation, micro arrays, genomic aberrations, R package."
abstract = "The algorithm mBPCR is a tool for estimating the profile of the
log2ratio of copy number data. The procedure is a Bayesian piecewise
constant regression and can be applied, generally, to estimate any
piecewise constant function (like the log2ratio of the copy number
data). The algorithm has been implemented in R and integrated into
bioconductor, an open source software for bioinformatics. This
document describes how to use the mBPCR bioconductor package in
general and on several examples.",
support = "SNF grant 205321-112430",
}
@Article{Hutter:09phimdpx,
author = "Marcus Hutter",
title = "Feature Reinforcement Learning: Part {I}: Unstructured {MDP}s",
journal = "Journal of Artificial General Intelligence",
volume = "1",
pages = "3--24",
_month = oct,
year = "2009",
bibtex = "http://www.hutter1.net/official/bib.htm#phimdpx",
url = "http://arxiv.org/abs/0906.1713",
pdf = "http://www.hutter1.net/ai/phimdpx.pdf",
ps = "http://www.hutter1.net/ai/phimdpx.ps",
latex = "http://www.hutter1.net/ai/phimdpx.tex",
slides = "http://www.hutter1.net/ai/sphimdp.pdf",
project = "http://www.hutter1.net/official/projects.htm#uai",
issn = "1946-0163",
keywords = "Reinforcement learning; Markov decision process;
partial observability; feature learning; explore-exploit;
information \& complexity; rational agents.",
abstract = "General-purpose, intelligent, learning agents cycle through
sequences of observations, actions, and rewards that are complex,
uncertain, unknown, and non-Markovian. On the other hand,
reinforcement learning is well-developed for small finite state
Markov decision processes (MDPs). Up to now, extracting the right
state representations out of bare observations, that is, reducing
the general agent setup to the MDP framework, is an art that
involves significant effort by designers. The primary goal of this
work is to automate the reduction process and thereby significantly
expand the scope of many existing reinforcement learning algorithms
and the agents that employ them. Before we can think of mechanizing
this search for suitable MDPs, we need a formal objective criterion.
The main contribution of this article is to develop such a
criterion. I also integrate the various parts into one learning
algorithm. Extensions to more realistic dynamic Bayesian networks
are developed in Part II. The role of POMDPs is also considered there.",
}
@Article{Hutter:09aixiopen,
author = "Marcus Hutter",
title = "Open Problems in Universal Induction \& Intelligence",
journal = "Algorithms",
volume = "3",
number = "2",
pages = "879--906",
_month = jul,
year = "2009",
bibtex = "http://www.hutter1.net/official/bib.htm#aixiopen",
url = "http://arxiv.org/abs/0907.0746",
pdf = "http://www.hutter1.net/ai/aixiopen.pdf",
ps = "http://www.hutter1.net/ai/aixiopen.ps",
latex = "http://www.hutter1.net/ai/aixiopen.tex",
project = "http://www.hutter1.net/official/projects.htm#uai",
doi = "10.3390/a2030879",
issn = "1999-4893",
keywords = "Kolmogorov complexity; information theory;
sequential decision theory; reinforcement learning;
artificial intelligence; universal Solomonoff induction;
rational agents.",
abstract = "Specialized intelligent systems can be found everywhere: finger
print, handwriting, speech, and face recognition, spam filtering,
chess and other game programs, robots, et al. This decade the first
presumably complete {\em mathematical} theory of artificial
intelligence based on universal induction-prediction-decision-action
has been proposed. This information-theoretic approach solidifies
the foundations of inductive inference and artificial intelligence.
Getting the foundations right usually marks a significant progress
and maturing of a field. The theory provides a gold standard and
guidance for researchers working on intelligent algorithms. The
roots of universal induction have been laid exactly half-a-century
ago and the roots of universal intelligence exactly one decade ago.
So it is timely to take stock of what has been achieved and what
remains to be done. Since there are already good recent surveys, I
describe the state-of-the-art only in passing and refer the reader
to the literature. This article concentrates on the open problems in
universal induction and its extension to universal intelligence.",
}
@InProceedings{Hutter:09cnloh,
author = "Paola M.V. Rancoita and Marcus Hutter and Francesco Bertoni and Ivo Kwee",
title = "Bayesian Joint Estimation of {CN} and {LOH} Aberrations",
booktitle = "Proc. 3rd International Workshop on Practical Applications of Computational Biology & Bioinformatics ({IWPACBB'09}) ",
volume = "5518",
series = "LNCS",
pages = "1109--1117",
_editor = "S. Omatu et al.",
publisher = "Springer",
address = "Spain",
_month = jun,
year = "2009",
url = "http://iwpacbb.usal.es/",
pdf = "http://www.hutter1.net/ai/cnloh.pdf",
poster = "http://www.hutter1.net/ai/scnloh.pdf",
http = "http://iwpacbb.usal.es/",
doi = "10.1007/978-3-642-02481-8_168",
issn = "0302-9743",
isbn = "978-3-642-02480-1",
keywords = "Bayesian regression; piecewise constant function;
change point problem; DNA copy number estimation; LOH estimation",
abstract = "SNP-microarrays are able to measure simultaneously both copy number
and genotype at several single nucleotide polymorphism positions.
Combining the two data, it is possible to better identify genomic
aberrations. For this purpose, we propose a Bayesian piecewise
constant regression which infers the type of aberration occurred,
taking into account all the possible influence in the microarray
detection of the genotype, resulting from an altered copy number
level. Namely, we model the distributions of the detected genotype
given a specific genomic alteration and we estimate the
hyper-parameters used on public reference datasets.",
support = "Swiss National Science Foundation grant 205321-112430;
Oncosuisse grants OCS-1939-8-2006 and OCS-02296-08-2008;
Cantone Ticino ``Ticino in rete'' grant;
Fondazione per la Ricerca e la Cura sui Linfomi (Lugano, Switzerland)",
}
@InProceedings{Hutter:09ldof,
author = "Ke Zhang and Marcus Hutter and Warren Jin",
title = "A New Local Distance-based Outlier Detection Approach for Scattered Real-World Data",
booktitle = "Proc. 13th Pacific-Asia Conf. on Knowledge Discovery and Data Mining (PAKDD'09)",
series = "LNAI",
volume = "5467",
pages = "813--822",
_editor = "T. Theeramunkong and B. Kijsirikul and N. Cercone and H. T. Bao",
publisher = "Springer",
address = "Bangkok",
_month = apr,
year = "2009",
bibtex = "http://www.hutter1.net/official/bib.htm#ldof",
url = "http://arxiv.org/abs/0903.3257",
pdf = "http://www.hutter1.net/ai/ldof.pdf",
ps = "http://www.hutter1.net/ai/ldof.ps",
latex = "http://www.hutter1.net/ai/ldof.zip",
slides = "http://www.hutter1.net/ai/sldof.pdf",
project = "http://www.hutter1.net/official/projects.htm#???",
doi = "10.1007/978-3-642-01307-2_84",
issn = "0302-9743 ",
isbn = "978-3-642-01306-5",
keywords = "local outlier; scattered data; k-distance; KNN; LOF; LDOF.",
abstract = "Detecting outliers which are grossly different from or inconsistent
with the remaining dataset is a major challenge in real-world KDD
applications. Existing outlier detection methods are ineffective on
scattered real-world datasets due to implicit data patterns and
parameter setting issues. We define a novel ``Local
Distance-based Outlier Factor'' (LDOF) to measure the outlier-ness
of objects in scattered datasets which addresses these issues. LDOF
uses the relative location of an object to its neighbours to
determine the degree to which the object deviates from its
neighbourhood.
Properties of LDOF are theoretically analysed including LDOF's lower
bound and its false-detection probability, as well as parameter
settings. In order to facilitate parameter settings in real-world
applications, we employ a top-n technique in our outlier detection
approach, where only the objects with the highest LDOF values are
regarded as outliers. Compared to conventional approaches (such as
top-n KNN and top-n LOF), our method top-n LDOF is more
effective at detecting outliers in scattered data. It is also easier
to set parameters, since its performance is relatively stable over a
large range of parameter values, as illustrated by experimental
results on both real-world and synthetic datasets.",
znote = "Acceptance rate: 111/338 = 33\%",
}
@Article{Hutter:09alttcs,
author = "Marcus Hutter and Rocco A. Servedio",
title = "ALT'07 Special Issue",
journal = "Theoretical Computer Science",
_editor = "M. Hutter and R. A. Servedio",
volume = "410",
number = "19",
pages = "1747--1748/1912",
_month = apr,
year = "2009",
bibtex = "http://www.hutter1.net/official/bib.htm#alttcs",
http = "http://www.sciencedirect.com/science?_ob=PublicationURL&_tockey=%23TOC%235674%232009%23995899980%231003105%23FLP%23&_cdi=5674&_pubType=J&view=c&_auth=y&_acct=C000050221&_version=1&_urlVersion=0&_userid=10&md5=90cfd70be9f8d46fd6eb6f7b8370ddec",
pdf = "http://www.hutter1.net/ai/alttcs.pdf",
ps = "http://www.hutter1.net/ai/alttcs.ps",
latex = "http://www.hutter1.net/ai/alttcs.tex",
xproject = "http://www.hutter1.net/official/projects.htm#???",
doi = "10.1016/j.tcs.2009.01.008",
issn = "0304-3975",
keywords = "algorithmic learning theory, special issue, preface",
abstract = "This special issue contains expanded versions of papers that appeared in
preliminary form in the proceedings of the 18th International Conference
on Algorithmic Learning Theory (ALT 2007), which was held in Sendai,
Japan during October 1--4, 2007. \emph{Algorithmic Learning Theory} is
a conference series which is dedicated to the theoretical study of the
algorithmic aspects of learning. The best papers of the conference ALT 2007
were invited for this special issue and after a thorough reviewing process,
most of them qualified for this Special Issue on Algorithmic Learning Theory
of Theoretical Computer Science. The preface contains a short introduction
to each of these papers.",
}
@Article{Hutter:09improbx,
author = "Alberto Piatti and Marco Zaffalon and Fabio Trojani and Marcus Hutter",
title = "Limits of Learning about a Categorical Latent Variable under Prior Near-Ignorance",
journal = "International Journal of Approximate Reasoning",
volume = "50",
number = "4",
pages = "597--611",
_month = apr,
year = "2009",
bibtex = "http://www.hutter1.net/official/bib.htm#improbx",
url = "http://arxiv.org/abs/0904.4527",
pdf = "http://www.hutter1.net/ai/improbx.pdf",
ps = "http://www.hutter1.net/ai/improbx.ps",
latex = "http://www.hutter1.net/ai/improbx.tex",
slides = "http://www.hutter1.net/ai/simprob.pdf",
project = "http://www.hutter1.net/official/projects.htm#robust",
doi = "10.1016/j.ijar.2008.08.003",
issn = "1012-2443",
keywords = "Near-ignorance set of priors; Latent variables; Imprecise Dirichlet model.",
abstract = "In this paper, we consider the coherent theory of (epistemic)
uncertainty of Walley, in which beliefs are represented through sets
of probability distributions, and we focus on the problem of
modeling prior ignorance about a categorical random variable. In
this setting, it is a known result that a state of prior ignorance
is not compatible with learning. To overcome this problem, another
state of beliefs, called \emph{near-ignorance}, has been proposed.
Near-ignorance resembles ignorance very closely, by satisfying some
principles that can arguably be regarded as necessary in a state of
ignorance, and allows learning to take place. What this paper does,
is to provide new and substantial evidence that also near-ignorance
cannot be really regarded as a way out of the problem of starting
statistical inference in conditions of very weak beliefs. The key to
this result is focusing on a setting characterized by a variable of
interest that is \emph{latent}. We argue that such a setting is by
far the most common case in practice, and we provide, for the case
of categorical latent variables (and general \emph{manifest}
variables) a condition that, if satisfied, prevents learning to take
place under prior near-ignorance. This condition is shown to be
easily satisfied even in the most common statistical problems. We
regard these results as a strong form of evidence against the
possibility to adopt a condition of prior near-ignorance in real
statistical problems.",
}
@TechReport{Hutter:09bayestreex,
author = "Marcus Hutter",
title = "Exact Non-Parametric {B}ayesian Inference on Infinite Trees",
number = "0903.5342",
institution = "ARXIV",
_month = mar,
year = "2009",
bibtex = "http://www.hutter1.net/official/bib.htm#bayestreex",
url = "http://arxiv.org/abs/0903.5342",
pdf = "http://www.hutter1.net/ai/bayestreex.pdf",
ps = "http://www.hutter1.net/ai/bayestreex.ps",
latex = "http://www.hutter1.net/ai/bayestreex.zip",
slides = "http://www.hutter1.net/ai/sbayestree.pdf",
project = "http://www.hutter1.net/official/projects.htm#bayes",
code = "http://www.hutter1.net/ai/bayestree.c",
keywords = "Bayesian density estimation, exact linear time algorithm,
non-parametric inference, adaptive infinite tree, Polya tree,
scale invariance, consistency, asymptotics.",
msc = "62G07; 60B10; 68W99",
abstract = "Given i.i.d. data from an unknown distribution, we consider the
problem of predicting future items. An adaptive way to estimate
the probability density is to recursively subdivide the domain to
an appropriate data-dependent granularity. A Bayesian would assign
a data-independent prior probability to ``subdivide'', which leads
to a prior over infinite(ly many) trees. We derive an exact, fast,
and simple inference algorithm for such a prior, for the data
evidence, the predictive distribution, the effective model
dimension, moments, and other quantities. We prove asymptotic
convergence and consistency results, and illustrate the behavior
of our model on some prototypical functions.",
}
@Book{Hutter:09agiproc,
editor = "Ben Goertzel and Pascal Hitzler and Marcus Hutter",
title = "Artificial General Intelligence",
subtitle = "2nd Conference ({AGI'09})",
publisher = "Atlantis Press",
address = "Arlington",
_month = mar,
year = "2009",
bibtex = "http://www.hutter1.net/official/bib.htm#agiproc",
http = "http://www.atlantis-press.com/publications/aisr/AGI-09/",
pdf = "http://www.hutter1.net/ai/agifb.pdf",
pdfall = "http://www.hutter1.net/ai/agiproc.pdf",
project = "http://www.hutter1.net/official/projects.htm#uai",
issn = "1951-6851",
isbn = "978-90-78677-24-6",
abstract = "The Conference on Artificial General Intelligence is the only major
conference series devoted wholly and specifically to the creation of
AI systems possessing general intelligence at the human level and
ultimately beyond. Its second installation, AGI-09, in Arlington,
Virginia, March 6-9, 2009, attracted 67 paper submissions, which is
a substantial increase from the previous year. Of these submissions,
33 (i.e., 49\%) were accepted as full papers for presentation at the
conference. Additional 13 papers were included as position papers.
The program also included a keynote address by J\"u{}rgen
Schmidhuber on \emph{The New AI}, a post-conference workshop on
\emph{The Future of AI}, and a number of pre-conference tutorials on
various topics related to AGI.",
}
@InProceedings{Hutter:09phimdp,
author = "Marcus Hutter",
title = "Feature {M}arkov Decision Processes",
booktitle = "Proc. 2nd Conf. on Artificial General Intelligence ({AGI'09})",
subtitle = "Advances in Intelligent Systems Research",
volume = "8",
pages = "61--66",
publisher = "Atlantis Press",
_address = "Arlington, Virginia",
_month = mar,
year = "2009",
bibtex = "http://www.hutter1.net/official/bib.htm#phimdp",
url = "http://arXiv.org/abs/0812.4580",
pdf = "http://www.hutter1.net/ai/phimdp.pdf",
ps = "http://www.hutter1.net/ai/phimdp.ps",
latex = "http://www.hutter1.net/ai/phimdp.tex",
slides = "http://www.hutter1.net/ai/sphimdp.pdf",
award = "http://agi-conf.org/2009/kurzweilprize.php",
project = "http://www.hutter1.net/official/projects.htm#uai",
doi = "10.2991/agi.2009.30",
issn = "1951-6851",
isbn = "978-90-78677-24-6",
keywords = "Reinforcement learning; Markov decision process;
partial observability; feature learning; explore-exploit.",
abstract = "General purpose intelligent learning agents cycle through
(complex,non-MDP) sequences of observations, actions, and rewards.
On the other hand, reinforcement learning is well-developed for
small finite state Markov Decision Processes (MDPs). So far it is an
art performed by human designers to extract the right state
representation out of the bare observations, i.e. to reduce the
agent setup to the MDP framework. Before we can think of mechanizing
this search for suitable MDPs, we need a formal objective criterion.
The main contribution of this article is to develop such a
criterion. I also integrate the various parts into one learning
algorithm. Extensions to more realistic dynamic Bayesian networks
are developed in a companion article.",
znote = "Acceptance rate: 33/67 = 49\%. First Runner-Up for the Kurzweil Best Paper Award",
}
@InProceedings{Hutter:09phidbn,
author = "Marcus Hutter",
title = "Feature Dynamic {B}ayesian Networks",
booktitle = "Proc. 2nd Conf. on Artificial General Intelligence ({AGI'09})",
subtitle = "Advances in Intelligent Systems Research",
volume = "8",
pages = "67--73",
publisher = "Atlantis Press",
_address = "Arlington, Virginia",
_month = mar,
year = "2009",
bibtex = "http://www.hutter1.net/official/bib.htm#phidbn",
url = "http://arXiv.org/abs/0812.4581",
pdf = "http://www.hutter1.net/ai/phidbn.pdf",
ps = "http://www.hutter1.net/ai/phidbn.ps",
latex = "http://www.hutter1.net/ai/phidbn.tex",
slides = "http://www.hutter1.net/ai/sphimdp.pdf",
project = "http://www.hutter1.net/official/projects.htm#uai",
doi = "10.2991/agi.2009.6",
issn = "1951-6851",
isbn = "978-90-78677-24-6",
keywords = "Reinforcement learning; dynamic Bayesian network;
structure learning; feature learning;
global vs. local reward; explore-exploit.",
abstract = "Feature Markov Decision Processes (PhiMDPs) are well-suited for
learning agents in general environments. Nevertheless, unstructured
(Phi)MDPs are limited to relatively simple environments. Structured
MDPs like Dynamic Bayesian Networks (DBNs) are used for large-scale
real-world problems. In this article I extend PhiMDP to PhiDBN. The
primary contribution is to derive a cost criterion that allows to
automatically extract the most relevant features from the
environment, leading to the ``best'' DBN representation. I discuss all
building blocks required for a complete general learning algorithm.",
znote = "Acceptance rate: 33/67 = 49\%",
}
@Article{Hutter:09idmx,
author = "Marcus Hutter",
title = "Practical Robust Estimators under the {I}mprecise {D}irichlet {M}odel",
journal = "International Journal of Approximate Reasoning",
volume = "50",
number = "2",
pages = "231--242",
_month = feb,
year = "2009",
bibtex = "http://www.hutter1.net/official/bib.htm#idmx",
url = "http://arxiv.org/abs/0901.4137",
pdf = "http://www.hutter1.net/ai/idmx.pdf",
ps = "http://www.hutter1.net/ai/idmx.ps",
latex = "http://www.hutter1.net/ai/idmx.tex",
slides = "http://www.hutter1.net/ai/sidm.pdf",
project = "http://www.hutter1.net/official/projects.htm#robust",
doi = "10.1016/j.ijar.2008.03.020",
issn = "0888-613X",
keywords = "Imprecise Dirichlet Model; exact, conservative, approximate,
robust, credible interval estimates; entropy; mutual
information.",
abstract = "Walley's Imprecise Dirichlet Model (IDM) for categorical i.i.d.\
data extends the classical Dirichlet model to a set of priors. It
overcomes several fundamental problems which other approaches to
uncertainty suffer from. Yet, to be useful in practice, one needs
efficient ways for computing the imprecise=robust sets or
intervals. The main objective of this work is to derive exact,
conservative, and approximate, robust and credible interval
estimates under the IDM for a large class of statistical
estimators, including the entropy and mutual information.",
}
@Article{Hutter:09bcnax,
author = "Paola M. V. Rancoita and Marcus Hutter and Francesco Bertoni and Ivo Kwee",
title = "Bayesian {DNA} Copy Number Analysis",
journal = "BMC Bioinformatics",
volume = "10",
number = "10",
pages = "1--19",
_month = jan,
year = "2009",
bibtex = "http://www.hutter1.net/official/bib.htm#bcna",
http = "http://www.biomedcentral.com/1471-2105/10/10",
supplement = "http://www.biomedcentral.com/content/supplementary/1471-2105-10-10-s2.pdf",
code = "http://www.biomedcentral.com/content/supplementary/1471-2105-10-10-s1.zip",
doi = "10.1186/1471-2105-10-10",
abstract = "Background: Some diseases, like tumors, can be related to
chromosomal aberrations, leading to changes of DNA copy number. The
copy number of an aberrant genome can be represented as a piecewise
constant function, since it can exhibit regions of deletions or
gains. Instead, in a healthy cell the copy number is two because we
inherit one copy of each chromosome from each our parents. Bayesian
Piecewise Constant Regression (BPCR) is a Bayesian regression method
for data that are noisy observations of a piecewise constant
function. The method estimates the unknown segment number, the
endpoints of the segments and the value of the segment levels of the
underlying piecewise constant function. The Bayesian Regression
Curve (BRC) estimates the same data with a smoothing curve. However,
in the original formulation, some estimators failed to properly
determine the corresponding parameters. For example, the boundary
estimator did not take into account the dependency among the
boundaries and succeeded in estimating more than one breakpoint at
the same position, losing segments.
Results: We derived an improved version of the BPCR (called mBPCR)
and BRC, changing the segment number estimator and the boundary
estimator to enhance the fitting procedure. We also proposed an
alternative estimator of the variance of the segment levels, which
is useful in case of data with high noise. Using artificial data, we
compared the original and the modified version of BPCR and BRC with
other regression methods, showing that our improved version of BPCR
generally outperformed all the others. Similar results were also
observed on real data.
Conclusions: We propose an improved method for DNA copy number
estimation, mBPCR, which performed very well compared to previously
published algorithms. In particular, mBPCR was more powerful in the
detection of the true position of the breakpoints and of small
aberrations in very noisy data. Hence, from a biological point of
view, our method can be very useful, for example, to find targets of
genomic aberrations in clinical cancer samples.",
support = "SNF grant 205321-112430",
znote = "Marked as highly accessed.",
alt = "Also 2-page abstract and poster at 9th ISBA and 18th MASAMB meetings (2008)",
abstract2p = "http://www.hutter1.net/ai/bcnas.pdf",
poster = "http://www.hutter1.net/ai/sbcnas.pdf",
}
%-------------Publications-of-Marcus-Hutter-2008--------------%
@InProceedings{Hutter:08qlearn,
author = "Marcus Hutter and Shane Legg",
title = "Temporal Difference Updating without a Learning Rate",
booktitle = "Advances in Neural Information Processing Systems 20",
pages = "705--712",
publisher = "MIT Press",
address = "Cambridge, MA",
_month = nov,
year = "2008",
bibtex = "http://www.hutter1.net/official/bib.htm#qlearn",
url = "http://arxiv.org/abs/0810.5631",
pdf = "http://www.hutter1.net/ai/qlearn.pdf",
ps = "http://www.hutter1.net/ai/qlearn.ps",
latex = "http://www.hutter1.net/ai/qlearn.zip",
poster = "http://www.hutter1.net/ai/sqlearn.pdf",
project = "http://www.hutter1.net/official/projects.htm#rl",
xdoi = "",
xissn = "",
keywords = "reinforcement learning; temporal difference;
eligibility trace; variational principle; learning rate.",
abstract = "We derive an equation for temporal difference learning from
statistical principles. Specifically, we start with the variational
principle and then bootstrap to produce an updating rule for
discounted state value estimates. The resulting equation is similar
to the standard equation for temporal difference learning with
eligibility traces, so called TD(lambda), however it lacks the
parameter alpha that specifies the learning rate. In the place
of this free parameter there is now an equation for the learning
rate that is specific to each state transition. We experimentally
test this new learning rule against TD(lambda) and find that it
offers superior performance in various settings. Finally, we make
some preliminary investigations into how to extend our new temporal
difference algorithm to reinforcement learning. To do this we
combine our update equation with both Watkins' Q(lambda) and
Sarsa(lambda) and find that it again offers superior performance
without a learning rate parameter.",
znote = "Acceptance rate: 217/975 = 22\%",
}
@Article{Hutter:08actoptx,
author = "Daniil Ryabko and Marcus Hutter",
title = "On the Possibility of Learning in Reactive Environments with Arbitrary Dependence",
journal = "Theoretical Computer Science",
volume = "405",
number = "3",
pages = "274--284",
_month = oct,
year = "2008",
bibtex = "http://www.hutter1.net/official/bib.htm#actoptx",
ftp = "http://www.idsia.ch/idsiareport/IDSIA-08-08.pdf",
url = "http://arxiv.org/abs/0810.5636",
pdf = "http://www.hutter1.net/ai/actoptx.pdf",
ps = "http://www.hutter1.net/ai/actoptx.ps",
latex = "http://www.hutter1.net/ai/actoptx.tex",
slides = "http://www.hutter1.net/ai/sactopt.pdf",
project = "http://www.hutter1.net/official/projects.htm#uai",
doi = "10.1016/j.tcs.2008.06.039",
issn = "0304-3975",
keywords = "Reinforcement learning, asymptotic average value,
self-optimizing policies, (non) Markov decision processes.",
abstract = "We address the problem of reinforcement learning in which
observations may exhibit an arbitrary form of stochastic dependence
on past observations and actions, i.e.\ environments more general
than (PO)MDPs. The task for an agent is to attain the best possible
asymptotic reward where the true generating environment is unknown
but belongs to a known countable family of environments. We find
some sufficient conditions on the class of environments under which
an agent exists which attains the best asymptotic reward for any
environment in the class. We analyze how tight these conditions are
and how they relate to different probabilistic assumptions known in
reinforcement learning and related fields, such as Markov Decision
Processes and mixing conditions.",
support = "SNF grant 200020-107616",
}
@InProceedings{Hutter:08select,
author = "Kassel Hingee and Marcus Hutter",
title = "Equivalence of Probabilistic Tournament and Polynomial Ranking Selection",
booktitle = "Proc. 2008 Congress on Evolutionary Computation ({CEC'08})",
pages = "564--571",
publisher = "IEEE",
address = "Hongkong",
isbn = "978-1-4244-1823-7",
_month = jun,
year = "2008",
bibtex = "http://www.hutter1.net/official/bib.htm#select",
url = "http://arxiv.org/abs/0803.2925",
pdf = "http://www.hutter1.net/ai/select.pdf",
ps = "http://www.hutter1.net/ai/select.ps",
latex = "http://www.hutter1.net/ai/select.zip",
slides = "http://www.hutter1.net/ai/sselect.pdf",
project = "http://www.hutter1.net/official/projects.htm#optimize",
doi = "10.1109/CEC.2008.4630852",
keywords = "evolutionary algorithms, ranking selection,
tournament selection, equivalence, efficiency.",
abstract = "Crucial to an Evolutionary Algorithm's performance is its selection
scheme. We mathematically investigate the relation between
polynomial rank and probabilistic tournament methods which are
(respectively) generalisations of the popular linear ranking and
tournament selection schemes. We show that every probabilistic
tournament is equivalent to a unique polynomial rank scheme. In
fact, we derived explicit operators for translating between these
two types of selection. Of particular importance is that most linear
and most practical quadratic rank schemes are probabilistic
tournaments.",
}
@Article{Hutter:08pquestx,
author = "Daniil Ryabko and Marcus Hutter",
title = "Predicting Non-Stationary Processes",
journal = "Applied Mathematics Letters",
volume = "21",
number = "5",
pages = "477--482",
_month = may,
year = "2008",
bibtex = "http://www.hutter1.net/official/bib.htm#pquestx",
url = "http://arxiv.org/abs/cs.LG/0606077",
ftp = "http://www.idsia.ch/idsiareport/IDSIA-13-06.pdf",
pdf = "http://www.hutter1.net/ai/pquestx.pdf",
ps = "http://www.hutter1.net/ai/pquestx.ps",
latex = "http://www.hutter1.net/ai/pquestx.tex",
slides = "http://www.hutter1.net/ai/spquest.pdf",
project = "http://www.hutter1.net/official/projects.htm#bayes",
doi = "10.1016/j.aml.2007.04.004",
issn = "0893-9659",
keywords = "sequence prediction, local absolute continuity,
non-stationary measures, average/expected criteria,
absolute/KL divergence, mixtures of measures.",
abstract = "Suppose we are given two probability measures on the set of
one-way infinite finite-alphabet sequences and consider the
question when one of the measures predicts the other, that is,
when conditional probabilities converge (in a certain sense) when
one of the measures is chosen to generate the sequence. This
question may be considered a refinement of the problem of sequence
prediction in its most general formulation: for a given class of
probability measures, does there exist a measure which predicts
all of the measures in the class? To address this problem, we find
some conditions on local absolute continuity which are sufficient
for prediction and which generalize several different notions
which are known to be sufficient for prediction. We also formulate
some open questions to outline a direction for finding the
conditions on classes of measures for which prediction is
possible.",
support = "SNF grant 200020-107616",
}
@Article{Hutter:08kolmo,
author = "Marcus Hutter",
title = "Algorithmic Complexity",
journal = "Scholarpedia",
volume = "3",
number = "1",
pages = "2573",
_month = jan,
year = "2008",
bibtex = "http://www.hutter1.net/official/bib.htm#kolmo",
http = "http://www.scholarpedia.org/article/Algorithmic_Complexity",
pdf = "http://www.hutter1.net/ai/kolmo.pdf",
ps = "http://www.hutter1.net/ai/kolmo.ps",
latex = "http://www.hutter1.net/ai/kolmo.zip",
project = "http://www.hutter1.net/official/projects.htm#ait",
issn = "1941-6016",
keywords = "algorithmic information theory,
prefix code, prefix Turing machine,
Universal Turing machine, Kolmogorov complexity,
plain complexity, prefix complexity.",
abstract = "The information content or complexity of an object can be measured
by the length of its shortest description. For instance the string
`01010101010101010101010101010101' has the short description ``16
repetitions of 01'', while `11001000011000011101111011101100'
presumably has no simpler description other than writing down the
string itself. More formally, the Algorithmic ``Kolmogorov''
Complexity (AC) of a string $x$ is defined as the length of the
shortest program that computes or outputs $x$, where the program is
run on some fixed reference universal computer.",
}
%-------------Publications-of-Marcus-Hutter-2007--------------%
@InProceedings{Hutter:07intest,
author = "Shane Legg and Marcus Hutter",
title = "Tests of Machine Intelligence",
booktitle = "50 Years of Artificial Intelligence",
booksubtitle = "Essays Dedicated to the 50th Anniversary of Artificial Intelligence",
address = "Monte Verita, Switzerland",
series = "LNAI",
volume = "4850",
_editor = "M. Lungarella, F. Iida, J. Bongard, R. Pfeifer",
pages = "232--242",
_month = dec,
year = "2007",
bibtex = "http://www.hutter1.net/official/bib.htm#intest",
url = "http://arxiv.org/abs/0712.3825",
pdf = "http://www.hutter1.net/ai/intest.pdf",
ps = "http://www.hutter1.net/ai/intest.ps",
latex = "http://www.hutter1.net/ai/intest.tex",
poster = "http://www.hutter1.net/ai/siors.pdf",
project = "http://www.hutter1.net/official/projects.htm#uai",
press = "http://www.hutter1.net/official/press.htm#mim",
doi = "10.1007/978-3-540-77296-5_22",
issn = "0302-9743",
isbn = "978-3-540-77295-8",
keywords = "Turing test and derivatives; Compression tests; Linguistic complexity;
Multiple cognitive abilities; Competitive games;
Psychometric tests; Smith's test; C-test; Universal intelligence",
abstract = "Although the definition and measurement of intelligence is clearly
of fundamental importance to the field of artificial intelligence,
no general survey of definitions and tests of machine intelligence
exists. Indeed few researchers are even aware of alternatives to
the Turing test and its many derivatives. In this paper we fill
this gap by providing a short survey of the many tests of machine
intelligence that have been proposed.",
support = "SNF grant 200020-107616",
}
@Article{Hutter:07iorx,
author = "Shane Legg and Marcus Hutter",
title = "Universal Intelligence: A Definition of Machine Intelligence",
volume = "17",
number = "4",
journal = "Minds \& Machines",
pages = "391--444",
_month = dec,
year = "2007",
bibtex = "http://www.hutter1.net/official/bib.htm#iorx",
url = "http://arxiv.org/abs/0712.3329",
pdf = "http://www.hutter1.net/ai/iorx.pdf",
ps = "http://www.hutter1.net/ai/iorx.ps",
latex = "http://www.hutter1.net/ai/iorx.zip",
poster = "http://www.hutter1.net/ai/sior.pdf",
project = "http://www.hutter1.net/official/projects.htm#uai",
press = "http://www.hutter1.net/official/press.htm#mim",
doi = "10.1007/s11023-007-9079-x",
issn = "0924-6495",
keywords = "AIXI, complexity theory, intelligence,
theoretical foundations, Turing test,
intelligence tests/measures/definitions",
abstract = "A fundamental problem in artificial intelligence is that nobody really
knows what intelligence is. The problem is especially acute when we
need to consider artificial systems which are significantly different
to humans. In this paper we approach this problem in the following
way: We take a number of well known informal definitions of human
intelligence that have been given by experts, and extract their
essential features. These are then mathematically formalised to
produce a general measure of intelligence for arbitrary machines. We
believe that this equation formally captures the concept of machine
intelligence in the broadest reasonable sense. We then show how this
formal definition is related to the theory of universal optimal
learning agents. Finally, we survey the many other tests and
definitions of intelligence that have been proposed for machines.",
support = "SNF grant 200020-107616",
}
@Article{Hutter:07pcregx,
author = "Marcus Hutter",
title = "Exact {B}ayesian Regression of Piecewise Constant Functions",
journal = "Bayesian Analysis",
volume = "2",
number = "4",
pages = "635--664",
_month = dec,
year = "2007",
bibtex = "http://www.hutter1.net/official/bib.htm#pcregx",
url = "http://arxiv.org/abs/math.ST/0606315",
pdf = "http://www.hutter1.net/ai/pcregx.pdf",
ps = "http://www.hutter1.net/ai/pcregx.ps",
latex = "http://www.hutter1.net/ai/pcregx.tex",
slides = "http://www.hutter1.net/ai/spcreg.pdf",
award = "http://www.bayesian.org/awards/LindleyPrize.html",
project = "http://www.hutter1.net/official/projects.htm#bayes",
code = "http://www.hutter1.net/ai/cpcreg.zip",
doi = "10.1214/07-BA225",
issn = "1936-0975",
keywords = "Bayesian regression, exact polynomial algorithm,
non-parametric inference, piecewise constant function,
dynamic programming, change point problem.",
abstract = "We derive an exact and efficient Bayesian regression algorithm for
piecewise constant functions of unknown segment number, boundary
locations, and levels. The derivation works for any noise and segment
level prior, e.g.\ Cauchy which can handle outliers. We derive
simple but good estimates for the in-segment variance. We also
propose a Bayesian regression curve as a better way of smoothing
data without blurring boundaries. The Bayesian approach also allows
straightforward determination of the evidence, break probabilities
and error estimates, useful for model selection and significance and
robustness studies. We discuss the performance on synthetic and
real-world examples. Many possible extensions are discussed.",
}
@Proceedings{Hutter:07altproc,
editor = "Marcus Hutter and Rocco A. Servedio and Eiji Takimoto",
title = "Algorithmic Learning Theory",
subtitle = "18th International Conference ({ALT'07})",
publisher = "Springer, Berlin",
address = "Sendai",
series = "LNAI",
volume = "4754",
_month = oct,
year = "2007",
bibtex = "http://www.hutter1.net/official/bib.htm#altproc",
http = "http://www.springer.com/west/home?SGWID=4-102-22-173760307-0",
pdf = "http://www.hutter1.net/ai/altproc.pdf",
project = "http://www.hutter1.net/official/projects.htm#other",
doi = "10.1007/978-3-540-75225-7",
issn = "0302-9743",
isbn = "978-3-540-75224-0",
keywords = "algorithmic learning theory, query models, online
learning, inductive inference, boosting, kernel methods, complexity
and learning, reinforcement learning, unsupervised learning,
grammatical inference, algorithmic forecasting.",
abstract = "The LNAI series reports state-of-the-art results in artificial
intelligence research, development, and education. This volume (LNAI
4754) contains research papers presented at the 18th International
Conference on Algorithmic Learning Theory (ALT 2007), which was held
in Sendai (Japan) during October 1-4, 2007. The main objective of
the conference was to provide an interdisciplinary forum for
high-quality talks with a strong theoretical background and
scientific interchange in areas such as query models, online
learning, inductive inference, boosting, kernel methods, complexity
and learning, reinforcement learning, unsupervised learning,
grammatical inference, and algorithmic forecasting. The conference
was co-located with the 10th International Conference on Discovery
Science (DS 2007). The volume includes 25 technical contributions
that were selected from 50 submissions, and five invited talks
presented to the audience of ALT and DS. Longer versions of the
DS invited papers are available in the proceedings of DS 2007.",
znote = "Acceptance rate: 25/50 = 50\%",
}
@InProceedings{Hutter:07altintro,
author = "Marcus Hutter and Rocco A. Servedio and Eiji Takimoto",
title = "Algorithmic Learning Theory 2007: Editors' Introduction",
booktitle = "Proc. 18th International Conf. on Algorithmic Learning Theory ({ALT'07})",
address = "Sendai",
series = "LNAI",
volume = "4754",
_editor = "Marcus Hutter and Rocco A. Servedio and Eiji Takimoto",
publisher = "Springer, Berlin",
pages = "1--8",
_month = oct,
year = "2007",
bibtex = "http://www.hutter1.net/official/bib.htm#altintro",
pdf = "http://www.hutter1.net/ai/altintro.pdf",
ps = "http://www.hutter1.net/ai/altintro.ps",
latex = "http://www.hutter1.net/ai/altintro.tex",
slides = "http://www.hutter1.net/ai/saltintro.pdf",
project = "http://www.hutter1.net/official/projects.htm#other",
issn = "0302-9743",
isbn = "3-540-75224-2",
doi = "10.1007/978-3-540-75225-7_1",
keywords = "algorithmic learning theory, query models, online
learning, inductive inference, boosting, kernel methods, complexity
and learning, reinforcement learning, unsupervised learning,
grammatical inference, algorithmic forecasting.",
abstract = "Learning theory is an active research area that incorporates ideas,
problems, and techniques from a wide range of disciplines including
statistics, artificial intelligence, information theory, pattern
recognition, and theoretical computer science. The research reported
at the 18th International Conference on Algorithmic Learning Theory
(ALT 2007) ranges over areas such as unsupervised learning,
inductive inference, complexity and learning, boosting and
reinforcement learning, query learning models, grammatical
inference, online learning and defensive forecasting, and kernel
methods. In this introduction we give an overview of the five
invited talks and the regular contributions of ALT 2007.",
}
@Article{Hutter:07uspx,
author = "Marcus Hutter",
title = "On Universal Prediction and {B}ayesian Confirmation",
journal = "Theoretical Computer Science",
volume = "384",
number = "1",
pages = "33--48",
_month = sep,
year = "2007",
bibtex = "http://www.hutter1.net/official/bib.htm#uspx",
url = "http://arxiv.org/abs/0709.1516",
pdf = "http://www.hutter1.net/ai/uspx.pdf",
ps = "http://www.hutter1.net/ai/uspx.ps",
latex = "http://www.hutter1.net/ai/uspx.tex",
slides = "http://www.hutter1.net/ai/susp.pdf",
project = "http://www.hutter1.net/official/projects.htm#uai",
doi = "10.1016/j.tcs.2007.05.016",
issn = "0304-3975",
keywords = "Sequence prediction, Bayes, Solomonoff prior,
Kolmogorov complexity, Occam's razor, prediction bounds,
model classes, philosophical issues, symmetry principle,
confirmation theory, reparametrization invariance,
old-evidence/updating problem, (non)computable environments.",
abstract = "The Bayesian framework is a well-studied and successful framework
for inductive reasoning, which includes hypothesis testing and
confirmation, parameter estimation, sequence prediction,
classification, and regression. But standard statistical guidelines
for choosing the model class and prior are not always available or
fail, in particular in complex situations.
Solomonoff completed the Bayesian framework by providing a
rigorous, unique, formal, and universal choice for the model class
and the prior. We discuss in breadth how and in which sense
universal (non-i.i.d.) sequence prediction solves various
(philosophical) problems of traditional Bayesian sequence
prediction. We show that Solomonoff's model possesses many
desirable properties: Strong total and weak instantaneous bounds,
and in contrast to most classical continuous prior densities has
no zero p(oste)rior problem, i.e. can confirm universal
hypotheses, is reparametrization and regrouping invariant, and
avoids the old-evidence and updating problem. It even performs
well (actually better) in non-computable environments.",
}
@Article{Hutter:07mlconvxx,
author = "Marcus Hutter and Andrej A. Muchnik",
title = "On Semimeasures Predicting {Martin-L{\"o}f} Random Sequences",
journal = "Theoretical Computer Science",
volume = "382",
number = "3",
pages = "247--261",
_month = sep,
year = "2007",
bibtex = "http://www.hutter1.net/official/bib.htm#mlconvxx",
xhttp = "http://www.hutter1.net/ai/mlconvxx.htm",
url = "http://arxiv.org/abs/0708.2319",
pdf = "http://www.hutter1.net/ai/mlconvxx.pdf",
ps = "http://www.hutter1.net/ai/mlconvxx.ps",
latex = "http://www.hutter1.net/ai/mlconvxx.tex",
slides = "http://www.hutter1.net/ai/smlconvx.pdf",
project = "http://www.hutter1.net/official/projects.htm#ait",
doi = "10.1016/j.tcs.2007.03.040",
issn = "0304-3975",
keywords = "Sequence prediction; Algorithmic Information Theory;
universal enumerable semimeasure; mixture distributions;
posterior convergence; Martin-L{\"o}f randomness;
quasimeasures.",
abstract = "Solomonoff's central result on induction is that the posterior of
a universal semimeasure M converges rapidly and with probability
1 to the true sequence generating posterior mu, if the latter is
computable. Hence, M is eligible as a universal sequence predictor
in case of unknown mu. Despite some nearby results and proofs in
the literature, the stronger result of convergence for all
(Martin-Loef) random sequences remained open. Such a convergence
result would be particularly interesting and natural, since
randomness can be defined in terms of M itself. We show that there
are universal semimeasures M which do not converge for all random
sequences, i.e. we give a partial negative answer to the open
problem. We also provide a positive answer for some non-universal
semimeasures. We define the incomputable measure D as a mixture
over all computable measures and the enumerable semimeasure W as a
mixture over all enumerable nearly-measures. We show that W
converges to D and D to mu on all random sequences. The Hellinger
distance measuring closeness of two distributions plays
a central role.",
support = "SNF grant 2100-67712 and RFBF grants N04-01-00427 and N02-01-22001",
}
@Article{Hutter:07algprob,
author = "Marcus Hutter and Shane Legg and Paul M. B. Vit{\'a}nyi",
title = "Algorithmic Probability",
journal = "Scholarpedia",
volume = "2",
number = "8",
pages = "2572",
_month = aug,
year = "2007",
bibtex = "http://www.hutter1.net/official/bib.htm#algprob",
http = "http://www.scholarpedia.org/article/Algorithmic_Probability",
pdf = "http://www.hutter1.net/ai/algprob.pdf",
ps = "http://www.hutter1.net/ai/algprob.ps",
project = "http://www.hutter1.net/official/projects.htm#ait",
issn = "1941-6016",
keywords = "algorithmic information theory,
algorithmic complexity,
discrete/continuous algorithmic probability,
Bayes, Occam, Epicurus,
applications, references",
abstract = "Algorithmic ``Solomonoff'' Probability (AP) assigns to objects an a
priori probability that is in some sense universal. This prior
distribution has theoretical applications in a number of areas,
including inductive inference theory and the time complexity
analysis of algorithms. Its main drawback is that it is not
computable and thus can only be approximated in practice",
}
@InProceedings{Hutter:07improb,
author = "Alberto Piatti and Marco Zaffalon and Fabio Trojani and Marcus Hutter",
title = "Learning about a Categorical Latent Variable under Prior Near-Ignorance",
booktitle = "Proc. 5th International Symposium on
Imprecise Probability: Theories and Applications ({ISIPTA'07})",
pages = "357--364",
_editor = "G. de Cooman and J. Vejnarova and M. Zaffalon",
publisher = "Action M Agency",
address = "Prague",
_month = jul,
year = "2007",
bibtex = "http://www.hutter1.net/official/bib.htm#improb",
url = "http://arxiv.org/abs/0705.4312",
pdf = "http://www.hutter1.net/ai/improb.pdf",
ps = "http://www.hutter1.net/ai/improb.ps",
latex = "http://www.hutter1.net/ai/improb.tex",
slides = "http://www.hutter1.net/ai/simprob.pdf",
project = "http://www.hutter1.net/official/projects.htm#robust",
code = "http://www.hutter1.net/ai/improb.cpp",
isbn = "978-80-86742-20-5",
keywords = "Prior near-ignorance, latent and manifest variables,
observational processes, vacuous beliefs, imprecise probabilities.",
abstract = "It is well known that complete prior ignorance is not compatible
with learning, at least in a coherent theory of (epistemic)
uncertainty. What is less widely known, is that there is a state
similar to full ignorance, that Walley calls \emph{near-ignorance},
that permits learning to take place. In this paper we provide new
and substantial evidence that also near-ignorance cannot be really
regarded as a way out of the problem of starting statistical
inference in conditions of very weak beliefs. The key to this result
is focusing on a setting characterized by a variable of interest
that is \emph{latent}. We argue that such a setting is by far the
most common case in practice, and we show, for the case of
categorical latent variables (and general \emph{manifest} variables)
that there is a sufficient condition that, if satisfied, prevents
learning to take place under prior near-ignorance. This condition is
shown to be easily satisfied in the most common statistical
problems.",
znote = "Acceptance rate: 48/70 = 68\%",
}
@InProceedings{Hutter:07pcreg,
author = "Marcus Hutter",
title = "{B}ayesian Regression of Piecewise Constant Functions",
booktitle = "Proc. ISBA 8th International Meeting on Bayesian Statistics",
address = "Benidorm",
_editor = "J.M. Bernardo and M.J. Bayarri and J.O. Berger and
A.P. David and D. Heckerman and A.F.M. Smith and M. West",
publisher = "Oxford University Press",
pages = "607--612",
_month = jul,
year = "2007",
bibtex = "http://www.hutter1.net/official/bib.htm#pcreg",
url = "http://arxiv.org/abs/math.ST/0606315",
pdf = "http://www.hutter1.net/ai/pcreg.pdf",
ps = "http://www.hutter1.net/ai/pcreg.ps",
latex = "http://www.hutter1.net/ai/pcreg.tex",
slides = "http://www.hutter1.net/ai/spcreg.pdf",
award = "http://www.bayesian.org/awards/LindleyPrize.html",
project = "http://www.hutter1.net/official/projects.htm#bayes",
ccode = "http://www.hutter1.net/ai/pcreg.cpp",
rcode = "http://www.hutter1.net/ai/cpcreg.zip",
xdoi = "http://www.oup.com/uk/catalogue/?ci=9780199214655",
isbn = "978-0-19-921465-5",
abstract = "We derive an exact and efficient Bayesian regression algorithm for
piecewise constant functions of unknown segment number, boundary
location, and levels. It works for any noise and segment level
prior, e.g.\ Cauchy which can handle outliers. We derive simple but
good estimates for the in-segment variance. We also propose a
Bayesian regression curve as a better way of smoothing data without
blurring boundaries. The Bayesian approach also allows
straightforward determination of the evidence, break probabilities
and error estimates, useful for model selection and significance and
robustness studies. We briefly mention the performance on synthetic
and real-world examples. The full version of the paper contains
detailed derivations, more motivation and discussion, the complete
algorithm, the experiments, and various extensions.",
keywords = "Bayesian regression, exact polynomial algorithm, non-parametric
inference, piecewise constant function, dynamic programming,
change point problem.",
znote = "Acceptance rate: 19/326 = 6\%. Lindley best paper award.",
}
@InProceedings{Hutter:07pquest,
author = "Daniil Ryabko and Marcus Hutter",
title = "On Sequence Prediction for Arbitrary Measures",
booktitle = "Proc. IEEE International Symposium on Information Theory ({ISIT'07})",
pages = "2346--2350",
_editor = "A. Goldsmith and M. Medard and A. Shokrollahi and R. Zamir",
publisher = "IEEE",
address = "Nice, France",
_month = jun,
year = "2007",
bibtex = "http://www.hutter1.net/official/bib.htm#pquest",
url = "http://arxiv.org/abs/cs.LG/0606077",
ftp = "http://www.idsia.ch/idsiareport/IDSIA-13-06.pdf",
pdf = "http://www.hutter1.net/ai/pquest.pdf",
ps = "http://www.hutter1.net/ai/pquest.ps",
latex = "http://www.hutter1.net/ai/pquest.tex",
slides = "http://www.hutter1.net/ai/spquest.pdf",
project = "http://www.hutter1.net/official/projects.htm#bayes",
doi = "??",
isbn = "1-4244-1429-6",
keywords = "sequence prediction, local absolute continuity,
non-stationary measures, average/expected criteria,
absolute/KL divergence, mixtures of measures.",
abstract = "Suppose we are given two probability measures on the set of
one-way infinite finite-alphabet sequences. Consider the
question when one of the measures predicts the other, that is,
when conditional probabilities converge (in a certain sense), if
one of the measures is chosen to generate the sequence. This
question may be considered a refinement of the problem of sequence
prediction in its most general formulation: for a given class of
probability measures, does there exist a measure which predicts
all of the measures in the class? To address this problem, we find
some conditions on local absolute continuity which are sufficient
for prediction and generalize several different notions
that are known to be sufficient for prediction. We also formulate
some open questions to outline a direction for finding the
conditions on classes of measures for which prediction is
possible.",
support = "SNF grant 200020-107616",
}
@InProceedings{Hutter:07idefs,
author = "Shane Legg and Marcus Hutter",
title = "A Collection of Definitions of Intelligence",
booktitle = "Advances in Artificial General Intelligence: Concepts, Architectures and Algorithms",
series = "Frontiers in Artificial Intelligence and Applications",
volume = "157",
pages = "17--24",
editor = "B. Goertzel and P. Wang",
publisher = "IOS Press",
address = "Amsterdam, NL",
_month = jun,
year = "2007",
bibtex = "http://www.hutter1.net/official/bib.htm#idefs",
url = "http://arxiv.org/abs/0706.3639",
http = "http://www.idsia.ch/~shane/intelligence.html",
pdf = "http://www.hutter1.net/ai/idefs.pdf",
ps = "http://www.hutter1.net/ai/idefs.ps",
latex = "http://www.hutter1.net/ai/idefs.tex",
project = "http://www.hutter1.net/official/projects.htm#uai",
isbn = "978-1-58603-758-1",
issn = "0922-6389",
keywords = "intelligence definitions, collective, psychologist,
artificial, universal",
abstract = "This chapter is a survey of a large number of informal definitions
of ``intelligence'' that the authors have collected over the years.
Naturally, compiling a complete list would be impossible as many
definitions of intelligence are buried deep inside articles and
books. Nevertheless, the 70-odd definitions presented here are, to
the authors' knowledge, the largest and most well referenced
collection there is.",
support = "SNF grant 200020-107616",
}
@InProceedings{Hutter:07lorp,
author = "Marcus Hutter",
title = "The Loss Rank Principle for Model Selection",
booktitle = "Proc. 20th Annual Conf. on Learning Theory ({COLT'07})",
address = "San Diego",
series = "LNAI",
volume = "4539",
_editor = "N. Bshouty and C. Gentile",
publisher = "Springer, Berlin",
pages = "589--603",
_month = jun,
year = "2007",
bibtex = "http://www.hutter1.net/official/bib.htm#lorp",
url = "http://arxiv.org/abs/math.ST/0702804",
pdf = "http://www.hutter1.net/ai/lorp.pdf",
ps = "http://www.hutter1.net/ai/lorp.ps",
latex = "http://www.hutter1.net/ai/lorp.tex",
slides = "http://www.hutter1.net/ai/slorp.pdf",
project = "http://www.hutter1.net/official/projects.htm#mdl",
doi = "10.1007/978-3-540-72927-3_42",
issn = "0302-9743",
keywords = "Model selection, loss rank principle,
non-parametric regression, classification
general loss function, k nearest neighbors.",
abstract = "We introduce a new principle for model selection in regression and
classification. Many regression models are controlled by some
smoothness or flexibility or complexity parameter c, e.g. the number
of neighbors to be averaged over in k nearest neighbor (kNN)
regression or the polynomial degree in regression with polynomials.
Let f_D^c be the (best) regressor of complexity c on data D. A more
flexible regressor can fit more data D' well than a more rigid one.
If something (here small loss) is easy to achieve it's typically
worth less. We define the loss rank of f_D^c as the number of other
(fictitious) data D' that are fitted better by f_D'^c than D is
fitted by f_D^c. We suggest selecting the model complexity c that
has minimal loss rank (LoRP). Unlike most penalized maximum
likelihood variants (AIC,BIC,MDL), LoRP only depends on the
regression function and loss function. It works without a stochastic noise
model, and is directly applicable to any non-parametric regressor,
like kNN. In this paper we formalize, discuss, and motivate LoRP,
study it for specific regression problems, in particular linear
ones, and compare it to other model selection schemes.",
znote = "Acceptance rate: 41/92 = 45\%",
}
@Article{Hutter:07ait,
author = "Marcus Hutter",
title = "Algorithmic Information Theory: a brief non-technical guide to the field",
journal = "Scholarpedia",
volume = "2",
number = "3",
pages = "2519",
_month = mar,
year = "2007",
bibtex = "http://www.hutter1.net/official/bib.htm#ait",
http = "http://www.scholarpedia.org/article/Algorithmic_Information_Theory",
url = "http://arxiv.org/abs/cs.IT/0703024",
pdf = "http://www.hutter1.net/ai/ait.pdf",
ps = "http://www.hutter1.net/ai/ait.ps",
latex = "http://www.hutter1.net/ai/ait.zip",
project = "http://www.hutter1.net/official/projects.htm#ait",
issn = "1941-6016",
keywords = "Algorithmic information theory,
algorithmic ``Kolmogorov'' complexity,
algorithmic ``Solomonoff'' probability,
universal ``Levin'' search,
algorithmic ``Martin-Loef'' randomness,
applications, history, references, notation, nomenclature, map.",
abstract = "This article is a brief guide to the field of algorithmic
information theory (AIT), its underlying philosophy, and the most
important concepts. AIT arises by mixing information theory and
computation theory to obtain an objective and absolute notion of
information in an individual object, and in so doing gives rise to
an objective and robust notion of randomness of individual objects.
This is in contrast to classical information theory that is based on
random variables and communication, and has no bearing on
information and randomness of individual objects. After a brief
overview, the major subfields, applications, history, and a map of
the field are presented.",
}
@Article{Hutter:07postbndx,
author = "Alexey Chernov and Marcus Hutter and J{\"u}rgen Schmidhuber",
title = "Algorithmic Complexity Bounds on Future Prediction Errors",
journal = "Information and Computation",
volume = "205",
number = "2",
pages = "242--261",
_month = feb,
year = "2007",
bibtex = "http://www.hutter1.net/official/bib.htm#postbndx",
url = "http://arxiv.org/abs/cs.LG/0701120",
conf = "http://www-alg.ist.hokudai.ac.jp/~thomas/ALT05/alt05.jhtml",
pdf = "http://www.hutter1.net/ai/postbndx.pdf",
ps = "http://www.hutter1.net/ai/postbndx.ps",
latex = "http://www.hutter1.net/ai/postbndx.tex",
slides = "http://www.hutter1.net/ai/spostbnd.pdf",
project = "http://www.hutter1.net/official/projects.htm#ait",
doi = "10.1016/j.ic.2006.10.004",
issn = "0890-5401",
keywords = "Kolmogorov complexity, posterior bounds, online sequential prediction,
Solomonoff prior, monotone conditional complexity, total error,
future loss, randomness deficiency",
abstract = "We bound the future loss when predicting any (computably) stochastic
sequence online. Solomonoff finitely bounded the total deviation
of his universal predictor $M$ from the true distribution $mu$ by
the algorithmic complexity of $mu$. Here we assume we are at a
time $t>1$ and already observed $x=x_1...x_t$. We bound the future
prediction performance on $x_{t+1}x_{t+2}...$ by a new variant of
algorithmic complexity of $mu$ given $x$, plus the complexity of
the randomness deficiency of $x$. The new complexity is monotone
in its condition in the sense that this complexity can only
decrease if the condition is prolonged. We also briefly discuss
potential generalizations to Bayesian model classes and to
classification problems.",
support = "SNF grant 2000-61847",
}
@InCollection{Hutter:07aixigentle,
author = "Marcus Hutter",
title = "Universal Algorithmic Intelligence: A Mathematical Top$\rightarrow$Down Approach",
booktitle = "Artificial General Intelligence",
_editor = "B. Goertzel and C. Pennachin",
publisher = "Springer",
address = "Berlin",
_series = "Cognitive Technologies",
pages = "227--290",
_month = jan,
year = "2007",
bibtex = "http://www.hutter1.net/official/bib.htm#aixigentle",
http = "http://www.hutter1.net/ai/aixigentle.htm",
url = "http://arxiv.org/abs/cs.AI/0701125",
ftp = "http://www.idsia.ch/idsiareport/IDSIA-01-03.ps.gz",
pdf = "http://www.hutter1.net/ai/aixigentle.pdf",
ps = "http://www.hutter1.net/ai/aixigentle.ps",
latex = "http://www.hutter1.net/ai/aixigentle.tex",
slides = "http://www.hutter1.net/ai/skcunai.pdf",
project = "http://www.hutter1.net/official/projects.htm#uai",
press = "http://www.hutter1.net/official/press.htm#uaibook",
isbn = "3-540-23733-X",
categories = "I.2. [Artificial Intelligence]",
keywords = "Artificial intelligence; algorithmic probability;
sequential decision theory; rational agents;
value function; Solomonoff induction;
Kolmogorov complexity; reinforcement learning;
universal sequence prediction; strategic games;
function minimization; supervised learning.",
abstract = "Decision theory formally solves the problem of rational agents in
uncertain worlds if the true environmental prior probability
distribution is known. Solomonoff's theory of universal induction
formally solves the problem of sequence prediction for unknown
prior distribution. We combine both ideas and get a parameter-free
theory of universal Artificial Intelligence. We give strong
arguments that the resulting AIXI model is the most intelligent
unbiased agent possible. We outline for a number of problem
classes, including sequence prediction, strategic games, function
minimization, reinforcement and supervised learning, how the AIXI
model can formally solve them. The major drawback of the AIXI
model is that it is uncomputable. To overcome this problem, we
construct a modified algorithm AIXI$tl$ that is still
effectively more intelligent than any other time $t$ and length $l$
bounded agent. The computation time of AIXI$tl$ is of the order $t
\cdot 2^l$. Other discussed topics are formal definitions of
intelligence order relations, the horizon problem and relations of
the AIXI theory to other AI approaches.",
}
%-------------Publications-of-Marcus-Hutter-2006--------------%
@Article{Hutter:06unipriorx,
author = "Marcus Hutter",
title = "On Generalized Computable Universal Priors and their Convergence",
journal = "Theoretical Computer Science",
volume = "364",
number = "1",
pages = "27--41",
_month = nov,
year = "2006",
bibtex = "http://www.hutter1.net/official/bib.htm#unipriorx",
url = "http://arxiv.org/abs/cs.LG/0503026",
ftp = "http://www.idsia.ch/idsiareport/IDSIA-05-05.pdf",
pdf = "http://www.hutter1.net/ai/unipriorx.pdf",
ps = "http://www.hutter1.net/ai/unipriorx.ps",
latex = "http://www.hutter1.net/ai/unipriorx.tex",
slides = "http://www.hutter1.net/ai/sunipriors.pdf",
project = "http://www.hutter1.net/official/projects.htm#ait",
doi = "10.1016/j.tcs.2006.07.039",
issn = "0304-3975",
keywords = "Sequence prediction; Algorithmic Information Theory;
Solomonoff's prior; universal probability;
mixture distributions; posterior convergence;
computability concepts; Martin-Loef randomness.",
abstract = "Solomonoff unified Occam's razor and Epicurus' principle of
multiple explanations to one elegant, formal, universal theory of
inductive inference, which initiated the field of algorithmic
information theory. His central result is that the posterior of
the universal semimeasure M converges rapidly to the true sequence
generating posterior mu, if the latter is computable. Hence, M is
eligible as a universal predictor in case of unknown mu. The first
part of the paper investigates the existence and convergence of
computable universal (semi)measures for a hierarchy of
computability classes: recursive, estimable, enumerable, and
approximable. For instance, M is known to be enumerable, but
not estimable, and to dominate all enumerable semimeasures. We
present proofs for discrete and continuous semimeasures. The
second part investigates more closely the types of convergence,
possibly implied by universality: in difference and in ratio, with
probability 1, in mean sum, and for Martin-Loef random sequences.
We introduce a generalized concept of randomness for individual
sequences and use it to exhibit difficulties regarding these
issues. In particular, we show that convergence fails (holds) on
generalized-random sequences in gappy (dense) Bernoulli classes.",
}
@Article{Hutter:06fuo,
author = "Marcus Hutter and Shane Legg",
title = "Fitness Uniform Optimization",
journal = "IEEE Transactions on Evolutionary Computation",
volume = "10",
number = "5",
pages = "568--589",
_month = oct,
year = "2006",
bibtex = "http://www.hutter1.net/official/bib.htm#fuo",
url = "http://arxiv.org/abs/cs.NE/0610126",
ftp = "http://www.idsia.ch/idsiareport/IDSIA-16-06.pdf",
pdf = "http://www.hutter1.net/ai/fuo.pdf",
ps = "http://www.hutter1.net/ai/fuo.ps",
latex = "http://www.hutter1.net/ai/fuo.zip",
slides = "http://www.hutter1.net/ai/sfuss.pdf",
project = "http://www.hutter1.net/official/projects.htm#optimize",
press = "http://www.hutter1.net/official/press.htm#fuss",
doi = "10.1109/TEVC.2005.863127",
issn = "1089-778X",
keywords = "Evolutionary algorithms, fitness uniform selection scheme, fitness
uniform deletion scheme, preserve diversity, local optima, evolution,
universal similarity relation, correlated recombination, fitness tree
model, traveling salesman, set covering, satisfiability.",
abstract = "In evolutionary algorithms, the fitness of a population increases with
time by mutating and recombining individuals and by a biased selection
of more fit individuals. The right selection pressure is critical in
ensuring sufficient optimization progress on the one hand and in
preserving genetic diversity to be able to escape from local optima on
the other hand. Motivated by a universal similarity relation on the
individuals, we propose a new selection scheme, which is uniform in
the fitness values. It generates selection pressure toward sparsely
populated fitness regions, not necessarily toward higher fitness, as
is the case for all other selection schemes. We show analytically on a
simple example that the new selection scheme can be much more
effective than standard selection schemes. We also propose a new
deletion scheme which achieves a similar result via deletion and show
how such a scheme preserves genetic diversity more effectively than
standard approaches. We compare the performance of the new schemes to
tournament selection and random deletion on an artificial deceptive
problem and a range of NP-hard problems: traveling salesman, set
covering and satisfiability.",
}
@InProceedings{Hutter:06discount,
author = "Marcus Hutter",
title = "General Discounting versus Average Reward",
booktitle = "Proc. 17th International Conf. on Algorithmic Learning Theory ({ALT'06})",
address = "Barcelona",
series = "LNAI",
volume = "4264",
_editor = "Jose L. Balcázar and Phil Long and Frank Stephan",
publisher = "Springer, Berlin",
pages = "244--258",
_month = oct,
year = "2006",
bibtex = "http://www.hutter1.net/official/bib.htm#discount",
url = "http://arxiv.org/abs/cs.LG/0605040",
ftp = "http://www.idsia.ch/idsiareport/IDSIA-11-06.pdf",
conf = "http://www-alg.ist.hokudai.ac.jp/~thomas/ALT06/alt06.jhtml",
pdf = "http://www.hutter1.net/ai/discount.pdf",
ps = "http://www.hutter1.net/ai/discount.ps",
latex = "http://www.hutter1.net/ai/discount.tex",
slides = "http://www.hutter1.net/ai/sdiscount.pdf",
project = "http://www.hutter1.net/official/projects.htm#rl",
issn = "0302-9743",
isbn = "3-540-46649-5",
doi = "10.1007/11894841_21",
keywords = "reinforcement learning; average value;
discounted value; arbitrary environment;
arbitrary discount sequence; effective horizon;
increasing farsightedness; consistent behavior.",
abstract = "Consider an agent interacting with an environment in cycles. In
every interaction cycle the agent is rewarded for its performance.
We compare the average reward U from cycle 1 to m (average
value) with the future discounted reward V from cycle k to
infinity (discounted value). We consider essentially arbitrary
(non-geometric) discount sequences and arbitrary reward sequences
(non-MDP environments). We show that asymptotically U for
m->infinity and V for k->infinity are equal, provided both
limits exist. Further, if the effective horizon grows linearly
with k or faster, then existence of the limit of U implies
that the limit of V exists. Conversely, if the effective horizon
grows linearly with k or slower, then existence of the limit of
V implies that the limit of U exists.",
znote = "Acceptance rate: 24/53 = 45\%",
}
@InProceedings{Hutter:06actopt,
author = "Daniil Ryabko and Marcus Hutter",
title = "Asymptotic Learnability of Reinforcement Problems with Arbitrary Dependence",
booktitle = "Proc. 17th International Conf. on Algorithmic Learning Theory ({ALT'06})",
address = "Barcelona",
series = "LNAI",
volume = "4264",
_editor = "Jose L. Balcázar and Phil Long and Frank Stephan",
publisher = "Springer, Berlin",
pages = "334--347",
_month = oct,
year = "2006",
bibtex = "http://www.hutter1.net/official/bib.htm#actopt",
url = "http://arxiv.org/abs/cs.LG/0603110",
ftp = "http://www.idsia.ch/idsiareport/IDSIA-09-06.pdf",
conf = "http://www-alg.ist.hokudai.ac.jp/~thomas/ALT06/alt06.jhtml",
pdf = "http://www.hutter1.net/ai/actopt.pdf",
ps = "http://www.hutter1.net/ai/actopt.ps",
latex = "http://www.hutter1.net/ai/actopt.tex",
slides = "http://www.hutter1.net/ai/sactopt.pdf",
project = "http://www.hutter1.net/official/projects.htm#universal",
press = "http://www.hutter1.net/official/press.htm#universal",
issn = "0302-9743",
isbn = "3-540-46649-5",
doi = "10.1007/11894841_27",
keywords = "Reinforcement learning, asymptotic average value,
self-optimizing policies, (non) Markov decision processes.",
abstract = "We address the problem of reinforcement
learning in which observations may exhibit an arbitrary form of
stochastic dependence on past observations and actions,
i.e. environments more general than (PO)MDPs.
The task for an agent is to attain the best possible asymptotic
reward where the true generating environment is unknown but
belongs to a known countable family of environments. We find some
sufficient conditions on the class of environments under which an
agent exists which attains the best asymptotic reward for any
environment in the class. We analyze how tight these conditions
are and how they relate to different probabilistic assumptions
known in reinforcement learning and related fields, such as Markov
Decision Processes and mixing conditions.",
znote = "Acceptance rate: 24/53 = 45\%",
}
@Article{Hutter:06mdlspeedx,
author = "Jan Poland and Marcus Hutter",
title = "{MDL} Convergence Speed for {B}ernoulli Sequences",
journal = "Statistics and Computing",
volume = "16",
number = "2",
pages = "161--175",
_month = jun,
year = "2006",
bibtex = "http://www.hutter1.net/official/bib.htm#mdlspeedx",
url = "http://arxiv.org/abs/math.ST/0602505",
ftp = "http://www.idsia.ch/idsiareport/IDSIA-04-06.pdf",
pdf = "http://www.hutter1.net/ai/mdlspeedx.pdf",
ps = "http://www.hutter1.net/ai/mdlspeedx.ps",
latex = "http://www.hutter1.net/ai/mdlspeedx.tex",
slides = "http://www.hutter1.net/ai/smdlspeed.pdf",
slidesppt = "http://www.hutter1.net/ai/smdlspeed.ppt",
project = "http://www.hutter1.net/official/projects.htm#mdl",
issn = "0960-3174",
doi = "10.1007/s11222-006-6746-3",
keywords = "MDL, Minimum Description Length, Convergence Rate,
Prediction, Bernoulli, Discrete Model Class.",
abstract = "The Minimum Description Length principle for online sequence
estimation/prediction in a proper learning setup is studied. If
the underlying model class is discrete, then the total expected
square loss is a particularly interesting performance measure: (a)
this quantity is finitely bounded, implying convergence with
probability one, and (b) it additionally specifies the convergence
speed. For MDL, in general one can only have loss bounds which are
finite but exponentially larger than those for Bayes mixtures. We
show that this is even the case if the model class contains only
Bernoulli distributions. We derive a new upper bound on the
prediction error for countable Bernoulli classes. This implies a
small bound (comparable to the one for Bayes mixtures) for certain
important model classes. We discuss the application to Machine
Learning tasks such as classification and hypothesis testing, and
generalization to countable classes of i.i.d. models.",
}
@InProceedings{Hutter:06usp,
author = "Marcus Hutter",
title = "On the Foundations of Universal Sequence Prediction",
booktitle = "Proc. 3rd Annual Conference on Theory and
Applications of Models of Computation ({TAMC'06})",
volume = "3959",
series = "LNCS",
pages = "408--420",
_editor = "J.-Y. Cai and S. B. Cooper and A. Li",
publisher = "Springer",
_address = "Beijing",
_month = may,
year = "2006",
bibtex = "http://www.hutter1.net/official/bib.htm#usp",
url = "http://arxiv.org/abs/cs.LG/0605009",
ftp = "http://www.idsia.ch/idsiareport/IDSIA-03-06.pdf",
conf = "http://gcl.iscas.ac.cn/accl06/TAMC06_Home.htm",
pdf = "http://www.hutter1.net/ai/usp.pdf",
ps = "http://www.hutter1.net/ai/usp.ps",
latex = "http://www.hutter1.net/ai/usp.tex",
slides = "http://www.hutter1.net/ai/susp.pdf",
project = "http://www.hutter1.net/official/projects.htm#ait",
issn = "0302-9743",
isbn = "3-540-34021-1",
doi = "10.1007/11750321_39",
keywords = "Sequence prediction, Bayes, Solomonoff prior,
Kolmogorov complexity, Occam's razor, prediction bounds,
model classes, philosophical issues, symmetry principle,
confirmation theory, reparametrization invariance,
old-evidence/updating problem, (non)computable environments.",
abstract = "Solomonoff completed the Bayesian framework by providing a
rigorous, unique, formal, and universal choice for the model class
and the prior. We discuss in breadth how and in which sense
universal (non-i.i.d.) sequence prediction solves various
(philosophical) problems of traditional Bayesian sequence
prediction. We show that Solomonoff's model possesses many
desirable properties: Fast convergence and strong bounds, and in
contrast to most classical continuous prior densities has no zero
p(oste)rior problem, i.e. can confirm universal hypotheses, is
reparametrization and regrouping invariant, and avoids the
old-evidence and updating problem. It even performs well (actually
better) in non-computable environments.",
znote = "Acceptance rate: 76/400 = 19\%",
alt = "Also 2-page abstract and poster at 9th ISBA World Meeting (2008)",
abstract2p = "http://www.hutter1.net/ai/usps.pdf",
poster = "http://www.hutter1.net/ai/susps.pdf",
}
@InProceedings{Hutter:06aixifoe,
author = "Jan Poland and Marcus Hutter",
title = "Universal Learning of Repeated Matrix Games",
booktitle = "Proc. 15th Annual Machine Learning Conf. of {B}elgium and {T}he {N}etherlands ({Benelearn'06})",
pages = "7--14",
address = "Ghent",
_editor = "Yvan Saeys and Bernard De Baets and Elena Tsiporkova and Yves Van de Peer",
xpublisher = "",
_month = may,
year = "2006",
isbn = "90 382 0948 7",
bibtex = "http://www.hutter1.net/official/bib.htm#aixifoe",
url = "http://arxiv.org/abs/cs.LG/0508073",
ftp = "http://www.idsia.ch/idsiareport/IDSIA-18-05.pdf",
conf = "http://bioinformatics.psb.ugent.be/benelearn2006/",
pdf = "http://www.hutter1.net/ai/aixifoe.pdf",
ps = "http://www.hutter1.net/ai/aixifoe.ps",
latex = "http://www.hutter1.net/ai/aixifoe.zip",
slides = "http://www.hutter1.net/ai/saixifoe.pdf",
project = "http://www.hutter1.net/official/projects.htm#expert",
abstract = "We study and compare the learning dynamics of two universal
learning algorithms, one based on Bayesian learning and the
other on prediction with expert advice. Both approaches have
strong asymptotic performance guarantees. When confronted with
the task of finding good long-term strategies in repeated
2 x 2 matrix games, they behave quite differently. We consider
the case where the learning algorithms are not even informed
about the game they are playing.",
}
@InProceedings{Hutter:06ior,
author = "Shane Legg and Marcus Hutter",
title = "A Formal Measure of Machine Intelligence",
booktitle = "Proc. 15th Annual Machine Learning Conference of {B}elgium and {T}he {N}etherlands ({Benelearn'06})",
pages = "73--80",
address = "Ghent",
_editor = "Yvan Saeys and Bernard De Baets and Elena Tsiporkova and Yves Van de Peer",
_month = may,
year = "2006",
isbn = "90 382 0948 7",
bibtex = "http://www.hutter1.net/official/bib.htm#ior",
url = "http://arxiv.org/abs/cs.AI/0605024",
ftp = "http://www.idsia.ch/idsiareport/IDSIA-10-06.pdf",
conf = "http://bioinformatics.psb.ugent.be/benelearn2006/",
pdf = "http://www.hutter1.net/ai/ior.pdf",
ps = "http://www.hutter1.net/ai/ior.ps",
latex = "http://www.hutter1.net/ai/ior.zip",
slides = "http://www.hutter1.net/ai/sior.pdf",
project = "http://www.hutter1.net/official/projects.htm#uai",
press = "http://www.hutter1.net/official/press.htm#ior",
abstract = "A fundamental problem in artificial intelligence is that nobody really
knows what intelligence is. The problem is especially acute when we
need to consider artificial systems which are significantly different
to humans. In this paper we approach this problem in the following
way: We take a number of well known informal definitions of human
intelligence that have been given by experts, and extract their
essential features. These are then mathematically formalised to
produce a general measure of intelligence for arbitrary machines. We
believe that this measure formally captures the concept of machine
intelligence in the broadest reasonable sense.",
}
@InProceedings{Hutter:06robot,
author = "Viktor Zhumatiy and Faustino Gomez and Marcus Hutter and J{\"u}rgen Schmidhuber",
title = "Metric State Space Reinforcement Learning for a Vision-Capable Mobile Robot",
booktitle = "Proc. 9th International Conf. on Intelligent Autonomous Systems ({IAS'06})",
pages = "272--281",
_editor = "Tamio Arai and Rolf Pfeifer and Tucker Balch and Hiroshi Yokoi",
publisher = "IOR Press",
_month = mar,
year = "2006",
bibtex = "http://www.hutter1.net/official/bib.htm#robot",
url = "http://arxiv.org/abs/cs.RO/0603023",
ftp = "http://www.idsia.ch/idsiareport/IDSIA-05-06.pdf",
conf = "http://www.arai.pe.u-tokyo.ac.jp/IAS-9/",
pdf = "http://www.hutter1.net/ai/robot.pdf",
ps = "http://www.hutter1.net/ai/robot.ps",
latex = "http://www.hutter1.net/ai/robot.zip",
slides = "http://www.hutter1.net/ai/srobot.pdf",
slidesppt = "http://www.hutter1.net/ai/srobot.ppt",
isbn = "1-58603-595-9",
keywords = "reinforcement learning; mobile robots.",
abstract = "We address the problem of autonomously learning controllers for
vision-capable mobile robots. We extend McCallum's (1995)
Nearest-Sequence Memory algorithm to allow for general metrics
over state-action trajectories. We demonstrate the feasibility of
our approach by successfully running our algorithm on a real
mobile robot. The algorithm is novel and unique in that it (a)
explores the environment and learns directly on a mobile robot
without using a hand-made computer model as an intermediate step,
(b) does not require manual discretization of the sensor input
space, (c) works in piecewise continuous perceptual spaces, and
(d) copes with partial observability. Together this allows
learning from much less experience compared to previous methods.",
znote = "Acceptance rate: 112/146 = 77\%",
}
@Article{Hutter:06knapsack,
author = "Monaldo Mastrolilli and Marcus Hutter",
title = "Hybrid Rounding Techniques for Knapsack Problems",
journal = "Discrete Applied Mathematics",
volume = "154",
number = "4",
pages = "640--649",
_month = mar,
year = "2006",
bibtex = "http://www.hutter1.net/official/bib.htm#knapsack",
url = "http://arxiv.org/abs/cs.CC/0305002",
ftp = "http://www.idsia.ch/idsiareport/IDSIA-03-02.ps.gz",
pdf = "http://www.hutter1.net/ai/knapsack.pdf",
ps = "http://www.hutter1.net/ai/knapsack.ps",
latex = "http://www.hutter1.net/ai/knapsack.tex",
project = "http://www.hutter1.net/official/projects.htm#optimize",
issn = "0166-218X",
doi = "10.1016/j.dam.2005.08.004",
abstract = "We address the classical knapsack problem and a variant in which an upper
bound is imposed on the number of items that can be selected. We show that
appropriate combinations of rounding techniques yield novel and powerful
ways of rounding. As an application of these techniques, we present faster
polynomial time approximation schemes that computes an approximate solution
of any fixed accuracy in linear time. This linear complexity bounds give a
substantial improvement of the best previously known polynomial bounds",
}
@Article{Hutter:06unimdlx,
author = "Marcus Hutter",
title = "Sequential Predictions based on Algorithmic Complexity",
journal = "Journal of Computer and System Sciences",
volume = "72",
number = "1",
pages = "95--117",
_month = feb,
year = "2006",
url = "http://arxiv.org/abs/cs.IT/0508043",
ftp = "http://www.idsia.ch/idsiareport/IDSIA-16-04.pdf",
bibtex = "http://www.hutter1.net/official/bib.htm#unimdlx",
url = "http://arxiv.org/abs/cs.IT/0508043",
ftp = "http://www.idsia.ch/idsiareport/IDSIA-16-04.pdf",
pdf = "http://www.hutter1.net/ai/unimdlx.pdf",
ps = "http://www.hutter1.net/ai/unimdlx.ps",
latex = "http://www.hutter1.net/ai/unimdlx.tex",
slides = "http://www.hutter1.net/ai/sunimdl.pdf",
project = "http://www.hutter1.net/official/projects.htm#mdl",
issn = "0022-0000",
doi = "10.1016/j.jcss.2005.07.001",
keywords = "Sequence prediction; Algorithmic Information Theory;
Solomonoff's prior; Monotone Kolmogorov Complexity;
Minimal Description Length; Convergence;
Self-Optimizingness",
abstract = "This paper studies sequence prediction based on the
monotone Kolmogorov complexity $\Km=-\lb m$, i.e.\ based on
universal MDL. $m$ is extremely close to Solomonoff's prior $M$,
the latter being an excellent predictor in deterministic as well
as probabilistic environments, where performance is measured in
terms of convergence of posteriors or losses. Despite this
closeness to $M$, it is difficult to assess the prediction quality
of $m$, since little is known about the closeness of their
posteriors, which are the important quantities for prediction.
We show that for deterministic computable environments, the
``posterior'' and losses of $m$ converge, but rapid convergence
could only be shown on-sequence; the off-sequence behavior is
unclear. In probabilistic environments, neither the posterior nor
the losses converge, in general.",
}
@Proceedings{Hutter:06kcdagabs,
editor = "Marcus Hutter and Wolfgang Merkle and Paul M. B. Vit\'anyi",
title = "Kolmogorov Complexity and Applications",
number = "06051",
_month = jan/aug,
year = "2006",
series = "Dagstuhl Seminar Proceedings",
url1 = "http://www.hutter1.net/dagstuhl/",
url2 = "http://drops.dagstuhl.de/portals/06051",
url3 = "http://drops.dagstuhl.de/opus/volltexte/2006/663",
pdf = "http://www.hutter1.net/ai/kcdagabs.pdf",
ps = "http://www.hutter1.net/ai/kcdagabs.ps",
latex = "http://www.hutter1.net/ai/kcdagabs.tex",
project = "http://www.hutter1.net/official/projects.htm#ait",
issn = "1862-4405",
publisher = "IBFI",
_publisher = "Internationales Begegnungs- und Forschungszentrum fuer Informatik (IBFI), Schloss Dagstuhl, Germany",
address = "Dagstuhl, Germany",
keywords = "Information theory, Kolmogorov Complexity, effective randomnes,
algorithmic probability, recursion theory, computational complexity,
machine learning",
abstract = "From 29.01.06 to 03.02.06,
the Dagstuhl Seminar 06051 ``Kolmogorov Complexity and Applications''
was held in the International Conference and Research Center (IBFI),
Schloss Dagstuhl. During the seminar, several participants presented
their current research, and ongoing work and open problems were
discussed. Abstracts of the presentations given during the seminar
as well as abstracts of seminar results and ideas are put together
in this proceedings. The first section describes the seminar topics and
goals in general. Links to extended abstracts or full papers are
provided, if available.",
note = "http://drops.dagstuhl.de/portals/06051",
}
%-------------Publications-of-Marcus-Hutter-2005--------------%
@Article{Hutter:05mdl2px,
author = "Jan Poland and Marcus Hutter",
title = "Asymptotics of Discrete {MDL} for Online Prediction",
journal = "IEEE Transactions on Information Theory",
_month = nov,
volume = "51",
number = "11",
pages = "3780--3795",
year = "2005",
bibtex = "http://www.hutter1.net/official/bib.htm#mdl2px",
url = "http://arxiv.org/abs/cs.IT/0506022",
ftp = "http://www.idsia.ch/idsiareport/IDSIA-13-05.pdf",
pdf = "http://www.hutter1.net/ai/mdl2px.pdf",
ps = "http://www.hutter1.net/ai/mdl2px.ps",
latex = "http://www.hutter1.net/ai/mdl2px.zip",
slides = "http://www.hutter1.net/ai/smdl2p.pdf",
slidesppt = "http://www.hutter1.net/ai/smdl2p.ppt",
project = "http://www.hutter1.net/official/projects.htm#mdl",
doi = "10.1109/TIT.2005.856956",
issn = "0018-9448",
keywords = "Algorithmic Information Theory, Classification, Consistency,
Discrete Model Class, Loss Bounds, Minimum Description Length,
Regression, Sequence Prediction, Stabilization, Universal Induction.",
abstract = "Minimum Description Length (MDL) is an important principle for induction and
prediction, with strong relations to optimal Bayesian learning. This paper
deals with learning non-i.i.d. processes by means of two-part MDL, where the
underlying model class is countable. We consider the online learning framework,
i.e. observations come in one by one, and the predictor is allowed to update
his state of mind after each time step. We identify two ways of predicting by
MDL for this setup, namely a static and a dynamic one. (A third variant,
hybrid MDL, will turn out inferior.) We will prove that under the only
assumption that the data is generated by a distribution contained in the model
class, the MDL predictions converge to the true values almost surely. This is
accomplished by proving finite bounds on the quadratic, the Hellinger, and the
Kullback-Leibler loss of the MDL learner, which are however exponentially worse
than for Bayesian prediction. We demonstrate that these bounds are sharp, even
for model classes containing only Bernoulli distributions. We show how these
bounds imply regret bounds for arbitrary loss functions. Our results apply to a
wide range of setups, namely sequence prediction, pattern classification,
regression, and universal induction in the sense of Algorithmic Information
Theory among others.",
}
@Article{Hutter:05tree,
author = "Marco Zaffalon and Marcus Hutter",
title = "Robust Inference of Trees",
journal = "Annals of Mathematics and Artificial Intelligence",
volume = "45",
pages = "215--239",
_month oct,
year = "2005",
_publisher = "Springer",
bibtex = "http://www.hutter1.net/official/bib.htm#tree",
url = "http://arxiv.org/abs/cs.LG/0511087",
ftp = "http://www.idsia.ch/idsiareport/IDSIA-11-03.pdf",
pdf = "http://www.hutter1.net/ai/tree.pdf",
ps = "http://www.hutter1.net/ai/tree.ps",
latex = "http://www.hutter1.net/ai/tree.zip",
project = "http://www.hutter1.net/official/projects.htm#robust",
doi = "10.1007/s10472-005-9007-9",
issn = "1012-2443",
categories = "I.2. [Artificial Intelligence]",
keywords = "Robust inference, spanning trees, intervals,
dependence, graphical models, mutual information, imprecise
probabilities, imprecise Dirichlet model.",
abstract = "This paper is concerned with the reliable inference of optimal
tree-approximations to the dependency structure of an unknown
distribution generating data. The traditional approach to the
problem measures the dependency strength between random variables
by the index called mutual information. In this paper reliability
is achieved by Walley's imprecise Dirichlet model, which
generalizes Bayesian learning with Dirichlet priors. Adopting the
imprecise Dirichlet model results in posterior interval
expectation for mutual information, and in a set of plausible
trees consistent with the data. Reliable inference about the
actual tree is achieved by focusing on the substructure common to
all the plausible trees. We develop an exact algorithm that infers
the substructure in time O(m^4), m being the number of random
variables. The new algorithm is applied to a set of data sampled
from a known distribution. The method is shown to reliably infer
edges of the actual tree even when the data are very scarce,
unlike the traditional approach. Finally, we provide lower and
upper credibility limits for mutual information under the
imprecise Dirichlet model. These enable the previous developments
to be extended to a full inferential method for trees.",
}
@InProceedings{Hutter:05postbnd,
author = "Alexey Chernov and Marcus Hutter",
title = "Monotone Conditional Complexity Bounds on Future Prediction Errors",
booktitle = "Proc. 16th International Conf. on Algorithmic Learning Theory ({ALT'05})",
address = "Singapore",
series = "LNAI",
volume = "3734",
_editor = "Sanjay Jain and Hans Ulrich Simon and Etsuji Tomita",
publisher = "Springer, Berlin",
pages = "414--428",
_month = oct,
year = "2005",
bibtex = "http://www.hutter1.net/official/bib.htm#postbnd",
url = "http://arxiv.org/abs/cs.LG/0507041",
ftp = "http://www.idsia.ch/idsiareport/IDSIA-16-05.pdf",
pdf = "http://www.hutter1.net/ai/postbnd.pdf",
ps = "http://www.hutter1.net/ai/postbnd.ps",
latex = "http://www.hutter1.net/ai/postbnd.tex",
slides = "http://www.hutter1.net/ai/spostbnd.pdf",
project = "http://www.hutter1.net/official/projects.htm#ait",
issn = "0302-9743",
isbn = "3-540-29242-X",
keywords = "Kolmogorov complexity, posterior bounds,
online sequential prediction, Solomonoff prior,
monotone conditional complexity, total error,
future loss, randomness deficiency.",
abstract = "We bound the future loss when predicting any (computably)
stochastic sequence online. Solomonoff finitely bounded the total
deviation of his universal predictor M from the true
distribution m by the algorithmic complexity of m. Here we
assume we are at a time t>1 and already observed x=x_1...x_t.
We bound the future prediction performance on x_{t+1}x_{t+2}...
by a new variant of algorithmic complexity of m given x,
plus the complexity of the randomness deficiency of x. The new
complexity is monotone in its condition in the sense that this
complexity can only decrease if the condition is prolonged. We
also briefly discuss potential generalizations to Bayesian model
classes and to classification problems.",
support = "SNF grant 200020-100259 and 2100-67712",
znote = "Acceptance rate: 30/98 = 30\%",
}
@InProceedings{Hutter:05actexp2,
author = "Jan Poland and Marcus Hutter",
title = "Defensive Universal Learning with Experts",
booktitle = "Proc. 16th International Conf. on Algorithmic Learning Theory ({ALT'05})",
address = "Singapore",
series = "LNAI",
volume = "3734",
_editor = "Sanjay Jain and Hans Ulrich Simon and Etsuji Tomita",
publisher = "Springer, Berlin",
_month = oct,
pages = "356--370",
year = "2005",
bibtex = "http://www.hutter1.net/official/bib.htm#actexp2",
url = "http://arxiv.org/abs/cs.LG/0507044",
ftp = "http://www.idsia.ch/idsiareport/IDSIA-15-05.pdf",
pdf = "http://www.hutter1.net/ai/actexp2.pdf",
ps = "http://www.hutter1.net/ai/actexp2.ps",
latex = "http://www.hutter1.net/ai/actexp2.tex",
slides = "http://www.hutter1.net/ai/sactexp.pdf",
slidesppt = "http://www.hutter1.net/ai/sactexp.ppt",
project = "http://www.hutter1.net/official/projects.htm#expert",
issn = "0302-9743",
isbn = "3-540-29242-X",
keywords = "Prediction with expert advice, responsive
environments, partial observation game, bandits, universal
learning, asymptotic optimality.",
abstract = "This paper shows how universal learning can be achieved with
expert advice. To this aim, we specify an experts algorithm with
the following characteristics: (a) it uses only feedback from the
actions actually chosen (bandit setup), (b) it can be applied with
countably infinite expert classes, and (c) it copes with losses
that may grow in time appropriately slowly. We prove loss bounds
against an adaptive adversary. From this, we obtain a master
algorithm for ``reactive'' experts problems, which means that the
master's actions may influence the behavior of the adversary. Our
algorithm can significantly outperform standard experts algorithms
on such problems. Finally, we combine it with a universal expert
class. The resulting universal learner performs -- in a certain
sense -- almost as well as any computable strategy, for any online
decision problem. We also specify the (worst-case) convergence
speed, which is very slow.",
znote = "Acceptance rate: 30/98 = 30\%",
}
@InProceedings{Hutter:05iors,
author = "Shane Legg and Marcus Hutter",
title = "A Universal Measure of Intelligence for Artificial Agents",
booktitle = "Proc. 21st International Joint Conf. on Artificial Intelligence ({IJCAI-2005})",
pages = "1509--1510",
_editor = "L. P. Kaelbling and A. Saffiotti",
_publisher = "Professional Book Center",
address = "Edinburgh",
_month = aug,
year = "2005",
bibtex = "http://www.hutter1.net/official/bib.htm#iors",
ftp = "http://www.idsia.ch/idsiareport/IDSIA-04-05.pdf",
conf = "http://ijcai05.csd.abdn.ac.uk/index.php?section=posterlist",
pdf = "http://www.hutter1.net/ai/iors.pdf",
ps = "http://www.hutter1.net/ai/iors.ps",
slides = "http://www.hutter1.net/ai/siors.pdf",
project = "http://www.hutter1.net/official/projects.htm#uai",
press = "http://www.hutter1.net/official/press.htm#ior",
code = "http://www.hutter1.net/ai/iors.cpp",
isbn_print = "0-938075-93-4",
isbn_cd = "0-938075-94-2",
support = "SNF grant 2100-67712",
znote = "Acceptance rate: 112/453 = 25\%",
}
@InProceedings{Hutter:05fuds,
author = "Shane Legg and Marcus Hutter",
title = "Fitness Uniform Deletion for Robust Optimization",
booktitle = "Proc. Genetic and Evolutionary Computation Conference ({GECCO'05})",
address = "Washington, OR",
editor = "H.-G. Beyer et al.",
publisher = "ACM SigEvo",
_month = jun,
year = "2005",
pages = "1271--1278",
bibtex = "http://www.hutter1.net/official/bib.htm#fuds",
http = "http://www.hutter1.net/ai/fuds.htm",
url = "http://arxiv.org/abs/cs.NE/0504035",
ftp = "http://www.idsia.ch/idsiareport/IDSIA-11-04.pdf",
pdf = "http://www.hutter1.net/ai/fuds.pdf",
ps = "http://www.hutter1.net/ai/fuds.ps",
latex = "http://www.hutter1.net/ai/fuds.zip",
slides = "http://www.hutter1.net/ai/sfuds.pdf",
slidesppt = "http://www.hutter1.net/ai/sfuds.ppt",
project = "http://www.hutter1.net/official/projects.htm#optimize",
press = "http://www.hutter1.net/official/press.htm#fuss",
code1 = "http://www.hutter1.net/ai/fussdd.cpp",
code2 = "http://www.hutter1.net/ai/fussdd.h",
code3 = "http://www.hutter1.net/ai/fusstsp.cpp",
code4 = "http://www.hutter1.net/ai/fusstsp.h",
isbn = "1-59593-010-8",
keywords = "Evolutionary algorithm, deletion schemes, fitness evaluation,
optimization, fitness landscapes, (self)adaptation.",
abstract = "A commonly experienced problem with population based optimisation
methods is the gradual decline in population diversity that tends
to occur over time. This can slow a system's progress or even
halt it completely if the population converges on a local optimum
from which it cannot escape. In this paper we present the Fitness
Uniform Deletion Scheme (FUDS), a simple but somewhat
unconventional approach to this problem. Under FUDS the deletion
operation is modified to only delete those individuals which are
``common'' in the sense that there exist many other individuals of
similar fitness in the population. This makes it impossible for
the population to collapse to a collection of highly related
individuals with similar fitness. Our experimental results on a
range of optimisation problems confirm this, in particular for
deceptive optimisation problems the performance is significantly
more robust to variation in the selection intensity.",
znote = "Acceptance rate: 253/549 = 46\%",
}
@Article{Hutter:05expertx,
author = "Marcus Hutter and Jan Poland",
title = "Adaptive Online Prediction by Following the Perturbed Leader",
volume = "6",
_month = apr,
year = "2005",
pages = "639--660",
journal = "Journal of Machine Learning Research",
publisher = "Microtome",
bibtex = "http://www.hutter1.net/official/bib.htm#expertx",
http = "http://www.hutter1.net/ai/expertx.htm",
url = "http://arxiv.org/abs/cs.AI/0504078",
url2 = "http://www.jmlr.org/papers/v6/hutter05a.html",
ftp = "http://www.idsia.ch/idsiareport/IDSIA-10-05.pdf",
pdf = "http://www.hutter1.net/ai/expertx.pdf",
ps = "http://www.hutter1.net/ai/expertx.ps",
latex = "http://www.hutter1.net/ai/expertx.tex",
slides = "http://www.hutter1.net/ai/sexpert.pdf",
project = "http://www.hutter1.net/official/projects.htm#expert",
issn = "1532-4435",
keywords = "Prediction with Expert Advice, Follow the Perturbed Leader,
general weights, adaptive learning rate,
adaptive adversary, hierarchy of experts,
expected and high probability bounds, general alphabet and loss,
online sequential prediction.",
abstract = "When applying aggregating strategies to Prediction with Expert
Advice, the learning rate must be adaptively tuned. The natural
choice of sqrt(complexity/current loss) renders the analysis of
Weighted Majority derivatives quite complicated. In particular,
for arbitrary weights there have been no results proven so far.
The analysis of the alternative ``Follow the Perturbed Leader''
(FPL) algorithm from Kalai & Vempala (2003) (based on Hannan's
algorithm) is easier. We derive loss bounds for adaptive learning
rate and both finite expert classes with uniform weights and
countable expert classes with arbitrary weights. For the former
setup, our loss bounds match the best known results so far, while
for the latter our results are new.",
}
@Article{Hutter:05mifs,
author = "Marcus Hutter and Marco Zaffalon",
title = "Distribution of Mutual Information from Complete and Incomplete Data",
journal = "Computational Statistics \& Data Analysis",
volume = "48",
number = "3",
pages = "633--657",
_month = mar,
year = "2005",
publisher = "Elsevier Science",
bibtex = "http://www.hutter1.net/official/bib.htm#mifs",
http = "http://www.hutter1.net/ai/mifs.htm",
url = "http://arxiv.org/abs/cs.LG/0403025",
ftp = "http://www.idsia.ch/idsiareport/IDSIA-11-02.pdf",
pdf = "http://www.hutter1.net/ai/mifs.pdf",
ps = "http://www.hutter1.net/ai/mifs.ps",
latex = "http://www.hutter1.net/ai/mifs.zip",
slides = "http://www.hutter1.net/ai/smimiss.pdf",
slidesppt = "http://www.hutter1.net/ai/smimiss.ppt",
project = "http://www.hutter1.net/official/projects.htm#robust",
code = "http://www.hutter1.net/ai/mifs.cpp",
doi = "10.1016/j.csda.2004.03.010",
issn = "0167-9473",
categories = "I.2. [Artificial Intelligence]",
keywords = "Mutual information, cross entropy, Dirichlet distribution, second
order distribution, expectation and variance of mutual
information, feature selection, filters, naive Bayes classifier,
Bayesian statistics.",
abstract = "Mutual information is widely used, in a descriptive way, to measure the
stochastic dependence of categorical random variables. In order to address
questions such as the reliability of the descriptive value, one must consider
sample-to-population inferential approaches. This paper deals with the
posterior distribution of mutual information, as obtained in a Bayesian
framework by a second-order Dirichlet prior distribution. The exact analytical
expression for the mean, and analytical approximations for the variance,
skewness and kurtosis are derived. These approximations have a guaranteed
accuracy level of the order O(1/n^3), where n is the sample size. Leading order
approximations for the mean and the variance are derived in the case of
incomplete samples. The derived analytical expressions allow the distribution
of mutual information to be approximated reliably and quickly. In fact, the
derived expressions can be computed with the same order of complexity needed
for descriptive mutual information. This makes the distribution of mutual
information become a concrete alternative to descriptive mutual information in
many applications which would benefit from moving to the inductive side. Some
of these prospective applications are discussed, and one of them, namely
feature selection, is shown to perform significantly better when inductive
mutual information is used.",
}
@InProceedings{Hutter:05mdlreg,
author = "Jan Poland and Marcus Hutter",
title = "Strong Asymptotic Assertions for Discrete {MDL} in Regression and Classification",
booktitle = "Proc. 14th {D}utch-{B}elgium Conf. on Machine Learning ({Benelearn'05})",
address = "Enschede",
_editor = "Martijn {van Otterlo} and Mannes Poel and Anton Nijholt",
pages = "67--72",
_month = feb,
year = "2005",
_number = "WP05-03",
_series = "CTIT Workshop Proceedings Series",
_organization = "CTIT Research Institute, University of Twente",
bibtex = "http://www.hutter1.net/official/bib.htm#mdlreg",
url = "http://arxiv.org/abs/math.ST/0502315",
conf = "http://hmi.ewi.utwente.nl/conference/benelearn2005",
ftp = "http://www.idsia.ch/idsiareport/IDSIA-02-05.pdf",
pdf = "http://www.hutter1.net/ai/mdlreg.pdf",
ps = "http://www.hutter1.net/ai/mdlreg.ps",
latex = "http://www.hutter1.net/ai/mdlreg.tex",
slides = "http://www.hutter1.net/ai/smdlreg.pdf",
slidesppt = "http://www.hutter1.net/ai/smdlreg.ppt",
project = "http://www.hutter1.net/official/projects.htm#mdl",
issn = "0929-0672",
keywords = "Regression, Classification, Sequence Prediction,
Machine Learning, Minimum Description Length, Bayes Mixture,
Marginalization, Convergence, Discrete Model Classes.",
abstract = "We study the properties of the MDL (or maximum penalized
complexity) estimator for Regression and Classification, where the
underlying model class is countable. We show in particular a
finite bound on the Hellinger losses under the only assumption
that there is a ``true'' model contained in the class. This implies
almost sure convergence of the predictive distribution to the true
one at a fast rate. It corresponds to Solomonoff's central theorem
of universal induction, however with a bound that is exponentially
larger.",
}
@InProceedings{Hutter:05actexp,
author = "Jan Poland and Marcus Hutter",
title = "Master Algorithms for Active Experts Problems based on Increasing Loss Values",
booktitle = "Proc. 14th {D}utch-{B}elgium Conf. on Machine Learning ({Benelearn'05})",
address = "Enschede",
_editor = "Martijn {van Otterlo} and Mannes Poel and Anton Nijholt",
pages = "59--66",
_month = feb,
year = "2005",
_number = "WP05-03",
_series = "CTIT Workshop Proceedings Series",
_organization = "CTIT Research Institute, University of Twente",
bibtex = "http://www.hutter1.net/official/bib.htm#actexp",
url = "http://arxiv.org/abs/cs.LG/0502067",
ftp = "http://www.idsia.ch/idsiareport/IDSIA-01-05.pdf",
conf = "http://hmi.ewi.utwente.nl/conference/benelearn2005",
pdf = "http://www.hutter1.net/ai/actexp.pdf",
ps = "http://www.hutter1.net/ai/actexp.ps",
latex = "http://www.hutter1.net/ai/actexp.tex",
slides = "http://www.hutter1.net/ai/sactexp.pdf",
slidesppt = "http://www.hutter1.net/ai/sactexp.ppt",
project = "http://www.hutter1.net/official/projects.htm#expert",
issn = "0929-0672",
keywords = "Prediction with expert advice, responsive
environments, partial observation game, bandits, universal
learning, asymptotic optimality.",
abstract = "We specify an experts algorithm with the following
characteristics: (a) it uses only feedback from the actions
actually chosen (bandit setup), (b) it can be applied with
countably infinite expert classes, and (c) it copes with
losses that may grow in time appropriately slowly. We
prove loss bounds against an adaptive adversary. From this, we
obtain master algorithms for ``active experts problems'', which
means that the master's actions may influence the behavior of
the adversary. Our algorithm can significantly outperform
standard experts algorithms on such problems. Finally, we
combine it with a universal expert class. This results in a
(computationally infeasible) universal master algorithm
which performs - in a certain sense - almost as well as any
computable strategy, for any online problem.",
}
@Slides{Hutter:05predict,
author = "Marcus Hutter",
title = "How to predict with {Bayes}, {MDL}, and {Experts}",
_month = jan,
year = "2005",
note = "Presented at the Machine Learning Summer School (MLSS)",
http = "http://canberra05.mlss.cc/",
url = "http://www.idsia.ch/~marcus/ai/predict.htm",
slides = "http://www.idsia.ch/~marcus/ai/spredict.pdf",
}
@InProceedings{Hutter:05bayestree,
author = "Marcus Hutter",
title = "Fast Non-Parametric {B}ayesian Inference on Infinite Trees",
booktitle = "Proc. 10th International Conf. on Artificial Intelligence and Statistics ({AISTATS-2005})",
_address = "Barbados",
_editor = "R. G. Cowell and Z. Ghahramani",
publisher = "Society for Artificial Intelligence and Statistics",
pages = "144--151",
_month = jan,
year = "2005",
bibtex = "http://www.hutter1.net/official/bib.htm#bayestree",
http = "http://www.hutter1.net/ai/bayestree.htm",
url = "http://arxiv.org/abs/math.PR/0411515",
ftp = "http://www.idsia.ch/idsiareport/IDSIA-24-04.pdf",
pdf = "http://www.hutter1.net/ai/bayestree.pdf",
ps = "http://www.hutter1.net/ai/bayestree.ps",
latex = "http://www.hutter1.net/ai/bayestree.zip",
slides = "http://www.hutter1.net/ai/sbayestree.pdf",
project = "http://www.hutter1.net/official/projects.htm#bayes",
code = "http://www.hutter1.net/ai/bayestree.c",
isbn = "0-9727358-1-X",
keywords = "Bayesian density estimation, exact linear time algorithm,
non-parametric inference, adaptive infinite tree, Polya tree,
scale invariance.",
abstract = "Given i.i.d. data from an unknown distribution,
we consider the problem of predicting future items.
An adaptive way to estimate the probability density
is to recursively subdivide the domain to an appropriate
data-dependent granularity. A Bayesian would assign a
data-independent prior probability to ``subdivide'', which leads
to a prior over infinite(ly many) trees. We derive an exact, fast,
and simple inference algorithm for such a prior, for the data
evidence, the predictive distribution, the effective model
dimension, and other quantities.",
znote = "Acceptance rate: 57/150 = 38\%",
}
%-------------Publications-of-Marcus-Hutter-2004--------------%
TechReport{Hutter:04mdp,
author = "Shane Legg and Marcus Hutter",
number = "IDSIA-21-04",
title = "Ergodic {MDP}s Admit Self-Optimising Policies",
year = "2004",
institution = "{IDSIA}",
}
TechReport{Hutter:04env,
author = "Shane Legg and Marcus Hutter",
number = "IDSIA-20-04",
title = "A Taxonomy for Abstract Environments",
year = "2004",
institution = "{IDSIA}",
}
@Book{Hutter:04uaibook,
author = "Marcus Hutter",
title = "Universal Artificial Intelligence:
Sequential Decisions based on Algorithmic Probability",
_series = "EATCS",
publisher = "Springer",
address = "Berlin",
year = "2004",
note = "300 pages, http://www.idsia.ch/$_{^{\sim}}$marcus/ai/uaibook.htm",
url = "http://www.hutter1.net/ai/uaibook.htm",
review = "http://www.reviews.com/review/review_review.cfm?review_id=131175",
keywords = "Artificial intelligence; algorithmic probability;
sequential decision theory; Solomonoff induction;
Kolmogorov complexity; Bayes mixture distributions;
reinforcement learning; universal sequence prediction;
tight loss and error bounds; Levin search;
strategic games; function minimization; supervised learning.",
abstract = "This book presents sequential decision theory from a
novel algorithmic information theory perspective. While the former
theory is suited for active agents in known environments, the
latter is suited for passive prediction of unknown environments.
The book introduces these two well-known but very different ideas
and removes the limitations by unifying them to one parameter-free
theory of an optimal reinforcement learning agent interacting with
an arbitrary unknown world. Most if not all AI problems can easily
be formulated within this theory, which reduces the conceptual
problems to pure computational ones. Considered problem classes
include sequence prediction, strategic games, function
minimization, reinforcement and supervised learning. Formal
definitions of intelligence order relations, the horizon problem
and relations to other approaches to AI are discussed. One
intention of this book is to excite a broader AI audience about
abstract algorithmic information theory concepts, and conversely
to inform theorists about exciting applications to AI.",
}
@InProceedings{Hutter:04mlconvx,
author = "Marcus Hutter and Andrej A. Muchnik",
title = "Universal Convergence of Semimeasures on Individual Random Sequences",
booktitle = "Proc. 15th International Conf. on Algorithmic Learning Theory ({ALT'04})",
address = "Padova",
series = "LNAI",
volume = "3244",
_editor = "S. Ben-David and J. Case and A. Maruoka",
publisher = "Springer, Berlin",
pages = "234--248",
year = "2004",
issn = "0302-9743",
isbn = "3-540-23356-3",
http = "http://www.hutter1.net/ai/mlconvx.htm",
url = "http://arxiv.org/abs/cs.LG/0407057",
ftp = "http://www.idsia.ch/idsiareport/IDSIA-14-04.pdf",
keywords = "Sequence prediction; Algorithmic Information Theory;
universal enumerable semimeasure; mixture distributions;
posterior convergence; Martin-L{\"o}f randomness;
quasimeasures.",
abstract = "Solomonoff's central result on induction is that the posterior of
a universal semimeasure M converges rapidly and with probability
1 to the true sequence generating posterior mu, if the latter is
computable. Hence, M is eligible as a universal sequence predictor
in case of unknown mu. Despite some nearby results and proofs in
the literature, the stronger result of convergence for all
(Martin-Loef) random sequences remained open. Such a convergence
result would be particularly interesting and natural, since
randomness can be defined in terms of M itself. We show that there
are universal semimeasures M which do not converge for all random
sequences, i.e. we give a partial negative answer to the open
problem. We also provide a positive answer for some non-universal
semimeasures. We define the incomputable measure D as a mixture
over all computable measures and the enumerable semimeasure W as a
mixture over all enumerable nearly-measures. We show that W
converges to D and D to mu on all random sequences. The Hellinger
distance measuring closeness of two distributions plays
a central role.",
znote = "Acceptance rate: 29/91 = 32\%",
}
@InProceedings{Hutter:04expert,
author = "Marcus Hutter and Jan Poland",
title = "Prediction with Expert Advice by Following the Perturbed Leader for General Weights",
booktitle = "Proc. 15th International Conf. on Algorithmic Learning Theory ({ALT'04})",
address = "Padova",
series = "LNAI",
volume = "3244",
_editor = "S. Ben-David and J. Case and A. Maruoka",
publisher = "Springer, Berlin",
pages = "279--293",
year = "2004",
issn = "0302-9743",
isbn = "3-540-23356-3",
http = "http://www.hutter1.net/ai/expert.htm",
url = "http://arxiv.org/abs/cs.LG/0405043",
ftp = "http://www.idsia.ch/idsiareport/IDSIA-08-04.pdf",
keywords = "Prediction with Expert Advice, Follow the Perturbed Leader,
general weights, adaptive learning rate,
hierarchy of experts, expected and high probability bounds,
general alphabet and loss, online sequential prediction.",
abstract = "When applying aggregating strategies to Prediction with Expert
Advice, the learning rate must be adaptively tuned. The natural
choice of sqrt(complexity/current loss) renders the
analysis of Weighted Majority derivatives quite complicated. In
particular, for arbitrary weights there have been no results
proven so far. The analysis of the alternative ``Follow the
Perturbed Leader'' (FPL) algorithm from Kalai \& Vempala (2003) (based on
Hannan's algorithm) is easier. We derive loss bounds for adaptive
learning rate and both finite expert classes with uniform weights
and countable expert classes with arbitrary weights. For the
former setup, our loss bounds match the best known results so far,
while for the latter our results are new.",
znote = "Acceptance rate: 29/91 = 32\%",
}
@InProceedings{Hutter:04mdlspeed,
author = "Jan Poland and Marcus Hutter",
title = "On the convergence speed of {MDL} predictions for {B}ernoulli sequences",
booktitle = "Proc. 15th International Conf. on Algorithmic Learning Theory ({ALT'04})",
address = "Padova",
series = "LNAI",
volume = "3244",
_editor = "S. Ben-David and J. Case and A. Maruoka",
publisher = "Springer, Berlin",
pages = "294--308",
year = "2004",
issn = "0302-9743",
isbn = "3-540-23356-3",
http = "http://www.hutter1.net/ai/mdlspeed.htm",
url = "http://arxiv.org/abs/cs.LG/0407039",
ftp = "http://www.idsia.ch/idsiareport/IDSIA-13-04.pdf",
keywords = "MDL, Minimum Description Length, Convergence Rate,
Prediction, Bernoulli, Discrete Model Class.",
abstract = "We consider the Minimum Description Length principle for online
sequence prediction. If the underlying model class is discrete,
then the total expected square loss is a particularly interesting
performance measure: (a) this quantity is bounded, implying
convergence with probability one, and (b) it additionally
specifies a `rate of convergence'. Generally, for MDL only
exponential loss bounds hold, as opposed to the linear bounds for
a Bayes mixture. We show that this is even the case if the model
class contains only Bernoulli distributions. We derive a new upper
bound on the prediction error for countable Bernoulli classes.
This implies a small bound (comparable to the one for Bayes
mixtures) for certain important model classes. The results apply
to many Machine Learning tasks including classification and
hypothesis testing. We provide arguments that our theorems
generalize to countable classes of i.i.d. models.",
znote = "Acceptance rate: 29/91 = 32\%",
}
TechReport{Hutter:04bayespea,
author = "Marcus Hutter",
title = "Online Prediction -- {B}ayes versus Experts",
institution = "http://www.idsia.ch/$_{^\sim}$marcus/ai/bayespea.htm",
month = jul,
pages = "4 pages",
year = "2004",
note = "Presented at the {\em EU PASCAL Workshop on
Learning Theoretic and Bayesian Inductive Principles (LTBIP-2004)}",
url = "http://www.hutter1.net/ai/bayespea.htm",
ps = "http://www.hutter1.net/ai/bayespea.ps",
pdf = "http://www.hutter1.net/ai/bayespea.pdf",
slides = "http://www.hutter1.net/ai/sbayespea.pdf",
keywords = "Bayesian sequence prediction;
Prediction with Expert Advice;
general weights, alphabet and loss.",
abstract = "We derive a very general regret bound in the framework of
prediction with expert advice, which challenges the best known
regret bound for Bayesian sequence prediction. Both bounds of the
form $\sqrt{\mbox{Loss}\times\mbox{complexity}}$ hold for any
bounded loss-function, any prediction and observation spaces,
arbitrary expert/environment classes and weights, and unknown
sequence length.",
}
@InProceedings{Hutter:04mdl2p,
author = "Jan Poland and Marcus Hutter",
title = "Convergence of Discrete {MDL} for Sequential Prediction",
booktitle = "Proc. 17th Annual Conf. on Learning Theory ({COLT'04})",
address = "Banff",
series = "LNAI",
volume = "3120",
_editor = "J. Shawe-Taylor and Y. Singer",
publisher = "Springer, Berlin",
pages = "300--314",
year = "2004",
isbn = "3-540-22282-0",
http = "http://www.hutter1.net/ai/mdl2p.htm",
url = "http://arxiv.org/abs/cs.LG/0404057",
ftp = "http://www.idsia.ch/idsiareport/IDSIA-03-04.pdf",
keywords = "Minimum Description Length, Sequence Prediction,
Convergence, Discrete Model Classes, Universal Induction,
Stabilization, Algorithmic Information Theory.",
abstract = "We study the properties of the Minimum Description Length principle for
sequence prediction, considering a two-part MDL estimator which is chosen from
a countable class of models. This applies in particular to the important case
of universal sequence prediction, where the model class corresponds to all
algorithms for some fixed universal Turing machine (this correspondence is by
enumerable semimeasures, hence the resulting models are stochastic). We prove
convergence theorems similar to Solomonoff's theorem of universal induction,
which also holds for general Bayes mixtures. The bound characterizing the
convergence speed for MDL predictions is exponentially larger as compared to
Bayes mixtures. We observe that there are at least three different ways of
using MDL for prediction. One of these has worse prediction properties, for
which predictions only converge if the MDL estimator stabilizes. We establish
sufficient conditions for this to occur. Finally, some immediate consequences
for complexity relations and randomness criteria are proven.",
znote = "Acceptance rate: 44/107 = 41\%",
}
@InProceedings{Hutter:04fussexp,
author = "Shane Legg and Marcus Hutter and Akshat Kumar",
title = "Tournament versus Fitness Uniform Selection",
booktitle = "Proc. 2004 Congress on Evolutionary Computation ({CEC'04})",
address = "Portland, OR",
xeditor = "??",
publisher = "IEEE",
ISBN = "0-7803-8515-2",
_month = jun,
year = "2004",
pages = "2144--2151",
keywords = "Selection schemes, fitness evaluation, optimization,
fitness landscapes, basic working principles of evolutionary computations,
(self)adaptation, evolutionary algorithm,
deceptive \& multimodal optimization problems.",
http = "http://www.hutter1.net/ai/fussexp.htm",
url = "http://arxiv.org/abs/cs.LG/0403038",
ftp = "http://www.idsia.ch/idsiareport/IDSIA-04-04.pdf",
doi = "10.1109/CEC.2004.1331162",
press = "http://www.trnmag.com/Stories/032801/Diversity_trumps_fitness_032801.html",
abstract = "In evolutionary algorithms a critical parameter that must be tuned is
that of selection pressure. If it is set too low then the rate of
convergence towards the optimum is likely to be slow. Alternatively
if the selection pressure is set too high the system is likely to
become stuck in a local optimum due to a loss of diversity in the
population. The recent Fitness Uniform Selection Scheme (FUSS) is a
conceptually simple but somewhat radical approach to addressing this
problem --- rather than biasing the selection towards higher fitness,
FUSS biases selection towards sparsely populated fitness levels. In
this paper we compare the relative performance of FUSS with the well
known tournament selection scheme on a range of problems.",
znote = "Acceptance rate: 300/460 = 65\%",
}
%-------------Publications-of-Marcus-Hutter-2003--------------%
@PhDThesis{Hutter:03habil,
author = "Marcus Hutter",
school = "Fakult{\"a}t f{\"u}r Informatik",
address = "TU M{\"u}nchen",
title = "Optimal Sequential Decisions based on Algorithmic Probability",
year = "2003",
pages = "1--288",
url = "http://www.hutter1.net/ai/habil.htm",
_url = "http://arxiv.org/abs/cs.AI/0306091",
xftp = "http://www.idsia.ch/idsiareport/IDSIA-16-03.ps.gz",
keywords = "Artificial intelligence; algorithmic probability;
sequential decision theory; Solomonoff induction;
Kolmogorov complexity; Bayes-mixture distributions;
reinforcement learning; universal sequence prediction;
tight loss and error bounds; Levin search;
strategic games; function minimization;
supervised learning.",
abstract = "Decision theory formally solves the problem of rational agents in
uncertain worlds if the true environmental prior probability
distribution is known. Solomonoff's theory of universal induction
formally solves the problem of sequence prediction for unknown
prior distribution. In this \thesis\ both ideas are unified to one
parameter-free theory for universal Artificial Intelligence. We
give strong arguments that the resulting AIXI model is the most
intelligent unbiased agent possible. We outline for a number of
problem classes, including sequence prediction, strategic games,
function minimization, reinforcement and supervised learning, how
the AIXI model can formally solve them. The major drawback of the
AIXI model is that it is uncomputable. To overcome this problem,
we construct a modified algorithm AIXI$tl$, which is still
effectively more intelligent than any other time $t$ and length $l$
bounded agent. The computation time of AIXI$tl$ is of the order
$t\cdot 2^l$. The discussion includes formal definitions of
intelligence order relations, the horizon problem and relations of
the AIXI theory to other AI approaches.",
note = "288 pages, draft, http://www.idsia.ch/$_{^\sim}$marcus/ai/habil.htm",
}
@InProceedings{Hutter:03unimdl,
author = "Marcus Hutter",
title = "Sequence Prediction based on Monotone Complexity",
booktitle = "Proc. 16th Annual Conf. on Learning Theory ({COLT'03})",
address = "Washington, DC",
series = "LNAI",
volume = "2777",
_editor = "B. Sch{\"o}lkopf and M. K. Warmuth",
publisher = "Springer, Berlin",
pages = "506--521",
year = "2003",
isbn = "3-540-40720-0",
http = "http://www.hutter1.net/ai/unimdl.htm",
url = "http://arxiv.org/abs/cs.AI/0306036",
ftp = "http://www.idsia.ch/idsiareport/IDSIA-09-03.ps.gz",
keywords = "Sequence prediction; Algorithmic Information Theory;
Solomonoff's prior; Monotone Kolmogorov Complexity;
Minimal Description Length; Convergence;
Self-Optimizingness",
abstract = "This paper studies sequence prediction based on the
monotone Kolmogorov complexity $\Km=-\lb m$, i.e.\ based on
universal MDL. $m$ is extremely close to Solomonoff's prior $M$,
the latter being an excellent predictor in deterministic as well
as probabilistic environments, where performance is measured in
terms of convergence of posteriors or losses. Despite this
closeness to $M$, it is difficult to assess the prediction quality
of $m$, since little is known about the closeness of their
posteriors, which are the important quantities for prediction.
We show that for deterministic computable environments, the
``posterior'' and losses of $m$ converge, but rapid convergence
could only be shown on-sequence; the off-sequence behavior is
unclear. In probabilistic environments, neither the posterior nor
the losses converge, in general.",
znote = "Acceptance rate: 49/92 = 53\%",
}
@InProceedings{Hutter:03unipriors,
author = "Marcus Hutter",
title = "On the Existence and Convergence of Computable Universal Priors",
booktitle = "Proc. 14th International Conf. on Algorithmic Learning Theory ({ALT'03})",
address = "Sapporo",
_editor = "Ricard Gavald{\'a} and Klaus P. Jantke and Eiji Takimoto",
series = "LNAI",
volume = "2842",
publisher = "Springer, Berlin",
pages = "298--312",
_month = sep,
year = "2003",
ISSN = "0302-9743",
isbn = "3-540-20291-9",
http = "http://www.hutter1.net/ai/uniprior.htm",
url = "http://arxiv.org/abs/cs.LG/0305052",
ftp = "http://www.idsia.ch/idsiareport/IDSIA-05-03.ps.gz",
keywords = "Sequence prediction; Algorithmic Information Theory;
Solomonoff's prior; universal probability;
mixture distributions; posterior convergence;
computability concepts; Martin-L{\"o}f randomness.",
abstract = "Solomonoff unified Occam's razor and Epicurus' principle
of multiple explanations to one elegant, formal, universal theory
of inductive inference, which initiated the field of algorithmic
information theory. His central result is that the posterior of
his universal semimeasure $M$ converges rapidly to the true
sequence generating posterior $\mu$, if the latter is computable.
Hence, $M$ is eligible as a universal predictor in case of unknown
$\mu$. We investigates the existence, computability and convergence of
universal (semi)measures for a hierarchy of computability classes:
finitely computable, estimable, (co)enumerable, and approximable.
For instance, $\MM(x)$ is known to be enumerable, but not finitely
computable, and to dominates all enumerable semimeasures.
We define seven classes of (semi)measures based on these four
computability concepts. Each class may or may not contain a
(semi)measures which dominates all elements of another class. The
analysis of these 49 cases can be reduced to four basic cases, two
of them being new. We present proofs for discrete and continuous
semimeasures.
We also investigate more closely the type of convergence, possibly
implied by universality (in difference and in ratio, with probability
1, in mean sum, and for Martin-L{\"o}f random sequences).",
znote = "Acceptance rate: 19/37 = 51\%?",
}
@InProceedings{Hutter:03mlconv,
author = "Marcus Hutter",
title = "An Open Problem Regarding the Convergence
of Universal A Priori Probability",
booktitle = "Proc. 16th Annual Conf. on Learning Theory ({COLT'03})",
address = "Washington, DC",
series = "LNAI",
volume = "2777",
_editor = "B. Sch{\"o}lkopf and M. K. Warmuth",
publisher = "Springer, Berlin",
pages = "738--740",
year = "2003",
isbn = "3-540-40720-0",
url = "http://www.hutter1.net/ai/mlconv.htm",
keywords = "Sequence prediction; Algorithmic Information Theory;
Solomonoff's prior; universal probability;
posterior convergence; Martin-L{\"o}f randomness.",
abstract = "Is the textbook result that Solomonoff's universal
posterior converges to the true posterior for all Martin-L{\"o}f
random sequences true?",
}
@Article{Hutter:03optisp,
author = "Marcus Hutter",
title = "Optimality of Universal {B}ayesian Prediction for General Loss and Alphabet",
_month = Nov,
volume = "4",
year = "2003",
pages = "971--1000",
journal = "Journal of Machine Learning Research",
publisher = "MIT Press",
http = "http://www.hutter1.net/ai/optisp.htm",
url = "http://arxiv.org/abs/cs.LG/0311014",
url2 = "http://www.jmlr.org/papers/volume4/hutter03a/",
url3 = "http://www.jmlr.org/papers/v4/hutter03a.html",
ftp = "http://www.idsia.ch/idsiareport/IDSIA-02-02.ps.gz",
keywords = "Bayesian sequence prediction; mixture distributions; Solomonoff
induction; Kolmogorov complexity; learning; universal probability;
tight loss and error bounds; Pareto-optimality; games of chance;
classification.",
abstract = "Various optimality properties of universal sequence predictors
based on Bayes-mixtures in general, and Solomonoff's prediction
scheme in particular, will be studied. The probability of
observing $x_t$ at time $t$, given past observations
$x_1...x_{t-1}$ can be computed with the chain rule if the true
generating distribution $\mu$ of the sequences $x_1x_2x_3...$ is
known. If $\mu$ is unknown, but known to belong to a countable or
continuous class $\M$ one can base ones prediction on the
Bayes-mixture $\xi$ defined as a $w_\nu$-weighted sum or integral
of distributions $\nu\in\M$. The cumulative expected loss of the
Bayes-optimal universal prediction scheme based on $\xi$ is shown
to be close to the loss of the Bayes-optimal, but infeasible
prediction scheme based on $\mu$. We show that the bounds are
tight and that no other predictor can lead to significantly
smaller bounds. Furthermore, for various performance measures, we
show Pareto-optimality of $\xi$ and give an Occam's razor argument
that the choice $w_\nu\sim 2^{-K(\nu)}$ for the weights is
optimal, where $K(\nu)$ is the length of the shortest program
describing $\nu$. The results are applied to games of chance,
defined as a sequence of bets, observations, and rewards. The
prediction schemes (and bounds) are compared to the popular
predictors based on expert advice. Extensions to infinite
alphabets, partial, delayed and probabilistic prediction,
classification, and more active systems are briefly discussed.",
znote = "Inofficial numbers: Acceptance rate: 27\%",
}
@InProceedings{Hutter:03idm,
author = "Marcus Hutter",
title = "Robust Estimators under the {I}mprecise {D}irichlet {M}odel",
booktitle = "Proc. 3rd International Symposium on
Imprecise Probabilities and Their Application ({ISIPTA-2003})",
_editor = "Jean-Marc Bernard and Teddy Seidenfeld and Marco Zaffalon",
publisher = "Carleton Scientific",
series = "Proceedings in Informatics",
volume = "18",
address = "Canada",
year = "2003",
pages = "274--289",
isbn = "1-894145-17-8",
http = "http://www.hutter1.net/ai/idm.htm",
url = "http://arxiv.org/abs/math.PR/0305121",
ftp = "http://www.idsia.ch/idsiareport/IDSIA-03-03.ps.gz",
keywords = "Imprecise Dirichlet Model; exact, conservative, approximate,
robust, confidence interval estimates; entropy; mutual information.",
abstract = "Walley's Imprecise Dirichlet Model (IDM) for categorical data
overcomes several fundamental problems which other approaches to
uncertainty suffer from. Yet, to be useful in practice, one needs
efficient ways for computing the imprecise=robust sets or
intervals. The main objective of this work is to derive exact,
conservative, and approximate, robust and credible interval
estimates under the IDM for a large class of statistical
estimators, including the entropy and mutual information.",
znote = "Inofficial numbers: Acceptance rate: 44/55 = 80\% ?",
}
@InProceedings{Hutter:03mimiss,
author = "Marcus Hutter and Marco Zaffalon",
title = "Bayesian Treatment of Incomplete Discrete Data applied
to Mutual Information and Feature Selection",
_month = sep,
year = "2003",
pages = "396--406",
series = "LNAI",
volume = "2821",
booktitle = "Proc. 26th German Conf. on Artificial Intelligence (KI-2003)",
_editor = "A. G{\"u}nter, R. Kruse and B. Neumann",
publisher = "Springer, Berlin",
issn = "0302-9743",
isbn = "3-540-00168-9",
http = "http://www.hutter1.net/ai/mimiss.htm",
url = "http://arxiv.org/abs/cs.LG/0306126",
ftp = "http://www.idsia.ch/idsiareport/IDSIA-15-03.ps.gz",
keywords = "Incomplete data, Bayesian statistics, expectation maximization,
global optimization, Mutual Information, Cross Entropy, Dirichlet
distribution, Second order distribution, Credible intervals,
expectation and variance of mutual information, missing data,
Robust feature selection, Filter approach, naive Bayes classifier.",
abstract = "Given the joint chances of a pair of random variables one can
compute quantities of interest, like the mutual information. The
Bayesian treatment of unknown chances involves computing, from a
second order prior distribution and the data likelihood, a
posterior distribution of the chances. A common treatment of
incomplete data is to assume ignorability and determine the
chances by the expectation maximization (EM) algorithm. The two
different methods above are well established but typically
separated. This paper joins the two approaches in the case of
Dirichlet priors, and derives efficient approximations for the
mean, mode and the (co)variance of the chances and the mutual
information. Furthermore, we prove the unimodality of the
posterior distribution, whence the important property of
convergence of EM to the global maximum in the chosen framework.
These results are applied to the problem of selecting features for
incremental learning and naive Bayes classification. A fast filter
based on the distribution of mutual information is shown to
outperform the traditional filter based on empirical mutual
information on a number of incomplete real data sets.",
znote = "Acceptance rate: 42/90 = 46\%",
}
@Article{Hutter:03spupper,
author = "Marcus Hutter",
title = "Convergence and Loss Bounds for {Bayesian} Sequence Prediction",
_month = aug,
volume = "49",
number = "8",
year = "2003",
pages = "2061--2067",
address = "Manno(Lugano), CH",
journal = "IEEE Transactions on Information Theory",
issn = "0018-9448",
http = "http://www.hutter1.net/ai/spupper.htm",
url = "http://arxiv.org/abs/cs.LG/0301014",
ftp = "http://www.idsia.ch/idsiareport/IDSIA-09-01.ps.gz",
keywords = "Bayesian sequence prediction;
general loss function and bounds;
convergence; mixture distributions.",
abstract = "The probability of observing $x_t$ at time $t$, given past
observations $x_1...x_{t-1}$ can be computed with Bayes rule if
the true generating distribution $\mu$ of the sequences
$x_1x_2x_3...$ is known. If $\mu$ is unknown, but known to belong
to a class $M$ one can base ones prediction on the Bayes mix
$\xi$ defined as a weighted sum of distributions $\nu\in M$.
Various convergence results of the mixture posterior $\xi_t$ to
the true posterior $\mu_t$ are presented. In particular a new
(elementary) derivation of the convergence $\xi_t/\mu_t\to 1$ is
provided, which additionally gives the rate of convergence. A
general sequence predictor is allowed to choose an action $y_t$
based on $x_1...x_{t-1}$ and receives loss $\ell_{x_t y_t}$ if
$x_t$ is the next symbol of the sequence. No assumptions are made
on the structure of $\ell$ (apart from being bounded) and $M$.
The Bayes-optimal prediction scheme $\Lambda_\xi$ based on mixture
$\xi$ and the Bayes-optimal informed prediction scheme
$\Lambda_\mu$ are defined and the total loss $L_\xi$ of
$\Lambda_\xi$ is bounded in terms of the total loss $L_\mu$ of
$\Lambda_\mu$. It is shown that $L_\xi$ is bounded for bounded
$L_\mu$ and $L_\xi/L_\mu\to 1$ for $L_\mu\to \infty$. Convergence
of the instantaneous losses is also proven.",
}
%-------------Publications-of-Marcus-Hutter-2002--------------%
@Article{Hutter:02ulaos,
author = "J{\"u}rgen Schmidhuber and Marcus Hutter",
title = "Universal Learning Algorithms and Optimal Search",
journal = "NIPS 2001 Workshop",
volume = "",
pages = "",
year = "2002",
note = "http://www.idsia.ch/$_{^\sim}$marcus\linebreak[1]/idsia/nipsws.htm",
}
@InProceedings{Hutter:02feature,
author = "Marco Zaffalon and Marcus Hutter",
title = "Robust Feature Selection by Mutual Information Distributions",
_month = jun,
year = "2002",
pages = "577--584",
booktitle = "Proc. 18th International Conf. on
Uncertainty in Artificial Intelligence (UAI-2002)",
_editor = "A. Darwiche and N. Friedman",
publisher = "Morgan Kaufmann, San Francisco, CA",
http = "http://www.hutter1.net/ai/feature.htm",
url = "http://arxiv.org/abs/cs.AI/0206006",
ftp = "http://www.idsia.ch/idsiareport/IDSIA-08-02.ps.gz",
categories = "I.2. [Artificial Intelligence]",
keywords = "Robust feature selection, Filter approach, naive Bayes classifier,
Mutual Information, Cross Entropy, Dirichlet distribution, Second
order distribution, Bayesian statistics, Credible intervals,
expectation and variance of mutual information, missing data.",
abstract = "Mutual information is widely used in artificial intelligence, in a
descriptive way, to measure the stochastic dependence of discrete random
variables. In order to address questions such as the reliability of the
empirical value, one must consider sample-to-population inferential
approaches. This paper deals with the distribution of mutual information, as
obtained in a Bayesian framework by a second-order Dirichlet prior
distribution. The exact analytical expression for the mean and an
analytical approximation of the variance are reported. Asymptotic
approximations of the distribution are proposed. The results are applied to
the problem of selecting features for incremental learning and
classification of the naive Bayes classifier. A fast, newly defined method
is shown to outperform the traditional approach based on empirical mutual
information on a number of real data sets. Finally, a theoretical
development is reported that allows one to efficiently extend the above
methods to incomplete samples in an easy and effective way.",
znote = "Acceptance rate: 66/192 = 34\%",
}
@InProceedings{Hutter:02selfopt,
author = "Marcus Hutter",
title = "Self-Optimizing and {P}areto-Optimal Policies in
General Environments based on {B}ayes-Mixtures",
_month = jul,
series = "LNAI",
volume = "2375",
year = "2002",
pages = "364--379",
address = "Sydney",
booktitle = "Proc. 15th Annual Conf. on Computational
Learning Theory ({COLT'02})",
_editor = "J. Kivinen and R. H. Sloan",
publisher = "Springer, Berlin",
http = "http://www.hutter1.net/ai/selfopt.htm",
url = "http://arxiv.org/abs/cs.AI/0204040",
ftp = "http://www.idsia.ch/idsiareport/IDSIA-04-02.ps.gz",
keywords = "Rational agents, sequential decision theory,
reinforcement learning, value function, Bayes mixtures,
self-optimizing policies, Pareto-optimality,
unbounded effective horizon, (non) Markov decision
processes.",
abstract = "The problem of making sequential decisions in unknown
probabilistic environments is studied. In cycle $t$ action $y_t$
results in perception $x_t$ and reward $r_t$, where all quantities
in general may depend on the complete history. The perception
$x_t'$ and reward $r_t$ are sampled from the (reactive)
environmental probability distribution $\mu$. This very general
setting includes, but is not limited to, (partial observable, k-th
order) Markov decision processes. Sequential decision theory tells
us how to act in order to maximize the total expected reward,
called value, if $\mu$ is known. Reinforcement learning is usually
used if $\mu$ is unknown. In the Bayesian approach one defines a
mixture distribution $\xi$ as a weighted sum of distributions
$\nu\in\M$, where $\M$ is any class of distributions including the
true environment $\mu$. We show that the Bayes-optimal policy
$p^\xi$ based on the mixture $\xi$ is self-optimizing in the sense
that the average value converges asymptotically for all $\mu\in\M$
to the optimal value achieved by the (infeasible) Bayes-optimal
policy $p^\mu$ which knows $\mu$ in advance. We show that the
necessary condition that $\M$ admits self-optimizing policies at
all, is also sufficient. No other structural assumptions are made
on $\M$. As an example application, we discuss ergodic Markov
decision processes, which allow for self-optimizing policies.
Furthermore, we show that $p^\xi$ is Pareto-optimal in the sense
that there is no other policy yielding higher or equal value in
{\em all} environments $\nu\in\M$ and a strictly higher value in
at least one.",
znote = "Acceptance rate: 26/55 = 47\%",
}
@InProceedings{Hutter:01xentropy,
author = "Marcus Hutter",
title = "Distribution of Mutual Information",
_month = dec,
booktitle = "Advances in Neural Information Processing Systems 14",
_editor = "T. G. Dietterich and S. Becker and Z. Ghahramani",
publisher = "MIT Press",
address = "Cambridge, MA",
pages = "399--406",
year = "2002",
http = "http://www.hutter1.net/ai/xentropy.htm",
url = "http://arxiv.org/abs/cs.AI/0112019",
ftp = "http://www.idsia.ch/idsiareport/IDSIA-13-01.ps.gz",
categories = "I.2. [Artificial Intelligence]",
keywords = "Mutual Information, Cross Entropy, Dirichlet distribution, Second
order distribution, expectation and variance of mutual
information.",
abstract = "The mutual information of two random variables i and j with joint
probabilities t_ij is commonly used in learning Bayesian nets as
well as in many other fields. The chances t_ij are usually
estimated by the empirical sampling frequency n_ij/n leading to a
point estimate I(n_ij/n) for the mutual information. To answer
questions like ``is I(n_ij/n) consistent with zero?'' or ``what is
the probability that the true mutual information is much larger
than the point estimate?'' one has to go beyond the point estimate.
In the Bayesian framework one can answer these questions by
utilizing a (second order) prior distribution p(t) comprising
prior information about t. From the prior p(t) one can compute the
posterior p(t|n), from which the distribution p(I|n) of the mutual
information can be calculated. We derive reliable and quickly
computable approximations for p(I|n). We concentrate on the mean,
variance, skewness, and kurtosis, and non-informative priors. For
the mean we also give an exact expression. Numerical issues and
the range of validity are discussed.",
znote = "Acceptance rate: 196/660 = 30\%",
}
@InProceedings{Hutter:02fuss,
author = "Marcus Hutter",
title = "Fitness Uniform Selection to Preserve Genetic Diversity",
booktitle = "Proc. 2002 Congress on Evolutionary Computation (CEC-2002)",
address = "Honolulu, HI",
publisher = "IEEE",
ISSN = "1098-7576",
_month = may,
year = "2002",
pages = "783--788",
keywords = "Evolutionary algorithms, fitness uniform selection strategy,
preserve diversity, local optima, evolution,
correlated recombination, crossover.",
http = "http://www.hutter1.net/ai/pfuss.htm",
url = "http://arxiv.org/abs/cs.AI/0103015",
ftp = "http://www.idsia.ch/idsiareport/IDSIA-01-01.ps.gz",
abstract = "In evolutionary algorithms, the fitness of a population increases
with time by mutating and recombining individuals and by a biased
selection of more fit individuals. The right selection pressure is
critical in ensuring sufficient optimization progress on the one
hand and in preserving genetic diversity to be able to escape from
local optima on the other. We propose a new selection scheme,
which is uniform in the fitness values. It generates selection
pressure towards sparsely populated fitness regions, not
necessarily towards higher fitness, as is the case for all other
selection schemes. We show that the new selection scheme can be
much more effective than standard selection schemes.",
znote = "Acceptance rate: 264/372 = 71\%",
}
@Article{Hutter:02fast,
author = "Marcus Hutter",
title = "The Fastest and Shortest Algorithm for All Well-Defined Problems",
journal = "International Journal of Foundations of Computer Science",
publisher = "World Scientific",
volume = "13",
number = "3",
pages = "431--443",
year = "2002",
keywords = "Acceleration, Computational Complexity,
Algorithmic Information Theory, Kolmogorov Complexity, Blum's
Speed-up Theorem, Levin Search.",
http = "http://www.hutter1.net/ai/pfastprg.htm",
url = "http://arxiv.org/abs/cs.CC/0206022",
ftp = "http://www.idsia.ch/idsiareport/IDSIA-16-00.ps.gz",
abstract = "An algorithm M is described that solves any well-defined problem
p as quickly as the fastest algorithm computing a solution to
p, save for a factor of 5 and low-order additive terms. M
optimally distributes resources between the execution of provably
correct p-solving programs and an enumeration of all proofs,
including relevant proofs of program correctness and of time
bounds on program runtimes. M avoids Blum's speed-up theorem by
ignoring programs without correctness proof. M has broader
applicability and can be faster than Levin's universal search, the
fastest method for inverting functions save for a large
multiplicative constant. An extension of Kolmogorov complexity and
two novel natural measures of function complexity are used to show
that the most efficient program computing some function f is
also among the shortest programs provably computing f.",
press = "http://guide.supereva.it/c_/interventi/2001/04/38469.shtml",
}
@Article{Hutter:02uspatent,
author = "Marcus Hutter",
title = "System and method for analysing and displaying two- or three-dimensional sets of data",
volume = "number US2002041701, pages 1--15",
journal = "{\rm BrainLAB}, US patent",
year = "2002",
url = "http://l2.espacenet.com/espacenet/bnsviewer?CY=ep&LG=en&DB=EPD&PN=US2002041701&ID=US2002041701A1+I+",
}
%-------------Publications-of-Marcus-Hutter-2001--------------%
@Article{Hutter:01eupatent,
author = "Marcus Hutter",
title = "{S}tufenfreie {D}arstellung von zwei- oder dreidimensionalen Datens{\"a}tzen durch kr{\"u}mmungsminimierende {V}erschiebung von {P}ixelwerten",
volume = "number EP1184812, pages 1--19",
journal = "{\rm BrainLAB}, EU patent",
year = "2001",
url = "http://l2.espacenet.com/espacenet/bnsviewer?CY=ep&LG=en&DB=EPD&PN=EP1184812&ID=EP+++1184812A1+I+",
}
@InProceedings{Hutter:01market,
author = "Ivo Kwee and Marcus Hutter and J{\"u}rgen Schmidhuber",
title = "Market-Based Reinforcement Learning in Partially Observable Worlds",
address = "Vienna",
_month = aug,
year = "2001",
pages = "865--873",
booktitle = "Proc. International Conf. on Artificial Neural Networks (ICANN-2001)",
_journal = "Artificial Neural Networks (ICANN-2001)",
_editor = "Georg Dorffner and Horst Bishof and Kurt Hornik",
publisher = "Springer, Berlin",
series = "LNCS",
volume = "2130",
http = "http://www.hutter1.net/ai/pmarket.htm",
url = "http://arxiv.org/abs/cs.AI/0105025",
ftp = "http://www.idsia.ch/idsiareport/IDSIA-10-01.ps.gz",
categories = "I.2. [Artificial Intelligence]",
keywords = "Hayek system; reinforcement learning; partial observable environment",
abstract = "Unlike traditional reinforcement learning (RL), market-based
RL is in principle applicable to worlds described by partially
observable Markov Decision Processes (POMDPs), where an agent needs
to learn short-term memories of relevant previous events in order to
execute optimal actions. Most previous work, however, has focused
on reactive settings (MDPs) instead of POMDPs. Here we reimplement
a recent approach to market-based RL and for the first time evaluate
it in a toy POMDP setting.",
znote = "Acceptance rate: 171/300 = 57\%",
}
@InProceedings{Hutter:01loss,
author = "Marcus Hutter",
title = "General Loss Bounds for Universal Sequence Prediction",
year = "2001",
pages = "210--217",
booktitle = "Proc. 18th International Conf. on Machine Learning (ICML-2001)",
address = "Williamstown, MA",
_editor = "Carla. E. Brodley and Andrea Pohoreckyj Danyluk",
publisher = "Morgan Kaufmann",
ISBN = "1-55860-778-1",
ISSN = "1049-1910",
http = "http://www.hutter1.net/ai/ploss.htm",
url = "http://arxiv.org/abs/cs.AI/0101019",
ftp = "http://www.idsia.ch/idsiareport/IDSIA-03-01.ps.gz",
categories = "I.2. [Artificial Intelligence],
I.2.6. [Learning],
I.2.8. [Problem Solving, Control Methods and Search],
F.1.3. [Complexity Classes].",
keywords = "Bayesian and deterministic prediction; general loss function;
Solomonoff induction; Kolmogorov complexity; leaning; universal
probability; loss bounds; games of chance; partial and delayed
prediction; classification.",
abstract = "The Bayesian framework is ideally suited for induction problems.
The probability of observing $x_k$ at time $k$, given past
observations $x_1...x_{k-1}$ can be computed with Bayes rule if
the true distribution $\mu$ of the sequences $x_1x_2x_3...$ is
known. The problem, however, is that in many cases one does not
even have a reasonable estimate of the true distribution. In order
to overcome this problem a universal distribution $\xi$ is defined
as a weighted sum of distributions $\mu_i\in M$, where $M$ is
any countable set of distributions including $\mu$. This is a
generalization of Solomonoff induction, in which $M$ is the set of
all enumerable semi-measures. Systems which predict $y_k$, given
$x_1...x_{k-1}$ and which receive loss $l_{x_k y_k}$ if $x_k$ is
the true next symbol of the sequence are considered. It is proven
that using the universal $\xi$ as a prior is nearly as good as
using the unknown true distribution $\mu$. Furthermore, games of
chance, defined as a sequence of bets, observations, and rewards
are studied. The time needed to reach the winning zone is
estimated. Extensions to arbitrary alphabets, partial and delayed
prediction, and more active systems are discussed.",
znote = "Acceptance rate: 80/249 = 32\%",
}
@InProceedings{Hutter:01alpha,
author = "Marcus Hutter",
title = "Convergence and Error bounds for Universal Prediction of Nonbinary Sequences",
booktitle = "Proc. 12th European Conf. on Machine Learning (ECML-2001)",
address = "Freiburg",
_editor = "Luc De Raedt and Peter Flach",
publisher = "Springer, Berlin",
series = "LNAI",
volume = "2167",
ISBN = "3-540-42536-5",
_month = dec,
year = "2001",
pages = "239--250",
ftp = "http://www.idsia.ch/idsiareport/IDSIA-07-01.ps.gz",
http = "http://www.hutter1.net/ai/palpha.htm",
url = "http://arxiv.org/abs/cs.LG/0106036",
keywords = "Induction; Solomonoff, Bayesian, deterministic
prediction; Kolmogorov complexity; leaning; Loss function;
algorithmic information theory; universal probability",
abstract = "Solomonoff's uncomputable universal prediction scheme $\xi$ allows
to predict the next symbol $x_k$ of a sequence $x_1...x_{k-1}$ for
any Turing computable, but otherwise unknown, probabilistic
environment $\mu$. This scheme will be generalized to arbitrary
environmental classes, which, among others, allows the
construction of computable universal prediction schemes $\xi$.
Convergence of $\xi$ to $\mu$ in a conditional mean squared sense
and with $\mu$ probability $1$ is proven. It is shown that the
average number of prediction errors made by the universal $\xi$
scheme rapidly converges to those made by the best possible
informed $\mu$ scheme. The schemes, theorems and proofs are given
for general finite alphabet, which results in additional
complications as compared to the binary case.
Several extensions of the presented theory and
results are outlined. They include general loss functions and
bounds, games of chance, infinite alphabet, partial and delayed
prediction, classification, and more active
systems.",
znote = "Acceptance rate: 90/240 = 37\% (includes PKDD)",
}
@InProceedings{Hutter:01grep,
author = "Ivo Kwee and Marcus Hutter and J{\"u}rgen Schmidhuber",
title = "Gradient-based Reinforcement Planning in Policy-Search Methods",
year = "2001",
pages = "27--29",
booktitle = "Proc. 5th European Workshop on Reinforcement Learning (EWRL-5)",
volume = "27",
_editor = "Marco A. Wiering",
publisher = "Onderwijsinsituut CKI, Utrecht Univ.",
_series = "Cognitieve Kunstmatige Intelligentie",
ISBN = "90-393-2874-9",
ISSN = "1389-5184",
keywords = "Artificial intelligence, reinforcement learning, direct policy search,
planning, gradient decent.",
http = "http://www.hutter1.net/ai/pgrep.htm",
url = "http://arxiv.org/abs/cs.AI/0111060",
ftp = "http://www.idsia.ch/idsiareport/IDSIA-14-01.ps.gz",
categories = "I.2. [Artificial Intelligence],
I.2.6. [Learning],
I.2.8. [Problem Solving, Control Methods and Search]",
abstract = "We introduce a learning method called ``gradient-based reinforcement
planning'' (GREP). Unlike traditional DP methods that improve their
policy backwards in time, GREP is a gradient-based method that plans
ahead and improves its policy {\em before} it actually acts in the
environment. We derive formulas for the exact policy gradient that
maximizes the expected future reward and confirm our ideas
with numerical experiments.",
}
@InProceedings{Hutter:01decision,
author = "Marcus Hutter",
title = "Universal Sequential Decisions in Unknown Environments",
year = "2001",
pages = "25--26",
booktitle = "Proc. 5th European Workshop on Reinforcement Learning (EWRL-5)",
volume = "27",
_editor = "Marco A. Wiering",
publisher = "Onderwijsinsituut CKI, Utrecht Univ.",
_series = "Cognitieve Kunstmatige Intelligentie",
ISBN = "90-393-2874-9",
ISSN = "1389-5184",
keywords = "Artificial intelligence, Rational agents,
sequential decision theory, universal Solomonoff induction,
algorithmic probability, reinforcement learning, computational
complexity, Kolmogorov complexity.",
url = "http://www.hutter1.net/ai/pdecision.htm",
categories = "I.2. [Artificial Intelligence],
I.2.6. [Learning],
I.2.8. [Problem Solving, Control Methods and Search],
F.1.3. [Complexity Classes],
F.2. [Analysis of Algorithms and Problem Complexity]",
abstract = "We give a brief introduction to the AIXI model, which unifies and
overcomes the limitations of sequential decision theory and
universal Solomonoff induction. While the former theory is suited
for active agents in known environments, the latter is suited for
passive prediction of unknown environments.",
abstract2 = "Decision theory formally solves the problem of rational agents in
uncertain worlds if the true environmental probability
distribution is known. Solomonoff's theory of universal induction
formally solves the problem of sequence prediction for unknown
distribution. We unify both theories and give strong arguments
that the resulting universal AIXI model behaves optimal in any
computable environment.",
}
@InProceedings{Hutter:01aixi,
author = "Marcus Hutter",
title = "Towards a Universal Theory of Artificial Intelligence based on Algorithmic
Probability and Sequential Decisions",
year = "2001",
pages = "226--238",
booktitle = "Proc. 12th European Conf. on
Machine Learning (ECML-2001)",
address = "Freiburg",
_editor = "Luc De Raedt and Peter Flach",
publisher = "Springer, Berlin",
series = "LNAI",
volume = "2167",
ISBN = "3-540-42536-5",
keywords = "Artificial intelligence, Rational agents,
sequential decision theory, universal Solomonoff induction,
algorithmic probability, reinforcement learning, computational
complexity, theorem proving, probabilistic reasoning, Kolmogorov
complexity, Levin search.",
http = "http://www.hutter1.net/ai/paixi.htm",
url = "http://arxiv.org/abs/cs.AI/0012011",
ftp = "http://www.idsia.ch/idsiareport/IDSIA-14-00.ps.gz",
categories = "I.2. [Artificial Intelligence],
I.2.3. [Deduction and Theorem Proving],
I.2.6. [Learning],
I.2.8. [Problem Solving, Control Methods and Search],
F.1.3. [Complexity Classes],
F.2. [Analysis of Algorithms and Problem Complexity]",
abstract = "Decision theory formally solves the problem of rational agents in
uncertain worlds if the true environmental probability
distribution is known. Solomonoff's theory of universal induction
formally solves the problem of sequence prediction for unknown
distribution. We unify both theories and give strong arguments
that the resulting universal AIXI model behaves optimally in any
computable environment. The major drawback of the AIXI model is
that it is uncomputable. To overcome this problem, we construct a
modified algorithm AIXI^tl, which is still superior to any
other time t and space l bounded agent. The computation time
of AIXI^tl is of the order t x 2^l.",
znote = "Acceptance rate: 90/240 = 37\% (includes PKDD)",
}
@Article{Hutter:01errbnd,
author = "Marcus Hutter",
title = "New Error Bounds for {Solomonoff} Prediction",
year = "2001",
volume = "62",
number = "4",
pages = "653--667",
journal = "Journal of Computer and System Sciences",
address = "Manno(Lugano), CH",
keywords = "Kolmogorov Complexity, Solomonoff Prediction, Error
Bound, Induction, Learning, Algorithmic Information
Theory, Bayes",
http = "http://www.hutter1.net/ai/perrbnd.htm",
url = "http://arxiv.org/abs/cs.AI/9912008",
ftp = "http://www.idsia.ch/idsiareport/IDSIA-11-00.ps.gz",
abstract = "Several new relations between Solomonoff prediction
and Bayesian prediction and general probabilistic
prediction schemes will be proved. Among others they
show that the number of errors in Solomonoff prediction
is finite for computable prior probability, if finite
in the Bayesian case. Deterministic variants will also
be studied. The most interesting result is that the
deterministic variant of Solomonoff prediction is
optimal compared to any other probabilistic or
deterministic prediction scheme apart from additive
square root corrections only. This makes it well suited
even for difficult prediction problems, where it does
not suffice when the number of errors is minimal to
within some factor greater than one. Solomonoff's
original bound and the ones presented here complement
each other in a useful way.",
}
%-------------Publications-of-Marcus-Hutter-2000--------------%
@Article{Hutter:00speed,
author = "Marcus Hutter",
title = "An effective Procedure for Speeding up Algorithms",
year = "10 pages, 2001",
journal = "Presented at the 3rd Workshop on Algorithmic
Information Theory (TAI-2001)",
keywords = "Acceleration, Computational Complexity,
Algorithmic Information Theory, Blum's Speed-up, Levin Search.",
http = "http://www.hutter1.net/ai/pspeed.htm",
url = "http://arxiv.org/abs/cs.CC/0102018",
ftp = "http://www.idsia.ch/idsiareport/IDSIA-16-00-v1.ps.gz",
abstract = "The provably asymptotically fastest algorithm within a factor of 5
for formally described problems will be constructed. The main idea
is to enumerate all programs provably equivalent to the original
problem by enumerating all proofs. The algorithm could be
interpreted as a generalization and improvement of Levin search,
which is, within a multiplicative constant, the fastest algorithm
for inverting functions. Blum's speed-up theorem is avoided by
taking into account only programs for which a correctness proof
exists. Furthermore, it is shown that the fastest program that
computes a certain function is also one of the shortest programs
provably computing this function. To quantify this statement, the
definition of Kolmogorov complexity is extended, and two new
natural measures for the complexity of a function are defined.",
}
@TechReport{Hutter:00kcunai,
author = "Marcus Hutter",
title = "A Theory of Universal Artificial Intelligence based on Algorithmic Complexity",
number = "cs.AI/0004001",
month = apr,
year = "2000",
institution = "M{\"u}nchen, 62 pages",
keywords = "Artificial intelligence, algorithmic complexity,
sequential decision theory; induction; Solomonoff; Kolmogorov;
Bayes; reinforcement learning; universal sequence prediction;
strategic games; function minimization; supervised learning.",
url = "http://arxiv.org/abs/cs.AI/0004001",
http = "http://www.hutter1.net/ai/pkcunai.htm",
abstract = "Decision theory formally solves the problem of rational agents in
uncertain worlds if the true environmental prior probability
distribution is known. Solomonoff's theory of universal induction
formally solves the problem of sequence prediction for unknown
prior distribution. We combine both ideas and get a parameterless
theory of universal Artificial Intelligence. We give strong
arguments that the resulting AIXI model is the most intelligent
unbiased agent possible. We outline for a number of problem
classes, including sequence prediction, strategic games, function
minimization, reinforcement and supervised learning, how the
AIXI model can formally solve them. The major drawback of the
AIXI model is that it is uncomputable. To overcome this
problem, we construct a modified algorithm AIXI-tl, which is
still effectively more intelligent than any other time t and
space l bounded agent. The computation time of AIXI-tl
is of the order tx2^l. Other discussed topics are formal
definitions of intelligence order relations, the horizon problem
and relations of the AIXI theory to other AI approaches.",
note = "http://arxiv.org/abs/cs.AI/0004001",
}
%----------Publications-of-Marcus-Hutter-1987-1999------------%
@Article{Hutter:97instanto,
author = "Marcus Hutter",
title = "Instantons and Meson Correlators in {QCD}",
year = "1997",
pages = "131--143",
journal = "Zeitschrift f{\"u}r Physik",
volume = "C74",
url = "http://arxiv.org/abs/hep-ph/9501245",
http = "http://www.hutter1.net/physics/pinstant.htm",
abstract = "Various QCD correlators are calculated in the instanton liquid model
in zeromode approximation and $1/N_c$ expansion. Previous works are
extended by including dynamical quark loops. In contrast to the
original ``perturbative'' $1/N_c$ expansion not all quark loops are
suppressed. In the flavor singlet meson correlators a chain of quark
bubbles survives the $N_c\to\infty$ limit causing a massive
$\eta^\prime$ in the pseudoscalar correlator while keeping massless
pions in the triplet correlator. The correlators are plotted and
meson masses and couplings are obtained from a spectral fit. They
are compared to the values obtained from numerical studies of the
instanton liquid and to experimental results.",
}
@Article{Hutter:97family,
author = "Andreas Blumhofer and Marcus Hutter",
title = "Family Structure from Periodic Solutions of an Improved Gap Equation",
journal = "Nuclear Physics",
volume = "B484",
year = "1997",
pages = "80--96",
url = "http://arxiv.org/abs/hep-ph/9605393",
http = "http://www.hutter1.net/physics/pfamily.htm",
abstract = "Fermion mass models usually contain a horizontal symmetry and
therefore fail to predict the exponential mass spectrum of the Standard
Model in a natural way. In dynamical symmetry breaking there are
different concepts to introduce a fermion mass spectrum, which
automatically has the desired hierarchy. In constructing a specific
model we show that in some modified gap equations periodic solutions
with several fermion poles appear. The stability of these excitations
and the application of this toy model are discussed. The mass ratios
turn out to be approximately e^pi and e^2pi. Thus the model explains
the large ratios of fermion masses between successive generations in
the Standard Model without introducing large or small numbers by hand.",
note = "Missing figures in B494 (1997) 485",
}
@PhdThesis{Hutter:96thesis,
author = "Marcus Hutter",
school = "Faculty for Theoretical Physics, LMU Munich",
title = "Instantons in QCD: Theory and application of the instanton liquid model",
year = "1996",
pages = "1--100",
url = "http://arxiv.org/abs/hep-ph/0107098 ",
http = "http://www.hutter1.net/physics/pdise.htm",
abstract = "Numerical and analytical studies of the instanton liquid model have
allowed the determination of many hadronic parameters during the
last 13 years. Most part of this thesis is devoted to the extension
of the analytical methods. The meson correlation (polarization)
functions are calculated in the instanton liquid model including
dynamical quark loops. The correlators are plotted and masses and
couplings of the sigma, rho, omega, a1 and f1 are obtained from a
spectral fit. A separated analysis allows the determination of the
eta' mass too. The results agree with the experimental values on
a 10% level. Further I give some predictions for the proton form
factors, which are related to the proton spin (problem). A gauge
invariant gluon mass for small momenta is also calculated. At the
end of the work some predictions are given, which do not rely on
the instanton liquid model. A gauge invariant quark propagator is
calculated in the one instanton background and is compared to the
regular and singular propagator. An introduction to the skill of
choosing a suitable gauge, especially a criterion for choosing regular
or singular gauge, is given. An application is the derivation of a
finite relation between the quark condensate and the QCD scale Lambda,
where neither an infrared cutoff nor a specific instanton model has
been used. In general the instanton liquid model exhibits an astonishing
internal consistency and a good agreement with the experimental data.",
note = "Translated from the German original http://www.hutter1.net/physics/pdiss.htm",
}
@PhdThesis{Hutter:96diss,
author = "Marcus Hutter",
school = "Fakult{\"a}t f{\"u}r Theoretische Physik, LMU M{\"u}nchen",
title = "Instantonen in der QCD: Theorie und Anwendungen des Instanton-Fl{\"u}ssigkeit-Modells",
year = "1996",
pages = "1--105",
url = "http://arxiv.org/abs/hep-ph/9603280",
http = "http://www.hutter1.net/physics/pdiss.htm",
abstract = "Durch numerische Simulation des Instanton-Flüssigkeit-Modells
konnten eine Reihe hadronischer Größen in den letzten 13 Jahren
bestimmt werden. Der größte Teil dieser Arbeit ist der Erweiterung
der analytischen Methoden gewidmet. Die Meson-Korrelatoren
(auch Polarisations-Funktionen genannt) werden im Instanton-Flüssigkeits-Modell
berechnet, wobei dynamische Quark-Schleifen berücksichtigt werden.
Die Korrelatoren werden grafisch dargestellt und die Massen und Kopplungen
der sigma, rho, omega, a1 und f1 Mesonen werden mit Hilfe eines spektralen
Fits bestimmt. Eine gesonderte Betrachtung ermöglicht auch die Berechnung
der eta' Masse. Die Ergebnisse stimmen auf 10% Niveau mit den experimentellen
Werten überein. Weiterhin wird versucht, die axialen Formfaktoren des Protons
zu bestimmen. Diese stehen in Zusammenhang mit dem Proton-Spin(-Problem).
Eine eichinvariante Gluon-Masse wird für kleine Impulse berechnet.
Die Arbeit wird abgeschlossen mit einigen Vorhersagen, die sich nicht
speziell auf das Instanton-Flüssigkeits-Modell stützen. Im
ein-Instanton-Vakuum wird ein eichinvarianter Quark-Propagator berechnet
und mit dem regulüren und dem singulären Propagator verglichen.
Kriterien für die Wahl einer geeignete Eichung, insbesondere für die
Wahl der singulären oder der regulüren Eichung, werden gegeben.
Eine Anwendung ist die Herleitung einer endlichen Relation zwischen
dem Quark-Kondensat und der QCD-Skala Lambda, wobei weder ein
Infrarot-Cutoff noch ein spezifisches Instanton-Modell verwendet werden.
Allgemein weist das Instanton-Flüssigkeits-Modell eine erstaunliche interne
Konsistenz und gute Übereinstimmung mit experimentellen Daten auf.",
note = "English translation available at http://www.hutter1.net/physics/pdise.htm",
}
@Article{Hutter:96eta,
author = "Marcus Hutter",
title = "The mass of the $\eta'$ in self-dual {QCD}",
year = "1996",
pages = "275--278",
journal = "Physics Letters",
volume = "B367",
url = "http://arxiv.org/abs/hep-ph/9509401",
http = "http://www.hutter1.net/physics/petamas.htm",
abstract = "The QCD gauge field is modeled as an ensemble of statistically
independent selfdual and antiselfdual regions. This model is
motivated from instanton physics. The scale anomaly then allows
to relate the topological susceptibility to the gluon condensate.
With the help of Wittens formula for m_eta' and an estimate of
the suppression of the gluon condensate due to light quarks the
mass of the eta' can be related to f_pi and the physical gluon
condensate. We get the quite satisfactory value m_eta'=884+-116 MeV.
Using the physical eta' mass as an input it is in principle possible
to get information about the interaction between instantons and
anti-instantons.",
}
TechReport{Hutter:95spin,
author = "Marcus Hutter",
number = "LMU-95-15",
institution = "Theoretische Physik, LMU M{\"u}nchen",
title = "Proton Spin in the Instanton Background",
year = "1995",
url = "http://arxiv.org/abs/hep-ph/9509402",
http = "http://www.hutter1.net/physics/pspin.htm",
abstract = "The proton form factors are reduced to vacuum correlators
of 4 quark fields by assuming independent constituent
quarks. The axial singlet quark and gluonic form factors
are calculated in the instanton liquid model. A discussion
of gauge(in)dependence is given.",
note = "15 pages",
}
TechReport{Hutter:95prop,
author = "Marcus Hutter",
number = "LMU-95-03",
institution = "Theoretische Physik, LMU M{\"u}nchen",
title = "Gauge Invariant Quark Propagator in the Instanton Background",
year = "1995",
url = "http://arxiv.org/abs/hep-ph/9502361",
http = "http://www.hutter1.net/physics/pprop.htm",
abstract = "After a general discussion on the choice of gauge, we compare
the quark propagator in the background of one instanton in
regular and singular gauge with a gauge invariant propagator
obtained by inserting a path-ordered gluon exponential.
Using a gauge motivated by this analysis, we were able to
obtain a finite result for the quark condensate without
introducing an infrared cutoff nor invoking some instanton
model.",
note = "15 pages",
}
TechReport{Hutter:93gluon,
author = "Marcus Hutter",
number = "LMU-93-18",
institution = "Theoretische Physik, LMU M{\"u}nchen",
title = "Gluon Mass from Instantons",
year = "1993",
url = "http://arxiv.org/abs/hep-ph/9501335",
http = "http://www.hutter1.net/physics/pgluon.htm",
abstract = "The gluon propagator is calculated in the instanton background
in a form appropriate for extracting the momentum dependent
gluon mass. In background-xi-gauge we get for the mass 400 MeV
for small p^2 independent of the gauge parameter xi.",
note = "13 pages",
}
@MastersThesis{Hutter:92cfs,
author = "Marcus Hutter",
school = "Theoretische Informatik, TU M{\"u}nchen",
title = "{I}mplementierung eines {K}lassifizierungs-{S}ystems",
year = "1991",
url = "http://www.hutter1.net/ai/pcfs.htm",
ps = "http://www.hutter1.net/ai/pcfs.ps",
pdf = "http://www.hutter1.net/ai/pcfs.pdf",
abstract = "A classifier system is a massively parallel rule based system,
whose components (classifier) can exchange messages, whose behavior is
is assessed by a teacher (reinforcement), and which is able to learn by
means of credit assignment and a genetic algorithm. For an introduction
we have to refer to the, meanwhile extensive, literature; see especially
Goldberg (1989). The concept of a classifier system was first developed
by Holland (1986), but meanwhile a multitude of variants and extensions
exist (Booker et. al, 1989). So far it is impossible to
compare these variants in their performance, statements on the
quality of the various approaches are, hence, hard to impossible.
The program developed in this diploma thesis allows, for the first time,
a direct comparison of the most important variants.
The thesis describes the program, in which we have taken special attention
to an efficient implementation.",
zusammenfassung = "Ein Klassifizierungssystem (CFS, engl. Classifiersystem) ist
ein massiv paralleles regelbasiertes System, dessen Komponenten
(Classifier) Nachrichten (Messages) austauschen können, dessen
Verhalten von einem Lehrer beurteilt wird (Reinforcement) und
das mittels Credit-Assignment und genetischen Algorithmen fähig
ist zu lernen. Für eine einführende Darstellung muß auf die
inzwischen sehr umfangreiche Literatur, insbesondere Goldberg (1989),
verwiesen werden. Das Konzept des CFS wurde zuerst von Holland (1986)
entwickelt, inzwischen gibt es aber eine Vielzahl von Varianten und
Erweiterungen (Booker et. al (1989). Bisher ist es nicht möglich,
diese Varianten in ihrer Performance zu vergleichen, eine Aussage
über die Güte der verschiedenen Ansätze ist somit kaum oder
überhaupt nicht möglich. Das in dieser Diplomarbeit erstellte
Programm gestattet erstmals bzgl. der wichtigsten Varianten einen
direkten Vergleich. In den folgenden Kapiteln wird dieses Programm,
bei dem besonders auf eine effiziente Implementierung geachtet wurde,
beschrieben.",
note = "72 pages with C listing, in German",
}
TechReport{Hutter:90faka,
author = "Marcus Hutter",
institution = "Universit{\"a}t Erlangen-N{\"u}rnberg \&
Technische Universit{\"a}t M{\"u}nchen",
title = "{P}arallele {A}lgorithmen in der {S}tr{\"o}mungsmechanik",
type = "{F}erianakademie: {N}umerische {M}ethoden der {S}tr{\"o}mungsmechanik",
year = "1990",
url = "http://www.hutter1.net/official/faka.htm",
note = "10 pages, in German",
}
TechReport{Hutter:90fopra,
author = "Marcus Hutter",
institution = "Theoretische Informatik, TU M{\"u}nchen",
title = "A Reinforcement Learning {H}ebb Net",
year = "1990",
type = "Fortgeschrittenenpraktikum",
url = "http://www.hutter1.net/ai/fopra.htm",
ftp = "http://www.hutter1.net/ai/fopra.ps.gz",
pdf = "http://www.hutter1.net/ai/fopra.pdf",
abstract = "This Fopra is motivated by the following observations about
human learning and about human neural information processing.
On the one side humans are able to learn supervised, unsupervised
and by reinforcement, on the other side there is no neural
distinction between informative, uninformative and evaluative
feedback. Furthermore, the Hebb learning rule is the only
biological inspired learning mechanism. If the human brain
is indeed a Hebb net this would imply that Hebb nets are
able to learn by reinforcement. The goal of this Fopra is
to investigate whether and how Hebb nets could be used for
reinforcement learning. It is shown that Hebb nets with a
suitable prior net topology can indeed learn, at least
simple tasks, by reinforcement.",
note = "30 pages with Pascal listing, in German",
}
@Article{Hutter:87cad,
author = "Marcus Hutter",
title = "Fantastische {3D-Graphik} mit dem {CPC-Giga-CAD}",
journal = "7. Schneider Sonderheft, Happy Computer, Sonderheft 16",
publisher = "Markt\&Technik",
year = "1987",
pages = "41--92",
url = "http://www.hutter1.net/gigacad/gigacad.htm",
abstract = "CAD steht fur Computer Aided Design. Bis heute war dieses
Gebiet hauptsächlich Domäne der Großrechner.
Mit $\gg$CPC-Giga-CAD$\ll$ wird auch auf dem Schneider CPC
automatisiertes und computergestütztes Zeichnen und
Konstruieren zum Kinderspiel.",
}
| © 2000 by ... |
| ... Marcus Hutter |