Formalizing Triggers: A Learning Model for Finite Spaces
MASSACHUSETTS INST OF TECH CAMBRIDGE ARTIFICIAL INTELLIGENCE LAB
Pagination or Media Count:
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 GWs central convergence proof, a list of problem states in addition to local maxima, and batch and PAC-style learning bounds for the model.
- Statistics and Probability