(57)【要約】最大エントロピー・モデリングのために特徴を選択する方法であって、初期化段階期間に全ての候補特徴の利得が決定され、各特徴選択段階期間に最上位の特徴のみの利得が決定される方法が提供される。決定された利得に基づいて、順位付けリストにおいて候補特徴がランク付けられる。順序付けリストにおいて、最高の利得を有する最上位の特徴が選択され、該選択された最上位の特徴を用いてモデルが調整される。【特許請求の範囲】
【請求項１】
最大エントロピー・モデリングのために特徴を選択する方法であって、
初期化段階期間に候補特徴に対する利得を決定し、各特徴選択段階期間に最上位の特徴のみに対する利得を決定するステップと、
前記決定された利得に基づいて、前記候補特徴を、順序付きリストにおいてランク付けするステップと、
前記順序付きリストにおいて、最高の利得を有する最上位の特徴を選択するステップと、
前記選択された最上位の特徴を利用してモデルを調整するステップと、
を含む方法。
【請求項２】
請求項１記載の方法であって、以前の特徴選択段階で決定された前記候補特徴の利得が、現在の特徴選択段階において、残りの候補特徴の上限利得として再利用される方法。
【請求項３】
請求項２記載の方法であって、前記最上位の特徴は、該特徴の決定された利得が前記残りの候補特徴の前記上限利得より大きい場合に選択される方法。
【請求項４】
請求項１記載の方法であって、前記最上位の特徴は、現在の調整されたモデルを用いて決定された前記最上位の特徴の利得が、以前に調整されたモデルを用いて決定された残りの候補特徴の前記利得より大きい場合に選択される方法。
【請求項５】
請求項１記載の方法であって、各特徴選択段階において、所定数の最上位の特徴に対する利得が決定される方法。
【請求項６】
請求項１記載の方法であって、更に、所定の特徴選択段階において、全ての残りの候補特徴の利得を再評価するステップを含む方法。
【請求項７】
請求項１記載の方法であって、選択された一組の特徴を満たす非正規化条件付確率のみが修正される方法。
【請求項８】
最大エントロピー・モデリングのための特徴を選択する方法であって、
（ａ）一様分布を用いて候補特徴の利得を計算するステップと、
（ｂ）順序付きリストにおいて、前記計算された利得に基づいて候補特徴を順序付けるステップと、
（ｃ）前記順序付きリストにおいて、最高の利得を有する最上位の特徴を選択するステップと、
（ｄ）前記選択された最上位の特徴を利用して、モデルを調整するステップと、
（ｅ）前記順序付きリストにおいて次にランクされた特徴が最上位の特徴となるよう、前記順序付きリストから前記最上位の特徴を取り除くステップと、
（ｆ）前記調整されたモデルを用いて、前記最上位の特徴の利得を計算するステップと、
（ｇ）前記最上位の特徴の前記利得と、前記順序付きリストにおいて次にランクされた特徴の利得とを比較するステップと、
（ｈ）前記最上位の特徴の前記利得が、前記次にランクされた特徴の前記利得より小さい場合に、前記次にランクされた特徴が最上位の特徴となって前記順序付けリストの順序が維持されるよう、前記順序付けリストにおいて前記最上位の特徴を位置付け直し、ステップ（ｆ）から（ｇ）を繰り返すステップと、
（ｉ）選択された特徴の品質の１つが所定値を超え、最後に選択された特徴の利得が所定値を下回るまで、ステップ（ｃ）から（ｈ）を繰り返すステップと、
を備える方法。
【請求項９】
請求項８記載の方法であって、前記最上位の特徴の利得を計算する前記ステップ（ｆ）が、所定数の最上位の特徴の利得を計算するステップを含む方法。
【請求項１０】
請求項８記載の方法であって、残りの全ての特徴の利得が、所定の特徴選択において再評価される方法。
【請求項１１】
請求項７記載の方法であって、各特徴選択段階において残っている前記候補特徴の大部分の利得が、以前の特徴選択段階で調整されたモデルに基づいて再利用される方法。
【請求項１２】
最大エントロピー・モデリングを実行する処理装置システムにおいて、データのコーパスから得られた１つ又はそれ以上の候補特徴が、言語行動を予測するモデルに組み込まれるシステムにおいて、
初期化段階期間に候補特徴に対する利得を決定し、特徴選択段階期間に最上位の特徴のみに対する利得を決定する利得計算装置と、
前記決定された利得に基づいて特徴をランク付けする特徴ランク付け装置と、
最高の利得を有する特徴を選択する特徴選択装置と、
前記選択された特徴を用いてモデルを調整するモデル調整装置と、
を備える処理装置システム。
【請求項１３】
請求項１２記載の処理装置であって、特徴ランク付け装置が、以前の特徴選択段階において以前に調整されたモデルを用いて決定された残りの候補特徴の利得を再利用するよう構成される装置。
【請求項１４】
請求項１２記載の処理装置であって、前記利得計算装置が、対応する利得が現在のモデルに基づいて残りの候補特徴の利得よりも大きい最上位の特徴が見出されるまで、最高から最低まで昇順に最上位の特徴に対する利得を決定するよう構成される装置。
【請求項１５】
請求項１２記載の処理装置であって、前記利得計算装置が、各特徴選択段階において、所定数の最上位の特徴に対する利得を決定するよう構成される方法。
【請求項１６】
請求項１５記載の処理装置であって、最上位の特徴の前記所定数が５００である装置。
【請求項１７】
請求項１１記載の処理装置であって、所定の特徴選択段階において残っている全ての候補特徴の利得が再評価される装置。
【請求項１８】
候補特徴の順序付けリストを形成するために、一様分布において計算された利得に基づいて、候補特徴を順序付けるステップと、
次の段階のためのモデルを形成するために、最高の利得を有する最上位の特徴を選択するステップと、
前記候補特徴の前記順位付けリストから、最上位の特徴を取り除くステップと、
以前の段階で形成されたモデルに基づいて、前記最上位の特徴の利得を計算するステップと、
前記最上位の特徴の利得と、前記順位付けリストの残りの候補特徴の利得とを比較するステップと、
前記最上位の特徴の利得が、前記順位付けリストにおいて次にランクされた特徴の利得より大きい場合に、前記最上位の特徴を前記モデルに含めるステップと、
前記最上位の特徴の前記利得が、前記順序付けリストの前記次にランクされた特徴の利得のうちの任意のものより小さい場合に、前記次にランクされた特徴が最上位の特徴となって前記順序付けリストの順序が維持されるよう、前記最上位の特徴を前記順位付けリストに挿入するステップと、
前記最上位の特徴の利得が、順序付けられた候補特徴の利得を上回るまで、前記最上位の特徴の利得を計算するステップ、及び前記最上位の特徴の利得と次にランクされた特徴の利得とを比較するステップを繰り返すステップと、
選択された特徴の品質の１つが所定値に達し、最後の特徴の利得が所定値に達する場合に、該方法を終了するステップと、
を実行するために、プロセッサによって実行可能な命令セットを含む記憶媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
発明の分野
本発明は、条件付最大エントロピー・モデリングのために高品質な特徴を効率的に選択する方法及びシステムに関する。
【０００２】
発明の背景
最大エントロピー（ＭＥ）・モデリングは、それぞれが何らかの言語的な統計事象を符号化する様々な情報特性を、データのコーパスから条件付モデルの共通フレームワークへと組み込むことにより、言語行動を予測するための言語モデリング及び自然言語処理に適用され得る一般的な統計的モデリング・パラダイムである。しかしながら、そのようなモデリングは膨大な処理を要し得る。
【０００３】
ＭＥモデリングは、２つの主要な作業に分けられ得る。即ち、モデルに含まれるべき所望の特徴のサブセットを特徴事象空間から選択する特徴選択処理、及び、選択された個々の特徴に対する重み付け係数を予測するパラメータ予測処理である。しかしながら、多くの適用において、特定の作業に対してどの特徴が重要であるかは、明らかではないかもしれない。そのため、重要な特徴を見失わないことを保証するためには、大きな特徴事象空間が必要とされ得る。しかし、全て又はほとんど全ての特徴を含むことは、データの過剰適合を引き起こし、予測処理を遅くして、結果としてのモデルを、資源の制約のあるアプリケーションにとって大き過ぎるものにしてしまう可能性がある。
【０００４】
ＭＥモデリングにおける多くの努力が、パラメータ予測に集中してきたこと、特徴選択には、より少ない努力しか為されてこなかったことが信じられている。なぜなら、パラメータ予測アルゴリズムが十分に高速である場合、特定の作業にとって、特徴選択は必要とされない可能性があるからである。しかし、特徴事象空間が必然的に大きく複雑である場合、確率計算を高速化し、実行時のメモリ要求を低減し、訓練期間のモデル選択サイクルを短縮するために、少なくとも何らかの形態の特徴選択を実行することが望まれ得る。不運なことに、調べられる特徴事象空間が大きい場合、特徴選択そのものが難しく、遅くなり得る。全ての可能性のある特徴サブセットを選択するための母集団は、はなはだしく大きくなり可能性があるからである。具体的に、全ての可能性のある特徴サブセットの母集団は、２｜Ω｜のサイズを持ち得る。ここで、｜Ω｜は特徴事象空間のサイズである。
【０００５】
特徴選択作業を促進及び／又は最小化するために、様々な技術が適用され得る。Ronald Rosenfeldによる１９９４年４月カーネギーメロン大学博士論文「適応的統計言語モデリング：最大エントロピー法」（「Rosenfeld（１９９４）」）、Adwait Ratnaparkhiによる１９９８年のペンシルヴァニア大学博士論文「自然言語多義性解決のための最大エントロピー・モデル」（「Ratnaparkhi（１９９８）」）、J. Reynar及びA． RatnaparkhiによるワシントンD.C.における１９９７年の応用自然言語処理に関する第５会議の議事録１６〜１９頁の「文境界識別のための最大エントロピー手法」（「Reynar及びRatnaparkhi（１９９７）」）、Rob Koelingによるポルトガル国リスボンのＣｏＮＬＬ−２０００及びＬＬＬ−２０００の議事録１３９〜１４１頁の「最大エントロピー・モデルによるチャンキング」（「Koeling（２０００）」）に論じられるように、コーパスにおいて所定のカットオフ閾値より多く発生する特徴のみが選択される単純なカウントカットオフ技術が利用され得る。Ratnaparkhi（１９９８）に論じられるように、カットオフ技術は、高速且つ実現し易いものであり得るが、多くの重複した特徴を含み得る。２００１年のAdam L. Berger、Stephen A. Della Pietra及びVincent J. Della Pietraによるコンピュータ的言語学２２（１）の３９〜７１頁の「自然言語処理に対する最大エントロピー手法」（「Bergerら（１９９６）」）で参照される、増分特徴選択（ＩＦＳ）アルゴリズム呼ばれる一層洗練されたアルゴリズムは、各選択段階において１つだけの特徴が追加されること、及び、予測パラメータ値が前段階で選択された特徴について維持されることを必要とする。これについて、ＩＦＳアルゴリズムは、各選択段階対して、全ての候補特徴に対する特徴利得（特徴の情報内容の測度）を計算し、最高の利得を有する特徴を選択し、選択された特徴によってモデルを調整するために利用され得る。
【０００６】
単純なカウントカットオフ技術と比較して、ＩＦＳアルゴリズムは、選択された特徴セットにおける重複を排除し得るが、複雑な作業にとっては、アルゴリズムの速度が問題になり得る。ＩＦＳアルゴリズムの欠点を認識した上で、Adam L. Berger及びHarry Printzによる１９９８年のスペイン国グラナダにおける自然言語処理の経験的方法に関する第３回会議の議事録「最大エントロピーのための条件比較／最小相違特徴選択」（「Berger及びPrintz（１９９８）」）は、選択される特徴の品質にあまり影響を与えずにｋ個の特徴を同時に選択するためのΦ直交条件を提案した。この技法は、例えば単語間のリンク特徴のような特定の特徴セットに適用可能であるが、Φ直交条件は、特徴サブセットに品詞（ＰＯＳ）タグが優勢に存在する場合に有効ではない。
【０００７】
Stanley Chen及びRonald Rosenfeldは、アリゾナ州フェニックスで行われたＩＣＡＳＳＰ−１９９９の議事録の「文全体最大エントロピー言語モデルにおける効率的サンプリング及び特徴選択」（「Chen及びRosenfeld（１９９９）」）において、特徴がＭＥモデルに含まれるべきかを判定するためにｘ２乗検定を利用する特徴選択技術を実験した。ｘ２乗検定は、以前の分布からのカウント、及び実際の訓練データからのカウントを用いて計算される。それは、幾つかの言語モデリング作業にとっては、十分であり得る。しかし、ｘ２乗検定スコアと、ＭＥモデルを最適化するために必要とされ得る見込み利得との関係は、存在しないかもしれない。
【０００８】
要するに、既存の特徴選択アルゴリズムは、低速で、最適よりも低い品質で特徴を選択し、少なからぬ量の手作業を含み、又は、低い低減率を有し得る。従って、既存の特徴選択アルゴリズムを利用する人は、発見されていない重要な特徴を見過ごす可能性のある、一層小さな制約された特徴事象空間を利用するか、一層大きなモデルを構築して、システムメモリ要件に特別な要求を課す可能性がある。
【０００９】
発明の概要
本発明は、言語理解及びバイオインフォマティクスから株式市場予測までの範囲に渡る、統計モデリング及び直線回帰の分野で適用され得る最大エントロピー（ＭＥ）モデリングのために高品質な特徴を選択する高速な方法を提供することを意図する。ここで、本発明の高速特徴選択法は、簡潔で高品質且つ強固なモデルを構築し、実行可能な多くの以前は実行不可能であったタスクを実行し得る。
【００１０】
本発明の例としての特徴選択方法によれば、各選択段階において全ての候補特徴に対するおよその特徴利得を計算するという、大きな特徴事象空間を必要とし、適用に時間がかかり得る作業の代わりに、以前の特徴選択段階から得られたモデルに基づいて、最上位の特徴のおよその利得のみを計算する。このため、例としての特徴選択方法は、選択的利得計算（ＳＧＣ）方法と呼ばれ、選択される特徴の品質を犠牲にすることなく、より高速な特徴選択を提供し得る。例えば、例としてのＳＧＣ特徴選択方法は、既存の増分特徴選択（ＩＦＳ）アルゴリズムより数百から数千倍高速に実行され得る。
【００１１】
１つの例としての実施の形態によれば、ＳＧＣ特徴選択法は、「先読み」機能を備え得る。
もう１つの例としての実施の形態によれば、ＳＧＣ特徴選択法は、予め特定された間隔における全ての特徴の特徴利得の再評価を含み得る。
【００１２】
例としての選択的利得計算（ＳＧＣ）特徴選択法が、選択された特徴の品質を同じに保ちながら特徴選択処理を著しく高速化することができることを示すために、言語データコンソーシアムによって提供されるＰｅｎｎＴｒｅｅｂａｎｋから得られたウォール・ストリート・ジャーナルの経済紙テキストを用いた実験が行われた。
【００１３】
もう１つの例としての実施の形態によれば、高速選択方法は、条件付最大エントロピー・モデリングのための特徴を選択し得る。この場合、各選択段階において全ての候補特徴に対するおよその利得を決定する代わりに、例としての高速選択方法は、以前の段階から得られたモデルに基づいて、最上位の特徴のみのおよその利得を決定する。例としての高速選択方法は、また、選択された特徴の品質を更に確かにするための先読み機能を備える。サイズＦの特徴空間がある場合、例としての高速選択方法は、各選択段階において全ての候補特徴に対するおよその利得を決定する手法より、Ｏ（Ｆ）だけ大きな空間を利用する。
【００１４】
本発明の例としての方法は、最大エントロピー・モデリングのために特徴を選択するものであり、該方法において、初期化段階期間に候補特徴に対する利得が決定され、各特徴選択段階期間に最上位の特徴のみに対する利得が決定される。候補特徴は、順序付けリストにおいて、決定された利得に基づいてランク付けられ、順位付けリストにおいて最高の利得を備える最上位の特徴が選択され、選択された最上位の特徴を用いてモデルが調整される。
【００１５】
本発明のもう１つの例としての方法は、最大エントロピー・モデリングのために特徴を選択するものであり、該方法において、以前の特徴選択段階で決定された候補特徴の利得が、現在の特徴選択段階において、残りの候補特徴の上限利得として再利用される。
【００１６】
本発明の更にもう１つの例としての方法は、最大エントロピー・モデリングのために特徴を選択するものであり、該方法において、特徴の決定された利得が残りの候補特徴の上限利得より大きい場合に、最上位の特徴が選択される。
【００１７】
本発明の更にもう１つの例としての方法は、最大エントロピー・モデリングのために特徴を選択するものであり、該方法において、現在の調整されたモデルを用いて決定された最上位の特徴の利得が、以前に調整されたモデルを用いて決定された残りの候補特徴の利得より大きい場合に、最上位の特徴が選択される。
【００１８】
本発明の更にもう１つの例としての方法は、最大エントロピー・モデリングのために特徴を選択するものであり、該方法において、各特徴選択段階において、所定数の最上位の特徴の利得が決定される。
【００１９】
本発明の更にもう１つの例としての方法は、最大エントロピー・モデリングのために特徴を選択するものであり、該方法において、全ての残りの候補特徴の利得が、所定の特徴選択段階において再評価される。
【００２０】
本発明の更にもう１つの例としての方法は、最大エントロピー・モデリングのために特徴を選択するものであり、該方法において、選択された一組の特徴を満たす非正規化条件付確率のみが修正される。
【００２１】
本発明の更にもう１つの方法は、最大エントロピー・モデリングのために特徴を選択するものであり、該方法において、一様分布を用いて候補特徴の利得が計算され、計算された利得に基づいて順序付きリストにおいて候補特徴が順序付けられ、順序付きリストにおいて最高の利得を有する最上位の特徴が選択され、選択された最上位の特徴を利用してモデルが調整され、順序付きリストにおいて次にランクされた特徴が最上位の特徴となるよう、順序付きリストから最上位の特徴が取り除かれ、調整されたモデルを用いて最上位の特徴の利得が計算され、最上位の特徴の利得が、順序付きリストにおいて次にランクされた特徴の利得と比較される。最上位の特徴の利得が、次にランクされた特徴の利得より小さい場合に、次にランクされた特徴が最上位の特徴となって順序付けリストの順序が維持されるよう、順序付けリストにおいて最上位の特徴が位置付け直され、最上位の特徴の利得を計算するステップと、最上位の特徴の利得を次にランクされた特徴の利得と比較するステップとが繰り返される。選択された特徴の品質が所定値を超えるまで、又は、最後に選択された特徴の利得が所定値を下回るまで、初期化以外の全てのステップが繰り返される。
【００２２】
本発明の更に他の方法は、最大エントロピー・モデリングのために特徴を選択するものであり、該方法において、最上位の特徴の利得を計算するステップは、所定数の最上位の特徴の利得を計算するステップを含む。
【００２３】
本発明の更に他の方法は、最大エントロピー・モデリングのために特徴を選択するものであり、該方法において、所定の特徴選択における残りの全ての特徴の利得が再評価される。
【００２４】
本発明の更に他の方法は、最大エントロピー・モデリングのために特徴を選択するものであり、該方法において、各特徴選択段階において残っている候補特徴の大部分の利得が、以前の特徴選択段階で調整されたモデルに基づいて再利用される。
【００２５】
本発明の更にもう１つの例としての実施の形態は、最大エントロピー・モデリングを実行する処理装置システムであって、データのコーパスから得られた１つ又はそれ以上の候補特徴が、言語行動を予測するモデルに組み込まれるシステムにおいて、初期化段階期間に候補特徴に対する利得を決定し、特徴選択段階期間に最上位の特徴のみに対する利得を計算する利得計算装置と、決定された利得に基づいて特徴をランク付けする特徴ランク付け装置と、最高の利得を有する特徴を選択する特徴選択装置と、選択された特徴を用いてモデルを調整するモデル調整装置とを備えるシステムを提供する。
【００２６】
本発明の更にもう１つの例としての実施の形態は、最大エントロピー・モデリングを実行するための処理装置システムであって、特徴ランク付け装置が、以前に調整されたモデルを用いて以前の特徴選択段階において決定された残りの候補特徴の利得を再利用するよう構成されるシステムを提供する。
【００２７】
本発明の更にもう１つの例としての実施の形態は、最大エントロピー・モデリングを実行するための処理装置システムであって、利得計算装置が、現在のモデルに基づく対応する利得が残りの候補特徴の利得よりも大きい最上位の特徴が見出されるまで、最高から最低まで昇順に最上位の特徴に対する利得を決定するよう構成されるシステムを提供する。
【００２８】
本発明の更にもう１つの例としての実施の形態は、最大エントロピー・モデリングを実行するための処理装置システムであって、利得計算装置が、各特徴選択段階において、所定数の最上位の特徴に対する利得を決定するよう構成されるシステムを提供する。
【００２９】
本発明の更にもう１つの例としての実施の形態は、最大エントロピー・モデリングを実行するための処理装置システムであって、最上位の特徴の所定数が５００であるシステムを提供する。
【００３０】
本発明の更にもう１つの例としての実施の形態は、最大エントロピー・モデリングを実行するための処理装置システムであって、所定の特徴選択段階において残っている全ての候補特徴の利得が再評価されるシステムを提供する。
【００３１】
本発明の更にもう１つの例としての実施の形態は、候補特徴の順序付けリストを形成するために、一様分布において計算された利得に基づいて候補特徴を順序付けるステップと、次の段階のためのモデルを形成するために、最高の利得を有する最上位の特徴を選択するステップと、候補特徴の順位付けリストから最上位の特徴を取り除くステップと、以前の段階で形成されたモデルに基づいて最上位の特徴の利得を計算するステップと、最上位の特徴の利得と、順位付けリストの残りの候補特徴の利得とを比較するステップと、最上位の特徴の利得が順位付けリストにおいて次にランク付けられた特徴の利得より大きい場合に、最上位の特徴をモデルに含めるステップと、最上位の特徴の利得が順序付けリストの次にランクされた特徴の利得のうちの任意のものより小さい場合に、次にランクされた特徴が最上位の特徴となって順序付けリストの順序が維持されるよう、最上位の特徴を順位付けリストに挿入するステップと、最上位の特徴の利得が順序付けられた候補特徴の利得を上回るまで、最上位の特徴の利得を計算するステップ、及び最上位の特徴の利得と次にランクされた特徴の利得とを比較するステップを繰り返すステップと、選択された特徴の品質の１つが所定値に達し、最後の特徴の利得が所定値に達する場合に、該方法を終了するステップと、を実行するためにプロセッサによって実行可能な命令セットを有する記憶媒体を提供する。
【００３２】
詳細な説明
図１は、特徴選択を実行するために選択的利得計算（ＳＧＣ）方法を利用する例としてのエントロピー・モデリング・システム１００を示す。選択的利得計算（ＳＧＣ）法では、言語行動を予測するために新しいモデル１０４を生成する処理装置１１０により、１つ又はそれ以上の候補特徴１０３がデータのコーパス１０２から取り出されて、基礎モデル１０１に組み込まれる。データのコーパス１０２は、例えば、言語データコンソーシアムによって提供されるＰｅｎｎＴｒｅｅｂａｎｋからのウォール・ストリート・ジャーナルの経済紙テキストを含むことができ、基礎モデル１０１は、例えば、一様分布であり得る。
【００３３】
例としての処理装置１１０は、初期化段階期間に全ての候補特徴１０３の利得を決定又は計算し、各特徴選択段階期間に最上位の特徴のみに対する利得を計算する利得計算装置１１１と、順序付きリスト内の特徴をランク付ける特徴ランク付け装置１１２と、順序付きリストにおいて最高の利得を有する特徴を選択する特徴選択装置１１３と、選択された特徴を用いてモデルを調整するモデル調整装置１１４と、本明細書に記載された方法及び計算を実行するプロセッサ１１５と、データを記憶するメモリ１１６と、例としてのエントロピー・モデリング・システム１００と相互作用するためのインターフェース１１７又は他の適切なグラフィカル・インターフェース（ＧＵＩ）とを含む。
【００３４】
図２は、特徴を選択するための増分特徴選択（ＩＦＳ）手法を反映する擬似コードの例であり、Ｓは選択された特徴の集合を表し、Ｉは訓練インスタンスの数を表し、Ｙは出力クラスの数を表し、Ｆは候補特徴の数又は候補特徴集合の大きさを表す。ＩＦＳ擬似コード例は、以下のように記載され得る。条件付ＭＥモデルは、以下の形式を取ると想定する。即ち、
【００３５】
【数１】
2007529047.tif 000002
である。ただし、ｆｊ（ｘ，ｙ）は、特定の言語事象（ｘ、ｙ）を表す特徴関数（又は短縮して特徴）であり、λｊは対応する重み付けであって、特徴ｆｊがモデルにとっていかに重要かを示すものであり、Ｚ（ｘ）は正規化係数であり、ｐ（ｙ｜ｘ）はエントロピーを最大化させる結果としての条件付確率分布、即ち文脈情報ｘが存在する場合にモデルが出力ｙを割り当てる確率である。
【００３６】
ＩＦＳ手法を反映する例としての実現形態は、指数モデルにおける特徴ｆの追加が、関連する重み付けαのみに影響し、他の特徴と関連するλ値を変わらないままにすると想定することにより、近似値を作成し得る。この場合、図２のＩＦＳ擬似コード例は、２００２年にペンシルヴァニア州フィラデルフィアにおいてコンピュータ的言語学協会によって出版されたJoshua Goodmanによる「順次条件付汎用反復スケーリング」（「Goodman（２００２）」）において参照された、条件付ＭＥモデリングにおいてパラメータを最適化するための技術を反映する。より詳細には、配列ｚは、正規化係数を記憶するために利用され、配列ｓｕｍは、全ての非正規化条件付確率ｓｕｍ[ｉ，ｙ]のために利用される。従って、
【００３７】
【数２】
2007529047.tif 000003
を満たすｓｕｍ[ｉ，ｙ]を修正し、それらの対応する正規化係数ｚ[ｉ]を変更するだけでよい。このＩＦＳ擬似コード例の様々な値は、以下のように計算又は決定され得る。即ち、
【００３８】
【数３】
2007529047.tif 000004
である。次に、モデルは、ｓｕｍ（ｙ｜ｘ）及びＺ（ｘ）によって以下のように表され得る。即ち、
【００３９】
【数４】
2007529047.tif 000005
である。ただし、ｓｕｍ（ｙ｜ｘｉ）及びＺ（ｘｉ）は、それぞれ図１のｓｕｍ[ｉ,ｙ]及びｚ[ｉ]に対応する。
【００４０】
選択された特徴の集合がＳであり、特徴ｆが現在考慮されていると想定すると、各選択段階において、対数尤度の利得を最大化する特徴ｆを選択する試みがなされ、ｆの重み付け係数α及び利得が以下のステップで求められる。即ち、モデルの対数尤度は、
【００４１】
【数５】
2007529047.tif 000006
であり、特徴ｆの経験的期待値は、
【００４２】
【数６】
2007529047.tif 000007
になる。
【００４３】
Bergerら（１９９６）において参照される近似値推定を用いると、モデルの非正規化要素及び正規化係数は、以下の再帰形を有し得る。即ち、
【００４４】
【数７】
2007529047.tif 000008
である。
【００４５】
対数尤度の近似利得は、以下のように計算又は決定される。即ち、
【００４６】
【数８】
2007529047.tif 000009
である。
【００４７】
最大化近似利得及びそれに対応するαは、以下のように表される。即ち、
【００４８】
【数９】
2007529047.tif 000010
である。
【００４９】
ＩＦＳ手法を反映する上記の例としての実現形態は、非効率的であり得る。なぜなら、１つが選択される前に全ての候補特徴が考慮され、各選択段階において全ての特徴に対する利得が再計算又は再決定されるからである。更に、例えばニュートン法などの反復根探索技法を用いてパラメータを計算することは、非効率であり得る。従って、選択処理全体のための総計算数は、望ましくないほどに数になり得る。
【００５０】
図３は、ＩＦＳ手法を反映する図２の例としての擬似コードの実現形態と比べてより高速な特徴選択を提供し得る、ＭＥモデリングのための例としての選択的利得計算（ＳＧＣ）方法の擬似コードを示す。例としてのＳＧＣ特徴選択方法を、以下に説明する。
【００５１】
ｇ（ｊ、ｋ）は、選択段階ｋにおける能動的モデルへの特徴ｆｊの追加による利得を表す。実験において、Δ（即ち、段階ｋ以降の追加の段階数）が大きい場合でも、たいていのｊについて、ｇ（ｊ、ｋ＋Δ）―ｇ（ｊ、ｋ）は、負の数又は最大でも非常に小さい正の数であることが見出され得る。従って、ｇ（ｊ、ｋ）は、ｇ（ｊ、ｋ＋Δ）の上限を近似するために利用され得る。
【００５２】
ここで、モデルに新しい特徴が追加される場合、追加の前と後で、他の特徴に対する利得はあまり変わらないかもしれない。変化がある場合、その実際の量は、最上位の特徴から最下位の特徴までの異なる特徴間の実質的に狭い範囲内に限られる。従って、利得は、計算されて、新しいモデルに基づく対応する利得が残りの特徴の利得より大きくなる特徴に到達するまで、最上位の特徴から下方へと比較されさえすればよい。わずかな例外を除き、残りの特徴の大半の利得は、以前のモデルに基づいて再利用され得る。
【００５３】
ＩＦＳ手法を反映する図２の例としての擬似コード実現形態と同様に、特徴ｆの追加は、その重み付け係数αのみに影響すると想定され得る。初期化段階では、前述の通り一様分布が想定されるため、α（ｊ、０）及びｇ（ｊ、０）に対する閉形式公式が、以下のように求められ得る。即ち、
【００５４】
【数１０】
2007529047.tif 000011
であるとき、
【００５５】
【数１１】
2007529047.tif 000012
である。ただし、
【００５６】
【数１２】
2007529047.tif 000013
は空集合を示し、
【００５７】
【数１３】
2007529047.tif 000014
は一様分布を示す。利得を計算又は決定し、特徴を選択する他のステップが、擬似コードとして、図３に提供される。少数の最上位の特徴に対する利得のみが計算されるため、この特徴選択方法は、選択的利得計算（ＳＧＣ）方法と呼ばれる。
【００５８】
例としてのＳＧＣ特徴選択法において、配列ｇは、記録された利得及びそれらの対応する特徴指標を保持するために利用される。実際には、配列の順位を維持するためにバイナリ検索木が利用され得る。
【００５９】
ＩＦＳ手法を反映する図２の例としての擬似コード実現形態と違い、図３の例としてのＳＧＣ特徴選択法は、全ての段階において、能動的モデルについて全ての特徴を評価することはしない（１つの段階は、１つの特徴の選択に対応する）。最初に、一様分布を用いて計算された候補特徴の利得に基づいて、特徴候補が順序付けられる。最高の利得を有する特徴が選択され、次の段階のためのモデルを形成する。次の段階において、順序付きリストにおける最上位の特徴の利得が、前の段階で形成されたばかりのモデルに基づいて計算される。この利得は、リストの残りの特徴の利得と比較される。この新しく計算された利得が依然として最高である場合、次の段階のモデルを形成するために、この特徴が追加される。利得が最高ではない場合、利得は、順序が維持されるように、順序付きリストに挿入される。この場合、順序付きリストにおいて次に最上位にランクされた特徴の利得が、現段階のモデルを用いて再計算される。
【００６０】
この処理は、現在のモデルで計算された最上位の特徴の利得が、順序付きリストにおいて依然として最高の利得であるまで続けられ得る。その後、次の段階のためのモデルが、この新しく選択された特徴を追加して作成される。全体としての特徴選択処理は、選択された特徴の数が入力における所定値に達した場合か、利得が小さ過ぎてモデルにとって有用ではなくなった場合に停止する。
【００６１】
ＳＧＣ特徴選択法の第１の例としての実施の形態に加えて、各段階において、選択された特徴
【００６２】
【数１４】
2007529047.tif 000015
が、所定の先読み距離内において本当に最高の利得を有する特徴であることを保証するために、順序付きリストの（ステップ２で得られた）特徴
【００６３】
【数１５】
2007529047.tif 000016
の直後に列挙された所定の数の特徴に対して、現在のモデルに基づいて、追加の利得が再計算され得る。この例としての実施の形態は、ＳＧＣ特徴選択方法の先読み版と呼ばれ得る。
【００６４】
図４〜７は、５つの候補特徴ｆ１、ｆ２、ｆ３、ｆ４、ｆ５を含む例としての特徴事象空間に対する、特徴選択の初期化から段階ｋ＝０、１及び２の、ＩＦＳ特徴選択法及びＳＧＣ特徴選択法の「ステップごとの」比較を提供する。ただし、ｇｊ，ｋは段階ｋにおける特徴ｆｊの利得を表し、Ｍｋは段階ｋにおいて最高の利得を有する特徴の追加に起因するモデルを表し、
【００６５】
【数１６】
2007529047.tif 000017
は一様分布を表す。特に、図４は、ＩＦＳ手法又はＳＧＣ方法に従う例としての初期化ステップを示し、図５Ａ、６Ａ及び７Ａは、選択段階ｋ＝０、１及び２のそれぞれにおける例としてのＩＦＳステップを示し、図５Ｂ、６Ｂ及び７Ｂは、選択段階ｋ＝０、１及び２のそれぞれにおける例としてのＳＧＣステップを示す。
【００６６】
図８は、図４、５Ａ、６Ａ及び７Ａにおける増分特徴選択（ＩＦＳ）手法に対する特徴選択ステップの例としてのフローチャート８００を示す。ステップＳ８１において、全ての候補特徴の利得が計算される。ステップＳ８２において、最高の利得を有する単一の特徴が選択される。ステップＳ８３において、選択されたばかりの特徴と、以前に選択された全ての特徴との重み付け係数が、変わらないままにされる。ステップＳ８４において、選択されたばかりの特徴を用いてモデルが調整される。ステップＳ８５において、選択された特徴が、候補特徴のリストから取り除かれる。
【００６７】
図９は、図１の例としての処理装置及びシステムにおいて利用され得る、例としてのフローチャート９００を示し、図４、５Ｂ、６Ｂ及び７Ｂに示される選択的利得計算（ＳＧＣ）方法の特徴選択ステップを説明する。ステップＳ９１において、システムは、全ての候補特徴の利得を計算する。ステップＳ９２において、システムは、候補特徴に対応する計算された利得に基づいて候補特徴を順序付け、例えば、最高の利得を有する特徴が最初にランクされ、最低の利得を有する特徴が最後にランクされる。順序付きリストは、例えば、例えば利得配列と呼ばれる配列に記憶され得る。ステップＳ９３において、システムは、最高の利得を有する最上位の特徴を選択する。ステップＳ９４において、システムは、選択されたばかりの特徴を用いてモデルを調整する。ステップＳ９５において、システムは、選択された特徴を、候補特徴の順序付きリストから除去する。ステップＳ９６において、システムは、候補特徴の順序付きリストの最上位の特徴の利得を計算する。ステップＳ９７において、システムは、最上位の特徴の利得を、候補特徴の順序付きリストにおいて次にランクされた特徴の利得と比較する。最上位の特徴の利得が、次にランクされた特徴の利得より大きい場合、ＳＧＣ法は、システムのステップＳ９３に進み、そうではない場合、即ち最上位の特徴の利得が次にランクされた特徴の利得より小さい場合に、ＳＧＣ法は、システムのステップＳ９８に進む。ステップＳ９８において、次にランクされた特徴が新たに最上位の特徴となってリストの適正な順位が保たれるよう、即ち、前の最上位の特徴が、順序付きリストにおいて、最近計算された利得に基づいて最高の位置から適正な位置へと移動するよう、順序付きリストにおいて最上位の特徴が位置付け直される。その後、ＳＧＣ法は、ステップＳ９６に戻り、候補特徴の順序付きリストにおいて新しく最上位にランクされた特徴の利得を計算する。
【００６８】
ＩＦＳ法と、本発明に係るＳＧＣ特徴選択法との性能を比較するための実験が実施された。
実験の第１のセットは、言語データコンソーシアムによって提供されたＰｅｎｎＴｒｅｅｂａｎｋから引き出されたデータセット｛（ｘ，ｙ）｝を利用する。ただし、ｘは、単語、品詞（ＰＯＳ）タグ、及び２つの隣接する部分からの文法関係タグ情報を含む１０次元ベクトルであり、ｙは、２つの部分間の文法関係タグである。文法関係タグの例には、右側部分又は左側部分を主要語とする、主語及び目的語が含まれる。様々な文法タグの総数、即ち、出力空間のサイズは、８６である。６００、０００個よりやや多い訓練インスタンスが、ＰｅｎｎＴｒｅｅｂａｎｋのセクション０２〜２２から得られたウォール・ストリート・ジャーナルの経済紙テキストのコーパスから生成され、試験コーパスがセクション２３から生成された。
【００６９】
実験において、特徴事象空間は、特徴テンプレートと呼ばれる、特定の次元のみを含むサブスペースに区切られる。１０次元空間において可能性のある全ての組み合わせを考慮するためには、２１０個の特徴テンプレートが必要とされ得る。比較を実行するため、言語知識を用いて怪しい部分空白がフィルター除去され、２４個の特徴テンプレートのみが実際に利用される。この数の特徴テンプレートで、１，９００，０００個の候補特徴が訓練データから取得され得る。ＩＦＳ手法を反映する例としての擬似コード実現形態について必要とされ得る実験を高速化するため、特徴空間を１９１，０９８個まで低減する５のカットオフが利用され得る。平均として、個々の候補特徴は４８５個のインスタンスをカバーし、それらは、全体としての訓練インスタンスのセットの０．０８３％を占め、以下の通りに計算される。即ち、
【００７０】
【数１７】
2007529047.tif 000018
である。
【００７１】
第１の実験は、ＩＦＳ手法を反映する例としての擬似コードの実現形態の速度と、例としてのＳＧＣ特徴選択方法の速度とを比較した。ＩＦＳ手法を反映する例としての擬似コードの実現形態が、全段階における全特徴の利得を計算すると仮定すると、ＩＦＳ手法を反映する例としての実現形態は、サイズＦの候補特徴セットからサイズＮの特徴サブセットを選択するためにＯ（ＮＦ）時間を必要とする。それに対して、例としてのＳＧＣ特徴選択方法は、本実験において大きな特徴空間から特徴を選択する際に、はるかに少ない特徴（例えば、各段階において平均で２４．１個だけの特徴）を考慮し得る。
【００７２】
図１０は、例としてのＳＧＣ特徴選択法、「５００」個の先読みを有する例としてのＳＧＣ特徴選択法、及びＩＦＳ手法を反映する例としての擬似コードの実現形態について、利得が計算される特徴の平均数を示す。平均特徴数は、初期化段階から現在の特徴選択時点までの間隔に渡って取得され、個々の選択段階に考慮される特徴数の揺らぎを平滑化することを意図する。「５００」個の先読みを有する例としてのＳＧＣ特徴選択法は、先読み機能を有さない例としてのＳＧＣ特徴選択法によって考慮される特徴を超えて、この実験では５００個である決まった数の追加の特徴を調べる。「５００」個の先読みを有する例としてのＳＧＣ特徴選択法は、線形に減少する数の特徴を選択する。選択された特徴は、再び考慮されることはないからである。図１０において、ＩＦＳ手法を反映する例としての擬似コードの実現形態は、１０００個の特徴が選択された後に停止する。全ての選択処理を完了するのは、このアルゴリズムにとって時間がかかり過ぎるからである。以下に説明する図１１において、同一の停止が発生する。「５００」個の先読みを有する例としてのＳＧＣ特徴選択法は、平均的に、ＩＦＳ手法を反映する例としての擬似コード実現形態より少ない特徴に対する利得を計算する。「５００」個の先読み機能を有しないＳＧＣ特徴選択法は、更に少ない特徴を計算する。
【００７３】
図１１は、例としてのＳＧＣ特徴選択法と、ＩＦＳ手法を反映する例としての擬似コードの実現形態とによって必要とされる時間量を比較する。２つの実験を同時実行するために、１．６ギガのデュアルＸｅｏｎＣＰＵと、１ギガ（ギガバイト）のメモリを有するＬｉｎｕｘ（登録商標）ワークステーションが利用された。通常共有されるコードの最初の部分を除いて、例としてのＳＧＣ特徴選択法の利用による高速化は、ＩＦＳ手法を反映する例としての実現形態より、選択される特徴の数に応じて、１００倍から１０００倍ほども高速である。
【００７４】
例としてのＳＧＣ特徴選択法で選択された特徴の品質を確認するために、４つの実験が実施された。第１の実験において、全ての特徴を利用して、条件付きＭＥモデルが構築された。第２の実験において、ＩＦＳ手法を反映する例としての擬似コード実現形態を利用して、１，０００個の特徴が選択された。第３の実験において、例としてのＳＧＣ特徴選択法が利用された。第４の実験において、「５００」個の先読みを有する例としてのＳＧＣ特徴選択法が利用された。第５の実験において、最上位のｎ個の最も頻出する特徴が、訓練データから取得された。ＰｅｎｎＴｒｅｅｂａｎｋのセクション２３のウォール・ストリート・ジャーナルのデータセットにおいて、適合率の割合が計算された。
【００７５】
図１２から明らかになるように、モデルが３０００個以上の選択される特徴を含む場合、ＳＧＣ特徴選択法の性能は、全特徴を含むモデルを著しく上回る。図の右側にある、全特徴を含むモデルの劣った性能は、データの過剰適用の問題のせいである可能性がある。更に、単一のカウントカットオフ・アルゴリズムは、１０，０００個以下の特徴を含む特徴サブセットが考慮される場合に、他の特徴選択アルゴリズムの性能を下回る。
【００７６】
適合率に関する結果を更に確認するため、ＢａｓｅＮＰ認識をタスクとするもう１つの実験が実施された。実験は、ウォール・ストリート・ジャーナルのテキストのセクション１５〜１８を訓練データとして利用し、セクション２０を試験データとして利用する。実験中に、９２．７５％／９３．２５％の適合率／再現率を得るために、ＳＧＣ特徴選択法を用いて、単一の特徴空間から１、１６０個の特徴が選択された。このタスクについて報告された最良のＭＥ研究は、５のカットオフにおいて９２．８４％／９３．１８％の適合率／再現率を有するKoeling（２００）を含み、２００３年に北京で出版されたコンピュータ研究開発ジャーナル４０（３）号４４０〜４４６頁のZhou Ya-qian、Guo Yi-kun、Huang Xuan-jing及びWu Li-deによる「最大エントロピーによる中国語及び英語のＢａｓｅＮＰ認識」（「Zhouら（２００３）」）は、７のカットオフにおいて９３．０４％／９３．３１％の性能を達成し、ＩＦＳ手法を反映する擬似コード実現形態を用いて６１５個の特徴について９２．４６％／９２．７４％の性能を達成したことが理解される。上記の実験では異なる特徴事象空間が利用されているため、結果を直接比較することができないかもしれないが、結果は、ＳＧＣ特徴選択法が高品質な特徴の選択に効果的であり、タスク実行において有効であり得ることを示す、これらの最良の数値に劣らないものと考えられ得る。
【図面の簡単な説明】
【００７７】
【図１】図１は、選択的利得計算（ＳＧＣ）方法を利用して特徴選択を実行する、例としての最大エントロピー・モデリング・システムを示す。
【図２】図２は、例としての増分特徴選択（ＩＦＳ）手法を反映する擬似コードを示す。
【図３】図３は、特徴選択のための例としての選択的利得計算（ＳＧＣ）方法を反映する擬似コードを示す。
【図４】図４は、ＩＦＳ手法又はＳＧＣ方法のいずれかに従う例としての初期化ステップを示す。
【図５Ａ】図５Ａは、特徴選択段階ｋ＝０に対する例としてのＩＦＳステップを示す。
【図５Ｂ】図５Ｂは、特徴選択段階ｋ＝０に対する例としてのＳＧＣステップを示す。
【図６Ａ】図６Ａは、特徴選択段階ｋ＝１に対する例としてのＩＦＳステップを示す。
【図６Ｂ】図６Ｂは、特徴選択段階ｋ＝１に対する例としてのＳＧＣステップを示す。
【図７Ａ】図７Ａは、特徴選択段階ｋ＝２に対する例としてのＩＦＳステップを示す。
【図７Ｂ】図７Ｂは、特徴選択段階ｋ＝２に対する例としてのＳＧＣステップを示す。
【図８】図８は、図４、５Ａ、６Ａ及び７Ａに示された増分特徴選択（ＩＦＳ）手法に対する例としての特徴選択ステップを記載するフローチャート８００を示す。
【図９】図９は、図４、５Ｂ、６Ｂ及び７Ｂに示された選択的特徴計算（ＳＧＣ）方法に対する例としての特徴選択ステップを記載するフローチャート９００を示す。
【図１０】図１０は、ＩＦＳ手法を反映する例としての実現形態によって考慮される特徴数と、例としてのＳＧＣ特徴選択方法によって考慮される特徴数と、先読みを有するＳＧＣ特徴選択方法によって考慮される特徴数とを比較する実験的又は経験的な結果を示す。
【図１１】図１１は、ＩＦＳ手法を反映する例としての実現形態によって利用される処理時間量と、例としてのＳＧＣ特徴選択方法によって利用される処理時間量とを比較する実験的又は経験的な結果を示す。
【図１２】図１２は、ＩＦＳ手法を反映する例としての実現形態、例としてのＳＧＣ特徴選択方法、例としての先読みを有するＳＧＣ選択方法、及び単純なカウントカットオフ・アルゴリズムの選択適合性を比較する実験的又は経験的な結果を示す。
【図１】
2007529047.tif 000019
【図２】
2007529047.tif 000020
【図３】
2007529047.tif 000021
【図４】
2007529047.tif 000022
【図５Ａ】
2007529047.tif 000023
【図５Ｂ】
2007529047.tif 000024
【図６Ａ】
2007529047.tif 000025
【図６Ｂ】
2007529047.tif 000026
【図７Ａ】
2007529047.tif 000027
【図７Ｂ】
2007529047.tif 000028
【図８】
2007529047.tif 000029
【図９】
2007529047.tif 000030
【図１０】
2007529047.tif 000031
【図１１】
2007529047.tif 000032
【図１２】
2007529047.tif 000033