(57)【要約】      （修正有）【課題】所定の概念体系によってエンティティの概念が形式化されたデータベース上において、クラスが決定されていないエンティティのクラスを自動的に決定する情報処理装置、情報処理方法及びプログラムを提供する。【解決手段】情報処理装置１００は、制御部１１０において、クラスが決定済みの第１エンティティに関連したコンテンツの検索ログと、クラスが未決定の第２エンティティに関連したコンテンツの検索ログとのそれぞれから、一つ以上のコンテキストタームを抽出する抽出部１１２と、抽出部１１２によって抽出された一つ以上のコンテキストタームと、第１エンティティのクラスとに基づいて、第２エンティティのクラスを決定するクラス決定部１１６と、を備える。【選択図】図３
2020154583.tif 000002
【特許請求の範囲】
【請求項１】
クラスが決定済みの第１エンティティに関連したコンテンツの検索ログと、前記クラスが未決定の第２エンティティに関連したコンテンツの検索ログとのそれぞれから、一つ以上のコンテキストタームを抽出する抽出部と、
前記抽出部によって抽出された前記一つ以上のコンテキストタームと、前記第１エンティティのクラスとに基づいて、前記第２エンティティのクラスを決定する決定部と、
を備える情報処理装置。
【請求項２】
前記決定部は、ラベルスプレッディング法を利用して、前記一つ以上のコンテキストタームと、前記第１エンティティのクラスとから、前記第２エンティティのクラスを決定する、
請求項１に記載の情報処理装置。
【請求項３】
前記第１エンティティおよび前記第２エンティティが互いに独立したノードとして含まれる第１の部分集合と、前記一つ以上のコンテキストタームが互いに独立したノードとして含まれる第２の部分集合とに基づいて、二部グラフを生成する生成部を更に備え、
前記決定部は、前記生成部によって生成された前記二部グラフに基づいて、前記第２エンティティのクラスを決定する、
請求項２に記載の情報処理装置。
【請求項４】
前記決定部は、前記第１の部分集合および前記第２の部分集合に含まれる複数のノードのそれぞれの前記クラスを示す値を要素とした第１行列と、前記第１の部分集合に含まれるノードと前記第２の部分集合に含まれるノードとを接続するエッジの重み係数を要素とした第２行列との積で前記第１行列を更新することで、前記第２エンティティのクラスを決定する、
請求項３に記載の情報処理装置。
【請求項５】
前記決定部は、
前記第１行列が収束するまで、前記第１行列と前記第２行列との積で前記第１行列を更新することを繰り返し、
前記第１行列を更新することを繰り返す過程で、前記第１エンティティのクラスを再決定する、
請求項４に記載の情報処理装置。
【請求項６】
前記重み係数は、前記コンテンツの検索結果から得られる統計的指標値に基づいて決定される、
請求項４または５に記載の情報処理装置。
【請求項７】
前記決定部は、ラベルプロパゲーティング法を利用して、前記一つ以上のコンテキストタームと、前記第１エンティティのクラスとから、前記第２エンティティのクラスを決定する、
請求項１に記載の情報処理装置。
【請求項８】
コンピュータが、
クラスが決定済みの第１エンティティに関連したコンテンツの検索ログと、前記クラスが未決定の第２エンティティに関連したコンテンツの検索ログとのそれぞれから、一つ以上のコンテキストタームを抽出し、
前記抽出した前記一つ以上のコンテキストタームと、前記第１エンティティのクラスとに基づいて、前記第２エンティティのクラスを決定する、
情報処理方法。
【請求項９】
コンピュータに、
クラスが決定済みの第１エンティティに関連したコンテンツの検索ログと、前記クラスが未決定の第２エンティティに関連したコンテンツの検索ログとのそれぞれから、一つ以上のコンテキストタームを抽出する処理と、
前記抽出した前記一つ以上のコンテキストタームと、前記第１エンティティのクラスとに基づいて、前記第２エンティティのクラスを決定する処理と、
を実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報処理装置、情報処理方法、およびプログラムに関する。
【背景技術】
【０００２】
エンティティ間の関係性を適切に示すデータベースを構築する技術が知られている（例えば、特許文献１参照）。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開２０１７−２０８０１５号公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
例えば、インターネット上で新しいディジタルコンテンツが公開された場合、そのコンテンツに関する新規のエンティティを既存のデータベースに登録することが望まれている。しかしながら、従来の技術では、データベースに新規に登録されたエンティティには、専らクラスと呼ばれる情報を付与できておらず、データベースを十分に有効活用することができていない場合があった。
【０００５】
本発明は、上記の課題に鑑みてなされたものであり、データベースをより有効活用することができる情報処理装置、情報処理方法、およびプログラムを提供することを目的としている。
【課題を解決するための手段】
【０００６】
本発明の一態様は、クラスが決定済みの第１エンティティに関連したコンテンツの検索ログと、前記クラスが未決定の第２エンティティに関連したコンテンツの検索ログとのそれぞれから、一つ以上のコンテキストタームを抽出する抽出部と、前記抽出部によって抽出された前記一つ以上のコンテキストタームと、前記第１エンティティのクラスとに基づいて、前記第２エンティティのクラスを決定する決定部と、を備える情報処理装置である。
【発明の効果】
【０００７】
本発明の一態様によれば、データベースをより有効活用することができる情報処理装置、情報処理方法、およびプログラムを提供することができる。
【図面の簡単な説明】
【０００８】
【図１】第１実施形態における情報処理装置１００を含む情報処理システム１の一例を示す図である。
【図２】エンティティパネルの一例を示す図である。
【図３】第１実施形態における情報処理装置１００の構成の一例を示す図である。
【図４】ナレッジベース１３２の一例を示す図である。
【図５】検索ログ１３４の一例を示す図である。
【図６】第１実施形態における制御部１１０による一連の処理の流れを示すフローチャートである。
【図７】コンテキストタームの抽出方法を説明するための図である。
【図８】二部グラフの一例を示す図である。
【図９】ラベルスプレッディング法の一連の処理の流れを示すフローチャートである。
【図１０】二部グラフの初期化の様子を模式的に示す図である。
【図１１】クラス行列Ｆが収束したときの二部グラフを模式的に示す図である。
【図１２】二部グラフの初期化の様子を模式的に示す図である。
【図１３】実施形態の情報処理装置１００のハードウェア構成の一例を示す図である。
【発明を実施するための形態】
【０００９】
以下、本発明を適用した情報処理装置、情報処理方法、およびプログラムを、図面を参照して説明する。
【００１０】
［概要］
情報処理装置は、一以上のプロセッサによって実現される。情報処理装置は、オントロジーと呼ばれる所定の概念体系（または語彙体系）によってエンティティの概念が形式化されたデータベース上において、未だクラスが決定されていないエンティティのクラスを自動的に決定する。
【００１１】
データベースは、エンティティに関する情報と、エンティティ同士の意味的関係に関する情報とがグラフとして記述されたナレッジ型のデータベース（以下、ナレッジベースと称する）として表現される。ナレッジベースにおけるエンティティは、例えば、あるエンティティの実体（実世界で存在している物体）や、あるエンティティの概念（実世界または仮想世界の中で定義された概念）を表した情報である。より具体的には、エンティティは、例えば、「人間」、「機械」、「建物」、「組織」、「美」、「学問」、「旅行」といった抽象的な概念を表すエンティティあってもよいし、「○○タワー」のように「建物」という概念の実体や、「検索太郎（人名）」のように「人間」という概念の実体を表すエンティティであってもよい。
【００１２】
このようなナレッジベースは、プロセッサ（コンピュータ）による処理を可能とするため、オントロジーによって定められたクラスとプロパティを用いて記述される。オントロジーとは、エンティティのクラスおよびプロパティを定義したものであると共に、クラスとプロパティとの間に成り立つ制約を集めたものである。
【００１３】
クラスとは、後述するプロパティと呼ばれる性質が同じエンティティ同士を一つのグループにしたものである。例えば、くちばしを持ち、卵生の脊椎動物であり、前肢が翼になっている、という性質（プロパティ）を持つエンティティは、「鳥」というクラスあるいはその下位のクラスに分類される。また、「鳥」というクラスの中で、飛べない、という性質を持つエンティティは、例えば、「ペンギン」や「ダチョウ」という、より下位のクラスに分類される。このように、クラスの体系は、上位と下位の関係を有する階層構造をなし、上位のクラスの性質は、下位のクラスに継承される。上述した例では、「鳥」というクラスの、「くちばしを持ち、卵生の脊椎動物であり、前肢が翼になっている」という性質は、「ペンギン」や「ダチョウ」という下位のクラスの性質にも含まれることになる。クラスを識別するためのクラス名自体は必ずしもクラスの意味を表している必要はないが、以下の説明では簡単のためにクラスの意味を表すクラス名が与えられていることとする。
【００１４】
プロパティとは、エンティティの性質（または特徴）や、クラス間の関係を記述する属性である。例えば、プロパティは、「〜を体の構成要素としてもつ」という性質や、「〜に生息する」という性質を示す属性であってもよいし、「あるクラスが上位クラスであり、あるクラスが下位クラスである」というクラス間の上位下位の関係を示す属性であってもよい。プロパティを識別するためのプロパティ名自体は必ずしもプロパティの意味を表している必要はないが、以下の説明では簡単のためにプロパティの意味を表すプロパティ名が与えられていることとする。
【００１５】
ナレッジベースの基本的な単位は、ノード間を、ノード間の関係を表すラベル付きの方向性をもつエッジでつないだ３つ組であり、上述したエンティティはノードであり、プロパティはエッジであり、プロパティを用いて記述したエンティティの情報の値もノードで表現する。このような、ノード、エッジ、およびノードの値の３つを組み合わせたグラフにより、エンティティに関する情報やエンティティ間の関係が明確に表現される。
【００１６】
例えば、現実世界で新しく映画やドラマといったコンテンツが制作され、インターネット上で、それらコンテンツを話題にしたブログや公式サイトなどが公開されたとする。この場合、新規公開されたコンテンツのタイトルや、公式サイトのＵＲＬ（Uniform Resource Locator）などが新規エンティティとして既存のナレッジベースに登録される。既存のナレッジベースに登録された時点では、新規エンティティのクラスは定まっておらず、専ら人間が手動で決定したり、コンピュータがエンティティの抽出元であるコンテンツの文脈を解釈した上で、その文脈の意味に応じて自動的に決定したりする。しかしながら、ナレッジベース上では、依然としてクラスが定まっていない新規エンティティの数が多く、速やかにクラスを決定することが望まれている。
【００１７】
そこで、情報処理装置は、ナレッジベースにおいて、既にクラスが決定されたエンティティ（以下、クラス定義済みエンティティと称する）に関連したコンテンツの検索ログと、未だクラスが決定されていないエンティティ（以下、クラス未定義エンティティと称する）とに関連したコンテンツの検索ログとのそれぞれから、一つ以上のコンテキストタームを抽出する。クラス定義済みエンティティは、「第１エンティティ」の一例であり、クラス未定義エンティティは、「第２エンティティ」の一例である。
【００１８】
コンテキストタームとは、コンテンツを検索する際にユーザによって入力されるクエリに含まれ得るワード或いは表現である。例えば、「〇〇物語」というタイトルの書籍を検索する際に、ユーザが「〇〇物語＿漫画」という文字列をクエリとして入力したとする。アンダーバーはスペースを表している。このような場合に、ナレッジベース上に、「〇〇物語」という名称のエンティティが存在する場合、「〇〇物語」の後にスペースを挟んで続く「漫画」という文字列がコンテキスタームとなる。
【００１９】
情報処理装置は、一つ以上のコンテキストタームを抽出すると、そのコンテキストタームと、クラス定義済みエンティティのクラスとに基づいて、クラス未定義エンティティのクラスを決定する。これによって、ナレッジベースの情報量が充実するため、ナレッジベースをより有効活用することができる。
【００２０】
＜第１実施形態＞
［全体構成］
図１は、第１実施形態における情報処理装置１００を含む情報処理システム１の一例を示す図である。第１実施形態における情報処理システム１は、例えば、一つ以上の端末装置１０と、サービス提供装置２０と、情報処理装置１００とを備える。これらの装置のうち一部または全部は、ネットワークＮＷを介して互いに接続される。なお、これらの装置のうち一部は、仮想的な装置として他の装置に包含されてもよく、例えば、サービス提供装置２０の機能の一部または全部が、情報処理装置１００の機能によって実現される仮想マシンであってもよいし、これとは反対に、情報処理装置１００の機能の一部または全部が、サービス提供装置２０の機能によって実現される仮想マシンであってもよい。
【００２１】
図１に示す各装置は、ネットワークＮＷを介して種々の情報を送受信する。ネットワークＮＷは、例えば、無線基地局、Ｗｉ‐Ｆｉアクセスポイント、通信回線、プロバイダ、インターネットなどを含む。なお、図１に示す各装置の全ての組み合わせが相互に通信可能である必要はなく、ネットワークＮＷは、一部にローカルなネットワークを含んでもよい。
【００２２】
端末装置１０は、例えば、スマートフォンなどの携帯電話、タブレット端末、各種パーソナルコンピュータなどの、入力装置、表示装置、通信装置、記憶装置、および演算装置を備える端末装置である。通信装置は、ＮＩＣ（Network Interface Card）などのネットワークカード、無線通信モジュールなどを含む。端末装置１０では、ウェブブラウザやアプリケーションプログラムなどのＵＡ（User Agent）が起動し、ユーザの入力に応じたリクエストをサービス提供装置２０に送信する。また、ＵＡが起動された端末装置１０は、サービス提供装置２０から取得した情報に基づいて、表示装置に各種画像を表示させる。
【００２３】
サービス提供装置２０は、例えば、ＵＡとして起動されたウェブブラウザからのリクエストに応じてウェブページを端末装置１０に提供するウェブサーバである。ウェブページは、例えば、インターネット上において商品を販売するショッピングサイトやオークションサイト、フリーマーケットサイトといった各種ウェブサイトを構成するウェブページであってよい。また、サービス提供装置２０は、検索サイトやＳＮＳ（Social Networking Service）、メールサービスなどの各種サービスを提供するウェブページを端末装置１０に提供してもよい。また、サービス提供装置２０は、ＵＡとして起動されたアプリケーションからのリクエストに応じてコンテンツを端末装置１０に提供することで、販売サイトなどの各種ウェブサイトと同様のサービスを提供するアプリケーションサーバであってもよい。
【００２４】
例えば、サービス提供装置２０は、端末装置１０からクエリを取得した場合、クエリによる検索結果を端末装置１０に提供する。この際、サービス提供装置２０は、クエリの検索結果の一覧を表示させるページの所定領域に、クエリとして入力された単語や語句の実体或いは概念がどういったものであるのかを表す文字列や画像を表示させる。以下、所定領域をエンティティパネルと称して説明する。
【００２５】
図２は、エンティティパネルの一例を示す図である。例えば、現実世界において、「〇〇物語」というタイトルの漫画が存在しており、「検索太郎」という漫画家がその漫画を制作していたとする。この場合に、ユーザが端末装置１０を利用して、検索サイトなどのクエリの入力欄に「〇〇物語」という文字列を入力した場合、サービス提供装置２０は、ナレッジベースを参照し、「〇〇物語」という漫画の概要や漫画家名、他の漫画作品をエンティティパネルに表示させたり、「〇〇物語」に関する他の映画作品などをエンティティパネルに表示させたりする。なお、エンティティパネルは、検索サイトなどに限られず、ショッピングサイトや動画配信サイトなどにも表示されてよい。また、エンティティパネルを表示させることは、入力されたクエリに対応した検索結果を出力するものであれば、「検索」や「販売」といったサービスに限定されず、如何なるサービスにも適用されてよい。
【００２６】
情報処理装置１００は、オントロジーによってエンティティの概念が形式化されたナレッジベースにおいて、クラス未定義エンティティのクラスを決定する。ナレッジベースは、予め情報処理装置１００に記憶されていてもよいし、情報処理装置１００がウェブサイトを定期的にクロールすることで、ウェブサイトごとに生成してもよい。
【００２７】
［情報処理装置の構成］
図３は、第１実施形態における情報処理装置１００の構成の一例を示す図である。図示のように、情報処理装置１００は、例えば、通信部１０２と、制御部１１０と、記憶部１３０とを備える。
【００２８】
通信部１０２は、例えば、ＮＩＣ（Network Interface Card）等の通信インターフェースやＤＭＡ（Direct Memory Access）コントローラを含む。通信部１０２は、ネットワークＮＷを介して、サービス提供装置２０や他のウェブサーバと通信する。
【００２９】
制御部１１０は、例えば、抽出部１１２と、グラフ生成部１１４と、クラス決定部１１６とを備える。制御部１１０の構成要素は、例えば、ＣＰＵ（Central Processing Unit）やＧＰＵ（Graphics Processing Unit）などのプロセッサが記憶部１３０に格納されたプログラムを実行することにより実現される。また、制御部１１０の構成要素の一部または全部は、ＬＳＩ（Large Scale Integration）、ＡＳＩＣ（Application Specific Integrated Circuit）、ＦＰＧＡ（Field-Programmable Gate Array）などのハードウェア（回路部；circuitry）により実現されてもよいし、ソフトウェアとハードウェアの協働によって実現されてもよい。
【００３０】
記憶部１３０は、例えば、ＨＤＤ（Hard Disc Drive）、フラッシュメモリ、ＥＥＰＲＯＭ（Electrically Erasable Programmable Read Only Memory）、ＲＯＭ（Read Only Memory）、ＲＡＭ（Random Access Memory）などにより実現される。記憶部１３０には、ファームウェアやアプリケーションプログラムなどの各種プログラムの他に、ナレッジベース１３２と、検索ログ１３４とが格納される。
【００３１】
図４は、ナレッジベース１３２の一例を示す図である。ナレッジベース１３２は、例えば、ウェブサイトやアプリケーションを媒体として提供される百科事典を基にして生成されたナレッジベースであり、図示の例では、エンティティＥ０を最上位のクラスとし、矢印で表されたエッジを介してエンティティＥ０に接続された矢印先のエンティティＥ１〜Ｅ６が下位クラスとして定義されている。
【００３２】
エンティティＥ０には、「○○物語」という文字列がそのエンティティＥ０の名称を表すプロパティとして付与されており、そのエンティティＥ０に対して、「漫画家」というプロパティＰ１（エッジ）を介して、エンティティＥ１が接続されている。エンティティＥ１には、「検索太郎」という文字列がそのエンティティＥ１の名称を表すプロパティとして付与されている。従って、ナレッジベース１３２は、「○○大冒険」というエンティティＥ０の属性の一つである「漫画家」が、「検索太郎」であることを表現している。また、エンティティＥ０に対し、「掲載誌」というプロパティＰ２を介して「○○週刊誌」という名称のエンティティＥ２が接続されており、「出版日」というプロパティＰ３を介して「２０１３年」という名称のエンティティＥ３が接続されており、「ＵＲＬ」というプロパティＰ４を介して「ｈｔｔｐｓ：／／＊＊＊＊」という名称のエンティティＥ４が接続されており、「ジャンル」というプロパティＰ５を介して「漫画」という名称のエンティティＥ５が接続されており、「ジャンル」というプロパティＰ６を介して「映画」という名称のエンティティＥ６が接続されている。従って、図示のナレッジベース１３２は、「○○物語」について、「掲載誌」が「○○週刊誌」であり、「出版日」が「２０１３年」であり、「ＵＲＬ」が「ｈｔｔｐｓ：／／＊＊＊＊」であり、「ジャンル」が「漫画」と「映画」であることを有向グラフによって表している。なお、図４に例示するナレッジベース１３２は、あくまでも一例であり、適宜変更されてよい。
【００３３】
図５は、検索ログ１３４の一例を示す図である。図示の例のように、検索ログ１３４は、クエリとして入力した文字列に対して、そのクエリの検索結果として提示された一以上のＵＲＬのうち、ユーザが実際にクリックしたＵＲＬや、そのＵＲＬのクリック回数などが対応付けられたデータである。
【００３４】
［処理フロー］
以下、第１実施形態における制御部１１０による一連の処理の流れをフローチャートに即して説明する。図６は、第１実施形態における制御部１１０による一連の処理の流れを示すフローチャートである。本フローチャートの処理は、所定の周期で繰り返し行われてよい。
【００３５】
まず、抽出部１１２は、ナレッジベース１３２に登録された複数のエンティティの中に、クラス未定義エンティティが存在するか否かを判定する（Ｓ１００）。例えば、抽出部１１２は、ナレッジベース１３２に登録されてから間もないエンティティが存在する場合、クラス未定義エンティティが存在すると判定する。
【００３６】
抽出部１１２は、クラス未定義エンティティが存在すると判定すると、検索ログ１３４から、コンテキストタームを抽出する（Ｓ１０２）。例えば、抽出部１１２は、クラス未定義エンティティに関連したコンテンツが検索される際にクエリとして入力された文字列の中からコンテキストタームを抽出する。
【００３７】
図７は、コンテキストタームの抽出方法を説明するための図である。図中Ｅ１は、あるＵＲＬのエンティティを表しており、Ｅ２は、Ｅ１とは異なるＵＲＬのエンティティを表している。具体的には、エンティティＥ１は、映画関係のウェブサイトのＵＲＬを表し、エンティティＥ２は、漫画関係のウェブサイトのＵＲＬを表している。また、Ｅ３は、エンティティＥ１およびＥ２に対してエッジを介して接続されたエンティティを表しており、「〇〇物語」という文字列のエンティティを表している。エンティティＥ３にはプロパティが付与されておらず、そのクラスが未だ決定されていない。すなわち、エンティティＥ３は、クラス未定義エンティティであることを表している。そのため、エンティティＥ３は、「〇〇物語」というタイトルの映画を表しているのか、「〇〇物語」というタイトルの漫画を表しているのか、或いはその他の概念を表しているのか確定できない状態にある。
【００３８】
図示の例では、エンティティＥ１のＵＲＬは、「〇〇物語＿映画」というクエリを入力した一人または複数のユーザによってａ回クリックされ、「〇〇物語＿漫画」というクエリを入力した一人または複数のユーザによってｂ回クリックされていることを表している。また、エンティティＥ２のＵＲＬは、「〇〇物語＿映画」というクエリを入力した一人または複数のユーザによってｃ回クリックされ、「〇〇物語＿出演」というクエリを入力した一人または複数のユーザによってｄ回クリックされていることを表している。
【００３９】
このような場合、抽出部１１２は、クラス未定義エンティティＥ３のコンテキストタームとして、「漫画」というコンテキストタームＣ１と、「映画」というコンテキストタームＣ２と、「出演」というコンテキストタームＣ３とを検索ログ１３４から抽出する。
【００４０】
同様に、抽出部１１２は、クラス定義済みエンティティに関連したコンテンツが検索される際にクエリとして入力された文字列の中からコンテキストタームを抽出する。
【００４１】
図６のフローチャートの説明に戻る。次に、グラフ生成部１１４は、抽出部１１２によって抽出された一つ以上のコンテキストタームと、クラス定義済みエンティティと、クラス未定義エンティティとを用いて、二部グラフ（Bipartite graph）を生成する（Ｓ１０４）。
【００４２】
二部グラフとは、互いに独立したノード（頂点）を含む第１の部分集合と、同じく互いに独立したノードを含む第２の部分集合とが存在したときに、各部分集合内のノード同士の間にはエッジ（辺）が無く、第１の部分集合のノードと第２の部分集合のノードとの間にはエッジが存在し得るグラフである。本実施形態では、第１の部分集合には、クラス定義済みエンティティおよびクラス未定義エンティティが互いに独立したノードとして含まれ、第２の部分集合には、一つ以上のコンテキストタームが互いに独立したノードとして含まれる。
【００４３】
図８は、二部グラフの一例を示す図である。図示の例では、第１の部分集合に、「〇〇物語」という文字列のエンティティＥ３と、「◇◇体験記」という文字列のエンティティＥ４と、「△△日記」という文字列のエンティティＥ５とが互いに独立したノードとして含まれている。また、第２の部分集合に、「漫画」という文字列のコンテキストタームＣ１と、「映画」という文字列のコンテキストタームＣ２と、「出演」という文字列のコンテキストタームＣ３とが互いに独立したノードとして含まれている。
【００４４】
上述した例では、ナレッジベース１３２上で「〇〇物語」のエンティティＥ３に接続されたエンティティＥ１およびＥ２のＵＲＬに対応付けられたクエリから、コンテキストタームＣ１、Ｃ２、Ｃ３が抽出されている。従って、グラフ生成部１１４は、第１の部分集合にノードとして含まれるエンティティＥ３を、第２の部分集合のノードであるコンテキストタームＣ１、Ｃ２、Ｃ３のそれぞれにエッジを介して接続する。
【００４５】
エンティティＥ４およびＥ５は、エンティティＥ３とコンテキストタームとが共通している。すなわち、グラフ生成部１１４は、クラス未定義エンティティのコンテキストタームと、クラス定義済みエンティティのコンテキストタームとが共通するように、ナレッジベース１３２に含まれる複数のクラス定義済みエンティティの中から第１の部分集合に含めるクラス定義済みエンティティを選出する。これによって、第１の部分集合内で、クラス定義済みエンティティとクラス未定義エンティティとがエッジを介して互いに接続されなくとも、第２の部分集合のコンテキストタームを介して間接的にこれらのエンティティ同士を接続することができる。
【００４６】
グラフ生成部１１４は、第１の部分集合のノードと第２の部分集合のノードとをエッジを介して接続する際に、検索ログ１３４を参照し、各コンテキストタームの抽出元のクエリによって検索されたＵＲＬのクリック回数に応じて、各エッジを重みづける。
【００４７】
例えば、グラフ生成部１１４は、クリック回数そのものをエッジの重み係数ｗとしてもよいし、クリック回数に何らかの係数を乗算したり、バイアス成分を加えたりした値をエッジの重み係数ｗとしてもよい。以下、一例として、エッジの重み係数ｗがクリック回数であるものとして説明する。なお、グラフ生成部１１４は、クリック回数に代えて、或いは加えて、インプレッション回数やコンバージョン回数、コンバージョン率、クリック率といった他の統計的指標値に基づいて各エッジを重み付けてもよい。
【００４８】
上述した例では、ナレッジベース１３２上において、エンティティＥ３に接続されたエンティティＥ１およびＥ２のうち、エンティティＥ１のＵＲＬは、「漫画」というコンテキストタームＣ１を含むクエリを入力したユーザによってｂ回クリックされ、エンティティＥ２のＵＲＬは、「漫画」というコンテキストタームＣ１を含むクエリを入力したユーザによって一度もクリックされていない。
【００４９】
そのため、グラフ生成部１１４は、二部グラフにおいて、第１の部分集合に含まれるエンティティＥ３と、第２の部分集合に含まれるコンテキストタームＣ１とを互いに接続するエッジの重み係数ｗを「ｂ」に決定する。
【００５０】
また、上述した例では、ナレッジベース１３２上において、エンティティＥ３に接続されたエンティティＥ１およびＥ２のうち、エンティティＥ１のＵＲＬは、「映画」というコンテキストタームＣ２を含むクエリを入力したユーザによってａ回クリックされ、エンティティＥ２のＵＲＬは、「映画」というコンテキストタームＣ２を含むクエリを入力したユーザによってｃ回クリックされている。
【００５１】
そのため、グラフ生成部１１４は、二部グラフにおいて、第１の部分集合に含まれるエンティティＥ３と、第２の部分集合に含まれるコンテキストタームＣ２とを互いに接続するエッジの重み係数ｗを「ａ＋ｃ」に決定する。
【００５２】
また、上述した例では、ナレッジベース１３２上において、エンティティＥ３に接続されたエンティティＥ１およびＥ２のうち、エンティティＥ１のＵＲＬは、「出演」というコンテキストタームＣ３を含むクエリを入力したユーザによって一度もクリックされておらず、エンティティＥ２のＵＲＬは、「出演」というコンテキストタームＣ３を含むクエリを入力したユーザによってｄ回クリックされている。
【００５３】
そのため、グラフ生成部１１４は、二部グラフにおいて、第１の部分集合に含まれるエンティティＥ３と、第２の部分集合に含まれるコンテキストタームＣ３とを互いに接続するエッジの重み係数ｗを「ｄ」に決定する。
【００５４】
グラフ生成部１１４は、各エッジの重み係数ｗを決定すると、数式（１）に基づいて、各エッジの重み係数ｗを正規化する。
【００５５】
【数１】
2020154583.tif 000003
【００５６】
例えば、第１の部分集合に含まれるｉ番目のノードと、第２の部分集合に含まれるｊ番目のノードとの間に接続されるエッジの重み係数ｗｉｊは、その重み係数ｗｉｊを、ｉ番目のノードに接続される全エッジの重み係数の合計値で除算することで正規化される。
【００５７】
例えば、エンティティＥ３に着目した場合、エンティティＥ３は、コンテキストタームＣ１、Ｃ２、Ｃ３のそれぞれにエッジを介して接続されている。従って、グラフ生成部１１４は、エンティティＥ３とコンテキストタームＣ１との間のエッジの重み係数ｗを、「ｂ／（ａ＋ｂ＋ｃ＋ｄ）」とし、エンティティＥ３とコンテキストタームＣ２との間のエッジの重み係数ｗを、「（ａ＋ｃ）／（ａ＋ｂ＋ｃ＋ｄ）」とし、エンティティＥ３とコンテキストタームＣ３との間のエッジの重み係数ｗを、「ｄ／（ａ＋ｂ＋ｃ＋ｄ）」とする。
【００５８】
このように、各エッジの重み係数ｗを正規化することで、第１の部分集合のノードと第２の部分集合のノードとの間を状態遷移確率によって表すことができる。
【００５９】
図６のフローチャートの説明に戻る。次に、クラス決定部１１６は、ラベルスプレッディング法と呼ばれる半教師あり学習を利用して、クラス未定義エンティティのクラスを決定する（Ｓ１０６）。これによって本フローチャートの処理が終了する。
【００６０】
［ラベルスプレッディング法］
図９は、ラベルスプレッディング法の一連の処理の流れを示すフローチャートである。本フローチャートの処理は、上述したＳ１０６の処理に相当する。
【００６１】
まず、クラス決定部１１６は、グラフ生成部１１４によって生成された二部グラフの各ノードにクラスを割り当て、そのクラスを初期化する（Ｓ２００）。
【００６２】
図１０は、二部グラフの初期化の様子を模式的に示す図である。図中Ｘは、二部グラフの各ノードを表している。また、図示の例では、説明を簡略化するために、第１の部分集合に含まれるノード数を３とし、第２の部分集合に含まれるノード数を１としている。これらの複数のノードＸのうち、ノードＸ１およびＸ３は、クラス定義済みエンティティを表し、ノードＸ４は、クラス未定義エンティティを表すものとする。更に、クラス定義済みエンティティであるノードＸ１のクラスはαであり、クラス定義済みエンティティであるノードＸ３のクラスはβであるものとする。
【００６３】
例えば、既存のナレッジベース１３２のオントロジーにおいて、α、β、γの計３種類のクラスが定められている場合、クラス決定部１１６は、二部グラフの各ノードに３種類のクラスをラベルとして割り当てる。そして、クラス決定部１１６は、クラス定義済みエンティティを除いた全ノードＸのクラスを初期化する。
【００６４】
例えば、α、β、γの各クラスを数値で表した場合、クラス値が１．０であれば、そのノードＸはそのクラスに属し、クラス値が０．０であれば、そのノードＸはそのクラスに属さないということを意味する。クラス定義済みエンティティであるノードＸ１については、クラスαであることが既に定められているため、αのクラス値を１．０とし、他のクラス値を０．０とする。同様に、クラス定義済みエンティティであるノードＸ３については、クラスβであることが既に定められているため、βのクラス値を１．０とし、他のクラス値を０．０とする。クラス未定義エンティティであるノードＸ４については、未だクラスが定められていないため、全てのクラス値を０．０とする。また、コンテキストタームであるノードＸ２については、ナレッジベース１３２に含まれるエンティティではないものの、全てのクラス値が０．０であるクラスをラベルとして付与する。
【００６５】
図９のフローチャートの説明に戻る。次に、クラス決定部１１６は、数式（２）に基づいて、クラス行列Ｆと重み行列Ｗとの積を計算し、クラス行列Ｆを更新する（Ｓ２０２）。式中Ｆｔ−１は、更新前のクラス行列を表し、Ｆｔは、更新後のクラス行列を表している。
【００６６】
【数２】
2020154583.tif 000004
【００６７】
数式（３）は、図１０に例示する二部グラフのクラス行列Ｆを表している。クラス行列Ｆは、「第１行列」の一例である。
【００６８】
【数３】
2020154583.tif 000005
【００６９】
クラス行列Ｆは、各ノードＸのクラス値を行とした行列である。第１行は、ノードＸ１のクラス値を［α１  β１  γ１］＝［１．０  ０．０  ０．０］というベクトルで表しており、第２行は、ノードＸ２のクラス値を［α２  β２  γ２］＝［０．０  ０．０  ０．０］というベクトルで表しており、第３行は、ノードＸ３のクラス値を［α３  β３  γ３］＝［０．０  １．０  ０．０］というベクトルで表しており、第４行は、ノードＸ４のクラス値を［α４  β４  γ４］＝［０．０  ０．０  ０．０］というベクトルで表している。
【００７０】
数式（４）は、図１０に例示する二部グラフの重み行列Ｗを表している。重み行列Ｗは、「第２行列」の一例である。
【００７１】
【数４】
2020154583.tif 000006
【００７２】
重み行列Ｗは、各エッジの正規化された重み係数ｗｉｊを要素とした行列である。図１０に例示する二部グラフでは、ノードＸ１およびノードＸ２間と、ノードＸ３およびノードＸ２間と、ノードＸ４およびノードＸ２間とに重み係数ｗ付きエッジが接続されている。そのため、重み行列Ｗは、要素ｗ１２、ｗ２１、ｗ２３、ｗ２４、ｗ３２、ｗ４２を除いて、その他の全要素が０の行列となる。
【００７３】
このように、クラス決定部１１６は、クラス行列Ｆｔ−１と重み行列Ｗとの積を計算すると、その積である行列を、新たなクラス行列Ｆｔとする。これによって、クラス値が初期化されたノードＸ２、Ｘ４だけでなく、既にクラス値が決定されているノードＸ１、Ｘ３についても、そのクラス値が更新される。
【００７４】
次に、クラス決定部１１６は、更新後のクラス行列Ｆｔと更新前のクラス行列Ｆｔ−１とを比較し、更新後のクラス行列Ｆｔが収束したか否かを判定する（Ｓ２０４）。ラベルスプレッディング法では、対象とするグラフが二部グラフであれば、ラベル（本実施形態ではクラス）の伝搬の繰り返すことで、ある一つの値に収束することが知られている。従って、クラス決定部１１６は、更新後のクラス行列Ｆｔが収束していなければ、Ｓ２０２に処理を戻し、クラス行列Ｆｔが収束するまで、クラス行列Ｆｔを更新することを繰り返す。
【００７５】
一方、クラス決定部１１６は、更新後のクラス行列Ｆｔが収束した場合、そのクラス行列Ｆｔの要素であるクラス値に基づいて、クラス定義済みエンティティのクラスを再決定するとともに、未定義エンティティのクラスを決定する（Ｓ２０６）。
【００７６】
図１１は、クラス行列Ｆが収束したときの二部グラフを模式的に示す図である。図示の例では、クラス定義済みエンティティを表すノードＸ１のクラス値は、αが０．８であり、βが０．２であり、γが０．０である。また、クラス定義済みエンティティを表すノードＸ３のクラス値は、αが０．３であり、βが０．７であり、γが０．０である。
【００７７】
ラベルスプレッディング法の適用前では、ノードＸ１としたクラス定義済みエンティティは、αが唯一のクラスであり、ノードＸ３としたクラス定義済みエンティティは、βが唯一のクラスであった。
【００７８】
一方、ラベルスプレッディング法の適用後では、ノードＸ１としたクラス定義済みエンティティのクラスは、αであることの尤度が最も大きく、βであることの尤度が次点で大きい。また、ノードＸ３としたクラス定義済みエンティティのクラスは、βであることの尤度が最も大きく、αであることの尤度が次点で大きい。従って、クラス決定部１１６は、ノードＸ１としたクラス定義済みエンティティのクラスがαおよびβであり、ノードＸ３としたクラス定義済みエンティティのクラスがαおよびβであると再決定する。
【００７９】
また、ラベルスプレッディング法の適用前では、ノードＸ４としたクラス未定義エンティティは、いずれかのクラスであるのか決まっていなかった。
【００８０】
一方、ラベルスプレッディング法の適用後では、ノードＸ４としたクラス未定義エンティティのクラスは、αであることの尤度が最も大きく、βおよびγであることの尤度が次点で大きい。従って、クラス決定部１１６は、ノードＸ４としたクラス定義済みエンティティのクラスがα、β、およびγであると決定する。
【００８１】
また、クラス決定部１１６は、ラベルスプレッディング法を適用して収束したクラス値に基づいてクラスを決定する際に、そのクラス値に閾値を設定し、クラス値が閾値以上となったクラスのみを各エンティティのクラスとしてもよい。
【００８２】
なお、第２の部分集合のノードＸ２であるコンテキストタームにもクラスをラベルとして割り振っているため、コンテキストタームのクラスも付随的に決定される。図示の例では、ノードＸ２としたコンテキストタームのクラスは、β、α、γの順に尤度が大きい。従って、クラス決定部１１６は、ノードＸ２としたコンテキストタームのクラスがα、β、およびγであると決定する。
【００８３】
以上説明した第１実施形態によれば、情報処理装置１００は、クラス定義済みエンティティに関連したコンテンツの検索ログから一つ以上のコンテキストタームを抽出するとともに、クラス未定義エンティティに関連したコンテンツの検索ログから一つ以上のコンテキストタームを抽出する。情報処理装置１００は、クラス未定義エンティティと共通するコンテキストタームを抽出したクラス定義済みエンティティと、クラス未定義エンティティとを第１の部分集合とし、それらエンティティで共通するコンテキストタームを第２の部分集合とした二部グラフを生成する。そして、情報処理装置１００は、二部グラフにラベルスプレッディング法を適用することで、少なくともクラス未定義エンティティのクラスを決定する。
【００８４】
これによって、例えば、現実世界で新しい言葉が流行したり、新作のコンテンツが公開されたりした場合であっても、既にクラスが決定されているナレッジベース１３２上のエンティティと、そのエンティティに関連付けられたコンテンツにアクセスするためにユーザが入力したクエリとに基づいて、流行語のエンティティや新作コンテンツのエンティティのクラスを速やかに決定することができる。この結果、ナレッジベースの情報量が充実するため、ナレッジベースをより有効活用することができる。
【００８５】
＜第１実施形態の変形例＞
以下、第１実施形態の変形例について説明する。上述した第１実施形態では、二部グラフにラベルスプレッディング法を適用して、クラス未定義エンティティのクラスを決定し、更には、クラス定義済みエンティティのクラスも再決定するものとして説明したがこれに限られない。例えば、クラス決定部１１６は、二部グラフにラベルスプレッディング法を適用する代わりに、ラベルプロパゲーティング法を適用してクラス未定義エンティティのクラスを決定してもよい。ラベルプロパゲーティング法とは、ラベルスプレッディング法とは異なり、クラス行列Ｆにおいて、クラス定義済みエンティティのクラス値は初期値から変更しない手法である。このような手法を利用することでも、クラス未定義エンティティのクラスを決定することができる。
【００８６】
＜第２実施形態＞
以下、第２実施形態について説明する。第２実施形態では、クラス未定義エンティティのクラスを新たに決定する際に、二部グラフの第２の部分集合に含めるコンテキストタームのクラスを初期化しない点で上述した第１実施形態と相違する。以下、第１実施形態との相違点を中心に説明し、第１実施形態と共通する点については説明を省略する。なお、第２実施形態の説明において、第１実施形態と同じ部分については同一符号を付して説明する。
【００８７】
図１２は、二部グラフの初期化の様子を模式的に示す図である。図に例示する二部グラフでは、クラス未定義エンティティを表すノードＸ４のクラスがα、β、およびγに決定された後に、新たなクラス未定義エンティティを表すノードＸ５が第１の部分集合に追加されている。図示の例では、ノードＸ５のコンテキストタームは、ノードＸ１、Ｘ３、Ｘ４のコンテキストタームと同じであり、ノードＸ２に対して、ノードＸ１、Ｘ３、Ｘ４、Ｘ５が重み付きエッジを介して接続されている。
【００８８】
このような場合、クラス決定部１１６は、ノードＸ５にクラスを割り当て、そのクラス値を例えば０．０といった数値で初期化する。この際、クラス決定部１１６は、第１の部分集合に含まれるノードＸ１、Ｘ３、Ｘ４だけでなく、第２の部分集合に含まれるノードＸ２についても初期化せず、前回の処理結果であるクラス値を保持する。例えば、前回の処理でコンテキストタームを表すノードＸ２のクラス値が（α，β，γ）＝（０．２，０．７，０．１）に決定されていた場合、クラス決定部１１６は、新たなクラス未定義エンティティを表すノードＸ５のクラス値を決定する際に、ノードＸ２のクラス値として（０．２，０．７，０．１）を利用する。このように、コンテキストタームのクラス値を次回以降も引き続き利用することで、クラス行列Ｆが収束までの処理回数を少なくすることができる。
【００８９】
以上説明した第２実施形態によれば、情報処理装置１００は、クラス未定義エンティティのクラスを新たに決定する際に、二部グラフの第２の部分集合に含めるコンテキストタームのクラスを初期化せず、前回のクラスを引き続き利用することで、クラス行列Ｆが収束までの処理回数を少なくすることができる。
【００９０】
＜ハードウェア構成＞
上述した実施形態の情報処理装置１００は、例えば、図１３に示すようなハードウェア構成により実現される。図１３は、実施形態の情報処理装置１００のハードウェア構成の一例を示す図である。
【００９１】
情報処理装置１００は、ＮＩＣ１００−１、ＣＰＵ１００−２、ＲＡＭ１００−３、ＲＯＭ１００−４、フラッシュメモリやＨＤＤなどの二次記憶装置１００−５、およびドライブ装置１００−６が、内部バスあるいは専用通信線によって相互に接続された構成となっている。ドライブ装置１００−６には、光ディスクなどの可搬型記憶媒体が装着される。二次記憶装置１００−５、またはドライブ装置１００−６に装着された可搬型記憶媒体に格納されたプログラムがＤＭＡコントローラ（不図示）などによってＲＡＭ１００−３に展開され、ＣＰＵ１００−２によって実行されることで、制御部１１０が実現される。制御部１１０が参照するプログラムは、ネットワークＮＷを介して他の装置からダウンロードされてもよい。
【００９２】
以上、本発明を実施するための形態について実施形態を用いて説明したが、本発明はこうした実施形態に何ら限定されるものではなく、本発明の要旨を逸脱しない範囲内において種々の変形及び置換を加えることができる。
【符号の説明】
【００９３】
１…情報処理システム、１０…端末装置、２０…サービス提供装置、１００…情報処理装置、１０２…通信部、１１０…制御部、１１２…抽出部、１１４…グラフ生成部、１１６…クラス決定部、１３０…記憶部
【図１】
2020154583.tif 000007
【図２】
2020154583.tif 000008
【図３】
2020154583.tif 000009
【図４】
2020154583.tif 000010
【図５】
2020154583.tif 000011
【図６】
2020154583.tif 000012
【図７】
2020154583.tif 000013
【図８】
2020154583.tif 000014
【図９】
2020154583.tif 000015
【図１０】
2020154583.tif 000016
【図１１】
2020154583.tif 000017
【図１２】
2020154583.tif 000018
【図１３】
2020154583.tif 000019