Boosting over non-deterministic ZDDs. (English) Zbl 1436.68301
Summary: 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.
MSC:
| 68T05 | Learning and adaptive systems in artificial intelligence |
| 68P05 | Data structures |
| 68P30 | Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) |
References:
| [1] | Hazan, E., Introduction to Online Convex Optimization (2016), Now Publishers Inc |
| [2] | Lifshits, Y., Processing compressed texts: a tractability border, (CPM’07 Proceedings of the 18th Annual Conference on Combinatorial Pattern Matching (2007)), 228-240 · Zbl 1138.68419 |
| [3] | Hermelin, D.; Landau, G. M.; Landau, S.; Weimann, O., A unified algorithm for accelerating edit-distance computation via text-compression, (26th International Symposium on Theoretical Aspects of Computer Science. 26th International Symposium on Theoretical Aspects of Computer Science, STACS 2009 (2009)) · Zbl 1236.68308 |
| [4] | Goto, K.; Bannai, H.; Inenaga, S.; Takeda, M., Fast q-gram mining on SLP compressed strings, J. Discrete Algorithms, 18, 89-99 (2013) · Zbl 1267.68112 |
| [5] | Nishino, M.; Yasuda, N.; Minato, S.-i.; Nagata, M., Accelerating graph adjacency matrix multiplications with adjacency forest, (Proceedings of the 2014 SIAM International Conference on Data Mining. Proceedings of the 2014 SIAM International Conference on Data Mining, SDM 14 (2014)), 1073-1081 |
| [6] | Tabei, Y.; Saigo, H.; Yamanishi, Y.; Puglisi, S. J., Scalable partial least squares regression on grammar-compressed data matrices, (Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD ’16 (2016)), 1875-1884 |
| [7] | Minato, S., Zero-suppressed BDDs for set manipulation in combinatorial problems, (DAC ’93: Proceedings of the 30th International Conference on Design Automation (1993)) |
| [8] | Knuth, D. E., Art of Computer Programming, Volume 4, Fascicle 1: Bitwise Tricks & Techniques; Binary Decision Diagrams (2009), Addison-Wesley |
| [9] | Minato, S.; Uno, T.; Arimura, H., LCM over ZBDDs: fast generation of very large-scale frequent itemsets using a compact graph-based representation, (Pacific-Asia Conference on Knowledge Discovery and Data Mining (2008)), 234-246 |
| [10] | Minato, S.; Uno, T., Frequentness-transition queries for distinctive pattern mining from time-segmented databases, (Proceedings of the 10th SIAM International Conference on Data Mining. Proceedings of the 10th SIAM International Conference on Data Mining, SDM2010 (2010)), 339-349 |
| [11] | Inoue, T.; Takano, K.; Watanabe, T.; Kawahara, J.; Yoshinaka, R.; Kishimoto, A.; Tsuda, K.; Minato, S.-i.; Hayashi, Y., Distribution loss minimization with guaranteed error bound, IEEE Trans. Smart Grid, 5, 1, 102-111 (2014) |
| [12] | Rätsch, G.; Warmuth, M. K., Efficient margin maximizing with boosting, J. Mach. Learn. Res., 6, 2131-2152 (2005) · Zbl 1222.68285 |
| [13] | Freund, Y.; Schapire, R. E., A decision-theoretic generalization of on-line learning and an application to boosting, J. Comput. System Sci., 55, 1, 119-139 (1997) · Zbl 0880.68103 |
| [14] | Mangasarian, O. L., Arbitrary-norm separating plane, Oper. Res. Lett., 24, 1-2, 15-23 (1999) · Zbl 1028.90037 |
| [15] | Rätsch, G., Robust Boosting Via Convex Optimization: Theory and Applications (2001), University of Potsdam, Ph.D. thesis |
| [16] | Jiang, T.; Ravikumar, B., Minimal NFA problems are hard, SIAM J. Comput., 22, 6, 1117-1141 (1993) · Zbl 0799.68079 |
| [17] | Toda, T., Fast compression of large-scale hypergraphs for solving combinatorial problems, (Discovery Science - 16th International Conference. Discovery Science - 16th International Conference, DS 2013, Singapore, October 6-9, 2013, Proceedings (2013)), 281-293 |
| [18] | Revuz, D., Minimisation of acyclic deterministic automata in linear time, Theoret. Comput. Sci., 92, 181-189 (1992) · Zbl 0759.68066 |
| [19] | Takimoto, E.; Warmuth, M., Path kernels and multiplicative updates, J. Mach. Learn. Res., 4, 773-818 (2003) · Zbl 1083.68592 |
| [20] | Mohri, M., General Algebraic Frameworks and Algorithms for Shortest-Distance Problems (1998), 62 pp |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
