Por que usar descida de gradiente para regressão linear, quando uma solução matemática em formato fechado está disponível?

74

Estou participando dos cursos de aprendizado de máquina on-line e aprendi sobre a descida do gradiente para calcular os valores ideais da hipótese.

h(x) = B0 + B1X

por que precisamos usar a descida do gradiente se podemos encontrar facilmente os valores com a fórmula abaixo? Isso parece direto e fácil também. mas o GD precisa de várias iterações para obter o valor.

B1 = Correlation * (Std. Dev. of y/ Std. Dev. of x)

B0 = Mean(Y) – B1 * Mean(X)

NOTA: Tomada como em https://www.dezyre.com/data-science-in-r-programming-tutorial/linear-regression-tutorial

Eu verifiquei as perguntas abaixo e, para mim, não estava claro para entender.

Por que a descida do gradiente é necessária?

Por que a otimização é resolvida com descida gradiente e não com uma solução analítica?

As respostas acima comparam GD x usando derivadas.

Purus
fonte
5
Você não precisa de descida de gradiente para estimar os coeficientes de regressão linear.
Reintegrar Monica
8
@ Sycorax "don't need" é uma afirmação forte. O método iterativo pode ser útil para grandes dados. Digamos que a matriz de dados seja muito grande e não caiba na memória.
Haitao Du
8
@ hxd1011 Obrigado por esclarecer esta dimensão prática do problema. Eu estava pensando em termos puramente matemáticos.
Reintegrar Monica

Respostas:

90

A principal razão pela qual a descida do gradiente é usada para regressão linear é a complexidade computacional: é computacionalmente mais barato (mais rápido) encontrar a solução usando a descida do gradiente em alguns casos.

A fórmula que você escreveu parece muito simples, mesmo computacionalmente, porque funciona apenas para casos univariados, ou seja, quando você possui apenas uma variável. No caso multivariado, quando você tem muitas variáveis, as fórmulas são um pouco mais complicadas no papel e exigem muito mais cálculos quando implementadas em software: Aqui, você precisa calcular o matriz X X

β=(XX)1XY
XXinverta-o (veja a nota abaixo). É um cálculo caro. Para sua referência, a matriz (de design) X possui K + 1 colunas em que K é o número de preditores e N linhas de observações. Em um algoritmo de aprendizado de máquina, você pode acabar com K> 1000 e N> 1.000.000. O própria matriz demora um pouco para calcular, então você tem que inverter K × K matriz - este é caro.XXK×K

Portanto, a descida do gradiente permite economizar muito tempo nos cálculos. Além disso, a maneira como isso é feito permite uma paralelização trivial, ou seja, distribuir os cálculos entre vários processadores ou máquinas. A solução de álgebra linear também pode ser paralelizada, mas é mais complicada e ainda cara.

Além disso, há versões de descida gradiente quando você mantém apenas um pedaço de seus dados na memória, diminuindo os requisitos de memória do computador. No geral, para problemas extra grandes, é mais eficiente que a solução de álgebra linear.

Isso se torna ainda mais importante à medida que a dimensionalidade aumenta, quando você tem milhares de variáveis, como no aprendizado de máquina.

Observação . Fiquei surpreso com quanta atenção é dada à descida gradiente nas palestras de Ng. Ele passa um tempo não trivial falando sobre isso, talvez 20% de todo o curso. Para mim, é apenas um detalhe de implementação, é exatamente como você encontra o melhor. A chave está na formulação do problema de otimização e como exatamente você o acha não essencial. Eu não me preocuparia muito com isso. Deixe isso para as pessoas da ciência da computação e concentre-se no que é importante para você como estatístico.

Dito isto, devo me qualificar dizendo que é realmente importante entender a complexidade computacional e a estabilidade numérica dos algoritmos da solução. Ainda acho que você não deve conhecer os detalhes da implementação e o código dos algoritmos. Geralmente, não é o melhor uso do seu tempo como estatístico.

Nota 1 . Escrevi que você tem que inverter a matriz para fins didáticos e não é como costuma resolver a equação. Na prática, os problemas de álgebra linear são resolvidos usando algum tipo de fatoração, como QR, onde você não inverte diretamente a matriz, mas faz outras manipulações matematicamente equivalentes para obter uma resposta. Você faz isso porque a inversão de matriz é uma operação cara e numericamente instável em muitos casos.

Isso traz outra pequena vantagem do algoritmo de descida de gradiente como efeito colateral: funciona mesmo quando a matriz de design apresenta problemas de colinearidade. O caminho usual da álgebra linear explodiria e a descida do gradiente continuará, mesmo para os preditores colineares.

Aksakal
fonte
17
Mas Ng é uma pessoa de ciência da computação.
Ameba diz Reinstate Monica
21
Em relação à sua observação: como matemático, eu costumava concordar. Mas agora entendo que, no aprendizado de máquina moderno, o método de otimização está inerentemente vinculado ao objetivo que está sendo otimizado. Algumas formas de regularização, como o abandono, são mais claramente expressas em termos do algoritmo, em vez do objetivo. Em resumo: se você usar uma rede profunda, mantenha a função objetivo, mas altere o método de otimização, poderá obter um desempenho muito diferente. Na verdade, por vezes, um otimizador de melhor rende resultados piores na prática ...
A. Rex
14
XXXXβ=Xyβ
3
A solução @AnderBiguri com fatoração QR, por outro lado, é estável ao contrário, portanto, fornece uma solução o mais precisa possível, dada a incerteza nos dados de entrada.
Federico Poloni
7
β=(XtX)1XtyXtXβ=Xty
21

