Boosting over non-deterministic ZDDs

• 藤田, 隆寛

  九州大学大学院システム情報科学府

• 畑埜, 晃平

  理化学研究所

• 瀧本, 英二

  九州大学大学院システム情報科学府

抄録

We propose a new approach to large-scale machine learning, learning over compressed data: First compress the training data somehow and then em-ploy various machine learning algorithms on the compressed data, with the hope that the computation time is signi_cantly reduced when the training data is well compressed. As a _rst 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.

収録刊行物

• Theoretical computer science

  Theoretical computer science 806 195-206, 2018-12-04

  Elsevier

キーワード

• data compression
• optimization
• machine learning
• boosting
• ZDD

詳細情報

• CRID: 1050017057728163840
• NII論文ID: 120006603510
• DOI: 10.1007/978-3-319-75172-6_17
• DOI: 10.1016/j.tcs.2018.11.027
• ISSN: 16113349
• ISSN: 03029743
• ISSN: 03043975
• HANDLE: 2324/2231502
• HANDLE: 2324/1932329
• Web Site: https://link.springer.com/content/pdf/10.1007/978-3-319-75172-6_17
• Web Site: https://api.elsevier.com/content/article/PII:S0304397518307175?httpAccept=text/xml
• Web Site: https://api.elsevier.com/content/article/PII:S0304397518307175?httpAccept=text/plain
• 本文言語コード: en
• 資料種別: journal article
• データソース種別:
  • IRDB
  • Crossref
  • CiNii Articles
  • KAKEN