VL13 IL1 §

Question §

Notes §

Flashcards §

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:
  • $P(T)={\prod }_{n\in T}p(r(n))$

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 §

• 📣 Sentence
  • ⛓️ Clause
    • ⛓️ Phrase
      • 🈁 Word
        • 🦋 Morpheme

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 §

• 🗣 Natural language != mathematics
• problems of 🌙 Symbolic (deep) processing

State the time complexity for each type of Automaton#card §

• Finite State: n (linear)
• Pushdown: $n^3$ (cubic)
• Linear-bounded: $e^n$ (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
  • 🧑 BERT