Fonte:
A regresión lineal é un dos algoritmos básicos para moitas áreas relacionadas coa análise de datos. A razón disto é obvia. Este é un algoritmo moi sinxelo e comprensible, que contribuíu ao seu uso xeneralizado durante moitas decenas, se non centos, de anos. A idea é que asumimos unha dependencia lineal dunha variable sobre un conxunto doutras variables e despois tentamos restaurar esta dependencia.
Pero este artigo non trata de usar a regresión lineal para resolver problemas prácticos. Aquí consideraremos características interesantes da implementación de algoritmos distribuídos para a súa recuperación, que atopamos ao escribir un módulo de aprendizaxe automática en . Un pouco de matemáticas básicas, aprendizaxe automática e computación distribuída poden axudarche a descubrir como realizar a regresión lineal aínda que os teus datos estean distribuídos en miles de nodos.
De que estamos a falar?
Estamos ante a tarefa de restaurar a dependencia lineal. Como datos de entrada, dáse un conxunto de vectores de variables supostamente independentes, cada un dos cales está asociado a un determinado valor da variable dependente. Estes datos pódense representar en forma de dúas matrices:
Agora, dado que a dependencia é asumida, e, ademais, lineal, escribiremos a nosa suposición en forma de produto de matrices (para simplificar o rexistro, aquí e abaixo asúmese que o termo libre da ecuación está agochado detrás , e a última columna da matriz contén unidades):
Soa moito a un sistema de ecuacións lineais, non? Parece, pero o máis probable é que non haxa solucións para tal sistema de ecuacións. A razón disto é o ruído, que está presente en case todos os datos reais. Outra razón pode ser a falta de dependencia lineal como tal, que se pode combater introducindo variables adicionais que non dependen linealmente das orixinais. Considere o seguinte exemplo:
Fonte:
Este é un exemplo sinxelo de regresión lineal que mostra a relación dunha variable (ao longo do eixe ) doutra variable (ao longo do eixe ). Para que o sistema de ecuacións lineais correspondente a este exemplo teña solución, todos os puntos deben estar exactamente na mesma recta. Pero iso non é certo. Pero non se atopan na mesma liña recta precisamente polo ruído (ou porque a suposición dunha relación lineal era errónea). Así, para restaurar unha relación lineal a partir de datos reais, adoita ser necesario introducir unha suposición máis: os datos de entrada conteñen ruído e este ruído ten ruído. . Podes facer suposicións sobre outros tipos de distribución de ruído, pero na gran maioría dos casos é a distribución normal a que se considera, que se comentará máis adiante.
Método de máxima verosimilitud
Entón, asumimos a presenza de ruído aleatorio distribuído normalmente. Que facer ante tal situación? Para este caso en matemáticas hai e é moi utilizado . En definitiva, a súa esencia reside na elección e a súa maximización posterior.
Volvemos a restaurar unha relación lineal a partir de datos con ruído normal. Nótese que a relación lineal asumida é a expectativa matemática distribución normal existente. Ao mesmo tempo, a probabilidade de que adquire un valor ou outro, suxeito á presenza de observables , como segue:
Imos agora substituír no seu lugar и As variables que necesitamos son:
Só queda atopar o vector , no que esta probabilidade é máxima. Para maximizar tal función, é conveniente tomar primeiro un logaritmo dela (o logaritmo da función alcanzará un máximo no mesmo punto que a propia función):
O que, á súa vez, reduce ao mínimo a seguinte función:
Por certo, isto chámase método . Moitas veces omítense todas as consideracións anteriores e simplemente úsase este método.
Descomposición QR
O mínimo da función anterior pódese atopar atopando o punto no que o gradiente desta función é cero. E o gradiente escribirase do seguinte xeito:
é un método matricial para resolver o problema de minimización utilizado no método dos mínimos cadrados. Neste sentido, reescribimos a ecuación en forma matricial:
Entón descompoñemos a matriz ás matrices и e realizar unha serie de transformacións (non se considerará aquí o propio algoritmo de descomposición de QR, só o seu uso en relación coa tarefa a realizar):
Matriz é ortogonal. Isto permítenos desfacernos do traballo :
E se o substitúe en , entón vai funcionar . Tendo en conta iso é unha matriz triangular superior, ten o seguinte aspecto:
Isto pódese resolver mediante o método de substitución. Elemento está situado como , elemento anterior está situado como e así por diante.
Paga a pena sinalar aquí que a complexidade do algoritmo resultante debido ao uso da descomposición QR é igual a . Ademais, a pesar de que a operación de multiplicación da matriz está ben paralelizada, non é posible escribir unha versión distribuída efectiva deste algoritmo.
Descenso Gradiente
Cando se fala de minimizar unha función, sempre convén lembrar o método de descenso do gradiente (estocástico). Este é un método de minimización sinxelo e eficaz baseado en calcular de forma iterativa o gradiente dunha función nun punto e despois desprazalo na dirección oposta ao gradiente. Cada paso deste tipo achega a solución ao mínimo. O gradiente segue sendo o mesmo:
Este método tamén está ben paralelizado e distribuído debido ás propiedades lineais do operador de gradiente. Teña en conta que na fórmula anterior, baixo o signo de suma hai termos independentes. Noutras palabras, podemos calcular o gradiente de forma independente para todos os índices dende o primeiro ata , paralelamente a isto, calcula o gradiente para índices con para . A continuación, engade os gradientes resultantes. O resultado da suma será o mesmo que se calculasemos inmediatamente o gradiente dos índices do primeiro ao . Así, se os datos se distribúen entre varios datos, o gradiente pódese calcular de forma independente en cada peza, e despois pódense sumar os resultados destes cálculos para obter o resultado final:
Dende o punto de vista da implementación, isto encaixa co paradigma . En cada paso do descenso do gradiente, envíase unha tarefa a cada nodo de datos para calcular o gradiente, despois recóllense os gradientes calculados e utilízase o resultado da súa suma para mellorar o resultado.
A pesar da facilidade de implementación e da capacidade de execución no paradigma MapReduce, a baixada de gradientes tamén ten os seus inconvenientes. En particular, o número de pasos necesarios para lograr a converxencia é significativamente maior en comparación con outros métodos máis especializados.
LSQR
é outro método para resolver o problema, que é adecuado tanto para restaurar a regresión lineal como para resolver sistemas de ecuacións lineais. A súa principal característica é que combina as vantaxes dos métodos matriciales e un enfoque iterativo. As implementacións deste método pódense atopar en ambas as bibliotecas e en . Non se dará aquí unha descrición deste método (pódese atopar no artigo ). Pola contra, demostrarase un enfoque para adaptar LSQR á execución nun ambiente distribuído.
O método LSQR baséase en . Este é un procedemento iterativo, cada iteración consta dos seguintes pasos:
Pero se asumimos que a matriz está dividido horizontalmente, entón cada iteración pode representarse como dous pasos de MapReduce. Deste xeito, é posible minimizar as transferencias de datos durante cada iteración (só vectores cunha lonxitude igual ao número de incógnitas):
Este enfoque é o que se usa cando se implementa a regresión lineal .
Conclusión
Hai moitos algoritmos de recuperación de regresión lineal, pero non todos poden aplicarse en todas as condicións. Polo tanto, a descomposición QR é excelente para unha solución precisa en conxuntos de datos pequenos. O descenso en gradiente é sinxelo de implementar e permítelle atopar rapidamente unha solución aproximada. E LSQR combina as mellores propiedades dos dous algoritmos anteriores, xa que se pode distribuír, converxe máis rápido en comparación co descenso de gradientes e tamén permite a detención temperá do algoritmo, a diferenza da descomposición QR, para atopar unha solución aproximada.
Fonte: www.habr.com