算法导论33 Problems 答案

33-1

a

直线\(y=f'(x)(x-x^{(t)})+f(x^{(t)})\)的\(x\)轴截距是，令\(y=0\)，然后计算出\(x=-\dfrac{f(x^{(t)})}{f'(x^{(t)})}+x^{(t)}\)。因此有

\[x^{(t+1)}=x^{(t)}-\dfrac{f(x^{(t)})}{f'(x^{(t)})}\]

b

由于题中已经给定了，如果\(x^{(0)}\)满足方程33.34，那么对于距离比\(x^{(0)}\)更近的点，也满足这个方程。

也就是说，对于迭代过程所得到的\(x^{(1)},x^{(2)},\dots,x^{(t)}\)中的所有\(t\)，上述方程均成立，因为\(x^{(1)},x^{(2)},\dots,x^{(t)}\)都将比\(x^{(0)}\)距离\(x^{\ast}\)更近。因此只需要证明\(t=0\)的情况即可。

考虑\(\epsilon^{(1)}\)的值，有

\(\begin{aligned} \epsilon^{(1)}&=|x^{(1)}-x^{\ast}|\\ &=\left|x^{(0)}-\dfrac{f(x^{(0)})}{f'(x^{(0)})}-x^{\ast}\right|\\ &=\left|x^{(0)}+\dfrac{f'(x^{(0)})(x^{\ast}-x^{(0)})+\frac{1}{2}f''(\gamma^{(0)})(x^{\ast}-x^{(0)})^2-f(x^{\ast})}{f'(x^{(0)})}-x^{\ast}\right|\\ &=\left|\dfrac{\frac{1}{2}f''(\gamma^{(0)})(x^{\ast}-x^{(0)})^2-f(x^{\ast})}{f'(x^{(0)})}\right|\\ &=\left|\dfrac{f''(\gamma^{(0)})(x^{\ast}-x^{(0)})^2}{2f'(x^{(0)})}\right|\\ &=\left|\dfrac{f''(\gamma^{(0)})}{2f'(x^{(0)})}\right|(\epsilon^{(0)})^2\\ &=\left|\dfrac{f''(\gamma^{(0)})}{2f'(\gamma^{(0)})}\right|\epsilon^{(0)}&\qquad(?)\\ \end{aligned}\)

步骤\((?)\)暂时未知怎么得出，目前在此提问。

因此对于\(t=1,2,3,4,\dots\)，原结论都成立。

c

由于\(\dfrac{|f''(\gamma^{(t)})|}{2|f'(\gamma^{(t)})|}\le c\)，因此有\(\epsilon^{(t+1)}\le c\epsilon^{(t)}\)。随着每一次代入，那么有\(\epsilon^{(t)}\le c^t\epsilon^{(0)}\)。

如果要令\(\epsilon^{(t)}\le \delta\)，那么就有

\[c^t\epsilon^{(0)}\le \delta\]

由于\(c<1\)，那么对两边对\(c\)取对数，可以得到迭代轮数\(t\ge\log_c(\delta/\epsilon^{(0)})\)。也就是说迭代轮\(t\)必须至少要达到这个值。

d

可以知道，\(f''(x)=2,f'(x)=2x-6\)。并且不难知道，\(x^{\ast}=3,f(x^{\ast})=0\)。

考虑使用梯度下降法最小化\(f(x)\)。由于\(x_0=3.5,x^{\ast}=3\)，因此\(R=0.5\)。由于\(x\in[x^{\ast},x^{(0)}]\)，那么有\(f'(x)\in[0,1]\)，因此\(L=1\)。根据定理33.8，为了使\(f(x-\text{avg})-f(x^{\ast})<\delta\)，那么迭代轮数\(T\)必须满足\(\delta=\dfrac{LR}{\sqrt{T}}\)，也就是\(T=\dfrac{1}{4\delta^2}\)，此时需要选择\(\gamma=\dfrac{R}{L \sqrt{T}}=\delta\)。

考虑使用牛顿迭代法求解\(f(x)=0\)的根，那么考虑从\(x^{(t)}\)计算出\(x^{(t+1)}\)的值，并比较\(\epsilon^{(t)}=x^{(t)}-x^{\ast}\)和\(\epsilon^{(t+1)}=x^{(t+1)}-x^{\ast}\)。结合\(x^{(t+1)}=x^{(t)}-\dfrac{f(x^{(t)})}{f'(x^{(t)})}\)，有：

\(\begin{aligned} \epsilon^{(t+1)}&=x^{(t+1)}-x^{\ast}\\ &=x^{(t)}-\dfrac{(x^{(t)}-3)^2}{2(x^{(t)}-3)}-3\\ &=x^{(t)}-\dfrac{x^{(t)}-3}{2}-3\\ &=\dfrac{x^{(t)}-3}{2}\\ &=\dfrac{\epsilon^{(t)}}{2} \end{aligned}\)

也就是说，有\(\dfrac{\epsilon^{(t+1)}}{\epsilon^{(t)}}=\dfrac{1}{2}\)。同时可以知道，\(\epsilon^{(0)}=0.5\)。因此有\(\epsilon^{(t)}=\dfrac{1}{2^{t+1}}\)。

也就是说，为了达到一个精度\(\delta\)，那么有\(\epsilon^{(t)}<\delta\)，可以解得\(t>-1-\lg\delta\)。也就是说，只有迭代轮数达到了\(-1-\lg\delta\)，这个精度才能达到。

因此，当精度要求足够高时，使用牛顿迭代法求解方程的根的迭代轮数远远低于使用梯度下降法求最小值。

33-3

令\(S=\{0,1,2,3\},k=2\)。如果\(S^{(1)}=\{0\},S^{(2)}=\{1,2,3\}\)，那么实际上迭代一次后，这个聚类结果仍然不变（因为重心的位置一直没有产生变化），此时\(c^{(1)}=0,c^{(2)}=2\)，计算出\(f(S,C)=2\)，程序终止。

实际上，\(S'^{(1)}=\{0,1\},S'^{(2)}=\{2,3\}\)才是最优的聚类结果，此时\(c'^{(1)}=0.5,c'^{(2)}=2.5\)，那么有\(f(S,C')=1\)。

33-4

整个算法的伪代码由程序STOCHASTIC-GRADIENT-DESCENT给出（这里给出的是更一般的情况，也就是这个向量有\(n\)维）。

NABLA-W'(W, x, y, n)
  let D[0 : n] be new array
  e = 0
  for j = 1 to n
    e = e + W[j] * x[j]
  e = e + W[0] - y
  D[0] = 2 * e
  for j = 1 to n
    D[j] = 2 * e * x[j]
  return D

STOCHASTIC-GRADIENT-DESCENT(w(0), X, Y, γ, n, T)
  sum = 0
  S = {1, 2, 3, ..., T}
  for i = 0 to T - 1
    sum = sum + w(i)
    j = RANDOM(1, T)
    w(i+1) = w(i) - γ ⋅ NABLA-W'(w(i), X[j], Y[j], n)
  w-avg = sum / T
  return w-avg 

由于是对每个点随机选择一个来进行梯度下降，考虑第一步过后梯度的期望步长\(E[(\Delta e)(\mathbf{w^{(i)}})]\)。

先考虑计算\(E\left[\dfrac{\partial e}{\partial w^{(i)}_0}\right]\)的值，有：

\(\begin{aligned} E\left[\dfrac{\partial e}{\partial w^{(i)}_0}\right]&=\dfrac{1}{T}\sum_{i=1}^T\dfrac{\partial e^{(i)}}{\partial w^{(i)}_0}\\ &=\dfrac{2}{T}\sum_{i=1}^T e^{(i)} \end{aligned}\)

接下来考虑计算\(E\left[\dfrac{\partial e}{\partial w^{(i)}_k}\right]\)的值，其中\(k\in[1,n]\)，有：

\(\begin{aligned} E\left[\dfrac{\partial e}{\partial w^{(i)}_k}\right]&=\dfrac{1}{T}\sum_{i=1}^T\dfrac{\partial e^{(i)}}{\partial w^{(i)}_k}\\ &=\dfrac{2}{T}\sum_{i=1}^T x_k^{(i)}\cdot e^{(i)} \end{aligned}\)

可以发现，梯度的期望\(E[(\Delta e)(\mathbf{w^{(i)}})]\)和题目33.3-5计算出来的\(\dfrac{\partial g}{\partial\mathbf{w}}\)是一致的，其中\(\displaystyle{g(\mathbf{w})=\dfrac{1}{T}\sum_{i=1}^T (e^{(i)})^2}\)。因此我们可以认为，权重向量\(\mathbf{w^{(i+1)}}\)的期望是和普通梯度下降算法是一样的，并且“走出”了这一小步。

因此最终分析方式和定理33.8的一致，其误差值\(\delta\)可以视为是值\(\dfrac{LR}{\sqrt{T}}\)。