447 Final Flashcards

Front 1

What are grammar formalisms?

Back 1

The rules of a language, a precise way to detail and describe the structure of sentences.

Front 2

What are specific grammars?

Back 2

Implementations of a particular grammar formalism

Front 3

Types of verbs?

Back 3

1) Intransitive Verbs: Takes only a subject (sleep)

2) Transitive Verbs: Takes one direct object (eat)

3) Ditransitive Verbs: Takes one indirect object (give)

Front 4

Why can't FSA describe grammar?

Back 4

FSA's cannot generate a hierarchical structure that suits most grammars.

Front 5

Difference between strong and weak generative capacity?

Back 5

Weak generative capacity: Only generating strings that fit a language.

Strong generative capacity: Also concerns with generating the right structure that fit a language

Front 6

Use of CFG's?

Back 6

CFG's can capture recursion. However, they are not able to capture bounded recursion (only embed one or two relative causes). They are equivalent to pushdown automata (PDA's).

Front 7

DG?

Back 7

Dependency Grammar: describes the structured of sentences as a directed acyclic graph (words = nodes, dependencies = edges).

Front 8

Constituent?

Back 8

A constituent is a phrase that acts as a single unit.

Front 9

How to find constituents?

Back 9

1) Substitution Test

2) Movement Test

3) Answer Test -- used as an answer

Front 10

Arguments vs Adjuncts

Back 10

Arguments: Mandatory

Adjuncts: Optional

Front 11

Chomsky Normal Form

Back 11

Can only have 2 kinds of right-had sides:

1) 2 Nonterminals

2) 1 Terminal

Front 12

CKY Algorithm

Back 12

O(n3|G|) dynamic programming algorithm to find the POS tagging of the a sentence

Front 13

Number of Parse Trees in CKY

Back 13

# of Parse Trees #(VP --> V NP) = #(V)#(NP)

Then add up all the possible combinations

Front 14

Probabilistic Context-Free Grammar

Back 14

A CFG with probabilities associated with each transaction. Each possible left hand side has to all equate to 1

Front 15

PCFG Modeling

Back 15

It makes independence assumptions --> The flatter the better.

Front 16

Bias/Variance Tradeoff

Back 16

A probability model has low bias if it makes few independence assumptions, but this leads to a higher variance which is a poor estimate of the data.

Front 17

Parser Evaluation: Evaluation of phrase-structure trees

Back 17

Precision: What percentage of retrieved documents are relevant to the query?

P = TP/(TP + FN)

Recall: What percentage of the relevant documents were retrieved?

R = TP/(TP + FP)

F-Measure: Harmonic Mean

Front 18

Penn Treebank

Back 18

The Penn Treebank was the first publicly available POS annotated corpus

Front 19

Ways to improve performance in PFCG

Back 19

1) Change the internal grammar

2) Change the probability model

Front 20

Parent Transformation

Back 20

PCFG assume the expansion of any nonterminal is independent of its parent. We can change the grammar by adding the name of the parent node to each nonterminal

Front 21

Lexicalization with PCFG

Back 21

PFGs cant distinguish between "eat sushi with chopsticks" and "eat sushi with tuna", therefore we need to take into account head words.

Front 22

Dependency Grammer

Back 22

Word-word dependencies are a component of many (most/all) grammar formalisms.

Dependency grammar assumes that syntactic structure consists only of dependences

Purely descriptive

Front 23

Kinds of dependencies

Back 23

Head-argument: eat sushi

Head-modifier: fresh sushi

Head-specifier: the sushi

Coordination: Sushi and Sashimi

Front 24

Dependency

Back 24

There is a syntactic relation between a head H and a dependent D in a construction C if:

The head H determines the syntactic category of the construction C

The head H determines the semantic category of the construction C; D gives semantic specification

The H is obligatory.

The head selects D and determines whether D is obligatory or not.

Front 25

Prague Dependency Treebank

Back 25

3 levels of annotation:

Morphological

Surface-syntactic

Semantic

Front 26

