Algorithmic Learning Theory

This volume contains papers presented at the 19th International Conference on Algorithmic Learning Theory (ALT 2008), which was held in Budapest, Hungary during October 1316, 2008. The conference was co-located with the 11th - ternational Conference on Discovery Science (DS 2008). The technical program of ALT 2008 contained 31 papers selected from 46 submissions, and 5 invited talks. The invited talks were presented in joint sessions of both conferences. ALT 2008 was the 19th in the ALT conference series, established in Japan in 1990. The series Analogical and Inductive Inference is a predecessor of this series: it was held in 1986, 1989 and 1992, co-located with ALT in 1994, and s- sequently merged with ALT. ALT maintains its strong connections to Japan, but has also been held in other countries, such as Australia, Germany, Italy, Sin- pore, Spain and the USA. The ALT conference series is supervised by its Steering Committee: Naoki Abe (IBM T. J.

Autorentext
Yoav Freund is Professor of Computer Science at the University of California, San Diego.

Klappentext

This book constitutes the refereed proceedings of the 19th International Conference on Algorithmic Learning Theory, ALT 2008, held in Budapest, Hungary, in October 2008, co-located with the 11th International Conference on Discovery Science, DS 2008.

The 31 revised full papers presented together with the abstracts of 5 invited talks were carefully reviewed and selected from 46 submissions. The papers are dedicated to the theoretical foundations of machine learning; they address topics such as statistical learning; probability and stochastic processes; boosting and experts; active and query learning; and inductive inference.

Inhalt
Invited Papers.- On Iterative Algorithms with an Information Geometry Background.- Visual Analytics: Combining Automated Discovery with Interactive Visualizations.- Some Mathematics behind Graph Property Testing.- Finding Total and Partial Orders from Data for Seriation.- Computational Models of Neural Representations in the Human Brain.- Regular Contributions.- Generalization Bounds for Some Ordinal Regression Algorithms.- Approximation of the Optimal ROC Curve and a Tree-Based Ranking Algorithm.- Sample Selection Bias Correction Theory.- Exploiting Cluster-Structure to Predict the Labeling of a Graph.- A Uniform Lower Error Bound for Half-Space Learning.- Generalization Bounds for K-Dimensional Coding Schemes in Hilbert Spaces.- Learning and Generalization with the Information Bottleneck.- Growth Optimal Investment with Transaction Costs.- Online Regret Bounds for Markov Decision Processes with Deterministic Transitions.- On-Line Probability, Complexity and Randomness.- Prequential Randomness.- Some Sufficient Conditions on an Arbitrary Class of Stochastic Processes for the Existence of a Predictor.- Nonparametric Independence Tests: Space Partitioning and Kernel Approaches.- Supermartingales in Prediction with Expert Advice.- Aggregating Algorithm for a Space of Analytic Functions.- Smooth Boosting for Margin-Based Ranking.- Learning with Continuous Experts Using Drifting Games.- Entropy Regularized LPBoost.- Optimally Learning Social Networks with Activations and Suppressions.- Active Learning in Multi-armed Bandits.- Query Learning and Certificates in Lattices.- Clustering with Interactive Feedback.- Active Learning of Group-Structured Environments.- Finding the Rare Cube.- Iterative Learning of Simple External Contextual Languages.- Topological Properties of Concept Spaces.- Dynamically Delayed Postdictive Completeness and Consistency in Learning.- Dynamic Modeling in Inductive Inference.- Optimal Language Learning.- Numberings Optimal for Learning.- Learning with Temporary Memory.- Erratum: Constructing Multiclass Learners from Binary Learners: A Simple Black-Box Analysis of the Generalization Errors.