JP6535355B2 - テンソル因子分解処理装置、テンソル因子分解処理方法及びテンソル因子分解処理プログラム - Google Patents

Description

本発明は、データマイニング技術、特に、複数の属性情報から要因パターンを抽出する因子分解に関する技術、具体的には非負値複合テンソル因子分解の技術に関する。

複数の属性情報から要因パターンを抽出する技術として、非負値テンソル因子分解及び非負値複合テンソル因子分解と呼ばれる技術がある（非特許文献１）。これらの技術には、高速化技術が提案されており、スパーステンソルに対して高速に処理することができる（特許文献１）。

さらに、非負値テンソル因子分解の応用として、属性情報の一部が欠損している場合、この欠損値を補完する非負値テンソル補完と呼ばれる技術がある（非特許文献２）。非負値テンソル補完は、目的こそ異なるが、非負値テンソル因子分解において欠損値に関する処理を追加したものであるといえる。

Koh Takeuchi , Ryota Tomioka , Katsuhiko Ishiguro , Akisato Kimura , and Hiroshi Sawada ," Non-negative Multiple Tensor Factorization ", ICDM , 2013 , 1199-1204 竹内孝，納谷太，上田修功，「一般化ＫＬダイバージェンスを用いた非負テンソル補完と交通流解析への応用」，Proceedings of DEIM Forum, 2016 H7-2

特開２０１６−１３９３９１号公報

従来の高速化技術（特許文献１）は、非負値テンソルが「０値スパーステンソル」または「欠損値スパーステンソル」のいずれかである場合に適用できる高速化技術である。「０値スパーステンソル」は、欠損値のない非負値テンソルである。「欠損値スパーステンソル」は、欠損値のある非負値テンソルの欠損値を値が「０」である要素（ゼロ要素）として表現したものである。この技術では、観測値としての「０」と欠損値とを一つのテンソル内で同時に表現することができない。したがって、非負値（複合）テンソル補完の内部で用いる非負値（複合）テンソル因子分解を高速に処理するためには、以下の課題がある。

上記の従来の高速化技術を欠損値のあるテンソルに適用するためには、事前に欠損値をゼロ要素で置き換えたうえで、すべてのゼロ要素を欠損値として扱わなければならず、元のテンソルに欠損値ではないゼロ要素が存在すると計算結果が不正確になる。

一方、上記の従来の高速化技術を用いずに正確な計算を行おうとすると、同程度の規模で欠損値のないテンソルの因子分解と比べて計算時間が増大する。

本発明は、上記の事情に鑑み、非負値テンソル因子分解の高速化と計算精度の向上を図ることを課題とする。

そこで、本発明の一態様は、非負値テンソルの因子分解処理を行うテンソル因子分解処理装置であって、特定の事象の複数の属性情報に対応した値を要素とする前記テンソルを構築し、前記属性情報が欠損している要素の値を示す、ゼロ要素と区別できる欠損値を、負の値に置換するテンソル構築手段と、前記テンソルの因子行列の要素を乱数で初期化する初期化手段と、前記初期化された因子行列の要素を、二つのテンソル間の距離の指標である一般化ＫＬダイバージェンスに基づく更新式によって更新する行列更新手段と、前記要素が更新された因子行列から推定されるテンソルと元のテンソルとの距離として前記一般化ＫＬダイバージェンスを算出し、この距離が予め設定された前記更新の終了条件を満たしている場合または当該更新の計算回数が予め設定された上限に達している場合には当該更新を終了させる一方で当該距離が当該終了条件を満たさない場合には当該更新を継続させる計算終了評価手段とを備える。

