The Informational Complexity of Learning

Active Learning Algorithms.- 3.3.2.1 Derivation of an optimal sampling strategy.- 3.3.3 Some Simulations.- 3.3.3.1 Distribution of points selected.- 3.3.3.2 Error Rates:.- 3.4 Conclusions, Extensions, and Open Problems.- 3.5 A Simple Example.- 3.6 Generalizations.- 3.6.1 Localized Function Classes.- 3.6.2 The General ?-focusing strategy;.- 3.6.3 Generalizations and Open Problems.- 4. Language Learning.- 4.1 Language Learning and The Poverty of Stimulus.- 4.2 Constrained Grammars-Principles and Parameters.- 4.2.1 Example: A 3-parameter System from Syntax.- 4.2.2 Example: Parameterized Metrical Stress in Phonology.- 4.3 Learning in the Principles and Parameters Framework.- 4.4 Formal Analysis of the Triggering Learning Algorithm.- 4.4.1 Background.- 4.4.2 The Markov formulation.- 4.4.2.1 Parameterized Grammars and their Corresponding Markov Chains.- 4.4.2.2 Markov Chain Criteria for Learnability.- 4.4.2.3 The Markov chain for the 3-parameter Example.- 4.4.3 Derivation of the transition probabilities for the Markov TLA structure.- 4.4.3.1 Formalization.- 4.4.3.2 Additional Properties of the Learning System.- 4.5 Characterizing Convergence Times for the Markov Chain Model.- 4.5.1 Some Transition Matrices and Their Convergence Curves.- 4.5.2 Absorption Times.- 4.5.3 Eigenvalue Rates of Convergence.- 4.5.3.1 Eigenvalues and Eigenvectors.- 4.5.3.2 Representation of Tk.- 4.5.3.3 Initial Conditions and Limiting Distributions.- 4.5.3.4 Rate of Convergence.- 4.5.3.5 Transition Matrix Recipes:.- 4.6 Exploring Other Points.- 4.6.1 Changing the Algorithm.- 4.6.2 Distributional Assumptions.- 4.6.3 Natural Distributions-CHILDES COORPUS.- 4.7 Batch Learning Upper and Lower Bounds: An Aside.- 4.8 Conclusions, Open Questions, and Future Directions.- 4-A Unembedded Sentences For Parametric Grammars.- 4-B Memoryless Algorithms and Markov Chains.- 4-C Proof of Learnability Theorem.- 4-C.1 Markov state terminology.- 4-C.2 Canonical Decomposition.- 4-D Formal Proof.- 5. Language Change.- 5.1 Introduction.- 5.2 Language Change in Parametric Systems.- 5.3 Example 1: A Three Parameter System.- 5.3.1 Starting with Homogeneous Populations:.- 5.3.1.1 A = TLA; Pi = Uniform; Finite Sample = 128.- 5.3.1.2 A = Greedy, No S.V.; Pi = Uniform; Finite Sample = 128.- 5.3.1.3 A = a) R.W. b) S. V. only; Pi = Uniform; Finite Sample = 128.- 5.3.1.4 Rates of Change.- 5.3.2 Non-homogeneous Populations: Phase-Space Plots.- 5.3.2.1 Phase-Space Plots: Grammatical Trajectories.- 5.3.2.2 Issues of Stability.- 5.4 Example 2: The Case of Modern French:.- 5.4.1 The Parametric Subspace and Data.- 5.4.2 The Case of Diachronie Syntax Change in French.- 5.4.3 Some Dynamical System Simulations.- 5.4.3.1 Homogeneous Populations [Initial-Old French].- 5.4.3.2 Heterogeneous Populations (Mixtures).- 5.5 Conclusions.- 6. Conclusions.- 6.1 Emergent Themes.- 6.2 Extensions.- 6.3 A Concluding Note.- References.