需要長時間來完成梯度下降算法 - 效率 - Python的

Question

我想實現使用python梯度下降算法和下面是我的代碼，

def grad_des(xvalues, yvalues, R=0.01, epsilon = 0.0001, MaxIterations=1000): 
    xvalues= np.array(xvalues) 
    yvalues = np.array(yvalues) 
    length = len(xvalues) 
    alpha = 1 
    beta = 1 
    converged = False 
    i=0 
    cost = sum([(alpha + beta*xvalues[i] - yvalues[i])**2 for i in range(length)])/(2 * length) 
    start_time = time.time() 
    while not converged:  
     alpha_deriv = sum([(alpha + beta*xvalues[i] - yvalues[i]) for i in range(length)])/(length) 
     beta_deriv = sum([(alpha + beta*xvalues[i] - yvalues[i])*xvalues[i] for i in range(length)])/(length) 
     alpha = alpha - R * alpha_deriv 
     beta = beta - R * beta_deriv 
     new_cost = sum([ (alpha + beta*xvalues[i] - yvalues[i])**2 for i in range(length)])/(2*length) 
     if abs(cost - new_cost) <= epsilon: 
      print 'Converged' 
      print 'Number of Iterations:', i 
      converged = True 
     cost = new_cost 
     i = i + 1  
     if i == MaxIterations: 
      print 'Maximum Iterations Exceeded' 
      converged = True 
    print "Time taken: " + str(round(time.time() - start_time,2)) + " seconds" 
    return alpha, beta 

此代碼工作正常。但問題是，約600次迭代需要超過25秒。我覺得這樣做效率不夠高，我在做計算之前嘗試將它轉換爲數組。這確實將時間從300秒縮短到了25秒。我仍然覺得它可以減少。任何人都可以幫助我改進這個算法嗎？

感謝

Answer 1

我能看到的最低懸掛水果是矢量化的。你有很多列表理解;它們比循環更快，但沒有正確使用numpy數組。

def grad_des_vec(xvalues, yvalues, R=0.01, epsilon=0.0001, MaxIterations=1000): 
    xvalues = np.array(xvalues) 
    yvalues = np.array(yvalues) 
    length = len(xvalues) 
    alpha = 1 
    beta = 1 
    converged = False 
    i = 0 
    cost = np.sum((alpha + beta * xvalues - yvalues)**2)/(2 * length) 
    start_time = time.time() 
    while not converged: 
     alpha_deriv = np.sum(alpha + beta * xvalues - yvalues)/length 
     beta_deriv = np.sum(
      (alpha + beta * xvalues - yvalues) * xvalues)/length 
     alpha = alpha - R * alpha_deriv 
     beta = beta - R * beta_deriv 
     new_cost = np.sum((alpha + beta * xvalues - yvalues)**2)/(2 * length) 
     if abs(cost - new_cost) <= epsilon: 
      print('Converged') 
      print('Number of Iterations:', i) 
      converged = True 
     cost = new_cost 
     i = i + 1 
     if i == MaxIterations: 
      print('Maximum Iterations Exceeded') 
      converged = True 
    print("Time taken: " + str(round(time.time() - start_time, 2)) + " seconds") 
    return alpha, beta 

爲了比較

In[47]: grad_des(xval, yval) 
Converged 
Number of Iterations: 198 
Time taken: 0.66 seconds 
Out[47]: 
(0.28264882215511067, 0.53289263416071131) 

In [48]: grad_des_vec(xval, yval) 
Converged 
Number of Iterations: 198 
Time taken: 0.03 seconds 
Out[48]: 
(0.28264882215511078, 0.5328926341607112) 

這是關於一個因子20加速（XVAL和yval均爲1024個元件陣列）。

Answer 2

正如我評論，我不能重現緩慢，但這裏有一些潛在的問題：

1. 它看起來像length不會改變，但你反覆調用range(length)。使用xrange（或從six或future導入一個與Py3兼容的迭代器range），並在Python 2.x中創建一個列表，並重復執行此操作可能會減慢速度（創建對象並不便宜）。而不是每次。

2. i正在這裏以可能導致問題的方式重複使用。您試圖將其用作整體迭代計數，但是每個使用i的列表解析將在該函數的範圍內覆蓋i，這意味着「迭代」計數總是以length - 1結尾。