Natural-Language-Processing-inside-pages-2-munotes

Page 1

1 1 INTRODUCTION Unit Structure 1.0 Objectives 1.1 History of NLP 1.2 Generic NLP system 1.3 Levels of NLP 1.4 Knowledge in Language Processing 1.5 Ambiguity in Natural Language 1.6 Stages in NLP 1.7 Challenges in NLP 1.8 Applications of NLP 1.9 Summary 1.10 Multiple Choice Question Answers 1.11 True or False 1.12 Sample Questions 1.13 List of References 1.0 OBJECTIVES The objective of this module is to learn about history of Natural Language Processing (NLP), Generic NLP system, Levels of NLP. After that we will discuss the knowledge in language processing. This is followed by a discussion of the Ambiguity in Natural language, Stages in NLP, and challenges of NLP. Finally we will discuss the applications of NLP. 1.1 HISTORY OF NLP As we all know Natural Language refers to the language spoken by people e.g. English, Hindi, Marathi as opposed to artificial/programming languages, like C, C++, Java, etc. Natural Language Processing (NLP) is a field of research which determines the way computers can be used to understand and manage natural language text or speech to do useful things. Natural Language Processing (NLP) a subset technique of Artificial Intelligence which is used to narrow the communication gap between the Computer and Human. It is originated from the idea of Machine Translation (MT) which came to existence during the 1950. The primary aim was to translate one human language to another human language, for example, Russian language to English language using the brain of the Computers but after that, the thought of conversion of human language to computer language and vice-versa emerged, so that communication with the machine became easy. munotes.in

Page 2

2 Natural Language Processing
2 NLP is a process where input provided in a human language and converts this input into a useful form of representation. The field of NLP is primarily concerned with getting computers to perform interesting and useful tasks with human languages. The field of NLP is secondarily concerned with helping us come to a better understanding of human language. As stated above the idea had emerged from the need for Machine Translation in the 1950s. Then the original language was English and Russian. But the use of other words such as Chinese also came into existence in the initial period of the 1960s. In the 1960s, the NLP got a new life when the idea and need of Artificial Intelligence emerged. In 1978 LUNAR is developed by W.A woods; it could analyze, compare and evaluate the chemical data on a lunar rock and soil composition that was accumulating as a result of Apollo moon missions and can answer the related question. In the 1980s the area of computational grammar became a very active field of research which was linked with the science of reasoning for meaning and considering the user‘s beliefs and intentions. In the period of 1990s, the pace of growth of NLP increased. Grammars, tools and Practical resources related to NLP became available with the parsers. Probabilistic and data-driven models had become quite standard by then. In 2000, Engineers had a large amount of spoken and textual data available for creating systems. Today, large amount of work is being done in the field of NLP using Machine Learning or Deep Neural Networks in general, where we are able to create state-of-the-art models in text classification, Question and Answer generation, Sentiment Classification, etc. 1.2 GENERIC NLP SYSTEM Natural language Processing should start with some input and ends with effective and accurate output. The possible inputs to an NLP are quite broad. Language can be in a variety of forms such as the paragraphs of text, commands that are typed directly to a computer system, etc. The input language might be given to the system a sentence at a time or it might be multiple sentences all at once. The inputs for natural language processor can be typed input, message text or speech. NLP systems have some kind of pre-processor. Data preprocessing involves preparing and cleaning text data for machines to be able to analyze it. Preprocessing puts data in workable form and highlights features in the text that an algorithm can work with. Preprocessing does dictionary lookup, morphological analysis, lexical substitutions, and part-of-speech assignment. munotes.in

Page 3

3 Introduction There are variety of output can be generated by the system. The output from a system that incorporates an NLP might be an answer from a database, a command to change some data in a database, a spoken response, Semantics, Part of speech, Morphology of word, Semantics of the word or some other action on the part of the system. Remember these are the output of the system as a whole, not the output of the NLP component of the system. Figure 1.2.1 shows a generic NLP system and its input-output variety. Figure 1.2.2 shows a typical view of what might be inside the NLP box of Figure 1.2.1. Each of the boxes in Figure 1.2.2 represents one of the types of processing that make up an NLP analysis.
Figure 1.2.1 Generic NLP system.
Figure 1.2.2 Pipeline view of the components of a generic NLP system. munotes.in

Page 4

4 Natural Language Processing
4 1.3 LEVELS OF NLP There are two components of Natural Language Processing a. Natural Language Understanding (NLU) • NLU takes some spoken/typed sentence and working out what it means. • Here different level of analysis required such as morphological analysis, syntactic analysis, semantic analysis, discourse analysis, … b. Natural Language Generation (NLG) • NLG takes some formal representation of what you want to say and working out a way to express it in a natural (human) language (e.g., English) • Here different level of synthesis required: deep planning (what to say), syntactic generation Difference between NLU and NLG NLU NLG It is the process o f reading and
interpreting language. It is the process of writing or generating
language. NLU explains the meaning behind
the written text or speech in natural
language NLG generates the natural language
using machines. NLU draws facts from the natural
language using various tools and
technologies such as parsers, POS
taggers, etc, NLG uses the insights generated from
parsers, POS tags, etc. to generate the
natural language. NLU understands the human
language and converts it into data NLG uses the structured data
and generates meaningful narratives out
of it The NLP can broadly be divided into various levels as shown in Figure 1.3.1. munotes.in

Page 5

5 Introduction
Figure 1.3.1 Levels of NLP 1. Phonology: It concerned with interpretation of speech sound within and across words. 2. Morphology: It deals with how words are constructed from more basic meaning units called morphemes. A morpheme is the primitive unit of meaning in a language. For example, “truth+ful+ness”. 3. Syntax: It concerns how words can be put together to form correct sentences and determines what structural role each word plays in the sentence and what phrases are subparts of other phrases. For example, “the dog ate my homework” 4. Semantics: It is a study of the meaning of words and how these meaning combine in sentences to form sentence meaning. It is study of context- independent meaning. For example, plant: industrial plant/ living organism Pragmatics concerns with how sentences are used in different situations and how it affects the interpretation of the sentence. Discourse context deals with how the immediately preceding sentences affect the interpretation of the next sentence. For example, interpreting pronouns and interpreting the temporal aspects of the information. 5. Reasoning: To produce an answer to a question which is not explicitly stored in a database; Natural Language Interface to Database (NLIDB) carries out reasoning based on data stored in the database. For example, consider the database that holds the student academic information, and user posed a query such as: ‘Which student is likely to fail in Science subject?’ To answer the query, NLIDB needs a domain expert to narrow down the reasoning process. munotes.in

Page 6

6 Natural Language Processing
6 1.4 KNOWLEDGE IN LANGUAGE PROCESSING A natural language understanding system must have detailed information about what the words mean, how words combine to form sentences, how word meanings combine to form sentence meanings and so on. What distinguishes these language processing applications from other data processing systems is their use of knowledge of language. For example consider the Unix wc program, which is used to count the total number of bytes, words, and lines in a text file. When used to count lines and bytes, wc is an ordinary data processing application. However, when it is used to count the words in a file it requires information about what it means to be a word, and thus becomes a language processing system. Of course, wc is an extremely simple system with an extremely limited and impoverished knowledge of language. The different forms of knowledge required for natural language understanding are given below: Phonetic and Phonological Knowledge Phonetics is the study of language at the level of sounds while phonology is the study of combination of sounds into organized units of speech, the formation of syllables and larger units. Phonetic and phonological knowledge are necessary for speech based systems as they are concerned with how words are related to the sounds that realize them. Morphological Knowledge Morphology concerns with word formation. It’s a study of the patterns of formation of words by the combination of sounds into minimal distinctive units of meaning called mophemes. Morphological knowledge deals with how words are constructed from morphemes. Syntactic Knowledge Syntax is the level at which we study how words combine to form phrases, phrases combine to form clauses and clauses join to make sentences. Syntactic analysis concerns sentence formation. It’s concerned with how words can be put together to form correct sentences. It also determines what structural role each word plays in the sentence and what phrases are subparts of what other phrases. Semantic Knowledge It deals with meanings of the words and sentences. This is the study of context independent meaning that is the meaning a sentence has, no matter in which context it is used. Defining the meaning of a sentence is very difficult due to the ambiguities involved. munotes.in

Page 7

7 Introduction Pragmatic Knowledge Pragmatics is the extension of the meaning or semantics. Pragmatics concerned with the contextual aspects of meaning in particular situations. It concerned with how sentences are used in different situations and how use affects the interpretation of the sentence. Discourse Knowledge Discourse concerns connected sentences. It’s a study of chunks of language which are bigger than a single sentence. Discourse language concerned with inter-sentential links means how the immediately preceding sentences affect the interpretation of the next sentence. Discourse knowledge is important for interpreting pronouns and temporal aspects of the information conveyed. World Knowledge Word knowledge is nothing but everyday knowledge that all speakers share about the world. It includes the general knowledge about the structure of the world and what each language user must know about the other user’s beliefs and goals. This is essential to make the language understanding much better. 1.5 AMBIGUITY IN NATURAL LANGUAGE Ambiguity can occur at all NLP levels. It is a property of linguistic expressions. If an expression (word/phrase/sentence) has more than one meaning we can refer it as ambiguous. For eg: Consider the sentence, “The chicken is ready to eat.” The meaning in the above phrase can be, The chicken (food) is ready to be eaten or the chicken (bird) is ready to be feeder Consider another sentence, “There was not a single man at the party.” The meaning in this case can be Lack of men altogether or Lack of bachelors at the party. There are different forms of ambiguity that are relevant in natural language processing. 1. Lexical Ambiguity: It’s the ambiguity of a single word. A word can be ambiguous with respect to its syntactic class. Eg: book, study. For eg: The word "silver" can be used as, an adjective, a noun or a verb. • She made a silver speech. • She bagged two silver medals. • His worries had silvered his hair. munotes.in

