決定リストは、分類または予測タスクを、順序付けられたif-thenルールの列として表現する機械学習モデルである。各ルールは、条件（1つ以上の入力特徴量に対するテスト）と結果（クラスラベルまたは予測値）から構成される。新しいインスタンスが提示されると、モデルはリストに現れる順序でルールを評価し、条件が満たされた最初のルールの結果が予測として返される。ルールが一致しない場合、デフォルトの結果、通常はトレーニングデータ内で最も一般的なクラスが使用される。この構造により、決定リストは本質的に解釈可能であり、決定プロセス全体を単純な線形の命令セットとして読み取ることができる。
決定リストはルールベース学習の一形態であり、階層的な分岐構造を使用する決定木とは異なる。決定リストの順次的な性質は、初期のルールが後期のルールよりも優先されることを意味し、複雑な決定境界のコンパクトな表現を可能にする。それらは、医療診断、信用スコアリング、法的推論など、説明可能性が重要となる領域で特に有用であり、Machine learningとArtificial intelligenceの文脈で広く研究されてきた。
歴史的起源
決定リストの概念は、1990年代初頭にコンピューター科学者のロナルド・リベストによって形式化され、1987年の論文「Learning Decision Lists」で紹介された。RSA暗号システムの研究で知られるリベストは、例からブール関数を学習する方法として決定リストを提案した。彼は、固定サイズの決定リストがPAC学習可能（おそらくほぼ正しい）であること、つまり合理的な数のトレーニング例から効率的に学習できることを示した。この理論的基盤により、決定リストは、当時は理解が不十分で訓練が困難だったニューラルネットワークなどのより複雑なモデルに対する実用的な代替手段として位置づけられた。
リベストの研究は、Carnegie Mellon Universityの研究者ross quinlanによって開発された決定木用のID3アルゴリズムなど、ルール帰納の初期の研究に基づいていた（提供されたスラッグリストには含まれていないが、その影響は顕著である）。決定リストは後に連続特徴量と多クラス問題を扱うように拡張され、帰納論理プログラミングの分野で定番となった。
アルゴリズムによる学習
データから決定リストを学習するには、通常、貪欲なアプローチが使用される。アルゴリズムは空のリストから始まり、トレーニングインスタンスのサブセットをカバーする最良のルールを反復的に選択し、それらのインスタンスを削除し、残りのデータに対してプロセスを繰り返す。「最良の」ルールは、多くの場合、精度、情報利得、またはカバレッジと精度の組み合わせなどのメトリクスに基づいて選択される。このプロセスは、すべてのインスタンスがカバーされるか、最小残存インスタンス数や最大リスト長などの停止基準が満たされるまで続行される。
このアルゴリズムの変種には、複数の候補ルールを同時に探索するビームサーチの使用や、過学習を回避するための枝刈り技術の組み込みが含まれる。例えば、1980年代後半に開発されたCN2アルゴリズムは、ビームサーチを使用して順序付けられたルールを誘導し、これは決定リスト学習と密接に関連している。より最近のアプローチでは、訓練されたNeural networkモデルからルールを抽出するプロセスであるルール抽出を通じて、決定リストをDeep learningと統合し、解釈可能性を向上させている。
応用と利点
決定リストの主な利点は、その透明性である。Large language modelやTransformer (architecture)ベースのシステムがブラックボックスとして動作するのとは異なり、決定リストは人間が検査して理解できるため、高リスクな決定に適している。例えば、医療分野では、決定リストは「年齢が60歳以上かつ血圧が140を超える場合、高リスク」などのルールをエンコードでき、臨床医が容易に検証できる。金融分野では、不正検出に使用され、各ルールは疑わしい行動の特定のパターンに対応する。
決定リストはまた、保存と実行が単純であるため、最小限の計算リソースを必要とする。これにより、Qualcomm搭載のモバイルデバイスやArm Holdingsベースのマイクロコントローラーなど、レイテンシが重要な組み込みシステムやリアルタイムアプリケーションに魅力的である。それらは、Chess computerプログラムでオープニングやエンドゲームのヒューリスティックをエンコードするために使用され、TomTomナビゲーションシステムで交通分類に使用されてきた。
他のモデルとの関係
決定リストは決定木と密接に関連しているが、構造が異なる。決定木は、各ルートからリーフへのパスをルールとしてたどることで、同等の決定リストに変換できるが、これによりリストが長くなる可能性がある。逆に、決定リストは、各ノードが最大1つの子を持つ縮退した木として表現できるが、これは常に効率的であるとは限らない。Machine learningの広範な状況では、決定リストは「ホワイトボックス」モデルの一種と見なされ、Deep learningネットワークなどの「ブラックボックス」モデルとは対照的である。それらは、より複雑なアルゴリズムとの比較のためのベースラインとしてよく使用され、ブースティングなどのアンサンブル手法で、複数の弱い決定リストが組み合わされる構成要素として機能する。
現代のAI研究では、決定リストは説明可能なAI（XAI）の文脈で新たな関心を集めている。MIT CSAILやStanford AI Labなどの機関の研究者は、Neural networkの予測から決定リストを生成する方法を探求し、Generative AIシステムによって行われた決定に対する人間が理解できる説明を提供することを目指している。このハイブリッドアプローチは、深層モデルの精度を活用しながら、ルールベースシステムの解釈可能性を保持する。
制限と拡張
決定リストの主な制限は、その表現力である。それらは、軸に沿った決定境界（つまり、各ルールが単一の特徴量または単純な条件の連言をテストする）のみを表現でき、特徴量間の複雑な相互作用を捉えられない場合がある。これにより、複雑なパターンを持つタスクでは、Residual Network (ResNet)やU-Netなどの非線形モデルと比較して精度が低下する可能性がある。さらに、貪欲な学習プロセスは最適ではないリストを生成する可能性があり、ルールの順序が重要であり、初期の過度に広範なルールがより具体的なルールを覆い隠す可能性がある。
これらの問題に対処するための拡張には、条件が真実の度合いを持つことを可能にするファジー決定リストや、信頼スコアを出力する確率的決定リストが含まれる。もう1つの拡張は、強化学習での決定リストの使用であり、状態をアクションにマッピングするポリシーとして機能し、一部のSanctuary AIロボティクスプロジェクトで見られる。その単純さにもかかわらず、決定リストは、精度と解釈可能性を他のモデルがほとんど匹敵できない方法でバランスさせる、AIツールキットにおける貴重なツールであり続けている。