Introduction

This module will provide an introduction to methods for analyzing text. Text analytics is a complicated topic, covering a wide range of problems and solutions. For example, consider the following simple questions. How should text data be structured? What types of analysis are appropriate for text data? How can these analyses be performed? How should results from text analytics be presented to a viewer?

We will focus on simple approaches to address each of these questions. In particular, we will discuss different ways to represent text, and present the use of term frequency to structure a document's text. We will then present algorithms that use this approach to measure the similarity between text, to cluster text into topics, to estimate the sentiment in text, and to present text and text analytics results to a viewer.

Why Text Analytics?

Much of the data now being captured and stored is semi-structured or unstructured: it is not being saved in a structured format, for example, in a database or data repository with a formal framework. Text data often makes up a large part of these unstructured collections: email, web pages, news articles, books, social network postings, and so on. Text analytics and text mining are meant to be applied to this type of data to

where interesting means non-trivial, hidden, previously unknown, and potentially useful.

Text analytics has many potential applications. These can be discovery driven, where we try to answer specific questions through text mining, or data driven, where we take a large collection of text data and try to derive useful information by analyzing it.

There are many reasons why analyzing text is difficult.

• Abstract. The concepts contained in text are often difficult to identify and represent (e.g., sentiment or sarcasm, "I loved the way you put that. No, really, I LOVED it.")
• Relationships. Subtle, complex relationships between concepts must be extracted (e.g., negation, "I thought I'd enjoy that movie, but in the end it just didn't work out the way I expected.")
• Scale. A document can contain many thousands of words, and a document collection can contain thousands or hundreds of thousands of documents.

Each homework group will complete a text analytics assignment. This involves choosing a problem of interest to address, identifying and collecting appropriate text data to support the problem, then using text analysis techniques discussed during this module to analyze your data and form conclusions and results that will be presented in class.

Sept. 27, 11:59pm

Submit a draft proposal via the Moodle section on Text Mining (Text Mining Project Proposal Submission) that describes the problem you will investigate. As taught in communications, the proposal must be a Word document so we can return comments through change tracking. The proposal must include the following items.

• A problem statement explaining the issue you want to study and the goals you plan to achieve.
• A description of the dataset(s) you will use, detailing either where the data is available, or how it will be collected. Provide enough specificity for us to confirm that the data will be available in a timely manner.
• A description of the types of analysis you plan to apply to your datasets to achieve the goals listed in your problem statement.
• A detailed justification of why the data you plan to collect will support the problem and analysis you propose to complete. Projects that we do not feel have a high probability of success will be returned and will need to be improved or replaced with a different proposal.
• A list of the results you will present at the end of your analysis.

The draft proposal should be approximately one page in length. We have provided an example draft proposal to give you an idea of its length, content, and format.

Oct. 2, 11:59pm

Submit a revised proposal through the Moodle section on Text Mining (Text Mining Project Revised Submission) that addresses comments and/or concerns made by the instructors on your draft proposal. The revised proposal represents a template for what we expect to see during your final presentation.

Oct. 17, 9:00am–12:00pm (blue), 1:00pm–4:00pm (orange)

Present your project and its results to the class. Each group will be allotted 10 minutes: 8 minutes to present, and 2 minutes to answer one or two questions. Because of our tight schedule, each group must provide their slides to Andrea by 5pm on Oct. 16 through the Moodle section on Text Mining (Text Mining Project Submission). This will allow us to review the presentations ahead of time. During presentations, groups will screen share their slides, so you are expected to be prepared and ready to being presenting immediately when your group is scheduled. Each group will be strictly limited to 10 minutes for their presentations (i.e., 4–5 slides for the average presentation). Please plan your presentations accordingly. For example, consider having only 1 or 2 groups members present your slides, then have the entire team available for questions at the end.

You must attend all of the presentations for your cohort. Attending presentations for the opposite cohort is optional, but certainly encouraged if you want to see the work they did.

NLTK, Gensim, and Scikit-Learn

Throughout this module we will provide code examples in Python using the Natural Language Toolkit (NLTK). NLTK is designed to support natural language processing and analysis of human language data. It includes the ability to perform many different language processing operations, including all of the text analytics techniques we will be discussing.

For techniques beyond the scope of NLTK, we will provide Python examples that use Gensim, a more sophisticated text analysis package that includes the text similarity algorithms we will discuss during the module. We will also discuss the text analytics preprocessing capabilities built into scikit-learn, and the full NLP package spaCy.

spaCy

Since spaCy is a much more complicated Python package, we will offer a brief overview here. spaCy implements a convolution neural net (CNN)-trained set of statistical models and processing pipelines to support common natural language processing (NLP) tasks including tokenization, part-of-speech tagging, named entity recognition, lemmatization, and support for many different languages. spaCy is kept up-to-date through regular updates and improvements to its code base.

Don't worry if terms like "part-of-speech tagging" or "lemmatization" are unfamiliar. All of these will be covered in detail during this module, including code examples in both spaCy and other Python packages.

In order to install spaCy in your Anacoda environment, executed the Anacode Prompt and enter the following at the command line.

Although the above command installs the spaCy package into your Anaconda environment, spaCy's strength comes from a set of pre-trained CNN models. Each model is pre-loaded manually from the Anaconda Prompt to make it available to spaCy. These are the pre-trained English language models spaCy provides, along with a brief description of what their makeup and intended purpose is.

In order to pre-load a spaCy trained model into your Anaconda environment, execute the following command from the Anaconda Prompt with the name of the library provided. For example, to pre-load the en_core_web_sm, en_core_web_md, and en_core_web_lg models, you would execute the following command. Note, spacy must already be installed for these commands to work.

Once the required model is downloaded, it can be loaded with spaCy's load() command.

Alternatively, you can import a spaCy model directly in your Python code. The model still needs to be downloaded before it can be imported.

In both cases, spaCy uses its NLP pipeline to convert the text you provide into a wide range of text properties. The standard pipeline runs in the following fashion.

• tokenizer: converts text into words and punctuation tokens,
• tagger: performs part-of-speech tagging,
• parser: performs dependency parsing to find the structure and relationships between words in a sentence,
• NER: performs named entity recognition,
• attribute ruler: performs any user-assigned rules (e.g.word/phrase token matching), and
• lemmatizer: performs lemmatization to convert terms to a common base form.

All of the various properties spaCy identifies are available in the doc object. For example, the following simple code snippet performs NER and returns the entities and the spaCy estimation of what they represent.

You can view spaCy as a high-level NLP engine, capable of completing all of the preprocessing steps in preparation for follow-on analysis in a single nlp() call. Preprocessing is performed based in large part on the pre-trained models spaCy encapsulates. The advantage, of course, is that this significantly reduces the effort needed to get to an analysis point in your programming. The potential disadvantage is that, although spaCy allows control of the steps it performs, these may not provide the fine-grained control needed, and even when it does, it may be just as much work to tune spaCy versus performing the individual steps manually. Still, spaCy is a high quality and commonly used option in the text analytics area.

Text Representations

There are many different ways to represent text. We describe some of the most common approaches, discussing briefly their advantages and disadvantages.

Character

The simplest representation views text as an ordered collection of characters. A text document is described by the frequency of sequences of characters of different lengths. For example, consider the following text data.

This could be represented by a set of single character frequencies fq (1-grams), a set of two-character frequencies (2-grams), and so on.

Character representations have the advantage of being simple and fairly unambiguous, since they avoid many common language issues (homonyms, synonyms, etc.) They also allow us to compress large amounts of text into a relative compact representation. Unfortunately, character representations provide almost no access to the semantic properties of text data, making them a poor representation for analyzing meaning in the data.

Word

A very common representation of text is to convert a document into individual words or terms. Our example sentence represented as words would look something like this.

Words strike a good balance between simplicity and semantics. At this level various ambiguities begin to arise, however.

