(57)【要約】【課題】  常に、高速に二値行列と実数ベクトルとの積を計算する。【解決手段】  本発明は、二値行列をゼロサプレス型二分決定グラフ（ZDD）に変換するか、変換せずに該二値行列をそのまま二値行列として計算するかを、該二値行列の非ゼロ要素の密度が大きい程小さな値をとり、行列の階数が小さいほど小さな値をとる関数を用いて算出したスコアに基づいて判定し、ZDDに変換すると判定された場合には、二値行列をZDDに変換し、入力されたN次元実数ベクトルとZDD変換された二値行列との積を計算する。ZDDに変換しないと判定された場合には、ZDDを用いない二値行列とN次元実数ベクトルの積を計算する。【選択図】  図１
2014044540.tif 000002
【特許請求の範囲】
【請求項１】
線形代数におけるベクトルと行列との積を計算するベクトルと行列との積の計算装置であって、
二値行列を取得する二値行列入力手段と、
N次元実数ベクトルを取得するベクトル入力手段と、
前記二値行列をゼロサプレス型二分決定グラフ（ZDD）に変換するか、変換せずに該二値行列をそのまま二値行列として計算するかを、該二値行列の非ゼロ要素の密度が大きい程小さな値をとり、行列の階数が小さいほど小さな値をとる関数を用いて算出したスコアに基づいて判定する判定手段と、
前記判定手段でZDDに変換すると判定された場合には、前記二値行列をZDDに変換し、記憶手段に格納するZDD構築手段と、
前記ベクトル入力手段で取得した前記N次元実数ベクトルと前記記憶手段に格納されているZDD変換された二値行列との積を計算するZDD演算手段と、
前記判定手段でZDDに変換しないと判定された場合には、ZDDを用いない二値行列と前記N次元実数ベクトルの積を計算する行列演算手段と、
を有することを特徴とするベクトルと行列との積の計算装置。
【請求項２】
前記判定手段は、
前記二値行列の非ゼロ要素の密度をσ、一つの二値行列を繰り返し演算用に用いる平均の計算回数をK、行列の階数をrank、実数パラメータをλ1、λ2、ZDDの構築にかかる時間をλ1MN、通常の二値行列とベクトルとの乗算にかかる時間をλ2MN、二値行列をZDDで表現したときに削減される計算される時間の割合を表す関数をh(σ,rank)とし、関数ｈは、σが大きい程小さな値をとる、及び、rankが小さいほど小さな値をとるものとし、
【数３】
2014044540.tif 000005
によりスコアθを算出し、θ＜１の場合には、ZDDに変換すると判定する手段を含む
請求項1記載のベクトルと行列との積の計算装置。
【請求項３】
線形代数におけるベクトルと行列との積を計算するベクトルと行列との積の計算方法であって、
二値行列入力手段と、ベクトル入力手段と、判定手段と、ZDD構築手段と、ZDD演算手段と、記憶手段と、行列演算手段と、を有する装置において、
前記二値行列入力手段が、二値行列を取得する二値行列入力ステップと、
前記判定手段が、前記二値行列をゼロサプレス型二分決定グラフ（ZDD）に変換するか、変換せずに該二値行列をそのまま二値行列として計算するかを、該二値行列の非ゼロ要素の密度が大きい程小さな値をとり、行列の階数が小さいほど小さな値をとる関数を用いて算出したスコアに基づいて判定する判定ステップと、
前記ZDD構築手段が、前記判定ステップでZDDに変換すると判定された場合には、前記二値行列をZDDに変換し、記憶手段に格納するZDD構築ステップと、
前記ベクトル入力手段が、N次元実数ベクトルを取得するベクトル入力ステップと、
前記ZDD演算手段が、前記ベクトル入力ステップで取得した前記N次元実数ベクトルと前記記憶手段に格納されているZDD変換された二値行列との積を計算するZDD演算ステップと、
前記行列演算手段が、前記判定ステップでZDDに変換しないと判定された場合には、ZDDを用いない二値行列と前記N次元実数ベクトルの積を計算する行列演算ステップと、
を行うことを特徴とするベクトルと行列との積の計算方法。
【請求項４】
前記判定ステップにおいて、
前記二値行列の非ゼロ要素の密度をσ、一つの二値行列を繰り返し演算用に用いる平均の計算回数をK、行列の階数をrank、実数パラメータをλ1、λ2、ZDDの構築にかかる時間をλ1MN、通常の二値行列とベクトルとの乗算にかかる時間をλ2MN、二値行列をZDDで表現したときに削減される計算される時間の割合を表す関数をh(σ,rank)とし、関数ｈは、σが大きい程小さな値をとる、及び、rankが小さいほど小さな値をとるものとし、
【数４】
2014044540.tif 000006
によりスコアθを算出し、θ＜１の場合には、ZDDに変換すると判定する
請求項３記載のベクトルと行列との積の計算方法。
【請求項５】
コンピュータを、
請求項１または２に記載のベクトルと行列との積の計算装置の各手段として機能させるためのベクトルと行列との積の計算プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ベクトルと行列との積の計算装置及び方法及びプログラムに係り、特に、線形代数における一般的な演算であるベクトルと行列との積の計算を高速に行うためのベクトルと行列との積の計算装置及び方法及びプログラムに関する。
【背景技術】
【０００２】
ベクトルと行列との積の計算は、様々な工学の分野で用いられる一般的な演算であり、その高速化が求められる。疎な二値行列をゼロサプレス型二分決定グラフ（ZDD）と呼ばれるデータ構造に変換して保持することによって、ベクトルとの積の演算を高速に行う手法が存在する（例えば、非特許文献１）。また、行列とベクトルの積を計算するためには疎な二値行列をZDDに変換する手続を実行する必要があるが、この手続を高速に実行するため、ZDDの簡約規約（削除・共有）がどのような場面で適用されるかを分析し、行列の各列を一度ずつ処理することで規則的用語の既約なZDDを得る方法も提案されている（例えば、非特許文献２）。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】西野 正彬, 安田 宜仁, 小林 透: "ZDD を用いた効率的な集合拡張の計算"、人工知能学会論文誌、 Vol. 27, No. 2, pp. 22-27 (2012)
【非特許文献２】西野 正彬, 安田宜仁, 湊 真一, 片岡 良治, "ZDD を用いた行列圧縮における演算高速化" 人工知能学会第26回全国大会, 2012
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかしながら、非特許文献１のZDDを用いた行列の表によって高速に計算が実行できる場合とそうでない場合とがある。また、非特許文献２の手法によってZDDへの変換が高速にできるとは云え、それでも変換したZDDを何度も利用することがないような場合には、高速に計算が行えない場合がある。
【０００５】
本発明は、上記の点に鑑みなされたもので、常に高速に二値行列と実数ベクトルとの積を計算することが可能なベクトルと行列との積の計算装置及び方法及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００６】
上記の課題を解決するため、本発明（請求項１）は、線形代数におけるベクトルと行列との積を計算するベクトルと行列との積の計算装置であって、
二値行列を取得する二値行列入力手段と、
N次元実数ベクトルを取得するベクトル入力手段と、
前記二値行列をゼロサプレス型二分決定グラフ（ZDD）に変換するか、変換せずに該二値行列をそのまま二値行列として計算するかを、該二値行列の非ゼロ要素の密度が大きい程小さな値をとり、行列の階数が小さいほど小さな値をとる関数を用いて算出したスコアに基づいて判定する判定手段と、
前記判定手段でZDDに変換すると判定された場合には、前記二値行列をZDDに変換し、記憶手段に格納するZDD構築手段と、
前記ベクトル入力手段で取得した前記N次元実数ベクトルと前記記憶手段に格納されているZDD変換された二値行列との積を計算するZDD演算手段と、
前記判定手段でZDDに変換しないと判定された場合には、ZDDを用いない二値行列と前記N次元実数ベクトルの積を計算する行列演算手段と、を有する。
【０００７】
また、本発明（請求項２）は、前記判定手段において、
前記二値行列の非ゼロ要素の密度をσ、一つの二値行列を繰り返し演算用に用いる平均の計算回数をK、行列の階数をrank、実数パラメータをλ1、λ2、ZDDの構築にかかる時間をλ1MN、通常の二値行列とベクトルとの乗算にかかる時間をλ2MN、二値行列をZDDで表現したときに削減される計算される時間の割合を表す関数をh(σ,rank)とし、関数ｈは、σが大きい程小さな値をとる、及び、rankが小さいほど小さな値をとるものとし、
【０００８】
【数１】
2014044540.tif 000003
によりスコアθを算出し、θ＜１の場合には、ZDDに変換すると判定する手段を含む。
【発明の効果】
【０００９】
上述のように本発明によれば、ZDDに変換するかどうかをスコア関数に基づいて判定することで、常に高速に二値行列と実数ベクトルの積を計算することができる。
【図面の簡単な説明】
【００１０】
【図１】本発明の一実施の形態における計算装置の構成図である。
【図２】本発明の一実施の形態における入力される二値行列の例である。
【図３】本発明の一実施の形態における図２の行列に対応するZDDとその計算機上の表現である。
【図４】本発明の一実施の形態における計算装置の処理のフローチャートである。
【発明を実施するための形態】
【００１１】
以下、図面と共に本発明の実施の形態を説明する。
【００１２】
図１は、本発明の一実施の形態における計算装置の構成を示す。
【００１３】
同図に示すベクトルと行列との積の計算装置は、二値行列入力部１、判定処理部２、ZDD構築部３、ZDD演算部４、ベクトル入力部５、行列演算部６、演算結果出力部７を有する。
【００１４】
二値行列入力部１は、Ｍ行Ｎ列の二値行列を入力として受け取る。図２に入力される二値行列の例を示す。
【００１５】
判定処理部２は、入力された二値行列について、非ゼロ成分の比率を求め、非ゼロの比率が大きい程コンパクトなZDDになり変換の効果が大きいと判定する。また、同じ行列を何回使いまわすかを判定する。これは、何度も使いまわすほど変換のオーバヘッド分を補うことができるためである。非ゼロの比率と使いまわす回数のスコア関数を設定し、所定の値と比較することでZDDに変換するか否かを判定する。
【００１６】
ZDD構築部３は、二値行列をZDDに変換する。例えば、図２の二値行列が入力として与えられたならば、図３に示すようなZDDに変換する。
【００１７】
ZDD演算部４は、ZDDに変換された二値行列と、ベクトル入力部５から与えられたＮ次元の実数ベクトルとの積を計算し、メモリ（図示せず）に格納する。
【００１８】
ベクトル入力部５は、行列入力部１から与えられたＭ行Ｎ列の二値行列と乗算を行いたい、Ｎ次元実数ベクトルの入力を受け付け、ZDD演算部４及び行列演算部６に出力する。
【００１９】
行列演算部６は、ZDDを用いない行列とベクトルとの積の計算を行い、メモリ（図示せず）に格納する。
【００２０】
演算結果出力部７は、メモリ（図示せず）からZDD演算部４、行列演算部６の演算結果読み出して出力する。
【００２１】
図４は、本発明の一実施の形態における計算装置の処理のフローチャートである。
【００２２】
ステップ１）  二値行列入力部１が二値行列を受け取る。
【００２３】
ステップ２）  判定処理部２において、二値行列をZDDに変換するか、そうでないかを判定する。変換においては、以下の計算式でスコアθを計算し、メモリ（図示せず）に格納する。
【００２４】
【数２】
2014044540.tif 000004
ここで、MNはM行N列、σは行列の非ゼロ要素の密度、Kは一つの二値行列を繰り返し演算に用いる平均の計算回数、そして、rankは行列の階数を表す。λ1、λ2は、事前に類似した行列で試行することによって得られる実数パラメータであり、λ1MNはZDDの構築にかかる時間、λ2MNは通常の二値行列とベクトルとの乗算にかかる時間を表すようにオペレータが決定し、入力する。h(σ，rank)は二値行列をZDDで表現したときに削減される計算時間の割合を表す関数とする。例えば、ZDDにすることで計算にかかる時間が半分になるなら、h(σ,rank)=0.5とする。関数ｈを
・σが大きい程小さな値をとる；
・rankが小さいほど小さな値をとる；
関数として定義する。
【００２５】
ステップ３）  判定処理部２は、ステップ２で計算したスコアθをメモリ（図示せず）から読み出して、当該スコアθが１より小さいかどうかを判定し、小さいならば構築条件を満たすとしてステップ４に移行する。大きい場合は、構築条件を満たさないとしてステップ６に移行する。
【００２６】
ステップ４）ZDD構築部３で二値行列をZDDに変換し、図３（ｂ）のようにメモリ（図示せず）に格納する。この処理については、非特許文献２の「4. に値行列を表すZDDの構築」の項に記載の処理を利用する。
【００２７】
ステップ５）ZDD演算部４で、ステップ４でメモリ（図示せず）に格納されたZDDとベクトル入力部５より与えられたN次元実数ベクトルとの積を計算し、演算結果出力部７より外部に出力する。ZDDの積の計算は、非特許文献１の「4. ZDDを用いた行列とベクトルの乗算」の項に記載の処理を利用する。
【００２８】
ステップ６）  ステップ３において、構築条件を満たさないと判定された場合は、ZDDへの変換を介さずに、二値行列入力部１から入力された行列とベクトル入力部５から入力されたベクトルとの積を計算する。計算結果は演算結果出力部７より出力される。
【００２９】
なお、上記の図１に示す計算装置の構成要素の動作をプログラムとして構築し、当該計算装置として利用されるコンピュータにインストールして実行させる、または、ネットワークを介して流通させることが可能である。
【００３０】
本発明は、上記の実施の形態に限定されることなく、特許請求の範囲内において、種々変更・応用が可能である。
【符号の説明】
【００３１】
１  二値行列入力部
２  判定処理部
３  ZDD構築部
４  ZDD演算部
５  ベクトル入力部
６  行列演算部
７  演算結果出力部
【図１】
2014044540.tif 000007
【図２】
2014044540.tif 000008
【図３】
2014044540.tif 000009
【図４】
2014044540.tif 000010