交互決定木

交代決定木(ADTree)は、分類のための機械学習手法です。これは決定木を一般化し、ブースティングと関連しています。

ADTree は、述語条件を指定する決定ノードと、単一の数値を含む予測ノードの交互の組み合わせで構成されます。インスタンスは、すべての決定ノードが true であるすべてのパスをたどり、通過した予測ノードを合計することによって、ADTree によって分類されます。

ADTreeはYoav FreundとLlew Masonによって導入されました。 ^[1] しかし、提示されたアルゴリズムにはいくつかの誤植がありました。その後、Bernhard Pfahringer、Geoffrey Holmes、Richard Kirkbyによって説明と最適化が提示されました。^[2]実装はWekaとJBoost で利用可能です。

オリジナルのブースティングアルゴリズムでは、通常、決定スタンプ または決定木のいずれかが弱い仮説として使用されていました。たとえば、ブースティング決定スタンプでは、重み付けされた決定スタンプのセット( ブースティングの反復回数) が作成され、重みに応じて最終的な分類に投票します。個々の決定スタンプは、データを分類する能力に応じて重み付けされます。 ${\displaystyle T}$${\displaystyle T}$

単純な学習者をブーストすると、構造化されていない仮説セットが生成され、属性間の相関関係を推測することが難しくなります。交互決定木は、以前の反復で生成された仮説に基づいて仮説セットを構築することを要求することで、仮説セットに構造を導入します。結果として得られる仮説セットは、仮説とその「親」の関係に基づいてツリーで視覚化できます。 ${\displaystyle T}$

ブースト アルゴリズムのもう 1 つの重要な特徴は、反復ごとにデータに異なる分布が与えられることです。誤分類されたインスタンスには大きな重みが与えられ、正確に分類されたインスタンスには小さな重みが与えられます。

交互決定木は、決定ノードと予測ノードで構成されます。 決定ノードは述語条件を指定します。 予測ノードには 1 つの数値が含まれます。ADTree には常に、ルートとリーフの両方に予測ノードがあります。インスタンスは、すべての決定ノードが true であるすべてのパスをたどり、通過した予測ノードを合計することで、ADTree によって分類されます。これは、インスタンスがツリー内の 1 つのパスのみをたどる CART (分類および回帰ツリー) やC4.5などのバイナリ分類ツリーとは異なります。

以下のツリーは、スパムベースデータセット^[3]（UCI機械学習リポジトリから入手可能）上でJBoostを使用して構築された。^[4] この例では、スパムは次のようにコード化されている。1通常の電子メールは次のようにコード化されます−1。

次の表には、単一インスタンスの情報の一部が含まれています。

インスタンスは、通過するすべての予測ノードを合計することによってスコア付けされます。上記のインスタンスの場合、スコアは次のように計算されます。

最終スコア0.657は正なので、インスタンスはスパムとして分類されます。値の大きさは予測の信頼度を表します。元の著者は、ADTree によって識別される属性セットの解釈の 3 つのレベルを挙げています。

• 個々のノードは、独自の予測能力に基づいて評価できます。
• 同じパス上のノードのセットは共同効果を持つと解釈される可能性がある
• ツリーは全体として解釈できます。

スコアは各反復におけるデータの重み付けを反映しているため、個々のノードを解釈する際には注意が必要です。

交互決定木アルゴリズムへの入力は次のとおりです。

• 入力のセット。は属性のベクトルであり、-1 または 1 のいずれかです。入力はインスタンスとも呼ばれます。${\displaystyle (x_{1},y_{1}),\ldots ,(x_{m},y_{m})}$${\displaystyle x_{i}}$${\displaystyle y_{i}}$
• 各インスタンスに対応する重みのセット。${\displaystyle w_{i}}$

ADTree アルゴリズムの基本要素はルールです。 1 つのルールは、前提条件、条件、および 2 つのスコアで構成されます。条件は、「属性 <比較> 値」という形式の述語です。前提条件は、条件の論理結合にすぎません。ルールの評価には、ネストされた if ステートメントのペアが含まれます。

1   if (前提条件)
2       if (条件)
3          スコア1を返す
4      そうでない場合は
5          スコア2を返す
6      終了
7  そうでない場合
8       0を返す
9  終了の場合

アルゴリズムにはいくつかの補助機能も必要です。

• ${\displaystyle W_{+}(c)}$述語を満たすすべての肯定ラベル付き例の重みの合計を返します。${\displaystyle c}$
• ${\displaystyle W_{-}(c)}$述語を満たすすべての否定ラベル付き例の重みの合計を返します。${\displaystyle c}$
• ${\displaystyle W(c)=W_{+}(c)+W_{-}(c)}$述語を満たすすべての例の重みの合計を返します${\displaystyle c}$

アルゴリズムは次のとおりです。

1  関数ad_tree
2  入力m個のトレーニングインスタンスのセット
3
4   w i = 1/ m for all i 
5   
6   R 0 =スコアaおよび0、前提条件「true」、条件「true」を持つルール。${\displaystyle a={\frac {1}{2}}{\textrm {ln}}{\frac {W_{+}(true)}{W_{-}(true)}}}$
7   
8  すべての可能な条件の集合
9  に対して
10 を      最小化する値を取得
11       
12       
13       
14       R j =前提条件p、条件c、重みa 1とa 2を持つ新しいルール
15       
16  に対して終了
17   R jの集合を返す${\displaystyle {\mathcal {P}}=\{true\}}$${\displaystyle {\mathcal {C}}=}}$ ${\displaystyle j=1\dots T}$${\displaystyle p\in {\mathcal {P}},c\in {\mathcal {C}}}$ ${\displaystyle z=2\left({\sqrt {W_{+}(p\wedge c)W_{-}(p\wedge c)}}+{\sqrt {W_{+}(p\wedge \neg c)W_{-}(p\wedge \neg c)}}\right)+W(\neg p)}$${\displaystyle {\mathcal {P}}+=p\wedge c+p\wedge \neg c}$${\displaystyle a_{1}={\frac {1}{2}}{\textrm {ln}}{\frac {W_{+}(p\wedge c)+1}{W_{-}(p\wedge c)+1}}}$${\displaystyle a_{2}={\frac {1}{2}}{\textrm {ln}}{\frac {W_{+}(p\wedge \neg c)+1}{W_{-}(p\wedge \neg c)+1}}}$${\displaystyle w_{i}=w_{i}e^{-y_{i}R_{j}(x_{i})}}$

セットは各反復で 2 つの前提条件ずつ増加し、後続の各ルールで使用される前提条件を書き留めることで、ルール セットのツリー構造を導出できます。 ${\displaystyle {\mathcal {P}}}$

原著論文^{[1]の図6は、ADTreeがブースト決定木やブースト}決定スタンプと同じくらい堅牢であることを示しています。通常、再帰分割アルゴリズムよりもはるかに単純なツリー構造で同等の精度を達成できます。

• Boosting と ADTrees の紹介 (実際の交互決定木のグラフィカルな例が多数あります)。
• ADTree を実装する JBoost ソフトウェア。