Introduction to Machine Learning

1. Review of Probability Models

Let us take a closer look at 3 discrete distributions – Bernoulli distribution, Binomial

distribution, and Multinomial distribution.

1.1 Binomial Distribution:

Consider an experiment which generates 2 outcomes: Category-1 or Category-2. Let

us denote these categories as (1 , 0) and (0 , 1) respectively. Assume that
P ( Z =( 1 ,0 ) )= p1, and P ( Z =( 0 ,1 ) )= p2. We write this distribution as

Z Categorical ( p1 , p 2) .

Consider n runs of this experiment. This will produce a sequence Z1 , … , Z n where

Zi ∈ { ( 1, 0 ) , ( 0 , 1 ) }. Suppose we get x 1 elements in category-1, and x 2 elements in
category-2.

n!
We claim that is the number of distinct ways to obtain x 1 elements in
x1 ! x 2 !
category-1, and x 2 elements in category-2. This can be seen as follows:

n!
 Out of n place holders we can choose x 1 place holders in ways.
x1 ! ( n−x 1) !
 Out of the remaining n−x 1 place holders we can choose x 2 place holders in
(n−x 1)!
ways. But we know that x 1+ x2 =n, so this reduces to
x2 ! ( n−x 1−x 2) !
(n−x 1)!
.
x2 !

Therefore, the total number of combinations are:

n! (n−x 1)!
×
x1 ! ( n−x 1) ! x2!

This simplifies to the desired expression.

n!
The number has a curious relationship with the Binomial expansion:
x1 ! x 2 !

n!
( a+ b )n= ∑ x1! x2 !
x x
a b
1 2

x 1+ x2=n
x 1 , x 2≥ 0

The expression on the right is actually a double sum subject to the constraint
x 1+ x2 =n:
 n n
n!
∑ ∑ x1 ! x2 !
ax bx 1 2

x1=0 x 2=0
x 1+ x2=n

In the above expression for the binomial expansion, put a= p1, and b= p2 to obtain

n!
1= ∑ x1! x2!
x x
p1 p2 1 2

x 1+ x2=n
x 1 , x 2≥ 0

Let us define

