<p><div><div><div><div data-show-faces="false" data-height="21" data-width="100" data-layout="button_count" data-send="true" data-href="https://www.r-bloggers.com/linear-regression-with-map-reduce/"></div></div><div></div></div><div></div></div>
<div>
(This article was first published on <strong><a href="https://freakonometrics.hypotheses.org/53269"> R-english – Freakonometrics</a></strong>, and kindly contributed to <a rel="nofollow" href="https://www.r-bloggers.com/">R-bloggers)</a> </div>
<p>Sometimes, with big data, matrices are too big to handle, and it is possible to use tricks to numerically still do the map. <a rel="nofollow" href="https://en.wikipedia.org/wiki/MapReduce" target="_blank">Map-Reduce</a> is one of those. With several cores, it is possible to split the problem, to map on each machine, and then to agregate it back at the end.</p>
<p>Consider the case of the linear regression, <img alt="\mathbf{y}=\mathbf{X}\mathbf{\beta}+\mathbf{\varepsilon}" title="\mathbf{y}=\mathbf{X}\mathbf{\beta}+\mathbf{\varepsilon}" src="https://s0.wp.com/latex.php?latex=%5Cmathbf%7By%7D%3D%5Cmathbf%7BX%7D%5Cmathbf%7B%5Cbeta%7D%2B%5Cmathbf%7B%5Cvarepsilon%7D&bg=ffffff&fg=000&s=0" class="latex"> (with classical matrix notations). The OLS estimate of <img alt="\mathbf{\beta}" title="\mathbf{\beta}" src="https://s0.wp.com/latex.php?latex=%5Cmathbf%7B%5Cbeta%7D&bg=ffffff&fg=000&s=0" class="latex"> is <img alt="\widehat{\mathbf{\beta}}=[\mathbf{X}^T\mathbf{X}]^{-1}\mathbf{X}^T\mathbf{y}" title="\widehat{\mathbf{\beta}}=[\mathbf{X}^T\mathbf{X}]^{-1}\mathbf{X}^T\mathbf{y}" src="https://s0.wp.com/latex.php?latex=%5Cwidehat%7B%5Cmathbf%7B%5Cbeta%7D%7D%3D%5B%5Cmathbf%7BX%7D%5ET%5Cmathbf%7BX%7D%5D%5E%7B-1%7D%5Cmathbf%7BX%7D%5ET%5Cmathbf%7By%7D&bg=ffffff&fg=000&s=0" class="latex">. To illustrate, consider a not too big dataset, and run some regression.</p>
<div><table><tr><td><pre>1
2
3
4
5
6
7
8
9
</pre></td><td><pre><span>lm</span><span>(</span><span>dist</span>~speed,<span>data</span><span>=</span><span>cars</span><span>)</span>$coefficients
<span>(</span>Intercept<span>)</span>       speed 
 <span>-</span><span>17.579095</span>    <span>3.932409</span>
y<span>=</span><span>cars</span>$dist
X<span>=</span><span>cbind</span><span>(</span><span>1</span>,<span>cars</span>$speed<span>)</span>
<span>solve</span><span>(</span><span>crossprod</span><span>(</span>X,X<span>)</span><span>)</span><span>%*%</span><span>crossprod</span><span>(</span>X,y<span>)</span>
           <span>[</span>,<span>1</span><span>]</span>
