(57)【要約】【課題】エンティティリンキングの精度を維持しつつ、ナレッジグラフの情報量を削減する。【解決手段】情報処理装置１は、ナレッジグラフのエンティティと、テキスト中の単語とを対応付けるエンティティリンキングを実行する際に、ナレッジグラフの中の遷移元の第１ノードに接続されるエッジの数と、遷移先の第２ノードに接続されるエッジの数とに基づいて、ナレッジグラフのうち予め設定された次数の第２ノードと接続されたエッジから削除すべきエッジを特定する。そして、情報処理装置１は、該特定したエッジを削除したナレッジグラフを生成し、生成したナレッジグラフについて、削除されたエッジで接続されていた第１ノードおよび第２ノードを、削除されていないエッジで接続された第３ノードを介して接続し、テキスト中の単語と、当該単語と対応付けたエンティティをユーザに提示する。【選択図】図１１
2020187419.tif 000002
【特許請求の範囲】
【請求項１】
ナレッジグラフのエンティティと、テキスト中の単語とを対応付けるエンティティリンキング方法であって、
前記ナレッジグラフの中の遷移元の第１ノードに接続されるエッジの数と、遷移先の第２ノードに接続されるエッジの数とに基づいて、前記ナレッジグラフのうち予め設定された次数の第２ノードと接続されたエッジから削除すべきエッジを特定し、
該特定したエッジを削除したナレッジグラフを生成し、
削除されたエッジで接続されていた第１ノードおよび第２ノードを、削除されていないエッジで接続された第３ノードを介して接続し、前記テキスト中の単語と、当該単語と対応付けたエンティティをユーザに提示する、
処理をコンピュータが実行することを特徴とするエンティティリンキング方法。
【請求項２】
該特定する処理は、
前記遷移先の第２ノードに遷移するエッジの次数に応じて前記第２ノードをクラスタリングし、
該クラスタリングされた各クラスタに遷移するエッジの集合に対して、予め定められた全体のエッジの削減数に応じた削減数を割り当て、
前記エッジの集合ごとに、割り当てられた削減数分の削除すべきエッジを特定する
処理を実行することを特徴とする請求項１に記載のエンティティリンキング方法。
【請求項３】
該特定する処理は、さらに、エッジの集合の中から、重要度の小さい順に、割り当てられた削減数分のエッジを削減すべきエッジとして特定する
処理を実行することを特徴とする請求項２に記載のエンティティリンキング方法。
【請求項４】
ナレッジグラフのエンティティと、テキスト中の単語とを対応付けるエンティティリンキングを実行する情報処理装置であって、
前記ナレッジグラフの中の遷移元の第１ノードに接続されるエッジの数と、遷移先の第２ノードに接続されるエッジの数とに基づいて、前記ナレッジグラフのうち予め設定された次数の第２ノードと接続されたエッジから削除すべきエッジを特定する特定部と、
前記特定部によって特定されたエッジを削除したナレッジグラフを生成する生成部と、
削除されたエッジで接続されていた第１ノードおよび第２ノードを、削除されていないエッジで接続された第３ノードを介して接続し、前記テキスト中の単語と、当該単語と対応付けたエンティティをユーザに提示する提示部と、
を有することを特徴とする情報処理装置。
【請求項５】
ナレッジグラフのエンティティと、テキスト中の単語とを対応付けるエンティティリンキングプログラムであって、
前記ナレッジグラフの中の遷移元の第１ノードに接続されるエッジの数と、遷移先の第２ノードに接続されるエッジの数とに基づいて、前記ナレッジグラフのうち予め設定された次数の第２ノードと接続されたエッジから削除すべきエッジを特定し、
該特定したエッジを削除したナレッジグラフを生成し、
削除されたエッジで接続されていた第１ノードおよび第２ノードを、削除されていないエッジで接続された第３ノードを介して接続し、前記テキスト中の単語と、当該単語と対応付けたエンティティをユーザに提示する、
処理をコンピュータに実行させることを特徴とするエンティティリンキングプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、エンティティリンキング方法などに関する。
【背景技術】
【０００２】
自然言語処理では、単語を知識情報である知識ベースとリンクさせる手法としてエンティティリンキングという手法が知られている（例えば、特許文献１〜４）。エンティティリンキングの手法では、テキストの中の単語と、知識ベースであるナレッジグラフの中のエンティティとを対応付ける。
【０００３】
エンティティリンキングの手順の一例は以下のとおりである。エンティティリンキングを行う装置は、知識ベースの各エンティティ（ノード）を事前に何らかの方法でスコアリングする。装置は、入力される入力文から、単語を抽出する。装置は、知識ベースから、単語と各ノードとの組をスコアリングし、最もスコアの高い組の単語とノードとを対応付ける。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２０１２−４３２９４号公報
【特許文献２】特開２０１７−４０９７号公報
【特許文献３】特開２０１４−２２９０４７号公報
【特許文献４】特開２０１４−２４１１２２号公報
【非特許文献】
【０００５】
【非特許文献１】Knowledge-rich  Word  Sense  Disambiguation  Rivaling  Supervised  Systems［2010］
【発明の概要】
【発明が解決しようとする課題】
【０００６】
しかしながら、エンティティリンキングでは、ナレッジグラフのエッジが多いと、スコア計算の際に、参照すべき情報が多くなるため、計算量が増大する。そこで、計算量を減少させるために、ナレッジグラフから、スコアを利用してスコアの低い順からエッジを削除することが考えらえる。ところが、ナレッジグラフから、スコアを利用してエッジを削除すると、本来接続されているべきノード間のエッジが削除されてしまうことがある。次数の大きなノードに接続しているエッジは、スコアが低いため、削除されやすい。エッジが削除されると、他のノードを介した接続があれば、スコア計算への影響は軽微であるが、他のノードを介した接続がないと、スコア計算への影響は大きい。
【０００７】
本発明は、１つの側面では、エンティティリンキングの精度を維持しつつ、ナレッジグラフの情報量を削減することを目的とする。
【課題を解決するための手段】
【０００８】
１つの態様では、エンティティリンキング方法は、ナレッジグラフのエンティティと、テキスト中の単語とを対応付けるエンティティリンキング方法であって、前記ナレッジグラフの中の遷移元の第１ノード（主語）に接続されるエッジの数と、遷移先（目的語）の第２ノードに接続されるエッジの数とに基づいて、前記ナレッジグラフのうち予め設定された次数の第２ノードと接続されたエッジから削除すべきエッジを特定し、該特定したエッジを削除したナレッジグラフを生成し、削除されたエッジで接続されていた第１ノードおよび第２ノードを、削除されていないエッジで接続された第３ノードを介して、前記テキスト中の単語と、当該単語と対応付けたエンティティをユーザに提示する、処理をコンピュータが実行する。
【発明の効果】
【０００９】
１実施態様によれば、ナレッジグラフの情報量を削減するが、エンティティリンキングの精度を維持できる。
【図面の簡単な説明】
【００１０】
【図１】図１は、実施例に係る情報処理装置の機能構成を示すブロック図である。
【図２】図２は、述語削減の考え方を説明する図（１）である。
【図３】図３は、述語削減の考え方を説明する図（２）である。
【図４】図４は、実施例に係る述語スコア計算の一例を示す図である。
【図５】図５は、実施例に係る統合スコア計算の一例を示す図である。
【図６】図６は、実施例に係るクラスタリングの一例を示す図である。
【図７Ａ】図７Ａは、実施例に係る削減数割当の一例を示す図（１）である。
【図７Ｂ】図７Ｂは、実施例に係る削減数割当の一例を示す図（２）である。
【図８】図８は、実施例に係る削減対象選択の一例を示す図である。
【図９】図９は、実施例に係る削減した結果の一例を示す図である。
【図１０】図１０は、実施例に係るエンティティリンキング実行の一例を示す図である。
【図１１】図１１は、実施例に係る情報処理のフローチャートの一例を示す図である。
【図１２】図１２は、実施例に係る削減数割当処理のフローチャートの一例を示す図である。
【図１３】図１３は、クラスタリングしないでスコア順に削減した結果の参考例を示す図である。
【図１４】図１４は、クラスタリングしないでスコア順に削減した場合のエンティティリンキング実行の参考例を示す図である。
【図１５】図１５は、エンティティリンキングプログラムを実行するコンピュータの一例を示す図である。
【図１６】図１６は、エンティティリンキングの参考例を示す図である。
【図１７】図１７は、エンティティリンキングの課題の概念を示す図である。
【発明を実施するための形態】
【００１１】
以下に、本願の開示するエンティティリンキング方法、情報処理装置およびエンティティリンキングプログラムの実施例を図面に基づいて詳細に説明する。なお、本発明は、実施例により限定されるものではない。
【実施例】
【００１２】
まず、知識ベースを利用したエンティティリンキングの課題の概念を、図１６および図１７を参照して説明する。図１６は、エンティティリンキングの参考例を示す図である。図１６に示すように、入力文と知識ベースとが示されている。知識ベースは、ナレッジグラフで示されている。ナレッジグラフは、各エンティティをノードとし、エンティティ間のスコアをエッジの重みとして持つグラフのことをいう。つまり、エンティティリンキングでは、入力文の中のメンション（単語）と、知識ベースであるナレッジグラフのエンティティ（ノード）とを、エッジの重みを利用して対応付ける。
【００１３】
ここで、知識ベースでは、１つの情報は、主語、述語、目的語の３つの組で表現される。例えば、符号Ｇ０で示すように、主語として「武蔵中原」、述語として「locatedIn」、目的語として「川崎市」が１つの情報として表現される。そして、それぞれの情報は、グラフとして可視化される。なお、主語と目的語はノードで表わされ、述語はエッジで表わされる。
【００１４】
そして、エンティティリンキングでは、入力文が、例えば「友達と東横線で小杉に行って、グランツリーで買い物した」の場合には、入力文の中の「東横線」と、知識ベースの「東急東横線」のノードとがスコアを利用して対応付けられる。入力文の中の「小杉」と、知識ベースの「武蔵小杉」のノードとがスコアを利用して対応付けられる。入力文の中の「グランツリー」と、知識ベースの「グランツリー」のノードとがスコアを利用して対応付けられる。
【００１５】
図１７は、エンティティリンキングの課題の概念を示す図である。図１７に示すように、ナレッジグラフから、スコアを利用してエッジを削除すると、本来接続されているべきノード間のエッジが削除されてしまうことがある。特に、次数の大きいノードに接続されているエッジは、スコアが低いため、エッジが削除されやすい。例えば、図１７では、「武蔵小杉」のノードは、他のノードと比べて次数が大きいとする。すると、「武蔵小杉」のノードに接続されている「南武線」、「武蔵中原」、「川崎市」に遷移するそれぞれのエッジが削除されやすい。また、「東急東横線」、「グランツリー」、「東急スクエア」や「タワープレイス」に遷移するそれぞれのエッジが削除されやすい。
【００１６】
スコアが小さいいずれかのエッジが削除される場合、ノード間が直接的ではないが間接的にエッジで接続される場合には、スコア計算への影響は軽微である。ところが、スコアが小さいいずれかのエッジが削除される場合、ノード間が直接的にも間接的にもエッジで接続されなくなる場合がある。かかる場合には、スコア計算への影響は大きい。すなわち、エンティティリンキングの精度が落ちてしまう。例えば、図１７では、「武蔵小杉」のノードから「南武線」のノードに遷移するエッジが削除されても、「武蔵小杉」→「武蔵中原」→「南武線」とノード間が間接的にエッジで接続されるため、スコア計算への影響は軽微である。ところが、「武蔵小杉」のノードから「東急東横線」のノードに遷移するエッジが削除されると、ノード間が直接的にも間接的にもエッジで接続されなくなるので、スコア計算への影響は大きい。すなわち、エンティティリンキングの精度が落ちてしまう。つまり、ナレッジグラフの情報量を減少させるためにエッジを削除すると、エンティティリンキングの精度が落ちるという課題がある。
【００１７】
そこで、エンティティリンキングの精度を維持しつつ、ナレッジグラフの情報量を削減する情報処理装置について、以下に説明する。
【００１８】
［情報処理装置の構成］
図１は、実施例に係る情報処理装置の機能構成を示すブロック図である。図１に示すように、情報処理装置１は、述語スコア計算部１１、統合スコア計算部１２、クラスタリング部１３、削減数割当部１４、削減対象選択部１５およびエンティティリンキング実行部１６を有する。これらの機能部は、図示しない制御部に含まれる。制御部は、ＣＰＵ（Central  Processing  Unit）などの電子回路に対応する。そして、制御部は、各種の処理手順を規定したプログラムや制御データを格納するための内部メモリを有し、これらによって種々の処理を実行する。なお、述語スコア計算部１１〜削減対象選択部１５は、特定部の一例である。エンティティリンキング実行部１６は、生成部および提示部の一例である。
【００１９】
また、情報処理装置１は、知識ベース２１、述語スコア記憶部２２、統合スコア記憶部２３およびクラスタ情報記憶部２４を有する。これらの機能部は、図示しない記憶部に含まれる。記憶部は、例えば、ＲＡＭ、フラッシュメモリ（Flash  Memory）などの半導体メモリ素子、または、ハードディスク、光ディスクなどの記憶装置である。
【００２０】
知識ベース２１は、ナレッジグラフの情報を示す。なお、知識ベース２１は、予め記憶部に記憶される。
【００２１】
述語スコア記憶部２２は、知識ベース２１に含まれる述語のスコアを記憶する。なお、述語スコア記憶部２２は、述語スコア計算部１１によって生成される。
【００２２】
統合スコア記憶部２３は、知識ベース２１に含まれる述語（エッジ）の統合スコアを記憶する。なお、統合スコア記憶部２３は、統合スコア計算部１２によって生成される。
【００２３】
クラスタ情報記憶部２４は、エンティティを述語の入次数に応じてクラスタリングした結果を示すクラスタ情報を記憶する。すなわち、クラスタ情報は、ナレッジグラフ内のノードをエッジの入力の次数に応じてクラスタリングした結果を示す情報である。なお、クラスタ情報記憶部２４は、クラスタリング部１３によって生成される。
【００２４】
述語スコア計算部１１は、知識ベース２１内の述語のスコアを計算する。すなわち、述語スコア計算部１１は、目的語から見た場合の述語の重要度をスコアとして計算する。例えば、述語スコア計算部１１は、述語ｐが目的語ｏｐへ遷移する確率をＰ（ｏｐ）とすると、目的語ｏｐへ遷移する述語ｐのスコアＨｏｐ（ｐ）を、以下の式（１）のように計算する。なお、述語は、ナレッジグラフのエッジに対応する。
【数１】
2020187419.tif 000003
【００２５】
すなわち、述語ｐのスコアＨｏｐ（ｐ）は、述語ｐが目的語ｏｐへの遷移が起こる場合の情報量として計算される。述語ｐが目的語ｏｐへ遷移する確率Ｐ（ｏｐ）が高い程、情報量が低くなる。つまり、情報量が示す情報は曖昧となる。ここで、確率Ｐ（ｏｐ）が高いとは、述語ｐがあったとき、述語ｐの遷移先を示す目的語は、ｏｐのことが多いことを表す。つまり、目的語ｏｐは、述語ｐの遷移元を示す主語を判別するための情報として役に立ちにくい。したがって、目的語から見た場合に、主語を判別するための情報として役に立ちにくい述語を、削除すべき述語とする。
【００２６】
図２は、述語削減の考え方を説明する図（１）である。図２に示すように、目的語ｏｐが「川崎市」である場合に、目的語としての「川崎市」へ述語ｐとしての「locatedIn」が遷移する確率が高い程、情報量が低くなる。すなわち、「川崎市」である目的語ｏｐは、「locatedIn」である述語ｐの遷移元を示すそれぞれのエンティティ（主語）を判別するための情報として役に立ちにくい。情報量が低く、情報量が示す情報が曖昧であるからである。そこで、目的語から見た場合の情報量が低い述語を削除するようにしたい。なお、かかる述語削減の考え方だけでノードが削除されても、ノード（エンティティ）間が直接的および間接的にエッジで接続されなくなる場合があるので、エンティティリンキングの精度が落ちてしまうという課題を解決するには、不十分である。
【００２７】
図１に戻って、統合スコア計算部１２は、知識ベース２１内の述語の統合スコアを計算する。すなわち、統合スコア計算部１２は、主語から見た場合の述語の相対的な重要度を統合スコアとして計算する。例えば、統合スコア計算部１２は、主語ｓの出次数をｎ、主語ｓの目的語ｏｎに対応する述語ｐｎのスコアをＨｏｐｎ（ｐｎ）とし、ｓを主語とする述語ｐｘの統合スコアＩ（ｐｘ）を、以下の式（２）のように計算する。ここでいう出次数とは、遷移元の主語のノードから遷移する（出る）エッジの次数のことをいう。
【数２】
2020187419.tif 000004
【００２８】
すなわち、述語ｐｘの統合スコアＩ（ｐｘ）は、主語から見た場合のそれぞれの述語の重要性を反映するために、述語ｐｘの重要度（スコア）の値を、述語ｐｘに対応する主語が持つｎ個の述語の重要度（スコア）の値の平均値で割ったものとして計算される。述語ｐｘの重要度（スコア）の値を、ｎ個の述語の重要度（スコア）の平均値で割ることにより、ｎ個の述語の中で、相対的に述語の重要度（スコア）の値が大きい述語ｐｘの統合スコアＩ（ｐｘ）が大きくなる。つまり、ｎ個の述語の中で、相対的に述語の重要度（スコア）の値が大きい述語ｐｘは、主語から見て主語が持つ他の述語よりも主語を判別するための情報として役に立ちやすい。主語から見た場合に相対的に重要度が高いからである。そこで、実施例では、主語から見た場合に、相対的に重要度が低い述語を削除すべき述語とする。
【００２９】
図３は、述語削減の考え方を説明する図（２）である。図３に示すように、主語ｓから述語ｐ１、ｐ２、ｐ３、ｐ４がそれぞれの目的語ｏ１、ｏ２，ｏ３、ｏ４に遷移しているとする。述語ｐ１の重要度（スコア）は、Ｈｏｐ１（ｐ１）であるとする。述語ｐ２の重要度（スコア）は、Ｈｏｐ２（ｐ２）であるとする。述語ｐ３の重要度（スコア）は、Ｈｏｐ３（ｐ３）であるとする。述語ｐ４の重要度（スコア）は、Ｈｏｐ４（ｐ４）であるとする。ここで、述語ｐ１の重要度（スコア）と、述語ｐ３の重要度（スコア）とが、他の述語ｐ２とｐ４より低いとする。すると、述語ｐ１と、述語ｐ３は、主語ｓを特定するうえで、相対的に重要度が低い。そこで、主語から見た場合の相対的に重要度が低い述語を削除するようにしたい。なお、かかる述語削減の考え方だけでノードが削除されても、図２で説明した述語削減の考え方と同様に、ノード（エンティティ）間が直接的および間接的にエッジで接続されなくなる場合があるので、エンティティリンキングの精度が落ちてしまうという課題を解決するには、不十分である。
【００３０】
図１に戻って、クラスタリング部１３は、目的語のエンティティを、当該目的語へ遷移する述語の入次数に応じてクラスタリングする。ここでいう入次数とは、遷移先（目的語）のノードに遷移する（入力する）エッジの次数のことをいう。
【００３１】
削減数割当部１４は、各クラスタに遷移する述語集合に対して、全体の述語削減数に応じた削減数を割り当てる。すなわち、削減数割当部１４は、クラスタごとに、クラスタに含まれる遷移先（目的語）のノードに遷移するエッジの集合に対して、エッジの削減数を割り当てる。
【００３２】
例えば、削減数割当部１４は、削減数を割り当てるクラスタから、述語の入次数が０または１のクラスタを除外する。述語の入字数が０または１のクラスタにエッジの削減数が割り当てられると、本来接続されているべきノード間のエッジが確実に削除されることとなり、ノード間が直接的にも間接的にもエッジで接続されなくなるからである。また、削減数割当部１４は、述語の入次数が２以上のクラスタに遷移する述語集合に対して、予め定められた全体の述語削減数に応じた削減数を割り当てる。一例として、まず、削減数割当部１４は、各クラスタに対して、割り当て数として「１」を割り当てる。そして、削減数割当部１４は、各クラスタに対して、割り当て数／クラスタに遷移する述語の数を計算する。そして、削減数割当部１４は、計算した結果が最も小さいクラスタに対して、割り当て数を１加算する。そして、削減数割当部１４は、全体の割り当て数が予め定められた全体の述語削減数になるまで、繰り返し、各クラスタに対する割り当ての計算を継続する。
【００３３】
削減対象選択部１５は、削減対象の述語を選択する。例えば、削減対象選択部１５は、クラスタごとのエッジの集合について、統合スコアの小さい順に、クラスタに割り当てられた削減数分のエッジを削減対象のエッジとして選択する。すなわち、削減対象選択部１５は、クラスタごとのエッジの集合について、述語の重要度の低いエッジから順番に、クラスタに割り当てられた削減数分選択する。そして、削減対象選択部１５は、ナレッジグラフ内の削減対象のエッジを削除する。
【００３４】
エンティティリンキング実行部１６は、エンティティリンキングを実行する。例えば、エンティティリンキング実行部１６は、入力文の中の単語と、新たに生成されたナレッジグラフのエンティティとを対応付ける。つまり、エンティティリンキング実行部１６は、削除されたエッジで接続されていた主語のノードと述語のノードを、削除されていないエッジで接続されたノードを介して接続し、入力文中の単語と、生成したナレッジグラフのノードとを対応付ける。
【００３５】
また、エンティティリンキング実行部１６は、入力文中の単語と、対応付けたエンティティとをユーザに提示する。
【００３６】
ここで、実施例に係るエンティティリンキングの一例を、図４〜図９を参照して説明する。なお、図４〜図９では、知識ベースとして「武蔵小杉」周辺の地域に関するナレッジグラフを用いて説明する。
【００３７】
［述語スコア計算の一例］
図４は、実施例に係る述語スコア計算の一例を示す図である。図４に示すように、述語スコア計算部１１は、ナレッジグラフの全ての述語（エッジ）ｐについて、述語ｐが目的語ｏｐへ遷移する場合の情報量Ｈｏｐ（ｐ）を計算する。例えば、述語ｐが「ｌｉｎｅ」であり、目的語ｏｐが「東急東横線」である場合に、述語ｐが目的語ｏｐへ遷移する場合の情報量Ｈｏｐ（ｐ）は、以下のように計算される。ナレッジグラフの中で、述語が「ｌｉｎｅ」である総数は、７個である。目的語である「東急東横線」へ遷移する述語「ｌｉｎｅ」は、２個である。述語ｐが「ｌｉｎｅ」であり、目的語ｏｐが「東急東横線」である場合の述語ｐが目的語ｏｐへ遷移する確率Ｐ（ｏｐ）は、２／７である。したがって、かかる場合の述語ｐが目的語ｏｐへ遷移する場合の情報量Ｈｏｐ（ｐ）は、式（１）により、１．８１と計算される。同様に、全ての述語ｐについて、述語ｐが目的語ｏｐへ遷移する場合の情報量Ｈｏｐ（ｐ）が、式（１）により、計算される。計算された情報量Ｈｏｐ（ｐ）は、それぞれ述語と対応付けて、「Ｈ」の横に記述されている。
【００３８】
［統合スコア計算の一例］
図５は、実施例に係る統合スコア計算の一例を示す図である。図５に示すように、統合スコア計算部１２は、ナレッジグラフの全ての述語（エッジ）ｐｘについて、主語ｓの出次数をｎ、主語ｓの目的語ｏｎに対応する述語ｐｎのスコアをＨｏｐｎ（ｐｎ）とし、ｓを主語とする述語ｐｘの統合スコアＩ（ｐｘ）を計算する。例えば、主語ｓが「武蔵小杉」であり、目的語ｏｘ（ｏ１）が「東急東横線」である場合に、ｓを主語とする述語ｐｘの統合スコアＩ（ｐｘ）は、以下のように計算される。主語ｓが「武蔵小杉」である場合の主語ｓの出次数ｎは、目的語「東急東横線」（ｏｘまたはｏ１）への遷移、目的語「新丸子」（ｏ２）への遷移、目的語「中原区」（ｏ３）への遷移、目的語「武蔵中原」（ｏ４）への遷移、目的語「南武線」（ｏ５）への遷移を示す「５」である。主語ｓが「武蔵小杉」である場合の主語ｓの目的語「東急東横線」（ｏｘまたはｏ１）に対応する述語「ｌｉｎｅ」（ｐｘまたはｐ１）の情報量（スコア）は、「１．８１」である。主語ｓが「武蔵小杉」である場合の主語ｓの目的語「新丸子」（ｏ２）に対応する述語「ｎｅｘｔ」（ｐ２）の情報量（スコア）は、「２．３２」である。主語ｓが「武蔵小杉」である場合の主語ｓの目的語「中原区」（ｏ３）に対応する述語「ｌｏｃａｔｅｄＩｎ」（ｐ３）の情報量（スコア）は、「０．５８」である。主語ｓが「武蔵小杉」である場合の主語ｓの目的語「武蔵中原」（ｏ４）に対応する述語「ｎｅｘｔ」（ｐ４）の情報量（スコア）は、「２．３２」である。主語ｓが「武蔵小杉」である場合の主語ｓの目的語「南武線」（ｏ５）に対応する述語「ｌｉｎｅ」（ｐ５）の情報量（スコア）は、「０．４９」である。したがって、かかる場合の述語ｐｘの統合スコアＩ（ｐｘ）は、式（２）により、１．２０と計算される。すなわち、述語ｐｘの統合スコアＩ（ｐｘ）は、述語ｐｘの情報量（スコア）の値を、主語ｓが持つｎ個の述語の情報量（スコア）の値の平均値で割った値と計算される。同様に、全ての述語ｐｘについて、統合スコアＩ（ｐｘ）が、式（２）により、計算される。計算された統合スコアＩ（ｐｘ）は、それぞれ述語と対応付けて、「Ｉ」の横に記述されている。
【００３９】
［クラスタリングの一例］
図６は、実施例に係るクラスタリングの一例を示す図である。図６に示すように、クラスタリング部１３は、目的語のエンティティを、当該目的語へ遷移する述語の入次数に応じてクラスタリングする。ここでは、目的語としての「南武線」は、当該目的語へ遷移する述語の入次数として「５」を示す。目的語としての「中原区」は、当該目的語へ遷移する述語の入次数として「４」を示す。目的語としての「高津区」、「武蔵中原」、「新丸子」、「東急東横線」は、当該目的語へ遷移する述語の入次数として「２」を示す。目的語としての「津田山」、「武蔵溝の口」、「武蔵新城」、「武蔵小杉」は、当該目的語へ遷移する述語の入次数として「１」を示す。目的語としての「等々力競技場」は、当該目的語へ遷移する述語の入次数として「０」を示す。したがって、入次数が「５」を示す目的語「南武線」が１つのクラスタ（Ａクラスタ）とされる。入次数が「４」を示す目的語「中原区」が１つのクラスタ（Ｂクラスタ）とされる。入次数が「２」を示す目的語「高津区」、「武蔵中原」、「新丸子」、「東急東横線」が１つのクラスタ（Ｃクラスタ）とされる。入次数が「１」を示す目的語「津田山」、「武蔵溝の口」、「武蔵新城」、「武蔵小杉」が１つのクラスタ（Ｄクラスタ）とされる。入次数が「０」を示す目的語「等々力競技場」が１つのクラスタ（Ｅクラスタ）とされる。
【００４０】
［削減数割当の一例］
図７Ａおよび図７Ｂは、実施例に係る削減数割当の一例を示す図である。図７Ａに示すように、全体の述語の削減数は、「１０」であるとする。クラスタＡに遷移する述語集合の数は「５」である。クラスタＢに遷移する述語集合の数は「４」である。クラスタＣに遷移する述語集合の数は「８」である。クラスタＤに遷移する述語集合の数は「４」である。クラスタＥに遷移する述語集合の数は「０」である。
【００４１】
このような状況の下、削減数割当部１４は、削減数を割り当てるクラスタＡ〜Ｅから、述語の入次数が「０」または「１」のクラスタを除外する。ここでは、入次数が「１」のＤクラスタが除外される。入次数が「０」のＥクラスタが除外される。
【００４２】
クラスタを除外後、まず、削減数割当部１４は、クラスタＡ〜Ｃに対して、割り当て数として「１」を割り当てる（ａ１）。残りの述語の削減数は、「７」となる。
【００４３】
そして、削減数割当部１４は、各クラスタに対して、割り当て数／クラスタに遷移する述語の数を計算し、計算した結果が最も小さいクラスタに対して、割り当て数を１加算する。ここでは、Ａクラスタが１／５、Ｂクラスタが１／４、Ｃクラスタが１／８であるので、最も小さいクラスタＣに対して、割り当て数が１加算される（ａ２）。残りの述語の削減数は、「６」となる。
【００４４】
同様に、削減数割当部１４は、各クラスタに対して、割り当て数／クラスタに遷移する述語の数を計算し、計算した結果が最も小さいクラスタに対して、割り当て数を１加算する。ここでは、Ａクラスタが１／５、Ｂクラスタが１／４、Ｃクラスタが２／８であるので、最も小さいクラスタＡに対して、割り当て数が１加算される（ａ３）。残りの述語の削減数は、「５」となる。
【００４５】
同様に、削減数割当部１４は、各クラスタに対して、割り当て数／クラスタに遷移する述語の数を計算し、計算した結果が最も小さいクラスタに対して、割り当て数を１加算する。ここでは、Ａクラスタが２／５、Ｂクラスタが１／４、Ｃクラスタが２／８であるので、最も小さいクラスタＢ，Ｃに対して、割り当て数が１加算される（ａ４）。残りの述語の削減数は、「３」となる。
【００４６】
同様に、削減数割当部１４は、各クラスタに対して、割り当て数／クラスタに遷移する述語の数を計算し、計算した結果が最も小さいクラスタに対して、割り当て数を１加算する。ここでは、Ａクラスタが２／５、Ｂクラスタが２／４、Ｃクラスタが３／８であるので、最も小さいクラスタＣに対して、割り当て数が１加算される（ａ５）。残りの述語の削減数は、「２」となる。
【００４７】
同様に、削減数割当部１４は、各クラスタに対して、割り当て数／クラスタに遷移する述語の数を計算し、計算した結果が最も小さいクラスタに対して、割り当て数を１加算する。ここでは、Ａクラスタが２／５、Ｂクラスタが２／４、Ｃクラスタが４／８であるので、最も小さいクラスタＡに対して、割り当て数が１加算される（ａ６）。残りの述語の削減数は、「１」となる。
【００４８】
同様に、削減数割当部１４は、各クラスタに対して、割り当て数／クラスタに遷移する述語の数を計算し、計算した結果が最も小さいクラスタに対して、割り当て数を１加算する。ここでは、Ａクラスタが３／５、Ｂクラスタが２／４、Ｃクラスタが４／８であるので、最も小さいクラスタＢ，Ｃのうち割り当て数が少ないクラスタに対して、割り当て数が１加算される（ａ７）。残りの述語の削減数は、「０」となる。
【００４９】
そして、削減数割当部１４は、残りの述語の削減数が「０」になったので、削減数の割り当てを終了する。この結果、Ａクラスタについて、割り当てられた削減数は「３」となる。Ｂクラスタについて、割り当てられた削減数は「３」となる。Ｃクラスタについて、割り当てられた削減数は「４」となる。
【００５０】
［削減対象選択の一例］
図８は、実施例に係る削減対象選択の一例を示す図である。図８に示すように、削減対象選択部１５は、クラスタに遷移する述語集合（エッジの集合）ごとに、統合スコアが小さい順に、割り当てられた削減数に応じて述語集合に属する述語を削除する。ここでは、Ａクラスタに割り当てられた削減数は「３」である。したがって、統合スコアが小さい順に、Ａクラスタに遷移する述語集合の中から、「武蔵小杉」から「南武線」への述語、「武蔵溝の口」から「南武線」への述語、「武蔵中原」から「南武線」への述語が削除される。Ｂクラスタに割り当てられた削減数は「３」である。したがって、統合スコアが小さい順に、Ｂクラスタに遷移する述語集合の中から、「武蔵小杉」から「中原区」への述語、「新丸子」から「中原区」への述語、「武蔵新城」から「中原区」への述語が削除される。Ｃクラスタに割り当てられた削減数は「４」である。したがって、統合スコアが小さい順に、Ｃクラスタに遷移する述語集合の中から、「等々力競技場」から「新丸子」への述語、「等々力競技場」から「武蔵中原」への述語、「武蔵溝の口」から「高津区」への述語、「東急東横線」から「武蔵小杉」への述語が削除される。
【００５１】
［削減した結果の一例］
図９は、実施例に係る削減した結果の一例を示す図である。図９に示すように、削減対象選択部１５は、削減対象の述語（エッジ）を削除したナレッジグラフを生成する。生成された新たなナレッジグラフが、図９に示されるグラフである。
【００５２】
［エンティティリンキング実行の一例］
図１０は、実施例に係るエンティティリンキング実行の一例を示す図である。図１０に示すように、入力文は、「南武線で中原駅に行った」であるとする。すると、エンティティリンキング実行部１６は、入力文の中の単語と、新たに生成したナレッジグラフのエンティティとを対応付ける。なお、エンティティリンキングの方法は、どのような方法であっても構わない。例えば、入力文の中の単語（メンション）「南武線」は、ナレッジグラフ（知識ベース）の「南武線」と完全一致するので、入力文の中の単語「南武線」とナレッジグラフの「南武線」とが対応付けられる。入力文の中の単語（メンション）「中原駅」のナレッジグラフ（知識ベース）の中の対応候補として「武蔵中原」と「中原区」とがある。かかる場合には、「南武線」へのパスが短い「武蔵中原」が選択される。すなわち、入力文の中の単語「中原駅」とナレッジグラフの「武蔵中原」とが対応付けられる。つまり、エンティティリンキング実行部１６は、例えば「武蔵中原」と「南武線」との間の削除されたエッジで接続されていた主語のノードと述語のノードを、削除されていない「武蔵新城」のノードを介して接続し、入力文中の単語と、生成したナレッジグラフのノードとを対応付ける。
【００５３】
［情報処理のフローチャート］
図１１は、実施例に係る情報処理のフローチャートの一例を示す図である。図１１に示すように、述語スコア計算部１１は、知識ベースの情報を取得する（ステップＳ１１）。述語スコア計算部１１は、知識ベースのすべての述語について、スコアＨを計算する（ステップＳ１２）。例えば、述語スコア計算部１１は、述語ｐが目的語ｏｐへ遷移する確率をＰ（ｏｐ）とすると、目的語ｏｐへ遷移する述語ｐのスコアＨｏｐ（ｐ）を、式（１）に基づいて計算する。
【００５４】
そして、統合スコア計算部１２は、知識べースのすべての述語について、（統合）スコアＩを計算する（ステップＳ１３）。例えば、統合スコア計算部１２は、主語ｓの出次数をｎ、主語ｓの目的語ｏｎに対応する述語ｐｎのスコアをＨｏｐｎ（ｐｎ）とし、ｓを主語とする述語ｐｘの統合スコアＩ（ｐｘ）を、式（２）に基づいて計算する。
【００５５】
そして、クラスタリング部１３は、知識ベースの目的語のエンティティを入次数によってクラスタリングする（ステップＳ１４）。
【００５６】
そして、削減数割当部１４は、各クラスタに遷移する述語集合に対して、予め定められた全体の述語削減数に応じた削減数を割り当てる（ステップＳ１５）。なお、かかる削減数割当処理のフローチャートは、後述する。
【００５７】
そして、削減対象選択部１５は、述語集合ごとに、（統合）スコアＩの小さい順に、割り当てられた削減数に応じて、述語集合に属する述語を削除し、新たな知識ベース（ナレッジグラフ）を生成する（ステップＳ１６）。そして、エンティティリンキング実行部１６は、入力文の中の単語と、新たに生成された知識ベース（ナレッジグラフ）のエンティティとを対応付けるエンティティリンキングを実行する（ステップＳ１７）。
【００５８】
［削減数割当処理のフローチャート］
図１２は、実施例に係る削減数割当処理のフローチャートの一例を示す図である。図１２に示すように、削減数割当部１４は、予め定められた全体の述語削減数Ｎを取得する（ステップＳ２１）。削減数割当部１４は、述語の入次数が２以上のクラスタについて、そのクラスタに遷移する述語の数Ｍを取得する（ステップＳ２２）。
【００５９】
そして、削減数割当部１４は、複数のクラスタのうち［割り当て数］／Ｍが最も小さいクラスタに対して削減数を１割り当てる（ステップＳ２３）。なお、削減数割当部１４は、すべての値が同じである場合には、入次数が最も大きいクラスタに１割り当てる。また、削減数割当部１４は、複数の値が同じである場合には、複数のクラスタに１割り当てる。
【００６０】
そして、削減数割当部１４は、全体の述語削減数Ｎから割り当てた削減数分を減算する（ステップＳ２４）。
【００６１】
そして、削減数割当部１４は、全体の述語削減数Ｎが０より大きいか否かを判定する（ステップＳ２５）。全体の述語削減数Ｎが０より大きいと判定した場合には（ステップＳ２５；Ｙｅｓ）、削減数割当部１４は、さらに削減数を割り当てるために、ステップＳ２３に移行する。
【００６２】
一方、全体の述語削減数Ｎが０より大きくないと判定した場合には（ステップＳ２５；Ｎｏ）、削減数割当部１４は、削減数割当処理を終了する。
【００６３】
［クラスタリングしないで削減した場合の参考例］
なお、クラスタリングしないで削減した場合の参考例を、図１３および図１４を参照して説明する。図１３は、クラスタリングしないでスコア順に削減した結果の参考例を示す図である。図１３に示すように、統合スコアＩの低いエッジから順番に、予め定められた全体の述語削減数分のエッジが、削減対象のエッジとして選択される。そして、ナレッジグラフ内の削減対象のエッジが削除される。生成された新たなナレッジグラフが、図１３に示されるグラフである。ここでは、「南武線」に接続するエッジが失われている。「中原区」に接続するエッジが失われている。
【００６４】
図１４は、クラスタリングしないでスコア順に削減した場合のエンティティリンキング実行の参考例を示す図である。図１４に示すように、入力文は、「南武線で中原駅に行った」であるとする。すると、入力文の中の単語と、新たに生成したナレッジグラフのエンティティとを対応付けるエンティティリンキングが実行される。ここでは、入力文の中の単語（メンション）「南武線」は、ナレッジグラフ（知識ベース）の「南武線」と完全一致するので、入力文の中の単語「南武線」とナレッジグラフの「南武線」とが対応付けられる。入力文の中の単語（メンション）「中原駅」の、ナレッジグラフ（知識ベース）の中の対応候補として「武蔵中原」と「中原区」とがある。ところが、かかる場合には、「南武線」と「中原区」にそれぞれ接続するエッジが失われているため、入力文の「中原駅」が「武蔵中原」と対応付けられるのか、「中原区」と対応付けられるのかが不明である。すなわち、エンティティリンキングのために重要なエッジが失われているため、エンティティリンキングの精度が下がる。
【００６５】
［実施例の効果］
上記実施例によれば、情報処理装置１は、ナレッジグラフ内の遷移元の第１ノードに接続されるエッジの数と、遷移先の第２ノードに接続されるエッジの数とに基づいて、ナレッジグラフのうち予め設定された次数の第２ノードと接続されたエッジから削除すべきエッジを特定する。情報処理装置１は、該特定したエッジを削除したナレッジグラフを生成する。情報処理装置１は、削除されたエッジで接続されていた第１ノードおよび第２ノードを、削除されていないエッジで接続された第３ノードを介して接続し、テキスト中の単語と、当該単語と対応付けたエンティティをユーザに提示する。かかる構成によれば、情報処理装置１は、ナレッジグラフからエッジを削除することでナレッジグラフの情報量を削減するが、エンティティリンキングの精度を維持することが可能である。
【００６６】
また、上記実施例によれば、情報処理装置１は、遷移先の第２ノードに遷移するエッジの次数に応じて第２ノードをクラスタリングする。情報処理装置１は、該クラスタリングされた各クラスタに遷移するエッジの集合に対して、予め定められた全体のエッジの削減数に応じた削減数を割り当てる。そして、情報処理装置１は、エッジの集合ごとに、割り当てられた削減数分の削除すべきエッジを特定する。かかる構成によれば、情報処理装置１は、第２ノードへのエッジの入次数を用いて第２ノードをクラスタリングし、各クラスタに対してエッジの削減数を割り当てることで、スコアの小さい順に削除すべきエッジを特定する場合と比べて、エンティティリンキングの精度を維持しながら、ナレッジグラフの情報量を削減することが可能となる。
【００６７】
また、上記実施例によれば、情報処理装置１は、さらに、エッジの集合の中から、重要度の小さい順に、割り当てられた削減数分のエッジを削減すべきエッジとして特定する。かかる構成によれば、情報処理装置１は、ナレッジグラフ全体の中からスコアの小さい順に削除すべきエッジを特定する場合と比べて、エンティティリンキングの精度を維持しながら、ナレッジグラフの情報量を削減することが可能となる。
【００６８】
［その他］
なお、図示した情報処理装置１の各構成要素は、必ずしも物理的に図示の如く構成されていることを要しない。すなわち、情報処理装置１の分散・統合の具体的態様は図示のものに限られず、その全部または一部を、各種の負荷や使用状況などに応じて、任意の単位で機能的または物理的に分散・統合して構成することができる。例えば、削減数割当部１４を、削減数を割り当てるクラスタを除外する除外部と、除外したクラスタ以外のクラスタに削減数を割り当てる割当部とに分離しても良い。また、述語スコア計算部１１と、統合スコア計算部１２とを統合してスコア計算部にしても良い。また、知識ベース２１、述語スコア記憶部２２、統合スコア記憶部２３等を記憶する記憶部を情報処理装置１の外部装置としてネットワーク経由で接続するようにしても良い。
【００６９】
また、上記実施例で説明した各種の処理は、予め用意されたプログラムをパーソナルコンピュータやワークステーションなどのコンピュータで実行することによって実現することができる。そこで、以下では、図１に示した情報処理装置１と同様の機能を実現するエンティティリンキングプログラムを実行するコンピュータの一例を説明する。図１５は、エンティティリンキングプログラムを実行するコンピュータの一例を示す図である。
【００７０】
図１５に示すように、コンピュータ２００は、各種演算処理を実行するＣＰＵ２０３と、ユーザからのデータの入力を受け付ける入力装置２１５と、表示装置２０９を制御する表示制御部２０７とを有する。また、コンピュータ２００は、記憶媒体からプログラムなどを読取るドライブ装置２１３と、ネットワークを介して他のコンピュータとの間でデータの授受を行う通信制御部２１７とを有する。また、コンピュータ２００は、各種情報を一時記憶するメモリ２０１と、ＨＤＤ（Hard  Disk  Drive）２０５を有する。そして、メモリ２０１、ＣＰＵ２０３、ＨＤＤ２０５、表示制御部２０７、ドライブ装置２１３、入力装置２１５、通信制御部２１７は、バス２１９で接続されている。
【００７１】
ドライブ装置２１３は、例えばリムーバブルディスク２１０用の装置である。ＨＤＤ２０５は、エンティティリンキングプログラム２０５ａおよびエンティティリンキング処理関連情報２０５ｂを記憶する。
【００７２】
ＣＰＵ２０３は、エンティティリンキングプログラム２０５ａを読み出して、メモリ２０１に展開し、プロセスとして実行する。かかるプロセスは、情報処理装置１の各機能部に対応する。エンティティリンキング処理関連情報２０５ｂは、知識ベース２１、述語スコア記憶部２２、統合スコア記憶部２３およびクラスタ情報記憶部２４に対応する。そして、例えばリムーバブルディスク２１０が、エンティティリンキングプログラム２０５ａなどの各情報を記憶する。
【００７３】
なお、エンティティリンキングプログラム２０５ａについては、必ずしも最初からＨＤＤ２０５に記憶させておかなくても良い。例えば、コンピュータ２００に挿入されるフレキシブルディスク（ＦＤ）、ＣＤ−ＲＯＭ（Compact  Disk  Read  Only  Memory）、ＤＶＤ（Digital  Versatile  Disk）、光磁気ディスク、ＩＣ（Integrated  Circuit）カードなどの「可搬用の物理媒体」に当該プログラムを記憶させておく。そして、コンピュータ２００がこれらからエンティティリンキングプログラム２０５ａを読み出して実行するようにしても良い。
【符号の説明】
【００７４】
１  情報処理装置
１１  述語スコア計算部
１２  統合スコア計算部
１３  クラスタリング部
１４  削減数割当部
１５  削減対象選択部
１６  エンティティリンキング実行部
２１  知識ベース
２２  述語スコア記憶部
２３  統合スコア記憶部
２４  クラスタ情報記憶部
【図１】
2020187419.tif 000005
【図２】
2020187419.tif 000006
【図３】
2020187419.tif 000007
【図４】
2020187419.tif 000008
【図５】
2020187419.tif 000009
【図６】
2020187419.tif 000010
【図７Ａ】
2020187419.tif 000011
【図７Ｂ】
2020187419.tif 000012
【図８】
2020187419.tif 000013
【図９】
2020187419.tif 000014
【図１０】
2020187419.tif 000015
【図１１】
2020187419.tif 000016
【図１２】
2020187419.tif 000017
【図１３】
2020187419.tif 000018
【図１４】
2020187419.tif 000019
【図１５】
2020187419.tif 000020
【図１６】
2020187419.tif 000021
【図１７】
2020187419.tif 000022