CN2アルゴリズムは、機械学習における分類タスクに使用されるルール誘導手法である。データセットからif-thenルールの集合を生成し、各ルールは属性値に関する条件の連言と予測クラスから構成される。CN2は1987年にチューリング研究所のピーター・クラークとティム・ニブレットによって導入され、機械学習と人工知能における初期の研究に基づいている。このアルゴリズムは、AQファミリーの分割統治探索戦略と、エントロピーなどの情報理論的評価基準を決定木誘導で使用されるものと組み合わせた点で注目に値する。これは記号的ルール学習における基礎的なアプローチであり、ニューラルネットワークや深層学習手法の不透明な性質とは対照的な解釈可能なモデルを提供する。
このアルゴリズムは、トレーニング例のサブセットをカバーする最良のルールを反復的に探索し、それらの例を除去して、残りのデータに対してプロセスを繰り返すことで動作する。この分割統治戦略は、被覆法とも呼ばれ、分割統治アプローチを使用する決定木アルゴリズムからCN2を区別する。CN2は、バリアントに応じて、順序付きルールリスト（決定リスト）または順序なしルール集合のいずれかを生成できる。元のバージョンは順序付きリストを生成し、ルールが順番に適用され、最初に一致したルールが予測を決定する。後の拡張、例えばCN2-SD（サブグループ発見）は、完全な分類器ではなく興味深いサブグループを発見するためにアルゴリズムを適応させた。
探索と評価
CN2は、ルール条件の空間を通じてビーム探索を実行する。空のルールから始めて、ルールの品質を向上させる条件を繰り返し追加し、ビーム幅パラメータを使用して各ステップで考慮される候補ルールの数を制限する。探索は、ルールの品質を測定する評価関数によって導かれる。元のCN2は、ID3の利得基準と同様のエントロピーに基づく情報理論的尺度を使用した。具体的には、アルゴリズムはカバーされた例のクラス分布のエントロピーを使用してルールを評価し、エントロピーを減少させるルールを優先する。後のバージョンでは、特に小規模なサンプルを扱う際の過学習を避けるために、ラプラス精度推定を導入した。ラプラス補正は各クラスに擬似カウントを追加し、ルール精度のより堅牢な推定を提供する。
ビーム探索は本質的に貪欲であり、バックトラックしないが、ビーム幅により複数の有望な経路を同時に探索できる。この貪欲さと探索の間のトレードオフは、CN2の重要な特徴である。探索空間はデータに存在する属性値ペアによって定義され、条件は通常、名義属性ではattribute = valueの形式、数値属性ではattribute <= valueおよびattribute >= valueの形式であるが、元のアルゴリズムは名義データに焦点を当てていた。
アルゴリズムのバリアント
長年にわたり、CN2のいくつかのバリアントが開発されてきた。最も重要なのは、1990年代後半にナダ・ラブラッチらによって導入されたCN2-SDであり、これは分類からサブグループ発見へと目標をシフトさせる。サブグループ発見では、完全な分類器を構築するのではなく、異常なクラス分布を持つ興味深い母集団サブグループを記述するルールを見つけることを目的とする。CN2-SDは、ルールの一般性と分布の異常性のバランスを取る加重相対精度尺度を使用してルールを評価する。別のバリアントであるCN2-Rは、ランダム化テストを組み込んでルールの統計的有意性を評価し、偶然に生じた可能性のあるルールをフィルタリングする。これは、より信頼性が高く一般化可能なルールセットの生成に役立つ。
CN2の順序なしバリアントは、各ルールが独立して学習されるルールの集合を生成し、予測時にはすべてのルールが適用され、その予測が組み合わされる。多くの場合、投票または最も特異性の高いルールの選択によって行われる。このアプローチは、クラス領域が重複するデータセットに対してより堅牢である可能性がある。順序付きルールと順序なしルールの選択はアプリケーションに依存し、順序付きリストはより単純で高速である一方、順序なし集合は稀なクラスに対してより良いカバレッジを提供できる。
応用と影響
CN2は、医療診断、故障検出、生態モデリングなど、さまざまな分野で応用されてきた。その解釈可能性は、医療や規制遵守など、意思決定プロセスの理解が重要となる分野で特に価値がある。例えば、医療アプリケーションでは、CN2ルールはif blood_pressure > 140 and age > 60 then high_riskのような単純な条件として表現でき、臨床医が容易に検証できる。このアルゴリズムは、機械学習における記号的アプローチとサブ記号的アプローチを比較するためのベンチマークとしても使用されてきた。深層学習のような現代の手法は複雑なタスクでより高い精度を達成することが多いが、CN2は透明なモデルが必要な問題やデータが限られている場合に依然として関連性がある。
このアルゴリズムの影響は、RIPPERやPARTなどの後のルール学習システムにも及んでおり、これらは同様の探索および評価戦略を採用した。CN2のエントロピーに基づく評価は、決定木誘導や特徴選択で使用されるより洗練された情報理論的尺度の先駆けとなった。その分割統治フレームワークは理論的に分析され、PAC学習フレームワークやルール学習の複雑さとの関連が示されている。
限界と拡張
CN2には既知の限界がある。貪欲な探索がスプリアスなパターンに過学習する可能性があるため、ノイズの多いデータに敏感である。ビーム探索は純粋な山登り法よりも徹底的であるが、限られた先読みにより最適なルールを見逃す可能性がある。このアルゴリズムは属性が独立であると仮定しており、これは実世界のデータでは成り立たない場合がある。拡張によりこれらの問題の一部が対処されてきた。例えば、前処理ステップまたは探索内での離散化を通じて連続属性を組み込むことで、CN2は数値データを扱えるようになる。CN2-Rのような統計的テストの使用は過学習を軽減する。より最近の研究では、CN2をアンサンブル手法と統合し、複数のルールセットを組み合わせて堅牢性を向上させている。
現代の機械学習の文脈では、CN2はしばしばニューラルネットワークアプローチと対比される。ニューラルネットワークは複雑な特徴間の相互作用を自動的に学習できるが、大量のデータを必要とし、解釈が難しい。一方、CN2はコンパクトで人間が読めるルールを生成するが、高次元または高度に非線形な問題では苦戦する可能性がある。このトレードオフは、記号的ルールとサブ記号的学習を組み合わせたハイブリッドシステムの研究を推進し続けており、これはニューロシンボリックAIの広範な分野での関心のトピックである。
実装とソフトウェア
CN2は、いくつかの機械学習ライブラリに実装されている。リュブリャナ大学で開発されたOrangeデータマイニングスイートにはCN2学習器が含まれており、Wekaツールキットにも含まれている。これらの実装は、アルゴリズムを実データセットに適用するためのユーザーフレンドリーなインターフェースを提供する。アルゴリズムの単純さにより、さまざまなプログラミング言語で簡単に実装でき、機械学習やデータマイニングのコースで教育用の例としてよく使用される。オープンソース実装の利用可能性は、研究と教育での継続的な使用に貢献してきた。
1980年代後半に導入されたにもかかわらず、CN2は機械学習実践者のツールボックスにおいて依然として関連性のあるアルゴリズムである。その解釈可能性への焦点と効率的な探索戦略は、現在の深層学習の支配に先行する他の記号的手法と並んで、AIの歴史におけるその位置を確実にしている。2020年代現在、CN2はルール学習と解釈可能なAIに関する研究で依然として引用されており、新しいルール誘導手法を評価するためのベースラインとして機能している。