CS771 Introduction to ML Homework Assignment 1 Solved

Solution 1
Define

N

f(w) = X |yn − wT xn| + λ||w||1
(1)
n =1

where λ 0, yn ∈ R, xn ∈ RD×1 and w ∈ RD×1

We want to show that f(w) is convex, i.e,
 
f(tw1 + (1 − t)w2) ≤ tf(w1) + (1 − t)f(w2)
∀ t ∈ [0,1], w1, w2 ∈ RD×1
(2)
Note that,

                                     N                                                                     N                                              D

f(w) = X |yn − wT xn| + λ||w||1 = X |yn − xnTw| + λ X |wd|

                                    n =1                                                                n =1                                          d =1

Now consider, f(tw1 + (1 − t)w2)

       N                                                                                       D

= X  yn − xTn(tw1 + (1 − t)w2)  + λ X  t(w1)d + (1 − t)(w2)d 

      n =1                                                                                   d =1

       N                                                                                          D

= X  yn − txTnw1 − (1 − t)xnTw2  + λ X  t(w1)d + (1 − t)(w2)d 

      n =1                                                                                     d =1

       N                                                                                                                       D

= X  (t + (1 − t))yn − txTnw1 − (1 − t)xTnw2  + λ X  t(w1)d + (1 − t)(w2)d 

      n =1                                                                                                                  d =1

       N                                                                                                               D

= X  t(yn − xTnw1) + (1 − t)(yn − xTnw2)  + λ X  t(w1)d + (1 − t)(w2)d 

      n =1                                                                                                          d =1

       N                                                                                                                            D

≤ X   t(yn − xTnw1)  +  (1 − t)(yn − xTnw2)   + λ X   t(w1)d  +  (1 − t)(w2)d  

      n =1                                                                                                                        d =1

             N                                                                      N                                                               D                                                    D

= t X  (yn − xTnw1)  + (1 − t) X  (yn − xTnw2)  + λ t X  (w1)d  + (1 − t) X  (w2)d  

            n =1                                                                  n =1                                                           d =1                                               d =1

                 N                                                    D                                                           N                                                    D

= t ·  X  yn − xTnw1  + λ X (w1)d  + (1 − t) ·  X  yn − xnTw2  + λ X (w2)d 

                n =1                                               d =1                                                      n =1                                                d =1

= tf(w1) + (1 − t)f(w2)

Hence, we’ve shown that f(w) is convex

Subgradient
A subgradient of a convex function f : Rn → R at x0 ∈ Rn is any g ∈ Rn such that

f(x) ≥ f(x0) + gT (x − x0) ∀ x ∈ dom(f)

Collection of all subgradients of f at x0 is denoted by ∂f(x0), which is called subdifferential

We know that for h : R → R 3 x 7→ |x|, we have
 
                                     ∂h(x) = sign(x)      if x 6= 0      and       ∂h(0) = [−1,1]

where ∀ x 6= 0 (

                                                                          1        if x 0

sign(x) =

                                                                          −1     if x < 0

Let

n

                                              F : Rn → R 3 x 7→ ||x||1                     = X|xi|

i=1

Then, using (3), we can see that, if g ∈ ∂F(x), then

                                gi = sign(xi)      if xi 6= 0        and         gi ∈ [−1,1]      if xi = 0

Hence, we must have
(3)
                               ∂F(x) ⊇ {g ∈ Rn  g = X sign(xi) eDi + X cj eDj                           with cj ∈ [−1,1]}

                                                         xi6=0                                     xj=0

where eDj = (01, ...0i−1,1,0i+1 ...0D) ∈ RD×1

We wish to calculate the subgradient vector of

N f(w) = X |yn − wT xn| + λ||w||1

n =1

N

= X |yn − xTnw| + λ||w||1 n =1
(4)
N

= X |xTnw − yn| + λ||w||1
(5)
n =1

Using subdifferential calculus, we have

N

                    ∂f(w) = ∂        X |xTnw − yn| + λ||w||1 )

n =1

N

= ∂ X |xTnw − yn| + λ ∂||w||1

n =1

N

= X ∂|xTnw − yn| + λ ∂||w||1

n =1 N

= X xn∂|tn| + λ ∂||w||1 where tn = xTnw − yn n =1

N

                                         ⊇  X cn xn + λ X sign(wi) eiD + λ X kj eDj                  (6)

                                    n=1                           wi6=0                                          wj=0

                               where cn = sign(tn) if tn 6= 0            else cn ∈ [−1,1], and kj ∈ [−1,1]

