NATURAL LANGUAGE PROCESSING

This notebook covers chapters 22 and 23 from the book Artificial Intelligence: A Modern Approach, 3rd Edition. The implementations of the algorithms can be found in nlp.py.

Run the below cell to import the code from the module and get started!

CONTENTS

• Overview
• Languages
• HITS
• Question Answering
• CYK Parse
• Chart Parsing

OVERVIEW

Natural Language Processing (NLP) is a field of AI concerned with understanding, analyzing and using natural languages. This field is considered a difficult yet intriguing field of study, since it is connected to how humans and their languages work.

Applications of the field include translation, speech recognition, topic segmentation, information extraction and retrieval, and a lot more.

Below we take a look at some algorithms in the field. Before we get right into it though, we will take a look at a very useful form of language, context-free languages. Even though they are a bit restrictive, they have been used a lot in research in natural language processing.

LANGUAGES

Languages can be represented by a set of grammar rules over a lexicon of words. Different languages can be represented by different types of grammar, but in Natural Language Processing we are mainly interested in context-free grammars.

Context-Free Grammars

A lot of natural and programming languages can be represented by a Context-Free Grammar (CFG). A CFG is a grammar that has a single non-terminal symbol on the left-hand side. That means a non-terminal can be replaced by the right-hand side of the rule regardless of context. An example of a CFG:

S -> aSb | ε

That means S can be replaced by either aSb or ε (with ε we denote the empty string). The lexicon of the language is comprised of the terminals a and b, while with S we denote the non-terminal symbol. In general, non-terminals are capitalized while terminals are not, and we usually name the starting non-terminal S. The language generated by the above grammar is the language aⁿbⁿ for n greater or equal than 1.

Probabilistic Context-Free Grammar

While a simple CFG can be very useful, we might want to know the chance of each rule occurring. Above, we do not know if S is more likely to be replaced by aSb or ε. Probabilistic Context-Free Grammars (PCFG) are built to fill exactly that need. Each rule has a probability, given in brackets, and the probabilities of a rule sum up to 1:

S -> aSb [0.7] | ε [0.3]

Now we know it is more likely for S to be replaced by aSb than by ε.

An issue with PCFGs is how we will assign the various probabilities to the rules. We could use our knowledge as humans to assign the probabilities, but that is a laborious and prone to error task. Instead, we can learn the probabilities from data. Data is categorized as labeled (with correctly parsed sentences, usually called a treebank) or unlabeled (given only lexical and syntactic category names).

With labeled data, we can simply count the occurrences. For the above grammar, if we have 100 S rules and 30 of them are of the form S -> ε, we assign a probability of 0.3 to the transformation.

With unlabeled data we have to learn both the grammar rules and the probability of each rule. We can go with many approaches, one of them the inside-outside algorithm. It uses a dynamic programming approach, that first finds the probability of a substring being generated by each rule, and then estimates the probability of each rule.

Chomsky Normal Form

A grammar is in Chomsky Normal Form (or CNF, not to be confused with Conjunctive Normal Form) if its rules are one of the three:

• X -> Y Z
• A -> a
• S -> ε

Where X, Y, Z, A are non-terminals, a is a terminal, ε is the empty string and S is the start symbol (the start symbol should not be appearing on the right hand side of rules). Note that there can be multiple rules for each left hand side non-terminal, as long they follow the above. For example, a rule for X might be: X -> Y Z | A B | a | b.

Of course, we can also have a CNF with probabilities.

This type of grammar may seem restrictive, but it can be proven that any context-free grammar can be converted to CNF.

Lexicon

The lexicon of a language is defined as a list of allowable words. These words are grouped into the usual classes: verbs, nouns, adjectives, adverbs, pronouns, names, articles, prepositions and conjunctions. For the first five classes it is impossible to list all words, since words are continuously being added in the classes. Recently "google" was added to the list of verbs, and words like that will continue to pop up and get added to the lists. For that reason, these first five categories are called open classes. The rest of the categories have much fewer words and much less development. While words like "thou" were commonly used in the past but have declined almost completely in usage, most changes take many decades or centuries to manifest, so we can safely assume the categories will remain static for the foreseeable future. Thus, these categories are called closed classes.

