Resolução de parâmetros de regressão em forma fechada versus descida de gradiente

71

No curso de aprendizado de máquina de Andrew Ng , ele introduz a regressão linear e a regressão logística e mostra como ajustar os parâmetros do modelo usando a descida do gradiente e o método de Newton.

Eu sei que a descida gradiente pode ser útil em algumas aplicações de aprendizado de máquina (por exemplo, retropropagação), mas no caso mais geral existe alguma razão para que você não resolva os parâmetros de forma fechada - ou seja, tomando a derivada de a função de custo e resolução via Cálculo?

Qual é a vantagem de usar um algoritmo iterativo como descida de gradiente em relação a uma solução de forma fechada em geral, quando uma estiver disponível?

Jeff
fonte
9
Eu não acho que exista uma solução de formulário fechado para o MLE dos parâmetros de regressão na maioria das glms (por exemplo, regressão logística). A regressão linear com erros normais é uma exceção.
Macro
5
Interessante ... Isso significa que diferentes pacotes de estatísticas podem fornecer respostas diferentes para a regressão logística, dependendo, por exemplo, das configurações iniciais dos parâmetros, número de iterações, múltiplos mínimos locais etc. - ou existe um procedimento convencional em que todos os bons pacotes de estatísticas serão Segue? (Embora eu tenho certeza que quaisquer diferenças, se eles existem, são minutos na maioria dos casos)
Jeff
3
(+1) À sua pergunta e seu comentário, Jeff. Os GLMs que usam o link canônico (como a regressão logística) se beneficiam das boas propriedades da convexidade. Pode haver mais de um algoritmo para resolver esses problemas, mas o resultado básico disso é que (módulo alguns detalhes bastante pequenos), algoritmos numéricos bem implementados fornecerão resultados consistentes entre eles.
cardeal
2
Pessoalmente, não gosto do curso de Andrew Ng porque levou as pessoas a acreditar que a regressão linear é "aprendizado de máquina".
Digio 19/05/19

Respostas:

85

A menos que a solução de formulário fechado seja extremamente cara de calcular, geralmente é o caminho a seguir quando está disponível. Contudo,

  1. Para a maioria dos problemas de regressão não linear, não há solução de forma fechada.

  2. Mesmo em regressão linear (um dos poucos casos em que uma solução de formulário fechado está disponível), pode ser impraticável usar a fórmula. O exemplo a seguir mostra uma maneira pela qual isso pode acontecer.

Para regressão linear em um modelo da forma , em que é uma matriz com classificação completa da coluna, a solução dos mínimos quadrados,y=XβX

β^=argminXβy2

É dado por

β^=(XTX)1XTy

Agora, imagine que é uma matriz muito grande, mas esparsa. por exemplo, pode ter 100.000 colunas e 1.000.000 linhas, mas apenas 0,001% das entradas em são diferentes de zero. Existem estruturas de dados especializadas para armazenar apenas as entradas diferentes de zero dessas matrizes esparsas. XXX

Imagine também que não temos sorte e é uma matriz bastante densa, com uma porcentagem muito maior de entradas diferentes de zero. Armazenar uma matriz densa de 100.000 por 100.000 elementos exigiria números de ponto flutuante (a 8 bytes por número, isso chega a 80 gigabytes). Isso seria impraticável para armazenar qualquer coisa mas um supercomputador. Além disso, o inverso dessa matriz (ou mais comumente um fator de Cholesky) também tenderia a ter entradas na maioria diferentes de zero. XTXXTX1×1010

No entanto, existem métodos iterativos para resolver o problema dos mínimos quadrados que não necessitam de mais espaço de armazenamento do que , , e e nunca formar explicitamente o produto matriz . Xyβ^XTX

Nessa situação, usar um método iterativo é muito mais eficiente em termos computacionais do que usar a solução de formulário fechado para o problema dos mínimos quadrados.

