ill-identified diary

所属組織の見解などとは一切関係なく小難しい話しかしません

[計量経済学] [機械学習] Generalized Random Forest (GRF) について

この記事は最終更新日から3年以上が経過しています


概要

Athey, Tibshirani, & Wager (2016, Generalized Random Forests) で提案されている Generalized Random Forest (GRF) について解説してみる.

[1610.01271] Generalized Random Forests 2019/7/4 追記: この論文は Annals of Statistics にアクセプトされたようだ.
projecteuclid.org

計量経済学機械学習の両方の文脈を追う必要が出てくるので, 機械学習を学んできた人, (計量) 経済学を学んできた人, それぞれに対して伝わりやすいように説明を試みる.

先日の Tokyo R #71 で以下のような発表があった.

cold-start-problem.hatenablog.com

ここで公開されているソースを確認していると, grf というパッケージが読み込まれていた. しかし, ソースコードではこのパッケージの関数は使われていない. なんのパッケージなのか気になって調べたところ, 上記で提案されたアルゴリズムの実装らしい. ということで調べてみると, 機械学習を経済学で応用することを研究している経済学者らが提案した方法である. よって, (計量) 経済学の知識と機械学習の知識の両方がないと何をやろうとしているのかわかりづらいと思われる. たとえば, 一般化ランダムフォレスト (GRF) という名前は, ランダムフォレストの一般化なのか? 何をどう一般化したのか? と思うかもしれないが, これは計量経済学の文脈を知っているとその名前の意図に気づける. というわけで, 予備知識を補いながら解説していく.

この論文で提案されている GRF をできる限り短くまとめると, 「個別効果の異質性 (heterogeneity) のある因果推論モデルのパラメータ (異質的処置効果: Heterogeneous Treatment Effect) を推定するために, モデルの誤差を基準にした Ramdom Forest で個体をクラスタリングし, 得られた推定クラスタをもとに一般化モーメント法 (GMM) を 局所回帰してパラメータを識別するアルゴリズム」である. これで何をやってるかわかった人はこれ以降読まなくても大丈夫だが, たぶん多くの人は分からないと思うので, 説明をしていく.

予備知識のセットアップ

経済学寄りの人, 機械学習寄りの人のどちらに対しても説明になるように, GRFの理解のために特に重要な概念を順に説明していく*1. 以下では, 「目的意識」「一般化モーメント法」「カーネル回帰」「ランダムフォレスト」について簡単に説明しておく.

目的は因果推論

単に因果推論, と言うだけでは, 文脈を共有しない人には少しわかりにくいと思われる. 特に機械学習寄りの人向けに経済学の問題意識を解説する. (\boldsymbol{x}_{i},y_{i}) というデータにたいして, パラメータ (重みベクトル) \boldsymbol{\theta} をもつモデル

\begin{align}
y_{i}= & \psi_{\boldsymbol{\theta}}(\boldsymbol{x}_{i})\end{align}
を仮定したとき, 精度の良い予測値 \hat{y}_{i}を得たいというのが典型的な機械学習の問題である. 一方, 計量経済学では, 確率モデルを予測に使うよりもパラメータの推定に使うことが多い. つまり, パラメータ \theta を, バイアスが発生しないように点推定したり, 少ない誤差でパラメータの事後分布を推定したりしたい, というのが典型的な経済学の問題意識である*2. そのため, 単に予測分布を近似するだけではなく, 生成モデルの構造を近似あるいは同定することも重要になってくる. 推定アルゴリズムが提案される場合には, 得られる推定量は適切に収束するか, バイアスはないか, 分散はどの程度か, 分布はどうなるか, といった理論的性質が論じられる. よって, ニューラルネットワークのように, パラメータの一意性にこだわらないようなアプローチや, 決定木のように重みベクトルを明示的に求めないような手法は, この問題の解決に向いていない. もちろん, 予測精度も要求されるが, パラメータの同定がなければ予測がいくら正確でもモデルに意味はない. 制御可能な変数を調整することで, 結果がどのように変化するか, という応用が求められている*3.

