Today’s Lecture • Where we’ve been – Big Data – Statistics – MapReduce – Interpretation of results
• Where we’re going today – Machine learning
• Where we’re going next – Part 2 of course: Security and InSecurity in the Real World – 2 readings each lecture 2
Machine Learning Systems that automatically learn programs from data P. Domingos, CACM 2012
• Supervised learning: have inputs and associated outputs – Learn relationships between them using available training data (also called “labeled data”, “ground truth”) – Predict future values – Classification: The output (learned attribute) is categorical – Regression: The output (learned attribute) is numeric
• Unsupervised learning: have only inputs – Learn “latent” labels – Clustering: Identify natural groups in the data 3
Rules Weather and golf outlook overcast overcast overcast overcast rainy rainy rainy rainy rainy sunny sunny sunny sunny sunny
temp cool hot hot mild cool mild cool mild mild hot hot mild cool mild
humidity windy normal TRUE high FALSE normal FALSE high TRUE normal TRUE high TRUE normal FALSE high FALSE normal FALSE high FALSE high TRUE high FALSE normal FALSE normal TRUE
play yes yes yes yes no no yes yes yes no no no yes yes
• Want to decide when to play – Create rules based on attributes
• Example: 1 attribute if (outlook == “rainy”) then play = “no” else play = “yes”
– Errors: 6/14
• Can refine rule by adding conditions on other attributes – Create a decision tree 4
Entropy Which attribute do we choose at each level? • Consider two sequences of coin flips – How much information do we get after flipping each coin once? – We want some function “Information” that satisfies: Information1&2(p1p2) = Information1(p1) + Information2(p2) – Expected Information = “Entropy”
I(X) = -log2 px H (X) = E(I(X)) = -å px log2 px x
• Examples – Flipping a coin
H(X) = - ( 0.5log2 0.5+ 0.5log2 0.5) =1
! In learning the outcome of the coin flip we learned 1 bit of information æ1 1ö – Rolling a fair die H (X) = 6 ´ - ç log 2 ÷ » 2.58 è6 6ø ! A die is more unpredictable than a coin H(X) » 2.16 – Rolling a weighted die with p1..5=0.1, p6=0.5 ! A weighted die is less unpredictable than a fair die
Decision Tree • At each level, choose the attribute with the highest information gain
Weather and golf outlook overcast overcast overcast overcast rainy rainy rainy rainy rainy sunny sunny sunny sunny sunny
temp cool hot hot mild cool mild cool mild mild hot hot mild cool mild
humidity windy normal TRUE high FALSE normal FALSE high TRUE normal TRUE high TRUE normal FALSE high FALSE normal FALSE high FALSE high TRUE high FALSE normal FALSE normal TRUE
play yes yes yes yes no no yes yes yes no no no yes yes
– The one that reduces the unpredictability the most
• Before: 9/14 “yes” outcomes => H=0.94 – Outlook: H=0.69 • 4/4 “yes” for overcast (H=0) • 3/5 “yes” for rainy (H=0.97) • 2/5 “yes” for sunny (H=0.97)
• Outlook provides highest information gain: 0.94 – 0.69 = 0.25 6
Resulting Decision Tree • Putting the decision tree together – Choose the attribute with the highest Information Gain – Create branches for each value of attribute – Discretize continuous attributes (choose partition with highest gain) – R package: rpart • Not a perfect classification (still makes some incorrect decisions)
7
Overfitting • Low error on training data and high error on test data – “If the knowledge and data we have are not sufficient to completely determine the correct classifier, […] we run the risk of just hallucinating a classifier that […] simply encodes random quirks in the data.” – P. Domingos, CACM’12
Underfitting
• Some algorithms can prune the tree to avoid overfitting Overfitting 8
Confusion Matrix How to determine if the classifier does a good job? • You need a training set (ground truth) and a testing set – Or you can split your ground truth into two data sets – Even better: K-fold cross-validation • Select K samples without replacement and train classifier multiple times
– Also called true negative rate FP rate (1 – Specificity)
• Can plot a Receiver Operating Characteristic (ROC) curve – R package: ROCR
10
Unsupervised Learning • Agglomerative hierarchical clustering (R: hclust) – No ground truth; goal is to identify patterns that describe the data – Start from individual points and progressively merge nearby clusters – Distance metric (e.g. Euclidian, rank correlation, Gower) – Linkage: how to aggregate pairwise point distances into cluster distances • Average? Minimum (single)? Maximum (complete)? Variance decrease (Ward)?
Dendrogram of 1970 cars (features: MPG, weight, drive ratio)
! Choose classification or clustering features carefully
Additional Machine Learning Resources • Classification – We saw: decision trees – Other classifiers: naïve Bayes, Support Vector Machines (SVM) – Natural language processing • Text mining (R package: tm) • Sentiment analysis (annotated English wordlist: http://www2.imm.dtu.dk/pubdb/views/publication_details.php?id=6010)
• Clustering – We saw: hierarchical clustering – Other clustering techniques: k-means, k-medoids, time series clustering – Dimensionality reduction: principal component analysis (PCA)
• Machine learning tools – For R: http://cran.r-project.org/web/views/MachineLearning.html – For Hadoop: Mahout (http://mahout.apache.org/)
12
Project Peer-Reviews • Pilot project reports – Reports due today • Discuss hypothesis (security problem and data analyzed to solve it) • Feasibility study • Report data volume, velocity, variety and quality
– Post report on Piazza
• Pilot project peer reviews – Review at least 2 project reports from other students • Use skills learned from paper reviews
– Peer reviews are a part of your grade – Post reviews on Piazza (as follow-ups to report posts) by Monday 13
Review of Lecture • What did we learn? – Classification – Clustering
• What’s next? – Paper discussion: ‘Sex, Lies and Cyber-crime Surveys’ – Next lecture: start of part 2 of course – 2 readings / lecture
• Deadline reminders – Pilot project reports due today – Pilot project reviews due Monday – Group project proposals due Monday, 09/30 14
