lOMoAR cPSD| 70487227
CSE 547: Machine Learning for Big Data ASSIGNMENT
Problem Set 3
Please read the homework submission policies.
Assignment Submission All students should submit their assignments electronically via
GradeScope. No handwritten work will be accepted. Math formulas must be typeset using
LATEX or other word processing software that supports mathematical symbols (E.g. Google
Docs, Microsoft Word). Simply sign up on Gradescope and use the course code V84RPB.
Please use your UW NetID if possible.
For the non-coding component of the homework, you should upload a PDF rather than
submitting as images. We will use Gradescope for the submission of code as well. Please
make sure to tag each part correctly on Gradescope so it is easier for us to grade. There will
be a small point deduction for each mistagged page and for each question that includes code.
Put all the code for a single question into a single file and upload it. Only files in text format
(e.g. .txt, .py, .java) will be accepted. There will be no credit for coding questions without
submitted code on Gradescope, or for submitting it after the deadline, so please
remember to submit your code.
Coding You may use any programming languages and standard libraries, such as NumPy and
PySpark, but you may not use specialized packages and, in particular, machine learning
libraries (e.g. sklearn, TensorFlow), unless stated otherwise. Ask on the discussion board
whether specific libraries are allowed if you are unsure.
Late Day Policy All students will be given two no-questions-asked late periods, but only one
late period can be used per homework and cannot be used for project deliverables. A late-
period lasts 48 hours from the original deadline (so if an assignment is due on Thursday at
11:59 pm, the late period goes to the Saturday at 11:59pm Pacific Time).
Academic Integrity We take academic integrity extremely seriously. We strongly encourage
students to form study groups. Students may discuss and work on homework problems in
groups. However, each student must write down the solutions and the code independently.
In addition, each student should write down the set of people whom they interacted with.
Discussion Group (People with whom you discussed ideas used in your answers):
On-line or hardcopy documents used as part of your answers:
I acknowledge and accept the Academic Integrity clause.
, lOMoAR cPSD| 70487227
CSE 547 - Machine Learning for Big Data - Problem Set 3 2
(Signed)
1 Dead Ends in PageRank Computations (25 points)
We learned about PageRank in lecture which is an algorithm for ranking webpages. In this
problem, we are going to focus on dead ends and examine how they affect the PageRank
computations.
Suppose we denote the matrix of the Internet as the n-by-n matrix M, where n is the number
of webpages. Suppose there are k links out of the node (webpage) j, and
if there is a link from j to i
ij =
0 otherwise
For a webpage j that is a dead end (i.e., one having zero links out), the column j is all zeroes.
Let r = [r1,r2,...,rn]> be an estimate of the PageRank vector. In one iteration of the PageRank
algorithm, we compute the next estimate r0 of the PageRank as: r0 = Mr.
Given any PageRank estimate vector r, define .
(a) [6pts] Suppose the Web has no dead ends. Prove that w(r0) = w(r).
(b) [9pts] Suppose there are still no dead ends, but we use a teleportation probability (i.e.,
the probability of jumping to some random page) of 1 − β, where 0 < β < 1. The expression
for the next estimate of ri becomes . Under what
conditions will w(r0) = w(r)? Prove your conclusion.
Hint: The conditions required for the equality are related to w(r).
(c) [10pts] Now, let us assume a teleportation probability of 1 − β in addition to the fact that
there are one or more dead ends. Call a node “dead” if it is a dead end and “live” if not.
Assume w(r) = 1. At each iteration, when not teleporting, each live node j distributes βrj
PageRank uniformly across each of the nodes it links to, and each dead node j distributes
rj/n PageRank to all the nodes.
Write the equation for ri0 in terms of β, M, r, n, and D (where D is the set of dead nodes).
Then, prove that w(r0) = 1.
What to submit
(i) Proof [1(a)]
(ii) Condition for w(r0) = w(r) and Proof [1(b)]
CSE 547: Machine Learning for Big Data ASSIGNMENT
Problem Set 3
Please read the homework submission policies.
Assignment Submission All students should submit their assignments electronically via
GradeScope. No handwritten work will be accepted. Math formulas must be typeset using
LATEX or other word processing software that supports mathematical symbols (E.g. Google
Docs, Microsoft Word). Simply sign up on Gradescope and use the course code V84RPB.
Please use your UW NetID if possible.
For the non-coding component of the homework, you should upload a PDF rather than
submitting as images. We will use Gradescope for the submission of code as well. Please
make sure to tag each part correctly on Gradescope so it is easier for us to grade. There will
be a small point deduction for each mistagged page and for each question that includes code.
Put all the code for a single question into a single file and upload it. Only files in text format
(e.g. .txt, .py, .java) will be accepted. There will be no credit for coding questions without
submitted code on Gradescope, or for submitting it after the deadline, so please
remember to submit your code.
Coding You may use any programming languages and standard libraries, such as NumPy and
PySpark, but you may not use specialized packages and, in particular, machine learning
libraries (e.g. sklearn, TensorFlow), unless stated otherwise. Ask on the discussion board
whether specific libraries are allowed if you are unsure.
Late Day Policy All students will be given two no-questions-asked late periods, but only one
late period can be used per homework and cannot be used for project deliverables. A late-
period lasts 48 hours from the original deadline (so if an assignment is due on Thursday at
11:59 pm, the late period goes to the Saturday at 11:59pm Pacific Time).
Academic Integrity We take academic integrity extremely seriously. We strongly encourage
students to form study groups. Students may discuss and work on homework problems in
groups. However, each student must write down the solutions and the code independently.
In addition, each student should write down the set of people whom they interacted with.
Discussion Group (People with whom you discussed ideas used in your answers):
On-line or hardcopy documents used as part of your answers:
I acknowledge and accept the Academic Integrity clause.
, lOMoAR cPSD| 70487227
CSE 547 - Machine Learning for Big Data - Problem Set 3 2
(Signed)
1 Dead Ends in PageRank Computations (25 points)
We learned about PageRank in lecture which is an algorithm for ranking webpages. In this
problem, we are going to focus on dead ends and examine how they affect the PageRank
computations.
Suppose we denote the matrix of the Internet as the n-by-n matrix M, where n is the number
of webpages. Suppose there are k links out of the node (webpage) j, and
if there is a link from j to i
ij =
0 otherwise
For a webpage j that is a dead end (i.e., one having zero links out), the column j is all zeroes.
Let r = [r1,r2,...,rn]> be an estimate of the PageRank vector. In one iteration of the PageRank
algorithm, we compute the next estimate r0 of the PageRank as: r0 = Mr.
Given any PageRank estimate vector r, define .
(a) [6pts] Suppose the Web has no dead ends. Prove that w(r0) = w(r).
(b) [9pts] Suppose there are still no dead ends, but we use a teleportation probability (i.e.,
the probability of jumping to some random page) of 1 − β, where 0 < β < 1. The expression
for the next estimate of ri becomes . Under what
conditions will w(r0) = w(r)? Prove your conclusion.
Hint: The conditions required for the equality are related to w(r).
(c) [10pts] Now, let us assume a teleportation probability of 1 − β in addition to the fact that
there are one or more dead ends. Call a node “dead” if it is a dead end and “live” if not.
Assume w(r) = 1. At each iteration, when not teleporting, each live node j distributes βrj
PageRank uniformly across each of the nodes it links to, and each dead node j distributes
rj/n PageRank to all the nodes.
Write the equation for ri0 in terms of β, M, r, n, and D (where D is the set of dead nodes).
Then, prove that w(r0) = 1.
What to submit
(i) Proof [1(a)]
(ii) Condition for w(r0) = w(r) and Proof [1(b)]
