haskell - Monoid 如何协助并行训练？

Question

HLearn 的自述文件指出 Monoid 类型类用于并行批量训练。我在几个文件中看到了 trainMonoid ，但我很难剖析这个巨大的代码库。有人可以用初学者友好的术语解释它是如何工作的吗？我猜这与关联性属性有某种关系。

Answer 1

this article中有解释它链接在您在问题中链接的页面中。由于您想要初学者友好的描述，因此我将向您提供我在阅读本文后所理解的内容的非常高级的描述。将此视为对该想法的粗略概述，以准确理解您研究文章所拥有的一切。

基本思想是使用代数性质来避免一遍又一遍地重复相同的工作。他们通过使用幺半群运算和同态的结合性来做到这一点。

给定两组A和B有两个二元运算+和*同态是一个函数f: A -> B这样f(x + y) = f(x) * f(y) ，即它是一个保留两个集合之间的结构的函数。在那篇文章中，函数 f基本上是将输入集映射到训练模型的函数。

所以我们的想法是，您可以将输入数据分为不同的部分 x和y ，而不必像 T(x + y) 那样计算整个事物的模型您只需 x 即可进行培训和y然后合并结果:T(x) * T(y) .

现在这并没有多大帮助但是，在训练中你经常重复工作。例如，在交叉验证中，对于 k有时，将数据采样为训练器的一组输入和用于测试训练器的一组数据。但这意味着在这些k您正在执行的迭代T多次对输入的相同部分进行操作。

这里幺半群开始发挥作用:您可以首先将域拆分为子集，然后计算 T在这些子集上，然后计算交叉验证的结果，您只需将相应子集的结果放在一起即可。

给个想法:如果数据是 {1,2,3,4}和k = 3而不是这样做:

• T({1,2})加上 {3, 4} 上的测试
• T({1,3})加上 {2, 4} 上的测试
• T({1,4})加上 {2, 3} 上的测试

在这里您可以看到我们训练了 1三次。使用同态我们可以计算 T({1}) 一次然后将结果与其他部分结果相结合以获得最终的训练模型。

运算的结合性和同态性保证了最终结果的正确性。

并行化时可以应用相同的想法:将输入划分为 k组，并行执行训练，然后复合结果:T(x_1 + x_2 + ... + x_k) = T(x_1) * T(x_2) * ... * T(x_k)其中T(x_i)调用完全并行执行，只有在最后您才需要组合结果。

关于在线训练算法，其想法是给定一个“批量”训练算法T您可以通过以下操作将其变成在线版本:

T_O(m, d) = m * T(d)

哪里m是一个已经训练过的模型(通常是该点之前训练过的模型)并且 d是您为训练添加的新数据点。

结果的准确性再次取决于同态，它告诉您如果 m = T(x)然后m * T(d) = T(x+d) ，即在线算法对所有这些数据点给出与批处理算法相同的结果。

<小时/>

这一切中更有趣(也更复杂)的部分是如何将训练任务视为同态等。我将把它留给你个人研究。