Natural Language Processing (NLP)

Course Notes — Module 1 & Module 2

Course Code: CSDC7013
Module 1: Introduction to NLP | Module 2: Word Level Analysis

MODULE 1: INTRODUCTION TO NLP

1. What is Natural Language Processing?
• NLP is a subfield of linguistics, computer science, and artificial intelligence that deals with the interaction between
computers and human language — how to make computers understand, process, and generate large amounts of natural
language data.
• It is a branch of AI that lets computers analyze and understand human language, both spoken and written.
• Goal: build software that generates and comprehends natural language, so users can converse with computers naturally
instead of through rigid programming/artificial languages (like Java or C).
• NLP is a subset of AI and relies heavily on Machine Learning (ML) and Deep Learning (DL) techniques.

2. Prerequisite Concepts
2.1 Theory of Computer Science
• Grammar = the set of rules for forming well-structured sentences; it plays a key role in describing the syntactic structure
of well-formed programs/languages.
• Grammar denotes the syntactic rules used in natural-language conversation.
• Context-Free Grammar (CFG): a list of rules defining all well-formed sentences in a language. Each rule has a left-hand
side (a syntactic category) and a right-hand side (its component parts, read left to right).

2.2 System Programming & Compiler Construction

• Two main techniques used in NLP: syntax analysis and semantic analysis.
• Syntax: arrangement of words in a sentence to make grammatical sense; NLP uses syntax + grammar rules to assess
meaning.
• Syntax techniques: Parsing, Word segmentation, Sentence breaking, Morphological segmentation, Stemming.
• Semantics: the use and meaning behind words; NLP applies algorithms to understand meaning and sentence structure.
• Semantics techniques: Word Sense Disambiguation, Named Entity Recognition, Natural Language Generation.

3. What is a Corpus?
• A corpus (plural: corpora) is a large, structured set of machine-readable text or speech from native speakers of a
language, organized into datasets.
• It is the (pre)processed text/audio data used to train ML models in NLP.

4. Popular Open-Source NLP Toolkits

Toolkit Key Points

NLTK (Python) Leading platform for building Python programs on human language data;
provides interfaces to 50+ corpora/lexical resources (e.g. WordNet) and libraries
 Toolkit Key Points

for classification, tokenization, stemming, tagging, parsing, semantic reasoning.

Stanford CoreNLP Statistical, deep-learning, and rule-based NLP tools for major computational
linguistics problems; widely used in industry, academia, government.

Gensim (Python) Open-source package mainly for unsupervised topic modeling; handles large text
files without loading them fully into memory; doesn't need tagged documents
since it is unsupervised.

OpenNLP Open-source library for common NLP tasks (tokenizing, POS tagging, NER, etc.).

5. Generic NLP System — Components

Not every system has every component below, but together they describe the pipeline most systems draw from:
• Input Preprocessing: speech recognizer / text preprocessor / gesture recognizer — produces segmented text as input to
the main NLP pipeline.
• Morphological Analysis: well understood for common languages but complex for others (e.g. Turkish, Basque).
• Part-of-Speech Tagging: not essential to every deep-processing system, but often used to cut down the parser's search
space.
• Parsing: covers syntax and compositional semantics, sometimes treated as separate stages.
• Disambiguation: can happen during parsing or be left to a later phase.
• Context Module: maintains contextual information, e.g. for anaphora resolution.
• Text Planning: part of language generation — decides what meaning to convey.
• Tactical Generation: converts meaning representations into strings, may reuse the parser's grammar/lexicon.
• Morphological Generation: the reverse of morphological analysis — fairly straightforward for English.
• Output Processing: text-to-speech, text formatting, etc.
Note: Application-specific components are added on top, e.g. an interface to a knowledge base for NL interfaces/email
answering, or a mapping component between semantic representations for transfer-based Machine Translation.

6. Levels of NLP (7 Interdependent Levels)

NLP begins with a word's morphological structure, then moves to word order, grammar, meaning, and finally overall context.
A system may use any subset of these levels depending on the task.

Level Deals with

1. Phonological Pronunciation — applies only when the input is speech; interprets speech sounds
within and across words.

2. Morphological Study of word structure/formation — analysis of individual word components

(morphemes).

3. Lexical Lexical meaning and part-of-speech of individual words, using the language's
lexicon (set of lexemes).

4. Syntactic Grammar and sentence structure — grouping words into phrases/clauses (parsing).

5. Semantic Meaning of words and sentences — disambiguating multi-sense words using

context.

6. Discourse Structure/meaning of text beyond a single sentence — connects sentences (e.g.

anaphora resolution).

7. Pragmatic Real-world knowledge external to the document that affects interpretation.

6.1 Morphological Level — Example
Example: "unhappiness" → three morphemes: un- (prefix, "not"), happy (stem), -ness (suffix, "state of being"). "happy"
is a free morpheme (a word on its own); un- and -ness are bound morphemes (cannot stand alone).

6.2 Lexical Level — Example