We can always choose cn = 0 when tn = 0 and kj = 0 to get the required (sub)gradient vector

                        g =        X                      sign(xTnw − yn) xn + λ X sign(wi) eDi                 (∈ RD×1)                     (7)

                                xTnw−yn6=0                                                            wi6=0


Introduction to ML (CS771

QUESTION

Homework Assignment Number 1

Solution 2
Note that,

N

X(y − wT x )2 = (y − Xw)T (y − Xw) i        i

i=1

where y ∈ RN×1, X ∈ RN×D and w ∈ RD×1

We want to replace xi by ˜xi where ˜xi = xi ◦ mi, where mid ∈ {0,1} and mid ∼ Bern(p)

Let us define M ∈ RN×D where Mij ∈ {0,1} and Mij ∼ Bern(p)

Then similar to above, we can essentially write

N

                                   X                      − wT x˜i)2 = (y − (X ◦ M)w)T (y − (X ◦ M)w)

(yi i=1

For convenience, let L = X ◦ M and consider,

EM[(y − (X ◦ M)w)T (y − (X ◦ M)w)]

= EM[(y − Lw)T (y − Lw)]

= EM[yT y − 2wT LT y + wT LT Lw]

= yT y − 2wT EM(LT )y + wT E(LT L)w
(1)
= yT y − 2wT (EM(L))T y + wT E(LT L)w

Now, note that,

[EM(L)]ij = EM(Lij)

= E(XijMij)

= pXij ⇒ EM(L) = pX
(2)
⇒ 2wT (EM(L))T y = 2pwT XT y
(3)
Also, note that,

[EM(LT L)]ij = EM[(LT L)ij]

N

= EM[X(LT )ikLkj]

k=1

N

= EM[X LkiLkj]

k=1 N

= EM[X XkiMkiXkjMkj]

k=1 N

= EM[X XkiXkjMkiMkj]

k=1
 
N

= X XkiXkjEM[MkiMkj]

k=1
(4)
When i = j, EM[MkiMkj] = EM[Mki2 ] = VM(Mki) + E(Mki)2 = p(1 − p) + p2 = p and when i 6= j, EM[MkiMkj] = EM[Mki]EM[Mkj] = p2 Therefore, using these observations, we have

                                                  N                          N

When i = j, [EM(LT L)]ij = p P Xki2 = p P (XT )ikXki = p(XT X)ii = p(XT X)ij

                                                 k=1                       k=1

                                                         N                                     N

and when i 6= j, [EM(LT L)]ij = p2 P XkiXkj = p2 P (XT )ikXkj = p2(XT X)ij

                                                        k=1                                  k=1

Therefore,
                             [EM(LT L)]ii = p(XT X)ii               and           [EM(LT L)]ij = p2(XT X) (i 6= j)

Using (2),(3) and (5), we get

EM[(y − (X ◦ M)w)T (y − (X ◦ M)w)]

= yT y − 2wT (EM(L))T y + wT E(LT L)w

= yT y − 2pwT XT y + wT EM(LT L)w

= yT y − 2pwT XT y + p2wT XT Xw − p2wT XT Xw + wT EM(LT L)w
(5)
= (y − pXw)T (y − pXw) + wT (EM(LT L) − p2XT X]w
(6)
Now note that, from (5),

[EM(LT L) − p2XT X]ii = p(1 − p)(XT X)ii and [EM(LT L) − p2XT X]ij = 0 (i =6 j)

and therefore,

                                                 EM(LT L) − p2XT X = p(1 − p)diag(XT X)                                             (7)

Finally, using (6) and (7), we obtain

EM[(y − (X ◦ M)w)T (y − (X ◦ M)w)]

= (y − pXw)T (y − pXw) + wT (EM(LT L) − p2XT X]w

= (y − pXw)T (y − pXw) + p(1 − p)wT diag(XT X)w

= (y − pXw)T (y − pXw) + p(1 − p)[diag(XT X)1/2]T [diag(XT X)1/2]w

                             = (y − pXw)T (y − pXw) + p(1 − p)[diag(XT X)1/2w]T [diag(XT X)1/2w]                        (1)

Hence, we get

N

EM[X(yi − wT x˜i)2] = (y − pXw)T (y − pXw) + p(1 − p)[diag(XT X)1/2w]T [diag(XT X)1/2w]

i=1

(9) Therefore,

N

arg minw[EM[X(yi − wT x˜i)2]]

i=1

                   = arg minw[(y − pXw)T (y − pXw) + p(1 − p)[diag(XT X)1/2w]T [diag(XT X)1/2w]]                  (10)

which is equivalent to Ridge Regression and the required regularized loss function is

L(w) = (y − pXw)T (y − pXw) + p(1 − p)[diag(XT X)1/2w]T [diag(XT X)1/2w]        (11) Introduction to ML (CS771), Autumn 2020

QUESTION
Indian Institute of Technology Kanpur Homework Assignment Number 1          3

Student Name: Vishweshwar Tyagi

Roll Number: 191173

Date: October 30, 2020



Solution 3
M

TR[(Y − XW)T (Y − XW)] = X[(Y − XW)T (Y − XW)]ii

i=1

                                                                         M      N

= X X[(Y − XW)T ]ik(Y − XW)ki

i=1 k=1

                                                                         M      N

= X X(Y − XW)ki(Y − XW)ki

i=1 k=1

                                                                         M      N

= X X[(Y − XW)ki]2

i=1 k=1

                                                                         M      N

= X X[Yki − (XW)ki]2

i=1 k=1

                                                                         M      N

= X X yki − X[k,:]W[:,i]2

i=1 k=1

M N = X X yki − xTk wi2

i=1 k=1

M                N = X X yki − wiT xk2

i=1 k=1

N                 M

= X Xyki − wiT xk2

k=1 i=1

                                                                          N       M

= X X ynm − wmT xn2

n=1 m=1

Hence, we have shown that,

                                N       M

                                              X X ynm − wmT xn2 = TR[(Y − XW)T (Y − XW)]                                         (1)

n=1 m=1

Now, we assume that,

                                                                      W = BS                                                                  (2)

where B ∈ RD×K and S ∈ RK×M

Note that, ∀ m ∈ {1,2...M}

wm = W[:,m]

= (BS)[:,m]

= BS[:,m]

K

                                                                       = XsimB[:,i]                                                            (3)

i=1

Hence, we note that, the columns of W, that is, wm (m = 1,2...M) can be written as a linear

combination of the K columns of B

Using (1) and (2), out optimization problem now becomes
(4)
{Bˆ,Sˆ} = arg minB,STR[(Y − XBS)T (Y − XBS)]
(5)
We will try to learn B and S using Alternating Optimization

Define

L(B,S) = TR[(Y − XBS)T (Y − XBS)]

= TR[(Y T − ST BT XT )(Y − XBS)]

= TR(Y T Y − ST BT XT Y − Y T XBS + ST BT XT XBS)

= TR(Y T Y ) − TR(ST BT XT Y ) − TR(Y T XBS) + TR(ST BT XT XBS)

= TR(Y T Y ) − 2 TR(Y T XBS) + TR(ST BT XT XBS)

Given Bt and St, we will first try to solve the following two sub-problems:
(6)
Bt+1 = arg minBL(B,St)

and
(6.1)
St+1 = arg minSL(Bt+1,S)
(6.2)
∇BL(B,S) = ∇BTR(Y T Y ) − 2 TR(Y T XBS) + TR(ST BT XT XBS)

                                            = −2XT YST + 2XT XBSST                                                                                                     (6.3)

∇SL(B,S) = ∇STR(Y T Y ) − 2 TR(Y T XBS) + TR(ST BT XT XBS)

                                            = −2BT XT Y + 2BT XT XBS                                                                  (6.4)

Using (6.3) and (6.1) we have

∇BL(B,S) = 0

⇒ − 2XT YST + 2XT XBSST = 0

⇒ XT XBSST = XT YST

⇒ B = (XT X)−1XT YST (SST )−1

⇒ arg minBL(B,St) = (XT X)−1XT Y (St)T (St(St)T )−1

Using (6.4) and (6.2) we have

∇SL(B,S) = 0

⇒ − 2BT XT Y + 2BT XT XBS = 0

⇒ BT XT XBS = BT XT Y

⇒ S = (BT XT XB)−1BT XT Y

⇒ S = [(XB)T XB]−1(XB)T Y
(6.5)
⇒ arg minSL(Bt+1,S) = [(XBt+1)T XBt+1]−1(XBt+1)T Y
(6.6)
Hence, the required Alternating Optimization algorithm is:

Optimization problem:

{Bˆ,Sˆ} = arg minB,SL(B,S) = arg minB,STR[(Y − XBS)T (Y − XBS)]

1.   Initialise S0, t = 0

2.   Update

Bt+1 = arg minBL(B,St)

                                                           = (XT X)−1XT Y (St)T (St(St)T )−1                                                                     (7)

St+1 = arg minSL(Bt+1,S)

                                                           = [(XBt+1)T XBt+1]−1(XBt+1)T Y                                               (8)

3.   t = t + 1

4.   Goto Step 2 if not yet converged.

Therefore, (7) and (8) provide the required updates for Alternating Optimization algorithm

Since we have K < min{D,M}, it becomes clear from (7) and (8) that the subproblem

Bt+1 = arg minBL(B,St)

is computationally more demanding and difficult to solve than the subproblem

St+1 = arg minSL(Bt+1,S)

as in (7) we need to invert XT X which is a D × D matrix whereas in (8) we need to invert (XB)T XB which is only a K × K matrix with K < D

Introduction to ML (CS771), Autumn 2020

QUESTION

Indian Institute of Technology Kanpur

Homework Assignment Number 1

Student Name: Vishweshwar Tyagi                                                                                4

Roll Number: 191173

Date: October 30, 2020



Solution 4
For a given loss function L(w) of unknown weight vector w ∈ RD×1, the Newton’s method minimises the second order approximation of L(w), that is, in order to get the next updated weight vector wt+1 from wt, we solve

              wt+1 = arg minwL                       (1∗)

Let

                      f )                  (2)

