上次說到看了 paper 學了 Einstein Notation 怎麼用，說的就是 Deep Neural Decision Trees (DNDT) 這篇 paper，朋友看了說希望我解釋這篇 paper 所以就想說也好，當作讀後感寫一寫也不錯，免得 paper 都是看一篇忘一篇 😂
我們來看看怎麼用 Deep Learning 去實作一個 decision tree 吧！
The Building Block of DNDT
Soft Binning Function
其實熟悉 decision tree 的人應該都理解，decision tree 的重點就在於 split node 是怎麼把資料切割成一個一個變異越小越好的小群資料，然後看新資料落到哪一小群就用那一小群的特徵去預測有興趣的變量，因此 decison tree 很自然可以做常見的迴歸與分類問題。
DNDT 也不例外，它的核心在於如何實作一個可微分的分群函數，也就是這邊說的 binning function，這樣就可以用 deep learning 的方式去訓練它。那到底怎麼實作一個可微分的 binning function 呢？
Medium 不能打 LaTeX 所以我只好貼圖了 😅
其中 x 是我們的某個 scalar feature，beta 向量是我們的 cut points (單調遞增，也就是 beta_i < beta_{i+1})。也就是說我們想把 x 根據 beta 切割成 n+1 個區塊 (x < beta_1 or beta_1 < x < beta_2 …etc)。
其中最巧妙的我想是 o，也是剛開始一看會傻一下的地方。但用一些例子可以發現，如果 beta_i < x < beta_{i+1} 的話，那麼 o_i 就會是所有 o 的元素裡面最大的一個。
證明其實也不難，可以考慮 o_{i-1}、 o_i、 o_{i+1} 三者：
假如 x 現在是在 (beta_i, beta_{i+1}) 區間中的話，可以知道 (x - beta_i) > 0 且 (x - beta_{i+1}) < 0，所以說 o_i 比 o_{i-1} 多加了一個正數，而 o_{i+1} 比 o_i 多加了一個負數，也就是說 o_i 會是最大的。
所以說其實如果對 o 向量取 argmax 的話，它就會成了一個 x 要被切進哪個區間的 binning function 。一個自然的延伸就是，在資料複雜的情況下，你可能不會想要 argmax 這麼果斷的方式，所以說就可以改成用 softmax 讓它變成一個機率分佈，也就是說 x 有多少機率落在某個區間這樣 (量子力學的味道 😛)。
Kronecker Product
在 wiki 上可以找到 Kronecker Product 的定義，對於我們 decision tree 的實作中，它的用途在於做決定要用哪個 leaf value 做預測。要看懂這個實作，我們可以用一個簡單的例子來看看：
上面的例子就是，假設我們把 x1 跟 x2 兩個 feature 都分割成 3 個區間中，所以說最終的 leaf nodes 應該會有 3 x 3 = 9 個。那這邊我們為了凸顯 Kronecker Product 做為 routing 的功用，選用 onehot encoding 的方式去舉例，但在 softmax 下只是變成機率分佈而已。
從上面第三條式子中間可以看出來，如果其中某一個向量的 element 是 0 ，最終的結果就會是 0，又或者我們可以把中間的 product 擺橫的看：
如果你跟著是 1 的元素由上往下劃線的話，你就會發現 Kronecker Product 在這裡就是作為一個 routing 的功能，去根據切割出來的區間去算出最後 leaf node 的 indicator vector 。如果把 onehot encoding 換成 softmax，最後就會得到一個 leaf 的 distribution。我們的 soft binning function 於焉完成，而且因為中間只涉及矩陣運算，整個 binning function 是可微的，也就可以放進 deep learning 的訓練之中。
Deep Neural Decision Tree (DNDT)
理解前面的 soft binning function 之後，理解 DNDT 就不是什麼難事了。這邊我直接擷取論文中的圖片：
論文中是以 Iris 資料集作為範例，但不難看出，基本上就是你可以在前面套上 Binning layer (也就是前面說到的 soft binning function)，再用 Kronecker Product 得到 leaf score，最後接上一個 fully connected 或任何其他 layer 得到 output。當然 Binning layer 也可以疊加多層得到一個多層的 deep decision tree model 。
大概就是這樣啦，我收穫最大的是學到 Kronecker Product 跟 soft binning 實作一個 decision tree 的部分，其實都是不難懂的技巧，但以前從來沒這麼想過。希望寫了筆記之後，自己可以記得久一點，雖然應該又會是學了忘忘了學吧 XD
References
- Deep Neural Decision Trees: https://arxiv.org/pdf/1806.06988.pdf