(57)【要約】【課題】入力テンソル上の欠損値を精度よく推定することができるようにする。【解決手段】曖昧性解消部２３は、タグを、タクソノミの末端クラスにリンクさせて、ユーザ、アイテム、及び末端クラスの関係を示す要素からなる曖昧性解消テンソルを作成する。スパース性緩和部２４は、タクソノミの各末端クラスからスパースクラスを抽出し、スパースクラスの親クラスを用いて、ユーザ、アイテム、及び親クラスの関係を示す要素からなる抽象テンソルを作成する。クラスタリング部２５は、デンスクラスを抽出しデンスクラスにリンクするタグを複数のマシンドリブンクラスに分類して、ユーザ、アイテム、及びマシンドリブンクラスの関係を示す要素からなるクラスタテンソルを作成する。テンソル拡張部２６は、曖昧性解消テンソル、抽象テンソル、及びクラスタテンソルを用いた拡張テンソルを計算する。【選択図】図１
2014164612.tif 000002
【特許請求の範囲】
【請求項１】
複数次元の各々のオブジェクト間の関係を示す関係データの各観測値を要素として含む入力テンソル上の欠損値を推定する欠損値推定装置であって、
前記複数次元の何れかのクラスの背景知識として予め用意されたクラス階層構造であるタクソノミに基づいて、前記入力テンソルの前記観測値に対応する各要素について、前記タクソノミのクラス階層構造の末端クラスの何れかにリンクし、前記末端クラスを含む複数次元の各々のオブジェクト間の関係を示す前記関係データの各観測値を要素として含む曖昧性解消テンソルを作成する曖昧性解消手段と、
前記曖昧性解消手段によって作成された前記曖昧性解消テンソルに基づいて、前記タクソノミの各末端クラスから、少なくとも１つの観測値に対応する要素に含まれる末端クラスであって、かつ、観測数が所定値未満であるスパースクラスを抽出し、前記曖昧性解消テンソルの要素のうち、前記抽出されたスパースクラスを用いた要素の各々について、前記抽出されたスパースクラスの親クラスを用いて、前記親クラスを含む複数次元の各々のオブジェクト間の関係を示す前記関係データの観測値を要素として含む抽象テンソルを作成するスパース性緩和手段と、
前記曖昧性解消手段によって作成された前記曖昧性解消テンソルに基づいて、前記タクソノミの各末端クラスから、密な観測を持つ末端クラスであるデンスクラスを抽出し、前記抽出されたデンスクラスの各々に対し、前記入力テンソルの要素のうち、前記抽出されたデンスクラスにリンクされる要素の各々を、複数のクラスに分類し、前記分類されたクラスを含む複数次元の各々のオブジェクト間の関係を示す前記関係データの観測値を要素として含むクラスタテンソルを作成するクラスタリング手段と、
前記曖昧性解消手段によって作成された前記曖昧性解消テンソル、前記スパース性緩和手段によって作成された前記抽象テンソル、及び前記クラスタリング手段によって作成されたクラスタテンソルを用いた拡張テンソルを計算するテンソル拡張手段と、
前記テンソル拡張手段によって拡張された拡張テンソルを、テンソル分解法により分解及び復元することで、前記拡張テンソルにおける未観測値の要素を推定し、前記推定した前記拡張テンソルにおける未観測値の要素に基づいて、前記入力テンソル上の欠損値を推定する欠損値推定手段と、
を含む欠損値推定装置。
【請求項２】
前記テンソル拡張手段は、前記タクソノミの各末端クラスのうち、前記デンスクラスでない末端クラスの各々について、前記末端クラスに関する前記関係データの要素の各々を、前記曖昧性解消テンソルから取り出して、前記拡張テンソルの対応する要素の各々として設定し、
前記末端クラスの親クラスの各々について、前記親クラスに関する前記関係データの要素の各々を、前記抽象テンソルから取り出して、前記拡張テンソルの対応する要素の各々として設定し、
前記分類されたクラスの各々について、前記クラスに関する前記関係データの要素の各々を、前記クラスタテンソルから取り出して、前記拡張テンソルの対応する要素の各々として設定する請求項１記載の欠損値推定装置。
【請求項３】
前記テンソル拡張手段は、前記タクソノミの各末端クラスのうち、前記スパースクラス及び前記デンスクラスの何れでもない末端クラスの各々について、前記末端クラスに関する前記関係データの要素の各々を、前記曖昧性解消テンソルから取り出して、前記拡張テンソルの対応する要素の各々として設定し、
前記スパースクラスの各々の親クラスについて、前記親クラスに関する前記関係データの要素の各々を、前記抽象テンソルから取り出して、前記拡張テンソルの対応する要素の各々として設定し、
前記分類されたクラスの各々について、前記クラスに関する前記関係データの要素の各々を、前記クラスタテンソルから取り出して、前記拡張テンソルの対応する要素の各々として設定する請求項１記載の欠損値推定装置。
【請求項４】
前記入力テンソルは、個人ユーザの商品及び商品消費コンテクストの組み合わせに対する消費頻度からなるユーザの消費履歴から得られる、ユーザ、商品、及び商品消費コンテクストの関係を示す関係データの観測値を要素として含み、
前記タクソノミは、商品クラスのクラス階層構造であり、
前記欠損値推定手段は、前記入力テンソル上の欠損値を推定し、前記推定した前記入力テンソル上の欠損値に基づいて、ユーザが関心を持ち得る商品を予測する請求項１〜請求項３の何れか１項記載の欠損値推定装置。
【請求項５】
複数次元の各々のオブジェクト間の関係を示す関係データの各観測値を要素として含む入力テンソル上の欠損値を推定する欠損値推定装置における欠損値推定方法であって、
曖昧性解消手段によって、前記複数次元の何れかのクラスの背景知識として予め用意されたクラス階層構造であるタクソノミに基づいて、前記入力テンソルの前記観測値に対応する各要素について、前記タクソノミのクラス階層構造の末端クラスの何れかにリンクし、前記末端クラスを含む複数次元の各々のオブジェクト間の関係を示す前記関係データの各観測値を要素として含む曖昧性解消テンソルを作成し、
スパース性緩和手段によって、前記曖昧性解消手段によって作成された前記曖昧性解消テンソルに基づいて、前記タクソノミの各末端クラスから、少なくとも１つの観測値に対応する要素に含まれる末端クラスであって、かつ、観測数が所定値未満であるスパースクラスを抽出し、前記曖昧性解消テンソルの要素のうち、前記抽出されたスパースクラスを用いた要素の各々について、前記抽出されたスパースクラスの親クラスを用いて、前記親クラスを含む複数次元の各々のオブジェクト間の関係を示す前記関係データの観測値を要素として含む抽象テンソルを作成し、
クラスタリング手段によって、前記曖昧性解消手段によって作成された前記曖昧性解消テンソルに基づいて、前記タクソノミの各末端クラスから、密な観測を持つ末端クラスであるデンスクラスを抽出し、前記抽出されたデンスクラスの各々に対し、前記入力テンソルの要素のうち、前記抽出されたデンスクラスにリンクされる要素の各々を、複数のクラスに分類し、前記分類されたクラスを含む複数次元の各々のオブジェクト間の関係を示す前記関係データの観測値を要素として含むクラスタテンソルを作成し、
テンソル拡張手段によって、前記曖昧性解消手段によって作成された前記曖昧性解消テンソル、前記スパース性緩和手段によって作成された前記抽象テンソル、及び前記クラスタリング手段によって作成されたクラスタテンソルを用いた拡張テンソルを計算し、
欠損値推定手段によって、前記テンソル拡張手段によって拡張された拡張テンソルを、テンソル分解法により分解及び復元することで、前記拡張テンソルにおける未観測値の要素を推定し、前記推定した前記拡張テンソルにおける未観測値の要素に基づいて、前記入力テンソル上の欠損値を推定する
欠損値推定方法。
【請求項６】
前記入力テンソルは、個人ユーザの商品及び商品消費コンテクストの組み合わせに対する消費頻度からなるユーザの消費履歴から得られる、ユーザ、商品、及び商品消費コンテクストの関係を示す関係データの観測値を要素として含み、
前記タクソノミは、商品クラスのクラス階層構造であり、
前記欠損値推定手段は、前記入力テンソル上の欠損値を推定し、前記推定した前記入力テンソル上の欠損値に基づいて、ユーザが関心を持ち得る商品を予測する請求項５記載の欠損値推定方法。
【請求項７】
請求項１〜請求項４の何れか１項に記載の欠損値推定装置を構成する各手段として、コンピュータを機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、欠損値推定装置、方法、及びプログラムに係り、特に、複数次元の各々のオブジェクト間の関係を示す関係データの各観測値を要素として含む入力テンソル上の欠損値を推定する欠損値推定装置、方法、及びプログラムに関する。
【背景技術】
【０００２】
Web／ネットワーク上において、ユーザによる対象の意味や概念に対する参照要求が大きくなるにつれ、WikiPedia(登録商標)などの体系化された辞書が普及するようになってきている。また、こうしたユーザの要求を人手ではなく、人の代わりにサービスが処理し、ユーザにカスタマイズして提示可能とするため、機械処理可能な概念参照API(Application Programming Interface)が急速に普及しており、DBPedia（登録商標）、WordNet（登録商標）、FreeBase(登録商標)など様々な情報プロバイダが、自身の持つ情報を体系化しAPIを通じ安価、無料で提示するようになってきている（例えば、非特許文献１参照）。
【０００３】
一方、ユーザの興味のある概念を推測し、ユーザに代わり情報を収集提示するような推薦システムも必要とされ、研究されてきた。特に、商品、ユーザの２次元の行列を分解する方法による商品推薦方法が普及しつつあり、特に、商品にユーザが与える評点の予測などの分野への応用や実用化が行われるようになってきている。こうした推薦手法の研究に、商品の属する概念を適用することができれば、より詳細かつ広範囲にユーザの興味を推定できる可能性がある。
【０００４】
現在、ユーザが商品に与える［ユーザ，商品］という関係と、その関係の示す値である「評点」と言う関係からなる行列を生成し、その行列を分解することで、ユーザがまだ購入していない商品に対する評価を予測するという行列分解による欠損値の予測が行われている（例えば、非特許文献２参照）。
【０００５】
それに対し、ユーザが商品に与えるタグを基に、[ユーザ，タグ，商品]という関係と、その関係の示す値である「評点」と言う関係からなるテンソルを生成し、そのテンソルを分解することで、ユーザがまだ購入していない商品に対する評価を予測するという研究も行われている（例えば、非特許文献３参照）。
【先行技術文献】
【非特許文献】
【０００６】
【非特許文献１】Linked Open Data Project (htt://linkeddata.org/)
【非特許文献２】Liang Xiong, Xi chen, Tzu-kuo Huang, Jeff Schneider, and Jaime Carbonell, Temporal Collaborative Filtering with Bayesian Probabilistic Tensor Factorization, SIAM Data Mining 2010.
【非特許文献３】Steffen Rendle, Christoph Freudenthaler, and Lars Schmidt-Thieme. Factorizing personalized markov chains for next-basket recommendation. In Proc. WWW ’10, pages 811-820, 2010.
【発明の概要】
【発明が解決しようとする課題】
【０００７】
しかしながら、上記の非特許文献３の技術は、タグはキーワードであり、例えば、［ユーザＡ，クラシック，ビートルズ］という関係がある場合、クラシックというのが、ロックにおけるクラシックであるという意味が把握できない。そうすると、この関係は［ユーザＢ，クラシック，バッハ］という関係と親しい関係となり得る。しかし、実際は［ユーザＡ，クラシック，ビートルズ］は、［ユーザＡ，ロック／クラシック，ビートルズ］という意味であり、それは［ユーザＡ，ロック／クラシック，ローリング・ストーンズ］の方が［ユーザＢ，クラシック，バッハ］よりも関係としては近いと常識的には考えられる。こうした商品を分類するタグの曖昧性を回避しなければ、テンソル分解の精度に問題を残すと考えられる。
【０００８】
また、［ユーザＡ，ロック／クラシック，ビートルズ］と［ユーザＢ，ロック／ギター，エリック・クラプトン］は、子ジャンルは異なっているが大ジャンルは等しい。そのことから、ロックつながりで関係が近いということも考えられ、末端のクラスのみでなく、上位クラスから生まれる関係もテンソル上で取り扱えるようにすると、テンソル分野の精度がよくなる可能性もあると考えられる。
【０００９】
また、[ユーザA，90s/ロック，ニルバーナ]と、[ユーザB，90s/ロック，ガンズ＆ローゼス]は、子ジャンルも同じであるが、実際はアイテムの種類が異なる。つまり、この場合、子ジャンルをより具体化して取扱う事ができれば、テンソル分解の精度がよくなる可能性もあると考えられる。
【００１０】
様々な出来事が、いくつかの物事同士の関わりによって表される。対象が２種類であれば２次元の配列としての行列によってデータを表すことができるが、より多くの対象が同時に関わってくるのなら、高次元の配列、つまりテンソルという形で表すことができる。誤差が大きい、実験にコストが掛かるために一部しか観測できない、などといった理由でデータに欠損が生じるといった状況は様々に発生する。欠損の生じたデータはそのままでは解析に適さないといった理由で多くの場合満足に利用することができず、そのまま無駄になってしまうことになる。このような場合には未知のデータを推定することができれば、初めから一部しか観測を行わないことでコストや手間を軽減することができる。組み合わせの数が膨大なためにそもそも網羅的な観測が不可能な場合であっても、一部の観測から全体像を捉えるといったことも考えられる。そのような目的のためにテンソルを補完する手法が重要になってくる。
【００１１】
本発明は、上記の事情を鑑みてなされたもので、入力テンソル上の欠損値を精度よく推定することができる欠損値推定装置、方法、及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１２】
上記の目的を達成するために本発明に係る欠損値推定装置は、複数次元の各々のオブジェクト間の関係を示す関係データの各観測値を要素として含む入力テンソル上の欠損値を推定する欠損値推定装置であって、前記複数次元の何れかのクラスの背景知識として予め用意されたクラス階層構造であるタクソノミに基づいて、前記入力テンソルの前記観測値に対応する各要素について、前記タクソノミのクラス階層構造の末端クラスの何れかにリンクし、前記末端クラスを含む複数次元の各々のオブジェクト間の関係を示す前記関係データの各観測値を要素として含む曖昧性解消テンソルを作成する曖昧性解消手段と、前記曖昧性解消手段によって作成された前記曖昧性解消テンソルに基づいて、前記タクソノミの各末端クラスから、少なくとも１つの観測値に対応する要素に含まれる末端クラスであって、かつ、観測数が所定値未満であるスパースクラスを抽出し、前記曖昧性解消テンソルの要素のうち、前記抽出されたスパースクラスを用いた要素の各々について、前記抽出されたスパースクラスの親クラスを用いて、前記親クラスを含む複数次元の各々のオブジェクト間の関係を示す前記関係データの観測値を要素として含む抽象テンソルを作成するスパース性緩和手段と、前記曖昧性解消手段によって作成された前記曖昧性解消テンソルに基づいて、前記タクソノミの各末端クラスから、密な観測を持つ末端クラスであるデンスクラスを抽出し、前記抽出されたデンスクラスの各々に対し、前記入力テンソルの要素のうち、前記抽出されたデンスクラスにリンクされる要素の各々を、複数のクラスに分類し、前記分類されたクラスを含む複数次元の各々のオブジェクト間の関係を示す前記関係データの観測値を要素として含むクラスタテンソルを作成するクラスタリング手段と、前記曖昧性解消手段によって作成された前記曖昧性解消テンソル、前記スパース性緩和手段によって作成された前記抽象テンソル、及び前記クラスタリング手段によって作成されたクラスタテンソルを用いた拡張テンソルを計算するテンソル拡張手段と、前記テンソル拡張手段によって拡張された拡張テンソルを、テンソル分解法により分解及び復元することで、前記拡張テンソルにおける未観測値の要素を推定し、前記推定した前記拡張テンソルにおける未観測値の要素に基づいて、前記入力テンソル上の欠損値を推定する欠損値推定手段と、を含んで構成されている。
【００１３】
本発明に係る欠損値推定方法は、複数次元の各々のオブジェクト間の関係を示す関係データの各観測値を要素として含む入力テンソル上の欠損値を推定する欠損値推定装置における欠損値推定方法であって、曖昧性解消手段によって、前記複数次元の何れかのクラスの背景知識として予め用意されたクラス階層構造であるタクソノミに基づいて、前記入力テンソルの前記観測値に対応する各要素について、前記タクソノミのクラス階層構造の末端クラスの何れかにリンクし、前記末端クラスを含む複数次元の各々のオブジェクト間の関係を示す前記関係データの各観測値を要素として含む曖昧性解消テンソルを作成し、スパース性緩和手段によって、前記曖昧性解消手段によって作成された前記曖昧性解消テンソルに基づいて、前記タクソノミの各末端クラスから、少なくとも１つの観測値に対応する要素に含まれる末端クラスであって、かつ、観測数が所定値未満であるスパースクラスを抽出し、前記曖昧性解消テンソルの要素のうち、前記抽出されたスパースクラスを用いた要素の各々について、前記抽出されたスパースクラスの親クラスを用いて、前記親クラスを含む複数次元の各々のオブジェクト間の関係を示す前記関係データの観測値を要素として含む抽象テンソルを作成し、クラスタリング手段によって、前記曖昧性解消手段によって作成された前記曖昧性解消テンソルに基づいて、前記タクソノミの各末端クラスから、密な観測を持つ末端クラスであるデンスクラスを抽出し、前記抽出されたデンスクラスの各々に対し、前記入力テンソルの要素のうち、前記抽出されたデンスクラスにリンクされる要素の各々を、複数のクラスに分類し、前記分類されたクラスを含む複数次元の各々のオブジェクト間の関係を示す前記関係データの観測値を要素として含むクラスタテンソルを作成し、テンソル拡張手段によって、前記曖昧性解消手段によって作成された前記曖昧性解消テンソル、前記スパース性緩和手段によって作成された前記抽象テンソル、及び前記クラスタリング手段によって作成されたクラスタテンソルを用いた拡張テンソルを計算し、欠損値推定手段によって、前記テンソル拡張手段によって拡張された拡張テンソルを、テンソル分解法により分解及び復元することで、前記拡張テンソルにおける未観測値の要素を推定し、前記推定した前記拡張テンソルにおける未観測値の要素に基づいて、前記入力テンソル上の欠損値を推定する。
【００１４】
本発明に係るプログラムは、上記の欠損値推定装置の各手段としてコンピュータを機能させるためのプログラムである。
【発明の効果】
【００１５】
以上説明したように、本発明の欠損値推定装置、方法、及びプログラムによれば、タクソノミの末端クラスを用いた曖昧性解消テンソルを作成し、タクソノミの各末端クラスから、スパースクラスを抽出して親クラスを用いた抽象テンソルを作成し、密な観測を持つデンスクラスを抽出し複数のクラスに分類してクラスタテンソルを作成し、曖昧性解消テンソル、抽象テンソル、及びクラスタテンソルを用いた拡張テンソルを計算し、拡張テンソルにおける未観測値の要素を推定することにより、入力テンソル上の欠損値を精度よく推定することができる、という効果が得られる。
【図面の簡単な説明】
【００１６】
【図１】本発明の第１の実施の形態に係る欠損値推定装置の構成を示す概略図である。
【図２】（Ａ）曖昧性を解消する処理を説明するための図、及び（Ｃ）クラスタリング処理を説明するための図である。
【図３】本発明の第１の実施の形態に係る欠損値推定装置における欠損値推定処理ルーチンの内容を示すフローチャートである。
【発明を実施するための形態】
【００１７】
以下、図面を参照して本発明の実施の形態を詳細に説明する。
【００１８】
＜概要＞
まず、本発明の概要について説明する。
【００１９】
複数次元のオブジェクト間の関係を表現するテンソルを分析し、有用な関係集合などを抽出するテンソル分析においては、各次元をクロスしたオブジェクト間の取りうる関係の数が非常に多いが、観測されているデータ数は少なく、その場合、分析の結果に悪影響を与えることがわかっている。そこで、本発明では、そうした関係を予測するという、テンソル分析の精度向上のための、テンソル上の欠損値の予測を扱う。
【００２０】
タグの背景知識であるタグのタクソノミを用い、ユーザ、タグ、アイテムではなく、ユーザ、クラス、アイテムという関係のテンソルを構築する。また、クラスの関係における、クラスの粒度を調整することで、ユーザ、クラス、アイテムの取り得るパターンの数を減らしたテンソルを構築し、テンソルがスパースになることを防ぐことも行う。クラスは同種のアイテムを纏めているため、語彙が異なるが同じ意味のものを纏める効果がある。また、密なクラスに対してクラスタリングを行って、詳細なクラスを用いたユーザ、クラス、アイテムの関係のテンソルを構築する。これらのテンソルを統合することにより、元のテンソルにバイアスを与え、新たなテンソルに拡張した上で、テンソル分解を実施する。これにより、タグの背景知識を用い、疎なテンソルを密にすることができ、また、タグの曖昧性を回避しているため、結果として、欠損値の予測精度が向上する。また、複数粒度のクラスをテンソル上に同時に混入させることで詳細なクラスを用いて詳細なユーザ、アイテム、クラスの関係を学習しつつ、簡素なクラスを用いて粗いユーザ、アイテム、クラスの関係も学習し、両者の良い点を補完する。
【００２１】
本実施の形態では、テンソル分解の代表的手法である、BPTF（上記非特許文献２を参照）を用い、BPTFへ入力するデータの構築法を与える。オントロジとは、機械が参照可能な概念辞書の事を指すが、そのコア技術がタクソノミである。本実施の形態で用いるタクソノミは、同種のタグ集合から定義されるクラスとそのクラスの階層からなる。また末端クラスのみにタグが存在する、という制約を持つ。本実施の形態におけるセマンティクスとは、同種のタグ集合から定義されるクラ、及びクラスの階層から得られる、タグの持つ特性の事を指す。
【００２２】
本実施の形態において、複数オブジェクト間の関係の例として、ユーザui、アイテムvj、タグtk 間の関係を用いる。テンソルは「^^」を付して^^Rのように記される。行列は、「＾」を付して＾Rと記される。ベクトルは、「＾」を付して＾rと記される。^^Rは、＾U、＾V、＾T間の関係から構築され、集合~U、~V、~T 間の関係からなる。(i, j, k)要素は^^Ri,j,kと記され、ｉ番目のユーザの、ｊ番目のアイテムのｋ番目のタグを伴う評点を格納する。テンソルのタグkに関する展開は、＾Rk = ^^R:,:,kと記される。
【００２３】
［第１の実施の形態］
＜システム構成＞
図１は、本発明の第１の実施の形態に係る欠損値推定装置１００の模式図の一例である。欠損値推定装置１００は、ＣＰＵと、ＲＡＭと、後述する欠損値推定処理ルーチンを実行するためのプログラムを記憶したＲＯＭとを備えたコンピュータで構成され、機能的には、欠損値推定装置１００は、入力部１０と、演算部２０と、出力部３０と、を備えている。
【００２４】
入力部１０は、複数次元の各々のオブジェクト間（ユーザ、アイテム、タグ間）の関係の観測値の集合の入力を受け付けると共に、各観測値に対する関係データ（評点）の入力を受け付ける。
【００２５】
演算部２０は、テンソル構築部２１、タクソノミ記憶部２２、曖昧性解消部２３、スパース性緩和部２４、クラスタリング部２５、テンソル拡張部２６、及び欠損値推定部２７を備えている。
【００２６】
テンソル構築部２１は、入力された各観測値に対する評点を取得し、ユーザｉ、アイテムｊ、タグｋの３次元のオブジェクト間の関係の各観測値に対する評点を各要素として含む入力テンソル^^Rを構築する。
【００２７】
タクソノミ記憶部２２は、タグの背景知識として予め用意されたタグのクラス階層構造であるタクソノミを記憶している。タクソノミは、DBPedia（登録商標）やwordNet（登録商標）を利用する事もできるし、タグがあるサービスプロバイダ内で管理されているとすると、そのプロバイダの提供するタクソノミを利用することもできる。本実施の形態では、タクソノミは事前に用意されているものとし、タグはその末端クラスに分類されているものとする。末端クラスの集合を~Cと記す。
【００２８】
＜曖昧性解消部＞
既存の研究(上記非特許文献３)では、様々な意味を持つタグの曖昧性を解消しないまま、テンソル分解を実施する。しかし、実際にはそのような曖昧性を持つタグが多く存在する。例えば、“Classical”というタグは、“Beatles”というアーチストにも良く与えられる。また、“Bach”や“Wargber”といったアーチストにも“Classical”というタグは頻繁に与えられる。しかし、“Bach”や“Wargber”は“Beatles”とは異なる種類のアーチストである。こうしたタグの曖昧性を解消しないまま、テンソル分解を行うと、その予測精度は悪くなる。そこで、本実施の形態では、曖昧性解消部２３は、テンソル構築部２１によって構築された入力テンソル及びタクソノミ記憶部２２に記憶されているタクソノミに基づいて、テンソル分解を行う前にタグの曖昧性を解消する。
【００２９】
タグの曖昧性は、タグのタクソノミを用い解消する。アイテムvjに付与されているタグtk の曖昧性を解消する曖昧性解消関数を以下の（１）式のように定義する。
【００３０】
【数１】
2014164612.tif 000003
【００３１】
上記（１）式は、タグが付与されているアイテムとの関係を見て、タグの曖昧性を解消しているという事を意味する。
【００３２】
具体的には、タクソノミから、タグｔkと同じ名前属性を持つ末端クラスを候補として取得し、入力されたユーザ、アイテム、及びタグ間の関係の観測値の集合に基づいて、各末端クラスの候補について、当該候補の親クラスｃpの名前属性と一致するタグが、アイテムｖjに割り当てられる頻度を計算し、最も頻度の高い親クラスｃpを選択し、親クラスｃpに所属する末端クラスの候補を、曖昧性を解消したクラスｃlとして出力する。
【００３３】
なお、以下の式のように、タグのみを見て、末端クラスclにリンクさせてもよい。
【００３４】
【数２】
2014164612.tif 000004
【００３５】
この場合には、別途用意した辞書データなどを用いて、タグｔkが割り当てられる頻度が最も高い末端クラスを、曖昧性を解消したクラスｃlとして出力する。
【００３６】
また、末端クラスclの親クラスcp を返却する関数を以下のように定義する。
【００３７】
【数３】
2014164612.tif 000005
【００３８】
上記関数の、詳細な実装は、タグデータやタクソノミの各データセットに応じて異なる。
【００３９】
上述した（１）式の関数を用いて、曖昧性解消部２３は、テンソル構築部２１によって構築された入力テンソルの、観測値に対応する各要素について、当該要素のタグをタクソノミ上の末端クラスにリンクし、タグの曖昧性を解消する（図２（A）参照）。
【００４０】
関数を用いて曖昧性を解消した後、タグ集合~T に含まれるタグによりリンクされる末端クラスからなるクラスセット~Cを獲得する事ができる。次に、曖昧性解消部２３は、入力テンソル^^Rに基づいて、曖昧性を解消したテンソル^^Rdを、cl=ｇ(vj,tk)という条件下において、以下の式に基づき作成する。
【００４１】
【数４】
2014164612.tif 000006
【００４２】
曖昧性解消テンソル^^Rdの(i, j, l)要素、^^Rdi,j,lは、i番目のユーザとj番目のアイテムと、k番目のタグによりリンクされるl番目の末端クラスとに対する要素（評点）を示す。
【００４３】
＜スパース性緩和部＞
BPTFは、観測された評点のみからテンソル分解により未観測の評点の予測分布を計算する。しかし、テンソル分解のスパース問題に有用であるならば、タグのタクソノミから得られる補助情報を用いたモデルが望ましい。推薦に関する研究でアイテムのタクソノミを用いる事がスパース問題に有用であるという知見（非特許文献４：Makoto Nakatsuji, Yasuhiro Fujiwara, Akimichi Tanaka, Toshio Uchiyama, Ko Fujimura, and Toru Ishida. Classical music for rock fans?: novel recommendations for expanding user interests. In Proc. CIKM ’10, pages 949958, 2010.）に触発され、本実施の形態では、スパース性緩和部２４は、曖昧性解消部２３によって作成された曖昧性解消テンソル^^Ｒdに基づいて、^^Rdの末端クラスをその親クラスに抽象化する事で構築される抽象テンソル^^Raを作成する。結果として、^^Rdにおいて観測されている末端クラスの親クラスにバイアスを掛け、未観測の評点の予測分布を計算できる。特に^^Rdのエントリ（要素）において、あまり観測されない、スパースな末端クラスに焦点をあてて、抽象テンソル^^Raを作成する。
【００４４】
親クラスcp 配下の末端クラス集合は以下の（４）式で計算できる。
【００４５】
【数５】
2014164612.tif 000007
【００４６】
本実施の形態では、まず親クラスcp 配下において、あまり観測されていないスパースなクラスcsを~Cplを用い計算する。親クラスcp 配下のスパースなクラス集合~Cpsは、以下の式で計算される。
【００４７】
【数６】
2014164612.tif 000008
【００４８】
ここで、med(~Cpl)という関数は、親クラスcp に含まれる全末端クラスの観測数の中間値を返す。全親クラス集合~Cpに対し、上記式を適用し得られたスパースクラス集合を~Csと記す。本実施の形態では、~Csから各スパースクラスcsを取り出し、上記（２）式で定義された関数f(cs)により、抽象クラスca を計算する。そして、次に、^^Rdに存在する、スパースクラスcs を含む観測値に対応する各要素からなり、ユーザ集合~U、アイテム集合~V、抽象クラス集合~Ca間の関係をモデリングする抽象テンソル^^Raを作成する。具体的には、^^Rdにおけるユーザuのアイテムiに対するスパースクラスcsに対する評点を用いて、ca = f(cs) という条件下において、ユーザu のアイテムiに対する抽象クラスcaに対する評点を以下の式のようにセットすることにより、抽象テンソル^^Raを作成する。
【００４９】
【数７】
2014164612.tif 000009
【００５０】
^^Rai,j,aの(i, j, a) 要素は、i番目のユーザとj番目のアイテムとa番目の抽象クラス（ｌ番目の末端クラスの親クラス）とに対する要素（評点）を示す。
【００５１】
本実施の形態では、^^Rdの要素においてスパースに観測されるクラスにバイアスを掛ける事により、そうしたスパースに観測されるクラスに起因するスパース問題を解決し、結果として、抽象テンソル^^Raを用いテンソル分解の予測精度を向上できる。
【００５２】
＜クラスタリング部＞
情報抽出や推薦にタクソノミを用いる既存研究（上記非特許文献４参照）においては、タクソノミの粒度が細かい程、予測精度がよくなることが指摘されている。本実施の形態においては、^^Rdにおいて頻繁に観測されているクラスは、粒度が粗いクラスである可能性があり、結果として、予測精度を下げる傾向がある。例えば、“acoustic”という親クラス配下の“melancholic”は、^^Rdにおいて頻繁に観測されているとする。また、“Kate Winslet”というアイテムは、“acoustic”という親クラス配下の“melancholic”にリンクされるタグ、および“british”という親クラス配下の“rock”にリンクされるタグを持つとする。また、“Gustavo Santaolalla”というアイテムは、“acoustic”という親クラス配下の“melancholic”にリンクされるタグおよび“world”という親クラス配下の“latin”にリンクされるタグを持つとする。上記２つのアイテムは種類の異なるアイテムであるため、上記“melancholic”というクラスはより詳細化できると考えられる。そこで、タクソノミ以外に、上記アイテムを分類する事のできる方法を必要とする。
【００５３】
そこで、本実施の形態では、クラスタリング部２５は、曖昧性解消テンソル^^Rdに基づいて、密な観測を持つデンスクラスcdの集合~Cdを以下の式で抽出する。
【００５４】
【数８】
2014164612.tif 000010
【００５５】
次に、クラスタリング部２５は、デンスクラスの集合~Cdに含まれる各デンスクラスｃdについて、当該デンスクラスｃdにリンクされているタグをクラスタリングする。
【００５６】
本実施の形態では、K-means algorithm（非特許文献５（［インターネット検索］http://en.wikipedia.org/wiki/K-means_clustering）参照）を用い、タグをマシンドリブンクラス(K-meansにおけるクラスタ)にクラスタリングする。クラスタリングにおいて、本実施の形態ではタグが与えられたアイテムをタグの属性として用いる。クラスタリング部２５は、タグをクラスタリングした後、マシンドリブンクラスcmを用いクラスタテンソル^^Rmを作る（図２（B）参照）。具体的には、入力テンソル^^Rにおいて、ユーザuiと、アイテムvjと、マシンドリブンクラスcmに分類され、かつ、デンスクラスcdにリンクされたタグtkとに対する要素（評点）を、ユーザuiとアイテムvjとマシンドリブンクラスcmとに対する要素（評点）として以下の式のようにセットして、クラスタテンソル^^Rmを作成する。
【００５７】
【数９】
2014164612.tif 000011
【００５８】
この^^Rmは、^^Rdにおいて頻度高く観測されるクラスに対し、マシンドリブンクラスを用いバイアスを与える事で、テンソル分解の精度をあげる事ができる。
【００５９】
＜テンソル拡張部＞
テンソル拡張部２６は、曖昧性解消部２３で作成した曖昧性解消テンソル^^Rd、スパース性緩和部２４で作成した抽象テンソル^^Ra、及びクラスタリング部２５で作成したクラスタテンソル^^Rmを用い、拡張テンソル^^Re を以下の式で計算する。
【００６０】
【数１０】
2014164612.tif 000012
【００６１】
上記（９）式では、タクソノミの末端クラス集合~Cのうち、デンスクラスでない末端クラスｃeの各々について、末端クラスｃeに関する要素の各々を、曖昧性解消テンソル^^Rdから取り出して、拡張テンソル^^Reの対応する要素の各々として設定する。また、末端クラスの親クラス集合~Cpに含まれる親クラスｃeの各々について、親クラスｃeに関する要素の各々を、抽象テンソル^^Raから取り出して、拡張テンソル^^Reの対応する要素の各々として設定する。また、マシンドリブンクラス集合~Cmに含まれるマシンドリブンクラスｃeの各々について、マシンドリブンクラスｃeに関する要素の各々を、クラスタテンソル^^Rmから取り出して、拡張テンソル^^Reの対応する要素の各々として設定する。
【００６２】
なお、上記式の定義以外に、以下のように拡張テンソルを計算する方法もある。この方法は、テンソルのサイズを増やさずに、スパースクラスやデンスクラスに関してのみ、ク
【００６３】
ラスをアブストラクトクラスやマシンドリブンクラスに置き換えるというものである。
【００６４】
【数１１】
2014164612.tif 000013
【００６５】
上記（１０）式では、タクソノミの末端クラス集合~Cのうち、デンスクラスでもスパースクラスでもない末端クラスｃeの各々について、末端クラスｃeに関する要素の各々を、曖昧性解消テンソル^^Rdから取り出して、拡張テンソル^^Reの対応する要素の各々として設定する。また、スパースクラス集合~Csに含まれるスパースクラスｃsの各々の親クラスｃeの各々について、当該親クラスｃeに関する要素の各々を、抽象テンソル^^Raから取り出して、拡張テンソル^^Reの対応する要素の各々として設定する。また、マシンドリブンクラス集合~Cmに含まれるマシンドリブンクラスｃeの各々について、マシンドリブンクラスｃeに関する要素の各々を、クラスタテンソル^^Rmから取り出して、拡張テンソル^^Reの対応する要素の各々として設定する。
【００６６】
上記（９）式の拡張テンソルと、上記（１０）式の拡張テンソルとは、データセットに応じて、使い分けて利用すれば良い。
【００６７】
＜欠損値推定部＞
欠損値推定部２７は、テンソル拡張部２６によって計算された拡張テンソル^^Reに対し、テンソル分解法（BPTF）を用いて、テンソルを分解及び復元することで、拡張テンソルの未観測のデータに対応する要素である欠損値を推定し、拡張テンソルにおける欠損値の推定結果から、入力テンソルの未観測のデータに対応する要素である欠損値を抽出し、出力部３０により出力する。本実施の形態では、曖昧性を除去しつつ、スパースクラスcs やデンスクラスcdを用い、通常のBPTFよりも精度よくテンソル分解を実施できる。
【００６８】
具体的には、上記非特許文献１に記載の式(3.15)の^^Rの代わりに^^Reを代入した、以下の式に示す評点の予測分布に基づいて、拡張テンソルの未観測のデータに対する欠損値（評点）^^R’ei,j,kの各々を推定する。
【００６９】
【数１２】
2014164612.tif 000014
【００７０】
＜欠損値推定装置の動作＞
次に、第１の実施の形態に係る欠損値推定装置１００の作用について説明する。まず、ユーザ、アイテム、及びタグ間の関係の観測値の集合の入力を受け付けると共に、各観測値に対する関係データ（評点）が、入力部１０を介して欠損値推定装置１００に入力されると、欠損値推定装置１００において、図３に示す欠損値推定処理ルーチンが実行される。
【００７１】
まず、ステップＳ１０１において、入力部１０により入力された、ユーザ、アイテム、及びタグ間の関係の観測値の集合と、各観測値に対する関係データ（評点）とに基づいて、ユーザ、アイテム、及びタグ間の関係に対する関係データ（評点）を各要素とする入力テンソル^^Ｒを構築する。
【００７２】
次のステップＳ１０２では、タクソノミ記憶部２２から、タグのクラス階層構造であるタクソノミを読み込む。ステップＳ１０３において、上記ステップＳ１０１で構築した入力タクソノミの観測値に対応する各要素について、上記（１）式に従って、当該要素のタグを、上記ステップＳ１０２で読み込んだタクソノミの末端クラスにリンク付けし、上記（３）式に従って、ユーザ、アイテム、及び末端クラス間の関係に対する関係データ（評点）を各要素とする曖昧性解消テンソル^^Ｒdを作成する。
【００７３】
そして、ステップＳ１０４では、上記ステップＳ１０３で作成した曖昧性解消テンソル^^Ｒdに基づいて、上記（５）式に従って、スパースなクラス集合~Ｃsを抽出する。ステップＳ１０５では、上記ステップＳ１０３で作成した曖昧性解消テンソル^^Ｒdと、上記ステップＳ１０４で抽出されたスパースなクラス集合~Ｃsとに基づいて、上記（６）式に従って、ユーザ、アイテム、及び親クラス間の関係に対する関係データ（評点）を各要素とする抽象テンソル^^Ｒaを作成する。
【００７４】
そして、ステップＳ１０６では、上記ステップＳ１０３で作成した曖昧性解消テンソル^^Ｒdに基づいて、上記（７）式に従って、デンスクラス集合~Ｃdを抽出する。ステップＳ１０７では、上記ステップＳ１０６で抽出したデンスクラス集合~Ｃdのデンスクラスｃdの各々について、当該デンスクラスｃdにリンクされているタグに対してクラスタリングを行って、複数のマシンドリブンクラスに分類する。
【００７５】
次のステップＳ１０８では、上記ステップＳ１０１で構築した入力テンソル^^Ｒと、上記ステップＳ１０７におけるデンスクラス集合~Ｃdのデンスクラスｃdの各々についてのクラスタリング結果とに基づいて、上記（８）式に従って、ユーザ、アイテム、及びマシンドリブンクラス間の関係に対する関係データ（評点）を各要素とするクラスタテンソル^^Ｒmを作成する。
【００７６】
そして、ステップＳ１０９において、上記ステップＳ１０３で作成した曖昧性解消テンソル^^Ｒdと、上記ステップＳ１０５で作成した抽象テンソル^^Ｒaと、上記ステップＳ１０８で作成したクラスタテンソル^^Ｒmと、に基づいて、上記（９）式又は（１０）式に従って、拡張テンソル^^Ｒeを計算する。
【００７７】
次のステップＳ１１０では、上記ステップＳ１０９で計算された拡張テンソル^^Ｒeに基づいて、上記（１１）式に従って、拡張テンソル^^Ｒeの欠損値の各々を推定する。そして、ステップＳ１１１において、上記ステップＳ１１０で推定された拡張テンソル^^Ｒeの欠損値から、上記ステップＳ１０１で構築された入力テンソル^^Rの欠損値を抽出し、出力部３０により出力して、欠損値推定処理ルーチンを終了する。
【００７８】
以上説明したように、本発明の第１の実施の形態に係る欠損値推定装置によれば、ユーザ、アイテム、及びタグの関係の観測値と各観測値の関係に対する評点とに基づいて、タグを、タクソノミの末端クラスにリンクさせて、ユーザ、アイテム、及び末端クラスの関係を示す要素からなる曖昧性解消テンソルを作成する。タクソノミの各末端クラスからスパースクラスを抽出し、スパースクラスの親クラスを用いて、ユーザ、アイテム、及び親クラスの関係を示す要素からなる抽象テンソルを作成する。密な観測を持つデンスクラスを抽出しデンスクラスにリンクするタグを複数のマシンドリブンクラスに分類して、ユーザ、アイテム、及びマシンドリブンクラスの関係を示す要素からなるクラスタテンソルを作成する。曖昧性解消テンソル、抽象テンソル、及びクラスタテンソルを用いた拡張テンソルを計算し、拡張テンソルにおける未観測値の要素を推定することにより、入力テンソル上の欠損値を精度よく推定することができる。
【００７９】
また、クラスの背景知識を活用し、テンソル分解に基づく欠損値の予測精度を向上させる。広く普及するmatlab(登録商標)のtensor tool box など既存のツールとの相性もよく、簡易に精度を上げることができるため、今後の産業面での活用が期待できる。
【００８０】
[第２の実施の形態]
＜システム構成＞
次に、第２の実施の形態に係る欠損値推定装置について説明する。なお、第２の実施の形態に係る欠損値推定装置の構成は、第１の実施の形態と同様であるため、同一符号を付して説明を省略する。
【００８１】
第２の実施の形態では、個人ユーザの商品及び商品消費コンテクストの組み合わせに対する消費頻度からなるユーザの消費履歴を用いて、テンソルを構築し、テンソルの欠損値を推定することにより、ユーザが関心を持ち得る推薦商品を予測している点が、第１の実施の形態と異なっている。
【００８２】
第２の実施の形態に係る欠損値推定装置の入力部１０は、個人ユーザ、商品、及び商品消費コンテクストの各次元のオブジェクト間の関係の観測値の集合の入力を受け付けると共に、各観測値に対する関係データ（消費頻度）としての、個人ユーザの商品及び商品消費コンテクストの組み合わせに対する消費頻度からなるユーザの消費履歴の入力を受け付ける。
【００８３】
テンソル構築部２１は、入力された各観測値に対する消費頻度を取得し、ユーザ、商品、商品消費コンテクストの３次元のオブジェクト間の関係の観測値に対する消費頻度を各要素として含む入力テンソルを構築する。
【００８４】
タクソノミ記憶部２２は、商品の背景知識として予め用意された商品のクラス階層構造であるタクソノミを記憶している。タクソノミは、FreeBase(登録商標)、WikiPedia（登録商標）、商品販売元の品番情報等の情報源から得られる商品のクラス階層構造を利用することができる。
【００８５】
曖昧性解消部２３は、テンソル構築部２１によって構築された入力テンソルの、観測値に対応する各要素について、当該要素の商品をタクソノミ上の末端クラスにリンクし、商品の曖昧性を解消する。
【００８６】
欠損値推定部２７は、テンソル拡張部２６によって計算された拡張テンソルに対し、テンソル分解法（BPTF）を用いて、テンソルを分解及び復元することで、拡張テンソルの未観測のデータに対する欠損値を推定し、拡張テンソルにおける欠損値の推定結果から、入力テンソルの欠損値を抽出し、入力テンソルの欠損値に基づいて、各ユーザが関心を持ち得る推薦商品を予測し、出力部３０により出力する。
【００８７】
なお、第２の実施の形態に係る欠損値予測装置の他の構成及び作用については、第１の実施の形態と同様であるため、説明を省略する。
【００８８】
このように、ユーザ、商品、及び商品消費コンテクストの関係の観測値と各観測値に対する消費頻度とに基づいて、商品を、タクソノミの末端クラスにリンクさせて、ユーザ、商品クラス、及び商品消費コンテクストの関係を示す要素からなる曖昧性解消テンソルを作成する。タクソノミの各末端クラスからスパースクラスを抽出して、スパースクラスの親クラスを用いて、ユーザ、親クラス、及び商品消費コンテクストの関係を示す要素からなる抽象テンソルを作成する。密な観測を持つデンスクラスを抽出しデンスクラスにリンクする商品を複数のマシンドリブンクラスに分類して、ユーザ、マシンドリブンクラス、及び商品消費コンテクストの関係を示す要素からなるクラスタテンソルを作成する。曖昧性解消テンソル、抽象テンソル、及びクラスタテンソルを用いた拡張テンソルを計算し、拡張テンソルにおける未観測値の要素を推定することにより、入力テンソル上の欠損値を精度よく推定し、ユーザが関心を持ち得る推薦商品を精度よく予測することができる。
【００８９】
なお、本発明は、上述した実施形態に限定されるものではなく、この発明の要旨を逸脱しない範囲内で様々な変形や応用が可能である。
【００９０】
例えば、予め構築された入力テンソルが、欠損値推定装置に入力されてもよい。
【００９１】
また、上述の欠損値推定装置は、内部にコンピュータシステムを有しているが、「コンピュータシステム」は、ＷＷＷシステムを利用している場合であれば、ホームページ提供環境（あるいは表示環境）も含むものとする。
【００９２】
また、本願明細書中において、プログラムが予めインストールされている実施形態として説明したが、当該プログラムを、コンピュータ読み取り可能な記録媒体に格納して提供することも可能である。
【符号の説明】
【００９３】
１０   入力部
２０   演算部
２１   テンソル構築部
２２   タクソノミ記憶部
２３   曖昧性解消部
２４   スパース性緩和部
２５   クラスタリング部
２６   テンソル拡張部
２７   欠損値推定部
３０   出力部
１００ 欠損値推定装置
【図１】
2014164612.tif 000015
【図２】
2014164612.tif 000016
【図３】
2014164612.tif 000017