また、本発明の一態様は、非負値テンソルの因子分解処理を行うテンソル因子分解処理装置が実行するテンソル因子分解処理方法であって、
特定の事象の複数の属性情報に対応した値を要素とする前記テンソルを構築し、前記属性情報が欠損している要素の値を示す、ゼロ要素と区別できる欠損値を、負の値に置換するテンソル構築ステップと、
前記テンソルの因子行列の要素を乱数で初期化する初期化ステップと、
前記初期化された因子行列の要素を、二つのテンソル間の距離の指標である一般化ＫＬダイバージェンスに基づく更新式によって更新する行列更新ステップと、
前記要素が更新された因子行列から推定されるテンソルと元のテンソルとの距離として前記一般化ＫＬダイバージェンスを算出し、この距離が予め設定された前記更新の終了条件を満たしている場合または当該更新の計算回数が予め設定された上限に達している場合には当該更新を終了させる一方で当該距離が当該終了条件を満たさない場合には当該更新を継続させる計算終了評価ステップと
を有する。

前記行列更新手段及び前記行列更新ステップの一態様は、前記テンソルの要素が負の値であると当該要素は当該テンソルの欠損値であると判断して前記一般化ＫＬダイバージェンスに基づく当該要素の分母の補正値を前記更新式の分母の補正値に加算することにより当該更新式を補正する。

前記テンソル構築手段及びテンソル構築ステップの一態様は、前記構築の際に前記テンソルをより低階の部分テンソルに変換して非ゼロ要素または欠損値の要素を列挙可能とする。

尚、本発明は、上記装置を構成する各手段としてコンピュータを機能させるプログラム若しくは上記方法の各ステップをコンピュータに実行させるテンソル因子分解処理プログラムの態様とすることもできる。

以上の本発明によれば、非負値テンソル因子分解の高速化と計算精度の向上が図られる。

（ａ）は本発明の実施形態におけるテンソル因子分解処理装置のブロック構成図、（ｂ）は同装置におけるテンソル分解部のブロック構成図。 （ａ）ログデータに基づくテンソルの一例を示した構成図、（ｂ）は当該テンソルの欠損値情報を例示した一覧表。 テンソルを構築する過程を説明したフローチャート。 テンソルの圧縮形式を例示した説明図。 テンソルの因子行列を初期化する過程を説明したフローチャート。 テンソルの因子行列を更新する過程を説明したフローチャート。

以下、図面を参照しながら本発明の実施の形態について説明するが本発明はこの実施形態に限定されるものではない。

［概要］
図１に例示のテンソル因子分解処理装置１は、非負値テンソル因子分解の高速化技術を拡張してゼロ要素と区別できる欠損値の表現を導入する。すなわち、本来のテンソルの要素が０以上であることを利用して、テンソルの欠損値を負の値の要素として表現することにより、一度のデータ走査で観測値と欠損値の処理をまとめて行う。また、テンソルの更新式の分母について、先ず、不正確であるが高速に計算できる概算値を算出し、その後、補正値を計算することにより、計算精度が確保される。そして、補正値の算出のためのデータ走査を前記更新式の分子の計算と一括して行うことにより、補正値の高速計算が実現する。

［技術用語の説明］
本実施形態の説明にあたり、本実施形態に関連する技術用語について説明する。

属性情報とは、特定の事象を一つ以上の属性の組合せとこの組合せに対応する値で表したものである。例えば、人々が商店を訪れたことの属性情報は、例えば、ユーザＩＤ，店ＩＤ，曜日の３つの属性と、これらの属性に対応する訪問回数や滞在時間とで表すことができる。尚、属性情報は、各属性をモードとみなすことでテンソルとして表すことができる。

テンソルとは、本実施形態においては多次元の配列と同義である。例えば、３階のテンソルは３次元配列として表現できる。但し、非負値テンソルとは、テンソルの全ての要素が０以上であるテンソルを示す。

モードとは、テンソルの軸を指す。例えば、行列は２階のテンソルとみなせるが、このとき行方向と列方向の２つのモードがある。

因子行列とは、非負値テンソルを因子分解することで得られる行列であり、モードと同じ数だけ存在する。

欠損値とは、テンソルの要素のうち、その値が不明なものを示す。テンソルに欠損値が含まれる要因としては、例えば、複数のセンサの状態を一定期間収集したデータにおいて、特定のセンサが特定の期間に故障しており、当該データの値が不明な場合が挙げられる。欠損値は、観測値としての「０」とは区別される。観測値としての「０」とは、例えば、特定のセンサが特定の期間に正常に稼働していた上で何も観測しなかった場合に「０」を出力するような場合に対応する。

