 |
|
図 1: NPCアルゴリズムで発見された構造的不確実性．黒い（無向）リンクは，選択可能で，ユーザーが方向を決定できます．各あいまい領域のリンクは，同じ色で描画されている．これらのリンクも選択可能で，ユーザーが実行するアクションによって，消去または保持される． |
構造学習には2つのアルゴリズムがあります: The PCアルゴリズム と NPCアルゴリズム．
NPC は，Necessary Path Condition の略で，それはPC アルゴリズムのような制約ベース（constraint-based）学習アルゴリズムのいくつかの問題を解決するために，ミュンヘンのシーメンスの研究者が開発した基準です．PCアルゴリズムとNPCアルゴリズムの基本的な仕組みは同じです（すなわち，これらは両方とも条件付き独立に関する統計的検定を通して導かれる骨組みの生成に基づきます）．
NPCアルゴリズムは，とくに限定されたデータ集合に直面したときに起きるPCアルゴリズムの不備を補償するものと見なされます．NPCアルゴリズムが提供する解は，necessary path condition（必要パス条件）として知られる基準の算入に基づきます．この基準は，相互依存の不確実なリンクの集合を選択するための言語を提供するambiguous regions（あいまい領域）の考え方を導入するための基盤を形成します．
制約ベース学習アルゴリズムでは，条件付き独立であるべき対応するノードが発見されると， 導出されたグラフ内にリンクを含まないグラフの骨組みが構築されます．しかしながら，限定されたデータ集合から導かれた条件付き独立および従属のステートメント（CIDｓ）の集合間に矛盾があるかもしれません．つまり， すべてのCIDs が同時に表現できるわけではありません．
矛盾は，もっぱらサンプリング・ノイズに起因すると仮定されます；すなわち，我々はまだ，そのデータが生成されたものと（未知の）確率分布の完全独立マップが存在すると仮定しています．
CIDs の集合での矛盾の数は，構造モデルの不確実性を反映します．したがって，不確実性の数は，学習された構造についての信頼測度であり，学習を実行するために十分なデータが使用されたかどうかの指標のようなものとして使用できます．矛盾 CIDs は，それらから有向非巡回グラフ（DAG:directed acyclic graph）を導出するときの複数解を産出します．これらの解は，含まれるリンクの集合ごとに異なります．
矛盾を解決するために， NPCアルゴリズムは，無向リンクの方向性を決定し，ambiguous regionsを解決するためのユーザーのインタラクションに頼っています．
ざっくばらんに言えば，necessary path conditionは，2つの変数XとYが，集合Sの不適切な部分集合によって，集合Sを条件とする独立であるために，（Yと交わらない）S中のXとすべてのZ の間，および（Xと交わらない）S中のYとすべてのZの間に，パスが存在しなければならないことを示します．それ以外の場合，S中へのZの算入は説明されません．したがって，独立ステートメントが有効であるためには，グラフ中にたくさんのリンクが存在することが必要です．
リンクaの非存在は，もう１つのリンクｂの存在に依存する場合，またその逆の場合，我々は，aとbを相互依存（従属）であると定義します．ａとｂは，我々が不確実リンクと呼ぶものを構成します．ambiguous region は，相互依存リンクの極大集合です．つまり，ambiguous region は，不確実リンクの集合からなります．
主要な目的は，できるだけ少なく小さなambiguous regions を得ることです．変数間の決定論的関係性が，ambiguous regionsも産出することに注意するべきです（下記の事例参照）． (see example below).
いくつかの不確実リンク（または方向づけされる必要のあるリンク）がある場合，ambiguous regions がどのように解決されるべきかについての情報を提供する可能性が提供されます．特別な直感的グラフィカル・インターフェースが，このインタラクションのために提供されます．
NPC アルゴリズムを使用しているとき， アルゴリズムによって発見された構造的不確実性を（もしあれば）解決するために直感的なグラフィカル・インタフェースが提供されます． 図 1 は，解決されていない不確実性を持つ構造の例を示します．
|
|
図 1: NPCアルゴリズムで発見された構造的不確実性．黒い（無向）リンクは，選択可能で，ユーザーが方向を決定できます．各あいまい領域のリンクは，同じ色で描画されている．これらのリンクも選択可能で，ユーザーが実行するアクションによって，消去または保持される． |
このような情報の提供を望まない場合は，完了ボタンをクリックするだけで，NPCアルゴリズムが不確実性を解決します．しかしながら，無向リンクの方向性は，ランダムに決定されること，そして，情報が提供されていないそれらのあいまい領域については，すべての不確実リンクが消去されて，貧弱なモデルになるかもしれないことに注意してください．
学習された構造のデータから自動的に決定できないリンクの方向性をランダムに決定する代わりに，NPCアルゴリズムが，そのようなリンクの方向性を決定する方法を提供します．
無向リンク（あいまい領域に属さない）は，黒で描かれます．選択すると，リンクがハイライトされ，2つの方向性のボタンが使用可能になります :
または 
または 
または  |
|
図 2: 方向性ボタンのさまざまな外観. |
上記のボタンの対の概観のどれを使用するかは，選択されたリンクのノーの相対位置によります．したがって，選択されたリンクの望ましい方向性を実現するために，2つのボタンのどれを選択するべきかは簡単にわかるはずです． しかしながら，マウス・カーソルがボタンの上にある場合，程なくして，どの方向が問題のボタンに関連しているかをはっきりと説明するツール・ティップスが現われます．
リンクへの方向性の割り当ては，方向づけされる他のリンクに自動的に起因することに注意してください．たとえば，変数ｘとｙの間，yとｚの間，ｘとｚの間に無向リンクがある場合，方向性 x --> y と y --> z を強制すると x --> zが含意されます; さもなくば，有向巡回が発生します．
あいまい領域は，相互依存の不確実リンクの集合から成ります: あいまい領域内のリンクの非存在は，1つまたは複数の他の領域のリンクの存在によります．また逆も真なりです．
各あいまい領域は，同じ色のリンクからなるので，簡単に識別できます．（たくさんのあいまい領域があると，同じ色を再使用しなければならないので，それらを色だけで区別するのが難しくなることに注意してください．）また，あいまい領域のリンクを選択すると，その領域のすべてのリンクがハイライトされます;選択されたリンクは太く描かれ，その他のリンクは二重線で描かれます．
あいまい領域のリンクが選択されると，リンクを含む/除外するボタンが使用可能になります．:
 |