<span>[</span><span>1</span>,<span>]</span> <span>-</span><span>17.579095</span>
<span>[</span><span>2</span>,<span>]</span>   <span>3.932409</span></pre></td></tr></table></div>
<p>How is this computed in R? Actually, it is based on the <a rel="nofollow" href="https://en.wikipedia.org/wiki/QR_decomposition" target="_blank">QR decomposition</a> of <img alt="\mathbf{X}" title="\mathbf{X}" src="https://s0.wp.com/latex.php?latex=%5Cmathbf%7BX%7D&bg=ffffff&fg=000&s=0" class="latex">, <img alt="\mathbf{X}=\mathbf{Q}\mathbf{R}" title="\mathbf{X}=\mathbf{Q}\mathbf{R}" src="https://s0.wp.com/latex.php?latex=%5Cmathbf%7BX%7D%3D%5Cmathbf%7BQ%7D%5Cmathbf%7BR%7D&bg=ffffff&fg=000&s=0" class="latex">, where <img alt="\mathbf{Q}" title="\mathbf{Q}" src="https://s0.wp.com/latex.php?latex=%5Cmathbf%7BQ%7D&bg=ffffff&fg=000&s=0" class="latex"> is an orthogonal matrix (ie <img alt="\mathbf{Q}^T\mathbf{Q}=\mathbb{I}" title="\mathbf{Q}^T\mathbf{Q}=\mathbb{I}" src="https://s0.wp.com/latex.php?latex=%5Cmathbf%7BQ%7D%5ET%5Cmathbf%7BQ%7D%3D%5Cmathbb%7BI%7D&bg=ffffff&fg=000&s=0" class="latex">). Then <img alt="\widehat{\mathbf{\beta}}=[\mathbf{X}^T\mathbf{X}]^{-1}\mathbf{X}^T\mathbf{y}=\mathbf{R}^{-1}\mathbf{Q}^T\mathbf{y}" title="\widehat{\mathbf{\beta}}=[\mathbf{X}^T\mathbf{X}]^{-1}\mathbf{X}^T\mathbf{y}=\mathbf{R}^{-1}\mathbf{Q}^T\mathbf{y}" src="https://s0.wp.com/latex.php?latex=%5Cwidehat%7B%5Cmathbf%7B%5Cbeta%7D%7D%3D%5B%5Cmathbf%7BX%7D%5ET%5Cmathbf%7BX%7D%5D%5E%7B-1%7D%5Cmathbf%7BX%7D%5ET%5Cmathbf%7By%7D%3D%5Cmathbf%7BR%7D%5E%7B-1%7D%5Cmathbf%7BQ%7D%5ET%5Cmathbf%7By%7D&bg=ffffff&fg=000&s=0" class="latex"></p>
<div><table><tr><td><pre>1
2
3
4
</pre></td><td><pre><span>solve</span><span>(</span><span>qr.<span>R</span></span><span>(</span><span>qr</span><span>(</span><span>as.<span>matrix</span></span><span>(</span>X<span>)</span><span>)</span><span>)</span><span>)</span> <span>%*%</span> <span>t</span><span>(</span><span>qr.<span>Q</span></span><span>(</span><span>qr</span><span>(</span><span>as.<span>matrix</span></span><span>(</span>X<span>)</span><span>)</span><span>)</span><span>)</span> <span>%*%</span> y
           <span>[</span>,<span>1</span><span>]</span>
