来源：
线性回归是与数据分析相关的许多领域的基本算法之一。 原因是显而易见的。 这是一种非常简单且易于理解的算法，这使其广泛使用了数十年甚至数百年。 这个想法是，我们假设一个变量对一组其他变量的线性依赖，然后尝试恢复这种依赖。
但本文并不是关于使用线性回归来解决实际问题。 在这里，我们将考虑分布式算法实现其恢复的有趣特征，这是我们在编写机器学习模块时遇到的 。 即使您的数据分布在数千个节点上，一点点基础数学、机器学习和分布式计算也可以帮助您弄清楚如何执行线性回归。
我们在说什么？
我们面临着恢复线性依赖的任务。 作为输入数据，给出一组假定自变量的向量，每个向量都与因变量的某个值相关联。 该数据可以用两个矩阵的形式表示：
现在，由于依赖性是假设的，而且是线性的，我们将以矩阵乘积的形式写下我们的假设（为了简化记录，这里和下面假设方程的自由项隐藏在后面） ，以及矩阵的最后一列 包含单位）：
听起来很像线性方程组，不是吗？ 看起来，但很可能这样的方程组没有解。 其原因是噪声，几乎所有实际数据中都存在噪声。 另一个原因可能是缺乏线性相关性，这可以通过引入非线性依赖于原始变量的附加变量来解决。 考虑以下示例：
来源：
这是线性回归的一个简单示例，显示一个变量的关系（沿轴 ）来自另一个变量（沿轴 ）。 为了使与该示例相对应的线性方程组有解，所有点必须精确地位于同一条直线上。 但事实并非如此。 但由于噪声（或者因为线性关系的假设是错误的），它们并不精确地位于同一条直线上。 因此，为了从真实数据中恢复线性关系，通常需要引入一个假设：输入数据包含噪声，并且该噪声具有 。 您可以对其他类型的噪声分布做出假设，但在绝大多数情况下，考虑的是正态分布，这将进一步讨论。
最大似然法
因此，我们假设存在随机正态分布噪声。 遇到这种情况怎么办？ 对于数学中的这种情况，存在并且被广泛使用 。 简而言之，其本质在于选择 及其随后的最大化。
我们回到从具有正常噪声的数据恢复线性关系。 请注意，假设的线性关系是数学期望 现有的正态分布。 同时，概率为 根据可观察量的存在而呈现一种或另一种值 ，看起来像这样：
现在让我们代替 и 我们需要的变量是：
剩下的就是找到向量 ，此时此概率最大。 为了最大化这样的函数，首先取它的对数是很方便的（函数的对数将在与函数本身相同的点达到最大值）：
反过来，这又可以归结为最小化以下函数：
顺便说一句，这被称为方法 。 通常上述所有考虑因素都会被忽略，而简单地使用这种方法。
QR分解
通过找到该函数的梯度为零的点即可找到上述函数的最小值。 梯度将写成如下：
是最小二乘法中使用的用于求解最小化问题的矩阵方法。 对此，我们将方程改写为矩阵形式：
所以我们分解矩阵 到矩阵 и 并执行一系列变换（这里不考虑 QR 分解算法本身，只考虑它与手头任务相关的使用）：
矩阵 是正交的。 这让我们摆脱了工作 :
如果你更换 上 , 那么它将起作用 。 考虑到 是一个上三角矩阵，它看起来像这样：
这可以用替换法来解决。 元素 位于 , 前一个元素 位于 等。
这里值得注意的是，由于使用 QR 分解而产生的算法的复杂度等于 。 此外，尽管矩阵乘法运算具有良好的并行性，但不可能编写该算法的有效分布式版本。
梯度下降
当谈论最小化函数时，总是值得记住（随机）梯度下降的方法。 这是一种简单而有效的最小化方法，基于迭代计算函数在一点处的梯度，然后将其向与梯度相反的方向移动。 每一个这样的步骤都会使解决方案更接近最小值。 渐变看起来仍然相同：
由于梯度算子的线性特性，该方法也具有良好的并行性和分布式性。 注意，在上式中，和号下面有独立项。 换句话说，我们可以独立计算所有索引的梯度 从一开始到 ，与此并行，计算索引的梯度 对 。 然后添加所得的渐变。 加法的结果将与我们立即计算从第一个到第二个索引的梯度相同 。 因此，如果数据分布在几块数据中，则可以对每块数据独立计算梯度，然后将这些计算的结果相加，得到最终结果：
从实现的角度来看，这符合范式 。 在梯度下降的每一步，都会向每个数据节点发送一个任务来计算梯度，然后将计算出的梯度收集在一起，并将它们的总和结果用于改进结果。
尽管易于实现并且能够在 MapReduce 范例中执行，但梯度下降也有其缺点。 特别是，与其他更专业的方法相比，实现收敛所需的步骤数量明显更多。
最小二乘法
是解决该问题的另一种方法，它既适用于恢复线性回归，也适用于求解线性方程组。 其主要特点是结合了矩阵方法和迭代方法的优点。 该方法的实现可以在两个库中找到 和在 。 该方法这里不再赘述（可以在文章中找到） ）。 相反，我们将演示一种使 LSQR 适应分布式环境中执行的方法。
LSQR方法基于 。 这是一个迭代过程，每次迭代都包含以下步骤：
但如果我们假设矩阵 是水平分区的，那么每次迭代可以表示为两个MapReduce步骤。 通过这种方式，可以最大限度地减少每次迭代期间的数据传输（仅限长度等于未知数数量的向量）：
在实现线性回归时使用的就是这种方法 .
结论
线性回归恢复算法有很多，但并非所有算法都可以应用于所有情况。 因此，QR 分解非常适合小数据集的精确求解。 梯度下降实现起来很简单，可以让您快速找到近似解。 LSQR 结合了前两种算法的最佳特性，因为它可以是分布式的，与梯度下降相比收敛得更快，并且与 QR 分解不同，它还允许算法提前停止以找到近似解。
来源： habr.com