VL13 IL1




Explain Top-Down parsing#card

⬇️ Top-Down (= goal-driven)

  • Start at S and progressively replace left-hand sides with right hand sides that match the string

List 1/2 Problems of Top-Down parsing#card

  • Left recursion (= NT at left edge of left-hand side)
  • Ambiguity

Explain Bottom-Up parsing#card

🔼 Bottom-Up (= data-driven)

  • Start at word level, progressively replace strings that match right-hand sides with left-hand sides

List 1/3 Problems of Bottom-Up parsing#card

  • Left recursion
  • Ambiguity
  • BU: backtracking → lower ⚡️ Efficiency

Define Chart Parsing#card

= a parsing strategy suitable for ambiguous grammars, which works without backtracking

How does Chart Parsing work?#card

  • For each input word, record all possible parses
  • Build up candidate trees in a chart
  • onEnd: chart contains all possible parses

Define what the Early Algorithm is#card

= left-right, top-down 🧾 Chart parsing algorithm

Describe how the Early Algorithm works#card

  1. Generate predictions for input symbol
    • store all possible predictions in columns
  2. Scan predictions
    • for each column: check rule
    • if fulfilled: continue & update state → [symbol, state + 1]
  3. Complete predictions
    • Move cursor to next symbol & update symbol → [symbol + 1, state]
  4. Repeat, if has active prediction && has next input symbol

Define Probabilistic parsing#card

= a parsing strategy to find the most likely parse for ambiguous grammars using 🎲 Probability Theory

How does Probabilistic Parsing work?#card

  • Augment context free grammars with the 🎲 Probability for each rule
  • Calculate the overall probability P(T) of a parse T as the product of all the rules r probabilities:

List 1/2 problems of Probabilistic parsing#card

  • Independence assumption
  • Structural & lexical dependencies

Define what FOPC is#card

📕 Formal Language for expressing meaning through the use of statements that are built from atomic formulas

List 1/2 pro and 1/2 con of FOPC#card

  • 👍 easy & well understood
  • 👍 flexible, sufficient for most applications
  • 👎 representation of belief?
  • 👎 discourse resolution

List the Units of a Formal Grammar#card

Define Syntax#card

= the grammatical arrangement of words in sentences or morphemes in words

Define Syntax-driven semantic analysis#card

= 👯‍♂️ Semantic level analysis building on top of 🔠 Syntax level analysis

List 1/2 problems of syntax-driven semantic analysis#card

State the time complexity for each type of Automaton#card

  • Finite State: n (linear)
  • Pushdown: (cubic)
  • Linear-bounded: (exponential)
  • Turing machine: undecideable

List 2/4 Applications of NLE#card

  • Question-answering
    • IBM-Watson
  • dialogue systems, chatbots
  • text summarization
    • extractive
      • single document
      • query-based multi document
    • abstractive
      • sequence-to-sequence model
  • answer extraction