Note to other teachers and users of these slides: We would be delighted if you found this ourmaterial useful in giving your own lectures. Feel free to use these slides verbatim, or to modify
them to fit your own needs. If you make use of a significant portion of these slides in your own
lecture, please include this message, or a link to our web site: http://www.mmds.org

Mining of Massive Datasets
Jure Leskovec, Anand Rajaraman, Jeff Ullman
Stanford University

http://www.mmds.org

High dim.
data

Graphdata

Infinitedata

MachinelearningAppsLocality
sensitive
hashing

PageRank,
SimRank

Filteringdatastreams

SVM

Recommender systems

Clustering

Community
DetectionWebadvertising

Decision
TreesAssociation
Rules

Dimensional
ityreduction

Spam
Detection

Queries onstreams

Perceptron,kNN

Duplicate
document
detection

8/11/2014

Jure Leskovec, Stanford C246: Mining Massive Datasets2 Would like to do prediction:

estimate a function f(x) so that y = f(x) Where y can be: Real number: Regression
 Categorical: Classification
 Complex object: Ranking of items, Parse tree, etc.

 Data is labeled: Have many pairs {(x, y)}

XYX’Y’

Training and test set
Estimate y = f(x) on X,Y.
Hope that the same f(x)also works on unseen X’, Y’

 x … vector of binary, categorical, real valued features
 y … class ({+1, -1}, or a real number)
J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org

3 We will talk about the following methods:

 k-Nearest Neighbor (Instance based learning) Perceptron and Winnow algorithms
 Support Vector Machines Decision trees
 Main question:

How to efficiently train(build a model/find model parameters)?

J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org

4 Instance based learning Example: Nearest neighbor Keep the whole training dataset: {(x, y)} A query example (vector) q comes Find closest example(s) x*
 Predict y*
 Works both for regression and classification

 Collaborative filtering is an example of k-NN classifier Find k most similar people to user x that have rated movie y Predict rating yx of x as an average of ykJ. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org

5 To make Nearest Neighbor work we need 4 things:

 Distance metric:
 Euclidean

 How many neighbors to look at?
 One Weighting function (optional): Unused How to fit with the local points?
 Just predict the same output as the nearest neighbor

J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org

6 Distance metric:

 Euclidean

 How many neighbors to look at?

 k Weighting function (optional): Unused How to fit with the local points?

 Just predict the average output among k nearest neighbors

k=9J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org

7

Distance metric:How many neighbors to look at?
 All of them (!)

wi Euclidean

Weighting function:   

,







d(xi, q) = 0

 Nearby points to query q are weighted more strongly. Kw…kernel width.

How to fit with the local points?
∑  Predict weighted average: ∑   Kw=10

Kw=20Kw=80

J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org

8 Given: a set P of n points in Rd
 Goal: Given a query point q

 NN: Find the nearest neighbor p of q in P
 Range search: Find one/all points in P within
distance r from qpq

J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org

9 Main memory: Linear scan Tree based: Quadtree
 kd-tree

 Hashing: Locality-Sensitive Hashing Secondary storage: R-treesJ. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org

10 Example: Spam filtering Instance space x ∈ X (|X|= n data points)

 Binary or real-valued feature vector x of word
occurrences
 d features (words + other things, d~100,000)
 Class y ∈ Y y: Spam (+1), Ham (-1)
J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org

