(57)【要約】【課題】二値行列とベクトルとの積との演算において一時記憶領域を削減することができる。【解決手段】ＺＤＤ構築部２２によって、入力された二値行列を、ゼロサプレス型二分決定グラフに変換し、残り参照数配列作成部２８によって、中間ノードの親ノードの数である参照数を格納する残り参照数配列を作成し、積計算部３６によって、中間ノードの各々について、一時記憶領域に格納された、中間ノードの各子ノードのスコアと、中間ノードに対応する二値行列の要素、及び乗算すべきＮ次元ベクトルの要素の積との和を、スコアとして算出すると共に、残り参照数配列の子ノードの各々に対する参照数を各々１減算し、０となった要素に対応する中間ノードのスコアが格納された一時記憶領域を未使用にし、かつ、算出されたスコアを、未使用となっている一時記憶領域に格納し、行ノードの子ノードのスコアを積演算の結果として、Ｍ次元ベクトルを出力する。【選択図】図１
2014182615.tif 000002
【特許請求の範囲】
【請求項１】
入力されたＭ行Ｎ列の二値行列とＮ次元ベクトルとの積演算を行う積演算装置であって、
前記二値行列を、値を示す終端ノード、前記二値行列の各行に対応する各行ノード、及び前記二値行列の非ゼロの各要素に対応する各中間ノードを含むゼロサプレス型二分決定グラフ（Zero-suppressed Binary Decision Diagrams）に変換するＺＤＤ構築手段と、
前記ＺＤＤ構築手段により構築されたゼロサプレス型二分決定グラフの中間ノードの各々に対応する各要素を含む配列であり、前記要素の各々に、前記要素に対応する前記中間ノードの親ノードの数である参照数を格納する残り参照数配列を作成する残り参照数配列作成手段と、
前記ゼロサプレス型二分決定グラフの前記終端ノードから前記行ノードに向かう順序で、前記中間ノードの各々について、スコアを算出するスコア算出手段であって、
算出対象の中間ノードの各々について、前記積演算の結果を格納するための一時記憶領域に格納された、前記算出対象の中間ノードの子ノードである各中間ノードのスコアと、前記算出対象の中間ノードに対応する前記二値行列の要素、及び乗算すべき前記Ｎ次元ベクトルの要素の積との和を、前記算出対象の中間ノードのスコアとして算出すると共に、前記残り参照数配列の前記子ノードである中間ノードの各々に対する要素に格納された参照数を各々１減算して前記残り参照数配列の参照数が０となった要素に対応する中間ノードのスコアが格納された前記一時記憶領域を未使用にし、かつ、前記算出された前記算出対象の中間ノードのスコアを、未使用となっている前記一時記憶領域に格納し、
前記行ノードの各々について、前記行ノードの子ノードである中間ノードのスコアを前記一時記憶領域から取得し、前記積演算の結果として、Ｍ次元ベクトルを出力するスコア算出手段と、
を含む積演算装置。
【請求項２】
前記積演算の結果を格納するための一時記憶領域として、少なくともＭ個の要素からなるスコア配列を作成するスコア配列作成手段を更に含み、
前記スコア算出手段は、算出対象の中間ノードの各々について、前記スコア配列に格納された、前記算出対象の中間ノードの各子ノードである中間ノードのスコアと、前記算出対象の中間ノードに対応する前記二値行列の要素、及び乗算すべき前記Ｎ次元ベクトルの要素の積との和を、前記算出対象の中間ノードのスコアとして算出すると共に、前記残り参照数配列の前記子ノードである中間ノードの各々に対する要素に格納された参照数を各々１減算し、前記残り参照数配列の参照数が０となった要素に対応する中間ノードのスコアが格納された、前記スコア配列の要素を未使用にし、かつ、前記算出された前記算出対象の中間ノードのスコアを、未使用となっている前記スコア配列の要素に格納し、
前記行ノードの各々について、前記行ノードの子ノードである中間ノードのスコアを前記スコア配列から取得し、前記積演算の結果として、Ｍ次元ベクトルを出力する請求項１記載の積演算装置。
【請求項３】
入力されたＭ行Ｎ列の二値行列とＮ行Ｇ列の行列との積演算を行う積演算装置であって、
前記二値行列を、値を示す終端ノード、前記二値行列の各行に対応する各行ノード、及び前記二値行列の非ゼロの各要素に対応する各中間ノードを含むゼロサプレス型二分決定グラフ（Zero-suppressed Binary Decision Diagrams）に変換するＺＤＤ構築手段と、
前記ＺＤＤ構築手段により構築されたゼロサプレス型二分決定グラフの中間ノードの各々に対応する各要素を含む配列であり、前記要素の各々に、前記要素に対応する前記中間ノードの親ノードの数である参照数を格納する残り参照数配列を作成する残り参照数配列作成手段と、
前記ゼロサプレス型二分決定グラフの前記終端ノードから前記行ノードに向かう順序で、前記中間ノードの各々について、Ｇ次元のスコアベクトルを算出するスコア算出手段であって、
算出対象の中間ノードの各々について、前記積演算の結果を格納するための一時記憶領域に格納された、前記算出対象の中間ノードの各子ノードである中間ノードのスコアベクトルと、前記算出対象の中間ノードに対応する前記二値行列の要素、及び乗算すべき前記Ｎ行Ｇ列の行列のうちのＧ次元ベクトルの積との和を、前記算出対象の中間ノードのスコアベクトルとして算出すると共に、前記残り参照数配列の前記子ノードである中間ノードの各々に対する要素に格納された参照数を各々１減算し、前記残り参照数配列の参照数が０となった要素に対応する中間ノードのスコアベクトルが格納された前記一時記憶領域を未使用にし、かつ、前記算出された前記算出対象の中間ノードのスコアベクトルを、未使用となっている前記一時記憶領域に格納し、
前記行ノードの各々について、前記行ノードの子ノードである中間ノードのスコアベクトルを前記一時記憶領域から取得し、前記積演算の結果として、Ｍ行Ｇ列の行列を出力するスコア算出手段と、
を含む積演算装置。
【請求項４】
前記積演算の結果を格納するための一時記憶領域として、要素をＧ次元のベクトルとした少なくともＭ個の要素からなるスコア配列を作成するスコア配列作成手段を更に含み、
前記スコア算出手段は、算出対象の中間ノードの各々について、前記スコア配列に格納された、前記算出対象の中間ノードの各子ノードである中間ノードのスコアベクトルと、前記算出対象の中間ノードに対応する前記二値行列の要素、及び乗算すべき前記Ｎ行Ｇ列の行列のうちのＧ次元ベクトルの積との和を、前記算出対象の中間ノードのスコアベクトルとして算出すると共に、前記残り参照数配列の前記子ノードである中間ノードの各々に対する要素に格納された参照数を各々１減算し、前記残り参照数配列の参照数が０となった要素に対応する中間ノードのスコアベクトルが格納された、前記スコア配列の要素を未使用にし、かつ、前記算出された前記算出対象の中間ノードのスコアベクトルを、未使用となっている前記スコア配列の要素に格納し、
前記行ノードの各々について、前記行ノードの子ノードである中間ノードのスコアベクトルを前記スコア配列から取得し、前記積演算の結果として、Ｍ行Ｇ列の行列を出力する請求項３記載の積演算装置。
【請求項５】
ＺＤＤ構築手段と、残り参照数配列作成手段と、スコア算出手段と、を含み、入力されたＭ行Ｎ列の二値行列とＮ次元ベクトルとの積演算を行う積演算装置における積演算方法であって、
前記ＺＤＤ構築手段によって、前記二値行列を、値を示す終端ノード、前記二値行列の各行に対応する各行ノード、及び前記二値行列の非ゼロの各要素に対応する各中間ノードを含むゼロサプレス型二分決定グラフ（Zero-suppressed Binary Decision Diagrams）に変換するステップと、
前記参照数配列作成手段によって、前記ＺＤＤ構築手段により構築されたゼロサプレス型二分決定グラフの中間ノードの各々に対応する各要素を含む配列であり、前記要素の各々に、前記要素に対応する前記中間ノードの親ノードの数である参照数を格納する残り参照数配列を作成するステップと、
前記算出手段によって、前記ゼロサプレス型二分決定グラフの前記終端ノードから前記行ノードに向かう順序で、前記中間ノードの各々について、スコアを算出するステップであって、
前記算出手段によって、算出対象の中間ノードの各々について、前記積演算の結果を格納するための一時記憶領域に格納された、前記算出対象の中間ノードの子ノードである各中間ノードのスコアと、前記算出対象の中間ノードに対応する前記二値行列の要素、及び乗算すべき前記Ｎ次元ベクトルの要素の積との和を、前記算出対象の中間ノードのスコアとして算出すると共に、前記残り参照数配列の前記子ノードである中間ノードの各々に対する要素に格納された参照数を各々１減算して前記残り参照数配列の参照数が０となった要素に対応する中間ノードのスコアが格納された前記一時記憶領域を未使用にし、かつ、前記算出された前記算出対象の中間ノードのスコアを、未使用となっている前記一時記憶領域に格納し、
前記行ノードの各々について、前記行ノードの子ノードである中間ノードのスコアを前記一時記憶領域から取得し、前記積演算の結果として、Ｍ次元ベクトルを出力するステップと、
を含む積演算方法。
【請求項６】
ＺＤＤ構築手段と、残り参照数配列作成手段と、スコア算出手段と、を含み、入力されたＭ行Ｎ列の二値行列とＮ行Ｇ列の行列との積演算を行う積演算装置における積演算方法であって、
前記ＺＤＤ構築手段によって、前記二値行列を、値を示す終端ノード、前記二値行列の各行に対応する各行ノード、及び前記二値行列の非ゼロの各要素に対応する各中間ノードを含むゼロサプレス型二分決定グラフ（Zero-suppressed Binary Decision Diagrams）に変換するステップと、
前記残り参照数配列作成手段によって、前記ＺＤＤ構築手段により構築されたゼロサプレス型二分決定グラフの中間ノードの各々に対応する各要素を含む配列であり、前記要素の各々に、前記要素に対応する前記中間ノードの親ノードの数である参照数を格納する残り参照数配列を作成するステップと、
前記スコア算出手段によって、前記ゼロサプレス型二分決定グラフの前記終端ノードから前記行ノードに向かう順序で、前記中間ノードの各々について、Ｇ次元のスコアベクトルを算出するステップであって、
前記スコア算出手段によって、算出対象の中間ノードの各々について、前記積演算の結果を格納するための一時記憶領域に格納された、前記算出対象の中間ノードの各子ノードである中間ノードのスコアベクトルと、前記算出対象の中間ノードに対応する前記二値行列の要素、及び乗算すべき前記Ｎ行Ｇ列の行列のうちのＧ次元ベクトルの積との和を、前記算出対象の中間ノードのスコアベクトルとして算出すると共に、前記残り参照数配列の前記子ノードである中間ノードの各々に対する要素に格納された参照数を各々１減算し、前記残り参照数配列の参照数が０となった要素に対応する中間ノードのスコアベクトルが格納された前記一時記憶領域を未使用にし、かつ、前記算出された前記算出対象の中間ノードのスコアベクトルを、未使用となっている前記一時記憶領域に格納し、
前記行ノードの各々について、前記行ノードの子ノードである中間ノードのスコアベクトルを前記一時記憶領域から取得し、前記積演算の結果として、Ｍ行Ｇ列の行列を出力するステップと、
を含む積演算方法。
【請求項７】
コンピュータを、請求項１〜４の何れか１項記載の積演算装置を構成する各手段として機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、積演算装置、方法、及びプログラムに係り、特に、二値行列とベクトル又は行列との積の演算を行う積演算装置、方法、及びプログラムに関する。
【背景技術】
【０００２】
行列の積の計算は、様々な工学の分野で用いられる演算であり、その高速化が求められる。一般に、Ｍ行Ｎ列の二値行列と、Ｎ次元ベクトルとの積の計算にはＮ×Ｍ回の要素間の乗算が必要である。ここで、二値行列とは、行列のすべての要素が０あるいは１であるような行列である。
【０００３】
行列が疎な場合、すなわち、行列の大半の要素が零である場合には、すべての要素について計算する代わりに零でない要素についてのみ計算を行うことで高速に計算する方法が広く知られている（非特許文献１）。この場合、行列中の非零要素の個数をＫとすると、Ｋ回の要素間の乗算回数が必要となる。
【０００４】
また、近年、二値行列をゼロサプレス型二分決定グラフ（ＺＤＤ：Zero-suppressed Binary Decision Diagrams）と呼ばれるデータ構造に変換して保持することによって、二値行列に対する乗算を高速に行う手法が提案されている（非特許文献２）。
【０００５】
非特許文献２の手法は、二値行列とベクトルの積の演算に必要な要素間の乗算回数を、変換後のＺＤＤのノード数と同じ数まで減らすことができる。この変換後のＺＤＤのノード数は行列の非零要素数以下であり、非特許文献２によれば約１／２倍程度にできるものとされている。なお、かける側のベクトルの各要素が行ベクトルで表現されていると考えることにより、従来手法を二値行列と一般の行列との積に適用することも可能である。
【先行技術文献】
【非特許文献】
【０００６】
【非特許文献１】Saad, Y, “SPARSKIT: A basic toolkit for sparse matrix compu-tations”, 1994
【非特許文献２】西野正彬, 安田宜仁, 小林透: ZDD を用いた効率的な集合拡張の計算 人工知能学会論文誌Vol. 27, No.2 , pp. 22-27 (2012)
【発明の概要】
【発明が解決しようとする課題】
【０００７】
しかし、上記ＺＤＤを用いた方法を用いて積の計算を行う場合、ＺＤＤのノード数分だけの一時的な記憶領域が必要となってしまうという問題がある。
【０００８】
これは、ＺＤＤのノードを辿りつつ計算を行う際、後のＺＤＤのノードに対応する値を決定するためには、他の決定済みのＺＤＤノードに対応する値を参照する必要があるため、すべてのノードに対応する値を保持する必要があるためである。
【０００９】
非特許文献２によれば、ＺＤＤのノード数は少なくなったとしても元行列の非零の要素数の１／２倍程度であるとされていることから、結果としては、元行列の非零の要素数に比例した一時的な記憶領域が必要になる。もし非零要素が一定割合で出現するような行列の場合、非特許文献２の方法によれば、Ｍ行Ｎ列の行列においてＭ×Ｎに比例した大きさの一時的な記憶領域が必要となる、という問題がある。
【００１０】
一方、ＺＤＤを用いない非特許文献１の方法では、通常一時的な記憶領域はかけるベクトルの次元数分、すなわちＮ個だけで済むことになる。これは、単一要素数からなるベクトルの場合には、これらの差異は大きな問題とはならないが、行列にかけるものが行方向に巨大な行列である場合等は、これらの差は無視できないという問題がある。
【００１１】
本発明では、上記問題点を解決するために成されたものであり、二値行列とベクトル又は行列との積の演算に使用する一時記憶領域を低減することできる積演算装置、方法、及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１２】
上記目的を達成するために、第１の発明に係る積演算装置は、入力されたＭ行Ｎ列の二値行列とＮ次元ベクトルとの積演算を行う積演算装置であって、前記二値行列を、値を示す終端ノード、前記二値行列の各行に対応する各行ノード、及び前記二値行列の非ゼロの各要素に対応する各中間ノードを含むゼロサプレス型二分決定グラフ（Zero-suppressed Binary Decision Diagrams）に変換するＺＤＤ構築手段と、前記ＺＤＤ構築手段により構築されたゼロサプレス型二分決定グラフの中間ノードの各々に対応する各要素を含む配列であり、前記要素の各々に、前記要素に対応する前記中間ノードの親ノードの数である参照数を格納する残り参照数配列を作成する残り参照数配列作成手段と、前記ゼロサプレス型二分決定グラフの前記終端ノードから前記行ノードに向かう順序で、前記中間ノードの各々について、スコアを算出するスコア算出手段であって、算出対象の中間ノードの各々について、前記積演算の結果を格納するための一時記憶領域に格納された、前記算出対象の中間ノードの子ノードである各中間ノードのスコアと、前記算出対象の中間ノードに対応する前記二値行列の要素、及び乗算すべき前記Ｎ次元ベクトルの要素の積との和を、前記算出対象の中間ノードのスコアとして算出すると共に、前記残り参照数配列の前記子ノードである中間ノードの各々に対する要素に格納された参照数を各々１減算して前記残り参照数配列の参照数が０となった要素に対応する中間ノードのスコアが格納された前記一時記憶領域を未使用にし、かつ、前記算出された前記算出対象の中間ノードのスコアを、未使用となっている前記一時記憶領域に格納し、前記行ノードの各々について、前記行ノードの子ノードである中間ノードのスコアを前記一時記憶領域から取得し、前記積演算の結果として、Ｍ次元ベクトルを出力するスコア算出手段と、を含んで構成されている。
【００１３】
第２の発明に係る積演算方法は、ＺＤＤ構築手段と、残り参照数配列作成手段と、スコア算出手段と、を含み、入力されたＭ行Ｎ列の二値行列とＮ次元ベクトルとの積演算を行う積演算装置における積演算方法であって、前記ＺＤＤ構築手段によって、前記二値行列を、値を示す終端ノード、前記二値行列の各行に対応する各行ノード、及び前記二値行列の非ゼロの各要素に対応する各中間ノードを含むゼロサプレス型二分決定グラフ（Zero-suppressed Binary Decision Diagrams）に変換するステップと、前記参照数配列作成手段によって、前記ＺＤＤ構築手段により構築されたゼロサプレス型二分決定グラフの中間ノードの各々に対応する各要素を含む配列であり、前記要素の各々に、前記要素に対応する前記中間ノードの親ノードの数である参照数を格納する残り参照数配列を作成するステップと、前記算出手段によって、前記ゼロサプレス型二分決定グラフの前記終端ノードから前記行ノードに向かう順序で、前記中間ノードの各々について、スコアを算出するステップであって、前記算出手段によって、算出対象の中間ノードの各々について、前記積演算の結果を格納するための一時記憶領域に格納された、前記算出対象の中間ノードの子ノードである各中間ノードのスコアと、前記算出対象の中間ノードに対応する前記二値行列の要素、及び乗算すべき前記Ｎ次元ベクトルの要素の積との和を、前記算出対象の中間ノードのスコアとして算出すると共に、前記残り参照数配列の前記子ノードである中間ノードの各々に対する要素に格納された参照数を各々１減算して前記残り参照数配列の参照数が０となった要素に対応する中間ノードのスコアが格納された前記一時記憶領域を未使用にし、かつ、前記算出された前記算出対象の中間ノードのスコアを、未使用となっている前記一時記憶領域に格納し、前記行ノードの各々について、前記行ノードの子ノードである中間ノードのスコアを前記一時記憶領域から取得し、前記積演算の結果として、Ｍ次元ベクトルを出力する。
【００１４】
第１の発明及び第２の発明によれば、ＺＤＤ構築手段によって、入力された二値行列をゼロサプレス型二分決定グラフに変換し、残り参照数配列作成手段により、中間ノードの親ノードの数である参照数を格納する残り参照数配列を作成する。
【００１５】
そして、スコア算出手段により、中間ノードの各々について、中間ノードの各子ノードである中間ノードのスコアと、中間ノードに対応する二値行列の要素、及び乗算すべきＮ次元ベクトルの要素の積との和を、中間ノードのスコアとして算出すると共に、残り参照数配列の子ノードである中間ノードの各々に対する要素に格納された参照数を各々１減算し、参照数が０となった要素に対応する中間ノードのスコアが格納された一時記憶領域を未使用にし、かつ、算出された中間ノードのスコアを、未使用となっている一時記憶領域に格納し、行ノードの各々について、行ノードの子ノードである中間ノードのスコアを一時記憶領域から取得し、積演算の結果として、Ｍ次元ベクトルを出力する。
【００１６】
このように、第１の発明及び第２の発明によれば、入力された二値行列をゼロサプレス型二分決定グラフに変換し、中間ノードの親ノードの数である参照数を格納する残り参照数配列を作成し、中間ノードの各々について、中間ノードの各子ノードである中間ノードのスコアと、中間ノードに対応する二値行列の要素、及び乗算すべきＮ次元ベクトルの要素の積との和を、中間ノードのスコアとして算出すると共に、残り参照数配列の子ノードである中間ノードの各々に対する要素に格納された参照数を各々１減算し、参照数が０となった要素に対応する中間ノードのスコアが格納された一時記憶領域を未使用にし、かつ、算出された中間ノードのスコアを、未使用となっている一時記憶領域に格納し、行ノードの各々について、行ノードの子ノードである中間ノードのスコアを一時記憶領域から取得し、積演算の結果として、Ｍ次元ベクトルを出力することにより、二値行列とベクトルとの積との演算において利用する一時記憶領域を削減することができる。
【００１７】
また、第１の発明及び第２の発明において、前記積演算の結果を格納するための一時記憶領域として、少なくともＭ個の要素からなるスコア配列を作成するスコア配列作成手段を更に含み、前記スコア算出手段は、算出対象の中間ノードの各々について、前記スコア配列に格納された、前記算出対象の中間ノードの各子ノードである中間ノードのスコアと、前記算出対象の中間ノードに対応する前記二値行列の要素、及び乗算すべき前記Ｎ次元ベクトルの要素の積との和を、前記算出対象の中間ノードのスコアとして算出すると共に、前記残り参照数配列の前記子ノードである中間ノードの各々に対する要素に格納された参照数を各々１減算し、前記残り参照数配列の参照数が０となった要素に対応する中間ノードのスコアが格納された、前記スコア配列の要素を未使用にし、かつ、前記算出された前記算出対象の中間ノードのスコアを、未使用となっている前記スコア配列の要素に格納し、前記行ノードの各々について、前記行ノードの子ノードである中間ノードのスコアを前記スコア配列から取得し、前記積演算の結果として、Ｍ次元ベクトルを出力するようにしてもよい。
【００１８】
第３の発明に係る積演算装置は、入力されたＭ行Ｎ列の二値行列とＮ行Ｇ列の行列との積演算を行う積演算装置であって、前記二値行列を、値を示す終端ノード、前記二値行列の各行に対応する各行ノード、及び前記二値行列の非ゼロの各要素に対応する各中間ノードを含むゼロサプレス型二分決定グラフ（Zero-suppressed Binary Decision Diagrams）に変換するＺＤＤ構築手段と、前記ＺＤＤ構築手段により構築されたゼロサプレス型二分決定グラフの中間ノードの各々に対応する各要素を含む配列であり、前記要素の各々に、前記要素に対応する前記中間ノードの親ノードの数である参照数を格納する残り参照数配列を作成する残り参照数配列作成手段と、前記ゼロサプレス型二分決定グラフの前記終端ノードから前記行ノードに向かう順序で、前記中間ノードの各々について、Ｇ次元のスコアベクトルを算出するスコア算出手段であって、算出対象の中間ノードの各々について、前記積演算の結果を格納するための一時記憶領域に格納された、前記算出対象の中間ノードの各子ノードである中間ノードのスコアベクトルと、前記算出対象の中間ノードに対応する前記二値行列の要素、及び乗算すべき前記Ｎ行Ｇ列の行列のうちのＧ次元ベクトルの積との和を、前記算出対象の中間ノードのスコアベクトルとして算出すると共に、前記残り参照数配列の前記子ノードである中間ノードの各々に対する要素に格納された参照数を各々１減算し、前記残り参照数配列の参照数が０となった要素に対応する中間ノードのスコアベクトルが格納された前記一時記憶領域を未使用にし、かつ、前記算出された前記算出対象の中間ノードのスコアベクトルを、未使用となっている前記一時記憶領域に格納し、前記行ノードの各々について、前記行ノードの子ノードである中間ノードのスコアベクトルを前記一時記憶領域から取得し、前記積演算の結果として、Ｍ行Ｇ列の行列を出力するスコア算出手段と、を含んで構成されている。
【００１９】
第４の発明に係る積演算方法は、ＺＤＤ構築手段と、残り参照数配列作成手段と、スコア算出手段と、を含み、入力されたＭ行Ｎ列の二値行列とＮ行Ｇ列の行列との積演算を行う積演算装置における積演算方法であって、前記ＺＤＤ構築手段によって、前記二値行列を、値を示す終端ノード、前記二値行列の各行に対応する各行ノード、及び前記二値行列の非ゼロの各要素に対応する各中間ノードを含むゼロサプレス型二分決定グラフ（Zero-suppressed Binary Decision Diagrams）に変換するステップと、前記残り参照数配列作成手段によって、前記ＺＤＤ構築手段により構築されたゼロサプレス型二分決定グラフの中間ノードの各々に対応する各要素を含む配列であり、前記要素の各々に、前記要素に対応する前記中間ノードの親ノードの数である参照数を格納する残り参照数配列を作成するステップと、前記スコア算出手段によって、前記ゼロサプレス型二分決定グラフの前記終端ノードから前記行ノードに向かう順序で、前記中間ノードの各々について、Ｇ次元のスコアベクトルを算出するステップであって、前記算出手段によって、算出対象の中間ノードの各々について、前記積演算の結果を格納するための一時記憶領域に格納された、前記算出対象の中間ノードの各子ノードである中間ノードのスコアベクトルと、前記算出対象の中間ノードに対応する前記二値行列の要素、及び乗算すべき前記Ｎ行Ｇ列の行列のうちのＧ次元ベクトルの積との和を、前記算出対象の中間ノードのスコアベクトルとして算出すると共に、前記残り参照数配列の前記子ノードである中間ノードの各々に対する要素に格納された参照数を各々１減算し、前記残り参照数配列の参照数が０となった要素に対応する中間ノードのスコアベクトルが格納された前記一時記憶領域を未使用にし、かつ、前記算出された前記算出対象の中間ノードのスコアベクトルを、未使用となっている前記一時記憶領域に格納し、前記行ノードの各々について、前記行ノードの子ノードである中間ノードのスコアベクトルを前記一時記憶領域から取得し、前記積演算の結果として、Ｍ行Ｇ列の行列を出力する。
【００２０】
第３の発明及び第４の発明によれば、ＺＤＤ構築手段によって、入力された二値行列をゼロサプレス型二分決定グラフに変換し、残り参照数配列作成手段により、中間ノードの親ノードの数である参照数を格納する残り参照数配列を作成する。
【００２１】
そして、スコア算出手段により、中間ノードの各々について、中間ノードの各子ノードである中間ノードのスコアベクトルと、中間ノードに対応する二値行列の要素、及び乗算すべき前記Ｎ行Ｇ列の行列のうちのＧ次元ベクトルの積との和を、中間ノードのスコアベクトルとして算出すると共に、残り参照数配列の子ノードである中間ノードの各々に対する要素に格納された参照数を各々１減算し、参照数が０となった要素に対応する中間ノードのスコアベクトルが格納された一時記憶領域を未使用にし、かつ、算出された中間ノードのスコアベクトルを、未使用となっている一時記憶領域に格納し、行ノードの各々について、行ノードの子ノードである中間ノードのスコアベクトルを一時記憶領域から取得し、積演算の結果として、Ｍ行Ｇ列の行列を出力する。
【００２２】
このように、第３の発明及び第４の発明によれば、入力された二値行列をゼロサプレス型二分決定グラフに変換し、中間ノードの親ノードの数である参照数を格納する残り参照数配列を作成し、中間ノードの各々について、中間ノードの各子ノードである中間ノードのスコアベクトルと、中間ノードに対応する二値行列の要素、及び乗算すべき前記Ｎ行Ｇ列の行列のうちのＧ次元ベクトルの積との和を、中間ノードのスコアベクトルとして算出すると共に、残り参照数配列の子ノードである中間ノードの各々に対する要素に格納された参照数を各々１減算し、参照数が０となった要素に対応する中間ノードのスコアベクトルが格納された一時記憶領域を未使用にし、かつ、算出された中間ノードのスコアベクトルを、未使用となっている一時記憶領域に格納し、行ノードの各々について、行ノードの子ノードである中間ノードのスコアベクトルを一時記憶領域から取得し、積演算の結果として、Ｍ行Ｇ列の行列を出力することにより、二値行列と行列との積との演算において利用する一時記憶領域を削減することができる。
【００２３】
また、本発明のプログラムは、コンピュータを、上記の積演算装置を構成する各手段として機能させるためのプログラムである。
【発明の効果】
【００２４】
以上説明したように、本発明の積演算装置、方法、及びプログラムによれば、二値行列とベクトル又は行列との積演算において利用する一時記憶領域を削減することができる。
【図面の簡単な説明】
【００２５】
【図１】本発明の実施の形態に係る積演算装置の構成を示す概略図である。
【図２】入力される二値行列の例を示す図である。
【図３】二値行列をＺＤＤへ変換した例を示す図である。
【図４】ＺＤＤの簡略表記の例を示す図である。
【図５】ＺＤＤの配列表現の例を示す図である。
【図６】ＺＤＤ配列表現と参照数配列の併記の例を示す図である。
【図７】スコア−ノード対応表の例を示す図である。
【図８】中間ノードのスコアを算出する例を示す図である。
【図９】Ｍ行Ｎ列の二値行列とＮ次元のベクトルとの積の例を示す図である。
【図１０】本発明の実施の形態に係る積演算装置における積演算処理ルーチンを示す図である。
【図１１】本発明の実施の形態に係る積演算装置における積の計算処理ルーチンを示す図である。
【図１２】本発明の実施の形態に係る積演算装置におけるスコア配列未使用位置取得処理ルーチンを示す図である。
【図１３】本発明の実施の形態に係る積演算装置におけるスコア算出処理ルーチンを示す図である。
【発明を実施するための形態】
【００２６】
以下、図面を参照して本発明の第１の実施の形態を詳細に説明する。なお、本発明の第１の実施の形態においては、Ｍ行Ｎ列の二値行列ＸとＮ次元のベクトルｑとの積（ｐ＝Ｘｑ）について説明する。なお、入力ベクトルｑのη（ｉ）番目の要素をｑη（ｉ）と表し、ベクトルの各要素は実数値でもベクトルであっても良い。ここで、η（ｉ）はノードＩＤ＝ｉのノードのラベルを受け取り、当該ラベルの添え字を返す関数である。
【００２７】
＜第１の実施の形態に係る積演算装置の構成＞
本発明の第１の実施の形態に係る積演算装置について説明する。図１に示すように、本発明の実施の形態に係る積演算装置１００は、ＣＰＵと、ＲＡＭと、後述する積演算処理ルーチンを実行するためのプログラムや各種データを記憶したＲＯＭと、を含むコンピュータで構成することが出来る。この積演算装置１００は、機能的には図１に示すように入力部１０と、演算部２０と、出力部５０とを備えている。
【００２８】
入力部１０は、キーボードなどの入力装置から、図２に示すようなＭ行Ｎ列の二値行列Ｘと、Ｎ次元のベクトルｑとを受け付ける。なお、入力部１０は、ネットワーク等を介して外部から入力されたものを受け付けるようにしてもよい。なお、本発明の第１の実施の形態においては、Ｍ行Ｎ列の二値行列Ｘとして、図２に示す４行４列の二値行列が入力され、また、Ｎ次元ベクトルとして、ｑ＝［１，１，０，１］Ｔが入力されたものとして説明する。
【００２９】
演算部２０は、ＺＤＤ構築部２２と、参照数配列作成部２６と、ＺＤＤ記憶部２４と、残り参照数配列作成部２８と、スコア配列作成部３０と、対応配列作成部３２と、配列記憶部３４と、積計算部３６と、を備えている。
【００３０】
ＺＤＤ構築部２２は、入力部１０において受け付けた二値行列Ｘを図３に示すようなＺＤＤのデータ構造に変換する。ＺＤＤは、０、１の値の各々に対する終端ノード、二値行列Ｘの各行に対応する各行ノード、及び二値行列Ｘの非ゼロの各要素に対応する各中間ノードを含む。図３中のＦは始点ノードへのポインタを示し、ｒで始まるラベルがついた各ノード（行ノード）は二値行列Ｘの各行に対応し、ｃで始まるラベルがついた各ノード（中間ノード）は二値行列Ｘの各列に対応している。中間ノードはすべてＬＯ側のリンクが０終端ノードへつながっているため、これらのＬＯ側のリンクを省略し、図４のように表記する。なお、二値行列ＸをＺＤＤのデータ構造に変換する手法については、上記の非特許文献２に記載の方法を用いればよい。
【００３１】
また、このダイヤグラムを図５のように、終端ノードから始点ノードへ向かって順番ににノードＩＤを付し、ノードごとに、ノードＩＤと、ラベルと、ＨＩ側リンクの接続先のノードＩＤと、ＬＯ側リンクの接続先のノードＩＤと、を対応付けた一次元配列で表現し、ＺＤＤ記憶部２４に記憶する。なお、図３及び図４に対応する配列表現を図５左に示し、図５右にＺＤＤの各ノードにノードＩＤを記したものを示す。図５のように、０終端、１終端の２つの終端ノードには、配列番号１、２が割り当てられているとし、配列番号３以降に中間ノードが並び、その後に行ノードが並ぶように構成する。
【００３２】
具体的には、入力部１０により受け付けた二値行列Ｘを組み合わせ集合として表現し、組み合わせ集合で用いられるシンボルの集合Ｓを、Ｓ＝｛r1,...,rM,c1,...,cN｝とする。ここで、r1,...,rMは、それぞれ各行に対応するシンボルであり、c1,...,cNは、それぞれ各列に対応するシンボルとする。これらのシンボルを用いて、Ｘに対応する組み合わせ集合ＺＸを、下記（１）式として表現し、当該組み合わせ集合をＺＤＤとして構築する。
【００３３】
【数１】
2014182615.tif 000003
【００３４】
ここで、aｋ(l)は、k行目のｘkのベクトルの成分xk1,...,xkNのうち、値が１となるl番目の要素の添え字を表す。また、bkはxk1,...,xkNのうち値が１となる要素の総数である。１≦ak（１）＜…＜ak（bk）≦Ｎを満たす。例えば、図２の二値行列Ｘには、組み合わせ集合{r1c1c3,r2c1c2,r3c1c2c4,r4c1c4}が対応する。これをＺＤＤとして表現したものが図３となる。
【００３５】
また、構築されたＺＤＤにはいくつかの特徴がある。まず、ＺＤＤの節点数は、
【００３６】
【数２】
2014182615.tif 000004
【００３７】
以下であり、かつシンボルr1,...,rMに対応する節点は、常に高々一つしか出現しないという特徴がある。また、集合中の２つの項について、ある節点の共有による簡約化はc1,...,cNに対応する節点でのみ起きるようになる。各項に含まれるシンボルのうち、順序的に後にくるものがすべて共通な場合にのみ、ＺＤＤにおいて構造の共有が行われるということになる。図４では、図２の二値行列Ｘの１行目に相当する項がr1c1c3、２行目に相当する項がr2c1c2c3であり、c3に相当する節点で共有されている。
【００３８】
参照数配列作成部２６は、ＺＤＤ記憶部２４に記憶されているＺＤＤについて、各ノードの親ノードの数である参照数を記憶する参照数配列を作成し、ＺＤＤ記憶部２４に記憶する。
【００３９】
具体的には、要素数がＺＤＤのノード数となる配列を作成し、すべての要素を０で初期化する。そして、ノードＩＤが３から最大ノード番号Ｗまでのノードの各々について、ＨＩカラムを参照し、ＨＩカラムの値が３以上であれば、参照数配列のノードＩＤの番号が、ＨＩカラムの値となるノードＩＤに対応する、配列の要素の値に１を加える。また、ＬＯのカラムについても同様に、ノードＩＤが３から最大ノード番号Ｗまでのノードの各々について、ＬＯカラムを参照し、ＬＯカラムの値が３以上であれば、参照数配列のノードＩＤの番号が、ＬＯカラムの値となるノードＩＤに対応する、配列の要素の値に１を加える。また、始点ノードに対応する配列の要素については、便宜上１の値を与える。なお、ノードＩＤが３未満であれば、そのノードは終端ノードに相当するので参照数は考慮しない。また、ＺＤＤ記憶部２４に記憶されている図６に示すような配列表現にカラムを追加して、参照数配列を記憶するようにしても良い。
【００４０】
ＺＤＤ記憶部２４には、ＺＤＤ構築部２２において構築された図５に示すような二値行列ＸのＺＤＤを一次元配列で表現した配列と、参照数配列作成部２６において作成された参照数配列とが記憶されている。
【００４１】
残り参照数配列作成部２８は、ＺＤＤ記憶部２４に記憶されている参照数配列を複製し、残り参照数配列として配列記憶部３４に記憶する。
【００４２】
スコア配列作成部３０は、計算の途中結果を保持するための一時記憶領域としての、中間ノード各々のスコアを保持するための各要素からなるスコア配列を作成し、配列記憶部３４に記憶する。計算の途中結果を保持するために、少なくとも行数分の一時記憶領域が必要であり、第１の実施の形態においては、Ｍ＋１個の要素からなる１次元配列をスコア配列として作成する。なお、このスコア配列をscoreとする。
【００４３】
対応配列作成部３２は、図７に示すように、配列記憶部３４に記憶されているスコア配列の要素が現在どのノードのスコアを格納しているかどうかを管理するための表として、スコア−ノード対応表を作成し、配列記憶部３４に記憶する。スコア−ノード対応表は、Ｍ＋１個の要素からなる配列であり、各要素が０で初期化される。
【００４４】
積計算部３６は、ＺＤＤ記憶部２４に記憶されている二値行列ＸのＺＤＤと、配列記憶部３４に記憶されている残り参照配列、スコア配列、及びスコア−ノード対応表とに基づいて、入力部１０において受け付けたＭ行Ｎ列の二値行列Ｘと、Ｎ次元のベクトルｑとの積（ｐ＝Ｘｑ）の計算を行い、その結果を出力部５０に出力する。
【００４５】
具体的には、ＺＤＤ記憶部２４に記憶されている二値行列ＸのＺＤＤと、入力部１０において受け付けたＮ次元のベクトルｑとを受け付ける。そして、ＺＤＤ記憶部２４に記憶されている二値行列ＸのＺＤＤの構造を利用して、ノードＩＤが３からの中間ノードの各々について、ノードＩＤの昇順に各中間ノードのスコアを算出する。なお、ノードＩＤが１又は２のノードは終端ノードであるので当該ノードのスコアは０とする。
【００４６】
また、中間ノードのスコアを算出する場合には、算出したスコアを格納するため、配列記憶部３４に記憶されているスコア配列の未使用位置を取得する必要がある。そのため、配列記憶部３４に記憶されているスコア−ノード対応表の配列を走査し、値が０となる要素に対応するスコア配列の番地を、未使用位置として取得する。また、スコア−ノード対応表の、スコア配列の未使用位置に対応する要素に、スコアを算出する対象の中間ノードのノードＩＤを格納し、当該未使用位置の番地に対応するスコア配列の要素を０で初期化する。そして、下記（２）式により算出対象の中間ノード（ノードＩＤ＝ｉ）のスコアを算出し、取得した未使用位置であるスコア配列の要素にスコアを格納する。図８に各中間ノードのスコアの算出例を示す。
【００４７】
【数３】
2014182615.tif 000005
【００４８】
ここで、ｉはノードＩＤの値であり、η（ｉ）はノードＩＤ＝ｉのノードのラベルを受け取り、当該ラベルの添え字を返す関数である。例えば、図５を例に示すと、η（３）＝４、η（５）＝２となる。また、ｑη（ｉ）は、入力部１０において受け付けたＮ次元ベクトルｑのη（ｉ）番目の要素であり、ノードＩＤ＝ｉのノードに対応する二値行列Ｘの要素と乗算すべき、ベクトルｑ中の要素である。また、配列記憶部３４に記憶されているスコア−ノード対応表を順に走査し、算出対象の中間ノード（ノードＩＤ＝ｉ）のＨＩ側の子ノードのノードＩＤの値HI(i)が格納されている要素を探索し、探索された当該要素に対応する配列番号が示す、スコア配列の要素に格納されているスコアを取得することでscore[HI(i)]の値を取得する。
【００４９】
そして、配列記憶部３４に記憶されている残り参照配列の、ノードＩＤの値HI(i)に対応する要素の値を１減算し、当該要素の値が０となった場合に、配列記憶部３４に記憶されているスコア−ノード対応表において、ノードＩＤの値HI(i)が格納されている要素の値を０に初期化し、対応するスコア配列の要素が未使用位置であることを示すようにする。
【００５０】
また、中間ノードの全てのスコアが算出された場合、下記（３）式によりｐ１〜Ｍを求め、出力部５０により、ｐ１〜Ｍを各要素とするＭ次元ベクトルｐを、積演算の結果として出力する。図９にｐ１〜Ｍ及びｐの算出例を示す。
【００５１】
【数４】
2014182615.tif 000006
【００５２】
ここで、上記（３）式は、ラベルｒ１〜ｒＭに対応する行ノードの各々について算出される。そのため、当該行ノードの各々に対応するｐη（ｉ）の値はベクトルｐの各要素に該当する。そして、ｐη（ｉ）をメモリ（図示省略）に格納しておき、ラベルｒ１〜ｒＭに対応する全てのノードについてｐη（ｉ）が算出された場合に、ｐη（ｉ）の値を結合しｐとして結果を出力部５０に出力する。
【００５３】
＜第１の実施の形態に係る積演算装置の作用＞
次に、本発明の第１の実施の形態に係る積演算装置１００の作用について説明する。まず、入力部１０により、Ｍ行Ｎ列の二値行列Ｘ及びＮ次元のベクトルｑが入力され、積演算装置１００のＲＯＭに記憶されたプログラムを、ＣＰＵが実行することにより、図１０に示す積演算処理ルーチンが実行される。
【００５４】
まず、ステップＳ１００では、入力部１０により入力されたＭ行Ｎ列の二値行列Ｘ及びＮ次元のベクトルｑを受け付ける。
【００５５】
次に、ステップＳ１０２では、ステップＳ１００において取得したＭ行Ｎ列の二値行列Ｘを、０，１の値の各々に対する終端ノード、二値行列Ｘの各行に対応する各行ノード、及び二値行列Ｘの非ゼロの各要素に対応する各中間ノードを含むＺＤＤのデータ構造に変換し、ＺＤＤ記憶部２４に記憶する。
【００５６】
次に、ステップＳ１０４では、ステップＳ１０２において構築したＺＤＤに基づいて、ＺＤＤの各ノードについて親ノードの数である参照数を各々記憶した参照数配列を作成し、ＺＤＤ記憶部２４に記憶する。
【００５７】
次に、ステップＳ１０６では、ＺＤＤ記憶部２４に記憶されている参照数配列を複製して、残り参照数配列を作成し、配列記憶部３４に記憶する。
【００５８】
次に、ステップＳ１０８では、ステップＳ１００において取得したＭ行Ｎ列の二値行列Ｘ及びＮ次元ベクトルｑに基づいて、計算途中結果を保持するためのＭ＋１個の要素からなる一次元配列のスコア配列を作成する。
【００５９】
次に、ステップＳ１１０では、ステップＳ１０８で作成したスコア配列に対応して、スコア−ノード対応表を作成し、配列記憶部３４に記憶する。
【００６０】
次に、ステップＳ１１２において、ステップＳ１０２において構築した二値行列ＸのＺＤＤと、配列記憶部３４に記憶された残り参照数配列、スコア配列、及びスコア−ノード対応表とに基づいて、ステップＳ１００において受け付けたＭ行Ｎ列の二値行列Ｘと、Ｎ次元のベクトルｑとの積（ｐ＝Ｘｑ）の積を計算し、結果を出力部５０に出力して処理を終了する。
【００６１】
上記ステップＳ１１２は、図１１に示す積の計算処理ルーチンによって実現される。
【００６２】
まず、ステップＳ２００では、変数ｉに初期値として３を与える。
【００６３】
次に、ステップＳ２０２では、ノードＩＤ＝ｉのノードのラベルがＣｈ（ｈ＝１,...,Ｎ）か否かを判定する。ノードＩＤ＝ｉのノードのラベルがＣｈである場合には、ステップＳ２０４に移行し、ノードＩＤ＝ｉのノードのラベルがＣｈでない場合には、ノードＩＤ＝ｉのノードが行ノードであると判断し、ステップＳ２１８へ移行する。
【００６４】
次に、ステップＳ２０４では、配列記憶部３４に記憶されたスコア−ノード対応表に基づいて、配列記憶部３４に記憶されたスコア配列の未使用位置を取得する。
【００６５】
上記ステップＳ２０４は、図１２に示すスコア配列未使用位置取得処理ルーチンによって実現される。
【００６６】
まず、ステップＳ３００では、変数ｊに初期値として０を与える。
【００６７】
次に、ステップＳ３０２では、配列記憶部３４に記憶されたスコア−ノード対応表のｊ番目の要素の値が０か否かを判定する。スコア−ノード対応表のｊ番目の値が０である場合には、スコア配列のｊ番目の要素が未使用であると判断し、ステップＳ３０６に移行し、スコア−ノード対応表のｊ番目の値が０でない場合には、ステップＳ３０４に移行する。
【００６８】
ステップＳ３０４では、変数ｊの値に１を加えた値をｊとする。
【００６９】
次に、ステップＳ３０６では、スコア配列のｊ番目の要素に、ノードＩＤ＝ｉのノードのスコアを格納するために、配列記憶部３４に記憶されたスコア−ノード対応表のｊ番目の要素にノード番号ｉを格納する。
【００７０】
次に、ステップＳ３０８では、配列記憶部３４に記憶されたスコア配列のj番目の要素score[j]の値を０で初期化する。
【００７１】
次に、ステップＳ３１０では、ノードＩＤ＝ｉのノードのスコアを格納するスコア配列の未使用位置として、変数ｊを出力する。
【００７２】
図１１のステップＳ２０６では、ノードＩＤ＝ｉのノードのスコアを算出する。
【００７３】
上記ステップＳ２０６は、図１３に示すスコア算出処理ルーチンによって実現される。
【００７４】
まず、ステップＳ４００では、配列記憶部３４に記憶されたスコア−ノード対応表の要素を順に走査し、ノードＩＤ＝ｉのノードのＨＩ側の子ノードのノードＩＤの値ＨＩ（ｉ）が格納されている要素を探索する。
【００７５】
次に、ステップＳ４０２では、配列記憶部３４に記憶されたスコア−ノード対応表において、上記ステップＳ４００で探索された要素に対応するスコア配列の要素番号を取得し、取得した要素番号に基づいて、スコア配列に格納されている、ノードＩＤ＝ｉのノードのＨＩ側の子ノードのスコアscore［ＨＩ（ｉ）］を取得する。
【００７６】
次に、ステップＳ４０４では、ノードＩＤ＝ｉのノードのラベルの添え字η（ｉ）を取得し、取得したη（ｉ）に基づいて、ステップＳ１００において取得したＮ次元のベクトルｑから、ｑη（ｉ）を取得し、ステップＳ４０２において取得したscore［ＨＩ（ｉ）］の値と、取得したｑη（ｉ）とに基づいて、上記（２）式に従って、ノードＩＤ＝ｉのノードのスコアを算出する。
【００７７】
図１１のステップＳ２０８では、配列記憶部３４に記憶された残り参照数配列から、ノードＩＤ＝ｉのノードのＨＩ側の子ノードのノードＩＤの値ＨＩ（ｉ）に対応する要素を取得し、取得した要素の値を１減算して、配列記憶部３４に記憶された残り参照数配列の当該要素を更新する。
【００７８】
図１１のステップＳ２１０では、上記ステップＳ２０８で更新された、配列記憶部３４に記憶された残り参照数配列の当該要素の値が０か否かを判定する。残り参照数配列の、ノードＩＤ＝ｉのＨＩ側の子ノードに対応する当該要素の値が０である場合にはステップＳ２１２に移行し、残り参照数配列の当該要素の値が０でない場合にはステップＳ２１４に移行する。
【００７９】
次に、ステップＳ２１２では、配列記憶部３４に記憶されたスコア−ノード対応表において、上記ステップＳ４００で探索された、ノードＩＤ＝ｉのノードのＨＩ側の子ノードのノードＩＤの値ＨＩ（ｉ）が格納されている要素の値を０に初期化する。
【００８０】
次に、ステップＳ２１４では、変数ｉの値が最大ノード番号Ｗ未満であるか否かを判定する。変数ｉが最大ノード番号Ｗ未満である場合にはステップＳ２１６に移行し、それ以外の場合にはステップＳ２２０に移行する。
【００８１】
次に、ステップＳ２１６では、変数ｉに１を加えた値を変数ｉとする。
【００８２】
ステップＳ２１８では、ノードＩＤ＝ｉの行ノードについて、スコアノード対応表において、当該行ノードのＨＩ側の子ノードのノードＩＤの値ＨＩ（ｉ）が格納されている要素を探索し、探索された要素に対応するスコア配列の要素番号を取得し、取得した要素番号に基づいて、スコア配列に格納されている、当該行ノードのＨＩ側の子ノードのスコアを取得する。そして、当該行ノードについて、ノードＩＤ＝ｉの当該行ノードのラベルの添え字η（ｉ）を取得し、当該行ノードについて取得したスコアを、積演算の結果であるＭ次元ベクトルの要素ｐη（ｉ）とする。
【００８３】
次に、ステップＳ２２０では、ステップＳ２１８において取得したＭ次元ベクトルの要素ｐ１〜Ｍの結果に基づいて、ｐ１〜Ｍを各要素とするＭ次元ベクトルｐを、積演算の結果として出力部５０に出力して処理を終了する。
【００８４】
以上説明したように、本発明の第１の実施の形態に係る積演算装置によれば、入力された二値行列をゼロサプレス型二分決定グラフに変換し、中間ノードの親ノードの数である参照数を格納する残り参照数配列を作成し、中間ノードの各々について、中間ノードの各子ノードのスコアと、中間ノードに対応する二値行列の要素、及び乗算すべきＮ次元ベクトルの要素の積との和を、中間ノードのスコアとして算出すると共に、残り参照数配列の子ノードの各々に対する要素に格納された参照数を各々１減算し、参照数が０となった要素に対応する中間ノードのスコアが格納されたスコア配列の要素を未使用にし、かつ、算出された中間ノードのスコアを、スコア配列の未使用となっている要素に格納し、行ノードの各々について、行ノードの子ノードのスコアをスコア配列の要素から取得し、積演算の結果として、Ｍ次元ベクトルを出力することにより、二値行列とベクトルとの積との演算において利用するスコア配列の領域を削減することができる。
【００８５】
また、ＺＤＤノード間の参照数を参考にすることで、スコア値を格納する一時的な記憶領域に必要な量を最大で行数分＋１に抑えることができる。
【００８６】
次に、第２の実施の形態について説明する。第２の実施の形態では、二値行列Ｘと行列Ｙとの積を計算する点が第１の実施の形態とは異なる。なお、第１の実施の形態の積演算装置１００と同一の構成となる部分については、同一の符号を付して説明を省略する。
【００８７】
＜第２の実施の形態に係る積演算装置の構成＞
入力部１０は、キーボードなどの入力装置から、図２に示すようなＭ行Ｎ列の二値行列Ｘと、Ｎ行Ｇ列の行列Ｙとを受け付ける。なお、入力部１０は、ネットワーク等を介して外部から入力されたものを受け付けるようにしてもよい。なお、本発明の第２の実施の形態においては、Ｍ行Ｎ列の二値行列Ｘとして、図２に示す４行４列の二値行列が入力されたものとして説明する。
【００８８】
スコア配列作成部３０は、計算の途中結果を保持するための一時記憶領域としての、中間ノード各々のスコアを保持するための各要素からなるスコア配列を作成し、配列記憶部３４に記憶する。計算の途中結果を保持するために、要素をＧ次元のベクトルとすると、少なくとも行数分の要素が必要であり、第２の実施の形態においては、Ｍ＋１個の要素（Ｇ次元ベクトル）からなる１次元配列をスコア配列として作成する。なお、このスコア配列をscoreとする。
【００８９】
積計算部３６は、ＺＤＤ記憶部２４に記憶されている二値行列ＸのＺＤＤと、配列記憶部３４に記憶されている残り参照配列、スコア配列、及びスコア−ノード対応表とに基づいて、入力部１０において受け付けたＭ行Ｎ列の二値行列Ｘと、Ｎ行Ｇ列の行列Ｙとの積（ｐ＝ＸＹ）の計算を行い、その結果を出力部５０に出力する。
【００９０】
具体的には、ＺＤＤ記憶部２４に記憶されている二値行列ＸのＺＤＤと、入力部１０において受け付けたＮ行Ｇ列の行列Ｙとを受け付ける。そして、ＺＤＤ記憶部２４に記憶されている二値行列ＸのＺＤＤの構造を利用して、ノードＩＤが３からの中間ノードの各々について、ノードＩＤの昇順に各中間ノードのスコアベクトルを算出する。なお、ノードＩＤが１又は２のノードは終端ノードであるので当該ノードのスコアベクトルは各値が０のベクトルとする。
【００９１】
また、中間ノードのスコアを算出する場合には、算出したスコアを格納するため、配列記憶部３４に記憶されているスコア配列の未使用位置を取得する必要がある。そのため、配列記憶部３４に記憶されているスコア−ノード対応表の配列を走査し、値が０となる要素に対応するスコア配列の番地を、未使用位置として取得する。また、スコア−ノード対応表の、スコア配列の未使用位置に対応する要素に、スコアを算出する対象の中間ノードのノードＩＤを格納し、当該未使用位置の番地に対応するスコア配列の要素を、各値が０のＧ次元のベクトルで初期化する。そして、下記（４）式により算出対象の中間ノード（ノードＩＤ＝ｉ）のスコアベクトルを算出し、取得した未使用位置であるスコア配列の要素にスコアベクトルを格納する。
【００９２】
【数５】
2014182615.tif 000007
【００９３】
ここで、ｉはノードＩＤの値であり、η（ｉ）はノードＩＤ＝ｉのノードのラベルを受け取り、当該ラベルの添え字を返す関数である。例えば、図５を例に示すと、η（３）＝４、η（５）＝２となる。また、Ｙη（ｉ）は、入力部１０において受け付けたＮ行Ｇ列の行列Ｙのη（ｉ）行目の各要素からなるベクトルであり、ノードＩＤ＝ｉのノードに対応する二値行列Ｘの要素と乗算すべき行列の各要素からなるベクトルである。また、配列記憶部３４に記憶されているスコア−ノード対応表を順に走査し、算出対象の中間ノード（ノードＩＤ＝ｉ）のＨＩ側の子ノードのノードＩＤの値HI(i)が格納されている要素を探索し、探索された当該要素に対応する配列番号が示す、スコア配列の要素に格納されているスコアベクトルを取得することでscore[HI(i)]の値を取得する。
【００９４】
そして、配列記憶部３４に記憶されている残り参照配列の、ノードＩＤの値HI(i)に対応する要素の値を１減算し、当該要素の値が０となった場合に、配列記憶部３４に記憶されているスコア−ノード対応表において、ノードＩＤの値HI(i)が格納されている要素の値を０に初期化し、対応するスコア配列の要素が未使用位置であることを示すようにする。
【００９５】
また、中間ノードの全てのスコアベクトルが算出された場合、上記（３）式によりベクトルｐ１〜Ｍを求め、出力部５０により、ベクトルｐ１〜Ｍを各行に並べたＭ行Ｇ列の行列ｐを、積演算の結果として出力する。
【００９６】
ここで、上記（３）式は、ラベルｒ１〜ｒＭに対応するノードの各々について算出される。そのため、当該ノードの各々に対応するｐη（ｉ）のベクトルはｐの各行に該当する。そして、ｐη（ｉ）をメモリ（図示省略）に格納しておき、ラベルｒ１〜ｒＭに対応する全てのノードについてｐη（ｉ）が算出された場合に、ｐη（ｉ）のベクトルを結合しｐとして結果を出力部５０に出力する。
【００９７】
＜第２の実施の形態に係る積演算装置の作用＞
次に、本発明の第２の実施の形態に係る積演算装置１００の作用について説明する。まず、入力部１０により、Ｍ行Ｎ列の二値行列Ｘ及びＮ行Ｇ列の行列Ｙが入力され、積演算装置１００のＲＯＭに記憶されたプログラムを、ＣＰＵが実行することにより、図１０に示す積演算処理ルーチンが実行される。
【００９８】
まず、ステップＳ１００では、入力部１０により入力されたＭ行Ｎ列の二値行列Ｘ及びＮ行Ｇ列の行列Ｙを受け付ける。
【００９９】
次に、ステップＳ１０２では、ステップＳ１００において取得したＭ行Ｎ列の二値行列Ｘを、０，１の値の各々に対する終端ノード、二値行列Ｘの各行に対応する各行ノード、及び二値行列Ｘの非ゼロの各要素に対応する各中間ノードを含むＺＤＤのデータ構造に変換し、ＺＤＤ記憶部２４に記憶する。
【０１００】
次に、ステップＳ１０４では、ステップＳ１０２において構築したＺＤＤに基づいて、ＺＤＤの各ノードについて親ノードの数である参照数を各々記憶した参照数配列を作成し、ＺＤＤ記憶部２４に記憶する。
【０１０１】
次に、ステップＳ１０６では、ＺＤＤ記憶部２４に記憶されている参照数配列を複製して、残り参照数配列を作成し、配列記憶部３４に記憶する。
【０１０２】
次に、ステップＳ１０８では、ステップＳ１００において取得したＭ行Ｎ列の二値行列Ｘ及びＮ行Ｇ列の行列Ｙに基づいて、計算途中結果を保持するための、各要素をＧ次元ベクトルとしたＭ＋１個の要素からなる一次元配列のスコア配列を作成する。
【０１０３】
次に、ステップＳ１１０では、スコア−ノード対応表を作成し、配列記憶部３４に記憶する。
【０１０４】
次に、ステップＳ１１２において、ステップＳ１０２において構築した二値行列ＸのＺＤＤと、配列記憶部３４に記憶された残り参照数配列、スコア配列、及びスコア−ノード対応表とに基づいて、ステップＳ１００において受け付けたＭ行Ｎ列の二値行列Ｘと、Ｎ行Ｇ列の行列Ｙとの積（ｐ＝ＸＹ）の積を計算し、結果を出力部５０に出力して処理を終了する。
【０１０５】
以上説明したように、本発明の第２の実施の形態に係る積演算装置によれば、入力された二値行列をゼロサプレス型二分決定グラフに変換し、中間ノードの親ノードの数である参照数を格納する残り参照数配列を作成し、中間ノードの各々について、中間ノードの各子ノードのスコアベクトルと、中間ノードに対応する二値行列の要素、及び乗算すべきＮ行Ｇ列の行列の要素からなるベクトルの積との和を、中間ノードのスコアベクトルとして算出すると共に、残り参照数配列の子ノードの各々に対する要素に格納された参照数を各々１減算し、参照数が０となった要素に対応する中間ノードのスコアベクトルが格納されたスコア配列の要素を未使用にし、かつ、算出された中間ノードのスコアベクトルを、スコア配列の未使用となっている要素に格納し、行ノードの各々について、行ノードの子ノードのスコアベクトルをスコア配列の要素から取得し、積演算の結果として、Ｍ行Ｇ列の行列を出力することにより、二値行列と行列との積との演算において利用するスコア配列を削減することができる。
【０１０６】
なお、本発明は、上述した実施形態に限定されるものではなく、この発明の要旨を逸脱しない範囲内で様々な変形や応用が可能である。
【０１０７】
例えば、本実施の形態においては、スコア配列の要素数をＭ＋１とする場合について説明したが、これに限定されるものではなく、スコア配列の要素数をＭ＋１以上としてもよい。
【０１０８】
また、本実施の形態においては、算出対象の中間ノードのスコアを算出する前に、スコアを格納するためのスコア配列の未使用領域を確保する場合について説明したが、これに限定されるものではない。例えば、算出対象の中間ノードのスコアを算出し、当該算出対象の中間ノードのＨＩ側の子ノード（中間ノード）の参照数を１減算し、当該参照数が０となった場合には、当該算出対象の中間ノードのＨＩ側の子ノードのスコアが格納されている、スコア配列の要素を未使用にしてから、算出対象の中間ノードのスコアを格納するための、スコア配列の未使用領域を確保し、当該確保したスコア配列の要素に当該算出対象の中間ノードのスコアを格納するようにしてもよい。この場合、スコア配列の要素数の最小値はＭとなる。
【０１０９】
また、固定数の要素からなるスコア配列を作成してから、ノードの各々のスコアをスコア配列に格納する場合を説明したが、これに限定されるものではない。各スコアを格納する一時記憶領域の数を固定せずに、ＯＳのメモリ管理機構（malloc、free等）を用いてスコアを格納する一時記憶領域を動的に用意するようにしてもよい。この場合、mallocを用いて未使用の一時記憶領域を確保し、残り参照数配列の値が０となった場合にfreeを用いてmallocにより確保した一時記憶領域を未使用にする。なお、この場合、ノードの各々と当該ノードのスコアが格納されている一時記憶領域のアドレスとを対応付ける対応表が必要となる。
【符号の説明】
【０１１０】
１０   入力部
２０   演算部
２２   ＺＤＤ構築部
２４   ＺＤＤ記憶部
２６   参照数配列作成部
２８   残り参照数配列作成部
３０   スコア配列作成部
３２   対応配列作成部
３４   配列記憶部
３６   積計算部
５０   出力部
１００ 積演算装置
【図１】
2014182615.tif 000008
【図２】
2014182615.tif 000009
【図６】
2014182615.tif 000010
【図７】
2014182615.tif 000011
【図３】
2014182615.tif 000012
【図４】
2014182615.tif 000013
【図５】
2014182615.tif 000014
【図８】
2014182615.tif 000015
【図９】
2014182615.tif 000016
【図１０】
2014182615.tif 000017
【図１１】
2014182615.tif 000018
【図１２】
2014182615.tif 000019
【図１３】
2014182615.tif 000020