Linear regression

Question 1

Data-set

Answer 1

Supervised Learning problem:
{(x1,y1),…,(xN,yN)}
xi app R^d
yi app R

Question 2

Hypothesis

Answer 2

Assuming a linear relation between x and y
h(x) = sum(i=0,d) wi*xi = w’ x

where
w = [w0, w1, …, wd]’
x = [x0, …, xd]’

Question 3

Learning algorithm

Answer 3

Minimize wrt h the sum of the squared distances between the data and the line h(x)

In theory, minimization of the out of sample error:
Eout(h) = E[ (h(x) - f(x))^2 ]

Since the probability distribution of f is unknown, in practice, minimization of the in sample error:
Ein(h) = 1/N * sum(n=1,N) (h(xn) - yn)^2

Question 4

Analytical formula that solves the problem

Answer 4

Least squares formula:
w^ = (X’ X)^-1 X’ Y

where X is the input matrix N x d+1
Y is the output vector app R^N

Question 5

Generalization

Answer 5

Theorem:

Eout(h) = E[ (h(x) - f(x))^2 ] = Ein(h) + O(d/N)