Algorithmic Learning Theory

Name: Algorithmic Learning Theory | 22nd International Conference, ALT 2011, Espoo, Finland, October 5-7, 2011, Proceedings
Brand: Springer
Price: 53.49 EUR
Availability: OnlineOnly

22nd International Conference, ALT 2011, Espoo, Finland, October 5-7, 2011, Proceedings

Jyriki Kivinen Csaba Szepesvári Esko Ukkonen Thomas Zeugmann(Herausgeber*in)

Springer (Verlag)

Erschienen am 7. Oktober 2011

XIII, 453 Seiten

E-Book

PDF mit Wasserzeichen-DRM

Systemvoraussetzungen

978-3-642-24412-4 (ISBN)

53,49 €inkl. 7% MwSt.

Systemvoraussetzungen

für PDF mit Wasserzeichen-DRM

E-Book Einzellizenz

Als Download verfügbar

Beschreibung

Weitere Details

Weitere Ausgaben

Inhalt

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

Systemvoraussetzungen

Als PDF speichern Als Link merken