1

Natural Language Processing:

Natural language processing (NLP) uses computers to work with language. It's a big field, but we'll cover
some basic and advanced techniques.
Word Clouds
In Chapter 1, we counted users' interests. One way to visualize these counts is with word clouds, where
word size reflects frequency. However, data scientists don't usually value word clouds much because the
word placement is random and doesn't add meaning.

•If you have to create a word cloud, try to make the axes meaningful.
•For example, use data like how often a word appears in job postings versus on résumés to
add value.
data = [ ("big data", 100, 15), ("Hadoop", 95, 25), ("Python", 75,
50),
("R", 50, 40), ("machine learning", 80, 20), ("statistics", 20, 60),
("data science", 60, 70), ("analytics", 90, 3),
("team player", 85, 85), ("dynamic", 2, 90), ("synergies", 70, 0),
("actionable insights", 40, 30), ("think out of the box", 45, 10),
("self-starter", 30, 50), ("customer focus", 65, 15),
2
("thought leadership", 35, 35)]
This looks neat but doesn’t really tell us anything. A more interesting approach
might be to scatter them so that the horizontal position indicates posting popularity
and vertical position indicates resume popularity, which produces a visualization
that conveys a few insights (Figure 21-2):

3
from matplotlib import pyplot as plt
def text_size(total: int) -> float:
"""equals 8 if total is 0, 28 if total is 200"""
return 8 + total / 200 * 20
for word, job_popularity, resume_popularity in data:
[Link](job_popularity, resume_popularity, word,
ha='center', va='center',
size=text_size(job_popularity + resume_popularity))
[Link]("Popularity on Job Postings")
[Link]("Popularity on Resumes")
[Link]([0, 100, 0, 100])
[Link]([])
[Link]([])
[Link]()

