Formalizing Triggers: A Learning Model for Finite Spaces

Abstract

In a recent seminal paper, Gibson and Wexler (1993) take important steps to formalizing the notion of language teaming in a (finite) space whose grammars are characterized by a finite number of parameters. They introduce the Triggering Learning Algorithm (TLA) and show that even in finite space convergence may be a problem due to local maxima. In this paper we explicitly formalize learning in finite parameter space as a Markov structure whose states are parameter settings. We show that this captures the dynamics of TLA completely and allows us to explicitly compute the rates of convergence for TLA and other variants of TLA e.g. random walk. Also included in the paper are a corrected version of GW's central convergence proof, a list of 'problem states' in addition to local maxima, and batch and PAC-style learning bounds for the model.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Nov 01, 1993
Accession Number
ADA276776

Entities

People

  • Partha Niyogi
  • Robert C. Berwick

Organizations

  • Massachusetts Institute of Technology

Tags

Communities of Interest

  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Absorption
  • Algorithms
  • Artificial Intelligence
  • Bits
  • Computational Complexity
  • Computer Programs
  • Convergence
  • Dynamics
  • Language
  • Markov Chains
  • Markov Processes
  • Numbers
  • Probability
  • Probability Distributions
  • Random Variables
  • Random Walk
  • Stochastic Processes

Fields of Study

  • Mathematics

Readers

  • Enterprise Information Systems Architecture and Joint Command Capability Interoperability Support.
  • Linear Algebra
  • Neural Network Machine Learning.

Technology Areas

  • Space