TOP > 国内特許検索 > 生成装置、生成方法及びプログラム > 明細書

明細書 :生成装置、生成方法及びプログラム

発行国 日本国特許庁(JP)
公報種別 公開特許公報(A)
公開番号 特開2019-153047 (P2019-153047A)
公開日 令和元年9月12日(2019.9.12)
発明の名称または考案の名称 生成装置、生成方法及びプログラム
国際特許分類 G06N   5/04        (2006.01)
FI G06N 5/04
請求項の数または発明の数 4
出願形態 OL
全頁数 17
出願番号 特願2018-037413 (P2018-037413)
出願日 平成30年3月2日(2018.3.2)
発明者または考案者 【氏名】西野 正彬
【氏名】山本 章博
【氏名】新藤 光
出願人 【識別番号】000004226
【氏名又は名称】日本電信電話株式会社
【識別番号】504132272
【氏名又は名称】国立大学法人京都大学
個別代理人の代理人 【識別番号】100107766、【弁理士】、【氏名又は名称】伊東 忠重
【識別番号】100070150、【弁理士】、【氏名又は名称】伊東 忠彦
【識別番号】100124844、【弁理士】、【氏名又は名称】石原 隆治
審査請求 未請求
要約 【課題】帰納論理プログラミングの全ての解を得る生成装置、生成方法及びプログラムを提供する。
【解決手段】帰納論理プログラミングの問題の解となる論理プログラムを表す仮説Σの各々を示す情報を生成する生成装置であって、正例の訓練例を示す基礎原子論理式の集合εに含まれる基礎原子論理式Eが背景知識Bと仮説Σとの和集合の論理的帰結となるような仮説Σに対応する論理関数fを表す第1の二分決定図を構築する第1の生成手段と、負例の仮説Σに対応する論理関数gを表す第2の二分決定図を構築する第2の生成手段と、前記第1の二分決定図の各々と、前記第2の二分決定図の各々とをApply演算することで、第3の二分決定図を生成する第3の生成手段と、を有する。
【選択図】図2
特許請求の範囲 【請求項1】
帰納論理プログラミングの問題の解となる論理プログラムを表す仮説Σの各々を示す情報を生成する生成装置であって、
背景知識Bと、正例の訓練例を示す基礎原子論理式の集合εと、前記仮説Σに含まれ得る縮小確定節の集合Pとが入力されると、前記集合εに含まれる各基礎原子論理式Eについて、該基礎原子論理式Eが前記背景知識Bと仮説Σとの和集合の論理的帰結となるような仮説Σに対応する論理関数fを表す第1の二分決定図を構築する第1の生成手段と、
前記背景知識Bと、負例の訓練例を示す基礎原子論理式の集合εと、前記集合Pとが入力されると、前記集合εに含まれる各基礎原子論理式Eについて、該基礎原子論理式Eが前記背景知識Bと仮説Σとの和集合の論理的帰結となるような仮説Σに対応する論理関数gを表す第2の二分決定図を構築する第2の生成手段と、
前記第1の二分決定図の各々と、前記第2の二分決定図の各々とをApply演算することで、第3の二分決定図を生成する第3の生成手段と、
を有し、
前記第1の生成手段及び第2の生成手段は、
前記基礎原子論理式Eを論理的帰結とする仮説の集合を表現する論理関数を[E]、前記集合Pに含まれる各縮小確定節A←B,・・・,Bのうち、代入θに対してE=Aθを満たす縮小確定節A←B,・・・,Bの添え字の集合をJとして、
【数14】
JP2019153047A_000016t.gif
を再帰的にApply演算することで、前記第1の二分決定図及び前記第2の二分決定図をそれぞれ構築する、ことを特徴とする生成装置。
【請求項2】
前記第3の生成手段は、
前記第1の二分決定図の各々を表すM個の論理関数をf,・・・f、前記第2の二分決定図の各々を表すK個の論理関数をg,・・・gとして、
【数15】
JP2019153047A_000017t.gif
によって表される前記第3の二分決定図をApply演算により生成する、ことを特徴とする請求項1に記載の生成装置。
【請求項3】
帰納論理プログラミングの問題の解となる論理プログラムを表す仮説Σの各々を示す情報を生成するコンピュータが、
背景知識Bと、正例の訓練例を示す基礎原子論理式の集合εと、前記仮説Σに含まれ得る縮小確定節の集合Pとが入力されると、前記集合εに含まれる各基礎原子論理式Eについて、該基礎原子論理式Eが前記背景知識Bと仮説Σとの和集合の論理的帰結となるような仮説Σに対応する論理関数fを表す第1の二分決定図を構築する第1の生成手順と、
前記背景知識Bと、負例の訓練例を示す基礎原子論理式の集合εと、前記集合Pとが入力されると、前記集合εに含まれる各基礎原子論理式Eについて、該基礎原子論理式Eが前記背景知識Bと仮説Σとの和集合の論理的帰結となるような仮説Σに対応する論理関数gを表す第2の二分決定図を構築する第2の生成手順と、
前記第1の二分決定図の各々と、前記第2の二分決定図の各々とをApply演算することで、第3の二分決定図を生成する第3の生成手順と、
を実行し、
前記第1の生成手順及び第2の生成手順は、
前記基礎原子論理式Eを論理的帰結とする仮説の集合を表現する論理関数を[E]、前記集合Pに含まれる各縮小確定節A←B,・・・,Bのうち、代入θに対してE=Aθを満たす縮小確定節A←B,・・・,Bの添え字の集合をJとして、
【数16】
JP2019153047A_000018t.gif
を再帰的にApply演算することで、前記第1の二分決定図及び前記第2の二分決定図をそれぞれ構築する、ことを特徴とする生成方法。
【請求項4】
コンピュータを、請求項1又は2の何れか一項に記載の生成装置における各手段として機能させるためのプログラム。
発明の詳細な説明 【技術分野】
【0001】
本発明は、生成装置、生成方法及びプログラムに関する。
【背景技術】
【0002】
論理プログラムを用いた機械学習手法である帰納論理プログラミング(ILP:Inductive Logic Programming)が従来から知られている(非特許文献1)。帰納論理プログラミングでは、与えられた訓練データ(以降では、「訓練例」とも表す。)と整合性がとれるような論理プログラムを推定する技術である。このため、帰納論理プログラミングにより、論理プログラムを人手で設計しなくても、訓練例を与えるだけで、これらの訓練例と整合性がとれるような論理プログラムを獲得することができる。
【先行技術文献】
【0003】

