算法导论33.3 Exercises 答案

发表于 更新于 分类于 阅读次数： 本文字数： 5.2k 阅读时长 ≈ 5 分钟

33.3-1

由于$f$是凸函数，因此改写不等式33.18，可以得到

经过移项，可以写出

假设$\lambda\neq 0$，那么有

当$\lambda$无限接近于$0$时，也就是

最终得到

也就是有

交换变量$\mathbf{x,y}$即可得到原结论。

33.3-2

为了方便，这题使用的下标范围是从$1$到$T$，即证明

令$\displaystyle{\mathbf{y^{(i)}}=\dfrac{\sum_{j=1}^i \mathbf{x^{(j)}}}{T}}$，那么对$i=2,3,4,\dots,T$，都有

$\begin{aligned}
f(\mathbf{y^{i}})&=f\left(\dfrac{\mathbf{x^{(i)}}}{i}+\dfrac{(i-1)\mathbf{y^{(i-1)}}}{i}\right)\
&\le \dfrac{f(\mathbf{x^i})}{i}+\dfrac{(i-1)f(\mathbf{y^{(i-1)}})}{i}&\qquad(A)
\end{aligned}$

其中步骤$(A)$使用了凸函数$f$的性质，因为此时$\lambda=\dfrac{1}{i}$。

考虑对$Tf(\mathbf{y^{(T)}})$循环代入上面的不等式，那么得到

$\begin{aligned}
T(\mathbf{y^{(T)}})&\le f(\mathbf{x^{(T)}})+(T-1)f(\mathbf{y^{(T-1)}})\
&\le f(\mathbf{x^{(T)}})+f(\mathbf{x^{(T-1)}})+(T-2)f(\mathbf{y^{(T-2)}})\
&\dots\
&\le f(\mathbf{x^{(T)}})+f(\mathbf{x^{(T-1)}})+\dots+ f(\mathbf{y^{(1)}})\
&\le f(\mathbf{x^{(T)}})+f(\mathbf{x^{(T-1)}})+\dots+f(\mathbf{x^{(1)}})
\end{aligned}$

重新将$\mathbf{y^{(T)}}$回代到上面的不等式，并将$T$进行移项，即可得到

33.3-3

令$\mathbf{a}=(a_1,a_2,\dots,a_n),\mathbf{b}=(b_1,b_2,\dots,b_n)$。考虑计算$\lVert\mathbf{a}+\mathbf{b}\rVert^2-\lVert\mathbf{a}\rVert^2$的值，根据向量积和模长的定义，可以得到：

$\begin{aligned}
\lVert\mathbf{a}+\mathbf{b}\rVert^2-\lVert\mathbf{a}\rVert^2&=\sum{i=1}^n(a_i+b_i)^2-\sum{i=1}^nai^2\
&=\sum{i=1}^n(2aib_i+b_i^2)\
&=2\sum{i=1}^naib_i+\sum{i=1}^nb_i^2\
&=2\langle\mathbf{a},\mathbf{b}\rangle+\lVert\mathbf{b}\rVert^2
\end{aligned}$

原结论得证。

33.3-4

令$\mathbf{x}=(x_1,x_2,\dots,x_n),\mathbf{y}=(y_1,y_2,\dots,y_n)$。考虑使用不等式33.18来证明$f(\mathbf{x})$是凸函数。那么对于$\lambda\in[0,1]$，有以下两个值：

$\begin{aligned}
f(\lambda\mathbf{x}+(1-\lambda)\mathbf{y})&=w0+\sum{i=1}^n wi(\lambda x_i+(1-\lambda)y_i)\
&=w_0+\sum{i=1}^n (wiy_i+\lambda w_i(x_i-y_i))\
\
\lambda f(\mathbf{x})+(1-\lambda)f(\mathbf{y})&=\lambda\left(w_0+\sum{i=1}^{n}wix_i\right)+(1-\lambda)\left(w_0+\sum{i=1}^{n}wiy_i\right)\
&=w_0+\sum{i=1}^n \lambda wi x_i+(1-\lambda)w_iy_i\
&=w_0+\sum{i=1}^n (w_iy_i+\lambda w_i(x_i-y_i))\
\end{aligned}$

因此有$f(\lambda\mathbf{x}+(1-\lambda)\mathbf{y})=\lambda f(\mathbf{x})+(1-\lambda)f(\mathbf{y})$。这满足了凸函数的等号特殊条件，因此$f(\mathbf{x})$是凸函数。

33.3-5

令$\displaystyle{g(\mathbf{w})=\dfrac{1}{m}\sum{i=1}^m (e^{(i)})^2}$，其中$\displaystyle{e^{(i)}}=\left(w_0+\sum{j=1}^nw_jx_j^{(i)}\right)-y^{(i)}$。注意，$\mathbf{w}$是未知的；但是$\mathbf{x^{(i)}}$和$y^{(i)}$都是已知的，都将它们看作常数对待。