12 Binary classification:f (x) ={+1-1Decisionboundary
is linear

if w1 x1 + w2 x2 +. . . wd xd ≥ θotherwise Input: Vectors x(j) and labels y(j) Vectors x(j) are real valued where  Goal: Find vector w = (w1, w2 ,... , wd )

 Each wi is a real numberw⋅x=0-- - - -- - - -w
-J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org

Note:x ⇔ x, 1∀xw ⇔ w, − θ13 (very) Loose motivation: Neuron Inputs are feature values
 Each feature has a weight wi

 f(x) = Σi wi xi = w⋅ x
 If the f(x) is: Positive: Predict +1
 Negative: Predict -1w⋅⋅x=0nigeria

w1x1
w2x2
w3x3
w4x4

 Activation is the sum:

∑≥ 0?

x(1)
Spam=1x(2)w
Ham=-1

J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org

viagra14

 Perceptron: y’ = sign(w⋅ x)
 How to find parameters w?

Note that the Perceptron isa conservative algorithm: it
ignores samples that itclassifies correctly.

 Start with w0 = 0
 Pick training examples x(t) one by one (from disk)
 Predict class of x(t) using current weights
 y’ = sign(w(t)⋅ x(t))

 If y’ is correct (i.e., yt = y’) No change: w(t+1) = w(t)η⋅yη⋅ (t)⋅x(t) If y’ is wrong: adjust w(t)w(t+1) = w(t) + η ⋅ y (t) ⋅ x(t) η is the learning rate parameter x(t) is the t-th training example
 y(t) is true t-th class label ({+1, -1})
J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.orgw(t)w(t+1)

x(t), y(t)=115

 Perceptron Convergence Theorem:

 If there exist a set of weights that are consistent(i.e., the data is linearly separable) the Perceptron
learning algorithm will converge
 How long would it take to converge?
 Perceptron Cycling Theorem:

 If the training data is not linearly separable thePerceptron learning algorithm will eventually
repeat the same set of weights and therefore
enter an infinite loop
 How to provide robustness, more

expressivity?
J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org

16 Separability: Some parameters gettraining set perfectly
 Convergence: If training set is separable,perceptron will converge
 (Training) Mistake bound:Number of mistakes  γ
 where    |  |,and    1
 Note we assume x Euclidean length 1, then γ is theminimum distance of any example to plane u
J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org

17 Perceptron will oscillate and won’t converge
 When to stop learning?
 (1) Slowly decrease the learning rate η A classic way is to: η = c1/(t + c2)
 But, we also need to determine constants c1 and c2

 (2) Stop when the training error stops chaining (3) Have a small test dataset and stop when thetest set error stops decreasing (4) Stop when we reached some maximum
number of passes over the data
J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org

18 What if more than 2 classes?
 Weight vector wc for each class c

 Train one class vs. the rest: Example: 3-way classification y = {A, B, C} Train 3 classifiers: wA: A vs. B,C; wB: B vs. A,C; wC: C vs. A,B Calculate activation for each classf(x,c) = Σi wc,i xi = wc⋅ x
 Highest activation winsc = arg maxc f(x,c)

w C⋅ xbiggest
wC

wA

wB

wB⋅x
biggestwA ⋅ xbiggestJ. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org

19 Overfitting: Regularization: If the data

is not separable weights
dance around Mediocre generalization:

 Finds a “barely” separating
solution
J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org

20 Winnow : Predict f(x) = +1 iff  ⋅"# Similar to perceptron, just different updates
 Assume x is a real-valued feature vector,&• Initialize: #  ,  '',…,&&

 • For every training example • Compute )  *  • If no mistake (  ′): do nothing• If mistake then:  ←  % $ w … weights (can never get negative!) $  ∑  %


is the normalizing const.

J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org

21



 %
$

 About the update:  ←  If x is false negative, increase wi If x is false positive, decrease wi In other words: Consider1 Then ∝ 
 ∈.

(promote)(demote)1, /104% 67 89:  ; :
⋅ 3 5%
4<=>< Notice: This is a weighted majority algorithm of“experts” xi agreeing with yJ. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org

22 Problem: All wi can only be >0 Solution:

 For every feature xi, introduce a new feature xi’ = -xi
 Learn Winnow over 2d features
 Example:

 Consider:  1, .7, .4 ,   B.5, . 2, .3F
 Then new and  are  B1, . 7, .4,1, .7, . 4F, G  B.5, . 2, 0, 0, 0, .3F
 Note this results in the same dot values as if weused original and G

 New algorithm is called Balanced Winnow