【非特許文献1】山本,「帰納論理プログラミングの基礎理論とその展開」,コンピュータソフトウェア,Vol.23, No. 2, pp. 29-44, 2006.
【発明の概要】
【発明が解決しようとする課題】
【0004】
ここで、従来の帰納論理プログラミングのアルゴリズムでは、与えられた訓練例と矛盾しない論理プログラム(解)を1つ獲得することを目的としている。しかしながら、実際には訓練例と矛盾しないような解が多数存在する可能性がある。
【0005】
このため、従来の帰納論理プログラミングでは、与えられた訓練例と矛盾しない解を複数列挙することができず、例えば、与えられた訓練例と矛盾しない論理プログラムの中から所望の条件を満たす最適な論理プログラムを求めたい等の要求に応えることが困難であった。
【0006】
本発明の実施の形態は、上記の点に鑑みてなされたもので、帰納論理プログラミングの全ての解を得ることを目的とする。
【課題を解決するための手段】
【0007】
上記目的を達成するため、本発明の実施の形態は、帰納論理プログラミングの問題の解となる論理プログラムを表す仮説Σの各々を示す情報を生成する生成装置であって、背景知識Bと、正例の訓練例を示す基礎原子論理式の集合εと、前記仮説Σに含まれ得る縮小確定節の集合Pとが入力されると、前記集合εに含まれる各基礎原子論理式Eについて、該基礎原子論理式Eが前記背景知識Bと仮説Σとの和集合の論理的帰結となるような仮説Σに対応する論理関数fを表す第1の二分決定図を構築する第1の生成手段と、前記背景知識Bと、負例の訓練例を示す基礎原子論理式の集合εと、前記集合Pとが入力されると、前記集合εに含まれる各基礎原子論理式Eについて、該基礎原子論理式Eが前記背景知識Bと仮説Σとの和集合の論理的帰結となるような仮説Σに対応する論理関数gを表す第2の二分決定図を構築する第2の生成手段と、前記第1の二分決定図の各々と、前記第2の二分決定図の各々とをApply演算することで、第3の二分決定図を生成する第3の生成手段と、を有し、前記第1の生成手段及び第2の生成手段は、前記基礎原子論理式Eを論理的帰結とする仮説の集合を表現する論理関数を[E]、前記集合Pに含まれる各縮小確定節A←B,・・・,Bのうち、代入θに対してE=Aθを満たす縮小確定節A←B,・・・,Bの添え字の集合をJとして、所定の式を再帰的にApply演算することで、前記第1の二分決定図及び前記第2の二分決定図をそれぞれ構築する、ことを特徴とする。
【発明の効果】
【0008】
帰納論理プログラミングの全ての解を得ることができる。
【図面の簡単な説明】
【0009】
【図1】二分決定図の一例を示す図である。
【図2】本発明の実施の形態における生成装置の機能構成の一例を示す図である。
【図3】本発明の実施の形態における生成処理部が実行する処理の流れの一例を示すフローチャートである。
【図4】本発明の実施の形態における生成装置のハードウェア構成の一例を示す図である。
【発明を実施するための形態】
【0010】
以下、本発明の実施の形態について説明する。本発明の実施の形態では、帰納論理プログラミングにおいて、与えられた訓練例と整合性がとれる論理プログラムを全て得ることを目的とする。ただし、帰納論理プログラミングの解となる論理プログラムの数は指数的に増加する可能性がある。このため、これらの全ての論理プログラムを出力するようなシステムは現実的な設定では動作しない可能性がある。そこで、全ての論理プログラムを出力するのではなく、全ての解の集合を表す二分決定図(BDD:Binary Decision Diagram)を構築することで、これら全ての論理プログラムの列挙を実現する。なお、BDDについては以下の参考文献1を参照されたい。

