(57)【特許請求の範囲】
【請求項１】
入力データに対して、複数のカテゴリの各々に属するか否かを示す複数の要素からなる出力データが得られるときの前記入力データから前記出力データを予測する出力予測装置であって、
前記入力データ及び該入力データに対して得られる前記出力データのペアのサンプルの集合である入力されたペア集合と、前記入力データのサンプルの集合であって、かつ、前記出力データが未知の入力された入力データ集合と、前記出力データのサンプルの集合であって、かつ、前記入力データが未知の入力された出力データ集合とを読み込む読み込み手段と、
前記ペア集合及び前記入力データ集合に含まれるサンプルの各組み合わせについて、サンプル間の前記入力データの類似度であるサンプル類似度を計算するサンプル類似度計算手段と、
前記ペア集合及び前記出力データ集合に基づいて、前記出力データに含まれる要素の各組み合わせについて、要素間の値の類似度であるカテゴリ類似度を計算するカテゴリ類似度計算手段と、
前記サンプル類似度計算手段によって計算されたサンプル類似度と、前記カテゴリ類似度計算手段によって計算されたカテゴリ類似度とに基づいて、前記サンプル類似度が高いサンプルの組み合わせの各入力データに対する出力データにおける、前記カテゴリ類似度が高い要素の組み合わせの値が類似するように、前記入力データ集合の各入力データに対する前記出力データを予測する予測手段と、
を含む出力予測装置。
【請求項２】
前記予測手段は、前記ペア集合及び前記入力データ集合の各サンプルに対する出力データについて、前記サンプル類似度が高いサンプルの組み合わせの各入力データに対する出力データにおける、前記カテゴリ類似度が高い要素の組み合わせの値が類似するように予め定めた目的関数を最適化するように、前記入力データ集合の各入力データに対する前記出力データを予測する請求項１記載の出力予測装置。
【請求項３】
入力データに対して、複数のカテゴリの各々に属するか否かを示す複数の要素からなる出力データが得られるときの前記入力データから前記出力データを予測する出力予測装置における出力予測方法であって、
読み込み手段によって、前記入力データ及び該入力データに対して得られる前記出力データのペアのサンプルの集合である入力されたペア集合と、前記入力データのサンプルの集合であって、かつ、前記出力データが未知の入力された入力データ集合と、前記出力データのサンプルの集合であって、かつ、前記入力データが未知の入力された出力データ集合とを読み込むステップと、
サンプル類似度計算手段によって、前記ペア集合及び前記入力データ集合に含まれるサンプルの各組み合わせについて、サンプル間の前記入力データの類似度であるサンプル類似度を計算するステップと、
カテゴリ類似度計算手段によって、前記ペア集合及び前記出力データ集合に基づいて、前記出力データに含まれる要素の各組み合わせについて、要素間の値の類似度であるカテゴリ類似度を計算するステップと、
予測手段によって、前記サンプル類似度計算手段によって計算されたサンプル類似度と、前記カテゴリ類似度計算手段によって計算されたカテゴリ類似度とに基づいて、前記サンプル類似度が高いサンプルの組み合わせの各入力データに対する出力データにおける、前記カテゴリ類似度が高い要素の組み合わせの値が類似するように、前記入力データ集合の各入力データに対する前記出力データを予測するステップと、
を含む出力予測方法。
【請求項４】
前記予測手段によって予測するステップは、前記ペア集合及び前記入力データ集合の各サンプルに対する出力データについて、前記サンプル類似度が高いサンプルの組み合わせの各入力データに対する出力データにおける、前記カテゴリ類似度が高い要素の組み合わせの値が類似するように予め定めた目的関数を最適化するように、前記入力データ集合の各入力データに対する前記出力データを予測する請求項３記載の出力予測方法。
【請求項５】
コンピュータを、請求項１又は２記載の出力予測装置を構成する各手段として機能させるための出力予測プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、出力予測装置、方法、及びプログラムに係り、特に、入力データ集合の各入力データに対する出力データを予測する出力予測装置、方法、及びプログラムに関する。
【背景技術】
【０００２】
教師あり学習では、ペア集合が学習データとして与えられたとき、出力が未知のサンプルの出力を予測する。しかしながら、入力と出力のペアを得ることが困難な場合や、コストがかかる場合がある。そこで、ペア集合とともに、出力が未知の入力集合を用いて、予測精度を高める半教師あり学習法が知られている（非特許文献１）。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】Fujino, A., Ueda, N., and Saito, K. (2008). Semisupervised learning fora hybrid generative/discriminative classi_er based on the maximum entropy principle. IEEE Transactions on Pattern Analysis and Machine Intelligence (TPAMI), 30(3), 424-437
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかしながら、上記非特許文献１では、出力集合を利用して予測精度を高めることができない、という問題点がある。
【０００５】
本発明は上記事情に鑑みてなされたものであり、入力データが未知の出力データ集合を用いて、入力データに対する出力データを精度よく予測することができる出力予測装置、方法、及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００６】
上記目的を達成するために、本発明の出力予測装置は、入力データに対して、複数のカテゴリの各々に属するか否かを示す複数の要素からなる出力データが得られるときの前記入力データから前記出力データを予測する出力予測装置であって、前記入力データ及び該入力データに対して得られる前記出力データのペアのサンプルの集合である入力されたペア集合と、前記入力データのサンプルの集合であって、かつ、前記出力データが未知の入力された入力データ集合と、前記出力データのサンプルの集合であって、かつ、前記入力データが未知の入力された出力データ集合とを読み込む読み込み手段と、前記ペア集合及び前記入力データ集合に含まれるサンプルの各組み合わせについて、サンプル間の前記入力データの類似度であるサンプル類似度を計算するサンプル類似度計算手段と、前記ペア集合及び前記出力データ集合に基づいて、前記出力データに含まれる要素の各組み合わせについて、要素間の値の類似度であるカテゴリ類似度を計算するカテゴリ類似度計算手段と、前記サンプル類似度計算手段によって計算されたサンプル類似度と、前記カテゴリ類似度計算手段によって計算されたカテゴリ類似度とに基づいて、前記サンプル類似度が高いサンプルの組み合わせの各入力データに対する出力データにおける、前記カテゴリ類似度が高い要素の組み合わせの値が類似するように、前記入力データ集合の各入力データに対する前記出力データを予測する予測手段と、を含んで構成されている。
【０００７】
また、本発明の出力予測方法は、入力データに対して、複数のカテゴリの各々に属するか否かを示す複数の要素からなる出力データが得られるときの前記入力データから前記出力データを予測する出力予測装置における出力予測方法であって、読み込み手段によって、前記入力データ及び該入力データに対して得られる前記出力データのペアのサンプルの集合である入力されたペア集合と、前記入力データのサンプルの集合であって、かつ、前記出力データが未知の入力された入力データ集合と、前記出力データのサンプルの集合であって、かつ、前記入力データが未知の入力された出力データ集合とを読み込むステップと、サンプル類似度計算手段によって、前記ペア集合及び前記入力データ集合に含まれるサンプルの各組み合わせについて、サンプル間の前記入力データの類似度であるサンプル類似度を計算するステップと、カテゴリ類似度計算手段によって、前記ペア集合及び前記出力データ集合に基づいて、前記出力データに含まれる要素の各組み合わせについて、要素間の値の類似度であるカテゴリ類似度を計算するステップと、予測手段によって、前記サンプル類似度計算手段によって計算されたサンプル類似度と、前記カテゴリ類似度計算手段によって計算されたカテゴリ類似度とに基づいて、前記サンプル類似度が高いサンプルの組み合わせの各入力データに対する出力データにおける、前記カテゴリ類似度が高い要素の組み合わせの値が類似するように、前記入力データ集合の各入力データに対する前記出力データを予測するステップと、を含む。
【０００８】
本発明によれば、読み込み手段によって、前記入力データ及び該入力データに対して得られる前記出力データのペアのサンプルの集合である入力されたペア集合と、前記入力データのサンプルの集合であって、かつ、前記出力データが未知の入力された入力データ集合と、前記出力データのサンプルの集合であって、かつ、前記入力データが未知の入力された出力データ集合とを読み込む。
【０００９】
そして、サンプル類似度計算手段によって、前記ペア集合及び前記入力データ集合に含まれるサンプルの各組み合わせについて、サンプル間の前記入力データの類似度であるサンプル類似度を計算する。カテゴリ類似度計算手段によって、前記ペア集合及び前記出力データ集合に基づいて、前記出力データに含まれる要素の各組み合わせについて、要素間の値の類似度であるカテゴリ類似度を計算する。
【００１０】
そして、予測手段によって、前記サンプル類似度計算手段によって計算されたサンプル類似度と、前記カテゴリ類似度計算手段によって計算されたカテゴリ類似度とに基づいて、前記サンプル類似度が高いサンプルの組み合わせの各入力データに対する出力データにおける、前記カテゴリ類似度が高い要素の組み合わせの値が類似するように、前記入力データ集合の各入力データに対する前記出力データを予測する。
【００１１】
このように、サンプル間の入力データの類似度であるサンプル類似度と、各カテゴリに属するか否かを示す出力データの要素間の値の類似度であるカテゴリ類似度とを計算し、サンプル類似度及びカテゴリ類似度を用いて、入力データ集合の各入力データに対する出力データを予測することにより、入力データが未知の出力データ集合を用いて、入力データに対する出力データを精度よく予測することができる。
【００１２】
また、本発明の出力予測プログラムは、コンピュータを、上記の出力予測装置を構成する各手段として機能させるためのプログラムである。
【発明の効果】
【００１３】
以上説明したように、本発明の出力予測装置、方法、及びプログラムによれば、サンプル間の入力データの類似度であるサンプル類似度と、各カテゴリに属するか否かを示す出力データの要素間の値の類似度であるカテゴリ類似度とを計算し、サンプル類似度及びカテゴリ類似度を用いて、入力データ集合の各入力データに対する出力データを予測することにより、入力データが未知の出力データ集合を用いて、入力データに対する出力データを精度よく予測することができる、という効果が得られる。
【図面の簡単な説明】
【００１４】
【図１】本発明の実施の形態の出力予測装置の機能的構成を示すブロック図である。
【図２】本発明の実施の形態の出力予測装置における出力予測処理ルーチンの内容を示すフローチャートである。
【図３】本発明の実施の形態の出力予測装置における入力データに対する出力データを予測する処理の流れを示すフローチャートである。
【図４】（Ａ）多様体を示す図、（Ｂ）ペア集合および入力集合に含まれるサンプルを示す図、及び（Ｃ）入力集合に含まれるサンプル及びカテゴリを示す図である。
【図５】実験結果を示す図である。
【発明を実施するための形態】
【００１５】
以下、図面を参照して本発明の実施の形態を詳細に説明する。
【００１６】
＜データの概要＞
ペア集合をD={(xi;yi)}i=1N、入力データ集合をX={xi}I=N+1N+U、出力データ集合Y={yi}i=N+U+1N+U+O とする。ここでN,U,Oはそれぞれペア集合、入力データ集合、出力データ集合の大きさを表す。入力データ集合Ｘは、出力データが未知の入力データの集合であり、出力データＹは、入力データが未知の出力データの集合である。サンプルiとは、ペア集合の場合(xi,yi)を表わし、入力データ集合の場合xiを表わし、出力データ集合の場合yiを表わすものとする。
【００１７】
ペア集合及び入力データ集合に含まれる、サンプルiの入力データはV次元のベクトルxi=(xiv) v=1Vで表される。ここでxivは実数値をとるサンプルiのv番目の特徴量であり、Vは特徴量数である。また、ペア集合及び出力データ集合に含まれる、サンプルiの出力データはK次元のベクトルyi=(yik) k=1Kで表される。ここでKはカテゴリ数を表す。サンプルiのカテゴリkに関する出力データの要素はyik∈{-1,1}であり、サンプルiがカテゴリkに属する場合yik=1であり、カテゴリkに属さない場合yik=-1である。
【００１８】
例えば、入力データが、商品の特徴量を示す特徴量ベクトルであり、出力データが、当該商品が各カテゴリに属するか否かを示す要素からなるベクトルである。
【００１９】
なお、ペア集合のどのサンプルも属しないカテゴリに、出力データ集合のサンプルが属していてもよい。また、あるサンプルは、複数のカテゴリに属することが可能であり、また、どのカテゴリに属しないサンプルが含まれていてもよい。
【００２０】
＜システム構成＞
本発明の実施の形態に係る出力予測装置１００は、ＣＰＵ（Central Processing Unit）と、ＲＡＭ（Random Access Memory）と、後述する出力予測処理ルーチンを実行するためのプログラムを記憶したＲＯＭ（Read Only Memory）とを備えたコンピュータで構成されている。このコンピュータは、機能的には、図１に示すように、読み込み部１０、記憶部２０、及び演算部３０を含んだ構成で表すことができる。
【００２１】
読み込み部１０は、ペア集合読み込み部１１と、入力集合読み込み部１２と、出力集合読み込み部１３とを備えている。
【００２２】
ペア集合読み込み部１１は、入力されたペア集合Ｄを読み込む。入力集合読み込み部１２は、入力された入力データ集合Ｘを読み込む。出力集合読み込み部１３は、入力された出力データ集合Ｙを読み込む。
【００２３】
記憶部２０には、読み込まれたペア集合Ｄが記憶されるペア集合記憶部２１、読み込まれた入力データ集合Ｘが記憶される入力集合記憶部２２、及び読み込まれた出力データ集合Ｙが記憶される出力集合記憶部２３が設けられている。
【００２４】
演算部３０は、サンプル類似度計算部３１と、カテゴリ類似度計算部３２と、予測部３３と、書き込み部３４とを備えている。
【００２５】
サンプル類似度計算部３１は、ペア集合Ｄおよび入力データ集合Ｘに含まれる、サンプルi（i =1,…,N+U）とサンプルj（j =1,…,N+U）との全ての組み合わせについて、サンプル間の入力データの類似度を、サンプル類似度として計算する。サンプルiとサンプルjの類似度をwijとすると、これは、例えば、以下の（１）式に従って計算される。
【００２６】
【数１】
0005698159.tif 000002
【００２７】
ただし、αは予め定められたパラメータである。上記（１）式を用いる方法以外であってもよく、近傍k個のサンプルは1とし、それ以外のサンプルは0とするk近傍グラフや、距離ε以内のサンプルは1とし、それ以外のサンプルは0とするεグラフなどを、サンプルの類似度として用いてもよい。
【００２８】
カテゴリ類似度計算部３２は、ペア集合および出力データ集合に含まれる各サンプルの出力データを用いて、カテゴリk（k=1,…,K）とカテゴリl（l=1,…,K）との全ての組み合わせについて、カテゴリの組み合わせに対する要素間の値の類似度を、カテゴリ類似度として計算する。カテゴリkとカテゴリlとに対応する要素ｙik,ｙil間の類似度をvklとして、例えば、以下の（２）式に従って類似度vklを計算する。
【００２９】
【数２】
0005698159.tif 000003
【００３０】
ただし、βはパラメータである。なお、k近傍グラフや、εグラフなどを、カテゴリの類似度として用いてもよい。
【００３１】
予測部３３は、計算されたサンプル類似度およびカテゴリ類似度を用いて、ペア集合及び入力データ集合の各サンプルi=1,…,N+Uの出力データを予測する。ここで、サンプルiの出力データにおけるカテゴリkの要素の予測をfikとする。
【００３２】
サンプル間の類似度が高い場合、それらのサンプルの出力データは類似すると共に、カテゴリ間の類似度が高い場合、あるサンプルの出力データでそれらのカテゴリの要素値は類似すると仮定する。また、カテゴリ間の類似度が高い場合、類似するサンプルの出力データでそれらのカテゴリに関する要素値は類似すると仮定する。これらの性質を満たすように、入力データ集合の各サンプルの出力データを予測する。
【００３３】
例えば、以下の（３）式に示す目的関数Ｅを最適化（最小化）するように、各サンプルｉの出力データの各要素の値fikを求めることで、ペア集合及び入力データ集合の各サンプルの出力データについて上記の性質が満たされる。
【００３４】
【数３】
0005698159.tif 000004
【００３５】
目的関数Eの最小化は、以下のように、行列演算を用いて効率的に計算できる。まず、グラフラプラシアンをＬ=Ｄ-Ａとする。ここでＡはその(iK+k,jK+l) 要素がwijvklである(N+U)K×(N+U)Kの行列であり、Ｄはその対角要素がDii=Σ(N+U)Kj=1Aijである対角行列である。また、ｆ=(f11,f12,・・・;f1K,f21,・・・,fN+U,K)Tとする。このとき目的関数EはE=ｆTＬｆと書き換えることができる。
【００３６】
ペア集合に含まれるサンプルの出力データは既知のため、ペア集合のサンプルi=1,…,Nにおいてfik=yikとなる制約のもと、目的関数Eを最小化するｆは、以下の（４）式、（５）式に従って計算される。
【００３７】
【数４】
0005698159.tif 000005
【００３８】
ここで、ｆ=(ｆl,ｆu)は、予測ベクトルを、ペア集合に関するものと、入力データ集合に関するものとに分割したものである。以下の（６）式で示されるＬは、グラフラプラシアンを、ペア集合に関するものと、入力データ集合に関するものの4つの部分行列に分割したものである。
【００３９】
【数５】
0005698159.tif 000006
【００４０】
なお、ここでは逆行列を用いて予測ベクトルfを計算する場合を例に説明したが、非特許文献２（Yoshua Bengio, Olivier Delalleau, Nicolas Le Roux: Label Propagation andQuadratic Criterion, Section 11, in Chapelle O, Scholkopf B and Zien A: Semi-Supervised Learning, 508, MIT Press, Cambridge, MA, USA, (2006).）に記載されている繰り返し法など他の手法を用いて、目的関数Eを最小化するfを計算するようにしてもよい。
【００４１】
書き込み部３４は、入力データ集合の各サンプルについて予測した出力データfを記憶部２０に書き込む。
【００４２】
＜出力予測装置の作用＞
本実施の形態の出力予測装置１００に、ペア集合Ｄ、入力データ集合Ｘ、及び出力データ集合Ｙが入力されると、出力予測装置１００において、図２に示す、出力予測処理ルーチンが実行される。
【００４３】
まず、ステップＳ１０１で、読み込み部１０によって、入力されたペア集合Ｄ、入力データ集合Ｘ、及び出力データ集合Ｙを読みこみ、ペア集合記憶部２１、入力集合記憶部２２、及び出力集合記憶部２３に格納する。
【００４４】
次のステップＳ１０２では、演算部３０によって、入力データ集合Ｘに含まれる各サンプルに対する出力データｆを予測する。
【００４５】
ここで、上記ステップＳ１０２は、図３に示す処理ルーチンによって実現される。
【００４６】
ステップＳ１１０において、サンプル類似度計算部３１によって、ペア集合Ｄ及び入力データ集合Ｘの各サンプルの入力データに基づいて、上記（１）式に従って、ペア集合Ｄ及び入力データ集合Ｘに含まれるサンプルｉ，ｊの全組み合わせについてサンプル類似度ｗi,jを計算する。
【００４７】
次のステップＳ１１１では、カテゴリ類似度計算部３２によって、ペア集合Ｄ及び出力データ集合Ｙの各サンプルの出力データに基づいて、上記（２）式に従って、カテゴリｋ、ｌの全組み合わせについてカテゴリ類似度ｖk,lを計算する。
【００４８】
そして、ステップＳ１１２では、予測部３３によって、上記ステップＳ１１０で計算したサンプル類似度及び上記ステップＳ１１１で計算したカテゴリ類似度に基づいて、上記（３）式で表わされる目的関数Ｅを最小化するサンプルの出力データを計算することにより、入力データ集合Ｘの各サンプルに対する出力データを予測する。
【００４９】
次のステップＳ１１３では、書き込み部３４によって、予測した出力データを、記憶部２０に書き込み、処理を終了する。
【００５０】
＜実験結果＞
本発明を評価するため、人工データを用いた実験を行った。ペア集合サイズN = 10、入力集合サイズU = 990、出力集合サイズO = 990、入力次元数V = 3、カテゴリ数K = 10 とし、図４のような多様体からデータをサンプリングし、人工データを作成した。図４（Ａ）は多様体、図４（Ｂ）はペア集合および入力集合に含まれるサンプル、図４（Ｃ）は入力集合に含まれるサンプル、色はカテゴリを表す。多様体上において近くにあるサンプルは、類似したカテゴリに属する。
【００５１】
評価尺度として、Mean Reciprocal Rank (MRR) およびNormalized Discounted Cumulative Gain (NDCG) を用いた。両尺度ともに、正解ラベルが上位にランキングされれば高い値になる。
【００５２】
結果を図５に示す。教師あり手法や、半教師あり手法に比べ，本発明が高い性能を達成しており、本発明の有効性を示している。
【００５３】
以上説明したように、本発明の実施の形態に係る出力予測装置によれば、サンプル間の入力データの類似度であるサンプル類似度と、各カテゴリに属するか否かを示す出力データの要素間の値の類似度であるカテゴリ類似度とを計算し、サンプル類似度及びカテゴリ類似度を用いて、入力データ集合の各入力データに対する出力データを予測することにより、入力データが未知の出力データ集合を有効利用して、入力データに対する出力データを精度よく予測することができる。
【００５４】
あるサンプルに対する入力データと出力データのペアの集合と、サンプル集合に対する入力データ集合、およびサンプル集合に対する出力データ集合から、サンプル間の類似度およびカテゴリ間の類似度を計算し、サンプル間の類似度が高いサンプルの入力データに対する出力データにおける、類似度の高いカテゴリの要素値は類似している、という仮定の下で最も尤度が高くなるように、入力データに対する出力データを予測する。これによって、入力データと出力データのペア集合が入出力の関係を学習できるほど十分に多く得られない場合でも、出力データが未知である入力データに対する出力データを精度よく予測することができる。
【００５５】
本発明は、上記実施の形態に限定されるものではなく、この発明の要旨を逸脱しない範囲内で様々な変形や応用が可能である。
【００５６】
例えば、上述の出力予測装置は、内部にコンピュータシステムを有しているが、「コンピュータシステム」は、ＷＷＷシステムを利用している場合であれば、ホームページ提供環境（あるいは表示環境）も含むものとする。
【００５７】
また、本願明細書中において、プログラムが予めインストールされている実施形態として説明したが、当該プログラムを、コンピュータ読み取り可能な記録媒体に格納して提供することも可能である。
【符号の説明】
【００５８】
１０   読み込み部
２０   記憶部
３０   演算部
３１   サンプル類似度計算部
３２   カテゴリ類似度計算部
３３   予測部
１００ 出力予測装置
【図１】
0005698159.tif 000007
【図２】
0005698159.tif 000008
【図３】
0005698159.tif 000009
【図４】
0005698159.tif 000010
【図５】
0005698159.tif 000011