课程视频地址: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()

png

png

总体来说图像效果还不错。