Régression linéaire et méthodes pour sa récupération

Source: xkcd

La régression linéaire est l'un des algorithmes de base pour de nombreux domaines liés à l'analyse des données. La raison de ceci est évidente. Il s’agit d’un algorithme très simple et compréhensible, qui a contribué à son utilisation généralisée depuis plusieurs dizaines, voire centaines d’années. L’idée est de supposer une dépendance linéaire d’une variable à l’égard d’un ensemble d’autres variables, puis d’essayer de restaurer cette dépendance.

Mais cet article ne vise pas à utiliser la régression linéaire pour résoudre des problèmes pratiques. Nous examinerons ici les fonctionnalités intéressantes de la mise en œuvre d'algorithmes distribués pour sa récupération, que nous avons rencontrés lors de l'écriture d'un module d'apprentissage automatique dans Apache Ignite. Un peu de mathématiques de base, d'apprentissage automatique et d'informatique distribuée peuvent vous aider à comprendre comment effectuer une régression linéaire même lorsque vos données sont réparties sur des milliers de nœuds.

Qu'est-ce que c'est?

Nous sommes confrontés à la tâche de restaurer la dépendance linéaire. En tant que données d'entrée, un ensemble de vecteurs de variables supposées indépendantes est donné, dont chacun est associé à une certaine valeur de la variable dépendante. Ces données peuvent être représentées sous la forme de deux matrices :

Maintenant, puisque la dépendance est supposée, et de plus linéaire, nous écrirons notre hypothèse sous la forme d'un produit de matrices (pour simplifier l'enregistrement, ici et ci-dessous on suppose que le terme libre de l'équation est caché derrière , et la dernière colonne de la matrice contient des unités) :

Cela ressemble beaucoup à un système d’équations linéaires, n’est-ce pas ? Il semble que, mais il n'y aura très probablement pas de solutions à un tel système d'équations. La raison en est le bruit, présent dans presque toutes les données réelles. Une autre raison peut être l'absence de dépendance linéaire en tant que telle, qui peut être combattue en introduisant des variables supplémentaires qui dépendent de manière non linéaire des variables d'origine. Prenons l'exemple suivant :

Source: Wikipédia