Parsing Algorithms for DG

Back 26

1) Transition-based parsers

2) Graph-based parsers

Front 27

Transition-based parsing

Back 27

Transition based shift reduce parsing processes the sentences S w0w1...wn from left to right. It constructs a single tree.

Utilizes a stack, and a buffer to create arcs.

Front 28

Feature Structures

Back 28

List of features (= attributes), and values.

Represented as AVM (attribute value matrix)

Can be recursive

Can be used as a way to properly do constraints

Front 29

Grammar Formalisms

Back 29

Formalisms provide a language in which linguistic theories can be expressed and implemented.

Formalisms define elementary objects and recursive operations which generate complex objects from simple objects

Front 30

Mildly context-sensitive gramars

Back 30

Contains all context-free grammars/languages

Can be parsed in polynomial time (On6)

Strong generative capacity: capture certain kinds of dependences: nested and cross serial

Front 31

Tree-Adjoining Grammar (TAG)

Back 31

Tree-rewriting format that defines operations on trees (elementary objects = trees)

Is lexicalized by anchoring to another lexical item

Is mildly context sensitive

Front 32

Combinatory Categorial Grammar (CCG)

Back 32

Categories: specify subcat lists of words/constituents

Combinatory rules: specify how constituents can combine

Lexicon: Specifies which categories a word can have

Derivations: spell out process of combining constituents

Front 33

CCG Categories

Back 33

Simple (atomic) categories: NP, S, PP

Complex Categories (functions):

VP, intransitive verbs: S\NP

Transitive Verb: (S\NP)/NP

Adverbs: (S\NP)/(S/NP)

Prepositions:

((S\NP)\(S\NP))/NP

(NP/NP)/NP

PP/NP

Front 34

Function Application

Back 34

Forward Application: (S\NP)/NP NP => S\NP

Backward Application: (NP S\NP) => S

Front 35

Why is MT Difficult

Back 35

1) Correspondences

2) Lexical Divergences:

3) Syntactic divergences

Front 36

MT - Correspondences

Back 36

One to one,

One to Many/Many to One,

Many to Many

Reordering Required

Front 37

MT - Lexical Divergences

Back 37

Different senses of homonymous words generally have different translations (river bank, vs financial bank).

Different senses of polysemous words may also have different translations:

Front 38

MT - Lexical Specificity and Morphological Divergences

Back 38

Lexical Specificity:

German Kürbis = English pumpkin or squash

English brother = Chinese gege (older), didi (younger)

Morphological divergences:

un nouveau, une nouvelle, etc.

Front 39

MT - Syntactic Divergences

Back 39

Head-marking vs. Dependent-marking

Front 40

MT - Semantic Differences

Back 40

Peter swims vs Peter is swimming

Front 41

Direct Translation

Back 41

1) Morphological Analysis of Source String

2) Lexical transfer (using a translation dictionary)

3) Local reordering

4) Morphology

Front 42

Limits of direct translation:

Back 42

Phrasal reordering

Front 43

Syntactic Transfer

Back 43

Requires a syntactic parse of the source language, followed by reordering of the tree. Moves the words around to work.

Front 44

Interlingua Approach

Back 44

Based on the assumption there is a common representation for a phrase in all languages, just have to find that and say that in the language.

Front 45

Noisy Channel Model

Back 45

E = argmax P(F|E) X P(E)

P(F|E) = Translation model, captures faithful-ness of the translation

P(E) = Language Model, captures the fluency of the translation

Used to translate

Front 46

Translation Probability

Back 46

Use a phrase table and phrase alignment on a parallel corpus to get the counts

Front 47

IBM Model 1

Back 47

Based on the noisy channel, word-based translation models

1) Generates length

2) Generate an alignment

3) Generate the words of the translation

Front 48

IBM Model 1 Parameters

Back 48

Length Probability: P(m|n): Probability of generating a source sentence of length m given a target sentence of length n?

Alignment Probability: P( A|m,n)

Translation Probability: P(fj="lac"|aj = i, ei="lake")

