(57)【要約】  行列情報に関する処理に要する記憶領域を、記憶容量に関して効率よく確保することが可能な領域確保装置等を提供する。領域確保装置２２０１は、行及び列により２次元に配置された配列情報のうちの該行または該列の一方を表す第１配列と他方を表す第２配列とに関して、少なくとも一部の該第１配列における情報を含む部分配列情報において、該第２配列に配列された要素に格納されている値のうち、少なくとも１つの値が所定の値とは異なる対象配列を表す配列識別子を特定する配列特定部２２０２と、配列特定部２２０２が特定した該配列識別子の個数を算出し、算出した該個数に応じた記憶容量を有する記憶領域を確保する領域確保部２２０３とを有する。
2018070376.tif 000002
【特許請求の範囲】
【請求項１】
行及び列により２次元に配置された配列情報のうちの前記行または前記列の一方を表す第１配列と他方を表す第２配列とに関して、少なくとも一部の前記第１配列における情報を含む部分配列情報において、前記第２配列に配列された要素に格納されている値のうち、少なくとも１つの値が所定の値とは異なる対象配列を表す配列識別子を特定する配列特定手段と、
前記配列特定手段が特定した前記配列識別子の個数を算出し、算出した前記個数に応じた記憶容量を有する記憶領域を確保する領域確保手段と
を備える領域確保装置。
【請求項２】
前記部分配列情報に対して、前記部分配列情報に関する処理を実行する処理装置を割り当てる割り当て手段
をさらに備える請求項１に記載の領域確保装置。
【請求項３】
前記部分配列情報のうち、前記配列特定手段が特定した前記配列識別子が表す配列に含まれている要素を含む小配列情報を作成する行列変換手段
をさらに備える請求項２に記載の領域確保装置。
【請求項４】
前記行列変換手段は、前記配列情報における前記第２配列を表す配列識別子と、当該第２配列が前記対象配列である場合に前記小配列情報において格納される第２配列を表す配列識別子とが関連付けされた変換情報を作成する
請求項３に記載の領域確保装置。
【請求項５】
前記配列特定手段は、前記部分配列情報における複数の第１配列を含むバッチ情報に関して、前記配列識別子を特定し、
前記領域確保手段は、前記バッチ情報に関して前記個数を算出し、算出した該個数に応じて、前記記憶容量を有する記憶領域を確保する
請求項１、または、請求項２に記載の領域確保装置。
【請求項６】
前記割り当て手段は、前記部分配列情報に関して算出された値を集計する処理を、ある処理装置に割り当てる
請求項２乃至請求項４のいずれかに記載の領域確保装置。
【請求項７】
前記変換情報に基づき、前記小配列情報に含まれている第２配列の第２個数を算出し、前記部分配列情報に関して算出された値を集計する処理に関して、前記第２個数が少ない前記小配列情報に関する処理を実行する前記処理装置から、前記第２個数が多い前記小配列情報に関する処理を実行する前記処理装置に送信するよう通信順序を決定する決定手段
をさらに備える請求項４に記載の領域確保装置。
【請求項８】
前記第２配列に関して、前記第２配列を表す前記配列識別子を含む前記変換情報の第３個数を算出し、前記第２配列を、算出した該第３個数の総計が均等、または、略均等である複数のグループに分類し、前記グループに対して、前記部分配列情報に関して算出された値を集計する処理装置を決定する決定手段
をさらに備える請求項４に記載の領域確保装置。
【請求項９】
情報処理装置によって、行及び列により２次元に配置された配列情報のうちの前記行または前記列の一方を表す第１配列と他方を表す第２配列とに関して、少なくとも一部の前記第１配列における情報を含む部分配列情報において、前記第２配列に配列された要素に格納されている値のうち、少なくとも１つの値が所定の値とは異なる対象配列を表す配列識別子を特定し、特定された前記配列識別子の個数を算出し、算出した前記個数に応じた記憶容量を有する記憶領域を確保する領域確保方法。
【請求項１０】
行及び列により２次元に配置された配列情報のうちの前記行または前記列の一方を表す第１配列と他方を表す第２配列とに関して、少なくとも一部の前記第１配列における情報を含む部分配列情報において、前記第２配列に配列された要素に格納されている値のうち、少なくとも１つの値が所定の値とは異なる対象配列を表す配列識別子を特定する配列特定機能と、
特定された前記配列識別子の個数を算出し、算出した前記個数に応じた記憶容量を有する記憶領域を確保する領域確保機能と
をコンピュータに実現させる領域確保プログラムが記録された記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、行列に関する演算処理に必要な記憶領域を確保する領域確保装置等に関する。
【背景技術】
【０００２】
ビッグデータ分析において、大規模なデータを対象として機械学習が行われる場合が増えている。たとえば、非特許文献１には、大規模な機械学習を並列処理によって実行する方法の一例が記載されている。【０００３】
非特許文献１に示された並列処理手法に従えば、各処理装置は、独立に処理を行った演算結果に対して、「Ａｌｌ  Ｒｅｄｕｃｅ」（他の処理装置に格納されているデータを参照しながら演算処理を実行し、各処理装置が同じ演算結果を算出する方法）と呼ばれる機能を用いて、該演算結果を集計する。【０００４】
「Ａｌｌ  Ｒｅｄｕｃｅ」機能は、たとえば、あるグループ内のすべての処理装置のデータを加算し、その結果を、該あるグループ内のすべての処理装置が共有する機能である。【０００５】
特許文献１は、サービスにおけるアイテムを、該サービスのユーザに推奨する推奨システムを開示している。該推奨システムは、サービスにおけるアイテムを利用したユーザが該アイテムに対して行なった評価の履歴に基づき、サービスにおけるアイテムの中から、該サービスのユーザに対して推奨するアイテムを選択する。【０００６】
特許文献２は、２つのベクトルに対する演算を実行するベクトル演算装置を開示している。該ベクトル演算装置は、一方のベクトルを疎ベクトル形式に従ったデータ構造を有する第１ベクトルに変換し、他方のベクトルを密ベクトル形式に従ったデータ構造を有する第２ベクトルに変換する。該ベクトル演算装置は、該第１ベクトルと、該第２ベクトルとに対して演算処理を実行する。ここで、該疎ベクトル形式は、非ゼロの値である要素のみが格納されるデータ形式を表す。該密ベクトル形式は、すべての要素が格納されるデータ形式を表す。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】特開２０１４−２２８９８４号公報
【特許文献２】特開２０１４−００２４８４号公報
【非特許文献】
【０００８】
【非特許文献１】Ａｌｅｋｈ  Ａｇａｒｗａｌ，  ｅｔ  ａｌ．  Ａ  Ｒｅｌｉａｂｌｅ  Ｅｆｆｅｃｔｉｖｅ  Ｔｅｒａｓｃａｌｅ  Ｌｉｎｅａｒ  Ｌｅａｒｎｉｎｇ  Ｓｙｓｔｅｍ，  Ｊｏｕｒｎａｌ  ｏｆ  Ｍａｃｈｉｎｅ  Ｌｅａｒｎｉｎｇ  Ｒｅｓｅａｒｃｈ  １５  （２０１４）  ＰＰ．１１１１−１１３３
【発明の概要】
【発明が解決しようとする課題】
【０００９】
しかし、特許文献１、または、特許文献２に開示されたいずれの装置を用いたとしても、行列に関する処理に要する記憶容量を、効率よく確保することはできない。この理由は、特許文献１乃至特許文献２に開示された方法に従ったとしても、機械学習における処理にて出現する行列情報に関して効率的に並列処理できるとは限らないからである。詳細な理由については、図２５を参照しながら実施形態にて後述する。【００１０】
そこで、本発明の目的の１つは、行列情報に関する処理に要する記憶領域を、記憶容量に関して効率よく確保することが可能な領域確保装置等を提供することである。
【課題を解決するための手段】
【００１１】
本発明の１つの態様として、領域確保装置は、
行及び列により２次元に配置された配列情報のうちの前記行または前記列の一方を表す第１配列と他方を表す第２配列とに関して、少なくとも一部の前記第１配列における情報を含む部分配列情報において、前記第２配列に配列された要素に格納されている値のうち、少なくとも１つの値が所定の値とは異なる対象配列を表す列識別子を特定する配列特定手段と、
前記配列特定手段が特定した前記列識別子の個数を算出し、算出した前記個数に応じた記憶容量を有する記憶領域を確保する領域確保手段と
を備える。【００１２】
また、本発明の他の態様として、領域確保方法は、
情報処理装置によって、行及び列により２次元に配置された配列情報のうちの前記行または前記列の一方を表す第１配列と他方を表す第２配列とに関して、少なくとも一部の前記第１配列における情報を含む部分配列情報において、前記第２配列に配列された要素に格納されている値のうち、少なくとも１つの値が所定の値とは異なる対象配列を表す列識別子を特定し、特定された前記列識別子の個数を算出し、算出した前記個数に応じた記憶容量を有する記憶領域を確保する。【００１３】
また、本発明の他の態様として、領域確保プログラムは、
行及び列により２次元に配置された配列情報のうちの前記行または前記列の一方を表す第１配列と他方を表す第２配列とに関して、少なくとも一部の前記第１配列における情報を含む部分配列情報において、前記第２配列に配列された要素に格納されている値のうち、少なくとも１つの値が所定の値とは異なる対象配列を表す列識別子を特定する配列特定機能と、
特定された前記列識別子の個数を算出し、算出した前記個数に応じた記憶容量を有する記憶領域を確保する領域確保機能と
をコンピュータに実現させる。【００１４】
さらに、同目的は、係るプログラムを記録するコンピュータが読み取り可能な記録媒体によっても実現される。
【発明の効果】
【００１５】
本発明に係る領域確保装置等によれば、行列情報に関する処理に要する記憶領域を、記憶容量に関して効率よく確保することができる。
【図面の簡単な説明】
【００１６】
【図１】本発明の第１の実施形態に係る情報処理システムが有する構成を示すブロック図である。
【図２】第１の実施形態に係る情報処理システムにおける処理の流れを示すシーケンス図である。
【図３】行列情報の一例を概念的に表す図である。
【図４】行列変換部における処理の一例を概念的に表す図である。
【図５】集約部における処理を概念的に表す図である。
【図６】モデル変換部における処理を概念的に表す図である。
【図７】ミニバッチ単位にて処理される部分行列情報を概念的に表す図である。
【図８】行列情報（または、部分行列情報、小行列情報）に関して実行される処理を概念的に表す図である。
【図９】本発明の第２の実施形態に係る情報処理システムが有する構成を表すブロック図である。
【図１０】第２の実施形態に係る情報処理システム９０１における処理の流れを示すフローチャートである。
【図１１】ツリー構造に従い通信しながら全体モデル情報を作成する処理を概念的に表す図である。
【図１２】ツリー構造に従い通信しながら全体モデル情報を作成する処理を概念的に表す図である。
【図１３】情報処理システムにおける処理を概念的に表す図である。
【図１４】情報処理システムにおける処理を概念的に表す図である。
【図１５】情報処理システムにおける処理を概念的に表す図である。
【図１６】本発明の第３の実施形態に係る情報処理システムが有する構成を示すブロック図である。
【図１７】情報処理システムにおける処理の流れを示すフローチャートである。
【図１８】全体モデル情報が各処理装置にて並列処理される場合に実行される処理を概念的に表す図である。
【図１９】処理装置の台数に基づき集約処理を処理装置に割り当てる処理の一例を概念的に表す図である。
【図２０】情報処理システムにおける処理を概念的に表す図である。
【図２１】情報処理システムにおける処理を概念的に表す図である。
【図２２】本発明の第４の実施形態に係る領域確保装置が有する構成を示すブロック図である。
【図２３】第４の実施形態に係る領域確保装置における処理の流れを示すフローチャートである。
【図２４】第１の実施形態乃至第３の実施形態に係る情報処理システム、または、第４の実施形態に係る領域確保装置を実現可能な計算処理装置のハードウェア構成例を概略的に示すブロック図である。
【図２５】学習情報の一例を概念的に表す図である。
【発明を実施するための形態】
【００１７】
まず、本願発明の理解を容易にするため、本発明が解決しようとする課題を詳細に説明する。
【００１８】
機械学習において学習する対象である学習情報は、通常、大規模な情報であり、行列情報を用いて表わされる。図２５を参照しながら、機械学習において学習対象である学習情報の一例について説明する。図２５は、学習情報の一例を概念的に表す図である。
【００１９】
学習情報は、たとえば、あるサイトのユーザが、該あるサイトに表示された広告をクリックしたか否かを表す情報である。図２５に例示された学習情報においては、列方向にサイト名を表し、行方向に広告名を表す。サイト名が表すサイトが、広告名が表す広告を表示し、ユーザによって該サイトにて該広告がクリックされたことがある場合に、学習情報においては、該サイト名が表す列、及び、該広告名が表す行によって決まる要素の値に所定の値（たとえば、０（ゼロ）、空値）とは異なる値（たとえば、１）が設定される。また、ユーザによって該サイトにて該広告がクリックされたことがない場合に、学習情報においては、該サイト名が表す列、及び、該広告名が表す行によって決まる要素の値に所定の値（たとえば、０（ゼロ）、空値）が設定される。図２５においては、空値を用いて所定の値が表されている。また、図２５に例示された学習情報は、たとえば、「Ｏｎｅ  Ｈｏｔ  Ｅｎｃｏｄｉｎｇ」とも呼ばれる方法に従い作成される。
【００２０】
以降、説明の便宜上、所定の値が０（ゼロ）、所定の値と異なる値が１であるとして説明する。しかし、これらの値は、０、及び、１に限定されない。また、所定の値が格納されている要素を「ゼロ要素」と表す。所定の値と異なる値が格納されている要素を「非ゼロ要素」と表す。
【００２１】
学習情報が「Ｏｎｅ  Ｈｏｔ  Ｅｎｃｏｄｉｎｇ」に従い作成されている場合に、該学習情報は、値が０である要素の個数に比べ、値が１である要素の個数が極めて少ないので、疎行列とも呼ばれる。クリックスルー率を算出する基となるモデル情報を最適化する場合には、たとえば、ロジスティック回帰法等の所定の算出手順に従い、モデル情報を構成しているパラメタの値を図２５に例示された学習情報に基づき最適化する。
【００２２】
最適化されたモデル情報は、該モデル情報を構成しているパラメタの値を含む数値列（ベクトル）を用いて表すことができる。この場合に、該ベクトルは、該モデル情報を構成している該パラメタの値が、すべて格納されている密ベクトル（または、密行列）であってもよい。該ベクトルに含まれる要素の個数は、たとえば、学習情報に含まれている非ゼロ要素の個数に応じて決まる。学習情報に基づき作成されるモデル情報は、たとえば、学習情報に含まれている列数分の要素を含むベクトルを用いて表わされる。したがって、学習情報に含まれている列数が増えるにつれ、該学習情報に基づき作成されるモデル情報における要素数は多い。
【００２３】
複数の情報処理装置を有する情報処理システムにて所定の算出手順を並列処理する場合に、図３（第１の実施形態にて後述する）に例示されているように学習情報（行列情報）を分割し、分割された学習情報（図３における部分行列情報）が各情報処理装置に割り当てられる（配置される）。
【００２４】
以降、説明の便宜上、情報処理装置を、単に、「処理装置」と表す。
【００２５】
各処理装置は、所定の算出手順に従い、該分割された学習情報を用いて、該分割された学習情報に関するモデル情報（説明の便宜上、「部分モデル情報」（図５に例示）と表す）を作成する。モデル情報を作成する処理において、各処理装置は、「Ａｌｌ  Ｒｅｄｕｃｅ」機能を用いて、作成したモデル情報を構成しているパラメタの値（すなわち、各処理装置に分散配置されているパラメタの値）に基づき、全体の学習情報に関して最適化されたモデル情報（説明の便宜上、「全体モデル情報」（図５に例示）と表す）を作成する。この結果、各処理装置には、全体の学習情報に関して最適化されたモデル情報が格納される。この場合に、各処理装置は、「Ａｌｌ  Ｒｅｄｕｃｅ」機能に従った処理において、該モデル情報を構成しているパラメタの値を相互に通信する。したがって、学習情報に含まれている列数が増えるにつれモデル情報を構成しているパラメタの個数が増えるので、「Ａｌｌ  Ｒｅｄｕｃｅ」機能における通信時間が長くなる。
【００２６】
本願発明者は、数値シミュレーション等で用いられている並列処理手法を、上述したような処理手順に従った処理に適用したとしても、必ずしも、高効率な並列処理になるとは限らないという課題を見出した。このような課題について説明する。
【００２７】
たとえば、数値シミュレーションにおいて、行列に含まれている非ゼロ要素は、該非ゼロ要素が位置している縦方向に対応している列に割り当てられている情報、及び、該非ゼロ要素が位置している横方向に対応している行に割り当てられている情報が相互に関連していることを表す。たとえば、第Ｉ（ただし、Ｉは自然数）行に割り当てられている情報と、第Ｉ列に割り当てられている情報とは同じパラメタに関する情報を表す。したがって、数値シミュレーションにおいて、該行列の行を並べ替えた場合に、行及び列に割り当てられている情報の整合性を保つために、列を適切に並び替える必要がある。
【００２８】
行列に関する処理（たとえば、行列と配列（ベクトル）との行列ベクトル積）を並列に処理する場合には、たとえば、あらかじめ、行ごとに処理を実行する処理装置が決定される。この場合に、各処理装置は、自装置に割り当てられた行に関する演算処理を実行する。各処理装置は、元々の行列（すなわち、全体の行列）に含まれている非ゼロ列の列数に基づき、自装置に該行列を格納するための記憶領域を確保する必要がある。したがって、各処理装置における記憶容量は、元々の行列に含まれている非ゼロ列の列数に応じて決定される。
【００２９】
これに対して、上述したような学習処理に出現する行列に含まれている非ゼロ要素は、該非ゼロ要素が位置している縦方向に対応している列に割り当てられている情報、及び、該非ゼロ要素が位置している横方向に対応している行に割り当てられている情報に関連がない。たとえば、第Ｉ（ただし、Ｉは自然数）行に割り当てられている情報と、第Ｉ列に割り当てられている情報とは、図２５に例示したように、一般的に異なっている。したがって、学習処理において出現する行列に関しては、該行列における行を並び替えた場合であっても、行及び列に割り当てられている情報の整合性を保つために、列を並び替える必要はない。同様に、該行列における列を並び替えた場合であっても行を並び替える必要はない。この結果、元々の行列に含まれている非ゼロ列の列数ではなく、各処理装置に割り当てられた行列（部分行列）に含まれている非ゼロ列の列数に基づき、記憶容量を決めることができる。
【００３０】
学習処理に対して、数値シミュレーションにおいて用いられる並列処理手法を適用した場合には、要素（たとえば、モデル情報を構成しているパラメタ）の値を算出する処理において多くの通信が必要である。本願発明者は、このような考察に基づき、上述したような課題を見出すとともに、係る課題を解決する手段を導出するに至った。以降、このような課題を解決可能な、本発明を実施する実施形態について、図面を参照しながら説明する。
【００３１】
＜第１の実施形態＞
図１を参照しながら、本発明の第１の実施形態に係る情報処理システム１０１が有する構成について詳細に説明する。図１は、本発明の第１の実施形態に係る情報処理システム１０１が有する構成を示すブロック図である。
【００３２】
第１の実施形態に係る情報処理システム１０１は、ワーカー処理装置１０２と、マスター処理装置１０３とを有する。ワーカー処理装置１０２は、行列変換部１０４と、処理部１０５とを有する。マスター処理装置１０３は、集約部１０６と、モデル変換部１０７とを有する。情報処理システム１０１において、マスター処理装置１０３の台数は、たとえば、１台であり、ワーカー処理装置１０２の台数は、たとえば、少なくとも１台である。マスター処理装置１０３は、ワーカー処理装置１０２が有している機能を有していてもよい。
【００３３】
行列変換部１０４は、たとえば、部分行列情報（図３を参照しながら後述する）を入力し、入力した情報を変換することによって、変換情報（図４を参照しながら後述する）と、小行列情報（図４を参照しながら後述する）とを作成する。行列変換部１０４は、作成した変換情報を、マスター処理装置１０３に送信し、さらに、作成した小行列情報を処理部１０５に対して出力する。
【００３４】
処理部１０５は、行列変換部１０４が作成した小行列情報と、この段落にて後述するようなモデル情報（以降、「入力モデル情報」と表す）とを入力し、入力した小行列情報（図４に例示）とモデル情報とに対して、所定の算出手順に従った処理を実行することによって、処理結果モデル（以降、「出力モデル情報」（たとえば、図５における部分モデル情報）と表す）を作成する。処理部１０５は、作成した出力モデル情報をマスター処理装置１０３に送信する。出力モデル情報は、小行列情報（または、行列情報）における行に含まれている値と、予測対象である値との関連性を表すモデル情報である。入力モデル情報は、該出力モデル情報を算出する基である情報である。出力モデル情報は、たとえば、所定の算出手順（たとえば、最小二乗法、ロジスティック回帰法）に従い、入力モデル情報に含まれているパラメタの値を決定することによって作成される。ただし、所定の算出手順は、上述した手法に限定されない。まとめると、モデル情報は、入力と予測対象である値との関連性が、パラメタを用いて表現された情報である。処理部１０５は、入力した小行列情報に基づき、入力モデル情報に含まれているパラメタを所定の算出手順に従い決定することによって、出力モデル情報（たとえば、図５における部分モデル情報）を作成する。
【００３５】
所定の算出手順が線形回帰モデルを算出手順である場合に、部分モデル情報は、たとえば、各パラメタの係数を算出する際の、部分行列情報に関する部分的な算出結果を表す。たとえば、該パラメタの値が行列情報（図３に例示）に含まれている複数の要素の総和によって算出される場合に、部分モデル情報におけるパラメタは、部分行列情報（図３に例示）に含まれている要素の総和を表す。
【００３６】
マスター処理装置１０３において、集約部１０６は、ワーカー処理装置１０２が送信した変換情報と、部分モデル情報とを受信し、受信した該部分モデル情報を該変換情報に従い集約することによって、行列情報（図３に例示）に関する全体モデル情報（図５に例示）を作成する。この場合に、全体モデル情報（図５に例示）においては、行列情報（図３に例示）に基づき、モデル情報に含まれているパラメタが所定の算出手順に従い最適化されている。
【００３７】
次に、図３を参照しながら、学習情報の一例である行列情報について説明する。図３は、行列情報の一例を概念的に表す図である。行列情報は、たとえば、図２５を参照しながら説明したような学習情報である。図３に示された例において、「△」は、所定の値と異なる値（たとえば、０以外の数値）を表している。行列情報における空値は、所定の値（たとえば、０）を表している。図３においては、理解を助けるため、行列情報、及び、部分行列情報においては、すべての値を含めて表示しているが、図４等を参照しながら説明するように、必ずしも、所定の値が該行列情報に格納されている必要はない。
【００３８】
説明の便宜上、情報処理システム１０１において処理される対象である行列情報において、各行に割り当てられている情報は、一つの対象（Ｉｎｓｔａｎｃｅ）に関する学習情報（図２５に例示）を表しているとする。該行列情報において、各列に割り当てられている情報は、該対象に関する特徴（Ｆｅａｔｕｒｅ）を表すパラメタ（すなわち、モデル情報を構成しているパラメタ）の値を表しているとする。行列情報は、上述した例に限定されない。たとえば、各列に割り当てられている情報は、一つの対象に関する学習情報（図２５に例示）を表してもよい。該行列情報において、各行に割り当てられている情報は、該対象に関する特徴を表すパラメタ（すなわち、モデル情報を構成しているパラメタ）の値を表してもよい。
【００３９】
行列情報（図３に例示）は、横（行）方向に分割され、分割された行列情報（たとえば、図３における部分行列情報）に対して、図２を参照しながら後述するような処理が実行される。ここで、横（行）方向に分割された各行列情報を、「部分行列情報」と表す。所定の算出手順を並列処理する場合に、たとえば、該部分行列情報ごとに、各処理装置に処理が割り当てられる。たとえば、図３に示された例においては、行列情報は、該行列情報における第１行、及び、第２行における要素の値が格納された部分行列情報（図３の左側）と、該行列情報における第３行、及び、第４行における要素の値が格納された部分行列情報（図３の右側）とに分割される。
【００４０】
所定の処理手順に従い部分行列情報に関するモデル情報（図５に例示された部分モデル情報）が作成される場合に、作成されるモデル情報を構成しているパラメタの値は、該部分行列情報（図３に例示）における列に含まれている値に基づき決定される。たとえば、図３におけるモデル情報に例示するように、該列が少なくとも１つの非ゼロ要素を含んでいる場合に、該列に関するパラメタの値は非ゼロである可能性が高い。しかし、該列が非ゼロ要素を含んでいない場合に、該列に関するパラメタの値はゼロである。
【００４１】
以降の説明においては、所定の値（ゼロ、空値等）とは異なる値を有する要素を少なくとも１個含む列を「対象列」（ｔａｒｇｅｔ  ｃｏｌｕｍｎ）と表すとする。特に、所定の値がゼロある場合に、ゼロとは異なる値（すなわち、非ゼロ、ｎｏｎ−ｚｅｒｏ）を有する要素を少なくとも１個含む列を「非ゼロ列」（ｎｏｎ−ｚｅｒｏ  ｃｏｌｕｍｎ）と表すとする。したがって、非ゼロ列は、対象列の一例である。
【００４２】
図３に示された行列情報において非ゼロ列である列であっても、該行列情報に関する部分行列情報においては、該部分行列情報における列に含まれる要素の値がすべてゼロである場合がある。この結果、該部分行列情報に基づき算出されるモデル情報は、該部分行列情報に含まれている非ゼロ列の個数分の非ゼロであるパラメタを含む。所定の算出手順に従った処理を並列処理する場合には、たとえば、非ゼロである値のみが通信されるので、非ゼロであるパラメタの個数を減らすことによって通信量を低減することができる。
【００４３】
以降、説明の便宜上、部分行列情報に基づき作成されるモデル情報を「部分モデル情報」と表す。また、行列情報に基づき作成されるモデル情報を「全体モデル情報」と表す。
【００４４】
図４を参照しながら、行列変換部１０４における処理について説明する。図４は、行列変換部１０４における処理の一例を概念的に表す図である。図４に示された例において、「Ａ」乃至「Ｄ」は、所定の値と異なる値を表している。部分行列情報（または、小行列情報）における空値は、所定の値（たとえば、０）を表している。図４においては、理解を助けるため、部分行列情報（または、小行列情報）がすべての値（すなわち、「Ａ」乃至「Ｄ」と、空値）を格納する記憶領域を含む態様にて表示しているが、必ずしも、所定の値が格納される記憶領域を該部分行列情報（または、小行列情報）が含む必要はない。また、図４に例示された部分行列情報においては、説明の便宜上、行識別子、及び、列識別子の値が示されているが、必ずしも、該部分行列情報が、行識別子、または、列識別子を含んでいるわけではない。
【００４５】
行列変換部１０４は、部分行列情報を入力し、入力した該部分行列情報のうち非ゼロ列を表す列識別子を特定する。行列変換部１０４は、図４に示された部分行列情報に関して、たとえば、１、４、及び、６として算出する。行列変換部１０４は、特定した該列識別子を含む変換情報と、該非ゼロ列に含まれている要素を含む小行列情報とを作成する。すなわち、該変換情報は、該部分行列情報における非ゼロ列を表す列識別子と、該小行列情報における列識別子とが関連付けされた情報である。該変換情報においては、たとえば、部分行列情報における第４列と、該小行列情報における第２列とが関連付けされている。行列変換部１０４は、非ゼロ列（すなわち、対象列）に着目することによって変換情報を作成したが、値がゼロである要素のみを含む列に着目することによって変換情報を作成してもよい。すなわち、行列変換部１０４における処理は、上述した処理に限定されない。
【００４６】
たとえば、図４に例示された部分行列情報においては、第１列、第４列、及び、第６列が非ゼロ列である。この場合に、行列変換部１０４は、部分行列情報において、非ゼロ列である第１列、第４列、及び、第６列を特定し、特定した列を指し示す値（すなわち、１、４、及び、６）を含む変換情報を作成する。さらに、行列変換部１０４は、第１列、第４列、及び、第６列の順に非ゼロ列が格納されている小行列情報を作成する。図４に例示された処理の場合に、ゼロ列（すなわち、第２列、第３列、第５列、及び、第７列）に含まれている要素の値は、小行列情報に格納されず、また、ゼロ列を表す列識別子（すなわち、２、３、５、及び、７）は、変換情報に格納されない。
【００４７】
次に、処理部１０５における処理について詳細に説明する。処理部１０５は、行列変換部１０４が作成した小行列情報（図４に例示）を入力し、入力した小行列情報に対して、所定の処理手順に従った処理を実行することによって、該小行列情報に関する部分モデル情報（図５に例示）を作成する。所定の処理手順が、たとえば、ロジスティック回帰法である場合に、処理部１０５は、小行列情報に対して、ロジスティック回帰法に従った処理を実行することによって、部分モデル情報を構成しているパラメタを該小行列情報に基づき決定する。処理部１０５は、算出した部分モデル情報をマスター処理装置１０３に送信する。
【００４８】
次に、図５を参照しながら、集約部１０６における処理について説明する。図５は、集約部１０６における処理を概念的に表す図である。集約部１０６は、各ワーカー処理装置１０２における行列変換部１０４が送信した変換情報と、処理部１０５が送信した部分モデル情報とを受信し、受信した該変換情報と、該部分モデル情報とに基づき、全体モデル情報を作成する。集約部１０６は、たとえば、図５に示すような、２個の変換情報と、該変換情報に関する小行列情報に基づき算出された部分モデル情報とを受信する。集約部１０６は、たとえば、受信した部分モデル情報における各要素に関して、行列情報における列識別子を該変換情報に基づき特定し、特定した該列識別子ごとに所定の処理手順に従った処理（加算演算等）を実行することにより、全体モデル情報を作成する。この処理は、たとえば、通信処理と、演算処理とが実行される「Ａｌｌ  Ｒｅｄｕｃｅ」機能を用いて実現することができる。以降、説明の便宜上、上述したような集約部１０６における処理を「集約処理」とも表す。
【００４９】
所定の処理手順を並列処理する場合に、行列情報を小行列情報に変換することによって、通信処理を短時間に実行することができる。この理由は、各小行列情報に含まれている列数が、行列情報における非ゼロ列数に比べ少ないからである。すなわち、上述したように、モデル情報に関して送受信する対象である値が減るので、集約処理における通信量を削減することができる。
【００５０】
次に、図６を参照しながら、モデル変換部１０７における処理について説明する。図６は、モデル変換部１０７における処理を概念的に表す図である。
【００５１】
モデル変換部１０７は、集約部１０６が作成した全体モデル情報と、変換情報とに基づき、各小行列情報に関する部分モデル情報を作成する。より具体的に、モデル変換部１０７は、各小行列情報に関する変換情報に含まれている列識別子を読み取り、全体モデル情報のうち、読み取った列識別子が表す列に関する値を読み取り、読み取った値を含む部分モデル情報を作成する。すなわち、該部分モデル情報は、全体モデル情報を作成する基である情報である。所定の処理手順を並列処理する場合に、モデル変換部１０７は、作成した部分モデル情報を、該小行列情報に関する処理を割り当てられたワーカー処理装置１０２に送信する。
【００５２】
情報処理システム１０１における処理は、必ずしも、上述した例に限定されず、たとえば、「Ｓｔｏｃｈａｓｔｉｃ  Ｇｒａｄｉｅｎｔ  Ｄｅｓｃｅｎｔ」アルゴリズムに従い、処理を実行してもよい。該アルゴリズムに従えば、各ワーカー処理装置１０２は、自処理装置が有するデータをミニバッチ（図７を参照）と呼ばれる単位に分割し、分割した該ミニバッチごとに部分モデル情報を作成する。図７は、ミニバッチ単位にて処理される部分行列情報を概念的に表す図である。図７においては、理解を助けるため、部分行列情報においては、すべての値を含めて表示しているが、必ずしも、所定の値と異なる値が該部分行列情報（または、小行列情報）に格納されている必要はない。また、図７に例示された部分行列情報においては、説明の便宜上、行識別子、及び、列識別子の値が表示されているが、必ずしも、該部分行列情報が、行識別子、または、列識別子を含んでいるわけではない。
【００５３】
図７に例示された部分行列情報は、２行ごとにミニバッチ単位にて、上述したような部分モデル情報を作成する処理が実行される。該部分行列情報に関する処理を実行するワーカー処理装置１０２は、ミニバッチ識別子「Ｂ１」、ミニバッチ識別子「Ｂ２」、及び、ミニバッチ識別子「Ｂ３」が表すミニバッチにて、それぞれ、当該ミニバッチ識別子が表す行に関する部分モデル情報を作成する。ワーカー処理装置１０２は、たとえば、ミニバッチ識別子「Ｂ２」が表すミニバッチに関して、部分行列情報における第３行、及び、第４行を含む部分行列情報を作成し、作成した部分行列情報に関する変換情報、及び、小行列情報（図４に例示）を作成する。ワーカー処理装置１０２は、該小行列情報に関する部分モデル情報を作成し、ミニバッチごとに作成した変換情報、及び、部分モデル情報をマスター処理装置１０３に送信する。
【００５４】
マスター処理装置１０３において、集約部１０６は、ワーカー処理装置１０２が送信した変換情報、及び、部分モデル情報を受信し、受信した変換情報に従い、部分モデル情報を全体モデル情報に集約する集約処理を実行する。その後、上述した処理と同様な処理を実行することによって、集約部１０６は、受信した変換情報に基づき、作成した全体モデル情報から、ミニバッチ単位にて部分モデル情報を作成し、作成した該部分モデル情報をワーカー処理装置１０２に送信する。
【００５５】
部分行列情報が分割されたミニバッチ単位にて処理することによって、各ミニバッチに含まれる非ゼロ列の列数が減少するので、部分行列情報を、記憶容量に関して一層効率よく格納することができる。尚、ミニバッチは、部分行列情報において、複数の行数を含む処理単位であればよい。
【００５６】
次に、図２を参照しながら、第１の実施形態に係る情報処理システム１０１における処理について詳細に説明する。図２は、第１の実施形態に係る情報処理システム１０１における処理の流れを示すシーケンス図である。
【００５７】
ワーカー処理装置１０２において、行列変換部１０４は、入力した部分行列情報（図４に例示）のうち、非ゼロ列を特定し、特定した該非ゼロ列のみが格納された小行列情報、及び、該非ゼロ列の列識別子が格納されている変換情報（図４に例示）を作成する（ステップＳ１０１）。ワーカー処理装置１０２は、作成した変換情報を、マスター処理装置１０３に送信する（ステップＳ１０２）。
【００５８】
マスター処理装置１０３は、ワーカー処理装置１０２が送信した変換情報（図４に例示）を受信する（ステップＳ１０６）。
【００５９】
ワーカー処理装置１０２において、処理部１０５は、所定の処理手順に従い、行列変換部１０４が作成した小行列情報に関する部分モデル情報（図５に例示）を作成し（ステップＳ１０３）、作成した部分モデル情報をマスター処理装置１０３に送信する（ステップＳ１０４）。
【００６０】
マスター処理装置１０３は、ワーカー処理装置１０２が送信した部分モデル情報（図５に例示）を受信し（ステップＳ１０７）、受信した部分モデル情報に対して集約処理を実行することにより、全体モデル情報（図５に例示）を作成する（ステップＳ１０８）。マスター処理装置１０３は、ステップＳ１０６にて受信した変換情報、及び、作成した全体モデル情報（図６に例示）に基づき、ステップＳ１０１にて作成された小行列情報に関する部分モデル情報（図６に例示）を作成し（ステップＳ１０９）、作成した部分モデル情報をワーカー処理装置１０２に送信する（ステップＳ１１０）。
【００６１】
ワーカー処理装置１０２は、マスター処理装置１０３が送信した部分モデル情報（図６に例示）を受信する（ステップＳ１０５）。
【００６２】
尚、図３乃至図７に示された例において、行列情報（または、部分行列情報、小行列情報）は、２次元状に配置されたデータ構造を有する行列として示されているが、図８を参照しながら説明するように、データ構造は、必ずしも、２次元状に配置されたデータ構造でなくともよい。図８は、行列情報（または、部分行列情報、小行列情報）に関して実行される処理を概念的に表す図である。図８においては、ＣＲＳ（Ｃｏｍｐｒｅｓｓｅｄ  Ｒｏｗ  Ｓｔｏｒａｇｅ）形式と呼ばれるデータ構造に従った行列情報（または、部分行列情報、小行列情報）に関して実行される処理が概念的に示されている。また、図８においては、点線にて描かれた矩形の上部に部分行列情報を示し、該矩形の下部に該部分行列情報がＣＲＳ形式に従い格納される場合のデータ構造を示している。
【００６３】
ＣＲＳ形式、または、ＣＯＯ（Ｃｏｏｒｄｉｎａｔｅｄ）等のデータ構造は、非ゼロ要素を多く含む疎行列と呼ばれる行列情報を、容量効率（メモリ効率）よく格納することが可能なデータ構造の一例である。ＣＲＳ形式に従えば、行列情報に含まれている要素の値のうち非ゼロ要素の値を含む値情報と、該行列情報において非ゼロ要素が格納されている列を表す列識別子を含むインデックス情報と、該インデックス情報の要素に関して、該行列情報における行の区切りに該当する位置を指し示すオフセット情報とがメモリ等に格納される。
【００６４】
説明の便宜上、図８に例示するように、部分行列情報は、たとえば、２行７列を有する行列情報であるとする。図８に示された例においては、説明の便宜上、列には列識別子を付し、行には行番号を付して表しているが、部分行列情報が、行識別子、または、列識別子を含んでいるわけではない。また、行列情報に含まれる、ある要素の位置を特定する情報を、「第（行識別子、列識別子）要素」なる記載形式によって表すとする。
【００６５】
係る記載形式を基に、たとえば、図８を参照すると、部分行列情報には、第（１、１）要素に非ゼロの値Ａ、第（１、４）要素に非ゼロの値Ｂ、第（２、４）要素に非ゼロの値Ｃ、及び、第（２、６）要素に非ゼロの値Ｄが格納されている。当該部分行列情報において、当該４つの要素以外の要素の値はゼロである。ＣＲＳ形式に従えば、該部分行列情報に対して、非ゼロの値Ａ、Ｂ、Ｃ、及び、Ｄを含む値情報が作成され、当該４つの非ゼロ要素が格納されている列を指し示す列識別子を含むインデックス情報が作成される。たとえば、図８に例示されている部分行列情報の場合に、非ゼロ値が格納されている第（１、１）要素、第（１、４）要素、第（２、４）要素、及び、第（２、６）要素の列識別子１、４、４、及び、６が、インデックス情報に格納されている。また、当該インデックス情報において、第１要素、及び、第２要素に格納されている値は、それぞれ、当該部分行列情報における非ゼロ要素のうち、第１行に含まれている要素の列識別子を表している。当該インデックス情報において、第３要素、及び、第４要素に格納されている値は、それぞれ、当該部分行列情報における非ゼロ要素のうち、第２行に含まれている要素の列識別子を表している。したがって、当該インデックス情報において第２要素と第３要素との間にて当該部分行列情報における行識別子が変化する。このため、オフセット情報の第１要素にはインデックス情報の先頭を表す第１要素を指し示す値が格納され、オフセット情報の第２要素には、インデックス情報において、部分行列情報の第１行と、第２行との区切りに対応していることを表す第３要素を指し示す値が格納される。
【００６６】
次に、当該部分行列情報に関する小行列情報を、ＣＲＳ形式に従い作成する処理について説明する。
【００６７】
まず、部分行列情報における各列が非ゼロ列であるか否かを表す情報が格納される記憶領域が確保される。次に、当該記憶領域には、該部分行列情報における各列が非ゼロ列であるか否かを表す情報が格納される。変換情報には、行列情報における非ゼロ列を表す列識別子が格納される。たとえば、図８に例示されている部分行列情報において、第１列、第４列、及び、第６列が非ゼロ列であるので、変換情報には、１、４、及び、６が格納される。
【００６８】
次に、行列変換部１０４は、部分行列情報における非ゼロ列に含まれる要素の値が格納されている小行列情報を作成する。図８に例示されている部分行列情報の場合に、小行列情報には、非ゼロ列である第１列、第４列、及び、第６列に含まれている要素が格納される。
【００６９】
次に、行列変換部１０４は、変換情報に基づき、部分行列情報に関するインデックス情報を、小行列情報に関するインデックス情報（以降、「小行列インデックス情報」と表す）に変換する。たとえば、インデックス情報における第２要素には「４」という値が格納され、また、変換情報における第１要素には同じ「４」が格納されているので、小行列インデックス情報における第２要素には、当該第１要素を表す「１」という値が格納されている。行列変換部１０４は、インデックス情報に含まれている他の要素に関しても、上述した処理と同様の処理を実行する。この処理は、２分探索法等によって実現することができる。
【００７０】
ワーカー処理装置１０２において、行列変換部１０４は、作成した変換情報をマスター処理装置１０３に送信する。処理部１０５は、行列変換部１０４が作成した変換情報と、ＣＲＳ形式に従ったデータ構造を有する小行列情報とに基づき、部分モデル情報を作成する。部分モデル情報に含まれている要素（パラメタ）の個数は、たとえば、変換情報に含まれている要素の個数と同じである。ワーカー処理装置１０２において、処理部１０５は、作成した部分モデル情報をマスター処理装置１０３に送信する。この場合に、ワーカー処理装置１０２が作成する部分モデル情報は、小行列情報に関する部分モデル情報を表す。
【００７１】
マスター処理装置１０３は、ワーカー処理装置１０２が送信した変換情報と、部分モデル情報（図５に例示）とを受信し、受信した該変換情報と、該部分モデル情報とに基づき、該部分モデル情報に関する集約処理を実行することによって、全体モデル情報（図５に例示）を作成する。全体モデル情報に含まれている要素（パラメタ）の個数は、たとえば、行列情報に含まれている非ゼロ列の列数と一致していてもよい。
【００７２】
マスター処理装置１０３は、図６を参照しながら説明したような処理を実行することによって、各ワーカー処理装置１０２から受信した変換情報と、該全体モデル情報（図６に例示）とに基づき、各小行列情報に関する部分モデル情報（図６に例示）を作成し、作成した部分モデル情報を、当該小行列情報に関する処理を実行するワーカー処理装置１０２に送信する。
【００７３】
ワーカー処理装置１０２は、マスター処理装置１０３が送信した部分モデル情報（図６に例示）を受信する。
【００７４】
上述したような処理は、所定の算出手順に従い、たとえば、算出した全体モデル情報が収束する、または、所定の繰り返し回数に到達する等、繰り返し実行されることもある。
【００７５】
尚、ミニバッチ単位にて処理する場合には、当該ミニバッチを処理対象として上述したような処理が実行される。
【００７６】
第１の実施形態においては、各ワーカー処理装置１０２が部分モデル情報をマスター処理装置１０３と通信する通信態様にて全体モデル情報を作成したが、必ずしも、該通信態様に従い通信する必要はない。たとえば、通信態様は、図９等を参照しながら第２の実施形態にて後述するように、ツリー構造に従い通信が実行される態様であってもよい。または、図１６等を参照しながら第３の実施形態にて後述するように、全体モデル情報が複数の処理装置にて並列処理される態様であってもよい。すなわち、全体モデル情報を作成する態様は、上述した例に限定されない。
【００７７】
次に、本発明の第１の実施形態に係る情報処理システム１０１に関する効果について説明する。
【００７８】
第１の実施形態に係る情報処理システム１０１によれば、行列情報に関する処理に要する記憶領域を、記憶容量に関して効率よく確保することができる。この理由は、処理対象である小行列情報に関する処理に要する記憶領域を、処理が必要な列の列数に応じた容量にて確保するからである。
【００７９】
また、情報処理システム１０１によれば、所定の処理手順に関する処理を効率よく実行することができる。この理由は、上述したように確保された記憶領域にて部分モデル情報に関する集約処理を、情報処理システム１０１が実行するからである。言い換えると、情報処理システム１０１においては、確保された記憶領域を用いて集約処理が実行される結果、マスター処理装置１０３と、ワーカー処理装置１０２との間で、処理対象ではない要素（たとえば、上述したゼロ要素）に関する通信量が削減されるからである。この結果、情報処理システム１０１によれば、集約処理における通信時間を削減することができる。
【００８０】
さらに、情報処理システム１０１によれば、所定の処理手順に従った処理に要する時間を削減することができる。この理由は、上述したように確保された記憶領域にて処理を実行することによって、キャッシュメモリを有効に利用することができるからである。言い換えると、上述したように確保された該記憶領域には、部分行列情報のうち処理対象である非ゼロ列のみが格納されるので、該記憶領域の容量は、該部分行列情報を格納するのに要する容量よりも小さい。したがって、上述したように確保された該記憶領域を用いることによって、部分モデル情報がキャッシュメモリに格納されている可能性が高く、したがって、キャッシュヒット率が向上するので、情報処理システム１０１によれば、該所定の処理手順に従った処理に要する所要時間を削減することができる。
【００８１】
また、行列変換部１０４によれば、少ない記憶容量にて、行列情報を格納することができる。この理由は、部分モデル情報の作成に必要な列（すなわち、所定の値とは異なる値が格納されている要素を少なくとも１つ以上含む対象列）のみを記憶するからである。
【００８２】
さらに、行列変換部１０４によれば、行列情報を並列処理するのに要する通信を短期間に決定することができる。この理由は、行列変換部１０４が提供する変換情報が、並列処理において必要な通信処理に関する通信情報を含んでいるからである。該変換情報が該通信情報を含んでいることに関して具体的に説明する。所定の処理手順が、たとえば、ロジスティック回帰法である場合には、行列情報における列に対して処理を実行する必要がある。したがって、所定の処理手順が、たとえば、ロジスティック回帰法である場合に、各処理装置に配置された小行列情報であっても、１つの列識別子が表す列に含まれている要素に関しては、各処理装置が算出した値を集計する必要がある。変換情報には該列を表す列識別子が格納されているので、該変換情報を参照することによって、必要な通信を短期間に決定することができる。
【００８３】
さらに、情報処理システム１０１によれば、対象処理を短期間に実現することが可能な情報を提供することができる。この理由は、行列情報を並列に処理可能な処理態様を情報処理システム１０１が提供するからである。たとえば、並列情報処理システムは、該行列情報に関する処理を、情報処理システム１０１が決定する割り当てに従い並列に実行することによって、該処理に要する所要時間を短期にすることができる。
【００８４】
尚、上述した例においては、部分行列情報に関する処理が１台の処理装置に割り当てられていたが、情報処理システム１０１は、さらに、行列情報（図３に例示）を分割することによって作成される部分行列情報（図３に例示）に関する処理を、処理装置に割り当てる割り当て部を有していてもよい。
【００８５】
尚、上述した実施形態においては、行列情報（または、部分行列情報、小行列情報）において、行及び列という言葉を便宜的に用いて情報処理システム１０１における処理について説明したが、行と列とを入れ換えても同様な処理によって、同様な効果を奏する。以降、第１の実施形態と同様に、行及び列という言葉を便宜的に用いて処理を説明するが、行と列とを入れ換えても同様な処理によって、同様な効果を奏する。
【００８６】
＜第２の実施形態＞
次に、上述した第１の実施形態を基本とする本発明の第２の実施形態について説明する。
【００８７】
以降の説明においては、本実施形態に係る特徴的な部分を中心に説明すると共に、上述した第１の実施形態と同様な構成については、同一の参照番号を付すことにより、重複する説明を省略する。
【００８８】
図９を参照しながら、本発明の第２の実施形態に係る情報処理システム９０１が有する構成について説明する。図９は、本発明の第２の実施形態に係る情報処理システム９０１が有する構成を表すブロック図である。
【００８９】
第２の実施形態に係る情報処理システム９０１は、ワーカー処理装置１０２と、マスター処理装置９０２とを有する。ワーカー処理装置１０２は、行列変換部１０４と、処理部１０５とを有する。マスター処理装置９０２は、集約部１０６と、モデル変換部１０７と、ツリー構造作成（決定）部９０３と、変換情報マージ部９０４とを有する。情報処理システム９０１において、マスター処理装置９０２の台数は、たとえば、１台である。ただし、マスター処理装置９０２は、ワーカー処理装置１０２が有している機能を有していてもよい。
【００９０】
ツリー構造に従い通信しながら全体モデル情報を作成する処理について、図１１を参照しながら説明する。図１１は、ツリー構造に従い通信しながら全体モデル情報を作成する処理を概念的に表す図である。図１１においては、非ゼロ要素を「△」印にて表している。
【００９１】
説明の便宜上、全体モデル情報は、第１要素乃至第７要素を含んでいるとする。第１処理装置は、第２要素、第３要素、第６要素、及び、第７要素を非ゼロ要素として有する部分モデル情報を算出するとする。第２処理装置は、第１要素、及び、第４要素を非ゼロ要素として部分モデル情報を算出するとする。第３処理装置は、第４要素、第５要素、及び、第７要素を非ゼロ要素として部分モデル情報を算出するとする。第４処理装置は、第４要素、及び、第７要素を非ゼロ要素として部分モデル情報を算出するとする。第５処理装置は、第１要素乃至第５要素、及び、第７要素を非ゼロ要素として部分モデル情報を算出するとする。説明の便宜上、図１１においては、各処理装置が全体モデル情報を処理する態様にて処理が示されているが、上述したように、各処理装置は、たとえば、非ゼロ要素のみを含む部分モデル情報に関して処理を実行する。
【００９２】
第４処理装置、及び、第５処理装置は、各処理装置にて作成された部分モデル情報を、第２処理装置に送信する。第２処理装置は、第４処理装置が送信した部分モデル情報、及び、第５処理装置が送信した部分モデル情報を受信し、受信した２つの該部分モデル情報と、自処理装置にて算出した部分モデル情報とに基づき、当該３つの部分モデル情報が集約された部分モデル情報を作成する。この場合に、集約された部分モデル情報は、第１要素乃至第５要素、及び、第７要素を非ゼロ要素として部分モデル情報である。第２処理装置は、作成した部分モデル情報を第１処理装置に送信する。第３処理装置は、作成した部分モデル情報を第１処理装置に送信する。第１処理装置は、第２処理装置が送信した部分モデル情報と、第３処理装置が送信した部分モデル情報とを受信し、受信した２つの該部分モデル情報と、自処理装置が作成した部分モデル情報とに基づき全体モデル情報を作成する。
【００９３】
当該処理における通信量について説明する。上述したように第４処理装置にて作成された部分モデル情報に含まれる非ゼロ要素数は２個である。第５処理装置にて作成された部分モデル情報に含まれる非ゼロ要素数は６個である。この結果、第２処理装置は、８個（＝２＋６）の非ゼロ要素を受信する。第２処理装置は、受信した部分モデル情報と、自処理装置が作成した部分モデル情報とに基づき、第１要素乃至第５要素、及び、第７要素が非ゼロ要素である部分モデル情報を作成する。この結果、第２処理装置にて作成された部分モデル情報に含まれる非ゼロ要素数は６つである。第１処理装置は、９個（＝６＋３）の非ゼロ要素を受信する。したがって、全体モデル情報を作成する処理においては、１７個（＝８＋９）の非ゼロ要素を通信する必要がある。
【００９４】
全体モデル情報と、変換情報とに基づき、小行列情報に関する部分モデル情報を送信する処理においては、集約処理にて実行された通信処理と逆方向に該部分モデル情報を送信する。すなわち、図１１に示す例においては、第１処理装置が第２処理装置及び第３処理装置に部分モデル情報を送信し、その後、第２処理装置が第４処理装置及び第５処理装置に部分モデル情報を送信する。
【００９５】
処理装置が通信する順序を変更することによって、通信量を減らすことができることについて、図１２を参照しながら説明する。図１２は、ツリー構造に従い通信しながら全体モデル情報を作成する処理を概念的に表す図である。
【００９６】
この例では、第２処理装置及び第４処理装置が、それぞれ、部分モデル情報を第３処理装置に送信する。第３処理装置は、第２処理装置及び第４処理装置が送信した部分モデル情報と、自処理装置が算出した部分モデル情報とに基づき、３個の当該部分モデル情報が集約された部分モデル情報を作成し、作成した部分モデル情報を第５処理装置に送信する。第５処理装置は、第３処理装置が送信した部分モデル情報と、第１処理装置が送信した部分モデル情報とを受信する。したがって、第３処理装置は、４個（＝２＋２）の非ゼロ要素を受信し、その後、４個の非ゼロ要素（第１、４、５、及び、７要素）を含む部分モデル情報（すなわち、集約された部分モデル情報）を作成する。第５処理装置は、８個（＝４＋４）の非ゼロ要素を受信する。したがって、全体モデル情報を作成する処理においては、１２個（＝４＋８）の非ゼロ要素を通信する必要がある。よって、処理装置が通信する順序を変更することによって、上述した処理に比べて通信量が少ない処理を実現することができる。
【００９７】
通信量が少ない処理は、たとえば、非ゼロ要素の個数が多い部分モデル情報を算出する処理装置をツリー構造におけるルートノード（Ｒｏｏｔ  Ｎｏｄｅ）の近く（すなわち、上位）に配置する。さらに、非ゼロ要素の個数が少ない部分モデル情報を算出する処理装置をツリー構造におけるリーフノード（Ｌｅａｆ  Ｎｏｄｅ）の近く（すなわち、下位）に配置することによって実現することができる。尚、上述したように、部分モデル情報に含まれている非ゼロ要素の個数は、当該部分モデル情報を作成する基である小行列情報における非ゼロ列の個数に応じて決まる。
【００９８】
以降の説明においては、ルートノード、及び、リーフノード以外のノードを「中間ノード」と表す。
【００９９】
尚、ツリー構造において、あるノードに配置されたある処理装置に対して、該ノードの親ノード（Ｐａｒｅｎｔ  Ｎｏｄｅ）に配置された処理装置を、該ある処理装置の「親処理装置」と表す。また、ツリー構造において、あるノードに配置されたある処理装置に対して、該ノードの子ノード（Ｃｈｉｌｄ  Ｎｏｄｅ）に配置された処理装置を、該ある処理装置の「子処理装置」と表す。たとえば、図１１に示す例において、第２処理装置の親処理装置は、第１処理装置である。図１１に示す例において、第２処理装置の子処理装置は、第４処理装置、及び、第５処理装置である。第４処理装置の親処理装置は、第２処理装置であり、第４処理装置の子処理装置は、ない。
【０１００】
図１３乃至図１５を参照しながら、情報処理システム９０１における処理のうち、特に、入出力に関する処理について説明する。図１３乃至図１５は、情報処理システム９０１における処理を概念的に表す図である。
【０１０１】
図１３に示された情報処理システム１３１５において、行列変換部１３０３、処理部１３０９の動作は、第１の実施形態にて図１を参照しながら説明した処理と同様であるが、変換情報１３０４、及び、部分モデル情報１３１０を通信する通信先が、必ずしも、当該処理と同様であるとは限らない。たとえば、各処理装置は、変換情報１３０４、及び、部分モデル情報１３１０を当該処理装置の親処理装置１３０５に送信する。各処理装置は、さらに、自処理装置にて作成された変換情報１３０４を、各処理装置の通信順序を決定する特定処理装置１３０１に送信する。
【０１０２】
特定処理装置１３０１において、ツリー構造作成（決定）部１３１２は、各処理装置が送信した変換情報１３１１を受信し、受信した変換情報１３１１に含まれている要素数（サイズ）に基づき、各処理装置の通信順序を決定する。すなわち、ツリー構造作成部１３１２は、各処理装置の通信順序を表すツリー構造１３１３を作成する。特定処理装置１３０１において、ツリー構造作成（決定）部１３１２は、各処理装置１３１４に、該処理装置が割り当てられたノードの親ノードとして配置された親処理装置を表す識別子と、該処理装置が割り当てられたノードの子ノードとして配置された子処理装置を表す識別子とを送信する。各処理装置は、特定処理装置１３０１が送信した親処理装置を表す識別子と、子処理装置を表す識別子とを受信する。以降、各処理装置は、これらの識別子に基づき、該処理装置の親処理装置、または、該処理装置の子処理装置との通信を実行する。
【０１０３】
図１４を参照すると、中間ノード及びルートノードに配置された処理装置において、変換情報マージ部１４０７は、自処理装置の子処理装置が送信した変換情報１４０１を受信し、受信した変換情報１４０１と、自処理装置が作成した変換情報１４０２とを含む変換情報１４０９を作成する。中間ノードに配置された処理装置において、変換情報マージ部１４０７は、作成した変換情報１４０９を自処理装置の親処理装置１４１０に送信する。
【０１０４】
中間ノード及びルートノードに配置された処理装置において、集約部１４０８は、自処理装置の子処理装置が送信した変換情報１４０３と、自処理装置の子処理装置が送信した部分モデル情報１４０４と、自処理装置が作成した変換情報１４０５と、自処理装置が作成した部分モデル情報１４０６とを集約することによって、集約後の部分モデル情報１４１１を作成する。この場合に、ルートノードに配置された処理装置における集約部１４０８が作成する部分モデル情報１４１１は、全体モデル情報（すなわち、すべての処理装置における部分モデル情報が集約されたモデル情報）である。中間ノードに配置された処理装置において、集約部１４０８は、作成した部分モデル情報１４１１を、自処理装置の親処理装置１４１０に送信する。
【０１０５】
図１１（または、図１２）に示されたツリー構造において、部分モデル情報は、ツリー構造におけるルートノードに配置された処理装置から該ツリー構造における下位ノードに配置された処理装置の順に、モデル変換部１５０４によって作成される。中間ノードに配置された処理装置において、モデル変換部１５０４は、自処理装置の親処理装置が送信した部分モデル情報１５０２と、自処理装置が作成した変換情報１５０３とに基づき、自処理装置が処理する対象である部分モデル情報１５０７を作成する。中間ノードに配置された処理装置において、モデル変換部１５０４は、作成した変換情報１５０３と、自処理装置の子処理装置から受信した変換情報１５０１とに基づき、該子処理装置が処理する対象である部分モデル情報１５０６を作成し、作成した該部分モデル情報を該子処理装置１５０５に送信する。
【０１０６】
次に、図１０を参照しながら、本発明の第２の実施形態に係る情報処理システム９０１における処理の流れについて説明する。図１０は、第２の実施形態に係る情報処理システム９０１における処理の流れを示すフローチャートである。
【０１０７】
まず、ツリー構造内の各ノードに配置された処理装置において、行列変換部１０４は、部分行列情報のうち非ゼロ列における要素の値が格納されている小行列情報と、該小行列情報における列と、該部分行列情報における列との対応関係を表す変換情報とを作成する（ステップＳ１００１）。次に、各処理装置は、上述したような特定処理装置に、該変換情報を送信する（ステップＳ１００２）。該特定処理装置は、各処理装置が送信した変換情報を受信し、該処理装置が送信した変換情報に含まれている要素の個数（すなわち、非ゼロ要素の個数）の降順に、ツリー構造における上位ノードから当該処理装置を割り当てる。すなわち、該特定処理装置は、情報処理システム９０１において各処理装置が通信する順序を表すツリー構造を作成することによって、各処理装置の処理順序を決める（ステップＳ１００３）。
【０１０８】
次に、中間ノード及びルートノードに配置された各処理装置において、該処理装置は、自処理装置の子処理装置が送信した変換情報を受信し（ステップＳ１００４）、受信した該変換情報と、自処理装置が作成した変換情報とを含む変換情報（マージ後変換情報）を作成し（ステップＳ１００５）、作成した変換情報を自処理装置の親処理装置に送信する（ステップＳ１００６）。
【０１０９】
そして、各処理装置は、変換情報に基づき、該処理装置に割り当てられた小行列情報に関する部分モデル情報を作成する（ステップＳ１００７）。該変換情報に含まれている要素の個数と、該部分モデル情報に含まれている要素の個数とは、同数であってもよい。すなわち、各処理装置は、小行列情報に対して所定の処理手順に従い処理を実行することによって、当該部分モデル情報を作成する。中間ノード及びリーフノードに配置された処理装置において、該処理装置は、作成した部分モデル情報を自処理装置の親処理装置に送信する（ステップＳ１００８）。
【０１１０】
中間ノード及びルートノードに配置された各処理装置において、該処理装置は、変換情報に従い、自処理装置の子処理装置が送信した部分モデル情報と、自処理装置が作成した部分モデル情報とが集約された部分モデル情報を作成する。すなわち、該処理装置は、自処理装置の子処理装置が送信した部分モデル情報と、自処理装置が作成した部分モデル情報とを集約する集約処理を実行する（ステップＳ１００９）。
【０１１１】
ツリー構造（図１１、図１２に例示）において上位に配置された処理装置から該ツリー構造において下位に配置された処理装置に至るまで順に後述の処理が実行される。モデル変換部１０７は、自処理装置の親処理装置が送信した部分モデル情報を受信する。モデル変換部１０７は、自処理装置が作成した変換情報に従い該部分モデル情報から自処理装置が処理する対象である部分モデル情報を作成する。さらに、モデル変換部１０７は、自処理装置の子処理装置が送信した変換情報に従い、該部分モデル情報から当該子処理装置が処理する対象である部分モデル情報を作成し、作成した部分モデル情報を該子処理装置に送信する（ステップＳ１０１０）。
【０１１２】
上述したような処理は、算出した全体モデル情報が収束する、または、所定の繰り返し回数に到達する等、所定の処理手順に従い規定される方法に従い繰り返し実行される。
【０１１３】
また、ミニバッチ単位にて処理が実行される場合には、上述したような処理と同様な処理が、ミニバッチ単位にて作成された変換情報に関して実行される。
【０１１４】
次に、本発明の第２の実施形態に係る情報処理システム９０１に関する効果について説明する。
【０１１５】
第２の実施形態に係る情報処理システム９０１によれば、行列情報に関する処理に要する記憶領域を、容量に関して効率よく確保することができる。この理由は、第１の実施形態に示した理由と同様に、処理対象である小行列情報に関する処理に要する記憶領域を、処理が必要な列の列数に応じた容量にて確保するからである。
【０１１６】
さらに、本実施形態に係る情報処理システム９０１によれば、所定の処理手順に従った処理に要する時間が、さらに、少なくなるという効果を奏する。この理由は、情報処理システム９０１が、図１２を参照しながら説明したような処理に従い、通信処理にて通信する非ゼロ要素の個数が少なくなるよう、通信順序を決定するからである。言い換えると、列数が多い小行列情報よりも少ない小行列情報の方が、データ容量が少ないので、本実施形態に係る情報処理システム９０１によれば、通信量が減る。すなわち、本実施形態に係る情報処理システム９０１によれば、所定の処理手順に従った処理に要する時間が、さらに、短くなる。
【０１１７】
＜第３の実施形態＞
次に、上述した第１の実施形態を基本とする本発明の第３の実施形態について説明する。
【０１１８】
以降の説明においては、本実施形態に係る特徴的な部分を中心に説明すると共に、上述した第１の実施形態と同様な構成については、同一の参照番号を付すことにより、重複する説明を省略する。
【０１１９】
図１６を参照しながら、本発明の第３の実施形態に係る情報処理システム１６０１における処理について説明する。図１６は、本発明の第３の実施形態に係る情報処理システム１６０１が有する構成を示すブロック図である。
【０１２０】
本発明の第３の実施形態に係る情報処理システム１６０１は、ワーカー処理装置１０２と、マスター処理装置１６０２とを有する。ワーカー処理装置１０２は、行列変換部１０４と、処理部１０５とを有する。マスター処理装置１６０２は、変換情報分割部１６０５と、モデル情報分割部１６０３と、分割範囲決定部１６０４と、集約部１０６と、モデル変換部１０７とを有する。
【０１２１】
行列変換部１０４、及び、処理部１０５は、それぞれ、図２を参照しながら第１の実施形態にて説明した処理と同様な処理を実行する。
【０１２２】
図２０を参照しながら、特に、情報処理システム１６０１において入出力される情報を中心に、情報処理システム１６０１における処理について説明する。図２０は、情報処理システム１６０１における処理を概念的に表す図である。
【０１２３】
図２０に示された情報処理システム１６０１において、行列変換部２００２、及び、処理部２０１０における処理は、第１の実施形態にて図１を参照しながら説明した処理と同様であるが、変換情報、及び、部分モデル情報を通信する通信先が、必ずしも、当該処理と同様であるとは限らない。
【０１２４】
各処理装置は、変換情報２０１５を、分割範囲を決定する処理装置を表す特定処理装置２００５（または、分割範囲決定部２０１６）に送信する。特定処理装置２００５において、分割範囲決定部２０１６は、該変換情報２０１５を受信し、図１８、及び、図１９を参照しながら後述するような処理を実行することにより、受信した変換情報２０１５に関する処理範囲の各処理装置２０１４に対する割り当てを表す分割範囲２０１７を決定する。分割範囲決定部２０１６は、決定した分割範囲２０１７を各処理装置２０１４に送信する。
【０１２５】
各処理装置２０１４において、変換情報分割部２００４は、特定処理装置２００５が送信した分割範囲２００７（すなわち、分割範囲２０１７）を受信し、受信した分割範囲２００７に基づき、変換情報２００３を処理装置ごとの分割変換情報２００６に分割し、該分割変換情報２００６を各処理装置２０１４に送信する。また、各処理装置２０１４において、処理結果分割部２０１２は、受信した分割範囲２００７（すなわち、分割範囲２０１７）に基づき、部分モデル情報２０１１についても分割し、分割範囲２００７に関する部分モデル情報２０１３を、当該処理が割り当てられた処理装置２０１４に送信する。
【０１２６】
図２１を参照しながら、特に、集約部２１０６における処理を中心に、情報処理システム１６０１における処理について説明する。図２１は、情報処理システム１６０１における処理を概念的に表す図である。
【０１２７】
各処理装置において、集約部２１０６は、他処理装置（たとえば、処理装置２１０１、処理装置２１０４）が送信した分割変換情報２１０２、及び、分割部分モデル情報２１０５を受信し、受信した分割部分モデル情報２１０５を全体モデル情報に集約する集約処理を実行する。さらに、各処理装置において、モデル変換部２１０３は、該分割変換情報２１０２に基づき、各処理装置に割り当てられた範囲における要素の値を読み取り、読み取った要素の値を当該処理装置（たとえば、処理装置２１０７）に送信する。
【０１２８】
図１８を参照しながら、全体モデル情報が各処理装置にて並列処理される場合に実行される処理について説明する。図１８は、全体モデル情報が各処理装置にて並列処理される場合に実行される処理を概念的に表す図である。
【０１２９】
説明の便宜上、全体モデル情報に含まれている要素の個数は、６個であるとする。第１処理装置には、全体モデル情報のうち第１要素（要素１１、要素２１、要素３１）と、第２要素（要素１２、要素２２、要素３２）とに関して集約する処理が割り当てられているとする。第２処理装置には、全体モデル情報のうち第３要素（要素１３、要素２３、要素３３）と、第４要素（要素１４、要素２４、要素３４）とに関して集約する処理が割り当てられているとする。この場合に、第３処理装置には、全体モデル情報のうち第５要素（要素１５、要素２５、要素３５）と、第６要素（要素１６、要素２６、要素３６）とに関して集約する処理が割り当てられているとする。第１処理装置、及び、第３処理装置は、それぞれ、第３要素（要素１３、要素３３）の値と、第４要素（要素１４、要素３４）の値とを第２処理装置に送信する。第１処理装置、及び、第２処理装置は、それぞれ、第５要素（要素１５、要素２５）の値と、第６要素（要素１６、要素２６）の値とを第３処理装置に送信する。第２処理装置、及び、第３処理装置は、それぞれ、第１要素（要素２１、要素３１）の値と、第２要素（要素２２、要素３２）の値とを第１処理装置に送信する。
【０１３０】
各処理装置は、部分モデル情報を、自処理装置に割り当てられた処理範囲の要素に関して集約する処理を実行する。その後、各処理装置は、自処理装置が算出した処理範囲の要素の値を他処理装置に送信する。この処理によって、各処理装置は、全体モデル情報が格納されている。
【０１３１】
尚、部分モデル情報を全体モデル情報に集約する処理等は、上述した各実施形態と同様な処理である。本実施形態においては、該処理に関する詳細な説明を省略する。
【０１３２】
また、各処理装置に割り当てられた集約処理における演算量（または、通信量）を各処理装置に亘って均等化することにより、情報処理システム１６０１における処理時間を短時間に処理することができる。図１９を参照しながら、演算量（または、通信量）を均等化する処理について説明する。図１９は、処理装置の台数に基づき集約処理を処理装置に割り当てる処理の一例を概念的に表す図である。尚、説明の便宜上、図１９に示された例においては、値がゼロである要素が示されているが、値がゼロである該要素を各処理装置が処理する（または、格納している）わけでない。
【０１３３】
集約処理における演算量（または、通信量）は、各処理装置に割り当てられた集約処理において演算対象である要素の個数に応じて変化する。該個数が多ければ該通信量（または、演算量）は増大し、該個数が少なければ該通信量（または、演算量）は減少する。
【０１３４】
しかし、上述したように、全体モデル情報に関する要素識別子に基づき集約処理を各処理装置に割り当てた場合に、各要素識別子が表す要素のうち非ゼロ要素の個数は、必ずしも、均等であるとは限らない。したがって、要素識別子に基づき各処理装置に集約処理を割り当てた場合には、各処理装置に関して、演算量（または、通信量）が均等化されているとは限らない。
【０１３５】
そこで、図１８に例示するように、全体モデル情報に関する要素識別子に基づき集約処理を各処理装置に割り当てるのではなく、図１９に例示するように、該要素識別子が表す要素を処理している処理装置の台数に基づき各処理装置に割り当てることによって、各処理装置における演算量を均等化することができる。
【０１３６】
図１９の上部における部分モデル情報に例示されているように、第１要素識別子乃至第３要素識別子が表す要素（すなわち、要素１１、要素３２、及び、要素２３）、及び、第６要素識別子が表す要素（すなわち、要素２６）には、それぞれ、１台の処理装置が割り当てられているとする。第４要素識別子が表す要素（すなわち、要素１４、要素２４、及び、要素３４）には、３台の処理装置が割り当てられ、さらに、第５要素識別子が表す要素（すなわち、要素１５、及び、要素３５）には、２台の処理装置に割り当てられているとする。
【０１３７】
集約処理を処理装置に均等に割り当てる目的のためには、たとえば、第１処理装置に第１要素識別子乃至第３要素識別子が表す要素に関する集約処理を割り当て、第２処理装置に第４要素識別子が表す要素に関する集約処理を割り当てる。さらに、第３処理装置に第５要素識別子乃至第６要素識別子が表す要素に関する集約処理を割り当てる。この割り当てによって、該要素を処理する処理装置の台数が均等化される。したがって、情報処理システム１６０１は、上述したように割り当てを決定することによって、各処理装置に関して、演算量（または、通信量）が均等化する。この割り当て処理の一例について、具体的に説明する。
【０１３８】
たとえば、分割範囲決定部１６０４は、全体モデル情報に関する要素識別子ごとに、該要素識別子が表す要素を処理している処理装置の台数を求める。図１９における上部に示された部分モデル情報の場合に、第１要素識別子乃至第６要素識別子が表す要素に当てられている処理装置の台数は、それぞれ、１（要素１１）、１（要素３２）、１（要素２３）、３（要素１４、要素２４、要素３４）、２（要素１５、要素３５）、及び、１（要素２６）である。分割範囲決定部１６０４は、たとえば、各処理装置が作成した変換情報に基づき、上述した台数を求める。次に、分割範囲決定部１６０４は、１台の処理装置あたりの非ゼロ要素の個数が均等であるように割り当てを決定する。たとえば、分割範囲決定部１６０４は、後述するような処理に従い、割り当てを決定する。
【０１３９】
たとえば、分割範囲決定部１６０４は、処理装置の台数に関して、順に累計値を算出する。図１９に示された例の場合に、分割範囲決定部１６０４は、１、２（＝１＋１）、３（＝２＋１）、６（＝３＋３）、８（＝６＋２）、及び、９（＝８＋１）を求める。最後に算出した累計値（たとえば、９）は、非ゼロ要素の個数の累計値を表す。分割範囲決定部１６０４は、最後に算出した該累計値を、処理装置の台数（たとえば、３）にて割り算することによって、１台に割り当てる非ゼロ要素の個数（すなわち、平均値、たとえば、３（＝９÷３））を求める。分割範囲決定部１６０４は、上述した順に、該平均値に近い値となるよう割り当てを決定する。以降、説明の便宜上、算出した値「１、２、３、６、８、９」を数値列と表す。
【０１４０】
分割範囲決定部１６０４は、たとえば、２分探索手法等に従い、数値列のうち平均値が３に近い値である要素を特定する。この場合に、該数値列の左から３番目の値が３であるので、分割範囲決定部１６０４は、第１処理装置に対して割り当てる範囲を第１要素乃至第３要素に決定する。次に、分割範囲決定部１６０４は、２台目の処理装置に対して割り当てを決定する値（６（＝３×２））を算出し、該数値列において左から４番目の値が６であることを決定する。分割範囲決定部１６０４は、２台目の処理装置である第２処理装置に対して割り当てる範囲を第４要素に決定する。次に、分割範囲決定部１６０４は、３台目の処理装置に対して割り当てを決定する値（９（＝３×３））を算出し、該数値列において左から６番目の値が９であることを決定する。分割範囲決定部１６０４は、３台目の処理装置である第３処理装置に対して割り当てる範囲を第５要素乃至第６要素に決定する。
【０１４１】
尚、割り当てを算出する手順は、上述した手順に限定されない。
【０１４２】
次に、図１７を参照しながら、本発明の第３の実施形態に係る情報処理システム１６０１における処理について説明する。図１７は、情報処理システム１６０１における処理の流れを示すフローチャートである。
【０１４３】
各処理装置において、行列変換部１０４は、部分行列情報（図４に例示）のうち、非ゼロ列に含まれている要素の値が格納されている小行列情報（図４に例示）と、該小行列情報における列を表す列識別子と、該行列情報における列を表す列識別子との関係を表す変換情報（図４に例示）を作成する（ステップＳ１７０１）。
【０１４４】
各処理装置において、行列変換部１０４は、作成した変換情報（図４に例示）を、分割範囲を決定する機能を有する特定処理装置に送信する（ステップＳ１７０２）。
【０１４５】
特定処理装置において、分割範囲決定部１６０４は、たとえば、図１７を参照しながら説明したような処理を実行することによって、処理を割り当てる範囲（すなわち、分割範囲）を決定する（ステップＳ１７０３）。その後、分割範囲決定部１６０４は、決定した分割範囲に基づき、変換情報を、処理装置ごとの部分変換情報に分割し（ステップＳ１７０４）、各処理装置に当該部分変換情報を送信する。
【０１４６】
各処理装置は、特定処理装置が送信した部分変換情報を受信し、受信した該部分変換情報に基づき、小行列情報と部分モデル情報とに対して、所定の処理手順に従い処理を実行する（ステップＳ１７０５）。各処理装置は、該所定の処理手順に従い処理を実行することによって、該小行列情報に関する部分モデル情報を作成する。各処理装置は、作成した部分モデル情報を、分割範囲情報（たとえば、図２０における分割範囲２００７）に基づき分割し、分割された該部分モデル情報を、当該部分モデル情報に関する処理を実行する処理装置に送信する。該部分モデル情報を分割する処理は、変換情報を分割する処理と同様な処理である。
【０１４７】
該部分モデル情報を受信した処理装置は、分散された変換情報に従い、該部分モデル情報を集約する（ステップＳ１７０６）ことによって部分モデル情報を作成し、作成した部分モデル情報を各処理装置に送信する。
【０１４８】
上述したような処理は、算出した部分モデル情報が収束する、または、所定の繰り返し回数に到達する等、所定の処理手順にて規定される方法に従い繰り返し実行される。
【０１４９】
また、ミニバッチ単位にて処理が実行される場合には、上述したような処理と同様な処理が、ミニバッチ単位にて作成された変換情報に関して実行される。
【０１５０】
次に、本発明の第３の実施形態に係る情報処理システム１６０１に関する効果について説明する。
【０１５１】
第３の実施形態に係る情報処理システム１６０１によれば、行列情報に関する処理に要する記憶領域を、容量に関して効率よく確保することができる。この理由は、第１の実施形態に示した理由と同様に、処理対象である小行列情報に関する処理に要する記憶領域を、処理が必要な列の列数に応じた容量にて確保するからである。
【０１５２】
さらに、第３の実施形態に係る情報処理システム１６０１によれば、行列情報に関する処理を高い並列性能にて実行することが可能な情報を提供することができる。この理由は、図１９を参照しながら説明したような処理によって、情報処理システム１６０１が、所定の処理手順に従った処理を均等（または、略均等）に処理装置に割り当てるからである。言い換えると、列識別子を含む変換情報の個数が均等（または、略均等）であるグループに列を分類することによって、該グループに含まれている列に関する集計処理は均等（または、略均等）である。この結果、たとえば、情報処理システム１６０１が該グループを１つの処理装置に割り当てることによって、高い並列効率にて集計処理を実行することができる。略均等は、処理量の平均値に対する、該処理量の分散値がある値（たとえば、０％乃至８％）以下であるか否かに基づき判定することができる。
【０１５３】
＜第４の実施形態＞
次に、本発明の第４の実施形態について説明する。
【０１５４】
図２２を参照しながら、本発明の第４の実施形態に係る領域確保装置２２０１が有する構成について説明する。図２２は、本発明の第４の実施形態に係る領域確保装置２２０１が有する構成を示すブロック図である。
【０１５５】
第４の実施形態に係る領域確保装置２２０１は、配列特定部２２０２と、領域確保部２２０３とを有する。領域確保装置２２０１は、配列情報の少なくとも一部である部分配列情報を入力する。尚、部分配列情報は、配列情報のうち、連続した行番号に配置された値に関する情報でなくともよく、たとえば、離散的な行番号に配置された値に関する情報であってもよい。
【０１５６】
配列情報は、たとえば、図３に例示された行列情報を表す。部分配列情報は、たとえば、図４に例示された部分行列情報を表す。すなわち、本実施形態において、配列情報は、行及び列により２次元に配置された情報を表す。配列情報のうち、行、または、列を表す配列のうち、一方を第１配列と表し、他方を第２配列と表す。
【０１５７】
次に、図２３を参照しながら、第４の実施形態に係る領域確保装置２２０１における処理について説明する。図２３は、第４の実施形態に係る領域確保装置２２０１における処理の流れを示すフローチャートである。
【０１５８】
まず、配列特定部２２０２は、入力した部分配列情報（たとえば、図４に例示された部分行列情報）に関して、縦方向に配置された要素に格納されている値のうち、少なくとも１つの値が所定の値とは異なる対象配列を特定し、さらに、特定した該対象配列を表す配列識別子を特定する（ステップＳ２３０１）。たとえば、図４に示された例の場合に、配列特定部２２０２は、部分配列情報のうち、第１配列と、第４配列と、第６配列とに関して、これらの配列に含まれている要素に格納されている値のうち、少なくとも１つの値が所定の値とは異なっていることを特定する。すなわち、配列特定部２２０２は、第１配列と、第４配列と、第６配列とが特定配列であることを特定する。次に、配列特定部２２０２は、第１配列と、第４配列と、第６配列を表す配列識別子として、たとえば、「１」、「４」、及び、「６」を特定する。配列識別子は、列識別子及び行識別子のうち、少なくとも一方を表す。
【０１５９】
次に、領域確保部２２０３は、配列特定部２２０２が特定した配列識別子の個数を算出し（ステップＳ２３０２）、算出した個数に応じた記憶容量を有する記憶領域を確保する（ステップＳ２３０３）。たとえば、配列特定部２２０２が配列識別子「１」、「４」、及び、「６」を特定した場合に、領域確保部２２０３は、配列識別子の個数である「３」を算出し、算出した個数に応じた記憶領域（たとえば、３個の値分の記憶領域）を確保する。領域確保部２２０３が確保した記憶領域には、たとえば、該部分配列情報に関する部分モデル情報（図５等に例示）が格納される。
【０１６０】
配列特定部２２０２、及び、領域確保部２２０３は、行列変換部１０４（図１）、行列変換部１３０３（図１３）、または、行列変換部２００２（図２０）が有する機能等と同様な機能によって実現することができる。すなわち、領域確保装置２２０１は、情報処理システム１０１（図１）、情報処理システム９０１（図９）、または、情報処理システム１６０１（図１６）が有する機能等と同様な機能によって実現することができる。
【０１６１】
次に、本発明の第４の実施形態に係る領域確保装置２２０１に関する効果について説明する。
【０１６２】
第４の実施形態に係る領域確保装置２２０１によれば、配列情報に関する処理に要する記憶領域を、記憶容量に関して効率よく確保することができる。この理由は、処理対象である小配列情報に関する処理に要する記憶領域を、処理が必要な配列の配列数に応じた容量にて確保するからである。処理が必要な配列は、該小配列情報のうち、縦（列）方向に配列された要素に格納されている値のうち、少なくとも１つの値が所定の値とは異なる配列である。この結果、情報処理システムは、領域確保装置２２０１が確保した記憶領域に部分モデル情報等を格納することによって、所定の処理手順に従った処理を効率よく実行することができる。
【０１６３】
（ハードウェア構成例）
上述した本発明の第１の実施形態乃至第３の実施形態に係る情報処理システム、または、第４の実施形態に係る領域確保装置を、１つの計算処理装置（情報処理装置、コンピュータ）を用いて実現するハードウェア資源の構成例について説明する。但し、係る領域確保装置は、物理的または機能的に少なくとも２つの計算処理装置を用いて実現されてもよい。また、係る領域確保装置は、専用の装置として実現されてもよい。
【０１６４】
図２４は、第１の実施形態乃至第３の実施形態に係る情報処理システム、または、第４の実施形態に係る領域確保装置を実現可能な計算処理装置のハードウェア構成例を概略的に示すブロック図である。計算処理装置２４２０は、中央処理演算装置（Ｃｅｎｔｒａｌ＿Ｐｒｏｃｅｓｓｉｎｇ＿Ｕｎｉｔ、以降「ＣＰＵ」と表す）２４２１、メモリ２４２２、ディスク２４２３、不揮発性記録媒体２４２４、及び、通信インターフェース（以降、「通信ＩＦ」と表す）２４２７を有する。計算処理装置２４２０は、入力装置２４２５、出力装置２４２６に接続可能であってもよい。計算処理装置２４２０は、通信ＩＦ２４２７を介して、他の計算処理装置、及び、通信装置と情報を送受信することができる。
【０１６５】
不揮発性記録媒体２４２４は、コンピュータが読み取り可能な、たとえば、コンパクトディスク（Ｃｏｍｐａｃｔ＿Ｄｉｓｃ）、デジタルバーサタイルディスク（Ｄｉｇｉｔａｌ＿Ｖｅｒｓａｔｉｌｅ＿Ｄｉｓｃ）である。また、不揮発性記録媒体２４２４は、ユニバーサルシリアルバスメモリ（ＵＳＢメモリ）、ソリッドステートドライブ（Ｓｏｌｉｄ＿Ｓｔａｔｅ＿Ｄｒｉｖｅ）等であってもよい。不揮発性記録媒体２４２４は、電源を供給しなくても係るプログラムを保持し、持ち運びを可能にする。不揮発性記録媒体２４２４は、上述した媒体に限定されない。また、不揮発性記録媒体２４２４の代わりに、通信ＩＦ２４２７、及び、通信ネットワークを介して係るプログラムを持ち運びしてもよい。
【０１６６】
すなわち、ＣＰＵ２４２１は、ディスク２４２３に格納されているソフトウェア・プログラム（コンピュータ・プログラム：以下、単に「プログラム」と称する）を、実行する際にメモリ２４２２にコピーし、演算処理を実行する。ＣＰＵ２４２１は、プログラム実行に必要なデータをメモリ２４２２から読み取る。外部への出力が必要な場合に、ＣＰＵ２４２１は、出力装置２４２６に出力結果を出力する。外部からプログラムを入力する場合に、ＣＰＵ２４２１は、入力装置２４２５からプログラムを読み取る。ＣＰＵ２４２１は、上述した図１、図９、図１６、または、図２２に示す各部が表す機能（処理）に対応するところのメモリ２４２２にある情報処理プログラム（図２、図１０、または、図１７）、または、領域確保プログラム（図２３）を解釈し実行する。ＣＰＵ２４２１は、上述した本発明の各実施形態において説明した処理を順次実行する。
【０１６７】
すなわち、このような場合に、本発明は、係る領域確保プログラムによっても成し得ると捉えることができる。さらに、係るプログラムが記録されたコンピュータが読み取り可能な不揮発性の記録媒体によっても、本発明は成し得ると捉えることができる。
【０１６８】
以上、上述した実施形態を模範的な例として本発明を説明した。しかし、本発明は、上述した実施形態には限定されない。すなわち、本発明は、本発明のスコープ内において、当業者が理解し得る様々な態様を適用することができる。
【０１６９】
この出願は、２０１６年１０月１１日に出願された日本出願特願２０１６−１９９７１０を基礎とする優先権を主張し、その開示の全てをここに取り込む。
【符号の説明】
【０１７０】
１０１    情報処理システム
１０２    ワーカー処理装置
１０３    マスター処理装置
１０４    行列変換部
１０５    処理部
１０６    集約部
１０７    モデル変換部
９０１    情報処理システム
９０２    マスター処理装置
９０３    ツリー構造作成部
９０４    変換情報マージ部
１３０１    特定処理装置
１３０３    行列変換部
１３０４    変換情報
１３０５    親処理装置
１３０９    処理部
１３１０    部分モデル情報
１３１１    変換情報
１３１２    ツリー構造作成部
１３１３    ツリー構造
１３１４    処理装置
１３１５    情報処理システム
１４０１    変換情報
１４０２    変換情報
１４０３    変換情報
１４０４    部分モデル情報
１４０５    変換情報
１４０６    部分モデル情報
１４０７    変換情報マージ部
１４０８    集約部
１４０９    変換情報
１４１０    親処理装置
１４１１    部分モデル情報
１５０１    変換情報
１５０２    部分モデル情報
１５０３    変換情報
１５０４    モデル変換部
１５０５    子処理装置
１５０６    部分モデル情報
１５０７    部分モデル情報
１６０１    情報処理システム
１６０２    マスター処理装置
１６０３    モデル情報分割部
１６０４    分割範囲決定部
１６０５    変換情報分割部
２００２    行列変換部
２００３    変換情報
２００４    変換情報分割部
２００５    特定処理装置
２００６    分割変換情報
２００７    分割範囲
２０１０    処理部
２０１１    部分モデル情報
２０１２    処理結果分割部
２０１３    部分モデル情報
２０１４    処理装置
２０１５    変換情報
２０１６    分割範囲決定部
２０１７    分割範囲
２１０１    処理装置
２１０２    分割変換情報
２１０３    モデル変換部
２１０４    処理装置
２１０５    分割部分モデル情報
２１０６    集約部
２１０７    処理装置
２２０１    領域確保装置
２２０２    配列特定部
２２０３    領域確保部
２４２０    計算処理装置
２４２１    ＣＰＵ
２４２２    メモリ
２４２３    ディスク
２４２４    不揮発性記録媒体
２４２５    入力装置
２４２６    出力装置
２４２７    通信ＩＦ
【図１】
2018070376.tif 000003
【図２】
2018070376.tif 000004
【図３】
2018070376.tif 000005
【図４】
2018070376.tif 000006
【図５】
2018070376.tif 000007
【図６】
2018070376.tif 000008
【図７】
2018070376.tif 000009
【図８】
2018070376.tif 000010
【図９】
2018070376.tif 000011
【図１０】
2018070376.tif 000012
【図１１】
2018070376.tif 000013
【図１２】
2018070376.tif 000014
【図１３】
2018070376.tif 000015
【図１４】
2018070376.tif 000016
【図１５】
2018070376.tif 000017
【図１６】
2018070376.tif 000018
【図１７】
2018070376.tif 000019
【図１８】
2018070376.tif 000020
【図１９】
2018070376.tif 000021
【図２０】
2018070376.tif 000022
【図２１】
2018070376.tif 000023
【図２２】
2018070376.tif 000024
【図２３】
2018070376.tif 000025
【図２４】
2018070376.tif 000026
【図２５】
2018070376.tif 000027
【手続補正書】
【提出日】平成31年3月20日(2019.3.20)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
複数要素からなる配列を表す情報を複数含む配列情報のうち、少なくとも一部の前記配列に対応する部分配列情報が表す各前記配列において、所定の値とは異なる値が格納されている要素の位置を表す配列識別子を特定する配列特定手段と、
前記配列特定手段が特定した前記配列識別子の個数を算出し、算出した前記個数に応じた記憶容量を有する記憶領域を確保する領域確保手段と
を備える領域確保装置。
【請求項２】
前記部分配列情報に対して、前記部分配列情報に関する処理を実行する処理装置を割り当てる割り当て手段
をさらに備える請求項１に記載の領域確保装置。
【請求項３】
前記部分配列情報のうち、前記配列特定手段が特定した前記配列識別子が表す配列に含まれている要素を含む小配列情報を作成する行列変換手段
をさらに備える請求項２に記載の領域確保装置。
【請求項４】
前記行列変換手段は、前記配列情報において前記異なる値が格納されている要素の第１位置を表す配列識別子と、前記第１位置の要素に格納されている値が前記小配列情報において格納されている第２位置を表す配列識別子とが関連付けされた変換情報を作成する
請求項３に記載の領域確保装置。
【請求項５】
前記配列特定手段は、前記部分配列情報のうち一部の配列を含むバッチ情報に関して、前記配列識別子を特定し、
前記領域確保手段は、前記バッチ情報に関して前記個数を算出し、算出した該個数に応じて、前記記憶容量を有する記憶領域を確保する
請求項１、または、請求項２に記載の領域確保装置。
【請求項６】
前記割り当て手段は、前記部分配列情報に関して算出された値を集計する処理を、ある処理装置に割り当てる
請求項２乃至請求項４のいずれかに記載の領域確保装置。
【請求項７】
前記変換情報に基づき、前記小配列情報のうち前記異なる値が格納されている要素の位置の第２個数を算出し、前記部分配列情報に関して算出された値を集計する処理に関して、前記第２個数が少ない前記小配列情報に関する処理を実行する前記処理装置から、前記第２個数が多い前記小配列情報に関する処理を実行する前記処理装置に送信するよう通信順序を決定する決定手段
をさらに備える請求項４に記載の領域確保装置。
【請求項８】
前記配列情報に含まれている前記配列において、前記異なる値が格納されている要素の位置を表す前記配列識別子の第３個数を算出し、前記配列を、算出した該第３個数の総計が均等、または、略均等である複数のグループに分類し、前記グループに対して、前記部分配列情報に関して算出された値を集計する処理装置を決定する決定手段
をさらに備える請求項４に記載の領域確保装置。
【請求項９】
情報処理装置によって、複数要素からなる配列を表す情報を複数含む配列情報のうち、少なくとも一部の前記配列に対応する部分配列情報が表す各前記配列において、所定の値とは異なる値が格納されている要素の位置を表す配列識別子を特定し、特定された前記配列識別子の個数を算出し、算出した前記個数に応じた記憶容量を有する記憶領域を確保する領域確保方法。
【請求項１０】
複数要素からなる配列を表す情報を複数含む配列情報のうち、少なくとも一部の前記配列に対応する部分配列情報が表す各前記配列において、所定の値とは異なる値が格納されている要素の位置を表す配列識別子を特定する配列特定機能と、
特定された前記配列識別子の個数を算出し、算出した前記個数に応じた記憶容量を有する記憶領域を確保する領域確保機能と
をコンピュータに実現させる領域確保プログラム。
【国際調査報告】
2018070376.tif 000028
2018070376.tif 000029