これは典型的な因果推論である. 以下, 因果推論を形式的に説明しておく. この応用は, 独立変数 w_{i} の増減に対して目的変数 y_{i} がどれだけ変化するか, という含意を得たい, ということである*4. w_{i}=\{0,1\} というバイナリ変数とすると, これはある政策 (施策) を打ったかどうかを表す. \boldsymbol{x}_i のうち, w_i 以外の残りの独立変数 \boldsymbol{z}_{i}g(\boldsymbol{z}_{i}) としてまとめておく. そこで

\begin{align}
y_{i}= & \theta w_{i}+g(\boldsymbol{z}_{i})\end{align}
というモデルを仮定すると, パラメータ\theta は, \boldsymbol{z}_i の値が一定だったとき (つまり g(\boldsymbol{z}_i) も一定) の, w_{i}=0 の場合と w_{i}=1 の場合のそれぞれの, y_{i} の大きさの差ということになる. よって, \theta は施策を打ったことによる純粋な効果 (因果効果) を意味することになる.

ただし, このような解釈は本質的に反実仮想的 (counterfactual) であり, \theta が本当にこのような因果効果の大きさとみなせるかどうかは, さらに追加の仮定が必要になる. これについては, モデルをどう定式化するかだけでなく, サンプルの取り方の問題などが絡んでくる. この仮定を無視した因果推論の「濫用」はしばしば問題となり, 慎重に分析しなければならないが, ここでそこまで詳細に説明するのは面倒*5なので, ここではこの問題をクリアしていると仮定し, 単なるパラメータ同定と同じ問題としてみなすことにする.

一般化モーメント法 (GMM)

一般化モーメント法 (GMM) は計量経済学ではとてもメジャーなパラメータの推定方法であり, 様々な派生バージョンが存在する. しかし, 経済学以外の分野では私の知る範囲ではほとんど見られない.

典型的な回帰モデル,

\begin{align}
y_{i}= & \alpha+\beta x_{i}+\varepsilon_{i}\end{align}
では, 独立変数 x_{i} が誤差項と相関しないことを前提としている. しかし, 経済学においては, しばしばこのような仮定を満たさないようなモデルを扱うことになる. この原因としては, 一部の変数に無視できない大きさの観測誤差がある, 背後に共変関係が存在する, 同時決定的なモデルで x,y の因果関係の向きがわかりにくい (同時決定問題), などの理由がある. 既に書いたように, パラメータの同定はしなければならないので, 次のような方法が長らく使われている.

ここで, x_{i}や, それ以外の変数が\varepsilon_{i} と無相関ならば, それらをz_{i} とすると,

\begin{align}
\mathrm{E}z_{i}\cdot\varepsilon_{i}= & 0\end{align}
が成り立つ. これをモーメント条件といい, 経済学ではよくパラメータを推定できるモデルを考案するための基点となっている. このような z_{i} は操作変数と呼ばれる. 操作変数を含むモデルの推定方法には, 間接最小二乗法とか, 2段階最小二乗法とか呼ばれているものがあるが, これらを一般化したのが一般化モーメント法 (GMM) である. GMM は最小二乗法と同じ線形推定量である. GMM は単一の方程式だけでなく, 背後の共編構造も仮定するという点で構造方程式モデル (SEM) とも似ている発想だが*6, GMMはモーメント条件を守っている限り (最適化可能な関数の範囲内でなら) 非線形な関数で表されるモデルにも一般化できるので, SEM より広い範囲を指すとも言える*7. 逆に, こういった外生性がまったくない, シンプルな線形回帰モデルも, z_{i}=1 とすればモーメント条件を守っていることになるので, 線形回帰モデルも GMM の範囲に含まれることになる. 今回紹介する GRFは GMM の枠組みで説明されているため, 線形回帰モデルにも当然適用可能ということになる.

GMMの枠組みではモーメント条件からどうやってパラメータを推定するのか, 簡単に説明する.