An example lexicon for a PCFG (note that other classes can also be used according to the language, like digits, or RelPro for relative pronoun):

Verb -> is [0.3] | say [0.1] | are [0.1] | ...
Noun -> robot [0.1] | sheep [0.05] | fence [0.05] | ...
Adjective -> good [0.1] | new [0.1] | sad [0.05] | ...
Adverb -> here [0.1] | lightly [0.05] | now [0.05] | ...
Pronoun -> me [0.1] | you [0.1] | he [0.05] | ...
RelPro -> that [0.4] | who [0.2] | which [0.2] | ...
Name -> john [0.05] | mary [0.05] | peter [0.01] | ...
Article -> the [0.35] | a [0.25] | an [0.025] | ...
Preposition -> to [0.25] | in [0.2] | at [0.1] | ...
Conjunction -> and [0.5] | or [0.2] | but [0.2] | ...
Digit -> 1 [0.3] | 2 [0.2] | 0 [0.2] | ...

Grammar

With grammars we combine words from the lexicon into valid phrases. A grammar is comprised of grammar rules. Each rule transforms the left-hand side of the rule into the right-hand side. For example, A -> B means that A transforms into B. Let's build a grammar for the language we started building with the lexicon. We will use a PCFG.

S -> NP VP [0.9] | S Conjunction S [0.1]

NP -> Pronoun [0.3] | Name [0.1] | Noun [0.1] | Article Noun [0.25] |
      Article Adjs Noun [0.05] | Digit [0.05] | NP PP [0.1] |
      NP RelClause [0.05]

VP -> Verb [0.4] | VP NP [0.35] | VP Adjective [0.05] | VP PP [0.1]
      VP Adverb [0.1]

Adjs -> Adjective [0.8] | Adjective Adjs [0.2]

PP -> Preposition NP [1.0]

RelClause -> RelPro VP [1.0]

Some valid phrases the grammar produces: "mary is sad", "you are a robot" and "she likes mary and a good fence".

What if we wanted to check if the phrase "mary is sad" is actually a valid sentence? We can use a parse tree to constructively prove that a string of words is a valid phrase in the given language and even calculate the probability of the generation of the sentence.

The probability of the whole tree can be calculated by multiplying the probabilities of each individual rule transormation: 0.9 * 0.1 * 0.05 * 0.05 * 0.4 * 0.05 * 0.3 = 0.00000135.

To conserve space, we can also write the tree in linear form:

[S [NP [Name mary]] [VP [VP [Verb is]] [Adjective sad]]]

Unfortunately, the current grammar overgenerates, that is, it creates sentences that are not grammatically correct (according to the English language), like "the fence are john which say". It also undergenerates, which means there are valid sentences it does not generate, like "he believes mary is sad".

Implementation

In the module we have implementation both for probabilistic and non-probabilistic grammars. Both these implementation follow the same format. There are functions for the lexicon and the rules which can be combined to create a grammar object.

Non-Probabilistic

Execute the cell below to view the implemenations:

Let's build a lexicon and a grammar for the above language:

Both the functions return a dictionary with keys the left-hand side of the rules. For the lexicon, the values are the terminals for each left-hand side non-terminal, while for the rules the values are the right-hand sides as lists.

We can now use the variables lexicon and rules to build a grammar. After we've done so, we can find the transformations of a non-terminal (the Noun, Verb and the other basic classes do not count as proper non-terminals in the implementation). We can also check if a word is in a particular class.

If the grammar is in Chomsky Normal Form, we can call the class function cnf_rules to get all the rules in the form of (X, Y, Z) for each X -> Y Z rule. Since the above grammar is not in CNF though, we have to create a new one.

