(57)【要約】【課題】閉形式の解が存在しない場合であっても、疎構造の変数を計算量を抑えて最適化できる疎変数最適化装置を提供する。【解決手段】勾配計算部８１は、最適化対象とする変数における目的関数の勾配を計算する。追加変数選択部８２は、変数集合に含まれる変数のうち、計算された勾配の絶対値が最も大きい変数を非ゼロ変数集合へ追加する。変数最適化部８３は、非ゼロ変数集合に含まれる変数に対して、最適化対象とする変数の値を最適化する。削除変数選択部８４は、非ゼロ変数集合に含まれる変数のうち、その変数を除いた場合に目的関数の増加が最も小さな変数を、その非ゼロ変数集合から削除する。目的関数評価部８５は、最適化対象とする変数に対する目的関数の値を算出する。【選択図】図３
2014160456.tif 000002
【特許請求の範囲】
【請求項１】
変数の指定された値における目的関数の勾配を計算する勾配計算部と、
変数集合に含まれる変数の一つを非ゼロ変数集合へ追加する追加変数選択部と、
前記非ゼロ変数集合に含まれる変数に対して、最適化対象とする変数の値を最適化する変数最適化部と、
前記非ゼロ変数集合に含まれる変数のうち、当該変数を除いた場合に前記目的関数の増加が最も小さな変数を、当該非ゼロ変数集合から削除する削除変数選択部と、
最適化対象とする変数に対する前記目的関数の値を算出する目的関数評価部とを備え、
前記勾配計算部は、最適化対象とする変数における前記目的関数の勾配を計算し、
前記追加変数選択部は、前記変数集合に含まれる変数のうち、計算された勾配の絶対値が最も大きい変数を非ゼロ変数集合へ追加する
ことを特徴とする疎変数最適化装置。
【請求項２】
勾配計算部は、ロジスティック回帰モデルを表わす目的関数の、最適化対象とする変数における勾配を計算し、
削除変数選択部は、前記目的関数の増加が最も小さな変数を、非ゼロ変数集合から削除する
請求項１記載の疎変数最適化装置。
【請求項３】
勾配計算部は、目的関数として共分散関数を使用し、共分散行列の逆行列である精度行列の非対角要素における前記目的関数の勾配を計算し、
変数最適化部は、前記精度行列の非対角の非ゼロ成分に対して、当該精度行列の非対角要素を最適化し、
削除変数選択部は、前記精度行列の非対角の非ゼロ成分のうち、当該非ゼロ成分を除いた場合に前記目的関数の増加が最も小さな非ゼロ成分をゼロとし、
目的関数評価部は、前記精度行列の非対角要素に対する前記目的関数の値を算出する
請求項１記載の疎変数最適化装置。
【請求項４】
算出された勾配の絶対値のうち最も大きいものが、予め定められた閾値よりも小さい場合、最適化対象とする変数が最適化されたと判定する最適性判定部を備えた
請求項１から請求項３のうちのいずれか１項に記載の疎変数最適化装置。
【請求項５】
変数の指定された値における目的関数の勾配を計算し、
変数集合に含まれる変数の一つを非ゼロ変数集合へ追加し、
前記非ゼロ変数集合に含まれる変数に対して、最適化対象とする変数の値を最適化し、  前記非ゼロ変数集合に含まれる変数のうち、当該変数を除いた場合に前記目的関数の増加が最も小さな変数を、当該非ゼロ変数集合から削除し、
最適化対象とする変数に対する前記目的関数の値を算出し、
勾配を計算する際、最適化対象とする変数における前記目的関数の勾配を計算し、
前記変数集合に含まれる変数のうち、計算された勾配の絶対値が最も大きい変数を非ゼロ変数集合へ追加する
ことを特徴とする疎変数最適化方法。
【請求項６】
勾配を計算する際、ロジスティック回帰モデルを表わす目的関数の、最適化対象とする変数における勾配を計算し、
前記目的関数の増加が最も小さな変数を、非ゼロ変数集合から削除する
請求項５記載の疎変数最適化方法。
【請求項７】
コンピュータに、
変数の指定された値における目的関数の勾配を計算する勾配計算処理、
変数集合に含まれる変数の一つを非ゼロ変数集合へ追加する追加変数選択処理、
前記非ゼロ変数集合に含まれる変数に対して、最適化対象とする変数の値を最適化する変数最適化処理、
前記非ゼロ変数集合に含まれる変数のうち、当該変数を除いた場合に前記目的関数の増加が最も小さな変数を、当該非ゼロ変数集合から削除する削除変数選択処理、および、
最適化対象とする変数に対する前記目的関数の値を算出する目的関数評価処理を実行させ、
前記勾配計算処理で、最適化対象とする変数における前記目的関数の勾配を計算させ、
前記追加変数選択処理で、前記変数集合に含まれる変数のうち、計算された勾配の絶対値が最も大きい変数を非ゼロ変数集合へ追加させる
ための疎変数最適化プログラム。
【請求項８】
コンピュータに、
勾配計算処理で、ロジスティック回帰モデルを表わす目的関数の、最適化対象とする変数における勾配を計算させ、
削除変数選択処理で、前記目的関数の増加が最も小さな変数を、非ゼロ変数集合から削除させる
請求項７記載の疎変数最適化プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、最適化すべき変数の多くが０になる制約を有する疎構造の変数を最適化する疎変数最適化装置、疎変数最適化方法および疎変数最適化プログラムに関する。
【背景技術】
【０００２】
凸関数の最適化は、機械学習、信号処理、パタン認識、金融工学など、さまざまな分野において利用される基本的な技術である。特に、近年の大規模変数を扱う最適化問題では、多くの変数が最適解において０となる、疎制約をもった最適化が重要となっている。
【０００３】
例えば、健康リスクスコアをロジスティック回帰モデルでモデル化し最適化する際には、変数のうちリスクに寄与するものだけが非ゼロとなり、リスクに寄与しない変数はゼロとなるようにモデルをコントロールする必要がある。これにより、例えば、どの健康診断項目がリスクに寄与しているかをモデル化できる。
【０００４】
また、例えばネットワークトラフィックの相関を分析する際には、精度行列（共分散行列の逆行列）を分析する事が一般的に行われる。この精度行列の算出時には、真に依存関係がない変数がゼロとなるように制約をつけて解くことが必要となる。これも変数に対する疎制約をもった凸関数の最適化問題となる。
【０００５】
一般に、疎制約をもった凸関数の最適化問題は、組み合わせ最適化問題になる。すなわち、この最適化問題は、どの変数がゼロ／非ゼロであるかを示す組合せを最適化する問題になる。大規模なケースでは、厳密解を求めることは計算時間の問題で事実上不可能である。そのため、一般的に、大きく２種類の近似最適化方法が提案されている。
【０００６】
一つは、疎制約を凸関数によって近似し、最適化問題全体を凸最適化へ変換する方法である。最も代表的な例として、変数の非ゼロ要素が多いという制約を、変数のL1ノルムが小さいと置き換える方法が挙げられる。ここで、L1ノルムは、凸関数である。
【０００７】
この方法として、例えば、疎制約をもつ線形回帰モデル最適化（Lasso。 非特許文献１参照。）、ロジスティック回帰モデル最適化（L1ロジスティック回帰。非特許文献２参照。）、精度行列最適化（Graph Lasso。非特許文献３参照。）などが挙げられる。これらの方法に共通する基本的なアイデアは、元の組み合わせ最適化問題自体を、解きやすい別の最適化問題に近似して解くことで計算の容易性を得ることと言える。
【０００８】
もう一つは、最適解の探索方法を工夫する方法で、一般には貪欲探索（Greedy Search ）と呼ばれる方法である。例えば、非特許文献４に記載されたOrthogonal Matching Pursuit （OMP ）と呼ばれる探索技術では、変数をすべてゼロの状態からスタートし、最も最適化の目的関数を下げる変数を前向きに一つずつ追加していく。
【０００９】
また、他にも、前向き後ろ向き貪欲探索（Forward-Backward Greedy Search; Foba。非特許文献５、非特許文献６参照）が近年提案されている。この方法は、OMP  のような前向きプロセスの間に、ある基準によって追加された変数を削除する探索を追加した方法で、理論的にも優れた性質を持つ事が証明されている。
【先行技術文献】
【非特許文献】
【００１０】
【非特許文献１】Tibshirani, R. (1996) Regression shrinkage and selection via the lasso. Journal of the Royal Statistical Society, B 58, 267-288, 2007.
【非特許文献２】Ng, A. Y. 2004. Feature selection, l1 vs. l2 regularization, and rotational invariance. In Proceedings of International Conference on Machine Learning, 2004.
【非特許文献３】Jerome Friedman, Trevor Hastie, and Robert Tibshirani. Sparse inverse covariance estimation with the graphical lasso. Biostatistics, 9:432-441, 2007.
【非特許文献４】Zhang, T. Sparse recovery with orthogonal matching pursuit under rip. IEEE Transactions on Information Theory, 57(9):6215-6221, 2011.
【非特許文献５】Zhang, T. Adaptive forward-backward greedy algorithm for learning sparse representations. IEEE Transactions on Information Theory, 57(7):4689-4708, 2011.
【非特許文献６】Jalali, A., Johnson, C.C., and Ravikumar, P.D. On learning discrete graphical models using greedy methods. Neural Information Processing Systems, 2011.
【発明の概要】
【発明が解決しようとする課題】
【００１１】
一方、非特許文献１〜３に記載された方法では、問題そのものを近似してしまうため、非特許文献４〜６に記載された方法と比較すると、解の精度が悪くなるという問題がある。
【００１２】
また、非特許文献４に記載された方法（OMP）では、一度追加された変数を後から削除する（すなわち、変数をゼロにする）プロセスがないため、最終的な解が悪くなるという問題がある。
【００１３】
また、非特許文献５〜６に記載された方法（Foba）では、閉形式の解が存在する場合には高速に計算する事が可能である。しかし、上述したロジスティック回帰や精度行列の最適化など、一般の凸関数では、１変数最適化であっても閉形式の解が存在しないため、非特許文献５〜６に記載された方法（Foba）では、特に変数の数が大規模になると大きな計算量が必要になるという問題がある。
【００１４】
そこで、本発明は、閉形式の解が存在しない場合であっても、計算量を抑えて最適化できる疎変数最適化装置、疎変数最適化方法および疎変数最適化プログラムを提供することを目的とする。
【課題を解決するための手段】
【００１５】
本発明による疎変数最適化装置は、変数の指定された値における目的関数の勾配を計算する勾配計算部と、変数集合に含まれる変数の一つを非ゼロ変数集合へ追加する追加変数選択部と、非ゼロ変数集合に含まれる変数に対して、最適化対象とする変数の値を最適化する変数最適化部と、非ゼロ変数集合に含まれる変数のうち、その変数を除いた場合に目的関数の増加が最も小さな変数を、その非ゼロ変数集合から削除する削除変数選択部と、最適化対象とする変数に対する目的関数の値を算出する目的関数評価部とを備え、勾配計算部は、最適化対象とする変数における目的関数の勾配を計算し、追加変数選択部は、変数集合に含まれる変数のうち、計算された勾配の絶対値が最も大きい変数を非ゼロ変数集合へ追加することを特徴とする。
【００１６】
本発明による疎変数最適化方法は、変数の指定された値における目的関数の勾配を計算し、変数集合に含まれる変数の一つを非ゼロ変数集合へ追加し、非ゼロ変数集合に含まれる変数に対して、最適化対象とする変数の値を最適化し、非ゼロ変数集合に含まれる変数のうち、その変数を除いた場合に目的関数の増加が最も小さな変数を、その非ゼロ変数集合から削除し、最適化対象とする変数に対する目的関数の値を算出し、勾配を計算する際、最適化対象とする変数における目的関数の勾配を計算し、変数集合に含まれる変数のうち、計算された勾配の絶対値が最も大きい変数を非ゼロ変数集合へ追加することを特徴とする。
【００１７】
本発明による疎変数最適化プログラムは、コンピュータに、変数の指定された値における目的関数の勾配を計算する勾配計算処理、変数集合に含まれる変数の一つを非ゼロ変数集合へ追加する追加変数選択処理、非ゼロ変数集合に含まれる変数に対して、最適化対象とする変数の値を最適化する変数最適化処理、非ゼロ変数集合に含まれる変数のうち、その変数を除いた場合に目的関数の増加が最も小さな変数を、その非ゼロ変数集合から削除する削除変数選択処理、および、最適化対象とする変数に対する目的関数の値を算出する目的関数評価処理を実行させ、勾配計算処理で、最適化対象とする変数における目的関数の勾配を計算させ、追加変数選択処理で、変数集合に含まれる変数のうち、計算された勾配の絶対値が最も大きい変数を非ゼロ変数集合へ追加させることを特徴とする。
【発明の効果】
【００１８】
本発明によれば、閉形式の解が存在しない場合であっても、疎構造の変数を計算量を抑えて最適化できる。
【図面の簡単な説明】
【００１９】
【図１】本発明による疎変数最適化装置の一実施形態を示すブロック図である。
【図２】疎変数最適化装置１００の動作例を示すフローチャートである。
【図３】本発明による疎変数最適化装置の概要を示すブロック図である。
【発明を実施するための形態】
【００２０】
本発明は、非特許文献５および非特許文献６で提案されているFobaの問題点を改善した技術である。その違いを説明するため、まずは、非特許文献５および非特許文献６に記載されたFobaの手順を説明する。なお、以下では値がゼロの変数の集合を変数プールと記し、値が非ゼロとして選択された変数を非ゼロ変数と記す。
【００２１】
Foba Step1: 最適化すべき変数をすべてゼロに初期化する。
【００２２】
Foba Step2: 変数プールから変数を１つ選び、１変数最適化問題を解く。これを変数プールの全ての変数に対して行い、最も目的関数を改善する変数を、非ゼロ変数に追加する。
【００２３】
Foba Step3: 非ゼロ変数と変数プールを固定し、変数を最適化する。すなわち、非ゼロ変数の値を最適化する。
【００２４】
Foba Step4: Foba Step3の前後で目的関数の改善が十分に小さい場合には、最適化を終了する。
【００２５】
Foba Step5: 非ゼロ変数から変数を１つ選び、その変数を除去した場合の目的関数の改悪を評価する。これを全ての非ゼロ変数に対して行い、目的関数の改悪が十分に小さい場合に、改悪が最も小さい変数を変数プールへ追加する。すなわち、変数をゼロにする。
【００２６】
Foba Step6: Foba Step5の処理を、「目的関数の改悪が十分に小さい」という条件を満たす変数がなくなるまで続ける。
【００２７】
Foba Step7: Foba Step2の処理へ移動して最適化を継続する。
【００２８】
非特許文献５および非特許文献６に記載されたFobaの手順を利用する場合、例えば、非特許文献５に記載された二乗損失関数のように、閉形式の解が存在する場合には高速に計算する事ができる。しかし、上述した一般の凸関数では、１変数最適化であっても閉形式の解が存在しないため、特に変数の数が大規模になると大きな計算量が必要になる。これは、Foba Step2において１変数最適化問題を解く必要があるためである。以下、この問題を解決する本発明の実施形態を図面を参照して説明する。
【００２９】
以下では、最適化すべき変数をw=(w1,…,wD)、目的関数をf(w)と表記する。また、全体の変数集合をF 、現在の非ゼロ変数集合をF(k)、現在の変数プール（F に含まれる変数のうち、F(k)に含まれていない、値が０の変数の集合）をFp(k)と表記する。
【００３０】
これらの表記を利用すると、変数の多くがゼロであるという制約付きの最適化問題は、一般に
min_w f(w) 
subject to |w|_0 <= K
と表される。ここで、|w|_0 はw のL0ノルムであり、非ゼロ要素の個数を表す。また、K は最適化される変数w にどの程度の非ゼロ要素が残るかを制御する入力パラメータである。
【００３１】
図１は、本発明による疎変数最適化装置の一実施形態を示すブロック図である。本実施形態の疎変数最適化装置１００は、データ入力装置１０１と、変数初期化処理部１０２と、勾配計算処理部１０３と、最適性判定処理部１０４と、追加変数選択処理部１０５と、変数最適化処理部１０６と、削除変数選択処理部１０７と、目的関数評価処理部１０８と、最適化結果出力装置１０９とを備えている。
【００３２】
疎変数最適化装置１００は、入力データ１１１を入力し、入力データ１１１に対して変数を最適化し、最適化結果１１２を出力する。
【００３３】
データ入力装置１０１は、入力データ１１１を入力するための装置であり、目的関数の種類や、以降の処理に必要なパラメータなどを入力する。また、例えば、前述の健康リスクスコアのロジスティック回帰モデルをデータから最適化する場合のように、必要に応じて最適化に必要なデータも入力される。
【００３４】
変数初期化処理部１０２は、k=0 に設定し、F(k)を空集合に、Fp(k)を全変数（F ）に、w をゼロベクトルにそれぞれ初期化する。
【００３５】
勾配計算処理部１０３は、f(w)の現在のw における勾配を算出する。
【００３６】
最適性判定処理部１０４は、勾配計算処理部１０３で計算されたf(w)の勾配ベクトルの絶対値の最大値が十分に小さいかを判定する。
【００３７】
追加変数選択処理部１０５では、Fp(k) に含まれる変数のうち、f(w)の現在のw に対する勾配の絶対値が、最も大きい変数を１つ選択し、Fp(k) から除去してF(k)へ追加する。このとき、k=k+1 と計算する。
【００３８】
変数最適化処理部１０６は、F(k)に含まれる変数に対して、w の値を最適化する。なお、このときに最適化されたf(w) の値が算出さるため、変数最適化処理部１０６は、更新前のf(w)の値と、更新後のf(w)の値の差分をD(k)として算出できる。
【００３９】
削除変数選択処理部１０７は、F(k)に含まれる変数のうち、その変数を除いた場合にf(w)の増加が最も小さな変数を１つ選択し、F(k)から除去してFp(k) へ追加する。このとき、k=k-1と計算する。
【００４０】
目的関数評価処理部１０８は、w に対して、f(w)の値を算出する。
【００４１】
最適化結果出力装置１０９は、最適化されたw 、F(k)及びその他必要なパラメータを、最適化結果１１２として出力する。
【００４２】
変数初期化処理部１０２と、勾配計算処理部１０３と、最適性判定処理部１０４と、追加変数選択処理部１０５と、変数最適化処理部１０６と、削除変数選択処理部１０７と、目的関数評価処理部１０８とは、例えば、プログラム（疎変数最適化プログラム）に従って動作するコンピュータのＣＰＵによって実現される。
【００４３】
例えば、プログラムは、疎変数最適化装置１００の記憶部（図示せず）に記憶され、ＣＰＵは、そのプログラムを読み込み、プログラムに従って、変数初期化処理部１０２、勾配計算処理部１０３、最適性判定処理部１０４、追加変数選択処理部１０５、変数最適化処理部１０６、削除変数選択処理部１０７および目的関数評価処理部１０８して動作してもよい。また、上記プログラムは、コンピュータ読み取り可能な記憶媒体に記憶されていてもよい。
【００４４】
また、変数初期化処理部１０２と、勾配計算処理部１０３と、最適性判定処理部１０４と、追加変数選択処理部１０５と、変数最適化処理部１０６と、削除変数選択処理部１０７と、目的関数評価処理部１０８とは、それぞれが専用のハードウェアで実現されていてもよい。
【００４５】
次に、本実施形態の疎変数最適化装置１００の動作を説明する。図２は、本実施形態の疎変数最適化装置１００の動作例を示すフローチャートである。
【００４６】
まず、データ入力装置１０１は、入力データ１１１を入力する（ステップＳ１００）。次に、変数初期化処理部１０２は、k=0 設定し、F(k)を空集合に、Fp(k)を全変数（F ）に、w をゼロベクトルにそれぞれ初期化する（ステップＳ１０１）。
【００４７】
次に、勾配計算処理部１０３は、f(w)の現在のw 対する勾配を算出する（ステップＳ１０２）。次に、最適性判定処理部１０４は、ステップＳ１０２で算出された各変数の勾配の絶対値のうち最も大きいものが、事前にパラメータとして入力された閾値よりも小さいか否かを判定する（ステップＳ１０３）。この処理は、w が最適化されたか否かを判定する処理である。
【００４８】
算出結果が閾値よりも小さい場合（ステップＳ１０３におけるＹｅｓ）、ステップＳ１０９へ処理が移り、算出結果が閾値よりも以上の場合（ステップＳ１０３におけるＮｏ）、ステップＳ１０４へ処理が移る。
【００４９】
ステップＳ１０３において、勾配の絶対値の最大値が閾値以上の場合、追加変数選択処理部１０５は、勾配の絶対値が最大の変数をFp(k) から除去し、その変数をF(k)へ追加する（ステップＳ１０４）。
【００５０】
次に、変数最適化処理部１０６は、F(k)に含まれる変数を、f(w)に対して最適化する（ステップＳ１０５）。なお、この処理の直前の処理が、変数を追加するステップＳ１０４の処理である場合、変数最適化処理部１０６は、更新前のf(w)の値と更新後のf(w)の値の差分をD(k)として算出する。
【００５１】
次に、目的関数評価処理部１０８は、F(k)に対するf(w)の値を算出する。この算出された値を（ｉ）とする。また、目的関数評価処理部１０８は、F(k)に含まれる変数ごとに、その変数の値を0 した場合のf(w)の値を算出する。この算出された値を（ｉｉ）とする（ステップＳ１０６）。
【００５２】
次に、削除変数選択処理部１０７は、ステップＳ１０６において算出された（ｉｉ）と（ｉ）の値の差の最小値が、a * D(k)よりも小さいか否かを判定する（ステップＳ１０７）。この処理は、変数を削除すべきか否かを判定する処理である。ただし、a は0 < a < 1 を満たす事前に入力される閾値パラメータである。
【００５３】
差の最小値がa * D(k)よりも小さい場合（ステップＳ１０７におけるＹｅｓ）、削除変数選択処理部１０７は、変数を削除可能と判定する。その後、ステップＳ１０８へ処理が移る。一方、差の最小値がa * D(k)以上の場合（ステップＳ１０７におけるＮｏ）、削除変数選択処理部１０７は、削除可能な変数はないと判定する。その後、ステップＳ１０２へ処理が移る。
【００５４】
ステップＳ１０７において、変数を削除可能と判定された場合、削除変数選択処理部１０７は、ステップＳ１０６で算出された（ｉｉ）と（ｉ）の値の差が最も小さくなる変数をF(k)から除去し、Fp(k) へ追加する（ステップＳ１０８S108）。その後、ステップＳ１０５へ処理が移る。
【００５５】
一方、ステップＳ１０３において、勾配の絶対値の最大値が閾値以上よりも小さい場合、最適であると判定され、最適化結果出力装置１０９は、最適化結果１１２を出力する（ステップＳ１０９）。
【００５６】
以上のように、本実施形態によれば、勾配計算処理部１０３が、w におけるf(w)の勾配を計算し、追加変数選択処理部１０５が、Fp(k) に含まれる変数のうち、計算された勾配の絶対値が最も大きい変数をF(k)へ追加し、変数最適化処理部１０６が、F(k)に含まれる変数に対して、w の値を最適化する。また、削除変数選択処理部１０７が、F(k)に含まれる変数のうち、その変数を除いた場合にf(w)の増加が最も小さな変数を、F(k)から削除し、目的関数評価処理部１０８が、w に対するf(w)の値を算出する。よって、閉形式の解が存在しない場合であっても、疎構造の変数を計算量を抑えて最適化できる。
【００５７】
すなわち、本実施形態による方法が、一般的なFobaと本質的に相違する点は、変数の追加処理である。一般的なFobaでは、変数を追加するステップであるFoba Step2において、Fp(k)に含まれる変数の全てに対する最適化問題を解く必要がある。そのため、目的関数が二乗損失のような特殊ケースを除き、計算コストが極めて高い。一方、本実施形態によれば、ステップＳ１０３およびステップＳ１０４において、Fp(k) に含まれる変数の勾配だけが計算されるため、高速に追加すべき変数を算出できる。
【実施例１】
【００５８】
以下、具体的な実施例により本発明を説明するが、本発明の範囲は以下に説明する内容に限定されない。第１の実施例では、本発明による疎変数最適化装置を応用して、健康診断ログから健康リスク分析を行う場合を例に説明する。
【００５９】
生活習慣や健康診断検査値と、健康や疾病リスクの関係性をモデル化し、リスクを予測することは、疾病予防やリスク分析、生活習慣指導などに応用可能である。
【００６０】
また、リスクの予測関数が複雑すぎると人間に理解不可能になる。そのため、入力される変数（生活習慣や健康診断検査値の各種項目）のうち、少数の変数でリスク予測関数を構成することが重要である。なお、少数の変数で予測するということは、変数の多くが０で疎であると言える。
【００６１】
ロジスティック回帰モデルによるリスクスコア関数の学習を、上記応用の一例として説明する。ロジスティック回帰モデルは、あるリスク指標（例えば、血圧が閾値より高いかどうか）を、リスクが発現する確率p （p = 1 /(1 + exp(-wx)）としてモデル化する方法で、健康や医療分野の応用で典型的に用いられるモデルである。
【００６２】
ロジスティック回帰モデルの学習には、典型的にL2罰則付き尤度関数がよく用いられる。本発明では、f(w)= Σn log (1 + exp (-yn wxn)) + λ||w||2を満たす目的関数に相当する。
【００６３】
ただし、(xn, yn) (n=1, …, N) は、学習サンプルである。xnは、生活習慣や健康診断検査値の各項目をベクトル化したデータを表わす。yn(+1 or -1)は、xnに対応するリスクの有無を表わす。λは、L2罰則項の強さを示す入力パラメータを表わす。||w||2は、w のL2ノルムを表わす。
【００６４】
すなわち、勾配計算処理部１０３が、ロジスティック回帰モデルを表わす目的関数の現在のw における勾配を算出し、削除変数選択処理部１０７が、この目的関数の増加が最も小さな変数をF(k)から削除すればよい。
【００６５】
本発明を利用することで、パラメータw の要素の多くが0 で、リスクに関係する少数の要素のみが非ゼロであるモデルを得ることができる。本発明を利用することによって、例えば、高血圧のリスク予測関数を最適化した場合には、肥満の度合いや、運動習慣の有無など、高血圧リスクに直結する少数の変数のみを利用した、人間に理解可能なモデルを得ることができる。
【実施例２】
【００６６】
第２の実施例では、本発明による疎変数最適化装置を応用して、健康診断ログの間の相関分析を行う場合を例に説明する。
【００６７】
生活習慣や健診検査値の各項目には、複雑な相関関係があり、通常の相関係数を用いた分析を行う場合、実際には相関がない変数間に相関があるように誤分析をする可能性がある。
【００６８】
例えば、肥満と血圧の相関が高く、肥満と血糖値の相関が高い場合、血圧と血糖値の間の相関は高くなかったとしても肥満という変数を介して、見かけ上、血圧と血糖値の相関係数が高くなる。
【００６９】
このような誤分析を防ぐためには、共分散行列の逆行列（以下、精度行列）が相関の指標として利用されることが一般的である。なお、精度行列の要素は、対応する変数間の条件付相関を示す。すなわち、精度行列の要素は、他の変数が全て与えられた場合の相関を示す。上記の例では、肥満を介して血圧と血糖値の間の相関が見かけ上高くなっていても、条件付相関は小さくなる。
【００７０】
精度行列をデータから推定する場合、データにノイズが含まれているため、実際には相関がない変数間に対応する要素もゼロにならないという問題がある。そこで、精度行列の非対角要素（変数間の条件付相関）の多くが０になるように最適化することが重要である。
【００７１】
精度行列をS 、データから推定された共分散行列をC とすると、本発明では、目的関数がf(S) = S*C - log det (S)とし、S の非対角の非ゼロ成分の個数がK 以下であると解釈することができる。ただし、S*C は、S とC の内積を表わし、det(S)は、S の行列積を表す。
【００７２】
すなわち、最適化すべき変数w が、精度行列S の非対角要素に相当し、目的関数f(w)が精度行列S と共分散行列C に基づいて定められる共分散関数f(S)に相当し、F(k)が、精度行列S の非対角の非ゼロ成分に相当する。
【００７３】
このとき、勾配計算処理部１０３は、精度行列S の非対角要素におけるf(S)の勾配を計算し、変数最適化処理部１０６は、精度行列S の非対角の非ゼロ成分に対して、その精度行列の非対角要素を最適化する。また、削除変数選択処理部１０７は、精度行列S の非対角の非ゼロ成分のうち、その非ゼロ成分を除いた場合にf(S)の増加が最も小さな非ゼロ成分をゼロとし、目的関数評価処理部１０８は、精度行列S の非対角要素に対するf(S)の値を算出する。
【００７４】
このように、本発明を利用して疎な精度行列を最適化することで、生活習慣や健診検査値の各項目の間の相関関係を発見できる。
【００７５】
次に、本発明の概要を説明する。図３は、本発明による疎変数最適化装置の概要を示すブロック図である。本発明による疎変数最適化装置は、変数の指定された値（具体的には、現在の最適値）における目的関数（例えば、f(w)）の勾配を計算する勾配計算部８１（例えば、勾配計算処理部１０３）と、変数集合（例えば、Fp(k) ）に含まれる変数の一つを非ゼロ変数集合（例えば、F(k)）へ追加する追加変数選択部８２（例えば、追加変数選択処理部１０５）と、非ゼロ変数集合に含まれる変数に対して、最適化対象とする変数（例えば、w ）の値を最適化する変数最適化部８３（例えば、変数最適化処理部１０６）と、非ゼロ変数集合に含まれる変数のうち、その変数を除いた場合に目的関数の増加（例えば、a * D(k)）が最も小さな変数を、その非ゼロ変数集合から削除する削除変数選択部８４（例えば、削除変数選択処理部１０７）と、最適化対象とする変数に対する目的関数の値を算出する目的関数評価部８５（例えば、目的関数評価処理部１０８）とを備えている。
【００７６】
勾配計算部８１は、最適化対象とする変数における目的関数の勾配を計算し、追加変数選択部８２は、変数集合に含まれる変数のうち、計算された勾配の絶対値が最も大きい変数を非ゼロ変数集合へ追加する。
【００７７】
そのような構成により、閉形式の解が存在しない場合であっても、疎構造の変数を計算量を抑えて最適化できる。
【００７８】
また、勾配計算部８１は、ロジスティック回帰モデルを表わす目的関数（例えば、L2罰則付き尤度関数）の、最適化対象とする変数における勾配を算出してもよい。そして、削除変数選択部８４は、目的関数の増加が最も小さな変数を、非ゼロ変数集合から削除してもよい。
【００７９】
他にも、勾配計算部８１は、目的関数として共分散関数（例えば、f(S)）を使用し、共分散行列の逆行列である精度行列（例えば、S ）の非対角要素における目的関数の勾配を計算してもよい。このとき、変数最適化部８３は、精度行列の非対角の非ゼロ成分に対して、その精度行列の非対角要素を最適化し、削除変数選択部８４は、精度行列の非対角の非ゼロ成分のうち、その非ゼロ成分を除いた場合に目的関数の増加が最も小さな非ゼロ成分をゼロとし、目的関数評価部８５は、精度行列の非対角要素に対する目的関数の値を算出してもよい。
【００８０】
また、疎変数最適化装置は、算出された勾配の絶対値のうち最も大きいものが、予め定められた閾値よりも小さい場合、最適化対象とする変数が最適化されたと判定する最適性判定処理部（例えば、最適性判定処理部１０４）を備えていてもよい。
【００８１】
以上、実施形態及び実施例を参照して本願発明を説明したが、本願発明は上記実施形態および実施例に限定されるものではない。本願発明の構成や詳細には、本願発明のスコープ内で当業者が理解し得る様々な変更をすることができる。
【００８２】
この出願は、２０１３年２月２０日に出願された米国仮出願第６１／７６７，０３８号を基礎とする優先権を主張し、その開示の全てをここに取り込む。
【符号の説明】
【００８３】
１０１  データ入力装置
１０２  変数初期化処理部
１０３  勾配計算処理部
１０４  最適性判定処理部
１０５  追加変数選択処理部
１０６  変数最適化処理部
１０７  削除変数選択処理部
１０８  目的関数評価処理部
１０９  最適化結果出力装置
【図１】
2014160456.tif 000003
【図２】
2014160456.tif 000004
【図３】
2014160456.tif 000005