迅速で節約的な木

高速かつ質素な木 または マッチングヒューリスティック^{[1] (}意思決定の研究において) は、一度に 1 つの質問をすることでオブジェクトを分類する単純なグラフィカル構造です。これらの決定木は、心理学、人工知能、経営科学など、さまざまな分野で使用されています。レオ・ブレイマンの CART ^[2]などの他の決定木や分類 木とは異なり、高速かつ質素な木は、構築と実行の両方において意図的に単純化されており、少ない情報で迅速に動作します。このため、高速かつ質素な木は、リソースが制限されたタスクを設計する際に魅力的である可能性があります。^[3]

ローラ・マルティニョン、ヴィトーシュ、タケザワ、フォースターは2003年に初めてこの概念と用語を導入しました。^[4]ゲルト・ギゲレンツァーとハーバート・A・サイモンによって作成された正式なモデルに基づいて、他のタスクに対する同様のヒューリスティックが以前に使用されていました。

2 つのオプションと、そのような決定を行うために利用できるm個の手がかり (特徴または属性とも呼ばれる) がある分類タスクでは、FFT は次のように定義されます。

高速かつ簡素なツリーは、最初の m −1 個のキューのそれぞれに 1 つの出口があり、最後のキューに 2 つの出口がある、m+1 個の出口を持つ分類ツリーまたは決定ツリーです。

数学的には、高速かつ簡素な木は辞書式ヒューリスティックス、または非補償重みと閾値を持つ線形分類モデルとして見ることができます。^[MKW]それらの形式的な特性と構成は、2011年にLuan、Schooler、Gigerenzerによって信号検出理論を使用して分析されました。^{[5] [LSG]}

基本要素はキューです。キューはランク付けされており、ツリーの各レベルに 1 つのキュー、各レベルに 1 つの終了ノードがあります (ツリーの最後のレベルにある最後のキューの 2 つの終了ノードを除く)。キューが使用されるたびに、キューの値に関する質問が行われます。質問に対する回答は、すぐに終了につながる場合もあれば、さらに別の質問につながる場合もあります (最終的には終了につながります)。高速で簡素なツリーの特徴は、各質問に対して、終了につながる可能性のある回答が少なくとも 1 つあることです。

高速かつ簡素なツリーに関する文献では、(1) キューを順序付けし、(2) キューに関する質問に対するどの可能な回答が出口に直接つながるかを決定するためのさまざまなアルゴリズムが提案されています[4 ^{] [MKW] [LSG] [6]。}高速かつ簡素なツリーは、次の条件の両方が満たされている場合に完全に定義されます。多くの場合、構築を単純かつ直感的に保つために、アルゴリズムは (1) キューの「良さ」の単純な尺度 (たとえば、キュ​​ーとカテゴリ間の相関関係、各キューを他のキューとは独立して考慮する) と (2) 出口に関する単純な選択 (たとえば、各出口を他の出口とは独立して決定する) を使用しますが、より複雑なアルゴリズムも提案されています。

高速で質素なツリーを使用するには、ルートから始めて、一度に 1 つのキューをチェックします。各ステップで、可能な結果の 1 つは、決定 (またはアクション) を可能にする出口ノードです。出口に到達した場合は停止し、それ以外の場合は出口に到達するまで続行します。出口を出て停止し、それ以外の場合は続行し、出口に到達するまでさらに質問します。

図 1 は、患者を心臓発作の「リスクが高い」と分類して「冠動脈疾患治療室」に送る必要があるか、または「リスクが低い」と分類して「通常の看護ベッド」に送る必要があるかを判断するための簡素なツリーを示しています (Green & Mehr、1997)。^[GM]

ジョン、メアリー、ジャックという 3 人の患者について考えてみましょう。

• ジョンはST セグメントの変化があるため、「高リスク」と分類され、他の兆候を考慮せずに冠動脈ケアユニットに送られます。
• メアリーはST 部分の変化がなく、主な訴えとして胸痛がありますが、残りの 5 つの要因はいずれもないため、3 つの兆候がすべて確認された後、「低リスク」と分類され、通常の介護ベッドに送られます。
• ジャックはST 部分の変化がなく、主訴は胸痛ではないため、これら 2 つの兆候を考慮して「低リスク」と分類され、通常の看護ベッドに送られます。

高速かつ簡素なツリーの精度と堅牢性は、LaskeyとMartignon (2014) の研究ではベイジアンベンチマークに匹敵することが示されています。^[LM]また、高速かつ簡素なツリーのパフォーマンスを、ナイーブベイズ、CART、ランダムフォレスト、ロジスティック回帰などの統計や機械学習で使用される分類アルゴリズムと比較する広範な研究も、数十の実際のデータセットを使用して実施されています。^{[WHM] [MKW] [6]}

高速かつ簡素な木は、バイナリ分類や決定を実行するために使用されます。心理学、医学、その他の分野では、信号検出理論 (または検出理論) が、このようなタスクを分析するための古典的な理論となっています。

