[home] [search] |
BibTeX of Marcus Hutter |
[contact] [up] |

## %-------------Publications-of-Marcus-Hutter-2007--------------%

@Article{Hutter:07uspx, author = "M. 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", press = "http://www.hutter1.net/official/press.htm#???", 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 = "M. Hutter and An. 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 = "M. Hutter and S. Legg and P. M. B. Vit{\'a}nyi", title = "Algorithmic Probability", journal = "Scholarpedia", pages = "19046", _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", 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:07pquest, author = "D. Ryabko and M. 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 = "S. Legg and M. 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 = "M. 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 = "M. Hutter", title = "Algorithmic Information Theory: a brief non-technical guide to the field", journal = "Scholarpedia", pages = "9620", _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", 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 = "A. Chernov and M. Hutter and J. Schmidhuber", _author = "Alexey Chernov and Marcus Hutter and Juergen 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 = "M. 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 = "M. 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 = "M. Hutter and S. Legg", title = "Fitness Uniform Optimization", journal = "IEEE Transactions on Evolutionary Computation", volume = "10", mumber = "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 = "M. 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 = "D. Ryabko and M. 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 = "J. Poland and M. 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 = "M. 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 = "J. Poland and M. 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 = "S. Legg and M. 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 = "V. Zhumatiy and F. Gomez and M. Hutter and J. Schmidhuber", _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 = "M. Mastrolilli and M. 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", mumber = "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 = "M. Hutter and W. Merkle and P. 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 = "S. Legg and M. Hutter", number = "IDSIA-21-04", title = "Ergodic {MDP}s Admit Self-Optimising Policies", year = "2004", institution = "{IDSIA}", }

TechReport{Hutter:04env, author = "S. Legg and M. 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 = "M. Hutter and An. 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 = "M. Hutter and J. 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 = "J. Poland and M. 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 = "J. Poland and M. 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 = "S. Legg and M. Hutter and A. 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", 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", 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. Schmidhuber and M. 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+", note = "\\ 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+", note = "\\ 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 Juergen 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 Juergen 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", 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 = "A. Blumhofer and M. Hutter", _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 ... | [home] [search] [science] [contact] [up] | ... Marcus Hutter |