J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org

23 In practice we implement Balanced Winnow:

 2 weight vectors w+, w-; effective weight is thedifference• Classification rule:• f(x) =+1 if (w+-w-)·x ≥ θ• Update rule:• If mistake:• G1 ← G1• G5 ← G5

 % $I 5% $J$5  K  J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org

% 24

 Thick Separator (aka Perceptron with Margin)(Applies both to Perceptron and Winnow) Set margin
parameter γ Update if y=+1but w ⋅ x < θ + γ
 or if y=-1but w ⋅ x > θ - γ-- - -- - - -- -w

Note: γ is a functional margin. Its effect could disappear as w grows.
Nevertheless, this has been shown to be a very effective algorithmic addition.
J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org

25





Setting: Examples: ∈ .L, 0, weights  ∈ M
 Prediction: *   / iff  ⋅ " # else 

Perceptron: Additive weight updatew ← w + η yx

 If y=+1 but w∙x ≤ θ then wi ← wi + 1 (if xi=1) (promote) If y=-1 but w∙x > θ then wi ← wi - 1 (if xi=1) (demote)Winnow: Multiplicative weight updatew ← w exp{η y x} If y=+1 but w∙x ≤ θ then wi ← 2 ∙ wi (if xi=1) (promote) If y=-1 but w∙x > θ then wi ← wi / 2 (if xi=1) (demote)J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org

26 How to compare learning algorithms?
 Considerations: Number of features d is very large
 The instance space is sparse Only few features per training example are non-zero The model is sparse Decisions depend on a small subset of features
 In the “true” model on a few wi are non-zero Want to learn from a number of examples thatis small relative to the dimensionality dJ. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org

27Perceptron Online: Can adjust tochanging target, overtime Advantages
 Simple Guaranteed to learn alinearly separable problem
 Advantage with few
relevant features pertraining example
 Limitations

 Only linear separations
 Only converges for linearly
separable data
 Not really “efficient withmany features”

Winnow
 Online: Can adjust tochanging target, overtime Advantages
 Simple Guaranteed to learn alinearly separable problem
 Suitable for problems withmany irrelevant attributes
 Limitations

 Only linear separations
 Only converges for linearly
separable data
 Not really “efficient withmany features”

J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org

28 New setting: Online Learning Allows for modeling problems where we havea continuous stream of data
 We want an algorithm to learn from it and slowly
adapt to the changes in data
 Idea: Do slow updates to the model Both our methods Perceptron and Winnow makeupdates if they misclassify an example
 So: First train the classifier on training data. Then forevery example from the stream, if we misclassify,
update the model (using small learning rate)
J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org29

 Protocol:

 User comes and tell us origin and destination
 We offer to ship the package for some money ($10 - $50)
 Based on the price we offer, sometimes the user uses
our service (y = 1), sometimes they don't (y = -1)
 Task: Build an algorithm to optimize what price

we offer to the users
 Features x capture: Information about user Origin and destination
 Problem: Will user accept the price?
J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org30

 Model whether user will accept our price:y = f(x; w) Accept: y =1, Not accept: y=-1
 Build this model with say Perceptron or Winnow The website that runs continuously Online learning algorithm would do something like

 User comes She is represented as an (x,y) pair where x: Feature vector including price we offer, origin, destination
 y: If they chose to use our service or not The algorithm updates w using just the (x,y) pair
 Basically, we update the w parameters every time we getsome new data
J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org

31 We discard this idea of a data “set”
 Instead we have a continuous stream of data Further comments:

 For a major website where you have a massive
stream of data then this kind of algorithm is pretty
reasonable Don’t need to deal with all the training data If you had a small number of users you could savetheir data and then run a normal algorithm on thefull dataset
 Doing multiple passes over the data
J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org

32 An online algorithm can adapt to changing

user preferences For example, over time users may become

more price sensitive The algorithm adapts and learns this So the system is dynamic

J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org

33