TOP > 国内特許検索 > 予測装置、パラメータ集合生産方法及びプログラム > 明細書

明細書 :予測装置、パラメータ集合生産方法及びプログラム

発行国 日本国特許庁(JP)
公報種別 再公表特許(A1)
発行日 平成31年4月25日(2019.4.25)
発明の名称または考案の名称 予測装置、パラメータ集合生産方法及びプログラム
国際特許分類 G06Q  10/04        (2012.01)
FI G06Q 10/04
国際予備審査の請求 未請求
全頁数 21
出願番号 特願2018-527609 (P2018-527609)
国際出願番号 PCT/JP2017/025236
国際公開番号 WO2018/012487
国際出願日 平成29年7月11日(2017.7.11)
国際公開日 平成30年1月18日(2018.1.18)
優先権出願番号 2016138075
優先日 平成28年7月12日(2016.7.12)
優先権主張国 日本国(JP)
指定国 AP(BW , GH , GM , KE , LR , LS , MW , MZ , NA , RW , SD , SL , ST , SZ , TZ , UG , ZM , ZW) , EA(AM , AZ , BY , KG , KZ , RU , TJ , TM) , EP(AL , AT , BE , BG , CH , CY , CZ , DE , DK , EE , ES , FI , FR , GB , GR , HR , HU , IE , IS , IT , LT , LU , LV , MC , MK , MT , NL , NO , PL , PT , RO , RS , SE , SI , SK , SM , TR) , OA(BF , BJ , CF , CG , CI , CM , GA , GN , GQ , GW , KM , ML , MR , NE , SN , TD , TG) , AE , AG , AL , AM , AO , AT , AU , AZ , BA , BB , BG , BH , BN , BR , BW , BY , BZ , CA , CH , CL , CN , CO , CR , CU , CZ , DE , DJ , DK , DM , DO , DZ , EC , EE , EG , ES , FI , GB , GD , GE , GH , GM , GT , HN , HR , HU , ID , IL , IN , IR , IS , JO , JP , KE , KG , KH , KN , KP , KR , KW , KZ , LA , LC , LK , LR , LS , LU , LY , MA , MD , ME , MG , MK , MN , MW , MX , MY , MZ , NA , NG , NI , NO , NZ , OM , PA , PE , PG , PH , PL , PT , QA , RO , RS , RU , RW , SA , SC , SD , SE , SG , SK , SL , SM , ST , SV , SY , TH , TJ , TM , TN , TR , TT
発明者または考案者 【氏名】松原 靖子
【氏名】櫻井 保志
出願人 【識別番号】504159235
【氏名又は名称】国立大学法人 熊本大学
個別代理人の代理人 【識別番号】100136180、【弁理士】、【氏名又は名称】羽立 章二
審査請求 未請求
テーマコード 5L049
Fターム 5L049AA04
要約 大規模な時系列データストリームを用いて、高精度に長期予測をも実現することが可能な予測装置等を提案する。予測装置1において、データストリームの階層的な構造に、カレントウィンドウ計算部11、レジーム更新部13、レジーム追加部15が対応する。さらに、パラメータ集合記憶部7に記憶されたパラメータ集合により特定される数理モデルは、非線形要素を含み、データストリームの非線形性を表現することができる。レジーム更新部13は、パラメータ集合を更新することにより、非線形動的システムによる予測を実現する。さらに、レジーム追加部15は、データストリームにおける新たなパターン(レジーム)を追加する。レジーム更新部13は、あるレジームから別のレジームへと移るイベントストリーム上でのレジームシフトを利用する。これにより、高精度な長期予測をも実現する。
特許請求の範囲 【請求項1】
時刻tcまでの時系列データXの一部であるカレントウィンドウXCを用いて時刻tcからlsステップ以降の一つ又は複数のイベント値を予測する予測装置であって、
パラメータ集合記憶手段と、レジーム更新手段と、予測手段を備え、
前記パラメータ集合記憶手段は、数理モデルを特定するパラメータ集合を記憶し、
前記数理モデルは、非線形要素を含み、
前記パラメータ集合は、前記非線形要素の係数を特定する非線形パラメータを含み、
前記レジーム更新手段は、前記非線形パラメータを変更せず、前記パラメータ集合に含まれる他のパラメータの一部又は全部を更新して、カレントウィンドウXCの各時刻のデータと、更新後の前記パラメータ集合により特定される数理モデルを用いて得られるカレントウィンドウXcの各時刻に対応するイベント値VCとの違いを小さくし、
前記予測手段は、更新後の前記パラメータ集合により特定される数理モデルを用いて時刻tcからlsステップ以降の一つ又は複数のイベント値を予測する、予測装置。
【請求項2】
前記パラメータ集合記憶手段は、c個(cは自然数)のパラメータ集合θi(i=1,…,c)を記憶し、
前記予測手段は、更新後のc個のパラメータ集合θiの一部又は全部を用いてイベント値VEを予測する、請求項1記載の予測装置。
【請求項3】
レジーム追加手段を備え、
前記レジーム追加手段は、カレントウィンドウXCの各時刻でのデータと、更新後のc個のパラメータ集合θiを用いて得られる対応する各時刻のイベント値VCとの違いが追加条件を満たすならば、前記パラメータ集合記憶手段に、新たなパラメータ集合θc+1を追加し、
前記レジーム更新手段は、c+1個のパラメータ集合θi(i=1,…,c+1)に含まれる非線形パラメータ以外のパラメータの一部又は全部を更新し、
前記予測手段は、更新後のc+1個のパラメータ集合θi(i=1,…,c+1)により特定される数理モデルの一部又は全部を用いてイベント値を予測する、請求項2記載の予測装置。
【請求項4】
前記数理モデルは、線形要素を含み、
前記パラメータ集合は、前記線形要素を特定する線形パラメータを含み、
前記レジーム追加手段は、
前記非線形パラメータを変更せずに前記線形パラメータを決定し、
決定した前記線形パラメータを使用して前記非線形パラメータを決定する、請求項1から3のいずれかに記載の予測装置。
【請求項5】
カレントウィンドウXc(j)(j=1,…,h、hは自然数)は、h階層であり、
前記パラメータ集合は、h階層の前記カレントウィンドウXc(j)に対応してh階層であり、
前記レジーム更新手段は、各階層において前記パラメータ集合を更新し、
前記予測手段は、各階層において予測されたイベント値から全体のイベント値を予測する、請求項1から4のいずれかに記載の予測装置。
【請求項6】
時刻tcまでの時系列データの一部であるカレントウィンドウXCを用いて、数理モデルを特定するパラメータ集合の一部のパラメータを変更して新たなパラメータ集合を生産するパラメータ集合生産方法であって、
前記数理モデルは、非線形要素を含み、
前記パラメータ集合は、前記非線形要素を特定する非線形パラメータを含み、
前記情報処理装置が備えるレジーム更新手段が、前記非線形パラメータを変更せず、前記パラメータ集合に含まれる他のパラメータの一部又は全部を更新して、カレントウィンドウXCの各時刻のデータと、更新後の前記パラメータ集合により特定される数理モデルを用いて得られるカレントウィンドウXCの各時刻に対応するイベント値VCとの違いを小さくする更新ステップを含むパラメータ集合生産方法。
【請求項7】
コンピュータを、請求項1から5のいずれかに記載の予測装置として機能させるためのプログラム。
発明の詳細な説明 【技術分野】
【0001】
本願発明は、予測装置、パラメータ集合生産方法及びプログラムに関し、特に、時刻tcまでのデータストリームXの一部であるカレントウィンドウXCを用いて時刻tcからlsステップ以降の一つ又は複数のイベント値VEを予測する予測装置等に関する。
【背景技術】
【0002】
発明者らは、これまで、時系列データの解析を研究してきた(非特許文献1参照)。発明者らが提案したAutoPlaitは、時系列データの特徴抽出に関して注目されている。
【0003】
時系列データに基づく予測について、例えば、自己回帰モデル(AR:autoregressive model)、その発展形であるARIMA(Autoregressive integrated moving average model)、線形動的システム(LDS:linear dynamical systems)、カルマンフィルタ(KF:Kalman filters)などが知られている。これらに基づく時系列の解析と予測手法として、AWSOM、TBATS、PLiFなどが提案されている。
【先行技術文献】
【0004】

