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

截圖 2020-04-27 上午12.11.16

今天想跟大家介紹的論文是 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 = xY 的分量 q,在此處 \theta(x) = F^{-1}(q),~q\in [0,1],其中 FY|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):

截圖 2020-04-27 下午1.35.50

其中 \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) ,以數學公式表示為:

截圖 2020-04-28 上午12.40.37

 

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

截圖 2020-04-27 上午12.11.16

 

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

 

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

截圖 2020-04-28 上午12.34.21

 

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

截圖 2020-04-28 上午12.39.29

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

截圖 2020-04-28 上午12.34.35

此處「極小化估計誤差」與「極大化兩個節點間的參數差異」其實是等價的,也就是說,在進行分枝時,可以以「極大化兩個節點的異質性 (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 的為:

截圖 2020-04-28 上午12.45.19

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

截圖 2020-04-28 上午12.45.37

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

 

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

截圖 2020-04-28 上午12.46.55

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

截圖 2020-04-28 上午12.47.11

以最簡單的迴歸分析問題為例,此時 \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) 的信賴區間。 截圖 2020-04-27 下午1.21.12

截圖 2020-04-27 下午1.21.25

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

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

About David Huang

即將於 2020 年秋季至哈佛商學院 (Harvard Business School) 就讀量化行銷博士。過去曾在 Migo TV 擔任 Data Lead、Mastercard Data & Services 擔任顧問,過去專案經歷包括:客戶分群、消費者終生價值預測、市場實驗與學習、新產品上市測試、影片推薦系統、使用者行為預測、線上機器學習、文字探勘與產品分析、互聯網產品分析策略、企業指標體系與儀表板建立等。

1 Comment

發表迴響

你的電子郵件位址並不會被公開。 必要欄位標記為 *