(57)【要約】【課題】整合性を保ちつつ、高速に、因子分解を行うことができる。【解決手段】複数のテンソルの各々に基づいて、複数のテンソルを分解して得られる複数の因子行列を頂点とし、同一のテンソルを分解して得られる因子行列の頂点間を辺で結合したグラフを構築する。グラフの各頂点に番号を割り当てることであって、辺で結合された他の頂点とは同じ番号が割り当てられないように、番号を割り当てる。同じ番号が割り当てられた因子行列を、並列処理が可能な因子行列の組とすることにより、因子行列の更新順序を決定し、複数のテンソルに基づいて、更新順序に従って、複数の因子行列を更新することであって、並列処理が可能な因子行列の組を並列に更新することを繰り返す。【選択図】図７
2019220015.tif 000002
【特許請求の範囲】
【請求項１】
属性に対応するモードを軸とする多次元の配列を表現する複数のテンソルの各々を、複数の因子行列に分解する際に、前記テンソルを分解して得られる因子行列の少なくとも１つを、他のテンソルを分解して得られる因子行列と共有するように、前記複数のテンソルの各々を、複数の因子行列に分解する処理装置であって、
前記複数のテンソルの各々に基づいて、前記複数のテンソルを分解して得られる複数の因子行列を頂点とし、同一のテンソルを分解して得られる因子行列の頂点間を辺で結合したグラフを構築し、前記グラフの各頂点に番号を割り当てることであって、辺で結合された他の頂点とは同じ番号が割り当てられないように、前記番号を割り当て、同じ番号が割り当てられた因子行列を、並列処理が可能な前記因子行列の組とすることにより、前記因子行列の更新順序を決定する更新順序決定部と、
前記複数のテンソルに基づいて、前記更新順序に従って、前記複数の因子行列を更新することであって、並列処理が可能な前記因子行列の組を並列に更新することを繰り返すことにより、前記複数のテンソルの各々を、複数の因子行列に分解するテンソル分解部と、
を含む処理装置。
【請求項２】
前記更新順序決定部は、前記グラフのうち、１つのテンソルを分解して得られる複数の因子行列の頂点と、前記複数の因子行列の頂点間の辺で構成される部分グラフごとに、所定の番号から始まる番号を順番に、前記部分グラフの各頂点に異なる番号を割り当てる際に、辺で結合された他の頂点とは同じ番号が割り当てられないように、前記番号を割り当てる請求項１記載の処理装置。
【請求項３】
属性に対応するモードを軸とする多次元の配列を表現する複数のテンソルの各々を、複数の因子行列に分解する際に、前記テンソルを分解して得られる因子行列の少なくとも１つを、他のテンソルを分解して得られる因子行列と共有するように、前記複数のテンソルの各々を、複数の因子行列に分解する処理装置における処理方法であって、
更新順序決定部が、前記複数のテンソルの各々に基づいて、前記複数のテンソルを分解して得られる複数の因子行列を頂点とし、同一のテンソルを分解して得られる因子行列の頂点間を辺で結合したグラフを構築し、前記グラフの各頂点に番号を割り当てることであって、辺で結合された他の頂点とは同じ番号が割り当てられないように、前記番号を割り当て、同じ番号が割り当てられた因子行列を、並列処理が可能な前記因子行列の組とすることにより、前記因子行列の更新順序を決定するステップと、
テンソル分解部が、前記複数のテンソルに基づいて、前記更新順序に従って、前記複数の因子行列を更新することであって、並列処理が可能な前記因子行列の組を並列に更新することを繰り返すことにより、前記複数のテンソルの各々を、複数の因子行列に分解するステップと、
を含む処理方法。
【請求項４】
前記更新順序決定部が決定するステップは、前記グラフのうち、１つのテンソルを分解して得られる複数の因子行列の頂点と、前記複数の因子行列の頂点間の辺で構成される部分グラフごとに、所定の番号から始まる番号を順番に、前記部分グラフの各頂点に異なる番号を割り当てる際に、辺で結合された他の頂点とは同じ番号が割り当てられないように、前記番号を割り当てる請求項３記載の処理方法。
【請求項５】
コンピュータを、請求項１又は請求項２に記載の処理装置の各部として機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、処理装置、方法、及びプログラムに係り、特に、パターンを抽出する因子分解を行うための処理装置、方法、及びプログラムに関する。
【背景技術】
【０００２】
複数の属性情報から要因パターンを抽出する技術として、非負値テンソル因子分解（ＮＴＦ）および非負値複合テンソル因子分解（ＮＭＴＦ）と呼ばれる技術がある（非特許文献１）。ＮＴＦ／ＮＭＴＦでは、まず入力されたテンソルに対応する各因子行列の初期値を乱数等を用いて決める。次に、すべての因子行列を更新式に基づいて更新する処理（因子行列更新処理）を繰り返すことで、各因子行列の値を改善していく。各因子行列を更新する際には、それに関係する他の因子行列を参照する必要があるため、従来技術では各因子行列を逐次的に更新する。
【０００３】
なお、属性情報とは、何らかの事象を１つ以上の属性の組合せとそれに対応する値で表したものである。例えば、人々が商店を訪れたことを、（ユーザＩＤ，店ＩＤ，曜日）の３つの属性と、それに対応する訪問回数や滞在時間で表すことができる。属性情報は、各属性をモードとみなすことでテンソルとして表すことができる。
【０００４】
テンソルとは、以下の説明において多次元の配列と同義とする。例えば３階のテンソルは３次元配列として表現できる。ただし、非負値テンソルとは、テンソルの全ての要素が０以上であるテンソルを指す。
【０００５】
モードとは、テンソルの軸を指す。例えば行列は２階のテンソルとみなせるが、このとき行方向と列方向の２つのモードがある。
【０００６】
因子行列とは、非負値テンソルを因子分解することで得られる行列であり、モードと同じ数だけ存在する。
【先行技術文献】
【非特許文献】
【０００７】
【非特許文献１】Non-negative Multiple Tensor Factorization (K Takeuchi, R Tomioka, K Ishiguro, A Kimura, H Sawada, ICDM, 2013)
【発明の概要】
【発明が解決しようとする課題】
【０００８】
従来の技術（非特許文献１）では、因子行列更新処理において、各因子行列を逐次的に更新していく。つまり、同時に複数の因子行列を更新することはない。これは、ある因子行列を更新するためにはそれに関係する他の因子行列の値を参照する必要があるため、この関係を無視して同時に複数の因子行列を更新してしまうと、計算結果の整合性が取れなくなるためである。
【０００９】
因子行列同士の参照関係が自明であれば、整合性を保ったまま一部の因子行列を同時に更新することができるが、ＮＭＴＦにおいては因子行列の関係が複雑になるため、自明ではない。例えば、３階テンソル１つのＮＴＦでは、３つの因子行列が存在し、各因子行列は自身以外の２つの因子行列を参照するため、同時に更新可能な因子行列の組み合わせがないのは自明である。一方で、ＮＭＴＦでは任意の階数の複数のテンソルが存在し、さらに任意のテンソルの組に対して任意の数の共有因子行列が存在するため、同時に更新可能な因子行列の組み合わせが存在する可能性はあるものの、具体的な組み合わせは自明ではない。
【００１０】
上記の理由から、従来の技術では、処理を実行する装置が複数のＣＰＵコアや並列計算に特化したハードウェアをもつ場合に、１つの因子行列を更新している間に余剰の計算資源を有効に利用して処理時間を短縮することが難しいという課題がある。
【００１１】
本発明は、上記問題点を解決するために成されたものであり、整合性を保ちつつ、高速に、因子分解を行うことができる処理装置、方法、及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１２】
上記目的を達成するために、第１の発明に係る処理装置は、属性に対応するモードを軸とする多次元の配列を表現する複数のテンソルの各々を、複数の因子行列に分解する際に、前記テンソルを分解して得られる因子行列の少なくとも１つを、他のテンソルを分解して得られる因子行列と共有するように、前記複数のテンソルの各々を、複数の因子行列に分解する処理装置であって、前記複数のテンソルの各々に基づいて、前記複数のテンソルを分解して得られる複数の因子行列を頂点とし、同一のテンソルを分解して得られる因子行列の頂点間を辺で結合したグラフを構築し、前記グラフの各頂点に番号を割り当てることであって、辺で結合された他の頂点とは同じ番号が割り当てられないように、前記番号を割り当て、同じ番号が割り当てられた因子行列を、並列処理が可能な前記因子行列の組とすることにより、前記因子行列の更新順序を決定する更新順序決定部と、前記複数のテンソルに基づいて、前記更新順序に従って、前記複数の因子行列を更新することであって、並列処理が可能な前記因子行列の組を並列に更新することを繰り返すことにより、前記複数のテンソルの各々を、複数の因子行列に分解するテンソル分解部と、を含んで構成されている。
【００１３】
また、第１の発明に係る処理装置において、前記更新順序決定部は、前記グラフのうち、１つのテンソルを分解して得られる複数の因子行列の頂点と、前記複数の因子行列の頂点間の辺で構成される部分グラフごとに、所定の番号から始まる番号を順番に、前記部分グラフの各頂点に異なる番号を割り当てる際に、辺で結合された他の頂点とは同じ番号が割り当てられないように、前記番号を割り当てるようにしてもよい。
【００１４】
第２の発明に係る処理方法は、属性に対応するモードを軸とする多次元の配列を表現する複数のテンソルの各々を、複数の因子行列に分解する際に、前記テンソルを分解して得られる因子行列の少なくとも１つを、他のテンソルを分解して得られる因子行列と共有するように、前記複数のテンソルの各々を、複数の因子行列に分解する処理装置における処理方法であって、更新順序決定部が、前記複数のテンソルの各々に基づいて、前記複数のテンソルを分解して得られる複数の因子行列を頂点とし、同一のテンソルを分解して得られる因子行列の頂点間を辺で結合したグラフを構築し、前記グラフの各頂点に番号を割り当てることであって、辺で結合された他の頂点とは同じ番号が割り当てられないように、前記番号を割り当て、同じ番号が割り当てられた因子行列を、並列処理が可能な前記因子行列の組とすることにより、前記因子行列の更新順序を決定するステップと、テンソル分解部が、前記複数のテンソルに基づいて、前記更新順序に従って、前記複数の因子行列を更新することであって、並列処理が可能な前記因子行列の組を並列に更新することを繰り返すことにより、前記複数のテンソルの各々を、複数の因子行列に分解するステップと、を含んで実行することを特徴とする。
【００１５】
第３の発明に係るプログラムは、コンピュータを、第１の発明に係る処理装置の各部として機能させるためのプログラムである。
【発明の効果】
【００１６】
本発明の処理装置、方法、及びプログラムによれば、複数のテンソルの各々に基づいて、複数のテンソルを分解して得られる複数の因子行列を頂点とし、同一のテンソルを分解して得られる因子行列の頂点間を辺で結合したグラフを構築し、グラフの各頂点に番号を割り当てることであって、辺で結合された他の頂点とは同じ番号が割り当てられないように、番号を割り当て、同じ番号が割り当てられた因子行列を、並列処理が可能な因子行列の組とすることにより、因子行列の更新順序を決定し、複数のテンソルに基づいて、更新順序に従って、複数の因子行列を更新することであって、並列処理が可能な因子行列の組を並列に更新することを繰り返すことにより、複数のテンソルの各々を、複数の因子行列に分解することにより、整合性を保ちつつ、高速に、因子分解を行うことができる、という効果が得られる。
【図面の簡単な説明】
【００１７】
【図１】因子行列とテンソルの関係の一例を示す図である。
【図２】ｋ部グラフを説明するための図の一例である。
【図３】ｋ部グラフを説明するための図の一例である。
【図４】ｋ部グラフを説明するための図の一例である。
【図５】ｋ部グラフを説明するための図の一例である。
【図６】ｋ部グラフを説明するための図の一例である。
【図７】本発明の実施の形態に係る処理装置の構成を示すブロック図である。
【図８】入力データ記憶部に記憶されるテンソルの例である。
【図９】更新順序決定部の構成を示すブロック図である。
【図１０】テンソル分解部の構成を示すブロック図である。
【図１１】本発明の実施の形態に係る処理装置における処理ルーチンを示すフローチャートである。
【図１２】因子行列分類部の処理の詳細を示すフローチャートである。
【図１３】部分グラフの頂点に番号を割り当てる場合の一例を示す図である。
【図１４】更新順所出力部の処理の詳細を示すフローチャートである。
【図１５】頂点と更新順序リストの関係を表す図である。
【図１６】行列更新部の処理の詳細を示すフローチャートである。
【発明を実施するための形態】
【００１８】
以下、図面を参照して本発明の実施の形態を詳細に説明する。
【００１９】
＜本発明の実施の形態に係る処理装置の概要＞
【００２０】
まず本発明の実施の形態の前提となる概要を説明する。
【００２１】
図１に示すように、ＮＭＴＦ問題では因子行列とテンソルの関係が複雑なため、計算結果の整合性を維持できる並列な更新手順は自明ではないという問題がある。図１では、テンソルのモードにおけるＡとＢは互いに参照しているため同時に更新できない。同時に更新できる組み合わせは、（Ａ，Ｆ），（Ｂ，Ｄ），（Ｂ，Ｅ），（Ｃ，Ｆ），（Ｄ，Ｆ），（Ｅ，Ｆ）であり、その他は互いに参照しあってしまう。
【００２２】
そこで、本発明の実施の形態では、図２に示す、テンソルと因子行列の関係を一定のルールでグラフ化した、ｋ部グラフを構築して用いることで、上記課題を解決する。ｋ部グラフとは、頂点集合をｋ個の部分集合に分割し、各部分集合内の頂点同士に辺が無いようにできるグラフである。なお、ｋは、ＮＭＴＦ問題を構成するテンソルの最大の階数である。このｋ部グラフの各頂点集合が、同時に更新可能な因子行列の組であり、すべての頂点集合を走査することで，従来技術の更新手順の１ループに相当する処理をより早く行うことができる。図２はｋ部グラフを用いる場合の更新の例である。
【００２３】
次に、ｋ部グラフの詳細について説明する。
【００２４】
まず、図３に示すように、因子行列を頂点、因子行列同士が同一のテンソルを構成するという関係を辺と考えると、ＮＭＴＦ問題はグラフで表現することができる。
【００２５】
次に、図４に示すように、任意のｋ階テンソルに対応する部分グラフに着目すると、ｋ点からなる完全グラフとなる。この部分グラフは同時に、各頂点集合の頂点数が１であるｋ部グラフともいえる。なお、ｋ部グラフは、頂点集合をｋ個の部分集合に分割し、各部分集合内の頂点同士に辺が無いようにできるグラフと捉えられる。
【００２６】
次に、図５に示すように、各部分グラフは、共有因子行列に対応する頂点集合によって連結しているものと考える。これらの頂点集合によって連結しているグラフ全体は、大きい方の頂点数ｋ’についてｋ’部グラフであるといえる。
【００２７】
次に、図６に示すように、ＮＭＴＦ問題が３つ以上のテンソルからなる場合であっても、上記の連結を、すべての部分グラフについて繰り返すと、グラフ全体は、ＮＭＴＦを構成するテンソルの階数のうち最も大きい階数ｋ’について、ｋ’部グラフであるといえることがわかる。
【００２８】
以上のｋ部グラフを用いることによって、同時に更新可能な因子行列の組を発見することができる。
【００２９】
以下、上記の前提を元に、処理装置の具体的な構成について説明する。
【００３０】
本発明の実施の形態の処理装置は、属性に対応するモードを軸とする多次元の配列を表現する複数のテンソルの各々を、複数の因子行列に分解する際に、テンソルを分解して得られる因子行列の少なくとも１つを、他のテンソルを分解して得られる因子行列と共有するように、複数のテンソルの各々を、複数の因子行列に分解する処理装置である。
【００３１】
＜本発明の実施の形態に係る処理装置の構成＞
【００３２】
次に、本発明の実施の形態に係る処理装置の構成について説明する。図７に示すように、本発明の実施の形態に係る処理装置１は、ＣＰＵと、ＲＡＭと、後述する処理ルーチンを実行するためのプログラムや各種データを記憶したＲＯＭと、を含むコンピュータで構成することが出来る。
【００３３】
処理装置１は、機能的には図７に示すように入力データ記憶部１０と、テンソル構築部１１と、更新順序決定部１２と、テンソル分解部１３と、出力データ記憶部１４とを備えている。
【００３４】
入力データ記憶部１０は、因子分解を行う対象の複数の非負値テンソル（以下、単にテンソルと呼ぶ）と、因子分解で用いるパラメータを記憶する。これらは事前に記憶されているものとする。
【００３５】
図８は入力データ記憶部１０に記憶されるテンソルの例である。３つのテンソルＸ，Ｙ，Ｚは、データＸ，Ｙ，Ｚをもとに構築されている。データＸは、属性情報｛Ａ，Ｂ，Ｃ｝によって定められる値を持っており、したがってテンソルＸはモード｛Ａ，Ｂ，Ｃ｝を持ち、それらのモード（属性情報）に対応した値を要素として持つ。テンソルＹ，Ｚも同様である。
【００３６】
ＮＭＴＦ問題を考えるとき、各テンソルは少なくとも１つのモードを他のテンソルと共有する。これは、テンソルの元となる各データが少なくとも１つの属性情報を他のデータと共有することに対応する。
【００３７】
テンソル構築部１１は、入力データ記憶部１０から複数のテンソルを取り出し、ＲＡＭに読み込むことにより、処理装置１において、テンソルを構築する。
【００３８】
更新順序決定部１２は、複数のテンソルの各々に基づいて、複数のテンソルを分解して得られる複数の因子行列を頂点とし、同一のテンソルを分解して得られる因子行列の頂点間を辺で結合したグラフを構築し、グラフの各頂点に番号を割り当てることであって、辺で結合された他の頂点とは同じ番号が割り当てられないように、番号を割り当て、同じ番号が割り当てられた因子行列を、並列処理が可能な因子行列の組とすることにより、因子行列の更新順序を決定する。
【００３９】
更新順序決定部１２は、図９に示すように、因子行列分類部２０と、更新順所出力部２１とを含む。各処理部の詳細な処理は後述する作用において説明する。
【００４０】
因子行列分類部２０は、テンソル構築部１１で読み込んだすべてのテンソルに関係する因子行列を分類する。詳細な処理は作用において後述する。
【００４１】
更新順所出力部２１は、因子行列分類部２０の分類結果に基づいて因子行列の更新順序を出力する。詳細な処理は作用において後述する。
【００４２】
テンソル分解部１３は、図１０に示すように、複数のテンソルに基づいて、更新順序に従って、複数の因子行列を更新することであって、並列処理が可能な因子行列の組を並列に更新することを繰り返すことにより、複数のテンソルの各々を、複数の因子行列に分解する。
【００４３】
テンソル分解部１３は、初期化部３０と、行列更新部３１と、計算終了評価部３２とを含む。
【００４４】
初期化部３０は、テンソルの因子分解に必要な初期化処理を行う。具体的には、テンソルの各モードに対応する因子行列を記憶するための領域をＲＡＭ上に確保し、すべての因子行列のすべての要素に初期値として乱数を代入する。
【００４５】
行列更新部３１は、因子行列の更新式を用いて因子行列を更新する。詳細な処理は作用において後述する。
【００４６】
計算終了評価部３２は、予め定められた終了条件に基づいて、行列更新部３１の因子行列の更新を終了するか、行列更新部３１に戻って再度行列を更新するかを決定する。具体的には、テンソルごとに対応する因子行列から当該テンソルの推定値を計算し、元のテンソルと推定されたテンソルの距離を計算する。テンソルの距離には、一般化ＫＬダイバージェンスを用いることができる。予め定められた終了条件は、テンソルの距離が、予め設定された終了条件を満たすか、計算回数が予め設定された上限に達したときとする。終了条件を満たす場合は更新を終了し、上限に達していななければ行列更新部３１に戻る。
【００４７】
出力データ記憶部１４は、テンソル分解部１３で得られた因子行列を記憶する。
【００４８】
＜本発明の実施の形態に係る処理装置の作用＞
【００４９】
次に、本発明の実施の形態に係る処理装置１の作用について説明する。処理装置１は、図１１のフローチャートに示す処理ルーチンを実行する。
【００５０】
まず、ステップＳ１００では、テンソル構築部１１が、複数のテンソルを読み込むことにより、複数のテンソルを構築する。
【００５１】
次に、ステップＳ１０２では、因子行列分類部２０が、複数のテンソルの各々に基づいて、複数のテンソルを分解して得られる複数の因子行列を頂点とし、同一のテンソルを分解して得られる因子行列の頂点間を辺で結合したグラフを構築し、グラフの各頂点に番号を割り当てることであって、辺で結合された他の頂点とは同じ番号が割り当てられないように、番号を割り当てる。
【００５２】
ステップＳ１０４では、更新順所出力部２１が、同じ番号が割り当てられた因子行列を、並列処理が可能な因子行列の組とすることにより、因子行列の更新順序を決定する。
【００５３】
ステップＳ１０６では、初期化部３０が、テンソルの因子分解に必要な初期化処理を行う。
【００５４】
ステップＳ１０８では、行列更新部３１が、複数のテンソルに基づいて、更新順序に従って、複数の因子行列を更新する。このとき、並列処理が可能な因子行列の組を並列に更新する。
【００５５】
ステップＳ１１０では、計算終了評価部３２が、予め定められた終了条件を満たすか否かを判定し、終了条件を満たす場合には、行列更新部３１の因子行列の更新を終了する。一方、終了条件を満たさない場合には、ステップＳ１０８に戻って再度、因子行列を更新する。
【００５６】
次に、ステップＳ１０２における因子行列分類部２０の処理の詳細を図１２のフローチャートを参照して説明する。
【００５７】
ステップＳ２００では、テンソル構築部１１が構築した複数のテンソルと、当該テンソルを分解して得られる因子行列の各々を読み込む。
【００５８】
ステップＳ２０２では、因子行列を頂点、２つ以上の因子行列が同じテンソルに存在するという関係を辺としたグラフを構築する。グラフは、１つのテンソルを分解して得られる複数の因子行列の頂点と、複数の因子行列の頂点間の辺で構成される部分グラフの各々を組み合わせるように構築する。
【００５９】
図１３の（ａ）は、３つのテンソルとテンソルに関係する因子行列とをグラフ化した場合の例である。
【００６０】
ステップＳ２０４では、各テンソルに対応する部分グラフについて、すべての部分グラフについて処理が終了したかを判定し、処理が終了していれば本処理ルーチンを終了し、処理が終了していなければステップＳ２０６へ移行して処理を繰り返す。
【００６１】
ステップＳ２０６では、部分グラフを選択し、選択した部分グラフの頂点のうち、まだ番号が割り当てられていない頂点に、１から始まり辺で結合された他の頂点と重複しない番号を付与する。部分グラフを選択する順序としては、例えば、まだ一度も部分グラフを選択したことがない場合は、任意の部分グラフを選択し、そうでなければ、すでに選択した部分グラフのいずれかに隣接する部分グラフを選択するという方法を用いることができる。選択した部分グラフに属する複数の頂点が、隣接する複数の部分グラフの選択によってすでに重複する番号を割り当てられているときは、それらの隣接する部分グラフにおいて、重複が解消するように番号を入れ替えることもできる。
【００６２】
図１３の（ｂ）〜（ｄ）は、部分グラフごとにその頂点に番号を割り当てていく様子を表した例である。（ｂ）で、テンソルＹに対応する部分グラフの頂点Ａ，Ｅ，Ｄ，Ｃに１〜４の番号を割り当てる。
【００６３】
次に（ｃ）で、テンソルＸに対応する部分グラフの頂点Ａ，Ｃ，Ｂに番号を割り当てるが、Ａ，Ｃにはすでに１，４が割り当てられているため、Ｂに１から始まり重複しない番号として２を割り当てる。最後に（ｄ）で、テンソルＺに対応する部分グラフの頂点Ｂ，Ｆに番号を割り当てるが、Ｂにはすでに２が割り当てられているため、Ｆに１から始まり重複しない番号として１を割り当てる。
【００６４】
以上が因子行列分類部２０の処理の詳細である。上記のように、部分グラフごとに、所定の番号から始まる番号を順番に、部分グラフの各頂点に異なる番号を割り当てる際に、辺で結合された他の頂点とは同じ番号が割り当てられないように、番号を割り当てる。なお、所定の番号は１から始まる番号に限定されるものでなく、０から始まる番号などでも良い。
【００６５】
次に、ステップＳ１０４における更新順所出力部２１の処理の詳細を図１４のフローチャートを参照して説明する。
【００６６】
ステップＳ３００では、因子行列分類部２０からグラフを読み込む。
【００６７】
ステップＳ３０２では、グラフの頂点に付与された各番号について、すべての番号について処理が終了したかを判定し、処理が終了していれば本処理ルーチンを終了し、処理が終了していなければステップＳ３０４へ移行して処理を繰り返す。
【００６８】
ステップＳ３０４では、番号を選択し、同じ番号が付与されたすべての頂点を列挙し、更新順序リストＬに追加する。
【００６９】
図１５の（ａ）は、各番号について頂点を列挙した例である。図１５の（ｂ）のようにこの更新順序リストＬを順に読んでいくと、因子行列の組み合わせ｛Ａ，Ｆ｝，｛Ｂ，Ｅ｝がそれぞれ並列処理によって同時に更新できることがわかる。
【００７０】
次に、ステップＳ１０４における行列更新部３１の処理の詳細を図１６のフローチャートを参照して説明する。
【００７１】
ステップＳ４００では、ｉ＝０とｉを設定する。
【００７２】
ステップＳ４０１では、更新順序リストＬから、更新順序リストＬの要素である因子行列の組み合わせｌｉを選択する。
【００７３】
ステップＳ４０２では、更新順序リストＬの全ての組み合わせを処理したかを判定し、処理していれば本処理ルーチンを終了し、処理していなければステップＳ４０４へ移行して処理を繰り返す。ｉがＬの大きさ以上であれば本処理ルーチンを終了し、Ｌの大きさ未満であればステップＳ４０４へ移行する。
【００７４】
ステップＳ４０４では、ｌｉに含まれる各因子行列について、並列処理が可能な因子行列の組を並列で処理するように更新処理を実行する。図１５の（ａ）の更新順序リストＬを例とすると、ｌ１＝｛Ａ，Ｆ｝については因子行列Ａ，Ｆについて更新処理を並列に行う。同様に、ｌ２＝｛Ｂ，Ｅ｝については因子行列Ｂ，Ｅを並列に処理する。ｌ３＝｛Ｄ｝，ｌ４＝｛Ｃ｝については因子行列がそれぞれ１つのみであるため、因子行列Ｄ，Ｃを並列に処理することはない。
【００７５】
例えば、テンソルＡ（０）を因子行列Ｔ，Ｕ，Ｖに分解する際には、更新対象の因子行列Ｔの各要素ｔは以下（１）式の更新式に基づいて更新される。
【００７６】
【数１】
2019220015.tif 000003
・・・（１）
【００７７】
（１）式は、テンソル間の距離として一般化ＫＬダイバージェンスを用いるときの、因子行列Ｔの要素ｔｉｒを更新するための更新式である。ｔｉｒは因子行列ｔのｉ行目ｒ列目の要素を表し、ａｉ，ｊ，ｋ（ｎ）はｔがそのモードの因子行列となるようなｎ番目のテンソルの要素を表す。＾ａｉ，ｊ，ｋ（ｎ）はｎ番目のテンソルの要素の推定値を表す。ｕ（ｎ），ｖ（ｎ）はｎ番目のテンソルのｔ以外の因子行列を表す。テンソルは簡略化のために１個の３階テンソルと仮定しているが、個数は１以上、階数は２以上の任意の数をとりうる。この更新式の詳細は非特許文献１で示されている。
【００７８】
ステップＳ４０６では、ｉ＝ｉ＋１とし、ステップＳ４０２に戻る。
【００７９】
以上説明したように、本発明の実施の形態に係る処理装置によれば、複数のテンソルの各々に基づいて、複数のテンソルを分解して得られる複数の因子行列を頂点とし、同一のテンソルを分解して得られる因子行列の頂点間を辺で結合したグラフを構築し、グラフの各頂点に番号を割り当てることであって、辺で結合された他の頂点とは同じ番号が割り当てられないように、番号を割り当て、同じ番号が割り当てられた因子行列を、並列処理が可能な因子行列の組とすることにより、因子行列の更新順序を決定し、複数のテンソルに基づいて、更新順序に従って、複数の因子行列を更新することであって、並列処理が可能な因子行列の組を並列に更新することを繰り返すことにより、複数のテンソルの各々を、複数の因子行列に分解することにより、整合性を保ちつつ、高速に、因子分解を行うことができる。
また、以上本発明の実施の形態に係る手法のポイントは、１点目は、入力されたテンソルから、それらのテンソルと因子行列の関係性を表すグラフを構築し、構築したグラフを所定のアルゴリズムで探索することで、並列に更新可能な因子行列の組み合わせを決定する手法を用いることである。２点目は、当該手法がテンソルの数、各テンソルの階数、及び因子行列の共有関係に依存しないことである。
【００８０】
１点目については、テンソルと因子行列の関係性を所定のルールに基づいてグラフ化することで、因子行列間の参照関係を容易に探索可能な形で明確化し、さらにこのグラフを所定のアルゴリズムに基づいて探索することで、互いに参照しない、すなわち同時に更新を行っても整合性を維持できる因子行列の組み合わせを決定できる。
【００８１】
２点目については、１点目の手法がテンソルの数、各テンソルの階数、因子行列の共有関係に依存しないことから、大規模な問題や、ＮＭＴＦの特殊例であるＮＭ２Ｆ（非負値複合行列因子分解）にも適用可能である。さらに、上述した処理装置１の構成によって、一つのテンソルしか扱わない特殊例、例えば、ＮＴＦ（非負値テンソル因子分解）、ＮＭＦ（非負値行列因子分解）も処理することができる。
【００８２】
なお、本発明は、上述した実施の形態に限定されるものではなく、この発明の要旨を逸脱しない範囲内で様々な変形や応用が可能である。
【符号の説明】
【００８３】
１     処理装置
１０   入力データ記憶部
１１   テンソル構築部
１２   更新順序決定部
１３   テンソル分解部
１４   出力データ記憶部
２０   因子行列分類部
２１   更新順所出力部
３０   初期化部
３１   行列更新部
３２   計算終了評価部
【図１】
2019220015.tif 000004
【図２】
2019220015.tif 000005
【図３】
2019220015.tif 000006
【図４】
2019220015.tif 000007
【図５】
2019220015.tif 000008
【図６】
2019220015.tif 000009
【図７】
2019220015.tif 000010
【図８】
2019220015.tif 000011
【図９】
2019220015.tif 000012
【図１０】
2019220015.tif 000013
【図１１】
2019220015.tif 000014
【図１２】
2019220015.tif 000015
【図１３】
2019220015.tif 000016
【図１４】
2019220015.tif 000017
【図１５】
2019220015.tif 000018
【図１６】
2019220015.tif 000019