<jupyter_start><jupyter_text>CS4619: Artificial Intelligence IIBag of Words    Derek Bridge    School of Computer Science and Information Technology    University College Cork Initialization$\newcommand{\Set}[1]{\{1\}}$ $\newcommand{\Tuple}[1]{\langle1\rangle}$ $\newcommand{\v}[1]{\pmb{1}}$ $\newcommand{\cv}[1]{\begin{bmatrix}1\end{bmatrix}}$ $\newcommand{\rv}[1]{[1]}$ $\DeclareMathOperator{\argmax}{arg\,max}$ $\DeclareMathOperator{\argmin}{arg\,min}$ $\DeclareMathOperator{\dist}{dist}$$\DeclareMathOperator{\abs}{abs}$<jupyter_code>%load_ext autoreload
%autoreload 2
%matplotlib inline
import pandas as pd
import numpy as np
import matplotlib.pyplot as plt

from sklearn.feature_extraction.text import CountVectorizer
from sklearn.feature_extraction.text import TfidfVectorizer

from sklearn.model_selection import train_test_split
from sklearn.model_selection import ShuffleSplit
from sklearn.model_selection import GridSearchCV
from sklearn.model_selection import cross_val_score

from sklearn.metrics import accuracy_score

from sklearn.pipeline import Pipeline

from sklearn.preprocessing import LabelEncoder

from sklearn.linear_model import LogisticRegression