{
n!
∑ x1 ! x2 !
p1x px2 ; whenever x 1 + x 2=n
1 2

f ( x1 , x2)= 0≤ x 1 ≤n
0≤ x 2 ≤n
0; whenever x 1 + x 2 ≠ n

In view of the Binomial expansion, we have

1= ∑ f (x 1 , x 2)
0≤ x 1 ≤n
0 ≤ x 2 ≤n

We say that X =(x 1 , x 2 ) has a Binomial distribution with parameters p1, and p2, and write

X Binomial(n , p1 , p 2)

(Note that p2=1−p 1 so we can omit p2 and keep only a single parameter p1)

We call the above as a “Categorical View” of the Binomial distribution. Next, we relate it to a
more familiar view of counting the number of successes in n runs of a binary experiment.

Here, our experiment produces either “Failure” or “Success”. Denote “Failure” by 0; and
“Success” by 1. Such experiments are called Bernoulli trials.

Performing this experiment n times would result in a sequence Z1 , Z 2 , … , Z n.

We have Zi =1 if the i th run of the experiment results in a success; else Zi =0.

Assume that probability of success is p. Hence probability of failure is 1− p .

Clearly, the sum Z1 +…+ Z n counts the number of times “Success” appears. This defines a
random variable Z that can take values 0 , 1 , … ,n .

Observe that Z=x means that there are x number of terms of this sequence are 1. This can

happen in ( nx) distinct number of ways. The probability of occurrence of each configuration is
x n−x
p ( 1− p ) . So the overall probability that Z=x is given by:

P ( Z=x ) = ( nx) p ( 1−p )

x n−x
 We set the above probability to 0 in case x ∉ {0 , 1 , … , n} and say that the random variable
Z follows a Binomial distribution with parameters n and p. In symbols, we write:
Z Binomial(n , p)
n! x n− x
It can be easily seen that the expression p ( 1− p ) is equivalent to
x ! ( n−x ) !
n! x x
p 1 p 2 where x 1+ x2 =n and p1 + p2=1.
1 2

x1 ! x 2 !

Therefore, the Categorical View is equivalent to the Sum of Bernoulli trials view.

1.2 Trinomial Distribution:

Instead of working with 2 categories, lets now work with 3 categories: (1 , 0 , 0) , (0 , 1 , 0) , and
(0 , 0 , 1) . Assume that P ( Z =( 1 ,0 , 0 ) ) = p1, P ( Z =( 0 ,1 , 0 ) ) = p2, and P ( Z =( 0 , 0 ,1 ) ) = p3. We write
this distribution as Z Categorical ( p1 , p 2 , p3 ).

Consider n runs of this “generalized Bernoulli trial”. This will produce a sequence Z1 , … , Z n where
Zi ∈ { ( 1, 0 , 0 ) , ( 0 , 1, 0 ) , ( 0 , 0 , 1 ) }. Suppose we get x 1 elements in category-1, x 2 elements in
category-2, and x 3 elements in category-3. Then the probability is given by:

n! x x x
p1 p2 p 3
1 2 3

x1 ! x 2 ! x 3 !

n!
Note that is the number of distinct ways to obtain x 1 elements in category-1, x 2
x1 ! x 2 ! x 3 !
elements in category-2, and x 3 elements in category-3. This can be seen as follows:

n!
 Out of n place holders we can choose x 1 place holders in ways.
x1 ! ( n−x 1) !
 Out of the remaining n−x 1 place holders we can choose x 2 place holders in
(n−x 1)!
Ways.
x2 ! ( n−x 1−x 2) !
 Lastly, out of the remaining n−x 1−x 2 place holders we can choose x 3 place
(n−x 1−x 2)!
holders in Ways. But we know that x 1+ x2 + x 3=n , so
x3 ! ( n−x 1−x 2−x 3 ) !
(n−x 1−x 2)!
this reduces to .
x3 !

Therefore, the total number of combinations are:

 n! (n−x 1)! ( n−x 1−x 2)!
× ×
x1 ! ( n−x 1) ! x2 ! ( n−x 1−x 2) ! x3 !

This simplifies to the desired expression.

n!
The number has a curious relationship with the Trinomial expansion:
x1 ! x 2 ! x 3 !

n!
( a+ b+c )n= ∑ x1 ! x2 ! x3 !
x x x
a b c 1 2 3

x 1+ x2 +x 3=n
x 1 , x 2 , x3 ≥ 0

The expression on the right is actually a triple sum subject to the constraint x 1+ x2 + x 3=n :
n n n
n!
∑∑ ∑ x 1 ! x 2 ! x3 !
ax bx c x
1 2 3

x1=0 x 2=0 x 3=0

x 1+ x 2+ x3=n

In the above expression for the trinomial expansion, put a= p1, b= p2, and c= p3 to obtain

n!
1= ∑ x x
p p p1

x1 ! x 2 ! x 3 ! 1 2 3
x 2 3

x 1+ x2 +x 3=n
x 1 , x 2 , x3 ≥ 0

Let us define

{
n!
∑ x x x
p p p ; whenever x1 + x 2 + x 3=n
x 1 ! x 2 ! x3 ! 1 2 3
1 2 3

0 ≤x 1 ≤n
f ( x 1 , x 2 , x3 ) = 0 ≤x 2 ≤n
0 ≤x 3 ≤n
0; whenever x1 + x 2 + x 3 ≠ n

In view of the Trinomial expansion, we have

1= ∑ f (x 1 , x 2 , x 3 )
0≤ x 1 ≤n
0 ≤ x 2 ≤n
0 ≤ x 3 ≤n

We say that X =(x 1 , x 2 , x 3 ) has a trinomial distribution with parameters p1, p2, and p3, and write

X Trinomial (n , p1 , p 2 , p3 )

1.3 Multinomial Distribution:

Let us now consider k categories: c 1=(1 ,0 , … , 0), c 2=(0 , 1, 0 , … , 0), …, c k =(0 , … , 0 , 1). Assume
that P ( Z =c i )= pi. Since p1 + p2 +…+ pk =1, we see that P satisfies all axioms of a probability
distribution We write this distribution as Z Categorical ( p1 , p 2 , p3 ).

Consider n runs of this “generalized Bernoulli trial”. This will produce a sequence Z1 , … , Z n where
Zi ∈ { c 1 , … , c k }. Suppose we get x i elements of the type c i. Then the probability is given by:
 n! x x x
p1 p2 … pk 1 2 k

x1 ! x 2 ! … x k !

n!
It can be argued in a manner similar to the Trinomial case, that the number represents
x1 ! x 2 ! … x k !
the number of distinct ways to obtain x 1 elements in category-1, x 2 elements in category-2, and so
on.

n!
Once again, the quantity also appears in the Multinomial expansion:
x1 ! x 2 ! … x k !

n!
( a 1+ …+a k ) =
n
∑ x1 ! x2 ! … xk !
x x x
a1 a 2 … ak 1 2 k

x1 +…+ xk =n
x 1 ,… , x k ≥ 0

In the above expression for the trinomial expansion, put a i= pi to obtain:

n!
1= ∑ x x x
p p … pk
x1 ! x2 ! … xk ! 1 2
1 2 k

x 1+…+ x k =n
x 1 , …, x k ≥0

Let us define

{
n!
∑ x x x
p p … p k ; whenever x 1+ …+ x k =n
x1 ! x2 ! … xk ! 1 2
1 2 k

0 ≤ x1 ≤n
f ( x1 , … , xk )= 0 ≤x 2 ≤n
⋮
0 ≤x k ≤ n
0; whenever x 1+ …+ x k ≠ n

In view of the Multinomial expansion, we have

1= ∑ f ( x1 , … , xk )
0≤ x 1 ≤n
0≤ x 2 ≤n
⋮
0 ≤ x k ≤n

We say that X =( x 1 , … , x k ) has a multinomial distribution with parameters p1, p2,…, pk , and write

X Multinomial (n , p1 ,… , pk )

1.4 Gaussian Mixture Model:

We wish to see the connection between the Multinomial distribution and the process of sampling
from a mixture of Gaussian distributions.

A univariate Gaussian distribution admits a pdf of the form:

( )
2
1 x−μ
1
f ( x )= e2 σ
;−∞< x <∞ .
√2 π σ 2
In this case we say that the random variable X follows a Normal distribution with parameters μ and
σ , and write
2
X N (μ , σ )
A Gaussian mixture model is of the form:
k
g ( x )=∑ π i f i ( x ) .
i=1

Where, π 1 , π 2 , … , π k are the mixing proportions satisfying π 1 +π 2+ …+ π k =1, and f i takes the
form:

( ) ;−∞ < x <∞ .

2
−1 x−μi
1 2 σi
f i ( x )= e
√2 π σ 2
i

We can also write

k
g ( x )=∑ π i N (μi , σ 2i ).
i=1

Define a categorical distribution Z Multinomial (1 , π 1 , π 2 , … , π k ) so that P ( Z =c i )=π i.

Next, define f X∨Z =c (x )=f i (x ) for each −∞ < x <∞ .

i

The Law of Total probability says

k
P ( X=x ) =∑ P ( Z=ci ) P( X=x∨Z=c i )
i=1

k
¿ ∑ π i f i ( x )=g ( x ) .
i=1

This provides a simple algorithm for sampling from a mixture model:

1. Draw one random category Z=i from Multinomial (1 , π 1 , π 2 , … , π k ).

2
2. Draw a random sample x of size 1 from N ( μi , σ i ).
3. Repeat the above steps N times to create a random sample of size N .

1.5 Law of total probability:

A1 ∪ A 2 ∪ … ∪ A n=Ω

Therefore

P ( A )=P ( A ∩ ( A 1 ∪ A 2 ∪ … ∪ A n) )

¿ P ( A ∩ A 1 ) +…+ P ( A ∩ A n )

¿ P ( A 1 ) P ( A|A 1 ) +…+ P ( A n ) P (A∨ A n)

Example: Draw a random sample from the Gaussian mixture:

0.3 N (−2 , 12) + 0.7 N ( 2 ,0.5 2)

1.6 Bivariate Gaussian Distribution

A pair of random variables (X 1 , X 2 ) is said to follow a bivariate normal distribution if its pdf takes
the form:

−q
1 2
f ( x1 , x2)= 2 1
e ,
( 2 π ) σ 1 σ 2 ( 1−ρ )
2 2 2

Where −∞ < x 1 <∞ ,−∞< x 2 <∞ , and

[( ) ( )(
x 1−μ1 2
)( )]
2
1 x −μ x 2−μ2 x −μ
q= ❑ −2 ρ 1 ❑ 1 + 2 2
1−ρ2 σ1 σ1 σ2 σ2

The quantity ρ is the correlation between X and Y and is given by:

Cov (X 1 , X 2 )
ρ= .
σ1 σ2

Here we assume that ρ2 <1.

The above pdf can be put in a convenient form.

() () ( )
2
x1 μ σ1 ρ σ1 σ2
Let ¿ , μ= 1 , Σ=
x2 μ2 ρ σ1 σ2
2
σ2
Then the quantity q can be written as:
T −1
q=( x−μ ) Σ (x −μ)
So the pdf takes the form:
−q
1 2
f ( x , y )= 1
e
2 π |Σ|
2

We explain the calculation ( x−μ )T Σ −1 (x −μ) in detail below:

Note that det ( Σ )=σ 21 σ 22 ( 1− ρ2 )> 0. Now using the familiar formula for inverse we have:

−1 1
Σ = adj ( Σ )
σ σ ( 1− ρ2 )
2
1
2
2

( )
2 T
1 σ2 −ρ σ 1 σ 2
¿
σ 21 σ 22 ( 1−ρ2 ) −ρ σ 1 σ 2
2
σ1

)( )
2
1 σ2 −ρ σ 1 σ 2
¿
σ σ ( 1−ρ
2 2 2 2
1 2 −ρ σ 1 σ 2 σ1

( )
1 −ρ
2
1 σ1 σ1 σ2
¿ .
( 1−ρ2 ) − ρ 1
2
σ1 σ2 σ2

( )(
1 −ρ

)
2
1 σ1 σ1 σ2 x 1−μ1
Lastly the computation ( x 1−μ1 x 2−μ 2) yields the form:
( 1− ρ2) −ρ 1 x 2−μ2
2
σ 1σ 2 σ2

[( ) ( )( )( )]
2 2
1 x1 −μ 1 x 1−μ1 x2 −μ 2 x −μ
❑ −2 ρ ❑ + 2 2 .
1−ρ2 σ1 σ1 σ2 σ2

The Gaussian distribution in n variables has pdf in the following form:

−1 T −1
1 2
( x−μ ) Σ (x−μ)
f ( x )=f ( x 1 , x 2 , … , x n )= n 1
e
2 2
( 2 π ) det ( Σ )
Example: Generate a scatter plot of a mixture of 2 bivariate Gaussian distributions.

2. Classification models

We can predict a label for a new observation x using the Bayes theorem for each label i :
 P ( x|Z=i ) P(Z=i)
P ( Z=i|x )= k

∑ P ( x|Z= j ) P (Z= j)
j=1

Finally the most likely label for x is

h( x)= argma xi P(Z=i∨x )

The above rule h( x) is called as the Bayes classifier.

Suppose we want to predict whether a company will issue a dividend (“Yes” or “No”)
based on last year’s percentage profit X . From historical data, the mean of X is 10 for
companies that issued dividends and 0 for those that did not. The variance of X is 36 for
both groups, and 80% of companies issue dividends.

Assuming that X is normally distributed within each group, compute the probability that a
company will issue a dividend given that its last year’s profit was X =4 .

2.1 k-NN Classifier:

Suppose we have n data points: X 1 , X 2 , … , X n. Assume that each X i carries a label Y = y i and
y i ∈{1 , 2 , … ,m }.

We want to predict the label for a new test point x 0.

We first calculate the distance d ( x 0 , X i ) of x 0 from each data point X i .

Arrange these distances in ascending order:

d ( x 0 , X i ) ≤ d ( x 0 , X i ) ≤… ≤ d ( x 0 , X i ) .
1 2 n

Then X i , … , X i are the k-closest points to x 0.

1 k

The probability that x 0 will be labelled as j is set to

1
P ( Y = j| X=x 0 ) = ∑ 1(¿ y i= j). ¿
k i ∈{i ,… ,i }
1 k

The symbol 1( y i= j) takes the value 1 if y i= j; and takes the value 0 if y i ≠ j. Thus, we are selecting
the final label according to majority vote (among the k nearest neighbours).

Attempt the following question from the textbook:

 A data set of 6 observations is shown below. We wish to use this data set to predict Y for the
query observation Q=(0 , 0 , 0) using KNN classifier.

Obs X 1 X 2 X 3 Y

1 0 3 0 Red

2 2 0 0 Red

3 0 1 3 Red

4 0 1 2 Green

5 −1 0 1 Green

6 1 1 1 Red

a) Compute the Euclidean distance between Q and each data point.

b) Determine the predicted class when K=1 with full justification.
c) Determine the predicted class when K=3 with full justification.
d) Which model has a higher variance?