Page 8

8 Natural Language Processing
8 Lexical ambiguity can be resolved by Lexical category disambiguation ie, parts-of speech tagging. As many words may belong to more than one lexical category. Part-of speech tagging is the process of assigning a part-of-speech or lexical category such as a noun, pronoun, verb, preposition, adverb, adjective etc. to each word in a sentence. Lexical Semantic Ambiguity: The type of lexical ambiguity, which occurs when a single word is associated with multiple interpretations. Eg: fast, bat, bank, pen, cricket etc. For eg: 1. The tank was full of water. 2. I saw a military tank. Words have multiple meanings for such sentences. Consider the sentence "I saw a bat." Possible meaning of the words which changes the contexts of the sentence are: • bat flying mammal / wooden club? • saw past tense of "see" /present tense of "saw “ (to cut with a saw.) The occurrence of tank in both sentences corresponds to the syntactic category noun, but their meanings are different. Lexical Semantic ambiguity resolved using word sense disambiguation (WSD) techniques, where WSD aims at automatically assigning the meaning of the word in the context in a computational manner. 2. Syntactic Ambiguity: A sentence can be parsed in different ways. For example, “He lifted the beetle with red cap” or “Did he use cap to lift the beetle”. The structural ambiguities were syntactic ambiguities Structural ambiguity is of two kinds: i) Scope Ambiguity ii) Attachment Ambiguity – Scope Ambiguity: Scope ambiguity involves operators and quantifiers. For example: Old men and women were taken to safe locations. The scope of the adjective (i.e., the amount of text it qualifies) is ambiguous. That is, whether the structure (old men and women) or ((old men) and women)? The scope of quantifiers is often not clear and creates ambiguity. Every man loves a woman munotes.in

Page 9

9 Introduction The meaning can be, For every man there is a woman and also it can be there is one particular woman who is loved by every man. • Attachment Ambiguity A sentence has attachment ambiguity if a constituent fits more than one position in a parse tree. Attachment ambiguity arises from uncertainty of attaching a phrase or clause to a part of a sentence. Consider the example: The man saw the girl with the telescope. It is ambiguous whether the man saw her through his telescope or he saw a girl carrying a telescope. The meaning is dependent on whether the preposition ‘with’ is attached to the girl or the man. Consider the example: Buy books for children and attach to the verb buy Preposition Phrase ‘for children’ can be either adverbial or adjectival and attach to the object noun books. 3. Semantic Ambiguity: This type of ambiguity is typically related to the interpretation of sentence. Even after the syntax and the meanings of the individual words have been resolved, there are two ways of reading the sentence. Consider example: "Seema loves mother and Sriya does too" The interpretations can be Sriya loves Seema's mother Sriya likes her own mother. Semantic ambiguities born from the fact that generally a computer is not in a position to distinguishing what is logical from what is not. Consider the example: “The car hit the pole while it was moving" The interpretations can be • The car, while moving, hit the pole • The car the pole while the pole was moving. The interpretation is preferred than the second because we have model of the world that helps distinguish what logical (or possible) from what is not. To supply to computer model the world is not so easy. Consider the example: "We saw his duck” Duck can refer person's bird or to a motion he made. Semantic ambiguity happens when a sentence contains an ambiguous word or phrase. munotes.in

Page 10

10 Natural Language Processing
10 4. Discourse Ambiguity: Discourse level processing needs shared world or shared knowledge and interpretation is carried out using this context. Anaphoric ambiguity under discourse level. • Anaphoric Ambiguity: Anaphora's are the entities that have been previously introduced into the discourse. For example, The horse ran up the hill. It was very steep. It soon got tired. The anaphoric reference of ‘it’ in the two situation cause ambiguity. Steep applies to surface hence ‘it’ can be hill. Tired applies to animate object hence ‘it’ can be horse. 5. Pragmatic Ambiguity: Pragmatic ambiguity refers to a situation where the context of a phrase gives it multiple meanings. One of the hardest tasks in NLP. The problem involves processing user intention, sentiment, belief world etc. all of which are highly complex tasks. Consider the example, "Tourist (checking out of the hotel): Waiter, go upstairs to myroom and see it my sandals are there; do not be late; I have to catch the train in 15 minutes." Waiter (running upstairs and coming back panting) Yes sir, they are there. Clearly, the waiter is falling short of the expectation of the tourist, since he does not understand the pragmatics of the situation. Pragmatic ambiguity arises when the statement is not specific, and the context does not provide the information needed to clarify the statement. Information is missing, and must be inferred. Consider the example: "I love you too." This can be interpreted as: • I love you (as well as liking you) • I love you (just like someone else does) • I love you (just like you love me) • I love you (and I love someone else) It is a highly complex task to resolve all these kinds of ambiguities, especially in the upper levels of NLP. The meaning of a word, phrase, or sentence cannot be understood in isolation and contextual knowledge is needed to interpret the meaning, pragmatic and world knowledge is required in higher levels. It is not easy job to create a world model for disambiguation tasks. Linguistic tools and lexical resources are needed for the development of disambiguation techniques. Resourceless languages are lagging behind in these fields compared to resourceful languages in implementation of these techniques. Rule based methods are language specific where as munotes.in

Page 11

11 Introduction stochastic or statistical methods are language independent. Automatic resolution of all these ambiguities contains several long standing problems but again development towards full-fledged disambiguation techniques is required which takes care of all the ambiguities. It is very much necessary for the accurate working of NLP applications such as Machine Translation, Information Retrieval, Question Answering etc. Statistical Approaches of Ambiguity Resolution in Natural Language Processing are: 1. Probabilistic model 2. Part of Speech Tagging • Rule-Based Approaches • Mak Model Approaches • Maxman Entropy Approaches • HMI Based Taggers 3. Machine Learning Approaches 1.6 STAGES IN NLP There are general five steps in natural language processing
Figure 1.6.1 General five steps of NLP munotes.in

Page 12

12 Natural Language Processing
12 1) Lexical Analysis: It is the first stage in NLP. It is also known as morphological analysis. It consists of identifying and analyzing the structure of words. Lexicon of a language means the collection of phrases and words in a language. Lexical analysis is dividing the whole chunk of text into words, sentences, and paragraphs 2) Syntactic Analysis: Syntactic analysis consists of analysis of words in the sentence for grammar and ordering words in a way that shows the relationship among the words. For example the sentence such as “The school goes to boy” is rejected by English syntactic analyzer. 3) Semantic Analysis: Semantic analysis is a structure created by the syntactic analyzer which assigns meanings. This component transfers linear sequences of words into structures. It shows how the words are associated with each other. Semantics focuses only on the literal meaning of words, phrases, and sentences. This only draws the dictionary meaning or the real meaning from the given text. The structures assigned by the syntactic analyzer always have assigned meaning The text is checked for meaningfulness. It is done by mapping syntactic structure and objects in the task domain. E.g. “colorless green idea”. This would be rejected by the Symantec analysis as colorless here; green doesn’t make any sense. 4) Discourse Integration: The meaning of any sentence depends upon the meaning of the sentence just before it. Furthermore, it also brings about the meaning of immediately succeeding sentence. For example, “He wanted that”, in this sentence the word “that” depends upon the prior discourse context. 5) Pragmatic Analysis: Pragmatic analysis concerned with the overall communicative and social content and its effect on interpretation. It means abstracting or deriving the meaningful use of language in situations. In this analysis, what was said is reinterpreted on what it truly meant. It contains deriving those aspects of language which necessitate real world knowledge. E.g., “close the window?” should be interpreted as a request instead of an order. munotes.in

Page 13

13 Introduction
Figure 1.6.2 Stages of NLP Morphological Analysis: Consider we have an English interface to an operating system and the following sentence is typed: “I want to print Bill’s .init file “. Morphological analysis must do the following things: • Pull apart the word “Bill’s” into proper noun “Bill” and the possessive suffix “’s”. • Recognize the sequence “.init” as a file extension that is functioning as an adjective in the sentence. This process will usually assign syntactic categories to all the words in the sentence. Consider the word “prints”. This word is either a plural noun or a third person singular verb (he prints).
munotes.in

Page 14

14 Natural Language Processing
14 Syntactic analysis: This method examines the structure of a sentence and performs detailed analysis of the sentence and semantics of the statement. In order to perform this, the system is expected to have through knowledge of the grammar of the language. The basic unit of any language is sentence, made up of group of words, having their own meanings and linked together to present an idea or thought. Apart from having meanings, words fall under categories called parts of speech. In English languages, there are eight different parts of speech. They are nouns, pronoun, adjectives, verb, adverb, prepositions, conjunction and interjections. In English language, a sentence S is made up of a noun phrase (NP) and a verb phrase (VP), i.e. S=NP+VP The given noun phrase (NP) normally can have an article or delimiter (D) or an adjective (ADJ) and the noun (N), i.e. NP=D+ADJ+N Also a noun phrase may have a prepositional phrase (PP) which has a preposition (P), a delimiter (D) and the noun (N), i.e. PP=D+P+N The verb phrase (VP) has a verb (V) and the object of the verb. The object of the verb may be a noun (N) and its determiner, i.e. VP=V+N+D These are some of the rules of the English grammar that helps one to construct a small parser for NLP.
Syntactic analysis must exploit the results of morphological analysis to build a structural description of the sentence. The goal of this process, called parsing, is to convert the flat list of words that forms the sentence into a structure that defines the units that are represented by that flat list. The important thing here is that a flat sentence has been converted into a hierarchical structure and that the structures correspond to meaning units munotes.in