Note that, L : RD → R 3 w 7→ L(w)

Hence

                                ∇L(w) ∈ R1×D and ∇2L(w) ∈ RD×D which is the Hessian matrix                         (3∗∗)

For convenience, denote ∇L(wt) by gt and denote ∇2L(wt) by Ht and note that (Ht)T = Ht

From (2) we have

f 

1

= L(wt) + gt(w − wt) +(w − wt)T Ht(w − wt)

2

1

= L(wt) + gt(w − wt) +(wT Htw − 2(wt)T Htw + (wt)T Htwt)

2

 wT Ht − 2(wt)T Ht + 0)

⇒ ∇f(w) = gt + wT Ht − (wt)T Ht

∇f(w) = 0

⇒ wT Ht = (wt)T Ht − gt

⇒ wT = (wt)T − gt(Ht)−1

                              ⇒ w = wt − (Ht)−1(gt)T                           using (Ht)−1T = (Ht)T −1 = (Ht)−1

                             ⇒ w = wt  T                                                                                                               (4)

* Contrary to what is used in slides, I have used ∇L(w) instead of [L(w)]T because of (3∗∗)

** Convention followed in Calculus on Manifolds, Michael Spivak, Theorem 2-7

Using (1∗) and (4) we get

                                                        wt+1 = wt − (Ht)−1[∇L(wt)]T                                                                               (6)