モーメント条件は期待値だから、適切な仮定のもとでは標本平均 (標本モーメントともいう) で推定することができる. よって, 標本平均がゼロという条件から逆算してパラメータを推定することが考えられる. もちろん, 実際のデータにはノイズがあるから, 標本平均が正確にゼロとなるわけではない. そこで, GMM によるパラメータの推定は, 距離最小化問題として定式化される. 独立変数が複数ある場合に一般化すると、モーメント条件は, 以下のようなベクトルで表される.

\begin{align}
\mathrm{E}\boldsymbol{z}_{i}\varepsilon_{i} &=	\mathbf{0},\\
\mathrm{E}\boldsymbol{z}_{i}(y-\boldsymbol{x}_{i}^{\intercal}\boldsymbol{\beta}) &=	\mathbf{0}
\end{align}
よって, 標本平均は,
\begin{align}
\frac{1}{N}\sum_{i=1}^{N}\boldsymbol{z}_{i}(y_{i}-x_{i}^{\intercal}\boldsymbol{\beta}) \to & 0
\end{align}
となる. この標本平均の内積がゼロに近づくように最小化すればよい, ということになる. ただし, 変数どうしの共分散やスケールの違いから*8, マハラノビス距離のように重み行列  \mathbf{W} を挟んで, 以下のように定義される

\begin{align}
\hat{\boldsymbol{\beta} } =&	\arg\min_{\boldsymbol{\beta}}\sqrt{N}\left[\sum_{i=1}^{N}\boldsymbol{h}_{i}(\boldsymbol{\beta})\right]^{\intercal}\mathbf{W}\left[\sum_{i=1}^{N}\boldsymbol{h}_{i}(\boldsymbol{\beta})\right],\\
\boldsymbol{h}_{i}(\boldsymbol{\beta} ):=& \boldsymbol{z}_{i}(y_{i}-x_{i}^{\intercal}\boldsymbol{\beta } )
\end{align}

これ以上の GMM の詳しい説明は, 以前書いた記事や, 記事で挙げられている参考文献, あるいはぐぐったら出てくる各大学の講義ノートなどで確認してほしい.


カーネル回帰

カーネル回帰*9あるいはカーネル平滑化法という名称は分野によってばらつきがありそうだ. 統計学/計量経済学では局所回帰 (local regression) やノンパラメトリック回帰と呼ばれることが多い*10ようで, 本文中でも局所回帰という表現が使われている. カーネル回帰は, 機械学習の教科書でもよく取り上げられているが, 機械学習の典型的な問題である予測 (外挿) には使いにくいため, 実際に使う人は少ないかもしれない. 計量経済学では, 部分的に使われることもあるが, 標準的な教科書にはあまり取り上げられることのないトピックのように思われる.

カーネル回帰はナダラヤ・ワトソン (Nadaraya-Watson) 推定量が代表例で, 矩形3次カーネルエパネチニコフ (Epanechnikov) ・カーネル (Епанечников, В. А., 1969) などのカーネル関数を使った方法のことを指す*11.

局所回帰の基本的なアイディアは, ある点の周囲に分布するデータだけでフィットさせる方法のことである. 例えば, 線形回帰で

\begin{align}
\hat{f}(x):= & \alpha(x)+\beta(x)x_{i}\end{align}
という回帰直線を仮定する. パラメータ \alpha(x),\beta(x) は, 入力される点 x に応じて変わることを意味する.

その際に, 点が離れるほど重みが減衰するようにしたい. この重み付けをカーネル関数と呼ばれる関数で行うのがカーネル回帰である. 例えばエパネチニコフ・カーネルならば

\begin{align}
K_{\lambda}(x,x_{i})= & D\left(\frac{\left|x_{i}-x\right|}{\lambda}\right),\\
D(t):= & \begin{cases}
\frac{3}{4}(1-t^{2}) & \text{if }\left|t\right|\leq1\\
0 & \text{otherwise}
\end{cases}\end{align}
というふうに定義される. あとは重み付き推定なので, 通常の最小二乗法にカーネルによる重みを与えた
\begin{align}
\min_{\alpha(x),\beta(x)} & \sum_{i=1}^{n}\left(K_{\lambda}(x,x_{i})\left[y_{i}-\hat{f}(x)\right]^{2}\right)\end{align}
を解くことでパラメータを求められる.

