DOCANA FULL

Why is NLP difficult?

• Language is social communication that computers cannot mimic

• Emergent Complexity:Turning a simple sentence to a whole story

• Subltelty of Word order

• Anaphora resolution: which requires semantic understanding

• Use of World knowledge and Interpretation

• Hetronyms:different pronunciations of words indicate diff meanings

Resolcing Linguistic Challenges

1. Rule Based

2. Statisticsa based

Rule based NLP

use of linguistic rules

-doesnt sclae well

-diminishing returns

Stats based NLP

• combine word memorizing coocurences with the rules

• Use large collections of text and compute stats of words over it.

• Use thes to learn rules

Distributional Semantics

You shall know a word by the company it keeps

ALGO: keep track of cooccuring words with the diff spellings and predict best spelling by surrounding wordxs

-doesnt cover all words

Zipfs Law

freq of words is inversly prop to its rank in the freq table

Deep Learning for NLP

feed web-scale corpora of unlabeled text into (deep) neural networks with billions of parameters to learn word cooccurrence patterns.

Current deep neural language models:

• can solve some NLP tasks better than humans

• can solve tasks for which they have not or barely been trained (transfer learning, zero-shot learning)

• can be quite biased (garbage in, garbage out)

Morphology

The study of the way in which words are constructed from smaller units of meaning

Morpheme

The smallest meaningful unit in the grammar of a language.

Inflectional Morphology

• Variation in the form of a word, typically by means of an affix, that expresses a grammatical contrast.

• Does not change the word class

• no change of meaning.

• Modifies words to serve a new grammatical role

• Adds morphemes that encode: tense, number, person, mood, aspect, etc.

Derivational Morphology

• The formation of a new word or inflectable stem from another word or stem

• Nominalization: formation of nouns from other parts of speech

• Formation of ADJECTIVES

• irregular process

Stem

• The common part to all inflected words.

• Is not necessarily a proper word from the dictionary

Lemma

The base form of a word

Root

• is common to a set of derived or inflected forms, if any, when all affixes are removed

• cannot be split further into meaningful components

• carries the principal portion of meaning of the words

Affix

A bound morpheme that is joined before, after, or within a root or stem.

Clitic

A morpheme that functions syntactically like a word, but does not appear as an

independent phonological word

Segments of a text

● Volumes

● Books

● Chapters

● Paragraphs

● Sentences

● Tokens (and punctuation)

● Characters

Sentence Splitting

NAIVE: with whitespaces and punctions(doesnt work for all languages)

Binary Classifier

● Sequentially iterate over all tokens and punctuation

● Decide whether the sentence ends here.

Token

The occurrence of a word in a text

Tokenization

Segmentation of an input stream into an ordered sequence of tokens

Tokenizer

A system that splits texts into word tokens

Naïve approach: Split tokens at whitespace characters

Problems with naive tokenization

periods and whitespace are ambigious

irregular cases and spelling variations

Agglutinative Languages(compunds nouns in german)

Sinitic Languages (where moving of a character can change the meaning )

Tokenization Algorithm: Maximum Matching

Consider the input sentence as a simple word sequence

● Use a dictionary

● Start at the beginning of the sentence

● Search for the longest matching string in the dictionary and cut

● Start matching against the dictionary again

However it does not work well in English

Token Normalization

To make these words comparable, we want to normalize them by grouping them into equivalence classes.

Lemmatization, Stemmatization

Porter Stemmer

● We effectively chop off the end of the word!

● Only suffixes are considered for removal

● Frequently used algorithm (especially for Information Retrieval)

● Results are pretty ugly from a linguistic perspective

Idea behind Porter Stemmer

● Consecutively remove / replace suffixes

● The number of iterations depends on the “syllables” of the word

● In each step, one rule from a fixed set of rules is applied

● No rule may be applied twice

● Once no rule can be applied, the algorithm stops

Measure of a word for porter stemmer

● V denote a sequence of vowels and

● C denote a sequence of consonants.

Then each word can be modeled as: [C](VC)m[V] and m is called the measure of the word,

use m to approximate the number of syllables.

Problems with Porter stemmer

Overstemming

Understemming

Overstemming

