(57)【要約】【課題】時系列データから急激な変化があった時点である変化点を、オンラインで精度良く検出する。【解決手段】時系列データを逐次的に読み込み、時系列モデル学習装置１１で時系列モデルのパラメータを学習し、コンプレキシティ及びパラメータ記憶装置１４に記憶する。入力データの１つ１つに対して逐次的に記憶装置１４からパラメータを読み込んで損失関数の値を計算し、これらを足し合わせていくことで逐次的に入力時系列データへのモデルの当てはめ誤差としてのコンプレキシティを計算し、記憶装置１４に記憶する。変化点探索装置１５が、変化点候補の全てに対して変化点前後の時系列データに対するコンプレキシティを記憶装置１４から読み出して、それらの和と変化点を仮定しない場合の全時系列データに対するコンプレキシティとを比較し、その差分値に基づいて変化点度合いを計算し、変化点度合いの大きさをもって変化点を検出して出力する。【選択図】図１
2005004658.tif 000002
【特許請求の範囲】
【請求項１】
時系列データを入力として逐次的に読み込みつつ、該入力時系列データにおいて急激に変化した時点である変化点を検出する変化点検出装置であって、
時系列データを読み込みながら時系列モデルのパラメータを逐次的に学習する時系列モデル学習手段と、
前記時系列モデル学習手段により学習された該時系列モデルのパラメータおよび該時系列モデルの該入力時系列データへの当てはめ誤差としてのコンプレキシティを記憶する記憶装置と、
前記記憶装置からパラメータを読み込んで、該入力時系列データの１つ１つに対して該時系列モデルの損失を計算する損失関数計算手段と、
前記記憶装置からパラメータおよびコンプレキシティを読み込んで、該入力時系列データの部分列のコンプレキシティを逐次的に更新しながら計算して前記記憶装置の記憶内容を更新するコンプレキシティ計算手段と、
該入力時系列データの全ての変化点候補に対して、変化点候補の前後の時系列データに対するコンプレキシティを前記記憶装置から読み込み、変化点候補の前後のコンプレキシティの和と変化点がないとしたときのコンプレキシティとを比較することにより変化点スコアを計算して変化点を検出する変化点探索手段とを備え、
前記変化点探索手段が検出した変化点を出力することを特徴とする変化点検出装置。
【請求項２】
時系列データを入力として逐次的に読み込みつつ、該入力時系列データにおいて急激に変化した時点である変化点を検出する変化点検出装置であって、
時系列データを読み込みながら時系列モデルのパラメータを逐次的に学習する時系列モデル学習手段と、
前記時系列モデル学習手段により学習された該時系列モデルのパラメータおよび該時系列モデルの該入力時系列データへの当てはめ誤差としてのコンプレキシティを記憶する記憶装置と、
前記記憶装置からパラメータを読み込んで、該入力時系列データの１つ１つに対して該時系列モデルの損失を計算する損失関数計算手段と、
前記記憶装置から読み込んだコンプレキシティに前記損失関数計算手段により計算された損失値を逐次的に加算することにより、該入力時系列データの部分列のモデルへの当てはめ誤差としてのコンプレキシティを計算して前記記憶装置の記憶内容を更新するコンプレキシティ計算手段と、
該入力時系列データの全ての変化点候補に対して、変化点候補の前後の時系列データに対するコンプレキシティを前記記憶装置から読み込み、変化点候補の前後のコンプレキシティの和と変化点がないとしたときのコンプレキシティとを比較することにより変化点スコアを計算して変化点を検出する変化点判定手段とを備え、
前記変化点判定手段が検出した変化点を出力することを特徴とする変化点検出装置。
【請求項３】
時系列データを入力として逐次的に読み込みつつ、該入力時系列データにおいて急激に変化した時点である変化点を検出する変化点検出方法であって、
時系列データを逐次的に読み込む工程と、
該入力時系列データから時系列モデルのパラメータを逐次的に学習する工程と、
該入力時系列データの１つ１つに対して該時系列モデルの損失を計算する損失関数計算工程と、
該時系列モデルの該入力時系列データへの当てはめ誤差としてのコンプレキシティを逐次的に計算するコンプレキシティ計算工程と、
該入力時系列データの全ての変化点候補に対して、変化点候補の前後の時系列データに対するコンプレキシティを計算して、変化点候補の前後のコンプレキシティの和と変化点がないとしたときのコンプレキシティとを比較することにより変化点スコアを計算して変化点を検出する変化点探索工程とを備え、
該変化点探索工程で検出した変化点を出力することを特徴とする変化点検出方法。
【請求項４】
時系列データを入力として逐次的に読み込みつつ、該入力時系列データにおいて急激に変化した時点である変化点を検出する変化点検出方法であって、
時系列データを逐次的に読み込む工程と、
該入力時系列データから時系列モデルのパラメータを逐次的に学習する工程と、
該入力時系列データの１つ１つに対して該時系列モデルの損失を計算する損失関数計算工程と、
該損失関数計算工程で計算した損失値を逐次的に加算することにより、該入力時系列データの部分列のモデルへの当てはめ誤差としてのコンプレキシティを計算するコンプレキシティ計算工程と、
該入力時系列データの全ての変化点候補に対して、変化点候補の前後の時系列データに対するコンプレキシティを前記記憶装置から読み込み、変化点候補の前後のコンプレキシティの和と変化点がないとしたときのコンプレキシティとを比較することにより変化点スコアを計算して変化点を検出する変化点判定工程とを備え、
該変化点判定工程が検出した変化点を出力することを特徴とする変化点検出方法。
【請求項５】
コンピュータを、時系列データを読み込みながら時系列モデルのパラメータを逐次的に学習する時系列モデル学習手段，前記時系列モデル学習手段により学習された該時系列モデルのパラメータおよび該時系列モデルの該入力時系列データへの当てはめ誤差としてのコンプレキシティを記憶する記憶装置，前記記憶装置からパラメータを読み込んで、該入力時系列データの１つ１つに対して該時系列モデルの損失を計算する損失関数計算手段，前記記憶装置からパラメータおよびコンプレキシティを読み込んで、該入力時系列データの部分列のコンプレキシティを逐次的に更新しながら計算して前記記憶装置の記憶内容を更新するコンプレキシティ計算手段，ならびに該入力時系列データの全ての変化点候補に対して、変化点候補の前後の時系列データに対するコンプレキシティを前記記憶装置から読み込み、変化点候補の前後のコンプレキシティの和と変化点がないとしたときのコンプレキシティとを比較することにより変化点スコアを計算して変化点を検出する変化点探索装置として動作させることを特徴とする変化点検出用プログラム。
【請求項６】
コンピュータを、時系列データを読み込みながら時系列モデルのパラメータを逐次的に学習する時系列モデル学習手段，前記時系列モデル学習手段により学習された該時系列モデルのパラメータおよび該時系列モデルの該入力時系列データへの当てはめ誤差としてのコンプレキシティを記憶する記憶装置，前記記憶装置からパラメータを読み込んで、該入力時系列データの１つ１つに対して該時系列モデルの損失を計算する損失関数計算手段，前記記憶装置から読み込んだコンプレキシティに前記損失関数計算手段により計算された損失値を逐次的に加算することにより、該入力時系列データの部分列のモデルへの当てはめ誤差としてのコンプレキシティを計算して前記記憶装置の記憶内容を更新するコンプレキシティ計算手段，および該入力時系列データの全ての変化点候補に対して、変化点候補の前後の時系列データに対するコンプレキシティを前記記憶装置から読み込み、変化点候補の前後のコンプレキシティの和と変化点がないとしたときのコンプレキシティとを比較することにより変化点スコアを計算して変化点を検出する変化点探索装置として動作させることを特徴とする変化点検出用プログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は変化点検出装置，変化点検出方法および変化点検出用プログラムに関し、特に時系列データにおいて急激に変化した時点を検出できる変化点検出装置，変化点検出方法および変化点検出用プログラムに関する。
【０００２】
【従来の技術】
従来の変化点検出装置の一例が、Ｖ．Ｇｕｒａｌｎｉｋ，Ｊ．Ｓｔｉｖａｓｔａｖａによる方式（例えば、非特許文献１参照）に記載されている。Ｖ．Ｇｕｒａｌｎｉｋ，Ｊ．Ｓｔｉｖａｓｔａｖａによる方式では、変化点がないとして曲線当てはめをした場合の当てはめ誤差の総和と、変化点の候補の前後で別々に曲線当てはめをした場合の当てはめ誤差の総和とを計算して、その差がある値以上になった場合に、変化点が生じたものと判定していた。
【０００３】
【非特許文献１】
Ｖ．Ｇｕｒａｌｎｉｋ  ａｎｄ  Ｊ．Ｓｒｉｖａｓｔａｖａ，  Ｅｖｅｎｔ  Ｄｅｔｅｃｔｉｏｎ  ｆｒｏｍ  Ｔｉｍｅ  Ｓｅｒｉｅｓ  Ｄａｔａ，  ｉｎ  Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  Ｆｉｆｔｈ  ＡＣＭ  ＳＩＧＫＤＤ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｋｎｏｗｌｅｄｇｅ  Ｄｉｓｃｏｖｅｒｙ  ａｎｄ  Ｄａｔａ  Ｍｉｎｉｎｇ，  ｐｐ：３３−４２，  ＡＣＭ  Ｐｒｅｓｓ，  １９９９．
【０００４】
【発明が解決しようとする課題】
第１の問題点は、従来技術では、当てはめ誤差がオンラインで計算できないということである。その理由は、Ｖ．Ｇｕｒａｌｎｉｋ，  Ｊ．Ｓｒｉｖａｓｔａｖａによる方法では、当てはめ誤差をバッチで計算する方法をとっているため、データが追加されるごとに全体の当てはめ誤差を計算し直さなければならないからである。また、バッチでモデルの当てはめを行っているため、区間内のパラメータは一定値をとるものと仮定しており、パラメータ値のゆるやかな時間的変化をとらえることができず、変化点検出の精度を下げてしまうからである。
【０００５】
本発明の目的は、時系列データに対して、オンラインで当てはめおよび当てはめ誤差に相当するコンプレキシティを計算することにより効率的に変化点検出を行い、かつモデルの非連続性に対応してモデル当てはめを行うことにより効果的に変化点を検出できる変化点検出装置，変化点検出方法および変化点検出用プログラムを提供することにある。
【０００６】
【課題を解決するための手段】
本発明の請求項１の変化点検出装置は、時系列データを入力として逐次的に読み込みつつ、該入力時系列データにおいて急激に変化した時点である変化点を検出する変化点検出装置であって、時系列データを読み込みながら時系列モデルのパラメータを逐次的に学習する時系列モデル学習手段と、前記時系列モデル学習手段により学習された該時系列モデルのパラメータおよび該時系列モデルの該入力時系列データへの当てはめ誤差としてのコンプレキシティを記憶する記憶装置と、前記記憶装置からパラメータを読み込んで、該入力時系列データの１つ１つに対して該時系列モデルの損失を計算する損失関数計算手段と、前記記憶装置からパラメータおよびコンプレキシティを読み込んで、該入力時系列データの部分列のコンプレキシティを逐次的に更新しながら計算して前記記憶装置の記憶内容を更新するコンプレキシティ計算手段と、該入力時系列データの全ての変化点候補に対して、変化点候補の前後の時系列データに対するコンプレキシティを前記記憶装置から読み込み、変化点候補の前後のコンプレキシティの和と変化点がないとしたときのコンプレキシティとを比較することにより変化点スコアを計算して変化点を検出する変化点探索手段とを備え、前記変化点探索手段が検出した変化点を出力することを特徴とする。
【０００７】
本発明の請求項２の変化点検出装置は、時系列データを入力として逐次的に読み込みつつ、該入力時系列データにおいて急激に変化した時点である変化点を検出する変化点検出装置であって、時系列データを読み込みながら時系列モデルのパラメータを逐次的に学習する時系列モデル学習手段と、前記時系列モデル学習手段により学習された該時系列モデルのパラメータおよび該時系列モデルの該入力時系列データへの当てはめ誤差としてのコンプレキシティを記憶する記憶装置と、前記記憶装置からパラメータを読み込んで、該入力時系列データの１つ１つに対して該時系列モデルの損失を計算する損失関数計算手段と、前記記憶装置から読み込んだコンプレキシティに前記損失関数計算手段により計算された損失値を逐次的に加算することにより、該入力時系列データの部分列のモデルへの当てはめ誤差としてのコンプレキシティを計算して前記記憶装置の記憶内容を更新するコンプレキシティ計算手段と、該入力時系列データの全ての変化点候補に対して、変化点候補の前後の時系列データに対するコンプレキシティを前記記憶装置から読み込み、変化点候補の前後のコンプレキシティの和と変化点がないとしたときのコンプレキシティとを比較することにより変化点スコアを計算して変化点を検出する変化点判定手段とを備え、前記変化点判定手段が検出した変化点を出力することを特徴とする。
【０００８】
本発明の請求項３の変化点検出方法は、時系列データを入力として逐次的に読み込みつつ、該入力時系列データにおいて急激に変化した時点である変化点を検出する変化点検出方法であって、時系列データを逐次的に読み込む工程と、該入力時系列データから時系列モデルのパラメータを逐次的に学習する工程と、該入力時系列データの１つ１つに対して該時系列モデルの損失を計算する損失関数計算工程と、該時系列モデルの該入力時系列データへの当てはめ誤差としてのコンプレキシティを逐次的に計算するコンプレキシティ計算工程と、該入力時系列データの全ての変化点候補に対して、変化点候補の前後の時系列データに対するコンプレキシティを計算して、変化点候補の前後のコンプレキシティの和と変化点がないとしたときのコンプレキシティとを比較することにより変化点スコアを計算して変化点を検出する変化点探索工程とを備え、該変化点探索工程で検出した変化点を出力することを特徴とする。
【０００９】
本発明の請求項４の変化点検出方法は、時系列データを入力として逐次的に読み込みつつ、該入力時系列データにおいて急激に変化した時点である変化点を検出する変化点検出方法であって、時系列データを逐次的に読み込む工程と、該入力時系列データから時系列モデルのパラメータを逐次的に学習する工程と、該入力時系列データの１つ１つに対して該時系列モデルの損失を計算する損失関数計算工程と、該損失関数計算工程で計算した損失値を逐次的に加算することにより、該入力時系列データの部分列のモデルへの当てはめ誤差としてのコンプレキシティを計算するコンプレキシティ計算工程と、該入力時系列データの全ての変化点候補に対して、変化点候補の前後の時系列データに対するコンプレキシティを前記記憶装置から読み込み、変化点候補の前後のコンプレキシティの和と変化点がないとしたときのコンプレキシティとを比較することにより変化点スコアを計算して変化点を検出する変化点判定工程とを備え、該変化点判定工程が検出した変化点を出力することを特徴とする。
【００１０】
本発明の請求項５の変化点検出用プログラムは、コンピュータを、時系列データを読み込みながら時系列モデルのパラメータを逐次的に学習する時系列モデル学習手段，前記時系列モデル学習手段により学習された該時系列モデルのパラメータおよび該時系列モデルの該入力時系列データへの当てはめ誤差としてのコンプレキシティを記憶する記憶装置，前記記憶装置からパラメータを読み込んで、該入力時系列データの１つ１つに対して該時系列モデルの損失を計算する損失関数計算手段，前記記憶装置からパラメータおよびコンプレキシティを読み込んで、該入力時系列データの部分列のコンプレキシティを逐次的に更新しながら計算して前記記憶装置の記憶内容を更新するコンプレキシティ計算手段，ならびに該入力時系列データの全ての変化点候補に対して、変化点候補の前後の時系列データに対するコンプレキシティを前記記憶装置から読み込み、変化点候補の前後のコンプレキシティの和と変化点がないとしたときのコンプレキシティとを比較することにより変化点スコアを計算して変化点を検出する変化点探索装置として動作させることを特徴とする。
【００１１】
本発明の請求項６の変化点検出用プログラムは、コンピュータを、時系列データを読み込みながら時系列モデルのパラメータを逐次的に学習する時系列モデル学習手段，前記時系列モデル学習手段により学習された該時系列モデルのパラメータおよび該時系列モデルの該入力時系列データへの当てはめ誤差としてのコンプレキシティを記憶する記憶装置，前記記憶装置からパラメータを読み込んで、該入力時系列データの１つ１つに対して該時系列モデルの損失を計算する損失関数計算手段，前記記憶装置から読み込んだコンプレキシティに前記損失関数計算手段により計算された損失値を逐次的に加算することにより、該入力時系列データの部分列のモデルへの当てはめ誤差としてのコンプレキシティを計算して前記記憶装置の記憶内容を更新するコンプレキシティ計算手段，および該入力時系列データの全ての変化点候補に対して、変化点候補の前後の時系列データに対するコンプレキシティを前記記憶装置から読み込み、変化点候補の前後のコンプレキシティの和と変化点がないとしたときのコンプレキシティとを比較することにより変化点スコアを計算して変化点を検出する変化点探索装置として動作させることを特徴とする。
【００１２】
【発明の実施の形態】
次に、本発明の実施の形態について、図面を参照して詳細に説明する。
【００１３】
［第１の実施の形態］
図１は、本発明の第１の実施の形態に係る変化点検出装置の構成を示すブロック図である。本実施の形態では、Ｎ個の与えられたデータ列ｘＮ＝ｘ１，…，ｘＮから変化点を検出する。本実施の形態に係る変化点検出装置は、時系列モデル学習装置１１と、コンプレキシティ計算装置１２と、損失関数計算装置１３と、コンプレキシティ及びパラメータ記憶装置１４と、変化点探索装置１５とから構成されている。
【００１４】
図２は、図１の変化点検出装置の概略動作を表すフローチャートであり、図１の変化点検出装置は以下のように動作する。
【００１５】
時系列モデル学習装置１１は、パラメトリックな時系列モデルを用意して、時系列データを逐次的に取り入れながら、パラメータを更新する。
【００１６】
以下、時系列モデルを記述する。Ｎ個のデータからなる系列をｘＮ＝ｘ１，ｘ２，…，ｘＮと表す。
【００１７】
ｎを与えられた正整数として、各データはｎ次元であり、それぞれの要素は実数値をとるものとする。
【００１８】
このような系列が確率密度関数ｐ（ｘＮ｜Θ）（Ｎ＝１，…）をもつ時系列モデルにしたがって発生しているとする。Θは確率密度を指定するパラメータである。また、ｔ番目のデータｘｔの確率密度はそれまでの系列ｘｔ−１に依存して定まるので、ｐ（ｘｔ｜ｘｔ−１，Θ）と書く。
【００１９】
確率密度関数の例としては、例えば、自己回帰モデル（ＡＲ（ａｕｔｏ−ｒｅｇｒｅｓｓｓｉｏｎ）モデル）を用いることができる。ｋを与えられた正整数として、ｋ次ＡＲモデルは、μをパラメータとして、ｔ番目のデータｘｔを、数１と書くとき、過去のｋ個のデータによってきまり、数２で表されるモデルである。ここに、Ａｉ（ｉ＝１，…，ｋ）はｎ次正方行列であり、εは平均値０、共分散行列Σの正規分布に従う確率変数である。
【００２０】
【数１】
2005004658.tif 000003
【００２１】
【数２】
2005004658.tif 000004
【００２２】
今、数３のように表すとき、データｘｔの確率密度関数は、数４で記述される。
【００２３】
【数３】
2005004658.tif 000005
【００２４】
【数４】
2005004658.tif 000006
【００２５】
ただし、数５であり、パラメータベクトルを、数６とおいた。
【００２６】
【数５】
2005004658.tif 000007
【００２７】
【数６】
2005004658.tif 000008
【００２８】
本発明の変化点探索装置は、ＡＲモデルに限らず、自己回帰移動平均（ＡＲＭＡ：Ａｕｔｏ  Ｒｅｇｒｅｓｓｉｏｎ  Ｍｏｖｉｎｇ  Ａｖｅｒａｇｅ）モデルや移動平均（ＭＡ：Ｍｏｖｉｎｇ  Ａｖｅｒａｇｅ）モデルのような他の時系列モデルを用いてもよい。
【００２９】
図３は、時系列モデル学習装置１１のより詳細な構成を示すブロック図である。この時系列モデル学習装置１１は、忘却型統計量計算装置１０１と、パラメータ更新装置１０２と、データ，パラメータ及び統計量記憶装置１０３とから構成されている。
【００３０】
図４は、図３の時系列モデル学習装置１１の概略動作を表すフローチャートであり、図１の時系列モデル学習装置１１は、以下のように動作する。
【００３１】
時系列モデル学習装置１１は、データの系列を逐次読み込みながら読み込んだデータに基づいて逐次的にパラメータを変更する。ここで、データｘ１からｘｔまでを用いて学習した結果得られるパラメータの値をΘ（ｔ）書く。時系列モデルをＡＲモデルとするときは、パラメータ値Θ（ｔ）を更新することができる。以下、その概要を述べる。
【００３２】
まず、データが読み込まれる前にデータ，パラメータ及び統計量記憶装置１０３に格納されている各パラメータの値が初期化される（ステップＳ１０１）。
【００３３】
次に、ｔ番目のデータｘｔが入力される度に、以下のように動作する。
【００３４】
データｘｔが、忘却型統計量計算装置１０１およびデータ，パラメータ及び統計量記憶装置１０３に入力されると（ステップＳ１０２）、データ，パラメータ及び統計量記憶装置１０３は、記憶していたデータのうち最も古いものを消去し、代わりに最新のデータｘｔを記憶し、データの列ｘｔ，ｘｔ−１，…，ｘｔ−ｋ＋１を得る。
【００３５】
忘却型統計量計算装置１０１は、データ，パラメータ及び統計量記憶装置１０３から供給されたデータ列ｘｔ，ｘｔ−１，…，ｘｔ−ｋ＋１と保持している十分統計量μ，Ｃｊ（ｊ＝０，…，ｋ）を数７および数８の更新ルールにより更新し（ステップ１０３）、得られた十分統計量をデータ，パラメータ及び統計量記憶装置１０３に送り込んで記憶させ、またパラメータ更新装置１０２に送り込む。
【００３６】
【数７】
2005004658.tif 000009
【００３７】
【数８】
2005004658.tif 000010
【００３８】
パラメータ更新装置１０２は、ｎ次正方行列Ｂｉ（ｉ＝１，…，ｋ）を未知数とする連立方程式である数９の解を求める。
【００３９】
【数９】
2005004658.tif 000011
【００４０】
ただし、数１０とする。
【００４１】
【数１０】
2005004658.tif 000012
【００４２】
次に、パラメータ更新装置１０２は、求めた解をＡｉに代入し、数１１および数１２によってパラメータを計算し（ステップ１０３）、得られたパラメータ値Θ＝（Ａ１，…，Ａｋ，μ，Σ）を出力する（ステップ１０４）。
【００４３】
【数１１】
2005004658.tif 000013
【００４４】
【数１２】
2005004658.tif 000014
【００４５】
また、このパラメータ値Θをデータ，パラメータ及び統計量記憶装置１０３に送り込んで記憶させる。
【００４６】
時系列モデル学習装置１１は、０から１までの値をとる忘却パラメータをτとして、過去の十分統計量を（１−τ）倍し、新しい十分統計量をτ倍して重み付き平均によって十分統計量を更新することにより推定パラメータ値を更新する装置であり、古いデータの影響を徐々に忘却する効果をもつ。忘却パラメータτを入力データ列中のｔ番目のデータｘｔに対しては、１／ｔとおくと、通常の最尤推定を逐次的に実行することに相当する。
【００４７】
時系列モデル学習装置１１が計算したパラメータ値Θは、コンプレキシティ及びパラメータ記憶装置１４に供給される。
【００４８】
損失関数計算装置１３は、各時点ｔにおける入力データｘｔに対して時系列モデル学習装置１１またはコンプレキシティ及びパラメータ記憶装置１４から時点前のパラメータ値Θ（ｔ−１）を読み込み、数１３のように損失を計算する（ステップＳ１３）。
【００４９】
【数１３】
2005004658.tif 000015
【００５０】
ここで計算された損失値は、時系列モデルのデータに対する当てはめ誤差の意味をもつ。この損失値は、コンプレキシティ計算装置１２に送り込まれ、各時点ｒに対して、コンプレキシティとして、数１４，数１５および数１６を計算する（ステップＳ１４）。
【００５１】
【数１４】
2005004658.tif 000016
【００５２】
【数１５】
2005004658.tif 000017
【００５３】
【数１６】
2005004658.tif 000018
【００５４】
ただし、数１７は、ｘｒ＋１，…，ｘｉ−１を用いて推定したパラメータの値を表している。
【００５５】
【数１７】
2005004658.tif 000019
【００５６】
この値も、また、時系列モデル学習装置１１によって計算され、その結果はコンプレキシティ及びパラメータ記憶装置１４に供給され記憶される。
【００５７】
数１４の値は、データ列ｘＮ＝ｘ１，ｘ２，…，ｘＮに対する予測的確率的コンプレキシティとよばれる量であり、データ列ｘＮを各ｘｔについてパラメータ値Θ（ｔ−１）を用いて逐次的に符号化したときの総符号長である。
【００５８】
ここで、数１８なる関係があるので、コンプレキシティ計算装置１２は、予測的確率的コンプレキシティの計算を逐次的に行うことができる。
【００５９】
【数１８】
2005004658.tif 000020
【００６０】
コンプレキシティ計算装置１２の計算結果は、コンプレキシティ及びパラメータ記憶装置１４に供給される。
【００６１】
変化点探索装置１５は、各時点ｒ（ｒ＝２，…，Ｎ）に対して、コンプレキシティ及びパラメータ記憶装置１４から供給された数１４，数１５および数１６の値を用いて変化点スコアＳＣＯＲＥ（ｒ）を計算する（ステップＳ１５）。変化点スコアＳＣＯＲＥ（ｒ）は、時点ｒが変化点である可能性の大きさを表す。例えば、数１９のように計算する。
【００６２】
【数１９】
2005004658.tif 000021
【００６３】
数１４で計算される値はデータ列ｘＮを単一のモデルで記述したときの予測的確率的コンプレキシティであるのに対し、数１５と数１６との和は時点ｒを境にして不連続にモデルを当てはめたときの予測的確率的コンプレキシティの総和である。
【００６４】
もし時点ｒが本当に変化点であれば、数１５と数１６との和は、数１４の値よりも有意に小さくなる。したがって、数１９が大きいほど時点ｒが変化点である可能性が高いことがわかる。
【００６５】
変化点探索装置１５は、例えばある閾値δを設けてＳＣＯＲＥ（ｒ）の値が閾値δより大の時点の中で最大の値をもつものを探索して、この時点ｒを変化点とみなしてこれを出力する（ステップＳ１６）。
【００６６】
この方法では、入力データ列ｘＮ中に１つ変化点を発見することができる。これを再帰的に行い、複数の変化点を見つけることもできる。
【００６７】
また、数１９の代わりに、数２０のようなスコアを考えることもできる。
【００６８】
【数２０】
2005004658.tif 000022
【００６９】
以上において、数１３では符号長を損失関数としているが、＾ｘｔを時点ｔのデータｘｔに対する予測値として、二乗損失関数である数２１を用いることもできる。
【００７０】
【数２１】
2005004658.tif 000023
【００７１】
さらに、一般の損失関数である数２２に置き換えてもよい。
【００７２】
【数２２】
2005004658.tif 000024
【００７３】
そのとき、予測的確率的コンプレキシティＥＳＣは、数２３のように一般の損失関数に関する累積予測損失に置き換えられる。以下は、一般にそのような場合に拡張されるものとする。
【００７４】
【数２３】
2005004658.tif 000025
【００７５】
［第２の実施の形態］
図５は、本発明の第２の実施の形態に係る変化点検出装置の構成を示すブロック図である。本実施の形態に係る変化点検出装置は、時系列モデル学習装置２１と、コンプレキシティ計算装置２２と、損失関数計算装置２３と、コンプレキシティ及びパラメータ記憶装置２４と、変化点判定装置２５とから構成され、データを逐次的に読み込み、過去に読み込んだデータ列の中に変化点を検出する。
【００７６】
図６は、第１の実施の形態に係る変化点検出装置の概略動作を示すフローチャートである。
【００７７】
なお、特に言及しない部分は、図１に示した第１の実施の形態に係る変化点検出装置における対応部分と同様に構成されているので、それらの詳しい説明は省略する。
【００７８】
次に、このように構成された第２の実施の形態に係る変化点検出装置の動作について、図５および図６を参照しながら説明する。
【００７９】
ステップＳ２１〜Ｓ２４の動作は基本的に図２のステップＳ１１〜Ｓ１４の動作と同じであるが、データの逐次的入力に伴い、計算を開始する時点が、変化点判定装置２５で最後に検出された変化点の時点であることと、終点が固定されたＮではなく、変化する時点ｔである点のみが異なる。
【００８０】
具体的には、時系列モデル学習装置２１では、パラメータを推定するのに、現時点のデータを取り込み（ステップＳ２１）、これと変化点判定装置２５で最後に検出された変化点の時点を入力として、これを開始点とし、現在の時点までのパラメータを時系列モデル学習装置１１と同様に逐次的に計算し（ステップＳ２２）、この値をコンプレキシティ及びパラメータ記憶装置２４に送り記憶させる。
【００８１】
損失関数計算装置２３は、入力データとコンプレキシティ及びパラメータ記憶装置２４から供給されたパラメータ値とを用いて、損失関数計算装置１３と同様に損失関数の値を計算して、コンプレキシティ計算装置２２に送る（ステップＳ２３）。
【００８２】
コンプレキシティ計算装置２２は、損失関数計算装置２３とコンプレキシティ及びパラメータ記憶装置２４との入力を受け、変化点判定装置２５で最後に検出された変化点の時点を入力として、これを開始点とし、現在の時点を終点とする、コンプレキシティの値を、コンプレキシティ計算装置１１と同様に計算する（ステップＳ２４）。
【００８３】
変化点判定装置２５は、現在の時点をｔとして、過去に変化点が見つかっていれば、その時点を起点とする範囲の中で変化点の探索を行う。すなわち、過去最後に検出した変化点をｖｉとすると、時点ｒ（ｖｉ＜ｒ＜ｔ）での変化点スコアＳＣＯＲＥ（ｒ；ｖｉ，ｔ）を計算する。変化点スコアＳＣＯＲＥ（ｒ；ｖｉ，ｔ）は、例えば、数２４のように計算する。
【００８４】
【数２４】
2005004658.tif 000026
【００８５】
そこで、時点ｒに関する最小化、数２５を考えて、あらかじめ与えられた閾値δを超えた場合、数２５の最小値を与える時点ｒにおいて変化点が起こったと判定し（ステップＳ２５）、変化点を出力する（ステップＳ２６）。
【００８６】
【数２５】
2005004658.tif 000027
【００８７】
そして、またデータを入力して、ステップＳ２１に戻る。
【００８８】
時点ｒの動く範囲はｖｉ＋１からｔ−１までとするが、ある幅Ｄを設けてｔ−Ｄからｔ−１までとすることにより、必要なメモリ量および計算量を一定以下にしてもよいとする。
【００８９】
変化点判定装置２５は、数２４を効率的に計算することができる。以下、その計算方法を説明する。ここで、データを１つ読み込んで行う計算手続きを、１イタレーションと呼ぶことにする。
【００９０】
データｘｔを新たに読み込んだ１イタレーションにおいて、時点ｒ＝ｔ−Ｄ，…，ｔ−１（またはｒ＝ｖｉ＋１，…，ｔ−１）について求められた数２６をコンプレキシティ及びパラメータ記憶装置２４に送り、記憶させる。
【００９１】
【数２６】
2005004658.tif 000028
【００９２】
次に、データｘｔ＋１を新たに読み込んだ１イタレーションにおいては、時点ｒ＝ｔ−Ｄ＋１，…，ｔ（またはｒ＝ｖｉ＋１，…，ｔ）について、数２７を求める。
【００９３】
【数２７】
2005004658.tif 000029
【００９４】
この際、数２８は、前のイタレーションで既に求めたものをコンプレキシティ及びパラメータ記憶装置２４から読み出して用いる。
【００９５】
【数２８】
2005004658.tif 000030
【００９６】
また、時点ｒ＝ｔについては、損失関数計算装置２３で求めた計算結果を用いて、数２９のように逐次的に計算して、これをコンプレキシティ及びパラメータ記憶装置２４に送り記憶させる。
【００９７】
【数２９】
2005004658.tif 000031
【００９８】
ここで、時系列モデルがＡＲモデルの場合、推定パラメータ値と同時に十分統計量も記憶させておけば、過去のデータを使わずに求められる。すなわち、古いデータは記憶しておく必要がない。
【００９９】
さらに、時点ｒ＝ｔ＋１については、損失関数計算装置２３で求めた計算結果を用いて、以下のように逐次的に計算する。
【０１００】
【数３０】
2005004658.tif 000032
【０１０１】
上記計算法では、常に２Ｄ個のＳＣの値を記憶しておき、１イタレーション毎にそのうち１＋Ｄ個を消去し、更新して得られるＤ個を新たに記憶することになる。
【０１０２】
すなわち、以下の量を記憶しておく。
【０１０３】
【数３１】
2005004658.tif 000033
【０１０４】
新たにデータｘｔ＋１を読み込んだときに、必要な量は、数３２であり、１行目において新たに計算すべき量は最後の１つのみである。
【０１０５】
【数３２】
2005004658.tif 000034
【０１０６】
２行目はすべての量を更新する必要があるが、それは、数３０と同様な計算を行うことで逐次的に行える。
【０１０７】
また、時点ｒの探索範囲を、整数Ｉで割り切れる値に制限することにより、記憶する数と更新する数を１／Ｉに削減することもできる。
【０１０８】
［第３の実施の形態］
図７は、本発明の第３の実施の形態に係る変化点検出装置の構成を示すブロック図である。本実施の形態に係る変化点検出装置は、図１に示した第１の実施の形態に係る変化点検出装置を実現するコンピュータ１００に対して、変化点検出用プログラム１１０を付加するようにした点だけが異なる。したがって、その他の特に言及しない部分には、同一符号を付してそれらの詳しい説明を省略する。
【０１０９】
変化点検出用プログラム１１０は、コンピュータ１００に読み込まれ、コンピュータ１００の動作を、時系列モデル学習装置１１，コンプレキシティ計算装置１２，損失関数計算装置１３，コンプレキシティ及びパラメータ記憶装置１４，および変化点探索装置１５を備える変化点検出装置として制御する。変化点検出用プログラム１１０の制御によるコンピュータ１００の動作は、第１の実施の形態における変化点検出装置の動作と全く同様になるので、その詳しい説明を割愛する。
【０１１０】
［第４の実施の形態］
図８は、本発明の第４の実施の形態に係る変化点検出装置の構成を示すブロック図である。本実施の形態に係る変化点検出装置は、図５に示した第２の実施の形態に係る変化点検出装置を実現するコンピュータ２００に対して、変化点検出用プログラム２１０を付加するようにした点だけが異なる。したがって、その他の特に言及しない部分には、同一符号を付してそれらの詳しい説明を省略する。
【０１１１】
変化点検出用プログラム２１０は、コンピュータ２００に読み込まれ、コンピュータ２００の動作を、時系列モデル学習装置２１，コンプレキシティ計算装置２２，損失関数計算装置２３，コンプレキシティ及びパラメータ記憶装置１４，および変化点探索装置１５を備える変化点検出装置として制御する。変化点検出用プログラム１１０の制御によるコンピュータ１００の動作は、第２の実施の形態における変化点検出装置の動作と全く同様になるので、その詳しい説明を割愛する。
【０１１２】
【発明の効果】
第１の効果は、オンラインで当てはめおよび当てはめ誤差を計算することができ、効率的に変化点検出ができることである。その理由は、逐次的に計算可能な予測的確率コンプレキシティを規準にして当てはめ誤差を計算し、これに基づいて変化点を検出しているためである。
【０１１３】
第２の効果は、モデルの非連続性に対応してモデル当てはめを行うことにより効果的に変化点を検出できることである。その理由は、変化点の前後で異なるモデルを当てはめ、その当てはめ誤差を予測的確率的コンプレキシティを用いて計算し、変化点がないと仮定した際のモデルの当てはめ誤差と比較することによって変化点を検出するためである。
【図面の簡単な説明】
【図１】本発明の第１の実施の形態に係る変化点検出装置の構成を示すブロック図である。
【図２】第１の実施の形態に係る変化点検出装置の動作を示すフローチャートである。
【図３】図１中の時系列モデル学習装置の構成を示すブロック図である。
【図４】図３の時系列モデルの学習装置の動作を示すフローチャートである。
【図５】本発明の第２の実施の形態に係る変化点検出装置の構成を示すブロック図である。
【図６】第２の実施の形態に係る変化点検出装置の変化点検出装置の動作を示すフローである。
【図７】本発明の第３の実施の形態に係る変化点検出装置の構成を示すブロック図である。
【図８】本発明の第４の実施の形態に係る変化点検出装置の構成を示すブロック図である。
【符号の説明】
１１  時系列モデル学習装置
１２  コンプレキシティ計算装置
１３  損失関数計算装置
１４  コンプレキシティ及びパラメータ記憶装置
１５  変化点探索装置
２１  時系列モデル学習装置
２２  コンプレキシティ計算装置
２２  コンプレキシティ及びパラメータ記憶装置
２３  損失関数計算装置
２４  コンプレキシティ及びパラメータ記憶装置
２５  変化点判定装置
１００，２００  コンピュータ
１０１  忘却型統計量計算装置
１０２  パラメータ更新装置
１０３  データ，パラメータ及び統計量記憶装置
１１０，２１０  変化点検出用プログラム
【図１】
2005004658.tif 000035
【図２】
2005004658.tif 000036
【図３】
2005004658.tif 000037
【図４】
2005004658.tif 000038
【図５】
2005004658.tif 000039
【図６】
2005004658.tif 000040
【図７】
2005004658.tif 000041
【図８】
2005004658.tif 000042