これは, ある点の周囲で最も近い観測点から順にk個を取り出して計算に使うk-最近傍法 (k-NN) と似ている. 再近傍法ベースのアルゴリズムには B-スプライン近似や ggplot2geom_smooth() でデフォルトで使われる LOESS がある*12.

カーネル回帰は入力された点 x ごとにパラメータを計算し, 予測値 \hat{y} を返すという処理をする, 怠惰学習*13と呼ばれるタイプのアルゴリズムである. よって, 一旦パラメータを学習させれば後は任意の x に対してただちに予測値を計算, ということができない. よって, 活用できる場面が限られるが, 上記のように線形回帰モデルを定義していながら滑らかな回帰曲線を得られるという特徴がある. たとえば, 3次曲線をもとに生成させたデータ に, 上記の単純なカーネル線形回帰を適用した結果が以下になる.


f:id:ill-identified:20180802002708p:plain

エパネチニコフ・カーネルを使った局所線形回帰の当てはめ例

同様に, GMM (より一般化するなら, 尤度関数にも) カーネル関数でウエイトをつけて計算することもできる. 本文中では, カーネル関数で重み付けした GMM は local GMM と呼ばれている.

カーネル回帰の詳しい話も, 文献が充実しているので適当に確認してほしい.

例えば, 日本学術会議 経済学委員会 数量的経済・政策分析分科会の発表スライド

西山慶彦 『ノンパラメトリック,セミパラメトリック計量経済分析:概観』

や, 機械学習の分厚い教科書などでは説明がなされていることが多い. 例えばHastie, Tibshriani, & Friedman (2009, The elements of statistical learning: Data mining, inference, and prediction)など.

ランダムフォレスト

経済学寄りの人はおそらくランダムフォレストを知らないことが多いので, 今度は主に経済学寄りの人向けに説明する. 本文にも簡単な解説があるが, 一応.

ランダムフォレストは, パラメータの識別ではなく, 変数 x に対して目的変数 yの予測値 \hat{y} を求めるためのアルゴリズムである. よって, 予測値 \hat{y}がどれだけ y を正確に予測するかが課題であり, パラメータをバイアスなく推定するといったことは必ずしも要求されない. これはランダムフォレストに限らず, 機械学習全般に当てはまる*14. このランダムフォレストというアルゴリズムも, 線形回帰のような形でパラメータを明示的に求めることなく, 予測値を返すアルゴリズムである.

ランダムフォレストの説明の前に, まず基礎となる決定木について説明する. 決定木は, 条件分岐の組み合わせ構造で記述されるモデルを作成するアルゴリズムである. 決定木と呼ばれるアルゴリズムは実は複数あるが, 一番広く使われているのは CART アルゴリズム*15で, 今回提案される方法でも CART を使っているため, これを説明する. CART は2択分岐をネストさせて作るアルゴリズムで, 分類にも回帰にも適用できる. 決定木という名称は, モデルがノードと枝で構成された木構造で表せることに由来している. この木構造を特定するには, 数学的には組合せ最適問題になり, 全体最適化の計算が難しい. そこで, 局所最適化を繰り返すヒューリスティックな方法 (貪欲法) で計算するしかない. 具体的には, 分岐のたびに, 分岐の誤分類を最小限に抑えるように分割方法を決める, ということである.

例えば以下の図が決定木の例である.


f:id:ill-identified:20180802002740p:plain

決定木の木構造の例

