NeurIPS2022にて「決定木の羅生門集合構築技術」について発表します

こんにちは．人工知能研究所発見数理PJの高木です．富士通研究所では「AIを用いた知識発見」に関する研究開発を行っています．このたび，デューク大学のInterpretable Machine Learning Lab （解釈可能機械学習研究室）との共同研究成果である「決定木の羅生門集合構築技術」が機械学習の主要な国際会議であるNeurIPS2022に採択されたので，その内容を紹介します．

対象論文

タイトル： Exploring the Whole Rashomon Set of Sparse Decision Trees (Rui Xin, Chudi Zhong, Zhi Chen, Takuya Takagi, Margo Seltzer, Cynthia Rudin)
発表会議：Thirty-sixth Conference on Neural Information Processing Systems (NeurIPS 2022)
論文へのリンク

採択された論文の内容

概要

予測モデルを用いた知識発見の手法として，人間が解釈可能なホワイトボックスモデル（決定木やルールセット，Lassoモデルなど）を構築する手法があります．既存研究では目的関数を最小化するモデル１つを出力することを目的としています．しかしながら，Leo Breimanが指摘したように「データをうまく説明できるモデルは複数存在する」という羅生門効果（Rashomon Effect）が知られています[1]．羅生門効果は，芥川龍之介の小説『藪の中』を原作とした黒澤明監督の映画『羅生門』における「ひとつの事象に対する見解が互いに矛盾してしまう状況」から命名されました．さきほど述べた通り羅生門効果は機械学習における知識発見においても有効であり，データを説明するのに最適なモデルは1つだけではないため，多様なモデルを構築することでこれまで見逃していた知識を発見できることを示唆しています．そこで本論文では最適な訓練精度とほとんど変わらない精度を達成する予測モデルをすべて格納した羅生門集合（Rashomon Set）の構築を目標としました．もし羅生門集合を構築することができれば解釈可能性や公平性，特定の特徴量を使用しているか，などの特性を指定して該当するモデルの一覧を得ることができます．また羅生門集合内から自身の専門知識と一致するモデルを選択することもできますし，それとは逆に非自明な説明をしているモデルを選択し知識発見につなげることもできます．このように単一の予測モデルを提供するのではなく複数モデル（羅生門集合）を出力することは説明可能性・知識発見のために今後ますます重要になっていくと考えられます．

しかしながら，非線形なモデルに対する羅生門集合の構築は計算量の観点から非常に困難です．例えば本論文で扱う疎な決定木（Sparse Decision Tree）を考えてみます．深さ4で2値特徴量が10個しかない木でさえ，とりえる木の数（仮説空間の大きさ）は $9.338 \times 10^{20}$ 個以上になります．そのためこれらの木をすべてを構築し，その精度を測定して愚直に羅生門集合に格納するかどうかを判定する手法では現実時間で羅生門集合を構築することはできません．これまで，決定木クラスに限らず相互作用を持つ非線形なモデルに対する羅生門集合構築に成功した先行研究はありませんでした．

疎な決定木の仮説空間は巨大ですが，良い決定木の集合である羅生門集合はその小さな部分集合になっています．実際，仮説空間全体が大きすぎて列挙できない場合でも羅生門集合自体は保持できるほど小さいこともあります．そこで，全ての疎な決定木を列挙して羅生門集合に含まれるものだけを保存するのではなく，解析的境界（analytical bounds）を用いることで羅生門集合のメンバーに含まれない部分を安全に除外（枝刈り）するようにしました．これにより羅生門集合のメンバーを含む空間の部分だけに焦点を合わせることができます．また，羅生門集合を新たに提案するデータ構造に格納することで，メモリ効率の良い保持と羅生門集合のメンバーへの容易なアクセスを可能にしました．これらの枝刈りと効率的な表現の組み合わせにより実世界のデータセットにおける疎な決定木に対する羅生門集合の完全な列挙アルゴリズムを初めて提案することができました．

羅生門集合は問題を検討する際に新しい指標を与えます．例えば，羅生門集合はどのくらいの大きさか？　その大きさはデータセットによって違うのか？　羅生門集合の木の間で変数の重要度はどのように変化しているか？　などです．これらの質問により，ある変数が1つのモデルに対してだけでなく，データセットに対してどの程度重要であるかがより良く理解できる可能性があります．

疎な決定木（Sparse Decision Tree）と羅生門集合の定義

まず本論文で扱う疎な決定木を定義します．訓練データを ${(\textbf{x}_i, \textbf{y}_i)}_{i=1}^n$ ，ここで $\textbf{x} _i \in \{0,1\}^p$ , $y_i \in \{0,1\}$ とします．マルチラベルにも拡張可能ですが簡単のため本記事では二値とします．木の損失を $\ell(t, \textbf{x}, \textbf{y}) = \frac{1}{n}\sum_{i=1}^n\mathbf{1}[\hat{y}_i \neq y_i]$ と定義し，最小化したい目的関数を，葉の数 $H_t$ を正則化項とした $Obj(t, \textbf{x}, \textbf{y}) = \ell(t, \textbf{x}, \textbf{y}) + \lambda H_t$ とします．これを目的関数とした決定木は疎な決定木と呼ばれます[2]．

次にこの決定木に対する羅生門集合を定義します．

定義：ε-羅生門集合