この理論では、イベントまたは人物には 2 つのカテゴリ (心臓に問題のある人とない人など) があり、私たちにとってより関連のあるカテゴリは「シグナル」と呼ばれ、もう 1 つは「ノイズ」と呼ばれていると想定しています。この 2 つは、私たちが「証拠」と呼ぶことができる観察スケールでの分布が異なり、シグナル分布の方が平均が高くなっています。証拠を収集すると、「シグナル」または「ノイズ」という 2 つの分類が可能になります。これにより、ヒット (実際にはシグナルであるのに「シグナル」として分類)、正しい拒否 (実際にはノイズであるのに「ノイズ」として分類)、ミス (実際にはシグナルであるのに「ノイズ」として分類)、誤報 (実際にはノイズであるのに「シグナル」として分類) という 4 つの結果が考えられます。全体的な精度または分類の期待値を最大化するには、この理論では、証拠スケールで分類基準を慎重に選択し、それを超えると「シグナル」と判定し、それ以下の場合は「ノイズ」と判定する必要があるとしています。特に、誤報のコストが非常に高い場合 (心臓疾患のある患者を正常と分類するなど)、より低く、より「寛容な」基準 (証拠スケールの左側) を選択する必要がありますが、誤報のコストが非常に高い場合 (無実の人を殺人罪で有罪と分類するなど)、より高く、より「保守的な」基準の方が適しています。これは、ほとんどの現実の状況において、優れた意思決定者は適切なバイアスを持つ必要があることを意味します。これは、分類と意思決定に関する信号検出理論から得られる最も重要で関連性のある洞察です。

2011 年、Luan、Schooler、および Gigerenzer は、信号検出理論の観点から高速かつ簡素なツリーの特性を分析しました。この分析から、いくつかの重要な発見がありました。まず、高速かつ簡素なツリーの出口構造の選択は、信号検出の決定基準の設定に対応します。簡単に言えば、高速かつ簡素なツリーで「信号出口」が早く現れるほど、ツリーのバイアスはよりリベラルになります。2 つの高速かつ簡素なツリーの相対的なバイアスは、2 つのツリーが異なる最初の出口によって決定され、「信号出口」 (「s」で示される) を持つツリーは、「ノイズ出口」 (「n」で示される) を持つツリーよりも常にリベラルになります (図 2)。たとえば、FFTsnnn (ここでも s = 「信号出口」、n = 「ノイズ出口」) は、FFTnsss よりもリベラルなバイアスになります。この原理は、高速かつ簡素なツリーの「辞書式決定バイアス」と呼ばれます。

第二に、一連のシミュレーションにより、異なる出口構造を持つ高速かつ簡素なツリーは、ミスと誤報の結果が異なる場合、決定の期待値が異なり、場合によっては大幅に異なることが示されています。したがって、高速かつ簡素なツリーを構築して適用する場合は、タスクの決定の報酬構造とよく一致する出口構造を選択する必要があります。

3 番目に、高速かつ簡素なツリーの全体的な感度 (つまり、ツリーが信号とノイズをどれだけうまく区別できるか、信号検出理論の d' または A' で測定できる) は、キューの感度の平均と分散、キュー間のキュー間相関など、ツリーを構成するキューの特性によって影響を受けますが、ツリーの出口構造によってはあまり影響を受けません。そして最後に、高速かつ簡素なツリーのパフォーマンスは堅牢で、理想的な観察者分析モデルや最適な順次サンプリング モデルなど、信号検出理論で開発されたはるかに洗練された決定アルゴリズムに匹敵します。サンプル外予測のコンテキストでは、学習サンプル サイズが比較的小さい場合 (たとえば、80 試行未満)、高速かつ簡素なツリーは他のモデルと比較して最高のパフォーマンスを発揮します。

2017年に、Phillips、Neth、Woike、Gaissmaier ^[PNWG]は、CRANでホストされているRパッケージFFTrees ^{[7] （付属アプリ[8]}付き）を発表しました。これは、ユーザーフレンドリーな方法で、高速で質素なツリーを構築し、グラフィカルに描画し、定量的に評価します。

高速倹約ツリーは、意思決定の方法の規定と、人々が実際に意思決定を行う方法の記述の両方において、数多く応用されてきました。医療分野以外では、規定的な応用例として、アフガニスタンに駐留する兵士に、検問所に近づいてくる車が民間人か自爆テロリストの可能性がある人のどちらを運転しているかを区別する方法を指導することが挙げられます。^{[9] [KK]}このツリーは図 3 に示されています。高速倹約ツリーの記述的使用例を 2 つ図 4 に示します。左側と右側のツリーはそれぞれ、ある人が社交中に犯した犯罪を許すかどうかを決定する方法^[TLK]と、英国の裁判官が保釈か投獄かの決定を下す方法を説明しています。^[D]一般に、高速倹約ツリーは、複数の手がかりが関係するあらゆる二者択一の意思決定プロセスを支援またはモデル化するために適用できます。