これは y_{i}=\{A,B,C\} という3通りの値を取る目的変数に対して決定木を適用したものである*16. この図を例に, 決定木のアルゴリズムの流れを説明する. (1) は, 木の出発点である根ノードである. このノードにはデータ \mathcal{D}:=\{X_{1,i},X_{2,i},X_{3,i},X_{4,i},y_{i}\}_{i=1}^{N} が存在する. これを, 2つのデータに分割する. この分類によって, y_{i} の誤分類が最小になるように*17分割の条件を決めなければならない. ここでは, X_{3}<2.5 ならば y=A, そうでなければ y=B, という条件が選ばれた. この条件式は, 必ず1つの変数をつかった不等号で表される. これによって, データはノード(2) と ノード (3) に分割された. ノード (2) に振り分けられたデータは, 全て y_{i}=A なので, これ以上分割する必要はない. 一方, ノード (3) に分けられたデータには B, C の例が五分五分で含まれている. 今度は X_{4}<1.8 という条件で分割している. これによってy=B で誤分類率 0.9 % のノード (6) と y=C で誤分類率 0.2 % のノード (7) が出来た. このようにして, 誤分類がなくなるまで分割する*18.

このようにしてできた木構造に対して, データの例を入力し, 終端のノード (リーフノード) のどれにたどり着くかでy_{i}の予測値を出力できる.

貪欲法で解かれる決定木は, 計算量が比較的少ないが, 結果のばらつきが大きくなってしまいがちである. そこで, 結果のばらつきの大きい決定木を複数作って, その平均を取る*19ことでばらつきを小さくする, というのがランダムフォレストのアイディアである*20. 実際に, ランダムフォレストと, これを構成するそれぞれの木の決定領域を図示してみる.


f:id:ill-identified:20180802002758p:plain

ランダムフォレストの決定領域

この図では, tree1 から tree8 までの8つの木と, それらを合成した forest の決定領域と, 実際のデータの散布図を重ねたものである. 色分けされた領域は, それぞれの木の予測値を表し, 破線は真の境界を表している. 個々の木の決定領域はかなり異なるが, 的中率 (accuracy) はそれぞれ大差ない. つまり, それぞれの木にはばらつきがあるが, それぞれ同じくらい正しい決定領域の近傍をさまよっている. このような時, 複数のモデルの予測値を合成したランダムフォレストの予測する決定領域は、ばらつきのあるそれぞれの木の決定領域を平均するため, より正しい決定領域に近づき, 予測精度が向上する*21. 実際, この図では 8つの木の的中率がそれぞれ 0.63 から 0.87 程度だったものが, ランダムフォレストに合成することで 0.94 にまで上昇している.

かなり大雑把にアイディアだけを述べたが, GRF を説明するのに最低限必要なランダムフォレストへの理解は「2分割を繰り返す」「ブートストラップ標本で複数回計算し、結果の平均を取る」「複雑な分類ができるわりに計算量が少なく, 実装も比較的簡単なアルゴリズム」程度で良いと思う.

本題

以上, 「目的意識」「一般化モーメント法」「カーネル回帰」「ランダムフォレスト」の4つを踏まえて, 論文の主題について説明する.

この論文でも, メインはモーメント条件

\begin{align}
\mathrm{E}\left(\psi_{\theta,\nu}(O_{i})\mid\boldsymbol{x}_{i}\right)= & 0\end{align}
を満たすモデルを考えている. つまり, 今回の問題では \psi_{\theta,v} が GMM の枠組みの範囲内で解けることを暗に仮定している.

主な目的はパラメータ \theta の同定を通して因果効果の大きさ知ることで, それ以外のパラメータ \nu は, あまり関心のない局外母数 (nuisance parameter) ということになる. パラメータの同定が目的と言ったが, ここでは最低限 \theta さえ同定できればいい*22. \psi_{\theta,\nu}(O_{i}) は, そのような2種類のパラメータを含むモデルを表している. O_{i} は, 問題に直接関係のあるデータを表し, 例えば, O_{i}:=\{y_{i},w_{i}\} として, そこに共変量 x_{i}を加えた,

