Optimization - Linear Models

Optimization - Linear models

Grégoire Passault

Grégoire Passault
Introduction

Introduction

Grégoire Passault
Introduction

Machine Learning

Machine learning is often divided into three categories

  • Supervised learning
  • Unsupervised learning
  • Reinforcement learning
Grégoire Passault
Introduction
⭐ Supervised learning ⭐
Given some example input and outputs, the goal is to learn a function that maps inputs to outputs.
Grégoire Passault
Introduction
Unsupervised learning
Given some data, the goal is to learn the underlying structure of the data.
Grégoire Passault
Introduction
Reinforcement learning
By interacting with an environment, the goal is to learn a policy that maximizes a reward.
Grégoire Passault
Introduction

Supervised learning

Input:
A dataset where is the input and is the output.

Output:
A function that maps inputs to outputs.

If the output is a continuous value, we call this a regression problem, if it is a category (like cat or dog), we call this a classification problem.
Grégoire Passault
Introduction

Method

Step 1: choose a model

We first choose a model , which is a specific function that depends on some parameters .

Step 2: choose a metric

We then decide a metric to evaluate how well the model is performing.

Step 3: train the model

Finally, we search for the parameters that minimize the metric on the dataset .

Grégoire Passault
Introduction

Outline

Approach Pros Cons
Exact solution Efficient Solvable equations, overfitting
Least square Efficient Linear model, quadratic error
Netwon's method Any model Suboptimal, can diverge
Gradient descent Any model Suboptimal, slow
Grégoire Passault
Linear models

Linear models

Grégoire Passault
Linear models

Linear models

Linear models are those of the forms:

Where are some functions of the input .

Note: the models are linear in the parameters , and not in the input .

Grégoire Passault
Linear models

Examples

⚙️ Which models are linear ?

Grégoire Passault
Linear models

Examples

⚙️ Which models are linear ?

Grégoire Passault
Exact solutions

Exact solutions

Grégoire Passault
Exact solutions

Exact solutions

Given some dataset, we can first search for a solution that exactly fits the data.

In that case, for all .

This approach is especially useful for interpolation.
Grégoire Passault
Exact solutions

Affine fitting

Let's start with the simplest example:

⚙️ What is the model ? How to find ?

Grégoire Passault
Exact solutions

Affine fitting

First, let's define the model:

We can then write the equations:

Grégoire Passault
Exact solutions

Affine fitting

This yields the system of equations:

In matrix form:
Grégoire Passault
Exact solutions

Affine fitting

The solution is then:

Grégoire Passault
Exact solutions

Cubic fitting

We can also impose derivatives:

⚙️ What are and ?

Grégoire Passault
Exact solutions

Cubic fitting

We have:

Then:
Grégoire Passault
Exact solutions

Quintic fitting

Now, what if we have 6 data points and want to find a model ?

⚙️ How do you expect to look like ?

Grégoire Passault
Exact solutions

Quintic fitting

The output will look like this:

Grégoire Passault
Exact solutions

Quintic fitting

We can notice the following:

  • With exact solution, we need as much parameters as data points
  • The model is overfitting the data, and will likely perform poorly on new data
Grégoire Passault
Least squares

Least squares

Grégoire Passault
Least squares

Linear regression

Suppose we have many data points and wand to find :

Grégoire Passault
Least squares

Linear regression

If we write the system as seen before:

Problem: is not square, so we cannot invert it.
This is because we only have two parameters, but many data points.

Grégoire Passault
Least squares

Minimizing an error

Idea: instead of finding that exactly fits the data, we can find that minimizes an error.

We will call this error .
The most common error is the least squares error:
Grégoire Passault
Least squares

Minimizing an error

We then want to find that minimizes :

Grégoire Passault
Least squares

Least squares

We have a linear model and a square error.
is then a quadratic function of :

is obtained where all the derivatives of is zero.

Grégoire Passault
Least squares

Back to linear regression

Back to the linear regression problem:

⚙️ Can you find an equation to find and ?

Grégoire Passault
Least squares

Solving linear regression

First, let's write

We can expand it to:

Then, we can compute the derivatives with respect to and :
Grégoire Passault
Least squares

Solving linear regression

To cancel the derivatives, we then have:

Grégoire Passault
Least squares

Solving linear regression

Thus:

Substitute in the second equation:
Grégoire Passault
Least squares

Solving linear regression

This yields:

Grégoire Passault
Least squares

Example

We can then write some code to solve the linear regression problem:

Grégoire Passault
Least squares

A more general form

Remember that we can write the exact form equation as:

The loss function is then:
Grégoire Passault
Least squares

A more general form

This expands to:

The derivatives can then be computed as:
Grégoire Passault
Least squares

A more general form

Setting the derivative to zero yields:

And thus:
Grégoire Passault
Least squares

A more general form

The least square solution can then be obtained with the exact same approach as the exact solution.

is replaced by .

is called the pseudo-inverse of .

import numpy as np
np.linalg.inv(A) # inverse
np.linalg.pinv(A) # pseudo-inverse
Grégoire Passault
Least squares

Linear regression with pseudo-inverse

We can then write some code using numpy.linalg.pinv to solve the linear regression problem. Yielding the same result:

Grégoire Passault
Practical exercices

Practical exercices

Grégoire Passault
Practical exercices

Let's write some Python!

On the next slide, you will find data and models.

⚙️ Using the linear regression example, you can write some code to find the parameters used!

Hint: to load the data, you can use:

import numpy as np
data = np.loadtxt('data.csv')
Grégoire Passault
Practical exercices

Let's write some Python!

Grégoire Passault
Practical exercices

Practical case: identifying a RR robot

Let us consider the following RR robot:

: position of its base. : lengths of its arms.
: angles of its arms. : position of its end-effector.

⚙️ Can you express as function of other variables ?

Grégoire Passault
Practical exercices

Practical case: identifying a RR robot

We have:

The model is linear in the parameters .

Grégoire Passault
Practical exercices

Practical case: identifying a RR robot

Here are some data generated with this script.

They contain noisy measurements of for different values of .

import numpy as np
data = np.loadtxt('data/rr_data.csv')
alpha, beta, x_e, y_e = data[0] # first data

⚙️ Write some code to retrieve parameters .

Grégoire Passault