(57)【要約】【課題】高い近似計算の精度を維持しつつ、より計算コストが小さく、計算時間の増加を抑えた次元圧縮装置、次元圧縮方法及び次元圧縮プログラムを提供する。【解決手段】ランダム系列の巡回行列又は逆巡回行列をランダム行列として採用する次元圧縮装置とする。また、擬似白色雑音ベクトル処理部と、データサンプルベクトル処理部と、乗算部と、を有する次元圧縮装置とする。なおこの場合において、擬似白色雑音ベクトル処理部は、擬似白色雑音ベクトルｎを作成し、疑似白色雑音ベクトルｎに対し前処理を行いベクトルｒを作成し、ベクトルｒに高速フーリエ変換を施しベクトルｓを作成するようにすることが好ましい。【選択図】図１
2011077958.tif 000002
【特許請求の範囲】
【請求項１】
ランダム系列の巡回行列又は逆巡回行列をランダム行列として採用する次元圧縮装置。
【請求項２】
擬似白色雑音ベクトル処理部と、
データサンプルベクトル処理部と、
乗算部と、を有する次元圧縮装置。
【請求項３】
前記擬似白色雑音ベクトル処理部は、擬似白色雑音ベクトルｎを作成し、前記疑似白色雑音ベクトルｎに対し前処理を行いベクトルｒを作成し、前記ベクトルｒに高速フーリエ変換を施しベクトルｓを作成する請求項２記載の次元圧縮装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、次元圧縮装置、次元圧縮方法及び次元圧縮プログラムに関する。
【背景技術】
【０００２】
一般的な大規模データベースの多くは、大量のサンプル（例えば文書や画像）を蓄積したものであり、類似したサンプルの検索や分類のため、属性と呼ばれる数値（例えば文書の単語の出願頻度や画像の特徴量・画素値及び付加情報）の集合で各サンプルを表すことが多い。属性を成分とするベクトルで各サンプルを表し、ベクトルの内積やノルム等を利用した類似度計算や統計的な処理が必要とされる。
【０００３】
しかしながら、実用上このベクトルの次元数（例えば辞書の単語数、画像の画素数等）は非常に高く、高次元に起因する検索効率等の低下は次元の呪いとして知られている。そこで、次元圧縮又は次元削減（本明細書では単に「次元圧縮」と表現する。）と呼ばれる技術による低次元化によって計算の効率化が図られている。
【０００４】
ところで上記次元圧縮に関する技術の一つとしてランダム射影が知られている。ここで「ランダム射影」とは、ランダムな要素を持つ行列によって高次元ベクトルを低次元ベクトルに線形射影することをいう。公知のランダム射影に関する技術は、例えば下記非特許文献１、２に記載されている。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】Ｓ．Ｓ．Ｖｅｍｐａｌａ，Ｔｈｅ  Ｒａｎｄｏｍ  Ｐｒｏｊｅｃｔｉｏｎ  Ｍｅｔｈｏｄ，Ｖｏｌｕｍｅ６５  ｏｆ  Ｓｅｒｉｅｓ  ｉｎ  Ｄｉｓｃｒｅｔｅ  Ｍａｔｈｅｍａｔｉｃｓ  ａｎｄ  Ｔｈｅｏｒｅｔｉｃａｌ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ，Ａｍｅｒｉｃａｎ  Ｍａｔｈｅｍａｔｉｃａｌ  Ｓｏｃｉｅｔｙ，２００４
【非特許文献２】Ｄ．Ａｃｈｌｉｏｐｔａｓ，Ｄａｔａｂａｓｅ−ｆｒｉｅｎｄｌｙ  ｒａｎｄｏｍ  ｐｒｏｊｅｃｔｉｏｎｓ：  Ｊｏｈｎｓｏｎ−Ｌｉｎｄｅｎｓｔｒａｕｓｓ  ｗｉｔｈ  ｂｉｎａｒｙ  ｃｏｉｎｓ，Ｊｏｕｒｎａｌ  ｏｆ  Ｃｏｍｐｕｔｅｒ  ａｎｄ  Ｓｙｓｔｅｍ  Ｓｃｉｅｎｃｅｓ，６６：６７１−６８７，２００３
【非特許文献３】渡邉達也、瀧本英二、丸岡章，ランダムプロジェクションによる次元圧縮，信学技報ＣＯＭＰ２００１−９２，ｐｐ．７３−７９，電子情報通信学会，２００２
【非特許文献４】大内浩仁、三浦孝夫、塩谷勇，ランダムプロジェクションを用いたニュースストリームの検索，日本データベース学会論文誌（ＤＢＳＪ  Ｌｅｔｔｅｒｓ），Ｖｏｌ．３，Ｎｏ．３，ｐｐ．１−４，２００４
【発明の概要】
【発明が解決しようとする課題】
【０００６】
しかしながら、上記非特許文献により例示されるランダム射影では、射影前後の次元の積のサイズのランダム行列を生成して記憶する必要があり、ランダム行列によるベクトル射影に必要な計算コストが大きくなってしまうといった課題がある。例えば１００万次元、８０００次元の場合、単精度でも約３２ＧＢの記憶領域を要し、その記憶領域は非現実的である。また、ランダム射影に必要な計算時間も射影前後の次元数の積に比例し、近似計算の精度を高めるために射影後の次元数を高くすると計算時間の増加を招いてしまう。
【０００７】
そこで、本発明は、上記課題を鑑み、高い近似計算の精度を維持しつつ、より計算コストが小さく、計算時間の増加を抑えた次元圧縮装置、次元圧縮方法及び次元圧縮プログラムを提供することを目的とする。
【課題を解決するための手段】
【０００８】
上記課題について本発明者らが鋭意検討を行ったところ、ランダム系列の巡回行列又は逆巡回行列をランダム行列として採用することで上記課題を解決することができる点に想到し、本発明を完成させるに至った。
【０００９】
即ち、本発明の一観点に係る次元圧縮装置は、ランダム系列の巡回行列又は逆巡回行列をランダム行列として採用する。
【００１０】
また本発明のための一観点に係る次元圧縮装置は、擬似白色雑音ベクトル処理部と、データサンプルベクトル処理部と、乗算部と、を有する。
【発明の効果】
【００１１】
以上本発明は、高い近似計算の精度を維持しつつ、より計算コストが小さく、計算時間の増加を抑えた次元圧縮装置、次元圧縮方法及び次元圧縮プログラムとなる。
【図面の簡単な説明】
【００１２】
【図１】実施形態に係る機能ブロックを示す図である。
【図２】擬似白色雑音処理部における処理のフローを示す図である。
【図３】擬似処理雑音処理部における前処理のフローを示す図である。
【図４】データサンプルベクトル処理のフローを示す図である。
【図５】乗算部４の処理について示す図である。
【図６】ベクトルｒ、巡回行列Ｒ、ベクトルｂ、対角行列Ｂを示す図である。
【発明を実施するための最良の形態】
【００１３】
以下、本発明の実施形態について図面を参照しつつ説明する。ただし、本発明は多くの異なる態様で実施することが可能であり、以下に示す実施形態に限定されるものではない。
【００１４】
（実施形態１）
図１は、本実施形態に係る次元圧縮装置の機能ブロックを示す図である。本図で示すように本実施形態に係る次元圧縮装置１は、擬似白色雑音ベクトル処理部２と、データサンプルベクトル処理部３と、乗算部４と、を有する。本実施形態に係る次元圧縮装置１は、様々な形で実現可能であり、例えばいわゆるコンピュータのハードディスク等の記録媒体に実行されることで上記各部として機能させるためのコンピュータプログラムを格納させ、これを実行させることで実現することができる。また特に、インターネット上のサーバーの記録媒体にこのプログラムを格納させ、実行することでも実現できる。
【００１５】
擬似白色雑音ベクトル処理部２は、擬似白色雑音ベクトルの作成及び処理を行なうための部であって、限定されるわけではないが、具体的にはＤ次元（Dは正数）の疑似白色雑音ベクトルｎを作成し（Ｓ２１）、この疑似白色雑音ベクトルｎに対し前処理を行いベクトルｒを作成し（Ｓ２２）、このベクトルｒに高速フーリエ変換を施し（Ｓ２３）ベクトルｓを作成する。ここで「擬似白色雑音ベクトル」とは、成分の期待値と相互相関がゼロで、自己相関が定数であるベクトルをいう。また、この高速フーリエ変換が施された後のベクトルｓは、ハードディスク等の記憶領域に記録される。なお、本実施形態に係る擬似白色雑音ベクトル処理部２においては、広く実用されている高速フーリエ変換を用いているが、
整数演算のため専用演算装置をシンプルに実装できる高速ウォルシュ・アダマール変換を利用することも可能である。また、上記いずれの変換において、高速でない場合であっても、計算時間が増大するものの巨大な行列を確保することなくランダム射影できるといった利点が残る。図２に、擬似白色雑音ベクトル処理部の処理のフローについて示す。
【００１６】
ここで前処理（Ｓ２２）とは、本実施形態で圧縮したベクトルを用いた近似計算の精度を改善するために擬似白色雑音ベクトルに施す事前の処理であって、本発明の適用対象に応じて省略可能であるが、一般的には正規化処理を含むことが好ましく、より好ましくは、例えば図３で示すように、平均値除去処理（Ｓ２２１）、第一の正規化処理（Ｓ２２２）、バイアス処理（Ｓ２２３）、第二の正規化処理（Ｓ２２４）を行うことが好ましい。
【００１７】
ここで平均値除去処理（Ｓ２２１）は、ベクトルの成分の平均値が０となるよう各成分から平均値を除去する処理をいう。また第一の正規化処理（Ｓ２２２）は、ベクトルの二乗ノルムが１になるように行う正規化処理をいう。またバイアス処理（Ｓ２２３）は、ベクトルの各成分にＤの平方根の逆数を加算する処理をいう。そして第二の正規化処理（Ｓ２２４）は、ベクトルの二乗ノルムがＤ／Ｋとなるように行う正規化処理をいう。なおここでＫは、射影後の次元数をいう。
【００１８】
また、本実施形態においてデータサンプルベクトル処理部３は、データサンプルに対して処理を行うための部であり、データサンプルを表す入力ベクトルｘに対し、拡散符号ｂとの乗算処理（Ｓ３１）を行なった後、高速フーリエ変換を行い（Ｓ３２）、更に複素共役処理を行い（Ｓ３３）、ベクトルｚを作成する。なおここで「拡散符号」とは、データサンプルを表す入力ベクトルｘと同じ長さのベクトルであって、±１の乱数を要素とするものをいう。図４に、データサンプルベクトル処理部３の処理について示す。
【００１９】
また本実施形態において乗算部４は、上記擬似白色雑音ベクトル部２が作成したベクトルｓと、上記データサンプル処理部３が作成したベクトルｚを成分ごとに乗算し（Ｓ４１）、高速逆フーリエ変換を行い（Ｓ４２）、出力ベクトルｙを作成する。そして、このベクトルｙから任意にＫ個の成分を抽出すれば、ベクトルｘをランダム射影したＫ次元ベクトルを得ることができる。図５に、乗算部４の処理について示す。
【００２０】
ところで、図６で示すように、上記Ｄ次元のベクトルｒを左に巡回して構築した行列（巡回行列）をＲ、Ｄ次元ベクトルｂを要素にもつ対角行列をＢとすると、出力ベクトルｙは入力ベクトルｘを行列ＢとＲで射影したＤ次元ベクトルに等しい。なお、本実施形態の説明では左に巡回して構築した行列を用いているが、上記データサンプルベクトル処理部３における複素共役処理を省略した場合は、右に巡回した行列によるランダム射影となる。巡回の方向は右であっても左であっても良い。
【００２１】
本次元圧縮装置は、白色雑音の性質から、前処理後のベクトルｒとこれを巡回させたベクトルが無相関となる。ゆえに、行列Ｒから任意にＫ本の行ベクトルを取り出すと、サイズがＫ×Ｄのランダム行列となる。この原理によって、本実施形態に係る次元圧縮装置は従来のランダム射影に類似した性質を持つ次元圧縮を実現している。実用上は、ベクトルｎの成分として疑似乱数や無相関な符号｛−１，＋１｝、独立同型分布とみなせる数列等を使用することができる。また従来技術で用いられるランダム行列の任意の１行をベクトルｎとして使用することができる。
【００２２】
以上、本実施形態に係る次元圧縮装置は、ランダム射影で数理的に保証された近似精度について大きな犠牲を払うことなく高い近似計算の精度を維持することができ、更にランダム行列の記憶領域を大きく削減することが可能となり、従来はほぼ不可能であった規模の高次元データにランダム射影を適用することが可能となり、高い近似計算の精度を維持しつつ、より計算コストが小さく、計算時間の増加を抑えた次元圧縮装置、次元圧縮方法及び次元圧縮プログラムを提供することができるようになる。
【産業上の利用可能性】
【００２３】
本次元圧縮装置、次元圧縮方法及び次元圧縮プログラムは、大量のサンプルを蓄積したデータベースにおける類似したサンプルの検索や分類に用いることが可能であり、産業上の利用可能性がある。
【符号の説明】
【００２４】
１…次元圧縮装置、２…擬似白色雑音ベクトル処理部、３…データサンプルベクトル処理部、４…乗算部
【図１】
2011077958.tif 000003
【図２】
2011077958.tif 000004
【図３】
2011077958.tif 000005
【図４】
2011077958.tif 000006
【図５】
2011077958.tif 000007
【図６】
2011077958.tif 000008