Page 15

15 Introduction when semantic analysis is performed. Reference markers are shown in the parenthesis in the parse tree. Each one corresponds to some entity that has been mentioned in the sentence. Semantic Analysis: The structures created by the syntactic analyzer assigned meanings. Also, a mapping made between the syntactic structures and objects in the task domain. Moreover, Structures for which no such mapping possible may reject Semantic analysis must do two important things: It must map individual words into appropriate objects in the knowledge base or database It must create the correct structures to correspond to the way the meanings of the individual words combine with each other.
Discourse Integration: The meaning of an individual sentence may depend on the sentences that precede it. And also, may influence the meanings of the sentences that follow it Specifically we do not know whom the pronoun “I” or the proper noun “Bill” refers to. To pin down these references requires an appeal to a model of the current discourse context, from which we can learn that the current user is USER068 and that the only person named “Bill” about whom we could be talking is USER073.Once the correct referent for Bill is known, we can also determine exactly which file is being referred to. munotes.in

Page 16

16 Natural Language Processing
16
Pragmatic Analysis Moreover, The structure representing what said reinterpreted to determine what was actually meant. The final step toward effective understanding is to decide what to do as a results. One possible thing to do is to record what was said as a fact and be done with it. For some sentences, whose intended effect is clearly declarative, that is precisely correct thing to do. But for other sentences, including this one, the intended effect is different. We can discover this intended effect by applying a set of rules that characterize cooperative dialogues. The final step in pragmatic processing is to translate, from the knowledge based representation to a command to be executed by the system. Results of each of the main processes combine to form a natural language system. The results of the understanding process are lpr /ali/stuff.init. All of the processes are important in a complete natural language understanding system. Not all programs are written with exactly these components. Sometimes two or more of them collapsed. Doing that usually results in a system that is easier to build for restricted subsets of English but one that is harder to extend to wider coverage 1.7 CHALLENGES IN NLP There are a number of challenges of natural language processing because natural language is ever-evolving and always somewhat ambiguous. The major challenges around NLP that one must be aware of are as follows: 1. Language differences. Different languages have not only different sets of vocabulary, but also different types of phrasing, different modes of inflection, and different cultural norms. You can resolve this issue with the help of munotes.in

Page 17

17 Introduction “universal” models that can move at least part of what you’ve learned to other languages. However, you have to spend time updating your NLP system for each additional language. 2. Training data NLP is all about studying language to better understand it. For a person to be proficient, it is essential to spend a substantial amount of time listening, reading, and understanding it, Even the best AI must also spend a significant amount of time reading, listening to, and using a language. The training data given to an NLP system determines its capabilities. If you feed the system bad or questionable data, it’s going to learn the wrong things, or learn in an inefficient way. 3. Development time. You also need to think about the development time for an NLP system. The total time taken to develop an NLP system is higher. AI evaluates the data points to process them and use them accordingly. With a shared deep network and many GPUs working together, the training time can be reduced by a few hours. The pre-existing NLP technologies can help in developing the product from scratch. 4. Phrasing ambiguities. Many times it’s hard even for another human being to parse out what someone means when they say something ambiguous. There may not be a clear, concise meaning to be found in analysis of their words. In order to resolve this, an NLP system must be able to seek context that can help it understand the phrasing. It may also need to ask the user for clarity. 5. Misspellings. It is common for humans to make spelling mistakes but it can be easily interpreted by human being. But for a machine, misspellings can be harder to detect it, hence it is essential to employ NLP technology to progress and identify the misspellings. 6. Words with multiple meanings. No language is perfect, and most languages have words that can have multiple meanings, depending on the situation. For example, a user who asks, “how are you?” has a totally different aim than a user who asks something like “how do I add a new debit card?” Good NLP tools should be able to discriminate between these utterances with the help of context. 7. Phrases with multiple intentions. Some words and questions actually have multiple meaning, so your NLP system can’t oversimplify the situation by interpreting only one of them. For example, a user may say to your chatbot with something like, “I need to cancel my previous order and update my card on file.” Your AI needs to be able to distinguish these intentions separately. munotes.in

Page 18

18 Natural Language Processing
18 8. False positives and uncertainty. A false positive occurs when an NLP notices a word that should be intelligible or addressable, but cannot be sufficiently answered. The idea is to develop an NLP system that can recognize its own limitations, and use questions to clear up the ambiguity. 9. Keeping a conversation moving. Many current NLP applications are built on communication between a human and a machine. Accordingly, your NLP AI needs to be able to keep the conversation moving, providing more questions to collect more information or data and always pointing toward a solution. 1.8 APPLICATIOS OF NLP • Machine Translation Machine translation is basically used to convert text or speech from one natural language to another natural language. Machine translation, an integral part of Natural Language Processing where translation is done from source language to target language preserving the meaning of the sentence. Example: Google Translator • Information Retrieval It refers to the human-computer interaction (HCI) that happens when we use a machine to search a body of information for information objects (content) that match our search query. A Person's query is matched against a set of documents to find a subset of 'relevant' document. Examples: Google, Yahoo, Altavista, etc. • Text Categorization Text categorization (also known as text classification or topic spotting) is the task of automatically sorting a set of documents into categories (clusters). Uses of Text Categorization • Filtering of content • Spam filtering Identification of document content • Survey coding • Information Extraction - Identify specific pieces of information in unstructured or semi-structured textual document. Transform unstructured information in a corpus of documents or web pages into a structured database. munotes.in

Page 19

19 Introduction Applied to different types of text: • Newspaper articles • Web pages • Scientific articles • Newsgroup messages • Classified ads • Medical notes • Grammar Correction- In word processor software like MS-word, NLP techniques are widely used for spelling correction & grammar check. • Sentiment Analysis- Sentiment Analysis is also known as opinion mining. It is mainly used on the web to analyse the behaviour, attitude, and emotional state of the sender. This application is implemented through a combination of NLP) and statistics by assigning the values to the text (natural, positive or negative), identify the mood of the context (sad, happy, angry, etc.) • Question-Answering systems- Question Answering focuses on constructing systems that automatically answer the questions asked by humans in a natural language. It presents only the requested information instead of searching full documents like search engine. The basic idea behind the QA system is that the users just have to ask the question and the system will retrieve the most appropriate and correct answer for that question. E.g. Q. “What is the birth place of Shree Krishna? A. Mathura • Spam Detection To detect unwanted e-mails getting to a user's inbox, spam detection is used • Chatbot Chatbot is one of the most important applications of NLP. It is used by many companies to provide the customer's chat services. • Speech Recognition- Speech recognition is used for converting spoken words into text. It is used in applications, such as mobile, home automation, video recovery, dictating to Microsoft Word, voice biometrics, voice user interface, and so on. munotes.in

Page 20

20 Natural Language Processing
20 • Text summarization This task aims to create short summaries of longer documents while retaining the core content and preserving the overall meaning of the text. 1.9 SUMMARY In this chapter we studied what is natural language processing (NLP), history of NLP, generic NLP system, levels of NLP, and knowledge and ambiguity in NLP. Here we also discussed the stages in NLP, challenges and applications of NLP. 1.10 MULTIPLE CHOICE QUSETION ANSWERS i. What is the field of Natural Language Processing (NLP)? a) Computer Science b) Artificial Intelligence c) Linguistics d) All of the mentioned Ans : d ii. What is the main challenge/s of NLP? a) Handling Ambiguity of Sentences b) Handling Tokenization c) Handling POS-Tagging d) All of the mentioned Ans : a iii. Choose form the following areas where NLP can be useful. a) Automatic Text Summarization b) Automatic Question-Answering Systems c) Information Retrieval d) All of the mentioned Ans : d iv. Which of the following includes major tasks of NLP? a) Automatic Summarization b) Discourse Analysis c) Machine Translation d) All of the mentioned Ans : d v. Natural language processing is divided into the two subfields of - a) symbolic and numeric b) understanding and generation c) algorithmic and heuristic d) None of the above. Ans : b munotes.in

Page 21

21 Introduction 1.11 TRUE OR FALSE i. NLP is concerned with the interactions between computers and human (natural) languages. True ii. Machine Translation converts human language to machine language False iii. Modern NLP algorithms are based on machine learning, especially statistical machine learning. True 1.12 SAMPLE QUESTIONS 1. What is NLP? Discuss the different stages in NLP 2. What are the different types of ambiguities present in NLP? How to remove it 3. Explain generic NLP system with a diagram 4. State and explain the different applications and challenges in 5. Explain Components of NLP LIST OF REFERENCES 1. https://www.guru99.com/nlp-tutorial.html 2. https://www.datascienceprophet.com/different-levels-of-nlp/ 3. https://www.slideshare.net/HareemNaz/natural-languageprocessing 4. “Natural Language Processing”, Staredu Solutions. 5. Dan Jurafsky and James Martin. “Speech and Language Processing: An Introduction to Natural Language Processing, Computational Linguistics and Speech Recognition”, Prentice Hall, Second Edition, 2009. 6. http://www.deepsky.com/~merovech/voynich/ voynich_manchu_reference_materials/PDFs/jurafsky_martin.pdf 7. Christopher D.Manning and Hinrich Schutze, ― Foundations of Statistical Natural Language Processing ―, MIT Press, 1999. 8. https://www.cs.vassar.edu/~cs366/docs/ Manning_Schuetze_StatisticalNLP.pdf 9. https://slideplayer.com/slide/4211188/ munotes.in

