(57)【特許請求の範囲】
【請求項１】
不整合な知識ベースを使用してブールクエリに応答するための、プロセッサのための方法であって、
オリジナル論理式を含んだ前記ブールクエリを受け取ることと、
前記不整合な知識ベースが前記オリジナル論理式を非標準的に含意するかどうかを判定することと、
前記不整合な知識ベースが前記オリジナル論理式を非標準的に含意する場合、前記不整合な知識ベースによって非標準的に含意され、前記オリジナル論理式と融合させることができ、前記オリジナル論理式と矛盾しない、ブリッジ論理式を選択することと、
前記オリジナル論理式、ｂｕｔ論理式、および前記ブリッジ論理式を含む、ｂｕｔ回答を構成することであって、前記ｂｕｔ論理式が、前記オリジナル論理式と前記ブリッジ論理式の融合節の否定である、構成することと、
前記ｂｕｔ回答の妥当性を確認することと、
前記ｂｕｔ回答を少なくとも前記オリジナル論理式および前記ｂｕｔ論理式とともに送信または表示することと
を含む方法。
【請求項２】
前記ブリッジ論理式を選択することが、
前記不整合な知識ベース内のあるステップ数の異なる節の連言として、前記ブリッジ論理式を形成することと、
前記オリジナル論理式と前記ブリッジ論理式を融合させることができるかどうかを判定することと、
前記オリジナル論理式と前記ブリッジ論理式を融合させることができず、そのため、前記ブリッジ論理式が拒否された場合、
終了条件が満たされているかどうかを判定することと、
前記終了条件が満たされていない場合、前記ステップ数をインクリメントし、前記ブリッジ論理式を形成することから開始して上述のステップを繰り返すことと、
前記終了条件が満たされている場合、前記方法を終了させることと、
前記オリジナル論理式と前記ブリッジ論理式を融合させることができる場合、
前記オリジナル論理式と前記ブリッジ論理式が矛盾するかどうかを判定することと、
前記オリジナル論理式と前記ブリッジ論理式が矛盾しており、そのため、前記ブリッジ論理式が拒否された場合、
前記終了条件が満たされているかどうかを判定することと、
前記終了条件が満たされていない場合、前記ステップ数をインクリメントし、前記ブリッジ論理式を形成することから開始して上述のステップを繰り返すことと、
前記終了条件が満たされている場合、前記方法を終了させることと、
前記オリジナル論理式と前記ブリッジ論理式が矛盾していない場合、前記構成することおよび前記妥当性を確認することのために、前記ブリッジ論理式を使用することと
を含む、請求項１に記載の方法。
【請求項３】
前記ブリッジ論理式を選択することが、前記ブリッジ論理式が、（１）先に選択されたブリッジ論理式、（２）前記オリジナル論理式と矛盾する先に拒否されたブリッジ論理式、または（３）前記オリジナル論理式と融合させることができない２つの先に拒否されたブリッジ論理式を含む連言である場合、前記ブリッジ論理式を除去することをさらに含む、請求項２に記載の方法。
【請求項４】
前記終了条件が、（１）１つのブリッジ論理式を見つけたこと、（２）前記ステップ数の終了値に達したこと、および（３）前記方法を実行するための期間の限度を超えたことのうちの１つまたは複数を含む、請求項２に記載の方法。
【請求項５】
前記ｂｕｔ回答の妥当性を確認することが、前記不整合な知識ベースが前記ｂｕｔ論理式を非標準的に含意するかどうかを判定することを含み、前記不整合な知識ベースが前記ｂｕｔ論理式を非標準的に含意する場合、前記ｂｕｔ回答の妥当性が確認される、請求項１に記載の方法。
【請求項６】
前記ｂｕｔ回答の妥当性を確認することの後に、
終了条件が満たされているかどうかを判定することと、
前記終了条件が満たされていない場合、前記選択することから開始して上述のステップを繰り返すことと、
前記終了条件が満たされている場合、前記方法を終了させることと
をさらに含む、請求項１に記載の方法。
【請求項７】
前記終了条件が、（１）１つのブリッジ論理式を見つけたこと、（２）前記ステップ数の終了値に達したこと、および（３）前記方法を実行するための期間の限度を超えたことのうちの１つまたは複数を含む、請求項６に記載の方法。
【請求項８】
前記ｂｕｔ回答を送信することが、前記ブリッジ論理式を回答および前記ｂｕｔ論理式とともに送信することをさらに含む、請求項１に記載の方法。
【請求項９】
非標準的含意が、前記不整合な知識ベースから、前記ｂｕｔ論理式を標準的に含意するサブセットを決定するために、融合ベースの選択関数を使用することを含み、前記融合ベースの選択関数が、以下のように、すなわち、
【数１】
0005646118.tif 000090
【数２】
0005646118.tif 000091
【数３】
0005646118.tif 000092
にある
と定義される、請求項１に記載の方法。
【請求項１０】
前記融合ベースの選択関数を使用することが、
初期サブセットおよびステップ値を設定することと、
前記不整合な知識ベースから論理式をサブセットに追加するために、前記融合ベースの選択関数および前記ステップ値を使用することであって、前記サブセットが、初期整合サブセットを拡張したものである、使用することと、
前記サブセットが整合しているかどうかを判定することと、
前記サブセットが整合していない場合、
前記サブセットが整合サブセットになるように、前記サブセットから１つまたは複数の論理式を除去することと、
前記サブセットが前記オリジナル論理式を古典的に含意するかどうかを判定することであって、
前記サブセットが前記オリジナル論理式を標準的に含意する場合、前記不整合な知識ベースが前記オリジナル論理式を非標準的に含意し、
前記サブセットが前記オリジナル論理式を標準的に含意しない場合、前記不整合な知識ベースが前記オリジナル論理式を非標準的に含意しない、
判定することと、
前記サブセットが整合している場合、
前記サブセットが前記初期サブセットのスーパーセットであるかどうかを判定することであって、前記サブセットが前記初期サブセットのスーパーセットでない場合、前記不整合な知識ベースが前記オリジナル論理式を非標準的に含意しない、判定することと、
前記サブセットが前記初期サブセットのスーパーセットである場合、
前記サブセットが前記オリジナル論理式を標準的に含意するかどうかを判定することであって、前記サブセットが前記オリジナル論理式を標準的に含意する場合、前記不整合な知識ベースが前記オリジナル論理式を非標準的に含意する、判定することと、
前記サブセットが前記オリジナル論理式を標準的に含意しない場合、
前記サブセットを前記初期整合サブセットとして設定し、前記ステップ値をインクリメントし、前記融合ベースの選択関数および前記ステップ値を使用することから開始して上述のステップを繰り返すことと
を含む、請求項９に記載の方法。
【請求項１１】
不整合な知識ベースを使用してブールクエリに応答する不整合リーズナを実施するための、プロセッサのためのコンピュータ実行可能命令を用いて符号化された、非一時的なコンピュータ可読記憶媒体であって、前記命令が、
オリジナル論理式を含んだ前記ブールクエリを受け取ることと、
前記不整合な知識ベースが前記オリジナル論理式を非標準的に含意するかどうかを判定することと、
前記不整合な知識ベースが前記オリジナル論理式を非標準的に含意する場合、前記不整合な知識ベースによって非標準的に含意され、前記オリジナル論理式と融合させることができ、前記オリジナル論理式と矛盾しない、ブリッジ論理式を選択することと、
前記オリジナル論理式、ｂｕｔ論理式、および前記ブリッジ論理式を含む、ｂｕｔ回答を構成することであって、前記ｂｕｔ論理式が、前記オリジナル論理式と前記ブリッジ論理式の融合節の否定である、構成することと、
前記ｂｕｔ回答の妥当性を確認することと、
前記ｂｕｔ回答を少なくとも前記オリジナル論理式および前記ｂｕｔ論理式とともに送信または表示することと
を含む、非一時的なコンピュータ可読媒体。
【請求項１２】
前記ブリッジ論理式を選択することが、
前記不整合な知識ベース内のあるステップ数の異なる節の連言として、前記ブリッジ論理式を形成することと、
前記オリジナル論理式と前記ブリッジ論理式を融合させることができるかどうかを判定することと、
前記オリジナル論理式と前記ブリッジ論理式を融合させることができず、そのため、前記ブリッジ論理式が拒否された場合、
終了条件が満たされているかどうかを判定することと、
前記終了条件が満たされていない場合、前記ステップ数をインクリメントし、前記ブリッジ論理式を形成することから開始して上述のステップを繰り返すことと、
前記終了条件が満たされている場合、前記方法を終了させることと、
前記オリジナル論理式と前記ブリッジ論理式を融合させることができる場合、
前記オリジナル論理式と前記ブリッジ論理式が矛盾するかどうかを判定することと、
前記オリジナル論理式と前記ブリッジ論理式が矛盾しており、そのため、前記ブリッジ論理式が拒否された場合、
前記終了条件が満たされているかどうかを判定することと、
前記終了条件が満たされていない場合、前記ステップ数をインクリメントし、前記ブリッジ論理式を形成することから開始して上述のステップを繰り返すことと、
前記終了条件が満たされている場合、前記方法を終了させることと、
前記オリジナル論理式と前記ブリッジ論理式が矛盾していない場合、前記構成することおよび前記妥当性を確認することのために、前記ブリッジ論理式を使用することと
を含む、請求項１１に記載の非一時的なコンピュータ可読媒体。
【請求項１３】
前記ブリッジ論理式を選択することが、前記ブリッジ論理式が、（１）先に選択されたブリッジ論理式、（２）前記オリジナル論理式と矛盾する先に拒否されたブリッジ論理式、または（３）前記オリジナル論理式と融合させることができない２つの先に拒否されたブリッジ論理式を含む連言である場合、前記ブリッジ論理式を除去することをさらに含む、請求項１２に記載の非一時的なコンピュータ可読媒体。
【請求項１４】
前記終了条件が、（１）１つのブリッジ論理式を見つけたこと、（２）前記ステップ数の終了値に達したこと、および（３）前記方法を実行するための期間の限度を超えたことのうちの１つまたは複数を含む、請求項１２に記載の非一時的なコンピュータ可読媒体。
【請求項１５】
前記ｂｕｔ回答の妥当性を確認することが、前記不整合な知識ベースが前記ｂｕｔ論理式を非標準的に含意するかどうかを判定することを含み、前記不整合な知識ベースが前記ｂｕｔ論理式を非標準的に含意する場合、前記ｂｕｔ回答の妥当性が確認される、請求項１１に記載の非一時的なコンピュータ可読媒体。
【請求項１６】
前記ｂｕｔ回答の妥当性を確認することの後に、
終了条件が満たされているかどうかを判定することと、
前記終了条件が満たされていない場合、前記選択することから開始して上述のステップを繰り返すことと、
前記終了条件が満たされている場合、前記方法を終了させることと
をさらに含む、請求項１１に記載の非一時的なコンピュータ可読媒体。
【請求項１７】
前記終了条件が、（１）１つのブリッジ論理式を見つけたこと、（２）前記ステップ数の終了値に達したこと、および（３）前記方法を実行するための期間の限度を超えたことのうちの１つまたは複数を含む、請求項１６に記載の非一時的なコンピュータ可読媒体。
【請求項１８】
前記ｂｕｔ回答を送信することが、前記ブリッジ論理式を回答および前記ｂｕｔ論理式とともに送信することをさらに含む、請求項１１に記載の非一時的なコンピュータ可読媒体。
【請求項１９】
非標準的含意が、前記不整合な知識ベースから、前記ｂｕｔ論理式を標準的に含意するサブセットを決定するために、融合ベースの選択関数を使用することを含み、前記融合ベースの選択関数が、以下のように、すなわち、
【数４】
0005646118.tif 000093
【数５】
0005646118.tif 000094
【数６】
0005646118.tif 000095
と定義される、請求項１１に記載の非一時的なコンピュータ可読媒体。
【請求項２０】
前記融合ベースの選択関数を使用することが、
初期サブセットおよびステップ値を設定することと、
前記不整合な知識ベースから論理式をサブセットに追加するために、前記融合ベースの選択関数および前記ステップ値を使用することであって、前記サブセットが、初期整合サブセットを拡張したものである、使用することと、
前記サブセットが整合しているかどうかを判定することと、
前記サブセットが整合していない場合、
前記サブセットが整合サブセットになるように、前記サブセットから１つまたは複数の論理式を除去することと、
前記サブセットが前記オリジナル論理式を古典的に含意するかどうかを判定することであって、
前記サブセットが前記オリジナル論理式を標準的に含意する場合、前記不整合な知識ベースが前記オリジナル論理式を非標準的に含意し、
前記サブセットが前記オリジナル論理式を標準的に含意しない場合、前記不整合な知識ベースが前記オリジナル論理式を非標準的に含意しない、
判定することと、
前記サブセットが整合している場合、
前記サブセットが前記初期サブセットのスーパーセットであるかどうかを判定することであって、前記サブセットが前記初期サブセットのスーパーセットでない場合、前記不整合な知識ベースが前記オリジナル論理式を非標準的に含意しない、判定することと、
前記サブセットが前記初期サブセットのスーパーセットである場合、
前記サブセットが前記オリジナル論理式を標準的に含意するかどうかを判定することであって、前記サブセットが前記オリジナル論理式を標準的に含意する場合、前記不整合な知識ベースが前記オリジナル論理式を非標準的に含意する、判定することと、
前記サブセットが前記オリジナル論理式を標準的に含意しない場合、
前記サブセットを前記初期整合サブセットとして設定し、前記ステップ値をインクリメントし、前記融合ベースの選択関数および前記ステップ値を使用することから開始して上述のステップを繰り返すことと
を含む、請求項１９に記載の非一時的なコンピュータ可読媒体。
【発明の詳細な説明】
【背景技術】
【０００１】
本明細書で別段の指摘がない限り、本セクションで説明される手法は、本出願の請求項に対する先行技術ではなく、本セクションに含まれることによって先行技術であると認められることはない。
【０００２】
セマンティックウェブ（Ｓｅｍａｎｔｉｃ  Ｗｅｂ）とは、ワールドワイドウェブ上で利用可能な情報をマシンが理解できるようにすることを指す。ワールドワイドウェブ上の情報をユーザが処理し、操作する代わりに、コンピュータ上のパーソナルエージェント（ｐｅｒｓｏｎａｌ  ａｇｅｎｔ）が、ユーザのためにデータを利用して、ブールクエリ（Ｂｏｏｌｅａｎ  ｑｕｅｒｙ）に回答するなどのタスクを実行する。しかし、ワールドワイドウェブ上には多数の知識ベースが存在し、それらを性急にマージすると、不整合が生じる。
【０００３】
一般に、知識ベースにおける不整合に対処するには、２つの方法が存在する。第１の方法は、不整合な知識ベースに訂正を施すことである。しかし、不整合な知識ベースが膨大なことがあり、または不整合を訂正する権限を人が有さないことがあるので、不整合の訂正は、効果が上がらないことがあり、または不可能なことさえある。さらに、不整合な知識ベースは、高頻度で変更されることがあり、したがって、意味のあるいかなる訂正も可能ではないことがある。不整合な知識ベースに対処する第２の方法は、不整合な知識ベースを用いて直接的に推論を実行することである。不整合を含んだ推論には、いくつかの研究が存在する。ブールクエリを与えた場合、これらの推論方法は、通常、「はい」、「いいえ」、または「分からない」を返す。
【発明の概要】
【０００４】
本開示の１つまたは複数の実施形態では、プロセッサが不整合な知識ベースを使用してブールクエリに応答するための方法が提供される。方法は、オリジナル論理式（ｏｒｉｇｉｎａｌ  ｆｏｒｍｕｌａ）を含んだブールクエリを受け取ることと、不整合な知識ベースがオリジナル論理式を非標準的に含意する（ｎｏｎ−ｓｔａｎｄａｒｄｌｙ  ｅｎｔａｉｌ）かどうかを判定することとを含む。不整合な知識ベースがオリジナル論理式を非標準的に含意する場合、方法は、不整合な知識ベースから、オリジナル論理式との矛盾を説明するブリッジ論理式（ｂｒｉｄｇｅ  ｆｏｒｍｕｌａ）を選択することと、オリジナル論理式、オリジナル論理式との矛盾を引き起こすｂｕｔ論理式（ｂｕｔ  ｆｏｒｍｕｌａ）、およびブリッジ論理式を含む、ｂｕｔ回答（ｂｕｔ  ａｎｓｗｅｒ）を構成することとを含む。方法は、ｂｕｔ回答の妥当性を確認することと、ｂｕｔ回答を少なくともオリジナル論理式およびｂｕｔ論理式とともに送信または表示することをさらに含む。
【０００５】
上述の要約は、単に例示的なものにすぎず、決して限定的であることを意図したものではない。上で説明された例示的な態様、実施形態、および特徴に加えて、さらなる態様、実施形態、および特徴が、図面および以下の詳細な説明を参照することによって明らかとなる。
【０００６】
本開示の上述および他の特徴は、以下の説明および添付の特許請求の範囲を添付の図面を併用して理解することで、より完全に明らかとなる。これらの図面は、本開示によるいくつかの実施形態のみを示しており、したがって、本開示の範囲を限定するものと見なすべきではないことを理解したうえで、添付の図面を使用して、さらに具体的かつ詳細に本開示が説明される。
【図面の簡単な説明】
【０００７】
【図１】不整合な知識ベースを用いてｂｕｔ推論を実施するための、コンピュータの例示的なシステムのブロック図である。
【図２】不整合な知識ベースに基づいてブールクエリに対するｂｕｔ回答を決定する不整合リーズナ（ｉｎｃｏｎｓｉｓｔｅｎｔ  ｒｅａｓｏｎｅｒ）を実施するための、図１のコンピュータによって実行される例示的な方法のフローチャートである。
【図３】不整合な知識ベースがオリジナル論理式を非標準的に含意するかどうかを判定するための、図１のコンピュータによって実行される例示的な方法のフローチャートである。
【図４】不整合な知識ベースを用いてｂｕｔ推論を行うための方法を実施するための、例示的なコンピュータプログラム製品を示す図である。
【図５】本開示の少なくともいくつかの実施形態に従ってすべてが構成された、例示的なコンピューティングデバイスのブロック図である。
【発明を実施するための形態】
【０００８】
Ｉ．導入
以下の詳細な説明では、詳細な説明の一部を形成する添付の図面を参照する。図面では、関連する文言による別段の指摘がない限り、一般に、類似の記号は、類似の構成要素を識別する。詳細な説明、図面、および特許請求の範囲において説明される例示的な実施形態は、限定的であることを意図していない。本明細書で提示される本発明の主題の主旨または範囲から逸脱することなく、他の実施形態を利用することができ、他の変更を施すことができる。本明細書で全般的に説明され、図面に示される、本開示の態様は、多種多様な異なる構成を取るように配置し、置き換え、組み合わせ、および設計することができ、そのすべてが、本明細書において明白に企図されていることが容易に理解されよう。
【０００９】
本開示は、とりわけ、不整合な知識ベースに基づいてブールクエリに対する「ｂｕｔ回答」を決定するために「ｂｕｔ推論」を使用することに関連する、方法、装置、コンピュータプログラム、およびシステムに関する。
【００１０】
単語「ｂｕｔ（しかし）」は、２つの節の逆接を表すために使用することができ、そのようなｂｕｔ文（ｂｕｔ  ｓｔａｔｅｍｅｎｔ）を含んだ推論は、ｂｕｔ推論と呼ばれることがある。不整合な知識ベースに基づいてブールクエリに回答する場合、ｂｕｔ推論は、ブールクエリに対する「オリジナル回答（ｏｒｉｇｉｎａｌ  ａｎｓｗｅｒ）」ばかりでなく、オリジナル回答と対照的である「対照的回答（ｃｏｎｔｒａｓｔｉｎｇ  ａｎｓｗｅｒ）」も与えることができる。
【００１１】
ｂｕｔ推論は、２つの主要な目標を有する。ｂｕｔ推論は、関連する対照的回答を提供することによって、情報の誤解を避けることができる。例えば、「すべての自動車は汚染を引き起こす、しかし電気自動車は汚染を引き起こさない」と言うことが可能である。すべての自動車は汚染を引き起こすという単純な回答は、誤解を招くおそれがあり、それは、電気自動車がこの規則の例外であるからである。ｂｕｔ推論は、予想されていなかった付加的な回答を用いて、効果的な影響を達成することもできる。例えば、「会議はオランダで開催される、しかしアムステルダムでは開催されない」と言うことが可能である。会議がアムステルダムでは開催されないという対照的な回答は、オランダで開催されるすべての会議はアムステルダムで開催されるという通常の予想に反しており意外である。
【００１２】
ｂｕｔ推論は、（会議の例におけるように）知識ベースと外部の予想との間の矛盾、または（汚染を引き起こす自動車の例におけるように）知識ベースの異なる部分の間の矛盾を露呈させることがある。これらの理由で、ｂｕｔ推論は、不整合な知識ベースを用いる推論にとって有益なことがあり、それは、ｂｕｔ推論が、ブールクエリに対して「はい」、「いいえ」、または「分からない」というブール回答（Ｂｏｏｌｅａｎ  ａｎｓｗｅｒ）を用いて単純に応答せずに、何らかの「意外な」情報を伴った情報価値のあるｂｕｔ回答を提供するからである。
【００１３】
ＩＩ．ｂｕｔ推論の形式化
論理学における古典的な標準的含意（ｓｔａｎｄａｒｄ  ｅｎｔａｉｌｍｅｎｔ）は、論争の種となるもので、これによれば、任意の論理式が、矛盾の論理的帰結となる。したがって、不整合な知識ベースから古典的推論によって引き出される結論は、完全に無意味なことがある。不整合な知識ベースにおいて推論を行う任意のシステムの一般的なタスクは、不整合な知識ベースが与えられた場合に、クエリに対して「意味がある」回答を返すことである。回答は、それが不整合な知識ベース内の選択された整合したサブセットによって支持されるが、その否定は整合したサブセットによって支持されない場合に、「意味がある」。以下では、表記
【数１】
0005646118.tif 000002
は、標準的含意を表し、表記
【数２】
0005646118.tif 000003
は、非標準的含意（ｎｏｎｓｔａｎｄａｒｄ  ｅｎｔａｉｌｍｅｎｔ）を表す。
【００１４】
非標準的含意
【数３】
0005646118.tif 000004
は、健全性（ｓｏｕｎｄｎｅｓｓ）および有意味性（ｍｅａｎｉｎｇｆｕｌｎｅｓｓ）を満たすべきである。「健全性」は、不整合な知識ベース
【数４】
0005646118.tif 000005
から得られる論理式が、古典的推論を使用して、不整合な知識ベース内の整合したサブセットから得られることを意味する。非標準的含意の有意味性は、含意されるすべての回答が有意味であることを意味する。
【００１５】
【数５】
0005646118.tif 000006
の特性は、標準的含意
【数６】
0005646118.tif 000007
のそれと類似している。しかし、重要な例外が存在する。不整合な知識ベース
【数７】
0005646118.tif 000008
と、
【数８】
0005646118.tif 000009
および
【数９】
0005646118.tif 000010
であるような２つの論理式αおよびβとが与えられた場合、
【数１０】
0005646118.tif 000011
であると常に結論付けることができるとは限らない。これの１つの理由は、
【数１１】
0005646118.tif 000012
を支持する選択されたサブセットが、
【数１２】
0005646118.tif 000013
を支持する選択されたサブセットと異なることがある一方で、２つのサブセットの和（ｕｎｉｏｎ）が、不整合である可能性があることであり、別の理由は、α∧βが、矛盾である可能性があることである。
【００１６】
非標準的含意の概念は、ｂｕｔ回答の中心的概念を定義するために使用することができる。形式張らずに言えば、ｂｕｔ回答は、３つの部分を含むことができる。
オリジナル論理式：オリジナルクエリに回答する論理式。
ｂｕｔ論理式：オリジナル回答論理式と対照的である論理式。
ブリッジ論理式：オリジナル論理式とｂｕｔ論理式の間に矛盾が生じる理由を説明する論理式。知識ベースによって、解明論理式（ｃｌａｒｉｆｉｃａｔｉｏｎ  ｆｏｒｍｕｌａ）を暗示する（ことはできるが、その）必要はない。いくつかの応用例シナリオでは、ユーザが対照的な回答の説明を要求しない場合、ｂｕｔ回答において、解明論理式を省略することができる。
【００１７】
本開示における論理式とは、一階論理（ＦＯＬ：ｆｉｒｓｔ−ｏｒｄｅｒ  ｌｏｇｉｃ）論理式を指すことに留意されたい。一般性を失うことなく、記述論理（ＤＬ：ｄｅｓｃｒｉｐｔｉｏｎ  ｌｏｇｉｃ）の公理は、（連言の）ＦＯＬ論理式に変換することができる。多数の論理式は、連言を使用して単一の論理式に変換できるので、以下では、単一の論理式のみを考察する。
【００１８】
上述のことが、ｂｕｔ回答の正式な定義をもたらす。
【００１９】
定義１（ｂｕｔ回答）：不整合な知識ベース
【数１３】
0005646118.tif 000014
が与えられた場合、ｂｕｔ回答
【数１４】
0005646118.tif 000015
は、
【数１５】
0005646118.tif 000016
、
【数１６】
0005646118.tif 000017
、および
【数１７】
0005646118.tif 000018
であり、α∧βは矛盾でなく、β∧γは矛盾でないが、α∧β∧γは矛盾である（すなわち、
【数１８】
0005646118.tif 000019
）ような、以下の部分、すなわち、オリジナル論理式α、ｂｕｔ論理式γ、およびブリッジ論理式βを含む。
【００２０】
ブリッジ論理式は、ｂｕｔ回答から除外することができるが、ｂｕｔ回答は、ブリッジ論理式が存在する場合にのみ対照的であることに留意されたい。論理式は、論理式を満たすことができるモデルが存在しないときかつそのときに限り、矛盾であり、知識ベースは、知識ベース内のすべての論理式を満たすことができるモデルが存在しないときかつそのときに限り、不整合であることにさらに留意されたい。
【００２１】
定義２（説明のないｂｕｔ回答）：不整合な知識ベース
【数１９】
0005646118.tif 000020
が与えられた場合、
【数２０】
0005646118.tif 000021
がｂｕｔ回答であるような、ブリッジ論理式βが存在するならば、
【数２１】
0005646118.tif 000022
は、説明のないｂｕｔ回答である。
【００２２】
上述の定義は、ｂｕｔ回答が良好な交換特性を有することを暗示する。すなわち、オリジナル論理式、ｂｕｔ論理式、およびブリッジ論理式を交換することによって、より多くのｂｕｔ回答を獲得することができる。
【００２３】
命題１（ｂｕｔ回答の交換特性）：不整合な知識ベース
【数２２】
0005646118.tif 000023
と、３つの論理式α、β、γが与えられた場合、以下が成り立つ。
交換（Ｅｘｃｈａｎｇｅ）：
【数２３】
0005646118.tif 000024
条件付きリフティング（Ｃｏｎｄｉｔｉｏｎａｌ  Ｌｉｆｔｉｎｇ）：
【数２４】
0005646118.tif 000025
およびα∧γが、矛盾でない⇒
【数２５】
0005646118.tif 000026
条件付きシフティング（Ｃｏｎｄｉｔｉｏｎａｌ  Ｓｈｉｆｔｉｎｇ）：
【数２６】
0005646118.tif 000027
およびα∧γが、矛盾でない⇒
【数２７】
0005646118.tif 000028
【００２４】
上述の交換特性の他にも、ｂｕｔ回答は、以下の他の特性を有する。
【００２５】
第１に、ｂｕｔ回答内の論理式は、連言演算子∧を用いて、拡張することができる。例えば、「ペンギンは鳥である」、しかし「ペンギンは飛ぶことができない」は、ｂｕｔ回答であり、そのため、「ペンギンは翼をもつ」そして「ペンギンは鳥である」、しかし「ペンギンは飛ぶことができない」もｂｕｔ回答である。
【００２６】
第２に、ｂｕｔ回答では、オリジナル論理式、ｂｕｔ論理式、およびブリッジ論理式は、一緒になって、１つの論理式と他の２つの論理式の連言とは融合（ｒｅｓｏｌｖｅ）させることができるという特性を有する。例えば、「ペンギンは鳥である」、「すべての鳥は飛ぶことができる」のであるが、しかし、「ペンギンは飛ぶことができない」というペンギンの例では、オリジナル論理式は、「ペンギンは鳥である（Ｐｅｎｇｕｉｎｓ  ａｒｅ  ｂｉｒｄｓ）」であり、ブリッジ論理式とｂｕｔ論理式の連言は、「すべての鳥は飛ぶことができる（Ａｌｌ  ｂｉｒｄｓ  ｃａｎ  ｆｌｙ）」そして「ペンギンは飛ぶことができない（Ｐｅｎｇｕｉｎｓ  ｃａｎｎｏｔ  ｆｌｙ）」である。ｂｉｒｄｓがオリジナル論理式の中にある一方で、すべての鳥は飛ぶことができるは、何かは飛ぶことができるか、または鳥ではないかのいずれかであるを意味するので、¬ｂｉｒｄｓが連言の中にあることを理解するのは容易である。
【００２７】
第３に、ｂｕｔ回答
【数２８】
0005646118.tif 000029
が与えられた場合、その中の任意の論理式、例えば、αについて、｛β，γ｝によって含意される論理式¬φが存在し、φはαによって含意され、¬αはαと矛盾する。矛盾は、文「α、しかしγ」が人々を驚かす理由である。
【００２８】
上述の分析に基づいて、ｂｕｔ回答のこれらの追加の特性は、以下のように形式化される。
【００２９】
命題２（ｂｕｔ回答の追加の特性）：不整合な知識ベース
【数２９】
0005646118.tif 000030
と、３つの論理式α、β、γが与えられた場合、
１．１）
【数３０】
0005646118.tif 000031
およびα∧α’∧βは、矛盾ではなく、
【数３１】
0005646118.tif 000032
⇒
【数３２】
0005646118.tif 000033
（拡張）であり、ここで、α’は、任意の論理式である。
１．２）
【数３３】
0005646118.tif 000034
およびα∧β∧β’は、矛盾ではなく、β∧β’∧γは、矛盾ではなく、
【数３４】
0005646118.tif 000035
⇒
【数３５】
0005646118.tif 000036
（拡張）であり、ここで、β’は、任意の論理式である。
１．３）
【数３６】
0005646118.tif 000037
およびβ∧γ∧γ’は、矛盾ではなく、
【数３７】
0005646118.tif 000038
⇒
【数３８】
0005646118.tif 000039
（拡張）であり、ここで、γ’は、任意の論理式である。
２）
【数３９】
0005646118.tif 000040
⇒αおよびβ∧γは融合させることができる（融合）。
３）
【数４０】
0005646118.tif 000041
⇒
【数４１】
0005646118.tif 000042
（意外である理由）。
【００３０】
乗法標準形（ＣＮＦ：ｃｏｎｊｕｎｃｔｉｖｅ  ｎｏｒｍａｌ  ｆｏｒｍ）内の２つの論理式は、ＡがこれらのＣＮＦ論理式の一方の中にあり、¬Ａが他方の中にあるような、原子論理式（ａｔｏｍｉｃ  ｆｏｒｍｕｌａ）Ａが存在するときかつそのときに限り、融合させることができる。
【００３１】
ＩＩＩ．実施
本開示の１つまたは複数の実施形態では、方法は、不整合な知識ベースがオリジナル論理式を非標準的に含意するかどうかを判定することができる。不整合な知識ベースがオリジナル論理式を非標準的に含意する場合、方法は、不整合な知識ベースから、オリジナル論理式とともに融合でき、オリジナル論理式と矛盾しないブリッジ論理式を選択することができる。方法は、オリジナル論理式およびブリッジ論理式の融合節（ｒｅｓｏｌｖｅｎｔ）であるｂｕｔ論理式を選択することができる。方法は、オリジナル論理式とｂｕｔ論理式とを含むｂｕｔ回答を生成することができ、その後、知識ベースがｂｕｔ論理式を非標準的に含意することを確認することによって、ｂｕｔ回答の妥当性を確認することができる。
【００３２】
図１は、本開示の１つまたは複数の実施形態において、不整合な知識ベースを用いてｂｕｔ推論を実施するための、コンピュータの例示的なシステム１００のブロック図である。システム１００は、不整合な知識ベースＫを有するストレージ１０２と、コンピュータ１０４とを含む。不整合な知識ベースＫは、１組のＦＯＬ論理式として表される。ＦＯＬ論理式は、収集し、導出し、またはさもなければワールドワイドウェブなどのコンピュータネットワーク１０６から獲得することができる。ストレージ１０２は、コンピュータ１０４のローカルストレージとすることができ、またはコンピュータネットワークを介した先の別のコンピュータを通してアクセス可能なリモートストレージとすることができる。コンピュータ１０４は、不整合な知識ベースＫに基づいてブールクエリに対するｂｕｔ回答を決定するためにｂｕｔ推論を使用する、不整合リーズナと呼ばれる、ソフトウェアアプリケーションを実行するための、プロセッサおよびメモリを含む。ブールクエリは、コンピュータ１０４上の別のソフトウェアアプリケーション、ユーザ１０８、または別のマシン１１０から発行することができる。
【００３３】
図２は、本開示の１つまたは複数の実施形態による、不整合な知識ベースＫに基づいてブールクエリに対するｂｕｔ回答を決定する不整合リーズナを実施するための、コンピュータ１０４によって実行される例示的な方法２００のフローチャートである。方法２００は、ブロックによって示される１つまたは複数の操作、機能、またはアクションを含むことができる。ブロックは、順次的な順序で示されているが、これらのブロックは、並列して、および／または本明細書で説明される順序とは異なる順序で実行することもできる。また、様々なブロックは、所望の実施に基づいて、組み合わせてより僅かなブロックにすること、分割してさらなるブロックを作ること、および／または除去することができる。
【００３４】
狂牛（Ｍａｄ  Ｃｏｗ）知識ベースに基づいた動作例を使用して、方法２００を説明する。狂牛知識ベースでは、狂牛は羊の脳を食べる（ｅａｔ  ｂｒａｉｎ  ｏｆ  ｓｈｅｅｐ）牛と定義され、牛は草食性（ｖｅｇｅｔａｒｉａｎ）と定義されるので、不整合が存在する。狂牛知識ベース内のＦＯＬ論理式は、以下の表１に列挙されたＤＬ公理として表される。
【表１】
0005646118.tif 000043
ここで、
【数４２】
0005646118.tif 000044
は、包含概念を表し、∃は、存在記号（ｅｘｉｓｔｅｎｔｉａｌ  ｑｕａｎｔｉｆｉｅｒ）（該当する要素が存在する）を表し、∀は、全称記号（ｕｎｉｖｅｒｓａｌ  ｑｕａｎｔｉｆｉｅｒ）（すべての要素に該当する）を表し、¬は、否定を表す。
【００３５】
方法２００は、ブロック２０２において開始することができる。ブロック２０２において、コンピュータ１０４は、不整合な知識ベースＫ内のＦＯＬ論理式を等価なＣＮＦ論理式に変換する。ＣＮＦ論理式は、「節（ｃｌａｕｓｅ）」の連言であり、各節は、「リテラル（ｌｉｔｅｒａｌ）」の選言である。したがって、不整合な知識ベースＫは、ｃ０∧ｃ１∧…∧ｃｉ∧…と表すことができ、ここで、ｃｉは、ρ１∨ρ２∨…であり、リテラルρｉは、原子論理式または原子論理式の否定であり、∨は、選言演算子である。一般に、コンピュータ１０４は、任意のブールクエリを受け取る前に、オフラインでブロック２０２を実行する。代替として、コンピュータ１０４が、任意のブールクエリを受け取る前に、別のコンピュータが、オフラインでブロック２０２を実行する。動作例における、狂牛知識ベース内の変換された論理式を、以下の表２に列挙する。
【表２】
0005646118.tif 000045
ブロック２０２の後には、ブロック２０４が続くことができる。
【００３６】
ブロック２０４において、コンピュータ１０４は、ブールクエリαを受け取り、αは、オリジナル論理式である。動作例において、オリジナル論理式αは、Ｃｏｗ（Ｄａｚｙ）であり、そのため、ブールクエリαは、「Ｄａｚｙは牛か？（Ｉｓ  Ｄａｚｙ  ａ  ｃｏｗ？）」を表す。ブロック２０４の後には、ブロック２０６が続くことができる。
【００３７】
ブロック２０６において、コンピュータ１０４は、不整合な知識ベースＫがオリジナル論理式αを非標準的に含意する（すなわち、
【数４３】
0005646118.tif 000046
である）かどうかを判定する。不整合な知識ベースＫがオリジナル論理式αを非標準的に含意するかどうかを判定するため、コンピュータ１０４は、不整合な知識ベースＫから、オリジナル論理式αを標準的に含意する（すなわち、
【数４４】
0005646118.tif 000047
である）サブセットΣ”を選択する。コンピュータ１０４は、オリジナル論理式αに関連する論理式だけを選択する。非標準的含意を判定するための多くの方法が存在する。本明細書では、非標準的含意のための１つの方法を説明するが、他の方法を使用することもできる。
【００３８】
図３は、本開示の１つまたは複数の実施形態による、不整合な知識ベースＫがオリジナル論理式αを非標準的に含意するかどうかを判定するための、コンピュータ１０４によって実行される例示的な方法３００のフローチャートである。融合技法によれば、ブールクエリ論理式の否定と直接的または間接的に融合させることができる論理式だけが、含意結果に影響することができる。したがって、方法３００は、サブセットΣ”がすべての融合可能関係にある（ｒｅｓｏｌｖａｂｌｙ  ｒｅｌｅｖａｎｔ）論理式を含むか、または不整合になるまで、オリジナル論理式αの否定と融合させることができる論理式をサブセットΣ”に追加するために、選択関数（ｓｅｌｅｃｔｉｏｎ  ｆｕｎｃｔｉｏｎ）「ｒｓ」を使用する。サブセットΣ”が不整合になった場合、方法３００は、サブセットΣ”がその整合性を取り戻すまで、カージナリティ（ｃａｒｄｉｎａｌｉｔｙ）を減少させながら、最後に追加された論理式において、幅優先探索（ｂｒｅａｄｔｈ−ｆｉｒｓｔ  ｓｅａｒｃｈ）を実行する。最後に、方法３００は、不整合な知識ベースＫがオリジナル論理式αを非標準的に含意するかどうかを判定するために、サブセットΣ”がオリジナル論理式αを含意するかどうかを判定する。方法３００は、ブロック３０２において開始する。
【００３９】
ブロック３０２において、コンピュータ１０４は、パスカウント（ｐａｓｓ  ｃｏｕｎｔ）ｋを初期サブセットΣ’を表す１に初期化する。ブロック３０２の後には、ブロック３０４が続くことができる。
【００４０】
ブロック３０４において、コンピュータ１０４は、不整合な知識ベースＫから論理式を初期サブセットΣ’に追加して、現パスについてのサブセットΣ”を形成するために、選択関数ｒｓを使用する。ブロック３０４の後には、ブロック３０６が続くことができる。
【００４１】
ブロック３０６において、コンピュータ１０４は、サブセットΣ”が整合しているかどうかを判定する。整合していない場合、ブロック３０６の後には、ブロック３０８が続くことができる。整合している場合、ブロック３０６の後には、ブロック３１６が続くことができる。
【００４２】
ブロック３０８において、コンピュータ１０４は、サブセットΣ”を整合させるために、サブセットΣ”から１つまたは複数の論理式を取り除く。上で説明したように、コンピュータ１０４は、サブセットΣ”がその整合性を取り戻すまで、カージナリティを減少させながら、最後に追加された論理式において、幅優先探索を実行する。ブロック３０８の後には、ブロック３１０が続くことができる。
【００４３】
ブロック３１０において、コンピュータ１０４は、サブセットΣ”がオリジナル論理式αを標準的に含意するかどうか（すなわち、
【数４５】
0005646118.tif 000048
か？）を判定する。含意しない場合、ブロック３１０の後には、ブロック３１２が続くことができる。含意する場合、ブロック３１０の後には、ブロック３１４が続くことができる。
【００４４】
ブロック３１２において、コンピュータ１０４は、不整合な知識ベースＫはオリジナル論理式αを非標準的に含意しないと判定し、方法３００を終了させる。
【００４５】
ブロック３１４において、コンピュータ１０４は、不整合な知識ベースＫはオリジナル論理式αを非標準的に含意すると判定し、方法３００を終了させる。
【００４６】
ブロック３１６において、コンピュータ１０４は、サブセットΣ”が初期サブセットΣ’のスーパーセット（ｓｕｐｅｒｓｅｔ）であるかどうかを判定する。スーパーセットでない場合、ブロック３１６の後には、ブロック３１８が続くことができる。スーパーセットである場合、ブロック３１６の後には、ブロック３２０が続くことができる。
【００４７】
ブロック３１８において、コンピュータ１０４は、不整合な知識ベースＫはオリジナル論理式αを非標準的に含意しないと判定し、方法３００を終了させる。
【００４８】
ブロック３２０において、コンピュータ１０４は、サブセットΣ”がオリジナル論理式αを標準的に含意するかどうかを判定する。含意する場合、ブロック３２０の後には、ブロック３２２が続くことができる。含意しない場合、ブロック３２０の後には、ブロック３２４が続くことができる。
【００４９】
ブロック３２２において、コンピュータ１０４は、不整合な知識ベースＫはオリジナル論理式αを非標準的に含意すると判定し、方法３００を終了させる。
【００５０】
ブロック３２４において、コンピュータ１０４は、初期サブセットΣ’をサブセットΣ”に等しく設定し、パスカウントｋをインクリメントする。ブロック３２４は、ブロック３０４にループバックして、上で説明されたブロックを繰り返すことができる。
【００５１】
上で説明したように、選択関数ｒｓは、融合可能関係（ｒｅｓｏｌｖａｂｌｅ  ｒｅｌｅｖａｎｃｅ）に基づいている。２つのＣＮＦ論理式
【数４６】
0005646118.tif 000049
は、これらのＣＮＦ論理式の一方の中にＡがあり、他方の中に¬Ａがあるような、原子論理式Ａが存在するときかつそのときに限り、直接的な融合可能関係にある（ｄｉｒｅｃｔｌｙ  ｒｅｓｏｌｖａｂｌｙ  ｒｅｌｅｖａｎｔ）。これは、融合節
【数４７】
0005646118.tif 000050
を有する論理式
【数４８】
0005646118.tif 000051
、または論理式
【数４９】
0005646118.tif 000052
は融合させることができるとも言われる。
【００５２】
ＣＮＦ論理式φおよびφ’は、
【数５０】
0005646118.tif 000053
が直接的な融合可能関係にあるような、論理式
【数５１】
0005646118.tif 000054
が存在するときかつそのときに限り、論理式集合Ωに関して、ｋ次の融合可能関係にある（ｒｅｓｏｌｖａｂｌｙ  ｋ−ｒｅｌｅｖａｎｔ）（次数ｋの間接的な融合可能関係にある（ｋ  ｄｅｇｒｅｅ  ｉｎｄｉｒｅｃｔｌｙ  ｒｅｓｏｖａｂｌｙ  ｒｅｌｅｖａｎｔ））。
【００５３】
本開示の１つまたは複数の実施形態では、選択関数ｒｓは、以下のように定義される。
【数５２】
0005646118.tif 000055
【数５３】
0005646118.tif 000056
【数５４】
0005646118.tif 000057
言い換えると、
【数５５】
0005646118.tif 000058
は、知識ベース
【数５６】
0005646118.tif 000059
内の、φと１次の関係（すなわち、直接的な関係）にあるすべての論理式を選択することを意味し、
【数５７】
0005646118.tif 000060
は、知識ベース
【数５８】
0005646118.tif 000061
内の、φとｋ次の関係にあるすべての論理式を選択することを意味する。
【００５４】
動作例において、方法３００は、以下のようにして、α：＝Ｃｏｗ（Ｄａｚｙ）である場合に、
【数５９】
0005646118.tif 000062
であるかどうかを判定する。
【数６０】
0005646118.tif 000063
【数６１】
0005646118.tif 000064
これは整合しており、
【数６２】
0005646118.tif 000065
であり、ｋ＝２の場合に進んで、続行する。
【数６３】
0005646118.tif 000066
これは整合しており、
【数６４】
0005646118.tif 000067
であり、したがって、
【数６５】
0005646118.tif 000068
である。
【００５５】
図２を再び参照すると、コンピュータ１０４が、不整合な知識ベースＫはオリジナル論理式αを非標準的に含意すると判定した場合、ブロック２０６の後には、ブロック２０８が続くことができる。そのように判定しなかった場合、ブロック２０６の後には、ブロック２２０が続くことができ、回答「分からない」を返す。
【００５６】
ブロック２０８において、コンピュータ１０４は、不整合な知識ベースＫからブリッジ論理式βを選択する。ブロック２０８は、サブブロック２０８Ａと、（２０８Ｂ−１、２０８Ｂ−２、２０８Ｂ−３を含む）２０８Ｂと、２０８Ｃと、２０８Ｄとを含む。
【００５７】
ブロック２０８Ａにおいて、コンピュータ１０４は、不整合な知識ベースＫによって非標準的に含意される論理式をブリッジ論理式βとして選択する。不整合な知識ベースＫがブリッジ論理式βを非標準的に含意する（すなわち、
【数６６】
0005646118.tif 000069
である）場合、ブリッジ論理式βは、いくつかの節の連言、またはその連言の融合節であることに留意されたい。したがって、コンピュータ１０４は、幅優先探索法を使用して、不整合な知識ベースＫによって非標準的に含意されるすべてのブリッジ論理式βを漸増的に選択することができる。
【００５８】
第１のレベル（すなわち、ブロック２０８Ａの１回目のパス）において、コンピュータ１０４は、すべての節ｃｉの連言を選択する。第ｋのレベル（すなわち、ブロック２０８Ａのｋ回目のパス）において、コンピュータ１０４は、ｋ個の異なる節の連言
【数６７】
0005646118.tif 000070
を選択する。ブロック２０８Ａの後には、ブロック２０８Ｂが続くことができる。
【００５９】
ブロック２０８Ｂにおいて、コンピュータ１０４は、フィルタリングを実行する。選択プロセスをより効率的にするため、３つのフィルタリング方法が導入されて、ブリッジ論理式βの数を減少させ、したがって、プロセスをより効率的にする。
【００６０】
ブロック２０８Ｂ−１において、コンピュータ１０４は、拡張フィルタリング（ｅｘｐａｎｓｉｏｎ  ｆｉｌｔｅｒｉｎｇ）を実行することができる。上で説明された命題２の拡張特性によれば、
【数６８】
0005646118.tif 000071
であれば、
【数６９】
0005646118.tif 000072
も満たされ、ここで、ｃｉは、不整合な知識ベースＫ内の節である。したがって、ｋレベルにおいて、
【数７０】
0005646118.tif 000073
が満たされる場合、コンピュータ１０４は、（ｋ＋１）レベルにおいて、β∧ｃｉをブリッジ論理式として選択しない。
【００６１】
ブロック２０８Ｂ−２において、コンピュータ１０４は、矛盾フィルタリング（ｃｏｎｔｒａｄｉｃｔｉｏｎ  ｆｉｌｔｅｒｉｎｇ）を実行することができる。ｋレベルにおいて、ブリッジ論理式βが、α∧βは矛盾であるを満たす場合、β∧ｃｉも矛盾であるので、コンピュータ１０４は、（ｋ＋１）レベルにおいて、β∧ｃｉをブリッジ論理式として選択しない。
【００６２】
ブロック２０８Ｂ−３において、コンピュータ１０４は、融合フィルタリング（ｒｅｓｏｌｕｔｉｏｎ  ｆｉｌｔｅｒｉｎｇ）を実行することができる。ブリッジ論理式βとオリジナル論理式αを融合させることができず、論理式β’とオリジナル論理式αを融合させることができない場合、β∧β’とαは、融合させることができない。したがって、コンピュータ１０４は、β∧β’をブリッジ論理式として選択しない。ブロック２０８Ｂの後には、ブロック２０８Ｃが続くことができる。
【００６３】
ブロック２０８Ｃにおいて、コンピュータ１０４は、現パスにおいて選択されたすべてのブリッジ論理式に対して、融合条件をチェックする。各ブリッジ論理式βについて、コンピュータ１０４は、オリジナル論理式αとブリッジ論理式βを融合させることができるかどうかをテストする。融合させることができる場合、ブリッジ論理式βは、保持され、ブロック２０８Ｃの後には、ブロック２０８Ｄが続くことができる。ブリッジ論理式βが拒否された場合、少なくとも１つの終了条件が満たされているかどうかをチェックするために、ブロック２０８Ｃの後には、ブロック２１６が続くことができる。
【００６４】
ブロック２０８Ｄにおいて、コンピュータ１０４は、現パスにおいて選択されたすべてのブリッジ論理式に対して、矛盾条件をチェックする。各ブリッジ論理式βについて、コンピュータ１０４は、α∧βが矛盾かどうかをテストする。矛盾ではない場合、ブリッジ論理式βは、保持され、ブロック２０８Ｄの後には、ブロック２１０が続くことができる。ブリッジ論理式βが拒否された場合、少なくとも１つの終了条件が満たされているかどうかをチェックするために、ブロック２０８Ｄの後には、ブロック２１６が続くことができる。
【００６５】
ブロック２１０において、コンピュータ１０４は、ｂｕｔ回答を構成する。各ブリッジ論理式βについて、コンピュータ１０４は、α∧βの融合節λを決定する。融合節λが、後で妥当性を確認する必要がある候補ｂｕｔ論理式であることを示すために、ここでは、記号γの代わりに、記号λが使用されていることに留意されたい。各融合節λについて、コンピュータ１０４は、オリジナル論理式αと、ｂｕｔ論理式¬λと、ブリッジ論理式βとを含む、ｂｕｔ回答を構成する。ブロック２１０の後には、ブロック２１２が続くことができる。
【００６６】
ブロック２１２において、コンピュータ１０４は、ｂｕｔ回答の妥当性を確認する。各ｂｕｔ回答
【数７１】
0005646118.tif 000074
について、コンピュータ１０４は、不整合な知識ベースＫが¬λを非標準的に含意するかどうかを判定する。含意する場合、ｂｕｔ回答の妥当性が確認され、ブロック２１２の後には、ブロック２１４が続くことができる。ｂｕｔ回答の妥当性が確認できなかった場合、ブロック２１２の後には、ブロック２１６が続くことができる。
【００６７】
ブロック２１４において、コンピュータ１０４は、ｂｕｔ回答をセーブする。ブロック２１４の後には、ブロック２１６が続くことができる。
【００６８】
ブロック２１６において、コンピュータ１０４は、少なくとも１つの終了条件が満たされているかどうかを判定する。
【００６９】
プロセスは、少なくとも１つの終了条件が満たされるまで反復される。１つの妥当性確認プロセスが完了した場合、またはブリッジ論理式の１つの選択プロセスが失敗した場合、コンピュータ１０４は、方法２００を停止させるかどうかを判定するために、終了条件をチェックする。ユーザが指定できる終了条件が、以下で説明される。
【００７０】
１つのｂｕｔ回答を見つけたときに停止する。ブリッジ論理式βを漸増的に獲得し、対応するｂｕｔ回答を計算するために、方法２００が使用される。この終了条件の下では、コンピュータ１０４は、１つのｂｕｔ回答が獲得されたときに、方法２００を停止させる。
【００７１】
ｋレベルにおける探索。ユーザは、方法２００においてブリッジ論理式βを選択するための値ｋを指定することができる。その場合、コンピュータ１０４は、探索の次数をたかだかレベルｋに保つことによって、すべてのｂｕｔ回答を計算する。
【００７２】
ｔ時間内での探索。ユーザは、時間の値ｔを指定することができる。方法２００は、すべてのｂｕｔ回答を計算し始める。候補ｂｕｔ回答の妥当性を確認した後、コンピュータ１０４は、実行時間がｔよりも大きくなったときに、方法２００を停止させる。
【００７３】
ｂｕｔ回答を計算するための他の終了条件も存在し、これらの条件は組み合わせることができる。
【００７４】
少なくとも１つの終了条件が満たされたとき、ブロック２１６の後には、ブロック２１８が続くことができる。さもなければ、ブロック２１６はブロック２０８にループバックして、別のブリッジ論理式を選択することができる。
【００７５】
ブロック２１８において、コンピュータ１０４は、１つまたは複数のｂｕｔ回答を送信または表示する。各ｂｕｔ回答は、オリジナル論理式αと、ｂｕｔ論理式¬λとを含み、ブリッジ論理式βをさらに含むことができる。
【００７６】
動作例における、ブロック２０８Ａからブロック２１６を、ｋ＝１およびｋ＝２の場合について示すと、以下のようになる。
【数７２】
0005646118.tif 000075
についてのブリッジ論理式を選択する。ｋ＝１の場合、ただ１つの
【数７３】
0005646118.tif 000076
しか存在しないので、フィルタリングプロセスには何の効果もなく、α１は、αと融合させることができ、α１∧αは、矛盾ではない。したがって、β：＝α１である。
α１およびαは、１つの融合節Ｖｅｇｅｔａｒｉａｎ（Ｄａｚｙ）しか有さないので、候補
【数７４】
0005646118.tif 000077
を構成する。
【数７５】
0005646118.tif 000078
か？をチェックする。方法３００を使用して、
【数７６】
0005646118.tif 000079
であると決定される。したがって、コンピュータ１０４は、
【数７７】
0005646118.tif 000080
というｂｕｔ回答を返す。
ｋ＝２の場合、拡張フィルタリングおよび融合フィルタリングによれば、
【数７８】
0005646118.tif 000081
および
【数７９】
0005646118.tif 000082
のみが、ブリッジ論理式として選択される。
候補
【数８０】
0005646118.tif 000083
および
【数８１】
0005646118.tif 000084
を構成する。
【数８２】
0005646118.tif 000085
か？および
【数８３】
0005646118.tif 000086
か？をチェックする。方法３００を使用して、
【数８４】
0005646118.tif 000087
および
【数８５】
0005646118.tif 000088
であると決定される。したがって、
【数８６】
0005646118.tif 000089
というｂｕｔ回答が獲得される。
すべてのチェックポイントにおいて、コンピュータ１０４は、方法２００を終了させるべきかを判定するために、終了条件をチェックする。
【００７７】
図４は、本開示の１つまたは複数の実施形態による、不整合な知識ベースに基づいてブールクエリに対するｂｕｔ回答を決定するための方法を実施するための、コンピュータプログラム製品４００の例示的な一実施形態のブロック図である。コンピュータプログラム製品４００は、信号保持媒体４０２を含むことができる。信号保持媒体４０２は、例えばプロセッサによって実行されたときに、上で説明された機能を提供するように適合できる、１組または複数組の実行可能命令４０４を含むことができる。したがって、例えば、図１のコンピュータ１０４は、信号保持媒体４０２によって搬送された命令４０４に応答して、少なくとも図２または図３に示されたブロックの１つまたは複数に着手することができる。
【００７８】
いくつかの実施では、信号保持媒体４０２は、ハードディスクドライブ、コンパクトディスク（ＣＤ）、デジタル多用途ディスク（ＤＶＤ）、デジタルテープ、メモリなどの、しかし、それらに限定されない、非一時的なコンピュータ可読媒体４０６を包含することができる。いくつかの実施では、信号保持媒体４０２は、メモリ、リード／ライト（Ｒ／Ｗ）ＣＤ、Ｒ／Ｗ  ＤＶＤなどの、しかし、それらに限定されない、記録可能媒体４０８を包含することができる。いくつかの実施では、信号保持媒体４０２は、デジタルおよび／またはアナログ通信媒体（例えば、光ファイバケーブル、導波路、有線通信リンク、無線通信リンクなど）などの、しかし、それらに限定されない、通信媒体４１０を包含することができる。したがって、例えば、コンピュータプログラム製品４００は、信号保持媒体４０２によって無線で搬送することができ、その場合、信号保持媒体４０２は、無線通信媒体５１０（例えば、ＩＥＥＥ８０２．１１規格に準拠した無線通信媒体）によって搬送される。コンピュータプログラム製品４００は、非一時的なコンピュータ可読媒体４０６または別の類似の記録可能媒体４０８上に記録することができる。
【００７９】
図５は、本開示に従ってｂｕｔ推論のために構成された、例示的なコンピューティングデバイス５００を説明するブロック図である。非常に基本的な構成５０２では、コンピューティングデバイス５００は、一般に、１つまたは複数のプロセッサ５０４と、システムメモリ５０６とを含むことができる。メモリバス５０８は、プロセッサ５０４とシステムメモリ５０６の間で通信を行うために使用することができる。
【００８０】
所望の構成に応じて、プロセッサ５０４は、マイクロプロセッサ（μＰ）、マイクロコントローラ（μＣ）、デジタル信号プロセッサ（ＤＳＰ）、またはそれらの任意の組み合わせを含むが、それらに限定されない、任意のタイプを取ることができる。プロセッサ５０４は、レベル１キャッシュ５１０およびレベル２キャッシュ５１２などの１つまたは複数のレベルのキャッシングと、プロセッサコア５１４と、レジスタ５１６とを含むことができる。例示的なプロセッサコア５１４は、算術論理演算ユニット（ＡＬＵ）、浮動小数点ユニット（ＦＰＵ）、デジタル信号処理コア（ＤＳＰコア）、またはそれらの任意の組み合わせを含むことができる。例示的なメモリコントローラ５１８も、プロセッサ５０４とともに使用することができ、またはいくつかの実施では、メモリコントローラ５１８は、プロセッサ５０４の内部部品とすることができる。
【００８１】
所望の構成に応じて、システムメモリ５０６は、（ＲＡＭなどの）揮発性メモリ、（ＲＯＭ、フラッシュメモリなどの）不揮発性メモリ、またはそれらの任意の組み合わせを含むが、それらに限定されない、任意のタイプを取ることができる。システムメモリ５０６は、オペレーティングシステム５２０と、１つまたは複数のアプリケーション５２２と、プログラムデータ５２４とを含むことができる。アプリケーション５２２は、ブールクエリに対するｂｕｔ回答を決定するように構成された、不整合リーズナ５２６を含むことができる。プログラムデータ５２４は、本明細書で説明されたような不整合リーズナ５２６とともに動作する不整合な知識ベース５２８を含むことができる。いくつかの実施形態では、アプリケーション５２２は、ｂｕｔ推論の実施が本明細書で説明したように提供され得るように、オペレーティングシステム５２０上でプログラムデータ５２４を用いて動作するように構成することができる。図５では、この説明された基本構成５０２は、内側の破線内のコンポーネントによって示されている。
【００８２】
コンピューティングデバイス５００は、追加の特徴または機能と、基本構成５０２と任意の必要なデバイスおよびインターフェースの間の通信を円滑化するための追加のインターフェースとを有することができる。例えば、バス／インターフェースコントローラ５３０は、ストレージインターフェースバス５３４を介する、基本構成５０２と１つまたは複数のデータ記憶装置５３２の間の通信を円滑化するために使用することができる。データ記憶装置５３２は、取外し式記憶装置５３６、非取外し式記憶装置５３８、またはそれらの組み合わせとすることができる。取外し式記憶装置および非取外し式記憶装置の例は、いくつかの名前を挙げると、フレキシブルディスクドライブおよびハードディスクドライブ（ＨＤＤ）などの磁気ディスク装置、コンパクトディスク（ＣＤ）ドライブまたはデジタル多用途ディスク（ＤＶＤ）ドライブなどの光ディスクドライブ、ソリッドステートドライブ（ＳＳＤ）、ならびにテープドライブを含む。例示的なコンピュータ記憶媒体は、コンピュータ可読命令、データ構造、プログラムモジュール、または他のデータなどの情報を記憶するための任意の方法または技術で実施された、揮発性および不揮発性の取外し式および非取外し式媒体を含むことができる。
【００８３】
システムメモリ５０６、取外し式記憶装置５３６、および非取外し式記憶装置５３８は、コンピュータ記憶媒体の例である。コンピュータ記憶媒体は、ＲＡＭ、ＲＯＭ、ＥＥＰＲＯＭ、フラッシュメモリ、もしくは他のメモリ技術、ＣＤ−ＲＯＭ、デジタル多用途ディスク（ＤＶＤ）、もしくは他の光ストレージ、磁気カセット、磁気テープ、磁気ディスクストレージ、もしくは他の磁気記憶装置、または所望の情報を記憶するのに使用でき、コンピューティングデバイス５００によってアクセスできる他の任意の媒体を含むが、それらに限定されない。そのようなコンピュータ記憶媒体はいずれも、コンピューティングデバイス５００の一部とすることができる。
【００８４】
コンピューティングデバイス５００は、バス／インターフェースコントローラ５３０を介する、様々なインターフェース装置（例えば、出力装置５４２、周辺インターフェース５４４、および通信装置５４６）から基本構成５０２への通信を円滑化するための、インターフェースバス５４０も含むことができる。例示的な出力装置５４２は、１つまたは複数のＡ／Ｖポート５５２を介してディスプレイまたはスピーカなどの様々な外部装置と通信するように構成できる、グラフィックス処理ユニット５４８およびオーディオ処理ユニット５５０を含む。例示的な周辺インターフェース５４４は、１つまたは複数のＩ／Ｏポート５５８を介して、入力装置（例えば、キーボード、マウス、ペン、音声入力装置、タッチ入力装置など）または他の周辺装置（例えば、プリンタ、スキャナなど）などの、外部装置と通信するように構成できる、シリアルインターフェースコントローラ５５４またはパラレルインターフェースコントローラ５５６を含む。例示的な通信装置５４６は、１つまたは複数の通信ポート５６４を介する、ネットワーク通信リンク上での、１つまたは複数の他のコンピューティングデバイス５６２との通信を円滑化するように構成できる、ネットワークコントローラ５６０を含む。
【００８５】
ネットワーク通信リンクは、通信媒体の一例とすることができる。通信媒体は、搬送波または他のトランスポートメカニズムなどの変調データ信号内のコンピュータ可読命令、データ構造、プログラムモジュール、または他のデータによって一般に具現することができ、任意の情報配送媒体を含むことができる。「変調データ信号」は、情報を信号内に符号化するなどの方法で、その特性の１つまたは複数が設定または変更された信号とすることができる。限定することなく、例を挙げると、通信媒体は、有線ネットワークまたは直接配線接続などの有線媒体、ならびに音響、無線周波（ＲＦ）、マイクロ波、赤外線（ＩＲ）、および他の無線媒体などの無線媒体を含むことができる。本明細書で使用される場合、コンピュータ可読媒体という用語は、記憶媒体と通信媒体の両方を含むことができる。
【００８６】
コンピューティングデバイス５００は、セルフォン、携帯情報端末（ＰＤＡ）、パーソナルメディアプレーヤデバイス、無線ウェブウォッチデバイス、パーソナルヘッドセットデバイス、特定用途向けデバイス、または上述の機能のいずれかを含むハイブリッドデバイスなど、フォームファクタが小さいポータブル（またはモバイル）電子デバイスの一部として実施することができる。コンピューティングデバイス５００は、ラップトップコンピュータおよび非ラップトップコンピュータ構成の両方を含むパーソナルコンピュータとしても実施することができる。
【００８７】
前述の詳細な説明では、ブロック図、フローチャート、および／または例の使用によって、装置および／またはプロセスの様々な実施形態を説明してきた。そのようなブロック図、フローチャート、および／または例が１つまたは複数の機能および／または動作を含む限りにおいて、そのようなブロック図、フローチャート、または例の中のそれぞれの機能および／または動作は、広範囲のハードウェア、ソフトウェア、ファームウェア、または実質上それらのすべての組み合わせにより、個別におよび／または集合的に実装可能であることが、当業者には理解されるであろう。
【００８８】
本明細書に記載された主題は、様々なコンポーネントをしばしば例示しており、これらのコンポーネントは、他の様々なコンポーネントに包含されるか、または他の様々なコンポーネントに接続される。そのように図示されたアーキテクチャは、単に例示にすぎず、実際には、同じ機能を実現する多くの他のアーキテクチャが実装可能であることが理解されよう。概念的な意味で、同じ機能を実現するコンポーネントの任意の構成は、所望の機能が実現されるように効果的に「関連付け」される。したがって、特定の機能を実現するために組み合わされた、本明細書における任意の２つのコンポーネントは、アーキテクチャまたは中間のコンポーネントにかかわらず、所望の機能が実現されるように、お互いに「関連付け」されていると見ることができる。同様に、そのように関連付けされた任意の２つのコンポーネントは、所望の機能を実現するために、互いに「動作可能に接続」または「動作可能に結合」されていると見なすこともでき、そのように関連付け可能な任意の２つのコンポーネントは、所望の機能を実現するために、互いに「動作可能に結合できる」と見なすこともできる。動作可能に結合できる場合の具体例には、物理的にかみ合わせ可能な、および／もしくは物理的に相互作用するコンポーネントが含まれるが、それらに限定されない。
【００８９】
本明細書における実質的にすべての複数形および／または単数形の用語の使用に対して、当業者は、状況および／または用途に適切なように、複数形から単数形に、および／または単数形から複数形に変換することができる。様々な単数形／複数形の置き換えは、理解しやすいように、本明細書で明確に説明することができる。
【００９０】
通常、本明細書において、特に添付の特許請求の範囲（例えば、添付の特許請求の範囲の本体部）において使用される用語は、全体を通じて「オープンな（ｏｐｅｎ）」用語として意図されていることが、当業者には理解されよう（例えば、用語「含む（ｉｎｃｌｕｄｉｎｇ）」は、「含むがそれに限定されない（ｉｎｃｌｕｄｉｎｇ  ｂｕｔ  ｎｏｔ  ｌｉｍｉｔｅｄ  ｔｏ）」と解釈されるべきであり、用語「有する（ｈａｖｉｎｇ）」は、「少なくとも有する（ｈａｖｉｎｇ  ａｔ  ｌｅａｓｔ）」と解釈されるべきであり、用語「含む（ｉｎｃｌｕｄｅｓ）」は、「含むがそれに限定されない（ｉｎｃｌｕｄｅｓ  ｂｕｔ  ｉｓ  ｎｏｔ  ｌｉｍｉｔｅｄ  ｔｏ）」と解釈されるべきである、など）。導入される請求項で具体的な数の記載が意図される場合、そのような意図は、当該請求項において明示的に記載されることになり、そのような記載がない場合、そのような意図は存在しないことが、当業者にはさらに理解されよう。例えば、理解の一助として、添付の特許請求の範囲は、導入句「少なくとも１つの（ａｔ  ｌｅａｓｔ  ｏｎｅ）」および「１つまたは複数の（ｏｎｅ  ｏｒ  ｍｏｒｅ）」を使用して請求項の記載を導くことを含む場合がある。しかし、そのような句の使用は、同一の請求項が、導入句「１つまたは複数の」または「少なくとも１つの」および「ａ」または「ａｎ」などの不定冠詞を含む場合であっても、不定冠詞「ａ」または「ａｎ」による請求項の記載の導入が、そのように導入される請求項の記載を含む任意の特定の請求項を、単に１つのそのような記載を含む発明に限定する、ということを示唆していると解釈されるべきではない（例えば、「ａ」および／または「ａｎ」は、通常、「少なくとも１つの」または「１つまたは複数の」を意味すると解釈されるべきである）。同じことが、請求項の記載を導入するのに使用される定冠詞の使用にも当てはまる。また、導入される請求項の記載で具体的な数が明示的に記載されている場合でも、そのような記載は、通常、少なくとも記載された数を意味すると解釈されるべきであることが、当業者には理解されよう（例えば、他の修飾語なしでの「２つの記載（ｔｗｏ  ｒｅｃｉｔａｔｉｏｎｓ）」の単なる記載は、通常、少なくとも２つの記載、または２つ以上の記載を意味する）。さらに、「Ａ、ＢおよびＣ、などの少なくとも１つ」に類似の慣例表現が使用されている事例では、通常、そのような構文は、当業者がその慣例表現を理解するであろう意味で意図されている（例えば、「Ａ、Ｂ、およびＣの少なくとも１つを有するシステム」は、Ａのみ、Ｂのみ、Ｃのみ、ＡおよびＢを共に、ＡおよびＣを共に、ＢおよびＣを共に、ならびに／またはＡ、Ｂ、およびＣを共に、などを有するシステムを含むが、それに限定されない）。「Ａ、Ｂ、またはＣ、などの少なくとも１つ」に類似の慣例表現が使用されている事例では、通常、そのような構文は、当業者がその慣例表現を理解するであろう意味で意図されている（例えば、「Ａ、Ｂ、またはＣの少なくとも１つを有するシステム」は、Ａのみ、Ｂのみ、Ｃのみ、ＡおよびＢを共に、ＡおよびＣを共に、ＢおよびＣを共に、ならびに／またはＡ、Ｂ、およびＣを共に、などを有するシステ���を含むが、それに限定されない）。２つ以上の代替用語を提示する事実上いかなる離接する語および／または句も、明細書、特許請求の範囲、または図面のどこにあっても、当該用語の一方（ｏｎｅ  ｏｆ  ｔｈｅ  ｔｅｒｍｓ）、当該用語のいずれか（ｅｉｔｈｅｒ  ｏｆ  ｔｈｅ  ｔｅｒｍｓ）、または両方の用語（ｂｏｔｈ  ｔｅｒｍｓ）を含む可能性を企図すると理解されるべきであることが、当業者にはさらに理解されよう。例えば、句「ＡまたはＢ」は、「Ａ」または「Ｂ」あるいは「ＡおよびＢ」の可能性を含むことが理解されよう。
【００９１】
本明細書では、様々な態様および実施形態が開示されたが、他の態様および実施形態も当業者には明らかである。本明細書で開示された様々な態様および実施形態は、例示を目的としており、限定することは意図しておらず、真の範囲および主旨は、以下の特許請求の範囲によって示されている。
【図１】
0005646118.tif 000096
【図２】
0005646118.tif 000097
【図３】
0005646118.tif 000098
【図４】
0005646118.tif 000099
【図５】
0005646118.tif 000100