\begin{align}
y_{i}= & \theta w_{i}+\nu x_{i}+\varepsilon_{i}\end{align}
という線形回帰モデルが考えられる. 誤差項 \varepsilon_{i} は, 期待値がゼロと仮定すれば,
\begin{align}
\psi_{\theta,\nu}(O_{i}):= & \varepsilon_{i}=y_{i}-\theta w_{i}-\nu x_{i}\end{align}
とおけば, 先に挙げたモーメント条件を満たすので, ここで提案されるアルゴリズムで解ける範囲の問題となる. もちろん, これくらい簡単な場合は最小二乗法を使ったほうが速いだろう. もう少し複雑な場合は, 操作変数を伴う GMM 的なモデル
\begin{align}
\psi_{\theta,\nu}(O_{i})= & z_{i}\varepsilon_{i}\\
= & z_i (y_i - \theta w_i - \nu x_i)
\end{align}
などが考えられる.

さらに, より正確には, モーメント条件は,

\begin{align}
\mathrm{E}\left(\psi_{\theta(x),\nu(x)}(O_{i})\mid x_{i}\right)= & 0\end{align}
と記述され, パラメータ \theta,\nu が共変量 x に依存して変化する場合も考慮している.

さて, GMMとは, モーメント条件の期待値を標本平均に置き換えた標本モーメントの距離最小化問題を解くことだった. ここでも同様だが, 実際のデータには異質効果が存在するため, 通常と同じように推定するとパラメータの推定にバイアスがかかる. よって, パラメータを推定するには, 新たに重み \alpha_{i}(x) を加えた, 以下のような最適化問題を解くことになる (GMM の重みは, 観測例 i ごとに異なる値であるという仮定を置いていなかった).

\begin{align}
\hat{\theta}(x),\hat{\nu}(x) = & \arg\min_{\theta,\nu}\left\Vert \sum_{i=1}^{n}\alpha_{i}(x)\psi_{\theta(x),\nu(x)}(O_{i})\right\Vert _{2} \tag{A} \end{align}

という状況でどうすればいいか, というのがこの論文の問題設定である.

この式は, \alpha_{i}(x)カーネル関数とすれば, カーネル回帰ともみなせる. もちろん, \theta(x) が任意の x で同一であると仮定すれば, 通常の回帰モデルにもなる. さらに, \psi_{\theta,\nu}の部分については特に仮定してないため, 理論上は GMM や最小二乗法だけでなく, 分位点回帰, サポートベクター回帰など色々な回帰アルゴリズムを適用できる.

既存の研究でも, こういった問題に対処する方法が全く提案されなかったわけではない. 例えば経済学分野の生産関数の推定では, Olley & Pakes (1996), Levinsohn & Petrin (2003), Ackerberg, Caves, & Frazer (2006) という一連の研究で, 企業ごとに異なる生産性を表現するために, カーネル多項式回帰が使われている. これらは生産関数の推定という特定のジャンルの問題を対象とした方法なので問題にならなかったが, 一般にカーネル回帰は x の次元が増えると近傍の点が減るため (次元の呪い), 計算がうまくいかないという問題がある*23.

そこで, この論文では, \alpha_{i}(x)カーネル関数ではなく, ランダムフォレストを使って推定する, という方法を提案している. 決定木で, 分岐を作る際に, 分割による局所回帰の当てはまりを最適化するように決定する. そのようにして作成したランダムフォレストについて, 「分類結果」ではなく, 最終的にどのリーフノードに行き着くか, という情報をクラスタリングに使う*24. 本来のランダムフォレスト (決定木) は, 誤分類を基準に分割するものだが GRF では回帰モデルの平均2乗損失関数を代わりに当てはめている. この点では一般化かもしれないが, 個人的には GMM の派生アルゴリズムという意味ということにしたほうがしっくりくる気がする.

この GRF のアイディアをそのままアルゴリズムに落とし込むと, 次のようになる.

  1. B本の決定木について, それぞれ以下を繰り返す.

    1. データの初期値として, ブートストラップ標本を生成する.

    2. 親ノードPのデータを,C_{1},C_{2} の2つに分割する. 分割は決定木と同様に, いずれかの軸に平行になるようにする.

    3. 分割後の2集合それぞれに対応する部分データで上の最適化問題

      \begin{align}