Page 22

22 Natural Language Processing
22 2 WORD LEVEL ANALYSIS - I Unit Structure 2.0 Objectives 2.0.1 Morphology Analysis 2.0.2 Survey of English Morphology 2.0.3 Inflectional Morphology 2.0.4 Derivational Morphology 2.0.5 Difference of inflectional and derivational morphology 2.0.6 Stemming and Lemmatization 2.1 Summary 2.2 Multiple Choice Question Answers 2.3 List of References 2.1 OBJECTIVES The objective of this module is to learn about morphology, morphology analysis, concentrating mainly on survey of English Morphology. After that we will discuss the Inflectional Morphology & Derivational Morphology. This is followed by a discussion of the difference of Inflectional and Derivational Morphology. At last we will discuss the Stemming and Lemmatization. 2.0.1 MORPHOLOGY ANALYSIS Word is a letter or group of letters that has meaning when spoken, signed or written. Words are orthographic tokens separated by white space. Many languages the distinction between words and sentences is less clear. In Chinese, Japanese languages no white space between words Example: nowhitespace ~ no white space/no whites pace/now hit esp ace In Turkish language words could represent a complete “sentence” Example: uygarlastiramadiklarimizdanmissinizcasina Morphology is a study of word formation. Some words can be divided into two parts but still have meaning. Example: handsome (hand + some). Many words have meaning in themselves but some words have meaning only when used with other words. Example: sleeping, colourful. Some words can stand alone. Example: free, cat, run tree, table, local etc. Words parts must be combined in the correct way and systematically. Morphology deals with the syntax of complex words and parts of words, also called morphemes, as well as with the semantics of their lexical meanings. Understanding how words are formed and what semantic munotes.in

Page 23

23 Word level analysis - I properties they convey through their forms enables human beings to easily recognize individual words and their meanings in discourse. Morpheme is defined as “minimal meaning-bearing unit in a language" Morphology handles the formation of words by using morphemes base form (stem , lemma), e.g., believe affixes (suffixes, prefixes, infixes), e.g., un-, -able, -ly Morphological parsing is the task of recognizing the morphemes inside a word e.g., hands, foxes, children and it’s important for many tasks machine translation, information retrieval, ,in parsing, and text simplification, etc 2.0.2 SURVEY OF ENGLISH MORPHOLOGY Morphology concerns the structure of words. Words are assumed to be made up of morphemes, which are the minimal information carrying unit. So for example the word dog consists of a single morpheme (the morpheme dog) while the word cats consists of two: the morpheme cat and the morpheme-s. Consider a word like: "unhappyness". This has three parts as shown in figure 2.1.2
Figure 2.1.2 There are three morphemes, each carrying a certain amount of meaning. un means "not", while ness means "being in a state or condition". Happy is a free morpheme because it can appear on its own (as a "word" in its own right). Bound morphemes have to be attached to a free morpheme, and so cannot be words in their own right. Thus you can't have sentences in English such as "Jason feels very un ness today". We can usefully divide morphemes into two broad classes of morphemes: stems and affixes. • The stem is the “main” morpheme of the word, supplying the main meaning • The affixes add “additional” meanings of various kinds. munotes.in

Page 24

24 Natural Language Processing
24
Affixes are further divided into prefixes, suffixes, infixes, and circumfixes. • prefixes precede the stem, • suffixes follow the stem, • circumfixes do both, • infixes are inserted inside the stem. For example, the word cats is composed of a stem cat and the suffix -s. The word undo is composed of a stem do and the prefix un-. Good examples of circumfixes are e.g Unreachable, Unbelievable. Infixes, in which a morpheme is inserted in the middle of a word, occur very commonly for example in the Philipine language Tagalog. For example the affix um, which marks the agent of an action, is infixed to the Tagalog stem hingi “borrow” to produce humingi (ask for or to demand). A word can have more than one affix. For example, the word rewrites has the prefix re-, the stem write, and the suffix -s. The word unbelievably has a stem (believe) plus three affixes (un-, -able, and -ly). There are many ways to combine morphemes to create words. Four of these methods are common and play important roles in speech and language processing: inflection, derivation, compounding, and cliticization. Inflection is the combination of a word stem with a grammatical morpheme, usually resulting in a word of the same class as the original stem, and usually filling some syntactic function like agreement. For example, English has the inflectional morpheme -s for marking the plural on nouns, and the inflectional morpheme –ing for marking the present tense on verbs. e.g. clean (verb), clean-ing (verb) Derivation is the combination of a word stem with a grammatical morpheme, usually resulting in a word of a different class, often with a meaning hard to predict exactly. For example the verb delight can take the munotes.in

Page 25

25 Word level analysis - I derivational suffix -ful to produce the adjective delightful. e.g delight (verb), delight-ful (adj) Compounding is the combination of multiple words stems together. In English compounds can be written together, for example, notebook, bookstore, fireman etc. For example the noun doghouse is the concatenation of the morpheme dog with the morpheme house. Finally, cliticization is the combination of a word stem with a clitic. A clitic is a morpheme that acts syntactically like a word, but is reduced in form and attached (phonologically and sometimes orthographically) to another word. For example the English morpheme’ve in the word I’ve is a clitic. That is different words from different syntactic categories, e.g. I’ve = I + have. 2.0.3 INFLECTIONAL MORPHOLOGY Inflection is a morphological process that adapts existing words so that they function effectively in sentences without changing the category of the base morpheme. Inflectional affixes are only suffixes which express grammatical features such as singular/plural, past/present forms of verbs. The study of such morphemes is called inflectional morphemes. Examples: bigger (big+er), loves (love+s). English has a relatively simple inflectional system; only nouns, verbs, and sometimes adjectives can be inflected, and the number of possible inflectional affixes is quite small. English nouns have only two kinds of inflection: an affix that marks plural and an affix that marks possessive. For example, many English nouns can either appear in the singular form, or take a plural suffix. Here are examples of the regular plural suffix -s (also spelled -es), and irregular plurals and sometimes -x (box/boxes). Nouns ending in -y preceded by a consonant change the -y to -i (butterfly/butterflies). Table 2.1.3.1 Regular Nouns Irregular Nouns Singular cat thrush mouse ox Plural cats thrushes mice oxen The possessive suffix is realized by apostrophe + -s for regular singular nouns (llama’s) and plural nouns not ending in -s (children’s) and often by a lone apostrophe after regular plural nouns (llamas’) and some names ending in -s or -z (Euripides’ comedies). English verbal inflection is more complicated than nominal inflection. First, English has three kinds of verbs; munotes.in

Page 26

26 Natural Language Processing
26 • main verbs, (eat, sleep, impeach), • modal verbs (can, will, should), • primary verbs (be, have, do). Here we will mostly be concerned with the main and primary verbs, because it is these that have inflectional endings. Of these verbs a large class are regular, that is to say all verbs of this class have the same endings marking the same functions. These regular verbs (e.g. walk, or inspect) have four morphological forms. These verbs are called regular because just by knowing the stem we can predict the other forms by adding one of three predictable endings and making some regular spelling changes. These regular verbs and forms are significant in the morphology of English first because they cover a majority of the verbs, and second because the regular class is productive. As discussed earlier, a productive class is one that automatically includes any new words that enter the language. For example the recently-created verb fax (My mom faxed me the note from cousin Everett) takes the regular endings -ed, -ing, -es. (Note that the -s form is spelled faxes rather than faxs). The table 2.0.3.2 shows the morphological forms for regular verbs. Table 2.0.3.2 Morphological
Form Classes Regularly Inflected Ve rbs stem talk merge cry map -s form talks merg es cries maps -ing participle talking merging crying mapping Past form or -ed
participle talked merged cried mapped The irregular verbs are those that have some more or less idiosyncratic forms of inflection. Irregular verbs in English often have five different forms, but can have as many as eight (e.g., the verb be) or as few as three (e.g. cut or hit). While constituting a much smaller class of verbs estimate there are only about 250 irregular verbs, not counting auxiliaries), this class includes most of the very frequent verbs of the language. The table 2.4.3 shows some sample irregular forms. Note that an irregular verb can inflect in the past form (also called the preterite) by changing its vowel (eat/ate), or its vowel and some consonants (catch/caught), or with no change at all (cut/cut). The table 2.1.3.3 shows the morphological forms for irregular verbs. Table 2.1.3.3 Morphological Form Classes Irregularly Inflected Verbs stem eat catch put -s form eats catches puts -ing participle eating catching putting Past form ate caught put -ed participle eaten caught put munotes.in

Page 27

