(57)【要約】【課題】尤度関数から最尤推定値を解析的に求めるのが困難である場合に、数値的に求める際の処理を効率化することを可能とする最尤推定方法を提供する。【解決手段】推定区間の初期値を特定する推定区間初期設定処理Ｓ１０１と、推定区間の最小幅を特定する最小幅初期設定処理Ｓ１０２と、推定区間を区間分割数の小区間に分割する推定区間分割処理Ｓ１０３と、小区間の幅が最小幅よりも小さいか否かを判定する判定処理Ｓ１０４と、小区間の幅が最小幅以上である場合に、小区間内でのパラメータの代表値における尤度を尤度計算方法によって計算する尤度計算処理Ｓ１０５と、前記尤度が最大となる前記小区間を選択して、次の前記推定区間として特定する次推定区間選定処理Ｓ１０６と、小区間の幅が最小幅よりも小さくなる場合に、その時点における推定区間でのパラメータの代表値を最尤推定値として出力する最尤推定値出力処理Ｓ１０７とを実行する。【選択図】図１
2010211693.tif 000002
【特許請求の範囲】
【請求項１】
コンピュータシステムによって、対象とする問題領域についての観測データである教師データに基づいて、前記教師データを得られる可能性を示す尤度が最も高くなるパラメータである最尤推定値を推定して出力する最尤推定方法であって、
前記コンピュータシステムは、
前記パラメータが取り得る値の範囲に対して、推定の対象とする区間である推定区間の初期値を前記教師データに基づいて特定する推定区間初期設定処理と、
前記推定区間の推定の終了条件となる前記推定区間の最小幅を前記教師データに基づいて特定する最小幅初期設定処理と、
前記推定区間を予め設定された区間分割数の小区間に分割する推定区間分割処理と、
前記推定区間分割処理での分割後の前記小区間の幅が、前記最小幅初期設定処理で設定された前記推定区間の最小幅よりも小さいか否かを判定する判定処理と、
前記判定処理において前記小区間の幅が前記最小幅以上である場合に、前記小区間毎に、前記小区間内での前記パラメータの代表値における前記尤度を予め設定された尤度計算方法によって計算する尤度計算処理と、
前記小区間毎に前記尤度計算処理によって計算された前記尤度を比較し、前記尤度が最大となる前記小区間を選択して、選択した前記小区間を次の前記推定区間として特定する次推定区間選定処理と、
前記判定処理において前記小区間の幅が前記最小幅より小さくなる場合に、その時点における前記推定区間での前記パラメータの代表値を前記最尤推定値として出力する最尤推定値出力処理とを実行することを特徴とする最尤推定方法。
【請求項２】
請求項１に記載の最尤推定方法において、
前記推定区間初期設定処理では、前記教師データにおける、前記パラメータに対応する指標の値が同じであるにも関わらず観測結果が異なっているデータの中で、前記指標の値が最小のものと最大のものとに基づいて前記推定区間の初期値を特定することを特徴とする最尤推定方法。
【請求項３】
請求項１または２に記載の最尤推定方法において、
前記最小幅初期設定処理では、前記教師データにおける、前記パラメータ対応する指標の精度に基づいて前記推定区間の最小幅を特定することを特徴とする最尤推定方法。
【請求項４】
請求項１〜３のいずれか１項に記載の最尤推定方法において、
前記推定区間もしくは前記小区間での前記パラメータの代表値は、前記推定区間もしくは前記小区間の中央のパラメータ値であることを特徴とする最尤推定方法。
【請求項５】
請求項１〜４のいずれか１項に記載の最尤推定方法において、
対象とする前記問題領域は、データ群に対して前記データを特徴付ける値に基づいて適切な前記データを取捨選択することであり、前記最尤推定値は、前記問題領域において適切な前記データを取捨選択する際の前記データを特徴付ける値の閾値となるものであることを特徴とする最尤推定方法。
【請求項６】
請求項５に記載の最尤推定方法において、
前記尤度は、前記問題領域において取捨選択された前記データの適合率と再現率のいずれか一方、もしくは前記適合率と前記再現率の調和平均であるＦ値とすることを特徴とする最尤推定方法。
【請求項７】
コンピュータシステムを、対象とする問題領域についての観測データである教師データに基づいて、前記教師データを得られる可能性を示す尤度が最も高くなるパラメータである最尤推定値を推定して出力する最尤推定システムとして機能させる最尤推定プログラムであって、
前記パラメータが取り得る値の範囲に対して、推定の対象とする区間である推定区間の初期値を前記教師データに基づいて特定する推定区間初期設定処理と、
前記推定区間の推定の終了条件となる前記推定区間の最小幅を前記教師データに基づいて特定する最小幅初期設定処理と、
前記推定区間を予め設定された区間分割数の小区間に分割する推定区間分割処理と、
前記推定区間分割処理での分割後の前記小区間の幅が、前記最小幅初期設定処理で設定された前記推定区間の最小幅よりも小さいか否かを判定する判定処理と、
前記判定処理において前記小区間の幅が前記最小幅以上である場合に、前記小区間毎に、前記小区間内での前記パラメータの代表値における前記尤度を予め設定された尤度計算方法によって計算する尤度計算処理と、
前記小区間毎に前記尤度計算処理によって計算された前記尤度を比較し、前記尤度が最大となる前記小区間を選択して、選択した前記小区間を次の前記推定区間として特定する次推定区間選定処理と、
前記判定処理において前記小区間の幅が前記最小幅より小さくなる場合に、その時点における前記推定区間での前記パラメータの代表値を前記最尤推定値として出力する最尤推定値出力処理とを実行することを特徴とする最尤推定プログラム。 
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、最尤推定法により問題領域における閾値などのパラメータを決定する技術に関し、特に、尤度関数から尤度最大となるパラメータを解析的に求めることが困難な場合において最尤もしくは準最尤なパラメータを推定する最尤推定方法および最尤推定プログラムに適用して有効な技術に関するものである。
【背景技術】
【０００２】
例えば、いわゆる連想検索を行う検索エンジンなどにおいて、入力されたキーワードに対して関連するキーワードを選択して出力する際に、入力キーワードと関連キーワード候補との類似度を算出し、類似度が所定の閾値以上であるものを関連キーワードとして出力するということが行われる。この閾値をどのような値に設定するかによって出力結果が変わる、すなわち連想検索エンジンの性能が変わることになるが、この閾値を決定する際に用いられる手法として、例えば、最尤推定法がある。
【０００３】
最尤推定法とは、ある問題領域において観測されたサンプルデータの集合に対して、各データの出現があるパラメータのもとでの確率分布に従うものと仮定し、サンプルデータの集合が生じる確率を最大にするパラメータの値を推定するものである。
【０００４】
ここで、上記の関連キーワードの閾値の例では、例えば、サンプルデータの集合を、入力キーワードとこれに対する関連キーワードの候補となる各単語との実際に算出された類似度、および各候補の単語が関連キーワードとして実際に適切（正解）であるか否かの判定結果のデータとする。また、パラメータを、連想検索エンジンにおいて関連キーワードを選択する際の類似度の閾値とする。これにより、適切な関連キーワード（サンプルデータの集合）が得られる確率を最大にする類似度の閾値（パラメータ）を推定することができる。
【０００５】
最尤推定法では一般的に、対象の問題領域において出現するデータについての確率モデルを仮定し、その確率モデルに基づいて、観測結果からみてパラメータが何であったかを推定する尤もらしさ（尤度）を表す尤度関数を定義する。この尤度関数はパラメータの関数であり、尤度関数が最大となるパラメータが求める推定値（最尤推定値）となる。
【０００６】
尤度関数から最尤推定値を求める方法としては、例えば、尤度関数をパラメータで微分したものを零と置いた尤度方程式を解いて解析的に求める方法がある。また、総当たり方式やＥＭ（Expectation Maximization）アルゴリズム等の反復アルゴリズムによって数値的に尤度関数の最大値もしくは尤度方程式の解を求める方法がある。さらに、特開平９−６２６５２号公報（特許文献１）には、ＥＭアルゴリズムの局所最適性の問題を解決するため、結合確率密度関数を用いて観測データに基づく対数尤度関数を計算し、該関数を最大化するパラメータを非線形数値解法により求める技術が開示されている。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】特開平９−６２６５２号公報
【発明の概要】
【発明が解決しようとする課題】
【０００８】
尤度関数から最尤推定値を求める際に、尤度関数が微分可能で解析的に最大値を求めることができるものであれば、比較的容易に最尤推定値を求めることができる。しかし、多くの問題領域においてデータの確率モデルは未知である。この場合、適当な尤度関数を定義することになるが、尤度関数を微分可能な形式で記述できることはまれである。従って、最尤推定値を解析的に求めることができる場合は少ない。
【０００９】
また、総当たり方式や、ＥＭアルゴリズムおよび特許文献１に記載されたような反復アルゴリズムにより数値的に最尤推定値を求める方法では、サンプルデータ数が多い場合やパラメータの取り得る範囲が広い場合等には計算量が膨大となる。また、場合によっては数値積分などの多くの計算処理を必要とする場合もあり、非常に多くの計算コストがかかるという問題がある。
【００１０】
そこで本発明の目的は、尤度関数から最尤推定値を解析的に求めるのが困難である場合に、数値的に求める際の処理を効率化することを可能とする最尤推定方法および最尤推定プログラムを提供することにある。本発明の前記ならびにその他の目的と新規な特徴は、本明細書の記述および添付図面から明らかになるであろう。
【課題を解決するための手段】
【００１１】
本願において開示される発明のうち、代表的なものの概要を簡単に説明すれば、以下のとおりである。
【００１２】
本発明の代表的な実施の形態による最尤推定システムは、対象とする問題領域についての観測データである教師データに基づいて、前記教師データを得られる可能性を示す尤度が最も高くなるパラメータである最尤推定値を推定して出力する最尤推定方法であって、前記パラメータが取り得る値の範囲に対して、推定の対象とする区間である推定区間の初期値を前記教師データに基づいて特定する推定区間初期設定処理と、前記推定区間の推定の終了条件となる前記推定区間の最小幅を前記教師データに基づいて特定する最小幅初期設定処理と、前記推定区間を予め設定された区間分割数の小区間に分割する推定区間分割処理と、前記推定区間分割処理での分割後の前記小区間の幅が、前記最小幅初期設定処理で設定された前記推定区間の最小幅よりも小さいか否かを判定する判定処理と、前記判定処理において前記小区間の幅が前記最小幅以上である場合に、前記小区間毎に、前記小区間内での前記パラメータの代表値における前記尤度を予め設定された尤度計算方法によって計算する尤度計算処理と、前記小区間毎に前記尤度計算処理によって計算された前記尤度を比較し、前記尤度が最大となる前記小区間を選択して、選択した前記小区間を次の前記推定区間として特定する次推定区間選定処理と、前記判定処理において前記小区間の幅が前記最小幅より小さくなる場合に、その時点における前記推定区間での前記パラメータの代表値を前記最尤推定値として出力する最尤推定値出力処理とを実行することを特徴とするものである。
【発明の効果】
【００１３】
本願において開示される発明のうち、代表的なものによって得られる効果を簡単に説明すれば以下のとおりである。
【００１４】
本発明の代表的な実施の形態によれば、多分割探索法を用いることにより、必要十分な精度の最尤推定値を高い時間効率によって求めることができる最尤推定方法および最尤推定プログラムを実現することが可能となる。
【図面の簡単な説明】
【００１５】
【図１】本発明の一実施の形態における最尤推定処理の例を示したフローチャートである。
【図２】本発明の一実施の形態である最尤推定システムの構成例の概要を示した図である。
【図３】本発明の一実施の形態における初期設定処理の具体例について説明する図である。
【図４】本発明の一実施の形態における尤度計算処理の具体例について説明する図である。
【図５】本発明の一実施の形態における多分割探索法により尤度を最大とする最尤推定値を求める処理の具体例について説明する図である。
【発明を実施するための形態】
【００１６】
以下、本発明の実施の形態を図面に基づいて詳細に説明する。なお、実施の形態を説明するための全図において、同一部には原則として同一の符号を付し、その繰り返しの説明は省略する。
【００１７】
本発明の一実施の形態である最尤推定システムは、対象とする問題領域についての観測データ（教師データ）に基づいて、最尤推定方法により当該教師データを得られる可能性が最も高いパラメータ（最尤推定値）を求めて出力するものである。本実施の形態では、最尤推定方法によって最尤推定値、すなわち尤度関数が最大値となるパラメータを求める際に、いわゆる二分探索法を応用した多分割探索法を導入する。
【００１８】
本実施の形態の多分割探索法では、以下の処理によりパラメータの最尤推定値を求める。まず、パラメータの取り得る範囲に対して推定区間を定義し、推定区間を２以上の複数の小区間に分割する。この小区間に対して、区間内のパラメータの代表値において尤度関数が最大となる小区間を特定し、この小区間を次の推定区間とする。この処理を所定の終了条件を満たすまで反復し、その時点における推定区間でのパラメータの代表値を最尤推定値とする。
【００１９】
この多分割探索法を用いることにより、本実施の形態の最尤推定システムでは、必要十分な精度の最尤推定値を高い時間効率によって求めることが可能である。なお、ここで得られる最尤推定値は、必ずしも尤度関数の全パラメータ範囲での最大値や、局所的な範囲での極大値を得るパラメータになるとは限らず、厳密な意味での「最尤」なパラメータではない準最尤なパラメータということになる。しかし、実用上は問題のない必要十分な精度のものを得ることができるため、本実施の形態の最尤推定システムにおいてはこれを実質的な意味で最尤推定値として取り扱う。
【００２０】
本実施の形態の最尤推定システムの利用場面としては、例えば、上述した連想検索エンジンにおける関連キーワードの閾値の決定や、ノイズ除去システムにおけるノイズ閾値の決定、文書分類システムにおける文書類似度の閾値の決定などのように、データ群に対して当該データを特徴付ける値に基づいて適切なデータを取捨選択することを問題領域とし、当該問題領域において適切なデータを取捨選択する際の、データを特徴付ける値の閾値を決定するために用いることが可能である。その他にも最尤推定法を用いることが可能な種々の問題領域に利用することが可能であるが、本実施の形態では、以下、連想検索エンジンにおける関連キーワードの閾値の決定に利用する場合を例として説明する。
【００２１】
［システム構成］
図２は、本発明の一実施の形態である最尤推定システムの構成例の概要を示した図である。最尤推定システム１は、コンピュータシステムによって構成される最尤推定サーバ１００に対して、インターネットや社内ＬＡＮ等のネットワーク３００を介して、ＰＣ等のクライアント端末２００が接続される構成となっている。なお、本実施の形態ではネットワーク３００を介したクライアント／サーバの構成としているが、特に構成に制約があるものではなく、例えば、最尤推定サーバ１００に相当するＰＣ等のスタンドアロンの構成であってもよい。
【００２２】
最尤推定サーバ１００は、ある問題領域についての観測データを教師データ１３１として保持し、この教師データ１３１および予め設定された尤度計算方法１３３（尤度関数）に基づいて最尤推定を行い、パラメータの最尤推定値を求めて出力する。最尤推定サーバ１００は、例えば、初期化部１１０、多分割探索部１２０、管理部１３０、ユーザインタフェース部１４０を有する。これら各部は、例えば、ソフトウェアプログラムによって実現される。
【００２３】
初期化部１１０は、最尤推定における初期化処理を行い、例えば、推定区間特定部１１１、最小幅特定部１１２を有する。推定区間特定部１１１は、最尤推定の際のパラメータの推定区間の初期値を教師データ１３１に基づいて自動的に特定する処理を行う。最小幅特定部１１２は、多分割探索法によって最尤推定を行う際の終了条件となる推定区間の最小幅を教師データ１３１に基づいて自動的に特定する処理を行う。
【００２４】
多分割探索部１２０は、多分割探索法によりパラメータの最尤推定値を求める処理を行い、例えば、区間分割部１２１、尤度計算部１２２、区間選定部１２３を有する。区間分割部１２１は、多分割探索法によって最尤推定を行う際に、対象の推定区間を区間分割数１３２に設定された数の小区間に分割する処理を行う。このとき、分割後の小区間の幅が最小幅特定部１１２によって特定された最小幅以下となる場合は分割を行わず、多分割探索部１２０によって当該推定区間におけるパラメータの代表値を最尤推定値として出力する。
【００２５】
尤度計算部１２２は、区間分割部１２１によって推定区間を分割して作成された小区間毎に、小区間内でのパラメータの代表値における尤度を尤度計算方法１３３に設定された方法（尤度関数）によって計算する処理を行う。区間選定部１２３は、対象の推定区間内の小区間毎に尤度計算部１２２によって計算された尤度を比較し、尤度が最大となる小区間を選択して、選択した小区間を次の推定区間として特定する処理を行う。
【００２６】
管理部１３０は、教師データ１３１や、区間分割数１３２、尤度計算方法１３３などの設定情報を保持・管理する処理を行い、例えば、これらのデータに対する参照や、登録・更新などのインタフェースを有していてもよい。教師データ１３１は、対象の問題領域における観測されたサンプルデータであり、例えば、データベースなどを利用して保持する。区間分割数１３２、および尤度計算方法１３３は、それぞれ、多分割探索法によって最尤推定を行う際の推定区間の分割数、および尤度の計算方法（尤度関数）の定義をファイルや、スクリプト、プログラム等に設定して保持する。
【００２７】
ユーザインタフェース部１４０は、管理部１３０が保持するデータの登録・更新画面や、多分割探索部１２０での最尤推定の処理結果を表示する画面等を生成・表示する処理を行う。各画面は、例えばＨＴＭＬ（HyperText Markup Language）によって画面を生成し、図示しないＷｅｂサーバプログラムを介して、クライアント端末２００上の図示しないＷｅｂブラウザによって表示させる。また、最尤推定サーバ１００に接続された図示しないディスプレイ等の表示装置に直接画面を出力する構成であってもよい。なお、例えば、入出力をコマンドラインやファイル等を介して行うことで固有の画面を介さない処理とすることも可能であり、この場合はユーザインタフェース部１４０は不要である。
【００２８】
［最尤推定処理フロー］
図１は、本実施の形態の最尤推定システム１における最尤推定処理の例を示したフローチャートである。まず、初期化部１１０での初期化処理として、推定区間特定部１１１により、最尤推定の際のパラメータの推定区間の初期値を教師データ１３１に基づいて自動的に特定する推定区間初期設定処理を行う（ステップＳ１０１）。
【００２９】
ここでは、詳細は後述するが、教師データ１３１（本実施の形態では、各キーワードについて連想検索エンジンによって算出された他のキーワードとの類似度、および各キーワードが実際に関連キーワードとして適切か否かの判定結果のデータ）の中で、パラメータ（本実施の形態では関連キーワードを選択するための類似度の閾値）に対応する指標（本実施の形態ではキーワード間の類似度）の値が同じ、もしくはほぼ同じであるにも関わらず観測結果（本実施の形態では判定結果）が異なっているデータを特定する。特定されたデータのうち、当該指標の値が最小値および最大値のものを特定し、これらの値に基づいて特定される区間を、パラメータの推定区間の初期値として設定する。
【００３０】
次に、最小幅特定部１１２により、多分割探索法によって最尤推定の処理における終了条件となる推定区間の最小幅を教師データ１３１に基づいて自動的に特定する最小幅初期設定処理を行う（ステップＳ１０２）。ここでは、詳細は後述するが、教師データ１３１におけるパラメータに対応する指標の値の精度に基づいて、推定区間を分割する際の最小幅を特定して設定する。以上のステップＳ１０１〜Ｓ１０２を実行することによって初期化処理を終了する。
【００３１】
次に、多分割探索部１２０によって、二分探索法を応用した多分割探索法により反復処理によって最尤推定を行う。まず、区間分割部１２１により、推定区間を区間分割数１３２に設定された数の小区間に分割する推定区間分割処理を行う（ステップＳ１０３）。ここでは、管理部１３０を介して区間分割数１３２に設定された値を取得し、その数で推定区間を単純に均等の幅に分割して小区間とする。次に、区間分割部１２１により、ステップＳ１０３での分割後の小区間の幅（現在幅）が、ステップＳ１０２で設定された最小幅よりも小さいか否かを判定する（ステップＳ１０４）。
【００３２】
ステップＳ１０４で、小区間の幅が最小幅以上である場合は、尤度計算部１２２により、小区間毎に、小区間内でのパラメータの代表値における尤度を尤度計算方法１３３に設定された方法（尤度関数）によって計算する尤度計算処理を行う（ステップＳ１０５）。ここでは、詳細は後述するが、管理部１３０を介して尤度計算方法１３３に設定された計算方法（尤度関数ｆ（ｐ））を取得し、取得した尤度関数ｆ（ｐ）について各小区間内でのパラメータｐの代表値ｐｒ（本実施の形態では小区間の中央でのパラメータ値）におけるｆ（ｐｒ）を計算する。
【００３３】
次に、区間選定部１２３により、小区間毎にステップＳ１０４で計算された尤度（ｆ（ｐｒ））を比較し、尤度が最大となる小区間を選択して、選択した小区間を次の推定区間として特定する次推定区間選定処理を行う（ステップＳ１０６）。その後、ステップＳ１０３に戻り、新たな推定区間に対して、さらに小区間に分割して各小区間での尤度を計算し、尤度が最大の小区間を次の推定区間とするという処理（ステップＳ１０３〜Ｓ１０６）を繰り返す。この処理により、推定区間の幅は次第に小さくなっていく。
【００３４】
ステップＳ１０４で、分割した小区間の幅が最小幅より小さくなった場合は、これ以上推定区間の幅を小さくしても、指標の値（本実施の形態ではキーワード間の類似度）の精度との関係でパラメータの最尤推定の精度を上げることができなくなる。従って、これ以上の分割は行わずに多分割探索法における反復処理を終了し、ステップＳ１０７へ進む。ステップＳ１０７では、その時点での推定区間におけるパラメータの代表値（本実施の形態では推定区間の中央でのパラメータ値）を最尤推定値として出力する最尤推定値出力処理を行い、最尤推定処理を終了する。
【００３５】
以上のように、多分割探索法を用いることにより、解析的に最尤推定値を求めることができない場合であっても、反復的に尤度が最大となる推定区間を特定してそれを分割して小さくしていくことで、数値的に最尤推定値を求めることができる。また、初期設定および終了条件の判定を自動的に行うため、最尤推定の際の労力を大幅に軽減することが可能となる。
【００３６】
［初期設定処理］
図３は、図１における初期設定処理（推定区間初期設定処理（ステップＳ１０１）および最小幅初期設定処理（ステップＳ１０２））の具体例について説明する図である。
【００３７】
図３には、本実施の形態における教師データ１３１の内容の例が示されており、キーワード（単語１）に対して連想検索エンジンにより他の単語（単語２）との間で算出された類似度が保持されている。また、実際に単語１のキーワードに対して単語２を関連キーワードとして選択することが適当か否か（正解か否か）の判定をユーザ等が行った判定結果が○×で保持されている。なお、教師データ１３１のデータは、パラメータ（本実施の形態では類似度の閾値）に対応する指標（本実施の形態では類似度）の昇順（もしくは降順）でソートしておく。
【００３８】
推定区間初期設定処理（ステップＳ１０１）では、上述したように、指標（類似度）の値が同じ（もしくはほぼ同じ）であるにも関わらず観測結果（本実施の形態では判定結果）が異なっているデータを特定する。図３の例では、単語１と単語２がそれぞれｗ１とｗ２、およびｗ３とｗ６の場合で類似度がともに０．４７であるにも関わらず判定結果が○と×で異なっている。また、同様に、ｗ１とｗ４、およびｗ２とｗ５の場合で類似度がともに０．５８であるにも関わらず判定結果が異なっている。また、同様に、ｗ１とｗ５、およびｗ２とｗ４の場合で類似度がともに０．７１であるにも関わらず判定結果が異なっている。
【００３９】
このように特定されたデータのうち、指標（類似度）の値が最小および最大であるものは、それぞれ類似度０．４７および０．７１ということになる。このように特定された類似度に対して、本実施の形態では、推定区間の初期値として、その開始値を教師データ１３１のデータにおいて類似度が最小のデータ（０．４７）の１つ前のデータの類似度である０．４５とし、終了値を類似度が最大のデータ（０．７１）の１つ後のデータの類似度である０．７５と特定する。これにより、類似度が十分小さい、もしくは十分大きい範囲で、明らかに閾値として適当な値とはなり得ないパラメータの範囲を最尤推定の処理の対象から除外し、無駄な処理を回避して処理の効率化を図ることができる。
【００４０】
なお、推定区間の開始値・終了値を特定する手法はこれに限るものではなく、例えば、判定結果が○であるデータのうち類似度が最小のデータの１つ前のデータの類似度を開始値とし、判定結果が×であるデータのうち類似度が最大のデータの１つ後のデータの類似度を終了値とするなど、教師データ１３１の内容に基づいてある範囲を決定できる手法であれば他の手法であってもよい。
【００４１】
最小幅初期値設定処理（ステップＳ１０２）では、上述したように、指標（類似度）の精度に基づいて、推定区間を分割する際の最小幅を特定して設定する。図３の例では、類似度の精度は１／１００＝０．０１であるため、推定区間の最小幅は０．０１とする。これより小さい幅の推定区分に対して多分割探索法を施しても最尤推定値の有効桁数での正確さには影響しないためであり、これにより無駄な処理を回避して処理の効率化を図ることができる。
【００４２】
以上のように、教師データ１３１に基づいて、多分割探索法により最尤推定を行う際の推定区間の初期値、および終了条件である推定区間の最小幅を、必要十分な精度の最尤推定値を得られるように自動的に特定して設定することができ、これにより無駄な処理を回避して高い時間効率によって最尤推定値を得ることが可能となる。
【００４３】
［尤度計算処理］
図１における尤度計算処理（ステップＳ１０５）では、上述したように、尤度関数ｆ（ｐ）について各小区間内でのパラメータｐの代表値ｐｒ（本実施の形態では小区間の中央でのパラメータ値）におけるｆ（ｐｒ）を計算する。
【００４４】
ここで、尤度関数ｆ（ｐ）は、問題領域の特性や確率モデルに応じて種々のものを切換えて適用することが可能である。本実施の形態では、例えば、情報検索システムの検索性能評価によく用いられるＦ値（F-measure）を利用する。このＦ値は、検索結果の正確性と網羅性の観点から情報検索システムを評価するものであり、適合率（Ｐ：precision）と再現率（Ｒ：recall）とから、
Ｆ値＝２ＰＲ／（Ｐ＋Ｒ）
の式によって求められる。
【００４５】
ここで、本実施の形態において、Ｐは、連想検索エンジンによる検索結果として得られた関連キーワード中にどれだけ関連キーワードとして適切なもの（正解）を含んでいるかという正確性の指標となる。また、Ｒは、すべての対象の単語の中で関連キーワードとして適切なもの（正解）の中からどれだけの単語を関連キーワードとして検索することができたかという網羅性の指標となる。
【００４６】
例えば、連想検索エンジンにおいて、関連キーワードとして選択する際の類似度の閾値（パラメータ値）ｐを変化させた場合に、検索結果として得られる関連キーワードは変化する。このとき、一般的に、閾値ｐを大きくすると類似度が高い単語のみが選択され、適合率Ｐが大きくなる一方再現率Ｒが小さくなり、逆に閾値ｐを小さくすると、再現率Ｒが大きくなる一方適合率Ｐが小さくなるという傾向がある。従って、このＰとＲの調和平均であるＦ値が大きいほど、連想検索エンジンとしての性能が高いということが言える。
【００４７】
すなわち、Ｆ値が大きいほど、連想検索エンジンによって、教師データ１３１における判定結果（正解）に沿った検索結果が得られる確率が大きくなるということが言える。従って、Ｆ値を尤度関数ｆ（ｐ）として、Ｆ値を最大にする閾値ｐを最尤推定値とすれば、連想検索エンジンにおける関連キーワードを選択する際の最適な閾値を得ることができる。ここで、Ｆ値を閾値ｐの関数として数式で表現する（さらにはｐによって微分する）ことは困難である。従って、本実施の形態では、上述したような多分割探索法を用いてＦ値を最大とする最尤推定値を求める。
【００４８】
図４は、図１における尤度計算処理（ステップＳ１０５）の具体例について説明する図である。教師データ１３１は、上述した図３に示したものと同様である。ここで、尤度の算出対象の小区間における中央の閾値（パラメータ値）がｐｒ＝０．５０であった場合を例とする。このとき、連想検索エンジンでの閾値ｐｒによる特定では、類似度が０．５０より小さい単語の組合せは関連キーワードとして選択されず、類似度が０．５０以上の単語の組合せは全て関連キーワードとして選択されることになる（右表の○×）。
【００４９】
ここで、この閾値による判定結果と、教師データ１３１での判定結果（正解）とを比較して、選択結果が適合しているか否かを特定する（右表の「ＯＫ」「ＮＧ」）。この適合しているか否かの判定結果に基づいて、上記の適合率Ｐおよび再現率Ｒを計算することができ、これらからＦ値、すなわち尤度ｆ（ｐｒ）を計算することができる。
【００５０】
なお、上記のＦ値の計算方法を設定した尤度計算方法１３３は、例えば、スクリプトやマクロなどを含むコンピュータプログラムによって実現することができる。また、本実施の形態では、尤度関数としてＦ値を用いているが、目的に応じて、例えば、検索結果に多少漏れがあってもよいが誤った検索結果の出力を最小限にしたいという場合には、尤度関数として適合率Ｐを用いてもよい。また、逆に、多少検索結果が誤っていてもよいが漏れを極力なくしたいという場合には、尤度関数として再現率Ｒを用いてもよい。また、これらを両立させたい場合には尤度関数としてＦ値を用いるようにしてもよい。
【００５１】
［多分割探索法による最尤推定］
図５は、多分割探索法により尤度を最大とする最尤推定値を求める処理の具体例について説明する図である。図５の例では、尤度関数ｆ（ｐ）を上述したＦ値としている。また、初期化処理（図１のステップＳ１０１、Ｓ１０２）において、推定区間の初期値として図３の例に示すようにパラメータ（類似度の閾値）ｐ＝０．４５〜０．７５の範囲（｛０．４５，０．７５｝）が特定され、また、推定区間の最小幅が０．０１として特定されたものとしている。また、区間分割数１３２に設定された分割数は３であるものとしている。
【００５２】
まず、上段の図に示すように、図１の推定区間分割処理（ステップＳ１０３）により、推定区間｛０．４５，０．７５｝を３つの小区間（｛０．４５，０．５５｝、｛０．５５，０．６５｝、｛０．６５，０．７５｝）に分割する。このとき、各小区間の幅は０．１となる。次に、尤度計算処理（ステップＳ１０５）により、各小区間の中央でのパラメータ値ｐｒにおける尤度ｆ（ｐｒ）を計算する。例えば、小区間｛０．４５，０．５５｝の場合は、パラメータ値ｐｒ＝０．５０となり、この値を閾値とした場合について上述の図４で説明した手順によりＦ値を計算する。同様の処理を他の小区間に対しても行う。
【００５３】
次に、次推定区間選定処理（ステップＳ１０６）により、各小区間でのｆ（ｐｒ）の値の最大値を求める。図５の例では、小区間｛０．５５，０．６５｝でのｆ（ｐｒ）の値が最大である。従って、小区間｛０．５５，０．６５｝を次の推定区間とする。
【００５４】
次に、中段の図に示すように、推定区間｛０．５５，０．６５｝を３つの小区間（｛０．５５，０．５８｝、｛０．５８，０．６１｝、｛０．６１，０．６５｝）に分割する。このとき、各小区間の幅は０．０３となる。さらに、上記と同様に、各小区間でのｆ（ｐｒ）を求め、これが最大となる小区間を求める。図５の例では、小区間｛０．５８，０．６１｝でのｆ（ｐｒ）の値が最大である。従って、小区間｛０．５８，０．６１｝を次の推定区間とする。
【００５５】
次に、下段の図に示すように、推定区間｛０．５８，０．６１｝を３つの小区間（｛０．５８，０．５９｝、｛０．５９，０．６０｝、｛０．６０，０．６１｝）に分割する。このとき、各小区間の幅は０．０１となる。さらに、上記と同様に、各小区間でのｆ（ｐｒ）を求め、これが最大となる小区間を求める。図５の例では、小区間｛０．５８，０．５９｝でのｆ（ｐｒ）の値が最大である。従って、小区間｛０．５８，０．５９｝を次の推定区間とする。
【００５６】
次に、推定区間｛０．５８，０．５９｝を３つの小区間に分割するが、推定区間｛０．５８，０．５９｝の幅が０．０１であるため、これを３つに分割すると小区間の幅が最小幅である０．０１よりも小さくなってしまう。従って、図１のステップＳ１０４での判定により反復処理を終了し、最尤推定値出力処理（ステップＳ１０７）により、推定区間｛０．５８，０．５９｝での中央のパラメータ値であるｐｒ＝０．５８５を最尤推定値として出力し、最尤推定処理を終了する。この最尤推定値（ｐｒ＝０．５８５）を、連想検索エンジンにおける関連キーワード選択の際の類似度の閾値として設定することができる。
【００５７】
以上に説明したように、本発明の実施の形態における最尤推定方法によれば、尤度関数を最大にする最尤推定値を解析的に求めることが難しい場合であっても、多分割探索法を用いることにより、数値的に求めることが可能となる。また、多分割探索法における推定区間の初期値および終了条件である推定区間の最小幅を、必要十分な精度の最尤推定値が得られるように自動的に特定して設定することができるため、無駄な処理を回避して高い時間効率によって最尤推定値を得ることができる。また、初期設定および終了条件の判定を自動的に行うため、最尤推定の際の労力を大幅に軽減することが可能となる。
【００５８】
以上、本発明者によってなされた発明を実施の形態に基づき具体的に説明したが、本発明は前記実施の形態に限定されるものではなく、その要旨を逸脱しない範囲で種々変更可能であることはいうまでもない。
【産業上の利用可能性】
【００５９】
本発明は、最尤推定法により問題領域における閾値などのパラメータを推定する最尤推定方法に利用可能である。
【符号の説明】
【００６０】
１…最尤推定システム、１００…最尤推定サーバ、１１０…初期化部、１１１…推定区間特定部、１１２…最小幅特定部、１２０…多分割探索部、１２１…区間分割部、１２２…尤度計算部、１２３…区間選定部、１３０…管理部、１３１…教師データ、１３２…区間分割数、１３３…尤度計算方法、１４０…ユーザインタフェース部、２００…クライアント端末、３００…ネットワーク。 
【図１】
2010211693.tif 000003
【図２】
2010211693.tif 000004
【図３】
2010211693.tif 000005
【図４】
2010211693.tif 000006
【図５】
2010211693.tif 000007