Finally, we can generate random phrases using our grammar. Most of them will be complete gibberish, falling under the overgenerated phrases of the grammar. That goes to show that in the grammar the valid phrases are much fewer than the overgenerated ones.

Probabilistic

The probabilistic grammars follow the same approach. They take as input a string, are assembled from a grammar and a lexicon and can generate random sentences (giving the probability of the sentence). The main difference is that in the lexicon we have tuples (terminal, probability) instead of strings and for the rules we have a list of tuples (list of non-terminals, probability) instead of list of lists of non-terminals.

Execute the cells to read the code:

Let's build a lexicon and rules for the probabilistic grammar:

Let's use the above to assemble our probabilistic grammar and run some simple queries:

If we have a grammar in CNF, we can get a list of all the rules. Let's create a grammar in the form and print the CNF rules:

Lastly, we can generate random sentences from this grammar. The function prob_generation returns a tuple (sentence, probability).

As with the non-probabilistic grammars, this one mostly overgenerates. You can also see that the probability is very, very low, which means there are a ton of generateable sentences (in this case infinite, since we have recursion; notice how VP can produce another VP, for example).

HITS

Overview

Hyperlink-Induced Topic Search (or HITS for short) is an algorithm for information retrieval and page ranking. You can read more on information retrieval in the text notebook. Essentially, given a collection of documents and a user's query, such systems return to the user the documents most relevant to what the user needs. The HITS algorithm differs from a lot of other similar ranking algorithms (like Google's Pagerank) as the page ratings in this algorithm are dependent on the given query. This means that for each new query the result pages must be computed anew. This cost might be prohibitive for many modern search engines, so a lot steer away from this approach.

HITS first finds a list of relevant pages to the query and then adds pages that link to or are linked from these pages. Once the set is built, we define two values for each page. Authority on the query, the degree of pages from the relevant set linking to it and hub of the query, the degree that it points to authoritative pages in the set. Since we do not want to simply count the number of links from a page to other pages, but we also want to take into account the quality of the linked pages, we update the hub and authority values of a page in the following manner, until convergence:

• Hub score = The sum of the authority scores of the pages it links to.

• Authority score = The sum of hub scores of the pages it is linked from.

So the higher quality the pages a page is linked to and from, the higher its scores.

We then normalize the scores by dividing each score by the sum of the squares of the respective scores of all pages. When the values converge, we return the top-valued pages. Note that because we normalize the values, the algorithm is guaranteed to converge.

Implementation

The source code for the algorithm is given below:

First we compile the collection of pages as mentioned above. Then, we initialize the authority and hub scores for each page and finally we update and normalize the values until convergence.

A quick overview of the helper functions functions we use:

• relevant_pages: Returns relevant pages from pagesIndex given a query.

• expand_pages: Adds to the collection pages linked to and from the given pages.

• normalize: Normalizes authority and hub scores.

• ConvergenceDetector: A class that checks for convergence, by keeping a history of the pages' scores and checking if they change or not.

• Page: The template for pages. Stores the address, authority/hub scores and in-links/out-links.

Example

Before we begin we need to define a list of sample pages to work on. The pages are pA, pB and so on and their text is given by testHTML and testHTML2. The Page class takes as arguments the in-links and out-links as lists. For page "A", the in-links are "B", "C" and "E" while the sole out-link is "D".

We also need to set the nlp global variables pageDict, pagesIndex and pagesContent.

