¿Cómo ejecutar la regresión lineal de forma paralela / distribuida para la configuración de Big Data?

Estoy trabajando en un problema de regresión lineal muy grande, con un tamaño de datos tan grande que deben almacenarse en un grupo de máquinas. Será demasiado grande para agregar todas las muestras en la memoria de una sola máquina (incluso el disco)

Para hacer la regresión de estos datos, estoy pensando en un enfoque paralelo, es decir, ejecutar la regresión en cada cuadro individual y luego calcular la beta en función de las estadísticas de cada beta individual (probablemente una media o una mediana)

Tiene esto algún sentido ? Si es así, ¿cómo debo obtener el total esperado de cada individual ?$R^2$$R^2$

Respuesta corta:

Sí, se realizó una regresión lineal en paralelo. Por ejemplo, Xiangrui Meng et al. (2016) para Machine Learning en Apache Spark. La forma en que funciona es usando el descenso de gradiente estocástico (SGD). En la sección 3, características principales, el autor mencionó:

Los modelos lineales generalizados se aprenden a través de algoritmos de optimización que paralelizan el cálculo de gradiente, utilizando bibliotecas de álgebra lineal basadas en C ++ rápidas para los cálculos de los trabajadores.

Puede encontrar un ejemplo de cómo funciona SGD en mi respuesta aquí: ¿Cómo podría el descenso de gradiente estocástico ahorrar tiempo en comparación con el descenso de gradiente estándar?

Respuesta larga:

Tenga en cuenta que la notación no es consistente con el enlace que proporcioné, creo que la notación matricial es mejor en esta pregunta.

Para hacer una regresión lineal estamos tratando de hacer

La derivada es

En configuraciones de datos pequeños, podemos establecer la derivada en y resolverla directamente. (p. ej., descomposición QR en R.) En configuraciones de datos grandes, la matriz de datos es demasiado grande para ser almacenada en la memoria y puede ser difícil de resolver directamente. (No estoy familiarizado con cómo hacer la descomposición QR o la descomposición de Cholesky para matrices enormes).$0$$X$

Una forma de paralelizar esto es intentar usar un método iterativo: el descenso de gradiente estocástico, donde podemos aproximar el gradiente utilizando un subconjunto de datos. (Si usamos , para representar un subconjunto de los datos, el gradiente puede aproximarse en , y podemos actualizar con el gradiente aproximado).$X_s$$y_s$$2X_s^T(X_s\beta-y_s)$$\beta$

Además, para la estadística , podemos calcular para todos los datos en paralelo o aproximarlos usando un subconjunto de datos.$R^2$$R^2$

Intuición sobre cómo funciona (paradigma mapreduce):

Sigo diciendo aproximación usando un subconjunto; La intuición de por qué esto funciona puede describirse en el siguiente ejemplo: supongamos que tengo 100 mil millones de puntos de datos y queremos calcular el promedio de todos los puntos de datos. Supongamos que llevar a cabo una operación de este tipo lleva mucho tiempo y además que no se pueden almacenar todos los datos en la memoria.

Lo que podemos hacer es tomar un subconjunto, decir mil millones de elementos y calcular el promedio de estos. La aproximación así producida no debe estar muy lejos de la verdad (es decir, utilizando todos los datos).

Para paralelizar, podemos usar 100 computadoras, y cada una de ellas toma un subconjunto diferente de los mil millones de puntos de datos y calcula el promedio de estos. (Comúnmente conocido como el paso MAP). Finalmente, ejecute otro promedio en estos 100 números (también conocido como el paso REDUCIR).

Tenga en cuenta que el "paradigma de reducción de mapas" funcionaría bien en algunos casos, pero no en otros. Por ejemplo, la operación "promedio" mencionada anteriormente es muy fácil, porque sabemos , ( asumiendo que la longitud de e son iguales). Para algunos métodos iterativos, es decir, la iteración actual depende de los resultados de la iteración anterior, es difícil paralelizar. El descenso de gradiente estocástico resuelve este problema al aproximar el gradiente utilizando un subconjunto de datos. Y los detalles se pueden encontrar en la respuesta de @ user20160.$\text{mean}(<x,y>)=\text{mean}(x)+\text{mean(y)}$$x$$y$