2.2 Optimality of Bayes’ classifier

The function defined by L ( j , y )=1( y ≠ j) is called a 0-1 loss function.

There is a well known theorem that the Bayes classifier is optimal under the 0−1 loss function.

In precise terms, we have the following theorem:

Theorem (Optimality of Bayes Classifier): Let X be a random variable defined on the feature space
X and Y be a random variable taking values in {0 ,1 }. Let η ( x )=P(Y =1∨X =x).

{
1
¿ 1 if η ( x ) ≥
Define the Bayes classifier as g ( x )= 2.
0 otherwise
¿
Then for any classifier g : X →{0 , 1} we have R ( g ) ≤ R(g).

Here R(g) stands for the misclassification error which is defined as

R ( g )=P ( g ( X ) ≠ Y ) .
¿
Further, R(g ) takes a neat expression:

[ ] [ ]
R ( g ) =E 1−max ( η ( x ) ,1−η ( x ) ) =E min ( η ( x ) ,1−η ( x ) ) .
¿
❑ ❑

Remark: The above theorem can be extended to the case of multi-class classification as well. In this
¿ ¿
case, if we put η k ( x )=P(Y =k ∨X=x ), then g and R(g ) take the form:
¿
g ( x )=max ηk (x)and
k
 [
R ( g ) =E 1−max ηk ( x ) . ]
¿

2.3 Simulating the Bayes Classifier:

In this illustration, we will generate sample data from a mixture of Bivariate Gaussian distributions.
We shall make two categories – BLUE and ORANGE.

The BLUE category will be made up of a mixture of 10 Gaussians; and the ORANGE category shall also
be made up of 10 Gaussians as follows:

Pick 10 random points from N ( ( 1 , 0 ) , I 2× 2 ). These will act as the means for the mixture
T

governing the BLUE category. Let us call these 10 points as b 1 , b2 , … , b10 and freeze them.

Pick 10 random points from N ( ( 0 , 1 ) , I 2× 2 ). These will act as the means for the mixture
T

governing the ORANGE category. Let us call these 10 points as o 1 , o 2 , … , o 10 and freeze
them.

 Assume that the distribution of the BLUE category takes the form:

( )
10
1 1
P ( X=x|BLUE )=∑ N b i , I 2 ×2 .Think of this as dividing the BLUE into 10 buckets
i=1 10 5
where each follows a different bivariate normal distribution. For simplicity, we are keeping
the correlation matrix fixed.

 Assume that the distribution of the ORANGE category takes the form:

( )
10
1 1
P ( X=x|ORANGE )=∑ N oi , I 2 × 2 .
i=1 10 5
Using the Bayes theorem, we have the following identities:

P ( X =x|BLUE ) P (BLUE)
P ( BLUE|X =x )= and
P( X =x)
P ( X=x|ORANGE ) P(ORANGE)
P ( ORANGE| X=x )= .
P(X =x)
The decision boundary comprises of those points x which satisfy:

P ( BLUE|X =x )=P (ORANGE|X =x )

Simplifying we get:

P ( X=x|BLUE ) P ( BLUE )=P ( X =x|ORANGE ) P (ORANGE ) .

1
 For simplicity, let us take P ( BLUE )= =P (ORANGE ) .
2
Thus the Bayes decision boundary reduces to

P ( X=x|BLUE )=P ( X=x|ORANGE ) .

This is easy to calculate because we know both the conditional distributions fully.

2.4 Linear Discriminant Analysis (LDA):

Our starting point will be the Bayes theorem:

P ( B|A i ) P( Ai )
P ( A i|B )= k
.
∑ P ( B|A j ) P( A j )
j=1

Here A1 , … , A k are mutually exclusive (pairwise disjoint) and exhaustive events (union
covers the whole sample space). B is some arbitrary event.
In order to apply the Bayes theorem to the classification problem, let B be the event that the
predictor X =x , and A j are the events that x is assigned a label Y = j , j=1 ,2 , … , k .

Note that P( A j ) can be calculated from the sample data (favorable cases/total cases).

But P ( B| A i ) cannot be determined because the distribution of predictors is never known.

We shall build methods based on certain assumptions on P( X=x∨Y =i). Let’s work with
the assumption that X ∨( Y =i ) N (μi , σ 2i ).

Precisely, the PDFs for the buckets i are given by:

( ) ,−∞ < x <∞ ; 1≤ j ≤ k

2
−1 x−μi
1 2 σi
f i ( x )= e
√ 2 π σi 2

Substituting this expression into the Bayes rule we see that

f i (x) P(Y =i) f i ( x ) πi

p ( i ) ≔ P ( Y =i|X =x )= k
= k

∑ f j ( x) P(Y = j) ∑ f j ( x ) π j
j=1 j=1

The probabilities π j are called priors.

The predicted label will be

argma x i p (i)

We make the following computation to simplify matters:

{ }
f i ( x ) πi
arg max { p ( i ) }=argmax k
i 1 ≤i ≤ k
∑ f j( x ) π j
j=1
 ¿ argmax
1 ≤i ≤k
{ f i( x ) π i
D ( x) }
¿ argmax
1 ≤i ≤k
{ f i( x ) π i
1 }
¿ argmax { log f i ( x ) + log π i }
1 ≤i ≤k

{ ( ) }
2
1 x−μi 1
¿ argmax log − +log π i
1 ≤i ≤k
√ 2 π σ i 2 σi
2

¿ argmax log
1 ≤i ≤k { √2 π σ
1
2
i
−
1
2
2 σi
2 2
(x −2 x μi + μi )+ log π i
}
1 1 2 2
The k numbers log − (x −2 x μ i+ μ i )+log π i are called discriminants.
√2 π σ 2
i
2
2 σi

We analyze these discriminants in two cases:

2 2 2 2
 σ 1=σ 2=…=σ k =σ
2
 σ i need not be equal.

Under case 1, the discriminants take the form

1 1 2 2
log − (x −2 x μ i+ μ i )+log π i
√2 π σ 2
2σ
2

Therefore,

argmax log
1 ≤i ≤k { √2 π σ
1
2
−
1
2σ
2(
x −2 x μi + μi ) + log π i
2 2
}
¿ argmax
1 ≤i ≤k { −1 2
2σ 2(
x −2 x μi + μ2i ) + log π i
}
¿ argmax
1 ≤i ≤k { −1
2σ 2(
−2 x μi + μ2i ) + log π i
}
−1
2(
−2 x μ i+ μ i ) +log π i. This method is
2
Thus, it is enough to look at linear discriminants
2σ
called the Linear Discriminant Analysis (LDA).
 Assume that the observations in class k are drawn from a normal distribution with mean μk
and common variance σ 2:

X ∣Y =k ∼ N ( μk , σ 2 ) .

Let π k denote the prior probability of class k .

Show that assigning an observation x to the class that maximizes the posterior probability
P(Y =k ∣ X =x) is equivalent to assigning it to the class that maximizes the discriminant
function
2
μk μk
δ k (x)= 2
x− 2
+ log ⁡π k .
σ 2σ
In other words, you are proving that under the Gaussian assumption with equal variance, the
Bayes classifier can be expressed as maximizing the linear discriminant function.

In linear discriminant analysis (LDA) with multiple features, derive an expression for
the log posterior odds between class k and a reference class K .

Consider the simpler case where there is only one feature ( p=1 ), so that each class has
a scalar mean μk and all classes share a common variance σ 2. Repeat the above
derivation for this one-dimensional setting and show that the log posterior odds

log
( P (Y =k ∣ X=x )
P(Y =K ∣ X =x) )
can be written in the linear form a k + bk x .

Express a kand b k in terms of the class priors π k , π K , the means μk , μ K , and the variance
2
σ .

For the second case, the discriminants are quadratic. This method is called Quadratic
Discriminant Analysis (QDA).
 Consider a classification problem with K classes and a single predictor ( p=1 ). Suppose that,
conditional on belonging to class k , the feature follows a normal distribution:

2
X ∣Y =k ∼ N (μk , σ k ),
2
where both the mean μk and variance σ k may differ across classes, and let π k denote the prior
probability of class k .

Show that the Bayes classifier, which assigns an observation x to the class that maximizes the
posterior probability P(Y =k ∣ X =x), results in a decision rule that is quadratic in x . Conclude
that the decision boundary is not linear.

This problem refreshes the concept of odds.

a) If the odds that a person will default on their credit card payment are 0.37,
what is the corresponding probability (fraction of people) who will default?
b) If the probability that a person will default is 16%, what are the corresponding
odds of default?

