(57)【要約】【課題】より少ない計算量で非凸スパース最適化問題に対して最適解を保証する最適解探索技術を提供することである。【解決手段】本発明の一態様は、与えられた目的関数及び条件に対して最良優先探索を実行する主装置部と、前記最良優先探索の優先度を計算する計算部と、を有する最適解探索装置に関する。【選択図】図５
2019168748.tif 000002
【特許請求の範囲】
【請求項１】
与えられた目的関数及び条件に対して最良優先探索を実行する主装置部と、
前記最良優先探索の優先度を計算する計算部と、
を有する最適解探索装置。
【請求項２】
与えられた集合Sの要素数|S|と正の整数kとが同じである場合、前記計算部は、k個の非ゼロ成分のパターンが全て指定された最小化問題を解くことによって前記優先度を計算し、
前記優先度と前記目的関数の値とが同じである場合、前記主装置部は、前記目的関数の値を最適解として取得することによって前記最良優先探索を終了する、請求項１記載の最適解探索装置。
【請求項３】
プロセッサが、与えられた目的関数及び条件に対して最良優先探索を実行するステップと、
前記プロセッサが、前記最良優先探索の優先度を計算するステップと、
を有する最適解探索方法。
【請求項４】
与えられた集合Sの要素数|S|と正の整数kとが同じである場合、前記計算するステップは、k個の非ゼロ成分のパターンが全て指定された最小化問題を解くことによって前記優先度を計算し、
前記優先度と前記目的関数の値とが同じである場合、前記実行するステップは、前記目的関数の値を最適解として取得することによって前記最良優先探索を終了する、請求項３記載の最適解探索方法。
【請求項５】
請求項１又は２記載の最適解探索装置の各部としてプロセッサを機能させるプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、スパース推定などの分野で現れる非凸スパース最適化問題に関する。
【背景技術】
【０００２】
非凸スパース最適化問題は、d個の成分を持つ変数ベクトルx∈Rdがk個（k<d）の非ゼロ成分しか持たないという制約の下で、xについての関数P(x)の値を最小化する問題である。例えば、ノイズを含むd個の値を持つ信号からノイズを除去し、k個の非ゼロ要素からなる真の信号の値を復元したいというような状況で非凸スパース最適化問題は現れる。
【０００３】
非凸スパース最適化問題に対しては、非特許文献１のような高速ではあるが最適解が得られる保証がない手法が広く研究されてきた。一方、最適解を確実に得るための手法としては、d個の成分の中から非ゼロの値を取りうるk個の選び方を全て試すような素朴な全探索法以外は知られていない。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】Bo Liu, Xiao-Tong Yuan, Lezi Wang, Qingshan Liu and Dimitris N. Metaxas, "Dual Iterative Hard Thresholding: From Non-convex Sparse Minimization to Non-smooth Concave Maximization", Proceedings of the 34th international Conference on Machine Learning, 70: 2179-2187, 2017.
【非特許文献２】Judea Pearl, "Intelligent Search Strategies for Computer Problem Solving", Addison-Wesley Longman Publishing Co., Inc., 1984.
【発明の概要】
【発明が解決しようとする課題】
【０００５】
このような素朴な方法は、最適解を確実に得られる手法としては現状唯一のものであるが、dCk通りの全てのパターンに対して最適化問題を解く必要があり、膨大な計算量が必要となる。
【０００６】
上述した問題点を鑑み、本発明の課題は、より少ない計算量で非凸スパース最適化問題に対して最適解を保証する最適解探索技術を提供することである。
【課題を解決するための手段】
【０００７】
上記課題を解決するため、本発明の一態様は、与えられた目的関数及び条件に対して最良優先探索を実行する主装置部と、前記最良優先探索の優先度を計算する計算部と、を有する最適解探索装置に関する。
【発明の効果】
【０００８】
本発明によると、より少ない計算量で非凸スパース最適化問題に対して最適解を保証する最適解探索技術を提供することができる。
【図面の簡単な説明】
【０００９】
【図１】本発明の一実施例による状態空間木の具体例を示す図である。
【図２】本発明の一実施例による最適解探索装置の機能構成を示すブロック図である。
【図３】本発明の一実施例による最良優先探索の擬似コードを示す図である。
【図４】本発明の一実施例によるORACLE(S)の擬似コードを示す図である。
【図５】本発明の一実施例による最適解探索処理を示すフローチャートである。
【図６】本発明の一実施例による最適解探索処理と従来技術による全探索法との実行時間の比較を示す図である。
【発明を実施するための形態】
【００１０】
以下の実施例では、非凸スパース最適化問題に対して最適解を提供する最適解探索装置が開示される。後述される実施例による最適解探索装置は、最適な非ゼロ成分のパターンを探索するためのアプローチとして最良優先探索（例えば、非特許文献２を参照）を利用すると共に、当該最良優先探索の優先度計算において、非特許文献１に記載されるようなDIHT(Dual Iterative Hard Thresholding)でなく、以下で詳細に説明されるような非ゼロ成分のパターンが全て指定された最小化問題を解く手法を適用する。
【００１１】
まず、図１を参照して、本発明の一実施例による最適解探索処理を概略する。任意の正の整数mに対して、[m]={1, 2, ..., m}とする。また、あるd次元ベクトルx∈Rdが与えられたとき、
【００１２】
【数１】
2019168748.tif 000003
をベクトルxの成分で値がゼロでないものの個数とする。さらに、P: Rd→Rをベクトルxを変数とする関数（目的関数）とする。
【００１３】
以下では、ある与えられたd以下の正の整数kに対して、次のような最小化問題の最適解、すなわち、非ゼロ成分がk個以下であって、P(x)の値を最小にするxを計算することを考える。
【００１４】
【数２】
2019168748.tif 000004
まず、この問題のための最良優先探索について説明する。当該探索は次のように定義される状態空間木の上で行われる。状態空間木G=(V, E)は、Vを頂点集合とし、Eを有向枝集合とする木構造である。ここで、与えられたS⊆[d]に対して、Sの要素数を|S|と表し、Sに含まれる正の整数の最大値をmaxSと表す。このとき、Vは次のように定義できる。
【００１５】
【数３】
2019168748.tif 000005
また、Eは次のように定義できる。
【００１６】
【数４】
2019168748.tif 000006
すなわち、Gは空集合
【００１７】
【数５】
2019168748.tif 000007
を根とする木構造となる。例として、d=3, k=2の場合のGを図１に示す。例えば、{1}と{1, 3}との間には、
【００１８】
【数６】
2019168748.tif 000008
が成立しているため、有向枝({1}, {1, 3})がEに存在する。
【００１９】
本実施例による最適解探索装置では、以下で詳細に説明するように、このように定義された状態空間木の上で探索を行うことで、最適な非ゼロ成分の出現パターンを発見する。
【００２０】
図２は、本発明の一実施例による最適解探索装置の機能構成を示すブロック図である。
【００２１】
図２に示されるように、最適解探索装置１００は、入力部１１０、主装置部１２０、計算部１３０及び出力部１４０を有する。
【００２２】
入力部１１０は、最良優先探索のための目的関数P(.)と条件kとを入力データとして受け取り、主装置部１２０にわたす。
【００２３】
主装置部１２０は、入力された目的関数P(.)と条件kとに対して最良優先探索を実行する。具体的には、主装置部１２０は、図３に示されるような計算手順Algorithm 1に従って最良優先探索を実行する。
【００２４】
ここで、当該探索では、当該技術分野において知られるMinHeapと呼ばれるデータ構造を用いる。MinHeapは、S∈Vと、Sに対して計算される値LowS∈Rと、k個以下の非ゼロ成分からなる解SolS∈Rdの三つ組<LowS, SolS, S>を保存するデータ構造である。MinHeap.push(<LowS, SolS, S>)によって新たな三つ組<LowS, SolS, S>をMinHeapに追加することができる。また、MinHeap.pop()によってMinHeapに保存されている三つ組の中でLowSの値が最小である三つ組<LowS, SolS, S>を取り出すことができる。
【００２５】
図３に示されるAlgorithm 1では、与えられたSに対してLowS, SolSを計算する手段として、後述されるORACLE(S)が利用可能であると仮定し、当該最良優先探索の手続を記述している。手続としては、LowS=P(SolS)となるSが得られるまで、LowSが小さい部分から順に探索を進めていく。すなわち、LowSが低いものほど優先度が高いとみなされる。図示されるように、優先度LowSと目的関数P(SolS)の値とが同じである場合、主装置部１２０は、目的関数P(SolS)の値SolSを最適解として取得し、最良優先探索を終了する。
【００２６】
計算部１３０は、最良優先探索の優先度を計算する。具体的には、計算部１３０は、上述した最良優先探索におけるORACLE(S)を実現する。すなわち、計算部１３０は、図４に示されるような計算手順Algorithm 2を実行する。supp(x)⊆[d]は、xが非ゼロとなる添え字の集合を表すものとする。
【００２７】
まず、|S|=kである場合、計算部１３０は、k個の非ゼロ成分のパターンが全て指定された最小化問題
【００２８】
【数７】
2019168748.tif 000009
を解くことによって、SolS, LowSを取得する。すなわち、与えられた集合Sの要素数|S|と正の整数kとが同じである場合、計算部１３０は、k個の非ゼロ成分のパターンが全て指定された最小化問題を解くことによって優先度を計算する。この問題を解くこと自体は、当該技術分野において広く知られた基本的な最適化手法を用いて実現できる。
【００２９】
他方、|S|<kである場合、計算部１３０は、例えば、非特許文献１において提案されるDIHT手法を用いてSolS, LowSを計算できる。なお、DIHTについては本発明の範囲外であるため、詳細は割愛する。
【００３０】
出力部１４０は、最良優先探索において取得した最適解SolSを出力する。
【００３１】
ここで、最適解探索装置１００は、典型的には、サーバなどの計算装置により実現されてもよく、例えば、バスを介し相互接続されるドライブ装置、補助記憶装置、メモリ装置、プロセッサ、インタフェース装置及び通信装置から構成されてもよい。最適解探索装置１００における各種機能及び処理を実現するプログラムを含む各種コンピュータプログラムは、ＣＤ−ＲＯＭ（Ｃｏｍｐａｃｔ  Ｄｉｓｋ−Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）、ＤＶＤ（Ｄｉｇｉｔａｌ  Ｖｅｒｓａｔｉｌｅ  Ｄｉｓｋ）、フラッシュメモリなどの記録媒体によって提供されてもよい。プログラムを記憶した記録媒体がドライブ装置にセットされると、プログラムが記録媒体からドライブ装置を介して補助記憶装置にインストールされる。但し、プログラムのインストールは必ずしも記録媒体により行う必要はなく、ネットワークなどを介し何れかの外部装置からダウンロードするようにしてもよい。補助記憶装置は、インストールされたプログラムを格納すると共に、必要なファイルやデータなどを格納する。メモリ装置は、プログラムの起動指示があった場合に、補助記憶装置からプログラムやデータを読み出して格納する。プロセッサは、メモリ装置に格納されたプログラムやプログラムを実行するのに必要なパラメータなどの各種データに従って、上述した最適解探索装置１００の各種機能及び処理を実行する。インタフェース装置は、ネットワーク又は外部装置に接続するための通信インタフェースとして用いられる。通信装置は、インターネットなどのネットワークと通信するための各種通信処理を実行する。
【００３２】
しかしながら、最適解探索装置１００は、上述したハードウェア構成に限定されるものでなく、他の何れか適切なハードウェア構成により実現されてもよい。
【００３３】
図５は、本発明の一実施例による最適解探索処理を示すフローチャートである。
【００３４】
ステップS101において、入力部１１０は、例えば、装置起動時に、関数P及び非ゼロ成分数の上限数kを受け取る。
【００３５】
ステップS102において、主装置部１２０は、状態空間木上で最良優先探索を実行する。ただし、状態空間木は事前に全て構築した場合、膨大なメモリを要するため、Algorithm 1に示されるように、主装置部１２０は、実行中に必要になった部分から逐次的に探索を行うようにしてもよい。また、探索中にLowS, SolSの計算が必要になった場合、主装置部１２０は、計算部１３０にSをわたし、計算部１３０のORACLE(S)によって計算されたLowS, SolSを取得する。
【００３６】
ステップS103において、主装置部１２０は、Algorithm 1に示されるように、LowS=P(SolS)を検出すると、当該Solsを最適解として決定し記録する。
【００３７】
ステップS104において、出力部１４０は、最適解SolSを出力する。
【００３８】
上述した実施例による最適解探索装置１００によると、上述したような最良優先探索とORACLEとを組み合わせることによって、従来技術による全探索法と比較して、高速に非凸スパース最適化問題を解くことができる。図６は、本発明の一実施例による最適解探索処理と従来技術による全探索法との実行時間の比較を示す図である。問題のサイズとして、d=20, 40, 60, 80について、k=0.05dとした場合を考える。図示されるように、本実施例による最適解探索処理は、全探索法と比較して、最大１０００倍以上高速に最適解を計算可能であることが観察できる。また、図の傾向から、さらに大きな問題サイズでは、計算時間により大きな差がつくことが予想される。
【００３９】
以上、本発明の実施例について詳述したが、本発明は上述した特定の実施形態に限定されるものではなく、特許請求の範囲に記載された本発明の要旨の範囲内において、種々の変形・変更が可能である。
【符号の説明】
【００４０】
１００  最適解探索装置
１１０  入力部
１２０  主装置部
１３０  計算部
１４０  出力部
【図１】
2019168748.tif 000010
【図２】
2019168748.tif 000011
【図３】
2019168748.tif 000012
【図４】
2019168748.tif 000013
【図５】
2019168748.tif 000014
【図６】
2019168748.tif 000015