We can now run the HITS algorithm. Our query will be 'mammals' (note that while the content of the HTML doesn't matter, it should include the query words or else no page will be picked at the first step).

Let's see how the pages were scored:

The top score is 0.82 by "C". This is the most relevant page according to the algorithm. You can see that the pages it links to, "A" and "D", have the two highest authority scores (therefore "C" has a high hub score) and the pages it is linked from, "B" and "E", have the highest hub scores (so "C" has a high authority score). By combining these two facts, we get that "C" is the most relevant page. It is worth noting that it does not matter if the given page contains the query words, just that it links and is linked from high-quality pages.

QUESTION ANSWERING

Question Answering is a type of Information Retrieval system, where we have a question instead of a query and instead of relevant documents we want the computer to return a short sentence, phrase or word that answers our question. To better understand the concept of question answering systems, you can first read the "Text Models" and "Information Retrieval" section from the text notebook.

A typical example of such a system is AskMSR (Banko et al., 2002), a system for question answering that performed admirably against more sophisticated algorithms. The basic idea behind it is that a lot of questions have already been answered in the web numerous times. The system doesn't know a lot about verbs, or concepts or even what a noun is. It knows about 15 different types of questions and how they can be written as queries. It can rewrite [Who was George Washington's second in command?] as the query [* was George Washington's second in command] or [George Washington's second in command was *].

After rewriting the questions, it issues these queries and retrieves the short text around the query terms. It then breaks the result into 1, 2 or 3-grams. Filters are also applied to increase the chances of a correct answer. If the query starts with "who", we filter for names, if it starts with "how many" we filter for numbers and so on. We can also filter out the words appearing in the query. For the above query, the answer "George Washington" is wrong, even though it is quite possible the 2-gram would appear a lot around the query terms.

