特許ウォッチ

公開番号2024046750
公報種別公開特許公報(A)
公開日2024-04-04
出願番号2023152927
出願日2023-09-20
発明の名称最適化問題の逐次的グループ処理
出願人富士通株式会社
代理人個人,個人
主分類G06N 99/00 20190101AFI20240328BHJP(計算;計数)
要約【課題】最適化問題の逐次的グループ処理のための方法等を提供する。
【解決手段】方法は、最適化問題に関係がある特性を表す変数と、変数に対応する重みとを取得することを含んでよい。変数は、変数の一部を夫々が含むグループに分けられてよい。方法は、変数の各グループについてグループ局所場行列を取得することを更に含んでもよい。各局所場行列は、各々の変数と他の変数との間の、それらの各々の重みによって影響を及ぼされるインタラクションを示す局所場値を含んでよい。方法は準逐次的試行プロセスを実行することを含んでもよく、それは、変数に対する試行の実行を含む確率過程であってよく、各試行は、変数の状態を変更すべきかどうかを決定する。準逐次的試行プロセスは、確率過程の結果に基づいてグループ局所場行列の全てを更新することを含んでもよく、最適化問題に対する解は、結果に基づいて決定され得る。
【選択図】図8
特許請求の範囲【請求項１】
最適化問題に関係がある特性を夫々が表している複数の変数を取得することと、
前記変数に対応する重みを取得することであり、各々の重みは、各々の変数と前記最適化問題に関係がある１つ以上の他の変数との間の１つ以上の関係に関係がある、ことと、
前記変数を複数のグループに分けることであり、各々のグループは、前記複数の変数のうちの一部の変数を含む、ことと、
変数の各々のグループごとに各々のグループ局所場行列を取得することであり、前記各々の局所場行列は、前記各々の変数の前記各々の重みによって影響を及ぼされる前記複数の変数のうちの各変数と他の変数との間のインタラクションを夫々示している局所場値を含む、ことと、
前記複数のグループに対して準逐次的試行プロセスを実行することと、
前記準逐次的試行プロセスに基づいて前記最適化問題に対する解を決定することと
を有し、前記準逐次的試行プロセスは、
前記複数のグループの第１変数の第１グループに対応する第１重み及び第１局所場値に基づいて、前記第１グループに対して第１確率過程を実行することであり、前記第１確率過程は、前記第１グループの前記第１変数のうちの１つ以上の変数の各々の状態を変更することに関連し、前記第１確率過程は、前記第１変数のうちの１つ以上の変数に対して第１試行を実行することを含み、各々の第１試行は、各々の第１変数の各々の状態を変更すべきかどうかを決定する、ことと、
前記第１確率過程の結果に基づいて前記グループ局所場行列の全てを更新することと、
前記複数のグループの第２変数の第２グループに対応する第２重み及び第２局所場値に基づいて、前記第２グループに対して第２確率過程を実行することであり、前記第２確率過程は、前記第２グループの前記第２変数のうちの１つ以上の変数の各々の状態を変更することに関連し、前記第２確率過程は、前記第２変数のうちの１つ以上の変数に対して第２試行を実行することを含み、各々の第２試行は、各々の第２変数の各々の状態を変更すべきかどうかを決定する、ことと、
前記第２確率過程の結果に基づいて前記グループ局所場行列の全てを更新することと
を含む、
方法。
続きを表示（約 2,100 文字）【請求項２】
前記変数に対応する前記重みを取得することは、前記最適化問題に含まれる他の変数の夫々に対する各変数の重みを含む重み行列を参照することを含む、
請求項１に記載の方法。
【請求項３】
前記重み行列は、前記最適化問題に含まれる他の変数の夫々に対する各変数の重みを含むが、各変数と他の変数の夫々との間の双方向の重みを含まない半重み行列である、
請求項２に記載の方法。
【請求項４】
前記変数は第１メモリに格納され、
前記重み行列を参照することは、前記重み行列が格納されている第２メモリにアクセスすることを含み、
前記第２メモリは前記第１メモリとは別個である、
請求項２に記載の方法。
【請求項５】
前記第１確率過程のために実行される前記第１試行の数は、各々の第１変数に関連した各々の温度に基づいて決定され、
前記温度は第１温度から始まり、
前記温度は、前記第１確率過程の結果に基づいて前記グループ局所場行列の全てを更新した後で、前記第１温度よりも低い第２温度に更新する、
請求項１に記載の方法。
【請求項６】
前記変数を前記複数のグループに分けることは、前記準逐次的試行プロセスを実行するよう構成されるコンピュータシステムのコンピューティングコアの数と、前記コンピューティングコアの夫々のプロセッシング能力とに基づく、
請求項１に記載の方法。
【請求項７】
前記最適化問題は、二次制約なし二値最適化（ＱＵＢＯ）問題である、
請求項１に記載の方法。
【請求項８】
複数のコンピューティングコアを夫々が含む１つ以上のプロセッサと、
ローカルメモリと、
オフチップメモリと、
命令を記憶するよう構成される１つ以上の非一時的なコンピュータ可読記憶媒体と
を有するシステムであって、
前記命令は、前記ローカルメモリによって実行されることに応答して、前記システムに、
最適化問題に関係がある特性を夫々が表している複数の変数を取得することと、
前記変数に対応する重みを取得することであり、各々の重みは、各々の変数と前記最適化問題に関係がある１つ以上の他の変数との間の１つ以上の関係に関係がある、ことと、
前記変数を複数のグループに分けることであり、各々のグループは、前記複数の変数のうちの一部の変数を含む、ことと、
変数の各々のグループごとに各々のグループ局所場行列を取得することであり、前記各々の局所場行列は、前記各々の変数の前記各々の重みによって影響を及ぼされる前記複数の変数のうちの各変数と他の変数との間のインタラクションを夫々示している局所場値を含む、ことと、
前記複数のグループに対して準逐次的試行プロセスを実行することと、
前記準逐次的試行プロセスに基づいて前記最適化問題に対する解を決定することと
を有する動作を実行させ、前記準逐次的試行プロセスは、
前記複数のグループの第１変数の第１グループに対応する第１重み及び第１局所場値に基づいて、前記第１グループに対して第１確率過程を実行することであり、前記第１確率過程は、前記第１グループの前記第１変数のうちの１つ以上の変数の各々の状態を変更することに関連し、前記第１確率過程は、前記第１変数のうちの１つ以上の変数に対して第１試行を実行することを含み、各々の第１試行は、各々の第１変数の各々の状態を変更すべきかどうかを決定する、ことと、
前記第１確率過程の結果に基づいて前記グループ局所場行列の全てを更新することと、
前記複数のグループの第２変数の第２グループに対応する第２重み及び第２局所場値に基づいて、前記第２グループに対して第２確率過程を実行することであり、前記第２確率過程は、前記第２グループの前記第２変数のうちの１つ以上の変数の各々の状態を変更することに関連し、前記第２確率過程は、前記第２変数のうちの１つ以上の変数に対して第２試行を実行することを含み、各々の第２試行は、各々の第２変数の各々の状態を変更すべきかどうかを決定する、ことと、
前記第２確率過程の結果に基づいて前記グループ局所場行列の全てを更新することと
を含む、
システム。
【請求項９】
前記変数に対応する前記重みを取得することは、前記最適化問題に含まれる他の変数の夫々に対する各変数の重みを含む重み行列を参照することを含む、
請求項８に記載のシステム。
【請求項１０】
前記重み行列は、前記最適化問題に含まれる他の変数の夫々に対する各変数の重みを含むが、各変数と他の変数の夫々との間の双方向の重みを含まない半重み行列である、
請求項９に記載のシステム。
（【請求項１１】以降は省略されています）
発明の詳細な説明【技術分野】
【０００１】
本開示は、概して、最適化問題の逐次的グループ処理に関係がある。
続きを表示（約 2,700 文字）【背景技術】
【０００２】
最適化問題は、最適化問題を表す関数について最大値又は最小値を返す入力値を見つけることによって解くことができる。いくつかの最適化問題は、夫々が複数のとり得る入力値を含む複数の入力を含んでもよく、それにより、最適化問題について解く最大値又は最小値の決定は、複数の入力のうちの１つ以上を調整することを含んでもよい。コンピュータシステムは、最適化問題に対する解をより効果的かつ効率的に特定するために使用されることがある。
【０００３】
本開示で請求される対象は、上述された任意の欠点を解消する実施形態又は上述された環境でしか動作しない実施形態に限られない。むしろ、この背景は、本開示で記載されるいくつかの実施形態が実施される可能性がある一つの例示的な技術分野を説明するためにのみ与えられている。
【発明の概要】
【０００４】
本開示の態様に従って、方法は、最適化問題に関係がある特性を表す変数と、変数に対応する重みとを取得することを含んでよい。変数は、変数の一部を夫々が含むグループに分けられてよい。方法は、変数の各グループについてグループ局所場行列（group local field matrix）を取得することを含んでもよい。各局所場行列は、各々の変数と他の変数との間の、それらの各々の重みによって影響を及ぼされるインタラクションを示す局所場値を含んでよい。方法は準逐次的試行プロセス（semi-sequential trial process）を実行することを含んでもよく、それは、変数に対する試行の実行を含む確率過程（stochastic process）であってよく、各試行は、変数の状態を変更すべきかどうかを決定する。準逐次的試行プロセスは、確率過程の結果に基づいてグループ局所場行列の全てを更新することを含んでもよく、最適化問題に対する解は、結果に基づいて決定され得る。
【０００５】
実施形態の目的及び利点は、特許請求の範囲で特に指し示されている要素、特徴、及び組み合わせによって少なくとも実現及び達成されるであろう。上記の概要及び下記の詳細な説明はいずれも、請求される発明の例示であって、その限定ではないことが理解されるべきである。
【図面の簡単な説明】
【０００６】
例示的な実施形態は、添付の図面を通して、追加の特定性及び詳細を用いて記載及び説明されるであろう。
【０００７】
本開示の少なくとも１つの実施形態に従って、最適化問題を解くことに関係がある１つ以上の動作を実行するよう構成されるマルチコアコンピュータプロセッサアーキテクチャの例示的な環境の図である。
本開示の少なくとも１つの実施形態に従って、最適化問題を解くための試行ステップ及び更新ステップを実行するよう構成されるマルチコアコンピュータプロセッサアーキテクチャの例示的な実施形態の図である。
本開示の少なくとも１つの実施形態に従って、最適化問題に関連したニューロンを１つ以上のコンピューティングコアにマッピングする例示的な実施形態の図である。
本開示の少なくとも１つの実施形態に従って、試行カーネルにおける１つ以上のニューロンの選択及び試行の例示的な実施形態の図である。
本開示の少なくとも１つの実施形態に従って、マルチコアコンピュータプロセッサアーキテクチャの試行カーネルと更新カーネルとの間のやりとりを表す図である。
本開示の少なくとも１つの実施形態に従って、重み行列の例示的な実施形態を表す。
本開示の少なくとも１つの実施形態に従って、重み行列の転置を表す。
本開示の少なくとも１つの実施形態に従って、ハイブリッド重みアクセスプロセスの例示的な実施形態を表す。
本開示の少なくとも１つの実施形態に従って、マルチコアコンピュータプロセッサアーキテクチャを使用して最適化問題に関連した動作を実行する例示的な方法のフローチャートである。
例示的なコンピューティングシステムである。
【発明を実施するための形態】
【０００８】
多種多様な入力変数が最適化問題に対する解を決定するよう調整される可能性があるので、最適化問題を解くことは困難である認められる場合がある。追加的に、又は代替的に、最適化問題に対する決定された解が最良の解又は高度に最適化された解を表すかどうかを結論づけることは難しい場合がある。例えば、特定の最適化問題は、その特定の最適化問題に関連したパラメータを最大化しようとすることがあるが、特定の解がパラメータのとり得る最大値をもたらすかどうか、又はパラメータの値がとり得る最大値のある閾範囲内にあるかどうかを確認することは難しい場合がある。
【０００９】
コンピュータシステムは、最適化問題を解くことを支援するために使用されることがある。しかし、様々な計算手法は、コンピュータシステムによってもたらされる解が最適化問題に対する最適化された解であるかどうかを特定する際に同様の課題に直面する。例えば、特定の計算手法は、特定の最適化問題に対する特定の解を決定することができる。しかし、特定の計算手法が、特定の最適化問題の極値を表す解を決定している可能性があるので、特定の解が最適解であるかどうかの確認は難しい場合がある。追加的に、又は代替的に、最適化問題に対する最適化された解の決定が多数の動作及び計算を伴う反復的なプロセスである可能性があるので、最適化問題に関連した計算の実行には、相当な計算資源利用量が伴う場合がある。
【００１０】
最適化問題の複雑性及び多変量の性質のために、最適化問題に対する解を依然としてもたらしながらコンピュータ資源利用量を減らすように、近似方法が使用されてもよい。例えば、二次制約なし二値最適化（quadratic unconstrained binary optimization）（ＱＵＢＯ）モデルが、バイナリ入力値（例えば、０又は１）を持った一連のノードとして特定の最適化問題を表すために使用されてもよい。しかし、ＱＵＢＯ問題及び他の二値最適化問題を解く現在の方法は、少数の入力変数にした対応することができず、かつ／あるいは、変数の値が増えるにつれて、二値最適化問題を解くために大量の処理時間及び計算資源を必要とする可能性がある。
（【００１１】以降は省略されています）

関連特許