Como a descida estocástica do gradiente poderia economizar tempo em comparação com a descida padrão do gradiente?

A Descida de gradiente padrão calcularia o gradiente para todo o conjunto de dados de treinamento.

for i in range(nb_epochs):
  params_grad = evaluate_gradient(loss_function, data, params)
  params = params - learning_rate * params_grad

Para um número predefinido de épocas, primeiro calculamos o vetor de gradiente weights_grad da função de perda para todo o conjunto de dados, usando nossos parâmetros de vetor de parâmetros.

A descida estocástica do gradiente, por outro lado, executa uma atualização de parâmetro para cada exemplo de treinamento x (i) e o rótulo y (i).

for i in range(nb_epochs):
  np.random.shuffle(data)
  for example in data:
    params_grad = evaluate_gradient(loss_function, example, params)
    params = params - learning_rate * params_grad

Diz-se que o SGD é muito mais rápido. No entanto, não entendo como pode ser muito mais rápido se ainda tivermos um loop sobre todos os pontos de dados. O cálculo do gradiente em GD é muito mais lento que o cálculo de GD para cada ponto de dados separadamente?

O código vem daqui .

Resposta curta:

• Em muitas configurações de big data (digamos vários milhões de pontos de dados), o cálculo do custo ou do gradiente leva muito tempo, porque precisamos somar todos os pontos de dados.
• Nós não precisa ter inclinação exata para reduzir o custo de uma determinada iteração. Alguma aproximação do gradiente funcionaria bem.
• O gradiente estocástico decente (SGD) aproxima o gradiente usando apenas um ponto de dados. Portanto, avaliar o gradiente economiza muito tempo em comparação com a soma de todos os dados.
• Com um número "razoável" de iterações (esse número pode ser alguns milhares e muito menor que o número de pontos de dados, que podem ser milhões), o gradiente estocástico decente pode obter uma boa solução razoável.

Resposta longa:

Minha anotação segue o curso Coursera de aprendizado de máquina de Andrew NG. Se você não estiver familiarizado com isso, pode rever a série de palestras aqui .

Vamos assumir a regressão na perda ao quadrado, a função de custo é

e o gradiente é

para gradiente decente (GD), atualizamos o parâmetro por

$1/m$$x^{(i)},y^{(i)}$

Eis por que estamos economizando tempo:

Suponha que tenhamos 1 bilhão de pontos de dados.

• No GD, para atualizar os parâmetros uma vez, precisamos ter o gradiente (exato). Isso requer a soma desses 1 bilhão de pontos de dados para executar 1 atualização.

• No SGD, podemos pensar nisso como tentar obter um gradiente aproximado em vez do gradiente exato . A aproximação é proveniente de um ponto de dados (ou vários pontos de dados chamados mini lote). Portanto, no SGD, podemos atualizar os parâmetros muito rapidamente. Além disso, se "repetirmos" todos os dados (chamados de uma época), na verdade teremos 1 bilhão de atualizações.

O truque é que, no SGD, você não precisa ter 1 bilhão de iterações / atualizações, mas muito menos iterações / atualizações, digamos 1 milhão, e você terá um modelo "bom o suficiente" para usar.

Estou escrevendo um código para demonstrar a ideia. Primeiro resolvemos o sistema linear pela equação normal, depois resolvemos com SGD. Em seguida, comparamos os resultados em termos de valores de parâmetros e valores da função objetivo final. Para visualizá-lo mais tarde, teremos 2 parâmetros para ajustar.

set.seed(0);n_data=1e3;n_feature=2;
A=matrix(runif(n_data*n_feature),ncol=n_feature)
b=runif(n_data)
res1=solve(t(A) %*% A, t(A) %*% b)

sq_loss<-function(A,b,x){
  e=A %*% x -b
  v=crossprod(e)
  return(v[1])
}

sq_loss_gr_approx<-function(A,b,x){
  # note, in GD, we need to sum over all data
  # here i is just one random index sample
  i=sample(1:n_data, 1)
  gr=2*(crossprod(A[i,],x)-b[i])*A[i,]
  return(gr)
}

x=runif(n_feature)
alpha=0.01
N_iter=300
loss=rep(0,N_iter)

for (i in 1:N_iter){
  x=x-alpha*sq_loss_gr_approx(A,b,x)
  loss[i]=sq_loss(A,b,x)
}

Os resultados:

as.vector(res1)
[1] 0.4368427 0.3991028
x
[1] 0.3580121 0.4782659

Observe que, embora os parâmetros não estejam muito próximos, os valores de perda são $124.1343$ e $123.0355$ que estão muito perto.

Aqui estão os valores da função de custo nas iterações, podemos ver que ela pode efetivamente diminuir a perda, o que ilustra a idéia: podemos usar um subconjunto de dados para aproximar o gradiente e obter resultados "bons o suficiente".

Agora vamos verificar os esforços computacionais entre duas abordagens. No experimento, temos$1000$os pontos de dados, usando SD, avaliam o gradiente uma vez que precisa somar os dados. MAS, no SGD, a sq_loss_gr_approxfunção resume apenas 1 ponto de dados e, em geral, o algoritmo converge menos que$300$ iterações (observe, não $1000$ iterações.) Essa é a economia computacional.