(57)【要約】  テンソルのデータ量を抑制することができる情報処理装置を提供する。情報処理装置（１）は、ＣＳＦ（Compressed Sparse Fiber）表現のデータにテンソルを変換するためにＭ（ただし、Ｍは３以上の自然数）階以上のテンソルの軸の順序を設定するＣＳＦ設計部（１１）と、ＣＳＦ設計部（１１）による設定にしたがい、前記Ｍ階以上のテンソルをＣＳＦ表現のデータに変換するＣＳＦ構築部（１２）と、前記ＣＳＦ表現のデータに現れる重複構造を、当該重複構造を表す代替構造に置換することにより前記ＣＳＦ表現のデータを圧縮し、圧縮された前記ＣＳＦ表現のデータである圧縮ＣＳＦデータと、置換ルールを示すデータである置換ルールデータとを出力するＣＳＦ圧縮部（１３）とを有する。
2020008513.tif 000002
【特許請求の範囲】
【請求項１】
ＣＳＦ（Compressed Sparse Fiber）表現のデータにテンソルを変換するためにＭ（ただし、Ｍは３以上の自然数）階以上のテンソルの軸の順序を設定するＣＳＦ設定部と、
前記ＣＳＦ設定部による設定にしたがい、前記Ｍ階以上のテンソルをＣＳＦ表現のデータに変換するＣＳＦ構築部と、
前記ＣＳＦ表現のデータに現れる重複構造を、当該重複構造を表す代替構造に置換することにより前記ＣＳＦ表現のデータを圧縮し、圧縮された前記ＣＳＦ表現のデータである圧縮ＣＳＦデータと、置換ルールを示すデータである置換ルールデータとを出力するＣＳＦ圧縮部と
を有する情報処理装置。
【請求項２】
前記圧縮ＣＳＦデータと前記置換ルールデータとを取得する圧縮テンソル取得部と、
（Ｍ−１）個の行列を取得する行列取得部と、
前記圧縮テンソル取得部が取得した前記圧縮ＣＳＦデータ及び前記置換ルールデータと、前記行列取得部が取得した前記（Ｍ−１）個の行列とに基づいて、前記圧縮ＣＳＦデータで表されるテンソルと前記（Ｍ−１）個の行列との積を演算する積演算部と
を有する請求項１に記載の情報処理装置。
【請求項３】
前記積演算部は、
前記置換ルールデータを用いて、前記テンソルと前記行列との積の演算するための所定の演算を行う第１の演算部と、
前記第１の演算部による演算結果を保持する演算結果保持部と、
前記演算結果保持部が保持する前記演算結果を利用して、前記テンソルと前記行列との積の演算を行う第２の演算部と
を有する請求項２に記載の情報処理装置。
【請求項４】
前記ＣＳＦ圧縮部は、文法圧縮によって前記ＣＳＦ表現のデータを圧縮し、前記圧縮ＣＳＦデータと、前記置換ルールを表すデータである辞書を出力する
請求項１乃至３のいずれか１項に記載の情報処理装置。
【請求項５】
前記テンソルは、知識グラフである
請求項１乃至４のいずれか１項に記載の情報処理装置。
【請求項６】
ＣＳＦ（Compressed Sparse Fiber）表現のデータにテンソルを変換するためにＭ（ただし、Ｍは３以上の自然数）階以上のテンソルの軸の順序を設定し、
前記設定にしたがい、前記Ｍ階以上のテンソルをＣＳＦ表現のデータに変換し、
前記ＣＳＦ表現のデータに現れる重複構造を、当該重複構造を表す代替構造に置換することにより前記ＣＳＦ表現のデータを圧縮し、圧縮された前記ＣＳＦ表現のデータである圧縮ＣＳＦデータと、置換ルールを示すデータである置換ルールデータとを出力する
テンソル圧縮方法。
【請求項７】
ＣＳＦ（Compressed Sparse Fiber）表現のデータにテンソルを変換するためにＭ（ただし、Ｍは３以上の自然数）階以上のテンソルの軸の順序を設定するＣＳＦ設定ステップと、
前記ＣＳＦ設定ステップでの設定にしたがい、前記Ｍ階以上のテンソルをＣＳＦ表現のデータに変換するＣＳＦ構築ステップと、
前記ＣＳＦ表現のデータに現れる重複構造を、当該重複構造を表す代替構造に置換することにより前記ＣＳＦ表現のデータを圧縮し、圧縮された前記ＣＳＦ表現のデータである圧縮ＣＳＦデータと、置換ルールを示すデータである置換ルールデータとを出力するＣＳＦ圧縮ステップと
をコンピュータに実行させるプログラムが格納された非一時的なコンピュータ可読媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本開示は、情報処理装置、テンソル圧縮方法、及びプログラムに関する。
【背景技術】
【０００２】
テンソル（多次元配列）は近年のデータ収集技術の向上と計算機性能の向上から、データ表現として用いられるようになってきた。
テンソルは多次元配列であり、行列の一般化と考えることができる。行列は例えば、文書−単語行列のように、文書と単語の２項関係しか表現することができない。一方でテンソルは文書−単語−時間といった３項関係を表現できる。このように、テンソルは行列よりも多くの情報を表現することが可能である。そのため機械学習やデータマイニングの分野で研究が進んでいる。【０００３】
しかし、テンソルによって表現されたデータのマイニングは非常に大きな計算時間がかかる。例えば、テンソル分解と呼ばれるテンソルを複数の行列の積に分解する手法は、各行列の最適化において、テンソルと複数の行列（最適化する行列以外のすべての行列）の積が必要となる。これは非常に大きな計算量であることが知られている。
テンソル分解における大きな計算量が必要とされるのは以下のテンソル−行列積演算である。【０００４】
式（１）：
【数１】
2020008513.tif 000003
【０００５】
式（１）はM階のテンソルについてのテンソル−行列積演算を表す。ここで、N(k)はテンソル分解によって得られる行列である。
この演算はN(n)を最適化する際に用いる勾配の計算に必要になり、すべてのinおよびjに対して演算を行いPを求める必要がある。
なお、式（１）において、行列Pは、テンソル−行列積演算の演算結果を示す行列、すなわちテンソル−行列積演算の演算結果を格納する行列である。言い換えると、テンソル−行列積の演算結果として行列Pが得られることとなる。式（１）はPの要素ごとの演算方法を示す式である。また、Xはテンソルである。jおよびinは要素のインデックスを示す。nはテンソルの軸を示す。例えば、２階のテンソル（すなわち行列）の場合n=1が行を指し、n=2が列を指す。３階のテンソルの場合、n=3は奥行き方向を指す。【０００６】
また、近年のテンソルサイズの増加からテンソル自体がメモリに載らずインメモリプロセス（in-memory process）による計算ができないという問題がある。これはテンソルの非零要素はテンソルの軸の分だけインデックス（index）を必要とするためである。例えば、４階のテンソルは(i,j,k,l)といったインデックスを保持する必要がある。これは行列においては(i,j)成分だけでよい場合と比べて２倍のメモリ使用量になる。【０００７】
非特許文献１はこの問題に対して、テンソルの非零要素のインデックスを木構造で表現することでテンソルのサイズを小さくするＣＳＦ（Compressed Sparse Fiber）表現と、その木構造を用いたテンソル−行列積演算アルゴリズムを提案している。木構造によってテンソル−行列積演算は計算が省略される場合がある。しかし、それは主に葉ノードに対する演算のみであるため多くの場合で演算が省略されるわけではない。【０００８】
特許文献１に開示された技術では、非零要素のみを保持するとともに、またテンソル−行列積の効率の良い計算のために、複数の行列形式でデータを表現することで、メモリの削減と計算の高速化を行っている。しかし、メモリの削減は、非零要素のみを保持することによるものであり、非零要素の数も膨大なテンソルには適用が困難である。また、重複した表現を利用する必要があるため、非零要素のみを単純に表現する場合よりも大きな計算空間が必要になる。【０００９】
特許文献２はテンソル分解を圧縮として用いる手法である。しかし、この手法はテンソル分解が実行できる前提の技術である。また、テンソル分解は情報の損失がおこるために、圧縮後のタスクの精度を悪化させる危険性がある。
【先行技術文献】
【特許文献】
【００１０】
【特許文献１】特開２０１６−１３９３９１号公報
【特許文献２】特表２００５−５１４６８３号公報
【非特許文献】
【００１１】
【非特許文献１】Smith, S., Ravindran, N., Sidiropoulos, N. D., & Karypis, G. “SPLATT: Efficient and parallel sparse tensor-matrix multiplication”, In 2015 IEEE International Parallel and Distributed Processing Symposium (IPDPS), pp. 61-70, May 2015.
【発明の概要】
【発明が解決しようとする課題】
【００１２】
したがってテンソルをメモリに格納できるようにする新規な技術が依然として求められている。【００１３】
本開示の目的は、テンソルのデータ量を抑制することができる情報処理装置、テンソル圧縮方法、及びプログラムを提供することにある。
【課題を解決するための手段】
【００１４】
本開示にかかる情報処理装置は、ＣＳＦ（Compressed Sparse Fiber）表現のデータにテンソルを変換するためにＭ（ただし、Ｍは３以上の自然数）階以上のテンソルの軸の順序を設定するＣＳＦ設定部と、前記ＣＳＦ設定部による設定にしたがい、前記Ｍ階以上のテンソルをＣＳＦ表現のデータに変換するＣＳＦ構築部と、前記ＣＳＦ表現のデータに現れる重複構造を、当該重複構造を表す代替構造に置換することにより前記ＣＳＦ表現のデータを圧縮し、圧縮された前記ＣＳＦ表現のデータである圧縮ＣＳＦデータと、置換ルールを示すデータである置換ルールデータとを出力するＣＳＦ圧縮部とを有する。【００１５】
また、本開示にかかるテンソル圧縮方法では、ＣＳＦ（Compressed Sparse Fiber）表現のデータにテンソルを変換するためにＭ（ただし、Ｍは３以上の自然数）階以上のテンソルの軸の順序を設定し、前記設定にしたがい、前記Ｍ階以上のテンソルをＣＳＦ表現のデータに変換し、前記ＣＳＦ表現のデータに現れる重複構造を、当該重複構造を表す代替構造に置換することにより前記ＣＳＦ表現のデータを圧縮し、圧縮された前記ＣＳＦ表現のデータである圧縮ＣＳＦデータと、置換ルールを示すデータである置換ルールデータとを出力する。【００１６】
また、本開示にかかるプログラムは、ＣＳＦ（Compressed Sparse Fiber）表現のデータにテンソルを変換するためにＭ（ただし、Ｍは３以上の自然数）階以上のテンソルの軸の順序を設定するＣＳＦ設定ステップと、前記ＣＳＦ設定ステップでの設定にしたがい、前記Ｍ階以上のテンソルをＣＳＦ表現のデータに変換するＣＳＦ構築ステップと、前記ＣＳＦ表現のデータに現れる重複構造を、当該重複構造を表す代替構造に置換することにより前記ＣＳＦ表現のデータを圧縮し、圧縮された前記ＣＳＦ表現のデータである圧縮ＣＳＦデータと、置換ルールを示すデータである置換ルールデータとを出力するＣＳＦ圧縮ステップとをコンピュータに実行させる。
【発明の効果】
【００１７】
本開示により、テンソルのデータ量を抑制することができる情報処理装置、テンソル圧縮方法、及びプログラムを提供することができる。
【図面の簡単な説明】
【００１８】
【図１】第１の実施の形態の情報処理装置の構成例を示すブロック図である。
【図２】ＣＳＦの例を示す図である。
【図３】第１の実施の形態及び第２の実施の形態の情報処理装置のハードウェア構成を示す図である。
【図４】第１の実施の形態のテンソル圧縮装置の動作を示すフローチャートである。
【図５】ＣＳＦの頻出部分構造を置換した例を示す図である。
【図６】第２の実施の形態の圧縮テンソル−行列積演算装置の構成例を示すブロック図である。
【図７】第２の実施の形態の圧縮テンソル−行列積演算装置の動作例を示すフローチャートである。
【発明を実施するための形態】
【００１９】
以下では、本開示の実施の形態について、図面を参照しながら詳細に説明する。各図面において、同一又は対応する要素には同一の符号が付されており、説明の明確化のため、必要に応じて重複説明は省略される。
【００２０】
＜第１の実施の形態＞
＜構成の説明＞
図１は本実施の形態１にかかるテンソル圧縮装置としての情報処理装置１の構成を示すブロック図である。また、図２はＣＳＦの例を示す図である。図２に示す木構造おいて、各軸がテンソルの階層に対応しており、ノードラベル（各ノード内に記載された数字）は、テンソルの非零要素のインデックスを示している。テンソル圧縮装置としての情報処理装置１は、図１に示されるように、ＣＳＦ設計部１１とＣＳＦ構築部１２とＣＳＦ圧縮部１３とを備える。
【００２１】
ＣＳＦ設計部１１は、M階以上のテンソルの非零要素インデックスを表現するＣＳＦを構築するための前段階の処理として、ＣＳＦの構築方法を設定する。ＣＳＦは図２で示すように、木の深さが軸に対応する。例えば、軸の数が３つの場合、図２に示すように、深さ０のノード、深さ１のノード、及び深さ２のノードから構成されるＣＳＦの構築が可能である。つまり、ＣＳＦの構築方法は、軸の組み合わせ分だけ存在する。しがたって、具体的には、ＣＳＦ設計部１１はこのＣＳＦの軸の組み合わせ順序を設定する。この軸の設定順序はユーザーの任意の方法を用いてよい。例えば、あらかじめ入力されたテンソルの軸の順番でもよいし、各軸の次元の大きさを昇順にソートしたものでもよい。このように、ＣＳＦ設計部１１は、ＣＳＦ表現のデータにテンソルを変換するためにＭ（ただし、Ｍは３以上の自然数）階以上のテンソルの軸の順序を設定する。なお、ＣＳＦ設計部１１は、ＣＳＦ設定部と称されてもよい。
【００２２】
ＣＳＦ構築部１２は、ＣＳＦ設計部１１により設定されたＣＳＦの構築における軸の順序を用いて入力であるテンソルの非零要素のインデックスからＣＳＦを構築する。ＣＳＦは軸の順序を定めると構造は一意に定まる。そのため、どのように構築を行ってもよい。例えば、ＣＳＦ構築部１２は、上述した非特許文献１に記載した手法により、ＣＳＦを構築する。このように、ＣＳＦ構築部１２は、ＣＳＦ設計部１１による設定にしたがい、Ｍ階以上のテンソルをＣＳＦ表現のデータに変換する。
【００２３】
ＣＳＦ圧縮部１３はＣＳＦ構築部１２により構築されたＣＳＦを圧縮する。ＣＳＦの圧縮は頻出部分構造を置換する圧縮方法を用いる。たとえば、そのような置換方法の一つに文法圧縮と呼ばれる圧縮方法がある。文法圧縮とは、圧縮した結果とは別に、辞書と呼ばれる補助データ構造を保持し、この辞書に置換方法を記述することで、高い圧縮率を実現する圧縮方法である。ＣＳＦ圧縮部１３は、文法圧縮に限らず、他の公知の技術を用いることが可能である。ただし、辞書を用いることで完全に情報を復元できるような圧縮をおこなう圧縮方法を用いることが望ましいが、その限りではない。なお、頻出部分構造は、ＣＳＦの木構造において、所定の回数以上（ただし、少なくとも２回以上）出現する部分木である。頻出部分構造は、重複構造と称されてもよい。このように、ＣＳＦ圧縮部１３は、ＣＳＦ表現のデータに現れる重複構造を、当該重複構造を表す代替構造に置換することによりＣＳＦ表現のデータを圧縮する。そして、ＣＳＦ圧縮部１３は、圧縮されたＣＳＦ表現のデータである圧縮ＣＳＦデータと、置換ルールを示すデータである置換ルールデータ（辞書）とを出力する。
【００２４】
尚、情報処理装置１は、例えば、図３に示すように、プロセッサ５０と、メモリ５１と、記憶装置５２とを備える、これらの構成により、処理を実行する。プロセッサ５０は、例えば、マイクロプロセッサ、ＭＰＵ(Micro Processor Unit)、又はＣＰＵ(Central Processing Unit)などであってもよい。メモリ５１は、例えば、揮発性メモリ又は不揮発性メモリによって構成されるメモリである。記憶装置５２は、例えばハードディスクドライブ、ソリッドステートドライブなどのストレージである。
【００２５】
記憶装置５２には、図１に示した各構成要素を実現するための１以上の命令を含むコンピュータプログラムが記憶されている。そして、プロセッサ５０は、記憶装置５２からコンピュータプログラムをメモリ５１へ読み込み、当該コンピュータプログラムを実行する。これによりプロセッサ５０は、ＣＳＦ設計部１１、ＣＳＦ構築部１２およびＣＳＦ圧縮部１３の機能を実現する。
【００２６】
上述したプログラムは、様々なタイプの非一時的なコンピュータ可読媒体（non-transitory computer readable medium）を用いて格納され、コンピュータに供給することができる。非一時的なコンピュータ可読媒体は、様々なタイプの実体のある記録媒体（tangible storage medium）を含む。非一時的なコンピュータ可読媒体の例は、磁気記録媒体（例えばフレキシブルディスク、磁気テープ、ハードディスクドライブ）、光磁気記録媒体（例えば光磁気ディスク）、Compact Disc Read Only Memory（CD-ROM）、CD-R、CD-R/W、半導体メモリ（例えば、マスクROM、Programmable ROM（PROM）、Erasable PROM（EPROM）、フラッシュROM、Random Access Memory（RAM））を含む。また、プログラムは、様々なタイプの一時的なコンピュータ可読媒体（transitory computer readable medium）によってコンピュータに供給されてもよい。一時的なコンピュータ可読媒体の例は、電気信号、光信号、及び電磁波を含む。一時的なコンピュータ可読媒体は、電線及び光ファイバ等の有線通信路、又は無線通信路を介して、プログラムをコンピュータに供給できる。
【００２７】
情報処理装置１は、例えば、記憶装置５２に予め記憶されたテンソル（すなわち、圧縮前のテンソルのデータ）について圧縮処理を行う。情報処理装置１はＣＳＦ圧縮部１３によって圧縮されたテンソルおよび補助データ構造である辞書をメモリ５１に保存してもよいし、情報処理装置１の外部の装置へ出力してもよい。
【００２８】
図４は本実施の形態１にかかる情報処理装置１が実施するテンソル圧縮方法の流れを説明するためのフローチャートである。まずＣＳＦ設計部１１は、M階のテンソルの非零要素インデックスをすべて受けとり、ＣＳＦの軸の順序をあらかじめ定めた基準によって決定する（ステップＳ１０１）。次にＣＳＦ構築部１２はＣＳＦ設計部１１によって得られたＣＳＦ構造（すなわち、軸の順序）に基づいてM階のテンソルの非零要素からＣＳＦを構築する（ステップＳ１０２）。そして、ＣＳＦ圧縮部１３は、ＣＳＦ構築部１２で構築されたＣＳＦの頻出部分構造を予め定められた圧縮方法で圧縮する（ステップＳ１０３）。
【００２９】
このように、本実施の形態により、テンソルを圧縮することが可能である。すなわち、テンソルのＣＳＦ表現を直接用いるのではなく、ＣＳＦの圧縮表現と補助データ構造である辞書を用いることでデータの表現を行う。
【００３０】
尚、本実施の形態で対象とするテンソルとしては、例えば、知識グラフと呼ばれるデータがあげられる。知識グラフは(主語（Subject）, 述語（Predicate）, 目的語（Object）)のトリプレット（triplet）で表現されるもので、SubjectはObjectのPredicateである場合に、１を持ちそうでないときに０を持つ。そのためSubject, Predicate, Objectを各軸として、インデックスを与えることによって、知識グラフは３階のテンソルで表現される。そのため、本実施の形態にかかる情報処理装置１は知識グラフ圧縮装置と呼ぶこともできる。
【００３１】
＜具体例１＞
具体例を用いて、本実施の形態１にかかるテンソル圧縮装置としての情報処理装置１の動作を説明する。
まず、圧縮の対象となるテンソルの非零要素インデックスは以下であるものとする。また、テンソルのサイズは(2,3,3)であるとする。
【００３２】
式（２）：
【数２】
2020008513.tif 000004
【００３３】
これに対して、ＣＳＦ設計部１１は任意の基準によって、構築の構造、すなわち軸の順序を決定する。本具体例では、軸の次元の大きさが降順になるようにソートされた軸の順を採用する。ＣＳＦは節、または、根において、木の深さが浅ければ浅いほどインデックスが共有されて一つのノードで表現される。そのため、インデックスの種類が少なければ少ないほど共有される可能性が高まる。つまり、ＣＳＦにおける表現に必要なメモリ使用量が減る可能性が高いといえる。
【００３４】
よって式（２）で表現されているテンソルの場合は、3-2-1（または2-3-1）がＣＳＦの構造として選ばれる。ここで、3-2-1は、式（２）において左から３番目に記載されているインデックスに対応する軸、左から２番目に記載されているインデックスに対応する軸、左から１番目に記載されているインデックスに対応する軸、という軸の順序を示す。
【００３５】
次にＣＳＦ構築部１２はＣＳＦ設計部１１で選ばれた構造3-2-1と式（２）のテンソルから図２のようなＣＳＦを構築する。
【００３６】
次にＣＳＦ圧縮部１３はＣＳＦ構築部１２で構築されたＣＳＦの圧縮を行う。本説明では、理解を容易にするため、葉ノードにおける頻出部分構造のみを置き換える手法を説明する。
【００３７】
図２のＣＳＦの葉ノードにおける頻出部分構造はラベル”1”とラベル”2”の同時出現である。そのため、ＣＳＦ圧縮部１３はこの部分構造をラベル”a”が記述された新しいノードへと置換する。そして図５のような新たなＣＳＦを得る。これが圧縮されたＣＳＦである。そして、置換した情報、すなわち置換ルールを示すデータ（置換ルールデータ）を、辞書に以下のように保存する。
【００３８】
式（３）：
【数３】
2020008513.tif 000005
【００３９】
これによって、２つのノードが１つのノードに置換される。この置換が４回出現するため、ノード数が８個から４個に圧縮されており、また、辞書の置換ルール（式（３））は３つの数(a,1,2)で表現できるため、合計で８個のデータによる表現から７個のデータによる表現へと圧縮がなされていることがわかる。なお、上記例では、２つのノードが１つのノードに置換されるが、３以上のノードが１つのノードに置換されてもよい。
【００４０】
ＣＳＦ圧縮部１３はこのように頻出部分構造をすべて列挙し、置換によって全体のデータ数が減る場合にのみ置換を行う。置換を行った後再度頻出部分構造を列挙し、置換によって全体のデータ数を減らすことが可能な頻出部分構造を再び置換する。この動作を例えば、置換によるデータ数の削減ができなくなるまで行う。なお、圧縮効率を上げるためにはこのように可能な限り置換を繰り返すことが好ましいが、ＣＳＦ圧縮部１３はデータ数を減らすことが可能な頻出部分構造が残存した状態で置換処理を終了してもよい。ＣＳＦ圧縮部１３によるこのような処理により圧縮を行うことができる。
【００４１】
上記説明では、葉ノードにおける頻出部分構造のみを置換する例を示したが、節ノードや根ノードを含めた任意の頻出部分構造に対して圧縮を考えることができる。すなわち、部分木に対しても圧縮を行うことができる。ただし、置換対象の部分構造は、その部分構造に子ノードが一つもついていない状態である必要がある。なぜなら、ＣＳＦは多分木であるためである。仮に子ノードがついている部分構造を置換した場合に、その子ノードが置換前のどのノードの子ノードであるか一意に定まらないためである。
【００４２】
以上、実施の形態１について説明した。実施の形態１にかかる情報処理装置１によれば、ＣＳＦ圧縮部１３によりＣＳＦのデータ数が削減される。このため、テンソルのデータ量を抑制することができる。したがって、例えば、機械学習又はデータ解析などの所定の処理をテンソルを用いて行う装置に搭載された限られた容量のメモリに、当該テンソルを格納することができる。
【００４３】
＜実施の形態２＞
本実施の形態では、実施の形態１にかかるテンソル圧縮装置で圧縮されたテンソルと複数の行列との積の演算を行う、圧縮テンソル−行列積演算装置としての情報処理装置２について説明する。すなわち、本実施の形態では、式（１）で表現された演算を、圧縮されたテンソルを用いて演算する圧縮テンソル−行列積演算装置について説明する。
【００４４】
図５は、本実施の形態にかかる圧縮テンソル−行列積演算装置としての情報処理装置２構成を示すブロック図である。情報処理装置２は、圧縮テンソル取得部２１と、行列取得部２２と、演算指定部２３と、辞書演算部２４と、辞書演算結果保持部２５と、圧縮ＣＳＦ演算部２６とを有する。なお、情報処理装置２は、実施の形態１にかかる情報処理装置１を含む情報処理装置であってもよい。
【００４５】
圧縮テンソル取得部２１はテンソル圧縮装置としての情報処理装置１によって圧縮されたテンソルを取得する構成要素である、具体的には、圧縮テンソル取得部２１は圧縮されたＣＳＦと補助データ構造である辞書を取得する。圧縮テンソル取得部２１は例えば、メモリ５１又は記憶装置５２に記憶された、圧縮されたＣＳＦ及び辞書を読み出す。
【００４６】
行列取得部２２は圧縮されたテンソルとの積を演算する（Ｍ−１）個の行列を取得する。すなわち、行列取得部２２は演算対象の行列を取得する。行列取得部２２は例えば、メモリ５１又は記憶装置５２に記憶された行列を読み出す。
【００４７】
演算指定部２３は、テンソルと行列との積の演算において、行列取得部２２によって取得された（Ｍ−１）個の行列をどの軸にどのように演算するかを指定する。テンソルと行列との積では、行列同士の積において右からかけるか左からかけるかといった指定が必要であるのと同様に、どの軸方向からかけるのかを指定する必要がある。そのため、あらかじめどの軸に対してどの行列との積を演算するかを指定する必要がある。演算指定部２３は、例えば演算を定義する予め設定された定義情報に従って指定する。
【００４８】
辞書演算部２４は、補助データ構造である辞書に従って置換された頻出部分構造について、式（１）の演算で必要な演算を予め計算する構成要素である。辞書演算部２４は、置換前の頻出部分構造で示されるインデックスに対応する行列要素を用いて、テンソル−行列積を演算するための演算（以下、サブ演算と称す）を行う。
【００４９】
辞書演算結果保持部２５は、辞書演算部２４による演算で得られた演算結果を保持する構成要素である。より詳細には、辞書演算結果保持部２５は、置換される前の頻出部分構造に対する演算結果を置換された新たなノードに対して紐づけて保持する。換言すると、辞書演算結果保持部２５は、置換される前の頻出部分構造に対するサブ演算の結果を、置換後の新たなノードに対するサブ演算の結果として保持する。これによって、置換された新たなノードに対する演算を求められた場合に、この辞書演算結果保持部２５から演算結果を呼び出すことが可能になり、繰り返し同じ計算を行わずに済むために、計算回数を削減することができる。
【００５０】
圧縮ＣＳＦ演算部２６は、圧縮されたＣＳＦに対し探索と演算を実行する構成要素である。圧縮ＣＳＦ演算部２６は、根ノードから順に探索し、ＣＳＦに対する演算を行う。圧縮ＣＳＦ演算部２６は、演算指定部２３の指定により演算対象として選ばれなかった軸がＣＳＦのどの深さに対応するかに応じて演算方法を変化させて演算を行う。具体的には、圧縮ＣＳＦ演算部２６は、選ばれなかった軸が根ノードに対応する場合、所定の第１の演算方法により演算し、葉ノードに対応する場合、所定の第２の演算方法により演算し、節ノードに対応する場合、所定の第３の演算方法により演算する。
【００５１】
図６は本実施の形態２にかかる情報処理装置２が実施する圧縮テンソル−行列積演算方法の流れを説明するためのフローチャートである。
【００５２】
まず圧縮テンソル取得部２１は演算対象である圧縮されたテンソルを取得する（ステップＳ２０１）。
次に、行列取得部２２は演算対象である行列を取得する（ステップＳ２０２）。
次に演算指定部２３は、どの軸にどの行列の積の演算を行うかを指定する（ステップＳ２０３）。
【００５３】
ステップＳ２０３の後、行列の各列に対して、すなわち式（１）におけるPのj番目のベクトルに対して以下の動作（ステップＳ２０４からステップＳ２０７）を行う。
【００５４】
まず、辞書演算部２４で、すべての頻出部分構造に対して、テンソル−行列積を演算するためのサブ演算をおこなう（ステップＳ２０４）。
そして、ステップＳ２０４で得られたすべての演算結果を辞書に記載された置換後の新たなノードに紐づけて辞書演算結果保持部２５に保存する（ステップＳ２０５）。
次に、圧縮ＣＳＦ演算部２６は、演算指定部２３の指定により演算対象として選ばれなかった軸がＣＳＦのどの深さに対応するかに応じて演算方法を変化させ、根ノードから順にＣＳＦに対する演算を行う（ステップＳ２０５）。
圧縮ＣＳＦ演算部２６は、ステップ２０５の演算結果をPのj番目の要素に代入する（ステップＳ２０７）。すなわち、圧縮ＣＳＦ演算部２６は、Pのj番目のベクトルについての演算結果を保存する。
この一連の動作（Ｓ２０４からＳ２０７）は、すべてのベクトルに対して実行されるまで、ベクトル毎に繰り返される。Ｓ２０４からＳ２０７をすべてのベクトルに行うことで圧縮テンソル−行列積が得られる。
【００５５】
＜具体例２＞
本具体例では、実施の形態２にかかるテンソル−行列積演算装置による演算例を説明する。本具体例では、具体例１で示した圧縮されたテンソルに対しての演算を考える。行列については、様々な場合の説明のため、一般化したものにより説明する。また、簡単のため、行列の列の数は１であるとする。すなわち、j=1とする。そのため、本具体例では、テンソル−ベクトル積演算と同じ演算を扱うこととなる。ただし、列毎の演算は変わらないため、これは容易にテンソル−行列積演算に一般化可能である。
【００５６】
求めるテンソル−行列積は、入力によって異なる演算方法が必要になる。入力は(M-1)個の行列であるため、必ず一つの軸が、行列との積の演算対象とはならない。この軸nが（１）根ノードに対応する軸か（すなわち、n=1であるか）、（２）葉ノードに対応する軸か（すなわち、n=Mであるか）、（３）節ノードに対応する軸か（すなわち、1< n <Mであるか）、によって演算方法が異なる。
【００５７】
ここで、図４のＣＳＦの深さに対応するインデックスを次のように定義する。すなわち、根ノードに対応するインデックスをi1とし、節ノードに対応するインデックスをi2とし、葉ノードに対応するインデックスをi3とする。また、根ノードに対応する軸に対応する行列をAとし、節ノードに対応する軸に対応する行列をBとし、葉ノードに対応する軸に対応する行列をCとする。
【００５８】
上述したケース（１）からケース（３）に対する挙動について順に、図５の圧縮されたＣＳＦおよび式（３）で表現される辞書が得られた場合に対して説明をする。
ケース（１）の場合に求めるテンソル−行列積の要素演算は以下のものになる。
【００５９】
式（４）：
【数４】
2020008513.tif 000006
【００６０】
ここで、j=1のため、以降ではjの記述を省略する。また、ここでテンソルはバイナリである。本具体例では、P1の演算方法を示す。まず、辞書演算部２４は、式（３）で表される置換ルールに対して、この置換ルールに対応する演算を行う。式（３）で表される置換ルールにおいて置換前のインデックスは、”1”と”2”であり、葉ノードに対応する行列はCであるため、この置換ルールに対する辞書演算部２４の演算結果は(C1+C2)である。よって、辞書演算結果保持部２５はa=(C1+C2)という結果を保持する。すなわち、辞書演算結果保持部２５は、”a”と、(C1+C2)の演算結果とを紐付けて保持する。
【００６１】
圧縮ＣＳＦ演算部２６はP1を求めるために、対応する根ノード、すなわち図５における深さ0にあるラベル”1”のノードから深さ優先探索の要領で処理を実行する。まず、探索は、左の子ノードに進み、続いて、２段目のラベル”1”のノードに進む。次に、探索は、２段目のラベル”1”の子ノードであるラベル”a”のノードへ進む。ここで、このラベル”a”ノードの深さがM-1であるため、子ノードは存在しない。そのため、ノードが、値を親ノードに返していくよう圧縮ＣＳＦ演算部２６は処理を行う。ここで、子ノードが存在しないノードが置換されたノードであった場合に、辞書演算結果保持部２５から、そのノードに対応する演算結果が獲得され、この演算結果が親ノードに返される。そのため、２段目のラベル”1”のノードはラベル”a”のノードから(C1+C2)を受けとる。子ノードを持っているノードが値を返す時は、そのノードに対応する行列の要素と、すべての子ノードから受け取った結果の和との積の演算結果を親ノードに値を返す。この例ではラベル”a”のノード以外のノードがないため、２段目のラベル”1”のノードに対応する要素B1と子ノードから受け取った(C1+C2)の積であるB1(C1+C2)を親ノードに返す。
【００６２】
辞書演算部２４はn=Mではないときに、呼ばれたノードに対する演算を行う。具体的には、上述の通り、この例ではラベル”a”のノードが呼ばれると、式（３）の置換ルールより、aはラベル”1”とラベル”2”に対応しているため、辞書演算部２４は要素C1と要素C2の和を演算結果として出力する。この演算は、ラベル”1”のノードとラベル”2”のノードに対する式（４）における演算に対応する。
辞書演算結果保持部２５はこの演算結果をa=(C1+C2)として保持し、２段目のラベル”1”のノードは返値として、(C1+C2)を得る。そして、圧縮ＣＳＦ演算部２６は、B1(C1+C2)の演算を行う。そして、１段目(深さ0)のノードにB1(C1+C2)の値が返される。
次に、圧縮ＣＳＦ演算部２６は、１段目のラベル”1”についての次の子ノード（右側の子ノード）である２段目のラベル”3”のノードに対して同様の操作を行う。
２段目のラベル”3”のノードの探索後、同様に、探索はラベル”a”のノードへとすすむ。ラベル”a”のノードは(C1+C2)を返し、２段目のラベル”3”のノードはB3(C1+C2)を返す。
最後に、圧縮ＣＳＦ演算部２６は、１段目のラベル”1”のノードがすべての子ノードから得た結果の和を算出する。この算出結果がP1と同じものになる。
【００６３】
ここで、ラベル”a”についての圧縮がされていない場合について考える。この場合、各２段目のノードにおいて、各子ノードからC1とC2を受け取り、C1+C2を計算することになる。そのため、C1+C2の演算は２回行う必要がある。これに対し、ラベル”a”についての圧縮が行われ、かつ、辞書演算結果保持部２５においてラベル”a”についての演算結果が保持されている場合、C1+C2の演算は辞書演算部２４による１回の演算で済む。このことから本実施の形態では演算回数が少なくなっていることがわかる。
【００６４】
次にケース（２）の場合（n=Mの場合）について例を示す。
この場合に求めるテンソル−行列積の要素演算は以下になる。
【００６５】
式（５）：
【数５】
2020008513.tif 000007
【００６６】
残念ながら、この場合は計算量の改善は得られない。なぜなら、式（５）にはC1やC2が出現しないためである。計算量の削減のため、辞書演算部２４および辞書演算結果保持部２５は指定された軸に応じては演算および保持を行わないとしてもよい。
【００６７】
この場合もケース（１）の場合と同様に、圧縮ＣＳＦ演算部２６は、深さ優先探索の要領で処理を行う。しかし、ケース（１）の場合とは異なり、圧縮ＣＳＦ演算部２６は、探索で辿ってきた値を子ノードへと伝播させる。
【００６８】
ケース１の説明と同様に１段目にラベル”1”のノードを有する木について説明する。
まず１段目のラベル”1”のノードはこのラベルで示されるインデックスに対応する要素であるA1を左の子ノードである２段目のラベル”1”のノードに送る。
次に、圧縮ＣＳＦ演算部２６は、２段目のラベル”1”のノードで示されるインデックスに対応する値B1と親ノードから送られた値を掛け算する。そして得られた値A1*B1を子ノードである３段目のノード（ラベル”a”のノード）へ送る。３段目のノード（ラベル”a”のノード）は置換によって得られたものなので、ここで圧縮ＣＳＦ演算部２６は親ノードから受け取った値をそれぞれ、圧縮されたノードが持つインデックスに対応する、演算結果を格納する行列の要素に足し合わせるという動作を行う。具体的には、圧縮ＣＳＦ演算部２６はP1+= A1*B1とP2+=A1*B1の演算を行う。なお、P1及びP2の初期値は０である。
このような処理をすべての１段目のノードに対して実行することで、式（５）の演算が可能である。
【００６９】
最後にケース（３）の場合について説明する。これはケース（１）とケース（２）の複合によって解くことができる。
ケース（３）の場合に求めるテンソル−行列積の要素演算は以下である。
【００７０】
式（６）：
【数６】
2020008513.tif 000008
【００７１】
ケース（３）では、圧縮ＣＳＦ演算部２６は、i<nとなるようなi段目のノードまでケース（２）の挙動と同様に値を子ノードへと送り、i=nとなるときに、それまでの探索で得た値を保持し、ケース（１）の挙動に切り替えるという方法で演算を行う。
【００７２】
具体的に、n=2のときの例をしめす。ケース１及びケース２の説明と同様に１段目にラベル”1”のノードを有する木についての演算方法を示す。
１段目のラベル”1”のノードはi=1<n=2のため、このノードに対応する値A1を子ノードである２段目のラベル”1”のノードへと渡すよう圧縮ＣＳＦ演算部２６は処理する。次に２段目のラベル”1”のノードが一旦親ノードから送られてきた値を保持するよう圧縮ＣＳＦ演算部２６は処理を行う。そして、圧縮ＣＳＦ演算部２６は、子ノードへと値は送らずに探索を進める。ここでケース（１）と同様に、圧縮ＣＳＦ演算部２６は、ラベル”a”についてのサブ演算結果の値である(C1+C2)を辞書演算部２４から獲得し、２段目のラベル”1”のノードへとこの値を返すよう処理する。なお、このとき、辞書演算部２４によるサブ演算結果は、辞書演算結果保持部２５に保持される。２段目のラベル”1”のノードはこのノードが示すインデックスに対応する要素であるP1に、親ノードから送られてきた値A1と子ノードから送られてきた値(C1+C2)を掛け算したものを、足し合わせる。具体的には、圧縮ＣＳＦ演算部２６はP1+=A1(C1+C2)を演算する。なお、P1の初期値は０である。
このような処理をすべてのノードに対して同様に行うことで、式（６）の演算を実現することができる。ケース（３）ではケース（１）と同様に辞書演算結果保持部２５の結果を利用できるため、計算回数が減らすことができる。
【００７３】
以上、実施の形態２について説明した。なお、演算指定部２３、辞書演算部２４、辞書演算結果保持部２５、及び圧縮ＣＳＦ演算部２６は、積演算部と称されてもよい。したがって、本実施の形態にかかる情報処理装置２においては、積演算部が、圧縮ＣＳＦデータ及び置換ルールデータと、（Ｍ−１）個の行列とに基づいて、圧縮ＣＳＦデータで表されるテンソルと（Ｍ−１）個の行列との積を演算する。このため、本実施の形態にかかる情報処理装置２によれば、圧縮されたＣＳＦと行列とのテンソル−行列積演算を行うことができる。また、特に、この積演算部は、置換ルールデータを用いて、テンソルと行列との積の演算するための所定の演算を行う辞書演算部２４（第１の演算部）と、その演算結果を保持する辞書演算結果保持部２５とを有する。そして、更に、この積演算部は、辞書演算結果保持部２５が保持する演算結果を利用して、テンソルと行列との積の演算を行う圧縮ＣＳＦ演算部（第２の演算部）を有する。このような構成によれば、計算コストを抑制することができる。すなわち、ＣＳＦの圧縮における置換対象となったノードについてのサブ演算結果を辞書演算結果保持部２５に保持することで当該サブ演算の計算回数を減らすことができ、計算コストを抑制することができる。したがって、本実施の形態によれば、大規模なテンソルと行列との積の計算コストを抑制することができる。
なお、情報処理装置２は、さらに、積演算部により算出されるテンソルと行列の積演算結果を用いて機械学習処理を行う学習部を備えてもよいし、積演算部により算出されるテンソルと行列の積演算結果を用いたデータ解析を行うデータ解析部を備えてもよい。
【００７４】
以上、実施の形態を参照して本願発明を説明したが、本願発明は上記によって限定されるものではない。本願発明の構成や詳細には、発明のスコープ内で当業者が理解し得る様々な変更をすることができる。
【符号の説明】
【００７５】
１    情報処理装置
２    情報処理装置
１１    ＣＳＦ設計部
１２    ＣＳＦ構築部
１３    ＣＳＦ圧縮部
２１    圧縮テンソル取得部
２２    行列取得部
２３    演算指定部
２４    辞書演算部
２５    辞書演算結果保持部
２６    圧縮ＣＳＦ演算部
５０    プロセッサ
５１    メモリ
５２    記憶装置
【図１】
2020008513.tif 000009
【図２】
2020008513.tif 000010
【図３】
2020008513.tif 000011
【図４】
2020008513.tif 000012
【図５】
2020008513.tif 000013
【図６】
2020008513.tif 000014
【図７】
2020008513.tif 000015
【手続補正書】
【提出日】令和2年12月17日(2020.12.17)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
ＣＳＦ（Compressed Sparse Fiber）表現のデータにテンソルを変換するためにＭ（ただし、Ｍは３以上の自然数）階以上のテンソルの軸の順序を設定するＣＳＦ設定部と、
前記ＣＳＦ設定部による設定にしたがい、前記Ｍ階以上のテンソルをＣＳＦ表現のデータに変換するＣＳＦ構築部と、
前記ＣＳＦ表現のデータに現れる重複構造を、当該重複構造を表す代替構造に置換することにより前記ＣＳＦ表現のデータを圧縮し、圧縮された前記ＣＳＦ表現のデータである圧縮ＣＳＦデータと、置換ルールを示すデータである置換ルールデータとを出力するＣＳＦ圧縮部と
を有する情報処理装置。
【請求項２】
前記圧縮ＣＳＦデータと前記置換ルールデータとを取得する圧縮テンソル取得部と、
（Ｍ−１）個の行列を取得する行列取得部と、
前記圧縮テンソル取得部が取得した前記圧縮ＣＳＦデータ及び前記置換ルールデータと、前記行列取得部が取得した前記（Ｍ−１）個の行列とに基づいて、前記圧縮ＣＳＦデータで表されるテンソルと前記（Ｍ−１）個の行列との積を演算する積演算部と
を有する請求項１に記載の情報処理装置。
【請求項３】
前記積演算部は、
前記置換ルールデータを用いて、前記テンソルと前記行列との積を演算するための所定の演算を行う第１の演算部と、
前記第１の演算部による演算結果を保持する演算結果保持部と、
前記演算結果保持部が保持する前記演算結果を利用して、前記テンソルと前記行列との積の演算を行う第２の演算部と
を有する請求項２に記載の情報処理装置。
【請求項４】
前記ＣＳＦ圧縮部は、文法圧縮によって前記ＣＳＦ表現のデータを圧縮し、前記圧縮ＣＳＦデータと、前記置換ルールを表すデータである辞書を出力する
請求項１乃至３のいずれか１項に記載の情報処理装置。
【請求項５】
前記テンソルは、知識グラフである
請求項１乃至４のいずれか１項に記載の情報処理装置。
【請求項６】
ＣＳＦ（Compressed Sparse Fiber）表現のデータにテンソルを変換するためにＭ（ただし、Ｍは３以上の自然数）階以上のテンソルの軸の順序を設定し、
前記設定にしたがい、前記Ｍ階以上のテンソルをＣＳＦ表現のデータに変換し、
前記ＣＳＦ表現のデータに現れる重複構造を、当該重複構造を表す代替構造に置換することにより前記ＣＳＦ表現のデータを圧縮し、圧縮された前記ＣＳＦ表現のデータである圧縮ＣＳＦデータと、置換ルールを示すデータである置換ルールデータとを出力する
テンソル圧縮方法。
【請求項７】
ＣＳＦ（Compressed Sparse Fiber）表現のデータにテンソルを変換するためにＭ（ただし、Ｍは３以上の自然数）階以上のテンソルの軸の順序を設定するＣＳＦ設定ステップと、
前記ＣＳＦ設定ステップでの設定にしたがい、前記Ｍ階以上のテンソルをＣＳＦ表現のデータに変換するＣＳＦ構築ステップと、
前記ＣＳＦ表現のデータに現れる重複構造を、当該重複構造を表す代替構造に置換することにより前記ＣＳＦ表現のデータを圧縮し、圧縮された前記ＣＳＦ表現のデータである圧縮ＣＳＦデータと、置換ルールを示すデータである置換ルールデータとを出力するＣＳＦ圧縮ステップと
をコンピュータに実行させるプログラム。
【国際調査報告】
2020008513.tif 000016
2020008513.tif 000017