<span>[</span><span>1</span>,<span>]</span> <span>-</span><span>17.579095</span>
<span>[</span><span>2</span>,<span>]</span>   <span>3.932409</span></pre></td></tr></table></div>
<p>So far, so good, we get the same output. Now, what if we want to parallelise computations. Actually, it is possible.</p>
<p>Consider <img alt="m" title="m" src="https://s0.wp.com/latex.php?latex=m&bg=ffffff&fg=000&s=0" class="latex"> blocks</p>
<div><table><tr><td><pre>1
</pre></td><td><pre>m <span>=</span> <span>5</span></pre></td></tr></table></div>
<p>and split vectors and matrices<br>
<img alt="\mathbf{y}=\left[\begin{matrix}\mathbf{y}_1\\\mathbf{y}_2\\\vdots \\\mathbf{y}_m\end{matrix}\right]" title="\mathbf{y}=\left[\begin{matrix}\mathbf{y}_1\\\mathbf{y}_2\\\vdots \\\mathbf{y}_m\end{matrix}\right]" src="https://s0.wp.com/latex.php?latex=%5Cmathbf%7By%7D%3D%5Cleft%5B%5Cbegin%7Bmatrix%7D%5Cmathbf%7By%7D_1%5C%5C%5Cmathbf%7By%7D_2%5C%5C%5Cvdots+%5C%5C%5Cmathbf%7By%7D_m%5Cend%7Bmatrix%7D%5Cright%5D&bg=ffffff&fg=000&s=0" class="latex"> and <img alt="\mathbf{X}=\left[\begin{matrix}\mathbf{X}_1\\\mathbf{X}_2\\\vdots\\\mathbf{X}_m\end{matrix}\right]=\left[\begin{matrix}\mathbf{Q}_1^{(1)}\mathbf{R}_1^{(1)}\\\mathbf{Q}_2^{(1)}\mathbf{R}_2^{(1)}\\\vdots \\\mathbf{Q}_m^{(1)}\mathbf{R}_m^{(1)}\end{matrix}\right]" title="\mathbf{X}=\left[\begin{matrix}\mathbf{X}_1\\\mathbf{X}_2\\\vdots\\\mathbf{X}_m\end{matrix}\right]=\left[\begin{matrix}\mathbf{Q}_1^{(1)}\mathbf{R}_1^{(1)}\\\mathbf{Q}_2^{(1)}\mathbf{R}_2^{(1)}\\\vdots \\\mathbf{Q}_m^{(1)}\mathbf{R}_m^{(1)}\end{matrix}\right]" src="https://s0.wp.com/latex.php?latex=%5Cmathbf%7BX%7D%3D%5Cleft%5B%5Cbegin%7Bmatrix%7D%5Cmathbf%7BX%7D_1%5C%5C%5Cmathbf%7BX%7D_2%5C%5C%5Cvdots%5C%5C%5Cmathbf%7BX%7D_m%5Cend%7Bmatrix%7D%5Cright%5D%3D%5Cleft%5B%5Cbegin%7Bmatrix%7D%5Cmathbf%7BQ%7D_1%5E%7B%281%29%7D%5Cmathbf%7BR%7D_1%5E%7B%281%29%7D%5C%5C%5Cmathbf%7BQ%7D_2%5E%7B%281%29%7D%5Cmathbf%7BR%7D_2%5E%7B%281%29%7D%5C%5C%5Cvdots+%5C%5C%5Cmathbf%7BQ%7D_m%5E%7B%281%29%7D%5Cmathbf%7BR%7D_m%5E%7B%281%29%7D%5Cend%7Bmatrix%7D%5Cright%5D&bg=ffffff&fg=000&s=0" class="latex"><br>
To split vectors and matrices, use (eg)</p>
<div><table><tr><td><pre>1
2
3
4
</pre></td><td><pre>Xlist <span>=</span> <span>list</span><span>(</span><span>)</span>
<span>for</span><span>(</span>j <span>in</span> <span>1</span><span>:</span>m<span>)</span> Xlist<span>[</span><span>[</span>j<span>]</span><span>]</span> <span>=</span> X<span>[</span><span>(</span>j<span>-</span><span>1</span><span>)</span><span>*</span><span>10</span><span>+</span><span>1</span><span>:</span><span>10</span>,<span>]</span>
ylist <span>=</span> <span>list</span><span>(</span><span>)</span>
<span>for</span><span>(</span>j <span>in</span> <span>1</span><span>:</span>m<span>)</span> ylist<span>[</span><span>[</span>j<span>]</span><span>]</span> <span>=</span> y<span>[</span><span>(</span>j<span>-</span><span>1</span><span>)</span><span>*</span><span>10</span><span>+</span><span>1</span><span>:</span><span>10</span><span>]</span></pre></td></tr></table></div>
<p>and get small QR recomposition (per subset)</p>
<div><table><tr><td><pre>1
2
</pre></td><td><pre>QR1 <span>=</span> <span>list</span><span>(</span><span>)</span>
<span>for</span><span>(</span>j <span>in</span> <span>1</span><span>:</span>m<span>)</span> QR1<span>[</span><span>[</span>j<span>]</span><span>]</span> <span>=</span> <span>list</span><span>(</span>Q<span>=</span><span>qr.<span>Q</span></span><span>(</span><span>qr</span><span>(</span><span>as.<span>matrix</span></span><span>(</span>Xlist<span>[</span><span>[</span>j<span>]</span><span>]</span><span>)</span><span>)</span><span>)</span>,R<span>=</span><span>qr.<span>R</span></span><span>(</span><span>qr</span><span>(</span><span>as.<span>matrix</span></span><span>(</span>Xlist<span>[</span><span>[</span>j<span>]</span><span>]</span><span>)</span><span>)</span><span>)</span><span>)</span></pre></td></tr></table></div>
<p>Consider the QR decomposition of <img alt="\mathbf{R}^{(1)}" title="\mathbf{R}^{(1)}" src="https://s0.wp.com/latex.php?latex=%5Cmathbf%7BR%7D%5E%7B%281%29%7D&bg=ffffff&fg=000&s=0" class="latex"> which is the first step of the reduce part<img alt="\mathbf{R}^{(1)}=\left[\begin{matrix}\mathbf{R}_1^{(1)}\\\mathbf{R}_2^{(1)}\\\vdots \\\mathbf{R}_m^{(1)}\end{matrix}\right]=\mathbf{Q}^{(2)}\mathbf{R}^{(2)}" title="\mathbf{R}^{(1)}=\left[\begin{matrix}\mathbf{R}_1^{(1)}\\\mathbf{R}_2^{(1)}\\\vdots \\\mathbf{R}_m^{(1)}\end{matrix}\right]=\mathbf{Q}^{(2)}\mathbf{R}^{(2)}" src="https://s0.wp.com/latex.php?latex=%5Cmathbf%7BR%7D%5E%7B%281%29%7D%3D%5Cleft%5B%5Cbegin%7Bmatrix%7D%5Cmathbf%7BR%7D_1%5E%7B%281%29%7D%5C%5C%5Cmathbf%7BR%7D_2%5E%7B%281%29%7D%5C%5C%5Cvdots+%5C%5C%5Cmathbf%7BR%7D_m%5E%7B%281%29%7D%5Cend%7Bmatrix%7D%5Cright%5D%3D%5Cmathbf%7BQ%7D%5E%7B%282%29%7D%5Cmathbf%7BR%7D%5E%7B%282%29%7D&bg=ffffff&fg=000&s=0" class="latex">where<img alt="\mathbf{Q}^{(2)}=\left[\begin{matrix}\mathbf{Q}^{(2)}_1\\\mathbf{Q}^{(2)}_2\\\vdots\\\mathbf{Q}^{(2)}_m\end{matrix}\right]" title="\mathbf{Q}^{(2)}=\left[\begin{matrix}\mathbf{Q}^{(2)}_1\\\mathbf{Q}^{(2)}_2\\\vdots\\\mathbf{Q}^{(2)}_m\end{matrix}\right]" src="https://s0.wp.com/latex.php?latex=%5Cmathbf%7BQ%7D%5E%7B%282%29%7D%3D%5Cleft%5B%5Cbegin%7Bmatrix%7D%5Cmathbf%7BQ%7D%5E%7B%282%29%7D_1%5C%5C%5Cmathbf%7BQ%7D%5E%7B%282%29%7D_2%5C%5C%5Cvdots%5C%5C%5Cmathbf%7BQ%7D%5E%7B%282%29%7D_m%5Cend%7Bmatrix%7D%5Cright%5D&bg=ffffff&fg=000&s=0" class="latex"></p>
<div><table><tr><td><pre>1
2
3
4
5
6
</pre></td><td><pre>R1 <span>=</span> QR1<span>[</span><span>[</span><span>1</span><span>]</span><span>]</span>$R
<span>for</span><span>(</span>j <span>in</span> <span>2</span><span>:</span>m<span>)</span> R1 <span>=</span> <span>rbind</span><span>(</span>R1,QR1<span>[</span><span>[</span>j<span>]</span><span>]</span>$R<span>)</span>
Q1 <span>=</span> <span>qr.<span>Q</span></span><span>(</span><span>qr</span><span>(</span><span>as.<span>matrix</span></span><span>(</span>R1<span>)</span><span>)</span><span>)</span>
R2 <span>=</span> <span>qr.<span>R</span></span><span>(</span><span>qr</span><span>(</span><span>as.<span>matrix</span></span><span>(</span>R1<span>)</span><span>)</span><span>)</span>
Q2list<span>=</span><span>list</span><span>(</span><span>)</span>
<span>for</span><span>(</span>j <span>in</span> <span>1</span><span>:</span>m<span>)</span> Q2list<span>[</span><span>[</span>j<span>]</span><span>]</span> <span>=</span> Q1<span>[</span><span>(</span>j<span>-</span><span>1</span><span>)</span><span>*</span><span>2</span><span>+</span><span>1</span><span>:</span><span>2</span>,<span>]</span></pre></td></tr></table></div>
<p>Define – as step 2 of the reduce part<img alt="\mathbf{Q}^{(3)}_j=\mathbf{Q}^{(2)}_j\mathbf{Q}^{(1)}_j" title="\mathbf{Q}^{(3)}_j=\mathbf{Q}^{(2)}_j\mathbf{Q}^{(1)}_j" src="https://s0.wp.com/latex.php?latex=%5Cmathbf%7BQ%7D%5E%7B%283%29%7D_j%3D%5Cmathbf%7BQ%7D%5E%7B%282%29%7D_j%5Cmathbf%7BQ%7D%5E%7B%281%29%7D_j&bg=ffffff&fg=000&s=0" class="latex"><br>
and<img alt="\mathbf{V}_j=\mathbf{Q}^{(3)T}_j\mathbf{y}_j" title="\mathbf{V}_j=\mathbf{Q}^{(3)T}_j\mathbf{y}_j" src="https://s0.wp.com/latex.php?latex=%5Cmathbf%7BV%7D_j%3D%5Cmathbf%7BQ%7D%5E%7B%283%29T%7D_j%5Cmathbf%7By%7D_j&bg=ffffff&fg=000&s=0" class="latex"></p>
<div><table><tr><td><pre>1
2
3
4
</pre></td><td><pre>Q3list <span>=</span> <span>list</span><span>(</span><span>)</span>
<span>for</span><span>(</span>j <span>in</span> <span>1</span><span>:</span>m<span>)</span> Q3list<span>[</span><span>[</span>j<span>]</span><span>]</span> <span>=</span> QR1<span>[</span><span>[</span>j<span>]</span><span>]</span>$Q <span>%*%</span> Q2list<span>[</span><span>[</span>j<span>]</span><span>]</span>
Vlist <span>=</span> <span>list</span><span>(</span><span>)</span>
<span>for</span><span>(</span>j <span>in</span> <span>1</span><span>:</span>m<span>)</span> Vlist<span>[</span><span>[</span>j<span>]</span><span>]</span> <span>=</span> <span>t</span><span>(</span>Q3list<span>[</span><span>[</span>j<span>]</span><span>]</span><span>)</span> <span>%*%</span> ylist<span>[</span><span>[</span>j<span>]</span><span>]</span></pre></td></tr></table></div>
<p>and finally set – as the step 3 of the reduce part<img alt="\widehat{\mathbf{\beta}}=[\mathbf{R}^{(2)}]^{-1}\sum_{j=1}^m\mathbf{V}_j" title="\widehat{\mathbf{\beta}}=[\mathbf{R}^{(2)}]^{-1}\sum_{j=1}^m\mathbf{V}_j" src="https://s0.wp.com/latex.php?latex=%5Cwidehat%7B%5Cmathbf%7B%5Cbeta%7D%7D%3D%5B%5Cmathbf%7BR%7D%5E%7B%282%29%7D%5D%5E%7B-1%7D%5Csum_%7Bj%3D1%7D%5Em%5Cmathbf%7BV%7D_j&bg=ffffff&fg=000&s=0" class="latex"></p>
<div><table><tr><td><pre>1
2
3
4
5
6
</pre></td><td><pre>sumV <span>=</span> Vlist<span>[</span><span>[</span><span>1</span><span>]</span><span>]</span>
<span>for</span><span>(</span>j <span>in</span> <span>2</span><span>:</span>m<span>)</span> sumV <span>=</span> sumV<span>+</span>Vlist<span>[</span><span>[</span>j<span>]</span><span>]</span>
<span>solve</span><span>(</span>R2<span>)</span> <span>%*%</span> sumV
           <span>[</span>,<span>1</span><span>]</span>