［装置の構成例］
テンソル因子分解処理装置１は、入力データ記憶部１０，テンソル構築部１１，テンソル分解部１２，欠損値推定部１３，出力データ記憶部１４を備える。

入力データ記憶部１０は、因子分解及び欠損値の推定を行う対象の非負値テンソル（以下、テンソルと称する）と、各テンソルの欠損値の位置を示す欠損値情報と、因子分解で用いるパラメータを保存している。これらの情報は入力データ記憶部１０に予め保存されているものとする。

図２は入力データ記憶部１０に保存されているテンソルとその欠損値情報の一例を示す。本事例のテンソルは３階テンソルであり、３つのモードは「ユーザＩＤ」「曜日」「店ＩＤ」という３つの属性情報に対応している。テンソルの要素は属性情報の組に対応する値を表現している。例えば、「ユーザ２」が「月曜」に「店３」に「４回」訪問した、という情報をテンソルの要素として表現できる。テンソルは非特許文献１の技術により複数個あってもよい。欠損値情報は、対応するテンソルのどの要素が欠損しているかを示す。

テンソル構築部（テンソル構築手段）１１は、予め、特定の事象の複数の属性情報をモードとするテンソルを構築する。前記テンソルは入力データ記憶部１０に保存される。そして、テンソル構築部１１は、入力データ記憶部１０から前記テンソルを引き出し、このテンソルの因子分解の際に効率的に走査可能な形式に変換する。具体的には、前記引き出されたテンソルよりも低階のテンソルである部分テンソルに変換し、その要素のうちゼロでない要素（非ゼロ要素）を並べた形で主記憶に展開する。尚、テンソル内の要素に欠損値があるときは、当該要素の値を任意の負の値に置換し、これを非ゼロ要素として当該テンソルの部分テンソルに加える。詳細な処理は後述する。

テンソル分解部１２は、テンソル構築部１１により得られたテンソルの因子分解を行う。詳細な処理は後述する。

欠損値推定部１３は、テンソル分解部１２により得られたテンソルの因子行列に基づき当該テンソルの欠損値を推定する。

出力データ記憶部１４は、欠損値推定部１３により得られた欠損値の推定値を保存する。

また、テンソル分解部１２は、図１（ｂ）に例示されたように、初期化部２０、行列更新部２１及び計算終了評価部２２を備える。

初期化部２０は、テンソル構築部１１により得られたテンソルの因子分解に必要な初期化処理を行う。具体的には前記テンソルの因子行列の要素を乱数で初期化する。詳細な処理は後述する。

行列更新部（行列更新手段）２１は、前記初期化された因子行列の要素をテンソル構築部１１により得られたテンソルとその因子行列から算出されるテンソルの間の距離に基づく更新式により更新する。詳細な処理は後述する。

計算終了評価部２２は、行列更新部２１により更新された因子行列に基づき当該更新の継続を決定する。具体的には、テンソル毎に対応する因子行列からそのテンソルの推定値を計算し、元のテンソルと推定されたテンソルの距離を計算する。但し、欠損値は比較ができないためこの計算の対象外とする。テンソルの距離には、一般化ＫＬダイバージェンスを用いることができる。この距離が予め設定された前記更新の終了条件を満たしている場合または前記更新の計算回数が予め設定された上限に達している場合に当該更新を終了させる。一方、前記距離が前記終了条件を満たさない場合は、前記更新を継続させる。

以上のテンソル因子分解処理装置１の機能部１０〜１４，２０〜２２はコンピュータのハードウェアリソースにより実現される。すなわち、テンソル因子分解処理装置１は、少なくとも演算装置（ＣＰＵ）、記憶装置（メモリ、ハードディスク装置等）、通信インタフェース等のコンピュータに係るハードウェアリソースを備える。そして、これらのハードウェアリソースがソフトウェアリソース（ＯＳ、アプリケーション等）と協働することにより各機能部１０〜１４，２０〜２２が実装される。また、各々のコンピュータに機能部１０〜１４，２０〜２２を各々実装させるようにしてもよい。