Two words are stemmed to the same root when they should have been treated as separate

Understemming

Two separate inflected words should be stemmed to the same root but are stemmed to different roots

Lemmatization problem

complexity and need for knowledge and understanding of the context

Lemmatization approach

refers to doing things properly with the use of a vocabulary and morphological analysis of words, normally aiming to remove inflectional endings only and to return the base or dictionary form of a word, which is known as the lemma

Data Formats

POS Tagging

The process of classifying words into their parts of speech and labeling them accordingly.

Parts of speech are also known as word classes or lexical categories.

The collection of tags used for a particular task is known as a tagset.

Purpose of Tagging

• Collapsing distinctions into equivalence classes

• Introducing distinctions to resolve ambiguities

• Helpful features in classification and prediction tasks

Tagging

The process of associating labels with each token in a text

Tag Set

● The collection of tags that is used for a particular task

● Tag sets are defined by linguists and not unambiguous.

● Different languages require different language-specific tag sets

● It is difficult to compare tags between different languages

Requirements for Tagsets

Informativeness: degree of ambiguity

Specifiability: inter-annotator (inter-judge) agreement should be good

Frequently Used Tagset

English:

● Brown corpus

● Penn Treebank

● Lancaster UCREL C5

● Lancaster C7

German:

● Stuttgart-Tübingen Tagset (STTS)

Feature based Tagging

Knowledge of tag combinations for neighbouring words enables us to leverage syntactic rules to make decisions.

Using word level and tag sequence features: 93.7% accuracy

NLP Pipeline

Probabilistic Tagging

Count POS tag frequencies for a given token in the annotated corpus

Select the most probable (= frequent) POS tag in new, unseen data

Naive Unigram issue

Problem: many words might never be seen in the training data (out-of-vocabulary)

Solution: specify a default tag as “backoff

The most frequent tag is obviously not always correct, it depends on context

POS Tagging Approaches

Unigram Tagger bayes

We use bayes formula instead

The most frequent tag is obviously not always correct, it depends on context

n gram

An n-gram is a contiguous sequence of n tokens from a given sample of text. The n stands for how many tokens are used. (n-1) is the order

using n > 5 is rare.

N-grams can encode different types of contexts, e.g.

● Character based n-grams

● Token-based n-grams

● POS-based n-grams

● Combinations of the above

Use of n gram

○ Words before and after a period to determine if it is the end of a sentence

○ Detecting open compound nouns

n gram idea

● Use the unigram probability for the current token (→ unigram tagger)

● Use the predicted preceding n-1 tags

The tagger picks the tag which is most likely, given that context

Backoff

● Attempt to tag the token with the 1st order tagger (e.g., bigram tagger)

● If the 1st order tagger is unable to find a tag for the token, fall back tousing a 0th order tagger (e.g., unigram tagger)

● If the 0th order tagger is also unable to find a tag, use the default taggerto find a tag (e.g., feature based tagger)

Bigram and trigram taggers need the previous tag context to assign new tags. If they see a [na] tag in the previous context, they will also output [na]. → Error propagation

Rule based Tagging

handcrafted sets of rules to tag input sentences

Brill Tagger

Core idea:

○ Use a probabilistic approach first

○ Then revise and correct it using contextual rules

supervised method and requires tagged corpus

Parsing

process of determining syntactical structure of a sentence using grammar

Syntactical corecctness =! meaningful semantic

Formal Grammar

A formal grammar G = (N,T,P,S) provides a schema for generating a formal language. It consists of:

• A finite set of non-terminal symbols N (for natural language: constituents)

• A finite set of terminal symbols T (for natural language: words)

• A start symbol S (for natural language: a sentence)

• A finite set of production rules P of the form: left hand side → right hand side

Grammar’s Language

The grammar’s language L(G) is the set of all sequences of terminal symbols that can be generated with the grammar.

To generate a sentence from the language:

• Beginning with the start symbol, consecutively apply rules (“derivation”)

• Applying a rule replaces all symbols on the left hand side with the right hand side.

• Once only terminal symbols remain, the derivation is complete

Chomsky Hierachy

Chomsky Normal Form

A context-free grammar (CFG), is said to be in Chomsky normal form if all of its production rules are in one of the following three forms:

