Algorithmic Learning Theory

1. Front Matter

   PDF

2. Invited Papers

   1. On Iterative Algorithms with an Information Geometry Background

      • Imre Csiszár

      Pages 1-1

   2. Visual Analytics: Combining Automated Discovery with Interactive Visualizations

      • Daniel A. Keim, Florian Mansmann, Daniela Oelke, Hartmut Ziegler

      Pages 2-2

   3. Some Mathematics behind Graph Property Testing

      • László Lovász

      Pages 3-3

   4. Finding Total and Partial Orders from Data for Seriation

      • Heikki Mannila

      Pages 4-4

   5. Computational Models of Neural Representations in the Human Brain

      • Tom M. Mitchell

      Pages 5-6

3. Regular Contributions

   1. Statistical Learning

      1. Generalization Bounds for Some Ordinal Regression Algorithms

         • Shivani Agarwal

         Pages 7-21

      2. Approximation of the Optimal ROC Curve and a Tree-Based Ranking Algorithm

         • Stéphan Clémençon, Nicolas Vayatis

         Pages 22-37

      3. Sample Selection Bias Correction Theory

         • Corinna Cortes, Mehryar Mohri, Michael Riley, Afshin Rostamizadeh

         Pages 38-53

      4. Exploiting Cluster-Structure to Predict the Labeling of a Graph

         • Mark Herbster

         Pages 54-69

      5. A Uniform Lower Error Bound for Half-Space Learning

         • Andreas Maurer, Massimiliano Pontil

         Pages 70-78

      6. Generalization Bounds for K-Dimensional Coding Schemes in Hilbert Spaces

         • Andreas Maurer, Massimiliano Pontil

         Pages 79-91

      7. Learning and Generalization with the Information Bottleneck

         • Ohad Shamir, Sivan Sabato, Naftali Tishby

         Pages 92-107

   2. Probability and Stochastic Processes

      1. Growth Optimal Investment with Transaction Costs

         • László Györfi, István Vajda

         Pages 108-122

      2. Online Regret Bounds for Markov Decision Processes with Deterministic Transitions

         • Ronald Ortner

         Pages 123-137

      3. On-Line Probability, Complexity and Randomness

         • Alexey Chernov, Alexander Shen, Nikolai Vereshchagin, Vladimir Vovk

         Pages 138-153

      4. Prequential Randomness

         • Vladimir Vovk, Alexander Shen

         Pages 154-168

      5. Some Sufficient Conditions on an Arbitrary Class of Stochastic Processes for the Existence of a Predictor

         • Daniil Ryabko

         Pages 169-182

      6. Nonparametric Independence Tests: Space Partitioning and Kernel Approaches

         • Arthur Gretton, László Györfi

         Pages 183-198

   3. Boosting and Experts

      1. Supermartingales in Prediction with Expert Advice

         • Alexey Chernov, Yuri Kalnishkan, Fedor Zhdanov, Vladimir Vovk

         Pages 199-213

This volume contains papers presented at the 19th International Conference on Algorithmic Learning Theory (ALT 2008), which was held in Budapest, Hungary during October 13–16, 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.

• Clustering
• comlexity
• concept spaces
• half-space learning
• language learning
• learning
• machine learning
• markov process
• neural representation
• visual datamining
• visualization

• Computer Science and Engineering, University of California, San Diego, USA

  Yoav Freund

• Department of Computer Science and Information Theory, Department of Computer Science and Budapest University of Technology and Economics, Budapest, Hungary

  László Györfi

• Department of Math., Stat. and Comp. Sci,, University of Illinois, Chicago, USA

  György Turán

• Division of Computer Science, Hokkaido University, Sapporo, Japan

  Thomas Zeugmann

Policies and ethics