• Homonym. Words with identical form but different meaning (e.g., lie: to recline versus lie: not telling the truth; or bass: a musical instrument versus bass: a fish).
• Synonym. Words with different form but the same or similar meaning (e.g., ambiguous, confusing, opaque, uncertain, unclear, vague).
• Polysemy. Words with the same form and multiple related meanings (e.g., bank: a financial institution and bank: to rely upon, as in "You can bank on me").
• Hyponym. Words that are a semantic subclass of another word, forming a type-of relationship (e.g. salmon is a hyponym of fish).

It's also the case that some words may be more useful than others, due to their commonality. Suppose we're trying to determine the similarity between the text of two documents that discuss the financial crisis. Would comparing the frequency of the word like "an" be as useful as comparing the frequency of a word like "investment" or "collapse"?

Phrase

Combining words together forms phrases, which are often called n-grams when n words are combined. Phrases may be contiguous, "Mary switches her table lamp off" ⇒ "table lamp off", or non-contiguous, "Mary switches her table lamp off" ⇒ { lamp, off, switches }. An important advantage of phrase representations is that they often give a better meaning to the semantics of sense of the individual words in a phrase (e.g., "lie down" versus "lie shamelessly").

Google has published a number of online applications and datasets related to n-grams. One example is the Ngram Viewer which allows you to compare the occurrence of n-grams in books Google has indexed over a range of years. The Ngram Viewer allows not only explicit phrase searches, but also searches that include wildcards, inflection, or part-of-speech. They have also made their underlying n-gram datasets available to interested researchers.

Part of Speech

Words can be further enriched by performing part-of-speech tagging. Common parts of speech in English include nouns, verbs, adjectives, adverbs, and so on. Part-of-speech tagging is often used to filter a document, allowing us to restrict analysis to "information rich" parts of the text like nouns and verbs or noun phrases. The Cognitive Computation Group at UIUC provides a comprehensive part-of-speech tagger as a web-based application.

WordNet

WordNet is a lexical database of English words. In its simplest form, WordNet contains four databases of nouns, verbs, adjectives, and adverbs. Like a thesaurus, WordNet groups synonymous words into synsets, sets of words with similar meanings. Unlike a thesaurus, however, WordNet forms conceptual relations between synsets based on semantics. For example, for the noun database the following relations are defined.

WordNet also includes general to specific troponym relations between verbs: communicate–talk–whisper, move–jog–run, or like–love–idolize; and antonym relations between verbs and adjectives: wet–dry, young–old or like–hate. Finally, WordNet provides a brief explanation (or gloss) and example sentences for each of its synsets.

WordNet is extremely useful for performing tasks like part-of-speech tagging or word disambiguation. WordNet's databases can be searched through an online web application. The databases can also be downloaded for use by researchers and practitioners.

Text Representation Analytics

Dr. Peter Norvig, a leading artificial intelligence researcher and Director of Research at Google, recently complied a set of statistics about character, n-gram, and word frequencies based on the Google Books archive. His results showed some interesting similarities and differences to the seminal work of Mark Mayzner, who studied the original frequency of letters in the English language in the 1960s. The video below provides an interesting overview of Dr. Norvig's findings.

Practice Problem 1

Take the following except from John Steinbeck's famous novel, Of Mice and Men.

Convert this text into four separate text representations:

• character
• term
• bigram, pairs of adjacent terms
• term with appropriate part-of-speech disambiguation

You can use Python's nltk or spaCy libraries to assign part-of-speech tags to terms in a term list.

The various part-of-speech tags like CC (coordinating conjunction), RB (adverb), and ADP (adposition) are part of the Penn Treebank part-of-speech tag list for numpy and the Universal POS tag list for spaCy, both of which are available online.

Term Vectors

As discussed above, perhaps the most common method of representing text is by individual words or terms. Syntactically, this approach converts the text in document D into a term vector D_j. Each entry in D_j corresponds to a specific term t_i, and its value defines the frequency of t_i ∈ D_j. Other possible approaches include language modelling, which tries to predict the probabilities of specific sequences of terms, and natural language processing (NLP), which converts text into parse trees that include parts of speech and a hierarchical breakdown of phrases and sentences based on rules of grammar. Although useful for a variety of tasks (e.g., optical character recognition, spell checking, or language understanding), language modelling and NLP are normally too specific or too complex for our purposes.

As an example of term vectors, suppose we had the following four documents.

Taking the union of the documents' unique terms, the documents produce the following term vectors.

Intuitively, the overlap between term vectors might provide some clues about the similarity between documents. In our example, there is no overlap between D₁ and D₂, but a three-term overlap between D₁ and D₃, and a one-term overlap between D₃ and D₄.

Stop Words

A common preprocessing step during text analytics is to remove stop words, words that are common in text but that do not provide any useful context or semantics. Removing stop words is simple, since it can be performed in a single pass over the text. There is no single, definitive stop word list. Here is one fairly extensive example.

Applying stop word removal to our initial four document example would significantly shorten their term vectors.

Notice that the overlap between D₁ and D₃, which was based on stop words, has vanished. The only remaining overlap is between D₃ and D₄.

As with all operations, removing stop words is normally appropriate, but not always. The classic example is the sentence "To be or not to be." Removing stop words eliminates the entire sentence, which could be problematic. Consider a search engine that performs stop word removal prior to search to improve performance. Searching on the sentence "To be or not to be." using this strategy would fail.

Stemming

Stemming removes suffixes from words, trimming them down to conflate them into a single, common term. For example, the terms

could be stemmed to a single term connect. There are a number of potential advantages to stemming terms in a document. The two most obvious are: (1) it reduces the total number of terms, improving efficiency, and (2) it better captures the content of a document by aggregating terms that are semantically similar.

Researchers in IR quickly realized it would be useful to develop automatic stemming algorithms. One of the first algorithms for English terms was published by Julie Beth Lovins in 1968 (Lovins, J. B. Development of a Stemming Algorithm, Mechanical Translation and Computational Linguistics 11, 1–2, 1968, 22–31.) Lovins's algorithm used 294 endings, 29 conditions, and 35 transformation rules to stem terms. Conditions and endings are paired to define when endings can be removed from terms. For example

Consider the term NATIONALLY. This term ends in ATIONALLY but condition B restricts its application to terms whose minimum stem length (after stemming) is 3 characters or longer, so it cannot be applied. The term also ends in IONALLY, however, and it satisfies condition A (no restriction on stem), so this ending can be removed, producing NAT.

Lovins's transformation rules handle issues like letter doubling (SITTING → SITT → SIT), odd pluralization (MATRIX as MATRICES), and other irregularities (ASSUME and ASSUMPTION).

The order that rules are applied is important. In Lovins's algorithm, the longest ending that satisfies its condition is found and applied. Next, each of the 35 transformation rules are tested in turn.

Lovins's algorithm is a good example of trading space for coverage and performance. The number of endings, conditions, and rules is fairly extensive, but many special cases are handled, and the algorithm runs in just two major steps: removing a suffix, and handling language-specific transformations.

Porter Stemming

Perhaps the most popular stemming algorithm was developed by Michael Porter in 1980 (Porter, M. F. An Algorithm for Suffix Stripping, Program 14, 3, 1980, 130–137.) Porter's algorithm attempted to improve on Lovins's in a number of ways. First, it is much simpler, containing many fewer endings and conditions. Second, unlike Lovins's approach of using stem length and the stem's ending character as a condition, Porter uses the number of consonant-vowel pairs that occur before the ending, to better represent syllables in a stem. The algorithm begins by defining consonants and vowels.

• Consonant. A letter other than A, E, I, O, U, or Y preceded by a consonant.
• Vowel. A letter than is not a consonant.

A sequence of consonants ccc... of length > 0 is denoted C. A list of vowels vvv... of length > 0 is denoted V. Therefore, any term has four forms: CVCV...C, CVCV...V, VCVC...C, or VCVC...V. Using square brackets [C] to denote arbitrary presence and parentheses (VC)^m to denote m repetitions, this can be simplified to

[C] (VC)^m [V]

m is the measure of the term. Here are some examples of different terms and their measures, denoted using Porter's definitions.

Once terms are converted into consonant–vowel descriptions, rules are defined by a conditional and a suffix transformation.

(condition) S1 → S2

