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