［本実施形態のテンソル因子分解の過程］
本実施形態のテンソル因子分解の過程は、以下の「テンソルの構築（Ｓ１００〜Ｓ１０４）」「因子行列の初期化（Ｓ２００〜Ｓ２０２）」「因子行列の更新（Ｓ５００〜Ｓ５０６）」の過程を有する。

（テンソルの構築）
図３を参照しながら本態様のテンソル構築ステップ（Ｓ１００〜Ｓ１０４）について説明する。本過程はテンソル構築部１１により実行される。

Ｓ１００：入力データ記憶部１０からテンソルを引き出す。以降の説明ではテンソルが一つの場合を仮定して説明するが、本装置が処理するテンソル因子分解の問題設定により、テンソルが複数ともなり得る。テンソルが複数の場合、テンソルの個数分だけＳ１００以降の処理を繰り返す。

Ｓ１０１：テンソルの各モードについて、Ｓ１０２以降の処理を行う。全てのモードの処理が終了したときは、処理終了に進む。

Ｓ１０２：対象モードの次元と同じ次元の配列を用意する。例えば、１０×８×６の３階テンソルでは、第１モードについては１０個の要素をもつ配列を、第２モードについては８個の要素をもつ配列を、第３モードについては６個の要素をもつ配列を用意する。

Ｓ１０３：対象モードの各次元について、Ｓ１０４の処理を行う。全ての次元の処理が終了したときは、Ｓ１０１に進む。例えば、１０×８×６の３階テンソルの第１モードを対象モードとするとき、Ｓ１０４は１０回行われる。

Ｓ１０４：対象の次元に対応する部分テンソルを非ゼロ要素に着目した圧縮形式で表現し、その参照を配列の対応する要素にセットする。この圧縮形式としては、Coordinate list （ＣＯＯ）と呼ばれる形式が適用できる。テンソルが３階テンソルであれば、部分テンソルは当該テンソルよりも低階のテンソルである２階テンソル、すなわち、行列となるため、Compressed row storage（ＣＲＳ）と呼ばれる形式も適用できる。但し、本態様では、テンソル内の要素に欠損値があるときは、当該要素の値を任意の負の値に置換し、これを非ゼロ要素として圧縮形式に加える。

図４は、Ｓ１０４の一連の処理の流れを例示したものである。（ａ）は処理対象の３階テンソルである。（ｂ）は、（ａ）を部分テンソル、すなわち、行列の列として表したものである。（ｃ）は、各部分テンソルの圧縮形式の列である。（ｄ）は、部分テンソルに欠損値がないときのＣＯＯ形式及びＣＲＳ形式の例である。（ｅ）は、（ｄ）の部分テンソルのうち１個の要素が欠損値であったときのＣＯＯ形式及びＣＲＳ形式の例であり、当該要素が負の値を持つ非ゼロ要素とみなされることを示している。

（因子行列の初期化）
図５を参照しながら因子行列の初期化の過程（Ｓ２００〜Ｓ２０２）について説明する。本過程はテンソル分解部１２の初期化部２０により実行される。

Ｓ２００：入力データ記憶部１０から本実施形態の因子分解で用いるパラメータとしてランク数を引き出す。

Ｓ２０１：テンソル構築部１１（Ｓ１００〜Ｓ１０４）により得られたテンソルに対応する各因子行列について、Ｓ２０２の処理を実行する。全ての因子行列について処理が終了したときは、処理終了に進む。

Ｓ２０２：対象である前記各因子行列の全ての要素について、０より大きい乱数を代入する。尚、因子行列は、行の大きさを対応するモードの大きさとし、列の大きさをＳ２００で引き出したランク数とする。

（因子行列の更新）
図６を参照しながら本態様の行列更新ステップ（Ｓ５００〜Ｓ５０６）について説明する。本過程はテンソル分解部１２の行列更新部２１により実行される。

Ｓ５００：初期化部２０により初期化された因子行列の各要素について、Ｓ５０１以降の処理を行う。全ての要素について処理が終了したときは、処理終了に進む。

Ｓ５０１：因子行列の要素を更新するための更新式の分母の値について概算値を計算する。更新式は、テンソル間の距離として一般化ＫＬダイバージェンスが用いられる場合、下記の式（１）〜（３）のように示される。

テンソルは簡略化のために１個の３階テンソルと仮定しているが、個数は１以上、階数は２以上の任意の数でよい。この更新式の詳細は非特許文献２で示されている。

尚、テンソルに欠損値がない、すなわち、全ての要素は観測値であると仮定してこの更新式を展開すると、上記の式（４）のようになる。この更新式の詳細は、テンソルが複数個である場合も含めて非特許文献１で示されている。

上記の式（１）における分母の値は、テンソルに欠損値がないと仮定すれば上記の式（５）のような式変形により高速に計算することができる。しかし、欠損値がある場合、前記分母の値は欠損値が多いほど不正確になるため、本態様ではこれを概算値と称する。

Ｓ５０２：テンソルの対応する要素を走査し、各要素についてＳ５０３以降の処理を行う。全ての要素について処理が終了したときは、Ｓ５０６に進む。

対応する要素とは、上記の式（１）の構造からわかるとおり、更新する因子行列に対応するモードのインデックスを固定し、残りのモードの全てのインデックスを任意としたときの非ゼロ要素集合である。例えば、１０×８×６の３階テンソルで第１モードを処理対象とするとき、最大で８×６=４８個の非ゼロ要素がこの集合に含まれる。

Ｓ５０３：要素が欠損値であれば、Ｓ５０４に進み、そうでなければＳ５０５に進む。要素が欠損値であることの判定は、テンソル構築部１１で欠損値を負の値の非ゼロ要素で表現していることから、値の符号によって行える。

Ｓ５０４：要素の分母の補正値を計算し、更新式の分母の補正値に加算する。要素の分母の補正値は上記の式（６）により算出される。

Ｓ５０５：要素の分子の式を計算し、更新式の分子に加算する。尚、要素の分子の式は、上記の式（２）である。

Ｓ５０６：更新式の値を計算し、因子行列の要素を更新する。更新式の分母は、Ｓ５０１の概算値からＳ５０４の補正値を引くことで得られる。更新式の分子は、Ｓ５０５で得られたものを用いる。これらを上記の式（１）に代入することにより更新式の値が求められる。

欠損値推定部１３は、以上のテンソル分解部１２による更新処理により得られたテンソルの因子行列に基づき当該テンソルの欠損値を推定する。そして、この欠損値の推定値は、出力データ記憶部１４に保存される。

［本実施形態の効果］
以上のテンソル因子分解処理装置１によれば、非負値（複合）テンソル補完に用いるテンソル因子分解にあたり、テンソルの欠損値に対応した因子分解の高速化が実現する。したがって、計算結果の正確性を維持しながら、高速化技術を導入した欠損値のない非負値テンソルに対する非負値（複合）因子分解と比べて計算時間の増大を抑制できる。

特に、前記テンソルの要素が負の値であると当該要素は当該テンソルの欠損値であると判断して当該要素の補正値が前記更新に加算されることにより、当該テンソルの因子分解の計算結果の正確性が確保される。

以上のように、欠損値のあるテンソルの因子分解が低速にならざるをえない状況であっても、従来の欠損値非対応の高速化技術を拡張することにより、欠損値のないテンソルの因子分解のように非負値テンソル補完の高速化が図れる。

［本発明の他の態様］
本発明は、テンソル因子分解処理装置１を構成する各手段（機能部１０〜１４，２０〜２２）の一部若しくは全てとしてコンピュータを機能させるプログラムで構成しこれを当該コンピュータに実行させることにより実現できる。または、同装置１が実行するテンソル因子分解処理方法のステップＳ１００〜Ｓ１０４，Ｓ２００〜Ｓ２０２，Ｓ５００〜Ｓ５０６の一部若しくは全てをコンピュータに実行させるプログラムで構成しこれを当該コンピュータに実行させることにより実現できる。そして、これらのプログラム（テンソル因子分解処理プログラム）をそのコンピュータが読み取り可能な周知の記録媒体（例えば、ハードディスク、フレキシブルディスク、ＣＤ−ＲＯＭ等）に格納して提供できる。または、前記プログラムをインターネットや電子メール等でネットワークを介して提供できる。

