Fonte:
A regressão linear é um dos algoritmos básicos para muitas áreas relacionadas à análise de dados. A razão para isto é óbvio. Este é um algoritmo muito simples e compreensível que contribuiu para seu uso generalizado por muitas dezenas, senão centenas, de anos. A ideia é assumirmos uma dependência linear de uma variável em um conjunto de outras variáveis e então tentarmos restaurar essa dependência.
Mas este artigo não trata do uso de regressão linear para resolver problemas práticos. Aqui consideraremos recursos interessantes da implementação de algoritmos distribuídos para sua recuperação, que encontramos ao escrever um módulo de aprendizado de máquina em . Um pouco de matemática básica, aprendizado de máquina e computação distribuída podem ajudá-lo a descobrir como realizar a regressão linear mesmo quando seus dados estão distribuídos por milhares de nós.
O que estamos falando?
Enfrentamos a tarefa de restaurar a dependência linear. Como dados de entrada, é dado um conjunto de vetores de variáveis supostamente independentes, cada um dos quais está associado a um determinado valor da variável dependente. Esses dados podem ser representados na forma de duas matrizes:
Agora, como a dependência é assumida e, além disso, linear, escreveremos nossa suposição na forma de um produto de matrizes (para simplificar o registro, aqui e abaixo assume-se que o termo livre da equação está escondido atrás , e a última coluna da matriz contém unidades):
Parece muito com um sistema de equações lineares, não é? Parece, mas muito provavelmente não haverá soluções para tal sistema de equações. A razão para isso é o ruído, que está presente em quase todos os dados reais. Outra razão pode ser a falta de dependência linear como tal, que pode ser combatida pela introdução de variáveis adicionais que dependem de forma não linear das originais. Considere o seguinte exemplo:
Fonte:
Este é um exemplo simples de regressão linear que mostra a relação de uma variável (ao longo do eixo ) de outra variável (ao longo do eixo ). Para que o sistema de equações lineares correspondente a este exemplo tenha solução, todos os pontos devem estar exatamente na mesma linha reta. Mas isso não é verdade. Mas eles não estão na mesma linha reta precisamente por causa do ruído (ou porque a suposição de uma relação linear era errônea). Assim, para restaurar uma relação linear a partir de dados reais, normalmente é necessário introduzir mais uma suposição: os dados de entrada contêm ruído e este ruído tem . Você pode fazer suposições sobre outros tipos de distribuição de ruído, mas na grande maioria dos casos é a distribuição normal que é considerada, o que será discutido mais adiante.
Método de máxima verossimilhança
Portanto, assumimos a presença de ruído aleatório normalmente distribuído. O que fazer em tal situação? Para este caso em matemática existe e é amplamente utilizado . Em suma, a sua essência reside na escolha e sua subsequente maximização.
Voltamos a restaurar uma relação linear de dados com ruído normal. Observe que a relação linear assumida é a expectativa matemática distribuição normal existente. Ao mesmo tempo, a probabilidade de que assume um valor ou outro, sujeito à presença de observáveis , parece com isso:
Vamos agora substituir и As variáveis que precisamos são:
Resta apenas encontrar o vetor , em que esta probabilidade é máxima. Para maximizar tal função, é conveniente primeiro obter um logaritmo dela (o logaritmo da função atingirá um máximo no mesmo ponto que a própria função):
O que, por sua vez, se resume a minimizar a seguinte função:
A propósito, isso é chamado de método . Muitas vezes todas as considerações acima são omitidas e este método é simplesmente usado.
Decomposição QR
O mínimo da função acima pode ser encontrado encontrando o ponto em que o gradiente desta função é zero. E o gradiente será escrito da seguinte forma:
é um método matricial para resolver o problema de minimização usado no método dos mínimos quadrados. A este respeito, reescrevemos a equação em forma de matriz:
Então decompomos a matriz para matrizes и e realizar uma série de transformações (o algoritmo de decomposição QR em si não será considerado aqui, apenas seu uso em relação à tarefa em questão):
Matriz é ortogonal. Isso nos permite livrar-nos do trabalho :
E se você substituir em , então vai funcionar . Considerando que é uma matriz triangular superior, fica assim:
Isso pode ser resolvido usando o método de substituição. Elemento está localizado como , elemento anterior está localizado como e assim por diante.
É importante notar aqui que a complexidade do algoritmo resultante devido ao uso da decomposição QR é igual a . Além disso, apesar da operação de multiplicação de matrizes ser bem paralelizada, não é possível escrever uma versão distribuída eficaz deste algoritmo.
Gradiente descendente
Ao falar em minimizar uma função, vale sempre lembrar o método de descida gradiente (estocástica). Este é um método de minimização simples e eficaz baseado no cálculo iterativo do gradiente de uma função em um ponto e depois deslocá-lo na direção oposta ao gradiente. Cada etapa aproxima a solução do mínimo. O gradiente ainda parece o mesmo:
Este método também é bem paralelizado e distribuído devido às propriedades lineares do operador gradiente. Observe que na fórmula acima, sob o sinal de soma existem termos independentes. Em outras palavras, podemos calcular o gradiente de forma independente para todos os índices do primeiro ao , paralelamente a isso, calcule o gradiente para índices com para . Em seguida, adicione os gradientes resultantes. O resultado da adição será o mesmo que se calculássemos imediatamente o gradiente dos índices do primeiro ao . Assim, se os dados estiverem distribuídos entre vários dados, o gradiente pode ser calculado independentemente em cada pedaço, e então os resultados desses cálculos podem ser somados para obter o resultado final:
Do ponto de vista da implementação, isso se enquadra no paradigma . Em cada etapa da descida do gradiente, uma tarefa é enviada a cada nó de dados para calcular o gradiente, então os gradientes calculados são coletados juntos e o resultado de sua soma é usado para melhorar o resultado.
Apesar da facilidade de implementação e da capacidade de execução no paradigma MapReduce, a descida gradiente também tem suas desvantagens. Em particular, o número de passos necessários para alcançar a convergência é significativamente maior em comparação com outros métodos mais especializados.
LSQR
é outro método para resolver o problema, adequado tanto para restaurar a regressão linear quanto para resolver sistemas de equações lineares. Sua principal característica é combinar as vantagens dos métodos matriciais e uma abordagem iterativa. Implementações deste método podem ser encontradas nas bibliotecas e em . A descrição deste método não será fornecida aqui (pode ser encontrada no artigo ). Em vez disso, será demonstrada uma abordagem para adaptar o LSQR à execução em um ambiente distribuído.
O método LSQR é baseado em . Este é um procedimento iterativo, cada iteração consistindo nas seguintes etapas:
Mas se assumirmos que a matriz é particionado horizontalmente, então cada iteração pode ser representada como duas etapas do MapReduce. Desta forma, é possível minimizar as transferências de dados durante cada iteração (apenas vetores com comprimento igual ao número de incógnitas):
É esta abordagem que é usada ao implementar a regressão linear em .
Conclusão
Existem muitos algoritmos de recuperação de regressão linear, mas nem todos podem ser aplicados em todas as condições. Portanto, a decomposição QR é excelente para soluções precisas em pequenos conjuntos de dados. O gradiente descendente é simples de implementar e permite encontrar rapidamente uma solução aproximada. E o LSQR combina as melhores propriedades dos dois algoritmos anteriores, pois pode ser distribuído, converge mais rápido em comparação com o gradiente descendente e também permite a parada antecipada do algoritmo, ao contrário da decomposição QR, para encontrar uma solução aproximada.
Fonte: habr.com