无法应用MapReduce模型的机器学习算法

Question

"Map-Reduce for Machine Learning on Multicore"这篇论文展示了10种可以从Map Reduce模型中受益的机器学习算法。关键点是“适合统计查询模型的任何算法都可以写成某种‘总和形式’”，而这些可以用总和形式表达的算法可以应用Map Reduce编程模型。

那些不能表示为总和形式的算法并不意味着它们不能应用Map Reduce模型。能否指出任何特定的机器学习算法，无法通过Map Reduce模型加速？

- user1841342

---

你可以将每个算法适配到MapReduce中，但这并不意味着它们能够高效地工作。 - Thomas Jungblut

是的，我知道我们可以将MapReduce应用于每个算法，但这并不意味着我们可以加速某些算法的性能。我上面提到的论文列出了10种算法，并展示了如何将原始算法转换为所谓的“求和形式”。然后，我们可以将MapReduce技术应用于求和形式。我想知道哪些算法无法从MapReduce模型中受益。 - user1841342

Answer 1

MapReduce在数据存在计算依赖关系时无法工作。这一限制使得难以表示基于结构化模型的算法。

因此，在面对大规模问题时，我们经常放弃丰富的结构化模型，而选择过于简单的方法，以适应MapReduce抽象2。

在机器学习社区中，许多算法在学习和推理过程中都会迭代地转换参数，例如置信传播、最大期望算法、梯度下降和吉布斯采样。这些算法会迭代地优化一组参数，直到满足某个终止条件2。

如果每次迭代都调用MapReduce，是的，我认为仍然可以加速计算。关键在于我们需要一个更好的抽象框架，以便能够接受数据的图形结构，表达复杂的调度或自动评估终止2。

顺便提一下，Graphlab 是受上述原因激励的替代方案之一2。

- greeness

---

感谢您的回答。因此，BP、EM、GD和Gibbs采样不能从map reduce模型中受益，对吗？据我所知，我列出的论文中的EM和批量梯度下降可以从map reduce中受益。作者说随机梯度下降不是这种情况，即使在大规模问题上，GSD通常比GD更有效。 - user1841342

是的，我同意EM和批量GD可以从map/reduce中受益。我想指出的是，有时候我们是否能从map/reduce中受益并不像拥有更好的抽象模型那样重要。请看我的倒数第二段。加速算法的能力并不意味着它是最好的模型。通过使用另一个模型，我们可能能够更显著地加速。 - greeness