(57)【特許請求の範囲】
【請求項１】
入力構造ｘに対する出力構造ｙを予測するために利用される構造予測モデルを、教師データＤＬ及び教師なしデータＤＵを用いて学習する構造予測モデル学習装置であって、Ｋを自然数とし、ｋ∈｛１，２，…，Ｋ｝とし、
構造予測問題により特定される出力候補生成用定義データ集合を用いて、教師データに対する教師データ用出力候補グラフを生成し、教師なしデータに対する教師なしデータ用出力候補グラフを生成する出力候補グラフ生成部と、
特徴抽出テンプレートを用いて、前記教師データ用出力候補グラフ及び前記教師なしデータ用出力候補グラフから特徴を抽出し、前記教師データ用出力候補グラフから抽出した特徴の集合に対するＤ次元の基本モデル用特徴ベクトルｆｘ，ｙを生成し、前記教師なしデータ用出力候補グラフから抽出した特徴の集合をＫ個の部分集合に分割し、部分集合ｋに含まれる特徴に対するＤｋ次元の補助モデル用特徴ベクトルｇ（ｋ）ｘ，ｙを生成する特徴ベクトル生成部と、
基本モデル用特徴ベクトルｆｘ，ｙのＤ個の要素にそれぞれ１対１対応するＤ個の第１パラメタで構成される第１パラメタ集合ｗを含む基本モデル用パラメタ集合λを生成し、補助モデル用特徴ベクトルｇ（ｋ）ｘ，ｙのＤｋ個の要素にそれぞれ１対１対応するＤｋ個の補助モデル用パラメタで構成される補助モデル用パラメタ集合θ（ｋ）を生成し、Ｋ個の補助モデル用パラメタ集合θ（ｋ）で構成される補助モデル用パラメタ集合の集合Θ＝｛θ（１），θ（２），…，θ（Ｋ）｝を生成するパラメタ生成部と、
各補助モデルｑｋは前記補助モデル用パラメタ集合θ（ｋ）を対数線形モデルにより定義するものとし、前記補助モデル用パラメタ集合θ（ｋ）から得られる正則化項と前記教師なしデータＤＵを用いて、非負関数であって、入力構造ｘに対する出力構造ｙの擬似的な正解の度合いを表す参照関数ｒ~（ｘ，ｙ）と前記補助モデルｑｋとの間の正則化項付
きブレグマン距離を最小にする補助モデル用パラメタ集合の集合Θを推定する補助モデル用パラメタ推定部と、
前記基本モデル用パラメタ集合λは、Ｋ個の前記補助モデルとそれぞれ１対１対応するＫ個の第２パラメタで構成される第２パラメタ集合ｖ＝｛ｖ１，ｖ２，…,ｖＫ｝を含む
ものとし、前記教師データＤＬと前記補助モデル用パラメタ集合の集合Θを用いて、事前に定義された経験リスク関数を最小にする前記基本モデル用パラメタ集合λを推定する基本モデル用パラメタ推定部とを備え、
ＣＵをハイパーパラメタ、Ｇ＾ＤＵ（ｒ~||ｑｋ）を教師なしデータＤＵを使った実測値を用いて得られる一般化相対エントロピーとし、前記補助モデル用パラメタ推定部は、補助モデル用パラメタ集合θ（ｋ）を用いてＬ１ノルム正則化項｜θ（ｋ）｜１を求め、前記ブレグマン距離を、正則化項付き経験一般化相対エントロピー
【数５２】
0005250076.tif 000042
として求め、正則化項付き経験一般化相対エントロピーを最小にする前記補助モデル用パラメタ集合の集合Θを推定する、
ことを特徴とする構造予測モデル学習装置。
【請求項２】
請求項１記載の構造予測モデル学習装置であって、
前記基本モデル用パラメタ集合λと前記補助モデル用パラメタ集合の集合Θの値が、収束したか否かを判定する収束判定部と、
収束した前記基本モデル用パラメタ集合λと前記補助モデル用パラメタ集合の集合Θを統合するパラメタ統合部と、をさらに備え、
前記収束判定部において、前記基本モデル用パラメタ集合λと前記補助モデル用パラメタ集合の集合Θの値が、収束していないと判定された場合には、前記補助モデル用パラメタ推定部と前記基本モデル用パラメタ推定部において、それぞれ補助モデル用パラメタ集合の集合Θと基本モデル用パラメタ集合λを推定する処理を繰り返し、
前記参照関数ｒ~は、繰り返し処理における１つ前の基本モデルＰである、
ことを特徴とする構造予測モデル学習装置。
【請求項３】
請求項１記載の構造予測モデル学習装置であって、
ＣＬをハイパーパラメタ、ｄ（ｘ，ｙ；λ，Θ）を入力構造ｘに対して出力構造ｙが得られる可能性を表すスコアを返す判別関数、Ｅ（ｙ，ｙ＾）をある正解の出力ｙと任意の出力ｙ＾を比較した際のｙ＾の誤りの度合いを表す関数、Ａ＼Ｂを集合Ａから集合Ｂを取り去って得られる差集合、Ｙ（ｘ）を入力構造ｘから生成できる全ての出力候補の集合とし、
前記基本モデル用パラメタ推定部は、基本モデル用パラメタ集合λから得られる正則化項Ω（λ）を用いて、前記経験リスク関数を正則化項付き経験リスク関数
Ｌ（λ｜Θ，ＤＬ）＝Ｒ（λ｜Θ，ＤＬ）＋ＣＬΩ（λ）として求め、経験リスク関数として、負の対数尤度を用いる場合には、
【数４１】
0005250076.tif 000043
とし、線形識別モデルでのマージン最大化に基づき、Ｌ（λ｜Θ，ＤＬ）を最小にする前記基本モデル用パラメタ集合λを推定する場合には、
【数４２】
0005250076.tif 000044
とする、
ことを特徴とする構造予測モデル学習装置。
【請求項４】
請求項１記載の構造予測モデル学習装置であって、
入力構造ｘが与えられたときに出力構造ｙが出力される条件付確率をｑ１ｋ（ｙ｜ｘ；θ（ｋ））とし、ｑ１ｋのオッズをｑ’１ｋとし、ｂ（ｙ）を１以上の値を返す関数とし、ｃｏｎｓｔ（θ（ｋ））をθ（ｋ）に対して定数項になるものをまとめた値とし、
前記補助モデル用パラメタ推定部は、前記正則化付き経験一般化相対エントロピーを
【数４４】
0005250076.tif 000045
として、または、
【数４５】
0005250076.tif 000046
として求め、これを最小にする補助モデル用パラメタ集合の集合Θを推定する、
ことを特徴とする構造予測モデル学習装置。
【請求項５】
請求項１記載の構造予測モデル学習装置であって、
入力構造ｘが与えられたときに出力構造ｙに局所構造ｚが出力される条件付確率をｑ２ｋ（ｚ｜ｘ；θ（ｋ））とし、ｑ２ｋのオッズをｑ’２ｋとし、ｂ（ｚ）を局所的構造ｚの対立候補となる局所的構造の個数とし、ｃｏｎｓｔ（θ（ｋ））をθ（ｋ）に対して定数項になるものをまとめた値とし、
前記補助モデル用パラメタ推定部は、前記正則化付き経験一般化相対エントロピーを
【数４６】
0005250076.tif 000047
として、または、
【数４７】
0005250076.tif 000048
として求め、これを最小にする補助モデル用パラメタ集合の集合Θを推定する、
ことを特徴とする構造予測モデル学習装置。
【請求項６】
請求項１記載の構造予測モデル学習装置であって、
入力構造ｘが与えられたときに出力構造ｙに特徴ｎを備える局所構造ｚが出力される条件付確率をｑ３ｋ（ｚ｜ｘ，ｎ；θ（ｋ））とし、ｑ３ｋのオッズをｑ’３ｋとし、ｎ＝１，２，…，Ｄｋとし、θ（ｋ）＝（θ（ｋ）１，θ（ｋ）２，…，θ（ｋ）Ｄｋ）、ｇ（ｋ）ｘ，ｚ＝（ｇ（ｋ）ｘ，ｚ，１，ｇ（ｋ）ｘ，ｚ，２，…，ｇ（ｋ）ｘ，ｚ，Ｄｋ）とし、ｂ（ｚ）を局所的構造ｚの対立候補となる局所的構造の個数とし、ｃｏｎｓｔ（θ（ｋ）ｎ）をθ（ｋ）ｎに対して定数項になるものをまとめた値とし、
前記補助モデル用パラメタ推定部は、前記正則化付き経験一般化相対エントロピーを
【数４８】
0005250076.tif 000049
として、または、
【数４９】
0005250076.tif 000050
として求め、これを最小にする補助モデル用パラメタ集合の集合Θを推定する、
ことを特徴とする構造予測モデル学習装置。
【請求項７】
出力候補グラフ生成部と特徴ベクトル生成部とパラメタ生成部と補助モデル用パラメタ推定部と基本モデル用パラメタ推定部とを備える構造予測モデル学習装置によって、入力構造ｘに対する出力構造ｙを予測するために利用される構造予測モデルを、教師データＤＬ及び教師なしデータＤＵを用いて学習する構造予測モデル学習方法であって、Ｋを自然数とし、ｋ∈｛１，２，…，Ｋ｝とし、
前記出力候補グラフ生成部が、構造予測問題により特定される出力候補生成用定義データ集合を用いて、教師データに対する教師データ用出力候補グラフを生成し、教師なしデータに対する教師なしデータ用出力候補グラフを生成する出力候補グラフ生成ステップと、
前記特徴ベクトル生成部が、特徴抽出テンプレートを用いて、前記教師データ用出力候補グラフ及び前記教師なしデータ用出力候補グラフから特徴を抽出し、前記教師データ用出力候補グラフから抽出した特徴の集合に対するＤ次元の基本モデル用特徴ベクトルｆｘ，ｙを生成し、前記教師なしデータ用出力候補グラフから抽出した特徴の集合をＫ個の部分集合に分割し、部分集合ｋに含まれる特徴に対するＤｋ次元の補助モデル用特徴ベクトルｇ（ｋ）ｘ，ｙを生成する特徴ベクトル生成ステップと、
前記パラメタ生成部が、基本モデル用特徴ベクトルｆｘ，ｙのＤ個の要素にそれぞれ１対１対応するＤ個の第１パラメタで構成される第１パラメタ集合ｗを含む基本モデル用パラメタ集合λを生成し、補助モデル用特徴ベクトルｇ（ｋ）ｘ，ｙのＤｋ個の要素にそれぞれ１対１対応するＤｋ個の補助モデル用パラメタで構成される補助モデル用パラメタ集合θ（ｋ）を生成し、Ｋ個の補助モデル用パラメタ集合θ（ｋ）で構成される補助モデル用パラメタ集合の集合Θ＝｛θ（１），θ（２），…，θ（Ｋ）｝を生成するパラメタ生成ステップと、
各補助モデルｑｋは前記補助モデル用パラメタ集合θ（ｋ）を対数線形モデルにより定義するものとし、前記補助モデル用パラメタ推定部が、前記補助モデル用パラメタ集合θ（ｋ）から得られる正則化項と前記教師なしデータＤＵを用いて、非負関数であって、入力構造ｘに対する出力構造ｙの擬似的な正解の度合いを表す参照関数ｒ~（ｘ，ｙ）と前記補助モデルｑｋとの間の正則化項付きブレグマン距離を最小にする補助モデル用パラメタ集合の集合Θを推定する補助モデル用パラメタ推定ステップと、
前記基本モデル用パラメタ集合λは、Ｋ個の前記補助モデルとそれぞれ１対１対応するＫ個の第２パラメタで構成される第２パラメタ集合ｖ＝｛ｖ１，ｖ２，…,ｖＫ｝を含むものとし、前記基本モデル用パラメタ推定部が、前記教師データＤＬと前記補助モデル用パラメタ集合の集合Θを用いて、事前に定義された経験リスク関数を最小にする前記基本モデル用パラメタ集合λを推定する基本モデル用パラメタ推定ステップとを備え、
ＣＵをハイパーパラメタとし、Ｇ＾ＤＵ（ｒ~||ｑｋ）を教師なしデータＤＵを使った実測値を用いて得られる一般化相対エントロピーとし、前記補助モデル用パラメタ推定ステップにおいて、前記補助モデル用パラメタ推定が、補助モデル用パラメタ集合θ（ｋ）を用いてＬ１ノルム正則化項｜θ（ｋ）｜１を求め、前記ブレグマン距離を、正則化項付き経験一般化相対エントロピー
【数５２】
0005250076.tif 000051
として求め、正則化項付き経験一般化相対エントロピーを最小にする前記補助モデル用パラメタ集合の集合Θを推定する、
ことを特徴とする構造予測モデル学習方法。
【請求項８】
請求項７記載の構造予測モデル学習方法であって、
前記構造予測モデル学習装置は、さらに、収束判定部と、パラメタ統合とを備え、
前記収束判定部が、前記基本モデル用パラメタ集合λと前記補助モデル用パラメタ集合の集合Θの値が、収束したか否かを判定する収束判定ステップと、
前記パラメタ統合が、収束した前記基本モデル用パラメタ集合λと前記補助モデル用パラメタ集合の集合Θを統合するパラメタ統合ステップと、をさらに備え、
前記収束判定ステップにおいて、前記基本モデル用パラメタ集合λと前記補助モデル用パラメタ集合の集合Θの値が、収束していないと判定された場合には、前記補助モデル用パラメタ推定ステップと前記基本モデル用パラメタ推定ステップにおいて、それぞれ補助モデル用パラメタ集合の集合Θと基本モデル用パラメタ集合λを推定する処理を繰り返し、
前記参照関数ｒ~は、繰り返し処理における１つ前の基本モデルＰである、
ことを特徴とする構造予測モデル学習方法。
【請求項９】
請求項７記載の構造予測モデル学習方法であって、
ＣＬをハイパーパラメタ、ｄ（ｘ，ｙ；λ，Θ）を入力構造ｘに対して出力構造ｙが得られる可能性を表すスコアを返す判別関数、Ｅ（ｙ，ｙ＾）をある正解の出力ｙと任意の出力ｙ＾を比較した際のｙ＾の誤りの度合いを表す関数、Ａ＼Ｂを集合Ａから集合Ｂを引いた差集合、Ｙ（ｘ）を入力構造ｘから生成できる全ての出力候補の集合とし、
前記基本モデル用パラメタ推定ステップは、基本モデル用パラメタ集合λから得られる正則化項Ω（λ）を用いて、前記経験リスク関数を正則化項付き経験リスク関数
Ｌ（λ｜Θ，ＤＬ）＝Ｒ（λ｜Θ，ＤＬ）＋ＣＬΩ（λ）
として求め、経験リスク関数として、負の対数尤度を用いる場合には、
【数５０】
0005250076.tif 000052
とし、線形識別モデルでのマージン最大化に基づき、Ｌ（λ｜Θ，ＤＬ）を最小にする前記基本モデル用パラメタ集合λを推定する場合には、
【数５１】
0005250076.tif 000053
とする、
ことを特徴とする構造予測モデル学習方法。
【請求項１０】
請求項７記載の構造予測モデル学習方法であって、
入力構造ｘが与えられたときに出力構造ｙが出力される条件付確率をｑ１ｋ（ｙ｜ｘ；θ（ｋ））とし、ｑ１ｋのオッズをｑ’１ｋとし、ｂ（ｙ）を１以上の値を返す関数とし、ｃｏｎｓｔ（θ（ｋ））をθ（ｋ）に対して定数項になるものをまとめた値とし、
前記補助モデル用パラメタ推定ステップは、前記正則化付き経験一般化相対エントロピーを
【数５３】
0005250076.tif 000054
として、または、
【数５４】
0005250076.tif 000055
として求め、これを最小にする補助モデル用パラメタ集合の集合Θを推定する、
ことを特徴とする構造予測モデル学習方法。
【請求項１１】
請求項７記載の構造予測モデル学習方法であって、
入力構造ｘが与えられたときに出力構造ｙに局所構造ｚが出力される条件付確率をｑ２ｋ（ｚ｜ｘ；θ（ｋ））とし、ｑ２ｋのオッズをｑ’２ｋとし、ｂ（ｚ）を局所的構造ｚの対立候補となる局所的構造の個数とし、ｃｏｎｓｔ（θ（ｋ））をθ（ｋ）に対して定数項になるものをまとめた値とし、
前記補助モデル用パラメタ推定ステップは、前記正則化付き経験一般化相対エントロピーを
【数５５】
0005250076.tif 000056
として、または、
【数５６】
0005250076.tif 000057
として求め、これを最小にする補助モデル用パラメタ集合の集合Θを推定する、
ことを特徴とする構造予測モデル学習方法。
【請求項１２】
請求項７記載の構造予測モデル学習方法であって、
入力構造ｘが与えられたときに出力構造ｙに特徴ｎを備える局所構造ｚが出力される条件付確率をｑ３ｋ（ｚ｜ｘ，ｎ；θ（ｋ））とし、ｑ３ｋのオッズをｑ’３ｋとし、ｎ＝１，２，…，Ｄｋとし、θ（ｋ）＝（θ（ｋ）１，θ（ｋ）２，…，θ（ｋ）Ｄｋ）、ｇ（ｋ）ｘ，ｚ＝（ｇ（ｋ）ｘ，ｚ，１，ｇ（ｋ）ｘ，ｚ，２，…，ｇ（ｋ）ｘ，ｚ，Ｄｋ）とし、ｂ（ｚ）を局所的構造ｚの対立候補となる局所的構造の個数とし、ｃｏｎｓｔ（θ（ｋ）ｎ）をθ（ｋ）ｎに対して定数項になるものをまとめた値とし、
前記補助モデル用パラメタ推定ステップは、前記正則化付き経験一般化相対エントロピーを
【数５７】
0005250076.tif 000058
として、または、
【数５８】
0005250076.tif 000059
として求め、これを最小にする補助モデル用パラメタ集合の集合Θを推定する、
ことを特徴とする構造予測モデル学習方法。
【請求項１３】
請求項１記載の構造予測モデル学習装置として、コンピュータを機能させるためのプログラム。
【請求項１４】
請求項１記載の構造予測モデル学習装置として、コンピュータを機能させるためのプログラムを記録したコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、機械学習の手法に関する。特に、本発明は、離散的な構造（いわゆるグラフ）で記述される入力構造に対して、出力構造を予測する「構造予測器」において用いる構造予測モデルを学習する装置、方法、プログラム及び記録媒体に関する。機械学習は、予め用意された学習用のデータから、有用な規則性、知識表現、判断基準などを学習（抽出）する技術である。
【背景技術】
【０００２】
ある情報に対して、その背後の隠された構造を予測する問題は、「構造予測問題」と呼ぶ。入力構造に対する出力構造を予測する装置（またはプログラム）は「構造予測器」と呼ぶ。なお、入力構造及び出力構造は任意の離散構造であり、いわゆるグラフによって記述できる構造（ノード集合とエッジ集合からなる構造）である。さらに入力および出力構造はラベルつきグラフにより記述できる構造である（ノード、および／または、エッジにラベルが付与されているグラフ）。この構造予測器において利用されるモデルを構造予測モデルと呼ぶ。構造予測モデルは、入力構造に対して最も尤もらしい出力構造を予測するモデルである。
【０００３】
実世界の構造予測問題としては、例えば、（１）テキストデータに対して、その文法・意味的な構造を予測する問題、（２）遺伝子配列データに対して、蛋白質の構造を予測する問題、（３）画像データに対して、画像データ中の物体を予測（認識）する問題、（４）人と人や事柄間の関係を表現するデータに対して、そのネットワーク構造を予測する問題、等がある。
【０００４】
計算機上で処理される実世界の問題のいくつかは（例えば上記（１）〜（４）に関する問題）、計算機で扱い易い形式に変換する段階で、構造予測問題として定式化できる。その例を図１から図３に示す。但し、ここでは、数式上での記述として、入力構造をｘ、出力構造をｙとする。ｘは可能な全ての入力の集合Ｘの要素の一つであり、ｘ∈Ｘである。ｙも同様に、可能な全ての出力の集合Ｙの要素の一つであり、ｙ∈Ｙである。但し、出力構造ｙは入力構造ｘに依存して決まるので、ｙはｘが与えられた時の可能な全ての出力集合Ｙ（ｘ）の要素の一つとなり、ｙ∈Ｙ（ｘ）となる。また、Ｙ（ｘ）⊆Ｙである。
【０００５】
図１は、系列構造予測問題のうち英語のテキストから固有表現を抽出する問題に関するものを示す。図１は、固有名詞に対して固有名詞の種類を示すラベルを付与する例を示す。
【０００６】
入力構造ｘは、「U.N. official John Smith heads for Baghdad on July 4th .」のように、１１個のトークン（または単語）に区切られている。このうち、「U.N.」、「John」、「Smith」、「Baghdad」、「July」、「4th」の６つのトークンは、それぞれ対応するラベル「ＯＲＧ．」、「ＰＥＲ．」、「ＰＥＲ．」、「ＬＯＣ．」、「ＤＡＴＥ」、「ＤＡＴＥ」が付与されている。なお、「ＰＥＲ．」はPerson Nameを、「ＬＯＣ．」はLocation Nameを、「ＯＲＧ．」はOrganization Nameを表す。
【０００７】
図２は、木構造予測問題のうち、英語のテキスト内の依存構造を解析する問題に関するものを示す。図２は、トークン（または単語）に対して文法的な係り受け関係を示すラベルを付与する例を示している。入力系列ｘは、「U.N. official John Smith heads for Baghdad on July 4th .」のように、１１個のトークンに区切られている。各トークンには、文法的な係り受け関係を示すラベルが、それぞれ付与されている。例えば、「U.N.」に付与されているラベルは「Smith」からのリンク（「ｘ１←ｘ４」）であり、「official」に付与されているラベルは「Smith」からのリンク（「ｘ２←ｘ４」）であり、「John」に付与されているラベルは「Smith」からのリンク（「ｘ３←ｘ４」）であり、「Smith」に付与されているラベルは「heads」からのリンク（「ｘ４←ｘ５」）である。「heads」はこの文の係り受け関係におけるヘッドとなる単語なので、「heads」に付与されているラベルは「リンクが存在しない」というものである。「for」に付与されているラベルは「heads」からのリンク（「ｘ６→ｘ７」）であり、「Baghdad」に付与されているラベルは「for」からのリンク（「ｘ７→ｘ８」）であり、「on」に付与されているラベルは「Baghdad」からのリンク(「ｘ８→ｘ９」)であり、「July」に付与されているラベルは「on」からのリンク(「ｘ９→ｘ１０」）であり、「4th」に付与されているラベルは「July」からのリンク(「ｘ１０→ｘ１１」)であり、「.」に付与されているラベルは「heads」からのリンク（「ｘ１１←ｘ５」）である。
【０００８】
図３Ａは、系列構造予測問題のうちＤＮＡ塩基配列から遺伝子領域を推定する問題に関するものを示す。４種類の塩基（Ｔ，Ｃ，Ａ，Ｇ）の３個の順列（コドン）からなる塩基配列に対してアミノ酸を示すラベルが付与されている。ここでは、コドン「ＡＴＧ」に対して、メチオニン(Methionine)を示すラベル「Ｍ」が付与されている。また、コドン「ＴＧＡ」に対して、ヒスチジン(Histidine)を示すラベル「Ｈ」が付与されている。また、コドン「ＡＴＧ」とコドン「ＴＧＡ」とに挟まれた各コドンには、対応するラベル「Ｒ」、「Ｄ」、「Ｗ」、「Ｑ」が付与されている。また、コドン「ＡＴＧ」より前（左側）の文字と、コドン「ＴＧＡ」より後（右側）の文字とには、対応するアミノ酸ではないことを示すラベル「Ｏ」が付与されている。なお、「Ｍ」は、たんぱく質への翻訳開始を示す開始コドンを意味し、「Ｈ」は、たんぱく質への翻訳終了を示す終止コドンを意味する。
【０００９】
図３Ｂは、人と人や事柄間の関係を表現するデータに対して、そのネットワーク構造を予測する問題に関するものを示す。この例では、人名と各人の特定物品の購入履歴の組合せを入力構造とし、各人に対して同じ嗜好を持った人を付与する。例えば、
（Smith,(A,B,E)）,(Johnson,(F,G,J)),(Williams,(A,C,D)), (Brown,(A,B,C,D,E)),(Jones,(A,C,D)),(Miller,(D,F,G,J)),(Davis,(A,F,G,H,J))を入力構造とする。各ノード（人名）には、同じ嗜好を持った人を示すラベルが、それぞれ付与されている。例えば、「Smith」には「Brown」が、「Johnson」には「Miller,Davis」が、「Williams」には「Brown, Jones」が、「Brown」には「Smith, Williams, Jones」が、「Jones」には「Williams,Brown」が、「Miller」には「Johnson,Davis」が、「Davis」には「Johnson, Miller」が付与されている。
【００１０】
入力構造に対して正しい出力構造を予測するには、機械学習によって構造予測モデルを学習し、その学習モデルを利用する必要がある。一般的に、機械学習において構造予測器が用いる構造予測モデルを学習する方法は、大きく三つに分類される。第一の方法は、入力構造に対して正しい出力構造が付与された、いわゆる「教師データ」を用いて学習を行う方法である。この方法は、データを教師信号として利用することから「教師あり学習」と呼ばれる。なお、教師信号とは、入力構造に対して理想的と考えられる出力構造のことである。このとき、教師データは入力構造と教師信号（理想的な出力構造）のペアの集合で与えられ、サンプル数がＪ個のときにＤＬ＝｛（ｘ（ｊ），ｙ（ｊ））｝Ｊｊ＝１と書く。教師データを利用した教師あり学習の利点は、高性能な構造予測モデルを学習することができることである。但し、出力構造ｙにラベルつきグラフによって記述できる相互依存関性がある点が、出力構造を予測（推定）に応用するときの問題となる。そのため、全体的な出力構造における関係性を考慮したデータ作成が必要とされる。また、タスクの専門知識等が必要とされることが多い。よって、構造予測モデルの学習に必要な教師データを大量に作成することは、多大な人的、時間的及び費用的コストが掛かるという問題がある。また、教師あり学習は教師データの量に性能が大きく依存する。そのため、十分な量の教師データを作成することができない場合には、その教師データを用いた教師あり学習により学習された構造予測モデルの性能は低くなるという問題がある。
【００１１】
第二の方法は、出力構造が不明なデータ（以下、「教師なしデータ」という）のみを利用して学習を行う「教師なし学習」である。教師データの作成コストを気にせずに学習が行える点で、教師なし学習は、教師あり学習より優れている。しかし、教師なし学習は、十分な予測性能を得るために、人間の事前知識による仮説や入力構造間の類似度尺度などのなにかしらの事前知識を必要とする。これらの事前知識がわからない、あるいは、うまく機能しない場合には、教師なし学習により学習された構造予測モデルは、十分な予測性能が得られないという問題がある。また一般的に、これらの事前知識を計算機上で記述するのは非常に困難なので、教師なし学習により学習された構造予測モデルは、教師あり学習により学習された構造予測モデルより予測性能が低くなることが多いという問題がある。
【００１２】
第三の方法は、教師データと教師なしデータの双方を利用する「半教師あり（凖教師あり）学習」である。半教師あり学習は、教師あり学習において教師ありデータの数が限られているときに、補助的に教師なしデータを用いることで、構造予測モデルの予測性能を向上させる方法である。そのため、半教師あり学習は、低コストで高性能の構造予測モデルを学習できる可能性がある。
【００１３】
非特許文献１が半教師あり学習を用いた構造予測モデルの学習法の従来技術として知られている。この方法は、条件付確率場（非特許文献２参照）と呼ばれる教師あり学習による構造予測モデルの学習を、半教師あり学習に拡張した方法である。この方法により学習された構造予測モデルを用いた構造予測器は、実データで非常に良好な予測性能を示している。
【先行技術文献】
【非特許文献】
【００１４】
【非特許文献１】J. Suzuki, H. Isozaki, "Semi-Supervised Sequential Labeling and Segmentation Using Giga-word Scale Unlabeled Data", Proceedings of ACL-08, 2008, pp.665-673
【非特許文献２】J. Lafferty, A. McCallum, F. Pereira, "Conditional Random Fields: Probabilistic Models for Segmenting and Labeling Sequence Data", In Proc. 18th International Conf. on Machine Learning, 2001, pp.282-289
【発明の概要】
【発明が解決しようとする課題】
【００１５】
教師データは作成が高コストであるため少数の教師データしか利用できない場合がほとんどである。構造予測問題に対して十分な教師データを利用できない場合、背景技術で述べたように、教師あり学習により学習された構造予測モデルは十分な予測性能が得られないという問題がある。
【００１６】
一方、教師なしデータは、教師データと比べて相対的に大量かつ容易に得られることが多い。しかし、大量の教師なしデータが存在しても、教師なし学習では十分な予測性能を得ることは、背景技術で述べたようにそもそも困難であるという問題がある。
【００１７】
そのため、少量の教師データと大量の教師なしデータを利用して、半教師あり学習により構造予測モデルを学習することが理想的である。
【００１８】
構造予測モデルを学習する際に、教師なしデータでは出力構造ｙが不明であるため、直接入力構造ｘが与えられた時の出力構造ｙの条件付確率ｐ（ｙ|ｘ）を推定できない。そこで、例えば、特開２００８−２２５９０７号公報や非特許文献１は、同時確率ｐ（ｘ，ｙ）によるモデル（生成モデル）を使って、出力構造を推定する方法を提案している。一般に、半教師あり学習による構造予測モデルの学習では、少量の教師データしか存在しない場合、十分な予測性能を得るため膨大な量の教師なしデータを必要とする。そして、膨大な量の教師なしデータから得られる構造予測モデルは、より複雑になるという問題点がある。複雑な構造予測モデルは、構造予測モデル作成装置及び構造予測器上の記憶領域を多く必要とする。また、構造予測器の予測速度が遅くなる原因となる。
【００１９】
そこで本発明では、予測性能を保持したまま、省メモリ化を実現する構造予測モデルを学習する装置、方法、プログラム、及び記録媒体を提供することを目的とする。
【課題を解決するための手段】
【００２０】
上記の課題を解決するために、本発明に係る構造予測モデル学習技術は、入力構造ｘに対する出力構造ｙを予測するために利用される構造予測モデルを、教師データＤＬ及び教師なしデータＤＵを用いて学習する。本発明に係る構造予測モデル学習技術では、構造予測問題により特定される出力候補生成用定義データ集合を用いて、教師データに対する教師データ用出力候補グラフを生成し、教師なしデータに対する教師なしデータ用出力候補グラフを生成し、特徴抽出テンプレートを用いて、教師データ用出力候補グラフ及び教師なしデータ用出力候補グラフから特徴を抽出し、教師データ用出力候補グラフから抽出した特徴の集合に対するＤ次元の基本モデル用特徴ベクトルｆｘ，ｙを生成し、教師なしデータ用出力候補グラフから抽出した特徴の集合をＫ個の部分集合に分割し、部分集合ｋに含まれる特徴に対するＤｋ次元の補助モデル用特徴ベクトルｇ（ｋ）ｘ，ｙを生成し（但し、Ｋを自然数とし、ｋ∈｛１，２，…，Ｋ｝とする）、基本モデル用特徴ベクトルｆｘ，ｙのＤ個の要素にそれぞれ１対１対応するＤ個の第１パラメタで構成される第１パラメタ集合ｗを含む基本モデル用パラメタ集合λを生成し、補助モデル用特徴ベクトルｇ（ｋ）ｘ，ｙのＤｋ個の要素にそれぞれ１対１対応するＤｋ個の補助モデル用パラメタで構成される補助モデル用パラメタ集合θ（ｋ）を生成し、Ｋ個の補助モデル用パラメタ集合θ（ｋ）で構成される補助モデル用パラメタ集合の集合Θ＝｛θ（１），θ（２），…，θ（Ｋ）｝を生成し、各補助モデルｑｋは補助モデル用パラメタ集合θ（ｋ）を対数線形モデルにより定義するものとし、補助モデル用パラメタ集合θ（ｋ）から得られる正則化項と教師なしデータＤＵを用いて、非負関数であって、入力構造ｘに対する出力構造ｙの擬似的な正解の度合いを表す参照関数ｒ~（ｘ，ｙ）と補助モデルｑｋとの間の正則化項付きブレグマン距離を最小にする補助モデル用パラメタ集合の集合Θを推定し、基本モデル用パラメタ集合λは、Ｋ個の補助モデルとそれぞれ１対１対応するＫ個の第２パラメタで構成される第２パラメタ集合ｖ＝｛ｖ１，ｖ２，…,ｖＫ｝を含むものとし、教師データＤＬと補助モデル用パラメタ集合の集合Θを用いて、事前に定義された経験リスク関数を最小にする基本モデル用パラメタ集合λを推定する。
【発明の効果】
【００２１】
本発明は、教師なしデータを用いて、擬似的な正解の度合いを表す参照関数と補助モデルとの間のブレグマン距離を最小化する補助モデル用パラメタを推定する。このような構成とすることで、正解が不明な教師なしデータの正解を近似的に推定して利用することを可能とした。作成コストが高い教師データが少量でも、作成コストが低い教師なしデータを追加利用して構造予測モデルを学習でき、さらに構造予測モデルの予測性能を向上させることが可能となる。また、本発明は、補助モデルを対数線形モデル等により定義することで、ブレグマン距離を最小化する際に、Ｌ１ノルム正則化の技術を導入できる。Ｌ１ノルム正則化の技術を導入することで、活性状態にあるパラメータ（言い換えると、０以外のパラメタ）の数を減らすことができる。このような構成とすることで、自然かつシステマティックに構造予測モデルを省メモリ化することができるという効果を奏する。
【００２２】
さらに、このような構造予測モデルを利用すれば、構造予測器に必要な記憶量を削減できる。よって、構造予測モデルを記憶した外部記憶装置（ＨＤＤ等）から主記憶装置（メモリ）へのロード時間を短縮できる。また、特徴に対するインデックス引きの速度が向上し、構造予測に掛かる時間を短縮できる。
【図面の簡単な説明】
【００２３】
【図１】図１は、系列構造予測問題のうち英語のテキストから固有表現を抽出する問題に関するものを示す図。
【図２】図２は、木構造予測問題のうち、英語のテキスト内の依存構造を解析する問題に関するものを示す図。
【図３】図３Ａは系列構造予測問題のうちＤＮＡ塩基配列から遺伝子領域を推定する問題に関するものを示す図、図３Ｂは、人と人や事柄間の関係を表現するデータに対して、そのネットワーク構造を予測する問題に関するものを示す図である。
【図４】図４は構造予測モデル学習装置１００と構造予測器７の関係を示す図。
【図５】図５は構造予測モデル学習装置１００の構成を模式的に示す機能ブロック図。
【図６】図６は構造予測モデル学習装置１００の処理フローを示す図。
【図７】図７は英語の教師データを示す図。
【図８】図８は英語の教師なしデータを示す図。
【図９】図９は出力候補生成用定義データ集合Ｔ１を示す図。
【図１０】図１０は英語の入力構造に対する出力候補グラフを示す図。
【図１１】図１１は特徴抽出テンプレートＴ２を模式的に示す図。
【図１２】図１２は特徴抽出テンプレートＴ２を用いて英語の入力構造に対する出力候補グラフから特徴を抽出する例を示す図
【図１３】図１３は図１２のノード４１１に付与される特徴ベクトルの例を示す図。
【図１４】図１４は図１２のノード４１２に付与される特徴ベクトルの例を示す図。
【図１５】図１５は英語の入力構造に対する基本モデル用パラメタ集合λのデータ例を示す図。
【図１６】図１６は英語の入力構造に対する補助モデル用パラメタ集合の集合Θのデータ例を示す図。
【図１７】図１７は補助モデル用パラメタ推定部１４０の構成を模式的に示す機能ブロック図。
【図１８】図１８は補助モデル用パラメタ推定部１４０の処理フローを示す図。
【図１９】図１９は基本モデル用パラメタ推定部１６０の構成を模式的に示す機能ブロック図。
【図２０】図２０は基本モデル用パラメタ推定部１６０の処理フローを示す図。
【図２１】図２１は英語の入力構造に対するパラメタｕのデータ例を示す図。
【図２２】図２２は構造予測モデル学習装置１００のハードウェア構成を例示したブロック図。
【図２３】図２３は教師データのみに基づき学習された構造予測モデルを用いた構造予測器の正解率と、タイプ３の補助モデルを利用した構造予測モデル学習装置１００により学習された構造予測モデルを用いた構造予測器の正解率を示す図。
【図２４】図２４は英語の係り受け構造予測問題に対する出力候補グラフの例を示す図。
【発明を実施するための形態】
【００２４】
＜本発明のポイント＞
構造予測モデルは、入力構造ｘに対して出力構造ｙを予測するモデルである。また、本発明の一例において、構造予測モデルは数式を用いて以下のように定義される。
【００２５】
【数１】
0005250076.tif 000002
【００２６】
式（１）は、入力構造ｘと出力構造ｙの組合せから抽出した特徴に対応するスコアを利用して構造を予測する。式（１）は、その特徴に対するスコアの総計が最も高い出力構造ｙ＾が、入力構造ｘに対して最も尤もらしい出力構造であるとし、予測結果として求める。但し、ｄ（ｘ，ｙ；λ，Θ）は、入力構造ｘに対して出力構造ｙが得られる可能性を表すスコアを返す判別関数を表す。ｄ（ｘ，ｙ；λ，Θ）の戻り値は１つの実数値である。また、ｄ（ｘ，ｙ）は、後述する基本モデル用パラメタ集合λと補助モデル用パラメタ集合の集合Θを利用して、予め与えられた計算式を計算する。但し、λ＝｛ｗ，ｖ１，ｖ２，…，ｖＫ｝とし、Θ＝｛θ（１），θ（２），…，θ（Ｋ）｝とする。また、ｆｘ，ｙは、教師データＤＬから抽出した特徴の集合に対するＤ次元の基本モデル用特徴ベクトルを表す。ｗは、基本モデル用特徴ベクトルｆｘ，ｙのＤ個の要素にそれぞれ１対１対応するＤ個の第１パラメタで構成される第１パラメタ集合を表す。また、ｇ（ｋ）ｘ，ｙは、教師なしデータＤＬから抽出した特徴の集合をＫ個の部分集合に分割し、各部分集合ｋに含まれる特徴の集合に対するＤｋ次元の補助モデル用特徴ベクトルを表す。θ（ｋ）は、特徴ベクトルｇ（ｋ）ｘ，ｙのＤｋ個の要素にそれぞれ１対１対応するＤｋ個の補助モデル用パラメタで構成される補助モデル用パラメタ集合を表す。なお、ｖ＝｛ｖ１，ｖ２，…，ｖＫ｝を、Ｋ個の補助モデルとそれぞれ１対１対応するＫ個の第２パラメタで構成される第２パラメタ集合とする。但し、Ｋは自然数とし、ｋ∈｛１，２，…，Ｋ｝とする。なお、基本モデルは、教師データＤＬを用いて、判別関数内で用いられる基本モデル用パラメタ集合λを推定するために用いられるモデルである。補助モデルは、教師なしデータＤＵを用いて、判別関数内で用いられる補助モデル用パラメタ集合Θを推定するために用いられるモデルである。各パラメタや各ベクトルの求め方は後述する。
【００２７】
＜補助モデル＞
構造予測モデルを学習する際に、教師なしデータでは出力構造ｙが不明であるため、直接入力構造ｘが与えられた時の出力構造ｙを利用した学習が行えない。そこで、本発明の一例では、Ｋ個の補助モデルを用いて正解の出力構造ｙを近似的に推定して利用する。補助モデルを非負関数として定義する。例えば、ロジスティック回帰モデルや、対数線形モデルが、補助モデルとして用いられる。次に、導入した補助モデルと、与えられた参照関数（reference function）とのブレグマン距離（Bregman divergence）を最小化するように、補助モデル用パラメタ集合の集合Θを推定する。このとき、構造予測モデルを省メモリ化するために、Ｌ１ノルム正則化項を導入する。これにより、非ゼロのパラメタ数を最小に保ったまま最適なパラメタ集合の集合Θを推定できる。
【００２８】
＜局所的構造＞
式（１）において、入力構造ｘが与えられたときの可能な全ての出力構造の候補Ｙ（ｘ）の数は一般的に非常に大きくなる。このため、全ての候補Ｙ（ｘ）を列挙し、それぞれの特徴を抽出してスコアを評価するのは計算量的に困難となる場合が多い。この計算量の問題を克服するため、出力構造ｙを、局所的構造（部分構造）ｚに分解する。そして、出力構造ｙの大域的な特徴は使わず、局所的構造ｚから得られる特徴のみを利用して出力構造を予測する。
【００２９】
局所的構造の定義は、扱う構造予測問題に合わせて自由に、人手により事前に定義すればよい。例えば、局所的構造は、出力構造グラフのクリークにより定義される。但し、出力構造内の要素を排他的に区分して、局所的構造を定義する必要はない。また、局所的構造の定義は、局所的構造同士が完全に包含関係にあるなど重複するような定義でもよい。あるいは逆に、局所的構造の定義は、任意の要素が被覆されていないような定義でもよい。
【００３０】
ここで、ある出力構造ｙから事前の定義に従って得られる全ての局所的構造の集合をＺ（ｘ，ｙ）で表す。局所的構造の集合Ｚ（ｘ，ｙ）の一つの要素をｚ∈Ｚ（ｘ，ｙ）と表す。同様に、ｘから生成できる全ての出力候補の集合Ｙ（ｘ）に出現する全ての局所的構造の集合をＺ（ｘ，Ｙ（ｘ））と表す。
【００３１】
ここで、与えられた入力構造ｘと任意の局所的構造ｚの情報から抽出される特徴ベクトルをｆｘ，ｚ、または、ｇ（ｋ）ｘ，ｚと書くこととする。このとき、本発明の一例では、以下の等式が成り立つこととする。
【００３２】
【数２】
0005250076.tif 000003
【００３３】
式（２）は、各局所的構造ｚで得られた特徴ベクトルｆｘ，ｚの総和が出力構造全体の特徴ベクトルｆｘ，ｙとなることを意味する。式（３）は、各局所的構造ｚで得られた特徴ベクトルｇ（ｋ）ｘ，ｚの総和が出力構造全体の特徴ベクトルｇ（ｋ）ｘ，ｙとなることを意味する。なお、式（１）は、以下の式（１）’で表すことができる。
【００３４】
【数３】
0005250076.tif 000004
【００３５】
次に、基本モデルＰ及び補助モデルｑｋを定義する。ｑｋはｋ番目の補助モデルを表す。３つのタイプの補助モデルを例示する。なお、何れのタイプの補助モデルも、非負関数であり、補助モデル用パラメタ集合θ（ｋ）を対数線形モデルにより定義する。
【００３６】
＜補助モデル（タイプ１）＞
タイプ１のｋ番目の補助モデルをｑ１ｋと表す。ｘが与えられたときに出力構造ｙが出力される条件付確率ｑ（ｙ|ｘ）と出力されない条件付確率ｑ（¬ｙ|ｘ）＝１−ｑ（ｙ|ｘ）は以下の式で表される。
【００３７】
【数４】
0005250076.tif 000005
【００３８】
但し、ｂ（ｙ）＝Σｚb（ｚ）は１以上の値を返す関数を表す。また、ｂ（ｙ）には、θ（ｋ）・ｇ（ｋ）ｘ，ｙ＝０のとき、式（４）が、一様分布と一致するような値を代入する。次に、ｑ１ｋのオッズを用いてｑ’１ｋを以下のように定義する。
【００３９】
【数５】
0005250076.tif 000006
【００４０】
よって、ｑ’１ｋは、ｑ１ｋのを１／ｂ（ｙ）倍した値になる。つまり、ｑ’１ｋはｑ１ｋに比例する値となる。
【００４１】
ここで、以降の処理のために、Ｑｋを以下のように定義する。
Ｑｋ（ｚ|ｘ；θ（ｋ））＝ｑ１ｋ（ｚ|ｘ，θ（ｋ））        （６）
但し、ｑ１ｋ（ｚ|ｘ，θ（ｋ））は、ｘが与えられたときの出力構造ｙのなかに局所的構造ｚが出現する条件付確率を表す。この条件付確率は、ｑ１ｋ（ｙ|ｘ，θ（ｋ））の定義から、ｚの周辺確率として計算できる。
【００４２】
＜補助モデル（タイプ２）＞
タイプ２の補助モデルをｑ２ｋと表す。ｑ２ｋは、計算量を削減するために、より簡単な構造を導入する。タイプ２の補助モデルは、入力構造ｘに対する出力構造ｙをモデル化するのではなく、ｙを構成する個々の局所的構造ｚに対するモデル化を行う。ｘが与えられたときに出力構造ｙに局所的構造ｚが含まれる条件付確率ｑ（ｚ|ｘ）と出力されない条件付確率ｑ（¬ｚ|ｘ）＝１−ｑ（ｚ|ｘ）は以下の式で表される。
【００４３】
【数６】
0005250076.tif 000007
【００４４】
但し、ｂ（ｚ）を局所的構造ｚの対立候補となる局所的構造の個数とする。これは、θ（ｋ）・ｇ（ｋ）ｘ，ｚ＝０をデフォルトの値と仮定した場合、ｚの出現確率が対立候補と等確率
【００４５】
【数７】
0005250076.tif 000008
【００４６】
となるような補正項を意味する。次に、ｑ２ｋのオッズを用いてｑ’２ｋを以下のように定義する。
【００４７】
【数８】
0005250076.tif 000009
【００４８】
ここで以降の処理のために、Ｑｋを以下のように定義する。
【００４９】
【数９】
0005250076.tif 000010
【００５０】
＜補助モデル（タイプ３）＞
タイプ３の補助モデルをｑ３ｋと表す。ｑ３ｋは、さらに補助モデルの計算量を削減できる。タイプ３の補助モデルは、個々の局所的構造ｚの出現確率を単一の特徴ｎのみでモデル化する。ｘが与えられたときに出力構造ｙにｎを特徴とする局所的構造ｚが含まれる条件付確率ｑ（ｚ|ｘ，ｎ）と出力されない条件付確率ｑ（¬ｚ|ｘ，ｎ）＝１−ｑ（ｚ|ｘ，ｎ）は以下の式で表される。
【００５１】
【数１０】
0005250076.tif 000011
【００５２】
次に、ｑ３ｋのオッズを用いてｑ’３ｋを以下のように定義する。
【００５３】
【数１１】
0005250076.tif 000012
【００５４】
ここでタイプ１、２と同様に以降の処理のために、Ｑｋを以下のように定義する。但し、θ（ｋ）＝（θ（ｋ）１，θ（ｋ）２，…，θ（ｋ）Ｄｋ）、ｇ（ｋ）ｘ，ｚ＝（ｇ（ｋ）ｘ，ｚ，１，ｇ（ｋ）ｘ，ｚ，２，…，ｇ（ｋ）ｘ，ｚ，Ｄｋ）とする。
【００５５】
【数１２】
0005250076.tif 000013
【００５６】
Ｑｋはｑ３ｋのオッズまたはｑ’３ｋをｎ＝１，２，…，Ｄｋまでをまとめたものに相当する。
【００５７】
＜基本モデル＞
基本モデルは、学習後の構造予測モデルが式（１）’で記述できるものであれば、どのようなモデルでもよい。ここでは、式（６）、（９）、（１２）において補助モデルｑ１ｋ、ｑ２ｋ、ｑ３ｋのそれぞれから得られるＱｋを導入して、基本モデルを定義する。基本モデルを確率モデルに基づき定義する場合と、基本モデルをマージン最大化モデル原理に基づき定義する場合を例示する
【００５８】
＜確率モデルに基づく基本モデルの定義＞
基本モデルＰを確率モデルに基づき定義する場合には、以下のように表す。
【００５９】
【数１３】
0005250076.tif 000014
【００６０】
これは、入力構造ｘが与えられたときの出力構造ｙが出る条件付確率Ｐ（ｙ｜ｘ）を、対数線形モデルと補助モデルとの各局所的構造ｚ毎の積として定義していることを意味する。
なお、実際には、補助モデルｑ１ｋ、ｑ２ｋ、ｑ３ｋの何れを利用しても、式（１３）の右辺を整理して以下のように書ける。
【００６１】
【数１４】
0005250076.tif 000015
【００６２】
特に、補助モデルの数が１のとき（つまりＫ＝１）、かつ、基本モデル用特徴ベクトルと補助モデル用特徴ベクトルが同じとき（つまりｆｘ，ｙ＝ｇ（１）ｘ，ｙ）、式（１４）を整理してｄを以下のように示すことができる。
【００６３】
【数１５】
0005250076.tif 000016
【００６４】
＜マージン最大化モデルに基づく基本モデルの定義＞
基本モデルＰを線形識別モデルでのマージン最大化に基づき定義する場合には、以下のように表す。
【００６５】
【数１６】
0005250076.tif 000017
【００６６】
但し、Ｅ（ｙ，ｙ＾）は、ある正解の出力ｙと任意の出力ｙ＾を比較した際のｙ＾の誤りの度合いを表す関数である。Ｅ（ｙ，ｙ＾）は、誤りが大きければ、つまり、ｙとｙ＾の違いが大きければ大きいほど値が大きくなる。なお、Ａ＼Ｂは、集合Ａから集合Ｂを引いた差集合を表す。式（１６）は、入力構造ｘに対する正解の出力構造ｙのスコアｄ（ｘ，ｙ；λ，Θ）と、最も誤りリスクの高い不正解の出力ｙ＾のスコアｄ（ｘ，ｙ＾；λ，Θ）の差分が、エラーの推定値Ｅ（ｙ，ｙ＾）以上になるようにする。
以下、これらの定義を用いて、本発明の実施の形態について、詳細に説明する。
【実施例１】
【００６７】
図４に示すように、構造予測モデル学習装置１００は、学習フェーズにおいて、構造予測モデル学習装置１００は、教師データＤＬと、教師なしデータＤＵと、学習支援情報記憶部４に格納された情報とを用いて、構造予測モデルを学習し、学習後の構造予測モデルを構造予測モデル記憶部６に出力する。構造予測モデル記憶部６は学習後の構造予測モデルを記憶する。構造予測器７は、構造予測モデル記憶部６から構造予測モデルを受け取る。さらに、構造予測器７は、ラベルなしサンプルＳＵ（入力構造ｘ）を受け取り、これに対するラベル有りサンプルＳＬ（出力構造ｙ）を、構造予測モデルを利用して推定し、出力する。
【００６８】
なお、教師データＤＬは入力構造ｘと教師信号（理想的な出力構造ｙ）のペアの集合である。サンプル数がＮ個の教師データをＤＬ＝｛（ｘ（ｎ），ｙ（ｎ））｝Ｎｎ＝１と表す。教師なしデータＤＵは入力構造ｘのみからなるデータの集合であり、正解の出力構造ｙが不明なデータの集合である。サンプル数がＭ個の教師なしデータをＤＵ＝｛（ｘ（ｍ））｝Ｍｍ＝１と表す。なお、例えば図１に示されている固有表現抽出の場合には、構造予測モデルを学習するために、Ｎ＝１万、Ｍ≧１０００万といった規模のサンプルが必要となる。
【００６９】
学習支援情報記憶部４は、学習支援情報として、後記する特徴抽出テンプレートＴ２と、出力候補生成用定義データ集合Ｔ１とを記憶するものである。
【００７０】
＜構造予測モデル学習装置１００＞
図５、図６を用いて実施例１に係る構造予測モデル学習装置１００を説明する。構造予測モデル学習装置１００は、例えば、ＣＰＵ（Central Processing Unit）と、ＲＡＭ（Random Access Memory）と、ＲＯＭ（Read Only Memory）と、ＨＤＤ（Hard Disk Drive）と、入出力インタフェース等から構成される。
【００７１】
構造予測モデル学習装置１００は、例えば、記憶部１０３と、制御部１０５と、出力候補グラフ生成部１１０と、特徴ベクトル生成部１２０と、パラメタ生成部１３０と、補助モデル用パラメタ推定部１４０と、基本モデル用パラメタ推定部１６０と、第１収束判定部１８０と、パラメタ統合部１９０を備える。このうち、出力候補グラフ生成部１１０と特徴ベクトル生成部１２０は、学習のための前処理を行うためのものである。
【００７２】
＜記憶部１０３及び制御部１０５＞
記憶部１０３は、前述のＲＡＭ、ＲＯＭ、ＨＤＤ等からなる。記憶部１０３は、教師データＤＬ、教師なしデータＤＵ、学習支援情報、処理途中の信号や各種パラメタ等を記憶する。制御部１０５は、前述のＣＰＵ等からなる。制御部１０５は、記憶部１０３に対し、各処理過程で所定の信号やパラメタの読み書きを行う。但し、制御部１０５は、必ずしも記憶部１０３に対し各データの読み書きを行わなければならないわけではなく、各部間で直接データを受け渡すように制御してもよい。
【００７３】
＜入力データ例＞
本実施例では、英語のテキストデータからなる入力構造に対し、固有表現を示すラベルを付与する出力構造を予測するために利用される構造予測モデルを学習する例を示す。図７、図８は、図５に示した構造予測モデル学習装置１００に入力する情報の例を示す図である。図７は英語の教師データを、図８は英語の教師なしデータをそれぞれ示す。図７に示す例は、図１に示したものと同様である。但し、トークン区切りは事前に施されているものとする。
【００７４】
図９は、出力候補生成用定義データ集合Ｔ１を示す。この例では、出力候補生成用定義データ集合は、予め定められた５つの出力候補生成用定義データを要素としている。この出力候補生成用定義データ集合Ｔ１は、対象とする構造予測問題によって自動的に決定される。構造予測モデル学習装置１００は、この出力候補生成用定義データ集合Ｔ１を学習支援情報記憶部４から取得する。
【００７５】
＜出力候補グラフ生成部１１０＞
出力候補グラフ生成部１１０は、教師データＤＬと教師なしデータＤＵと出力候補生成用定義データ集合Ｔ１を受け取る。そして、出力候補グラフ生成部１１０は、構造予測問題により特定される出力候補生成用定義データ集合Ｔ１を用いて、受け取った教師データＤＬに対する教師データ用出力候補グラフＧｒＤＬを生成する（ｓ１１０）。出力候補グラフ生成部１１０は、同様に出力候補生成用定義データ集合Ｔ１を用いて、受け取った教師なしデータＤＵに対する教師なしデータ用出力候補グラフＧｒＤＵを生成する（ｓ１１０）。出力候補グラフ生成部１１０は、受け取った教師データＤＬと、その教師データＤＬから生成した教師データ用出力候補グラフＧｒＤＬとを対応付ける。出力候補グラフ生成部１１０は、受け取った教師なしデータＤＵと、その教師なしデータＤＵから生成した教師なしデータ用出力候補グラフＧｒＤＵとを対応付ける。さらに、出力候補グラフ生成部１１０は、各データを特徴ベクトル生成部１２０に出力する。出力候補グラフは、図１０に示すように、可能性のある全ての出力構造候補をパスで接続したラティス形式で表現したものである。なお、以下の例では、出力候補生成用定義データ集合は、予め定められた３つの出力候補生成用定義データを要素としている。図１０の例では、出力候補生成用定義データ集合は「ＰＥＲ．」、「ＯＲＧ．」、「Ｏ」の３つの出力候補生成用定義データを要素としている。図１０は、図５に示した構造予測モデル学習装置１００で生成される出力候補グラフの一例を模式的に示す図である。ここで、＜ＢＯＳ＞は、入力構造ｘの始まりを表す固定の特別なラベルであり、＜ＥＯＳ＞は、入力構造ｘの終わりを表す固定の特別なラベルである。ラティスは、入力構造ｘ（教師データＤＬまたは教師なしデータＤＵ）に対する出力構造ｙを示すものであり、出力構造ｙの個々のインスタンスｙｅ（ｅ＝１，２，３）をノードで示し、各インスタンス間の依存関係をリンクで示す。出力候補グラフ中の＜ＢＯＳ＞から＜ＥＯＳ＞間の１つのパスは１つの出力に対応し、出力候補グラフは、とり得る全ての出力の候補を包含したグラフになっている。例えば、図１０の出力候補グラフは３８通りのパス（出力候補）を包含する。例えば、図１０のノード４０１は、入力構造ｘの４番目の単語「ＳＤ」に対してラベル「ＯＲＧ．」を付与した出力のインスタンスを示す。同様に、図１０のノード４０２は、入力構造ｘの６番目の単語「two」に対してラベル「Ｏ」を付与した出力のインスタンスを示す。
【００７６】
＜特徴ベクトル生成部１２０＞
特徴ベクトル生成部１２０は、特徴抽出テンプレートＴ２と教師データ用出力候補グラフＧｒＤＬと教師なしデータ用出力候補グラフＧｒＤＵを受け取る。そして、特徴ベクトル生成部１２０は、受け取った特徴抽出テンプレートＴ２を用いて、教師データ用出力候補グラフＧｒＤＬ及び教師なしデータ用出力候補グラフＧｒＤＵから特徴を抽出する（ｓ１２０）。さらに、特徴ベクトル生成部１２０は、教師データ用出力候補グラフＧｒＤＬから抽出した特徴の集合に対するＤ次元の基本モデル用特徴ベクトルｆｘ，ｙを生成する（ｓ１２０）。また、特徴ベクトル生成部１２０は、教師なしデータ用出力候補グラフＧｒＤＵから抽出した特徴の集合をＫ個の部分集合に分割する。特徴ベクトル生成部１２０は、部分集合ｋに含まれる特徴に対するＤｋ次元の補助モデル用特徴ベクトルｇ（ｋ）ｘ，ｙを生成する（ｓ１２０）。特徴ベクトル生成部１２０は、教師データ用出力候補グラフＧｒＤＬに基本モデル用特徴ベクトルｆｘ，ｙを付与して、パラメタ生成部１３０に出力する。また、特徴ベクトル生成部１２０は、教師なしデータ用出力候補グラフＧｒＤＵに補助モデル用特徴ベクトルｇ（ｋ）ｘ，ｙを付与して、パラメタ生成部１３０に出力する。
【００７７】
以下、特徴ベクトル生成部１２０が、出力候補グラフから特徴を抽出する方法を説明する。特徴ベクトル生成部１２０は、出力候補グラフから、ラベルｙｉと、特徴抽出テンプレートに記述された入力構造中のインスタンスとの組合せにより、特徴を抽出する。但し、ｙｉは出力構造のｉ番目のラベルを表す。図１１は、特徴抽出テンプレートＴ２の例を示す図である。特徴ベクトル生成部１２０は、この特徴抽出テンプレートＴ２を用いて、ラベルｙｉとその前後２個ずつまでに対応する入力単語ｘｉ−２、ｘｉ−１、ｘｉ、ｘｉ＋１、ｘｉ＋２それぞれとの組合せ（ｙｉ＆ｘｉ−２、ｙｉ＆ｘｉ−１、ｙｉ＆ｘｉ、ｙｉ＆ｘｉ＋１、ｙｉ＆ｘｉ＋２）や、ラベルｙｉの後２個の入力単語ｘｉ＋１とｘｉ＋２とｙｉとの組合せ（ｙｉ＆ｘｉ＋１＆ｘｉ＋２）等を特徴として抽出する。図１２に、特徴ベクトル生成部１２０が、特徴抽出テンプレートＴ２を用いて、出力候補グラフから特徴を抽出する例を示す。
【００７８】
図１２において、ノード４１１は出力構造１番目のラベル（ｙ１）が「ＰＥＲ．」である場合を示す。このとき、特徴ベクトル生成部１２０は、図１２に示す特徴４１１Ａを抽出する。図１２において、ノード４１２は出力構造３番目のラベル（ｙ３）が「ＯＲＧ．」である場合を示す。このとき、特徴ベクトル生成部１２０は、図１２に示す特徴４１２Ａを抽出する。図１２において、ノード４１３は出力構造５番目（ｙ５）のラベルが「ＯＲＧ．」である場合を示す。このとき、特徴ベクトル生成部１２０は、図１２に示す特徴４１３Ａを抽出する。
【００７９】
次に、特徴ベクトルを生成し、付与する方法を説明する。特徴ベクトル生成部１２０は、全ての教師データＤＬから得られる全ての教師データ用出力候補グラフＧｒＤＬの全てのノードから抽出される特徴を集め、そこから重複する特徴を削除し、教師データ用特徴集合を生成する。なお、各教師なしデータ用特徴集合に含まれる要素の数をＤ個とする。
【００８０】
同様に、特徴ベクトル生成部１２０は、全ての教師なしデータＤＵから得られる全ての教師なしデータ用出力候補グラフＧｒＤＵの全てのノードから抽出される特徴を集め、そこから重複する特徴を削除し、教師なしデータ用特徴集合を生成する。さらに、特徴ベクトル生成部１２０は、生成した教師なしデータ用特徴集合を、Ｋ個の部分集合に分割する。なお、特徴のタイプに応じて、教師なしデータ用特徴集合を分割するとよい。特徴のタイプは、例えば、その教師なしデータの媒体（新聞やＷｅｂ等）、内容（経済、スポーツ等）、作成者により分類される。なお、各部分集合に含まれる要素の数をＤｋ個とする。異なる特徴のタイプが異なる分布を持つことがあるため、このような構成とすることで、より予測性能を向上させることができる。
【００８１】
特徴ベクトル生成部１２０は、出力候補グラフの各ノード（または各リンク）に対して、特徴ベクトルを付与する。基本モデル用特徴ベクトルｆｘ，ｙは、教師データ用出力候補グラフＧｒＤＬから抽出した特徴の集合の要素と１対１対応する要素からなるＤ次元のベクトルである。なお、補助モデル用特徴ベクトルｇ（ｋ）ｘ，ｙは、教師なしデータ用出力候補グラフＧｒＤＵから抽出した特徴の集合の部分集合の要素と１対１対応する要素からなるＤｋ次元のベクトルである。なお、教師データ用出力候補グラフＧｒＤＬであっても、教師なしデータ用出力候補グラフＧｒＤＵであっても、特徴ベクトルを付与する方法は、同じである。図１３は、図１２のノード４１１に対して、付与される特徴ベクトルの説明図である。図１４は、図１２のノード４１２に対して、付与される特徴ベクトルの説明図である。特徴ベクトル生成部１２０は、各ノードから抽出した特徴には値「１」を紐付け、また、各ノードから抽出できなかった特徴には値「０」を紐付けることで、「１」と「０」とを要素に持つ特徴ベクトルを生成する。特徴ベクトル生成部１２０は、生成した特徴ベクトルを対応するノードに付与する。なお、特徴ベクトル生成部１２０は、各ラベルとその前後２個ずつまでに対応する入力単語それぞれとの組合せ等で特徴を生成する。そのため、入力構造のｉ番目の単語に対する出力構造のｉ番目のラベルの違うノードの特徴ベクトルは、それぞれ互いに直交する。よって、それらの内積は「０」となる。
【００８２】
＜パラメタ生成部１３０＞
パラメタ生成部１３０は、基本モデル用特徴ベクトルｆｘ，ｙが付与された教師データ用出力候補グラフＧｒＤＬと補助モデル用特徴ベクトルｇ（ｋ）ｘ，ｙが付与された教師なしデータ用出力候補グラフＧｒＤＵを受け取る。パラメタ生成部１３０は、基本モデル用特徴ベクトルｆｘ，ｙのＤ個の要素にそれぞれ１対１対応するＤ個の第１パラメタで構成される第１パラメタ集合ｗ＝｛ｗ１，ｗ２，…，ｗＤ｝を含む基本モデル用パラメタ集合λを生成し（ｓ１３０）、基本モデル用パラメタ推定部１６０に出力する。
【００８３】
また、パラメタ生成部１３０は、補助モデル用特徴ベクトルｇ（ｋ）ｘ，ｙのＤｋ個の要素にそれぞれ１対１対応するＤｋ個の補助モデル用パラメタで構成される補助モデル用パラメタ集合θ（ｋ）＝｛θ（ｋ）１，θ（ｋ）２，…，θ（ｋ）Ｄ｝を生成する。さらに、パラメタ生成部１３０は、Ｋ個の補助モデル用パラメタ集合θ（ｋ）で構成される補助モデル用パラメタ集合の集合Θ＝｛θ（１），θ（２），…，θ（Ｋ）｝を生成し（ｓ１３０）、補助モデル用パラメタ推定部１４０に出力する。
【００８４】
なお、パラメタ生成部１３０は、例えば、各パラメタに初期値として０を設定する。図１５に、基本モデル用パラメタ集合λのデータ例を示す。図１６に、補助モデル用パラメタ集合の集合Θのデータ例を示す。
【００８５】
また、パラメタ生成部１３０は、補助モデル用パラメタ推定部１４０と基本モデル用パラメタ推定部１６０の繰り返し回数を示すパラメタｔ＝０を生成してもよい。
【００８６】
＜補助モデル用パラメタ推定部１４０＞
補助モデル用パラメタ推定部１４０は、補助モデル用パラメタ集合θ（ｋ）から正則化項を求める。さらに、補助モデル用パラメタ推定部１４０は、教師なしデータＤＵを用いて、参照関数ｒ~（ｘ，ｙ）と補助モデルｑｋとの間の正則化項付きブレグマン距離を最小にする補助モデル用パラメタ集合の集合Θを推定する（ｓ１４０）。
【００８７】
例えば、補助モデル用パラメタ推定部１４０は、参照関数ｒ~（ｘ，ｙ）と、補助モデル用パラメタ集合の集合Θと、補助モデル用特徴ベクトルｇ（ｋ）ｘ，ｙが付与された教師なしデータ用出力候補グラフＧｒＤＵを受け取る。
【００８８】
補助モデル用パラメタ推定部１４０は、参照関数ｒ~と補助モデルｑｋ間のブレグマン距離を最小化する補助モデル用パラメタ集合の集合Θを推定する。ここで、参照関数と補助モデル間のブレグマン距離を最小化するとは、解空間の中で補助モデルが参照関数に最も近くなるような補助モデル用パラメタ集合の集合Θを求めることを意味する。また、ブレグマン距離を最小化する際に、Ｌ１正則化項を導入する。これにより、学習後の構造予測モデルを省メモリ化することができる。なお、各補助モデルｑｋが補助モデル用パラメタ集合θ（ｋ）を確率モデルにより定義する場合には、その総和が１でなければならないため、Ｌ１正則化項を導入することはできない。本実施例では、各補助モデルｑｋが補助モデル用パラメタ集合θ（ｋ）を対数線形モデルにより定義する。対数線形モデルには、上記制約がないため、Ｌ１正則化項を導入できる。
【００８９】
（参照関数）
まず、参照関数を定義する。参照関数ｒ~（ｘ，ｙ）は、非負関数である。つまり、その値域は[０，∞)である。但し、上述の補助モデルｑ１ｋ、ｑ２ｋ、ｑ３ｋを利用する場合には、それらの値域が[０，１］なので、参照関数の値域も[０，１]とする。また、参照関数ｒ~（ｘ，ｙ）は、入力構造ｘに対する出力構造ｙの擬似的な正解の度合いを表す。例えば、初めて、補助モデル用パラメタ推定部１４０が補助モデル用パラメタを推定する場合には、事前に教師ありデータＤＬを用いて、第１パラメタ集合ｗを推定し（特開２００８−２２５９０７号公報参照）、推定した第１パラメタ集合ｗを対数線形モデルで定義した基本モデル（但し、補助モデルはなく、例えば、第２パラメタｖの各要素に０を設定する）を参照関数とする。この場合、ｒ~（ｘ、ｚ）＝Ｐ（ｚ|ｘ，ｗ＊）となる。
【００９０】
さらに、２回目以降、補助モデル用パラメタ推定部１４０が補助モデル用パラメタを推定する場合には、繰り返し計算の際に１つ前の繰り返しで得られた基本モデルＰ（ｚ|ｘ，λｔ−１，Θｔ−１）を参照関数として利用する。また、例えば、参照関数として、人間が事前に決めた関数や、全く別のモデル（例えば、特開２００８−２２５９０７号公報記載の言語解析モデル）を用いることができる。
【００９１】
（ブレグマン距離）
参照関数ｒ~と補助モデルｑｋ間のブレグマン距離ＢＦは、以下のように定義される。
【００９２】
【数１７】
0005250076.tif 000018
このとき、Ｆは、任意の連続微分可能実数値関数であり、かつ、狭義凸関数である。例えば、ＦとしてＬ２ノルムが用いられる。本実施例では、Ｆ（ｘ）＝Σｘｌｏｇｘ−Σｘとする。このとき、ブレグマン距離ＢＦは、以下の式（２２）に示すように、一般化相対エントロピーＧと一致する。
【００９３】
【数１８】
0005250076.tif 000019
【００９４】
最終的に、補助モデル用パラメタ集合の集合Θの推定は、参照関数ｒ~と補助モデルｑｋ間の一般化相対エントロピーＧをＬ１ノルム正則化項付きで最小化することに帰着する。また、一般化相対エントロピーを正確に求めるには、全ての可能性のある入力と出力のペア（ｘ，ｙ）が必要である。しかし、全ての可能性のある入力と出力のペアを列挙することは不可能である。よって、実際には、全ての可能性のある入力と出力のペアの代わりに、教師なしデータＤＵを使った実測値を用いる。この限られた大きさの実測値を用いて得られる一般化相対エントロピーを、経験一般化相対エントロピーと呼び、Ｇ＾ＤＵと表す。よって、最適な補助モデル用パラメタ集合の集合Θを求める式（つまり、正則化項付き経験一般化相対エントロピーＵ（Θ｜ＤＵ）を最小化する式）は、以下のように表される。
【００９５】
【数１９】
0005250076.tif 000020
【００９６】
なお、|θ（ｋ）|１はｋ番目の補助モデル用パラメタ集合θ（ｋ）のＬ１ノルムを表す。また、ＣＵは、右辺第１項と右辺第２項の重要度を調節する変数である。つまり、ＣＵは、経験一般化相対エントロピーとＬ１正則化項のどちらを重要視するかを決める。また、ＣＵは、人手でチューニングするハイパーパラメタである。
【００９７】
以下に、補助モデルｑ１ｋ、ｑ２ｋ、ｑ３ｋ、ｑ’１ｋ、ｑ’２ｋまたはｑ’３ｋを用いた場合に、得られる正則化項付き経験一般化相対エントロピーＵ（Θ｜ＤＵ）を示す。
【００９８】
（ｑ１を用いた場合）
補助モデルとしてｑ１ｋを用いた場合、式（２２）、式（２３）及び式（４）を用いて、正則化項付き経験一般化相対エントロピーＵ（Θ｜ＤＵ）は以下のように表される。
【００９９】
【数２０】
0005250076.tif 000021
【０１００】
なお、ｃｏｎｓｔ（θ（ｋ））は、θ（ｋ）に対して定数項になるものをまとめた値である。なお、最適化する際に（Ｕ（Θ｜ＤＵ）を最小化する際に）、ｃｏｎｓｔ（θ（ｋ））は解に影響を与えない。また、式（２４）の勾配は以下のように表される。
【０１０１】
【数２１】
0005250076.tif 000022
【０１０２】
但し、σ（ａ）は、ベクトルａの各要素に対して−１、０、１の３つの値のどれかで構成するベクトルを返す関数である。σ（ａ）は、要素が０より大きいとき１で、要素が０より小さいとき−１で、０のとき０で、それぞれ要素を置き換えたベクトルを返す。全てのｋで∇ｋＵ（Θ|ＤＵ）＝０のときに、式（２３）は最適値を得る（つまり、Ｕ（Θ｜ＤＵ）の最小値を得る）。実際には、勾配に基づく最適化法により最適値を求めることができる。
【０１０３】
（ｑ’１を用いた場合）
ｑ’１ｋを用いた場合、式（２２）、式（２３）及び式（５）を用いて、正則化項付き経験一般化相対エントロピーＵ（Θ｜ＤＵ）は以下のように表される。
【０１０４】
【数２２】
0005250076.tif 000023
【０１０５】
また、式（２６）の勾配は以下のように表される。
【０１０６】
【数２３】
0005250076.tif 000024
【０１０７】
（ｑ２を用いた場合）
補助モデルとしてｑ２ｋを用いた場合、式（２２）、式（２３）及び式（７）を用いて、正則化項付き経験一般化相対エントロピーＵ（Θ｜ＤＵ）は以下のように表される。
【０１０８】
【数２４】
0005250076.tif 000025
【０１０９】
また、式（２８）の勾配は以下のように表される。
【０１１０】
【数２５】
0005250076.tif 000026
【０１１１】
（ｑ’２を用いた場合）
ｑ’２ｋを用いた場合、式（２２）、式（２３）及び式（８）を用いて、正則化項付き経験一般化相対エントロピーＵ（Θ｜ＤＵ）は以下のように表される。
【０１１２】
【数２６】
0005250076.tif 000027
【０１１３】
また、式（３０）の勾配は以下のように表される。
【０１１４】
【数２７】
0005250076.tif 000028
【０１１５】
タイプ２の補助モデルの場合は、出力構造ｙ全体ではなく、各局所構造ｚ単位に計算する。このような構成により、タイプ１と比較して、高速化が期待できる。ダイプ１の補助モデルを用いた場合と同様に、タイプ２の補助モデルを用いた場合も、勾配に基づく最適化法により最適値を求めることができる。
【０１１６】
（ｑ３を用いた場合）
補助モデルとしてｑ３ｋを用いた場合、式（２２）、式（２３）及び式（１０）を用いて、正則化項付き経験一般化相対エントロピーＵ（Θ｜ＤＵ）は以下のように表される。
【０１１７】
【数２８】
0005250076.tif 000029
【０１１８】
また、式（３２）の勾配は以下のように表される。
【０１１９】
【数２９】
0005250076.tif 000030
【０１２０】
（ｑ’３を用いた場合）
ｑ’３ｋを用いた場合、式（２２）、式（２３）及び式（１１）を用いて、正則化項付き経験一般化相対エントロピーＵ（Θ｜ＤＵ）は以下のように表される。
【０１２１】
【数３０】
0005250076.tif 000031
【０１２２】
また、式（３４）の勾配は以下のように表される。
【０１２３】
【数３１】
0005250076.tif 000032
【０１２４】
タイプ３の補助モデルを用いた場合、各パラメタ間の依存関係を考慮しなくてよくなる。そのため、１変数の線形探索で解を求めることができる。よって、数値最適化時の計算量の大部分を占める勾配の計算が非常に簡単になる。このため、タイプ３の補助モデルを用いることは、学習時の計算量の面で非常に優れている。
【０１２５】
なお、タイプ１、２、３の補助モデルの何れを用いた場合にも、正則化項付き経験一般化相対エントロピーＵ（Θ｜ＤＵ）は、各パラメタに対して凸関数となる。よって、最適解は唯一に決定する。
【０１２６】
（補助モデル用パラメタ推定部１４０の構成例及び処理フロー）
図１７及び図１８を用いて補助モデル用パラメタ推定部１４０を説明する。補助モデル用パラメタ推定部１４０は、条件付き確率場に基づいて補助モデル用集合の集合Θを推定するために、例えば、正則化項付き経験一般化相対エントロピー計算部１４５と勾配計算部１４７と第２収束判定部１４９とパラメタ更新部１５１とを備える。なお、条件付き確率場については、例えば、「F. Sha and F. Pereira, Shallow Parsing with Conditional Random Fields, In Proc. of HLT/NAACL-2003. pages 134-141, 2003」（以下、「参考文献１」という）に詳述されているので説明を省略する。
【０１２７】
正則化項付き経験一般化相対エントロピー計算部１４５は、教師なしデータＤＵと参照関数ｒ~（ｘ，ｙ）と補助モデル用パラメタの集合の集合Θを受け取り、式（２４）、（２６）、（２８）、（３０）、（３２）、（３４）の何れかの正則化項付き経験一般化相対エントロピーＵ（Θ｜ＤＵ）を計算する（ｓ１４５）。さらに、正則化項付き経験一般化相対エントロピー計算部１４５は、正則化項付き経験一般化相対エントロピーＵ（Θ｜ＤＵ）を、勾配計算部１４７に出力する。
【０１２８】
正則化項付き経験一般化相対エントロピーＵ（Θ｜ＤＵ）を最適化（最小化）するには、Ｌ−ＢＦＧＳといった勾配に基づく数値最適化法を適用することができる。なお、Ｌ−ＢＦＧＳについては、例えば、「D. C. Liu and J. Nocedal, "On the Limited Memory BFGS Method for Large Scale Optimization", Math.Programming, Ser. B, 1989, Volume 45, Issue 3, p.503-528,」（以下、「参考文献２」という）に記載されているので、説明を省略する。
【０１２９】
勾配計算部１４７は、Ｕ（Θ｜ＤＵ）の勾配を計算するものである。式（２４）、（２６）、（２８）、（３０）、（３２）、（３４）の勾配はそれぞれ式（２５）、（２７）、（２９）、（３１）、（３３）、（３５）で示される。
【０１３０】
第２収束判定部１４９は、式（２５）、（２７）、（２９）、（３１）、（３３）、（３５）で示される勾配∇Ｕ（Θ｜ＤＵ）が収束したか否かを判定する（ｓ１４９）。また、第２収束判定部１４９は、勾配∇Ｕ（Θ｜ＤＵ）の値が収束したと判定した場合には、その時点の補助モデル用パラメタ集合の集合Θ＊を、第１収束判定部１８０と基本モデル用パラメタ推定部１６０に出力する。パラメタ更新部１５１は、勾配∇Ｕ（Θ｜ＤＵ）の値が収束していない場合に、補助モデル用パラメタ集合の集合Θを更新する（ｓ１５１）。
【０１３１】
＜基本モデル用パラメタ推定部１６０＞
基本モデル用パラメタ推定部１６０は、教師データＤＬと補助モデル用パラメタ集合の集合Θを用いて、事前に定義された経験リスク関数を最小にする基本モデル用パラメタ集合λを推定する（ｓ１６０）。
【０１３２】
リスク関数と正則化項の定義の選択肢は様々な可能性がある。例えば、以下のように定義する。
【０１３３】
【数３２】
0005250076.tif 000033
【０１３４】
ここで、Ｒ（λ｜Θ，ＤＬ）は、任意のリスク関数を表す。リスク関数とは、学習時の誤りを推定するための任意の関数である。つまり、リスク関数の値が小さい程学習がうまくできていることを表す。また、ＣＬは、式（２３）のＣＵと同様の人手でチューニングするハイパーパラメタである。また、Ω（λ）は、λに関する正則化項を表す。例えば、正則化項として、Ｌ１ノルム正則化項やＬ２ノルム正則化項が用いられる。
【０１３５】
【数３３】
0005250076.tif 000034
【０１３６】
（リスク関数として負の対数尤度を用いる場合）
まず、リスク関数に負の対数尤度を用いる場合を示す。負の正則化対数尤度最小化では、以下の式により最適パラメタを求める。
【０１３７】
【数３４】
0005250076.tif 000035
【０１３８】
これは、基本モデルに確率モデルを利用した場合の一般的な最適化の方法である。式（４３）の勾配は以下のように表すことができる。
【０１３９】
【数３５】
0005250076.tif 000036
【０１４０】
このとき、正則化項の勾配は、以下のように示される。
【０１４１】
【数３６】
0005250076.tif 000037
【０１４２】
式（４１）に式（４３）を代入した場合、式（４１）の勾配は以下のように表される。
【０１４３】
【数３７】
0005250076.tif 000038
【０１４４】
実際の教師データＤＬ内に出現した特徴ベクトルの総和をとったベクトルとなる。
式（４１）の最適パラメタは、式（４６）での勾配が０となるときに得られる。実際の最適化では、Ｌ-ＢＦＧＳといった勾配に基づく数値最適化法により求めることができる（参考文献２参照）。
【０１４５】
（マージン最大化モデルに基づき推定する場合）
次に、マージン最大化原理に基づき基本モデル用パラメタ集合λを推定する場合について説明する。この場合は、リスク関数は以下のように表される。
【０１４６】
【数３８】
0005250076.tif 000039
【０１４７】
例えば、式（４１）に式（４７）と式（４５）のＬ２正則化を代入した場合、式（４１）の勾配は以下のよ
【０１４８】
【数３９】
0005250076.tif 000040
【０１４９】
Ｒ（λ｜Θ，ＤＬ）＝０の場合、Ｌ（λ｜Θ）を微分できない。そのため、通常の勾配法ではＬ（λ｜Θ，ＤＬ）を最適化できない。この場合、劣勾配法を用いてＬ（λ｜Θ，ＤＬ）を最適化することができる。
【０１５０】
（基本モデル用パラメタ推定部１６０の構成例及び処理フロー）
図１９及び図２０を用いて基本モデル用パラメタ推定部１６０を説明する。基本モデル用パラメタ推定部１６０は、条件付き確率場（参考文献１参照）に基づいて基本モデル用パラメタ集合λを推定するために、図１９に示すように、例えば、経験リスク関数計算部１６１と正則化項計算部１６３と、正則化項付き経験リスク関数計算部１６５と勾配計算部１６７と第３収束判定部１６９とパラメタ更新部１７１とを備える。
【０１５１】
経験リスク関数計算部１６１は、教師データＤＬと補助モデル用パラメタ集合の集合Θと基本モデル用パラメタ集合λを受け取り、式（４３）または式（４７）の経験リスク関数Ｒ（λ｜Θ，ＤＬ）を計算する（ｓ１６１）。さらに、経験リスク関数計算部１６１は、Ｒ（λ｜Θ，ＤＬ）を正則化項付き経験リスク関数計算部１６５に出力する。
【０１５２】
正則化項計算部１６３は、基本モデル用パラメタ集合λを受け取り、式（４２）の正則化項Ω（λ）を計算する（ｓ１６３）。さらに、正則化項計算部１６３は、Ω（λ）を正則化項付き経験リスク関数計算部１６５に出力する。
【０１５３】
正則化項付き経験リスク関数計算部１６５は、経験リスク関数Ｒ（λ｜Θ，ＤＬ）と正則化項Ω（λ）を受け取り、式（４１）に代入し、の正則化項付き経験リスク関数Ｌ（λ｜Θ，ＤＬ）を計算する（ｓ１６５）。さらに、正則化項付き経験リスク関数計算部１６５は、正則化項付き経験リスク関数Ｌ（λ｜Θ，ＤＬ）を、勾配計算部１６７に出力する。
【０１５４】
正則化項付き経験リスク関数Ｌ（λ｜Θ，ＤＬ）を最適化するには、Ｌ−ＢＦＧＳといった勾配に基づく数値最適化法を適用することができる。なお、Ｌ−ＢＦＧＳについては、参考文献２に記載されているので、説明を省略する。
【０１５５】
勾配計算部１６７は、式（４６）または（４８）の勾配∇Ｌ（λ｜Θ，ＤＬ）を計算する（ｓ１６７）。
【０１５６】
第３収束判定部１６９は、式（４６）または（４８）の勾配∇Ｌ（λ｜Θ，ＤＬ）が収束したか否かを判定する（ｓ１６９）。また、第３収束判定部１６９は、勾配∇Ｌ（λ｜Θ，ＤＬ）の値が収束したと判定した場合には、その時点の基本モデル用パラメタ集合λ＊を、第１収束判定部１８０に出力する。
【０１５７】
パラメタ更新部１７１は、勾配∇Ｌ（λ｜Θ，ＤＬ）の値が収束していない場合に、基本モデル用パラメタ集合λを更新する（ｓ１７１）。
【０１５８】
＜第１収束判定部１８０＞
第１収束判定部１８０は、基本モデル用パラメタ集合λと補助モデル用パラメタ集合の集合Θの値を受け取り、これらの値が、収束したか否かを判定する（ｓ１８０）。なお、特許請求の範囲における収束判定部は、第１収束判定部１８０に対応する。
【０１５９】
第１収束判定部１８０は、例えばパラメタの増分を用いて、判定する。第１収束判定部１８０は、｜λ(t)−λ(t＋１)｜＋｜Θ(t)−Θ(t＋１)｜の値が、閾値以下となった場合、収束したと判定する。または、第１収束判定部１８０は、事前に繰り返し回数Ｔを決定しておいて、繰り返し回数ｔが規定の回数Ｔ（ｔ＝Ｔ）に達したら、収束したと判定してもよい。
【０１６０】
第１収束判定部１８０が収束していないと判定した場合には、補助モデル用パラメタ推定部１４０に対して、補助モデル用パラメタ集合の集合Θと基本モデル用パラメタ集合λを推定する処理を繰り返すことを指示する制御信号ｃを出力する。第１収束判定部１８０は、また繰り返し回数を示すパラメタｔを１増加させる（ｔ←ｔ＋１）。なお、このとき、参照関数ｒ~として、繰り返し処理における１つ前の基本モデルＰ（ｘ，ｙ；λｔ−１，Θｔ−１）を出力してもよい。
【０１６１】
第１収束判定部１８０が収束したと判定した場合には、そのときの補助モデル用パラメタ集合の集合Θと基本モデル用パラメタ集合λをパラメタ統合部１９０に出力する。
【０１６２】
＜パラメタ統合部１９０＞
パラメタ統合部１９０は、収束した基本モデル用パラメタ集合λと補助モデル用パラメタ集合の集合Θを統合する（ｓ１９０）。
【０１６３】
パラメタ統合部１９０は、例えば、基本モデルのｊ番目の特徴と、ｋ番目の補助モデルのｐ番目の特徴が一致する場合には、統合後のパラメタ集合ｕのｉ番目の要素ｕｉを以下の式により求める。図２１にパラメタ集合ｕのデータ例を示す。
ｕｉ＝ｗｊ+ｖｋθ(k)ｐ        （５１）
また、例えば、基本モデルにしかｉ番目の要素ｕｉに対応する特徴がない場合には、パラメタ統合部１９０は、要素ｕｉを以下の式により求める。
ｕｉ＝ｗｊ        （５２）
また、例えば、補助モデルにしかｉ番目の要素ｕｉに対応する特徴がない場合には、要素ｕｉを以下の式により求める。
ｕｉ＝ｖｋθ(k)ｐ        （５３）
このとき、構造予測モデルは、式（１）に代えて、以下の式で表すことができる。
【０１６４】
【数４０】
0005250076.tif 000041
【０１６５】
但し、基本モデル用パラメタ集合λと補助モデル用パラメタ集合の集合Θを統合したときのパラメタ集合ｕの要素の数をＩとすると、ｕ＝｛ｕ１，ｕ２，…，ｕＩ｝である。
【０１６６】
さらに、パラメタ統合部１９０は、統合したパラメタ集合ｕ、または、パラメタ集合ｕを用いて表される構造予測モデルを構造予測モデル記憶手段６に出力する。本実施例では、θ（ｋ）ｌの多くがゼロ（つまり活性状態ではないパラメータ）となっている。このとき、式（５２）により求められるｕｉもゼロのパラメータとなる。
【０１６７】
＜効果＞
このような構成とすることで、学習後の構造予測モデルから活性状態にないパラメタ（言い換えると、０のパラメタ）及びそのパラメタに対応する特徴を削除することで、学習後の構造予測モデルを省メモリ化することができる。さらに、教師データと教師なしデータに基づき作成された構造予測データは高い予測性能を維持したまま、省メモリ化を実現している。実験結果を後述する。なお、教師データＤＬから得られる基本モデル用パラメタ集合の要素数は、前述の通り、教師データＤＬの生成コストが高いため、それほど多くは得られない。一方、教師なしデータＤＵから得られる補助モデル用パラメタ集合の集合Θの要素数は、膨大な量を容易に求めることができる。このΘの要素のほとんどをゼロにすることで、省メモリ化を実現する。
【０１６８】
＜ハードウェア構成＞
図２２は、本実施例における構造予測モデル学習装置１００のハードウェア構成を例示したブロック図である。図２２に例示するように、この例の構造予測モデル学習装置１００は、それぞれＣＰＵ（Central Processing Unit）１１、入力部１２、出力部１３、補助記憶装置１４、ＲＯＭ（Read Only Memory）１５、ＲＡＭ（Random Access Memory）１６及びバス１７を有している。
【０１６９】
この例のＣＰＵ１１は、制御部１１ａ、演算部１１ｂ及びレジスタ１１ｃを有し、レジスタ１１ｃに読み込まれた各種プログラムに従って様々な演算処理を実行する。また、入力部１２は、データが入力される入力インタフェース、キーボード、マウス等であり、出力部１３は、データが出力される出力インタフェース、ディスプレイ、プリンタ等である。補助記憶装置１４は、例えば、ハードディスク、半導体メモリ等であり、構造予測モデル学習装置１００としてコンピュータを機能させるためのプログラムや各種データが格納される。また、ＲＡＭ１６には、上記のプログラムや各種データが展開され、ＣＰＵ１１等から利用される。また、バス１７は、ＣＰＵ１１、入力部１２、出力部１３、補助記憶装置１４、ＲＯＭ１５及びＲＡＭ１６を通信可能に接続する。なお、このようなハードウェアの具体例としては、例えば、パーソナルコンピュータの他、サーバ装置やワークステーション等を例示できる。
【０１７０】
＜プログラム構成＞
上述のように、補助記憶装置１４には、本実施例の構造予測モデル学習装置１００の各処理を実行するための各プログラムが格納される。構造予測プログラムを構成する各プログラムは、単一のプログラム列として記載されていてもよく、また、少なくとも一部のプログラムが別個のモジュールとしてライブラリに格納されていてもよい。
【０１７１】
＜ハードウェアとプログラムとの協働＞
ＣＰＵ１１は、読み込まれたＯＳプログラムに従い、補助記憶装置１４に格納されている上述のプログラムや各種データをＲＡＭ１６に展開する。そして、このプログラムやデータが書き込まれたＲＡＭ１６上のアドレスがＣＰＵ１１のレジスタ１１ｃに格納される。ＣＰＵ１１の制御部１１ａは、レジスタ１１ｃに格納されたこれらのアドレスを順次読み出し、読み出したアドレスが示すＲＡＭ１６上の領域からプログラムやデータを読み出し、そのプログラムが示す演算を演算部１１ｂに順次実行させ、その演算結果をレジスタ１１ｃに格納していく。
【０１７２】
図５は、このようにＣＰＵ１１に上述のプログラムが読み込まれて実行されることにより構成される構造予測モデル学習装置１００の機能構成を例示したブロック図である。
【０１７３】
ここで、記憶部１０３は、補助記憶装置１４、ＲＡＭ１６、レジスタ１１ｃ、その他のバッファメモリやキャッシュメモリ等の何れか、あるいはこれらを併用した記憶領域に相当する。また、出力候補グラフ生成部１１０、特徴ベクトル生成部１２０、パラメタ生成部１３０、補助モデル用パラメタ推定部１４０、基本モデル用パラメタ推定部１６０、第１収束判定部１８０、パラメタ統合部１９０は、ＣＰＵ１１に構造予測プログラムを実行させることにより構成されるものである。
【０１７４】
＜実験結果＞
図２３において、教師データのみに基づき学習された構造予測モデルを用いた構造予測器の正解率を一点鎖線で示し、タイプ３の補助モデルを利用した構造予測モデル学習装置１００により学習された構造予測モデルを用いた構造予測器の正解率を実線で示す。何れのパラメタ数であっても、構造予測モデル学習装置１００により学習された構造予測モデルを用いた構造予測器の正解率のほうが高い。また、正解率９２．５％弱の場合には、構造予測モデル学習装置１００により学習された構造予測モデルで利用されるパラメタｕの数は、教師データのみに基づき学習された構造予測モデルで利用されるパラメタ集合の要素の数の約１０分の１程度となることが分かる。
【０１７５】
＜変形例＞
構造予測モデル学習装置１００、学習支援情報記憶部４、構造予測モデル記憶部６及び構造予測器７を一体化し、１つの計算機上で実現してもよい。
【０１７６】
構造予測モデル学習装置１００は、問題に応じて、出力候補定義データ集合や特徴抽出テンプレートを代えることで、系列構造予測問題以外の問題に対しても利用可能である。図２４は、係り受け構造予測問題に対する出力候補グラフの例を示す。
【０１７７】
なお、特徴ベクトル生成部１２０は、教師データ用出力候補グラフＧｒＤＬから抽出した特徴の集合と、教師なしデータ用出力候補グラフＧｒＤＵから抽出した特徴の集合を合体してもよい。特徴ベクトル生成部１２０は、合体した特徴の集合から重複する特徴を削除し、共通の特徴集合を生成する。このとき、基本モデル用特徴ベクトルｆｘ，ｙは、共通の特徴の集合の要素と１対１対応する要素からなるＤ次元のベクトルである。補助モデル用特徴ベクトルｇ（ｋ）ｘ，ｙは、共通の特徴の集合の部分集合の要素と１対１対応する要素からなるＤｋ次元のベクトルである。なお、部分集合は、共通の特徴の集合をＫ個に分割したものである。この場合、各ベクトルの次元数はＤ＝Ｄ１＋Ｄ２＋…＋ＤＤＫとなる。また、この場合、パラメタ統合部１９０では、式（５１）のみを用いる。
【０１７８】
補助モデル用パラメタ推定部１４０では、式（２４）、（２６）、（２８）、（３０）、（３２）または（３４）で表される正則化項付き経験一般化相対エントロピーＵ（Θ｜ＤＵ）の勾配を用いて、正則化項付き経験一般化相対エントロピーＵ（Θ｜ＤＵ）を最小化する補助モデル用パラメタ集合の集合を推定しているが、勾配を用いない他の方法を用いて、推定してもよい。同様に基本モデル用パラメタ推定部１６０では、式（４１）で表される正則化項付き経験リスク関数Ｌ（λ｜Θ，ＤＬ）の勾配を用いて、正則化項付き経験リスク関数Ｌ（λ｜Θ，ＤＬ）を最小化する基本モデル用パラメタ集合を推定しているが、勾配を用いない他の方法を用いて、推定してもよい。
【図１】
0005250076.tif 000060
【図２】
0005250076.tif 000061
【図３】
0005250076.tif 000062
【図４】
0005250076.tif 000063
【図５】
0005250076.tif 000064
【図６】
0005250076.tif 000065
【図７】
0005250076.tif 000066
【図８】
0005250076.tif 000067
【図９】
0005250076.tif 000068
【図１０】
0005250076.tif 000069
【図１１】
0005250076.tif 000070
【図１２】
0005250076.tif 000071
【図１３】
0005250076.tif 000072
【図１４】
0005250076.tif 000073
【図１５】
0005250076.tif 000074
【図１６】
0005250076.tif 000075
【図１７】
0005250076.tif 000076
【図１８】
0005250076.tif 000077
【図１９】
0005250076.tif 000078
【図２０】
0005250076.tif 000079
【図２１】
0005250076.tif 000080
【図２２】
0005250076.tif 000081
【図２３】
0005250076.tif 000082
【図２４】
0005250076.tif 000083