Two Algorithms for Learning the Parameters of Stochastic Context-Free Grammars

Abstract

Stochastic context-free grammars (SCFGs) are often used to represent the syntax of natural languages. Most algorithms for learning them require storage and repeated processing of a sentence corpus. The memory and computational demands of such algorithms are illsuited for embedded agents such as a mobile robot. Two algorithms are presented that incrementally learn the parameters of stochastic context-free grammars as sentences are observed. Both algorithms require a fixed amount of space regardless of the number of sentence observations. Despite using less information than the inside-outside algorithm, the algorithms perform almost as well.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jan 01, 2001
Accession Number
ADA459920

Entities

People

  • Brent Heeringa
  • Tim Oates

Organizations

  • University of Massachusetts Amherst

Tags

Communities of Interest

  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Algorithms
  • Artificial Intelligence
  • Computational Complexity
  • Computer Science
  • Computers
  • Context Free Grammars
  • Electrical Engineering
  • Grammars
  • Histograms
  • Iterations
  • Language
  • Learning
  • Natural Languages
  • Observation
  • Probability
  • Standards
  • Statistics

Fields of Study

  • Computer science

Readers

  • Computational Linguistics
  • Parallel and Distributed Computing.
  • Statistical inference.

Technology Areas

  • AI & ML
  • AI & ML - Machine Learning Algorithms
  • AI & ML - Machine Translation
  • Autonomy
  • Space
  • Space - Spacecraft Maneuvers