"入力構造xに対する出力構造yを予測するために利用される構造予測モデルを、教師データDL及び教師なしデータDUを用いて学習する構造予測モデル学習装置であって、Kを自然数とし、k∈{1,2,...,K}とし、構造予測問題により特定される出力候補生成用定義データ集合を用いて、教師データに対する教師データ用出力候補グラフを生成し、教師なしデータに対する教師なしデータ用出力候補グラフを生成する出力候補グラフ生成部と、特徴抽出テンプレートを用いて、前記教師データ用出力候補グラフ及び前記教師なしデータ用出力候補グラフから特徴を抽出し、前記教師データ用出力候補グラフから抽出した特徴の集合に対するD次元の基本モデル用特徴ベクトルfx,yを生成し、前記教師なしデータ用出力候補グラフから抽出した特徴の集合をK個の部分集合に分割し、部分集合kに含まれる特徴に対するDk次元の補助モデル用特徴ベクトルgkx,yを生成する特徴ベクトル生成部と、基本モデル用特徴ベクトルfx,yのD個の要素にそれぞれ1対1対応するD個の第1パラメタで構成される第1パラメタ集合wを含む基本モデル用パラメタ集合λを生成し、補助モデル用特徴ベクトルgkx,yのDk個の要素にそれぞれ1対1対応するDk個の補助モデル用パラメタで構成される補助モデル用パラメタ集合θkを生成し、K個の補助モデル用パラメタ集合θkで構成される補助モデル用パラメタ集合の集合Θ={θ1,θ2,...,θK}を生成するパラメタ生成部と、各補助モデルqkは前記補助モデル用パラメタ集合θkを対数線形モデルにより定義するものとし、前記補助モデル用パラメタ集合θkから得られる正則化項と前記教師なしデータDUを用いて、非負関数であって、入力構造xに対する出力構造yの擬似的な正解の度合いを表す参照関数rx,yと前記補助モデルqkとの間の正則化項付きブレグマン距離を最小にする補助モデル用パラメタ集合の集合Θを推定する補助モデル用パラメタ推定部と、前記基本モデル用パラメタ集合λは、K個の前記補助モデルとそれぞれ1対1対応するK個の第2パラメタで構成される第2パラメタ集合v={v1,v2,...vK}を含むものとし、前記教師データDLと前記補助モデル用パラメタ集合の集合Θを用いて、事前に定義された経験リスク関数を最小にする前記基本モデル用パラメタ集合λを推定する基本モデル用パラメタ推定部とを備える、ことを特徴とする構造予測モデル学習装置。請求項1記載の構造予測モデル学習装置であって、前記基本モデル用パラメタ集合λと前記補助モデル用パラメタ集合の集合Θの値が、収束したか否かを判定する収束判定部と、収束した前記基本モデル用パラメタ集合λと前記補助モデル用パラメタ集合の集合Θを統合するパラメタ統合部と、をさらに備え、前記収束判定部において、前記基本モデル用パラメタ集合λと前記補助モデル用パラメタ集合の集合Θの値が、収束していないと判定された場合には、前記補助モデル用パラメタ推定部と前記基本モデル用パラメタ推定部において、それぞれ補助モデル用パラメタ集合の集合Θと基本モデル用パラメタ集合λを推定する処理を繰り返し、前記参照関数rは、繰り返し処理における1つ前の基本モデルPである、ことを特徴とする構造予測モデル学習装置。請求項1記載の構造予測モデル学習装置であって、CLをハイパーパラメタとし、前記基本モデル用パラメタ推定部は、基本モデル用パラメタ集合λから得られる正則化項Ωλを用いて、前記経験リスク関数を正則化項付き経験リスク関数Lλ|Θ,DL=Rλ|Θ,DLCLΩλとして求め、経験リスク関数として、負の対数尤度を用いる場合には、とし、線形識別モデルでのマージン最大化に基づき、Lλ|Θ,DLを最小にする前記基本モデル用パラメタ集合λを推定する場合には、とする、ことを特徴とする構造予測モデル学習装置。請求項1記載の構造予測モデル学習装置であって、CUをハイパーパラメタとし、前記補助モデル用パラメタ推定部は、補助モデル用パラメタ集合θkを用いてL1ノルム正則化項|θk|1を求め、前記ブレグマン距離を、正則化項付き経験一般化相対エントロピーとして求め、正則化項付き経験一般化相対エントロピーを最小にする前記補助モデル用パラメタ集合の集合Θを推定する、ことを特徴とする構造予測モデル学習装置。請求項4記載の構造予測モデル学習装置であって、入力構造xが与えられたときに出力構造yが出力される条件付確率をq1ky|x;θkとし、q1kのオッズをq’1kとし、前記補助モデル用パラメタ推定部は、前記正則化付き経験一般化相対エントロピーをとして、または、として求め、これを最小にする補助モデル用パラメタ集合の集合Θを推定する、ことを特徴とする構造予測モデル学習装置。請求項4記載の構造予測モデル学習装置であって、入力構造xが与えられたときに出力構造yに局所構造zが出力される条件付確率をq2kz|x;θkとし、q2kのオッズをq’2kとし、前記補助モデル用パラメタ推定部は、前記正則化付き経験一般化相対エントロピーをとして、または、として求め、これを最小にする補助モデル用パラメタ集合の集合Θを推定する、ことを特徴とする構造予測モデル学習装置。請求項4記載の構造予測モデル学習装置であって、入力構造xが与えられたときに出力構造yに特徴nを備える局所構造zが出力される条件付確率をq3kz|x,n;θkとし、q3kのオッズをq’3kとし、前記補助モデル用パラメタ推定部は、前記正則化付き経験一般化相対エントロピーをとして、または、として求め、これを最小にする補助モデル用パラメタ集合の集合Θを推定する、ことを特徴とする構造予測モデル学習装置。入力構造xに対する出力構造yを予測するために利用される構造予測モデルを、教師データDL及び教師なしデータDUを用いて学習する構造予測モデル学習方法であって、Kを自然数とし、k∈{1,2,...,K}とし、構造予測問題により特定される出力候補生成用定義データ集合を用いて、教師データに対する教師データ用出力候補グラフを生成し、教師なしデータに対する教師なしデータ用出力候補グラフを生成する出力候補グラフ生成ステップと、特徴抽出テンプレートを用いて、前記教師データ用出力候補グラフ及び前記教師なしデータ用出力候補グラフから特徴を抽出し、前記教師データ用出力候補グラフから抽出した特徴の集合に対するD次元の基本モデル用特徴ベクトルfx,yを生成し、前記教師なしデータ用出力候補グラフから抽出した特徴の集合をK個の部分集合に分割し、部分集合kに含まれる特徴に対するDk次元の補助モデル用特徴ベクトルgkx,yを生成する特徴ベクトル生成ステップと、基本モデル用特徴ベクトルfx,yのD個の要素にそれぞれ1対1対応するD個の第1パラメタで構成される第1パラメタ集合wを含む基本モデル用パラメタ集合λを生成し、補助モデル用特徴ベクトルgkx,yのDk個の要素にそれぞれ1対1対応するDk個の補助モデル用パラメタで構成される補助モデル用パラメタ集合θkを生成し、K個の補助モデル用パラメタ集合θkで構成される補助モデル用パラメタ集合の集合Θ={θ1,θ2,...,θK}を生成するパラメタ生成ステップと、各補助モデルqkは前記補助モデル用パラメタ集合θkを対数線形モデルにより定義するものとし、前記補助モデル用パラメタ集合θkから得られる正則化項と前記教師なしデータDUを用いて、非負関数であって、入力構造xに対する出力構造yの擬似的な正解の度合いを表す参照関数rx,yと前記補助モデルqkとの間の正則化項付きブレグマン距離を最小にする補助モデル用パラメタ集合の集合Θを推定する補助モデル用パラメタ推定ステップと、前記基本モデル用パラメタ集合λは、K個の前記補助モデルとそれぞれ1対1対応するK個の第2パラメタで構成される第2パラメタ集合v={v1,v2,...vK}を含むものとし、前記教師データDLと前記補助モデル用パラメタ集合の集合Θを用いて、事前に定義された経験リスク関数を最小にする前記基本モデル用パラメタ集合λを推定する基本モデル用パラメタ推定ステップとを備える、ことを特徴とする構造予測モデル学習方法。請求項8記載の構造予測モデル学習方法であって、前記基本モデル用パラメタ集合λと前記補助モデル用パラメタ集合の集合Θの値が、収束したか否かを判定する収束判定ステップと、収束した前記基本モデル用パラメタ集合λと前記補助モデル用パラメタ集合の集合Θを統合するパラメタ統合ステップと、をさらに備え、前記収束判定ステップにおいて、前記基本モデル用パラメタ集合λと前記補助モデル用パラメタ集合の集合Θの値が、収束していないと判定された場合には、前記補助モデル用パラメタ推定ステップと前記基本モデル用パラメタ推定ステップにおいて、それぞれ補助モデル用パラメタ集合の集合Θと基本モデル用パラメタ集合λを推定する処理を繰り返し、前記参照関数rは、繰り返し処理における1つ前の基本モデルPである、ことを特徴とする構造予測モデル学習方法。請求項8記載の構造予測モデル学習方法であって、CLをハイパーパラメタとし、前記基本モデル用パラメタ推定ステップは、基本モデル用パラメタ集合λから得られる正則化項Ωλを用いて、前記経験リスク関数を正則化項付き経験リスク関数Lλ|Θ,DL=Rλ|Θ,DLCLΩλとして求め、経験リスク関数として、負の対数尤度を用いる場合には、とし、線形識別モデルでのマージン最大化に基づき、Lλ|Θ,DLを最小にする前記基本モデル用パラメタ集合λを推定する場合には、とする、ことを特徴とする構造予測モデル学習方法。請求項8記載の構造予測モデル学習方法であって、CUをハイパーパラメタとし、前記補助モデル用パラメタ推定ステップは、補助モデル用パラメタ集合θkを用いてL1ノルム正則化項|θk|1を求め、前記ブレグマン距離を、正則化項付き経験一般化相対エントロピーとして求め、正則化項付き経験一般化相対エントロピーを最小にする前記補助モデル用パラメタ集合の集合Θを推定する、ことを特徴とする構造予測モデル学習方法。請求項11記載の構造予測モデル学習方法であって、入力構造xが与えられたときに出力構造yが出力される条件付確率をq1ky|x;θkとし、q1kのオッズをq’1kとし、前記補助モデル用パラメタ推定ステップは、前記正則化付き経験一般化相対エントロピーをとして、または、として求め、これを最小にする補助モデル用パラメタ集合の集合Θを推定する、ことを特徴とする構造予測モデル学習方法。請求項11記載の構造予測モデル学習方法であって、入力構造xが与えられたときに出力構造yに局所構造zが出力される条件付確率をq2kz|x;θkとし、q2kのオッズをq’2kとし、前記補助モデル用パラメタ推定ステップは、前記正則化付き経験一般化相対エントロピーをとして、または、として求め、これを最小にする補助モデル用パラメタ集合の集合Θを推定する、ことを特徴とする構造予測モデル学習方法。請求項11記載の構造予測モデル学習方法であって、入力構造xが与えられたときに出力構造yに特徴nを備える局所構造zが出力される条件付確率をq3kz|x,n;θkとし、q3kのオッズをq’3kとし、前記補助モデル用パラメタ推定ステップは、前記正則化付き経験一般化相対エントロピーをとして、または、として求め、これを最小にする補助モデル用パラメタ集合の集合Θを推定する、ことを特徴とする構造予測モデル学習方法。請求項1記載の構造予測モデル学習装置として、コンピュータを機能させるためのプログラム。請求項1記載の構造予測モデル学習装置として、コンピュータを機能させるためのプログラムを記録したコンピュータ読み取り可能な記録媒体。教師データは作成が高コストであるため少数の教師データしか利用できない場合がほとんどである。構造予測問題に対して十分な教師データを利用できない場合、背景技術で述べたように、教師あり学習により学習された構造予測モデルは十分な予測性能が得られないという問題がある。一方、教師なしデータは、教師データと比べて相対的に大量かつ容易に得られることが多い。しかし、大量の教師なしデータが存在しても、教師なし学習では十分な予測性能を得ることは、背景技術で述べたようにそもそも困難であるという問題がある。そのため、少量の教師データと大量の教師なしデータを利用して、半教師あり学習により構造予測モデルを学習することが理想的である。構造予測モデルを学習する際に、教師なしデータでは出力構造yが不明であるため、直接入力構造xが与えられた時の出力構造yの条件付確率pyxを推定できない。そこで、例えば、特開2008-225907号公報や非特許文献1は、同時確率px,yによるモデル生成モデルを使って、出力構造を推定する方法を提案している。一般に、半教師あり学習による構造予測モデルの学習では、少量の教師データしか存在しない場合、十分な予測性能を得るため膨大な量の教師なしデータを必要とする。そして、膨大な量の教師なしデータから得られる構造予測モデルは、より複雑になるという問題点がある。複雑な構造予測モデルは、構造予測モデル作成装置及び構造予測器上の記憶領域を多く必要とする。また、構造予測器の予測速度が遅くなる原因となる。そこで本発明では、予測性能を保持したまま、省メモリ化を実現する構造予測モデルを学習する装置、方法、プログラム、及び記録媒体を提供することを目的とする。上記の課題を解決するために、本発明に係る構造予測モデル学習技術は、入力構造xに対する出力構造yを予測するために利用される構造予測モデルを、教師データDL及び教師なしデータDUを用いて学習する。本発明に係る構造予測モデル学習技術では、構造予測問題により特定される出力候補生成用定義データ集合を用いて、教師データに対する教師データ用出力候補グラフを生成し、教師なしデータに対する教師なしデータ用出力候補グラフを生成し、特徴抽出テンプレートを用いて、教師データ用出力候補グラフ及び教師なしデータ用出力候補グラフから特徴を抽出し、教師データ用出力候補グラフから抽出した特徴の集合に対するD次元の基本モデル用特徴ベクトルfx,yを生成し、教師なしデータ用出力候補グラフから抽出した特徴の集合をK個の部分集合に分割し、部分集合kに含まれる特徴に対するDk次元の補助モデル用特徴ベクトルgkx,yを生成し但し、Kを自然数とし、k∈{1,2,...,K}とする、基本モデル用特徴ベクトルfx,yのD個の要素にそれぞれ1対1対応するD個の第1パラメタで構成される第1パラメタ集合wを含む基本モデル用パラメタ集合λを生成し、補助モデル用特徴ベクトルgkx,yのDk個の要素にそれぞれ1対1対応するDk個の補助モデル用パラメタで構成される補助モデル用パラメタ集合θkを生成し、K個の補助モデル用パラメタ集合θkで構成される補助モデル用パラメタ集合の集合Θ={θ1,θ2,...,θK}を生成し、各補助モデルqkは補助モデル用パラメタ集合θkを対数線形モデルにより定義するものとし、補助モデル用パラメタ集合θkから得られる正則化項と教師なしデータDUを用いて、非負関数であって、入力構造xに対する出力構造yの擬似的な正解の度合いを表す参照関数rx,yと補助モデルqkとの間の正則化項付きブレグマン距離を最小にする補助モデル用パラメタ集合の集合Θを推定し、基本モデル用パラメタ集合λは、K個の補助モデルとそれぞれ1対1対応するK個の第2パラメタで構成される第2パラメタ集合v={v1,v2,...vK}を含むものとし、教師データDLと補助モデル用パラメタ集合の集合Θを用いて、事前に定義された経験リスク関数を最小にする基本モデル用パラメタ集合λを推定する。本発明は、教師なしデータを用いて、擬似的な正解の度合いを表す参照関数と補助モデルとの間のブレグマン距離を最小化する補助モデル用パラメタを推定する。このような構成とすることで、正解が不明な教師なしデータの正解を近似的に推定して利用することを可能とした。作成コストが高い教師データが少量でも、作成コストが低い教師なしデータを追加利用して構造予測モデルを学習でき、さらに構造予測モデルの予測性能を向上させることが可能となる。また、本発明は、補助モデルを対数線形モデル等により定義することで、ブレグマン距離を最小化する際に、L1ノルム正則化の技術を導入できる。L1ノルム正則化の技術を導入することで、活性状態にあるパラメータ言い換えると、0以外のパラメタの数を減らすことができる。このような構成とすることで、自然かつシステマティックに構造予測モデルを省メモリ化することができるという効果を奏する。さらに、このような構造予測モデルを利用すれば、構造予測器に必要な記憶量を削減できる。よって、構造予測モデルを記憶した外部記憶装置HDD等から主記憶装置メモリへのロード時間を短縮できる。また、特徴に対するインデックス引きの速度が向上し、構造予測に掛かる時間を短縮できる。<本発明のポイント>構造予測モデルは、入力構造xに対して出力構造yを予測するモデルである。また、本発明の一例において、構造予測モデルは数式を用いて以下のように定義される。式1は、入力構造xと出力構造yの組合せから抽出した特徴に対応するスコアを利用して構造を予測する。式1は、その特徴に対するスコアの総計が最も高い出力構造y^が、入力構造xに対して最も尤もらしい出力構造であるとし、予測結果として求める。但し、dx,y;λ,Θは、入力構造xに対して出力構造yが得られる可能性を表すスコアを返す判別関数を表す。dx,y;λ,Θの戻り値は1つの実数値である。また、dx,yは、後述する基本モデル用パラメタ集合λと補助モデル用パラメタ集合の集合Θを利用して、予め与えられた計算式を計算する。但し、λ={w,v1,v2,...,vK}とし、Θ={θ1,θ2,...,θK}とする。また、fx,yは、教師データDLから抽出した特徴の集合に対するD次元の基本モデル用特徴ベクトルを表す。wは、基本モデル用特徴ベクトルfx,yのD個の要素にそれぞれ1対1対応するD個の第1パラメタで構成される第1パラメタ集合を表す。また、gkx,yは、教師なしデータDLから抽出した特徴の集合をK個の部分集合に分割し、各部分集合kに含まれる特徴の集合に対するDk次元の補助モデル用特徴ベクトルを表す。θkは、特徴ベクトルgkx,yのDk個の要素にそれぞれ1対1対応するDk個の補助モデル用パラメタで構成される補助モデル用パラメタ集合を表す。なお、v={v1,v2,...,vK}を、K個の補助モデルとそれぞれ1対1対応するK個の第2パラメタで構成される第2パラメタ集合とする。但し、Kは自然数とし、k∈{1,2,...,K}とする。なお、基本モデルは、教師データDLを用いて、判別関数内で用いられる基本モデル用パラメタ集合λを推定するために用いられるモデルである。補助モデルは、教師なしデータDUを用いて、判別関数内で用いられる補助モデル用パラメタ集合Θを推定するために用いられるモデルである。各パラメタや各ベクトルの求め方は後述する。<補助モデル>構造予測モデルを学習する際に、教師なしデータでは出力構造yが不明であるため、直接入力構造xが与えられた時の出力構造yを利用した学習が行えない。そこで、本発明の一例では、K個の補助モデルを用いて正解の出力構造yを近似的に推定して利用する。補助モデルを非負関数として定義する。例えば、ロジスティック回帰モデルや、対数線形モデルが、補助モデルとして用いられる。次に、導入した補助モデルと、与えられた参照関数referencefunctionとのブレグマン距離Bregmandivergenceを最小化するように、補助モデル用パラメタ集合の集合Θを推定する。このとき、構造予測モデルを省メモリ化するために、L1ノルム正則化項を導入する。これにより、非ゼロのパラメタ数を最小に保ったまま最適なパラメタ集合の集合Θを推定できる。<局所的構造>式1において、入力構造xが与えられたときの可能な全ての出力構造の候補Yxの数は一般的に非常に大きくなる。このため、全ての候補Yxを列挙し、それぞれの特徴を抽出してスコアを評価するのは計算量的に困難となる場合が多い。この計算量の問題を克服するため、出力構造yを、局所的構造部分構造zに分解する。そして、出力構造yの大域的な特徴は使わず、局所的構造zから得られる特徴のみを利用して出力構造を予測する。局所的構造の定義は、扱う構造予測問題に合わせて自由に、人手により事前に定義すればよい。例えば、局所的構造は、出力構造グラフのクリークにより定義される。但し、出力構造内の要素を排他的に区分して、局所的構造を定義する必要はない。また、局所的構造の定義は、局所的構造同士が完全に包含関係にあるなど重複するような定義でもよい。あるいは逆に、局所的構造の定義は、任意の要素が被覆されていないような定義でもよい。ここで、ある出力構造yから事前の定義に従って得られる全ての局所的構造の集合をZx,yで表す。局所的構造の集合Zx,yの一つの要素をz∈Zx,yと表す。同様に、xから生成できる全ての出力候補の集合Yxに出現する全ての局所的構造の集合をZx,Yxと表す。ここで、与えられた入力構造xと任意の局所的構造zの情報から抽出される特徴ベクトルをfx,z、または、gkx,zと書くこととする。このとき、本発明の一例では、以下の等式が成り立つこととする。式2は、各局所的構造zで得られた特徴ベクトルfx,zの総和が出力構造全体の特徴ベクトルfx,yとなることを意味する。式3は、各局所的構造zで得られた特徴ベクトルgkx,zの総和が出力構造全体の特徴ベクトルgkx,yとなることを意味する。なお、式1は、以下の式1’で表すことができる。次に、基本モデルP及び補助モデルqkを定義する。qkはk番目の補助モデルを表す。3つのタイプの補助モデルを例示する。なお、何れのタイプの補助モデルも、非負関数であり、補助モデル用パラメタ集合θkを対数線形モデルにより定義する。<補助モデルタイプ1>タイプ1のk番目の補助モデルをq1kと表す。xが与えられたときに出力構造yが出力される条件付確率qyxと出力されない条件付確率q¬yx=1-qyxは以下の式で表される。但し、by=Σzbzは1以上の値を返す関数を表す。また、byには、θkgkx,y=0のとき、式4が、一様分布と一致するような値を代入する。次に、q1kのオッズを用いてq’1kを以下のように定義する。よって、q’1kは、q1kのを1/by倍した値になる。つまり、q’1kはq1kに比例する値となる。ここで、以降の処理のために、Qkを以下のように定義する。Qkzx;θk=q1kzx,θk6但し、q1kzx,θkは、xが与えられたときの出力構造yのなかに局所的構造zが出現する条件付確率を表す。この条件付確率は、q1kyx,θkの定義から、zの周辺確率として計算できる。<補助モデルタイプ2>タイプ2の補助モデルをq2kと表す。q2kは、計算量を削減するために、より簡単な構造を導入する。タイプ2の補助モデルは、入力構造xに対する出力構造yをモデル化するのではなく、yを構成する個々の局所的構造zに対するモデル化を行う。xが与えられたときに出力構造yに局所的構造zが含まれる条件付確率qzxと出力されない条件付確率q¬zx=1-qzxは以下の式で表される。但し、bzを局所的構造zの対立候補となる局所的構造の個数とする。これは、θkgkx,z=0をデフォルトの値と仮定した場合、zの出現確率が対立候補と等確率となるような補正項を意味する。次に、q2kのオッズを用いてq’2kを以下のように定義する。ここで以降の処理のために、Qkを以下のように定義する。<補助モデルタイプ3>タイプ3の補助モデルをq3kと表す。q3kは、さらに補助モデルの計算量を削減できる。タイプ3の補助モデルは、個々の局所的構造zの出現確率を単一の特徴nのみでモデル化する。xが与えられたときに出力構造yにnを特徴とする局所的構造zが含まれる条件付確率qzx,nと出力されない条件付確率q¬zx,n=1-qzx,nは以下の式で表される。次に、q3kのオッズを用いてq’3kを以下のように定義する。ここでタイプ1、2と同様に以降の処理のために、Qkを以下のように定義する。但し、θk=θk1,θk2,...,θkDk、gkx,z=gkx,z,1,gkx,z,2,...,gkx,z,Dkとする。Qkはq3kのオッズまたはq’3kをn=1,2,...,Dkまでをまとめたものに相当する。<基本モデル>基本モデルは、学習後の構造予測モデルが式1’で記述できるものであれば、どのようなモデルでもよい。ここでは、式6、9、12において補助モデルq1k、q2k、q3kのそれぞれから得られるQkを導入して、基本モデルを定義する。基本モデルを確率モデルに基づき定義する場合と、基本モデルをマージン最大化モデル原理に基づき定義する場合を例示する<確率モデルに基づく基本モデルの定義>基本モデルPを確率モデルに基づき定義する場合には、以下のように表す。これは、入力構造xが与えられたときの出力構造yが出る条件付確率Py|xを、対数線形モデルと補助モデルとの各局所的構造z毎の積として定義していることを意味する。なお、実際には、補助モデルq1k、q2k、q3kの何れを利用しても、式13の右辺を整理して以下のように書ける。特に、補助モデルの数が1のときつまりK=1、かつ、基本モデル用特徴ベクトルと補助モデル用特徴ベクトルが同じときつまりfx,y=g1x,y、式14を整理してdを以下のように示すことができる。<マージン最大化モデルに基づく基本モデルの定義>基本モデルPを線形識別モデルでのマージン最大化に基づき定義する場合には、以下のように表す。但し、Ey,y^は、ある正解の出力yと任意の出力y^を比較した際のy^の誤りの度合いを表す関数である。Ey,y^は、誤りが大きければ、つまり、yとy^の違いが大きければ大きいほど値が大きくなる。なお、A\Bは、集合Aから集合Bを引いた差集合を表す。式16は、入力構造xに対する正解の出力構造yのスコアdx,y;λ,Θと、最も誤りリスクの高い不正解の出力y^のスコアdx,y^;λ,Θの差分が、エラーの推定値Ey,y^以上になるようにする。以下、これらの定義を用いて、本発明の実施の形態について、詳細に説明する。図4に示すように、構造予測モデル学習装置100は、学習フェーズにおいて、構造予測モデル学習装置100は、教師データDLと、教師なしデータDUと、学習支援情報記憶部4に格納された情報とを用いて、構造予測モデルを学習し、学習後の構造予測モデルを構造予測モデル記憶部6に出力する。構造予測モデル記憶部6は学習後の構造予測モデルを記憶する。構造予測器7は、構造予測モデル記憶部6から構造予測モデルを受け取る。さらに、構造予測器7は、ラベルなしサンプルSU入力構造xを受け取り、これに対するラベル有りサンプルSL出力構造yを、構造予測モデルを利用して推定し、出力する。なお、教師データDLは入力構造xと教師信号理想的な出力構造yのペアの集合である。サンプル数がN個の教師データをDL={xn,yn}Nn=1と表す。教師なしデータDUは入力構造xのみからなるデータの集合であり、正解の出力構造yが不明なデータの集合である。サンプル数がM個の教師なしデータをDU={xm}Mm=1と表す。なお、例えば図1に示されている固有表現抽出の場合には、構造予測モデルを学習するために、N=1万、M≧1000万といった規模のサンプルが必要となる。学習支援情報記憶部4は、学習支援情報として、後記する特徴抽出テンプレートT2と、出力候補生成用定義データ集合T1とを記憶するものである。<構造予測モデル学習装置100>図5、図6を用いて実施例1に係る構造予測モデル学習装置100を説明する。構造予測モデル学習装置100は、例えば、CPUCentralProcessingUnitと、RAMRandomAccessMemoryと、ROMReadOnlyMemoryと、HDDHardDiskDriveと、入出力インタフェース等から構成される。構造予測モデル学習装置100は、例えば、記憶部103と、制御部105と、出力候補グラフ生成部110と、特徴ベクトル生成部120と、パラメタ生成部130と、補助モデル用パラメタ推定部140と、基本モデル用パラメタ推定部160と、第1収束判定部180と、パラメタ統合部190を備える。このうち、出力候補グラフ生成部110と特徴ベクトル生成部120は、学習のための前処理を行うためのものである。<記憶部103及び制御部105>記憶部103は、前述のRAM、ROM、HDD等からなる。記憶部103は、教師データDL、教師なしデータDU、学習支援情報、処理途中の信号や各種パラメタ等を記憶する。制御部105は、前述のCPU等からなる。制御部105は、記憶部103に対し、各処理過程で所定の信号やパラメタの読み書きを行う。但し、制御部105は、必ずしも記憶部103に対し各データの読み書きを行わなければならないわけではなく、各部間で直接データを受け渡すように制御してもよい。<入力データ例>本実施例では、英語のテキストデータからなる入力構造に対し、固有表現を示すラベルを付与する出力構造を予測するために利用される構造予測モデルを学習する例を示す。図7、図8は、図5に示した構造予測モデル学習装置100に入力する情報の例を示す図である。図7は英語の教師データを、図8は英語の教師なしデータをそれぞれ示す。図7に示す例は、図1に示したものと同様である。但し、トークン区切りは事前に施されているものとする。図9は、出力候補生成用定義データ集合T1を示す。この例では、出力候補生成用定義データ集合は、予め定められた5つの出力候補生成用定義データを要素としている。この出力候補生成用定義データ集合T1は、対象とする構造予測問題によって自動的に決定される。構造予測モデル学習装置100は、この出力候補生成用定義データ集合T1を学習支援情報記憶部4から取得する。<出力候補グラフ生成部110>出力候補グラフ生成部110は、教師データDLと教師なしデータDUと出力候補生成用定義データ集合T1を受け取る。そして、出力候補グラフ生成部110は、構造予測問題により特定される出力候補生成用定義データ集合T1を用いて、受け取った教師データDLに対する教師データ用出力候補グラフGrDLを生成するs110。出力候補グラフ生成部110は、同様に出力候補生成用定義データ集合T1を用いて、受け取った教師なしデータDUに対する教師なしデータ用出力候補グラフGrDUを生成するs110。出力候補グラフ生成部110は、受け取った教師データDLと、その教師データDLから生成した教師データ用出力候補グラフGrDLとを対応付ける。出力候補グラフ生成部110は、受け取った教師なしデータDUと、その教師なしデータDUから生成した教師なしデータ用出力候補グラフGrDUとを対応付ける。さらに、出力候補グラフ生成部110は、各データを特徴ベクトル生成部120に出力する。出力候補グラフは、図10に示すように、可能性のある全ての出力構造候補をパスで接続したラティス形式で表現したものである。なお、以下の例では、出力候補生成用定義データ集合は、予め定められた3つの出力候補生成用定義データを要素としている。図10の例では、出力候補生成用定義データ集合はPER.、ORG.、Oの3つの出力候補生成用定義データを要素としている。図10は、図5に示した構造予測モデル学習装置100で生成される出力候補グラフの一例を模式的に示す図である。ここで、<BOS>は、入力構造xの始まりを表す固定の特別なラベルであり、<EOS>は、入力構造xの終わりを表す固定の特別なラベルである。ラティスは、入力構造x教師データDLまたは教師なしデータDUに対する出力構造yを示すものであり、出力構造yの個々のインスタンスyee=1,2,3をノードで示し、各インスタンス間の依存関係をリンクで示す。出力候補グラフ中の<BOS>から<EOS>間の1つのパスは1つの出力に対応し、出力候補グラフは、とり得る全ての出力の候補を包含したグラフになっている。例えば、図10の出力候補グラフは38通りのパス出力候補を包含する。例えば、図10のノード401は、入力構造xの4番目の単語SDに対してラベルORG.を付与した出力のインスタンスを示す。同様に、図10のノード402は、入力構造xの6番目の単語twoに対してラベルOを付与した出力のインスタンスを示す。<特徴ベクトル生成部120>特徴ベクトル生成部120は、特徴抽出テンプレートT2と教師データ用出力候補グラフGrDLと教師なしデータ用出力候補グラフGrDUを受け取る。そして、特徴ベクトル生成部120は、受け取った特徴抽出テンプレートT2を用いて、教師データ用出力候補グラフGrDL及び教師なしデータ用出力候補グラフGrDUから特徴を抽出するs120。さらに、特徴ベクトル生成部120は、教師データ用出力候補グラフGrDLから抽出した特徴の集合に対するD次元の基本モデル用特徴ベクトルfx,yを生成するs120。また、特徴ベクトル生成部120は、教師なしデータ用出力候補グラフGrDUから抽出した特徴の集合をK個の部分集合に分割する。特徴ベクトル生成部120は、部分集合kに含まれる特徴に対するDk次元の補助モデル用特徴ベクトルgkx,yを生成するs120。特徴ベクトル生成部120は、教師データ用出力候補グラフGrDLに基本モデル用特徴ベクトルfx,yを付与して、パラメタ生成部130に出力する。また、特徴ベクトル生成部120は、教師なしデータ用出力候補グラフGrDUに補助モデル用特徴ベクトルgkx,yを付与して、パラメタ生成部130に出力する。以下、特徴ベクトル生成部120が、出力候補グラフから特徴を抽出する方法を説明する。特徴ベクトル生成部120は、出力候補グラフから、ラベルyiと、特徴抽出テンプレートに記述された入力構造中のインスタンスとの組合せにより、特徴を抽出する。但し、yiは出力構造のi番目のラベルを表す。図11は、特徴抽出テンプレートT2の例を示す図である。特徴ベクトル生成部120は、この特徴抽出テンプレートT2を用いて、ラベルyiとその前後2個ずつまでに対応する入力単語xi-2、xi-1、xi、xi1、xi2それぞれとの組合せyixi-2、yixi-1、yixi、yixi1、yixi2や、ラベルyiの後2個の入力単語xi1とxi2とyiとの組合せyixi1xi2等を特徴として抽出する。図12に、特徴ベクトル生成部120が、特徴抽出テンプレートT2を用いて、出力候補グラフから特徴を抽出する例を示す。図12において、ノード411は出力構造1番目のラベルy1がPER.である場合を示す。このとき、特徴ベクトル生成部120は、図12に示す特徴411Aを抽出する。図12において、ノード412は出力構造3番目のラベルy3がORG.である場合を示す。このとき、特徴ベクトル生成部120は、図12に示す特徴412Aを抽出する。図12において、ノード413は出力構造5番目y5のラベルがORG.である場合を示す。このとき、特徴ベクトル生成部120は、図12に示す特徴413Aを抽出する。次に、特徴ベクトルを生成し、付与する方法を説明する。特徴ベクトル生成部120は、全ての教師データDLから得られる全ての教師データ用出力候補グラフGrDLの全てのノードから抽出される特徴を集め、そこから重複する特徴を削除し、教師データ用特徴集合を生成する。なお、各教師なしデータ用特徴集合に含まれる要素の数をD個とする。同様に、特徴ベクトル生成部120は、全ての教師なしデータDUから得られる全ての教師なしデータ用出力候補グラフGrDUの全てのノードから抽出される特徴を集め、そこから重複する特徴を削除し、教師なしデータ用特徴集合を生成する。さらに、特徴ベクトル生成部120は、生成した教師なしデータ用特徴集合を、K個の部分集合に分割する。なお、特徴のタイプに応じて、教師なしデータ用特徴集合を分割するとよい。特徴のタイプは、例えば、その教師なしデータの媒体新聞やWeb等、内容経済、スポーツ等、作成者により分類される。なお、各部分集合に含まれる要素の数をDk個とする。異なる特徴のタイプが異なる分布を持つことがあるため、このような構成とすることで、より予測性能を向上させることができる。特徴ベクトル生成部120は、出力候補グラフの各ノードまたは各リンクに対して、特徴ベクトルを付与する。基本モデル用特徴ベクトルfx,yは、教師データ用出力候補グラフGrDLから抽出した特徴の集合の要素と1対1対応する要素からなるD次元のベクトルである。なお、補助モデル用特徴ベクトルgkx,yは、教師なしデータ用出力候補グラフGrDUから抽出した特徴の集合の部分集合の要素と1対1対応する要素からなるDk次元のベクトルである。なお、教師データ用出力候補グラフGrDLであっても、教師なしデータ用出力候補グラフGrDUであっても、特徴ベクトルを付与する方法は、同じである。図13は、図12のノード411に対して、付与される特徴ベクトルの説明図である。図14は、図12のノード412に対して、付与される特徴ベクトルの説明図である。特徴ベクトル生成部120は、各ノードから抽出した特徴には値1を紐付け、また、各ノードから抽出できなかった特徴には値0を紐付けることで、1と0とを要素に持つ特徴ベクトルを生成する。特徴ベクトル生成部120は、生成した特徴ベクトルを対応するノードに付与する。なお、特徴ベクトル生成部120は、各ラベルとその前後2個ずつまでに対応する入力単語それぞれとの組合せ等で特徴を生成する。そのため、入力構造のi番目の単語に対する出力構造のi番目のラベルの違うノードの特徴ベクトルは、それぞれ互いに直交する。よって、それらの内積は0となる。<パラメタ生成部130>パラメタ生成部130は、基本モデル用特徴ベクトルfx,yが付与された教師データ用出力候補グラフGrDLと補助モデル用特徴ベクトルgkx,yが付与された教師なしデータ用出力候補グラフGrDUを受け取る。パラメタ生成部130は、基本モデル用特徴ベクトルfx,yのD個の要素にそれぞれ1対1対応するD個の第1パラメタで構成される第1パラメタ集合w={w1,w2,...,wD}を含む基本モデル用パラメタ集合λを生成しs130、基本モデル用パラメタ推定部160に出力する。また、パラメタ生成部130は、補助モデル用特徴ベクトルgkx,yのDk個の要素にそれぞれ1対1対応するDk個の補助モデル用パラメタで構成される補助モデル用パラメタ集合θk={θk1,θk2,...,θkD}を生成する。さらに、パラメタ生成部130は、K個の補助モデル用パラメタ集合θkで構成される補助モデル用パラメタ集合の集合Θ={θ1,θ2,...,θK}を生成しs130、補助モデル用パラメタ推定部140に出力する。なお、パラメタ生成部130は、例えば、各パラメタに初期値として0を設定する。図15に、基本モデル用パラメタ集合λのデータ例を示す。図16に、補助モデル用パラメタ集合の集合Θのデータ例を示す。また、パラメタ生成部130は、補助モデル用パラメタ推定部140と基本モデル用パラメタ推定部160の繰り返し回数を示すパラメタt=0を生成してもよい。<補助モデル用パラメタ推定部140>補助モデル用パラメタ推定部140は、補助モデル用パラメタ集合θkから正則化項を求める。さらに、補助モデル用パラメタ推定部140は、教師なしデータDUを用いて、参照関数rx,yと補助モデルqkとの間の正則化項付きブレグマン距離を最小にする補助モデル用パラメタ集合の集合Θを推定するs140。例えば、補助モデル用パラメタ推定部140は、参照関数rx,yと、補助モデル用パラメタ集合の集合Θと、補助モデル用特徴ベクトルgkx,yが付与された教師なしデータ用出力候補グラフGrDUを受け取る。補助モデル用パラメタ推定部140は、参照関数rと補助モデルqk間のブレグマン距離を最小化する補助モデル用パラメタ集合の集合Θを推定する。ここで、参照関数と補助モデル間のブレグマン距離を最小化するとは、解空間の中で補助モデルが参照関数に最も近くなるような補助モデル用パラメタ集合の集合Θを求めることを意味する。また、ブレグマン距離を最小化する際に、L1正則化項を導入する。これにより、学習後の構造予測モデルを省メモリ化することができる。なお、各補助モデルqkが補助モデル用パラメタ集合θkを確率モデルにより定義する場合には、その総和が1でなければならないため、L1正則化項を導入することはできない。本実施例では、各補助モデルqkが補助モデル用パラメタ集合θkを対数線形モデルにより定義する。対数線形モデルには、上記制約がないため、L1正則化項を導入できる。参照関数まず、参照関数を定義する。参照関数rx,yは、非負関数である。つまり、その値域は0,∞である。但し、上述の補助モデルq1k、q2k、q3kを利用する場合には、それらの値域が0,1]なので、参照関数の値域も0,1とする。また、参照関数rx,yは、入力構造xに対する出力構造yの擬似的な正解の度合いを表す。例えば、初めて、補助モデル用パラメタ推定部140が補助モデル用パラメタを推定する場合には、事前に教師ありデータDLを用いて、第1パラメタ集合wを推定し特開2008-225907号公報参照、推定した第1パラメタ集合wを対数線形モデルで定義した基本モデル但し、補助モデルはなく、例えば、第2パラメタvの各要素に0を設定するを参照関数とする。この場合、rx、z=Pzx,wとなる。さらに、2回目以降、補助モデル用パラメタ推定部140が補助モデル用パラメタを推定する場合には、繰り返し計算の際に1つ前の繰り返しで得られた基本モデルPzx,λt-1,Θt-1を参照関数として利用する。また、例えば、参照関数として、人間が事前に決めた関数や、全く別のモデル例えば、特開2008-225907号公報記載の言語解析モデルを用いることができる。ブレグマン距離参照関数rと補助モデルqk間のブレグマン距離BFは、以下のように定義される。このとき、Fは、任意の連続微分可能実数値関数であり、かつ、狭義凸関数である。例えば、FとしてL2ノルムが用いられる。本実施例では、Fx=Σxlogx-Σxとする。このとき、ブレグマン距離BFは、以下の式22に示すように、一般化相対エントロピーGと一致する。最終的に、補助モデル用パラメタ集合の集合Θの推定は、参照関数rと補助モデルqk間の一般化相対エントロピーGをL1ノルム正則化項付きで最小化することに帰着する。また、一般化相対エントロピーを正確に求めるには、全ての可能性のある入力と出力のペアx,yが必要である。しかし、全ての可能性のある入力と出力のペアを列挙することは不可能である。よって、実際には、全ての可能性のある入力と出力のペアの代わりに、教師なしデータDUを使った実測値を用いる。この限られた大きさの実測値を用いて得られる一般化相対エントロピーを、経験一般化相対エントロピーと呼び、G^DUと表す。よって、最適な補助モデル用パラメタ集合の集合Θを求める式つまり、正則化項付き経験一般化相対エントロピーUΘ|DUを最小化する式は、以下のように表される。なお、θk1はk番目の補助モデル用パラメタ集合θkのL1ノルムを表す。また、CUは、右辺第1項と右辺第2項の重要度を調節する変数である。つまり、CUは、経験一般化相対エントロピーとL1正則化項のどちらを重要視するかを決める。また、CUは、人手でチューニングするハイパーパラメタである。以下に、補助モデルq1k、q2k、q3k、q’1k、q’2kまたはq’3kを用いた場合に、得られる正則化項付き経験一般化相対エントロピーUΘ|DUを示す。q1を用いた場合補助モデルとしてq1kを用いた場合、式22、式23及び式4を用いて、正則化項付き経験一般化相対エントロピーUΘ|DUは以下のように表される。なお、constθkは、θkに対して定数項になるものをまとめた値である。なお、最適化する際にUΘ|DUを最小化する際に、constθkは解に影響を与えない。また、式24の勾配は以下のように表される。但し、σaは、ベクトルaの各要素に対して-1、0、1の3つの値のどれかで構成するベクトルを返す関数である。σaは、要素が0より大きいとき1で、要素が0より小さいとき-1で、0のとき0で、それぞれ要素を置き換えたベクトルを返す。全てのkで∇kUΘDU=0のときに、式23は最適値を得るつまり、UΘ|DUの最小値を得る。実際には、勾配に基づく最適化法により最適値を求めることができる。q’1を用いた場合q’1kを用いた場合、式22、式23及び式5を用いて、正則化項付き経験一般化相対エントロピーUΘ|DUは以下のように表される。また、式26の勾配は以下のように表される。q2を用いた場合補助モデルとしてq2kを用いた場合、式22、式23及び式7を用いて、正則化項付き経験一般化相対エントロピーUΘ|DUは以下のように表される。また、式28の勾配は以下のように表される。q’2を用いた場合q’2kを用いた場合、式22、式23及び式8を用いて、正則化項付き経験一般化相対エントロピーUΘ|DUは以下のように表される。また、式30の勾配は以下のように表される。タイプ2の補助モデルの場合は、出力構造y全体ではなく、各局所構造z単位に計算する。このような構成により、タイプ1と比較して、高速化が期待できる。ダイプ1の補助モデルを用いた場合と同様に、タイプ2の補助モデルを用いた場合も、勾配に基づく最適化法により最適値を求めることができる。q3を用いた場合補助モデルとしてq3kを用いた場合、式22、式23及び式10を用いて、正則化項付き経験一般化相対エントロピーUΘ|DUは以下のように表される。また、式32の勾配は以下のように表される。q’3を用いた場合q’3kを用いた場合、式22、式23及び式11を用いて、正則化項付き経験一般化相対エントロピーUΘ|DUは以下のように表される。また、式34の勾配は以下のように表される。タイプ3の補助モデルを用いた場合、各パラメタ間の依存関係を考慮しなくてよくなる。そのため、1変数の線形探索で解を求めることができる。よって、数値最適化時の計算量の大部分を占める勾配の計算が非常に簡単になる。このため、タイプ3の補助モデルを用いることは、学習時の計算量の面で非常に優れている。なお、タイプ1、2、3の補助モデルの何れを用いた場合にも、正則化項付き経験一般化相対エントロピーUΘ|DUは、各パラメタに対して凸関数となる。よって、最適解は唯一に決定する。補助モデル用パラメタ推定部140の構成例及び処理フロー図17及び図18を用いて補助モデル用パラメタ推定部140を説明する。補助モデル用パラメタ推定部140は、条件付き確率場に基づいて補助モデル用集合の集合Θを推定するために、例えば、正則化項付き経験一般化相対エントロピー計算部145と勾配計算部147と第2収束判定部149とパラメタ更新部151とを備える。なお、条件付き確率場については、例えば、FShaandFPereiraShallowParsingwithConditionalRandomFieldsInProcofHLTNAACL2003pages1341412003以下、参考文献1というに詳述されているので説明を省略する。正則化項付き経験一般化相対エントロピー計算部145は、教師なしデータDUと参照関数rx,yと補助モデル用パラメタの集合の集合Θを受け取り、式24、26、28、30、32、34の何れかの正則化項付き経験一般化相対エントロピーUΘ|DUを計算するs145。さらに、正則化項付き経験一般化相対エントロピー計算部145は、正則化項付き経験一般化相対エントロピーUΘ|DUを、勾配計算部147に出力する。正則化項付き経験一般化相対エントロピーUΘ|DUを最適化最小化するには、L-BFGSといった勾配に基づく数値最適化法を適用することができる。なお、L-BFGSについては、例えば、DCLiuandJNocedalOntheLimitedMemoryBFGSMethodforLargeScaleOptimizationMathProgrammingSerB1989Volume45Issue3p503528以下、参考文献2というに記載されているので、説明を省略する。勾配計算部147は、UΘ|DUの勾配を計算するものである。式24、26、28、30、32、34の勾配はそれぞれ式25、27、29、31、33、35で示される。第2収束判定部149は、式25、27、29、31、33、35で示される勾配∇UΘ|DUが収束したか否かを判定するs149。また、第2収束判定部149は、勾配∇UΘ|DUの値が収束したと判定した場合には、その時点の補助モデル用パラメタ集合の集合Θを、第1収束判定部180と基本モデル用パラメタ推定部160に出力する。パラメタ更新部151は、勾配∇UΘ|DUの値が収束していない場合に、補助モデル用パラメタ集合の集合Θを更新するs151。<基本モデル用パラメタ推定部160>基本モデル用パラメタ推定部160は、教師データDLと補助モデル用パラメタ集合の集合Θを用いて、事前に定義された経験リスク関数を最小にする基本モデル用パラメタ集合λを推定するs160。リスク関数と正則化項の定義の選択肢は様々な可能性がある。例えば、以下のように定義する。ここで、Rλ|Θ,DLは、任意のリスク関数を表す。リスク関数とは、学習時の誤りを推定するための任意の関数である。つまり、リスク関数の値が小さい程学習がうまくできていることを表す。また、CLは、式23のCUと同様の人手でチューニングするハイパーパラメタである。また、Ωλは、λに関する正則化項を表す。例えば、正則化項として、L1ノルム正則化項やL2ノルム正則化項が用いられる。リスク関数として負の対数尤度を用いる場合まず、リスク関数に負の対数尤度を用いる場合を示す。負の正則化対数尤度最小化では、以下の式により最適パラメタを求める。これは、基本モデルに確率モデルを利用した場合の一般的な最適化の方法である。式43の勾配は以下のように表すことができる。このとき、正則化項の勾配は、以下のように示される。式41に式43を代入した場合、式41の勾配は以下のように表される。実際の教師データDL内に出現した特徴ベクトルの総和をとったベクトルとなる。式41の最適パラメタは、式46での勾配が0となるときに得られる。実際の最適化では、LBFGSといった勾配に基づく数値最適化法により求めることができる参考文献2参照。マージン最大化モデルに基づき推定する場合次に、マージン最大化原理に基づき基本モデル用パラメタ集合λを推定する場合について説明する。この場合は、リスク関数は以下のように表される。例えば、式41に式47と式45のL2正則化を代入した場合、式41の勾配は以下のよRλ|Θ,DL=0の場合、Lλ|Θを微分できない。そのため、通常の勾配法ではLλ|Θ,DLを最適化できない。この場合、劣勾配法を用いてLλ|Θ,DLを最適化することができる。基本モデル用パラメタ推定部160の構成例及び処理フロー図19及び図20を用いて基本モデル用パラメタ推定部160を説明する。基本モデル用パラメタ推定部160は、条件付き確率場参考文献1参照に基づいて基本モデル用パラメタ集合λを推定するために、図19に示すように、例えば、経験リスク関数計算部161と正則化項計算部163と、正則化項付き経験リスク関数計算部165と勾配計算部167と第3収束判定部169とパラメタ更新部171とを備える。経験リスク関数計算部161は、教師データDLと補助モデル用パラメタ集合の集合Θと基本モデル用パラメタ集合λを受け取り、式43または式47の経験リスク関数Rλ|Θ,DLを計算するs161。さらに、経験リスク関数計算部161は、Rλ|Θ,DLを正則化項付き経験リスク関数計算部165に出力する。正則化項計算部163は、基本モデル用パラメタ集合λを受け取り、式42の正則化項Ωλを計算するs163。さらに、正則化項計算部163は、Ωλを正則化項付き経験リスク関数計算部165に出力する。正則化項付き経験リスク関数計算部165は、経験リスク関数Rλ|Θ,DLと正則化項Ωλを受け取り、式41に代入し、の正則化項付き経験リスク関数Lλ|Θ,DLを計算するs165。さらに、正則化項付き経験リスク関数計算部165は、正則化項付き経験リスク関数Lλ|Θ,DLを、勾配計算部167に出力する。正則化項付き経験リスク関数Lλ|Θ,DLを最適化するには、L-BFGSといった勾配に基づく数値最適化法を適用することができる。なお、L-BFGSについては、参考文献2に記載されているので、説明を省略する。勾配計算部167は、式46または48の勾配∇Lλ|Θ,DLを計算するs167。第3収束判定部169は、式46または48の勾配∇Lλ|Θ,DLが収束したか否かを判定するs169。また、第3収束判定部169は、勾配∇Lλ|Θ,DLの値が収束したと判定した場合には、その時点の基本モデル用パラメタ集合λを、第1収束判定部180に出力する。パラメタ更新部171は、勾配∇Lλ|Θ,DLの値が収束していない場合に、基本モデル用パラメタ集合λを更新するs171。<第1収束判定部180>第1収束判定部180は、基本モデル用パラメタ集合λと補助モデル用パラメタ集合の集合Θの値を受け取り、これらの値が、収束したか否かを判定するs180。なお、特許請求の範囲における収束判定部は、第1収束判定部180に対応する。第1収束判定部180は、例えばパラメタの増分を用いて、判定する。第1収束判定部180は、|λ-λ||Θ-Θ|の値が、閾値以下となった場合、収束したと判定する。または、第1収束判定部180は、事前に繰り返し回数Tを決定しておいて、繰り返し回数tが規定の回数Tt=Tに達したら、収束したと判定してもよい。第1収束判定部180が収束していないと判定した場合には、補助モデル用パラメタ推定部140に対して、補助モデル用パラメタ集合の集合Θと基本モデル用パラメタ集合λを推定する処理を繰り返すことを指示する制御信号cを出力する。第1収束判定部180は、また繰り返し回数を示すパラメタtを1増加させるt←t1。なお、このとき、参照関数rとして、繰り返し処理における1つ前の基本モデルPx,y;λt-1,Θt-1を出力してもよい。第1収束判定部180が収束したと判定した場合には、そのときの補助モデル用パラメタ集合の集合Θと基本モデル用パラメタ集合λをパラメタ統合部190に出力する。<パラメタ統合部190>パラメタ統合部190は、収束した基本モデル用パラメタ集合λと補助モデル用パラメタ集合の集合Θを統合するs190。パラメタ統合部190は、例えば、基本モデルのj番目の特徴と、k番目の補助モデルのp番目の特徴が一致する場合には、統合後のパラメタ集合uのi番目の要素uiを以下の式により求める。図21にパラメタ集合uのデータ例を示す。ui=wjvkθp51また、例えば、基本モデルにしかi番目の要素uiに対応する特徴がない場合には、パラメタ統合部190は、要素uiを以下の式により求める。ui=wj52また、例えば、補助モデルにしかi番目の要素uiに対応する特徴がない場合には、要素uiを以下の式により求める。ui=vkθp53このとき、構造予測モデルは、式1に代えて、以下の式で表すことができる。但し、基本モデル用パラメタ集合λと補助モデル用パラメタ集合の集合Θを統合したときのパラメタ集合uの要素の数をIとすると、u={u1,u2,...,uI}である。さらに、パラメタ統合部190は、統合したパラメタ集合u、または、パラメタ集合uを用いて表される構造予測モデルを構造予測モデル記憶手段6に出力する。本実施例では、θklの多くがゼロつまり活性状態ではないパラメータとなっている。このとき、式52により求められるuiもゼロのパラメータとなる。<効果>このような構成とすることで、学習後の構造予測モデルから活性状態にないパラメタ言い換えると、0のパラメタ及びそのパラメタに対応する特徴を削除することで、学習後の構造予測モデルを省メモリ化することができる。さらに、教師データと教師なしデータに基づき作成された構造予測データは高い予測性能を維持したまま、省メモリ化を実現している。実験結果を後述する。なお、教師データDLから得られる基本モデル用パラメタ集合の要素数は、前述の通り、教師データDLの生成コストが高いため、それほど多くは得られない。一方、教師なしデータDUから得られる補助モデル用パラメタ集合の集合Θの要素数は、膨大な量を容易に求めることができる。このΘの要素のほとんどをゼロにすることで、省メモリ化を実現する。<ハードウェア構成>図22は、本実施例における構造予測モデル学習装置100のハードウェア構成を例示したブロック図である。図22に例示するように、この例の構造予測モデル学習装置100は、それぞれCPUCentralProcessingUnit11、入力部12、出力部13、補助記憶装置14、ROMReadOnlyMemory15、RAMRandomAccessMemory16及びバス17を有している。この例のCPU11は、制御部11a、演算部11b及びレジスタ11cを有し、レジスタ11cに読み込まれた各種プログラムに従って様々な演算処理を実行する。また、入力部12は、データが入力される入力インタフェース、キーボード、マウス等であり、出力部13は、データが出力される出力インタフェース、ディスプレイ、プリンタ等である。補助記憶装置14は、例えば、ハードディスク、半導体メモリ等であり、構造予測モデル学習装置100としてコンピュータを機能させるためのプログラムや各種データが格納される。また、RAM16には、上記のプログラムや各種データが展開され、CPU11等から利用される。また、バス17は、CPU11、入力部12、出力部13、補助記憶装置14、ROM15及びRAM16を通信可能に接続する。なお、このようなハードウェアの具体例としては、例えば、パーソナルコンピュータの他、サーバ装置やワークステーション等を例示できる。<プログラム構成>上述のように、補助記憶装置14には、本実施例の構造予測モデル学習装置100の各処理を実行するための各プログラムが格納される。構造予測プログラムを構成する各プログラムは、単一のプログラム列として記載されていてもよく、また、少なくとも一部のプログラムが別個のモジュールとしてライブラリに格納されていてもよい。<ハードウェアとプログラムとの協働>CPU11は、読み込まれたOSプログラムに従い、補助記憶装置14に格納されている上述のプログラムや各種データをRAM16に展開する。そして、このプログラムやデータが書き込まれたRAM16上のアドレスがCPU11のレジスタ11cに格納される。CPU11の制御部11aは、レジスタ11cに格納されたこれらのアドレスを順次読み出し、読み出したアドレスが示すRAM16上の領域からプログラムやデータを読み出し、そのプログラムが示す演算を演算部11bに順次実行させ、その演算結果をレジスタ11cに格納していく。図5は、このようにCPU11に上述のプログラムが読み込まれて実行されることにより構成される構造予測モデル学習装置100の機能構成を例示したブロック図である。ここで、記憶部103は、補助記憶装置14、RAM16、レジスタ11c、その他のバッファメモリやキャッシュメモリ等の何れか、あるいはこれらを併用した記憶領域に相当する。また、出力候補グラフ生成部110、特徴ベクトル生成部120、パラメタ生成部130、補助モデル用パラメタ推定部140、基本モデル用パラメタ推定部160、第1収束判定部180、パラメタ統合部190は、CPU11に構造予測プログラムを実行させることにより構成されるものである。<実験結果>図23において、教師データのみに基づき学習された構造予測モデルを用いた構造予測器の正解率を一点鎖線で示し、タイプ3の補助モデルを利用した構造予測モデル学習装置100により学習された構造予測モデルを用いた構造予測器の正解率を実線で示す。何れのパラメタ数であっても、構造予測モデル学習装置100により学習された構造予測モデルを用いた構造予測器の正解率のほうが高い。また、正解率92.5弱の場合には、構造予測モデル学習装置100により学習された構造予測モデルで利用されるパラメタuの数は、教師データのみに基づき学習された構造予測モデルで利用されるパラメタ集合の要素の数の約10分の1程度となることが分かる。<変形例>構造予測モデル学習装置100、学習支援情報記憶部4、構造予測モデル記憶部6及び構造予測器7を一体化し、1つの計算機上で実現してもよい。構造予測モデル学習装置100は、問題に応じて、出力候補定義データ集合や特徴抽出テンプレートを代えることで、系列構造予測問題以外の問題に対しても利用可能である。図24は、係り受け構造予測問題に対する出力候補グラフの例を示す。なお、特徴ベクトル生成部120は、教師データ用出力候補グラフGrDLから抽出した特徴の集合と、教師なしデータ用出力候補グラフGrDUから抽出した特徴の集合を合体してもよい。特徴ベクトル生成部120は、合体した特徴の集合から重複する特徴を削除し、共通の特徴集合を生成する。このとき、基本モデル用特徴ベクトルfx,yは、共通の特徴の集合の要素と1対1対応する要素からなるD次元のベクトルである。補助モデル用特徴ベクトルgkx,yは、共通の特徴の集合の部分集合の要素と1対1対応する要素からなるDk次元のベクトルである。なお、部分集合は、共通の特徴の集合をK個に分割したものである。この場合、各ベクトルの次元数はD=D1D2...DDKとなる。また、この場合、パラメタ統合部190では、式51のみを用いる。補助モデル用パラメタ推定部140では、式24、26、28、30、32または34で表される正則化項付き経験一般化相対エントロピーUΘ|DUの勾配を用いて、正則化項付き経験一般化相対エントロピーUΘ|DUを最小化する補助モデル用パラメタ集合の集合を推定しているが、勾配を用いない他の方法を用いて、推定してもよい。同様に基本モデル用パラメタ推定部160では、式41で表される正則化項付き経験リスク関数Lλ|Θ,DLの勾配を用いて、正則化項付き経験リスク関数Lλ|Θ,DLを最小化する基本モデル用パラメタ集合を推定しているが、勾配を用いない他の方法を用いて、推定してもよい。"