27 Word level analysis - I The -s form is used in the “habitual present” form to distinguish the third-person singular ending (She jogs every Tuesday) from the other choices of person and number (I/you/we/they jog every Tuesday). The stem form is used in the infinitive form, and also after certain other verbs (I’d rather walk home, I want to walk home). The -ing participle is used in the progressive construction to mark present or ongoing activity (It is raining), or when the verb is treated as a noun; this particular kind of nominal use of a verb is called a gerund use: Fishing is fine if you live near water. The -ed participle is used in the perfect construction (He’s eaten lunch already) or the passive construction (The verdict was overturned yesterday). In addition to noting which suffixes can be attached to which stems, we need to capture the fact that a number of regular spelling changes occur at these morpheme boundaries. For example, a single consonant letter is doubled before adding the -ing and -ed suffixes (beg/begging/begged). If the final letter is “c”, the doubling is spelled “ck” (picnic/picnicking/picnicked). If the base ends in a silent -e, it is deleted before adding -ing and -ed (merge/merging/merged). Just as for nouns, the -s ending is spelled -es after verb stems ending in -s (toss/tosses), -z, (waltz/waltzes) -sh, (wash/washes) -ch, (catch/catches) and sometimes -x (tax/taxes). Also like nouns, verbs ending in –y preceded by a consonant change the -y to -i (try/tries). 2.0.4 DERIVATIONAL MORPHOLOGY Derivation is concerned with the way morphemes are connected to existing lexical forms as affixes. English inflection is relatively simple compared to other languages, derivation in English is quite complex. Recall that derivation is the combination of a word stem with a grammatical morpheme, usually resulting in a word of a different class, often with a meaning hard to predict exactly. The common kind of derivation in English is the formation of new nouns, often from verbs or adjectives. This process is called nominalization. For example, the suffix -ation produces nouns from verbs ending often in the suffix -ize (computer-ize → computerization). The table 2.0.4.1 shows the formation of new nouns, often from verbs or adjectives. Table 2.0.4.1 Suffix Base
Verb/Adjective Derived Noun -ation computerize (V) computerization -ee appoint (V) appointee -er kill (V) killer -ness fuzzy (A) fuzziness munotes.in

Page 28

28 Natural Language Processing
28 Adjectives can also be derived from nouns and verbs. The table 2.0.4.2 shows adjectives derived from the verbs or noun. Table 2.0.4.2 Suffix Base Noun/Verb Derived Adjective -al
-able
-less computation (N)
embrace (V)
clue (N) computational
embraceable
clueles s Derivation in English is more complex than inflection for a number of reasons. One is that it is generally less productive; even a nominalizing suffix like -ation, which can be added to almost any verb ending in -ize, cannot be added to absolutely every verb. Thus we can’t say *eatation or *spellation (we use an asterisk (*) to mark “non-examples” of English). Another is that there are subtle and complex meaning differences among nominalizing suffixes. For example sincerity has a subtle difference in meaning from sincereness. 2.0.5 DIFFERENCE OF INFLECTIONAL AND DERIVATIONAL MORPHOLOGY 1) Inflectional morphemes never change the grammatical category (part of speech) of a word. For example, tall and taller are both adjectives. The inflectional morpheme -er (comparative marker) simply produces a different version of the adjective tall. derivational morphemes often change the part of speech of a word. Thus, the verb read becomes the noun reader when we add the derivational morpheme -er. It is simply that read is a verb, but reader is a noun example:-For example, such derivational prefixes as re- and un- in English generally do not change the category of the word to which they are attached. Thus, both happy and unhappy are adjectives, and both fill and refill are verbs, for example. The derivational suffixes -hood and -dom, as in neighborhood and kingdom, are also the typical examples of derivational morphemes that do not change the grammatical category of a word to which they are attached. 2) When a derivational suffix and an inflectional suffix are added to the same word, they always appear in a certain relative order within the word That is, inflectional suffixes follow derivational suffixes. Thus, the derivational (-er) is added to read, then the inflectional (-s) is attached to produce readers. Similarly, in organize– organizes the inflectional -s comes after the derivational -ize. When an inflectional suffix is added to a verb, as with organizes, then we cannot add any further derivational suffixes It is impossible to have a form like organizesable, with inflectional -munotes.in

Page 29

29 Word level analysis - I s after derivational - able because inflectional morphemes occur outside derivational morphemes and attach to the base or stem. 3) A third point worth emphasizing is that certain derivational morphemes serve to create new base forms or new stems to which we can attach other derivational or inflectional affixes. For example, we use the derivational -atic to create adjectives from nouns, as in words like systematic and problematic. 2.0.6 STEMMING AND LEMMATIZATION In natural language processing, there may come a time when you want your program to recognize that the words “ask” and “asked” are just different tenses of the same verb. This is the idea of reducing different forms of a word to a core root. Words that are derived from one another can be mapped to a central word or symbol, especially if they have the same core meaning. “When we are running a search, we want to find relevant results not only for the exact expression we typed on the search bar, but also for the other possible forms of the words we used. For example, it’s very likely we will want to see results containing the form “shoot” if we have typed “shoots” in the search bar.” This can be achieved through two possible methods: stemming and lemmatization. The aim of both processes is the same: reducing the inflectional forms of each word into a common base or root. However, these two methods are not exactly the same. Example: Affectation, affects, affections, affected, affection, affecting -> all of these came from single root work affect. Stemming Stemming algorithms work by cutting off the end or the beginning of the word, taking into account a list of common prefixes and suffixes that can be found in an inflected word. This indiscriminate cutting can be successful on some occasions, but not always, and that is why we affirm that this approach presents some limitations.
Ex: writing writ + ing (or write + ing) munotes.in

Page 30

30 Natural Language Processing
30 Lemmatization Lemmatization usually refers to doing things properly with the use of a vocabulary and morphological analysis of words, normally aiming to remove inflectional endings only and to return the base or dictionary form of a word, which is known as the lemma Example: Lemmatization will map gone, going and went->Go. • Output of Lemmatization is proper word • If confronted with the token saw, stemming might return just s, whereas lemmatization would attempt to return either see or saw depending on whether the use of the token was as a verb or a noun.

How do they work? • Stemming: there are different algorithms that can be used in the stemming process, but the most common in English is Porter stemmer. The rules contained in this algorithm are divided in five different phases numbered from 1 to 5. The purpose of these rules is to reduce the words to the root. • Lemmatization: the key to this methodology is linguistics. To extract the proper lemma, it is necessary to look at the morphological analysis of each word. This requires having dictionaries for every language to provide that kind of analysis. Difference between Stemming and Lemmatization: Sr.no Stemming Lemmatization 1 Stemming is used to
group words with a
similar basic meaning
together Lemmatization concept is used to
make dictionary or WordNet kind
of dictionary 2 Accuracy is less Accuracy is more as compared to
stemming. 3 Stemming is preferred
when the meaning of the
word is not important for
analysis. Exampl e: Spam
detection Lemmatization would be
recommended when the meaning
of the word is not important for
analysis. Example: Question
Answer munotes.in

Page 31

31 Word level analysis - I 4 Stemming usually
operates on single word
without knowledge of the
context Lemmatization usually considers
words and the context of the word
in the sentence 5 When we convert any
word into root form then
stemming may create the
non-existence meaning of
word. Lemmatization always gives the
dictionary meaning word while
converting into root form 6 Stemming for the word
"studies" is studi Lemma for the word "studies" is
study 2.1 SUMMARY In this chapter we studied concept of morphology, morphology analysis in detailed, and survey of English Morphology. Morphological parsing is the process of finding the constituent morphemes in a word. We discussed the Inflectional morphology & Derivational morphology, English mainly uses prefixes and suffixes to express inflectional and derivational morphology. English inflectional morphology is relatively simple and includes person and number agreement (-s) and tense markings (-ed and -ing). English derivational morphology is more complex and includes suffixes like -ation, -ness, -able as well as prefixes like co- and re-. Here we also discussed stemming and Lemmatization. 2.2 MULTIPLE CHOICE QUSETION ANSWERS i. In linguistic morphology, _____________ is the process for reducing inflected words to their root form. a) Rooting b) Stemming c) Text-Proofing d) Both a & b Ans : b ii. ________ techniques looks at the meaning of the word a) Stemming b) Stop Word c) Leematization d) Marphological Analysis Ans : c munotes.in

Page 32

32 Natural Language Processing
32 iii. _________is the study of the internal structure of words, and the rules by which words are formed a) Syntax b) Semantics c) Pragmatics d) Morphing Ans : d iv. Lemma for the word "studies" is_______________ a) studies b) ies c) studi d) study Ans : d v. Stemming for the word "studies" is_______________ a) studies b) ies c) studi d) study Ans : c TRUE OR FALSE i. Derivational morphemes form new lexemes conveying new meanings True ii. Lemmatization involves resolving words to their dictionary form. True iii. Inflectional morphemes change the grammatical category (part of speech) of a word. False SAMPLE QUESTIONS 1. Define morpheme, stem and affixes. 2. Explain stemming and lemmatization with example 3. Explain with examples Inflectional morphology & Derivational morphology 4. State differences between inflectional and derivational morphemes munotes.in

Page 33

33 Word level analysis - I 2.3 LIST OF REFERENCES 1. “Natural Language Processing”, Staredu Solutions. 2. Dan Jurafsky and James Martin. “Speech and Language Processing: An Introduction to Natural Language Processing, Computational Linguistics and Speech Recognition”, Prentice Hall, Second Edition, 2009. 3. http://www.deepsky.com/~merovech/voynich/ voynich_manchu_reference_materials/PDFs/jurafsky_martin.pdf 4. Christopher D.Manning and Hinrich Schutze, ― Foundations of Statistical Natural Language Processing ―, MIT Press, 1999. 5. https://cl-illc.github.io/nlp1/resources/slides/Morphology-notes.pdf 6. https://www.cs.vassar.edu/~cs395/docs/3.pdf munotes.in

