Table of Contents



          Invited Papers
          On Iterative Algorithms with a n I nformation Geometry B a c k g r o u n d . . . .    1
              Irare Csiszdr
          Visual Analytics: Combining Automated Discovery with Interactive
          Visualizations                                                                       2
             Daniel A. Keim, Florian Mansmann, Daniela Oelke, and
             Hartmut Ziegler
          Some Mathematics behind Graph Property Testing                                        3
            Ldszlö Lovdsz
          Finding Total and Partial Orders from Data for Seriation                             4
             Heikki Mannila
          Computational Models of Neural Representations in the Human
          Brain (Extended Abstract)                                                             5
             Tom M. Mitchell

          Regulär Contributions

          Statistical Learning
          Generalization Bounds for Some Ordinal Regression Algorithms                          7
            Shivani Agarwal
          Approximation of t he Optimal ROC Curve and a Tree-Based Ranking
          Algorithm                                                                            22
             Stephan Clemengon and Nicolas Vayatis
          Sample Selection Bias Correction Theory                                              38
             Corinna Cortes, Mehryar Mohri, Michael Riley, and
            Afshin Rostamizadeh
          Exploiting Cluster-Structure t o Predict the Labeling of a G raph                    54
            Mark Herbster
          A Uniform Lower Error Bound for Half-Space Learning                                  70
             Andreas Maurer and Massimiliano Pontil
          Generalization Bounds for K-Dimensional Coding Schemes in H ubert
          Spaces                                                                               79
             Andreas Maurer and Massimiliano Pontil




XII    Table of Contents

Learning and Generalization with the Information Bottleneck              92
   Ohad Shamir, Sivan Sabato, and Naftali Tishby

Probability and Stochastic Processes
Growth Optimal Investment with Transaction Costs                        108
   Ldszlö Györfi and Istvdn Vajda
Online Regret Bounds for Markov Decision Processes with Deterministic
Transitions                                                             123
   Ronald Ortner
On-Line Probability, Complexity and Randomness                          138
   Alexey Chernov, Alexander Shen, Nikolai Vereshchagin, and
   Vladimir Vovk
Prequential Randomness                                                  154
   Vladimir Vovk and Alexander Shen
Some Sufficient Conditions on an Arbitrary Class of Stochastic
Processes for the Existence of a Predictor                              169
   Daniil Ryabko
Nonparametric Independence Tests: Space Partitioning and Kernel
Approaches                                                              183
   Arthur Gretton and Ldszlö Györfi

Boosting and Experts
Supermartingales in Prediction with Expert Advice                   199
   Alexey Chernov, Yuri Kalnishkan, Fedor Zhdanov, and
    Vladimir Vovk
Aggregating Algorithm for a Space of Analytic Functions             214
   Mikhail Dashevskiy
Smooth Boosting for Margin-Based Ranking                            227
   Jun-ichi Moribe, Kohei Hatano, Eiji Takimoto, and Masayuki Takeda
Learning with Continuous Experts Using Drifting Games               240
   Indraneel Mukherjee and Robert E. Schapire
Entropy Regularized LPBoost                                         256
   Manfred K. Warmuth, Karen A. Glocer, and S.V.N. Vishwanathan

Active Learning and Queries
Optimally Learning Social Networks with Activations and
Suppressions                                                            272
   Dana Angluin, James Aspnes, and Lev Reyzin
Active Learning in Multi-armed Bandits                                  287
   Andrds Antos, Varun Grover, and Csaba Szepesvdri
                                                       Table of Contents   XIII

Query Learning and Certificates in Lattices                                303
  M. Arias and J.L. Balcdzar

Clustering with Interactive Feedback                                       316
   Maria-Florina Balcan and Avrim Blum

Active Learning of Group-Structured Environments                           329
   Gabor Bartök, Csaba Szepesvdri, and Sandra Zilles

Finding the Rare Cube                                                      344
   Shlomo Hoory and Oded Margalit

Inductive Inference
Iterative Learning of Simple External Contextual Languages                 359
    Leonor Becerra-Bonache, John Case, Sanjay Jain, and
    Frank Stephan

Topological Properties of Concept Spaces                                   374
   Matthew de Brecht and Akihiro Yamamoto

Dynamically Delayed Postdictive Completeness and Consistency in
Learning                                                                   389
   John Case and Timo Kötzing

Dynamic Modeling in Inductive Inference                                    404
  John Case and Timo Kötzing

Optimal Language Learning                                                  419
  John Case and Samuel E. Moelius III

Numberings Optimal for Learning                                            434
  Sanjay Jain and Frank Stephan

Learning with Temporary Memory                                             449
   Steffen Lange, Samuel E. Moelius III, and Sandra Zilles

Errat um
Erratum: Constructing Multiclass Learners from Binary Learners: A
Simple Black-Box Analysis of t he Generalization Errors                    464
   Jittat Fakcharoenphol and Boonserm Kijsirikul

Author Index                                                               467