(57)【要約】【課題】ノイズを含むデータであっても各ノードの対応付けを見つけることができる対応付け装置、対応付け方法及びプログラムを提供する。【解決手段】複数のネットワークのデータが入力されたときに、当該複数のネットワークのデータの各ノードの対応付けを見つける対応付け装置は、各ノードとクラスタとの関係を推定するときに、前記入力されたデータ、該当ノード以外のクラスタ割当集合、該当ノード以外の関連割当集合、及びパラメータに基づき、該当ノードがクラスタに関連するかどうかを推定するクラスタ関連推定部と、前記パラメータがどのくらい前記入力されたデータをもっともらしく説明できているかを示す尤度が高くなるようにパラメータを推定するパラメータ推定部と、前記クラスタ関連推定部における推定を、終了条件が満たされるまで繰り返す終了条件判定部とを有する。【選択図】図１
2018067189.tif 000002
【特許請求の範囲】
【請求項１】
複数のネットワークのデータが入力されたときに、当該複数のネットワークのデータの各ノードの対応付けを見つける対応付け装置であって、
各ノードとクラスタとの関係を推定するときに、前記入力されたデータ、該当ノード以外のクラスタ割当集合、該当ノード以外の関連割当集合、及びパラメータに基づき、該当ノードがクラスタに関連するかどうかを推定するクラスタ関連推定部と、
前記パラメータがどのくらい前記入力されたデータをもっともらしく説明できているかを示す尤度が高くなるようにパラメータを推定するパラメータ推定部と、
前記クラスタ関連推定部における推定を、終了条件が満たされるまで繰り返す終了条件判定部と、
を有する対応付け装置。
【請求項２】
前記クラスタ関連推定部は、該当ノードがクラスタに関連しない場合、ノードによって異なる確率でノード間のリンクがはられると仮定し、該当ノードがクラスタに関連するかどうかを推定する、請求項１に記載の対応付け装置。
【請求項３】
前記パラメータ推定部は、前記パラメータに対してガンマ事前分布を仮定して事後確率からサンプリングすることで、前記パラメータを推定する、請求項１又は２に記載の対応付け装置。
【請求項４】
複数のネットワークのデータが入力されたときに、当該複数のネットワークのデータの各ノードの対応付けを見つける対応付け装置における対応付け方法であって、
各ノードとクラスタとの関係を推定するときに、前記入力されたデータ、該当ノード以外のクラスタ割当集合、該当ノード以外の関連割当集合、及びパラメータに基づき、該当ノードがクラスタに関連するかどうかを推定するクラスタ関連推定ステップと、
前記パラメータがどのくらい前記入力されたデータをもっともらしく説明できているかを示す尤度が高くなるようにパラメータを推定するパラメータ推定ステップと、
前記クラスタ関連推定ステップにおける推定を、終了条件が満たされるまで繰り返す終了条件判定ステップと、
を有する対応付け方法。
【請求項５】
前記クラスタ関連推定ステップにおいて、該当ノードがクラスタに関連しない場合、ノードによって異なる確率でノード間のリンクがはられると仮定し、該当ノードがクラスタに関連するかどうかを推定する、請求項４に記載の対応付け方法。
【請求項６】
前記パラメータ推定ステップにおいて、前記パラメータに対してガンマ事前分布を仮定して事後確率からサンプリングすることで、前記パラメータを推定する、請求項４又は５に記載の対応付け方法。
【請求項７】
コンピュータを、請求項１乃至３のいずれか１項に記載の対応付け装置の各部として機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数のネットワークのデータが与えられたときに、与えられたデータの各ノードの対応付けを見つける対応付け装置、対応付け方法及びプログラムに関する。
【背景技術】
【０００２】
異なるネットワークのノードを対応付ける技術は様々な場面で必要となる。例えば、異なるデータベースのIDを対応付けたり、語彙を対応付けることで辞書を作成したり、画像と説明文の対応を見つけたりする際に、ノードの対応付けが必要となる。
【０００３】
これまでにノードの対応付け手法は数多く提案されている（例えば、非特許文献１及び２参照）。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】Yuya Yoshikawa, Tomoharu Iwata, Hiroshi Sawada, Takeshi Yamada,"Cross-Domain Matching for Bag-of-Words Data via Kernel Embeddings of Latent Distributions,"Advances in Neural Information Processing Systems, 2015
【非特許文献２】Tomoharu Iwata, James Robert Lloyd, Zoubin Ghahramani,"Unsupervised Many-to-Many Object Matching for Relational Data,"IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol.38, No.3, 607-619, 2016
【発明の概要】
【発明が解決しようとする課題】
【０００５】
非特許文献１の対応付け手法は、異なるネットワークのノードの距離が計測できることや、一部のノード間の対応が既知であることを仮定しており、距離が計測できず、かつ、対応が全く得られない場合に、利用できないという問題がある。
【０００６】
非特許文献２の対応付け手法は、距離が計測できず、かつ、対応が全く得られない場合にも適用可能な、教師なし対応付け手法である。しかし、データにノイズが含まれる場合に精度が低くなるという問題点がある。
【０００７】
本発明は、各ノードがクラスタに関連するかどうかを推定しながら各ノードをクラスタに割り当てることにより、ノイズを含むデータであっても各ノードの対応付けを見つけることができる対応付け装置、対応付け方法及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００８】
本発明の一形態に係る対応付け装置は、
複数のネットワークのデータが入力されたときに、当該複数のネットワークのデータの各ノードの対応付けを見つける対応付け装置であって、
各ノードとクラスタとの関係を推定するときに、前記入力されたデータ、該当ノード以外のクラスタ割当集合、該当ノード以外の関連割当集合、及びパラメータに基づき、該当ノードがクラスタに関連するかどうかを推定するクラスタ関連推定部と、
前記パラメータがどのくらい前記入力されたデータをもっともらしく説明できているかを示す尤度が高くなるようにパラメータを推定するパラメータ推定部と、
前記クラスタ関連推定部における推定を、終了条件が満たされるまで繰り返す終了条件判定部と、
を有することを特徴とする。
【０００９】
また、本発明の一形態に係る対応付け方法は、
複数のネットワークのデータが入力されたときに、当該複数のネットワークのデータの各ノードの対応付けを見つける対応付け装置における対応付け方法であって、
各ノードとクラスタとの関係を推定するときに、前記入力されたデータ、該当ノード以外のクラスタ割当集合、該当ノード以外の関連割当集合、及びパラメータに基づき、該当ノードがクラスタに関連するかどうかを推定するクラスタ関連推定ステップと、
前記パラメータがどのくらい前記入力されたデータをもっともらしく説明できているかを示す尤度が高くなるようにパラメータを推定するパラメータ推定ステップと、
前記クラスタ関連推定ステップにおける推定を、終了条件が満たされるまで繰り返す終了条件判定ステップと、
を有する対応付け方法。
【００１０】
また、本発明の一形態に係るプログラムは、
コンピュータを、上記の対応付け装置の各部として機能させることを特徴とする。
【発明の効果】
【００１１】
本発明によれば、ノイズを含むデータであっても各ノードの対応付けを見つけることが可能になる。
【図面の簡単な説明】
【００１２】
【図１】本発明の実施例に係る対応付け装置の機能ブロック図
【図２】本発明の実施例に係る対応付け装置における処理を示すフローチャート
【図３】本発明の実施例によるネットワークの生成過程を示す図
【図４】クラスタ割当及び関連割当を行った結果を示す図
【図５】本発明の実施例によるシミュレーション結果を示す図
【図６】本発明の実施例による単語のクラスタ割当と関連割当結果を示す図
【図７】本発明の実施例に係る対応付け装置のハードウェア構成例を示す図
【発明を実施するための形態】
【００１３】
以下、図面を参照して本発明の実施例について説明する。
【００１４】
本発明の実施例では、複数のネットワークのデータが入力されたときに、当該複数のネットワークのデータの各ノードの対応付けを見つける対応付け装置について説明する。
【００１５】
入力データとしてD個のネットワークデータが与えられたとする。ネットワーク表現されていないデータの場合、事例間の類似度などをもとにリンクをはることにより、ネットワークデータに変換することで、本発明の実施例が適用可能になる。このように、入力データはノード及びリンクの有無によって表現される。簡単のため、以下の実施例ではタイプ１のノードとタイプ２のノードで構成される重みのない二部グラフについて説明を行うが、重み付きのネットワークや、二部グラフではない一般的なグラフ、リンクに複数のタイプがあるネットワーク（リンクが友人関係、家族関係、仕事関係等の属性があるネットワーク）など、他のネットワークでも適用可能である。
【００１６】
入力データは
【００１７】
【数１】
2018067189.tif 000003
と表現する。ここで
【００１８】
【数２】
2018067189.tif 000004
はd番目のネットワーク、xdnm∈{0,1}はタイプ１のn番目のノードとタイプ２のm番目のノードの間にリンクの有無を表す変数であり、リンクがある場合xdnm=1、リンクがない場合xdnm=0である。また、Dはネットワーク数であり、Ndtはネットワークdのタイプtのノード数である。
【００１９】
また、以下の説明において、Ktはタイプtのクラスタ数であり、zdtnはネットワークdのタイプtのn番目のノードのクラスタ割当を表し、zdtn∈{0,1,…,∞}である。rdtnはネットワークdのタイプtのn番目のノードの関連割当であり、関連する場合rdtn=1、関連しない場合rdtn=0である。
【００２０】
例えば、後述の例にて説明するWikipediaは、１つ文章に含まれる単語がリンクによって他の文章に結びつけられている。Wikipediaの例では、１つの文章を構成するノードをタイプ１のノードとし、他の文章を構成するノードをタイプ２のノードとして、本発明の実施例に係る対応付け装置は、タイプ１及びタイプ２の各ノードがクラスタに関連するかどうか、また、どのクラスタに割り当てられるかを推定する。更に、異なる言語のWikipediaを異なるネットワークとして扱うことにより、各ノードを複数ネットワークに共通するクラスタに割り当てる。
【００２１】
図１は、本発明の実施例に係る対応付け装置１００の機能ブロック図である。対応付け装置１００は、クラスタ関連推定部１１０と、パラメータ推定部１２０と、終了条件判定部１３０とを有する。
【００２２】
図２を参照して、図１の対応付け装置１００における処理について説明する。
【００２３】
ステップＳ１０１において、クラスタ関連推定部１１０は、入力データを受け取り、ステップＳ１０２において、クラスタ関連推定部１１０は、各ノードがクラスタに関連するかどうかを推定する。具体的には、クラスタ関連推定部１１０は、各ネットワークの各タイプの各ノードがどのクラスタに割り当てられるか、および、関連があると割り当てるか、を表す割当度を計算する。関連があると割り当てる場合には、ノードはいずれかのクラスタに割り当てられ、関連がないと割り当てる場合には、ノードはクラスタに割り当てられない。ノードとクラスタとの関係を示す割当度は、入力データ、該当ノード以外のクラスタ割当集合、該当ノード以外の関連割当集合、及びパラメータを考慮したものである。そして、クラスタ関連推定部１１０は、割当度に基づいて、クラスタ割当（各ノードをクラスタに割り当てること）と関連割当（各ノードがクラスタに関連するかどうかを割り当てること）を繰り返す。
【００２４】
ここで、クラスタ関連推定部１１０は、クラスタと関連がどのくらい入力データをもっともらしく説明できているかを表す尤度が高くなるように、クラスタ割当と関連割当を繰り返す。同じようなリンク構造を持っている関連するノードが同じクラスタに割り当てられる場合、尤度は高くなる。また、ランダムにリンクがはられる場合、関連がないと割り当てると尤度が高くなり、リンクがクラスタ構造に従ってはられている場合、関連があると割り当てると尤度が高くなる。
【００２５】
図３は、本発明の実施例によるネットワークデータの生成過程を示す図である。リンク確率を用いることで、ノード間のリンクがはられる。関連がない場合、ノードによらず一定の確率でノード間のリンクがはられると仮定した場合で以下の説明を進めるが、ノードによって異なる確率でノード間のリンクがはられると仮定してもよい。なお、本発明の実施例では、ネットワークデータは与えられるため、逆問題を解いてネットワークデータからリンク確率等を推定することができる。
【００２６】
ステップＳ１０３において、パラメータ推定部１２０は、クラスタ関連推定部１１０において用いたパラメータがどのくらい入力データをもっともらしく説明できているかを表す尤度が高くなるようにパラメータを推定する。
【００２７】
ステップＳ１０４において、終了条件判定部１３０は、クラスタ関連推定部１１０での処理と、パラメータ推定部１２０での処理を終了条件が満たされるまで繰り返す。終了条件としては、尤度が収束した、繰り返し数が一定数をこえた、クラスタや関連、パラメータの変化量があるしきい値以下であった、などが用いられる。なお、クラスタ関連推定部１１０は、割当度に従ってクラスタ割当と関連割当を決めるため、終了条件判定部１３０は、クラスタ関連推定部１１０のみの処理を繰り返すことで求められた推定結果に対して、終了条件が満たされているかを判定してもよい。すなわち、パラメータ推定部１２０におけるパラメータの更新が行われずに、クラスタ関連推定部１１０の処理を繰り返すことで求められた別のクラスタ割当と関連割当に対して、終了条件が満たされているかを判定してもよい。
【００２８】
ステップＳ１０５において、クラスタ関連推定部１１０は、終了条件が満たされたときの推定結果であるクラスタ割当と関連割当を出力する。図４は、クラスタ関連推定部１１０において複数のネットワークのノードに対してクラスタ割当と関連割当を行った結果を示している。最後に、関連するノードのうち、同じクラスタに割り当てられたノードが対応するノードと判断する。
【００２９】
なお、尤度の代わりに、事後確率など同等の性質を持つ値を用いることも可能である。また、以下ではマルコフ連鎖モンテカルロ法に基づいて潜在ベクトルを割り当てる場合について記述するが、最尤推定法や変分ベイズ法などを用いることも可能である。
【００３０】
次に、クラスタ関連推定部１１０について詳細に説明する。
【００３１】
図１に示すように、クラスタ関連推定部１１０は、初期化部１１１と、割当部１１２とを備えている。
【００３２】
まず、初期化部１１１により、各ノードにランダムにクラスタ、関連を割り当てる。
【００３３】
次に、割当部１１２において、まず、各ネットワークの各タイプの各ノードがどのクラスタに割り当てられるか、および、関連があると割り当てるか、を表す割当度を計算する。割当度は、入力として、ネットワークデータ、該当ノード以外のクラスタ割当集合と関連割当集合、パラメータ、をとり、これらの値を考慮したものである必要がある。ここではクラスタの割当は無限混合モデル（Charles Kemp, Joshua Tenenbaum, Thomas Griffiths, Takeshi Yamada, Naonori Ueda,"Learning Systems of Concepts with an Infinite Relational Model,"AAAI, 2006）をもとに行っているが、ネットワークのリンク構造に基づいてクラスタリングを行う手法であれば、他のクラスタリング手法を用いてもよい。
【００３４】
クラスタ割当集合を
【００３５】
【数３】
2018067189.tif 000005
とし、関連割当集合を
【００３６】
【数４】
2018067189.tif 000006
とする。例えば、ネットワークdのタイプtのn番目のクラスタ割当zdtnと関連割当rdtnは、i=(d,t,n)としたとき、割当度は下式で計算できる。
【００３７】
【数５】
2018067189.tif 000007
ここで
【００３８】
【数６】
2018067189.tif 000008
はノードiを除いたときの集合や値を表し、
【００３９】
【数７】
2018067189.tif 000009
はノードiに関するリンクの集合、
【００４０】
【数８】
2018067189.tif 000010
である。
【００４１】
第一因子は
【００４２】
【数９】
2018067189.tif 000011
で計算できる。ここで
【００４３】
【数１０】
2018067189.tif 000012
は関連割当rのタイプtのノード数、
【００４４】
【数１１】
2018067189.tif 000013
は関連すると割り当てられたクラスタkに割り当てられたタイプtのノード数を表す。
【００４５】
関連しない場合の第二因子は
【００４６】
【数１２】
2018067189.tif 000014
で計算できる。ここで
【００４７】
【数１３】
2018067189.tif 000015
は関連しないノードのリンク数、
【００４８】
【数１４】
2018067189.tif 000016
は関連しないノードの非リンク数、+i0はri=0とした場合の
【００４９】
【数１５】
2018067189.tif 000017
に関する統計量を表す。
【００５０】
関連する場合の第二因子は
【００５１】
【数１６】
2018067189.tif 000018
で計算できる。ここで
【００５２】
【数１７】
2018067189.tif 000019
はクラスタkとlに割り当てられた関連するノードの間のリンク数、
【００５３】
【数１８】
2018067189.tif 000020
はクラスタkとlに割り当てられた関連するノードの間の非リンク数、+ikはri=1とzi=kとした場合の
【００５４】
【数１９】
2018067189.tif 000021
に関する統計量を表す。
【００５５】
次に、パラメータ推定部１２０について詳細に説明する。
【００５６】
パラメータ推定部１２０は、パラメータαt,a,b,c,d,e,fがどのくらい入力データをもっともらしく説明できているかを表す尤度が高くなるようにパラメータを推定する。例えば、パラメータに対してガンマ事前分布を仮定して事後確率からサンプリングすることにより尤度が高くなるように、パラメータを推定できる。
【００５７】
＜本発明の実施例の評価＞
本発明の実施例を評価するため、Wikipediaの英語、ドイツ語、イタリア語、日本語の５カテゴリ（ノーベル物理学賞、ノーベル化学賞、アメリカのバスケットボール選手、アメリカの作曲家、イングランドのサッカー選手）の文書を用いて実験を行った。各言語ペアで各カテゴリから50文書をサンプリングし２つの文書単語ネットワークを作成した。ここでストップワードを除去し、頻出する1000語彙を用いた。１つの文書単語ネットワークのサイズは(150×1000)である。
【００５８】
比較手法として、ReMatch（非特許参考文献２）とIRM+KSを用いた。IRM+KSは無限関係モデル（Charles Kemp, Joshua Tenenbaum, Thomas Griffiths, Takeshi Yamada, Naonori Ueda,"Learning Systems of Concepts with an Infinite Relational Model,"AAAI, 2006）を用いてクラスタリングした後に教師なし対応付け手法であるカーネル並び替え法（Nemanja Djuric, Mihajlo Grbovic, Slobodan Vucetic,"Convex Kernelized Sorting,"AAAI, 2012）を用いて、クラスタの対応を見つける手法である。評価尺度としてはMatching Adjusted Rand Index (MARI)を用いた。
MARIは正しいクラスタ対応付ができるほど高い値をとる。図５にその結果である平均MARIとその標準誤差を示す。太字は最もよい手法に比べてt検定により有意差がなかったことを示す。図５から、本発明の実施例が比較手法に比べ高い性能を示しており、その有効性が確認できる。
【００５９】
図６は、は英語(EN)とドイツ語(DE)のデータでのクラスタ割当および関連割当結果を示す。２行ずつで１つのクラスタに対応し、そのなかの上の行が英語の単語であり、下の行がドイツ語の単語である。一番下の２行は関連しないと割り当てられた単語である。例えば、一番上のクラスタには音楽に関連する単語がクラスタリングされており、２番目のクラスタにはバスケットボールに関連する単語がクラスタリングされている。このように、言語をまたいで関連する単語がクラスタリングされ、また、トピックに関係しない単語が関連なしと判断されている。
【００６０】
＜ハードウェア構成例＞
図７に、本発明の実施例に係る対応付け装置１００のハードウェア構成例を示す。対応付け装置１００は、CPU（Central Processing Unit）１５１等のプロセッサ、RAM（Random Access Memory）やROM（Read Only Memory）等のメモリ装置１５２、ハードディスク等の記憶装置１５３等から構成されたコンピュータでもよい。例えば、対応付け装置１００の機能及び処理は、記憶装置１５３又はメモリ装置１５２に格納されているデータやプログラムをCPU１５１が実行することによって実現される。また、対応付け装置１００に必要な情報は、入出力インタフェース装置１５４から入力され、対応付け装置１００において求められた結果は、入出力インタフェース装置１５４から出力されてもよい。
【００６１】
＜補足＞
説明の便宜上、本発明の実施例に係る対応付け装置は機能的なブロック図を用いて説明しているが、本発明の実施例に係る対応付け装置は、ハードウェア、ソフトウェア又はそれらの組み合わせで実現されてもよい。例えば、本発明の実施例は、コンピュータに対して本発明の実施例に係る対応付け装置の機能を実現させるプログラム、コンピュータに対して本発明の実施例に係る方法の各手順を実行させるプログラム等により、実現されてもよい。また、各機能部が必要に応じて組み合わせて使用されてもよい。また、本発明の実施例に係る方法は、実施例に示す順序と異なる順序で実施されてもよい。
【００６２】
以上、ノイズを含むデータであっても各ノードの対応付けを見つけることができる手法について説明したが、本発明は、上記の実施例に限定されることなく、特許請求の範囲内において、種々の変更・応用が可能である。
【符号の説明】
【００６３】
１００  対応付け装置
１１０  クラスタ関連推定部
１１１  初期化部
１１２  割当部
１２０  パラメータ推定部
１３０  終了条件判定部
１５１  ＣＰＵ
１５２  メモリ装置
１５３  記憶装置
１５４  入出力インタフェース装置
【図１】
2018067189.tif 000022
【図２】
2018067189.tif 000023
【図３】
2018067189.tif 000024
【図４】
2018067189.tif 000025
【図５】
2018067189.tif 000026
【図６】
2018067189.tif 000027
【図７】
2018067189.tif 000028