Newton Method’s update for the given model
We are given that,

                                                L  Xw)T (y − Xw) + λwT w]                                          (7)

 1[yT y − 2yT Xw + wT XT Xw + λwT w]  yT X + 2wT XT X + 2λwT ]

                                      ⇒ ∇[L(wt)]T = XT Xwt + λwt − XT y                                                               (8)

⇒ ∇2L(w) = XT X + λID

                                      ⇒ ∇2L(wt) = XT X + λID                                                                                                                    (9)

Using (6), (8) and (9), we get the Newton Method’s update for our model as follows:

wt+1 = wt − (XT X + λID)−1[XT Xwt + λwt − XT y]

= wt − (XT X + λID)−1[(XT X + λID)wt − XT y]

                                              = (XT X + λID)−1XT y                                                                         (10)

(10) gives the required update for Newton’s Method.

We see that this update is independent of the input wt

Infact, for input w0, we get w1 = (XT X + λID)−1XT y which is the closed form solution of Ridge Regression given in (7).

Hence, in the case of Ridge Regression, Newton’s Method converges just after one step!

Introduction to ML (CS771), Autumn 2020

QUESTION
Homework Assignment Number 1       


Solution 5
We are rolling a six faced die N times. Ni = # of times i’th face is obtained πi = probability of showing i’th face on a dice roll

                  6                                     6

Note that P Ni = N and P πi = 1 where πi ∈ (0,1)

                  i=1                                  i=1

Likelihood
Let the outcome of N dice rolls be represented as Y = {y1,y2 ...,yN} where yi ∈ {1,2,...6}. Assuming that this data is Independent and Identically Distributed (IID), we have the following likelihood:

6

                                                                 p(Y |π) = Y πiNi                                                                                                                                                                                      (1)

i=1

where, π = {π1,π2,...,π6}

Prior
6

Note that we have, πi ∈ (0,1) and P πi = 1

i=1

Hence, an appropriate prior conjugate to our likelihood above would be the Dirichlet prior given by:

                                                                                   1     Y6       αi−1

                                                  p(π) = Dir(π|α) =           πi                                                                          (2)

B(α)

i=1

where, α = {α1,α2,...,α6} is a vector of hyperparameters which we assume to be fixed and

6

Q Γαi

                                                              B(α) = i=1                                                                                       (3)

6

