Loading article…
情報理論および機械学習における決定木の文脈では、情報利得とは、ある変数の単変量確率分布と、別の変数が与えられた場合のその変数の条件付き分布との間のカルバック・ライブラー情報量の条件付き期待値を指します。（より広い文脈では、情報利得はカルバック・ライブラー情報量または相互情報量の同義語として使用されることもありますが、この記事では以下のより狭義の意味に焦点を当てます。）
具体的には、確率変数の情報利得はランダム変数の観測から得られた価値を追求するは次のように定義されます。
言い換えれば、それはカルバック・ライブラー発散であり、（） から（事後分布与えられた)
すなわち、エントロピーの減少ランダム変数の状態を学習することによって達成される。
機械学習では、この概念を使用して、 Xの状態を最も迅速に絞り込むために調査する属性の優先シーケンスを定義できます。このようなシーケンス (各段階での以前の属性の調査結果に依存します) は決定木と呼ばれ、機械学習の分野で適用される場合は決定木学習として知られています。通常、ターゲット変数との相互情報量が高い属性が優先されます。これは、相互情報量が、その属性で分割することによって得られるエントロピー (情報利得) の期待される減少量に相当するためです。[ 1 ]
一般的に言えば、期待される情報利得とは、ある情報が所与の状態である状態から、以前の状態への情報エントロピーΗの減少量である。
どこは条件付きエントロピーである属性の値を考慮すると。
エントロピーΗを確率変数の不確実性の尺度として解釈する場合、これは直感的に妥当である。: 学習（または仮定）によってについて不確実性について減少する（つまりもちろん、独立しているその場合、 意味。
T をトレーニング例の集合とし、各例の形式は次のとおりとする。どこの値は例の属性または特徴yは対応するクラスラベルである。属性aの情報利得はシャノンエントロピーによって定義される。以下のように。属性aが取る値vに対して、を、属性aがvと等しいTのトレーニング入力の集合として定義する。すると、属性aに対するTの情報利得は、事前シャノンエントロピーの差となる。トレーニングセットと条件付きエントロピー。
相互情報量は、各属性値に対して結果属性の一意の分類が可能であれば、属性の総エントロピーと等しくなります。この場合、総エントロピーから差し引かれる相対エントロピーは 0 になります。特に、値はトレーニングセットデータTを相互に排他的かつ包括的なサブセットに分割し、カテゴリカル確率分布を誘導する。値について属性aの分布は次のように与えられます。この表現では、 aが与えられたときのTの情報利得は、Tの無条件シャノンエントロピーと a を条件とした T の期待エントロピーとの差として定義できます。ここで、期待値はaの値に関する誘導分布に関して取られます 。
工学的な応用では、情報は信号に、エントロピーはノイズに相当します。エントロピーは、決定木がデータをどのように分割するかを決定します。[ 2 ]下の左端の図は非常に不純で、高いエントロピーは高い無秩序と低い情報価値に対応しています。右に進むにつれて、エントロピーは減少し、情報価値は増加します。
さて、情報利得とは、ある特徴量がクラスについてどれだけの情報を提供するかを示す尺度であることは明らかです。右図に示すように、情報利得を決定木で視覚化してみましょう。
ノードtは親ノードであり、サブノードt Lとt Rは子ノードです。この場合、親ノードtには、それぞれ C と NC で表される癌サンプルと非癌サンプルの集合があります。情報利得を用いて、決定木におけるノードの分割の良し悪しを判断できます。エントロピーの観点から、情報利得は次のように定義されます。
この考え方を理解するために、まずは簡単なデータセットを作成し、遺伝子変異が癌患者と関連しているかどうかを調べる例から始めましょう。4種類の遺伝子変異と7つのサンプルが与えられた場合、決定のためのトレーニングセットは次のように作成できます。
このデータセットでは、1はサンプルに突然変異があること（真）、0は突然変異がない（偽）ことを意味します。Cは癌であることが確認されたサンプル、NCは非癌であるサンプルを示します。このデータを用いて、情報利得によって各ノードの候補となる分割を決定する決定木を作成できます。
次のステップとして、上記の単純な決定木の親ノードtにおけるエントロピーは次のように計算されます。
H( t ) = − [ p C,t log 2 ( p C,t ) + p NC,t log 2 ( p NC,t )] [ 4 ]
どこ、
ノード t でクラス 'C' のサンプルを選択する確率、p C,t = n ( t, C) / n ( t ) 、
ノード t でクラス 'NC' サンプルを選択する確率、p NC,t = n ( t, NC) / n ( t ) 、
n ( t )、n ( t, C)、n ( t, NC)は、それぞれノードtにおける全サンプル数、「C」サンプル数、「NC」サンプル数です。
これを例のトレーニングセットで使用すると、情報利得を見つけるプロセスは、変異1については以下のとおりです。
注記：根元におけるすべての突然変異について、同じ結果となるでしょう。
エントロピーの値が比較的高い（1が最適値）は、ルートノードが非常に不純であり、ルートノードの入力の構成要素が上記のエントロピー図の左端の図のようになることを示唆しています。ただし、このようなデータセットは、ノードを分割するために使用される突然変異の属性を学習するのに適しています。あるノードで、入力の構成要素の均一性が発生すると（上記のエントロピー図の右端の図に示すように）、データセットは学習に適さなくなります。
次に、上記の決定木の左子ノードと右子ノードのエントロピーは、以下の式を用いて計算されます。
H( t L ) = − [ p C,L log 2 ( p C,L ) + p NC,L log 2 ( p NC,L )] [ 2 ]
H( t R ) = − [ p C,R log 2 ( p C,R ) + p NC,R log 2 ( p NC,R )] [ 2 ]
どこ、
左の子ノードでクラス「C」のサンプルを選択する確率、p C,L = n ( t L , C) / n ( t L )、
左の子ノードでクラス「NC」サンプルを選択する確率、p NC,L = n ( t L , NC) / n ( t L )、
右子ノードでクラス「C」のサンプルを選択する確率、p C,R = n ( t R , C) / n ( t R )、
右子ノードでクラス「NC」サンプルを選択する確率、p NC,R = n ( t R , NC) / n ( t R )、
n ( t L ) 、n ( t L , C) 、およびn ( t L , NC) は、それぞれ左の子ノードにおけるサンプルの総数、'C' サンプル数、および 'NC' サンプル数です。
n ( t R ) 、n ( t R , C) 、およびn ( t R , NC) は、それぞれ右の子ノードにおけるサンプルの総数、「C」サンプル、および「NC」サンプルの数です。
これらの式を用いると、突然変異1のH(t L )とH(t R )は以下のようになる。
これに続いて、上記の決定木のノードt での分割による子ノードの平均エントロピーは次のように計算されます。
H( s , t ) = P L H ( t L ) + P R H ( t R )
どこ、
左の子のサンプルの確率、P L = n ( t L ) / n ( t )、
右の子供におけるサンプルの確率、PR = n ( t R ) / n ( t )、
最後に、突然変異1におけるH (s,t)とPLおよびPRは以下のとおりです。
したがって、式（i）の定義により、次のようになります。
（情報利得）＝H( t ) - H( s , t )
すべてのステップを終えた後、例における候補分割sに対するgain( s )は次のようになります。
他の3つの突然変異にも同じ数式を適用すると、情報利得に基づいてランク付けされた候補となる分割の表が得られます。
最も有用な情報を提供する変異は変異3であるため、これを用いて決定木のルートノードを分割します。ルートを分割し、すべてのサンプルを通過させて子ノードに追加します。分割の様子を示すツリーを左側に示します。
ツリーの左側のノードにあるサンプルは癌と分類され、右側のノードにあるサンプルは非癌と分類されます。このツリーは、構築に使用されたサンプルの分類に関しては比較的正確ですが（これは過学習の一例です）、サンプルC2は依然として誤って分類されます。これを修正するために、ツリーを子ノードで再度分割することで、さらに正確な結果が得られる可能性があります。
適切なノードを分割するには、以前のノードで使用されなかったすべての可能な候補分割について、情報利得を再度計算する必要があります。したがって、今回選択できるのは、変異1、2、および4のみです。
注記：今回は、右側の子供にはサンプルが4つしかないため、状況が異なります。
この新しい候補となる分割は、ルートノードと同じ式を使用して計算できます。
したがって、右側の子供は変異4によって分割される。変異を持つサンプルはすべて左側の子供に渡され、変異を持たないサンプルは右側の子供に渡される。
左側のノードを分割する場合も手順は同じですが、チェックするサンプルは3つだけになります。ノードが純粋なセット、つまりノード内のすべてのサンプルが癌性または非癌性のみである場合は、ノードを分割する必要がない場合もあります。ノードを分割するとツリーの精度が低下する可能性があるため、この場合は分割されません。
構築に使用したサンプルでテストすれば、ツリーの精度は100%になります。しかし、これはツリーがデータに過学習してしまうため、良い方法ではありません。最善策は、元のデータセットに含まれていない他のサンプルでツリーをテストすることです。以下に、2つの外部サンプルを示します。
このツリーをたどると、NC10は正しく分類されましたが、C15はNCと分類されました。他のサンプルでは、このツリーの精度は100%ではなくなります。ただし、ツリーの深さを増やしたり、トレーニングセットのサイズを大きくしたりすることで、精度を向上させることは可能です。
情報利得は、特徴量をノード分割に用いるべきかどうかを判断するための基本的な基準です。最適な分割、すなわち決定木のノードにおける情報利得の値が最も高い特徴量が、ノード分割のための特徴量として使用されます。
情報利得関数の概念は、決定木を生成し、決定木ノードの最適な分割を選択するためのC4.5アルゴリズムに属します。 [ 2 ]その利点には以下のようなものがあります。
情報利得は通常、属性の関連性を判断するのに適した指標ですが、完璧ではありません。特に、情報利得を多数の異なる値を取り得る属性に適用する場合に問題が生じます。例えば、ある企業の顧客に関するデータに基づいて決定木を構築しているとします。情報利得は、どの属性が最も関連性が高いかを判断し、決定木の根元付近でテストするためによく用いられます。入力属性の一つとして、顧客が企業の会員プログラムに加入している場合の会員番号が挙げられます。この属性は各顧客を一意に識別するため相互情報量は高くなりますが、決定木には含めたくありません。会員番号に基づいて顧客への対応方法を決定すると、これまで見たことのない顧客には一般化できない可能性が高くなります（過学習）。この問題は、テスト対象のサンプルに多数の異なる値を持つ属性が複数ある場合にも発生する可能性があります。この場合、これらの属性それぞれの情報利得は、異なる値が少ない属性の情報利得よりもはるかに高くなる可能性があります。
この問題に対処するため、ロス・クインランは、情報利得が平均以上である属性の中から、情報利得比率が最も高い属性を選択することを提案した。 [ 6 ]これにより、決定木は、多数の異なる値を持つ属性を考慮することを抑制しつつ、情報値が情報利得以上であるため、情報値が非常に低い属性に不当な優位性を与えることはなくなる。[ 7 ]
![{\displaystyle \operatorname {E} _{A}[{\mathit {IG}}(X,A)]=I(X;A)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5552a64741b2fe470a565abf6a029338b7e942ca)
![{\displaystyle {\begin{alignedat}{2}IG(T,a)&=\mathrm {H} (T)-\sum _{v\in \mathrm {vals} (a)}{P_{a}{(v)}\mathrm {H} \left(S_{a}{(v)}\right)}\\&=\mathrm {H} (T)-\mathbb {E} _{P_{a}}{\left[\mathrm {H} {(S_{a}{(v)})}\right]}\\&=\mathrm {H} (T)-\mathrm {H} {(T|a)}.\end{alignedat}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/531fa7b5f713bf5e00d71c249f6a2e461737d1e7)