The rule states that if a term ends in S1, and if the stem before S1 satisfies the condition, then S1 should be replaced by S2. The condition is often specified in terms of m.

(m > 1) EMENT →

This rule replaces a suffix EMENT with nothing if the remainder of the term has measure of 2 or greater. For example, REPLACEMENT would be stemmed to REPLAC, since REPLAC ⇒ [R] (E PL A C) [ ] with m = 2. PLACEMENT, on the other hand, would not be stemmed, since PLAC ⇒ [PL] (A C) [ ] has m = 1. Conditions can also contain more sophisticated requirements.

Conditions can also include boolean operators, for example, (m > 1 and (*S or *T)) for a stem with a measure of 2 or more that ends in S or T, or (*d and not (*L or *S or *Z)) for a stem that ends in a double consonant but does not end in L or S or Z.

Porter defines bundles of conditions that form eight rule sets. Each rule set is applied in order, and within a rule set the matching rule with the longest S1 is applied. The first three rules deal with plurals and past participles (a verb in the past tense, used to modify a noun or noun phrase). The next three rules reduce or strip suffixes. The final two rules clean up trailing characters on a term. Here are some examples from the first, second, fourth, and seventh rule sets.

This web site provides an online demonstration of text being stemmed using Porter's algorithm. Stemming our four document example produces the following result, with happy stemming to happi.

Practice Problem 2

Take the following three excepts from John Steinbeck's Of Mice and Men, William Golding's Lord of the Flies, and George Orwell's 1984, and use stop word removal and Porter stemming to produce a \(3 \times n\) term–frequency matrix.

Similarity

Once documents have been converted into term vectors, vectors can be compared to estimate the similarity between pairs or sets of documents. Many algorithms weight the vectors' term frequencies to better distinguish documents from one another, then use the cosine of the angle between a pair of document vectors to compute the documents' similarity.

Term Frequency–Inverse Document Frequency

A well known document similarity algorithm is term frequency–inverse document frequency, or TF-IDF (Salton, G. and Yang, C. S. On the Specification of Term Values in Automatic Indexing, Journal of Documentation 29, 4, 351–372, 1973). Here, individual terms in a document's term vector are weighted by their frequency in the document (the term frequency), and by their frequency over the entire document collection (the document frequency).

Consider an m×n matrix X representing m unique terms t_i as rows of X and n documents D_j as columns of X. The weight X[i, j] = w_i,j for t_i ∈ D_j is defined as w_i,j = tf_i,j × idf_i, where tf_i,j is the number of occurrences of t_i ∈ D_j, and idf_i is the log of inverse fraction of documents n_i that contain at least one occurrence of t_i, idf_i = ln( n / n_i ).

The left matrix below shows our four document example transposed to place the m=11 terms in rows and the n=4 documents in columns. The center matrix weights each term count using TF-IDF. The right matrix normalizes each document column, to remove the influence of document length from the TF-IDF weights.

Most of the weights in the center matrix's columns are 1.39. These correspond to single frequency occurrences of terms (tf_i,j = 1) that exist in only one document (idf_i = ln(4 / 1) = 1.39). Single frequency occurrences of dagger in D₃ and D₄ have weights of 0.69, because idf_dagger = ln(4 / 2) = 0.69. Finally, the weight for far in D₁ is 2.77 because its term frequency is tf_far,1 = 2.

Once documents are converted into normalized TF-IDF vectors, the similarity between two documents is the dot product of their vectors. In our example, the only documents that share a common term with a non-zero weight are D₃ and D₄. Their similarity is D₃ · D₄ = 0.44 × 0.33 = 0.15.

Mathematically, recall that cos θ = D_i · D_j / |D_i| |D_j|. Since the document vectors are normalized, this reduces to cos θ = D_i · D_j. Dot product similarity measures the cosine of the angle between two document vectors. The more similar the direction of the vectors, the more similar the documents.

Intuitively, TF-IDF implies the following. In any document D_j, if a term t_i occurs frequently, it's an important term for characterizing D_j. Moreover, if t_i does not occur in many other documents, it's an important term for distinguishing D_j from other documents. This is why t_i's weight in D_j increases based on term frequency and inverse document frequency. If two documents share terms with high term frequency and low document frequency, they are assumed to be similar. The dot product captures exactly this situation in its sum of the product of individual term weights.

Latent Semantic Analysis

