算法导论33.3 Exercises 答案

33.3-1

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

\[f(\mathbf{y}+\lambda(\mathbf{x}-\mathbf{y}))\le\lambda f(\mathbf{x})+(1-\lambda)f(\mathbf{y})\]

经过移项，可以写出

\[f(\mathbf{y}+\lambda(\mathbf{x}-\mathbf{y}))-f(\mathbf{y})\le\lambda f(\mathbf{x})-\lambda f(\mathbf{y})\]

假设\(\lambda\neq 0\)，那么有

\[\dfrac{f(\mathbf{y}+\lambda(\mathbf{x}-\mathbf{y}))-f(\mathbf{y})}{\lambda}+f(\mathbf{y})\le f(\mathbf{x})\]

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

\[\lim_{\lambda\rightarrow 0^{+}}\dfrac{f(\mathbf{y}+\lambda(\mathbf{x}-\mathbf{y}))-f(\mathbf{y})}{\lambda}+f(\mathbf{y})\le f(\mathbf{x})\]

最终得到

\[\langle(\nabla f)(\mathbf{y}),\mathbf{x-y}\rangle+f(\mathbf{y})\le f(\mathbf{x})\]

也就是有

\[f(\mathbf{y})\le f(\mathbf{x})+\langle(\nabla f)(\mathbf{y}),\mathbf{y-x}\rangle\]

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

33.3-2

为了方便，这题使用的下标范围是从\(1\)到\(T\)，即证明 \[f\left(\dfrac{\mathbf{x^{(1)}+x^{(2)}+\dots+x^{(T)}}}{T}\right)\le\dfrac{f(\mathbf{x^{(1)}})+f(\mathbf{x^{(2)}})+\dots+f(\mathbf{x^{(T)}})}{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\)进行移项，即可得到 \[f\left(\dfrac{\mathbf{x^{(1)}+x^{(2)}+\dots+x^{(T)}}}{T}\right)\le\dfrac{f(\mathbf{x^{(1)}})+f(\mathbf{x^{(2)}})+\dots+f(\mathbf{x^{(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}^na_i^2\\ &=\sum_{i=1}^n(2a_ib_i+b_i^2)\\ &=2\sum_{i=1}^na_ib_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})&=w_0+\sum_{i=1}^n w_i(\lambda x_i+(1-\lambda)y_i)\\ &=w_0+\sum_{i=1}^n (w_iy_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}w_ix_i\right)+(1-\lambda)\left(w_0+\sum_{i=1}^{n}w_iy_i\right)\\ &=w_0+\sum_{i=1}^n \lambda w_i 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 w_0}&=\sum_{i=1}^m \dfrac{\partial (e^{(i)})^2}{\partial w_0}\\ &=\dfrac{2}{m}\sum_{i=1}^m \left(w_0+\sum_{j=1}^nw_jx_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 w_k}&=\dfrac{1}{m}\sum_{i=1}^m \dfrac{\partial (e^{(i)})^2}{\partial w_k}\\ &=\dfrac{2}{m}\sum_{i=1}^m x_k^{(i)}\cdot\left(\left(w_0+\sum_{j=1}^nw_jx_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给出。

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}=(x_1,x_2,\dots,x_n),\mathbf{w}=(w_{\mathbf{0}},w_1,w_2,\dots,w_n)\)。

由于\(\displaystyle{f(\mathbf{x})=w_0+\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问题。