Algorithmic Learning Theory
22nd International Conference, ALT 2011, Espoo, Finland, October 5-7, 2011, Proceedings
Published on 7. October 2011
XIII, 453 pages
978-3-642-24412-4 (ISBN)
Description
This book constitutes the refereed proceedings of the 22nd International Conference on Algorithmic Learning Theory, ALT 2011, held in Espoo, Finland, in October 2011, co-located with the 14th International Conference on Discovery Science, DS 2011.
The 28 revised full papers presented together with the abstracts of 5 invited talks were carefully reviewed and selected from numerous submissions. The papers are divided into topical sections of papers on inductive inference, regression, bandit problems, online learning, kernel and margin-based methods, intelligent agents and other learning models.
The 28 revised full papers presented together with the abstracts of 5 invited talks were carefully reviewed and selected from numerous submissions. The papers are divided into topical sections of papers on inductive inference, regression, bandit problems, online learning, kernel and margin-based methods, intelligent agents and other learning models.
More details
Other editions
Additional editions
Jyriki Kivinen | Csaba Szepesvári | Esko Ukkonen
Algorithmic Learning Theory
22nd International Conference, ALT 2011, Espoo, Finland, October 5-7, 2011, Proceedings
Book
09/2011
1st Edition
Springer
€53.49
Shipment within 7-9 days
Content
- Title
- Preface
- Organization
- Table of Contents
- Editors' Introduction
- Invited Papers
- Models for Autonomously Motivated Exploration in Reinforcement Learning
- Introduction
- Preliminaries
- Learning to Reach States
- Infinite State Spaces
- Other Learning Objectives
- Further Research Directions
- References
- On the Expressive Power of Deep Architectures
- Learning Artificial Intelligence
- Local and Non-local Generalization: The Challenge and Curse of Many Factors of Variation
- Expressive Power of Deep Architectures
- Distributed and Sparse Representations
- Depth
- A Deep Sum-Product Networks Case Study
- A Zoo of Learning Algorithms
- Principles, Challenges and Ideas Ahead
- References
- Optimal Estimation
- Modeling Problem
- Models and Estimators
- Learning from Label Preferences
- Information Distance and Its Extensions
- Inductive Inference
- Iterative Learning from Positive Data and Counters
- Introduction
- Differences in Counters
- Mathematical Preliminaries
- Learning Criteria
- Separations by Classes of Infinite Languages
- Comparison of Counter Types
- References
- Robust Learning of Automatic Classes of Languages
- Introduction
- Automatic Structures, Languages and Translations
- Texts and Learnability
- General Characterisation
- Characterisations of Learnability Variously Constrained
- Learning from Queries
- Conclusion
- References
- Learning and Classifying
- Introduction
- Definitions and Examples
- General Notions and Learnability
- Classification
- Illustrative Examples
- Classification Versus BC-Learnability
- Classification Versus Finite and Ex-learnability
- Limitations of Classification Variously Constrained
- Conclusion
- References
- Learning Relational Patterns
- Introduction
- Learning (Typed) Pattern Languages
- Relational Patterns
- The Membership Problem
- Probabilistic Relational Patterns
- Conclusion
- References
- Regression
- Adaptive and Optimal Online Linear Regression on $\ell^1$-Balls
- Introduction
- Setting
- Contributions and Related Works
- Optimal Rates
- Upper Bound
- Lower Bound
- Adaptation to Unknown X, Y and T
- Lipschitzification of the Loss Function
- Lipschitzifying Exponentiated Gradient Algorithm
- Adaptation to Unknown U
- Extension to a Fully Adaptive Algorithm and Other Discussions
- References
- Re-adapting the Regularization ofWeights for Non-stationary Regression
- Introduction
- Problem Setting
- Algorithm
- Analysis
- Proof of Theorem 1
- Algorithm for Unknown Amount of Drift
- Simulations
- Related Work and Summary
- References
- Competing against the Best Nearest Neighbor Filter in Regression
- Introduction
- Notation and Background
- Oracle Inequalities
- Nearest Neighbor Filtering
- General Linear Smoothing
- Main Result
- Numerical Experiments
- Conclusion and Outlook
- References
- Bandit Problems
- Lipschitz Bandits without the Lipschitz Constant
- Introduction
- Setting and Notation
- The Minimax Optimal Orders of Magnitude of the Regret
- How to Achieve a Minimax Optimal Regret When L is Known
- Achieving a Minimax Optimal Regret Not Knowing L
- Some Preliminary Approximation Results
- A Strategy in Two Phases
- References
- Deviations of Stochastic Bandit Regret
- Introduction
- Problem Setup and Definitions
- Impossibility Result
- Positive Results
- is Finite
- Bernoulli Laws
- * Is Known
- Proof of Theorem 6
- References
- On Upper-Confidence Bound Policies for Switching Bandit Problems
- Introduction
- Algorithms
- Regret Bounds
- Tuning the Parameters
- Analysis of D-UCB
- A Lower-Bound on the Regret in Abruptly Changing Environment
- Simulations
- Technical Results
- Conclusion and Perspectives
- References
- Upper-Confidence-Bound Algorithms for Active Learning in Multi-armed Bandits
- Introduction
- Preliminaries
- Allocation Strategy Based on Chernoff-Hoeffding UCB
- The CH-AS Algorithm
- Regret Bound and Discussion
- Allocation Strategy Based on Bernstein UCB
- The B-AS Algorithm
- Regret Bound and Discussion
- Regret for Gaussian Distributions
- Numerical Experiments
- CH-AS, B-AS, and GAFS-MAX with Gaussian Arms
- B-AS with Non-gaussian Arms
- Conclusions and Open Questions
- References
- Online Learning
- The Perceptron with Dynamic Margin
- Introduction
- Motivation of the Algorithm
- Theoretical Analysis
- Efficient Implementation
- Experimental Evaluation
- Conclusions
- References
- Combining Initial Segments of Lists
- Introduction
- Setting
- Batch Algorithm
- The Randomized Online Algorithm Based on Sampling
- Lower Bounds
- Combining Lists with Duplicates
- NP-Hardness by Reduction from Set Cover
- Working around the Hardness
- Open Problems
- References
- Regret Minimization Algorithms for Pricing Lookback Options
- Introduction
- Preliminaries
- Arbitrage-Free Bounds
- Trading Algorithms and Bounds for Lookback Options
- Simple Arbitrage-Free Bounds
- Combining Regret Minimization and One-Way Trading
- A Price-Oriented Rule and Bound.
- Bounds Based on Competitive Ratio.
- Discussion of the Bounds
- Empirical Results
- References
- Making Online Decisions with Bounded Memory
- Introduction
- Preliminaries
- Our First Algorithm
- Our Second Algorithm
- A Lower Bound
- References
- Universal Prediction of Selected Bits
- Introduction
- Notation and Definitions
- Mnorm Predicts Selected Bits
- M Fails to Predict Selected Bits
- Discussion
- References
- Semantic Communication for Simple Goals Is Equivalent to On-line Learning
- Introduction
- Semantic Communication in Infinite Executions
- Sensing: Implicit Descriptions of Goals in Terms of Feedback
- On-line Learning is Equivalent to Semantic Communication with One-Round Goals
- Universal Users from On-line Learning Algorithms
- Richer Feedback and the Limitations of Basic Sensing
- Limitations of Basic Sensing
- Richer Feedback
- References
- Kernel and Margin Based Methods
- Accelerated Training of Max-Margin Markov Networks with Kernels
- Introduction
- Excessive Gap Technique with Bregman Projection
- Training Max-Margin Markov Networks
- Rates of Convergence
- Efficient Computation by Clique Decomposition
- Basics
- Efficient Computation
- Kernelization
- Efficiency in Memory and Computation
- Discussion
- References
- Domain Adaptation in Regression
- Introduction
- Preliminaries
- Learning Scenario
- Discrepancy Distance
- Theoretical Analysis
- Discrepancy with Universal Kernels
- Guarantees for Kernel-Based Regularization Algorithms
- Optimization Problems
- Discrepancy Minimization in Feature Space
- Discrepancy Minimization with Kernels
- Algorithm
- Experiments
- Conclusion
- References
- Approximate Reduction from AUC Maximization to 1-Norm Soft Margin Optimization
- Introduction
- Preliminaries
- 1-Norm Soft Margin over Pairs of Positive and Negative Instances
- 1-Norm Hard Margin Optimization over Pairs
- Reduction Methods from 1-Norm Soft Margin Optimization over Pairs
- Our Method
- Practical Heuristics
- Experiments
- Artificial Data
- UCI Data
- Reuters Data
- Computation Time
- Conclusion and Future Work
- References
- Intelligent Agents
- Axioms for Rational Reinforcement Learning
- Introduction
- Rational Decisions for Accepting or Rejecting Contracts
- Probabilities and Expectations
- Multiple Events
- Marginals
- Conditioning
- Learning
- Choosing between Contracts
- Choosing between Environments
- Countable Sets of Events
- Rational Agents for Classes of Environments
- Asymptotic Optimality
- Conclusions
- References
- Universal Knowledge-Seeking Agents
- Introduction
- Notation
- Knowledge-Seeking Agents
- Square Knowledge-Seeking Agent
- Optimal Non-learning Agent
- Asymptotic Optimality
- Asymptotic Optimality of Square-KSA
- Separability
- Full Separability
- Shannon-KSA
- Curiosity-Seeking Complexity
- Discussion and Conclusion
- Technical Proofs
- Asymptotically Optimal Agents
- Introduction
- Notation and Definitions
- Non-existence of Asymptotically Optimal Policies
- Existence of Weak Asymptotically Optimal Policies
- Discussion
- References
- Time Consistent Discounting
- Introduction
- Notation and Problem Setup
- Examples
- Theorems
- Game Theoretic Approach
- Discussion
- References
- Other Learning Models
- Distributional Learning of Simple Context-Free Tree Grammars
- Introduction
- Preliminaries
- Trees and Substitutions
- Simple Context-Free Tree Grammars
- Distributional Learning of Simple Context-Free Tree Grammars
- Decomposition of Trees
- Substitutable Simple Context-Free Tree Languages
- Finite Environment Property
- Conclusion
- References
- On Noise-Tolerant Learning of Sparse Parities and Related Problems
- Introduction
- Sparse Parity
- Implications to Related Problems
- Our Approach
- Past Work
- Notation and Preliminaries
- Learning Sparse Parities
- Improved Bounds for Improper Learning of r-Parities
- Application to Learning Juntas and DNF
- Discussion
- References
- Supervised Learning and Co-training
- Introduction
- Definitions, Notations, and Facts
- A Closer Look to the Disagreement Coefficient
- A Combinatorial Upper Bound
- Invariance of the Disagreement Coefficient under Padding
- Supervised Learning and Co-training
- General Upper Bounds on the Sample Size
- Lower Bounds on the Sample Size
- Sample Size in Case of One-Sided Errors
- Final Remarks
- References
- Learning a Classifier when the Labeling Is Known
- Introduction
- Our Results
- Applications to Semi-supervised Learning
- Outline of the Paper
- Basic Definitions
- Main Result
- KLCL of Classes of Infinite VC Dimension
- KLCL Learning of Finite VC-Classes
- The Weighted Dice Problem
- Reducing the Dice Problem to KLCL Learning
- Reduction of Usual Learning to KLCL and Classes That Are Not KLCL Learnable
- Conclusions and Future Work
- References
- Erratum
- Erratum: Learning without Coding
- References
- Author Index
