(57)【要約】  コンピューティングデバイスが、複数のノードを含むグラフを生成することであって、複数のノードが、複数のエンティティを表す複数のエンティティノード、および複数の特徴を表す複数の特徴ノードを含み、複数のエンティティノードの各々が、グラフ内で複数の特徴ノードのうちの1つまたは複数に接続される、生成することを行う可能性がある。コンピューティングデバイスは、複数のノードの各々にラベルの分布を関連付けるためにラベル伝搬を実行する可能性がある。コンピューティングデバイスは、関心のある特徴または関心のあるエンティティのうちの少なくとも一方の指示を受信するように構成される可能性がある。コンピューティングデバイスは、関心のある特徴または関心のあるエンティティに関連する1つまたは複数の関連エンティティの指示を出力するようにさらに構成される可能性がある。
2019514149.tif 000002
【特許請求の範囲】
【請求項１】
複数のノードを含むグラフをコンピューティングデバイスによって生成するステップであって、前記複数のノードが、複数のエンティティを表す複数のエンティティノード、および複数の特徴を表す複数の特徴ノードを含み、前記複数のエンティティノードの各々が、前記グラフ内で前記複数の特徴ノードのうちの1つまたは複数に接続される、ステップ、
前記複数のノードの各々にラベルの分布を関連付けるために前記グラフにわたって複数のラベルを伝搬させるラベル伝搬を前記コンピューティングデバイスによって実行するステップを含み、
前記コンピューティングデバイスが、
関心のある特徴または関心のあるエンティティのうちの少なくとも一方の指示を受信し、
関心のある前記特徴または関心のある前記エンティティのうちの前記少なくとも一方に関して、関心のある前記特徴または関心のある前記エンティティに関連する1つまたは複数の関連エンティティの指示を出力するように構成され、前記1つまたは複数の関連エンティティの前記指示を出力することが、関心のある前記特徴を表す前記複数の特徴ノードのうちの1つ、または関心のある前記エンティティを表す前記複数のエンティティノードのうちの1つに関連するラベルのそれぞれの分布に少なくとも部分的に基づく、方法。
【請求項２】
前記ラベル伝搬を前記コンピューティングデバイスによって実行するステップが、
前記コンピューティングデバイスによって前記複数のエンティティノードの各々に前記複数のラベルのうちのそれぞれ1つをシードとして付けることであって、前記ラベルのそれぞれ1つが、前記複数のエンティティノードのうちの対応する1つを特定する、シードとして付けることをさらに含む、請求項1に記載の方法。
【請求項３】
前記ラベル伝搬を前記コンピューティングデバイスによって実行するステップが、
前記複数のノードの各々に関連するラベルの前記分布を目的関数を最小化する最適解として決定するために前記ラベル伝搬を前記コンピューティングデバイスによって実行することをさらに含む、請求項1または2に記載の方法。
【請求項４】
前記目的関数が、前記複数の特徴ノードのエンティティノードに関して最小化され、前記目的関数が、
前記エンティティノードに関連するラベルの真の分布と前記エンティティノードに関連するラベルの学習された分布との間の2乗損失、
前記エンティティノードに関連するラベルの前記分布と異なるラベルの分布に関連付けられる近接する特徴ノードにペナルティーを科す第1の正則化項、および
ラベルの前の分布に向かって前記エンティティノードに関連するラベルの前記学習された分布を平滑化する第2の正則化項を含む、請求項3に記載の方法。
【請求項５】
前記目的関数が、前記複数の特徴ノードの特徴ノードに関して最小化され、前記目的関数が、
前記特徴ノードに関連するラベルの前記分布と異なるラベルの分布に関連付けられる近接するエンティティノードにペナルティーを科す第1の正則化項、および
ラベルの前の分布に向かって前記特徴ノードに関連するラベルの学習された分布を平滑化する第2の正則化項を含む、請求項3に記載の方法。
【請求項６】
ラベルの前記分布の各々が、関連するエンティティノードまたは特徴ノードによって表されるエンティティまたは特徴に関連する1つまたは複数のエンティティのランク付けの指示を含む、請求項1から5のいずれか一項に記載の方法。
【請求項７】
前記関連するノードによって表される前記エンティティまたは前記特徴に関連する前記1つまたは複数のエンティティの前記ランク付けの前記指示が、前記関連するエンティティノードまたは特徴ノードによって表される前記エンティティまたは前記特徴との前記1つまたは複数のエンティティの各々の関わりのレベルの指示を含む、請求項6に記載の方法。
【請求項８】
前記コンピューティングデバイスによって、対応するエンティティを表す前記グラフ内の前記複数のエンティティノードの各々を、前記対応するエンティティに関連する1つまたは複数の特徴を表す前記グラフ内の前記複数の特徴ノードのうちの1つまたは複数に、前記グラフの1つまたは複数のエッジによって接続するステップをさらに含む、請求項1から7のいずれか一項に記載の方法。
【請求項９】
前記コンピューティングデバイスによって前記1つまたは複数のエッジに1つまたは複数の重みを関連付けるステップをさらに含む、請求項8に記載の方法。
【請求項１０】
メモリと、
前記メモリに通信可能なように結合された少なくとも1つのプロセッサとを含み、前記少なくとも1つのプロセッサが、
複数のノードを含む、前記メモリに記憶されるグラフを生成することであって、前記複数のノードが、複数のエンティティを表す複数のエンティティノード、および複数の特徴を表す複数の特徴ノードを含み、前記複数のエンティティノードの各々が、前記グラフ内で前記複数の特徴ノードのうちの1つまたは複数に接続される、生成すること、ならびに
前記複数のノードの各々にラベルの分布を関連付けるために前記グラフにわたって複数のラベルを伝搬させるラベル伝搬を実行することを行うように構成される、コンピューティングシステム。
【請求項１１】
メモリと、
前記メモリに通信可能なように結合された少なくとも1つのプロセッサとを含み、前記少なくとも1つのプロセッサが、請求項1から9のいずれか一項に記載の方法を実行するためのコンピュータ可読命令の制御の下で動作するように構成される、コンピューティングシステム。
【請求項１２】
関心のある特徴または関心のあるエンティティのうちの少なくとも一方の指示をコンピューティングデバイスによって受信するステップと、
関心のある前記特徴を表すグラフ内の複数の特徴ノードのうちの1つまたは関心のある前記エンティティを表す前記グラフ内の複数のエンティティノードのうちの1つに関連するラベルのそれぞれの分布に少なくとも部分的に基づいて関心のある前記特徴または関心のある前記エンティティに関連する1つまたは複数の関連エンティティを前記コンピューティングデバイスによって決定するステップであって、前記グラフが、複数のノードを含み、前記複数のノードが、複数のエンティティを表す複数のエンティティノード、および複数の特徴を表す複数の特徴ノードを含み、前記複数のエンティティノードの各々が、前記グラフ内で前記複数の特徴ノードのうちの1つまたは複数に接続され、複数のラベルが、前記複数のノードの各々にラベルの分布を関連付けるために前記グラフにわたってラベル伝搬によって伝搬させられる、ステップと、
関心のある前記特徴または関心のある前記エンティティのうちの前記少なくとも一方に関して、関心のある前記特徴または関心のある前記エンティティに関連する1つまたは複数の関連エンティティの指示を前記コンピューティングデバイスによって出力するステップとを含み、前記1つまたは複数の関連エンティティの前記指示を出力するステップが、関心のある前記特徴を表す前記複数の特徴ノードのうちの1つ、または関心のある前記エンティティを表す前記複数のエンティティノードのうちの1つに関連するラベルの前記それぞれの分布に少なくとも部分的に基づく、方法。
【請求項１３】
関心のある前記特徴または関心のある前記エンティティのうちの前記少なくとも一方の前記指示を受信するステップが、関心のある前記特徴または関心のある前記エンティティのうちの前記少なくとも一方を示す着信データをリモートコンピューティングデバイスからネットワークを介して前記コンピューティングデバイスによって受信することをさらに含み、
前記コンピューティングデバイスによって、関心のある前記特徴または関心のある前記エンティティのうちの前記少なくとも一方に関して、関心のある前記特徴または関心のある前記エンティティに関連する前記1つまたは複数の関連エンティティの前記指示を出力するステップが、関心のある前記特徴または関心のある前記エンティティに関連する前記1つまたは複数の関連エンティティの前記指示を含む発信データを前記リモートコンピューティングデバイスに前記ネットワークを介して前記コンピューティングデバイスによって送信することをさらに含む、請求項12に記載の方法。
【請求項１４】
メモリと、
前記メモリに通信可能なように結合された少なくとも1つのプロセッサとを含み、前記少なくとも1つのプロセッサが、
関心のある特徴または関心のあるエンティティのうちの少なくとも一方の指示を受信すること、
関心のある前記特徴を表すグラフ内の複数の特徴ノードのうちの1つまたは関心のある前記エンティティを表す前記グラフ内の複数のエンティティノードのうちの1つに関連するラベルのそれぞれの分布に少なくとも部分的に基づいて関心のある前記特徴または関心のある前記エンティティに関連する1つまたは複数の関連エンティティを決定することであって、前記グラフが、複数のノードを含み、前記複数のノードが、複数のエンティティを表す複数のエンティティノード、および複数の特徴を表す複数の特徴ノードを含み、前記複数のエンティティノードの各々が、前記グラフ内で前記複数の特徴ノードのうちの1つまたは複数に接続され、複数のラベルが、前記複数のノードの各々にラベルの分布を関連付けるために前記グラフにわたってラベル伝搬によって伝搬させられる、決定すること、ならびに
関心のある前記特徴または関心のある前記エンティティのうちの前記少なくとも一方に関して、関心のある前記特徴または関心のある前記エンティティに関連する1つまたは複数の関連エンティティの指示を出力することを行うように構成され、前記1つまたは複数の関連エンティティの前記指示を出力することが、関心のある前記特徴を表す前記複数の特徴ノードのうちの1つ、または関心のある前記エンティティを表す前記複数のエンティティノードのうちの1つに関連するラベルの前記それぞれの分布に少なくとも部分的に基づく、コンピューティングシステム。
【請求項１５】
前記少なくとも1つのプロセッサが、
関心のある前記特徴または関心のある前記エンティティのうちの前記少なくとも一方を示す着信データをリモートコンピューティングデバイスからネットワークを介して受信し、
関心のある前記特徴または関心のある前記エンティティに関連する前記1つまたは複数の関連エンティティの前記指示を含む発信データを前記リモートコンピューティングデバイスに前記ネットワークを介して送信するようにさらに構成される、請求項14に記載のコンピューティングシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、関連エンティティの発見に関する。
【背景技術】
【０００２】
コンピューティングデバイスは、ユーザが関心のあるエンティティの指示を特定のユーザから受信することが多いことがある。たとえば、ユーザは、コンピューティングデバイスを使用して場所、イベント、人、会社、レストランなどのエンティティの検索を実行する可能性がある。ユーザは、ソーシャルメディアアプリケーションを使用してイベントにチェックインすることによってまたはユーザのカレンダーにイベントの指示を書き込むことによって、ユーザがイベントに参加したかまたはレストランで食事をしたという指示を提供する可能性もある。
【発明の概要】
【課題を解決するための手段】
【０００３】
一例において、本開示は、方法を対象とする。方法は、複数のノードを含むグラフをコンピューティングデバイスによって生成するステップであって、複数のノードが、複数のエンティティを表す複数のエンティティノード、および複数の特徴を表す複数の特徴ノードを含み、複数のエンティティノードの各々が、グラフ内で複数の特徴ノードのうちの1つまたは複数に接続される、ステップを含み得る。方法は、複数のノードの各々にラベルの分布を関連付けるためにグラフにわたって複数のラベルを伝搬させるラベル伝搬をコンピューティングデバイスによって実行するステップをさらに含み得る。コンピューティングデバイスは、関心のある特徴または関心のあるエンティティのうちの少なくとも一方の指示を受信し、関心のある特徴または関心のあるエンティティのうちの少なくとも一方に関して、関心のある特徴または関心のあるエンティティに関連する1つまたは複数の関連エンティティの指示を出力するように構成され、1つまたは複数の関連エンティティの指示を出力することは、関心のある特徴を表す複数の特徴ノードのうちの1つ、または関心のあるエンティティを表す複数のエンティティノードのうちの1つに関連するラベルのそれぞれの分布に少なくとも部分的に基づく。
【０００４】
別の例において、本開示は、メモリおよび少なくとも1つのプロセッサを含むコンピューティングシステムを対象とする。少なくとも1つのプロセッサは、メモリに通信可能なように結合され、複数のノードを含む、メモリに記憶されるグラフを生成することであって、複数のノードが、複数のエンティティを表す複数のエンティティノード、および複数の特徴を表す複数の特徴ノードを含み、複数のエンティティノードの各々が、グラフ内で複数の特徴ノードのうちの1つまたは複数に接続される、生成すること、ならびに複数のノードの各々にラベルの分布を関連付けるためにグラフにわたって複数のラベルを伝搬させるラベル伝搬を実行することを行うように構成される可能性がある。
【０００５】
別の例において、本開示は、方法を対象とする。方法は、関心のある特徴または関心のあるエンティティのうちの少なくとも一方の指示をコンピューティングデバイスによって受信するステップを含み得る。方法は、関心のある特徴を表すグラフ内の複数の特徴ノードのうちの1つまたは関心のあるエンティティを表すグラフ内の複数のエンティティノードのうちの1つに関連するラベルのそれぞれの分布に少なくとも部分的に基づいて関心のある特徴または関心のあるエンティティに関連する1つまたは複数の関連エンティティをコンピューティングデバイスによって決定するステップであって、グラフが、複数のノードを含み、複数のノードが、複数のエンティティを表す複数のエンティティノード、および複数の特徴を表す複数の特徴ノードを含み、複数のエンティティノードの各々が、グラフ内で複数の特徴ノードのうちの1つまたは複数に接続され、複数のラベルが、複数のノードの各々にラベルの分布を関連付けるためにグラフにわたってラベル伝搬によって伝搬させられる、ステップをさらに含み得る。方法は、関心のある特徴または関心のあるエンティティのうちの少なくとも一方に関して、関心のある特徴または関心のあるエンティティに関連する1つまたは複数の関連エンティティの指示をコンピューティングデバイスによって出力するステップをさらに含む可能性があり、1つまたは複数の関連エンティティの指示を出力することは、関心のある特徴を表す複数の特徴ノードのうちの1つ、または関心のあるエンティティを表す複数のエンティティノードのうちの1つに関連するラベルのそれぞれの分布に少なくとも部分的に基づく。
【０００６】
別の例において、本開示は、メモリおよび少なくとも1つのプロセッサを含むコンピューティングシステムを対象とする。少なくとも1つのプロセッサは、メモリに通信可能なように結合され、関心のある特徴または関心のあるエンティティのうちの少なくとも一方の指示を受信すること、関心のある特徴を表すグラフ内の複数の特徴ノードのうちの1つまたは関心のあるエンティティを表すグラフ内の複数のエンティティノードのうちの1つに関連するラベルのそれぞれの分布に少なくとも部分的に基づいて関心のある特徴または関心のあるエンティティに関連する1つまたは複数の関連エンティティを決定することであって、グラフが、複数のノードを含み、複数のノードが、複数のエンティティを表す複数のエンティティノード、および複数の特徴を表す複数の特徴ノードを含み、複数のエンティティノードの各々が、グラフ内で複数の特徴ノードのうちの1つまたは複数に接続され、複数のラベルが、複数のノードの各々にラベルの分布を関連付けるためにグラフにわたってラベル伝搬によって伝搬させられる、決定すること、ならびに関心のある特徴または関心のあるエンティティのうちの少なくとも一方に関して、関心のある特徴または関心のあるエンティティに関連する1つまたは複数の関連エンティティの指示を出力することを行うように構成される可能性があり、1つまたは複数の関連エンティティの指示を出力することは、関心のある特徴を表す複数の特徴ノードのうちの1つ、または関心のあるエンティティを表す複数のエンティティノードのうちの1つに関連するラベルのそれぞれの分布に少なくとも部分的に基づく。
【０００７】
1つまたは複数の例の詳細が、添付の図面および以下の説明に記載されている。本開示のその他の特徴、目的、および利点は、説明および図面ならびに請求項から明らかになるであろう。
【図面の簡単な説明】
【０００８】
【図１】本開示の1つまたは複数の態様による、関連エンティティを決定するように構成される例示的なシステムを示す概念図である。
【図２】本開示の1つまたは複数の態様による、1組のエンティティの関わりのレベルを決定するように構成される例示的なコンピューティングシステムを示すブロック図である。
【図３Ａ】本開示の態様による例示的なエキスパンダ(expander)技術を実行するために例示的なランク付けモジュールが構築し得る例示的な特徴-エンティティ2部グラフを示すブロック図である。
【図３Ｂ】本開示の態様による例示的なエキスパンダ技術を実行するために例示的なランク付けモジュールが構築し得る例示的な特徴-エンティティ2部グラフを示すブロック図である。
【図３Ｃ】本開示の態様による例示的なエキスパンダ技術を実行するために例示的なランク付けモジュールが構築し得る例示的な特徴-エンティティ2部グラフを示すブロック図である。
【図４】本開示の1つまたは複数の態様による、関連エンティティを決定するための例示的なプロセスを示す流れ図である。
【図５】本開示の1つまたは複数の態様による、関連エンティティを決定するための例示的なプロセスを示す流れ図である。
【発明を実施するための形態】
【０００９】
概して、本開示の技術は、コンピューティングシステムがエンティティに関して1つまたは複数の関連エンティティを決定することを可能にし得る。コンピューティングシステムは、関心のあるエンティティに関して、関心のあるエンティティに意味的に関連する1つまたは複数のエンティティを決定する可能性があり、関心のあるエンティティとの1つまたは複数のエンティティの関わりに少なくとも部分的に基づいてそれらのエンティティをランク付けする可能性がある。したがって、コンピューティングシステムは、ユーザがエンティティに関心があると判定する場合、ユーザが関心のあるエンティティに意味的に関連する1つまたは複数のエンティティにもユーザが潜在的に関心がある可能性があると判定する可能性がある。このようにして、コンピューティングシステムは、ユーザが関心のある可能性がある提案されるエンティティをユーザに提供し得る。
【００１０】
2つのエンティティの関わりは、第1のエンティティに関心がある無作為のユーザが第2のエンティティにも関心がある確率に比例する可能性がある。コンピューティングシステムは、複数のエンティティの各々とのエンティティの関わりを決定する可能性があり、エンティティが複数のエンティティの各々に関連する度合いに少なくとも部分的に基づいて複数のエンティティのランク付けされたリストを生成する可能性がある。
【００１１】
図1は、本開示の1つまたは複数の態様による、関連エンティティを決定するように構成され得る例示的なシステムとしてシステム10を示す概念図である。システム10は、ネットワーク12を介してコンピューティングデバイス2と通信する情報サーバシステム(「ISS」) 14を含む。コンピューティングデバイス2は、コンピューティングデバイス2によって受け取られたクエリまたはコンピューティングデバイス2のユーザが関心のあるエンティティを示す情報をISS 14に提供するためにネットワーク12を介してISS 14と通信し得る。ISS 14は、クエリまたはエンティティに関連する1つまたは複数のエンティティのランク付けされたリストを生成する可能性があり、1つまたは複数のエンティティのランク付けされたリストをコンピューティングデバイス2に伝達する可能性がある。コンピューティングデバイス2は、コンピューティングデバイス2のユーザに対して表示するために1つまたは複数のエンティティのランク付けされたリストをユーザインターフェースデバイス4によって出力し得る。
【００１２】
ネットワーク12は、コンピューティングシステムと、サーバと、コンピューティングデバイスとの間でデータを送信するための任意の公共または私設通信ネットワーク、たとえば、セルラ、Wi-Fi、および/またはその他の種類のネットワークを表す。ネットワーク12は、相互に動作可能なように結合され、それによって、ISS 14とコンピューティングデバイス2との間の情報のやりとりを提供する1つまたは複数のネットワークハブ、ネットワークスイッチ、ネットワークルータ、または任意のその他のネットワーク機器を含み得る。コンピューティングデバイス2およびISS 14は、任意の好適な有線またはワイヤレス通信技術を使用してネットワーク12を介してデータを送信および受信し得る。一部の例において、ネットワーク12は、インターネット20である可能性がある。
【００１３】
ISS 14およびコンピューティングデバイス2は、それぞれが、それぞれのネットワークリンクを使用してネットワーク12に動作可能なように結合され得る。コンピューティングデバイス2およびISS 14をネットワーク12に結合するリンクは、イーサネット(登録商標)またはその他の種類のネットワーク接続である可能性があり、そのような接続は、ワイヤレス接続および/または有線接続である可能性がある。
【００１４】
コンピューティングデバイス2は、個々のモバイルまたは非モバイルコンピューティングデバイスを表す。コンピューティングデバイス2の例は、モバイル電話、タブレットコンピュータ、ラップトップコンピュータ、デスクトップコンピュータ、サーバ、メインフレーム、セットトップボックス、テレビ、ウェアラブルデバイス(たとえば、コンピュータ化された腕時計、コンピュータ化されたアイウェア、コンピュータ化された手袋など)、ホームオートメーションデバイスもしくはシステム(たとえば、インテリジェントサーモスタットもしくはホームアシスタント)、携帯情報端末(PDA)、ポータブルゲームシステム、メディアプレイヤー、電子ブックリーダ、モバイルテレビプラットフォーム、自動車ナビゲーションおよびエンターテインメントシステム、またはネットワーク12などのネットワークを介して情報を受信するように構成された任意のその他の種類のモバイル、非モバイル、ウェアラブル、および非ウェアラブルコンピューティングデバイスを含む。
【００１５】
コンピューティングデバイス2は、ユーザインターフェースデバイス(UID) 4およびユーザインターフェース(UI)モジュール6を含む。UIモジュール6は、それぞれのコンピューティングデバイス2に存在しおよび/またはそれぞれのコンピューティングデバイス2において実行されるソフトウェア、ハードウェア、ファームウェア、またはハードウェア、ソフトウェア、およびファームウェアの混合を使用して説明される動作を実行し得る。一部の例において、コンピューティングデバイス2は、1つもしくは複数のプロセッサまたは1つもしくは複数のデバイスによってUIモジュール6を実行する可能性がある。一部の例において、コンピューティングデバイス2は、基礎をなすハードウェア上で実行される1つまたは複数の仮想マシンとしてUIモジュール6を実行する可能性がある。一部の例において、UIモジュール6は、オペレーティングシステムまたはコンピューティングプラットフォームの1つまたは複数のサービスとして実行される可能性がある。一部の例において、UIモジュール6は、コンピューティングプラットフォームのアプリケーションレイヤにおいて1つまたは複数の実行可能なプログラムとして実行される可能性がある。
【００１６】
コンピューティングデバイス2のUID 4は、コンピューティングデバイス2のための入力および/または出力デバイスとして機能し得る。UID 4は、様々なテクノロジーを使用して実装され得る。たとえば、UID 4は、抵抗式タッチスクリーン、表面弾性波式タッチスクリーン、静電容量式タッチスクリーン、投影型静電容量式タッチスクリーン、感圧スクリーン、音響波照合(acoustic pulse recognition)タッチスクリーン、または別の存在感知(presence-sensitive)ディスプレイテクノロジーなどの1つまたは複数の存在感知入力構成要素を使用する入力デバイスとして機能する可能性がある。加えて、UID 4は、マイクロフォンテクノロジー、赤外線センサーテクノロジー、またはユーザ入力を受け取る際に使用するためのその他の入力デバイステクノロジーを含む可能性がある。
【００１７】
UID 4は、液晶ディスプレイ(LCD)、ドットマトリクスディスプレイ、発光ダイオード(LED)ディスプレイ、有機発光ダイオード(OLED)ディスプレイ、電子インク、またはコンピューティングデバイス2のユーザに可視情報を出力することができる同様のモノクロもしくはカラーディスプレイなどの任意の1つまたは複数のディスプレイ構成要素を使用する出力(たとえば、表示)デバイスとして機能する可能性がある。加えて、UID 4は、スピーカテクノロジー、触覚フィードバックテクノロジー、またはユーザに情報を出力する際に使用するためのその他の出力デバイステクノロジーを含む可能性がある。
【００１８】
UID 4は、コンピューティングデバイス2のユーザから触覚入力を受け取り得る存在感知ディスプレイを含む可能性がある。UID 4は、ユーザから1つまたは複数のジェスチャー(たとえば、ユーザが指またはスタイラスペンによってUID 4の1つまたは複数の位置にタッチするかまたはそれらの位置を指すこと)を検出することによって触覚入力の指示を受け取る可能性がある。UID 4は、たとえば、存在感知ディスプレイにおいてユーザに出力を提示する可能性がある。UID 4は、コンピューティングデバイス2によって提供される機能に関連付けられ得るグラフィカルユーザインターフェース(たとえば、ユーザインターフェース8)として出力を提示する可能性がある。たとえば、UID 4は、UIモジュール120によって提供されるコンピューティングデバイス2のユーザが関心を持っている可能性がある1組のエンティティに関連する様々なユーザインターフェース(たとえば、ユーザインターフェース8)、あるいはコンピューティングデバイス2において実行されるかまたはコンピューティングデバイス2からアクセスされ得るコンピューティングプラットフォーム、オペレーティングシステム、アプリケーション、および/またはサービス(たとえば、電子メッセージアプリケーション、インターネットブラウザアプリケーション、モバイルもしくはデスクトップオペレーティングシステムなど)のその他の特徴を提示する可能性がある。
【００１９】
UIモジュール6は、UID 4において1つまたは複数のエンティティの指示を提供するためにISS 14とインタラクションすることを含め、コンピューティングデバイス2のUID 4およびその他の構成要素とのユーザインタラクションを管理し得る。UIモジュール6は、コンピューティングデバイス2のユーザがUID 4において出力を見るおよび/または入力を与えるときに表示するためのユーザインターフェース8(またはその他の例示的なユーザインターフェース)などのユーザインターフェースをUID 4に出力させ得る。UIモジュール6およびUID 4は、ユーザがユーザインターフェースとインタラクションするときにユーザから入力の1つまたは複数の指示を受け取り得る。UIモジュール6およびUID 4は、UID 4において検出された入力を解釈する可能性があり、UID 4において検出された入力についての情報を、たとえば、コンピューティングデバイス2に機能を実行させるために、コンピューティングデバイス2において実行される1つまたは複数の関連するプラットフォーム、オペレーティングシステム、アプリケーション、および/またはサービスに中継する可能性がある。
【００２０】
UIモジュール6は、コンピューティングデバイス2および/またはISS 14などの1つもしくは複数のリモートコンピューティングシステムにおいて実行される1つまたは複数の関連するプラットフォーム、オペレーティングシステム、アプリケーション、および/またはサービスから情報および命令を受信し得る。加えて、UIモジュール6は、コンピューティングデバイス2において実行される1つまたは複数の関連するプラットフォーム、オペレーティングシステム、アプリケーション、および/またはサービスと、コンピューティングデバイス2によって出力(たとえば、グラフィック、光のひらめき、音、触覚による応答など)を生成するためのコンピューティングデバイス2の様々な出力デバイス(たとえば、スピーカ、LEDインジケータ、オーディオまたは静電式の触覚出力デバイスなど)との間の仲介者として働き得る。
【００２１】
UIモジュール6は、コンピューティングデバイス2のユーザが関心を持っているエンティティの指示を受け取り得る。エンティティは、一部の例においては、イベント、場所、人、会社、映画、レストランなどである可能性がある。たとえば、コンピューティングデバイス2のユーザは、コンピューティングデバイス2上で実行されるウェブブラウザアプリケーションを使用して特定のイベントに関するウェブページ(たとえば、ロッククライミングをする旅行に関するウェブページ)を訪問するか、または特定のイベントに関するソーシャルメディアの投稿に「いいね!」をする可能性があり、これらのことは、ユーザが特定のイベントに関心があることをUIモジュール6に示し得る。
【００２２】
UIモジュール6は、関心のあるエンティティの指示をネットワーク12を介してISS 14に送信し得る。たとえば、UIモジュール6は、エンティティに関するウェブページのインターネットアドレス(たとえば、ユニフォームリソースロケータ)を送信し得る。それに応じて、UIモジュール6は、関心のあるエンティティに最も関連のある1つまたは複数のエンティティの指示をISS 14からネットワーク12を介して受信し得る。たとえば、UIモジュール6は、1つまたは複数のエンティティのインターネットアドレスを受信し得る。UIモジュール6は、1つもしくは複数のエンティティの各々が関心のあるエンティティにどれだけ関連しているかのランク付け、または関心のあるエンティティとの1つもしくは複数のエンティティの各々の関わりのレベルの数量化(たとえば、0から1.0まで)などの、関心のあるエンティティとの1つまたは複数のエンティティの関わりのレベルの指示をISS 14から受信する可能性もある。
【００２３】
UID 4は、関心のあるエンティティに関連する1つまたは複数のエンティティの指示を含むグラフィカルユーザインターフェースなどのユーザインターフェース8を出力し得る。図1に示されるように、関心のあるエンティティがハイキング旅行である場合、ユーザインターフェース8は、ロッククライミングイベント、バックパッキングイベント、およびケービングイベントの指示をハイキング旅行に関連するエンティティとして含み得る。UID 4は、ロッククライミングイベントが最も関連するエンティティである可能性があり、バックパッキングイベントがその次に関連するエンティティである可能性があり、ケービングイベントが3番目に関連するエンティティである可能性があるように、図1の非限定的な例において関連エンティティを関心のあるエンティティとの関わりの順序で提示する可能性がある。このようにして、UID 4は、特定のハイキング旅行へのユーザの関心に基づいて、コンピューティングデバイス2のユーザが関心のある可能性があるエンティティのランク付けされたリストを提示し得る。
【００２４】
図1の例において、ISS 14は、エンティティモジュール16およびランク付けモジュール18を含む。モジュール16および18は、合わせて、関心のあるエンティティに関連する1つまたは複数のエンティティを提供するためにネットワーク12に接続されたコンピューティングデバイス2およびその他のコンピューティングデバイスによってアクセスされ得る関連エンティティサービスである可能性がある。モジュール16および18は、ISS 14に存在するおよび/またはISS 14において実行されるソフトウェア、ハードウェア、ファームウェア、またはハードウェア、ソフトウェア、およびファームウェアの混合を使用して説明される動作を実行し得る。ISS 14は、ほんのいくつか非限定的な例を挙げるとすれば、1つもしくは複数のプロセッサ、1つもしくは複数のデバイス、基礎をなすハードウェア上で実行される仮想マシンによって、および/またはオペレーティングシステムもしくはコンピューティングプラットフォームの1つもしくは複数のサービスとしてモジュール16および18を実行する可能性がある。一部の例において、モジュール16および18は、ISS 14のコンピューティングプラットフォームのアプリケーションレイヤにおいて1つまたは複数の実行可能なプログラムを実行する可能性がある。
【００２５】
エンティティモジュール16は、エンティティに関連するインターネットリソースをインターネット20から取り出すおよび/または受信する可能性があり、関連するインターネットリソースからエンティティの各々に関連する1組の特徴を抽出する可能性がある。エンティティモジュール16は、インターネットサーバ22(たとえば、ウェブサーバ)に記憶されたウェブページ、ソーシャルメディアの投稿などのインターネットリソースに関してインターネット20をクロールする可能性があり、またはそうでなければ1組のインターネットリソースを受信する可能性があり、そのようなインターネットリソースから特徴を抽出する可能性がある。たとえば、ハイキング旅行に関連するインターネットリソースは、ハイキング旅行を説明するウェブサイトまたはソーシャルメディアの投稿である可能性がある。
【００２６】
一例において、エンティティモジュール16は、エンティティに関連する1つまたは複数の特徴をエンティティに関する1つまたは複数のウェブページから抽出する可能性がある。エンティティに関連する特徴は、関連するエンティティを説明する文脈的情報(contextual information)である可能性がある。特徴は、エンティティに関するウェブページに含まれる単語、語句などのテキストを含み得る。一部の例において、特徴は、画像、動画、およびその他のメディアも含み得る。エンティティモジュール16は、エンティティの記述、ウェブページ内の周辺のテキスト、エンティティが現れるウェブページに関連するクエリ、エンティティに関するウェブページを指すアンカーテキスト、エンティティに関するウェブページの分類上のカテゴリー分けなどの特徴をエンティティに関するウェブページから抽出する可能性がある。
【００２７】
エンティティモジュール16は、インターネットリソースから抽出された特徴、およびエンティティと特徴との間の関連付けの指示を、情報サーバシステム14内のディスク、不揮発性メモリなどのコンピュータ可読ストレージデバイスに記憶し得る。たとえば、エンティティモジュール16は、そのような特徴、およびエンティティと特徴との間の関連付けの指示を、コンマ区切り値、リレーショナルデータベースエントリ、拡張可能マークアップ言語(XML)データ、JavaScript(登録商標)オブジェクト表記法(JSON: JavaScript(登録商標) Object Notation)データなどを含むがこれらに限定されない1つまたは複数のドキュメント、データベースエントリ、またはその他の構造データとして記憶する可能性がある。
【００２８】
エンティティモジュール16は、それぞれのエンティティに関連するインターネットリソースから抽出される各エンティティに関連する1組の特徴に対して特徴の準備を実行する可能性もある。たとえば、エンティティモジュール16は、言語の中で最も一般的な単語(たとえば、英語のa、the、is、at、which、onなど)を取り除くためにストップワードの削除を実行する可能性がある。エンティティモジュール16は、特徴がエンティティに関連するインターネットリソースに現れる頻度に少なくとも部分的に基づいてエンティティに関連する特徴を重み付けするための特徴再重み付けを実行する可能性がある。たとえば、エンティティモジュール16は、エンティティに関連するインターネットリソースにより頻繁に現れる特徴により高い重みを割り当てる可能性がある。エンティティモジュール16は、エンティティに関する特徴のそのような重みを、コンマ区切り値、リレーショナルデータベースエントリ、XMLデータ、JSONデータなどを含むがこれらに限定されない1つまたは複数のドキュメント、データベースエントリ、またはその他の構造データとしてISS 14内のコンピュータ可読ストレージデバイスに記憶する可能性がある。
【００２９】
ランク付けモジュール18は、コンピューティングデバイス2から関心のあるエンティティの指示を受信し、関心のあるエンティティとの1つまたは複数のエンティティの各々の関わりのレベルに少なくとも部分的に基づいて関心のあるエンティティに関連する1つまたは複数のエンティティのランク付けを決定し、コンピューティングデバイス2に1つまたは複数のエンティティの指示を伝達する可能性がある。この目的で、ランク付けモジュール18は、関心のあるエンティティと複数のその他のエンティティの各々との間の類似性の測定値を決定する可能性があり、類似性の測定値は、関わりのレベルに対応する可能性があり、複数のその他のエンティティのうちのどれが関心のあるエンティティに最も関連するかを類似性の測定値に少なくとも部分的に基づいて決定する可能性がある。
【００３０】
一例において、ランク付けモジュール18は、2つのエンティティの特徴の間の類似性を測定し、2つのエンティティのそれぞれの特徴の種類の間の類似性の測定値を組み合わせることに少なくとも部分的に基づいて2つのエンティティの間の類似性の測定値を決定する可能性がある。関心のあるエンティティと目標のエンティティとの間の類似性の測定値を決定するために、ランク付けモジュール18は、関心のあるエンティティに関連するそれぞれの特徴の種類の特徴に関して、関心のあるエンティティの特徴の種類の特徴と目標のエンティティの特徴の種類の特徴との間の類似性の測定値を決定する可能性があり、エンティティの特徴の種類の各々に関する類似性の測定値を組み合わせて関心のあるエンティティと目標のエンティティとの間の類似性の測定値を決定する可能性がある。
【００３１】
別の例において、ランク付けモジュール18は、2つのエンティティがその他の類似したエンティティとの接続を共有するかどうかに少なくとも部分的に基づいて2つのエンティティ(たとえば、関心のあるエンティティおよび目標のエンティティ)の間の類似性の測定値を決定する可能性がある。言い換えると、ランク付けモジュール18は、たとえ2つのエンティティが同じ特徴を共有しないとしても、2つのエンティティの関連する特徴の一部が意味的に関連するので、2つのエンティティが関連すると決定する可能性がある。
【００３２】
この目的で、本開示の態様によれば、ランク付けモジュール18は、様々な非限定的な例において、2部グラフを生成する可能性があり、ランク付けモジュール18は、意味メッセージを受け渡すためにグラフ中に情報を伝搬させる可能性がある。特に、2部グラフは、複数の特徴に関連する複数の特徴ノードに接続される複数のエンティティに関連する複数のエンティティノードを含む可能性があり、複数のエンティティノードの各々は、複数の特徴ノードのうちの1つまたは複数に接続される。したがって、2部グラフにおいて、エンティティに関連付けられるエンティティノードは、エンティティの1つまたは複数の特徴に関連する1つまたは複数の特徴ノードに接続される可能性がある。
【００３３】
ランク付けモジュール18は、関心のあるエンティティに関して、1つまたは複数の関連エンティティに関連する1つまたは複数のエンティティノードの間の2部グラフ内の、関心のあるエンティティに関連するエンティティノードへの接続に少なくとも部分的に基づいて1つまたは複数の関連エンティティを決定し得る。特に、ランク付けモジュール18は、図3A〜図3Cに関連して以下でより詳細に検討されるように、2部グラフの複数のノードの各々にラベルの分布を関連付けるためにラベル伝搬を複数回反復して実行することを含む教師なし機械学習を実行する可能性がある。ランク付けモジュール18は、2部グラフの各ノードに関連付けられるラベルの分布を生成するために目的関数を最小化する最適解としてそのようなラベル伝搬を実行する可能性があり、ラベルの分布は、関連するエンティティノードまたは特徴ノードによって表されるエンティティまたは特徴に関連する1つまたは複数のエンティティのランク付けの指示を含む。このように、ランク付けモジュール18は、関心のある特定のエンティティに関して、関心のあるエンティティに関連する1つまたは複数のエンティティのランク付けを決定し得る。
【００３４】
2部グラフを用いて説明されるが、本開示の態様は、テーブル、データベース、またはその他の基礎をなすデータ構造として実装され得る。したがって、2部グラフのノードおよびエッジは、データ構造の一部、テーブルのエントリ、データベース、関数、変換、あるいはテーブルのエントリ、データベース、もしくはその他の基礎をなすデータ構造にまたはテーブルのエントリ、データベース、もしくはその他の基礎をなすデータ構造の間に適用されるデータとして実装される可能性もある。したがって、本明細書において開示されるように、データ構造、テーブル、データベース、関数、データなどは、1つまたは複数の2部グラフを表す可能性がある。
【００３５】
ランク付けモジュール18は、上述の技術を実行して関心のあるエンティティと複数のその他のエンティティとの間の類似性の測定値(たとえば、類似性スコア)を決定する可能性があり、類似性の決定された測定値に基づいて、関心のあるエンティティとの複数のエンティティの関わりのランク付けを決定する可能性がある。ランク付けモジュール18は、関心のあるエンティティに最も関連するエンティティのうちの1つまたは複数のランク付けされたリストの指示をネットワーク12を介してコンピューティングデバイス2に送信し得る。たとえば、ランク付けモジュール18は、最も関連するエンティティのうちの1つまたは複数のランク付けされたリストに関連するウェブページへのリンクを含むウェブページをコンピューティングデバイス2に送信する可能性がある。それに対応して、コンピューティングデバイス2上で実行されるウェブブラウザが、最も関連するエンティティのうちの1つまたは複数のランク付けされたリストに関連するウェブページへのリンクを含むユーザインターフェース8をUIデバイス4が提示し得るように受信されたウェブページをレンダリングする可能性がある。
【００３６】
本開示の態様によれば、ISS 14は、複数のノードを含むグラフを生成する可能性があり、複数のノードは、複数のエンティティを表す複数のエンティティノードと、複数の特徴を表す複数の特徴ノードとを含み、複数のエンティティノードの各々は、グラフ内で複数の特徴ノードのうちの1つまたは複数に接続される。ISS 14は、複数のノードの各々にラベルの分布を関連付けるためにグラフにわたって複数のラベルを伝搬させるラベル伝搬を実行し得る。ISS 14は、関心のある特徴または関心のあるエンティティのうちの少なくとも一方の指示を受信する可能性がある。ISS 14は、関心のある特徴または関心のあるエンティティのうちの少なくとも一方に関して、関心のある特徴または関心のあるエンティティに関連する1つまたは複数の関連エンティティの指示を出力する可能性があり、1つまたは複数の関連エンティティの指示を出力することは、関心のある特徴を表す複数の特徴ノードのうちの1つ、または関心のあるエンティティを表す複数のエンティティノードのうちの1つに関連するラベルのそれぞれの分布に少なくとも部分的に基づく。本開示のこれらのおよびその他の態様が、下でより詳細に検討される。
【００３７】
図2は、本開示の1つまたは複数の態様による、1組のエンティティの関わりのレベルを決定するように構成された例示的なコンピューティングシステムとしてISS 14を示すブロック図である。図2は、ISS 14の1つの特定の例のみを示し、ISS 14の多くのその他の例が、その他の場合に使用される可能性があり、例示的なISS 14に含まれる構成要素のサブセットを含む可能性があり、または図2に示されていないさらなる構成要素を含む可能性がある。
【００３８】
ISS 14は、コンピューティングデバイス2などのコンピューティングデバイスが関心のあるエンティティまたは関心のある特徴に関する1つまたは複数の関連エンティティを示す情報を自動的に受信するために関連エンティティサービスにアクセスし得る通信路をコンピューティングデバイス2に提供する。図2の例に示されるように、ISS 14は、1つまたは複数のプロセッサ44、1つまたは複数の通信ユニット46、および1つまたは複数のストレージデバイス48を含む。ISS 14のストレージデバイス48は、エンティティモジュール16およびランク付けモジュール18を含む。
【００３９】
ISS 14のストレージデバイス48は、特徴-エンティティデータストア52A、グラフデータストア52B、ランク付けデータストア52C、およびインターネットリソースデータストア52D(集合的に「データストア52」)をさらに含む。通信チャネル50は、構成要素間通信のために(物理的に、通信可能なように、および/または動作可能なように)構成要素44、46、および48の各々を相互に接続し得る。一部の例において、通信チャネル50は、システムバス、ネットワーク接続、プロセス間通信データ構造、またはデータを伝達するための任意のその他の方法を含み得る。
【００４０】
ISS 14の1つまたは複数の通信ユニット46は、図1のネットワーク12またはインターネット20などの1つまたは複数のネットワーク上でネットワーク信号を送信および/または受信することによって図1のコンピューティングデバイス2などの外部コンピューティングデバイスと通信し得る。たとえば、ISS 14は、コンピューティングデバイス2と情報をやりとりするために通信ユニット46を使用してネットワーク12を介して無線信号を送信および/または受信し得る。通信ユニット46の例は、(たとえば、イーサネット(登録商標)カードなどの)ネットワークインターフェースカード、光トランシーバ、無線周波数トランシーバ、GPS受信機、または情報を送信および/もしくは受信することができる任意のその他の種類のデバイスを含む。通信ユニット46のその他の例は、短波無線、セルラデータ無線、ワイヤレスイーサネット(登録商標)ネットワーク無線、およびユニバーサルシリアルバス(USB)コントローラを含み得る。
【００４１】
ストレージデバイス48は、ISS 14の動作中に処理するための情報を記憶し得る(たとえば、ISS 14は、ISS 14における実行中にモジュール16および18によってアクセスされるデータを記憶し得る)。一部の例において、ストレージデバイス48は一時的メモリであり、つまり、ストレージデバイス48の主目的は長期的な記憶ではない。ISS 14のストレージデバイス48は、揮発性メモリとして情報の短期記憶のために構成され、したがって、電源がオフにされた場合、記憶されたコンテンツを保たない可能性がある。揮発性メモリの例は、ランダムアクセスメモリ(RAM)、ダイナミックランダムアクセスメモリ(DRAM)、スタティックランダムアクセスメモリ(SRAM)、および当技術分野で知られているその他の形態の揮発性メモリを含む。
【００４２】
一部の例において、さらに、ストレージデバイス48は、1つまたは複数のコンピュータ可読ストレージ媒体を含む。ストレージデバイス48は、揮発性メモリよりも多くの量の情報を記憶するように構成され得る。さらに、ストレージデバイス48は、不揮発性メモリ空間として情報の長期記憶のために構成され、電源のオン/オフのサイクルの後に情報を保つ可能性がある。不揮発性メモリの例は、磁気ハードディスク、光ディスク、フロッピー(登録商標)ディスク、フラッシュメモリ、または電気的にプログラミング可能なメモリ(EPROM)もしくは電気的に消去可能でありプログラミング可能である(EEPROM)メモリの形態を含む。ストレージデバイス48は、モジュール16および18に関連するプログラム命令および/またはデータを記憶し得る。
【００４３】
1つまたは複数のプロセッサ44は、ISS 14内で機能を実施し得るおよび/または命令を実行し得る。たとえば、ISS 14のプロセッサ44は、モジュール16および18の機能を実行するストレージデバイス48によって記憶された命令を受け取り、実行し得る。プロセッサ44によって実行されるとき、これらの命令は、ISS 14にプログラムの実行中にストレージデバイス48内に情報を記憶させ得る。プロセッサ44は、モジュール16および18の命令を実行して、複数のインターネットソースから複数のエンティティに関連する複数の特徴を抽出し、エンティティの各々の間の関わりのレベルを決定し、関心のある特定のエンティティまたは関心のある特定の特徴に関する1つまたは複数の関連エンティティのランク付けを出力し得る。つまり、モジュール16および18は、本明細書において説明されるISS 14の様々な行為または機能を実行するためにプロセッサ44によって動作可能である可能性がある。
【００４４】
データストア52に記憶された情報は、検索可能であるおよび/またはカテゴリー分けされる構造化されたデータとして記憶される可能性がある。たとえば、1つまたは複数のモジュール16および18は、データストア52にデータを記憶する可能性がある。1つまたは複数のモジュール16および18は、データストア52のうちの1つまたは複数からの情報を要求する入力を与え、入力に応答して、データストア52に記憶された情報を受け取る可能性もある。ISS 14は、コンピューティングデバイス2などのネットワーク12またはインターネット20に接続されたデバイスに、データストア52に記憶された情報へのアクセスを、クラウドに基づくデータアクセスサービスとして提供する可能性がある。データストア52が個々のユーザに関連する情報を含むとき、または情報が複数のユーザの間で不特定化されるとき、情報を個々の人に再びリンクする、名前、住所、電話番号、および/または電子メールアドレスなどのすべての個人を特定し得る情報は、ISS 14に記憶される前に削除される可能性がある。さらに、ISS 14は、ISS 14に記憶された任意の情報へのアクセスを防止するためにデータストア52に記憶される情報を暗号化する可能性がある。加えて、ISS 14は、コンピューティングデバイスのユーザが情報のそのような集合に積極的に同意する場合にのみそれらのユーザに関連する情報を記憶する可能性がある。さらに、ISS 14は、ユーザが同意を撤回する機会を与える可能性があり、その場合、ISS 14は、その特定のユーザに関連する情報を収集することまたはそうではなく保持することをやめる可能性がある。
【００４５】
エンティティモジュール16は、インターネット20を介してインターネットサーバ22などからインターネットリソースを取り出すか、受信するか、またはそうではなく取得し、インターネットリソースに関連するリソース情報を取り出すか、受信するか、またはそうではなく取得する可能性があり、インターネットリソースおよびインターネットリソースに関連するリソース情報をインターネットリソースデータストア52Dに記憶する可能性がある。
【００４６】
エンティティモジュール16によって取得されるインターネットリソースは、一部の例において、ドキュメントに関してインターネット20をクロールすることによって取得されるドキュメント(たとえば、ウェブページ)である可能性がある。一部の例において、エンティティモジュール16は、インターネットリソースをインターネットリソースデータストア52Dに記憶しない可能性がある。その代わりに、インターネットリソースは、エンティティモジュール16がインターネット20を介して通信し得る1つまたは複数のリモートコンピューティングデバイス(図示せず)などの他の場所に記憶される可能性がある。
【００４７】
インターネットリソースに関連するリソース情報は、インターネットリソース自体の本体に含まれない可能性があるインターネットリソースについての文脈情報(context information)を含み得る。たとえば、特定のインターネットリソースに関連するリソース情報は、検索結果に含まれるインターネットリソースへのリンクを介してインターネットリソースを訪問する結果となるインターネット検索エンジンに発行されたクエリを含み得る。別の例において、特定のインターネットリソースに関連するリソース情報は、別のインターネットリソースからインターネットリソースへのリンクのアンカーテキストを含み得る。別の例において、特定のインターネットリソースに関連するリソース情報は、インターネットリソースの分類上のカテゴリー分けを含み得る。
【００４８】
エンティティモジュール16によって取得されるインターネットリソースは、各エンティティが1つまたは複数のインターネットリソースに関連付けられ得るような複数のエンティティに関連付けられる可能性がある。エンティティは、一部の例においては、イベント、場所、人、会社、映画、レストランなどである可能性がある。エンティティは、記述、場所、および時間のうちの1つまたは複数にさらに関連付けられる可能性がある。エンティティの記述は、一部の例において、イベントの題名、会社の名前などである可能性がある。場所は、イベントの場所、会社の場所などの地理的な場所である可能性がある。時間は、一部の例において、イベントが行われる時間である可能性がある。
【００４９】
特定のエンティティに関連付けられるインターネットリソースは、特定のエンティティを説明する可能性がある。たとえば、特定のエンティティがイベントである場合、特定のエンティティに関連付けられるインターネットリソースは、イベントに関するウェブページ、イベントに関するソーシャルメディアの投稿、イベントが開かれる開催地に関するウェブサイトなどである可能性がある。
【００５０】
エンティティモジュール16は、少なくともエンティティモジュール16によって取得されたインターネットリソースから複数のエンティティを抽出する可能性があり、複数のエンティティの各エンティティに関して、特定のエンティティに関連付けられる1つまたは複数のインターネットリソースを決定する可能性がある。エンティティモジュール16は、複数のエンティティの各々に関して、少なくとも特定のエンティティに関連付けられる1つまたは複数のインターネットリソースおよび1つまたは複数のインターネットリソースに関連するリソース情報からエンティティに関連する1つまたは複数の特徴を抽出する可能性がある。エンティティに関連する1つまたは複数の特徴は、エンティティを説明する文脈的情報を含む可能性がある。一部の例において、特徴は、単語、語句、文などのテキスト情報を含む可能性がある。たとえば、エンティティモジュール16は、音楽のコンサートに関連するウェブページから、「Beethoven」、「symphony」、「concerto」、「orchestra」、「conductor」、「pianist」、「concertmaster」、「violinist」などの単語および語句を、音楽のコンサートを説明するかまたはそうでなければ音楽のコンサートに関連付けられる特徴として抽出する可能性がある。
【００５１】
特定のエンティティに関してエンティティモジュール16によって抽出された特徴は、関連するエンティティを説明する情報の種類に対応する1つまたは複数の特徴のカテゴリーにカテゴリー分けされる可能性がある。1組の特徴のカテゴリーは、題名、周辺、クエリ、アンカー、および分類法のうちの1つまたは複数を含む可能性がある。エンティティに関連する1つまたは複数のインターネットリソース(たとえば、1つまたは複数のウェブページ)の題名または見出しから抽出された1つまたは複数の特徴は、特徴題名カテゴリーに属するものとしてカテゴリー分けされる可能性があり、エンティティを説明する1つまたは2つの文を含む可能性がある。エンティティに関連する1つまたは複数のウェブページの本文などの1つまたは複数のインターネットリソースに含まれる周辺のテキストから抽出される1つまたは複数の特徴は、周辺特徴カテゴリーに属するものとしてカテゴリー分けされる可能性がある。
【００５２】
クエリ特徴カテゴリーは、検索結果に含まれる1つまたは複数のインターネットリソースへのリンクを介して、エンティティによって関連付けられる1つまたは複数のインターネットリソースを訪問する結果となるインターネット検索エンジンに発行されたクエリから抽出された1つまたは複数の特徴を含み得る。たとえば、エンティティモジュール16は、音楽のコンサートに関するウェブページを訪問する結果となった問い合わせ「classical music concerts」をクエリ特徴カテゴリーに属する特徴「classical」、「music」、および「concerts」としてカテゴリー分けする可能性がある。
【００５３】
アンカー特徴カテゴリーは、別のインターネットリソースからエンティティに関連する1つまたは複数のインターネットリソースへのリンクのアンカーテキストから抽出された1つまたは複数の特徴を含み得る。したがって、一例において、ウェブページが音楽のコンサートであるエンティティに関するウェブページにリンクする「classical concert」というアンカーを含む場合、エンティティモジュール16は、アンカーテキスト「classical concert」を、音楽のコンサートに関連するエンティティに関するアンカー特徴カテゴリーに属する特徴「classical」および「concert」として分類する可能性がある。
【００５４】
分類法特徴カテゴリーは、エンティティに関連する1つまたは複数のインターネットリソースの分類上のカテゴリー分けから抽出された1つまたは複数の特徴を含み得る。エンティティモジュール16は、エンティティに関連する1つまたは複数のインターネットリソースの各々を、スポーツおよびアートなどの比較的高いレベルのカテゴリーからゴルフおよびロックミュージックなどの比較的低いレベルのカテゴリーまで、1つまたは複数のカテゴリーに関連付けられるものとしてラベル付けするためにインターネットソースの分類上のカテゴリー分けを実行し得る。
【００５５】
エンティティモジュール16は、各エンティティに関して、特徴値を特定のエンティティに関連するそれぞれの異なる特徴に関連付け得る。エンティティに関連付けられる特徴に関連する特徴値は、エンティティに関連する1つまたは複数のインターネットリソースおよび1つまたは複数のインターネットソースに関連するリソース情報から同じ特徴が抽出される回数に対応する可能性がある。たとえば、音楽イベントであるエンティティに関して、特徴「concert」は、1つまたは複数のインターネットリソースの題名およびインターネットリソースの本文などに何度も現れる可能性がある。エンティティモジュール16は、リソースの単一のインスタンスをエンティティに関連付けることによって、およびエンティティに関連する1つまたは複数のインターネットリソースおよび1つまたは複数のインターネットソースに関連するリソース情報から同じ特徴が抽出される回数に対応する特徴値をそのエンティティに割り当てることによって、エンティティに関連する1つまたは複数のインターネットリソースおよび1つまたは複数のインターネットソースに関連するリソース情報から複数回抽出される同じイベントの重複を取り除く可能性がある。
【００５６】
インターネットリソースから特徴を抽出し、インターネットリソースから関連するリソース情報を抽出した結果として、エンティティモジュール16は、1つまたは複数の特徴を複数のエンティティの各々に関連付ける可能性があり、1つまたは複数の特徴は、対応するエンティティに関する文脈的情報を説明するかまたはそうでなければ提供するテキスト情報である可能性がある。特徴を特徴のカテゴリーにカテゴリー分けすることによって、各エンティティは、特徴のカテゴリーのうちの1つまたは複数に関連付けられる可能性があり、それぞれの関連するカテゴリーに関して、その特徴のカテゴリー内の1つまたは複数の特徴に関連付けられる可能性がある。一部の例において、エンティティは、上述の5つの特徴のカテゴリーの各々の特徴に関連付けられる可能性がある。その他の例において、エンティティは、上述の5つの特徴のカテゴリーのうちの一部の特徴に関連付けられる可能性がある。さらなる例において、エンティティは、上述の特徴のカテゴリー以外の1つまたは複数のさらなる特徴のカテゴリーの特徴に関連付けられる可能性がある。
【００５７】
エンティティモジュール16は、各エンティティに関して、エンティティと、インターネットリソースから抽出された特徴とを処理するための特徴処理を実行し得る。たとえば、特徴は、エンティティモジュール16が特徴の語幹処理(stemming)を実行する(たとえば、Porterステマー(Porter stemmer)を適用する)ために、テキスト情報を含む可能性があり、語幹処理された特徴をユニグラムおよびバイグラムの特徴に変換する可能性がある。
【００５８】
エンティティモジュール16は、同じ名前または題名を有するエンティティの重複を取り除くことになどによってエンティティの重複除去を実行する可能性もあり、重複するイベントに関連する特徴をマージするための特徴のマージを実行する可能性がある。上で検討されたように、重複するイベントに関連する各特徴は、それらのイベントがそれぞれの特徴のカテゴリーに現れる頻度に対応する可能性がある関連する特徴値を有する可能性がある。たとえば、単語「jazz」が特定のイベントに関して周辺特徴カテゴリーに複数回現れる特徴である場合、特徴「jazz」の特徴値は、エンティティに関連する1つまたは複数のインターネットリソースに含まれる周辺のテキストに単語「jazz」が現れる回数に対応する可能性がある。重複するイベントの特徴をマージするために、エンティティモジュール16は、それらの特徴が題名、周辺、クエリ、およびアンカー特徴カテゴリーに入る場合、マージされる特徴の特徴値を、両方のエンティティの同じ特徴の特徴値の合計として決定する可能性がある。エンティティモジュール16は、分類法特徴カテゴリーに入るエンティティに関して、マージされる特徴の特徴値を、両方のエンティティの同じ特徴の特徴値のうちの最大として決定する可能性もある。
【００５９】
エンティティモジュール16は、特徴処理の一部として、情報を取り出す際に特徴のノイズを削減するためにストップワードの削除および特徴再重み付けを実行する可能性もある。ストップワードの削除は、大域的なストップワードの削除と局所的なストップワードの削除との両方を含む可能性がある。大域的なストップワードの削除を実行するために、エンティティモジュール16は、特定の特徴に関連付けられるエンティティの数である可能性がある、抽出された特徴の各々の特徴頻度を決定する可能性がある。エンティティモジュール16は、比較的高い特徴頻度を有する特徴(たとえば、閾値を超える数のエンティティに関連する特徴、関連する特徴頻度のうちの上位10パーセント以内の特徴など)が大域的なストップワードである可能性があると判定する可能性があり、エンティティからそれらの特徴を取り除くかまたはそうでなければエンティティとのそれらの特徴の関連付けを解除する可能性がある。
【００６０】
エンティティモジュール16は、局所的なストップワードを取り除くために局所的なストップワードの削除も実行する可能性がある。局所的なストップワードは、大域的なストップワードの削除を実行した後に残っている特定の領域のエンティティに関する頻度の高い特徴である可能性がある。上で検討されたように、各エンティティは、関連する地理的な場所または地理的な領域を有する可能性がある。たとえば、ニューヨークなどの特定の場所のエンティティに焦点を当てるとき、ニューヨークからの多くのエンティティが語句「New York」を含む可能性があり、語句「New York」はストップワードの削除中に削除されない可能性がある。エンティティモジュール16は、指定された地理的な場所(たとえば、ニューヨーク)に関して、その特定の地理的な場所内のエンティティに関する特徴として頻繁に現れる可能性がある単語または語句を削除するために局所的なストップワードの削除を実行する可能性がある。したがって、エンティティモジュール16は、地理的な場所に関連する特定のエリア内の特徴頻度を決定し、地理的な場所に関連するストップワードを取り除くことによってエンティティの関連する地理的な場所に関する局所的なストップワードの削除を実行する可能性がある。
【００６１】
エンティティモジュール16は、各エンティティに関して、それぞれのエンティティに関する各特徴の特徴頻度に少なくとも部分的に基づくエンティティに関連する各特徴の特徴重みを決定することによってエンティティに関連する1つまたは複数の特徴の特徴再重み付けをさらに実行する可能性がある。言い換えると、エンティティモジュール16は、特定の特徴が特定のエンティティに関連するとき、特定の特徴の特徴値に少なくとも部分的に基づいて特定のエンティティに関連する特定の特徴を再重み付けする可能性がある。特徴が複数のエンティティに関連付けられる場合、エンティティモジュール16は、そのような特徴がその特徴が関連付けられる各エンティティにつき1つずつ複数の特徴重みに関連付けられ得るように、それぞれの特徴-エンティティのペアに関して別々の特徴重みを決定する可能性がある。
【００６２】
特徴再重み付けを実行することは、各エンティティに関して、ストップワードの削除を実行した後でさえも特徴頻度の潜在的に歪んだ分布が原因で、エンティティに関して高い特徴値を有する頻度の高い特徴を縮小することと、エンティティに関して低い特徴値を有する特徴を拡大することとを含む可能性がある。エンティティの各特徴の頻度に関して、エンティティモジュール16は、頻度を対数スケール化し、対数スケール化された頻度にその逆文書頻度(inverse document frequency)を掛けることによって対数正規化された(log-noemalized)単語の出現頻度-逆文書頻度(TF-IDF:term frequency-inverse document frequency)を適用して、次、すなわち、
【００６３】
【数１】
2019514149.tif 000003
【００６４】
のようにエンティティi内の特定の特徴jに関する重みを決定する可能性があり、式中、weightijは、エンティティiに関連する特徴jの特徴重みである可能性があり、tfijは、エンティティに関する特徴の特徴値などの、エンティティi内の特徴jの頻度である可能性があり、Nは、集合のサイズ(つまり、エンティティの総数)である可能性があり、dfjは、特徴jが現れるエンティティの数である可能性がある。このようにして、エンティティモジュール16は、各エンティティに関して、特定のエンティティに関連する各特徴に関する重みを決定し得る。
【００６５】
エンティティモジュール16は、エンティティに関連する各特徴に関する特徴重みだけでなく、エンティティと、インターネットリソースから抽出された各エンティティに関する特徴と、特徴のカテゴリーとの間の関連付けの指示を特徴-エンティティデータストア52Aに記憶する可能性がある。たとえば、各エンティティに関して、エンティティモジュール16は、少なくとも、構造化されたデータに関連する1つまたは複数の特徴、1つまたは複数の特徴の各々の特徴重み、および1つまたは複数の特徴が入る1つまたは複数の特徴のカテゴリーを構造化されたデータとして記憶する可能性がある。さらに、エンティティモジュール16は、エンティティの各々に関連する地理的な場所などのエンティティに関連する任意の追加的な情報または任意のその他の好適な情報を特徴-エンティティデータストア52Aに記憶する可能性がある。
【００６６】
ランク付けモジュール18は、特定のエンティティに関して、特定のエンティティに関連する1つまたは複数のエンティティのランク付けを決定し得る。特定のエンティティに関連する1つまたは複数のエンティティのランク付けは、特徴-エンティティデータストア52Aに記憶された1組のエンティティの中で特定のエンティティと最も高いレベルの関わりを有する1つまたは複数のエンティティの指示である可能性がある。1組のエンティティの中の各エンティティがそれぞれのエンティティと特定のエンティティとの間の関わりのレベルを示す関連する類似性スコアをそれぞれ有する場合、特定のエンティティに関連する1つまたは複数のエンティティは、特定のエンティティに関して1組のエンティティの中で最も高い類似性スコアを有する1つまたは複数のエンティティである可能性がある。言い換えると、特定のエンティティに関心を持っている無作為のユーザを考えたとき、特定のエンティティに関連する1つまたは複数のエンティティは、特徴-エンティティデータストア52Aに記憶された1組のエンティティの中で同じ無作為のユーザが最も関心がある1つまたは複数のエンティティである可能性がある。
【００６７】
一部の例において、ランク付けモジュール18は、特徴-エンティティデータストア52Aに記憶されたエンティティの各々の間の関わりのレベル(たとえば、類似性スコア)を決定し得る。したがって、この例においては、特徴-エンティティデータストア52Aに記憶された各エンティティに関して、ランク付けモジュール18が、特定のエンティティと特徴-エンティティデータストア52Aに記憶されたそれぞれのその他のエンティティとの間の関わりのレベルを決定し得る。
【００６８】
その他の例においては、特定のエンティティに関心のあるユーザが同じ地理的エリア内にあるその他のエンティティにのみ関心がある可能性もあるので、特徴-エンティティデータストア52Aに記憶されたエンティティの各々の間の関わりのレベルを決定するのではなく、ランク付けモジュール18は、その代わりに、同じ地理的な領域もしくは場所の中にあるかまたは同じ地理的な領域もしくは場所に関連付けられる特徴-エンティティデータストア52A記憶されたエンティティの間でのみ関わりを決定する可能性がある。ランク付けモジュール18は、エンティティに関連する地理的な場所に少なくとも部分的に基づいて、エンティティが同じ地理的な領域内にあるかどうかを判定する可能性がある。このようにして、この例において、ランク付けモジュール18は、特徴-エンティティデータストア52Aに記憶されたエンティティのサブセット(たとえば、一部)の各々の間の関わりのレベル(たとえば、類似性スコア)を決定する可能性がある。
【００６９】
一例において、ランク付けモジュール18は、1組のエンティティの各々に関連する1つまたは複数のエンティティのランク付けを決定するためにコンバイナ(combiner)技術を実行する可能性がある。ランク付けモジュール18は、特徴-エンティティデータストア52Aに記憶された1組のエンティティの各エンティティの間の関わりのレベルを決定するためにコンバイナ技術を実行する可能性がある。たとえば、ランク付けモジュール18は、特徴-エンティティデータストア52Aに記憶された同じ地理的な領域または地理的な場所に関連する1組のエンティティの各エンティティの間の関わりのレベルを決定する可能性がある。ソースエンティティと呼ばれる可能性がある特定のエンティティに関して、ランク付けモジュール18は、ソースエンティティとターゲットエンティティと呼ばれる可能性がある別のエンティティとの間の関わりのレベルを、ソースエンティティとターゲットエンティティとの間の同じ1組の特徴のカテゴリーの特徴の類似性のレベルを決定することによって決定する可能性がある。
【００７０】
ソースエンティティおよびターゲットエンティティに関連するk個の特徴のカテゴリーのリストを仮定して、
【００７１】
【数２】
2019514149.tif 000004
【００７２】
は、ソースエンティティSに関する特徴のカテゴリーjに属する1組の特徴である可能性があり、
【００７３】
【数３】
2019514149.tif 000005
【００７４】
は、ターゲットエンティティTに関する特徴のカテゴリーjから抽出された1組の特徴である可能性がある。特定の特徴のカテゴリーjに関して、ランク付けモジュール18は、ソースエンティティSとターゲットエンティティTとの間の類似性スコアを
【００７５】
【数４】
2019514149.tif 000006
【００７６】
として決定する可能性があり、式中、sc()は、類似性スコア関数であり、類似性スコアは、その特徴のカテゴリーに関するソースエンティティとターゲットエンティティとの間の類似性のレベルに対応する。
【００７７】
より詳細には、特定の特徴のカテゴリーに関するソースエンティティSとターゲットエンティティTとの間の類似性スコアを決定するために、ランク付けモジュール18は、各エンティティを特徴の分布として扱う可能性がある。その目的のために、ランク付けモジュール18は、Kullback-Leiblerダイバージェンス(Kullback-Leibler divergence)の対称バージョンである可能性があるJeffreys-Kullback-Leiblerダイバージェンス(Jeffreys-Kullback-Leibler divergence)を利用して、ソースおよびターゲットエンティティの特徴の分布の間の差の測定値を決定し得る。1組の特徴
【００７８】
【数５】
2019514149.tif 000007
【００７９】
が与えられると、ランク付けモジュール18は、特徴のカテゴリーjに関するソースエンティティSとターゲットエンティティTとの間の類似性を
【００８０】
【数６】
2019514149.tif 000008
【００８１】
として定義する可能性があり、式中、D(・||・)は、Kullback-Leiblerダイバージェンスである。このようにして、ランク付けモジュール18は、ソースエンティティとターゲットエンティティとの間のそれぞれの特徴のカテゴリーに関する類似性スコアを決定するためにコンバイナ技術を実行し得る。
【００８２】
ランク付けモジュール18は、k個の特徴のカテゴリーの各々に関するソースエンティティSとターゲットエンティティTとの間の類似性スコアを
【００８３】
【数７】
2019514149.tif 000009
【００８４】
のように決定するためにコンバイナ技術を実行し得る。ソースエンティティとターゲットエンティティとの間のそれぞれの特徴のカテゴリーに関する類似性スコアに基づいて、ランク付けモジュール18は、ソースイベントとターゲットイベントとの間の全体的な類似性スコアを、ソースエンティティとターゲットエンティティとの間のそれぞれの特徴のカテゴリーに関する類似性スコアの集約として決定し得る。特に、ランク付けモジュール18は、特徴のカテゴリーの各々に関する類似性スコアに基づいて、ソースエンティティSとターゲットエンティティTとの間の全体的な類似性スコアを
【００８５】
【数８】
2019514149.tif 000010
【００８６】
として決定する可能性があり、式中、φは、集約関数である可能性がある。
【００８７】
特徴のカテゴリーjが与えられたときのソースエンティティSおよびターゲットエンティティTに関する類似性スコアは、rjと表記される可能性がある。ランク付けモジュール18は、逆ランク融合(Reciprocal Rank Fusion)によってソースエンティティSおよびターゲットエンティティTの特徴のカテゴリーの各々に関する類似性スコアを単一のランク付けリストへと組み合わせ得る。ターゲットエンティティTがソースエンティティSに関して類似性スコア
【００８８】
【数９】
2019514149.tif 000011
【００８９】
に関連付けられるものとすると、ソースエンティティSとターゲットエンティティTとの間の全体的な類似性スコアsc(S, T)は、
【００９０】
【数１０】
2019514149.tif 000012
【００９１】
として表される可能性があり、式中、jは、特徴のカテゴリーの各々である可能性があり、Kは、アウトライナランカー(outlier ranker)によって高いランク付けの付与の影響を小さくする大きな予め定義された定数である可能性がある。一例において、Kは60である可能性がある。
【００９２】
したがって、ランク付けモジュール18は、コンバイナ技術を実行することによって、2つのエンティティの特徴の間の類似性の集約に少なくとも部分的に基づいて2つのエンティティの間の関わりのレベルを決定し得る。上で検討されたように、ランク付けモジュール18は、特徴-エンティティデータストア52Aに記憶されたエンティティの中の1組のエンティティの各々の間の関わりのレベルを決定する可能性があり、ランク付けモジュール18によって決定された1組のエンティティの各々の間の関わりのレベルの指示をランク付けデータストア52Cに記憶する可能性がある。たとえば、ランク付けデータストア52Cは、類似性スコアなどの関わりの関連するレベルの指示と一緒にエンティティのペアの指示をランク付けデータストア52Cに記憶する可能性がある。
【００９３】
その他の例において、ランク付けモジュール18は、1組のエンティティの各々に関して、特徴-エンティティデータストア52Aに記憶されたエンティティの中の1組のエンティティの各々の間の関わりのレベルに基づいて、1組のエンティティの中で特定のエンティティと最も高いレベルの関わりを有する1つまたは複数のエンティティのランク付けなどの、特定のエンティティに関連する1つまたは複数のエンティティのランク付けを決定する可能性があり、1組のエンティティの中の各エンティティに関連する1つまたは複数エンティティのランク付けのそのような指示をランク付けデータストア52Cに記憶する可能性がある。
【００９４】
このようにして、ISS 14は、たとえば、コンピューティングデバイス2からエンティティの指示を受信し、ランク付けデータストア52Cに記憶されたデータから、特定のエンティティに関連する1つまたは複数のエンティティのランク付けを決定し、特定のエンティティに関連する1つまたは複数のエンティティのランク付けの指示をコンピューティングデバイス2に送信し得る。一例において、ISS 14がコンピューティングデバイス2から受信するエンティティの指示は、「Miles Davis」または「Beethoven's 5th Symphony」などのエンティティに関連する名前を示す可能性がある。ランク付けモジュール18は、その名前に関連するエンティティを見つけるためにランク付けデータストア52Cにインデックスを付けるためにエンティティに関連する名前を利用する可能性があり、特定のエンティティに関連する1つまたは複数のエンティティの指示のランク付けが記憶されるランク付けデータストア52C内の場所を決定する可能性がある。ランク付けモジュール18は、特定のエンティティに関連する1つまたは複数のエンティティのランク付けの指示を取り出し得る。ISS 14は、特定のエンティティに関連する1つまたは複数のエンティティのランク付けの取り出された指示を、JSONまたはXMLなどの1つまたは複数のエンティティのランク付けの指示を送信するための任意の好適な構造化されたデータフォーマットへとフォーマットする可能性があり、ネットワーク12またはインターネット20などを介して1つまたは複数のエンティティの指示をコンピューティングデバイス2に出力する可能性がある。
【００９５】
その他の例においては、ランク付けデータストア52Cから特定のエンティティに関連する1つまたは複数のエンティティのランク付けを取り出す代わりに、ISS 14は、たとえば、コンピューティングデバイス2からエンティティの指示を受信することに応じて、本明細書において説明されるコンバイナ技術を使用して特定のエンティティに関連する1つまたは複数のエンティティのランク付けをオンザフライで決定し、本明細書において説明される技術を使用してネットワーク12またはインターネット20などを介して1つまたは複数のエンティティのランク付けの指示をコンピューティングデバイス2に出力する可能性がある。
【００９６】
別の例において、ISS 14は、たとえば、コンピューティングデバイス2からクエリの指示を受信する可能性がある。クエリは、コンピューティングデバイス2が入力として受け取り得る単語、語句などのテキストデータである可能性がある。たとえば、クエリは、クエリに関連する1つまたは複数のエンティティに関する検索語句である可能性がある。クエリの指示を受信することに応じて、コンピューティングデバイス2は、クエリに関連する1つまたは複数のエンティティのランク付けをランク付けモジュール18によって決定する可能性があり、クエリに関連する1つまたは複数のエンティティのランク付けの指示をコンピューティングデバイス2に出力する可能性がある。
【００９７】
特に、コンピューティングデバイス2が「marathon」などのクエリの指示を受信することに応じて、ランク付けモジュール18は、ランク付けモジュール18は、本明細書において説明されるコンバイナ技術を実行することに少なくとも部分的に基づいて、検索語句に対する1つまたは複数の関連エンティティのランク付けを決定し得る。ランク付けモジュール18は、発行されたクエリに一致するエンティティの名前または題名をそれぞれが有する1組の1つまたは複数のエンティティをシードセットSとして決定し得る。ランク付けモジュール18は、これらのシードエンティティを使用して、シードエンティティを含むシードセットS内の各エンティティに関連する1つまたは複数のエンティティを1組の候補エンティティCSとして決定し得る。ランク付けモジュール18は、1組の候補エンティティCS内の候補エンティティをそれらの候補エンティティのそれぞれの類似性スコアによってランク付けし得る。1組の候補エンティティ内のエンティティが異なるシードエンティティから複数回取り出される場合、ランク付けモジュール18は、エンティティがシードセットS内のエンティティのうちの2つ以上に関連すると判定するので、そのエンティティに関する単一の類似性スコアをもたらすようにそのエンティティの類似性スコアを合計し得る。より形式的には、クエリQに対するターゲットエンティティTの類似性は、
【００９８】
【数１１】
2019514149.tif 000013
【００９９】
として定義される可能性があり、式中、sc(S, T)は、本明細書において開示されるコンバイナ技術によってランク付けモジュール18により計算され得る。ランク付けモジュール18は、候補エンティティCS内のエンティティに関連する類似性スコアからクエリに関連する1つまたは複数のエンティティのランク付けを決定する可能性があり、本明細書において説明される技術を使用してネットワーク12またはインターネット20などを介して1つまたは複数のエンティティのランク付けの指示をコンピューティングデバイス2に出力する可能性がある。
【０１００】
別の例において、ランク付けモジュール18は、1組のエンティティの各々に関連する1つまたは複数のエンティティのランク付けを決定するためにエキスパンダ技術を実行する可能性がある。ランク付けモジュール18は、特徴-エンティティデータストア52Aに記憶された1組のエンティティのうちの各エンティティの間の関わりのレベルを決定するためにエキスパンダ技術を実行する可能性がある。特に、ランク付けモジュール18は、2つのエンティティの特徴の間の意味的関わりを決定することに少なくとも部分的に基づいて2つのエンティティの所与のペアの間の関わりのレベルを決定するためにエキスパンダ技術を実行する可能性がある。たとえば、ランク付けモジュール18は、たとえ2つのエンティティが上で検討されたコンバイナ技術を実行することに基づく類似性の比較的低い測定値を有するとしても、それらの2つのエンティティが両方とも第三者エンティティによく似ている場合、2つのエンティティがよく似ていると判定する可能性がある。
【０１０１】
この目的のために、ランク付けモジュール18は、特徴およびエンティティがノードとして表される特徴-エンティティ2部グラフ(図3A〜図3Cに関連してさらに詳細に検討される)を生成し得る。特に、グラフは、複数の特徴を表す特徴ノードおよび複数のエンティティを表すエンティティノードを含む複数のノードを含み得る。グラフ内のエンティティノードの各々は、エッジ重みを有する1つまたは複数のエッジによって特徴ノードのうちの1つまたは複数に接続される可能性があり、エンティティノードは、エンティティノードによって表されるエンティティが特徴ノードによって表される特徴に関連付けられる場合、特徴ノードに接続される可能性がある。
【０１０２】
ランク付けモジュール18は、ランク付けモジュール18によって生成された特徴-エンティティ2部グラフの指示を、配列、データベースレコード、レジスタなどの1つまたは複数のデータ構造を含む可能性があるグラフデータストア52Bにデータとして記憶する可能性がある。たとえば、ランク付けモジュール18は、複数の特徴ノード、複数のエンティティノード、エンティティノードの各々を特徴ノードのうちの1つまたは複数に接続する1つまたは複数のエッジ、1つまたは複数のエッジのエッジ重みなどを示すデータをグラフデータストア52Bに記憶する可能性がある。一例において、特徴-エンティティ2部グラフの各エンティティノードに関して、ランク付けモジュール18は、エンティティノードによって表されるエンティティを示すデータ、エンティティノードに接続された1つもしくは複数の特徴ノードを示すデータ、および/またはエンティティノードを1つもしくは複数の特徴ノードの各々に接続する1つもしくは複数のエッジのエッジ重みの値をグラフデータストア52Bに記憶する可能性がある。同様に、特徴-エンティティ2部グラフの各特徴ノードに関して、ランク付けモジュール18は、特徴ノードによって表される特徴を示すデータをグラフデータストア52Bに記憶する可能性がある。
【０１０３】
本開示全体を通じて、特徴-エンティティ2部グラフまたはグラフという用語は、特徴-エンティティ2部グラフを示すグラフデータストア52Bに記憶されたデータと同義である可能性がある。言い換えると、本開示は特徴-エンティティ2部グラフに対してモジュール16および18によって実行される動作を説明する可能性があるが、モジュール16および18は、実際には、特徴-エンティティ2部グラフを構成する特徴ノード、エンティティノード、エッジ、エッジ重み、エッジによる特徴ノードのうちの1つまたは複数へのエンティティノードの各々の接続などの、特徴-エンティティ2部グラフを示すグラフデータストア52Bに記憶されたデータに対して動作している可能性があることを理解されたい。
【０１０４】
エンティティノードを特徴ノードに接続する各エッジは、特徴再重み付けに関連して上で検討されたように、接続されたエンティティノードによって表されるエンティティに関連する特徴ノードによって表される特徴に関する特徴重みに対応するエッジ重みを有する可能性がある。一部の例においては、グラフ内で、エンティティノードが、その他のエンティティノードに接続されない可能性があり、特徴ノードが、その他の特徴ノードに接続されない可能性がある。エンティティに関する特徴が複数の特徴のカテゴリー内に現れる場合、ランク付けモジュール18は、それらの特徴を、エンティティを表すエンティティノードに接続される単一の特徴ノードによって表される単一の特徴にまとめる可能性がある。たとえば、ランク付けモジュール18は、特定のエンティティに関してクエリ特徴カテゴリーと題名特徴カテゴリーとの両方にカテゴリー分けされる特徴「movie」を単一の特徴ノードによって表される単一の特徴にまとめる可能性があり、2つの特徴の中の特徴の特徴重みを、エンティティノードを特徴ノードに接続するエッジに関する単一のエッジ重みへと合計する可能性があり、それによって、特徴の次元を減らし、特徴の希薄さの問題を軽減する。
【０１０５】
概念的に言って、ランク付けモジュール18は、ソースエンティティSとターゲットエンティティTとの間など、エンティティのペアの関わりを
【０１０６】
【数１２】
2019514149.tif 000014
【０１０７】
として決定する可能性があり、
【０１０８】
【数１３】
2019514149.tif 000015
【０１０９】
は、グラフ内のエンティティSおよびTに関連するエンティティノードの近傍であり、
【０１１０】
【数１４】
2019514149.tif 000016
【０１１１】
は、グラフ内で複数のホップによって接続される(たとえば、丁度すぐ近傍でない)関連エンティティのペアを発見するためにグラフの構造全体をモデル化する可能性がある。
【０１１２】
言い換えると、2つのエンティティノードは、それらのエンティティノードが両方とも同じ特徴ノードに接続するので、グラフ内で互いにすぐ近傍にある可能性がある。しかし、ランク付けモジュール18は、それにもかかわらず、ソースおよびターゲットエンティティを表すエンティティノードの近傍にあるエンティティノードによって表される別のエンティティの特徴と一緒にソースおよびターゲットエンティティの特徴の間の類似性に基づいて、たとえ2つのエンティティのそれぞれのエンティティノードが互いのすぐ近傍にないとしてもそれらのエンティティが関連すると判定し得る。したがって、ランク付けモジュール18は、特定のソースエンティティに関して、ソースエンティティおよびターゲットエンティティを表すエンティティノードがソースおよびターゲットエンティティを表すエンティティノードの近傍にあるエンティティノードによって表される別のエンティティに関連する限り、たとえソースエンティティおよびターゲットエンティティを表すエンティティノードが同じ特徴ノードに接続されないとしても、そのソースエンティティがターゲットエンティティに関連すると判定し得る。
【０１１３】
特徴-エンティティ2部グラフを生成すると、ランク付けモジュール18は、グラフ内の各ノードがラベルの分布に関連付けられ得るようにラベルの分布を複数のノードの各々に関連付けるために特徴-エンティティ2部グラフにわたってラベルを伝搬させるラベル伝搬を実行する可能性がある。したがって、グラフ内の各特徴ノードおよび各エンティティノードは、ラベル伝搬の結果としてラベルの分布に関連付けられる可能性がある。上で検討されたように、特徴-エンティティ2部グラフへのラベル伝搬を実行することは、ラベル伝搬を実行するために、特徴-エンティティ2部グラフを示すグラフデータストア52B内に記憶されたデータに対してランク付けモジュール18が動作することを含み得る。
【０１１４】
ランク付けモジュール18がグラフに伝搬させるラベルの各々は、グラフ内のノードに関連するラベルの分布が特定のノードによって表されるエンティティまたは特徴に関連する1つまたは複数のエンティティの分布である可能性があるように、グラフ内のノードとして表されるエンティティのうちの1つを示し得る。さらに、グラフ内のノードに関連するラベルの分布は、グラフ内のノードに関連するラベルの分布が特徴ノードの特定のエンティティノードによって表されるエンティティまたは特徴に関連する1つまたは複数のエンティティの関わりのランク付けの指示である可能性があるように、特定のノードによって表されるエンティティまたは特徴との1つまたは複数のエンティティの分布の中の1つまたは複数のエンティティの各々の関わりのレベルを示し得る。
【０１１５】
特徴-エンティティ2部グラフへのラベル伝搬を開始するために、ランク付けモジュール18は、複数のエンティティノードの各々に複数のラベルのうちの1つをシードとして付ける(seed)ことによってラベルを各エンティティノードに関連付ける可能性がある。エンティティノードに最初に関連付けられるそのようなラベルは、シードラベルとして知られる可能性がある。特定のエンティティノードに関連するラベルは、ランク付けモジュール18によってシードとして付けられたラベルのそれぞれ1つずつがエンティティノードの対応する1つを特定し得るように、エンティティノードによって表されるエンティティを特定する可能性がある。各ラベルは、エンティティがそれ自体の関連するラベルであり得るようなアイデンティティラベル(identity label)である可能性がある。したがって、エンティティAを表すエンティティノードは、関連するエンティティの題名である可能性があるラベル「entity A」に関連付けられ得る。
【０１１６】
ランク付けモジュール18は、各ノードがラベルのうちの1つまたは複数の分布に関連付けられ得るように、エンティティノードに関連するラベルをグラフに伝搬させるラベル伝搬を実行する可能性がある。ラベル伝搬を実行するために、ランク付けモジュール18は、グラフの各ノードに関連するラベルの分布を目的関数を最小化する最適解として決定し得る。
【０１１７】
特徴-エンティティ2部グラフが与えられると、目的関数は、グラフ内のすべてのノードに渡って以下、すなわち、真のラベルの分布と帰納されたラベルの分布(induced label distribution)との間の2乗損失(squared loss)、このエンティティノードと異なるラベルの分布を有する近接する特徴ノードにペナルティーを科す正則化項(regularization term)、および実際には通常一様な分布である前の分布に向かって帰納されたラベルの分布を平滑化する正則化項を同時に最小化し得る。
【０１１８】
より詳細には、エンティティノードの特徴近接ノード(feature neighbor)がエンティティノードにエッジによって直接接続される特徴ノードである可能性があるものとして、その特徴近接ノード
【０１１９】
【数１５】
2019514149.tif 000017
【０１２０】
を有する各エンティティノードiに関して、ランク付けモジュール18は、エンティティノードに関連するラベルの分布を、目的関数
【０１２１】
【数１６】
2019514149.tif 000018
【０１２２】
を最小化する最適解として決定する可能性があり、式中、
【０１２３】
【数１７】
2019514149.tif 000019
【０１２４】
は、エンティティノードiに関する学習されたラベルの分布であり、Yiは、真のラベルの分布であり、μnpは、発散するラベルの分布(divergent label distribution)を有する近接するノードに関する予め定義されたペナルティーであり、
【０１２５】
【数１８】
2019514149.tif 000020
【０１２６】
は、特徴近接ノードjに関する学習されたラベルの分布であり、Wijは、エンティティi内の特徴jの重みであり、μppは、前の一様な分布Uから逸脱するラベルの分布に関するペナルティーである。一部の例において、μnpは、0.5である可能性があり、μppは、0.001である可能性がある。
【０１２７】
したがって、この例において、
【０１２８】
【数１９】
2019514149.tif 000021
【０１２９】
は、エンティティノードに関連するラベルの真の分布とエンティティノードに関連するラベルの学習された分布との間の2乗損失である可能性があり、式中、Yiは、エンティティノードiに関連するラベルの真の分布であり、
【０１３０】
【数２０】
2019514149.tif 000022
【０１３１】
は、エンティティノードiに関するラベルの学習された分布である。エンティティノードiに関連するラベルの真の分布は、ランク付けモジュール18がエンティティノードiに関してシードとして付けるラベルである可能性があり、一方、ラベルの学習された分布は、ランク付けモジュール18がグラフにわたってラベル伝搬を実行した結果としてエンティティノードiに関連付けられるラベルの分布である可能性がある。
【０１３２】
さらに、μnpは、エンティティノードに関連するラベルの分布と異なるラベルの分布に関連付けられる近接する特徴ノードにペナルティーを科す第1の正則化項である可能性があり、
【０１３３】
【数２１】
2019514149.tif 000023
【０１３４】
は、エンティティノードiに関連するラベルの分布からの近接する特徴ノードに関連するラベルの分布の差を表し、
【０１３５】
【数２２】
2019514149.tif 000024
【０１３６】
は、ランク付けモジュール18がグラフにわたってラベル伝搬を実行した結果として、エッジ重みWijを有するエッジによってエンティティノードiに接続される特徴ノードjに関連付けられラベルの分布である可能性がある。加えて、μppは、μppを
【０１３７】
【数２３】
2019514149.tif 000025
【０１３８】
に掛けることによってラベルの前の分布に向かってエンティティノードに関連するラベルの学習された分布を平滑化する第2の正則化項である可能性がある。
【０１３９】
ランク付けモジュール18は、特徴ノードに関連するラベルの分布を、特徴ノードjにエッジによって直接接続されるそのエンティティ近接ノード(entity neighbor)
【０１４０】
【数２４】
2019514149.tif 000026
【０１４１】
を有する各特徴ノードjに関して目的関数
【０１４２】
【数２５】
2019514149.tif 000027
【０１４３】
を最小化する最適解として決定し得る。特徴ノードに関する目的関数は、ランク付けモジュール18が特徴ノードに関するシードラベルを提供しないので第1項がないことを除いてエンティティノードに関する目的関数と同様である。したがって、μnpは、特徴ノードに関連するラベルの分布と異なるラベルの分布に関連付けられる近接するエンティティノードにペナルティーを科す第1の正則化項である可能性があり、
【０１４４】
【数２６】
2019514149.tif 000028
【０１４５】
は、特徴ノードjに関連するラベルの分布からの近接するエンティティノードに関連するラベルの分布の差を表す可能性がある。さらに、μppは、μppを
【０１４６】
【数２７】
2019514149.tif 000029
【０１４７】
に掛けることによってラベルの前の分布に向かって特徴ノードに関連するラベルの学習された分布を平滑化する第2の正則化項である可能性がある。
【０１４８】
ランク付けモジュール18は、ラベル伝搬を実行することによって、グラフのエンティティノードおよび特徴ノードに関するラベルの分布を、グラフの全体で目的関数を最小化する最適解として決定し得る。したがって、ランク付けモジュール18は、それぞれの個々のエンティティノードまたは特徴ノードに関する目的関数を最小化しない可能性があるが、グラフを構成する特徴ノードおよびエンティティノードに関する全体的な目的関数を最小化し得る。
【０１４９】
ランク付けモジュール18は、本明細書において検討されるラベル伝搬を実行するために教師なし機械学習を実行し得る。特に、複数のエンティティノードが複数のラベルをシードとして付けられる、複数のエンティティノードが関連するエッジ重みを有するエッジによって複数の特徴ノードに接続される特徴-エンティティ2部グラフが与えられると、ランク付けモジュール18は、上述の目的関数を最小化するためにグラフの各ノードに関するラベルの分布を決定するために追加の入力なしにラベル伝搬を複数回(たとえば、5回反復して)実行する可能性がある。
【０１５０】
ラベル伝搬を実行することによって、ランク付けモジュール18は、ラベルの分布をグラフ内の各ノードに関連付け得る。ノードに関連するラベルの分布の各々は、関連するエンティティノードまたは特徴ノードによって表されるエンティティまたは特徴に関連する1つまたは複数のエンティティのランク付けの指示を含み得る。グラフ内の各ラベルはエンティティノードによって表される特定のエンティティを特定する可能性があるので、ノードに関連するラベルの分布は、ノードによって表される特定の特徴またはエンティティに関連する1つまたは複数のエンティティのエンティティ名を示す可能性がある。さらに、ノードに関連するラベルの分布は、ノードによって表される特定の特徴またはエンティティとのエンティティの関わりのレベルを示す可能性もある。このようにして、ラベルの分布は、関連するエンティティノードまたは特徴ノードによって表されるエンティティまたは特徴に関連する1つまたは複数のエンティティのランク付けを示す可能性がある。ランク付けモジュール18は、エンティティまたは特徴に関連する1つまたは複数のエンティティの(関わりのレベルによる)ランク付けの指示を含む、グラフに表される各エンティティおよび各特徴の指示をランク付けデータストア52Cに記憶し得る。
【０１５１】
したがって、ISS 14は、ネットワーク12またはインターネット20を介して、たとえば、コンピューティングデバイス2からエンティティを示す着信データまたは特徴の指示を受信し、ランク付けデータストア52Cに記憶されたデータから、エンティティまたは特徴に関連する1つまたは複数のエンティティのランク付けの指示を決定し、特定のエンティティまたは特徴に関連する1つまたは複数のエンティティのランク付けの指示を含む発信データをコンピューティングデバイス2に送信し得る。一例において、ISS 14がコンピューティングデバイス2から受信するエンティティの指示は、「Miles Davis」または「Beethoven's 5th Symphony」などのエンティティに関連する名前を示す可能性がある。ランク付けモジュール18は、その名前に関連するエンティティを見つけるためにランク付けデータストア52Cにインデックスを付けるためにエンティティに関連する名前を利用する可能性があり、特定のエンティティに関連する1つまたは複数のエンティティのランク付けの指示が記憶されるランク付けデータストア52C内の場所を決定する可能性がある。ランク付けモジュール18は、特定のエンティティに関連する1つまたは複数のエンティティのランク付けの指示を取り出し得る。ISS 14は、特定のエンティティに関連する1つまたは複数のエンティティのランク付けの取り出された指示を、JSONまたはXMLなどの1つまたは複数のエンティティのランク付けの指示を送信するための任意の好適な構造化されたデータフォーマットへとフォーマットする可能性があり、ネットワーク12またはインターネット20などを介して1つまたは複数のエンティティの指示をコンピューティングデバイス2に出力する可能性がある。
【０１５２】
別の例において、ISS 14は、たとえば、コンピューティングデバイス2からクエリを示す着信データを受信する可能性がある。クエリは、コンピューティングデバイス2が入力として受け取り得る単語、語句などのテキストデータである可能性がある。たとえば、クエリは、クエリに関連する1つまたは複数のエンティティに関する検索語句である可能性がある。クエリの指示を受信することに応じて、コンピューティングデバイス2は、クエリに関連する1つまたは複数のエンティティのランク付けをランク付けモジュール18によって決定する可能性があり、クエリに関連する1つまたは複数のエンティティのランク付けの指示をコンピューティングデバイス2に出力する可能性がある。
【０１５３】
「marathon」などのクエリの指示が与えられると、ランク付けモジュール18は、クエリに対する1つまたは複数の関連エンティティのランク付けを決定し得る。ランク付けモジュール18は、クエリのテキストを特徴のテキストにマッピングすることなどによってクエリを特徴として扱って、それによって
【０１５４】
【数２８】
2019514149.tif 000030
【０１５５】
を決定する可能性があり、式中、FQは、クエリQにマッピングされる特徴のすべての組である可能性がある。特に、各特徴が特徴に関連する1つまたは複数のエンティティのランク付けを示すラベルの分布に関連付けられるので、ランク付けモジュール18は、クエリがマッピングされる特定の特徴を決定し、特定の特徴を見つけるためにランク付けデータストア52Cにインデックスを付ける可能性があり、特定の特徴に関連する1つまたは複数のエンティティのランク付けの指示が記憶されるランク付けデータストア52C内の場所を決定する可能性がある。ランク付けモジュール18は、特定の特徴に関連する1つまたは複数のエンティティのランク付けの指示を取り出し得る。ISS 14は、特定の特徴に関連する1つまたは複数のエンティティのランク付けの取り出された指示を、JSONまたはXMLなどの1つまたは複数のエンティティのランク付けの指示を送信するための任意の好適な構造化されたデータフォーマットへとフォーマットする可能性があり、ネットワーク12またはインターネット20などを介して1つまたは複数のエンティティの指示をコンピューティングデバイス2に出力する可能性がある。
【０１５６】
図3A〜図3Cは、本開示の態様によるエキスパンダ技術を実行するためにランク付けモジュール18が構築し得る例示的な特徴-エンティティ2部グラフをそれぞれ示すブロック図である。図3Aに示されるように、ランク付けモジュール18は、エッジ86A〜86Fによって接続された特徴ノード84D〜84Fに接続されたエンティティノード84Aおよび84Bを含む特徴-エンティティ2部グラフ80を生成し得る。ランク付けモジュール18は、エンティティノード84Aおよび84Bにラベル88Aおよび88Bをそれぞれシードとして付ける可能性がある。エッジ86A〜86Fの各々は、関連するエッジ重み(図示せず)を有する可能性がある。
【０１５７】
ランク付けモジュール18は、それぞれのラベル付けされたシードノードに関連する情報を使用して、原理に基づいた反復的な方法でグラフにこれらのラベルを伝搬させるグラフに基づく学習技術であるラベル伝搬の考え方を利用することによってグラフ90上で機械学習を実行し得る。ラベル伝搬は、2つの入力ソース、すなわち、グラフ80ならびにシードラベル88Aおよび88Bを利用し得る。ランク付けモジュール18は、グラフ80に与えられたグラフ構造に基づいてシードラベル88Aおよび88Bを伝搬させて、グラフ80内のノード84A〜84Fの各々に関するシードラベルの分布を目的関数を最小化する最適解として関連付け得る。
【０１５８】
ランク付けモジュール18は、ラベル伝搬を複数回反復して実行して、グラフ80内のノード84A〜84Fの各々に関するシードラベルの分布を目的関数を最小化する最適解として関連付け得る。図3Bは、グラフ80へのラベル伝搬の第1の反復を示す。図3Bに示されるように、ラベル伝搬の第1の反復の後、ランク付けモジュール18は、ラベル82A〜82Fの分布をノード84A〜84Fにそれぞれ関連付け得る。ランク付けモジュール18は、ラベル82A〜82Fの分布が1つまたは両方のラベル88Aおよび88Bの指示を含み得るようにラベル88Aおよび88Bをグラフ80に分配する可能性もある。ラベルの各分布は、1つまたは複数の関連エンティティの指示、およびノードによって表されるエンティティまたは特徴と1つまたは複数の関連エンティティの各々との間の関わりのレベルの指示を含み得る。たとえば、特徴ノード84Dに関連するラベル82Dの分布は、エンティティScience Fiction MoviesおよびScience Fiction Filmsの指示を含み、それらのエンティティと特徴ノード84Dに関連する特徴との間の関わりの指示を0から1.0までのスケールで含み、より大きいスコアほど、類似性のより高いレベルを示す。
【０１５９】
ランク付けモジュール18は、グラフ80へのラベル伝搬の実行をさらに反復する可能性がある。図3Cは、グラフ80へのラベル伝搬のさらなる反復を示す。図3Cに示されるように、フィールド伝搬(field propagation)のさらなる反復の後、グラフ80上で目的関数を最小化するより最適化された解を決定するためにノード84A〜84Fのうちの1つまたは複数に関連するラベルの分布をさらに修正し得る。たとえば、ノード82Cの分布は、今、エンティティScience Fiction MoviesおよびScience Fiction Filmsの指示を含み、それらのエンティティと特徴ノード84Dに関連する特徴との間の関わりの指示を0から1.0までのスケールで含み、より大きいスコアほど、類似性のより高いレベルを示す。
【０１６０】
図4は、本開示の1つまたは複数の態様による、関連エンティティを決定するための例示的なプロセスを示す流れ図である。一部の例において、プロセスは、図1および図2に示されたISS 14、エンティティモジュール16、およびランク付けモジュール18のうちの1つまたは複数によって実行され得る。一部の例において、プロセスは、図1〜図2に示された追加的なモジュールまたは構成要素によって実行され得る。例示のみを目的として、一例において、プロセスは、図2に示されたISS 14によって実行される。図4に示されるように、プロセスは、複数のノードを含むグラフ80などのグラフをランク付けモジュール18によって生成することであって、複数のノードが、複数のエンティティを表す複数のエンティティノードと、複数の特徴を表す複数の特徴ノードとを含み、複数のエンティティノードの各々が、グラフ内で複数の特徴ノードのうちの1つまたは複数に接続される、生成することを含む可能性がある(102)。プロセスは、複数のノードの各々にラベルの分布を関連付けるためにグラフにわたって複数のラベルを伝搬させるラベル伝搬をランク付けモジュール18によって実行することをさらに含む可能性がある(104)。一部の例において、ISS 14は、関心のある特徴または関心のあるエンティティのうちの少なくとも一方の指示を受信するように構成される可能性がある。一部の例において、ISS 14は、関心のある特徴または関心のあるエンティティに関連する1つまたは複数の関連エンティティの指示を出力するように構成される可能性がある。
【０１６１】
一部の例において、プロセスは、ランク付けモジュール18によって複数のエンティティノードの各々に複数のラベルのうちのそれぞれ1つをシードとして付けることであって、ラベルのそれぞれ1つが、複数のエンティティノードのうちの対応する1つを特定する、シードとして付けることをさらに含む可能性がある。一部の例において、ラベル伝搬を実行することは、複数のノードの各々に関連するラベルの分布を目的関数を最小化する最適解として決定するためにラベル伝搬をランク付けモジュール18によって実行することをさらに含む可能性がある。
【０１６２】
一部の例において、目的関数は、複数の特徴ノードのエンティティノードに関して最小化され、目的関数は、エンティティノードに関連するラベルの真の分布とエンティティノードに関連するラベルの学習された分布との間の2乗損失、エンティティノードに関連するラベルの分布と異なるラベルの分布に関連付けられる近接する特徴ノードにペナルティーを科す第1の正則化項、およびラベルの前の分布に向かってエンティティノードに関連するラベルの学習された分布を平滑化する第2の正則化項を含む。
【０１６３】
一部の例において、目的関数は、複数の特徴ノードの特徴ノードに関して最小化され、目的関数は、特徴ノードに関連するラベルの分布と異なるラベルの分布に関連付けられる近接するエンティティノードにペナルティーを科す第1の正則化項、およびラベルの前の分布に向かって特徴ノードに関連するラベルの学習された分布を平滑化する第2の正則化項を含む。
【０１６４】
一部の例において、ラベルの分布の各々は、関連するエンティティノードまたは特徴ノードによって表されるエンティティまたは特徴に関連する1つまたは複数のエンティティのランク付けの指示を含む。一部の例において、関連するノードによって表されるエンティティまたは特徴に関連する1つまたは複数のエンティティのランク付けの指示は、関連するエンティティノードまたは特徴ノードによって表されるエンティティまたは特徴との1つまたは複数のエンティティの各々の関わりのレベルの指示を含む。
【０１６５】
一部の例において、プロセスは、ランク付けモジュール18によって、対応するエンティティを表すグラフ内の複数のエンティティノードの各々を、対応するエンティティに関連する1つまたは複数の特徴を表すグラフ内の複数の特徴ノードのうちの1つまたは複数に、グラフの1つまたは複数のエッジによって接続することをさらに含む。一部の例において、プロセスは、ランク付けモジュール18によって1つまたは複数のエッジに1つまたは複数の重みを関連付けることをさらに含む可能性がある。
【０１６６】
一部の例において、プロセスは、エンティティモジュール16によって、複数のエンティティに関連する複数のインターネットリソースから、複数のエンティティに関連する複数の特徴を抽出することをさらに含む可能性がある。一部の例において、複数のエンティティは、同じ地理的エリアに関連付けられる。
【０１６７】
図5は、本開示の1つまたは複数の態様による、関連エンティティを決定するための例示的なプロセスを示す流れ図である。一部の例において、プロセスは、図1および図2に示されたISS 14、エンティティモジュール16、およびランク付けモジュール18のうちの1つまたは複数によって実行され得る。一部の例において、プロセスは、図1〜図2に示された追加的なモジュールまたは構成要素によって実行され得る。例示のみを目的として、一例において、プロセスは、図2に示されたISS 14によって実行される。図5に示されるように、プロセスは、関心のある特徴または関心のあるエンティティのうちの少なくとも一方の指示をISS 14の通信ユニット46によって受信することを含む可能性がある(202)。プロセスは、ISS 14の1つまたは複数のプロセッサ44によって、関心のある特徴を表すグラフ内の複数の特徴ノードのうちの1つまたは関心のあるエンティティを表すグラフ内の複数のエンティティノードのうちの1つに関連するラベルのそれぞれの分布に少なくとも部分的に基づいて関心のある特徴または関心のあるエンティティに関連する1つまたは複数の関連エンティティを決定することであって、グラフが、複数のノードを含み、複数のノードが、複数のエンティティを表す複数のエンティティノード、および複数の特徴を表す複数の特徴ノードを含み、複数のエンティティノードの各々が、グラフ内で複数の特徴ノードのうちの1つまたは複数に接続され、複数のラベルが、複数のノードの各々にラベルの分布を関連付けるためにグラフにわたってラベル伝搬によって伝搬させられる、決定することをさらに含む可能性がある(204)。プロセスは、ISS 14の通信ユニット46によって、関心のある特徴または関心のあるエンティティのうちの少なくとも一方に関して、関心のある特徴または関心のあるエンティティに関連する1つまたは複数の関連エンティティの指示を出力することをさらに含む可能性があり、1つまたは複数の関連エンティティの指示を出力することは、関心のある特徴を表す複数の特徴ノードのうちの1つ、または関心のあるエンティティを表す複数のエンティティノードのうちの1つに関連するラベルのそれぞれの分布に少なくとも部分的に基づく(206)。
【０１６８】
一部の例において、関心のある特徴または関心のあるエンティティのうちの少なくとも一方の指示を受信することは、関心のある特徴または関心のあるエンティティのうちの少なくとも一方を示す着信データをリモートコンピューティングデバイス2からネットワーク12を介してISS 14によって受信することをさらに含み、ISS 14によって、関心のある特徴または関心のあるエンティティのうちの少なくとも一方に関して、関心のある特徴または関心のあるエンティティに関連する1つまたは複数の関連エンティティの指示を出力することは、関心のある特徴または関心のあるエンティティに関連する1つまたは複数の関連エンティティの指示を含む発信データをリモートコンピューティングデバイス2にネットワーク12を介してISS 14によって送信することをさらに含む。
【０１６９】
例1:  複数のノードを含むグラフをコンピューティングデバイスによって生成するステップであって、複数のノードが、複数のエンティティを表す複数のエンティティノード、および複数の特徴を表す複数の特徴ノードを含み、複数のエンティティノードの各々が、グラフ内で複数の特徴ノードのうちの1つまたは複数に接続される、ステップ、複数のノードの各々にラベルの分布を関連付けるためにグラフにわたって複数のラベルを伝搬させるラベル伝搬をコンピューティングデバイスによって実行するステップを含み、コンピューティングデバイスが、関心のある特徴または関心のあるエンティティのうちの少なくとも一方の指示を受信し、関心のある特徴または関心のあるエンティティのうちの少なくとも一方に関して、関心のある特徴または関心のあるエンティティに関連する1つまたは複数の関連エンティティの指示を出力するように構成され、1つまたは複数の関連エンティティの指示を出力することが、関心のある特徴を表す複数の特徴ノードのうちの1つ、または関心のあるエンティティを表す複数のエンティティノードのうちの1つに関連するラベルのそれぞれの分布に少なくとも部分的に基づく、方法。
【０１７０】
例2:  ラベル伝搬をコンピューティングデバイスによって実行するステップが、コンピューティングデバイスによって複数のエンティティノードの各々に複数のラベルのうちのそれぞれ1つをシードとして付けることであって、ラベルのそれぞれ1つが、複数のエンティティノードのうちの対応する1つを特定する、シードとして付けることをさらに含む例1の方法。
【０１７１】
例3:  ラベル伝搬をコンピューティングデバイスによって実行するステップが、複数のノードの各々に関連するラベルの分布を目的関数を最小化する最適解として決定するためにラベル伝搬をコンピューティングデバイスによって実行することをさらに含む例1〜2のいずれかの方法。
【０１７２】
例4:  目的関数が、複数の特徴ノードのエンティティノードに関して最小化され、目的関数が、エンティティノードに関連するラベルの真の分布とエンティティノードに関連するラベルの学習された分布との間の2乗損失、エンティティノードに関連するラベルの分布と異なるラベルの分布に関連付けられる近接する特徴ノードにペナルティーを科す第1の正則化項、およびラベルの前の分布に向かってエンティティノードに関連するラベルの学習された分布を平滑化する第2の正則化項を含む例3の方法。
【０１７３】
例5:  目的関数が、複数の特徴ノードの特徴ノードに関して最小化され、目的関数が、特徴ノードに関連するラベルの分布と異なるラベルの分布に関連付けられる近接するエンティティノードにペナルティーを科す第1の正則化項、およびラベルの前の分布に向かって特徴ノードに関連するラベルの学習された分布を平滑化する第2の正則化項を含む例3および4のいずれかの方法。
【０１７４】
例6:  ラベルの分布の各々が、関連するエンティティノードまたは特徴ノードによって表されるエンティティまたは特徴に関連する1つまたは複数のエンティティのランク付けの指示を含む例1〜5のいずれかの方法。
【０１７５】
例7:  関連するノードによって表されるエンティティまたは特徴に関連する1つまたは複数のエンティティのランク付けの指示が、関連するエンティティノードまたは特徴ノードによって表されるエンティティまたは特徴との1つまたは複数のエンティティの各々の関わりのレベルの指示を含む例6の方法。
【０１７６】
例8:  コンピューティングデバイスによって、対応するエンティティを表すグラフ内の複数のエンティティノードの各々を、対応するエンティティに関連する1つまたは複数の特徴を表すグラフ内の複数の特徴ノードのうちの1つまたは複数に、グラフの1つまたは複数のエッジによって接続するステップをさらに含む例1〜7のいずれかの方法。
【０１７７】
例9:  コンピューティングデバイスによって1つまたは複数のエッジに1つまたは複数の重みを関連付けるステップをさらに含む例8の方法。
【０１７８】
例10:  メモリと、メモリに通信可能なように結合された少なくとも1つのプロセッサであって、複数のノードを含む、メモリに記憶されるグラフを生成することであって、複数のノードが、複数のエンティティを表す複数のエンティティノード、および複数の特徴を表す複数の特徴ノードを含み、複数のエンティティノードの各々が、グラフ内で複数の特徴ノードのうちの1つまたは複数に接続される、生成すること、ならびに複数のノードの各々にラベルの分布を関連付けるためにグラフに複数のラベルを伝搬させるラベル伝搬を実行することを行うように構成される、少なくとも1つのプロセッサとを含むコンピューティングシステム。
【０１７９】
例11:  メモリと、メモリに通信可能なように結合された少なくとも1つのプロセッサであって、例1〜9の任意の組合せの方法を実行するためのコンピュータ可読命令の制御の下で動作するように構成される、少なくとも1つのプロセッサとを含むコンピューティングシステム。
【０１８０】
例12:  関心のある特徴または関心のあるエンティティのうちの少なくとも一方の指示をコンピューティングデバイスによって受信するステップであって、関心のある特徴を表すグラフ内の複数の特徴ノードのうちの1つまたは関心のあるエンティティを表すグラフ内の複数のエンティティノードのうちの1つに関連するラベルのそれぞれの分布に少なくとも部分的に基づいて関心のある特徴または関心のあるエンティティに関連する1つまたは複数の関連エンティティをコンピューティングデバイスによって決定するステップであって、グラフが、複数のノードを含み、複数のノードが、複数のエンティティを表す複数のエンティティノード、および複数の特徴を表す複数の特徴ノードを含み、複数のエンティティノードの各々が、グラフ内で複数の特徴ノードのうちの1つまたは複数に接続され、複数のラベルが、複数のノードの各々にラベルの分布を関連付けるためにグラフにわたってラベル伝搬によって伝搬させられる、ステップと、関心のある特徴または関心のあるエンティティのうちの少なくとも一方に関して、関心のある特徴または関心のあるエンティティに関連する1つまたは複数の関連エンティティの指示をコンピューティングデバイスによって出力するステップとを含み、1つまたは複数の関連エンティティの指示を出力するステップが、関心のある特徴を表す複数の特徴ノードのうちの1つ、または関心のあるエンティティを表す複数のエンティティノードのうちの1つに関連するラベルのそれぞれの分布に少なくとも部分的に基づく、方法。
【０１８１】
例13:  関心のある特徴または関心のあるエンティティのうちの少なくとも一方の指示を受信するステップが、関心のある特徴または関心のあるエンティティのうちの少なくとも一方を示す着信データをリモートコンピューティングデバイスからネットワークを介してコンピューティングデバイスによって受信することをさらに含み、コンピューティングデバイスによって、関心のある特徴または関心のあるエンティティのうちの少なくとも一方に関して、関心のある特徴または関心のあるエンティティに関連する1つまたは複数の関連エンティティの指示を出力するステップが、関心のある特徴または関心のあるエンティティに関連する1つまたは複数の関連エンティティの指示を含む発信データをリモートコンピューティングデバイスにネットワークを介してコンピューティングデバイスによって送信することをさらに含む例12の方法。
【０１８２】
例14:  メモリと、メモリに通信可能なように結合された少なくとも1つのプロセッサであって、関心のある特徴または関心のあるエンティティのうちの少なくとも一方の指示を受信すること、関心のある特徴を表すグラフ内の複数の特徴ノードのうちの1つまたは関心のあるエンティティを表すグラフ内の複数のエンティティノードのうちの1つに関連するラベルのそれぞれの分布に少なくとも部分的に基づいて関心のある特徴または関心のあるエンティティに関連する1つまたは複数の関連エンティティを決定することであって、グラフが、複数のノードを含み、複数のノードが、複数のエンティティを表す複数のエンティティノード、および複数の特徴を表す複数の特徴ノードを含み、複数のエンティティノードの各々が、グラフ内で複数の特徴ノードのうちの1つまたは複数に接続され、複数のラベルが、複数のノードの各々にラベルの分布を関連付けるためにグラフにわたるラベル伝搬によって伝搬させられる、決定すること、ならびに関心のある特徴または関心のあるエンティティのうちの少なくとも一方に関して、関心のある特徴または関心のあるエンティティに関連する1つまたは複数の関連エンティティの指示を出力することを行うように構成される、少なくとも1つのプロセッサとを含み、1つまたは複数の関連エンティティの指示を出力することが、関心のある特徴を表す複数の特徴ノードのうちの1つ、または関心のあるエンティティを表す複数のエンティティノードのうちの1つに関連するラベルのそれぞれの分布に少なくとも部分的に基づくコンピューティングシステム。
【０１８３】
例15:  少なくとも1つのプロセッサが、関心のある特徴または関心のあるエンティティのうちの少なくとも一方を示す着信データをリモートコンピューティングデバイスからネットワークを介して受信し、関心のある特徴または関心のあるエンティティに関連する1つまたは複数の関連エンティティの指示を含む発信データをリモートコンピューティングデバイスにネットワークを介して送信するようにさらに構成される例14のコンピューティングシステム。
【０１８４】
1つまたは複数の例において、説明された機能は、ハードウェア、ソフトウェア、ファームウェア、またはこれらの任意の組合せで実装され得る。ソフトウェアに実装される場合、機能は、1つまたは複数の命令またはコードとしてコンピュータ可読媒体上に記憶されるかまたはコンピュータ可読媒体上で送信され、ハードウェアに基づく処理ユニットによって実行され得る。コンピュータ可読媒体は、データストレージ媒体などの有形の媒体に対応するコンピュータ可読ストレージ媒体、またはたとえば通信プロトコルによるある場所から別の場所へのコンピュータプログラムの転送を容易にする任意の媒体を含む通信媒体を含む可能性がある。このようにして、概して、コンピュータ可読媒体は、(1)非一時的である有形のコンピュータ可読ストレージ媒体または(2)信号もしくは搬送波などの通信媒体に対応する可能性がある。データストレージ媒体は、本開示において説明された技術の実装のための命令、コード、および/またはデータ構造を取り出すために1つもしくは複数のコンピュータまたは1つもしくは複数のプロセッサによってアクセスされ得る任意の利用可能な媒体である可能性がある。コンピュータプログラム製品は、コンピュータ可読媒体を含む可能性がある。
【０１８５】
限定ではなく例として、そのようなコンピュータ可読ストレージ媒体は、RAM、ROM、EEPROM、CD-ROMもしくはその他の光ディスクストレージ、磁気ディスクストレージもしくはその他の磁気ストレージデバイス、フラッシュメモリ、または命令もしくはデータ構造の形態で所望のプログラムコードを記憶するために使用可能であり、コンピュータによってアクセス可能である任意のその他のストレージ媒体を含み得る。また、当然、任意の接続がコンピュータ可読媒体と呼ばれる。たとえば、命令が、同軸ケーブル、光ファイバケーブル、ツイストペアケーブル、デジタル加入者線(DSL)、または赤外線、ラジオ波、およびマイクロ波などのワイヤレステクノロジーを用いてウェブサイト、サーバ、またはその他のリモートソースから送信される場合、同軸ケーブル、光ファイバケーブル、ツイストペアケーブル、DSL、または赤外線、ラジオ波、およびマイクロ波などのワイヤレステクノロジーは、媒体の定義に含まれる。しかし、コンピュータ可読ストレージ媒体およびデータストレージ媒体は、接続、搬送波、信号、またはその他の一時的媒体を含まず、その代わりに、非一時的な有形のストレージ媒体を対象とすることを理解されたい。本明細書において使用されるとき、ディスク(disk)およびディスク(disc)は、コンパクトディスク(CD: compact disc)、レーザディスク(laser disc)、光ディスク(optical disc)、デジタルバーサタイルディスク(DVD: digital versatile disc)、フロッピー(登録商標)ディスク(floppy disk)、およびブルーレイディスク(Blu-ray(登録商標) disc)を含み、ディスク(disk)が、通常、磁気的にデータを再生する一方、ディスク(disc)は、レーザを用いて光学的にデータを再生する。上記のものの組合せも、コンピュータ可読媒体の範囲内に含まれるべきである。
【０１８６】
指示は、1つまたは複数のデジタル信号プロセッサ(DSP)、汎用マイクロプロセッサ、特定用途向け集積回路(ASIC)、フィールドプログラマブルロジックアレイ(FPGA)、またはその他の等価な集積もしくはディスクリート論理回路などの1つまたは複数のプロセッサによって実行され得る。したがって、用語「プロセッサ」は、本明細書において使用されるとき、上述の構造または本明細書において説明された技術の実装に好適な任意のその他の構造のいずれかを指す可能性がある。加えて、一部の態様において、本明細書において説明された機能は、専用のハードウェアおよび/またはソフトウェアモジュール内に設けられる。また、技術は、1つまたは複数の回路または論理要素にすべて実装される可能性がある。
【０１８７】
本開示の技術は、ワイヤレスハンドセット、集積回路(IC)、または1組のIC(たとえば、チップセット)を含む多種多様なデバイスまたは装置に実装される可能性がある。様々な構成要素、モジュール、またはユニットが、開示された技術を実行するように構成されたデバイスの機能の態様を強調するために本開示において説明されているが、異なるハードウェアユニットによる実現を必ずしも必要としない。むしろ、上述のように、様々なユニットが、ハードウェアユニットにおいて組み合わされるか、または好適なソフトウェアおよび/もしくはファームウェアと連携した、上述の1つもしくは複数のプロセッサを含む相互運用性のあるハードウェアユニットの集合によって提供される可能性がある。
【０１８８】
様々な実施形態が、説明された。これらのおよびその他の実施形態は、添付の請求項の範囲内にある。
【符号の説明】
【０１８９】
2  コンピューティングデバイス
4  ユーザインターフェースデバイス
6  ユーザインターフェースモジュール
8  ユーザインターフェース
10  システム
12  ネットワーク
14  情報サーバシステム
16  エンティティモジュール
18  ランク付けモジュール
20  インターネット
22  インターネットサーバ
44  プロセッサ
46  通信ユニット
48  ストレージデバイス
50  通信チャネル
52A  特徴-エンティティデータストア
52B  グラフデータストア
52C  ランク付けデータストア
52D  インターネットリソースデータストア
80  特徴-エンティティ2部グラフ
84A  エンティティノード
84B  エンティティノード
82A〜82F  ラベル
84A〜84F  ノード
86A〜86F  エッジ
88A  ラベル
88B  ラベル
90  グラフ
【図１】
2019514149.tif 000031
【図２】
2019514149.tif 000032
【図３Ａ】
2019514149.tif 000033
【図３Ｂ】
2019514149.tif 000034
【図３Ｃ】
2019514149.tif 000035
【図４】
2019514149.tif 000036
【図５】
2019514149.tif 000037
【国際調査報告】
2019514149.tif 000038
2019514149.tif 000039
2019514149.tif 000040