Referencias

Xiangrui Meng y col. (2016) . MLlib: Aprendizaje automático en Apache Spark

Como se mencionó en @ hxd1011, un enfoque es formular la regresión lineal como un problema de optimización, luego resolverlo usando un algoritmo iterativo (por ejemplo, descenso de gradiente estocástico). Este enfoque puede ser paralelo, pero hay un par de preguntas importantes: 1) ¿Cómo se debe dividir el problema en subproblemas? 2) Dado que los algoritmos de optimización como SGD son inherentemente secuenciales, ¿cómo se deben combinar las soluciones a los subproblemas para obtener una solución global?

Zinkevich y col. (2010) describen algunos enfoques anteriores para la paralelización en varias máquinas:

• 1) Paralelo SGD de la siguiente manera: Divida los datos en varias máquinas. En cada paso, cada máquina local estima el gradiente utilizando un subconjunto de datos. Todas las estimaciones de gradiente se pasan a una máquina central, que las agrega para realizar una actualización de parámetros global. La desventaja de este enfoque es que requiere una gran comunicación de red, lo que reduce la eficiencia.

• 2) Particionar los datos de manera uniforme en las máquinas locales. Cada máquina resuelve el problema exactamente para su propio subconjunto de datos, utilizando un solucionador de lotes. Las estimaciones finales de los parámetros de las máquinas locales se promedian para producir una solución global. El beneficio de este enfoque es que requiere muy poca comunicación de red, pero la desventaja es que las estimaciones de los parámetros pueden ser subóptimas.

Proponen un nuevo enfoque:

• 3) Permita que cada máquina local dibuje puntos de datos al azar. Ejecute SGD en cada máquina. Finalmente, promedie los parámetros entre máquinas para obtener una solución global. Al igual que (2), este método requiere poca comunicación de red. Pero, las estimaciones de los parámetros son mejores porque cada máquina puede acceder a una fracción mayor de los datos.

El enfoque de optimización paralela es muy general y se aplica a muchos algoritmos de aprendizaje automático (no solo a la regresión lineal).

Otra alternativa sería utilizar algoritmos de descomposición de matriz paralela / distribuida o solucionadores lineales. La regresión lineal de mínimos cuadrados tiene una estructura especial que le permite resolverse utilizando métodos de descomposición matricial. Así es como normalmente lo resolvería en el caso de un conjunto de datos más pequeño que cabe en la memoria. Esto se puede paralelizar mediante la distribución de bloques de la matriz en varias máquinas, y luego resolver el problema utilizando cálculos de matriz paralela / distribuida. Dado que este enfoque es más especializado para resolver sistemas lineales, sería interesante ver cómo se compara su rendimiento con el enfoque de optimización distribuida más general. Si alguien puede proporcionar más información sobre esto, me alegraría saberlo.

Referencias

Zinkevich y col. (2010) . Descenso de gradiente estocástico en paralelo.

Mucho, mucho, antes de reducir el mapa, resolví esto. A continuación se muestra una referencia a un antiguo artículo mío en Journal of Econometrics 1980. Era para una probabilidad máxima no lineal paralela y funcionaría para la estimación de M.

El método es exacto para las regresiones. Divida los datos en k subconjuntos en k procesadores / unidades (también podría hacerse secuencialmente). ¿Las k regresiones mantienen los coeficientes de regresión en la matriz X'X para cada uno? Llame a estos b1, ..., bk y W1, ..., Wk respectivamente, entonces los coeficientes de regresión generales están dados por b = inverso (W1 + .. + Wk) * (W1 * b1 + ... + Wk * bk) uno necesita otra transferencia a través de los datos para calcular los residuos usando b para que los parámetros obtengan sigma ^ 2 la varianza de error estimada, R ^ 2 F general y similares. Entonces la matriz de covarianza de b está dada exactamente por sigma ^ 2 (inversa (W1 + .. + Wk)). Arriba * indica la multiplicación de matrices.

https://www.sciencedirect.com/science/article/pii/0304407680900950