(57)【要約】【課題】  任意のベクトル同士の演算量をO(m1)に押さえることを可能にする。【解決手段】  本発明は、処理対象ベクトル記憶手段から読み込んだベクトル（ベクトルA）について、値が０でない要素を何次元目であるかを表す添字と値の組の集合である疎ベクトル表現し、該処理対象ベクトル記憶手段から取得した他方のベクトル（ベクトルB）について、全ての次元に関して該次元を表す添字を指定したときに対応する値を直接アクセスできるように密ベクトル表現し、ベクトルAの疎ベクトル表現の添字集合から添字を順次取り出し、該ベクトルAにおいて該添字に対応する値（値１）を取り出し、ベクトルBにおいて該添字に対応する値（値２）を取り出し、該値１と該値２から部分演算結果を算出して記憶手段の演算結果に加算する。【選択図】  図２
2014002484.tif 000002
【特許請求の範囲】
【請求項１】
２つのベクトルの演算を行うベクトル演算装置であって、
処理対象ベクトルを格納した処理対象ベクトル記憶手段と、
前記処理対象ベクトル記憶手段から読み込んだベクトル（ベクトルA）について、値が０でない要素を何次元目であるかを表す添字と値の組の集合である疎ベクトル表現し、該処理対象ベクトル記憶手段から取得した他方のベクトル（ベクトルB）について、全ての次元に関して該次元を表す添字を指定したときに対応する値を直接アクセスできるように密ベクトル表現するベクトル表現変換手段と、
ベクトルAの疎ベクトル表現の添字集合から添字を順次取り出し、該ベクトルAにおいて該添字に対応する値（値１）を取り出し、ベクトルBにおいて該添字に対応する値（値２）を取り出し、該値１と該値２から部分演算結果を算出して記憶手段の演算結果に加算するベクトル演算手段と、
を有することを特徴とするベクトル演算装置。
【請求項２】
前記ベクトル演算手段は、
前記部分演算として、前記値１と前記値２の積を求める手段を含む
請求項１記載のベクトル演算装置。
【請求項３】
前記ベクトル演算手段は、
前記部分演算として、前記値２と前記値１をα：１−α（０＜α＜１）の重みを付けて加算して得られる値（値３）に対する該値１の比の値（値４）に関して対数を取った値（値５）と該値１との積を求める手段を含む
請求項１記載のベクトル演算装置。
【請求項４】
２つのベクトルの演算を行うベクトル演算方法であって、
処理対象ベクトルを格納した処理対象ベクトル記憶手段と、
ベクトル表現変換手段と、
ベクトル演算手段と、を有する装置において、
前記ベクトル表現変換手段が、前記処理対象ベクトル記憶手段から読み込んだベクトル（ベクトルA）について、値が０でない要素を何次元目であるかを表す添字と値の組の集合である疎ベクトル表現し、該処理対象ベクトル記憶手段から取得した他方のベクトル（ベクトルB）について、全ての次元に関して該次元を表す添字を指定したときに対応する値を直接アクセスできるように密ベクトル表現するベクトル表現変換ステップと、
前記ベクトル演算手段が、ベクトルAの疎ベクトル表現の添字集合から添字を順次取り出し、該ベクトルAにおいて該添字に対応する値（値１）を取り出し、ベクトルBにおいて該添字に対応する値（値２）を取り出し、該値１と該値２から部分演算結果を算出して記憶手段の演算結果に加算するベクトル演算ステップと、
を行うことを特徴とするベクトル演算方法。
【請求項５】
前記ベクトル演算ステップにおいて、
前記部分演算として、前記値１と前記値２の積を求める
請求項４記載のベクトル演算方法。
【請求項６】
前記ベクトル演算ステップにおいて、
前記部分演算として、前記値２と前記値１をα：１−α（０＜α＜１）の重みを付けて加算して得られる値（値３）に対する該値１の比の値（値４）に関して対数を取った値（値５）と該値１との積を求める
請求項４記載のベクトル演算方法。
【請求項７】
コンピュータを、
請求項１乃至３のいずれか１項に記載のベクトル演算装置の各手段として機能させるためのベクトル演算プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ベクトル演算装置及び方法及びプログラムに係り、特に、ベクトル同士の演算を高速に行うためのベクトル演算装置及び方法及びプログラムに関する。
【背景技術】
【０００２】
疎ベクトル同士の内積などの演算について、疎ベクトルを次元を表す添字と対応する値の組として表し、高速に処理を行う方法が知られている（例えば、非特許文献１参照）。当該非特許文献１では、マージソートの考え方を応用した方法、スキップベースの方法、添字番号の集合に対する転置ファイルを利用する方法が示され、２つのベクトルの要素数をｍ1，ｍ2としたとき、それぞれの方法の内積演算１回あたりの計算量はＯ(m1+m2)、O(m1 log m2/m1)、O(m1)であることが示されている。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】岡野原大輔，"超高速テキスト処理のためのアルゴリズムとデータ構造"，NLP2010 チュートリアル資料,  "http://www.ss.cs.tut.ac.jp/nlp2011/nlp2010_tutorial_okanohara.pdf",2010年3月
【発明の概要】
【発明が解決しようとする課題】
【０００４】
上記従来の方法において、マージソートの考え方を利用する方法とスキップベースの方法は、添字が一致する組み合わせの逐次探査処理に計算量を必要とする。一方、添字集合に対する転置ファイルを利用する方法は、転置ファイルを活用することで逐次探索処理をなくし、一方のベクトルの要素数m1のみに依存する計算量O(m1)で内積演算ができる。しかし、転置ファイルを利用する方法は、ベクトル集合が与えられた時に、あるベクトルとそれ以外の全てのベクトルとの内積を計算する場合に限り、１回あたりの内積計算量がO(m1)となるのであり、「全ての」という制約が存在する。そのために、任意のベクトル同士の演算の計算量をO(m1)にはできないという問題がある。また、ベクトルが逐次更新される場合は、転置ファイルの更新コストが掛かるという問題も生じる。
【０００５】
本発明は、上記の点に鑑みなされたもので、任意のベクトル同士の演算量をO(m1)に抑えることが可能なベクトル演算装置及び方法及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００６】
上記の課題を解決するため、本発明（請求項１）は、２つのベクトルの演算を行うベクトル演算装置であって、
処理対象ベクトルを格納した処理対象ベクトル記憶手段と、
前記処理対象ベクトル記憶手段から読み込んだベクトル（ベクトルA）について、値が０でない要素を何次元目であるかを表す添字と値の組の集合である疎ベクトル表現し、該処理対象ベクトル記憶手段から取得した他方のベクトル（ベクトルB）について、全ての次元に関して該次元を表す添字を指定したときに対応する値を直接アクセスできるように密ベクトル表現するベクトル表現変換手段と、
ベクトルAの疎ベクトル表現の添字集合から添字を順次取り出し、該ベクトルAにおいて該添字に対応する値（値１）を取り出し、ベクトルBにおいて該添字に対応する値（値２）を取り出し、該値１と該値２から部分演算結果を算出して記憶手段の演算結果に加算するベクトル演算手段と、を有する。
【０００７】
また、本発明（請求項２）は、前記ベクトル演算手段において、
前記部分演算として、前記値１と前記値２の積を求める手段を含む。
【０００８】
また、本発明（請求項３）は、前記ベクトル演算手段において、
前記部分演算として、前記値２と前記値１をα：１−α（０＜α＜１）の重みを付けて加算して得られる値（値３）に対する該値１の比の値（値４）に関して対数を取った値（値５）と該値１との積を求める手段を含む。
【発明の効果】
【０００９】
上記のように本発明によれば、要素値が０であれば内積に関係しないことに着目し、一方のベクトルから見て０ではない要素に着目し、順に他方のベクトルの要素の乗算値を加算していくことにより、制約を設けずに任意のベクトル同士の演算（内積など）を、一方のベクトルの要素数m1のオーダO(m1)の計算量で実現できるという効果を奏する。
【図面の簡単な説明】
【００１０】
【図１】本発明の一実施の形態における概要動作を示す図である。
【図２】本発明の一実施の形態におけるベクトル演算装置のハードウェア構成図である。
【図３】本発明の一実施の形態におけるCPUの機能を示す図である。
【図４】本発明の一実施の形態におけるベクトル演算装置の動作のフローチャートである。
【発明を実施するための形態】
【００１１】
以下、図面と共に本発明の実施の形態を説明する。
【００１２】
図１は、本発明の一実施の形態における概要動作を示す。
【００１３】
本発明は、２つのベクトルの内積を高速に計算する方法である。本発明では、要素値が０であれば内積には関係しないことに着目する。あるベクトル（ベクトルA）を取得して、値が０ではない要素を何次元目であるかを表す添字と値の組の集合（疎ベクトル）として表現する。また、他のベクトル（ベクトルB）を取得して、全ての次元に関してその次元を表す添字を指定したときに対応する値を直接とりだせるように密ベクトルで表現する。ベクトルAから見て０でない要素だけに着目して順にベクトルＢの要素の演算を行い、その結果を出力する。
【００１４】
図２は、本発明の一実施の形態におけるベクトル演算装置のハードウェア構成を示す。
【００１５】
同図に示すベクトル演算装置１０は、CPU１１、メモリ１２、ディスプレイ１３、キーボード１４、処理プログラム１５、処理対象ベクトル記憶部１６、OS１７を有する。
【００１６】
CPU１１は、図３に示すように、ベクトル取得部１１１、ベクトル表現変換部１１３、ベクトル演算部１１５、演算結果出力部１１７、制御部１１９の機能を有する。
【００１７】
ベクトル取得部１１１は、処理対象ベクトル記憶部１６からベクトルAを取得し、メモリ１２に格納する。
【００１８】
ベクトル表現変換部１１３は、入力されたベクトルAについて、値が０ではない要素を何次元目であるかを表す添字と値の組の集合として表し、疎ベクトルとしてメモリ１２に格納する。また、入力されたベクトルBについて、全ての次元に関してその次元を表す添字を指定した時に対応する値を直接取り出せるように変換し、密ベクトルとしてメモリ１２に格納する。
【００１９】
ベクトル演算部１１５は、ベクトルAの疎ベクトル表現の添字集合から添字を順次取り出し、ベクトルAにおいて添字に対応する値（値1）を取り出し、ベクトルBにおいて当該添字に対応する値（値２）を取り出し、値1と値２の積を求め、その部分演算結果を算出して、メモリ１２の演算結果に加算する。
【００２０】
また、ベクトル演算部１１５は、上記の算出方法以外に、値２と値１をα：１−α（０＜α＜１）の重みを付けて加算して得られる値（値３）に対する値１の比の値（値４）に関して対数を取った値（値５）と該値１との積を求めることにより部分演算結果を算出して、メモリ１２の演算結果に加算してもよい。
【００２１】
演算結果出力部１１７は、メモリ１２から演算結果を読み出して出力する。
【００２２】
以下に、上記の各機能における動作を説明する。
【００２３】
図４は、本発明の一実施の形態におけるベクトル演算装置の動作のフローチャートである。
【００２４】
以下では、ベクトルは、処理対象ベクトル記憶部１６に記憶され、ベクトルの個数はn、ベクトルの次元数はKであるとし、ベクトルにはそれぞれ異なるベクトル番号｛1,…,n｝が付与されているとする。
【００２５】
ステップ１１０）  ベクトル取得部１１１は、処理対象ベクトルを処理対象ベクトル記憶部１６からメモリ１２へ読み込む。
【００２６】
ステップ１２０）  制御部１１９において、ベクトル番号iを１に初期化する。
【００２７】
ステップ１３０）  ベクトル番号がi≦ｎであればステップ１４０に移行し、そうでなければステップ２００に移行する。
【００２８】
ステップ１４０）  ベクトル表現変換部１１３は、メモリ１２から読み出したベクトルiについて、値が０でない要素を順次見つけ、その要素が何次元目であるかを表す添字kと値ｖの組（k,v）を作り（疎ベクトル表現）としてメモリ１２に格納する。
【００２９】
ステップ１５０）  ベクトル表現変換部１１３は、メモリ１２から読み出したベクトルiについて、全ての次元k=1,…,Kに関して、次元を表す添字kが与えられた時に対応する値の記憶アドレスに直接アクセスできるように密ベクトル表現し、メモリ１２に格納する。
【００３０】
ステップ１６０）  ベクトル番号iに１加算し、ステップ１３０に戻る。
【００３１】
ステップ２００）  キーボード１４からベクトルAのベクトル番号iA(1≦iA≦n)とベクトルBのベクトル番号iB(１≦iB≦n)を入力する。
【００３２】
ステップ２１０）  制御部１１９は、メモリ１２上の演算結果を０に初期化する。
【００３３】
ステップ２２０）  ベクトル演算部１１５は、メモリ１２から取得したベクトルiAの疎ベクトル表現における添字集合から先頭の添字kを取り出す。
【００３４】
ステップ２３０）  もし、ベクトルiAの添字集合の終端に達していて、添字が得られなければステップ３００に移行する。
【００３５】
ステップ２４０）  ベクトル演算部１１５は、ベクトルiAについて添字kに対応する値ｖAを取り出し、ベクトルiBについて添字kの次元に対応する値vBを取り出し、vAとvBの積を計算してメモリ１２の演算結果に加算する。
【００３６】
また、値vBと値vAをα：１−α（０＜α＜１）の重みを付けて加算して得られる値Aに対する値vAの比の値（r= vA／A）に関して対数を取った値（log r）とvAとの積を求めてもよい。
【００３７】
ステップ２５０）  ベクトルiAの疎ベクトル表現における添字集合から次の添字kを取り出し、ステップ２３０に戻る。
【００３８】
ステップ３００）  演算結果出力部１１７は、演算結果をメモリ１２から読み出して、ディスプレイ１３に表示して処理を終了する。
【００３９】
なお、上記の図２に示す構成の動作をプログラムとして構築し、処理プログラム１５としてベクトル演算装置１０に格納して実行させる、または、ネットワークを介して流通させることが可能である。
【００４０】
本発明は、上記の実施の形態に限定されることなく、特許請求の範囲内において、種々変更・応用が可能である。
【符号の説明】
【００４１】
１０  ベクトル演算装置
１１  CPU
１２  メモリ
１３  ディスプレイ
１４  キーボード
１５  処理プログラム
１６  処理対象ベクトル記憶部
１７  OS
１１１  ベクトル取得部
１１３  ベクトル表現変換部
１１５  ベクトル演算部
１１７  演算結果出力部
１１９  制御部
【図１】
2014002484.tif 000003
【図２】
2014002484.tif 000004
【図３】
2014002484.tif 000005
【図４】
2014002484.tif 000006