Regresión lineal y métodos para su recuperación.

Fuente: xkcd

La regresión lineal es uno de los algoritmos básicos para muchas áreas relacionadas con el análisis de datos. La razón de esto es obvia. Se trata de un algoritmo muy simple y comprensible, que ha contribuido a su uso generalizado durante muchas decenas, si no cientos, de años. La idea es que asumimos una dependencia lineal de una variable con respecto a un conjunto de otras variables y luego intentamos restaurar esta dependencia.

Pero este artículo no trata sobre el uso de la regresión lineal para resolver problemas prácticos. Aquí consideraremos características interesantes de la implementación de algoritmos distribuidos para su recuperación, que encontramos al escribir un módulo de aprendizaje automático en apache encender. Un poco de matemáticas básicas, aprendizaje automático y computación distribuida pueden ayudarlo a descubrir cómo realizar una regresión lineal incluso cuando sus datos están distribuidos en miles de nodos.

¿Qué es?

Nos enfrentamos a la tarea de restablecer la dependencia lineal. Como datos de entrada se da un conjunto de vectores de variables supuestamente independientes, cada una de las cuales está asociada a un determinado valor de la variable dependiente. Estos datos se pueden representar en forma de dos matrices:

Ahora, dado que se supone que la dependencia es lineal, escribiremos nuestra suposición en forma de producto de matrices (para simplificar la entrada, aquí y a continuación se supone que el término libre de la ecuación está oculto detrás , y la última columna de la matriz contiene unidades):

Suena muy parecido a un sistema de ecuaciones lineales, ¿no? Parece, pero lo más probable es que no haya soluciones para tal sistema de ecuaciones. La razón de esto es el ruido, que está presente en casi todos los datos reales. Otra razón puede ser la falta de dependencia lineal como tal, que puede combatirse introduciendo variables adicionales que dependan de forma no lineal de las originales. Considere el siguiente ejemplo:

Fuente: Wikipedia

Este es un ejemplo simple de regresión lineal que muestra la relación de una variable (a lo largo del eje ) de otra variable (a lo largo del eje ). Para que el sistema de ecuaciones lineales correspondiente a este ejemplo tenga solución, todos los puntos deben estar exactamente en la misma línea recta. Pero eso no es cierto. Pero no se encuentran en la misma línea recta precisamente debido al ruido (o porque la suposición de una relación lineal era errónea). Por lo tanto, para restaurar una relación lineal a partir de datos reales, generalmente es necesario introducir una suposición más: los datos de entrada contienen ruido y este ruido tiene distribución normal. Se pueden hacer suposiciones sobre otros tipos de distribución de ruido, pero en la gran mayoría de los casos se considera la distribución normal, que se analizará más adelante.

método de máxima verosimilitud

Entonces, asumimos la presencia de ruido aleatorio distribuido normalmente. ¿Qué hacer en tal situación? Para este caso en matemáticas existe y es ampliamente utilizado. método de máxima verosimilitud. En definitiva, su esencia radica en la elección. funciones de probabilidad y su posterior maximización.

Volvemos a restaurar una relación lineal a partir de datos con ruido normal. Tenga en cuenta que la relación lineal supuesta es la expectativa matemática distribución normal existente. Al mismo tiempo, la probabilidad de que Toma un valor u otro, sujeto a la presencia de observables. , se ve así:

Sustituyamos ahora и Las variables que necesitamos son:

Sólo queda encontrar el vector. , en el que esta probabilidad es máxima. Para maximizar dicha función, es conveniente tomar primero un logaritmo de la misma (el logaritmo de la función alcanzará un máximo en el mismo punto que la función misma):

Lo que, a su vez, se reduce a minimizar la siguiente función:

Por cierto, esto se llama método. mínimos cuadrados. A menudo se omiten todas las consideraciones anteriores y simplemente se utiliza este método.

descomposición QR

El mínimo de la función anterior se puede encontrar encontrando el punto en el que el gradiente de esta función es cero. Y el gradiente se escribirá de la siguiente manera:

descomposición QR es un método matricial para resolver el problema de minimización utilizado en el método de mínimos cuadrados. En este sentido, reescribimos la ecuación en forma matricial:

