所有统计算法都能使用Map Reduce框架并行化吗？

Question

任何统计学习算法(线性/logistic回归、支持向量机、神经网络、随机森林)都可以在地图缩减框架内实现，这是正确的吗？还是有限制？

我想可能有一些算法不可能并行化？

Answer 1

事实上，有：

• 梯度提升是通过构造顺序进行的，因此并行化并不是真正可行的。
  • 广义线性模型同时需要所有数据，尽管从技术上讲，您可以并行化一些内部线性代数螺母和螺栓。
  • 支持向量机

Answer 2

我建议您可以在Map中实现几乎任何类型的数据处理，只要有足够的时间对其进行编码，但是您将得到的并行化的程度将取决于您的数据是什么以及您要对其做什么。

我可以想象一个简单的场景，即并行化将大大减少。例如，如果连接键(1、2、3和4)均匀分布在映射节点上，则具有4个映射器节点和4个减法器节点的简单连接任务将高度并行化，并且每个(4) -4减法器的数目相同，然后每个连接键将得到相同的工作份额：

Mapper    1 2 3 4   |   1 2 3 4   |   1 2 3 4   |   1 2 3 4
             / \         / \            / \           / \
            v   v       v   v          v   v         v   v

Reducer   1 1 1 1   |   2 2 2 2   |  3 3 3 3    |   4 4 4 4

但是，如果您遇到的情况是，大多数连接键是相同的(例如几乎所有的1s)，处理1s的减速机将被淹没：

Mapper    1 1 1 1   |   1 1 1 1   |   1 1 1 1   |   1 1 1 2
             /          /            /             /     /
            v          v            v             v     v

Reducer   1 1 1 1 1 1 1 1 1 1 1 1 1 1 1  |  2  |  nothing!  |  nothing!

因为1减速器完全淹没，而其他人什么都不做，你将失去你的大部分并行，而Hadoop停止和等待还原机完成。

警告:可能有更复杂的Map Reduce实现来处理这种问题，我只知道Hadoop的基础知识。

另外，我知道这与统计学习算法无关(我几乎一无所知)，但我认为这个原理仍然是正确的--有些算法或数据就是不能划分成高度并行的子任务。

Answer 3

不是的。

按定义，地图还原一次只在一个记录上工作。

因此，如果不滥用编程模型，就无法计算距离/相似矩阵。像支持向量机这样的方法确实需要两两相似。

然而，这种滥用是非常普遍的(这就是为什么地图减少是死亡的原因)。最简单的是，您可以将每个对象映射到键0，并在“还原器”中完成所有的工作。更聪明的方法将数据划分为k个分区，这样它们至少可以并行运行一些工作。

但所有这些方法都是骇人听闻的，它们围绕着为地图减少而做出的深思熟虑的设计决策进行黑客攻击:在地图减少中，必须独立处理每一条记录，以使平台能够自动优化并行性和恢复。在上面的黑客中，利用映射阶段将数据分割成手动选择的并行，而减速器则是简单的并行作业。它不再是mapreduce，而是分区数据上并行编程的抽象模型。

在所有早期的炒作之后，mapreduce现在已经死了。Apache等工具不再接受mapreduce，而是希望您继续使用更灵活的、不需要这种恶意攻击的羊毛衫。