Week 3 - Supervised learning: regression

Question 1

Regression

Answer 1

mapping inputs to outputs. Now, given a new input, predict
the output

Regression deals with continuous (real-valued) outputs.

Question 2

Linear regression
- standard formula

Answer 2

y = mx + b
* We need a cost function! (e.g. SSE)

Question 3

But how do we actually find the parameters m and b in the function y=mx+b?

Answer 3

You want to find the right parameters for the function f(x) = c0 + c1x + c2x2 + c3x3 + … + ckxk, so that f(x) is as small as possible

Question 4

Overparameterizing a model leads
to …

Answer 4

Overparameterizing a model leads
to overfitting

Question 5

optimization (or minimization) problem

Answer 5

Let f(p1, p2, …, pk) be a function that maps our parameter values to the sum of
squared errors.

Find the values p1, p2, …, pk that minimize f(p1, p2, …, pk).

Function f returns one value (sum of squared errors).

In other words, we need to minimize the difference between human data and the
data generated by our computational model

Question 6

How would you go about finding p1, p2, …, pk?

Answer 6

Grid search (aka parameter sweep)

Question 7

Grid search aka parameter sweep
Why is this an exhaustive search?

Answer 7

Grid Search is an exhaustive search, meaning it looks at all possible combinations of parameter values within a specified range.

Question 8

Grid search aka parameter sweep

Answer 8

With precision j, we evaluate the function in increments of 1/j of the parameter range.

Example:

Let’s say you have a parameter ‘p’ with a range [200, 400].

Choose precision ‘j’ as 101.

Evaluate the objective function at 101 points within the range, with ‘p’ values like [200, 202, …, 400].

For each combination, you calculate how well your model performs.

Question 9

Grid search aka parameter sweep
- Con (1)

Answer 9

Con of grid search:

Curse of dimensionality*

Question 10

To do an exhaustive search over k parameters with precision j, we need to evaluate
the function … times.

Answer 10

To do an exhaustive search over k parameters with precision j, we need to evaluate
the function jk times.

• This is considered computationally inefficient.

Question 11

simplex

Answer 11

A simplex is a shape defined by connecting
k + 1 vertices in k-dimensional space.

Question 12

Nelder–Mead (aka simplex) algorithm uses (4 steps) to find a
minimum.

Answer 12

uses reflection, expansion,
contraction and shrinking to find a
minimum.

Question 13

Nelder-Mead algorithm:

Simplex
What kind of simplex?
- zie sheet

Answer 13

In the context of Nelder-Mead, we’re dealing with a 2D simplex, which means a triangle with three vertices.

Example: In 2D space with parameters m and b, our simplex is a triangle with vertices B, G, and W.

B = Best

G = Good

W = Worst

Question 14

Nelder-Mead algorithm:

Reflection

• zie sheet

Answer 14

Reflect the worst vertex (W) through the midpoint of the line formed by the best and good vertices (B and G) to get a new vertex (R).

Question 15

Nelder-Mead algorithm:

Expansion

(If f(B) < f(R) < f(G))

• zie sheet

Answer 15

Groter dan = beter!

Replace vertex W with vertex R

Question 16

Nelder-Mead algorithm:

Contraction

• zie sheet

Answer 16

If R is worse than the current best point (B), contract the worst point (W) towards R (towards ¼ of the line between W and R), call this point C1.

If the contracted point (C1) is better than the current worst, replace W; otherwise, shrink the simplex toward B.

Question 17

Nelder-Mead algorithm:

Shrinking

• zie sheet

Answer 17

If the contraction doesn’t improve the simplex, shrink it towards the best point (B).

Question 18

Nelder-Mead algorithm:

Rules in comparison of function values

If f(B) < f(R) < f(G)

Answer 18

replace W with R.

Question 19

Nelder-Mead algorithm:

Rules in comparison of function values

If f(R) < f(B)

Answer 19

expand further to E.

If f(E) > f(R), replace W with E; If f(E) < f(R), replace W with R.

Question 20

Nelder-Mead algorithm:

Rules in comparison of function values

If f(B) < f(G) < f(R)

Answer 20

contract W. If the contracted point is better, replace W; otherwise, shrink the simplex toward B.

Question 21

Nelder-Mead algorithm:

Convergence

Answer 21

Continue iterating through these steps until the algorithm converges. Convergence is achieved when the shortest edge of the simplex falls below a certain size.