Boosting over non-deterministic ZDDs
Boosting over non-deterministic ZDDs
复制标题
提升非确定性 ZDD
DOI：
10.1016/j.tcs.2018.11.027
复制
发表时间：
2018
影响因子：
1.1
通讯作者：
Kohei Hatano and Eiji Takimoto
中科院分区：
文献类型：
--
作者：
Takahiro Fujita;Kohei Hatano and Eiji Takimoto
我们提出了一种大规模机器学习的新方法，即在压缩数据上进行学习：首先对训练数据进行某种程度的压缩，然后在压缩数据上使用各种机器学习算法，希望在训练数据压缩得很好的情况下，大大减少计算时间。作为这种方法的第一步，我们考虑将零抑制二叉决策图(ZDD)的变体作为表示训练数据的数据结构，这是ZDD的推广，纳入了非确定性。对于要使用的学习算法，我们考虑一种称为AdaBoost⁎的Boost算法及其前身AdaBoost。在本文中，我们给出了Boosting算法的有效实现，其运行时间(每次迭代)与给定ZDD的大小成线性关系。
We propose a new approach to large-scale machine learning,learning over compressed data: First compress the training data somehow and then employ various machine learning algorithms on the compressed data, with the hope that the computation time is significantly reduced when the training data is well compressed. As a first step toward this approach, we consider a variant of the Zero-Suppressed Binary Decision Diagram (ZDD) as the data structure for representing the training data, which is a generalization of the ZDD by incorporating non-determinism. For the learning algorithm to be employed, we consider a boosting algorithm called AdaBoost⁎ and its precursor AdaBoost. In this paper, we give efficient implementations of the boosting algorithms whose running times (per iteration) are linear in the size of the given ZDD.