Este exemplo pode parecer absurdamente grande. No entanto, grandes problemas esparsos de mínimos quadrados desse tamanho são rotineiramente resolvidos por métodos iterativos em computadores de mesa em pesquisas de tomografia sísmica.

Brian Borchers
fonte
4
Devo mencionar que também existem problemas de precisão numérica que podem tornar desaconselhável o uso da solução de formulário fechado para o problema dos mínimos quadrados. No entanto, isso exigiria uma discussão sobre maus condicionamentos que parece estar além do entendimento atual do pôster original.
Brian Borchers
17
por favor, não hesite em postar uma resposta porque você acha que eu não vou entender. primeiro - não vai doer fornecer mais informações, mesmo que me leve alguma pesquisa para entender. segundo - o modelo stackexchange assume que esta pergunta e resposta beneficiarão outras pessoas no futuro. em outras palavras, não embuste sua resposta com base no quanto você acha que o OP sabe ou estará prestando um desserviço aos outros.
20412 Jeff
2
@ Brian, meu sentimento é que seu comentário chega mais perto do cerne da questão e está um pouco em desacordo com a primeira frase da resposta. Eu não acho que nenhum software de mínimos quadrados (no seu perfeito juízo) emprega a solução em formato fechado. :)
cardeal
4
Cardeal - na prática, é melhor usar a fatoração QR ou SVD para resolver problemas de mínimos quadrados em pequena escala. Eu argumentaria que uma solução usando uma dessas fatorações ortogonais também é uma "solução de forma fechada" em comparação ao uso de uma técnica iterativa como LSQR. Não mergulhei nisso na minha resposta, porque desnecessariamente afasta a atenção do meu ponto principal.
Brian Borchers
2
Mal-condicionado? Solução de formulário fechado para livros didáticos? Adoro o cheiro de números quadrados de condição pela manhã. Tem um grande número de condição? Por que não quadrá-lo e torná-lo ainda maior? Tem um número de condição não tão grande? Por que não quadrá-lo e torná-lo grande.
Mark L. Stone
2

Houve vários posts sobre aprendizado de máquina (ML) e regressão. O ML não é necessário para resolver os mínimos quadrados ordinários (OLS), pois envolve uma operação de sanduíche de matriz de uma etapa para resolver um sistema de equações lineares - isto é, . O fato de tudo ser linear significa que apenas uma operação em uma etapa é necessária para resolver os coeficientes. A regressão logística baseia-se em maximizar a função de probabilidade , que pode ser resolvida usando Newton-Raphson, ou outros métodos de subida de gradiente ML, metaheurísticas (escaladas, algoritmos genéticos, inteligência de enxame, otimização de colônias de formigas etc.) . β=(XTX)1XTyL=ipi

Em relação à parcimônia, o uso de ML para OLS seria um desperdício, porque o aprendizado iterativo é ineficiente para resolver o OLS.

Agora, voltemos à sua verdadeira pergunta sobre abordagens de derivativos vs. ML para resolver problemas baseados em gradiente. Especificamente, para regressão logística, a abordagem de descida de gradiente de Newton-Raphson (baseada em derivadas) é comumente usada. Newton-Raphson exige que você conheça a função objetivo e suas derivadas parciais em cada parâmetro (contínuo no limite e diferenciável). ML é usado principalmente quando a função objetivo é muito complexa ("narly") e você não conhece os derivados. Por exemplo, uma rede neural artificial (RNA) pode ser usada para resolver um problema de aproximação de função ou problema de classificação supervisionada quando a função não é conhecida. Nesse caso, a RNA é a função.

Não cometa o erro de usar métodos ML para resolver um problema de regressão logística, apenas porque você pode. Para a logística, Newton-Raphson é extremamente rápido e é a técnica apropriada para resolver o problema. ML é comumente usado quando você não sabe qual é a função. (a propósito, as RNAs são do campo da inteligência computacional, e não da ML).

JoleT
fonte