(57)【要約】  クエリについてラベル付けされたドキュメントの関連性を、ラベル付けされていないドキュメントに伝搬する方法およびシステムを提供する。伝搬システムは、クエリと、クエリとの関連性でラベル付けされたドキュメントと、ラベル付けされていないドキュメントとを含むトレーニングデータを提供する。伝搬システムは次いで、トレーニングデータ内のドキュメントの対の間の類似性を計算する。伝搬システムは次いで、ラベル付けされたドキュメントの関連性を、類似であるがラベル付けされていないドキュメントに伝搬する。伝搬システムは、ラベルが解に収束するまでドキュメントのラベルを繰り返し伝搬することができる。伝搬された関連性を有するトレーニングデータを次いで使用して、ランキング機能をトレーニングすることができる。
2009528627.tif 000002
【特許請求の範囲】
【請求項１】
ドキュメントランキングコンポーネントをトレーニングするシステムであって、
ドキュメントの表示と、複数のクエリの各クエリに関して、前記クエリに対する前記ドキュメントの関連性による前記ドキュメントの一部へのラベル付けとを含むトレーニングデータを含むトレーニングデータストア（２３２）と、
ラベル付けされたドキュメントの関連性を、ドキュメント間の類似性に基づいてラベル付けされていないドキュメントに伝搬する関連性伝搬コンポーネント（２３５）と、
ドキュメントランキングコンポーネントをトレーニングして、前記トレーニングデータのドキュメントの伝搬された関連性に基づいて、クエリに対するドキュメントの関連性をランク付けするトレーニングコンポーネント（２４１）と
を備えることを特徴とするシステム。
【請求項２】
前記ドキュメントランキングコンポーネントは、ニューラルネットワークアルゴリズム、アダプティブブースティングアルゴリズム、およびサポートベクトルマシンアルゴリズムから成るグループから選択される分類アルゴリズムを実装することを特徴とする請求項１に記載のシステム。
【請求項３】
前記ドキュメントランキングコンポーネントは、回帰ベースのアルゴリズムを実装することを特徴とする請求項１に記載のシステム。
【請求項４】
前記関連性伝搬コンポーネントは、各クエリに関する関連性を別々に伝搬し、前記トレーニングコンポーネントは、別々に伝搬された前記関連性を使用して前記ドキュメントランキングコンポーネントをトレーニングすること特徴とする請求項１に記載のシステム。
【請求項５】
前記関連性伝搬コンポーネントは、複数のクエリに関する関連性を同時に伝搬し、前記トレーニングコンポーネントは、同時に伝搬された前記関連性を使用して前記ドキュメントランキングコンポーネントをトレーニングすること特徴とする請求項１に記載のシステム。
【請求項６】
ドキュメント間の類似性を表すエッジによって接続されたノードとして表されたドキュメントでグラフを作成するグラフコンポーネントを含むことを特徴とする請求項１に記載のシステム。
【請求項７】
前記グラフコンポーネントは、
類似のドキュメントを表すノードがエッジを介して接続されるグラフを構築するグラフ構築コンポーネントと、
接続された前記ノードによって表される前記ドキュメントの類似性に基づいて前記エッジの重みを生成する重み生成コンポーネントと
を含むことを特徴とする請求項６に記載のシステム。
【請求項８】
前記グラフ構築コンポーネントは、最近傍アルゴリズムを使用してノード間のエッジを確立することを特徴とする請求項７に記載のシステム。
【請求項９】
前記関連性伝搬コンポーネントは、マニホールドランキングベースのアルゴリズムを使用して関連性を伝搬することを特徴とする請求項１に記載のシステム。
【請求項１０】
ドキュメントの表示を、クエリに対するドキュメントの関連性を示す前記ドキュメントの一部へのラベル付けとともに提供すること（２３２）と、
ドキュメント間の類似性を表すエッジによって接続されているノードとして表されたドキュメントでグラフを作成すること（２３６）と、
作成された前記グラフによって示されるドキュメント間の類似性に基づいて、およびマニホールドランキングベースのアルゴリズムに基づいて、ラベル付けされたドキュメントの関連性をラベル付けされていないドキュメントに伝搬すること（２３９）と、
ドキュメントの伝搬された前記関連性に基づいて、クエリに対するドキュメントの関連性をランク付けするために、ドキュメントランキングコンポーネントをトレーニングすること（２４１）と
を含む方法によってコンピュータシステムを制御してドキュメントランキングコンポーネントをトレーニングする命令を含むことを特徴とする、コンピュータ読み取り可能な媒体。
【請求項１１】
前記ドキュメントランキングコンポーネントは、ベイズネットアルゴリズム、アダプティブブースティングアルゴリズム、およびサポートベクトルマシンアルゴリズムから成るグループから選択される分類アルゴリズムを実装することを特徴とする請求項１０に記載のコンピュータ読み取り可能な媒体。
【請求項１２】
前記ドキュメントランキングコンポーネントは、回帰ベースのランキングアルゴリズムを実装することを特徴とする請求項１０に記載のコンピュータ読み取り可能な媒体。
【請求項１３】
前記関連性を伝搬することは、各クエリに関する関連性を別々に伝搬し、前記トレーニングは別々に伝搬された前記関連性を使用して前記ドキュメントランキングコンポーネントをトレーニングすること特徴とする請求項１０に記載のコンピュータ読み取り可能な媒体。
【請求項１４】
前記関連性伝搬コンポーネントは、関連性を伝搬（クエリ内伝搬）することを特徴とする請求項１０に記載のコンピュータ読み取り可能な媒体。
【請求項１５】
グラフを作成することは、
類似のドキュメントを表すノードがエッジを介して接続されるグラフを構築することと、
接続された前記ノードにより表された前記ドキュメントの類似性に基づいて前記エッジの重みを生成することと
を含むことを特徴とする請求項１０に記載のコンピュータ読み取り可能な媒体。
【請求項１６】
ドキュメントランキングコンポーネントをトレーニングするシステムであって、
ドキュメントの表示を、クエリに対するドキュメントの関連性を示す前記ドキュメントの一部へのラベル付けとともに提供するコンポーネント（２３１）と、
ドキュメント間の類似性を表すエッジによって接続されているノードとして表されたドキュメントでグラフを作成するコンポーネント（２３６）と、
作成された前記グラフによって示されるドキュメント間の類似性に基づいて、ラベル付けされたドキュメントの関連性をラベル付けされていないドキュメントに伝搬するコンポーネント（２３９）と、
ドキュメントの伝搬された前記関連性に基づいて、ドキュメントランキングコンポーネントを生成してクエリに対するドキュメントの関連性をランク付けするコンポーネントと
を備えることを特徴とするシステム。
【請求項１７】
関連性を伝搬する前記コンポーネントは、マニホールドランキングベースのアルゴリズムに基づいて関連性を伝搬することを特徴とする請求項１６に記載のシステム。
【請求項１８】
関連性を伝搬する前記コンポーネントは、複数のクエリに関する関連性を同時に伝搬し、前記ドキュメントランキングコンポーネントを生成する前記コンポーネントは、同時に伝搬された前記関連性を使用して前記コンポーネントを生成すること特徴とする請求項１７に記載のシステム。
【請求項１９】
グラフを作成する前記コンポーネントは、グラフを構築し、接続された前記ノードによって表された前記ドキュメントの類似性に基づいて前記エッジの重みを生成することを特徴とする請求項１６に記載のシステム。
【請求項２０】
前記ドキュメントランキングコンポーネントは、回帰ベースのランキングアルゴリズムを実装することを特徴とする請求項１６に記載のシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、伝搬されるドキュメントの関連性を用いてランキング機能をトレーニングすることに関する。
【背景技術】
【０００２】
Ｇｏｏｇｌｅ（登録商標）およびＯｖｅｒｔｕｒｅ（登録商標）などの多数の検索エンジンサービスは、インターネット経由でアクセス可能な情報の検索を提供する。これらの検索エンジンサービスによりユーザは、ウェブページなどの、ユーザにとって関心のある可能性がある表示ページを検索することができる。検索語句を含む検索要求（すなわち、クエリ）をユーザが提出（submit）した後、検索エンジンサービスは、これらの検索語句に関連する可能性のあるウェブページを特定する。関連するウェブページをすばやく特定するために、検索エンジンサービスは、ウェブページに対するキーワードのマッピングを保持することができる。ウェブ（すなわち、Ｗｏｒｌｄ  Ｗｉｄｅ  Ｗｅｂ）を「クロール」することによりこのマッピングを生成して、各ウェブページのキーワードを特定することができる。ウェブをクロールするために、検索エンジンサービスは、ルートウェブページのリストを使用して、これらのルートウェブページを通してアクセス可能な全てのウェブページを特定することができる。任意の特定のウェブページのキーワードを、見出し語、ウェブページのメタデータに与えられた語、強調された語などを特定することなどの様々な周知の情報取り出し技術（information retrieval technique）を使用して特定することができる。検索エンジンサービスは、検索要求に関連する可能性のあるウェブページを、ウェブページのキーワードがそのクエリの語にマッチする程度に基づいて特定する。検索エンジンサービスは次いで、特定されたウェブページへのリンクを、クエリに対するそれらの関連性、人気度、重要度、および／または何らかの他の指標によって決定可能なランキングに基づいた順序で、ユーザに表示する。
【０００３】
ウェブページのランクキングに関する３つの周知の技術は、ＰａｇｅＲａｎｋ（登録商標）、ＨＩＴＳ（「Hyperlinked-induced Topic Search」）、およびＤｉｒｅｃｔＨＩＴである。ＰａｇｅＲａｎｋは、ウェブページが重要なウェブページへのリンク（すなわち、「出リンク（outgoing link）」）を有するという原理に基づいている。したがって、あるウェブページの重要度は、該ウェブページへリンクする（すなわち、「入リンク（incoming link）」）他のウェブページの数と重要度に基づいている。簡単な形式では、ウェブページ間のリンクを隣接行列Ａによって表すことができ、ここでＡｉｊはウェブページiからウェブページｊへの出リンクの数を表す。ウェブページｊの重要度スコアｗｊを、次式で表すことができる。
【０００４】
【数１】
2009528627.tif 000003
【０００５】
この式を、次式に基づいて反復計算によって解くことができる。
【０００６】
【数２】
2009528627.tif 000004
【０００７】
ここで、ｗはウェブページの重要度スコア（important score）のベクトルであり、ＡＴの主要固有ベクトル（principal eigenvector）である。
【０００８】
ＨＩＴＳ技術はさらに、他の重要なウェブページへの多くのリンクを有するあるウェブページは、それ自身が重要である可能性があるという原理に基づいている。したがってＨＩＴＳは、ウェブページの「重要度」を２つの関連する属性、すなわち「ハブ（hub）」と「オーソリティ（authority）」に分割する。「ハブ」は、あるウェブページがリンクする複数のウェブページの「オーソリティ」スコアにより測定され、「オーソリティ」は、あるウェブページにリンクする複数のウェブページの「ハブ」スコアにより測定される。ウェブページの重要度をクエリと独立に計算するＰａｇｅＲａｎｋとは対照的に、ＨＩＴＳは重要度を、結果のウェブページと、後の入リンクおよび出リンクによって結果のウェブページに関連づけられるウェブページとに基づいて計算する。ＨＩＴＳは、クエリを検索エンジンサービスに提出し、結果のウェブページをウェブページの初期集合として使用する。ＨＩＴＳは該集合に、入リンクの宛先であるウェブページと、結果のウェブページの出リンク元であるウェブページとを追加する。ＨＩＴＳは、次いで反復アルゴリズムを使用して、各ウェブページのオーソリティとハブのスコアを計算する。オーソリティとハブのスコアを次式により表すことができる。
【０００９】
【数３】
2009528627.tif 000005
【００１０】
ここで、ａ（ｐ）はウェブページｐのオーソリティスコアを表し、ｈ（ｐ）はウェブページｐのハブスコアを表す。ＨＩＴＳは隣接行列Ａを使用してリンクを表す。隣接行列は次式によって表される。
【００１１】
【数４】
2009528627.tif 000006
【００１２】
ベクトルａおよびｈはそれぞれ、集合内の全てのウェブページのオーソリティとハブのスコアに対応し、次式で表すことができる。
【００１３】
【数５】
2009528627.tif 000007
【００１４】
したがって、ａおよびｈは、行列ＡＴＡおよびＡＡＴの固有ベクトルである。ＨＩＴＳを、訪問の数で測定されるウェブページの人気度の要因について修正することもできる。クリックスルーデータの分析に基づいて、ユーザがウェブページｉからウェブページｊに移動する度に隣接行列のｂｉｊを増加することができる。
【００１５】
ＤｉｒｅｃｔＨＩＴは、類似のクエリの結果を有する過去のユーザ履歴に基づいてウェブページをランク付けする。例えば、類似のクエリを提出するユーザが、典型的に結果の第３のウェブページを最初に選択していた場合、このユーザ履歴は、その第３のウェブページがより高くランク付けされるべきこと示すことになる。別の例として、類似のクエリを提出するユーザが、典型的にほとんどの時間を結果の第４のウェブページを見るのに費やす場合、このユーザ履歴は、その第４のウェブページがより高くランク付けされるべきこと示すことになる。ＤｉｒｅｃｔＨＩＴは、ユーザ履歴をクリックスルーデータの分析から導出する。
【００１６】
一部のランキング技術は、機械学習アルゴリズムを使用して、クエリ、ページを表す特徴ベクトル（feature vector）、および各クエリに関する各ページへのランキングを含むトレーニングデータからランキング機能を学習する。ランキング機能は、所与のクエリに関して、ページの特徴からそのランクへのマッピングの役割を果たす。ランキング機能の学習は一部によって、数的ランクで順序付けされた集合のメンバに対する特徴ベクトルのマッピングを学習する回帰問題として考えられていた。一部の回帰ベースの技術は、ページのランク付けに使用可能な絶対的関連性スコア（absolute relevance score）を提供しようと試みる。しかしながら、ランキング機能は絶対的関連性スコアを提供する必要はなく、ページの相対的ランキングを提供することのみが必要である。したがって、これらの回帰ベースの技術は、必要以上に困難な問題を解決する。
【発明の開示】
【発明が解決しようとする課題】
【００１７】
ランキング機能に関する機械学習アルゴリズムは、クエリ、特徴ベクトル、およびユーザがラベル付けした関連性スコアを、トレーニングデータとして使用する。トレーニングデータを生成するために、検索結果のページを生成する検索エンジンにクエリを提出することができる。該アルゴリズムは次いで、ページに関する特徴ベクトルを生成して、ユーザから各ページに関する関連性スコアを入力する。上記アプローチの難点は、検索エンジンがその検索結果として何百ものページを返す場合があることである。ユーザに検索結果の全てのページにラベル付けさせることは、非常にコストがかかる可能性がある。さらに、ユーザにとって、そのような非常に多数のページの関連性を正確に評価することは困難である可能性がある。ユーザは、ページのごく一部のみをラベル付けできるが、上記のごく一部に基づいた学習では正確なランキング機能を提供することができないことがある。
【課題を解決するための手段】
【００１８】
クエリについてラベル付けされたドキュメント（labeled document）の関連性を、ラベル付けされていないドキュメント（unlabeled document）の関連性に伝搬する方法およびシステムを提供する。伝搬システムは、クエリと、クエリとの関連性でラベル付けされたドキュメントと、ラベル付けされていないドキュメントとを含むトレーニングデータを提供する。伝搬システムは、次いでトレーニングデータ内のドキュメントの対の間の類似性を計算する。伝搬システムは、次いでラベル付けされたドキュメントの関連性を、類似であるがラベル付けされていないドキュメントに伝搬する。伝搬システムは、ドキュメントのラベルを、ラベルが解に収束するまで繰り返し伝搬することができる。次いで、伝搬された関連性を有するトレーニングデータを使用して、ランキング機能をトレーニングすることができる。
【００１９】
この「課題を解決するための手段」は、以下の「発明を実施するための最良の形態」でさらに詳細に説明される概念の選択を、簡略化した形式で紹介するために提供される。この「課題を解決するための手段」は、特許請求される主題の主要な特徴または本質的な特徴を特定するようには意図されておらず、特許請求される主題の範囲を定める助けとして用いられることも意図されていない。
【発明を実施するための最良の形態】
【００２０】
クエリについてラベル付けされたドキュメントの関連性を、ラベル付けされていないドキュメントの関連性に伝搬する方法およびシステムを提供する。一実施形態では、伝搬システムは、クエリ、クエリとの関連性でラベル付けされた（特徴ベクトルによって表された）ドキュメント、およびラベル付けされていないドキュメントを含むトレーニングデータを提供する。例えば、伝搬システムは、クエリを検索エンジンに提出して、検索結果をドキュメント（例えば、ウェブページ）として使用することができる。伝搬システムは次いで、ユーザに、検索結果のドキュメントの一部をそのクエリとの関連性に基づいてラベル付けするように促すことができる。伝搬システムは次いで、トレーニングデータ内のドキュメントの対の間の類似性を計算する。例えば、伝搬システムは、各ドキュメントを特徴ベクトルによって表すことができ、ドキュメント間の類似性を、特徴空間内のユークリッド距離（Euclidean distance）に基づいて、または余弦類似性メトリック（cosine similarity metric）に基づいて計算することができる。伝搬システムは次いで、ラベル付けされたドキュメントの関連性を、類似であるがラベル付けされていないドキュメントに伝搬する。伝搬システムは、ドキュメントのラベルを、ラベルが解に収束するまで繰り返し伝搬することができる。伝搬された関連性を有するトレーニングデータを次いで使用して、ランキング機能をトレーニングすることができる。このように伝搬システムは、ドキュメント間の類似性に基づいて、トレーニングデータを追加のトレーニングデータで自動的に増補することができる。
【００２１】
一実施形態において伝搬システムは、あるドキュメントを各ノードが表し、かつ接続されたノードによって表されるドキュメント間の類似性を各エッジが表すドキュメントグラフを使用して、複数のドキュメントを表す。伝搬システムはグラフを、各ドキュメントの行と列を有する正方行列で表すことができ、該正方行列では、ゼロでない値が行のノードと列のノードとの間のエッジを示す。伝搬システムは、様々な技術を使用してグラフのエッジを定義することができる。例えば、伝搬システムは、グラフが十分に接続されると見なすことがあり、この場合、各ノードは全ての他のノードに対するエッジを有する。別の例として、伝搬システムは、ノードが最小スパニングツリー（minimum spanning tree）を介して接続されると見なすことがある。一実施形態において、伝搬システムは、ノードがｋ最近傍アルゴリズム（k-nearest neighbor algorithm）を使用して接続されると見なす。特に、伝搬システムは、各ノードに対するｋ最近傍を特定して、そのノードからそのｋ最近傍のそれぞれにエッジを追加する。伝搬システムは次いで、エッジの重みを、接続されたエッジによって表されたドキュメント間の類似性に基づいて計算する。伝搬システムは、ドキュメント間の類似性を決定する様々な技術を使用することができる。一実施形態において、伝搬システムは、特徴空間内のドキュメントの特徴ベクトル表示に基づいてユークリッド距離のメトリクスを使用する。伝搬システムは類似性を、類似性行列または親和性行列となる正方行列の値として記憶する。伝搬システムは、類似性行列を正規化することもできる。伝搬システムは対角値を０に設定して、関連性の伝搬中の自己強化（self-reinforcement）を防止することもできる。
【００２２】
類似性行列の生成後、伝搬システムはラベル付けされたドキュメントの関連性を、マニホールドランキングベース（manifold ranking based）の伝搬アルゴリズムを使用して、ラベル付けされていないドキュメントに伝搬する。マニホールドランキングベースのアルゴリズムは、「He, J., Li, M., Zhang, H.J., et al., “Manifold-Ranking Based Image Retrieval,” Proc. of the 12th Annual ACM International Conf. on Multimedia, 2004」において説明されている。伝搬システムは最初に、ラベル付けされたドキュメントの関連性をユーザによって提供される関連性スコアに設定し、ラベル付けされていないドキュメントの関連性を０に設定する。伝搬システムは次いで、ラベル付けされたドキュメントの関連性を、類似性行列によって示されるように類似性の因子となっている、その接続されるラベル付けされていないドキュメントに広げる。伝搬システムは関連性スコアを、関連性スコアが解に収束するまで繰り返し広げる。結果として得られるラベル付けされていないドキュメントの関連性スコアは、それがラベル付けされたドキュメントのときの同一のクエリに関連する確率に比例することになる。高い関連性スコアを有する多数のラベル付けされたドキュメントと非常に類似するラベル付けされていないドキュメントは、したがって高い関連性スコアを有することになる。反対に、いずれのラベル付けされたドキュメントともあまり類似しないラベル付けされていないドキュメントは、低い関連性スコアを有することになる。
【００２３】
伝搬システムは、次式で表すことができるラプラスカーネル（Laplace kernel）を使用して、類似性を表すことができる。
【００２４】
【数６】
2009528627.tif 000008
【００２５】
ここで、ｘｉｌおよびｘｊｌはそれぞれｘｉおよびｘｊの第ｌ次元を表し、ｔは特徴空間の次元を表し、σlは類似性計算における異なる次元の重みを示す正のパラメータを表す。したがって、伝搬システムは次式でエッジの重みを表す。
【００２６】
【数７】
2009528627.tif 000009
【００２７】
ここで、Ｗｉｊはドキュメントｉとｊの間の類似性を表す。伝搬システムは、一定係数１／２σlを省略することができるが、これは類似性行列Ｗに対する一定係数の影響が行列の正規化によって相殺されるからである。伝搬システムは、次式で表されるように類似性行列を正規化する。
【００２８】
【数８】
2009528627.tif 000010
【００２９】
ここで、Ｓは正規化した類似性行列を表し、Ｄは（ｉ，ｉ）は類似性行列Ｗのｉ番目の行の和に等しい対角行列を表す。正規化では、接続されたドキュメントの類似性と関連するように類似性を正規化する。
【００３０】
伝搬システムは各ドキュメントを、ユークリッド空間内の点を形成するｔ次元の特徴ベクトルｘとして表すことができる。クエリに関して、伝搬システムはドキュメントの結果集合
【００３１】
【数９】
2009528627.tif 000011
【００３２】
を受け取る。（特徴空間内の）最初のｍ個の点はユーザがラベル付けしたドキュメントを表し、（特徴空間内の）最後のｎ個の点はラベル付けされていないドキュメントを表す。伝搬システムは対応するラベルベクトル
【００３３】
【数１０】
2009528627.tif 000012
【００３４】
も受け取る。最後のｎ個のラベルは０の値を有し、ラベル付けされていないドキュメントを表す。伝搬システムは、正のラベルだけではなく負のラベルの指定も可能にし、負の関連性の例を表すことができる。伝搬システムは、特徴空間内のドキュメント間の距離を、
【００３５】
【数１１】
2009528627.tif 000013
【００３６】
と表して、点ｘｉおよびｘｊの各対に距離ｄ（ｘｉ，ｘｊ）を割り当て、ドキュメントのランキング機能を、
【００３７】
【数１２】
2009528627.tif 000014
【００３８】
と表して、各点χｉをランキングスコアｆｉに割り当てる。ランキング機能の学習の問題は、特徴Ｘ＝｛χｑ｝およびラベルＹ＝｛γｑ｝を有するクエリの集合から
【００３９】
【数１３】
2009528627.tif 000015
【００４０】
を学習することである。伝搬システムは、次式により関連性伝搬の限界を表す。
【００４１】
【数１４】
2009528627.tif 000016
【００４２】
ここで、ｆ＊は関連性の限界を表し、ｙは初期ラベルを表し、αは減衰因子（decay factor）を表す。正規化した類似性行列Ｓの逆行列を計算することは計算量的に困難であるので、伝搬システムは、テイラー級数展開（Taylor series expansion）を使用してｆ＊を近似する。伝搬システムは、次式によりテイラー級数展開を表すことができる。
【００４３】
【数１５】
2009528627.tif 000017
【００４４】
伝搬システムは、解に収束するまで、または一定回数繰り返すまで、ｆ＊に関して繰り返し解く。
【００４５】
関連性を伝搬すると、伝搬ラベル付けシステムは、トレーニングデータの集合（クエリおよびラベル付けされた特徴ベクトル）を使用してランキング機能をトレーニングすることができる。ランキング機能を、サポートベクトルマシン、アダプティブブースティング分類器（adaptive boosting classifier）、ニューラルネットワーク分類器などとして実装することができる。サポートベクトルマシンは、可能性ある入力の空間内で超平面を見つけることによって動作する。超平面は、該超平面に対する最近傍の正の例と負の例との間の距離を最大化することによって、負の例から正の例を分離することを試みる。これにより、トレーニングデータに類似するが同一ではないデータの正しい分類が可能になる。様々な技術を使用して、サポートベクトルマシンをトレーニングすることができる。ある技術では、大きな二次計画問題（quadratic programming problem）を分析的に解くことができる一連の小さな二次計画問題に分解する、逐次最小最適化（sequential minimal optimization）アルゴリズムを使用する。（http://research.microsoft.com/~jplatt/smo.htmlで逐次最小最適化アルゴリズムを参照されたい）。
【００４６】
アダプティブブースティング（adaptive boosting）は、トレーニングデータの収集において複数のテストを実行する反復プロセスである。アダプティブブースティングは弱い学習アルゴリズム（運よりわずかだけ良いレベルで実施するアルゴリズム）を強い学習アルゴリズム（低い誤り率を示すアルゴリズム）に変換する。弱い学習アルゴリズムは、トレーニングデータの異なるサブセットにおいて実行される。該アルゴリズムは、その前の学習者が誤りを示す傾向にある例にますます集中する。該アルゴリズムは、以前の弱い学習者による誤りを補正する。該アルゴリズムは、その前の学習者の誤り率に順応するので適応的である。アダプティブブースティングは、不正確な経験法則を大まかかつ適度に結合して、高性能のアルゴリズムを作成する。アダプティブブースティングはそれぞれ別々に実行されたテストの結果を、単一の非常に正確な分類器に結合する。
【００４７】
ニューラルネットワークモデルは３つの主要なコンポーネント、すなわち、アーキテクチャ、費用関数、および検索アルゴリズムを有する。アーキテクチャは（ネットワークトポロジ、ユニット接続性、および活性化関数の観点で）入力を出力に関連付ける機能の形式を定義する。重みの集合に関する重み空間では、目的関数を最小化する検索がトレーニングプロセスである。ニューラルネットワークモデルは、ＲＢＦ（radial basis function）ネットワークおよび標準勾配降下（standard gradient descent）をその検索技術として使用することができる。
【００４８】
図１は、クエリの検索結果として返されるドキュメントのグラフを示す図である。本例では、サブグラフ１００は、検索結果において返されたドキュメントの一部分を表す。ノード１０１−１１２は、検索結果の１２個のドキュメントを表す。ノード１０１および１０６は、ラベル付けされたドキュメントを表す。ノード１０１によって表されるドキュメントは．７５の関連性スコアがラベル付けされており、ノード１０６によって表されるドキュメントは．６の関連性スコアがラベル付けされている。伝搬システムは、最近傍アルゴリズムを使用してノード間のエッジを生成する。本例では、ノード１０２、１０３、および１０４はそれぞれ、ノード１０１に対するｋ最近傍のノードであるが、ノード１０５−１１２はｋ最近傍のノードではない。伝搬システムは次いで、類似性スコアアルゴリズムを使用して、接続されたノード間の類似性を計算する。例えば、ノード１０１は．８の重みを有するエッジでノード１０２と接続され、その重みは接続されたノード間の類似性を示す。
【００４９】
図２は、一実施形態における伝搬システムのコンポーネントを示すブロック図である。伝搬システム２３０は、通信リンク２２０（例えば、インターネット）を介してドキュメントストア２１０（例えば、ウェブサイト）に接続される。伝搬システムは、トレーニングデータ収集コンポーネント２３１、トレーニングデータストア２３２、およびドキュメントインデックス２３３を含む。ドキュメントインデックスには、ドキュメントストア内のドキュメント（例えば、ウェブページ）のインデックスが含まれる。ドキュメントインデックスをウェブクローラ（web crawler）によって生成することができる。ドキュメントインデックスは、ランキング機能のトレーニングに使用される、各ドキュメントの特徴ベクトルを含むことができる。特徴ベクトルは、逆ドキュメント（inverse document）頻度、キーワード、フォントサイズなどの、ドキュメントの多くの異なるタイプの特徴を表すことができる。トレーニングデータ収集コンポーネントは、クエリを検索エンジン（図示せず）に提出し、そのクエリにマッチするドキュメントを受け取る。検索エンジンは伝搬システムと独立にすることができる。このような場合、伝搬システムは、検索結果から動的に特徴ベクトルを生成することができる。トレーニングデータ収集コンポーネントは、ユーザに、クエリにマッチする一部のドキュメントの関連性をラベル付けするよう促すことができる。トレーニングデータ収集コンポーネントは、クエリ、検索結果（例えば、特徴ベクトル）、およびラベルをトレーニングデータストアに格納する。伝搬システムは、関連性伝搬コンポーネント２３５、グラフ構築コンポーネント２３６、グラフ重み生成コンポーネント２３７、グラフ重み正規化コンポーネント２３８、およびグラフに基づく関連性伝搬コンポーネント２３９も含む。関連性伝搬コンポーネントは、ラベル付けされたドキュメントの関連性を、トレーニングデータストア内に格納されるラベル付けされていないドキュメントに伝搬する。関連性伝搬コンポーネントは、グラフ構築コンポーネントを起動（invoke）して、検索結果のドキュメントを表すエッジを含むグラフを構築する。関連性伝搬コンポーネントは次いで、グラフ重み生成コンポーネントを起動して、グラフのエッジの初期の重みを生成する。関連性伝搬コンポーネントは、グラフ重み正規化コンポーネントを起動して、生成された重みを正規化する。関連性伝搬コンポーネントは次いで、グラフに基づく関連性伝搬コンポーネントを起動して、ラベル付けされたドキュメントからラベル付けされていないドキュメントへの関連性の実際の伝搬を実行する。伝搬システムには、ランキング機能作成コンポーネント２４１、およびランキング機能２４２も含まれる。ランキング機能作成では、伝搬された関連性を有するトレーニングデータを使用してランキング機能を作成する。
【００５０】
伝搬システムを実装することができるコンピューティング装置は、中央演算装置、メモリ、入力装置（例えば、キーボードおよびポインティングデバイス）、出力装置（例えば、ディスプレイ装置）、および記憶装置（例えば、ディスクドライブ）を含むことができる。メモリおよび記憶装置は、伝搬システムを実装する命令を含むことができるコンピュータ読み取り可能な媒体である。さらに、データ構造およびメッセージ構造を、格納するか、または通信リンク上の信号などのデータ伝送媒体を介して伝送することができる。インターネット、ローカルエリアネットワーク、広域ネットワーク、ポイントツーポイントダイヤルアップ接続などの様々な通信リンクを使用することができる。
【００５１】
伝搬システムは、パーソナルコンピュータ、サーバコンピュータ、ハンドヘルドまたはラップトップデバイス、マルチプロセッサシステム、マイクロプロセッサベースのシステム、プログラム可能な家庭用電化製品、ネットワークＰＣ、ミニコンピュータ、メインフレームコンピュータ、上記のシステムまたは装置のいずれかを含む分散コンピューティング環境などを含め、様々なコンピューティングシステムまたは装置にサービスを提供することができる。
【００５２】
伝搬システムは、プログラムモジュールなどの、１つまたは複数のコンピュータあるいは他の装置によって実行されるコンピュータ実行可能な命令との一般的な関連において説明することができる。一般的に、プログラムモジュールは、特定のタスクを実行するかまたは特定の抽象データ型を実装するルーチン、プログラム、オブジェクト、コンポーネント、データ構造などを含む。典型的に、プログラムモジュールの機能性を、様々な実施形態において望まれるように組み合わせるかまたは分散させることができる。
【００５３】
図３は、一実施形態における伝搬システムのランキング機能作成コンポーネントの処理を示すフロー図である。ランキング機能作成コンポーネントは、トレーニングデータを収集し、ラベル付けされたドキュメントの関連性をラベル付けされていないドキュメントに伝搬し、次いでランキング機能をトレーニングする。ブロック３０１で、該コンポーネントは、トレーニングデータを収集する。ブロック３０２で、該コンポーネントは、トレーニングデータのサブセットにラベルを入力する。ブロック３０３で、該コンポーネントは、関連性伝搬コンポーネントを起動して、ラベル付けされたドキュメントの関連性をラベル付けされていないドキュメントに伝搬する。ブロック３０４で、該コンポーネントは、伝搬された関連性を使用してランキング機能をトレーニングする。
【００５４】
図４は、一実施形態における伝搬システムの関連性伝搬コンポーネントの処理を示すフロー図である。該コンポーネントはトレーニングデータを提供され、該コンポーネントは、ラベル付けされたドキュメントの関連性をラベル付けされていないドキュメントに伝搬する。ブロック４０１で、該コンポーネントは、グラフ構築コンポーネントを起動して、エッジを含む初期グラフを構築する。ブロック４０２で、該コンポーネントは、グラフ重み生成コンポーネントを起動して、接続されたノードによって表されるドキュメント間の類似性を示す重みを生成する。ブロック４０３で、該コンポーネントは、グラフ重み正規化コンポーネントを起動して、グラフの重みを正規化する。ブロック４０４で、該コンポーネントは、グラフに基づく関連性伝搬コンポーネントを起動して、関連性の伝搬を実行する。その後、該コンポーネントの処理は戻る。
【００５５】
図５は、一実施形態における伝搬システムのグラフ構築コンポーネントの処理を示すフロー図である。該コンポーネントは、それぞれドキュメントを表す行と列で正方行列を作成する。該コンポーネントは次いで、各ノードとそのｋ最近傍（例えば、ｋ＝１０）との間の接続を特定して追加する。ブロック５０１で、該コンポーネントは次のドキュメントｉを選択する。決定ブロック５０２で、全てのドキュメントｉが既に選択されていた場合、該コンポーネントの処理は戻り、そうでなければ該コンポーネントはブロック５０３に続く。ブロック５０３で、該コンポーネントは次のドキュメントｊを選択する。決定ブロック５０４で、選択されたドキュメントｉに対するドキュメントｊの全てが既に選択されていた場合、該コンポーネントはブロック５０６に続き、そうでなければ該コンポーネントはブロック５０５に続く。ブロック５０５で、該コンポーネントは、選択されたドキュメントｉと選択されたドキュメントｊとの間の距離を計算し、次いでブロック５０３にループして次のドキュメントｊを選択する。ブロック５０６で、該コンポーネントは、ドキュメントｉへの最小距離を有する（すなわち、最近傍）１０個のドキュメントｊを選択し、次いでブロック５０１にループして次のドキュメントｉを選択する。
【００５６】
図６は、一実施形態における伝搬システムのグラフ重み生成コンポーネントの処理を示すフロー図である。該コンポーネントは、接続されたドキュメント間の類似性をマンハッタンメトリック（Manhattan metric）に基づいて計算する。ブロック６０１で、該コンポーネントは次のドキュメントｉを選択する。決定ブロック６０２で、全てのドキュメントｉが既に選択されていた場合、該コンポーネントの処理は戻り、そうでなければ該コンポーネントはブロック６０３に続く。ブロック６０３で、該コンポーネントは、ドキュメントの自身に対する類似性を０に初期化する。ブロック６０４で、該コンポーネントは、選択されたドキュメントｉに対する次の最近傍のドキュメントｊ（すなわち、接続されたドキュメント）を選択する。決定ブロック６０５で、選択されたドキュメントｉに対する最近傍のドキュメントｊの全てが既に選択されていた場合、該コンポーネントはブロック６０１にループして次のドキュメントｉを選択し、そうでなければ該コンポーネントはブロック６０６に続く。ブロック６０６で、該コンポーネントは、選択されたドキュメントｉと選択されたドキュメントｊとの間の類似性を１に初期化する。ブロック６０７−６０９では、該コンポーネントはループして距離メトリックを計算する。ブロック６０７で、該コンポーネントは、特徴ベクトルの次の次元ｌを選択する。決定ブロック６０８で、全ての次元が既に選択されていた場合、該コンポーネントはブロック６０４にループして次の最近傍ドキュメントｊを選択し、そうでなければ該コンポーネントはブロック６０９に続く。ブロック６０９で、該コンポーネントは、選択されたドキュメントｉと選択されたドキュメントｊとの間の類似性を、その現在の類似性に、式２による選択されたドキュメントｉの選択された特徴ｌと選択されたドキュメントｊの選択された特徴ｌとの間の差の関数を乗じたものに設定する。該コンポーネントは、次いでブロック６０７にループして次の次元を選択する。
【００５７】
図７は、一実施形態における伝搬システムのグラフ重み正規化コンポーネントの処理を示すフロー図である。該コンポーネントは類似性行列の重みを正規化する。ブロック７０１で、該コンポーネントは類似性行列の次の行ｉを選択する。決定ブロック７０２で、全ての行が既に選択されていた場合、該コンポーネントはブロック７０６に続き、そうでなければ該コンポーネントはブロック７０３に続く。ブロック７０３−７０５では、該コンポーネントは、選択された行に関して対角行列Ｄの値を計算する。ブロック７０３で、該コンポーネントは類似性行列の次の列ｊを選択する。決定ブロック７０４で、全ての列が既に選択されていた場合、該コンポーネントはブロック７０１にループして次の行を選択し、そうでなければ該コンポーネントはブロック７０５に続く。ブロック７０５で、該コンポーネントは、選択された行ｉと選択された列ｊの重みを、選択された行ｉの対角要素に追加する。該コンポーネントは、次いでブロック７０３にループして、選択された行ｉに対して次の列ｊを選択する。ブロック７０６で、該コンポーネントは、式３に従って類似性行列を正規化する。
【００５８】
図８は、一実施形態における伝搬システムのグラフに基づく関連性伝搬コンポーネントの処理を示すフロー図である。該コンポーネントは式５のテイラー級数展開を、それが解に収束するまで繰り返し計算する。ブロック８０１で、該コンポーネントはインデックスｉをゼロに初期化する。ブロック８０２で、該コンポーネントは解ベクトルを０に初期化する。ブロック８０３−８０５では、該コンポーネントは解に収束するまでループする。ブロック８０３で、該コンポーネントは、前の繰り返しの値にテイラー級数展開の次の因子を足したものに基づいて、次の繰り返しの値を計算する。決定ブロック６０４で、値が解に収束する場合、該コンポーネントの処理は戻り、そうでなければ該コンポーネントはブロック８０５に続く。ブロック８０５で、該コンポーネントは、次の繰り返しに対してインデックスをインクリメントし、ブロック８０３にループして次の繰り返しを実行する。
【００５９】
本主題を、構造的特徴および／または方法論的アクトに特有の言葉で説明してきたが、添付の特許請求の範囲において定義される主題は、必ずしも上述の特定の特徴またはアクトに制限されないことは理解されよう。むしろ、上述の特定の特徴およびアクトは、請求項を実装する形式の例として開示してある。伝搬システムを使用して検索結果を増加させることができる。例えば、検索エンジンは、ドキュメントのある特定のコーパスに基づいて検索結果を生成することができる。次いで検索結果のドキュメントの関連性を、伝搬システムを使用して異なるコーパスのドキュメントに伝搬することができる。次いで、最高の関連性を有する異なるコーパスのドキュメントを、検索結果に追加することができる。伝搬システムを使用して、単一のクエリに関する関連性でラベル付けされたドキュメントからラベル付けされていないドキュメントへ（クエリ内伝搬）、または複数のクエリに対する関連性でラベル付けされたドキュメントからラベル付けされていないドキュメントへ（クエリ間伝搬）、関連性を伝搬することができる。伝搬コンポーネントはトレーニングコンポーネントを、クエリ内伝搬で各クエリに関して別々に、クエリ間伝搬で複数のクエリに関して同時にトレーニングする。したがって、本発明は、添付の特許請求の範囲によるものを除き、限定されない。
【図面の簡単な説明】
【００６０】
【図１】ドキュメントのグラフの一部分を示す図である。
【図２】一実施形態における伝搬システムのコンポーネントを示すブロック図である。
【図３】一実施形態における伝搬システムのランキング機能作成コンポーネントの処理を示すフロー図である。
【図４】一実施形態における伝搬システムの関連性伝搬コンポーネントの処理を示すフロー図である。
【図５】一実施形態における伝搬システムのグラフ構築コンポーネントの処理を示すフロー図である。
【図６】一実施形態における伝搬システムのグラフ重み生成コンポーネントの処理を示すフロー図である。
【図７】一実施形態における伝搬システムのグラフ重み正規化コンポーネントの処理を示すフロー図である。
【図８】一実施形態における伝搬システムのグラフに基づく関連性伝搬コンポーネントの処理を示すフロー図である。
【図１】
2009528627.tif 000018
【図２】
2009528627.tif 000019
【図３】
2009528627.tif 000020
【図４】
2009528627.tif 000021
【図５】
2009528627.tif 000022
【図６】
2009528627.tif 000023
【図７】
2009528627.tif 000024
【図８】
2009528627.tif 000025
【国際調査報告】
2009528627.tif 000026
2009528627.tif 000027