CS229 2017版作业3
课程视频地址：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
这部分回顾2017版作业3。
1. A Simple Neural Network
记第二层的输出为$g^{(i)}$
(a)由$w^{[1]}_{1,2}$的定义可知，我们需要先求出关于$h_2$的偏导数。
注意到我们有
其中$f$为sigmoid函数，那么先计算$l$关于$h_2^{(i)} $的偏导数可得
接着求$h_2^{(i)}$关于$w^{[1]}_{1,2}$的偏导数，注意到我们有
其中$f$为sigmoid函数，那么
(b)根据提示，中间层每个神经元应该对应于三角形区域的一条边，所以第一层的权重可以取
当点在三角形区域内时，结合激活函数可得输出结果为
注意只有此时神经元的输出结果为$1$，其余$7$中情形输出结果都为$0$，所以第二层的权重可以取
(c)不存在，因为当激活函数为$f(x)=x$时，产生的边界为直线，但是图像中边界为三角形，所以不可能使得损失为$0$。
2. EM for MAP estimation
对数似然函数为
对每个$i$，令$Q_i$是关于$z$的某个分布（$\sum_{z}Q_i(z)=1,Q_i(z)\ge 0$），考虑下式
等号成立当且仅当对某个不依赖的$z^{(i)}$的常数$c$，下式成立
结合$\sum_{i}Q_i(z^{(i)}) =1$，我们有
所以E步骤我们选择$Q_i(z^{(i)}) =p(z^{(i)}|x^{(i)},\theta)$，那么M步骤中，我们需要选择$\theta $为
最后证明上述算法会让$\prod_{i=1}^m p(x^{(i)}|\theta) p(\theta)$单调递增。假设$\theta^{(t)}$和$\theta^{(t+1)}$是两次成功迭代得到的参数那么
第一个不等号成立是因为如下不等式对任意$Q_i$和$\theta$都成立
特别地，上式对$Q_i=Q_i^{(t)},\theta = \theta^{(t+1)}$成立。第二个不等号成立是因为我们选择$\theta^{(t+1)}$为
因此这个式子在$\theta^{(t+1)}$的取值必然大于等于在$\theta^{(t)}$的取值。最后一个等号成立是在选择$Q_i^{(t)}$时我们就是要保证不等号取等号。
3. EM application
(a)
(i)因为$y^{(pr)},z^{(pr)}, \epsilon^{(pr)}$服从正态分布且相互独立，所以$(y^{(pr)},z^{(pr)}, \epsilon^{(pr)})^T$服从多元正态分布，因为
所以$(y^{(pr)},z^{(pr)}, x^{(pr)})^T$服从多元正态分布，因此只要分别计算期望和协方差矩阵即可。
首先求期望：
接着求协方差矩阵，首先求方差：
最后求协方差：
所以期望方差分别为
(ii)在求解该问题之前，介绍如下结论：
假设我们有一个向量值随机变量
其中$x_1\in \mathbb R^r, x_2 \in \mathbb R^s$，因此$x\in \mathbb R^{r+s}$。假设$x\sim \mathcal N(\mu, \Sigma)$，其中
其中，$\mu_1\in \mathbb R^r$，$\mu_2\in \mathbb R^s$，$\Sigma_{11}=\mathbb R^{r\times r}$，$\Sigma_{12}\in \mathbb R^{r\times s}$，以此类推。注意到因为协方差矩阵对称，所以$\Sigma_{12}=\Sigma_{21}^T$。
对上述随机变量，我们有
对于此题，我们有
所以
其中
因此
为了后续计算，这里再计算如下几个量：
(b)接下来我们需要最大化下式
注意到在迭代过程中我们视$Q_{pr}(y^{(pr)}, z^{(pr)})$为常数，因此我们需要最大化
上式可以记为
利用题目中的条件化简可得
将和参数无关的项丢弃，我们需要最大化：
代入(1)(2)(3)(4)，得到：
所以
令上述梯度为$0$，求解得到：
4. KL divergence and Maximum Likelihood
(a)我们知道$f(x)=-\log x$是凸函数，所以
当且仅当存在与$x$无关的$c$，使得下式成立时等号成立
所以
所以当且仅当$Q(x)=P(x)$时等号成立。
(b)
(c)不妨设对应的离散分布取值于$\{x_1,…,x_N\}$
所以最小化$KL(\hat P|| P_{\theta}) $等于最大化$\sum_{i=1}^n \log P_{\theta}(x^{(i)})$，因此
5. K-means for compression
本题有一个注意点，图片的数据格式为整型，运行聚类前需要将其转换为浮点型，否则会报错。另外，本题使用向量化的方法加快计算速度，介绍如下：
假设
其中$x^{(i)} ,y^{(i)} \in \mathbb R^d$，现在的问题是如何高效计算矩阵$D \in \mathbb R^{m\times n}$，其中
首先对$D_{i,j}$进行处理
那么
利用numpy的广播机制上式可以简写如下：
#计算距离矩阵
d1 = np.sum(X ** 2, axis=1).reshape(-1, 1)
d2 = np.sum(centroids ** 2, axis=1).reshape(1, -1)
dist = d1 + d2 - 2 * X.dot(centroids.T)全部代码如下：
from matplotlib.image import imread
import matplotlib.pyplot as plt
import numpy as np
plt.rcParams['font.sans-serif']=['SimHei'] #用来正常显示中文标签
plt.rcParams['axes.unicode_minus']=False #用来正常显示负号
def k_means(X, k, D=1e-5):
"""
X数据，k为聚类数量，D为阈值
"""
#数据数量
n = X.shape[0]
#聚类标签
clusters = np.zeros(n, dtype=int)
#初始中心点
index = np.random.randint(0, n, k)
centroids = X[index]
#记录上一轮迭代的聚类中心
centroids_pre = np.copy(centroids)
while True:
#计算距离矩阵
d1 = np.sum(X ** 2, axis=1).reshape(-1, 1)
d2 = np.sum(centroids ** 2, axis=1).reshape(1, -1)
dist = d1 + d2 - 2 * X.dot(centroids.T)
#STEP1:找到最近的中心
clusters = np.argmin(dist, axis=1)
#STEP2:重新计算中心
for i in range(k):
index = X[clusters==i]
#判断是否有点和某聚类中心在一类
if len(index) != 0:
centroids[i] = np.mean(index, axis=0)
#计算误差
delta = np.linalg.norm(centroids - centroids_pre)
#判断是否超过阈值
if delta < D:
break
centroids_pre = np.copy(centroids)
return clusters, centroids运行结果如下：
#读取图片并展示图片
A = imread('mandrill-large.tiff')
plt.imshow(A)
plt.title("聚类前的图像")
plt.show()
#将图片转化为矩阵
A_proceed = A.reshape(-1, 3)
#转换为浮点型，否则会报错
A_proceed = A_proceed.astype(np.float32)
#运行聚类
clusters, centroids = k_means(A_proceed, 16, 30)
#变成图片的形状
A_compressed = np.reshape(centroids[clusters], A.shape)
#转换为整型
A_compressed = A_compressed.astype(np.uint8)
#显示图像
plt.imshow(A_compressed)
plt.title("聚类后的图像")
plt.show()
总体来说图像效果还不错。