Front 49

IBM Model 1 EM

Back 49

Expectation-Maximization (EM)

E: Go through training data to compute counts

M: Use the expected counts to compute a new model

Check for convergence

Front 50

Phrase-based MT

Back 50

Fundamental units of translation are phrases.

Splits target sentence deterministically into phrases and translate each phrase. Reorder foreign phrases with distortion probability.

Front 51

Phrase-based MT - Finding the best translation

Back 51

Since there is an exponential number of possible translations, we can use a heuristic-search algorithm.

Score the partial translation based on the cost.

Front 52

MT Evaluation

Back 52

Automatic: BLEU - Uses n-gram precision to grade a translation

Manual: Use a human to track fluency and adequacy.

Front 53

Semantics

Back 53

Lexical Semantics: meaning of a word

Compositional Semantics: meaning of a sentence

Discourse Semantics: meaning of a longer piece of text

Front 54

Nouns/Verbs

Back 54

Nouns: Refers to entities in the world

Verbs: define n-ary predicates: depending on the arguments they take, the results can be true or false

Front 55

Sentences

Back 55

Declarative Sentences: can be true or false depending on the state of the world.

Consists of a verb + 1 or more NP's

Front 56

Principle of compositionally (Frege):

Back 56

The meaning of an expression depends on the meaning of its parts and how they are put together.

Front 57

Predicate logic expressions/ First-order predicate language (FOL)

Back 57

Terms: refers to entities

Predicates: relations between entitites

Formulas: Can be true or false

Front 58

Predicate Formulas

Back 58

Atomic Formulas:

book(x), eat(x, y)

Complex Formulas involve

1) Negation

2) Connectives

3) Quantifiers

Front 59

Limitations of FOL

Back 59

Tense, Aspect, Modals, Quantifiers

Front 60

lambda-expressions

Back 60

Use lambda expressions along with CCG's to construct sentences

N = lambda z, chef(z)

Front 61

Quantifier Scope Ambiguity

Back 61

"Every chef cooks a meal": For every chef, there is a meal which he cooks or There is some meal which every chef cooks

Front 62

Thematic Roles

Back 62

Verbs describe events or states.

Thematic roles refer to participants of these events:

Agent: Person who performs the action

Patient: Entity in which the action was performed on

Tool: What was used to perform the action

Front 63

Proposition Bank (PropBank)

Back 63

PropBank information classifies arguments needed for verbs.

Front 64

Diathesis Alternations

Back 64

Active/passive alternation

Causative alternation

Dative alternation

Locative alternation

Front 65

Discourse

Back 65

Discourse is a linguistic unit that consists of multiple sentences.

Speaker describes some state of the world

Speaker attempts to get the listener to construct a similar model of the situation

Front 66

Entity-based coherence

Back 66

How we refer to entities influenced how coherent a discourse is.

Front 67

Centering Theory

Back 67

A linguistic theory of entity-based coherence and salience that predicts which entities are salient at any point during a discourse. Also predicts whether a discourse in entity-coherent based on referring theory. It is not a computational model

Front 68

Coherence relations

Back 68

A sentence is coherent if it provides explanation to context.

Front 69

Rhetorical Structure Theory (RST)

Back 69

Describes coherence relations between utterances.

It defines a set of rhetorical relations:

Evidence, Elaboration, Attribution, Contrast, List

Hold a relation between a nucleus and a satellite

Some impose constraints

Front 70

How to understand discourse

Back 70

1) Coreference Resolution: "the cafe" = "Bevande"

2) Identifying discourse relations: "He wanted to buy lunch" is the reason "John went to Bevande"

Front 71

Discourse Models

Back 71

Explicit Representation of the events and entities that a discourse talks about and the relations between them.

Captures: Physical Entities, Events, States, Temporal Relations, Rhetorical Relations

Front 72

Referring expression ("this book")

Co-reference

Back 72

Refers to some entity which is called the referent

Two referring expressions that refer to the same entity

Front 73

Indefinite NPs

