(57)【要約】  クエリに対してラベルが付されたドキュメントの関連度をラベルなしドキュメントに伝播する方法とシステムを提供する。伝播システムは、クエリと、クエリに対する関連度によってラベルが付されたドキュメントと、ラベルが付されていないドキュメントと、を含む学習データを与える。伝播システムは学習データ内の複数対のドキュメント間における類似度を算出する。伝播システムはラベル付きのドキュメントの関連度を同様であるもののラベルなしのドキュメントに伝播する。伝播システムは、ラベルが解に収束するまで、ドキュメントのラベルを繰り返して伝播してもよい。伝播された関連度を有する学習データを、順位関数を訓練するのに利用することができる。
2009528628.tif 000002
【特許請求の範囲】
【請求項１】
ラベル付きドキュメントの関連度をラベルなしドキュメントに伝播するシステムであって、
クエリに対する関連度によってラベルが付されたいくつかのドキュメントの表示と、前記クエリに対する関連度によってラベルが付されていない他のドキュメントの表示と、を含むドキュメント蓄積部（２３２）と、
ドキュメント間の類似度を表すエッジによって接続されたノードとして表された前記ドキュメントを用いて前記ドキュメントのグラフを作成するグラフ部（２３６）と、
前記グラフの前記エッジによって表された類似度によって示されたドキュメント間の前記類似度に基づいて、前記ラベル付きドキュメントの関連度を前記ラベルなしドキュメントに伝播する関連度伝播部（２３９）と、
を備えるシステム。
【請求項２】
前記グラフ部は、
同様のドキュメントを表すノードがエッジを介して接続されているグラフを形成するグラフ形成部と、
接続された前記ノードによって表された前記ドキュメントの類似度に基づいて、前記エッジの重みを生成する重み生成部と、
前記グラフの前記重みを正規化する重み正規化部と、
を備えることを特徴とする請求項１に記載のシステム。
【請求項３】
前記グラフ形成部は最近接アルゴリズムを使用してノード間のエッジを確立することを特徴とする請求項２に記載のシステム。
【請求項４】
前記最近接アルゴリズムがユークリッド距離メトリックを用いていることを特徴とする請求項３に記載のシステム。
【請求項５】
前記グラフ形成部が、１つのノードを１０個の最近接ノードに接続することを特徴とする請求項３に記載のシステム。
【請求項６】
前記グラフ形成部が複数のノードの各対間におけるエッジを確立することを特徴とする請求項２に記載のシステム。
【請求項７】
前記グラフ形成部が、ノード間のエッジを確立して、最小スパニングツリーを生成することを特徴とする請求項２に記載のシステム。
【請求項８】
前記ラベル付きドキュメントの前記関連度はドキュメントのコーパス内のクエリに関連したドキュメントを検索することによって生成され、前記ラベルなしドキュメントはドキュメントのコーパス内に含まれないことを特徴する請求項１に記載のシステム。
【請求項９】
前記関連度伝播部が、多種の順位付けベースのアルゴリズムを使用して関連度を伝播することを特徴とする請求項１に記載のシステム。
【請求項１０】
前記関連度伝播部は以下の方程式によって関連度を伝播し、
f*=(1-α)(I-αS)-1y
f*が伝播された関連度ベクトルを表し、Sは類似マトリクスであり、yは初期関連度ベクトルを表し、αは減衰率を表していることを特徴とする請求項１に記載のシステム。
【請求項１１】
前記関連度伝播部は以下の方程式によって関連度を伝播し、
f*=(1＋αS＋α2S2＋…αNSN)y
f*が伝播された関連度ベクトルを表し、Sは類似マトリクスであり、yは初期関連度ベクトルを表し、αは減衰率を表しており、ｎはf*が解に収束する指数を表していることを特徴とする請求項1に記載のシステム。
【請求項１２】
ラベル付きページの関連度をラベルなしページに伝播するシステムであって、
クエリに対する関連度によってラベルが付されたいくつかのページの表示と、前記クエリに対する関連度によってラベルが付されていない他のページの表示と、を含むページ蓄積部（２３２）と、
ページ間の類似度を表すエッジによって接続されたノードとして表された前記ページを用いて前記ページのグラフを作成するグラフ部（２３６）と、
前記グラフの前記エッジによって表された類似度によって示されたページ間の前記類似度及び多種の順位アルゴリズムに基づいて、前記ラベル付きページの関連度を前記ラベルなしページに伝播する関連度伝播部（２３９）と、を備え、
前記グラフ部（２３６）は、
同様のページを表すノードがエッジを介して接続されているグラフを形成するグラフ形成部（２３６）と、
接続された前記ノードによって表された前記ページの類似度に基づいて、前記エッジの重みを生成する重み生成部（２３７）と、
を備えることを特徴とするシステム。
【請求項１３】
前記グラフ形成部は最近接アルゴリズムを使用してノード間のエッジを確立することを特徴とする請求項１２に記載のシステム。
【請求項１４】
前記最近接アルゴリズムがユークリッド距離メトリックを用いていることを特徴とする請求項１３に記載のシステム。
【請求項１５】
前記グラフ形成部が、１つのノードを１０個の最近接ノードに接続することを特徴とする請求項１３に記載のシステム。
【請求項１６】
前記重み生成部がページ間の類似度を表すマンハッタン距離メトリックを用いることを特徴とする請求項１２に記載のシステム。
【請求項１７】
ページの各々が特徴ベクトルによって表され、ページ間の類似度が特徴ベクトル空間内の距離によって表されることを特徴とする請求項１２に記載のシステム。
【請求項１８】
ドキュメント間の類似度を表す重みを有するエッジによって接続されたノードとして表されたドキュメントのグラフを生成するステップ（２３６）と、
多種の順位ベースアルゴリズムを用いて、ノード間の前記エッジの前記重みに基づいて、ラベルが付されていないドキュメントの関連度をラベルが付されていないドキュメントに伝播するステップ（２３９）と、を含む方法によって、
クエリに対するドキュメントの関連度を他のドキュメントに伝播するコンピュータシステムを制御する指示を含むコンピュータ読み取り可能な記録媒体。
【請求項１９】
前記ラベル付きドキュメントの前記関連度の前記伝播ステップは、式f*=(1-α)(I-αS)-1yを反復して解くテイラー展開を利用するステップを含むことを特徴とする請求項１８に記載のコンピュータ読み取り可能な記録媒体。
【請求項２０】
前記グラフの前記生成ステップは、最近接アルゴリズムを利用してエッジを接続するステップと、前記エッジにより接続された前記ノードによって表されたドキュメント間の距離に基づいてエッジの前記重みを確立するステップと、を含むことを特徴とする請求項１８に記載のコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、クエリに対してラベルが付されたドキュメントの関連度をラベルなしドキュメントに伝播するシステムに関する。
【背景技術】
【０００２】
GoogleやOverture等の多くの検索エンジン・サービスにより、インターネットを介してアクセス可能な情報が検索されている。これらの検索エンジン・サービスにより、ユーザは自身が興味あるウェブページ等の表示ページを検索することができる。ユーザが検索項目を含む検索要求(すなわち、クエリー)を送信した後に、検索エンジン・サービスはその検索項目に関連し得るウェブページを特定する。関連するウェブページを高速に特定する為に、検索エンジン・サービスはウェブページに対するキーワードのマッピングを保持する。このマッピングは、ウェブ(すなわち、ワールドワイドウェブ)を“這う（crawling）”ことによって生成され、各ウェブページのキーワードが特定される。ウェブを這うために、検索エンジン・サービスは、ルートウェブページのリストを利用しており、これらのルートウェブページを介してアクセス可能なウェブページの全てが特定される。様々な既知の情報検索技術を使用して、いかなる特定のウェブページのキーワードも特定することができ、見出しの単語、ウェブページのメタデータ内にある単語、強調表示された言葉等が特定されている。検索エンジン・サービスは、ウェブページのキーワードがクエリの単語にどの程度合致するかという事に基づいて、検索要求に関連し得るウェブページを特定する。そして、検索エンジン・サービスは特定されたウェブページへのリンクをユーザに表示し、その表示は、クエリ、人気度、重要度、及び/又はある他の指標とそれらとの関連度で判定された順位に基づいた順序でなされる。
【０００３】
ウェブページを順位付ける３つの既知の技術が、PageRank、HITS(“Hyperlinked-lnduced Topic Search”)、及びDirectHITである。PageRankは、ウェブページが重要度の高いウェブページへのリンク（即ち、“発信リンク”）を有しているという原理に基づいている。したがって、ウェブページの重要度は、そのウェブページ（即ち、“受信リンク”）に接続する他のウェブページの数と重要度に基づいている。単純な形態においては、ウェブページ間のリンクは隣接行列Aによって表される。Aijはウェブページiからウェブページjまでの発信リンクの数を表している。ウェブページjに対する重要度得点wjは以下の方程式で表される。
【０００４】
【数１】
2009528628.tif 000003
【０００５】
以下の方程式に基づく反復計算によって、この方程式を解くことができる。
【０００６】
【数２】
2009528628.tif 000004
【０００７】
ここで、wは、ウェブページの重要度得点のベクトルであり、且つＡTの主固有ベクトルである。
【０００８】
HITS技術は、他の重要度の高いウェブページに多くのリンク有するウェブページ自体の重要度が高いという原理に、更に基づいている。従って、HITSは、複数のウェブページの「重要度」を2つの関連する帰属、「hub」と「authority」に分割している。「hub」は１つのウェブページがリンクする複数のウェブページの「authority」得点によって測定され、「authority」はウェブページにリンクされる複数のウェブページの「hub」得点によって測定される。クエリとは無関係にウェブページの重要度を算出するPageRankとは対照的に、HITSは、結果のウェブページと、受信リンク及び発信リンクによって結果のウェブページに関連付けられたウェブページと、に基づいて重要度を算出する。HITSは、検索エンジン・サービスにクエリを送信し、ウェブページの初期設定として結果のウェブページを利用する。HITSは、受信リンクの目的地であるウェブページ及び結果のウェブページの発信リンクのソースであるウェブページに設定を加える。HITSは、反復アルゴリズムを使用して、各ウェブページの「hub」と「authority」得点を算出する。「hub」と「authority」得点は、以下の方程式によって表される。
【０００９】
【数３】
2009528628.tif 000005
【００１０】
ここで、ａ(p)はウェブページpの「authority」得点を表し、h(p)はウェブページpの「hub」得点を表している。HITSは、リンクを表すために隣接行列Aを利用している。隣接行列は以下の方程式により表される。
【００１１】
【数４】
2009528628.tif 000006
【００１２】
ベクトルaとhの各々は、設定中の全ウェブページのauthority得点とhub得点に対応し、次式で表される。
【００１３】
【数５】
2009528628.tif 000007
【００１４】
従って、aとhはマトリクスATAとAATの固有ベクトルである。また、HITSは、訪問数によって測定されるように、ウェブページの人気度の要素に変更されてもよい。クリックスルーデータの分析に基づいて、ユーザがウェブページiからウェブページjに移る場合はいつでも、隣接行列bijは増大され得る。
【００１５】
DirectHITは、同様のクエリの結果を有する過去のユーザ履歴に基づいて、ウェブページを順位付ける。例えば、同様のクエリを送信するユーザが、結果の第3ウェブページを最初に選択した場合、このユーザ履歴は、第3ウェブページがより高く順位付けされるべきであるということを示すものであろう。別の例としては、同様のクエリを送信するユーザが、結果の第4ウェブページを見るのに最も多くの時間を通常費やす場合、このユーザ履歴は第4ウェブページが、より高く順位付けされるべきであるということを示すものであろう。DirectHITにおいて、クイックスルーデータの分析からユーザ履歴が導き出される。
【００１６】
クエリと、ページを表す特徴ベクトルと、各クエリに対しては各ページに対する順位と、を含む学習データから順位関数を学習する機械学習アルゴリズムが、いくつかの順位付け技術において利用されている。順位関数は1ページの特徴から任意のクエリの順位に至るまでのマッピングとして機能する。順位関数の学習は、数字の順位の秩序化された一組の一部分に対する特徴ベクトルのマッピングを学ぶ回帰問題として考えられている。回帰ベースのいくつかの技術においては、ページを順位付けるのに利用される絶対関連度得点が与えられる。しかしながら、順位関数により、絶対関連度得点が与えられる必要はないが、むしろページの相対的な順位付けが与えられる必要がある。このように、これらの回帰ベースの技術により、必要とされるよりも困難な問題が解決される。
【００１７】
【非特許文献１】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
【発明の開示】
【発明が解決しようとする課題】
【００１８】
順位関数を求めるための機械的学習アルゴリズムは、学習データとしてクエリ、特徴ベクトル、及びユーザラベルの関連度得点を利用している。学習データを生成するためには、複数のクエリは、検索結果のページを生成するサーチエンジンに送信されてもよい。そして、アルゴリズムは、ページの特徴ベクトルを生成して、各ページの関連度得点をユーザから入力する。そのような手法における困難性は、サーチエンジンが検索結果として何百ページをも返信することにある。検索結果のすべてのページに対しユーザラベルを有することは、かなりコスト高となる。その上、ユーザがそのような多くのページの関連度を正確に評価するのは、難しい場合がある。ユーザは少数のページだけにラベルを付することができるが、そのような少数部分に基づく学習によっては、正確な順位関数が与えられない。
【課題を解決するための手段】
【００１９】
クエリに対してラベルが付されたドキュメントの関連度を、ラベルが付されていないドキュメントに伝播する方法とシステムを提供する。伝播システムは、クエリと、クエリに対する関連度によってラベルが付されたドキュメントと、ラベルなしのドキュメントと、を含む学習データを与える。伝播システムは学習データ内のドキュメントの複数対の間における類似度を算出する。伝播システムはラベル付きのドキュメントの関連度を同様であるもののラベルが付されていないドキュメントに伝播する。ラベルが解に収束するまで、伝播システムはドキュメントのラベルを反復して伝播してもよい。伝播された関連度を有する学習データは、順位関数を訓練するのに使用される。
【００２０】
本概要は、概念の中から１の選択を詳細な説明内でさらに記載される単純化された形態に取り入れるために与えられたものである。本概要によって請求項に記載された対象の重要な特徴又は本質的な特徴を特定することを意図しておらず、また、請求項に記載された対象の範囲を決定する際の補助として用いることを意図していない。
【発明を実施するための最良の形態】
【００２１】
クエリに対してラベルが付されたドキュメントの関連度をラベルが付されていないドキュメントに伝播する方法とシステムを提供する。一実施例では、伝播システムは、クエリと、クエリに対する関連度によってラベルが付された(特徴ベクトルによって表された)ドキュメントと、ラベルが付されていないドキュメントと、を含む学習データを与える。例えば、伝播システムは、サーチエンジンにクエリを送信し、且つドキュメント(例えば、ウェブページ)として検索結果を利用してもよい。伝播システムは、ユーザがクエリに対する関連度に基づいて検索結果のいくつかのドキュメントにラベルを付するように入力を指示してもよい。伝播システムは学習データ内の複数のドキュメントの複数組の類似度を算定する。例えば、伝播システムは、各ドキュメントを特徴ベクトルによって表してもよいし、特徴空間内のユークリッド距離に基づいて若しくはコサイン類似度距離に基づいて、複数ドキュメント間の類似度を算定してもよい。伝播システムは、ラベルが付されたドキュメントの関連度を、同様であるもののラベルが付されていないドキュメントに伝播する。ラベルが解に収束するまで、伝播システムはドキュメントのラベルを繰り返して伝播してもよい。伝播された関連度を伴う学習データを、順位関数を訓練するのに利用することが可能である。このように、伝播システムは、複数ドキュメント間の類似度に基づいて付加学習データを含む学習データを自動的に増強させることができる。
【００２２】
一実施例では、伝播システムは、１つのドキュメントを表すノードの各々と、接続されたノードによって表された複数ドキュメント間の類似度を表すエッジの各々と、を有するドキュメントグラフを使用してドキュメントを表す。伝播システムは、各ドキュメントに対する行と列を有する正方行列としてグラフを表してもよく、グラフにおいては、ゼロでない値は、行のノードと列のノードとの間のエッジを示している。伝播システムは、様々な技術を使用してグラフに対してエッジを定義してもよい。例えば、伝播システムは、グラフが完全に接続されているとみなし、その場合においては、ノードの各々は他のあらゆるノードに対して1つのエッジを有している。別の実施例としては、伝播システムは、複数のノードが最小のスパニングツリーを介して接続されるとみなしてもよい。一実施例では、伝播システムは、ノードがk-最近接アルゴリズムを使用して接続されるとみなす。特に、伝播システムは、各ノードに対するk-最近接ノードを特定し、且つそのノードからk-最近接ノードの各々にエッジを加える。伝播システムは、接続されたエッジによって表されたドキュメント間の類似度に基づいて、エッジに重みを計算する。伝播システムは、ドキュメント間の類似度を判定するのに様々な技術を使用してもよい。一実施例では、伝播システムは、特徴空間内のドキュメントの特徴ベクトル表現に基づいてユークリッド距離メトリックを利用している。伝播システムは、類似度若しくは親和性行列をもたらす正方行列の値として類似度を記憶する。また、伝播システムは類似マトリクスを正規化してもよい。また、伝播システムは、関連度を伝播する間において自己補強を防ぐため対角値を0に設定してもよい。
【００２３】
類似マトリクスを生成した後、伝播システムは、多様順位付けベースの伝搬アルゴリズムを使用して、ラベルが付されたドキュメントの関連性をラベルが付されていないドキュメントに伝播する。多様順位付けベースの伝搬アルゴリズムは、非特許文献１に開示されている。伝播システムは、ユーザ及びラベルなしドキュメントの関連度によって与えられた関連度得点に対してラベルが付されたドキュメントの関連度を初期において０に設定する。そして、伝播システムは、類似マトリクスで示したように、類似度で因数分解されるそれらの接続ラベルされていないドキュメントにラベル付きのドキュメントの関連度を拡張する。関連度得点が解に収束するまで、伝播システムは関連度得点を繰り返して拡張する。ラベルが付されていないドキュメントの関連度得点の結果は、それらが、ラベルが付されたドキュメントと同一のクエリに関連する確率に比例するであろう。高い関連度得点を有する多くのラベルが付されたドキュメントと類似するラベルが付されていないドキュメントの関連度得点は高いであろう。逆に、ラベルが付されたいかなるドキュメントとは全く類似しないラベルが付されていないドキュメントの関連度得点は低いであろう。
【００２４】
伝播システムは、以下の方程式で表されるラプラスカーネルを使用して類似度を表してもよい。
【００２５】
【数６】
2009528628.tif 000008
【００２６】
xilとxjlのそれぞれは、xiとxjのｌ次の次元を表しており、tは特徴空間の次元性を表し、σlは類似度計算における異なる次元の重みを反映している正のパラメータを表している。したがって、伝播システムは以下の方程式によりエッジの重みを表す。
【００２７】
【数７】
2009528628.tif 000009
【００２８】
Wijはドキュメントi及びjの間の類似度を表している。伝播システムは定係数1/2σlを省略してもよい。類似マトリクスWにおけるその効果がマトリクスの正規化によって打ち消されるからである。伝播システムは以下の方程式で表されるように類似マトリクスを正規化する。
【００２９】
【数８】
2009528628.tif 000010
【００３０】
ここで、Sは正規化された類似マトリクスを表し、Dは対角行列を表しており、 (i, i)は類似マトリクスWのi番目の行の合計に等しい。正規化によって、接続された複数ドキュメントの類似度に関連すべき類似度が正規化される。
【００３１】
伝播システムはユークリッド空間内の点を形成するt次元の特徴ベクトルxとして各ドキュメントを表してもよい。クエリに対して、伝播システムは、ドキュメントχ={xl1,xl2 …xlm, xu1,xu2…xum}の結果セットを受信する。 (特徴空間の)最初のm点はユーザラベルのドキュメントを表し、(特徴空間の)最後のn点(特徴空間の)がラベルされていないドキュメントを表している。伝播システムはさらに対応するラベルベクトルγ=[yl1,yl2,…ylm, 0, ,0 …0]Tを受信する。最後のnは、ラベルなしドキュメントを表す0の値を有している。さらに、伝播システムによって、関連度の否定的標本を表すために、肯定的ラベルだけというよりも、むしろ否定的ラベルによって指定されてもよい。伝播システムは特徴空間内のドキュメント間の距離をd: χ×χ→□として表しておいり、その距離は点xi及びxjの各ペアを距離d(xi, xj)として指定し且つドキュメントの順位関数をf: χ→□として表しており、その順位関数は点xiの各々に対して順位得点fiを指定している。順位関数学習問題は、特徴X={χq}及びラベルY={γq}を有する一組のクエリからf: χ→□を学習することである。伝播システムは以下の方程式により関連度伝播限界を表している。
f*=(1-α)(I-αS)-1y
ここで、f*が関連度限界を表し、yは初期ラベルを表し、αは減衰係数を表している。正規化された類似マトリクスSの逆マトリクスを計算するのが、計算上困難であるので、伝播システムはテイラー級数展開を使用して近似する。伝播システムは以下の方程式によりテイラー級数展開を表してもよい。
f* = (I-αS)-1y
= (I＋αS＋α2S2＋…)y
= y +αSy +αS(αSy) + …
伝播システムは、f*が解に収束するまで又は一定の反復回数まで、f*を反復して解く。
【００３２】
一旦、関連度が伝播されると、伝播ラベルシステムは、学習データの複数セット(クエリ及びラベルが付された特徴ベクトル)を使用して、順位関数を訓練してもよい。順位関数は、サポートベクトルマシン、適応ブースティング分類器、ニューラルネットワーク分類器等として実装されてもよい。サポートベクトルマシンは、可能な入力の空間内の超曲面を見出すことによって動作する。超曲面によって、肯定的標本及び否定的標本の最近接間の距離を超曲面に対して最大にすることにより、否定的標本から肯定的標本の分離がなされる。これにより、学習データと同様であるものの同一ではないデータの正確な分類がなされる。サポートベクトルマシンを訓練するのに、様々な技術を利用することができる。１技術によれば、連続最小最適化アルゴリズムが利用され、連続最小最適化アルゴリズムにおいては、大なる２次プログラミング問題は、分析的に解決され得る小なる一連の２次プログラミング問題に分解される。(連続的な最小最適化を、http://research.microsoft.com/~iplatt/smo.htmlにおいて参照されたい。)
適応ブースティングとは、収集された学習データに対して多重に検査を実行する反復処理である。適応ブースティングによって、弱学習アルゴリズム(見込みよりもわずかに良いレベルで動作するアルゴリズム)が、強学習アルゴリズム(低誤差率を示すアルゴリズム)に変えられる。弱学習アルゴリズムは学習データの異なったサブセットに対して実行される。アルゴリズムは、その先行アルゴリズムが誤りを示す傾向のあるこれらの標本に、さらに集中する。アルゴリズムは、先の弱学習アルゴリズムによって生成されたエラーを修正する。アルゴリズムは、先行アルゴリズムの誤差率に順応するので、適応型である。適応ブースティングによって、概略的な経験則と中程度に不正確な経験則が結合され、高性能アルゴリズムが形成される。適応ブースティングは、別々に実行された検査の各々の結果を、単一の非常に正確な分類子に結合する。
【００３３】
神経回路網模型は、三大コンポーネント、すなわち、アーキテクチャ、コスト関数、及びサーチアルゴリズムを有している。アーキテクチャは、(ネットワークトポロジー、ユニットの接続性、及び活性化関数に関する)出力に入力を関連付ける関数形式を定義する。目的関数を最小にする1組の重みに対する重み空間での検索が学習処理である。神経回路網模型は、検索技術として、動径基底関数(RBF：radial basis function)ネットワーク及び標準最急降下法（standard gradient descent）を利用してもよい。
【００３４】
図１は、クエリの検索結果として返されたドキュメントのグラフを示すダイヤグラムである。この実施例では、サブグラフ１００は検索結果で返されたドキュメントの一部分を表している。ノード１０１−１１２は検索結果の１２個のドキュメントを表している。ノード１０１と１０６はラベルが付されたドキュメントを表している。ノード１０１によって表されたドキュメントは、．７５の関連度得点を用いてラベルを付されている。ノード１０６によって表されたドキュメントは、．６の関連度得点を用いてラベルを付されている。伝播システムは、最近接アルゴリズムを使用してノード間のエッジを生成した。この実施例では、ノード１０２、１０３、及び１０４の各々はノード１０１に対するｋ―最近接ノードの１つであるが、ノード１０５−１１２はｋ―最近接ノードの１つではない。そして、伝播システムは、類似度得点アルゴリズムを使用して接続されたノード間の類似度を算定した。例えば、ノード１０１は．８の重みを有するエッジでノード１０２に接続されており、その重みは接続されたノード間の類似度を示している。
【００３５】
図２は、一実施例における伝播システムの構成要素を示すブロックダイアグラムである。伝播システム２３０は通信リンク２２０（例えば、インターネット）を介してドキュメント蓄積部２１０（例えば、ウェブサイト）に接続されている。伝播システムは、学習データ集積部２３１と、学習データ蓄積部２３２と、ドキュメントインデックス２３３と含んでいる。ドキュメントインデックスは、ドキュメント蓄積部内のドキュメント（例えば、ウェブページ）のインデックスを含んでいる。ドキュメントインデックスはウェブクローラによって生成されてもよい。ドキュメントインデックスは、順位関数を訓練するのに使用される各ドキュメントの特徴ベクトルを含んでもよい。特徴ベクトルが、ドキュメントの逆頻度、キーワード、フォントサイズ等の多くの異なったタイプのドキュメントを表してもよい。学習データ集積部は、サーチエンジン（図示せず）にクエリを送り、クエリに合致するドキュメントを受信する。サーチエンジンは伝播システムから独立していてもよい。このような場合には、伝播システムが検索結果から特徴ベクトルを動的に生成してもよい。学習データ集積部は、クエリに合致するドキュメントのいくつかの関連度にラベルを付するようにユーザに指示してもよい。学習データ集積部は、クエリ、検索結果（例えば、特徴ベクトル）、及び学習データ蓄積部内のラベルを記憶する。伝播システムは、関連度伝播部２３５、グラフ形成部２３６、グラフ重み生成部２３７、グラフ重み正規化部２３８、及びグラフベース関連度伝播部２３９を含んでいる。関連度伝播部は、学習データ蓄積部内で記憶されているラベルが付されていないドキュメントにラベル付きのドキュメントの関連度を伝播する。関連度伝播部は、検索結果のドキュメントを表すエッジを含むグラフを形成するようにラフ形成部に対して命令する。そして、関連度伝播部は、グラフのエッジに対する最初の重みを生成するようにグラフ重み生成部に対して命令する。関連度伝播部は、生成された重みを正規化するようにグラフ重み正規化部に対して命令する。そして、関連度伝播部は、ラベル付きのドキュメントからラベルされていないドキュメントまで関連度の実際の伝播を実行するようにグラフベース関連度伝播部に対して命令する。また、伝播システムは順位関数生成部２４１と順位関数２４２を含んでいる。順位関数生成部は、順位関数を作成するために、伝播された関連度を有する学習データを使用する。
【００３６】
伝播システムが実装され得るコンピューターデバイスは、中央処理装置、メモリ、入力装置（例えば、キーボードとポインティングデバイス）、出力装置（例えば、表示装置）、および記憶装置（例えば、ディスクドライブ）を含んでもよい。メモリと記憶装置は、伝播システムを実装する指示を含んでもよいコンピュータ読み込み可能なメディアである。さらに、データ構造とメッセージ構造が、通信リンク上の信号等のデータ伝送媒体を介して記憶又は送信されてもよい。インターネット、ローカルエリアネットワーク、広域ネットワーク、又は２地点間回線ダイヤルアップ接続等の様々な通信リンクを利用してもよい。
【００３７】
パーソナルコンピュータ、サーバー・コンピュータ、携帯型若しくはラップトップデバイス、マルチプロセッサシステム、マイクロプロセッサベースシステム、プログラム可能家庭用電化製品、ネットワークＰＣ、ミニコンピュータ、メインフレーム計算機、上記のシステム若しくはデバイスのいずれも含んでいる分散コンピューティング環境等を含む様々なコンピュータシステム等に対して、伝播システムはサービスを提供してもよい。
【００３８】
伝播システムは、1つ以上のコンピュータ又は他の装置によって実行されたプログラムモジュール等のコンピュータ実行ファイル指示の一般的内容において説明されてもよい。一般に、プログラムモジュールは、特定のタスクを実行するか若しくは特定の抽象データタイプを実装するルーチン、プログラム、オブジェクト、コンポーネント、データ構造等を含んでいる。典型的には、プログラムモジュールの機能性を、種々の実施例において所望に応じて結合又は分配してもよい。
【００３９】
図３は、一実施例の伝播システムの順位関数生成部の処理を示すフローチャートである。順位関数生成部は、学習データを収集し、ラベル付きのドキュメントの関連度をラベルが付されていないドキュメントに伝播して、順位関数を訓練する。ブロック３０１では、順位関数生成部は学習データを収集する。ブロック３０２では、順位関数生成部は学習データのサブセットに対してラベルを入力する。ブロック３０３では、順位関数生成部は、ラベル付きのドキュメントの関連度をラベルされていないドキュメントに伝播するように関連度伝播部に対して命令する。ブロック３０４では、順位関数生成部は、伝播された関連度を利用して順位関数を訓練する。
【００４０】
図４は、一実施例の伝播システムの関連度伝播部の処理を示すフローチャートである。関連度伝播部は、ラベルが付されていないドキュメントに学習データを与え且つラベル付きのドキュメントの関連度をラベルされていないドキュメントに伝播する。ブロック４０１では、関連度伝播部は、エッジを含んだ初期のグラフを形成するようにグラフ形成部に対して命令する。ブロック４０２では、関連度伝播部は、接続されたノードによって表されたドキュメント間の類似度を示す重みを生成するようにグラフ重み生成部に対して命令する。ブロック４０３では、関連度伝播部は、グラフの重みを正規化するようにグラフ重み正規化部に対して命令する。ブロック４０４では、関連度伝播部は、関連度の伝播を実行するようにグラフベース関連度伝播部に対して命令する。そして、関連度伝播部は元に戻る。
【００４１】
図５は、一実施例における伝播システムのグラフ形成部の処理を示すフローチャートである。グラフ形成部はドキュメントを表す行と列の各々を有する正方行列を生成する。次に、グラフ形成部は、各ノードとそのｋ−最近接（例えば、ｋ＝１０）ノードとの間の接続を特定且つ加える。ブロック５０１では、グラフ形成部は次のドキュメントｉを選択する。決定ブロック５０２では、すべてのドキュメントｉが既に選択されたならば、グラフ形成部は元に戻り、さもなければ、グラフ形成部はブロック５０３に継続する。ブロック５０３では、グラフ形成部は次のドキュメントｊを選択する。決定ブロック５０４では、選択されたドキュメントｉに対するすべてのドキュメントｊが既に選択されたならば、グラフ形成部はブロック５０６に継続し、さもなければ、グラフ形成部はブロック５０５に継続する。ブロック５０５では、グラフ形成部は、選択されたドキュメントｉと選択されたドキュメントｊとの間の距離を計算して、ブロック５０３にループして、次のドキュメントｊを選択する。ブロック５０６では、グラフ形成部は、ドキュメントｉ（すなわち、最近接）に対して最小距離を有する１０個のドキュメントｊを選択して、ブロック５０１にループして次のドキュメントｉを選択する。
【００４２】
図６は、一実施例における伝播システムのグラフ重み生成部の処理を示すフローチャートである。グラフ重み生成部は、マンハッタンメトリック（Ｍａｎｈａｔｔａｎ  ｍｅｔｒｉｃ）に基づいて、接続されたドキュメント間の類似度について計算する。ブロック６０１では、グラフ重み生成部は次のドキュメントｉを選択する。決定ブロック６０２では、すべてのドキュメントｉが既に選択されたならば、グラフ重み生成部は元に戻り、さもなければ、グラフ重み生成部はブロック６０３に継続する。ブロック６０３では、グラフ重み生成部はそれ自身に対するドキュメントの類似度を０に初期化する。ブロック６０４では、グラフ重み生成部は、選択されたドキュメントｉに対する次近接ドキュメントｊ（すなわち、接続されたドキュメント）を選択する。決定ブロック６０５では、選択されたドキュメントｉに対するすべての最近接ドキュメントｊが既に選択されたならば、グラフ重み生成部は、ブロック６０１にループして、次のドキュメントｉを選択し、さもなければ、グラフ重み生成部はブロック６０６に継続する。ブロック６０６では、グラフ重み生成部は選択されたドキュメントｉと選択されたドキュメントｊとの間の類似度を１に初期化する。ブロック６０７−６０９では、グラフ重み生成部は、距離を計算しながら、ループする。ブロック６０７では、グラフ重み生成部は特徴ベクトルの次のディメンションｌを選択する。決定ブロック６０８では、すべてのディメンションが既に選択されたならば、グラフ重み生成部は、ブロック６０４にループして、次近接ドキュメントｊを選択し、さもなければ、コンポーネントはブロック６０９に継続する。ブロック６０９では、グラフ重み生成部は、選択されたドキュメントｉと選択されたドキュメントｊとの間の類似度を、数式２によって、選択されたドキュメントｉの選択された特徴ｌと選択されたドキュメントｊとの間の差の関数によって乗ぜられた最新の類似度に設定する。そして、グラフ重み生成部は、ブロック６０７にループして、次のディメンションを選択する。
【００４３】
図７は、一実施例における伝播システムのグラフ重み正規化部の処理を示すフローチャートである。グラフ重み正規化部は類似マトリクスの重みを正規化する。ブロック７０１では、グラフ重み正規化部は類似マトリクスの次の行ｉを選択する。決定ブロック７０２では、すべての列が既に選択されたならば、グラフ重み正規化部はブロック７０６に継続し、さもなければ、グラフ重み正規化部はブロック７０３に継続する。ブロック７０３−７０５では、グラフ重み正規化部は選択された行に対する対角行列Ｄの値を計算する。ブロック７０３では、グラフ重み正規化部は類似マトリクスの次の列ｊを選択する。決定ブロック７０４では、すべての列が既に選択されているならば、グラフ重み正規化部はブロック７０１にループして、次の行を選択し、さもなければ、グラフ重み正規化部はブロック７０５に継続する。ブロック７０５では、グラフ重み正規化部は選択された行ｉの重み及び選択された列ｊを選択された行ｉの対角要素に加算する。そして、グラフ重み正規化部はブロック７０３にループして、選択された行ｉに対する次の列ｊを選択する。ブロック７０６では、グラフ重み正規化部は方程式３に従って類似マトリクスを正規化する。
【００４４】
図８は、一実施例における伝播システムのグラフベース関連度伝播部の処理を示すフローチャートである。グラフベース関連度伝播部は、方程式５のテイラー級数展開が解に収束するまで、方程式５のテイラー級数展開を繰り返して計算する。ブロック８０１では、グラフベース関連度伝播部はインデックスｉをゼロに初期化する。ブロック８０２では、グラフベース関連度伝播部は解ベクトルを０に初期化する。ブロック８０３−８０５では、グラフベース関連度伝播部は、それが解に収束するまで、ループする。ブロック８０３では、グラフベース関連度伝播部は、先の反復値とテイラー級数展開の次の因数に基づいて、次の反復値を計算する。決定ブロック８０４では、その値が解に収束するならば、グラフベース関連度伝播部は戻り、さもなければ、グラフベース関連度伝播部はブロック８０５に継続する。ブロック８０５では、グラフベース関連度伝播部は、次の反復に対してインデックスを増加させ、且つブロック８０３にループして次の反復を実行する。
【００４５】
対象を構造的特徴及び／又は方法論的に特有の言語で説明したが、添付した請求項において定義された対象は上記の特有の特徴又は機能に必ずしも限定されないという事を理解すべきである。むしろ、上記の特有の特徴又は機能は請求項を利用する例示的形態として開示されている。伝播システムは、検索結果を増大させるのに使用されてもよい。例えば、サーチエンジンは、ドキュメントの特定コーパスに基づいて、検索結果を生成してもよい。伝播システムを使用して、検索結果のドキュメントの関連度は異なったコーパスのドキュメントに伝播され得る。そして、最も関連度が高いを有する異なるコーパスのドキュメントが、検索結果に加えられ得る。伝播システムは、単一のクエリに対する関連度によってラベルが付されたドキュメントからラベルなしドキュメントに（クエリ内伝播）、又は、複数のクエリに対する関連度によってラベルが付されたドキュメントからラベルなしドキュメントに（クエリ間伝播）関連度を伝播するのに利用されてもよい。伝播部が、クエリ内伝播のクエリの各々に対して別々に学習部を訓練し、クエリ間伝播の複数クエリに対しては一斉に学習部を訓練する。従って、本発明は添付の請求項以外に限定されない。
【図面の簡単な説明】
【００４６】
【図１】ドキュメントのグラフの一部分を示すダイヤグラムである。
【図２】一実施例における伝播システムのコンポーネントを示すブロックダイアグラムである。
【図３】一実施例における伝播システムの順位関数生成部の処理を示すフローチャートである。
【図４】一実施例における伝播システムの関連度伝播部の処理を示すフローチャートである。
【図５】一実施例における伝播システムのグラフ形成部の処理を示すフローチャートである。
【図６】一実施例における伝播システムのグラフ重み生成部の処理を示すフローチャートである。
【図７】一実施例における伝播システムのグラフ重み正規化部の処理を示すフローチャートである。
【図８】一実施例における伝播システムのグラフベース関連度伝播部の処理を示すフローチャートである。
【図１】
2009528628.tif 000011
【図２】
2009528628.tif 000012
【図３】
2009528628.tif 000013
【図４】
2009528628.tif 000014
【図５】
2009528628.tif 000015
【図６】
2009528628.tif 000016
【図７】
2009528628.tif 000017
【図８】
2009528628.tif 000018
【国際調査報告】
2009528628.tif 000019
2009528628.tif 000020
2009528628.tif 000021