6

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

4

1 回答 1

18

本文对此进行了解释，该文章链接在您在问题中链接的页面中。既然你想要一个初学者友好的描述，我会给你一个非常高层次的描述，说明我在阅读这篇文章后所理解的内容。将其视为对该想法的粗略概述，以准确了解您研究文章所需的一切。

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

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

所以想法是你可以将输入数据分成不同的部分x和yT(x + y)xyT(x) * T(y)

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

这里 monoids 发挥作用：您可以首先将域拆分为子集，并计算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)

wherem是一个已经训练好的模型（在此之前通常是训练好的模型），并且d是您为训练添加的新数据点。

再次，结果的精确性是由于同态告诉你 if m = T(x)then m * T(d) = T(x+d)，即在线算法给出了与所有这些数据点的批处理算法相同的结果。

所有这一切中更有趣（和复杂）的部分是您如何将训练任务视为同态等。我将把它留给您个人研究。

于 2016-10-09T13:15:55.763 回答