|
図 3: リンクを含む/除外するボタン. |
リンクが存在するかしないかの決定が下されると，あいまい領域の他のリンクがつぎのいずれかの影響を受けます:
これらの結果のどれが観察されるかは，NPCアルゴリズムによって実行される統計的検定から発見される条件付き独立および従属ステートメント（CDIs）によります．
あいまい領域は，多数の不確実エッジからなる場合もあります． これは，あいまい領域の適切な解決を発見することがとても難しいことを意味します．
各あいまい領域は，最低1つの極小解を持つでしょう．極小解は，あいまい領域を解決するエッジの極小集合です．，
 |
|
図 4: 極小解を識別ボタン. |
あいまい領域の不確実リンクが選択されると，図4に示すボタンが現れます． このボタンが押し下げられると，すべての極小解を示すウィンドウが表示されます．ユーザーは，極小解を選択することができます．
無向リンクの方向性に関して，またはあいまい領域のリンクの存在か非存在かに関してなされた決定の結果を予測することが，しばしば不可能（もしくはとても難しい）です．したがって，アンドゥ機能がとても便利なことがあるでしょう．
アンドゥ・ボタンをクリックすると，実行された直近の（非アンドゥ）アクションが取り消せます:
 |
|
図 5: アンドゥ・ボタン. |
アンドゥ・ボタンを繰り返しクリックすると，実行された任意の数の操作を取り消せます．
興味のある読者は，NPCアルゴリズムの背後にある考え方の詳細な説明の文献を参照できます．たとえば，次の文献があります．
翻訳者：多田くにひろ（マインドウェア総研）