<span>[</span><span>1</span>,<span>]</span> <span>-</span><span>17.579095</span>
<span>[</span><span>2</span>,<span>]</span>   <span>3.932409</span></pre></td></tr></table></div>
<p>It looks like we’ve been able to parallelise our linear regression…</p>
	<p>
<div>
<div>To <strong>leave a comment</strong> for the author, please follow the link and comment on their blog: <strong><a href="https://freakonometrics.hypotheses.org/53269"> R-english – Freakonometrics</a></strong>.</div>
<hr>
<a rel="nofollow" href="https://www.r-bloggers.com/">R-bloggers.com</a> offers <strong><a rel="nofollow" href="https://feedburner.google.com/fb/a/mailverify?uri=RBloggers">daily e-mail updates</a></strong> about <a rel="nofollow" href="https://www.r-project.org/" title="The R Project for Statistical Computing">R</a> news and <a rel="nofollow" href="https://www.r-bloggers.com/search/tutorial" title="R tutorials">tutorials</a> on topics such as: <a rel="nofollow" href="https://www.r-bloggers.com/search/data%20science" title="Data science">Data science</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/Big%20Data" title="Big Data">Big Data, <a rel="nofollow" href="https://www.r-users.com/" title="R jobs">R jobs</a>, visualization (<a rel="nofollow" href="https://www.r-bloggers.com/search/ggplot2" title="ggplot and ggplot2 tutorials">ggplot2</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/boxplot" title="Boxplots using lattice and ggplot2 tutorials">Boxplots</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/map" title="Maps and gis">maps</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/animation" title="Animation in R">animation</a>), programming (<a rel="nofollow" href="https://www.r-bloggers.com/search/RStudio" title="RStudio IDE for R">RStudio</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/sweave" title="Sweave and literate programming">Sweave</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/LaTeX" title="LaTeX in R">LaTeX</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/SQL" title="SQL and databases">SQL</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/eclipse" title="Eclipse IDE for R">Eclipse</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/git" title="git and github, Version Control System">git</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/hadoop" title="Large data in R using Hadoop">hadoop</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/Web+Scraping" title="Web Scraping of google, facebook, yahoo, twitter and more using R">Web Scraping</a>) statistics (<a rel="nofollow" href="https://www.r-bloggers.com/search/regression" title="Regressions and ANOVA analysis tutorials">regression</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/PCA" title="principal component analysis tutorial">PCA</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/time+series" title="Time series">time series</a>, <a rel="nofollow" href="https://www.r-bloggers.com/search/trading" title="finance trading">trading</a>) and more...
<img width="1" alt="" src="http://feeds.feedburner.com/~r/RBloggers/~4/3m3cRUf_uKo" height="1"></a></div>