一般化隨機森林 (Generalized Random Forest)

今天想跟大家介紹的論文是 2019 年刊載在 The Annals of Statistics 的 Generalized Random Forest，將原本只用來預測 $Y_i$ 的隨機森林 (random forest) 推廣到任何種類的觀察值 $O_i$ 。這個架構非常適合估計異質處理效果 (heterogeneous treatment effect)，以及任何待估計參數會受到個體特徵 (features) 影響的情況。這篇論文有個特別有趣的觀點，一是將隨機森林的結果當作 kernel，在估計時給予「與目標相似」的樣本點更多權重 (weights)；二是在進行節點分割時，分割條件 (Splitting Criteria) 是「最大化兩個節點的異質性 (Heterogeneity)」，而不是 RSS、Gini Index 等常見指標。另外，這篇論文所提出的方法也有很好的統計表現，可以說是機器學習與因果推論結合的一大推進。

估計問題的定義

假設我們有一組 i.i.d. 的樣本 $i = 1, \cdots, N$ ，每一個觀察個體都有觀察值 $lates O_i$ 與共變量 (covariate) $X_i$ ，比如說：在一般迴歸的情況下 $O_i = Y_i$ ，有進行處置/實驗時 $O_i = \{Y_i, W_i\}$ （ $W_i$ 是用來記錄處置類型），如果是工具變數 (instrument variable) 則 $O_i = \{Y_i, W_i,Z_i\}$ 。令我們有興趣的參數為 $\theta(x)$ (受到共變量的影響)，而 $v(x)$ 為多餘參數 (nuisance parameter，如：簡單迴歸分析中的 $\alpha$ )。此處採用很常見的參數估計技巧：

假設參數 $\theta(x)$ 與 $v(x)$ 滿足 $\mathbb{E}\left(\psi_{\theta(x),v(x)}(O_i)|X_i = x\right)=0,~~\forall x \in \mathcal{X}$ ，其中 $\phi(\cdot)$ 是某個評分函數 (Scoring Function)。

以分量迴歸 (quantile regression) 為例子，假設我們想估計的是給定 $X_i = x$ ， $Y$ 的分量 $q$ ，在此處 $\theta(x) = F^{-1}(q),~q\in [0,1]$ ，其中 $F$ 是 $Y|X$ 的累積分配函數 (cumulative distribution function)，而評分函數可以訂為 $\psi_{\theta(x),v(x)}(Y_i) = q \mathbf{1}(\{Y_i > \theta (x)\}) - (1-q) \mathbf{1}(\{Y_i \leq \theta (x)\})$ 。

以 Forest 為基礎的局部估計

在實際資料集合上進行估計時，可以採取「局部估計法」(local estimation)：

其中 $\alpha_i(x)$ 就是用來調節第 $i$ 個樣本對於 $\theta$ 的貢獻程度。換句話說，給定共變量 $X=x$ ，我們想決定哪些樣本點比較適合用來估計 $\phi(x)$ ，因此針對每個樣本點都 $i = 1, \cdots, N$ 給定 $\alpha_i(x)$ ，而 $\alpha_i$ 越大，代表該樣本貢獻給待估計參數的資訊量越多。

這篇論文採用類似「隨機森林」的方式來決定這個權重。首先，透過重抽樣 (resampling / bootstraping) 訓練 $B$ 個迴歸樹。對於第 $b$ 棵樹而言，將與 $x$ 落在同一個節點 / leaf 的樣本點所形成的集合計為 $L_b(x)$ ，而 $|L_b(x)|$ 代表這棵樹分類與 $x$ 落在同一個節點的樣本點個數。

假設在這棵樹中總共有 10 個樣本點落在與 $x$ 相同的節點，對於這些樣本設定他們貢獻給 $\theta(x)$ 的貢獻為 1/10，其他樣本點的貢獻度則為 0，因而得到這棵樹第 $i$ 個樣本點的去中 $\alpha_{bi}(x)$ 。接著，我們將每棵樹得到的權重做平均，得到最終的權重 $\alpha_i(x)$ ，以數學公式表示為：