2.5 Decision Boundary:

For a binary classification problem, the decision boundary is the set:
∂ :={x :P ( Y =0|X =x )=P(Y =1∨X =x)}

Let us compute the decision boundary in case of LDA when the predictor is a real number.
Here
( )
2
−1 x−μi
1
πi e2 σ❑

P ( Y =i|X =x ) :=f i (x)=

√ 2 π σ❑
2

D(x )

Therefore

∂≔ x:
{ f 0( x )
f 1( x )
=1
}
{ ( ) ( ) = π1
}
2 2
−1 x−μ0 1 x− μ1
+
2 σ❑ 2 σ❑
¿ x :e
π0

{( )( ) }
2 2
x−μ 0 x−μ 1 π
¿ x: − =−2 log 1
σ❑ σ❑ π0

{ 2
¿ x : ( x−μ 0 ) −( x−μ1 ) =−2 σ log
2 2 π1
π0 }
 {
¿ x :(μ 1−μ0 )(2 x −μ 0−μ1 )=−2 σ log
2 π1
π0 }
Thus, the decision boundary is a point when μ0 ≠ μ 1 because solving the expression

2 π1
(μ1−μ 0)(2 x−μ0 −μ 1)=−2 σ log , we get only one value of x :
π0

1 1 π
x= − σ 2 log 1 .
2(μ1 + μ0 ) μ1−μ 0 π0

2.6 Decision boundary in 2 variables:

We have two classes k =0 , 1. Let the pdf of these classes be
−1 T −1
1 2
( x−μ k ) Σ (x−μ k )
f k ( x )= 1
e .
2 π|Σ|
2

Here, x=
[] [ ]
x1
x2
μ σ
, μk = k 1 , and Σ= 11
μk 2
σ 12
σ 12 σ 22
.
[ ]
It is easy to see that

|Σ|=σ 11 σ 22−σ 12 σ 21 and

−1
Σ =
1
|Σ| −σ 12[ σ 22 −σ 12
σ 11
.
]
Let us now compute:

T 1 σ
( x−μ k ) Σ−1 ( x −μ k )= [ x 1−μ k 1 x 2−μk 2 ] ⋅ 22
|Σ|
−σ 12 x1−μ k 1
−σ 12 σ 11
⋅
x 2−μ k 2 [ ][ ]
1
¿
|Σ|
( σ 22 ( x 1−μ k 1) + σ 11 ( x 2−μk 2 ) −2 σ 12 ( x 1−μk 1 ) ( x2 −μ k 2 ) ) .
2 2

The decision boundary is given by:

∂= x :
{ f 0(x)
f 1(x) }{f (x)
=1 = x :log 0 =0
f 1 (x ) }
¿ { x : log f 0( x)=log f 1 (x) }

¿ { x : ( x−μ0 ) T Σ −1 ( x−μ 0 )=( x−μ 1) T Σ −1 ( x−μ 1) }

Expand the terms:

( x−μ k ) Σ−1 ( x −μ k )=( xT −μTk ) Σ−1 ( x −μ k )

T
 T −1 T −1 T −1 T −1
¿ x Σ x−x Σ μk −μ k Σ x + μk Σ μ k .
T −1 T −1
Thus, the equality ( x−μ 0 ) Σ ( x−μ 0 )=( x−μ 1 ) Σ ( x−μ 1 ) yields
T −1 T −1 T −1 T −1 T −1 T −1
−x Σ μ 0−μ0 Σ x+ μ 0 Σ μ0 =−x Σ μ1−μ1 Σ x + μ1 Σ μ 1 .
This further simplifies to
T −1 T −1 T −1 T −1 T −1 T −1
−x Σ μ 0+ x Σ μ1−μ0 Σ x+ μ 1 Σ x=μ 1 Σ μ1−μ 0 Σ μ0 .
Therefore
T −1 T −1 T −1 T −1
x Σ ( μ 1−μ0 ) + ( μ1 −μ 0 ) Σ x =μ 1 Σ μ1 −μ 0 Σ μ 0 .
−1
Observe that Σ ( μ1−μ0 ) is a matrix of order 2 ×1 and it does not depend on x . For
convenience, write this matrix as []
a1
a2
.

Therefore
T −1 T −1
x Σ ( μ 1−μ0 ) + ( μ1 −μ 0 ) Σ x

¿ [ x1 x2 ]
[]
a1
a2
x
[]
+ [ a 1 a2 ] 1 =2 a1 x 1+2 a 2 x 2 .
x2

This gives
T −1 T −1
2 a1 x1 +2 a 2 x 2=α =μ1 Σ μ1−μ0 Σ μ0 .
This proves the boundary is a line.

2.7 Decision boundary for QDA:

Here, we have the following form for the probability distribution functions for the k th class:
−1 T −1
1 2
( x− μk ) Σk (x−μ k )
f k ( x )= 1
e .
2 π|Σ k|2

The major difference compared to LDA is that in this case the covariance matrices are not fixed.

Therefore, ∂={ x : log f 0 (x )=log f 1 (x) } takes the form:

{ x : ( x−μ 0) T Σ−10 ( x−μ 0 )=( x−μ 1) T Σ−11 ( x−μ 1) }

T −1
Just as in the case of LDA, we can expand ( x−μ k ) Σ k ( x −μ k ) as
T −1 T −1 T −1 T −1
x Σ k x−x Σ k μk −μ k Σ k x + μk Σ k μ k
So we have
T −1 T −1 T −1 T −1 T −1 T −1 T −1 T −1
x Σ 0 x−x Σ 0 μ0−μ 0 Σ 0 x + μ0 Σ 0 μ 0=x Σ 1 x−x Σ 1 μ1−μ1 Σ 1 x+ μ 1 Σ 1 μ1
This simplifies to
T −1 T −1 T −1 T −1 T −1 T −1 T −1 T −1
x Σ 0 x−x Σ 1 x−x Σ 0 μ 0−μ0 Σ 0 x+ x Σ 1 μ 1+ μ 1 Σ 1 x=μ 1 Σ 1 μ1−μ 0 Σ 0 μ0

The terms in RED are quadratic in the coordinates x 1 and x 2. Whereas, the terms in BLUE are linear in
x 1 and x 2. The green term on the RHS is a constant (call it as α ) for simplicity. So overall we have an
equation that is quadratic in the coordinates x 1 and x 2.

3. Curse of dimensionality
We are aware of basic shapes like a cube. In 2D, the unit cube is a unit square which can also
be expressed as a set

[ 0 , 1 ]2 ={( x 1 , x 2 ) ∈ R2 :0 ≤ x1 , x2 ≤1 } .
In 3D, we have the familiar cube of side length equal to 1:

[ 0 , 1 ]3 ={( x 1 , x 2 , x3 ) ∈ R 3 :0 ≤ x i ≤ 1 ,i=1 , 2 ,3 } .
These definitions generalize to d dimensions and we have a d−¿dimensional hypercube:

[ 0 , 1 ] d= {( x 1 , x 2 , … , x d ) ∈ R d :0 ≤ x i ≤1 , i=1 ,2 , … , d } .
Note that the definition of a hypercube is a natural extension of the familiar case. However,
in higher dimensions strange things begin to happen which we shall now analyze.
 Volume gets concentrated in a thin shell:
Let us begin by calculating the volume of a d−¿ dimensional hypercube of side r :

V ❑ ( [ 0 , r ] ) =r
d d

In case of a unit cube the volume stays at unity irrespective of the dimension. When r <1
then the volume shrinks to 0 as d → ∞, and it explodes to infinity when r >1.

For simplicity, we shall write V ( [ 0 , r ] ) as V d (r ).

d

d
Look at the case r =1. Then, for any 0< ϵ< 1, the cube [ 0 , 1−ϵ ] d has volume V d ( 1−ϵ )=( 1−ϵ )
.

Note that [ 0 , 1−ϵ ] d is contained in the unit cube and V d ( 1−ϵ ) → 0 as d → ∞.

This is particularly a strange and curious observation because it means that volume of a unit
hypercube is getting concentrated near its edges. Look at it again, [ 0 , 1−ϵ ] d is a cubical shell
inside the unit cube [ 0 , 1 ] d (outer shell) and the volume of the outer shell is always 1
irrespective of d but the volume of the inner shell diminishes to 0. So the entire volume of
the outer shell is between the inner shell and the outer shell. The gap between the two
shells is ϵ which can be as small as you like. So the entire volume of the unit cube gets
concentrated near the edges.
 This observation looks counter-intuitive since we normally picture cubes as boxes in 3D
