Intro to Big Data Science: Assignment 4 Solution

Description

Exercise 1

Log into “cookdata.cn”, and enroll the course “êâ‰Æ Ú”. Finish the online exer-cise there.

Exercise 2

The soft margin support vector classifier (SVC) is to solve the optimization problem:

1

w 2

n

(wT x

min

¯

C

»

,

s.t. y

i ¯

b)

˚

1

¡

»

,

»

i ˚

0,

i

˘

1, . . . , n (1)

w,b 2 k k2

i ˘1

i

i

i

X

1. Show that the KKT condition is

8

>_>fi_i ˚ 0,

>

>

>y (w^T x ¯b) ¡1 ¯» ˚ 0,

• iii

>

>

>	fii [yi (wT xi ¯b) ¡1 ¯»i ] ˘ 0,
>
>
>
>
>
>	„		˚		0,
	»ii				0,
>			˚
>
>
>	„	i	»	i		0,
>
<
>					˘
>	n
>
>
>
> P fii yi ˘ 0,
>
>					n	fii yi xi ,
>w
>	i ˘1
			˘ i 1
>					˘
>
>					P
>	fii					C ,
>					„i
>			¯			˘
>
>
>
>
>
:

where fi_i and „_i are the Lagrange multiplier for the constraints y_i (w^T x_i ¯b) ˚ 1¡»_i and »_i ˚ 0, respectively.

2. Show that the dual optimization problem is

1		n n				T	n
		X X					X
min					j yi y j xi xj ¡				,
			fi	fi			fi
fi 2 i ˘1 j ˘1			i				i ˘1	i
		n				0 É fii É C ,			i ˘ 1, . . . , n
s.t.		X fii yi ˘ 0,

• ˘1

• 3. Properties of Kernel:

• 3. 1. Using the definition of kernel functions in SVM, prove that the kernel K (x_i , x_j ) is symmetric, where x_i and x_j are the feature vectors for i -th and j -th exam-ples.

• 3. 2. Given n training examples (x_i , x_j ) for (i , j ˘ 1, . . . , n), the kernel matrix A is an n £ n square matrix, where A(i , j ) ˘ K (x_i , x_j ). Prove that the kernel matrix A is semi-positive definite.

Exercise 3 (Linear Classifiers) We can also use linear function f_w(x) ˘ w^T x to make classification. The idea is as follows: if f_w(x) ¨ 0, we assign 1 to label y; if f_w(x) ˙ 0, we assign -1 to label y. This can be regarded as 0/1-loss minimization:

n	1
X								(x
min			(1	¡	y	sign( f	w		))).
w i ˘1 2					i			i

1. Given a two-class data set {(x_i , y_i )}ⁿ_i˘1, we assume that there is a vector w satisfy-ing y_i sign( f_w(x_i )) ¨ 0 for i ˘ 1, . . . , n. Show that the 0/1-loss minimization can be formulated as a linear programming problem:

min 0, subject to Aw ˚ 1,

w

where A_{i j} ˘ y_i x_{i j} , 1 ˘ (1, . . . , 1)^T 2 Rⁿ , and the objective is dummy which means we don’t have to minimize it.

2. Another way to solve 0/1-loss minimization is to replace it by l₂-loss (sometimes this is also called surrogate loss):

min	n	2	n	f (x ))2.
	X		min (y
			X
w i ˘1(1 ¡ yi fw(xi )) ˘			w i ˘1	i ¡ w i

Please give the analytical formula of the solution.

• 3. So far we have introduced two loss functions: L_0/1(y, f ) ˘ ¹₂ (1¡ysign f ) and L₂(y, f ) ˘ (1 ¡ y f )². Show that the SVM can also be written as a loss minimization problem with the hinge loss function L(y, f ) ˘ [1¡y f ]_¯ ˘ max{1¡y f , 0} (the positive part of the function 1 ¡ y f ). Please also plot these three loss functions in the same figure and check their differences.

Exercise 4 (Logistic Regression)

We consider the following models of logistic regression for a binary classification with a sigmoid function g (z) ˘ _1¯¹_e¡z .

– Model 1: P(Y ˘ 1jX, w₁, w₂) ˘ g (w₁ X₁ ¯ w₂ X₂);

– Model 2: P(Y ˘ 1jX, w₁, w₂) ˘ g (w₀ ¯ w₁ X₁ ¯ w₂ X₂). We have three training examples:

x(1) ˘ (1, 1)T ,	x(2) ˘ (1, 0)T , x(3) ˘ (0, 0)T
y(1) ˘ 1,	y(2) ˘ ¡1, y(3) ˘ 1

1. Does it matter how the third example is labeled in Model 1? i.e., would the learned value of w ˘ (w₁, w₂) be different if we change the label of the third example to ¡1? Does it matter in Model 2? Briefly explain your answer. (Hint: think of the decision boundary on 2D plane.)

2. Now, suppose we train the logistic regression model (Model 2) based on the n training examples x⁽¹⁾, . . . , x⁽ⁿ⁾ and labels y⁽¹⁾, . . . , y⁽ⁿ⁾ by maximizing the penalized log-likelihood of the labels:

Xi	log P(y(i )jx(i ), w) ¡	‚	kwk2 ˘	Xi	log g (y(i )wT x(i )) ¡	‚		kwk2
		2				2

For large ‚ (strong regularization), the log-likelihood terms will behave as linear functions of w:

_{log g (y}(i )_wT _x(i )_{) …} ¹ _y(i )_wT _x(i )_.

2

Express the penalized log-likelihood using this approximation (with Model 1), and derive the expression for MLE wˆ in terms of ‚ and training data {x^{(i )}, y^{(i )}}. Based on this, explain how w behaves as ‚ increases. (We assume each x^{(i )} ˘ (x₁^{(i )}, x₂^{(i )})^T and y^{(i )} is either 1 or ¡1)

Exercise 5 (Back propagation in neural network) In a neural network, we have one layer of input x ˘ {x_i }, several hidden layers of hidden units {(z⁽_j^{l )}, a⁽_j^{l )})}, and a final layer of

outputs y. Let w_i^(l_j⁾ be the weight connecting unit j in layer l to unit i in layer l ¯ 1, z_i^(l) and a_i^{(l )} be the input and output of unit i in layer l before and after activation respec-tively, b_i^(l) be the bias (intercept) of unit i in layer l ¯ 1. For an L-layer network with an

input x and an output y, the forward propagating network is established according to the weighted sum and nonlinear activation f :

z(l ¯1)	˘W (l )a(l ) ¯b(l ), a(l ¯1) ˘ f (z(l ¯1)), for l ˘ 1, . . . , L ¡1
a(1)	˘x, and hW,b (x) ˘ a(L)

We use the square error as our loss function:

J(W, b; x, y) ˘ ¹ kh_W,b (x) ¡ yk²,

2

then the sample mean of loss functions after penalization is

1		n	‚ L¡1 sl			sl¯1	(jli))2.
J(W, b) ˘ n		X	J(W, b; x, y) ¯ 2			(w
					X X X
		i ˘1			l ˘1 i ˘1 j ˘1

1. In order to optimize the parameters W and b, we need to use gradient descent method to update their values:

wi( lj)

ˆ wi(lj)

¡fi

@

J(W, b),

bi(l ) ˆ bi(l ) ¡fi

@

J(W, b).

@w(l)

@b(l )

i j

i

The key point is to compute the partial derivatives

@

J(W, b; x, y) and

@

J(W, b; x, y).

(l )

(l )

@w

i j

@b

i

Show that these two partial derivatives can be written in terms of the residual

4