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

31

Eu estava tentando aprender aprendizado de máquina usando o material Coursera . Nesta palestra, Andrew Ng usa o algoritmo de descida de gradiente para encontrar os coeficientes do modelo de regressão linear que minimizarão a função de erro (função de custo).

Para regressão linear, precisamos de descida de gradiente? Parece que eu posso diferenciar analiticamente a função de erro e defini-la como zero para resolver os coeficientes; isso esta certo?

regression machine-learning linear-model gradient-descent Vencedor
fonte
3
Os modelos lineares têm sido decentemente bem tratados desde os anos 1700. Existem várias maneiras de lidar com eles que não exigem descida de gradiente (GD). Existem modelos não lineares em que a maioria desses métodos cai de cara no chão. O Andrew está fazendo você usar um método desconhecido, mas muito útil, contra um problema muito simples, para que você possa depurar sua abordagem. Quando você é bom com o método, pode aplicá-lo aos problemas incrivelmente não-lineares para os quais o GD é o único método para obter resultados.
EngrStudent - Reintegrar Monica
10
Não, você não precisa usar abordagens como a descida do gradiente (esse não é o único método de otimização, em qualquer caso). Você pode realmente resolvê-lo analiticamente, como sugere; você diferencia em relação a cada parâmetro, para obter uma equação por parâmetro. Mas é útil resolver problemas simples que podem ser feitos de outras maneiras; se você já conhece a resposta, pode ter certeza de quando está recebendo a resposta certa com descida gradiente.
Glen_b -Reinstar Monica
Se a função de custo for a penalidade quadrática usual ('distância'), existe uma solução de formulário fechado. No entanto, a descida do gradiente geralmente é muito mais rápida, por isso é normalmente usada.
aginensky
Além disso, a descida do gradiente pode ser usada para encontrar soluções numéricas para problemas analiticamente intratáveis. Eu suspeitaria que ele usa descida gradiente desde o início para se acostumar. Eu acredito que ele usa descida gradiente com redes neurais. Escusado será dizer que a situação da rede neural é mais complicada. Penso que, a partir de uma situação pedagógica, tendo-os visto antes, com modelos lineares, a descida gradiente para uso com redes neurais parece mais razoável.
aginensky
3
Obrigado por postar o link para os vídeos de Andre Ng que eu assisti vários. Eu já sabia disso, embora não seja tão extremo, mas é assustador ver o que a grande maioria das pessoas que "aprendem" a otimização está aprendendo, sem mencionar o que pelo menos algumas delas estão aprendendo sobre computação estatística. Gene Golub, o pioneiro em computação e uso de SVD, estaria rolando no túmulo se soubesse o que está sendo ensinado agora em seu Departamento de Ciência da Computação de Stanford. O vídeo "mais engraçado" é youtube.com/watch?v=B3vseKmgi8E , que recomenda e compara os 2 piores algoritmos para mínimos quadrados
Mark L. Stone

Respostas:

43

Os mínimos quadrados lineares podem ser resolvidos por

0) Usando o solucionador de mínimos quadrados lineares de alta qualidade, com base em SVD ou QR, conforme descrito abaixo, para mínimos quadrados lineares sem restrições ou com base em uma versão de Programação Quadrática ou Otimização Cônica para mínimos quadrados limitados ou com restrição linear, conforme descrito abaixo. Esse solucionador é pré-enlatado, fortemente testado e pronto para uso - use-o.

1) SVD, que é o método mais confiável e numericamente preciso, mas também exige mais computação do que alternativas. No MATLAB, a solução SVD do problema de mínimos quadrados lineares sem restrições A * X = b é pinv (A) * b, que é muito precisa e confiável.

2) QR, que é razoavelmente confiável e numericamente preciso, mas não tanto quanto SVD, e é mais rápido que SVD. No MATLAB, a solução QR do problema de mínimos quadrados lineares sem restrições A * X = b é A \ b, que é razoavelmente preciso e confiável, exceto quando A está mal condicionado, ou seja, possui um grande número de condições. A \ b é mais rápido em calcular que pinv (A) * b, mas não é tão confiável ou preciso.

3) Formação das equações normais (TERRÍVEL do ponto de vista da confiabilidade e precisão numérica, porque quadratura o número da condição, o que é uma coisa muito ruim de se fazer) e

3a) resolver pela fatoração de Cholesky (não é bom)

3b) matriz explicitamente invertida (HORRÍVEL)

4) Solucionando problemas de programação quadrática ou de cone de segunda ordem

4a) Resolva usando o software de programação quadrática de alta qualidade. Isso é confiável e numericamente preciso, mas leva mais tempo que SVD ou QR. No entanto, é fácil adicionar restrições lineares vinculadas ou gerais, ou termos de penalidade ou regularização linear ou quadrática (duas normas) à função objetivo, e ainda resolver o problema usando o software de programação quadrática.

4b) Resolva como um problema de cone de segunda ordem usando o software de otimização cônica de alta qualidade. As observações são iguais às do software de programação quadrática, mas você também pode adicionar restrições lineares vinculadas ou gerais e outras restrições cônicas ou termos objetivos de função, como termos de penalização ou regularização em várias normas.

