來源：
線性迴歸是與資料分析相關的許多領域的基本演算法之一。 原因是顯而易見的。 這是一種非常簡單且易於理解的演算法，這使其廣泛使用了數十年甚至數百年。 這個想法是，我們假設一個變數對一組其他變數的線性依賴，然後嘗試恢復這種依賴。
但本文並不是關於使用線性迴歸來解決實際問題。 在這裡，我們將考慮分散式演算法實現其恢復的有趣特徵，這是我們在編寫機器學習模組時遇到的 。 即使資料分佈在數千個節點上，一點基礎數學、機器學習和分散式運算也可以幫助您弄清楚如何執行線性迴歸。
我們在說啥啊？
我們面臨著恢復線性依賴的任務。 作為輸入數據，給出一組假定自變數的向量，每個向量都與因變數的某個值相關聯。 此數據可以用兩個矩陣的形式表示：
現在，由於依賴性是假設的，而且是線性的，我們將以矩陣乘積的形式寫下我們的假設（為了簡化記錄，這裡和下面假設方程式的自由項隱藏在後面） ，以及矩陣的最後一列 包含單位）：
聽起來很像線性方程組，不是嗎？ 看起來，但很可能這樣的方程組沒有解。 原因是噪聲，幾乎所有實際資料中都存在噪聲。 另一個原因可能是缺乏線性相關性，這可以透過引入非線性依賴原始變數的附加變數來解決。 考慮以下範例：
來源：
這是線性迴歸的一個簡單範例，顯示一個變數的關係（沿著軸 ）來自另一個變數（沿軸 ）。 為了使與該範例相對應的線性方程組有解，所有點必須精確地位於同一條直線上。 但事實並非如此。 但由於雜訊（或因為線性關係的假設是錯誤的），它們並不精確地位於同一條直線上。 因此，為了從真實資料中恢復線性關係，通常需要引入一個假設：輸入資料包含噪聲，並且該噪聲具有 。 您可以對其他類型的雜訊分佈做出假設，但在絕大多數情況下，考慮的是常態分佈，這將進一步討論。
最大似然法
因此，我們假設存在隨機常態分佈雜訊。 遇到這種情況怎麼辦？ 對於數學中的這種情況，存在並且被廣泛使用 。 簡而言之，其本質在於選擇 及其隨後的最大化。
我們回到從具有正常雜訊的資料恢復線性關係。 請注意，假設的線性關係是數學期望 現有的常態分佈。 同時，機率為 根據可觀察量的存在而呈現一種或另一種值 ， 如下：
現在讓我們來代替 и 我們需要的變數是：
剩下的就是找到向量 ，此時此機率最大。 為了最大化這樣的函數，首先取它的對數是很方便的（函數的對數將在與函數本身相同的點達到最大值）：
反過來，這又可以歸結為最小化以下函數：
順便說一句，這被稱為方法 。 通常上述所有考慮因素都會被忽略，而簡單地使用這種方法。
QR分解
透過找到函數的梯度為零的點即可找到上述函數的最小值。 梯度將寫成如下：
是最小平方法中使用的用於求解最小化問題的矩陣方法。 對此，我們將方程式改寫為矩陣形式：
所以我們分解矩陣 到矩陣 и 並執行一系列變換（這裡不考慮 QR 分解演算法本身，只考慮它與手邊任務相關的使用）：
矩陣 是正交的。 這讓我們擺脫了工作 :
如果你更換 上 ，然後就會解決 。 考慮到 是一個上三角矩陣，它看起來像這樣：
這可以用替換法來解決。 元素 位於 , 前一個元素 位於 等。
這裡值得注意的是，由於使用 QR 分解而產生的演算法的複雜度等於 。 此外，儘管矩陣乘法運算具有良好的平行性，但不可能編寫該演算法的有效分散式版本。
梯度下降
當談論最小化函數時，總是值得記住（隨機）梯度下降的方法。 這是一種簡單而有效的最小化方法，基於迭代計算函數在一點處的梯度，然後將其向與梯度相反的方向移動。 每一個這樣的步驟都會讓解決方案更接近最小值。 漸層看起來仍然相同：
由於梯度算子的線性特性，此方法也具有良好的平行性和分佈式性。 請注意，在上式中，和號下方有獨立項。 換句話說，我們可以獨立計算所有索引的梯度 從一開始到 ，與此並行，計算索引的梯度 對 。 然後加入所得的漸層。 加法的結果將與我們立即計算從第一個到第二個索引的梯度相同 。 因此，如果資料分佈在幾塊資料中，則可以對每塊資料獨立計算梯度，然後將這些計算的結果相加，得到最終結果：
從實現的角度來看，這符合範式 。 在梯度下降的每一步，都會向每個資料節點發送一個任務來計算梯度，然後將計算的梯度收集在一起，並將它們的總和結果用於改進結果。
儘管易於實現並且能夠在 MapReduce 範例中執行，但梯度下降也有其缺點。 特別是，與其他更專業的方法相比，實現收斂所需的步驟數量明顯更多。
最小平方法
是解決此問題的另一種方法，它既適用於恢復線性迴歸，也適用於求解線性方程組。 其主要特徵是結合了矩陣方法和迭代方法的優點。 該方法的實作可以在兩個庫中找到 所以 。 該方法這裡不再贅述（可在文章中找到） ）。 相反，我們將示範一種使 LSQR 適應分散式環境中執行的方法。
LSQR方法是基於 。 這是一個迭代過程，每次迭代都包含以下步驟：
但如果我們假設矩陣 是水平分區的，那麼每次迭代可以表示為兩個MapReduce步驟。 透過這種方式，可以最大限度地減少每次迭代期間的資料傳輸（僅限長度等於未知數數量的向量）：
在實現線性迴歸時使用的就是這種方法 .
結論
線性迴歸恢復演算法有很多，但並非所有演算法都可以應用於所有情況。 因此，QR 分解非常適合小資料集的精確求解。 梯度下降實現起來很簡單，可以讓您快速找到近似解。 LSQR 結合了前兩種演算法的最佳特性，因為它可以是分佈式的，與梯度下降相比收斂得更快，並且與 QR 分解不同，它還允許演算法提前停止以找到近似解。
來源： www.habr.com