ルール誘導(RIPPER)
- 提唱者
- William W. Cohen
- 年
- 1995
- 種類
- Supervised rule learning algorithm
- 系統
- Rule learning
この文章は機械翻訳で、まだ確認されていません。 英語の原文を読む
何をする手法か?
RIPPER(Repeated Incremental Pruning to Produce Error Reduction)を用いたルール誘導は、教師あり機械学習手法であり、ラベル付けされた訓練データから、コンパクトなIF-THEN分類ルールの集合を学習する。1995年にWilliam W. Cohenによって導入されたRIPPERは、逐次被覆(分離征服)戦略と最小記述長(MDL)プルーニングを組み合わせて、精度が高く解釈可能なルールを生成する。これは、帰納的ルール学習の分野における画期的なアルゴリズムである。
手法の背後にある直感
医師のための診断チェックリストを作成することを想像してほしい。各ルールは、診断を確実に予測する症状の特定の組み合わせを捉える。RIPPERは、患者データからこのチェックリストを自動的に構築する。一度に1つのルールを起草し、可能な限り多くの陽性事例をカバーした後、各ルールを保持セットで検証して、過度に特異的な条件を除去する。結果として、完全な訓練履歴を調べる必要なく、新しい患者に適用できる、短く人間が読めるルールブックが得られる。
歴史学
RIPPERを用いたルール誘導は、1969年のAQ(Michalski)や1989年のCN2(Clark and Niblett)のような初期の機械学習システムにルーツを持つ。Cohenの1995年のRIPPER論文は、これらの先行研究の計算上の非効率性と過学習の傾向に対処するため、増分プルーニングとMDLベースの最適化を導入した。1995年のICMLで発表されたRIPPERは、その競争力のある精度と透明性により、すぐにベンチマークアルゴリズムとなり、ルール学習の文献や教科書における標準的な参照であり続けている。
使うべき場面
RIPPERを用いたルール誘導は、モデルの解釈可能性が主要な要件である場合、例えば臨床意思決定支援、不正検出、または規制遵守の設定に適している。混合名義特徴量と数値特徴量を扱い、数万インスタンスまで合理的にスケールする。RIPPERは、訓練ラベルが十分に信頼でき、基盤となる決定境界が軸に平行な結合によって近似できると仮定する。高次元連続特徴量空間や確率的に較正された出力を必要とするタスクにはあまり適しておらず、そのような場合は勾配ブースティング木やロジスティック回帰が好まれる場合がある。
限界と注意点
- ルール品質は、非常に高次元またはスパースな特徴量空間では著しく低下する
- 順序付けられたルールリストはクラスの順序に敏感である可能性があり、最後に学習された少数派クラスはより弱いルールを受け取る可能性がある
- 確率推定値を較正しないため、コストに敏感なタスクやランキングタスクでの使用が制限される
- 結合ルールは、特徴量エンジニアリングなしでは非軸に平行な境界を必要とする複雑な相互作用を捉えることができない
出典に示された条件は、独立した科学的レビューや分析エンジンによる検証の代わりにはなりません。
強み
- 領域の専門家が監査および検証できる、人間が読めるIF-THENルールを生成する
- MDL誘導プルーニングによる効率的な逐次被覆学習は、過学習を軽減する
- 広範な前処理を必要とせずに、名義属性と数値属性の両方を処理する
- 中規模データセットサイズの場合、アンサンブル手法と比較して一般的に訓練時間が速い
応用
- 臨床意思決定支援および医療診断ルール抽出
- 金融取引監視における不正および異常検出
- 語彙的および構造的特徴量を用いたテキスト分類
- 解釈可能なアラートルールによるネットワーク侵入検出
- 実務に使えるビジネスルールによる顧客チャーン予測
使い方
使い方
RIPPERは一度に1つのクラスを処理し、残りのすべてのインスタンスをネガティブセットとして扱う。陽性インスタンスの総インスタンス数に対する比率を最大化する条件を繰り返し追加することにより、結合ルールを貪欲に成長させる。成長したら、ルールは確定され、カバーするすべてのインスタンスは、Cohen (1995) によって記述された古典的な逐次被覆(分離征服)のパラダイムに従って、次のルールが学習される前に削除される。
数式
\text{For each class } c \in \mathcal{C} \text{, grow a rule } R: \text{cond} \Rightarrow c \text{ maximizing } \frac{p}{p+n}各候補ルールは、pとnがそれぞれ正しくカバーされたインスタンス数と誤ってカバーされたインスタンス数を表す指標 (p - n) / (p + n) を使用して、保持された検証パーティションでプルーニングされる。プルーニングによってこの値が増加する限り、条件はルールの末尾から内側に向かって削除され、訓練セットに適合するだけの非常に特異的な結合によって引き起こされる過学習を防ぐ。
数式
\text{Prune rule } R \text{ by removing conditions to maximize } v(R, \text{prune set}) = \frac{p - n}{p + n}すべてのクラスごとのルールが学習された後、RIPPERは最小記述長原理によってガイドされるオプションの最適化パスを実行する。最終セット内の各ルールについて、アルゴリズムはルールの置換または改訂を検討し、ルールセットと残りの誤分類データの結合記述長が短縮される場合にのみ変更を受け入れる。これにより、精度とモデルの複雑さのバランスが取られる。
数式
\text{Minimize description length: } DL(\text{ruleset}) + DL(\text{data} \mid \text{ruleset})予測時には、ルールは学習された順序で適用される。未知のインスタンスは、そのインスタンスの特徴値によってすべての条件が満たされた最初のルールのクラスラベルが割り当てられる。どのルールも発火しない場合、インスタンスは既定クラス、通常は訓練データからの多数派クラスに分類され、入力空間の完全なカバレッジが保証される。
数式
\hat{y} = c_k \text{ where } R_k \text{ is the first rule in the ordered list that fires on instance } \mathbf{x}よくある落とし穴
- 十分な保持プルーニングデータがない小規模データセットにRIPPERを適用すると、過度にプルーニングされた、カバレッジの低いルールにつながる
- クラス不均衡を無視すると、既定クラスが少数派クラスを吸収し、少数派クラスのリコールの悪さをマスクする
- 学習されたルール順序を予測的ではなく因果的と見なすと、探索的分析で誤解を招く
- MDL最適化パス(一部の実装で利用可能)をスキップすると、最終セットに冗長または競合するルールが残る可能性がある
よくある質問
RIPPERは決定木とどのように異なるか?
どちらも軸に平行な境界を学習するが、決定木は特徴量空間全体を再帰的に分割し、階層構造を生成する。一方RIPPERは、逐次被覆を用いて順序付けられたルールリストを学習し、少数のクラス固有のパターンのみが重要な場合には、よりコンパクトな表現をもたらす可能性がある。また、ルールは、ツリーパスよりも領域の専門家が単独で読みやすい。
RIPPERは多クラス問題を扱えるか?
はい。RIPPERは、各クラスについて順にルールを学習することで多クラス設定に拡張され、最もまれなクラスから最も頻繁なクラスへと順序付けられる。前のクラスのルールによってカバーされたインスタンスは、後のクラスのルールが学習される前に削除される。既定ルールは、明示的なルールによってカバーされないインスタンスに多数派クラスを割り当てる。
RIPPERにおける最小記述長原理の役割は何か?
MDLは、ルール複雑性とデータ適合性のバランスをとるための正式な基準を提供する。最適化フェーズでは、RIPPERは、ルールと誤分類インスタンスの両方をエンコードした総記述長が短いルールセットを優先する。これにより、アルゴリズムは、データ内の真のパターンを捉えるのではなく、ノイズを記憶する過度に特異的なルールを保持することを防ぐ。
関連する手法
参考文献
Cohen, W. W. (1995). Fast effective rule induction. Proceedings of the 12th International Conference on Machine Learning, 115–123.
DOI 文献を開くコピーしました。