Optimization for machine learning - riassunto completo corso

Supervised and unsupervised machine learning

Supervised problem: The outcome variable is present to guide the learning process (classification: SVM, discriminant analysis, naive Bayes, logistic classifier; regression: linear, DT, NN, SVR).

Unsupervised problem: Only the features are observed, and there is no measurement of the outcome (clustering: k-means, Gaussian mixtures, NN, hierarchical).

Machine learning fundamentals

Machine learning = statistical modelling + data collection + numerical optimisation.

Bayes' theorem and Bayesian approach

Bayesian approach is very suitable for online, recursive inference since it can be applied recursively.

Loss functions

Loss functions measure the error in predicting a parameter with an estimate. Loss functions can be:

• Quadratic
• Absolute value
• Hit or miss
• Huber loss

Bayesian estimators are defined to minimize the expected loss, under posterior conditional density.

According to the MMSE (Medium Mean Square Error) estimator that minimizes the average squared error:

According to the MAE (Minimum Absolute Error) the definition of median of the posterior is:

The MAP (Maximum A-Posteriori, derived by the hit-or-miss loss function) estimator is the mode of the posterior pdf:

The ML (Maximum Likelihood) is equivalent to the MAP estimator under uniform prior.

Distribution functions and classifiers

The Bernoulli distribution function is:

ML could work poorly for a small number of data: MAP uses an informative prior in order to avoid extreme estimates.

When we want to classify a class of vectors of n features into K classes and assume that all the features are conditionally independent given the class label, we can use an NBC (Naive Bayes Classifier):

The class probability given the input feature can be expressed as:

For Bernoulli problems, we obtain the Bernoulli NBC:

For the MNB (Multinomial Naive Bayes) model, the class-conditional probability mass function of x is:

In the case when the classification is to be made between two classes, i.e. K=2, the above derivations specialize as follows:

In binary classification with BBNB (Binomial Naive Bayes), the discrimination function is linear, and the classification is done according to the sign of:

A trained model can yield values equal to zero when the i-th feature in a class k is zero, thus never classifying the feature vector in the k-th class. To solve this problem, we can modify the results of the ML estimation in Multinomial models by perturbing the observed events counts, making sure that they are all non-zero. This is called Laplace smoothing and is realized via the smoothing parameter a (can be 0 or 1, for Laplace rule of succession).

Model evaluation and error estimation

The application of the ML principle to generate a model yields a technique for estimating the parameter w that is based on the minimization of an empirical loss function L:

The most common case deals with the squared loss:

We can either minimize the training error or the out-sample error (which is more interesting for us).

The test error is the one made on new, unseen data; hence it is the more explicative.

Data is generated by a DGM (Data Generation Mechanism), and we can postulate in this family the EM (Explanatory Model):

The model can be subject to:

• Underfitting: Model is too simple; function cannot be fit satisfactorily by our explanatory model (type 1 error). Fix: more expressive model —> increase number of features d.
• Overfitting: Model is too complex, cannot determine a good EM due to high noise or small sample data (type 2 error). Fix: less expressive model and/or increase N.

Let’s consider the mean square prediction error:

• The first contribution in RED is the bias: expectation of the squared difference between y and the “long-term” expectation for what the learner will do if we averaged over many datasets D.
• The second contribution in BLUE is the variance: expectation of the squared difference between our long-term expectation for learner's performance and what we get in a representative run on a dataset D.

We can empirically estimate the two error contributions in a model (variance and bias) by averaging over many batches of data D, or we can adopt bootstrapping.

Bootstrapping

Create t new datasets by drawing N examples at random with replacement from D and adding them to Dt. When evaluating bias and variance via bootstrapping, we can determine how to improve our model:

• High bias —> model needs to be more complex
• High variance —> model needs to be less complex

Cross-validation

• Hold-out method: Part of the dataset available for training is held out and used as a test set since they are actual unseen data. Unfortunately, this method only gives an estimate of the model’s accuracy and “throws away” a lot of information that would be useful for training.
• k-fold CV: Divide dataset into k different parts, choose one of the k parts and use the other k-1 parts to train the model, use the held-out part to test the model; repeat k times. This yields k estimates of the prediction error e. A good value of k is between 5 and 10. Bias is the average of all e (low is good); variance is the standard deviation of all e (high is bad).

Linear regression and generative models

In linear regression, a generative model output is assumed in the form:

Linear regression model:

Other regression models are:

• Polynomial models
• Sigmoidal models
• Gaussian basis function models

A common way to estimate parameters is to compute the MLE (Maximum Likelihood Estimation), which is the same as maximizing the log-likelihood, which is the same as minimizing the negative of the log-likelihood (NLL). If the noise variance is known, we can compute the MLE of the second term.

The RSS (Residual Sum of Squares) is:

For a given variance, the MLE is found by minimizing the least squares criterion:

If we try to solve the least square optimization problem we find that:

A formal solution of the Normal Equations is:

In the case phi is full rank, is invertible, thus yielding:

This last solution might not be the most efficient if N and/or d are very large.

Robustness in regression models

Gaussian linear regression models can be very sensitive to outliers since squared errors penalize deviations quadratically. One way to achieve robustness (being less sensitive to outliers) is to choose a distribution that has heavy tails, so as to assign higher likelihood to outliers without having them perturb the straight line.

One possibility is to use the Laplace distribution:

The robustness arises from the use of | . | instead of ( . )².

The ML estimate of w is found by minimizing the SAE (Sum of Absolute Residuals):

The solution of the above LR problem can be found via Linear Programming since:

LP is very fast, very accurate, and can deal with huge-scale problems.

Another path in the pursuit of robustness could lead to the minimization of the average Huber loss:

The Huber loss penalizes small residuals quadratically and large residuals linearly, plus it is a smooth and convex function.

The Gauss-Markov theorem states that the LS estimate provides an unbiased estimator having minimum variance.

There can be biased estimators having a smaller mean square error: those trade a little bias for a larger reduction in variance —> shrinkage methods.

Shrinkage methods and ridge regression

Ridge Regression shrinks regression coefficients by imposing a penalty on their size; it minimizes a penalized residual sum of squares:

The regularization ridge is selected via CV and improves the “out of sample” performance, alleviating the weight of the prior. It is a complexity parameter that controls the amount of shrinkage: the larger, the greater the penalty.