Back 73

Indefinites usually introduce a new discourse entity. They can refer to a specific entity or not.

No determiner,

The indefinite determiner

Numeral

Indefinite quantifiers

Indefinite this

Front 74

Definite NPs

Back 74

Definite NPs refer to an identifiable entity (previously mentioned or not)

Front 75

Information Status

Back 75

Hearer-new vs Hearer-old: Assumes entity is (un)known to the listener.

Discourse-new vs. Discourse-old: Speaker introduces new entity into the discourse

Front 76

Coref as binary classifier

Back 76

Represent each NP-NP pair (+ context) as a feature vector.

Pass through the text and for each NP go through the previous sentences to find the best antecedent NP

Front 77

Features for Coref Resolution

Back 77

Do the 2 NPs have the same head noun?

Do they contain the same modifier?

Does the gender and number match?

Is one NP a hypernym/synonym of the other?

Are both NP's named entities of the same time.

Front 78

Evaluation of Coref resolution:

Back 78

B-Cubed F-Score

Precision P: Co and To/Co

Recall: Co and To/To

F-measure: 2PR/(P+R)

Front 79

Natural Language Generation

Back 79

Automatic production of natural language text usually from underlying semantic representation

Front 80

NLG Architectures

Back 80

1) Text Planning: Content determination and discourser planning

2) Sentence Planning: Sentence aggregation, lexicaliztation and referring expression generation.

3) Linguistic Realization: Syntactic, morphological and orthographic processing

Front 81

NLG Tasks - Text Planning

Back 81

1. Content Determination: What information should be communicated.

2. Discourse Planning: How should the message be structured

Front 82

NLG Tasks - Sentence Planning

Back 82

3. Sentence Aggregation: Which messages should be combined into individual sentences?

4. Lexicalization: In which words should domain concepts be expressed.

5. Referring expression generation: How should entities be referred to?

Front 83

NLG Tasks - Linguistic Realization

Back 83

Linguistic Realization: Generate a grammar and orthographically formed text.

Front 84

Summarization

Back 84

"The process of distilling the most important information from a text to produce an abridged version for a particular task and user"

Front 85

Centroid-based content selection

Back 85

Which sentences are most central in a document?

A) Central Sentences = Salient/Informative sentences (contains many salient words)

B) Central Sentences = most similar to other s's in doc.

Front 86

RST-Based Summarization

Back 86

Use a discouse parser to identify rhetorical relations between sentences/clauses in a document.

This gives a discourse tree that defines a salience ranking

Front 87

Dialogue Manager

Back 87

Controls the architecture and structure of dialogue

1. FS

2. Frame Based

3. Information State

4. AI Planning

Front 88

Grounding

Back 88

Dialogue is a collective act performed by speaker and hearer

Common ground: set of things mutually believed by both speaker and hearer.

Front 89

NLP Pipeline

Back 89

1. Tokenizer/Segmenter: to identify words and sentences.

2. Morphological Analyzer/POS tagger: to identify the part of speech and structure of words.

3. Word Sense Disambiguation: To find the meaning of the words.

4. Syntactic/Semantic Parser: To obtain the structure and meaning of sentences.

5. Coreference resolution/discourse model: to keep track of the various entities and events mentioned.

Front 90

Core Problems of NLP

Back 90

Ambiguity: Natural Language is highly ambiguous

Coverage (Zipf's Law): Any NLP system will come across words that did not occur during training.

Front 91

Statistical Models for NLP

Back 91

Probabilistic Models (HMM, MEMM, CRFs, PCFGS)

Front 92

Deep Learning

Back 92

Neural networks with several hidden layers

Very impressive performanc gains in computer vision and speech recognition

Fast Computers have finally made it viable

Front 93

Challenges in Neural Networks for NLP

Back 93

Input is discrete, NN works best with continuous vectores.

Used in word embeddings and NL models

Front 94

NLG Architecture

Back 94

Goal

Text Planner

Sentence Planner

Linguistic Realizer

Surface Text