Scribd
Upload
1 views98 pages

NLP Complete Notes

The document provides an overview of Natural Language Processing (NLP), detailing its origins, challenges, and key concepts such as language modeling, grammar-based models, and statistical language models. It highlights the complexities of natural language, including ambiguity, context dependency, and the need for annotated data, while also discussing advancements in machine learning that have propelled NLP forward. Additionally, it covers applications of language modeling in various NLP tasks, including text generation, machine translation, and speech recognition.

Uploaded by

Rajeswari Bolla
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF or read online on Scribd
1 views98 pages

NLP Complete Notes

The document provides an overview of Natural Language Processing (NLP), detailing its origins, challenges, and key concepts such as language modeling, grammar-based models, and statistical language models. It highlights the complexities of natural language, including ambiguity, context dependency, and the need for annotated data, while also discussing advancements in machine learning that have propelled NLP forward. Additionally, it covers applications of language modeling in various NLP tasks, including text generation, machine translation, and speech recognition.

Uploaded by

Rajeswari Bolla
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF or read online on Scribd
12214601 NATURAL LANGUAGE PROCESSING UNIT 1 INTRODUCTION Origins and challenges of NLP ~ Language Modeling: Grammar-based LM, Statistical LM - Regular Expressions, Finite-State Automata — English Morphology, Transducers for lexicon and rules, Tokenization, Detecting and Correcting Spelling Errors, Minimum Edit Distance ‘The origins of Natural Language Processing (NLP) can be traced back to the 1950s and 1960s with the development of early computational linguistics and machine translation systems. Some key milestones include the development of the Georgetown-IBM experiment in 1954, which translated Russian sentences into English, and the creation of the first chatbot, ELIZA, in the mid-1960s. Challenges in NLP stem from the complexity and ambiguity inherent in natural language. Here are some of the key challenges: Ambiguity: Natural language is highly ambiguous, with words and phrases often having multiple meanings depending on context. Resolving this ambiguity is a major challenge in tasks such as parsing, word sense disambiguation, and machine translation. 2. Syntax and Semantics: Understanding the syntactic and semantic structure of sentences Is crucial for NLP tasks. However, natural language exhibits complex syntactic and semantic pattems that can be difficult for machines to parse and understand accurately. 3. Context Dependency: The meaning of a word or phrase can vary depending on the surounding context. Capturing and modeling context dependencies is essential for tasks like sentiment analysis, named entity recognition, and question answering, 4. Lack of Annotated Data: Many NLP tasks require large amounts of annotated data for training machine learning models. However, creating high-quality annotated datasets iming and expensive, especially for languages with limited resources. ity: Natural language varies greatly across different domains and genres (e.g., medical texts, legal documents, social media posts). Building NLP systems that perform well across diverse domains is challenging due to the need for domain adaptation and specialized knowledge. 6. Commonsense Reasoning: Understanding and reasoning about commonsense knowledge is essential for many NLP tasks, such as language understanding and generation, However, capturing and representing commonsense knowledge in a machine-readable format is still an ongoing research challenge. 7. Ethical and Bias Concerns: NLP systems can inadvertently perpetuate biases present in the data they are trained on, leading to issues such as algorithmic bias and fairness concems. Addressing these ethical considerations is crucial for the responsible development and deployment of NLP technologies. Despite these challenges, significant progress has been made in NLP in recent years, driven by advances in machine learning, deep leaning, and computational linguistics. Ongoing research continues to push the boundaries of what is possible in natural language understanding and generation. 2. Language modeling is a fundamental task in natural language processing (NLP) that involves predicting the next word in a sequence of words. The goal is to capture the statistical structure of language and generate coherent and contextually relevant text. Here's how language modeling typically works: 1. Input Sequence: language model takes as input a sequence of words or tokens. This sequence can be a sentence, paragraph, or longer text. 2. Context Encoding: The input sequence is encoded into a numerical representation that can be processed by the language model. This encoding captures the contextual information of the input, such as the meaning of words and their relationships within the sequence. 3. Prediction: Based on the encoded context, the language model predicts the probability distribution over the vocabulary of possible next words. This distribution indicates the likelihood of each word occurring given the context provided by the input sequence. 4, Sampling: To generate text, the language model can either select the word with the highest probability (greedy decoding) or sample from the probability distribution to introduce randomness and generate diverse text. Language modeling can be approached using different techniques: 1. Statistical Language Models: These models estimate the probability of word sequences based on statistical analysis of large text corpora. Techniques such as n- grams and smoothing methods are commonly used in statistical language modeling 2. Neural Language Models: Neural network-based approaches, particularly recurrent neural networks (RNNs) and more recently transformer-based architectures like GPT (Generative Pre-trained Transformer), have become prevalent for language modeling. ‘These models learn distributed representations of words and capture long-range dependencies in text 3. Fine-tuning: Pre-trained language models can be fine-tuned on specific tasks or domains to improve performance on downstream tasks like text generation, machine translation, and sentiment analysis. This fine-tuning process adapts the pre-trained model to the characteristics of the target dataset or task. Language modeling has numerous applications in NLP, including: + Text generation: Generating coherent and contextually relevant text, such as in chatbots, language generation systems, and content creation tools. + Machine translation: Modeling the probability of target language words given the source language context. * Speech recognition: Estimating the likelihood of spoken words or phrases given acoustic features. © Information retrieval: Ranking documents based on their relevance to a query by modeling the likelihood of word sequences in documents. + Summarization: Generating concise summaries of longer texts by predicting the most important words or phrases. Overall, language modeling plays a crucial role in various NLP tasks and continues to be an active area of research and development. Grammar-based language models (LMs) are a class of language models that rely on explicit, grammar rules to generate or understand natural language text. These models are based on linguistic theories and formal grammars, which define the syntax and structure of a language. Here's how grammar-based language models typically work: 1. Grammar Rules: Grammar-based LMs start with a set of grammar rules that describe the syntactic structure of the language. These rules define how words and phrases can be combined to form grammatically correct sentences. . Parsing: When generating or understanding text, the input is parsed according to the grammar rules to identify the syntactic structure of the input sentence. This involves breaking down the input into its constituent parts, such as words, phrases, and clauses, and determining how they relate to each other. 3. Rule Application: The grammar rules are then applied to the parsed input to generate or interpret text. These rules govern how words and phrases can be combined to form valid sentences according to the grammar of the language. 4, Constraints: Grammar-based LMs may incorporate additional constraints to ensure that the generated text adheres to specific criteria, such as style, domain-specific vocabulary, or semantic coherence. 5. Evaluation: The generated text is evaluated based on its grammaticality and coherence according to the rules of the grammar. This evaluation may involve checking for violations of grammar rules, semantic inconsistencies, or other lingui criteria. Grammar-based language models have several advantages: + Explicit Linguistic Knowledge: By encoding linguistic knowledge in the form of grammar rules, these models can capture intricate syntactic structures and language patterns, + _Interpretability: Since the grammar rules are explicitly defined, the behavior of grammar-based LMs is often more interpretable compared to black-box models like neural networks. However, grammar-based LMs also have limitations: + Scalability: Creating comprehensive grammar rules for natural languages can be challenging, especially for languages with complex syntax and semantics. As a result, grammar-based LMs may struggle to handle the full richness of natural language. + Coverage: Grammar-based LMs may not capture all linguistic phenomena, leading to gaps in coverage and potential errors in text generation or interpretation. Overall, while grammar-based language models provide a principled approach to natural language processing, they are often supplemented or replaced by data-driven approaches, such as statistical language models and neural language models, which can learn pattems directly from data without relying on explicit grammar rules. grammar-based language modeling using context-free grammar (CFG) and a probabilistic context-free grammar (PCFG). Examples: N-> "cat" [dog | "bal B-> "on" | "under" | "with" This grammar consists of rules for generating, 1. sentences (S), 2, noun phrases (NP), 3, verb phrases (VP), 4, prepositional phrases (PP), 5, determiners (Det), 6. nouns (N), 7. verbs (V), 8. prepositions (P). We start with the start symbol "S" and recursively apply the production rules until we derive a complete sentence: 1s 2. NP VP (using the rule S -> NP VP) 3. Det N VP (using the rule NP -> Det N) 4 N VP (using the rule Det -> "the") 5. NV NP (using the rule VP > V NP) 6. NV Det N (using the rule NP > Det N) 7. NV Det N PP (using the rule VP -> V NP PP) NV Det NP NP (using the rule PP -> P NP) NV Det NP Det N (using the rule NP -> Det N) Now we have a complete sentence: "the cat chased the dog on a ball." Statistical language modelling Statistical language modeling is a technique used to estimate the probability distribution of ‘word sequences in a language based on observed data. It forms the basis for many natural language processing tasks, such as speech recognition, machine translation, and text generation. Here's how statistical language modeling typically works: 1. Training Data: Statistical language models are trained on large amounts of text data, known as a corpus. This corpus contains sequences of words along with their frequencies of occurrence. n-gram Models: One of the simplest approaches to statistical language modeling is the n-gram model, where the probability of a word sequence is estimated based on the frequencies of occurrence of n-length sequences of words (n-grams) in the training data. For example, a bigram model (n=2) estimates the probability of a word given its preceding word, while a trigram model (n=3) estimates the probability of a word given its two preceding words. 3. Estimating Probabilities: Given a sequence of words w1, w2, ..., wn, the probability of the entire sequence P(w1, w2, ..., wn) is estimated as the product of the conditional probabilities of each word given its preceding context: POW, W2, «5 wn) © P(w1) * P(w2|w1) * P(w3|wl, w2) * .. * P(wnlwn-L, «+5 WI) ‘These probabilities are estimated from the frequencies of n-grams in the training data using techniques such as maximum likelihood estimation (MLE) or smoothed estimation methods like add-one smoothing or Kneser-Ney smoothing, 4, Backoff and Interpolation: To address data sparsity issues and improve the robustness of n-gram models, techniques like backoff and interpolation are often employed. Backoff involves using lower-order n-grams when higher-order n-grams have zero counts, while interpolation combines probabilities from different n-gram orders to smooth the probability estimates. 5. Application: Once trained, a statistical language model can be used for various NLP tasks. For example, in speech recognition, the language model helps to recognize the most likely sequence of words given the input speech signal. In machine translation, it guides the generation of fluent and grammatically correct translations. Statistical language modeling provides a simple yet effective framework for capturing the statistical properties of natural language. However, it has limitations such as the inability to capture long-range dependencies and the need for large amounts of training data to achieve good performance. More sophisticated approaches, such as neural language models, have been developed to address these limitations and achieve state-of-the-art results in many NLP tasks. 1. Speech Recognition: In speech recognition systems, statistical language models are used to decode the most likely sequence of words given an input speech signal. The language model helps to distinguish between alternative word sequences and improve the accuracy of the recognized text. For example, given the audio signal "I want to eat," the language model may help decide between "I want two eat” and "I want to eat.” 2. Autocomplete and Text Prediction: Statistical language models power autocomplete and text prediction features in applications such as search engines, messaging apps, and word processors. These models suggest the most likely next word or phrase based cn the context of the Input text. For example, when typing "I am going to," the Janguage model may suggest "the store” or "the park” as likely completions. 3. Machine Translation: In machine translation systems, statistical language models help generate fluent and grammatically correct translations by estimating the probability of different word sequences in the target language. The language model guides the selection of the most likely translation given the source text. For example, given the source text "Je suis content” in French, the language model may help choose between "I am happy" and "I am satisfied" as translations. 4, Text Generation: Statistical language models can be used to generate coherent and contextually relevant text for various applications, such as chatbots, content creation tools, and language generation systems. These models estimate the probability of word sequences and use sampling techniques to generate new text based on the leamed language patterns. For example, a language model trained on news articles may generate new headlines or article summaries. 5, Spell Checking and Correction: Statistical language models are used in spell checking and correction systems to identify and correct spelling errors in text. These models estimate the likelihood of word sequences and suggest corrections based on the context of the input text. For example, when detecting the misspelled word "recieve," the language model may suggest "receive" as a likely correction based on its training data. These examples demonstrate how statistical language modeling is applied in various NLP tasks to improve the accuracy, fluency, and naturalness of text processing and generation. a simple example of statistical language modeling using a bigram model. Suppose we have a small corpus consisting of the following sentences: 1, "Llike to eat apples.” 2, “Apples are delicious." 3. "Like to eat bananas.” We can use this corpus to build a bigram language model, which estimates the probability of, cach word given its preceding word. Here's how we can do it: 1. Tokenization: First, we tokenize the sentences into individual words, removing punctuation and converting everything to lowercase. This gives us the following, tokenized corpus: 2. Counting Bigrams: Next, we count the occurrences of bigrams (pairs of consecutive words) in the tokenized corpus: Ci. ik ("like", "to"): 2 ("to", eat"): 2 "eat", "apples"): 1 apples”, "are"): 1 (‘are", "delicious"): 1 ("eat", "bananas": 1 3. Estimating Probabilities: We calculate the probability of each word given its preceding word using maximum likelihood estimation (MLE) P("like" | "i") = Count("i like") / Count("t") PC*to" | "lke") = Count("like to") / Count("like") = 2/2 = 1.0 P(“eat" | "to") = Count("to eat") / Count("to") = 2/ P("apples” | "eat") = Count("eat apples") / Count("eat" P(“are" | “apples") = Count("‘apples are") / Count("apples P("delicious” | "are") = Count("are delicious") / Count("“are P("bananas" | "eat") = Count("eat bananas") / Count("eat") = 1/2= 0.5 Now, we have a bigram language model that can estimate the probability of word sequences. For example, if we want to compute the probability of the sentence "I like to eat bananas," we can multiply the probabilities of the bigrams: PC'i") * PC"like" | "i" * P("to” | "like") * P("eat" | "to") * P("bananas” | "eat") = 1.0*1.0* 10" 1.0705 =05 This shows that according to our bigram model, the probability of the sentence "I like to eat bananas” is 0.5. Regular expressions (regex) are powerful tools used in natural language processing (NLP) for pattern matching and text processing tasks. They allow for efficient searching, extraction, and manipulation of text based on specified patterns. Here are some common applications of regular expressions In NLP: . Tokenization: Regular expressions can be used to split a text into tokens, such as words or sentences. For example, \w*+ matches one or more word characters, effectively tokenizing words in a sentence. 2. Text Cleaning: Regular expressions are useful for cleaning and preprocessing text data by removing unwanted characters, punctuation, or formatting. For instance, \W matches any non-word character, which can be used to remove punctuation marks from text. 3. Pattern Matching: Regular expressions enable the extraction of specific patterns or entities from text data. For example, \b\d{3)-\d{3}\d(4)\b matches phone numbers in the format XXX-XXX-XXXX. 4, Named Entity Recognition (NER): Regular expressions can be used as simple rules for identifying named entities such as dates, emails, or URLs in text. For example, a regex pattern can match strings that resemble email addresses (\b[A-Za-20-9,_ 96+] +@[A-Za-20-9.-]+\,[A-Z|a-z] {2,\b). 5. Information Extraction: Regular expressions can aid in extracting structured information from unstructured text, such as dates, addresses, or numerical data. For instance, \b\d{2}/d{2}/d{4}\b matches dates in the format MM/DD/YYYY. 6. Text Normalization: Regular expressions can be used to normalize text by converting it to a standard format. For example, \b[A-Z]+*\b matches all uppercase words, which can be converted to lowercase for normalization. 7. Text Segmentation: Regular expressions can help in segmenting text into meaningful units, such as paragraphs or sections. For example, \n\n matches two consecutive newline characters, which can be used to split text into paragraphs. While regular expressions are powerful, they also have limitations. They may not handle complex patterns or variations in text well, and writing and maintaining complex regex patterns can be challenging. Additionally, regular expressions are often not robust to noisy or ambiguous text data. In such cases, more advanced techniques, such as rule-based systems or machine learning models, may be more suitable. Example simple example of a regular expression in Python that matches email addresses: import re # Sample text containing email addresses text = "Contact us at info@[Link] or support@[Link] for assistance.” # Regular expression pattern to match email addresses pattern = r'\b[A-Za-z0-9._%+-]+@[A-Za-z0-9.-]+\.[A-Zja-z] {2, }\b" # Find all email addresses in the text matches = [Link](pattern, text) # Print the matches print(matches) Output: [info@[Link],, ‘support@[Link]'] In this example: The regular expression pattern r\b[A-Za-20-9. {2,}b' consists of several components: ‘©. \b: Word boundary anchor to ensure that the email address starts and ends with a word boundary. © [A-Za-z0-9,_%+-]+: Matches one or more characters that can occur in the local part of the email address (before the '@’ symbol), including letters, digits, dots, underscores, percent signs, plus signs, and hyphens. © @:Matches the ‘@’ symbol. © [A-Za-20-9,-]+: Matches one or more characters that can occur in the domain part of the email address (after the '@" symbol), including letters, digits, dots, and hyphens. © \ Matches a literal dot" (used to separate domain levels). © [A-Zla-z]{2,}: Matches two or more letters (upper or lowercase) representing the top-level domain (TLD), such as ‘com’, ‘net’, ‘[Link]’, etc. ©. \b: Word boundary anchor to ensure that the email address ends with a word boundary. The [Link]() function is used to find all occurrences of the pattern in the given text. The matches found are printed, which are the email addresses present in the text. 96+-}+@[A-Za-20-9. Finite State Automata (FSA) or Finite State Machines (FSM), which are models used in computer science and mathematics to represent systems that can be in only a finite number of states at any given time. These automata are widely used in various fields, including natural language processing, compiler design, and digital circuit design. Definition: A Finite State Automaton is defined by a finite set of states, a finite set of input symbols, a transition function that describes how the automaton transitions between states based on input symbols, a start state, and a set of accept states. ‘Types of FSAs: © Deterministic Finite Automaton (DFA): Ina DFA, for each state and input symbol, there is exactly one transition leading to a next state. DFAs are commonly used in lexical analysis and pattern matching. © Nondeterministic Finite Automaton (NFA): In an NFA, there can be multiple transitions for a given state and input symbol, or there can be e- transitions (transitions without consuming an input symbol). NFAs are often used in regular expression matching. Operations on FSAs: (© Union, intersection, and complementation of automata. © Concatenation, Kleene star (closure), and concatenation of automata. © Minimization of DFAs to reduce the number of states while preserving the language recognized by the automaton. Applications: ‘© Regular expression matching: FSAs are used to implement regular expression engines. © Lexical analysis: DFAs are used to recognize tokens in programming Tanguages. ‘© Pattern recognition: FSAs can be used to model and recognize pattems in data 5. Limitations: © FSAs are limited in their expressive power compared to more complex automata models like pushdown automata and Turing machines. © They can only recognize regular languages, which are a subset of the languages recognized by context-free grammars. Let's consider a simple example of a deterministic finite automaton (DFA) that recognizes strings over the alphabet {0, 1} that end with "01". Here's the DFA: 1. States: {q0, a1, 42} 2. Alphabet: {0, 1} 3. Start state: q0 4. Accept states: {q2} 5. Transition function: ‘State ° 1 co «0 a a 0 a 2 0 at + The start state is q0. + The accept state is q2. + The DFA transitions from state to state based on the input symbols. For example, if it reads a 0 in state q0, it stays in q0, if it reads a 1 in q0, it transitions to ql, and so on. + The string will be accepted if it ends in state q2, ating that it ends with "0 English morphology is an essential aspect of natural language processing (NLP) that deals with the structure and formation of words in the English language. It encompasses various morphological processes, such as inflection, derivation, compounding, and others. Understanding English morphology is crucial for tasks like tokenization, stemming, Jemmatization, and part-of-speech tagging. Here's a brief overview of some key concepts in English morphology and their relevance in NLP: 1. Inflection: Inflection involves adding affixes (prefixes, suffixes, infixes) to a base ‘word to indicate grammatical features such as tense, aspect, mood, number, case, and gender. For example: © Walk (base form) -> walks, walked, walking (inflected forms) © Cat (singular) -> cats (plural) 2. Derivation: Derivation involves forming new words by adding affixes to base words, resulting in changes in meaning or word class. For example: © Happy (adjective) -> happiness (noun) © Nation (noun) -> national (adjective) 3. Compounding: Compounding involves combining two or more words to form a new word with a new meaning. Compounds can be open (e.g., Ice cream), hyphenated (e.g,, well-being), or closed (e.g., keyboard). 4. Stemming: Stemming is the process of reducing words to thelr base or root forms by removing affixes. It aims to normalize words so that different inflected forms map to the same stem. For example: © Running, runs -> run (stem) © Cats, cat's -> cat (stem) 5. Lemmatization: Lemmatization is similar to stemming but considers the context of words to determine thelr base forms (lemmas). It typically involves dictionary lookup and morphological analysis to ensure that the lemma is a valid word. For example: © Running, runs -> run (lemma) ‘© Better, best -> good (lemma) 6. Part-of-Speech Tagging: Part-of-speech tagging assigns grammatical categories (nouns, verbs, adjectives, etc.) to words in a sentence. Morphological features play a significant role in determining the part of speech of a word. For example: © Running (verb) © Cat (noun) © Happy (adjective) Morphological Analysis: Morphological analysis involves breaking down words into their constituent morphemes (the smallest units of meaning). This process is essential for understanding the Internal structure of words and for various NLP tasks. In NLP, algorithms and models are developed to handle these morphological processes efficiently, enabling tasks such as text normalization, syntactic analysis, semantic analysis, and more. Proper handling of English morphology enhances the accuracy and effectiveness of NLP systems across a wide range of applications. English morphology in natural language processing (NLP) involves analyzing the structure and formation of words in the English language. Morphology deals with the internal structure of words and how they are formed from smaller meaningful units called morphemes. Here's an example Illustrating English morphology. Consider the word “unhappiness.” 1. Root: The root or base of the word is "happ} 2. Affix (© “un-" is a prefix indicating negation or reversal. © “snes” is a suffix indicating the quality or state of being. 3. Morphemes: © “un-" (prefix) © “happi-" (root) co "-ness” (suffix) 4, Morphological Analysis: Prefix: "un-": negation © Root: "happy": feeling or showing pleasure © Suffix: "-ness": state or quality 5. Word Formation: The word "unhappiness" is formed by combining the prefix "un- with the root “happy” and the suffix "-ness," resulting in the meaning "the state of not being happy" or "lack of happiness.” In NLP, understanding English morphology is crucial for various tasks, including: 1. Tokenization: Breaking text into words or tokens, considering morphological boundaries. 2. Stemming: Reducing words to thelr root form (stem) by removing affixes. For example, stemming "unhappiness" would result in "happi.” 3. Lemmatization: Similar to stemming but produces the base or dictionary form of a word (lemma). For “unhappiness,” the lemma would be "happiness." 4. Part-of-Speech Tagging: Identifying the grammatical category of each word based on ts morphology. For example, "unhappiness" would be tagged as a noun. 5. Named Entity Recognition (NER): Identifying named entities like person names, organization names, etc., which often have specific morphological patterns. Understanding English morphology helps NLP systems better comprehend and process text, enabling tasks such as sentiment analysis, machine translation, information retrieval, and more. 1. Lexical Transduction: © Lexical transduction refers to the process of mapping words from one form to another based on specific rules or patterns. This could involve transformations such as stemming or lemmatization, where words are reduced to their base or dictionary forms. © For example, in English morphology, converting the word "running" to its base form "run" involves a lexical transduction rule that removes the suffix "-ing.” 2. Rules for Lexical Transduction: © Lexical transduction rules are typically based on linguistic knowledge and patterns observed in the language. These rules define how words are transformed from one form to another. © Rulles can involve the application of affix stripping, suffix removal, or applying irregular transformation patterns. © Example lexical transduction rule: "If a word ends with ' suffix to obtain the base form.” 3. Grammatical Transduction: © Grammatical transduction refers to the process of transforming sentences or phrases from one grammatical form to another. This could involve tasks such as converting active voice to passive voice, changing tense, or altering sentence structure. 0 Example: Converting the sentence "The cat chased the mouse” from active voice to passive voice results in "The mouse was chased by the cat.” 4. Rules for Grammatical Transduction: © Grammatical transduction rules are based on syntactic and grammatical structures. These rules define how sentences or phrases are transformed while preserving their meaning. © Rules can involve rearranging word order, changing verb conjugation, or altering grammatical features. ng’, remove the © Example grammatical transduction rule: "To convert active voice to passive voice, move the object of the active sentence to the subject position and change the verb form to the passive voice." ‘Tokenization is a fundamental task in natural language processing (NLP) that involves breaking down a text into smaller units called tokens. These tokens can be words, phrases, symbols, or other meaningful elements, depending on the context and the specific requirements of the task at hand. Here's an overview of tokenization in NLP: 1, Word Tokenization: © Word tokenization, also known as word segmentation or word splitting, involves dividing a text into individual words based on whitespace or punctuation boundaries. © Example: The sentence "Tokenization is an important NLP task” can be tokenized into ["Tokenization", "is", "an", "important", "NLP", "task"]. 2. Sentence Tokenization: (©. Sentence tokenization involves splitting a text into individual sentences based on punctuation marks like periods, exclamation marks, and question marks. © Example: The paragraph "This is the first sentence. This Is the second sentence! And this is the third sentence?" can be tokenized into ["This is the first sentence.”, "This is the second sentence!”, "And this is the third sentence?"]. 3. Subword Tokenization: ‘© Subword tokenization involves dividing words into smaller units, such as morphemes or character n-grams. This approach is commonly used in Tanguages with complex morphology or for handling out-of-vocabulary words. © Example: In subword tokenization, the word "tokenization" can be split into ['to", "ken", "iza", “tion"] of ["token", "Iza, "tion'] 4, Tokenization Challenges: © Tokenization can be challenging for languages with complex word boundaries or agglutinative morphology. © Ambiguity in tokenization can arise due to punctuation marks, abbreviations, contractions, and compound words. 5. Tokenization Libraries: © Various NLP libraries provide built-in functions for tokenization, including, NLTK (Natural Language Toolkit), spaCy, and the tokenization module in the ‘TensorFlow and PyTorch frameworks. 6. Preprocessing: (© Tokenization is typically the first step in text preprocessing, followed by tasks such as lowercasing, stemming, lemmatization, and stop word removal. Detecting and correcting spelling errors is an important task in natural language processing (NLP) and can significantly improve the accuracy and readability of text. Here's an overview of how spelling errors are detected and corrected: 1. Spell Checking: ‘© Spell checking involves identifying words in a text that are not found in a dictionary or known vocabulary. ©. Spell checkers compare each word in the text against a dictionary or a list of known words to determine if itis spelled correctly. © Words that are not found in the dictionary are flagged as potential spelling errors. 2. Candidate Generation: © Once spelling errors are detected, candidate words are generated as potential replacements for the misspelled words. © Candidate generation techniques may involve: Generating possible corrections by applying operations such as insertion, deletion, substitution, or transposition of characters. + Using statistical language models to suggest the most likely replacements based on context. 3. Candidate Ranking: © After generating candidate replacements, a ranking algorithm is applied to score and rank the candidate corrections. © Ranking algorithms consider factors such as: + Edit distance: How many edits are required to transform the misspelled word into each candidate. + Language model probabilities: How likely each candidate is based on the surrounding context. = Frequency of occurrence: How frequently each candidate appears in a large corpus of text. 4. Correction Selection: (© The correction selection process involves choosing the highest-ranked candidate as the replacement for the misspelled word. co Insome cases, multiple candidate corrections may be suggested to the user for manual selection. 5. Contextual Spelling Correction: © Contextual spelling correction takes surrounding context into account when detecting and correcting spelling errors. © Contextual information, such as adjacent words, grammar, syntax, and semantics, can help improve the accuracy of spelling correction. 6. Evaluation and Feedback: (© Spell checkers are often evaluated using manually annotated datasets or user feedback to assess their accuracy and effectiveness. © Continuous improvement based on user feedback helps refine and enhance spelling correction algorithms over time. In natural language processing (NLP), the minimum edit distance (also known as Levenshtein distance) is a metric used to quantify the similarity between two strings by ‘measuring the minimum number of single-character edits (insertions, deletions, or substitutions) required to transform one string into the other. It’s a fundamental concept used in various NLP tasks, such as spell checking, text correction, and approximate string matching. Here's how it works: 1. Definition: © Given two strings, A of length m and B of length n, the minimum edit distance between them, denoted as D(A, B), is the minimum number of edits required to transform string A into string B. 2. Operations: (© Insertion: Add a character to string A. © Deletion: Remove a character from string A. (© Substitution: Replace a character in string A with another character. |. Dynamic Programming Algorithm: © The minimum edit distance can be efficiently computed using dynamic programming. © The algorithm fills in a matrix where each cell (i j) represents the minimum edit distance between the substrings A(0:i] and Bi0-j). © The algorithm iterates through each position in the matrix, updating the values based on the minimum cost of the possible edit operations. © The final value in the bottom-right corner of the matrix represents the minimum edit distance between the two strings. 4. Application: (© Spell Checking: Determine the closest words to a misspelled word by computing the minimum edit distance between the misspelled word and all words in a dictionary. © Approximate String Matching: Find strings in a database that are similar to a given query string by computing the minimum edit distance between the query string and database strings. © OGR (Optical Character Recognition): Correct errors in OCR output by comparing the recognized text with the original text using minimum edit distance. 5, Example: © For example, consider the strings "kitten" and "sitting" + The minimum edit distance between them is 3. + One possible sequence of edit operations is: substitute 'k’ with 's', substitute 'e' with '/, and insert’ at the end. UNIT Il WORD LEVEL ANALYSIS Unsmoothed N-grams, Evaluating N-grams, Smoothing, Interpolation and Backoff = Word classes, Part-of-Speech Tagging, Rule-based, Stochastic and Transformation-based tagging, Issues in PoS tagging Unsmoothed N-gram: Definition: © Ann-gram isa contiguous sequence of n items (words, characters, or tokens) ‘within a larger sequence of text. © Unsmoothed n-grams involve calculating the probability of observing each n- gram in the training data directly from the counts of those n-grams, without any adjustments for unseen or rare events. 2. Probability Estimation: © Given a corpus of text, the probability of a word sequence is estimated by counting the occurrences of each n-gram in the training data and dividing by the total count of all n-grams. © For example, the probability of observing the word sequence "the cat sat” using tigrams would be estimated by counting the number of occurrences of the trigram "the cat sat" and dividing by the total count of all trigrams in the corpus. 3. Challenges: ‘© Unsmoothed n-grams can suffer from data sparsity issues, especially for higher-order n-grams or in corpora with limited training data. © If an n-gram is not observed in the training data, its probability will be zero, which can lead to severe underestimation of the likelihood of unseen word sequences. 4. Usage: (© Despite their limitations, unsmoothed n-grams can still be useful in certain, contexts, particularly for small or specialized corpora where data sparsity is less of an issue. © Unsmoothed n-grams can serve as a baseline model for comparison with more sophisticated language models that incorporate smoothing techniques. 5, Evaluation: © The performance of unsmoothed n-gram models can be evaluated using standard metrics such as perplexity or accuracy on a held-out test set. © Perplexity measures how well the model predicts the test data and can indicate the effectiveness of the language model in capturing the distribution of word sequences in the training corpus. Unsmoothed N-grams Language modeling Is the way of determining the probability of any sequence of words. Language modeling is used in a wide variety of applications such as Speech Recognition, Spam filtering, etc. In fact, language modeling Is the key aim bebind the implementation of many state- of-the-art Natural Language Processing models. Methods of Language Modelings: Two types of Language Modelings: * Statistical Language Modelings: Statistical Language Modeling, or Language Modeling, is the development of probabilistic models that are able to predict the next, word in the sequence given the words that precede. Examples such as N-gram language modeling. * Neural Language Modelings: Neural network methods are achieving better results, than classical methods both on standalone language models and when models are incorporated into larger models on challenging tasks like speech recognition and machine translation. A way of performing a neural language model is through word embeddings. N-gram N-gram can be defined as the contiguous sequence of n items from a given sample of text or speech. The items can be letters, words, or base pairs according to the application. The N-grams typically are collected from a text or speech corpus (A Iong text dataset). N-gram Language Mo: An N-gram language model predicts the probability of a given N-gram within any sequence of words in the language. A good N-gram model can predict the next word in the sentence i.e the value of p(wih) Example of N-gram such as unigram (““This”, “article”, “is”, “on”, “NLP”) or (‘This article’, ‘article is’, “is on’,’on NLP’). gram Now, we will establish a relation on how to find the next word in the sentence using - We need to calculate p(wih), where is the candidate for the next word. For example in the above example, lets’ consider, we want to calculate what is the probability of the last word being “NLP” given the previous words: P(NLPithis article ison) After generalizing the above equation can be calculated as: plu wi, wa, wystr4) or POW) = P(waltr, 2.--te) But how do we calculate it? The answer lies in the chain rule of probability: PAB) = "hi P(A, B) = P(A\B)P(B) Now generalize the above equation: PUM, P(wywyt...tp) TI, P(wiltiwe...trn) Xn) = P(X1)P(Xa|X1)P(X3|X1, X2) P(X X Simplifying the above formula using Markov assumptions: Pl ww, wa, tina) © Pw |wits trea) * For unigram: Pw, ttn) * TT, Plu) + For Bigram: P(wy|wy wa, ..wy1) = P(welwy1) +# imports import string import random import nitk [Link](punkt’) [Link](‘stopwords’) [Link]( reuters’) from [Link] import reuters from nitk import FreqDist # input the reuters sentences sents =[Link]() # write the removal characters such as set([Link](‘english’)) [Link] = string,punctuation +"™4"™+"4"+ Stopwords and punctuation stop_words = string. punctuation removal_list = list(stop_words) + list([Link])* ['It'rt'] removal_list Evaluating N-grams Metrics for Language Modelings Entropy: Entropy, as a measure of the amount of information conveyed by Claude Shannon. Below is the formula for representing entropy H(p) = Fl): (~log(p(z))) * Cross-Entropy: It measures the ability of the trained model to represent test data wr. H(p) = Diy M—Loge(p(wy|wi-*))) The cross-entropy is always greater than or equal to Entropy i.e the model uncertainty can be no less than the true uncertainty. * Perplexity: Perplexity is a measure of how good a probability distribution predict: a sample. It can be understood as a measure of uncertainty. The perplexity can be calculated by cross-entropy to the exponent of 2. 0 rose Bnirony Following is the formula for the calculation of Probabi the language model, normalized by the number of wor PPW) = 9/11 For Example: Paar wad * Let's take an example of the sentence: ‘Natural Lai predicting the first word, let's say the word has the word P(word | ) The 0.4 Processing 0.3 Natural 0.12 Language 0.18 * Now, we know the probability of getting the first word as natural. But, what's the probability of getting the next word after getting the word “Language* after the word Natural". word P(word | ‘Natural’ ) The 0.05 Processing 0.3 Natural 0.15 Language 0.5 Interpolation and Backoff In unigram prior smoothing, we replace (1/V) with P(W1). This includes Interpolation as ‘we include Unigram result in Bigram calculation. (Read Interpolation below). This works well but still cannot we used for Language Modelling, Add one smoothing makes massive changes in actual data. Its used in text-classification where the number of zeros are not large. Backoff : Sometimes we don’t have enough data to trust our k-model , so we move to lower model Language model. INTERPOLATION: Mix Unigram, Bigram and ‘Trigram, Linear Interpolation: It is of 2 types. 4. Simple Interpolation: L1 P(Wi) + L2 P(Wi|Wi-1) + L3 P(Wi|Wi-2Wi-1); L1+L2+L3 = 1k 2. Lambdas conditional Interpolation: Lambdas depend on context. ‘The value of these lambdas can be calculated if we have a dev set/training data to set these lambdas to maximize the likelihood of these models. Open vs Closed Vocabulary tasks: If we know all the words in advance then its a close Vocabulary. But many times we don’t know all words. In our test set there might occur OOV (Out of Vocabulary ) words. One way to deal with them is to create a special token called . Any word which has low probability while training is changed to and then the model is treated as if the word is there. At decoding time, we change the unseen word to and then compute its probability want the Language Model. Smoothing for Large N-Grams (Web-scale-N-Grams): We use Stupid Backoff technique. P(WilWik ... Wi-L) = { simple probability formula } but if count(Wi-k .... Wi) is less than some threshold then we use k* P(WilWi-k+1 .... Wiel). Where k is some fraction and this can be best calculated by our dev set data. Stupid backoff produces scores rather than probabilities. And this works quite well for large scale N-Grams. Add-K does not work good for Language modelling, Stupid backoff works well for Large N-Grams, Lets start with Good Turing smoothing. Good Turing Smoothing Ne = Frequency of frequency c. Example : Abhinav I am Abhinav am 1 this this = 1;1=2;am=2; Abhinav 2 NL=1;N2=3 Read the intuition of Good Turing smoothing here. Done by leave one out validation and by taking a held set. Very well explained here (from 11th Minute). P (new things occurring ) = NI /N 3 Generalizing: c* = (c+1)*Ne+1 / Ne And P = c* / N. ‘Therefore in case of new things, c* = 0 as we have not observed it earlier. After first few N’s namely NO,NI ... N10, we replace the N’s by a smooth function as there will be gaps. Say N127 can be zero. Therefore we replace with the best fit paralog function. Kneser Ney Smoothing First do absolute discounting (as a result of good turing smoothing). But we see the discounting factor is nearly equal to 0.75. So we do absolute discounting and then do interpolation — Discounting + (L(Wi-1)*P(w) ). Instead of P(w) (Unigtam probability) {How likely is w}, Pcontinuation(w){How likely is w to appear as a novel continuation} is a better estimate. P continuation (w) = Words which precede w / Total word bigtams. A frequent word like Fransisco will have low continuation probability as it only appears, after San. P kn (Wi | Wi-1) = (count (Wi-1Wi) — d)/count (Wi-1) + L(Wi-1) Peont(Wi) Kneser Ney Smoothing for N-Grams is as below: Pkn( wi | wi-an+l ... wi-l) = [ max( countkn( wi-n+1... wi) —d, 0) ] /[ countkn( wi- n+L,.. wie )] + O( wi-n+1 .... wi-l ) x Pkn( wi | wi-n*2..... wi-l ) Where: ckn(+) =the actual count(+) for the highest order n-gram + the actual count(+) for the highest order n-gram. or continuation_count(+) for lower order n-gram => continuation_count = Number of unique single word contexts for WORD CLASSES: ‘Words can be grouped into classes referred to as Part of Speech (PoS) or morphological classes Traditional grammar is based on few types of PoS (noun, verb, adjective, preposition, adverb, conjunction, etc..) “More recent models are based on a larger number of classes 45 Penn Treebank 87 Brown corpus 146 C7 tagset ‘The word PoS provides crucial information to determine the roles of the word itself and of the words close to it in the sentence knowing if a word is a personal pronoun (I, you, he/she... ) or a possessive pronoun (my, ‘your, his/her;...) allows a more accurate selection of the most probable words that appear in its neighborhood (the syntactic rules are often based on the PoS of words) €.g. possessive pronoun - noun vs. personal pronoun ~ verbs ‘The 4 largest open classes of words, present in most of the languages, are ® nouns ® verbs » adverbs * adjectives Nouns are concrete terms (e.g. ship, table), abstractions (e.g. relationship, function), verb-like terms (e.g. pacing, pricing) ‘They can be functionally tied to determiners (the ship, a ship, .) and they can assume the plural form (the ships), etc.. They are traditionally divided into proper nouns (e.g. Marco, Italy) and common nouns (e.g. book, lecture) In many languages common nouns are also divided count nouns (they have the plural form) and mass nouns (they are used only in their singular form, e.g. snow, communism) Word classes- verbs & adjectives + The class of verbs includes most of the words that refer to actions and processes © to write, to go, to eat * they have “some” morphological inflections + In English non-3"-person-sg (eat), 3"-person-sg (eats), progressive (eating), past-participle (eaten), past perfect (ate) + Asspecial class of verbs is that of auxiliary verbs (to be, to have) + The class of adjectives contains terms describing properties or qualities © Most of the languages have adjectives for concepts like color (white, red,..), age (young, old,..) quality (good, bad....), ete Word classes- adverbs + Usually adverbs are used to modify other terms (not only verbs) ¢ Directional or locative adverbs specify the direction or location of a given action (here, there, up, ..) + Degree adverbs specify the extent of an action, process or property (extremely, very,...) © Manner adverbs describe the modality of some action or process (slowly, delicately, smartly,..) + Temporal adverbs describe the time for an action or event (yesterday, today, before, after, later, Monday...) + The class of adverbs is somehow heterogeneous + Some adverbs are similar to nouns (e.g. Monday — we will meet Monday, we meet on Mondays) PoS tagging & tags + PoS tagging consists in assigning a tag to each word in a document The selection of the employed tagset depends on the language and specific application The input is a word sequence and the employed tagset while the output is the association of each word to its “best” tag ‘There may exist more tags for a given word (ambiguity) Did/VED youPP | yourlPP$ belongings/NNS 2/2 INN The PoS tagger task is to solve these ambiguities by selecting the most appropriate tag given the word context + ‘The percentage of ambiguous words is not too high, but among them there are very frequent words (e.g. can — Auxiliary verb, Noun, Verb, still has 7 compatible tags — adj, adv, verb, noun) PoS tagging algorithms + Rule-based taggers * The are based on the “handcrafting” of a large rule-base that specifies the conditions to be verified to assign a specific tag in the ambiguous cases + eg. a word is a noun ifit is preceded by a determiner + Probabilistic taggers © They revolve ambiguities by estimating the probability that a given word as a specific tag in the observed context. The parameters for the probability model are estimated on a reference corpus. + Other approaches © tagging can be cast as a classification task (each tag corresponds to a class and the classifiers exploits features that describe the context — e.g. features of the words on the left/right of the considered word) * Taggers can exploits rules learnt from examples Rule-based PoS tagging + Two step process (e.g. ENGTWOL Voutilainen, 1995) » Word tagging using a lexicon (more than one tag can be assigned to each word) exploiting morphological /orthographic rules Ne Noun Verb Pavov PAVLOV | _N NOMSG PROPER PCpP2: Past Pariciple HAVE: V_ PAST VFIN SVO ADV: Adverb Have __| pcP2svo PRON: Pronoun [shown |SHOW | PCP2/SvOO SVO SV DET: Determiner thet —_~|THAT OV ‘GS: Subordinting Conjunction THAT [PRON |DEM SG ——_—— mat DET |CENTRAL DEM 56 '8VOO: Subject Verb-Object-Object NOM: non genitive (salvation SALIVATION| N/NOMSG ‘VEIN: fit verb DEM: demonstrative * Application of rules to select only one tag among those assigned to each word (rules exploit the word context) Rules + Rules are aimed to removing the cases that are not compatible with the context In ENGTWOL there are about 1100 rules ‘ADVERBIAL-THAT RULE ‘input: “that” if (+1 AVADV/QUANT); // the following word is an adjective, adverb orquantifier (2SENT-LIM); _// and the following one is a sentence boundary (NOT-1SVOC/A); // and the preceding word is a verb like “consider” ‘// that admits an adjective as object (I consider that good) then eliminate non-ADV tags else eliminate ADV tag ENGTWOL has also probabilistic information ‘onstraints and it may exploit syn! tic Stochastic POS Tagging Another technique of tagging is Stochastic POS Tagging. Now, the question that arises here is which model can be stochastic. The model that includes frequency or probability (statistics) can be called stochastic. Any number of different approaches to the problem of part-of-speech tagging can be referred to as stochastic tagger. The simplest stochastic tagger applies the following approaches for POS tagging ~ Word Frequency Approach In this approach, the stochastic taggers disambiguate the words based on the probability that a word occurs with a particular tag. We can also say that the tag encountered most frequently with the word in the training set is the one assigned to an ambiguous instance of that word. The main issue with this approach is that it may yield inadmissible sequence of tags. ‘Tag Sequence Probabilities It is another approach of stochastic tagging, where the tagger calculates the probability of a given sequence of tags occurring, It is also called n-gram approach. It is called so because the best tag for a given word is determined by the probability at which it occurs with the n previous tags. Properties of Stochastic POST Tagging Stochastic POS taggers possess the following properties ~ + This POS tagging is based on the probability of tag occuning, + It requires training corpus + There would be no probability for the words that do not exist in the corpus. + Ituses different testing corpus (other than training corpus). + It is the simplest POS tagging because it chooses most frequent tags associated with a word in training corpus. ‘Transformation-based Tagging Transformation based tagging is also called Brill tagging. It is an instance of the transformation-based learning (TBL), which is a rule-based algorithm for automatic tagging of POS to the given text. TBL, allows us to have linguistic knowledge in a readable form, transforms one state to another state by using transformation rules. It draws the inspiration from both the previous explained taggers ~ rule-based and stochastic. If we see similarity between rule-based and transformation tagger, then like rule-based, it is also based on the rules that specify what tags need to be assigned to what words. On the other hand, if we see similarity between stochastic and transformation tagger then like stochastic, it is machine learning technique in which rules are automatically induced from data. Working of Transformation Based Learning(TBL) In order to understand the working and concept of transformation-based taggers, we need to understand the working of transformation-based learning. Consider the following steps to understand the working of TBL ~ + Start with the solution - The TBL usually starts with some solution to the problem and works in cycles. + Most beneficial transformation chosen ~ In each cycle, TBL will choose the most beneficial transformation. + Apply to the problem ~ The transformation chosen in the last step will be applied to the problem. The algorithm will stop when the selected transformation in step 2 will not add either more value or there are no more transformations to be selected. Such kind of learning is best suited in classification tasks. Advantages of Transformation-based Learning (TBL) The advantages of TBL are as follows ~ + We learn small set of simple rules and these rules are enough for tagging. + Development as well as debugging is very easy in TBL because the leamed rules are easy to understand + Complexity in tagging is reduced because in TBL there is interlacing of machineleamed and human-generated rules. + Transformation-based tagger is much faster than Markov-model tagger. Disadvantages of Transformation-based Learning (TBL) ‘The disadvantages of TBL are as follows ~ + Transformation-based learning (TBL) does not provide tag probabilities. + In TBL, the training time is very long especially on large corpora. UNIT-3 Syntactic Analysis Context-Free-Grammars, Grammar rules for English, Treebanks,Normal Forms for grammar- Dependency Grammar-Syntactic Parsing Ambiguity,Dynamic Programming parsing-Shallow parsing- Probabilistic CFG,Probabilistic [Link] lized CFGs-Feature structure ,Unification of feature structures. Context-Free Grammars To understand the need of having a good amount of context-free grammar we need to first get familiar with a term which is known as a constituency. This simply propagates the fact that all the strings or words present in the string behave like independent single units. These units come together to constitute the corpus. Grammar is simply based on the use of this constituency to develop the language further. Let us consider a noun phrase, which is essentially a string of words that has a noun followed by an object in it. We can look at some examples of the same. + Clifford the horse «The Nazi Germans + They All of these may not make complete sense while being written alone. They need to have a few more words as part of the entire constituent that surrounds the noun phrase. We can simply see this when we assign a certain number of verbs or verb phrases to these to get a better idea. «Clifford the horse trots away. + The Nazi Germans tortured the Jews. + They wandered off in the forest. With this simple addition, the sentence now makes complete sense. However, to be recognized and understood, the sentences need to be placed as a constituent of different phrases as learned in the previous unit. Certainly, noun phrases would most definitely occur before verbs in the sentence. ‘The constituency of a sentence can be further understood by placing a phrase in different parts of a sentence that would mean the same. The structure of the statement is one that has an immense understanding of it. If the phrase is placed at the start it is known as preposed and if it is placed at the end it is known as postposed. Let us see some examples of the same’ 1. On November eight, I would like to travel to New Delhi. 2. L would like to travel to New Delhi on November eight. As you can see the first example has the phrase ‘on November eight’ at the start of the sentence and the second example has it at the end. However, both of the examples mean the same thing in their entirety. Now that we know how a sentence is constituted and formed, we can move on to understanding Context-free Grammar (CFG). Context-free Grammar (CFG) is one of the most commonly used nomenclatures to model a certain sentence or phrase in the English language. This can also be done in any other natural language that could be used. CFG makes use of the constituents to make a fundamentally correct sentence. This type of grammar is also known as Phrase Structure Grammar. Nomenclature - a system of naming things, especially in science There are a few rules from the base of writing appropriate Context-free grammar that could be used to structure the constituents in a string. Let us look at some of the rules which are given below carefully. Each rule is essentially made up of a left side as well as a right side in a language. The left side shows the category whereas the right side shows the constituent parts that make up the left. CFG is made up of ¢ very important parts which are given in the set C = (V, ,T, P ) + V-Set of variables ‘The set V can have examples of V = {S, NOUN, VERB, AUXILLARY VERB, PROPER NOUN, VP, Det, PREPOSITION, etc.} NP = Determiner noun VP = Verb determiner noun Det =‘the’,‘a’ Preposition = ‘around’, ‘near’ Verb = ‘worked’, ‘ate’ + T-Set of terminal symbols ‘The setT can have examples T = {‘maggt’, ‘ate’, ‘a’, ‘boy’, ‘knife’, ‘with’} + S—Set of start symbols + P-Setrules for production ‘We can understand the same by looking at an example of how the same is formed with the help of a flowchart. Derivation: S=NP+VP = Det+ Noun+VP = The + Noun+VP =rne + cnua + vern + NY =The + child + ate + NP = The + child + ate + Det + NP =The + child + ate +a+NP =The + child + ate + a+ mango Sentence = “The child ate a mango.” Another example in terms of a flowchart is given below as Pro Verb NP | | 2 1 prefer Det Nom | aN a@ Nom Noun Noun flight morning Fig. Description 1: Flowchart breakdown of the entire table into 2 parts ‘Noun Phrase: A noun phrase can either be constituted of a ‘Proper Noun’ or a ‘determiner’. This is followed by a Nominal which can have different types of nouns that are part of it. NOUN PHRASE = PROPER NOUN / DETERMINER NOUN + NOMINAL qvoun) Key Takeaways: + CFG is made up of 4 very important parts which are given in the set C =(V, 5,7, P) + KCFG is known to be in Chomsky Normal Form when all of the production is ina particular form whichisA>BC OR ADa Grammar Rules for English - Dependency Grammar Grammar is the most important part of any language. Having a grammatically correct sentence allows fluent communication with the user to get the task done correctly. This can be further divided into different types of ways to get an idea of having appropriate rules that are used for grammar. + Sentence Construction The sentence is made up of words that are made up in turn of letters. The sentence forms part of a string which further is part of the corpus. People need to understand that if a sentence is well constructed it would most definitely mean a well-defined and inferentially active corpus. There are 5 types of sentences as given below: + Assertive sentence This sentence is also known as a declarative sentence which allows the user to say something without having a point of emphasis or interrogation. This could just be a plain sentence that does not ask any person to work. Model = NP E.g. [Link] rides a bike. 2. They swam across the river yesterday. + Imperative sentence This type of sentence is used when a person wants to request or show some authority for a work that is to be done. It usually begins with a Verb Phrase because people show their authority through verbs. Model =VP E.g. 1. Get me to work fast. 2. Show me the fastest route + Yes/No question These are as simple as the name suggests. The answer in reply to this interrogative question would either be a yes or a no. the user can elaborate on the answer if they wish. However, a single word answer would also suffice. They mainly begin with an auxiliary verb. It could also be a request just as the above examples but with an interrogation. Auxiliary verbs (also called helping verbs) are used along with a main verb to express tense, mood, or voice. For example, in the statement “it is raining,” “is” functions as an auxiliary verb indicating that the action of the main verb ("raining") is ongoing. Examples of auxiliary verbs include "be," “do,” “have,” “will” “shall,” “may,” "can," “must,” “ought,” *should,” “could,” and “would.” Model = Aux. Verb + NP +VP E.g. [Link] any of these cars work? 2. Could you please show me to the nearest hotel? + Wh question ‘The WH-sentence is one of the most complex forms out of all. This is because the answer could be anything including a simple yes/no as a reply. They must contain a Wh-question as part. Some examples of the same are {who, where, what, which, when, whose, how, why}. Model = Wh-NP + VP E.g. 1. Which car company does this belong to? [Link] airlines fly from New Delhi to Mumbai? + Non-Wh question This type of sentence would be speaking about the wh is not the main subject in the sentence. There is also another subject that is part of the entire sentence. There would be a‘wh phrase’ as well as a regular ‘NP phrase’. Model = Wh-NP + Aux. Verb + NP + VP. E.g. 1. What flights do you have from New Delhi to Mumbai? Key Takeaways: + Sentences can be transformed into different types with the help of features and components identified in them Treebanks Having a well-designed corpus would mean some strings make complete sense in the same and following grammatical meanings. Treebanks are essentially used to assign a parse tree to the string. This would simply mean that it is possible to go through a corpus and build a treebank for the same that shows a similar correspondence as to the same corpus. To get a better understanding of the above let us look at a famous example of a treebank which is also known as the Penn Treebank Project. This treebank was made from the corpora of the Brown and WS] pages. There was a type of syntactic movement in the treebank that was made to get a better idea. Below are representations of the same in terms of the sentence, “That cold, empty sky was full of fire and light.”: + Parsed sentences ccs (NP-SB3 CDT That) ©) cold) ©, 49 3 empty) CHN sky) > ve cvBD was CADIP-PRD (33 full) CPP CIN of) cup CNN fire Cec and) (NM Light» 9999 Gx: 2d BS. A sentences breakdown entirely Fig. Description 2: Parr + Treebank s ie ve TT a is NN VED ADIP-PRD That cold | empty sky was 3b putt | -™ of NS co NN fre and tight ‘Treebanks can also be used in the form of grammar. They are the main basis on which the user can use tags that are given to the same to get the entire NP rules. We can see below that there are some rules which are made to sustain the NP form of conduct. A sentence is made up of S= NP +VP. The sentence "That cold, empty sky was full of fire and light" is broken down into its grammatical components. The subject of the sentence is the noun phrase “That cold, empty sky," and the predicate is “was full of fire and light," with "full" as the predicate adjective and “of fire and light" as the prepositional phrase that modifies "full." This tree visually illustrates the hierarchical relationships between the different parts of the sentence according to the rules of syntax Sentence: "That cold, empty sky was full of fire and light.” Structure: 1. § (Sentence): The root node, representing the entire sentence. 2. NP-SBJ (Noun Phrase - Subject): This is the subject of the sentence. It contains: © DT (Determiner): "That" 43 (Adjective): "cold" » (Comma): Separates adjectives 43 (Adjective): “empty” NN (Noun): "sky’ So, the subject is "That cold, empty sky." 3. VP (Verb Phrase): This represents the action or predicate in the sentence. It contains: © VBD (Verb, Past Tense): "was" (the linking verb in past tense). © ADJP-PRD (Adjective Phrase - Predicate): The predicate describing the subject. + (Adjective): "full" (describing the state of the subject). + PP (Prepositional Phrase): Begins with a preposition and includes: + IN (Preposition): "of" + NP (Noun Phrase): The object of the preposition “of,” consisting oft + NN (Noun): "fire" + CC (Coordinating Conjunction): "and" + NN (Noun): “light” This forms the phrase “of fire and light." Hence, we are certain that a sentence can be made up of a noun phrase and well as a word phrase. Knowing the appropriate constituent compositions that can be achieved from the following we get an idea of the sentence that can be forme: Above are all the combinations in the form of their POS TAGs as we have studied in the previous unit. Key Takeaways: + Treebanks are essentially used to assign a parse tree to the string. This would simply mean that it is possible to go through a corpus and build a treebank for the same that shows a similar correspondence as to the same corpus. Normal Forms in Context-free Grammar ‘We notice that when we reduce the grammar in a particular corpus there is a minimization of the same. However, standardization does not take place throughout. This takes place mainly because the right-hand side of RHS products has no particular format that can be used. To make sure that the corpus is standardized we ‘come across two normalization forms that can be used for the same. + Chomsky Normal Form ‘This is a type of CFG that involves having the terminals and non-terminal components to normalize the corpus. A CFG is known to be in Chomsky Normal ‘Form when all of the production area in a particular form which is: ABC OR 4A~a;Hore A,B,C are known to NOT be terminals whereas ‘a’ is CONCLUSION: + For the grammar to be in the CNF form there need to be 2 non-terminal components as well as one single component. + The RHS of a certain product has the maximum number of symbols to be accommodated as 2. + These symbols must be a couple of non-terminal components or a single terminal component. We can look at the different steps used to solve a certain example to get a good idea of the same. Q) Standardize the following M>a&D A> aB/bAB Bb Dea rieecomenicasioen Ey studocu Solution: We notice that there are 2 non-terminal components as well as a single terminal component. This prompts to us the fact that this is in CNF. Now to convert it to CFG we need to follow certain steps. + Step1 Reduce it to the simplest form, we notice that the grammar is already in the simplest form which is: M>aaD A> aB/bAB Bb pea + Step2 We need to spot if any of the given expressions are already in GNF. Out of the following. B> band D > d are already in CNF and will hence not have any changes. ‘We need to also convert M> aAD and A> aB / bAB into CNF which we will do in the next step now that we have identified them. + Steps Replace the letters a and b with new symbols. Let us say they are replaced by C” and C” respectively. Therefore, Cra c">b Hence, we get M>C’AD A> C’B/C”AB + Step4 ‘We now work to replace the combination of non-terminal components with different letters. ‘Therefore, ABDE’ ADE” Hence, we get; M>C’E” ADC'B/C"E’ + Steps Through all the above conversions we finally get our normal form of all the expressions which are shown below as follows: 1.M> CE” AD C’B/C"E” Bb Dea ota c’>b BBOE ADE” ‘This is the final conversion of the given question into CNF. Key Takeaways: + CFG is known to be in Chomsky Normal Form when all of the production isina particular formwhichisK>BC OR A>a Syntactic Parsing ‘Syntactic Parsing is the process of having the program recognize a string and assign a certain syntactic structure to it. This is done after the normalization process as seen above. Parse trees are the exact thing that is assigned to each string in the process of parsing. This becomes very ‘useful to the person who is going to have tasks like grammar checking as well as word processing say the least. Parge trees are very important because they have good knowledge about the semantic analysis that takes place throughout the entire process of language processing. Before we work with certain algorithms there is always a question regarding the ambiguity that is proposed to the system before any change is made to it. Hence, we need to understand the topic of ambiguity before getting any further into the dynamics of parsing. Key Takeaways: ‘© Syntactic Parsing is the process of having the program recognize a string and assign a certain syntactic structure to it Ambiguity Being ambiguous is one of the main strengths of an algorithm. However, this very fact is the reason for its downfall. People understand that the structure is made up of strings in the corpus. So let us get on with an important understanding of the same. Different types of ambiguities are present in NLP. 1, Structural Ambiguity ‘This is the ambiguity that deals with the problems posed by the syntactic parsers to gain a comfortable yet challenging role of the same. This has a different structure that can be seen while making the same sentence. This type of ambiguity can give more than just a single parse toa certain string. Attachment Ambiguity ‘The next type of ambiguity that we have is known as attachment ambiguity. A string is called an attachment ambiguity when there is a parse tree at more than one position on the string. It must contain a prepositional phrase right behind the verb and noun. It must make the string syntactically ambiguous Jurafsky's Miniature Grammar, “4 Omitting the lexicon Ss — NPVP S —+ Auxiliary-Verb NP VP s — vP NP —+ Pronoun NP —+ Proper-Noun NP —+ Determiner Nominal Nominal —+ Noun Nominal —+ Nominal Noun Nominal —+ Nominal PP VP —+ Verb VP —> Verb NP VP —+ Verb NP PP VP —+ Verb PP ve —> VP PP PP —+ Preposition NP I saw 2 man with 2 telescope NP 1 Pronoun 2 Noun man medoammnonscen EY studocu Nominal Noun Fig Description 4: The above figure shows the difference in the structure faced by the entire ‘sentence while being formed Coordination Ambiguity The next type of ambiguity that we have is one that combines two strings that are from the corpus. We are then going to use conjunctions which are the parts of speech. If we take an example of the sentence, “The boys and girls are together” We can see that 2 tokens viz. boys and girls. ‘Example: Jurafsky’s Miniature Grammar, A, Omitting the lexicon Ss — NPVP S —+ Auxiliary-Verb NP VP s — VP NP —+ Pronoun NP —+ Proper-Noun NP —+ Determiner Nominal Nominal —+ Noun Nominal —+ Nominal Noun Nominal —+ Nominal PP VP —> Verb VP —+ Verb NP vP —+ Verb NP PP VP —+ Verb PP VP —+ VP PP PP —+ reposition NP NP —+ NP Conjunction NP Nominal —+ Nominal Conjunction Nominal VP —+ VP Conjunction VP PP —+ PP Conjunction PP Also, for adjectives include NP —>+ Adjective Nominal Coordination Ambiguity: 1 Spicy rice and apples Adjective Nominal | <7 spicy Nominal Conjunction Nominal 1 1 Noun and Noun | rice apples Coordination Ambiguity: 2 Spicy rice and apples Conjunction NP | Adjective Nominal and Nominal \ \ spicy Noun Noun | rice apples Dynamic Programming Parsing ‘Whenever we look at different algorithms, we need to understand the different happenings that take place in the sequential process. Having a dynamic programming approach allows us to get a frame that can sustain all the problems. This is a very similar algorithm when it comes to the processes like Minimum Edit Distance and the Viterbi algorithm. Key Takeaways: + Having a dynamic programming approach allows us to get a frame that can sustain all the problems, medoammnonscen EY studocu Shallow Parsing A lot of languages may not need too much parsing due to the lesser complex structure of the corpus. To make sure that the parsing takes place we use shallow parsing. Information retrieval can take place throughout the entire system taking place. Partial parsing has 2 many different approaches that can be used to allow the algorithm to work. One can simply use FST's or other tree-like representations, There is a certain flatness that would arise from the entire function throughout the transducer attachments, The intent to make parse trees throughout the algorithm while managing the lesser complex strategy. The alternate style that has been developed throughout is known as chunking. It is the process of classifying the segments that do not overlap in a particular sentence after identifying it from the corpus. POS contents containing noun phrases as well a8 verb phrases and other phrases come into the algorithm of shallow parsing. Let us understand this with the help of an example ina sentence. + [The evening flight] [from] [New Delhi] [has arrived]. NP PP NP ve * [The evening flight] from [New Delhi] has arrived. NP NP Evaluating Chunking Systems As we get an idea about the chunking parsing, we need to understand that the model needs to be evaluated at constant intervals. Evaluation of POS chunkers behaves like normal annotators. We can evaluate the following with the help of being precise. F-measure is a measure of understanding the precision. Precision is a part of the whole process that speaks about the system chunks that need correction throughout the whole process. Chunk labels are different for each model that has been decided. We can see the formula that is given by. Precision = ( Total correct chunks gave by the system ) / (Total chunks in the system ) Recall measures the percentage of correct chunks that might be present in the output. The difference between precision and recall is that it talks about the total chunks in the corpus rather than the entire system, Recall = (Total correct chunks given by system) / (Total number of chunks given in the text ) ‘The P-measure allows the chunking system to be measured along with a single metric. (B?+1)PR ~ BP+R~ B is the term that talks about the different weight being given to the system based on precision and recall. These are the different types of B values: + B>1 implies that we favour recall + B<1 implies that we favour precision + B=] implies that both precision and recall are balanced equally Probabilistic Context-free Grammar When the user wants to augment the Context-free grammar, the simplest way to do so is by adopting the Probabilistic Context-free Grammar model. This is also known as the Stochastic Context-free Grammar model. As one would recall that the usual CFG is made up of 4 tuples. It means that there are essentially 4 main parameters that play an important role in understanding the augmentation that takes place in the entire sequence. ‘They are * V-Set of variables ‘The set V can have examples of V = {S, NOUN, VERB, AUXILLARY VERB, PROPER NOUN, ‘VP, Det, PREPOSITION, etc.} NP = Determiner noun VP =Verb determiner noun Jet = ‘the’, ‘a’ * T-~Set of terminal symbols ‘maggi’, ‘ate’, ‘a’, ‘boy’, ‘Imnife’, ‘with’} The set T can have examples T rmucccumennaasnen EY studocu * >-petorstart sympois © P-Set rules for production We can understand the same by looking at an example of how the same is formed with the help of a flowchart, The new model simply adds a conditional probability to each of the 4 parameters. Let us call this conditional probability ‘p’. This conditional probability will tell us about the expansion of anon-terminal component (LHS) into the B sequence. ‘This can be represented as P( AB ) or also as P( LHS|RHS ). If we consider all the possible ‘events of the conditional probability that has been assigned to the model, we conclude that the sum is equal to 1 Consistency of a PCFG ‘We need to also figure out if the model is consistent or not, This would give the user a clear idea about the probabilities being assigned to the same. Grammar rules can also be very recursive at times. This involves loops to be formed. A PCFG is said to be consistent if the probabilities of all the strings summed up to equal 1. These PCFG's can be used easily to estimate the probabilities coming out of each string present in the parse tree. Ss Ss | | + A a 7 ~. Verb NP Verb NP NP [ ws | # | ook evi «== ai all oad 1b “ws | | | the Nominal Noun the Noun Noun wa sl wl, wl a Fig. Description 6: There is a comparison between the consistencies in each of the sentences composed of the same words, ‘Key Takeaways: + A PCFG is said to be consistent if the probabilities of all the strings summed up to equal 1 3.7 Probabilistic Cocke-Younger-Kasami (PCYK/PCKY) A simple problem that is created due to parsing by a PCFG is a parse tree which we can call T which is unique for a particular sentence . all of these are simply an extension or a modified version of the algorithms that have been used formerly for parsing. Now a probabilistic CYK algorithm simply assumes that the CPG is already in the CNP form. The CNP now has a simple rule as mentioned earlier which states that the CNF must have either 2 non-terminal components or a single terminal component on the RHS of it. ‘This same property of terminal and non-terminal components has been exploited a little and ‘each word/token in the sentence is given a specific index to work with. CKY Algorithm + With the grammar in CNF, each non-terminal node above the POS level of the parse tree will have exactly two children + Thus, a two-dimensional matrix can be used to encode the tree structure + For sentence of length n, work with upper-triangular portion of (n+1) x (+1) matrix + Each cell [//] contains a set of non-terminals that represent all constituents. spanning positions / through / of the input + Cell that represents the entire input resides in position [0,7] CKY Algorithm + Non-terminal entries: For each constituent [ij], there is a position, k, where the constituent can be split into two parts such that / NP VP) » An example parameter in a Lexicalized PCFG: /a(S(saw) ~+2 NP(man) VP(saw)) Parsing with Lexicalized CFGs S > we vp OC w®) a. » The new form of grammar looks just like a Chomsky normal why beh form CFG, but with potentially O((S? x |/N|*) possible rules. own) » Naively, parsing an n word sentence usin mic programming algorithm wil tak OC? SPIN) time, But [S| can be hugelt a Ba de » Crucial observation: at most{O(n? x [N|) rules can be applicable to a given sentence Wj, Wy, Wy of length n. This is because any rules which contain a lexical item that is nt one of tw ... wy, can be safely discarded. iON) Sine 2 Whe » The result: we can parse i edoammnonscen EY studocu 32. Feature Structures Feature suctares Ate ave One of the simplest ways to encode the kind of properties that we have in mind is through the use of feature structures. These are simply sets of feature-value pairs, where features are unanalyzable atomic symbols drawn from some finite set, and values are either atomic symbols or feature structures themselves. Such feature structures are illustrated with the following kind of diagram, called an attribute-value matrix or AVM: FEATURE) value FEATURE? value, FEATURE, valuey To make this concrete, consider the number property discussed above, To capture this property, we will use the symbol NUMBER to designate this grammatical attribute, and the symbols sg and p! (introduced in Ch. 3) to designate the possible values it ean take on in English. A simple feature structure consisting of this single feature would then be illustrated as follows: [NumpeR sg] Adding an additional feature-value pair to capture the grammatical notion of person leads to the following feature structure: NUMBER sg PERSON — 3rd| Next we can encode the grammatical category of the constituent that this structure corresponds to through the use of the CAT feature. For example, we can indicate that these features are associated with a noun phrase by using the following structure: CAT NP’ NUMBER sg PERSON 3rd. This ability to use feature structures as values leads fairly directly to the notion of a feature path. A feature path is nothing more than a sequence of features through a feature structure leading to a particular value. For example, in the last feature struc ture, we can say that the (AGREEMENT NUMBER) path leads to the value sg, while the 8 3rd ‘A feature structure with shared values. The location (value) found by following the (HEAD SUBJECT AGREEMENT) path is the same as that found via the (HEAD AGREEMENT) path. (AGREEMENT PERSON) path leads to the value 3rd. This notion of a path leads natu- rally to an alternative graphical way of illustrating feature structures, shown in Figure 15.1, which as we will sce in Section 15.4 is suggestive of how they will be imple- mented. In these diagrams, feature structures are depicted as directed graphs where features appear as labeled edges and values as nodes. While this notion of paths will prove useful in a number of settings, we introduce it here to help explain an additional important kind of feature structure: those that contain features that actually share some feature structure as a value. Such feature structures will be referred to as reentrant structures structures. What we have in mind here is not the simple idea that two features might have equal values, but rather that they share precisely the same feature structure (or node in the graph). These two cases can be distinguished clearly if we think in terms of paths through a graph. In the case of simple equality, two paths lead to distinct nodes in the graph that anchor identical, but distinct structures. In the case of a reentrant structure, two feature paths actually lead to the same node in the structure, CAT Ss NUMBER 9g AGREEMENT rita: PERSON 3rd| sumect — [acreement [] medoammnonscen EY studocu CAL___re@ s AGREEMENT ‘SUBJECT ‘AGREEMENT A feature structure with shared values. The location (value) found by following the (HEAD SUBJECT AGREEMENT) path is the same as that found via the (HEAD AGREEMENT) path, ‘There are a few paths that can be specified when it comes to a feature structure. Knowledge of the tuple, as well as the path, could help get an idea of the feature structure value that we are intending to calculate. ‘There are 2 types of feature structures known, Feature lists: The identifiers that are implemented are in the form of integers, 1, Feature dictionaries: The identifiers that are implemented are in the form of strings. 3.10 Unification of Feature Structures We begin with the following simple appl [wumper sg]U [Numper sg]= [NuMBER sg] mn of the unification operator. As this equation illustrates, unification is a binary operation (represented here as L)) that accepts two feature structures as arguments and returns a feature structure when it succeeds. In this example, unification is being used to perform a simple equality check. The unification succeeds because the corresponding NUMBER features in each structure agree as to their values. In this ease, since the original structures are identical, the output is the same as the input. The following similar kind of check fails since the NUMBER features in the two structures have incompatible values. [yomper sg] [yumper pil Fails! This next unification illustrates an important aspect of the notion of compatibility in unification. frummer sg]U [Numer []]~ [NuMBER sg| Unification of Feature Structures Agreement is checked by the unification operation and merged feature structure is determined according to the following cases: [feature; value] |_| [feature; value;] = [feature, value|] [feature; value] |_| [feature,; value,] = fail if value; + value, [feature, value,] |_| [feature, undef] = [feature, value] [feature, value] |_| [feature, value,] =| feature, value; feature, value, if feature; = feature, In this situation, these features structures are taken to be compatible, and are hence capable of being merged, despite the fact that the given values for the respective NUM- BER features are different. The [] value in the second structure indicates that the value has been left unspecified. A feature with such a [] value can be successfully matched to any value in a corresponding feature in another structure. Therefore, in this case, the value sg from the first structure can match the [] value from the second, and as is indicated by the output shown, the result of this type of unification is a structure with the value provided by the more specific, non-null, value. The next example illustrates another of the merger aspects of unification. [romper sg] [rersow 3rd] = ee a PERSON 3rd] medoammnonscen EY studocu We will now consider a series of cases involving the unification of somewhat more complex reentrant structures, The following example illustrates an equality check com- plicated by the presence of a reentrant structure in the first argument. acreement [| “MBER 88 PERSON 3rd! sumect — [acreement 2 PERSON 3rd] SUBJECT] AGREEMENT NUMBER sg PERSON = 3rd! NUMBER 9 AGREEMENT a * | sumect — [acreement ] The important elements in this example are the SUBJECT features in the two input structures. The unification of these features succeeds because the values found in the first argument by following the [] numerical index, match those that are directly present in the second argument. Note that, by itself, the value of the AGREEMENT feature in the first argument would have no bearing on the success of unification since the sec- ond argument lacks an AGREEMENT feature at the top level. It only becomes relevant because the value of the AGREEMENT feature is shared with the SUBJECT feature. The following example illustrates the copying capabilities of unification. (15.1) [aceement supect — [acreemeNt [i] u PERSON 3rd SUBJECT | AGREEMENT NUMBER sg = faoreement PERSON 3rd SUBJECT AGREEMENT [J NUMBER sg. Here the value found via the second argument’s (SUBJECT AGREEMENT) path is copied over to the corresponding place in the first argument. In addition, the AGREEMENT feature of the first argument receives a value as a side-effect of the index linking it to the value at the end of the (SUBJECT AGREEMENT) path. (152) [agreement [NUMBER sg] sumecr [soreeaenr [romper sl] u PERSON 3 SUBJECT | AGREEMENT NUMBER sg AGREEMENT [NUMBER sg] NUMBER sg PERSON 3 Finally, consider the following example of a failure to unify. NUMBER AGREEMENT [] = PERSON 3 SUBJECT [sokeEMeNt q u NUMBER sg] AGREEMENT PERSON 3 NUMBER PL suBIECT AGREEMENT PERSON 3 Fails! edoammnonscen EY studocu Feature structures are a way of representing partial information about some linguis- tie object or placing informational constraints on what the object can be. Unification ‘can be scen as a way of merging the information in each feature structure, or describing objects which satisfy both sets of constraints. Intuitively, unifying two feature strue- tures produces a new feature structure which is more specific (has more information) than, or is identical to, either of the input feature structures. We say that a less specific (more abstract) feature structure subsumes an equally or more specific one. Sub- sumption is represented by the operator C. A feature structure F subsumes a feature structure G (F CG) if and only if: 1. For every feature x in F, F(x) C G(x) (where F(x) means “the value of the feature x of feature structure F”).. 2. Forall paths p and q in F such that F (p) = F(q), itis also the case that G(p) = Gq). For example, consider these feature structures: (18.3) [xumper sg] (154) [reson 3] (15.5) ah | PERSON 3 (15.6) }caT vP AGREEMENT [J suBJECT [ackeEMENT i) (15.7) [car vp AGREEMENT = 3 ] SUBJECT AGREEMENT [I] NUMBER 5g The following subsumption relations hold among them: 15.30 15.5 154C 15.5 15.6C 15.7 Subsumption is a partial ordering; there are pairs of feature structures that neither subsume nor are subsumed by each other: 15.32 15.4 15.4.2. The Unification Algorithm The unification algorithm that we have been leading up to is shown m Figure 15.9. This algorithm accepts two feature structures represented using the extended DAG represen- tation and returns as its value a modified version of one of the arguments, or 3 failure signal in the event that the feature structures are incompatible. The first step in this algorithm is to acquire the irue contents of both of the argu- ments. Recall that if the pointer theld of an extended feature structure is non-null. then the real content of that structure is found by following the pointer found in pointer field The variables f? and /2 are the result of this pointer following process, often referred to as dereferencing_ NUMBER ‘An extended DAG notation for Example 15,19. (15.19) |NUMBER sg PERSON 3rd edoammnonscen EY studocu function UNIFY(//-orig. f2-orig) returns f-structure or failure ‘fl —Dereferenced contents of fl-orig (f2-—Dereferenced contents of f2-orig if fl and 2 are identical then Sl_pointer—2 return /2 else if/1 1s null then Si-pointer-—f2 return /2 ‘else if /2 is null then [Link]-—f1 return fl else if both /1 and /2 are complex feature structures then, PP pointer—fl for each 2-feature in f2 do {fi-feature— Find or create a corresponding feature in f? if UnIFY(f7-fearure value, f2-feature value) returns failure then return failure return /I else return failure The unification algorithm. Feature Structures, Grammar, Parsing Feature Structures * describe additional syntactic-semantic information, like category, person, number, e.g. goes = * specify feature structure constraints (agreements) as part of the grammar rules + during parsing, check agreements of feature structures (unification) example S— NP VP = S—NP VP = Feature Structures, Grammar, Parsing Feature Structures * describe additional syntactic-semantic information, like category, person, number, e.g. goes = * specify feature structure constraints (agreements) as part of the grammar rules * during parsing, check agreements of feature structures (unification) example S— NP VP = S—>NP VP = Feature Structures * Feature structures describe linguistic attributes or features like number, person associated with words or syntactic constituents like noun phrase. * Feature structures are sets of features and values, e.g. hat [Number — sing ] buys [Person a jl [Number — sing ] rmucccumennaasnen EY studocu Feature Structures - Agreement Feature structures can be collected in one ‘variable’ called agreement. buys | agreement [Person 3] [Number sing] Often these feature structures are referenced through an identifier. Feature Structures as Constraints Ungrammatical expressions like * Hego or We goes * One scarf... + He sleeps the book ... can be excluded using feature constraints. Feature structures are used to describe grammatical attributes of the respective item (word, syntactic category, phrase) like number, person, ... and connections between them (constraints), which are checked during processing (unification). example S-—NPVP_ = S—NPVP_ = = Feature Structures and Categories Add to feature structure the syntactic category cat: buys [cat verb agreement [Person 3 ] [Number sing] Feature Structures and Unification 1 Compare and combine feature structures: he buys _ buys [cat verb agreement [Person 3 ] [Number sing] he [cat noun agreement [Person 3 ] [Number sing] rmucccumennaasnen EY studocu Using Feature Structures S—NPVP = = buys | cat verb agreement [Person 3 ] [Number sing] [ must match | he fat noun unification agreement [Person 3 ] [Number sing] "Inheritance" of Feature Structures Feature structures are "inherited" during parsing or generation, using the feature structure of the head of a phrase: NP > det Nom NP i<1,... > Pre-Nom Nom )=1,, Post-Nom Complex feature structures are often referenced through identifying numbers. Constraints on feature structures can be checked using these references; and the same feature structure can be used in different parts of the parse tree through reference. Features and Subcategorization NP modifiers or Verb complements head noun + modifiers + agreement head verb + complements + agreements “\. the man who chased the cat out of the house ...” “. the man chased the barking dog who bit him...” Agreements are passed on / inherited within phrases, e.g. agreement of VP derived from Head-Verb of VP: determined by determined by tiseomerianison Ey studocu Second Assumption ‘The second probability in equation (1) above can be approximated by assuming that a word appears in a category independent of the words in the preceding or succeeding categories which can be explained mathematically as follows ~ PROB (W1...., WT | CL... CT) = [lis L..T PROB (WilCi) Now, on the basis of the above two assumptions, our goal reduces to finding a sequence C which maximizes TT T PROB(Ci|Cj-1) * PROB(Wi|Ci) Now the question that arises here is has converting the problem to the above form really helped us. The answer is - yes, it has. If we have a large tagged corpus, then the two probabilities in the above formula can be calculated as ~ PROB (Ci=VERBICi-1=NOUN) = (# of instances where Verb follows Noun) / (# of instances where Noun appears) (2) PROB (WilC @) (@ of instances where Wi appears in Ci) /(# of instances where Ci appears) Maximum Entropy models introduction ‘We can see any problems in natural language processing as linguistic classification problems in which linguistic contexts are used to predict linguistic classes. Maximum entropy models are a clean way to combine various pieces of contextual evidence to estimate the probability of a particular linguistic class occurring with a specific linguistic context. Maximum entropy classification is a method that generalizes logistic regression to multiclass problems. The Maximum Entropy model is a type of log-linear model. If we are given some data and told to decide, we could think of attributes about the data,i.e. features. Some of these features might be more important than others. ‘We apply a weight to each feature found in the data, and we add up all of the features. Finally, the weighted sum is normalized to give a fraction between 0 and 1. We can use this fraction to tell us the score of how confident we might be in making a decision. Maximum Likelihood The principle of Maximum Likelihood is defined as we have to find the parameter values w such that it models the input data x with the maximum probability. The aim is to find the weight parameters that will maximize the likelihood of the training data. SOC en OD — TD, Sox: ed DS ararmaxineS Cx ~~ + + ns HOD ‘We Assume we have a random sample with a training set of n examples. We assume input values to be independent, so the probability function f(x,w) is the product of the probabilities of each input. Like maximum likelihood, the entire conditional probability says we choose a parameter estimate w_hat that maximizes the product f(yilxi, w). wm argmax» TT, SCv|xis w) ‘We assume yi are independent conditionally on xi. To find w_hat, we can use gradient-based solutions like gradient descent. Gradient descent involves: ‘+ Starting with random weights w. + Looping through the training dataset. + Calculating the gradient. At each iteration, we update the weights w by moving some distance in the direction of the gradient. We repeat this until it converges or completes its iteration count. Log-Linear Model The log-linear model uses a linear combination of features and weights to find the predicted label with maximum log-likelihood. The log-likelihood is the logarithm of the likelihood function. Since the logarithm function is a monotonic increasing function, maximizing the log-likelihood maximizes the likelihood. ‘We describe the probability as: exe Dye, Fx 2 O00 8 ena Ey ea FFD ‘The function f(x,y) is a function that can account for relations between data and labels. It expresses some characteristics of the data point. It results in a value of 0 or 1 depending on the absence or presence. The wj is a weight of the feature function that captures how closely a given feature is related to a provided label. In the training process, wj is randomly initialized initially. The training process will learn the weight through gradient descent with some optimization methods. Approach In the training phase, we have to find weight w. Let us start with the log-likelihood function: This function L(w) measures how well w explains the labeled data. The higher LG) = EY log pox: wy value of P(y|x; w) greater is the value of L(w). The maximum-likelihood function uses the argmax function to find the best values for the parameter w: & = argmax,, Ei tox polis w> ‘The process involves iterating through training data many iterations. 1, Initially, initialize the w to some random values. 2. Keep iterating through each input. During each iteration, we update the weight by finding the derivative of L(w) concerning w). 3. Updating vector was below and repeated until converged. Maximum Entropy Likelihood ‘The maximum entropy model is log-linear. MaxEnt handles multinomial distribution. The maximum entropy principle states that we have to model the given set of data by finding the highest entropy to satisfy the constraints of our previous knowledge. To find the probability for each class, Maximum Entropy is defined as: POND he CROCE 104 Tee WD ZOOS Bie eC B te Fie Applications, MaxEnt classification is a more classical machine learning task and solves problems beyond natural language processing. Here are a few: + Sentiment analysis (e.g., given a product review, the reviewer likes and dislikes about the product). + Preferences (e.g., Given a person's demographics, who will a person vote for? Would they prefer Superman, Batman, or the Teenage Mutant Ninja Turtles? etc.).. + Diagnosis (e.g., Given characteristics of several medical images and patient history, what medical condition is a person at risk of having?). Maximum Entropy Markov Model ‘There are many systems where there is a time or state dependency. These systems evolve through a sequence of states, and past states influence the current state. For example, stock prices, DNA sequencing, human speech, or words in a sentence. Maximum Entropy Markov Model makes use of state-time dependencies,i.e., it uses predictions of the past and the current observation to make the current prediction. In Image analysis, we're required to classify the object into one of many classes. We estimate the probability for each class. Rather than take a hard decision on one of the outcomes, its better to output probabilities, which will benefit downstream tasks. Multinomial logistic regression is also called softmax regression or Maximum Entropy (MaxEnt) classifier. Entropy's related to the disorder. Higher the disorder, less predictable the outcomes, and hence more information. For example, an unbiased coin has more information (and entropy) than one that mostly lands up heads. MaxEnt is about picking a probability distribution that maximizes the entropy. Then, there's Markov Chain. It models a system as a set of states with probabilities assigned to state transitions. While MaxEnt computes probabilities for each input independently, the Markov chain recognizes a dependency from one state to the next. Thus, MEMM maximizes entropy plus using state dependencies (Markov Model). ‘The MEMM has dependencies between each state and the full observation sequence explicitly. MEMM has only one transition probability matrix. This matrix encapsulates previous states y(i-1) and current observation x(i) pairs in the training data to the current state y(i). Our goal is to find the P(y1,y2,...,yn)x1,x2,...xn). This is given by; PO. + Yn) = Tay PO nly «+ Vint X1- + Xn) Since HMM only depends on the previous state, we can limit the condition of y(n) given y(n-1). This is the Markov independence assumption. P(y1. + Yn) = Ty (PO nl yints x1. + Xn) So MEMM defines using Log-linear model as: i i PUyilyi-1. 4) = ———— i Si(Yis Vi-1s (vilyia x) Zon hE wher Yi-ts)) Shortcomings Of MEMM MEMM suffers from what's called the label bias problem, Once we're in a state or label, the following observation will select one of many transitions leaving that state. However, the model as a whole would have many more transitions. If a state has only cone outgoing change, the observation has no influence. Simply put, transition scores are normalized on a per-state basis. UNIT 4 SEMANTICS AND PRAGMATICS Requirement for representation, First-Order Logic, Description Logics-Syntax-Driven Semantic analysis, ‘Semantic attachments-word Senses, Relations between senses, Thematic Roles,selctional restrictions-Word Sense ,Disambiguation, WSD using Supervised-Word similarity using Thesaurus and Distributional methods. What are Semantics? * _ Study of words, phrases and sentences in a language. * Explores how words and grammatical structures contribute to the meaning of sentences, and how meaning is composed and interpreted. * focuses on the literal meaning of language, and aims to understand how meaning is derived from the linguistic form. ‘What is Pragmatics? * Study of how language is used in context. * Investigates how meaning is affected by factors such as the speaker's intentions, the listener's knowledge, and the communicative situation. * focuses on the non-literal or implied meaning of language, and aims to understand how meaning, is derived from the use of language in social interaction. Requirements for representation: © —_Compositionality: The meaning of a sentence is composed of the meanings of each word and the way they are combined. This means that the meaning of a sentence can be derived from the meanings of its parts. © Truth conditions: A representation must specify the truth conditions for a sentence, i.e., the conditions under which the sentence would be true or false. © Context sensitivity: The meaning of a sentence may depend on the context in which it is used. Therefore, a representation must be able to account for the effects of context on meaning. e Pragmatic relevance: A representation must be relevant to the communicative situation. This means that it should take into account the speaker's intended meaning and the listener's interpretation. @ — Generality: A representation should apply to a wide range of sentences and situations. © Consistency: A representation should be consistent with other linguistic and cognitive theories, and should not lead to contradictions or inconsistencies. First-order Logi e First-order logic (FOL) is a formal language that has been used in semantics and pragmatics to represent the meaning of sentences in a structured and logical way. e FOL allows us to represent the relationships between objects, properties, and events in a precise and formal manner, which can be useful for analyzing and understanding the meaning of natural language expressions. In semantics: oO In pragmatics: fe) FOL allows us to represent the meanings of words and sentences regarding their truth conditions. a Example: The sentence "John is a doctor" can be represented in FOL as "Doctor(John)", which means that the object "John" has the property of being a doctor. FOL allows us to represent the logical structure of sentences, including their subject- predicate structure and the relationships between different parts of the sentence. Example: The sentence "All dogs bark" can be represented in FOL as "For all x, if x is a dog, then x barks", where "For all x" is a quantifier that means "for every x", “if x is a dog” is a predicate that describes the property of being a dog, and "x barks" is a predicate that describes the action of barking. FOL representations can help to avoid ambiguity and inconsistency in interpretation. Example: The sentence "Every student passed the exam" can be represented in FOL as "For all x, if x is a student, then x passed the exam", which avoids the ambiguity of the sentence "Every student passed the exam with flying colours", since the latter may suggest that all students scored exceptionally well, which is not necessarily implied by the former. FOL allows us to represent the speaker's intended meaning and the listener's interpretation of a sentence. M___Example: The sentence "I need help with my homework" can be represented in FOL as a request for assistance, such as "Request(Assistance, Speaker, Homework)", where "Request" is a predicate that describes the communicative act of making a request, "Assistance" is a variable that represents the object being requested, "Speaker" is a variable that represents the speaker, and "Homework" is a variable that represents the object for which assistance is needed. FOL allows us to represent the context in which a sentence is used, including the speaker's beliefs, intentions, and assumptions, and the listener's knowledge and expectations, Example: The sentence "Do you have the time?" can be represented in FOL as a request for information, such as "Request(Time, Listener)", where "Request" is a predicate that describes the communicative act of making a request, "Time" is a variable that represents the object being requested, and "Listener" is a variable that represents the person being addressed. FOL representations can help to capture the communicative function of a sentence and its relationship to other expressions in the discourse. Example: The sentence "I'm sorry, I can't come to your party tonight" can be represented in FOL as a polite refusal, such as "Refusal(Party, Speaker, Listener)", where "Refusal" is a predicate that describes the communicative act of refusing an invitation, "Party" is a variable that represents the event being refused, "Speaker" is a variable that represents the person making the refusal, and "Listener" is a variable that represents the person being addressed. © Description Logics (DLs) are a family of formal knowledge representation languages used to represent and reason complex concepts and relationships in a structured and logical manner. DLs are a subset of first-order logic (FOL) specifically designed for representing knowledge in a way that is both expressive and computationally tractable. Provides formal semantics for natural language expressions, allowing us to represent their meaning in a structured and logical way. Used to construct ontologies, which are structured representations of knowledge in a particular domain. Allows us to reason about the relationships between concepts and instances, and to infer new knowledge based on existing knowledge. Often uses inference engines to perform reasoning tasks, such as consistency checking, classification, and query [Link] operates under an open-world assumption, which allows for more flexible and incremental development of ontologies. Syntax-Driven Semantic Analysis: @ A type of DL approach @ The syntax of natural language expression is used to drive the process of semantic analysis, @ Involves mapping the syntax of a sentence onto a formal logical structure, such as a DL ontology, to derive its meaning. © This approach allows for a more efficient and accurate analysis of natural language expressions, as the syntactic structure can provide important cues for determining the meaning of ambiguous or complex expressions. The grammar of the language works as a guide. The assumption is that the grammatical structure of a sentence reflects its underlying meaning and that by analyzing this structure, we can infer the meaning of the sentence. @ — Forexample, the sentence "John is a doctor who specializes in cardiology" can be analyzed syntactically to identify the subclauses "John is a doctor” and "who specializes in cardiology”, which can then be mapped onto corresponding concepts in a DL ontology to derive the overall meaning of the sentence. Semantic Attachments: @ Semantic attachments, also known as semantic roles or theta roles, are a linguistic concept that describes the relationship between the semantic content of a sentence and its syntactic structure In other words, they represent the different roles that words or phrases play in a sentence based on their meaning. @ For example, in the sentence "John ate the pizza with a fork,” the word "John" is the agent who acts as eating, "pizza" is the patient that undergoes the action of being eaten, and "fork" is the instrument that John uses to eat the pizza. These different roles are represented as semantic attachments associated with each word or phrase in the sentence. ‘Word Senses: @ A word sense is a specific meaning of a word that is determined by its context. Semantic attachments are a way of representing the meaning of a word in context by linking it to the concepts or entities that it refers to. @ For example, consider the word "bank." Depending on the context in which it appears, it could refer to a financial institution or the side of a river. In semantic attachments, we might represent these two senses of the word as follows: © For the financial institution sense: Word: "bank" I Sense: "financial institution” IE Attachment: links to the concept of a financial institution, such as a bank account, loans, or mortgages. © For the side of a river sense: Word: "bank" @ Sense: "river bank" © Attachment: links to the concept of a river, such as water, shore, or sediment. @ By representing word senses in this way, we can better understand the meaning of words in context and use this information for various NLP tasks, such as information retrieval, machine translation, and sentiment analysis. Relations between senses: @ The relationship between senses is typically represented by semantic relations or roles. @ These relations capture the semantic relationships between the different senses of a word, as well as the relationships between different words in a sentence or discourse © Some common types of semantic relations include: O Hyponymy/Hypernymy: IH Captures the relationship between a specific instance of a concept (hyponym) and its more general category (hypernym). I For example, "dog" is a hyponym of “animal” and "animal" is a hypernym of “dog”. O Synonymy: IH Captures the relationship between different words or senses that have the same or similar meaning. I For example, "car" and "automobile" are synonyms. O Antonymy: IH Captures the relationship between words or senses that are opposite in meaning. 1 For example, "hot" and "cold" are antonyms. O Meronymy/Holonymy: I Captures the relationship between a part and a whole. I For example, "wheel" is a meronym of "car" and "car" is a holonym of "wheel". O Troponymy: I Captures the relationship between a verb and a more specific way in which the action is carried out. I For example, "walk" is a troponym of "move" and “stroll” is a troponym of @ These relations can be used to build a network of interconnected senses and concepts, which can be used for various NLP tasks such as word sense disambiguation, information retrieval, and machine translation. ‘Thematic rol @ Also known as semantic roles or theta roles in certain places. @ Defined as the various roles that a noun phrase may play concerning the action or state described by a governing verb, commonly the sentence’s main verb. @ | Inother words, it is a way of describing the relationship between the participants in a sentence and the event or state that the sentence describes. © Roles that are commonly recognized are: © Agent: I The entity that performs the action or event described by the verb. I For example, in the sentence "John kicked the ball," "John" is the agent. © Patient: I The entity affected by the action or event described by the verb. ML For example, in the sentence "John kicked the ball,” "the ball © Theme: I The entity that is the topic or point of reference in the sentence. I For example, in the sentence "John gave the book to Mary,” "the book" is the theme. © Experiencer: I The entity that experiences a mental or emotional state or perception. I For example, in the sentence "John loves Mary." "John" is the experiencer. © Instrument: I The entity that is used to act. IH For example, in the sentence "John cut the bread with a knife, instrument. © Location: I The place where the action or event described by the verb takes place. I For example, in the sentence "John is at the store,” “the store” is the location. © Source: I The entity from which something moves or originates. I For example, in the sentence "John came from New York,” source. is the patient. ‘a knife" is the "New York" is the © Goal: I The entity toward which something moves. IH For example, in the sentence "John went to the store, the store” is the goal Selectional Restrictions: @ Also known as the semantic constraints or lexical constraints. @ They are the limitations on the arguments that can be used with a given predicate or verb. @ _Inother words, they are the semantic properties or features that a verb's argument must have to be licensed by that verb. @ Types: © Syntactic restrictions: I These are limitations based on the grammatical structure of a sentence. I For example, a wansitive verb requires two arguments, while an intransitive verb only requires one. © Semantic restrictions: I These are limitations based on the meaning of the verb or predicate and its arguments. I For example, the verb “eat” has a semantic restriction that its object must be edible. © Selectional preference: I These are tendencies for certain types of arguments to be associated with a particular verb. I For example, the verb "give" typically takes a recipient and a theme argument. © Prototypicality effects: I These are effects based on the typical or prototypical characteristics of the verb and its arguments. I For example, the verb "eat" typically takes a solid object as its object. © Frame semantics: I This is a more general approach that considers the entire event frame or situation that a predicate and its arguments participate in, not just the meaning of individual words. @ | Sclectional restrictions specify the types of arguments that a pre @ They help identify and disambiguate the correct interpretation of a word in a particular context. @ By narrowing down the possible meanings of the word, they increase the accuracy of natural language processing applications such as text-to-speech, machine translation, and information retrieval. @ Violations of selectional restrictions can indicate errors or inconsistencies in text or the computational model being used to analyze it. @ Sclectional restrictions can be used to identify errors and inconsistencies in the text. ate can take. Word Sense Disambiguation: @ WSD involves determining the correct sense of a word based on its context in a given sentence or text. @ Many words have multiple senses, and the correct sense must be identified to accurately interpret the text. @ WSD can be performed using various techniques, including rule-based methods, knowledge-based methods, and supervised and unsupervised machine leaning algorithms, @ Applications of WSD include machine translation, information retrieval, and text-to-speech synthesis. @ WSD is a challenging problem, as context can be ambiguous and may require a deep understanding of language and its nuances to correctly disambiguate word senses. @ Reasons, why WSD is used, are: © Ambiguity: Many words in natural language have multiple meanings or senses, and WSD is used to disambiguate the correct sense in a given context. © Accuracy: Helps to improve the accuracy of NLP applications by ensuring that the correct sense of a word is used. © Precision: WSD can also help to improve the precision of NLP applications by reducing the number of false positives and false negatives. © Language understanding: WSD is an important task for natural language understanding as it requires understanding the context and the meaning of the words in the sentence. © Information retrieval: WSD is used in information retrieval systems to retrieve relevant documents based on the intended meaning of the query. WSD using Supervised, Dictionary and Thesaurus: Supervised Approach: @ This approach uses labelled examples to train a machine learning model to predict the correct sense of a word in context. @ A popular algorithm for supervised WSD is the Naive Bayes classi @ Example: In the sentence "I went to the bank to deposit my paycheck,” the word "bank" could refer to a financial institution or a river bank. A supervised WSD model would use labelled examples to learn how to predict the correct sense based on the context of the sentence. n Dictionary-Based Approach: © This approach uses a dictionary or lexical database that provides information on the different senses of a word. @ When presented with a word in context, the approach looks up the word in the dictionary and chooses the sense that best fits the context. @ Example: In the sentence "I love to play the bass guitar,” the word "bass" could refer to a fish or a low-pitched musical instrument. A dictionary-based WSD approach would look up "bass" and choose the sense that matches the context of the sentence. Thesaurus-Based Approach: @ This approach uses a thesaurus or semantic network that groups words based on their semantic similarity. @ When presented with a word in context, the approach identifies related words in the

You might also like