Algorithmic Learning Theory

Marcus Hutter received his masters in computer sciences in 1992 at the Technical University in Munich, Germany. After his PhD in theoretical particle physics he developed algorithms in a medical software company for 5 years. For four years he has been working as a researcher at the AI institute IDSIA in Lugano, Switzerland. His current interests are centered around reinforcement learning, algorithmic information theory and statistics, universal induction schemes, adaptive control theory, and related areas.

Editors' Introduction.- Editors' Introduction.- Invited Papers.- A Theory of Similarity Functions for Learning and Clustering.- Machine Learning in Ecosystem Informatics.- Challenge for Info-plosion.- A Hilbert Space Embedding for Distributions.- Simple Algorithmic Principles of Discovery, Subjective Beauty, Selective Attention, Curiosity and Creativity.- Invited Papers.- Feasible Iteration of Feasible Learning Functionals.- Parallelism Increases Iterative Learning Power.- Prescribed Learning of R.E. Classes.- Learning in Friedberg Numberings.- Complexity Aspects of Learning.- Separating Models of Learning with Faulty Teachers.- Vapnik-Chervonenkis Dimension of Parallel Arithmetic Computations.- Parameterized Learnability of k-Juntas and Related Problems.- On Universal Transfer Learning.- Online Learning.- Tuning Bandit Algorithms in Stochastic Environments.- Following the Perturbed Leader to Gamble at Multi-armed Bandits.- Online Regression Competitive with Changing Predictors.- Unsupervised Learning.- Cluster Identification in Nearest-Neighbor Graphs.- Multiple Pass Streaming Algorithms for Learning Mixtures of Distributions in .- Language Learning.- Learning Efficiency of Very Simple Grammars from Positive Data.- Learning Rational Stochastic Tree Languages.- Query Learning.- One-Shot Learners Using Negative Counterexamples and Nearest Positive Examples.- Polynomial Time Algorithms for Learning k-Reversible Languages and Pattern Languages with Correction Queries.- Learning and Verifying Graphs Using Queries with a Focus on Edge Counting.- Exact Learning of Finite Unions of Graph Patterns from Queries.- Kernel-Based Learning.- Polynomial Summaries of Positive Semidefinite Kernels.- Learning Kernel Perceptrons on Noisy Data Using Random Projections.- Continuityof Performance Metrics for Thin Feature Maps.- Other Directions.- Multiclass Boosting Algorithms for Shrinkage Estimators of Class Probability.- Pseudometrics for State Aggregation in Average Reward Markov Decision Processes.- On Calibration Error of Randomized Forecasting Algorithms.