How is our preferred car positioned?

FIAT 500 C, 1953

Regression

Regression

Segment C: price vs. weight/power

20,000 25,000 30,000 35,000 40,000 45,000

12,00 13,00 14,00 15,00 16,00 17,00 18,00 19,00

w eight/pow er (g/W)

price (M£)

How is our preferred car positioned?

Rover 45

Segment C: price vs. weight/power

20,000 25,000 30,000 35,000 40,000 45,000

12,00 13,00 14,00 15,00 16,00 17,00 18,00 19,00

w eight/pow er (g/W)

price (M£)

Regression

trend

How is our preferred car positioned?

Rover 45

Regression

Definition Let Ψ be a class of curves of IR

. We call trend or regression line of the set A in the class Ψ the element C

of Ψ that lies at a

minimum distance from A

For any x, y ∈ IR

, let d(x, y) be the distance of x from y based on some metric, with

d(x, y) > 0, d(x, y) = 0 ⇔ x = y (non negativity)

d(x, y) = d(y, x) (symmetry)

d(x, y) + d(y, z) > d(x, z) (triangle inequality) Let C be a curve of IR

, x ∈ IR

, A discrete and finite ⊆ IR

Definition d(x, C) = min{d(x, y): y ∈ C} is called distance of x from C Definition d(A, C) = Σ d(x, C) is called distance of A from C

x∈A

1

|A|

normal to C by P_k

x_k y_k

d

= d((x

, y

), C) = |y

– f(x

)|

On the metric

Definition Let Ψ be a class of curves of IR

. We call trend or regression line of the set A in the class Ψ the element C

of Ψ that lies at a

minimum distance from A The metric chosen depends on the

situation modeled

1) If in an experiment all the record entries are affected by error, it is convenient to define the distance as the length of the shortest segment touching both P

and C

2) If uncertainty affects just the

dependent variable y, one can choose the absolute value of the difference between the y-coordinate of P

and the value attained by the curve in x

x y

P_k

f(x_k) d((x_k, y_k), C)

x_k y_k

Linear regression

Definition Let Ψ be a class of curves of IR

. We call trend or regression line of the set A in the class Ψ the element C

of Ψ that lies at a

minimum distance from A If the curve is a straight line y = c

x + c

, we speak of linear regression.

Consider case (2), in which the distance of P

= (x

, y

) ∈ A from C is given

by the absolute value of the difference between the y-variable of P

and the value attained by the line in x

, namely

d

= |y

– c

x

– c

|

x y

c₁x_k – c₀ d_k

P_k

x_k y_k

Linear regression

If the curve is a straight line y = c

x + c

, we speak of linear regression.

Consider case (2), in which the distance of P

= (x

, y

) ∈ A from C is given

by the absolute value of the difference between the y-variable of P

and the value attained by the line in x

, namely

d

= |y

– c

x

– c

|

x y

c₁x_k – c₀ d_k

Basically, the distance d

of P

from C depends on c

and c

Also the choice of the straight line depends on these two coefficients.

Hence a line at a minimum distance from the point set {P

, P

, …, P

} is one given by those c

and c

that minimize

P_k

(d

+ d

+ … + d

)

1 m

x_k y_k

Linear regression

x y

c₁x_k – c₀ d_k

Basically, the distance d

of P

from C depends on c

and c

Also the choice of the straight line depends on these two coefficients.

Hence a line at a minimum distance from the point set {P

, P

, …, P

} is one given by those c

and c

that minimize the sum d

+ d

+ … + d

Formulation:

min d

+ … + d

d

> y

– c

x

– c

d

> c

x

+ c

– y

…

d

> y

– c

x

– c

d

> c

x

+ c

– y

d

= |y

– c

x

– c

|

P_k

x_k y_k

Linear regression

x y

c₁x_k – c₀ d_k

Basically, the distance d

of P

from C depends on c

and c

Also the choice of the straight line depends on these two coefficients.

Hence a line at a minimum distance from the point set {P

, P

, …, P

} is one given by those c

and c

that minimize the sum d

+ d

+ … + d

Formulation:

min d

+ … + d

d

+ x

c

+ c

> y

d

– x

c

– c

> – y

…

d

+ x

c

+ c

> y

d

– x

c

– c

> – y

d

= |y

– c

x

– c

|

P_k

∂ d

(c

, c

)

∂ c

= – Σ

