Miracle Educational Society Group of Institutions (Autonomous)

Department of AI&DS
UNIT I: Natural Language Processing (NLP)

1. Finding the Structure of Words

1.1 Words and Their Components
Tokens
Basic units in text, separated by whitespace or punctuation.
Example: In "Will you read the newspaper?", tokens are "Will", "you", "read", "the",
"newspaper".
Example sentence
sentence = "Will you read the newspaper?"
# Tokenize by splitting on whitespace and punctuation
import re
tokens = [Link](r"\b\w+\b", sentence)
print("Tokens:", tokens)
OUTPUT:Tokens: ['Will', 'you', 'read', 'the', 'newspaper']
Lexemes
The conceptual representation of a word, including its variants.
Example: The lexeme "run" includes run, runs, ran, running.
The lexeme "talk" represents the core concept of the action "to speak." All its variants
—"talk," "talks," "talked," and "talking"—share the same basic meaning but differ in tense,
number, or grammatical form. These variants are different word forms that stem from the
same underlying lexeme. The lexeme encapsulates the core meaning, while the variants are
concrete realizations used in different contexts.

Morphemes
The smallest meaningful units of language.
Example: "played" = "play" + "ed" (root + suffix).
Example:
The word "played" consists of two morphemes:
 "play" (the root) — meaning the core concept of playing
 "ed" (the suffix) — indicating past tense
Explanation:
In "played," the root morpheme "play" conveys the main idea, and the suffix "ed" adds
grammatical information, showing that the action happened in the past. Both "play" and "ed"
are meaningful units, making them morphemes. The combination of these morphemes creates
the full word "played."

Typology
Classification of languages based on their morphological structure:
Isolating (analytic): Few morphemes per word, e.g., Chinese.
Agglutinative: Clear morphemes attached sequentially, e.g., Turkish.
Fusional: Morphemes fused, e.g., Latin, Russian.
Typology classifies languages according to how they use morphemes within words.
1. Isolating (Analytic) Languages
o Characterized by few morphemes per word.
o Words tend to be simple and composed of a single morpheme.
o Example: Chinese
 "吃" (chī) means "eat." It is a single morpheme and a word by itself.
 In Chinese, grammatical relationships are often expressed using word
order rather than inflections.
2. Agglutinative Languages
o Have clear, separate morphemes attached in sequence.
o Each morpheme typically carries a single grammatical meaning.
o Example: Turkish
 "ev" (house)
 "evler" (houses) — "ev" + plural suffix "-ler"
 "evlerde" (in the houses) — "ev" + plural "-ler" + locative "-de"
 The morphemes are strung together in a chain, each with a distinct
meaning.
3. Fusional Languages
 o Morphemes are fused together, often with multiple grammatical meanings
embedded in a single morpheme.
o The boundaries between morphemes are less clear.
o Example: Latin or Russian
 Latin "amō" (I love), "amābam" (I was loving) — the endings combine
tense, mood, and person into one morpheme.
 In Russian, the word "говорил" (govoril) means "he spoke," where the
suffix "-ил" indicates past tense, gender, and number all at once.

1.2 Issues and Challenges in Morphological Models

Irregularity: Words with unpredictable forms, e.g., "went" (past of "go").
Ambiguity: Words with multiple meanings, e.g., "bat" (animal or sports equipment).
Productivity: Creating new words or forms dynamically, e.g., "googled".
Complexity: Handling inflection, derivation, and irregular forms efficiently.

Irregularity
Definition: Words that do not follow standard or predictable patterns in their forms.
Example:
 "went" is the past tense of "go," but unlike regular past tense verbs ending in "-ed," it
changes irregularly.
 Regular: "walk" → "walked"
 Irregular: "go" → "went"

Ambiguity
Definition: Words that have multiple meanings depending on context.
Example:
 The word "bat" can mean:
o An animal that flies at night
o A piece of sports equipment used in baseball or cricket

Productivity
Definition: The ability of language to create new words or forms easily and systematically.
Example:
  The verb "google" has become productive, meaning to search for information online.
 Past tense "googled" is formed by adding "-ed" to the base word, demonstrating how
new words and forms are regularly generated.

Complexity
Definition: The capacity of language to handle various linguistic processes like inflection,
derivation, and irregular forms efficiently.
Example:
 In English, verbs conjugate for tense and agreement:
o Regular: "talk" → "talked" (past)
o Irregular: "bring" → "brought"
 The language manages these diverse forms through rules, templates, and exceptions,
making communication precise despite complexity.

1.3 Morphological Models

1.3.1 Dictionary Lookup