【0011】
[参考文献1]
Bryant, R.E., "Graph-Based Algorithms for Boolean Function Manipulation", IEEE Trans. Computers, Vol.C-35, No.8, pp.677-691, 1986.
BDDは、論理プログラムの集合をグラフとして表現可能なデータ構造である。BDDを用いて論理プログラムの集合を表現することで、膨大な数の論理プログラムの集合を圧縮及び索引化することができるため、計算機の記憶媒体等に格納することができるようになる。また、BDDによって表現された論理プログラムの集合から、或る条件を満たす論理プログラムを1つ取り出すような操作も効率的に実行することが可能となる。

【0012】
そこで、本発明の実施の形態では、与えられた訓練例と整合性がとれる全ての論理プログラムの集合の索引を表すBDDを生成及び出力する生成装置10について説明する。

【0013】
まず、本発明の実施の形態に係る生成装置10について説明する前に、いくつかの用語等について説明する。

【0014】
<一階述語論理>
一階述語論理における項とは、(1)変数、(2)定数記号、及び(3)アリティnの関数記号fとn個の項t,・・・,tとによって作られる記号列f(t,・・・,t)のことである。

【0015】
また、アリティnの述語記号Pとn個の項t,・・・,tとによって作られる記号列P(t,・・・,t)を原子論理式という。原子論理式A及びその否定¬Aをリテラルといい、特にAを「正リテラル」、¬Aを「負リテラル」という。リテラルの換言(すなわち、「∨」)に現れる変数の全体を束縛して得られる論理式を節という。

【0016】
一階述語論理における論理式の真偽値は解釈によって決定される。一階述語論理の言語Lに対する解釈Iは、空でない集合(ドメイン)Dによって決定される。すなわち、解釈Iによって、定数記号はDの要素に割り当てられ、アリティnの関数記号はDからDへの写像に割り当てられ、アリティnの述語記号はDから真偽値{True,false}への写像に割り当てられる。

【0017】
論理式φが解釈Iの下で真である場合、解釈Iはφのモデルであるという。論理式の集合Σの任意のモデルが論理式φのモデルである場合、論理式φは、論理式の集合Σの論理的帰結であるといい、

【0018】
【数1】
JP2019153047A_000003t.gif
と表す。一方で、論理式φが、論理式の集合Σの論理的帰結でない場合は、

【0019】
【数2】
JP2019153047A_000004t.gif
と表す。

【0020】
また、変数を含まない原子論理式を基礎原子論理式という。同様に、変数を含まないリテラルを基礎リテラルという。変数を含まない節を基礎節という。

【0021】
一階述語論理において、変数x,・・・,xを項t,・・・,tに置き換えることを代入という。このような代入は、θ={x/t,・・・,x/t}と表される。また、一階述語論理の節Cに含まれる全ての変数x,・・・,xを項t,・・・,tに同時に置き換えたものをCθと表す。