4
n-Gram Language Models
•The VP of Search Engine Marketing wants to generate thousands of data science web pages to
boost search rankings, even though search engines can see through this tactic.
•She asks if you can programmatically create these pages instead of writing them manually or
hiring others to do it.
•To do this, you'll need a language model, which you can build using a collection of documents
like Mike Loukides's essay "What Is Data Science?" along with tools like the Requests and
Beautiful Soup libraries.
•The first is that the apostrophes in the text are actually the Unicode
character u"\u2019". We’ll create a helper function to replace them with
normal apostrophes:
def fix_unicode(text: str) -> str:
return [Link](u"\u2019", “’”) html = [Link](url).text
a sequence of words and periods (so that soup = BeautifulSoup(html, 'html5lib')
we can tell where sentences end). We can content = [Link]("div", "article-body")
do # find article-body div
this using [Link]: regex = r"[\w']+|[\.]" # matches a word
import re or a period
from bs4 import BeautifulSoup document = []
import requests for paragraph in content("p"):
5
url = "[Link] words = [Link](regex,
•We could clean the data more since there’s still some extra text and split sentences, but we'll
work with it as is.
•With the text as a sequence of words, we can model language by starting with a word (like
"book"), looking at what words follow it, and randomly choosing the next word until we reach a
period.
•This approach is called a bigram model, as it uses word pairs from the original text
•To choose a starting word, we can randomly pick from words that come after a period.
•First, let's precompute the possible word transitions. Using zip(document, document[1:])
Now we’re ready to generate sentences:
gives us all pairs of consecutive words in the document.
from collections import defaultdict def generate_using_bigrams() -> str:
transitions = defaultdict(list) current = "." # this means the next word
for prev, current in zip(document, document[1:]): will start a sentence
transitions[prev].append(current) result = []
while True: next_word_candidates =
transitions[current] # bigrams (current, _)
current =
[Link](next_word_candidates) #
choose one at random
[Link](current) # append it to 6
results
-The sentences it creates are nonsense, but they sound like something you'd write if you were trying to
sound technical or data-science-related. For instance:
-"If you want to sort data feeds on trending topics, Hadoop and Python can be used to visualize
massive correlations across many disk drives and make connections to solve data problems."
-This is an example generated by a Bigram Model, which combines pairs of words without
understanding context, leading to gibberish that superficially resembles technical language.
-We can make the sentences less nonsensical by using trigrams, which are groups of three consecutive
words. This way, each word depends on the two words before it, making the sentences more coherent.
trigram_transitions = defaultdict(list)
starts = []
for prev, current, next in zip(document,
document[1:], document[2:]): prev = "." # and precede it with a '.'
if prev == ".": # if the previous "word" result = [current]
was a period while True:
[Link](current) # then this is a next_word_candidates =
start word trigram_transitions[(prev, current)]
trigram_transitions[(prev, next_word =
current)].append(next) [Link](next_word_candidates)
Notice that now we have to track the starting prev, current = current, next_word
words separately. We can generate sentences in 7
pretty much the same way: [Link](current)
Grammars
-Grammars are rules for creating proper sentences. You likely learned about parts of speech in school
and how to combine them.
-For instance, a simple rule might be that a sentence must have a noun followed by a verb. With lists
of nouns and verbs, you can create sentences following this rule.
We’ll define a slightly more I made up the convention that names
complicated grammar: starting with underscores refer to
from typing import List, Dict rules that
# Type alias to refer to grammars -Some grammar rules need to be expanded further,
later while others, called terminals, don’t need more
Grammar = Dict[str, List[str]] processing.
grammar = { -For example, the "_S" rule stands for a "sentence"
"_S" : ["_NP _VP"], and breaks down into a "_NP" ("noun phrase")
"_NP" : ["_N", "_A _NP _P _A _N"], followed by a "_VP" ("verb phrase").
"_VP" : ["_V", "_V _NP"], -The verb phrase rule can either be just a "_V"
"_N" : ["data science", "Python", ("verb") or a verb followed by a noun phrase.
"regression"], -The "_NP" rule can also include itself, making the
"_A" : ["big", "linear", "logistic"], grammar recursive. This allows even a limited set of
"_P" : ["about", "near"], rules to create an infinite number of sentences.
8
"_V" : ["learns", "trains", "tests",
-Start with the sentence rule ["_S"] and expand it by replacing each rule with a randomly chosen option.
-Continue expanding until the list contains only terminals, meaning the sentence is complete.

For example, one such progression might look like:

['_S']
['_NP','_VP']
['_N','_VP']
['Python','_VP'] How do we implement this? Well,
['Python','_V','_NP'] to start, we’ll create a simple
['Python','trains','_NP'] helper function to identify
['Python','trains','_A','_NP','_P','_A','_N'] terminals:
['Python','trains','logistic','_NP','_P','_A','_N']def is_terminal(token: str) ->
['Python','trains','logistic','_N','_P','_A','_N'] bool:
return token[0] != "_"
['Python','trains','logistic','data science','_P','_A','_N']
['Python','trains','logistic','data science','about','_A', '_N']
['Python','trains','logistic','data science','about','logistic','_N']
['Python','trains','logistic','data
science','about','logistic','Python']
9
-We need to create a function to turn a list of tokens into a sentence. First, we search for the first
nonterminal token. If there isn’t one, the sentence is complete, and we’re done.
-If we find a nonterminal, we randomly choose one of its options. If that option is a terminal (a word),
we replace the token with it.
-If it's a sequence of nonterminal tokens, we split it and insert it into the list of tokens. We then repeat
the process with the updated tokens.
Putting it all together, we get:
def expand(grammar: Grammar,
tokens: List[str]) -> List[str]: # split it on spaces and splice it in.
for i, token in enumerate(tokens): tokens = tokens[:i] +
# If this is a terminal token, skip it. [Link]() + tokens[(i+1):]
if is_terminal(token): continue # Now call expand on the new list of
# Otherwise, it's a nonterminal token, tokens.
# so we need to choose areturn expand(grammar, tokens)
replacement at random. # If we get here, we had all terminals
replacement =and are done.
[Link](grammar[token]) return tokens
if is_terminal(replacement): And now we can start generating
tokens[i] = replacement sentences:
10
else: def generate_sentence(grammar:
An Aside: Gibbs Sampling
-Generating samples from some distributions is easy. We can get uniform random variables with:
[Link]()
and normal random variables with:
inverse_normal_cdf([Link]())
-But some distributions are harder to sample from. Gibbs sampling is a technique for generating
samples from multidimensional distributions when we only know some of the conditional
distributions.
-For example, imagine rolling two dice. Let x be the value of the first die and y be the sum of the dice,
and imagine you wanted to generate lots of (x, y) pairs. In this case it’s easy to generate the samples
directly:
from typing import Tuple conditional distributions. The
import random distribution of y conditional on x is
def roll_a_die() -> int: easy—if you know the value of x, y is
return [Link]([1, 2, 3, 4, 5, 6]) equally likely to be x + 1, x + 2, x +
def direct_sample() -> Tuple[int, int]: 3, x + 4, x + 5, or x + 6:
d1 = roll_a_die()
d2 = roll_a_die() def random_y_given_x(x: int) -> int:
return d1, d1 + d2 """equally likely to be x + 1,11 x +
The other direction is more complicated. -The way Gibbs sampling works is that
For example, we start with any (valid) values for x and
-if you know that y is 2, then necessarily y and
x is 1 (since the only way two dice can -then repeatedly alternate replacing x
sum to 2 is if both of them are 1). with a random value picked conditional
-If you know y is 3, then x is equally on yand replacing y with a random value
likely to be 1 or 2. Similarly, if y is 11, picked conditional on x.
then x has to be either 5 or 6: -After a number of iterations, the
def random_x_given_y(y: int) -> int: resulting values of x and y will represent
if y <= 7: a sample from the unconditional joint
# if the total is 7 or less, the first die is distribution:
equally likely to be
# 1, 2, ..., (total - 1) def gibbs_sample(num_iters: int = 100) -
return [Link](1, y) > Tuple[int, int]:
else: x, y = 1, 2 # doesn't really matter
# if the total is 7 or more, the first die is for _ in range(num_iters):
equally likely to be x = random_x_given_y(y)
# (total - 6), (total - 5), ..., 6 y = random_y_given_x(x)
return [Link](y - 6, 7) return x, y
. 12
You can check that this gives similar results to the direct sample:
def compare_distributions(num_samples: int = 1000) -> Dict[int, List[int]]:
counts = defaultdict(lambda: [0, 0])
for _ in range(num_samples):
counts[gibbs_sample()][0] += 1
counts[direct_sample()][1] += 1
return counts
We’ll use this technique in the next section

13
Topic modeling is a technique used to uncover the hidden themes or topics in a set of
documents. Instead of just matching exact words, topic modeling helps identify the broader topics that
the words represent.
One popular method for topic modeling is Latent Dirichlet Allocation (LDA). LDA assumes that:
[Link] is a fixed number of topics (K).
[Link] topic has a certain probability of generating specific words.
[Link] document has a mix of these topics, with certain probabilities for each.
[Link] every word in a document, the model first picks a topic based on the document's topic mix, and
then picks a word based on the chosen topic's word distribution.
In essence, LDA helps us discover the underlying topics that explain the content of documents, even
when those topics aren't explicitly stated.
So, the fifth word in the fourth document is:
documents[3][4]
and the topic from which that word was chosen is:
document_topics[3][4]
This very explicitly defines each document’s distribution over topics, and it
implicitly defines each topic’s distribution over words.
14
We can estimate the likelihood that topic 1 produces a certain word by
comparing how many times topic 1 produces that word with how many times
topic 1 produces any word.

-Although these topics are just numbers, we can give them descriptive
names by looking at the words on which they put the heaviest weight. We
just have to somehow generate the document_topics. This is where Gibbs
-We begin bycomes
sampling randomlyinto
assigning
play.a topic to every word in every document. Then, for each word in a
document, we calculate how likely each topic is based on two things:
[Link] current mix of topics in that document.
[Link] often that word appears in each topic.

-Using these likelihoods, we reassign the word to a new topic. We repeat this process many times.
Over time, the topics and word assignments will settle into patterns that represent the topics in the
documents more accurately.

15
To start with, we’ll need a function to randomly choose an index based on an
arbitrary set of weights:
def sample_from(weights: List[float]) -> int:
"""returns i with probability weights[i] / sum(weights)"""
total = sum(weights)
rnd = total * [Link]() # uniform between 0 and total
for i, w in enumerate(weights):
rnd -= w # return the smallest i such that
if rnd <= 0: return i # weights[0] + ... + weights[i] >= rnd
-For instance, if you give it weights [1, 1, 3], then one-fifth of the time it will return ,
one-fifth of the time it will return 1, and three-fifths of the time it will return 2.
Let’s write a test:
from collections import Counter
# Draw 1000 times and count
draws = Counter(sample_from([0.1, 0.1, 0.8]) for _ in range(1000))
assert 10 < draws[0] < 190 # should be ~10%, this is a really loose test
assert 10 < draws[1] < 190 # should be ~10%, this is a really loose test
assert 650 < draws[2] < 950 # should be ~80%, this is a really loose test
assert draws[0] + draws[1] + draws[2] == 1000 16
Our documents are our users’ interests, which look like:
documents = [
["Hadoop", "Big Data", "HBase", "Java", "Spark", "Storm", "Cassandra"],
["NoSQL", "MongoDB", "Cassandra", "HBase", "Postgres"],
["Python", "scikit-learn", "scipy", "numpy", "statsmodels", "pandas"],
["R", "Python", "statistics", "regression", "probability"],
["machine learning", "regression", "decision trees", "libsvm"],
["Python", "R", "Java", "C++", "Haskell", "programming languages"],
["statistics", "probability", "mathematics", "theory"],
["machine learning", "scikit-learn", "Mahout", "neural networks"],
["neural networks", "deep learning", "Big Data", "artificial intelligence"],
["Hadoop", "Java", "MapReduce", "Big Data"],
["statistics", "R", "statsmodels"],
["C++", "deep learning", "artificial intelligence", "probability"],
["pandas", "R", "Python"],
["databases", "HBase", "Postgres", "MySQL", "MongoDB"],
["libsvm", "regression", "support vector machines"]
]
And we’ll try to find: topics. In order to calculate the sampling weights,
K=4 we’ll need to keep track of several counts. 17Let’s
• How many times each topic is assigned to each document:
# a list of Counters, one for each document
document_topic_counts = [Counter() for _ in documents]
• How many times each word is assigned to each topic:
# a list of Counters, one for each topic
topic_word_counts = [Counter() for _ in range(K)]
• The total number of words assigned to each topic:
# a list of numbers, one for each topic
topic_counts = [0 for _ in range(K)]
• The total number of words contained in each document:
# a list of numbers, one for each document
document_lengths = [len(document) for document in documents]
• The number of distinct words:
distinct_words = set(word for document in documents for word in
document)
W = len(distinct_words)
• And the number of documents:
D = len(documents)
Once we populate these, we can find, for example, the number of words in
documents[3] associated with topic 1 as follows: document_topic_counts[3]
18
•The formula helps figure out how likely it is to choose a topic or a word.
•A small number is added to make sure that everything has at least a tiny chance of being picked.
•This way, nothing is completely left out.
def p_topic_given_document(topic: int, d: int, alpha: float = 0.1) -> float:
The fraction of words in document 'd'that are assigned to 'topic' (plus some
smoothing) """
return ((document_topic_counts[d][topic] + alpha) / (document_lengths[d] + K *
alpha))

def p_word_given_topic(word: str, topic: int, beta: float = 0.1) -> float:
"""The fraction of words assigned to 'topic’ that equal 'word' (plus some smoothing)
"""
return ((topic_word_counts[topic][word] + beta) / (topic_counts[topic] + W * beta))
We’ll use these to create the weights for updating topics:
def topic_weight(d: int, word: str, k: int) -> float:
""“ Given a document and a word in that document, return the weight for the kth
topic """
return p_word_given_topic(word,
•The formula k) *on
for topic_weight is based p_topic_given_document(k, d) details.
math, but we won't go into all the
def
•The choose_new_topic(d: int, word:
main idea is that the chance str) ->aint:
of picking topic depends on how likely the topic is for
return sample_from([topic_weight(d,
the document and how likely the word isword, k)topic.
for that
19
-What are the topics? They’re just numbers 0, 1, 2, and 3. If we want names
for them, we have to do that ourselves. Let’s look at the five most heavily
weighted words for each (Table 21-1):
for k, word_counts in enumerate(topic_word_counts):
for word, count in word_counts.most_common():
if count > 0:
print(k, word, count)

20
Word Vectors
• In recent advances in NLP, deep learning plays a big role. One key idea is representing words as low-
dimensional vectors.
•These word vectors can be compared, combined, and used in machine learning models. Similar words
usually have similar vectors. For example, the vector for "big" is close to the vector for "large," helping
models understand synonyms better.
•These vectors can also show interesting patterns. For example, if you take the vector for "king," subtract
the vector for "man," and add the vector for "woman," you get a vector close to "queen."
•Creating these vectors for many words is challenging, so we usually learn them from a large amount of
text. The basic steps are:
[Link] a lot of text.
[Link] a dataset where the goal is to predict a word based on nearby words (or vice versa).
[Link] a neural network to perform well on this task.
[Link] the internal states of the trained network as the word vectors.
-In particular, because the task is to predict a word given nearby words, words
that occur in similar contexts (and hence have similar nearby words) should have
similar internal states and therefore similar word vectors.
-Here we’ll measure “similarity” using cosine similarity, which is a number
between –1 and 1 that measures the degree to which two vectors point in the
same direction:
21
from scratch.linear_algebra import dot, Vector
import math
def cosine_similarity(v1: Vector, v2: Vector) -> float:
return dot(v1, v2) / [Link](dot(v1, v1) * dot(v2, v2))
assert cosine_similarity([1., 1, 1], [2., 2, 2]) == 1, "same direction"
assert cosine_similarity([-1., -1], [2., 2]) == -1, "opposite direction"
assert cosine_similarity([1., 0], [0., 1]) == 0, "orthogonal"
Let’s learn some word vectors to see how this works.
-To start with, we’ll need a toy dataset. The commonly used word vectors are
typically derived from training on millions or even billions of words. As our toy
library can’t cope with that much data, we’ll create an artificial dataset with some
structure to it:
colors = ["red", "green", "blue", "yellow", "black", ""] nouns = ["bed", "car",
"boat", "cat"]
verbs = ["is", "was", "seems"] adverbs = ["very", "quite", "extremely", ""]
adjectives = ["slow", "fast", "soft", "hard"]
def make_sentence() -> str:
return "
".join(["The",[Link](colors),[Link](nouns),[Link](verbs), 22
[Link](adverbs),[Link](adjectives),"."])
•This process creates many sentences with the same structure but different words, like
“The green boat seems quite slow.”
•Because of this, words like colors will often appear in similar contexts.
•If the word vectors are assigned well, similar words, like different colors, should end up
with similar vectors.

23
-As mentioned earlier, we’ll want to one-hot-encode our words, which means we’ll
need to convert them to IDs. We’ll introduce a Vocabulary class to keep track of this
mapping:
from scratch.deep_learning import Tensor
class Vocabulary:
def __init__(self, words: List[str] = None) -> None:
self.w2i: Dict[str, int] = {} # mapping word -> word_id
self.i2w: Dict[int, str] = {} # mapping word_id -> word
for word in (words or []): # If words were provided,
[Link](word) # add them. @property
def size(self) -> int:"""how many words are in the vocabulary"""
return len(self.w2i)
def add(self, word: str) -> None:
if word not in self.w2i: # If the word is new to us:
word_id = len(self.w2i) # Find the next id.
self.w2i[word] = word_id # Add to the word -> word_id map.
self.i2w[word_id] = word # Add to the word_id -> word map.
def get_id(self, word: str) -> int:"""return the id of the word (or None)"""
return [Link](word)
def get_word(self, word_id: int) -> str:"""return the word with the given 24id (or
def one_hot_encode(self, word: str) -> Tensor:
word_id = self.get_id(word)
assert word_id is not None, f"unknown word {word}"
return [1.0 if i == word_id else 0.0 for i in range([Link])]
These are all things we could do manually, but it’s handy to have it in a class. We
should probably test it:
vocab = Vocabulary(["a", "b", "c"])
assert [Link] == 3, "there are 3 words in the vocab"
assert vocab.get_id("b") == 1, "b should have word_id 1"
assert vocab.one_hot_encode("b") == [0, 1, 0]
assert vocab.get_id("z") is None, "z is not in the vocab"
assert vocab.get_word(2) == "c", "word_id 2 should be c"
[Link]("z")
assert [Link] == 4, "now there are 4 words in the vocab"
assert vocab.get_id("z") == 3, "now z should have id 3"
assert vocab.one_hot_encode("z") == [0, 0, 0, 1]

25
We can also extract the first two principal components and plot them:
from scratch.working_with_data import pca, transform
import [Link] as plt
# Extract the first two principal components and transform the word vectors
components = pca([Link], 2)
transformed = transform([Link], components)
# Scatter the points (and make them white so they're "invisible")
fig, ax = [Link]()
[Link](*zip(*transformed), marker='.', color='w')
# Add annotations for each word at its transformed location
for word, idx in [Link]():
[Link](word, transformed[idx])
# And hide the axes
ax.get_xaxis().set_visible(False)
ax.get_yaxis().set_visible(False)
[Link]()

26
Recurrent Neural Networks
•The word vectors we created earlier are often used as inputs to neural networks. But sentences
have different lengths, which can be a challenge.
•A 3-word sentence and a 10-word sentence have different dimensions, so we need to adjust for
this.
•One option is to sum or average the word vectors, but this ignores word order, which is
important for meaning. For example, “dog bites man” and “man bites dog” mean very different
things.
•Another approach is using Recurrent Neural Networks (RNNs). RNNs keep a hidden state that
updates with each new word, allowing the network to "remember" the order of words and their
context.
•We’ll build a simple RNN that takes one input at a time (like a word in a sentence) and keeps
track of the context as it processes the sentence.

27
-Recall that our Linear layer had some weights, w, and a bias, b. It took a vector input
and produced a different vector as output using the logic:
output[o] = dot(w[o], input) + b[o]
-Here we’ll want to incorporate our hidden state, so we’ll have two sets of weights—
one to apply to the input and one to apply to the previous hidden state:
output[o] = dot(w[o], input) + dot(u[o], hidden) + b[o]
-Next, we’ll use the output vector as the new value of hidden. This isn’t a huge
change, but it will allow our networks to do wonderful things.
from scratch.deep_learning import tensor_apply, tanh
class SimpleRnn(Layer): """Just about the simplest possible recurrent layer."""
def __init__(self, input_dim: int, hidden_dim: int) -> None:
self.input_dim = input_dim
self.hidden_dim = hidden_dim
self.w = random_tensor(hidden_dim, input_dim, init='xavier')
self.u = random_tensor(hidden_dim, hidden_dim, init='xavier')
self.b = random_tensor(hidden_dim)
self.reset_hidden_state()
def reset_hidden_state(self) -> None:
[Link] = [0 for _ in range(self.hidden_dim)]
You can see that we start out the hidden state as a vector of 0s, and we provide a function that people28using
the network can call to reset the hidden state.
-Given this setup, the forward -The backward pass is similar to the one in our Linear
function is reasonably layer, except that it needs to compute an additional
straightforward (at least, it is if set of gradients for the u weights:
you remember and understand def backward(self, gradient: Tensor):
how our Linear layer worked): # Backpropagate through the tanh
def forward(self, input: Tensor) - a_grad = [gradient[h] * (1 - [Link][h] ** 2)
> Tensor: for h in range(self.hidden_dim)]
[Link] = input # Save both # b has the same gradient as a
input and previous self.b_grad = a_grad
# Each w[h][i] is multiplied by input[i] and added to
self.prev_hidden = [Link] #
a[h],
hidden state to use in backprop. # so each w_grad[h][i] = a_grad[h] * input[i]
a = [(dot(self.w[h], input) + # self.w_grad = [[a_grad[h] * [Link][i]
weights @ input for i in range(self.input_dim)]
dot(self.u[h], [Link]) + # for h in range(self.hidden_dim)]
weights @ hidden # Each u[h][h2] is multiplied by hidden[h2] and added
self.b[h]) # bias to a[h],
for h in range(self.hidden_dim)] # so each u_grad[h][h2] = a_grad[h] *
[Link] = tensor_apply(tanh, prev_hidden[h2]
a) # Apply tanh activation self.u_grad = [[a_grad[h] * self.prev_hidden[h2]
return [Link] # and return for h2 in range(self.hidden_dim)]
the result. for h in range(self.hidden_dim)]
29
# Each input[i] is multiplied by every w[h][i] and
And finally we need to override the params and grads methods:
def params(self) -> Iterable[Tensor]:
return [self.w, self.u, self.b]
def grads(self) -> Iterable[Tensor]:
return [self.w_grad, self.u_grad, self.b_grad]

•The VP of Branding didn’t create the name "DataSciencester" and thinks a better name might
help the company.
•He asks you to use data science to find new name ideas.
•A fun way to do this is by using RNNs with characters as inputs. The RNN learns patterns in
the data and can then generate new, similar names.
•For example, you could train an RNN on the names of alternative bands, create new band
names, and pick the funniest ones to share online.

30
•You’ve seen this idea before but decide to try it out anyway.
•You find a list of the top 100 successful startups from Y Combinator, which seems like a good
place to start.
•The company names are easy to find on the webpage because they’re all inside certain tags.
You use web scraping to get the names with this code:
import requests
url = "[Link]
soup = BeautifulSoup([Link](url).text, 'html5lib')
# We get the companies twice, so use a set comprehension to deduplicate.
companies = list({[Link]
for b in soup("b")
if "h4" in [Link]("class", ())})
assert len(companies) == 101

31
•Note that the webpage might change, and if the code stops working, you can either fix it
using your data science skills or get the list from the book’s GitHub site.
•The plan is to train a model that predicts the next character of a company name based on
the current character and the characters it has already seen.
•The model will predict a probability for each possible next character and be trained to
minimize a specific loss function.
•After training, the model will generate probabilities for each character, pick one randomly
based on those probabilities, and then use it to generate new company names.
•To start, you’ll build a list of all the characters used in the company names:
vocab = Vocabulary([c for company in companies for c in company])

You’ll also use special tokens to mark the beginning and end of a company name, so the model
knows how to start and finish names. These tokens won’t appear in any company names, so
they’re safe to use:
START = "^"
STOP = "$"
# We need to add them to the vocabulary too.
32
[Link](START)
[Link](STOP)
For our model, we’ll one-hot-encode each character, pass it through two SimpleRnns,
and then use a Linear layer to generate the scores for each possible next character:
HIDDEN_DIM = 32 # You should experiment with different sizes!
rnn1 = SimpleRnn(input_dim=[Link], hidden_dim=HIDDEN_DIM)
rnn2 = SimpleRnn(input_dim=HIDDEN_DIM, hidden_dim=HIDDEN_DIM)
linear = Linear(input_dim=HIDDEN_DIM, output_dim=[Link])
model = Sequential([
rnn1,
rnn2,
linear
])

33
Imagine for the moment that we’ve trained this model. Let’s write the function that uses it
to generate new company names, using the sample_from function from “Topic Modeling”:
from scratch.deep_learning import softmax
def generate(seed: str = START, max_len: int = 50) -> str:
rnn1.reset_hidden_state() # Reset both hidden states
rnn2.reset_hidden_state()
output = [seed] # Start the output with the specified seed # Keep going until we produce
the STOP character or reach the max length
while output[-1] != STOP and len(output) < max_len:
# Use the last character as the input
input = vocab.one_hot_encode(output[-1])
# Generate scores using the model
predicted = [Link](input)
# Convert them to probabilities and draw a random char_id
probabilities = softmax(predicted)
next_char_id = sample_from(probabilities)
# Add the corresponding char to our output
[Link](vocab.get_word(next_char_id))
# Get rid of START and END characters and return the word
return ''.join(output[1:-1])
At long last, we’re ready to train our character-level RNN. It will take a while!
loss = SoftmaxCrossEntropy()
optimizer = Momentum(learning_rate=0.01, momentum=0.9)
for epoch in range(300): 34
[Link](companies) # Train in a different order each epoch.
epoch_loss = 0 # Track the loss.
for company in [Link](companies):
rnn1.reset_hidden_state() # Reset both hidden states.
rnn2.reset_hidden_state()
company = START + company + STOP # Add START and STOP characters.
# The rest is just our usual training loop, except that the inputs # and target are the one-hot-
encoded previous and next characters.
for prev, next in zip(company, company[1:]):
input = vocab.one_hot_encode(prev)
target = vocab.one_hot_encode(next)
predicted = [Link](input)
epoch_loss += [Link](predicted, target)
gradient = [Link](predicted, target)
[Link](gradient)
[Link](model)
# Each epoch, print the loss and also generate a name.
print(epoch, epoch_loss, generate())
# Turn down the learning rate for the last 100 epochs. # There's no principled
reason for this, but it seems to work. 35
if epoch == 200:
•After training, the model creates some real names from the list (which makes sense since
it has a lot of capacity but not much training data).
•It also generates names that are slightly different from the original ones (like Scripe,
Loinbare, Pozium), some creative names (like Benuus, Cletpo, Equite, Vivest), and some
random, word-like names (like SFitreasy, Sint ocanelp, GliyOx, Doorboronelhav).
•However, these names aren’t very impressive, so the VP of Branding can’t really use them.
•When I increased the model’s size, it mostly repeated names from the list. When I made it
smaller, it mostly produced random nonsense.
•You can find the vocabulary and weights for different model sizes on the book’s GitHub
site, and you can use them with load_weights and load_vocab.
•The GitHub code also includes an LSTM version, which you can try instead of the simple
RNN in the company name model.

36
Network Analysis
-Networks are made up of nodes (like points) connected by edges (like lines). For example, on Facebook,
each friend is a node, and the friendship between you and a friend is an edge. This type of connection is
undirected because if you’re friends with someone, they are also friends with you.
-Another example is the World Wide Web, where each webpage is a node and each hyperlink between
pages is an edge. Unlike Facebook, these links are directed because one page might link to another, but
the second page might not link back.
-We’ll explore both types of networks: undirected (like Facebook friendships) and directed (like web
links).
Betweenness Centrality
DataSciencester network by
counting the number of friends each user had. Now we have enough machinery to
take a look at other approaches. We will use the same network, but now we’ll use
NamedTuples for the data.
Recall that the network (Figure 22-1) comprised users:
from typing import NamedTuple
class User(NamedTuple):
id: int
name: str
37
users = [User(0, "Hero"), User(1, "Dunn"), User(2, "Sue"), User(3, "Chi"),
User(4, "Thor"), User(5, "Clive"), User(6, "Hicks"),
User(7, "Devin"), User(8, "Kate"), User(9, "Klein")]
and friendships:
friend_pairs = [(0, 1), (0, 2), (1, 2), (1, 3), (2, 3), (3, 4),
(4, 5), (5, 6), (5, 7), (6, 8), (7, 8), (8, 9)] The friendships will be easier
to work with as a dict:
from typing import Dict, List
# type alias for keeping track
of Friendships
Friendships = Dict[int,
List[int]]
friendships: Friendships =
{[Link]: [] for user in users}
for i, j in friend_pairs:
friendships[i].append(j)
friendships[j].append(i)
assert friendships[4] == [3, 5]
assert friendships[8] == [6, 7,
38
9]
We weren't happy with how degree centrality showed key connectors in a network.
-A better measure is betweenness centrality. It finds people who are often on the shortest paths
connecting other people. To calculate it for a person, like Thor, you look at all the shortest paths
between pairs of people (excluding Thor) and count how many of those paths go through Thor. For
example, if Thor is on many of these shortest paths, he has high betweenness centrality.
-The shortest path from Chi (id 3) to Clive (id 5) goes through Thor, but neither of the shortest paths
from Hero (id 0) to Chi (id 3) involves Thor.
-To find this out, we need to calculate the shortest paths between every pair of people. There are
advanced methods for this, but we’ll use a simpler, less efficient method that’s easier to understand.

39
We’ll use a breadth-first search algorithm to find the shortest paths from a starting user to
every other user. Here’s how it works:
[Link]: Create a function that finds the shortest paths from a starting user (from_user) to all other
users.
[Link] Representation: A path is a list of user IDs, but it doesn’t include the starting user’s ID. So,
the length of the list is the length of the path.
[Link] of Paths: Use a dictionary called shortest_paths_to where each key is a user ID and
the value is a list of all shortest paths to that user. If there’s only one shortest path, the list will have just that
path. If there are multiple shortest paths, the list will have all of them.
[Link]: Use a queue called frontier to explore users in order. The queue holds pairs of (previous user,
current user) so we know how we got to each user. Start by adding all neighbors of from_user to the
queue.
[Link]: As you explore, add new users you find to the queue if you don’t already have the
shortest paths to them, marking the current user as the previous user.
[Link] Users: When you pull a user from the queue for the first time, you’ve found the shortest
paths to them, adding one extra step from the previous user.
[Link] Users: If you pull a user from the queue that you’ve seen before, check if the new path
is shorter. If so, add it to your list. If it’s longer, ignore it.
[Link]: Continue until the queue is empty. At this point, you’ve explored all reachable parts of the
graph from the starting user. 40
We can put this all together into a (large)
function:
from collections import deque paths_to_prev_user =
Path = List[int] shortest_paths_to[prev_user_id]
def shortest_paths_from(from_user_id: int, new_paths_to_user = [path + [user_id] for
friendships: Friendships) -> Dict[int, path in paths_to_prev_user]
List[Path]]: # It's possible we already know a shortest
# A dictionary from user_id to *all* shortest path to user_id.
paths to that user. old_paths_to_user =
shortest_paths_to: Dict[int, List[Path]] = shortest_paths_to.get(user_id, [])
{from_user_id: [[]]} # What's the shortest path to here that
# A queue of (previous user, next user) that we've seen so far?
we need to check. if old_paths_to_user:
# Starts out with all pairs (from_user, min_path_length =
friend_of_from_user). len(old_paths_to_user[0])
frontier = deque((from_user_id, friend_id) else:
for friend_id in friendships[from_user_id]) min_path_length = float('inf')
# Keep going until we empty the queue. # Only keep paths that aren't too long and
while frontier: are actually new.
# Remove the pair that's next in the queue. new_paths_to_user = [path
prev_user_id, user_id = [Link]() for path in new_paths_to_user
# Because of the way we're adding to the if len(path) <= min_path_length
41
queue, # necessarily we already know some and path not in old_paths_to_user]
Now let’s compute all the shortest paths:
# For each from_user, for each to_user, a list of shortest paths.
shortest_paths = {[Link]: shortest_paths_from([Link], friendships)
for user in users}
-And we’re finally ready to compute betweenness centrality. For every pair
of nodes I and j, we know the n shortest paths from i to j. Then, for each of
those paths, we just add 1/n to the centrality of each node on that path:
betweenness_centrality = {[Link]: 0.0 for user in users}
for source in users:
for target_id, paths in shortest_paths[[Link]].items():
if [Link] < target_id: # don't double count
num_paths = len(paths) # how many shortest paths?
contrib = 1 / num_paths # contribution to centrality
for path in paths:
for between_id in path:
if between_id not in [[Link], target_id]:
betweenness_centrality[between_id] += contrib
-As shown in Figure 22-2, users 0 and 9 have centrality 0 (as neither is on
any shortest path between other users), whereas 3, 4, and 5 all have 42 high
-Another measure we can look at is closeness centrality. First, for each user we
compute her farness, which is the sum of the lengths of her shortest paths to each
other user. Since we’ve already computed the shortest paths between each pair of
nodes, it’s easy to add their lengths. (If there are multiple shortest paths, they all
have the same length,
def farness(user_id: so->
int) wefloat:
can just look at the first one.)
"""the sum of the lengths of the shortest paths to each other user"""
return sum(len(paths[0])
for paths in shortest_paths[user_id].values())
after which it’s very little work to compute closeness centrality (Figure 22-3):
closeness_centrality = {[Link]: 1 / farness([Link]) for user in users} 43
-There is much less variation here—even
the very central nodes are still pretty far
from the nodes out on the periphery.
-As we saw, computing shortest paths is
kind of a pain. For this reason,
betweenness and closeness centrality
aren’t often used on large networks. The
less intuitive (but generally easier to
compute) eigenvector centrality is more
frequently used.
44
Eigenvector Centrality
-In order to talk about eigenvector centrality, we have to talk about eigenvectors,
and in order to talk about eigenvectors, we have to talk about matrix multiplication.
-Matrix Multiplication
If A is an n × m matrix and B is an m × k matrix (notice that the second dimension of
A is same as the first dimension of B), then their product AB is the n × k matrix
whose (i,j)th entry is:
Ai1B1j + Ai2B2j + ⋯ + AimBmj
-which is just the dot product of the ith row of A (thought of as a vector) with the jth
column of B (also thought of as a vector).
-We can implement this using the make_matrix function from Chapter 4:
from scratch.linear_algebra import Matrix, make_matrix, shape
def matrix_times_matrix(m1: Matrix, m2: Matrix) -> Matrix:
nr1, nc1 = shape(m1)
nr2, nc2 = shape(m2)
assert nc1 == nr2, "must have (# of columns in m1) == (# of rows in m2)"
def entry_fn(i: int, j: int) -> float: """dot product of i-th row of m1 with j-th column of
m2"""
return sum(m1[i][k] * m2[k][j] for k in range(nc1))
return make_matrix(nr1, nc2, entry_fn) 45
-This means another way to think about an (n, m) matrix is as a linear mapping that
transforms m-dimensional vectors into n-dimensional vectors:
from scratch.linear_algebra import Vector, dot
def matrix_times_vector(m: Matrix, v: Vector) -> Vector:
nr, nc = shape(m)
n = len(v)
assert nc == n, "must have (# of cols in m) == (# of elements in v)"
return [dot(row, v) for row in m] # output has length nr
-When A is a square matrix, this operation maps n-dimensional vectors to other
ndimensional vectors. It’s possible that, for some matrix A and vector v, when A
operates on v we get back a scalar multiple of v—that is, that the result is a vector
that points in the same direction as v. When this happens (and when, in addition, v is
not a vector of all zeros), we call v an eigenvector of A. And we call the multiplier an
eigenvalue.

46
47
-One possible way to find an eigenvector of A is by picking a starting vector v,
applying matrix_times_vector, rescaling the result to have magnitude 1, and
repeating until the process converges:
from typing import Tuple
import random
from scratch.linear_algebra import magnitude, distance
def find_eigenvector(m: Matrix,
tolerance: float = 0.00001) -> Tuple[Vector, float]:
guess = [[Link]() for _ in m]
while True:
result = matrix_times_vector(m, guess) # transform guess
norm = magnitude(result) # compute norm
next_guess = [x / norm for x in result] # rescale
if distance(guess, next_guess) < tolerance:
# convergence so return (eigenvector, eigenvalue)
return next_guess, norm
guess = next_guess

48
-When you use the function to guess an eigenvector, it produces a vector that, when transformed by the
matrix and scaled to length 1, is very close to itself. This shows it's an eigenvector.
-Not all matrices have eigenvectors. For example, the matrix that rotates vectors 90 degrees clockwise
only maps vectors to zero, so you can’t find an eigenvector for it.
-Some matrices have eigenvectors but can cause problems. For instance, the matrix that swaps
coordinates will keep swapping coordinates forever for most vectors, but it does have eigenvectors.

-More advanced libraries like NumPy handle these cases differently.

-When the function does give a result, it’s an eigenvector.

49
Centrality
-How does this help us understand the DataSciencester network? To start, we’ll
need to represent the connections in our network as an adjacency_matrix, whose
(i,j)th entry is either 1 (if user i and user j are friends) or 0 (if they’re not):
def entry_fn(i: int, j: int):
return 1 if (i, j) in friend_pairs or (j, i) in friend_pairs else 0
n = len(users)
adjacency_matrix = make_matrix(n, n, entry_fn)
-The eigenvector centrality for each user is then the entry corresponding to that
user in the eigenvector returned by find_eigenvector (Figure 22-4).

50
Directed Graphs and PageRank
-DataSciencester isn’t getting much traction, so the VP of Revenue considers
pivoting from a friendship model to an endorsement model. It turns out that no one
particularly cares which data scientists are friends with one another, but tech
recruiters care very much which data scientists are respected by other data
scientists.
-In this new model, we’ll track endorsements (source, target) that no longer
represent a reciprocal relationship, but rather that source endorses target as an
awesome data scientist (Figure 22-5). We’ll need to account for this asymmetry:

endorsements = [(0, 1), (1, 0), (0, 2), (2,

0), (1, 2),
(2, 1), (1, 3), (2, 3), (3, 4), (5, 4),
(5, 6), (7, 5), (6, 8), (8, 7), (8, 9)]
-after which we can easily find the
most_endorsed data scientists and sell
that information to recruiters:
from collections import Counter
endorsement_counts = Counter(target
for source, target in endorsements) 51
-Counting endorsements can be easily manipulated by creating fake accounts or having friends
endorse each other.
-A better approach considers who is giving the endorsements. Endorsements from influential people
should be valued more.
-This idea is used in the PageRank algorithm by Google, which ranks websites based on links from
other websites and their links.
Here’s a simplified way PageRank works:
[Link] total PageRank in the network is 1.0 (or 100%).
[Link], this PageRank is evenly shared among all nodes.
[Link] step, most of a node’s PageRank is spread out to its outgoing links.
[Link] remaining PageRank is distributed evenly across all nodes.

52
import tqdm
def page_rank(users: List[User],
endorsements: List[Tuple[int, int]],
damping: float = 0.85,
num_iters: int = 100) -> Dict[int, float]:
# Compute how many people each person endorses
outgoing_counts = Counter(target for source, target in endorsements)
# Initially distribute PageRank evenly
num_users = len(users)
pr = {[Link] : 1 / num_users for user in users}
# Small fraction of PageRank that each node gets each iteration
base_pr = (1 - damping) / num_users
for iter in [Link](num_iters):
next_pr = {[Link] : base_pr for user in users} # start with base_pr
for source, target in endorsements:
# Add damped fraction of source pr to target
next_pr[target] += damping * pr[source] / outgoing_counts[source]
pr = next_pr
return pr
53
If we compute page ranks:
pr = page_rank(users, endorsements)
# Thor (user_id 4) has higher page rank than anyone else
assert pr[4] > max(page_rank
for user_id, page_rank in [Link]()
if user_id != 4)
PageRank (Figure 22-6) identifies user 4 (Thor) as the highest-ranked
data scientist.

-Even though Thor has fewer

endorsements (two) than users 0, 1,
and 2, his endorsements
carry with them rank from their
endorsements.
-Additionally, both of his endorsers
endorsed only him, which means
that he doesn’t have to divide their
rank with anyone else.
Recommender Systems
•A common data task is making suggestions for users.
•Netflix suggests movies you might enjoy.
•Amazon suggests products you might want to buy.
•Twitter suggests people you might want to follow.
•This chapter will explore different ways to use data for making these suggestions.
In particular, we’ll look at the dataset of
users_interests that we’ve used before: ["machine learning", "scikit-learn",
users_interests = [ "Mahout", "neural networks"],
["Hadoop", "Big Data", "HBase", "Java", ["neural networks", "deep learning", "Big
"Spark", "Storm", "Cassandra"], Data", "artificial intelligence"],
["NoSQL", "MongoDB", "Cassandra", ["Hadoop", "Java", "MapReduce", "Big
"HBase", "Postgres"], Data"],
["Python", "scikit-learn", "scipy", "numpy", ["statistics", "R", "statsmodels"],
"statsmodels", "pandas"], ["C++", "deep learning", "artificial
["R", "Python", "statistics", "regression", intelligence", "probability"],
"probability"], ["pandas", "R", "Python"],
["machine learning", "regression", ["databases", "HBase", "Postgres",
"decision trees", "libsvm"], "MySQL", "MongoDB"],
["Python", "R", "Java", "C++", "Haskell", ["libsvm", "regression", "support vector
"programming languages"] machines"]
55
["statistics", "probability", "mathematics", ]
Manual Curation:
•Before the internet, if you wanted book recommendations, you’d ask a librarian, who would suggest
books based on your interests.
•For a small platform like DataSciencester, you could manually recommend interests for each user.
•However, this method doesn’t work well for larger groups and is limited by your own knowledge and
creativity.
•Instead, let's explore how we can use data to make better recommendations.
Recommending What’s Popular
One easy approach is to simply recommend what’s popular:
from collections import Counter
popular_interests = Counter(interest
for user_interests in users_interests
for interest in user_interests)
which looks like:
[('Python', 4), ('R', 4), ('Java', 3),
('regression', 3), ('statistics', 3),
('probability', 3),# ...]

56
Having computed this, we can just suggest to a user the most popular
interests that
he’s not already interested in:
from typing import List, Tuple
def most_popular_new_interests(
user_interests: List[str],
max_results: int = 5) -> List[Tuple[str, int]]:
suggestions = [(interest, frequency)
for interest, frequency in popular_interests.most_common()
if interest not in user_interests]
return suggestions[:max_results]
So, if you are user 1, with interests:
["NoSQL", "MongoDB", "Cassandra", "HBase", "Postgres"]
then we’d recommend you:
[('Python', 4), ('R', 4), ('Java', 3), ('regression', 3), ('statistics', 3)]
If you are user 3, who’s already interested in many of those things, you’d
instead get:
[('Java', 3), of
•Saying, "Lots ('HBase',
people like3), ('BigsoData',
Python, maybe 3),
you should too," isn't very convincing.
•If a new user
('neural networks',
joins and we2), ('Hadoop',
don’t 2)] about them, this might be our best option.
know anything
•We can improve by recommending things based on what the user already likes. 57
User-Based Collaborative Filtering:
•One way to consider a user’s interests is by finding similar users and suggesting what they like.
•To do this, we need a way to measure how similar two users are. We'll use cosine similarity.
•Each user’s interests will be represented as a vector of 0s and 1s, where 1 means the user has that
interest and 0 means they don’t.
•Users with similar interests will have vectors that point in the same direction. A similarity score of 1
means identical interests, while 0 means no shared interests.
•The next step is to list all known interests, assign them indices, and sort them into a list. This will help
in creating the vectors.
unique_interests = sorted({interest
for user_interests in users_interests
for interest in user_interests})
This gives us a list that starts:
assert unique_interests[:6] == [
'Big Data',
'C++',
'Cassandra',
'HBase',
'Hadoop',
58
'Haskell',# ...]
-Next we want to produce an “interest” vector of 0s and 1s for each user.
We just need to iterate over the unique_interests list, substituting a 1 if the
user has each interest, and a 0 if not:
def make_user_interest_vector(user_interests: List[str]) -> List[int]:
""“ Given a list of interests, produce a vector whose ith element is 1 if
unique_interests[i] is in the list, 0 otherwise """
return [1 if interest in user_interests else 0 for interest in unique_interests]
-And now we can make a list of user interest vectors:
user_interest_vectors = [make_user_interest_vector(user_interests)
for user_interests in users_interests]
-Now user_interest_vectors[i][j] equals 1 if user i specified interest j, and 0
otherwise.
from [Link] import giveas us the similarity between
-Because we have a small dataset, it’s no problem to compute the pairwise
cosine_similarity users i and j:
similarities between all of our users:
user_similarities = # Users 0 and 9 share interests in
[[cosine_similarity(interest_vector_i, Hadoop, Java, and Big Data
interest_vector_j) assert 0.56 < user_similarities[0][9] <
for interest_vector_j in 0.58, "several shared interests"
user_interest_vectors] # Users 0 and 8 share only one
for interest_vector_i in interest: Big Data
59
user_interest_vectors] assert 0.18 < user_similarities[0][8] <
•User similarities: user_similarities[i] represents how similar user i is to every other user.
•We can create a function to find the users most similar to a given user.
•We'll exclude the user herself and any users with zero similarity.
•The results will be sorted from most similar to least similar.
def most_similar_users_to(user_id: int) -> List[Tuple[int, float]]:
pairs = [(other_user_id, similarity) # Find other
for other_user_id, similarity in # users with
enumerate(user_similarities[user_id]) # nonzero
if user_id != other_user_id and similarity > 0] # similarity.
return sorted(pairs, # Sort them
key=lambda pair: pair[-1], # most similar
reverse=True) # first.
For instance, if we call most_similar_users_to(0) we get:
[(9, 0.5669467095138409),
(1, 0.3380617018914066),
(8, 0.1889822365046136),
(13, 0.1690308509457033),
(5, 0.1543033499620919)] 60
-How do we use this to suggest new
interests to a user?
-For each interest, we can just add up the
user similarities of the other users
interested in it:
from collections import defaultdict
def user_based_suggestions(user_id: int, else:
include_current_interests: bool = False): return [(suggestion, weight)
# Sum up the similarities for suggestion, weight in suggestions
suggestions: Dict[str, float] = if suggestion not in
defaultdict(float) users_interests[user_id]]
for other_user_id, similarity
in most_similar_users_to(user_id): If we call user_based_suggestions(0),
for interest in the first several suggested interests
users_interests[other_user_id]: are:
suggestions[interest] += similarity [('MapReduce', 0.5669467095138409),
# Convert them to a sorted list ('MongoDB', 0.50709255283711),
suggestions = ('Postgres', 0.50709255283711),
sorted([Link](), ('NoSQL', 0.3380617018914066),
key=lambda pair: pair[-1], # weight ('neural networks',
61
•These suggestions seem good for someone interested in "Big Data" and databases. The
weights are just used to order the suggestions.
•This method doesn’t work well when there are too many items. In large spaces with many
interests, most users are very different from each other.
•For example, on a site like Amazon, where I've bought thousands of items over many years,
it's unlikely anyone has a purchase history like mine.
•So, even my "most similar" user might not be similar at all, and their purchases wouldn't make
good recommendations for me.

62
Item-Based Collaborative Filtering:
•Instead of comparing users, we can compare the interests themselves.
•We can suggest new interests to a user by finding interests similar to what they already like.
•To do this, we'll switch our user-interest matrix so that rows represent interests and columns represent
users.
interest_user_matrix = [[user_interest_vector[j]
for user_interest_vector in user_interest_vectors]
for j, _ in enumerate(unique_interests)]

Interest-User Matrix:
•Row j of interest_user_matrix is the same as column j of user_interest_matrix.
•It shows 1 for users who have that interest and 0 for those who don't.

-For example, unique_interests[0] is Big Data, and so

interest_user_matrix[0] is:
[1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0]
because users 0, 8, and 9 indicated interest in Big Data.

63
-We can now use cosine similarity again. If precisely the same users are
interested in two topics, their similarity will be 1. If no two users are
interested in both topics, their similarity will be 0:

interest_similarities = [[cosine_similarity(user_vector_i, user_vector_j)

for user_vector_j in interest_user_matrix]
for user_vector_i in interest_user_matrix]

-For example, we can find the interests most similar to Big Data (interest 0)
using: [('Hadoop',
def most_similar_interests_to(interest_id: int):0.8164965809277261),
similarities = interest_similarities[interest_id]
('Java', 0.6666666666666666),
pairs = [(unique_interests[other_interest_id],('MapReduce',
similarity)
0.5773502691896258),
for other_interest_id, similarity in enumerate(similarities)
('Spark',
if interest_id != other_interest_id and similarity > 0] 0.5773502691896258),
return sorted(pairs, ('Storm', 0.5773502691896258),
key=lambda pair: pair[-1], ('Cassandra',
reverse=True) 0.4082482904638631),
which suggests the following similar interests: ('artificial intelligence',
0.4082482904638631), 64
Now we can create recommendations
for a user by summing up the
similarities of the interests similar to
his:
def item_based_suggestions(user_id:
int,
include_current_interests: bool = if include_current_interests:
False): return suggestions
# Add up the similar interests else:
suggestions = defaultdict(float) return [(suggestion, weight)
user_interest_vector = for suggestion, weight in
user_interest_vectors[user_id] suggestions
for interest_id, is_interested in if suggestion not in
enumerate(user_interest_vector): users_interests[user_id]]
if is_interested == 1: For user 0, this generates the
similar_interests = following (seemingly reasonable)
most_similar_interests_to(interest_id recommendations:
) [('MapReduce', 1.861807319565799),
for interest, similarity in ('Postgres', 1.3164965809277263),
('MongoDB', 1.3164965809277263), 65
similar_interests:
('NoSQL', 1.2844570503761732),
Matrix Factorization:
•We can represent users' preferences with a matrix where 1 means they like an item and 0 means they don’t.
•If users give numeric ratings (like 1 to 5 stars), we use a matrix with these ratings instead.
•In this section, we’ll assume we have such ratings and aim to build a model to predict ratings for any user-
item pair.
•One approach is to assume users and items each have some hidden features, or “types,” represented by
vectors.
•We’ll create two matrices: one for user types and one for item types. Their product will approximate the
original ratings matrix.
•For example, with the MovieLens 100k dataset, which includes ratings for many movies by many users, we
can build a system to predict ratings for any (user, movie) pair.
•Download the dataset from here to get started.
[Link]
Unzip it and extract the files; we’ll only use two of them:
# This points to the current directory, modify if your files are elsewhere.
MOVIES = "[Link]" # pipe-delimited: movie_id|title|...
RATINGS = "[Link]" # tab-delimited: user_id, movie_id, rating, timestamp
As is often the case, we’ll introduce a NamedTuple to make things easier to work with:
from typing import NamedTuple
class Rating(NamedTuple):
user_id: str
movie_id: str
rating: float
66
-Now let’s read in the data and explore it. The movies file is pipe-delimited and has
many columns. We only care about the first two, which are the ID and the title:
import csv
# We specify this encoding to avoid a UnicodeDecodeError.
# See: [Link]
with open(MOVIES, encoding="iso-8859-1") as f:
reader = [Link](f, delimiter="|")
movies = {movie_id: title for movie_id, title, *_ in reader}
-The ratings file is tab-delimited and contains four columns for user_id, movie_id,
rating (1 to 5), and timestamp. We’ll ignore the timestamp, as we don’t need it:
# Create a list of [Rating]
with open(RATINGS, encoding="iso-8859-1") as f:
reader = [Link](f, delimiter="\t")
ratings = [Rating(user_id, movie_id, float(rating))
for user_id, movie_id, rating, _ in reader]
# 1682 movies rated by 943 users
assert len(movies) == 1682
assert len(list({rating.user_id for rating in ratings})) == 943
67
-There’s a lot of interesting exploratory analysis you can do on this data; for instance,
you might be interested in the average ratings for Star Wars movies (the dataset is
from 1998, which means it predates The Phantom Menace by a year):
import re
# Data structure for accumulating ratings by movie_id
star_wars_ratings = {movie_id: []
for movie_id, title in [Link]()
if [Link]("Star Wars|Empire Strikes|Jedi", title)}
# Iterate over ratings, accumulating the Star Wars ones
for rating in ratings:
They’re all pretty highly
if rating.movie_id in star_wars_ratings:
rated:
star_wars_ratings[rating.movie_id].append([Link] 4.36 Star Wars (1977)
g) 4.20 Empire Strikes Back,
# Compute the average rating for each movie The (1980)
avg_ratings = [(sum(title_ratings) / len(title_ratings), 4.01 Return of the Jedi
movie_id) (1983)
for movie_id, title_ratings in star_wars_ratings.items()] 68
# And then print them in order
for avg_rating, movie_id in sorted(avg_ratings,
reverse=True):
-So let’s try to come up with a model to predict these ratings. As a first step, let’s
split the ratings data into train, validation, and test sets:
import random
[Link](0)
[Link](ratings)
split1 = int(len(ratings) * 0.7)
split2 = int(len(ratings) * 0.85)
train = ratings[:split1] # 70% of the data
validation = ratings[split1:split2] # 15% of the data
test = ratings[split2:] # 15% of the data
-It’s always good to have a simple baseline model and make sure that ours
does better than that. Here a simple baseline model might be “predict the
average rating.” We’ll be using mean squared error as our metric, so let’s see
how the baseline does on our test set:
avg_rating = sum([Link] for rating in train) / len(train)
baseline_error = sum(([Link] - avg_rating) ** 2
for rating in test) / len(test)
# This is what we hope to do better than
assert 1.26 < baseline_error < 1.27
-Given our embeddings, the predicted ratings are given by the matrix product
69
of the user embeddings and the movie embeddings. For a given user and