(57)【要約】【課題】多次元データから疎な構造を計算するgraphical  lassoを高速に計算することができる。【解決手段】graphical  lasso計算装置１は、データポイント間の近似の共分散をＳＶＤ計算部１１が計算したＳＶＤから計算する近似共分散計算部１２と、近似によりエッジを有する可能性がある場合にデータポイント間の共分散を計算する共分散計算部１３と、共分散からなる隣接行列の連結部分であるブロックを計算する連結部分計算部１４と、ブロックの計算対象の成分を設定する更新成分設定部１５と、計算対象の成分においてlassoにおける第１の係数を繰り返し計算する係数計算部１６と、lassoにおける第２の係数が非零であるか否かを確認する非更新成分確認部１７と、非更新成分確認部１７の確認結果に応じて第１の係数の繰り返し計算の継続を判定する繰り返し計算判定部１８と、を有する。【選択図】図２
2018190160.tif 000002
【特許請求の範囲】
【請求項１】
多次元データから疎な構造を計算するgraphical  lasso計算装置であって、
入力される多次元行列の特異値分解（ＳＶＤ：Singular  Value  Decomposition）を計算するＳＶＤ計算部と、
データポイント間の近似の共分散をＳＶＤから計算する近似共分散計算部と、
近似によりエッジを有する可能性がある場合に、データポイント間の共分散を計算する共分散計算部と、
共分散からなる隣接行列の連結部分であるブロックを計算する連結部分計算部と、
前記ブロックのうち、lassoにおける係数の計算対象の成分を設定する更新成分設定部と、
前記計算対象の成分において、lassoにおける第１の係数を繰り返し計算する係数計算部と、
lassoにおける第２の係数が非零であるか否かを確認する非更新成分確認部と、
前記第２の係数が非零であるか否かの確認結果に応じて、前記計算対象の成分における前記第１の係数に対する繰り返し計算を継続するか否かを判定する第１の判定部と、
全成分の繰り返し計算を継続するか否かを判定する第２の判定部と、
を有することを特徴とするgraphical  lasso計算装置。
【請求項２】
前記近似共分散計算部は、ＳＶＤにより共分散の近似を行って該共分散の上限値及び下限値を計算し、
前記共分散計算部は、前記共分散の上限値及び下限値を用いて前記エッジを有する可能性の有無を特定することを特徴とする請求項１に記載のgraphical  lasso計算装置。
【請求項３】
前記第２の係数は、前記計算対象の成分のｉ（ｉは任意の数である。）番目の列に対応するｉ番目のlassoの係数であり、
前記第１の係数は、前記第２の係数のｉ番目の要素とする列ベクトルであることを特徴とする請求項１または２に記載のgraphical  lasso計算装置。
【請求項４】
前記第１の判定部は、前記第２の係数が非零でない場合に前記第１の係数に対する繰り返し計算を継続しないと判定し、前記第２の係数が非零である場合に前記第１の係数に対する繰り返し計算を継続すると判定することを特徴とする請求項１〜３のいずれか一つに記載のgraphical  lasso計算装置。
【請求項５】
多次元データから疎な構造を計算するgraphical  lasso計算装置が実行するgraphical  lasso計算方法であって、
入力される多次元行列のＳＶＤを計算するＳＶＤ計算工程と、
データポイント間の近似の共分散をＳＶＤから計算する近似共分散計算工程と、
近似によりエッジを有する可能性がある場合に、データポイント間の共分散を計算する共分散計算工程と、
共分散からなる隣接行列の連結部分であるブロックを計算する連結部分計算工程と、
前記ブロックのうち、lassoにおける係数の計算対象の成分を設定する更新成分設定工程と、
前記計算対象の成分において、lassoにおける第１の係数を繰り返し計算する係数計算工程と、
lassoにおける第２の係数が非零であるか否かを確認する非更新成分確認工程と、
前記第２の係数が非零であるか否かの確認結果に応じて、前記計算対象の成分における前記第１の係数に対する繰り返し計算を継続するか否かを判定する第１の判定工程と、
全成分の繰り返し計算を継続するか否かを判定する第２の収束判定工程と、
を有することを特徴とするgraphical  lasso計算方法。
【請求項６】
コンピュータを、請求項１〜４のいずれか一つに記載のgraphical  lasso計算装置として機能させるためのgraphical  lasso計算プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、graphical  lasso計算装置、graphical  lasso計算方法及びgraphical  lasso計算プログラムに関する。
【背景技術】
【０００２】
graphical  lassoは、Ｌ１正則化を用いて多次元データから無効グラフを計算する手法として最も有名なものの一つである（非特許文献１参照）。ここで、グラフのノードは、多次元データの各データポイントに対応し、エッジは、データポイント間の条件依存性に対応する。
【０００３】
graphical  lassoは平均μの多変数のガウス分布による共分散行列Σに対してその逆行列Θ（＝Σ−１）を推定するものである。もし行列Θの（ｉ，ｊ）要素が非零であれば（θ［ｉ，ｊ］≠０）、ｉ番目とｊ番目の変数は、条件付依存の関係にあるということになる。graphical  lassoは、構造を疎にするために行列Θを推定するときに、Ｌ１のペナルティを用いる。行列ＸをＮ次元からなるＰ個の変数に対応するＮ×Ｐのデータ行列としたとき、行列Ｓを、Ｓ＝ＸＴＸ（行列ＸＴは行列Ｘの転置とする。）であるような共分散行列とすると、graphical  lassoは、以下の式（１）に示す目的関数を最大化することによって、疎なグラフ構造を推定する。
【０００４】
【数１】
2018190160.tif 000003
【０００５】
式（１）において、ρは、推定されたグラフの疎具合を決定する正のＬ１正規化パラメータである。また、この（１）式において疎な構造を求める問題は凸になる。graphical  lassoは、この問題を解くために座標降下法を用いてlassoの係数の更新を繰り返し行う。具体的には、graphical  lassoは、推定する行列の各行及び各列を収束するまでラウンドロビンに計算する。
【０００６】
そして、計算コストを下げるため、Friedmanらはスクリーニングによる手法を提案した（例えば、非特許文献２参照）。このスクリーニングによる手法は、係数の更新のための計算を連結成分にのみに限定するため、効果的に更新の計算を行う変数を特定することができる。graphical  lassoの高速化については、このスクリーニングによる手法が最も知られている。
【先行技術文献】
【非特許文献】
【０００７】
【非特許文献１】Jerome  Friedman，  Trevor  Hastie  and  Robert  Tibshirani,  “Sparse  inverse  covariance  estimation  with  the  graphical  lasso”,  Biostatistics,  9(3):432−441,  2008.
【非特許文献２】Daniela  M.  Witten，  Jerome  H.  Friedman  and  Noah  Simon,  “New  Insights  and  Faster  Computations  for  the  Graphical  Lasso”,  Journal  of  Computational  and  Graphical  Statistics,  20(4):892−900,  2011.
【発明の概要】
【発明が解決しようとする課題】
【０００８】
しかしながら、このスクリーニングによる手法は、共分散行列の全ての要素を計算しなければならず、graphical  lassoの計算コストを有効に減らすことができないという問題がある。
【０００９】
本発明は、上記に鑑みてなされたものであって、多次元データから疎な構造を計算するgraphical  lassoを高速に計算することができるgraphical  lasso計算装置、graphical  lasso計算方法及びgraphical  lasso計算プログラムを提供することを目的とする。
【課題を解決するための手段】
【００１０】
上述した課題を解決し、目的を達成するために、本発明に係るgraphical  lasso計算装置は、多次元データから疎な構造を計算するgraphical  lasso計算装置であって、入力される多次元行列の特異値分解（ＳＶＤ：Singular  Value  Decomposition）を計算するＳＶＤ計算部と、データポイント間の近似の共分散をＳＶＤから計算する近似共分散計算部と、近似によりエッジを有する可能性がある場合に、データポイント間の共分散を計算する共分散計算部と、共分散からなる隣接行列の連結部分であるブロックを計算する連結部分計算部と、ブロックのうち、lassoにおける係数の計算対象の成分を設定する更新成分設定部と、計算対象の成分において、lassoにおける第１の係数を繰り返し計算する係数計算部と、lassoにおける第２の係数が非零であるか否かを確認する非更新成分確認部と、第２の係数が非零であるか否かの確認結果に応じて、計算対象の成分における第１の係数に対する繰り返し計算を継続するか否かを判定する第１の判定部と、全成分の繰り返し計算を継続するか否かを判定する第２の判定部と、を有することを特徴とする。
【発明の効果】
【００１１】
本発明によれば、多次元データから疎な構造を計算するgraphical  lassoを高速に計算することができる。
【図面の簡単な説明】
【００１２】
【図１】図１は、式（３）における係数の求め方を示す図である。
【図２】図２は、本実施の形態に係るgraphical  lasso計算装置の要部構成の一例を示すブロック図である。
【図３】図３は、定義１を示す図である。
【図４】図４は、定義２を示す図である。
【図５】図５は、補題１を示す図である。
【図６】図６は、補題２を示す図である。
【図７】図７は、補題３を示す図である。
【図８】図８は、実施の形態に係るgraphical  lasso計算処理のアルゴリズムを示す図である。
【図９】図９は、実施の形態に係るgraphical  lasso計算処理の処理手順を示すフローチャートである。
【図１０】図１０は、繰り返し計算打ち切りの条件を示す図である。
【図１１】図１１は、定理１を示す図である。
【図１２】図１２は、定理２を示す図である。
【図１３】図１３は、プログラムが実行されることにより、graphical  lasso計算装置が実現されるコンピュータの一例を示す図である。
【発明を実施するための形態】
【００１３】
以下、図面を参照して、本発明の一実施の形態を詳細に説明する。なお、この実施の形態により本発明が限定されるものではない。また、図面の記載において、同一部分には同一の符号を付して示している。
【００１４】
［従来のgraphical  lasso計算手法］
まず、従来のgraphical  lasso計算手法について説明する。graphical  lassoは、多次元データから疎な構造を計算する計算手法である。例えば、Ｎ個の観測とＰ個の変数とからなるＮ×Ｐのデータ行列Ｘが与えられたとき、graphical  lassoは、式（１）の目的関数を最大化することによって、行列Ｘから共分散行列Σの逆行列Θを推定する。Ｓを実際の共分散行列とし、Ｉを単位行列としたときに、graphical  lassoは、Ｓ＝Ｓ＋ρＩとして与えられる行列Ｗの各行と列とを座標降下法を用いて最適化する。具体的には、まず、graphical  lassoでは、行列ＷとＳとを以下の式（２）のように分割する。
【００１５】
【数２】
2018190160.tif 000004
【００１６】
graphical  lassoでは、lassoの解を計算する行及び列が最後になるように、繰り返し行列Ｗとの各行と列を並び替える。続いて、以下の式（３）を示す。
【００１７】
【数３】
2018190160.tif 000005
【００１８】
なお、繰り返し計算において、行列Ｗの対角要素は不変とする。図１は、式（３）における係数の求め方を示す図である。図１に示すように、式（３）における係数を求める。
【００１９】
ここで、従来、計算コストを下げるため、Friedmanらはスクリーニングによる手法を提案した（非特許文献２参照）。このスクリーニングによる手法は、もし、｜Ｓ［ｉ，ｊ］｜≦ρが、ｉ≠ｊであるすべてのｊ番目の変数に成り立てば、ｉ番目の変数は推定されたグラフにおいて孤立したノードになるという知見に基づいている。このため、このスクリーニングによる手法では、｜Ｓ［ｉ，ｊ］｜＞ρである場合に、ノードのペアがエッジでつながるグラフの隣接行列を求め、そのグラフの連結成分を求める。このスクリーニングによる手法は、係数の更新のための計算を連結成分にのみに限定するため、効果的に更新の計算を行う変数を特定することができる。
【００２０】
graphical  lassoの高速化において、このスクリーニングによる手法は最も知られている。しかしながら、この手法は共分散行列の全ての要素を計算しなければならず、計算コストを有効に減らすことができないという問題がある。この場合の、Ｔを行列Σの各行及び列における繰り返し計算の回数とし、Ｂを推定されたグラフの各行及び列における非零成分の数とすると、graphical  lassoに必要な計算コストは、Ｏ（ＮＰ２＋ＰＢＴ）になる。
【００２１】
［実施の形態の概要］
本実施の形態において用いられる手法によれば、より高速にgraphical  lassoを計算することができる。まず、本実施の形態の計算手法の概要を述べた後に、本実施の形態による計算手法の詳細を述べる。なお、各集合を示すシンボルは、明細書中ではアルファベットの大文字で示し、図面中ではアルファベットの大文字を中抜きした字体で示す。
【００２２】
上述したように、従来の手法では、各繰り返し計算において更新される係数の数を減らすために、共分散行列Ｓの各要素を計算し、｜Ｓ［ｉ，ｊ］｜＞ρであればエッジを追加する。これは、既存手法では、連続成分を計算するために行列Ｓの全ての要素を計算しなければならないことを示している。さらに、従来の手法では、lassoの性質により、ほぼ全ての係数の値が零になるにも関わらず、全ての係数をラウンドロビンに計算する。
【００２３】
これに対し、本実施の形態では、高速に計算を行うために、ＳＶＤを用いて、共分散Ｓ［ｉ，ｊ］の近似を行い、その上限値と下限値とを高速に計算する。
【００２４】
そして、本実施の形態では、共分散が近似によりエッジを持つ可能性があると判定された場合に正確な共分散の値を計算する。言い換えると、本実施の形態では、ＳＶＤを用いて推定された行列において、非零になる成分を持つブロックを繰り返し計算に入る前に高速に求める。また、本実施の形態では、非零要素を持つことを期待される成分を、選択して繰り返し更新を行う。言い換えると、本実施の形態では、推定された行列において、非零になる成分を選択的に更新する。
【００２５】
このように、本実施の形態では、共分散が近似によりエッジを持つ可能性があると判定された場合にのみ正確な共分散の値を計算するともに、連結成分において少数の成分のみ繰り返し更新を行う。したがって、本実施の形態によれば、従来の手法よりも繰り返し計算を少ない回数とすることができるため、graphical  lassoを高速に計算することができる。
【００２６】
［実施の形態の構成］
まず、図２を用いて、実施の形態に係るgraphical  lasso計算装置の構成について説明する。図２は、本実施の形態に係るgraphical  lasso計算装置の要部構成の一例を示すブロック図である。図２に示すように、graphical  lasso計算装置１は、ＳＶＤ計算部１１、近似共分散計算部１２、共分散計算部１３、連結部分計算部１４、更新成分設定部１５、係数計算部１６、非更新成分確認部１７、繰り返し計算判定部１８（第１の判定部）、収束判定部１９及び逆行列計算部２０を有する。
【００２７】
ＳＶＤ計算部１１は、入力される多次元行列のＳＶＤを計算する。近似共分散計算部１２は、近似によりエッジを有する可能性がある場合に、データポイント間の共分散を計算する。共分散計算部１３は、近似によりエッジを有する可能性がある場合に、データポイント間の共分散を計算する。連結部分計算部１４は、共分散からなる隣接行列の連結部分であるブロックを計算する。
【００２８】
更新成分設定部１５は、ブロックのうち、lassoにおける係数の計算対象の成分を設定する。係数計算部１６は、計算対象の成分において、lassoにおける第１の係数を繰り返し計算する。第１の係数は、後述の第２の係数のｉ番目の要素とする列ベクトルである。非更新成分確認部１７は、lassoにおける第２の係数が非零であるか否かを確認する。第２の係数は、隣接行列のｉ（ｉは任意の数である。）番目の列に対応するｉ番目のlassoの係数である。
【００２９】
繰り返し計算判定部１８（第１の判定部）は、第２の係数が非零であるか否かの確認結果に応じて、計算対象の成分における第１の係数に対する繰り返し計算を継続するか否かを判定する。繰り返し計算判定部１８は、lassoにおける第２の係数が非零でない場合に第１の係数に対する繰り返し計算を継続しないと判定する。収束判定部１９（第２の判定部）は、全成分の繰り返し計算を継続するか否かを判定する。逆行列計算部２０は、共分散行列Σの逆行列Θを計算する。
【００３０】
［近似共分散計算処理］
ここで、近似共分散計算部１２は、ＳＶＤにより共分散の近似を行って該共分散の上限値及び下限値を計算する。このため、近似共分散計算部１２による近似共分散計算処理、すなわち、近似共分散計算部１２が共分散Ｓ［ｉ，ｊ］の上限値と下限値を求める手法について述べる。
【００３１】
この手法は、Ｎ×Ｐのデータ行列を、ＳＶＤによりランクがｎ（ｎ≪Ｎ）の行列で近似する。ＳＶＤは直行変換であり、二乗誤差の観点で高い精度となる。図３は、定義１を示す図である。図４は、定義２を示す図である。定義１，２は、近似共分散計算処理の際に必要となる。近似共分散計算部１２は、図３に示す手法を用いて、共分散Ｓ［ｉ，ｊ］の上限値を求める。ここで繰り返し計算に入る前に列ベクトルのＬ２は、Ｏ（ＮＰ）の計算コストで求めることができる。同様に行列ＸのＳＶＤは、Ｏ（ＮＰｌｏｇｎ）の計算コストで求めることができる（詳細は、非特許文献１参照）。
【００３２】
そして、近似共分散計算部１２は、図４に示す手法を用いて、共分散Ｓ［ｉ，ｊ］の下限値を求める。図５は、補題１を示す図である。図５に示す補題１に示す関係が、共分散Ｓ［ｉ，ｊ］の上限値及び下限値について成り立つ（詳細は、Nathan  Halko，Per-Gunnar  Martinsson  and  Joel  A.  Tropp,  “FINDING  STRUCTURE  WITH  RANDOMNESS:  PROBABILISTIC  ALGORITHMS  FOR  CONSTRUCTING  APPROXIMATE  MATRIX  DECOMPOSITIONS”,  SIAM  Review,  53(2):217−288,  2011.参照）
【００３３】
なお、計算量の観点において、もし行列Ｘの各列ベクトルのＬ２とＳＶＤとが計算済みであれば、上限値と下限値を計算するのに必要なコストは、図３及び図４に示す定義１，２からＯ（ｎ）となる。
【００３４】
［共分散計算処理］
続いて、共分散計算部１３による共分散計算処理を説明する。共分散計算部１３は、共分散の上限値及び下限値を用いてエッジを有する可能性の有無を特定する。データポイント間の共分散を計算する。図６は、補題２を示す図である。
【００３５】
補題２より、Ｌ１正規パラメータρが共分散の上限値以上、かつ、−ρが共分散の下限値以下である場合には、このノードのペアは隣接行列においてエッジを持たない。すなわち、ρが共分散の上限値未満、かつ、−ρが共分散の下限値より大である場合に、このノードのペアは隣接行列においてエッジを持つ可能性を有する。
【００３６】
本実施の形態では、共分散計算部１３は、近似によりエッジを有する可能性がある場合、すなわち、ρが共分散の上限値未満、かつ、−ρが共分散の下限値より大である場合にのみ、データポイント間の共分散を計算する。したがって、共分散計算部１３は、共分散の上限値及び下限値を用いてスクリーニングによる手法における隣接行列を、図６の補題２に示す性質から高速に計算することができる。
【００３７】
［繰り返し計算処理］
続いて、実施の形態における繰り返し計算処理について説明する。実施の形態では、高速にgraphical  lassoを計算するために、係数計算部１６は、非零になることが期待されるlassoにおける第１の係数を選択的に収束するまで計算する。係数計算部１６によって選択されなかった第１の係数については、非更新成分確認部１７が、繰り返し計算の後に非零の係数を持つか否かを確認する。
【００３８】
この処理では、｜Ｓ［ｉ，ｊ］｜＞ρが成り立てば逆行列Θの（ｉ，ｊ）要素は非零の値を持つことが期待され、それに対応するlassoの係数も非零になる可能性が高いという知見に基づいている。Ｂｉをスクリーニングによる手法から得られたｉ番目の変数を含む連結成分のブロックとし、集合Ｂｉを集合Ｂｉ=｛ｊ｜Ｂｊ=Ｂｉ｝であるような集合とすると、スクリーニングによる手法では、ｉ番目の係数を集合Ｂｉ−ｉを用いて計算する。一方、本実施の形態では、係数計算部１６は、ｉ番目の変数に対して係数を、以下の式（４）として初期化される集合Ｕｉを用いて収束するまで式（３）を用いて計算を行う。
【００３９】
【数４】
2018190160.tif 000006
【００４０】
ここで集合Ｕｉ⊆集合Ｂｉの関係であるあることは明らかである。そして、また上限値と下限値を用いて集合Ｕｉは高速に求めることができる。
【００４１】
また、Ｕｉ´を以下の式（５）であるような集合とする。
【００４２】
【数５】
2018190160.tif 000007
【００４３】
非更新成分確認部１７は、集合Ｕｉ´に含まれる係数が非零の係数を持つのか繰り返し計算の後に確認する。結果として、本実施の形態では、ｉ番目の係数を計算するために、集合Ｕｉ＋集合Ｕｉ´＝集合Ｂｉ−ｉであるため、集合Ｂｉ−ｉを用いてｉ番目の係数を計算するスクリーニングによる手法と同じ結果を得ることができる。図７は、補題３を示す図である。本実施の形態は、理論的に補題３の性質に基づいている。
【００４４】
従来のスクリーニングよる手法が集合Ｂｉに含まれる係数をランドロビンに更新するのに対して、補題３は、本実施の形態が、集合Ｕｉ´に含まれる係数を確認することにより推定の結果に影響を与えることなく、集合Ｕｉ(集合Ｕｉ⊆集合Ｂｉ)に含まれる係数を選択的に更新することができることを示している。
【００４５】
本実施の形態では、集合Ｕｉに含まれる係数は繰り返し更新される一方、集合Ｕｉ´に含まれる係数に対しては繰り返し計算を行わない。この結果、本実施の形態によれば、係数を選択的に収束させているため、高速な処理が可能である。そして、本実施の形態では、非更新成分確認部１７が、集合Ｕｉ´に非零の係数が含まれているか否かを確認し、集合Ｕｉ´に非零の係数が含まれていることを確認した場合、その係数を集合Ｕｉに追加する。そして、再帰的に係数が収束し、ｉ∈集合Ｕｉ´であるような全てのｉに対し、以下の式（６）となるまで処理を行う。
【００４６】
【数６】
2018190160.tif 000008
【００４７】
［graphical  lasso計算処理の処理手順］
図８及び図９を参照して、実施の形態に係るgraphical  lasso計算処理の処理手順について説明する。図８は、実施の形態に係るgraphical  lasso計算処理のアルゴリズムを示す図である。また、図９は、実施の形態に係るgraphical  lasso計算処理の処理手順を示すフローチャートである。
【００４８】
図８に示すAlgorithm１において、行列Ａは、Ｐ×Ｐの隣接行列であり、ｍは、スクリーニングによる手法で得られる連結成分のブロックの数とする。そして、本実施の形態に係るgraphical  lasso計算処理では、ブロックを一つ一つ処理していく。また、行列Ｓ（ｉ）、行列Ｗ（ｉ）、単位行列Ｉ（ｉ）、ベクトルｗ（ｉ）１２，ｗ（ｉ）１１、逆行列Θ（ｉ）は、それぞれｉのブロックに対応する行列Ｓ、行列Ｗ、単位行列Ｉ、ベクトルｗ１２，ｗ１１、逆行列Θとする。
【００４９】
本実施の形態では、まず、ＳＶＤ計算部１１が、データ行列ＸのＳＶＤを計算し，隣接行列Ａを初期化する（図８に示すアルゴリズム１，２行目、図９に示すステップＳ１，Ｓ２）。続いて、隣接行列のエッジを高速に求めるため、近似共分散計算部１２が、行列Ｓの共分散の上限値と下限値とを計算し、もしこれらが補題２のエッジに対する条件を満たしたとき、共分散計算部１３は、正確な共分散の値を計算する（図８に示すアルゴリズム３〜９行目、図９に示すステップＳ３〜Ｓ１１）。
【００５０】
そして、連結部分計算部１４は、行列Ａから連結成分のブロックを計算する（図８に示すアルゴリズム１０行目、図９のステップＳ１２）。更新成分設定部１５が、lassoにおける係数の計算対象のブロック１〜ｍを設定すると（図８に示すアルゴリズム１１行目、図９のステップＳ１３）、係数計算部１６が、それぞれのブロックに対して、まず行列Ｓ（ｉ）と行列Ｗ（ｉ）とを計算する（図８に示すアルゴリズム１２〜１３行目、図９のステップＳ１４，Ｓ１５）。そして、係数計算部１６が、集合Ｕｊを用いて繰り返し係数を収束するまで計算する（図８に示すアルゴリズム１５〜１８行目、図９のステップＳ１６〜ステップＳ１８）。
【００５１】
図１０は、繰り返し計算打ち切りの条件を示す図である。非更新成分確認部１７は、補題３に基づき、lassoにおける第２の係数が非零であるか否かを確認し、もし、図１０に示す関係が成り立つと判断した場合、繰り返し計算判定部１８は、繰り返し計算を打ち切る（図８に示すアルゴリズム１９〜２４行目、図９に示すステップＳ１９〜Ｓ２５）。
【００５２】
そして、更新成分設定部１５は、繰り返し計算の後で行列Ｗ（ｉ）を更新する（図８に示すアルゴリズム２５行目、図９に示すステップＳ２６）。続いて、収束判定部１９は、行列Ｗ（ｉ）が収束するか否かを判断する（図９に示すステップＳ２７）。
【００５３】
収束判定部１９は、行列Ｗ（ｉ）が収束すると判断しない場合には（図９に示すステップＳ２７：Ｎｏ）、これらの処理（図８に示すアルゴリズム１１〜２５行目、図９に示すステップＳ１３〜Ｓ２５）を行う（図８に示すアルゴリズム２６行目）。
【００５４】
続いて、行列Ｗ（ｉ）が収束すると収束判定部１９が判断した場合には（図９に示すステップＳ２７：Ｙｅｓ）、逆行列計算部２０は、行列Ｗ（ｉ）から逆行列Θ（ｉ）を計算し（図８に示すアルゴリズム２７行目、図９に示すステップＳ２８）、計算した逆行列Θ（ｉ）を出力して（図９に示すステップＳ２９）、graphical  lasso計算処理を終了する。
【００５５】
そして、上記Algorithm１に対して、定理１，２に示す性質が成り立つ。図１１は、定理１を示す図である。図１２は、定理２を示す図である。
【００５６】
［本実施の形態の効果］
このように、本実施の形態では、共分散が近似によりエッジを持つ可能性があると判定された場合にのみ正確な共分散の値を計算するともに、連結成分において少数の非零要素を持つことを期待される成分のみ繰り返し更新を行う。したがって、本実施の形態によれば、従来の手法よりも繰り返し計算を少ない回数とすることができるため、graphical  lassoを高速に計算することができる。
【００５７】
［実施の形態のシステム構成について］
図１に示したgraphical  lasso計算装置１の各構成要素は機能概念的なものであり、必ずしも物理的に図示のように構成されていることを要しない。すなわち、graphical  lasso計算装置１の機能の分散及び統合の具体的形態は図示のものに限られず、その全部または一部を、各種の負荷や使用状況などに応じて、任意の単位で機能的または物理的に分散または統合して構成することができる。
【００５８】
また、graphical  lasso計算装置１においておこなわれる各処理は、全部または任意の一部が、ＣＰＵ（Central  Processing  Unit）、ＧＰＵ（Graphics  Processing  Unit）、及び、ＣＰＵ、ＧＰＵにより解析実行されるプログラムにて実現されてもよい。また、graphical  lasso計算装置１においておこなわれる各処理は、ワイヤードロジックによるハードウェアとして実現されてもよい。
【００５９】
また、実施の形態において説明した各処理のうち、自動的におこなわれるものとして説明した処理の全部または一部を手動的に行うこともできる。もしくは、手動的におこなわれるものとして説明した処理の全部または一部を公知の方法で自動的に行うこともできる。この他、上述及び図示の処理手順、制御手順、具体的名称、各種のデータやパラメータを含む情報については、特記する場合を除いて適宜変更することができる。
【００６０】
［プログラム］
図１３は、プログラムが実行されることにより、graphical  lasso計算装置１が実現されるコンピュータの一例を示す図である。コンピュータ１０００は、例えば、メモリ１０１０、ＣＰＵ１０２０を有する。また、コンピュータ１０００は、ハードディスクドライブインタフェース１０３０、ディスクドライブインタフェース１０４０、シリアルポートインタフェース１０５０、ビデオアダプタ１０６０、ネットワークインタフェース１０７０を有する。これらの各部は、バス１０８０によって接続される。
【００６１】
メモリ１０１０は、ＲＯＭ（Read  Only  Memory）１０１１及びＲＡＭ１０１２を含む。ＲＯＭ１０１１は、例えば、ＢＩＯＳ（Basic  Input  Output  System）等のブートプログラムを記憶する。ハードディスクドライブインタフェース１０３０は、ハードディスクドライブ１０９０に接続される。ディスクドライブインタフェース１０４０は、ディスクドライブ１１００に接続される。例えば磁気ディスクや光ディスク等の着脱可能な記憶媒体が、ディスクドライブ１１００に挿入される。シリアルポートインタフェース１０５０は、例えばマウス１１１０、キーボード１１２０に接続される。ビデオアダプタ１０６０は、例えばディスプレイ１１３０に接続される。
【００６２】
ハードディスクドライブ１０９０は、例えば、ＯＳ１０９１、アプリケーションプログラム１０９２、プログラムモジュール１０９３、プログラムデータ１０９４を記憶する。すなわち、graphical  lasso計算装置１の各処理を規定するプログラムは、コンピュータ１０００により実行可能なコードが記述されたプログラムモジュール１０９３として実装される。プログラムモジュール１０９３は、例えばハードディスクドライブ１０９０に記憶される。例えば、graphical  lasso計算装置１における機能構成と同様の処理を実行するためのプログラムモジュール１０９３が、ハードディスクドライブ１０９０に記憶される。なお、ハードディスクドライブ１０９０は、ＳＳＤ（Solid  State  Drive）により代替されてもよい。
【００６３】
また、上述した実施の形態の処理で用いられる設定データは、プログラムデータ１０９４として、例えばメモリ１０１０やハードディスクドライブ１０９０に記憶される。そして、ＣＰＵ１０２０が、メモリ１０１０やハードディスクドライブ１０９０に記憶されたプログラムモジュール１０９３やプログラムデータ１０９４を必要に応じてＲＡＭ１０１２に読み出して実行する。
【００６４】
なお、プログラムモジュール１０９３やプログラムデータ１０９４は、ハードディスクドライブ１０９０に記憶される場合に限らず、例えば着脱可能な記憶媒体に記憶され、ディスクドライブ１１００等を介してＣＰＵ１０２０によって読み出されてもよい。あるいは、プログラムモジュール１０９３及びプログラムデータ１０９４は、ネットワーク（ＬＡＮ、ＷＡＮ等）を介して接続された他のコンピュータに記憶されてもよい。そして、プログラムモジュール１０９３及びプログラムデータ１０９４は、他のコンピュータから、ネットワークインタフェース１０７０を介してＣＰＵ１０２０によって読み出されてもよい。
【００６５】
以上、本発明者によってなされた発明を適用した実施の形態について説明したが、本実施の形態による本発明の開示の一部をなす記述及び図面により本発明は限定されることはない。すなわち、本実施の形態に基づいて当業者等によりなされる他の実施の形態、実施例及び運用技術等は全て本発明の範疇に含まれる。
【符号の説明】
【００６６】
１  graphical  lasso計算装置
１１  ＳＶＤ計算部
１２  近似共分散計算部
１３  共分散計算部
１４  連結部分計算部
１５  更新成分設定部
１６  係数計算部
１７  非更新成分確認部
１８  繰り返し計算判定部
１９  収束判定部
２０  逆行列計算部
【図１】
2018190160.tif 000009
【図２】
2018190160.tif 000010
【図３】
2018190160.tif 000011
【図４】
2018190160.tif 000012
【図５】
2018190160.tif 000013
【図６】
2018190160.tif 000014
【図７】
2018190160.tif 000015
【図８】
2018190160.tif 000016
【図９】
2018190160.tif 000017
【図１０】
2018190160.tif 000018
【図１１】
2018190160.tif 000019
【図１２】
2018190160.tif 000020
【図１３】
2018190160.tif 000021