1

Applied Data Analysis (CS401)

Robert West

Lecture 9

Applied

machine learning

2018/11/15

Announcements

• Course evaluations are being collected -- please evaluate us!
• HW 4 due next week, Wed, Nov 21, 23:59
• HW 3 peer reviews due today 23:59
• Project milestone 2 due on Sun, Nov 25, 23:59
• Tomorrow’s lab session:�Office hours HW 4 + project [FAQ]�Teo Stocco (ADAlumnus who founded and�sold a startup, now at Smood)

2

3

Give us feedback on this lecture here: https://go.epfl.ch/ada2018-lec9-feedback

​

• What did you (not) like about this lecture?
• What was (not) well explained?
• On what would you like more (fewer) details?
• What’s your favorite messaging system?
• …

​

Why an extra class on applied ML?

4

link

Classic ML

class

ADA

Classification pipeline

5

Data collection

Model assessment

Model selection

Data collection

The first step is collecting data related to the classification task.

​

• Definition of the attributes (or features) that describe a data item and the class label.

​

Domain knowledge is needed.

What if assigning the class label would be too time-consuming or even impossible?

→ Unsupervised methods (e.g., clustering); cf. next lecture!

6

Data collection

7

Identification of features

Removing irrelevant features

Unsupervised/supervised discretisation

Discretisation?

Normalisation?

Standardisation/scaling

Y

N

Y

N

Class label available?

Y

N

Data labeling

Features

Different types of features [more]

• Continuous (e.g., height, temperature ...)
• Ordinal (e.g., “agree”, “don’t care”, “disagree” ...)
• Categorical (e.g., color, gender ...)

New features can be generated from simple stats

• Feature engineering is considered a form of art, therefore it is sometimes useful to find what other people did for similar problems

Some classifiers require categorical features => Discretization

8

ML before 2012*

(but still very common today)

​

​

​

​

​

​

* Before publication of Krizhevsky et al.’s ImageNet CNN paper

​

9

Cleverly designed�features

Input data

ML model

Most of the “heavy lifting” in here.

Final performance only as good as the�feature set.

A typical ML approach after 2012

​

​

10

Features

Input data

Model

Deep learning

Features and model learned together,�mutually reinforcing

Data collection

11

Identification of features

Removing irrelevant features

Unsupervised/supervised discretization

Discretisation?

Normalisation?

Standardisation/scaling

Y

N

Y

N

Class label available?

Y

Data labeling

N

Potential labelers

• You
• Older days:
• Undergraduate students
• Domain experts ($$$)
• Now: crowdsourcing
• Can get both amateurs (~ undergrad students)
• and experts

12

Labels

Collecting a lot of data (features) is easy

Labeling data is time consuming, difficult and sometimes even impossible

13

Label: “Is page credible?”

Dietary expert is needed

14

1. Submit task

2. Accept task

3. Return answers

4. Collect answers

Crowdsourcing

Different types of workers

