NLP Notes

GPU Usage Tips

• Don't use GPU Colab when not actively using GPUs to conserve resources.
• Start with a tiny dataset when building code, potentially using the CPU initially.
• HuggingFace transformers can be complex, so refer to HuggingFace tutorials for examples, as API documentation lacks them.
• Restart the notebook after installing packages and place installation code at the top.
• Disable GPUs for better error messages by using the following code at the start and restarting:
  
  import os
  
  
  os.environ["CUDAVISIBLEDEVICES"] = ""
  
• Alternative GPU options if Colab time runs out:
  • Personal machine's GPU.
  • Kaggle.
  • Avoid paying for Colab Pro if possible.

Part-of-Speech Tagging & Parsing

• Introduction to Natural Language Processing (NLP).
• Sequential labeling: Parts-of-Speech (POS), Named Entity Recognition.
• Classification techniques: Hidden Markov Model (HMM), Viterbi Algorithm.
• Tree Structures: Constituency and Dependency Syntax Trees.
• Parsing techniques: Transition-Based Parsing.

Understanding Text

• Previously covered:
  • Bag-of-words representations (e.g., {john, drank, some, wine, on, the, new, sofa, it, was, red}) with weighting schemes like TF-IDF.
  • N-gram language models: P("John drank some wine on the new sofa. It was red.") P("red" | "John drank some wine on the new sofa. It was") ≈ P("red" | "It was")
    • Markov Assumption
• Limitations of previous approaches: They lack true understanding of the text.

Examples of Textual Understanding

• Identifying self-contained phrases (Noun Phrases).
• Recognizing reference (anaphora) and its potential ambiguity.
• Subject and Direct Object identification.
• Understanding the modification provided by prepositional phrases.
• Grasping implications through pragmatics (e.g., John spilled the wine on the new sofa).

Relationships in Text

• Modeling relationships between words/phrases is crucial for understanding text beyond sequential words.
• Example: "I saw an elephant with a telescope. It was enormous!"
  • "an" and "elephant" form a Noun Phrase.

NLP Components

• Syntax: Identifying grammatical roles of words to form valid sentences.
  • Example: "Bank" as a direct object in "Rachel ran to the bank."
• Semantics: Understanding the meanings of words/phrases and their relationships.
  • Example: "Bank" referring to the riverbank; Rachel performing the running action.
• Pragmatics: Understanding how communicative context affects meaning.
  • Example: "John drank some wine on the new sofa. It was red." and its implications.

Context Dependence

• Context and background knowledge affect meaning.
  • "Rachel ran to the bank" vs. "Rachel swam to the bank".
  • "John drank some wine at the table. It was red." vs. "John drank some wine at the table. It was wobbly."

Complexity of NLP

• Real newspaper headlines demonstrate the complexity:
  • "Boy paralyzed after tumor fights back to gain black belt"
  • "Scientists study whales from space"
  • "Juvenile Court to Try Shooting Defendant"
• Garden Path Sentences: Sentences that initially appear syntactically incorrect.
  • "The old man the boat."
  • "The complex houses married and single soldiers and their families."
  • "The horse raced past the barn fell."

Typical NLP Pipeline

• Tokenization and lemmatization.
• Sentence boundary detection: Most NLP operates on individual sentences.
• Part-of-speech tagging: Identifying nouns, verbs, adjectives, etc.
• Parsing (dependency): Diagramming sentences.
• Named Entity Recognition: Detecting and classifying entities.
• Coreference resolution: Resolving pronouns to named entities.
• Example:
  • A tall boy ran home .
  • DT JJ NN VBD NN .
  • Mr. Mckintosh went shopping . He

NLP Approaches

• Statistical methods: Identifying patterns through supervised machine learning.
  • Learning from human interactions for training data.
• Rule-based approaches: Using linguistic and domain knowledge.
  • Example: tokenization using re.split(r'\w+', raw).
  • Challenges: Manual maintenance and updates are difficult.

Sequential NLP Structures

• NLP information as a sequence of labels.
• Examples include Part-of-Speech Tagging, Named Entity Recognition, and Word/Structure Segmentation.
• Units (token, character, sentence) are assigned labels that depend on surrounding labels.

Parts-of-Speech (POS) Tagging

• Basic syntactic analysis assigning tags to words based on grammatical role.
• Example:
  • John drank some wine on the new sofa . It was red .
  • PROPN VERB DET NOUN ADP DET ADJ NOUN PUNCT PRN AUX ADJ PUNCT
