TY - GEN
T1 - Boosting over non-deterministic ZDDs
AU - Fujita, Takahiro
AU - Hatano, Kohei
AU - Takimoto, Eiji
N1 - Funding Information:
Acknowledgments. We thank anonymous reviewers for helpful comments. This work is supported in part by JSPS KAKENHI Grant Number JP16J04621, JP16K00305 and JP15H02667, respectively.
Publisher Copyright:
© Springer International Publishing AG, part of Springer Nature 2018.
PY - 2018
Y1 - 2018
N2 - 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 the first step, 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 boosting algorithm called AdaBoost* and its precursor AdaBoost. In this work, we give efficient implementations of the boosting algorithms whose running times (per iteration) are linear in the size of the given ZDD.
AB - 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 the first step, 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 boosting algorithm called AdaBoost* and its precursor AdaBoost. In this work, we give efficient implementations of the boosting algorithms whose running times (per iteration) are linear in the size of the given ZDD.
UR - http://www.scopus.com/inward/record.url?scp=85043326518&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85043326518&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-75172-6_17
DO - 10.1007/978-3-319-75172-6_17
M3 - Conference contribution
AN - SCOPUS:85043326518
SN - 9783319751719
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 195
EP - 206
BT - WALCOM
A2 - Rahman, M. Sohel
A2 - Sung, Wing-Kin
A2 - Uehara, Ryuhei
PB - Springer Verlag
T2 - 12th International Conference and Workshop on Algorithms and Computation, WALCOM 2018
Y2 - 3 March 2018 through 5 March 2018
ER -