JP6625507B2

JP6625507B2 - 対応付け装置、対応付け方法及びプログラム

Info

Publication number: JP6625507B2
Application number: JP2016206082A
Authority: JP
Inventors: 具治岩田
Original assignee: Nippon Telegraph and Telephone Corp; NTT Inc USA
Current assignee: NTT Inc; NTT Inc USA
Priority date: 2016-10-20
Filing date: 2016-10-20
Publication date: 2019-12-25
Anticipated expiration: 2036-10-20
Also published as: JP2018067189A

Description

本発明は、複数のネットワークのデータが与えられたときに、与えられたデータの各ノードの対応付けを見つける対応付け装置、対応付け方法及びプログラムに関する。

異なるネットワークのノードを対応付ける技術は様々な場面で必要となる。例えば、異なるデータベースの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個のネットワークデータが与えられたとする。ネットワーク表現されていないデータの場合、事例間の類似度などをもとにリンクをはることにより、ネットワークデータに変換することで、本発明の実施例が適用可能になる。このように、入力データはノード及びリンクの有無によって表現される。簡単のため、以下の実施例ではタイプ１のノードとタイプ２のノードで構成される重みのない二部グラフについて説明を行うが、重み付きのネットワークや、二部グラフではない一般的なグラフ、リンクに複数のタイプがあるネットワーク（リンクが友人関係、家族関係、仕事関係等の属性があるネットワーク）など、他のネットワークでも適用可能である。

入力データは

と表現する。ここで

はd番目のネットワーク、x_dnm∈{0,1}はタイプ１のn番目のノードとタイプ２のm番目のノードの間にリンクの有無を表す変数であり、リンクがある場合x_dnm=1、リンクがない場合x_dnm=0である。また、Dはネットワーク数であり、N_dtはネットワークdのタイプtのノード数である。

また、以下の説明において、K_tはタイプtのクラスタ数であり、z_dtnはネットワークdのタイプtのn番目のノードのクラスタ割当を表し、z_dtn∈{0,1,…,∞}である。r_dtnはネットワークdのタイプtのn番目のノードの関連割当であり、関連する場合r_dtn=1、関連しない場合r_dtn=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）をもとに行っているが、ネットワークのリンク構造に基づいてクラスタリングを行う手法であれば、他のクラスタリング手法を用いてもよい。

クラスタ割当集合を

とし、関連割当集合を

とする。例えば、ネットワークdのタイプtのn番目のクラスタ割当z_dtnと関連割当r_dtnは、i=(d,t,n)としたとき、割当度は下式で計算できる。

ここで

はノードiを除いたときの集合や値を表し、

はノードiに関するリンクの集合、

である。

第一因子は

で計算できる。ここで

は関連割当rのタイプtのノード数、

は関連すると割り当てられたクラスタkに割り当てられたタイプtのノード数を表す。

関連する場合の第二因子は

で計算できる。ここで

はクラスタkとlに割り当てられた関連するノードの間のリンク数、

はクラスタkとlに割り当てられた関連するノードの間の非リンク数、+ikはr_i=1とz_i=kとした場合の

に関する統計量を表す。

次に、パラメータ推定部１２０について詳細に説明する。

パラメータ推定部１２０は、パラメータα_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１５１が実行することによって実現される。また、対応付け装置１００に必要な情報は、入出力インタフェース装置１５４から入力され、対応付け装置１００において求められた結果は、入出力インタフェース装置１５４から出力されてもよい。

＜補足＞
説明の便宜上、本発明の実施例に係る対応付け装置は機能的なブロック図を用いて説明しているが、本発明の実施例に係る対応付け装置は、ハードウェア、ソフトウェア又はそれらの組み合わせで実現されてもよい。例えば、本発明の実施例は、コンピュータに対して本発明の実施例に係る対応付け装置の機能を実現させるプログラム、コンピュータに対して本発明の実施例に係る方法の各手順を実行させるプログラム等により、実現されてもよい。また、各機能部が必要に応じて組み合わせて使用されてもよい。また、本発明の実施例に係る方法は、実施例に示す順序と異なる順序で実施されてもよい。

以上、ノイズを含むデータであっても各ノードの対応付けを見つけることができる手法について説明したが、本発明は、上記の実施例に限定されることなく、特許請求の範囲内において、種々の変更・応用が可能である。

１００対応付け装置
１１０クラスタ関連推定部
１１１初期化部
１１２割当部
１２０パラメータ推定部
１３０終了条件判定部
１５１ＣＰＵ
１５２メモリ装置
１５３記憶装置
１５４入出力インタフェース装置

Claims

複数のネットワークのデータが入力されたときに、当該複数のネットワークのデータの各ノードの対応付けを見つける対応付け装置であって、
各ノードとクラスタとの関係を推定するときに、前記入力されたデータ、該当ノード以外のクラスタ割当集合、該当ノード以外の関連割当集合、及びパラメータに基づき、該当ノードがクラスタに関連するかどうかを推定するクラスタ関連推定部と、
前記パラメータがどのくらい前記入力されたデータをもっともらしく説明できているかを示す尤度が高くなるようにパラメータを推定するパラメータ推定部と、
前記クラスタ関連推定部における推定を、終了条件が満たされるまで繰り返す終了条件判定部と、
を有する対応付け装置。
前記クラスタ関連推定部は、該当ノードがクラスタに関連しない場合、ノードによって異なる確率でノード間のリンクがはられると仮定し、該当ノードがクラスタに関連するかどうかを推定する、請求項１に記載の対応付け装置。
前記パラメータ推定部は、前記パラメータに対してガンマ事前分布を仮定して事後確率からサンプリングすることで、前記パラメータを推定する、請求項１又は２に記載の対応付け装置。
複数のネットワークのデータが入力されたときに、当該複数のネットワークのデータの各ノードの対応付けを見つける対応付け装置における対応付け方法であって、
各ノードとクラスタとの関係を推定するときに、前記入力されたデータ、該当ノード以外のクラスタ割当集合、該当ノード以外の関連割当集合、及びパラメータに基づき、該当ノードがクラスタに関連するかどうかを推定するクラスタ関連推定ステップと、
前記パラメータがどのくらい前記入力されたデータをもっともらしく説明できているかを示す尤度が高くなるようにパラメータを推定するパラメータ推定ステップと、
前記クラスタ関連推定ステップにおける推定を、終了条件が満たされるまで繰り返す終了条件判定ステップと、
を有する対応付け方法。
前記クラスタ関連推定ステップにおいて、該当ノードがクラスタに関連しない場合、ノードによって異なる確率でノード間のリンクがはられると仮定し、該当ノードがクラスタに関連するかどうかを推定する、請求項４に記載の対応付け方法。
前記パラメータ推定ステップにおいて、前記パラメータに対してガンマ事前分布を仮定して事後確率からサンプリングすることで、前記パラメータを推定する、請求項４又は５に記載の対応付け方法。
コンピュータを、請求項１乃至３のいずれか１項に記載の対応付け装置の各部として機能させるためのプログラム。