Page 34

34 Natural Language Processing
34 3 WORD LEVEL ANALYSIS - II Unit Structure 3.0 Objectives 3.1 Regular expression 3.2 Finite Automata 3.3 Finite State Morphological Parsing 3.4 Building a Finite State Lexicon 3.5 Finite State Transducers (FST) 3.6 Morphological Parsing with FST 3.7 Lexicon free FST Porter Stemmer 3.8 N –Grams 3.9 N-Gram Language Model 3.10 Summary 3.11 Multiple Choice Question Answers 3.12 True or False 3.13 Sample Questions 3.14 List of References 3.0 OBJECTIVES The objective of this module is to learn about Regular expression (RE), Finite Automata, Finite state morphological parsing, how to build finite state lexicon, and Finite State Transducers (FST). After that we will discuss the Morphological Parsing with FST. This is followed by a discussion of Lexicon free FST Porter Stemmer. Finally we will discuss N –Grams- N-gram language model. 3.1 REGULAR EXPRESSION Regular expressions are defined as a sequence of characters that are mainly used to find substrings in a given string. A regular expression (RE) is a language for specifying text search strings. It helps us to match or extract other strings or sets of strings, with the help of a specialized syntax present in a pattern. For Example, extracting all hashtags from a tweet, getting phone numbers, email ID etc from large unstructured text content. Regular Expressions are used in various tasks such as Data pre-processing, Text feature Engineering, Data Extraction, Rule-based information Mining systems, Pattern Matching, Web scraping, etc. munotes.in

Page 35

35 Word Level Analysis - II Properties of Regular Expressions Some of the important properties of Regular Expressions are as follows: 1. Regular Expression (RE) is a formula in a special language, which can be used for specifying a sequence of symbols, simple classes of strings. In simple words, we can say that regular Expression is an algebraic notation for characterizing a set of strings. 2. Regular expression requires two things, one is the pattern that we want to search and the other is a corpus of text or a string from which we need to search the pattern. For example, the Unix command-line tool grep takes a regular expression and returns every line of the input document that matches the expression Regular Expression can be defined in the following manner: 1. ε is a Regular Expression, which indicates that the language is having an empty string. 2. φ is a Regular Expression which denotes that it is an empty language. 3. If X and Y are Regular Expressions, then the following expressions are also regular. • X, Y • X.Y(Concatenation of XY) • X+Y (Union of X and Y) • X*, Y* (Kleen Closure of X and Y) 4. If a string is derived from the above rules then that would also be a regular expression. How can Regular Expressions be used in NLP? In NLP, we can use Regular expressions at many places such as, 1. To validate data fields. For example, URLs, dates, email address, abbreviations, etc. 2. To filter a particular text from the whole corpus. For example, disallowed websites, spam etc. 3. To identify particular strings in a text. For example, token boundaries 4. To convert the output of one processing component into the format required for a second component Basic Regular Expression Patterns Brackets ([ ]): They are used to specify a disjunction of characters. munotes.in

Page 36

36 Natural Language Processing
36 For Examples, /[A-Z]/ → matches an uppercase letter /[a-z]/ → matches a lowercase letter /[0–9]/ → matches a single digit
For Examples, /[cC]hirag/ → Chirag or chirag /[xyz]/ → ‘x’, ‘y’, or ‘z’ /[1234567890]/ → any digit Here slashes represent the start and end of a particular expression. Dash (-): They are used to specify a range.
Caret (^): They can be used for negation or just to mean ^. For Examples, /[ˆa-z]/ → not an lowercase letter /[ˆCc]/ → neither ‘C’ nor ‘c’ /[ˆ.]/ → not a period /[cˆ]/ → either ‘c’ or ‘ˆ’ /xˆy/ → the pattern ‘xˆy’
munotes.in

Page 37

37 Word Level Analysis - II Question mark (?): It marks the optionality of the previous expression. For Examples, /maths?/ → math or maths /colou?r/ → color or colour
Period (.): Used to specify any character between two expressions. /beg.n/ → Match any character between which fits between beg and n such as begin, begun
Anchors : These are special characters that help us to perform string operations either at the beginning or at the end of text input. They are used to assert something about the string or the matching process. The most common anchors are the caret ^ and the dollar sign $. i) Caret character ‘^’ It specifies the start of the string. For a string to match the pattern, the character followed by the ‘^’ in the pattern should be the first character of the string. For Examples, ^The: Matches a string that starts with ‘The’ ii) Dollar character ‘$’ It specifies the end of the string. For a string to match the pattern, the character that precedes the ‘$’ in the pattern should be the last character in the string. For Examples, end$: Matches a string that ends with ‘end’ ^The end$’: Exact string match (starts and ends with ‘The end’) roar: Matches a string that has the text roar in it. munotes.in

Page 38

38 Natural Language Processing
38 Quantifiers: They allow us to mention and control over how many times a specific character(s) pattern should occur in the given text. The most common Quantifiers are: *, +, ? and { }
For Examples, abc*: matches a string that has 'ab' followed by zero or more 'c'. abc+: matches 'ab' followed by one or more 'c' abc?: matches 'ab' followed by zero or one 'c' abc{2}: matches 'ab' followed by 2 'c' abc{2, }: matches 'ab' followed by 2 or more 'c' abc{2, 5}: matches 'ab' followed by 2 upto 5 'c' a(bc)*: matches 'a' followed by zero or more copies of the sequence 'bc' 3.2 FINITE AUTOMATA The term automata, derived from the Greek word "αὐτόματα. Automaton may be defined as an abstract self-propelled computing device that follows a predetermined sequence of operations automatically. An automaton having a finite number of states is called a Finite Automaton (FA) or Finite State automata (FSA). The finite-state automaton is not only the mathematical device used to implement regular expressions, but also one of the most significant tools of computational linguistics. Variations of automata such as finite- state transducers, Hidden Markov Models, and N-gram grammars are important components of the speech recognition and synthesis, spell-checking, and information-extraction applications. Mathematically, an automaton can be represented by a 5-tuple (Q, Σ, δ, q0, F), where − • Q is a finite set of states. • Σ is a finite set of symbols, called the alphabet of the automaton. • δ is the transition function • q0 is the initial state from where any input is processed (q0 ∈ Q). • F is a set of final state/states of Q (F ⊆ Q). munotes.in

Page 39

39 Word Level Analysis - II An RE is one way of describing finite state automata (FSA). An RE is one way of characterizing a particular kind of formal language called a regular language. Regular grammar is the equivalent ways of describing regular languages. Relation between Finite Automata, Regular Grammars and Regular Expressions • As we know that finite state automata are the theoretical foundation of computational work and regular expressions is one way of describing them. • We can say that any regular expression can be implemented as FSA and any FSA can be described with a regular expression. • On the other hand, regular expression is a way to characterize a kind of language called regular language. Hence, we can say that regular language can be described with the help of both FSA and regular expression. • Regular grammar, a formal grammar that can be right-regular or left-regular, is another way to characterize regular language.
Figure 3.2.1 Relation between Finite Automata, Regular languages and Regular Expressions Finite state automation is of two types: • Deterministic Finite automation (DFA) • Non-deterministic Finite Automation (NDFA) 1. Deterministic Finite automation (DFA) It may be defined as the type of finite automation wherein, for every input symbol we can determine the state to which the machine will move. It has a finite number of states that is why the machine is called Deterministic Finite Automaton (DFA). Mathematically, a DFA can be represented by a 5-tuple (Q, Σ, δ, q0, F), where − • Q is a finite set of states. • Σ is a finite set of symbols, called the alphabet of the automaton. • δ is the transition function where δ: Q × Σ → Q . • q0 is the initial state from where any input is processed (q0 ∈ Q). • F is a set of final state/states of Q (F ⊆ Q). munotes.in

Page 40

40 Natural Language Processing
40 Whereas graphically, a DFA can be represented by diagraphs called state diagrams where − The states are represented by vertices. The transitions are shown by labeled arcs. The initial state is represented by an empty incoming arc. The final state is represented by a double circle. Construct the state diagram for the finite-state automata M= (Q, Σ, δ, q0, F),, where Q = {q0, q1, q2, q3}, Σ = {0,1}, F= {q0, q3} and the transition function δ is given in the following table. State 0 1 q0 q0 q1 q1 q0 q2 q2 q0 q0 q3 q2 q1
2. Non-deterministic Finite Automation (NDFA) It may be defined as the type of finite automation where for every input symbol we cannot determine the state to which the machine will move i.e. the machine can move to any combination of the states. It has a finite number of states that is why the machine is called Non-deterministic Finite Automation (NDFA). Mathematically, NDFA can be represented by a 5-tuple (Q, Σ, δ, q0, F), where − ● Q is a finite set of states. ● Σ is a finite set of symbols, called the alphabet of the automaton. δ :-is the transition function where δ: Q × Σ → 2 Q. ● q0 :-is the initial state from where any input is processed (q0 ∈ Q). ● F :-is a set of final state/states of Q (F ⊆ Q). q2
munotes.in

Page 41

