Réponse courte:
Oui, une régression linéaire parallèle a été effectuée. Par exemple, Xiangrui Meng et al. (2016) pour Machine Learning dans Apache Spark. La façon dont cela fonctionne utilise la descente de gradient stochastique (SGD). Dans la section 3, principales fonctionnalités, l'auteur a mentionné:
Les modèles linéaires généralisés sont appris via des algorithmes d'optimisation qui parallélisent le calcul du gradient, en utilisant des bibliothèques d'algèbre linéaire rapide basées sur C ++ pour les calculs des travailleurs.
Un exemple sur la façon dont SGD fonctionne peut être trouvé dans ma réponse ici: Comment la descente de gradient stochastique pourrait-elle gagner du temps par rapport à la descente de gradient standard?
Longue réponse:
Remarque, la notation n'est pas cohérente avec le lien que j'ai fourni, je pense que la notation matricielle est meilleure dans cette question.
Pour faire une régression linéaire, nous essayons de faire
minimiser ∥ X β- y∥2
Le dérivé est
2 XT( Xβ- y)
Dans les petits paramètres de données, nous pouvons définir la dérivée sur et la résoudre directement. (par exemple, décomposition QR en R.) Dans les paramètres de Big Data, la matrice de données est trop volumineuse pour être stockée en mémoire et peut être difficile à résoudre directement. (Je ne sais pas comment faire la décomposition QR ou la décomposition Cholesky pour les matrices énormes).0X
Une façon de paralléliser cela est d'essayer d'utiliser une méthode itérative: la descente du gradient stochastique, où nous pouvons approximer le gradient en utilisant un sous-ensemble des données. (Si nous utilisons , pour représenter un sous-ensemble des données, le gradient peut être approximé par , et nous pouvons mettre à jour avec le gradient approximatif).Xsys2 XTs( Xsβ- ys)β
De plus, pour la statistique , nous pouvons calculer pour toutes les données en parallèle ou l'approximer en utilisant un sous-ensemble des données.R2R2
Intuition sur son fonctionnement (paradigme mapreduce):
Je continue à dire approximation en utilisant un sous-ensemble; l'intuition pour laquelle cela fonctionne peut être décrite dans l'exemple suivant: supposons que j'ai 100 milliards de points de données et que nous voulons calculer la moyenne de tous les points de données. Supposons que la réalisation d'une telle opération prenne beaucoup de temps et, en outre, que l'ensemble des données ne puisse pas être stocké en mémoire.
Ce que nous pouvons faire, c'est simplement prendre un sous-ensemble, disons 1 milliard d'articles, et calculer la moyenne de ceux-ci. L'approximation ainsi produite ne doit pas être éloignée de la vérité (c'est-à-dire en utilisant l'ensemble des données).
Pour paralléliser, nous pouvons utiliser 100 ordinateurs, chacun d'eux prenant un sous-ensemble différent du milliard de points de données et calculant la moyenne de ceux-ci. (Communément appelé étape MAP). Enfin, exécutez une autre moyenne sur ces 100 nombres (alias l'étape REDUCE).
Notez que le «paradigme mapreduce» fonctionnerait bien dans certains cas, mais pas bien dans d'autres. Pour l'exemple, l'opération "moyenne" mentionnée plus haut est très simple, car nous savons , ( en supposant que la longueur de et est la même). Pour certaines méthodes itératives, c'est-à-dire que l'itération actuelle dépend des résultats de l'itération précédente, il est difficile de paralléliser. La descente de gradient stochastique résout ce problème en approximant le gradient à l'aide d'un sous-ensemble de données. Et les détails peuvent être trouvés dans la réponse de @ user20160.moyenne ( < x , y> ) = moyenne ( x ) + moyenne (y)Xy
Les références:
Xiangrui Meng et al. (2016) . MLlib: Apprentissage automatique dans Apache Spark
Long, long, avant que la carte ne se réduise, j'ai résolu cela. Ci-dessous se réfère à un ancien article à moi dans Journal of Econometrics 1980. C'était pour la vraisemblance maximale non linéaire parallèle et fonctionnerait pour M-estimation.
La méthode est exacte pour les régressions. Fractionner les données en k sous-ensembles sur k processeurs / unités (pourrait également être fait de manière séquentielle.) Est-ce que k régressions conservent les coefficients de régression et la matrice X'X pour chacun. Appelons ces b1, ..., bk et W1, ..., Wk respectivement alors les coefficients de régression globaux sont donnés par b = inverse (W1 + .. + Wk) * (W1 * b1 + ... + Wk * bk) un a besoin d'un autre passage à travers les données pour calculer les résidus en utilisant b pour les paramètres pour obtenir sigma ^ 2 la variance d'erreur estimée, R ^ 2 F globale et similaires. Alors la matrice de covariance de b est donnée exactement par sigma ^ 2 (inverse (W1 + .. + Wk)). Ci-dessus * indique une multiplication matricielle.
https://www.sciencedirect.com/science/article/pii/0304407680900950
la source