Latent semantic analysis (LSA) reorganizes a set of documents using a semantic space derived from implicit structure contained in the text of the documents (Dumais, S. T., Furnas, G. W., Landauer, T. K., Deerwester, S. and Harshman, R. Using Latent Semantic Analysis to Improve Access to Textual Information, Proceedings of the Conference on Human Factors in Computing Systems (CHI '88), 281–286, 1988). LSA uses the same m×n term-by-document matrix X corresponding to m unique terms across n documents. Each frequency X[i, j] for term t_i in document D_j is normally weighted, for example, using TF-IDF.

Each row in X is a term vector t_i = [ x_i,1 ⋯ x_i,n ] defining the frequency of t_i in each document D_j. The dot product of two term vectors t_p · t_q^T defines a correlation between the distribution of the two terms across the documents. Similarly, the dot product D_p^T · D_q of two columns of X corresponding to the term frequencies for two documents defines a similarity between the documents.

Given X, we perform a singular value decomposition (SVD) to produce X = UΣV^T, where U and V are orthonormal matrices (a matrix whose rows and columns are unit length, and the dot product of any pair of rows or columns is 0) and Σ is a diagonal matrix. Mathematically, U contains the eigenvectors of XX^T (the t_p–t_q correlations), V contains the eigenvectors of X^TX (the D_p–D_q similarities), and ΣΣ^T contains the eigenvalues for U and V, which are identical. Mathematically, SVD can be seen as providing three related functions.

1. A method to transform correlated variables into uncorrelated variables that better expose relationships among the original data items.
2. A method to identify and order dimensions along which the data items exhibit the most variation.
3. A method to best approximate the data items with fewer dimensions.

To use SVD for text similarity, we first select the k largest singular values σ from Σ, together with their corresponding eigenvectors from U and V. This forms a rank-k approximation of X, X_k = U_kΣ_kV_k^T. The columns c_i of U_k represent concepts, linear combinations of the original terms. The columns D_j of V_k^T represent the documents defined based on which concepts (and how much of each concept) they contain. Consider the following example documents.

• D₁. Romeo and Juliet
• D₂. Juliet, O happy dagger!
• D₃. Romeo died by a dagger
• D₄. "Live free or die", that's the New Hampshire motto
• D₅. Did you know New Hampshire is in New England

We choose a subset of the terms in these documents, then construct an initial term–document matrix X.

Applying SVD to X_TF‑IDF produces the following decomposition.

We choose the k = 2 largest singular values, producing the following reduced matrices.

If we wanted to reconstruct a version of the original term–document matrix using our concepts from the rank-2 approximation, we would dot-product U₂ · Σ₂ · V₂^T to produce X₂ based on the largest k=2 singular values. We have also normalized the document columns to allow for dot product-based cosine similarity.

So what advantage does LSA provide over using a term–document matrix directly, as we do in TF-IDF? First, it hopefully provides some insight into why concepts might be more useful that independent terms. Consider the term frequencies contained in X versus X₂ for D₁. The original frequencies in X were 1 for romeo and juliet, and 0 for all other terms. The two largest LSA frequencies in X₂ are 0.56 for die and 0.57 for hampshire. Why is there a large positive frequency for die? LSA has inferred this connection based on the fact that D₃ associates die with romeo. On the other hand, hampshire has the largest contribution of 0.57. It is true that hampshire in D₄ associates with die, which associates with die in D₃, which associates with romeo in D₁, but this doesn't seem as strong the romeo–die relationship from D₃ directly. This highlights one issue with LSA, the inability to identify "intuitive" meanings for the concepts it extracts.

These associations affect document similarities. For example, in the original X the similarities between D₁–D₄ and D₁–D₅ are both 0. If you used the X₂ term–document matrix, however, the similarities are 0.06 and -0.15. The term die in D₄ associates to romeo, defining a similarity between D₁ and D₄. No such association exists between D₁ and D₅. Human readers with an understanding of the context of Romeo and Juliet would likely identify the same weak presence or lack of similarity.

Second, using a rank-k approximation can reduce computation during pairwise document similarity calculations. If we wanted to know the similarity between D₁ and D₂, normally we would not recreate X₂ and use its columns for cosine similarity. Instead, we would use V₂^T directly, since this encodes the original documents and the amount of each concept the documents contain. There is no need to step back to the terms themselves, since they aren't needed for the similarity calculation. Using D₁ and D₂ in V₂^T, we would first normalize the 2×1 columns, then dot product them to generate a result.

Notice that if you are using concept amounts from algorithms like LSA, there is a subtle but important consideration when computing cosine similarity. For raw term frequencies or TF-IDF weighted term frequencies, the values are always positive, because you cannot have a negative number of terms. For LSA, however, the amount of a concept contained in a document can be negative. Consider the similarity between D₂ and D₅.

The cosine similarity between D₂ and D₅ is negative. We saw that the cosine similarity using X₂ between D₁ and D₅ was also negative. What does it mean to have a "negative" similarity between two documents? The key is to recall that, for normalized vectors, cos( \(\theta\) ) = D₂ · D₅ and since the range of \(\theta\) is [0 … 180], this produces a range of [1 … -1] for \(\cos(\theta)\). To address this, we can use \(^{1+\cos(\theta)} / _{2}\) to shift the range of cosine similarities back to [1 … 0]. If we do this, |D₂| · |D₅| = 0.24. We would also need to apply this correction to |D₁| · |D₂| = 0.989 to ensure all similarities are directly comparable. Doing this for all pairs of documents produces the following similarity matrix Σ₂.

Latent Dirichlet Allocation

Latent Dirichlet allocation (LDA) is one of the most popular methods for topic modelling. LDA begins by asking the user to define a number of topics \(k\). LDA then assumes a Dirichlet allocation of words to form each topic, and a Dirichlet allocation of topics embedded in each document. A set of intuitive assumptions are made during LDA topic modelling.

• Documents with similar topics use similar groups of words,
• Latent topics are found by searching for groups of words that frequently occur together in documents \(d_i \in D\), and
• Documents are probability distributions over latent topics to highlight that a document will contain more or less words from a specific topic.

Given these assumptions, LDA assumes a statistical generative process constructed each document, and reverses this to backtrack from the documents in \(D\) to identify a set of \(k\) topics in the context of \(D\). LDA required the user to define three parameters.

• the document–topic density factor \(\alpha\),
• the topic–word density factor \(\beta\), and
• the number of topics \(k\) as noted above.

Note that \(\alpha\) is a \(k\)-dimensional vector allowing a separate \(\alpha\) to be defined for each topic. Similarly, \(\beta\) is a \(|D|\)-dimensional vector, where \(|D|\) is the number of unique terms in the document collection. The (imaginary) generative process is defined as follows.

1. \(\theta_i \sim \textrm{Dir}(\alpha_i), \; i \in \{ 1, \ldots, n \}\) is the distribution of topics for document \(d_i\).
2. \(\phi_j \sim \textrm{Dir}(\beta_j), \; j \in \{ 1, \ldots, k\}\) is the distribution of terms for topic \(T_j\).
3. \(t_{i,u}\) is the \(u\)-th term of document \(d_i\).
4. \(z_{i,u}\) is the topic for term \(t_{i,u}\).

LDA reverses this generative process by recognizing that the only observable variables are the documents themselves. From this, it must determine a topic for each word, the distribution of topics for each document, and the distribution of words for each topic. \(\theta_i\) and \(\beta_j\) are vectors of probabilities. \(z_{i,u}\) is an integer in \(\{1, \ldots, k\}\) defining the topic of the \(u\)-th term in document \(d_i\). The discrete random variables are distributed via the following probability distributions. \begin{align} \begin{split} p(z_{i,u} = T_s \, | \, \theta_i) &= (\theta_i)_s\\ p(t_{i,u} = v \, | \, z_{i,u}, \phi_1, \ldots, \phi_k) &= (\phi_{z_{i,u}})_v \end{split} \end{align}

Here, \((\theta_i)_s\) is the \(s\)-th element of vector \(\theta_i\), which defines the percentage of document \(d_i\) that corresponds to topic \(s\). To complete the discussion, the equations and parameters are combined into a joint probability distribution. \begin{equation} p(t,z,\theta,\phi \,|\, \alpha,\beta) = \prod_{u=1}^{k} p(\phi_u \,|\, \beta) \prod_{v=1}^{n} \left[ p(\theta_v \,|\, \alpha) \prod_{w=1}^{|D|} p(z_{w,v} \,|\, \theta_{v}) p(t_{v,w} \,|\, z_{v,w},\phi) \right] \end{equation}

Although the theoretical foundations of LDA are interesting and important, it is equally critical to understand how to determine the topics for documents in a document collection using Python and scikit-learn. The following code example takes our five Romeo and Juliet and New Hampshire documents and builds five topics, then reports the top five terms for each topic and the topic with the highest probability for each document.

Word Embeddings

A more recent alternative to document–term matrices are word embeddings. Word embeddings are numeric vectors assigned to individual terms such that words that are closer in the embedding space are expected to be similar, where similar means they point in a common direction in the embedding space. Because of this, cosine similarity (dot product) is normally used to calculate term similarity. spaCy uses word embeddings in its medium and large models to represent words. Remember, to use spaCy, you need to install both the package and its language models. As an example, here is part of the 300-element word embedding for the term wolverine.

The most common way to create word embeddings is through the use of neural networks, although dimensional reduction and term co-occurrence can also be used. A paper in 2013 by researchers at Google described Word2Vec, a neural network-based model that learns word associations from a very large corpus of text. It was discovered that the Word2Vec model captures both syntactic and semantic similarities between words. Since words are represented by equal-length vectors, vector operations like addition and subtraction can be applied. Perhaps the most often quoted example of Word2Vec's semantic capabilities was discovering that the most similar term to vec("King")-vec("Man")+Vec("Woman") is vec("Queen").

Although beyond the scope of these notes, there are two basic methods proposed to build a Word2Vec representation (for a more detailed explanation, refer to the paper by Nikhil Biradjdar). The first method is knows as continuous bag-of-words or CBOW. Here, \(n+1\) terms are considered. The first \(\frac{n}{2}\) terms and the last \(\frac{n}{2}\) terms are used to predict the middle term, the intuition being that a term's \(\frac{n}{2}\) preceding and succeeding terms provide context to predict the target term. The second technique, continuous skip-grams, reverses this idea. Given a target term, the model predicts two \(n\)-gram term lists that surround the target term. Weights are used to reduce correspondence for more distant terms.

The main constraint for Word2Vec models is the amount of time needed to train them. Each term embeds \(d\) float values in its vector, usually on the range of 100 to 300. The total vocabulary size of the Word2Vec dictionary is \(v\), which by necessity must be large to properly encode the majority of words contained in a general text corpus. Since deep neural nets are used to construct embeddings, a hidden layer with \(h\) neurons is included in the model. The general computational complexity of CBOW is \(nd + d \log_2(v)\), where \(n\) is the number of context terms. The corresponding complexity for skip-grams is \(n (d + d \log_2(v))\). Since these are fairly theoretical, consider a real-world example. A paper by Kavita Gansen compares timing between CBOW, skip-gram, and a variant of skip-gram (SkipGramSI) that uses bag-of-word n-grams rather than a sequence of preceding and succeeding context characters. For an embeddings size of \(d=150\), a vocabulary size of \(v=255\),\(000\), and a context word range of \(c=10\), the times to train a CBOW and a skip-gram model were 3m 41s and 16m 31s, respectively. The author did not specify the hidden layer size \(h\), but this is not necessarily needed. More importantly, focus on the relative difference in training time (about \(5\times\)) and not the absolute times to train, since we have no idea what type of machine architecture or DNN software was used to obtain these times. Incidentally, this is why we prefer computational complexity to absolute values, since complexity formulas abstract away any specifics about the hardware or software used and focus only on the model parameters' effects on overall runtime.

Understanding word embeddings is important, since spaCy uses them in its NLP pipeline. spaCy's pre-trained medium and large models contain 300-element embedding vectors for 685,000 terms. The difference is that the medium model contains 50-element embedding vectors and 20,000 "common" embeddings, whereas the large model contains 300-element embedding vectors and all 685,000 embeddings. This allows spaCy to provide many properties for each term it evaluates with nlp(). For example, here is a simple Python code snippet and the corresponding list of properties spaCy provides.

To replicate what we have done with TF-IDF–cosine similarity or LSA, we need to use spaCy to construct a similarity matrix. To do this, we perform the following operations.

1. Load a pre-trained spaCy NLP model.
2. Use the NLP model to compute NLP properties for each document.
3. Use the NLP properties to remove punctuation, numbers, and stop words from each document.
4. Recompute NLP properties on the documents without stop words.
5. Compute the similarity between all pairs of documents to build a similarity matrix.

Here is Python code to construct a similarity matrix for our five-document example using spaCy.

As a comparison, here are the similarity matrices for TF-IDF–cosine, LSA–cosine rank 2, and embedding–cosine.

Embedding Similarity

Since embeddings are n-element vectors, cosine similarity is used to compute similarity between two embeddings. A more important issue is how embeddings are obtained for multi-term text blocks like sentence, paragraphs, or entire documents. By default, spaCy averages the word embeddings for each term in a text block, then uses the average as an embedding for the text blocks. This is relevant, since an equal-weight average may not be the most appropriate method for aggregating term embeddings to construct a text block embedding. In this case, we can design our own aggregation strategy by taking individual term embeddings and combining them in different ways.

Gensim Word2Vec

spaCy comes with numerous pre-trained word embedding vocabularies. Situations may exist, however, where we may want to build our own word embedding dictionary. Consider a situation where we are working in a specialized domain. Two potential problems could occur. First, spaCy's vocabulary may not contain important terms from this domain. Second, even for terms that do exist in spaCy's model, the word embeddings may not be specialized to the specific domain being studied. One strategy to address this is to construct a specialized Word2Vec embedding dictionary \(\mathrm{D}_{\mathrm{domain}}\) for terms that are important to your domain. Once this is available, embeddings for a term \(t_i\) would be chosen as follows.

1. If \(t_i \in \mathrm{D}_\mathrm{domain}\), use the embedding in \(\mathrm{D}_\mathrm{domain}\).
2. Otherwise, if \(t_i \in \mathrm{spaCy}\), use the embedding in spaCy.
3. Otherwise, \(t_i\) is out-of-vocabulary (OOV) and no embedding exists.

The next question is, How do we created \(\mathrm{D}_\mathrm{domain}\)? Fortunately, gensim can built word2vec embeddings from a training corpus. The following code takes a sample dataset of hotel reviews from different cities, then builds word2vec embeddings for terms in the review corpus.

Once word embeddings are available, either through a pre-trained model or constructed using gensim, we can perform a variety of operations using the embeddings. The two most common operations are computing similarity between two words, and identifying which words are "most similar" to a target word.

Remember that since word embeddings are n-dimensional vectors, vector math can be performed using them. An often quoted example from the original Word2Vec paper was that the most similar word to the equation vec("King") - vec("man") + vec"woman") was vec("queen"). This seems quite amazing, since it suggests that semantics are also being included in a word's embedding, and those semantics can somehow be manipulated with simple vector mathematics. We need to be careful, though, to more fully examine this result. If we look at the top 10 most similar words to wv("king") - vec("man") + vec("woman") for our hotel review dataset, we obtain the following result.

This makes it clear that queen refers to a queen sized bed, and not to an individual of the monarchy. It also demonstrates clearly that the training set, as with all supervised machine learning algorithms, dictates how the model predicts. Did the original Word2Vec's training set produce queen in the monarchy sense? Looking at additional terms most similar to vec("king") - vec("man") + vec("woman") should answer that question (e.g., did vec("princess") appear on that list?)

Clustering

Once similarities between pairs of documents have been calculated, they can be used to cluster the documents into groups. This is often called topic clustering, since each group represents a set of documents with similar content, and by assumption that discuss a similar topic or topics.

Any similarity-based clustering algorithm can be used for topic clustering, for example, k-means, closest-neighbour agglomerative, density-based, and so on. We present a graph-based clustering algorithm that uses threshold similarities to partition the document collection into clusters. Varying the threshold similarity produces a hierarchical clustering at different levels of granularity.

Minimum Spanning Tree Clustering

Any similarity algorithm (e.g., TF-IDF or LSA) can be used to construct a pairwise document similarity matrix Σ, where σi,j ∈ Σ defines the similarity between documents D_i and D_j. Since σi,j = σj,i, only the upper or lower half of Σ is normally defined. The TF-IDF matrix X and the similarity matrix Σ for the five document example in the LSA section contains the following values.

We want to use values in Σ to build a graph with documents as nodes and weighted edges defining the similarity between documents, with similar documents close to one another. To do this, we must weight the edges with dissimilarities Δ = 1 - Σ. Now, two documents D_i and D_j with σ_i,j = 1 will have an edge weight of δ_i,j = 1 - σ_i,j = 0, so they will overlap. Two documents D_i and D_j with σ_i,j = 0 will have an edge weight of δ_i,j = 1 - σ_i,j = 1, so they will be a maximum possible distance from one another.

Once Δ is built, it is used to construct a complete graph with n nodes representing the n documents, and nm edges representing the similarities between all pairs of documents. Each edge connecting D_i and D_j is weighted with δ_i,j. Kruskal's minimum spanning tree (MST) algorithm is run to find a minimum-weight tree that includes all n documents.

This force-directed graph shows the five document example with the Euclidean distance between nodes roughly equal to the dissimilarity between the corresponding documents. MST edges are drawn in red and labelled with their δ_i,j.

Once the MST is constructed, topic clusters are formed by removing all edges e_i,j in the MST whose δ_i,j ≥ τ for a threshold dissimilarity τ. This produces one or more disconnected subgraphs, each of which represents a topic cluster. The larger the value of τ, the more dissimilarity we allow between documents in a common cluster. For example, suppose we chose τ = 0.5 in the above TF-IDF dissimilarity graph. This would produce four topic clusters: C₁ = { D₄, D₅ }, C₂ = { D₁ }, C₃ = { D₂ }, and C₄ = { D₃ }. Increasing τ to 0.6 produces two topic clusters: C₁ = { D₁, D₃, D₄, D₅ }, and C₂ = { D₂ }.

Semantically, we might expect to see two clusters: C₁ = { D₁, D₂, D₃ }, and C₂ = { D₁, D₅ }. However, because δ_1,2 = δ_3,4 = 0.69, it is not possible to subdivide the MST in a way that combines D₁ with D₃, but separates D₃ from D₄. This is a consequence of the fact that TF-IDF has no knowledge of context. It only has access to the terms in the documents to make its similarity estimates.

An alternative is to use LSA to derive a dissimilarity matrix that includes term correspondences in its results. The matrix Δ₂ below shows dissimilarities for the five document example derived from X₂, the LSA rank-2 estimate of the original term–frequency matrix X.

In this graph, choosing τ = 0.2 removes only the edge between D₃ and D₄, producing two clusters: C₁ = { D₁, D₂, D₃ } and C₂ = { D₄,D₄ }. This matches our intuitive idea of how the five documents should cluster.

Practice Problem 3

Take the following four excerpts from Haruki Murakami's Norwegian Wood, Yasunari Kawabata's Snow Country, Natsume Soseki's Kokoro, and Kazuo Ishiguro's The Remains of the Day.

Subdivide each document \(D_i\) into sentences \(s_{i,j}\). Perform stop word removal and stemming, then convert the sentences into a sentence-term matrix. Weight terms in the matrix using TF-IDF and normalize each row to correct for sentence length. Finally, use cosine similarity to compute a pairwise sentence similarity matrix, convert this to a dissimilarity matrix, then use k-means clustering to cluster the sentences into ten clusters.

Summarization

A common task when large document collections are analyzed is automatically compressing their content into a condensed text summarization that highlights the salient topics or information contained in the document collection. Not surprisingly, this is a difficult problem, particularly when the document collection is large. Three standard methods have been proposed, in increasing order of complexity: (1) representative term extraction; (2) representative sentence extraction; and (3) representative sentence construction. We will focus on the first two techniques, since construction of unique sentences based on topics or information in the collection requires a level of NLP that is beyond the scope of what we are discussing in this module.

In an ideal situation, automatic text summarization would: (1) recognize the content of a document collection; and (2) summarize the collection's central ideas. This requires a system that understands the semantics of the collection. Since this is an unsolved problem, most summarization algorithms fall back to extracting text from the document collection to summarize it. This has the disadvantage of generating extractions that may not be coherent. However, a reader can normally infer relationships between the extractions to form a reasonable understanding of the content document collection contains.

Term Extraction

In term extraction, we attempt to identify a small set of terms that accurately represent the main topics, ideas, or concepts contained in a document collection. Various simple methods exist to select the terms to extract.

• Term Frequency. Terms that occur frequently in the document collection can be assumed to be important, and therefore can be included in an extract term summary.
• Weighted Term Frequency. A weighted term frequency like TF-IDF can be used in place of raw term frequency, since this is designed to take into account both the absolute frequency of a term in a document, and the term's uniqueness across documents in the collection.
• Sentence Position. The position of a sentence within a document can imply the sentence's importance. For example, sentences at the beginning of a document often summarize the document, and so are considered more important than internal sentences. Term frequencies can be weighted by the estimated importance of their parent sentence.
• Title Words. Terms in a document's title are usually considered critical, since by design a title is meant to summarize the content of the document. These terms should be increased in weight to recognize this.
• Cue Words. Certain words like "important" or "relevant" within a sentence may indicate that terms in the sentence are directly related to topics contained in a document. Sentences with cue words can have the weights of the terms increased to represent this.
• Concept Relevance. Certain terms can be converted to concepts by considering properties like synonyms or part meronyms. For example, the term "bicycle" could be converted to a "bicycle" concept by converting the terms "bike" (synonym) and "pedal" (part meronym) to "bicycle".

Sentence Extraction

A simple approach to sentence extraction is to weight terms in the sentence, the apply an aggregation to those terms to estimate an overall sentence score. Any of the term extraction techniques discussed above could be used to do this. For example, TF-IDF scores for each term in a sentence could be averaged prior to normalizing each term vector. Other weights (position, title, cue word) could be used to adjust the term weights up or down before averaging. Different aggregation methods could also be applied (maximum, minimum, median, and so on).

Another approach that has recently been suggested converts sentences into a graph, then applies a ranking algorithm like HITS or Google's PageRank to identify high rank sentences to include in a summary. As an example, consider the Google PageRank algorithm.

To begin, sentences in a document or document collection must be converted into a graph structure. Each sentence is represented as a node, and the connection between pairs of sentences are represented by an edge between the sentences' nodes. An edge is weighted based on the similarity between the two sentences it connects, representing the concept overlap between the sentences. Only sentences with a similarity above a user-chosen threshold are included in the graph.

Next, the PageRank algorithm is run on the graph. In its general form, PageRank estimates the importance of a node by counting the number and quality of edges connecting to that node. Theoretically, PageRank represents the probability distribution for which node a random click would land on. Nodes are initialized with a weight of \(\frac{1}{n}\) for a graph containing n nodes. Next, each node evenly "contributes" its weight to nodes it links to, updating the node weights. This contribution process is run iteratively until the weights converge such that the average PageRank over the graph is 1. A damping factor d is used on each iteration to enforce convergence.

As an example consider a four-node graph A, B, C, and D, where B links to A and C, C links to A and D links to A, B, and C. The PageRank PR for A would be

In other words, given the number of outgoing links L for a node, a target node q, and the child nodes C_q that link to q, the PageRank of q is defined as

Adding in the damping factor d which represents the probability that a person will eventually stop clicking on random links, the above formula becomes:

The original value for d was 0.85. For our example, the PageRank of A would be 0.427.

Since the general PageRank algorithm does not assume any weights on the edges, these must be added. This is done by updating the basic PageRank algorithm as follows.

where w_q,r is the edge weight between nodes q and r, and P_r are the parents of node r (i.e., the nodes r connects to), and \(\sum_{s \in P_{r}} w_{q,s}\) is the sum of the edges leaving node r. Although this will give different ranks to the nodes compared to the original PageRank algorithm, about the same number of iterations are needed to converge to a set of final values. Once this is done, sentences are sorted in descending order of rank, and the top k sentences are returned as a summary of the document or document collection.

LSA can also be used to extract summary sentences from a document collection. Recall that LSA uses SVD to factor a term–sentence matrix X into three matrices X = UΣV^T. This converts X into a latent semantic structure where the columns of U form concepts as linear combinations of the original terms in X, the rows of V^T describe the amount of each concept contained in individual sentences, and Σ is a diagonal matrix that can be seen as defining the importance of individual topics. The factorization is normally reduced to the top k eigenvalues and corresponding columns and rows in U and V^T.

An initial suggestion for using LSA during summary sentence extraction was to extract the sentences in V^T with the largest value for each topic. This is done by simply collecting sentences with the largest value in the k-th column of V^T, then presenting these as the sentence extraction summary.

The potential problem with this approach is that it treats each topic as equally important. We know this is not true, since the eigenvalues in Σ differentiate the importance of different topics. An improved alternative is to calculate Σ²V, then select sentences s_i with the greatest length \(\sqrt{\sum_j s_{i,j} }\). The intuition is to choose sentences with the largest combined weight across all important topics. This may include more than one sentence discussing an important topic, or a sentence that discusses multiple important topics. When a document collection is summarized, the authors suggest first applying the graph summarization algorithm to individual documents D_i, generating document summary sentences s_i,j. Next, the summary sentences are combined into a graph and further summarized using exactly the same graph-based summary algorithm, producing an overall document collection summary.

Experimental analysis suggests this does a better job of identifying sentences that provide a good summary of the important topics and information in a document collection.

Named Entity Recognition

Named entity recognition (NER) is an NLP task that identifies and classifies entities within a text body. It is sometimes referred to as entity extraction, chunking, or identification. Entities can include text referring to names, organizations, locations, dates and times, numerical values, and so on. The basic pipeline for NER is as follows.

1. Text Preprocessing. Prepare the text for NER using standard text preprocessing operations like tokenization and part-of-speech tagging.
2. Entity Identification. Identify entities in the text.
3. Entity Classification. Classify identified entities.
4. Contextual Analysis. Use context to verify and correct entity classification, for example, does "apple" refer to a company or a fruit? Context may clarify this ambiguity.

Early NER systems used rule-based approaches to identify entities. Examples include capitalization, titles like "Dr.", and so on. An obvious drawback of this method is the time and expertise needed to build a comprehensive set of rules, and to update those rules over time or for specific domains. An example of a Python rule-based NER library is simpleNER. simpleNER supports user-specified rules as patterns or regular expressions, as well as built-in support to extract email addresses, locations, names, date–times, durations, units, keywords, and numbers. simpleNER also integrates with NLTK to perform NTLK-based NER.

Dictionary methods were also proposed as an obvious method to perform NER. These approaches use a dictionary with a large vocabulary and synonym collection to identify named entities. The definition of the entity defines its type. This method is common in domain-specific environments like biomedical analysis. For example, AstraZenca offers VecNER, a dictionary-based NER library that supports entity matching based on spacy's PhraseMatcher and entity identification based on similarity with terms in VecNER's lexicon. VecNER provides a pre-trained model based on Gensim's w2vec model. User-specific models can also be defined or used to extend the built-in models.

The most recent NER models are built on supervised machine learning, normally some form of deep learning. One example of this is the StanfordNERTagger, a Java-based NER model that can be accessed from Python. Specifically, Stanford's NER uses CRF (conditional random field) classification, a statistical pattern recognition technique used for contextual structure prediction. Although we will not explore CRFs in detail, more information about CRFs and the Markov Random Fields on which they are based is available here. Since the Stanford NER is written in Java, using it requires a Java SE runtime for your operating system, the proper support files from the Stanford NER page (click on the Download Stanford Named Entity Recognizer on this webpage), and NLTK, which includes the StanfordNERTagger in its nltk.tag.stanford library.

Another simple option is to use either spaCy's or NLTK's built-in NER parsers. spaCy performs NER as part of its standard NLP pipeline, so results can be extracted from the NLP object spaCy returns. NLTK converts a sentence into tokens, part-of-speech tags each token, then uses the built-in ne_chunk method to assign tags to recognized named entities.

Sentiment

Sentiment is defined as "an attitude, thought, or judgment prompted by feeling." An area of recent interest in text analytics is estimating the sentiment contained in a block of text. This has prompted a number of basic questions. For example, how should sentiment or emotion be characterized so we can measure it? And how can these measurements be extracted from text?

Emotional Models

Psychologists have proposed various models to define different emotional states. In psychology mood refers to a medium or long-term affective state, where affect is described using dimensions like pleasure, arousal, and engagement.

Psychological models use emotional dimensions to position emotions on a 2D plane. The simplest models represents pleasure along a horizontal axis, with highly unpleasant on one end, highly pleasant on the other, and different levels of pleasure in between. For example, when sentiment is described as positive, negative, or neutral, it is normally assumed that "sentiment" means pleasure.

More complex models use more than a single dimension. For example, Russell proposed using valence (or pleasure) and arousal (or activation) to build an emotional circumplex of affect (Russell, J. A. A Circumplex Model of Affect. Journal of Personality and Social Psychology 39, 6, 1161–1178, 1980). Russell applied multidimensional scaling to position 28 emotional states, producing the model shown to the left with valence running along the horizontal axis and arousal along the vertical axes. The intermediate terms excited–depressed and distressed–relaxed are polar opposites formed by intermediate states of valence and arousal.

Similar models have been proposed by Watson and Tellegen (with positive and negative valence axes), Thayer (with tension and energy axes), and Larsen and Diener (with pleasure and activation axes similar to Russell's). The circumplex can be further subdivided into additional emotional regions like happy, sad, calm, and tense.

Natural Language Processing

The area of natural language processing (NLP) in computer science is often used to analyze the structure of a text body. For example, it is useful to subjectivity classification to remove objective, fact-based text prior to estimating sentiment. Pang and Lee proposed a sentence-level subjectivity detector that computes a subjectivity weight for each sentence (Pang, B. and Lee, L. A Sentimental Education. Sentiment Analysis Using Subjectivity Summarization Based on Minimum Cuts. Proceedings of the 42nd Annual Meeting of the Association for Computational Linguistics (ACL '04), 271–278, 2004). Pairs of sentences are assigned an association score based on the difference of their subjectivity scores to estimate whether they belong to a common class. A graph is constructed with sentences and the two classifications (subjective and objective) forming nodes, association weights forming edges between sentences, and subjectivity weights forming edges between each sentence and the classification nodes. A minimum graph cut is then used to split the sentences into subjective and objective classes.

Another common NLP method for sentiment analysis is to train a machine learning algorithm on a set of documents with known sentiment. Naive Bayes, maximum entropy, and support vector machine (SVM) approaches were compared for classifying movie reviews as positive or negative. The presence of absence of a term (unigrams) performed best, with accuracies ranging from 80.4% for maximum entropy to 82.9% for SVM. Interestingly, more complex inputs like bigrams, term frequencies, part of speech tagging, and document position information did not improve performance.

In a similar manner, semantic orientation has been used to rate online reviews as positive or negative (Turney, P. Thumbs Up or Thumbs Down? Semantic Orientation Applied to Unsupervised Classification of Reviews. Proceedings of the 40th Annual Meeting of the Association for Computational Linguistics (ACL '02), 417–424, 2002). The semantic orientation of phrases in a review are compared to the anchor words "excellent" and "poor" by extracting phrases containing predefined target terms, then using pointwise mutual information (PMI) to calculate the statistical dependence between each phrase and the anchor words. The difference PMI(phrase, "excellent") − PMI(phrase, "poor") estimates the direction and the strength of a phrase's semantic orientation. Results for reviews about automobiles, banks, movies, and travel destinations produced accuracies of 84%, 80%, 65.8% and 70.5%, respectively.

Sentiment Dictionaries

An alternative to natural language approaches uses a term dictionary to estimate sentiment, often for short text snippets like online comments or social network conversations. Proponents argue that a short post does not contain enough text and grammar for an NLP algorithm to leverage, and therefore, independent word analysis may produce results comparable to NLP.

Profile of mood states (POMS) was originally designed as a psychometric tool to measure a person's mood state on six dimensions: tension–anxiety, depression–dejection, anger–hostility, fatigue–inertia, vigor–activity, and confusion–bewilderment. Subjects rate 65 adjectives on a five-point scale to produce a score in each dimension that can be compared to population norms. POMS was extended by including 793 synonyms of the original 65 adjectives to form POMS-ex, a word dictionary used to estimate sentiment.

Affective Norms for English Words (ANEW) was built to assess the emotional affect for a set of verbal terms. Three emotional dimensions were scored on a nine-point scale: valence (or pleasure), arousal (or activation), and dominance. A total of 1,033 word that were previously identified as emotion-carrying words, and that provided good coverage of all three dimensions, were rated.

Recent lexical approaches have focused specifically on short text and online social networks. SentiStrength was developed from manually scoring 2,600 MySpace comments on two five-point scales representing both the positive and the negative emotion of a comment. Analysis of the training set produced a dictionary of 298 positive terms and 465 negative terms (Thelwall, M., Buckley, K., Paltoglou, G., Cai, D., and Kappas, A. Sentiment Strength Detection in Short Informal Text. Journal of the American Society for Information Science and Technology 61, 12, 2544–2558, 2010). SentiStrength is augmented to recognize properties of social network text like emoticons, text abbreviations, and repeated letters and punctuation, as well simple use of booster words (somewhat, very) and negation.

WordNet is a lexical database that groups English nouns, verbs, adjectives, and adverbs into sets of cognitive synonyms---synsets---that represent distinct concepts. SentiWordNet estimates the sentiment of synsets by assigning them a positive, negative, and objective (or neutral) score on the range −1 to +1 (Baccianella, S., Esuli, A., and Sebastiani, F. SentiWordNet 3.0: An Enhanced Lexical Resource for Sentiment Analysis and Opinion Mining. Proceedings of the 7th International Conference on Language Resources and Evaluation (LREC '10), 2200–2204, 2010). Individual terms can be matched to their synset, and since these are taken from WordNet, properties like word disambiguation are automatically included.

Estimating Sentiment

As a practical example of estimating sentiment, consider analysis using ANEW's independent word dictionary. ANEW has a number of potential advantages. First, its word list is publically available. Second, it contains multiple emotional dimensions, allowing us to characterize sentiment in ways that more sophisticated than a simple positive–negative rating. We apply ANEW to process a text body as follows:

1. Parse the text body into terms, then identify the n ANEW terms { t₁, … , t_n } that match entries in the ANEW dictionary.
2. For each t_i, extract the average and standard deviation for valence (v_i,μ, v_i,σ) and arousal (a_i,μ, a_i,σ) from the dictionary.
3. If a text body has less than n=2 ANEW terms, discard it as having insufficient measurements to estimate an overall sentiment.
4. If n ≥ 2, aggregate individual term values to estimate an overall average and standard deviation for valence (V_μ, V_σ) and arousal (A_μ, A_σ).

Calculating an overall standard deviation from a set of term average and standard deviations pairs (μ_i, σ_i) is done using a formula for averaging standard deviations. For example, for V_σ it is

Calculating the overall average of individual term averages is more complicated. We could use a simple unweighted average, however, this ignores each term's standard deviation v_i,σ. A large deviation v_i,σ implies ambiguity in how respondents rated a term. The term could be a homonym: lie, to not tell the truth versus lie, to recline. The term could have been viewed in different contexts: a sentence where the term is used directly, "I'm happy" versus a sentence were it's negated, "I'm not happy." The term could simply be difficult to score: what valence should we attach to the ANEW term "bench?"

Intuitively, the larger v_i,σ, the less weight we want to give v_i,μ in the overall average, since we are less confident about where its true average lies. To do this, we calculate a term's cumulative distribution function (the normal curve) p, then use the probability at p(v_i,μ) to weight v_i,μ in the overall average. This gives a lower weights to terms with larger v_i,σ. The height of the normal curve with μ = v_i,μ and σ = v_i,σ at x = v_i,μ is

Given p_i for each term t_i, we normalize the p_i's, then calculate a final weighted average.

Consider the tweet "Congrats to @HCP_Nevada for their health care headliner win!" with two ANEW terms "health" (v_μ = 6.81, v_σ = 1.88) and "win" (v_μ = 8.38, v_σ = 0.92). An unweighted average of the v_μ's produces V_μ = 7.56, but since the standard deviation for health is higher than for win, v_health,μ receives a weight of  ^0.21/_0.64 = 0.33, while v_win,μ receives a weight of  ^0.43/_0.64 = 0.67. This produces a weighted average V_μ = 7.86 that falls closer to win's valence, exactly as we want.

Visualization

The simplest (and most common) way to visualize text is to display it directly to a user. This is useful, since it reveals the full detail of a document. It also has drawbacks, however. Documents take time to read. For a few documents, it might be possible to analyze them by reading them. For larger document collections, however, reading every document in its entirety is not feasible. Instead, some method is needed to present higher-level overviews of the documents and their relationships to one another, for example, summaries, topic clusters, or geolocations.

Tweet Visualization

As a practical example of a number of visualization techniques, consider an ongoing project to analyze tweets posted on Twitter, an online social network that allows users to upload short text messages—tweets—of up to 140 characters. This restriction encourages users to construct focused, timely updates. Twitter reported in its IPO filing users were posting an average of 500 million tweets per day. Tweets are now being archived at the U.S. Library of Congress. Twitter has also shown the potential for societal impact, for example, in its use as a communication and organizing tool for activists during the 2011 "Arab Spring" protests in various Middle Eastern countries.

Collections of tweets are visualized in numerous ways: by sentiment, by topic, by frequent terms, and so on. Individual tweets are drawn as circles. Each circle's colour, brightness, size, and transparency visualize different details about the sentiment of its tweet:

• Colour. The overall valence or pleasure of the tweet: pleasant tweets are green, and unpleasant tweets are blue.
• Brightness. The overall arousal of the tweet: active tweets are brighter, and subdued tweets are darker.
• Size. One measure of how confident we are about the estimate of the tweet's sentiment: larger tweets represent more confident estimates.
• Transparency. A second measure of how confident we are about its estimate of the tweet's emotion: more opaque (i.e. less transparent) tweets represent more confident estimates.

Tweets are presented using several different visualization techniques. Each technique is designed to highlight different aspects of the tweets and their sentiment.

Sentiment

The estimated sentiment of each tweet defines its position in an emotional scatterplot with pleasure and arousal on its horizontal and vertical axes. The spatial distribution of the tweets summarizes their overall sentiment.

Details are presented on demand. If the user hovers the mouse cursor over a tweet, it reveals its body. Words in the sentiment dictionary are highlighted in bold italics. Clicking on a tweet generates a detail dialog with the overall pleasure and arousal for the tweet, as well as each sentiment term's mean and standard deviation of pleasure, mean and standard deviation of arousal, and frequency.

Topics

Text similarity and MST clustering are used to identify tweets that discuss a common topic or theme. Each topic is visualized as a rectangular group of tweets, with keywords at the top to summarize the topic, and a number at the bottom to identify the number of tweets in the cluster.

Tweets within each cluster are laid out so that the distance between them shows their text similarity: closer for stronger similarity. Topic cluster rectangles are positioned in the same way: closer for more similar topics. Tweets that are not part of any topic are visualized as singletons on the right.

As with the sentiment, details are available on demand by hovering the mouse over a tweet or clicking a tweet to reveal its content and its estimated sentiment.

Heatmap Tab

A heatmap visualizes the a discretized distribution of elements in a 2D plot. Here, we use a sentiment histogram to highlight "hot" red regions with many tweets, and "cold" blue regions with only a few tweets.

The emotional scatterplot is subdivided into an 8 × 8 grid of bins representing one-unit steps in pleasure and arousal. The number of tweets falling within each bin is counted and visualized using colour: red for bins with more tweets than average, and blue for bins with fewer tweets than average. White bins contain no tweets. Stronger, more saturated colours lie farther from the average.

Hovering the mouse over a heatmap bin reveals the number of tweets that lie in the bin.

Tag Cloud

A tag cloud visualizes a collection of text documents as a set of frequent terms, where the size of a term represents the number of times is occurs in the document set.

Tweets are visualized as four separate tag clouds in four emotional regions: upset in the upper-left, happy in the upper-right, relaxed in the lower-right, and unhappy in the lower-left. A term's size shows how often it occurs over all the tweets in the given emotional region. Larger terms occur more frequently.

Timeline

A timeline visualizes the number of tweets that occur over a given time window using a double-ended bar graph. Pleasant tweets are shown in green above the horizontal axis, and unpleasant tweets in blue below the axis.

The height of a bar in the graph shows the number of tweets posted over the time range covered by the bar. Bars are split into four segments representing the number of relaxed and happy tweets—in dark green and light green—and the number of unhappy and upset tweets—in dark blue and light blue.

Map

Maps are used to geolocate data. Tweets are visualized at the latitude and longitude where they were posted. We use the same sized, coloured circles from the sentiment and topic visualizations to show estimated sentiment and confidence in the estimate.

Twitter presents an interesting problem for geolocation. Because it implements an "opt-in" system for reporting location, users must explicitly choose to allow their location to be posted before their tweets are geotagged. Most users have not done this, so only a very few tweets contain location data. The label in the upper-right corner of the map is modified to show the total number of geotagged tweets in parentheses, to highlight this difference relative to the other visualizations.

Affinity

An affinity graph visualizes relationships between text elements. The basis for a relationship depends on the type of data being visualized. For tweet data, the affinity graph includes frequent tweets, people, hashtags, and URLs, together with relationships or affinities between these elements.

As before, blue and green nodes represent tweets. Orange nodes represent people, yellow nodes represent hashtags, and red nodes represent URLs. Larger nodes show more frequent elements. Links between nodes highlight relationships, for example, tweets that are similar to one another, or hashtags and people that occur in a set of tweets.

Tweets

Even with sophisticated visualization techniques available, it is often important to show the raw text in a document. A common analysis strategy is to use visualizations to filter a large document collection into a small subset of documents that are of particular interest to an analyst. Those documents can then be read to reveal specific details that cannot be easily captured in the visualizations.

For tweets, we show the date, author, and body of each tweet, as well as its overall pleasure v and arousal a. Sentiment terms in each tweet are highlighted in bold italics. This allows a viewer to see both the raw text of the tweet, and the estimated sentiment values we derived.

Practice Problem 4

Take the following except from John Steinbeck's famous novel, Of Mice and Men.

Convert this text into sentences, then estimate the sentiment of each sentence. You can use the vaderSentiment (Valence Aware Dictionary and sEntiment Reasoner) package to perform sentence-level sentiment analysis. vaderSentiment is included in nltk, so you already have access to this library. To use vader's sentiment capabilities, import nltk and load vader's sentiment lexicon, import the sentiment analyzer, and use it to begin analyzing sentences. For more details and documentation, read the GitHub repository's README.rst.

vader scores each sentence in terms of its negative, neutral, and positive components, along with a compound aggregate score for the entire sentence. The compound score is reported on the range [-1 … 1], representing most negative at -1 to most positive at 1.

Once you have sentence-level sentiment, you need to consider two additional issues. First, how should you aggregate the sentence-level scores into a single, final score for the Of Mice and Men excerpt? Second, do you want to report (and use) the compound score for each sentence, or some combination of the scores returned? There is no "right answer" to either question, but what you choose will affect the results you report.