from sklearn.decomposition import TruncatedSVD<jupyter_output><empty_output><jupyter_text>Free-Form Text    We've looked at AI systems that can handle structured data (i.e. numeric-valued and non-numeric-valued features) and AI systems that can handle images.        Suppose instead the objects in your dataset are documents, rather than houses, students, irises or photos.                    E.g. web pages, tweets, blog posts, emails, posts to Internet forums and chatrooms, &hellip;            They might have a little structure to them (headings and so on), but they are primarily                free-form text, written in a natural language such as English.                            Many AI algorithms can only handle vectors of numbers. So one way to apply AI techniques to         a dataset of documents is to convert the raw text in the documents into vectors of numbers.        Note that in this lecture, each document becomes one vector. In the next lecture, each word becomes one vector and hence a document becomes a list of vectors.        <!--    Our treatment of this will be brief and high-level, since many of you studied        CS4611 Information Retrieval, where this is covered in depth.        -->     We'll illustrate this lecture using scikit-learn         although its facilities for handling text are quite limited.         If you really want to do AI with text, consider a more powerful library such as NLTK        (http://www.nltk.org/) or the Stanford Natural Language        Processing Toolkit         (https://nlp.stanford.edu/software/).      SetsBackground Maths    A set is a collection of objects with two properties:                    Order is not important,                e.g. $\Set{a, c, f} = \Set{c, f, a}$                        Duplicates are not allowed,                e.g. $\Set{a, c, f} = \Set{a, c, a, f}$                            The set of all possible objects $U$ is called the universal set, e.g. $U = \Set{a, b, c, d, e, f, g}$.Background Computer Science    There are many data structures we can use to store sets, e.g. linked lists, binary search trees, &hellip;    But we can describe a set by a binary-valued vector.                    E.g. if $U = \Set{a, b, c, d, e, f, g}$, then we can represent the set $\Set{a, c, f}$ as follows:                                                            $a$$b$$c$$d$$e$$f$$g$                                                                $1$$0$$1$$0$$0$$1$$0$                                                                Then, we can store the set using the same data structure that we use for storing vectors, e.g. numpy arrays.         In fact, if $U$ is large but the sets we store tend to be much smaller, then our vectors will be        sparse (mostly zero).        It may be more efficient to use a data structure that only stores the non-zero elements. numpy has several data structures for this (e.g. csr_matrix).     BagsBackground Maths    A bag is a collection of objects with one property:                    Order is not important,                e.g. $\Set{a, c, f} = \Set{c, f, a}$                        This time, duplicates are allowed,                e.g. $\Set{a, c, f} \neq \Set{a, c, a, f}$                        Background Computer Science    But we can describe a bag by a numeric-valued vector, where the numbers are the frequencies with which the elements occur.                    E.g. if $U = \Set{a, b, c, d, e, f, g}$, then we can represent the bag $\Set{a, c, a,  f}$ as follows:                                                            $a$$b$$c$$d$$e$$f$$g$                                                                $2$$0$$1$$0$$0$$1$$0$                                                                        We can store these as numpy arrays or, if they are sparse, we can use numpy's sparse data structures.     Bag-of-Words    We will represent each document by a bag-of-words.    This will lose us lots of information. Start thinking about what we will lose! Running example    Suppose our dataset contains just these three documents:            Tweet 0        Tweet 1        Tweet 2                        No one is born hating another person because of the color of his skin or his background             or his religion.                            People must learn to hate, and if they can learn to hate, they can be taught to love.                    For love comes more naturally to the human heart than its opposite.                   Three tweets from <NAME>, quoting <NAME>      Tokenization    First, we must tokenize each document. This means splitting it into tokens. terms.-->    In our simple treatment, the tokens  are just the words, ignoring punctuation and making everything        lowercase.       In reality, this is surprisingly complicated,                  e.g. is "don't" one token  or two or three?           e.g. maybe pairs of consecutive words (so-called 'bigrams') could also be treated as if they were single tokens  ("no one", "one is",               "is born")           and so on.             Stop-words    Optionally, discard stop-words:    Stop-words are common words such as "a", "the", "in", "on", "is, "are",&hellip;    Sometimes discarding them helps, or does no harm, e.g. spam detection.    Other times, you lose too much, e.g. web search engines ("To be, or not to be"). Running example    After tokenization and discarding stop-words:            Tweet 0        Tweet 1        Tweet 2                            born hating person color skin background religion                            people learn hate learn hate taught love                    love comes naturally human heart opposite          Stemming or lemmatization    Optionally, apply stemming or lemmatization to the tokens.     E.g. "hating" is replaced by "hate", "comes" is replaced by "come" Running example    What would the tweets look like after stemming?    What would they look like after lemmatization? Count vectorization    Each document becomes a vector, each token  becomes a feature, feature-values are        frequencies (how many times that token  appears in that document).     Running example                    background        born        color        comes        hate        hating        heart        human        learn        love        naturally        opposite        people        person        religion        skin        taught                Tweet 0:        1        1        1        0        0        1        0        0        0        0        0        0        0        1        1        1        0                Tweet 1:        0        0        0        0        2        0        0        0        2        1        0        0        1        0        0        0        1                Tweet 2:        0        0        0        1        0        0        1        1        0        1        1        1        0        0        0        0        0             TF-IDF vectorization    Optionally, replace the frequencies by tf-idf scores.    tf-idf scores penalise words that recur across multiple documents,                    e.g. in emails, word such as "hi", "best", "regards", &hellip;                You can look up the formual, if you are interested. CS4611.-->                    Variants of the formula might: scale frequencies to avoid biases towards long documents                 (not scikit-learn);                logarithmically scale frequencies (not default in scikit-learn);                add 1 to part of the formula to avoid division-by-zero (default in scikit-learn);                normalize the results (e.g. by default, scikit-learn divides by the L2-norm)                         Running example                    background        born        color        comes        hate        hating        heart        human        learn        love        naturally        opposite        people        person        religion        skin        taught                Tweet 0:        0.38        0.38        0.38        0        0        0.38        0        0        0        0        0        0        0        0.38        0.38        0.38        0                Tweet 1:        0        0        0        0        0.61        0        0        0        0.61        0.23        0        0        0.31        0        0        0        0.31                Tweet 2:        0        0        0        0.42        0        0        0.42        0.42        0        0.32        0.42        0.42        0        0        0        0        0     The dimension of these vectors    Sparsity:                    Here we have $n = 17$ features (columns). How many will there be in general?            Most of the feature-values are zero, hence the matrix is sparse. Why?                We have the curse of dimensionality again.                    Reduce the number of features by:                                    discarding tokens that appear in too few documents (min_df in scikit-learn);                                        discarding tokens that appear in too many documents (max_df);                    keeping only the most frequent tokens (max_features).                                        Use dimensionality reduction:                                    e.g. singular value decomposition (SVD) is suitable for bag-of-words, rather than PCA.                                         Observation about bag-of-words representations    This representation is good for many applications in AI but it does have drawbacks too:                    It loses all the information that English conveys through the order of words in sentences,                                    e.g. "People learn to hate" and "People hate to learn" have very different meanings but                        end up with the same bag-of-words representation.                                                            It loses the information that English conveys using its stop-words, most notably negation,                                    e.g. "They hate religion" and "I do not hate religion" will have the same bag-of-words                        representation.                                                                This may not matter for some applications (e.g. spam detection) but will matter for        others (e.g. machine translation), for which you need a different representation.        What other weaknesses does it have? Bag-of-Words in scikit-learn<jupyter_code>tweets = [
    "No one is born hating another person because of the color of his skin or his background or his religion.",
    "People must learn to hate, and if they can learn to hate, they can be taught to love.",
    "For love comes more naturally to the human heart than its opposite."
]
# Create the vectorizer
vectorizer = CountVectorizer(stop_words='english')