Entonces descomponemos la matriz. a matrices и y realizar una serie de transformaciones (aquí no se considerará el algoritmo de descomposición QR en sí, solo su uso en relación con la tarea en cuestión):

Matriz es ortogonal. Esto nos permite deshacernos del trabajo. :

Y si reemplazas en , entonces funcionará . Teniendo en cuenta que es una matriz triangular superior, se ve así:

Esto se puede resolver usando el método de sustitución. Elemento se encuentra como , elemento anterior se encuentra como y así sucesivamente.

Vale la pena señalar aquí que la complejidad del algoritmo resultante debido al uso de la descomposición QR es igual a . Además, a pesar de que la operación de multiplicación de matrices está bien paralelizada, no es posible escribir una versión distribuida eficaz de este algoritmo.

Descenso de gradiente

Cuando se habla de minimizar una función, siempre vale la pena recordar el método de descenso de gradiente (estocástico). Este es un método de minimización simple y efectivo basado en calcular iterativamente el gradiente de una función en un punto y luego desplazarlo en la dirección opuesta al gradiente. Cada uno de estos pasos acerca la solución al mínimo. El degradado sigue teniendo el mismo aspecto:

Este método también está bien paralelizado y distribuido debido a las propiedades lineales del operador de gradiente. Tenga en cuenta que en la fórmula anterior, bajo el signo de la suma hay términos independientes. En otras palabras, podemos calcular el gradiente de forma independiente para todos los índices. de primero a , en paralelo con esto, calcule el gradiente para índices con a . Luego agregue los gradientes resultantes. El resultado de la suma será el mismo que si calculáramos inmediatamente el gradiente para los índices del primero al . Por lo tanto, si los datos se distribuyen entre varios datos, el gradiente se puede calcular de forma independiente en cada uno de ellos y luego los resultados de estos cálculos se pueden sumar para obtener el resultado final:

Desde el punto de vista de la implementación, esto se ajusta al paradigma MapReduce. En cada paso del descenso del gradiente, se envía una tarea a cada nodo de datos para calcular el gradiente, luego los gradientes calculados se recopilan y el resultado de su suma se utiliza para mejorar el resultado.

A pesar de la facilidad de implementación y la capacidad de ejecución en el paradigma MapReduce, el descenso de gradiente también tiene sus inconvenientes. En particular, el número de pasos necesarios para lograr la convergencia es significativamente mayor en comparación con otros métodos más especializados.

LSQR

LSQR es otro método para resolver el problema, que es adecuado tanto para restaurar la regresión lineal como para resolver sistemas de ecuaciones lineales. Su característica principal es que combina las ventajas de los métodos matriciales y un enfoque iterativo. Las implementaciones de este método se pueden encontrar en ambas bibliotecas. Cienciay en MATLAB. No se proporcionará aquí una descripción de este método (se puede encontrar en el artículo LSQR: un algoritmo para ecuaciones lineales dispersas y mínimos cuadrados dispersos). En cambio, se demostrará un enfoque para adaptar LSQR a la ejecución en un entorno distribuido.

El método LSQR se basa en procedimiento de bidiagonalización. Este es un procedimiento iterativo, cada iteración consta de los siguientes pasos:


Pero si asumimos que la matriz está dividido horizontalmente, entonces cada iteración se puede representar como dos pasos de MapReduce. De esta forma, es posible minimizar las transferencias de datos durante cada iteración (solo vectores con una longitud igual al número de incógnitas):

Es este enfoque el que se utiliza al implementar la regresión lineal en Apache enciende ML.

Conclusión

Existen muchos algoritmos de recuperación de regresión lineal, pero no todos se pueden aplicar en todas las condiciones. Por tanto, la descomposición QR es excelente para una solución precisa en conjuntos de datos pequeños. El descenso de gradiente es sencillo de implementar y permite encontrar rápidamente una solución aproximada. Y LSQR combina las mejores propiedades de los dos algoritmos anteriores, ya que se puede distribuir, converge más rápido en comparación con el descenso de gradiente y también permite detener temprano el algoritmo, a diferencia de la descomposición QR, para encontrar una solución aproximada.

Fuente: habr.com