This book constitutes the refereed proceedings of the 18th International Conference on Algorithmic Learning Theory, ALT 2007, held in Sendai, Japan, October 1-4, 2007, colocated with the 10th International Conference on Discovery Science, DS 2007. The 25 revised full papers presented together with the abstracts of 5 invited papers were carefully reviewed and selected from 50 submissions. The papers are dedicated to the theoretical foundations of machine learning; they address topics such as query models, on-line learning, inductive inference, algorithmic forecasting, boosting, support vector machines, kernel methods, complexity and learning, reinforcement learning, unsupervised learning and grammatical inference. This volume contains the papers presented at the 18th International Conf- ence on Algorithmic Learning Theory (ALT 2007), which was held in Sendai (Japan) during October 1¿4, 2007. The main objective of the conference was to provide an interdisciplinary forum for high-quality talks with a strong theore- cal background and scienti?c interchange in areas such as query models, on-line learning, inductive inference, algorithmic forecasting, boosting, support vector machines, kernel methods, complexity and learning, reinforcement learning, - supervised learning and grammatical inference. The conference was co-located with the Tenth International Conference on Discovery Science (DS 2007). This volume includes 25 technical contributions that were selected from 50 submissions by the ProgramCommittee. It also contains descriptions of the ?ve invited talks of ALT and DS; longer versions of the DS papers are available in the proceedings of DS 2007. These invited talks were presented to the audience of both conferences in joint sessions. Editors' Introduction 1 Marcus Hutter, Rocco A. Servedio, and Eiji Takimoto Invited Papers A Theory of Similarity Functions for Learning and Clustering 9 Avrim Blum Machine Learning in Ecosystem Informatics 10 Thomas G. Dietterich Challenge for Info-plosion 12 Masaru Kitsuregawa A Hilbert Space Embedding for Distributions 13 Alex Smola, Arthur Gretton, Le Song, and Bernhard Sch lkopf Simple Algorithmic Principles of Discovery, Subjective Beauty, Selective Attention, Curiosity and Creativity 32 J rgen Schmidhuber Invited Papers Inductive Inference Feasible Iteration of Feasible Learning Functionals 34 John Case, Timo K tzing, and Todd Paddock Parallelism Increases Iterative Learning Power 49 John Case and Samuel E. Moelius III Prescribed Learning of R.E. Classes 64 Sanjay Jain, Frank Stephan, and Nan Ye Learning in Friedberg Numberings 79 Sanjay Jain and Frank Stephan Complexity Aspects of Learning Separating Models of Learning with Faulty Teachers 94 Vitaly Feldman, Shrenik Shah, and Neal Wadhwa Vapnik-Chervonenkis Dimension of Parallel Arithmetic Computations 107 C r L. Alonso and Jos uis Monta a Parameterized Learnability of k-Juntas and Related Problems 120 Vikraman Arvind, Johannes K bler, and Wolfgang Lindner On Universal Transfer Learning 135 M.M. Hassan Mahmud Online Learning Tuning Bandit Algorithms in Stochastic Environments 150 Jean-Yves Audibert, R Munos, and Csaba Szepesv Following the Perturbed Leader to Gamble at Multi-armed Bandits 166 Jussi Kujala and Tapio Elomaa Online Regression Competitive with Changing Predictors 181 Steven Busuttil and Yuri Kalnishkan Unsupervised Learning Cluster Identification in Nearest-Neighbor Graphs 196 Markus Maier, Matthias Hein, and Ulrike von Luxburg Multiple Pass Streaming Algorithms for Learning Mixtures of Distributions in Rd 211 Kevin L. Chang Language Learning Learning Efficiency of Very Simple Grammars from Positive Data, 227 Ryo Yoshinaka Learning Rational Stochastic Tree Languages 242 Fran s Denis and Amaury Habrard Query Learning One-Shot Learners Using Negative Counterexamples and Nearest Positive Examples 257 Sanjay Jain and Efirn Kinber Polynomial Time Algorithms for Learning k-Reversible Languages and Pattern Languages with Correction Queries 272 Cristina Tirnauca and Timo Knuutila Learning and Verifying Graphs Using Queries with a Focus on Edge Counting 285 Lev Reyzin and Nikhil Srivastava Exact Learning of Finite Unions of Graph Patterns from Queries 298 Rika Okada, Satoshi Matsumoto, Tomoyuki Uchida, Yusuke Suzuki, and Takayoshi Shoudai Kernel-Based Learning Polynomial Summaries of Positive Semidefinite Kernels 313 Kilho Shin and Tetsuji Kuboyama Learning Kernel Perceptrons on Noisy Data Using Random Projections 328 Guillaume Stempfel and Liva Ralaivola Continuity of Performance Metrics for Thin Feature Maps 343 Adam Kowalczyk Other Directions Multiclass Boosting Algorithms for Shrinkage Estimators of Class Probability 358 Takafumi Kanamori Pseudometrics for State Aggregation in Average Reward Markov Decision Processes 373 Ronald Ortner On Calibration Error of Randomized Forecasting Algorithms 388 Vladimir V. V'yugin Author Index 403