# Run the vectorizer
vectorizer.fit(tweets)
X = vectorizer.transform(tweets)<jupyter_output><empty_output><jupyter_text>In the example below, we used a CountVectorizer.    It does tokenization:                    By default, it converts to lowercase, it treats punctuation as spaces, and it treats two or more                consecutive characters as a word. Each word becomes a token  (feature).                            The example discards stop-words.<jupyter_code># FYI here's the list of stop-words that scikit-learn uses.

from sklearn.feature_extraction.text import ENGLISH_STOP_WORDS

ENGLISH_STOP_WORDS<jupyter_output><empty_output><jupyter_text>The CountVectorizer also, by default, discards any word that appears in every document.    It does not do stemming or lemmatization. scikit-learn doesn't have a stemmer, but does make it easy to call one, if you get one from another library,                 e.g. NLTK.<jupyter_code># FYI, let's see the tokens (features) that it ends up with
vectorizer.get_feature_names()<jupyter_output><empty_output><jupyter_text>Finally, the CountVectorizer vectorizes, producing sparse matrices of word frequencies.         (There is an option to produce a binary representation, instead of frequencies.)        We know we want this to be stored in an efficient sparse matrix, and scikit-learn takes care of this        'behind the scenes'. (Do not vectorize and then                convert back to Pandas DataFrames because, by default, DataFrames are not sparse data structures)<jupyter_code># We can look at the sparse array. The first number identifies the tweet (0, 1 or 2), the second is which feature, and
# the last is the frequency
print(X)
# Vectorize a new document
new_document = "Unsurprisingly, people hate to learn that their religion loves to hate."

new_document_as_vector = vectorizer.transform([new_document])
# Notice how it ignores words that weren't in the original tweets, such as "unsurprisingly" and "loves"

print(new_document_as_vector)<jupyter_output>(0, 4)	2
  (0, 8)	1
  (0, 12)	1
  (0, 14)	1<jupyter_text>In the example below, we use a TfidfVectorizer instead.    (Advanced: By default, it normalizes the values using the L2 norm.) --><jupyter_code># Create the vectorizer
vectorizer = TfidfVectorizer(stop_words='english')

# Run the vectorizer
vectorizer.fit(tweets)
X = vectorizer.transform(tweets)
print(X)
# Vectorize a new document
new_document = "Unsurprisingly, people hate to learn that their religion loves to hate."

new_document_as_vector = vectorizer.transform([new_document])
# Notice how it ignores words that weren't in the original tweets, such as "unsurprisingly" and "loves"

print(new_document_as_vector)<jupyter_output>(0, 14)	0.3779644730092272
  (0, 12)	0.3779644730092272
  (0, 8)	0.3779644730092272
  (0, 4)	0.7559289460184544<jupyter_text>Similarity &amp; Distance for Bag-of-Words    For details and formulae, see CS4611.-->    Euclidean distance is not suitable.    Very common is cosine similarity, which gives values in $[0, 1]$, where 1 means 'identical'.    To get cosine distance, we can subtract from 1, so now 1 means 'completely different'.    The exact formulae differ depending on what is assumed about normalization.                    If we assume the vectors have been normalized, then there is a simpler formula.            If not, then the formula is more complicated.             Similarity &amp; distance for bag-of-words representation in scikit-learn    The code below assumes that the vectors have already been normalized, e.g. produced        by TfidfVectorizer.<jupyter_code>def cosine(x, xprime):
    # Assumes x and  xprime are already normalized
    # Converts from sparse matrices because np.dot does not work on them
    return 1 - x.toarray().dot(xprime.toarray().T)
