Computational Linguistics: Slides (Kartei)

74 Karteikarten

• 1
  History of CL

  - 1950s: First experiments in mechanical translation, 10 ...
• 2
  Levels of linguistic description

  # Pronunciation model # Morphological rules # Lexicon and ...
• 3
  Examples for artificial languages

  - dates - license plates - chemistry formula - mathematical ...
• 4
  Formal language

  - A formal language is a subset {$ A \subseteq \Sigma* $} - ...
• 5
  Properties of concatenation

  - associative - neutral element {$ \epsilon $} - length ...
• 6
  Kleene closure *

  - The set of all finite concatenations of strings from A ...
• 7
  Definition of a finite language

  - Extensional definition - Complete listing
• 8
  Definition of an infinite language

  - Intensional definition - a) Algorithm that generates all ...
• 9
  Chomsky hierarchy

  # Type 0: Algorithmic languages - Turing machines, rewrite ...
• 10
  PCRE in the Chomsky hierarchy

  - Can't be classified - Some features of context-sensitive ...
• 11
  Minimal requirements on grammar formalism

  - includes all finite languages (extensional definition) - ...
• 12
  PCRE: Non-capturing parenthesis

  (?: ... )
• 13
  Compact vs. basic notation RE

  - {$ \{a\} = a $} - {$ \cup = | $} - {$ * = * $} - {$ \circ ...
• 14
  PCRE: Escape sequences for special character sets

  - \w word character (alphanumeric and underscore) - \W not ...
• 15
  PCRE: Anchors

  - ^ start of string - $ end of string - \b word boundary - ...
• 16
  PCRE: ^a+|b+$

  Matches any string that starts with a's or ends with b's
• 17
  Python extension for PCRE: Named groups

  - (?<name>[A-Z][a-z]+) - Substitution with \g<age> - ...
• 18
  PCRE: Lookahead and lookbehind

  - lookahead (?=...) tests whether ... would match at this ...
• 19
  Brzozowski algorithm

  Backward determinisation followed by forward ...
• 20
  Finite-state transducer

  - FSA that maps input to output symbols - FSA over the ...
• 21
  feasible pair

  - Any pair label found in the FSP - All the possible symbol ...
• 22
  default pair

  - a->a - leaves symbol unchanged - FSA is equivalent to FST ...
• 23
  insertion, deletion and eps-transition

  - Insertion: {$ epsilon $} -> b - Deletion: a -> {$ epsilon ...
• 24
  Properties of FST

  - "Special" FSA -> known properties - Closed under union, ...
• 25
  Sequential transducer

  - "input-deterministic" - Sequential FST cannot map to ...
• 26
  Are FST closed under intersection?

  - Yes ... as a FSA over the pair alphaet {$ \Sigma x \Gamma ...
• 27
  FST compositions

  - FST can be cascaded - T2 applied to the output of T1 - ...
• 28
  Inflectional morphology

  - Still the "same" word & syntactic category - Encodes ...
• 29
  Derivational word formation

  - Creates new words with different (modified) meaning - ...
• 30
  Compounding

  - Creates new words - Same syntactic category as head
• 31
  Types of morphemes

  - Stems (roots) - Derivational affixes (suffix, prefix, ...
• 32
  Goal of morphological parsing

  - Mapping: surface forms <-> grammatical words - ...
• 33
  Disadvantage of naive FST approach for plural FST, solution

  - Separate lists of regular noun stems for -s and -es (can ...
• 34
  Two-level morphology

  http://www.mindpicnic.de/media/img/user/andreas-70616-bild6. ...
• 35
  Surface mapping: Lexical mapping for e-epenthesis

  # Replace -s plural morph by -es if root ends in sibilant ...
• 36
  Rewrite rules

  - Surface mapping can be written concisely in the form of ...
• 37
  Why context-free grammars?

  - Regular expressions inadequate to characterize syntax of ...
• 38
  Ingredients for a context-free grammar

  - Terminal symbols {$ \Sigma $} - Nonterminals (variables) ...
• 39
  Derivations vs. parse trees

  - Many different derivations lead to the same parse tree ...
• 40
  Context-free languages

  - All formal languages that can be generated by a CFG - ...
• 41
  Formal equivalency of grammars

  - Describe the set of strings - Even if two different ...
• 42
  Why normal forms for CFGs?

  - Always possible to find an equivalent CFG ... - Without ...
• 43
  Chomsky normal form (CNF)

  - A -> B C - A -> {$ \alpha $} - S -> {$ \epsilon $} - ...
• 44
  Greibach normal form (GNF)

  - A -> {$ \alpha B_{1} ... B_{n} $} - Useful for formal ...
• 45
  Top-down parsing

  - Build parse tree from top (start symbol) - ...
• 46
  Bottom-up parsing

  - Build parse tree from bottom (lexical layer) - ...
• 47
  The recursive-descent parser

  - Generates all parse trees licensed by grammar and matches ...
• 48
  Problems of recursive-descent parsing

  - Left-recursive structures (infinite loop) - Takes many ...
• 49
  Recursive descent: Avoiding recursion traps

  - Re-ordering phrase structure rules may help (only when ...
• 50
  The shift-reduce parser

  - Bottom-up parser - Identifies possible constituents and ...
• 51
  Problems of shift-reduce parsing

  - Bottom-up parsers hypthesize many partial analyses that ...
• 52
  Advantages of CNF

  - Separation of lexical layer (terminal symbols) from ...
• 53
  Remaining problems, even with CNF

  - Repeated re-analysis in backtracking - Ambiguity: ...
• 54
  Dynamic programming

  - Space/time trade-off - Used to avoid re-analysis of ...
• 55
  Chart parsing

  - Chart stores intermediate results: partial analyses (or ...
• 56
  Algorithmic properties of languages ...

  http://www.mindpicnic.de/media/img/user/andreas-93682-bild8. ...
• 57
  Closure properties of languages ...

  http://www.mindpicnic.de/media/img/user/andreas-84850-bild10 ...
• 58
  Pumping Lemma

  Shows that a language cannot be regular # Assume that ...
• 59
  Appropriate grammar formalism for natural languages?

  - English: Unlimited recursion possible (in principle) -> ...
• 60
  Proposed grammar formalisms for natural language

  - indexed grammars - tree-adjoining grammars - categorial ...
• 61
  Support for strong generativism

  - = grammar explains not only formal structure of language ...
• 62
  Advantages of CFG

  - Build "appropriate" structural analyses - Recursion & ...
• 63
  Problems and shortcomings

  - Cannot account for all human languages - Modelling free ...
• 64
  subcategorisation

  - Split syntactic and phrasal nonterminals into more ...
• 65
  Underspecification

  - Redundant lexical entries - "leave" can be V_1sg, V_2sg, ...
• 66
  Which problems do feature bundles solve?

  - New subcategories for different phenomena multiplied out ...
• 67
  Feature bundles

  - Decompose syntactic subcategories into bundles of ...
• 68
  Phrase-structure rules, path notation

  http://www.mindpicnic.de/media/img/user/andreas-85066-bild11 ...
• 69
  Phrase-structure rules, graph notation

  http://www.mindpicnic.de/media/img/user/andreas-39791-bild12 ...
• 70
  Phrase-structure rules, attribute-value matrix (AVM)

  http://www.mindpicnic.de/media/img/user/andreas-24882-bild13 ...
• 71
  Unification

  - Feature bundles are not matched by equality but by ...
• 72
  Subsumption

  - Feature bundle A subsumes feature bundle B iff B contains ...
• 73
  Feature structures

  Feature bundles that allow complex values: Other feature ...
• 74
  Reentrancy

  - Feature structures with shared substructures are called ...