Riassunti Machine learning

Machine learning notes

Giacomo Varini 2019/2020

Lezione 2: Introduction to supervised learning

We suppose that there exists an unknown function that maps an input to an output. Goal: learn a good approximation of:

• Input variables are usually called features or attributes.
• Output variables are also called targets or labels.

Tasks:

• Classification if output is discrete.
• Regression if output is continuous.
• Probability estimation if output is a probability.

When supervised learning?

• When human cannot perform the task (e.g., DNA analysis).
• When human can perform the task but cannot explain how (e.g., medical image analysis).
• When the task changes over time (e.g., stock price prediction).
• When the task is user-specific (e.g., movie recommendation).

We want to approximate a function given a data set. The steps are:

1. Define a loss function L.
2. Choose the hypothesis space H.
3. Find in H an approximation h of the function that minimizes L.

NB: If we enlarge the hypothesis space we can approximate without error, but...

Supervised learning can be:

• Parametric: fixed and finite number of parameters.
• Nonparametric: the number of parameters depends on the training set.
• Frequentist: estimate model parameters.
• Bayesian: use prior probabilities to model uncertainty about the estimates.
• Empirical Risk Minimization: minimize error over the training set.
• Structural Risk Minimization: balance training error with model complexity.

Approaches

We distinguish between 3 different approaches:

1. Direct approach: learn directly an approximation of the form (input, output).
2. Generative approach: learns the joint probability distribution and infers conditional density.
3. Discriminative approach: learns directly the conditional probability distribution.

Lezione 3: Linear regression

The simplest linear model can be defined as:

A convenient loss function is the sum of squared errors (SSE). The sum in L is also called residual sum of squares (RSS) and can be written as:

Closed-form optimization of L can be easily derived from its matrix form.

Basis Functions

A linear combination of the input variables may not be enough to model data. But we just need our model to be linear in the parameters! We can define a model using non-linear basis functions. Some examples of basis functions:

Ordinary Least Squares

For linear models, a closed-form optimization of the RSS, known as least squares, can be derived starting from the matrix form of the loss function. We can compute first and second derivative of L() to find the optimal solution. Closed-form optimization (OLS) is not feasible with large datasets. Apply gradient descent.

Least Mean Square (LMS) algorithm:

Multiple Outputs

What happens if our regression problem has multiple outputs, i.e., t is not scalar? It is possible to use the same set of basis functions:

Regularization

Models with low complexity will not fit training data very well → under-fitting. Models with high-complexity will fit training data very well but the model will not behave well on unseen data → over-fitting. The evaluation is usually done by computing the error of the model on a test set. RMSE vs Model Complexity (order): How do we avoid over-fitting?

1. Model selection: choose the proper model.
2. Rely on a very large training set.
3. Regularization: account for model complexity in the loss function.

Over-fitting is always associated with extremely large weight estimates!

How do we extend the loss function?

• L_D() is the usual loss function (e.g., RSS).
• L_C() accounts for model complexity penalizing weights’ dimensions.
• λ is the regularization coefficient.

How do we design L_C()?

Ridge Regression

The loss function is still quadratic with respect to w and closed-form optimization is still possible. What happens to the weights when lambda increases?

Lasso Regression

In this case, closed-form optimization is not possible! Lasso typically leads to sparse regression models: when the regularization coefficient is large enough, some estimates of the weights become equal to zero. We can see regularization as equivalent to minimizing L_D() subject to a constraint:

Let’s visualize constraints of lasso and ridge. Why does lasso lead to sparse models?

Maximum Likelihood (ML)

We can find the best model by maximizing the likelihood. Our model can be defined as convenient to maximize the log-likelihood:

Bayesian approach

1. Define a probabilistic model that maps inputs to outputs.

1. The probabilistic model will include some unknown parameters.
2. We capture our assumptions about unknown parameters with the prior distribution.
3. Observed data is used to estimate the parameters. We want the most probable value of w given the data, i.e., the mode of the posterior, also known as maximum a posteriori (MAP).

How to model the prior? A conjugate prior is the most convenient choice. As a result, the posterior is still Gaussian! When the posterior is Gaussian, the MAP is equal to the mean.

NB: When the prior is infinitely broad, MAP is equal to the ML solution. The ML estimate of w has the smallest variance and the lowest MSE among linear unbiased estimates.

NB: MAP is equivalent to the solution of ridge regression with λ.

How to exploit the Bayesian approach for sequential learning?

1. We compute the posterior with initial data.
2. When additional data is available, the posterior becomes the prior.

With a Bayesian framework, it is possible to compute the probability distribution of the target for a new sample x* by integrating over the posterior distribution. This is often called predictive distribution. Unfortunately, computing the predictive distribution requires knowledge of the posterior distribution, which is usually intractable!

In our example (with normal likelihood and conjugate prior), we can compute the predictive distribution analytically: when the uncertainty associated with parameters (second term) goes to zero and the variance of the predictive distribution depends only on the variance of data.

Observations:

• Analytical integration is possible only using conjugate priors and works for simple models.
• Approximated approaches are used in more general cases (e.g., Monte Carlo integration).

The prior should not give zero or small probabilities to possible values but at the same time also avoid being uninformative. Solution: introduce hyperparameters into the prior.

Linear Models with Fixed Basis Functions

These models have several advantages:

• Allow closed-form solution.
• Tractable Bayesian treatment.

However, they also have several limitations:

• Basis functions are not adaptive with respect to the training data.
• These models suffer from the curse of dimensionality.

Lezione 4: Linear classification