Example: "Duck" can be a noun or a verb — its part-of-speech and meaning can only be resolved using the surrounding
context.

6.3 Discourse Level — Anaphora Resolution

• Anaphora Resolution = identifying the entity referenced by an anaphor (commonly a pronoun) earlier in the discourse.

7. Applications of NLP
• Machine Translation
• Text Summarization
• Sentiment / Opinion Analysis
• Information Retrieval
• Question Answering Systems
• Chatbots, Plagiarism & Spelling/Grammar checkers, Personal Assistants, Tutoring Systems

MODULE 2: WORD LEVEL ANALYSIS

1. Text Normalization — Overview
Text normalization converts text into a more convenient, standard form so indexed text and query terms match (e.g. "U.S.A."
should match "USA") — this is called defining equivalence classes of terms. It has four main sub-tasks:
• Tokenization
• Lemmatization
• Stemming
• Sentence Segmentation

1.1 Case Folding

• Reduces all letters to lowercase, but this is task-dependent:
◦ Upper-case in mid-sentence may signal a named entity (e.g. "General Motors").
◦ For Machine Translation / Information Extraction, keeping case can help (e.g. "US" vs "us").

1.2 Tokenization
• Separating (tokenizing) words out of running text.
• Whitespace alone isn't sufficient: "New York" or "rock 'n' roll" should sometimes stay as single tokens; "I'm"
sometimes needs to split into "I" and "am".
• Social-media text needs tokenization of emoticons (":)") and hashtags ("#nlproc").
• Some languages (e.g. Japanese) have no spaces between words, making tokenization much harder.
Common tokenization issues:
• Finland's → "Finland", "Finlands", or "Finland's"?
• What're, I'm, shouldn't → expand to "What are", "I am", "should not"?
• San Francisco → one token or two?
• m.p.h. → how should abbreviations be handled?
Hyphenation types:
• End-of-line hyphen: splits a word across lines for justification (e.g. "mid-dle English").
• Lexical hyphen: certain prefixes are conventionally hyphenated (co-, pre-, meta-, multi-).
• Sententially determined hyphenation: prevents incorrect parsing, e.g. "state-of-the-art", "three-to-five-year".

1.3 Lemmatization
• Determines that two words share the same root despite surface differences.
Example: sang, sung, sings → common lemma "sing".
• Essential for morphologically complex languages (e.g. Arabic).

1.4 Stemming
• A simpler, cruder version of lemmatization — mainly strips suffixes from the end of a word.
Example: watching → watch; caring → car.

1.5 Sentence Segmentation

• Breaking text into individual sentences using cues like periods and exclamation marks.
• '!' and '?' are usually unambiguous sentence boundaries; '.' is ambiguous — it appears in abbreviations (Dr., Mr., m.p.h.)
and numbers (2.4%, 4.3).
• Can be framed as a binary classifier per period: End-Of-Sentence vs Not-End-Of-Sentence, built with hand-written
rules, regular expressions, or machine learning.

2. Edit Distance
• A metric that measures how similar two strings are, based on the minimum number of edits (insertions, deletions,
substitutions) needed to turn one string into the other.

3. Regular Expressions (RE)

• A language for specifying text-search patterns / strings; central tool of text normalization.
• An RE search scans a corpus and returns all text matching the given pattern.

3.1 Basic Patterns

• Concatenation — placing characters in sequence.
• Range — e.g. [a-z].
• Kleene * — zero or more occurrences.
• Kleene + — one or more occurrences.

3.2 Other Operators

• Disjunction using the pipe | (e.g. woodchuck|groundhog).
• Negation inside brackets using ^ as the first character, e.g. [^Ss].
• ? \* + as quantifiers; ^ and $ as anchors (start/end of line).
Example: To find "the": plain "the" misses capitalised forms; [tT]he wrongly also matches "other"/"theology"; adding
boundary characters [^a-zA-Z][tT]he[^a-zA-Z] is more precise.

3.3 Types of Matching Errors

Error type Meaning

False positives (Type I) Matching strings that should NOT have matched (e.g. matching "there",
"then", "other" while searching for "the").

False negatives (Type II) Failing to match strings that SHOULD have matched (e.g. missing
 Error type Meaning

capitalised "The").

• Reducing error rate usually involves two competing goals: increasing precision (fewer false positives) vs increasing
recall (fewer false negatives).

4. Words: Types vs Tokens

• Corpus (plural corpora): a computer-readable collection of text or speech, e.g. the Brown corpus — about a million
words from 500 written English texts across genres, assembled at Brown University (1963–64).
• Type: a distinct word in the corpus; if V is the vocabulary, |V| = number of types.
• Token: the total count N of running words (including repeats).
Example: "I have a can opener; but I can't open these cans." → 11 word tokens, 10 word types.
• Common tokenization libraries: NLTK, spaCy, Polyglot (Python); Stanford CoreNLP (Java); Unix command-line tools.

