(57)【要約】コンピュータ読取り可能な媒体に、Ｎ個のドキュメントにおける夫々のドキュメント・ペア間の類似度についての情報を提供するデータ構造体が格納されている。前記データ構造体は、複数のドキュメント・ペアの夫々の類似度を表している類似度値を夫々に示している複数のエントリを含んでおり、前記類似度値の各々は、所与の１組のドキュメント・ペアにおける、一方のドキュメントの他方のドキュメントに対する類似度を表している。前記複数のエントリの各々の類似度値は、０より大きな値に設定されているスレショルド類似度値より大きな値である。各ドキュメント・ペアを構成している２つのドキュメントに関して類似度値が非対称性を有する場合には、夫々が類似度値を示している前記複数のエントリの個数が（Ｎ２−Ｎ）個より少なく、各ドキュメント・ペアを構成している２つのドキュメントに関して類似度値が対称性を有する場合には、夫々が類似度値を示している前記複数のエントリの個数が（（Ｎ２−Ｎ）／２）個より少ない。前記データ構造体を生成する方法及び装置について説明している。【選択図】図３
2009519543.tif 000002
【特許請求の範囲】
【請求項１】
ドキュメント集合における夫々のドキュメント・ペア間の類似度についての情報を含むデータ構造体を構築する方法において、
前記ドキュメント集合における夫々のドキュメント・ペアの類似度値を求めるステップと、
前記類似度値の各々について、当該類似度値がスレショルド類似度値以上であるか否かを判定するステップと、
前記スレショルド類似度値より大きな類似度値の各々について、当該類似度値を前記データ構造体に格納するステップと、
を含むことを特徴とする方法。
【請求項２】
夫々のドキュメント・ペアの類似度値を求める前記ステップにおいて、
前記ドキュメント集合についての複数のクェリーを実行し、それら複数のクェリーはその各々が前記ドキュメント集合に含まれているドキュメントのうちの所与の１つのドキュメントに関するものであり、
前記複数のクェリーに応答して、夫々のドキュメントのスコア値算出を行い、このスコア値算出によって、夫々の類似度値が得られるようにする、
ことを特徴とする請求項１記載の方法。
【請求項３】
前記複数のクェリーによって、類似度値に従ってランク付けされた、ドキュメントのランク付けリストが生成されるようにし、
夫々のドキュメント・ペアの類似度値を求める前記ステップにおいて、前記ランク付けリストから、その類似度値が前記スレショルド類似度値以上であるドキュメント・ペアの類似度値だけを抽出する、
ことを特徴とする請求項２記載の方法。
【請求項４】
前記スレショルド類似度値を示しているエントリを、前記データ構造体に格納するステップと、
デフォールト類似度値を示しているエントリを、前記データ構造体に格納するステップと、
を更に含むことを特徴とする請求項１記載の方法。
【請求項５】
前記デフォールト類似度値が前記スレショルド類似度値と等しいことを特徴とする請求項４記載の方法。
【請求項６】
前記デフォールト類似度値が前記スレショルド類似度値より小さいことを特徴とする請求項４記載の方法。
【請求項７】
前記データ構造体は、夫々が類似度値を示している複数のエントリを含んでおり、各ドキュメント・ペアを構成している２つのドキュメントに関して類似度値が非対称性を有する場合には、夫々が類似度値を示している前記複数のエントリの個数が（Ｎ２−Ｎ）個より少なく、各ドキュメント・ペアを構成している２つのドキュメントに関して類似度値が対称性を有する場合には、夫々が類似度値を示している前記複数のエントリの個数が（（Ｎ２−Ｎ）／２）個より少ないことを特徴とする請求項１記載の方法。
【請求項８】
請求項１記載の方法を処理装置に実行させるための処理命令が格納されていることを特徴とするコンピュータ読取り可能な媒体。
【請求項９】
ドキュメント集合に対応したデータ構造体から類似度値を取出す方法において、
前記データ構造体にアクセスして、所与のドキュメント・ペアの類似度値を明示しているエントリが前記データ構造体に含まれているか否かを判定するステップと、
前記所与のドキュメント・ペアの類似度値を明示しているエントリが前記データ構造体に含まれていたならば、当該類似度値を取出すステップと、
前記所与のドキュメント・ペアの類似度値を明示しているエントリが前記データ構造体に含まれていなかったならば、前記データ構造体またはその他の記憶位置からデフォールト類似度値を取出すステップと、
を含むことを特徴とする方法。
【請求項１０】
前記デフォールト類似度値が前記スレショルド類似度値と等しいことを特徴とする請求項９記載の方法。
【請求項１１】
前記デフォールト類似度値が前記スレショルド類似度値より小さいことを特徴とする請求項９記載の方法。
【請求項１２】
前記データ構造体は、夫々が類似度値を示している複数のエントリを含んでおり、各ドキュメント・ペアを構成している２つのドキュメントに関して類似度値が非対称性を有する場合には、夫々が類似度値を示している前記複数のエントリの個数が（Ｎ２−Ｎ）個より少なく、各ドキュメント・ペアを構成している２つのドキュメントに関して類似度値が対称性を有する場合には、夫々が類似度値を示している前記複数のエントリの個数が（（Ｎ２−Ｎ）／２）個より少ないことを特徴とする請求項９記載の方法。
【請求項１３】
請求項９記載の方法を処理装置に実行させるための処理命令が格納されていることを特徴とするコンピュータ読取り可能な媒体。
【請求項１４】
ドキュメント集合における夫々のドキュメント・ペア間の類似度についての情報を含むデータ構造体を構築する装置において、
メモリと、
前記メモリに接続された処理装置とを備え、
前記処理装置は、
前記ドキュメント集合における夫々のドキュメント・ペアの類似度値を求めるステップと、
前記類似度値の各々について、当該類似度値がスレショルド類似度値以上であるか否かを判定するステップと、
前記スレショルド類似度値より大きな類似度値の各々について、当該類似度値を前記データ構造体に格納するステップと、
を実行するように構成されている、
ことを特徴とする装置。
【請求項１５】
前記処理装置は、夫々のドキュメント・ペアの類似度値を求める際に、
前記ドキュメント集合についての複数のクェリーを実行し、それら複数のクェリーはその各々が前記ドキュメント集合に含まれているドキュメントのうちの所与の１つのドキュメントに関するものであり、
前記複数のクェリーに応答して、夫々のドキュメントのスコア値算出を行い、このスコア値算出によって、夫々の類似度値が得られるようにする、
ように構成されていることを特徴とする請求項１４記載の装置。
【請求項１６】
前記複数のクェリーによって、類似度値に従ってランク付けされた、ドキュメントのランク付けリストが生成されるようにしてあり、
前記処理装置は、夫々のドキュメント・ペアの類似度値を求める際に、前記ランク付けリストから、その類似度値が前記スレショルド類似度値以上であるドキュメント・ペアの類似度値だけを抽出するように構成されている、
ことを特徴とする請求項１５記載の装置。
【請求項１７】
前記データ構造体は、夫々が類似度値を示している複数のエントリを含んでおり、各ドキュメント・ペアを構成している２つのドキュメントに関して類似度値が非対称性を有する場合には、夫々が類似度値を示している前記複数のエントリの個数が（Ｎ２−Ｎ）個より少なく、各ドキュメント・ペアを構成している２つのドキュメントに関して類似度値が対称性を有する場合には、夫々が類似度値を示している前記複数のエントリの個数が（（Ｎ２−Ｎ）／２）個より少ないことを特徴とする請求項１４記載の装置。
【請求項１８】
ドキュメント集合に対応したデータ構造体から類似度値を取出す装置において、
メモリと、
前記メモリに接続された処理装置とを備え、
前記処理装置は、
前記データ構造体にアクセスして、所与のドキュメント・ペアの類似度値を明示しているエントリが前記データ構造体に含まれているか否かを判定するステップと、
前記所与のドキュメント・ペアの類似度値を明示しているエントリが前記データ構造体に含まれていたならば、当該類似度値を取出すステップと、
前記所与のドキュメント・ペアの類似度値を明示しているエントリが前記データ構造体に含まれていなかったならば、前記データ構造体またはその他の記憶位置からデフォールト類似度値を取出すステップと、
を実行するように構成されている、
ことを特徴とする装置。
【請求項１９】
前記データ構造体は、夫々が類似度値を示している複数のエントリを含んでおり、各ドキュメント・ペアを構成している２つのドキュメントに関して類似度値が非対称性を有する場合には、夫々が類似度値を示している前記複数のエントリの個数が（Ｎ２−Ｎ）個より少なく、各ドキュメント・ペアを構成している２つのドキュメントに関して類似度値が対称性を有する場合には、夫々が類似度値を示している前記複数のエントリの個数が（（Ｎ２−Ｎ）／２）個より少ないことを特徴とする請求項１８記載の装置。
【請求項２０】
Ｎ個のドキュメントを含んでいるドキュメント集合における夫々のドキュメント・ペア間の類似度についての情報を提供するデータ構造体が格納されているコンピュータ読取り可能な媒体において、
前記データ構造体は、複数のドキュメント・ペアの夫々の類似度を表している類似度値を夫々に示している複数のエントリを含んでおり、前記類似度値の各々は、所与の１組のドキュメント・ペアにおける、一方のドキュメントの他方のドキュメントに対する類似度を表しており、
前記複数のエントリの各々の類似度値は、０より大きな値に設定されているスレショルド類似度値より大きな値であり、
各ドキュメント・ペアを構成している２つのドキュメントに関して類似度値が非対称性を有する場合には、夫々が類似度値を示している前記複数のエントリの個数が（Ｎ２−Ｎ）個より少なく、各ドキュメント・ペアを構成している２つのドキュメントに関して類似度値が対称性を有する場合には、夫々が類似度値を示している前記複数のエントリの個数が（（Ｎ２−Ｎ）／２）個より少ない、
ことを特徴とするコンピュータ読取り可能な媒体。
【請求項２１】
前記スレショルド類似度値を含むエントリと、
デフォールト類似度値を含むエントリと、
を含んでいることを特徴とする請求項２０記載のコンピュータ読取り可能な媒体。
【請求項２２】
前記デフォールト類似度値が前記スレショルド類似度値と等しいことを特徴とする請求項２０記載のコンピュータ読取り可能な媒体。
【請求項２３】
前記デフォールト類似度値が前記スレショルド類似度値より小さいことを特徴とする請求項２０記載のコンピュータ読取り可能な媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、コンピュータを用いたドキュメントの解析に関し、より詳しくは、ドキュメント集合に含まれるドキュメントどうしの類似度を表す効率的でコンパクトなデータ構造体即ち表示構造体に関するものである。本開示は更に、このコンパクトな類似性表示体をドキュメントの関連性の解析のためのモデルにトレーニングを施すために使用する方法に関するものである。
【背景技術】
【０００２】
ドキュメントは、フリーテキスト形式の情報オブジェクトである。フリーテキスト形式の情報オブジェクトの解析や操作などに関与する最近のアプリケーションの多くは、情報オブジェクトのコンテンツのアブストラクションを生成して利用するようにしている。例えば、ドキュメントの分類やフィルタリングを行うアプリケーションは、クラスやトピックを表示しているデータ構造体である表示構造体を利用するようにしており、この表示構造体は、ドキュメント集合から抽出した、クラスやトピックを典型的に表すタームの集合（即ちベクトル）に基づいたデータ構造体である。また、クラスやトピックを典型的に表す事例の集合（しばしば「トレーニング集合」と呼ばれている）の特徴的なフィーチャを学習するという課題に対してマシン学習法及び統計法を適用することの利点を利用するようにした多くの方法が存在しており、そのような方法は、部分的に、当業界において「類似性行列」または「カーネル行列」と呼ばれているデータ構造体を構築することによって行われている。類似性行列は、トレーニング集合における全てのドキュメントに対するドキュメント・ペア間の類似性レベルを反映した値のテーブルである。
【０００３】
クラシファイヤやフィルタを生成するための最新の方法のうちには、トピックの正事例と負事例との両方をモデル化するようにしたものがり、そのような方法においては、「真ドキュメント」（オン・トピック・ドキュメント）及び「偽ドキュメント」（ノット・オン・トピック・ドキュメント）のサンプルを使用してトレーニング集合を生成している。この種の方法の１つである「サポートベクトルマシン」（ＳＶＭ）法では、トレーニング集合における正事例と負事例との分離度のマージンを、各ドキュメントのターム・ベクトルのコンビネーションの関数としてモデル化し、特徴抽出をするようにしている。また、最適マージンを、個々のＳＶＭアルゴリズムに固有の一連のステップによって求めるようにしている。更に、マージンの算出を容易にするために、トレーニング集合に含まれる全てのドキュメントについての類似性行列（カーネル行列）を生成して、その生成した類似性行列を反復して使用するようにしている。
【０００４】
従来、類似性行列を生成するには、所与のトレーニング・アルゴリズムが使用するトレーニング集合に含まれる全ての事例ドキュメントについての全てのドキュメント・ペア間の類似度値を算出するようにしていた。こうして類似性行列を構築したならば、その類似性行列のエントリを使用できるように、何らかの方法で格納しておく必要がある（この格納は、ディスクまたはメモリに行い、また特に、学習に使用する上で高速アクセスが必要とされる場合などにはメモリに格納するようにしている）。トレーニング集合に含まれる事例の個数が大量である場合には、ストレージ（例えば、類似性行列を保持するために必要なランダム・アクセス・メモリ）のためにも、また、計算プロセス（例えばＣＰＵサイクル）のためにも、莫大なリソースが必要とされることになる。必要とされるリソースを低減することは、重要な課題であり、しかも解決が容易でない課題であった。
【発明の開示】
【発明が解決しようとする課題】
【０００５】
本発明の目的は、トレーニング集合における夫々のドキュメント・ペア間の類似度を表している情報を格納するために必要とされるストレージ容量を、従来の類似性行列を格納するために必要とされるストレージ容量と比べて、より小さなものとすることにある。
【０００６】
本発明の更なる目的は、コンピュータのランダム・アクセス・メモリの容量には限りがあることを考慮して、トレーニング集合におけるドキュメント・ペア間の類似度に関する情報にアクセスすることを必要としているプロセスに用い得るトレーニング事例の個数を可及的に増大し、それによって、当該トレーニング集合を使用して学習させたモデルの精度が、より高くなるようにすることにある。
【０００７】
本発明の更なる目的は、トレーニング集合における夫々のドキュメント・ペア間の類似度を表す情報を含んでいるデータ構造体を算出するために必要とされる計算時間を（その算出に必要とされるＣＰＵサイクルの回数を低減することにより）短縮することにある。
【課題を解決するための手段】
【０００８】
具体的な１つの実施の形態によれば、ここに説明する方法は、ドキュメント集合における夫々のドキュメント・ペア間の類似度についての情報を含むデータ構造体を構築する方法である。この方法においては、前記ドキュメント集合における夫々のドキュメント・ペアの類似度値を求め、前記類似度値の各々について、当該類似度値がスレショルド類似度値以上であるか否かを判定する。そして、前記スレショルド類似度値より大きな類似度値の各々について、当該類似度値を前記データ構造体に格納する。
【０００９】
また別の具体的な１つの実施の形態によれば、ここに説明する方法は、ドキュメント集合に対応したデータ構造体から類似度値を取出す方法である。この方法においては、前記データ構造体にアクセスして、所与のドキュメント・ペアの類似度値を明示しているエントリが前記データ構造体に含まれているか否かを判定し、前記所与のドキュメント・ペアの類似度値を明示しているエントリが前記データ構造体に含まれていたならば、当該類似度値を取出す。一方、前記所与のドキュメント・ペアの類似度値を明示しているエントリが前記データ構造体に含まれていなかったならば、前記データ構造体またはその他の記憶位置からデフォールト類似度値を取出す。
【００１０】
更に別の局面によれば、本発明に係る装置は、メモリと、このメモリに接続された処理装置とを備えたものである。前記処理装置は、上述した方法を実行するように構成されている。更に別の局面によれば、コンピュータ読取り可能な媒体は、上述した方法のステップを処理装置に実行させるための処理命令が格納されている。
【００１１】
更に別の局面によれば、本発明に係るコンピュータ読取り可能な媒体には、Ｎ個のドキュメントを含んでいるドキュメント集合における夫々のドキュメント・ペア間の類似度についての情報を提供するデータ構造体が格納されている。前記データ構造体は、複数のドキュメント・ペアの夫々の類似度を表している類似度値を夫々に示している複数のエントリを含んでおり、前記類似度値の各々は、所与の１組のドキュメント・ペアにおける、一方のドキュメントの他方のドキュメントに対する類似度を表している。前記複数のエントリの各々の類似度値は、０より大きな値に設定されているスレショルド類似度値より大きな値である。各ドキュメント・ペアを構成している２つのドキュメントに関して類似度値が非対称性を有する場合には、夫々が類似度値を示している前記複数のエントリの個数が（Ｎ２−Ｎ）個より少なく、各ドキュメント・ペアを構成している２つのドキュメントに関して類似度値が対称性を有する場合には、夫々が類似度値を示している前記複数のエントリの個数が（（Ｎ２−Ｎ）／２）個より少ない。
【発明を実施するための最良の形態】
【００１２】
以下の説明では、ドキュメントについて論じると共に、ドキュメントが関与する操作についても論じる。本開示においてドキュメントと称するものは、文字などの明確に識別し得るフィーチャのストリングを１つまたは複数含んでいるテキストなどであって、オブジェクトとしての形態を有するものをいい、その具体例としては、イメージ、グラフィックス、ハイパーリンク、テーブル、チャート、スプレッドシートなどがあり、また更に、その他の種類の、視覚情報、数値情報、またはテキスト情報の情報オブジェクトが含まれ、しかも、これらのみに限定されない。例えば、文字のストリングとしては、ワード、フレーズ、センテンス、それにパラグラフなどの形態のストリングが存在する。また、ドキュメントに含まれる構成体は、特定の言語に対応した構成体即ちフォームに限定されない。また、フィーチャの具体例を挙げるならば、先ず、その種類として、構造的フィーチャ、物理的フィーチャ、注釈的フィーチャ、それに派生的フィーチャなどがある。構造的フィーチャには、例えば、そのドキュメントに含まれているフィールドの個数や、セクションの個数や、パラグラフの個数や、テーブルの個数などがある。物理フィーチャには、例えば、そのドキュメントのイメージに含まれている「黒」領域に対する「白」領域の領域比や、カラー・パターンなどがある。注釈的フィーチャには、例えば、そのドキュメントの特定のフィールドに記録される注釈値の有無や、手作業による処理または機械処理の結果としての注釈値の有無などがある。派生的フィーチャには、例えば、潜在意味解析などの変換機能によって発生したものなどがある。また、以上の様々な種類のフィーチャを組合せたフィーチャがあり、更には、当業者には容易に想到し得るその他の多くの種類のフィーチャがある。
【００１３】
更に、ドキュメントを処理対象として見るとき、ドキュメントの種類を、以下の（イ）〜（ホ）のように定義することができる。（イ）リテラル・ドキュメント、（ロ）サブドキュメント、（ハ）サブドキュメント集合体、（ニ）ドキュメント集合体即ちドキュメント群、及び、（ホ）上記（イ）〜（ニ）の組合せ。これらのうち、（イ）のリテラル・ドキュメントは、例えばフル・ドキュメントであり、システムがソース・ドキュメントとして入手可能なドキュメントである。（ロ）のサブドキュメントは、任意の大きさのものとすることができる。（ハ）のサブドキュメント集合体には、単一のソース・ドキュメントから得られた複数のサブドキュメントから成るものと、多数のソース・ドキュメントから得られた複数のサブドキュメントから成るものとがあるが、いずれにせよ、そのサブドキュメント集合体を構成している複数のサブドキュメントが、単一のエンティティ（ドキュメント）として処理されるものである。（ニ）のドキュメント集合体即ちドキュメント群は、ドキュメントの他にサブドキュメントが混合されていることもあるが、その集合体即ち群を構成している複数のドキュメントないしサブドキュメントが、単一のエンティティ（ドキュメント）として処理されるものである。また、サブドキュメントとは、フル・ドキュメントの適宜の一部分であって、例えば、個々のパラグラフや、テキストのうちの所定行数の複数行などである。サブドキュメントに関する詳細な説明は、例えば、米国特許第5,907,840号公報、米国特許第5,999,925号公報などに記載されており、これら米国特許第の開示内容はこの言及をもって本願開示に組込まれたものとする。
【００１４】
本発明の１つの局面によれば、コンピュータ読取り可能な媒体に格納されるデータ構造体は、ドキュメント集合（例えばトレーニング集合などのドキュメント集合など）における夫々のドキュメント・ペア間の類似度についての情報を提供するものである。このデータ構造体（以下の説明では、このデータ構造体を「コンパクト類似性構造体」または単に「類似性構造体」と呼ぶことがある）は、ドキュメント集合における夫々のドキュメント・ペア間の類似度を示している複数のエントリを含んでいるが、ただし、ドキュメント集合における全てのドキュメント・ペアについて、それらドキュメント・ペアの類似度を示しているエントリを個別に含むものではない。これと対照的に、従来の類似性行列（即ちカーネル行列）は、トレーニング集合における全てのドキュメント・ペアについて、それらドキュメント・ペアの類似度を示しているエントリを個別に含んでいる。そのため従来の類似性行列では、対応するトレーニング集合の大きさによっては、その類似性行列を格納しておくために必要とされるストレージ容量が過度に大きなものとなることがあった。これに対して、ここに開示する類似性構造体は、「コンパクトな」データ構造体であり、即ち、ドキュメント集合に含まれているドキュメントの個数が同じであるならば、従来の類似性行列と比べて、この類似性構造体を格納しておくために必要とされるストレージ容量は、格段に小さなもので済むのである。
【００１５】
このデータ構造体は、複数のドキュメント・ペアの夫々の類似度を表している数値である類似度値を夫々に示している複数のエントリを含んでいる。各々の類似度値は、所与の１組のドキュメント・ペアにおける、一方のドキュメントの他方のドキュメントに対する類似度を表している。このような類似度値（これは、例えば類似性スコア値などである）を求める方法としては、様々な適当な方法が存在しており、それらのうちの任意の方法を用いればよい。本明細書においても、類似度値を求める方法の具体例を開示するが、ただし、本明細書に開示する方法だけに限定されるものではない。複数のエントリの各々の類似度値は、０より大きな値に設定されているスレショルド類似度値より大きな値である。ここで、ドキュメント集合に含まれているドキュメントの個数をＮ個とするならば、各ドキュメント・ペアを構成している２つのドキュメントに関して類似度値が非対称性を有する場合（即ち、「第ｉ番ドキュメント」に対する「第ｊ番ドキュメント」の類似度値と、「第ｊ番ドキュメント」に対する「第ｉ番ドキュメント」の類似度値とが必ずしも同一ではない場合）には、夫々が類似度値を示している複数のエントリの個数が（Ｎ２−Ｎ）個より少なく、一方、各ドキュメント・ペアを構成している２つのドキュメントに関して類似度値が対称性を有する場合（即ち、「第ｉ番ドキュメント」に対する「第ｊ番ドキュメント」の類似度値と、「第ｊ番ドキュメント」に対する「第ｉ番ドキュメント」の類似度値とが常に同一である場合）には、夫々が類似度値を示している複数のエントリの個数が（（Ｎ２−Ｎ）／２）個より少ない。これに対して、従来の類似性行列では、それが非対称性を有するものである場合には、対角エントリを除いて（Ｎ２−Ｎ）個のエントリを格納する必要があり、また、それが対称性を有するものである場合には、対角エントリを除いて（（Ｎ２−Ｎ）／２）個のエントリを格納する必要がある。
【００１６】
本発明に係るコンパクト類似性構造体は、様々な適当な形態に構成することができる。本発明に係るコンパクト類似性構造体の１つの具体例を図１に示した。図１に示したのはＮ個のドキュメントを含んでいる仮想的なドキュメント集合（例えばＮ個のドキュメントを含んでいるトレーニング集合など）における夫々のドキュメント・ペアの仮想的な類似性スコア値のテーブル１００である。ドキュメント解析モデルのトレーニングのためのドキュメント集合の使用の仕方及びアセンブルの仕方については本明細書において後に詳述する。いずれにせよ、トレーニング集合として用いられるドキュメント集合の典型的なサイズは例えば、１万個のドキュメントを含むものである。この大きさのドキュメント集合ではＮ２が１０８となるため、この大きさのドキュメント集合に対応した従来の類似性行列のサイズは甚だしく大きなものとならざるを得ない。図１の具体例では、ドキュメント・ペアは、第１欄において、ドキュメント・ペア番号に従って検索され、ドキュメント・ペア番号は図示例では（１，２）、（１，３）、（１，２２）、等々である。第２欄に記入されているのは、所与のドキュメント・ペアに付随する類似度値（例えば類似性スコア値）であり、ここで、ドキュメント・ペア（ｘ，ｙ）の類似度値とは、ドキュメントｘに対するドキュメントｙの類似度値を意味している。図１の具体例では、エントリの類似度値はいずれも、スレショルド類似度値である０．４００より大きな値となっている。
【００１７】
類似性構造体が更に、スレショルド類似度値を示しているエントリと、デフォールト類似度値を示しているエントリとを含んでいるようにしてもよい。図１の具体例では、類似性構造体に、「０．４００」というスレショルド類似度値と、「０．２５０」というデフォールト類似度値とが格納されている。デフォールト類似度値とは、その類似度値を明示しているエントリがテーブル１００の中に個別のエントリとして含まれていない場合に、そのドキュメント・ペアの類似度値として使用するための値である。図１の具体例では、テーブルに含まれているエントリのうちの一部だけが示されており、図中の点線は、このテーブルに、その他のエントリも含まれていることを表している。一般的には、デフォールト類似度値は、スレショルド類似度値と等しい値に定めることもあり、また、スレショルド類似度値に対して所定割合をなす値に定めることもある（例えば、デフォールト類似度値を、スレショルド類似度値の５０％、８０％、９０％、１００％、または１１０％の値に定めることがある）。スレショルド類似度値を、そのままデフォールト類似度値として使用すると好都合である。
【００１８】
先に言及したように、本発明に係る類似性構造体は、ドキュメント集合における全てのドキュメント・ペアについて、それらドキュメント・ペアの夫々の類似度を示しているエントリを個別に含むものではなく、即ち、ドキュメント・ペアのうちには、対応する個別のエントリが類似性構造体に含まれていないものがある。これについて更に詳しく説明すると、その類似度値がスレショルド・スコア値（即ち、スレショルド類似度値）より小さいドキュメント・ペアについては、そのドキュメント・ペアの類似度値を示す個別のエントリを類似性構造体に含めないようにしている。例えば、図１の具体例のテーブル１００には、ドキュメント・ペア（１，４）、（１，５）、（１，６）、…、（１，２１）の夫々に対応したエントリは含まれておらず、それらエントリが含まれていないのは、この具体例では、それらドキュメント・ペアの夫々の類似度値が、スレショルド類似度値の「０．４００」より小さいからである。これと同じ理由によって、このテーブルには、ドキュメント・ペア（２，４）、（２，５）、（２，６）、…、（２，４４）の夫々に対応したエントリも含まれておらず、ドキュメント・ペア（３，２）に対応したエントリも含まれておらず、また、ドキュメント・ペア（３，５）、（３，６）、（３，７）、…、（３，５１）の夫々に対応したエントリも含まれていない。更には、ドキュメント・ペア（１，１）、（２，２）、（３，３）、などの夫々に対応したエントリも含まれていないが、ただし、それらが含まれていないのは、みずからに対する類似度を表したスコア値を示しているエントリは、提供する必要がないからである。
【００１９】
図１に示した具体例では、ドキュメント１に対するドキュメント２の類似度値（即ち、ドキュメント・ペア（１，２）の類似度値）が、ドキュメント２に対するドキュメント１の類似度値（即ち、ドキュメント・ペア（２，１）の類似度値）とは異なっていることが見て取れる。それらが異なっているのは、この具体例が、本発明に係る類似性構造体は、非対称性を有するデータ構造体とすることも可能であることを例示した具体例だからである。非対称性を有する類似性構造体は、所与のドキュメントのターム及び／またはフィーチャの部分集合を、その所与のドキュメントに対する別のドキュメントの類似性スコア値を算出するためのベースとして用いる場合に、生成されることがある。無論、本発明に係る類似性構造体は、非対称性を有するデータ構造体ではなく、対称性を有するデータ構造体とすることもできる（例えば、ドキュメント・ペア（１，２）の類似性スコア値が、ドキュメント・ペア（２，１）の類似性スコア値と同一であるようにすることもでき、それら２つの類似性スコア値の算出の仕方に応じて、両者は異なったものとなることもあれば、同一となることもある）。
【００２０】
図２に示したのは、本発明に係るコンパクト類似性構造体の別の具体例である。図２に示した具体例のデータ構造体２００の基礎となっているデータは、図１に示した具体例のデータ構造体の基礎となっているデータと同一のものである。図２の具体例において、データ構造体２００は、トレーニング集合に含まれているＮ個のドキュメントの夫々に対応したＮ個のレコードを含んでいる。更にこのデータ構造体２００は、オプションとして、スレショルド類似度値（例えば「０．４００」）を記入したフィールドと、デフォールト類似性スコア値（例えば「０．２５０」）を記入したフィールドとを有するレコードを含んでいる。Ｎ個のドキュメントの夫々に対応したＮ個のレコードは、その各々が、複数のフィールドを有している。第１番フィールドには、インデクスとしてのドキュメント番号が記入されている。第２番フィールドには、インデクスで表されたドキュメントに対する類似度値がスレショルド類似度値より大きなドキュメントのドキュメント番号が記入されており、第３番フィールドには、インデクスで表されたドキュメントに対するそのドキュメントの類似度値が記入されている。第４番フィールドには、インデクスで表されたドキュメントに対する類似度値がスレショルド類似度値より大きなまた別のドキュメントのドキュメント番号が記入されており、第５番フィールドには、インデクスで表されたドキュメントに対するそのドキュメントの類似度値が記入されており、以下同様とされている。１つのレコードにおける複数のフィールドは、図２に示した具体例では、それらフィールドに記入されたドキュメント番号が、左側から右側へ昇順で並ぶようにしてあるが、ただし、このように並べることは必須の要件ではない。
【００２１】
後に更に詳細に説明するように、本発明に係る類似性構造体を使用する際には、参照動作を実行して、その類似性構造体に、特定のドキュメント・ペアに対応したエントリが含まれているか否かを調べるようにする。そして、その特定のドキュメント・ペアに対応したエントリが類似性構造体に含まれていたならば、そのドキュメント・ペアの類似度値を類似性構造体から取出す。一方、その特定のドキュメント・ペアに対応したエントリが類似性構造体に含まれていなかったならば、類似性構造体またはその他の記憶位置からデフォールト類似度値を取出して、そのデフォールト類似度値をもってそのドキュメント・ペアの類似度値とする。例えば、図１に示した具体例のテーブル１００に関しては、ドキュメント・ペア（３，５２）の類似度値が必要なときには、このテーブル１００に対する参照動作を実行すれば、ドキュメント・ペア（３，５２）に対応したエントリが発見されるため、「０．６６０」という類似度値が取出されることになる。一方、ドキュメント・ペア（３，１８）の類似度値が必要なときには、参照動作を実行しても、ドキュメント・ペア（３，１８）に対応したエントリが発見されないため、「０．２５０」というデフォールト類似度値が取出されることになる。同様に、図２の具体例に関しても、ドキュメント・ペア（３，５２）の類似度値が必要なときには、このドキュメント・ペアの第１ドキュメント（即ち、ドキュメント３）に対応した、「００００３」というインデクス番号が付されたレコードが特定される。そして、このレコードの、該当するフィールド（例えば、この具体例では奇数番フィールド）が調べられて、ドキュメント５２に対応したエントリ（即ち「０００５２」）が存在するか否かが判定される。これによって「０００５２」のエントリが発見されるため、そのフィールドのすぐ右側のフィールドに記入されている類似度値（即ち「０．６６０」）が取出されることになる。一方、ドキュメント・ペア（３，１８）に対応した類似度値が必要なときには、「００００３」のレコードの奇数番フィールドが調べられるが、第１８番ドキュメントに対応したエントリ（即ち「０００１８」）が発見されないため、「０．２５０」というデフォールト類似度値が取出されることになる。
【００２２】
図３に、本発明に係るコンパクト類似性構造体を構築する方法の１つの具体例３００を示した。この具体例の方法３００も、また本明細書において説明するその他の具体例の方法も、処理装置（例えば複数のプロセッサから成る処理装置など）とメモリとを備えた任意の適当なコンピュータ・システムを用いて実施することができ、そのようなコンピュータ・システムについては、後に図６を参照して詳述する。ステップ３０２では、ドキュメント・ペア（ｉ，ｊ）の類似度値を求める。ドキュメント・ペアの類似度値を求める方法は、反復処理方式としてもよく、１個または複数個のプロセッサが複数のステップないしスレッドを実行することによる並行処理方式としてもよい。また、ドキュメント・ペアの類似度値（この類似度値は、例えば類似性スコア値などである）を求める方法には、既に算出されている類似度値のリストから取出すという方法と、任意の適当な算出方式によって類似度値を計算によって求めるという方法とがある。
【００２３】
更に別の具体例として、この類似度値を求めるステップにおいて、ドキュメント集合についての複数のクェリーを実行し、それら複数のクェリーはその各々がドキュメント集合に含まれているドキュメントのうちの所与の１つのドキュメントに関するものであり、そして、それら複数のクェリーに応答して、夫々のドキュメントのスコア値算出を行い、このスコア値算出によって、夫々の類似度値が得られるようにすることも可能である。この場合、クェリーそれ自体が、スコア値算出を行うようなものとしてもよい。また、１つの具体例として、複数のクェリーによって、類似度値に従ってランク付けされた、ドキュメントのランク付けリストが生成されるようにし、そして、上述した夫々のドキュメント・ペアの類似度値を求めるステップにおいて、そのランク付けリストから、その類似度値がスレショルド類似度値より大きいかまたはスレショルド類似度値と等しいドキュメント・ペアの類似度値だけを抽出するようにしてもよい。この方式は、類似性構造体にエントリを効率的に移植することのできる方式である。更に、類似度値を正規化することが望ましい場合には、その正規化を行うようにしてもよく、その場合に、例えば、類似度値の最大値を基準とした正規化を行うようにしてもよく、或いは、当業者には周知のその他の適当な方法で正規化するようにしてもよい。
【００２４】
類似性スコア値の算出方法は、当業者の周知事項に属するものである。例えば、２つのベクトルの間の類似性を評価するための方法として、様々な方法が当業者に周知となっており、そのような方法を用いて、例えば、プローブとドキュメントとの間の類似性を評価するようにしてもよく、ここでいうプローブとは、ドキュメントに含まれている様々なターム及び／またはフィーチャの部分集合である。そのような方法の１つの具体例として、米国特許出願公開第2004/0158569号公報に記載されている、ベクトル空間型のスコア値算出方法などを使用することができる。ベクトル空間型のスコア値算出方法は、全てのタームの直交空間に亘って、プロファイルＱとドキュメントＤとの間の類似性を比較し、それらの共通ターム及び非共通タームを評価することにより行われる。尚、ここでいうプロファイルとは、上述したプローブと同等である。この方法によれば、例えば、類似性スコア値を下式に従って算出することができる（ただし、当業界において周知のその他多くの類似性関数を使用することも可能である）。
【００２５】
【数１】
2009519543.tif 000003
【００２６】
上式において、Ｑｉはプロファイルに含まれているタームであり、Ｄｊはドキュメントに含まれているタームである。上式（または当業界において周知の同様の式）の値を求めることによって、類似性を表す数値である類似度値が得られる（その数値は、例えば小数の形の数値などである）。無論、類似性スコア値を求める方法は、以上に例示したものに限られず、その他の適当な方法を用いるようにしてもよい。
【００２７】
ステップ３０４では、こうして得られた類似度値（即ち、類似性スコア値など）が、スレショルド類似度値以上であるか否かを判定する。得られた類似度値がスレショルド値以上であったドキュメント・ペアについては、そのドキュメント・ペアの類似度値を類似性構造体に格納する（ステップ３０６）。一方、得られた類似度値がスレショルド値未満であったならば、その類似度値は類似性構造体に格納しない。
【００２８】
スレショルド類似度値を適切に定める方法は、当業者の周知事項に属する。適当な値を任意に選択するというのも１つの方法であり、スレショルド類似度値として適切な値には例えば「０．３」、「０．４」、「０．５」、「０．６」、「０．７」、「０．８」、それに「０．９」などの値がある。スレショルド類似度値を適切に定めるためのその他の方法については、ドキュメント分類モデルのトレーニング及び構築について説明した後に、図５を参照して説明する。
【００２９】
ステップ３０８では、ステップ３０４において類似度値のテストがされていないドキュメント・ペアがまだ他に存在しているか否かを判定する。そのようなドキュメント・ペアが存在していたならば、処理の流れはステップ３０２へ戻り、当該ドキュメント・ペアの類似度値を求め、そして、以上の処理を反復する。一方、類似度値のテストがされていないドキュメント・ペアが他にはもう存在していなかったならば、以上の処理を終了する。このステップ３０８は、類似性構造体が、上で述べたように対称性を有するものかそれとも非対称性を有するものかを考慮したステップとするようにしてもよい。即ち、類似性構造体が対称性を有するものである場合には、ドキュメント・ペア（ｊ，ｉ）の類似度値のテストが行われていれば、ドキュメント・ペア（ｉ，ｊ）の類似度値のテストを行う必要はない。
【００３０】
この時点で、以上の方法３００によって生成された類似性構造体は、その類似度値がスレショルド類似度値以上であるドキュメント・ペアの類似度値によって構成されたものとなっている。この類似性構造体には、その類似性構造体がスレショルド類似度値より小さなドキュメント・ペアに対応したエントリは含まれていない。尚、先に述べたように、この類似性構造体に、更に、スレショルド類似度値を示すエントリと、デフォールト類似度値を示すエントリとを含めるようにしてもよい。
【００３１】
別の具体例として、既に生成されている、トレーニング事例のランク付けリスト（このランク付けリストには、オプションとしてスレショルド処理が施されていることもある）を利用して、類似性構造体にエントリを充当するようにすることもでき、この具体例によれば、類似性構造体を構築するために必要とされる計算処理作業を軽減することができる（即ち、計算処理作業を高速化することができる）。この具体例は、ある事実を利用したものであり、その事実とは、類似事例のランク付けリストを生成する際には、その生成作業に先立って、何らかの既にアセンブルが完了したデータを入手できるならば、その生成作業がより効率的に行えるというものであり、ここでいう既にアセンブルが完了したデータとは、例えば、テキスト・ドキュメントを既にアセンブルしてある資料体などであり、このような資料体には、フィーチャ（タームなど）の逆インデクスが存在するため、その逆インデクスによって高い作業効率が得られるのである。このような既にアセンブルが完了したデータがあれば、ランク付けリストの中の所与の１つの事例に対する類似度が、所望のスレショルド類似度値以上であるような、その所与の事例に対する類似度が最大級の複数の事例を、高速で収集することができる。また、この場合、類似性構造体を生成するための計算処理は２つのステップによって行われる。第１のステップでは、ドキュメント集合（例えばトレーニング集合など）に含まれている事例の各々に対応させて、１つずつのスレショルド処理を施したランク付けリストを生成し、従って、夫々の事例に対応した複数のランク付けリストを生成する。そして、第２のステップでは、生成したそれら複数のランク付けリストを利用して、類似性構造体の中にデータを移植する（ある１つの事例に対応したランク付けリストを利用して移植されるデータは、当該事例と、ドキュメント集合に含まれているその他全ての事例の夫々との間の類似度についてのデータである）。
【００３２】
図４は、コンパクト類似性構造体を使用して情報を参照する方法の１つの具体例４００を示した図であり、このような方法も本発明の様々な局面のうちの１つである。ステップ４０２では、所与のドキュメント・ペア（ｉ，ｊ）のＩＤ（識別情報）を取得する。例えば、このＩＤは、その所与のドキュメント・ペア（ｉ，ｊ）の類似度値を必要とした、ドキュメント解析モデルの学習のためのトレーニング・アルゴリズムによって、既に生成されていることがある。続いてステップ４０４では、当該ドキュメント・ペアの類似度値を明確に示しているエントリが類似性構造体に含まれているか否かを判定する。当該ドキュメント・ペアの類似度値を明示しているエントリが類似性構造体に含まれていたならば、続いてステップ４０６において、類似性構造体（データ構造体）からその類似度値を取出す。一方、当該ドキュメント・ペアの類似度値を明示しているエントリが類似性構造体に含まれていなかったならば、この方法における処理の流れはステップ４０４からステップ４０８へ進み、このステップ４０８では、デフォールト類似度値を取出す。類似性構造体にデフォールト類似度値が含まれている場合には、類似性構造体からデフォールト類似度値を取出せばよく、そうでない場合には、その他の記憶位置からデフォールト類似度値を取出せばよい。ステップ４１０では、更に別のドキュメント・ペアの類似度値が必要とされているか否かを判定する。もし必要とされていたならば、この方法の処理の流れはステップ４０２へ戻り、以上の処理を反復する。一方、必要とされていなかったならば、この方法は終了する。
【００３３】
図５は、コンパクト類似性構造体を使用してドキュメント分類モデル（このモデルは、例えば、一度に１つのドキュメントをその関連性に応じてフィルタリングする際の確率を示したものなどである）にトレーニングを施す方法の１つの具体例を示した図であり、このような方法も本発明の様々な局面のうちの１つである。尚、本明細書では、このドキュメント分類モデルを「ドキュメント・クラシファイヤ」と称することがある。ドキュメント分類モデルは、ドキュメント・フィーチャ空間内に生成されるハイパー平面に対応するものであり、所定の条件下においてそのハイパー平面の法線ベクトルに対して類似性を有するドキュメントは「正ドキュメント」即ち「関連ドキュメント」に分類され、所定の条件下においてそのハイパー平面の法線ベクトルに対して類似性を有さないドキュメントは「負ドキュメント」即ち「無関連ドキュメント」に分類される。ただし、ハイパー平面及びその法線ベクトルを生成するには、先ず、事例ドキュメントの集合体であるドキュメント集合をトレーニング集合として使用して、ドキュメント解析モデルにトレーニングを施す必要がある。図５に示したのは、このようなトレーニングを施す方法の１つの具体例であり、この具体例の方法は、反復処理によって所期の結果が得られるようにした反復処理方式によるものである。以下に説明する具体例では、ハイパー平面は下式で表される。
【００３４】
【数２】
2009519543.tif 000004
【００３５】
上式において、ａｉは、ドキュメントｘｉに対応したドキュメント・ベクトルＸｉに適用される重み係数であり、ｚｉは、ドキュメントｘｉが正事例であれば「＋１」、負事例であれば「−１」の値を取る係数である。ドキュメントｘｉに対応したドキュメント・ベクトルＸｉをどのように定めるかということは、当業者の周知事項に属するものである（例えば、ドキュメントのターム及び／またはフィーチャの全体集合または部分集合をもってドキュメント・ベクトルとしてもよく、或いは、ドキュメントに基づいて生成したその他の適当なプローブをもってドキュメント・ベクトルとしてもよい）。また、その他の種類のサポートベクトルマシン（ＳＶＭ）のモデルでは、当業者には周知のごとく、上式と同様にして表されるハイパー平面の数式が、ドキュメント・フィーチャ空間以外のカーネル空間の中に存在している場合もあり、そのようなモデルは、そのカーネル空間内でのトレーニング及びドキュメント分類を実行するために用いられる。従って、上式は１つの具体例を示したものであり、本発明は上式を用いるものに限定されない。
【００３６】
既述のごとく、トレーニング集合として用いられるドキュメント集合に含まれているドキュメントの個数は、典型例としては、例えば約１万個にも及ぶことがある。また、トレーニング集合の典型例では、その集合に含まれているドキュメントのうちの約５％のドキュメントが、あるトピック、イシュー、またはその他のドキュメントに対して関連性を有しており（即ち、「正事例」であり）、９５％のドキュメントが、関連性を有していない（即ち、「負事例」である）ことが知られている。トレーニング集合を生成するために正事例と負事例とをどのようにアセンブルすればよいかは、当業者の周知事項に属するものであり（例えば、大勢の人たちがトレーニング集合の正事例と負事例とを１つ１つ確認しながらアセンブルすることもある）、それゆえこれについては詳述しない。
【００３７】
ステップ５０２では、ハイパー平面Ｗの初期設定を行い、この初期設定は、一連の係数ａ１、ａ２、…、ａＮの値とパラメータｂの値とを初期値に設定した上で、それら初期値に基づいてハイパー平面Ｗを計算することによって行う。パラメータｂの値は、固定値として「０」に設定しても一般性を失うことはないが、ただし、固定値とせずに調節可能なパラメータとしてもよい。一連の係数ａ１、ａ２、…、ａＮの値は、適当な初期推定条件に基づいて設定すればよく、実質的に任意の開始値に設定することが可能である。これら係数の値を「１」に設定することは、開始値として好適な設定である。ステップ５０４では、インデクス値ｊを初期値である「１」に設定し、反復処理を開始する。ステップ５０６では、所与のドキュメント・ベクトルＸｊと、ハイパー平面Ｗに対して垂直な法線ベクトルとの間のマージン「ｍ」（これは、両者の間の差分の大きさを表す値である）を算出し、その算出には、例えば下式などが用いられる。
【００３８】
【数３】
2009519543.tif 000005
【００３９】
上式において、Ｋ（Ｘｊ，Ｘｉ）は、ドキュメントｘｊに対するドキュメントｘｉの類似度値であり、上式は、この類似度値を全てのｉについて合計することを表している。ステップ５０６では、先に説明した類似性構造体にアクセスして、計算に必要とされる所与のドキュメント・ペアの類似度値を示しているエントリが、類似性構造体に含まれているか否かを判定する。そのエントリが類似性構造体に含まれていたならば、先に説明したように、その類似度値を取出す。一方、そのドキュメント・ペアの類似度値を示しているエントリが類似性構造体に含まれていなかったならば、先に説明したように、デフォールト類似度値を取出す。続いて、取出した類似度値に基づいてマージンｍを算出する。
【００４０】
ステップ５０８では、ステップ５０６で算出したマージンｍが所定の限界内に収まっているか否かを判定する。この判定のためのテストは、正トレーニング事例についても実行し、負トレーニング事例についても実行する。例えば、正トレーニング事例ｘｊについては、そのマージンの値ｍが、ｐ≦ｍ≦ｑであるか否かを判定するテストを行う。一方、負トレーニング事例ｘｊについては、そのマージンの値ｍが、−ｑ≦ｍ≦−ｐであるか否かを判定するテストを行う。より詳しく説明すると（ステップ５１０）、正トレーニング事例ｘｊについては、ｐ≦ｍ≦ｑであったならば、係数ａｊの現在値を容認する。一方、ｍがｐよりも小さかったならば、係数ａｊの値を増大させるように調節を加えればよく、その際には例えば、所定のステップ量だけ増大させるようにしてもよく、或いは、マージンの値ｍとｐとの差分に比例した量だけ増大させるようにしてもよい。また、ｍがｑよりも大きかったならば、係数ａｊの値を減少させるように調節を加えればよく、その際には例えば、所定のステップ量だけ減少させるようにしてもよく、或いは、マージンの値ｍとｑとの差分に比例した量だけ減少させるようにしてもよい。１つの具体例として、ｍがｑよりも大きかったならば、係数ａｊの値を「０」に設定するようにすることもできる。同様に、負トレーニング事例ｘｊについては、−ｑ≦ｍ≦−ｐであったならば、係数ａｊの現在値を容認する。一方、ｍが−ｐよりも大きかったならば、係数ａｊの値を増大させるように調節を加えればよく、その際には例えば、所定のステップ量だけ増大させるようにしてもよく、或いは、マージンの値ｍと−ｐとの差分に比例した量だけ増大させるようにしてもよい。また、ｍが−ｑよりも小さかったならば、係数ａｊの値を減少させるように調節を加えればよく、その際には例えば、所定のステップ量だけ減少させるようにしてもよく、或いは、マージンの値ｍと−ｑとの差分に比例した量だけ減少させるようにしてもよい。１つの具体例として、ｍが−ｑよりも小さかったならば、係数ａｊの値を「０」に設定するようにすることもできる。ｑの値は、事実上、マージンｍの絶対値の、目標値としての最小値を表すものであり、ＳＶＭドキュメント分類モデルに関しては、慣行として、このｑの値は「１」に設定されることが多い。また、ｐの値は、事実上、マージンｍの値が、その目標値であるｑの値にどれほどまで近似していれば容認可能であるかを表すものであり、例えば、このｐの値は、「０．９９」、「０．９９５」、「０．９９９」などの値に設定されることが多いが、ただしこれらの値に限定されるものではない。
【００４１】
係数の値に調節を加えて増減させる際の、そのステップ調節量または比例調節量を適切に定める方法は、当業者の周知事項に属するものであり、例えば、アルゴリズムが望ましい速度で収束するようにすることと、アルゴリズムが発散しないようにする必要があることとの、両方を勘案して定めるようにすればよく、このことは、反復処理によって確実に所期の結果が得られるようにする上での周知事項である。同様に、ｐの値及びｑの値を適切に定める方法も、当業者の周知事項に属するものであり、例えば、必要とされるモデルの精度に応じてそれらを定めるようにすればよい。
【００４２】
ステップ５１２では、現在反復過程においてステップ５０８でテストをしなければならないドキュメントｘｊがまだ他に存在しているか否かを判定する。現在反復過程においてそのテストをしなければならないドキュメントｘｊがまだ他に残っていたならば、この方法における処理の流れはステップ５０４へ戻り、そこでインデクス値ｊを更新した上で、以上に説明した一連のステップを反復実行する。一方、現在反復過程においてそのテストをしなければならないドキュメントがもう他には存在していなかったならば、処理の流れはステップ５１４へ進む。
【００４３】
ステップ５１４では、更なる反復過程を実行すべきか否かを判定する。この判定は、例えば、反復過程を実行した回数が目標回数に達したか否かを判定することによって行うようにしてもよい。この場合、反復過程を実行した回数が目標回数に達していなかったならば、反復過程を更に実行するようにする。別法として、この判定を、現在反復過程で得られたハイパー平面が「収束」したか否か、即ち、現在反復過程で得られたハイパー平面と前回の反復過程で得られたハイパー平面との差分が、所定量ないし所定割合より小さくなったか否かを判定することによって行うようにしてもよい。この場合、その差分が所定量ないし所定割合より小さくなっていたならば、更なる反復過程を実行する必要はないものと判定する。更に別の具体例として、この判定を、以上に説明したｐの値及びｑの値に関する正マージン誤差及び負マージン誤差の最大値が、所定の限界内に収まっているか否かを判定することによって行うようにしてもよい。この場合、それらマージン誤差が所定の限界内に収まっていなかったならば、更なる反復過程を実行すべきであると判定する。ステップ５１４においては更に、タイムアウト条件の判定を行うようにしてもよく、即ち、反復過程を実行した回数が所定の最大回数に達したならば、処理を終了するようにしてもよい。いずれの場合も、更なる反復過程を実行すべきであると判定されたならば、この方法における処理の流れはステップ５０４へ戻り、そこでインデクス値ｊを「１」にリセットした上で、以上に説明した処理を反復実行する。一方、ステップ５１４において、更なる反復処理を実行すべきでないと判定されたならば、処理を終了する。
【００４４】
この時点において、以上に説明したトレーニング・アルゴリズムによって適当なハイパー平面が得られていた場合には、そのハイパー平面に基づいて、新たなドキュメント（以前にテストが行われたことのないドキュメント）を、このドキュメント分類モデルにおける当該ハイパー平面に対する「関連ドキュメント（正ドキュメント）」と「無関連ドキュメント（負ドキュメント）」との一方に分類する。このプロセスを実行するには、新たなドキュメントＸの類似度値と、係数ａｉの値が非ゼロであるトレーニング事例の類似度値とを算出し、それら類似度値の合計値を下式に従って合算することで、マージンの値を算出するようにする。
【００４５】
【数４】
2009519543.tif 000006
【００４６】
上式における合算は係数ａｉの値が非ゼロである全てのｉについて行われる。そして、以上のようにして算出されたマージンの値が「０」より大きかったならば、当該ドキュメントＸは、当該ハイパー平面によってモデル化されたドキュメント・クラスに対して関連性を有する関連ドキュメントに分類され、一方、算出されたマージンの値が「０」より小さかったならば、当該ドキュメントＸは、そのドキュメント・クラスに対して関連性を有さない無関連ドキュメントに分類される。
【００４７】
ＳＶＭドキュメント分類モデルにトレーニングを施して生成するためのアルゴリズムとしては、以上に説明したアルゴリズムの他にも、当業者には周知の様々なアルゴリズムが存在しており、本発明に係る類似性構造体は、それらアルゴリズムにも使用可能である。それゆえ、以上に説明した具体例のトレーニング・アルゴリズム並びに具体例のドキュメント分類モデルは、あくまでも具体例を提示することを目的としたものであり、本発明はそれら具体例のみに限定されない。
【００４８】
スレショルド類似度値の設定の仕方については、先に図３を参照してその１つの具体例について説明したが、スレショルド類似度値の設定の仕方にはその他にも様々な方法がある。例えば、トレーニング・アルゴリズムを実行してドキュメント分類モデルを生成する際に、経験的方法によって、即ち、トライアル・アンド・エラー方式で、スレショルド類似度値を設定することも可能である。より詳しくは、トライアル・アンド・エラー方式のテストを行って、スレショルド類似度値をある値に設定したときに、或いは、スレショルド類似度値をある範囲内の値に設定したときに、正ドキュメントと負ドキュメントとを適切に弁別するドキュメント・クラシファイヤを生成することのできるトレーニング・アルゴリズムの能力を殆ど損なうことなく、必要格納容量を大幅に低減できる（例えば、６０％、７０％、８０％、９０％の低減ができる）ことを確認すればよい。従って、トライアル・アンド・エラー方式のテストを行うことによって、スレショルド類似度値を効果的に「チューニング」して、有利なスレショルド値に設定することができる。また別の具体例として、スレショルド類似度値を、ある値に設定したときに、所与の大きさのドキュメント集合に対応した従来の類似性行列の大きさと比較して格段に小さな大きさの類似性構造体が生成される（例えば、所与のドキュメント集合に対応した従来の類似性行列の大きさの約２０％の大きさしかない類似性構造体が生成される）ことを確認するようにしてもよい。この場合、トレーニング集合であるドキュメント集合の、ある部分集合に含まれているドキュメントに対してのみトレーニング・アルゴリズムを実行して、その部分集合における夫々のドキュメント・ペアの類似度値から成る類似度値集合を生成するだけで、トレーニング・アルゴリズムを完了してしまうことができる。続いて、その類似度値集合に含まれている類似度値のアセスメントを行うことによって、スレショルド類似度値をどのような値に設定すれば、その部分集合に含まれているドキュメントのうちの所望の割合のドキュメントが除外されるようにすることができるのかを判定する。続いて、このようにして判定したスレショルド類似度値を適用することによって、そのドキュメント集合の全体集合（即ち、そのトレーニング集合の全体集合）に対応した類似性構造体を生成することができ、この類似性構造体を使用することで、全体集合に対応した類似性構造体によるドキュメント分類モデルのトレーニングを行うことができる。
【００４９】
別の具体例として、スレショルド類似度値を設定するために、Ｎフォールド・クロスバリデーション法を用いるという方法があり、それによってスレショルド類似度値を有利な値に設定することができる。この具体例では、先ず、トレーニング集合であるドキュメント集合を、ドキュメントの個数が互いに略々等しいＮ個のドキュメント群に分割する。そして、それらＮ個のドキュメント群のうちのつの１つをテスト用ドキュメント集合とし、残りの（Ｎ−１）個のドキュメント群を用いて、ドキュメント分類モデルにトレーニングを施すようにし、そのトレーニングに際しては、スレショルド類似度値を所与のテスト用スレショルド類似度値に設定しておく。このトレーニングによって得られたドキュメント・クラシファイヤ（即ち、このトレーニングによって生成されたハイパー平面）に基づいて、テスト用ドキュメント集合に含まれているドキュメントの分類を行い、その分類性能（例えば、適正に分類されたドキュメントの割合などの、分類性能を表す適当な指標値）を記録する。これと同じプロセスを、更に（Ｎ−１）回に亘って反復実行し、その反復実行の度に、Ｎ個のドキュメント群のうちの異なったドキュメント群をテスト用ドキュメント集合とし、ただし、テスト用スレショルド類似度値は同一の値に設定しておく。そして、Ｎ個のドキュメント群を夫々にテスト用ドキュメント集合として実行して得られた全てのドキュメント・クラシファイヤの平均性能指標値を記録する。また更に、以上に説明したプロセスの全体を、テスト用スレショルド類似度値を別の新たな値に設定した上で反復実行する。従って、以上のＮフォールド・クロスバリデーションの全体によって、設定した複数のテスト用スレショルド類似度値の各々に１つずつが対応した、複数の平均性能指標値が得られる。そして、それら複数のテスト用スレショルド類似度値のうち、その平均性能指標値が最も優れている１つのテスト用スレショルド類似度値を、最終的なスレショルド類似度値として選択し、その選択したスレショルド類似度値を、先に説明したように類似性構造体を生成するために用いればよい。この方法によって得られるスレショルド類似度値は非常に優れたものであり、なぜならば、そのスレショルド類似度値は、同一ではないが同様のドキュメント群を分類するためのドキュメント・クラシファイヤに対しても適用できるからである。従って、この具体例は、スレショルド類似度値を「チューニング」して有利な値に設定することのできるもう１つの別の方法を提供するものである。
【００５０】
以上に説明した類似性構造体は、例えばドキュメント分類モデルにトレーニングを施すためなどに使用し得るものであり、その場合に、従来の類似性行列と比較して格段の利点を提供するものである。例えば、同じトレーニング用ドキュメント集合に対応した従来の類似性行列と以上に説明した類似性構造体とでは、以上に説明した類似性構造体の方が、そのサイズをはるかに小さくし得るため、以上に説明した類似性構造体を格納するために必要とされるストレージ容量は、従来の類似性行列を格納するために必要とされるストレージ容量と比べて格段に小さなものとすることができ、また以上に説明した類似性構造体を算出するために必要とされる計算時間は、従来の類似性行列を算出するために必要とされる計算時間と比べて格段に短縮することができる。更に、本発明の発明者が確認したところによれば、大部分のドキュメント・ペアについて、それらドキュメント・ペアの実際の類似度値ではなく、デフォールト類似度値が用いられた場合であっても、関連ドキュメントと無関連ドキュメントとを有意に弁別することのできるドキュメント分類モデルの能力を何ら損なうことなく、以上の利点が提供されるのである。また、所与のトレーニング用ドキュメント集合に対応した従来の類似性行列のサイズと本発明に係る類似性構造体のサイズとを比べたとき、本発明に係る類似性構造体のサイズが従来の類似性行列のサイズの１０〜２０％となっている場合であっても、以上に説明した本発明に係るコンパクト類似性構造体を使用してトレーニングを施すことによって得られるドキュメント分類モデルの性能は、従来の類似性行列を使用してトレーニングを施した場合と同等の性能であることも確認された。
【００５１】
ハードウェアの概要説明
図６に示したのは、本発明の実施の形態に係る方法を実行するために使用することのできるコンピュータ・システムの１つの具体例のブロック図である。このコンピュータ・システム１３００は、バス１３０２などのデータ伝達機構と、バス１３０２に接続されたデータ処理のためのプロセッサ１３０４とを備えている。コンピュータ・システム１３００は更に、バス１３０２に接続されたメイン・メモリ１３０６を備えており、このメイン・メモリ１３０６は、例えばランダム・アクセス・メモリ（ＲＡＭ）などのダイナミック・ストレージ・デバイスであって、データとプロセッサ１３０４が実行する命令とを格納するものである。このメイン・メモリ１３０６は更に、プロセッサ１３０４が命令を実行しているときに、一時的な変数や中間データを格納するためにも用いられる。コンピュータ・システム１３００は更に、バス１３０２に接続された、リード・オンリ・メモリ（ＲＯＭ）１３０８などのスタティック・ストレージ・デバイスを備えており、このスタティック・ストレージ・デバイスは、書換えられることのない、データやプロセッサ１３０４が実行する命令を格納するものである。更に、ストレージ・デバイス１３１０が備えられており、このストレージ・デバイス１３１０は、磁気ディスクや光ディスクなどであり、バス１３０２に接続されており、データや命令を格納するものである。
【００５２】
コンピュータ・システム１３００には、バス１３０２を介してディスプレイ１３１２を接続することができ、このディスプレイ１３１２は、コンピュータのユーザに対して情報を表示するものである。英数字キー及びその他のキーを備えた入力デバイス１３１４が、バス１３０２に接続されており、この入力デバイス１３１４は、データや選択したコマンドをプロセッサ１３０４に伝達するために用いられる。その他の種類のユーザ入力デバイスとして、マウス、トラックボール、それにカーソル移動キーなどの、カーソル制御デバイス１３１５が備えられており、このカーソル制御デバイス１３１５は、支持データや選択したコマンドをプロセッサ１３０４に伝達するために、また、ディスプレイ１３１２上のカーソルの移動を制御するために用いられる。
【００５３】
本明細書において先に説明した、類似性構造体を構築する方法の具体例や、類似性構造体を使用する方法の具体例は、このコンピュータ・システム１３００を用いて実行することができる。プロセッサ１３０４は、それら方法のための処理を実行する際には、様々な命令シーケンスを実行すると共に、メイン・メモリ１３０６及び／またはストレージ・デバイス１３１０をはじめとする、様々なメモリやストレージ・デバイスとの間で然るべく通信を行う。それらメモリないしストレージ・デバイスには、ドキュメント集合に含まれているドキュメントや、それらドキュメントに対応した類似度値（例えば類似性スコア値など）を格納し、また、取出すことができるようにしてあり、それらの格納及び取出しのためには、例えば、それらメモリないしストレージ・デバイスの中に適当なデータベースを構築しておくなどすればよい。実行する処理命令は、ストレージ・デバイス１３１０などのコンピュータ読取り可能な媒体から、メイン・メモリ１３０６の中へ読み込まれるようにしておくのもよい。ただし、処理命令を格納しておくコンピュータ読取り可能な媒体は、ストレージ・デバイス１３１０のようなデバイスのみに限定されない。例えば、利用可能なコンピュータ読取り可能な媒体には、フロッピー（登録商標）・ディスク、フレキシブル・ディスク、ハード・ディスク、磁気テープ、その他の様々な磁気記録媒体、ＣＤ−ＲＯＭ、その他の様々な光記憶媒体、ＲＡＭ、ＰＲＯＭ、ＥＰＲＯＭ、ＦＬＡＳＨ−ＥＰＲＯＭ、その他の様々なチップまたはカートリッジ型の媒体、また更にその他の、コンピュータが読取を行うことのできる様々な記録媒体があり、そのような媒体に、本明細書で説明した方法をプロセッサ１３０４に実行させるための適当なコンピュータ命令セットを格納しておけばよい。その命令シーケンスを実行させることによって、プロセッサ１３０４に、本明細書において先に説明した様々な処理ステップを実行させることができる。また、別の実施の形態として、ソフトウェア命令の替わりに、或いは、ソフトウェア命令と併用して、ハード・ワイヤド回路を用いて、本明細書において説明した具体例の方法を実行させるようにすることも可能である。従って、本発明は、様々な実施の形態とすることができ、ハードウェア回路とソフトウェアとの特定の組合せに限定されるものではない。
【００５４】
コンピュータ・システム１３００には、更に、バス１３０２に接続された通信インターフェース１３１６を備えるようにするのもよい。この通信インターフェース１３１６は、ネットワーク・リンク１３２０との間の双方向データ通信接続を提供するものであり、このネットワーク・リンク１３２０はローカル・ネットワーク１３２２及びインターネット１３２８に接続されている。このネットワーク・リンク１３２０を介して、インターネット１３２８とコンピュータ・システム１３００との間で、クラスタ化しようとするドキュメント集合を伝送することができ、そうすることで、処理対象のドキュメントを１つまたは複数のソースから取得することができる。通信インターフェース１３１６の具体例としては、例えば、対応する種類の電話線に対するデータ通信接続を提供する、サービス統合デジタル通信網（ＩＳＤＮ）カードや、モデムなどを挙げることができる。また、別の具体例として、通信インターフェース１３１６を、対応するＬＡＮに対するデータ通信接続を提供する、ローカル・エリア・ネットワーク（ＬＡＮ）カードとすることもできる。更には、無線リンクを提供するようなものとすることもできる。いずれの形態にせよ、通信インターフェース１３１６は、様々な種類の情報を表すデジタル・データ・ストリームを伝送するための、電気信号、電磁気信号、または光信号を送受信するものである。
【００５５】
ネットワーク・リンク１３２０は、その典型的な具体例においては、１つまたは複数のネットワークを介して他のデータ・デバイスとの間でデータ通信を行えるようにするものである。より具体的には、例えば、ネットワーク・リンク１３２０は、ローカル・ネットワーク１３２２を介して、ホスト・コンピュータ１３２４への接続や、インターネット・サービス・プロバイダ（ＩＳＰ）１３２６が運用しているデータ機器への接続を提供するものである。そして、ＩＳＰ１３２６は、インターネット１３２８を介した通信サービスを提供している。ローカル・ネットワーク１３２２と、インターネット１３２８とは、いずれも、デジタル・データ・ストリームを伝送するために、電気信号、電磁気信号、または光信号を使用している。コンピュータ・システム１３００が送受信するデジタル・データを伝送するための、それら様々なネットワーク上の信号、並びに、通信インターフェース１３１６及びネットワーク・リンク１３２０上の信号は、例えば、情報を伝送するための変調波形などから成る信号である。
【００５６】
このように、コンピュータ・システム１３００は、様々なネットワークと、ネットワーク・リンク１３２０と、通信インターフェース１３１６とを介して、様々なメッセージを送信することができ、また、プログラム・コードなどを含めた様々なデータを受信することができる。例えばインターネット１３２８に関していえば、サーバ１３３０が、アプリケーション・プログラムを要求されたときに、そのアプリケーション・プログラムのプログラム・コードを、インターネット１３２８と、ＩＳＰ１３２６と、ローカル・ネットワーク１３２２と、通信インターフェース１３１６とを介して送信することができる。本発明においては、そのような、ダウンロード可能なアプリケーションによって、先に説明したドキュメント処理を実行するようにすることができる。また、その場合に、プロセッサ１３０４は、ネットワークを介して受信するプログラム・コードを、受信と同時に実行するようにすることもでき、或いはまた、受信したプログラム・コードを一旦、ストレージ・デバイス１３１０や、その他の不揮発性ストレージなどに格納して、後で実行するようにすることもできる。この場合、コンピュータ・システム１３００は、アプリケーション・プログラムのプログラム・コードを、変調波形の形で入手することになるが、このような形態のものも、コンピュータ読取り可能な媒体の範疇に含まれる。
【００５７】
本発明は、その構成要素の全部または一部を、分散したロケーションに存在しているメモリまたはディスクに格納しておき、それら構成要素をアプリケーションが同期的または非同期的にアクセスするようにし、そして、構成要素が分解された形態で格納されている場合には、それら構成要素をメモリの中で組立てることにより、ドキュメントの取出し、ドキュメントのスコア値算出、及び／または、ドキュメント分類に用いるデータを提供できるようにすることも可能である。
【００５８】
以上、本発明をその幾つかの実施の形態に即して具体的に図示して説明したが、図示して説明したそれら実施の形態に対して、本発明の概念並びに範囲から逸脱することなく構成ないし細部構造に関する様々な変更を加え得ることは、当業者には容易に理解されることである。
【図面の簡単な説明】
【００５９】
【図１】トレーニング集合である事例ドキュメント集合における夫々のドキュメント・ペア間の類似度を表しているデータ構造体の１つの具体例を示した図である。
【図２】トレーニング集合である事例ドキュメント集合における夫々のドキュメント・ペア間の類似度を表しているデータ構造体の別の具体例を示した図である。
【図３】コンパクト類似性構造体を構築する方法の具体例を示したフローチャートであり、かかる方法は本発明の１つの局面をなすものである。
【図４】コンパクト類似性構造体を使用して情報を参照する方法の具体例を示したフローチャートであり、かかる方法は本発明の別の１つの局面をなすものである。
【図５】コンパクト類似性構造体を使用してドキュメント解析モデルにトレーニングを施す方法の具体例を示したフローチャートであり、かかる方法は本発明のまた別の１つの局面をなすものである。
【図６】コンパクト類似性構造体を構築する及び／または使用する方法の具体例を実行することのできるコンピュータ・システムの具体例のブロック図であり、かかるコンピュータ・システムは本発明のまた別の１つの局面をなすものである。
【図１】
2009519543.tif 000007
【図２】
2009519543.tif 000008
【図３】
2009519543.tif 000009
【図４】
2009519543.tif 000010
【図５】
2009519543.tif 000011
【図６】
2009519543.tif 000012
【国際調査報告】
2009519543.tif 000013