(57)【特許請求の範囲】
【請求項１】
述語記号に対応し所定の順序で並べられた複数の列と前記複数の列のいずれかの位置に配置されるセルを含む行とにより構成される表であり各セルにはそのセルの位置する列に対応する述語記号に適用することにより論理式を形成する値が格納されている表、に対応付けられるグラフデータ構造を有するルールベースであり、メモリ空間に配置されるルートノードと、前記表の各行における複数のセルの並びに対応して前記メモリ空間に前記列の順序にてポインタにより直列に接続される複数のノードの各並びと、を有し、前記複数のノードの各並びの両端のノードをポインタにより前記ルートノードに接続し、前記ルートノードから前記ノードを、ポインタをたどって順に読み出し走査可能とし、前記表の各行は、複数の論理式を論理積として左辺に並べ他の論理式を右辺に並べたルールを表すことを特徴とする、グラフデータ構造を有するルールベースと、
複数の入力領域に入力された情報であり前記論理式の真偽を判定するための情報を取得する情報取得部と、
前記情報取得部により取得された情報により、前記ルールいずれかの右辺の論理式が真と判定されると、前記真と判定された論理式が右辺に並ぶルールの左辺に並ぶ論理積の複数の論理式を表すノードを走査し、前記真と判定された論理式が右辺に並ぶルールが成り立つために真と判定されるべき論理式を算出し、前記情報取得部により取得された情報により、前記ルールの全ての右辺の論理式の真偽が不定であると判定されると、前記直列に接続されたノードを走査し、前記複数のルールのいずれかのルールの右辺に並ぶ論理式のうち真となる論理式を算出する推論部と
を有する推論装置。
【請求項２】
前記表の隣接する行において同じ列の位置に配置されるセルが格納する値が同じ値であれば、前記同じ値を格納する前記セルが統合されていることを特徴とする請求項１に記載の推論装置。
【請求項３】
前記複数のルールに並ぶ論理式の述語記号を順に左から右に並ぶ列名とし、各行を各ルールに対応付けて対応する列に前記各ルールに並ぶ論理式が有する定数を並べた表を作成した場合、最も右に並ぶ列を除き、各列に格納される値の種類の数は、その右隣の列の値の種類の数以下となることを特徴とする請求項１記載の推論装置。
【請求項４】
述語記号に対応し所定の順序で並べられた複数の列と前記複数の列のいずれかの位置に配置されるセルを含む行とにより構成される表であり各セルにはそのセルの位置する列に対応する述語記号に適用することにより論理式を形成する値が格納されている表、に対応付けられるグラフデータ構造を有するルールベースであり、メモリ空間に配置されるルートノードと、前記表の各行における複数のセルの並びに対応して前記メモリ空間に前記列の順序にてポインタにより直列に接続される複数のノードの各並びと、を有し、前記複数のノードの各並びの両端のノードをポインタにより前記ルートノードに接続し、前記ルートノードから前記ノードを、ポインタをたどって順に読み出し走査可能とし、前記表の各行は、複数の論理式を論理積として左辺に並べ他の論理式を右辺に並べたルールを表すことを特徴とする、グラフデータ構造により記憶されるルールベースを参照するコンピュータが実行する推論方法であり、
複数の入力領域に入力された情報であり前記論理式の真偽を判定するための情報を取得しメモリに記憶し、
前記取得された情報により、前記ルールいずれかの右辺の論理式が真と判定されると、前記真と判定された論理式が右辺に並ぶルールの左辺に並ぶ論理積の複数の論理式を表すノードを走査して前記真と判定された論理式が右辺に並ぶルールが成り立つために真と判定されるべき論理式を算出し、
前記取得された情報により、前記ルールの全ての右辺の論理式の真偽が不定であると判定されると、前記直列に接続されたノードを走査し、前記複数のルールのいずれかのルールの右辺に並ぶ論理式のうち真となる論理式を算出する
ことを含む推論方法。
【請求項５】
複数の論理式を論理積として左辺に並べ他の論理式を右辺に並べた複数のルールを、それぞれのルールに関して、ルールに並ぶ論理式を表すノードを直列に接続し列の両端のノードをルートノードに接続したグラフデータ構造により、記憶するルールベースと、
複数の入力領域に入力された情報であり前記論理式の真偽を判定するための情報を取得する情報取得部と、
前記情報取得部により取得された情報により、前記複数のルールいずれかのルールの右辺の論理式が真と判定されると、前記真と判定された論理式が右辺に並ぶルールの左辺に並ぶ論理積の複数の論理式を表すノードを走査し、前記真と判定された論理式が右辺に並ぶルールが成り立つために真と判定されるべき論理式を算出し、前記情報取得部により取得された情報により、前記複数のルールの全てのルールの右辺の論理式の真偽が不定であると判定されると、前記直列に接続されたノードを走査し、前記複数のルールのいずれかのルールの右辺に並ぶ論理式のうち真となる論理式を算出する推論部と
を有する推論装置。
【請求項６】
前記複数のルールそれぞれの右辺に並ぶ論理式の中に同じ論理式があれば、前記グラフデータ構造において前記同じ論理式を表すノードがマージされていることを特徴とする請求項５に記載の推論装置。
【請求項７】
前記複数のルールそれぞれの左辺に並ぶ論理式を表すノードのうち前記ルートノードから等しい距離にあるノードの表す論理式の述語記号が同じであることを特徴とする請求項５に記載の推論装置。
【請求項８】
前記複数のルールに並ぶ論理式の述語記号を順に左から右に並ぶ列名とし、各行を各ルールに対応付けて対応する列に前記各ルールに並ぶ論理式が有する定数を並べた表を作成した場合、最も右に並ぶ列を除き、各列に格納される値の種類の数は、その右隣の列の値の種類の数以下となることを特徴とする請求項７に記載の推論装置。
【請求項９】
前記複数のルールそれぞれの左辺に並ぶ論理式を表すノードそれぞれに直接接続されるノードの表す論理式が同じであれば、その同じ論理式を表すノードが前記グラフデータ構造においてマージされていることを特徴とする請求項７に記載の推論装置。
【請求項１０】
複数の論理式を論理積として左辺に並べ他の論理式を右辺に並べた複数のルールを、それぞれのルールに関して、ルールに並ぶ論理式を表すノードを直列に接続し列の両端のノードをルートノードに接続したグラフデータ構造により、記憶するルールベースを参照するコンピュータが実行する推論方法であり、
複数の入力領域に入力された情報であり前記論理式の真偽を判定するための情報を取得しメモリに記憶し、
前記取得された情報により、前記複数のルールいずれかのルールの右辺の論理式が真と判定されると、前記真と判定された論理式が右辺に並ぶルールの左辺に並ぶ論理積の複数の論理式を表すノードを走査して前記真と判定された論理式が右辺に並ぶルールが成り立つために真と判定されるべき論理式を算出し、
前記取得された情報により、前記複数のルールの全てのルールの右辺の論理式の真偽が不定であると判定されると、前記直列に接続されたノードを走査し、前記複数のルールのいずれかのルールの右辺に並ぶ論理式のうち真となる論理式を算出する
ことを含む推論方法。
【請求項１１】
述語記号に対応し所定の順序で並べられた複数の列と前記複数の列のいずれかの位置に配置されるセルを含む行とにより構成される表であり各セルにはそのセルの位置する列に対応する述語記号に適用する値が格納されている表、に対応付けられるグラフデータ構造を有するルールベースであり、
メモリ空間に配置されるルートノードと、
前記表の各行における複数のセルの並びに対応して前記メモリ空間に前記列の順序にてポインタにより直列に接続される複数のノードの各並びと、
を有し、前記複数のノードの各並びの両端のノードをポインタにより前記ルートノードに接続し、計算機に前記ルートノードから前記ノードを、ポインタをたどって順に読み出し可能とし、
前記表の隣接する行において同じ列の位置に配置されるセルが格納する値が同じ値であれば、前記同じ値を格納する前記セルが統合されていることを特徴とする、グラフデータ構造を有するルールベースを備える推論装置。
【請求項１２】
列の位置に配置されるセルに格納される値の種類が少ないほどその列は前記順序の最初の方に位置することを特徴とする請求項１１に記載の、グラフデータ構造を有するルールベースを備える推論装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、推論装置および推論方法などに関する。特に、ルールをグラフデータ構造によって表現し、判断の結論を得るための前向き推論および期待される結論を得るための後ろ向き推論の両方を行なうことができる推論装置および推論方法などに関する。
【背景技術】
【０００２】
銀行業務などの事務処理に計算機システムが用いられている。事務処理においては、どのような条件下にて次にどのような処理を行なうのかの事務規則が定められている。従来においては、事務処理に用いられる計算機システムを構築する際には、計算機システムで動作するプログラムのロジックの中にこのような事務規則が取り込まれていた。このため、事務規則が変更になるたびにプログラム全体の改修が必要となっていた。
【０００３】
そこで、プログラムのロジックから事務規則を分離することが行なわれている。すなわち、事務規則などをルールとして形式言語により記述しルールベースに格納しルールエンジンなどの推論装置（例えば特許文献１−４参照。）に推論を行なわせるようにし、推論に必要なデータをプログラムからルールエンジンに入力し推論の結論をルールエンジンからプログラムに返信することが行なわれている。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開平５−３４６８５５号公報
【特許文献２】特開平６−４４０７４号公報
【特許文献３】特開２００７−２５７２８５号公報
【特許文献４】特開２００７−１９３４５７号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
従来のルールエンジンにおいてはルールベースに格納されるルールは、木構造として表現されていた。このため、木構造のルートからリーフに向かう方向の推論は高速に行なえるが、逆方向の推論を行なうことは不可能であるか、行なえたとしても効率が悪くなっていた。
【課題を解決するための手段】
【０００６】
そこで、与えられた条件から結論を導くこと及び期待される結論を得るための条件を得ることの両方を効率良く行なえる推論装置について開示を行なう。
【０００７】
すなわち、本発明の一実施形態として、複数の論理式を論理積として左辺に並べ他の論理式を右辺に並べた複数のルールを、それぞれのルールに関して、ルールに並ぶ論理式を表すノードを直列に接続し列の両端のノードをルートノードに接続したグラフデータ構造により、記憶するルールベースと、複数の入力領域に入力された情報であり前記論理式の真偽を判定するための情報を取得する情報取得部と、前記情報取得部により取得された情報により、前記複数のルールのいずれかのルールの右辺の論理式が真と判定されると、前記真と判定された論理式が右辺に並ぶルールの左辺に並ぶ論理積の複数の論理式を表すノードを走査し、前記真と判定された論理式が右辺に並ぶルールが成り立つために真と判定されるべき論理式を算出し、前記情報取得部により取得された情報により、前記複数のルールの全てのルールの右辺の論理式の真偽が不定であると判定されると、前記直列に接続されたノードを走査し、前記複数のルールのいずれかのルールの右辺に並ぶ論理式のうち真となる論理式を算出する推論部とを有する推論装置を提供する。
【０００８】
また、本発明の一実施形態として、述語記号に対応し所定の順序で並べられた複数の列と前記複数の列のいずれかの位置に配置されるセルを含む行とにより構成される表であり各セルにはそのセルの位置する列に対応する述語記号に適用することにより論理式を形成する値が格納されている表、に対応付けられるグラフデータ構造を有するルールベースであり、メモリ空間に配置されるルートノードと、前記表の各行における複数のセルの並びに対応して前記メモリ空間に前記列の順序にてポインタにより直列に接続される複数のノードの各並びと、を有し、前記複数のノードの各並びの端のノードをポインタにより前記ルートノードに接続し、前記ルートノードから前記ノードを、ポインタをたどって順に読み出し走査可能とし、前記表の各行は、複数の論理式を論理積として右辺に並べ他の論理式を右辺に並べたルールを表すことを特徴とする、グラフデータ構造を有するルールベースと、複数の入力領域に入力された情報であり前記論理式の真偽を判定するための情報を取得する情報取得部と、前記情報取得部により取得された情報により、前記ルールいずれかの右辺の論理式が真と判定されると、前記真と判定された論理式が右辺に並ぶルールの左辺に並ぶ論理積の複数の論理式を表すノードを走査し、前記真と判定された論理式が右辺に並ぶルールが成り立つために真と判定されるべき論理式を算出し、前記情報取得部により取得された情報により、前記ルールの全ての右辺の論理式の真偽が不定であると判定されると、前記直列に接続されたノードを走査し、前記複数のルールのいずれかのルールの右辺に並ぶ論理式のうち真となる論理式を算出する推論部とを有する推論装置を提供する。
【０００９】
また、本発明の一実施形態として、複数の論理式を論理積として左辺に並べ他の論理式を右辺に並べた複数のルールを、それぞれのルールに関して、ルールに並ぶ論理式を表すノードを直列に接続し列の両端のノードをルートノードに接続したグラフデータ構造により、記憶するルールベースを参照するコンピュータが実行する推論方法であり、複数の入力領域に入力された情報であり前記論理式の真偽を判定するための情報を取得しメモリに記憶し、前記取得された情報により、前記複数のルールのいずれかのルールの右辺の論理式が真と判定されると、前記真と判定された論理式が右辺に並ぶルールの左辺に並ぶ論理積の複数の論理式を表すノードを走査して前記真と判定された論理式が右辺に並ぶルールが成り立つために真と判定されるべき論理式を算出し、前記取得された情報により、前記複数のルールの全てのルールの右辺の論理式の真偽が不定であると判定されると、前記直列に接続されたノードを走査し、前記複数のルールのいずれかのルールの右辺に並ぶ論理式のうち真となる論理式を算出することを含む推論方法を提供する。
【００１０】
また、本発明の一実施形態として、述語記号に対応し所定の順序で並べられた複数の列と前記複数の列のいずれかの位置に配置されるセルを含む行とにより構成される表であり各セルにはそのセルの位置する列に対応する述語記号に適用することにより論理式を形成する値が格納されている表、に対応付けられるグラフデータ構造を有するルールベースであり、メモリ空間に配置されるルートノードと、前記表の各行における複数のセルの並びに対応して前記メモリ空間に前記列の順序にてポインタにより直列に接続される複数のノードの各並びと、を有し、前記複数のノードの各並びの端のノードをポインタにより前記ルートノードに接続し、前記ルートノードから前記ノードを、ポインタをたどって順に読み出し走査可能とし、前記表の各行は、複数の論理式を論理積として右辺に並べ他の論理式を右辺に並べたルールを表すことを特徴とする、グラフデータ構造により記憶されるルールベースを参照するコンピュータが実行する推論方法であり、複数の入力領域に入力された情報であり前記論理式の真偽を判定するための情報を取得しメモリに記憶し、前記取得された情報により、前記ルールいずれかの右辺の論理式が真と判定されると、前記真と判定された論理式が右辺に並ぶルールの左辺に並ぶ論理積の複数の論理式を表すノードを走査して前記真と判定された論理式が右辺に並ぶルールが成り立つために真と判定されるべき論理式を算出し、前記取得された情報により、前記ルールの全ての右辺の論理式の真偽が不定であると判定されると、前記直列に接続されたノードを走査し、前記複数のルールのいずれかのルールの右辺に並ぶ論理式のうち真となる論理式を算出することを含む推論方法を提供する。
【００１１】
また、本発明の一実施形態として、述語記号に対応し所定の順序で並べられた複数の列と前記複数の列のいずれかの位置に配置されるセルを含む行とにより構成される表であり各セルにはそのセルの位置する列に対応する述語記号に適用する値が格納されている表、に対応付けられるグラフデータ構造を有するルールベースであり、メモリ空間に配置されるルートノードと、前記表の各行における複数のセルの並びに対応して前記メモリ空間に前記列の順序にてポインタにより直列に接続される複数のノードの各並びと、を有し、前記複数のノードの各並びの端のノードをポインタにより前記ルートノードに接続し、計算機に前記ルートノードから前記ノードを、ポインタをたどって順に読み出し可能とすることを特徴とする、グラフデータ構造を有するルールベースを提供する。
【発明の効果】
【００１２】
本発明の一実施形態によれば、与えられた条件から結論を導くこと及び期待される結論を得るための条件を得ることを行なえる推論装置が提供できる。また、ルールベースにおけるルールの表現において、共通するノードを統合（マージ）することにより、ルールベースに必要な記憶領域を削減し、また、推論を効率的に行なうことができる。
【図面の簡単な説明】
【００１３】
【図１】本発明の一実施形態に係る推論装置を含むシステムの機能ブロック図
【図２】本発明の一実施形態におけるルールの一例図
【図３】本発明の一実施形態におけるルールの解釈のための表の一例図
【図４】本発明の一実施形態におけるルールの解釈のための具体的な表の一例図
【図５】本発明の一実施形態に係る推論装置のルールベースに記憶されるデータ構造の模式図
【図６】本発明の一実施形態に係る推論装置のルールベースに記憶されるデータ構造の模式図
【図７】本発明の一実施形態に係る推論装置での表示の一例図
【図８】本発明の一実施形態に係る推論装置にて用いられるスタックの模式図
【図９】本発明の一実施形態に係る推論装置での前向き推論の処理のフローチャート
【図１０】本発明の一実施形態におけるルールの解釈のための表の一例図
【図１１】本発明の一実施形態に係る推論装置のルールベースに記憶されるデータ構造の模式図
【図１２】本発明の一実施形態におけるルールの解釈のための表の一例図
【図１３】本発明の一実施形態に係る推論装置のルールベースに記憶されるデータ構造の模式図
【図１４】本発明の一実施形態に係る推論装置での後ろ向き推論の処理のフローチャート
【発明を実施するための形態】
【００１４】
以下、本発明を実施するための形態を以下に説明する。なお本発明は以下の説明に限定されることはなく、種々に変形して実施することができる。
【００１５】
（構成）
図１は、本発明の一実施形態に係る推論システムの機能ブロック図を示す。推論システム１００は、推論装置１０１と、入力装置１０２と、出力装置１０３とを備える。入力装置１０２は、ユーザの操作の結果や他の装置の動作の結果として生成されるデータを推論装置１０１に入力し、出力装置１０３は、推論装置１０１による推論の結果を受信しディスプレイに表示などをして出力する。
【００１６】
このような推論システムの例としては次のようなものがある。入力装置１０２のディスプレイには、電子的な申請を行なうためのフォームが表示され、ユーザがそのフォームに入力を行ない、入力の結果を推論装置１０１に送信する。推論装置１０１は、フォームへの入力が正しいかどうかを推論し、その推論の結果を出力装置１０３に送信し、出力装置１０３が推論の結果を表示する。
【００１７】
なお、本発明の一実施形態においては、入力装置１０２と出力装置１０３とは別個の装置となっている必要はなく、同一の装置が、入力装置１０２の機能と出力装置１０３の機能とを有していてもよい。例えば、入力装置１０２のディスプレイに表示されるウィンドウの一部が出力装置１０３に対応していてもよい。
【００１８】
なお、電子的な申請には、確定申告などの電子申請、インターネットを用いる特許出願など、大学の履修科目の電子提出などがある。
【００１９】
特に、本実施形態に係る推論システムの推論装置１０１は、後に説明するように後ろ向き推論も行なうことができる。このため、例えば大学の履修科目の提出においては、入力装置１０２から推論装置１０１に、学生の既に履修した科目と単位数の情報を入力し、大学の卒業要件を表す規則を格納したルールベースを有する推論装置１０１が卒業要件を満たすためには、今後どの科目を履修すればよいのかを推論し、その結果を出力装置１０３に出力するようにすることもできる。
【００２０】
また、銀行の窓口業務においては、来店者から様々な要望が提示される場合が多い。例えば、紛失した預金通帳の再発行を依頼したい、届出印の変更を依頼したいなどの要望が提示される。そこで、入力装置１０２から入力された顧客の要望と、顧客の取引状況、顧客が現時点において提示できる身分確認書類などの情報から、銀行の規則を格納したルールベースを有する推論装置１０１が、顧客の要望がかなえられるか、もしかなえられない場合には、要望をかなえるために何を行なえばよいかを推論し、出力装置１０３に出力することもできる。
【００２１】
また、入力装置１０２と出力装置１０３とにより、電子化された申請書などを規則にしたがって配信するワークフローシステムを構成し、申請書などの配信先を決定するために、ワークフローシステムから申請書などの内容が推論装置１０１に送信され、ワークフローの規則を格納したルールベースを有する推論装置１０１による推論の結果得られる配信先などの情報がワークフローシステムに送信されるようになっていてもよい。
【００２２】
このような構成により、規則とプログラム処理のロジックとを分離することができ、規則が変更になってもその変更は推論装置の有するルールベースの記憶内容の変更となるが、システム全体に改修などの変更が波及することを防止することができる。
【００２３】
以下、推論装置１０１の構成について説明する。推論装置１０１は、ルールベース１１０と、次ノード取得部１１１と、真偽判定部１１２と、情報取得部１１３と、推論部１１４とを有する。
【００２４】
ルールベース１１０は、１または複数の規則（ルール）を表すデータ構造を記憶する。ルールベース１１０は、記憶装置を有し、記憶装置にデータ構造が記憶される。ルールは、「Ｆ１^Ｆ２^…^Ｆｎ⊃Ｇ」のようなプロダクションルールの形式により表現がされる。すなわち「⊃」の左辺に、１又は「^」により結合された複数の論理式「Ｆ１」−「Ｆｎ」の論理式が並び、「⊃」の右辺に論理式「Ｇ」が並ぶルールが用いられる。このようなルールは、「⊃」の左辺に配置された論理式「Ｆ１」−「Ｆｎ」の全てが真であれば、「⊃」の右辺に配置された論理式「Ｇ」が真となることを意味する。また、別の側面においては、「⊃」の右辺に配置された論理式「Ｇ」が真となるには、「⊃」の左辺に配置された論理式「Ｆ１」−「Ｆｎ」の全てが真となることが必要であることを意味する。
【００２５】
論理式は、原子式であってもよい。例えば、「ｘ＝ｖ」のような変数ｘの値が定数ｖであることを表す等式の原子式や「ｘ≦ｖ」や「ｘ≧ｖ」などの不等式の原子式であってもよい。また、「パスポートを持っている」を表す「Ｈａｖｅ（パスポート）」のように「パスポート」という定数が含まれ、「パスポート」に「Ｈａｖｅ」という述語記号を適用した形式であってもよい。「ｘ＝ｖ」という等式や「ｘ≦ｖ」や「ｘ≧ｖ」などの不等式においては、一般には、「＝」、「≦」および「≧」などが述語記号であると考えることもできるが、本実施形態においては、変数を含む等式および不等式においては、変数名を述語記号とみなして扱う場合がある。
【００２６】
また、「Ａ⊃Ｂ」および「Ａ⊃Ｃ」のように、「⊃」の左辺が同じであるが右辺が異なるルールが複数ある場合これらのルールをまとめて例えば「Ａ⊃Ｂ＾Ｃ」のように、「⊃」の左辺が「＾」により結合された論理式となっていてもよい。
【００２７】
図２は、ｍ個のルールの例を示す。図２において、「Ａ１」、「Ａ２」、…、「Ａｎ」、「Ｂ」は、述語記号を表し、「ａ１１」、「ａ１２」、…、「ａ１ｎ」、「ａ２１」、「ａ２２」、…、「ａ２ｎ」、「ａｍ１」、「ａｍ２」、…、「ａｍｎ」、「ｂ１」、「ｂ２」、…、「ｂｍ」は述語記号に適用される定数を表す。定数が述語記号に適用されることにより、論理式が形成される。ここに「ａ１１」などの表す定数は、単一の値により構成されるスカラー値に限定されず、複数の値により構成されていてもよい。例えばベクトル値となっていてもよい。また、「ａ１１」、「ａ１２」、…、「ａ１ｎ」、「ａ２１」、「ａ２２」、…、「ａ２ｎ」、「ａｍ１」、「ａｍ２」、…、「ａｍｎ」、「ｂ１」、「ｂ２」、…、「ｂｍ」の中には同じ定数が複数回現れてもよい。
【００２８】
なお、より一般的には、「⊃」の左辺に並ぶ述語記号の順序はルール毎に異なっていてもよい。このように、「⊃」の左辺に並ぶ述語の順序がルール毎に異なっている場合には、述語を並び換えて全てのルールにおいて同じ順序で述語記号が並ぶようにしてもよい。また、それぞれのルールの左辺に並ぶ述語記号の全体は、ルールごとに異なっていてもよい。この場合には、全ての述語に対して、特殊な定数−例えば「＊」−を適用すると真であるとみなす。そして、あるルールＲ１の「⊃」の左辺には述語記号「Ｐ」が無く、他のルールＲ２の「⊃」の左辺には述語記号「Ｐ」が現れる場合には、Ｒ１の左辺に「Ｐ（＊）」を加える操作を行なうことにより、「⊃」の左辺に並ぶ述語記号を、全てのルールにおいて、同じとすることができる。
【００２９】
図３は、図２に示すルールの集まりの解釈のための表の一例を示す。図２におけるルールに現れる述語記号「Ａ１」、「Ａ２」、…、「Ａｎ」、「Ｂ」は、図３に示す表における列の名前に対応している。列は、「Ａ１」、「Ａ２」、…、「Ａｎ」、「Ｂ」の順序で並べられている。そして、図３の表において、１行目は、例えば、列Ａ１の値がａ１１であり、かつ、列Ａ２の値がａ１２であり、かつ、…、かつ、列Ａｎの値がａ１ｎであれば、列Ｂの値はｂ１となることを表すセルを有する。そこで、例えば、表の各セルを、列の名前に対応する変数の値がセルに格納されている値に等しいことを表していると解釈する。また、一行の最も右に位置するセルはルールの「⊃」の右辺に対応させ、その他のセルは「⊃」の左辺に対応させ、「⊃」の左辺に対応するセルは、「＾」により結合されていると解釈する。
【００３０】
したがって、図３において、表の一行目は、「Ａ１（ａ１１）＾Ａ２（ａ１２）＾…＾Ａｎ（ａ１ｎ）⊃Ｂ（ｂ１）」というルールに対応している。他の行についても同様である。このような表を用いることにより、ルールを表の形式により人間にとって分かりやすく表現することができる。また、各ルールにおいて述語記号の並び方が同じであるので、このような表の形式によりルールの集まりを表現できることになる。
【００３１】
また、セルに格納される値の表現を拡張し、各セルに不等号と値とを格納することにより、列に対応する変数の値とセルに格納されている値との大小関係を示す不等式を表しているとすることもできる。例えば、Ａｎの列のセルに「＞１」が、例えば文字列により、格納されていれば、そのセルは「Ａｎ＞１」という不等式を表しているとすることもできる。さらに、例えば「＞１＆＜１０」が格納されていれば、「Ａｎ＞１」かつ「Ａｎ＜１０」という不等式を表しているとすることもできる。
【００３２】
図４は、図３に示す表の具体例を示す。図４の表は、企業などの組織における稟議書の要否を表している。即ち、稟議書の対象の種類を表す稟議種類と、申請者の役職と、稟議書の対象の金額と、稟議書要否との関係を示している。例えば、図４に示す表の１行目は、「物品購入」、「アシスタント」、「＊」および「必要」という定数を格納するセルがこの順に並んでいるので、「稟議種類が物品購入であり、かつ、役職がアシスタントであれば、稟議書は必要である」というルールを表す。すなわち、「稟議書＝物品購入＾役職＝アシスタント⊃稟議書要否＝必要」というルールを表す。なお、「＊」は上述したような特殊な値であり、「金額＝＊」は真であるとみなすことにすれば、「稟議書＝物品購入＾役職＝アシスタント＾金額＝＊⊃稟議書要否＝必要」というルールを表していると解釈することができる。また、図４に示す表の２行目は、「稟議種類＝物品購入^役職＝マネージャ^金額≦１０００ドル⊃稟議書要否＝不要」というルールを表している。したがって、各行は、左辺に現れる変数が「稟議種類」、「役職」および「金額」の３つであり、右辺に現れる変数が「稟議書要否」であるルールを表していることとなり、ルール間で、現れる変数を同じにすることができる。
【００３３】
なお、表計算ソフトウェアを用いれば、表の取扱を容易とすることができる。このため、表計算ソフトウェアを用いて表を作成することによりルールの作成を容易に行なうことができる。また、表計算ソフトウェアの一部には、表を表すデータを格納する際には、ＸＭＬ（ｅＸｔｅｎｓｉｂｌｅ  Ｍａｒｋ−ｕｐ  Ｌａｎｇｕａｇｅ）により表現されるデータとして格納する。このように表を表すデータがＸＭＬを用いて表現される場合には、表のデータは表計算ソフトウェアのみならず、広い範囲に属するソフトウェアにより処理することが可能である。したがって、ルールの集合を表計算ソフトウェアにより作成し、作成したルールを、ＸＭＬを用いた表現に変換することができる。変換されたＸＭＬを用いた表現は、推論装置１０１などにより読み込まれ、ルールベースに記憶されるデータ構造を生成することができる。また、ＸＭＬを用いた表現を、後に説明するようなセルのマージ、列の並び換えの処理を行なってから、ルールベースに記憶されるデータ構造を生成してもよい。
【００３４】
図５は、図２に示されるルールを表すデータ構造を示す模式図である。したがって、図５に示す模式図は、図３に示す表に対応するデータ構造を示す。なお、ルールベース１１０に、このようなデータ構造がメモリなどに記憶されることにより、ルールが記憶される。図５に示す模式図で表されるデータ構造がルールベース１１０に記憶される。
【００３５】
ルールを表すデータ構造は、ルートノード５０１を含む。ルートノード５０１は、全てのルールに対して共通して存在する。また、ルートノード５０１は、各ルールの「⊃」の左辺の一番左端の論理式を表現するノードにエッジにより接続される。また、ルートノード５０１は、各ルールの「⊃」の右辺の論理式を表現するノードにエッジにより接続される。
【００３６】
各ルールは、「⊃」の左辺の論理式を表現するノードと「⊃」の右辺の論理式を表現するノードとをエッジにより直列に接続したデータ構造により表すことができる。また、ノードの順序は、例えば表３の列の並びの順序に対応している。このような直列に接続されたノードの両端のノードがルートノード５０１に接続される。例えば、図２に示されるルールのうち、「Ａ１（ａ１１）^Ａ２（ａ１２）^…^Ａｎ（ａ１ｎ）⊃Ｂ（ｂ１）」は、「Ａ１（ａ１１）」を表現するするノード５０２と「Ａ２（ａ１２）」を表現するノード５０５と…「Ａｎ（ａ１ｎ）」を表現するノード５０６と「Ｂ（ｂ１）」を表現するノード５０７をエッジにより直列に接続されたデータ構造により表すことができる。他のルールについても同様である。
【００３７】
そして、各ルールの「⊃」の最も左に位置する論理式を表現するノード５０２、５０３、…、５０４がルートノード５０１にエッジにより接続され、⊃の右辺の論理式を表現するノード５０７、５０８、…、５０９がルートノード５０１にエッジにより接続される。
【００３８】
すなわち、ルールベース１１０に記憶されるデータ構造は、それぞれルールに並ぶ論理式を表すノードを直列に接続して各ルールに対応するノードの列を形成し、各列の両端のノードをルートノードに接続したグラフデータ構造となっている。また、一つのエッジの両端のノードは、直接に接続されていると記載する場合がある。
【００３９】
なお、本実施形態においては、ノードを接続するエッジは方向を有すると考えることもできる。すなわち、ノードとエッジにより有向グラフが形成されると考えることもできる。エッジが方向を有する理由の一つは、「⊃」の左辺の論理式が真であれば右辺の論理式が真となるという「⊃」の方向性に対応させるためである。そこで、図５において、エッジの始点を表すために「＋」の記号が用いられ、エッジの終点を表すために「−」の記号が付されている。これにより、例えばノード５０２、５０５、…５０６、５０７のどれが「⊃」の右辺の論理式を表現するノードであり、したがって、どれが「⊃」の左辺の論理式を表現するノードであるかを判別することができる。すなわち、ルートノードを終点とするエッジの始点のノードが、「⊃」の右辺の論理式を表現するノードであり、その他のノード（ルートノードを除く）が「⊃」の左辺の論理式を表現するノードである。
【００４０】
本実施形態においては、各ルールの「⊃」の左辺の論理式を表現する任意のノードを終点とするエッジは１本である。この性質により、本発明の一実施形態においては、期待される結論を得るための後ろ向き推論を効率良く行なえる。また、全てのルールにおいて同じ順序で述語記号が並ぶ順序が同じであるので、ルートノードから距離が同じノードが表現する論理式の述語記号は同一となる。これにより、ルールの集まりを表として表現することが可能となる。ここに、あるノードから別のノードへの距離とは、あるノードと別のノードとの間のエッジの数をいう。例えば、ルートノード５０１からノード５０２の距離は１であり、ルートノード５０１からノード５０５の距離は２となる。
【００４１】
また、ルートノード５０１を一つ用意する代わりに、次のようにしてもよい。すなわち、「⊃」の左辺のうち最も左の論理式を表現するノードに接続する第１のノードと、「⊃」の右辺の論理式を表現するノードに接続する第２のノードとを用意してもよい。すなわち、各列の左端のノードに直接接続される第１のノードと、各列の右端のノードに直接接続される第２のノードとを用意してもよい。以下では、ルートノード５０１を一つ用意する場合について説明するが、第１のノードと第２のノードとを用意する場合についても容易に理解される。
【００４２】
図６（ａ）は、図５に示すデータ構造において、ルートノード５０１を始点または終点とするエッジを表すデータ構造の模式図である。図６（ａ）において、「＋」の右側には、始点がルートノード５０１となるエッジの終点のノードを示す情報が格納され、「−」の右側には、終点がルートノード５０１となるエッジの始点のノードを示す情報が格納されている。ノードを示す情報としては、例えばノードに対応するデータ構造が記憶されているアドレスを指し示すポインタを用いることができる。このように図６（ａ）に示される模式図に相当する情報がルールベース１１０の記憶装置のメモリ空間に格納される。
【００４３】
図６（ｂ）は、図５に示すデータ構造において論理式「Ａｉ（ａｊｋ）」を表現するノードを始点または終点とするエッジを表すデータ構造の模式図である。図６（ｂ）において、「＋」の右側には、論理式「Ａｉ（ａｊｋ）」を表現するノードが始点となるエッジの終点ノードを示す情報が格納され、「−」の右側には、論理式「Ａｉ（ａｊｋ）」を表現するノードが終点となるエッジの始点のノードを示す情報が格納される。
【００４４】
次ノード取得部１１１は、ノードが指定された場合に、指定されたノードにエッジにより接続されている他のノードをルールベース１１０から取得する。本実施形態では、エッジは方向を有するので、次ノード取得部１１１は、２つのモードを有する。１つのモードでは、指定されたノードを始点とするエッジの終点となっているノードを取得し、別のモードでは、指定されたノードを終点とするエッジの始点となっているノードを取得する。なお、ノードは、例えばルールベース１１０において記憶されているアドレスで指定される。
【００４５】
なお、指定されたノードがルートノードである場合には、ルートノードとエッジにより接続されているノードは、複数となる。このため、次ノード取得部１１１は、複数のノードを取得する場合がある。したがって、指定されたノードが、ルートノード５０１であり、モードが、指定されたノードを始点とするエッジの終点となっているノードを取得するモードとなっている場合には、次ノード取得部１１１は、ノード５０２、ノード５０３、…、ノード５０４を取得する。
【００４６】
情報取得部１１３は、入力装置１０２により入力された情報を、入力装置１０２より取得する。図７は、入力装置１０２の有するディスプレイなどに表示される情報の入力画面の一例を示す。図７においては、ディスプレイにウィンドウ７０１が表示され、ウィンドウ７０１に、テキストエリアなどの入力領域７０２、７０３、７０４が表示される。それぞれの入力領域の左側には、「稟議種類」、「役職」、「金額」、「稟議書要否」の文字列が表示されている。これにより、例えば、テキストエリア７０２には、稟議種類の定数に対応する値を入力することが示される。図７においては、稟議種類の値として出張、役職の値としてアシスタント、金額の値として５１６ドルが入力されている。稟議書種類の値は入力されていない。これは、稟議種類、役職および金額の値から稟議書要否を判断することを推論装置１０１に要求することを意味する。すなわち、この場合には、前向き推論が行なわれる。
【００４７】
なお、テキストエリアを用いてテキストが入力されるかわりに、プルダウンメニューなどを用いて選択された値が入力されるようになっていてもよい。
【００４８】
本発明の一実施形態においては、一般的に、「⊃」の右辺の論理式についての値が入力されていない場合には、前向き推論が行なわれる。また、「⊃」の右辺の論理式についての値が入力されている場合には、後ろ向き推論が行なわれる。
【００４９】
情報取得部１１３は、入力装置１０２による入力された値を表す情報を入力装置１０２より取得した後、その情報を推論装置１０１のメモリなどの記憶装置に格納する。例えば、稟議種類に対応して指定されたメモリアドレスなどに「出張」を表す定数記号を記憶する。
【００５０】
真偽判定部１１２は、ノードが指定された場合に、指定されたノードに対応する論理式の真偽を判定する。論理式の真偽の判定には、情報取得部１１３により推論装置１０１のメモリなどの記憶装置に記憶された情報が参照される。例えば、指定されたノードが「稟議種類＝出張」に対応する場合、推論装置１０１のメモリなどの記憶装置における稟議種類に対応するメモリアドレスなどに「出張」を表す情報が記憶されていれば、真であると判定し、「物品購入」を表す情報が記憶されていれば、偽であると判定する。また、推論装置１０１のメモリなどの記憶装置における稟議種類に対応するメモリアドレスなどに情報が記憶されていなければ、真偽が判定できないことを示す不定であることを判定してもよい。
【００５１】
推論部１１４は、情報取得部１１３により推論装置１０１のメモリなどの記憶装置に記憶された情報およびルールベース１１０に記憶されているルールを表すデータ構造を参照して推論を行なう。また、推論の結果を出力装置１０３に出力する。例えば、図７に示す入力が行なわれた場合には、推論部１１４は「稟議書要否＝必要」を推論する。そこで、テキストエリア７０５に稟議書が必要であることを示す値を表示するための結果を出力装置１０３に送信する。
【００５２】
（前向き推論）
推論部１１４が推論を行なう際の処理の一例について以下説明する。ここでは、与えられた条件から結論を導く推論、すなわち前向き推論、について説明する。以下の説明では、スタックを用い、いわゆる「深さ優先」（ｄｅｐｔｈ  ｆｉｒｓｔ）の探索で推論を行なう処理の一例を説明する。スタックとは、ノード（あるいはノードへのポインタなどのノードを表す情報）を後入れ先出し（Ｌａｓｔ  Ｉｎ  Ｆｉｒｓｔ  Ｏｕｔ）で記憶する構造である。図８にスタックの一例を示す。図８においては、スタック８００の下から順に１番目のスロット８０１、２番目のスロット８０２、…、ｎ番目のスロット８０３がある。スロット８０１、８０２、８０３には、それぞれ、論理式「Ａｃ（ａｄｅ）」、「Ａｇ（ａｋｉ）」、「Ａｊ（ａｌｍ）」を表現するノードの情報（例えばノードのアドレス）が格納されている。この状態で新たにノードの情報をスタックに入れると、その情報は、ｎ＋１番目のスロットに記憶される。すなわち、一番上のスロットが用意され、一番上のスロットにノードの情報が記憶される。このように、一番上のスロットが用意される意味において、新たにノードの情報をスタックに入れることを、ノードをスタックに積む、あるいはノードをプッシュするという。
【００５３】
また、図８に示す状態でスタックからノードを表す情報を取り出すと、一番上のスロット８０３に格納されているノードである「Ａｊ（ａｋｌ）」を表現するノードの情報が得られる。また、次の一番上のスロットは、スロット８０３の直下のスロットとなる。そこで、このようにスタックからノードの情報を取り出すことを、スタックをポップするという。また、スタックにおいて一番下のスロット８０１にのみノードの情報が格納されている状態でスタックをポップすると、スタックは空の状態となる。
【００５４】
図９は、推論部１１４が前向き推論を行なう際の処理を説明するフローチャートを示す。このフローチャートの処理を行なう前には、スタックは空の状態となっているとする。また、次ノード取得部１１１は、指定されたノードを始点とするエッジの終点となっているノードを取得するモードとなる。
【００５５】
図９に示すフローチャートの処理は、例えば、入力装置１０２から推論の実行の命令を表す情報が情報取得部１１３に取得されたときなどに、行なわれる。前向き推論を行なうかどうかは、「⊃」の右辺の論理式の真偽値が不定であるかどうかにより、判断することができる。例えば、図７において、テキストエリア７０５に値が入力されていない場合には、「稟議要否＝必要」および「稟議要否＝不要」それぞれの真偽値は不定となるので、前向き推論を行なうことができる。
【００５６】
ステップＳ９０１の処理においては、ルートノードをプッシュする。これにより、ルートノードがスタックの一番上のスロットに格納される。
【００５７】
ステップＳ９０２の処理において、スタックが空であるかどうかを判断する。スタックが空であれば、推論が終了したことになる。そこで、推論の終了を示す情報を出力装置１０３に送信したり、推論の結果を出力装置１０３に送信したりする。
【００５８】
ステップＳ９０２の処理において、スタックが空でなければ、ステップＳ９０３へ処理を移行させて、スタックをポップする。これによりノードの情報が得られる。
【００５９】
ステップ９０４の処理において、ステップＳ９０３で得られた情報のノードが、「⊃」の右辺の論理式を表現するノードであるかどうかを判断する。「⊃」の右辺の論理式を表現するノードであるかどうかどうかは、例えば、そのノードを始点とするエッジの終点がルートノードであるかどうかにより判断することができる。なお、以下では、「⊃」の右辺の論理式を表すノードを「結論のノード」ということがある。
【００６０】
ステップ９０４の処理において、ステップＳ９０３で得られたノードが結論のノードでないと判断されると、ステップＳ９０５へ処理を移行させる。ステップＳ９０５の処理において、ステップＳ９０３で得られたノードが表す論理式の真偽値が真であるかどうかを真偽判定部１１２により判定する。もし、真偽判定部１１２による真偽値の判定の結果が真であれば、ステップＳ９０６へ処理を移行させ、偽であれば、ステップＳ９０２に戻る。
【００６１】
なお、真偽判定部１１２による真偽値の判定の結果が不定である場合には、ステップＳ９０３で得られたノードが表す論理式などを出力装置１０３に出力してもよい。例えば、「役職＝マネージャ」の真偽を判定した結果、不定であった場合には、「役職＝マネージャ」を出力装置１０３に送信してもよい。これにより、出力装置１０３は、「役職はマネージャですか？」や「役職を入力して下さい」などの表示を行なうことができる。これにより、入力装置１０２のユーザに未入力の項目があることや、未入力の項目の入力を促すことができる。入力を促した結果、入力装置１０２より情報が情報取得部１１３に取得された場合には、再度ステップＳ９０３で得られたノードの真偽を判定して、真偽値に応じてステップＳ９０６またはステップＳ９０２に処理を移行させてもよい。
【００６２】
また、ステップＳ９０３で得られたノードが表す論理式の真偽値の判定をステップＳ９０５において行なった結果が偽である場合には、ステップＳ９０３で得られたノードが表す論理式を記憶しておき、ステップＳ９０２に処理を移行させるのではなく、ステップＳ９０６へ処理を移行させてもよい。この後、ステップＳ９０８に処理が移行した場合には、記憶された論理式を出力装置１０３へ出力し、出力装置１０３は、実際には偽であった論理式が真であると仮定すると、どのような結論が得られるかを出力するようにしてもよい。
【００６３】
ステップＳ９０６の処理において、ステップＳ９０３で得られたノードの次のノードを次ノード取得部１１１により取得する。そして、ステップＳ９０７の処理において、ステップＳ９０６の処理により取得されたノードをプッシュし、ステップＳ９０２に戻る。もし、複数のノードが次ノード取得部１１１により取得された場合には、その複数のノードをプッシュする。
【００６４】
また、ステップ９０４の処理において、ステップＳ９０３で得られたノードが結論のノードであると判断されると、ステップＳ９０８へ処理を移行させる。ステップＳ０８の処理において、結論の結果を得る。結論の結果を得るとは、結論のノードが表す論理式を得ることである。また、さらに得られた論理式に含まれる値を得てもよい。例えば、「稟議書要否＝必要」という論理式が得られた場合には、必要を表す値を得てもよい。得られた値は、出力装置１０３に出力されてもよい。「稟議書要否＝必要」という論理式を表す情報が出力装置１０３に送信された場合には、「＝」を「を判断した結果、」という定型的な文字列に置換し、さらに別の定型的な文字列「となります」を補い、「稟議書要否を判断した結果、必要となります」などというメッセージを表示してもよい。
【００６５】
図９を用いて、深さ優先の探索で推論を行なう処理について説明したが、幅優先（ｂｒｅａｄｔｈ  ｆｉｒｓｔ）の探索で推論を行なうこともできる。この場合には、それぞれのルールに対応する作業領域をメモリなどに用意し、それぞれのルールの「⊃」の左辺の論理式を表現するノードを順に走査し、それぞれの作業領域に、その作業領域に対応するルールに、真偽判定部１１２により偽と判断された論理式があるかどうかを記録する。もし、偽と判断された論理式があると作業領域に記録された場合には、その作業領域に対応するルールについては走査を中止し、結論のノードに到達した場合に、そのノードに関する情報を出力装置１０３に送信する。本実施形態では、ルートノードから距離が同じノードが表現する論理式の述語記号は同一となるので、真偽の判定を複数のノードについて同時に行なうことができる。例えば、図５において、述語記号Ａ１について、Ａ１（ａ１１）、Ａ１（ａ２１）、…、Ａ１（ａｍ１）の真偽の判定をまとめて行なうことができる。次に、Ａ１（ａ１１）、Ａ１（ａ２１）、…、Ａ１（ａｍ１）の中の偽でないと判定された論理式を表すノードを有するルールの述語記号Ａ２についての真偽の判定をまとめて行なう。
【００６６】
以下においては、ルールベースに記憶するノード数を減少させる方法、また、推論を効率的に行なうためのデータ構造について説明する。
【００６７】
（セルまたはノードのマージ）
図３および図４に示すように、列の数と行の数との積の値の個数のセルにより構成される表の各行のセルを、１つのルールに対応付け、ルールベースに記憶するデータ構造を構成すると、列の数と行の数との積の値の個数のノードおよびルートノードが得られる。しかし、一般的には表のセルに格納される異なる値の数は、列の数と行の数との積の数よりも小さいことがある。例えば、図４に示す表は４列１０行からなるが、セルに格納される異なる値は、「物品購入」、「出張」、「一般」、「アシスタント」、「マネージャ」、「＊」、「１０００ドル以下」、「１０００ドル超」、「１００ドル以下」、「１００ドル超」、「５００ドル以下」、「５００ドル超」、「７００ドル以下」、「７００ドル超」、「必要」、「不要」の１６個である。
【００６８】
特に、図４に示す表において、列の中の最も左の列である稟議種類の列のセルに格納される異なる値は３個であり、行数の１０よりも小さい。このため、図４に示す表の各行を、１つのルールに対応付け、ルールベースに記憶するデータ構造を図５のように構成した場合において、ルートノード５０１から同じ距離にあるノード５０２、ノード５０３、…、ノード５０４の中に同じ論理式を表現するノードが存在することになる。このため、図９のステップＳ９０６において同じ論理式を表現するノードが複数回取得され、ステップＳ９０５において、同じ論理式の真偽値の判定が行なわれることとなる。
【００６９】
そこで、表の行の全てをそれぞれ列の値によりソート（並び換え）を行ない、左の列から同じ値のセルをマージすることを行なってもよい。例えば、図４に示す表においては表の行の全てをそれぞれ列の値によりソート（並び換え）がされており、１行目から３行目までにおいて、稟議種類の列の値は「物品購入」であり同じである。そこで、１行目から３行目までにおいて稟議種類の列セルをマージすること（統合して１つのセルにすること）ができる。次に、１行目から３行目までにおいて、役職の列の値を見ると、１行目は「アシスタント」であり、２行目と３行目とは「マネージャ」であり、２行目と３行目との「マネージャ」のセルをマージすることができる。以上のようなセルのマージの操作を他の行についても行なった結果が図１０である。図１０に示すように、セルのマージの処理を行なうと、任意のセルの右隣のセルの数は、１または２以上となる。
【００７０】
このようにセルのマージの処理をした表より、ルールベースに記憶するデータ構造を生成するには、次の手続により行なう。まず、列を左から右に走査しながら、各列において、その列のセルそれぞれに対応させてノードを生成する。次に、それぞれのノードについて、ノードに対応するセルの右隣のセルに対応するノードをエッジにより接続する。最後に、ルートノードと、最も左の列のセルに対応するノード及び最も右の列のセルに対応するノードとをエッジによりルートノードに接続する。なお、最も右の列については、列に格納されている異なる値に対応させたノードを生成するものとする。最も右の列のセルに対応するノードは、そのセルの値に対応させたノードとする。
【００７１】
図１１は、上記の手続により図１０に示す表から生成されたデータ構造を示す。ノード１１０２が稟議種類の列の「物品購入」が格納されているセルに対応している。ノード１１０５は、ノード１１０２に対応するセルの右隣の「アシスタント」が格納されているセルに対応し、ノード１１０６は、ノード１１０２に対応するセルの右隣の「マネージャ」が格納されているセルに対応する。ノード１１１１は、ノード１１０５に対応するセルの右隣の「＊」が格納されているセルに対応し、ノード１１１２は、ノード１１０６に対応するセルの右隣の「１０００ドル以下」が格納されているセルに対応し、ノード１１１３は、ノード１１０６に対応するセルの右隣の「１０００ドル超」が格納されているセルに対応する。他のセル１１０３−１１２０についても同様に説明することができる。
【００７２】
また、ノード１１２１は、稟議書要否の列に格納されている「必要」のセルに対応するノードであり、ノード１１２２は、稟議書要否の列に格納されている「不要」のセルに対応するノードである。したがって、複数のルールそれぞれの右辺に並ぶ論理式の中に同じ論理式があれば、ルールベース１１０に記憶されるグラフデータ構造においては、ノードがマージされるようになっていてもよい。
【００７３】
以上においては、セルのマージを行なった表からデータ構造を生成する手続について述べた。一方、セルのマージを行なう前の表からデータ構造を生成し、ノードをルートノードからマージして同じデータ構造を得ることもできる。この手続をＭｅｒｇｅ（ルートノード）と名付けるとすると、Ｍｅｒｇｅ（Ｎ）とは、（１）Ｎを始点とするエッジの終点のノードがルートノードであれば、ルートノードを終点とするノードの始点のノードについて、同じ論理式に対応するノードをマージして手続を終了し、（２）Ｎを始点とするエッジの終点のノードについて、同じ論理式に対応するノードをマージし、マージして得られたそれぞれのノードＭについてＭｅｒｇｅ（Ｍ）を行なう。
【００７４】
なお、セルまたはノードのマージを行なっても、ルートノードから距離が同じノードが表現する論理式の述語記号は同一である。また、各ルールの「⊃」の左辺の論理式を表現する任意のノードを終点とするエッジは１本である。
【００７５】
（表の列の並び換え）
セルまたはノードのマージを行なう前に、表の列の並び換えを行なってもよい。図１２は、図４に示す表の列の交換を行ない、セルのマージを行なって得られる表を示す。すなわち、図１０に示す表の列のうち、役職を最も左の列とし、その右隣を稟議種類の列とする列の並び換えの手続を行なって得られる表である。このような列の並び換えを行なったのは、稟議種類の列に格納される異なる値が「物品購入」、「出張」および「一般」であり個数が３であるのに対し、役職の列に格納される異なる値が「アシスタント」および「マネージャ」であり個数が２であるので、個数が少ない役職の列を稟議種類の列よりも優先した結果である。また、金額の列に格納される異なる値の個数は９であるので、役職および稟議種類の列が金額の列よりも優先される。なお、稟議書要否は、もっとも右側の列であり、結論に対応する列なので並び換えない。
【００７６】
すなわち、表の列の並び換えは、それぞれの列に格納されている異なる値の個数を求め、個数の少ない列を優先して左に位置するように行なうこととなる。これは、複数のルールに並ぶ論理式の述語記号を順に左から右に並ぶ列名とし、各行を各ルールに対応付けて対応する列に各ルールに並ぶ論理式が有する定数を並べた表を作成した場合、最も右に並ぶ列を除き、各列に格納される値の種類の数は、その右隣の列の値の種類の数以下となると言い換えることができる。
【００７７】
図１３は、図１２に示す表から生成されるデータ構造を示す。そのデータ構造は、符号１３０１−１３２１で示されるように、２１個のノードにより構成されている。一方、列の並び換えを行なっていない図１０からは、図１１に示されるように符号１１０１から１１２２に示される２２個のノードにより構成されるデータ構造が得られ、表の列の並び換えを行なうことにより、ノードの数を減少させることができる。
【００７８】
（後ろ向き推論）
以下に、期待される結論を得るための条件を得る推論、すなわち後ろ向き推論、について説明する。
【００７９】
図１４は、推論部１１４が後ろ向き推論を行なう際の処理を説明するフローチャートを示す。このフローチャートの処理を行なう前には、スタックは空の状態となっているとする。また、このフローチャートの処理は、例えば、入力装置１０２から推論の実行の命令を表す情報が情報取得部１１３に取得されたときなどに、行なわれる。また、後ろ向き推論を行なうかどうかは、「⊃」の右辺の論理式の真偽値が不定でないかどうかにより判断することができる。例えば、図７において、テキストエリア７０５に値として「必要」が入力されている場合には、「稟議要否＝必要」および「稟議要否＝不要」それぞれの真偽値は不定ではなくなるので、後ろ向き推論を行なうことができる。
【００８０】
ステップＳ１４０１の処理においては、ルートノードをスタックにプッシュする。これによりルートノードがスタックの一番上のスロットに格納される。
【００８１】
ステップＳ１４０２の処理において、スタックが空であるかどうかを判断する。スタックが空であれば、推論が終了したことになる。そこで、推論の終了を出力装置１０３に送信したり、推論の結果を出力装置１０３に送信したりする。
【００８２】
ステップＳ１４０２の処理において、スタックが空でなければ、ステップＳ１４０３へ処理を移行させて、スタックをポップする。これによりノードが得られる。
【００８３】
ステップＳ１４０４において、ステップＳ１４０３で得られたノードの表す論理式が真であるかどうかを真偽判定部１１２により判定する。もし、真偽判定部１１２による真偽の判定が真であれば、ステップＳ１４０６へ処理を移行する。真でなければステップＳ１４０５へ処理を移行させ、ステップＳ１４０３で得られたノードの表す論理式が真であることを表示する。例えば、「役職＝アシスタント」の論理式に対応して、役職はアシスタントでなければならない旨の表示を行なう。なお、真偽判定部１１２による判定が偽であれば、なにもせずにステップＳ１４０２へ処理を移行させ、ステップＳ１４０５が実行されるのは、真偽判定部１１２による判定が不定である場合となるようにしてもよい。
【００８４】
真偽判定部１１２による判定が偽であれば、ステップＳ１４０３で得られたノードの表す論理式を記憶し、ステップＳ１４０２においてスタックが空であると判断されたときに記憶された論理式を出力装置１０３に出力し、出力装置１０３は、偽と判定された論理式が真であれば、期待される結論が得られる旨を表示してもよい。
【００８５】
ステップＳ１４０６の処理において、ステップＳ１４０３で得られたノードの次のノードを次ノード取得部１１１により取得する。そして、ステップＳ１４０７の処理において、ステップＳ１４０７の処理により得られたノードの中にルートノードが存在するかどうかを判断する。もし、ルートノードがステップＳ１４０７の処理により得られたノードの中にルートノードが存在すれば、ステップＳ１４０２へ戻る。
【００８６】
もし、ステップＳ１４０７の判断により、ルートノードがステップＳ１４０７の処理により得られたノードの中にルートノードが存在しなければ、ステップＳ１４０７の処理により得られたノードをスタックにプッシュする。
【００８７】
なお、ステップＳ１４０５において、必要な条件として表示するかわりに、論理式を充足するべき条件としてメモリなどに記憶してもよい。そして、ステップＳ１４０７において、ルートノードがステップＳ１４０７の処理により得られたノードの中にルートノードが存在した場合に、記憶された条件を出力装置１０３に出力し、充足されるべき論理式として提示してもよい。特に、論理式が不等式である場合には、線形計画法などにより、最適解を求めるようにしてもよい。
【００８８】
図１４を用いて、深さ優先で推論を行なう処理について説明したが、幅優先で推論を行なうこともできる。
【００８９】
本発明の一実施形態に係る推論装置は、コンピュータを用いて実現することができる。例えば、ルールベースをメモリや二次記憶装置に複数のルールを表すグラフデータ構造を記憶する。入力装置より受信した情報をメモリなどの記憶領域に記憶する。そして、複数のルールいずれかのルールの右辺の論理式が真となるかを判断し、そうであれば、後ろ向き推論を行ない、真と判定された論理式が右辺に並ぶルールの左辺に並ぶ論理積の複数の論理式を表すノードを走査して、真と判定された論理式が右辺に並ぶルールが成り立つために真と判定されるべき論理式を算出する。また、複数のルールの全てのルールの右辺の論理式の真偽が不定であると判定されると、前向き推論を行ない、直列に接続されたノードを走査し、複数のルールのいずれかのルールの右辺に並ぶ論理式のうち真となる論理式を算出する。
【符号の説明】
【００９０】
１００  推論システム、１０１  推論装置、１０２  入力装置、１０３  出力装置、１１０  ルールベース、１１１  次ノード取得部、１１２  真偽判定部、１１３  情報取得部、１１４  推論部
【図１】
0005389890.tif 000002
【図２】
0005389890.tif 000003
【図３】
0005389890.tif 000004
【図４】
0005389890.tif 000005
【図５】
0005389890.tif 000006
【図６】
0005389890.tif 000007
【図７】
0005389890.tif 000008
【図８】
0005389890.tif 000009
【図９】
0005389890.tif 000010
【図１０】
0005389890.tif 000011
【図１１】
0005389890.tif 000012
【図１２】
0005389890.tif 000013
【図１３】
0005389890.tif 000014
【図１４】
0005389890.tif 000015