Por que a descida do gradiente é ineficiente para grandes conjuntos de dados?

12

Digamos que nosso conjunto de dados contenha 1 milhão de exemplos, ou seja, , e desejamos usar a descida do gradiente para realizar uma regressão logística ou linear nesse conjunto de dados.x1,,x106

O que é o método do gradiente descendente que o torna ineficiente?

Lembre-se de que a etapa de descida do gradiente no tempo é dada por:t

wt+1=wt+ηtf(x)

onde é a função de perda.f

Não estou vendo nada fora do comum com a etapa acima que faz com que o algoritmo seja ineficiente. É o cálculo de ? Esta operação não pôde ser pré-calculada, ou seja, cada ff(x) já calculado, e simplesmente avaliá-los em cada ponto de dadosxi?fxxEu?

Carlos - o Mangusto - Perigo
fonte
Ineficiente em relação a ...? Até os mínimos quadrados são ineficientes para um grande conjunto de dados. Você precisa da grande notação O para ter idéias significativas sobre o que o faz com o algoritmo. Nem todos os algoritmos GD têm o mesmo grande O. (não é?)n
Adamo

Respostas:

7

Ajudaria se você fornecesse um contexto para a alegação de que a descida do gradiente é ineficiente. Ineficiente em relação a quê?

Acho que o contexto que falta aqui é a comparação com a descida estocástica ou gradiente em lote no aprendizado de máquina. Veja como responder à pergunta neste contexto. Você está otimizando os parâmetros do modelo, mesmo hiperparâmetros. Portanto, você tem a função de custo , onde x i - seus dados e Θ - vetor de parâmetros e L ( ) - função de perda. Para minimizar esse custo, use a descida do gradiente sobre os parâmetros θ j : i=1nL(xi|Θ)xEuΘL() θj

θji=1nL(Θ|xi)

Então, você vê que precisa obter a soma de todos os dados . Isso é lamentável, porque significa que você continua repetindo os dados para cada etapa da descida do gradiente. É assim que surge a descida do lote e do gradiente estocástico: e se amostrássemos a partir do conjunto de dados e calculássemos o gradiente em uma amostra, não o conjunto completo? xi=1,,n Aqui,nsé o número de observações na amostras. Portanto, se sua amostra é 1/100 do conjunto total, você acelera seus cálculos em 100 vezes! Obviamente, isso introduz o ruído, o que prolonga o aprendizado, mas o ruído diminui na taxa de

θjk=1nsL(Θ|xk)
nss enquanto o valor do cálculo aumenta emn, então esse truque pode funcionar.nn

Como alternativa, insteado aguardando até a soma total ser calculada, você pode dividir isso em lotes e fazer uma etapa para cada lote M s = 1n s i s = 1 . Dessa forma, você teria executado M etapas no momento em que a soma de todo o conjunto de dados é calculada. Estes seriam passos mais ruidosos, mas o ruído é cancelado com o tempo.i=1ns=1Mis=1ns

Aksakal
fonte
19

Existem duas maneiras pelas quais a descida do gradiente pode ser ineficiente. Curiosamente, cada um deles leva a seu próprio método de conserto, que são soluções quase opostas. Os dois problemas são:

(1) Muitas atualizações de descida de gradiente são necessárias.

(2) Cada etapa de descida de gradiente é muito cara.

Em relação a (1), comparando a descida do gradiente com os métodos que levam em consideração as informações sobre as derivadas de segunda ordem, a descida do gradiente tende a ser altamente ineficiente em relação à melhoria da perda a cada iteração. Um método muito padrão, o Método de Newton , geralmente leva muito menos iterações para convergir, ou seja, para regressão logística, 10 iterações do Método de Newton geralmente terão perdas menores do que a solução fornecida por 5.000 iterações de descida de gradiente. Para regressão linear, isso é ainda mais extremo; existe uma solução de formulário fechado! No entanto, à medida que o número de preditores aumenta muito (por exemplo, mais de 500), o Método de Newton / solução direta para regressão linear pode se tornar muito caro por iteração devido à quantidade de operações de matriz necessárias, enquanto a descida do gradiente terá um custo consideravelmente menor por iteração.

O(nk)nkn=106k<100n=1012k=103será. Nesse caso, métodos que aproximam a derivada com base em subconjuntos menores de dados são mais atraentes, como a descida do gradiente estocástico .

Eu digo que essas correções são quase opostas, pois algo como o método de Newton é mais caro, mas mais eficiente (em termos de mudança na perda) por atualização, enquanto a descida estocástica do gradiente é realmente menos eficiente, mas muito mais computacionalmente mais barata por atualização.

Cliff AB
fonte
k
2
@Learningonepageatatime: covariates = variáveis ​​preditoras.
Cliff AB
10

L(w)f(x)Lwxwx

L(w)=(Lw1,,LwD),
D

wx

L(w)=i=1N(yiwTxi)2.
L(w)wNxN=106
tddevlin
fonte
3

Resposta curta: O cálculo do gradiente precisa somar todos os pontos de dados. Se tivermos uma grande quantidade de dados, leva muito tempo.

Eu tenho uma resposta detalhada aqui.

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


Por outro lado, sempre lembre-se de que existem métodos diretos, além dos métodos iterativos (gradiente decente). Se queremos resolver um problema do quadrado mínimo, o método direto pode ser super eficiente. Por exemplo, decomposição QR. Se não temos muitos recursos, é muito rápido.

Quando você o verifica, pode surpreendê-lo: 5 milhões de pontos de dados com 2 recursos, a resolução da regressão linear / mínimo quadrado leva alguns segundos!

x=matrix(runif(1e7),ncol=2)
y=runif(5e6)
start_time <- Sys.time()
lm(y~x)
end_time <- Sys.time()
end_time - start_time
# Time difference of 4.299081 secs
Haitao Du
fonte
1

Embora os dois exemplos que você mencionou sejam geralmente convexos, acrescentarei um ponto sobre problemas não convexos. Na minha opinião, existem duas razões principais pelas quais a descida do gradiente (em lote) pode ser considerada "ineficiente". O primeiro ponto sobre o esforço computacional de calcular o gradiente de uma soma "grande" de funções já foi muito claramente delineado nas outras respostas. Para problemas não convexos, no entanto, a GD tem o problema de geralmente ficar preso em um mínimo local "próximo". Esse mínimo pode ser muito ruim em comparação com o mínimo global. O SGD ou o mini-lote GD têm a "vantagem" de vagar (pelo menos parcialmente) aleatoriamente e, portanto, podem ter a chance de encontrar um mínimo local melhor. Veja esta resposta do CV aqui . Ou este outro post de currículo descrevendo como a aleatoriedade pode ser benéfica.

xel
fonte