(57)【要約】【課題】ウェブ・ディレクトリに有用であり、あるいは、情報検索を改良するための、自動的に生成されたさまざまなクラスタを関連づけて符号を付ける方法を提供すること。【解決手段】ドキュメントのポジティブ・セットからフィーチャーの第１のヒストグラムを供給するステップと、ドキュメントのコレクション・セットからフィーチャーの第２のヒストグラムを供給するステップと、前記フィーチャーを含む前記ポジティブ・セット内の前記ドキュメントの割合と、前記フィーチャーを含む前記コレクション・セット内の前記ドキュメントの割合にもとづいて、各フィーチャーがセルフ・フィーチャー、ペアレント・フィーチャーあるいはチャイルド・フィーチャーであるか否かを決定するステップを有する。【選択図】図１
2006318511.tif 000002
【特許請求の範囲】
【請求項１】
ドキュメントのポジティブ・セットからフィーチャーの第１のヒストグラムを供給するステップと、
ドキュメントのコレクション・セットからフィーチャーの第２のヒストグラムを供給するステップと、
前記フィーチャーを含む前記ポジティブ・セット内の前記ドキュメントの割合と、前記フィーチャーを含む前記コレクション・セット内の前記ドキュメントの割合にもとづいて、各フィーチャーがセルフ・フィーチャー、ペアレント・フィーチャーあるいはチャイルド・フィーチャーであるか否かを決定するステップを有する１組のドキュメントの階層的記述を推測する方法。
【請求項２】
ヒストグラム閾値を設定し、前記第１のヒストグラムおよび前記第２のヒストグラムの両方の中の前記閾値以下のフィーチャーを除去するステップをさらに有する請求項１記載の１組のドキュメントの階層的記述を推測する方法。
【請求項３】
ドキュメントの前記ポジティブ・セット内の出現の順序により前記フィーチャーを順位付けることをさらに有する請求項１記載の１組のドキュメントの階層的記述を推測する方法。
【請求項４】
ドキュメントは画像データを有する請求項１記載の１組のドキュメントの階層的記述を推測する方法。
【請求項５】
ドキュメントはテキストデータを有する請求項１記載の１組のドキュメントの階層的記述を推測する方法。
【請求項６】
前記テキストデータは英語以外の言語である請求項５記載の１組のドキュメントの階層的記述を推測する方法。
【請求項７】
ドキュメントはオーディオデータを有する請求項１記載の１組のドキュメントの階層的記述を推測する方法。
【請求項８】
ドキュメントはマルチメディア・データを有する請求項１記載の１組のドキュメントの階層的記述を推測する方法。
【請求項９】
前記決定するステップは、ペアレント、チルドレンおよびセルフ予測アルゴリズムを使用して実行される請求項１記載の１組のドキュメントの階層的記述を推測する方法。
【請求項１０】
ヒストグラム閾値を設定し、前記第１のヒストグラムおよび前記第２のヒストグラムの両方の中の前記閾値以下のフィーチャーを除去するステップをさらに有する請求項９記載の１組のドキュメントの階層的記述を推測する方法。
【請求項１１】
ドキュメントの前記ポジティブ・セット内の出現の順序により前記フィーチャーを順位付けることをさらに有する請求項９記載の１組のドキュメントの階層的記述を推測する方法。
【請求項１２】
ドキュメントは画像データを有する請求項９記載の１組のドキュメントの階層的記述を推測する方法。
【請求項１３】
ドキュメントはテキストデータを有する請求項９記載の１組のドキュメントの階層的記述を推測する方法。
【請求項１４】
前記テキストデータは英語以外の言語である請求項１３記載の１組のドキュメントの階層的記述を推測する方法。
【請求項１５】
ドキュメントはオーディオデータを有する請求項９記載の１組のドキュメントの階層的記述を推測する方法。
【請求項１６】
ドキュメントはマルチメディア・データを有する請求項９記載の１組のドキュメントの階層的記述を推測する方法。
【請求項１７】
ドキュメントのポジティブ・セットを有するＵＲＬの第１の集合を得るステップと、
ドキュメントのコレクション・セットを有するＵＲＬの第２の集合を得るステップと、
ＵＲＬの前記第１の集合内の各ＵＲＬと、ＵＲＬの前記第２の集合内の各ＵＲＬに対するインバウンド・リンクを決定するステップと、
ドキュメントの前記ポジティブ・セット内の各ＵＲＬに対する仮想ドキュメントと、ドキュメントの前記コレクション・セット内の各ＵＲＬに対する仮想ドキュメントを創るステップと、
ＵＲＬの前記第１の集合と組み合わされた前記仮想ドキュメントからフィーチャーの第１のヒストグラムを供給するステップと、
ＵＲＬの前記第２の集合と組み合わされた前記仮想ドキュメントからフィーチャーの第２のヒストグラムを供給するステップと、
前記フィーチャーを含むドキュメントの前記ポジティブ・セットと組み合わされた前記仮想ドキュメントの割合と、前記フィーチャーを含むドキュメントの前記コレクション・セットと組み合わされた前記仮想ドキュメントの割合にもとづいて、各フィーチャーがセルフ・フィーチャー、ペアレント・フィーチャーあるいはチャイルド・フィーチャーであるか否かを決定するステップを有するウェブ・ページを有する１組のドキュメントの階層的記述を推測する方法。
【請求項１８】
ヒストグラム閾値を設定し、前記第１のヒストグラムおよび前記第２のヒストグラムの両方の中の前記閾値以下のフィーチャーを除去するステップをさらに有する請求項１７記載の１組のドキュメントの階層的記述を推測する方法。
【請求項１９】
ドキュメントの前記ポジティブ・セット内の出現の順序により前記フィーチャーを順位付けることをさらに有する請求項１７記載の１組のドキュメントの階層的記述を推測する方法。
【請求項２０】
ＵＲＬは画像データを含むページを示す請求項１７記載の１組のドキュメントの階層的記述を推測する方法。
【請求項２１】
ＵＲＬはテキストデータを含むページを示す請求項１７記載の１組のドキュメントの階層的記述を推測する方法。
【請求項２２】
前記テキストデータは英語以外の言語である請求項２１記載の１組のドキュメントの階層的記述を推測する方法。
【請求項２３】
ＵＲＬはオーディオデータを含むページを示す請求項１７記載の１組のドキュメントの階層的記述を推測する方法。
【請求項２４】
ＵＲＬはマルチメディア・データを含むページを示す請求項１７記載の１組のドキュメントの階層的記述を推測する方法。
【請求項２５】
各フィーチャーがセルフ・フィーチャー、ペアレント・フィーチャーあるいはチャイルド・フィーチャーであるか否かを決定する前記ステップは、ペアレント、チルドレンおよびセルフ予測アルゴリズムを使用して実行される請求項１７記載のウェブ・ページを有する１組のドキュメントの階層的記述を推測する方法。
【請求項２６】
ヒストグラム閾値を設定し、前記第１のヒストグラムおよび前記第２のヒストグラムの両方の中の前記閾値以下のフィーチャーを除去するステップをさらに有する請求項２５記載の１組のドキュメントの階層的記述を推測する方法。
【請求項２７】
ドキュメントの前記ポジティブ・セット内の出現の順序により前記フィーチャーを順位付けることをさらに有する請求項２５記載の１組のドキュメントの階層的記述を推測する方法。
【請求項２８】
ＵＲＬは画像データを含むページを示す請求項２５記載の１組のドキュメントの階層的記述を推測する方法。
【請求項２９】
ＵＲＬはテキストデータを含むページを示す請求項２５記載の１組のドキュメントの階層的記述を推測する方法。
【請求項３０】
前記テキストデータは英語以外の言語である請求項２９記載の１組のドキュメントの階層的記述を推測する方法。
【請求項３１】
ＵＲＬはオーディオデータを含むページを示す請求項２５記載の１組のドキュメントの階層的記述を推測する方法。
【請求項３２】
ＵＲＬはマルチメディア・データを含むページを示す請求項２５記載の１組のドキュメントの階層的記述を推測する方法。
【請求項３３】
情報検索システムに検索問い合わせを提出するステップと、
前記検索問い合わせに応答する前記情報検索システムからのドキュメントの第１の集合を検索するステップと、
ドキュメントの第２の集合を供給するステップと、
前記第１の集合のドキュメント内の各検索されたドキュメントに対して、ならびにドキュメントの前記第２の集合内の各ドキュメントに対して、インバウンド・リンクを決定するステップと、
ドキュメントの前記第１の集合内の各ドキュメントに対して、ならびにドキュメントの前記第２の集合内の各ドキュメントに対して、仮想ドキュメントを創出するステップと、
ドキュメントの前記第１の集合と組み合わされた前記仮想ドキュメント内にフィーチャーの第１のヒストグラムを創出するステップと、
ドキュメントの前記第２の集合と組み合わされた前記仮想ドキュメント内にフィーチャーの第２のヒストグラムを創出するステップと、
前記フィーチャーを含むドキュメントの前記ポジティブ・セットと組み合わされた前記仮想ドキュメントの割合と、前記フィーチャーを含むドキュメントの前記コレクション・セットと組み合わされた前記仮想ドキュメントの割合にもとづいて、各フィーチャーがセルフ・フィーチャー、ペアレント・フィーチャーあるいはチャイルド・フィーチャーであるか否かを決定するステップと、
フィーチャーの分類に応答する前記検索問い合わせを変えるステップと、
ヒストグラム閾値を設定し、前記第１のヒストグラムおよび前記第２のヒストグラムの両方の中の前記閾値以下のフィーチャーを除去するステップと、
を有する１組のドキュメントの推測にもとづく階層的記述を使用する情報検索システムの検索方法。
【請求項３４】
情報検索システムに検索問い合わせを提出するステップと、
前記検索問い合わせに応答する前記情報検索システムからのドキュメントの第１の集合を検索するステップと、
ドキュメントの第２の集合を供給するステップと、
前記第１の集合のドキュメント内の各検索されたドキュメントに対して、ならびにドキュメントの前記第２の集合内の各ドキュメントに対して、インバウンド・リンクを決定するステップと、
ドキュメントの前記第１の集合内の各ドキュメントに対して、ならびにドキュメントの前記第２の集合内の各ドキュメントに対して、仮想ドキュメントを創出するステップと、
ドキュメントの前記第１の集合と組み合わされた前記仮想ドキュメント内にフィーチャーの第１のヒストグラムを創出するステップと、
ドキュメントの前記第２の集合と組み合わされた前記仮想ドキュメント内にフィーチャーの第２のヒストグラムを創出するステップと、
前記フィーチャーを含むドキュメントの前記ポジティブ・セットと組み合わされた前記仮想ドキュメントの割合と、前記フィーチャーを含むドキュメントの前記コレクション・セットと組み合わされた前記仮想ドキュメントの割合にもとづいて、各フィーチャーがセルフ・フィーチャー、ペアレント・フィーチャーあるいはチャイルド・フィーチャーであるか否かを決定するステップと、
フィーチャーの分類に応答する前記検索問い合わせを変えるステップと、
ドキュメントの前記第１の集合内の出現の順序により前記フィーチャーを順位付けるステップと、を有する１組のドキュメントの推測にもとづく階層的記述を使用する情報検索システムの検索方法。
【請求項３５】
各フィーチャーがセルフ・フィーチャー、ペアレント・フィーチャーあるいはチャイルド・フィーチャーであるか否かを決定する前記ステップは、ペアレント、チルドレンおよびセルフ予測アルゴリズムを使用して実行され、ヒストグラム閾値を設定し、前記第１のヒストグラムおよび前記第２のヒストグラムの両方の中の前記閾値以下のフィーチャーを除去するステップをさらに有する請求項３３または請求項３４記載の１組のドキュメントの推測にもとづく階層的記述を使用する情報検索システムの検索方法。
【請求項３６】
各フィーチャーがセルフ・フィーチャー、ペアレント・フィーチャーあるいはチャイルド・フィーチャーであるか否かを決定する前記ステップは、ペアレント、チルドレンおよびセルフ予測アルゴリズムを使用して実行され、ドキュメントの前記第１の集合内の出現の順序により前記フィーチャーを順位付けるステップをさらに有する請求項３３または請求項３４記載の１組のドキュメントの推測にもとづく階層的記述を使用する情報検索システムの検索方法。
【請求項３７】
（ａ）ドキュメントの集合の階層を設けるステップと、
（ｂ）ドキュメントのコレクション・セットを設けるステップと、
（ｃ）前記階層内の１組のドキュメント内の各ドキュメントに対して、ならびにドキュメントの前記コレクション・セット内の各ドキュメントに対して、インバウンド・リンクを決定するステップと、
（ｄ）前記階層内のドキュメントの前記集合内の各ドキュメントに対して、ならびにドキュメントの前記コレクション・セット内の各ドキュメントに対して、仮想ドキュメントを創出するステップと、
（ｅ）前記階層内のドキュメントの前記集合と組み合わされた前記仮想ドキュメントからフィーチャーの第１のヒストグラムを創出するステップと、
（ｆ）ドキュメントの前記コレクション・セットと組み合わされた前記仮想ドキュメントからフィーチャーの第２のヒストグラムを創出するステップと、
（ｇ）前記フィーチャーを含む前記階層内のドキュメントの前記集合と組み合わされた前記仮想ドキュメントの割合と、前記フィーチャーを含むドキュメントの前記コレクション・セットと組み合わされた仮想ドキュメントの割合にもとづいて、各フィーチャーがセルフ・フィーチャー、ペアレント・フィーチャーあるいはチャイルド・フィーチャーであるか否かを決定するステップと、
（ｈ）ドキュメントの集合の前記階層内のドキュメントの各集合に対してステップ（ｃ）からステップ（ｇ）を繰り返すステップと、
（ｉ）各フィーチャーを決定することに応答するドキュメントの集合の前記階層に符号を付けるステップを有するドキュメントの集合の推測にもとづく記述を使用してドキュメント・ディレクトリに符号を付ける方法。
【請求項３８】
各フィーチャーがセルフ・フィーチャー、ペアレント・フィーチャーあるいはチャイルド・フィーチャーであるか否かを決定する前記ステップは、ペアレント、チルドレンおよびセルフ予測アルゴリズムを使用して実行される請求項３７記載のドキュメントの集合の推測にもとづく記述を使用してドキュメント・ディレクトリに符号を付ける方法。
【請求項３９】
（ａ）ドキュメントの集合の階層を設けるステップと、
（ｂ）ドキュメントのコレクション・セットを設けるステップと、
（ｃ）前記階層内のドキュメントの各集合からフィーチャーの第１のヒストグラムを創出するステップと、
（ｄ）ドキュメントの前記コレクション・セットからフィーチャーの第２のヒストグラムを創出するステップと、
（ｅ）前記フィーチャーを含む前記階層内のドキュメントの前記集合と組み合わされたドキュメントの割合と、前記フィーチャーを含むドキュメントの前記コレクション・セットと組み合わされたドキュメントの割合にもとづいて、各フィーチャーがセルフ・フィーチャー、ペアレント・フィーチャーあるいはチャイルド・フィーチャーであるか否かを決定するステップと、
（ｆ）ドキュメントの集合の前記階層内のドキュメントの各集合に対してステップ（ｃ）からステップ（ｅ）を繰り返すステップと、
（ｇ）各フィーチャーを決定することに応答するドキュメントの集合の前記階層に符号を付けるステップを有するドキュメントの集合の推測にもとづく記述を使用してドキュメント・ディレクトリに符号を付ける方法。
【請求項４０】
各フィーチャーがセルフ・フィーチャー、ペアレント・フィーチャーあるいはチャイルド・フィーチャーであるか否かを決定する前記ステップは、ペアレント、チルドレンおよびセルフ予測アルゴリズムを使用して実行される請求項３９記載のドキュメントの集合の推測にもとづく記述を使用してドキュメント・ディレクトリに符号を付ける方法。
【請求項４１】
ドキュメントのポジティブ・セットを有するドキュメントの第１の集合を得るステップと、
ドキュメントのコレクション・セットを有するドキュメントの第２の集合を得るステップと、
ドキュメントの前記第１の集合内の各ドキュメントに対して、ならびにドキュメントの前記第２の集合内の各ドキュメントに対して、インバウンド・リンクを決定するステップと、
ドキュメントの前記ポジティブ・セット内の各ドキュメントに対する仮想ドキュメント、およびドキュメントの前記コレクション・セット内の各ドキュメントに対する仮想ドキュメントを創出するステップと、
ドキュメントの前記第１の集合と組み合わされた前記仮想ドキュメントからフィーチャーの第１のヒストグラムを供給するステップと、
ドキュメントの前記第２の集合と組み合わされた前記仮想ドキュメントからフィーチャーの第２のヒストグラムを供給するステップと、
前記フィーチャーを含むドキュメントの前記ポジティブ・セットと組み合わされた前記仮想ドキュメントの割合と、前記フィーチャーを含むドキュメントの前記コレクション・セットと組み合わされた前記仮想ドキュメントの割合にもとづいて、各フィーチャーがセルフ・フィーチャー、ペアレント・フィーチャーあるいはチャイルド・フィーチャーであるか否かを決定するステップを有する１組のドキュメントの階層的記述を推測する方法。
【請求項４２】
ヒストグラム閾値を設定し、前記第１のヒストグラムおよび前記第２のヒストグラムの両方の中の前記閾値以下のフィーチャーを除去するステップをさらに有する請求項４１記載の１組のドキュメントの階層的記述を推測する方法。
【請求項４３】
ドキュメントの前記ポジティブ・セット内の出現の順序により前記フィーチャーを順位付けることをさらに有する請求項４１記載の１組のドキュメントの階層的記述を推測する方法。
【請求項４４】
ドキュメントは画像データを含む請求項４１記載の１組のドキュメントの階層的記述を推測する方法。
【請求項４５】
ドキュメントはテキストデータを含む請求項４１記載の１組のドキュメントの階層的記述を推測する方法。
【請求項４６】
前記テキストデータは英語以外の言語である請求項４５記載の１組のドキュメントの階層的記述を推測する方法。
【請求項４７】
ドキュメントはオーディオデータを含む請求項４１記載の１組のドキュメントの階層的記述を推測する方法。
【請求項４８】
ドキュメントはマルチメディア・データを含む請求項４１記載の１組のドキュメントの階層的記述を推測する方法。
【請求項４９】
各フィーチャーがセルフ・フィーチャー、ペアレント・フィーチャーあるいはチャイルド・フィーチャーであるか否かを決定する前記ステップは、ペアレント、チルドレンおよびセルフ予測アルゴリズムを使用して実行される請求項４１記載の１組のドキュメントの階層的記述を推測する方法。
【請求項５０】
ヒストグラム閾値を設定し、前記第１のヒストグラムおよび前記第２のヒストグラムの両方の中の前記閾値以下のフィーチャーを除去するステップをさらに有する請求項４９記載の１組のドキュメントの階層的記述を推測する方法。
【請求項５１】
ドキュメントの前記ポジティブ・セット内の出現の順序により前記フィーチャーを順位付けることをさらに有する請求項４９記載の１組のドキュメントの階層的記述を推測する方法。
【請求項５２】
ドキュメントは画像データを含む請求項４９記載の１組のドキュメントの階層的記述を推測する方法。
【請求項５３】
ドキュメントはテキストデータを含む請求項４９記載の１組のドキュメントの階層的記述を推測する方法。
【請求項５４】
前記テキストデータは英語以外の言語である請求項５３記載の１組のドキュメントの階層的記述を推測する方法。
【請求項５５】
ドキュメントはオーディオデータを含む請求項４９記載の１組のドキュメントの階層的記述を推測する方法。
【請求項５６】
ドキュメントはマルチメディア・データを含む請求項４９記載の１組のドキュメントの階層的記述を推測する方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はワールド・ワイド・ウェブの検索に関し、具体的には、階層的情報についての事前の知識は何等無しに、検索されたウェブ・ページの小さい集合から、トピックについての階層的関係を推測することに関する。
【０００２】
さらに本発明は、ドキュメントの小さな集合の記述的名称である語、あるいは、句のグループを自動的に判定することと、概念についての事前の知識は何等無しに、記述的名称よりも一般的でより具体的なドキュメントの集合内の概念を推測することに関する。記述的名称および概念は、ドキュメントに含まれていないことさえ有り得る。本発明の主な応用はワールド・ワイド・ウェブの検索であるが、本発明はワールド・ワイド・ウェブあるいは特定の情報検索システムに使用することのみに制限されず、ドキュメントの任意の集合に応用することができる。
【背景技術】
【０００３】
ワールド・ワイド・ウェブの急速な発展は、オンライン・テキスト・ドキュメントの検索、ブラウジングおよび系統化を容易にすることを目的とする研究の急増をもたらした。この研究の多くは、ドキュメントを意味のあるグループにクラスタ化することに重点を置かれた。ドキュメント・クラスタを集合、あるいは階層化する多くの場合、利用者は、特定のドキュメントを詳細を確かめることなくクラスタを識別するために、コレクションにざっと目を通すことを好む。
【０００４】
ワールド・ワイド・ウェブは、生物学コミュニティ、あるいはＩＳＰホームページのコミュニティのような、関連するドキュメントについて大量な数のコミュニティを含んでいる。本発明は、孤立している単一のコミュニティについての有用な階層的情報を自動的に推測する方法である。
【０００５】
１組のドキュメントから始まって、その１組のドキュメントに関するさまざまに有用ないくつかの情報を自動的に推測することが望ましい。その情報は、記述的な名称あるいは関連する概念（時にはドキュメントの中に明示的に含まれていない）を有してもよい。このような情報は、検索あるいは解析のために有用である。
【０００６】
クラスタリングは、構成要素がある点で、対象を類似であるグループに系統化する処理と定義することができる。クラスタリングには、すべての対象が厳密に１つのグループに指定される「分割」（多くの場合ｋ−クラスタリングと呼ばれる）と、１を超える大きさの各グループをより小さなグループで構成することが可能な「階層的クラスタリング」の２つの主な形式がある。ワールド・ワイド・ウェブ検索エンジンの出現、明確には、利用可能な大量のデータを系統化する課題と、大規模データベースの「データ・マイニング」の概念は、クラスタリング・アルゴリズムに対する関心を復活させた。
【０００７】
本発明は、ドキュメントの集合あるいはクラスタの理解を助けるために、フィーチャーの意味のあるクラスを識別する方法を提供する。フィーチャーには３つのクラスがあることが望ましい。「セルフ」フィーチャーあるいはセルフ・タームは、全体としてクラスタを記述する。「ペアレント」フィーチャーあるいはペアレント・タームは、一般的な概念を記述する。「チャイルド」フィーチャーあるいはチャイルド・タームは、クラスタの特殊化を記述する。たとえば、１組の生物学ドキュメントを仮定すると、ペアレント・タームは科学であってよく、セルフ・タームは生物学であってよく、チャイルド・タームは遺伝学であってもよい。
【０００８】
セルフ・フィーチャーは推奨されたクラスタの名称として使用でき、ペアレント・フィーチャーおよびチャイルド・フィーチャーは、クラスタをより大きいコレクションのスペースに置くために使用できる。ペアレント・フィーチャーはより一般的な概念を示唆し、チャイルド・フィーチャーはセルフ・フィーチャーの特殊化についての記述である概念を示唆する。
【０００９】
ペアレント・フィーチャー、セルフ・フィーチャーおよびチャイルド・フィーチャーを自動的に発見することは、ウェブ・ディレクトリのオートマティック・ラベリングあるいは情報検索の改善を含むいくつかの目的に対して有用である。別の重要な利用法は、単一のクラスタの概要統計とバックグランド・コレクション統計のみを使用して、生成されたクラスタを自動的に命名するとともに、クラスタに含まれるより一般的でより具体的な概念の両方を推奨することである。
【００１０】
現在、ヤフー社が運営するポータルサイト(http://www.yahoo.com/)あるいはオープン・ディレクトリ(http://www.dmoz.org/)のような普及しているウェブ・ディレクトリは、人間が生成し、人間が維持している。カテゴリーが人間により定義される場合でも、自動的な階層的記述は、新しいペアレントあるいはチャイルド・リンク、あるいは別の名称を推奨するために有用なことがある。ドキュメントあるいはページの検索された集合にもとづいて、別の問い合わせ（より一般的で、より具体的な問い合わせ）を推奨することにより、同じ技術が情報検索を改良するために有用なことがある。
【００１１】
自動的な要約に関連する一連の先行する研究がある。たとえば、Radev と Fan は、"Automatic summarization of search engine hit lists" ,in Proceedings of ACL'2000 Workshop on Recent Advances in Nature Language Processing and nformation Retrieval, Hong Kong, P.R. China, 2000,（非特許文献１）でウェブ・ドキュメントのクラスタの要約の技術を説明している。彼等の技術は、ドキュメントを個別の文に構文解析し、テーマ、すなわち、「選択されたドキュメントからの最も顕著な一節」を識別する。この技術は、「重心ベースの要約」を使用し、階層的に関連するフィーチャーの集合を作ったり、あるいはクラスタ内の語あるいは句を発見することはない。
【００１２】
さまざまな概念関係をテキストから推測するために、語彙の技術が応用されてきた。たとえば、Marti A. Hearst in "Automatic acquisition of hyponyms from large text corpora" ,in Proceedings of the Fourteenth International Conference on omputational Linguistics, Nantes, France(1992)（非特許文献２）、Marti A. Hearst in "Automated discovery in wordnet relations", Christiane Fellbaum 編、WordNet: An Electronical Lexical Database, MIT Press (1998)（非特許文献３）、および、 Sharon A. Carballo in "automatic construction of a hypernym-labeled noun ierarchy from text", in Proceedings of the 37th Annual Meeting of the ssociation for Computational Linguistics (1999)（非特許文献４）等参照。
【００１３】
名詞句、たとえば、「打撲傷、外傷、骨折した骨あるいは他の傷害」の点で区切られたリストのような、１組の語彙統語的なパターンを識別することにより、語彙の関係を見出す方法を Hearst は説明している。これらのパターンは、語彙関係の型、たとえば打撲傷、外傷および骨折した骨が傷害のすべての型であることを示唆するために使用される。上位語がラベル付けられ、階層化された名詞を自動的に構築する技術を、Carabalo は説明している。英語を母国語とする人が文章「ＢはＡの一種である」を理解すれば、上位語としては語ＡとＢの間の関係を説明するものとする。HearstとCaraballo により説明されたような言語学関係はシソーラスを生成するために有用であるが、ドキュメントのクラスタとコレクションの残りの部分との関係を必然的には説明していない。スポーツに焦点が当てられたクラスタがあることを知っていれば、「野球がスポーツである」ことを知ることは、有用であることがある。しかし、抽出された関係は、集合の中にある概念の実際の頻度とは必然的には関連していない。主としてバスケットボールとホッケーを論じているスポーツ・ドキュメントのクラスタがあれば、野球もスポーツであるという事実は、その集合を説明するために非常に重要なものではない。
【００１４】
SandersonとCroftは、"Deriving concept hierarchies from text", in Research and Development in Information Retrieval" pages 206-213 (1999)（非特許文献５）において、包含関係にもとづく統計的技術を発表した。
【００１５】
SandersonとCroftのモデルにおいて、２つの用語ｘとｙに対して、所与のｙに対するｘの確率が１であり、所与のｘに対するｙの確率が１未満であれば、ｘはｙを含むと言う。実際のモデルにおいて、使用された確率は、雑音を減少するために０．８であった。包含関係は、ペアレント・チャイルド関係（本発明においてはセルフ・チャイルド関係）を示唆する。これは、所与のクラスタの関係の中で階層が創出されることを可能にする。これに対して、本発明は、「ペアレント」（共通のテーマより一般的）、「セルフ」（クラスタを全体として定義あるいは記述するフィーチャー）および「チルドレン」（共通の下位概念を記述するフィーチャー）として識別されたフィーチャーに特有の一般的な領域に関心を置いている。
【００１６】
PopesculとUngarは、http://citeseer.nj.nec.com/popsecu100automatic.htmlにて未刊行原稿で入手可能な、"Automatic labeling of document clusters"（非特許文献６）において、ドキュメント・クラスタに自動的に符号を付けるためにｘの２乗を使用して、単純な統計的技術を説明している。各（分岐した）フィーチャーは、局部的な頻度と予報性の積にもとづいて、スコアを割り当てられた。良いクラスタ・ラベルの概念は、現在のセルフ・フィーチャー」の概念に類似する。良いセルフ・フィーチャーは、ポジティブ・ットでは一般的であると共にネガティブ・セットで希少なものであり、局部的な高頻度と高い予報性に対応する。彼等の研究に対して、本発明は、良い名称ではないかもしれないがクラスタの理解を促進するフィーチャー（ペアレントおよびチャイルド・フィーチャー）を考慮している。
【００１７】
Eric J. Glover 他は、"Using web structure for classifying and describing web pages" in Proceedings of the 11th WWW Conference, Hawaii (2002)（非特許文献７）で、予想されるエントロピーの低下によるフィーチャーの順位付けが、セルフ名あるいはペアレントまたはチャイルドの概念に対する良い候補を識別するために、どのように使用できるかを説明している。ポジティブ・セット内では一般的であり、ネガティブ・セット内で希少となるフィーチャーは、良いセルフとチルドレンを作り、さらに予想されるエントロピーの低下が多くなることを示す。ペアレントもネガティブ・セット内で相対的に希少であり、ポジティブ・セット内で一般的であり、さらに予想されるエントロピーの低下が多くなる可能性が高い。本発明は、単一のエントロピー・ベースの基準による順位付け
とは対照的に、具体的なポジティブおよびネガティブ頻度を考慮することにより、異なるクラスのフィーチャーを分離することに関心を置いている。
【００１８】
単一のクラスタを分析する他の方法は、クラスタの階層を形成するために、クラスタをクラスタに分けることが挙げられる。http://citeseer.nj.nec.com/fasulo99analysi.htmlにより入手可能なD. Fasuloによる"An Analysis of recent work on clustering algorithms", Technical Report, University of Washington, (1999)（非特許文献８）では、ドキュメントのクラスタリング（および階層的クラスタリング）に対するさまざまな技術の概要を提供している。"Trawling the web for emerging cyber-communities" WWW8/Computer Networks, 31(11-16):1481-1493(1999)（非特許文献９）で、Kumar他は、クラスタを判定するためにウェブのリンク構造を使用して、コミュニティに対してウェブを具体的に分析することを説明している。HofmannとPuzichaは、"Statistical models for co-occurrence data" Technical Report AIM-1625 (1998)（非特許文献１０）で、同時に出現するデータおよび関連する階層的クラスタリング・アルゴリズムに対するいくつかの統計モデルを説明している。HofmannとPuzichaは、特に、情報検索問題と用語の関連に取り組んでいる。
【００１９】
次の例は、本発明と従来の階層的クラスタリング研究の間の相違を明確にするであろう。利用者が「生物学」に対してウェブ検索を行い、すべてが一般的な生物学の「中心」となるページである２０個のドキュメントを検索すると仮定する。各ページは、生物学の特有の面に集中していない点である程度類似である。階層的クラスタリングでは２０個のドキュメントを副クラスタに分け、各副クラスタは「チャイルド」概念を表すであろう。一番上のクラスタは、ほぼ間違いなく「セルフ」クラスタであると考えることができる。しかし、副クラスタを仮定すると、どのフィーチャー（語あるいは句）が意味がある名称であるかを認識する容易な方法はない。例えば、「植物学」は、副クラスタとして「大学」より良い名称であろうか、等。
【００２０】
さらに、１群の類似のドキュメントを仮定すると、クラスタリングは有意義ではない恐れがある。副クラスタは、ドキュメントの２分の１は句「著作権２００２年」を含み、他の２分の１は含まないというような、関連のない面に集中する恐れがある。文字内容に欠けるウェブ・ページ、すなわち「ウェルカム・ページ」に対して、あるいは、ページの一部が混合トピック（クラスタ全体としては主として生物学についてであっても）であれ、これは特に困難である。
【００２１】
本発明による教示によれば、（非記述的ページを処理するウェブ構造を考慮して）２０個のドキュメントの集合が分析され、各フィーチャーの出現を要約するヒストグラムが生成される（個別のドキュメント内の語の頻度は除去される）。本明細書において使用されるフィーチャーは、任意の用語あるいはｎグラム（単一の語あるいは句）を指す。さらにフィーチャーは構造的な情報、ドキュメントの一般的な性質、あるいは他の有意義な記述でも良い。構造的な情報は、ドキュメントの名称内の語あるいは句を含んでもよく、あるいはドキュメントのメタタグ内の語あるいは句および同等物であってもよい。ドキュメントの一般的な性質は、「これは最近のドキュメントである」のような要因、あるいは、「ニュース」あるいは「ホームページ」のようなドキュメント分類を含んでもよい。このようなフィーチャーは、通常２進法である。すべてのドキュメント（あるいは、若干の、より大きい参照コレクション）のヒストグラム内のフィーチャーの分析を使用する、生成されたヒストグラム内のフィーチャーの分析は、クラスタの「最良の」名称は「生物学」であり、「科学」はより一般的な概念を説明する用語であるとの識別をもたらす。同様に、異なる型についてのクラスタを形成するであろう集合内にドキュメントがなくても、生物学のいくつかの異なる「型」が識別されるであろう。例は、「植物学」、「細胞生物学」、「進化論」および同等物である。「著作権２００２年」のような句は、より大きいコレクション内での頻度のために重要ではないことが知られるであろう。さらに、ウェブ構造（以下に説明する拡張アンカーテキスト）の使用は、ドキュメントのフルテキストのみの使用と比較して、ドキュメントの小さい集合を指名する能力を大幅に改良することができ、その結果、非記述的なページ、たとえば、「ウェルカムページ」の問題に注意を集中する。ひとたび創出されたドキュメントのコレクション・セットのヒストグラムは、コレクション・セットが変化しない限り、ドキュメントの任意のポジティブ・セットと連係して使用される。すなわち、各ポジティブ・セットに対してコレクション・セットのヒストグラムを再生することと対照的に、ドキュメントのコレクション・セットのヒストグラムは、ドキュメントの多くの異なるポジティブ・セットに対して再利用することができる。
【００２２】
【非特許文献１】Radev and Fan in "Automatic summarization of search engine hit lists" ,in Proceedings of ACL'2000 Workshop on Recent Advances in Nature Language Processing and Information Retrieval, Hong Kong, P.R. China, 2000.
【非特許文献２】Marti A. Hearst in "Automatic acquisition of hyponyms from large text corpora" ,in Proceedings of the Fourteenth International Conference on Computational Linguistics, Nantes, France(1992).
【非特許文献３】Marti A. Hearst in "Automated discovery in wordnet relations", Christiane Fellbaum 編、WordNet: An Electronical Lexical Database MIT Press (1998).
【非特許文献４】Sharon A. Carballo in "automatic construction of a hypernym-labeled noun hierarchy from text", in Proceedings of the 37th Annual Meeting of the Association for Computational Linguistics (1999).
【非特許文献５】Sanderson and Croft in "Deriving concept hierarchies from text", in Research and Development in Information Retrieval" pages 206-213 (1999).
【非特許文献６】Popescul and Ungar in "Automatic labeling of document clusters"［平成１４年７月３１日検索］、インターネット＜URL：http://citeseer.nj.nec.com/popsecu100automatic.html＞
【非特許文献７】Eric J. Glover et al, "Using web structure for classifying and describing web pages" in Proceedings of the 11th WWW Conference, Hawaii (2002)
【非特許文献８】D. Fasulo in "An Analysis of recent work on clustering algorithms", Technical Report, University of Washington, (1999)［平成１４年７月３１日検索］、インターネット＜URL：http://citeseer.nj.nec.com/fasulo99analysi.html＞
【非特許文献９】Kumar et al "Trawling the web for emerging cyber-communities" WWW8/Computer Networks, 31(11-16):1481-1493(1999).
【非特許文献１０】Hofmann and Puzicha in "Statistical models for co-occurrence data" Technical Report AIM-1625 (1998).
【発明の開示】
【発明が解決しようとする課題】
【００２３】
本発明は、上述したような従来技術を踏まえてなされたものであり、相対的にドキュメントの小さいクラスタに対して、ペアレント、チャイルドおよびセルフ・フィーチャーを予測するための統計モデルを得る方法を提供するものである。
【００２４】
本発明によれば、トピックに関連するサンプル・ウェブ・ページの小さい集合のみを使用して、階層的情報の事前の知識無しに、トピックについての階層的な用語関係を推測する統計モデルが創られる。
【００２５】
本発明を形成する統計モデルは、クラスタ内のページのフルテキストあるいはページへ向かうリンクの前後関係のいずれかを利用することができる。
【００２６】
したがって、本発明の主な目的は、ウェブ・ディレクトリに有用であり、あるいは、情報検索を改良するための、自動的に生成されたさまざまなクラスタを関連づけて符号を付ける方法を提供することである。
【００２７】
本発明の他の目的は、ウェブ・ページの小さい集合あるいはトピックに関連するドキュメントの集合から、事前に何らの階層的情報の知識無しに、トピックについての階層的な用語関係を推測するための統計モデルを創るための方法を提供することである。
【００２８】
本発明の他の目的は、１組のドキュメント内のペアレント・フィーチャー、セルフ・フィーチャーおよびチャイルド・フィーチャーを識別する方法を提供することである。
【００２９】
本発明のさらに他の目的は、情報検索システムにおいて、より広いおよび／またはより狭い検索用語を推薦するために、１組のドキュメント内のペアレント・フィーチャー、セルフ・フィーチャーおよびチャイルド・フィーチャーを識別する方法を提供することである。
【００３０】
本発明のさらに他の目的は、ウェブ・ディレクトリに自動的に符号を付けるために、１組のドキュメント内のペアレント・フィーチャー、セルフ・フィーチャーおよびチャイルド・フィーチャーを識別する方法を提供することである。
【００３１】
本発明のさらに別の目的は、添付図面と関連する下記の説明により明白になるであろう。
【課題を解決するための手段】
【００３２】
ペアレント・フィーチャー、セルフ・フィーチャーおよびチャイルド・フィーチャーの自動的な選択は、ウェブ・ディレクトリの自動的なラベリングあるいは情報検索の改善を含むいくつかの目的に対して有用であり得る。別の重要な利用法は、クラスタの概要統計と背景となるコレクションの統計のみを使用して、生成されたクラスタを自動的に命名するとともに、より一般的でより具体的な概念を推奨することであろう。
【００３３】
時折ネガティブ・セットと呼ばれるドキュメントの全部のコレクション内のフィーャーｆの頻度と比較した、１組のドキュメント（「ポジティブ・クラスタ」）内のフィーャーｆの頻度の分析にもとづいて、ペアレント・フィーチャー、セルフ・フィーチャーおよびチャイルド・フィーチャーを区別することが可能である。具体的にいうと、ｆがポジティブ・クラスタ内では非常に普通であるが、コレクション内では相対的に希少であれば、ｆは良いセルフ・フィーチャーであることがある。ポジティブ・クラスタ内では普通であるが全体のコレクション内でもある程度普通であるフィーチャーは、ポジティブ・クラスタの記述であるが、より一般的であり、したがって良いペアレント・フィーチャーであることがある。ポジティブ・クラスタ内ではある程度普通であるが、一般的なコレクション内では非常に希少なフィーチャーは、正のドキュメントの部分集合のみを説明するから、良いチャイルド・フィーチャーであることがある。
【００３４】
本明細書において使用される用語「ドキュメント」は、ドキュメントと同様の表現、すなわち、ドキュメントのプロキシ、たとえば要約、概要、アンカーテキスト、および同等物を含むと理解されるが、それに制限されない。ポジティブ・セットあるいはコレクション・セットのいずれかを形成するドキュメントは、ウェブ・ブックマークを使用して、本発明による教示にしたがって説明されたもの以外を含むクラスタリング方法の結果を使用し、ドキュメントの先存する階層あるいはドキュメントを得る他の任意の方法を使用し、ワールド・ワイド・ウェブあるいは任意の情報検索システムに問い合わせを出すことにより得ることが可能である。ドキュメントのポジティブ・セットあるいはドキュメントのコレクション・セットは、たとえば既存の階層からのランダムなＵＲＬをコレクショ・セットとして使用するによる、ドキュメントのより大きい集合のサンプリングであってもよい。
【発明を実施するための最良の形態】
【００３５】
次に、本発明の実施例について図面を参照して説明する。
【００３６】
ここで、図、特に、図１を参照すると、ペアレント・フィーチャー、チャイルド・ィーチャーおよびセルフ・フィーチャーの間の予測される関係のグラフ図が示されている。正の頻度」は、所与のフィーチャーを含むポジティブ・セット内のドキュメントのパーセンテージあるいは割合を示す。「コレクション頻度」は、所与のフィーチャーを含むコレクション内のドキュメントの総合的なパーセンテージあるいは割合を示す。
【００３７】
長方形の箱により示されている３つの領域は、ペアレント・フィーチャー１０、チャイルド・フィーチャー１２およびセルフ・フィーチャー１４の間に予測される相対的な関係である。長方形の箱の外のフィーチャーは、ペアレント、チャイルドおよびセルフのクラスに対しては好ましくない候補であると考えられ、このようなフィーチャーは分類されない。図１は、絶対的な数値的境界を示すものではなく、単に領域の相対的な位置のみを示す。領域は、クラスの特有の一般性に依存する。たとえば、「生物学」のクラスタに対しては「科学」のペアレントは比較的普通であるが、「遺伝子配列決定」に関するドキュメントのクラスタに対しては「ＤＮＡ」のペアレントはもっと希少であるかもしれない、したがって、ペアレントとセルフの間の境界線はより０に近いであろう。
【００３８】
図２は、生物学のセルフ・エリア、科学のペアレント・エリアおよび植物学のチャイルド・エリアに対するフィーチャーの分布の見本を示す。外の円２０は、一般に「科学」の主題エリア内の集合内でのすべてのドキュメントの集合を表す。中央の円２２は「生物学」のエリア内のドキュメントの集合であり、最も内部の円２４は「植物学」のエリア内のドキュメントを表す。フィーチャー「科学」、「植物学」および「生物学」が、それぞれの対応する円の中でのみ出現し、それぞれの対応する円の中に含まれる各ドキュメント内に出現すると仮定すれば、ペアレント、チャイルド、セルフ関係は明確である。図２から、全体のドキュメントのおよそ２０％が「科学」に言及し、ドキュメントの約５％が生物学」に言及し、１％が「植物学」に言及している。「生物学」ドキュメントの集合の中
で、１００％が「科学」と「生物学」の両方に言及しているが、「植物学」には約２０％が言及している。生物学の円内のすべてのドキュメントが生物学と言う語を実際に含んでいると想定しているので、これは非常に単純化した表現であるが、必ずしもこうはならない。同様に、植物学の副カテゴリー内のすべてのドキュメントが、「生物学」と「科学」の両方に言及することはありそうもない。
【００３９】
最終的な結果を補償するために、所与の「適切な」フィーチャーが使用される何らかの確率があると想定する。この確率は、セルフあるいはチャイルドに対するよりも、ペアレントに対しては通常低い。結果として、図１において、ペアレント領域はセルフ領域よりも左方に延びている。使用されている所与のフィーチャーの確率は、右下のコーナーの座標にも影響を与えるであろう、低い確率はセルフ内の出現のパーセンテージを左方にシフトする。確率１は、すべてのセルフ・フィーチャーを含むポジティブ・セット内のすべての正のドキュメントに対応する。
【００４０】
図１に説明したモデルを試験するために、グラウンド・トルース・データと既知の正のドキュメントを使用し、ペアレント・フィーチャー、セルフ・フィーチャーおよびチャイルド・フィーチャーの実際の出現のグラフが生成された。階層的記述が推測されるべきコレクション・セットおよびドキュメントの集合を形成するために、オープン・ディレクトリ (http://www.dmoz.org/) が選択された。
ドキュメントの集合Ｓiを形成するために、「コンピュータ」、「科学」および「スポーツ」のトップレベルのカテゴリーを使用して、各カテゴリーからの上位１５の主題ベースのサブカテゴリーが選択され、（科学には１１の主題ベースのサブカテゴリーが存在し）合計４１のオープン・ディレクトリ・カテゴリーが得られた、ここでｉは階層的記述が推測されるべき異なるカテゴリーに対応する。表１は、実験に使用された４１のオープン・ディレクトリ・カテゴリーと、それらの３つのペアレント・カテゴリーを列挙している。フィーチャーのコレクション頻度の近似を収集するために、ドキュメントはオープン・ディレクトリ内の任意の場所からランダムに選ばれ、これらのドキュメントは集合Ｃを構成する。同じ集合Ｃが、実験のすべてに使用された。
【００４１】
【表１】
2006318511.tif 000003
各カテゴリーは、割り当てられたペアレント（この場合、科学、コンピュータあるいはスポーツのいずれか）、セルフ・フィーチャーを形成する関連する名称、およびチャイルドを形成するいくつかのサブカテゴリーを有する。各々の場合に、本発明者等は、割り当てられた名称を「および」、「あるいは」またはコンマのような句読点で分割した。したがって、カテゴリー「異常と代替科学」は２つのセルフ「異常」および「代替科学」となる。
【００４２】
実験の第１の部分は、集合Ｃ（コレクション統計）として、Ｓi集合を形成するために各カテゴリーから５００の任意のドキュメントの初期集合と、ディレクトリ内の任意の場所からの２０,０００のランダムなドキュメントを考慮した。ウェブのＵＲＬのそれぞれがダウンロードされ、フィーチャーがヒストグラムに入れられた。ＵＲＬがターミナル・エラーに終われば、ページは無視され、トレーニングのために使用された集合Ｓi内のドキュメントの数の変化として説明された。フィーチャーは、語あるいは２つあるいは３つの語句から成り、各フィーチャーはドキュメントごとに最大１と数える。
【００４３】
次に、各カテゴリーに対して、各ペアレント、チャイルドおよびセルフ・フィーチャー（オープン・ディレクトリにより割当られるように）が、フィーチャーを含む集合Ｓi内のドキュメントの割合としてＸ座標を使用し、そのフィーチャーを含む集合Ｃ内のドキュメント（ランダム・ドキュメント）の割合としてＹ座標を使用してグラフ化された。集合Ｓiの２％未満のフィーチャーが出現すれば、そのフィーチャーは無視された。
【００４４】
図３は、４１のカテゴリーのすべてのペアレント、チャイルドおよびセルフ・フィーチャーの分布を示す。一般的な傾向であるように見えるが、ペアレントの近くに出現するチャイルドが多く存在する。同じペアレント（独自のペアレントは３つのみ）を有する多くのカテゴリーが存在し、共通の集合Ｃが使用されたので、ペアレントは共通のＹ軸値の同一直線上にある。
【００４５】
チルドレンのいくつかは、カテゴリーの知識がない場合に明確に定義されていない語あるいは句である。たとえば、フィーチャー「ニュース」は、関連するカテゴリーを知らない限り、人工知能についてのニュー＃スか、あるいは野球についてのニュースか不確定である。同様に、ニュースを含むいくつかのフィーチャーは、「主題」ではなく、むしろページの非テキスト属性である。カテゴリーとそれらのチルドレンのリストは、手作業で検査され、孤立して十分に定義されなかったチャイルドは除去された。チルドレンの半分以上がこの方法で除去された。データを参照するより前に、「不十分に定義された」語あるいは句が何故除去されるかの正確な知識なしに、除去は行われた。
【００４６】
データの分析は、「コンピュータ」（computers） のペアレントが コンピュータ（computer） により置換されるべきであることを示唆した。普通の意味で使用される場合に語 スポーツ（sports） が多くの場合には複数形であるのと異なり、コンピュータ（computers）は多くの場合に単数形である。ステミング（stemming）あるいはストップ語除去は行われなかったので、コンピュータ（computers）とコンピュータ（computer） は異なるフィーチャーである。図４は、ペアレントが コンピュータ（computers）からコンピュータ（computer）に変わり、不十分に定義されたチルドレンが除去されたこと以外は、図３と同じデータを示す。すなわち、ペアレントの知識なしでは定義されないいくつかのサブカテゴリー、たとえば「ニュース」あるいは「リソース」が除去された。この変更は、ペアレント、セルフおよびチャイルド領域の間により明確な隔離をもたらす。除
去された不十分に定義されたチルドレンは、一般にフィーチャーの第４のクラスを形成する。図１において、フィーチャーのこの第４のクラスは、ペアレント・クラスタの左でチャイルド・クラスタの上に通常位置する。
【００４７】
ドキュメントは、多くの場合それらの「カテゴリー」を記述する語を含んでいない。たとえば「マルチメディア」のカテゴリーにおいて、フィーチャー「マルチメディア」は、正のドキュメントのわずか１３％のみに出現した。これは、ページの作者による用語の選択の組み合わせと、多くの場合にメイン・ウェブ・ページがテキスト・コンテントを有せず「エンターするためには、ここをクリックしてください」画像のみにより表されるためである。
【００４８】
モデルは、「ドキュメント」が実際に記述であると想定する。ページ自身に存在する語を使用するのではなく、図５に示すように、「拡張アンカー・テキスト」と呼ばれるであろうものを使用して、実験は繰り返された。参考文献として本明細書に包含される前掲の Glover他による文献（非特許文献７）に、拡張アンカー・テキストの記述と、拡張アンカー・テキストがドキュメントのフルテキストよりも「概要」を使用してより良く一致するフィーチャーを作り出す方法が説明されている。拡張アンカー・テキストを使用して見出されたフィーチャーは、より合理的な名称を作ると見られるクラスタを生成する。
【００４９】
拡張アンカー・テキストとは、目標ページへのリンクの近くに出現する語、すなわち、インバウンド・リンクにごく近接している語を示す。図５は、拡張アンカー・テキストの例を概略的に示す。フルテキストを使用する代わりに、最高１５の拡張アンカー・テキストで構成される仮想ドキュメントが使用された。ヤフー社の提供するポータルサイトあるいはオープン・ディレクトリからのインバウンドリンクは除外された。インバウンド・アンカー・テキストを含めて前後に最高２５の語を考慮することにより創り出された仮想ドキュメントを使用する場合（フルテキストの使用と比較して）、ドキュメントＳiのポジティブ・セット内のセルフ・フィーチャーの使用に著しい増加がある。マルチメディアのカテゴリーにおいて、フィーチャー「マルチメディア」は、フルテキストの１３％とは対
照的に、正の仮想ドキュメントの４２％に出現した。集合Ｃ（全体のコレクション）内のドキュメントの中のフィーチャー「マルチメディア」の出現は、フルテキストおよび仮想ドキュメントの両方に対して、約２％と殆ど同一であった。
【００５０】
図５において、拡張アンカー・テキストは、第１のドキュメント、すなわち、たとえば 「ＡＢＣＤＥ」ページ５０から、あるいは、第２のドキュメント、すなわち、たとえば「ＦＧＨＩＪ」ページ５０から決定される。他のドキュメント５２、５２’からページ５０へのインバウンド・リンク５１、５１’は、当業者に公知の多数の方法によって見出される。アンカー・テキスト５３、５３’は、ソース・ページ５０および５０’を示す他のページからのハイパーリンクである。一般的には、大部分の従来のドキュメントにおけるアンカー・テキストは、青いフォントで強調され、ドキュメント内で下線を引かれている。ページ５０を示しているページに対する拡張アンカー・テキストは、ハイパーリンクおよびハイパーリンクの前後のいくつかの語を含む拡張アンカー・テキスト５４、４’である。ドキュメント５２の場合、拡張アンカー・テキスト５４は、『私の好きな検索エンジンは「ＡＢＣＤＥ」である』である。ドキュメント５２’では、ドキュメント５０に対する拡張アンカー・テキスト５４’は、『検索エンジン「ＡＢＣＤＥ」は、「ＦＧＨＩＪ」によって駆動されている』である。
【００５１】
前者の場合には、拡張アンカー・テキストは、図５中に示されるように英語で表現した場合、テキストの最後の語「ＡＢＣＤＥ」で終わっている。後者の場合には、語「ＡＢＣＤＥ」は、拡張アンカー・テキストの中に出現する。
【００５２】
インバウンド・リンクを取り囲んでいるテキストを含めることは、そのページがリンクされている前後関係と意味を提供する。
【００５３】
すべてが「正」として識別される（すなわち、１つのトピックについて単一のクラスタ）１組のページから始まり、次いで１度に１つずつ、ポジティブ・セットの各ページが検査され、ポジティブ・セットのそのページにリンクするページが識別される。上の例では、「ＡＢＣＤＥ」は正のページであり、「ＡＢＣＤＥ」へのリンクに「近い」語を調査することにより、「ＡＢＣＤＥ」にリンクする第１のページが、ページ「ＡＢＣＤＥ」のトピックが関連するものの若干の表示を提供する。リンクは、必然的に「ＡＢＣＤＥ」のような検索エンジンからではなく、任意のページからであってよい。同じ手順が、コレクション・セットの各ページに対して繰り返される。
【００５４】
同じソース・ドキュメントに対して見出された拡張アンカー・テキストのすべては、仮想ドキュメント（図示せず）を形成するために一個所に配置される。
【００５５】
表２は、フルテキスト（Ｆ列）実験に対して、ならびに拡張アンカー・テキスト（Ｖ列）実験に対して、（第１の実験に使用された５００からランダムに選ばれた）各カテゴリーに使用された仮想ドキュメントの数を列挙している。合計７４３の仮想ドキュメントが、ドキュメント集合ｃとして使用された。仮想ドキュメントの生成は非常に費用がかかり、考慮されるページの総数の削減を余儀なくされる。仮想ドキュメントからの改良された要約能力は、より少数のドキュメントを使用して、処理が作動することを可能にするべきである。
【００５６】
【表２】
2006318511.tif 000004
【００５７】
【表３】
2006318511.tif 000005
【００５８】
【表４】
2006318511.tif 000006
図６は、拡張アンカー・テキストに対して、すべてのペアレント、チルドレンおよびセルフ・フィーチャーに対する結果を示す。ポジティブ・セットＳi内のドキュメントのパーセンテージは、セルフがチルドレンからより明らか分かれるにつれて、一般に右にシフトしている。図７は、不十分に定義されたチルドレンを除去し、"computers" を "computer"で置換した後の結果を示す。極めて少数のデータ点のみが、各クラスの周囲に定められた単純な長方形の領域の外に脱落している。
【００５９】
大部分のペアレント、チルドレンおよびセルフは示された領域に含まれるが、フィーチャーのステミングを行うことにより、結果を改善することが可能である。たとえば、フィーチャーによっては単数形と複数形の両方で出現することがあり、１方の形は偽のチャイルドとして出現する。さらに、句はそれらの個別の語よりも出現頻度が低い恐れがあり、「人工知能」のような場合に、セルフを誤ってチルドレンとして出現させる。この場合、句の出現頻度が比較的低いために、句「人工知能」はチャイルドとして出現する。
【００６０】
図７は、４１のカテゴリーに対するオープン・ディレクトリからのグラウンド・トルース・フィーチャーのグラフが、一般に図１の予測されたモデルに従うことを示すが、このモデルは各カテゴリーに出現するすべてのフィーチャーをグラフに表さず、オープン・ディレクトリにより割当られたフィーチャーのみがグラフに表されている。すべてのフィーチャーを可能性のあるペアレント、チルドレンおよびセルフとして順位付け、その出力をオープン・ディレクトリからのグラウンド・トルース・データと比較するアルゴリズムを使用することにより、モデルの妥当性は強化される。
【００６１】
問い合わせの結果、クラスタリング・オペレーションから結果として生ずるドキュメント、ブックマークを付されたドキュメントのリスト、あるいは、手作業で選択されたドキュメントであってもよい１群のドキュメント、を使用する。ドキュメントがウェブ・ページあるいは他のハイパーリンクされたドキュメント・コレクションを有するならば、上述のように各ページに対して仮想ドキュメントが創出されることが望ましい。ハイパーリンクされていないドキュメントがあれば、ドキュメントのフルテキスト・バージョンを使用することができる。次に、以下のアルゴリズムが適用される。順位は、結果について実行される。多くの順位付けが可能であるが、望ましい順位付けは、フィーチャーを含むドキュメントの最も高いパーセンテージにもとづいた順位に依存する。表３は、各カテゴリー内の上位２番にランクされたセルフ・フィーチャーを示し、ここで、順位はフィーチャーを含むポジティブ・セット内のドキュメントのパーセンテージにもとづいている。
【００６２】
ペアレント・チルドレンおよびセルフ予測アルゴリズム
１組の所望のフィーチャーからの各フィーチャーｆに対して、
１．フィーチャーｆに次のようにラベルを割り当てる。
if (f.C > maxParentC)[Label = 'N' ]
elseif (f.C>maxSelfC)[Label='P' ]
elseif (f.Si>minSelfSi)[Label='S' ]
elseif ((f.Si<maxChildSi) and (f.C<maxChildC))[Label='C')
else [Label='N')
２．各ラベル（Ｐ、Ｓ、Ｃ）に対して、そのラベルを使用して f.Si により各フィーチャーｆを分類する。
【００６３】
図７からのデータを使用して、次のカットオフを指定する。
maxParentC = 0.08
maxSelfC = 0.06
minSelfSi= 0.4
maxChildSi = 0.4
maxChildC = 0.02
Ｓiは階層的記述が推測されるべきドキュメントの集合であり、Ｃはドキュメントのコレクション・セットであり、ｆ．Ｃはフィーチャーｆを含むドキュメントＣのコレクション・セット内のドキュメントの割合であり、ｆ．Ｓｉはフィーチャーｆを含むポジティブ・ドキュメントＳｉの集合内のドキュメントの割合である。
【００６４】
上記の望ましいアルゴリズムは、セルフ、ペアレントおよびチャイルド領域が長方形であり、図１に示すように接続されている場合に、最も有用である。領域が、切断されている、および／または部分的に重なり合っている、および／または非長方形であることが望ましければ、アルゴリズムは当業者により適宜修正することができる。
【００６５】
表３は、ペアレント・チルドレンおよびセルフ予測アルゴリズムを使用して、試験された４１のカテゴリーのそれぞれに対する上位のペアレント・フィーチャー、上位のセルフ・フィーチャーおよび上位のチルドレン・フィーチャーを示す。空白のエントリは、そのカテゴリーに対して指定された領域に、語あるいはフィーチャーがないことを意味する。結果は、すべての４１のカテゴリーにおいて（"computers" を "computer"で置換）、オープン・ディレクトリが割当したペアレントが上位５に順位付けられたことを示している。カテゴリーの約８０％において、上位にランクされたセルフは、オープン・ディレクトリが割当したセルフと同一であるか、あるいは、実際上同一（同義語、あるいは同一の語幹）である。リストされない多くの合理的なチルドレンが存在するので、チルドレンを評価することはより困難である。
【００６６】
【表５】
2006318511.tif 000007
【００６７】
【表６】
2006318511.tif 000008
【００６８】
【表７】
2006318511.tif 000009
【００６９】
【表８】
2006318511.tif 000010
【００７０】
【表９】
2006318511.tif 000011
【００７１】
【表１０】
2006318511.tif 000012
【００７２】
【表１１】
2006318511.tif 000013
【００７３】
【表１２】
2006318511.tif 000014
アルゴリズムの改良は可能である。第１に、「インターネット」のような、いくつかのカテゴリーにおいて、カットオフ点は変化する。アルゴリズムは、所与のカテゴリーに対するデータに動的に順応しない。さらに、アルゴリズムは境界点を知ることを必要とする。第２に、時には句は単一の語より正の出現頻度が低い。たとえば、句「Artificial Intelligence(人工知能)」は、セルフの代わりに誤ってチャイルドとして出現する。第３に、ステミングあるいはインテリジェントなフィーチャー除去がない。たとえば、「university of(大学)」のようなフィーチャーは、ストップ語で終了するので、無視されるべきである。同様に、"consult" とは対照的に "consulting" 、あるいは computer" とは対照的に "computers" は、すべて語幹の失敗が誤りを起こす例である。別の改良は、効率的でないフィーチャーを自動的に除去する閾値を適用することである。上述のように、非長方形の領域が所望であれば、あるいは領域が部分的に重なり合ってい
れば、あるいは領域が接続されていなければ、アルゴリズムを変えることが可能である。
【００７４】
説明した発明は、英文に限定されるものではない。日本語を含む、ほとんどの言語が使用できる。次のリストは、日本の大学のカテゴリーから日本語のウェブ・ページからのフルテキストを使用して、ペアレント・チルドレンおよびセルフ予測アルゴリズムを適用した結果を示す。抽出されたフィーチャーは、日本語の単語であり、英語の翻訳ではない。
【００７５】
次のデータは、４３２の「ランダムな」ウェブ・ページ（日本語の）および、３６７の日本の大学のページ（同じく日本語の）を使用して収集された。
【００７６】
上位にランクされたペアレント：年度−year、学校−school、学−study  上位にランクされたセルフ： 大学−university、入試−admission examination
上位にランクされたチルドレン： 学生−student、学科−subject、入学−entrance、科−course、図書館−library、キャンパス−campus、学部−department、学内−inside the university、施設−facility、大学院−graduate school
ペアレント・チルドレンおよびセルフ予測アルゴリズムを適用するために使用されたカットオフ値は近似的に次の通りであった。
maxParentC : = 0.05;
maxSelfC = 0.04;
minSelfSi = maxChildSi = 0.35;
maxChildC = 0.03.
さらに本発明はテキスト・ドキュメントのみに限定されるものではない。本発明は、識別することが可能なフィーチャーが存在するマルチメディア・データ、オーディオデータ、画像データ、ビデオデータおよび同等物を含むが、それらのみに限定されない非テキスト・データに適用することができる。ＵＲＬ、リンク、あるいは、引用、参照、クローズド・キャプショニングまたは同等物のようなテキストの他のソースが非テキスト・データに利用できれば、拡張アンカー・テキスト方法が使用できる。ＵＲＬあるいはリンクが利用できなければ、非テキスト・データを記述するための一般的なフィーチャーが使用できる。ソースがターゲットたとえば引用参照についての情報を有するドキュメントの間のインターリンキング・システムは、ＵＲＬの代わりに使用できる。
【００７７】
これらの方法を使用することにより、サーチャーはドキュメントのクラスタに容易に名称をつけ、関連づけることができる。前の問い合わせよりも、より一般的で、より具体的な別の問い合わせを自動的に推薦されることにより、サーチャーは利益を得ることが可能である。問い合わせに対する１組の結果は、予測される階層にもとづいて拡大することができる。たとえば、利用者は単語「生物学」を検索し、単語「科学」は単語「生物学」より一般的であり、単語「植物学」は単語「生物学」より特有であるとの推薦を受ける。同様に、たとえば、複数のホームページに関連するいくつかのページを選択する利用者は、これらのページは「インターネット・サービス・プロバイダー」と命名されるべきであることを理解することができる。
【００７８】
要約すれば、比較的小さいドキュメントのクラスタに対するペアレント、チャイルドおよびセルフ・フィーチャーの予測に対して、統計モデルを創る方法を説明し、例示した。セルフ・フィーチャーはクラスタの推薦された名称として有用であり、ペアレントおよびチルドレン・フィーチャーはより大きいコレクションのスペースにクラスタを「配置する」ために使用することができる。ペアレント・フィーチャーはより一般的な概念を示唆し、一方チルドレン・フィーチャーはセルフ・フィーチャーの専門分野を説明する概念を示唆する。グラウンド・トルース・データのグラフ化の実験的なテストは、実際のペアレント、チャイルドおよびセルフ・フィーチャーが一般にモデルに従うことを確認した。フィーチャー・ヒストグラムからペアレント、チャイルドおよびセルフ・フィーチャーを予測することができるアルゴリズムを開示した。予測されたフィーチャーは、多くの場合にグラウンド・トルースと一致し、関連するカテゴリーの間の新しい相互接続を示唆した。
【００７９】
階層的情報の事前の知識なしに１組のドキュメントから階層的記述を推測する望ましい方法を説明し例示したが、本明細書に付された特許請求の範囲によりのみ制限されるべきである本発明の技術思想と広い範囲を逸脱せずに、修正および変形がさらに可能であることは、当業者に明白であろう。
【００８０】
以上、本発明の実施例について詳述したが、以下に本発明の実施態様を示す。
【００８１】
［実施態様１］  ドキュメントのポジティブ・セットからフィーチャーの第１のヒストグラムを供給するステップと、
ドキュメントのコレクション・セットからフィーチャーの第２のヒストグラムを供給するステップと、
前記フィーチャーを含む前記ポジティブ・セット内の前記ドキュメントの割合と、前記フィーチャーを含む前記コレクション・セット内の前記ドキュメントの割合にもとづいて、各フィーチャーがセルフ・フィーチャー、ペアレント・フィーチャーあるいはチャイルド・フィーチャーであるか否かを決定するステップを有する１組のドキュメントの階層的記述を推測する方法。
【００８２】
［実施態様２］  ヒストグラム閾値を設定し、前記第１のヒストグラムおよび前記第２のヒストグラムの両方の中の前記閾値以下のフィーチャーを除去するステップをさらに有する実施態様１記載の１組のドキュメントの階層的記述を推測する方法。
【００８３】
［実施態様３］  ドキュメントの前記ポジティブ・セット内の出現の順序により前記フィーチャーを順位付けることをさらに有する実施態様１記載の１組のドキュメントの階層的記述を推測する方法。
【００８４】
［実施態様４］  ドキュメントは画像データを有する実施態様１記載の１組のドキュメントの階層的記述を推測する方法。
【００８５】
［実施態様５］  ドキュメントはテキストデータを有する実施態様１記載の１組のドキュメントの階層的記述を推測する方法。
【００８６】
［実施態様６］  前記テキストデータは英語以外の言語である実施態様５記載の１組のドキュメントの階層的記述を推測する方法。
【００８７】
［実施態様７］  ドキュメントはオーディオデータを有する実施態様１記載の１組のドキュメントの階層的記述を推測する方法。
【００８８】
［実施態様８］  ドキュメントはマルチメディア・データを有する実施態様１記載の１組のドキュメントの階層的記述を推測する方法。
【００８９】
［実施態様９］  前記決定するステップは、ペアレント、チルドレンおよびセルフ予測アルゴリズムを使用して実行される実施態様１記載の１組のドキュメントの階層的記述を推測する方法。
【００９０】
［実施態様１０］  ヒストグラム閾値を設定し、前記第１のヒストグラムおよび前記第２のヒストグラムの両方の中の前記閾値以下のフィーチャーを除去するステップをさらに有する実施態様９記載の１組のドキュメントの階層的記述を推測する方法。
【００９１】
［実施態様１１］  ドキュメントの前記ポジティブ・セット内の出現の順序により前記フィーチャーを順位付けることをさらに有する実施態様９記載の１組のドキュメントの階層的記述を推測する方法。
【００９２】
［実施態様１２］  ドキュメントは画像データを有する実施態様９記載の１組のドキュメントの階層的記述を推測する方法。
【００９３】
［実施態様１３］  ドキュメントはテキストデータを有する実施態様９記載の１組のドキュメントの階層的記述を推測する方法。
【００９４】
［実施態様１４］  前記テキストデータは英語以外の言語である実施態様１３記載の１組のドキュメントの階層的記述を推測する方法。
【００９５】
［実施態様１５］  ドキュメントはオーディオデータを有する実施態様９記載の１組のドキュメントの階層的記述を推測する方法。
【００９６】
［実施態様１６］  ドキュメントはマルチメディア・データを有する実施態様９記載の１組のドキュメントの階層的記述を推測する方法。
【００９７】
［実施態様１７］  ドキュメントのポジティブ・セットを有するＵＲＬの第１の集合を得るステップと、
ドキュメントのコレクション・セットを有するＵＲＬの第２の集合を得るステップと、
ＵＲＬの前記第１の集合内の各ＵＲＬと、ＵＲＬの前記第２の集合内の各ＵＲＬに対するインバウンド・リンクを決定するステップと、
ドキュメントの前記ポジティブ・セット内の各ＵＲＬに対する仮想ドキュメントと、ドキュメントの前記コレクション・セット内の各ＵＲＬに対する仮想ドキュメントを創るステップと、
ＵＲＬの前記第１の集合と組み合わされた前記仮想ドキュメントからフィーチャーの第１のヒストグラムを供給するステップと、
ＵＲＬの前記第２の集合と組み合わされた前記仮想ドキュメントからフィーチャーの第２のヒストグラムを供給するステップと、
前記フィーチャーを含むドキュメントの前記ポジティブ・セットと組み合わされた前記仮想ドキュメントの割合と、前記フィーチャーを含むドキュメントの前記コレクション・セットと組み合わされた前記仮想ドキュメントの割合にもとづいて、各フィーチャーがセルフ・フィーチャー、ペアレント・フィーチャーあるいはチャイルド・フィーチャーであるか否かを決定するステップを有するウェブ・ページを有する１組のドキュメントの階層的記述を推測する方法。
【００９８】
［実施態様１８］  ヒストグラム閾値を設定し、前記第１のヒストグラムおよび前記第２のヒストグラムの両方の中の前記閾値以下のフィーチャーを除去するステップをさらに有する実施態様１７記載の１組のドキュメントの階層的記述を推測する方法。
【００９９】
［実施態様１９］  ドキュメントの前記ポジティブ・セット内の出現の順序により前記フィーチャーを順位付けることをさらに有する実施態様１７記載の１組のドキュメントの階層的記述を推測する方法。
【０１００】
［実施態様２０］  ＵＲＬは画像データを含むページを示す実施態様１７記載の１組のドキュメントの階層的記述を推測する方法。
【０１０１】
［実施態様２１］  ＵＲＬはテキストデータを含むページを示す実施態様１７記載の１組のドキュメントの階層的記述を推測する方法。
【０１０２】
［実施態様２２］  前記テキストデータは英語以外の言語である実施態様２１記載の１組のドキュメントの階層的記述を推測する方法。
【０１０３】
［実施態様２３］  ＵＲＬはオーディオデータを含むページを示す実施態様１７記載の１組のドキュメントの階層的記述を推測する方法。
【０１０４】
［実施態様２４］  ＵＲＬはマルチメディア・データを含むページを示す実施態様１７記載の１組のドキュメントの階層的記述を推測する方法。
【０１０５】
［実施態様２５］  各フィーチャーがセルフ・フィーチャー、ペアレント・フィーチャーあるいはチャイルド・フィーチャーであるか否かを決定する前記ステップは、ペアレント、チルドレンおよびセルフ予測アルゴリズムを使用して実行される実施態様１７記載のウェブ・ページを有する１組のドキュメントの階層的記述を推測する方法。
【０１０６】
［実施態様２６］  ヒストグラム閾値を設定し、前記第１のヒストグラムおよび前記第２のヒストグラムの両方の中の前記閾値以下のフィーチャーを除去するステップをさらに有する実施態様２５記載の１組のドキュメントの階層的記述を推測する方法。
【０１０７】
［実施態様２７］  ドキュメントの前記ポジティブ・セット内の出現の順序により前記フィーチャーを順位付けることをさらに有する実施態様２５記載の１組のドキュメントの階層的記述を推測する方法。
【０１０８】
［実施態様２８］  ＵＲＬは画像データを含むページを示す実施態様２５記載の１組のドキュメントの階層的記述を推測する方法。
【０１０９】
［実施態様２９］  ＵＲＬはテキストデータを含むページを示す実施態様２５記載の１組のドキュメントの階層的記述を推測する方法。
【０１１０】
［実施態様３０］  前記テキストデータは英語以外の言語である実施態様２９記載の１組のドキュメントの階層的記述を推測する方法。
【０１１１】
［実施態様３１］  ＵＲＬはオーディオデータを含むページを示す実施態様２５記載の１組のドキュメントの階層的記述を推測する方法。
【０１１２】
［実施態様３２］  ＵＲＬはマルチメディア・データを含むページを示す実施態様２５記載の１組のドキュメントの階層的記述を推測する方法。
【０１１３】
［実施態様３３］  情報検索システムに検索問い合わせを提出するステップと、
前記検索問い合わせに応答する前記情報検索システムからのドキュメントの第１の集合を検索するステップと、
ドキュメントの第２の集合を供給するステップと、
前記第１の集合のドキュメント内の各検索されたドキュメントに対して、ならびにドキュメントの前記第２の集合内の各ドキュメントに対して、インバウンド・リンクを決定するステップと、
ドキュメントの前記第１の集合内の各ドキュメントに対して、ならびにドキュメントの前記第２の集合内の各ドキュメントに対して、仮想ドキュメントを創出するステップと、
ドキュメントの前記第１の集合と組み合わされた前記仮想ドキュメント内にフィーチャーの第１のヒストグラムを創出するステップと、
ドキュメントの前記第２の集合と組み合わされた前記仮想ドキュメント内にフィーチャーの第２のヒストグラムを創出するステップと、
前記フィーチャーを含むドキュメントの前記ポジティブ・セットと組み合わされた前記仮想ドキュメントの割合と、前記フィーチャーを含むドキュメントの前記コレクション・セットと組み合わされた前記仮想ドキュメントの割合にもとづいて、各フィーチャーがセルフ・フィーチャー、ペアレント・フィーチャーあるいはチャイルド・フィーチャーであるか否かを決定するステップと、
フィーチャーの分類に応答する前記検索問い合わせを変えるステップを有する１組のドキュメントの推測にもとづく階層的記述を使用する情報検索システムの検索方法。
【０１１４】
［実施態様３４］  ヒストグラム閾値を設定し、前記第１のヒストグラムおよび前記第２のヒストグラムの両方の中の前記閾値以下のフィーチャーを除去するステップをさらに有する実施態様３３記載の１組のドキュメントの推測にもとづく階層的記述を使用する情報検索システムの検索方法。
【０１１５】
［実施態様３５］  ドキュメントの前記第１の集合内の出現の順序により前記フィーチャーを順位付けることをさらに有する実施態様３３記載の１組のドキュメントの推測にもとづく階層的記述を使用する情報検索システムの検索方法。
【０１１６】
［実施態様３６］  検索範囲を広げるために、検索の問い合わせがペアレント・フィーチャーに変えられた実施態様３３記載の１組のドキュメントの推測にもとづく階層的記述を使用する情報検索システムの検索方法。
【０１１７】
［実施態様３７］  検索範囲を狭めるために、検索の問い合わせがチャイルド・フィーチャーに変えられた実施態様３３記載の１組のドキュメントの推測にもとづく階層的記述を使用する情報検索システムの検索方法。
【０１１８】
［実施態様３８］  ドキュメントは画像データを有する実施態様３３記載の１組のドキュメントの推測にもとづく階層的記述を使用する情報検索システムの検索方法。
【０１１９】
［実施態様３９］  ドキュメントはテキストデータを有する実施態様３３記載の１組のドキュメントの推測にもとづく階層的記述を使用する情報検索システムの検索方法。
【０１２０】
［実施態様４０］  前記テキストデータは英語以外の言語である実施態様３９記載の１組のドキュメントの推測にもとづく階層的記述を使用する情報検索システムの検索方法。
【０１２１】
［実施態様４１］  ドキュメントはオーディオデータを有する実施態様３３記載の１組のドキュメントの推測にもとづく階層的記述を使用する情報検索システムの検索方法。
【０１２２】
［実施態様４２］  ドキュメントはマルチメディア・データを有する実施態様３３記載の１組のドキュメントの推測にもとづく階層的記述を使用する情報検索システムの検索方法。
【０１２３】
［実施態様４３］  各フィーチャーがセルフ・フィーチャー、ペアレント・フィーチャーあるいはチャイルド・フィーチャーであるか否かを決定する前記ステップは、ペアレント、チルドレンおよびセルフ予測アルゴリズムを使用して実行される実施態様３３記載の１組のドキュメントの推測にもとづく階層的記述を使用する情報検索システムの検索方法。
【０１２４】
［実施態様４４］  ヒストグラム閾値を設定し、前記第１のヒストグラムおよび前記第２のヒストグラムの両方の中の前記閾値以下のフィーチャーを除去するステップをさらに有する実施態様４３記載の１組のドキュメントの推測にもとづく階層的記述を使用する情報検索システムの検索方法。
【０１２５】
［実施態様４５］  ドキュメントの前記第１の集合内の出現の順序により前記フィーチャーを順位付けることをさらに有する実施態様４３記載の１組のドキュメントの推測にもとづく階層的記述を使用する情報検索システムの検索方法。
【０１２６】
［実施態様４６］  検索範囲を広げるために、検索の問い合わせをペアレント・フィーチャーに変えた実施態様４３記載の１組のドキュメントの推測にもとづく階層的記述を使用する情報検索システムの検索方法。
【０１２７】
［実施態様４７］  検索範囲を狭めるために、検索の問い合わせをチャイルド・フィーチャーに変えた実施態様４３記載の１組のドキュメントの推測にもとづく階層的記述を使用する情報検索システムの検索方法。
【０１２８】
［実施態様４８］  ドキュメントは画像データを有する実施態様４３記載の１組のドキュメントの推測にもとづく階層的記述を使用する情報検索システムの検索方法。
【０１２９】
［実施態様４９］  ドキュメントはテキストデータを有する実施態様４３記載の１組のドキュメントの推測にもとづく階層的記述を使用する情報検索システムの検索方法。
【０１３０】
［実施態様５０］  前記テキストデータは英語以外の言語である実施態様４９記載の１組のドキュメントの推測にもとづく階層的記述を使用する情報検索システムの検索方法。
【０１３１】
［実施態様５１］  ドキュメントはオーディオデータを有する実施態様４３記載の１組のドキュメントの推測にもとづく階層的記述を使用する情報検索システムの検索方法。
【０１３２】
［実施態様５２］  ドキュメントはマルチメディア・データを有する実施態様４３記載の１組のドキュメントの推測にもとづく階層的記述を使用する情報検索システムの検索方法。
【０１３３】
［実施態様５３］  （ａ）ドキュメントの集合の階層を設けるステップと、
（ｂ）ドキュメントのコレクション・セットを設けるステップと、
（ｃ）前記階層内の１組のドキュメント内の各ドキュメントに対して、ならびにドキュメントの前記コレクション・セット内の各ドキュメントに対して、インバウンド・リンクを決定するステップと、
（ｄ）前記階層内のドキュメントの前記集合内の各ドキュメントに対して、ならびにドキュメントの前記コレクション・セット内の各ドキュメントに対して、
仮想ドキュメントを創出するステップと、
（ｅ）前記階層内のドキュメントの前記集合と組み合わされた前記仮想ドキュメントからフィーチャーの第１のヒストグラムを創出するステップと、
（ｆ）ドキュメントの前記コレクション・セットと組み合わされた前記仮想ドキュメントからフィーチャーの第２のヒストグラムを創出するステップと、
（ｇ）前記フィーチャーを含む前記階層内のドキュメントの前記集合と組み合わされた前記仮想ドキュメントの割合と、前記フィーチャーを含むドキュメントの前記コレクション・セットと組み合わされた仮想ドキュメントの割合にもとづいて、各フィーチャーがセルフ・フィーチャー、ペアレント・フィーチャーあるいはチャイルド・フィーチャーであるか否かを決定するステップと、
（ｈ）ドキュメントの集合の前記階層内のドキュメントの各集合に対してステップ（ｃ）からステップ（ｇ）を繰り返すステップと、
（ｉ）各フィーチャーを決定することに応答するドキュメントの集合の前記階層に符号を付けるステップを有するドキュメントの集合の推測にもとづく記述を使用してドキュメント・ディレクトリに符号を付ける方法。
【０１３４】
［実施態様５４］  各フィーチャーがセルフ・フィーチャー、ペアレント・フィーチャーあるいはチャイルド・フィーチャーであるか否かを決定する前記ステップは、ペアレント、チルドレンおよびセルフ予測アルゴリズムを使用して実行される実施態様５３記載のドキュメントの集合の推測にもとづく記述を使用してドキュメント・ディレクトリに符号を付ける方法。
【０１３５】
［実施態様５５］  （ａ）ドキュメントの集合の階層を設けるステップと、
（ｂ）ドキュメントのコレクション・セットを設けるステップと、
（ｃ）前記階層内のドキュメントの各集合からフィーチャーの第１のヒストグラムを創出するステップと、
（ｄ）ドキュメントの前記コレクション・セットからフィーチャーの第２のヒストグラムを創出するステップと、
（ｅ）前記フィーチャーを含む前記階層内のドキュメントの前記集合と組み合わされたドキュメントの割合と、前記フィーチャーを含むドキュメントの前記コレクション・セットと組み合わされたドキュメントの割合にもとづいて、各フィーチャーがセルフ・フィーチャー、ペアレント・フィーチャーあるいはチャイルド・フィーチャーであるか否かを決定するステップと、
（ｆ）ドキュメントの集合の前記階層内のドキュメントの各集合に対してステップ（ｃ）からステップ（ｅ）を繰り返すステップと、
（ｇ）各フィーチャーを決定することに応答するドキュメントの集合の前記階層に符号を付けるステップを有するドキュメントの集合の推測にもとづく記述を使用してドキュメント・ディレクトリに符号を付ける方法。
【０１３６】
［実施態様５６］  各フィーチャーがセルフ・フィーチャー、ペアレント・フィーチャーあるいはチャイルド・フィーチャーであるか否かを決定する前記ステップは、ペアレント、チルドレンおよびセルフ予測アルゴリズムを使用して実行される実施態様５５記載のドキュメントの集合の推測にもとづく記述を使用してドキュメント・ディレクトリに符号を付ける方法。
【０１３７】
［実施態様５７］  ドキュメントのポジティブ・セットを有するドキュメントの第１の集合を得るステップと、
ドキュメントのコレクション・セットを有するドキュメントの第２の集合を得るステップと、
ドキュメントの前記第１の集合内の各ドキュメントに対して、ならびにドキュメントの前記第２の集合内の各ドキュメントに対して、インバウンド・リンクを決定するステップと、
ドキュメントの前記ポジティブ・セット内の各ドキュメントに対する仮想ドキュメント、およびドキュメントの前記コレクション・セット内の各ドキュメントに対する仮想ドキュメントを創出するステップと、
ドキュメントの前記第１の集合と組み合わされた前記仮想ドキュメントからフィーチャーの第１のヒストグラムを供給するステップと、
ドキュメントの前記第２の集合と組み合わされた前記仮想ドキュメントからフィーチャーの第２のヒストグラムを供給するステップと、
前記フィーチャーを含むドキュメントの前記ポジティブ・セットと組み合わされた前記仮想ドキュメントの割合と、前記フィーチャーを含むドキュメントの前記コレクション・セットと組み合わされた前記仮想ドキュメントの割合にもとづいて、各フィーチャーがセルフ・フィーチャー、ペアレント・フィーチャーあるいはチャイルド・フィーチャーであるか否かを決定するステップを有する１組のドキュメントの階層的記述を推測する方法。
【０１３８】
［実施態様５８］  ヒストグラム閾値を設定し、前記第１のヒストグラムおよび前記第２のヒストグラムの両方の中の前記閾値以下のフィーチャーを除去するステップをさらに有する実施態様５７記載の１組のドキュメントの階層的記述を推測する方法。
【０１３９】
［実施態様５９］  ドキュメントの前記ポジティブ・セット内の出現の順序により前記フィーチャーを順位付けることをさらに有する実施態様５７記載の１組のドキュメントの階層的記述を推測する方法。
【０１４０】
［実施態様６０］  ドキュメントは画像データを含む実施態様５７記載の１組のドキュメントの階層的記述を推測する方法。
【０１４１】
［実施態様６１］  ドキュメントはテキストデータを含む実施態様５７記載の１組のドキュメントの階層的記述を推測する方法。
【０１４２】
［実施態様６２］  前記テキストデータは英語以外の言語である実施態様６１記載の１組のドキュメントの階層的記述を推測する方法。
【０１４３】
［実施態様６３］  ドキュメントはオーディオデータを含む実施態様５７記載の１組のドキュメントの階層的記述を推測する方法。
【０１４４】
［実施態様６４］  ドキュメントはマルチメディア・データを含む実施態様５７記載の１組のドキュメントの階層的記述を推測する方法。
【０１４５】
［実施態様６５］  各フィーチャーがセルフ・フィーチャー、ペアレント・フィーチャーあるいはチャイルド・フィーチャーであるか否かを決定する前記ステップは、ペアレント、チルドレンおよびセルフ予測アルゴリズムを使用して実行される実施態様５７記載の１組のドキュメントの階層的記述を推測する方法。
【０１４６】
［実施態様６６］  ヒストグラム閾値を設定し、前記第１のヒストグラムおよび前記第２のヒストグラムの両方の中の前記閾値以下のフィーチャーを除去するステップをさらに有する実施態様６５記載の１組のドキュメントの階層的記述を推測する方法。
【０１４７】
［実施態様６７］  ドキュメントの前記ポジティブ・セット内の出現の順序により前記フィーチャーを順位付けることをさらに有する実施態様６５記載の１組のドキュメントの階層的記述を推測する方法。
【０１４８】
［実施態様６８］  ドキュメントは画像データを含む実施態様６５記載の１組のドキュメントの階層的記述を推測する方法。
【０１４９】
［実施態様６９］  ドキュメントはテキストデータを含む実施態様６５記載の１組のドキュメントの階層的記述を推測する方法。
【０１５０】
［実施態様７０］  前記テキストデータは英語以外の言語である実施態様６９記載の１組のドキュメントの階層的記述を推測する方法。
【０１５１】
［実施態様７１］  ドキュメントはオーディオデータを含む実施態様６５記載の１組のドキュメントの階層的記述を推測する方法。
【０１５２】
［実施態様７２］  ドキュメントはマルチメディア・データを含む実施態様６５記載の１組のドキュメントの階層的記述を推測する方法。
【図面の簡単な説明】
【０１５３】
【図１】ペアレント・フィーチャー、チャイルド・フィーチャーおよびセルフ・ィーチャーの間の予測される関係を示すグラフ図である。
【図２】生物学のセルフ・フィーチャー、科学のペアレント・フィーチャーおよび植物学のチャイルド・フィーチャーに対するフィーチャーの分布の見本である。
【図３】オープン・ディレクトリからのグラウンド・トルース・フィーチャーの分布のグラフである。
【図４】ペアレントが「computers」から「computer」に変わり、ペアレントの知識無しに定義されなかったサブカテゴリーのいくつか、すなわち、「ニュース」あるいは「リソース」が除去されたこと以外は、図３に類似のグラフである。
【図５】拡張アンカーテキストの概念図である。
【図６】フルテキストの代わりに拡張アンカーテキスト仮想ドキュメントを使用した、オープン・ディレクトリからのグラウンド・トルース・フィーチャーのグラフである。
【図７】ペアレントが「computers」から「computer」に変わり、不十分に定義されたチルドレンが除去され、フルテキストの代わりに拡張アンカーテキスト仮想ドキュメントを使用した、オープン・ディレクトリからのグラウンド・トルース・フィーチャーのグラフである。
【符号の説明】
【０１５４】
１０    ペアレント・フィーチャー
１２    チャイルド・フィーチャー
１４    セルフ・フィーチャー
【図１】
2006318511.tif 000015
【図２】
2006318511.tif 000016
【図３】
2006318511.tif 000017
【図４】
2006318511.tif 000018
【図５】
2006318511.tif 000019
【図６】
2006318511.tif 000020
【図７】
2006318511.tif 000021