先考虑计算$\dfrac{\partial g}{\partial w_0}$的值，那么有：

$\begin{aligned}
\dfrac{\partial g}{\partial w0}&=\sum{i=1}^m \dfrac{\partial (e^{(i)})^2}{\partial w0}\
&=\dfrac{2}{m}\sum{i=1}^m \left(w0+\sum{j=1}^nwjx_j^{(i)}\right)-y^{(i)}\
&=\dfrac{2}{m}\sum{i=1}^m e^{(i)}
\end{aligned}$

再考虑计算$\dfrac{\partial g}{\partial w_k}$的值，其中$k\in[1,n]$，那么有：

$\begin{aligned}
\dfrac{\partial g}{\partial wk}&=\dfrac{1}{m}\sum{i=1}^m \dfrac{\partial (e^{(i)})^2}{\partial wk}\
&=\dfrac{2}{m}\sum{i=1}^m xk^{(i)}\cdot\left(\left(w_0+\sum{j=1}^nwjx_j^{(i)}\right)-y^{(i)}\right)\
&=\dfrac{2}{m}\sum{i=1}^m x_k^{(i)}\cdot e^{(i)}
\end{aligned}$

那么计算方法非常简单。对于第$i$条数据，我们先以$O(n)$的时间计算出$e^{(i)}$的值，然后根据$e^{(i)}$，分别以$O(1)$的时间再计算出$\dfrac{\partial g}{\partial w_0},\dfrac{\partial g}{\partial w_1},\dots,\dfrac{\partial g}{\partial w_n}$的值，这总共需要$O(n)$的时间。对这$m$条数据都进行这样的操作，并将对应的梯度值相加即可得到结果，总共花费的时间为$O(nm)$。这个算法由NABLA-W给出。

1
2
3
4
5
6
7
8
9
10
11
NABLA-W(W, X, Y, n, m)
  let D[0 : n] be new array by 0
  for i = 1 to m
    e = 0
    for j = 1 to n
      e = e + W[j] * X[i, j]
    e = e + W[0] - Y[i]
    D[0] = D[0] + 2 * e
    for j = 1 to n
      D[j] = D[j] + 2 * e * X[i, j]
  return D

33.3-6

令$\mathbf{x}=(x1,x_2,\dots,x_n),\mathbf{w}=(w{\mathbf{0}},w_1,w_2,\dots,w_n)$。

由于$\displaystyle{f(\mathbf{x})=w0+\sum{i=1}^n w_ix_i}$，因此对于$\forall i\in [1,n]$，都有$\dfrac{\partial f}{\partial x_i}=w_i$。也就是说，有$(\nabla f)(\mathbf{x})=(w_1,w_2,\dots,w_n)$。

由于$\lVert \mathbf{w}\rVert\le B$，那么有

$\begin{aligned}
\lVert (\nabla f)(\mathbf{x})\rVert &=\sqrt{\sum{i=1}^n w_i^2}\
&\le\sqrt{w_0^2+\sum{i=1}^n w_i^2}\
&=B
\end{aligned}$

因此$\lVert (\nabla f)(\mathbf{x})\rVert\le B$对于任意$\mathbf{x}\in \mathbb{R}^n$都成立。只需要取$L=B$即可，因此$L=O(B)$。

33.3-7

本质上，我们的目标是将$\displaystyle{f(S,C)=\sum{\ell=1}^k\sum{\mathbf{x}\in S^{(\ell)}}\Delta(\mathbf{c^{(\ell)},x})}$最小化。对每个聚类中的重心$\mathbf{c^{(\ell)}}$，使用梯度下降来让重心朝某个方向移动一定距离，并且保证最终距离平方和减少。

具体过程是，令$\displaystyle{h(\mathbf{c^{(\ell)}})=\sum_{\mathbf{x}\in S^{(\ell)}}\Delta(\mathbf{c^{(\ell)},x})}$。那么将$h(\mathbf{c^{(\ell)}})$当作是损失函数，对原来的重心$\mathbf{c^{(\ell)}}$移动$\lambda \cdot(\nabla h)(\mathbf{c^{(\ell)}})$的一步。根据梯度下降的原理，$h(\mathbf{c^{(\ell)}})$值已经减小了。如果在下一步迭代中，某个点所属类别发生了变更（假设变更到了$S^{\ell’}$），那么说明$\Delta(\mathbf{x,c^{(\ell)}})>\Delta(\mathbf{x,c^{(\ell’)}})$，这将确保总体上$f(S,C)$的值是下降的。

因此，使用梯度下降可以有效解决$k$-means问题。