What is classification?

Learn, from a dataset, an approximation of a function that maps input to a discrete class (with k = 1,...,K).

How do we model it?

How do we encode it?

How do we evaluate our approximation?

How do we optimize our approximation?

Classification Approaches

Discriminant Function

• Model a parametric function that maps input to classes.
• Learn parameters from data.

Probabilistic Discriminative Approach

• Design a parametric model.
• Learn model parameters from data.

Probabilistic Generative Approach

• Model class priors.
• Fit models to data.
• Infer posterior with Bayes’ rule.

Linear Classification Models

In linear classification, we will use generalized linear models:

f(∙) is not linear in w: its output is either a discrete label or a probability value. f(∙) partitions the input space into decision regions whose boundaries are called decision boundaries or decision surfaces. These decision surfaces are linear functions of x and w, as they correspond to w_0 + x’_w = const.

Label Encoding

1. A common encoding for two-class problems is a binary encoding: {0,1} = 1 encodes positive class and = 0 encodes negative one. With this encoding, f(∙) represents the probability of the positive class.
2. A possible alternative encoding for two-class problems is {-1,1}. This encoding is convenient for some algorithms.
3. When the problem has K classes, a typical choice is 1-of-K encoding, a vector of length K, with a 1 in the position corresponding to the encoded class. With this encoding, f(∙) represents the probability density over the classes.

Discriminant Linear Function for a Two-Class Problem

How to deal with multiple classes problems?

In a multi-class problem, we have K classes:

1. One-versus-the-rest approach uses K-1 binary classifiers. Each classifier discriminates class i and not class i. Ambiguity: there are regions mapped to several classes.
2. One-versus-one approach uses K(K-1)/2 binary classifiers. Each classifier discriminates between class i and class j. Same ambiguity as before.

A possible solution is to use K linear discriminant functions: Map x to class k if _k > _j for all j ≠ k. No ambiguity. Decision surfaces (DS) are singly connected and convex.

Basis Functions

So far, we considered models that work in the input space (i.e., with x). However, we can still extend models by using a fixed set of basis functions. Basically, we apply a non-linear transformation to map the input space into a feature space. As a result, decision boundaries that are linear in the feature space would correspond to nonlinear boundaries in the input space. This allows applying linear classification models also to problems where samples are not linearly separable. Example: using two Gaussian basis functions.

Least Squares for Classification

Let us consider a K-class problem:

Problems with Least Squares

• Outliers.
• Output distribution.

Least Squares work under the assumption that the output follows a Gaussian distribution!

Perceptron

The perceptron is a linear discriminant model proposed by Rosenblatt. It is devised for a two-class problem, where classes encoding is {-1,1}. The perceptron algorithm aims at finding a decision surface (also called separating hyperplane) by minimizing the distance of misclassified samples to the boundary. Minimization of this loss function can be performed using stochastic gradient descent. Despite a simpler loss function could be used in principle (e.g., number of misclassified samples), these are more complex to minimize.

The Perceptron Criterion is defined as: Samples classified correctly do not contribute to L_. L_ can be minimized using stochastic gradient descent: Since the scale of w does not change the perceptron function, the learning rate is set to 1.

Perceptron Algorithm

A single update reduces the error on the single misclassified sample BUT this does not imply that the entire loss is reduced after each update.

Perceptron Convergence Theorem

If the training data set is linearly separable in the feature space, then the perceptron learning algorithm is guaranteed to find an exact solution in a finite number of steps.

• How many steps? Several steps might be necessary, thus it might be difficult to distinguish between non-separable problems and slowly converging ones.
• Which solution? If multiple solutions exist, the one found by the algorithm depends on the initialization of parameters and the order of updates.

Probabilistic Discriminative Approach

Two-Class Logistic Regression

Maximum Likelihood for Logistic Regression

A convenient loss function to minimize is the negative log-likelihood (also known as cross-entropy error function): Now we have to compute the derivative of it. The gradient of the loss function is:

Due to the nonlinear logistic regression function, it is not possible to find a closed-form solution. However, the error function is convex, and gradient-based optimization can be applied (also in an online learning setting).

In multiclass problems, the probability is modeled by a softmax transformation of the output of K linear functions (one for each class): We can compute the likelihood as:

As for the two-class problem, we can minimize the cross-entropy error function: Then, we compute the gradient for each weight vector:

Observation: if we replace the sigmoid function with a step function, logistic regression leads to the same updating rule of the perceptron algorithm.

Lezione 5: Model evaluation, selection and ensembles

Is the loss function computed in a good way to evaluate a model? No! This is the performance measure we want to compute:

Bias-Variance Decomposition

The Bias-Variance is a framework to analyze the performance of models.

• Model Variance: If we sample several datasets, we will learn different models. Variance measures the difference between each model learned from a particular dataset and what we expect to learn. Decreases with simpler models. Decreases with more samples.
• Model Bias: Bias measures the difference between truth and what we expect to learn. Decreases with more complex models.

NB: Data noise is the variance of data and does not depend on data sampling nor on the model complexity.

Bias-Variance for K-NN

Bias-Variance analysis allows us to understand how k affects performance:

• The data noise is the irreducible error.
• The model variance decreases as k increases.
• The model bias depends on the smoothness of the problem space, but in general, increases as k increases (because it increases the distance of the neighbors used to compute).

Regularization and Bias-Variance

Lasso outperforms Ridge regression when few features are related to the output.

Prediction Error

So what do we do in practice?

Test Error

1. Split randomly data into a training set and test set.
2. Estimate model parameters.