5) Resolva usando um software de otimização não linear de uso geral de alta qualidade. Isso ainda pode funcionar bem, mas em geral será mais lento que o software de Programação Quadrática ou Otimização Cônica, e talvez não seja tão confiável. No entanto, pode ser possível incluir não apenas restrições lineares vinculadas e gerais, mas também restrições não lineares na otimização de mínimos quadrados. Além disso, pode ser usado para mínimos quadrados não lineares e se outros termos não lineares forem adicionados à função objetivo.

6) Resolva usando algoritmos de otimização não linear de uso geral péssimo -> NUNCA FAÇA ISSO.

7) Resolva usando o pior algoritmo de otimização não linear de propósito geral possível, ou seja, descida de gradiente. Use isso apenas se desejar ver o quão ruim e não confiável um método de solução pode ser. Se alguém lhe disser para usar a descida de gradiente para resolver problemas lineares de mínimos quadrados

7 i) Aprenda sobre computação estatística com alguém que sabe algo sobre ela

7 ii) Aprenda a otimização de alguém que sabe algo sobre isso.

Mark L. Stone
fonte
Bom post, por que você acha que Cholesky não é bom, considerando que seu sistema é PD? (e não com um número de condição ridículo) BTW, acho que você quer dizer (ou acrescentar) a noção de inversa generalizada (usada principalmente para fins educacionais, obviamente), tanto no ponto "SVD" quanto no "explicitamente invertendo".
usεr11852 diz Reinstate Monic
2
BTW, é ridículo a frequência com que matrizes com números de condição muito altos são geradas, especialmente pelas massas não lavadas (ou seja, a maioria das pessoas que faz mínimos quadrados lineares, especialmente devido à democratização do acesso), que não estão sintonizadas com ela.
Mark L. Stone
11
mldivide, ie. barra invertida, ou seja, \ usa QR quando m ~ = n (mínimos quadrados), como afirmei na segunda frase do meu parágrafo (2) acima. Você ficaria surpreso com a quantidade de porcaria que existe no MATLAB - não apenas nas caixas de ferramentas, algumas das quais são absolutamente horríveis, mas em menor grau em algumas das principais funções.
Mark L. Stone
11
@ MarkL.Stone, ótima resposta! você poderia explicar um pouco mais sobre por que não é aconselhável usar a descida de gradiente para resolver o quadrado mínimo! (no meu entender, é apenas uma abordagem iterativa em comparação com as outras (abordagens de solução de direção) mencionadas acima). Além disso, você também pode comentar sobre o problema: "se eu tiver n> = 30.000 recursos para um problema, o método da equação normal será muito lento, pois a inversão da matriz n * n seria terrível! Por outro lado, a GD funcionaria dessa maneira caso bonito! quaisquer pensamentos sobre o desempenho do SVD & QR ". qualquer sugestão seria útil.
anu
11
@ anu Use apenas descida gradiente como último recurso. e isso seria apenas se o problema for grande demais para ser resolvido por SVD ou QR. Nunca forme as equações normais, muito menos inverta explicitamente uma matriz para resolver equações normais, NUNCA. Hoje em dia, 30.000 recursos não parecem muito muitos.
Mark L. Stone
0

Encontrar coeficientes de um modelo linear é tecnicamente o processo de encontrar soluções para um conjunto de Equações Lineares .

Para computar essas soluções, muitas optimization techniquesforam desenvolvidas e Gradient Descentsão uma delas.
Assim, a descida do gradiente não é a única maneira de fazer isso.

Andrew Ng o usa no curso porque é simples de entender, sem lidar com álgebra linear avançada e computação numérica.

Vikas Raturi
fonte
Embora não esteja errado, acho que sua resposta falha no quadro geral, concentrando-se em um caso não padrão. A grande maioria dos modelos de regressão linear é ajustada usando a decomposição QR empregando uma solução de formulário fechado. GD-gradient decent- é usado como exemplo para introduzir métodos mais avançados (por exemplo, SGD- estocástico GD).
usεr11852 diz Reinstate Monic
Você pode elaborar o que é decomposição QR?
Victor
3
UMAx=bUMA=QRRQUMAx=b⇒QRx=b⇔Rx=QTbRQTQ=Eu. Para matrizes muito grandes (milhões de entradas), isso pode ser mais caro do que um solucionador iterativo, por exemplo. SGD. Como a maioria das pessoas não possui matrizes muito grandes, a decomposição do QR é melhor. Em geral, a decomposição do QR moldou o mundo numérico; O SIAM o selecionou como um dos 10 principais algoritmos do século XX.
usεr11852 diz Reinstate Monic
@ usεr11852 sim, é claro. Isso porque, eu queria manter a resposta simples, para evitar conceitos como a decomposição do QR, permanecendo relevantes para o domínio do nível do curso de Ng.
Vikas Raturi 31/07/2015
3
O QR foi um dos 10 principais algoritmos do século XX. Mas o tempo avança, e mesmo que algoritmos eficazes para calcular SVD remontem à década de 1960, você precisa observar a importância das áreas de aplicação. Portanto, acredito que SVD é o algoritmo TOP do século XXI. Francamente, você já ouviu falar do QR ser usado para recomendar filmes? Não, o SVD é usado para essa aplicação crítica. O SVD é claramente o algoritmo de escolha quando o Twitter envia recomendações não solicitadas a velhotes conservadores sobre quais celebridades adolescentes devem seguir. Vamos ver o QR fazer isso !!!
Mark L. Stone