5. Morphology
• The study of how words are built from smaller meaning-bearing units called morphemes.
• Two broad classes of morphemes:
◦ Stems: the central morpheme carrying the main meaning.
◦ Affixes: add additional meaning to the stem.
Example: "fox" = 1 morpheme (fox); "cats" = 2 morphemes (cat + -s).

5.1 Free vs Bound Morphemes

• Free morpheme: can stand alone as a word (e.g. cat, boat, bad). Carries most of the semantic content; typically nouns,
verbs, adjectives, prepositions, adverbs.
• Bound morpheme: only occurs attached to another morpheme (e.g. -s, -er, -ing, -ment, -ly). Cannot stand alone.
Example: badly = bad (free) + -ly (bound).

5.2 Types of Affixes (by position)

Affix type Position Example

Prefix Before the root/stem re-search, un-kind, in-accurate

Suffix After the root/stem kind-ly, wait-er, book-s

Infix Inserted within the word cupsful, spoonsful, passersby ("s" as infix)

Circumfix Attached both before and after German ge...t: lieb → geliebt ("loved")
(discontinuous)

5.3 Open Class vs Closed Class Words

• Open class (lexical/content words): nouns, verbs, adjectives, adverbs — new words are added regularly (e.g. internet,
email, download, right-click).
• Closed class (function/grammatical words): conjunctions, prepositions, articles, pronouns — a fixed, rarely-expanded
set (e.g. of, the, but).

6. Stemming — Detailed
• Reduces terms to their stems for information retrieval; a crude, language-dependent chopping of affixes.
Example: automate(s), automatic, automation → all reduced to "automat".
6.1 The Porter Stemmer
• One of the most widely used stemming algorithms (Porter, 1980); chops off word-final affixes via a cascade of rewrite
rules — each pass's output feeds the next pass.
Sample rewrite rules:
• ATIONAL → ATE (relational → relate)
• ING → ε (if stem contains a vowel) (motoring → motor)
• SSES → SS (grasses → grass)
Porter's algorithm — representative steps:

Step Rule examples

Step 1a sses → ss (caresses → caress); ies → i (ponies → poni); ss → ss (caress → caress); s →

ø (cats → cat)

Step 1b (*v*)ing → ø (walking → walk); sing → sing (unchanged); (*v*)ed → ø (plastered →

plaster)

Step 2 (long stems) ational → ate (relational → relate); izer → ize (digitizer → digitize); ator → ate (operator
→ operate)

Step 3 (longer stems) al → ø (revival → reviv); able → ø (adjustable → adjust); ate → ø (activate → activ)

Example: Applying the Porter stemmer to a full sentence turns "This was not the map we found..." into a stream of
chopped stems: "Thi wa not the map we found... accur copi complet..." — illustrating how crude/aggressive the process
is.

6.2 Over-stemming vs Under-stemming

Error Definition Example

Over-stemming Too much is chopped off, so two words with university & universe → both wrongly
different roots get wrongly reduced to the reduced to "univers"; wander → wand;
same stem (a kind of false positive). news → new

Under-stemming Words that should share a root get reduced data & datum → wrongly reduced to
to different stems (a kind of false negative). "dat" and "datu" instead of both becoming
"dat"

6.3 Stemming vs Lemmatization — Comparison

Aspect Stemming Lemmatization

Speed Faster — chops without knowing sentence Slower — considers context before
context converting

Approach Rule-based Dictionary-based

Accuracy Less accurate More accurate

Output May create a non-existent word form Always gives a real dictionary root word

When to prefer When exact word meaning doesn't matter When word meaning matters (e.g. question
(e.g. spam detection) answering)

Example "Studies" → "Studi" "Studies" → "Study"

7. Applications of Stemming & Lemmatization
• Widely used in Text Mining — the analysis of natural-language text to extract high-quality information (text
categorization, clustering, sentiment analysis, summarization).

7.1 Information Retrieval (IR)

• Maps documents to general topics via stemming/lemmatization and indexes them for search.
• Query Expansion enhances a user's query to match more relevant documents (e.g. "marketing" should also surface
"markets").

7.2 Sentiment Analysis

• Analyzes user reviews/comments (e.g. for online retail); stemming/lemmatization is used as a text-preparation step
before interpretation.

7.3 Document Clustering

• Groups textual documents for topic extraction and fast retrieval.
• Stemming/lemmatization reduces the number of distinct tokens, which speeds up frequency-based feature computation
and clustering.

8. Why Does Morphology Matter?

• Information Retrieval: a query for "phones" should also match "phone".
• Language Modeling: having seen "scrutinize", the model can predict "scrutinized".
• Machine Translation: Swedish "bilen" corresponds to English "the car" — morphological info must be handled during
translation.

9. Types of Morphology
• Inflectional Morphology: produces different grammatical forms of the same word (e.g. tense, number, case) without
changing its core meaning or word class.
• Derivational Morphology: creates a new word (often a new word class) by adding affixes, e.g. happy → happiness.

— End of Notes —