【0022】
ここで、帰納論理プログラミングとは、節の有限集合

【0023】
【数3】
JP2019153047A_000005t.gif
が与えられた場合に、全ての節E∈εに対して、以下の式1が成り立ち、

【0024】
【数4】
JP2019153047A_000006t.gif
、かつ、全ての節E∈εに対して、以下の式2が成り立つような節の有限集合Σを求める問題のことである。なお、以降では、節の有限集合のことを仮説とも呼ぶ。

【0025】
【数5】
JP2019153047A_000007t.gif
ここで、

【0026】
【数6】
JP2019153047A_000008t.gif
は背景知識とも呼ばれる。この背景知識を、以降では、「背景知識B」とも表す。また、εは正例、εは負例とも呼ばれる。

【0027】
例えば、

【0028】
【数7】
JP2019153047A_000009t.gif
が与えられたとすると、仮説Σ={P(0)←,P(s(s(X)))←P(x)}は、この機能論理プログラミングの問題の1つの解である。なお、Pは述語記号、sは関数記号である。また、P(0)←、P(s(s(X)))←P(x)は確定節を表す。

【0029】
確定節とは、正リテラルをちょうど1つ含む節のことである。確定節は、原子論理式A,B,・・・,Bを用いて、A←B,・・・,B又はA←と表される。なお、A←の形で表される確定節は単位節と呼ばれる。また、変数を含まない確定節を基礎確定節といい、変数を含まない単位節を基礎単位節という。

【0030】
更に、或る原子論理式Aに含まれる関数記号、定数記号及び変数記号の総数を|A|と表す。任意の代入θ及びi=1,・・・,nに対して、|Aθ|≧|Bθ|を満たす場合、確定節A←B,・・・,Bを縮小確定節という。

【0031】
<二分決定図>
二分決定図(BDD)は、論理関数を有向非巡回グラフとして表現するデータ構造である。一例として、論理関数(x∧x)∨(x∧x)∨(x∧x)を表現するBDDを図1に示す。

【0032】
BDDは、終端ノードと分岐ノードとの2種類のノードを有する。終端ノードは、当該ノードを始点とする枝(アーク)を持たないノードである。図1に示す例では、終端ノードは四角形で表されたノード(ノードn5及びノードn6)である。終端ノードには、⊥終端ノード(以降、「第1終端ノード」という。)と、

【0033】
【数8】
JP2019153047A_000010t.gif
(以下、「第2終端ノード」という。)との2種類のノードがある。1つのBDDには、第1終端ノードと第2終端ノードとがそれぞれ高々1つずつ存在する。

【0034】
一方で、分岐ノードとは、終端ノードではないノードのことである。図1に示す例では、分岐ノードは円形で表されたノード(ノードn1、ノードn2、ノードn3及びノードn4)である。各分岐ノードには、BDDによって表現される論理関数の変数全体の集合のうち、当該分岐ノードに対応する要素を表すラベルが付与される。図1に示す例では、ノードn1には、変数xを表す要素1がラベルとして付与されている。同様に、ノードn2及びノードn3には、変数xを表す要素2がラベルとして付与されている。同様に、ノードn4には、変数xを表す要素3がラベルとして付与されている。

【0035】
また、各分岐ノードには、当該分岐ノードを始点とする枝が必ず2つ存在し、それぞれlo枝及びhi枝と呼ばれる。図1に示す例では、lo枝は破線、hi枝は実線で表されており、ノードn1のlo枝はノードn2を指し、hi枝はノードn3を指している。この場合、ノードn1は親ノード、ノードn2及びノードn3は子ノードとなる。

【0036】
同様に、ノードn2のlo枝はノードn5を指し、hi枝はノードn4を指している。この場合、ノードn2は親ノード、ノードn5及びノードn4は子ノードとなる。他のノードも同様に、ノードn3のlo枝及びhi枝はそれぞれノードn4及びノードn6を指し、ノードn3が親ノード、ノードn4及びノードn6が子ノードとなる。ノードn4のlo枝及びhi枝はそれぞれノードn5及びノードn6を指し、ノードn4が親ノード、ノードn5及びノードn6が子ノードとなる。

【0037】
BDDには親ノードを持たないノードが必ず1つのみ存在し、根ノードと呼ばれる。図1に示す例では、ノードn1が根ノードである。

