Endre søk
RefereraExporteraLink to record
Permanent link

Direct link
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annet format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annet språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
BoostVHT: Boosting distributed streaming decision trees
KTH, Skolan för elektroteknik och datavetenskap (EECS), Datavetenskap, Beräkningsvetenskap och beräkningsteknik (CST).
KTH.
2017 (engelsk)Inngår i: International Conference on Information and Knowledge Management, Proceedings, Association for Computing Machinery , 2017, s. 899-908Konferansepaper, Publicerat paper (Fagfellevurdert)
Abstract [en]

Online boosting improves the accuracy of classifiers for unbounded streams of data by chaining them into an ensemble. Due to its sequential nature, boosting has proven hard to parallelize, even more so in the online setting. This paper introduces BoostVHT, a technique to parallelize online boosting algorithms. Our proposal leverages a recently-developed model-parallel learning algorithm for streaming decision trees as a base learner. This design allows to neatly separate the model boosting from its training. As a result, BoostVHT provides a flexible learning framework which can employ any existing online boosting algorithm, while at the same time it can leverage the computing power of modern parallel and distributed cluster environments. We implement our technique on Apache SAMOA, an open-source platform for mining big data streams that can be run on several distributed execution engines, and demonstrate order of magnitude speedups compared to the state-of-the-art.

sted, utgiver, år, opplag, sider
Association for Computing Machinery , 2017. s. 899-908
Emneord [en]
Boosting, Decision trees, Distributed systems, Online learning, Big data, Cluster computing, Clustering algorithms, Data mining, Distributed computer systems, Forestry, Knowledge management, Online systems, Trees (mathematics), Distributed clusters, Distributed streaming, Flexible Learning, Open source platforms, Parallel learning algorithms, Learning algorithms
HSV kategori
Identifikatorer
URN: urn:nbn:se:kth:diva-227056DOI: 10.1145/3132847.3132974ISI: 000440845300089Scopus ID: 2-s2.0-85037345394ISBN: 9781450349185 (tryckt)OAI: oai:DiVA.org:kth-227056DiVA, id: diva2:1203551
Konferanse
26th ACM International Conference on Information and Knowledge Management, CIKM 2017, 6 November 2017 through 10 November 2017
Merknad

QC 20180503

Tilgjengelig fra: 2018-05-03 Laget: 2018-05-03 Sist oppdatert: 2022-06-26bibliografisk kontrollert
Inngår i avhandling
1. Scalable Machine Learning through Approximation and Distributed Computing
Åpne denne publikasjonen i ny fane eller vindu >>Scalable Machine Learning through Approximation and Distributed Computing
2019 (engelsk)Doktoravhandling, med artikler (Annet vitenskapelig)
Abstract [en]

Machine learning algorithms are now being deployed in practically all areas of our lives. Part of this success can be attributed to the ability to learn complex representations from massive datasets. However, computational speed increases have not kept up with the increase in the sizes of data we want to learn from, leading naturally to algorithms that need to be resource-efficient and parallel. As the proliferation of machine learning continues, the ability for algorithms to adapt to a changing environment and deal with uncertainty becomes increasingly important.

In this thesis we develop scalable machine learning algorithms, with a focus on efficient, online, and distributed computation. We make use of approximations to dramatically reduce the computational cost of exact algorithms, and develop online learning algorithms to deal with a constantly changing environment under a tight computational budget. We design parallel and distributed algorithms to ensure that our methods can scale to massive datasets.

We first propose a scalable algorithm for graph vertex similarity calculation and concept discovery. We demonstrate its applicability to multiple domains, including text, music, and images, and demonstrate its scalability by training on one of the largest text corpora available. Then, motivated by a real-world use case of predicting the session length in media streaming, we propose improvements to several aspects of learning with decision trees. We propose two algorithms to estimate the uncertainty in the predictions of online random forests. We show that our approach can achieve better accuracy than the state of the art while being an order of magnitude faster. We then propose a parallel and distributed online tree boosting algorithm that maintains the correctness guarantees of serial algorithms while providing an order of magnitude speedup on average. Finally, we propose an algorithm that allows for gradient boosted trees training to be distributed across both the data point and feature dimensions. We show that we can achieve communication savings of several orders of magnitude for sparse datasets, compared to existing approaches that can only distribute the computation across the data point dimension and use dense communication.

sted, utgiver, år, opplag, sider
KTH Royal Institute of Technology, 2019. s. 120
Serie
TRITA-EECS-AVL ; 2019:43
Emneord
Online Learning, Distributed Computing, Graph Similarity, Decision Trees, Gradient Boosting
HSV kategori
Identifikatorer
urn:nbn:se:kth:diva-250038 (URN)978-91-7873-181-7 (ISBN)
Disputas
2019-05-28, Sal B, Kistagången 16, våningsplan 2, Electrum 1, KTH Kista, Kista, 14:00 (engelsk)
Opponent
Veileder
Forskningsfinansiär
Swedish Foundation for Strategic Research , RIT10-0043Swedish Foundation for Strategic Research , BD15-0006
Merknad

QC 20190426

Tilgjengelig fra: 2019-04-26 Laget: 2019-04-25 Sist oppdatert: 2022-12-12bibliografisk kontrollert

Open Access i DiVA

Fulltekst mangler i DiVA

Andre lenker

Forlagets fulltekstScopus

Person

Vasiloudis, Theodore

Søk i DiVA

Av forfatter/redaktør
Vasiloudis, TheodoreBeligianni, Foteini
Av organisasjonen

Søk utenfor DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric

doi
isbn
urn-nbn
Totalt: 38 treff
RefereraExporteraLink to record
Permanent link

Direct link
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annet format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annet språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf