%-------------Publications-of-Marcus-Hutter-2008--------------%
@InProceedings{Hutter:08select,
author = "K. Hingee and M. 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",
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 = "D. Ryabko and M. 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/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",
project = "http://www.hutter1.net/official/projects.htm#bayes",
code = "http://www.hutter1.net/ai/cpcreg.zip",
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",
xdoi = "??",
issn = "0302-9743",
isbn = "3-540-75224-2",
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 = "??",
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 = "A. Piatti and M. Zaffalon and F. Trojani and M. 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",
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\%",
}
@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 = "A key issue in statistics and machine learning is to automatically
select the ``right'' model complexity, e.g.\ the number of neighbors
to be averaged over in k nearest neighbor (kNN) regression or the
polynomial degree in regression with polynomials. We suggest a novel
principle (LoRP) for model selection in regression and
classification. It is based on the loss rank, which counts how many
other (fictitious) data would be fitted better. LoRP selects the
model that has minimal loss rank. Unlike most penalized maximum
likelihood variants (AIC,BIC,MDL), LoRP only depends on the
regression functions and the loss function. It works without a
stochastic noise model, and is directly applicable to any
non-parametric regressor, like kNN.",
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\%",
}
@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,
@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 fi