Python에서 순진한 그라디언트 디센트 구현하기

Question

파이썬에서 매우 순진한 그라디언트 디센트를 구현하려고합니다. 그러나 무한 루프가되는 것처럼 보입니다. 디버깅을 도와 주시겠습니까?

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) 

편집 :

지금이 코드를 가지고, 난 정말 출력을 이해할 수 없다. 추신. CPU가 정지 될 수 있습니다.

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() 

고정 :

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) 

는 지금은 아래 출력과 같이 그러나 출력이 올바른 것으로 표시되지 않습니다, 회귀 문제에 적용하기 위해 노력하고있어 : 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 계산은 ated 부동 소수점 값은 0입니다. 부동 소수점 값은 거의 계산되지 않으므로 순진합니다. 계산 된 값이 일 때이 0에 가까울 때 루프를 중지하십시오. eps는 계산 된 값의 원하는 정밀도

while math.abs(derivative(optimum)) > 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