(57)【特許請求の範囲】
【請求項１】
訓練例入力手段、及びパラメータ推定手段を含み、確率パラメータが付与された事実を表す節の集合と、前記確率パラメータが付与されていない節の集合とを含む確率論理プログラムであって、かつ、質問として与えられた事実を論理的帰結として導出することができる確率を算出する確率論理プログラムで用いられる前記確率パラメータの各々の値を推定するパラメータ推定装置におけるパラメータ推定方法であって、
前記訓練例入力手段が、前記確率論理プログラムの論理的帰結として導出されるべき事実の集合と、論理的帰結として導出されるべきではない事実の集合とからなる予め用意された複数の訓練例を受け付けるステップと、
前記パラメータ推定手段が、前記訓練例入力手段によって受け付けた複数の訓練例と、前記確率論理プログラムとに基づいて、値が１又は０である前記確率パラメータの数が多いほど小さい値を出力するように予め定められたペナルティ関数により求まる項と、前記確率パラメータの各々の値の尤もらしさを表す負の対数尤度関数により求まる項との重み付け和である目的関数を、前記複数の訓練例に対して最小化するように、前記確率論理プログラムの前記確率パラメータの各々の値を推定し、推定された前記確率パラメータの値が１である事実を表す節から、前記確率パラメータを取り除いて、前記確率パラメータが付与されていない節とし、推定された前記確率パラメータの値が０である事実を表す節を、前記確率論理プログラムから取り除くステップと、
を含み、
前記ペナルティ関数は、前記確率パラメータが付与された事実を表す節の頭部の項ｔｉの集合のうち、前記項ｔｉを本体部に含む全ての節に対し、前記本体部に前記項ｔｉ以外の項が存在している前記項ｔｉの各々に付与されている前記確率パラメータであって、値が１である前記確率パラメータの数が多いほど小さい値を出力するように定められている
パラメータ推定方法。
【請求項２】
前記ペナルティ関数は、前記確率パラメータが付与された事実を表す節の頭部の項ｔｉの集合のうち、前記項ｔｉを本体部に含む全ての節に対し、前記節と頭部が等しく、かつ、前記項ｔｉを含まない節が存在している前記項ｔｉの各々に付与されている前記確率パラメータであって、値が０である前記確率パラメータの数が多いほど小さい値を出力するように定められている請求項１記載のパラメータ推定方法。
【請求項３】
前記パラメータ推定手段によるステップは、前記確率パラメータの各々の初期値、又は前回更新された前記確率パラメータの各々の値に基づいて、前記目的関数の勾配を計算し、計算された前記目的関数の勾配に基づいて、前記確率パラメータの各々の値を更新することを、予め定められた繰り返し終了条件を満たすまで繰り返すことにより、前記確率論理プログラムの前記確率パラメータの各々の値を推定する請求項１又は２記載のパラメータ推定方法。
【請求項４】
前記負の対数尤度関数は、前記複数の訓練例の各々に対する、前記確率論理プログラムにおける前記訓練例の出現確率を用いて表される請求項１〜請求項３の何れか１項記載のパラメータ推定方法。
【請求項５】
確率パラメータが付与された事実を表す節の集合と、前記確率パラメータが付与されていない節の集合とを含む確率論理プログラムであって、かつ、質問として与えられた事実を論理的帰結として導出することができる確率を算出する確率論理プログラムで用いられる前記確率パラメータの各々の値を推定するパラメータ推定装置であって、
前記確率論理プログラムの論理的帰結として導出されるべき事実の集合と、論理的帰結として導出されるべきではない事実の集合とからなる予め用意された複数の訓練例を受け付ける訓練例入力手段と、
前記訓練例入力手段によって受け付けた複数の訓練例と、前記確率論理プログラムとに基づいて、値が１又は０である前記確率パラメータの数が多いほど小さい値を出力するように予め定められたペナルティ関数により求まる項と、前記確率パラメータの各々の値の尤もらしさを表す負の対数尤度関数により求まる項との重み付け和である目的関数を、前記複数の訓練例に対して最小化するように、前記確率論理プログラムの前記確率パラメータの各々の値を推定し、推定された前記確率パラメータの値が１である事実を表す節から、前記確率パラメータを取り除いて、前記確率パラメータが付与されていない節とし、推定された前記確率パラメータの値が０である事実を表す節を、前記確率論理プログラムから取り除くパラメータ推定手段と、
を含み、
前記ペナルティ関数は、前記確率パラメータが付与された事実を表す節の頭部の項ｔｉの集合のうち、前記項ｔｉを本体部に含む全ての節に対し、前記本体部に前記項ｔｉ以外の項が存在している前記項ｔｉの各々に付与されている前記確率パラメータであって、値が１である前記確率パラメータの数が多いほど小さい値を出力するように定められている
パラメータ推定装置。
【請求項６】
前記ペナルティ関数は、前記確率パラメータが付与された事実を表す節の頭部の項ｔｉの集合のうち、前記項ｔｉを本体部に含む全ての節に対し、前記節と頭部が等しく、かつ、前記項ｔｉを含まない節が存在している前記項ｔｉの各々に付与されている前記確率パラメータであって、値が０である前記確率パラメータの数が多いほど小さい値を出力するように定められている請求項５記載のパラメータ推定装置。
【請求項７】
請求項１〜請求項４の何れか１項記載のパラメータ推定方法の各ステップをコンピュータに実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、パラメータ推定方法、装置、及びプログラムに係り、特に、確率論理プログラムで用いられる確率パラメータの各々の値を推定するパラメータ推定方法、装置、及びプログラムに関する。
【背景技術】
【０００２】
論理プログラムは一階述語論理の節の集まりによって、対象領域における関係性を表現するものである。例えば、
【０００３】
mother(X,Y):- parent(X,Y),female(X).
female(hanako).
parent(hanako,taro).
【０００４】
は３つの節からなる論理プログラムである。X,Yは変数、hanako,taroは定数、mother,parent,femaleは述語記号である。
【０００５】
また、Ａ:−Ｂ１,...,ＢＮの形の節のうち、Ａを頭部、Ｂ１,...,ＢＮを本体部とよぶ。上記の論理プログラムは、ある事象間の論理的な関係を定めている。
【０００６】
確率論理プログラムは論理プログラムの拡張であり、論理プログラムが確率を扱えるようにしたものである。通常の論理プログラムの枠組みにおいては、ある論理プログラムΓとある質問ｑが与えられたとき、節の集合からその質問を論理的帰結として導き出せるかどうかを判断するしかできなかった。すなわち、例えば３０％の確率でｑを導き出すことができるといったような、不確実性を含む関係を表現することができなかった。確率論理プログラムは確率分布を用いることによって、ある質問ｑをプログラムが導出できる確率
【０００７】
【数１】
0006452580.tif 000002
【０００８】
を定義することができるようになる。そのため、確率論理プログラムを用いることでより柔軟に対象領域の関係を記述することが可能となる。
【０００９】
mother(X, Y) :- parent(X, Y), female(X).
0.3::female(hanako).
0.5::parent(hanako, taro).
【００１０】
上記は確率論理プログラムの例である。なお、確率論理プログラムにはいくつかの変種があるが、以下ではその一種であるＰｒｏｂＬｏｇ（例えば、非特許文献１を参照）に基づいて説明を進める。通常の論理プログラムとの違いは、節female(hanako)., parent(taro).に数値が付与されていることである。この数値は該当の節が論理プログラムに含まれる確率を表すパラメータである。
【００１１】
例えば0.3::female(hanako).は、節female(hanako)が0.3の確率で論理プログラムに含まれることを意味している。確率論理プログラムでは、このように一部の節に［０，１］の間でパラメータを付与することによって、確率分布Ｐ（ｑ）を定義する。例えば上記のプログラムでは、
【００１２】
【数２】
0006452580.tif 000003
【００１３】
となる。
【００１４】
確率論理プログラムのパラメータが未知のときに、訓練データを入力として与え、訓練データに対する負の対数尤度を最小化するようなパラメータを求める、パラメータ推定手法が提案されている。すなわち、ｗｉ∈［０，１］を論理プログラムに含まれるｉ番目の確率の付与された節に対応するパラメータ、すべてのパラメータの集合をｗ＝｛ｗ１,...,ｗｎ｝とすると、論理プログラム、訓練データを入力として受け取り、訓練データに対する負の対数尤度を最小化するようなパラメータの集合＾ｗ＝｛＾ｗ１,...,＾ｗｎ｝を求める既存手法が提案されている。例えば、非特許文献２では、Expectation-Maximizationアルゴリズムを用いることでパラメータを推定する方法が提案されている。この手法を用いることによって、推定されるパラメータｗｉの多くを０または１をとるように設定することができる。値が０または１のパラメータをもつ確率つき節は、論理プログラムから削除することができるため、結果としてよりパラメータ数が少なく、そのプログラムを用いた推論が容易であるような確率論理プログラムを得ることができる。
【先行技術文献】
【非特許文献】
【００１５】
【非特許文献１】Luc De Raedt, Angelika Kimmig, and Hannu Toivonen.,"Problog: A probabilistic prolog and its application in link discovery.", In IJCAI, p.2462-2467, 2007.
【非特許文献２】Bernd Gutmann, Ingo Thon, and Luc De Raedt. "Learning the parameters of probabilistic logic programs from interpretations. ", In ECML/PKDD, p.581-596,2011.
【発明の概要】
【発明が解決しようとする課題】
【００１６】
上記の既存のペナルティ項の付与に基づいた確率論理プログラムのパラメータ推定手法では、プログラムに含まれる各パラメータに対して同一のペナルティ項を設定し、すべてのパラメータｗｉが均一に０または１になりやすいように設定していた。しかし、パラメータの中にはそれが０または１になると、他に与える影響が大きなものも存在する。例えば上記の確率論理プログラムの例において、確率つき事実female(hanako).の確率を０．０と設定したとすると、mother(hanako,X).の確率は、他のパラメータの値によらず常に０になる。これは、female(hanako).の確率を０．０とすることが、プログラムが確率を与えることができる事象の種類を減らすことに対応することを表している。既存のペナルティ項を利用した手法では、パラメータによらず均一にペナルティ項を設定するため、このようなプログラムが得られやすくなるという課題があった。
【００１７】
本発明では、上記の事情に鑑みてなされたものであり、確率論理プログラムで用いられる確率パラメータの数を適切に削減することができるパラメータ推定方法、装置、及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１８】
上記目的を達成するために、本発明に係るパラメータ推定方法は、訓練例入力手段、及びパラメータ推定手段を含み、確率パラメータが付与された事実を表す節の集合と、前記確率パラメータが付与されていない節の集合とを含む確率論理プログラムであって、かつ、質問として与えられた事実を論理的帰結として導出することができる確率を算出する確率論理プログラムで用いられる前記確率パラメータの各々の値を推定するパラメータ推定装置におけるパラメータ推定方法であって、前記訓練例入力手段が、前記確率論理プログラムの論理的帰結として導出されるべき事実の集合と、論理的帰結として導出されるべきではない事実の集合とからなる予め用意された複数の訓練例を受け付けるステップと、前記パラメータ推定手段が、前記訓練例入力手段によって受け付けた複数の訓練例と、前記確率論理プログラムとに基づいて、値が１又は０である前記確率パラメータの数が多いほど小さい値を出力するように予め定められたペナルティ関数と、前記確率パラメータの各々の値の尤もらしさを表す負の対数尤度関数との重み付け和である目的関数を、前記複数の訓練例に対して最小化するように、前記確率論理プログラムの前記確率パラメータの各々の値を推定し、推定された前記確率パラメータの値が１である事実を表す節から、前記確率パラメータを取り除いて、前記確率パラメータが付与されていない節とし、推定された前記確率パラメータの値が０である事実を表す節を、前記確率論理プログラムから取り除くステップと、を含み、前記ペナルティ関数は、前記確率パラメータが付与された事実を表す節の頭部の項ｔｉの集合のうち、前記項ｔｉを本体部に含む全ての節に対し、前記本体部に前記項ｔｉ以外の項が存在している前記項ｔｉの各々に付与されている前記確率パラメータであって、値が１である前記確率パラメータの数が多いほど小さい値を出力するように定められている。
【００１９】
本発明に係るパラメータ推定装置は、確率パラメータが付与された事実を表す節の集合と、前記確率パラメータが付与されていない節の集合とを含む確率論理プログラムであって、かつ、質問として与えられた事実を論理的帰結として導出することができる確率を算出する確率論理プログラムで用いられる前記確率パラメータの各々の値を推定するパラメータ推定装置であって、前記確率論理プログラムの論理的帰結として導出されるべき事実の集合と、論理的帰結として導出されるべきではない事実の集合とからなる予め用意された複数の訓練例を受け付ける訓練例入力手段と、前記訓練例入力手段によって受け付けた複数の訓練例と、前記確率論理プログラムとに基づいて、値が１又は０である前記確率パラメータの数が多いほど小さい値を出力するように予め定められたペナルティ関数と、前記確率パラメータの各々の値の尤もらしさを表す負の対数尤度関数との重み付け和である目的関数を、前記複数の訓練例に対して最小化するように、前記確率論理プログラムの前記確率パラメータの各々の値を推定し、推定された前記確率パラメータの値が１である事実を表す節から、前記確率パラメータを取り除いて、前記確率パラメータが付与されていない節とし、推定された前記確率パラメータの値が０である事実を表す節を、前記確率論理プログラムから取り除くパラメータ推定手段と、を含み、前記ペナルティ関数は、前記確率パラメータが付与された事実を表す節の頭部の項ｔｉの集合のうち、前記項ｔｉを本体部に含む全ての節に対し、前記本体部に前記項ｔｉ以外の項が存在している前記項ｔｉの各々に付与されている前記確率パラメータであって、値が１である前記確率パラメータの数が多いほど小さい値を出力するように定められている。
【００２０】
本発明に係る前記ペナルティ関数は、前記確率パラメータが付与された事実を表す節の頭部の項ｔｉの集合のうち、前記項ｔｉを本体部に含む全ての節に対し、前記節と頭部が等しく、かつ、前記項ｔｉを含まない節が存在している前記項ｔｉの各々に付与されている前記確率パラメータであって、値が０である前記確率パラメータの数が多いほど小さい値を出力するように定められているようにしてもよい。
【００２１】
本発明に係る前記パラメータ推定手段は、前記確率パラメータの各々の初期値、又は前回更新された前記確率パラメータの各々の値に基づいて、前記目的関数の勾配を計算し、計算された前記目的関数の勾配に基づいて、前記確率パラメータの各々の値を更新することを、予め定められた繰り返し終了条件を満たすまで繰り返すことにより、前記確率論理プログラムの前記確率パラメータの各々の値を推定するようにすることができる。
【００２２】
本発明の前記負の対数尤度関数は、前記複数の訓練例の各々に対する、前記確率論理プログラムにおける前記訓練例の出現確率を用いて表されるようにすることができる。
【００２３】
また、本発明のプログラムは、本発明のパラメータ推定方法の各ステップをコンピュータに実行させるためのプログラムである。
【発明の効果】
【００２４】
以上説明したように、本発明のパラメータ推定方法、装置、及びプログラムによれば、複数の訓練例と、確率論理プログラムとに基づいて、値が１又は０である確率パラメータの数が多いほど小さい値を出力するように予め定められたペナルティ関数と、確率パラメータの各々の値の尤もらしさを表す負の対数尤度関数との重み付け和である目的関数を、複数の訓練例に対して最小化するように、確率論理プログラムの確率パラメータの各々の値を推定し、推定された確率パラメータの値が１である事実を表す節から、確率パラメータを取り除いて、確率パラメータが付与されていない節とし、推定された確率パラメータの値が０である事実を表す節を、確率論理プログラムから取り除く際に、確率パラメータが付与された事実を表す節の頭部の項ｔｉの集合のうち、項ｔｉを本体部に含む節に対し、本体部に項ｔｉ以外の項が存在している項ｔｉの各々に付与されている確率パラメータであって、値が１である確率パラメータの数が多いほど小さい値を出力するようにペナルティ関数を定めることにより、事実の確率の影響を考慮しつつ、確率論理プログラムで用いられる確率パラメータの数を適切に削減することができる、という効果が得られる。
【図面の簡単な説明】
【００２５】
【図１】本発明の実施の形態に係るパラメータ推定装置の機能的構成を示すブロック図である。
【図２】ペナルティ関数の一例を示す図である。
【図３】本発明の実施の形態に係るパラメータ推定装置における推定処理ルーチンを示すフローチャート図である。
【図４】本発明の実施の形態に係るパラメータ推定装置におけるパラメータ推定処理ルーチンを示すフローチャート図である。
【発明を実施するための形態】
【００２６】
＜本発明の実施の形態の概要＞
まず、本発明の実施の形態の概要について説明する。本発明の実施の形態では、確率パラメータを付与した論理プログラム（以下、確率論理プログラムと称する。）の確率パラメータを、入力された訓練例より推定する。具体的には、本発明の実施の形態では、負の対数尤度関数を最小化する代わりに、負の対数尤度関数にペナルティ関数を付与した目的関数を最小化することで確率パラメータの推定を行う。推定された確率パラメータの値ｗｉが０または１をとったときにペナルティの値が小さくなるようなペナルティ関数を用いることで、推定された確率パラメータがよりｗｉ＝０またはｗｉ＝１となりやすいようにする。ここで、本発明の実施の形態では、確率論理プログラムのパラメータ推定を行う際に用いるペナルティ関数を、入力として与えられた確率論理プログラムのひな形における構造を利用して設定する。
【００２７】
そして、推定された確率パラメータがｗｉ＝０となった節を確率論理プログラムから取り除き、ｗｉ＝１となった節を、確率が付与されていない通常の節に変換することで、より確率パラメータの数が少ない確率論理プログラムを得ることができる。
【００２８】
以下、図面を参照して本発明の実施の形態を詳細に説明する。
【００２９】
＜パラメータ推定装置の構成＞
本発明の実施の形態に係るパラメータ推定装置の構成について説明する。本発明の実施の形態に係るパラメータ推定装置１００は、確率パラメータが付与された事実を表す節の集合と、確率パラメータが付与されていない節の集合とを含む確率論理プログラムであって、かつ、質問として与えられた事実を論理的帰結として導出することができる確率を算出する確率論理プログラムで用いられる確率パラメータの各々の値を推定する。
【００３０】
本発明の実施の形態に係るパラメータ推定装置１００は、ＣＰＵ（Central Processing Unit）と、ＣＰＵが後述する各処理ルーチンを実行するためのプログラム等を記憶したＲＯＭ（Read Only Memory）と、ＲＡＭ（Random Access Memory）と、を備えたコンピュータで構成することができる。このパラメータ推定装置１００は、機能的には図１に示すようにプログラム入力部１０と、訓練例入力部１２と、演算部２０と、出力部３０とを備えている。
【００３１】
プログラム入力部１０は、確率論理プログラムを受け付ける。具体的には、プログラム入力部１０は、確率パラメータを推定する対象となる確率論理プログラムのひな形の入力を受け付ける。ここで、ひな形とは、いくつかの節の確率パラメータの値が未定義であるような確率論理プログラムのことをいう。例えば、
【００３２】
mother(X, Y):- parent(X, Y), female(X).
w１::female(hanako).
w２::parent(hanako, taro).
【００３３】
は、２つの確率パラメータつき節の値が定まっていない、ひな形である。
【００３４】
訓練例入力部１２は、確率論理プログラムの論理的帰結として導出されるべき事実の集合と、論理的帰結として導出されるべきではない事実の集合とを含む予め用意された訓練例を複数受け付ける。訓練例は、確率論理プログラムのひな形のパラメータが正しく推定されたときに、生成されると考えられる事実の集合である。以下では、訓練例の集合をＤ＝｛Ｉ１,Ｉ２,...,Ｉｍ｝と表現する。各Ｉｉは一つの訓練例であり、訓練例Ｉｉは、Ｉｉ＝（Ｉ＋ｉ，Ｉ−ｉ）というペアから構成されるとする。Ｉ＋ｉは対象の確率論理プログラムから論理的帰結として導出される事実の集合、Ｉ−ｉは導出されなかった事実の集合である。上記の確率論理プログラムでは、例えば
【００３５】
Ｉ＋ｉ＝｛parent(hanako, taro)｝, Ｉ−ｉ＝｛female(hanako), mother(hanako, taro)｝
【００３６】
などが訓練例となり、これは推定された確率論理プログラムから、parent（hanako, taro）を論理的帰結として導出できるが、female(hanako)とmother(hanako, taro)を導出できないような例が生成されることがあるということを表している。
【００３７】
演算部２０は、プログラムデータベース２２と、訓練例データベース２４と、ペナルティ決定部２５と、パラメータ推定部２６とを備えている。
【００３８】
プログラムデータベース２２には、プログラム入力部１０によって受け付けた確率論理プログラムと、後述する代入の集合ＬＴ’とが格納される。
【００３９】
訓練例データベース２４には、訓練例入力部１２によって受け付けた複数の訓練例が格納される。
【００４０】
ペナルティ決定部２５は、訓練例データベース２４に格納された複数の訓練例に基づいて、確率つき節の頭部の項の集合をＨとして、Ｈの部分集合Ｓ０及びＳ１を以下のように定義する。まずＳ０は、項ｔｉ∈Ｈのうち、項ｔｉを本体部に含む全ての節について、その節と頭部が等しく、かつ項ｔｉを含まない節が存在しているものの集合と決定する。同様に、Ｓ１は、項ｔｉ∈Ｈのうち、項ｔｉを本体部に含む全ての節について、本体部にｔｉ以外の項が含まれているものの集合と決定する。ペナルティ決定部２５は、ここで定義したＳ０及びＳ１を用いて、以下の式に示すように、ペナルティ関数ｈ（ｗ）を決定する。これにより、事実の確率の影響を考慮しつつ、パラメータ推定を行うことができる。
【００４１】
【数３】
0006452580.tif 000004
【００４２】
上記（１）式のペナルティ関数は、右辺の二番目の項によって、確率パラメータが付与された事実を表す節の頭部の項ｔｉの集合のうち、項ｔｉを本体部に含む全ての節に対し、本体部に項ｔｉ以外の項が存在している項ｔｉの各々に付与されている確率パラメータであって、値が１である確率パラメータの数が多いほど小さい値を出力するように定められている。
【００４３】
また、上記（１）式のペナルティ関数は、右辺の一番目の項によって、確率パラメータが付与された事実を表す節の頭部の項ｔｉの集合のうち、項ｔｉを本体部に含む全ての節に対し、節と頭部が等しく、かつ、項ｔｉを含まない節が存在している項ｔｉの各々に付与されている確率パラメータであって、値が０である確率パラメータの数が多いほど小さい値を出力するように定められている。
【００４４】
パラメータ推定部２６は、訓練例データベース２４に格納された複数の訓練例と、プログラムデータベース２２に格納された確率論理プログラムとに基づいて、ペナルティ決定部２５により決定されたペナルティ関数と、確率パラメータの各々の値の尤もらしさを表す負の対数尤度関数との重み付け和である目的関数を、複数の訓練例に対して最小化するように、確率論理プログラムの確率パラメータの各々の値を推定する。ペナルティ関数は、後述するように、値が１又は０である確率パラメータの数が多いほど小さい値を出力するように予め定められる。
【００４５】
そして、パラメータ推定部２６は、推定された確率パラメータの値が１である事実を表す節から、確率パラメータを取り除いて、確率パラメータが付与されていない節とし、推定された確率パラメータの値が０である事実を表す節を、確率論理プログラムから取り除く。
【００４６】
パラメータ推定部２６の具体的な処理の内容を説明するために、はじめに、以下で用いる記法および確率論理プログラムについて説明する。
【００４７】
まず、一階述語論理の節の集合である確率論理プログラムをＴ’とする。さらにＴ’に含まれる節を、確率パラメータが付与された事実の集合Ｆと、確率パラメータが付与されていない節の集合ＫＢとに分ける。すなわち、Ｔ’＝Ｆ∪ＫＢかつＦ∩ＫＢ＝Oである。上述の例では、Ｆ＝｛female(hanako)., parent(hanako, taro).｝, ＫＢ＝｛mother(X,Y):-parent(X,Y) ，female(X).｝である。以下ではＦに含まれている事実の集合をｆ１,...,ｆｎとし、それぞれの事実に対応する確率パラメータの各々をｗ１,...,ｗｎとする。
【００４８】
次に、Ｆに含まれる事実ｆｉ∈Ｆに対する、代入後の項が変数を含まないような全ての代入を考える。定数記号の数が有限であると仮定すると、事実ｆｉに対する全ての代入の集合は
【００４９】
【数４】
0006452580.tif 000005
【００５０】
となる。ここでＫｉはｆｉに対する可能な代入の数である。全ての事実ｆｉ∈Ｆに対する全ての可能な代入の集合の和集合を
【００５１】
【数５】
0006452580.tif 000006
【００５２】
とする。パラメータ推定部２６は、プログラムデータベース２２に格納された確率論理プログラムに基づいて、全ての事実ｆｉ∈Ｆに対する全ての可能な代入の集合の和集合ＬＴ’を生成し、プログラムデータベース２２に格納する。
【００５３】
ここで、ある論理プログラムＴのもとで、質問（リテラル）ｑが論理的帰結として求められることを
【００５４】
【数６】
0006452580.tif 000007
【００５５】
とする。また、ある論理プログラムＴのもとで、論理的帰結として求められないことを
【００５６】
【数７】
0006452580.tif 000008
【００５７】
とする。そして、δ（Ｔ,Ｉｉ）を、すべてのｑ∈Ｉ＋ｉについて
【００５８】
【数８】
0006452580.tif 000009
【００５９】
かつすべてのｑ∈Ｉ−ｉについて
【００６０】
【数９】
0006452580.tif 000010
【００６１】
であるなら、δ（Ｔ，Ｉｉ）＝１、そうでないならばδ（Ｔ，Ｉｉ）＝０であるような関数として定義する。
【００６２】
以上を用いて、確率論理プログラムＴ’のもとでの訓練例Ｉｉの出現確率Ｐ（Ｉｉ｜Ｔ）を
【００６３】
【数１０】
0006452580.tif 000011
【００６４】
として定義する。
【００６５】
次に、パラメータ推定部２６の具体的な処理を説明する。まず、パラメータ推定部２６は、プログラムデータベース２２より、確率論理プログラムのひな形を入力として受け取る。次に、パラメータ推定部２６は、複数の訓練例を訓練例データベース２４より受け取る。ここで、ひな形に含まれる確率パラメータをｗ＝｛ｗ１，ｗ２,...,ｗｎ｝とする。また、訓練例の集合をＤ＝｛Ｉ１，Ｉ２,...,Ｉｍ｝とする。そして、パラメータ推定部２６は、パラメータ推定処理を行う。
【００６６】
パラメータ推定処理において、パラメータ推定部２６は、まず、確率パラメータの初期値を与える。確率パラメータの初期値は各ｉ＝１,...,ｎについて、０＜ｗｉ＜１となるようにｗ(０)を与える。次にパラメータ推定部２６は、現在のｗ（ｋ）を用いて目的関数の勾配を計算する。
【００６７】
目的関数は、負の対数尤度とペナルティ関数の和として表現される。全ての訓練例の集合Ｄ＝｛Ｉ１,...,Ｉｍ｝に対する負の対数尤度関数ｌ(ｗ)は、
【００６８】
【数１１】
0006452580.tif 000012
【００６９】
となる。従って、上記（３）式に示すように、負の対数尤度関数は、複数の訓練例の各々に対する、確率論理プログラムにおける当該訓練例の出現確率を用いて表される。通常のパラメータ推定問題では、この負の対数尤度関数を最小化するような＾ｗ＝（＾ｗ１,..., ＾ｗｎ）を推定する。一方、本発明の実施の形態では、非特許文献３と同様に射影勾配法に基づいた尤度関数とペナルティ項の和の最小化によってパラメータ推定を行う。
【００７０】
負の対数尤度関数とペナルティ関数の重みづけ和
【００７１】
【数１２】
0006452580.tif 000013
【００７２】
を目的関数とする。ここでεはｗｉ＝０またはｗｉ＝１となったときにｈ（ｗ）が未定義とならないためのパラメータであり、０＜ε＜1 とする。λは対数尤度関数とペナルティ関数の影響を調整するパラメータであり、正の実数である。
【００７３】
また、ｗが一次元のベクトル（スカラー）であるときに、ｗの値を０から１まで動かしたときの、上記（１）式の右辺の値の変化の一例を図２に示す。
【００７４】
図２に示すように、上記（１）式の右辺の値はｗが一番目の項において０または二番目の項において１に近づいたときに小さい値をとることが分かる。すなわち、値が１又は０である確率パラメータの数が多いほどペナルティ関数の値は小さくなる。結果としてｇ（ｗ）を最小化するパラメータはペナルティ関数を小さくするようにｗｉ＝０またはｗｉ＝１となりやすくなる。
【００７５】
そして、パラメータ推定部２６は、確率パラメータの各々の初期値、又は前回更新された確率パラメータの各々の値に基づいて、上記（４）式の目的関数の勾配を計算し、計算された目的関数の勾配に基づいて、確率パラメータの各々の値を更新することを、予め定められた繰り返し終了条件を満たすまで繰り返すことにより、確率論理プログラムの確率パラメータの各々の値を推定する。
【００７６】
具体的には、関数ｌ（ｗ）の勾配を∇ｌ（ｗ）、そのｉ番目の成分を［∇ｌ（ｗ）］ｉとすると、
【００７７】
【数１３】
0006452580.tif 000014
【００７８】
となる。ここでＱ（Ｌ，ｉ）は
【００７９】
【数１４】
0006452580.tif 000015
【００８０】
となる。同様に［∇ｈ（ｗ）］ｉは
【００８１】
【数１５】
0006452580.tif 000016
【００８２】
となる。以上よりｇ（ｗ）の勾配は
【００８３】
【数１６】
0006452580.tif 000017
【００８４】
となる。
【００８５】
そして、パラメータ推定部２６は、勾配∇ｇ（ｗ（ｋ））を計算した後、新しい確率パラメータｗ（ｋ＋１）を
【００８６】
【数１７】
0006452580.tif 000018
【００８７】
として更新する。このときのαｋはｗ（ｋ＋１）の更新の際のステップ幅を与えるパラメータであり、例えば参考文献（Dimitri P Bertsekas，“Nonlinear programming.”，1999.）にあるような、Armijo rule 等の手法を用いて定める。
【００８８】
次に、パラメータ推定部２６は、更新された確率パラメータｗ（ｋ＋１）の各成分を、０≦ｗｉ≦１の範囲に収まるように射影する。具体的には、ｗｉ＜０であるならｗｉ＝０とし、ｗｉ＞１であるならｗｉ＝１とする。それ以外のときはｗｉをそのまま用いる。
【００８９】
そして、パラメータ推定部２６は、例えば、ｗ（ｋ＋１）とｗ（ｋ）との差分が小さいことを繰り返し終了条件として、ｗ（ｋ＋１）とｗ（ｋ）との差分を計算し、差分が十分小さいならば、現在のｗ（ｋ＋１）を出力して処理を終了する。差分が十分小さくないならば、パラメータ推定部２６は、現在のｗ（ｋ＋１）をもとにｗ（ｋ＋２）を求める処理を行う。
【００９０】
パラメータ推定部２６は、パラメータ推定処理の終了後、推定結果を出力する。ここで、パラメータ推定部２６は、入力として与えられたひな形に推定された確率パラメータを付与したものを推定結果とする。このとき、あるｗｉがｗｉ＝０であったならば、対応する節を出力する確率論理プログラムから取り除く。また、ｗｉ＝１であったならば、Ｆよりｆｉを取り除き、かつＫＢにｆｉを追加する。こうして得られた確率論理プログラムを出力して処理を終了する。
【００９１】
出力部３０は、パラメータ推定部２６によって出力された確率論理プログラムを出力する。
【００９２】
＜パラメータ推定装置の作用＞
次に、本発明の実施の形態に係るパラメータ推定装置１００の作用について説明する。確率論理プログラムと複数の訓練例とがパラメータ推定装置１００に入力されると、演算部２０によって、図３に示す推定処理ルーチンが実行される。
【００９３】
まず、ステップＳ１００において、プログラム入力部１０によって、入力された確率論理プログラムを受け付け、プログラムデータベース２２に格納する。
【００９４】
次に、ステップＳ１０２において、訓練例入力部１２によって、入力された複数の訓練例を受け付け、訓練例データベース２４に格納する。
【００９５】
次に、ステップＳ１０３において、ペナルティ決定部２５によって、上記ステップＳ１０２で格納した複数の訓練事例に基づいて、確率つき節の頭部の項の集合をＨとして、部分集合Ｓ０及びＳ１を定義し、上記（１）式に従って、ペナルティ関数を決定する。
【００９６】
次に、ステップＳ１０４において、パラメータ推定部２６によって、上記ステップＳ１００でプログラムデータベース２２に格納された確率論理プログラムに基づいて、全ての事実ｆｉ∈Ｆに対する全ての可能な代入の集合の和集合ＬＴ’を生成し、プログラムデータベース２２に格納する。
【００９７】
次に、ステップＳ１０６において、パラメータ推定部２６によって、ステップＳ１０３で決定されたペナルティ関数を用いて、確率パラメータの各々の値を推定する。ステップＳ１０６は、図４に示すパラメータ推定処理ルーチンによって実現される。
【００９８】
＜パラメータ推定処理ルーチン＞
ステップＳ２００において、パラメータ推定部２６によって、確率パラメータの各々について、０＜ｗｉ＜１となるように当該確率パラメータの初期値ｗ(０）を設定する。
【００９９】
次に、ステップＳ２０１において、繰り返し回数ｋに１を代入する。
【０１００】
次に、ステップＳ２０２において、パラメータ推定部２６によって、上記ステップＳ２００で設定された確率パラメータの各々の初期値、又は前回のステップＳ２０６で更新された確率パラメータの各々の値に基づいて、上記（７）式に示す目的関数の勾配を計算する。
【０１０１】
次に、ステップＳ２０４において、パラメータ推定部２６によって、上記ステップＳ２０２で計算された目的関数の勾配に基づいて、上記（８）式に従って、確率パラメータの各々の値を更新し、メモリ（図示省略）に格納する。
【０１０２】
次に、ステップＳ２０６において、パラメータ推定部２６によって、上記ステップＳ２０４で更新された確率パラメータｗ（ｋ＋１）の各成分を、０≦ｗｉ≦１の範囲に収まるように射影し、メモリ（図示省略）に格納する。具体的には、パラメータ推定部２６は、ｗｉ＜０であるならｗｉ＝０とし、ｗｉ＞１であるならｗｉ＝１とする。それ以外のときはｗｉをそのまま用いる。
【０１０３】
次に、ステップＳ２０８において、予め定められた繰り返し終了条件を満たしたか否かを判定する。具体的には、上記ステップＳ２０６で更新された確率パラメータｗ（ｋ＋１）と、前回のステップＳ２０６で更新された確率パラメータｗ（ｋ）との差分を計算し、ｗ（ｋ＋１）とｗ（ｋ）との差分が十分小さいならば、計算が収束したと判定し、ステップＳ２１０へ進む。一方、差分が十分小さくないならば、ステップＳ２０９でｋをインクリメントして、ステップＳ２０２へ戻る。
【０１０４】
ステップＳ２１０において、パラメータ推定部２６によって、上記ステップＳ２０６でメモリ（図示省略）に格納された確率パラメータの各々に基づいて、ある確率パラメータｗｉがｗｉ＝０であったならば、対応する節を出力する確率論理プログラムから取り除く。また、確率パラメータｗｉ＝１であったならば、Ｆよりｆｉを取り除き、かつＫＢにｆｉを追加し、確率論理プログラムを生成する。
【０１０５】
ステップＳ２１２において、上記ステップＳ２１０で生成された確率論理プログラムを出力して、パラメータ推定処理ルーチンを終了する。
【０１０６】
次に、推定処理ルーチンに戻り、ステップＳ１０８において、出力部３０によって、上記ステップＳ１０６で出力された確率論理プログラムを出力して、推定処理ルーチンを終了する。
【０１０７】
以上説明したように、本発明の実施の形態に係るパラメータ推定装置によれば、複数の訓練例と、確率論理プログラムとに基づいて、値が１又は０である確率パラメータの数が多いほど小さい値を出力するように決定されたペナルティ関数と、確率パラメータの各々の値の尤もらしさを表す負の対数尤度関数との重み付け和である目的関数を、複数の訓練例に対して最小化するように、確率論理プログラムの確率パラメータの各々の値を推定し、推定された確率パラメータの値が１である事実を表す節から、確率パラメータを取り除いて、確率パラメータが付与されていない節とし、推定された確率パラメータの値が０である事実を表す節を、確率論理プログラムから取り除く際に、確率パラメータが付与された事実を表す節の頭部の項ｔｉの集合のうち、項ｔｉを本体部に含む節に対し、本体部に項ｔｉ以外の項が存在している項ｔｉの各々に付与されている確率パラメータであって、値が１である確率パラメータの数が多いほど小さい値を出力するようにペナルティ関数を決定することにより、事実の確率の影響を考慮しつつ、確率論理プログラムで用いられる確率パラメータの数を適切に削減することができる。
【０１０８】
また、訓練例から確率論理プログラムのパラメータを推定する問題において、推定された確率論理プログラムのパラメータ数を少なくすることができる。その結果として、推定された確率論理プログラムを用いて確率推論を行う際の計算回数を削減できるため、計算の高速化に寄与する。
【０１０９】
なお、本発明は、上述した実施形態に限定されるものではなく、この発明の要旨を逸脱しない範囲内で様々な変形や応用が可能である。
【０１１０】
例えば、本実施の形態のパラメータ推定装置１００は、プログラムデータベース２２及び訓練例データベース２４を備えている場合について説明したが、例えばプログラムデータベース２２及び訓練例データベース２４の少なくとも１つがパラメータ推定装置１００の外部装置に設けられ、パラメータ推定装置１００は、外部装置と通信手段を用いて通信することにより、プログラムデータベース２２及び訓練例データベース２４の少なくとも１つを参照するようにしてもよい。
【０１１１】
例えば、上述のパラメータ推定装置は、内部にコンピュータシステムを有しているが、「コンピュータシステム」は、ＷＷＷシステムを利用している場合であれば、ホームページ提供環境（あるいは表示環境）も含むものとする。
【０１１２】
また、本願明細書中において、プログラムが予めインストールされている実施形態として説明したが、当該プログラムを、コンピュータ読み取り可能な記録媒体に格納して提供することも可能である。
【符号の説明】
【０１１３】
１０   プログラム入力部
１２   訓練例入力部
２０   演算部
２２   プログラムデータベース
２４   訓練例データベース
２５   ペナルティ決定部
２６   パラメータ推定部
３０   出力部
１００ パラメータ推定装置
【図１】
0006452580.tif 000019
【図２】
0006452580.tif 000020
【図３】
0006452580.tif 000021
【図４】
0006452580.tif 000022