$t_{\textrm{ref}}$ を決定木の集合 $\mathcal{T}$ のベンチマークモデルとします． $\epsilon$ -羅生門集合 $R_{\textrm{set}}(\epsilon, t_{\textrm{ref}}, \mathcal{T})$ は，目的関数値が高々ベンチマークモデルの $1 + \epsilon$ 倍である木 $t\in \mathcal{T}$ からなる集合です．すなわち，

$\displaystyle R_{\textrm{set}}(\epsilon, t_{\textrm{ref}}, \mathcal{T}) := {t \in \mathcal{T} : Obj(t,\textbf{x},\textbf{y}) \leq (1+\epsilon) \times Obj(t_{\textrm{ref}},\textbf{x},\textbf{y}) }$

です．以下ではベンチマークモデルを訓練データに対して目的関数を最小化する最適なモデルとします．

探索空間の枝刈り

羅生門集合の構築のために探索空間を縮小するための枝刈りを考えます．動的計画法で決定木を成長させていく際，その葉の一部は決定済み（fixed）であり、他の一部はまだ決定されていない（unfixed）と考えられます．このような場合，木のすべてのunfixedな葉が最良の分類性能を持つと仮定します．これにより，目的関数の下界を見積もることができます．この下界と羅生門集合の目的関数値の閾値である $\theta_{\epsilon}$ を比較します．目的関数の下界が $\theta_{\epsilon}$ より大きい，つまり性能が悪い場合，決定木をどのように拡張しても決して羅生門集合に入らないことが分かります．そのため木の拡張は無意味であり，探索空間を縮小することができます．

これを定理として以下に示します．

まず各部分木 $t$ を次の5つ変数で表現します． $t_{fix}$ を拡張しないfixedな葉， ${\delta}_{fix}$ をfixed葉内のデータ点のラベル， $t_{split}$ を分割される可能性のあるunfixed葉（同様にデータ点のラベルを $\delta_{split}$ とします) ， $H_t$ は現在の木の葉の数とします．これを用いると探索空間における現在位置は部分木 $t = (t_{fix},\delta_{fix}, t_{split}, \delta_{split}, H_t)$ で表現可能です．

定理：下界による枝刈り

羅生門集合の閾値を $\theta_{\epsilon}$ とする． $t$ を葉 $t_{fix}, t_{split}$ をもつ決定木とし，目的関数の下界を $b(t_{fix}, \textbf{x}, \textbf{y}):=\ell(t_{fix}, \textbf{x}, \textbf{y})+\lambda H_t$ とする. このとき，もし $b(t_{fix}, \textbf{x}, \textbf{y}) > \theta_{\epsilon}$ ならば， $t$ とそのすべての子（葉を拡張したもの）は $\epsilon$ -羅生門集合ではない．

この定理はよりタイトな下界を用いることができますが，ここでは省略し詳細は論文に譲ります．

実験結果

他列挙手法との比較

まず，そもそもランダムフォレストなど決定木を複数構築する手法と厳密に羅生門集合を構築した場合を比較します．

TreeFARMSが我々の提案手法です．縦軸は列挙された決定木の目的関数値を示します．横軸は列挙した決定木を目的関数値が小さい順に並べたものです．黒い破線は羅生門集合の閾値です．今回は最適な決定木の1.1倍の目的関数値を達成する決定木の集合を列挙しています（すなわち， $\epsilon = 0.1$ ）．各手法名のカッコ内の数字は，分母が列挙した決定木の数，分子がそのうち羅生門集合に入る数です．

提案手法は厳密に羅生門集合を構築しますが，たとえばランダムフォレスト（RF）により構築される決定木は最もよい目的関数値を達成するものでも羅生門集合に入らない（すなわち，最適なものと比べて大きく精度が低い）ものになっています．他の手法を用いても羅生門集合に入る決定木をかなりの数見逃していることが分かります．

羅生門集合による特徴量重要度（MCR）

羅生門集合を構築することで，データセットに対する新たな特徴量重要度 Model Class Reliance（MCR）を定義することができます．MCRは簡単に言うと特徴量重要度の範囲を提供するものです．過去の研究では，線形モデルの凸損失に対してのみ$MCRを計算することができました[3]. 決定木の場合この問題は非凸であり、従来の手法では解決できませんでした．しかし本論文の結果を用いて羅生門集合の全ての木について重要度を計算し，その最小値と最大値を求めてMCRを計算することが可能です．

このデータセットはバーのクーポンを受け取ってくれるか否かを予測するものです．赤い点は最適な決定木が示す重要度です．たとえばchildrennumber_0（子供の数が０人）という特徴は，最適決定木上では重要視していませんが，他のほとんど同じ精度を達成する決定木（羅生門集合のメンバー）はある程度重視していることが分かります．このように，従来の手法では見逃していた重要な特徴を羅生門集合を用いることで見つけることが期待できます．

参考文献

[1]: Leo Breiman. Statistical modeling: The two cultures (with comments and a rejoinder by the author). Statistical Science, 16(3):199–231, 2001.
[2]: Jimmy Lin, Chudi Zhong, Diane Hu, Cynthia Rudin, and Margo Seltzer. Generalized and scalable optimal sparse decision trees. In International Conference on Machine Learning, pages 6150–6160. PMLR, 2020.
[3]: Aaron Fisher, Cynthia Rudin, and Francesca Dominici. All models are wrong, but many are useful: Learning a variable’s importance by studying an entire class of prediction models simultaneously. Journal of Machine Learning Research, 20(177):1–81, 2019

fltech - 富士通研究所の技術ブログ

富士通研究所の研究員がさまざまなテーマで語る技術ブログ