Supervised learning

Linear Discriminant Analysis

• LDA learns a linear combinations of the features as a way to separate observations from the two classes.
• It is assumed that \(p({\bf{x}}|y=0) \) and \(p({\bf{x}}|y=1) \) follow a similar distribution.
• Furthermore, it is assumed that the two conditional distributions follow a normal distribution with the same covariance matrix \( \Sigma \) and means \( \mu_0 \) and \( \mu_1 \), respectively.
• Given a vector of features \( {\bf{x}} \) , the decision criterion is \(w {\bf{x}} > c \), where \(w\) and \(c\) have a closed-form expression that depends on the parameters of the normal distributions.

Supervised learning

Linear Discriminant Analysis

Computing the prediction with LDA: \[ p(y=1|x) = sigm \left( {\bf{w}}^T ({\bf{x}} - {\bf{x}}_0) \right) \]

Assuming that the a-priori probability of the two classes is the same: \[ \begin{align} w &= \Sigma^{-1} (\mu_1 - \mu_0) \\ {\bf{x}}_0 &= \frac{1}{2} (\mu_1 + \mu_0) \end{align} \]

Supervised learning

Logistic regression

Let the Bernoulli distribution be defined as: \[ Ber({\bf{x}},p) = p^{{\bf{x}}} (1-p)^{1-{\bf{x}}} \; \forall {\bf{x}} \in \{0,1\} \]

and the sigmoid function defined as: \[ g(\eta) = \frac{1}{1+e^{-\eta}} = \frac{e^{\eta}}{e^{\eta}+1} \]

Then the logistic regression classifier is defined as: \[ p(y \mid {\bf{x}}, {\bf{w}}) = Ber(y, g({\bf{w}}^T {\bf{x}})) \]

Supervised learning

Classifiers

1. Decision trees
2. Ensembles
3. Random Forests

Decision Trees: How does it work?

• Each internal node corresponds to a test of the value of one of the input attributes \(A_i\) and the branches from the node are labeled with the possible values of the attribute.
• Each leaf node in the tree specifies a value to be returned by the function.
• A learning algorithm is used to extract the tree structure from the data.

Supervised learning

Decision Trees

1. A decision tree represents a function that takes as input a vector of attribute values and returns a decision (a single output value).
2. It reaches its decision by performing a sequence of tests.
3. Each internal node corresponds to a test of the value of one of the input attributes \(A_i\) and the branches from the node are labeled with the possible values of the attribute.
4. Each leaf node in the tree specifies a value to be returned by the function.
5. For many problems, the decision tree format yields a nice, concise result .

Supervised learning

Learning decision trees from examples

1. The algorithm to learn the decision trees (\(DT\_Learning\)) adopts a greedy divide-and-conquer strategy: always test the most important attribute first.
2. The test divides the problem up into smaller problems that can be solved recursively.
3. The most important attribute is the one that makes the most important difference to the classification of an example.
4. The goal is to get to the correct classification with a small number of tests.
5. To identify the most important attributes, different importance measures are defined.

Supervised learning

Learning decision trees: Split metrics

1. At each step, the DT learning algorithm finds the pair of attribute and cutting point which makes the maximal impurity decrease.
2. Let \(p_i\) denote the probability of a class computed from the observations at a given node.
3. Gini impurity: \[ 1- \sum_{i=1}^{c} p_i^2 \]
4. Entropy: \[ - \sum_{i=1}^{c} p_i^2 log_2(p_i) \]
5. Classification error: \[ 1 - \max_{i \in \{1 \dots c\}} p_i \]

Supervised learning

Learning decision trees: Variants of the algorithm according to split criteria

1. Iterative Dichotomiser 3 (ID3) algorithm is based on Shannon entropy.
2. C4.5 algorithm is based on Gain Ratio which is considered as a normalized Shannon entropy.
3. Classification And Regression Tree (CART) algorithm is based on Gini index.

Ensembles: What is it?

1. An ensemble is a combination of classifiers of the same type.
2. The classifiers are expected to be different in the structure and diverse.
3. Different methods for creating ensembles of classifiers exist. Two of this types are Boosting and Bagging ensembles.
4. Boosting: Each classifier is trained using samples that have been misclassified by the previous classifiers in the ensemble (e.g. Adaboost).

Supervised learning

Bootstrap Aggregating (Bagging)

1. Sets of observations (bootstrap samples) are chosen from the data with replacement (some observations can be in more than one bootstrap sample).
2. From each bootstrap sample, a classifier is learned.
3. The predictions computed from all samples are combined.
4. It is a variant of ensemble classifiers, is a method to reduce the variance of the prediction.
5. When used with decision trees, usually the same greedy algorithm is used to learn each tree, producing similar split points.

L. Breimann. Bagging predictors. Machine Learning. Vol. 24 No. 2. Pp. 123--140. 1996.

Random forests: What it is?