space and as squares in 2D space.

Observe that ( 1−ϵ )d is the fraction of the volume of the outer unit cube that is contained in
the inner cube of side 1−ϵ . The edge lengths 1−ϵ are tabulated below for various fractions
of volume across various dimensions.

2 3 4 5 6 7 8 9 10 11
5% 0.223607 0.368403 0.472871 0.54928 0.606962 0.651836 0.687656 0.716871 0.741134 0.761596
10% 0.316228 0.464159 0.562341 0.630957 0.681292 0.719686 0.749894 0.774264 0.794328 0.811131
20% 0.447214 0.584804 0.66874 0.72478 0.764724 0.794597 0.817765 0.836251 0.85134 0.863888
30% 0.547723 0.669433 0.740083 0.786003 0.818189 0.841982 0.860281 0.874787 0.886568 0.896325
40% 0.632456 0.736806 0.795271 0.832553 0.858374 0.877307 0.89178 0.903201 0.912444 0.920076
50% 0.707107 0.793701 0.840896 0.870551 0.890899 0.905724 0.917004 0.925875 0.933033 0.938931
60% 0.774597 0.843433 0.880112 0.90288 0.918386 0.929624 0.938143 0.944822 0.9502 0.954623
70% 0.83666 0.887904 0.914691 0.93115 0.942287 0.950323 0.956395 0.961144 0.964961 0.968095
80% 0.894427 0.928318 0.945742 0.956352 0.963492 0.968625 0.972492 0.975511 0.977933 0.979919
90% 0.948683 0.965489 0.974004 0.979148 0.982593 0.985061 0.986916 0.988362 0.989519 0.990467

 Center becomes unreachable from the corners

The center of the unit hypercube is the point

c= ( 12 , 12 , … , 12 ) ∈ R .
d

Note that one of the corners of the cube is the origin x 0=( 0 , 0 , … , 0 ) ∈ R d.

Now

( ) ()
1 1
1 1 1 d 2 1
dist ( x 0 , c )= 2
+ 2 +…+ 2 2 = = √d
2 2 2 4 2

Clearly dist ( x 0 , c ) → ∞ as d → ∞.

The strange part is that the length of the diagonal is exploding to infinity but the side length
remains frozen at 1.
 Number of points per axis (Sampling density)
Suppose there are N sample points in total and m points are placed along each axis.
Therefore, N=md. This is a routine way of constructing a mesh.

1
For N=10 6, let us compute m=N d for few values of d :
 d 2 3 10 25 50 75 100
m 1000 100 3.98 1.74 1.32 1.20 1.15

 Most random points are close to the center

d
Let x=( x 1 , x 2 , … , x d ) ∈ R be any point, and c= ( 12 , … , 12 ) be the center of the cube.
( ) ( )
2 2
( ) 2 1 1
Then, dist x , c = x 1− +…+ x d − .
2 2

Let us assume that X Unif ( [ 0 ,1 ] ) and x is just one instance of X .

d

Recall that X has a pdf of the form:

{
1
0 ≤ x i ≤1 , 1≤ i≤ d
f ( x 1 , … , x d )= (1−0 )d
0 otherwise

Introduce univariate independent uniform random variables X i Unif ( [ 0 ,1 ] ). Then dist ( x , c )2

is a particular instance of the random variable:

( ) ( )
2 2
1 1
Y ≔ X 1− +…+ X d −
2 2

We now compute the mean and variance of Y .

( ) so that
2
1
Put Y i= X i −
2
1

( )
2
1 1
E [ Y i ]=∫ t− dt = and
0 2 12
1

( )
4
1 1
E [ Y i ] =∫ t−
2
dt= .
0 2 80

So,
1 1 1
Var ( Y i )= − = .
80 144 180
Therefore
d
E [ Y ] =E [ Y 1 ] +…+ E [ Y d ] = and
12
d
Var ( Y ) =Var ( Y 1 ) +…+ Var ( Y d ) = .
180
Recall the Chebyshev’s inequality which measures how far a random variable deviates from
its mean using information about its variance only:
 Var ( X )
P (|X −E[ X ]|≥ ϵ ) ≤ .
ϵ2
Y
Applying this inequality to we get:
d

P (|Yd − 121 |≥ ϵ )≤ 1801dϵ .

2

Note that the RHS goes to 0 as d → ∞.

Hence, we have

P (|Yd − 121 |≥ ϵ )→ 0 as d → ∞.
In other words,

(|
P Y−
d
12 | )
≥ dϵ → 0 as d → ∞.

This means that, given any point X =x , its distance from the center c lies within a thin band
d
around with extremely high probability (because the probability of escaping that band is
12
shrinking to 0 ).
Thus, we cannot have points that are far away from the center for high values of d . This is
strange because when we plot large number uniformly distributed random points in one,
two, and three dimensions, they tend to fill the entire space. Here (for high values of d ) we
are seeing that no matter how large the sample size is, it is extremely unlikely for the points
to move out of a thin band. Thus the space filling nature of uniform distributions is violated!
You should now be able to attempt the following exercise from the textbook:
 The following question investigates the poor performance of KNN when the number of
features grow larger.

a. Suppose we observe data with a single feature X that is uniformly

distributed on the interval [ 0 , 1 ]. To predict the response for a test
observation, we use only those training observations whose feature
values lie within an interval of length 0.1(i.e., 10% of the range) centered
around the test point. What is the expected fraction of the training
observations that will be used for prediction?

b. Suppose we observe data with two features ( X 1 , X 2 )that are uniformly

distributed over the unit square ¿. To predict the response for a test
observation, we use only those training observations whose feature
values lie within an interval of length 0.1(10% of the range) around the
test point in each coordinate. What is the expected fraction of the
training observations that will be used for prediction?

c. Suppose we observe data with p=100 features, each uniformly

distributed on the interval [ 0 , 1 ]. To predict the response for a test
observation, we use only those training observations whose values lie
within an interval of length 0.1(10% of the range) around the test point
in each feature. What is the expected fraction of the training observations
that will be used for prediction?

Using your results from parts (a)–(c), explain why K-nearest neighbors suffers from poor
performance when the number of features pis large. In particular, argue why there are very
few training observations that lie close to any given test observation in high dimensions.

4. Logistic Regression
¿ ¿ ¿ ¿ ¿
Let the sample data be ( x 1 , y 1 ) , … ,( x n , y n). Here the responses y i are discrete. For example,
in a binary classification scenario we have y i=0∨1. For a K class problem, we have
y i=0 ,1 , … , K−1.

For this discussion, we shall consider only the binary case and use the labels as −1 and +1
instead of 0 and 1.
Here we will consider the case of a single predictor x and later generalize to multiple
predictors x 1 , x 2 ,… , x d .

The linear model g ( x )=w 0 +w1 x can be used to predict binary labels for the point x by
assigning −1 when g ( x )< 0 and +1 when g ( x ) ≥ 0.
Thus the predicted label is

h ( x )=sgn ( g(x ) )=sgn(w 0 +w 1 x).

 ¿ ¿
Suppose the true label for the observation x is y . We say that the linear model g correctly
¿ ¿ ¿ ¿
classifies x ¿ if h ( x ) = y and that g misclassifies x ¿ if h ( x ) ≠ y .

A natural definition of error would be the number (or proportion) of misclassifications by a

model g:
n
1
E ( w 0 , w1 )= ∑ 1 ( h ( x ¿i ) ≠ y ¿i ) .
n i=1

(The expression 1(⋅) evaluates to 1 if the expression inside is true and it evaluates to 0
otherwise.)
¿ ¿ ¿
Thus the optimal weights w =(w 0 , w1 ) would be
n
1
w ¿=argmi nw ,w 0 1
∑ 1 (h ( x ¿i ) ≠ y ¿i ) .
n i=1

Unfortunately, the above optimization problem is NP-hard.

So we need an alternative way of attacking this problem. The new approach is to come up
with an h( x) which serves as a reasonable model for P(Y =1∨X =x).
Now if h ( x )=P(Y =1∨ X=x) then 1−h ( x )=P (Y =−1∨X=x ).
t
e 1
Let θ : R → R be the Logistic function θ ( t )= t
= −t and define
h ( x )=θ (w 0+ w1 x).
1+ e 1+ e

Thus
w 0 +w 1 x
e
h ( x )= w +w x
.
1+e 0 1

Note that 1−θ ( t )=θ (−t). So we can write P ( Y = y| X=x )=θ ( y (w 0+ w1 x)).

This means that the conditional random variable Y ∨(X =x) is a Bernoulli random variable
with parameter θ(w0 + w1 x ).

We assume that Y i are independent. Also we have that Y i Ber ( pi ), where

¿
pi=θ (w 0+ w1 x i ).

The Likelihood function for (Y 1 , … ,Y n) can now be written as

L ( y ¿1 ,… , y ¿n ; w 0 , w 1 )= pY ( y ¿1) pY ( y ¿2 ) … p Y ( y ¿n )
1 2 n

n
¿ ∏ θ( y ¿i (w 0+ w1 x¿i )).
i=1

Maximizing L, is equivalent to maximizing it’s log:

 n
log L ( w 0 , w 1 )=−∑ log ( 1+ e− y (w +w )
¿ ¿
i 0 1 xi )

i=1

This is equivalent to minimizing:

n
−log L ( w 0 , w 1 )=∑ log ( 1+ e− y (w +w ).
¿ ¿
i 0 1 xi )

i=1

The expression on the right is called the Cross-Entropy error which we denote by E(w0 , w 1).

It can be checked that

[∑ − y ¿i − y ¿i x ¿i
]
n n
∇w E ( w ) = ¿ ¿
yi (w0 +w 1 x i )
,∑ ¿
yi (w0 +w 1 x i )
¿ .
i=1 1+ e i=1 1+ e

Observe that for E(w) to be small we require log ( 1+ e− y w ) to be small. That is, e− y w x
T ¿ T ¿
xi
i i i
is
T ¿ ¿ T ¿
small. This implies y i w x is a large positive number. This means that y =sgn (w x ). So you
i i i
¿
are imposing that the linear model correctly classifies x i !

In general we do not have closed form solutions for ∇ w E ( w ) =0. In fact, this system is solved
by numerical methods like the Conjugate Gradient method.
The above method is called as Logistic Regression. Here we are finding the sigmoid curve of
best fit instead of a line of best fit. Though the phrase ‘best fit’ is in the sense of Cross
entropy rather than RSS.
α+βx
e
In the context of a single feature we see that p= α + βx can be re-written as
1+e
p α+ βx
=e
1− p
Which is equivalent to

log ( 1−pp )=α + βx

p
The quantity is called the Odds. So, we are assuming a linear model for log of the odds.
1− p

The set { x : P ( Y =1|X =x )=P (Y =0| X=x ) } is called the decision boundary. For the logistic

regression model involving only one predictor it reduces to

−α
β
. { }
5. Logistic Regression in several variables
 ¿ ¿ ¿ ¿ ¿
Let the sample data be ( x 1 , y 1 ) , … ,( x n , y n). Here the responses y i are discrete. For example,
in a binary classification scenario we have y i=0∨1. For a K class problem, we have
y i=0 ,1 , … , K−1.

The linear model g ( x 1 , … , x d ) =w 0+ w1 x1 +…+ w d x d can be used to predict binary labels for
the point ( x 1 ,… , x d ) by assigning −1 when g ( x 1 , … , x d ) < 0 and +1 when g ( x 1 , … , x d ) ≥ 0.

Thus the predicted label is

h ( x )=sgn ( w T x ) .
T T
(Here w=( w0 , w1 , … , wd ) and x=( 1 , x 1 , … , x d ) .)

Suppose the true label for the observation x ¿ is y ¿. We say that the linear model g correctly
¿ ¿
classifies x if h ( x ¿ ) = y ¿ and that g misclassifies x if h ( x ¿ ) ≠ y ¿.

A natural definition of error would be the number (or proportion) of misclassifications by a

model g:
n
1
E ( w )= ∑ ⟦ h ( x ¿i ) ≠ y ¿i ⟧ .
n i=1

(The bracket ⟦ ⋅ ⟧ evaluates to 1 if the expression inside is true and it evaluates to 0

otherwise.)
Thus the optimal w would be
n
1
¿
w =argmi nw ∈R d+ 1 ∑
n i=1
⟦ h ( x¿i ) ≠ y ¿i ⟧ .

Unfortunately, the above optimization problem is NP-hard.

So we need an alternative way of attacking this problem. The new approach is to come up
with an h( x) which serves as a reasonable model for P(Y =1∨X =x).
Now if h ( x )=P(Y =1∨ X=x) then 1−h ( x )=P (Y =−1∨X=x ).
t
e 1
( )
Let θ : R → R be the Logistic function θ t = t
= T
−t and define h ( x ) =θ (w x ).
1+ e 1+ e
Thus
T

ew x
h ( x )= T .
1+e w x

Note that 1−θ ( t )=θ (−t). So we can write P ( Y = y| X=x )=θ ( y wT x ).

This means that the conditional random variable Y ∨(X =x) is a Bernoulli random variable
with parameter (wT x) .

We assume that Y i are independent. Also we have that Y i Ber ( pi ) where pi=θ (w T x¿i ) .
The Likelihood function for (Y 1 , … ,Y n) can now be written as

L ( y ¿1 ,… , y ¿n ; w ) = pY ( y ¿1) pY ( y ¿2 ) … p Y ( y ¿n )
1 2 n

n
¿ ∏ θ( y i wT x ¿i ).
i=1

Maximizing L, is equivalent to maximizing it’s log:

n
log L ( w )=−∑ log ( 1+ e− y w )
T ¿
i xi

i=1

This is equivalent to minimizing:

n
−log L ( w )=∑ log ( 1+ e− y w ).
T ¿
i xi

i=1

The expression on the right is called the Cross-Entropy error which we denote by E(w).
T

Let us differentiate log ⁡(1+e− y w x ) with respect to w . Here y is a scalar.

By chain rule:
1
∇ w log ( 1+e )= ⋅ ∇ w ( 1+ e )
− y wT x − y wT x
T
− yw x
1+e
1
⋅∇ w (− y w x ) .
− y wT x T
¿ T
−yw x
⋅e
1+ e
So it remains to calculate:

∇ w (− y wT x ) =− y ∇w ( w T x ) .

We know that w T x=w 0 +w1 x 1+ …+w d x d.

Therefore
∂
( wT x ) =1 , ∂ ( wT x ) =x 1 , … , ∂ ( w T x )=x d .
∂ w0 ∂ w1 ∂ wd

Hence ∇ w ( w x ) =[ 1 , x 1 , … , x d ] =x .
T T

Thus we conclude that

¿ T ¿
n
y ¿i e− y wi xi

∇ w E ( w ) =∑
¿
¿
− yi w x i
T ¿ xi .
i=1 1+ e

Observe that for E(w) to be small we require log ( 1+ e− y w ) to be small. That is, e− y w x
T ¿ T ¿
xi
i i i
is
T ¿ ¿ T ¿
small. This implies y i w x is a large positive number. This means that y =sgn (w x ). So you
i i i
¿
are imposing that the linear model correctly classifies x i !
In general we do not have closed form solutions for ∇ w E ( w ) =0. In fact, this system is solved
by numerical methods like the Conjugate Gradient method.
The above method is called as Logistic Regression. Here we are finding the sigmoid curve of
best fit instead of a line of best fit. Though the phrase ‘best fit’ is in the sense of Cross
entropy rather than RSS.

Suppose we fit a logistic regression model to predict whether a student receives an A in

a statistics class based on hours studied ( X 1) and undergraduate GPA ( X 2 ). The
estimated coefficients are

^β =−6 , β^ =0.05 , ^β =1.

0 1 2

(a) Estimate the probability that a student who studies 40 hours and has a GPA of 3.5
receives an A.

(b) How many hours must this student study to have a 50% probability of receiving an
A?

A dataset is split into equally sized training and test sets. Logistic regression yields a
training error of 20% and a test error of 30%. A 1-nearest neighbors classifier yields an
average error rate of 18% across the training and test sets combined.

Which method should be preferred for predicting new observations, and why?

6. Linear Regression in several variables

Suppose we have the dataset D= {( z i , y i ) :i=1 , 2, … , n }. Here z i ∈ R are called examples in the
d

data set and y i ∈ R is the response corresponding to the example x i. There are d features (columns)
X 1 , X 2 , … , X d in the data set.
T
Note that each z i is a vector of the form z i=( z i 1 , z i 2 , … , z id ) , and we define
¿ T d+1
x i = ( 1 , z i 1 , z i 2 , … , z id ) ∈ R . This is same as adding a new column of 1s in the beginning of the
data set.

In machine learning our goal is to find a relationship between the response variable Y and the
feature variables X 1 , X 2 , … , X d in the form Y =f ( X 1 , X 2 , … , X d ).

In case of linear regression we assume f to have the form

f ( x 1 , x 2 , … , xd )=w0 +w 1 x 1 +…+ wd x d .

The constants (weights) w 0 , w1 , … , wn will be determined from the data set D .

Note that we can write f in the matrix form:

T
f ( x )=w x .
T T
Here x=( 1 , x 1 , … , x d ) and w=( w0 , w1 , … , wd ) are vectors in Rd +1.
 ¿
The real numbers f ( xi )=w x i are the values predicted by the model f at each example x i .
¿ T ¿

| ¿
|
The error in prediction for the i th example is y i−f ( x i ) . To make the mathematics simpler we shall
¿ 2
consider the squared error ( y i−f ( x i ))
.

The overall error on D is defined as

n n
E ( w )=∑ ( y i−f ( x ¿i ) ) =∑ ( y i−wT x ¿i ) .
2 2
(1)
i=1 i=1
We will be able to write (1) in a more convenient form by introducing a matrix:

( )
1 x11 x 12 … x1d
1 x 21 x 22 … x2d
X=
⋮ ⋮ ⋮ ⋱ ⋮
1 xn 1 xn 2 … xnd n × ( d+1 )

The matrix A is nothing but the column of 1s appended to the entire data set. This means that
¿ T
x i = ( 1 , x i 1 , x i 2 , … , x id ) .

Note that

( )
T ¿
y 1−w x 1
T ¿
(2)
y− X w= y 2−w x 2 .
⋮
y n−w T x ¿n n ×1

In view of (2) we can write (1) as

E ( w )=‖ y−X w‖2 .

2
(3)

¿
We wish to find the weight vector w that minimizes the function E(w). That is,
¿
w =argmi nw ∈R E ( w ) . d+ 1

The function E(w) given by (3) is strictly convex. Hence it has a unique global minimum given by
∇ w E ( w ) =0. This implies −2 y T X +2 w T X T X =0.
−1
Therefore, w ¿= ( X T X ) T T
X y . (The matrix X X is invertible if it is positive definite.)

Let us show the calculation of ∇ w E ( w ) step by step:

T
E ( w )=( y− Xw ) ( y− Xw )

¿ ( y T −w T X T ) ( y −Xw )
T T T T T T
¿ y y− y Xw−w X y+ w X Xw
T
¿ y y− y Xw−( y Xw ) + w X Xw
T T T T T
 T T T T
¿ y y−2 y Xw+ w X Xw .
T
Because y T Xw is a real number so y T Xw =( y T Xw ) . Put A=X T X .

Now

∇ w E ( w ) =∇ w ( y T y ) −2 ∇ w ( y T Xw ) +∇ w (wT Aw)

Note that

∇ w ( y T y )=0

∇ w ( y Xw ) =∇ w ( ( X y ) w )= X y .
T T T T

Lastly, we have
n n
w T Aw=∑ ∑ A ij w i w j
i=1 j=1

¿ ( A11 w1 w1 + A12 w1 w2 +…+ A 1 n w1 wn ) + ¿

( A 21 w2 w 1+ A 22 w 2 w2 +…+ A 2n w 2 wn ) +¿
⋮
+ ( A n 1 w n w1 + An 2 wn w 2+ …+ Ann w n w n )

For the sake of illustration, lets compute the partial derivative with respect to w 1:
∂ T
w Aw=( A 11 w1 + A12 w2 +…+ A 1 n wn ) + ( A 11 w1 + A21 w2 +…+ A n 1 wn )
∂ w1

¿ 2 ( A 11 w 1+ A 12 w 2+ …+ A1 n w n) .

Similar pattern follows for other partial derivatives also.

Therefore,
T T
∇ w (w Aw)=Aw+ A w=2 Aw .

Suppose we collect 100 observations with one predictor X and one quantitative
response Y , and fit two linear models:

i. Y = β0 + β 1 X
2 3
ii. Y = β0 + β 1 X + β 2 X + β 3 X

a) If the true relationship between X and Y is linear, compare the training RSS of
the linear and cubic models. Which is supposed to be smaller, or are they the
same? Justify.

