# 論文導讀：Accelerating Random Forest on Memory-Constrained Devices through Data Storage Optimization
###### tags: `Random Forest`
## 介紹(隨機森林)
our objective in this study is to train models that are as accurate as the original methods at a lower cost.
**focus在Random Forests (RF)**
https://www.youtube.com/watch?v=Ix0UhijD4Ks
>隨機森林其實就是進階版的決策樹，所謂的森林就是由很多棵決策樹所組成。隨機森林是使用 Bagging 加上隨機特徵採樣的方法所產生出來的整體學習演算法。還記得在前幾天的決策樹演算法中，當模型的樹最大深度設定太大的話容易讓模型過擬合。因此隨機森林藉由多棵不同樹的概念所組成，讓結果比較不容易過度擬合，並使得預測能力更提升。

**實作方法**
* 從訓練集中抽取 n’ 筆資料出來
* n’ 筆資料隨機挑選 k 個特徵做樣本
* 重複 m 次，產生 m 棵決策樹
* 分類: 多數投票機制進行預測、迴歸: 平均機制進行預測
>首先從訓練集中抽取 n’ 筆資料出來，然而這 n’ 筆資料是可以被重複抽取的。假設我們有一千筆資料我們要從中抽取 100 筆資料出來，這 100 筆資料裡面可能會有重複的數據。接著第二步從這些抽取出來的資料中挑選 k 個特徵當作決策因子的後選，因此每一棵樹只能看見部分的特徵。第三步重複以上步驟 m 次並產生 m 棵決策樹。透過 Bootstrap 步驟重複 m 次，做完之後我們會有 m 組的訓練資料，每一組訓練資料內都有 n’ 筆資料。最後再透過每棵樹的決策並採多數決投票的方式，決定最終預測的類別。因為隨機森林每一棵樹的特徵數量可能都不同，所以最後決策出來的結果都會不一樣。最後再根據任務的不同來做回歸或是分類的問題，如果是回歸問題我們就將這些決策數的輸出做平均得到最後答案，若是分類問題我們則用投標採多數決的方式來整合所有樹預測的結果。

**Bootstrap(A subset of the data-set,called bootstrap)**
>隨機森林中的隨機有兩種方面可以解釋。首先第一個是隨機取樣，在模型訓練的過程中每棵樹的生成都會先從訓練集中隨機抽取 n’ 筆資料出來，而這 n’ 筆資料是可以被重複抽取的。此抽取資料的方式又稱為 Bootstrap，它是一種在統計學上常用的資料估計方法。第二個解釋隨機的理由是在隨機森林中每一棵樹都是隨機的特徵選取。每一棵樹都是從 n’ 筆資料中隨機挑選 k 個特徵做樣本。

## 論文動機
* Practically, the size of the data-set is usually larger than the memory capacity,這會導致data movement 我們的實驗表明，構建一個memory work-space比數據集大小小 8 倍的決策樹，比數據集完全fit memory work-space的情況慢 25 倍
* 傳統的RF有兩個缺點
* Block Under-Utilization
因為相同的data block倍加載多次這會導致poor spatial locality
* Data over-read
給定的dataset不在boostrap裡，因而導致 moved back and forth from/to the memory to storage。
## 論文目的
### 提出兩個方法去改善傳統的RF
* 1.Enhancing spatial locality by data-set reorganization
> 考量到RF的性質，如果一對data elements是在一個決策樹構建期間連續訪問，他們很有可能被連續訪問用於構建其他決策樹。 因此，那些data elements可以存儲在neighboring blocks中。
* 2.Accessing required data elements on-demand
> memory work-space僅加載有效需要的數據並調整決策樹構建過程並考慮三種情況
> * 加載全部數據構建完整的子樹
> * 加載必要的數據以僅構建一個節點子樹
> * 區分node's data elements 到chunks使得可以fit memory且分別遍歷它們的elements to test splitting features.。 在後一種情況，從每個chunk獲得的結果處理被aggregated(combine)
* optimizations were tested by modifying the framework Ranger

**The two optimizations individually evaluated gave
1).the following results: The data-set reorganization reduces the execution time by 35 to 74%.
2.)on-demand data-access reduces it by 20 to 77.**

## Random Forest building algorithm
RF is a supervised machine learning algorithm used for class sification and regression
### 名詞定義
### 創建RF有四個步驟
* Bootstrap creation (step 1):
>隨機選取dataset並建立root
* Split trial (step 2):
>根據0、1去區分子樹
* Effective split (step 3):
>最佳化區分，一旦有pure(子樹的元素皆為同個class)就不切
* Step 1, 2 and 3 are repeated with the resulting nodes if they do not satisfy a stopping condition that is theoretically the pureness, and a maximum tree depth or a minimum number of elements per node in practice.

### 也有三個缺點
* Low spatial locality
>假設兩個feature為一個class，but只有一個是需要的因此使用率只有50%
* Useless data movement
>C是需要的data，但是是一個區塊因此D也從secondary storage to main memory造成不必要的搬移
* Multiple accesses to the same blocks for an individual node
>需要重複load到memory，舉例今天要用到C、D但明明是同個block卻要load兩次造成I/O operation的上升(swapping)