41 Word Level Analysis - II The finite state automaton M= (Q, Σ, q0, δ, F), where Q= {a, b, c }, Σ ={0,1}, F={c}, and δ is depicted graphically as follows:
State 0 1 a a, b b b c a, c c b, c c 3.3 FINITE STATE MORPHOLOGICAL PARSING To know the structure about a word when we perform the morphological parsing for that word. Given a surface form (input form), e.g., “going” we might produce the parsed form: verb-go + gerund-ing. Morphological parsing can be done with the help of finite-state transducer. A morpheme is a meaning bearing unit of any language. For example, cats: has two morphemes, cat, -s. The objective of the morphological parsing is to produce output lexicons for single input lexicon. Our aim is to take input forms like in the first column of Table 3.3.1 and produce the output like in second column. The second column contains the stem of each word as well as mixed morphological features. These features include, like N (noun), V (verb), specify additional information about the word stem, e.g., +N means that word is noun, +SG means singular, +PL for plural, etc. Table 3.3.1 Mapping of input word to Morphemes.
munotes.in

Page 42

42 Natural Language Processing
42 To build morphological parser, we need at least following database: 1. Lexicon: List of stems, and affixes, plus additional information about them, like +N, +V. 2. Morphotactics rules: Rules about ordering of morphemes in a word, e.g. -ed is followed after a verb (e.g., worked, studied), un (undo) precede a verb, for example, unlock, untie, etc. 3. Orthographic rules (spelling): For combining morphemes, e.g., city+ -s gives cities and not citys. 3.4 BUILDING A FINITE-STATE LEXICON A lexicon is a repository for words. They are grouped according to their main categories like noun, adjective, verb, adverb etc. They may be divided in to sub categories like regular-nouns, irregular-singular nouns, irregular-plural nouns. The simplest possible lexicon would consist of an explicit list of every word of the language (every word, i.e., including abbreviations (“AAA”) and proper names (“Joy” or “Bebo”)) as follows: a, AAA, AA, Aachen, aardvark, aardwolf, aba, abaca, aback, The simplest way to create a morphological parser put all possible words in to lexicon. As it’s often impossible, for the various reasons, to list every word in the language, computational lexicons are usually structured with a list of each of the stems and affixes of the language together with a representation of the morphotactics that tells us how they can fit together. There are many ways to model morphotactics; one of the most common is the finite state automaton. A very simple finite-state model for English nominal inflection might look like Fig. 3.4.1.
Figure 3.4.1 A finite-state automaton for English nominal inflection. The FSA in Fig. 3.4.1 assumes that the lexicon includes regular nouns (reg-noun) that take the regular -s plural (e.g. dog, fox, cat, and aardvark). The lexicon also includes irregular noun forms that don’t take -s, both singular irreg-sg-noun (goose, mouse) and plural irreg-pl-noun (geese, mice). munotes.in

Page 43

43 Word Level Analysis - II reg-noun irreg -pl-noun irreg -sg-noun plural fox cat
aardvark geese sheep
mice goose sheep
mouse -s A similar model for English verbal inflection might look like Fig. 3.4.2
Figure 3.4.2 A finite-state automaton for English verbal inflection This lexicon has three stem classes (reg-verb-stem, irreg-verb-stem, and irreg-past- verb-form), plus four more affix classes (-ed past, -ed participle, -ing participle, and third singular -s): reg-
verb -
stem irreg -
verb-
stem irreg -
past-
verb past past-
part pres-
part 3sg
walk
cut
caught
-ed
-ed
-ing
-s fry speak ate talk sing eaten impeac
h sang English derivational morphology is significantly more complex than English inflectional morphology, and so automata for modeling English derivation tend to be quite complex. An initial hypothesis might be that adjectives can have an optional prefix (un-), an obligatory root (big, cool, etc.) and an optional suffix (-er, -est, or -ly). This might suggest the FSA in Fig. 3.4.3. big, bigger, biggest, cool, cooler, coolest, coolly happy, happier, happiest, happily red, redder, reddest unhappy, unhappier, unhappiest, unhappily real, unreal, really clear, clearer, clearest, clearly, unclear, unclearly munotes.in

Page 44

44 Natural Language Processing
44 Figure 3.4.3 An FSA for a fragment of English adjective morphology An FSA for another fragment of English adjective morphology is shown in Fig. 3.4.4.
Figure 3.4.4 An FSA for another fragment of English derivational morphology.
Figure 3.4.5 Expanded FSA for a few English nouns with their inflection
munotes.in

Page 45

45 Word Level Analysis - II Expanded FSA for a few English nouns with their inflection is shown in Fig, 3.4.5. Note that this automaton will incorrectly accept the input foxs. 3.5 FINITE STATE TRANSDUCERS (FST) FSAs can be used to recognise particular patterns but don’t, by themselves, allow for any analysis of word forms. Hence for morphology, we use finite state transducers (FSTs) which allow the surface structure to be mapped into the list of morphemes. FSTs are useful for both analysis and generation, because the mapping is bidirectional. This approach is known as two-level morphology. FST is a type of finite automaton which maps between two sets of symbols. We can visualize an FST as a two-tape automaton which recognizes or generates pairs of strings. We can do this by labelling each arc in the finite-state machine with two symbol strings, one from each tape. Fig 3.5.1 shows an example of an FST where each arc is labelled by an input and output string, separated by a colon.
Figure 3.5.1 A Finite-state transducer FSA defines a formal language by defining a set of strings, an FST defines a relation between sets of strings. In short, FST is as a machine that reads one string and generates another. Four-fold way of thinking about transducer: i. FST as recognizer: a transducer that takes a pair of strings as input and outputs accept if the string-pair is in the string-pair language, and reject if it is not. ii. FST as generator: a machine that outputs pairs of strings of the language. Means the output is a yes or no, and a pair of output strings. iii. FST as translator: a machine that reads a string and outputs another string iv. FST as set relater: a machine that computes relations between sets. For morphological parsing (and for many other NLP applications), we can apply the FST as translator metaphor, taking as input a string of letters and producing as output a string of morphemes. munotes.in

Page 46