Uses large lexicons for direct matching.
Example: To analyze "cats", look up "cat" + suffix "s".
Definition:
Dictionary lookup involves using a large lexicon (dictionary) to analyze or understand words
by matching them directly to known base words and affixes.
How it works:
 To analyze a word like "cats", the system searches the lexicon for the base
word "cat".
 It then checks for a suffix, in this case "s", which indicates plural form.
 By combining the base "cat" with the suffix "s," the system recognizes that "cats" is
the plural of "cat".
Example:
Suppose you want to analyze "dogs".
 The lookup searches the lexicon for "dog".
 It finds "dog" and then identifies the suffix "s" as a plural marker.
 So, "dogs" is understood as "dog" + plural suffix.
This method relies on a comprehensive lexicon that contains many root words and common
affixes, enabling direct matching and quick analysis of new or complex words.

1.3.2 FiniteState Morphology

Uses automata for modeling word formation.
Example: Analyzing "geese" into "goose" + plural suffix.
Definition:
Finite State Morphology uses computational models called automata (state machines) to
represent and analyze the rules of word formation in a language. These automata efficiently
handle complex morphological processes such as inflection, derivation, and irregular forms.
How it works:
 The automaton is designed with states and transitions that encode the morphological
rules.
 When analyzing a word like "geese", the automaton processes the word letter by
letter, following transitions that represent possible morphological components.
 It recognizes "geese" as the base "goose" plus the plural suffix "-s" (which is
irregular in this case).
Example:
 Analyzing "geese":
o The automaton identifies the root "goose".(bird)
o It then detects the suffix "s", which in this context indicates plural.
o Even though "geese" is irregular (not just "gooses"), the automaton's rules
handle this irregularity through specific transitions.
Whyit'suseful:
Finite State Morphology provides a systematic and efficient way to model complex
morphological patterns, including irregular forms, by encoding rules into a finite automaton.

1.3.3 UnificationBased Morphology

Uses feature structures and unification operations.
Example: Verb "run" with features: tense=past, number=singular.
Definition:
Unification-Based Morphology uses feature structures—sets of attributes and values—to
analyze and generate words. It employs unification operations, which are processes that
combine feature structures by merging compatible attributes, to handle complex
morphological phenomena.
How it works:
 Each word or morpheme is represented as a feature structure (e.g., tense, number,
person).
 When analyzing or generating words, the system unifies (merges) feature structures to
ensure compatibility and to build or check correct forms.
Example:
Consider the verb "run" with specific features:
 Tense = past
 Number = singular
This could be represented as a feature structure:
Verb
└─ tense = past
└─ number = singular
Usage:
 To generate the past singular form of "run", the system unifies the base verb's
features with the features for past tense and singular number.
 If the verb is irregular (like "run" → "ran"), the morphological rules encode this
irregularity within feature structures, and unification ensures the correct form is
generated or analyzed.
Whyit'spowerful:
Unification-based morphology allows for flexible and detailed modeling of complex and
irregular word forms by manipulating rich feature structures, making it ideal for natural
language processing tasks.
Another Example
Noun
└─ base_form = "book"
└─ number = plural
└─ case = genitive
Step 3:
Apply morphological rules based on the combined features:
 For plural, add -s
 For genitive, add "'s" or "of" depending on language rules
Result:
 "books" (plural)
 "book's" (possessive/genitive)

1.3.4 Functional Morphology

Uses principles of functional programming.
Example: Modeling inflection as functions transforming base forms.
Definition:
Functional Morphology models morphological processes using principles from functional
programming. It treats morphological operations—like inflection, derivation, or
compounding—as functions that take a base form (input) and produce an inflected or derived
form (output). This approach emphasizes the compositional and transformation-based nature
of morphology.
How it works:
 Base forms (like root words) are inputs to functions.
 Morphological rules are functions that transform these inputs into new forms by
applying functions (like adding suffixes, changing vowels, etc.).
 These functions can be composed to handle complex morphological processes.

Example: Modeling English Past Tense Inflection

Suppose we want to model the formation of the past tense of English verbs:
 Regular verbs add -ed
 Irregular verbs have special forms (e.g., "go" → "went")
Function for regular verbs:
past_tense(base) = base + "-ed"
Function for irregular verbs:
past_tense_irregular("go") = "went"
past_tense_irregular("run") = "ran"
Application:
 For the verb "walk" (regular):
past_tense("walk") = "walk" + "-ed" = "walked"
 For the verb "go" (irregular):
past_tense_irregular("go") = "went"

2. Finding the Structure of Documents

