Algorithmic Learning Theory : 20th International Conference, ALT 2009, Porto, Portugal, October 3-5, 2009, Proceedings

by Gavald…, Ricard; Lugosi, Gabor; Zeugmann, Thomas; Zilles, Sandra

• ISBN13: 9783642044137
• ISBN10: 3642044131
• Edition: 1st
• Format: Paperback
• Copyright: 2009-10-01
• Publisher: Springer-Verlag New York Inc

Summary

This book constitutes the refereed proceedings of the 20th International Conference on Algorithmic Learning Theory, ALT 2009, held in Porto, Portugal, in October 2009, co-located with the 12th International Conference on Discovery Science, DS 2009.The 26 revised full papers presented together with the abstracts of 5 invited talks were carefully reviewed and selected from 60 submissions. The papers are divided into topical sections of papers on online learning, learning graphs, active learning and query learning, statistical learning, inductive inference, and semisupervised and unsupervised learning. The volume also contains abstracts of theinvited talks: Sanjoy Dasgupta, The Two Faces of Active Learning; Hector Geffner, Inference andLearning in Planning; Jiawei Han, Mining Heterogeneous; Information Networks By Exploring the Power of Links, Yishay Mansour, Learning and Domain Adaptation; Fernando C.N. Pereira, Learning on the Web.

Table of Contents

Invited Papers
The Two Faces of Active Learning	p. 1
Inference and Learning in Planning	p. 2
Mining Heterogeneous Information Networks by Exploring the Power of Links	p. 3
Learning and Domain Adaptation	p. 4
Learning on the Web	p. 7
Regular Contributions
Online Learning
Prediction with Expert Evaluators' Advice	p. 8
Pure Exploration in Multi-armed Bandits Problems	p. 23
The Follow Perturbed Leader Algorithm Protected from Unbounded One-Step Losses	p. 38
Computable Bayesian Compression for Uniformly Discretizable Statistical Models	p. 53
Calibration and Internal No-Regret with Random Signals	p. 68
St. Petersburg Portfolio Games	p. 83
Learning Graphs
Reconstructing Weighted Graphs with Minimal Query Complexity	p. 97
Learning Unknown Graphs	p. 110
Completing Networks Using Observed Data	p. 126
Active Learning and Query Learning
Average-Case Active Learning with Costs	p. 141
Canonical Horn Representations and Query Learning	p. 156
Learning Finite Automata Using Label Queries	p. 171
Characterizing Statistical Query Learning: Simplified Notions and Proofs	p. 186
An Algebraic Perspective on Boolean Function Learning	p. 201
Statistical Learning
Adaptive Estimation of the Optimal ROC Curve and a Bipartite Ranking Algorithm	p. 216
Complexity versus Agreement for Many Views: Co-regularization for Multi-view Semi-supervised Learning	p. 232
Error-Correcting Tournaments	p. 247
Inductive Inference
Difficulties in Forcing Fairness of Polynomial Time Inductive Inference	p. 263
Learning Mildly Context-Sensitive Languages with Multidimensional Substitutability from Positive Data	p. 278
Uncountable Automatic Classes and Learning	p. 293
Iterative Learning from Texts and Counterexamples Using Additional Information	p. 308
Incremental Learning with Ordinal Bounded Example Memory	p. 323
Learning from Streams	p. 338
Semi-supervised and Unsupervised Learning
Smart PAC-Learners	p. 353
Approximation Algorithms for Tensor Clustering	p. 368
Agnostic Clustering	p. 384
Author Index	p. 399
Table of Contents provided by Ingram. All Rights Reserved.