(57)【要約】【課題】教師データを用いずとも、言語モデルの作成と単語分割とを行えるようにする。【解決手段】言語モデル作成装置は、文字列データ１３１に格納された複数の文をランダムな順に選択し、言語モデル１３２を用いて、この選択した文における単語の区切り目の候補となる文字列を示した文字列分割パターン群を作成する。また、その文がその文字列分割パターン群の文字列分割パターンに該当する確率を記憶部に記録しておき、この確率に従って、文字列分割パターン群の中から、文字列分割パターンを選択する。そして、この選択した文字列分割パターンを用いて言語モデル１３２を更新する。このような処理を、文字列データ１３１に格納された複数の文すべてについて実行し、言語モデル１３２を最適化する。そして、このようにして最適化された言語モデル１３２を用いて、文の最尤単語分割を実行する。【選択図】図２
2010170252.tif 000002
【特許請求の範囲】
【請求項１】
文を構成する文字列を単語ごとに分割し、その分割結果を用いて文字ｎグラムモデルおよび単語ｎグラムモデルからなる言語モデルを作成する言語モデル作成装置が、
学習データである複数の文の入力を受け付けるステップと、
前記入力された複数の文から処理対象の文を選択するステップと、
前記選択した文について、前記文における単語の区切り目の候補となる文字列を示した文字列分割パターンを所定数作成し、前記作成した文字列分割パターンそれぞれについて、前記選択した文が、その文字列分割パターンに該当する確率を記録し、その記録された確率に従い、前記作成した文字列分割パターンの中から、文字列分割パターンを選択するステップと、
前記文字列分割パターンの選択結果を用いて、前記言語モデルを更新するステップとを実行した後、
前記入力された複数の文から、他の別の文を選択するステップと、
前記選択した文について、前記更新した言語モデルを参照して、前記選択した文における単語の区切り目の候補を示した文字列分割パターンを所定数作成し、前記作成した文字列分割パターンそれぞれについて、前記更新した言語モデルを参照して、前記選択した文が、その文字列分割パターンに該当する確率を記録し、その記録された確率に従い、前記作成した文字列分割パターンの中から文字列分割パターンを選択するステップと、
前記選択した文字列分割パターンを用いて、前記言語モデルを更新するステップとを前記入力された複数の文すべてについて実行することを繰り返した後、最終的に更新した言語モデルを出力することを特徴とする言語モデル作成方法。
【請求項２】
前記言語モデル作成装置が、最終的に更新した言語モデルを用いて、前記学習データとして入力された文それぞれについて、ビタビアルゴリズムにより、その文字列分割の確率を最大にする単語分割を計算し、出力することを特徴とする請求項１に記載の言語モデル作成方法。
【請求項３】
前記言語モデル作成装置が、前記選択した文について、その文字列分割パターンに該当する確率を計算し、前記計算した確率に従い、前記文字列分割パターン群の中から、文字列分割パターンを選択するステップは、
以下の式（１）により、前記選択した文における１番目からｔ番目までの文字列Ｓ１：ｔにおいて、ｔ文字の文字列の末尾ｋ文字が１単語として生成される確率α［ｔ］［ｋ］をｔ＝１〜Ｎについて実行した結果を示した確率テーブルを作成し、記憶部に記憶するForwardパス実行ステップと、
【数５】
2010170252.tif 000007
前記確率テーブルを参照して、前記選択した文の文末に続く単語の文字数の確率を読み出し、この読み出した確率に基づき、前記選択した文の文末の単語候補の文字数ｋを選択した後、（１）前記確率テーブルを参照して、前記選択した文字数ｋの単語候補に続く単語候補の文字数の確率を読み出し、（２）この読み出した確率に基づき、前記選択した文字数ｋの単語候補に続く単語候補の文字数ｋ´を選択する処理を、前記選択した文の先頭に来るまで繰り返す確率的Backwardパス実行ステップとを含むことを特徴とする請求項１または請求項２の言語モデル作成方法。
【請求項４】
前記言語モデル作成装置が、前記選択した文について、その文字列分割パターンに該当する確率を計算し、前記計算した確率に従い、前記文字列分割パターン群の中から、文字列分割パターンを選択するステップは、
Particle MCMC（Markov Chain Monte Carlo）法により、前記言語モデルを参照して、前記選択した文の文頭から順に文末まで、単語候補ｗｉの後に続く単語候補の文字数ｋを確率的に選択する処理を、当該選択した文それぞれについて所定数ずつ実行することにより、当該選択した文１つあたり、所定数の文字列分割パターン群を作成する文字列分割パターン作成ステップと、
前記作成した文字列分割パターン群の文字列分割パターンそれぞれの確率の平均値Ｚ（Ｓ）を計算するステップと、
今回作成した文字列分割パターン群の文字列分割パターンそれぞれの確率の平均値Ｚ（Ｓ）と、過去に作成した文字列分割パターン群の文字列分割パターンそれぞれの確率の平均値Ｚ＾（Ｓ）とを比較して、前記Ｚ（Ｓ）の値がＺ＾（Ｓ）の値よりも大きかったとき、
今回作成した文字列パターン群の文字列分割パターンそれぞれの確率に従い、この文字列分割パターン群の中から文字列分割パターンを選択し、前記Ｚ（Ｓ）の値を、前記Ｚ＾（Ｓ）として置き換えて記憶部に記憶した後、前記文字列分割パターン作成ステップに戻るステップと、
前記Ｚ（Ｓ）とＺ＾（Ｓ）とを比較して、前記Ｚ（Ｓ）の値がＺ＾（Ｓ）の値以下だったとき、ベルヌーイ試行によりＺ（Ｓ）／Ｚ＾（Ｓ）の確率で、今回作成した文字列分割パターン群を選択するか否かを決定し、（１）今回作成した文字列パターン群を選択すると決定した場合、この文字列分割パターン群の文字列分割パターンそれぞれの確率に従い、この文字列分割パターン群の中から文字列分割パターンを選択し、（２）前記ベルヌーイ試行の結果、今回作成した文字列分割パターン群を選択しないと決定した場合、そのまま処理を終了するステップとを含むことを特徴とする請求項１または請求項２の言語モデル作成方法。
【請求項５】
文を構成する文字列を単語ごとに分割し、その分割結果を用いて文字ｎグラムモデルおよび単語ｎグラムモデルからなる言語モデルを作成する言語モデル作成装置であって、
学習データである複数の文の入力を受け付ける入力部と、
前記入力された複数の文から処理対象の文を選択する文選択部と、
前記選択した文について、前記文における単語の区切り目の候補となる文字列を示した文字列分割パターンを所定数作成する文字列分割パターン作成部と、
前記作成した文字列分割パターンそれぞれについて、現在の前記言語モデルを参照して、前記選択した文が、その文字列分割パターンに該当する確率を記録し、その記録された確率に従い、前記作成した文字列分割パターンの中から文字列分割パターンを選択する文字列分割パターン選択部と、
前記文字列分割パターンの選択結果を用いて、前記言語モデルを更新する言語モデル更新部と、
前記更新した言語モデルを出力する出力処理部とを備え、
前記言語モデル更新部が、
前記選択した文字列分割パターンを用いて、前記言語モデルを更新する処理を前記入力された複数の文すべてについて実行することを繰り返した後、
前記出力処理部は、
前記言語モデル更新部が最終的に更新した言語モデルを出力することを特徴とする言語モデル作成装置。
【請求項６】
コンピュータを請求項５に記載の言語モデル作成装置として機能させるための言語モデル作成プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、任意の自然言語における文字列または一般の離散的記号の時系列（例えば、ＤＮＡ（Deoxyribo Nucleic Acid)配列やビット列等）が与えられたとき、それを単語または同等の単位に分割する情報処理技術に関する。
【背景技術】
【０００２】
自然言語処理において、文の文字列を単語に分割することは、最も基本的かつ重要な処理である。特に、言語モデル（文において、ある単語の次にどのような単語が来るかを推測するためのモデル）を作成する際に、この単語分割の問題は非常に重要である。日本語や中国語等の言語では、分かち書き（単語の区切り目に空白を挟んで記述すること）が行われないので、単語分割が不可欠である。また、西欧語のように、分かち書きを行う言語の場合も「hot dog」や「with respect to」等の名詞や慣用句、「the united states of america」のような固有名詞は、本来１つの単語として見なすべきである。よって、このような言語においても単語分割の問題は重要である。
【０００３】
従来、このような単語分割を行うためには形態素解析器が用いられていた。この形態素解析器は、予め人手で分割された学習データおよび単語辞書等の教師データの利用を前提としていた。この教師データの構築、精度の保証、メンテナンスには多大なコストがかかり、また、単語分割の基準も曖昧で、本質的に主観的なものにならざるを得ない。さらに、これらの教師データは未知の言語や、話し言葉のように文法や、単語境界が明らかでない言語や、古文等については作成することが困難である。また、この教師データは、人手で単語分割した新聞記事等をもとに作成されており、新聞記事として掲載される可能性の低い内容に関する文については、高精度な単語分割は困難である。このような問題は、中国語や、英語等、日本語以外の言語でも同様に存在する。
【０００４】
このような問題を解決するため、教師データを必要としない単語分割技術が研究されている（非特許文献１，２参照）。また、近年、英語の単語分割について、ベイズ学習を用いる方法も提案されている（非特許文献３参照）。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】松原勇介他、「最小記述長原理に基づいた日本語話し言葉の単語分割」、言語処理学会、言語処理学会第１３回年次大会発表論文集、2007年
【非特許文献２】永田昌明、「単語出現頻度の期待値に基づくテキストからの語彙獲得」、情報処理学会、情報処理学会論文誌、40（9）：3373-3386，1999年
【非特許文献３】Sharon Goldwater, Thomas L. Griffiths, Mark Johnson、「Contextual Dependencies in Unsupervised Word Segmentation」、p.673-680、ACL/COLING、2006
【発明の概要】
【発明が解決しようとする課題】
【０００６】
しかし、非特許文献１，２に記載の技術において、単語分割は、発見的な基準に基づくものであり、また、最初に教師データを必要するという問題があった。また、この非特許文献１，２に記載の技術は、推論の際に、最尤推定に基づくＥＭ（Expectation Maximization）アルゴリズムが使われており、局所解に陥りやすいという問題があった。例えば、文中に登場する「東京都」という文字列について、「東京都」を単語とする解と、「東京」を単語とする解の両方の解があってよいような場合に、最尤推定に基づくＥＭアルゴリズムによれば、「東京都」を単語とする解しか出力されない場合もあるという問題があった。また、非特許文献３に記載の技術は、単語として分割する位置を一文字一文字変えていくため、莫大な計算量を要するという問題があった。また、単語分割のためには、アニーリング（大域的最適解を求めること）等、正解に近い結果を得るような工夫が必要であり、そのやり方によっては計算結果が大きく異なる可能性もある。
【０００７】
そこで、本発明は、前記した課題を解決し、教師データを用いずとも、精度の高い言語モデルの作成と単語分割とを効率的に行えるようにすることを目的とする。
【課題を解決するための手段】
【０００８】
前記した課題を解決するため、請求項１に記載の発明は、文を構成する文字列を単語ごとに分割し、その分割結果を用いて文字ｎグラムモデルおよび単語ｎグラムモデルからなる言語モデルを作成する言語モデル作成装置が、学習データである複数の文の入力を受け付けるステップと、入力された複数の文から処理対象の文を選択するステップと、選択した文について、この選択した文における単語の区切り目の候補となる文字列を示した文字列分割パターンを所定数作成するステップと、作成した文字列分割パターンそれぞれについて、選択した文が、その文字列分割パターンに該当する確率を記録し、その記録された確率に従い、作成した文字列分割パターンの中から、文字列分割パターンを選択するステップと、文字列分割パターンの選択結果を用いて、言語モデルを更新するステップとを実行した後、入力された複数の文から、他の別の文を選択するステップと、選択した文について、更新した言語モデルを参照して、選択した文における単語の区切り目の候補を示した文字列分割パターンを所定数作成し、作成した文字列分割パターンそれぞれについて、更新した言語モデルを参照して、選択した文が、その文字列分割パターンに該当する確率を記録し、その記録された確率に従い、作成した文字列分割パターンの中から文字列分割パターンを選択するステップと、選択した文字列分割パターンを用いて、言語モデルを更新するステップとを入力された複数の文すべてについて実行することを繰り返した後、最終的に更新した言語モデルを出力することを特徴とする言語モデル作成方法とした。
【０００９】
請求項５に記載の発明は、文を構成する文字列を単語ごとに分割し、その分割結果を用いて文字ｎグラムモデルおよび単語ｎグラムモデルからなる言語モデルを作成する言語モデル作成装置であって、学習データである複数の文の入力を受け付ける入力部と、入力された複数の文から処理対象の文を選択する文選択部と、選択した文について、文における単語の区切り目の候補となる文字列を示した文字列分割パターンを所定数作成する文字列分割パターン作成部と、作成した文字列分割パターンそれぞれについて、現在の言語モデルを参照して、選択した文が、その文字列分割パターンに該当する確率を記録し、その記録された確率に従い、作成した文字列分割パターンの中から文字列分割パターンを選択する文字列分割パターン選択部と、文字列分割パターン選択部と、文字列分割パターンの選択結果を用いて、言語モデルを更新する言語モデル更新部と、更新した言語モデルを出力する出力処理部とを備え、言語モデル更新部が、選択した文字列分割パターンを用いて、言語モデルを更新する処理を入力された複数の文すべてについて実行することを繰り返した後、出力処理部は、言語モデル更新部が最終的に更新した言語モデルを出力することを特徴とする。
【００１０】
このようにすることで、言語モデル作成装置は、教師データを用いずとも、文の単語分割と言語モデルの作成とを行うことができる。また、このとき、言語モデル作成装置は、言語モデルを参照して、計算した文字列分割パターンごとに、選択した文が、その文字列分割パターンに該当する確率を計算しておく。そして、その計算した確率に従い、文字列分割パターン群の中から、文字列分割パターンを選択する（文字列分割サンプリング処理を実行する）。例えば、選択した文が文字列分割パターンＡにあてはまる確率が０．５であり、文字列分割パターンＢにあてはまる確率が０．３であり、文字列分割パターンＣにあてはまる確率が０．２であるとき、文字列分割パターンＡ，Ｂ，Ｃそれぞれを選択する確率を５：３：２として選択する。そして、その選択した文字列分割パターンに基づき、言語モデルを更新する。このように確率的に文字列分割パターンを選択する処理を行うことで、文字列分割の結果が、局所解に陥ることがなくなる。また、文字列分割サンプリング処理を実行するたび、その処理結果を用いて言語モデルを更新する処理を繰り返すので、精度の高い言語モデルを効率よく作成できる。
【００１１】
請求項２に記載の発明は、請求項１に記載の言語モデル作成方法において、言語モデル作成装置が、最終的に更新した言語モデルを用いて、学習データとして入力された文それぞれについて、ビタビアルゴリズムにより、その文字列分割の確率を最大にする単語分割を計算し、出力することを特徴とする。
【００１２】
このようにすることで、言語モデル作成装置は、最終的に更新した言語モデル、つまり最適化された言語モデルを用いて、単語分割を行うので、精度の高い単語分割を行うことができる。
【００１３】
請求項３に記載の発明は、請求項１または請求項２に記載の言語モデル作成方法において、選択した文が、その文字列分割パターンに該当する確率を記録し、その記録された確率に従い、作成した文字列分割パターンの中から文字列分割パターンを選択するステップは、以下の式（１）により、選択した文における１番目からｔ番目までの文字列Ｓ１：ｔにおいて、ｔ文字の文字列の末尾ｋ文字が１単語として生成される確率α［ｔ］［ｋ］をｔ＝１〜Ｎについて実行した結果を示した確率テーブルを作成し、記憶部に記憶するForwardパス実行ステップと、
【数１】
2010170252.tif 000003
確率テーブルを参照して、選択した文の文末に続く単語の文字数の確率を読み出し、この読み出した確率に基づき、選択した文の文末の単語候補の文字数ｋを選択した後、（１）確率テーブルを参照して、選択した文字数ｋの単語候補に続く単語候補の文字数の確率を読み出し、（２）この読み出した確率に基づき、選択した文字数ｋの単語候補に続く単語候補の文字数ｋ´を選択する処理を、選択した文の先頭に来るまで繰り返す確率的Backwardパス実行ステップとを含むことを特徴とする。
【００１４】
このように言語モデル作成装置が、Forwardパスにより作成しておいた確率テーブルを用いて、確率的Backwardパスを実行することで、前後複数の単語同士の関係を考慮して単語分割を推定できる。つまり、より精度の高い単語分割の推定を行うことができる。また、言語モデル作成装置がBackwardパスを実行し、文字数ｋ（ｋ´）の単語候補に続く単語候補の文字数を、確率テーブルを用いて、確率的に選択するので、単語分割が局所解に陥ることを防止できる。
【００１５】
請求項４に記載の発明は、請求項１または請求項２に記載の言語モデル作成方法において、言語モデル作成装置が、選択した文が、その文字列分割パターンに該当する確率を記録し、その記録された確率に従い、作成した文字列分割パターンの中から文字列分割パターンを選択するステップは、Particle MCMC（Markov Chain Monte Carlo）法により、言語モデルを参照して、選択した文の文頭から順に文末まで、単語候補ｗｉの後に続く単語候補の文字数ｋを確率的に選択する処理を、当該選択した文それぞれについて所定数ずつ実行することにより、当該選択した文１つあたり、所定数の文字列分割パターン群を作成する文字列分割パターン作成ステップと、作成した文字列分割パターン群の文字列分割パターンそれぞれの確率の平均値Ｚ（Ｓ）を計算するステップと、今回作成した文字列分割パターン群の文字列分割パターンそれぞれの確率の平均値Ｚ（Ｓ）と、過去に作成した文字列分割パターン群の文字列分割パターンそれぞれの確率の平均値Ｚ＾（Ｓ）とを比較して、Ｚ（Ｓ）の値がＺ＾（Ｓ）の値よりも大きかったとき、今回作成した文字列パターン群の文字列分割パターンそれぞれの確率に従い、この文字列分割パターン群の中から文字列分割パターンを選択し、Ｚ（Ｓ）の値を、Ｚ＾（Ｓ）として置き換えて記憶部に記憶した後、文字列分割パターン作成ステップに戻るステップと、Ｚ（Ｓ）とＺ＾（Ｓ）とを比較して、Ｚ（Ｓ）の値がＺ＾（Ｓ）の値以下だったとき、ベルヌーイ試行によりＺ（Ｓ）／Ｚ＾（Ｓ）の確率で、今回作成した文字列分割パターン群を選択するか否かを決定し、（１）今回作成した文字列パターン群を選択すると決定した場合、この文字列分割パターン群の文字列分割パターンそれぞれの確率に従い、この文字列分割パターン群の中から文字列分割パターンを選択し、（２）ベルヌーイ試行の結果、今回作成した文字列分割パターン群を選択しないと決定した場合、そのまま処理を終了するステップとを含むことを特徴とする。
【００１６】
このようにすることで、言語モデル作成装置は、言語モデルを参照して、選択した文の文頭から順に単語候補の文字数を確率的に選択して文字列分割パターンを作成するので、文字列分割パターン作成のための計算量を低減できる。また、言語モデル作成装置は、文字列分割パターンを作成するとき、その文字列分割パターンの確率についても、計算できるので、文字列分割パターンのサンプリングを効率的に行うことができる。ここで、言語モデル作成装置は、今回作成した文字列分割パターン群の確率の平均値（Ｚ（Ｓ））と、前回作成した文字列分割パターン群の確率の平均値（Ｚ＾（Ｓ））とを比較し、今回作成した文字列分割パターン群の確率の平均値（Ｚ（Ｓ））が前回作成した文字列分割パターン群の確率の平均値（Ｚ＾（Ｓ））よりも高い値であることを確認した上で、この今回作成した文字列分割パターン群の方を用いてサンプリングを行う。このようにすることで、言語モデル作成装置は、今回作成した所定数（Ｊ個）の文字列分割パターン群が、たまたま確率の低い文字列分割パターン群であった場合に、その文字列分割パターン群をサンプリングの対象にしないようにできる。なお、Ｚ（Ｓ）がＺ＾（Ｓ）以下だった場合は、言語モデル作成装置は、ベルヌーイ試行によりＺ（Ｓ）／Ｚ＾（Ｓ）の確率で、今回作成した文字列分割パターン群を選択するか否かを決定する。このようにすることで、言語モデル作成装置は、サンプリングに用いる文字列分割パターン群を真の分布に近いものとすることができる。
【００１７】
請求項６に記載の発明は、コンピュータを請求項５に記載の言語モデル作成装置として機能させるための言語モデル作成プログラムとした。
【００１８】
このようなプログラムによれば、一般的なコンピュータを請求項５に記載の言語モデル作成装置として機能させることができる。
【発明の効果】
【００１９】
本発明によれば、教師データを用いずとも、精度の高い言語モデルの作成と単語分割とを実現できる。また、教師データを用いる必要がないので、任意の言語および離散記号列の言語モデルの作成と単語分割とを実現できる。
【図面の簡単な説明】
【００２０】
【図１】各実施の形態における言語モデルを模式的に示した図である。
【図２】各実施の形態の言語モデル作成装置の処理手順の概要を示したフローチャートである。
【図３】図３は、第１の実施の形態の言語モデル作成装置の構成を示したブロック図である。
【図４】図３の言語モデル作成装置による文字列分割サンプリング処理の詳細を示したフローチャートである。
【図５】図３の確率テーブルを例示した図である。
【図６】図３の言語モデル作成装置におけるα［ｔ］［ｋ］の計算処理を概念的に説明した図である。
【図７】図３の言語モデル作成装置における分割サンプリング処理を概念的に説明した図である。
【図８】第２の実施の形態の言語モデル作成装置におけるサンプリング処理を概念的に説明した図である。
【図９】第２の実施の形態の言語モデル作成装置の構成を示したブロック図である。
【図１０】図９の言語モデル作成装置の処理手順を示したフローチャートである。
【図１１】図１０のＳ３０６およびＳ３０７の処理の詳細を示したフローチャートである。
【発明を実施するための形態】
【００２１】
以下、本発明を実施するための形態を、第１の実施の形態および第２の実施の形態に分けて説明する。まず、第１の実施の形態の言語モデル作成装置および第２の実施の形態の言語モデル作成装置に共通する部分を、図１および図２を用いて説明する。以下、概要を説明すると、言語モデル作成装置は、まず、文字列データに格納された複数の文をランダムな順に選択し、言語モデルを用いて、この選択した文における単語の区切り目の候補となる文字列を示した文字列分割パターン群を作成する。また、その文がその文字列分割パターン群の文字列分割パターンに該当する確率を記憶部に記録しておき、この確率に従って、文字列分割パターン群の中から、文字列分割パターンを選択する。そして、この選択した文字列分割パターンを用いて言語モデルを更新する。このような処理を、文字列データに格納された複数の文すべてについて実行することを繰り返し、言語モデルを最適化する。そして、言語モデル作成装置は、このようにして最適化された言語モデルを用いて、文の最尤単語分割を実行する。
【００２２】
ここで、言語モデル作成装置における単語分割（統計的単語分割）は、文を構成する文字列Ｓ＝ｓ１ｓ２ｓ３…ｓＮを分割した単語列Ｗ＝ｗ１ｗ２ｗ３…ｗＭの確率Ｐ（Ｗ｜Ｓ）が最大になる分割Ｗ＾を求めることにより行われる。すなわち、Ｗ＾は以下の式（２）により表される。
【数２】
2010170252.tif 000004
【００２３】
例えば、文Ｓの文字列＝「彼女の言った話は…」の単語分割として、Ｗ１＝「彼女｜の｜言った｜話｜は｜…」、Ｗ２＝「彼｜女の言｜っ｜た話｜は｜…」等が考えられる。しかし、学習データとして読み込まれた様々な文を調べることで、Ｐ（Ｗ１｜Ｓ）＞Ｐ（Ｗ２｜Ｓ）であることが分かる。つまり、学習データとして読み込まれた多数の文の文字列の並びを統計解析することで、「彼」と「女」が切れる確率よりも、「彼女」というひとかたまりの文字列として登場する確率が高く、「女の言」というひとかたまりの文字列として登場する確率よりも「女」は「彼女」という文字列に含まれる確率が高く、また、「の」は助詞として、いったん切れ、「言」は「言った」という文字列に含まれる確率が高いことが確認できる。このように学習データをもとに、確率が最大になるＷ＾を求めることが単語分割の問題である。
【００２４】
ここで各実施の形態の言語モデル作成装置の扱う言語モデルは、確率Ｐ（Ｗ｜Ｓ）を、単語ｎグラム−文字ｎグラムとして階層化した言語モデルであるものとする。この階層化した言語モデルは、階層Pitman−Yor過程によるｎグラム言語モデル（Yee Whyeteh、A Hierarchical Bayesian Language Model based on Pitman-Yor Processes. In Proc  of COLING/ACL 2006, p985-992, 2006参照）を応用することにより実現可能である。図１に示すように、言語モデルは、単語列（単語列データ）に対し単語列確率を与えるための単語ｎグラムモデルと、その単語ｎグラムモデルを構成する単語の文字列データそれぞれに文字列確率を与えるための文字ｎグラムモデルとを含んで構成される。このように、言語モデルを、単語に関する単語ｎグラムモデルと、その単語ｎグラムモデルを構成する単語の文字列データそれぞれに対する文字ｎグラムモデルとの２つの階層からなるものとすることで、この言語モデルを用いた単語分割の推測精度を向上させることができる。
【００２５】
ここで、言語モデル作成装置は、図２に示す手順により、MCMC（Markov Chain Monte Carlo、マルコフ連鎖モンテカルロ）法によって、Ｐ（Ｗ｜Ｓ）を最大化する分割Ｗを計算し、言語モデルの最適化を行う。
【００２６】
まず、言語モデル作成装置は、文字列データ１３１から学習データである複数の文（まだ、単語分割されてない文）の読み込みを行う（Ｓ１０１）。
【００２７】
次に、言語モデル作成装置は、言語モデル１３２を参照して、文字列分割サンプリング処理を行う（Ｓ１０２）。この文字列分割サンプリング処理の詳細は後記するが、言語モデル作成装置が選択した文について、その文における単語の区切り目の候補を示した文字列分割パターンを所定数作成する。そして、この作成した文字列分割パターンそれぞれについて、選択した文が、その文字列分割パターンに該当する確率を計算する。そして、言語モデル作成装置は、その計算した確率に従い、文字列分割パターン群の中から、その文の文字列分割パターンを選択する。
【００２８】
次に、言語モデル作成装置は、Ｓ１０２で各文の文字列分割パターンが選択されるたびに（つまり、各文が分割されるたびに）、その分割結果（文字列分割パターン）を用いて言語モデル１３２を更新する（Ｓ１０３）。なお、初期状態において言語モデル１３２は、まだ単語が未学習の状態であるため、言語モデル作成装置は、言語モデル１３２の単語ｎグラムモデルにおける文全体を１つの単語としてみなす。そして、その単語（ここでは文全体）の中身が文字ｎグラムモデルによって解析し、その解析結果をもとに言語モデル１３２を更新するものとする。ここでの言語モデルの更新は、言語モデル１３２が与えた、以前のその文の文字列分割パターン（最初は、文全体が１つの単語であるような文字列分割パターン）によるデータを、言語モデル１３２から削除し、新たな文字列分割パターンを言語モデル１３２に与えることにより行われる。なお、言語モデル作成装置は、この言語モデル１３２の更新において、単語モデルにひもづく文字モデル（図１参照）も併せて更新する。
【００２９】
ここで、言語モデル作成装置は、すべての文の文字列の分割が完了したか否かを確認し（Ｓ１０４）、まだ分割していない文があれば（Ｓ１０４のＮｏ）、Ｓ１０２へ戻る。一方、すべての文の文字列の分割が完了していれば（Ｓ１０４のＹｅｓ）、言語モデル作成装置は文字列の分割の収束判定を行う（Ｓ１０５）。ここでの収束判定は、例えば、Ｓ１０２で行った文字列サンプリング処理により得られた文字列の分割結果の尤度が所定の閾値を超えたことをもって、文字列の分割結果が収束したと判定してもよいし、Ｓ１０２〜Ｓ１０４までの処理を所定回数繰り返し実行したことをもって収束したと判定してもよい。
【００３０】
このＳ１０５において、言語モデル作成装置が、各文の文字列の分割が収束したと判定したとき（Ｓ１０５のＹｅｓ）、言語モデル作成装置は、言語モデル１３２が最適化されたと判定し、最終的に更新された言語モデル１３２に基づき、ビタビアルゴリズムにより、最尤単語分割の計算を行う（Ｓ１０６）。つまり、言語モデル作成装置は、最適化された言語モデル１３２に基づき、Ｐ（Ｗ｜Ｓ）を最大化する分割Ｗを計算する。そして、その計算結果（単語分割Ｗ）を出力する。また、言語モデル作成装置は、この最適化された言語モデル１３２を出力する（Ｓ１０７）。一方、Ｓ１０５において、文字列の分割がまだ収束していないと判定したとき（Ｓ１０５のＮｏ）、Ｓ１０２へ戻る。
【００３１】
以上のように、言語モデル作成装置は、学習用データである複数の文それぞれに対し、文字列分割サンプリング処理を実行し、その結果を用いて言語モデル１３２を更新するので、効率よく、言語モデル１３２を最適化できる。また、このように最適化された言語モデル１３２を用いて、単語分割を行うので精度の高い単語分割結果を得ることができる。なお、図２のＳ１０２の文字列分割サンプリング処理において、複数の文それぞれについて、この文における単語の区切り目の候補を示した文字列分割パターンを作成する。ここで処理対象の文が、この作成した文字列分割パターンに該当する確率を記憶部の所定領域に記録しておき、その確率をもとに、この処理対象の文の文字列分割パターンを選択する。つまり、言語モデル作成装置は、その文に該当する文字列分割パターンについて確率的なサンプリングを行う。よって、サンプリングの結果が局所解に陥ることがなくなる。つまり、前記した例でいうと、文Ｓに登場する「東京都」という文字列について、「東京都」を１つの単語とする確率Ａと、「東京」を１つの単語とする確率Ｂとに基づき、確率的に「東京都」を１つの単語とするという解、または「東京」を１つの単語とするという解を選択する。よって、従来、確率Ａの方が、確率Ｂよりも高い値であれば、「東京都」を１つの単語とするという解しか選択されず、局所解に陥っていたが、この言語モデル作成装置によれば、「東京」を１つの単語とするという解も選択される可能性がある。つまり、サンプリングの結果が局所解に陥ることがなくなる。また、言語モデル作成装置は、教師データを用いないので、様々な言語データ、例えば、未知の言語、話し言葉、古文、口語等の単語分割および言語モデルの作成を実現できる。
【００３２】
＜第１の実施の形態＞
次に、第１の実施の形態の言語モデル作成装置１０を説明する。第１の実施の形態の言語モデル作成装置１０は、前記した図２のＳ１０２において、隠れマルコフモデルのForward Fitering-Backward Sampling法（Steven L. Scott .Bayesian Methods for Hidden Markov Models Journal of the American Statistical Association,97:337-351,2007参照）を用いたサンプリングを行うことを特徴とする。ここで、言語モデル作成装置１０は、Backward Sampling（Backwardパス）を確率的に行うことで、サンプリングの結果が局所解に陥らないようしている。
【００３３】
図３に示すように、言語モデル作成装置１０の機能は、大きく、入出力部１１、処理部１２および記憶部１３に分けられる。入出力部１１は、この学習データである文字列データの入力を受け付けたり、文の分割結果、最適化された言語モデル１３２等を出力したりする。処理部１２は、言語モデル作成装置１０全体の制御を司り、ここでは、主に各文の文字列分割パターンの作成や、その文字列分割パターンの確率を用いて選択した文字列分割パターンを用いて言語モデルの更新を行う。記憶部１３は、文字列分割パターンの作成や、言語モデル１３２の更新に必要な各種データを記憶する。
【００３４】
入出力部１１は、入出力インタフェースから構成される。また、処理部１２は、この言語モデル作成装置１０が備えるＣＰＵ（Central Processing Unit）による、実行処理や、専用回路等により実現される。さらに、記憶部１３は、ＲＡＭ（Random Access Memory）、ＲＯＭ（Read Only Memory）、ＨＤＤ（Hard Disk Drive）、フラッシュメモリ等の記憶媒体から構成される。なお、言語モデル作成装置１０をプログラム実行処理により実現する場合、記憶部１３には、この言語モデル作成装置１０の機能を実現するためのプログラムが格納される。
【００３５】
処理部１２は、パラメータ読み込み部１２０、文選択部１２１、文字列分割パターン作成部１２２、確率計算部１２３、文字列分割パターン選択部１２４、言語モデル更新部１２５、収束判定部１２６、最尤単語分割計算部１２７および出力処理部１２８を含んで構成される。
【００３６】
パラメータ読み込み部１２０は、言語モデル１３２の各種パラメータを読み込む。
【００３７】
文選択部１２１は、文字列データ１３１として格納される複数の文から、文を選択する。このときの文の選択順はランダムな順とする。
【００３８】
文字列分割パターン作成部１２２は、文選択部１２１により選択された文について、言語モデル１３２を参照して、この文における単語の区切り目の候補を示した文字列分割パターンを所定数作成する。
【００３９】
確率計算部１２３は、文字列分割パターン作成部１２２により作成された文字列分割パターンそれぞれについて、選択した文が、その文字列分割パターンに該当する確率を計算する。計算した確率については、確率テーブル１３３に記憶しておく。このときの確率計算の詳細は、フローチャートを用いて後記する。
【００４０】
文字列分割パターン選択部１２４は、文字列分割パターン作成部１２２により作成された文字列分割パターンそれぞれについて、現在の言語モデルを参照して、確率計算部１２３により計算された確率に従い、この作成した文字列分割パターンの中から文字列分割パターンを選択する。すなわち、文字列分割パターン選択部１２４は、同じ文に関する複数の文字列分割パターン群の中から、この確率テーブル１３３に示される確率が高い文字列分割パターンほど高い確率で、その文字列分割パターンを選択する。このように、文字列分割パターン選択部１２４が、確率的に文字列分割パターンの選択を行うことで、文字列分割の結果が局所解に陥ることがなくなる。
【００４１】
言語モデル更新部１２５は、文字列分割パターン選択部１２４により選択された文字列分割パターン（文字列分割結果）に基づき、言語モデル１３２の更新を行う。なお、更新された言語モデル１３２は、文字列データ１３１の他の文の文字列分割において参照される。
【００４２】
収束判定部１２６は、文字列分割結果の収束判定を行う。例えば、収束判定部１２６は、図２のＳ１０２〜Ｓ１０４までの処理を所定回数繰り返し実行したときに、文字列分割結果が収束したとみなす。
【００４３】
最尤単語分割計算部１２７は、言語モデル更新部１２５により最終的に更新された言語モデル１３２に基づき、文字列データ１３１に格納される各文ごとに、ビタビアルゴリズムにより、Ｐ（Ｗ｜Ｓ）を最大化する分割Ｗを計算する。
【００４４】
出力処理部１２８は、言語モデル更新部１２５により更新された言語モデル１３２や、最尤単語分割計算部１２７により計算された各文ごとのＰ（Ｗ｜Ｓ）を最大化する分割Ｗの計算結果を、入出力部１１経由で外部装置等に出力する。
【００４５】
記憶部１３は、文字列データ１３１、言語モデル１３２および確率テーブル１３３を記憶する。
【００４６】
文字列データ１３１は、この言語モデル作成装置１０の学習データである複数の文である。この文は、入出力部１１経由で入力される。
【００４７】
言語モデル１３２は、単語列（単語列データ）に対し単語列確率を与えるための言語モデルであり、単語nグラムモデルと、その単語ｎグラムモデルの単語の文字列データそれぞれの文字列確率を与えるための文字ｎグラムモデルとを含んで構成される（図１参照）。この言語モデル１３２は、初期状態においては、まだ単語が未学習の状態であるため、単語ｎグラムモデルにおける文全体を１つの単語としてみなすような言語モデルとなっている。その後、言語モデル更新部１２５が、文それぞれの文字列分割サンプリング処理の結果をもとに言語モデル１３２の更新をすることで、より精度の高い単語分割を行えるような言語モデルへ更新されていく。
【００４８】
確率テーブル１３３は、文選択部１２１により選択された文についての文字列分割パターンごとに、その文字列分割パターンの確率を示した情報である。この確率テーブル１３３は、図５に例示するように、文字列データ１３１として格納される文Ｓ（Ｓ１、Ｓ２、…、Ｓｎ）ごとに作成される。そして、その文Ｓの文頭から文末までの文字列の長さｔごとに、その文の末尾ｋ文字が単語を構成する文字列分割パターンとなる確率α[ｔ][ｋ]を示したものである。この確率テーブル１３３に示される確率は、文字列分割パターン選択部１２４が、各文ごとに、この文の文字列分割パターンを選択するときに参照される。
【００４９】
次に、このような言語モデル作成装置１０による文字列分割サンプリング処理（図２のＳ１０２）を、図４を用いて説明する。なお、言語モデル作成装置１０の全体の処理の流れは図２に示したとおりであるので省略する。ここでの文字列分割サンプリング処理は、確率テーブル計算処理により確率テーブル１３３を作成する（Forwardパス）と、この作成した確率テーブル１３３を参照した、分割サンプリング処理（Backwardパス）とに分けられる。
【００５０】
図４に示すように、まず図３の言語モデル作成装置１０のパラメータ読み込み部１２０は、現在の言語モデル１３２から、この言語モデル１３２のパラメータを読み込む（Ｓ２０１）。
【００５１】
そして、言語モデル作成装置１０は、確率テーブル計算処理を実行する（Ｓ２０２）。すなわち、まず、言語モデル作成装置１０の文選択部１２１は、図２のＳ１０１で読み込まれた複数の文の中から、ランダムに文を選択する。そして、文字列分割パターン作成部１２２は、この選択された文に対し、パラメータ読み込み部１２０により読み込まれた言語モデル１３２のパラメータを用いて、文字列分割パターンを作成する。そして、確率計算部１２３は、その文字列分割パターンごとに確率（α[ｔ][ｋ]）を計算し、確率テーブル１３３に記録していく。このときのForwardパス（確率テーブル１３３の作成）は、以下のようになる。
【００５２】
前記した図２のＳ１０２で選択された文Ｓについて、その文Ｓの文字数をＮ文字とする。このＮ文字の文Ｓのｔ文字目までの文字列（ｓ１：ｔ）において、このｔ文字目までのｋ文字（１≦ｋ≦ｔ）の文字列が単語として生成された確率を、α［ｔ］［ｋ］とする。ここで、ｋ文字より前の単語境界すべてについて周辺化されているので、このα［ｔ］［ｋ］は、以下の式（１）により計算される。
【数３】
2010170252.tif 000005
但し、α［０］［０］＝１とする。また、ｓｎ：ｍは、文Ｓの部分文字列ｓｎ…ｓｍを示し、Θは、現在の言語モデル１３２のパラメータである。この式（１）におけるｓｔ-ｋ＋１：ｔおよびｓｔ-ｋ-ｊ＋１：ｔ-ｋは、図６に示す文字列Ｘおよびに文字列Ｙに対応する。確率計算部１２３は、前記した式（１）により、文Ｓのα［ｔ］［ｋ］を計算すると、その計算結果を、確率テーブル１３３に記録する。
【００５３】
図４の説明に戻る。このようにして、確率計算部１２３が確率テーブル１３３を作成すると、文字列分割パターン選択部１２４は、分割サンプリング処理を行う（Ｓ２０３）。つまり、文字列分割パターン選択部１２４は、確率テーブル１３３に示される文Ｓの確率（α［ｔ］［ｋ］）の値を参照して、文Ｓの末尾側からの単語分割Ｗを確率的にサンプリングする。つまり、前記したＳ２０２の処理により、文Ｓの末尾ｋ文字の文字列ＳＮ-ｋ＋１：Ｎが１単語となる確率が確率テーブル１３３に記録されている。よって、文字列分割パターン選択部１２４は、この確率テーブル１３３に示される確率に従い、文末を表す特殊文字ｗ０＝ＥＯＳ（End Of Sentence）から、その文の文頭まで確率的にｋをサンプルする。つまり、文字列分割パターン選択部１２４は、まず、確率テーブル１３３に示される文Ｓのｗ０＝ＥＯＳに続く確率Ｐ（ｗ０＝ＥＯＳ｜ｓＮ-ｋ＋１：Ｎ）・α［Ｎ］［ｋ］に比例してｋを確率的にサンプリングする。例えば、ＥＯＳに続く確率Ｐ（ｗ０＝ＥＯＳ｜ＳＮ-ｋ＋１：Ｎ）・α［Ｎ］［ｋ］に基づき、図７の符号７０１，７０２，７０３，７０４に示す文字列それぞれからＥＯＳに続く確率に比例して、ＥＯＳに続く文字列を選択する。このようにして、文字列分割パターン選択部１２４は、ｗｏ＝ＥＯＳに続く単語の文字列ｗ１＝ＳＮ-ｋ＋１：Ｎを選択すると、次に、このｗ１＝ｓＮ-ｋ＋１：Ｎに続く単語をｐ（ポインタ）＝Ｎ−ｋとおいて、前記した手順と同様の手順により、ｗ１に続く確率Ｐ（ｗ１｜ｓｐ−ｋ＋１：ｐ）・α［ｐ］［ｋ］に従って、ｋを選ぶ。
【００５４】
図４の説明に戻る。文字列分割パターン選択部１２４は、以上のような処理を文Ｓの文字列すべてを使い切るまで、つまり、ｐ（ポインタ）が文Ｓの文頭に来るまで実行する。ここで、まだｐ（ポインタ）が文Ｓの文頭に来ていないとき（Ｓ２０４のＮｏ）、Ｓ２０３に戻る。一方、ｐ（ポインタ）が文Ｓの文頭に来たとき（Ｓ２０４のＹｅｓ）、文字列分割パターン選択部１２４は、この文字列の分割（文字列分割パターン）を出力し（Ｓ２０５）、文字列分割サンプリング処理を終了する。
【００５５】
文字列分割パターン選択部１２４は、具体的には、以下の処理を行う。
ｗｏ＝ＥＯＳ、ｐ＝Ｎ、ｉ＝０とする。但し、ｐ：ポインタ、ｉ：インデクスである。
以下の式（３）に従って、文末からの文字列ｋをサンプリングする。
Ｐ（ｋ）∝Ｐ（ｗｉ｜ｓｐ-ｋ＋１：ｐ，Θ）・α［ｐ］［ｋ］…式（３）
但し、１≦ｋ≦ｐとする。
次に、ｗｉ＝ｓｐ-ｋ＋１：ｐ、ｐ＝ｐ−ｋ、ｉ＝ｉ＋１に更新する。ここで、ｐ＞０ならば、再度、文末側から文字列ｋをサンプリングする。そうでなければ終了する。つまり、ｐが文Ｓの文頭に来た段階で、Ｗ＝ｗｉｗｉ−２…ｗ１が得られている。この後、図２のＳ１０３へ進み、言語モデル更新部１２５は、言語モデル１３２を更新する。
【００５６】
このようにすることで、言語モデル作成装置１０は、教師データを用いることなく、精度の高い言語モデルの作成および単語分割を行うことができる。また、言語モデル作成装置１０は、動的計画法により単語分割のサンプリングを行うので、効率よく単語分割の推測を行うことができる。
【００５７】
＜第２の実施の形態＞
次に、第２の実施の形態の言語モデル作成装置１０Ａを説明する。言語モデル作成装置１０Ａは、図２のＳ１０２における文字列分割サンプリング処理において、Particle MCMC法（Arnaud Doucet, Christophe Andrieu,and Roman Holenstein .Particle Markov Chain Monte Carlo,in submission,2008参照）を用いて文字列分割のサンプリングを行うことを特徴とする。
【００５８】
このParticle MCMC法は、粒子と呼ばれるモンテカルロサンプルを、１つの文につき所定数（ここでは、Ｊ個）、並列にサンプリングを行う。ここでのモンテカルロサンプリングの概要を、図８を用いて説明する。
【００５９】
言語モデル作成装置１０Ａは、与えられた文Ｓについて、言語モデル１３２に基づく単語分割を、文字列先頭から文字列末まで確率的にＪ通り行う。つまり、言語モデル作成装置１０Ａは、動的計画法によらず、Ｊ個の粒子（文字列分割パターン）を並列に作成する。このとき、言語モデル作成装置１０Ａは、このＪ通りの文字列分割パターンＷ（ｊ）を作成するとともに、その確率Ｐ（Ｗ（ｊ）｜Ｓ）を得ることができる。この後、言語モデル作成装置１０Ａは、このＰ（Ｗ（ｊ）｜Ｓ）に基づいた文Ｓの分割について、Ｗ（１）Ｗ（２）…Ｗ（Ｊ）（粒子＃１〜＃Ｊ）の中から、確率Ｐ（Ｗ（１）｜Ｓ）Ｐ（Ｗ（２）｜Ｓ）…Ｐ（Ｗ（Ｊ）｜Ｓ）に比例してランダムに選択すればよい。
【００６０】
但し、このＪ通りの文字列分割パターンが、目的とする確率分布Ｐ（Ｗ｜Ｓ）からの正しいサンプル群でない可能性もある。つまり、言語モデル作成装置１０Ａが、たまたま確率Ｐ（Ｗ（ｊ）｜Ｓ）の低い文字列分割パターン群を作成している可能性もある。そこで、まず、言語モデル作成装置１０Ａは、Ｊ通りの文字列分割パターン（粒子＃１〜＃Ｊ）の分割確率Ｐ（Ｗ（ｊ）｜Ｓ）の平均値を以下の式（４）により計算する。
【数４】
2010170252.tif 000006
【００６１】
また、言語モデル作成装置１０Ａは、前回作成した文字列分割パターン群と、その文字列分割パターン群の分割確率Ｐ（Ｗ（ｊ）｜Ｓ）の平均値Ｚ＾（Ｓ）とを記憶しておく。なお、言語モデル作成装置１０Ａが最初に文字列分割パターン群を作成するときには、文字列分割パターン群の作成を２回実行し、最初に作成した文字列分割パターン群のＰ（Ｗ（ｊ）｜Ｓ）の平均値Ｚ（Ｓ）を、Ｚ＾（Ｓ）とする。
【００６２】
そして、言語モデル作成装置１０Ａは、このＺ（Ｓ）とＺ＾（Ｓ）とを比較し、（１）Ｚ（Ｓ）＞Ｚ＾（Ｓ）であれば、今回作成した文字列分割パターン群による分割を受理する。つまり、言語モデル作成装置１０Ａは、今回作成した文字列分割パターン群Ｗ（１）Ｗ（２）…Ｗ（Ｊ）の中から、確率Ｐ（Ｗ（１）｜Ｓ）Ｐ（Ｗ（２）｜Ｓ）…Ｐ（Ｗ（Ｊ）｜Ｓ）に比例して、文字列分割パターンを選択し、Ｚ＾（Ｓ）をＺ（Ｓ）に置き換える。
【００６３】
一方、（２）Ｚ（Ｓ）≦Ｚ＾（Ｓ）であれば、言語モデル作成装置１０Ａは、Ｚ（Ｓ）／Ｚ＾（Ｓ）の確率で分割を受理する。つまり、Ｚ（Ｓ）／Ｚ＾（Ｓ）の確率でベルヌーイ試行を行い、今回作成した文字列分割パターン群を受理するか否かを決定する。ここで、今回作成した文字列分割パターン群による分割を受理すると決定したとき、前記したとおり、文字列分割パターン群Ｗ（１）Ｗ（２）…Ｗ（Ｊ）の中から、文字列分割パターンを選択し、Ｚ（Ｓ）をＺ＾（Ｓ）とする。一方、今回作成した文字列分割パターン群による分割を受理しないと決定したときは、そのまま処理を終了する。このようにすることで、言語モデル作成装置１０Ａは、正しいMCMC法となり、真の分布に近い確率で文字列分割パターンを選択できる。
【００６４】
このような言語モデル作成装置１０Ａの構成を、図９に示す。前記した実施の形態と同様の構成要素は、同じ符号を付して説明を省略する。ここで、言語モデル作成装置１０Ａは、図３の文字列分割パターン作成部１２２にかえて、文字列分割パターン作成部１２２Ａを備える。この文字列分割パターン作成部１２２Ａは、前記したParticle MCMC法により１つの文につき所定数（Ｊ個）のモンテカルロサンプル（文字列分割パターン）を作成する。さらに、言語モデル作成装置１０Ａは、図３の確率テーブル１３３にかえて、確率テーブル１３３Ａを備える。この確率テーブル１３３Ａは、Particle MCMC法により得られた各文字列分割パターンおよびその文字列分割パターンの確率を記録したものである。また、言語モデル作成装置１０Ａは、今回作成した文字列分割パターン群による文字列分割を受理するか否かを判定する分割受理判定部１２９を備える。この分割受理判定部１２９は、今回作成した文字列分割パターン群の分割確率Ｐ（Ｗ（ｊ）｜Ｓ）の平均値Ｚ（Ｓ）と、前回作成した文字列分割パターン群の分割確率Ｐ（Ｗ（ｊ）｜Ｓ）の平均値Ｚ＾（Ｓ）とを比較して、Ｚ（Ｓ）＞Ｚ＾（Ｓ）であれば、今回作成した文字列分割パターン群による分割を受理する。一方、Ｚ（Ｓ）≦Ｚ＾（Ｓ）であれば、Ｚ（Ｓ）／Ｚ＾（Ｓ）の確率でベルヌーイ試行を行い、文字列分割パターン群による分割を受理するか否かを決定する。なお、言語モデル作成装置１０Ａの文字列分割パターン作成部１２２Ａは、文字列分割パターン群の作成とともにその文字列分割パターンの確率の計算も行うので、言語モデル作成装置１０の確率計算部１２３を含まない構成となっている。
【００６５】
このような言語モデル作成装置１０Ａによる文字列分割サンプリング処理（図２のＳ１０２）を、図１０を用いて説明する。ここでも言語モデル作成装置１０Ａは、Ｊ通りの文字列分割パターン（粒子＃１〜＃Ｊ）を作成するものとする。
【００６６】
まず、図９の言語モデル作成装置１０Ａのパラメータ読み込み部１２０は、言語モデル１３２からパラメータの読み込みを行う（Ｓ３０１）。そして、文字列分割パターン作成部１２２Ａは、まず、ｊ＝１をセットする（Ｓ３０２）。次に、文字列分割パターン作成部１２２Ａは、Ｓ３０１で読み込まれた言語モデル１３２のパラメータに基づき、粒子ｊの文字列分割処理を実行する（Ｓ３０３）。つまり、文字列分割パターン作成部１２２Ａは、文Ｓについて、文頭文字列から文末文字列まで、言語モデル１３２のパラメータに基づき、文字列分割を行い、粒子ｊである文字列分割パターンを作成する。このとき、作成した文字列分割パターンと、その確率Ｐ（Ｗ（ｊ）｜Ｓ）とを確率テーブル１３３Ａに記録しておく。そして、ｊの値を１加算し（Ｓ３０４）、ｊ＝Ｊでなければ（Ｓ３０５のＮｏ）、Ｓ３０３へ戻る。一方、ｊ＝Ｊであるとき（Ｓ３０５のＹｅｓ）、つまり、文字列分割パターン作成部１２２ＡがＪ通りの文字列分割パターン群（粒子）の作成を完了したとき、分割受理判定部１２９は、この文字列分割パターン群による分割を受理するか否かを判断する（Ｓ３０６）。Ｓ３０６の処理の詳細は、後記する。
【００６７】
そして、Ｓ３０６において、分割受理判定部１２９が、今回作成した文字列分割パターン群による分割を受理すると判断したとき（Ｓ３０６のＹｅｓ）、この文字列分割パターン群の中から選択した単語分割Ｗを出力する（Ｓ３０７）。つまり、文字列分割パターン選択部１２４は、確率テーブル１３３Ａに示される、今回作成した文字列分割パターン群の文字列分割パターンそれぞれの分割確率に従い、この文字列分割パターン群の中から文字列分割パターンを選択する。そして、その選択した文字列分割パターンを記憶部１３に出力する。また、記憶部１３に記憶されたＺ＾（Ｓ）を、今回作成した文字列分割パターン群のＺ（Ｓ）の値に置き換える。このＺ＾（Ｓ）の値は、次回作成される文字列分割パターン群の確率の平均値（Ｚ（Ｓ））との比較に用いられる。一方、Ｓ３０６において、分割受理判定部１２９が今回作成した文字列分割パターン群による分割を受理しないと判断したとき（Ｓ３０６のＮｏ）、Ｓ３０７を実行せず、処理を終了する。この場合、分割受理判定部１２９は、記憶部１３に記憶された、前回の文字列分割パターン群から選択した文字列分割パターン（単語分割Ｗ）を、言語モデル更新部１２５へ出力する。そして、言語モデル更新部１２５は、この出力された単語分割Ｗを用いて言語モデル１３２を更新することになる。このような処理を繰り返すことで、この言語モデル作成装置１０Ａは、確率の平均値がたまたま低くなってしまった文字列分割パターン群をサンプリングの対象外とし、真の分布に近い文字列分割パターン群からのサンプリングを実行できる。
【００６８】
次に、図１１を用いて、図１０のＳ３０６の分割受理の判定およびＳ３０７の単語分割の出力の詳細を説明する。まず、図９の分割受理判定部１２９は、前記した式（４）に基づき、文字列分割パターン群の確率Ｐ（Ｗ（ｊ）｜Ｓ）の平均値Ｚ（Ｓ）を計算する（Ｓ４０１）。そして、分割受理判定部１２９は、記憶部１３に記憶された、前回作成した文字列分割パターン群の確率Ｐ（Ｗ（ｊ）｜Ｓ）の平均値Ｚ＾（Ｓ）の計算結果を読み出す（Ｓ４０２）。次に、分割受理判定部１２９は、このＺ（Ｓ）とＺ＾（Ｓ）とを比較し、Ｚ（Ｓ）＞Ｚ＾（Ｓ）であれば（Ｓ４０３のＹｅｓ）、今回作成した文字列分割パターン群による分割を受理し、この文字列分割パターン群による単語分割Ｗを記憶部１３へ出力し、また、Ｚ＾（Ｓ）＝Ｚ（Ｓ）に置き換える（Ｓ４０６）。
【００６９】
一方、Ｓ４０３において、Ｚ（Ｓ）≦Ｚ＾（Ｓ）であれば（Ｓ４０３のＮｏ）、分割受理判定部１２９は、Ｚ（Ｓ）／Ｚ＾（Ｓ）の確率で、今回作成した文字列分割パターン群による分割を受理する（Ｓ４０４）。つまり、分割受理判定部１２９は、Ｚ（Ｓ）／Ｚ＾（Ｓ）の確率でベルヌーイ試行を実行し、今回作成した文字列分割パターン群による分割を受理するか否かを決定する。すなわち、分割受理判定部１２９は、Ｚ（Ｓ）がＺ＾（Ｓ）に近い値であれば、高い確率で今回の文字列分割パターン群による分割を受理し、Ｚ（Ｓ）がＺ＾（Ｓ）よりもはるかに低い値であれば、それに応じて低い確率で今回作成した文字列分割パターン群による分割を受理する。ここで、分割受理判定部１２９が、今回作成した文字列分割パターン群による分割を受理すると決定したときには（Ｓ４０５のＹｅｓ）、Ｓ４０６へ進む。一方、分割受理判定部１２９が、今回作成した文字列分割パターン群による分割を受理しないと決定したときは（Ｓ４０５のＮｏ）、Ｓ４０６を実行せず、処理を終了する。
【００７０】
ここで、図１０に示した処理を具体的に説明する。まず、図９の文字列分割パターン選択部１２４は、以下の処理手順でサンプリングを行う。
【００７１】
（１）文頭を表す特殊文字を文末と同じＥＯＳとして、ｉ（単語のインデックス）＝０、ｊ＝１、Ｐ（Ｗ（ｊ）｜Ｓ）＝１、ｗｉ（ｊ）＝ＥＯＳとする（図１０のＳ３０１）。
（２）次に、文Ｓにおいて、ｗｉに続くべき文字列の長さｋを、言語モデル１３２の予測確率に従ってサンプリングする。すなわち、ｗｉに続くべき文字列の長さｋをＰ（ｓｐ：ｐ＋ｋ−１｜ｗ０（ｊ），…，ｗｉ（ｊ））に従ってサンプリングする（Ｓ３０３）。ここで、ｗｉに続くべき文字列の長さｋは、これまでに予測が確定した単語文脈（ｗ０（ｊ），…，ｗｉ（ｊ））すべてに依存し、着目している単語の１単語までまたは２単語までという制約は必要ない。
（３）そして、Ｐ（Ｗ（ｊ）｜Ｓ）＝Ｐ（Ｗ（ｊ）｜Ｓ）・Ｐ（Ｓｐ：ｐ＋ｋ−１｜ｗ０（ｊ），…，ｗｉ（ｊ））、ｗｉ（ｊ）＝ｓｐ：ｐ＋ｋ−１、ｐ＝ｐ＋ｋ、ｉ＝ｉ＋１に更新する。
（４）ここで、ｐ＜Ｎ（Ｎ＝文Ｓの文字列の長さ）ならば、（２）へ戻る。ｐ＝Ｎならば、文字列分割パターンが１つ完成したことになるので、ｊ＝ｊ＋１に更新する（Ｓ３０４）。
（５）ここで、ｊ＝Ｊならば文字列分割パターン（粒子）をＪ通り作成したことになるので（Ｓ３０５のＹｅｓ）、（６）へ進む。一方、ｊ＝Ｊでなければ（Ｓ３０５のＮｏ）、つまり、文字列分割パターンをＪ通り作成していなければ、（２）へ戻る。
【００７２】
次に、分割受理判定部１２９は、以下の手順により、（５）までの処理で作成した文字列分割パターン群による分割を受理するか否かを決定する（Ｓ３０６）。すなわち、
（６）文字列分割パターン群の確率Ｐ（Ｗ（ｊ）｜Ｓ）の平均値Ｚ（Ｓ）について、二値変数ａを、ベルヌーイ試行Bernoulli（min（１，Ｚ（Ｓ）／Ｚ＾（Ｓ）））によりサンプリングする。なお、Ｚ＾（Ｓ）は、前記したとおり、MCMC法で前回作成した文字列分割パターン群の確率Ｐ（Ｗ（ｊ）｜Ｓ）の平均値Ｚ（Ｓ）であり、MCMC法の最初の繰り返しでは、この値を１とする。ここで、min（１，Ｚ（Ｓ）／Ｚ＾（Ｓ））であるので、Ｚ（Ｓ）＜Ｚ＾（Ｓ）であれば、Ｚ（Ｓ）／Ｚ＾（Ｓ）が選択されることになる。そして、ベルヌーイ試行の結果、得られた二値変数ａ＝０ならば、ここで処理を終了する。つまり、文字列分割パターン作成部１２２Ａによる文字列分割パターン郡の作成は行わず、分割受理判定部１２９は、記憶部１３に記憶された、前回の文字列分割パターン群から選択した文字列分割パターン（単語分割Ｗ）を、言語モデル更新部１２５へ出力する。そして、言語モデル更新部１２５は、この文字列分割パターン（単語分割Ｗ）により言語モデル１３２を更新する（図２のＳ１０３）。一方、得られた二値変数ａ＝１ならば、今回作成した文字列分割パターン群のＷ（１）Ｗ（２）…Ｗ（Ｊ）の中から、確率Ｐ（Ｗ（１）｜Ｓ）Ｐ（Ｗ（２）｜Ｓ）…Ｐ（Ｗ（Ｊ）｜Ｓ）に比例して、文字列分割パターン（単語分割Ｗ）を選択し、出力する。そして、Ｚ＾（Ｓ）＝Ｚ（Ｓ）に置き換える。
【００７３】
このように言語モデル作成装置１０Ａは、Particle MCMC法によりサンプリングを行うので、言語モデル１３２が３グラム以上の言語モデルであっても、言語モデルの最適化のための計算量が膨大になることがない。また、この言語モデル作成装置１０Ａは、確率の平均値がたまたま低くなってしまった文字列分割パターン群をサンプリングの対象外とするので、言語モデル作成装置１０Ａは、真の分布に近い文字列分割パターン群からサンプリングを実行できる。
【００７４】
なお、前記した各実施の形態において、言語モデル作成装置１０，１０Ａが学習用データとして用いるデータは、主に自然言語の文字列であるものとして説明したが、マルコフ性（将来の状態の条件付確率分布が現在の状態のみに依存する）離散データ一般に適用可能である。例えば、ＤＮＡの時系列データ、音符の時系列データ、二進ビット列等を適切な単位に分割し、その間の遷移関係を与えるモデルを最適化する場合にも適用可能である。
【００７５】
また、言語モデル作成装置１０で扱う言語モデル１３２は、２グラムの場合を例に説明したが、３グラムであってもよい。この場合、文Ｓのｔ番目の文字列のｋ文字前に単語境界、さらにそのj文字前に単語境界がある確率をα［ｔ］［ｋ］［ｊ］とすることで、同様の分割サンプリング処理を実行することができる。
【００７６】
本実施の形態に係る言語モデル作成装置１０，１０Ａは、前記したような処理を実行させるプログラムによって実現することができ、そのプログラムをコンピュータによる読み取り可能な記録媒体（ＣＤ−ＲＯＭ等）に記憶して提供することが可能である。
【符号の説明】
【００７７】
１０，１０Ａ    言語モデル作成装置
１１    入出力部
１２    処理部
１３    記憶部
１２０  パラメータ読み込み部
１２１  文選択部
１２２，１２２Ａ  文字列分割パターン作成部
１２３  確率計算部
１２４  文字列分割パターン選択部
１２５  言語モデル更新部
１２６  収束判定部
１２７  最尤単語分割計算部
１２８  出力処理部
１２９  分割受理判定部
１３１  文字列データ
１３２  言語モデル
１３３，１３３Ａ  確率テーブル
【図１】
2010170252.tif 000008
【図２】
2010170252.tif 000009
【図３】
2010170252.tif 000010
【図４】
2010170252.tif 000011
【図５】
2010170252.tif 000012
【図６】
2010170252.tif 000013
【図７】
2010170252.tif 000014
【図８】
2010170252.tif 000015
【図９】
2010170252.tif 000016
【図１０】
2010170252.tif 000017
【図１１】
2010170252.tif 000018