^{2( y}

^{– c}

^x

^{– c}

⁾

k=1

1 m

c₀ z = d²(c₀, c₁)

c₁

Linear regression

c₁^*

c₀^*

* The surface z = d

(c

, c

) is an up-concave paraboloid of IR

d

(c

, c

) = (d

+ … + d

)

m

The minimum (c

, c

) ∈ IR

of d

(c

, c

) can be computed by annealing the partial derivatives in c

and c

∂ d

(c

, c

)

∂ c

= –

Σ ^2x

( y

– c

x

– c

)

m

m

= ( ^c

Σ ^x

^{+ c}

Σ ^x

^– Σ ^x

^y

)

m

k=1

m

k=1

m

k=1

2 m

= ( ^c

Σ ^x

^– Σ ^y

) ^{+ 2c}

m

k=1

m

k=1

2 m

x^uy^w = ¹

Σ

m

m

k=1

x c

+ x

c

= xy

c

+ x c

= y

Alternatively, one can define the distance d(A, c

, c

) = d(c

, c

) of y = c

x + c

from the set A via

d

= (y

– c

x

– c

)

= ( ^c

Σ ^x

^{+ c}

Σ ^x

^– Σ ^x

^y

)

m k=1

m k=1

m k=1

2 m

= ( ^c

Σ ^x

^– Σ ^y

) ^{+ 2c}

m k=1

m k=1

2 m

c₀ z = d²(c₀, c₁)

c₁

Linear regression

c₁^*

c₀^*

* This is known as the least squares method d

(c

, c

) = (d

+ … + d

)

m

x^uy^w = ¹

Σ

m

m

k=1

x c

+ x

c

= xy

c

+ x c

= y

d

= (y

– c

x

– c

)

Solving the linear systems returns the values of c

and c

, and hence the regression line

y = c

x + c

c₀ z = d²(c₀, c₁)

c₁

Linear regression

c₁^*

c₀^*

* This is known as the least squares method d

(c

, c

) = (d

+ … + d

)

m

d

= (y

– c

x

– c

)

x y

d₁²

d₄²

d₃²

d₂²

P₃ P₂

P₁

P₄

x_k y_k

Polynomial regression

Let us now pass to a curve of the form y = c

x

+ c

x

+ … + c

x + c

If we set:

x y

f(x_k) d_k

P_k

d

= |y

– c

x

– c

x

– … – c

| the parameters of C can be obtained by solving the LP

min d

+ … + d

d

> y

– c

x

– c

x

– … – c

d

> y

– c

x

– c

x

– … – c

d

> c

x

+ c

x

+ … + c

– y

d

> c

x

+ c

x

+ … + c

– y

t t–1

t t–1 t t–1

t t–1

…

x y

Other non linear models

d

= |g

(y

) – c

f

(x

) – … – c

f

(x

)|

can be determined by solving the LP y = g [ Σ ^c

f

(x) ]

t i=1

min d

+ … + d

d

> g

(y

) – c

f

(x

) – … – c

f

(x

) d

> c

f

(x

) + … + c

f

(x

) – g

(y

)

…

d

> g

(y

) – c

f

(x

) – … – c

f

(x

) d

> c

f

(x

) + … + c

f

(x

) – g

(y

) Generalizing, a model of the type

with f

, g known functions, g monotone invertible and

or, with minimum squares, by defining

d

= [g

(y

) – c

f

(x

) – … – c

f

(x

)]

d

= [g

(y

) – c

f

(x

) – … – c

f

(x

)]

and solving the relevant

linear system

7,2

23,2

62,9

122,8

203,2

0 50 100 150 200 250

1810 1850 1890 1930 1970 2010

Example

Let us try and estimate by the linear model y = c

x + c

the growth of US population

?

min

Σ

m k=1

Example

7,2

23,2

62,9

122,8

203,2

-26,6

23,2

73,0

122,8

172,6

222,4

-50 0 50 100 150 200 250

1810 1850 1890 1930 1970 2010

The outcome is clearly unacceptable: it even provides a negative value for the year 1810!

min

Σ

m k=1

7,2

23,2

62,9

122,8

203,2

0 50 100 150 200 250 300

1810 1850 1890 1930 1970 2010

Example

Let us then try an exponential model of the type y = e

?

min

Σ

m k=1

7,2

23,2

62,9

122,8

203,2

10,1

23,2

53,4

122,8

282,5

0 50 100 150 200 250 300

1810 1850 1890 1930 1970 2010

Example

In practice, this amounts to apply a linear regression to the points (x

, log(y

))

The model forecast is that in 2010 the US population will reach 650 million

min

Σ

m k=1

Example

The minimum squares method provides a slightly reduced trend, and a forecast of 589,1 million inhabitants for the year 2010

7,2

23,2

62,9

122,8

203,2

9,1

21,0

48,3

111,2

256,0

0 50 100 150 200 250 300

1810 1850 1890 1930 1970 2010

min

Σ

m k=1

Linear regression in IR ⁿ

x

x

The locus of points x of IR

whose scalar product by a given versor

u = (u

, …, u

) returns a known value β is a hyperplane H

The points of H fulfill the linear equation

u

x

+ … + u

x

= u

x =

or equivalently

a

x

+ … + a

x

= a

x = b where

u

x β

b =

|a| =

√ a

+ … + a

u =

|a|

If distance is expressed as in case (2), then we can describe the hyperplane by

its explicit form x

= c

+ c

x

+ … + c

x

ending up with an LP or a linear

system similar to that seen in IR

Linear regression in IR ⁿ

x

x

The locus of points x of IR

whose scalar product by a given versor

u = (u

, …, u

) returns a known value β is a hyperplane H

The points of H fulfill the linear equation

u

x

+ … + u

x

= u

x =

or equivalently

a

x

+ … + a

x

= a

x = b where

β

b =

|a| =

√ a

+ … + a

u =

|a|

If distance is expressed as in case (1), things get a bit more complicated:

d^k

u

x₁^k x₂k ux

k

d

= |u

x

–

|

x^k

Linear regression in IR ⁿ

x

x

The optimization problem reads min d

+ … + d

β

If distance is expressed as in case (1), things get a bit more complicated:

x^k d^k

u

x₁^k x₂k ux

k

d

= |u

x

–

| d

> x

u

+ … x

u

–

d

>

– x

u

+ … x

u

d

>

– x

u

+ … x

u

d

>

– x

u

+ … x

u

u

+ … + u

= 1

…

and is a non linear problem

Linear regression in IR ⁿ

x

x

The optimization problem reads min d

+ … + d

However, the information carried by versor u is redundant

For one, since

is unconstrained we can limit our attention to the directions belonging to a semi sphere

x^k d^k

u

x₁^k x₂k

d

> x

u

+ … x

u

–

d

>

– x

u

+ … x

u

d

>

– x

u

+ … x

u

d

>

– x

u

+ … x

u

u

+ … + u

= 1

…

and is a non linear problem

Linear regression in IR ⁿ

x

x

The optimization problem reads min d

+ … + d

However, the information carried by versor u is redundant

And in the very end, we are just interested to find a direction: to this purpose, also vectors a with distinct modules can be used

x^k d^k

a

x₁^k x₂k

d

> x

u

+ … x

u

–

d

>

– x

u

+ … x

u

d

>

– x

u

+ … x

u

d

>

– x

u

+ … x

u

u

+ … + u

= 1

…

and is a non linear problem

u

Linear regression in IR ⁿ

x

x

min d

+ … + d

x^k d^k

x₁^k x₂k

d

> x

a

+ … x

a

– b d

> b – x

a

+ … x

a

d

> b – x

a

+ … x

a

d

> b – x

a

+ … x

a

a

+ … + a

= 1, a

> 0

…

This calls for solving 2

linear problems in the n + 1 variables a

, …, a

, b

a

Note that d

= |u

x

–

| = |

x

–

|

|a|

But for any choice of a there exists a real b such that d

= |a

x

– b|

ax

k

Efficiency curve

5,4 5,1

5,0 5,6

5,2 consumption (l×100km) 4,8

8,9 10,6

10,4 8,5

9,8 12,4

price (K€)

6 5

4 3

2 1

Model

Let us make the (basically wrong) assumption that clients choose a car adopting a rational behaviour, and, prior to purchase, compute its cost on a five-year basis For the sake of simplicity, suppose that

• costs are given by the car price and by fuel consumption

• the car yearly covers 20.000 km

• a litre of fuel costs 1,3€

cost(k) = price(k) + 5

consumption(k)

200

1,3

Suppose that, since less fuel consumption means less pollution, we are interested

in finding the best solutions under both respects

Efficiency curve

5,4 5,1

5,0 5,6

5,2 consumption (l×100km) 4,8

15,92 17,23

16,90 15,78

16,56 18,64

cost (K€)

6 5

4 3

2 1

Model

costi vs. consumi

4,7 4,8 4,9 5,0 5,1 5,2 5,3 5,4 5,5 5,6 5,7

15,500 16,000 16,500 17,000 17,500 18,000 18,500 19,000 costo (k€)

consumo (lt x 100 km)

We look for a math model giving the cost c(x) associated with consumption x as

c(x) = a/x + bx + c (a, b, c > 0)

We look for a math model giving the cost c(x) associated with consumption x as

c(x) = a/x + bx + c

(a, b, c > 0)

more consumption less technology

more consumption more fuel

costi vs. consumi

4,7 4,8 4,9 5,0 5,1 5,2 5,3 5,4 5,5 5,6 5,7

15,500 16,000 16,500 17,000 17,500 18,000 18,500 19,000 costo (k€)

consumo (lt x 100 km)

Efficiency curve

5,4 5,1

5,0 5,6

5,2 consumption (l×100km) 4,8

15,92 17,23

16,90 15,78

16,56 18,64

cost (K€)

6 5

4 3

2 1

Model

+ bx_k + c

a x_k

x_k y_k

d

= y

–

– bx

– c > 0

x_k

c(x) = a/x + bx + c

formulation

Efficiency curve

a + x

b + x

c < x

y

…

a + x

b + x

c < x

y

a, b, c > 0

2

2

5,4 5,1

5,0 5,6

5,2 consumption (l×100km) 4,8

15,92 17,23

16,90 15,78

16,56 18,64

cost (K€)

6 5

4 3

2 1

Model

min d

+ … + d

d

= y

–

– bx

– c > 0

x_k

a = 75,678 b = 0,353 c = 0 a = 75,678 b = 0,353 c = 0

optimal solution

max ( + … + )

a + (x

+ … + x

) b + c

1

1 x_n

Efficiency curve

consumption vs. cost

14,000 16,000 18,000 20,000 22,000

4 4,5 5 5,5 6

consumption (lx100km)

cost (k€)

efficiency curve sample