градиентный алгоритм спуска с много времени, чтобы закончить - Эффективность - Python

Question

Я пытаюсь реализовать алгоритм градиентного спуска с помощью питона и после мой код,

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 

Этот код работает отлично. Но проблема в том, что она занимает более 25 секунд примерно для 600 итераций. Я считаю, что это недостаточно эффективно, и я попытался преобразовать его в массив перед выполнением вычислений. Это сократило время от 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). В Python 2.x, range создает список, и повторное выполнение этого может замедлить работу (создание объекта не из дешевых.) Используйте xrange (или импортируйте Py3-совместимый итератор range от six или future) и создайте диапазон, а не каждый раз.

2. i повторно используется здесь, что может вызвать проблемы. Вы пытаетесь использовать его как общий счетчик итераций, но каждое из ваших понятий списка, которое использует i, перезапишет i в рамках функции, что означает, что счетчик «итераций» всегда будет равен length - 1.