Γ(P αi) i=1 MLE Estimation
We have,

LL(π) = log(p(Y |π))

6

= log(Y πiNi)

i=1

6

                                                                        = XNi log(πi)                                                        (4)

i=1 6

We know that, πˆMLE = arg maxπLL(π) with respect to the constrain P πi = 1

i=1

where πˆMLE = (πˆ1,πˆ2 ...πˆ6)

We will solve this using Lagrange multiplier as follows:

                                                              6                                                   6

                                                      l(π,λ) = XNi log(πi) + λ(1 − Xπi)                                                 (5)

                                                             i=1                                                i=1

                                                                     6                              6

                                                       lλ = 0 ⇒ 1 − Xπi = 0 ⇒ Xπi = 1                                                (5.1)

                                                                    i=1                           i=1

Nj

                                               lπj = 0 ⇒        − λ = 0 ⇒ Nj = λπj                                                                       (5.2)

πj

From (5.1) and (5.2) we have

                                                        6                         6

                                                        X                        X

Nj = λ πj ⇒ N = λ j=1              j=1

Substituting this back into (5.2) we get

Nj

πˆj =     ∀ j = 1,2...6 N

Hence, we have

                                                             πˆMLE = N1, N2 ... N6                                                                                     (6)
                                                                        N     N        N

MAP Estimation
Using (4), we have,

6

LL(π) + log(p(π)) = XNi log(πi) + log(p(π))

i=1

                                                                  6                                                            6

                                                                 = XNi log(πi) + log(    1  Y πiαi−1)

B(α)

i=1       i=1 (ignoring any constants, we get)

6

                                                                  = X(Ni + αi − 1)log(πi)                                                  (7)

i=1 6

We know that, πˆMAP = arg maxπ(LL(π) + log(p(π)) with respect to the constrain P πi = 1

i=1 where πˆMAP = (πˆ1,πˆ2 ...πˆ6)

We will solve this using Lagrange multiplier as follows:

                                                          6                                                                           6

                                                   l(π,λ) = X(Ni + αi − 1)log(πi) + λ(1 − Xπi)                                       (8)

                                                         i=1                                                                         i=1

                                                                                   6                              6

                                                                    lλ = 0 ⇒ 1 − Xπi = 0 ⇒ Xπi = 1                                  (8.1)

                                                                                  i=1                           i=1

Nj + αj − 1

lπj = 0 ⇒              − λ = 0 ⇒ Nj + αj − 1 = λπj          (8.2) πj

                                                                                       6                                6

From (8.1) and (8.2) we have P6j=1(Nj + αj − 1) = λ P πj ⇒ N + P αj − 6 = λ

                                                                                      j=1                             j=1

Substituting this back into (8.2) we get

Nj + αj − 1

Hence, we have
πˆj =   6            ∀ j = 1,2...6

N + P αi − 6

i=1
 
πˆMAP =
N1 + α1 − 1              N2 + α2 − 1                N6 + α6 − 1

                       ,                         ...

         6                                    6                                          6
(9)
N + P αi − 6 N + P αi − 6 N + P αi − 6 i=1 i=1 i=1

Posterior
We have,

p(π|Y ) ∝ p(Y |π)p(π)

                                                               6                                          6

                                                             ∝ Y πiNi ×   1   × Y πiαi−1

B(α)

                                                              i=1                                       i=1

6

∝ Y πiNi+αi−1

i=1

                                                            = Dir(π|n + α)                                                                (10)

which gives the required posterior distribution where,

n = {N1,N2 ...N6} and hence, n + α = {N1 + α1,N2 + α2 ...N6 + α6}

MAP and MLE Estimation from Posterior
We can obtain MAP Estimation from Posterior using its mode.

The mode of Dir(π|n + α) where n + α = {N1 + α1,N2 + α2 ...N6 + α6} is given by

              Mode :                 N1 + α1 − 1 , N2 + α2 − 1 ... N6 + α6 − 1                                             = πˆMAP 

                                     6                                    6                                          6

                                   N + P αi − 6 N + P αi − 6                 N + P αi − 6

                                    i=1                                 i=1                                       i=1

which is precisely what we obtained in (9)

We can further obtain the MLE Estimation from this by using uniform prior, that is, by substituting above αi = 1 ∀ i = 1,2...6 to get

πˆMLE = N1, N2 ... N6

                                                                        N     N        N

Q When can we expect MAP solution to be better than MLE?

Since we are quite confident about the distribution of our prior, we can certainly say that MAP solution will always be better than MLE for this model because MAP takes into account regularization, which MLE doesn’t. Thus, to prevent overfitting, MAP will be better.