• Uses a set of "Universal" POS tags.

Examples of Universal POS tags

• ADJ (adjective): big, old, green
• ADP (adposition/preposition): in, to, during
• ADV (adverb): very, well, exactly
• AUX (auxiliary verb): is, has, must
• CCONJ (coordinating conjunction): and, or, but
• DET (determiner): a, the, some
• INTJ (interjection): psst, ouch, hello
• NOUN (noun): girl, cat, tree
• NUM (numeral): five, 70, IV
• PART (particle): 's, not
• PRON (pronoun): he, her, myself, everybody
• PROPN (proper noun): Mary, Glasgow, HBO
• PUNCT (punctuation): ., ( )
• SCONJ (subordinating conjunction): that, if, while
• SYM (symbol): $, ♥‿♥, 1-800-COMPANY
• VERB (verb): drank, running, sits

POS Tagging Accuracy

• State-of-the-art techniques achieve >98% accuracy on news text.
• Average POS tagging disagreement among expert human judges for the Penn Treebank was 3.5%.
• POS tagging in low-resource languages is harder (~87%).
• POS tagging for Tweets is harder (state-of-the-art ~88%).

Other Sequence Tagging Problems

• Word Segmentation
• Structure Segmentation

Sequence Labeling Approaches

• Rule-based: Error-prone; building & maintaining rules is challenging.
• Supervised Learning: Most common/effective approach; learns from labeled treebanks.
  • Hidden Markov Models (HMM) are covered.
  • More recent approaches exist based on neural networks, but many of the same ideas apply.

Naive Bayes for POS Tagging

• Problem: Ignores sequential information.
• Words will always be assigned the same POS tag, regardless of context.
• Example: "That was a bad call" vs. "Please call your mum after school."

Hidden Markov Model (HMM)

• Generalization of Naïve Bayes to sequences.
• Assumes an underlying set of hidden (unobserved) states (labels), y, in which the model can be.
• Assumes probabilistic transitions between states over time as sequence is generated.
• Assumes a probabilistic generation of tokens from states (e.g. words generated for each POS).
• Markov Assumption: Current state depends only on the previous state (may vary, e.g., 2nd order = previous 2 states).

HMM components

• x_i: observed nodes (i.e., words).
• y_i: hidden nodes (i.e., POS tags) - goal is to predict these.
• Transitions: p(yi | y{i-1}) (horizontal arrows).
• Emissions: p(xi | yi) (vertical arrows).

HMM Tasks

• Training: Learn p(yi | y{i-1}) and p(xi | yi).
• Inference (test): Given xi, infer yi or p(y_i).

POS Tagging with HMMs

• Hidden States: POS tags.
• Observed States: Words in the sequence.
• Goal: Predict the POS tags.

Example

• James ate the tasty food
• PROPN VERB DET ADJ NOUN
• Calculations:
  • P(PROPN | )
  • P(“James” | PROPN) * P(PROPN | )
  • P(“James” | PROPN) * P(PROPN | ) * P(“ate” | VERB) * P(VERB | PROPN)
  • P(“James” | PROPN) * P(PROPN | ) * P(“ate” | VERB) * P(VERB | PROPN) * P(DET | VERB) P(ADJ | DET) P(NOUN | DET) * P(“the” | DET) P(“tasty” | ADJ) P(“food” | NOUN)

HMM Training

• Count and normalize training data to learn transition and emission probabilities.
• Transition probabilities involve learning P(A|s), P(B|s), P(A|A), P(B|A), P(A|B), P(B|B), P(END| B), P(END| A).
• Emission probabilities involve learning P(Red|A), P(Blue|A), P(Red |B), P(Blue|B).

HMM Inference

• Goal: Determine the hidden states for a given sequence.
• Use transition and emission probabilities.

Greedy Approach

• Step through the sequence one output at a time.
• Decide the most likely hidden state based on the product of:
  • Transition probability.
  • Emission probability.
• "Greedy" because it picks the most likely choice at each outcome without looking ahead.

HMMs: Part-of-speech (POS) Training

• Transitions: p(yi | y{i-1}).
• Emissions: p(xi | yi).

HMMs: POS Inference

• Finding the hidden states gives parts-of-speech tags for each token.
• Example: James ate the food

Exercise: HMM Inference

• Calculate the probabilities and find the optimal sequence for the sentence using a greedy search.
• "Sue drew Mark"
• Transitions: P(yi | y{i-1})
• Emissions: P(xi | yi)$$