\hat{\theta}_{C_{j}},\hat{\nu}_{C_{j}}= & \arg\min_{\theta,\nu}\left\Vert \sum_{\{i\in C_{j}\}}\psi_{\theta,\nu}(O_{i})\right\Vert _{2}\end{align}
      を解き, パラメータ \hat{\theta}_{C_{1}},\hat{\theta}_{C_{2}} を得る.

    4. (2) から誤分類率を計算する. 誤分類率は以下のように, パラメータの平均2乗誤差の期待値として定義されるので, これを推定する.

      \begin{align}
\mathit{err}(C_{1},C_{2}) & :=\sum_{j\in\{1,2\}}\mathrm{P}(X\in C_{j}\mid X\in P)\mathrm{E}\left[\left(\hat{\theta}_{C_{j}}(\mathcal{J})-\theta(X)\right)^{2}\mid X\in C_{j}\right]\end{align}
      \mathcal{J} はノード P に属する部分データ, \hat{\theta}_{P} は親ノード P の時点でのデータ, つまり \mathcal{J}を使って (b) の式から推定したパラメータである.

    5. (2), (3) の方法で計算した誤分類率が最小になるような分割 C_{1},C_{2} を選択する.

  2. 以上をB 本の木について行ったら, 結果を合成する. \alpha_{i}(x) を,

    \begin{align}
\alpha_{i,b}(x):= & \frac{1(\{x_{i}\in L_{b}(x)\})}{\mathrm{card}(L_{b}(x))},\\
\alpha_{i}(x):= & \frac{1}{B}\sum_{b=1}^{B}\alpha_{i,b}(x)\end{align}
    とする. L_{b}(x) は, 木 b において x と同じリーフノードに行き着く点の集合を意味する. この \alpha_{i}(x) をもとに, (A) を解く.

ところで, 本来の決定木やランダムフォレストでは, 誤分類率の計算はこのような複雑ではなかった. ノードの分割のたびに, 最適な分割を探索するためにモデルのパラメータをいちいち推定する必要があるので, 計算量が膨大になり実用的ではない. そこで, この論文では, 計算を早めるために誤分類率を近似計算で置き換える方法を提案している*25.

さらに, この方法で得られた推定量の理論的性質について調べ, \psi がレギュラーな条件を満たすなら, GRFで推定された \hat{\theta} は一致性を持つことや, 漸近分布をを示している. レギュラーな条件は最小二乗法をはじめ, 分位点回帰*26などロバストな回帰など, 多くのアルゴリズムと矛盾しないため, 応用できる範囲は広い.

2019/7/4 追記: 私はこの論文の研究の背景をあまり確認してなかったのだが, 中村知繁氏の以下のスライドの44ページ目以降から読むと, この研究のモチベーションがわかりやすい (スライドの前半部分も因果推論フレームワークの理解に有益である).

speakerdeck.com



参考文献



*1:元論文も経済学者を対象とした論文であるため, 馴染みの薄い機械学習に関しては, 基本的なことがらも順序だてて説明している. しかしそれだけだと論文のリンク貼って「読め」で終わってしまうのでもう少し丁寧に説明しておく.

*2:予測値を得ることが目的なのか, パラメータの同定が目的なのか, という前提を共有しておらずに噛み合わない議論が時々インターネットで見られる (と書いたが自分も以前、論点のはっきりしていない文章を書いていた).

*3:なので, ニューラルネットであっても, その理論的挙動や感度分析の方法論の整備が進めば, もしかしたら使われるようになるかもしれない. あまり自信はないが.

*4:つまり, 一般化して言うと, \partial y_{i}/\partial x_{i} を知りたいということになる.

*5:星野 (2009) などが日本語の因果推論の教科書として支持されている.

