(57)【特許請求の範囲】
【請求項１】
コンピュータによって推薦タスクを実行するための方法において、
メモリが、ソーシャルメディアネットワークのソーシャルメディアデータモデルを表すリレーショナルグラフと、インスタンス生成されたソーシャルメディアデータとを記憶することと、
リレーショナルグラフ展開モジュールが、リレーショナルグラフに少なくとも一部基づいて、インスタンス生成されたソーシャルメディアデータを同時生起行列に展開することによって展開されたリレーショナルグラフを決定することと、
一般的なランダムウォーク生成器が、推薦タスク及び展開されたリレーショナルグラフに少なくとも一部基づいてランダムウォークモデルを生成することと、
重み付けランダムウォーク生成器が、ランダムウォークモデル及び重み付け値に基づいて重み付けランダムウォークモデルを生成することと、
学習モジュールが、ランダムウォークモデルについての定常分布を近似することと、訓練事例と連動して損失関数の最小化を使用することによって定常分布を最適化することとによって重み付け値を決定し、メモリ制限ブロイデン・フレッチャー・ゴールドファーブ・シャンノＢＦＧＳ（Ｌ−ＢＦＧＳ）法を使用して重み付け値を決定することと、
ソーシャルメディア選択モジュールが、重み付けランダムウォークモデルにおいてランダムウォークを実行し、ランダムウォークに少なくとも一部基づいて推薦を出力することとを備える、方法。
【請求項２】
ランダムウォークモデルを生成することが、リレーショナルグラフを、定常分布及び状態遷移確率の組を備えるマルコフ連鎖に変換することを備える、請求項１記載の方法。
【請求項３】
ソーシャルメディアネットワークが、エンティティ間で定義されたリレーションを有するエンティティを備える相互に接続された電子ネットワーク構造である、請求項１記載の方法。
【請求項４】
推薦タスクを実行するためのシステムにおいて、
ソーシャルメディアネットワークのソーシャルメディアデータモデルを表すリレーショナルグラフと、インスタンス生成されたソーシャルメディアデータとを記憶するメモリと、
リレーショナルグラフに少なくとも一部基づいて、インスタンス生成されたソーシャルメディアデータを同時生起行列に展開することによって展開されたリレーショナルグラフを決定するように構成されたリレーショナルグラフ展開モジュールと、
推薦タスク及び展開されたリレーショナルグラフに少なくとも一部基づいてランダムウォークモデルを生成するように構成された一般的なランダムウォーク生成器と、
ランダムウォークモデル及び重み付け値に基づいて重み付けランダムウォークモデルを生成するように構成された重み付けランダムウォーク生成器と、
ランダムウォークモデルについての定常分布を近似することと、訓練事例と連動して損失関数の最小化を使用することによって定常分布を最適化することとによって重み付け値を決定するように構成された学習モジュールであって、メモリ制限ブロイデン・フレッチャー・ゴールドファーブ・シャンノＢＦＧＳ（Ｌ−ＢＦＧＳ）法を使用して重み付け値を決定する重み学習モジュールと、
重み付けランダムウォークモデルにおいてランダムウォークを実行し、ランダムウォークに少なくとも一部基づいて推薦を出力するように構成されたソーシャルメディア選択モジュールとを備える、システム。
【発明の詳細な説明】
【技術分野】
【０００１】
以下は、ソーシャルネットワーク等のマルチリレーショナル環境において項目を推薦するためのシステム及び方法に関する。ソーシャルネットワークは、ソーシャルネットワークに属するエンティティが１つ以上のリレーションによってリンクされたリレーショナルグラフとして論理的に表される。
【背景技術】
【０００２】
メディア共有サイトＦｌｉｃｋｒ及びＹｏｕＴｕｂｅ等の大きなソーシャルメディアネットワークは、多くのユーザ（例えば数百万人）によってアップロードされて注釈が付けられた多くの画像及びビデオ（例えば数十億）を含む。ソーシャルネットワーク内のメディアオブジェクト（画像及びビデオ等）のタグ付けする能力は、メディア共有及び検索機能を改善する強力なメカニズムである。そのようなソーシャルネットワークにおいて、タグは、関連するメディアオブジェクトについてのメタデータの役割を担う。しかしながら、これらのタグは、多くの場合、オブジェクトにおける同定及びタグ付けのために均一で一貫性のある手順よりはむしろメディアオブジェクトの個々のユーザのユニークな知覚を反映した自由形式で提供される。タグ付けにおける均一性の欠乏は、検索者及びタグ付与者が異なる専門用語を使用することがあるため、タグに基づく検索の有効性を低減する可能性がある。この自由な個々の選択にもかかわらず、人々が所定のメディアオブジェクト又は一群のオブジェクトの意味記述について同意するとき、いくつかの共通使用トピックが現れる。
【０００３】
Ｆｌｉｃｋｒ及びＹｏｕＴｕｂｅ等のメディア共有サイトの場合、サイトにおいて注釈が付けられてタグが付けられた大量のオブジェクトは、新規及び既存のメディアオブジェクトについてのタグを提案するための基礎を形成する。推薦システムは、特に、ブートストラップ及びクエリーモードにおいて有益である。ブートストラップモードにおいて、推薦システムは、新たにアップロードされたオブジェクトについて最も関連のあるタグを提案する。クエリーモードにおいて、画像に注釈を付けているユーザは、既存の画像タグを強化することができる推薦されたタグが提示される。双方のモードは、ユーザのための注釈付けタスクを容易とすることができ、画像に注釈を付けているタグの範囲を拡大するのに役立つことができる。
【０００４】
より広い意味において、ソーシャルネットワークサイトにおける活動は、多くの場合、様々なエンティティ型（例えば「エンティティ」）及びそれらの間の関係（リレーション）を含む多次元に沿って及ぶ。それゆえに、タグ推薦は、他のソーシャルネットワークオブジェクトのメタデータに基づいてソーシャルネットワーキングサイトのユーザに対してデータを推薦する多くの可能なシナリオのうちの単に１つにすぎない。例えば、他の推薦シナリオは、ユーザについてのコンタクト又はグループの推薦、グループについての画像を推薦等と関係してもよい。これらの推薦は、ソーシャルネットワークにおけるエンティティ間の複数の関係に基づいて提供されてもよい。したがって、所定の推薦タスクのために、エンティティのどのリレーションが推薦タスクと関連しているか、及び、どのようにしてリレーションが最適な方法で項目を推薦するのに使用されるかについて知ることが望ましい。
【発明の概要】
【０００５】
典型的な実施形態の１つの態様によれば、既存のタグをソーシャルメディアエンティティインスタンスと関連付けるためにソーシャルネットワークのユーザに対する推薦を行うための方法が提供される。本方法は、ソーシャルネットワークの少なくとも一部についてのソーシャルメディアエンティティインスタンスを含むランダムウォークモデルを生成することと、ランダムウォークモデルについての重み付け値を決定することと、ランダムウォークモデル及び重み付け値に基づいて重み付けランダムウォークモデルを生成することと、ソーシャルメディアエンティティインスタンスから始めて重み付けランダムウォークモデルにおいてランダムウォークを実行することと、ランダムウォークに基づいてユーザに対して既存のタグを推薦することとを含む。
【０００６】
他の態様において、推薦タスクを実行するためのシステムが提供される。システムは、ソーシャルメディアネットワークのソーシャルメディアデータモデルとインスタンス生成されたソーシャルメディアデータとを表すリレーショナルグラフを記憶するためのメモリを含む。システムはまた、リレーショナルグラフに少なくとも一部基づいてインスタンス生成されたソーシャルメディアデータを同時生起行列に展開することによって展開されたリレーショナルグラフを決定するように構成されたリレーショナルグラフ展開モジュールと、推薦タスク及び展開されたリレーショナルグラフに少なくとも一部基づいてランダムウォークモデルを生成するように構成された一般的なランダムウォーク生成器と、ランダムウォークモデル及び重み付け値に基づいて重み付けランダムウォークモデルを生成する重み付けランダムウォーク生成器と、重み付けランダムウォークモデルにおいてランダムウォークを実行し、ランダムウォークに少なくとも一部基づいて推薦を出力するように構成されたソーシャルメディア選択モジュールとを含む。
【０００７】
さらに他の態様において、Ｓにわたる初期分布Ｐ０によって規定される状態Ｓの組にわたるマルコフ連鎖及び状態遷移確率
【数１】
0005789204.tif 000002
の組を決定することにより、推薦タスクに少なくとも一部基づいてソーシャルメディアデータモデルについてのランダムウォークモデルを生成し、ランダムウォークモデルについての重み付け値を学習し、ランダムウォークモデル及び学習された重み付け値に基づいて重み付けランダムウォークモデルを生成し、１つ以上の推薦を生成するように重み付けランダムウォークモデルにおいてランダムウォークを実行するように構成されたプロセッサを含む、推薦タスクを実行するための装置が提供される。マルコフ連鎖状態遷移確率は、初期状態分布Ｐ０にしたがって確率α＞０によってリセットされ、定常分布πは、以下として定義される。
【数２】
0005789204.tif 000003
【図面の簡単な説明】
【０００８】
【図１】図１は、ソーシャルメディアデータモデルを表すリレーショナルグラフの概略図である。
【図２】図２は、マルチリレーショナル環境において項目を推薦するためのシステムを図示している。
【図３】図３は、タグが付けられることになる画像に関する簡略化した重み付けランダムウォークモデルを図示している。
【図４】図４は、図２のシステムにおいて実行されてもよいマルチリレーショナル環境において項目を推薦するための方法を図示しているフローチャートである。
【図５】図５は、典型的な方法及びシステムの評価からの結果を、グラフを用いて図示している。
【図６】図６は、典型的な方法及びシステムの評価からの結果を、グラフを用いて図示している。
【図７】図７は、典型的な方法及びシステムの評価からの結果を、グラフを用いて図示している。
【図８】図８は、典型的な方法及びシステムの評価からの結果を、グラフを用いて図示している。
【図９】図９は、典型的な方法及びシステムの評価からの結果を、グラフを用いて図示している。
【発明を実施するための形態】
【０００９】
ソーシャルネットワーク等のマルチリレーショナル環境において項目を推薦するためのシステム及び方法が本願明細書において開示される。このために、典型的な実施形態は、多くの異なるエンティティ及びそれらの間のリレーションを統合し、異なる推薦タスクについてのデータモデルを構築するためにリレーションを使用し、所定の推薦タスクに対する各リレーションの最適な寄与を見出すことができるマルチリレーショナルフレームワークに関する。ソーシャルネットワークは、本願明細書では、ノードの特性に基づいてノード間で関係（リレーション）を有するノード（エンティティ）から構成された相互に接続された電子ネットワーク構造をいう。例えば、ソーシャルネットワークは、人々、グループ、機関、動物、コンピュータ、メディアオブジェクト（視聴覚作品又は画像等）、メタデータ要素（コメント又はタグ等）等の電子的表現物間における関係を表してもよい。
【００１０】
ソーシャルネットワーク等のマルチリレーショナル設定において、同じ又は異なる型のエンティティは、複数のリレーションを形成するように接続される。ネットワークにおける各リレーションは、単一型エッジ（ユーザ−ユーザ間のように、同じ型のエンティティについて）又は双部分エッジ（ユーザ−画像のように、異なる型のエンティティについて）によって表されてもよい。典型的なシステム及び方法において、ソーシャルネットワークを形成するエンティティ及びリレーションは、１つの特定のソーシャルネットワークに限定されず、複数のソーシャルネットワークからエンティティを統合してもよい。１つの実施形態において、別個のソーシャルネットワークからの個人プロフィール及びデータは、共通のエンティティ（共通の個人認証情報等）を介して接続される。例えば、いくつかのソーシャルネットワーキングサイト（Ｆａｃｅｂｏｏｋ（登録商標）、ＭｙＳｐａｃｅ（登録商標）、Ｇｏｏｇｌｅ  Ｆｒｉｅｎｄ  Ｃｏｎｎｅｃｔ（登録商標）等）は、ソーシャルネットワークコネクタを介してプラットホームにわたって共通のユーザを決定するのを許容するアプリケーションプログラミングインタフェース（ＡＰＩ）を提供する。いくつかの実施形態において、公然とアクセス可能なデータ（Ｄｅｌｉｃｉｏｕｓソーシャルネットワークにおけるページ推薦及びＴｗｉｔｔｅｒにおける関連ツイート等）は、統合されたソーシャルネットワークを構築するのに使用される。説明のために、ソーシャルメディアサイトＦｌｉｃｋｒがソーシャルメディア共有システムの例として使用される。Ｆｌｉｃｋｒは、同じ又は他のユーザによってアップロードされた画像にユーザがタグ付け及びコメントするのを許容するソーシャルメディアサイトである。ユーザ自身は、他のユーザに対して論理的に接続されてもよく、又は、グループのメンバーであってもよい。
【００１１】
本願明細書では、推薦タスクは、ネットワークにおける第２のエンティティのインスタンスについてのソーシャルネットワークにおける１つのエンティティの１つ以上のインスタンスの推薦と関係する。第１及び第２のエンティティは、同じ型からなってもよく、異なる型からなってもよい。例えば、推薦タスクは、画像についてタグを推薦すること、ユーザについてコンタクト若しくはグループを推薦すること、又は、ユーザについてユーザを推薦することを含んでもよい。さらに、本願明細書では、「エンティティ」は、データがそれについて記憶されることができる単一のオブジェクトの表現であり、エンティティのインスタンスは、エンティティの単一の発生である。例えば、ソーシャルネットワークは、「ユーザ」エンティティを有してもよい。ここで、ユーザエンティティのインスタンスは、「ボブ・ジョーンズ」である。この目的を達成するために、「インスタンス生成された」ソーシャルメディアデータは、１つ以上のソーシャルメディアデータインスタンスの集合をいう。
【００１２】
高いレベルにおいて、所定の推薦タスクのために、典型的な実施形態は、ソーシャルネットワークモデルを表すリレーショナルグラフを取得する。ソーシャルネットワークモデルは、単一のソーシャルネットワークのモデルであってもよく、又は、複数のソーシャルネットワークモデルの統合であってもよい。ソーシャルネットワークモデルを表すリレーショナルグラフは、ソーシャルネットワークモデルにおける２つのエンティティ間の各リレーションの強さが２つのエンティティの間におけるランダムウォークに依存するマルコフ連鎖に変換される。この変換を実行するために、リレーショナルグラフに関するソーシャルネットワークデータのインスタンス化とともに、リレーショナルグラフは、予め注釈が付けられた訓練事例に最適化された重み付け平均とその後に組み合わされる同時生起行列（エンティティ間の各リレーションについての１つ）に展開される。そして、ランダムウォークは、推薦の組を取得するために重み付けされて展開された行列に実行される。
【００１３】
図１を参照すると、（Ｆｌｉｃｋｒネットワークのような）ソーシャルメディアデータモデルを表す図示されたリレーショナルグラフ２が示されている。リレーショナルグラフ２は、リレーション６、１０、１４、１８、２０、２２、２６によって接続されたエンティティ４、８、１２、１６、２４を含む。各リレーションは、２つのエンティティがどのように関連があることができるかについて定義する。例えば、ユーザは画像を所有し、したがって、ユーザエンティティ１６は、リレーション「オーナ」２２によって画像エンティティ４とリンクされる。同様に、画像はタグによってタグ付けされてもよく、したがって、画像エンティティ４は、「ｔａｇｇｅｄ＿ｗｉｔｈ」リレーション６によってタグエンティティ８とリンクされる。さらに他の例として、例えばコンタクトとして、２人のユーザがリンクされることができ、これは、「コンタクト」単一型エッジリレーション１８を含むことによって図１のリレーショナルグラフ２において示される。
【００１４】
論理レベルにおいて、リレーショナルグラフ２は、一律にソーシャルネットワークの全てのエンティティ及びリレーションの統合を許容する。数学用語において、リレーショナルグラフ２は、Ｇ＝（Ｅ，Ｒ）として書かれてもよい。ここで、エンティティ型ek
【数３】
0005789204.tif 000004
は、ノードとして表され、エンティティ型ｅｋ及びｅｌ間のリレーションrkl
【数４】
0005789204.tif 000005
は、（型付き）リンクとして表される。ここで留意すべきは、「コンタクト」リレーション１８等の単一型リレーションについてはｋ＝ｌであるということである。しかしながら、インスタンス生成されたとき、ｅｋ及びｅｌは、２つの異なるユーザエンティティインスタンスのインスタンスとしてインスタンス生成される。図１において、図示したリレーショナルグラフ２は、任意の２つのエンティティ型ｅｋ及びｅｌ間の１つのリレーションしか有しない。しかしながら、リレーショナルグラフは、任意の２つのエンティティｅｋ及びｅｌ間の複数のリレーションを有してもよい。さらに、いくつかのエンティティは、許容可能なリレーションを有しなくてもよく、例えば、図１のリレーショナルグラフ２におけるタグエンティティ型８とコメントエンティティ型１２との間にリレーションがない。
【００１５】
リレーショナルグラフにおける各リレーションは、リレーションにおける同値が推薦タスクについて同じ重要性を有する傾向があるという意味で内部的に同種である。任意の所定の推薦タスクについて、異なるリレーションは、所定の推薦タスクと関連して重要性において異なっていてもよい。例えば、画像エンティティ４とタグエンティティ８との間のｔａｇｇｅｄ＿ｗｉｔｈリレーション６は、ユーザエンティティ１６とグループエンティティ２４との間のメンバーリレーション２０よりもタグ推薦タスクに対してより重要であると思われる。
【００１６】
図２は、ソーシャルネットワーク等のマルチリレーショナル環境において所定のエンティティインスタンスと関連することになるエンティティインスタンスを推薦するための典型的なシステム１００を図示している。システム１００は、エンティティインスタンス１０４（特定の画像等）、ソーシャルネットワークモデル１０６、インスタンス生成されたソーシャルメディアデータ１０８（ソーシャルネットワークについての特定のユーザデータ等）、及び、任意にランダムウォークモデルについての予め設定された重み１２３を表すデータを受けるための入力装置１０２を含む非一時的装置である。代わりに、入力１０４、１０６、１０８、１２３は、システム１００自身によって生成されてもよい及び／又はシステム１００に記憶されてもよい。入力する前に、入力１０４、１０６、１０８、１２３は、ディスク、ＲＯＭ若しくはＲＡＭ等の任意の適切な有形記憶媒体に記憶されてもよく、又は、例えばインターネットを介して搬送波の形態でシステム１００に入力されてもよい。入力装置１０２は、モデムリンク、有線若しくは無線通信、ＵＳＢポート、フロッピー若しくはハードディスク受信機、携帯電話の送受信機部分等を含んでもよく、システム１００の他の構成要素と分離され若しくは組み合わせられてもよい。
【００１７】
システム１００は、処理の間、ソーシャルメディアデータ１０４、ソーシャルメディアデータモデル１０６、インスタンス生成されたソーシャルメディアデータ１０８、及び、任意の予め設定された重み１２３の単一のインスタンスを記憶するためのデータメモリ１１２を含む。システム１００のメインメモリ１１４は、リレーショナルグラフ展開モジュール１１８、一般的なランダムウォーク生成器１２０、任意の重み学習モジュール１２２、重み付けランダムウォーク生成器、及び、ソーシャルメディア選択モジュール１２６を含む典型的な方法を実行するための命令１１６を記憶する。当然のことながら、２つのメモリ１１２、１１４は、単一の記憶装置として具体化されてもよく、又は、メモリ１１２、１１４の一方又は双方は、２つ以上の記憶装置構成要素を備えてもよい。命令１１６は、図示されたコンピュータプロセッサ１３６等のディジタルプロセッサ上で適切に実行される。コンピュータプロセッサは、シングルコアプロセッサ、デュアルコアプロセッサ（又は、さらに一般的にいえば複数コアプロセッサ）、ディジタルプロセッサ及び協動する数値演算コプロセッサ、デジタルコントローラによる等、様々に具体化されることができる。モジュール１１８、１２０、１２２、１２４、１２６からの出力は、メモリ１１２、１１４に記憶されてもよく、及び／又は、出力装置１２８を介して、任意にはインターネット等のネットワーク１３２を介して、クライアント端末機１３０に対して出力されてもよい。１つの図示された例において、ユーザは、携帯機器を使用してソーシャルネットワークにアクセスするが、システム１００は、ソーシャルネットワークによって提供されるサービスである。この場合、システム１００は、ソーシャルネットワークをサポートするサーバ（サーバは、分散型又は「クラウド」コンピューティングネットワークであってもよい）に位置し、入力１０２及び出力１２８は、適切には、サーバのインターネットポータルであり、プロセッサ１３６及びメモリ１１２、１１４は、サーバのディジタルプロセッサ（例えば、マイクロプロセッサ又はマイクロプロセッサのパラレルアレイ）及びメモリ構成要素によって適切に具体化され、ネットワーク１３２は、適切には、任意のダウンストリームネットワーク（例えば、携帯電話ネットワーク又はＷｉＦｉネットワーク）とともにインターネットであり、クライアント端末機１３０は、適切には、出力を表示するためのその表示画面を含む携帯機器である。
【００１８】
リレーショナルグラフ展開モジュール１１８は、入力装置１０２を介して、ソーシャルメディアデータモデル１０６及びインスタンス生成されたソーシャルメディアデータ１０８を入力として受信する。上述したように、ソーシャルメディアデータモデル１０６は、図１によって図示されたリレーショナルグラフ２のようなリレーショナルグラフであるか、又は、リレーショナルグラフに変換されてもよい。モジュール１１８は、インスタンス生成されたソーシャルメディアデータ１０８を、ソーシャルメディアリレーショナルグラフによって定義されるエンティティ関係を反映する同時生起行列に（すなわち、展開されたリレーショナルグラフ１１９）に展開する。この展開プロセスは、図４の工程Ｓ１４０に関してより詳細に記載される。
【００１９】
一般的なランダムウォーク生成器１２０は、リレーショナルグラフ展開モジュール１１８によって生成された展開されたリレーショナルグラフ１１９を入力として受信し、ランダムウォークモデル１２１を構築する。ランダムウォークモデル１２１は、展開されたリレーショナルグラフ１１９からマルコフ連鎖を構築することによって生成される。当業者によって理解されるように、マルコフ連鎖（又はマルコフモデル）は、任意の所定の状態についての次の状態が所定の状態のみに依存する状態を有するモデルである。典型的な実施形態において、マルコフ連鎖自身は、ランダムウォークモデル１２１として指定される。展開されたリレーショナルグラフ１１９からランダムウォークモデル１２１を生成するプロセスは、図４の工程Ｓ１５０に関してより詳細に記載される。
【００２０】
任意の重み学習モジュール１２２は、所定の推薦タスクについてのリレーショナルグラフ（例えば、図１、リレーショナルグラフ２）における各リレーションの重み付け寄与を表す重み付け値の組１２３を決定する。例えば、図１のリレーショナルグラフ２に関して、タグ８の推薦が所定の画像４に関して行われることになっている場合、オーナリレーション２２が、所定の画像４について推薦するのにタグ８がより良好な指示であることが決定される場合、オーナリレーション２２は、ａｐｐｅａｒｓ＿ｉｎリレーション２６よりも重く重み付けされてもよい。重み付け値の組１２３を決定するこのプロセスは、図４の工程Ｓ１６０に関して以下により詳細に記載される。
【００２１】
重み付けランダムウォーク生成器１２４は、重み学習モジュール１２２からの重み付け値の組１２３と、一般的なランダムウォーク生成器１２０からのランダムウォークモデル１２１とを入力として受信する。他の実施形態において、重み付け値１２３は、システム１００のオペレータによって直接入力された値等、重み学習モジュール１２２以外のソースから提供される。そして、重み付けランダムウォーク生成器１２４は、重み付けランダムウォークモデル１２５を作成するためにランダムウォークモデル１２１に対して重み付け値の組１２３を適用する。典型的な実施形態において、重み付けランダムウォークモデル１２５は、重み付け値の組１２３にしたがって調整された定常分布πを有するランダムウォークモデル１２１である。そして、生成器１２４は、ソーシャルメディア選択モジュール１２６に対して重み付けランダムウォークモデル１２５を提供する。重み付けランダムウォークモデル１２５を生成するプロセスは、図４の工程Ｓ１７０に関して以下により詳細に記載される。
【００２２】
ソーシャルメディア選択モジュール１２６は、重み付けランダムウォーク生成器１２４からの重み付けランダムウォークモデル１２５を入力として受信し、ソーシャルメディアデータ１０４の入力インスタンスに関して、所定の推薦タスクについての１つ以上のエンティティインスタンスを選択するために重み付けランダムウォークモデル１２５においてランダムウォークを実行する。そして、選択されたエンティティインスタンスは、所定の入力エンティティ１０４についての推薦１３４として出力される。例えば、簡略化した重み付けランダムウォークモデル１２５は、（状態Ｓ０によって示された）タグが付けられることになる画像に関して図３において提供される。この例において、Ｓ１についての２０％の機会及びＳ３についての３０％の機会とは対照的にＳ２が次の段階である５０％の機会をランダムウォークが提供することから、モデル１２５において実行されるランダムウォークは、選択されることになる状態Ｓ２によって表されるタグをもたらしそうである。ランダムウォークは、複数のエンティティインスタンスを選択するために複数回実行されてもよい。重み付けランダムウォークモデル１２５からエンティティインスタンスを選択するこのプロセスは、図４の工程Ｓ１８０に関して以下により詳細に記載される。
【００２３】
典型的な実施形態において、構成要素１１４、１１６、１１８、１２０、１２２、１２４、１２６は、コンピュータプロセッサ１３６によって実行されるメインメモリ１１２に記憶されたソフトウェア命令を備える。コンピュータのＣＰＵ等のプロセッサ１３６は、メモリ１１２に記憶された処理命令の実行によってコンピューターシステム１００の全体動作を制御してもよい。構成要素１０２、１１２、１１４、１１６、１１８、１２０、１２２、１２４、１２６、１２８、１３６は、データ制御バス１３８によって接続されてもよい。
【００２４】
明らかなように、システム１００は、さらに同じ機能性を有しながら、より少し又はより多くの構成要素を含んでもよい。例えば、構成要素１１６、１１８、１２０、１２２、１２４、１２６は、より少しの構成要素を形成するように組み合わされてもよく、又は、より多くの個々の構成要素を形成するように機能的に分離されてもよい。
【００２５】
システム１００は、パーソナルコンピュータ、ＰＤＡ、ラップトップコンピュータ、サーバコンピュータ、又は、それらの組み合わせ等、１つ以上の計算装置を備えてもよい。メモリ１１２、１１４は、一体であってもよく、又は、分離されていてもよく、ランダムアクセスメモリ（ＲＡＭ）、読み出し専用メモリ（ＲＯＭ）、磁気ディスク若しくはテープ、光ディスク、フラッシュメモリ、又は、ホログラフィックメモリ等、任意の種類のコンピュータ読み取り可能な媒体を表してもよい。１つの実施形態において、メモリ１１２、１１４は、ランダムアクセスメモリ及び読み出し専用メモリの組み合わせからなる。いくつかの実施形態において、プロセッサ１３６及びメモリ１１２及び／又は１１４は、単一チップに結合されてもよい。
【００２６】
システム１００は、クライアント端末機１３０やサーバ等の出力装置に対して推薦１３４を出力してもよい。出力装置１２８は、システム１００と直接接続されてもよく、又は、例えば、ローカルエリアネットワーク、ワイドエリアネットワーク、又は、インターネット等の有線−無線リンク１３２を介して、それに対してリンクされてもよい。システム１００又はクライアント端末機１３０は、ユーザに対する表示のためのグラフィカルユーザインターフェース（ＧＵＩ）を生成してもよい。典型的なＧＵＩ（図示しない）は、カーソル制御装置、キーボード、キーパッド、ジョイスティック等のユーザ入力装置を用いてクライアント端末機１３０の表示画面を介してユーザがシステム１００と対話するのを可能とする。典型的な実施形態において、クライアント端末機１３０は、ユーザがシステム１００と対話するのを許容するウェブブラウザを含んでもよく、それはサーバコンピュータによって実装されてもよい。
【００２７】
本願明細書では、用語「ソフトウェア」は、ソフトウェアの目的であるタスクを実行するようにコンピュータ又は他のディジタルシステムを構成するために、コンピュータ又は他のディジタルシステムによって実行可能な命令の任意の集合又はセットを含むことを目的としている。本願明細書では、用語「ソフトウェア」は、ＲＡＭ、ハードディスク、光ディスク等の記憶媒体に記憶されるそのような命令を含むことを目的としており、ＲＯＭ等に記憶されるソフトウェアであるいわゆる「ファームウェア」を含むことも目的としている。そのようなソフトウェアは、様々な方法で編成されてもよく、ライブラリ、リモートサーバ等に記憶されたインターネットベースのプログラム、ソースコード、解釈コード、オブジェクトコード、直接実行可能コード等として編成されたソフトウェアコンポーネントを含んでもよい。ソフトウェアが所定の機能を実行するためにサーバ又は他の位置にある他のソフトウェアに対してシステムレベルコード又はコールを呼び出してもよいと考えられる。
【００２８】
図４は、マルチリレーショナル環境において項目を推薦するための典型的な方法を図示している。本方法は、図２において詳述された典型的なシステムにおいて実行されてもよい。本方法は、Ｓ１００から始まる。
【００２９】
Ｓ１１０において、ソーシャルメディア推薦システム１００は、推薦タスクが実行されることになるソーシャルメディアデータ１０４（画像等）の単一のインスタンスをメモリ１１２及び／又は１１４に受信する。説明的な目的のために、推薦タスクが入力画像についての１つ以上のタグを推薦することになっていると仮定される。しかしながら、推薦タスクは、一般に、ネットワークにおける第２のエンティティのインスタンスについてのソーシャルネットワークにおける１つのエンティティのうちの１つ以上のインスタンスの推薦をカバーする。
【００３０】
Ｓ１２０において、ソーシャルメディア推薦システム１００は、ソーシャルメディアデータモデルを表すリレーショナルグラフ１０６をメモリ１１２及び／又は１１４に受信する。例えば、図１のリレーショナルグラフ２は、Ｆｌｉｃｋｒソーシャルメディアデータモデルの表現であり、システム１００への入力であってもよい。
【００３１】
Ｓ１３０において、ソーシャルメディア推薦システム１００は、インスタンス生成されたソーシャルメディアデータ１０８をメモリ１１２及び／又は１１４に受信する。インスタンス生成されたソーシャルメディアデータは、入力ソーシャルメディアデータモデル１０６にしたがう１つ以上のソーシャルメディアエンティティインスタンス（画像、タグ、ユーザ等）を含む。
【００３２】
Ｓ１４０において、リレーショナルグラフ展開モジュール１２０は、ソーシャルメディアデータモデル１０６及びインスタンス生成されたソーシャルメディアデータ１０８に基づいて同時生起行列を作成することによって展開されたリレーショナルグラフ１１９を生成する。上述したように、ソーシャルメディアデータモデル１０６は、Ｇ＝（Ｅ，Ｒ）によって与えられるグラフである。ここで、エンティティ型ek
【数５】
0005789204.tif 000006
は、ノードとして表され、型ｅｋ及びｅｌのエンティティ間のリレーションrkl
【数６】
0005789204.tif 000007
は、（型付き）リンクとして表される。展開されたリレーショナルグラフ１１９を作成するために、各リレーションｒｋｌは、以下の行列の形態で（インスタンス生成されて）展開される。
【数７】
0005789204.tif 000008
ここで、以下
【数８】
0005789204.tif 000009
は、以下
【数９】
0005789204.tif 000010
及び
【数１０】
0005789204.tif 000011
のエンティティ間のリレーションを示す（例えば、図１のｔａｇｇｅｄ＿ｗｉｔｈリレーション６において、画像ｉがタグｊによってタグ付けされた場合には、リレーションｒｋｌにおいてαｉｊ＝１であり、そうでない場合は０である）。
一般的な場合において、ａｉｊは、範囲［０，１］からの実数値である。リレーショナルグラフが型ｅ１，・・・，ｅｂのｂ個のエンティティＰを含むと仮定する。エンティティの総数は、以下である。
【数１１】
0005789204.tif 000012
展開されたリレーショナルグラフ１１９は、各（ｅｋ，ｅｌ）対について１つのブロックとしたとき、ｂ２個のブロックから構成される。利用可能なリレーションは、いくつかのブロックを満たし、他のブロックは、空のままにされることができるか、又は、リレーション他動性Ａｋｌ＝ＡｋｍＡｍｌを使用して構成されたリレーションによって満たされることができる。ここで、Ａｋｌは、基本的又は構成されたリレーションである。リレーション構成は、所定の推薦タスクに依存してもよい。
【００３３】
図１のＦｌｉｃｋｒリレーショナルモデル２に関して、Ｐにおける対応するブロックを満たし且つ他のリレーションを構成することができる７つの基本リレーション６、１０、１４、１８、２０、２２、２６がある。タグ同時生起関係は、構成されたリレーションの例である。行列ＡＩＴがリレーションｔａｇｇｅｄ＿ｗｉｔｈ（画像，タグ）を記載する場合、タグ同時生起行列は、ＡＴＴ＝Ａ’ＩＴＡＩＴによって取得されることができる。ＡＴＴにおけるより高い値は、より多くの画像が所定のタグ対によってタグ付けされることを示す。
【００３４】
Ｓ１５０において、一般的なランダムウォーク生成器１２０は、展開されたリレーショナルグラフ１１９からマルコフ連鎖を構築することによってランダムウォークモデル１２１を生成する。一般的なランダムウォーク生成器１２０によって構築されたマルコフ連鎖は、特定の予測タスクについて良好に作用する定常分布πを有する。状態Ｓの組にわたるマルコフ連鎖は、Ｓにわたる初期分布Ｐ０及び状態遷移確率
【数１２】
0005789204.tif 000013
の組によって規定される。マルコフ連鎖は、初期状態Ｓ０がＰ０にしたがって最初にサンプリングされ、その後、遷移確率にしたがって順に状態Ｓｔ（ｔ＝１，２，・・・）がサンプリングされる生成プロセスを介して、状態の配列にわたって分布を定義する。マルコフ連鎖の定常分布は、制限が存在する場合、以下によって与えられる。
【数１３】
0005789204.tif 000014
【００３５】
マルコフ連鎖が独特な定常分布を有するのを確実にするために、モジュール１２０は、初期状態分布Ｐ０にしたがって確率α＞０によってプロセスをリセットする。確率αは、本方法についての調整パラメータであり、実際には、適切な確率αは、連鎖が小ループから抜け出せなくなるのを防止する。典型的な実施形態において、約０．０５から０．４０に及ぶ値のαは、良好な結果を生成するが、αについての他の値が考えられる。Ｓ０にしたがって分布された初期状態Ｓ０、Ｐによって与えられる状態遷移及びリセット確率αによるマルコフ連鎖Ｓ０，Ｓ１，・・・を有する場合、以下のように定常分布πを表現することは容易である。
【数１４】
0005789204.tif 000015
【００３６】
式（１）は、効率的にπを計算するのに使用されることができる。大きいｔに対応する期間が非常に僅かな重みを有することから、πを計算するとき、このシーケンスは、重大な誤差を被ることなく最初の数期間（
【数１５】
0005789204.tif 000016
のオーダー）の後に打ち切られてもよい。
【数１６】
0005789204.tif 000017
一般的なランダムウォーク生成器１２０の出力は、ランダムウォークモデル１２１である。典型的な実施形態において、ランダムウォークモデル１２１は、マルコフ連鎖と同様である。
【００３７】
Ｓ１６０において、重み学習モジュール１２２は、所定の推薦タスクについてのリレーショナルグラフ１０６における各リレーションの重み付け寄与を表す重み付け値の組１２３を決定する。重み付け値１２３は、重み付け値１２３及び前に作成されたランダムウォークモデル１２１を組み合わせた重み付けランダムウォークモデル１２５を作成するために重み付けランダムウォーク生成器１２４によって使用される。他の実施形態において、重み付け値１２３は、計算される必要がないシステム１００への入力であってもよい。
【００３８】
説明の便宜上、所定のランダムウォークモデルを考える。重みｗｋｌは、エンティティｅｋ及びｅｌの間のランダムウォークモデルにおける所定のリレーションｒｋｌの相対的な寄与を表現する。以下によって表現されるリレーションの重み付け和及びπ（ｓ）ｊは、エンティティ型ｊにおける定常分布πの射影である。
【数１７】
0005789204.tif 000018
【００３９】
ランダムウォークモデルにおいてランダムウォークを開始するために、初期分布Ｐ０は、クエリーに利用可能な全ての要素を有するｂ個のベクトルδｉ、ｉ＝１，・・・，ｂから構成される。したがって、Ｐ０は、［δ１，δ２，・・・，δｂ］の正規化として定義されてもよい。それゆえに、重みｗｉｊが専門家によって公知であるか又は推薦された場合、式（１）は、定常分布π及びその射影πｊを推定するのに使用されてもよい。重みが事前に不明である場合、重み学習モジュール１２２は、所定の損失関数を最小化する重みｗｋｌについての値を見出す。
【００４０】
リレーショナルランダムウォークの重みを学習するために、定常分布πは、省略されたバージョンで近似され、最適化問題は、予測が訓練事例に対して適用されるときに、損失関数の最小化として重みｗｋｌにおいて表現される。それゆえに、重み付けランダムウォークは、確率分布をもたらす重み付けマルコフ連鎖クエリーによって定義される。より高い重みを有するより多くのリンク（例えば、エンティティ間のリレーション）を有するノードは、より少ないリンクを有し且つより低い重みのノードよりも多くの確率を集積する。さらに、リンク上の重みは、訓練事例から推定されることができる。ここで、モデルは、訓練事例Ｔにおける予測誤差を最小化するマルコフモデル重みのインスタンス化である。重み学習を支援するために、型ｅｋのエンティティに対して［０，１］の値を割り当てるスコアリング関数Ｈが使用される。重み学習モジュール１２２は、ソーシャルメディアデータモデル１０６及び／又は展開されたリレーショナルグラフ１１９から生じるもの等、エンティティ間における公知のリレーションの組から関数Ｈを学習する。関数Ｈは、所定のオブジェクトｉについての確率ｐを推定する。ｙをｉの真の確率を意味するものとし、ｐをＨによるその推定値とする。ｙの場所における予測ｐのときに取られる損失は、損失関数ｌ（ｙ，ｐ）として定義される。ｙ及びｐの間の二乗損失は、以下として表現される。
【数１８】
0005789204.tif 000019
【００４１】
ここで留意すべきは、ｐにおける一次及び二次の偏導関数は、それぞれ、以下であるということである。
【数１９】
0005789204.tif 000020
【数２０】
0005789204.tif 000021
【００４２】
一般性の損失なしに、タグ推薦タスクは、二乗損失関数を示すように表される。タグエンティティセットがＬ個のタグインスタンスを有すると仮定する。所定の画像について、画像がタグｉ、ｉ＝１，・・・，Ｌによってタグ付けされる場合、ＹＢを二値ベクトルＹＢ＝｛ｙ１，・・・，ｙＬ｝を意味するものとする。ここで、ｙｉは１である。タグ設定タグにわたる確率分布は、Ｙ＝（ｙ１，・・・，ｙｎ）である。ここで、ｙｉは以下である。
【数２１】
0005789204.tif 000022
【００４３】
Ｐを推定されたタグ確率分布Ｐ＝（ｐ１，・・・，ｐＬ）を意味するものとする。ここで、以下である。
【数２２】
0005789204.tif 000023
Ｙの場所において分布Ｐを使用した二乗損失は、以下として定義される。
【数２３】
0005789204.tif 000024
【００４４】
分布の二乗損失Ｌｓｑについて、導関数は、以下の形式を有する。
【数２４】
0005789204.tif 000025
そして、同様に以下である。
【数２５】
0005789204.tif 000026
【００４５】
画像の訓練事例Ｔがタグ確率分布Ｙを有する場合、重み学習モジュール１２２は、以下として定義されるＴにわたる経験的損失を最小化するスコアリング関数Ｈを見出す。
【数２６】
0005789204.tif 000027
ここで、Ｙｊは、画像ｊについての真の確率ベクトルであり、Ｐｊは、予測確率分布である。
【００４６】
ｂ個の異なるエンティティ型から構成される重み付け和は、以下である。
【数２７】
0005789204.tif 000028
ｗｋｌのより大きな値は、型ｉ及びｊの間のリレーションのより多くの重要度を示す。リレーションｒｋｌについての全ての行列Ａｋｌは、各状態遷移分布によって正規化される。行列混合Ａは、以下の同じ条件及び制約を満たさなければならない。
【数２８】
0005789204.tif 000029
しかしながら、混合行列Ａは、対称形であるのを必要とされなく、一般的な場合において
【数２９】
0005789204.tif 000030
iである。それゆえに、以下の最適化問題が以下に表される。
【数３０】
0005789204.tif 000031
【数３１】
0005789204.tif 000032
【００４７】
制約つき最適化問題（５）は、変数ｖｋｌ、ｋ，ｌ＝１，・・・，ｂを導入して以下を表すことによって制約がないものに変換されることができる。
【数３２】
0005789204.tif 000033
ｗｋｌに制約される問題は、ｖｋｌに制約されなくなる。
【００４８】
問題（５）を解決するために、重み学習モジュール１２２は、メモリ制限ブロイデン・フレッチャー・ゴールドファーブ・シャンノ（Ｌ−ＢＦＧＳ）法を使用する。Ｌ−ＢＦＧＳアルゴリズムは、準ニュートン最適化法の広い群の要素である。これらの方法は、周知のニュートン法を近似し、（２回連続して微分可能な）関数の停留点を求める山登り最適化技術の類である。そのような問題のために、最適化についての要件は、勾配がゼロであるということである。関数が最適条件の近くで二次テイラー展開を有しない限り、ニュートン法及びＢＦＧＳ法は、収束する必要はない。一般的にいえば、これらの方法は、一次及び二次の導関数を使用する。
【００４９】
準ニュートン法において、二次導関数のヘッセ行列は、直接推定される必要はない。代わりに、ヘッセ行列は、勾配推定値（又は近似の勾配推定値）によって指定される階数１のアップデートを使用して近似される。ブロイデン・フレッチャー・ゴールドファーブ・シャンノ（ＢＦＧＳ）法は、この類の最もよく知られた要素の１つである。
【００５０】
Ｌ−ＢＦＧＳは、逆ヘッセ行列を近似するためにＢＦＧＳのメモリ制限バリエーションを使用する。高密度のｎ×ｎの近似値を記憶するオリジナルのＢＦＧＳ法と異なり、Ｌ−ＢＦＧＳは、暗に近似値を表す少数のベクトルのみを記憶する。Ｌ−ＢＦＧＳルーチンによる最適化パッケージは、Ｍａｔｌａｂ及びＰｙｔｈｏｎ／Ｓｃｉｐｙ環境において使用される。
【００５１】
上述した反復スキームは、ヘッセ行列ＨＬ（Ｗ）の勾配
【数３３】
0005789204.tif 000034
及び逆行列を含む全てのｗｋｌ次元に一般化されてもよい。ここで、Ｗ＝（ｗｋｌ）、ｋ，ｌ＝１，・・・，ｂである。これは、近似された解決策Ｗ０，Ｗ１，・・・の以下の反復シーケンスを与える。
【数３４】
0005789204.tif 000035
【００５２】
重み付けランダムウォークのために準ニュートン法を展開するために、変数ｗｋｌに関する損失関数の導関数は、以下で取得される。
【数３５】
0005789204.tif 000036
ここで、以下及び
【数３６】
0005789204.tif 000037
は、画像ｊについての初期確率分布である。
【数３７】
0005789204.tif 000038
【００５３】
べき級数Ａｔ、ｔ＝１，２，・・・は、ｗｋｌに依存するＰｊにおける唯一の項であり、それらの一次導関数は、以下によって提供される。
【数３８】
0005789204.tif 000039
そして、二次導関数は、以下によって提供される。
【数３９】
0005789204.tif 000040
【００５４】
Ｓ１７０において、重み付けランダムウォーク生成器１２４は、一般的なランダムウォーク生成器１２０からのランダムウォークモデル１２１に対して重み学習モジュール１２２からの重み付け値の組１２３を適用することによって重み付けランダムウォークモデル１２５を生成する。典型的な実施形態において、重み付け値の組１２３は、ランダムウォークモデル１２１における各リレーションｒｋｌについての重みｗｋｌを備える。それゆえに、ランダムウォークモデル１２１におけるリレーションｒｋｌを有するエンティティ間の各リンク遷移確率は、重み付けランダムウォークモデル１２５を作成するために値ｗｋｌを乗じる。
【００５５】
Ｓ１８０において、ソーシャルメディア選択モデル１２６は、インスタンス生成されたソーシャルメディアデータ１０８の範囲内で、１つ以上のソーシャルメディアインスタンスを確認するために、重み付けランダムウォークモデル１２５において１つ以上のランダムウォークを実行する。初期クエリーＰ０は、ランダムウォークを開始するのに使用される。ランダムウォークは、推薦タスクが実行されることになるソーシャルメディアデータ１０４の単一のインスタンスを表す状態から始まる。典型的な実施形態において、ランダムウォークは、その後、要求される型のエンティティ（画像についてのタグ等）が見出されるまで、次の状態（すなわち、エンティティインスタンス）に進む。このプロセスは、推薦についての複数のエンティティインスタンスを選択するために複数回反復されてもよい。
【００５６】
Ｓ１９０において、ソーシャルメディア選択モジュール１２６は、出力装置１２８を介して推薦として選択されたエンティティインスタンスを出力する。典型的な実施形態において、エンティティインスタンスのリストが出力であるが、他の実施形態において、エンティティインスタンス自身が出力であってもよい。
【００５７】
図４に図示される方法は、コンピュータ上で実行されてもよいコンピュータプログラムにおいて実装されてもよい。コンピュータプログラムは、ディスクやハードディスク等の制御プログラムが記録される非一時的コンピュータ読み取り可能な記録媒体を備えてもよい。非一時的コンピュータ読み取り可能な媒体の一般的形態は、例えば、フロッピーディスク、フレキシブルディスク、ハードディスク、磁気テープ、若しくは、任意の他の磁気記憶媒体、ＣＤ−ＲＯＭ、ＤＶＤ、若しくは、任意の他の光媒体、ＲＡＭ、ＰＲＯＭ、ＥＰＲＯＭ、フラッシュＥＰＲＯＭ、若しくは、他のメモリチップ若しくはカートリッジ、又は、コンピュータが読み取って使用することができる任意の他の有形媒体を含む。
【００５８】
あるいは、本方法は、電波及び赤外線データ通信中に生成されるもの等、音波又は光波等の伝送媒体を使用して、制御プログラムがデータ信号として具体化される伝送可能な搬送波等の一時的媒体に実装されてもよい。
【００５９】
上述した典型的な方法は、ブートストラップ又はクエリーモードのいずれかにおいて実行されてもよい。ブートストラップモードにおいて、タスクは、新たにアップロードされたソーシャルネットワークエンティティインスタンス（例えば、特定の画像）と関連付けるようにエンティティインスタンス（例えば、特定のタグ）を推薦することである。実例の目的で、ブートストラップモードにおいて、タグ推薦は、新たにアップロードされた画像又はビデオクリップについて提供される。クエリーモードにおいて、エンティティインスタンスは、既に、それに関連した既存のエンティティインスタンスを有し（例えば、画像は、既に、いくつかの割り当てられたタグを有する）、これらの既存のリレーションは、推薦を作るときにそれらが考慮されるように展開プロセスに含まれる。
【００６０】
Ｆｌｉｃｋｒ  ＡＰＩを介してダウンロードされたＦｌｉｃｋｒデータセットにおいて定量的評価が実行された。データセットは、約２，０００人のユーザ、約１７０万個のコメント及び２００，０００個のタグを有する５００，０００枚の画像を含む。
【００６１】
重み付けランダムウォーク学習は、３つのエンティティ型、画像、タグ及びユーザにおいてテストされた。３つのコアリレーションは、ＲＩＴ＝ｔａｇｇｅｄ＿ｗｉｔｈ（画像，タグ）、ＲＵＩ＝オーナ（ユーザ，画像）、及び、ＲＵＵ＝コンタクト（ユーザ，ユーザ）である。構成されたリレーションは、推薦タスクに依存する。
【００６２】
タグ推薦のために、画像−画像行列が、
【数４０】
0005789204.tif 000041
として構成され、さらに、視覚的カテゴリ化ツールボックスの助けによって抽出された視覚的特徴を使用して類似性によって重み付けられた。他の構成されたリレーションは、タグ−タグ
【数４１】
0005789204.tif 000042
及びユーザ−タグ
【数４２】
0005789204.tif 000043
、並びに、それらの逆である。ユーザコンタクト推薦のために、合成された行列は、
【数４３】
0005789204.tif 000044
及び
【数４４】
0005789204.tif 000045
である。行列Ａは、ｌ＝３によるｌ×ｌのブロックのようであり、最適化は、ｌ２個の重みｗｉｊにおいて行われる。
【００６３】
テストされた推薦タスクのうちの２つは、画像についてのタグ推薦及びユーザについてのコンタクト推薦である。前者は、ブートストラップ又はクエリーモードのいずれでも実行する。ブートストラップモードにおいて、タスクは、新たにアップロードされた画像についてのタグを予測することである。クエリーモードにおいて、画像は、いくつかのタグを有してもよく、予測タスクは、新規のタグを推薦することによってタグの組を拡大することである。双方のモードにおいて、タグの数｜ｓｉｚｅ｜が画像によって変動するところのトップ５及び｜ｓｉｚｅ｜タグを予測する性能は、前もって公知である（そして、テストタグ事例と等しい）。コンタクト推薦は、クエリーモードのみにおいてテストされた。
【００６４】
複数のラベル付きモードにおいて定義される精度、再現率及びＦ１評価尺度が使用された。Ｙｉ及びＰｉを、それぞれ、画像ｉについての真の及び予測タグベクトルを意味するものとする。そして、精度及び再現率は、それぞれ、以下として定義される。
【数４５】
0005789204.tif 000046
【数４６】
0005789204.tif 000047
そして、Ｆ１スコアは、以下として定義される。
【数４７】
0005789204.tif 000048
【００６５】
ランダムウォークの重みが学習され、重み付けなしスキーマによって与えられる基準性能結果と比較される。重み付けなしスキーマは、等しい重みを有するコア及び構成されたリレーションによって構成される。初期分布は、クエリー型の関数において変動する。平均値は、５つの独立した実行にわたって報告される。
【００６６】
図５は、１，０００から２５，０００まで変動する画像セットの大きさによるブートストラップタグ推薦についての再現率及び精度値を報告している。テストは、ｌｅａｖｅ−ｏｎｅ−ｏｕｔスキーマにおいて実行され、予測されたタグのトップ５は、真のタグ事例と比較される。
【００６７】
図６は、クエリータグ推薦についての再現率及び精度値を報告している。ここで、画像セットの大きさは、１，０００から２５，０００まで変動する。この評価において、５０％のタグが所定の画像についてのクエリーを形成するようにランダムに選択され、残りの５０％のタグがテストを行うために使用される。そして、予測されたタグのトップ５は、真のタグ事例と比較される。重み付けなし全体の精度及び再現率利得は、それぞれ、約５％及び３％である。さらに、図７は、同じ設定についてのＦ１スコア値を報告している。ここで、予測されたタグの数は５ではないが、テストタグ事例と等しい。
【００６８】
さらに、クエリーベースのシナリオは、ユーザのコンタクト推薦タスクにおいてテストされた。前のテストと同様に、ユーザのコンタクトの５０％がクエリーを形成するようにランダムに選択され、残りの５０％のコンタクトがテストを行うために使用される。図８は、推薦されたコンタクトのトップ５についての精度及び再現率値を報告している。ここで、ユーザ数は、１００から１９００まで変動する。再現率におけるよりも精度において非常に高い利得を観察することができる。
【００６９】
図９は、１、２、３、４、５又は１０回反復後にシーケンスが打ち切られたとき、１，０００枚及び２０，０００枚の画像の２つの場合についての精度及び再現率値について報告された性能上の式（１）における異なる打ち切りの影響を図示している。図９が示唆するように、双方の測定結果は、２又は３等の非常に小さい値についてそれらの最良値を達成している。
【図１】
0005789204.tif 000049
【図２】
0005789204.tif 000050
【図３】
0005789204.tif 000051
【図４】
0005789204.tif 000052
【図５】
0005789204.tif 000053
【図６】
0005789204.tif 000054
【図７】
0005789204.tif 000055
【図８】
0005789204.tif 000056
【図９】
0005789204.tif 000057