Resolviendo parámetros de regresión en forma cerrada vs descenso de gradiente

72

En el curso de aprendizaje automático de Andrew Ng , introduce la regresión lineal y la regresión logística, y muestra cómo ajustar los parámetros del modelo utilizando el descenso de gradiente y el método de Newton.

Sé que el descenso de gradiente puede ser útil en algunas aplicaciones de aprendizaje automático (p. Ej., Retropropagación), pero en el caso más general, ¿hay alguna razón por la que no resolvería los parámetros en forma cerrada, es decir, tomando la derivada de la función de costos y la resolución a través de cálculo?

¿Cuál es la ventaja de usar un algoritmo iterativo como el descenso de gradiente sobre una solución de forma cerrada en general, cuando hay una disponible?

Jeff
fuente
9
No creo que haya una solución de forma cerrada para el MLE de los parámetros de regresión en la mayoría de los glms (por ejemplo, regresión logística). La regresión lineal con errores normales es una excepción.
Macro
55
Interesante ... ¿Esto significa que diferentes paquetes de estadísticas podrían dar diferentes respuestas para la regresión logística dependiendo, por ejemplo, de la configuración inicial de los parámetros, el número de iteraciones, múltiples mínimos locales, etc.? ¿seguir? (Aunque estoy seguro de que las diferencias, si existen, son mínimas en la mayoría de los casos)
Jeff
3
(+1) A tu pregunta y tu comentario, Jeff. Los GLM que usan el enlace canónico (como la regresión logística) se benefician de las buenas propiedades de convexidad. Puede haber más de un algoritmo para resolver tales problemas, pero el resultado básico de esto es que (módulo algunos detalles bastante menores), algoritmos numéricos bien implementados darán resultados consistentes entre ellos.
cardenal
2
Personalmente no me gusta el curso de Andrew Ng porque ha llevado a las personas a creer que la Regresión lineal es "aprendizaje automático".
Digio

Respuestas:

86

A menos que la solución de forma cerrada sea extremadamente costosa de calcular, generalmente es el camino a seguir cuando está disponible. Sin embargo,

  1. Para la mayoría de los problemas de regresión no lineal no existe una solución de forma cerrada.

  2. Incluso en la regresión lineal (uno de los pocos casos en los que hay disponible una solución de forma cerrada), puede ser poco práctico utilizar la fórmula. El siguiente ejemplo muestra una forma en que esto puede suceder.

Para la regresión lineal en un modelo de la forma , donde es una matriz con rango de columna completo, la solución de mínimos cuadrados,Xy=XβX

β^=argminXβy2

es dado por

β^=(XTX)1XTy

Ahora, imagine que es una matriz muy grande pero dispersa. por ejemplo, puede tener 100,000 columnas y 1,000,000 de filas, pero solo 0.001% de las entradas en son distintas de cero. Existen estructuras de datos especializadas para almacenar solo las entradas distintas de cero de tales matrices dispersas. X XXXX

También imagine que tenemos mala suerte, y es una matriz bastante densa con un porcentaje mucho mayor de entradas distintas de cero. Almacenar una matriz densa de 100,000 por 100,000 elementos requeriría números de coma flotante (a 8 bytes por número, esto equivale a 80 gigabytes). Esto sería poco práctico para almacenar en cualquier cosa pero una supercomputadora Además, el inverso de esta matriz (o más comúnmente un factor Cholesky) también tenderá a tener entradas mayormente distintas de cero. X T X 1 × 10 10XTXXTX1×1010

Sin embargo, existen métodos iterativos para resolver el problema de mínimos cuadrados que no requieren más almacenamiento que , , y y nunca de manera explícita formar el producto de la matriz . y β X T XXyβ^XTX

En esta situación, usar un método iterativo es mucho más eficiente computacionalmente que usar la solución de forma cerrada para el problema de mínimos cuadrados.

