PC アルゴリズム

構造学習には2つのアルゴリズムがあります: PCアルゴリズムとNPC アルゴリズム.

Huginの PC アルゴリズムは，Spirtes, Glymour & Scheines (2000)によるオリジナルのPCアルゴリズムの改良型で，制約ベース学習アルゴリズムの類に属します．これらのアルゴリズムの基本アイデアは，統計的検定による条件付き独立および従属ステートメント（CDIs）の集合を導出することです．

このアルゴリズムは以下のステップを実行します:

• 条件付き独立に関する統計的検定が，（構造的制約が指定された対を除く）変数のすべての対について実行されるー より詳しくは，学習ウィザードの構造的制約ページに関するヘルプ・ページを参照．
• 条件付き独立が発見されなかった変数の各対の間に無向リンクが追加されます．結果の無向グラフは，学習された構造の骨組み（スケトン）と呼ばれる．
• そして，有向巡回が発生しないようにコライダー（衝突）が識別される．（コライダーとは，あるノードでそれらが出会うように方向づけられたリンクの対）たとえば，AとBが従属，BとCが従属であるが，AとCはBを含まないSを仮定した条件付き独立であるとわかれば，これは構造 A --> B <-- Cで表現できる．
• 次に，発見された条件付き独立と識別されたコライダーから方向が導かれるリンクについて，方向が強制される．
• 最後に，残りの無向リンクは，有向巡回が発生しないようにランダムに方向づけされる．

PCアルゴリズムに関する重要なことの１つは，一般的に，それがデータからすべてのリンクの方向を導くことができなくて，したがって，いくつかのリンクがランダムに方向づけされることです．これは，学習された構造が検査されるべきで，もしいくつかのリンクが直観に反しているようであれば（たとえば，汗が熱の原因になるというようなあべこべ），学習ウィザード（構造的ドメイン知識を指定する方法を提供）または NPC アルゴリズム（無向リンクの方向性をインタラクティブに決定できる）の使用を検討できることを意味します．

従来の制約ベース学習アルゴリズムは，無限のデータ集合，完全な検定，DAG忠実性（すなわち，データがDAGによって分解する確率分布からシミュレートされてると仮定できること）を仮定して，正しいであろう構造を産出します．しかしながら，限定されたデータ集合の場合， これらのアルゴリズムは，しばしば，多すぎる条件付き独立ステートメントを導きます．また，それらは重要な従属関係を省略することもあります．

一般的に，NPCアルゴリズムを使用することが推奨されます．結果のグラフは，データ中の（条件付き）独立関係のより良いマップになるでしょう．とくに，データ集合が小さい場合，NPCアルゴリズムが実行されるべきです．ただし，NPCアルゴリズムは，PCアルゴリズムよりも実行時間が長くかかります．