This volume contains the papers presented at the 16th Annual International Conference on Algorithmic Learning Theory (ALT 2005), which was held in S- gapore (Republic of Singapore), October 8 11, 2005. The main objective of the conference is to provide an interdisciplinary forum for the discussion of the t- oretical foundations of machine learning as well as their relevance to practical applications. The conference was co-located with the 8th International Conf- enceonDiscoveryScience(DS2005). Theconferencewasalsoheldinconjunction with the centennial celebrations of the National University of Singapore. The volume includes 30 technical contributions, which were selected by the program committee from 98 submissions. It also contains the ALT 2005 invited talks presented by Chih-Jen Lin (National Taiwan University, Taipei, Taiwan) on Training Support Vector Machines via SMO-type Decomposition Methods, and by Vasant Honavar (Iowa State University, Ames, Iowa, USA) on Al- rithmsandSoftwareforCollaborativeDiscoveryfromAutonomous,Semantically Heterogeneous, Distributed, Information Sources. Furthermore, this volume - cludes an abstract of the joint invited talk with DS 2005 presented by Gary L. Bradshaw (Mississippi State University, Starkville, USA) on Invention and Arti?cial Intelligence, and abstracts of the invited talks for DS 2005 presented by Ross D. King (The University of Wales, Aberystwyth, UK) on The Robot Scientist Project, and by Neil Smalheiser (University of Illinois at Chicago, Chicago, USA) on The Arrowsmith Project: 2005 Status Report. The c- plete versions of these papers are published in the DS 2005 proceedings (Lecture Notes in Computer Science Vol. 3735).

Inhalt
Editors' Introduction.- Editors' Introduction.- Invited Papers.- Invention and Artificial Intelligence.- The Arrowsmith Project: 2005 Status Report.- The Robot Scientist Project.- Algorithms and Software for Collaborative Discovery from Autonomous, Semantically Heterogeneous, Distributed Information Sources.- Training Support Vector Machines via SMO-Type Decomposition Methods.- Kernel-Based Learning.- Measuring Statistical Dependence with Hilbert-Schmidt Norms.- An Analysis of the Anti-learning Phenomenon for the Class Symmetric Polyhedron.- Learning Causal Structures Based on Markov Equivalence Class.- Stochastic Complexity for Mixture of Exponential Families in Variational Bayes.- ACME: An Associative Classifier Based on Maximum Entropy Principle.- Constructing Multiclass Learners from Binary Learners: A Simple Black-Box Analysis of the Generalization Errors.- On Computability of Pattern Recognition Problems.- PAC-Learnability of Probabilistic Deterministic Finite State Automata in Terms of Variation Distance.- Learnability of Probabilistic Automata via Oracles.- Learning Attribute-Efficiently with Corrupt Oracles.- Learning DNF by Statistical and Proper Distance Queries Under the Uniform Distribution.- Learning of Elementary Formal Systems with Two Clauses Using Queries.- Gold-Style and Query Learning Under Various Constraints on the Target Class.- Non U-Shaped Vacillatory and Team Learning.- Learning Multiple Languages in Groups.- Inferring Unions of the Pattern Languages by the Most Fitting Covers.- Identification in the Limit of Substitutable Context-Free Languages.- Algorithms for Learning Regular Expressions.- A Class of Prolog Programs with Non-linear Outputs Inferable from Positive Data.- Absolute Versus Probabilistic Classification in a Logical Setting.-Online Allocation with Risk Information.- Defensive Universal Learning with Experts.- On Following the Perturbed Leader in the Bandit Setting.- Mixture of Vector Experts.- On-line Learning with Delayed Label Feedback.- Monotone Conditional Complexity Bounds on Future Prediction Errors.- Non-asymptotic Calibration and Resolution.- Defensive Prediction with Expert Advice.- Defensive Forecasting for Linear Protocols.- Teaching Learners with Restricted Mind Changes.