### 實驗
即使N/M=0.75 or 1 (代表可以fit memory)還是可以看到執行時間有顯著的上升，這是因為除了data size他所使用的data structure(ex index)也要考慮，而N/M=8執行時間是0.25的25倍這也證明了資料搬移造成很大的overhead

## 方法
### Data Reorganization
* Data Locality Learner
>去檢查block的element是能依序使用的，也就是上一次A下一次D，那麼AD為一個block
* Data-set Writer
>透過重組data-set達成，看似overhead很高但因會不斷重複使用因此還好

### On-demand Data Access Decision Tree Builder
* Decision Tree Building Module
>focus on decision tree building steps of the bagging algorithm，並非把所有data都load到memory而是將on-demand data loading根據目前可用的空間，會需要memory work-space monitor and the data loader
* Memory Work-Space Monitor
> * 所有node's data 可以fit memory
> * memory可以hold all value of feature在split trial step但是無法fit all node's data
> * 連value of feature都不行
* Data Loader Module
> 根據上面提供的三個情況，聰明的load data

### Re-write the data-set on the storage device
事實上寫入順序的不同不會影響決策數的準確率，因此我們把原本random select的方法改成sequential writes並帶有Data Locality Learner的性質去re-write the data-set

### Data-set Reorganization 實作
首先將每個impure node依序拆開，在將最常用到的兩個node綁在一起，之後去check如果這兩個是pure就將其綁在一起放回ssd，反之放進impure nodes list

### On-demand實作

依照上述(On-demand)的三個情況依序寫入data
* S(|F|+1)為子樹feature的數量-the volume |Ni|·S(d+1) is the volume occupied by the d features of the |Ni| elements of node i plus the effective class information (the function S(i) returns the memory space occupied by the i feature values).
* Scenario 1 (All data can fit memory)
在移動到更深層次之前會先處理same level的節點； 這樣，已經在memory中的data將被重新利用到full sub-tree中，而不會產生更多的 I/O 操作。
* Scenario 2 (不能fit all feature但是可以fit 當前需要的feature)
將這些需要用到的feature 保持在memory直到所有子樹的node處理完，這種方法使得降低swapping的overhead因為不用load useless data。
* Scenario 3 (useful data不能fit memory)

將每個useful data拆成chunk，最後將其merge。

### 整合演算法
先根據Algorithm 1重組數據集，在依照上述提到的三個情境去load data，若是前兩個使用Algorithm 2去load，而最後一個則是用chunk去load也就是algorithm3，最後在從 purest child nodes中找出最好的features，再去將這個feature split the node n，完成後重新建立new RF。

## 結果
### Experiment 1
* 6.a因當N/M太大時代表node受到影響的元素個數很可能大於M，dividing node很高。
* 6.b即使N/M上升表現還是不錯，因為這個策略只會load usefull data。
* 6.c結合a、b的演算法平均來看有最好的執行時間表現(下降最多)，但有些結果是比單獨的optimization2差，因為某些case可能即使資料重組也找不到好的block配置，又或者the random nature of bootstrap creation and the feature selection又太多變因了。
* Optimization 1, 2 and their combination are: 58%, 64% and 78%
### Experiment 2
* 第一個演算法在不同size T的情況下之圖表。
* 7.a execution time reduction ranges between 41 and 80%.
* 7.b 我們觀察到隨機森林中樹的數量越多，這個比例就越小
* 7.c 我們觀察到 I/O 時間減少遵循以下曲線執行時間減少。
* 7.a 可以發現T=25到T=50有顯著的上升，因為當T越來越大時，T0建立所花費的時間就不重要了，當忽略 T0 構建時間時，所有 RF 的執行時間減少在理論上是相同的，這與獲得的實驗結果一致。
### Experiment 3
* 主要是探討prefetch、fetch是否會影響結果
### Experiment 4
* The objective of this experiment is to evaluate the efficiency of the second optimization。
* Fig.9為剛才on demand提到的3個狀況對於執行時間的改進

## 總結
>其實還有四個實驗但我累了

* 數據重組，目的是從第一個構建的樹中推斷出哪些數據可能在同一時間窗口內被訪問。 此信息用於編寫新數據集，以在構建剩餘決策樹時增強空間局部性。
* On-demand data accesses，這種優化的目的是去除數據集駐留在內存中的假設，從而避免使用較少的數據交換到二級存儲。 在所提出的算法中，在決策樹節點級別訪問數據，例如僅加載有效需要的數據。 我們貢獻的好處取決於所使用的主內存和輔助存儲之間的性能比。
* 我們的實驗表明，當要處理的數據量available memory work-space的四倍時，數據集重組可以將執行時間平均減少 63%。 與評估的最先進方法相比，按需數據訪問優化平均可以將決策樹構建時間減少 71%。 與參考方法相比，這兩種優化的組合允許將執行時間減少近 75%。作為未來的工作，我們的目標是將數據集重組應用於其他集成學習方法，因為它們基於在同一數據集上訓練多個模型。
* In addition, the on-demand data access paradigm instead of a memory resident data-set assumption can be generalized to other machine learning algorithms.