• A → BC

• A → a

• S → ε

where:

• A,B,C are nonterminal symbols

• a is a terminal symbol

• S is the start symbol

• ε denotes the empty string

• Neither B nor C can be S

Constituent

A word or a group of words that function as a single unit
within a hierarchical structure.

A sentence has a Noun Phrase and Verb Phrase.

Parse Tree

 a parse tree (or derivation tree) is an ordered rooted tree that graphically represents the syntactic information of a string derived from a (context-free) grammar

Purpose of Parsing

●Grammar Checking & Translation:Identify syntax errors and preserve grammatical structure across languages.

● Information Extraction: Reveal who did what to whom using sentence structure.

● Question Answering Systems: Understand question structure to extract accurate answers

Parsing Issues

Synatctic Ambiguities

• Prepositional phrase attachment(unsure where prep belong)

• Coordination scope(who adj refers to)

• Particles vs. prepositions(diff meanings of a word)

• Gerund vs. adjectives

Agreement

Approaches to generate parse trees

Top-down approach

Bottom-up approach

Leftmost derivation approach

It is designed for restricted context free grammars (e.g., programming languages) and does not work perfectly on natural language.

Leftmost derivation is an example of top-down parsing.

Algorithm outline:

• Start with S

• In each step, apply a production rule to the
  leftmost non-terminal symbol

• Produce the observed terminal symbols
  (= tokens)

• Terminates once all observed words
  have been created.

Shift Reduce Parser

A shift reduce parser is effectively a pushdown automaton that uses a stack for recognizing a context free language. It is an example of bottom-up parsing.

Algorithm outline:

• SHIFT operation:
  Push a word from the input sentence onto the stack

• REDUCE operation:
  If the top n words on the top of the stack match the right hand side of a production rule, then they are popped and replaced by the left hand side of the production.

STOPPING condition:
The process stops when the input sentence has been processed and S has been popped from the stack

CKY Parser

The Cocke-Kasami-Younger parser (CKY parser, sometimes CYK parser) uses dynamic programming. It is an example of a bottom-up parser.

Core idea:

• Cache intermediate results (dynamic programming)

For building a parse for a sequence [i,j], keep track of all parses of
subsequences [i,k] and [k,j] that are included in it (i ≤ k ≤ j).

CYK Pros and Cons

Advantage:

• Backtracking: if the parser gets stuck, we can easily go back to a previous alternative

Downside:

• Requires a binarized grammar

The grammar must be in Chomsky Normal Form

Statistical Parsing

resolves ambiguous parse trees

Lexicalized Parsing

Using corpus statistics, we can go even further and construct a parser that takes lexical relations into account to compute probabilities.

Dependency Grammar

Dependency grammar assumes that syntactic structure consists only of dependencies between tokens.

• Dependencies are (labeled) asymmetric
  binary relations between two tokens.

• Dependencies typically form a tree with
  a single head (the root).

Dependency Parsing vs constituency Parsing

Event

Linguistic: verb

Information Retrieval: a relation of entities

Named Entity

A unique entity that is identified by its name. Can be of form:

• Persons

• Locations

• Organizations

• Dates

• Times

• Numeric expressions

• Or domain specific

Information Extraction Systems Goals

• Identify and understand relevant parts of texts

• Gather, collate, and link information within and between documents in the corpus

• Produce a structured representation of relevant information

• Organize information so that it is useful to people

• Store information in a semantically precise format that is usable by algorithms

IE Pipeline

• Recognition of named entities

• Extraction of relations between entities

• Knowledge base population

Name Entity Recognition

The goal:Identify named entities in a document and tag them with a type

Encoding Classes for NER

Inside-Outside (IO) encoding is less precise

Inside-Outside-Beginning (IOB) encoding is more precise but requires
a larger tagset

• the benefit is limited in practice, so IO is often used

Features for NER

Token level:current/prev/next

Tag level:Inferred linguistic classification

Label Level:Previous (and perhaps next) named entity label in the current sequence

Substrings in NER

we can detect patterns of substrings in certain domains however there are exceptions

Token Shape

Some named entity names tend to follow patterns that can be mapped to a simplified representation based on attributes such as:

