(57)【要約】選択される特徴群の有用性と独立性の双方の観点から多項式時間で適正な特徴選択を行なう情報処理装置が開示されている。この情報処理装置は、特徴群に含まれる各特徴の有用性を評価する有用性評価手段と、前記特徴群に含まれる特徴間の独立性を評価する独立性評価手段と、前記有用性評価手段で計算された有用性尺度と前記独立性評価手段で計算された独立性尺度とを用いて定義された劣モジュラ性評価関数を最適化する一組の選択特徴群を決定する選択特徴群決定手段と、を備える。【選択図】  図１
2012111235.tif 000002
【特許請求の範囲】
【請求項１】
特徴群に含まれる各特徴の有用性尺度を算出することにより有用性を評価する有用性評価手段と、
前記特徴群に含まれる特徴間の独立性尺度を算出することにより独立性を評価する独立性評価手段と、
前記有用性評価手段で計算された有用性尺度と前記独立性評価手段で計算された独立性尺度とを用いて定義された劣モジュラ性評価関数が所定条件を満たすように一組の選択特徴群を決定する選択特徴群決定手段と、
を備えたことを特徴とする情報処理装置。
【請求項２】
前記選択特徴群決定手段は、
前記劣モジュラ性評価関数を最小化する一組の選択特徴群を決定することを特徴とする請求項１に記載の情報処理装置。
【請求項３】
前記特徴群に含まれる各特徴は、それぞれ複数のパラメータを含むことを特徴とする請求項１または２に記載の情報処理装置。
【請求項４】
前記選択特徴群決定手段は、一組の選択特徴群を決定するため、最大で２つの特徴を引数とする項からなる劣モジュラ性評価関数を最適化することを特徴とする請求項１、２または３に記載の情報処理装置。
【請求項５】
前記有用性評価手段は、２つ以上の特徴を引数とする有用性尺度を算出することを特徴とする請求項１乃至４の何れか１項に記載の情報処理装置。
【請求項６】
前記有用性評価手段は、フィッシャーの判別基準を用いて有用性尺度を算出することを特徴とする請求項１乃至５の何れか１項に記載の情報処理装置。
【請求項７】
前記独立性評価手段は、前記特徴群から抽出した２つの特徴から独立性尺度を算出することを特徴とする請求項１乃至６の何れか１項に記載の情報処理装置。
【請求項８】
前記選択特徴群決定手段は、前記有用性評価手段で算出された有用性尺度と、前記独立性評価手段で算出された独立性尺度とを含む評価関数を、グラフカットによって最適化することを特徴とする請求項１乃至７の何れか１項に記載の情報処理装置。
【請求項９】
特徴群に含まれる各特徴の有用性を評価する有用性評価ステップと、
前記特徴群に含まれる特徴間の独立性を評価する独立性評価ステップと、
前記有用性評価ステップで計算された有用性尺度と前記独立性評価ステップで計算された独立性尺度とを用いて定義された劣モジュラ性評価関数が所定条件を満たすように一組の選択特徴群を決定する選択特徴群決定ステップと、
を含むことを特徴とする情報処理方法。
【請求項１０】
特徴群に含まれる各特徴の有用性を評価する有用性評価ステップと、
前記特徴群に含まれる特徴間の独立性を評価する独立性評価ステップと、
前記有用性評価ステップで計算された有用性尺度と前記独立性評価ステップで計算された独立性尺度とを用いて定義された劣モジュラ性評価関数が所定条件を満たすように一組の選択特徴群を決定する選択特徴群決定ステップと、
をコンピュータに実行させる情報処理プログラムを格納したことを特徴とする記憶媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、パターン認識などに有効な特徴群を選択する技術に関する。
【背景技術】
【０００２】
学習・識別などの計算コストを軽減するため、入力された特徴群から、機械学習などに用いる一部の特徴群を選択する特徴選択技術の一種として、特徴の有用性に着目した技術が、特許文献１及び２に開示されている。しかし、特徴の全ての組み合わせを直接評価しているため、特徴群候補探索の計算コストが高く、多項式時間で適正な特徴選択を行なうことができないという問題がある。【０００３】
これに対し、特徴の有用性に加えて、特徴間の独立性（言い換えれば冗長性の低さ）を評価することにより効率的に特徴選択を行なう方法が非特許文献１、２、３に開示されている。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】ＷＯ２００７／０２６１３０
【特許文献２】特開２００８−０７１２１４号公報
【非特許文献】
【０００５】
【非特許文献１】L.Zhou,L.Wang,and C.Shen,"Feature Selection with Redundancy-Constrained Class Separability",IEEE Transaction on Neural Networks,Vol.21,No.5,pp.853-858,2010
【非特許文献２】S.Loscalzo,L.Yu,and C.Ding,"Consensus Group Stable Feature Selection",ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,pp.567-576,2009
【非特許文献３】H.Peng,F.Long,C.Ding,"Feature Selection Based on Mutual Information: Criteria of Max-Dependency,Max-Relevance,and Min-Redundancy",IEEE Transactions on Pattern Analysis and Machine Intelligence,Vol.27,no.8,pp.1226-1238,2005
【発明の概要】
【発明が解決しようとする課題】
【０００６】
しかしながら、非特許文献１および非特許文献２では、まず、入力の特徴群を特徴間の独立性に応じてクラスタリングし、次に、クラスタリング結果を用いた拘束条件下で特徴の有用性による特徴選択を行っている。つまり、有用性による最適化と独立性による最適化を別々に行っているため、有用性と独立性の双方の観点から真に適正な特徴選択が得られることを保証しないという問題がある。【０００７】
また、非特許文献３においては、有用性を考慮して１つずつ特徴を選択していく際に、他の特徴との独立性を考慮している。そのため、最終的な特徴の組み合わせが適正であることを保証しない。最初に選択した特徴が不適正なものであれば、最終的な特徴の組み合わせが適正なものにはなり得ない。【０００８】
本発明の目的は、上述の課題を解決する技術を提供することにある。
【課題を解決するための手段】
【０００９】
上記目的を達成するため、本発明に係る装置は、
特徴群に含まれる各特徴の有用性を評価する有用性評価手段と、
前記特徴群に含まれる特徴間の独立性を評価する独立性評価手段と、
前記有用性評価手段で計算された有用性尺度と前記独立性評価手段で計算された独立性尺度とを用いて定義された劣モジュラ性評価関数を最適化する一組の選択特徴群を決定する選択特徴群決定手段と、
を備えたことを特徴とする。【００１０】
上記目的を達成するため、本発明に係る方法は、
特徴群に含まれる各特徴の有用性を評価する有用性評価ステップと、
前記特徴群に含まれる特徴間の独立性を評価する独立性評価ステップと、
前記有用性評価ステップで計算された有用性尺度と前記独立性評価ステップで計算された独立性尺度とを用いて定義された劣モジュラ性評価関数を最適化する一組の選択特徴群を決定する選択特徴群決定ステップと、
を含むことを特徴とする。【００１１】
上記目的を達成するため、本発明に係る記憶媒体は、
特徴群に含まれる各特徴の有用性を評価する有用性評価ステップと、
前記特徴群に含まれる特徴間の独立性を評価する独立性評価ステップと、
前記有用性評価ステップで計算された有用性尺度と前記独立性評価ステップで計算された独立性尺度とを用いて定義された劣モジュラ性評価関数を最適化する一組の選択特徴群を決定する選択特徴群決定ステップと、
をコンピュータに実行させるプログラムを格納したことを特徴とする。
【発明の効果】
【００１２】
本発明によれば、選択される特徴群の有用性と独立性の双方の観点から多項式時間で適正な特徴選択を行なうことができる。
【図面の簡単な説明】
【００１３】
【図１】本発明の第１実施形態に係る情報処理装置の構成を示すブロック図である。
【図２】本発明の第２実施形態に係る情報処理装置の機能構成を示すブロック図である。
【図３】本発明の第２実施形態に係る情報処理装置のハードウェア構成を示すブロック図である。
【図４】本発明の第２実施形態に係る情報処理装置の処理の流れを示すフローチャートである。
【図５】本発明の第２実施形態に係る情報処理装置の処理の流れの具体例を示すフローチャートである。
【図６】本発明の第２実施形態に係る情報処理装置におけるグラフカットについて説明するための図である。
【図７】本発明の第２実施形態の前提技術について説明するための図である。
【図８】本発明の第２実施形態の前提技術について説明するための図である。
【図９】本発明の第２実施形態の前提技術について説明するための図である。
【図１０】本発明の第２実施形態の前提技術について説明するための図である。
【図１１】本発明の第２実施形態の前提技術について説明するための図である。
【図１２】本発明の第２実施形態の前提技術について説明するための図である。
【発明を実施するための形態】
【００１４】
以下に、図面を参照して、本発明の実施の形態について例示的に詳しく説明する。ただし、以下の実施の形態に記載されている構成要素はあくまで例示であり、本発明の技術範囲をそれらのみに限定する趣旨のものではない。
【００１５】
（第１実施形態）
本発明の第１実施形態としての情報処理装置１００について、図１を用いて説明する。情報処理装置１００は、有用性評価部１０１と独立性評価部１０２と選択特徴群決定部１０３とを備え、特徴群から、選択すべき複数の特徴を決定する装置である。
【００１６】
有用性評価部１０１は、特徴群に含まれる各特徴の有用性を評価する。また、独立性評価部１０２は、特徴群に含まれる特徴間の独立性を評価する。更に、選択特徴群決定部１０３は、有用性評価部１０１で計算された有用性尺度と独立性評価部１０２で計算された独立性尺度(redundancy、冗長性尺度とも言い換えられる)とを用いて定義された劣モジュラ性評価関数を最適化する一組の選択特徴群を決定する。
【００１７】
以上の構成により、選択される特徴群の有用性と独立性の双方の観点から多項式時間で適正な特徴選択を行なうことができる。
【００１８】
（第２実施形態）
次に本発明の第２実施形態としての情報処理装置２００について、図２以降を用いて説明する。情報処理装置２００においては、評価関数Ｅを、各特徴の有用性と特徴間の独立性の双方を用いて定義する。そして、有用性が高くかつ独立性の高い特徴群を選択する際に評価関数Ｅの値が小さくなるように設計する。また、評価関数Ｅを、劣モジュラ性を満たす関数として定義し、グラフカットなどの最適化手法を用いることで、多項式時間で大局的に最適化することができる。
【００１９】
［前提技術］
まず、本実施形態としての情報処理装置２００において適用される特徴選択方法の前提となる技術について説明する。複数の特徴を含む特徴群から、どの特徴を選択すべきかを決定するにあたり、個々の特徴の有用性を何らかの尺度で評価し、有用性の高い順に特徴を選択していく方法が考えられる。図１０は、その場合のシステム構成を示す図である。特徴入力部１００１が入力した複数の特徴から、選択特徴群決定部１００２で、選択すべき特徴群を決定し、特徴出力部１００５で選択すべき特徴群を出力する。選択特徴群決定部１００２においては、有用性評価部１００３で、有用性を評価する。さらに有用性最適化部１００４において、各特徴の有用性が最適になるような特徴を選択する。ここで、有用性とは、特徴が機械学習の際にどれだけ有用かを表すものであり、フィッシャーの判別基準や特徴とクラスとの相関などを有用性の尺度として用いることができる。
【００２０】
しかし図１０の構成では、入力特徴群の中に、有用性は高いが互いに冗長な特徴群が含まれている場合（極端な例では、全く同じ特徴が複数ある場合）、選択後の特徴群に互いに冗長な特徴が含まれてしまうという問題がある。この問題を回避するため、図１１のように、特徴の有用性とともに特徴間の独立性も評価する手法が考えられる。そこで独立性を考慮、独立性とは、複数の特徴がお互いにどれだけ独立かを表すものである。広く用いられている独立性の尺度としては、相関係数や相互情報量が挙げられる。図１１の構成では、特徴入力部１１０１が入力した複数の特徴から、選択特徴群決定部１１０２で、選択すべき特徴群を決定し、特徴出力部１１０５で選択すべき特徴群を出力する。選択特徴群決定部１１０２においては、独立性評価部１１０６で独立性を評価した後、独立性最適化部１１０７で独立性を最適化し、有用性評価部１１０３で有用性を評価して、有用性最適化部１１０４において、各特徴の有用性が最適になるような特徴を選択する。つまり、入力の特徴群を特徴間の独立性に応じてクラスタリングし、次に、クラスタリング結果を用いた拘束条件下で特徴の有用性による特徴選択を行う。
【００２１】
しかし、この手法では、有用性による最適化と独立性による最適化を別々に行っているため、有用性と独立性の双方の観点から真に最適な特徴選択が得られることを保証しないという問題がある。
【００２２】
更に、図１２に示す構成では、特徴入力部１２０１が入力した複数の特徴から、選択特徴群決定部１２０２で、選択すべき特徴群を決定し、特徴出力部１２０５で選択すべき特徴群を出力する。選択特徴群決定部１２０２においては、特徴群候補探索部１２０４での特徴群候補の探索と、特徴群評価部１２０３での特徴群候補の評価とを繰り返し、最適な特徴群を見つけ出す。この方法では、特徴の組み合わせを直接評価しているため、より精度の高い特徴選択を行うことができるが、一方で、特徴群候補探索の計算コストが高く、多項式時間で最適な特徴選択を得ることができないという問題がある。
【００２３】
結局のところ、図１０〜図１２の構成では、選択される特徴群の有用性と独立性の双方の観点から真に最適な特徴選択が行われないという問題がある。その理由は、特徴の有用性を評価する段階と、特徴間の独立性を評価する段階とを直列に連結し、それぞれ別に最適化を行っているため、あるいは、１つずつ特徴を選択し、最終的に選択した特徴群に対する最適化が行われていないためである。
【００２４】
例えば、２クラスの識別問題に関するデータセットにおいて、２つの特徴を選択することを考える。識別問題では、特徴の有用性は、その特徴のみを用いた場合の最適な識別境界による誤識別率の低さとして表現でき、これはクラスごとのサンプルの確率密度関数の重なり部分の面積の小ささに等しい。ここで、有用性は同等だが相関が非常に高い特徴ａ、ｂを選択したときの、クラスごとのサンプルの分布に関する確率密度関数を図７に示す。２つの特徴は非常に相関が高いため、サンプルはａ＝ｂ上に分布する。このため、図７中に示した３種類の識別境界は同等の性能を示し、その誤識別率（図中斜線部の面積）は、片方の特徴のみを用いた場合と同じである。一方、特徴ｂの代わりに、有用性はやや劣るが特徴ａとの相関がほぼ無い特徴ｃを選択した場合を考える。
【００２５】
この時、特徴ａのみを用いた場合の誤識別率と同じ誤識別率を示す識別境界は図８のようになる。特徴ａ、ｂを用いた場合ではこの識別境界が最適であったが、特徴ａ、ｃを用いた場合では図９に示すように、より誤識別率の低い識別境界が存在する。すなわち、相関の非常に高い特徴ｂを選択するよりも、有用性は劣るが相関の無い特徴ｃを選択する方がよい。上記の例からわかるように、特徴選択において特徴の有用性と特徴間の独立性は双方同時に考慮する必要がある。
【００２６】
［機能構成の説明］
図２は、本実施形態に係る情報処理装置２００の機能構成を示す図である。情報処理装置２００は、事前に抽出された特徴群を入力する特徴入力部２０４と、入力された特徴の有用性を評価する有用性評価部２０１と、入力された特徴の独立性を評価する独立性評価部２０２とを備えている。また更に、情報処理装置２００は、有用性と独立性の評価結果から、選択すべき特徴群を決定する選択特徴群決定部２０３と、決定した選択特徴群を出力する選択特徴群出力部２０５を備えている。
【００２７】
有用性評価部２０１は、個々の特徴に関して、学習における有用性をあらかじめ定められた手法によって有用性尺度を計算する。例えば、２つ以上の特徴を引数とする有用性尺度を算出する。独立性評価部２０２は、特徴間の独立性をあらかじめ定められた手法によって独立性尺度を計算する。例えばここでは、特徴群から抽出した２つの特徴から独立性尺度を算出する。３つ以上の特徴を引数とする独立性尺度を算出してもよい。
【００２８】
評価関数設定部２３１は、有用性評価部２０１で得られた特徴の有用性尺度と、独立性評価部２０２で得られた特徴間の独立性尺度とを用いて劣モジュラ性評価関数を設定する。また、評価関数最適化部２３２は、構成された劣モジュラ性評価関数を最適化する。
【００２９】
［ハードウェア構成の説明］
図３は、本実施形態に係る情報処理装置２００のハードウェア構成を示す図である。情報処理装置２００は、ＣＰＵ３１０、ＲＯＭ３２０、通信制御部３３０、ＲＡＭ３４０、及びストレージ３５０を備えている。ＣＰＵ３１０は中央処理部であって、様々なプログラムを実行することにより情報処理装置３００全体を制御する。ＲＯＭ３２０は、リードオンリメモリであり、ＣＰＵ３１０が最初に実行すべきブートプログラムの他、各種パラメータ等を記憶している。また、通信制御部３３０は、他の端末とのネットワークを介した通信を制御する。
【００３０】
ＲＡＭ３４０は、ランダムアクセスメモリであり、特徴選択アプリケーション３４１の実行領域を有している。特徴選択アプリケーション３４１は、特徴入力モジュール３４２と、有用性評価モジュール３４３と、独立性評価モジュール３４５と、評価関数設定モジュール３４７とを有する。一方、ストレージ３５０は、特徴群データベース３５１として、全特徴群データベース３５２と選択特徴群データベース３５３とを有する。
【００３１】
［動作の説明］
図２乃至図４を参照して本実施形態の動作について詳細に説明する。図４は、本実施形態に係る情報処理装置の処理の流れを示すフローチャートである。
【００３２】
まず、ステップＳ４０１において、ＣＰＵ３１０が特徴入力モジュール３４２を実行することにより特徴入力部２０４として機能し、機械学習に用いるために事前に抽出された特徴群の入力を受ける。
【００３３】
次に、ＣＰＵ３１０は、有用性評価モジュール３４３を実行することにより有用性評価部２０１として機能し、入力した複数の特徴のそれぞれについて有用性を評価する。更に、生成した有用性評価尺度３４４を一旦ＲＡＭ３４０に格納した上で選択特徴群決定部２０３に出力する（Ｓ４０３）。
【００３４】
ほぼ同時に、ＣＰＵ３１０は、独立性評価モジュール３４５を実行することにより独立性評価部２０２として機能し、入力した複数の特徴のそれぞれについて独立性を評価する。更に、生成した独立性評価尺度３４６を一旦ＲＡＭ３４０に格納した上で選択特徴群決定部２０３に出力する（Ｓ４０３）。
【００３５】
ＣＰＵ３１０は評価関数設定モジュール３４７を実行することにより、評価関数設定部２３１として機能し、入力された有用性尺度と独立性尺度を用いて劣モジュラ性評価関数を生成する（Ｓ４０９）。
【００３６】
更に、ＣＰＵ３１０は、評価関数最適化モジュール３４８を実行して、評価関数最適化部２３２として機能し、ステップＳ４０９で生成した評価関数を最適化する。選択特徴群出力部２０５は、評価関数の最適化の結果から、選択される特徴群を決定し、出力する（Ｓ４１１）。
【００３７】
［数式を用いた処理の流れ］
識別問題を例に、特徴の評価方法について詳細に説明する。入力として、ｄ個の特徴からなるサンプルがＮ個と、各々のサンプルが所属するクラスを表すクラスラベルＮ個を仮定する。以下では、サンプルを並べた行列をＸ、クラスラベルを並べたベクトルをｙと表記する。特徴選択とは、ｄ個の特徴について選択・非選択を決定する処理であり、数式（１）に示すベクトルｓを決定する処理として定義できる。ただし、ｓの各要素は０（非選択）もしくは１（選択）の値をとる。
【数１】
2012111235.tif 000003
【００３８】
入力されたサンプルＸ、クラスラベルｙを用いて、有用性評価部２０１は、ｄ個の特徴について、以下の数式（２）のように、それぞれの特徴の有用性尺度Ｅ１を計算する。ただし、Ｘ（ｉ）はｉ番目の特徴のみからなるサンプル群である。有用性尺度Ｅ１の定義には、例えば、個々の特徴とクラスラベルとの相関係数や、１つの特徴のみで学習した識別器の識別性能などを用いることができる（Guyon and A. Elisseeff, "An Introduction to Variable and Feature Selection," the Journal of Machine Learning Research, vol. 3, pp. 1157--1182, 2003）。
【数２】
2012111235.tif 000004
【００３９】
また、独立性評価部２０２は、以下の数式（３）を用いて、全ての特徴の組み合わせについて独立性尺度Ｅ２を計算する。
【数３】
2012111235.tif 000005
【００４０】
ただし、独立性尺度Ｅ２は、劣モジュラ性と呼ばれる以下の条件（４）を常に満たすように定義する。劣モジュラ性については、V.Kolmogorov and R.Zabih,"What Energy Functions Can Be Minimized via Graph Cuts?",IEEE Transactions on Pattern Analysis and Machine Intelligence,vol.26,no.2,pp.147-159,2004.に記載がある。独立性尺度Ｅ２の定義には、例えば、特徴間の相関係数や相互情報量などを用いることができる。
【数４】
2012111235.tif 000006
【００４１】
有用性尺度Ｅ１、独立性尺度Ｅ２を用いて、評価関数設定部２３１は、以下の数式（５）のように評価関数Ｅを最小化する。ただし、λは２つの項の相対的な重さを決定する正の定数である。
【数５】
2012111235.tif 000007
【００４２】
評価関数Ｅの最小化には、例えばグラフカットといった手法を用いることができる。すなわちここでは、一組の選択特徴群を決定するため、最大で２つの特徴を引数とする項からなる劣モジュラ性評価関数を最適化する。選択特徴群出力部２０５は、評価関数最適化部２３２から出力される特徴選択ベクトルｓを受け、評価関数Ｅを最小化する特徴群Ｘ'を出力する。
【数６】
2012111235.tif 000008
【００４３】
最適化手法としては、グラフカットや楕円体法など、劣モジュラ関数最小化手法であれば如何なる方法をも用いることができる。他の手法としてなどがある。なおここでは、有用性尺度Ｅ１を個々の特徴のみから計算し、独立性尺度Ｅ２を２つの特徴のみから計算した。しかし、一般に評価関数Ｅが劣モジュラ性を満たす範囲で、２つ以上の特徴を引数とする有用性尺度の項、あるいは３つ以上の特徴を引数とする独立性尺度の項を定義することも可能である。例えば、有用性尺度ではｍ個以下の特徴を用い、独立性尺度ではｎ個以下の特徴を用いて計算する場合では、評価関数Ｅは以下の数式（７）のようになる。ただし、ｉ  （１），  ...，  ｉ  （ｍ）とｊ  （１），  ...，  ｊ  （ｎ）は、それぞれｍ、ｎ個の特徴を選んだ際の特徴のインデックスである。
【数７】
2012111235.tif 000009
【００４４】
この時、評価関数Ｅが劣モジュラ性を満たすためには、全ての２つの特徴の組み合わせに関して上述の数式（４）を満たすことが必要十分条件であり、Ｅ１、Ｅ２とも慎重に設計する必要がある。
【００４５】
［具体例］
図５のフローチャートを用いて具体的な実施形態を示す。ステップＳ５０１において特徴入力部２０４はサンプル群Ｘ，ｙを入力する。有用性評価部２０１では、フィッシャーの判別基準を用いて以下の数式（８）のように有用性尺度Ｅ１を計算する（Ｓ５０３）。ただし、ｍは全サンプルの平均、ｍｃはクラスｃに属するサンプルの平均、ｎｃはクラスｃに属するサンプルの数である。
【数８】
2012111235.tif 000010
【００４６】
数式（８）はフィッシャーの判別基準と呼ばれる尺度であり、一般的には値が大きいほどクラスごとのサンプルの分離度が高く、識別しやすいことを示す。評価関数Ｅの最小化によって有用性の高い特徴が選択されるためには、Ｅ１は、特徴の有用性が高いほど、Ｅ１（０，Ｘ，ｙ）に対するＥ１（１，Ｘ，ｙ）が大きくなる必要がある。Ｅ１（０，Ｘ，ｙ）の定義にはいくつかの方法が考えられるが、大きく２種類の設計が考えられる。１つは適当な定数値を用いる方法（例えば、数式（９））、もう１つはＥ１（１，Ｘ，ｙ）に依存する値を用いる方法（例えば、数式（１０））である。θは定数であり、例えば数式（１１）のようにＥ１（１，Ｘ，ｙ）の平均値などを用いることができる。
【数９】
2012111235.tif 000011
【数１０】
2012111235.tif 000012
【数１１】
2012111235.tif 000013
【００４７】
また、独立性評価部２０２では、以下のように相関係数ρを用いて独立性尺度Ｅ２を計算する（Ｓ５０５）。
【数１２】
2012111235.tif 000014
【数１３】
2012111235.tif 000015
ａ００、ａ０１、ａ１０、ａ１１はそれぞれ定数であり、例えば以下のように設定する。相関係数ρｉｊの絶対値は、ｉ番目の特徴とｊ番目の特徴との冗長性の高さ（独立性の低さ）を表している。
【数１４】
2012111235.tif 000016
【００４８】
上記のようにＥ２を定義すると、相関の低い（独立性の高い）特徴同士はＥ２の値が小さくなるため、主に有用性尺度Ｅ１によって選択・非選択が決定される。一方、相関の高い（独立性の低い）特徴同士は、両方選択する場合にＥ２が大きなエネルギーとなるため、同時に選択されにくくなる。これにより、有用性が高く、互いに独立性の高い特徴が選択されやすくなる。また、Ｅ２は劣モジュラ性（数式（４））を満たす。
【００４９】
選択する特徴の数は必要最低限であることが理想的であるため、選択する特徴の数が多いほどＥ２も大きくなるようにａ００、ａ０１、ａ１０、ａ１１を設定することが望ましく、また、劣モジュラ性を満たす範囲で自由に設定できる。ａ０１とａ１０は必ずしも一致する必要はなく、例えば有用性の高い特徴だけを選択する場合にはＥ２の値が小さくなるようにａ０１とａ１０を設定する、などといったことも可能である。評価関数最適化部２３２では、上記のように定義されたＥ１、Ｅ２からなる評価関数Ｅを、グラフカットによって最適化する（Ｓ５０７）。グラフカットを用いた最適化の詳細については、V.Kolmogorov and R.Zabih,"What Energy Functions Can Be Minimized via Graph Cuts?",IEEE Transactions on Pattern Analysis and Machine Intelligence,vol.26,no.2,pp.147-159,2004に示されている。
【００５０】
グラフカットによる最適化について述べる。まず、図６に示すように、各特徴を表すｄ個のノードｖｉ（６０３）と、２つのダミーノードｖｓ，ｖｔ（６０１，６０２）からなるグラフを生成する。全てのノード間をエッジで接続し、各エッジには以下の数式（１５）〜（１７）のようにコストｃを割り当てる。ただし、Ｋはエッジのコストが負にならないように設定される十分大きな定数である。
【数１５】
2012111235.tif 000017
【数１６】
2012111235.tif 000018
【数１７】
2012111235.tif 000019
【００５１】
上記のように生成したグラフをｖｓ−ｖｔ間で切断し、ｖｓを含むノード群Ｓとｖｔを含むノード群Ｔとに分ける。この時、グラフカットを用いて切断コストが最小となる切断を求め、以下の数式（１８）のようにｓを決定すると、ｓは評価関数Ｅの大局的な最適解に一致する。この証明はV.Kolmogorov and R.Zabih,"What Energy Functions Can Be Minimized via Graph Cuts?",IEEE Transactions on Pattern Analysis and Machine Intelligence,vol.26,no.2,pp.147-159,2004で示されている。
【数１８】
2012111235.tif 000020
【００５２】
選択特徴群出力部２０５では、ｉ番目の特徴に関し、グラフカットによって得られた解ｓにおいてｓｉ＝１ならば選択し、ｓｉ＝０ならば選択しないとすることで、最終的に選択する特徴群を決定する。
【００５３】
ここでは、評価関数Ｅの最小化にグラフカットを用いたが、一般に劣モジュラ性関数を多項式時間で最小化する手法は複数存在しており、それらを評価関数最適化部２３２に用いることもできる。なお特徴群に含まれる各特徴は、それぞれ複数のパラメータを含んでもよい。
【００５４】
［実施形態の効果］
以上本実施形態によれば、特徴群の有用性と独立性の双方の観点から最適な特徴選択を得ることができる。その理由は、特徴の有用性を評価する項と、特徴間の独立性を評価する項からなる評価関数を用いているためである。
【００５５】
また、多項式時間で真に最適な特徴選択を得ることができる。多項式時間とはすなわち、入力特徴数に対して、たかだかその定数乗でしか計算時間が増えないという意味である。その理由は、劣モジュラ性を満たす評価関数の最小化として特徴選択を行うためである。
【００５６】
［産業上の利用可能性］
上述の実施形態を、顔認識やオブジェクト認識、文字認識、音声認識などといった用途に、学習の前処理として適用できる。
【００５７】
（他の実施形態）
以上、実施形態を参照して本願発明を説明したが、本願発明は上記実施形態に限定されるものではない。本願発明の構成や詳細には、本願発明のスコープ内で当業者が理解し得る様々な変更をすることができる。また、それぞれの実施形態に含まれる別々の特徴を如何様に組み合わせたシステム又は装置も、本発明の範疇に含まれる。
【００５８】
また、本発明は、複数の機器から構成されるシステムに適用されても良いし、単体の装置に適用されても良い。さらに、本発明は、実施形態の機能を実現するプログラムが、システム或いは装置に直接或いは遠隔から供給される場合にも適用可能である。したがって、本発明の機能をコンピュータで実現するために、コンピュータにインストールされるプログラム、或いはそのプログラムを格納した記憶媒体、そのプログラムをダウンロードさせるＷＷＷ（World Wide Web）サーバも、本発明の範疇に含まれる。
【００５９】
［実施形態の他の表現］
上記の実施形態の一部又は全部は、以下の付記のようにも記載されうるが、以下には限られない。
【００６０】
（付記１）
特徴群に含まれる各特徴の有用性尺度を算出することにより有用性を評価する有用性評価手段と、
前記特徴群に含まれる特徴間の独立性尺度を算出することにより独立性を評価する独立性評価手段と、
前記有用性評価手段で計算された有用性尺度と前記独立性評価手段で計算された独立性尺度とを用いて定義された劣モジュラ性評価関数が所定条件を満たすように一組の選択特徴群を決定する選択特徴群決定手段と、
を備えたことを特徴とする情報処理装置。
（付記２）
前記選択特徴群決定手段は、
前記劣モジュラ性評価関数を最小化する一組の選択特徴群を決定することを特徴とする付記１に記載の情報処理装置。
（付記３）
前記特徴群に含まれる各特徴は、それぞれ複数のパラメータを含むことを特徴とする付記１に記載の情報処理装置。
（付記４）
前記選択特徴群決定手段は、一組の選択特徴群を決定するため、最大で２つの特徴を引数とする項からなる劣モジュラ性評価関数を最適化することを特徴とする付記１、２または３に記載の情報処理装置。
（付記５）
前記有用性評価手段は、２つ以上の特徴を引数とする有用性尺度を算出することを特徴とする付記１乃至４の何れかに記載の情報処理装置。
（付記６）
前記有用性評価手段は、フィッシャーの判別基準を用いて有用性尺度を算出することを特徴とする付記１乃至５の何れかに記載の情報処理装置。
（付記７）
前記独立性評価手段は、前記特徴群から抽出した２つの特徴から独立性尺度を算出することを特徴とする付記１乃至６の何れかに記載の情報処理装置。
（付記８）
前記選択特徴群決定手段は、前記有用性評価手段で算出された有用性尺度と、前記独立性評価手段で算出された独立性尺度とを含む評価関数を、グラフカットによって最適化することを特徴とする付記１乃至７の何れかに記載の情報処理装置。
（付記９）
特徴群に含まれる各特徴の有用性を評価する有用性評価ステップと、
前記特徴群に含まれる特徴間の独立性を評価する独立性評価ステップと、
前記有用性評価ステップで計算された有用性尺度と前記独立性評価ステップで計算された独立性尺度とを用いて定義された劣モジュラ性評価関数が所定条件を満たすように一組の選択特徴群を決定する選択特徴群決定ステップと、
を含むことを特徴とする情報処理方法。
（付記１０）
特徴群に含まれる各特徴の有用性を評価する有用性評価ステップと、
前記特徴群に含まれる特徴間の独立性を評価する独立性評価ステップと、
前記有用性評価ステップで計算された有用性尺度と前記独立性評価ステップで計算された独立性尺度とを用いて定義された劣モジュラ性評価関数が所定条件を満たすように一組の選択特徴群を決定する選択特徴群決定ステップと、
をコンピュータに実行させるプログラムを格納したことを特徴とする記憶媒体。
【００６１】
この出願は、２０１１年２月１７日に出願された日本国特許出願  特願２０１１−０３１８５６号を基礎とする優先権を主張し、その開示の全てをここに取り込む。
【図１】
2012111235.tif 000021
【図２】
2012111235.tif 000022
【図３】
2012111235.tif 000023
【図４】
2012111235.tif 000024
【図５】
2012111235.tif 000025
【図６】
2012111235.tif 000026
【図７】
2012111235.tif 000027
【図８】
2012111235.tif 000028
【図９】
2012111235.tif 000029
【図１０】
2012111235.tif 000030
【図１１】
2012111235.tif 000031
【図１２】
2012111235.tif 000032
【手続補正書】
【提出日】平成25年5月21日(2013.5.21)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
特徴群に含まれる各特徴の有用性尺度を算出することにより有用性を評価する有用性評価手段と、
前記特徴群に含まれる特徴間の独立性尺度を算出することにより独立性を評価する独立性評価手段と、
前記有用性評価手段で計算された有用性尺度と前記独立性評価手段で計算された独立性尺度とを用いて定義された劣モジュラ性評価関数が所定条件を満たすように一組の選択特徴群を決定する選択特徴群決定手段と、
を備えたことを特徴とする情報処理装置。
【請求項２】
前記選択特徴群決定手段は、前記劣モジュラ性評価関数を最小化する一組の選択特徴群を決定することを特徴とする請求項１に記載の情報処理装置。
【請求項３】
前記特徴群に含まれる各特徴は、それぞれ複数のパラメータを含むことを特徴とする請求項１または２に記載の情報処理装置。
【請求項４】
前記選択特徴群決定手段は、一組の選択特徴群を決定するため、最大で２つの特徴を引数とする項からなる劣モジュラ性評価関数を最適化することを特徴とする請求項１、２または３に記載の情報処理装置。
【請求項５】
前記有用性評価手段は、２つ以上の特徴を引数とする有用性尺度を算出することを特徴とする請求項１乃至４の何れか１項に記載の情報処理装置。
【請求項６】
前記有用性評価手段は、フィッシャーの判別基準を用いて有用性尺度を算出することを特徴とする請求項１乃至５の何れか１項に記載の情報処理装置。
【請求項７】
前記独立性評価手段は、前記特徴群から抽出した２つの特徴から独立性尺度を算出することを特徴とする請求項１乃至６の何れか１項に記載の情報処理装置。
【請求項８】
前記選択特徴群決定手段は、前記有用性評価手段で算出された有用性尺度と、
前記独立性評価手段で算出された独立性尺度とを含む評価関数を、グラフカットによって最適化することを特徴とする請求項１乃至７の何れか１項に記載の情報処理装置。
【請求項９】
特徴群に含まれる各特徴の有用性を評価する有用性評価ステップと、
前記特徴群に含まれる特徴間の独立性を評価する独立性評価ステップと、
前記有用性評価ステップで計算された有用性尺度と前記独立性評価ステップで計算された独立性尺度とを用いて定義された劣モジュラ性評価関数が所定条件を満たすように一組の選択特徴群を決定する選択特徴群決定ステップと、
を含むことを特徴とする情報処理方法。
【請求項１０】
特徴群に含まれる各特徴の有用性を評価する有用性評価ステップと、
前記特徴群に含まれる特徴間の独立性を評価する独立性評価ステップと、
前記有用性評価ステップで計算された有用性尺度と前記独立性評価ステップで計算された独立性尺度とを用いて定義された劣モジュラ性評価関数が所定条件を満たすように一組の選択特徴群を決定する選択特徴群決定ステップと、
をコンピュータに実行させる情報処理プログラム。
【国際調査報告】
2012111235.tif 000033
2012111235.tif 000034