ランダムフォレスト「マージン」の謎

僕が仕事でメインに扱っているのはSASだったりするのですが、SASは機械学習というよりは統計解析寄りのソフトです。そのため、分析屋もどきの身からすると、その出力もやや見慣れないものだったりします。

先日SASのプロシージャでランダムフォレストを弄っていたところ特徴量重要度の出力で「マージン」なる項目があり、聞きなれないワードだったので公式ドキュメントを読み解いてみました。

なお、この記事は個人的な備忘録として作成しています。

1. 前提：エントロピーやらGini不純度やら

そもそも決定木系の学習アルゴリズムの重要度と言えば、エントロピーやGini不純度を用いたものが主流ではないでしょうか。

Gini不純度やエントロピーは、集合の中に複数の要素がどの程度均一に含まれるかを定量化した値です。ある基準でノードを分割したとき、分岐元のノードと分岐先のノードのエントロピーまたはGini不純度の差分が大きいほど、「その基準によるノードの分割が効果的だった」と言えるわけです。そして、ある特徴量を基準とした分割のGini不純度の差分の総和を取ることで、その特徴量がモデル全体として判別力にどの程度寄与したか定量化することができる、というわけです。

エントロピーやGini不純度、および決定木のアルゴリズムについてはこちらの記事の解説がわかりやすかったので、ご参考にどうぞ。

qiita.com

重要度の説明はこちらの記事がわかりやすかったです。

yolo-kiyoshi.com

2. しれっと出力されてる「マージン」って何これ

で、そんな前提知識を踏まえつつSASのhpforestプロシージャでランダムフォレストを組んでみます。

ざっくりこんな感じのコードをかいて実行すると、、、、

f:id:toeming:20200519124925p:plain

こんな感じで重要度が出力されます。しれっと「マージン」が出力されていますね。

f:id:toeming:20200519124422p:plain

ここで、「マージンてなんやねん」という疑問にぶち当たったわけです。

いや、マージンという言葉自体はなんとなくわかるのですが、ランダムフォレストの特徴量の重要度とどんな関係があるのでしょうか。

調べてみてわかったことを要約すると、あるサンプルに含まれる各クラスの割合のクラス間差分をマージンと呼ぶようです。そして、これを用いてノード内のクラスの偏りや分岐条件の良し悪しを評価し、各特徴量の重要度を定量化した結果が「マージン」として出力されているようです。

3. マージンを用いた重要度の算出

ということで、マージンを用いた重要度の算出方法についてSAS公式のこちらのドキュメントを（僕の怪しい英語力と、今話題のDeepL先生のお力添えで）読み解いてわかったことを以下にまとめていきます。

大意は掴めてると思いますが、細かいところ間違ってたらごめんなさい。

3.1. ノード内のマージン

マージンは、ノード内のサンプルがどの程度偏っているかの指標となります。あるノードのマージンが高いほど、そのノードに含まれるクラスごとのサンプルサイズの差が大きく、クラス判別に有効であると言えます。

実際に評価値として使用されるのはSNM（"Sum of the Negative of Margin" の略？）というマージンにマイナスをかけた値です。

ノード内におけるSNMは以下の式で計算されます。

$\displaystyle SNM(w) = -\sum_{j=1}^J N_j(p_j - \max_{k\not=j} p_k)$

ただし、

$w$ : ノード

$SNM(w)$ : ノード $w$ におけるマージンの評価値

$J$ : サンプルのクラス数

$N_j$ : クラス $j$ のサンプル数

$p_j$ : クラス $j$ の割合（ノード内の $N_j$ / ノード内の全サンプル数）

はい、意味不明です。本当にありがとうございました。

とはいえ諦めるのはまだ早いので、がんばって具体例で考えてみます。

以下のようなノードのマージン（SNM）を考えてみましょう。

データセットの各サンプルにはA,B,Cの3クラスが割り振られている。
あるノード $w$ 内の各クラスのサンプル数は、(A, B, C) = (50, 40, 30)とする。

まず、先ほどの式を改めて考えてみます。

今回の例に添わせて日本語で式を解釈すると、こんな感じになります。

ノード $w$ のSNM

　= - { クラスAのサンプル数 × ( クラスAの割合 - クラスA以外の割合の最大値 )

　　+ クラスBのサンプル数 × ( クラスBの割合 - クラスB以外の割合の最大値 )

　　+ クラスCのサンプル数 × ( クラスCの割合 - クラスC以外の割合の最大値 ) }

あとは算数の問題です。前もって各クラスの割合を計算しておきます。

クラスAの割合 = 50 / ( 50+40+30) = 5/12

クラスBの割合 = 40 / ( 50+40+30) = 1/3

クラスCの割合 = 30 / ( 50+40+30) = 1/4

で、本題のマージンの計算です。SNMの計算式に代入します。

SNM

　= - { 50 × ( 5/12 - 1/3 )

　　+ 40 × ( 1/3 - 5/12 )

　　+ 30 × (1/4 - 5/12) }

　= 25/6

※ $\max_{k\not=j} p_k$ の部分は、自分以外のクラスの最大のクラスの割合を意味しています。例えば、”クラスA以外の割合の最大値” は、クラスB,Cの割のうち、大きい方のクラスBの割合(1/3) が採用されます。

はい、こんな感じでノードのSNMが計算できました。

ノードにおける各クラスの含有率に偏りがある（1つのクラスのサンプルサイズが極端に多く、他のクラスのサンプルサイズは極端に少ないような状態）ほど、そのノードにおけるマージンは大きくなります。そのため、ジニ不純度などと同じように、マージンによってノード内のクラスの偏りを評価することができます。

なお、評価値であるSNMがマージンにマイナスをかけた値になっているのは、ジニ不純度などと同様に低いほど偏りがある指標となるように調整するためです。

3.2. マージンの差分

次に、マージンの差分について考えてみます。

マージン（正確にはSNM）の差分を損失と呼び、以下の式で表されます。

$\displaystyle Loss(w) = SNM(w) -\sum_{b \in B(w)} SNM(w_b)$

ただし、

$Loss(w)$ : ノード $w$ での分岐による損失（マージンの差分）

$B(w)$ : ノード $w$ からの分岐の集合

$w_b$ : ノード $w$ からの分岐したノード