• Token length,

• Capitalization,

• Numerals,

• Greek letters,

• Internal punctuation,

• etc.

NER models

• Markov Models

  • Conditional Markov Models make a single decision at a time,
    conditioned on evidence from observations and previous decisions

• Conditional Random Fields

  • A whole-sequence conditional model, rather than a chain of local models

• Deep learning models

  • Bidirectional Long Short Term Memory models (LSTMs)

  • Transformers

Handling Ambiguity: Normalization

reducing or rewriting something to a common (normal) form.

NE disambiguation

The task of deciding whether two entity mentions refer to the same entity.

NE linking

The task of linking an entity mention to a unique identifier.

Linking with knowledge graph

For persons, organizations, and locations, we typically link to an entry in a knowledge graph. The most commonly used resource is Wikidata.

Entities have

• A unique Q-identifier

• Properties that connect them to other entities

• Validity times for properties

• A ranking mechanism for statements

Drawbacks of knowledge graph

Engineering the structure of a knowledge graph (an ontology) is difficult and subjective,

Normalizing Temporal Entities

it is a rule based approach.

• Absolute temporal expressions

• Relative temporal expression

Domain Dependence for Relative Temporal Expression

For relative temporal expressions, a reference time is necessary, which requires domain knowledge to retrieve.

• News-style texts: Use publication metadata

• Narrative texts: use preceding information in paragraph

Implicit Networks

Relations to entities have scores associated to them

Networks are aggregated

NER Applications

Types of similarity

Surface form similarity:

• Phonological similarity (e.g., brake | break)

• Morphological similarity (e.g., respect | respectful)

• Spelling similarity (e.g. theater | theatre)

Semantic similarity:

• Synonymy (e.g. verbose | wordy)

• Hypernymy, Hyponymy (e.g., color | red)

Content similarity:

• Sentence similarity (e.g., paraphrases)

• Document similarity (e.g., two news stories on the same event)

Phonological Similarity

• Uniform spelling is a (relatively) modern phenomenon.

• Names tend to have high spelling variation

• Variation is even higher across languages

• This is problematic for statistical approaches

Soundex

Soundex is a class of heuristics for expanding a query into phonetic equivalence classes. It is mainly used for names and is language-specific.

IDEA:Turn every token into a 4-character reduced form

• Build an index on the reduced forms

• Apply the same encoding to query terms (= tokens in the query)

• Search the index for phonetically similar tokens that have the same encoding

Soundex ALGO

Soundex Cons

• Language specificness: originally developed for English

• Homophonous names starting with a different character 

• Unable to discriminate between long words (4-character limit)

• Conflation of unrelated family names:

Morphological Similarity

• We can consider words to be similar if they share a root

• We can use stemming or lemmatization to measure similarity

Spelling Similarity: Spell Checking

There are two flavors of spell checking:

• Isolated words

• Context Sensitive

Isolated Word Correction

Word similarity for word correction:

• Given a lexicon and a word w, return the words in the lexicon that are closest to w (Edit Distance)

Levenshtein Distance

Given two strings S1 and S2, count the minimum number of basic operations to convert one string to the other.

Basic operations are typically character-level: 

• Insert

• Delete

• Replace (i.e., substitute)

Levenshtein (Wagner Fischer ALGO)

Step 1: Setup and parameters
Set n to be the length of string s
Set m to be the length of string t
If n=0, return m and exit.
In m=0, return n and exit.
Construct a matrix containing 0…m rows and 0…n columns.

Step 2: Initialization
Initialize the zeroth row to 0…n
Initialize the zeroth column to 0…m

Step 3: Iteration
For i from 1…m     // iterate over rows
    For j from 1…n       // iterate over columns

        if s[i] = t[j] then subCost := 0 // retain character
        if s[i] ≠ t[j] then subCost := 1 // replace character

        d[i, j] := minimum(d[i-1,   j] + 1,       // deletion
                                                          d[i,   j-1] + 1,       // insertion
                                                          d[i-1, j-1] + subCost) // substitution
return d[m, n]

Weighted Edit Distance

• Different costs for insert / delete operations

• Cost matrices to encode individual cost for replace operations

• Can use domain-specific knowledge