Hardware Acceleration of Nonincremental Algorithms for the Induction of Decision Trees and Decision Tree Ensembles

Abstract

The thesis proposes novel full decision tree and decision tree ensemble induction algorithms EFTI and EEFTI, and various possibilities for their implementations are explored. The experiments show that the proposed EFTI algorithm is able to infer much smaller DTs on average, without the significant loss in accuracy, when compared to the top-down incremental DT inducers. On the other hand, when compared to other full tree induction algorithms, it was able to produce more accurate DTs, with similar sizes, in shorter times. Also, the hardware architectures for acceleration of these algorithms (EFTIP and EEFTIP) are proposed and it is shown in experiments that they can offer substantial speedups.

У овоj дисертациjи, представљени су нови алгоритми EFTI и EEFTI за формирање стабала одлуке и њихових ансамбала неинкременталном методом, као и разне могућности за њихову имплементациjу. Експерименти показуjу да jе предложени EFTI алгоритам у могућности да произведе драстично мања стабла без губитка тачности у односу на постојеће top-down инкременталне алгоритме, а стабла знатно веће тачности у односу на постојеће неинкременталне алгоритме. Такође су предложене хардверске архитектуре за акцелерацију ових алгоритама (EFTIP и EEFTIP) и показано је да је уз помоћ ових архитектура могуће остварити знатна убрзања.

U ovoj disertaciji, predstavljeni su novi algoritmi EFTI i EEFTI za formiranje stabala odluke i njihovih ansambala neinkrementalnom metodom, kao i razne mogućnosti za njihovu implementaciju. Eksperimenti pokazuju da je predloženi EFTI algoritam u mogućnosti da proizvede drastično manja stabla bez gubitka tačnosti u odnosu na postojeće top-down inkrementalne algoritme, a stabla znatno veće tačnosti u odnosu na postojeće neinkrementalne algoritme. Takođe su predložene hardverske arhitekture za akceleraciju ovih algoritama (EFTIP i EEFTIP) i pokazano je da je uz pomoć ovih arhitektura moguće ostvariti znatna ubrzanja.