尚、以上の発明は、上記の実施の形態に限定されることなく、特許請求の範囲内において種々変更、応用が可能である。

１…テンソル因子分解処理装置
１１…テンソル構築部（テンソル構築手段）
１２…テンソル分解部
１３…欠損値推定部
２０…初期化部
２１…行列更新部（行列更新手段）
２２…計算終了評価部

Claims (7)

1. 非負値テンソルの因子分解処理を行うテンソル因子分解処理装置であって、
   特定の事象の複数の属性情報に対応した値を要素とする前記テンソルを構築し、前記属性情報が欠損している要素の値を示す、ゼロ要素と区別できる欠損値を、負の値に置換するテンソル構築手段と、
   前記テンソルの因子行列の要素を乱数で初期化する初期化手段と、
   前記初期化された因子行列の要素を、二つのテンソル間の距離の指標である一般化ＫＬダイバージェンスに基づく更新式によって更新する行列更新手段と、
   前記要素が更新された因子行列から推定されるテンソルと元のテンソルとの距離として前記一般化ＫＬダイバージェンスを算出し、この距離が予め設定された前記更新の終了条件を満たしている場合または当該更新の計算回数が予め設定された上限に達している場合には当該更新を終了させる一方で当該距離が当該終了条件を満たさない場合には当該更新を継続させる計算終了評価手段と
   を備えたことを特徴とするテンソル因子分解処理装置。
2. 前記行列更新手段は、前記テンソルの要素が負の値であると当該要素は当該テンソルの欠損値であると判断して前記一般化ＫＬダイバージェンスに基づく当該要素の分母の補正値を前記更新式の分母の補正値に加算することにより当該更新式を補正すること
   を特徴とする請求項１に記載のテンソル因子分解処理装置。
3. 前記テンソル構築手段は、前記構築の際に前記テンソルをより低階の部分テンソルに変換して非ゼロ要素または欠損値の要素を列挙可能とすること
   を特徴とする請求項１または２に記載のテンソル因子分解処理装置。
4. 非負値テンソルの因子分解処理を行うテンソル因子分解処理装置が実行するテンソル因子分解処理方法であって、
   特定の事象の複数の属性情報に対応した値を要素とする前記テンソルを構築し、前記属性情報が欠損している要素の値を示す、ゼロ要素と区別できる欠損値を、欠損値を負の値に置換するテンソル構築ステップと、
   前記テンソルの因子行列の要素を乱数で初期化する初期化ステップと、
   前記初期化された因子行列の要素を、二つのテンソル間の距離の指標である一般化ＫＬダイバージェンスに基づく更新式によって更新する行列更新ステップと、
   前記要素が更新された因子行列から推定されるテンソルと元のテンソルとの距離として前記一般化ＫＬダイバージェンスを算出し、この距離が予め設定された前記更新の終了条件を満たしている場合または当該更新の計算回数が予め設定された上限に達している場合には当該更新を終了させる一方で当該距離が当該終了条件を満たさない場合には当該更新を継続させる計算終了評価ステップと
   を有することを特徴とするテンソル因子分解処理方法。
5. 前記行列更新ステップは、前記テンソルの要素が負の値であると当該要素は当該テンソルの欠損値であると判断して前記一般化ＫＬダイバージェンスに基づく当該要素の分母の補正値を前記更新式の分母の補正値に加算することにより当該更新式を補正すること
   を特徴とする請求項４に記載のテンソル因子分解処理方法。
6. 前記テンソル構築ステップは、前記構築の際に前記テンソルをより低階の部分テンソルに変換して非ゼロ要素または欠損値の要素を列挙可能とすること
   を特徴とする請求項４または５に記載のテンソル因子分解処理方法。
7. 請求項１から３のいずれか１項に記載のテンソル因子分解処理装置を構成する各手段としてコンピュータを機能させることを特徴とするテンソル因子分解処理プログラム。

Images