(57)【特許請求の範囲】
【請求項１】
データベースにおいてドキュメントをリトリーブ・ランク付けをするためのコンピュータ・システムであって、
アトリビュート・データから得られる数値データを含むドキュメント・マトリックスを前記ドキュメントから形成する手段と、
前記ドキュメント・マトリックスから共分散マトリックスを形成する手段と、
ニューラル・ネットワーク・アルゴリズムを使用して前記共分散マトリックスの固有値を計算する手段と、
前記固有ベクトルの内積を計算して和Ｓ（ｎ＋χ）
【数１】
0003845553.tif 000017
（上式中、ｅｉ、ｅｊは、固有ベクトルを示す。）を算出し、前回までに計算された和Ｓ（ｎ）と前記和Ｓ（ｎ＋χ）の間の差が所定のしきい値以下となることにより前記和Ｓの収束を判定して、前記固有ベクトルの最終セットを決定する手段と（前記式中、χは、１以上の整数である。）、
前記固有ベクトルのセットを下記式
【数２】
0003845553.tif 000018
（上記式中、Ｋは、共分散マトリックスであり、Ｖは、固有ベクトルからなるマトリックスであり、Σは、対角マトリックスであり、ＶＴは、前記マトリックスＶの転置マトリックスを示す。）にしたがう前記共分散マトリックスの固有値分解に適用する手段と、
前記マトリックスＶに含まれると共に最大の固有値に対応する固有ベクトルを含む所定数の固有ベクトルを用いて前記マトリックスＶの次元を低下させる手段と、
前記ドキュメント・マトリックスに次元が低下されたマトリックスＶの転置マトリックスを乗算して前記ドキュメント・マトリックスの次元を低下させる手段と
を含む、ドキュメントをリトリーブまたはランク付け、またはリトリーブおよびランク付けをするためのコンピュータ・システム。
【請求項２】
前記次元が低下したドキュメント・マトリックスと、クエリーベクトルとの間の内積を計算させることにより、前記データベース内の前記ドキュメントをリトリーブまたはランク付け、またはリトリーブおよびランク付けする手段を含む、
請求項１に記載のコンピュータ・システム。
【請求項３】
前記共分散マトリックスは、下記式
【数３】
0003845553.tif 000019
（上記式中、Ｋは、共分散マトリックスであり、Ｂは、能率マトリックスであり、Ｘｂａｒは、平均ベクトルであり、ＸｂａｒＴは、平均ベクトルＸｂａｒの転置ベクトルを示す。）により算出される、請求項１〜２のいずれか１項に記載のコンピュータ・システム。
【請求項４】
前記所定数は、前記共分散マトリックスの固有ベクトルの総数の１５〜２５％である、請求項１〜３のいずれか１項に記載のコンピュータ・システム。
【請求項５】
データベースにおいてドキュメントをリトリーブ・ランク付けをするためのプログラムであって、前記プログラムは、
アトリビュート・データから得られる数値データを含むドキュメント・マトリックスを前記ドキュメントから形成し、
前記ドキュメント・マトリックスから共分散マトリックスを形成し、
ニューラル・ネットワーク・アルゴリズムを使用して前記共分散マトリックスの固有値を計算させ、
前記固有ベクトルの内積を計算して和Ｓ（ｎ＋χ）
【数４】
0003845553.tif 000020
（上式中、ｅｉ、ｅｊは、固有ベクトルを示す。）を算出し、前回までに計算された和Ｓ（ｎ）と前記和Ｓ（ｎ＋χ）の間の差が所定のしきい値以下となることにより前記和Ｓの収束を判定して、前記固有ベクトルの最終セットを決定し（前記式中、χは、１以上の整数である。）、
前記固有ベクトルのセットを下記式
【数５】
0003845553.tif 000021
（上記式中、Ｋは、共分散マトリックスであり、Ｖは、固有ベクトルからなるマトリックスであり、Σは、対角マトリックスであり、ＶＴは、前記マトリックスＶの転置マトリックスを示す。）にしたがう前記共分散マトリックスの固有値分解に適用し、
前記マトリックスＶに含まれると共に最大の固有値に対応する固有ベクトルを含む所定数の固有ベクトルを用いて前記マトリックスＶの次元を低下させ、
前記ドキュメント・マトリックスに次元が低下されたマトリックスＶの転置マトリックスを乗算して前記ドキュメント・マトリックスの次元を低下させる
ステップをコンピュータに実行させることにより、ドキュメントをリトリーブまたはランク付け、またはリトリーブおよびランク付けをするプログラム。
【請求項６】
さらにコンピュータに、前記次元が低下したドキュメント・マトリックスと、クエリー・ベクトルとの間の内積を計算させることにより、前記データベース内の前記ドキュメントをリトリーブまたはランク付け、またはリトリーブおよびランク付けする、
請求項５に記載のプログラム。
【請求項７】
前記共分散マトリックスは、下記式
【数６】
0003845553.tif 000022
（上記式中、Ｋは、共分散マトリックスであり、Ｂは、能率マトリックスであり、Ｘｂａｒは、平均ベクトルであり、ＸｂａｒＴは、平均ベクトルＸｂａｒの転置ベクトルを示す。）により算出される、請求項５または６に記載のプログラム。
【請求項８】
前記所定数は、前記共分散マトリックスの固有ベクトルの総数の１５〜２５％である、請求項５〜７のいずれか１項に記載のプログラム。
【請求項９】
数値データを含むマトリックスを形成する手段と、
前記マトリックスから共分散マトリックスを形成する手段と、
ニューラル・ネットワーク・アルゴリズムを使用して前記共分散マトリックスの固有値を計算する手段と、
前記固有ベクトルの内積を計算して和Ｓ（ｎ＋χ）
【数７】
0003845553.tif 000023
（上式中、ｅｉ、ｅｊは、固有ベクトルを示す。）を算出し、前回までに計算された和Ｓ（ｎ）と前記和Ｓ（ｎ＋χ）の間の差が所定のしきい値以下となることにより前記和Ｓの収束を判定して、前記固有ベクトルの最終セットを決定する手段と（前記式中、χは、１以上の整数である。）、
前記固有ベクトルのセットを下記式
【数８】
0003845553.tif 000024
（上記式中、Ｋは、共分散マトリックスであり、Ｖは、固有ベクトルからなるマトリックスであり、Σは、対角マトリックスであり、ＶＴは、前記マトリックスＶの転置マトリックスを示す。）にしたがう前記共分散マトリックスの固有値分解に適用する手段と、
前記マトリックスＶに含まれると共に最大の固有値に対応する固有ベクトルを含む所定数の固有ベクトルを用いて前記マトリックスＶの次元を低下させる手段と、
前記ドキュメント・マトリックスに次元が低下されたマトリックスＶの転置マトリックスを乗算して前記ドキュメント・マトリックスの次元を低下させる手段と
を含む、コンピュータ・システム。
【請求項１０】
前記所定数は、前記共分散マトリックスの固有ベクトルの総数の１５〜２５％である、請求項９に記載のコンピュータ・システム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、大きなマトリックスの計算方法に関し、より詳細には、ニューラル・ネットワークを使用する、きわめて大きなデータベース中のドキュメントのランク付けを行うための利便性のあるインタフェイスを提供することが可能な方法、コンピュータ・システムおよびプログラム・プロダクトに関する。
【０００２】
【従来の技術】
近年におけるデータベース・システムは、ニュースデータ、顧客情報、在庫データなどの膨大な量のデータをますます取り扱うようになってきている。このようなデータベースのユーザは、充分な精度をもって迅速、かつ効果的に所望する情報を検索することが、ますます困難となっている。したがって、適時、かつ精度よく、さらには安価に大きなデータベースから新たなトピックスおよび／または新たな事項を検出することは、在庫管理、先物取引やオプション取引、世界中に多数のレポータを配置することなしにレポータへと迅速に指令を行うニュース代理店、成功を収めるためには競合者についての主要、かつ新しい情報を知ることが必要なインターネットや、他の速いペースの行動に基づくビジネスといった、多くのタイプのビジネスに対し、きわめて価値ある情報を与えることになる。
【０００３】
従来ではデータベースの検索者は、検索をモニタするために別の要員を雇用する必要があるので、多くのデータベースにおける新規な事項の検出および追跡は、コストが高く、労力を要し、時間を浪費する作業となっている。
【０００４】
検索エンジンにおける検出および追跡方法は、近年ではデータベース内のデータをクラスタ化するためにベクトルモデルを用いている。この従来の方法は、概ねデータベース内のデータに対応したベクトルｑ（kwd1, kwd2,. . ., kwdn)を形成するものである。このベクトルｑは、kwd1, kwd2,. . ., kwdnといったデータに付されたアトリビュートの数に等しい次元を有するベクトルとして定義される。最も通常の場合には、アトリビュートは、単独のキーワード、フレーズ、人の名前、地名などとされる。通常では数学的にベクトルｑを形成するため、バイナリ・モデルが用いられ、このバイナリ・モデルにおいては、データがkwd1を含まない場合には、kwd1を０に置換し、データがkwd1を含む場合にはkwd1を１へと置換する。ある場合には重み付け因子をバイナリ・モデルと組み合わせて、検索の精度が向上されている。このような重み付け因子としては、例えばデータ中におけるキーワードの出現回数を挙げることができる。
【０００５】
図１には、上述したベクトルから構成されるドキュメント・マトリックスＤの対角化のための典型的な方法を示す。このマトリックスＤは、ｎ×ｎの対称的な正のマトリックスであるものとする。図１に示されるように、ｎ×ｎマトリックスＤは、マトリックスＤのサイズに応じて、２つの代表的な対角化方法により対角化することができる。ｎ×ｎマトリックスＤにおいてｎが比較的小さな場合には、典型的に用いられる方法は、ハウスホルダー・２重対角化法であり、マトリックスＤは、図１（ａ）に示すような２重対角化形態へと変換され、ついで２重化された要素をゼロへと掃き出しを行い、マトリックスＤの固有ベクトルからなるマトリックスＶを得る。
【０００６】
図１（ｂ）には、対角化の別の方法が示されている。図１（ｂ）に示す対角化法は、ｎ×ｎマトリックスＤにおけるｎが、大きいかまたは中程度の場合に有効である。この対角化プロセスは、まず、図１（ｂ）に示すようにLanczos３重対角化を行い、ついでStrumシーケンス化を行って固有値、λ１≧λ２≧．．．≧λｒを決定する。ここで、“ｒ”は、次元が低下されたドキュメント・マトリックスのランクを表す。このプロセスは、ついで逆イタレーションを行い、図１（ｂ）に示されるように予め見出されている固有値に伴う１番目の固有ベクトルを決定する。
【０００７】
データベースのサイズが、ドキュメント・マトリックスＤの固有ベクトルの算出を完了させるため、正確ではあるが労力を要する方法の適用を依然として許容することができる限り、従来の方法は、データベース内のドキュメントをリトリーブし、ランク付けを行うためにきわめて有効である。しかしながら、きわめて大きなデータベースにおいては、ドキュメントのリトリーブやランク付けに要する計算時間は、多くの場合、検索エンジンのユーザにとっては長すぎることになりがちである。また、計算を完了させるためのＣＰＵ性能やメモリ容量といった資源についても限りがある。
【０００８】
したがって、低コストで自動的な方法により、許容可能な計算時間できわめて大きなデータベースにおけるドキュメントを安定的にリトリーブし、かつ安定的にランク付けするための新規な方法を含んだシステムを提供することが必要とされている。
【０００９】
【発明が解決しようとする課題】
いくつかの統計的な手法が、ベクトル空間モデルに基づいた情報リトリーブのためのアルゴリズムを用いて提案されてきている（例えば、Baeza-Yates, R., Riberio-Neo, B., “モダン・インフォメーション・リトリーブ（Modern Information
Retrieval）”,
Addition-Wesley, NY, 1999年、およびManning, C., Shutze, N., 統計的な自然言語処理の原理（“Foundations of Statistical Natural Language Processing）”, MIT Press, Cambridge,
MA, 1999を参照されたい。）。
【００１０】
Salton,
G.,等は、“スマート・リトリーブ・システム−自動化ドキュメント処理における実験（The SMART Retrieval System-Experiments in Automatic Document
Processing）”,
Prentice-Hall, Englewood Cliffs, NJ, 1971年において、ベクトル空間モデルを総説している。彼らは、ベクトルを用いてドキュメントをモデル化しており、ベクトルの各座標軸がベクトルのアトリビュート、例えばキーワードを表すものとされている。ベクトルのバイナリ・モデルにおいては、座標軸は、ドキュメントに当該アトリビュートが含まれていれば１の値とされ、当該アトリビュートがドキュメントに含まれていなければ０とされる。より高度化されたドキュメント・ベクトル・モデルでは、タイトル、セクションヘッダ、要約における出現回数および位置といったキーワードに対する重み付けが考慮される。
【００１１】
クエリーはまた、ドキュメントについて説明したと同一の方法により、ベクトルとしてモデル化される。所定のユーザ入力クエリーに対して、特定のドキュメントの信頼度は、クエリーと、ドキュメント・ベクトルとのそれぞれの間の“距離”を決定することにより算出される。数多くの異なったノルムをクエリー・ベクトルとドキュメント・ベクトルとの間の“距離”計算するために用いることができるが、内積から得られるクエリー・ベクトルとドキュメント・ベクトルとの間の角度が、これらの間の距離を決定するため、最も普通に用いられるものである。
【００１２】
Deerwester等に付与された米国特許第４，８３９，８５３号、名称“ラテント・セマンティック構造を用いたコンピュータ情報リトリーブ（Computer information retrieval using latent semantic structure）”、およびDeerwester等、“ラテント・セマンティック・アナリシスによるインデキシング（Indexing by latent semantic analysis）”, Journal of American Society for
Information Science, Vol. 41, No. 6, 1990, pp. 391-407においては、データベースからドキュメントをリトリーブするためのユニークな方法が開示されている。開示された手順は、おおよそ以下のようなものである。
【００１３】
ステップ１：ドキュメントおよびそれらのアトリビュートのベクトル空間モデル化
ラテント・セマンティック・インデキシング（ＬＳＩ）においては、ドキュメントは、Saltonのベクトル空間モデルと同一の方法においてベクトル化されることにより、モデル化される。ＬＳＩ法においては、クエリーとデータベースのドキュメントとの間の関係は、要素がmn (i, j)により表されるｍ×ｎ行列ＭＮすなわち、
【００１４】
【数９】
0003845553.tif 000002
により表される。ここで、マトリックスＭＮの列は、データベースにおけるドキュメントそれぞれを表すベクトルである。
【００１５】
ステップ２：固有値分解によるランク付け問題の次元低下
ＬＳＩ法の次のステップでは、固有値分解、すなわちマトリックスＭＮのＳＶＤ（Singular Value Decomposition）を実行する。マトリックスＭＮにおけるノイズは、ｋ番目に大きな固有値σｉ、ｉ＝１，２，３，．．．，ｋ，．．．から変更マトリックスＡｋを形成することにより低減され、これらの対応する固有ベクトルは、下記式から得られる。
【００１６】
【数１０】
0003845553.tif 000003
上式中、Σｋは、σ１，σ２，σ３，．．．，σｋである対角要素が単調に減少する、対角化されたマトリックスである。マトリックスＵｋおよびＶｋは、マトリックスＭＮのｋ番目に大きな固有値に対応する右側と左側の固有ベクトルの列を含むマトリックスである。
【００１７】
ステップ３：クエリー処理
ＬＳＩ法に基づいた情報リトリーブにおけるクエリーの処理は、さらに２つのステップ、（１）クエリー射影ステップおよびそれに続いた（２）適合化ステップを含む。クエリー射影ステップでは、入力されたクエリーは、マトリックスＵｋにより次元が低減されたクエリー−ドキュメント空間における擬ドキュメントへとマップされ、その後ランクが低減された固有値マトリックスΣｋからの対応する固有値σｉにより重み付けされる。このプロセスは、数学的には以下のように記述される。
【００１８】
【数１１】
0003845553.tif 000004
上式中、ｑは、元のクエリー・ベクトルであり、ｈａｔ｛ｑ｝は、擬ドキュメント・ベクトルであり、ｑＴは、ｑの転置ベクトルであり、｛−１｝は、逆数演算子である。第２のステップでは、擬ドキュメント・ベクトルｈａｔ｛ｑ｝と、次元が低減されたドキュメント空間ＶｋＴとは同様に、多くの類似する方法のいずれか１つを用いることによって算出される。
【００１９】
一方で、ニューラル・ネットワークは、GolubおよびVan Loan、１９９６年（マトリックス計算、第３版、ジョーンズ・ホプキンス大学プレス、バルチモア、ＭＤ、１９９６年）において総説されているように、しばしばマトリックスの固有値および固有ベクトルを算出するために用いられている。固有値および固有ベクトルのためのニューラル・ネットワークを使用する別の計算方法は、Haykin（ニューラル・ネットワークス：総括的原理、第２版、プレンティス−ホール、アッパー・サドル・リバー、ＮＪ、１９９９年）により報告されている。
【００２０】
ニューラル・ネットワークを使用する上述した計算は、計算時間の削減およびメモリ資源の節約において効果的であるものの、計算の信頼性について下記に挙げるいくつかの問題があった。
（１）ニューラル・ネットワーク反復のための停止基準が明確に理解されておらず、保証された信頼限界がいかなる理論によっても利用できないこと、および
（２）ニューラル・ネットワークの計算においては、オーバー・フィッティングが共通する問題となること、である。
【００２１】
【課題を解決するための手段】
本発明は、部分的には共分散マトリックスを使用した固有ベクトルの内積の合計の収束を示す基準を与えることにより、大きなデータベースの固有値および固有ベクトルの計算を著しく改善することができるという認識の下になされたものである。
【００２２】
【００２３】
【００２４】
【００２５】
本発明の第１の構成によれば、データベースにおいてドキュメントをリトリーブ・ランク付けをするためのコンピュータ・システムであって、
アトリビュート・データから得られる数値データを含むドキュメント・マトリックスを前記ドキュメントから形成する手段と、
前記ドキュメント・マトリックスから共分散マトリックスを形成するステップと、
ニューラル・ネットワーク・アルゴリズムを使用して前記共分散マトリックスの固有値を計算する手段と、
前記固有ベクトルの内積を計算して和Ｓ（ｎ＋χ）
【００２６】
【数１２】
0003845553.tif 000005
（上式中、ｅｉ、ｅｊは、固有ベクトルを示す。）を算出し、前回までに計算された和Ｓ（ｎ）と前記和Ｓ（ｎ＋χ）の間の差が所定のしきい値以下となることにより前記和Ｓの収束を判定して、前記固有ベクトルの最終セットを決定する手段と（前記式中、χは、１以上の整数である。）、
前記固有ベクトルのセットを下記式
【００２７】
【数１３】
0003845553.tif 000006
（上記式中、Ｋは、共分散マトリックスであり、Ｖは、固有ベクトルからなるマトリックスであり、Σは、対角マトリックスであり、ＶＴは、前記マトリックスＶの転置マトリックスを示す。）にしたがう前記共分散マトリックスの固有値分解に適用する手段と、
前記マトリックスＶに含まれると共に最大の固有値に対応する固有ベクトルを含む所定数の固有ベクトルを用いて前記マトリックスＶの次元を低下させる手段と、
前記ドキュメント・マトリックスに次元が低下されたマトリックスＶの転置マトリックスを乗算して前記ドキュメント・マトリックスの次元を低下させる手段と
を含む、ドキュメントをリトリーブまたはランク付け、またはリトリーブおよびランク付けをするためのコンピュータ・システムが提供される。
【００２８】
本発明の第２の構成によれば、データベースにおいてドキュメントをリトリーブ・ランク付けをするためのプログラム・プロダクトであって、
アトリビュート・データから得られる数値データを含むドキュメント・マトリックスを前記ドキュメントから形成し、
前記ドキュメント・マトリックスから共分散マトリックスを形成し、
ニューラル・ネットワーク・アルゴリズムを使用して前記共分散マトリックスの固有値を計算させ、
前記固有ベクトルの内積を計算して和Ｓ（ｎ＋χ）
【００２９】
【数１４】
0003845553.tif 000007
（上式中、ｅｉ、ｅｊは、固有ベクトルを示す。）を算出し、前回までに計算された和Ｓ（ｎ）と前記和Ｓ（ｎ＋χ）の間の差が所定のしきい値以下となることにより前記和Ｓの収束を判定して、前記固有ベクトルの最終セットを決定し（前記式中、χは、１以上の整数である。）、
前記固有ベクトルのセットを下記式
【００３０】
【数１５】
0003845553.tif 000008
（上記式中、Ｋは、共分散マトリックスであり、Ｖは、固有ベクトルからなるマトリックスであり、Σは、対角マトリックスであり、ＶＴは、前記マトリックスＶの転置マトリックスを示す。）にしたがう前記共分散マトリックスの固有値分解に適用し、
前記マトリックスＶに含まれると共に最大の固有値に対応する固有ベクトルを含む所定数の固有ベクトルを用いて前記マトリックスＶの次元を低下させ、
前記ドキュメント・マトリックスに次元が低下されたマトリックスＶの転置マトリックスを乗算して前記ドキュメント・マトリックスの次元を低下させる
ドキュメントをリトリーブまたはランク付け、またはリトリーブおよびランク付けをするためのプログラム・プロダクトが提供される。
【００３１】
本発明の第３の構成によれば、数値データを含むマトリックスを形成する手段と、
前記マトリックスから共分散マトリックスを形成するステップと、
ニューラル・ネットワーク・アルゴリズムを使用して前記共分散マトリックスの固有値を計算する手段と、
前記固有ベクトルの内積を計算して和Ｓ（ｎ＋χ）
【００３２】
【数１６】
0003845553.tif 000009
（上式中、ｅｉ、ｅｊは、固有ベクトルを示す。）を算出し、前回までに計算された和Ｓ（ｎ）と前記和Ｓ（ｎ＋χ）の間の差が所定のしきい値以下となることにより前記和Ｓの収束を判定して、前記固有ベクトルの最終セットを決定する手段と（前記式中、χは、１以上の整数である。）、
前記固有ベクトルのセットを下記式
【００３３】
【数１７】
0003845553.tif 000010
（上記式中、Ｋは、共分散マトリックスであり、Ｖは、固有ベクトルからなるマトリックスであり、Σは、対角マトリックスであり、ＶＴは、前記マトリックスＶの転置マトリックスを示す。）にしたがう前記共分散マトリックスの固有値分解に適用する手段と、
前記マトリックスＶに含まれると共に最大の固有値に対応する固有ベクトルを含む所定数の固有ベクトルを用いて前記マトリックスＶの次元を低下させる手段と、
前記ドキュメント・マトリックスに次元が低下されたマトリックスＶの転置マトリックスを乗算して前記ドキュメント・マトリックスの次元を低下させる手段と
を含む、コンピュータ・システムが提供される。
【００３４】
【発明の実施の形態】
以下、本発明を図面に示した態様をもって説明するが、本発明は、後述する態様に制限されるものではない。
【００３５】
１．  ドキュメントのリトリーブおよびランキングの概略的手順
図２は、本発明の方法を概略的に示したフローチャートである。本発明の方法は、ステップ２０１から開始し、ステップ２０２へと進んでドキュメント・マトリックスＤ（ｍ×ｎマトリックス）を、ドキュメントに含まれたキーワードから形成する。時間、日付、月、年、およびこれらのいかなる組み合わせにおいて、タイムスタンプを同時に用いることも可能である。
【００３６】
この方法は、その後ステップ２０３へと進んでドキュメント・ベクトルの平均ベクトルＸｂａｒを算出する。さらにこの方法は、ステップ２０４へと進んで能率マトリックスＢ＝ＤＴ・Ｄ／ｎを算出する。ここで、Ｂは、能率マトリックスであり、ＤＴは、ドキュメント・マトリックスＤの転置マトリックスである。ついで、本発明の方法は、ステップ２０５に進み、下記式を用いて共分散マトリックスＫを算出する。
【００３７】
【数１８】
0003845553.tif 000011
上式中、ＸｂａｒＴは、平均ベクトルＸｂａｒの転置ベクトルを示す。
【００３８】
本発明の方法は、その後ステップ２０６へと進んで、共分散マトリックスＫの固有値分解を下記式に示すように実行する。
【００３９】
【数１９】
0003845553.tif 000012
上式中、共分散マトリックスＫのランク、すなわちｒａｎｋ（Ｋ）は、ｒである。
【００４０】
本発明の方法は、ステップ２０７へと進んで、ニューラル・ネットワーク・アルゴリズムを使用して大きな方から例えば１５〜２５％といった予め定められた数の固有値から計算される固有ベクトルの内積の合計を計算し、後の手順のために使用する固有ベクトルのセットを得る。
【００４１】
その後、本発明の方法は、ステップ２０８へと進んで、大きい方から１５％〜２５％の固有値を有する固有ベクトルに対応する所定数ｋを含ませて、次元の低下したマトリックスＶｋを形成することで、マトリックスＶの次元を減少させる。本発明の方法は、その後ステップ２０９へと進んで次元の低下したマトリックスＶｋを用いてドキュメント・マトリックスの次元を低下させ、同時にステップ２０９に示されているようなＤｏｃ／Ｋｗｄクエリー検索、新規事項検出、追跡といったクエリー・ベクトルについて、リトリーブおよびランク付けを行うために用いられるドキュメント・サブスペースである、次元が低下したドキュメント・マトリックスを形成する。以下、本発明の本質的なステップについて、詳細に説明する。
【００４２】
２．ドキュメント・マトリックスの形成
図３は、ドキュメント・マトリックスＤを例示した図である。マトリックスＤは、ドキュメント１（doc 1）からドキュメントｎ（doc n）までの行から構成されており、各行は、特定のドキュメントに含まれるキーワード（kwd1,..., kwdn）から得られた要素を含んでいる。ドキュメントの数およびキーワードの数は、本発明においては制限されるものではなく、ドキュメントおよびデータベースのサイズに依存する。図３においては、ドキュメント・マトリックスＤの要素は、数値１により示されているが、他の正の実数は、ドキュメント・マトリックスＤを形成するために重み付け因子を用いる場合には用いることができる。
【００４３】
図４には、ドキュメント・マトリックスを形成する実際の手順を示す。図４（ａ）では、ドキュメントがＳＧＭＬフォーマットにおいて記述されているものとしている。本発明の方法は、ドキュメントに基づいて、リトリーブおよびランク付けを行うためのキーワードを発生させ、その後ドキュメントのフォーマットを、本発明の方法において好適に用いることができる図４（ｂ）に示すような別のフォーマットへと変換する。ドキュメントのフォーマットは、ＳＧＭＬに限定されるものではなく、別のフォーマットであっても本発明においては用いることができる。
【００４４】
図４（ａ）を用いて、アトリビュートの発生手順を説明する。例えば、アトリビュートは、キーワードとすることができる。キーワード発生は、以下のようにして行うことができる。
（１）キャピタル文字の単語を抽出する、
（２）順序付けする、
（３）出現回数を算出する、
（４）ｎ＞Ｍａｘまたはｎ＜Ｍｉｎであれば単語を削除する、
（５）単独の単語（例えばＴｈｅ、Ａ、Ａｎｄ、Ｔｈｅｒｅなど）を除去する、などである。
【００４５】
ここで、Ｍａｘは、キーワードあたりの所定の最大出現回数であり、Ｍｉｎは、キーワードあたりの所定の最小出現回数である。（４）に示した手順は、精度を向上させるために多くの場合に有効である。上述の手順を実行する順序については実質的な制限はなく、上述した手順の順序は、用いるシステムの条件、プログラミングの便宜を考慮して決定することができる。上述した手順は、キーワード発生手順の１つの例を示したにすぎず、多くの別の手順も本発明において用いることができる。
【００４６】
キーワードを発生させ、ＳＧＭＬフォーマットを変換した後に構成されたのが、図３に示したドキュメント・マトリックスである。バイナリ・モデルを用い、重み付け因子および／または関数を用いない場合のドキュメント・ベクトル／マトリックスを形成させるための疑似コードを以下に示す。
【００４７】
REM:No Weighting factor and/or function
If kwd (j) appears in doc (i)
Then M (i, j) = 1
Otherwise M (i, j) = 0
同時にタイムスタンプを用いる場合には、タイムスタンプについても同様の手順を適用することができる。
【００４８】
本発明は、ドキュメント・マトリックスＤを形成する場合に、重み付け因子および／または重み付け関数をキーワードおよびタイムスタンプの双方について用いることができる。キーワードＷｋについての重み付け因子および／または重み付け関数としては、ドキュメントにおけるキーワードの出現回数、ドキュメントにおけるキーワードの位置、キーワードがキャピタルで記載されているか否か、を挙げることができるが、これらに制限されるものではない。タイムスタンプについての重み付け因子および／または重み付け関数ＷＴは、また本発明によればキーワードと同様に時間／日付スタンプを得る場合にも適用することができる。
【００４９】
３．共分散マトリックスの生成
共分散マトリックスの形成は、図５に示すように平均ベクトルＸｂａｒを算出するステップ５０２と、能率マトリックスを算出するステップ５０３と、共分散マトリックスを算出するステップ５０４と、ニューラル・ネットワークにより固有ベクトルを決定するステップ５０５とを含む、概ね４つのステップを含んでいる。図６は、図５に示した手順の詳細を示す。平均ベクトルＸｂａｒは、図６（ａ）に示すようにドキュメント・マトリックスＤの転置マトリックスの各行の要素を加算し、ドキュメント数、すなわちｎにより要素の和を除算することにより得られる。平均ベクトルＸｂａｒの構成を図６（ｂ）に示す。ドキュメント・マトリックスの転置マトリックスＤＴは、ｎ×ｍ要素を含み、Ｘｂａｒは、ＡＴの同一の行における要素の平均値から構成される列ベクトルを１列だけから構成される。
【００５０】
ステップ５０３においては、能率マトリックスＢを、下記式により算出する。
【００５１】
【数２０】
0003845553.tif 000013
上式中、Ｄは、ドキュメント・マトリックスであり、ＤＴは、その転置マトリックスである。ついで、この手順では、ステップ５０４において共分散マトリックスＫを、平均ベクトルＸｂａｒおよび能率マトリックスＢから算出する。
【００５２】
【数２１】
0003845553.tif 000014
【００５３】
４．共分散マトリックスの固有値の計算
得られた共分散マトリックスＫは対称、正の準正規なｎ×ｎ構造を有しており、本発明の方法は、共分散マトリックスＫの固有値および固有ベクトルを計算するためにニューラル・ネットワークを使用する。ニューラル・ネットワークを使用する固有値および固有ベクトルの計算の詳細については、GolubおよびVan Loan、およびHaykinに詳細に示されている方法に従うことができる。
【００５４】
ついで、算出された固有ベクトルを使用して上述した内積の和Ｓ（ｎ）
【００５５】
【数２２】
0003845553.tif 000015
を算出する。
【００５６】
上記式中、ｅｉおよびｅｊは、ｉ番目およびｊ番目の固有ベクトルで、ニューラル・ネットワークによりそれぞれ規格化された単位長さを有するベクトルであり、ｎは、ニューラル・ネットワークを使用する計算の反復数である。和Ｓ（ｎ）を、計算機資源を節約するため、大きな方から１５から２０％の固有値を使用して算出したが、その結果は、本発明においては実質的な影響を与えるものではない。本発明においては、次いで、上述した和を、例えば近接する合計Ｓ（ｎ）とＳ（ｎ＋χ）との間で比較する。ここで、χは、１以上の整数である。和の差、
【００５７】
【数２３】
0003845553.tif 000016
が、所定のしきい値以下となる場合に、本発明の手順はニューラル・ネットワーク計算の反復を停止し、その時点における固有ベクトルを得、共分散マトリックスの次元低下の計算を実行させる。この際のしきい値は、反復の収束を保証できる限り、いかなる値でも使用することができる。図７は、和Ｓの概ねの収束概要を、大きい方から１００個の固有ベクトルを使用して合計された反復サイクルについて示した図である。クロスハッチを付した領域は、算出された最も大きな方から２つの固有ベクトル（すなわち、最も大きな固有値に対応する固有ベクトル、またはユーザにより特定されるいかなる固有ベクトルであってもよい）の内積を含む内積の和である。
【００５８】
図７に示すように、和Ｓ（ｎ）は、反復のサイクル数につれて小さくなっているのがわかる。和の差εが所定のしきい値以下になると、反復が停止されて固有ベクトルのセットが決定される。本発明においては、図７に示される和Ｓの収束をクライアント・コンピュータといったコンピュータ・システムのディスプレイ・スクリーンに表示させ、ユーザが収束の状態を認識できるようにさせることも可能である。本発明においては、和を取る際の固有値の数には実質的な制限はなく、大きい方から２００、４００、５００の固有ベクトルを使用することも可能である。
【００５９】
本発明の別の実施の形態においては、それぞれ見積もられた固有値Ｖに共分散マトリックスを乗じてＶ′を生成することもできる。解が完全で、乗算が完全であれば、Ｖは、Ｖ′に等しくなるはずである。この場合には、ニューラル・ネットワーク計算の誤差を判断するために、Ｖと、Ｖ′との間の角度を使用することも可能である。
【００６０】
本発明のさらに別の実施の形態においては、座標軸の回転が可能かどうかの判断を含ませることも可能である。このような計算は、例えば回転された座標系における固有ベクトルの内積の和を算出し、この和の収束を上述したようにして検討することができる。このような計算は、また例えば共分散マトリックスＶｎｅｗと、ニューラル・ネットワークを用いて算出された固有ベクトルＶとの間の内積を算出させ、内積Ｖｎｅｗ・Ｖがゼロか、またはきわめて小さいかを判断することにより行うことができる。
【００６１】
マトリックスＶの次元減少は、最大の固有値に対応する固有ベクトルを含む複数の固有ベクトルの所定の数ｋを選択して、ｋ×ｍのマトリックスＶｋを生成するようにして実行することができる。本発明によれば、固有ベクトルの選択は、固有ベクトルが大きな方からｋの固有値に対応する固有ベクトルを含んでいる限り、種々の方法において実行することができる。数値ｋには実質的な制限はないものの、整数値ｋは、固有ベクトルの全数の約１５％〜２５％となるように設定して、データベース中のリトリーブおよびランキングを著しく改善するようにすることが好ましい。整数値ｋが小さすぎると検索精度が低下しがちとなり、整数値ｋが大きすぎると、本発明の効果が充分に得られなくなる。
【００６２】
５．ドキュメント・マトリックスの次元低下
ドキュメント・マトリックスの次元低下を図８に示す。ドキュメント・マトリックスＤの次元を低減させたマトリックスｈａｔＤは、ドキュメント・マトリックスＤと、マトリックスＶｋの転置マトリックスとを、図８（ａ）に示すように単に乗算するだけで得られる。また、図８（ｂ）に示すように、次元低下を行ったマトリックスｈａｔＤに対して、ｋ×ｋ要素の重み付けマトリックスを用いて、ある種の重み付けを行うことも可能である。このようにして算出されたマトリックスｈａｔＤは、図８（ｂ）に示すようにｋ×ｋの要素を含み、キーワードに対して比較的特有の特徴を含んでいる。このため、データベースにおけるドキュメントのリトリーブおよびランク付けは、検索エンジンのユーザにより入力されるクエリーに対して著しく向上することになる。したがって、データベース中のドキュメントのリトリーブおよびランキングは、検索エンジンのユーザによる入力クエリーに関して著しく改善されることになる。
【００６３】
６．コンピュータ・システム
図９を参照すると、本発明のコンピュータ・システムの代表的な態様が示されている。本発明のコンピュータ・システムは、スタンド・アローンのコンピュータ・システム、いかなる従来のプロトコルを用いてＬＡＮ／ＷＡＮを介して通信を行うクライアント・サーバ・システム、またはインターネット・インフラベースを通して通信を行うコンピュータ・システムとすることができる。図９においては、本発明に有効な代表的なコンピュータ・システムを、クライアント・サーバ・システムを用いて示している。
【００６４】
図９に示したコンピュータ・システムは、少なくとも１台のホスト・コンピュータと、サーバ・コンピュータとを含んでいる。クライアント・コンピュータと、サーバ・ホスト・コンピュータとは、通信プロトコルＴＣＰ／ＩＰを介して通信されている。しかしながら、本発明においては別のいかなる通信プロトコルであっても用いることができる。図９において説明するように、クライアント・コンピュータは、サーバ・ホスト・コンピュータへとリクエストを送信し、サーバ・ホスト・コンピュータにおいてサーバ・ホスト・コンピュータの記憶手段内に記録されているドキュメントのリトリーブおよび／またはランク付けを行なう。
【００６５】
このサーバ・ホスト・コンピュータは、クライアント・コンピュータからのリクエストに応じてデータベース内のリトリーブおよび／またはランク付けを行なう。リトリーブおよび／またはランク付けの結果は、その後クライアント・コンピュータにより、サーバ・スタッブを介してサーバ・ホスト・コンピュータからダウンロードされて、クライアント・コンピュータのユーザにより用いられることになる。図９においては、サーバ・ホスト・コンピュータは、ウエッブ・サーバとして記載しているが、これに限定されるものではなく、いかなる別のタイプのサーバ・ホストであっても、コンピュータ・システムが上述した機能を提供することができる限り、本発明において用いることができる。
【００６６】
これまで、本発明を特定の態様をもって説明を行ってきた。しかしながら、当業者によれば、本発明の範囲を逸脱することなく、種々の除外、変更、及び他の態様が可能であることは理解できよう。
【００６７】
本発明は、これまでリトリーブおよびランク付けのための方法について詳細に説明してきたが、本発明はまた、本発明で説明した方法を実行するためのシステム、方法自体、本発明の方法を実行するためのプログラムが記録された、例えば光学的、磁気的、電気−磁気的記録媒体といったプログラム製品をも含むものである。
【図面の簡単な説明】
【図１】  マトリックスを対角化させるための従来の方法を示した図。
【図２】  本発明の方法を示したフローチャート。
【図３】  ドキュメント・マトリックスの構成を示した図。
【図４】  ドキュメント・マトリックスの形成及びそのフォーマット化を示した図。
【図５】  共分散マトリックスを算出するためのフローチャート。
【図６】  ドキュメント・マトリックスの転置マトリックスおよび平均ベクトルの構成を示した図。
【図７】  本発明によるニューラル・ネットワークから算出される固有値のセット決定手法を示した概略図。
【図８】  本発明によるニューラル・ネットワークから算出される共分散マトリックスを用いる次元低下手順の詳細を示した図。
【図９】  本発明のコンピュータ・システムを例示した図。
【図１】
0003845553.tif 000025
【図２】
0003845553.tif 000026
【図３】
0003845553.tif 000027
【図４】
0003845553.tif 000028
【図５】
0003845553.tif 000029
【図６】
0003845553.tif 000030
【図７】
0003845553.tif 000031
【図８】
0003845553.tif 000032
【図９】
0003845553.tif 000033