b) If the true relationship is nonlinear (unknown form), compare the training RSS
of the two models. Justify.
The following question is a straight-forward application of the linear model:

Suppose we have a dataset with five predictors: GPA, IQ, an indicator for education
level (1 = college, 0 = high school), the interaction between GPA and IQ, and the
interaction between GPA and education level. The response variable is starting salary
(in thousands of dollars). A least squares fit yields the estimated coefficients:

β 0=50 , β 1=20 , β2 =0.07 , β3 =35 , β 4 =0.01 , β5 =−10

a) For fixed GPA and IQ, determine how starting salary compares between college
and high school graduates.

b) Predict the salary of a college graduate with GPA 4.0 and IQ 110.

c) Assess whether a small coefficient on the GPA–IQ interaction implies little

evidence of interaction.

7. Linear Regression – A Probabilistic View

We explain the mathematics in the case of simple linear regression, that is, when there is
only one feature variable X and an associated response variable Y .
p XY ( x , y )
Let X , Y be two random variables with a joint pdf p XY ( x , y ). Then f ( y|x ) := is
pX ( x )
called the conditional distribution function for Y given X =x .

Here p X (x) is the marginal distribution for X :

∞
p X ( x )= ∫ p XY ( x , y ) dy
−∞

f ( y|x ) can also be written as f (Y |x ) ( y ).

The conditional mean is given by

∞
E ( Y |X =x )= ∫ yf ( y ∨x) dy
−∞

and is also known as the regression equation of Y on X .

Simple linear regression is the case when E ( Y |X =x )=α + βx .

Remark: The relationship like α + β x 2 is also regarded under linear regression. The word
linear is to be interpreted as linear in parameters.
 ¿ ¿ ¿ ¿
Let the sample data be ( x 1 , y 1 ) , … ,( x n , y n).

In this approach, we assume that the features X 1 , … , X n in each example are fixed numbers
¿ ¿
x 1 , … , x n, that is, these are not to be treated as random variables. The corresponding
¿ ¿
responses y 1 , … , y n are assumed to be realizations of random variables Y 1 , … ,Y n generated
by the law:
¿
Y i=w0 + w1 x i + ϵ i ; i=1 , 2 ,… ,n

Here ϵ i are independent and identically distributed normal random variables with zero mean
and variance σ 2. That is, each ϵ i N (0 , σ 2 ).

Since a normal random variable offset by a constant c is also a normal random variable with
same variance and mean offset by c , so we have Y i N (w 0+ w1 x ¿i , σ 2) .

Further Y 1 , … ,Y n are assumed to be all independent.

The pdf for Y i is

( ) ;−∞< y < ∞
¿ 2
−1 y i −w 0−w 1 x i
1 2 σ
pY ( y i ) = e
√2 π σ
i 2 i

The Likelihood function for the tuple Y =(Y 1 , … ,Y n) is given by

L ( w 0 , w 1 ) := pY ( y ¿1 , … , y ¿n ; w 0 , w1)=p Y ( y ¿1 ) pY ( y ¿2 ) … pY ( y ¿n )
1 2 n

Therefore
n
log L(w0 , w1 , σ )=∑ log pY ( y ¿i ) i
i=1

(√ )
n n
1 1
¿ ∑ log 2∑( i
2
− y ¿−w0−w1 x¿i )
i=1 2 π σ2 2 σ i=1

We obtain the parameters w 0 , w1 , σ such that log L is maximized. This means that the
¿ ¿
parameters are chosen such that the probability of getting responses y 1 , … , y n
¿ ¿ ¿
corresponding to the observations x 1 , … , x n is maximum. This sounds reasonable because y i
¿
is the actual response corresponding to x i .

Partially differentiating w.r.t. w 0 , w1 we arrive at the same set of equations as obtained in the
OLS approach for computing the expressions for the parameters. (Exercise?)
Hence, we have the following MLE expressions:
¿ ¿
∑(x i −x)( y i − y ) S xY
w 1= 2
=
∑ ( x −x )
¿
i
S xx
 S xY
w 0=Y − x
S xx

Additionally, by equating the partial derivative w.r.t. σ to zero gives

√( )
2
1 S xY
σ= S YY −
n S xx

This can be seen as follows:

n
∂ log L −n 1
+ 3 ∑ ( yi¿−w0−w1 x¿i )
2
0= =
∂σ σ σ i=1

So we have
n
1 RSS
σ^ 2= ∑ ( y ¿ −^
n i=1 i
w 0− w
2
^1 x ¿i ) =
n
.

Note that
n
1
w 1= ∑ ( x ¿i −x )( y ¿i − y )
S xx i=1