# So which of Barack Obama's tweets is most similar to our new document?
tweets[np.argmin([cosine(new_document_as_vector, x) for x in X])]<jupyter_output><empty_output><jupyter_text>Case Study: A Classifier     Stanford University researchers have taken 50,000 movie reviews from IMDB,        labelled them as either positive or negative and made them available.        I've taken the first 5,000 of them.<jupyter_code>df = pd.read_csv("../datasets/dataset_5000_reviews.csv")
df.head()
# We'll just use holdout to keep things fast
dev_df, test_df = train_test_split(df, train_size=0.8, stratify=df["sentiment"], random_state=2)

ss = ShuffleSplit(n_splits=1, train_size=0.75, random_state=2)
# Extract the features but leave as a DataFrame
dev_X = dev_df["review"]
test_X = test_df["review"]

# Target values, encoded and converted to a 1D numpy array
label_encoder = LabelEncoder()
label_encoder.fit(df["sentiment"])
dev_y = label_encoder.transform(dev_df["sentiment"])
test_y = label_encoder.transform(test_df["sentiment"])
# We can just create a preprocessor with a CountVectorizer in a pipeline with logistic regression.
logistic = Pipeline([
    ("vectorizer", CountVectorizer(stop_words='english', max_features=100)),
    ("predictor", LogisticRegression())])

# Get the validation error
np.mean(cross_val_score(logistic, dev_X, dev_y, scoring="accuracy", cv=ss))
# Instead of discarding features in the vectorizer, we can use TruncatedSVD for dimensionality reduction.
logistic = Pipeline([
    ("vectorizer", CountVectorizer(stop_words='english')),
    ("svd", TruncatedSVD(n_components=100)),
    ("predictor", LogisticRegression())])

# Get the validation error
np.mean(cross_val_score(logistic, dev_X, dev_y, scoring="accuracy", cv=ss))
# Let's try some grid search
logistic = Pipeline([
    ("vectorizer", CountVectorizer()),
    ("svd", TruncatedSVD()),
    ("predictor", LogisticRegression(max_iter=300))])

# Create a dictionary of hyperparameters for logistic regression
logistic_param_grid = {"vectorizer__stop_words": [None, "english"],
                       "vectorizer__ngram_range": [(1, 1), (1, 2)],
                       "svd__n_components": [100, 200]}

# Create the grid search object which will find the best hyperparameter values based on validation error
logistic_gs = GridSearchCV(logistic, logistic_param_grid, scoring="accuracy", cv=ss)

# Run grid search by calling fit
logistic_gs.fit(dev_X, dev_y)

# Let's see how well we did
logistic_gs.best_params_, logistic_gs.best_score_
# And let's try it with a TF-IDF vectorizer
tfidf_logistic = Pipeline([
    ("vectorizer", TfidfVectorizer()),
    ("svd", TruncatedSVD()),
    ("predictor", LogisticRegression(max_iter=300))])

# Create a dictionary of hyperparameters for logistic regression
tfidf_logistic_param_grid = {"vectorizer__stop_words": [None, "english"],
                             "vectorizer__ngram_range": [(1, 1), (1, 2)],
                             "svd__n_components": [100, 200]}

# Create the grid search object which will find the best hyperparameter values based on validation error
tfidf_logistic_gs = GridSearchCV(tfidf_logistic, tfidf_logistic_param_grid, scoring="accuracy", cv=ss)

# Run grid search by calling fit
tfidf_logistic_gs.fit(dev_X, dev_y)

# Let's see how well we did
tfidf_logistic_gs.best_params_, tfidf_logistic_gs.best_score_
# Now we re-train the winner on train+validation and test on the test set
tfidf_logistic.set_params(**tfidf_logistic_gs.best_params_) 
tfidf_logistic.fit(dev_X, dev_y)
accuracy_score(test_y, tfidf_logistic.predict(test_X))<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.07017453534469444, 'fraction_numerical': 0.01807135869845029, 'mean_word_length': 2.267283431455004, 'pattern_counts': {'":': 6, '<': 34, '<?xml version=': 0, '>': 38, 'https://': 1, 'lorem ipsum': 0, 'www.': 1, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 45, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '8', 'dir': 'jupyter-structured-clean-dedup', 'id': '526799', 'license': 'MIT', 'n_tokens_mistral': 5213, 'n_tokens_neox': 4930, 'n_words': 2154, 'path': 'ai2/lectures/AI2_01_bag_of_words.ipynb', 'repo_name': 'derekgbridge/artificial_intelligence', 'size': '19437'}