【0038】
根ノードから第2終端ノードまでの各経路は、BDDが表現する論理関数を真とするような変数の割り当てに対応している。BDDの各経路を3つの変数(x,x,x)で表現することとし、各変数の値は0又は1を取るものとし、hi枝を通る経路のときは変数の値が1であり、lo枝を通る経路のときは変数の値が0であるものとすれば、図1に示すBDDにおいて、根ノードから第2終端ノードに至る各経路に対応する変数の割り当ては値(1,1,*)、(1,0,1)、(0,1,1)で表現できる。ここで、*は0又は1のいずれかの値を割り当てることに相当する。

【0039】
例えば、(1,1,*)は、図1に示すBDDにおいて、ノードn1、ノードn3及びノードn6を辿る経路を表す。ここで、この場合、変数xを表す要素3のラベルが付与されているノードを辿らないが、これは、図1に示すBDDでは冗長な節点が削除されているためである(すなわち、図1に示すBDDは既約である。)。

【0040】
同様に、(1,0,1)は、図1に示すBDDにおいて、ノードn1、ノードn3、ノードn4及びノードn6を辿る経路を表す。同様に、(0,1,1)は、図1に示すBDDにおいて、ノードn1、ノードn2、ノードn4及びノードn6を辿る経路を表す。

【0041】
なお、根ノードから第2終端ノード(及び第1終端ノード)までの各経路が表現する変数の順序が同じであるBDDを「順序付きBDD」ともいう。図1に示すBDDは順序付きBDD(より正確には、既約な順序付きBDD)である。本発明の実施の形態において、BDDは、順序付きBDD(及び既約な順序付きBDD)であるものとする。

【0042】
BDDの各ノードは、当該ノードを根ノードとする部分BDDを表現しており、部分BDDは1つの論理関数を表現している。図1に示す例では、例えば、ノードn2を根ノードとする部分BDDは、変数x及びxに対して定義される部分論理関数x∧xを表現している。なお、第1終端ノードはBDDによって表現される論理関数の真偽値が0であることに対応し、第2終端ノードはBDDによって表現される論理関数の真偽値が1であることに対応するものとする。

【0043】
なお、以降では、BDDのノードはB個存在するものとし、各ノードをb,・・・,bと表す。また、bを根ノード、bを第2終端ノードとし、任意の2つのノードb及びbに対して、i<jならばbはbの子ノードにはなり得ないものとする。

【0044】
BDDは、各ノードについて、(ノードのID,ラベル,hi枝の指すノードのID,lo枝の指すノードのID)の4つの組で表現できる。図1に示すBDDは6つノードを持つため、

【0045】
【数9】
JP2019153047A_000011t.gif
と表現することができる。

【0046】
<Apply演算>
論理関数fを表現するBDDをZ(f)、論理関数gを表現するBDDをZ(g)として、論理関数fとgとの間に二項演算を適用することによって得られる論理関数f∨g及びf∧gをそれぞれ表現するBDDをZ(f∨g)及びZ(f∧g)と表すものとする。Z(f)及びZ(g)からZ(f∨g)やZ(f∧g)を求める演算は、Apply演算と呼ばれる。Apply演算は、Z(f)及びZ(g)の大きさに比例する演算時間で実行できることが知られている。なお、Apply演算については上記の参考文献1を参照されたい。

【0047】
<生成装置10>
次に、本発明の実施の形態に係る生成装置10について説明する。

【0048】
≪機能構成≫
まず、本発明の実施の形態における生成装置10の機能構成について、図2を参照しながら説明する。図2は、本発明の実施の形態における生成装置10の機能構成の一例を示す図である。

【0049】
図2に示すように、本発明の実施の形態における生成装置10は、生成処理部100を有する。生成処理部100は、生成装置10にインストールされた1以上のプログラムがCPU(Central Processing Unit)等に実行させる処理により実現される。

【0050】
生成処理部100は、背景知識Bと、訓練例の集合ε及びεと、仮説Σに含まれ得る節の集合Pとを入力する。ここで、訓練例は全て基礎単位節であり、背景知識B、集合ε、集合ε及び集合Pは有限集合であるものとする。また、集合Pに含まれる節は全て縮小確定節であり、集合Pに含まれる縮小確定節の数をNとする。なお、集合εは正例の訓練例の集合であり、集合εは負例の訓練例の集合である。

【0051】
このとき、生成処理部100は、入力された集合ε及びεと背景知識Bとに基づいて、上記の式1及び式2が成立するような仮説Σの集合を求める。なお、仮説Σは集合Pの部分集合である。

