(57)【要約】  大規模な時系列データストリームを用いて、高精度に長期予測をも実現することが可能な予測装置等を提案する。予測装置１において、データストリームの階層的な構造に、カレントウィンドウ計算部１１、レジーム更新部１３、レジーム追加部１５が対応する。さらに、パラメータ集合記憶部７に記憶されたパラメータ集合により特定される数理モデルは、非線形要素を含み、データストリームの非線形性を表現することができる。レジーム更新部１３は、パラメータ集合を更新することにより、非線形動的システムによる予測を実現する。さらに、レジーム追加部１５は、データストリームにおける新たなパターン（レジーム）を追加する。レジーム更新部１３は、あるレジームから別のレジームへと移るイベントストリーム上でのレジームシフトを利用する。これにより、高精度な長期予測をも実現する。
2018012487.tif 000002
【特許請求の範囲】
【請求項１】
時刻ｔcまでの時系列データＸの一部であるカレントウィンドウＸCを用いて時刻ｔcからｌsステップ以降の一つ又は複数のイベント値を予測する予測装置であって、
パラメータ集合記憶手段と、レジーム更新手段と、予測手段を備え、
前記パラメータ集合記憶手段は、数理モデルを特定するパラメータ集合を記憶し、
前記数理モデルは、非線形要素を含み、
前記パラメータ集合は、前記非線形要素の係数を特定する非線形パラメータを含み、
前記レジーム更新手段は、前記非線形パラメータを変更せず、前記パラメータ集合に含まれる他のパラメータの一部又は全部を更新して、カレントウィンドウＸCの各時刻のデータと、更新後の前記パラメータ集合により特定される数理モデルを用いて得られるカレントウィンドウＸcの各時刻に対応するイベント値ＶCとの違いを小さくし、
前記予測手段は、更新後の前記パラメータ集合により特定される数理モデルを用いて時刻ｔcからｌsステップ以降の一つ又は複数のイベント値を予測する、予測装置。
【請求項２】
前記パラメータ集合記憶手段は、ｃ個（ｃは自然数）のパラメータ集合θi（ｉ＝１，…，ｃ）を記憶し、
前記予測手段は、更新後のｃ個のパラメータ集合θiの一部又は全部を用いてイベント値ＶEを予測する、請求項１記載の予測装置。
【請求項３】
レジーム追加手段を備え、
前記レジーム追加手段は、カレントウィンドウＸCの各時刻でのデータと、更新後のｃ個のパラメータ集合θiを用いて得られる対応する各時刻のイベント値ＶCとの違いが追加条件を満たすならば、前記パラメータ集合記憶手段に、新たなパラメータ集合θc+1を追加し、
前記レジーム更新手段は、ｃ＋１個のパラメータ集合θi（ｉ＝１，…，ｃ＋１）に含まれる非線形パラメータ以外のパラメータの一部又は全部を更新し、
前記予測手段は、更新後のｃ＋１個のパラメータ集合θi（ｉ＝１，…，ｃ＋１）により特定される数理モデルの一部又は全部を用いてイベント値を予測する、請求項２記載の予測装置。
【請求項４】
前記数理モデルは、線形要素を含み、
前記パラメータ集合は、前記線形要素を特定する線形パラメータを含み、
前記レジーム追加手段は、
前記非線形パラメータを変更せずに前記線形パラメータを決定し、
決定した前記線形パラメータを使用して前記非線形パラメータを決定する、請求項１から３のいずれかに記載の予測装置。
【請求項５】
カレントウィンドウＸc(j)（ｊ＝１，…，ｈ、ｈは自然数）は、ｈ階層であり、
前記パラメータ集合は、ｈ階層の前記カレントウィンドウＸc(j)に対応してｈ階層であり、
前記レジーム更新手段は、各階層において前記パラメータ集合を更新し、
前記予測手段は、各階層において予測されたイベント値から全体のイベント値を予測する、請求項１から４のいずれかに記載の予測装置。
【請求項６】
時刻ｔcまでの時系列データの一部であるカレントウィンドウＸCを用いて、数理モデルを特定するパラメータ集合の一部のパラメータを変更して新たなパラメータ集合を生産するパラメータ集合生産方法であって、
前記数理モデルは、非線形要素を含み、
前記パラメータ集合は、前記非線形要素を特定する非線形パラメータを含み、
前記情報処理装置が備えるレジーム更新手段が、前記非線形パラメータを変更せず、前記パラメータ集合に含まれる他のパラメータの一部又は全部を更新して、カレントウィンドウＸCの各時刻のデータと、更新後の前記パラメータ集合により特定される数理モデルを用いて得られるカレントウィンドウＸCの各時刻に対応するイベント値ＶCとの違いを小さくする更新ステップを含むパラメータ集合生産方法。
【請求項７】
コンピュータを、請求項１から５のいずれかに記載の予測装置として機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本願発明は、予測装置、パラメータ集合生産方法及びプログラムに関し、特に、時刻ｔcまでのデータストリームＸの一部であるカレントウィンドウＸCを用いて時刻ｔcからｌsステップ以降の一つ又は複数のイベント値ＶEを予測する予測装置等に関する。
【背景技術】
【０００２】
発明者らは、これまで、時系列データの解析を研究してきた（非特許文献１参照）。発明者らが提案したAutoPlaitは、時系列データの特徴抽出に関して注目されている。【０００３】
時系列データに基づく予測について、例えば、自己回帰モデル（AR：autoregressive model）、その発展形であるARIMA（Autoregressive integrated moving average model）、線形動的システム（LDS：linear dynamical systems）、カルマンフィルタ（KF：Kalman filters）などが知られている。これらに基づく時系列の解析と予測手法として、AWSOM、TBATS、PLiFなどが提案されている。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】Y. Matsubara、外１名, Christos Faloutsos: ”AutoPlait: Automatic Mining of Co-evolving Time Sequences”, ACM SIGMOD Conference, pp. 193-204, Snowbird, Utah, June 2014.
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかしながら、従来、ほとんどの手法が線形システムを利用しているため、非線形性を有する時系列データの特徴の表現には不十分であった。また、非線形システムを利用するものは、最近傍探索に基づくものが主流であり、長期予測のための時系列のモデル化の能力を有さなかった。【０００６】
そこで、本願発明は、大規模な時系列データストリームを用いて、高精度に長期予測をも実現することが可能な予測装置等を提案することを目的とする。
【課題を解決するための手段】
【０００７】
本願発明の第１の観点は、時刻ｔcまでの時系列データＸの一部であるカレントウィンドウＸCを用いて時刻ｔcからｌsステップ以降の一つ又は複数のイベント値を予測する予測装置であって、パラメータ集合記憶手段と、レジーム更新手段と、予測手段を備え、前記パラメータ集合記憶手段は、数理モデルを特定するパラメータ集合を記憶し、前記数理モデルは、非線形要素を含み、前記パラメータ集合は、前記非線形要素の係数を特定する非線形パラメータを含み、前記レジーム更新手段は、前記非線形パラメータを変更せず、前記パラメータ集合に含まれる他のパラメータの一部又は全部を更新して、カレントウィンドウＸCの各時刻のデータと、更新後の前記パラメータ集合により特定される数理モデルを用いて得られるカレントウィンドウＸcの各時刻に対応するイベント値ＶCとの違いを小さくし、前記予測手段は、更新後の前記パラメータ集合により特定される数理モデルを用いて時刻ｔcからｌsステップ以降の一つ又は複数のイベント値を予測するものである。【０００８】
本願発明の第２の観点は、第１の観点の予測装置であって、前記パラメータ集合記憶手段は、ｃ個（ｃは自然数）のパラメータ集合θi（ｉ＝１，…，ｃ）を記憶し、前記予測手段は、更新後のｃ個のパラメータ集合θiの一部又は全部を用いてイベント値ＶEを予測するものである。【０００９】
本願発明の第３の観点は、レジーム追加手段を備え、前記レジーム追加手段は、カレントウィンドウＸCの各時刻でのデータと、更新後のｃ個のパラメータ集合θiを用いて得られる対応する各時刻のイベント値ＶCとの違いが追加条件を満たすならば、前記パラメータ集合記憶手段に、新たなパラメータ集合θc+1を追加し、前記レジーム更新手段は、ｃ＋１個のパラメータ集合θi（ｉ＝１，…，ｃ＋１）に含まれる非線形パラメータ以外のパラメータの一部又は全部を更新し、前記予測手段は、更新後のｃ＋１個のパラメータ集合θi（ｉ＝１，…，ｃ＋１）により特定される数理モデルの一部又は全部を用いてイベント値を予測する、請求項２記載の予測装置。【００１０】
本願発明の第４の観点は、第１から第３のいずれかの観点の予測装置であって、前記数理モデルは、線形要素を含み、前記パラメータ集合は、前記線形要素を特定する線形パラメータを含み、前記レジーム追加手段は、前記非線形パラメータを変更せずに前記線形パラメータを決定し、決定した前記線形パラメータを使用して前記非線形パラメータを決定するものである。【００１１】
本願発明の第５の観点は、第１から第４のいずれかの観点の予測装置であって、カレントウィンドウＸc(j)（ｊ＝１，…，ｈ、ｈは自然数）は、ｈ階層であり、前記パラメータ集合は、ｈ階層の前記カレントウィンドウＸc(j)に対応してｈ階層であり、前記レジーム更新手段は、各階層において前記パラメータ集合を更新し、前記予測手段は、各階層において予測されたイベント値から全体のイベント値を予測するものである。【００１２】
本願発明の第６の観点は、時刻ｔcまでの時系列データの一部であるカレントウィンドウＸCを用いて、数理モデルを特定するパラメータ集合の一部のパラメータを変更して新たなパラメータ集合を生産するパラメータ集合生産方法であって、前記数理モデルは、非線形要素を含み、前記パラメータ集合は、前記非線形要素を特定する非線形パラメータを含み、前記情報処理装置が備えるレジーム更新手段が、前記非線形パラメータを変更せず、前記パラメータ集合に含まれる他のパラメータの一部又は全部を更新して、カレントウィンドウＸCの各時刻のデータと、更新後の前記パラメータ集合により特定される数理モデルを用いて得られるカレントウィンドウＸCの各時刻に対応するイベント値ＶCとの違いを小さくする更新ステップを含むものである。【００１３】
本願発明の第７の観点は、コンピュータを、第１から第５のいずれかの観点の予測装置として機能させるためのプログラムである。【００１４】
なお、本願発明を、第７の観点のプログラムを定常的に記録するコンピュータ読み取り可能な記録媒体として捉えてもよい。
【発明の効果】
【００１５】
発明者らは、レジームという概念に着目した。レジームは、環境生態学において、自然現象内の特徴的な時系列パターンのことを指す。レジームシフトとは、あるレジーム（時系列パターン）から別のレジームに変化する現象を示す。レジームシフトは、近年、様々な分野において活発に研究されており、とりわけ環境生態学分野において活発に取り組まれている課題である。【００１６】
発明者らは、自然界の動的システムにおけるレジームシフトの概念を拡張し、新たな時系列予測手法を提案する。自然界の動的システムと同様に、実世界におけるデータストリームは、様々な潜在的要素に影響されながら時間発展していく。【００１７】
本願発明の各観点によれば、大規模な時系列データストリームが与えられたとき、その潜在的なパターンを、非線形要素を含んだ数理モデルにより表現する。そして、非線形パラメータ以外のパラメータ（例えば初期値など）を変更して非線形動的システムを用いて、非線形要素による潜在的なパターンの表現を維持しつつ適応させて、実世界におけるデータストリームを使って精度よく予測することが可能になる。【００１８】
さらに、本願発明の第２の観点によれば、レジームシフトの概念を用いて、複数の非線形モデルを使用することにより時系列データストリーム上でのレジームシフトを発見し、複雑に変化する時系列パターンを表現して、高精度に予測することができる。【００１９】
さらに、本願発明の第３の観点によれば、レジームシフトに伴い、新たなレジームを自動発見して、新たな時系列パターンを追加することができる。【００２０】
さらに、本願発明の第４の観点によれば、新たなレジームを表すモデルを、線形要素を特定した後に非線形要素を特定することにより、計算量を抑えつつ、精度よく推定することが可能になる。【００２１】
さらに、実際の時系列データストリームは、異なる時間発展に基づく多階層の動的システムから構成され、複雑な時系列パターンを有する。つまり、階層的な構造を伴う。本願発明の第５の観点によれば、多階層の構造を利用して予測することにより、高精度に予測することができる。
【図面の簡単な説明】
【００２２】
【図１】（ａ）一般的なレジームシフトの概念と（ｂ）本願発明のレジームシフトの概念の一例を示す。
【図２】本願発明の実施例による現時刻ｔcにおける分析と予測のスナップショットを示す。
【図３】本願発明の実施例であるRegimeCastの３つのアルゴリズムを示す。
【図４】本願発明の実施の形態に係る予測装置１の構成の概要を示すブロック図である。
【図５】図４の予測装置１の動作の一例を示すフロー図である。
【図６】図４の予測装置１において生成されるデータの一例を示す。
【図７】身体の運動に関するモーションストリームに対するRegimeCastの解析例を示す。
【図８】チキンダンスに対するRegimeCastの解析例を示す。
【図９】Googleにおける3ヶ月先の各キーワードの検索量の予測結果を示す。
【図１０】本願発明と従来手法の予測精度を示す。
【図１１】提案手法と従来手法の計算コストを示し、長期的なイベント予測での予測精度と計算コストを示す。
【発明を実施するための形態】
【００２３】
以下では、図面を参照して、本願発明の実施例について説明する。なお、本願発明は、この実施例に限定されるものではない。
【実施例】
【００２４】
まず、図１を参照して、レジームシフトの概念について説明する。レジームは、環境生態学において自然現象内の特徴的な時系列パターンのことを指す。レジームシフトは、あるレジームから別のレジームに変化する現象を示す。【００２５】
レジームシフトは、主に、内的要因（システム内の安定性の変化等）及び／又は外部要因（システムへの外部ショック等）により引き起こされる。例えば、図１（ａ）のように、草原地帯は森林地帯へシフトすることがある。草原地帯は、例えば、草食動物の存在、火事、森林伐採などの要素により木々の成長が抑えられ、安定したシステムとなる。何らかの理由により木々が一定以上の大きさに成長すれば、草食動物や火事の影響を受ける可能性が減少し、森林地帯へ移行する。また、同様に、森林地帯から草原地帯へシフトすることがある。【００２６】
発明者らは、自然界の動的システムにおけるレジームシフトの概念を拡張し、新たな時系列予測手法を提案する。図１（ｂ）のモーションデータストリームのように、時系列データストリームでの時系列パターンをレジームとし、イベントストリーム上でのレジームシフトを利用することにより、予測精度を向上させる。特に、時系列データを適応型非線形動的システムとして表現することにより、複雑な時系列パターンを柔軟に表現する。そして、その適応型非線形動的システムを用いることにより予測精度を向上させる。【００２７】
本願発明によれば、様々な時系列パターン（例えばセンサデータやWebのアクセス履歴等）から構成される大規模データストリームが与えられたとき、それらの中から重要な特徴や潜在的なトレンドを発見し、長期的かつ継続的に将来の時系列予測を行うことができる。【００２８】
まず、予測に使用する数理モデルの一例について説明する。【００２９】
生態系における各要素の時間発展は、数１の常微分方程式で表現することができる。ここで、ｓ（ｔ）は時刻ｔにおける生態系の特性（養分や土壌など）を表す。ａ0は栄養負荷などのｓ（ｔ）を変化させる環境要因を表す。ａ1はシステム内のｓ（ｔ）の成長、減衰率を示す（例えば、ａ1＜０における栄養除去率など）。ａ2はｓ（ｔ）の関数ｆ（ｓ（ｔ））による回復率（栄養循環など）を示す。関数ｆによりレジームの推移が発生する。【００３０】
【数１】
2018012487.tif 000003
【００３１】
発明者らは、数１の動的システムにおけるレジームシフトの概念を拡張した。まず、最もシンプルなパターンとして、単一の動的パターン（レジーム）の表現方法について述べる。ここでは、イベントシーケンスの中にレジームシフトは存在しない。このモデルは、ｓ（ｔ）とｖ（ｔ）の２種類の時系列活動パターンから構成される。ここで、ｓ（ｔ）は、ｋ次元の潜在値（潜在的な時系列パターン）を示す。ｖ（ｔ）は、時刻ｔにおけるｄ次元の推定イベント（実際のイベント観測値）を示す（例えば、ｄ個のセンサから生成される実測値）。これにより、単一のレジームは、数２で表現される。
・ｓ(t)：潜在値、時刻ｔにおけるｋ次元の潜在的な活動値（ｓ(t)＝｛ｓi(t)｝ki=1）
・ｖ(t)：推定イベント、時刻ｔにおけるｄ次元の観測値（ｖ(t)＝｛ｖi(t)｝di=1）【００３２】
ここで、初期条件をｓ（０）＝ｓ0とする。ｄｓ（ｔ）／ｄｔを時刻ｔの導関数とする。Ｓ（ｔ）をｓ（ｔ）の２次形式とする（すなわち、Ｓ（ｔ）＝ｓ（ｔ）Tｓ（ｔ））。また、ｐ、Ｑ、Ａは、潜在値ｓ（ｔ）を生成するパラメータ集合であり、各成分が、線形、指数、非線形の動的パターンを表現する（なお、この例では、非線形動的パターンの要素Ａを２次関数として扱う）。ｕ、Ｖは、時刻ｔにおける潜在値ｓ（ｔ）から推定イベントｖ（ｔ）への射影を示す。さらに、非線形テンソルＡについては、動的システムの複雑化を防ぐために、スパースであることが重要である。【００３３】
単一の潜在的非線形動的システムにおけるパラメータ集合をθ＝｛ｓ0，ｐ，Ｑ，Ａ，ｕ，Ｖ｝とする。【００３４】
【数２】
2018012487.tif 000004
【００３５】
次に、イベントストリーム上でのレジームシフトについて述べる。例えば、図１（ｂ）におけるｃ＝２種類のレジーム（walking、wiping）が任意のタイミングで交互に繰り返されるものである。このような複雑なイベントを表現するため、順応性の高い時系列モデルが必要になる。そこで、より複雑な時系列パターンを表現するために、ｗ（ｔ）を導入する。ここで、ｗ（ｔ）は、時刻ｔにおけるｉ番目のレジーム（ｉ＝１，…，ｃ）の推移の強さを示す。
・ｗ(t)：レジーム活動値、時刻ｔにおけるｃ個のレジームにおけるレジームシフトの推移値。【００３６】
数２のモデルを拡張し、数３のモデルを提案する。ここで、ｓi（ｔ）は、時刻ｔにおけるｉ番目のレジームの潜在値である（ｓi（ｔ）＝｛ｓij（ｔ）｝kj=1）。ｗ（ｔ）は、時刻ｔにおけるｉ番目のレジームの強さである（ｗ（ｔ）＝｛ｗi（ｔ）｝ci=1）。ｖ（ｔ）は、時刻ｔにおけるｄ次元の推定イベントである。ｄｗ（ｔ）／ｄｔは、時刻ｔの導関数を示す。【００３７】
数３において、新たなパラメータとしてｒ（ｔ）を導入する。ｒ（ｔ）は、時刻ｔにおけるｃ次元のベクトルとして表現される。Ｒを、レジームシフトのダイナミクスを表現するパラメータ集合とする（Ｒ＝｛ｒ（ｔ）｝tct=1）。ここで、ｔcは、イベントストリームの長さを表す。Ｒをレジームシフト行列と呼ぶ。ｃ＝１の場合（イベントストリームが単一のレジームで構成されている場合）には、数３のモデルは、数２のモデルに一致する。【００３８】
レジームのパラメータ集合を、Θ＝｛θ1，…，θc，Ｒ｝とする。ここで、ｃは、イベントストリームに含まれるレジームの個数を示す。【００３９】
【数３】
2018012487.tif 000005
【００４０】
さらに、多階層の構造への拡張について説明する。数２及び数３のシステムは、単一階層における動的システムであった。しかしながら、実世界における時系列イベントは、異なる時間発展に基づく時系列活動パターンを含んでいる。例えば、Web上のイベントにおける１０年周期や１日周期などである。そこで、階層的な構造をともなう時系列パターンを表現するため、階層構造に基づくモデルを使用する。具体的には、多階層のレジーム集合Ｍ＝｛Θ(1)，Θ(2)，…｝を用いる。レジーム集合は、階層構造をともなう時系列パターンを表現するモデルの全パラメータ集合である。階層ｉにおいてローカルな推定イベントｖ(i)（ｔ）を生成し、重ね合わせることにより、実際の推定イベントｖ（ｔ）を表現する。【００４１】
続いて、必要な概念を説明する。表１は、主な記号と定義を示す。【００４２】
【表１】
2018012487.tif 000006
【００４３】
Ｘを、ｄ次元のイベントエントリから構成されるデータストリームＸ＝｛ｘ（１），…，ｘ（ｔc）｝とし、ｔcを現在の時刻とする。Ｘを、イベントストリームと呼ぶ。【００４４】
毎時刻において、新たなイベントエントリｘ（ｔc）が発生し、時刻が進むごとにｔcが増加するものとする。そこで、最新の時刻において発生したイベント集合をカレントウィンドウとして次のように定義する。ＸC＝Ｘ［ｔm：ｔc］を長さｌcのカレントウィンドウの部分シーケンスとする。ここで、ＸCは、イベントストリームＸの時刻ｔmから時刻ｔcまで（１≦ｔm≦ｔc）の部分シーケンスを示す。以下では、ｌc＝３・ｌsとする。【００４５】
カレントウィンドウＸCが与えられたとき、次の目標は、パラメータ集合Ｍの中から最適なレジームを発見し、数３のモデルに基づきｌsステップ先の未来のイベントＶF＝｛ｖ（ｔs），…，ｖ（ｔc)}を推定することである。ＶF＝Ｖ［ｔs：ｔc]をｌsステップ先の将来イベントシーケンス（ｔc≦ｔs≦ｔe）とし、ｔs＝ｔc＋ｌs、ｔe＝ｔs＋ｌpとする。ここで、ｌpは、出力単位時間の長さである。【００４６】
図２は、本願発明の実施例の一つであるRegimeCastの現時刻ｔcにおけるスナップショットを示す。ここで、黒点線は、オリジナルのイベントストリームＸを示す。図２では、ｄ＝４次元のイベントシーケンスで構成される。太線は、時刻ｔmから時刻ｔeにおけるRegimeCastによるイベントの推定値ＶEを示す。ここで、時刻ｔcから時刻ｔeまでの部分シーケンスは、未来の（つまり未知の）イベント集合である。本願発明は、これらの時系列パターンを高速かつ継続的に推定し続けなくてはならない。本願発明は、オリジナルのストリームＸ（黒点線）が与えられたとき、カレントウィンドウＸCに含まれる最新の時系列パターンを発見し、適応型非線形動的システムとして表現することで、現時刻の時系列パターンＶE（色太線）を推定し、ｌsステップ先の将来イベントＶF（矩形内）を高速かつ継続的に出力する。【００４７】
まとめると、以下のように表現することができる。イベントストリームＸ＝｛ｘ（１），…，ｘ（ｔc），…｝が与えられたとき、ｌsステップ先の将来イベントＶFを出力し続ける。具体的には、各時刻ｔcにおいて、カレントウィンドウＸCに含まれる最適なレジームのパターンを検出し、ＸCのレジームパターンに基づきモデルのパラメータ集合Ｍを更新し、ｌsステップ先の将来イベントＶFを出力する。【００４８】
図３を参照して、本願発明の実施例の一つであるRegimeCastの概要を説明する。RegimeCastは、以下の３つのアルゴリズムで構成される。
RegimeReader：カレントウィンドウＸCとレジームパラメータ集合Θが与えられたとき、レジームのダイナミクスを推定し、イベントＶE＝Ｖ［ｔm：ｔe］を生成する（図３（ａ）参照）。
RegimeEstimator：カレントウィンドウＸCの中に新たなレジームパターンが含まれていた場合に、ＸCを表現する新たなパラメータ集合θを推定する（図３（ｂ）参照）。
RegimeCast：各階層ｉ（ｉ＝１，…，ｈ）における最適なイベント集合ＶE(i)を推定し、推定イベントＶE＝ＶE(1)＋ＶE(2)＋…を計算する。その後、ｌsステップ先のイベント（つまりＶF）を報告する。さらに、レジームパラメータ集合Ｍを更新する（図３（ｃ）参照）。【００４９】
図３のアルゴリズムを詳細に説明する。議論の単純化のため、まずは、単一の階層（つまり、ｈ＝１）のみを考慮し、単一のカレントウィンドウＸCとレジームパラメータ集合Θが与えられた場合について説明する。【００５０】
RegimeReaderで、時刻ｔcにおけるカレントウィンドウＸCとレジームパラメータ集合Θ＝｛θ1，…，θc，Ｒ｝が与えられた場合を考える。RegimeReaderの目的は、現在のレジームパラメータ集合Θに基づき、イベントシーケンスＶE＝Ｖ［ｔm：ｔe］を推定することである。【００５１】
適切なイベントの推定値を得るための最も単純な解決法は、Θ内のパラメータ集合を固定し、数３のモデルに基づきｖ（ｔm）、ｖ（ｔm＋１），…を計算することである。しかしながら、実際のイベントストリームでは、カレントウィンドウＸCに含まれる潜在的なトレンドは、時間の経過とともに動的かつ連続的に変化していく。そこで、Θ内に含まれるレジームのパラメータを最新のカレントウィンドウＸCのパターンに基づき最適化する。具体的には、図３のアルゴリズムは、ＸC内に含まれる現時刻の活動パターンに応じてΘ内のパラメータ集合を柔軟に更新していく必要がある。【００５２】
図３（ａ）は、RegimeReaderの処理の流れを示す。RegimeReaderは、(1)個々のレジームの最適化、(2)レジームシフトの同定、の２つのパートから構成される。【００５３】
(1)個々のレジームの最適化
個々のレジームのレジームパラメータθi∈Θ（ｉ＝１，…，ｃ）について、潜在値の初期値ｓ0∈θiを最適化する。具体的には、オリジナルイベントと推定イベントの２乗誤差を最小化する（つまり、min||ＸC−ＸCi||）ようなｓ0を求める。ここで、関数ｆC（ｓ0|θ）は、数３のモデルにおける、レジームパラメータｓ0、θが与えられたうえでの推定イベントＶC＝｛ｖ（ｔm），…，ｖ（ｔc）｝を示す。【００５４】
(2)レジームシフトの同定
(1)で得られたｃ個の推定イベントの集合｛ＶCi｝ci=1に基づき、時刻ｔcにおけるレジームシフトの潜在的な動的パターンを推定する。具体的には、Θに含まれるレジームの集合を最適化するためにレジーム活動値ｗ（ｔc）を推定し、数３に基づきΘ内のレジームシフト行列Ｒを更新する（つまり、min||ＸC−ｆC（Θ）||）。その後、推定イベントＶE＝ｆE（Θ）をカレントウィンドウＸCに対する最適値として計算する。ここで、平均二乗誤差||・||を最小化する方法として、非線形性を有する学習に適したＬＭ（Levenberg-Marquardt）アルゴリズムを用いる。【００５５】
次に、図３（ｂ）を参照して、新たなレジームを推定するためのアルゴリズムであるRegimeEstimatorについて説明する。ここでの課題は、カレントウィンドウＸCに未知のレジームが含まれていた場合の処理についてである。提案アルゴリズムは、ＸCに含まれる未知の時系列パターンを表現するため、新たなレジームθを推定し、パラメータ集合Θに挿入する。【００５６】
ここで重要な問題として、レジームを表現するθは、非常に多くのパラメータ数から構成されている。一般に、非線形モデルにおける多数のパラメータの同時推定は、最適解の学習が非常に難しく、計算コストも高い。さらに、非線形活動テンソルＡは、単一のレジーム内の時系列パターンの複雑性を抑えるために、スパースであることが重要である。【００５７】
そこで、線形、非線形の双方のパラメータ集合を高速かつ効果的に推定するためのアルゴリズムとしてRegimeEstimatorを提案する。具体的には、パラメータ集合θを、線形、非線形の２種の部分集合：θL＝｛ｐ，Ｑ，ｕ，Ｖ｝、θN＝｛Ａ｝に分割し、それぞれのパラメータ集合を個別に推定する。図３（ｂ）を参照して、カレントウィンドウＸCが与えられたとき、提案アルゴリズムは、まず非線形活動テンソルをＡ＝０とし、ＸCの線形的なパターンを表現するための初期状態ｓ0及び線形パラメータ集合θLを推定する。パラメータの推定にはＥＭ（expectation-maximization）アルゴリズムを用いた。続いて、非線形要素Ａに関し、推定したｓ0とθLを用いて、Ｘcと潜在値Ｖcのエラー値を最小化するようにＬＭアルゴリズムによって最小化する。本研究では、非線形テンソルＡについて、モデルの複雑性を抑えるため、対角成分ａijk∈Ａ（ｉ＝ｊ＝ｋ）のみを推定した。【００５８】
これまでは、単一階層のレジーム集合Θに対する推定イベントＶEの生成方法について述べた。本研究の目的は、多階層における時系列パターンＭ＝｛Θ(1)，…，Θ(h)｝を表現し、ｌsステップ先の予測ウィンドウＶFを推定することである。イベントストリームＸが与えられたとき、年、週、日単位などの様々な階層の動的パターンを表現したい。そこで、本願発明は、階層モデルに基づく予測手法を提案する。具体的には、カレントウィンドウＸCをｈ個の階層的なイベント集合ＸC＝ＸC(1)＋…＋ＸC(h)に分割することで、より効果的な予測を実現する。ここで、ＸC(i)は、ｉ番目の階層におけるイベントを示し、数４で計算される。関数ｇ（・｜ｔ）は、長さｔの移動平均を示す。本論文では、Ｈ＝｛２・ｌs，１｝とした。【００５９】
【数４】
2018012487.tif 000007
【００６０】
図３（ｃ）は、RegimeCastの詳細を示す。時刻ｔcにおける新たなイベントｘ（ｔc)が与えられたとき、本願発明は、各階層ｉにおけるカレントウィンドウＸC(i)を計算し、(1)イベントシーケンスＶE(i)を推定する。もし、Θ(i)内に適切なレジームが存在しない場合（つまり、カレントウィンドウと推定イベントの誤差がε以上、例えば、ε＝１／２||ＸC(i)||の場合)、(2)新たなレジームθを生成し、レジームパラメータ集合Θ(i)を更新する。最後に(3)ｌsステップ先の予測ウィンドウＶFを出力する。【００６１】
続いて、ダイナミックポイントセット（ＤＳＰ）に基づく高速化を説明する。RegimeReaderは、数３のモデルに示したとおり、複雑な動的システムに基づくため、各時刻ｔcにおいて、潜在値ＳE＝｛ｓ（ｔm），…，ｓ（ｔe）｝の推定にＯ（ｌe）の計算量を要する。ここで、ｌeは、ＳEの長さを示す。しかし、この計算時間は、リアルタイム性を要する処理にはボトルネックとなりうる。そこで、本願では、動的なイベント生成を高速化するための手法を提案する。具体的には、すべてのイベント集合ＳE＝｛ｓ（ｔm），ｓ（ｔm＋１），ｓ（ｔm＋２），…，ｓ（ｔe）｝を生成する代わりに、ＳEの部分集合であるＳ^E＝｛ｓ（ｔm），ｓ（ｔm＋δ），ｓ（ｔm＋２δ），…，ｓ（ｔe）｝のみを生成する。ここで、部分集合Ｓ^EをＤＳＰと呼ぶ。δは、潜在値の時間の生成間隔（例えば、δ＝0.1・ｌs）を示す。Ｓ^Eは、数５の４次のルンゲ・クッタ法に基づき生成を行う。これにより、モデル推定の計算時間がＳ^Eの長さであるＯ（ｌe/δ）となり、飛躍的な高速化を実現することができる。【００６２】
理論的な分析を示す。ｌeを、推定イベント集合ＶEの長さとし、ｃを、Ｍに含まれるレジームの個数とする。このとき、各時刻におけるRegimeCastの計算時間は、最小でＯ（ｃ・ｌe／δ）、最大でＯ（ｃ・ｌe／δ＋ｌc）となる。各時刻ｔcにおいて、RegimeReaderは、ｃ個の最適なレジームＶEを推定するために、Ｏ（ｃ・ｌe／δ）の計算時間を要する。もし、カレントウィンドウＸCに新たなレジームが含まれていた場合、RegimeEstimatorは、パラメータ集合θの推定にＯ（ｌc）を要する。したがって、最小でＯ（ｃ・ｌe／δ）、最大でＯ（ｃ・ｌe／δ＋ｌc）の計算時間を要する。【００６３】
【数５】
2018012487.tif 000008
【００６４】
図４、図５及び図６を参照して、本願発明の実施の形態に係る予測装置の構成及び動作の一例を説明する。【００６５】
図４は、本願発明の実施の形態に係る予測装置１の構成の概要を示すブロック図である。（ａ）は、予測装置１の構成を示す。（ｂ）及び（ｃ）は、それぞれ、レジーム更新部１３j及びレジーム追加部１５jの構成を示す。【００６６】
図４（ａ）を参照して、予測装置１は、データストリーム記憶部３と、カレントウィンドウ記憶部５と、パラメータ集合記憶部７（本願請求項の「パラメータ集合記憶手段」の一例）と、ｈ個（ｈは自然数）のカレントウィンドウ計算部１１j（ｊ＝１，…，ｈ）と、ｈ個のレジーム更新部１３j（本願請求項の「レジーム更新手段」の一例）と、レジーム追加部１５j（本願請求項の「レジーム追加手段」の一例）と、予測部１７（本願請求項の「予測手段」の一例）を備える。なお、符号の添え字は、省略する場合がある。データストリーム記憶部３、カレントウィンドウ記憶部５、パラメータ集合記憶部７は、例えばメモリやハードディスクなどの記憶装置によって実現することができる。カレントウィンドウ計算部１１、レジーム更新部１３、レジーム追加部１５、予測部１７は、例えばＣＰＵなどの演算装置によって実現することができる。【００６７】
図４（ｂ）を参照して、レジーム更新部１３jは、ｃ個（ｃは自然数）のアクティビティ演算部２１jiと、重み演算部２３jと、レジームシフト変数演算部２５jと、パラメータ更新部２７jと、推定イベント演算部２９jを備える。【００６８】
図４（ｃ）を参照して、レジーム追加部１５jは、線形パラメータ推定部３１jと、非線形パラメータ推定部３３jと、パラメータ集合追加部３５jを備える。【００６９】
図５は、図４の（ａ）予測装置１と、（ｂ）レジーム更新部１３jと、（ｃ）レジーム追加部１５jの動作の一例を示すフロー図である。図５（ａ）、（ｂ）及び（ｃ）の実質的な処理は、それぞれ、図３（ｃ）、（ａ）及び（ｂ）と同様である。図６は、図４の予測装置１において生成されるデータの一例を示す。【００７０】
図５（ａ）を参照して、予測装置１の動作を説明する。予測装置１に、時系列データストリームＸが入力される（ステップＳＴ１）。図６（ａ）は、データストリームＸの一例を示す。データストリーム記憶部３は、入力されたデータストリームＸを記憶する。【００７１】
実際の時系列データストリームは、階層的な構造を伴う。カレントウィンドウ計算部１１j、レジーム更新部１３j及びレジーム追加部１５jは、階層的な構造を利用して解析するために、時系列データストリームのｈ階層のそれぞれに対応する。【００７２】
カレントウィンドウ計算部１１jは、対応する階層のカレントウィンドウＸC(j)を生成する（ステップＳＴ２）。図６（ａ）に、カレントウィンドウの設定の一例を示す。カレントウィンドウ記憶部５は、生成されたカレントウィンドウＸC(j)を記憶する。【００７３】
パラメータ集合記憶部７は、全パラメータ集合Ｍを記憶する。【００７４】
レジーム更新部１３jは、カレントウィンドウＸC(j)とレジームパラメータ集合Θ(i)から、ＶE(i)と更新後のΘ(j)を得る（ステップＳＴ３）。具体的な処理は、図５（ｂ）を用いて後に説明する。図６（ｂ）及び（ｃ）は、第１階層の２つのパラメータ集合θ1(1)及びθ2(1)により生成されるデータを示す。図６（ｄ）及び（ｅ）は、第２階層の２つのパラメータ集合θ1(2)及びθ2(2)により生成されるデータを示す。なお、実際には、多くのパラメータ集合が使用される。【００７５】
レジーム追加部１５jは、更新後のΘ(j)を用いて、カレントウィンドウＸC(j)の各時刻に対応するＶC(j)を得る（ステップＳＴ４）。そして、カレントウィンドウＸC(j)とＶC(j)との誤差が小さいか否かを判断する（ステップＳＴ５）。誤差は、例えば、図３にあるように、二乗誤差が所定の値ε以下か否かによって判断することができる。これらの値が近く、追加条件を満たさないならば、ステップＳＴ７に進む。これらの値が近くなく、追加条件を満たすならば、レジーム追加部１５jは、新たなパラメータ集合θを追加し（ステップＳＴ６）、ステップＳＴ７へ進む。ステップＳＴ６の具体的な処理は、図５（ｃ）を用いて説明する。【００７６】
ステップＳＴ７で、予測装置は、各階層の予測値ＶE(j)を統合し、全体の予測値ＶEを得る。そして、ｌsステップ先の未来のイベント値ＶFを出力する。図６（ｆ）は、各ＶE(j)を統合して得られるＶEと、将来イベントＶFとの関係を示す。【００７７】
続いて、図５（ｂ）を参照して、レジーム更新部１３jの動作を具体的に説明する。図４（ｂ）では、アクティビティ演算部２１jiは、階層のパラメータ集合θの数と同数である。【００７８】
レジーム更新部１３jは、カレントウィンドウＸC(j)と、現時点でのレジームパラメータΘ(j)を入力する（ステップＳＴＲ１）。そして、各アクティビティ演算部２１jiは、対応するパラメータ集合θi(j)の一部を変更して、カレントウィンドウＸC(j)とＶC(j)の値の誤差を小さくする（ステップＳＴＲ２）。ここで、変更するパラメータは、例えば初期値のように、非線形パラメータ以外のものとする。【００７９】
続いて、レジームのアクティビティを分析する。重み演算部２３jは、各ＶCiの重みを、重み付けしたＶCiとＸCとの誤差が小さくするように決定する。レジームシフト変数演算部２５jは、各ＶCiの重みの差分をとり、レジームシフト変数を演算する。パラメータ更新部２７jは、レジームシフト変数を利用して、対応する階層のレジームパラメータ集合Θ(j)を更新する（ステップＳＴＲ３）。推定イベント演算部２９jは、各階層の推定イベントＶE(j)を計算し、ＶE(j)とΘ(j)を出力する（ステップＳＴＲ４）。【００８０】
続いて、図５（ｃ）を参照して、レジーム追加部１５jの動作を具体的に説明する。レジーム追加部１５jは、カレントウィンドウＸC(j)を入力する（ステップＳＴＥ１）。そして、線形パラメータ推定部３１jは、非線形パラメータを初期化し（ステップＳＴＥ２）、初期値と線形パラメータを求める（ステップＳＴＥ３）。そして、非線形パラメータ推定部３３jは、求められた線形パラメータを使用して、新たな初期値と非線形パラメータを得る（ステップＳＴＥ４）。パラメータ集合追加部３５jは、求めたパラメータを用いてパラメータ集合を生成し、新たなパラメータ集合を追加する（ステップＳＴＥ５）。【００８１】
本願発明は、大規模データストリームが与えられたとき、その中から重要なトレンドを発見し、様々な時系列パターン（レジーム）をモデル化し、長期的な予測を実現する。本願発明の重要な特徴は、以下のように表現することができる。本願では、自然界の生態系モデルにおけるレジームシフトの概念を拡張し、大規模時系列データストリームを適応型非線形動的システムとして表現することで、複雑な時系列パターンを柔軟に表現し、長期的なイベント予測を可能にする。【００８２】
(1) 潜在的な非線形動的パターン
自然界の動的システムと同様に、実世界におけるデータストリームは、様々な潜在的要素に影響されながら時間発展していく。例えば、車両センサデータストリームは、交通状況、天候、運転者等の要素により推移し、Webのアクセス履歴データは、ユーザの嗜好や興味に基づき時間発展する。そこで、本願では、時系列データストリームの潜在的なパターンを非線形の動的システムとして表現する。より具体的には、時系列データシーケンスを潜在的非線形微分方程式として表現する。【００８３】
(2) データストリーム上でのレジームシフト
本願では、さらに、重要な時系列パターンの変化点（データストリーム上でのレジームシフト）を自動発見する。本願では、レジームシフトの概念に基づき、時系列データストリームをモデル化する。複数の非線形モデルを用いることにより、複雑に変化する時系列パターンの全てを表現する。【００８４】
(3) 階層的な構造
実際の時系列データストリームは、異なる時間発展に基づく多階層の動的システムから構成され、複雑な時系列パターンを有する。つまり、階層的な構造を伴う。本願は、階層構造に基づくモデルを使用することにより、高精度な予測を実現する。【００８５】
図７〜図１１を参照して、予測結果の実験例を説明する。【００８６】
図７は、身体の運動に関するモーションストリームに対するRegimeCastの解析例を示す。データセットは左右の腕と足の動きから生成され、walking （歩く）、stretch （腕のストレッチ）等の複数のモーションから構成される。（ａ）は、オリジナルデータを示す。（ｂ）は、(100:120)-ステップ先の将来イベントをｌp＝２０時刻ごとに出力する。（ｃ）〜（ｆ）は、異なる４つの時刻におけるスナップショットを示す。RegimeCastは自動的かつ効果的に、stretchモーションからwalkingモーションへの移り変わりをはじめとする複数のレジームシフトを検出し、長期的かつ継続的な将来イベントの予測に成功している。【００８７】
図８は、チキンダンスに対するRegimeCastの解析例を示す。具体的には、（ａ）はオリジナルデータを示し、（ｂ）は（ｃ）beaks、wings、tail feathers、clapsの４つの代表的なダンスステップから構成されている。一般に、ダンスステップのパターンは、多階層のレジームが含まれ、より複雑な時系列パターンから構成される。そのため、予測が非常に難しい。具体的には、図６（ｃ）〜（ｆ）に示されるように、各ステップには、いくつかの基本的な動作が含まれており、それぞれの動作が異なるテンポを持っている。RegimeCastは、複数の潜在的なレジームで構成される複雑な時系列パターンを表現し、長期的な動作の予測に成功している。特に、RegimeCastは、事前知識やステップに関する情報を使用しない。RegimeCastは、重要な時系列パターン（レジーム）を高速に発見し、新たなレジームのパラメータを時系列モデルデータベースに格納することで、柔軟なイベント予測を継続的に行うことができる。【００８８】
本願は、モーションキャプチャデータ以外に、Web情報にも応用可能である。図９はGoogleにおける3ヶ月先の各キーワードの検索量の予測結果を示している。図９から分かるように、3ヶ月先のホットトピックを知ることが可能である。さらに、本発明は、環境情報（気温と気圧）、経済情報（為替と金プラチナ相場）などでも良好な予測結果が出ている。【００８９】
図１０は、本願発明と従来手法の予測結果の比較を示している。従来手法としてARIMA、TBATSと比較している。図１０（ａ）及び（ｂ）は、それぞれ、図８の場合に、オリジナルデータと(100;120)-ステップ先の予測イベントの推定値との二乗平均誤差（ＲＭＳＥ）のエラー値及び平均値を示す。（ａ）では、TBATSはエラー値が極めて高いために省略している。図１０（ｃ）及び（ｄ）は、それぞれ、ARIMAとTBATSによる予測結果を示す。既存の予測手法であるARIMAとTBATSは、非線形の時系列パターンとその変化点であるレジームシフトを表現できないため、適切に予測することができないことがわかる。【００９０】
図１１は、提案手法と従来手法の計算コスト及び長期的なイベント予測での予測精度と計算コストを示す。なお、ＤＰＳの効果を検証するため、時間感覚をδ＝１とした場合についても比較を行った（RegimeCast-F）。（ａ）及び（ｂ）は、それぞれ、エクササイズでの計算コスト及び平均値を示す。（ｃ）及び（ｄ）は、それぞれ、家の掃除での計算コスト及び平均値を示す。（ｅ）及び（ｆ）は、ステップ数ｌsを50、75、…、200のように変化させたときの予測精度と計算コストを示している。いずれの場合にも、RegimeCastは、既存手法と比較して、長期的なイベント予測に対す大幅な性能向上を達成している。【００９１】
図１０及び図１１が示すように、提案手法は予測精度と計算コストの両面で優れている。
【符号の説明】
【００９２】
１  予測装置、３  データストリーム記憶部、５  カレントウィンドウ記憶部、７  パラメータ集合記憶部、１１  カレントウィンドウ計算部、１３  レジーム更新部、１５  レジーム追加部、１７  予測部、２１  アクティビティ演算部、２３  重み演算部、２５  レジームシフト変数演算部、２７  パラメータ更新部、２９  推定イベント演算部、３１  線形パラメータ推定部、３３  非線形パラメータ推定部、３５  パラメータ集合追加部
【図１】
2018012487.tif 000009
【図２】
2018012487.tif 000010
【図３】
2018012487.tif 000011
【図４】
2018012487.tif 000012
【図５】
2018012487.tif 000013
【図６】
2018012487.tif 000014
【図７】
2018012487.tif 000015
【図８】
2018012487.tif 000016
【図９】
2018012487.tif 000017
【図１０】
2018012487.tif 000018
【図１１】
2018012487.tif 000019
【国際調査報告】
2018012487.tif 000020
2018012487.tif 000021
2018012487.tif 000022