(57)【要約】【課題】精度よく、異なるデータ間のグループを対応付けることができる。【解決手段】カーネル計算部３２が、異なる２つのデータの各データについて、データのＮ個のグループのうち２つのグループの間の各々に対し、２つのグループ間の関連性を表すカーネルを計算し、データごとに、全てのグループ間のカーネルをまとめた行列を得て、並び替え部３４が、計算した２つのグループ間の各々のカーネルに基づいて、２つのデータ間の依存性が最も高くなるように、データのＮ個のグループを並び替える並替行列を求め、データのＮ個のグループを並び替える。【選択図】図１
2015219880.tif 000002
【特許請求の範囲】
【請求項１】
異なる複数のデータであって、各データが、Ｎ個のグループにグループ化されたオブジェクトの集合である複数のデータを入力として、前記複数のデータ間で、グループの対応付けを行うグループ対応付け装置であって、
前記複数のデータの各々に対し、前記データのＮ個のグループのうちの２つのグループ間の各々について、前記２つのグループ間の関連性を表すカーネルを計算するカーネル計算部と、
前記カーネル計算部により前記複数のデータの各々に対して計算した前記２つのグループ間の各々のカーネルに基づいて、前記複数のデータ間の依存性が高くなるように、前記データのＮ個のグループを並び替えることにより、前記複数のデータ間でグループの対応付けを行う並び替え部と、
を含むグループ対応付け装置。
【請求項２】
前記カーネル計算部は、前記２つのグループ間の各々について、前記グループに含まれるオブジェクトの分布間の類似度を用いて前記カーネルを計算する請求項１に記載のグループ対応付け装置。
【請求項３】
異なる複数のデータであって、各データが、Ｎ個のグループにグループ化されたオブジェクトの集合である複数のデータを入力として、前記複数のデータ間で、グループの対応付けを行うグループ対応付け方法であって、
カーネル計算部が、前記複数のデータの各々に対し、前記データのＮ個のグループのうちの２つのグループ間の各々について、前記２つのグループ間の関連性を表すカーネルを計算するステップと、
並び替え部が、前記カーネル計算部により前記複数のデータの各々に対して計算した前記２つのグループ間の各々のカーネルに基づいて、前記複数のデータ間の依存性が高くなるように、前記データのＮ個のグループを並び替えることにより、前記複数のデータ間でグループの対応付けを行うステップと、
を含むグループ対応付け方法。
【請求項４】
前記カーネル計算部において前記２つのグループ間の関連性を表すカーネルを計算するステップは、前記２つのグループ間の各々について、前記グループに含まれるオブジェクトの分布間の類似度を用いて前記カーネルを計算する請求項３に記載のグループ対応付け方法。
【請求項５】
コンピュータを、請求項１又は２に記載のグループ対応付け装置を構成する各部として機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、グループ対応付け装置、方法、及びプログラムに係り、特に、データ間のグループを対応付けるグループ対応付け装置、方法、及びプログラムに関する。
【背景技術】
【０００２】
異なるデータに含まれるオブジェクトを対応付ける手法は、画像と文の対応付けや、英語と日本語の単語の対応付け、異なるデータベースに含まれるユーザＩＤの対応付けなど、様々な応用が可能である。いくつかの応用例においては、オブジェクトをグループ化して、対応付けを行っている。例えば、画像や文をその内容に応じて分類して対応付けを行う場合や、単語がその意味に応じてまとめて対応付けを行う場合、ユーザをその属するコミュニティーに応じてグループ化して対応付けを行う場合などである。
【０００３】
これらの対応付けにおいては、オブジェクトに関する対応情報が事前に与えられている場合や、異なるデータ間の距離が計算できる場合の対応付け手法が提案されている (例えば、非特許文献１)。また、対応情報や距離尺度がない場合であっても、オブジェクトを対応付ける手法もいくつか提案されている（例えば、非特許文献２、３、４）。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】Tomoharu Iwata, Shinji Watanabe, Hiroshi Sawada: ”Fashion Coordinates Recommender System using Photographs from Fashion Magazines,” The twenty-second International Joint Conference on Artificial Intelligence (IJCAI), 2262-2267, 2011.
【非特許文献２】Tomoharu Iwata, Tsutomu Hirao, Naonori Ueda: ”Unsupervised Cluster Matching via Probabilistic Latent Variable Models,”The Twenty-Seventh AAAI Conference on Artificial Intelligence, 2013.
【非特許文献３】Novi Quadrianto, Alex J. Smola, Le Song, Tinne Tuytelaars. KernelizedSorting. IEEE Trans. on Pattern Analysis and Machine Intelligence PAMI, vol. 32(10), pp.1809-1821, 2010.
【非特許文献４】Djuric, N., Grbovic, M., Vucetic, S., Convex Kernelized Sorting, AAAI Conference on Artificial Intelligence (AAAI), Toronto, Canada, 2012.
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかし、非特許文献１の技術では、対応情報や距離尺度が事前に与えられない場合には適用できないという問題がある。また、非特許文献２、３、４の技術では、グループ化されていないデータを対象としているため、オブジェクトのグループについての対応付けができない、という問題がある。
【０００６】
本発明では、上記問題点を解決するために成されたものであり、精度よく、異なるデータ間のグループを対応付けることができるグループ対応付け装置、方法及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００７】
上記目的を達成するために、本発明に係るグループ対応付け装置は、異なる複数のデータであって、各データが、Ｎ個のグループにグループ化されたオブジェクトの集合である複数のデータを入力として、前記複数のデータ間で、グループの対応付けを行うグループ対応付け装置であって、前記複数のデータの各々に対し、前記データのＮ個のグループのうちの２つのグループ間の各々について、前記２つのグループ間の関連性を表すカーネルを計算するカーネル計算部と、前記カーネル計算部により前記複数のデータの各々に対して計算した前記２つのグループ間の各々のカーネルに基づいて、前記複数のデータ間の依存性が高くなるように、前記データのＮ個のグループを並び替えることにより、前記複数のデータ間でグループの対応付けを行う並び替え部と、を含んで構成されている。
【０００８】
前記カーネル計算部は、前記２つのグループ間の各々について、前記グループに含まれるオブジェクトの分布間の類似度を用いて前記カーネルを計算してもよい。
【０００９】
また、本発明に係るグループ対応付け装置において、前記カーネルは、線形カーネル、ガウスカーネル、及び多項式カーネルのうちいずれか一つのカーネルとしてもよい。
【００１０】
本発明に係るグループ対応付け方法は、異なる複数のデータであって、各データが、Ｎ個のグループにグループ化されたオブジェクトの集合である複数のデータを入力として、前記複数のデータ間で、グループの対応付けを行うグループ対応付け方法であって、カーネル計算部が、前記複数のデータの各々に対し、前記データのＮ個のグループのうちの２つのグループ間の各々について、前記２つのグループ間の関連性を表すカーネルを計算するステップと、並び替え部が、前記カーネル計算部により前記複数のデータの各々に対して計算した前記２つのグループ間の各々のカーネルに基づいて、前記複数のデータ間の依存性が高くなるように、前記データのＮ個のグループを並び替えることにより、前記複数のデータ間でグループの対応付けを行うステップと、を含んで実行することを特徴とする。
【００１１】
また、本発明に係るグループ対応付け方法において、前記カーネル計算部において前記２つのグループ間の関連性を表すカーネルを計算するステップは、前記２つのグループ間の各々について、前記グループに含まれるオブジェクトの分布間の類似度を用いて前記カーネルを計算してもよい。
【００１２】
また、本発明に係るグループ対応付け方法において、前記カーネルは、線形カーネル、ガウスカーネル、及び多項式カーネルのうちいずれか一つのカーネルとしてもよい。
【００１３】
本発明に係るプログラムは、コンピュータに、上記のグループ対応付け装置を構成する各部として機能させるためのプログラムである。
【発明の効果】
【００１４】
本発明のグループ対応付け装置、方法、及びプログラムによれば、異なる複数のデータの各データについて、Ｎ個のグループのうちの２つのグループ間の各々の関連性を示すカーネルを計算し、計算した２つのグループ間の各々のカーネルに基づいて、複数のデータ間の依存性が高くなるように、データのグループを並び替えることで、精度よく、異なるデータ間のグループを対応付けることができる、という効果が得られる。
【図面の簡単な説明】
【００１５】
【図１】本発明の実施の形態に係るグループ対応付け装置の主要構成を示すブロック図である。
【図２】本発明の実施の形態におけるグループ対応付け処理ルーチンの内容を示すフローチャートである。
【発明を実施するための形態】
【００１６】
以下、図面を参照して本発明の実施の形態を詳細に説明する。
【００１７】
＜本発明の実施の形態の原理＞
【００１８】
まず、本発明の実施の形態の原理について説明する。
【００１９】
入力データとして２つのグループ化されたオブジェクトの集合であるデータＸ＝｛Ｘ１，・・・，ＸＮ｝とＹ＝｛Ｙ１，・・・，ＹＮ｝という２つのデータが与えられたとする。ここで、
【００２０】
【数１】
2015219880.tif 000003
【００２１】
は、１つ目のデータのｎ番目のグループに含まれるオブジェクトの集合、ｘｎｉはｎ番目のグループのｉ番目のオブジェクト、Ｉｎはｎ番目のグループに含まれるオブジェクト数を表す。同様に
【００２２】
【数２】
2015219880.tif 000004
【００２３】
は、２つ目のデータのｎ番目のグループに含まれるオブジェクトの集合、ｙｎｊはｎ番目のグループのｊ番目のオブジェクト、Ｊｎはｎ番目のグループに含まれるオブジェクト数を表す。つまり、データＸとＹの各々が、Ｎ個のグループにグループ化されたオブジェクトの集合である。なお、本説明においては２つのデータが与えられた場合を想定して説明するが、３つ以上のデータが与えられた場合にも、２つのデータ毎に適用することにより、同様に適用可能である。
【００２４】
処理としては、まず、上記与えられた２つのデータを読み込む。次に、２つのデータの各々に対し、Ｎ個のグループのうち２つのグループ間の各々について、グループ間の関連性を表すカーネルを計算する。計算において、２つのグループの統計的性質が近似する場合、カーネルの値は高くなる。
【００２５】
次に、計算したカーネルの値を用いて、２つのデータ間の依存性が最も高くなるように、Ｎ個のグループを並び替えることにより、２つのデータ間のグループを対応付ける。
【００２６】
対応付けは下記（３）式により、並替行列π∈ΠＮで表現される。
【００２７】
【数３】
2015219880.tif 000005
【００２８】
ここで１Ｎは要素がすべて１のＮ次元ベクトルである。そして、下記（４）式により、グループ化されたオブジェクト集合であるデータＸＮとＹＮとの依存性が最大になるような並替行列を求める。
【００２９】
【数４】
2015219880.tif 000006
【００３０】
ここでＤ（・）は依存性の尺度である。依存性の尺度としては後述するヒルベルト−シュミット独立基準（Ｈｉｌｂｅｒｔ−Ｓｃｈｍｉｄｔ  Ｉｎｄｅｐｅｎｄｅｎｃｅ  Ｃｒｉｔｅｒｉｏｎ；  ＨＳＩＣ）を用いる。なお、依存性の尺度として、相互情報量など他の依存性の尺度を用いることも可能である。
【００３１】
上述したように、本発明の実施の形態では、異なる複数のデータについて、データ毎に、Ｎ個のグループのうちの２つのグループ間の各々に対してカーネルを計算し、複数のデータ間の依存性が高くなるように、Ｎ個のグループを並び替えることで、複数のデータ間のグループの対応付けを行う。
【００３２】
＜本発明の実施の形態に係るグループ対応付け装置の構成＞
【００３３】
次に、本発明の実施の形態に係るグループ対応付け装置の構成について説明する。図１に示すように、本発明の実施の形態に係るグループ対応付け装置１００は、ＣＰＵと、ＲＡＭと、後述するグループ対応付け処理ルーチンを実行するためのプログラムや各種データを記憶したＲＯＭと、を含むコンピュータで構成することが出来る。このグループ対応付け装置１００は、機能的には図１に示すように入力部１０と、演算部２０と、出力部５０とを備えている。
【００３４】
入力部１０は、異なる複数のデータであって、各データが、Ｎ個のグループにグループ化されたオブジェクトの集合である複数のデータを受け付ける。本実施の形態では、複数のデータは２つのデータＸ、Ｙとする。
【００３５】
演算部２０は、データ記憶部３０と、カーネル計算部３２と、並び替え部３４とを含んで構成されている。
【００３６】
データ記憶部３０は、入力部１０において受け付けた２つのデータを記憶している。
【００３７】
カーネル計算部３２は、まず、データ記憶部３０に記憶されている２つのデータを読み込む。次に、読み込んだ２つのデータに基づいて、２つのデータの各々について、当該データのＮ個のグループのうち２つのグループ間の各々に対し、２つのグループ間の関連性を表すカーネルを計算する。
【００３８】
カーネル計算部３２における計算は、当該データのＮ個のグループの各々を分布として捉え、グループの分布間の各々の統計的性質を類似度としてカーネルを計算する。まず、当該データの２つのグループに含まれる２つのオブジェクト間の各々の類似度であるカーネルを計算する。そして、計算した２つのオブジェクト間の各々のカーネルに基づいて、当該データについて、Ｎ個のグループのうちの２つのグループの分布間の各々のカーネルを計算する。ここで、カーネル埋め込み法により、オブジェクト間のカーネルを用いて、分布を、再生核ヒルベルト空間上の１点により表現できる。そして、再生核ヒルベルト空間上での分布間のカーネルが、２つのグループ間のカーネルであると考える。
【００３９】
オブジェクト間のカーネル、及び分布間のカーネルとしては、線形カーネル、ガウスカーネル、多項式カーネルのうち任意のカーネルを用いることができる。
【００４０】
オブジェクトｘｎｉとｘｍｊの間の線形カーネルは下記（５）式で計算できる。
【００４１】
【数５】
2015219880.tif 000007
【００４２】
また、オブジェクトｘｎｉとｘｍｊの間のガウスカーネルは下記（６）式で計算できる。
【００４３】
【数６】
2015219880.tif 000008
【００４４】
また、オブジェクトｘｎｉとｘｍｊの間の多項式カーネルは下記（７）式で計算できる。
【００４５】
【数７】
2015219880.tif 000009
【００４６】
再生核ヒルベルト空間上でのグループＸｎとＸｍの間の線形カーネルは下記（８）式で計算できる。
【００４７】
【数８】
2015219880.tif 000010
【００４８】
また、グループＸｎとＸｍの間のガウスカーネルは下記（９）式で計算できる。
【００４９】
【数９】
2015219880.tif 000011
【００５０】
また、グループＸｎとＸｍの間の多項式カーネルは下記（１０）式で計算できる。
【００５１】
【数１０】
2015219880.tif 000012
【００５２】
そして、カーネル計算部３２は、上記（８）式、（９）式、又は（１０）式に従って、計算した２つのグループ間の各々のカーネルに基づいて、２つのデータの各々について、データごとに、全てのグループ間のカーネルをまとめた行列を得る。本実施の形態では、１つ目のデータＸの全てのグループ間のカーネルをまとめたものをＫとする。ここでＫはＮ×Ｎの行列であり、Ｋの（ｎ，ｍ）要素はｎ番目のグループとｍ番目のグループのカーネルＫ（Ｘｎ，Ｘｍ）を表す。同様に、２つ目のデータＹの全てのグループ間のカーネルをまとめたものをＬとする。
【００５３】
並び替え部３４は、カーネル計算部３２により２つのデータの各々に対して計算した２つのグループ間の各々のカーネルに基づいて、２つのデータ間の依存性が高くなるように、データのＮ個のグループを並び替えて、２つのデータ間のグループを対応付ける。
【００５４】
例えば、並び替え部３４は、まず、カーネル計算部３２により得たデータＸついてのＫ、データＹについてのＬを読み込む。そして、ＸとＹとのデータ間の依存性が高くなるように、Ｎ個のグループを並べ替える。ここで、依存性の尺度としてヒルベルト−シュミット独立基準（Ｈｉｌｂｅｒｔ−Ｓｃｈｍｉｄｔ  Ｉｎｄｅｐｅｎｄｅｎｃｅ  Ｃｒｉｔｅｒｉｏｎ；ＨＳＩＣ）を用いる。２つのデータ間のＨＳＩＣは以下（１１）式により表される。
【００５５】
【数１１】
2015219880.tif 000013
【００５６】
ここでｔｒはトレース、Ｈ＝Ｉ−１Ｎ１ＮＴ／Ｎは中心化行列を表す。また、￣Ｋ＝ＨＫＨ、￣Ｌ＝ＨＬＨである。次の（１２）式により、ＨＳＩＣを最大化するように、並替行列を求める。
【００５７】
【数１２】
2015219880.tif 000014
【００５８】
なお、（１２）式は、ＤＣ  Ｐｒｏｇｒａｍｍｉｎｇを用いる方法、制約付き固有値問題として解く方法（非特許文献３）、又は凸問題として解く方法（非特許文献４）などを用いることにより最大化する。
【００５９】
＜本発明の実施の形態に係るグループ対応付け装置の作用＞
【００６０】
次に、本発明の実施の形態に係るグループ対応付け装置１００の作用について説明する。入力部１０において、各データが、Ｎ個のグループにグループ化されたオブジェクトの集合である２つのデータを受け付けると、データ記憶部３０に格納する。そして、グループ対応付け装置１００は、図２に示すグループ対応付け処理ルーチンを実行する。
【００６１】
まず、ステップＳ１００では、２つのデータをデータ記憶部３０から取得する。
【００６２】
次に、ステップＳ１０２では、ステップＳ１００で取得した２つのデータに基づいて、２つのデータの各々に対し、上記（８）式、（９）式、又は（１０）式に従って、当該データのＮ個のグループのうちの２つのグループ間の各々のカーネルを計算する。そして、２つのデータの各々について、データごとに、全てのグループ間のカーネルをまとめた行列を得る。
【００６３】
次に、ステップＳ１０６において、ステップＳ１０２で２つのデータの各々に対して計算したグループ間の各々のカーネルに基づいて、上記（１２）式に従って、２つのデータ間の依存性が最も高くなるように、データのＮ個のグループを並び替える並替行列を求める。そして、求めた並替行列に基づいて、データのＮ個のグループを並び替え、２つのデータ間でグループを対応付ける。そして、ステップＳ１０８において、ステップＳ１０６でデータ間のグループを対応付けた２つのデータを出力し、処理を終了する。
【００６４】
＜実験結果＞
【００６５】
次に、本実施の形態に係る手法に基づいて行った実験結果について説明する。
【００６６】
本発明の実施の形態に係る手法を評価するため、第１の実験例として、４つのラベル付きデータセットを用いて、データセットごとに実験を行った。実験のため、各データセットの特徴量をランダムに分割し、データセットごとに２つのデータを作成した。
【００６７】
第１の実験例において、本実施の形態と比較する手法としては、ＫＳ−ｍｅａｎ及びＫＳ−ｏｂｊｅｃｔを用いた。ＫＳ−ｍｅａｎは、グループ毎の特徴量をその平均で表し、オブジェクト対応付け法であるｃｏｎｖｅｘ  Ｋｅｒｎｅｌｉｚｅｄ  Ｓｏｒｔｉｎｇ（非特許文献４）を用いてグループを対応付ける方法である。ＫＳ−ｏｂｊｅｃｔは、まずオブジェクトの対応付けをｃｏｎｖｅｘ  Ｋｅｒｎｅｌｉｚｅｄ  Ｓｏｒｔｉｎｇを用いて行い、その後、グループ間の対応する確率を対応付けられたオブジェクト数によって計算し、グループ間の対応付ける方法である。
【００６８】
第１の実験例における本実施の形態に係る手法では、オブジェクト間の各々のカーネルの計算には（５）式を、グループ間の各々のカーネルの計算には（８）式を適用した。
【００６９】
第１の実験例における各実験結果の平均正答率と標準誤差を表１に表す。本発明の実施の形態に係る手法が、全データセットで最も高い正答率を示しており、効果的にグループの対応付けを発見できている。なお、ＫＳ−ｏｂｊｅｃｔは多くの計算量を必要とするため、オブジェクト数が多いＳａｔｉｍａｇｅとＬｅｔｔｅｒのデータセットには適用していない。
【００７０】
【表１】
2015219880.tif 000015
【００７１】
また、第２の実験例として、Ｗｉｋｉｐｅｄｉａ（登録商標）に含まれる６言語（英語、ドイツ語、フィンランド語、フランス語、日本語）の文書のカテゴリを対応付ける実験を行った。
【００７２】
第２の実験例において本実施の形態と比較する手法としては、ＫＳ−ｍｅａｎを用いた。第２の実験例における本実施の形態に係る手法では、オブジェクト間の各々のカーネルの計算には（６）式を、グループ間の各々のカーネルの計算には（９）式を適用した。
【００７３】
第２の実験例における各実験結果の平均正答率と標準誤差を表２に示す。１つの言語対を除き、本発明の実施の形態に係る手法がＫＳ−ｍｅａｎよりも高い正答率を示し、本発明の実施の形態に係る手法の有効性を示している。
【００７４】
【表２】
2015219880.tif 000016
【００７５】
以上、説明したように、本実施の形態に係るグループ対応付け装置によれば、異なる２つのデータの各データについて、Ｎ個のグループのうち２つのグループ間の各々のカーネルを計算し、計算した２つのグループ間の各々のカーネルに基づいて、２つのデータ間の依存性が高くなるように、データのグループを並び替えることで、精度よく、異なるデータ間のグループを対応付けることができる。
【００７６】
なお、本発明は、上述した実施形態に限定されるものではなく、この発明の要旨を逸脱しない範囲内で様々な変形や応用が可能である。
【符号の説明】
【００７７】
１０   入力部
２０   演算部
３０   データ記憶部
３２   カーネル計算部
３４   並び替え部
１００ グループ対応付け装置
【図１】
2015219880.tif 000017
【図２】
2015219880.tif 000018