Ceci est un exemple simple de régression linéaire qui montre la relation entre une variable (le long de l'axe ) à partir d'une autre variable (le long de l'axe ). Pour que le système d'équations linéaires correspondant à cet exemple ait une solution, tous les points doivent se trouver exactement sur la même droite. Mais ce n'est pas vrai. Mais ils ne se situent pas sur la même ligne droite précisément à cause du bruit (ou parce que l’hypothèse d’une relation linéaire était erronée). Ainsi, afin de restaurer une relation linéaire à partir de données réelles, il est généralement nécessaire d'introduire une hypothèse supplémentaire : les données d'entrée contiennent du bruit et ce bruit a distribution normale. Vous pouvez faire des hypothèses sur d'autres types de distribution du bruit, mais dans la grande majorité des cas, c'est la distribution normale qui est prise en compte et qui sera discutée plus en détail.

Méthode du maximum de vraisemblance

Nous avons donc supposé la présence d’un bruit aléatoire normalement distribué. Que faire dans une telle situation ? Pour ce cas en mathématiques, il existe et est largement utilisé méthode du maximum de vraisemblance. Bref, son essence réside dans le choix fonctions de vraisemblance et sa maximisation ultérieure.

Nous revenons à la restauration d'une relation linéaire à partir de données avec un bruit normal. Notez que la relation linéaire supposée est l'espérance mathématique distribution normale existante. En même temps, la probabilité que prend une valeur ou une autre, sous réserve de la présence d'observables , ressemble à ceci:

Remplaçons maintenant à la place и Les variables dont nous avons besoin sont :

Il ne reste plus qu'à trouver le vecteur , auquel cette probabilité est maximale. Pour maximiser une telle fonction, il convient d'en prendre d'abord un logarithme (le logarithme de la fonction atteindra un maximum au même point que la fonction elle-même) :

Ce qui revient à minimiser la fonction suivante :

D’ailleurs, cela s’appelle une méthode moindres carrés. Souvent, toutes les considérations ci-dessus sont omises et cette méthode est simplement utilisée.

Décomposition QR

Le minimum de la fonction ci-dessus peut être trouvé en trouvant le point auquel le gradient de cette fonction est nul. Et le dégradé s’écrira ainsi :

Décomposition QR est une méthode matricielle pour résoudre le problème de minimisation utilisée dans la méthode des moindres carrés. À cet égard, nous réécrivons l'équation sous forme matricielle :

On décompose donc la matrice aux matrices и et effectuer une série de transformations (l'algorithme de décomposition QR lui-même ne sera pas considéré ici, seulement son utilisation en relation avec la tâche à accomplir) :

Matrice est orthogonal. Cela nous permet de nous débarrasser du travail :

Et si tu remplaces sur , alors ça ira ... Étant donné que est une matrice triangulaire supérieure, elle ressemble à ceci :

Ce problème peut être résolu en utilisant la méthode de substitution. Élément est situé comme , élément précédent est situé comme et ainsi de suite.

Il convient de noter ici que la complexité de l'algorithme résultant en raison de l'utilisation de la décomposition QR est égale à . De plus, malgré le fait que l’opération de multiplication matricielle soit bien parallélisée, il n’est pas possible d’écrire une version distribuée efficace de cet algorithme.

Descente graduelle

Lorsqu'on parle de minimiser une fonction, il convient toujours de rappeler la méthode de descente de gradient (stochastique). Il s'agit d'une méthode de minimisation simple et efficace basée sur le calcul itératif du gradient d'une fonction en un point, puis sur son déplacement dans la direction opposée au gradient. Chacune de ces étapes rapproche la solution du minimum. Le dégradé est toujours le même :

Cette méthode est également bien parallélisée et distribuée en raison des propriétés linéaires de l'opérateur gradient. Notez que dans la formule ci-dessus, sous le signe somme se trouvent des termes indépendants. En d’autres termes, nous pouvons calculer le gradient indépendamment pour tous les indices du premier au , en parallèle, calculez le gradient pour les indices avec à . Ajoutez ensuite les dégradés obtenus. Le résultat de l'addition sera le même que si l'on calculait immédiatement le gradient des indices du premier au . Ainsi, si les données sont réparties sur plusieurs données, le gradient peut être calculé indépendamment sur chaque pièce, puis les résultats de ces calculs peuvent être additionnés pour obtenir le résultat final :

Du point de vue de la mise en œuvre, cela correspond au paradigme MapReduce. A chaque étape de descente de gradient, une tâche est envoyée à chaque nœud de données pour calculer le gradient, puis les gradients calculés sont rassemblés et le résultat de leur somme est utilisé pour améliorer le résultat.

Malgré la facilité de mise en œuvre et la capacité d'exécution dans le paradigme MapReduce, la descente de gradient présente également des inconvénients. En particulier, le nombre d’étapes nécessaires pour parvenir à la convergence est nettement plus élevé que celui d’autres méthodes plus spécialisées.

LSQR

LSQR est une autre méthode de résolution du problème, qui convient à la fois pour restaurer la régression linéaire et pour résoudre des systèmes d'équations linéaires. Sa principale caractéristique est de combiner les avantages des méthodes matricielles et d’une approche itérative. Des implémentations de cette méthode peuvent être trouvées dans les deux bibliothèques SciPyet MATLAB. Une description de cette méthode ne sera pas donnée ici (elle se trouve dans l'article LSQR : un algorithme pour les équations linéaires clairsemées et les moindres carrés clairsemés). Au lieu de cela, une approche sera démontrée pour adapter LSQR à l'exécution dans un environnement distribué.

La méthode LSQR est basée sur procédure de bidiagonalisation. Il s'agit d'une procédure itérative, chaque itération comprenant les étapes suivantes :


Mais si l'on suppose que la matrice est partitionné horizontalement, alors chaque itération peut être représentée comme deux étapes MapReduce. De cette manière, il est possible de minimiser les transferts de données lors de chaque itération (uniquement des vecteurs de longueur égale au nombre d'inconnues) :

C'est cette approche qui est utilisée lors de la mise en œuvre de la régression linéaire dans Apache Ignite ML.

Conclusion

Il existe de nombreux algorithmes de récupération par régression linéaire, mais tous ne peuvent pas être appliqués dans toutes les conditions. La décomposition QR est donc excellente pour une solution précise sur de petits ensembles de données. La descente de gradient est simple à mettre en œuvre et permet de trouver rapidement une solution approximative. Et LSQR combine les meilleures propriétés des deux algorithmes précédents, car il peut être distribué, converge plus rapidement que la descente de gradient et permet également un arrêt précoce de l'algorithme, contrairement à la décomposition QR, pour trouver une solution approximative.

Source: habr.com