• A random forest is an ensemble of decision trees each one learned on a bootstrap sample.
• Each tree is learned on a bootstrap sample.
• Each is computed using only a subset of variables selected randomly.
• A large number of tree is generally used.

Random forests: How does it work?

• In each sample, at the time of learning a tree, a subset of all variables is selected to determine the best split.
• The class prediction for an example is the majority class among the decision trees classifiers.
• Notably improves the accuracy of decision trees classifiers.
• However, the interpretability of the random forest is very limited.

Random forests: Variable importance

1. Variable importance: A relevant concept in machine learning. It is a measure of how important each variable is for the classification process.
2. Two variable importance measures are usually computed from random forests:
   • Based on the Gini, or other information-based measures.
   • Based on permutations of the variables in the trees and the quantification of their effect on the classification error.
3. Local variable importance can be also computed since son variables are relevant to classify subsets of observations.

Supervised learning

Random forests: Other uses

1. Variable selection
2. Survival analysis (survival random forests)
3. Clustering
4. Imputation of missing data
5. Visualization

Supervised learning

Evaluating classifiers

1. Performance measures
2. Confusion matrix
3. Cross-validation

Evaluating classifiers

Characterizing predictions

• Positive: Predictions have value 1.
• Negative: Predictions have value -1.

Evaluating classifiers

Comparing predictions to labels

• True positive: Class 1 correctly predicted as 1.
• True negative: Class -1 correctly predicted as -1.
• False positive: Class -1 incorrectly predicted as 1.
• False negative: Class 1 incorrectly predicted as -1.

Evaluating classifiers

Accuracy

• P= TP + FP
• N=TN + FN

\[ Accuracy = \frac{TP+TN}{P+N} \]

Evaluating classifiers using metrics

Exercise

• For the table shown above, compute: Accuracy, Precision, Recall, and Balanced accuracy.

Evaluating classifiers: k-fold crossvalidation

5-fold crossvalidation example

• The dataset is divided into five folds. \( Fold_1 = \{1,2\}, Fold_2= \{3,4 \} \dots, Fold_5 = \{9,10\} \).

Evaluating classifiers: k-fold crossvalidation

5-fold crossvalidation example

• In the first step, Train data comprises 4 folds: \( \{ Fold_1, Fold_2, Fold_3, Fold_4 \} \).

Evaluating classifiers: k-fold crossvalidation

5-fold crossvalidation example

• In the first step, Train data comprises 4 folds: \( \{ Fold_1, Fold_2, Fold_3, Fold_4 \} \).
• And Test data comprises 1 fold: \( \{ Fold_5 \} \).

Evaluating classifiers: k-fold crossvalidation

5-fold crossvalidation example

• In the first step, Train data comprises 4 folds: \( \{ Fold_1, Fold_2, Fold_3, Fold_4 \} \).
• And Test data comprises 1 fold: \( \{ Fold_5 \} \).
• So we learn on Train data and predict the Test data .

Evaluating classifiers: k-fold crossvalidation

5-fold crossvalidation example

• In the second step, Train data comprises 4 folds: \( \{ Fold_1, Fold_2, Fold_3, Fold_5 \} \).
• And Test data comprises 1 fold: \( \{ Fold_4 \} \).

Evaluating classifiers: k-fold crossvalidation

5-fold crossvalidation example

• In the second step, Train data comprises 4 folds: \( \{ Fold_1, Fold_2, Fold_3, Fold_5 \} \).
• And Test data comprises 1 fold: \( \{ Fold_4 \} \).
• So we learn on Train data and predict the Test data .

Evaluating classifiers: k-fold crossvalidation

5-fold crossvalidation example

• In the third step, Train data comprises 4 folds: \( \{ Fold_1, Fold_2, Fold_4, Fold_5 \} \).
• And Test data comprises 1 fold: \( \{ Fold_3 \} \).
• So we learn on Train data and predict the Test data .

Evaluating classifiers: k-fold crossvalidation

5-fold crossvalidation example

• In the fourth step, Train data comprises 4 folds: \( \{ Fold_1, Fold_3, Fold_4, Fold_5 \} \).
• And Test data comprises 1 fold: \( \{ Fold_2 \} \).
• So we learn on Train data and predict the Test data .

Evaluating classifiers: k-fold crossvalidation

5-fold crossvalidation example

• In the fourth step, Train data comprises 4 folds: \( \{ Fold_2, Fold_3, Fold_4, Fold_5 \} \).
• And Test data comprises 1 fold: \( \{ Fold_1 \} \).
• So we learn on Train data and predict the Test data .

Evaluating classifiers

k-fold crossvalidation

• Used to estimate the classifier performance (e.g., accuracy) when a validation set is not available.
• The dataset is randomly partitioned into k equal sized folds.
• The cross-validation process is repeated k times. Every time instances in a different fold are predicted.
• Leave-one-out cross-validation (LOOCV): Each fold corresponds to an instance. In every step, one instance is leave out for training and its class predicted.