Критерий конвергенции стохастических градиентов

Question

В настоящее время мои критерии конвергенции для SGD проверяют, является ли отношение ошибки MSE к определенной границе.

def compute_mse(data, labels, weights): 
    m = len(labels) 
    hypothesis = np.dot(data,weights) 
    sq_errors = (hypothesis - labels) ** 2 
    mse = np.sum(sq_errors)/(2.0*m) 
    return mse 

cur_mse = 1.0 
prev_mse = 100.0 
m = len(labels) 
while cur_mse/prev_mse < 0.99999: 
    prev_mse = cur_mse 

    for i in range(m): 
     d = np.array(data[i]) 
     hypothesis = np.dot(d, weights) 
     gradient = np.dot((labels[i] - hypothesis), d)/m 
     weights = weights + (alpha * gradient) 

    cur_mse = compute_mse(data, labels, weights) 
    if cur_mse > prev_mse: 
     return 

Веса обновляются w.r.t. к одной точке данных в учебном наборе.

С альфой 0,001, предполагается, что модель сходится в течение нескольких итераций, но я не получаю конвергенции. Являются ли эти критерии конвергенции слишком строгими?

Answer 1

Я постараюсь ответить на вопрос. Во-первых, псевдокод стохастического градиентного спуска выглядит примерно так:

input: f(x), alpha, initial x (guess or random) 
output: min_x f(x) # x that minimizes f(x) 

while True: 
    shuffle data # good practice, not completely needed 
    for d in data: 
     x -= alpha * grad(f(x)) # df/dx 
    if <stopping criterion>: 
     break 

Там могут быть и другие regularization параметры, добавленные к функции, которую вы хотите, чтобы свести к минимуму, например, l1 penalty, чтобы избежать переобучения.

Возвращаясь к вашей проблеме, глядя на ваши данные и определении градиента, выглядит, как вы хотите, чтобы решить простую линейную систему уравнений вида:

Ax = b 

который дает objevtive функции:

f(x) = ||Ax - b||^2 

стохастические градиентный спуск использует один строки данных в то время:

||A_i x - b|| 

, где || o || является евклидовой нормой, а _i означает индекс строки.

Здесь A это ваш data, x ваш weights и b ваш labels.

Градиент функции затем вычисляется как:

grad(f(x)) = 2 * A.T (Ax - b) 

Или в случае стохастического градиентного спуска:

2 * A_i.T (A_i x - b) 

.T, где средство транспонирование.

Собираем все обратно в свой код ... сначала я настроить синтетическую данные:

A = np.random.randn(100, 2) # 100x2 data 
x = np.random.randn(2, 1) # 2x1 weights 
b = np.random.randint(0, 2, 100).reshape(100, 1) # 100x1 labels 
b[b == 0] = -1 # labels in {-1, 1} 

Затем определяют параметры:

alpha = 0.001 
cur_mse = 100. 
prev_mse = np.inf 
it = 0 
max_iter = 100 
m = A.shape[0] 
idx = range(m) 

и петля!

while cur_mse/prev_mse < 0.99999 and it < max_iter: 
    prev_mse = cur_mse 
    shuffle(idx) 

    for i in idx: 
     d = A[i:i+1] 
     y = b[i:i+1] 
     h = np.dot(d, x) 
     dx = 2 * np.dot(d.T, (h - y)) 
     x -= (alpha * dx) 

    cur_mse = np.mean((A.dot(x) - b)**2) 
    if cur_mse > prev_mse: 
     raise Exception("Not converging") 
    it += 1 

Этот код почти так же, как ваша, с несколькими дополнениями:

• Другой критерий остановки на основе количества итераций (чтобы избежать зацикливания, если система не будет сходится или делает слишком медленно)

• Переопределение градиента dx (все еще похоже на ваше). У вас есть знак инвертированный, и поэтому обновление веса положительно +, так как в моем примере отрицательный - (имеет смысл, так как вы спускаетесь в градиенте).

• Индексирование data и labels. В то время как data[i] дает кортеж размера (2,) (в данном случае для данных 100x2), используя причудливую индексацию data[i:i+1] вернет представление данных без его изменения (например, с формой (1, 2)) и, следовательно, позволит вам выполнить правильные умножения матриц.

Вы можете добавить критерий 3-й остановки, основываясь на приемлемом mse ошибки, то есть: if cur_mse < 1e-3: break.

Этот алгоритм со случайными данными сходится в 20-40 итерациях для меня (в зависимости от генерируемых случайных данных).

Итак, если вы считаете, что это функция, которую вы хотите свести к минимуму, если этот метод не работает для вас, это может означать, что ваша система недоопределена (у вас меньше учебных данных, чем у функций, что означает, что A более широкий, чем высокий).

Надеюсь, это поможет!