這樣的過程可以由下面的示意圖表示，上面的每一個小圖都是一個迴歸樹的訓練結果，藍點是我們希望用來估計參數的 $x$ ，比較大的黑點則是與 $x$ 落在同一個節點的樣本點。將這些小樹得到的權重做平均，最後就可以得到最下方的結果，其中黑點的大小就代表最後得到該樣本點的權重。

以「最大化異質性」為分枝條件

由於我們的目標是能夠準確估計參數 $\theta(x)$ ，因此在每一個樹進行節點分枝的時候，我們的目標不再是 impurity measure 或 RSS，而是能夠使分枝出兩個節點估計的參數能夠越準確越好。首先，針對單一節點 $P$ 與一組樣本資料 $\mathcal{J}$ ，我們估計參數 $\theta, v$ 的方法是：

接著，我們要將節點 $P$ 分為兩個子節點 $C_1, C_2$ 。在此處我們分割的目標是極小化參數估計的誤差，也就是極小化：

實際上將這個誤差函數拆解後（論文中的 Proposition 1），我們會發現極小化 $err(C_1,C_2)$ 跟極大化下面的函數等價：

此處「極小化估計誤差」與「極大化兩個節點間的參數差異」其實是等價的，也就是說，在進行分枝時，可以以「極大化兩個節點的異質性 (Heterogenity)」為分枝條件。

利用 Gradient Tree 估計參數

想直接利用全域搜尋的方法解決上面的極小化 $\widehat{\theta}_P, \widehat{v}_P$ 與極大化 $\Delta(C_1,C_2)$ 問題其實不大可行，運算成本會非常高，因此可以使用 Gradient 逼近的方式簡化計算。首先，我們先計算出 $\nabla\mathbb{E}\left(\psi_{\widehat{\theta}_{P},\widehat{v}_{P}}(O_i)|X_i\in P\right)$ 的一致估計式 (consistent estimator)，計為 $A_P$ 。比如說，如果評分函數 $\phi$ 是連續可微分函數，那麼 $A_P$ 的為：

接著，我們可以得到 $\widehat{\theta}_C$ 的近似解為

其中 $\xi$ 向量可以將 $\phi$ 與 $\theta$ 有關的元素抽取出來。

從上述的推導，我們可以設計 Gradient tree 的演算法：在標記步驟 (labeling stage) 時，我們先在母節點 (parent node) 計算出 $\widehat{\theta}_P, \widehat{v}_P, A^{-1}_P$ ，並針對每個樣本點 $i$ 計算出虛擬的目標值：

接著，我們可以進行節點分枝 (splitting)，此時分枝條件為極大化以下的函數：

以最簡單的迴歸分析問題為例，此時 $\phi_{\theta(X)}(Y_i) = Y - \theta(X)$ ，此時 $\rho_i = Y_i - \overline{Y}_P$ ，而分枝條件則會變成與原本隨機森林函數中一致。

GRM 演算法

最後，將上述的各個元素整合在一起，就可以得到以下一般化隨機森林 (Generalized Random Forest) 的演算法。這個估計方法在一些不算嚴格的條件下有很好的統計性質：一致性 (consitency) 與漸進常態 (asymptotic normality)，因此也可以透過 delta-method 估計出參數 $\theta(X)$ 的信賴區間。

有關 David’s Perspective 的最新文章，都會發布在大鼻的 Facebook 粉絲專頁，如果你喜歡大鼻的文章，還請您不吝嗇地按讚或留言給我喔！

大鼻觀點：https://www.facebook.com/davidperspective/

一般化隨機森林 (Generalized Random Forest)

估計問題的定義

以 Forest 為基礎的局部估計

以「最大化異質性」為分枝條件

利用 Gradient Tree 估計參數

GRM 演算法

相關

About David Huang

2 Comments

對 Mei-Cheng Shih 發表迴響取消回覆

估計問題的定義

以 Forest 為基礎的局部估計

以「最大化異質性」為分枝條件

利用 Gradient Tree 估計參數

GRM 演算法

分享此文：

相關

About David Huang

2 Comments

對 Mei-Cheng Shih 發表迴響 取消回覆

對 Mei-Cheng Shih 發表迴響取消回覆