【0052】
本発明の実施の形態では、仮説ΣをN次元の2値ベクトルxを用いて表現する。2値ベクトルxのi番目の成分をxとする。そして、集合Pに含まれるi番目の縮小確定節が仮説Σに含まれる場合はx=1、i番目の縮小確定節が仮説Σに含まれない場合はx=0とする。このN次元2値ベクトルxによって仮説Σを表現することで、仮説Σの集合は論理関数として表現できる。すなわち、仮説Σを表す2値ベクトルxが帰納論理プログラミングの問題の解である場合はf(x)=1、解でない場合はf(x)=0となるような論理関数fは、全ての解の集合を表現していると見做すことができる。

【0053】
したがって、この2値ベクトルxを構成する各変数xを、BDDを表現する変数とみれば(すなわち、BDDの各ノードに付与されるi個のラベルがそれぞれ各変数xを表すとすれば)、論理関数fを表現するBDDによって、仮説Σの集合を表現することができる。このとき、BDDの根ノードから第2終端ノードまでに至る経路の各々が、帰納論理プログラミングの問題の解となる仮説を表す。一方で、BDDの根ノードから第1終端ノードまでに至る経路の各々が、帰納論理プログラミングの問題の解とならない仮説を表す。

【0054】
このことは、BDDの各経路に対応する変数の割り当ては、当該経路に対応する仮説の索引と捉えることができることを意味する。

【0055】
すなわち、生成処理部100は、入力された集合ε及びεと背景知識Bとに基づいて、BDD Z(h)を構築する。そして、生成処理部100は、構築したBDD Z(h)を出力する。このZ(h)の根ノードから第2終端ノードまでに至る経路に対応する変数の割り当てが、帰納論理プログラミングの解である仮説Σの索引である。したがって、生成処理部100は、入力された集合ε及びεと背景知識Bとに基づいて、BDD Z(h)を構築することにより、帰納論理プログラミングの解である仮説Σの索引を生成すると言うこともできる。

【0056】
なお、生成処理部100は、帰納論理プログラミングの解である仮説Σの索引として、構築したBDD Z(h)を出力しても良いし、このBDD Z(h)の根ノードから第2終端ノードまでに至る経路に対応する変数の割り当ての集合を出力しても良い。

【0057】
ここで、生成処理部100には、第1仮説集合生成部101と、第2仮説集合生成部102と、第3仮説集合生成部103とが含まれる。

【0058】
第1仮説集合生成部101は、背景知識Bと、訓練例の集合εと、集合Pとを入力して、全ての基礎原子論理式E∈εについて、上記の式1を満たす仮説Σの集合に対応する論理関数を表現するBDDを構築する。すなわち、εに基礎原子論理式がM個含まれるとした場合、i(i=1,・・・,M)毎に、第1仮説集合生成部101は、i番目の基礎原子論理式Eに対して、

【0059】
【数10】
JP2019153047A_000012t.gif
となるような仮説Σの集合を表現する論理関数fを表すBDD Z(f)を構築する。BDDの構築方法については後述する。なお、εに含まれる訓練例は全て基礎単位節であることから、これらは全て基礎原子論理式である。

【0060】
第2仮説集合生成部102は、背景知識Bと、訓練例の集合εと、集合Pとを入力して、全ての原子論理式E∈εについて、上記の式1を満たす仮説Σの集合に対応する論理関数を表現するBDDを構築する。すなわち、εに基礎原子論理式がK個含まれるとした場合、i(i=1,・・・,K)毎に、第2仮説集合生成部102は、i番目の基礎原子論理式Eに対して、

【0061】
【数11】
JP2019153047A_000013t.gif
となるような仮説Σの集合を表現する論理関数gを表すBDD Z(g)を構築する。BDDの構築方法については後述する。なお、εに含まれる訓練例は全て基礎単位節であることから、これらは全て基礎原子論理式である。

【0062】
ここで、上記では、負例である訓練例E∈εに対しても上記の式1を満たすΣの集合に対応する論理関数gを表すBDD Z(g)を構築した。これは、後述する式3において、各論理関数gに対して否定を示す論理記号(¬)を付与するためである。ただし、後述する式3において、各論理関数gに対して否定を示す論理記号(¬)を付与しない場合には、第2仮説集合生成部102は、上記の式2を満たす仮説Σの集合に対応する論理関数を表現するBDDを構築しても良い。

