The Robbins-Monro (RM) algorithm求解 g(w) = w^3 − 5的代码

[moneypi]

关于书中114页求解g(w) = 0，我没有搞懂如何计算，我认为是如下

$$w_1 = 0$$ $$g(w) = w^3 - 5=-5$$ $$w_k+1 = w_k - a_k g(w)$$ $$w_2 = w_1 - a_1 g(w)$$ $$a_1 = 1/1$$ $$w_2 = 0 - 1*(-5) = 5$$

很显然该结果跟书中的曲线不匹配，所以，不知道实际图中的值是如何计算出来的？
5^1/3 ≈ 1.71

[MathFoundationRL]

有考虑噪音吗？

[moneypi]

很荣幸得到老师的答复，我没有加噪音是不确定自己的理解是否正确，在试着不用噪音的时候用python实现，代码如下：

# f(x) = x^3 - 5
def f(x):
    return x**3 - 5

# Robbins-Monro algorithm
def robbins_monro(f, x0, max_iter):
    x = x0
    for i in range(max_iter):
        x = x - 1 / (i+1) * f(x)
        print(x)

robbins_monro(f, 0, 10)

但打印结果反而发散了

(base) sdx@sdx:~/tmp/drl$ python rm.py 
5.0
-55.0
55405.0
-42519376333375.0
1.537413367652862e+40
-6.0564858695856035e+119
Traceback (most recent call last):
  File "/home/sdx/tmp/drl/rm.py", line 12, in <module>
    robbins_monro(f, 0, 10)
  File "/home/sdx/tmp/drl/rm.py", line 9, in robbins_monro
    x = x - 1 / (i+1) * f(x)
  File "/home/sdx/tmp/drl/rm.py", line 3, in f
    return x**3 - 5
OverflowError: (34, 'Numerical result out of range')

虽然我也可以加噪音，但感觉不是噪音导致的发散，我的理解是噪音对收敛并没有帮助，不知道理解的对不对

[moneypi]

请教一下，书中的曲线是如何计算出来的呢？有没有代码？

[MathFoundationRL]

是按照书中描述的计算的

[MathFoundationRL]

可以试试下面的matlab代码：

wk=0; % if the gradient is not bounded, the initial guess must be good!
iterNum=50;
wkAll=zeros(1,iterNum);
wkAll(1)=wk;
nosieAll=zeros(1,iterNum);
for k=2:iterNum
    ak=1/k;
    noise=randn
    Nk=(wk^3-5)+noise;
    wk1=wk-ak*Nk;
    %
    wk=wk1;
    wkAll(k)=wk;
    nosieAll(k)=noise;
end

[moneypi]

感谢，该代码确实是可以收敛，但我有点转牛角尖哈，因为书中是

$$a_k=1/k$$ $$w_1=0$$

所以我认为应该是

$$a_1=1/1$$

但我理解上面代码中

for k=2:iterNum
    ak=1/k;

$$a_1=1/2$$

所以我是纠结这个细节，不知道对不对，这也是上面的python代码不收敛的原因，勿怪，哈哈

[renjieDLUT]

RM算法的完全适用的条件其中之一是: g(w)的梯度是严格单调递增且有上界. $w^3-5$这个函数的梯度是没有上界的(无穷大)..所以不收敛..
如果函数的梯度不满足严格单调递增且有上界的条件,那么在初值选择的适当时,也能work.
RM算法中对 $\alpha_t$的选择条件是: $\sum_{k=1}^\infty \alpha_t =\infty$, $\sum_{k=1}^\infty \alpha_t^2 <\infty$.意味着 $\alpha_t$ 应该收敛到0,但是不要收敛太快...所以 $\alpha$的选择可以是 $1/k$也可以是 $1/(k+c),c为常数$