Finally, the different results are weighted by the generality of the queries. The result from the general boolean query [George Washington OR second in command] weighs less that the more specific query [George Washington's second in command was *]. As an answer we return the most highly-ranked n-gram.

CYK PARSE

Overview

Syntactic analysis (or parsing) of a sentence is the process of uncovering the phrase structure of the sentence according to the rules of a grammar. There are two main approaches to parsing. Top-down, start with the starting symbol and build a parse tree with the given words as its leaves, and bottom-up, where we start from the given words and build a tree that has the starting symbol as its root. Both approaches involve "guessing" ahead, so it is very possible it will take long to parse a sentence (wrong guess mean a lot of backtracking). Thankfully, a lot of effort is spent in analyzing already analyzed substrings, so we can follow a dynamic programming approach to store and reuse these parses instead of recomputing them. The CYK Parsing Algorithm (named after its inventors, Cocke, Younger and Kasami) utilizes this technique to parse sentences of a grammar in Chomsky Normal Form.

The CYK algorithm returns an M x N x N array (named P), where N is the number of words in the sentence and M the number of non-terminal symbols in the grammar. Each element in this array shows the probability of a substring being transformed from a particular non-terminal. To find the most probable parse of the sentence, a search in the resulting array is required. Search heuristic algorithms work well in this space, and we can derive the heuristics from the properties of the grammar.

The algorithm in short works like this: There is an external loop that determines the length of the substring. Then the algorithm loops through the words in the sentence. For each word, it again loops through all the words to its right up to the first-loop length. The substring it will work on in this iteration is the words from the second-loop word with first-loop length. Finally, it loops through all the rules in the grammar and updates the substring's probability for each right-hand side non-terminal.

Implementation

The implementation takes as input a list of words and a probabilistic grammar (from the ProbGrammar class detailed above) in CNF and returns the table/dictionary P. An item's key in P is a tuple in the form (Non-terminal, start of substring, length of substring), and the value is a probability. For example, for the sentence "the monkey is dancing" and the substring "the monkey" an item can be ('NP', 0, 2): 0.5, which means the first two words (the substring from index 0 and length 2) have a 0.5 probablity of coming from the NP terminal.

Before we continue, you can take a look at the source code by running the cell below:

When updating the probability of a substring, we pick the max of its current one and the probability of the substring broken into two parts: one from the second-loop word with third-loop length, and the other from the first part's end to the remainer of the first-loop length.

Example

Let's build a probabilistic grammar in CNF:

Now let's see the probabilities table for the sentence "the robot is good":

A defaultdict object is returned (defaultdict is basically a dictionary but with a default value/type). Keys are tuples in the form mentioned above and the values are the corresponding probabilities. Most of the items/parses have a probability of 0. Let's filter those out to take a better look at the parses that matter.

The item ('Article', 0, 1): 0.5 means that the first item came from the Article non-terminal with a chance of 0.5. A more complicated item, one with two words, is ('NP', 0, 2): 0.12 which covers the first two words. The probability of the substring "the robot" coming from the NP non-terminal is 0.12. Let's try and follow the transformations from NP to the given words (top-down) to make sure this is indeed the case:

1. The probability of NP transforming to Article Noun is 0.6.

2. The probability of Article transforming to "the" is 0.5 (total probability = 0.6*0.5 = 0.3).

3. The probability of Noun transforming to "robot" is 0.4 (total = 0.3*0.4 = 0.12).

Thus, the total probability of the transformation is 0.12.

Notice how the probability for the whole string (given by the key ('S', 0, 4)) is 0.015. This means the most probable parsing of the sentence has a probability of 0.015.

CHART PARSING

Overview

Let's now take a look at a more general chart parsing algorithm. Given a non-probabilistic grammar and a sentence, this algorithm builds a parse tree in a top-down manner, with the words of the sentence as the leaves. It works with a dynamic programming approach, building a chart to store parses for substrings so that it doesn't have to analyze them again (just like the CYK algorithm). Each non-terminal, starting from S, gets replaced by its right-hand side rules in the chart, until we end up with the correct parses.

Implementation

A parse is in the form [start, end, non-terminal, sub-tree, expected-transformation], where sub-tree is a tree with the corresponding non-terminal as its root and expected-transformation is a right-hand side rule of the non-terminal.

The chart parsing is implemented in a class, Chart. It is initialized with a grammar and can return the list of all the parses of a sentence with the parses function.

The chart is a list of lists. The lists correspond to the lengths of substrings (including the empty string), from start to finish. When we say 'a point in the chart', we refer to a list of a certain length.

A quick rundown of the class functions:

• parses: Returns a list of parses for a given sentence. If the sentence can't be parsed, it will return an empty list. Initializes the process by calling parse from the starting symbol.

• parse: Parses the list of words and builds the chart.

• add_edge: Adds another edge to the chart at a given point. Also, examines whether the edge extends or predicts another edge. If the edge itself is not expecting a transformation, it will extend other edges and it will predict edges otherwise.

• scanner: Given a word and a point in the chart, it extends edges that were expecting a transformation that can result in the given word. For example, if the word 'the' is an 'Article' and we are examining two edges at a chart's point, with one expecting an 'Article' and the other a 'Verb', the first one will be extended while the second one will not.

• predictor: If an edge can't extend other edges (because it is expecting a transformation itself), we will add to the chart rules/transformations that can help extend the edge. The new edges come from the right-hand side of the expected transformation's rules. For example, if an edge is expecting the transformation 'Adjective Noun', we will add to the chart an edge for each right-hand side rule of the non-terminal 'Adjective'.

• extender: Extends edges given an edge (called E). If E's non-terminal is the same as the expected transformation of another edge (let's call it A), add to the chart a new edge with the non-terminal of A and the transformations of A minus the non-terminal that matched with E's non-terminal. For example, if an edge E has 'Article' as its non-terminal and is expecting no transformation, we need to see what edges it can extend. Let's examine the edge N. This expects a transformation of 'Noun Verb'. 'Noun' does not match with 'Article', so we move on. Another edge, A, expects a transformation of 'Article Noun' and has a non-terminal of 'NP'. We have a match! A new edge will be added with 'NP' as its non-terminal (the non-terminal of A) and 'Noun' as the expected transformation (the rest of the expected transformation of A).

You can view the source code by running the cell below:

Example

We will use the grammar E0 to parse the sentence "the stench is in 2 2".

First we need to build a Chart object:

And then we simply call the parses function:

You can see which edges get added by setting the optional initialization argument trace to true.

Let's try and parse a sentence that is not recognized by the grammar:

An empty list was returned.