46 Natural Language Processing
46 Formal definition an FST can be defined with 7 parameters: Q: a finite set of N states q0, q1, . . . , qN−1 Σ: a finite set corresponding to the input alphabet Δ: a finite set corresponding to the output alphabet q0 ∈ Q: start state F ⊆ Q: set of final states δ(q, w): the transition function between states; Given a state q ∈ Q and a string w ∈ Σ∗, δ(q, w) returns a set of new states Q′ ∈ Q. δ is thus a function from Q × Σ∗ to 2Q (because there are 2Q possible subsets of Q). δ returns a set of states rather than a single state because a given input may be ambiguous in which state it maps to. σ(q, w): the output function giving the set of possible output strings for each state and input. Given a state q ∈ Q and a string w ∈ Σ∗, σ(q, w) gives a set of output strings, each a string o ∈ Δ∗. σ is thus a function from Q ×Σ∗ to 2Δ∗ Where FSAs are isomorphic to regular languages, FSTs are isomorphic to regular relations. Regular relations are sets of pairs of strings, a natural extension of the regular languages, which are sets of strings. Like FSAs and regular languages, FSTs and regular relations are closed under union, although in general they are not closed under difference, complementation and. Besides union, FSTs have two additional closure properties that turn out to be extremely useful: ● Inversion: The inversion of a transducer T (T −1) simply switches the input and output labels. Thus if T maps from the input alphabet I to the output alphabet O, T −1 maps from O to I. Inversion is useful because it makes it easy to convert a FST-as-parser into an FST- as-generator. T = {(a, a1), (a, a2), (b, b1), (c, c1), (c, a)} T-1 = {(a1, a), (a2, a), (b1, b), (c1, c), (a, c) ● Composition: If T1 is a transducer from I1 to O1 and T2 a transducer from O1 to O2, then T1 ◦ T2 maps from I1 to O2. Composition is useful because it allows us to take two transducers that run in series and replace them with one more complex transducer. Composition works as in algebra; applying T1 ◦ T2 to an input sequence S is identical to applying T1 to S and then T2 to the result; thus T1 ◦ T2(S) = T2 (T1(S)). munotes.in

Page 47

47 Word Level Analysis - II
Fig. 3.5.2, for example, shows the composition of [a:b]+ with [b:c]+ to produce [a:c]+. Figure 3.5.2 The composition of [a: b]+ with [b:c]+ to produce [a:c]+. The projection of an FST is the FSA that is produced by extracting only one side of the relation. We can refer to the projection to the left or upper side of the relation as the upper or first projection and the projection to the lower or right side of the relation as the lower or second projection 3.6 MORPHOLOGICAL PARSING WITH FST Now we see the task of morphological parsing. If we give the input cats, we’d like to output cat +N +Pl, telling us that cat is a plural noun In the finite-state morphology paradigm, we represent a word as a correspondence between a lexical level (which represents a concatenation of morphemes making up a word) and the surface level (which represents the concatenation of letters which make up the actual spelling of the word). Fig. 3.6.1 shows these two levels for (English) cats.
Figure 3.6.1 Schematic examples of the lexical and surface tapes The actual transducers consist of intermediate tapes also. For finite-state morphology it’s convenient to view an FST as having two tapes. The lexical tape is composed from characters from one alphabet Σ. The surface tape is composed of characters from another alphabet Δ. In the two-level morphology, we allow each arc only to have a single symbol from each alphabet. We can then combine the two symbol alphabets Σ and Δ to create a new alphabet, Σ′, which makes the relationship to FSAs quite clear. Σ′ is a finite alphabet of complex symbols. Each complex symbol is composed of an input-output pair i : o; one symbol i from the input alphabet Σ, and one symbol o from an output alphabet Δ, thus Σ′ ⊆ Σ×Δ. Thus where an FSA accepts a language stated over a finite alphabet of single symbols, such as the alphabet of our sheep language: Σ = {b, a, ! } an FST defined this way accepts a language stated over pairs of symbols, as in: munotes.in

Page 48

48 Natural Language Processing
48 Σ′ = {a : a, b : b, ! : !, a : !, a : ǫ, ǫ : !} In two-level morphology, the pairs of symbols in Σ′ are also called feasible pairs. Thus each feasible pair symbol a : b in the transducer alphabet Σ′ expresses how the symbol a from one tape is mapped to the symbol b on the other tape. For example a : ǫ means that an a on the lexical tape will correspond to nothing on the surface tape. Just as for an FSA, we can write regular expressions in the complex alphabet Σ′. Since it’s most common for symbols to map to themselves, in two-level morphology we call pairs like a : a default pairs, and just refer to them by the single letter a. We can now build an FST morphological parser out of our earlier morphotactic FSAs and lexica by adding an extra “lexical” tape and the appropriate morphological features. Fig. 3.6.2 shows an augmentation of Fig. 3.4.1 with the nominal morphological features (+Sg and +Pl) that correspond to each morpheme. The symbol ˆ indicates a morpheme boundary, while the symbol # indicates a word boundary. The morphological features map to the empty string ǫ or the boundary symbols since there is no segment corresponding to them on the output tape.
Figure 3.6.2 A schematic transducer for English nominal number inflection Tnum. The symbols above each arc represent elements of the morphological parse in the lexical tape; the symbols below each arc represent the surface, using the morpheme-boundary symbol ˆ and word-boundary marker #. The arcs need to be expanded by individual words in the lexicon. In order to use Fig. 3.6.2 as a morphological noun parser, it needs to be expanded with all the individual regular and irregular noun stems, replacing the labels reg-noun etc. In order to do this we need to update the lexicon for this transducer, so that irregular plurals like geese will parse into the correct stem goose +N +Pl. We do this by allowing the lexicon to also have two levels. Since surface geese maps to lexical goose, the new lexical entry will be “g:g o:e o:e s:s e:e”. Regular forms are simpler; the two-level entry for fox will now be “f:f o:o x:x”, but by relying on the orthographic convention that f stands for f:f and so on, we can simply refer to it as fox and the form for geese as “g o:e o:e s e”. Thus the lexicon will look only slightly more complex munotes.in

Page 49

49 Word Level Analysis - II reg-noun irreg -pl-noun irreg -sg-noun fox cat
dog g o:e o:e se
sheep
m o:i u:ǫ s:c e goose sheep
mouse
Figure 3.6.3 A fleshed-out English nominal inflection FST Tlex, expanded from Tnum by replacing the three arcs with individual word stems (only a few sample word stems are shown). The resulting transducer, shown in Fig 3.6.3 will map plural nouns into the stem plus the morphological marker +Pl, and singular nouns into the stem plus the morphological marker +Sg. Thus surface cats will map to cat +N +Pl. This can be viewed in feasible-pair format as follows: c:c a:a t:t +N:ǫ +Pl:ˆs# Since the output symbols include the morpheme and word boundary markers ˆ and #, the lower labels do not correspond exactly to the surface level. Hence we refer to tapes with these morpheme boundary markers in Fig. 3.6.4 as intermediate tapes; the next section will show how the boundary marker is removed.
Figure 3.6.4 A schematic view of the lexical and intermediate tapes 3.7 LEXICON FREE FST PORTER STEMMER While building a transducer from a lexicon plus rules is the standard algorithm for morphological parsing, there are simpler algorithms that don’t require the large on-line lexicon demanded by this algorithm. These are used especially in Information Retrieval (IR) tasks like web search (a munotes.in

Page 50

50 Natural Language Processing
50 user needs some information, and is looking for relevant documents) User gives the system a query with some important characteristics of documents she desires, and the IR system retrieves what it thinks are the relevant documents. Morphological information in IR is thus only used to determine that two words have the same stem; the suffixes are thrown away. One of the most widely used such stemming algorithms are the simple and efficient Porter (1980) algorithm, which is based on a series of simple cascaded rewrite rules. Since cascaded rewrite rules are just the sort of thing that could be easily implemented as an FST, we think of the Porter algorithm as a lexicon-free FST stemmer. The algorithm contains rules like these: ATIONAL → ATE (e.g., relational → relate) ING → ǫ if stem contains vowel (e.g., motoring → motor) Do stemmers really improve the performance of information retrieval, especially with smaller documents? Nonetheless, not all IR engines use stemming, partly because of stemmer errors. Following kinds of errors of omission and commission in the Porter algorithm: Errors of Commission Errors of Omission Organization- organ European- Europe doing - doe analysis- analyzes generalization- generic matrices- matrix numerical- numerous noise- noisy policy- police sparse- sparsity university- universe explain- explanation 3.8 N-GRAMS N-gram is simply a sequence of N words. For instance, a 2-gram (or bigram) is a two-word sequence of words like “please turn”, “turn your”, or ”your homework”, and a 3-gram (or trigram) is a three-word sequence of words like “please turn your”, or “turn your homework.” In Natural Language Processing, n-grams are used for a variety of things. Some examples include like Auto completion of sentences, Auto spell check, Speech recognition and Machine translation. How do N-grams work? Let us take a look at the following examples. • San Francisco (is a 2-gram) • The Three Musketeers (is a 3-gram) • She stood up slowly (is a 4-gram) munotes.in

Page 51

51 Word Level Analysis - II Now which of these three N-grams have you seen quite frequently? Probably, “San Francisco” and “The Three Musketeers”. On the other hand, you might not have seen “She stood up slowly” that frequently. Basically, “She stood up slowly” is an example of an N-gram that does not occur as often in sentences as Examples 1 and 2. Now if we assign a probability to the occurrence of an N-gram or the probability of a word occurring next in a sequence of words, it can be very useful. Why? First of all, it can help in deciding which N-grams can be chunked together to form single entities (like “San Francisco” chunked together as one word, “high school” being chunked as one word). It can also help make next word predictions. Say you have the partial sentence “Please hand over your”. Then it is more likely that the next word is going to be “test” or “assignment” or “paper” than the next word being “school”. It can also help to make spelling error corrections. For instance, the sentence “drink cofee” could be corrected to “drink coffee” if you knew that the word “coffee” had a high probability of occurrence after the word “drink” and also the overlap of letters between “cofee” and “coffee” is high. 3.9 N –GRAM LANGUAGE MODEL An N-gram model is a type of Language Model (LM), that focuses on finding the probability distribution over word sequences. The model is built by counting how often word sequences occur in corpus text and then estimating the probabilities. Due to the fact that a simple N-gram model has limitations, improvements are often made through the means of smoothing, interpolation and backoff. A model that just focuses on how frequently a word occurs without looking at previous words is called unigram. If a model only considers just the previous word to predict the current word, then that model is called a bigram. When there is a sequence of N-1 words, an N-gram model is used to predict the most probable word that would follow that sequence. The N-gram model is a probabilistic model that is trained on a corpus of text. Formal grammars (e.g. regular, context free) give a hard “binary” model of the legal sentences in a language. For NLP, a probabilistic model of a language that gives a probability that a string is a member of a language is more useful. To specify a correct probability distribution, the probability of all sentences in a language must sum to 1. A language model also supports predicting the completion of a sentence. • Please turn off your cell______________. • Your program does not ______________. munotes.in

Page 52

52 Natural Language Processing
52 Predictive text input systems can guess what you are typing and give choices on how to complete it. Here N-Gram Models ,Estimate probability of each word given prior context. • P (phone | Please turn off your cell) Number of parameters required grows exponentially with the number of words of prior context. An N-gram model uses only N-1 words of prior context. • Unigram: P(phone) • Bigram: P(phone | cell) • Trigram: P(phone | your cell) The Markov assumption is the presumption that the future behaviour of a dynamical system only depends on its recent history. In particular, in a kth-order Markov model, the next state only depends on the k most recent states, therefore an N-gram model is a (N-1)-order Markov model. N-Gram Model Formulas Word sequences
Chain rule of probability
Bigram approximation
N-gram approximation
Estimating Probabilities N-gram conditional probabilities can be estimated from raw text based on the relative frequency of word sequences.
munotes.in

Page 53

53 Word Level Analysis - II Bigram:
N-gram:
• To have a consistent probabilistic model, append a unique start () and end () symbol to every sentence and treat these as additional words. • An N-gram model can be seen as a probabilistic automata for generating sentences. Initialize sentence with N-1 symbols Until is generated do: Stochastically pick the next word based on the conditional probability of each word given the previous N -1 words. Example: Let’s work through an example using a mini-corpus of three sentences I am Sam Sam I am I do not like green eggs and ham In general, we can say that this probability is (the number of times the previous word ‘wp’ occurs before the word ‘wn’) / (the total number of times the previous word ‘wp’ occurs in the corpus) = (Count (wp wn))/(Count (wp)) To find the probability of the word “I” following the word “”,we can write this as P (I | ) which is a conditional probability. This becomes equal to: = (No. of times “I” occurs) / (No. of times “” occurs) = 2/3 =0.67 Here are the calculations for some of the bigram probabilities from this corpus P (Sam | ) = 1/ 3 = 0.33 P (am | I) =2/3=0.67 P ( | Sam )=1/2 = 0.5 P (Sam | am =1/2 = 0.5 P (do | I) =1/3 = 0.33 munotes.in