00 Overview

Question 1

Sequence and grammar

Answer 1

Sequences:

• Probabilities over strings: n-gram models: Linear and surface oriented
• Sequence classification: HMMs add one layer of abstraction; class labels as hidden variables. But still only linear

Grammar; adds hierarchical structure

• Shift focus from “sequences” to “sentences”
• Identifying underlying structure using formal rules
  
  • Declarative aspect: formal grammar
  • Procedural aspect: parsing strategy
• Learn probability distribution over the rules for scoring trees

Question 2

We have been doing data-driven learning by counting observations in what contexts?

Answer 2

• feature vectors in semantic spaces; bag-of-words, etc.
• previous n-1 words in n-gram models
• previous n-1 states in HMMs
• local sub-trees in PCFGs

Question 3

Vector space models

Answer 3

• Data representation based on a spatial metaphor
• Objects modeled as feature vectors positioned in a coordinate system
• Semantic spaces = VS for distributional lexical semantics
• Some issues:
  
  • Usage = meaning? (The distributional hypothesis)
  • How do we define context / features? (BoW, n-grams, etc.)
  • Text normalization (lemmatization, stemming, etc.)
  • How do we measure similarity? Distance / proximity metrics. (Euclidean distance, cosine, dot-product, etc.)
  • Length-normalization (ways to deal with frequency effects / length-bias)
  • High-dimensional sparse vectors (i.e. few active features; consequences for low-level choice of data structure, etc.)

Question 4

Classification

Answer 4

Supervised learning from labeled training data.

Given data annotated with predefinded class labels, learn to predict membership for new/unseen objects.

Question 5

Cluster analysis

Answer 5

Unsupervised learning from unlabeled data.
􏰀 Automatically forming groups of similar objects.
􏰀 No predefined classes; we only specify the similarity measure.

Question 6

Issues with categorization tasks

Answer 6

• Measuring similarity
• Representing classes (e.g. exemplar-based vs. centroid-based)
• Representing class membership (hard vs. soft)

Question 7

Examples of vector space classifiers

Answer 7

Rocchio vs. kNN

Question 8

Differences between Rocchio and kNN

Answer 8

• Centroid- vs exemplar-based class representation
• Linear vs non-linear decision boundaries
• Assumptions about the distribution within the class
• Complexity in training vs complexity in prediction

Question 9

Evaluation of classifiers

Answer 9

• Accuracy, precision, recall and F-score
• Multi-class evaluation: Micro-/macro-averaging

Question 10

Types of clustering

Answer 10

• Flat /partitional clustering
• Hierarchical clustering
  
  • Agglomerative clustering (bottom-up)
  • Divisive clustering (top-down)

Question 11

Flat clustering algorithm

Answer 11

• Example: k-Means.
• Partitioning viewed as an optimization problem:
• 􏰀Minimize the within-cluster sum of squares.
• Approximated by iteratively improving on some initial partition.
• Issues: initialization / seeding, non-determinism, sensitivity to outliers, termination criterion, specifying k, specifying the similarity function.

Question 12

Agglomerative clustering

Answer 12

• Bottom-up hierarchical clustering
• Resulting in a set of nested partitions, often visualized as a dendrogram. 􏰀
• Issues:
  
  • Linkage criterions — how to measure inter-cluster similarity:
    
    • Single, Complete, Centroid, or Average Linkage
  • Cutting the tree

Question 13

Divisive clustering

Answer 13

• Top-down hierarchical clustering
• Generates the tree by iteratively applying a flat clustering method.

Question 14

Structured Probabilistic Models

Answer 14

• Switching from a geometric view to a probability distribution view.
• Model the probability that elements (words, labels) are in a particular configuration.
• We looked at many of the same concepts over structures that were linear or hierarchical

Question 15

What have we been modelling with Structured Probabilistic Models?

Answer 15

Linear

• With string is more likely?
• Which tag sequence is most likely?

Hierarchical

• Which tree structure is most likely?

Question 16

Structured Probabilistic Models: Types

Answer 16

Linear

• n-gram language models
  
  • Chain rule combines conditional probabilities to model context
  • Markov assumption allows us to limit the length of context
• Hidden Markov Model
  
  • addad a hidden layer of abstraction: PoS tags
  • also uses the chain rule with the Markov assumption

Hierarchical

• (Probabilistic) Context-Free Grammars (PCFGs)
  
  • Hidden layer of abstraction: trees
  • Chain rule over (P)CFG rules

Question 17

n-gram language models

Answer 17

n-gram language models

• Linear Structured Probabilistic Model
• Chain rule combines conditional probabilities to model context
• Markov assumption allows us to limit the length of context

Question 18

Hidden Markov Model

Answer 18

• Linear Structured Probabilistic Model
• A hidden layer of abstraction: PoS tags
• Uses the chain rule with the Markov assumption

Question 19

PCFGs

Answer 19

(Probabilistic) Context-Free Grammars

• Hierarchical Structured Probabilistic Model
• Hidden layer of abstraction: trees
• Chain rule over (P)CFG rules:

Question 20

Maximum Likelihood Estimation

Answer 20

Question 21

HMMs can be used to:

Answer 21

• calculate the probability of a string
• find the most likely state sequence for a particular observation sequence

Question 22

CFGs can be used to:

Answer 22

• A CFG can recognise strings that are a valid part of the defined language.
• A PCFG can calculate the probability of a tree (where the sentence is encoded by the leaves).

Question 23

n-gram models can be used to

Answer 23

n-gram models can be used to calculate the probability of a string

Question 24

When to use the Viterbi algorithm?

Answer 24

• HMM: Efficiently find the most likely state sequence
• PCFG: Efficiently find the most likely parse tree

Question 25

When to use the Forward algorithm?

Answer 25

HMM: To efficiently calculate the probability of the obervation sequence

Question 26

When to use chart parsing?

Answer 26

To efficiently explore the parse tree search space

Question 27

Dynamic programming: What are our sub-problems?

Answer 27

* HMM: Our sub-problems are prefixes to our full sequence * (P)CFG parsing: Our subproblems are sub-trees which cover sub-spans of our input

Question 28

Evaluation

Answer 28

Linear * **Tag accuracy** is the most common evaluation metric for POS tagging, since usually the number of words being tagged is fixed. Hierarchical * **Coverage** is a measure of how well a CFG models the full range of the language it is designed for. * The **ParsEval** metric evaluates parser accuracy by calculating the **precision**, **recall** and **F1** score over labelled constituents.

Question 29

Tag accuracy

Answer 29

Tag accuracy is the most common evaluation metric for POS tagging, since usually the number of words being tagged is fixed.

Question 30

Coverage

Answer 30

Coverage is a measure of how well a CFG models the full range of the language it is designed for.

Question 31

ParsEval

Answer 31

The ParsEval metric evaluates parser accuracy by calculating the precision, recall and F1 score over labelled constituents.