明細書 :生成装置、生成方法及びプログラム
| 発行国 | 日本国特許庁(JP) | ||||
|---|---|---|---|---|---|
| 公報種別 | 公開特許公報(A) | ||||
| 公開番号 | 特開2019-153047 (P2019-153047A) | ||||
| 公開日 | 令和元年9月12日(2019.9.12) | ||||
| 発明の名称または考案の名称 | 生成装置、生成方法及びプログラム | ||||
| 国際特許分類 | G06N 5/04 (2006.01) | ||||
| ＦＩ | G06N 5/04 | ||||
| 請求項の数または発明の数 | 4 | ||||
| 出願形態 | OL | ||||
| 全頁数 | 17 | ||||
| 出願番号 | 特願2018-037413 (P2018-037413) | ||||
| 出願日 | 平成30年3月2日(2018.3.2) | ||||
| 発明者または考案者 | 【氏名】西野 正彬 【氏名】山本 章博 【氏名】新藤 光 |
||||
| 出願人 | 【識別番号】000004226 【氏名又は名称】日本電信電話株式会社 【識別番号】504132272 【氏名又は名称】国立大学法人京都大学 |
||||
| 個別代理人の代理人 | 【識別番号】100107766、【弁理士】、【氏名又は名称】伊東 忠重 【識別番号】100070150、【弁理士】、【氏名又は名称】伊東 忠彦 【識別番号】100124844、【弁理士】、【氏名又は名称】石原 隆治 |
||||
| 審査請求 | 未請求 | ||||
| 要約 | 【課題】帰納論理プログラミングの全ての解を得る生成装置、生成方法及びプログラムを提供する。 【解決手段】帰納論理プログラミングの問題の解となる論理プログラムを表す仮説Σの各々を示す情報を生成する生成装置であって、正例の訓練例を示す基礎原子論理式の集合ε＋に含まれる基礎原子論理式Ｅが背景知識Ｂと仮説Σ１との和集合の論理的帰結となるような仮説Σ１に対応する論理関数ｆを表す第１の二分決定図を構築する第１の生成手段と、負例の仮説Σ２に対応する論理関数ｇを表す第２の二分決定図を構築する第２の生成手段と、前記第１の二分決定図の各々と、前記第２の二分決定図の各々とをＡｐｐｌｙ演算することで、第３の二分決定図を生成する第３の生成手段と、を有する。 【選択図】図２ |
||||
| 特許請求の範囲 | 【請求項1】 帰納論理プログラミングの問題の解となる論理プログラムを表す仮説Σの各々を示す情報を生成する生成装置であって、 背景知識Ｂと、正例の訓練例を示す基礎原子論理式の集合ε＋と、前記仮説Σに含まれ得る縮小確定節の集合Ｐとが入力されると、前記集合ε＋に含まれる各基礎原子論理式Ｅについて、該基礎原子論理式Ｅが前記背景知識Ｂと仮説Σ１との和集合の論理的帰結となるような仮説Σ１に対応する論理関数ｆを表す第１の二分決定図を構築する第１の生成手段と、 前記背景知識Ｂと、負例の訓練例を示す基礎原子論理式の集合ε－と、前記集合Ｐとが入力されると、前記集合ε－に含まれる各基礎原子論理式Ｅについて、該基礎原子論理式Ｅが前記背景知識Ｂと仮説Σ２との和集合の論理的帰結となるような仮説Σ２に対応する論理関数ｇを表す第２の二分決定図を構築する第２の生成手段と、 前記第１の二分決定図の各々と、前記第２の二分決定図の各々とをＡｐｐｌｙ演算することで、第３の二分決定図を生成する第３の生成手段と、 を有し、 前記第１の生成手段及び第２の生成手段は、 前記基礎原子論理式Ｅを論理的帰結とする仮説の集合を表現する論理関数を［Ｅ］、前記集合Ｐに含まれる各縮小確定節Ａ←Ｂ１，・・・，Ｂｎのうち、代入θに対してＥ＝Ａθを満たす縮小確定節Ａ←Ｂ１，・・・，Ｂｎの添え字の集合をＪＥとして、 【数14】 を再帰的にＡｐｐｌｙ演算することで、前記第１の二分決定図及び前記第２の二分決定図をそれぞれ構築する、ことを特徴とする生成装置。 【請求項2】 前記第３の生成手段は、 前記第１の二分決定図の各々を表すＭ個の論理関数をｆ１，・・・ｆＭ、前記第２の二分決定図の各々を表すＫ個の論理関数をｇ１，・・・ｇＫとして、 【数15】 によって表される前記第３の二分決定図をＡｐｐｌｙ演算により生成する、ことを特徴とする請求項１に記載の生成装置。 【請求項3】 帰納論理プログラミングの問題の解となる論理プログラムを表す仮説Σの各々を示す情報を生成するコンピュータが、 背景知識Ｂと、正例の訓練例を示す基礎原子論理式の集合ε＋と、前記仮説Σに含まれ得る縮小確定節の集合Ｐとが入力されると、前記集合ε＋に含まれる各基礎原子論理式Ｅについて、該基礎原子論理式Ｅが前記背景知識Ｂと仮説Σ１との和集合の論理的帰結となるような仮説Σ１に対応する論理関数ｆを表す第１の二分決定図を構築する第１の生成手順と、 前記背景知識Ｂと、負例の訓練例を示す基礎原子論理式の集合ε－と、前記集合Ｐとが入力されると、前記集合ε－に含まれる各基礎原子論理式Ｅについて、該基礎原子論理式Ｅが前記背景知識Ｂと仮説Σ２との和集合の論理的帰結となるような仮説Σ２に対応する論理関数ｇを表す第２の二分決定図を構築する第２の生成手順と、 前記第１の二分決定図の各々と、前記第２の二分決定図の各々とをＡｐｐｌｙ演算することで、第３の二分決定図を生成する第３の生成手順と、 を実行し、 前記第１の生成手順及び第２の生成手順は、 前記基礎原子論理式Ｅを論理的帰結とする仮説の集合を表現する論理関数を［Ｅ］、前記集合Ｐに含まれる各縮小確定節Ａ←Ｂ１，・・・，Ｂｎのうち、代入θに対してＥ＝Ａθを満たす縮小確定節Ａ←Ｂ１，・・・，Ｂｎの添え字の集合をＪＥとして、 【数16】 を再帰的にＡｐｐｌｙ演算することで、前記第１の二分決定図及び前記第２の二分決定図をそれぞれ構築する、ことを特徴とする生成方法。 【請求項4】 コンピュータを、請求項１又は２の何れか一項に記載の生成装置における各手段として機能させるためのプログラム。 |
||||
| 発明の詳細な説明 | 【技術分野】 【0001】 本発明は、生成装置、生成方法及びプログラムに関する。 【背景技術】 【0002】 論理プログラムを用いた機械学習手法である帰納論理プログラミング（ＩＬＰ：Inductive Logic Programming）が従来から知られている（非特許文献１）。帰納論理プログラミングでは、与えられた訓練データ（以降では、「訓練例」とも表す。）と整合性がとれるような論理プログラムを推定する技術である。このため、帰納論理プログラミングにより、論理プログラムを人手で設計しなくても、訓練例を与えるだけで、これらの訓練例と整合性がとれるような論理プログラムを獲得することができる。 【先行技術文献】 【0003】 【非特許文献1】山本，「帰納論理プログラミングの基礎理論とその展開」，コンピュータソフトウェア，Vol.23, No. 2, pp. 29-44, 2006. 【発明の概要】 【発明が解決しようとする課題】 【0004】 ここで、従来の帰納論理プログラミングのアルゴリズムでは、与えられた訓練例と矛盾しない論理プログラム（解）を１つ獲得することを目的としている。しかしながら、実際には訓練例と矛盾しないような解が多数存在する可能性がある。 【0005】 このため、従来の帰納論理プログラミングでは、与えられた訓練例と矛盾しない解を複数列挙することができず、例えば、与えられた訓練例と矛盾しない論理プログラムの中から所望の条件を満たす最適な論理プログラムを求めたい等の要求に応えることが困難であった。 【0006】 本発明の実施の形態は、上記の点に鑑みてなされたもので、帰納論理プログラミングの全ての解を得ることを目的とする。 【課題を解決するための手段】 【0007】 上記目的を達成するため、本発明の実施の形態は、帰納論理プログラミングの問題の解となる論理プログラムを表す仮説Σの各々を示す情報を生成する生成装置であって、背景知識Ｂと、正例の訓練例を示す基礎原子論理式の集合ε＋と、前記仮説Σに含まれ得る縮小確定節の集合Ｐとが入力されると、前記集合ε＋に含まれる各基礎原子論理式Ｅについて、該基礎原子論理式Ｅが前記背景知識Ｂと仮説Σ１との和集合の論理的帰結となるような仮説Σ１に対応する論理関数ｆを表す第１の二分決定図を構築する第１の生成手段と、前記背景知識Ｂと、負例の訓練例を示す基礎原子論理式の集合ε－と、前記集合Ｐとが入力されると、前記集合ε－に含まれる各基礎原子論理式Ｅについて、該基礎原子論理式Ｅが前記背景知識Ｂと仮説Σ２との和集合の論理的帰結となるような仮説Σ２に対応する論理関数ｇを表す第２の二分決定図を構築する第２の生成手段と、前記第１の二分決定図の各々と、前記第２の二分決定図の各々とをＡｐｐｌｙ演算することで、第３の二分決定図を生成する第３の生成手段と、を有し、前記第１の生成手段及び第２の生成手段は、前記基礎原子論理式Ｅを論理的帰結とする仮説の集合を表現する論理関数を［Ｅ］、前記集合Ｐに含まれる各縮小確定節Ａ←Ｂ１，・・・，Ｂｎのうち、代入θに対してＥ＝Ａθを満たす縮小確定節Ａ←Ｂ１，・・・，Ｂｎの添え字の集合をＪＥとして、所定の式を再帰的にＡｐｐｌｙ演算することで、前記第１の二分決定図及び前記第２の二分決定図をそれぞれ構築する、ことを特徴とする。 【発明の効果】 【0008】 帰納論理プログラミングの全ての解を得ることができる。 【図面の簡単な説明】 【0009】 【図1】二分決定図の一例を示す図である。 【図2】本発明の実施の形態における生成装置の機能構成の一例を示す図である。 【図3】本発明の実施の形態における生成処理部が実行する処理の流れの一例を示すフローチャートである。 【図4】本発明の実施の形態における生成装置のハードウェア構成の一例を示す図である。 【発明を実施するための形態】 【0010】 以下、本発明の実施の形態について説明する。本発明の実施の形態では、帰納論理プログラミングにおいて、与えられた訓練例と整合性がとれる論理プログラムを全て得ることを目的とする。ただし、帰納論理プログラミングの解となる論理プログラムの数は指数的に増加する可能性がある。このため、これらの全ての論理プログラムを出力するようなシステムは現実的な設定では動作しない可能性がある。そこで、全ての論理プログラムを出力するのではなく、全ての解の集合を表す二分決定図（ＢＤＤ：Binary Decision Diagram）を構築することで、これら全ての論理プログラムの列挙を実現する。なお、ＢＤＤについては以下の参考文献１を参照されたい。 【0011】 ［参考文献１］ Bryant, R.E., "Graph-Based Algorithms for Boolean Function Manipulation", IEEE Trans. Computers, Vol.C-35, No.8, pp.677-691, 1986. ＢＤＤは、論理プログラムの集合をグラフとして表現可能なデータ構造である。ＢＤＤを用いて論理プログラムの集合を表現することで、膨大な数の論理プログラムの集合を圧縮及び索引化することができるため、計算機の記憶媒体等に格納することができるようになる。また、ＢＤＤによって表現された論理プログラムの集合から、或る条件を満たす論理プログラムを１つ取り出すような操作も効率的に実行することが可能となる。 【0012】 そこで、本発明の実施の形態では、与えられた訓練例と整合性がとれる全ての論理プログラムの集合の索引を表すＢＤＤを生成及び出力する生成装置１０について説明する。 【0013】 まず、本発明の実施の形態に係る生成装置１０について説明する前に、いくつかの用語等について説明する。 【0014】 ＜一階述語論理＞ 一階述語論理における項とは、（１）変数、（２）定数記号、及び（３）アリティｎの関数記号ｆとｎ個の項ｔ１，・・・，ｔｎとによって作られる記号列ｆ（ｔ１，・・・，ｔｎ）のことである。 【0015】 また、アリティｎの述語記号Ｐとｎ個の項ｔ１，・・・，ｔｎとによって作られる記号列Ｐ（ｔ１，・・・，ｔｎ）を原子論理式という。原子論理式Ａ及びその否定￢Ａをリテラルといい、特にＡを「正リテラル」、￢Ａを「負リテラル」という。リテラルの換言（すなわち、「∨」）に現れる変数の全体を束縛して得られる論理式を節という。 【0016】 一階述語論理における論理式の真偽値は解釈によって決定される。一階述語論理の言語Ｌに対する解釈Ｉは、空でない集合（ドメイン）Ｄによって決定される。すなわち、解釈Ｉによって、定数記号はＤの要素に割り当てられ、アリティｎの関数記号はＤｎからＤへの写像に割り当てられ、アリティｎの述語記号はＤｎから真偽値｛Ｔｒｕｅ，ｆａｌｓｅ｝への写像に割り当てられる。 【0017】 論理式φが解釈Ｉの下で真である場合、解釈Ｉはφのモデルであるという。論理式の集合Σの任意のモデルが論理式φのモデルである場合、論理式φは、論理式の集合Σの論理的帰結であるといい、 【0018】 【数1】 と表す。一方で、論理式φが、論理式の集合Σの論理的帰結でない場合は、 【0019】 【数2】 と表す。 【0020】 また、変数を含まない原子論理式を基礎原子論理式という。同様に、変数を含まないリテラルを基礎リテラルという。変数を含まない節を基礎節という。 【0021】 一階述語論理において、変数ｘ１，・・・，ｘｍを項ｔ１，・・・，ｔｍに置き換えることを代入という。このような代入は、θ＝｛ｘ１／ｔ１，・・・，ｘｍ／ｔｍ｝と表される。また、一階述語論理の節Ｃに含まれる全ての変数ｘ１，・・・，ｘｍを項ｔ１，・・・，ｔｍに同時に置き換えたものをＣθと表す。 【0022】 ここで、帰納論理プログラミングとは、節の有限集合 【0023】 【数3】 が与えられた場合に、全ての節Ｅ∈ε＋に対して、以下の式１が成り立ち、 【0024】 【数4】 、かつ、全ての節Ｅ∈ε－に対して、以下の式２が成り立つような節の有限集合Σを求める問題のことである。なお、以降では、節の有限集合のことを仮説とも呼ぶ。 【0025】 【数5】 ここで、 【0026】 【数6】 は背景知識とも呼ばれる。この背景知識を、以降では、「背景知識Ｂ」とも表す。また、ε＋は正例、ε－は負例とも呼ばれる。 【0027】 例えば、 【0028】 【数7】 が与えられたとすると、仮説Σ＝｛Ｐ（０）←，Ｐ（ｓ（ｓ（Ｘ）））←Ｐ（ｘ）｝は、この機能論理プログラミングの問題の１つの解である。なお、Ｐは述語記号、ｓは関数記号である。また、Ｐ（０）←、Ｐ（ｓ（ｓ（Ｘ）））←Ｐ（ｘ）は確定節を表す。 【0029】 確定節とは、正リテラルをちょうど１つ含む節のことである。確定節は、原子論理式Ａ，Ｂ１，・・・，Ｂｎを用いて、Ａ←Ｂ１，・・・，Ｂｎ又はＡ←と表される。なお、Ａ←の形で表される確定節は単位節と呼ばれる。また、変数を含まない確定節を基礎確定節といい、変数を含まない単位節を基礎単位節という。 【0030】 更に、或る原子論理式Ａに含まれる関数記号、定数記号及び変数記号の総数を｜Ａ｜と表す。任意の代入θ及びｉ＝１，・・・，ｎに対して、｜Ａθ｜≧｜Ｂｉθ｜を満たす場合、確定節Ａ←Ｂ１，・・・，Ｂｎを縮小確定節という。 【0031】 ＜二分決定図＞ 二分決定図（ＢＤＤ）は、論理関数を有向非巡回グラフとして表現するデータ構造である。一例として、論理関数（ｘ１∧ｘ２）∨（ｘ１∧ｘ３）∨（ｘ２∧ｘ３）を表現するＢＤＤを図１に示す。 【0032】 ＢＤＤは、終端ノードと分岐ノードとの２種類のノードを有する。終端ノードは、当該ノードを始点とする枝（アーク）を持たないノードである。図１に示す例では、終端ノードは四角形で表されたノード（ノードｎ５及びノードｎ６）である。終端ノードには、⊥終端ノード（以降、「第１終端ノード」という。）と、 【0033】 【数8】 （以下、「第２終端ノード」という。）との２種類のノードがある。１つのＢＤＤには、第１終端ノードと第２終端ノードとがそれぞれ高々１つずつ存在する。 【0034】 一方で、分岐ノードとは、終端ノードではないノードのことである。図１に示す例では、分岐ノードは円形で表されたノード（ノードｎ１、ノードｎ２、ノードｎ３及びノードｎ４）である。各分岐ノードには、ＢＤＤによって表現される論理関数の変数全体の集合のうち、当該分岐ノードに対応する要素を表すラベルが付与される。図１に示す例では、ノードｎ１には、変数ｘ１を表す要素１がラベルとして付与されている。同様に、ノードｎ２及びノードｎ３には、変数ｘ２を表す要素２がラベルとして付与されている。同様に、ノードｎ４には、変数ｘ３を表す要素３がラベルとして付与されている。 【0035】 また、各分岐ノードには、当該分岐ノードを始点とする枝が必ず２つ存在し、それぞれｌｏ枝及びｈｉ枝と呼ばれる。図１に示す例では、ｌｏ枝は破線、ｈｉ枝は実線で表されており、ノードｎ１のｌｏ枝はノードｎ２を指し、ｈｉ枝はノードｎ３を指している。この場合、ノードｎ１は親ノード、ノードｎ２及びノードｎ３は子ノードとなる。 【0036】 同様に、ノードｎ２のｌｏ枝はノードｎ５を指し、ｈｉ枝はノードｎ４を指している。この場合、ノードｎ２は親ノード、ノードｎ５及びノードｎ４は子ノードとなる。他のノードも同様に、ノードｎ３のｌｏ枝及びｈｉ枝はそれぞれノードｎ４及びノードｎ６を指し、ノードｎ３が親ノード、ノードｎ４及びノードｎ６が子ノードとなる。ノードｎ４のｌｏ枝及びｈｉ枝はそれぞれノードｎ５及びノードｎ６を指し、ノードｎ４が親ノード、ノードｎ５及びノードｎ６が子ノードとなる。 【0037】 ＢＤＤには親ノードを持たないノードが必ず１つのみ存在し、根ノードと呼ばれる。図１に示す例では、ノードｎ１が根ノードである。 【0038】 根ノードから第２終端ノードまでの各経路は、ＢＤＤが表現する論理関数を真とするような変数の割り当てに対応している。ＢＤＤの各経路を３つの変数（ｘ１，ｘ２，ｘ３）で表現することとし、各変数の値は０又は１を取るものとし、ｈｉ枝を通る経路のときは変数の値が１であり、ｌｏ枝を通る経路のときは変数の値が０であるものとすれば、図１に示すＢＤＤにおいて、根ノードから第２終端ノードに至る各経路に対応する変数の割り当ては値（１，１，＊）、（１，０，１）、（０，１，１）で表現できる。ここで、＊は０又は１のいずれかの値を割り当てることに相当する。 【0039】 例えば、（１，１，＊）は、図１に示すＢＤＤにおいて、ノードｎ１、ノードｎ３及びノードｎ６を辿る経路を表す。ここで、この場合、変数ｘ３を表す要素３のラベルが付与されているノードを辿らないが、これは、図１に示すＢＤＤでは冗長な節点が削除されているためである（すなわち、図１に示すＢＤＤは既約である。）。 【0040】 同様に、（１，０，１）は、図１に示すＢＤＤにおいて、ノードｎ１、ノードｎ３、ノードｎ４及びノードｎ６を辿る経路を表す。同様に、（０，１，１）は、図１に示すＢＤＤにおいて、ノードｎ１、ノードｎ２、ノードｎ４及びノードｎ６を辿る経路を表す。 【0041】 なお、根ノードから第２終端ノード（及び第１終端ノード）までの各経路が表現する変数の順序が同じであるＢＤＤを「順序付きＢＤＤ」ともいう。図１に示すＢＤＤは順序付きＢＤＤ（より正確には、既約な順序付きＢＤＤ）である。本発明の実施の形態において、ＢＤＤは、順序付きＢＤＤ（及び既約な順序付きＢＤＤ）であるものとする。 【0042】 ＢＤＤの各ノードは、当該ノードを根ノードとする部分ＢＤＤを表現しており、部分ＢＤＤは１つの論理関数を表現している。図１に示す例では、例えば、ノードｎ２を根ノードとする部分ＢＤＤは、変数ｘ２及びｘ３に対して定義される部分論理関数ｘ２∧ｘ３を表現している。なお、第１終端ノードはＢＤＤによって表現される論理関数の真偽値が０であることに対応し、第２終端ノードはＢＤＤによって表現される論理関数の真偽値が１であることに対応するものとする。 【0043】 なお、以降では、ＢＤＤのノードはＢ個存在するものとし、各ノードをｂ１，・・・，ｂＢと表す。また、ｂ１を根ノード、ｂＢを第２終端ノードとし、任意の２つのノードｂｉ及びｂｊに対して、ｉ＜ｊならばｂｉはｂｊの子ノードにはなり得ないものとする。 【0044】 ＢＤＤは、各ノードについて、（ノードのＩＤ，ラベル，ｈｉ枝の指すノードのＩＤ，ｌｏ枝の指すノードのＩＤ）の４つの組で表現できる。図１に示すＢＤＤは６つノードを持つため、 【0045】 【数9】 と表現することができる。 【0046】 ＜Ａｐｐｌｙ演算＞ 論理関数ｆを表現するＢＤＤをＺ（ｆ）、論理関数ｇを表現するＢＤＤをＺ（ｇ）として、論理関数ｆとｇとの間に二項演算を適用することによって得られる論理関数ｆ∨ｇ及びｆ∧ｇをそれぞれ表現するＢＤＤをＺ（ｆ∨ｇ）及びＺ（ｆ∧ｇ）と表すものとする。Ｚ（ｆ）及びＺ（ｇ）からＺ（ｆ∨ｇ）やＺ（ｆ∧ｇ）を求める演算は、Ａｐｐｌｙ演算と呼ばれる。Ａｐｐｌｙ演算は、Ｚ（ｆ）及びＺ（ｇ）の大きさに比例する演算時間で実行できることが知られている。なお、Ａｐｐｌｙ演算については上記の参考文献１を参照されたい。 【0047】 ＜生成装置１０＞ 次に、本発明の実施の形態に係る生成装置１０について説明する。 【0048】 ≪機能構成≫ まず、本発明の実施の形態における生成装置１０の機能構成について、図２を参照しながら説明する。図２は、本発明の実施の形態における生成装置１０の機能構成の一例を示す図である。 【0049】 図２に示すように、本発明の実施の形態における生成装置１０は、生成処理部１００を有する。生成処理部１００は、生成装置１０にインストールされた１以上のプログラムがＣＰＵ（Central Processing Unit）等に実行させる処理により実現される。 【0050】 生成処理部１００は、背景知識Ｂと、訓練例の集合ε＋及びε－と、仮説Σに含まれ得る節の集合Ｐとを入力する。ここで、訓練例は全て基礎単位節であり、背景知識Ｂ、集合ε＋、集合ε－及び集合Ｐは有限集合であるものとする。また、集合Ｐに含まれる節は全て縮小確定節であり、集合Ｐに含まれる縮小確定節の数をＮとする。なお、集合ε＋は正例の訓練例の集合であり、集合ε－は負例の訓練例の集合である。 【0051】 このとき、生成処理部１００は、入力された集合ε＋及びε－と背景知識Ｂとに基づいて、上記の式１及び式２が成立するような仮説Σの集合を求める。なお、仮説Σは集合Ｐの部分集合である。 【0052】 本発明の実施の形態では、仮説ΣをＮ次元の２値ベクトルｘを用いて表現する。２値ベクトルｘのｉ番目の成分をｘｉとする。そして、集合Ｐに含まれるｉ番目の縮小確定節が仮説Σに含まれる場合はｘｉ＝１、ｉ番目の縮小確定節が仮説Σに含まれない場合はｘｉ＝０とする。このＮ次元２値ベクトルｘによって仮説Σを表現することで、仮説Σの集合は論理関数として表現できる。すなわち、仮説Σを表す２値ベクトルｘが帰納論理プログラミングの問題の解である場合はｆ（ｘ）＝１、解でない場合はｆ（ｘ）＝０となるような論理関数ｆは、全ての解の集合を表現していると見做すことができる。 【0053】 したがって、この２値ベクトルｘを構成する各変数ｘｉを、ＢＤＤを表現する変数とみれば（すなわち、ＢＤＤの各ノードに付与されるｉ個のラベルがそれぞれ各変数ｘｉを表すとすれば）、論理関数ｆを表現するＢＤＤによって、仮説Σの集合を表現することができる。このとき、ＢＤＤの根ノードから第２終端ノードまでに至る経路の各々が、帰納論理プログラミングの問題の解となる仮説を表す。一方で、ＢＤＤの根ノードから第１終端ノードまでに至る経路の各々が、帰納論理プログラミングの問題の解とならない仮説を表す。 【0054】 このことは、ＢＤＤの各経路に対応する変数の割り当ては、当該経路に対応する仮説の索引と捉えることができることを意味する。 【0055】 すなわち、生成処理部１００は、入力された集合ε＋及びε－と背景知識Ｂとに基づいて、ＢＤＤ Ｚ（ｈ）を構築する。そして、生成処理部１００は、構築したＢＤＤ Ｚ（ｈ）を出力する。このＺ（ｈ）の根ノードから第２終端ノードまでに至る経路に対応する変数の割り当てが、帰納論理プログラミングの解である仮説Σの索引である。したがって、生成処理部１００は、入力された集合ε＋及びε－と背景知識Ｂとに基づいて、ＢＤＤ Ｚ（ｈ）を構築することにより、帰納論理プログラミングの解である仮説Σの索引を生成すると言うこともできる。 【0056】 なお、生成処理部１００は、帰納論理プログラミングの解である仮説Σの索引として、構築したＢＤＤ Ｚ（ｈ）を出力しても良いし、このＢＤＤ Ｚ（ｈ）の根ノードから第２終端ノードまでに至る経路に対応する変数の割り当ての集合を出力しても良い。 【0057】 ここで、生成処理部１００には、第１仮説集合生成部１０１と、第２仮説集合生成部１０２と、第３仮説集合生成部１０３とが含まれる。 【0058】 第１仮説集合生成部１０１は、背景知識Ｂと、訓練例の集合ε＋と、集合Ｐとを入力して、全ての基礎原子論理式Ｅ∈ε＋について、上記の式１を満たす仮説Σ１の集合に対応する論理関数を表現するＢＤＤを構築する。すなわち、ε＋に基礎原子論理式がＭ個含まれるとした場合、ｉ（ｉ＝１，・・・，Ｍ）毎に、第１仮説集合生成部１０１は、ｉ番目の基礎原子論理式Ｅｉに対して、 【0059】 【数10】 となるような仮説Σ１の集合を表現する論理関数ｆｉを表すＢＤＤ Ｚ（ｆｉ）を構築する。ＢＤＤの構築方法については後述する。なお、ε＋に含まれる訓練例は全て基礎単位節であることから、これらは全て基礎原子論理式である。 【0060】 第２仮説集合生成部１０２は、背景知識Ｂと、訓練例の集合ε－と、集合Ｐとを入力して、全ての原子論理式Ｅ∈ε－について、上記の式１を満たす仮説Σ２の集合に対応する論理関数を表現するＢＤＤを構築する。すなわち、ε－に基礎原子論理式がＫ個含まれるとした場合、ｉ（ｉ＝１，・・・，Ｋ）毎に、第２仮説集合生成部１０２は、ｉ番目の基礎原子論理式Ｅｉに対して、 【0061】 【数11】 となるような仮説Σ２の集合を表現する論理関数ｇｉを表すＢＤＤ Ｚ（ｇｉ）を構築する。ＢＤＤの構築方法については後述する。なお、ε－に含まれる訓練例は全て基礎単位節であることから、これらは全て基礎原子論理式である。 【0062】 ここで、上記では、負例である訓練例Ｅｉ∈ε－に対しても上記の式１を満たすΣ２の集合に対応する論理関数ｇｉを表すＢＤＤ Ｚ（ｇｉ）を構築した。これは、後述する式３において、各論理関数ｇｉに対して否定を示す論理記号（￢）を付与するためである。ただし、後述する式３において、各論理関数ｇｉに対して否定を示す論理記号（￢）を付与しない場合には、第２仮説集合生成部１０２は、上記の式２を満たす仮説Σ２の集合に対応する論理関数を表現するＢＤＤを構築しても良い。 【0063】 第３仮説集合生成部１０３は、第１仮説集合生成部１０１で構築したＺ（ｆｉ）と、第２仮説集合生成部１０２で構築したＺ（ｇｉ）とを入力して、これらのＢＤＤのＡｐｐｌｙ演算を行うことにより、以下の式３に示す論理式ｈを表すＢＤＤ Ｚ（ｈ）を構築する。 【0064】 【数12】 ≪処理の流れ≫ 次に、本発明の実施の形態における生成処理部１００が実行する処理の流れについて、図３を参照しながら説明する。図３は、本発明の実施の形態における生成処理部１００が実行する処理の流れの一例を示すフローチャートである。なお、以降では、背景知識Ｂと、訓練例の集合ε＋及びε－と、集合Ｐとが生成処理部１００に入力されたものとする。 【0065】 ステップＳ１０１：生成処理部１００の第１仮説集合生成部１０１は、背景知識Ｂと、正例の訓練例の集合ε＋と、集合Ｐとを入力して、ｉ＝１，・・・，Ｍに対して、上述したＺ（ｆｉ）を構築する。 【0066】 ここで、ＢＢＤ Ｚ（ｆｉ）の構築方法について説明する。以降では、ｆｉの添字ｉを固定して、単に「ｆ」と表し、Ｚ（ｆ）の構築方法について説明する。 【0067】 或る基礎原子論理式Ｅを論理的帰結とするような仮説の集合を表現する論理関数を［Ｅ］とする。また、集合Ｐに含まれる各縮小確定節に対して添字ｉ（ｉ＝１，・・・，Ｎ）が付与されているものとして、集合Ｐに含まれる各縮小確定節Ａ←Ｂ１，・・・，Ｂｎのうち、或る代入θに対してＥ＝Ａθを満たすような縮小確定節の添字の集合をＪＥとする。すると、［Ｅ］は、 【0068】 【数13】 となる。ここで、θｉはｉ番目の縮小確定節に対してＥ＝Ａθｉとなるような代入を表す。このような代入は各縮小確定節に対して一意に決定される。また、ｎｉはｉ番目の縮小確定節を表す原子論理式Ｂ１，・・・，Ｂｎの数である。ｉ番目の縮小確定節は、原子論理式Ａ，Ｂ１，・・・，Ｂｎｉを用いて、Ａ←Ｂ１，・・・，Ｂｎｉと表される（ただし、「ｎｉ」は、実際には「ｉ」を下付きで表した「ｎｉ」である。）。 【0069】 上記の式４は、論理関数［Ｅ］が論理関数［Ｂｊθｉ］により再帰的に求められることを表している。縮小確定節の性質により、Ｂｊθｉは常に基礎原子論理式となり、かつ、その大きさ｜Ｂｊθｉ｜は常に｜Ｅ｜より小さくなる。他方で、背景知識Ｂと、正例の集合ε＋と、集合Ｐとはいずれも有限集合であるため、これらの集合に含まれる関数記号、定数記号、述語記号も有限である。このため、これらの関数記号、定数記号、述語記号によって構成される基礎原子論理式のうち、ε＋に含まれる最大の基礎原子論理式よりも小さいものの集合も常に有限となる。このような大きさが或る値以下の各基礎原子論理式Ｅについて、論理関数［Ｅ］を表すＢＤＤを、上記の式４により再帰的にＡｐｐｌｙ演算を実行して構築していくことによって、ε＋に含まれる各原子論理式Ｅについて論理関数ｆ＝［Ｅ］を表すＢＤＤ Ｚ（ｆ）を構築することができる。 【0070】 ステップＳ１０２：生成処理部１００の第２仮説集合生成部１０２は、背景知識Ｂと、負例の訓練例の集合ε－と、集合Ｐとを入力して、ｉ＝１，・・・，Ｋに対して、上述したＺ（ｇｉ）を構築する。 【0071】 ここで、ＢＢＤ Ｚ（ｇｉ）の構築方法について説明する。以降では、ｇｉの添字ｉを固定して、単に「ｇ」と表し、Ｚ（ｇ）の構築方法について説明する。なお、Ｚ（ｇ）の構築方法は、上述したＺ（ｆ）の構築方法と同様であるため、簡略化して説明する。 【0072】 或る基礎原子論理式Ｅを論理的帰結とするような仮説の集合を表現する論理関数を［Ｅ］とする。また、集合Ｐに含まれる各縮小確定節Ａ←Ｂ１，・・・，Ｂｎのうち、或る代入θに対してＥ＝Ａθを満たすような縮小確定節の添字の集合をＪＥとする。すると、［Ｅ］は、上記の式４となる。 【0073】 また、負例の集合ε－も有限集合であるため、背景知識Ｂ、負例の集合ε－及び集合Ｐに含まれる関数記号、定数記号、述語記号によって構成される基礎原子論理式のうち、ε－に含まれる最大の基礎原子論理式よりも小さいものの集合も常に有限となる。したがって、このような大きさが或る値以下の各基礎原子論理式Ｅについて、論理関数［Ｅ］を表すＢＤＤを、上記の式４により再帰的にＡｐｐｌｙ演算を実行して構築していくことによって、ε－に含まれる各原子論理式Ｅについて論理関数ｇ＝［Ｅ］を表すＢＤＤ Ｚ（ｇ）を構築することができる。 【0074】 ステップＳ１０３：生成処理部１００の第３仮説集合生成部１０３は、第１仮説集合生成部１０１で構築したＺ（ｆｉ）と、第２仮説集合生成部１０２で構築したＺ（ｇｉ）とを入力して、これらのＢＤＤのＡｐｐｌｙ演算を行うことにより、上記の式３に示す論理式ｈを表すＢＤＤ Ｚ（ｈ）を構築する。 【0075】 これにより、生成処理部１００により、帰納論理プログラミングの解である仮説Σの索引として、Ｚ（ｈ）又は当該Ｚ（ｈ）の根ノードから第２終端ノードまでに至る経路に対応する変数の割り当ての集合が出力される。 【0076】 以上のように、本発明の実施の形態における生成装置１０では、帰納論理プログラミングの解である仮説Σの索引の集合を、ＢＤＤ又は当該ＢＤＤの根ノードから第２終端ノードまでに至る経路に対応する変数の割り当ての集合として出力することができる。このため、本発明の実施の形態における生成装置１０によれば、膨大な数になる可能性がある帰納論理プログラミングの解の集合をＢＤＤとして圧縮・索引化して全列挙することができるようになる。このように全ての解の集合をＢＤＤとして索引化して表現することで、例えば、これらの解の中から所望の条件を満たす解を選び出して利用する等といった事も容易に行うことができるようになる。 【0077】 ≪ハードウェア構成≫ 最後に、本発明の実施の形態における生成装置１０のハードウェア構成について、図４を参照しながら説明する。図４は、本発明の実施の形態における生成装置１０のハードウェア構成の一例を示す図である。 【0078】 図４に示すように、本発明の実施の形態における生成装置１０は、入力装置２０１と、表示装置２０２と、外部Ｉ／Ｆ２０３と、ＲＡＭ（Random Access Memory）２０４と、ＲＯＭ（Read Only Memory）２０５と、ＣＰＵ２０６と、通信Ｉ／Ｆ２０７と、補助記憶装置２０８とを有する。これら各ハードウェアは、それぞれがバスＢを介して通信可能に接続されている。 【0079】 入力装置２０１は、例えばキーボードやマウス、タッチパネル等であり、ユーザが各種操作を入力するのに用いられる。表示装置２０２は、例えばディスプレイ等であり、生成装置１０の処理結果を表示する。なお、生成装置１０は、入力装置２０１及び表示装置２０２の少なくとも一方を有していなくても良い。 【0080】 外部Ｉ／Ｆ２０３は、外部装置とのインタフェースである。外部装置には、記録媒体２０３ａ等がある。生成装置１０は、外部Ｉ／Ｆ２０３を介して、記録媒体２０３ａ等の読み取りや書き込みを行うことができる。記録媒体２０３ａには、生成装置１０が有する各機能を実現するプログラム等が記録されていても良い。 【0081】 記録媒体２０３ａには、例えば、フレキシブルディスク、ＣＤ（Compact Disc）、ＤＶＤ（Digital Versatile Disk）、ＳＤメモリカード（Secure Digital memory card）、ＵＳＢ（Universal Serial Bus）メモリカード等がある。 【0082】 ＲＡＭ２０４は、プログラムやデータを一時保持する揮発性の半導体メモリである。ＲＯＭ２０５は、電源を切ってもプログラムやデータを保持することができる不揮発性の半導体メモリである。ＲＯＭ２０５には、例えば、ＯＳ（Operating System）設定やネットワーク設定等が格納されている。 【0083】 ＣＰＵ２０６は、ＲＯＭ２０５や補助記憶装置２０８等からプログラムやデータをＲＡＭ２０４上に読み出して処理を実行する演算装置である。 【0084】 通信Ｉ／Ｆ２０７は、生成装置１０を通信ネットワークに接続するためのインタフェースである。生成装置１０が有する各機能を実現するプログラムは、通信Ｉ／Ｆ２０７を介して、所定のサーバ装置等から取得（ダウンロード）されても良い。 【0085】 補助記憶装置２０８は、例えばＨＤＤ（Hard Disk Drive）やＳＳＤ（Solid State Drive）等であり、プログラムやデータを格納している不揮発性の記憶装置である。補助記憶装置２０８に格納されているプログラムやデータには、例えば、ＯＳ、当該ＯＳ上において各種機能を実現するアプリケーションプログラム、生成装置１０が有する各機能を実現するプログラム等がある。 【0086】 本発明の実施の形態における生成装置１０は、図４に示すハードウェア構成を有することにより、上述した各種処理を実現することができる。なお、図４では、本発明の実施の形態における生成装置１０が１台の装置で実現される場合について説明したが、これ限られない。本発明の実施の形態における生成装置１０は、複数台の装置で実現されていても良い。 【0087】 本発明は、具体的に開示された上記の実施形態に限定されるものではなく、特許請求の範囲から逸脱することなく、種々の変形や変更が可能である。 【符号の説明】 【0088】 １０ 生成装置 １０１ 第１仮説集合生成部 １０２ 第２仮説集合生成部 １０３ 第３仮説集合生成部 |
||||
| 図面 |
|