课程视频地址:http://open.163.com/special/opencourse/machinelearning.html

课程主页:http://cs229.stanford.edu/

更具体的资料链接:https://www.jianshu.com/p/0a6ef31ff77a

作业地址:https://github.com/Doraemonzzz/CS229

参考资料:https://github.com/zyxue/stanford-cs229

这部分回顾老版作业2。

1.Kernel ridge regression

(a)记

所以

关于$\theta$求梯度可得

令上式为$0$可得

(b)首先证明题目中的等式:

因为

所以

所以由(a)可得

从而

对等式

可得

带回原式得到

下面分别计算$\tilde X\tilde X^T,\tilde X\phi(x_{\text{new}})$:

所以每一项只与内积有关,不需要计算$\phi(x_{\text{new}})$

2.$ℓ_2$ norm soft margin SVMs

(a)只要说明最优解必然满足$\xi_i \ge 0,\forall i =1,…,m$即可,利用反证法,假设存在$\xi_j <0$,那么

此时目标函数为

现在取$\xi_j’ =-\frac {\xi_j } 2>0$,那么

但是此时目标函数为

$(1)$减去$(2)$可得

这就与$(1)$是最小值矛盾,从而原假设成立。

(b)优化问题为

将条件化为标准形式

我们可以得到拉格朗日算子

这里,$α_i$拉格朗日乘子(约束为$≥0$)。

(c)求偏导并令为$0$可得:

化简得到

(d)将等式$(4)$带入$(3)$可得

将等式$(5)$带入可得

将等式$(6)$带入可得

所以对偶问题为

3.SVM with Gaussian kernel

(a)按提示取

因为$y \in \{-1,+1\}$,所以当下式满足时

$f(x^{(j)})$与$y^{(j)}$同号,即此时预测正确,接下来找到$\tau $使得上述不等式对任意$j=1,…,m$都成立。

首先计算$f(x^{(j)})$

注意到

那么

现在考虑$|f(x^{(j)})- y ^{(j)}|$的上界:

注意到条件有$||x^{(j)}-x^{(i)}|| >\epsilon$,所以

因此

如果我们有

那么对于任意$j$,必然有

求解不等式可得

所以只要满足上述不等式即可。

(备注,题目中取$\alpha_i =1$,但是实际应该满足

由于$y^{(i)}\in \{-1,+1\}$,所以总存在$M>0$,使得$ |\alpha_i|<M $且

在这个条件下,对之前的不等式稍作修改即可,结论依然成立。)

(b)由(a)可知存在$w$,使得样本分类正确,即

由(a)可知取$b=0$,那么$(1)$化为

注意到

让$\alpha _i$乘以一定的倍数,必然可以使下式

从而训练误差为$0$。

(c)不一定,因为我们在最小化

如果$C$很小,那么$C \sum_{i=1}^m \xi_i$的值很小,所以使上式最小的参数可能存在$\xi_i >0$,即训练误差不等于$0$。

4.Naive Bayes and SVMs for Spam Classification

见2017版的作业。

5.Uniform convergence

(a)首先回顾定义:

考虑如下概率:

$A_i$表示事件$| \epsilon(h_i) -\hat \epsilon(h_i)| > \gamma,\hat \epsilon(h_i)=0$,注意题目的条件为存在$h$,使得$\hat \epsilon(h)=0$,所以

等价,所以

两边同时减$1$可得

令$\delta = k e^{-\gamma m}$可得

注意$\hat h =\arg \min_{h\in \mathcal H} \hat \epsilon(h)$(此处有$\hat \epsilon (\hat h)=0$),所以有$1-\delta $的概率,如下事件发生

(b)令

那么此时

解得

从而