(57)【要約】  遅延更新規則を用いて並列計算する場合の計算速度を高速化できる並列割当最適化装置を提供する。並列割当算出部８１は、並列に行われる処理ごとに割り当てられる対象データ中の要素の候補である並列割当候補を算出する。並列計算量推定処理部８２は、並列割当候補が割り当てられた場合の並列処理に要する計算量を対象データ中の非ゼロ要素数に基づいて推定する。最適性判定処理部８３は、算出された計算量に基づいて並列割当候補が最適か否か判定して、並列に行われる処理ごとに最適な要素を割り当てる。
2013179578.tif 000002
【特許請求の範囲】
【請求項１】
並列に行われる処理ごとに割り当てられる対象データ中の要素の候補である並列割当候補を算出する並列割当算出部と、
前記並列割当候補が割り当てられた場合の並列処理に要する計算量を対象データ中の非ゼロ要素数に基づいて推定する並列計算量推定処理部と、
算出された計算量に基づいて前記並列割当候補が最適か否か判定して、並列に行われる処理ごとに最適な要素を割り当てる最適性判定処理部とを備えた
ことを特徴とする並列割当最適化装置。
【請求項２】
並列計算量推定処理部は、並列に行われる処理ごとに割り当てられた非ゼロ要素数の最大値を当該処理ごとに算出し、並列に行われる全処理の最大値の和を並列処理に要する計算量と推定し、
最適性判定処理部は、算出された並列割当候補のうち、前記計算量が最小の並列割当候補を最適な要素として割り当てる
請求項１記載の並列割当最適化装置。
【請求項３】
並列割当算出部は、要素の割り当てに用いられる属性順序を生成し、当該属性順序に則して各要素をチャンクに割り当てることで並列割当候補を算出し、
並列計算量推定処理部は、前記属性順序に則して前記要素を前記チャンクに割り当てた場合における計算量を当該チャンクごとに推定し、
最適性判定処理部は、前記計算量が最小になるチャンクに前記要素を割り当てる
請求項１記載の並列割当最適化装置。
【請求項４】
対象データ中の要素が割り当てられたチャンクのうち、非ゼロ要素数が最も大きいチャンクにおける当該非ゼロ要素数を当該対象データごとに記憶する計算最大量記憶部と、
対象データごとに非ゼロ要素数が最も大きいチャンクを特定する情報を記憶する計算量最大チャンク位置記憶部とを備え、
並列計算量推定処理部は、前記計算量最大チャンク位置記憶部に記憶された情報に基づいて特定される非ゼロ要素数が最も大きいチャンクに対して非ゼロ要素が割り当てられた対象データ数を、前記計算最大量記憶部に記憶された非ゼロ要素数の合計に加算することにより計算量を算出する
請求項１記載の並列割当最適化装置。
【請求項５】
各チャンクに割り当てられる各対象データ中の非ゼロ要素数を記憶するチャンク計算量記憶部を備え、
並列計算量推定処理部は、前記チャンク計算量記憶部に記憶された各対象データ中の非ゼロ要素数に対して新たに割り当てられた非ゼロ要素数を加算して更新し、非ゼロ要素数が最も大きいチャンクに対して非ゼロ要素が割り当てられた場合には、計算量最大チャンク位置記憶部が記憶する情報を、当該チャンクが非ゼロ要素数が最も大きいチャンクと特定できる情報に更新し、かつ、計算最大量記憶部が記憶する対象データの非ゼロ要素数に１加算し、
並列計算量推定処理部は、非ゼロ要素数が最も大きいチャンクに対して非ゼロ要素が割り当てられなかった場合かつ計算最大量記憶部が記憶する対象データの非ゼロ要素数に１加算した値とチャンク計算量記憶部に記憶された対象データ中の非ゼロ要素数とが等しくなった場合には、計算量最大チャンク位置記憶部が記憶する情報を、割り当てられたチャンクが非ゼロ要素数が最も大きいチャンクと特定できる情報に更新する
請求項４記載の並列割当最適化装置。
【請求項６】
並列に行われる処理ごとに割り当てられる対象データ中の要素の候補である並列割当候補を算出し、
前記並列割当候補が割り当てられた場合の並列処理に要する計算量を対象データ中の非ゼロ要素数に基づいて推定し、
算出された計算量に基づいて前記並列割当候補が最適か否か判定して、並列に行われる処理ごとに最適な要素を割り当てる
ことを特徴とする並列割当最適化方法。
【請求項７】
並列に行われる処理ごとに割り当てられた非ゼロ要素数の最大値を当該処理ごとに算出し、並列に行われる全処理の最大値の和を並列処理に要する計算量と推定し、
算出された並列割当候補のうち、前記計算量が最小の並列割当候補を最適な要素として割り当てる
請求項６記載の並列割当最適化方法。
【請求項８】
コンピュータに、
並列に行われる処理ごとに割り当てられる対象データ中の要素の候補である並列割当候補を算出する並列割当算出処理、
前記並列割当候補が割り当てられた場合の並列処理に要する計算量を対象データ中の非ゼロ要素数に基づいて推定する並列計算量推定処理、および、
算出された計算量に基づいて前記並列割当候補が最適か否か判定して、並列に行われる処理ごとに最適な要素を割り当てる最適性判定処理
を実行させるための並列割当最適化プログラムを記録したコンピュータ読取可能な記録媒体。
【請求項９】
コンピュータに、
並列計算量推定処理で、並列に行われる処理ごとに割り当てられた非ゼロ要素数の最大値を当該処理ごとに算出させ、並列に行われる全処理の最大値の和を並列処理に要する計算量と推定させ、
最適性判定処理で、算出された並列割当候補のうち、前記計算量が最小の並列割当候補を最適な要素として割り当てさせる
ための並列割当最適化プログラムを記録した請求項８記載のコンピュータ読取可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、各並列処理に割り当てるデータを最適化する並列割当最適化装置、並列割当最適化方法およびコンピュータ読取可能な記録媒体に関する。
【背景技術】
【０００２】
近年、テキストの単語ベクトルデータ、疾病ログ（疾病にかかっているかどうかの論理値ベクトル）、購買履歴（商品を買ったかどうかの論理値ベクトル）など、大規模であるがデータ中の多くがゼロ要素である「疎な」データを分析する技術が重要になっている。【０００３】
疎なデータに対しては、データの多くが０である事を利用した効率的なデータ構造や計算技術が研究、および開発されている。このようなデータ構造として、例えば、非ゼロ要素の位置とその値を記憶する疎データ構造が挙げられる。また、このような計算技術として、０に何を乗じても０である性質を利用し、非ゼロ要素同士の掛け算のみを行う疎行列演算などが挙げられる。【０００４】
また、近年、機械学習分野において、データの疎性を利用した「遅延更新（ｌａｚｙ  ｕｐｄａｔｅ）」という学習規則が提案されている。これは、特殊なパラメータ最適化則をもつ学習器に対して、データのゼロ要素に対する更新を「遅延」させて、学習処理を高速化する技術である。【０００５】
非特許文献１には、学習器を最適化する方法が記載されている。以下、非特許文献１に記載された線形判別／回帰モデルに遅延更新規則を利用した場合の例を説明する。非特許文献１に記載された更新規則は、遅延なしの更新規則である。具体的には、非特許文献１に記載された更新規則は、損失関数の勾配方向への第一更新ステップと、モデル正則化関数に対する第二の更新ステップを繰り返すことで、学習器を最適化する。【０００６】
非特許文献１に記載された更新規則において、データ要素がゼロの場合には、損失関数の勾配がゼロになる。そのため、値がゼロのデータが連続した場合、第二更新ステップのみ繰り返される。このとき、第二更新ステップの計算は、複数回まとめて実行可能な性質を有する。そのため、この処理に遅延更新を利用した場合には、要素がゼロのデータが連続している間は更新を行わずに、要素が非ゼロのデータが現れた際に遅延させておいて第二更新ステップをまとめて行うことができる。そのため、計算量を大幅に削減できる。
【先行技術文献】
【非特許文献】
【０００７】
【非特許文献１】John Duchi, Yoram Singer, "Efficient Online and Batch Learning Using Forward Backward Splitting", Journal of Machine Learning Research, p.2899-2934, 2009
【発明の概要】
【発明が解決しようとする課題】
【０００８】
しかし、遅延更新規則を単純に並列化計算に適用したとしても、必ずしも高速化できるとは限らない。この問題を、図８を参照して説明する。図８は、並列割当対象のデータ例を示す説明図である。図８に示す例では、データテーブルの各行がデータを表わし、データテーブルの各列が各データの属性値を表している。また、各データは、データＩＤで識別され、各属性は、属性ＩＤで識別される。【０００９】
以下、データの内容を表す要素（例えば、属性）を並列化する際、各要素が割り当てられる領域のことをチャンクと記す。すなわち、データの各要素を各チャンクに割り当て、そのチャンクごとに並列化処理が行われる。図８に示す例では、各データの要素が３つのチャンクに割り当てられていることを示す。【００１０】
遅延更新規則では、非ゼロ要素の位置でパラメータが更新されるため、計算量は、模式的に、図８の右部分に例示した非並列および並列に関する計算量として表すことができる。【００１１】
ここで、図８に例示する３行目のデータに着目する。このデータでは、非並列に処理を行った場合も、並列に処理を行った場合も計算量が４になる。すなわち、この場合、並列計算の効果が全く生じないことが分かる。すなわち、遅延更新を利用して学習規則の計算効率を高めようとした場合に、データによっては単純に並列化すると効率が悪くなってしまうという問題がある。【００１２】
そこで、本発明は、遅延更新規則を用いて並列計算する場合の計算速度を高速化できる並列割当最適化装置、並列割当最適化方法およびコンピュータ読取可能な記録媒体を提供することを目的とする。
【課題を解決するための手段】
【００１３】
本発明による並列割当最適化装置は、並列に行われる処理ごとに割り当てられる対象データ中の要素の候補である並列割当候補を算出する並列割当算出部と、並列割当候補が割り当てられた場合の並列処理に要する計算量を対象データ中の非ゼロ要素数に基づいて推定する並列計算量推定処理部と、算出された計算量に基づいて並列割当候補が最適か否か判定して、並列に行われる処理ごとに最適な要素を割り当てる最適性判定処理部とを備えたことを特徴とする。【００１４】
本発明による並列割当最適化方法は、並列に行われる処理ごとに割り当てられる対象データ中の要素の候補である並列割当候補を算出し、並列割当候補が割り当てられた場合の並列処理に要する計算量を対象データ中の非ゼロ要素数に基づいて推定し、算出された計算量に基づいて並列割当候補が最適か否か判定して、並列に行われる処理ごとに最適な要素を割り当てることを特徴とする。【００１５】
本発明によるコンピュータ読取可能な記録媒体は、コンピュータに、並列に行われる処理ごとに割り当てられる対象データ中の要素の候補である並列割当候補を算出する並列割当算出処理、並列割当候補が割り当てられた場合の並列処理に要する計算量を対象データ中の非ゼロ要素数に基づいて推定する並列計算量推定処理、および、算出された計算量に基づいて並列割当候補が最適か否か判定して、並列に行われる処理ごとに最適な要素を割り当てる最適性判定処理を実行させるための並列割当最適化プログラムを記録したことを特徴とする。
【発明の効果】
【００１６】
本発明によれば、遅延更新規則を用いて並列計算する場合の計算速度を高速化できる。
【図面の簡単な説明】
【００１７】
【図１】本発明による並列割当最適化装置の一実施形態を示すブロック図である。
【図２】本発明による並列割当最適化装置の他の実施形態を示すブロック図である。
【図３】本発明による並列割当最適化装置のさらに他の実施形態を示すブロック図である。
【図４】本実施形態の並列割当最適化装置の動作例を示すフローチャートである。
【図５】本実施形態の並列割当最適化装置の他の動作例を示すフローチャートである。
【図６】並列計算量推定部の動作例を示すフローチャートである。
【図７】本発明による並列割当最適化装置の概要を示すブロック図である。
【図８】並列割当対象のデータ例を示す説明図である。
【発明を実施するための形態】
【００１８】
以下、本発明の実施形態を図面を参照して説明する。上述するように、以下の説明では、並列化の際に割り当てられる領域をチャンクと記す。また、以下の説明では、入力データの属性をＭ個のチャンクに割り当てる状況を例に説明する。また、以下の説明において、並列割当と記した場合、それは、データの属性を割り当てることを意味する。ただし、割り当てる対象は、属性に限られず、データの内容を表す他の要素であってもよい。
【００１９】
実施形態１．
図１は、本発明による並列割当最適化装置の一実施形態を示すブロック図である。本実施形態の並列割当最適化装置１００は、データ入力装置１０１と、並列割当算出部１０２と、並列計算量推定処理部１０３と、最適性判定処理部１０４と、最適並列割当出力装置１０５とを備えている。並列割当最適化装置１００は、入力データ１１１を入力し、最適並列割当結果１１２を出力する。この最適並列割当結果１１２は、遅延更新を利用した並列学習装置２００等により利用される。
【００２０】
また、並列割当最適化装置１００は、現時点で最適な割り当てと判断しているデータおよびその割当による計算量を記憶部（図示せず）に記憶するものとする。
【００２１】
データ入力装置１０１は、多次元の疎な入力データ１１１を入力する装置である。データ入力装置１０１は、並列割当最適化装置１００の処理に必要なパラメータなども併せて入力する。入力データ１１１は、複数の要素により識別されるデータであり、例えば、複数の属性を有するデータである。
【００２２】
並列割当算出部１０２は、並列に行われる処理ごとに割り当てられる対象データ中の要素の候補（以下、並列割当候補と記す。）を算出する。並列割当算出部１０２は、任意の方法を用いて並列割当候補を生成する。
【００２３】
並列割当算出部１０２は、例えば、属性番号に対する順列をランダムに生成し、生成した順列に沿って属性をＭ等分に分割することで、並列割当候補を算出してもよい。分割された属性は、各チャンクに割り当てられる。なお、並列割当候補を算出する他の方法は後述される。
【００２４】
並列計算量推定処理部１０３は、並列割当候補が割り当てられた場合の並列処理に要する計算量（以下、並列化計算量と記すこともある。）を対象データ中の非ゼロ要素数に基づいて推定する。具体的には、並列計算量推定処理部１０３は、「各チャンクにおける非ゼロ要素数」（すなわち、各チャンクに割り当てられたゼロでない属性の数）に基づいて、並列化計算量を算出する。
【００２５】
例えば、図８に例示される行列データが与えられた場合、並列計算量推定処理部１０３は、以下に例示する式１を用いて計算量を算出してもよい。
【００２６】
【数１】
2013179578.tif 000003
【００２７】
上述する式１において、Ｎは、データ数を示し、ｎ＝１，…，Ｎは、データＩＤを示す。また、Ｋｎｍはチャンクｋに割り当てられた次元のデータｎに対する非ゼロ要素数である。
【００２８】
例えば、ｎ番目のデータＸｎ＝（０．５，１．０，０．０，０．０，０．０，０．２）とし、属性１番から３番がチャンク１に割り当てられ、属性４番から６番がチャンク２に割り当てられているとする。この場合、Ｋｎ１＝２，Ｋｎ２＝１になる。
【００２９】
上述する式１は、並列化した遅延更新の各ステップにおいて、各チャンクに割当てられた非ゼロ要素数の最大値を算出し、さらに、全ステップの最大値の和をとった量を算出することを意味する。すなわち、並列計算量推定処理部１０３は、並列に行われる処理ごとに割り当てられた非ゼロ要素数の最大値をその処理ごとに算出し、並列に行われる全処理の最大値の和を並列処理に要する計算量と推定する。
【００３０】
最適性判定処理部１０４は、算出された計算量に基づいて、並列割当候補が最適か否か判定して、並列に行われる処理ごとに最適な要素を割り当てる。具体的には、最適性判定処理部１０４は、並列割当算出部１０２によって算出された並列割当候補のうち、計算量が最小の並列割当候補を最適な要素として割り当てる。
【００３１】
最適性判定処理部１０４は、例えば、記憶部（図示せず）に現在記憶されている最適な並列割当に対して推定された計算量と、並列計算量推定処理部１０３によって計算された並列割当の計算量とを比較し、計算量の小さい方を現在の最適な並列割当として、その計算量とともに記憶部（図示せず）に記憶してもよい。
【００３２】
なお、記憶部（図示せず）に現在記憶されている要素は、並列処理に最適な要素であることから、記憶部に記憶される並列割当が、最適なデータとして割り当てられた要素と言うことができる。
【００３３】
そして、最適性判定処理部１０４は、最適並列割当結果１１２を最適並列割当出力装置１０５に出力させる。最適性判定処理部１０４は、例えば、計算量が所定の値より小さくなった場合に、最適並列割当結果１１２を最適並列割当出力装置１０５に出力させてもよい。なお、計算量が所定の値以上の場合、最適性判定処理部１０４は、並列割当算出部１０２に並列割当候補を再度算出するように指示してもよい。
【００３４】
また、最適性判定処理部１０４は、例えば、並列割当算出部１０２に並列割当候補を算出する指示が所定の回数を超えた場合に、最適並列割当結果１１２を最適並列割当出力装置１０５に出力させてもよい。
【００３５】
ただし、最適並列割当出力装置１０５が最適並列割当結果１１２を出力するタイミングは、上記タイミングに限定されない。他にも、最適性判定処理部１０４は、判定結果に対するユーザの指示に応じて、最適並列割当出力装置１０５に最適並列割当結果１１２を出力させるようにしてもよい。
【００３６】
次に、並列割当算出部１０２が並列割当候補を算出する方法を具体的に説明する。図２は、本発明による並列割当最適化装置の他の実施形態を示すブロック図である。図２に例示する並列割当最適化装置は、図１に例示する並列割当算出部１０２を並列割当算出部１２０に置き換えたものである。なお、図２では、データ入力装置１０１の記載は省略している。
【００３７】
並列割当算出部１２０は、初期化処理部１２１と、属性順序生成処理部１２２と、属性割当計算処理部１２３とを備えている。属性割当計算処理部１２３は、並列計算量推定処理部１０３および最適性判定処理部１０４に接続されている。
【００３８】
初期化処理部１２１は、Ｍ個のチャンクを空の状態に初期化する。
【００３９】
属性順序生成処理部１２２は、属性をチャンクへ割り当てるための属性順序を生成する。属性順序生成処理部１２２は、任意の方法を利用して、属性順序を生成してもよい。属性順序生成処理部１２２は、例えば、ランダムに属性順序を生成する方法、非ゼロ要素数の多い属性から順序をつける方法、非零要素数の少ない属性から順序をつける方法などを利用してもよい。
【００４０】
属性割当計算処理部１２３は、属性の順にしたがって、チャンクへの割当候補を生成する。属性割当計算処理部１２３は、割当候補を一つずつ生成してもよく、複数まとめて生成してもよい。
【００４１】
例えば、属性１から属性ｄ−１までの割当が完了し、属性ｄを割り当てる状況を考える。この場合、チャンク１からチャンクＭまでのどこかに属性ｄが割り当てられるので、割当候補はＭ個生成される。
【００４２】
以降、並列計算量推定処理部１０３は、生成された候補に対して、上述する式１を用いて並列化計算量を算出する。そして、最適性判定処理部１０４は、生成されたＭ個の候補の並列化計算量を比較し、最も計算量が小さい並列割当を最適割当として記憶部（図示せず）に記憶する。そのため、遅延更新規則を用いて並列計算する場合の計算速度を高速化できる。
【００４３】
なお、並列計算量推定処理部１０３が並列化計算量を算出する方法は、上述する式１を用いる方法に限定されない。式１を用いた場合、ｍａｘ演算が必要になる。そこで、より効率的に並列化計算量を算出する方法を以下説明する。図３は、本発明による並列割当最適化装置のさらに他の実施形態を示すブロック図である。
【００４４】
図３に例示する並列割当最適化装置は、図２に例示する並列割当最適化装置の構成に、
計算量最大チャンク位置記憶部１３１と、計算最大量記憶部１３２と、チャンク計算量記憶部１３３とをさらに備えている。すなわち、図３に例示する並列割当最適化装置は、図２に例示する並列計算量推定処理部１０３を並列計算量推定部１３０に置き換えた構成になっている。計算量最大チャンク位置記憶部１３１、計算最大量記憶部１３２およびチャンク計算量記憶部１３３が記憶する情報は、並列計算量推定処理部１０３により更新される。
【００４５】
計算量最大チャンク位置記憶部１３１は、データ数（Ｎ）×チャンク数（Ｍ）の二値行列を記憶する。以下、この行列をＰと記す。行列Ｐのｎｍ要素は、Ｋｎｍ＝ｍａｘ｛Ｋｎ１，…，ＫｎＭ｝の場合１であり、それ以外の場合０である。すなわち、計算量最大チャンク位置記憶部１３１は、対象データｎごとに非ゼロ要素数Ｋｎｍが最も大きいチャンクｍを特定する情報を記憶する。
【００４６】
計算最大量記憶部１３２は、Ｎ次元のベクトルを記憶する。以下、このベクトルをＱと記す。Ｑのｎ要素は、ｍａｘ｛Ｋｎ１，…，ＫｎＭ｝である。すなわち、計算最大量記憶部１３２は、対象データｎ中の要素が割り当てられたチャンクｍのうち、非ゼロ要素数Ｋｎｍが最も大きいチャンクの非ゼロ要素数Ｋｎｍを対象データごとに記憶する。
【００４７】
チャンク計算量記憶部１３３は、データ数（Ｎ）×チャンク数（Ｍ）の二値行列を記憶する。以下、この行列をＫと記す。行列Ｋのｎｍ要素は、チャンクｍに割当てられているデータｎの属性の非ゼロ要素数（Ｋｎｍ）である。すなわち、チャンク計算量記憶部１３３は、各チャンクｍに割り当てられる各対象データｎ中の非ゼロ要素数Ｋｎｍを記憶する。
【００４８】
ここでも、属性１から属性ｄ−１までの割当が完了し、属性ｄを割り当てる状況を考える。すなわち、割当候補がＭ個生成される。ここで、並列割当算出部１２０が属性ｄをチャンクｍに割当てる状況を考える。なお、以下に示す添字（ｄ）は、属性順序にしたがってｄ回目の更新がされたことを表す。
【００４９】
Ｘｎｄ（すなわち、データｎのｄ番目の属性の値）がゼロの場合、すべてのチャンクについてＫｎｍ（ｄ）は変化しない（すなわち、Ｋｎｍ（ｄ）＝Ｋｎｍ（ｄ−１）を満たす）。そのため、計算をスキップする事が可能である。一方、Ｘｎｄが非ゼロの場合、Ｋｎｍ（ｄ）＝Ｋｎｍ（ｄ−１）＋１が成立する。
【００５０】
ここでは、データの要素が「ゼロか非ゼロ」である事が重要である。すなわち、Ｋｎｍ（ｄ−１）＝ｍａｘ｛Ｋｎ１（ｄ−１），…，ＫｎＭ（ｄ−１）｝が成立している場合、Ｋｎｍ（ｄ）＝ｍａｘ｛Ｋｎ１（ｄ），…，ＫｎＭ（ｄ）｝が成立する事が保証される。一方、Ｋｎｍ（ｄ−１）＝ｍａｘ｛Ｋｎ１（ｄ−１），…，ＫｎＭ（ｄ−１）｝が成立していない場合、Ｋｎｍ（ｄ）は、高々ｍａｘ｛Ｋｎ１（ｄ−１），…，ＫｎＭ（ｄ−１）｝である事が保証される。
【００５１】
チャンクｍに割り当てられた属性に対する計算量は、図３に例示する計算量最大チャンク位置記憶部１３１、計算最大量記憶部１３２およびチャンク計算量記憶部１３３に記憶された行列及びベクトルを用いて算出することが可能である。具体的には、並列計算量推定処理部１０３は、行列Ｐのｍ列の要素が１である行のうち、Ｘｎｄが非ゼロである行（すなわち、データＩＤで識別されるデータ）の数をベクトルＱに含まれる各要素の和に加算する事で、チャンクｍに対する計算量を算出可能である。
【００５２】
なお、ｄ番目の属性をｍ番目のチャンクに割当てる事が最適であると判断された場合、並列計算量推定処理部１０３は、Ｐ，Ｑ，Ｋを以下の手順によって更新する。
【００５３】
まず、Ｋｎｍ（ｄ）＝Ｋｎｍ（ｄ−１）＋Ｂ（Ｘｎｄ）に更新する。ただし、Ｂは、引数が非ゼロの場合に１を返し、引数が０の場合に０を返す関数とする。次に、Ｐｎｍ（ｄ−１）＝１の場合、Ｐｎｍ（ｄ）＝１かつＰｎｍ’（ｄ）＝０（ｍ’≠ｍ）かつＱｎ（ｄ）＝Ｑｎ（ｄ−１）＋１に更新する。一方、Ｐｎｍ（ｄ−１）＝０の場合であって、Ｋｎｍ（ｄ−１）＝Ｑｎ（ｄ−１）−１の場合、Ｐｎｍ（ｄ）＝１に更新する。
【００５４】
並列割当算出部１０２と、並列計算量推定処理部１０３と、最適性判定処理部１０４とは、プログラム（並列割当最適化プログラム）に従って動作するコンピュータのＣＰＵによって実現される。例えば、プログラムは、並列割当最適化装置１００の記憶部（図示せず）に記憶され、ＣＰＵは、そのプログラムを読み込み、プログラムに従って、並列割当算出部１０２、並列計算量推定処理部１０３および最適性判定処理部１０４として動作してもよい。また、並列割当算出部１０２と、並列計算量推定処理部１０３と、最適性判定処理部１０４とは、それぞれが専用のハードウェアで実現されていてもよい。
【００５５】
また、並列割当算出部１２０（より詳しくは、初期化処理部１２１と、属性順序生成処理部１２２と、属性割当計算処理部１２３）も、プログラム（並列割当最適化プログラム）に従って動作するコンピュータのＣＰＵによって実現される。また、初期化処理部１２１と、属性順序生成処理部１２２と、属性割当計算処理部１２３とは、それぞれが専用のハードウェアで実現されていてもよい。
【００５６】
また、計算量最大チャンク位置記憶部１３１と、計算最大量記憶部１３２と、チャンク計算量記憶部１３３とは、例えば、磁気ディスク等により実現される。
【００５７】
次に、本実施形態の並列割当最適化装置１００の動作を説明する。図４は、本実施形態の並列割当最適化装置の動作例を示すフローチャートである。
【００５８】
データ入力装置１０１は、入力データ１１１を入力する（ステップＳ１０１）。並列割当算出部１０２は、並列割当候補を算出する（ステップＳ１０２）。並列計算量推定処理部１０３は、算出された並列割当候補に対する計算量を算出する（ステップＳ１０３）。最適性判定処理部１０４は、並列割当候補の最適性を判定し、現在の最適な並列割当を更新する（ステップＳ１０４）。
【００５９】
最適性判定処理部１０４は、並列割当候補をさらに生成するか否かを判定する（ステップＳ１０５）。並列割当候補をさらに生成すると判定した場合（ステップＳ１０５におけるＹｅｓ）、ステップＳ１０２以降の処理が繰り返される。一方、並列割当候補をさらに生成すると判定した場合（ステップＳ１０５におけるＹｅｓ）、最適並列割当出力装置１０５は、最適並列割当結果１１２を出力する（Ｓ１０６）。
【００６０】
図５は、本実施形態の並列割当最適化装置の他の動作例を示すフローチャートである。図５に例示するフローチャートは、図１に例示する並列割当算出部１０２が図２に例示する並列割当算出部１２０に置き換わった場合の動作を示す。
【００６１】
データ入力装置１０１は、入力データ１１１を入力する（ステップＳ２０１）。初期化処理部１２１は、並列化に用いられるチャンクを空に初期化する（ステップＳ２０２）。
属性順序生成処理部１２２は、属性の割当順序を生成する（ステップＳ２０３）。属性割当計算処理部１２３は、生成された属性順序にしたがって並列割当候補を算出する（ステップＳ２０４）。
【００６２】
並列計算量推定処理部１０３は、算出された並列割当候補に対する計算量を算出する（ステップＳ２０５）。最適性判定処理部１０４は、並列割当候補の最適性を判定し、現在の最適な並列割当を更新する（ステップＳ２０６）。
【００６３】
最適性判定処理部１０４は、生成された属性順序にしたがって、全ての属性をチャンクに割当てたか否かを判定する（ステップＳ２０７）。すなわち、最適性判定処理部１０４は、属性順序の探索が終了したか否かを判定する。割当がまだ完了していないと判定された場合（ステップＳ２０７におけるＮｏ）、ステップＳ２０４以降の処理が繰り返される。一方、割当が完了した場合（ステップＳ２０７におけるＹｅｓ）、最適並列割当出力装置１０５は、最適並列割当結果１１２を出力する（Ｓ２０８）。
【００６４】
図６は、並列計算量推定部１３０の動作例を示すフローチャートである。本動作例は、図５におけるステップＳ２０５の動作と置き換え可能である。
【００６５】
並列計算量推定処理部１０３は、計算量最大チャンク位置記憶部１３１、計算最大量記憶部１３２、チャンク計算量記憶部１３３から、それぞれ、行列Ｐ、ベクトルＱ、および行列Ｋを読み込む（ステップＳ３０１）。並列計算量推定処理部１０３は、各割当候補に対する計算量を、Ｐ，Ｑ，Ｋを利用して算出する（ステップＳ３０２）。
【００６６】
並列計算量推定処理部１０３は、並列割当候補の最適性を判定し、現在の最適な並列割当を更新する（ステップＳ３０３）。並列計算量推定処理部１０３は、行列Ｐ、ベクトルＱおよび行列Ｋを更新し、それぞれの値を計算量最大チャンク位置記憶部１３１、計算最大量記憶部１３２、チャンク計算量記憶部１３３へ記憶する。
【００６７】
以上のように、本実施形態によれば、並列割当算出部１０２が、並列に行われる処理ごとに割り当てられる対象データ中の要素の候補（並列割当候補）を対象データ中の非ゼロ要素数に基づいて算出し、並列計算量推定処理部１０３が、並列割当候補が割り当てられた場合の並列処理に要する計算量を推定し、最適性判定処理部１０４が、算出された計算量に基づいて並列割当候補が最適か否か判定して、並列に行われる処理ごとに最適な要素を割り当てる。そのため、遅延更新規則を用いて並列計算する場合の計算速度を高速化できる。
【００６８】
具体的には、並列計算量推定処理部１０３が、上述する式１を用いて、並列に行われる処理ごとに割り当てられた非ゼロ要素数の最大値を処理ごとに算出し、並列に行われる全処理の最大値の和を並列処理に要する計算量と推定する。そして、最適性判定処理部１０４が、算出された並列割当候補のうち、計算量が最小の並列割当候補を最適な要素として割り当てる。
【００６９】
このように、非ゼロ要素数に着目して並列処理に要する計算量を推定することにより各データの要素を割り当てるので、遅延更新規則を用いて並列計算する場合の計算速度を高速化できる。
【実施例】
【００７０】
以下、具体的な実施例により本発明を説明するが、本発明の範囲は以下に説明する内容に限定されない。本実施例では、自動車のセンサデータからの故障診断に本発明の並列割当最適化装置を応用した例を説明する。【００７１】
不具合が発生した自動車からは、多数の電気信号値が取得可能である。この電気信号値は、例えば、制御信号を示しており、バイナリシグナルのため、多くの要素がゼロ要素である。この電気信号値から故障の種類を特定する方法として、例えば、故障の原因がわかっている過去の不具合事例を収集し、判別モデルを学習したうえで、新たに不具合が発生した自動車のデータの原因を予測するという方法が考えられる。判別モデルを学習する際には、多数の自動車から取得された多数の電気信号値を学習する必要があり、計算効率の向上は、重要な課題である。【００７２】
本発明の並列割当最適化装置を利用し、非特許文献１に記載された遅延更新を使った判別モデルの学習規則を並列化すると、上記自動車の故障診断モデル（判別モデル）の学習を高速化する事が可能である。本実施例において、入力データ１１１におけるデータＩＤが過去の不具合事例に対応し、属性ＩＤが電気信号のＩＤに対応する。【００７３】
以下、図２に例示する並列割当最適化装置の構成をもとに、本実施例の動作を説明する。入力データ１１１が、並列化数Ｍを例えば３として、過去の不具合事例データとともに入力される。初期化処理部１２１は、Ｍ＝３として、属性ＩＤのメモリ上の割当領域を空に初期化する。【００７４】
次に、属性順序生成処理部１２２は、ランダムに長さＤ（Ｄは、属性ＩＤの数）の順列を属性順序として生成する。以下、順列の順序を１〜Ｄで表し、電気信号ｄは、その番号に対応する電気信号であるとする。【００７５】
属性割当計算処理部１２３は、生成した順列にしたがって、１〜Ｄに対して一つずつ属性ＩＤをチャンクへ割り当てる。現時点で電気信号ｄ−１までの割当が完了しているとすると、属性割当計算処理部１２３は、属性ｄを３つのチャンクへ割り当てた場合の割当候補を生成する。【００７６】
並列計算量推定処理部１０３は、３つの割当候補に対して、上述する式１を用いて並列化計算量を推定する。そして、最適性判定処理部１０４は、３つの割当候補のうち最も並列化計算量が小さい割当候補を特定する。【００７７】
属性順序にしたがってすべての電気信号ＩＤがチャンクに割り当てられるまで以上の処理が繰り返される。処理完了後、最適並列割当出力装置１０５は、並列割当結果を出力する。【００７８】
例えば、非特許文献１に記載された遅延更新を利用した学習規則へこの並列割当を適用したとする。この場合、各並列チャンク内で割当てられた属性ＩＤに対する更新（具体的には、損失の勾配に対する更新と正則化に関する更新）が行われる。全てのチャンクに対して１ステップ更新処理が行われると、全体の結果を統合してパラメータの更新が行われる。【００７９】
以上の手順により、図８に例示するデータに対して並列化を行った場合の効率が悪くなるという問題が解決される。本実施例の場合では、自動車の故障診断モデルを高速に並列計算する事が可能になる。【００８０】
次に、本発明の概要を説明する。図７は、本発明による並列割当最適化装置の概要を示すブロック図である。本発明による並列割当最適化装置は、並列に行われる処理ごとに割り当てられる対象データ中の要素（例えば、属性）の候補である並列割当候補を算出する並列割当算出部８１（例えば、並列割当算出部１０２）と、並列割当候補が割り当てられた場合の並列処理に要する計算量を対象データ中の非ゼロ要素数に基づいて推定する並列計算量推定処理部８２（例えば、並列計算量推定処理部１０３）と、算出された計算量に基づいて並列割当候補が最適か否か判定して、並列に行われる処理ごとに最適な要素を割り当てる最適性判定処理部８３（例えば、最適性判定処理部１０４）とを備えている。【００８１】
そのような構成により、遅延更新規則を用いて並列計算する場合の計算速度を高速化できる。【００８２】
また、並列計算量推定処理部８２は、並列に行われる処理ごとに割り当てられた非ゼロ要素数の最大値（例えば、Ｋ＊ｎ＝ｍａｘ｛Ｋｎ１，…，Ｋｎｍ｝）を処理ごとに算出し、並列に行われる全処理の最大値の和（例えば、ΣＫ＊ｎ）を並列処理に要する計算量と推定してもよい。そして、最適性判定処理部８３は、算出された並列割当候補のうち、計算量が最小の並列割当候補を最適な要素として割り当ててもよい。【００８３】
また、並列割当算出部８１は、要素の割り当てに用いられる属性順序を生成し、その属性順序に則して各要素をチャンクに割り当てることで並列割当候補を算出してもよい。また、並列計算量推定処理部８２は、属性順序に則して要素をチャンクに割り当てた場合における計算量をチャンクごとに推定してもよい。そして、最適性判定処理部８３は、計算量が最小になるチャンクに要素を割り当ててもよい。【００８４】
また、並列割当最適化装置は、対象データ（例えば、ｎ）中の要素が割り当てられたチャンクのうち、非ゼロ要素数（例えば、Ｋｎｍ）が最も大きいチャンクにおける非ゼロ要素数を対象データごとに記憶する（例えば、ベクトルＱを記憶する）計算最大量記憶部（例えば、計算最大量記憶部１３２）と、対象データごとに非ゼロ要素数が最も大きいチャンクを特定する情報（例えば、１／０で識別される情報）を記憶する（例えば、行列Ｐを記憶する）計算量最大チャンク位置記憶部（例えば、計算量最大チャンク位置記憶部１３１）とを備えていてもよい。そして、並列計算量推定処理部８２は、計算量最大チャンク位置記憶部に記憶された情報に基づいて特定される非ゼロ要素数が最も大きいチャンクに対して非ゼロ要素が割り当てられた対象データ数を、計算最大量記憶部に記憶された非ゼロ要素数の合計に加算することにより計算量を算出してもよい。【００８５】
また、並列割当最適化装置は、各チャンク（例えば、ｍ）に割り当てられる各対象データ（例えば、ｎ）中の非ゼロ要素数（例えば、Ｋｎｍ）を記憶する（例えば、行列Ｋを記憶する）チャンク計算量記憶部（例えば、チャンク計算量記憶部１３３）を備えていてもよい。【００８６】
そして、並列計算量推定処理部８２は、チャンク計算量記憶部に記憶された各対象データ中の非ゼロ要素数に対して新たに割り当てられた非ゼロ要素数を加算（例えば、Ｋｎｍ（ｄ）＝Ｋｎｍ（ｄ−１）＋Ｂ（Ｘｎｄ））して更新してもよい。【００８７】
また、並列計算量推定処理部８２は、非ゼロ要素数が最も大きいチャンクに対して非ゼロ要素が割り当てられた場合（例えば、Ｐｎｍ（ｄ−１）＝１）には、計算量最大チャンク位置記憶部が記憶する情報を、チャンクが非ゼロ要素数が最も大きいチャンクと特定できる情報に更新（例えば、Ｐｎｍ（ｄ）＝１かつＰｎｍ’（ｄ）＝０（ｍ’≠ｍ））し、かつ、計算最大量記憶部が記憶する対象データの非ゼロ要素数に１加算（例えば、Ｑｎ（ｄ）＝Ｑｎ（ｄ−１）＋１）し、非ゼロ要素数が最も大きいチャンクに対して非ゼロ要素が割り当てられなかった場合（例えば、Ｐｎｍ（ｄ−１）＝０）かつ計算最大量記憶部が記憶する対象データの非ゼロ要素数に１加算した値とチャンク計算量記憶部に記憶された対象データ中の非ゼロ要素数とが等しくなった場合（例えば、Ｋｎｍ（ｄ−１）＝Ｑｎ（ｄ−１）−１）には、計算量最大チャンク位置記憶部が記憶する情報を、割り当てられたチャンクが非ゼロ要素数が最も大きいチャンクと特定できる情報（例えば、Ｐｎｍ（ｄ）＝１）に更新してもよい。【００８８】
上記の実施形態の一部又は全部は、以下の付記のようにも記載されうるが、以下には限られない。【００８９】
（付記１）コンピュータに、並列に行われる処理ごとに割り当てられる対象データ中の要素の候補である並列割当候補を算出する並列割当算出処理、並列割当候補が割り当てられた場合の並列処理に要する計算量を対象データ中の非ゼロ要素数に基づいて推定する並列計算量推定処理、および、算出された計算量に基づいて並列割当候補が最適か否か判定して、並列に行われる処理ごとに最適な要素を割り当てる最適性判定処理を実行させるための並列割当最適化プログラム。【００９０】
（付記２）コンピュータに、並列計算量推定処理で、並列に行われる処理ごとに割り当てられた非ゼロ要素数の最大値を当該処理ごとに算出させ、並列に行われる全処理の最大値の和を並列処理に要する計算量と推定させ、最適性判定処理で、算出された並列割当候補のうち、計算量が最小の並列割当候補を最適な要素として割り当てさせる付記１記載の並列割当最適化プログラム。【００９１】
以上、実施形態及び実施例を参照して本願発明を説明したが、本願発明は上記実施形態および実施例に限定されるものではない。本願発明の構成や詳細には、本願発明のスコープ内で当業者が理解し得る様々な変更をすることができる。【００９２】
この出願は、２０１２年５月３１日に出願された米国仮出願６１／６５３６２９を基礎とする優先権を主張し、その開示の全てをここに取り込む。
【産業上の利用可能性】
【００９３】
本発明は、各並列処理に割り当てるデータを最適化する並列割当最適化装置に好適に適用される。
【符号の説明】
【００９４】
１００，１２０  並列割当最適化装置
１０１  データ入力装置
１０２  並列割当算出部
１０３  並列計算量推定処理部
１０４  最適性判定処理部
１０５  最適並列割当出力装置
１２１  初期化処理部
１２２  属性順順序生成処理部
１２３  属性割当計算処理部
１３０  並列計算量推定部
１３１  計算量最大チャンク位置記憶部
１３２  計算最大量記憶部
１３３  チャンク計算量記憶部
【図１】
2013179578.tif 000004
【図２】
2013179578.tif 000005
【図３】
2013179578.tif 000006
【図４】
2013179578.tif 000007
【図５】
2013179578.tif 000008
【図６】
2013179578.tif 000009
【図７】
2013179578.tif 000010
【図８】
2013179578.tif 000011
【手続補正書】
【提出日】平成26年4月30日(2014.4.30)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】請求項８
【補正方法】変更
【補正の内容】
【請求項８】
コンピュータに、
並列に行われる処理ごとに割り当てられる対象データ中の要素の候補である並列割当候補を算出する並列割当算出処理、
前記並列割当候補が割り当てられた場合の並列処理に要する計算量を対象データ中の非ゼロ要素数に基づいて推定する並列計算量推定処理、および、
算出された計算量に基づいて前記並列割当候補が最適か否か判定して、並列に行われる処理ごとに最適な要素を割り当てる最適性判定処理
を実行させるための並列割当最適化プログラム。
【手続補正２】
【補正対象書類名】特許請求の範囲
【補正対象項目名】請求項９
【補正方法】変更
【補正の内容】
【請求項９】
コンピュータに、
並列計算量推定処理で、並列に行われる処理ごとに割り当てられた非ゼロ要素数の最大値を当該処理ごとに算出させ、並列に行われる全処理の最大値の和を並列処理に要する計算量と推定させ、
最適性判定処理で、算出された並列割当候補のうち、前記計算量が最小の並列割当候補を最適な要素として割り当てさせる
請求項８記載の並列割当最適化プログラム。
【手続補正４】
【補正対象書類名】明細書
【補正対象項目名】００１５
【補正方法】変更
【補正の内容】
【００１５】
本発明による並列割当最適化プログラムは、コンピュータに、並列に行われる処理ごとに割り当てられる対象データ中の要素の候補である並列割当候補を算出する並列割当算出処理、並列割当候補が割り当てられた場合の並列処理に要する計算量を対象データ中の非ゼロ要素数に基づいて推定する並列計算量推定処理、および、算出された計算量に基づいて並列割当候補が最適か否か判定して、並列に行われる処理ごとに最適な要素を割り当てる最適性判定処理を実行させることを特徴とする。
【国際調査報告】
2013179578.tif 000012
2013179578.tif 000013