Starting from:
$26.99
Anomaly Detection and Recommender Systems_Assignment 8
Programming Exercise 8:
Anomaly Detection and Recommender
Systems
1 Anomaly detection
In this exercise, you will implement an anomaly detection algorithm to detect
anomalous behavior in server computers. The features measure the through-
put (mb/s) and latency (ms) of response of each server. While your servers
were operating, you collected m = 307 examples of how they were behaving,
2
and thus have an unlabeled dataset fx(1); : : : ; x(m)g. You suspect that the
vast majority of these examples are \normal" (non-anomalous) examples of
the servers operating normally, but there might also be some examples of
servers acting anomalously within this dataset.
You will use a Gaussian model to detect anomalous examples in your
dataset. You will rst start on a 2D dataset that will allow you to visualize
what the algorithm is doing. On that dataset you will t a Gaussian dis-
tribution and then nd values that have very low probability and hence can
be considered anomalies. After that, you will apply the anomaly detection
algorithm to a larger dataset with many dimensions. You will be using ex8.m
for this part of the exercise.
The rst part of ex8.m will visualize the dataset as shown in Figure 1.
0 5 10 15 20 25 30
0
5
10
15
20
25
30
Latency (ms)
Throughput (mb/s)
Figure 1: The rst dataset.
1.1 Gaussian distribution
To perform anomaly detection, you will rst need to t a model to the data's
distribution.
Given a training set fx(1); :::; x(m)g (where x(i) 2 Rn), you want to esti-
mate the Gaussian distribution for each of the features xi. For each feature
i = 1 : : : n, you need to nd parameters i and 2
i that t the data in the
i-th dimension fx(1)
i ; :::; x(m)
i g (the i-th dimension of each example).
3
The Gaussian distribution is given by
p(x; ; 2) =
1
p
22
e(x)2
22 ;
where is the mean and 2 controls the variance.
1.2 Estimating parameters for a Gaussian
You can estimate the parameters, (i, 2
i ), of the i-th feature by using the
following equations. To estimate the mean, you will use:
i =
1
m
Xm
j=1
x(j)
i ; (1)
and for the variance you will use:
2
i =
1
m
Xm
j=1
(x(j)
i i)2: (2)
Your task is to complete the code in estimateGaussian.m. This function
takes as input the data matrix X and should output an n-dimension vector
mu that holds the mean of all the n features and another n-dimension vector
sigma2 that holds the variances of all the features. You can implement this
using a for-loop over every feature and every training example (though a vec-
torized implementation might be more ecient; feel free to use a vectorized
implementation if you prefer). Note that in Octave, the var function will
(by default) use 1
m1 , instead of 1
m, when computing 2
i .
Once you have completed the code in estimateGaussian.m, the next
part of ex8.m will visualize the contours of the tted Gaussian distribution.
You should get a plot similar to Figure 2. From your plot, you can see that
most of the examples are in the region with the highest probability, while
the anomalous examples are in the regions with lower probabilities.
You should now submit your estimate Gaussian parameters function.
1.3 Selecting the threshold, "
Now that you have estimated the Gaussian parameters, you can investigate
which examples have a very high probability given this distribution and which
examples have a very low probability. The low probability examples are
4
0 5 10 15 20 25 30
0
5
10
15
20
25
30
Latency (ms)
Throughput (mb/s)
Figure 2: The Gaussian distribution contours of the distribution t to the
dataset.
more likely to be the anomalies in our dataset. One way to determine which
examples are anomalies is to select a threshold based on a cross validation
set. In this part of the exercise, you will implement an algorithm to select
the threshold " using the F1 score on a cross validation set.
You should now complete the code in selectThreshold.m. For this, we
will use a cross validation set f(x(1)
cv ; y(1)
cv ); : : : ; (x(mcv)
cv ; y(mcv)
cv )g, where the la-
bel y = 1 corresponds to an anomalous example, and y = 0 corresponds
to a normal example. For each cross validation example, we will com-
pute p(x(i)
cv ). The vector of all of these probabilities p(x(1)
cv ); : : : ; p(x
(mcv)
cv ) is
passed to selectThreshold.m in the vector pval. The corresponding labels
y(1)
cv ; : : : ; y
(mcv)
cv is passed to the same function in the vector yval.
The function selectThreshold.m should return two values; the rst is
the selected threshold ". If an example x has a low probability p(x) < ",
then it is considered to be an anomaly. The function should also return the
F1 score, which tells you how well you're doing on nding the ground truth
anomalies given a certain threshold. For many di erent values of ", you will
compute the resulting F1 score by computing how many examples the current
threshold classi es correctly and incorrectly.
The F1 score is computed using precision (prec) and recall (rec):
F1 =
2 prec rec
prec + rec
; (3)
5
You compute precision and recall by:
prec =
tp
tp + fp
(4)
rec =
tp
tp + fn
; (5)
where
tp is the number of true positives: the ground truth label says it's an
anomaly and our algorithm correctly classi ed it as an anomaly.
fp is the number of false positives: the ground truth label says it's not
an anomaly, but our algorithm incorrectly classi ed it as an anomaly.
fn is the number of false negatives: the ground truth label says it's an
anomaly, but our algorithm incorrectly classi ed it as not being anoma-
lous.
In the provided code selectThreshold.m, there is already a loop that
will try many di erent values of " and select the best " based on the F1 score.
You should now complete the code in selectThreshold.m. You can im-
plement the computation of the F1 score using a for-loop over all the cross
validation examples (to compute the values tp, fp, fn). You should see a
value for epsilon of about 8.99e-05.
Implementation Note: In order to compute tp, fp and fn, you may
be able to use a vectorized implementation rather than loop over all the
examples. This can be implemented by Octave's equality test between a
vector and a single number. If you have several binary values in an n-
dimensional binary vector v 2 f0; 1gn, you can nd out how many values
in this vector are 0 by using: sum(v == 0). You can also apply a logical
and operator to such binary vectors. For instance, let cvPredictions be
a binary vector of the size of your number of cross validation set, where
the i-th element is 1 if your algorithm considers x(i)
cv an anomaly, and
0 otherwise. You can then, for example, compute the number of false
positives using: fp = sum((cvPredictions == 1) & (yval == 0)).
Once you have completed the code in selectThreshold.m, the next step
in ex8.m will run your anomaly detection code and circle the anomalies in
the plot (Figure 3).
You should now submit your select threshold function.
6
0 5 10 15 20 25 30
0
5
10
15
20
25
30
Latency (ms)
Throughput (mb/s)
Figure 3: The classi ed anomalies.
1.4 High dimensional dataset
The last part of the script ex8.m will run the anomaly detection algorithm
you implemented on a more realistic and much harder dataset. In this
dataset, each example is described by 11 features, capturing many more
properties of your compute servers.
The script will use your code to estimate the Gaussian parameters (i and
2
i ), evaluate the probabilities for both the training data X from which you
estimated the Gaussian parameters, and do so for the the cross-validation
set Xval. Finally, it will use selectThreshold to nd the best threshold ".
You should see a value epsilon of about 1.38e-18, and 117 anomalies found.
2 Recommender Systems
In this part of the exercise, you will implement the collaborative ltering
learning algorithm and apply it to a dataset of movie ratings.1 This dataset
consists of ratings on a scale of 1 to 5. The dataset has nu = 943 users, and
nm = 1682 movies. For this part of the exercise, you will be working with
the script ex8 cofi.m.
1MovieLens 100k Dataset from GroupLens Research.
7
In the next parts of this exercise, you will implement the function cofiCostFunc.m
that computes the collaborative tlering objective function and gradient. Af-
ter implementing the cost function and gradient, you will use fmincg.m to
learn the parameters for collaborative ltering.
2.1 Movie ratings dataset
The rst part of the script ex8 cofi.m will load the dataset ex8 movies.mat,
providing the variables Y and R in your Octave environment.
The matrix Y (a num movies num users matrix) stores the ratings y(i;j)
(from 1 to 5). The matrix R is an binary-valued indicator matrix, where
R(i; j) = 1 if user j gave a rating to movie i, and R(i; j) = 0 otherwise. The
objective of collaborative ltering is to predict movie ratings for the movies
that users have not yet rated, that is, the entries with R(i; j) = 0. This will
allow us to recommend the movies with the highest predicted ratings to the
user.
To help you understand the matrix Y, the script ex8 cofi.m will compute
the average movie rating for the rst movie (Toy Story) and output the
average rating to the screen.
Throughout this part of the exercise, you will also be working with the
matrices, X and Theta:
X =
2
6664
| (x(1))T |
| (x(2))T |
...
| (x(nm))T |
3
7775
; Theta =
2
6664
| ((1))T |
| ((2))T |
...
| ((nu))T |
3
7775
:
The i-th row of X corresponds to the feature vector x(i) for the i-th movie,
and the j-th row of Theta corresponds to one parameter vector (j), for the
j-th user. Both x(i) and (j) are n-dimensional vectors. For the purposes of
this exercise, you will use n = 100, and therefore, x(i) 2 R100 and (j) 2 R100.
Correspondingly, X is a nm 100 matrix and Theta is a nu 100 matrix.
2.2 Collaborative ltering learning algorithm
Now, you will start implementing the collaborative ltering learning algo-
rithm. You will start by implementing the cost function (without regulariza-
tion).
The collaborative ltering algorithm in the setting of movie recommen-
dations considers a set of n-dimensional parameter vectors x(1); :::; x(nm) and
8
(1); :::; (nu), where the model predicts the rating for movie i by user j as
y(i;j) = ((j))T x(i). Given a dataset that consists of a set of ratings produced
by some users on some movies, you wish to learn the parameter vectors
x(1); :::; x(nm); (1); :::; (nu) that produce the best t (minimizes the squared
error).
You will complete the code in cofiCostFunc.m to compute the cost func-
tion and gradient for collaborative ltering. Note that the parameters to the
function (i.e., the values that you are trying to learn) are X and Theta. In
order to use an o -the-shelf minimizer such as fmincg, the cost function has
been set up to unroll the parameters into a single vector params. You had
previously used the same vector unrolling method in the neural networks
programming exercise.
2.2.1 Collaborative ltering cost function
The collaborative ltering cost function (without regularization) is given by
J(x(1); :::; x(nm); (1); :::; (nu)) =
1
2
X
(i;j):r(i;j)=1
(((j))T x(i) y(i;j))2:
You should now modify cofiCostFunc.m to return this cost in the vari-
able J. Note that you should be accumulating the cost for user j and movie
i only if R(i; j) = 1.
After you have completed the function, the script ex8 cofi.m will run
your cost function. You should expect to see an output of 22:22.
You should now submit your cost function.
9
Implementation Note: We strongly encourage you to use a vectorized
implementation to compute J, since it will later by called many times
by the optimization package fmincg. As usual, it might be easiest to
rst write a non-vectorized implementation (to make sure you have the
right answer), and the modify it to become a vectorized implementation
(checking that the vectorization steps don't change your algorithm's out-
put). To come up with a vectorized implementation, the following tip
might be helpful: You can use the R matrix to set selected entries to 0.
For example, R .* M will do an element-wise multiplication between M
and R; since R only has elements with values either 0 or 1, this has the
e ect of setting the elements of M to 0 only when the corresponding value
in R is 0. Hence, sum(sum(R.*M)) is the sum of all the elements of M for
which the corresponding element in R equals 1.
2.2.2 Collaborative ltering gradient
Now, you should implement the gradient (without regularization). Speci -
cally, you should complete the code in cofiCostFunc.m to return the vari-
ables X grad and Theta grad. Note that X grad should be a matrix of the
same size as X and similarly, Theta grad is a matrix of the same size as
Theta. The gradients of the cost function is given by:
@J
@x(i)
k
=
X
j:r(i;j)=1
(((j))T x(i) y(i;j))(j)
k
@J
@(j)
k
=
X
i:r(i;j)=1
(((j))T x(i) y(i;j))x(i)
k :
Note that the function returns the gradient for both sets of variables
by unrolling them into a single vector. After you have completed the code
to compute the gradients, the script ex8 cofi.m will run a gradient check
(checkCostFunction) to numerically check the implementation of your gra-
dients.2 If your implementation is correct, you should nd that the analytical
and numerical gradients match up closely.
You should now submit your collaborative ltering gradient function.
2This is similar to the numerical check that you used in the neural networks exercise.
10
Implementation Note: You can get full credit for this assignment
without using a vectorized implementation, but your code will run much
more slowly (a small number of hours), and so we recommend that you
try to vectorize your implementation.
To get started, you can implement the gradient with a for-loop over movies
(for computing @J
@x(i)
k
) and a for-loop over users (for computing @J
@(j)
k
). When
you rst implement the gradient, you might start with an unvectorized
version, by implementing another inner for-loop that computes each ele-
ment in the summation. After you have completed the gradient computa-
tion this way, you should try to vectorize your implementation (vectorize
the inner for-loops), so that you're left with only two for-loops (one for
looping over movies to compute @J
@x(i)
k
for each movie, and one for looping
over users to compute @J
@(j)
k
for each user).
11
Implementation Tip: To perform the vectorization, you might nd this
helpful: You should come up with a way to compute all the derivatives
associated with x(i)
1 ; x(i)
2 ; : : : ; x(i)
n (i.e., the derivative terms associated with
the feature vector x(i)) at the same time. Let us de ne the derivatives for
the feature vector of the i-th movie as:
(Xgrad(i; :))T =
2
66664
@J
@x(i)
1
@J
@x(i)
2...
@J
@x(i)
n
3
77775
=
X
j:r(i;j)=1
(((j))T x(i) y(i;j))(j)
To vectorize the above expression, you can start by indexing into
Theta and Y to select only the elements of interests (that is, those with
r(i; j) = 1). Intuitively, when you consider the features for the i-th movie,
you only need to be concern about the users who had given ratings to the
movie, and this allows you to remove all the other users from Theta and Y.
Concretely, you can set idx = find(R(i, :)==1) to be a list of all the
users that have rated movie i. This will allow you to create the temporary
matrices Thetatemp = Theta(idx; :) and Ytemp = Y(i; idx) that index into
Theta and Y to give you only the set of users which have rated the i-th
movie. This will allow you to write the derivatives as:
Xgrad(i; :) = (X(i; :) ThetaT
temp Ytemp) Thetatemp:
(Note: The vectorized computation above returns a row-vector instead.)
After you have vectorized the computations of the derivatives with respect
to x(i), you should use a similar method to vectorize the derivatives with
respect to (j) as well.
2.2.3 Regularized cost function
The cost function for collaborative ltering with regularization is given by
12
J(x(1); :::; x(nm); (1); :::; (nu)) =
1
2
X
(i;j):r(i;j)=1
(((j))T x(i) y(i;j))2+
2
Xnu
j=1
Xn
k=1
((j)
k )2
!
+
2
Xnm
i=1
Xn
k=1
(x(i)
k )2
!
:
You should now add regularization to your original computations of the
cost function, J. After you are done, the script ex8 cofi.m will run your
regularized cost function, and you should expect to see a cost of about 31.34.
You should now submit your regularized cost function.
2.2.4 Regularized gradient
Now that you have implemented the regularized cost function, you should
proceed to implement regularization for the gradient. You should add to
your implementation in cofiCostFunc.m to return the regularized gradient
by adding the contributions from the regularization terms. Note that the
gradients for the regularized cost function is given by:
@J
@x(i)
k
=
X
j:r(i;j)=1
(((j))T x(i) y(i;j))(j)
k + x(i)
k
@J
@(j)
k
=
X
i:r(i;j)=1
(((j))T x(i) y(i;j))x(i)
k + (j)
k :
This means that you just need to add x(i) to the X grad(i,:) variable
described earlier, and add (j) to the Theta grad(j,:) variable described
earlier.
After you have completed the code to compute the gradients, the script
ex8 cofi.m will run another gradient check (checkCostFunction) to numer-
ically check the implementation of your gradients.
You should now submit the regularized gradient function.
2.3 Learning movie recommendations
After you have nished implementing the collaborative ltering cost function
and gradient, you can now start training your algorithm to make movie
13
recommendations for yourself. In the next part of the ex8 cofi.m script,
you can enter your own movie preferences, so that later when the algorithm
runs, you can get your own movie recommendations! We have lled out
some values according to our own preferences, but you should change this
according to your own tastes. The list of all movies and their number in the
dataset can be found listed in the le movie idx.txt.
2.3.1 Recommendations
Top recommendations for you:
Predicting rating 9.0 for movie Titanic (1997)
Predicting rating 8.9 for movie Star Wars (1977)
Predicting rating 8.8 for movie Shawshank Redemption, The (1994)
Predicting rating 8.5 for movie As Good As It Gets (1997)
Predicting rating 8.5 for movie Good Will Hunting (1997)
Predicting rating 8.5 for movie Usual Suspects, The (1995)
Predicting rating 8.5 for movie Schindler's List (1993)
Predicting rating 8.4 for movie Raiders of the Lost Ark (1981)
Predicting rating 8.4 for movie Empire Strikes Back, The (1980)
Predicting rating 8.4 for movie Braveheart (1995)
Original ratings provided:
Rated 4 for Toy Story (1995)
Rated 3 for Twelve Monkeys (1995)
Rated 5 for Usual Suspects, The (1995)
Rated 4 for Outbreak (1995)
Rated 5 for Shawshank Redemption, The (1994)
Rated 3 for While You Were Sleeping (1995)
Rated 5 for Forrest Gump (1994)
Rated 2 for Silence of the Lambs, The (1991)
Rated 4 for Alien (1979)
Rated 5 for Die Hard 2 (1990)
Rated 5 for Sphere (1998)
Figure 4: Movie recommendations
After the additional ratings have been added to the dataset, the script
will proceed to train the collaborative ltering model. This will learn the
parameters X and Theta. To predict the rating of movie i for user j, you need
14
to compute ((j))T x(i). The next part of the script computes the ratings for
all the movies and users and displays the movies that it recommends (Figure
4), according to ratings that were entered earlier in the script. Note that
you might obtain a di erent set of the predictions due to di erent random
initializations.
Anomaly Detection and Recommender
Systems
1 Anomaly detection
In this exercise, you will implement an anomaly detection algorithm to detect
anomalous behavior in server computers. The features measure the through-
put (mb/s) and latency (ms) of response of each server. While your servers
were operating, you collected m = 307 examples of how they were behaving,
2
and thus have an unlabeled dataset fx(1); : : : ; x(m)g. You suspect that the
vast majority of these examples are \normal" (non-anomalous) examples of
the servers operating normally, but there might also be some examples of
servers acting anomalously within this dataset.
You will use a Gaussian model to detect anomalous examples in your
dataset. You will rst start on a 2D dataset that will allow you to visualize
what the algorithm is doing. On that dataset you will t a Gaussian dis-
tribution and then nd values that have very low probability and hence can
be considered anomalies. After that, you will apply the anomaly detection
algorithm to a larger dataset with many dimensions. You will be using ex8.m
for this part of the exercise.
The rst part of ex8.m will visualize the dataset as shown in Figure 1.
0 5 10 15 20 25 30
0
5
10
15
20
25
30
Latency (ms)
Throughput (mb/s)
Figure 1: The rst dataset.
1.1 Gaussian distribution
To perform anomaly detection, you will rst need to t a model to the data's
distribution.
Given a training set fx(1); :::; x(m)g (where x(i) 2 Rn), you want to esti-
mate the Gaussian distribution for each of the features xi. For each feature
i = 1 : : : n, you need to nd parameters i and 2
i that t the data in the
i-th dimension fx(1)
i ; :::; x(m)
i g (the i-th dimension of each example).
3
The Gaussian distribution is given by
p(x; ; 2) =
1
p
22
e(x)2
22 ;
where is the mean and 2 controls the variance.
1.2 Estimating parameters for a Gaussian
You can estimate the parameters, (i, 2
i ), of the i-th feature by using the
following equations. To estimate the mean, you will use:
i =
1
m
Xm
j=1
x(j)
i ; (1)
and for the variance you will use:
2
i =
1
m
Xm
j=1
(x(j)
i i)2: (2)
Your task is to complete the code in estimateGaussian.m. This function
takes as input the data matrix X and should output an n-dimension vector
mu that holds the mean of all the n features and another n-dimension vector
sigma2 that holds the variances of all the features. You can implement this
using a for-loop over every feature and every training example (though a vec-
torized implementation might be more ecient; feel free to use a vectorized
implementation if you prefer). Note that in Octave, the var function will
(by default) use 1
m1 , instead of 1
m, when computing 2
i .
Once you have completed the code in estimateGaussian.m, the next
part of ex8.m will visualize the contours of the tted Gaussian distribution.
You should get a plot similar to Figure 2. From your plot, you can see that
most of the examples are in the region with the highest probability, while
the anomalous examples are in the regions with lower probabilities.
You should now submit your estimate Gaussian parameters function.
1.3 Selecting the threshold, "
Now that you have estimated the Gaussian parameters, you can investigate
which examples have a very high probability given this distribution and which
examples have a very low probability. The low probability examples are
4
0 5 10 15 20 25 30
0
5
10
15
20
25
30
Latency (ms)
Throughput (mb/s)
Figure 2: The Gaussian distribution contours of the distribution t to the
dataset.
more likely to be the anomalies in our dataset. One way to determine which
examples are anomalies is to select a threshold based on a cross validation
set. In this part of the exercise, you will implement an algorithm to select
the threshold " using the F1 score on a cross validation set.
You should now complete the code in selectThreshold.m. For this, we
will use a cross validation set f(x(1)
cv ; y(1)
cv ); : : : ; (x(mcv)
cv ; y(mcv)
cv )g, where the la-
bel y = 1 corresponds to an anomalous example, and y = 0 corresponds
to a normal example. For each cross validation example, we will com-
pute p(x(i)
cv ). The vector of all of these probabilities p(x(1)
cv ); : : : ; p(x
(mcv)
cv ) is
passed to selectThreshold.m in the vector pval. The corresponding labels
y(1)
cv ; : : : ; y
(mcv)
cv is passed to the same function in the vector yval.
The function selectThreshold.m should return two values; the rst is
the selected threshold ". If an example x has a low probability p(x) < ",
then it is considered to be an anomaly. The function should also return the
F1 score, which tells you how well you're doing on nding the ground truth
anomalies given a certain threshold. For many di erent values of ", you will
compute the resulting F1 score by computing how many examples the current
threshold classi es correctly and incorrectly.
The F1 score is computed using precision (prec) and recall (rec):
F1 =
2 prec rec
prec + rec
; (3)
5
You compute precision and recall by:
prec =
tp
tp + fp
(4)
rec =
tp
tp + fn
; (5)
where
tp is the number of true positives: the ground truth label says it's an
anomaly and our algorithm correctly classi ed it as an anomaly.
fp is the number of false positives: the ground truth label says it's not
an anomaly, but our algorithm incorrectly classi ed it as an anomaly.
fn is the number of false negatives: the ground truth label says it's an
anomaly, but our algorithm incorrectly classi ed it as not being anoma-
lous.
In the provided code selectThreshold.m, there is already a loop that
will try many di erent values of " and select the best " based on the F1 score.
You should now complete the code in selectThreshold.m. You can im-
plement the computation of the F1 score using a for-loop over all the cross
validation examples (to compute the values tp, fp, fn). You should see a
value for epsilon of about 8.99e-05.
Implementation Note: In order to compute tp, fp and fn, you may
be able to use a vectorized implementation rather than loop over all the
examples. This can be implemented by Octave's equality test between a
vector and a single number. If you have several binary values in an n-
dimensional binary vector v 2 f0; 1gn, you can nd out how many values
in this vector are 0 by using: sum(v == 0). You can also apply a logical
and operator to such binary vectors. For instance, let cvPredictions be
a binary vector of the size of your number of cross validation set, where
the i-th element is 1 if your algorithm considers x(i)
cv an anomaly, and
0 otherwise. You can then, for example, compute the number of false
positives using: fp = sum((cvPredictions == 1) & (yval == 0)).
Once you have completed the code in selectThreshold.m, the next step
in ex8.m will run your anomaly detection code and circle the anomalies in
the plot (Figure 3).
You should now submit your select threshold function.
6
0 5 10 15 20 25 30
0
5
10
15
20
25
30
Latency (ms)
Throughput (mb/s)
Figure 3: The classi ed anomalies.
1.4 High dimensional dataset
The last part of the script ex8.m will run the anomaly detection algorithm
you implemented on a more realistic and much harder dataset. In this
dataset, each example is described by 11 features, capturing many more
properties of your compute servers.
The script will use your code to estimate the Gaussian parameters (i and
2
i ), evaluate the probabilities for both the training data X from which you
estimated the Gaussian parameters, and do so for the the cross-validation
set Xval. Finally, it will use selectThreshold to nd the best threshold ".
You should see a value epsilon of about 1.38e-18, and 117 anomalies found.
2 Recommender Systems
In this part of the exercise, you will implement the collaborative ltering
learning algorithm and apply it to a dataset of movie ratings.1 This dataset
consists of ratings on a scale of 1 to 5. The dataset has nu = 943 users, and
nm = 1682 movies. For this part of the exercise, you will be working with
the script ex8 cofi.m.
1MovieLens 100k Dataset from GroupLens Research.
7
In the next parts of this exercise, you will implement the function cofiCostFunc.m
that computes the collaborative tlering objective function and gradient. Af-
ter implementing the cost function and gradient, you will use fmincg.m to
learn the parameters for collaborative ltering.
2.1 Movie ratings dataset
The rst part of the script ex8 cofi.m will load the dataset ex8 movies.mat,
providing the variables Y and R in your Octave environment.
The matrix Y (a num movies num users matrix) stores the ratings y(i;j)
(from 1 to 5). The matrix R is an binary-valued indicator matrix, where
R(i; j) = 1 if user j gave a rating to movie i, and R(i; j) = 0 otherwise. The
objective of collaborative ltering is to predict movie ratings for the movies
that users have not yet rated, that is, the entries with R(i; j) = 0. This will
allow us to recommend the movies with the highest predicted ratings to the
user.
To help you understand the matrix Y, the script ex8 cofi.m will compute
the average movie rating for the rst movie (Toy Story) and output the
average rating to the screen.
Throughout this part of the exercise, you will also be working with the
matrices, X and Theta:
X =
2
6664
| (x(1))T |
| (x(2))T |
...
| (x(nm))T |
3
7775
; Theta =
2
6664
| ((1))T |
| ((2))T |
...
| ((nu))T |
3
7775
:
The i-th row of X corresponds to the feature vector x(i) for the i-th movie,
and the j-th row of Theta corresponds to one parameter vector (j), for the
j-th user. Both x(i) and (j) are n-dimensional vectors. For the purposes of
this exercise, you will use n = 100, and therefore, x(i) 2 R100 and (j) 2 R100.
Correspondingly, X is a nm 100 matrix and Theta is a nu 100 matrix.
2.2 Collaborative ltering learning algorithm
Now, you will start implementing the collaborative ltering learning algo-
rithm. You will start by implementing the cost function (without regulariza-
tion).
The collaborative ltering algorithm in the setting of movie recommen-
dations considers a set of n-dimensional parameter vectors x(1); :::; x(nm) and
8
(1); :::; (nu), where the model predicts the rating for movie i by user j as
y(i;j) = ((j))T x(i). Given a dataset that consists of a set of ratings produced
by some users on some movies, you wish to learn the parameter vectors
x(1); :::; x(nm); (1); :::; (nu) that produce the best t (minimizes the squared
error).
You will complete the code in cofiCostFunc.m to compute the cost func-
tion and gradient for collaborative ltering. Note that the parameters to the
function (i.e., the values that you are trying to learn) are X and Theta. In
order to use an o -the-shelf minimizer such as fmincg, the cost function has
been set up to unroll the parameters into a single vector params. You had
previously used the same vector unrolling method in the neural networks
programming exercise.
2.2.1 Collaborative ltering cost function
The collaborative ltering cost function (without regularization) is given by
J(x(1); :::; x(nm); (1); :::; (nu)) =
1
2
X
(i;j):r(i;j)=1
(((j))T x(i) y(i;j))2:
You should now modify cofiCostFunc.m to return this cost in the vari-
able J. Note that you should be accumulating the cost for user j and movie
i only if R(i; j) = 1.
After you have completed the function, the script ex8 cofi.m will run
your cost function. You should expect to see an output of 22:22.
You should now submit your cost function.
9
Implementation Note: We strongly encourage you to use a vectorized
implementation to compute J, since it will later by called many times
by the optimization package fmincg. As usual, it might be easiest to
rst write a non-vectorized implementation (to make sure you have the
right answer), and the modify it to become a vectorized implementation
(checking that the vectorization steps don't change your algorithm's out-
put). To come up with a vectorized implementation, the following tip
might be helpful: You can use the R matrix to set selected entries to 0.
For example, R .* M will do an element-wise multiplication between M
and R; since R only has elements with values either 0 or 1, this has the
e ect of setting the elements of M to 0 only when the corresponding value
in R is 0. Hence, sum(sum(R.*M)) is the sum of all the elements of M for
which the corresponding element in R equals 1.
2.2.2 Collaborative ltering gradient
Now, you should implement the gradient (without regularization). Speci -
cally, you should complete the code in cofiCostFunc.m to return the vari-
ables X grad and Theta grad. Note that X grad should be a matrix of the
same size as X and similarly, Theta grad is a matrix of the same size as
Theta. The gradients of the cost function is given by:
@J
@x(i)
k
=
X
j:r(i;j)=1
(((j))T x(i) y(i;j))(j)
k
@J
@(j)
k
=
X
i:r(i;j)=1
(((j))T x(i) y(i;j))x(i)
k :
Note that the function returns the gradient for both sets of variables
by unrolling them into a single vector. After you have completed the code
to compute the gradients, the script ex8 cofi.m will run a gradient check
(checkCostFunction) to numerically check the implementation of your gra-
dients.2 If your implementation is correct, you should nd that the analytical
and numerical gradients match up closely.
You should now submit your collaborative ltering gradient function.
2This is similar to the numerical check that you used in the neural networks exercise.
10
Implementation Note: You can get full credit for this assignment
without using a vectorized implementation, but your code will run much
more slowly (a small number of hours), and so we recommend that you
try to vectorize your implementation.
To get started, you can implement the gradient with a for-loop over movies
(for computing @J
@x(i)
k
) and a for-loop over users (for computing @J
@(j)
k
). When
you rst implement the gradient, you might start with an unvectorized
version, by implementing another inner for-loop that computes each ele-
ment in the summation. After you have completed the gradient computa-
tion this way, you should try to vectorize your implementation (vectorize
the inner for-loops), so that you're left with only two for-loops (one for
looping over movies to compute @J
@x(i)
k
for each movie, and one for looping
over users to compute @J
@(j)
k
for each user).
11
Implementation Tip: To perform the vectorization, you might nd this
helpful: You should come up with a way to compute all the derivatives
associated with x(i)
1 ; x(i)
2 ; : : : ; x(i)
n (i.e., the derivative terms associated with
the feature vector x(i)) at the same time. Let us de ne the derivatives for
the feature vector of the i-th movie as:
(Xgrad(i; :))T =
2
66664
@J
@x(i)
1
@J
@x(i)
2...
@J
@x(i)
n
3
77775
=
X
j:r(i;j)=1
(((j))T x(i) y(i;j))(j)
To vectorize the above expression, you can start by indexing into
Theta and Y to select only the elements of interests (that is, those with
r(i; j) = 1). Intuitively, when you consider the features for the i-th movie,
you only need to be concern about the users who had given ratings to the
movie, and this allows you to remove all the other users from Theta and Y.
Concretely, you can set idx = find(R(i, :)==1) to be a list of all the
users that have rated movie i. This will allow you to create the temporary
matrices Thetatemp = Theta(idx; :) and Ytemp = Y(i; idx) that index into
Theta and Y to give you only the set of users which have rated the i-th
movie. This will allow you to write the derivatives as:
Xgrad(i; :) = (X(i; :) ThetaT
temp Ytemp) Thetatemp:
(Note: The vectorized computation above returns a row-vector instead.)
After you have vectorized the computations of the derivatives with respect
to x(i), you should use a similar method to vectorize the derivatives with
respect to (j) as well.
2.2.3 Regularized cost function
The cost function for collaborative ltering with regularization is given by
12
J(x(1); :::; x(nm); (1); :::; (nu)) =
1
2
X
(i;j):r(i;j)=1
(((j))T x(i) y(i;j))2+
2
Xnu
j=1
Xn
k=1
((j)
k )2
!
+
2
Xnm
i=1
Xn
k=1
(x(i)
k )2
!
:
You should now add regularization to your original computations of the
cost function, J. After you are done, the script ex8 cofi.m will run your
regularized cost function, and you should expect to see a cost of about 31.34.
You should now submit your regularized cost function.
2.2.4 Regularized gradient
Now that you have implemented the regularized cost function, you should
proceed to implement regularization for the gradient. You should add to
your implementation in cofiCostFunc.m to return the regularized gradient
by adding the contributions from the regularization terms. Note that the
gradients for the regularized cost function is given by:
@J
@x(i)
k
=
X
j:r(i;j)=1
(((j))T x(i) y(i;j))(j)
k + x(i)
k
@J
@(j)
k
=
X
i:r(i;j)=1
(((j))T x(i) y(i;j))x(i)
k + (j)
k :
This means that you just need to add x(i) to the X grad(i,:) variable
described earlier, and add (j) to the Theta grad(j,:) variable described
earlier.
After you have completed the code to compute the gradients, the script
ex8 cofi.m will run another gradient check (checkCostFunction) to numer-
ically check the implementation of your gradients.
You should now submit the regularized gradient function.
2.3 Learning movie recommendations
After you have nished implementing the collaborative ltering cost function
and gradient, you can now start training your algorithm to make movie
13
recommendations for yourself. In the next part of the ex8 cofi.m script,
you can enter your own movie preferences, so that later when the algorithm
runs, you can get your own movie recommendations! We have lled out
some values according to our own preferences, but you should change this
according to your own tastes. The list of all movies and their number in the
dataset can be found listed in the le movie idx.txt.
2.3.1 Recommendations
Top recommendations for you:
Predicting rating 9.0 for movie Titanic (1997)
Predicting rating 8.9 for movie Star Wars (1977)
Predicting rating 8.8 for movie Shawshank Redemption, The (1994)
Predicting rating 8.5 for movie As Good As It Gets (1997)
Predicting rating 8.5 for movie Good Will Hunting (1997)
Predicting rating 8.5 for movie Usual Suspects, The (1995)
Predicting rating 8.5 for movie Schindler's List (1993)
Predicting rating 8.4 for movie Raiders of the Lost Ark (1981)
Predicting rating 8.4 for movie Empire Strikes Back, The (1980)
Predicting rating 8.4 for movie Braveheart (1995)
Original ratings provided:
Rated 4 for Toy Story (1995)
Rated 3 for Twelve Monkeys (1995)
Rated 5 for Usual Suspects, The (1995)
Rated 4 for Outbreak (1995)
Rated 5 for Shawshank Redemption, The (1994)
Rated 3 for While You Were Sleeping (1995)
Rated 5 for Forrest Gump (1994)
Rated 2 for Silence of the Lambs, The (1991)
Rated 4 for Alien (1979)
Rated 5 for Die Hard 2 (1990)
Rated 5 for Sphere (1998)
Figure 4: Movie recommendations
After the additional ratings have been added to the dataset, the script
will proceed to train the collaborative ltering model. This will learn the
parameters X and Theta. To predict the rating of movie i for user j, you need
14
to compute ((j))T x(i). The next part of the script computes the ratings for
all the movies and users and displays the movies that it recommends (Figure
4), according to ratings that were entered earlier in the script. Note that
you might obtain a di erent set of the predictions due to di erent random
initializations.
1 file (2.0MB)