( )
¿
1
n
y
n n
x −x ¿
¿ ∑
S xx i=1
( i ) i
x ¿
−x y ¿
− ∑
S xx i=1
( i ) ∑ i
x¿
−x =
S xx
yi .
i=1

^1 defined below is also normal:

Since Y i are normal, the random variable w

( )
¿
n
x i −x
^1 :=∑
w Y i.
i=1 S xx
¿
(Here Y i is a random variable whose particular value is y i .)

We now find the precise values of E [^

w1 ] and Var [ w
^1] .

( )
¿
n
x i −x
^1 ]=∑
E [w E [Y i ]
i=1 S xx

∑( )(
¿
n
x i −x
¿ w 0+ w1 x¿i )
i=1 S xx

∑( ) ∑
¿
n
x i −x w 1 n
¿ w0 + (x ¿i −x ¿) ( x ¿i −x+ x ) ¿
i =1 S xx S xx i=1

w1 n ¿ 2 w1 x
n
¿ ∑
S xx i=1
( x i −x ) + ∑
S xx i=1
( x ¿i −x )
 w1
¿ S =w1 .
S xx xx

Next, we find variance.

( )
¿ 2
n
x i −x
^1 ]=∑
Var [ w Var [ Y i ]
i=1 S xx

∑( )
¿ 2
n
x i −x 2 σ 2
¿ σ= .
i=1 S xx S xx

( )
2
σ
^1 N w1 ,
Hence w .
S xx

Recall that if X 1 , … , X k are independent random variables which are normally distributed

(∑ )
k k n
with means μi and variance σ 2i , then ∑ ci X i N ci μi , ∑ ci σ i .
2 2

i=1 i=1 i=1

Since each Y i N ( w 0+ w1 xi , σ ). So ∑ Y i N (n w 0 +w1 ∑ x ¿i , n σ 2 ). Therefore

¿ 2

( )
2
σ
Y N w 0 +w 1 x , .
n
^0=Y −^
We need to find the distribution of w w1 x .

( ) ( )
2 2 2 2 2
x σ σ x σ
Note that −x w
^1 N −x w1 , ^0=Y −^
. Hence w w1 x N w0 , + .
S xx n S xx

Equating the partial derivative of the log-likelihood w.r.t. σ we see that:

n
∂ log L −n 1
+ 3 ∑ ( yi¿−w0−w1 x¿i )
2
0= =
∂σ σ σ i=1

This yields
n
1
σ 2= ∑ ( y ¿ −w 0−w1 x ¿i )2 .
n i=1 i

This value of σ 2 is a particular instant of the random variable defined by:

n
1
σ^ = ∑ ( y ¿i −^
2
2
^ 1 x ¿i )
w 0− w
n i=1

Note that
 ( ) S^
¿
n
x i −x 1
n
^1=∑
w Y i= ∑ ( x¿i −x ) ( Y i−Y ) = xY .
i=1 S xx S xx i=1 S xx

Therefore
n
1
σ^ = ∑ ( y ¿i −Y + w
2
2
^ 1 xi¿ )
^1 x− w
n i=1

( S^
)
1
n ^
S xY ¿ 2

¿ ∑ y i −Y + x
¿ xY
− x
n i=1 S xx S xx i

( ) ∑(
1
n ^
2 1 S xY
2 n
2^S xY n
¿ ∑ ( y i −Y ) + ∑ ( y ¿−Y )(x ¿i −x)
2
xi −x ) −
¿ ¿
n i=1 n S xx i=1 n S xx i=1 i

1 ^ 1 S^ 1 2 S^ 1 ^ ^
( )
2 2 2
xY xY S xY
¿ SYY + − = SYY − .
n n S xx n S xx n S xx

Hence

√(
1 ^ S^
)
2

σ^ =
xY
S −
n YY S xx

(particular instances of the random variables ^

SYY and ^
S xY are SYY and S xY respectively.)

Regarding the probability distribution of σ^ we have the following result (proof omitted):

n σ^
2
2
The random variable U = 2
χ (n−2) .
σ
^0 and
The following two statistics are used often to determine the confidence intervals of w
^1:
w

Theorem: The statistics

Qw =
1
w
σ^ n √
^1−w 1 ( n−2 ) S xx
t (n−2)

and

Qw =
0
w
σ^ √
^0−w0 ( n−2 ) S xx
n x 2+ S xx
t(n−2)

The proof requires these 2 facts from statistics:

n σ^
2
2
Fact 1: The random variable U = 2
χ (n−2) .
σ
Fact 2: Suppose Z , T are independent random variables such that Z N (0 ,1) and T χ 2(n) .
Z
t (n)
Then T
√ n
.

Over here, we establish the first assertion.

^1−w1
w

( )
σ Z :=2 N (0 ,1)

√
^1 N w1 ,
We know that w . So, σ
2
.
S xx
S xx

n σ^
2
2
By Fact 1, U = 2
χ (n−2) . So, by Fact 2, we have
σ
Z
t(n−2)

√ U
n−2

Note that

Z w
=σ 1
√
^ −w 1 n−2 w ^ −w1 ( n−2 ) S xx
= 1
√
=Q w .

√ √
U σ
2
n σ^ 2
σ^ n 1

n−2 S xx

Consider the data where x is the predictor and y is the dependent variable.
x 4 9 10 14 4 7 12 22 1 17
y 31 58 65 73 37 44 60 91 21 84

Find the 95% confidence intervals for w 0 and w 1. Test the hypothesis H 0 :w 1=0, and H 0 :w 1=3 against the
alternative hypotheses H a :w 1 ≠ 0 and H a :w 1 ≠ 3 respectively at a significance level of 0.05 .

Using the above theorem, we will be in a position to say whether or not there is a
relationship between Y and X . Precisely, we test the Hypothesis:
H 0 :w 1=0

Against the alternative hypothesis:

H a :w 1 ≠ 0

In this problem n=10. We calculate S xx , S xy , S yy to be

S xx =376 , S xy =1305 , S yy =4752.411

Therefore
 S xy
^1=
w =3.47
S xx

√( )
2
1 S xY
σ^ = S YY − =4.72
n S xx

So, the t-statistic Q β for the Hypothesis H 0 : β=0 is

Qw = 1
4.72 √
3.47 ( 8 ) ( 376)
10
=12.74 .

Since the significance level is given to be 95 % , so we find the cutoff at 0.975 (this leaves out
2.5% area on either side of the t-curve). This cut-off is 2.306 (here degree of freedom is 8).
This means that the area under the t-curve from −∞ < x ≤2.306 is 97.5 % . So, the area under
the t-curve for x >2.306 is 2.5 %.
By symmetry of the t-curve, the area under the t-curve for x ←2.306 is also 2.5 % .
Hence P (−2.306< x <2.306 )=0.95.

Since 12.74> 2.306 so it is unlikely given the significance of 95%. Thus, we reject H 0 which
means we accept H a : β ≠ 0.

Further the 95% CI for β is given by

0.95=P ( −2.306 ≤Q w ≤ 2.306 ) =P −2.306 ≤

1 ( σ^ √
^1−w1 ( n−2 ) S xx
w
n
≤2.306 )
(
¿ P −2.306 σ^
√ n
( n−2 ) S xx
^1−w 1 ≤ 2.306 σ^
≤w
n
√
( n−2 ) S xx )
¿ P ( 2.842≤ w1 ≤ 4.098 )

Prediction Interval:

For a fixed observation x , we write Y x =w 0+ w1 x , and Y^ x =^ ^1 x . Note that Y^ x can be

w 0+ w
calculated from the data sample. Whereas, Y x is unknown. We will determine Y x
probabilistically.
Note that

E [ Y^ x ]=E [ w
^0 ] + E [ w
^1 x ]

¿ w 0 + xE [ w
^1 ] =w 0+ w1 x=Y x .

Also,

Var ( Y^ x ) =Var ( α^ + ^β x )=Var ( α^ ) + x Var ( ^β )

2
 2 2 2 2
σ x σ 2 σ
¿ + +x
n S xx S xx

By the Central Limit Theorem,

Y^ x −Y x
N (0 , 1)
√ Var ( Y^ x )

Thus we can construct the CI for Y x by marking cut-off points on the standard normal curve,

Precisely,

0.95=P −2<
( √
Y^ x −Y x
Var ( Y^ )
x
<2
)
¿ P ( Y^ x −2 Var ( Y^ x ) <Y x < Y^ x +2 Var ( Y^ x ) )
√ √
[ √ √ ]
The interval Y^ x −2 Var ( Y^ x ) , Y^ x +2 Var ( Y^ x ) is called the 95% prediction interval.