【非特許文献1】Y. Matsubara、外1名, Christos Faloutsos: ”AutoPlait: Automatic Mining of Co-evolving Time Sequences”, ACM SIGMOD Conference, pp. 193-204, Snowbird, Utah, June 2014.
【発明の概要】
【発明が解決しようとする課題】
【0005】
しかしながら、従来、ほとんどの手法が線形システムを利用しているため、非線形性を有する時系列データの特徴の表現には不十分であった。また、非線形システムを利用するものは、最近傍探索に基づくものが主流であり、長期予測のための時系列のモデル化の能力を有さなかった。
【0006】
そこで、本願発明は、大規模な時系列データストリームを用いて、高精度に長期予測をも実現することが可能な予測装置等を提案することを目的とする。
【課題を解決するための手段】
【0007】
本願発明の第1の観点は、時刻tcまでの時系列データXの一部であるカレントウィンドウXCを用いて時刻tcからlsステップ以降の一つ又は複数のイベント値を予測する予測装置であって、パラメータ集合記憶手段と、レジーム更新手段と、予測手段を備え、前記パラメータ集合記憶手段は、数理モデルを特定するパラメータ集合を記憶し、前記数理モデルは、非線形要素を含み、前記パラメータ集合は、前記非線形要素の係数を特定する非線形パラメータを含み、前記レジーム更新手段は、前記非線形パラメータを変更せず、前記パラメータ集合に含まれる他のパラメータの一部又は全部を更新して、カレントウィンドウXCの各時刻のデータと、更新後の前記パラメータ集合により特定される数理モデルを用いて得られるカレントウィンドウXcの各時刻に対応するイベント値VCとの違いを小さくし、前記予測手段は、更新後の前記パラメータ集合により特定される数理モデルを用いて時刻tcからlsステップ以降の一つ又は複数のイベント値を予測するものである。
【0008】
本願発明の第2の観点は、第1の観点の予測装置であって、前記パラメータ集合記憶手段は、c個(cは自然数)のパラメータ集合θi(i=1,…,c)を記憶し、前記予測手段は、更新後のc個のパラメータ集合θiの一部又は全部を用いてイベント値VEを予測するものである。
【0009】
本願発明の第3の観点は、レジーム追加手段を備え、前記レジーム追加手段は、カレントウィンドウXCの各時刻でのデータと、更新後のc個のパラメータ集合θiを用いて得られる対応する各時刻のイベント値VCとの違いが追加条件を満たすならば、前記パラメータ集合記憶手段に、新たなパラメータ集合θc+1を追加し、前記レジーム更新手段は、c+1個のパラメータ集合θi(i=1,…,c+1)に含まれる非線形パラメータ以外のパラメータの一部又は全部を更新し、前記予測手段は、更新後のc+1個のパラメータ集合θi(i=1,…,c+1)により特定される数理モデルの一部又は全部を用いてイベント値を予測する、請求項2記載の予測装置。
【0010】
本願発明の第4の観点は、第1から第3のいずれかの観点の予測装置であって、前記数理モデルは、線形要素を含み、前記パラメータ集合は、前記線形要素を特定する線形パラメータを含み、前記レジーム追加手段は、前記非線形パラメータを変更せずに前記線形パラメータを決定し、決定した前記線形パラメータを使用して前記非線形パラメータを決定するものである。
【0011】
本願発明の第5の観点は、第1から第4のいずれかの観点の予測装置であって、カレントウィンドウXc(j)(j=1,…,h、hは自然数)は、h階層であり、前記パラメータ集合は、h階層の前記カレントウィンドウXc(j)に対応してh階層であり、前記レジーム更新手段は、各階層において前記パラメータ集合を更新し、前記予測手段は、各階層において予測されたイベント値から全体のイベント値を予測するものである。
【0012】
本願発明の第6の観点は、時刻tcまでの時系列データの一部であるカレントウィンドウXCを用いて、数理モデルを特定するパラメータ集合の一部のパラメータを変更して新たなパラメータ集合を生産するパラメータ集合生産方法であって、前記数理モデルは、非線形要素を含み、前記パラメータ集合は、前記非線形要素を特定する非線形パラメータを含み、前記情報処理装置が備えるレジーム更新手段が、前記非線形パラメータを変更せず、前記パラメータ集合に含まれる他のパラメータの一部又は全部を更新して、カレントウィンドウXCの各時刻のデータと、更新後の前記パラメータ集合により特定される数理モデルを用いて得られるカレントウィンドウXCの各時刻に対応するイベント値VCとの違いを小さくする更新ステップを含むものである。
【0013】
本願発明の第7の観点は、コンピュータを、第1から第5のいずれかの観点の予測装置として機能させるためのプログラムである。
【0014】
なお、本願発明を、第7の観点のプログラムを定常的に記録するコンピュータ読み取り可能な記録媒体として捉えてもよい。
【発明の効果】
【0015】
発明者らは、レジームという概念に着目した。レジームは、環境生態学において、自然現象内の特徴的な時系列パターンのことを指す。レジームシフトとは、あるレジーム(時系列パターン)から別のレジームに変化する現象を示す。レジームシフトは、近年、様々な分野において活発に研究されており、とりわけ環境生態学分野において活発に取り組まれている課題である。
【0016】
発明者らは、自然界の動的システムにおけるレジームシフトの概念を拡張し、新たな時系列予測手法を提案する。自然界の動的システムと同様に、実世界におけるデータストリームは、様々な潜在的要素に影響されながら時間発展していく。
【0017】
本願発明の各観点によれば、大規模な時系列データストリームが与えられたとき、その潜在的なパターンを、非線形要素を含んだ数理モデルにより表現する。そして、非線形パラメータ以外のパラメータ(例えば初期値など)を変更して非線形動的システムを用いて、非線形要素による潜在的なパターンの表現を維持しつつ適応させて、実世界におけるデータストリームを使って精度よく予測することが可能になる。
【0018】
さらに、本願発明の第2の観点によれば、レジームシフトの概念を用いて、複数の非線形モデルを使用することにより時系列データストリーム上でのレジームシフトを発見し、複雑に変化する時系列パターンを表現して、高精度に予測することができる。
【0019】
さらに、本願発明の第3の観点によれば、レジームシフトに伴い、新たなレジームを自動発見して、新たな時系列パターンを追加することができる。
【0020】
さらに、本願発明の第4の観点によれば、新たなレジームを表すモデルを、線形要素を特定した後に非線形要素を特定することにより、計算量を抑えつつ、精度よく推定することが可能になる。
【0021】
さらに、実際の時系列データストリームは、異なる時間発展に基づく多階層の動的システムから構成され、複雑な時系列パターンを有する。つまり、階層的な構造を伴う。本願発明の第5の観点によれば、多階層の構造を利用して予測することにより、高精度に予測することができる。
【図面の簡単な説明】
【0022】
【図1】(a)一般的なレジームシフトの概念と(b)本願発明のレジームシフトの概念の一例を示す。
【図2】本願発明の実施例による現時刻tcにおける分析と予測のスナップショットを示す。
【図3】本願発明の実施例であるRegimeCastの3つのアルゴリズムを示す。
【図4】本願発明の実施の形態に係る予測装置1の構成の概要を示すブロック図である。
【図5】図4の予測装置1の動作の一例を示すフロー図である。
【図6】図4の予測装置1において生成されるデータの一例を示す。
【図7】身体の運動に関するモーションストリームに対するRegimeCastの解析例を示す。
【図8】チキンダンスに対するRegimeCastの解析例を示す。
【図9】Googleにおける3ヶ月先の各キーワードの検索量の予測結果を示す。
【図10】本願発明と従来手法の予測精度を示す。
【図11】提案手法と従来手法の計算コストを示し、長期的なイベント予測での予測精度と計算コストを示す。
【発明を実施するための形態】
【0023】
以下では、図面を参照して、本願発明の実施例について説明する。なお、本願発明は、この実施例に限定されるものではない。
【実施例】
【0024】
まず、図1を参照して、レジームシフトの概念について説明する。レジームは、環境生態学において自然現象内の特徴的な時系列パターンのことを指す。レジームシフトは、あるレジームから別のレジームに変化する現象を示す。
【実施例】
【0025】
レジームシフトは、主に、内的要因(システム内の安定性の変化等)及び/又は外部要因(システムへの外部ショック等)により引き起こされる。例えば、図1(a)のように、草原地帯は森林地帯へシフトすることがある。草原地帯は、例えば、草食動物の存在、火事、森林伐採などの要素により木々の成長が抑えられ、安定したシステムとなる。何らかの理由により木々が一定以上の大きさに成長すれば、草食動物や火事の影響を受ける可能性が減少し、森林地帯へ移行する。また、同様に、森林地帯から草原地帯へシフトすることがある。
【実施例】
【0026】
発明者らは、自然界の動的システムにおけるレジームシフトの概念を拡張し、新たな時系列予測手法を提案する。図1(b)のモーションデータストリームのように、時系列データストリームでの時系列パターンをレジームとし、イベントストリーム上でのレジームシフトを利用することにより、予測精度を向上させる。特に、時系列データを適応型非線形動的システムとして表現することにより、複雑な時系列パターンを柔軟に表現する。そして、その適応型非線形動的システムを用いることにより予測精度を向上させる。
【実施例】
【0027】
本願発明によれば、様々な時系列パターン(例えばセンサデータやWebのアクセス履歴等)から構成される大規模データストリームが与えられたとき、それらの中から重要な特徴や潜在的なトレンドを発見し、長期的かつ継続的に将来の時系列予測を行うことができる。
【実施例】
【0028】
まず、予測に使用する数理モデルの一例について説明する。
【実施例】
【0029】
生態系における各要素の時間発展は、数1の常微分方程式で表現することができる。ここで、s(t)は時刻tにおける生態系の特性(養分や土壌など)を表す。a0は栄養負荷などのs(t)を変化させる環境要因を表す。a1はシステム内のs(t)の成長、減衰率を示す(例えば、a1<0における栄養除去率など)。a2はs(t)の関数f(s(t))による回復率(栄養循環など)を示す。関数fによりレジームの推移が発生する。
【実施例】
【0030】
【数1】
JP2018012487A1_000003t.gif
【実施例】
【0031】
発明者らは、数1の動的システムにおけるレジームシフトの概念を拡張した。まず、最もシンプルなパターンとして、単一の動的パターン(レジーム)の表現方法について述べる。ここでは、イベントシーケンスの中にレジームシフトは存在しない。このモデルは、s(t)とv(t)の2種類の時系列活動パターンから構成される。ここで、s(t)は、k次元の潜在値(潜在的な時系列パターン)を示す。v(t)は、時刻tにおけるd次元の推定イベント(実際のイベント観測値)を示す(例えば、d個のセンサから生成される実測値)。これにより、単一のレジームは、数2で表現される。
・s(t):潜在値、時刻tにおけるk次元の潜在的な活動値(s(t)={si(t)}ki=1
・v(t):推定イベント、時刻tにおけるd次元の観測値(v(t)={vi(t)}di=1
【実施例】
【0032】
ここで、初期条件をs(0)=s0とする。ds(t)/dtを時刻tの導関数とする。S(t)をs(t)の2次形式とする(すなわち、S(t)=s(t)Ts(t))。また、p、Q、Aは、潜在値s(t)を生成するパラメータ集合であり、各成分が、線形、指数、非線形の動的パターンを表現する(なお、この例では、非線形動的パターンの要素Aを2次関数として扱う)。u、Vは、時刻tにおける潜在値s(t)から推定イベントv(t)への射影を示す。さらに、非線形テンソルAについては、動的システムの複雑化を防ぐために、スパースであることが重要である。
【実施例】
【0033】
単一の潜在的非線形動的システムにおけるパラメータ集合をθ={s0,p,Q,A,u,V}とする。
【実施例】
【0034】
【数2】
JP2018012487A1_000004t.gif
【実施例】
【0035】
次に、イベントストリーム上でのレジームシフトについて述べる。例えば、図1(b)におけるc=2種類のレジーム(walking、wiping)が任意のタイミングで交互に繰り返されるものである。このような複雑なイベントを表現するため、順応性の高い時系列モデルが必要になる。そこで、より複雑な時系列パターンを表現するために、w(t)を導入する。ここで、w(t)は、時刻tにおけるi番目のレジーム(i=1,…,c)の推移の強さを示す。
・w(t):レジーム活動値、時刻tにおけるc個のレジームにおけるレジームシフトの推移値。
【実施例】
【0036】
数2のモデルを拡張し、数3のモデルを提案する。ここで、si(t)は、時刻tにおけるi番目のレジームの潜在値である(si(t)={sij(t)}kj=1)。w(t)は、時刻tにおけるi番目のレジームの強さである(w(t)={wi(t)}ci=1)。v(t)は、時刻tにおけるd次元の推定イベントである。dw(t)/dtは、時刻tの導関数を示す。
【実施例】
【0037】
数3において、新たなパラメータとしてr(t)を導入する。r(t)は、時刻tにおけるc次元のベクトルとして表現される。Rを、レジームシフトのダイナミクスを表現するパラメータ集合とする(R={r(t)}tct=1)。ここで、tcは、イベントストリームの長さを表す。Rをレジームシフト行列と呼ぶ。c=1の場合(イベントストリームが単一のレジームで構成されている場合)には、数3のモデルは、数2のモデルに一致する。
【実施例】
【0038】
レジームのパラメータ集合を、Θ={θ1,…,θc,R}とする。ここで、cは、イベントストリームに含まれるレジームの個数を示す。
【実施例】
【0039】
【数3】
JP2018012487A1_000005t.gif
【実施例】
【0040】
さらに、多階層の構造への拡張について説明する。数2及び数3のシステムは、単一階層における動的システムであった。しかしながら、実世界における時系列イベントは、異なる時間発展に基づく時系列活動パターンを含んでいる。例えば、Web上のイベントにおける10年周期や1日周期などである。そこで、階層的な構造をともなう時系列パターンを表現するため、階層構造に基づくモデルを使用する。具体的には、多階層のレジーム集合M={Θ(1),Θ(2),…}を用いる。レジーム集合は、階層構造をともなう時系列パターンを表現するモデルの全パラメータ集合である。階層iにおいてローカルな推定イベントv(i)(t)を生成し、重ね合わせることにより、実際の推定イベントv(t)を表現する。
【実施例】
【0041】
続いて、必要な概念を説明する。表1は、主な記号と定義を示す。
【実施例】
【0042】
【表1】
JP2018012487A1_000006t.gif
【実施例】
【0043】
Xを、d次元のイベントエントリから構成されるデータストリームX={x(1),…,x(tc)}とし、tcを現在の時刻とする。Xを、イベントストリームと呼ぶ。
【実施例】
【0044】
毎時刻において、新たなイベントエントリx(tc)が発生し、時刻が進むごとにtcが増加するものとする。そこで、最新の時刻において発生したイベント集合をカレントウィンドウとして次のように定義する。XC=X[tm:tc]を長さlcのカレントウィンドウの部分シーケンスとする。ここで、XCは、イベントストリームXの時刻tmから時刻tcまで(1≦tm≦tc)の部分シーケンスを示す。以下では、lc=3・lsとする。
【実施例】
【0045】
カレントウィンドウXCが与えられたとき、次の目標は、パラメータ集合Mの中から最適なレジームを発見し、数3のモデルに基づきlsステップ先の未来のイベントVF={v(ts),…,v(tc)}を推定することである。VF=V[ts:tc]をlsステップ先の将来イベントシーケンス(tc≦ts≦te)とし、ts=tc+ls、te=ts+lpとする。ここで、lpは、出力単位時間の長さである。
【実施例】
【0046】
図2は、本願発明の実施例の一つであるRegimeCastの現時刻tcにおけるスナップショットを示す。ここで、黒点線は、オリジナルのイベントストリームXを示す。図2では、d=4次元のイベントシーケンスで構成される。太線は、時刻tmから時刻teにおけるRegimeCastによるイベントの推定値VEを示す。ここで、時刻tcから時刻teまでの部分シーケンスは、未来の(つまり未知の)イベント集合である。本願発明は、これらの時系列パターンを高速かつ継続的に推定し続けなくてはならない。本願発明は、オリジナルのストリームX(黒点線)が与えられたとき、カレントウィンドウXCに含まれる最新の時系列パターンを発見し、適応型非線形動的システムとして表現することで、現時刻の時系列パターンVE(色太線)を推定し、lsステップ先の将来イベントVF(矩形内)を高速かつ継続的に出力する。
【実施例】
【0047】
まとめると、以下のように表現することができる。イベントストリームX={x(1),…,x(tc),…}が与えられたとき、lsステップ先の将来イベントVFを出力し続ける。具体的には、各時刻tcにおいて、カレントウィンドウXCに含まれる最適なレジームのパターンを検出し、XCのレジームパターンに基づきモデルのパラメータ集合Mを更新し、lsステップ先の将来イベントVFを出力する。
【実施例】
【0048】
図3を参照して、本願発明の実施例の一つであるRegimeCastの概要を説明する。RegimeCastは、以下の3つのアルゴリズムで構成される。
RegimeReader:カレントウィンドウXCとレジームパラメータ集合Θが与えられたとき、レジームのダイナミクスを推定し、イベントVE=V[tm:te]を生成する(図3(a)参照)。
RegimeEstimator:カレントウィンドウXCの中に新たなレジームパターンが含まれていた場合に、XCを表現する新たなパラメータ集合θを推定する(図3(b)参照)。
RegimeCast:各階層i(i=1,…,h)における最適なイベント集合VE(i)を推定し、推定イベントVE=VE(1)+VE(2)+…を計算する。その後、lsステップ先のイベント(つまりVF)を報告する。さらに、レジームパラメータ集合Mを更新する(図3(c)参照)。
【実施例】
【0049】
図3のアルゴリズムを詳細に説明する。議論の単純化のため、まずは、単一の階層(つまり、h=1)のみを考慮し、単一のカレントウィンドウXCとレジームパラメータ集合Θが与えられた場合について説明する。
【実施例】
【0050】
RegimeReaderで、時刻tcにおけるカレントウィンドウXCとレジームパラメータ集合Θ={θ1,…,θc,R}が与えられた場合を考える。RegimeReaderの目的は、現在のレジームパラメータ集合Θに基づき、イベントシーケンスVE=V[tm:te]を推定することである。
【実施例】
【0051】
適切なイベントの推定値を得るための最も単純な解決法は、Θ内のパラメータ集合を固定し、数3のモデルに基づきv(tm)、v(tm+1),…を計算することである。しかしながら、実際のイベントストリームでは、カレントウィンドウXCに含まれる潜在的なトレンドは、時間の経過とともに動的かつ連続的に変化していく。そこで、Θ内に含まれるレジームのパラメータを最新のカレントウィンドウXCのパターンに基づき最適化する。具体的には、図3のアルゴリズムは、XC内に含まれる現時刻の活動パターンに応じてΘ内のパラメータ集合を柔軟に更新していく必要がある。
【実施例】
【0052】
図3(a)は、RegimeReaderの処理の流れを示す。RegimeReaderは、(1)個々のレジームの最適化、(2)レジームシフトの同定、の2つのパートから構成される。
【実施例】
【0053】
(1)個々のレジームの最適化
個々のレジームのレジームパラメータθi∈Θ(i=1,…,c)について、潜在値の初期値s0∈θiを最適化する。具体的には、オリジナルイベントと推定イベントの2乗誤差を最小化する(つまり、min||XC-XCi||)ようなs0を求める。ここで、関数fC(s0|θ)は、数3のモデルにおける、レジームパラメータs0、θが与えられたうえでの推定イベントVC={v(tm),…,v(tc)}を示す。
【実施例】
【0054】
(2)レジームシフトの同定
(1)で得られたc個の推定イベントの集合{VCici=1に基づき、時刻tcにおけるレジームシフトの潜在的な動的パターンを推定する。具体的には、Θに含まれるレジームの集合を最適化するためにレジーム活動値w(tc)を推定し、数3に基づきΘ内のレジームシフト行列Rを更新する(つまり、min||XC-fC(Θ)||)。その後、推定イベントVE=fE(Θ)をカレントウィンドウXCに対する最適値として計算する。ここで、平均二乗誤差||・||を最小化する方法として、非線形性を有する学習に適したLM(Levenberg-Marquardt)アルゴリズムを用いる。
【実施例】
【0055】
次に、図3(b)を参照して、新たなレジームを推定するためのアルゴリズムであるRegimeEstimatorについて説明する。ここでの課題は、カレントウィンドウXCに未知のレジームが含まれていた場合の処理についてである。提案アルゴリズムは、XCに含まれる未知の時系列パターンを表現するため、新たなレジームθを推定し、パラメータ集合Θに挿入する。
【実施例】
【0056】
ここで重要な問題として、レジームを表現するθは、非常に多くのパラメータ数から構成されている。一般に、非線形モデルにおける多数のパラメータの同時推定は、最適解の学習が非常に難しく、計算コストも高い。さらに、非線形活動テンソルAは、単一のレジーム内の時系列パターンの複雑性を抑えるために、スパースであることが重要である。
【実施例】
【0057】
そこで、線形、非線形の双方のパラメータ集合を高速かつ効果的に推定するためのアルゴリズムとしてRegimeEstimatorを提案する。具体的には、パラメータ集合θを、線形、非線形の2種の部分集合:θL={p,Q,u,V}、θN={A}に分割し、それぞれのパラメータ集合を個別に推定する。図3(b)を参照して、カレントウィンドウXCが与えられたとき、提案アルゴリズムは、まず非線形活動テンソルをA=0とし、XCの線形的なパターンを表現するための初期状態s0及び線形パラメータ集合θLを推定する。パラメータの推定にはEM(expectation-maximization)アルゴリズムを用いた。続いて、非線形要素Aに関し、推定したs0とθLを用いて、Xcと潜在値Vcのエラー値を最小化するようにLMアルゴリズムによって最小化する。本研究では、非線形テンソルAについて、モデルの複雑性を抑えるため、対角成分aijk∈A(i=j=k)のみを推定した。
【実施例】
【0058】
これまでは、単一階層のレジーム集合Θに対する推定イベントVEの生成方法について述べた。本研究の目的は、多階層における時系列パターンM={Θ(1),…,Θ(h)}を表現し、lsステップ先の予測ウィンドウVFを推定することである。イベントストリームXが与えられたとき、年、週、日単位などの様々な階層の動的パターンを表現したい。そこで、本願発明は、階層モデルに基づく予測手法を提案する。具体的には、カレントウィンドウXCをh個の階層的なイベント集合XC=XC(1)+…+XC(h)に分割することで、より効果的な予測を実現する。ここで、XC(i)は、i番目の階層におけるイベントを示し、数4で計算される。関数g(・|t)は、長さtの移動平均を示す。本論文では、H={2・ls,1}とした。
【実施例】
【0059】
【数4】
JP2018012487A1_000007t.gif
【実施例】
【0060】
図3(c)は、RegimeCastの詳細を示す。時刻tcにおける新たなイベントx(tc)が与えられたとき、本願発明は、各階層iにおけるカレントウィンドウXC(i)を計算し、(1)イベントシーケンスVE(i)を推定する。もし、Θ(i)内に適切なレジームが存在しない場合(つまり、カレントウィンドウと推定イベントの誤差がε以上、例えば、ε=1/2||XC(i)||の場合)、(2)新たなレジームθを生成し、レジームパラメータ集合Θ(i)を更新する。最後に(3)lsステップ先の予測ウィンドウVFを出力する。
【実施例】
【0061】
続いて、ダイナミックポイントセット(DSP)に基づく高速化を説明する。RegimeReaderは、数3のモデルに示したとおり、複雑な動的システムに基づくため、各時刻tcにおいて、潜在値SE={s(tm),…,s(te)}の推定にO(le)の計算量を要する。ここで、leは、SEの長さを示す。しかし、この計算時間は、リアルタイム性を要する処理にはボトルネックとなりうる。そこで、本願では、動的なイベント生成を高速化するための手法を提案する。具体的には、すべてのイベント集合SE={s(tm),s(tm+1),s(tm+2),…,s(te)}を生成する代わりに、SEの部分集合であるS^E={s(tm),s(tm+δ),s(tm+2δ),…,s(te)}のみを生成する。ここで、部分集合S^EをDSPと呼ぶ。δは、潜在値の時間の生成間隔(例えば、δ=0.1・ls)を示す。S^Eは、数5の4次のルンゲ・クッタ法に基づき生成を行う。これにより、モデル推定の計算時間がS^Eの長さであるO(le/δ)となり、飛躍的な高速化を実現することができる。
【実施例】
【0062】
理論的な分析を示す。leを、推定イベント集合VEの長さとし、cを、Mに含まれるレジームの個数とする。このとき、各時刻におけるRegimeCastの計算時間は、最小でO(c・le/δ)、最大でO(c・le/δ+lc)となる。各時刻tcにおいて、RegimeReaderは、c個の最適なレジームVEを推定するために、O(c・le/δ)の計算時間を要する。もし、カレントウィンドウXCに新たなレジームが含まれていた場合、RegimeEstimatorは、パラメータ集合θの推定にO(lc)を要する。したがって、最小でO(c・le/δ)、最大でO(c・le/δ+lc)の計算時間を要する。
【実施例】
【0063】
【数5】
JP2018012487A1_000008t.gif
【実施例】
【0064】
図4、図5及び図6を参照して、本願発明の実施の形態に係る予測装置の構成及び動作の一例を説明する。
【実施例】
【0065】
図4は、本願発明の実施の形態に係る予測装置1の構成の概要を示すブロック図である。(a)は、予測装置1の構成を示す。(b)及び(c)は、それぞれ、レジーム更新部13j及びレジーム追加部15jの構成を示す。
【実施例】
【0066】
図4(a)を参照して、予測装置1は、データストリーム記憶部3と、カレントウィンドウ記憶部5と、パラメータ集合記憶部7(本願請求項の「パラメータ集合記憶手段」の一例)と、h個(hは自然数)のカレントウィンドウ計算部11j(j=1,…,h)と、h個のレジーム更新部13j(本願請求項の「レジーム更新手段」の一例)と、レジーム追加部15j(本願請求項の「レジーム追加手段」の一例)と、予測部17(本願請求項の「予測手段」の一例)を備える。なお、符号の添え字は、省略する場合がある。データストリーム記憶部3、カレントウィンドウ記憶部5、パラメータ集合記憶部7は、例えばメモリやハードディスクなどの記憶装置によって実現することができる。カレントウィンドウ計算部11、レジーム更新部13、レジーム追加部15、予測部17は、例えばCPUなどの演算装置によって実現することができる。
【実施例】
【0067】
図4(b)を参照して、レジーム更新部13jは、c個(cは自然数)のアクティビティ演算部21jiと、重み演算部23jと、レジームシフト変数演算部25jと、パラメータ更新部27jと、推定イベント演算部29jを備える。
【実施例】
【0068】
図4(c)を参照して、レジーム追加部15jは、線形パラメータ推定部31jと、非線形パラメータ推定部33jと、パラメータ集合追加部35jを備える。
【実施例】
【0069】
図5は、図4の(a)予測装置1と、(b)レジーム更新部13jと、(c)レジーム追加部15jの動作の一例を示すフロー図である。図5(a)、(b)及び(c)の実質的な処理は、それぞれ、図3(c)、(a)及び(b)と同様である。図6は、図4の予測装置1において生成されるデータの一例を示す。
【実施例】
【0070】
図5(a)を参照して、予測装置1の動作を説明する。予測装置1に、時系列データストリームXが入力される(ステップST1)。図6(a)は、データストリームXの一例を示す。データストリーム記憶部3は、入力されたデータストリームXを記憶する。
【実施例】
【0071】
実際の時系列データストリームは、階層的な構造を伴う。カレントウィンドウ計算部11j、レジーム更新部13j及びレジーム追加部15jは、階層的な構造を利用して解析するために、時系列データストリームのh階層のそれぞれに対応する。
【実施例】
【0072】
カレントウィンドウ計算部11jは、対応する階層のカレントウィンドウXC(j)を生成する(ステップST2)。図6(a)に、カレントウィンドウの設定の一例を示す。カレントウィンドウ記憶部5は、生成されたカレントウィンドウXC(j)を記憶する。
【実施例】
【0073】
パラメータ集合記憶部7は、全パラメータ集合Mを記憶する。
【実施例】
【0074】
レジーム更新部13jは、カレントウィンドウXC(j)とレジームパラメータ集合Θ(i)から、VE(i)と更新後のΘ(j)を得る(ステップST3)。具体的な処理は、図5(b)を用いて後に説明する。図6(b)及び(c)は、第1階層の2つのパラメータ集合θ1(1)及びθ2(1)により生成されるデータを示す。図6(d)及び(e)は、第2階層の2つのパラメータ集合θ1(2)及びθ2(2)により生成されるデータを示す。なお、実際には、多くのパラメータ集合が使用される。
【実施例】
【0075】
レジーム追加部15jは、更新後のΘ(j)を用いて、カレントウィンドウXC(j)の各時刻に対応するVC(j)を得る(ステップST4)。そして、カレントウィンドウXC(j)とVC(j)との誤差が小さいか否かを判断する(ステップST5)。誤差は、例えば、図3にあるように、二乗誤差が所定の値ε以下か否かによって判断することができる。これらの値が近く、追加条件を満たさないならば、ステップST7に進む。これらの値が近くなく、追加条件を満たすならば、レジーム追加部15jは、新たなパラメータ集合θを追加し(ステップST6)、ステップST7へ進む。ステップST6の具体的な処理は、図5(c)を用いて説明する。
【実施例】
【0076】
ステップST7で、予測装置は、各階層の予測値VE(j)を統合し、全体の予測値VEを得る。そして、lsステップ先の未来のイベント値VFを出力する。図6(f)は、各VE(j)を統合して得られるVEと、将来イベントVFとの関係を示す。
【実施例】
【0077】
続いて、図5(b)を参照して、レジーム更新部13jの動作を具体的に説明する。図4(b)では、アクティビティ演算部21jiは、階層のパラメータ集合θの数と同数である。
【実施例】
【0078】
レジーム更新部13jは、カレントウィンドウXC(j)と、現時点でのレジームパラメータΘ(j)を入力する(ステップSTR1)。そして、各アクティビティ演算部21jiは、対応するパラメータ集合θi(j)の一部を変更して、カレントウィンドウXC(j)とVC(j)の値の誤差を小さくする(ステップSTR2)。ここで、変更するパラメータは、例えば初期値のように、非線形パラメータ以外のものとする。
【実施例】
【0079】
続いて、レジームのアクティビティを分析する。重み演算部23jは、各VCiの重みを、重み付けしたVCiとXCとの誤差が小さくするように決定する。レジームシフト変数演算部25jは、各VCiの重みの差分をとり、レジームシフト変数を演算する。パラメータ更新部27jは、レジームシフト変数を利用して、対応する階層のレジームパラメータ集合Θ(j)を更新する(ステップSTR3)。推定イベント演算部29jは、各階層の推定イベントVE(j)を計算し、VE(j)とΘ(j)を出力する(ステップSTR4)。
【実施例】
【0080】
続いて、図5(c)を参照して、レジーム追加部15jの動作を具体的に説明する。レジーム追加部15jは、カレントウィンドウXC(j)を入力する(ステップSTE1)。そして、線形パラメータ推定部31jは、非線形パラメータを初期化し(ステップSTE2)、初期値と線形パラメータを求める(ステップSTE3)。そして、非線形パラメータ推定部33jは、求められた線形パラメータを使用して、新たな初期値と非線形パラメータを得る(ステップSTE4)。パラメータ集合追加部35jは、求めたパラメータを用いてパラメータ集合を生成し、新たなパラメータ集合を追加する(ステップSTE5)。
【実施例】
【0081】
本願発明は、大規模データストリームが与えられたとき、その中から重要なトレンドを発見し、様々な時系列パターン(レジーム)をモデル化し、長期的な予測を実現する。本願発明の重要な特徴は、以下のように表現することができる。本願では、自然界の生態系モデルにおけるレジームシフトの概念を拡張し、大規模時系列データストリームを適応型非線形動的システムとして表現することで、複雑な時系列パターンを柔軟に表現し、長期的なイベント予測を可能にする。
【実施例】
【0082】
(1) 潜在的な非線形動的パターン
自然界の動的システムと同様に、実世界におけるデータストリームは、様々な潜在的要素に影響されながら時間発展していく。例えば、車両センサデータストリームは、交通状況、天候、運転者等の要素により推移し、Webのアクセス履歴データは、ユーザの嗜好や興味に基づき時間発展する。そこで、本願では、時系列データストリームの潜在的なパターンを非線形の動的システムとして表現する。より具体的には、時系列データシーケンスを潜在的非線形微分方程式として表現する。
【実施例】
【0083】
(2) データストリーム上でのレジームシフト
本願では、さらに、重要な時系列パターンの変化点(データストリーム上でのレジームシフト)を自動発見する。本願では、レジームシフトの概念に基づき、時系列データストリームをモデル化する。複数の非線形モデルを用いることにより、複雑に変化する時系列パターンの全てを表現する。
【実施例】
【0084】
(3) 階層的な構造
実際の時系列データストリームは、異なる時間発展に基づく多階層の動的システムから構成され、複雑な時系列パターンを有する。つまり、階層的な構造を伴う。本願は、階層構造に基づくモデルを使用することにより、高精度な予測を実現する。
【実施例】
【0085】
図7~図11を参照して、予測結果の実験例を説明する。
【実施例】
【0086】
図7は、身体の運動に関するモーションストリームに対するRegimeCastの解析例を示す。データセットは左右の腕と足の動きから生成され、walking (歩く)、stretch (腕のストレッチ)等の複数のモーションから構成される。(a)は、オリジナルデータを示す。(b)は、(100:120)-ステップ先の将来イベントをlp=20時刻ごとに出力する。(c)~(f)は、異なる4つの時刻におけるスナップショットを示す。RegimeCastは自動的かつ効果的に、stretchモーションからwalkingモーションへの移り変わりをはじめとする複数のレジームシフトを検出し、長期的かつ継続的な将来イベントの予測に成功している。
【実施例】
【0087】
図8は、チキンダンスに対するRegimeCastの解析例を示す。具体的には、(a)はオリジナルデータを示し、(b)は(c)beaks、wings、tail feathers、clapsの4つの代表的なダンスステップから構成されている。一般に、ダンスステップのパターンは、多階層のレジームが含まれ、より複雑な時系列パターンから構成される。そのため、予測が非常に難しい。具体的には、図6(c)~(f)に示されるように、各ステップには、いくつかの基本的な動作が含まれており、それぞれの動作が異なるテンポを持っている。RegimeCastは、複数の潜在的なレジームで構成される複雑な時系列パターンを表現し、長期的な動作の予測に成功している。特に、RegimeCastは、事前知識やステップに関する情報を使用しない。RegimeCastは、重要な時系列パターン(レジーム)を高速に発見し、新たなレジームのパラメータを時系列モデルデータベースに格納することで、柔軟なイベント予測を継続的に行うことができる。
【実施例】
【0088】
本願は、モーションキャプチャデータ以外に、Web情報にも応用可能である。図9はGoogleにおける3ヶ月先の各キーワードの検索量の予測結果を示している。図9から分かるように、3ヶ月先のホットトピックを知ることが可能である。さらに、本発明は、環境情報(気温と気圧)、経済情報(為替と金プラチナ相場)などでも良好な予測結果が出ている。
【実施例】
【0089】
図10は、本願発明と従来手法の予測結果の比較を示している。従来手法としてARIMA、TBATSと比較している。図10(a)及び(b)は、それぞれ、図8の場合に、オリジナルデータと(100;120)-ステップ先の予測イベントの推定値との二乗平均誤差(RMSE)のエラー値及び平均値を示す。(a)では、TBATSはエラー値が極めて高いために省略している。図10(c)及び(d)は、それぞれ、ARIMAとTBATSによる予測結果を示す。既存の予測手法であるARIMAとTBATSは、非線形の時系列パターンとその変化点であるレジームシフトを表現できないため、適切に予測することができないことがわかる。
【実施例】
【0090】
図11は、提案手法と従来手法の計算コスト及び長期的なイベント予測での予測精度と計算コストを示す。なお、DPSの効果を検証するため、時間感覚をδ=1とした場合についても比較を行った(RegimeCast-F)。(a)及び(b)は、それぞれ、エクササイズでの計算コスト及び平均値を示す。(c)及び(d)は、それぞれ、家の掃除での計算コスト及び平均値を示す。(e)及び(f)は、ステップ数lsを50、75、…、200のように変化させたときの予測精度と計算コストを示している。いずれの場合にも、RegimeCastは、既存手法と比較して、長期的なイベント予測に対す大幅な性能向上を達成している。
【実施例】
【0091】
図10及び図11が示すように、提案手法は予測精度と計算コストの両面で優れている。
【符号の説明】
【0092】
1 予測装置、3 データストリーム記憶部、5 カレントウィンドウ記憶部、7 パラメータ集合記憶部、11 カレントウィンドウ計算部、13 レジーム更新部、15 レジーム追加部、17 予測部、21 アクティビティ演算部、23 重み演算部、25 レジームシフト変数演算部、27 パラメータ更新部、29 推定イベント演算部、31 線形パラメータ推定部、33 非線形パラメータ推定部、35 パラメータ集合追加部
図面
【図1】
0
【図2】
1
【図3】
2
【図4】
3
【図5】
4
【図6】
5
【図7】
6
【図8】
7
【図9】
8
【図10】
9
【図11】
10