Pythonで素朴なグラデーションディセントを実装する

Question

私は非常に素朴な勾配descentをPythonで実装しようとしています。しかし、それは無限ループになるようです。私はそれをデバッグするのを助けてくれますか？

y = lambda x : x**2 
dy_dx = lambda x : 2*x 
def gradient_descent(function,derivative,initial_guess): 
    optimum = initial_guess 
    while derivative(optimum) != 0: 
     optimum = optimum - derivative(optimum) 
    else: 
     return optimum 
gradient_descent(y,dy_dx,5) 

編集：

今、私はこのコードを持って、私は本当に出力を理解することはできません。 P.S. CPUがフリーズすることがあります。

y = lambda x : x**2 
dy_dx = lambda x : 2*x 
def gradient_descent(function,derivative,initial_guess): 
    optimum = initial_guess 
    while abs(derivative(optimum)) > 0.01: 
     optimum = optimum - 2*derivative(optimum) 
     print((optimum,derivative(optimum))) 
    else: 
     return optimum 
gradient_descent(y,dy_dx,5) 

今私は回帰問題に適用しようとしている、しかし、出力は以下の出力のように正しく表示されません。

固定

Output of gradient descent code below

import matplotlib.pyplot as plt 
def stepGradient(x,y, step): 
    b_current = 0 
    m_current = 0 
    b_gradient = 0 
    m_gradient = 0 
    N = int(len(x)) 
    for i in range(0, N): 
     b_gradient += -(1/N) * (y[i] - ((m_current*x[i]) + b_current)) 
     m_gradient += -(1/N) * x[i] * (y[i] - ((m_current * x[i]) + b_current)) 
    while abs(b_gradient) > 0.01 and abs(m_gradient) > 0.01: 
     b_current = b_current - (step * b_gradient) 
     m_current = m_current - (step * m_gradient) 
     for i in range(0, N): 
      b_gradient += -(1/N) * (y[i] - ((m_current*x[i]) + b_current)) 
      m_gradient += -(1/N) * x[i] * (y[i] - ((m_current * x[i]) + b_current)) 
    return [b_current, m_current] 

x = [1,2, 2,3,4,5,7,8] 
y = [1.5,3,1,3,2,5,6,7] 
step = 0.00001 
(b,m) = stepGradient(x,y,step) 


plt.scatter(x,y) 
abline_values = [m * i + b for i in x] 
plt.plot(x, abline_values, 'b') 
plt.show() 

：D

import matplotlib.pyplot as plt 
def stepGradient(x,y): 
    step = 0.001 
    b_current = 0 
    m_current = 0 
    b_gradient = 0 
    m_gradient = 0 
    N = int(len(x)) 
    for i in range(0, N): 
     b_gradient += -(1/N) * (y[i] - ((m_current*x[i]) + b_current)) 
     m_gradient += -(1/N) * x[i] * (y[i] - ((m_current * x[i]) + b_current)) 
    while abs(b_gradient) > 0.01 or abs(m_gradient) > 0.01: 
     b_current = b_current - (step * b_gradient) 
     m_current = m_current - (step * m_gradient) 
     b_gradient= 0 
     m_gradient = 0 
     for i in range(0, N): 
      b_gradient += -(1/N) * (y[i] - ((m_current*x[i]) + b_current)) 
      m_gradient += -(1/N) * x[i] * (y[i] - ((m_current * x[i]) + b_current)) 
    return [b_current, m_current] 

x = [1,2, 2,3,4,5,7,8,10] 
y = [1.5,3,1,3,2,5,6,7,20] 
(b,m) = stepGradient(x,y) 


plt.scatter(x,y) 
abline_values = [m * i + b for i in x] 
plt.plot(x, abline_values, 'b') 
plt.show() 

Answer 1

whileあなたのループは、calcul ated浮動小数点値はゼロに等しい。これは、浮動小数点値がまれに正確に計算されることが少ないため、単純です。代わりに、計算された値がで十分に近い場合は、ループを停止してをゼロにします。

while math.abs(derivative(optimum)) > eps: 

ここで、epsは、計算された値の望ましい精度です。これはおそらくデフォルト値1e-10またはそのようなものを用いて、別のパラメータにすることができます。

---

しかし、あなたの場合の問題は悪化しています。あなたのアルゴリズムは計算

optimum = optimum - 2*derivative(optimum) 

が実際の最適値に近いoptimumの値を移動すると仮定ではあまりにもナイーブです。あなたの特別なケースでは、変数optimumは、5（最初の推定値）と-5の間で前後に循環します。 5の誘導体は10であり、-5の誘導体は-10であることに留意されたい。

このようなサイクリングを避ける必要があります。デルタ2*derivative(optimum)に1より小さい何かを掛けることができます。具体的には、y=x**2で動作します。しかし、これは一般的には機能しません。

完全に安全であるためには、より小さい値と大きな値で最適点を「ブラケット」し、次の推測を見つけるために導関数を使用します。しかし、あなたの次の推測が括弧で囲まれた間隔の外に出ないようにしてください。そうした場合、または推測の収束が遅すぎる場合は、二分法や黄金平均法などの別の方法を使用してください。

もちろん、これは、あなたの「非常に純粋な勾配降下」アルゴリズムは、一般的に動作するにはあまりにも純粋ではないことを意味します。そのため、実際の最適化ルーチンはより複雑です。

Answer 2

はまた、（勾配降下式にガンマ）あなたのステップサイズを小さくする必要があります。

y = lambda x : x**2 
dy_dx = lambda x : 2*x 
def gradient_descent(function,derivative,initial_guess): 
    optimum = initial_guess 
    while abs(derivative(optimum)) > 0.01: 
     optimum = optimum - 0.01*derivative(optimum) 
     print((optimum,derivative(optimum))) 
    else: 
     return optimum