(57)【要約】【課題】複数の選択候補の中からより最適な変数をユーザに選択させることができる対話的変数選択装置を提供する。【解決手段】最適度算出手段７１は、変数集合に含まれる第一の変数を追加変数の候補にした場合の最適度を、目的関数を用いて算出する。追加閾値算出部７２は、第一の変数を追加変数の候補とすべきか否かを判断するための基準を表わす最適度の閾値である追加閾値を、算出された最適度に基づいて算出する。目的関数値算出部８１は、最適化対象とする変数を用いて算出される目的関数の値と、その最適化対象とする変数から非ゼロ変数集合に含まれる第二の変数を除いて算出される目的関数の値との差分である目的関数値を算出する。削除閾値算出部８２は、第二の変数を非ゼロ変数集合から削除すべきか否かを判断するための基準を表わす目的関数値の閾値である削除閾値を、算出された目的関数値に基づいて算出する。【選択図】図１３
2014160457.tif 000002
【特許請求の範囲】
【請求項１】
ユーザと対話的に変数を選択する対話的変数選択装置であって、
変数集合の中から非ゼロ変数集合に追加すべき変数である追加変数の候補を算出する追加変数候補算出部と、
前記非ゼロ変数集合に含まれる変数に対して、最適化された変数において最小値をとる目的関数を最小化することにより、最適化対象とする変数を更新する最適変数選択更新部と、
前記非ゼロ変数集合から削除すべき変数である削除変数の候補を算出する削除変数候補算出部と、
前記追加変数の候補と前記削除変数の候補の少なくとも一方を出力する変数選択結果出力部とを備え、
前記追加変数候補算出部は、
前記変数集合に含まれる第一の変数を前記追加変数の候補にした場合の最適度を、前記目的関数を用いて算出する最適度算出手段と、
前記第一の変数を前記追加変数の候補とすべきか否かを判断するための基準を表わす前記最適度の閾値である追加閾値を、算出された最適度に基づいて算出する追加閾値算出部とを含み、
前記削除変数候補算出部は、
前記最適化対象とする変数を用いて算出される前記目的関数の値と、当該最適化対象とする変数から前記非ゼロ変数集合に含まれる第二の変数を除いて算出される前記目的関数の値との差分である目的関数値を算出する目的関数値算出部と、
前記第二の変数を前記非ゼロ変数集合から削除すべきか否かを判断するための基準を表わす前記目的関数値の閾値である削除閾値を、算出された目的関数値に基づいて算出する削除閾値算出部とを含む
ことを特徴とする対話的変数選択装置。
【請求項２】
最適度算出手段は、第一の変数に対して目的関数を最小化する１変数の最適化問題を解くことにより、その目的関数の値を最適度として算出する
請求項１記載の対話的変数選択装置。
【請求項３】
最適度算出手段は、第一の変数について、最適化対象とする変数における目的関数の勾配を最適度として算出する
請求項１記載の対話的変数選択装置。
【請求項４】
非ゼロ変数集合の中から、変数集合に含まれる変数と交換する対象として指定された変数を入力し、前記指定された変数と交換すべき変数の候補を変数集合の中から算出する交換変数候補算出部を備えた
請求項１から請求項３のうちのいずれか１項に記載の対話的変数選択装置。
【請求項５】
交換変数候補算出部は、指定された変数を追加変数の候補から除いた変数の集合を用いて目的関数を最適化する最適変数一次更新部と、
変数集合に含まれる変数と指定された変数とを交換すべきか否かを判断するための基準を表わす閾値である交換閾値を、算出された最適度に基づいて算出する交換閾値算出部とを含み、
最適度算出手段は、指定された変数を含む変数集合に含まれる第一の変数を追加変数の候補にした場合の最適度を、目的関数を用いて算出する
請求項４記載の対話的変数選択装置。
【請求項６】
変数選択結果出力部は、追加閾値に基づいて追加変数の候補とすべきと判断される変数、または、削除閾値に基づいて追加変数の候補から削除すべきと判断される変数を出力する
請求項１から請求項５のうちのいずれか１項に記載の対話的変数選択装置。
【請求項７】
ユーザと対話的に変数を選択する対話的変数選択方法であって、
変数集合の中から非ゼロ変数集合に追加すべき変数である追加変数の候補を算出し、
前記非ゼロ変数集合に含まれる変数に対して、最適化された変数において最小値をとる目的関数を最小化することにより、最適化対象とする変数を更新し、
前記非ゼロ変数集合から削除すべき変数である削除変数の候補を算出し、
前記追加変数の候補と前記削除変数の候補の少なくとも一方を出力し、
前記追加変数の候補を算出する際、前記変数集合に含まれる第一の変数を前記追加変数の候補にした場合の最適度を、前記目的関数を用いて算出し、前記第一の変数を前記追加変数の候補とすべきか否かを判断するための基準を表わす前記最適度の閾値である追加閾値を、算出された最適度に基づいて算出し、
前記削除変数の候補を算出する際、前記最適化対象とする変数を用いて算出される前記目的関数の値と、当該最適化対象とする変数から前記非ゼロ変数集合に含まれる第二の変数を除いて算出される前記目的関数の値との差分である目的関数値を算出し、第二の変数を前記非ゼロ変数集合から削除すべきか否かを判断するための基準を表わす前記目的関数値の閾値である削除閾値を、算出された目的関数値に基づいて算出する
ことを特徴とする対話的変数選択方法。
【請求項８】
最適度を算出する際、第一の変数に対して目的関数を最小化する１変数の最適化問題を解くことにより、その目的関数の値を最適度として算出する
請求項７記載の対話的変数選択方法。
【請求項９】
ユーザと対話的に変数を選択するコンピュータに適用される対話的変数選択プログラムであって、
前記コンピュータに、
変数集合の中から非ゼロ変数集合に追加すべき変数である追加変数の候補を算出する追加変数候補算出処理、
前記非ゼロ変数集合に含まれる変数に対して、最適化された変数において最小値をとる目的関数を最小化することにより、最適化対象とする変数を更新する最適変数選択更新処理、
前記非ゼロ変数集合から削除すべき変数である削除変数の候補を算出する削除変数候補算出処理、および、
前記追加変数の候補と前記削除変数の候補の少なくとも一方を出力する変数選択結果出力処理を実行させ、
前記追加変数候補算出処理で、
前記変数集合に含まれる第一の変数を前記追加変数の候補にした場合の最適度を、前記目的関数を用いて算出する最適度算出処理、および、
前記第一の変数を前記追加変数の候補とすべきか否かを判断するための基準を表わす前記最適度の閾値である追加閾値を、算出された最適度に基づいて算出する追加閾値算出処理を実行させ、
前記削除変数候補算出処理で、
前記最適化対象とする変数を用いて算出される前記目的関数の値と、当該最適化対象とする変数から前記非ゼロ変数集合に含まれる第二の変数を除いて算出される前記目的関数の値との差分である目的関数値を算出する目的関数値算出処理、および、
第二の変数を前記非ゼロ変数集合から削除すべきか否かを判断するための基準を表わす前記目的関数値の閾値である削除閾値を、算出された目的関数値に基づいて算出する削除閾値算出処理
を実行させるための対話的変数選択プログラム。
【請求項１０】
コンピュータに、
最適度算出処理で、第一の変数に対して目的関数を最小化する１変数の最適化問題を解くことにより、その目的関数の値を最適度として算出させる
請求項９記載の対話的変数選択プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、最適な変数をユーザと対話的に選択するための対話的変数選択装置、対話的変数選択方法および対話的変数選択プログラムに関する。
【背景技術】
【０００２】
変数選択問題は、機械学習、信号処理、パタン認識、金融工学など、さまざまな応用分野において重要な基本的な技術である。
【０００３】
例えば、健康リスクスコアをロジスティック回帰モデルでモデル化し最適化する際には、変数のうちリスクに寄与する変数だけを選択し、リスクに寄与しない変数はゼロとなるようにモデルをコントロールする必要がある。
【０００４】
また、例えばネットワークトラフィックの相関を分析する際には、精度行列（共分散行列の逆行列）を分析する事が一般的に行われる。この精度行列の算出時には、真に依存関係がない変数がゼロになるように制約をつけて解くことが必要となり、変数選択の問題として扱うことが可能である。
【０００５】
一方、変数の数が大きな大規模な問題では、ユーザの手による変数選択が難しいため、機械による支援が重要になる。このような支援をする目的で、一般に、大きく分けて二種類の技術が提案されている。
【０００６】
一つ目は、機械によってデータから自動的に変数を最適選択する技術（feature selection, attribute selection）である。この技術として、例えば、凸最適化に基づく方法（疎制約をもつ線形回帰モデル最適化（Lasso。 非特許文献１参照。）、ロジスティック回帰モデル最適化（L1ロジスティック回帰。非特許文献２参照。）、精度行列最適化（Graph Lasso。非特許文献３参照。）など）が挙げられる。他にも、この技術として、貪欲探索（Greedy Search）に基づく方法（Orthogonal Matching Pursuit（OMP。非特許文献４参照）、前向き後ろ向き貪欲探索（Forward-Backward Greedy Search; Foba。非特許文献５、非特許文献６参照）など）が挙げられる。
【０００７】
二つ目は、機械に変数のスコアリングや順序付けをさせ、その結果に対して対話的にユーザに変数を選択させる技術である。
【先行技術文献】
【非特許文献】
【０００８】
【非特許文献１】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.
【発明の概要】
【発明が解決しようとする課題】
【０００９】
非特許文献１〜６に記載されているような機械による自動最適化は、データ数が十分にあれば高精度に変数選択をできるという利点があるが、一方で変数選択結果をユーザが制御することが難しいという欠点がある。
【００１０】
また、有限のデータ数を用いて変数を選択する場合、一般的に精度に統計的に有意な差がない複数の変数選択結果が存在する。その中からユーザにとって好ましい結果を選択することが重要になるが、非特許文献１〜６に記載されているような機械による自動変数選択では、そのような選択方法は自明ではない。統計的に有意な差がないモデルが多数存在すると、ユーザがすべてを比較して選択することは難しくなるという問題がある。
【００１１】
一方、変数に順序付けを行い、ユーザによって選択させる方法は、ユーザが結果を制御可能であるという利点を持つ。しかし、一般的な方法では変数の順序付けの基準が必ずしも目的達成（例えば予測精度の最適化）に整合していないという問題がある。また、一般的な方法では、順序付けしたときに第何位までが信頼できる変数かをユーザが客観的に決めることが難しいという問題がある。
【００１２】
そこで、本発明は、複数の選択候補の中からより最適な変数をユーザに選択させることができる対話的変数選択装置、対話的変数選択方法および対話的変数選択プログラムを提供することを目的とする。
【課題を解決するための手段】
【００１３】
本発明による対話的変数選択装置は、ユーザと対話的に変数を選択する対話的変数選択装置であって、変数集合の中から非ゼロ変数集合に追加すべき変数である追加変数の候補を算出する追加変数候補算出部と、非ゼロ変数集合に含まれる変数に対して、最適化された変数において最小値をとる目的関数を最小化することにより、最適化対象とする変数を更新する最適変数選択更新部と、非ゼロ変数集合から削除すべき変数である削除変数の候補を算出する削除変数候補算出部と、追加変数の候補と削除変数の候補の少なくとも一方を出力する変数選択結果出力部とを備え、追加変数候補算出部が、変数集合に含まれる第一の変数を追加変数の候補にした場合の最適度を、目的関数を用いて算出する最適度算出手段と、第一の変数を追加変数の候補とすべきか否かを判断するための基準を表わす最適度の閾値である追加閾値を、算出された最適度に基づいて算出する追加閾値算出部とを含み、削除変数候補算出部は、最適化対象とする変数を用いて算出される目的関数の値と、その最適化対象とする変数から非ゼロ変数集合に含まれる第二の変数を除いて算出される目的関数の値との差分である目的関数値を算出する目的関数値算出部と、第二の変数を非ゼロ変数集合から削除すべきか否かを判断するための基準を表わす目的関数値の閾値である削除閾値を、算出された目的関数値に基づいて算出する削除閾値算出部とを含むことを特徴とする。
【００１４】
本発明による対話的変数選択方法は、ユーザと対話的に変数を選択する対話的変数選択方法であって、変数集合の中から非ゼロ変数集合に追加すべき変数である追加変数の候補を算出し、非ゼロ変数集合に含まれる変数に対して、最適化された変数において最小値をとる目的関数を最小化することにより、最適化対象とする変数を更新し、非ゼロ変数集合から削除すべき変数である削除変数の候補を算出し、追加変数の候補と削除変数の候補の少なくとも一方を出力し、追加変数の候補を算出する際、変数集合に含まれる第一の変数を追加変数の候補にした場合の最適度を、目的関数を用いて算出し、第一の変数を追加変数の候補とすべきか否かを判断するための基準を表わす最適度の閾値である追加閾値を、算出された最適度に基づいて算出し、削除変数の候補を算出する際、最適化対象とする変数を用いて算出される目的関数の値と、その最適化対象とする変数から非ゼロ変数集合に含まれる第二の変数を除いて算出される目的関数の値との差分である目的関数値を算出し、第二の変数を非ゼロ変数集合から削除すべきか否かを判断するための基準を表わす目的関数値の閾値である削除閾値を、算出された目的関数値に基づいて算出することを特徴とする。
【００１５】
本発明による対話的変数選択プログラムは、ユーザと対話的に変数を選択するコンピュータに適用される対話的変数選択プログラムであって、コンピュータに、変数集合の中から非ゼロ変数集合に追加すべき変数である追加変数の候補を算出する追加変数候補算出処理、非ゼロ変数集合に含まれる変数に対して、最適化された変数において最小値をとる目的関数を最小化することにより、最適化対象とする変数を更新する最適変数選択更新処理、非ゼロ変数集合から削除すべき変数である削除変数の候補を算出する削除変数候補算出処理、および、追加変数の候補と削除変数の候補の少なくとも一方を出力する変数選択結果出力処理を実行させ、追加変数候補算出処理で、変数集合に含まれる第一の変数を追加変数の候補にした場合の最適度を、目的関数を用いて算出する最適度算出処理、および、第一の変数を追加変数の候補とすべきか否かを判断するための基準を表わす最適度の閾値である追加閾値を、算出された最適度に基づいて算出する追加閾値算出処理を実行させ、削除変数候補算出処理で、最適化対象とする変数を用いて算出される目的関数の値と、その最適化対象とする変数から非ゼロ変数集合に含まれる第二の変数を除いて算出される目的関数の値との差分である目的関数値を算出する目的関数値算出処理、および、第二の変数を非ゼロ変数集合から削除すべきか否かを判断するための基準を表わす目的関数値の閾値である削除閾値を、算出された目的関数値に基づいて算出する削除閾値算出処理を実行させることを特徴とする。
【発明の効果】
【００１６】
本発明によれば、複数の選択候補の中からより最適な変数をユーザに選択させることができる。
【図面の簡単な説明】
【００１７】
【図１】本発明による対話的変数選択装置の第１の実施形態の構成例を示すブロック図である。
【図２】第１の実施形態の追加変数候補算出処理部１０４の構成例を示すブロック図である。
【図３】第１の実施形態の削除変数候補算出処理部１０５の構成例を示すブロック図である。
【図４】第１の実施形態の対話的変数選択装置１００の動作例を示すフローチャートである。
【図５】本発明による対話的変数選択装置の第２の実施形態の構成例を示すブロック図である。
【図６】第２の実施形態の追加変数候補算出処理部２０１の構成例を示すブロック図である。
【図７】第２の実施形態の対話的変数選択装置２００の動作例を示すフローチャートである。
【図８】本発明による対話的変数選択装置の第３の実施形態の構成例を示すブロック図である。
【図９】第３の実施形態の交換変数候補算出処理部３０１の構成例を示すブロック図である。
【図１０】第３の実施形態の対話的変数選択装置３００の動作例を示すフローチャートである。
【図１１】本発明による対話的変数選択装置の第４の実施形態の構成例を示すブロック図である。
【図１２】第４の実施形態の交換変数候補算出処理部４０１の構成例を示すブロック図である。
【図１３】本発明による対話的変数選択装置の概要を示すブロック図である。
【発明を実施するための形態】
【００１８】
以下、本発明の実施形態を図面を参照して説明する。本発明は、順序付けした変数をユーザに提示し、ユーザに対話的に変数を選択させる技術である。
【００１９】
以下では、最適化すべき変数を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 にどの程度の非ゼロ要素が残るかを制御する入力パラメータである。
【００２１】
実施形態１．
図１は、本発明による対話的変数選択装置の第１の実施形態の構成例を示すブロック図である。本実施形態の対話的変数選択装置１００は、データ入力装置１０１と、データ記憶部１０２と、変数選択結果記憶部１０３と、追加変数候補算出処理部１０４と、削除変数候補算出処理部１０５と、変数選択候補出力装置１０６と、変数選択指示入力装置１０７と、最適変数選択更新処理部１０８と、変数選択結果出力装置１０９とを備えている。
【００２２】
対話的変数選択装置１００は、入力データ１１１と変数選択指示１１４を入力し、変数選択候補１１３と変数選択結果１１２を出力する。
【００２３】
データ入力装置１０１は、変数選択に必要なデータ及びパラメータを入力する。変数選択に必要なデータとは、例えば、前述の健康リスクスコアのロジスティック回帰モデルを用いて変数を選択する場合に必要な学習データを示す。
【００２４】
データ記憶部１０２は、入力データ１１１を記憶する。データ記憶部１０２は、例えば、磁気ディスク等により実現される。
【００２５】
変数選択結果記憶部１０３は、変数を選択した結果として、F(k)、Fp(k) 、w(k)、f(w(k)) を記憶する。ただし、w(k)はF(k)に対応するw の推定値である。なお、初期状態では、k=0 に設定され、F(k)は空集合に、Fp(k)は全変数に、w(k)はゼロベクトルにそれぞれ初期化されている。変数選択結果記憶部１０３は、例えば、磁気ディスク等により実現される。
【００２６】
追加変数候補算出処理部１０４は、Fp(k)内の変数からF(k)に追加する変数の候補を算出する。具体的には、追加変数候補算出処理部１０４は、Fp(k) に含まれる変数からF(k)に１つ追加する場合に、選択すべき変数の候補を算出する。
【００２７】
図２は、本実施形態の追加変数候補算出処理部１０４の構成例を示すブロック図である。本実施形態の追加変数候補算出処理部１０４は、１変数最適化処理部１０４−１と、追加閾値算出処理部１０４−２とを含む。
【００２８】
１変数最適化処理部１０４−１は、Fp(k) に含まれる各変数に対応するw の要素を、F(k)とw(k)を固定して最適化する。具体的には、１変数最適化処理部１０４−１は、j 番目の変数について、wjに対してf(w)を最小化する１変数の最適化問題を解く。以下、j 番目の変数に対する目的変数値をfj(w(k))と表記する。この場合、追加すべき変数の候補として、fj(w(k))が小さい変数の方が、f(w)を小さくできる可能性がより高く有望であると言える。
【００２９】
追加閾値算出処理部１０４−２は、fj(w(k))がどの程度小さい場合に、追加候補として有望であるかを表わす閾値を算出する。具体的には、追加閾値算出処理部１０４−２は、fj(w(k))を昇順に並べたときの上位K - k の平均値に、0 <= λ <=1 を満たすパラメータλを乗じたものを閾値とする。
【００３０】
削除変数候補算出処理部１０５は、F(k)から削除する変数の候補を算出する。具体的には、削除変数候補算出処理部１０５は、F(k)に含まれる変数から１つ削除する場合に、選択すべき変数の候補を算出する。
【００３１】
図３は、本実施形態の削除変数候補算出処理部１０５の構成例を示すブロック図である。本実施形態の削除変数候補算出処理部１０５は、目的関数値算出処理部１０５−１と、削除閾値算出処理部１０５−２とを含む。
【００３２】
目的関数値算出処理部１０５−１は、F(k)に含まれる変数をi とすると、f(w(k) - wi(k) ei)を、各i について算出する。ただし、wi(k) は、w(k)のi 番目の要素であり、eiは、w(k)のi 番目の要素に対応する規程である。すなわち、w(k) - wi(k) ei は、w(k)のi 番目の要素を０にする処理に相当する。
【００３３】
削除閾値算出処理部１０５−２は、変数を削除した場合の目的関数の増分f(w(k) - wi(k) ei) - f(w(k))がどの程度小さい場合に、その変数が削除候補として有望であるかを表わす閾値を算出する。具体的には、削除閾値算出処理部１０５−２は、変数選択結果記憶部１０３に記憶されている、f(w(k)) - f(w(k-1)) の値に、0 <= γ <= λ <=1 を満たすパラメータγを乗じたものを閾値とする。
【００３４】
変数選択候補出力装置１０６は、Fp(k) 及び追加変数候補算出処理部１０４で算出されたfj(w(k))と追加閾値、F(k)及び削除変数候補算出処理部１０５で算出されたf(w(k) - wi(k) ei)と削除閾値を変数選択候補１１３として出力する。
【００３５】
変数選択候補出力装置１０６は、任意の形式で変数選択候補１１３を出力可能である。変数選択候補出力装置１０６は、例えば、コンピュータモニタ上に、Fp(k)からの追加候補としてfj(w(k))の昇順に追加閾値以上の変数を表示してもよい。また、変数選択候補出力装置１０６は、例えば、コンピュータモニタ上に、F(k)からの削除候補としてf(w(k) - wi(k) ei)の昇順に削除閾値以上の変数を表示してもよい。なお、これらの方法は、出力の一例であり、他の方法で算出した情報および閾値を出力してもよい。
【００３６】
変数選択指示入力装置１０７は、Fp(k) から追加すべき変数や、F(k)から削除すべき変数を、変数選択指示１１４として入力する。指示される変数は１つでもよいし、複数であってもよい。なお、以下では、指示された変数が１つと仮定して説明をするが、複数であっても同様に処理可能である。
【００３７】
最適変数選択更新処理部１０８は、変数選択結果記憶部１０３に記憶されている現在の変数選択結果、及び、変数選択指示１１４に基づいて、変数選択結果を更新する。具体的には、最適変数選択更新処理部１０８は、変数の追加指示があった場合、指示された変数をFp(k) から削除し、F(k)に追加してk=k+1 とする。一方、変数の削除指示があった場合、最適変数選択更新処理部１０８は、指示された変数をF(k)から削除し、Fp(k) へ追加して、k=k-1 とする。
【００３８】
そして、最適変数選択更新処理部１０８は、更新後のF(k)に対してf(w)を最小化することによりw を最適化し、更新後のF(k)、Fp(k) およびw(k)を変数選択結果記憶部１０３へ記憶する。また、変数の追加指示の場合、最適変数選択更新処理部１０８は、新たに計算されたf(w(k)) を変数選択結果記憶部１０３へ併せて記憶する。一方、変数の削除指示の場合、最適変数選択更新処理部１０８は、変数選択結果記憶部１０３に記憶されているf(w(k+1)) を削除する。
【００３９】
変数選択結果出力装置１０９は、変数選択結果記憶部１０３に記憶されているF(k)、Fp(k) 、w(k)、f(w)などを、変数選択結果１１２として出力する。
【００４０】
追加変数候補算出処理部１０４（より具体的には、１変数最適化処理部１０４−１と、追加閾値算出処理部１０４−２）と、削除変数候補算出処理部１０５（より具体的には、目的関数値算出処理部１０５−１と、削除閾値算出処理部１０５−２）と、変数選択候補出力装置１０６と、最適変数選択更新処理部１０８とは、例えば、プログラム（対話的変数選択プログラム）に従って動作するコンピュータのＣＰＵによって実現される。
【００４１】
例えば、プログラムは、対話的変数選択装置１００の記憶部（図示せず）に記憶され、ＣＰＵは、そのプログラムを読み込み、プログラムに従って、追加変数候補算出処理部１０４、削除変数候補算出処理部１０５、変数選択候補出力装置１０６および最適変数選択更新処理部１０８として動作してもよい。また、上記プログラムは、コンピュータ読み取り可能な記憶媒体に記憶されていてもよい。
【００４２】
また、追加変数候補算出処理部１０４と、削除変数候補算出処理部１０５と、変数選択候補出力装置１０６と、最適変数選択更新処理部１０８とは、それぞれが専用のハードウェアで実現されていてもよい。
【００４３】
次に、本実施形態の対話的変数選択装置１００の動作を説明する。図４は、本実施形態の対話的変数選択装置１００の動作例を示すフローチャートである。
【００４４】
まず、データ入力装置１０１は、入力データ１１１を入力し（ステップＳ１００）、データ記憶部１０２に記憶する（ステップＳ１０１）。
【００４５】
次に、対話的変数選択装置１００は、変数選択結果を初期化し（ステップＳ１０２）、変数選択結果記憶部１０３へ記憶する（ステップＳ１０３）。
【００４６】
次に、ステップＳ１０４〜ステップＳ１０６の処理、および、ステップＳ１０７からステップＳ１０９の処理が実施される。なお、両者は独立した処理であり、同時に実行されてもよく、順番に実行されてもよい。
【００４７】
まず、ステップＳ１０４からステップＳ１０６の処理を説明する。
【００４８】
追加変数候補算出処理部１０４の１変数最適化処理部１０４−１は、Fp(k) に含まれる変数を１つ選択し、その変数に関してf(w)を最小化し、fj(w(k))を算出する（ステップＳ１０４）。
【００４９】
１変数最適化処理部１０４−１は、Fp(k) に含まれている全ての変数に対してステップＳ１０４に示す処理を実行したかを確認する（ステップＳ１０５）。ステップＳ１０４に示す処理が全ての変数に対して実行されていない場合（ステップＳ１０５におけるＮｏ）、１変数最適化処理部１０４−１は、全ての変数に対してステップＳ１０４に示す処理が実行されるまで繰り返す。一方、ステップＳ１０４に示す処理が全ての変数に対して実行された場合（ステップＳ１０５におけるＹｅｓ）、ステップＳ１０６へ処理が移る。
【００５０】
追加変数候補算出処理部１０４の追加閾値算出処理部１０４−２は、追加候補のfj(w(k))に対する閾値を算出する（ステップＳ１０６）。
【００５１】
次に、ステップＳ１０７からステップＳ１０９の処理を説明する。
【００５２】
削除変数候補算出処理部１０５の目的関数値算出処理部１０５−１は、F(k)に含まれる変数を１つ選択し、その変数についてf(w(k) - wi(k) ei)の値を算出する（ステップＳ１０７）。
【００５３】
目的関数値算出処理部１０５−１は、F(k)に含まれている全ての変数に対してステップＳ１０７の処理を実行したかを確認する（ステップＳ１０８）。ステップＳ１０７に示す処理が全ての変数に対して実行されていない場合（ステップＳ１０８におけるＮｏ）、目的関数値算出処理部１０５−１は、全ての変数に対してステップＳ１０７に示す処理が実行されるまで繰り返す。一方、ステップＳ１０７に示す処理が全ての変数に対して実行された場合（ステップＳ１０８におけるＹｅｓ）、ステップＳ１０９へ処理が移る。
【００５４】
削除変数候補算出処理部１０５の削除閾値算出処理部１０５−２は、削除候補のf(w(k) - wi(k) ei) - f(w(k))に対する閾値を算出する（ステップＳ１０９）。
【００５５】
次に、変数選択候補出力装置１０６は、変数選択候補１１３を出力する（ステップＳ１１０）。
【００５６】
一方、変数選択指示入力装置１０７が変数選択指示１１４を入力した場合には（ステップＳ１１１）、最適変数選択更新処理部１０８は、選択指示にしたがって変数選択結果を更新する（ステップＳ１１２）。更新された結果は、変数選択結果記憶部１０３に記憶され、ステップＳ１０３以降の処理が行われる。
【００５７】
また、変数選択結果出力装置１０９は、変数選択結果記憶部１０３に記憶された変数選択結果を任意のタイミングで変数選択結果１１２として出力する（ステップＳ１１３）。
【００５８】
以上のように、本実施形態によれば、追加変数候補算出処理部１０４が、Fp(k) の中からF(k)に追加すべき変数（追加変数）の候補を算出する。また、最適変数選択更新処理部１０８が、F(k)に含まれる変数に対してf(w)を最小化することによりw(k)を更新し、削除変数候補算出処理部１０５が、F(k)から削除すべき変数（削除変数）の候補を算出する。そして、変数選択候補出力装置１０６が、追加変数の候補と削除変数の候補の少なくとも一方を出力する。
【００５９】
具体的には、１変数最適化処理部１０４−１が、Fp(k) に含まれるj 番目の変数を追加変数の候補にした場合の目的変数値fj(w(k))を算出し、追加閾値算出処理部１０４−２が、fj(w(k))がどの程度小さい場合に、追加候補として有望であるかを表わす閾値（追加閾値）を、fj(w(k))に基づいて算出する。このとき、１変数最適化処理部１０４−１は、wjに対して目的関数を最小化する１変数の最適化問題を解いてもよい。
【００６０】
そして、削除変数候補算出処理部１０５が、変数wiを削除した場合の目的関数の増分f(w(k) - wi(k) ei) - f(w(k))を算出し、削除閾値算出処理部１０５−２が、変数wiを削除した場合の目的関数の増分がどの程度小さい場合に、その変数が削除候補として有望であるかを表わす閾値（削除閾値）を、その増分に基づいて算出する。
【００６１】
よって、複数の選択候補の中からより最適な変数をユーザに選択させることができる。
【００６２】
実施形態２．
図５は、本発明による対話的変数選択装置の第２の実施形態の構成例を示すブロック図である。本実施形態の対話的変数選択装置２００は、第１の実施形態の対話的変数選択装置１００と比較して、追加変数候補算出処理部１０４に代えて追加変数候補算出処理部２０１が接続されている点でのみ相違する。
【００６３】
図６は、本実施形態の追加変数候補算出処理部２０１の構成例を示すブロック図である。本実施形態の追加変数候補算出処理部２０１は、第１の実施形態の追加変数候補算出処理部１０４と比較して、１変数最適化処理部１０４−１に代えて勾配算出処理部２０１−１が接続され、追加閾値算出処理部１０４−２に代えて追加閾値算出処理部２０１−２が接続されている点でのみ相違する。
【００６４】
勾配算出処理部２０１−１は、Fp(k) に含まれる変数について、f(w)のw(k)における勾配を算出する。勾配は、目的関数値をどの程度下げることが可能かを示す目安になり、勾配の絶対値が大きな属性ほど、追加候補としては有望である。以下では、f(w)のw(k)における j 番目の属性に関する勾配を、∇fj(w(k))と表記する。
【００６５】
追加閾値算出処理部２０１−２は、|∇fj(w(k))|がどの程度大きい場合に、追加候補として有望であるかを表わす閾値を算出する。具体的には、追加閾値算出処理部２０１−２は、|∇fj(w(k))|を降順に並べたときの、上位K - kの平均値に、0 <= λ <=1 を満たすパラメータλを乗じたものを閾値とする。
【００６６】
なお、追加変数候補算出処理部２０１（より具体的には、勾配算出処理部２０１−１と、追加閾値算出処理部２０１−２）も、例えば、プログラム（対話的変数選択プログラム）に従って動作するコンピュータのＣＰＵによって実現される。
【００６７】
次に、本実施形態の対話的変数選択装置２００の動作を説明する。図７は、本実施形態の対話的変数選択装置２００の動作例を示すフローチャートである。
【００６８】
図７に示す対話的変数選択装置２００の動作は、図４に示す対話的変数選択装置１００の動作と比較して、ステップＳ１０４における処理（１変数を最適化する処理）が、勾配算出処理部２０１−１によって勾配が算出される処理（ステップＳ２０１）に変更されている点、および、ステップＳ１０６における処理（追加閾値を算出する処理）が、追加閾値算出処理部２０１−２によって勾配に基づく追加閾値が算出される処理（ステップＳ２０２）に変更されている点でのみ相違する。
【００６９】
以上のように、本実施形態によれば、勾配算出処理部２０１−１が、Fp(k) に含まれる変数について、f(w)のw(k)における勾配を算出し、追加閾値算出処理部２０１−２が、|∇fj(w(k))|がどの程度大きい場合に、追加候補として有望であるかを表わす閾値（追加閾値）を算出する。このとき、勾配算出処理部２０１−１は、wjを追加変数の候補にした場合における目的関数の勾配を算出してもよい。
【００７０】
このような構成によっても、複数の選択候補の中からより最適な変数をユーザに選択させることができる。
【００７１】
すなわち、第１の実施形態の対話的変数選択装置１００では、１変数最適化処理部１０４−１が、Fp(k) に含まれる変数の１変数最適化問題を解く必要があった。これは、最適化問題を高速に解くことが可能な場合には有効である。例えば、f(w)が二乗損失の場合、閉形式の解が存在するため、高速に計算することが可能である。一方、１変数最適化問題自体が難しい場合、第１の実施形態の対話的変数選択装置１００では、大きな計算コストが必要になる。
【００７２】
一方、本実施形態の対話的変数選択装置２００では、第１の実施形態の対応するステップにおいて、Fp(k) に含まれる変数に関する勾配のみが計算される。この方法の場合、１変数最適化問題を解く場合と比較して高速であるという利点がある。
【００７３】
なお、この方法では、追加候補を算出する際、目的関数を直接評価することはできない。しかし、算出される勾配は、目的関数値をどの程度下げることが可能かを表わす目安になるため、どの変数が追加候補として有望かを客観的に評価可能である。
【００７４】
実施形態３．
図８は、本発明による対話的変数選択装置の第３の実施形態の構成例を示すブロック図である。本実施形態の対話的変数選択装置３００は、第１の実施形態の対話的変数選択装置１００と比較して、交換変数候補算出処理部３０１と変数交換指示入出力装置３０２とが新たに接続され、変数交換候補要求３１１と変数交換指示３１３を入力し、変数交換候補３１２を出力する点で相違する。
【００７５】
変数交換候補要求３１１は、F(k)に含まれる変数のうち、Fp(k) に含まれる変数と交換したい変数を指定し、交換する候補の算出処理を要求するトリガである。
【００７６】
図９は、本実施形態の交換変数候補算出処理部３０１の構成例を示すブロック図である。本実施形態の交換変数候補算出処理部３０１は、最適変数一次更新処理部３０１−１と、１変数最適化処理部３０１−２と、交換閾値算出処理部３０１−３とを含む。
【００７７】
最適変数一次更新処理部３０１−１は、変数交換候補要求３１１で指定された変数をr とすると、F(k)から変数r を除いた変数のみについてf(w)を最適化する。なお、f(w)の最適化処理は、最適変数選択更新処理部１０８で実施することが可能である。以下では、F(k)から変数r を除いた集合をF*(k,-r)、Fp(k) に変数r を追加した集合をFp*(k,+r) 、F*(k,-r)に対して最適化されたw をw*(k,-r)と表記する。
【００７８】
１変数最適化処理部３０１−２は、第１の実施形態における１変数最適化処理部１０４−１と同様の処理を行う。なお、本実施形態の１変数最適化処理部３０１−２は、F(k)に代えてF*(k,-r)を利用し、Fp(k) に代えてFp*(k,+r) を利用し、w(k)に代えてw*(k,-r)を利用する点で１変数最適化処理部１０４−１と相違する。
【００７９】
交換閾値算出処理部３０１−３は、fj(w*(k,-r))を昇順に並べたときの、上位K-k-1 の平均値に、0 <= λ <=1 を満たすパラメータλを乗じた値と、fr(w*(k,-r))の小さい方を閾値として算出する。
【００８０】
変数交換指示入出力装置３０２は、変数交換候補要求３１１の入力、変数交換候補３１２の出力、および、変数交換指示３１３の入力を行う。
【００８１】
変数交換候補３１２は、Fp*(k,+r) 、fj(w*(k,-r))及び交換閾値算出処理部３０１−３で算出された閾値を含む。変数交換指示入出力装置３０２は、任意の形式で変数交換候補３１２を出力可能である。変数交換指示入出力装置３０２は、例えば、コンピュータモニタ上に、Fp*(k,+r)からの交換候補としてfj(w*(k,-r))の昇順に交換閾値以上の変数を表示してもよい。
【００８２】
変数交換指示３１３として交換すべき変数が入力された場合、変数交換指示入出力装置３０２は、変数交換候補要求３１１で指定された変数を削除すべき変数として、また、変数交換指示３１３で指定された変数を追加すべき候補として、最適変数選択更新処理部１０８へ入力する。
【００８３】
なお、交換変数候補算出処理部３０１（より具体的には、最適変数一次更新処理部３０１−１と、１変数最適化処理部３０１−２と、交換閾値算出処理部３０１−３）と、変数交換指示入出力装置３０２とは、例えば、プログラム（対話的変数選択プログラム）に従って動作するコンピュータのＣＰＵによって実現される。
【００８４】
次に、本実施形態の対話的変数選択装置３００の動作を説明する。図１０は、本実施形態の対話的変数選択装置３００の動作例を示すフローチャートである。図１０に示す対話的変数選択装置３００の動作は、図４に示す対話的変数選択装置１００の動作と比較して、ステップＳ３００〜ステップＳ３０７の処理が追加されている点において相違する。
【００８５】
まず、変数交換指示入出力装置３０２は、変数交換候補要求３１１を入力する（ステップＳ３００）。
【００８６】
次に、交換変数候補算出処理部３０１の最適変数一次更新処理部３０１−１は、ステップＳ１０３の処理で変数選択結果記憶部１０３に記憶された変数選択結果を読み込む。そして、最適変数一次更新処理部３０１−１は、変数交換候補要求３１１で指定された変数r を除いて、F*(k,-r)、Fp*(k,+r)、w*(k,-r)を算出する（ステップＳ３０１）。
【００８７】
次に、交換変数候補算出処理部３０１の１変数最適化処理部３０１−２は、Fp*(k,+r) に含まれる変数を１つ選択し、その変数に関してf(w)を最小化し、fj(w*(k,-r))を算出する（ステップＳ３０２）。
【００８８】
１変数最適化処理部３０１−２は、Fp*(k,+r) に含まれている全ての変数に対してステップＳ３０２に示す処理を実行したかを確認する（ステップＳ３０３）。ステップＳ３０２に示す処理が全ての変数に対して実行されていない場合（ステップＳ３０３におけるＮｏ）、１変数最適化処理部３０１−２は、全ての変数に対してステップＳ３０２に示す処理が実行されるまで繰り返す。一方、ステップＳ３０２に示す処理が全ての変数に対して実行された場合（ステップＳ３０３におけるＹｅｓ）、ステップＳ３０４へ処理が移る。
【００８９】
次に、交換変数候補算出処理部３０１の交換閾値算出処理部３０１−３は、交換候補のfj(w*(k,-r))に対する閾値を算出する（ステップＳ３０４）。
【００９０】
次に、変数交換指示入出力装置３０２は、変数交換候補３１２を出力する（ステップＳ３０５）。その後、変数交換指示入出力装置３０２は、変数交換候補３１２に対する変数交換指示３１３を入力する（ステップＳ３０６）。
【００９１】
変数交換指示入出力装置３０２は、変数交換候補要求３１１で指定された変数を削除すべき変数として、また、変数交換指示３１３で指定された変数を追加すべき候補として、選択指示に変換する（ステップＳ３０７）。その後、ステップＳ１１２へ処理が移る。
【００９２】
以上のように、本実施形態によれば、最適変数一次更新処理部３０１−１が、F*(k,-r)を用いて目的関数を最適化し、１変数最適化処理部３０１−２が、Fp*(k,+r)に含まれる変数wjを追加変数の候補にした場合のfj(w*(k,-r))を算出する。
【００９３】
すなわち、第１の実施形態の対話的変数選択装置１００では、変数の追加および削除を行うための２つの機能が提供される。変数の交換は、その組み合わせによって実現可能である。しかし、単純な交換には、以下のような問題が存在する。
【００９４】
例として、変数i がF(k)に含まれ、変数j がFp(k) に含まれ、変数i と変数j が高い相関を持つ状況を考える。すなわち、どちらの変数もf(w)の値を下げるという意味で、同程度の有用性をもつものとする。
【００９５】
ユーザが、変数i と変数j を交換したい場合、対話的変数選択装置１００の構成では、変数i は削除候補として提示される可能性がある。その一方で、変数j は、変数i と相関が高く、追加候補としては有用ではないと判断されるため、ユーザの意図する交換が難しくなる可能性がある。これは、変数i がすでに選択されているため、同じ情報量をもつ変数j は追加候補とはならないからである。
【００９６】
一方、本実施形態の対話的変数選択装置３００は、変数の交換機能を提供している。すなわち、変数交換候補要求で変数i が指定された場合、本実施形態の対話的変数選択装置３００は、変数i を除いたうえで、変数i と同程度に有用な変数を交換候補として出力する。そのため、変数i と変数j の交換が可能になるという利点がある。
【００９７】
言い換えると、本実施形態で交換とは、指定された変数r をF(k)から除いて、追加変数候補i を算出することであるということができる。
【００９８】
実施形態４．
図１１は、本発明による対話的変数選択装置の第４の実施形態の構成例を示すブロック図である。本実施形態の対話的変数選択装置４００は、第２の実施形態の対話的変数選択装置２００と比較して、交換変数候補算出処理部４０１と変数交換指示入出力装置３０２とが新たに接続され、変数交換候補要求３１１と変数交換指示３１３を入力し、変数交換候補３１２を出力する点で相違する。
【００９９】
なお、変数交換指示入出力装置３０２の内容は、第３の実施形態と同様である。また、変数交換候補要求３１１、変数交換指示３１３および変数交換候補３１２の内容も、第３の実施形態と同様である。また、交換変数候補算出処理部４０１の内容は、第３の実施形態の交換変数候補算出処理部３０１の内容に対応する。
【０１００】
すなわち、第３の実施形態の対話的変数選択装置３００は、第１の実施形態の対話的変数選択装置１００に変数交換機能が追加されたものであり、本実施形態の対話的変数選択装置４００は、第２の実施形態の対話的変数選択装置２００に同様の変数交換機能が追加されたものである。
【０１０１】
図１２は、本実施形態の交換変数候補算出処理部４０１の構成例を示すブロック図である。本実施形態の交換変数候補算出処理部４０１は、最適変数一次更新処理部４０１−１と、勾配算出処理部４０１−２と、交換閾値算出処理部４０１−３とを含む。
【０１０２】
最適変数一次更新処理部４０１−１および交換閾値算出処理部４０１−３の内容は、第３の実施形態の最適変数一次更新処理部３０１−１および交換閾値算出処理部３０１−３の内容と同様である。また、勾配算出処理部４０１−２の内容は、第２の実施形態の勾配算出処理部２０１−１の内容と同様である。
【実施例】
【０１０３】
以下、具体的な実施例により本発明を説明するが、本発明の範囲は以下に説明する内容に限定されない。本実施例では、本発明による対話的変数選択装置を応用して、健康診断ログから健康リスク分析を行う場合を例に説明する。なお、ここでは、第１の実施形態の対話的変数選択装置１００を医療分野に応用した例を説明する。
【０１０４】
生活習慣や健康診断検査値と、健康や疾病リスクの関係性をモデル化し、リスクを予測することは、疾病予防やリスク分析、生活習慣指導などに応用可能である。
【０１０５】
また、リスクの予測関数が複雑すぎると人間に理解不可能になる。そのため、入力される変数（生活習慣や健康診断検査値の各種項目）のうち、少数の変数でリスク予測関数を構成することが重要である。なお、少数の変数で予測するということは、変数の多くが０で疎であると言える。
【０１０６】
ロジスティック回帰モデルによるリスクスコア関数の学習を、上記応用の一例として説明する。ロジスティック回帰モデルは、あるリスク指標（例えば、血圧が閾値より高いかどうか）を、リスクが発現する確率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 の要素の多くが0 で、リスクに関係する少数の要素のみが非ゼロであるモデルを、一般的に知られた技術を用いることによって、データから自動的に学習することは可能である。しかし、例えば、高血圧に対するリスクとして肥満と喫煙が同程度のリスク要因であった場合、どちらを選択するかをコントロールすることは難しかった。
【０１１０】
しかし、本発明を利用することによって、例えば、高血圧のリスク予測関数を最適化した場合には、肥満の度合いや、運動習慣の有無など、高血圧リスクに直結する少数の変数のみを利用したモデルを、人間による制御のもとで算出することが可能になる。
【０１１１】
次に、本発明の概要を説明する。図１３は、本発明による対話的変数選択装置の概要を示すブロック図である。本発明による対話的変数選択装置は、ユーザと対話的に変数を選択する対話的変数選択装置（例えば、対話的変数選択装置１００）であって、変数集合（例えば、Fp(k) ）の中から非ゼロ変数集合（例えば、F(k)）に追加すべき変数である追加変数の候補を算出する追加変数候補算出部７０（例えば、追加変数候補算出処理部１０４）と、非ゼロ変数集合に含まれる変数に対して、最適化された変数において最小値をとる目的関数（例えば、f(w)）を最小化することにより、最適化対象とする変数（例えば、w 、w(k)）を更新する最適変数選択更新部９０（例えば、最適変数選択更新処理部１０８）と、非ゼロ変数集合から削除すべき変数である削除変数の候補を算出する削除変数候補算出部８０（例えば、削除変数候補算出処理部１０５）と、追加変数の候補と削除変数の候補の少なくとも一方を出力する変数選択結果出力部６０（例えば、変数選択結果出力装置１０９）とを備えている。
【０１１２】
追加変数候補算出部７０は、変数集合に含まれる第一の変数（例えば、wj）を追加変数の候補にした場合の最適度（例えば、fj(w(k))、|∇fj(w(k))|）を、目的関数を用いて算出する算出する最適度算出手段７１（例えば、１変数最適化処理部１０４−１、勾配算出処理部２０１−１）と、第一の変数を追加変数の候補とすべきか否かを判断するための基準を表わす最適度の閾値である追加閾値を、算出された最適度に基づいて算出する追加閾値算出部７２（追加閾値算出処理部１０４−２）とを含む。
【０１１３】
削除変数候補算出部８０は、最適化対象とする変数を用いて算出される目的関数の値（例えば、f(w(k)) ）と、その最適化対象とする変数から非ゼロ変数集合に含まれる第二の変数（例えば、wi(k) ）を除いて算出される目的関数の値（例えば、f(w(k) - wi(k) ei)）との差分である目的関数値（例えば、f(w(k) - wi(k) ei) - f(w(k))）を算出する目的関数値算出部８１（例えば、目的関数値算出処理部１０５−１）と、第二の変数を非ゼロ変数集合から削除すべきか否かを判断するための基準を表わす目的関数値の閾値である削除閾値を、算出された目的関数に基づいて算出する削除閾値算出部８２（例えば、削除閾値算出処理部１０５−２）とを含む。
【０１１４】
そのような構成により、複数の選択候補の中からより最適な変数をユーザに選択させることができる。
【０１１５】
具体的には、最適度算出手段７１（例えば、１変数最適化処理部１０４−１）が、第一の変数に対して目的関数を最小化する１変数の最適化問題を解くことにより、その目的関数の値を最適度として算出してもよい。このような構成によれば、最適化問題を高速に解くことが可能な場合、特に有効である。例えば、目的関数が二乗損失を表わす場合、閉形式の解が存在するため、高速に計算することが可能である。
【０１１６】
または、最適度算出手段７１（例えば、勾配算出処理部２０１−１）が、第一の変数について、最適化対象とする変数における目的関数の勾配を最適度として算出してもよい。このような構成によれば、Fp(k) に含まれる変数に関する勾配のみが計算されるため、１変数最適化問題自体が難しい場合には、より高速に計算可能である。
【０１１７】
また、対話的変数選択装置は、非ゼロ変数集合の中から、変数集合に含まれる変数と交換する対象として指定された変数（例えば、r ）を入力し、指定された変数と交換すべき変数の候補を変数集合の中から算出する交換変数候補算出部（例えば、交換変数候補算出処理部３０１，交換変数候補算出処理部４０１）を備えていてもよい。
【０１１８】
具体的には、交換変数候補算出部は、指定された変数を追加変数の候補から除いた変数の集合（例えば、F*(k,-r)）を用いて目的関数を最適化する最適変数一次更新部（例えば、最適変数一次更新処理部３０１−１、最適変数一次更新処理部４０１−１）と、変数集合に含まれる変数と指定された変数とを交換すべきか否かを判断するための基準を表わす閾値である交換閾値を、算出された最適度に基づいて算出する交換閾値算出部（例えば、交換閾値算出処理部３０１−３，交換閾値算出処理部４０１−３）とを含んでいてもよい。そして、最適度算出手段７１（例えば、１変数最適化処理部３０１−２）は、指定された変数を含む変数集合（例えば、Fp*(k,+r)）に含まれる第一の変数を追加変数の候補にした場合の最適度（fj(w*(k,-r)）を、目的関数を用いて算出してもよい。
【０１１９】
そのような構成によれば、２つの変数が高い相関をもつ状況であっても、両変数の候補を交換する（すなわち、一方の変数を追加変数の候補とし、他方の変数を削除変数の候補とする）ことが可能になる。
【０１２０】
また、変数選択結果出力部６０は、追加閾値に基づいて追加変数の候補とすべきと判断される変数、または、削除閾値に基づいて追加変数の候補から削除すべきと判断される変数を出力してもよい。そのような構成により、ユーザが追加候補とする変数を客観的に決め易くできる。
【０１２１】
また、追加閾値算出部７２は、最適化される変数に残ると想定される非ゼロ要素数（例えば、K ）から、非ゼロ変数集合に追加された変数の数（例えば、k ）を減じた数（例えば、K-k ）の最適度を、その最適度の高い順（例えば、fj(w(k))ならば昇順、|∇fj(w(k))|ならば降順）に特定し、特定した最適度の平均値に０以上１以下のパラメータ（例えば、0 <=λ<=1 を満たすλ）を乗じた値を追加閾値として算出してもよい。このような追加閾値を用いることで、生成された候補がどの程度有望かより適切に判断できる。
【０１２２】
上記の実施形態の一部又は全部は、以下の付記のようにも記載されうるが、以下には限られない。
【０１２３】
（付記１）ユーザと対話的に変数を選択する対話的変数選択装置であって、変数集合の中から非ゼロ変数集合に追加すべき変数である追加変数の候補を算出する追加変数候補算出部と、前記非ゼロ変数集合に含まれる変数に対して、最適化された変数において最小値をとる目的関数を最小化することにより、最適化対象とする変数を更新する最適変数選択更新部と、前記非ゼロ変数集合から削除すべき変数である削除変数の候補を算出する削除変数候補算出部と、前記追加変数の候補と前記削除変数の候補の少なくとも一方を出力する変数選択結果出力部とを備え、前記追加変数候補算出部は、前記変数集合に含まれる第一の変数を前記追加変数の候補にした場合の最適度を、前記目的関数を用いて算出する最適度算出手段と、前記第一の変数を前記追加変数の候補とすべきか否かを判断するための基準を表わす前記最適度の閾値である追加閾値を、算出された最適度に基づいて算出する追加閾値算出部とを含み、前記削除変数候補算出部は、前記最適化対象とする変数を用いて算出される前記目的関数の値と、当該最適化対象とする変数から前記非ゼロ変数集合に含まれる第二の変数を除いて算出される前記目的関数の値との差分である目的関数値を算出する目的関数値算出部と、前記第二の変数を前記非ゼロ変数集合から削除すべきか否かを判断するための基準を表わす前記目的関数値の閾値である削除閾値を、算出された目的関数値に基づいて算出する削除閾値算出部とを含むことを特徴とする対話的変数選択装置。
【０１２４】
（付記２）最適度算出手段は、第一の変数に対して目的関数を最小化する１変数の最適化問題を解くことにより、その目的関数の値を最適度として算出する付記１記載の対話的変数選択装置。
【０１２５】
（付記３）最適度算出手段は、第一の変数について、最適化対象とする変数における目的関数の勾配を最適度として算出する付記１記載の対話的変数選択装置。
【０１２６】
（付記４）非ゼロ変数集合の中から、変数集合に含まれる変数と交換する対象として指定された変数を入力し、前記指定された変数と交換すべき変数の候補を変数集合の中から算出する交換変数候補算出部を備えた付記１から付記３のうちのいずれか１つに記載の対話的変数選択装置。
【０１２７】
（付記５）交換変数候補算出部は、指定された変数を追加変数の候補から除いた変数の集合を用いて目的関数を最適化する最適変数一次更新部と、変数集合に含まれる変数と指定された変数とを交換すべきか否かを判断するための基準を表わす閾値である交換閾値を、算出された最適度に基づいて算出する交換閾値算出部とを含み、最適度算出手段は、指定された変数を含む変数集合に含まれる第一の変数を追加変数の候補にした場合の最適度を、目的関数を用いて算出する付記４記載の対話的変数選択装置。
【０１２８】
（付記６）変数選択結果出力部は、追加閾値に基づいて追加変数の候補とすべきと判断される変数、または、削除閾値に基づいて追加変数の候補から削除すべきと判断される変数を出力する付記１から付記５のうちのいずれか１つに記載の対話的変数選択装置。
【０１２９】
（付記７）追加閾値算出部は、最適化される変数に残ると想定される非ゼロ要素数から、非ゼロ変数集合に追加された変数の数を減じた数の最適度を、当該最適度の高い順に特定し、特定した最適度の平均値に０以上１以下のパラメータを乗じた値を追加閾値として算出する付記１から付記６のうちのいずれか１つに記載の対話的変数選択装置。
【０１３０】
この出願は、２０１３年２月２０日に出願された米国仮出願第６１／７６７，０１９号を基礎とする優先権を主張し、その開示の全てをここに取り込む。
【符号の説明】
【０１３１】
１００，２００，３００，４００  対話的変数選択装置
１０１  データ入力装置
１０２  データ記憶部
１０３  変数選択結果記憶部
１０４  追加変数候補算出処理部
１０５  削除変数候補算出処理部
１０６  変数選択候補出力装置
１０７  変数選択指示入力装置
１０８  最適変数選択更新処理部
１０９  変数選択結果出力装置
１０４−１，３０１−２  １変数最適化処理部
１０４−２  追加閾値算出処理部
１０５−１  目的関数値算出処理部
１０５−２  削除閾値算出処理部
２０１  追加変数候補算出処理部
２０１−１，４０１−２  勾配算出処理部
２０１−２  追加閾値算出処理部
３０１，４０１  交換変数候補算出処理部
３０２  変数交換指示入出力装置
３０１−１，４０１−１  最適変数一次更新処理部
３０１−３，４０１−３  交換閾値算出処理部
【図１】
2014160457.tif 000003
【図２】
2014160457.tif 000004
【図３】
2014160457.tif 000005
【図４】
2014160457.tif 000006
【図５】
2014160457.tif 000007
【図６】
2014160457.tif 000008
【図７】
2014160457.tif 000009
【図８】
2014160457.tif 000010
【図９】
2014160457.tif 000011
【図１０】
2014160457.tif 000012
【図１１】
2014160457.tif 000013
【図１２】
2014160457.tif 000014
【図１３】
2014160457.tif 000015