Finding the structure of documents in NLP involves analyzing textual and layout cues to
identify and organize the hierarchical components such as titles, headings, paragraphs, lists,
tables, and sections. This process helps transform unstructured or semi-structured text into a
structured format, enabling better information extraction, navigation, and understanding.
Techniques often include rule-based approaches that leverage formatting patterns, machine
learning models that classify text segments, and layout analysis for documents like PDFs. By
accurately detecting the document’s structure, NLP systems can facilitate tasks like
summarization, indexing, and information retrieval, making the content more accessible and
meaningful for downstream applications.
2.1 Introduction
Documents have an internal structure: sentences, paragraphs, topics.
Automatic segmentation helps NLP tasks: parsing, translation, summarization.
 Internal Structure of Documents:
o Composed of sentences, paragraphs, and topics that organize content logically.
o Example: A research article has an introduction paragraph, methods section,
results, and conclusion, each with multiple sentences.
 Automatic Segmentation:
o The process of dividing a document into meaningful units without manual
effort.
o Example: Automatically separating a long article into individual sentences and
grouping related sentences into paragraphs or sections.
 Benefits for NLP Tasks:
o Parsing: Accurate sentence boundaries help in syntactic analysis.
 Example: Knowing where sentences start and end improves parsing
accuracy in complex texts.
o Translation: Segmenting text preserves context and coherence across
languages.
 Example: Translating paragraph-by-paragraph maintains the flow of
ideas.
o Summarization: Identifying topic boundaries helps extract key information.
  Example: Summarizing a report by focusing on sections like
"Findings" and "Conclusions" rather than entire documents.

2.2 Sentence Boundary Detection

Key Points:
Detects where sentences start and end.
Uses punctuation marks: ".", "?", "!".
Challenges:
Abbreviations: "Dr.", "Mr."
Quoted speech, ellipses, misspelling, codeswitching.

Example:
"Dr. Smith arrived." The period after "Dr." does not indicate sentence end.

2.3 Topic Boundary Detection

Dividing text into coherent segments focused on a single topic.

Important for information retrieval, summarization.
Example: News articles divided into different stories or sections.
Topic Boundary Detection involves dividing a text into segments, each focused on a single,
coherent topic. This helps in understanding the structure of the document and improves
various NLP tasks.
Why is it important?
 Enhances information retrieval by allowing systems to locate specific topics
quickly.
 Improves summarization by capturing key themes without mixing unrelated
information.
 Facilitates document understanding and organization.
Examples:
1. News Articles:
 o A news article might contain multiple stories or sections such as:
 Politics: "The government announced new policies today..."
 Economy: "Stock markets rose after the announcement..."
o Topic boundary detection divides the article into these sections, making it
easier to access specific information.
2. Research Papers:
o Sections like:
 Introduction: discussing background
 Methodology: describing experiments
 Results: presenting findings
 Discussion: interpreting outcomes
o Detecting these boundaries helps in summarizing or retrieving specific parts.
3. Long Documents or Reports:
o Dividing a corporate report into:
 Financial Overview
 Market Analysis
 Future Plans
o Making navigation and focused analysis easier.

2.4 Methods
Boundary Classification
Treats boundary detection as a classification problem.
Features: punctuation, capitalization, lexical cues.
Approaches:
Local models: Classify each candidate boundary.
Sequence models: Use context (e.g., CRFs).

Example:
Classify whether position after "..." is a sentence boundary.
Boundary Classification
  Approach:
Treats boundary detection as a classification task—deciding whether a given position
in the text is a topic boundary or not.
 Features Used:
o Punctuation: e.g., periods, question marks, exclamation points.
o Capitalization: e.g., start of a new paragraph or sentence.
o Lexical cues: words like "however," "furthermore," or transition phrases
indicating a new topic.
 Approaches:
o Local models:
Classify each candidate boundary independently based on features at that
point.
Example: Decide if the position after "..." (ellipsis) is a sentence boundary by
analyzing nearby words and punctuation.
o Sequence models:
Use context to improve classification, considering neighboring boundaries.
Example: Conditional Random Fields (CRFs) model the sequence of
boundaries, capturing dependencies like if one boundary is likely, the next is
too.
Example:
Imagine the sentence:
"The results were promising... However, further research is needed."
 The system considers the position after "..." (ellipsis).
 It analyzes features: punctuation (ellipsis), the following word "However" (a lexical
cue), and capitalization.
 Classification:
o Is this a boundary (start of a new topic/segment)?
o Answer: Yes, it likely is, because "However" indicates a new point or topic.

3. NLP Components & Steps

