Linguistics 581

Scope and History of Computational Linguistics

Field of Computational Linguistics

Practical Applications

task-oriented speech or language systems

Theoretical Applications

Theoretical specification tool
Theoretical modeling

Practical Application Areas

1. System Functionality
   • Information-accessing Systems
   • Task-oriented Systems
   • Educational Systems
   • Translation Systems
   • Applications that involve knowledge of text or language structure
   • Psychoanalysis
2. System Modality
   • Text
     • Typed input
     • Online input
   • Speech
     • Spoken input
     • Recorded input
   • Multi-modal (primarily visual +)
     • Dynamic display or real time video
     • Online images or video
3. System Initiatives
   • Analysis
   • Generation

Examples of practical applications

1. Information-accessing Systems
   1. Database query
      • Bill Woods Moonrocks system (70s)
      • HP NL system (80s)
      • NLI Intellect System (Ginsparg, 90s)
      • Microsoft NL DB toolkit
   2. Information Retrieval (IR)
      • Document retrieval
      • Web search
        Why this is not just simple document retrieval: Google
      • Text segmentation
   3. Information Extraction (IE)
      • Text Summarization
        • Find the most important paragraphs or sentences
        • Try to generate an abstract
      • Document database query
        • Find the query-relevant paragraph or cluster of sentences
        • Try to generate an answer
      • Online help system query
2. Task-oriented Systems
   1. Online desktop
   2. Text editor
   3. Unix shell
   4. Robot
   5. Simulated armed forces (user=commander)
   6. Kitchen appliances
3. Educational Systems
   1. Intelligent Tutors
      • Language tutors
      • Reading tutors
      • Other subjects
   2. Student Modeling
      • Behavior, skill, and preference modeling
      • Error analysis
4. Translation Systems
   1. MT systems
   2. Translator's assistant's
5. Applications that involve knowledge of text or language structure
   • Text editors
   • Text formatters
     Knuth's hyphenation algorithm in TeX
     The lesson of hyphenation for linguists and computational linguists: Sometimes very complicated programs are required do things that are apparently very simple.
   • Text segmenters
   • Algorithms for reading machine-readable dictionaries
   • Netscape's "What's Related" Button
6. Psychoanalysis (Liza)
   A new Liza application on AOL
   The lesson of Liza for linguists and computational linguists: Sometimes very simple programs can do things that are apparently very complicated.

Reasons for the explosion of Computational linguistics

1. Success of Speech recognition
2. Increase in computing power and storage capacity of machines
3. Availability of online text and speech resources in unprecedented quantities
4. Success of statistical methods
5. World-wide web
6. Increasing demand for translation
7. Availability of venture capital

Theoretical Applications

• Theory-specification tool
  1. Zellig-Harris Transformational Grammar and the Linguistic String Project (Transdformational and Discourse Analysis Project, Sager, NYU String Grammar project)
  2. Chomskyan Transformational Grammars and ATNs (Woods, Moonrock system)
  3. Lexicalist Theories and Unification Grammar
     • Lexical Functional Grammar (LFG, Ron Kaplan, Xerox PARC system)
     • Generalized Phrase Structure Grammar (GPSG, HP system)
     • Head-Driven Phrase Structure Grammar (HPSG, HP system, Verbmobil English grammar at Stanford)
  4. Hallidayan Systemic Grammar and Functional Unification Grammar (Terry Winograd, Martin Kay)
  5. Hallidayan Systemic Grammar and Nigel (ISI)
• Theoretical modeling
  1. Processing models
     • Syntax
       • Garden path models (Bever 1970, McDonald 1993 and Jurafsky 1996)
         • The horse raced past the barn fell.
         • The complex houses married and single students and their families.
         • The student forgot the solution was in the back of the book.
       • Parse preference models (attachment preferences modeled; Pereira 1985, models "minimal attachment" and "right association" of Kimball 1973)
       • "Shallow" parsing (finite-state) models of human processing (Church 1980, Ramshaw and Marcus 1995, Argammom, et al. 1998, Munoz et al. 1999, Chapter 10, our text)
     • Semantics
       The astronomer married the star.
       The movie director married a star.(Reder 1983, Uszkoreit 1990)
     • Speech recognition systems as crude phonological processing models
  2. Acquisition models
     • Unsupervised learning systems
       1. Segmentation (Michael Brent)
       2. Derivational Morphology (Watkinson and Manandhar)
     • PDP models
  3. Language change models
     Briscoe 2000: biased learning creates linguistic change

  ---

  History
  1. Foundational insights (40s and 50s)
     • McCulloch-Pitts neuron: a simplified computational model of a neuron
     • Shannon (1948): automata for language, incorporating probablistic models
     • Chomsky (1956): formal language theory
     • Sound spectrograph (Koenig et al. 1946): foundation for instrumental phonetics.
     • First machine speech recognizers (Bell Labs, Davis et al. 1952)
     • Shannon-Weaver information theory: Noisy channel model
  2. Two camps (57-70)
     • AI
       • Beginnings of Artifical Intelligence as a field (John McCarthy, Marvin Minsky, Clause Shannon, Nathaniel Rochester)
       • Newell and Simon Logic Theorist and Problem Solver. computable models of reasoning and logic
         • Subjects speak aloud as they solve problems
         • Problem solving modeled with a production-system where the productions (or reasoning steps) correspond to the steps human reasoners took for those kinds of problems.
       • George Miller and Donald Broadbent: importing computational ideas into psychology.
       • Bayesian method and optical character recognition: Using probabilistic methods on recognition problems (see Chapter 5, history section, our text)
     • Zellig Harris project
     • Brown Corpus
  3. Four paradigms (70-83)
     • Stochastic: HMMs in speech recognition (Jelinek, Bahl and Mercer at IBM)
     • Logic-based programming Prolog:
       • Q-systems aand metapmorphosi grammars (Colmerauer)
       • Prolog, Definite Clause Grmmars (Pereira and Warren 1980)
       • Unification grammar (Kay, Bresnan and Kaplan)
     • Natural language understanding(Winograd, serious attention to semantics)
       • Winograd SHRDLU, blocks world
       • Yale school: Scripts, plans, goals (Schank and Abelson, Wilensky, Lehnert). Story and text understanding.
     • Discourse-modeling (Grosz, Sidner, Perrault, Allen, Cohen). Discourse as plans guided by intentions and beliefs. Communicative acts as steps in plans.
  4. Empiricism and Finite-state models redux (83-99)
     • Finite-state models
       • phonology and morphology (Kaplan and Kay 1981, Koskenniemi, Karttunen)
       • syntax (Church 1980)
     • Probabilistic models
       • Speech recognition work at IBM
       • Part of speech tagging (history section, chapter 8)
         • utter, direct: adj, v
         • walk, pilot, sneer, help: N,V
         • hard: adj, adv
       • Probabilistic parsing (history section, chapter 12)
  5. The field comes together (94-99)
     • Spread of probabilistic methods to all kinds of problems
     • Commercial ventures using speech, some NLP
     • The web
     • Some lessened emphasis on theoretical work

  ---

  Kinds of linguistic knowledge/Areas of Speech and Language Processing
  1. Phonetics and Phonology
  2. Orthography and Spelling
  3. Morphology
  4. Syntax
  5. Lexical Semantics
  6. Compositional semantics
  7. Pragmatics: Language involved in plans and goals
  8. Discourse: Coherence relations [text cohesion: discourse relations, anaphoric relations between sentences]