【0063】
第3仮説集合生成部103は、第1仮説集合生成部101で構築したZ(f)と、第2仮説集合生成部102で構築したZ(g)とを入力して、これらのBDDのApply演算を行うことにより、以下の式3に示す論理式hを表すBDD Z(h)を構築する。

【0064】
【数12】
JP2019153047A_000014t.gif
≪処理の流れ≫
次に、本発明の実施の形態における生成処理部100が実行する処理の流れについて、図3を参照しながら説明する。図3は、本発明の実施の形態における生成処理部100が実行する処理の流れの一例を示すフローチャートである。なお、以降では、背景知識Bと、訓練例の集合ε及びεと、集合Pとが生成処理部100に入力されたものとする。

【0065】
ステップS101:生成処理部100の第1仮説集合生成部101は、背景知識Bと、正例の訓練例の集合εと、集合Pとを入力して、i=1,・・・,Mに対して、上述したZ(f)を構築する。

【0066】
ここで、BBD Z(f)の構築方法について説明する。以降では、fの添字iを固定して、単に「f」と表し、Z(f)の構築方法について説明する。

【0067】
或る基礎原子論理式Eを論理的帰結とするような仮説の集合を表現する論理関数を[E]とする。また、集合Pに含まれる各縮小確定節に対して添字i(i=1,・・・,N)が付与されているものとして、集合Pに含まれる各縮小確定節A←B,・・・,Bのうち、或る代入θに対してE=Aθを満たすような縮小確定節の添字の集合をJとする。すると、[E]は、

【0068】
【数13】
JP2019153047A_000015t.gif
となる。ここで、θはi番目の縮小確定節に対してE=Aθとなるような代入を表す。このような代入は各縮小確定節に対して一意に決定される。また、nはi番目の縮小確定節を表す原子論理式B,・・・,Bの数である。i番目の縮小確定節は、原子論理式A,B,・・・,Bniを用いて、A←B,・・・,Bniと表される(ただし、「ni」は、実際には「i」を下付きで表した「n」である。)。

【0069】
上記の式4は、論理関数[E]が論理関数[Bθ]により再帰的に求められることを表している。縮小確定節の性質により、Bθは常に基礎原子論理式となり、かつ、その大きさ|Bθ|は常に|E|より小さくなる。他方で、背景知識Bと、正例の集合εと、集合Pとはいずれも有限集合であるため、これらの集合に含まれる関数記号、定数記号、述語記号も有限である。このため、これらの関数記号、定数記号、述語記号によって構成される基礎原子論理式のうち、εに含まれる最大の基礎原子論理式よりも小さいものの集合も常に有限となる。このような大きさが或る値以下の各基礎原子論理式Eについて、論理関数[E]を表すBDDを、上記の式4により再帰的にApply演算を実行して構築していくことによって、εに含まれる各原子論理式Eについて論理関数f=[E]を表すBDD Z(f)を構築することができる。

【0070】
ステップS102:生成処理部100の第2仮説集合生成部102は、背景知識Bと、負例の訓練例の集合εと、集合Pとを入力して、i=1,・・・,Kに対して、上述したZ(g)を構築する。

【0071】
ここで、BBD Z(g)の構築方法について説明する。以降では、gの添字iを固定して、単に「g」と表し、Z(g)の構築方法について説明する。なお、Z(g)の構築方法は、上述したZ(f)の構築方法と同様であるため、簡略化して説明する。

【0072】
或る基礎原子論理式Eを論理的帰結とするような仮説の集合を表現する論理関数を[E]とする。また、集合Pに含まれる各縮小確定節A←B,・・・,Bのうち、或る代入θに対してE=Aθを満たすような縮小確定節の添字の集合をJとする。すると、[E]は、上記の式4となる。

【0073】
また、負例の集合εも有限集合であるため、背景知識B、負例の集合ε及び集合Pに含まれる関数記号、定数記号、述語記号によって構成される基礎原子論理式のうち、εに含まれる最大の基礎原子論理式よりも小さいものの集合も常に有限となる。したがって、このような大きさが或る値以下の各基礎原子論理式Eについて、論理関数[E]を表すBDDを、上記の式4により再帰的にApply演算を実行して構築していくことによって、εに含まれる各原子論理式Eについて論理関数g=[E]を表すBDD Z(g)を構築することができる。