Natural Language Processing (NLP) involves several components and steps to enable
computers to understand, interpret, and generate human language.

Here’s an overview:
1. Core Components of NLP:
2. Tokenization
 3. Breaking down text into smaller units called tokens (words, sentences, or characters).
Example:
"Hello, world!" → ["Hello", ",", "world", "!"]
4. Part-of-Speech Tagging
5. Assigning grammatical tags (noun, verb, adjective, etc.) to each token.
Example:
"The cat sleeps" → [The/DT, cat/NN, sleeps/VB]
6. Named Entity Recognition (NER)
7. Identifying proper nouns like names, locations, organizations.
Example:
"Barack Obama was the 44th President of the USA" →
[Barack Obama (Person), USA (Location)]
8. Parsing
9. Analyzing the grammatical structure of sentences (syntax trees).
Example:Understanding the subject, verb, object relationships.
10. Semantic Analysis
11. Understanding the meaning of sentences and words.
Example:Recognizing that "bank" can mean a financial institution or riverbank
depending on context.
12. Discourse and Pragmatic Analysis
13. Understanding context, conversations, and implied meanings across sentences.
14. Typical Steps in NLP Workflow:
15. Text Preprocessing
16. Cleaning and preparing raw text (removing noise, lowercasing, etc.).
17. Tokenization
18. Splitting text into tokens.
19. Normalization
20. Converting words to a standard form (e.g., stemming, lemmatization).
21. POS Tagging & NER
22. Labeling tokens with grammatical tags and identifying entities.
23. Parsing and Syntactic Analysis
24. Building sentence structure trees.
25. Semantic Analysis
26. Interpreting the meaning.
27. Application-Specific Tasks
28. Summarization, translation, sentiment analysis, question-answering, etc.

3.1 Components of NLP

Natural Language Understanding (NLU): Transform human language into machinereadable

form.
Natural Language Generation (NLG): Convert data into natural language.
1. Natural Language Understanding (NLU)
 Definition:
NLU involves processing and interpreting human language so that machines can
understand its meaning. It transforms raw text or speech into a structured, machine-
readable form.
 Purpose:
To extract meaning, intent, entities, and context from human language.
 Example:
Input:
"Book me a flight to New York tomorrow."
NLU processes this and identifies:
o Intent: Book a flight
o Destination: New York
o Date: Tomorrow
The system understands what the user wants and the relevant details for executing the task.

2. Natural Language Generation (NLG)

 Definition:
NLG is the process of converting structured data or information into human-like
natural language text.
 Purpose:
To produce readable, coherent, and contextually appropriate language from data.
 Example:
Data:
{"destination": "New York", "date": "tomorrow", "status": "confirmed"}
NLG generates:
"Your flight to New York on tomorrow is confirmed."

3.2 Key Terminologies

Phonology: Study of sounds.
Morphology: Study of word formation.
Syntax: Sentence structure.
Semantics: Meaning of words and sentences.
Pragmatics: Contextual use.
Discourse: Connection across sentences.
World Knowledge: Common sense, background info.

Key Terminologies in NLP

1. Phonology
o Definition: Study of sounds and their patterns in language.
o Example:
The difference in sounds between "bat" and "pat". Phonology analyzes how
these sounds are produced and how they function in language.
2. Morphology
o Definition: Study of word formation and structure.
o Example:
The word "unhappiness" can be broken down
into "un-" (prefix), "happy" (root), and "-ness" (suffix). Morphology examines
how these parts form words.
3. Syntax
o Definition: Rules that govern sentence structure and word order.
o Example:
The sentence "The cat chased the mouse" follows English syntax rules.
Reversing the order to "Chased the cat the mouse" makes it ungrammatical.
4. Semantics
o Definition: Study of meaning in words and sentences.
o Example:
The sentence "The bank is open" can mean a financial institution or the side of
a river, depending on context. Semantics helps interpret such meanings.
5. Pragmatics
o Definition: Study of language use in context, including implied meanings.
o Example:
If someone says, "Can you pass the salt?", pragmatics recognizes it as a
request, not a question about ability.
6. Discourse
o Definition: How multiple sentences connect to form coherent conversations or
texts.
o Example:
In a conversation:
 Person A: "Where is the library?"
Person B: "It's next to the park."
Discourse analysis considers how these sentences relate and flow naturally.
7. World Knowledge
o Definition: Common sense, background information, and general knowledge
about the world.
o Example:
If someone says, "It's raining, so I took an umbrella," understanding that rain
usually warrants an umbrella involves world knowledge.

Complexity of Approaches in NLP with Examples