Este ejemplo puede parecer absurdamente grande. Sin embargo, los grandes problemas de mínimos cuadrados dispersos de este tamaño se resuelven rutinariamente mediante métodos iterativos en computadoras de escritorio en la investigación de tomografía sísmica.

Brian Borchers
fuente
44
Debo mencionar que también hay problemas de precisión numérica que pueden hacer que el uso de la solución de forma cerrada para el problema de mínimos cuadrados no sea aconsejable. Sin embargo, esto requeriría una discusión sobre el mal condicionamiento que parece estar más allá de la comprensión actual del póster original.
Brian Borchers
17
por favor no dude en publicar una respuesta porque no cree que lo entienda. primero: no me hará daño proporcionar más información, incluso si me lleva un poco de investigación para poder captarla. segundo: el modelo de stackexchange supone que esta pregunta y respuesta beneficiarán a otras en el futuro. en otras palabras, no tontes tu respuesta en función de cuánto creas que sabe el OP, o estarás perjudicando a los demás.
Jeff
2
@Brian, creo que tu comentario está más cerca del corazón del problema y está un poco en desacuerdo con la primera oración de la respuesta. No creo que ningún software de mínimos cuadrados (en su sano juicio) emplee la solución de forma cerrada. :)
cardenal
44
Cardinal: en la práctica, es mejor usar la factorización QR o SVD para resolver problemas de mínimos cuadrados a pequeña escala. Yo diría que una solución que usa una de estas factorizaciones ortogonales también es una "solución de forma cerrada" en comparación con el uso de una técnica iterativa como LSQR. No profundicé en esto en mi respuesta porque innecesariamente distrae la atención de mi punto principal.
Brian Borchers
2
¿Mal acondicionamiento? Libro de texto solución de forma cerrada? Me encanta el olor de los números de condición al cuadrado en la mañana. ¿Tiene un número de condición grande? ¿Por qué no cuadrarlo y hacerlo aún más grande? ¿Tiene un número de condición no tan grande? ¿Por qué no cuadrarlo y hacerlo grande?
Mark L. Stone
2

Ha habido varias publicaciones sobre aprendizaje automático (ML) y regresión. ML no es necesario para resolver mínimos cuadrados ordinarios (MCO), ya que involucra una operación de emparejamiento de matriz de un solo paso para resolver un sistema de ecuaciones lineales, es decir, . El hecho de que todo sea lineal significa que solo se necesita una operación de un paso para resolver los coeficientes. La regresión logística se basa en maximizar la función de probabilidad , que se puede resolver utilizando Newton-Raphson u otros métodos de ascenso de gradiente ML, metaheurística (escalada, algoritmos genéticos, inteligencia de enjambre, optimización de colonias de hormigas, etc.) . β=(XTX)1XTyL=ipi

Con respecto a la parsimonia, el uso de ML para OLS sería un desperdicio porque el aprendizaje iterativo es ineficiente para resolver OLS.

Ahora, volvamos a su pregunta real sobre los enfoques derivados frente a ML para resolver problemas basados ​​en gradientes. Específicamente, para la regresión logística, se usa comúnmente el enfoque de descenso de gradiente de Newton-Raphson (basado en derivadas). Newton-Raphson requiere que conozca la función objetivo y sus derivadas parciales en cada parámetro (continuo en el límite y diferenciable). ML se usa principalmente cuando la función objetivo es demasiado compleja ("narly") y no conoce las derivadas. Por ejemplo, una red neuronal artificial (ANN) se puede utilizar para resolver un problema de aproximación de función o un problema de clasificación supervisada cuando la función no se conoce. En este caso, el ANN es la función.

No cometa el error de usar métodos de ML para resolver un problema de regresión logística, solo porque puede hacerlo. Para la logística, Newton-Raphson es extremadamente rápido y es la técnica adecuada para resolver el problema. ML se usa comúnmente cuando no sabes cuál es la función. (por cierto, los ANN son del campo de la inteligencia computacional, y no ML).

JoleT
fuente