*6:なお, 操作変数アプローチが純粋な統計学的に見ると間違っている, などという主張がまれに現れるが, 実際のところ, SEM のように複数の方程式を集約したモデルを推定しているというだけであり, 多変量分布で表されるモデルの最尤推定と実質的に変わらない. ではなぜ最尤法を使わないのかと言うと, 理由の1つとして, モデルを線形近似した GMM のほうが, モデルの仮定の誤りに対して最尤法より頑健である, という性質があることが挙げられる. それ以外にも, どういう問題に応用するかで GMM と最尤法の優位点はいろいろと変わってくるため, 一概に論じることは難しい. 具体的なアルゴリズムどうしを比較するのではなく, 「ベイズ統計」や「ディープラーニング」といった広いカテゴリでまとめて, どちらが優位か比較するのがあまり意味をなさないのと同じように.

*7:SEM の定義にコンセンサスがあるのか, 私はよく分かっていない. 非線形なモデルも SEM に含むという人もいるかもしれない.

*8:パラメータの同定という観点から, 変数のスケール調整は好まれない

*9:カーネル密度推定 (KDE) と名前が似ているが, カーネル回帰が教師あり学習とすれば KDE教師なし学習と位置づけられる.

*10:こういうのもノンパラメトリックと言えるのか昔から疑問に思っている. そもそもノンパラメトリックを厳密にどう定義するかという問題かもしれないが. 頑健性 (robustness) と同じように明確に定義しないものなのだろうか.

*11:名前にカーネルとあるが, サポートベクターマシン (SVM) などに利用されるカーネルトリックとは直接の関係はない.

*12:LOESS などの最近傍法で重み付けするアルゴリズムは, カーネルによる重み付けとは理論上の性質が異なる. よって、狭義には最近傍法ベースのアルゴリズムだけを局所回帰というほうが正確であるように思えるが、カーネル回帰も含めて局所回帰と呼ばれることも多い.

*13:lazy learning.「遅延学習」というほうが適切か?

*14:よって, 機械学習で「バイアス」と言ったら, 通常は予測値と目的変数の差の大きさについて言及しているはずである.

*15:R の rpart や Python の scikit-laern でも CART が採用されている.

*16:実はこれは iris データの名前を変えただけである.

*17:この誤分類の計算には何通りかある. 単純に誤分類の発生割合とすることもできるが, CART では, ジニ多様性指数を使うことが多い.

*18:分割の終了条件にもいろいろなやり方があり, 誤分類がなくなるまで続けるという方法だけが正解というわけではない. 分割を細かくしすぎると過剰適合になる可能性もある.

*19:今回は予測対象がカテゴリカル変数なので, 平均ではなく多数決で最終的な予測値を決める.

*20:より正確には, ランダムフォレストとはブートストラップ標本を生成し, それぞれの標本で決定木を作り, 結果を合成するアルゴリズムのことを言う.

*21:このような手法は集団学習とかアンサンブル学習と総称される. ここでは大雑把な説明をしたが, より厳密な理論を知りたい場合は, Hastie et al. (2009, The elements of statistical learning: Data mining, inference, and prediction)Zhou (2012, Ensemble methods: Foundations and algorithms) などを読むと良い.

*22:あらゆる変数が制御可能ということはあまりないため, 一部の変数だけでもよいから特定したい, という場合はよくある.

*23:さらに言えば, OP, LP, ACF の論文では, モデルに追加の仮定を設けることで式をシンプルにすることで推定しやすくしている, という面もある

*24:このようなアイディアはこの論文が最初ではない. よく似たアイディアとして, リーフノードを特徴量に使うことで複雑な構造のデータに対しても線形モデルの予測性能を向上できるという方法が https://research.fb.com/publications/practical-lessons-from-predicting-clicks-on-ads-at-facebook/ で紹介されている.

*25:具体的な計算手順まで細かく解説するのはしんどいので, 興味があれば各自で調べてほしい.

*26:quantile regression forest というアルゴリズムが過去に提案されているようだが, これは, 予測値の期待値を平均ではなく中央値に寄せるようにしたランダムフォレストのバリエーションの1つであり, GRF とは直接の関係はない.