Primeiro, eu recomendo fortemente que você leia as duas postagens a seguir (se não estiver duplicada)

Verifique a resposta de JM em

Qual algoritmo é usado na regressão linear?

Verifique a resposta de Mark (do ponto de vista da estabilidade numérica) em

Precisamos de descida gradiente para encontrar os coeficientes de um modelo de regressão linear?


minimize Axb2
2AT(Axb)0
ATAx=ATb

Em alto nível, existem duas maneiras de resolver um sistema linear. Método direto e o método iterativo. Observe que o método direto está resolvendo , e a descida do gradiente (um método iterativo de exemplo) está resolvendo diretamente .ATAx=ATbminimize Axb2

Comparando com métodos diretos (Say Decomposition QR / LU ). Os métodos iterativos têm algumas vantagens quando temos uma grande quantidade de dados ou os dados são muito escassos.

Por outro lado, acredito que uma das razões pelas quais Andrew Ng enfatiza isso é o fato de ser um método genérico (método mais usado no aprendizado de máquina) e pode ser usado em outros modelos, como regressão logística ou rede neural.

Haitao Du
fonte
Você está absolutamente certo. O SGD é muito útil ao lidar com uma grande quantidade de dados. O método demonstrado pelo Prof Ng é o mais clássico e puro. Deve-se começar a partir desse ponto para ter uma ideia clara. Se alguém puder entender o lema disso, toda estimativa linear será cristalina para ele / ela.
Sandipan Karmakar
11
O tamanho da maxtrix de dados não é realmente um problema, usando o relacionamento ; você pode calcular e uma observação de cada vez. É assim que foi feito no SAS nos dias em que a memória do computador era muito mais limitada do que hoje. É o número de colunas em que é o fator limitante. X t X X T y XXTX=xixiTXTXXTyX
jbowman 24/08
6

O Sycorax está certo de que você não precisa de descida de gradiente ao estimar a regressão linear. Seu curso pode estar usando um exemplo simples para ensinar a descida do gradiente a preceder versões mais complicadas.

Uma coisa interessante que eu quero acrescentar, porém, é que não há atualmente um pequeno nicho de pesquisa envolvendo terminando gradiente descendente cedo para evitar overfitting de um modelo.

Tim Atreides
fonte
2
Para declaração de sobreajuste, você poderia fornecer o link? adicionar o termo de regularização é melhor do que limitar o número de iterações?
Haitao Du
Você pode ver o Capítulo 7 do Deep Learning, de Goodfellow et al., Que menciona a parada precoce para evitar o ajuste excessivo nas redes neurais.
Batman
2
A regularização por parada antecipada não é de modo algum uma nova técnica; é uma técnica bem conhecida, por exemplo, na iteração Landweber: en.wikipedia.org/wiki/Landweber_iteration
cfh
3

(XTX)1XTy

O método que você mencionou, ou seja, usando correlação, é aplicável apenas a um preditor e a uma quantidade de interceptação. Apenas observe o formulário. Então, quando o número de preditores é mais do que um em número, qual é a saída? Então é preciso recorrer aos outros métodos, ou seja, a equação ou otimização normal.

O(N3)NXX

Minha sugestão para você é não apenas resolver um problema. Tente entender a teoria. O Prof Ng é um dos melhores professores deste mundo que gentilmente ensina Machine Learning no MOOC. Portanto, quando ele está instruindo dessa maneira, deve ter algumas intenções latentes. Espero que você não se importe com minhas palavras.

Muito bem sucedida.

Sandipan Karmakar
fonte
5
"Inverter uma matriz" é fortemente NÃO recomendado. O QR é mais numericamente estável para resolver um sistema linear.
Haitao Du
11
Eu concordo com o argumento computacional. No entanto, o excesso ou a falta de ajuste não tem nada a ver com o uso de GD versus a equação Normal, mas com a complexidade do modelo (regressão). Ambos os métodos (GD, se funcionar corretamente) encontram a mesma solução de mínimos quadrados (se existir) e, portanto, ajustam ou superestimam os dados na mesma quantidade.
Ruben van Bergen
2

Primeiro, sim, a verdadeira razão é a de Tim Atreides; este é um exercício pedagógico.

No entanto, é possível, embora improvável, que alguém queira fazer uma regressão linear em, digamos, vários trilhões de pontos de dados sendo transmitidos a partir de um soquete de rede. Nesse caso, a avaliação ingênua da solução analítica seria inviável, enquanto algumas variantes de descida estocástica / gradiente adaptável convergiriam para a solução correta com o mínimo de sobrecarga de memória.

(para regressão linear, pode-se reformular a solução analítica como um sistema de recorrência, mas essa não é uma técnica geral.)

Timothy Teräväinen
fonte
2

Uma outra razão é que a descida do gradiente é um método mais geral. Para muitos problemas de aprendizado de máquina, a função de custo não é convexa (por exemplo, fatoração de matriz, redes neurais), portanto você não pode usar uma solução de formulário fechado. Nesses casos, a descida em gradiente é usada para encontrar bons pontos ótimos locais. Ou, se você deseja implementar uma versão online, é necessário usar um algoritmo baseado em descida gradiente.

Sanyo Mn
fonte