(57)【要約】【課題】線形変換されたスパース制約下での最適化問題の解を高い精度で得る。【解決手段】線形変換されたスパース制約下での最適化問題の解を算出する解算出装置は、関数と、線形変換と、スパース性を制限する定数と、初期解ベクトルとを入力する入力手段と、前記初期解ベクトルを移動させた移動後ベクトルであって、前記初期解ベクトルよりも前記関数の値を減少させる移動後ベクトルを算出する解ベクトル移動手段と、前記解ベクトル移動手段が算出した移動後ベクトルと、前記線形変換と、前記定数とに基づいて、有効なスパース制約を満たし、かつ、前記関数の値が最小となる解ベクトルを算出する厳密最小化計算手段と、を有し、前記解ベクトル移動手段は、前記厳密最小化計算手段が算出した解ベクトルを移動させた移動後ベクトルであって、前記解ベクトルよりも前記関数の値を減少させる移動後ベクトルを算出する、ことを特徴とする。【選択図】図３
2018195232.tif 000002
【特許請求の範囲】
【請求項１】
線形変換されたスパース制約下での最適化問題の解を算出する解算出装置であって、
関数と、線形変換と、スパース性を制限する定数と、初期解ベクトルとを入力する入力手段と、
前記初期解ベクトルを移動させた移動後ベクトルであって、前記初期解ベクトルよりも前記関数の値を減少させる移動後ベクトルを算出する解ベクトル移動手段と、
前記解ベクトル移動手段が算出した移動後ベクトルと、前記線形変換と、前記定数とに基づいて、有効なスパース制約を満たし、かつ、前記関数の値が最小となる解ベクトルを算出する厳密最小化計算手段と、
を有し、
前記解ベクトル移動手段は、
前記厳密最小化計算手段が算出した解ベクトルを移動させた移動後ベクトルであって、前記解ベクトルよりも前記関数の値を減少させる移動後ベクトルを算出する、ことを特徴とする解算出装置。
【請求項２】
前記厳密最小化計算手段は、
前記解ベクトル移動手段が算出した移動後ベクトルを前記線形変換により変換して、該変換後の移動後ベクトルの各成分のうち、前記定数が示す個数の成分を昇順に選択することで、有効でないスパース制約を選択する制約選択手段と、
前記制約選択手段により選択されなかったスパース制約を満たし、かつ、前記関数の値が最小となる解ベクトルを算出する制約付き最小化計算手段と、
を有する、ことを特徴とする請求項１に記載の解算出装置。
【請求項３】
前記制約付き最小化計算手段は、
射影勾配法により前記解ベクトルを算出する、ことを特徴とする請求項２に記載の解算出装置。
【請求項４】
前記解ベクトル移動手段による移動後ベクトルの算出と、前記厳密最小化計算手段による解ベクトルの算出とが所定の回数行われた場合、前記厳密最小化計算手段により算出された解ベクトルを出力する出力手段を有する、ことを特徴とする請求項１乃至３の何れか一項に記載の解算出装置。
【請求項５】
線形変換されたスパース制約下での最適化問題の解を算出するコンピュータが、
関数と、線形変換と、スパース性を制限する定数と、初期解ベクトルとを入力する入力手順と、
前記初期解ベクトルを移動させた移動後ベクトルであって、前記初期解ベクトルよりも前記関数の値を減少させる移動後ベクトルを算出する解ベクトル移動手順と、
前記解ベクトル移動手順が算出した移動後ベクトルと、前記線形変換と、前記定数とに基づいて、有効なスパース制約を満たし、かつ、前記関数の値が最小となる解ベクトルを算出する厳密最小化計算手順と、
を実行し、
前記解ベクトル移動手順は、
前記厳密最小化計算手順が算出した解ベクトルを移動させた移動後ベクトルであって、前記解ベクトルよりも前記関数の値を減少させる移動後ベクトルを算出する、ことを特徴とする解算出方法。
【請求項６】
前記厳密最小化計算手順は、
前記解ベクトル移動手順が算出した移動後ベクトルを前記線形変換により変換して、該変換後の移動後ベクトルの各成分のうち、前記定数が示す個数の成分を昇順に選択することで、有効でないスパース制約を選択する制約選択手順と、
前記制約選択手順により選択されなかったスパース制約を満たし、かつ、前記関数の値が最小となる解ベクトルを算出する制約付き最小化計算手順と、
が含まれる、ことを特徴とする請求項５に記載の解算出方法。
【請求項７】
コンピュータを、請求項１乃至４の何れか一項に記載の解算出装置における各手段として機能させるための解算出プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、解算出装置、解算出方法及び解算出プログラムに関する。
【背景技術】
【０００２】
機械学習の問題は、一般に、関数の最小化問題として定式化されることが知られている。例えば、回帰問題は、二乗損失関数等の最小化問題として定式化される。同様に、例えば、分類問題は、ロジスティック損失関数等の最小化問題として定式化される。
【０００３】
一方で、機械学習の汎化性能や結果の解釈性を向上させるため、線形変換されたスパース制約が用いられる。スパース制約を用いることで、例えば、グラフのノード上のパラメータで、その値がグラフ上で区分線型的に変化するものを求めることができる。
【０００４】
これらを組み合わせて、線形変換されたスパース制約下での最小化問題とすることで、様々な機会学習問題を定式化できる。一般に、この問題を解くことは困難であるため、近似を用いる手法が知られている（非特許文献１及び非特許文献２）。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】R. Giryesa, S. Namb, M. Elada, R.Gribonvalb and M. E. Daviesc, Greedy-like algorithms for the cosparse analysis model, Linear Algebra and its Applications, 441:22-60,2014.
【非特許文献２】A. Beck and M. Teboulle, A fast iterative shrinkage-thresholding algo-rithm for linear inverse problems, SIAM Journal on Imaging Sciences 2(1):183-202, 2009.
【発明の概要】
【発明が解決しようとする課題】
【０００６】
しかしながら、上記の近似を用いる手法では、得られる解の精度が低下するという問題がある。
【０００７】
本発明は、上記の問題点に鑑みてなされたものであり、線形変換されたスパース制約下での最適化問題の解を高い精度で得ることを目的とする。
【課題を解決するための手段】
【０００８】
上記課題を解決するため、線形変換されたスパース制約下での最適化問題の解を算出する解算出装置は、関数と、線形変換と、スパース性を制限する定数と、初期解ベクトルとを入力する入力手段と、前記初期解ベクトルを移動させた移動後ベクトルであって、前記初期解ベクトルよりも前記関数の値を減少させる移動後ベクトルを算出する解ベクトル移動手段と、前記解ベクトル移動手段が算出した移動後ベクトルと、前記線形変換と、前記定数とに基づいて、有効なスパース制約を満たし、かつ、前記関数の値が最小となる解ベクトルを算出する厳密最小化計算手段と、を有し、前記解ベクトル移動手段は、前記厳密最小化計算手段が算出した解ベクトルを移動させた移動後ベクトルであって、前記解ベクトルよりも前記関数の値を減少させる移動後ベクトルを算出する、ことを特徴とする。
【発明の効果】
【０００９】
線形変換されたスパース制約下での最適化問題の解を高い精度で得ることができる。
【図面の簡単な説明】
【００１０】
【図１】本発明の実施の形態における解算出装置の構成の一例を示す図である。
【図２】本発明の実施の形態における解算出装置のハードウェア構成の一例を示す図である。
【図３】本発明の実施の形態における解算出装置の機能構成の一例を示す図である。
【図４】本発明の実施の形態における解算出装置が実行する全体処理の一例を示すフローチャートである。
【図５】移動後ベクトルから次の解ベクトルを算出する処理の一例を示すフローチャートである。
【図６】本発明と従来技術との比較例を示す図である。
【発明を実施するための形態】
【００１１】
以下、本発明の実施の形態について、図面を参照しながら説明する。
【００１２】
＜解算出装置１０の構成＞
まず、本発明の実施の形態における解算出装置１０の構成について、図１を参照しながら説明する。図１は、本発明の実施の形態における解算出装置１０の構成の一例を示す図である。
【００１３】
図１に示す解算出装置１０は、線形変換されたスパース制約下での最適化問題の解を算出するコンピュータである。図１に示す解算出装置１０には、解算出プログラム１００がインストールされている。なお、解算出プログラム１００は、複数のモジュールで構成されるプログラム群であっても良い。
【００１４】
本発明の実施の形態における解算出装置１０は、解算出プログラム１００により、関数ｆ：Ｒｄ→Ｒと、線形変換Ａと、解のスパース性を制限する定数ｓと、初期解ｘ０とを入力して、最適化問題の解ベクトルｘ＊を出力する。このとき、出力される解ベクトルｘ＊は、ベクトルＡｘ＊の非零成分がｓ個以下で、かつ、関数値ｆ（ｘ＊）が最小となるものである。なお、Ｒ及びＲｄは、それぞれ１次元実数空間及びｄ次元実数空間である。また、ｘ０及びｘ＊は、ｄ次元の実ベクトルである。
【００１５】
より具体的には、本発明の実施の形態における解算出装置１０は、例えばｔ＝０，１，・・・，Ｔとした場合に、各ｔに対して、以下の（１）及び（２）を繰り返し実行することで、最適化問題の解ベクトルｘ＊＝ｘＴを算出及び出力する。Ｔは、繰り返しの終了条件であり、例えばユーザ等により予め設定された繰り返し回数である。
【００１６】
（１）まず、解ベクトルｘｔを微小に移動させ、関数値が小さくなるベクトル（移動後ベクトル）を算出する。
【００１７】
（２）次に、移動後ベクトルに基づいて、制約を満たし、かつ、関数値が最小となる解ベクトルｘｔ＋１を算出する。
【００１８】
なお、図１に示す解算出装置１０の構成は一例であって、他の構成であっても良い。例えば、図１に示す解算出装置１０は、複数台のコンピュータで構成されていても良い。
【００１９】
＜解算出装置１０のハードウェア構成＞
次に、本発明の実施の形態における解算出装置１０のハードウェア構成について、図２を参照しながら説明する。図２は、本発明の実施の形態における解算出装置１０のハードウェア構成の一例を示す図である。
【００２０】
図２に示す解算出装置１０は、入力装置１１と、表示装置１２と、外部Ｉ／Ｆ１３と、ＲＡＭ（Random Access Memory）１４と、ＲＯＭ（Read Only Memory）１５と、ＣＰＵ（Central Processing Unit）１６と、通信Ｉ／Ｆ１７と、補助記憶装置１８とを有する。これら各ハードウェアは、それぞれがバスＢを介して通信可能に接続されている。
【００２１】
入力装置１１は、例えばキーボードやマウス、タッチパネル等であり、ユーザが各種操作を入力するのに用いられる。表示装置１２は、例えばディスプレイ等であり、解算出装置１０の処理結果を表示する。
【００２２】
外部Ｉ／Ｆ１３は、外部装置とのインタフェースである。外部装置には、記録媒体１３ａ等がある。解算出装置１０は、外部Ｉ／Ｆ１３を介して、記録媒体１３ａ等の読み取りや書き込みを行うことができる。記録媒体１３ａには、解算出プログラム１００等が記録されていても良い。
【００２３】
記録媒体１３ａには、例えば、フレキシブルディスク、ＣＤ（Compact Disc）、ＤＶＤ（Digital Versatile Disk）、ＳＤメモリカード（Secure Digital memory card）、ＵＳＢ（Universal Serial Bus）メモリカード等がある。
【００２４】
ＲＡＭ１４は、プログラムやデータを一時保持する揮発性の半導体メモリである。ＲＯＭ１５は、電源を切ってもプログラムやデータを保持することができる不揮発性の半導体メモリである。ＲＯＭ１５には、例えば、ＯＳ（Operating System）設定やネットワーク設定等が格納されている。
【００２５】
ＣＰＵ１６は、ＲＯＭ１５や補助記憶装置１８等からプログラムやデータをＲＡＭ１４上に読み出して処理を実行する演算装置である。
【００２６】
通信Ｉ／Ｆ１７は、解算出装置１０をネットワークに接続するためのインタフェースである。解算出プログラム１００は、通信Ｉ／Ｆ１７を介して、所定のサーバ等から取得（ダウンロード）されても良い。
【００２７】
補助記憶装置１８は、例えばＨＤＤ（Hard Disk Drive）やＳＳＤ（Solid State Drive）等であり、プログラムやデータを格納している不揮発性の記憶装置である。補助記憶装置１８に格納されているプログラムやデータには、例えば、ＯＳ、当該ＯＳ上において各種機能を実現するアプリケーションプログラム、解算出プログラム１００等がある。
【００２８】
本発明の実施の形態における解算出装置１０は、図２に示すハードウェア構成を有することにより、後述する各種処理を実現することができる。
【００２９】
＜解算出装置１０の機能構成＞
次に、本発明の実施の形態における解算出装置１０の機能構成について、図３を参照しながら説明する。図３は、本発明の実施の形態における解算出装置１０の機能構成の一例を示す図である。
【００３０】
図３に示す解算出装置１０は、入力部１０１と、解ベクトル算出部１０２と、出力部１０３とを有する。これら各部は、解算出プログラム１００がＣＰＵ１６に実行させる処理により実現される。
【００３１】
入力部１０１は、関数ｆと、線形変換Ａと、解のスパース性を制限する定数ｓと、初期解ｘ０とを入力する。これらの情報は、例えば、ユーザが入力しても良いし、他のプログラム等から入力されても良い。又は、補助記憶装置１８等に記憶されている電子ファイルを読み込むことで、入力されても良い。
【００３２】
解ベクトル算出部１０２は、最適化問題の解ベクトルｘ＊を算出する処理を行う。ここで、解ベクトル算出部１０２は、解ベクトル移動部１１１と、厳密最小化計算部１１２と、終了条件判定部１１３とを有する。
【００３３】
解ベクトル移動部１１１は、各ｔに対して、現在の解ベクトルｘｔを微小に移動させ、関数ｆの値が小さくなるベクトル（移動後ベクトル）を算出する。以降では、解ベクトルｘｔの移動後ベクトルを「ｘｔ＋１／２」と表す。
【００３４】
厳密最小化計算部１１２は、解ベクトル移動部１１１が算出した移動後ベクトルｘｔ＋１／２に基づいて、次の解ベクトルｘｔ＋１を算出する処理を行う。ここで、厳密最小化計算部１１１２は、制約選択部１２１と、制約付き最小化計算部１２２とを有する。
【００３５】
制約選択部１２１は、解ベクトル移動部１１１が算出した移動後ベクトルｘｔ＋１／２に基づいて、有効でない制約を選択する。
【００３６】
制約付き最小化計算部１２２は、制約選択部１２１により選択されなかった制約（すなわち、有効な制約）を満たすように、関数値ｆ（ｘ）が最小となる解ベクトルｘｔ＋１を算出する。
【００３７】
終了条件判定部１１３は、解ベクトル移動部１１１による移動後ベクトルｘｔ＋１／２の算出と、厳密最小化計算部１１２による解ベクトルｘｔ＋１の算出との繰り返しを終了させるか否かを判定する。すなわち、終了条件判定部１１３は、繰り返しの終了条件ｔ＝Ｔを満たすか否かを判定する。
【００３８】
出力部１０３は、終了条件判定部１１３により終了条件ｔ＝Ｔを満たすと判定された場合、解ベクトル算出部１０２により最終的に得られた解ベクトルｘ＊＝ｘＴを出力する。解ベクトルｘ＊の出力先としては、例えば、表示装置１２でも良いし、他のプログラムでも良い。又は、解算出装置１０とネットワーク等を介して接続される他の装置等であっても良い。
【００３９】
＜処理の詳細＞
次に、本発明の実施の形態における解算出装置１０の処理の詳細について説明する。以降では、本発明の実施の形態における解算出装置１０が実行する全体処理について、図４を参照しながら説明する。図４は、本発明の実施の形態における解算出装置１０が実行する全体処理の一例を示すフローチャートである。
【００４０】
まず、入力部１０１は、関数ｆと、線形変換Ａと、解のスパース性を制限する定数ｓと、初期解ｘ０とを入力する（ステップＳ１０１）。
【００４１】
次に、解ベクトル算出部１０２は、ｔを０に初期化する（ステップＳ１０２）。すなわち、解ベクトル算出部１０２は、ｔ＝０とする。
【００４２】
次に、解ベクトル算出部１０２の解ベクトル移動部１１１は、現在の解ベクトルｘｔを微小に移動させ、関数ｆの値が小さくなる移動後ベクトルｘｔ＋１／２を算出する（ステップＳ１０３）。
【００４３】
ここで、２つのベクトルｘ１、ｘ２の距離を測るためには、例えば、以下の式１を用いる。
【００４４】
【数１】
2018195232.tif 000003
上記の式１に基づくと、現在の解ベクトルｘｔに近いベクトルで、かつ、関数ｆの値を小さくするベクトル（すなわち、移動後ベクトルｘｔ＋１／２）は、以下の式２で計算することができる。
【００４５】
【数２】
2018195232.tif 000004
なお、関数ｆが良条件である場合（すなわち、ｘが微小に変化したとき、関数値ｆ（ｘ）の変化量が、ｘの変化方向に大きく依存しない場合）には、上記の式２の代わりに、以下の式３で計算することもできる。
【００４６】
【数３】
2018195232.tif 000005
上記の式２及び式３は、例えば、コレスキー分解に基づく直接法や、共役勾配法等の反復法を用いて計算することができる。
【００４７】
次に、解ベクトル算出部１０２の厳密最小化計算部１１２は、解ベクトル移動部１１１が算出した移動後ベクトルをｘｔ＋１／２に基づいて、次の解ベクトルｘｔ＋１を算出する（ステップＳ１０４）。なお、本ステップの処理は、後述する。
【００４８】
次に、解ベクトル算出部１０２の終了条件判定部１１３は、終了条件を満たすか否かを判定する（ステップＳ１０５）。すなわち、終了条件判定部１１３は、ｔ＝Ｔを満たすか否かを判定する。
【００４９】
なお、終了条件はｔ＝Ｔに限られない。終了条件としては、例えば、関数ｆの値の変化量等を用いても良い。関数ｆの値の変化量を用いる場合、終了条件判定部１１３は、例えば、当該変化量が所定の値以下となった場合に、終了条件を満たすと判定すれば良い。
【００５０】
ステップＳ１０５において、終了条件を満たさないと判定された場合、解ベクトル算出部１０２は、ｔに１を加算する（ステップＳ１０６）。そして、解ベクトル算出部１０２は、ステップＳ１０３に戻る。すなわち、解ベクトル算出部１０２は、終了条件を満たすまでステップＳ１０３〜ステップＳ１０４を繰り返し実行する。
【００５１】
一方、ステップＳ１０５において、終了条件を満たすと判定された場合、出力部１０３は、解ベクトル算出部１０２により最終的に得られた解ベクトルｘ＊＝ｘＴを出力する（ステップＳ１０７）。これにより、線形変換されたスパース制約下での最適化問題の解ベクトルｘ＊が出力される。
【００５２】
ここで、上記のステップＳ１０４の処理の詳細について、図５を参照しながら説明する。図５は、移動後ベクトルｘｔ＋１／２から次の解ベクトルｘｔ＋１を算出する処理の一例を示すフローチャートである。
【００５３】
まず、厳密最小化計算部１１２の制約選択部１２１は、解ベクトル移動部１１１が算出した移動後ベクトルをｘｔ＋１／２に基づいて、有効でない制約を選択する（ステップＳ２０１）。制約選択部１２１は、例えば、次のようにして有効でない制約を選択することができる。
【００５４】
すなわち、まず、制約選択部１２１は、行列ベクトル積ｙ＝Ａｘｔ＋１／２を計算する。次に、制約選択部１２１は、ベクトルｙの各成分の絶対値を降順に並べ、その値が大きい順にｓ個を選択する。そして、制約選択部１２１は、選択したｓ個の成分に対応する制約を、有効でない制約に選択する。
【００５５】
次に、厳密最小化計算部１１２の制約付き最小化計算部１２２は、制約選択部１２１により選択されなかった制約を満たすように、関数値ｆ（ｘ）が最小となる解ベクトルｘｔ＋１を算出する（ステップＳ２０２）。制約付き最小化計算部１２２は、例えば、射影勾配法等の最適化手法を用いることで、解ベクトルｘｔ＋１を算出することができる。なお、特に、単純なスパース制約の場合は、単に選択されなかった変数を０に固定した問題を解くことで、解ベクトルｘｔ＋１を算出することができる。
【００５６】
以上により、本発明の実施の形態における解算出装置１０は、近似を用いることなく、線形変換されたスパース制約下での最適化問題を解くことができる。これにより、本発明の実施の形態における解算出装置１０は、高い精度で解ベクトルを得ることができる。
【００５７】
また、本発明の実施の形態における解算出装置１０では、関数が悪条件である場合であっても、線形変換されたスパース制約下での最適化問題を解くことができる。
【００５８】
＜比較例＞
次に、人工データを用いた実験を行った場合における本発明と従来技術との比較例について、図６を参照しながら説明する。図６は、本発明と従来技術との比較例を示す図である。
【００５９】
図６では、変換行列Ａは一階差分行列とし、関数ｆはランダムに生成したものを入力とした。また、従来技術としては、非特許文献１に開示されているＡＨＴＰ（Analysis Hard Thresholding Pursuit）と、非特許文献２に開示されているＦＩＳＴＡ（Fast Iterative Soft Thresholding Algorithm）とを用いた。
【００６０】
図６（ａ）は、本発明と従来技術とにおける出力解の精度の比較例である。図６（ａ）に示す比較例では、評価指標としてテスト誤差を用いた。すなわち、テスト誤差が低い程、出力解の精度が高いことを示している。図６（ａ）に示すように、従来技術と比較して、本発明が最もテスト誤差が低い（すなわち、出力解の精度が高い）ことがわかる。なお、Ｏｐｔｉｃａｌは理論上の最適値である。
【００６１】
図６（ｂ）は、本発明と従来技術とにおいて、出力解を得るまでのテスト誤差の変化の比較例である。図６（ｂ）に示すように、従来技術と比較して、本発明が最も短い時間で計算を完了していることがわかる。
【００６２】
以上のように、本発明の実施の形態における解算出装置１０によれば、従来技術と比較して、より精度の高い解を、より短時間で得ることができるようになる。
【００６３】
本発明は、具体的に開示された上記の実施形態に限定されるものではなく、特許請求の範囲から逸脱することなく、種々の変形や変更が可能である。
【符号の説明】
【００６４】
１０        解算出装置
１００      解算出プログラム
１０１      入力部
１０２      解ベクトル算出部
１０３      出力部
１１１      解ベクトル移動部
１１２      厳密最小化計算部
１１３      終了条件判定部
１２１      制約選択部
１２２      制約付き最小化計算部
【図１】
2018195232.tif 000006
【図２】
2018195232.tif 000007
【図３】
2018195232.tif 000008
【図４】
2018195232.tif 000009
【図５】
2018195232.tif 000010
【図６】
2018195232.tif 000011