【0074】
ステップS103:生成処理部100の第3仮説集合生成部103は、第1仮説集合生成部101で構築したZ(f)と、第2仮説集合生成部102で構築したZ(g)とを入力して、これらのBDDのApply演算を行うことにより、上記の式3に示す論理式hを表すBDD Z(h)を構築する。

【0075】
これにより、生成処理部100により、帰納論理プログラミングの解である仮説Σの索引として、Z(h)又は当該Z(h)の根ノードから第2終端ノードまでに至る経路に対応する変数の割り当ての集合が出力される。

【0076】
以上のように、本発明の実施の形態における生成装置10では、帰納論理プログラミングの解である仮説Σの索引の集合を、BDD又は当該BDDの根ノードから第2終端ノードまでに至る経路に対応する変数の割り当ての集合として出力することができる。このため、本発明の実施の形態における生成装置10によれば、膨大な数になる可能性がある帰納論理プログラミングの解の集合をBDDとして圧縮・索引化して全列挙することができるようになる。このように全ての解の集合をBDDとして索引化して表現することで、例えば、これらの解の中から所望の条件を満たす解を選び出して利用する等といった事も容易に行うことができるようになる。

【0077】
≪ハードウェア構成≫
最後に、本発明の実施の形態における生成装置10のハードウェア構成について、図4を参照しながら説明する。図4は、本発明の実施の形態における生成装置10のハードウェア構成の一例を示す図である。

【0078】
図4に示すように、本発明の実施の形態における生成装置10は、入力装置201と、表示装置202と、外部I/F203と、RAM(Random Access Memory)204と、ROM(Read Only Memory)205と、CPU206と、通信I/F207と、補助記憶装置208とを有する。これら各ハードウェアは、それぞれがバスBを介して通信可能に接続されている。

【0079】
入力装置201は、例えばキーボードやマウス、タッチパネル等であり、ユーザが各種操作を入力するのに用いられる。表示装置202は、例えばディスプレイ等であり、生成装置10の処理結果を表示する。なお、生成装置10は、入力装置201及び表示装置202の少なくとも一方を有していなくても良い。

【0080】
外部I/F203は、外部装置とのインタフェースである。外部装置には、記録媒体203a等がある。生成装置10は、外部I/F203を介して、記録媒体203a等の読み取りや書き込みを行うことができる。記録媒体203aには、生成装置10が有する各機能を実現するプログラム等が記録されていても良い。

【0081】
記録媒体203aには、例えば、フレキシブルディスク、CD(Compact Disc)、DVD(Digital Versatile Disk)、SDメモリカード(Secure Digital memory card)、USB(Universal Serial Bus)メモリカード等がある。

【0082】
RAM204は、プログラムやデータを一時保持する揮発性の半導体メモリである。ROM205は、電源を切ってもプログラムやデータを保持することができる不揮発性の半導体メモリである。ROM205には、例えば、OS(Operating System)設定やネットワーク設定等が格納されている。

【0083】
CPU206は、ROM205や補助記憶装置208等からプログラムやデータをRAM204上に読み出して処理を実行する演算装置である。

【0084】
通信I/F207は、生成装置10を通信ネットワークに接続するためのインタフェースである。生成装置10が有する各機能を実現するプログラムは、通信I/F207を介して、所定のサーバ装置等から取得(ダウンロード)されても良い。

【0085】
補助記憶装置208は、例えばHDD(Hard Disk Drive)やSSD(Solid State Drive)等であり、プログラムやデータを格納している不揮発性の記憶装置である。補助記憶装置208に格納されているプログラムやデータには、例えば、OS、当該OS上において各種機能を実現するアプリケーションプログラム、生成装置10が有する各機能を実現するプログラム等がある。

【0086】
本発明の実施の形態における生成装置10は、図4に示すハードウェア構成を有することにより、上述した各種処理を実現することができる。なお、図4では、本発明の実施の形態における生成装置10が1台の装置で実現される場合について説明したが、これ限られない。本発明の実施の形態における生成装置10は、複数台の装置で実現されていても良い。

【0087】
本発明は、具体的に開示された上記の実施形態に限定されるものではなく、特許請求の範囲から逸脱することなく、種々の変形や変更が可能である。
【符号の説明】
【0088】
10 生成装置
101 第1仮説集合生成部
102 第2仮説集合生成部
103 第3仮説集合生成部
図面
【図1】
0
【図2】
1
【図3】
2
【図4】
3