スパース主成分分析の基数制約組み合わせ最適化問題に対する候補解を最大にするための、そして該最適化問題を解くための、コンピュータによって実施される方法
【課題】方法は、スパース主成分分析の基数制約組み合わせ最適化問題に対する候補解を最大にする。
【解決手段】近似的な方法は、入力として、共分散行列Ａ、候補解、およびスパーシティパラメータｋを有する。その後、Ａの部分行列固有値分解によって、共分散行列Ａおよびスパーシティパラメータｋの固有値構造に関する候補解ベクトルｘのための変分再正規化を実行して、最も可能性の高い解である、分散最大化ｋ−スパース固有ベクトルｘ（＾）が求められる。別の方法は、順方向パスおよび逆方向パスを含むネストされた貪欲探索技法によって、その問題を解く。その問題に対する厳密解は、貪欲解の出力で、分岐限定探索を初期化する。
【解決手段】近似的な方法は、入力として、共分散行列Ａ、候補解、およびスパーシティパラメータｋを有する。その後、Ａの部分行列固有値分解によって、共分散行列Ａおよびスパーシティパラメータｋの固有値構造に関する候補解ベクトルｘのための変分再正規化を実行して、最も可能性の高い解である、分散最大化ｋ−スパース固有ベクトルｘ（＾）が求められる。別の方法は、順方向パスおよび逆方向パスを含むネストされた貪欲探索技法によって、その問題を解く。その問題に対する厳密解は、貪欲解の出力で、分岐限定探索を初期化する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、包括的には主成分分析（ＰＣＡ：Ｐｒｉｎｃｉｐａｌ Ｃｏｍｐｏｎｅｎｔ Ａｎａｌｙｓｉｓ）に関し、より詳細には、顔認識および金融資産管理のような実用的な応用形態にスパース主成分分析を適用することに関する。
【背景技術】
【０００２】
主成分分析（ＰＣＡ）は、よく知られている多変量統計分析技法である。ＰＣＡは、データ分析および次元削減のために頻繁に用いられる。ＰＣＡは、科学、工学および金融の至るところで応用形態を有する。
【０００３】
ＰＣＡは、データにおいて、最大分散を獲得する入力変数の一次結合を求める。典型的には、ＰＣＡは、データ行列の特異値分解（ＳＶＤ）を用いて実行される。別法として、共分散行列が用いられる場合には、固有値分解を適用することができる。ＰＣＡは、情報の損失を最小限に抑えたデータ圧縮を提供する。さらに、主成分は、無相関である。これは、データ分析を容易にする。
【０００４】
残念なことに、ＰＣＡは、通常、全てのデータの０でない一次結合、すなわち「負荷」を伴う。しかしながら、生命情報科学、計算機生物学、コンピュータビジョン、金融資産管理、並びに地球物理学的データ、遺伝学的データおよび医療データの分析のような、多くの実用的な応用形態の場合に、座標軸は、物理的な意味を有する。それゆえ、０でない負荷の数を削減することが好都合であろう。これは、低次元であるが、それでもデータ内の分散を特徴付ける「スパースな（まばらな）」主成分を提供するであろう。
【０００５】
スパースなデータ表現は、人間が理解するのを助け、計算コストを削減し、学習モデルにおいて、より良好な一般化を与えるので、一般的に望ましい。
【０００６】
金融ポートフォリオ最適化、および地理空間統計学における資源配分等の応用形態の場合、スパースネスは、多くの場合に、空間／時間および材料費が投資または測定単位の数を制約する可能性があるか否かの判定基準を定義する鍵である。機械学習では、入力データのスパースネスは、特徴選択および自動適合性判定に関連付けられる。
【０００７】
従来のスパースＰＣＡは、典型的には、軸回転および成分閾値処理等の簡単な変換を適用する。J. CadimaおよびI. Jolliffe著「Loadings and correlations in the interpretation of principal components」（Applied Statistics, vol. 22, pp. 203-214, 1995）を参照願いたい。基本的に、根底にある目標は、多くの場合に主変数の特定および分析に基づいて、回帰分析のための特徴の部分集合を選択することである。G. McCabe著「Principal Variables」（Technometrics, vol. 26, pp. 137-144, 1984）を参照願いたい。
【０００８】
最初の確実な計算方法、すなわち、ＳＣｏＴＬＡＳＳは、適当な最適化フレームワークを提供する。しかしながら、その方法は、計算上、実用的ではない。I. JolliffeおよびM. Uddin著「A modified principal component technique based on the Lasso」（Journal of Computational and Graphical Statistics, vol. 12, pp. 531-547, 2003）を参照願いたい。
【０００９】
別の方法は、従来の主成分に関して、Ｌ１−罰則付き回帰を用いるＥｌａｓｔｉｃＮｅｔ定式化を用いる。H. Zou、T. HastieおよびR. Tibshirani著「Sparse principal component analysis」（Journal of Computational and Graphical Statistics）（掲載予定）を参照願いたい。
【００１０】
別の方法は、スパースＰＣＡに関連する問題、すなわち、非凸性の高い目的関数を認識している。A. d'Aspremont、L. El Ghaoui、M. I. JordanおよびG. R. G. Lanckriet著「A direct formulation for sparse PCA using semi-definite programming」（Advances in Neural Information Processing Systems (NIPS), December 2004）を参照願いたい。その方法は、半正定値計画（ＳＤＰ：Ｓｅｍｉ−Ｄｅｆｉｎｉｔｅ Ｐｒｏｇｒａｍｍｉｎｇ）を用いて凸近似を求めることにより、厳しい基数制約を緩和する。
【発明の開示】
【発明が解決しようとする課題】
【００１１】
データのスパース主成分分析（ＰＣＡ）が、スパース固有ベクトルの基底を求める。スパース固有ベクトルの射影が、そのデータの最大分散を表す。スパースＰＣＡは、特定の部類のＮＰ困難で、基数制約の、非凸最適化問題に属する。スパースＰＣＡは、生命情報科学から金融工学およびコンピュータビジョンに及ぶ広範な応用形態のために用いることができる。
【００１２】
従来のスパースＰＣＡは、典型的には、連続的な近似および凸緩和を用いて、スパースな主成分を求める。
【００１３】
本発明は、新規のスパースＰＣＡ法を提供する。本方法は、変分固有値範囲に基づく離散的な定式化を用いる。本方法は、最適なスパースな主成分を求める。本方法は、近似的な貪欲探索過程および厳密分岐限定（探索過程を用いることができる。
【００１４】
さらに、任意のＰＣＡ法によって得られた近似的な候補解を改善するために、離散スペクトル定式化を用いる簡単な後処理再正規化ステップを適用することができる。
【課題を解決するための手段】
【００１５】
本発明の１つの実施の形態では、コンピュータによって実施される方法が、スパース主成分分析の基数制約組み合わせ最適化問題に対する候補解を最大にする。
【００１６】
複数の要素からなる候補解ベクトルｘが、その候補解ベクトルｘのそれぞれ取り得る要素対間の共分散を示す共分散行列Ａとともに与えられる。その候補解は、貪欲探索を用いて求めることができる。最終解の基数を表すスパーシティパラメータｋも自動的に与えられるか、または求められる。
【００１７】
その後、共分散行列Ａおよびスパーシティパラメータｋに関して候補解ベクトルｘのための変分再正規化を実行して、スパーシティパラメータｋに局所的に最適であり、かつスパース主成分分析最適化問題に対する最終解である、以下の分散最大化ｋ−スパース固有ベクトルｘ（＾）が得られる（ここで、ｘ（＾）は、ｘの上に＾がついたものを表す）。
【発明を実施するための最良の形態】
【００１８】
本発明の１つの実施の形態は、スペクトル範囲を用いて、データに対してスパース主成分分析を実行するための方法を提供する。スパースＰＣＡを用いて、実用的な組み合わせ最適化問題に対する解を求めることができる。
【００１９】
従来技術とは対照的に、本発明は、変分固有値範囲に基づく離散的な定式化を用いる。本方法は、近似解の場合には貪欲探索を、厳密解の場合には分岐限定探索を用いて、最適なスパースな主成分を求める。
【００２０】
たとえば、本方法は、以下の実用的な株式ポートフォリオ最適化問題を最適に解くために用いることができる。スタンダード＆プアーズ株価指数に掲載される５００銘柄のような、入手可能な株式の実質的に大きなプールから選定された１０銘柄ｘに投資することが望ましい。入力５００×５００共分散行列Ａは、５００銘柄の各対間のリスク／リターン実績における共分散を示す。最終解ベクトルｘ（＾）内に０でない１０個の要素だけが存在するという制約を前提として、ｘＴＡｘ／ｘＴｘが最大にされるような、配分の５００次元ベクトルｘ（＾）を見つけることが望ましい。
【００２１】
これは基本的には、２つの問題、すなわち最良の１０銘柄の株式を選定するという問題、および選択された株式の中で資金を配分するという問題に分解することができる。第２の問題は、第１の問題よりも解くのが容易である。第２の問題に対する解または「解決法」は、以下のとおりである。１０銘柄の株式が既に選定されているものと仮定する。その際、以下に記述される命題１に従って、最良の資金配分方式が、これらの１０銘柄の株式に対応する共分散行列Ａの行／列を抽出し、主要または主固有ベクトル、すなわち、最大固有値または分散に対応する固有ベクトルを求める。これは、候補解のための最良の局所解であることが保証される。ただし、「局所」は、同じ１０銘柄の株式を用いる全ての取り得る配分の中にあることを意味する。
【００２２】
これは簡単な解のように見えるかもしれないが、従来技術は、これまで、ここで示した目新しいやり方で、この問題を取り扱ったことがない。言い換えると、人々は、上記の２つの問題を一緒に取り扱っており、それゆえ、１０銘柄の株式のリストと同時に、各株式に配分される資金を見つけ出した。彼らは、１０銘柄の株式のリストを得た後に、主要固有ベクトルを用いて、選択された株式の中で資金を配分することへの最適解を求めるべきであることを理解していなかった。
【００２３】
第１の問題は、解くのがはるかに難しい。実際には、この問題は、ＮＰ困難として知られている問題である。これは、この問題の複雑さが、多項式時間における非決定性チューリング機械によって解くことができる問題よりも本質的に難解であることを意味する。組み合わせ最適化問題の決定性のものがＮＰ完全問題の部類に属するとき、最適化するものはＮＰ困難である。
【００２４】
それゆえ、その解は、以下のように特徴付けられる。株式の候補リストを与えられるとき、その最大値は、Ａの対応する部分行列の固有値によって範囲を定められることがわかっている。株式銘柄Ａ、Ｂ、Ｃが選定される場合には、Ａから３×３行列が生成され、その最大固有値が求められる。これが最大値になるであろう。さらに、１０銘柄の株式のリストがＡの対応する１０×１０部分行列の主要固有値によって上限を定められる場合には、これらの１０銘柄の株式の任意の部分集合が、その１０×１０部分行列の主要固有値によって同様に上限を定められる。
【００２５】
分岐限定探索において、これら２つの観測値の組み合わせが用いられ、全体的に最適な厳密解を見つけることが保証される。局所的に次善最適な貪欲探索は、その探索が終了するまで、株式を１つずつ追加（または削除）する。
【００２６】
コンピュータビジョンの応用形態では、同じ技法を用いて、１つの画像内で処理すべきピクセルの部分集合を求めることができる。たとえば、顔認識の応用形態では、計算資源およびメモリ資源が限られている。それゆえ、画像内の顔の突出部に対応するピクセルだけを処理することが理にかなっている。
【００２７】
最大化された解
ここで、図１を用いて、実用的な組み合わせ最適化問題に対する事前に得られた候補解１０１を改善するための方法１００を説明する。その方法への入力は、その問題の候補解である要素からなるデータベクトルｘ１０１、共分散行列Ａ１０３、およびスパーシティパラメータｋ１０２である。スパーシティパラメータｋは、その問題の最終解ベクトルｘ（＾）１０４内の０でない要素または「基数」の最大数を表す。
【００２８】
たとえば、データベクトルｘ内の要素は、４つの入手可能な株式または資産グループ内のスパースな投資に対応する。共分散行列Ａは、これら４つの資産の中のそれぞれ入手可能な要素対のリスク／リターン共分散を示す。株式および指標は、任意の既知の方法を用いて求めることができる。ここで、スパーシティパラメータｋは、２に設定される。言い換えると、最良の金融リターンを得るために、資金は、４つの資産のうちの２つだけに配分されることになる。
【００２９】
それらの入力に従って、変分再正規化２００が実行され、最大化された解ベクトルｘ（＾）１０４が求められる。図２に示されるように、変分再正規化２００は、入力データベクトルｘ１０１の最も大きなｋ個の要素１０２または「負荷」を、入力行列Ａ１０３の行および列から抽出される、対応するｋ×ｋ主部分行列Ａｋ２０１の主固有ベクトルｕ（Ａｋ）２０２のｋ個の要素で置き換え、そのベクトルｘの全ての他の要素を０に設定して、実用的な組み合わせ最適化問題に対する最大化された最終解ベクトルｘ（＾）１０４を求める。
【００３０】
貪欲探索解
図３は、スパースＰＣＡ最適化問題に対する貪欲解のステップ３００を示す。その方法への入力は、共分散行列Ａ１０３およびスパーシティパラメータｋ１０２である。ネストされた順方向探索４００および逆方向探索５００を適用して、候補解（複数可）１０１’〜１０１’’が得られる。その後、これら２つの候補解から、分散（最大固有値）が大きい方の解が、出力のスパース固有ベクトル（最終解ベクトル）ｘ（＾）１０４として選択される（３１０）。
【００３１】
順方向探索および逆方向探索
図４は、順方向探索４００のステップを示す。この探索では、候補解のリストは、最初に空であり、「最良の」、または最も大きな最大分散を有する要素が、値ｋまで１つずつ追加される。対応する逆方向探索５００は、図５に示すように、完全な候補リストで開始し、要素が１つずつ削除される。
【００３２】
厳密な最適解
図６は、スパースＰＣＡ問題に対する厳密解を得るための仕組み５００を示す。最初に、双方向貪欲法３００が、先に説明されたように、共分散行列１０３および所望のスパーシティパラメータｋ１０２を与えられる。貪欲探索３００の近似解は、後述する式（４）に関して後にさらに詳細に説明されるように、共分散行列１０３および固有値範囲６１１を用いて、分岐限定組み合わせ探索（６１０）アルゴリズムとともに後に用いるための初期の上限としてその分散を有する、初期の候補解ｘ０１０１を与える。その際、分岐限定アルゴリズム６１０は、そのアルゴリズムが終了するときに、厳密な最適解ｘ＊６０１を見つけることを保証される。
【００３３】
ここで、本発明の実施の形態について、明示的にさらに詳細に説明する。
【００３４】
スパースＰＣＡ定式化
一般的に、スパース主成分分析（ＰＣＡ）は、基数制約二次計画（ＱＰ）として定式化することができる。対称な正定値共分散行列Ａ∈Ｓ＋ｎ１０３が与えられるとき、ｋ＜ｎ個以下の０でない主成分を有するスパース測定ベクトルｘ∈Ｒｎの分散の二次形式ｘ’Ａｘが最大にされる。
【００３５】
【数１】
【００３６】
ただし、基数ｃａｒｄ（ｘ）＝‖ｘ‖０は、Ｌ０−ノルムの中にある。この最適化問題は、非凸で、ＮＰ困難であり、それゆえ手に負えない。
【００３７】
本発明は、最適なベクトルｘ（＾）１０４を求め、その後、従来の数値ルーチンを用いる共分散行列Ａの再帰的分解を用いて、スパース固有ベクトルが得られる。
【００３８】
その分解では、固有ベクトルのスパースネスが、スパーシティパラメータｋ１０２の値によって制御される。ｋの値が異なる場合、主成分も異なる。しかしながら、特に、主成分が多数の場合に、値ｋを設定するための指針はなく、それらの相互作用、たとえば、非直交基底が起こり得る。
【００３９】
したがって、従来のＰＣＡとは異なり、スパースな分解は、唯一の解を与えない。実際には、数多くの異なる解を取り得る。それゆえ、本発明の１つの実施の形態は、スパーシティパラメータｋの選択を「導く」。結果として、本発明によれば、最適なスパース固有ベクトルを求めることができる。
【００４０】
基数制約を用いない場合、式（１）のＱＰ最適化は、以下の分析範囲を有し、対応する唯一の固有ベクトル解を有するレイリー−リッツ商である。
【００４１】
【数２】
【００４２】
その場合に、最適な目標値または分散は、まさに、主固有ベクトルｘ（＾）＝ｕｎを用いる最大固有値λｎ（Ａ）である。全ての（λｉ，ｕｉ）のランクは、昇順である。それゆえ、λｍｉｎ＝λ１およびλｍａｘ＝λｎである。しかしながら、非線形基数制約の追加は、ｋ＜ｎの場合に、最適な目標値が厳密にλｍａｘ（Ａ）未満であり、従来技術の場合のように、主固有ベクトルがもはや、最適化問題の解に不可欠ではない。代わりに、それは、最適解ｘ（＾）１０４を得るために用いられる共分散行列Ａ１０３の固有値のスペクトルである。
【００４３】
最適性条件
式（１）を最適化するための計算方法を定式化する際に、最適解がわかっているものと仮定して、適合しなければならない条件を最初に考える。基数ｋを有する単位ノルムベクトルｘ（＾）が、最大目標値ｖ＊を生成する。すなわち、最終解ベクトルｘ（＾）は、スパーシティパラメータｋに局所的に最適である分散最大化ｋ−スパース固有ベクトルである。
【００４４】
ｚ∈Ｒｋの場合に、これは、ｘ’（＾）Ａｘ（＾）＝ｚ’Ａｋｚが、ベクトルｘ（＾）と同じｋ個の０でない主成分を含むことを意味する。部分行列Ａｋ２０１は、共分散行列Ａ１０３のｋ×ｋ主部分行列である。部分行列Ａｋは、順方向探索および逆方向探索を用いて、ベクトルｘ（＾）のゼロインデックスに対応する行および列を削除することによって、または同じく、０でないインデックスの行および列を追加することによって得られる。ベクトルｘ（＾）と同様に、ｋ−ベクトルｚは、単位ノルムであり、ｚ’Ａｋｚは、標準的な制約のないレイリー−リッツ商に等価である。下位問題の最大分散は、λｍａｘ（Ａｋ）であり、それは、最適な目標値ｖ＊である。これは、以下の命題によって要約することできる。
【００４５】
命題１
式（１）によって表されるスパースＰＣＡ最適化問題の最適値ｖ＊は、λｍａｘ（Ａ＊ｋ）に等しい。ただし、Ａ＊ｋは、最も大きな最大固有値を有する、共分散行列Ａのｋ×ｋ主部分行列である。詳細には、最適なスパースベクトルｘ（＾）の０でない主成分は、ｕ＊ｋの主成分に厳密に等しく、それは、部分行列Ａ＊ｋの主固有ベクトルを構成する。
【００４６】
この命題は、スパースＰＣＡ、および同等の部類の基数制約最適化問題の組み合わせの性質を明示する。しかしながら、特に、そのような簡単な行列項の場合に、スパース固有ベクトルのこの厳密な定義、および最適性のための必要十分条件は、組み合わせＣ（ｎ，ｋ）の指数関数的増加に起因し、主部分行列Ａ＊ｋを実際に求めるための効率的な方法を提供しない。しかしながら、ｎが比較的小さく、たとえば、約３０未満であり、最適性が保証されているときには、網羅的な探索が実用的である。それゆえ、実用科学および金融分野において示される数多くの実際のデータセットの場合には、最適化問題を強引に解くことができる。
【００４７】
変分再正規化
さらに、命題１は、命題２によって表されるように、従来の連続的なＰＣＡ法、たとえば、d'Aspremont他、Jolliffe他およびZou他の方法によって得られるスパースな主成分を改善するためのかなり簡単で、非常に効率的な、計算による「解決法」を提供する。
【００４８】
命題２
基数ｋを有する単位ノルムベクトルｘ（〜）が任意の既知の近似技法によって求められる候補主成分を含む（ここで、ｘ（〜）は、ｘの上に〜がついたものを表す）。ｘ（〜）の０でない部分ベクトルはｚ（〜）である。部分行列Ａｋの最大主固有ベクトルは、ｕｋであり、ｕｋは、ベクトルｘ（〜）の同じ０でないインデックスによって定義される。
【００４９】
ｚ（〜）≠ｕｋ（Ａｋ）である場合には、ｘ（〜）は、次善最適解である。ｘ（〜）の０でない主成分を主固有ベクトルｕｋの０でない主成分で置き換えることによって、分散がｖ（〜）からλｋ（Ａｋ）まで増加することが保証される。この変分再正規化２００は、任意の従来のＰＣＡ法を用いて、近似的なスパースな主成分、すなわち候補解１０１を求めることができ、その後、より簡単で、かつ容易な制約のない問題、すなわち部分行列Ａｋの固有分解を解くことができることを示す。この手順、すなわち「解決法」は、近似的な主成分の品質を低下させること、または分散を小さくすることは決してない。実際には、大体の場合に、解の品質は改善される。
【００５０】
詳細には、「簡単な閾値処理」の従来技術の方法の場合、従来の（スパースでない）主固有ベクトルは、ｕｎ（Ａ）の最も小さな絶対値負荷の（ｎ−ｋ）を０に設定し、その後、単位ノルムベクトルのために適した再正規化を適用することによって、単に閾値処理される。残念なことに、そのような簡単なベクトル再正規化（または等価な連続近似）は、０でない要素によって指示される部分空間（部分集合）内であっても、最適解を生成するためにほとんど当てにすることはできない。こうして、大部分の従来のスパースＰＣＡ法は、本明細書において記述される適当な再正規化によって容易に改善することができる。
【００５１】
変分固有値範囲
式（１）から得ることができる目標値ｖ＊は、レイリー−リッツ定理によって、スペクトル半径λｍａｘ（Ａ）によって範囲を定められることを思い起こされたい。さらに、共分散行列Ａの主部分行列のスペクトルは、ある程度、最適解を定義する。驚くほどのことではないが、２つの固有値スペクトルは、ポアンカレ包含原理（inclusion principle）として知られている不等式によって関連付けられる。
【００５２】
定理１：包含原理
Ａを、スペクトルλ（Ａ）を有する対称ｎ×ｎ行列とする。Ａｋを、固有値λｉ（Ａｋ）を有する、１≦ｋ≦ｎの場合の行列Ａの任意のｋ×ｋ主部分行列とする。ここで、各整数ｉは、１≦ｉ≦ｋであり、下式（２）の関係が成り立つ。
【００５３】
【数３】
【００５４】
この定理は、クーラント−フィッシャー「最小−最大」定理の変分不等式において、基数ｋのスパーシティパターンを付加的な直交性制約として課すことによって証明することができる。たとえば、J. H. Wilkinson著「The Algebraic Eigenvalue Problem」（Clarendon Press, Oxford, England, 1965）を参照願いたい。
【００５５】
それゆえ、対称行列の固有値は、その全ての部分行列の固有値６１２のための上限および下限６１１を形成する。ｋ＝ｎ−１である式（２）の特殊な場合には、下式（３）のように、対称行列のよく知られている固有値「飛越し特性（interlacing property）」が導かれる。
【００５６】
【数４】
【００５７】
すなわち、ＡｎおよびＡｎ−１のスペクトルは、交互に存在し、より大きな行列の固有値は、より小さな行列の固有値を包含する。
【００５８】
正定値対称共分散行列の場合、新たな変数を追加することによって、行列ＡｍからＡｍ＋１に拡大すると、λｍｉｎを減少させて、λｍａｘを増加させることによって、スペクトル範囲が必ず拡張される。こうして、固有値最大化の場合、式（１）の不等式制約ｃａｒｄ（ｘ）≦ｋが、最適時には等式になる。
【００５９】
それゆえ、基数のために指定された上限ｋにおいて、最大分散が達成される。さらに、関数ｖ＊（ｋ）は、所与の基数の場合の最適な分散を表す。その関数は、下式に示すある範囲にわたって単調に増加する。
【００６０】
【数５】
【００６１】
ただし、σ２ｍａｘは、行列Ａ内の最大対角分散である。実際には、スパースＰＣＡ法の動作を視覚化し、比較するための簡単で有益な方法は、それらの個々の分散曲線ｖ（〜）（ｋ）をプロットし、その曲線を最適な分散ｖ＊（ｋ）と比較することである。たとえば、図７を参照願いたい。
【００６２】
分散を最大にするので、式（２）において、ｉ＝ｋを設定することによって、関連する包含範囲６１１が得られる。これにより、以式（４）の場合の下限および上限がもたらされる。
【００６３】
【数６】
【００６４】
意外にも、行列Ａのｋ番目の最も小さな固有値は、基数ｋで得られる分散の場合の下限である。したがって、その下限によって、ｋの最適な値を選択できるようになる。また、従来のＰＣＡ法において、次元削減のための固有ベクトルの選択を導いた、行列Ａのスペクトルを用いて、スパースＰＣＡ法のための基数ｋを選択し、所望の最小分散が確実に得られるようにすることもできる。さらに、分岐限定過程を迅速化するために、また、種々の解の品質を従来の動作指標と比較するために、以式のように、下限λｋ（Ａ）を用いることができる。
【００６５】
【数７】
【００６６】
式（４）は、基数に関係なく、λｍａｘ（Ａ）において上限を定義し、それは、全ての分岐限定下位問題において、たとえば、べき乗法で求めることができる。式（４）は、λｍａｘ（Ａ）＝１のように共分散をあらかじめ正規化するために、または別法では、本発明の分散曲線ｖ（〜）／λｍａｘ（Ａ）を正規化するために用いることもできる。実際には、飛越し特性の結果として、この範囲に関連する興味深い関係が生じる。単一のｊ番目の行および列Ａ＼ｊを削除することによって得られる、Ａｎのｎ個の取り得る（ｎ−１）×（ｎ−１）主部分行列の中に、その最大固有値がλｎ（Ａ）の（ｎ−１）／ｎ以上である少なくとも１つの部分行列が、下式（５）に示されるように、存在する。
【００６７】
【数８】
【００６８】
分岐限定探索過程の場合のこの不等式の意味は、特に大きなｎの場合において、共分散行列Ａの全ての主部分行列のスペクトル半径（λｍａｘ）を恣意的に小さくできないことである。それゆえ、適度に高い基数において、λｎ（Ａ）の概ね全てが獲得される。この事実は、ｋが大きくなるのに応じて、下限λｋ（Ａ）が増加することによって裏付けられる。
【００６９】
組み合わせ探索アルゴリズム
命題１および２、包含原理および飛越し特性に基づいて、そして、特に分散曲線ｖ（ｋ）の単調性が与えられるとき、本明細書において記述されるようなスパースな主成分を求めるために、一般的な部類の整数計画（ＩＰ）最適化技法を用いることができる。
【００７０】
実際には、逆方向削除５００のような貪欲探索過程が、式（５）の範囲によって指示される。完全なインデックス集合Ｉ＝｛１，２，．．．，ｎ｝で開始し、その後、ｋ個の主成分だけが残るまで、最大のλｍａｘ（Ａ＼ｊ）を生成する変数ｊを順次削除することができる。小さな基数ｋ≪ｎの場合、逆方向探索の計算コストは、最大の複雑さＯ（ｎ４）まで増加する可能性がある。
【００７１】
それゆえ、順方向選択４００を実行することもできる。ゼロインデックス集合Ｉ＝｛｝で開始し、その後、ｋ個の主成分が選択されるまで、最大のλｍａｘ（Ａ＋ｊ）を生成する変数ｊを順次追加することができる。順方向貪欲探索は、Ｏ（ｎ３）未満の最悪時の複雑さを有する。順方向探索および逆方向探索を組み合わせて、双方向貪欲探索３００にすることができる。１からｎまで貪欲順方向パスを実行し、その後、ｎから１まで個別に逆方向探索を実行して、ｋ毎に最良の解を選択する。この双方向貪欲探索は、非常に有効である。
【００７２】
貪欲探索は、概ね最適であり、好都合ではあるが、特に、スパースＰＣＡ問題が金融または工学の応用分野の中にあり、最適性のギャップが小さい場合であっても、時間とともに大きな損失を生じる可能性がある場合には、やはり最適解を求める方法を使うだけの価値がある。
【００７３】
本発明の分岐限定探索６１０は、計算上効率の良い範囲、具体的には式（４）の上限を利用する。この範囲は、縦型探索のためのＦＩＦＯキューにおいて直面している全ての下位問題において用いられる。より効率的な最良優先探索のために、式（４）の下限を用いて、キューを分類することができる。それゆえ、この厳密なスパースＰＣＡ探索過程は、それが終了するときに、最適解を見つけるであろう。必然的に、分岐限定の場合、探索時間は、初期の候補主成分の分散の品質によって決まる。その品質が、通常、極めて高いので、本発明の双方向貪欲探索によって得られる解を用いて、厳密な探索を初期化することができる。
【００７４】
スパースＰＣＡのための全体として最もよい探索方法は、最初に双方向貪欲探索３００を実行し、その結果を用いて、厳密かつ最適解６０１を求めるための分岐限定探索６１０を初期化することである。
【００７５】
発明の効果
本発明の実施の形態は、変分固有値範囲を用いて、スパース主成分分析の離散スペクトル定式化を提供する。さらに、本方法は、任意の他の近似技法（式（１）の最適化における基数制約および／またはランク制約の連続緩和または凸緩和等）によって得られる任意のスパース固有ベクトルを再正規化し、それにより、獲得された分散を大きくすることによってその品質を改善することができる。さらに、貪欲探索手順および厳密分岐限定探索手順の両方を用いてスパースな主成分を得るための効率的な探索アルゴリズムが提供される。
【図面の簡単な説明】
【００７６】
【図１】本発明の１つの実施の形態による組み合わせ最適化問題に対する最大化された解のブロック図である。
【図２】本発明の１つの実施の形態による変分正規化手順のブロック図である。
【図３】本発明の１つの実施の形態による組み合わせ最適化問題に対する貪欲解のブロック図である。
【図４】本発明の１つの実施の形態による貪欲解のための順方向探索のブロック図である。
【図５】本発明の１つの実施の形態による貪欲解のための逆方向探索のブロック図である。
【図６】本発明の１つの実施の形態による組み合わせ最適化問題に対する厳密解のブロック図である。
【図７】本発明の複数の実施の形態による分散を比較するグラフである。
【技術分野】
【０００１】
本発明は、包括的には主成分分析（ＰＣＡ：Ｐｒｉｎｃｉｐａｌ Ｃｏｍｐｏｎｅｎｔ Ａｎａｌｙｓｉｓ）に関し、より詳細には、顔認識および金融資産管理のような実用的な応用形態にスパース主成分分析を適用することに関する。
【背景技術】
【０００２】
主成分分析（ＰＣＡ）は、よく知られている多変量統計分析技法である。ＰＣＡは、データ分析および次元削減のために頻繁に用いられる。ＰＣＡは、科学、工学および金融の至るところで応用形態を有する。
【０００３】
ＰＣＡは、データにおいて、最大分散を獲得する入力変数の一次結合を求める。典型的には、ＰＣＡは、データ行列の特異値分解（ＳＶＤ）を用いて実行される。別法として、共分散行列が用いられる場合には、固有値分解を適用することができる。ＰＣＡは、情報の損失を最小限に抑えたデータ圧縮を提供する。さらに、主成分は、無相関である。これは、データ分析を容易にする。
【０００４】
残念なことに、ＰＣＡは、通常、全てのデータの０でない一次結合、すなわち「負荷」を伴う。しかしながら、生命情報科学、計算機生物学、コンピュータビジョン、金融資産管理、並びに地球物理学的データ、遺伝学的データおよび医療データの分析のような、多くの実用的な応用形態の場合に、座標軸は、物理的な意味を有する。それゆえ、０でない負荷の数を削減することが好都合であろう。これは、低次元であるが、それでもデータ内の分散を特徴付ける「スパースな（まばらな）」主成分を提供するであろう。
【０００５】
スパースなデータ表現は、人間が理解するのを助け、計算コストを削減し、学習モデルにおいて、より良好な一般化を与えるので、一般的に望ましい。
【０００６】
金融ポートフォリオ最適化、および地理空間統計学における資源配分等の応用形態の場合、スパースネスは、多くの場合に、空間／時間および材料費が投資または測定単位の数を制約する可能性があるか否かの判定基準を定義する鍵である。機械学習では、入力データのスパースネスは、特徴選択および自動適合性判定に関連付けられる。
【０００７】
従来のスパースＰＣＡは、典型的には、軸回転および成分閾値処理等の簡単な変換を適用する。J. CadimaおよびI. Jolliffe著「Loadings and correlations in the interpretation of principal components」（Applied Statistics, vol. 22, pp. 203-214, 1995）を参照願いたい。基本的に、根底にある目標は、多くの場合に主変数の特定および分析に基づいて、回帰分析のための特徴の部分集合を選択することである。G. McCabe著「Principal Variables」（Technometrics, vol. 26, pp. 137-144, 1984）を参照願いたい。
【０００８】
最初の確実な計算方法、すなわち、ＳＣｏＴＬＡＳＳは、適当な最適化フレームワークを提供する。しかしながら、その方法は、計算上、実用的ではない。I. JolliffeおよびM. Uddin著「A modified principal component technique based on the Lasso」（Journal of Computational and Graphical Statistics, vol. 12, pp. 531-547, 2003）を参照願いたい。
【０００９】
別の方法は、従来の主成分に関して、Ｌ１−罰則付き回帰を用いるＥｌａｓｔｉｃＮｅｔ定式化を用いる。H. Zou、T. HastieおよびR. Tibshirani著「Sparse principal component analysis」（Journal of Computational and Graphical Statistics）（掲載予定）を参照願いたい。
【００１０】
別の方法は、スパースＰＣＡに関連する問題、すなわち、非凸性の高い目的関数を認識している。A. d'Aspremont、L. El Ghaoui、M. I. JordanおよびG. R. G. Lanckriet著「A direct formulation for sparse PCA using semi-definite programming」（Advances in Neural Information Processing Systems (NIPS), December 2004）を参照願いたい。その方法は、半正定値計画（ＳＤＰ：Ｓｅｍｉ−Ｄｅｆｉｎｉｔｅ Ｐｒｏｇｒａｍｍｉｎｇ）を用いて凸近似を求めることにより、厳しい基数制約を緩和する。
【発明の開示】
【発明が解決しようとする課題】
【００１１】
データのスパース主成分分析（ＰＣＡ）が、スパース固有ベクトルの基底を求める。スパース固有ベクトルの射影が、そのデータの最大分散を表す。スパースＰＣＡは、特定の部類のＮＰ困難で、基数制約の、非凸最適化問題に属する。スパースＰＣＡは、生命情報科学から金融工学およびコンピュータビジョンに及ぶ広範な応用形態のために用いることができる。
【００１２】
従来のスパースＰＣＡは、典型的には、連続的な近似および凸緩和を用いて、スパースな主成分を求める。
【００１３】
本発明は、新規のスパースＰＣＡ法を提供する。本方法は、変分固有値範囲に基づく離散的な定式化を用いる。本方法は、最適なスパースな主成分を求める。本方法は、近似的な貪欲探索過程および厳密分岐限定（探索過程を用いることができる。
【００１４】
さらに、任意のＰＣＡ法によって得られた近似的な候補解を改善するために、離散スペクトル定式化を用いる簡単な後処理再正規化ステップを適用することができる。
【課題を解決するための手段】
【００１５】
本発明の１つの実施の形態では、コンピュータによって実施される方法が、スパース主成分分析の基数制約組み合わせ最適化問題に対する候補解を最大にする。
【００１６】
複数の要素からなる候補解ベクトルｘが、その候補解ベクトルｘのそれぞれ取り得る要素対間の共分散を示す共分散行列Ａとともに与えられる。その候補解は、貪欲探索を用いて求めることができる。最終解の基数を表すスパーシティパラメータｋも自動的に与えられるか、または求められる。
【００１７】
その後、共分散行列Ａおよびスパーシティパラメータｋに関して候補解ベクトルｘのための変分再正規化を実行して、スパーシティパラメータｋに局所的に最適であり、かつスパース主成分分析最適化問題に対する最終解である、以下の分散最大化ｋ−スパース固有ベクトルｘ（＾）が得られる（ここで、ｘ（＾）は、ｘの上に＾がついたものを表す）。
【発明を実施するための最良の形態】
【００１８】
本発明の１つの実施の形態は、スペクトル範囲を用いて、データに対してスパース主成分分析を実行するための方法を提供する。スパースＰＣＡを用いて、実用的な組み合わせ最適化問題に対する解を求めることができる。
【００１９】
従来技術とは対照的に、本発明は、変分固有値範囲に基づく離散的な定式化を用いる。本方法は、近似解の場合には貪欲探索を、厳密解の場合には分岐限定探索を用いて、最適なスパースな主成分を求める。
【００２０】
たとえば、本方法は、以下の実用的な株式ポートフォリオ最適化問題を最適に解くために用いることができる。スタンダード＆プアーズ株価指数に掲載される５００銘柄のような、入手可能な株式の実質的に大きなプールから選定された１０銘柄ｘに投資することが望ましい。入力５００×５００共分散行列Ａは、５００銘柄の各対間のリスク／リターン実績における共分散を示す。最終解ベクトルｘ（＾）内に０でない１０個の要素だけが存在するという制約を前提として、ｘＴＡｘ／ｘＴｘが最大にされるような、配分の５００次元ベクトルｘ（＾）を見つけることが望ましい。
【００２１】
これは基本的には、２つの問題、すなわち最良の１０銘柄の株式を選定するという問題、および選択された株式の中で資金を配分するという問題に分解することができる。第２の問題は、第１の問題よりも解くのが容易である。第２の問題に対する解または「解決法」は、以下のとおりである。１０銘柄の株式が既に選定されているものと仮定する。その際、以下に記述される命題１に従って、最良の資金配分方式が、これらの１０銘柄の株式に対応する共分散行列Ａの行／列を抽出し、主要または主固有ベクトル、すなわち、最大固有値または分散に対応する固有ベクトルを求める。これは、候補解のための最良の局所解であることが保証される。ただし、「局所」は、同じ１０銘柄の株式を用いる全ての取り得る配分の中にあることを意味する。
【００２２】
これは簡単な解のように見えるかもしれないが、従来技術は、これまで、ここで示した目新しいやり方で、この問題を取り扱ったことがない。言い換えると、人々は、上記の２つの問題を一緒に取り扱っており、それゆえ、１０銘柄の株式のリストと同時に、各株式に配分される資金を見つけ出した。彼らは、１０銘柄の株式のリストを得た後に、主要固有ベクトルを用いて、選択された株式の中で資金を配分することへの最適解を求めるべきであることを理解していなかった。
【００２３】
第１の問題は、解くのがはるかに難しい。実際には、この問題は、ＮＰ困難として知られている問題である。これは、この問題の複雑さが、多項式時間における非決定性チューリング機械によって解くことができる問題よりも本質的に難解であることを意味する。組み合わせ最適化問題の決定性のものがＮＰ完全問題の部類に属するとき、最適化するものはＮＰ困難である。
【００２４】
それゆえ、その解は、以下のように特徴付けられる。株式の候補リストを与えられるとき、その最大値は、Ａの対応する部分行列の固有値によって範囲を定められることがわかっている。株式銘柄Ａ、Ｂ、Ｃが選定される場合には、Ａから３×３行列が生成され、その最大固有値が求められる。これが最大値になるであろう。さらに、１０銘柄の株式のリストがＡの対応する１０×１０部分行列の主要固有値によって上限を定められる場合には、これらの１０銘柄の株式の任意の部分集合が、その１０×１０部分行列の主要固有値によって同様に上限を定められる。
【００２５】
分岐限定探索において、これら２つの観測値の組み合わせが用いられ、全体的に最適な厳密解を見つけることが保証される。局所的に次善最適な貪欲探索は、その探索が終了するまで、株式を１つずつ追加（または削除）する。
【００２６】
コンピュータビジョンの応用形態では、同じ技法を用いて、１つの画像内で処理すべきピクセルの部分集合を求めることができる。たとえば、顔認識の応用形態では、計算資源およびメモリ資源が限られている。それゆえ、画像内の顔の突出部に対応するピクセルだけを処理することが理にかなっている。
【００２７】
最大化された解
ここで、図１を用いて、実用的な組み合わせ最適化問題に対する事前に得られた候補解１０１を改善するための方法１００を説明する。その方法への入力は、その問題の候補解である要素からなるデータベクトルｘ１０１、共分散行列Ａ１０３、およびスパーシティパラメータｋ１０２である。スパーシティパラメータｋは、その問題の最終解ベクトルｘ（＾）１０４内の０でない要素または「基数」の最大数を表す。
【００２８】
たとえば、データベクトルｘ内の要素は、４つの入手可能な株式または資産グループ内のスパースな投資に対応する。共分散行列Ａは、これら４つの資産の中のそれぞれ入手可能な要素対のリスク／リターン共分散を示す。株式および指標は、任意の既知の方法を用いて求めることができる。ここで、スパーシティパラメータｋは、２に設定される。言い換えると、最良の金融リターンを得るために、資金は、４つの資産のうちの２つだけに配分されることになる。
【００２９】
それらの入力に従って、変分再正規化２００が実行され、最大化された解ベクトルｘ（＾）１０４が求められる。図２に示されるように、変分再正規化２００は、入力データベクトルｘ１０１の最も大きなｋ個の要素１０２または「負荷」を、入力行列Ａ１０３の行および列から抽出される、対応するｋ×ｋ主部分行列Ａｋ２０１の主固有ベクトルｕ（Ａｋ）２０２のｋ個の要素で置き換え、そのベクトルｘの全ての他の要素を０に設定して、実用的な組み合わせ最適化問題に対する最大化された最終解ベクトルｘ（＾）１０４を求める。
【００３０】
貪欲探索解
図３は、スパースＰＣＡ最適化問題に対する貪欲解のステップ３００を示す。その方法への入力は、共分散行列Ａ１０３およびスパーシティパラメータｋ１０２である。ネストされた順方向探索４００および逆方向探索５００を適用して、候補解（複数可）１０１’〜１０１’’が得られる。その後、これら２つの候補解から、分散（最大固有値）が大きい方の解が、出力のスパース固有ベクトル（最終解ベクトル）ｘ（＾）１０４として選択される（３１０）。
【００３１】
順方向探索および逆方向探索
図４は、順方向探索４００のステップを示す。この探索では、候補解のリストは、最初に空であり、「最良の」、または最も大きな最大分散を有する要素が、値ｋまで１つずつ追加される。対応する逆方向探索５００は、図５に示すように、完全な候補リストで開始し、要素が１つずつ削除される。
【００３２】
厳密な最適解
図６は、スパースＰＣＡ問題に対する厳密解を得るための仕組み５００を示す。最初に、双方向貪欲法３００が、先に説明されたように、共分散行列１０３および所望のスパーシティパラメータｋ１０２を与えられる。貪欲探索３００の近似解は、後述する式（４）に関して後にさらに詳細に説明されるように、共分散行列１０３および固有値範囲６１１を用いて、分岐限定組み合わせ探索（６１０）アルゴリズムとともに後に用いるための初期の上限としてその分散を有する、初期の候補解ｘ０１０１を与える。その際、分岐限定アルゴリズム６１０は、そのアルゴリズムが終了するときに、厳密な最適解ｘ＊６０１を見つけることを保証される。
【００３３】
ここで、本発明の実施の形態について、明示的にさらに詳細に説明する。
【００３４】
スパースＰＣＡ定式化
一般的に、スパース主成分分析（ＰＣＡ）は、基数制約二次計画（ＱＰ）として定式化することができる。対称な正定値共分散行列Ａ∈Ｓ＋ｎ１０３が与えられるとき、ｋ＜ｎ個以下の０でない主成分を有するスパース測定ベクトルｘ∈Ｒｎの分散の二次形式ｘ’Ａｘが最大にされる。
【００３５】
【数１】
【００３６】
ただし、基数ｃａｒｄ（ｘ）＝‖ｘ‖０は、Ｌ０−ノルムの中にある。この最適化問題は、非凸で、ＮＰ困難であり、それゆえ手に負えない。
【００３７】
本発明は、最適なベクトルｘ（＾）１０４を求め、その後、従来の数値ルーチンを用いる共分散行列Ａの再帰的分解を用いて、スパース固有ベクトルが得られる。
【００３８】
その分解では、固有ベクトルのスパースネスが、スパーシティパラメータｋ１０２の値によって制御される。ｋの値が異なる場合、主成分も異なる。しかしながら、特に、主成分が多数の場合に、値ｋを設定するための指針はなく、それらの相互作用、たとえば、非直交基底が起こり得る。
【００３９】
したがって、従来のＰＣＡとは異なり、スパースな分解は、唯一の解を与えない。実際には、数多くの異なる解を取り得る。それゆえ、本発明の１つの実施の形態は、スパーシティパラメータｋの選択を「導く」。結果として、本発明によれば、最適なスパース固有ベクトルを求めることができる。
【００４０】
基数制約を用いない場合、式（１）のＱＰ最適化は、以下の分析範囲を有し、対応する唯一の固有ベクトル解を有するレイリー−リッツ商である。
【００４１】
【数２】
【００４２】
その場合に、最適な目標値または分散は、まさに、主固有ベクトルｘ（＾）＝ｕｎを用いる最大固有値λｎ（Ａ）である。全ての（λｉ，ｕｉ）のランクは、昇順である。それゆえ、λｍｉｎ＝λ１およびλｍａｘ＝λｎである。しかしながら、非線形基数制約の追加は、ｋ＜ｎの場合に、最適な目標値が厳密にλｍａｘ（Ａ）未満であり、従来技術の場合のように、主固有ベクトルがもはや、最適化問題の解に不可欠ではない。代わりに、それは、最適解ｘ（＾）１０４を得るために用いられる共分散行列Ａ１０３の固有値のスペクトルである。
【００４３】
最適性条件
式（１）を最適化するための計算方法を定式化する際に、最適解がわかっているものと仮定して、適合しなければならない条件を最初に考える。基数ｋを有する単位ノルムベクトルｘ（＾）が、最大目標値ｖ＊を生成する。すなわち、最終解ベクトルｘ（＾）は、スパーシティパラメータｋに局所的に最適である分散最大化ｋ−スパース固有ベクトルである。
【００４４】
ｚ∈Ｒｋの場合に、これは、ｘ’（＾）Ａｘ（＾）＝ｚ’Ａｋｚが、ベクトルｘ（＾）と同じｋ個の０でない主成分を含むことを意味する。部分行列Ａｋ２０１は、共分散行列Ａ１０３のｋ×ｋ主部分行列である。部分行列Ａｋは、順方向探索および逆方向探索を用いて、ベクトルｘ（＾）のゼロインデックスに対応する行および列を削除することによって、または同じく、０でないインデックスの行および列を追加することによって得られる。ベクトルｘ（＾）と同様に、ｋ−ベクトルｚは、単位ノルムであり、ｚ’Ａｋｚは、標準的な制約のないレイリー−リッツ商に等価である。下位問題の最大分散は、λｍａｘ（Ａｋ）であり、それは、最適な目標値ｖ＊である。これは、以下の命題によって要約することできる。
【００４５】
命題１
式（１）によって表されるスパースＰＣＡ最適化問題の最適値ｖ＊は、λｍａｘ（Ａ＊ｋ）に等しい。ただし、Ａ＊ｋは、最も大きな最大固有値を有する、共分散行列Ａのｋ×ｋ主部分行列である。詳細には、最適なスパースベクトルｘ（＾）の０でない主成分は、ｕ＊ｋの主成分に厳密に等しく、それは、部分行列Ａ＊ｋの主固有ベクトルを構成する。
【００４６】
この命題は、スパースＰＣＡ、および同等の部類の基数制約最適化問題の組み合わせの性質を明示する。しかしながら、特に、そのような簡単な行列項の場合に、スパース固有ベクトルのこの厳密な定義、および最適性のための必要十分条件は、組み合わせＣ（ｎ，ｋ）の指数関数的増加に起因し、主部分行列Ａ＊ｋを実際に求めるための効率的な方法を提供しない。しかしながら、ｎが比較的小さく、たとえば、約３０未満であり、最適性が保証されているときには、網羅的な探索が実用的である。それゆえ、実用科学および金融分野において示される数多くの実際のデータセットの場合には、最適化問題を強引に解くことができる。
【００４７】
変分再正規化
さらに、命題１は、命題２によって表されるように、従来の連続的なＰＣＡ法、たとえば、d'Aspremont他、Jolliffe他およびZou他の方法によって得られるスパースな主成分を改善するためのかなり簡単で、非常に効率的な、計算による「解決法」を提供する。
【００４８】
命題２
基数ｋを有する単位ノルムベクトルｘ（〜）が任意の既知の近似技法によって求められる候補主成分を含む（ここで、ｘ（〜）は、ｘの上に〜がついたものを表す）。ｘ（〜）の０でない部分ベクトルはｚ（〜）である。部分行列Ａｋの最大主固有ベクトルは、ｕｋであり、ｕｋは、ベクトルｘ（〜）の同じ０でないインデックスによって定義される。
【００４９】
ｚ（〜）≠ｕｋ（Ａｋ）である場合には、ｘ（〜）は、次善最適解である。ｘ（〜）の０でない主成分を主固有ベクトルｕｋの０でない主成分で置き換えることによって、分散がｖ（〜）からλｋ（Ａｋ）まで増加することが保証される。この変分再正規化２００は、任意の従来のＰＣＡ法を用いて、近似的なスパースな主成分、すなわち候補解１０１を求めることができ、その後、より簡単で、かつ容易な制約のない問題、すなわち部分行列Ａｋの固有分解を解くことができることを示す。この手順、すなわち「解決法」は、近似的な主成分の品質を低下させること、または分散を小さくすることは決してない。実際には、大体の場合に、解の品質は改善される。
【００５０】
詳細には、「簡単な閾値処理」の従来技術の方法の場合、従来の（スパースでない）主固有ベクトルは、ｕｎ（Ａ）の最も小さな絶対値負荷の（ｎ−ｋ）を０に設定し、その後、単位ノルムベクトルのために適した再正規化を適用することによって、単に閾値処理される。残念なことに、そのような簡単なベクトル再正規化（または等価な連続近似）は、０でない要素によって指示される部分空間（部分集合）内であっても、最適解を生成するためにほとんど当てにすることはできない。こうして、大部分の従来のスパースＰＣＡ法は、本明細書において記述される適当な再正規化によって容易に改善することができる。
【００５１】
変分固有値範囲
式（１）から得ることができる目標値ｖ＊は、レイリー−リッツ定理によって、スペクトル半径λｍａｘ（Ａ）によって範囲を定められることを思い起こされたい。さらに、共分散行列Ａの主部分行列のスペクトルは、ある程度、最適解を定義する。驚くほどのことではないが、２つの固有値スペクトルは、ポアンカレ包含原理（inclusion principle）として知られている不等式によって関連付けられる。
【００５２】
定理１：包含原理
Ａを、スペクトルλ（Ａ）を有する対称ｎ×ｎ行列とする。Ａｋを、固有値λｉ（Ａｋ）を有する、１≦ｋ≦ｎの場合の行列Ａの任意のｋ×ｋ主部分行列とする。ここで、各整数ｉは、１≦ｉ≦ｋであり、下式（２）の関係が成り立つ。
【００５３】
【数３】
【００５４】
この定理は、クーラント−フィッシャー「最小−最大」定理の変分不等式において、基数ｋのスパーシティパターンを付加的な直交性制約として課すことによって証明することができる。たとえば、J. H. Wilkinson著「The Algebraic Eigenvalue Problem」（Clarendon Press, Oxford, England, 1965）を参照願いたい。
【００５５】
それゆえ、対称行列の固有値は、その全ての部分行列の固有値６１２のための上限および下限６１１を形成する。ｋ＝ｎ−１である式（２）の特殊な場合には、下式（３）のように、対称行列のよく知られている固有値「飛越し特性（interlacing property）」が導かれる。
【００５６】
【数４】
【００５７】
すなわち、ＡｎおよびＡｎ−１のスペクトルは、交互に存在し、より大きな行列の固有値は、より小さな行列の固有値を包含する。
【００５８】
正定値対称共分散行列の場合、新たな変数を追加することによって、行列ＡｍからＡｍ＋１に拡大すると、λｍｉｎを減少させて、λｍａｘを増加させることによって、スペクトル範囲が必ず拡張される。こうして、固有値最大化の場合、式（１）の不等式制約ｃａｒｄ（ｘ）≦ｋが、最適時には等式になる。
【００５９】
それゆえ、基数のために指定された上限ｋにおいて、最大分散が達成される。さらに、関数ｖ＊（ｋ）は、所与の基数の場合の最適な分散を表す。その関数は、下式に示すある範囲にわたって単調に増加する。
【００６０】
【数５】
【００６１】
ただし、σ２ｍａｘは、行列Ａ内の最大対角分散である。実際には、スパースＰＣＡ法の動作を視覚化し、比較するための簡単で有益な方法は、それらの個々の分散曲線ｖ（〜）（ｋ）をプロットし、その曲線を最適な分散ｖ＊（ｋ）と比較することである。たとえば、図７を参照願いたい。
【００６２】
分散を最大にするので、式（２）において、ｉ＝ｋを設定することによって、関連する包含範囲６１１が得られる。これにより、以式（４）の場合の下限および上限がもたらされる。
【００６３】
【数６】
【００６４】
意外にも、行列Ａのｋ番目の最も小さな固有値は、基数ｋで得られる分散の場合の下限である。したがって、その下限によって、ｋの最適な値を選択できるようになる。また、従来のＰＣＡ法において、次元削減のための固有ベクトルの選択を導いた、行列Ａのスペクトルを用いて、スパースＰＣＡ法のための基数ｋを選択し、所望の最小分散が確実に得られるようにすることもできる。さらに、分岐限定過程を迅速化するために、また、種々の解の品質を従来の動作指標と比較するために、以式のように、下限λｋ（Ａ）を用いることができる。
【００６５】
【数７】
【００６６】
式（４）は、基数に関係なく、λｍａｘ（Ａ）において上限を定義し、それは、全ての分岐限定下位問題において、たとえば、べき乗法で求めることができる。式（４）は、λｍａｘ（Ａ）＝１のように共分散をあらかじめ正規化するために、または別法では、本発明の分散曲線ｖ（〜）／λｍａｘ（Ａ）を正規化するために用いることもできる。実際には、飛越し特性の結果として、この範囲に関連する興味深い関係が生じる。単一のｊ番目の行および列Ａ＼ｊを削除することによって得られる、Ａｎのｎ個の取り得る（ｎ−１）×（ｎ−１）主部分行列の中に、その最大固有値がλｎ（Ａ）の（ｎ−１）／ｎ以上である少なくとも１つの部分行列が、下式（５）に示されるように、存在する。
【００６７】
【数８】
【００６８】
分岐限定探索過程の場合のこの不等式の意味は、特に大きなｎの場合において、共分散行列Ａの全ての主部分行列のスペクトル半径（λｍａｘ）を恣意的に小さくできないことである。それゆえ、適度に高い基数において、λｎ（Ａ）の概ね全てが獲得される。この事実は、ｋが大きくなるのに応じて、下限λｋ（Ａ）が増加することによって裏付けられる。
【００６９】
組み合わせ探索アルゴリズム
命題１および２、包含原理および飛越し特性に基づいて、そして、特に分散曲線ｖ（ｋ）の単調性が与えられるとき、本明細書において記述されるようなスパースな主成分を求めるために、一般的な部類の整数計画（ＩＰ）最適化技法を用いることができる。
【００７０】
実際には、逆方向削除５００のような貪欲探索過程が、式（５）の範囲によって指示される。完全なインデックス集合Ｉ＝｛１，２，．．．，ｎ｝で開始し、その後、ｋ個の主成分だけが残るまで、最大のλｍａｘ（Ａ＼ｊ）を生成する変数ｊを順次削除することができる。小さな基数ｋ≪ｎの場合、逆方向探索の計算コストは、最大の複雑さＯ（ｎ４）まで増加する可能性がある。
【００７１】
それゆえ、順方向選択４００を実行することもできる。ゼロインデックス集合Ｉ＝｛｝で開始し、その後、ｋ個の主成分が選択されるまで、最大のλｍａｘ（Ａ＋ｊ）を生成する変数ｊを順次追加することができる。順方向貪欲探索は、Ｏ（ｎ３）未満の最悪時の複雑さを有する。順方向探索および逆方向探索を組み合わせて、双方向貪欲探索３００にすることができる。１からｎまで貪欲順方向パスを実行し、その後、ｎから１まで個別に逆方向探索を実行して、ｋ毎に最良の解を選択する。この双方向貪欲探索は、非常に有効である。
【００７２】
貪欲探索は、概ね最適であり、好都合ではあるが、特に、スパースＰＣＡ問題が金融または工学の応用分野の中にあり、最適性のギャップが小さい場合であっても、時間とともに大きな損失を生じる可能性がある場合には、やはり最適解を求める方法を使うだけの価値がある。
【００７３】
本発明の分岐限定探索６１０は、計算上効率の良い範囲、具体的には式（４）の上限を利用する。この範囲は、縦型探索のためのＦＩＦＯキューにおいて直面している全ての下位問題において用いられる。より効率的な最良優先探索のために、式（４）の下限を用いて、キューを分類することができる。それゆえ、この厳密なスパースＰＣＡ探索過程は、それが終了するときに、最適解を見つけるであろう。必然的に、分岐限定の場合、探索時間は、初期の候補主成分の分散の品質によって決まる。その品質が、通常、極めて高いので、本発明の双方向貪欲探索によって得られる解を用いて、厳密な探索を初期化することができる。
【００７４】
スパースＰＣＡのための全体として最もよい探索方法は、最初に双方向貪欲探索３００を実行し、その結果を用いて、厳密かつ最適解６０１を求めるための分岐限定探索６１０を初期化することである。
【００７５】
発明の効果
本発明の実施の形態は、変分固有値範囲を用いて、スパース主成分分析の離散スペクトル定式化を提供する。さらに、本方法は、任意の他の近似技法（式（１）の最適化における基数制約および／またはランク制約の連続緩和または凸緩和等）によって得られる任意のスパース固有ベクトルを再正規化し、それにより、獲得された分散を大きくすることによってその品質を改善することができる。さらに、貪欲探索手順および厳密分岐限定探索手順の両方を用いてスパースな主成分を得るための効率的な探索アルゴリズムが提供される。
【図面の簡単な説明】
【００７６】
【図１】本発明の１つの実施の形態による組み合わせ最適化問題に対する最大化された解のブロック図である。
【図２】本発明の１つの実施の形態による変分正規化手順のブロック図である。
【図３】本発明の１つの実施の形態による組み合わせ最適化問題に対する貪欲解のブロック図である。
【図４】本発明の１つの実施の形態による貪欲解のための順方向探索のブロック図である。
【図５】本発明の１つの実施の形態による貪欲解のための逆方向探索のブロック図である。
【図６】本発明の１つの実施の形態による組み合わせ最適化問題に対する厳密解のブロック図である。
【図７】本発明の複数の実施の形態による分散を比較するグラフである。
【特許請求の範囲】
【請求項１】
スパース主成分分析の基数制約組み合わせ最適化問題に対する候補解を最大にするための、コンピュータによって実施される方法であって、
複数の要素からなる候補解ベクトルｘ、該候補解ベクトルｘのそれぞれ取り得る要素対間の共分散を示す共分散行列Ａ、および最終解の基数を表すスパーシティパラメータｋを入力するステップと、
該スパーシティパラメータｋに局所的に最適であり、かつ前記スパース主成分分析最適化問題に対する前記最終解である、分散最大化ｋ−スパース固有ベクトルｘ（＾）を得るために、前記共分散行列Ａおよび前記スパーシティパラメータｋに関して前記候補解ベクトルｘの変分再正規化を実行するステップと
を含むスパース主成分分析の基数制約組み合わせ最適化問題に対する候補解を最大にするための、コンピュータによって実施される方法。
【請求項２】
前記変分再正規化は、
前記候補解ベクトルｘの最も大きなｋ個の要素を、前記共分散行列Ａの対応するｋ×ｋ主部分行列Ａｋの主固有ベクトルｕ（Ａｋ）のｋ個の要素で置き換えることと、
前記分散最大化ｋ−スパース固有ベクトルｘ（＾）を得るために、前記候補解ベクトルｘの全ての他の要素を０に設定することと
をさらに含む請求項１に記載の方法。
【請求項３】
前記共分散行列Ａの行および列から前記ｋ×ｋ主部分行列Ａｋを抽出することをさらに含む請求項２に記載の方法。
【請求項４】
候補解を求めるために貪欲探索を実行することをさらに含む請求項１に記載の方法。
【請求項５】
前記貪欲探索は、順方向パスおよび独立した逆方向パスを含む双方向のネストされた探索を含み、
前記方法は、前記スパーシティパラメータｋのために個別に、前記順方向パスまたは前記逆方向パスのいずれかから、前記分散最大化ｋ−スパース固有ベクトルとして最良のスパース固有ベクトルを選択する
ことをさらに含む請求項４に記載の方法。
【請求項６】
前記分散最大化ｋ−スパース固有ベクトルｘ（＾）のｋ個の非ゼロ値は、主固有ベクトルｕ＊ｋのｋ個のエントリに厳密に等しく、該ｋ個のエントリは、前記ｋ×ｋ主部分行列Ａｋの最大固有値に対応する請求項２に記載の方法。
【請求項７】
前記要素は、入手可能な株式の実質的に大きなプールから選択される相対的に少ない数の株式であり、前記共分散は、該株式のそれぞれ取り得る対間のリスク／リターン実績を示す請求項１に記載の方法。
【請求項８】
前記スパーシティパラメータｋは、前記分散最大化ｋ−スパース固有ベクトルｘ（＾）のために必要とされる最小の分散に対して大きさが最も近い前記共分散行列Ａの固有値のランクに少なくとも等しい請求項１に記載の方法。
【請求項９】
スパース主成分分析の基数制約組み合わせ最適化問題を解くための、コンピュータによって実施される方法であって、
スパース主成分分析最適化問題のための入力要素間の共分散を示す共分散行列Ａおよびスパーシティパラメータｋを入力するステップと、
複数の要素からなる候補解ベクトルｘを得るために貪欲探索を適用するステップと、
前記共分散行列Ａおよび前記スパーシティパラメータｋによって定義される前記基数制約組み合わせ最適化問題のための全体として最適な厳密解ベクトルｘ＊を得るために、前記候補解ベクトルｘを用いる分岐限定組み合わせ探索を適用するステップと
を含むスパース主成分分析の基数制約組み合わせ最適化問題を解くための、コンピュータによって実施される方法。
【請求項１０】
前記分岐限定組み合わせ探索は、探索木内の下位問題分岐パスを取り除くために固有値範囲を用いる請求項９に記載の方法。
【請求項１１】
前記スパーシティパラメータｋは、前記分散最大化ｋ−スパース固有ベクトルｘ（＾）のために必要とされる最小の分散に対して大きさが最も近い前記共分散行列Ａの固有値のランクに少なくとも等しい請求項９に記載の方法。
【請求項１２】
前記要素は、入手可能な株式の実質的に大きなプールから選択される相対的に少ない数の株式であり、前記共分散は、該株式のそれぞれ取り得る対間のリスク／リターン実績を示す請求項９に記載の方法。
【請求項１】
スパース主成分分析の基数制約組み合わせ最適化問題に対する候補解を最大にするための、コンピュータによって実施される方法であって、
複数の要素からなる候補解ベクトルｘ、該候補解ベクトルｘのそれぞれ取り得る要素対間の共分散を示す共分散行列Ａ、および最終解の基数を表すスパーシティパラメータｋを入力するステップと、
該スパーシティパラメータｋに局所的に最適であり、かつ前記スパース主成分分析最適化問題に対する前記最終解である、分散最大化ｋ−スパース固有ベクトルｘ（＾）を得るために、前記共分散行列Ａおよび前記スパーシティパラメータｋに関して前記候補解ベクトルｘの変分再正規化を実行するステップと
を含むスパース主成分分析の基数制約組み合わせ最適化問題に対する候補解を最大にするための、コンピュータによって実施される方法。
【請求項２】
前記変分再正規化は、
前記候補解ベクトルｘの最も大きなｋ個の要素を、前記共分散行列Ａの対応するｋ×ｋ主部分行列Ａｋの主固有ベクトルｕ（Ａｋ）のｋ個の要素で置き換えることと、
前記分散最大化ｋ−スパース固有ベクトルｘ（＾）を得るために、前記候補解ベクトルｘの全ての他の要素を０に設定することと
をさらに含む請求項１に記載の方法。
【請求項３】
前記共分散行列Ａの行および列から前記ｋ×ｋ主部分行列Ａｋを抽出することをさらに含む請求項２に記載の方法。
【請求項４】
候補解を求めるために貪欲探索を実行することをさらに含む請求項１に記載の方法。
【請求項５】
前記貪欲探索は、順方向パスおよび独立した逆方向パスを含む双方向のネストされた探索を含み、
前記方法は、前記スパーシティパラメータｋのために個別に、前記順方向パスまたは前記逆方向パスのいずれかから、前記分散最大化ｋ−スパース固有ベクトルとして最良のスパース固有ベクトルを選択する
ことをさらに含む請求項４に記載の方法。
【請求項６】
前記分散最大化ｋ−スパース固有ベクトルｘ（＾）のｋ個の非ゼロ値は、主固有ベクトルｕ＊ｋのｋ個のエントリに厳密に等しく、該ｋ個のエントリは、前記ｋ×ｋ主部分行列Ａｋの最大固有値に対応する請求項２に記載の方法。
【請求項７】
前記要素は、入手可能な株式の実質的に大きなプールから選択される相対的に少ない数の株式であり、前記共分散は、該株式のそれぞれ取り得る対間のリスク／リターン実績を示す請求項１に記載の方法。
【請求項８】
前記スパーシティパラメータｋは、前記分散最大化ｋ−スパース固有ベクトルｘ（＾）のために必要とされる最小の分散に対して大きさが最も近い前記共分散行列Ａの固有値のランクに少なくとも等しい請求項１に記載の方法。
【請求項９】
スパース主成分分析の基数制約組み合わせ最適化問題を解くための、コンピュータによって実施される方法であって、
スパース主成分分析最適化問題のための入力要素間の共分散を示す共分散行列Ａおよびスパーシティパラメータｋを入力するステップと、
複数の要素からなる候補解ベクトルｘを得るために貪欲探索を適用するステップと、
前記共分散行列Ａおよび前記スパーシティパラメータｋによって定義される前記基数制約組み合わせ最適化問題のための全体として最適な厳密解ベクトルｘ＊を得るために、前記候補解ベクトルｘを用いる分岐限定組み合わせ探索を適用するステップと
を含むスパース主成分分析の基数制約組み合わせ最適化問題を解くための、コンピュータによって実施される方法。
【請求項１０】
前記分岐限定組み合わせ探索は、探索木内の下位問題分岐パスを取り除くために固有値範囲を用いる請求項９に記載の方法。
【請求項１１】
前記スパーシティパラメータｋは、前記分散最大化ｋ−スパース固有ベクトルｘ（＾）のために必要とされる最小の分散に対して大きさが最も近い前記共分散行列Ａの固有値のランクに少なくとも等しい請求項９に記載の方法。
【請求項１２】
前記要素は、入手可能な株式の実質的に大きなプールから選択される相対的に少ない数の株式であり、前記共分散は、該株式のそれぞれ取り得る対間のリスク／リターン実績を示す請求項９に記載の方法。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【公開番号】特開２００７−１６４７８３（Ｐ２００７−１６４７８３Ａ）
【公開日】平成１９年６月２８日（２００７．６．２８）
【国際特許分類】
【外国語出願】
【出願番号】特願２００６−３２１９５０（Ｐ２００６−３２１９５０）
【出願日】平成１８年１１月２９日（２００６．１１．２９）
【出願人】（５９７０６７５７４）ミツビシ・エレクトリック・リサーチ・ラボラトリーズ・インコーポレイテッド (484)
【住所又は居所原語表記】２０１ ＢＲＯＡＤＷＡＹ， ＣＡＭＢＲＩＤＧＥ， ＭＡＳＳＡＣＨＵＳＥＴＴＳ ０２１３９， Ｕ．Ｓ．Ａ．
【Ｆターム（参考）】
【公開日】平成１９年６月２８日（２００７．６．２８）
【国際特許分類】
【出願番号】特願２００６−３２１９５０（Ｐ２００６−３２１９５０）
【出願日】平成１８年１１月２９日（２００６．１１．２９）
【出願人】（５９７０６７５７４）ミツビシ・エレクトリック・リサーチ・ラボラトリーズ・インコーポレイテッド (484)
【住所又は居所原語表記】２０１ ＢＲＯＡＤＷＡＹ， ＣＡＭＢＲＩＤＧＥ， ＭＡＳＳＡＣＨＵＳＥＴＴＳ ０２１３９， Ｕ．Ｓ．Ａ．
【Ｆターム（参考）】
[ Back to top ]