In NLP, different approaches vary in complexity based on how they process language data.
Here's an overview:

1. Rule-Based (Symbolic) Approaches

 Description:
Uses handcrafted rules and dictionaries to analyze and generate language.
 Complexity:
High initial effort to create rules, but relatively simple to implement for small
tasks.
Limitations: Difficult to scale, brittle with language variability.
 Example:
Grammar rules to identify noun phrases:
"The big dog" → noun phrase.
 Complexity Level:
Moderate to high in design, low in computational cost once rules are set.

2. Statistical and Machine Learning Approaches

 Description:
Uses large amounts of annotated data to learn patterns.
 Complexity:
Requires extensive data collection and preprocessing.
 Training models (like classifiers, neural networks) can be computationally intensive.
Once trained, inference is faster but depends on model size.
 Example:
Named Entity Recognition (NER) using a trained classifier to identify person names,
locations, etc.
 Complexity Level:
High during training, moderate to low during prediction.

3. Deep Learning Approaches

 Description:
Uses neural networks (like Transformers, LSTMs) to model language.
 Complexity:
Very high computational cost for training due to large models and data.
Requires powerful hardware (GPUs/TPUs).
Inference can also be resource-intensive.
 Example:
GPT models generating human-like text or translating languages.
 Complexity Level:
Very high in training, moderate in deployment with optimized models.

4. Hybrid Approaches
 Description:
Combines rule-based and statistical methods to balance interpretability and accuracy.
 Complexity:
Moderate to high, depending on integration level.
 Example:
Using rules for grammar correction and statistical models for context understanding.
 Rule-based approaches are simpler but less flexible.
 Statistical and deep learning methods are more powerful but require more
computational resources and data.
 The choice depends on the application's complexity, resources, and scalability needs.

Performance of Approaches in NLP with Explanation and Example

In NLP, the performance of different approaches is evaluated based on how well they
accomplish specific tasks such as translation, recognition, or understanding language. Key
metrics include accuracy, speed, scalability, and robustness.
1. Rule-Based Approaches
 Performance:
o High accuracy for simple, well-defined tasks (e.g., basic grammar rules).
o Limited flexibility; struggles with language variability, idiomatic expressions,
and ambiguities.
o Poor performance on large-scale or noisy data.
 Example:
A rule-based spelling corrector might correctly fix "recieve" to "receive" but fail with
context-dependent errors like "He went to the bank" (financial vs. river bank).
 Summary:
Reliable for simple, predictable tasks but not suitable for complex, real-world
language use.

2. Statistical and Machine Learning Approaches

 Performance:
o Improves accuracy with more data.
o Handles variability better than rule-based systems.
o Can generalize to unseen data if trained properly.
o Performance depends on quality and quantity of training data.
 Example:
Named Entity Recognition (NER) using a statistical classifier might correctly identify
"Barack Obama" as a person and "Paris" as a location with high accuracy on test data.
 Limitations:
o Requires large annotated datasets.
o May make mistakes with rare or ambiguous cases.
 Summary:
Good performance with sufficient data, but performance can degrade with
limited data.

3. Deep Learning Approaches

 Performance:
o State-of-the-art accuracy on many NLP tasks (translation, summarization,
question-answering).
o Can understand complex language patterns, context, and nuances.
 o Requires large datasets and computational resources.
 Example:
GPT-3 generating human-like text, translating languages with high fidelity, or
answering questions accurately.
 Limitations:
o Computationally expensive.
o Can sometimes generate plausible but incorrect or biased outputs.
 Summary:
Highest performance for complex tasks, but resource-intensive.

4. Hybrid Approaches
 Performance:
o Combines strengths of rule-based and statistical methods.
o Often achieves better performance than either alone by compensating for
each other's weaknesses.
 Example:
A system that uses rules for grammar correction and statistical models for context
understanding in translation.
 Summary:
Balanced performance, suitable for practical applications requiring both accuracy
and interpretability.

7. Applications of NLP
Information Retrieval & Web Search: Finding relevant documents.
Grammar Correction & Question Answering: Improving language quality.
Sentiment Analysis: Understanding opinions.
Text Classification: Categorizing texts.
Chatbots & Virtual Assistants: Humancomputer conversation.
Text Extraction: Extracting data from texts.
Machine Translation: Translating between languages.
Text Summarization: Summarizing long texts.
Market Intelligence: Analyzing market data.
AutoCorrect: Correcting spelling errors.
8. Challenges in NLP

Handling irregularities, ambiguities, and productivity.

Dealing with diverse languages and dialects.
Managing ungrammatical, noisy, and codeswitched data.