• Truthful
• Expert
• Normal
• Untruthful
• Uniform spammer
• Random spammer
• Malicious spammer (a.k.a. a$s#*le)

15

Catching malicious spammers

• Insert obvious examples for which you already know the labels (“honeypot”)
• Tell workers they won’t be paid if they don’t get those right
• Filter out workers who don’t get them right
• Aggregate multiple answers
• p.t.o.

16

Crowdsourcing

Answer aggregation problem

• Have each example labeled by several workers, aggregate:
• e.g., majority vote (works if only a minority is malicious)
• e.g., “peer prediction”

17

Aggregation

Data collection

18

Identification of features

Removing irrelevant features

Unsupervised/supervised discretization

Discretisation?

Normalisation?

Standardisation/scaling

Y

N

Y

N

Class label available?

Y

N

Data labeling

Discretization

Why?

• Some classifiers want discrete features (e.g., simplest kinds of decision trees)
• Discrete features let a linear classifier learn non-linear decision boundaries
• Certain feature selection methods require discrete (or even binary) features

19

Discretization

Unsupervised

• Equal width
• Divide the range into a predefined number of bins (bad for skewed data, e.g., from a power law)
• Equal frequency
• Divide the range into a predefined number of bins so that every interval contains the same number of values
• Clustering

20

Discretization

Supervised

• Test the hypothesis that membership in two adjacent intervals of a feature is independent of the class
• If they are independent, they should be merged
• Otherwise they should remain separate
• Independence test: χ² statistics

​

21

Data collection

22

Identification of features

Removing irrelevant features

Unsupervised/supervised discretization

Discretisation?

Normalisation?

Standardisation/scaling

Y

N

Y

N

Class label available?

Y

N

Data labeling

Feature selection

Reducing the number of N features to a subset of the best size M < N

There are 2^N possible subsets

​

Solutions

• Filtering as preprocessing (“offline”)
• Iterative feature selection (“online”)

23

Offline feature selection

Rank features according to their individual predictive power; select the best ones

• Pros
• Independent of the classifier (performed only once)
• Cons
• Independent of the classifier (ignore interaction with the classifier)
• Assume features are independent

24

Ranking of features

Continuous features (and ideally labels)

• Correlation coefficient (Pearson, linear rel.!)

​

​

Categorical features and labels

• Mutual information

25

Ranking of features

Categorical features and labels (cont’d)

• χ² method�Difference w.r.t. mutual information: the chi-square test checks the independence of the class and the feature, without indicating the strength or direction of any existing relationship (you just get a significance, a.k.a. p-value)

26

Ranking of features

Beware: collectively relevant features may look individually irrelevant!

​

​

27

Online feature selection

Forward feature selection: iteratively add features, using cross-validation to guide feature inclusion; stop when no improvement

• Pros
• Interact with the classifier
• No feature-independence assumption
• Cons
• Computationally intensive

28

Online feature selection

Backward selection (a.k.a. ablation): iteratively remove features, using cross-validation to guide feature removal; stop when no improvement

• Pros
• Interact with the classifier
• No feature-independence assumption
• Cons
• Computationally intensive

29

Cross-validation

30

Feature count vs. performance

​

​

​

​

​

​

​

31

Data collection

32

Identification of features

Removing irrelevant features

Unsupervised/supervised discretisation

Discretisation?

Normalisation?

Standardisation/scaling

Y

N

Y

N

Class label available?

Y

N

Data labeling

Feature normalization

Some classifiers do not manage well features with very different scales

• Revenue: 10,000,000 (CHF)
• # of employees: 300

Features with large values dominate the others, and the classifier tends to over-optimize them

33

Logarithmic scaling

x_i’ = log(x_i)

• Consider order of magnitude, rather than direct value
• Good for heavy-tailed features (e.g., from power laws)

​

34

Min-max scaling

​

x_i’ = (x_i – m_i)/(M_i – m_i)

​

where M_i and m_i are the max and min values of feature x_i respectively

​

The new feature x_i’ lies in the interval [0,1]

35

Standardization

​

x_i’ = (x_i – μ_i)/σ_i

​

where μ_i is the mean value of feature x_i, and σ_i is the standard deviation

​

The new feature x_i’ has mean 0 and �standard deviation 1

36

Dangers of standardization and scaling

Standardization:

• Assume that the data has been generated by a Gaussian
• Uses mean and std → not meaningful for heavy-tailed data (may be mitigated by log-scaling)

Min-max scaling:

• If the data has outliers, they scale the typical values to a very small interval

​

37

Classification pipeline

38

Data collection

Model assessment

Model selection

Model selection: high level

Need to choose type of model

• Logistic regression?
• Decision trees?
• Random forest?
• Gradient-boosted trees?
• Support vector machine?
• Deep learning?
• …

39

Model selection: low level

Usually a classifier has some “hyperparameters” to be tuned

• Threshold (e.g., logistic regression)
• Regularization factor
• Distance function (e.g., k-NN)
• Number of neighbors (e.g., k-NN)
• Number of trees (e.g., random forest)

40

Model selection

​

​

​

​

​

Need evaluation metric!

41

Split dataset into “training” and “validation”

Evaluate classifier with validation set

Train classifier with training set

Performance acceptable?

Y

N

Set classifier parameters

Loss function (more of them later!)

Categorical output

• e.g., 0-1 loss function (= 1 minus accuracy):

​

Real-valued output

• e.g., squared error:

​

• e.g., absolute error:

42

Model selection

43

Hyperparameter value

Loss function

Performance metrics for binary classification

For categorical binary classification, the usual metrics are based on the confusion matrix, which has 4 values:

• True Positives (positive examples classified as positive)
• True Negatives (negative examples classified as negative)
• False Positives (negative examples classified as positive)
• False Negatives (positive examples classified as negative)

44

Accuracy

​

​

​

Appropriate metric when

• classes are not skewed
• Errors (FP, FN) have the same importance

45

Accuracy (skewed example)

​

​

​

A = 85/100 = 0.85

​

​

​

A = 90/100 = 0.90

​

46

Question time

​

​

​

Which is the “best” classifier?

​

• Classifier 1
• Classifier 2
• Both are equally good

47

Question time

​

​

​

Which is the “best” classifier?

​

• Classifier 1
• Classifier 2
• Both are equally good

​

48

Precision and recall

Precision: what fraction of positive predictions are actually positive?

​

​

Recall: what fraction of positive examples did I recognize as such?

49

Precision and recall

​

​

P₁=45/65=0.69 P₂=40/50=0.8

R₁=45/50=0.9 R₂=40/50=0.8

50

P = 50/100 = 0.5

R = 50/50 = 1

F-score

Sometimes it’s necessary to have a unique metric to compare classifiers

​

F-score (or F1-score): harmonic mean of precision and recall

​

Precision and recall can be differently weighted, if one is more important than the other

​

​

​

51

F1 = 1 / (0.5 * (1/P + 1/R)) =

Precision and recall

​

​

F₁=2*(0.69*0.9)/(0.69+0.9) F₂=2*(0.8*0.8)/(0.8+0.8)

= 0.78 =0.8

52

F=2*(0.5*1)/(0.5+1)=0.66

Precision/recall curve

53

Recap

• Model selection:
• Use training data in cross-validation
• Need evaluation metric
• Typically based on confusion matrix
• e.g., accuracy, precision, recall

54

Data collection

Model assessment

Model selection

ROC plots

ROC = Receiver-Operating Characteristic (WTF?!)

Y-axis: true-positive rate = TP/(TP + FN), a.k.a. recall

X-axis: false-positive rate = FP/(FP + TN)

​

55

Decreasing classification threshold

False-positive rate

True-positive rate

ROC AUC

ROC AUC is the “Area under the curve” – a single number that captures the overall quality of the classifier. It should be between 0.5 (random classifier) and 1.0 (perfect).

​

56

Random ordering

area = 0.5

False-positive rate

True-positive rate

Bias and variance

57

Bias and variance

Bias and variance can be assessed by comparing the error metric on the training set and the test set => always plot learning curves (training set size vs. error)

​

In the ideal case, we want low bias (small training error) and low variance (small test error)

​

58

When more data helps

59

High bias

High variance

More data often beats better algorithms

60

Classification pipeline

61

Data collection

Model assessment

Model selection

Model assessment

Model assessment is the goal of estimating the performance of a fixed model (i.e., the best model found during model selection)

​

Use held-out test set that you’ve never seen during training

62

Important reads

63

64

slides

Feedback

65

Give us feedback on this lecture here: https://go.epfl.ch/ada2018-lec9-feedback

​

• What did you (not) like about this lecture?
• What was (not) well explained?
• On what would you like more (fewer) details?
• What’s your favorite messaging system?
• …

​

Training and testing with heaps of data

66

60% of D

40% of D

learn model

evaluate model

performance metric

Data-efficient training and testing:

Leave-one-out cross-validation

67

test set

(N-1)/N of D

1/N of D

learn model

evaluate model

Repeat N times

average of N runs

Data-efficient training and testing:

k-fold cross validation

68

test set

(k-1)/k of D

1/k of D

learn model

evaluate model

average of k runs

Repeat k times