Viterbi Algorithm

• Superior to the greedy method because it takes the whole sequence into account.
• Calculates the maximum possible probability of the entire sequence given transition and emission probabilities.
• Builds probabilities up one token at a time using dynamic programming.
• Works backwards to find the optimal path through the hidden states (POS tags).

Viterbi and Dynamic Programming

• Viterbi is an example of Dynamic Programming
• Dynamic programming solves problems that rely on recursion more efficiently
• Efficiently builds up the solution Example Problem: Calculate the 100th Fibonacci multiplied by the 101st Fibonacci

Viterbi Algorithm Steps

• Work through the sequence one output/emission at a time.
• Use probabilities of reaching each of the previous hidden states.
• Find the most likely transition and emission for this output/emission.
• Decide which is the most likely previous state at each step and use that.

Viterbi Demo Example

• black bears go home

Viterbi vs. Greedy

• Viterbi allows multiple possible paths through the hidden states and keeps track of their probabilities.
• Calculates the highest probability of getting to a hidden state given all the previous inputs.

Constituency Parsing

• Breaking a sentence into noun phrases, verb phrases, etc.
• Noun Phrase (NP): noun with determinants/adjectives (e.g., The small dog, five cars).
• Verb phrase (VP): verb plus arguments (excluding its subject) (e.g., passed David the salt, walked away).
• Prepositional phrase (PP): preposition plus object (noun phrase) (e.g., To the trains, On top of the Empire State Building).

Ambiguity in Syntactic Analysis

• Sentences can have multiple possible syntactic structures.
• Example: "I saw an elephant in my pajamas."
• Moderate length sentences (20-30 words) can have thousands of possible syntactic structures.

Significance of Syntactic Structure

• Meaning can be learnt using syntactic structure.
• The NP preceding VP is often the subject; the NP following VP is often the object.
• Basic units are helpful in modeling language.
• Useful for:
  • Predicting/completing sentences (language modeling).
  • Re-organizing sentences or simplifying them (summarization).
  • Relation extraction, question answering, machine translation, semantic role labeling.

Dependency Parsing

• Given a sentence, draw edges between pairs of words and label them.
• Result should be a tree.
• Edge-labels between word pairs should convey the correct syntactic relation.

Dependency Parsing Formal Definition

• A dependency structure for a given sentence is a directed graph originating out of a unique and artificially inserted root node.
• Properties of a valid dependency graph:
  • Each word has exactly one incoming edge (except the root).
  • Weakly connected (replacing edges with undirected edges results in a connected graph).
  • Acyclic.

Linguistic Phenomena

• Capture who did what to whom:
  • Subject, direct object, indirect object.

Transition Based Parsing

• Build a parse tree with a sequence of actions (transitions).

Set-up (state)

• A buffer initialized with the words
• A stack to store state:
  • Words under consideration for more edges
  • Dependency arcs (edges)
  • The partially constructed tree

Arc-Standard parsing

• Shift: pop from buffer, push to stack.
• Left-arc: add left edge.
• Right-arc: add right edge.

Analysis of Transition-Based Parsing

• "Shift-reduce" parsing:
  • Shift: move from buffer to stack.
  • Reduce: (left-arc, right-arc) add edges, and remove elements from stack.
• For N tokens:
  • O(N) shift operations (one for each token).
  • O(N) reduce operations (one for each edge).
• O(N) = linear time parsing (if you can choose the right transitions).
• Actions are irreversible, so must correctly choose action every time.

Transition Selection

• Multi-class prediction Inputs: state= {stack, buffer, other features}
• Targets: transitions= {shift, left-arc, right-arc}

Arc Labels

• Use a separate classifier that picks arc label (given the stack features & buffer features) ie subject, object, etc..

Parsing Summary

• Syntactic parsing aims to find phrase-structure in sentences and word-word relations.

Dependency parsing

• Word-word relations e.g., nsubj(ate, Elephant).
• Generates dependency trees by predicting edges or pruning edges.

Transition-based parsing

• Formulates edge prediction as a classification task to predict next action

NLP Summary

• NLP provides tools to model language beyond simple lexical (word) features.
• Sequence models like HMMs allow us to label break apart patterns in language such as:
  • part-of-speech tags
  • sentence or word breaks
• Tree structured prediction: Useful for constructing structures such as Dependency parsing.
• Helpful for advanced applications (QA, Dialogue Systems, etc.).