(57)【要約】【課題】スパーステンソルの因子分解のための処理を高速化するとともに、処理の際に必要とするメモリ量を削減する。【解決手段】  Ｎ次元（Ｎは３以上の整数）のテンソルデータに対し、当該テンソルデータの複数インデックスについてのループ計算を行うテンソルデータ計算装置において、計算ループの最下位のインデックスから最上位の１つ前までの各インデックスの順で各インデックスのループ方向順となるようにテンソルデータの要素の順番付けを行い、当該順番付けに従って、テンソルデータ中の空でない要素について、当該要素の値と、当該要素のテンソルデータ上の位置を示す最下位のインデックスから最上位の１つ前までのインデックスのインデックス値とをデータ記憶部上に配置するとともに、当該空でない要素のカウント数を配置する処理を行うデータ配置処理手段と、前記データ記憶部上に配置されたテンソルデータに対するループ計算を行う計算処理手段とを備える。【選択図】図５
2016139391.tif 000002
【特許請求の範囲】
【請求項１】
Ｎ次元（Ｎは３以上の整数）のテンソルデータに対し、当該テンソルデータの複数インデックスについてのループ計算を行うテンソルデータ計算装置であって、
計算ループの最下位のインデックスから最上位の１つ前までの各インデックスの順で各インデックスのループ方向順となるようにテンソルデータの要素の順番付けを行い、当該順番付けに従って、テンソルデータ中の空でない要素について、当該要素の値と、当該要素のテンソルデータ上の位置を示す最下位のインデックスから最上位の１つ前までのインデックスのインデックス値とをデータ記憶部上に配置するとともに、当該空でない要素のカウント数を算出して前記データ記憶部に配置する処理を、計算ループの最上位のインデックスの順番毎に当該インデックスの順番数だけ実行するデータ配置処理手段と、
前記データ配置処理手段により前記データ記憶部上に配置されたテンソルデータに対するループ計算を行う計算処理手段と
を備えることを特徴とするテンソルデータ計算装置。
【請求項２】
前記計算処理手段は、前記テンソルデータに対するループ計算により、当該テンソルデータの因子分解を実行する
ことを特徴とする請求項１に記載のテンソルデータ計算装置。
【請求項３】
前記計算処理手段は、前記因子分解の最適値を推定するための更新式におけるインデックスの依存関係に応じて、ループ計算を分離して実行する
ことを特徴とする請求項２に記載のテンソルデータ計算装置。
【請求項４】
Ｎ次元（Ｎは３以上の整数）のテンソルデータに対し、当該テンソルデータの複数インデックスについてのループ計算を行うテンソルデータ計算装置が実行するテンソルデータ計算方法であって、
計算ループの最下位のインデックスから最上位の１つ前までの各インデックスの順で各インデックスのループ方向順となるようにテンソルデータの要素の順番付けを行い、当該順番付けに従って、テンソルデータ中の空でない要素について、当該要素の値と、当該要素のテンソルデータ上の位置を示す最下位のインデックスから最上位の１つ前までのインデックスのインデックス値とをデータ記憶部上に配置するとともに、当該空でない要素のカウント数を算出して前記データ記憶部に配置する処理を、計算ループの最上位のインデックスの順番毎に当該インデックスの順番数だけ実行するデータ配置処理ステップと、
前記データ配置処理ステップにより前記データ記憶部上に配置されたテンソルデータに対するループ計算を行う計算処理ステップと
を備えることを特徴とするテンソルデータ計算方法。
【請求項５】
前記計算処理ステップにおいて、前記テンソルデータ計算装置は、前記テンソルデータに対するループ計算により、当該テンソルデータの因子分解を実行する
ことを特徴とする請求項４に記載のテンソルデータ計算方法。
【請求項６】
前記計算処理ステップにおいて、前記テンソルデータ計算装置は、前記因子分解の最適値を推定するための更新式におけるインデックスの依存関係に応じて、ループ計算を分離して実行する
ことを特徴とする請求項５に記載のテンソルデータ計算方法。
【請求項７】
コンピュータを、請求項１ないし３のうちいずれか１項に記載のテンソルデータ計算装置における各手段として機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数の属性情報から要因パターンを抽出する因子分解に関する技術であり、特に、非負値テンソル因子分解技術に関連する。
【背景技術】
【０００２】
購買ログやチェックインログなど、一般的にログデータはテンソルとして表現することが可能である。またそのようなデータは正の実数値で表現されるため、テンソルとして表現されたデータは非負値テンソル因子分解（Ｎｏｎｎｅｇａｔｉｖｅ  Ｔｅｎｓｏｒ  Ｆａｃｔｏｒｉｚａｔｉｏｎ）手法を用いて因子分析を行うことが可能である。しかしながら、ログデータ分析手法として、因子分解技術は広く用いられている一方、非常に計算時間がかかるという問題を抱えている。なお、例えば非特許文献１には、一般的な因子分解手法についての技術が記載されている。
【０００３】
ユーザが複数の商品の購買を行い、そのようなデータが数日間分存在する例を考える。一般的には「ユーザｘ商品ｘ日」の３次のテンソルデータとして表現し、Ｒ（Ｒａｎｋ）個の基底に分解を行う。この時、ユーザ数（Ｉ）、商品数（Ｊ）、日数（Ｋ）とすると、当該テンソルはサイズ（ＩｘＪｘＫ）のテンソルとして表現され、因子分解の計算量は（ＩｘＪｘＫｘＲ）に比例する。例えば、１０００人のユーザが、１０００種類のアイテムから購買を行い、そのようなデータが１０００日間蓄積され、１００個の基底に分解を行う時、その計算量は一回の反復計算に１０００億回規模の演算処理を行わなければならない。通常反復計算を１０００回ほど行うとして、１００兆回規模の演算処理を行い、その計算は近年の汎用コンピュータを用いると数日かかる。
【０００４】
また、テンソルデータを保持するためのメモリ領域は（ＩｘＪｘＫ）のオーダ量が必要になり、前述の規模でも数ＧＢのメモリを要する。従って、大規模なデータ（ユーザ数や商品数の増加）では物理的計算ができなくなる。
【０００５】
ここで、非負値テンソル因子分解の計算例について説明する。非負値テンソル因子分解では、非負性を保って、テンソルデータを因子行列のテンソル積に分解する。例えば図１に示すように、「ユーザ［Ｉ］ｘ商品［Ｊ］ｘ日［Ｋ］」の３次のテンソルデータＸは３個の因子行列Ａ、Ｂ、Ｃに分解することができ、下記の式のように表すことができる。
【０００６】
【数１】
2016139391.tif 000003
なお、本明細書のテキストでは、便宜上、テンソル積の記号を＊と表すことにする。また、本明細書のテキストでは、推定量を示すハット"＾"の記号を、便宜上、文字の頭上でなく、文字の直前に記載する。例えば、"＾Ｘ"のようにである。
【０００７】
上記のＡ、Ｂ、ＣはそれぞれＩｘＲ、ＪｘＲ、ＫｘＲの非負値の行列であり、テンソル積＊は下記のように各基底の積で表される。
【０００８】
【数２】
2016139391.tif 000004
上記のテンソルデータＸと、Ａ＊Ｂ＊Ｃが近似的に等しくなるように、Ａ、Ｂ、Ｃを求める手法がテンソル因子分解である。この時、＾Ｘ＝Ａ＊Ｂ＊Ｃとして、Ｄ（Ｘ｜｜＾Ｘ）を最小化させる。Ｄ（・）は距離関数であり、一般化ＫＬダイバージェンス（ｇＫＬ）距離では以下のように表される。
【０００９】
【数３】
2016139391.tif 000005
距離関数をｇＫＬとした時、因子分解の最適値を推定するための更新式は下記のようになる。
【００１０】
【数４】
2016139391.tif 000006
【００１１】
【数５】
2016139391.tif 000007
更新式を何回か繰り返し適用することで、因子分解後のＡ、Ｂ、Ｃが得られる。図２は、例として因子行列Ａの更新処理手順を示している。図２に示すように、ａｉｒの更新では、ａｉｒ自体についてＩｘＲのループ処理が必要となり、ａｉｒの値を求めるためにＪｘＫのループ処理が必要となる。従って、最終的にＩｘＪｘＫｘＲ回のループ処理が必要になる。また、＾Ｘｉｊｋ、ｂｊｋ、ｃｋｒの値を求めるためにも同様の処理回数が要求される。
【先行技術文献】
【非特許文献】
【００１２】
【非特許文献１】Liu, Weixiang, Tianfu Wang, and Siping Chen. "Nonnegative tensor factorization for clustering genes with time series microarrays from different conditions: A case study." Biomedical Engineering and Informatics (BMEI), 2010 3rd International Conference on. Vol. 6. IEEE, 2010.
【発明の概要】
【発明が解決しようとする課題】
【００１３】
一般的に多くのテンソルデータは値を持たない要素が多く、データ構造が疎である場合が多い（疎であることをここではスパースであるという表現を使う）。例えば、購買ログでは、全てのユーザが全ての商品を購入するわけではなく、テンソルの要素では「０」として意味のない値として扱われる事が多い。具体的な例としては、ユーザ毎にデータ収集期間が異なる場合や収集データの一部に欠損がある場合などは欠損値として扱う「欠損値スパーステンソル」があり、ユーザが意図的に購入しない場合（男性が女性用の下着を購入しないなど）などは０値として扱う「０値スパーステンソル」があり、いずれも因子分解の更新式において計算不要な要素を省略し、計算が必要な要素のみを演算処理することによって高速に計算が可能となる。
【００１４】
例えばログ数Ｌとした場合の欠損値スパーステンソルの更新式は以下のようになり、因子行列Ａの更新手順は図３に示すようになる。
【００１５】
【数６】
2016139391.tif 000008
【００１６】
【数７】
2016139391.tif 000009
図３に示すように、ａｉｒの更新では、ａｉｒ自体に対するＩｘＲのループ処理が必要ではあるが、ａｉｒの値を求めるためにＪｘＫのループ処理は行わず、ｉに対するｊ，ｋのログ数Ｌｉの処理回数でよく、最終的にＬｘＲ回のループ処理でよい。＾Ｘｉｊｋ、ｂｊｋ、ｃｋｒの値を求めるためにも同様の処理回数でよく、スパースなデータ構造では計算の処理回数はＬｘＲ回に比例する。よって、計算量を大幅に削減することが可能である。また、物理的なメモリ量も（Ｌ）のオーダとなり、汎用ＰＣによる処理が可能となる。
【００１７】
また、例えば、０値スパーステンソルの更新式は以下のようになり、因子行列Ａの更新手順は図４に示すようになる。
【００１８】
【数８】
2016139391.tif 000010
ここで、図４に示すように、０値スパーステンソルの更新手順においては、分母を分子とは別のループで処理をしている。すなわち、ａｉｒの更新では、「数８」に示すように分母はｉに非依存な値のため、分母をｉに関してのＩ回のループ処理の外に出すことができる。分母はｒに依存するため、ｒ個のデータ配列で取得しておくことによって分母の計算量は（Ｊ＋Ｋ）ｘＲ回に比例する程度に抑えることが可能である。ｂｊｋ、ｃｋｒの値を求めるためにも同様に、分母と分子を切り分けて計算することが可能であり、その結果、分母の計算量が（（Ｉ＋Ｊ＋Ｋ）ｘＲ）のオーダになり、分子の計算量が（ＬｘＲ）のオーダになる。しかしながら、一般的にはＩ，Ｊ，Ｋはログ数Ｌと比較して十分小さな値になるため、全体の計算量に対して分母の計算量は無視できるオーダになり、欠損値スパーステンソルの計算量と同程度のものになる。また、物理的なメモリ量も（Ｌ）のオーダとなり、汎用ＰＣによる処理が可能である。
【００１９】
しかしながら、いずれの例の場合でも、スパースな非負値テンソル因子分解は原理的に計算量を削減することが可能である一方、行列因子分解法と異なりデータ構造の複雑性から効果的な高速化手法が確立されていない。特に、単純にデータ構造を保持しただけではメモリのランダムアクセスが発生し、大規模な処理では処理が遅くなる。
【００２０】
本発明は上記の点に鑑みてなされたものであり、スパーステンソルの因子分解のための処理を高速化するとともに、処理の際に必要とするメモリ量とメモリアクセス通信量を削減する技術を提供することを目的とする。
【課題を解決するための手段】
【００２１】
本発明の実施の形態により、Ｎ次元（Ｎは３以上の整数）のテンソルデータに対し、当該テンソルデータの複数インデックスについてのループ計算を行うテンソルデータ計算装置であって、
計算ループの最下位のインデックスから最上位の１つ前までの各インデックスの順で各インデックスのループ方向順となるようにテンソルデータの要素の順番付けを行い、当該順番付けに従って、テンソルデータ中の空でない要素について、当該要素の値と、当該要素のテンソルデータ上の位置を示す最下位のインデックスから最上位の１つ前までのインデックスのインデックス値とをデータ記憶部上に配置するとともに、当該空でない要素のカウント数を算出して前記データ記憶部に配置する処理を、計算ループの最上位のインデックスの順番毎に当該インデックスの順番数だけ実行するデータ配置処理手段と、
前記データ配置処理手段により前記データ記憶部上に配置されたテンソルデータに対するループ計算を行う計算処理手段と
を備えることを特徴とするテンソルデータ計算装置が提供される。
【００２２】
また、本発明の実施の形態により、Ｎ次元（Ｎは３以上の整数）のテンソルデータに対し、当該テンソルデータの複数インデックスについてのループ計算を行うテンソルデータ計算装置が実行するテンソルデータ計算方法であって、
計算ループの最下位のインデックスから最上位の１つ前までの各インデックスの順で各インデックスのループ方向順となるようにテンソルデータの要素の順番付けを行い、当該順番付けに従って、テンソルデータ中の空でない要素について、当該要素の値と、当該要素のテンソルデータ上の位置を示す最下位のインデックスから最上位の１つ前までのインデックスのインデックス値とをデータ記憶部上に配置するとともに、当該空でない要素のカウント数を算出して前記データ記憶部に配置する処理を、計算ループの最上位のインデックスの順番毎に当該インデックスの順番数だけ実行するデータ配置処理ステップと、
前記データ配置処理ステップにより前記データ記憶部上に配置されたテンソルデータに対するループ計算を行う計算処理ステップと
を備えることを特徴とするテンソルデータ計算方法が提供される。
【発明の効果】
【００２３】
本発明の実施の形態によれば、スパーステンソルの因子分解のための処理を高速化するとともに、処理の際に必要とするメモリ量とメモリアクセス通信量を削減する技術が提供される。
【図面の簡単な説明】
【００２４】
【図１】非負値テンソル因子分解の例を示す図である。
【図２】密テンソルにおける因子行列Ａの更新処理手順を示す図である。
【図３】欠損値スパーステンソルにおける因子行列Ａの更新処理手順を示す図である。
【図４】０値スパーステンソルにおける因子行列Ａの更新処理手順を示す図である。
【図５】本発明の実施の形態におけるテンソルデータ計算装置の構成図である。
【図６】テンソルデータのデータ構造のイメージを示す図である。
【図７】テンソルデータを３次の配列で保持する場合における密テンソルの因子行列Ａの更新処理手順を示す図である。
【図８】テンソルデータを３次の配列で保持する場合における欠損値スパーステンソルの因子行列Ａの更新処理手順を示す図である。
【図９】テンソルデータを３次の配列で保持する場合における０値スパーステンソルの因子行列Ａの更新処理手順を示す図である。
【図１０】因子行列Ａに関し、ｉを固定して、ｊ毎に因子行列展開を行うことを説明するための図である。
【図１１】ユーザ１に対して必要な情報を示す図である。
【図１２】因子行列Ａの更新のために保持するデータを示す図である。
【図１３】因子行列Ｂ、因子行列Ｃにおける軸の取り方の例を説明するための図である。
【図１４】因子行列Ｂの更新のために保持するデータを示す図である。
【図１５】各因子行列の更新のためのデータを示す図である。
【図１６】軸毎の疎行列を用意する効果を説明するための図である。
【図１７】高次のテンソルへの拡張を示す図である。
【図１８】因子行列Ｚｋの更新のために保持するデータを示す図である。
【発明を実施するための形態】
【００２５】
以下、図面を参照して本発明の実施の形態を説明する。なお、以下で説明する実施の形態は一例に過ぎず、本発明が適用される実施の形態は、以下の実施の形態に限られるわけではない。
【００２６】
（装置構成）
図５に本発明の実施の形態に係るテンソルデータ計算装置１０の構成を示す。テンソルデータ計算装置１０は、テンソルデータの入力を受けて、非負値テンソル因子分解を行って、結果としての因子行列のデータを出力する装置である。図５に示すように、テンソルデータ計算装置１０は、データ入力部１１、データ配置処理部１２、データ記憶部１３、テンソル因子分解処理部１４、及びデータ出力部１５を有する。
【００２７】
データ入力部１１はテンソルデータを受信し、当該テンソルデータをデータ配置処理部１２に渡す。データ配置処理部１２は、テンソルデータを疎行列化して、後に詳細に説明するデータ構造でテンソルデータをデータ記憶部１３（メモリ等）に格納（配置）する。テンソル因子分解処理部１４は、データ記憶部１３に配置されている上記データ構造のテンソルデータに対し、非負値テンソル因子分解の処理を行って、処理結果である因子行列のデータをデータ出力部１５に渡し、データ出力部１５は当該データを出力する。
【００２８】
本実施の形態に係るテンソルデータ計算装置１０は、コンピュータに、本実施の形態で説明する処理内容を記述したプログラムを実行させることにより実現可能である。すなわち、テンソルデータ計算装置１０が有する機能は、当該コンピュータに内蔵されるＣＰＵやメモリ、ハードディスクなどのハードウェア資源を用いて、テンソルデータ計算装置１０で実施される処理に対応するプログラムを実行することによって実現することが可能である。また、上記プログラムは、コンピュータが読み取り可能な記録媒体（可搬メモリ等）に記録して、保存したり、配布したりすることが可能である。また、上記プログラムをインターネットや電子メールなど、ネットワークを通して提供することも可能である。
【００２９】
以下、テンソルデータ計算装置１０における処理をより詳細に説明する。以下では、特にデータ配置処理部１２により実行される処理を詳細に説明する。以下では、まず、図１に示したような、３次のテンソルデータを３個の因子行列Ａ、Ｂ、Ｃに分解する場合を例として説明する。その後に、Ｎ次（Ｎは３以上の整数）に拡張する例を説明する。
【００３０】
（テンソルデータ構造）
まず、テンソルデータ計算装置１０が扱う一般的なテンソルデータ構造について説明する。テンソルデータ計算装置１０では、高次のテンソルデータはプログラム処理上配列として格納して扱う。例えば、３次のテンソルデータＸｉｊｋをＸ［Ｉ］［Ｊ］［Ｋ］という３次の配列で保持する。この場合のデータ構造のイメージは図６に示すとおりである。
【００３１】
当該データ構造において、因子分解のための、通常の密行列の更新処理では、上記のとおり３次のテンソルデータをＸ［Ｉ］［Ｊ］［Ｋ］という３次の配列で保持し、図７に示すように、４重ループによる処理を行う。しかしながら、前述したように、密テンソルの処理には、計算量が大きくなり、必要とするメモリ領域も大きくなるという問題がある。
【００３２】
本実施の形態では、スパースなテンソルデータを対象としており、その場合、前述したとおり、因子分解の更新式において計算不要な要素を省略し、計算が必要な要素のみを演算処理することによって高速に計算を可能とする。
【００３３】
この場合の因子行列Ａの更新処理手順は図８及び図９に示すとおりである。当該更新処理は、テンソルデータ計算装置１０のテンソル因子分解処理部１４により実行されるものである。図８に示すとおり、欠損値スパースデータの場合、例えばａｉｒの更新では、ａｉｒ自体に対してＩｘＲのループ処理を行い、ｊ、ｋの組み合わせに関しては、ｉに対するｊ、ｋのログ数Ｌｉの処理ループを回す計算を行う。図９は、０値スパースデータの場合における因子行列Ａの更新処理手順を示す。図４を参照して既に説明したとおり、０値スパースデータの場合、因子分解の最適値を推定するための更新式におけるインデックスの依存関係に応じて、ループ計算を分離して実行している。具体的には、分母の計算処理に係るループ計算と、分子の計算処理に係るループ計算とを分離して実行している。最も計算量のかかる処理は分子の値の計算であり、分子の計算処理に関しては欠損値スパーステンソルと同様の計算を行う。すなわち、分子の計算処理において、例えばａｉｒの更新では、ａｉｒ自体に対してＩｘＲのループ処理を行い、ｊ、ｋの組み合わせに関しては、ｉに対するｊ、ｋのログ数Ｌｉの処理ループを回す計算を行う。分母に関しては、図９に示すとおり、Ｊ回のループ処理とＫ回のループ処理とをＲ回行う。前述したように、全体の計算量に対して分母の計算量は無視できるオーダである。
【００３４】
この時、各ｉにおけるｊ、ｋ、ｌの組み合わせ情報の保持が必要となる。図８及び図９では、当該情報は、Ａで示されるように、各指標データ（ｉｎｄｅｘ＿ｊ，ｉｎｄｅｘ＿ｋ，ｉｎｄｅｘ＿ｌ）としてデータ記憶部１３に配置される。また、Ｘｉｊｋと＾Ｘｉｊｋについては、ベクトル、もしくは同様な指標としてデータ記憶部１３に保持しておく。因子行列Ｂ、Ｃについても同様のデータをデータ記憶部１３に配置しておく。
【００３５】
本実施の形態では、これら指標のデータを、データ配置処理部１２により、更新処理を効率良く実行可能ならしめるデータ構造としてデータ記憶部１３に配置しておくことにより、テンソル因子分解処理部１４により実行されるスパーステンソルの行列更新を高速に実施することを可能としている。
【００３６】
以下では、本実施の形態において、データ記憶部１３に配置されるデータをより詳細に説明する。以下で説明する処理は、欠損値スパーステンソルの場合と０値スパーステンソルの場合とで共通である。ただし、以下で説明する処理は、欠損値スパーステンソルの場合は分母と分子の計算処理に関連し、０値スパーステンソルの場合は分子の計算処理に関連する。
【００３７】
（テンソルデータの疎行列化：因子行列Ａを例とした説明）
図８及び図９の更新手順に示したように、因子行列Ａに関しては、ｉ毎の要素で更新を行う。当該更新のループ計算において、ｉが最上位のインデックスである。
【００３８】
本実施の形態では、ｉを固定して、ｊ毎に行列展開を行うことで、テンソルデータの疎行列化を行う。すなわち、テンソルデータ計算装置１０のデータ配置処理部１２は、図１０（ａ）に示すようなテンソルデータを、図１０（ｂ）に示すように、ｉを固定して、ｊ毎の行列に展開する。本実施の形態では、これをテンソルデータの疎行列化と呼んでいる。なお、ここでのポイントは、ｊ毎に展開を行うことではなくて、ｉを固定することである。
【００３９】
図１０（ｂ）に示すとおり、展開した結果において、ｉ＝１では、
ｉ＝１，  ［６，０，２，４，０，０，０，０，０，１，２，０，０，０，０，２］
というベクトルができる。スパーステンソルでは０要素は処理が不要であるため、データ配置処理部１２は必要な要素の情報のみをデータ記憶部１３に配置する。当該情報を図１１において、Ｘｉｊｋとして示す。
【００４０】
また、このとき、ｊ、ｋの情報が必要なため当該情報を別途保持する。当該情報は、図１１において（ｊ，ｋ）として示されている。例えば、ユーザ１のログデータ値６は、（ｊ，ｋ）＝（１，１）に対応することが示されている。また、図１１には、更新処理上持つ必要がある情報として＾Ｘｉｊｋの値の例が示されている。当該値は、因子行列の更新に伴って順次更新されていく値である。
【００４１】
なお、上記ｋは、計算ループの最下位のインデックスであり、上記ｊは、最上位の１つ前のインデックスである。
【００４２】
上記のとおり、因子行列ＡはＩに関しての因子分解であり、更新処理はｉに関して行うため、データ配置処理部１２は、因子行列Ａに関して、各ｉのログ数、各ｉに関する（ｊ，ｋ）の組み合わせ、Ｘｉｊｋの値、＾Ｘｉｊｋの値をデータ記憶部１３に配置する。
【００４３】
最終的に因子行列Ａの更新のために、図１２（ａ）〜（ｃ）に示すデータをデータ記憶部１３に配置する。（ｃ）の＾Ｘｉｊｋは空欄になっているが、これは、計算結果を格納するメモリ領域として予め用意することを意味する。ここで、（ｊ，ｋ）の組み合わせを格納する疎行列データ（図１２の（ｂ））をインデックス疎行列と呼ぶ。
【００４４】
因子行列Ａについて、上記のようなインデックス疎行列等を保持しておき、図８及び図９に示した手順で更新処理を行うのである。このように、スパーステンソルを疎行列表現に置き換えて処理を行うことで、処理の高速化、及びメモリ使用量の低減を図る事が可能である。
【００４５】
上記のようなデータ配置を行う際に、データ配置処理部１２は、計算ループの最下位のインデックス（例：ｋ）から最上位の１つ前までの各インデックス（例：ｊ）の順で各インデックスのループ方向順となるようにテンソルデータの要素の順番付けを行い、当該順番付けに従って、テンソルデータ中の空でない要素について、当該要素の値（例：Ｘｉｊｋ）と、当該要素のテンソルデータ上の位置を示す最下位のインデックスから最上位の１つ前までのインデックスのインデックス値（例：（ｊ，ｋ）の値）とをデータ記憶部１３上に配置するとともに、当該空でない要素のカウント数（Ｌｉ）を算出して前記データ記憶部１３に配置する処理を、計算ループの最上位のインデックスの順番毎（例：ｉ＝１，２，３，４の順番）に当該インデックスの順番数（例：ｉ＝１，２，３，４の場合、４）だけ実行する。
【００４６】
なお、上記の「計算ループの最下位のインデックス（例：ｋ）から最上位の１つ前までの各インデックス（例：ｊ）の順で各インデックスのループ方向順となるように順番付けする」とは、例えば、図１０（ｂ）と図１２（ｂ）の各ｉの行の（ｊ，ｋ）について、（ｉ＝１ではｊ＝１，ｋ＝１からＬ１＝６なので６個を並べる），（ｉ＝２では、ｊ＝１，ｋ＝２からＬ２＝４なので４個を並べる）...のように順番付けすることである。
【００４７】
上記のようなデータ配置を行うことで、更新のための計算ループを実行する際は、要素のカウント数（Ｌｉ）だけインデックスおよび要素値を参照すればよく、空の要素を参照する必要がなくなるため、計算処理を効率化できるとともにメモリを効率的に利用可能となる。また、空でない要素の値にアクセスする際も、インデックスのループの最下位から最上位の順に従ってメモリ上で順次アクセスすることが可能となるため、ランダムアクセスが解消し、メモリアクセススピードを高速化できる効果を奏する。
【００４８】
（テンソルデータの疎行列化：因子行列Ｂ、Ｃに関して）
これまでに説明したとおり、因子行列Ａに対してはＩ方向に疎行列の行を取っている。因子行列Ｂに対しては、Ｊ方向を疎行列の行にするために、図１３の（ａ）から（ｂ）のように軸を変えて処理する。同様に、因子行列Ｃに対しては、Ｋ方向を疎行列の行にするために、図１３の（ｂ）から（ｃ）のように軸を変えて処理する。
【００４９】
図１４は、因子行列Ｂに対して保持するデータを示す。図１４に示すとおり、因子行列Ｂに対しては、Ｌｊ、Ｘｉｊｋ、（ｋ，ｉ）のインデックス疎行列を保持し、＾Ｘｉｊｋのメモリ領域を確保しておく。また、因子行列Ｃに対しても同様に、Ｌｋ、Ｘｉｊｋ、（ｉ，ｊ）のインデックス疎行列を保持し、＾Ｘｉｊｋのメモリ領域を確保しておく。図１５に、因子行列Ａ、Ｂ、Ｃの更新のためのデータをまとめて示す。
【００５０】
（テンソルデータの疎行列化：効果の説明）
例えば、因子行列Ａで用いたＸｉｊｋに対して、Ｊ軸要素を基とする因子行列Ｂの更新処理を行うと、図１６（ａ）に示すようにランダムアクセスをしてしまう。
【００５１】
一方、本実施の形態の技術のように、因子行列に対応する軸毎に疎行列を用意することにより、当該因子行列の更新処理を行う際に、図１６（ｂ）に示すように、ランダムアクセスは発生せず、通信コストが下がり計算処理の高速化が可能となる。
【００５２】
すなわち、本実施の形態のように、各軸（モード）毎に更新用の疎行列データ構造を保持することで、モード毎に対する処理を単純ループ処理で実施することが可能となる。また、単純ループ処理に加え、メモリのランダムアクセスを抑えることによって特に大規模データでの処理ではキャッシュヒット率を向上させるなど、高速化が期待できる。ランダムアクセスを抑える効果は、ＧＰＵなどの並列分散処理では参照メモリ量を予め各スレッドでの参照必要量だけに抑えるだけでよいなど、非常に有効である。
【００５３】
（Ｎ次への拡張）
ここまで３次のテンソルを例にとって因子分解例を説明したが、本実施の形態に係る技術は、３次のテンソルに限らず、３次よりも大きな次数であるＮ次（Ｎは３以上の整数）のテンソルに拡張可能である。
【００５４】
Ｎ次のテンソルデータにおいて、ログ数Ｌ、Ｘｉ１…ｉＮのテンソルデータがあり、これを、図１７に示すように、因子行列Ｚ１…ＺＮにそれぞれ分解するケースを考える。なお、Ｘの添字は、明細書での表記の便宜上"ｉ１…ｉＮ"と表しているが、これは"ｉ１…ｉＮ"を意図している。
【００５５】
Ｎ次の場合も、３次を例にとって説明した場合と同様であり、データ配置処理部１２は、因子行列Ｚ１…ＺＮの各々について、対応する軸に対して展開した疎行列を作成する。
【００５６】
図１８（ａ）〜（ｃ）に、因子行列Ｚｋの更新のためのデータを示す。図１８（ａ）〜（ｃ）に示すとおり、Ｚｋの因子行列を更新させる場合、ｋに関わるログ数はＬｋであり、Ｘｉ１…ｉＮのテンソルデータも（ａ）に示す構造で保持しておく。またインデックス疎行列については、（ｂ）に示すように、ｋ以外の要素の組み合わせ（ｉｋ＋１，…ｉＮ，ｉ１，…ｉｋ−１）を保持しておく。これは、前述した「計算ループの最下位のインデックスから最上位の１つ前までの各インデックス」に相当する。また、＾Ｘｉ１…ｉＮのメモリ領域を確保しておく。これにより、任意の次数Ｎのテンソル因子分解に拡張可能である。すなわち、本実施の形態の技術により、インデックス疎行列に複数要素をもたせることで、高次モードへの拡張が容易に可能である。
【００５７】
本発明は、上記の実施の形態に限定されることなく、特許請求の範囲内において、種々変更・応用が可能である。
【符号の説明】
【００５８】
１０  テンソルデータ計算装置
１１  データ入力部
１２  データ配置処理部
１３  データ記憶部
１４  テンソル因子分解処理部
１５  データ出力部
【図１】
2016139391.tif 000011
【図２】
2016139391.tif 000012
【図３】
2016139391.tif 000013
【図４】
2016139391.tif 000014
【図５】
2016139391.tif 000015
【図６】
2016139391.tif 000016
【図７】
2016139391.tif 000017
【図８】
2016139391.tif 000018
【図９】
2016139391.tif 000019
【図１０】
2016139391.tif 000020
【図１１】
2016139391.tif 000021
【図１２】
2016139391.tif 000022
【図１３】
2016139391.tif 000023
【図１４】
2016139391.tif 000024
【図１５】
2016139391.tif 000025
【図１６】
2016139391.tif 000026
【図１７】
2016139391.tif 000027
【図１８】
2016139391.tif 000028