Early structural change detection as an optimal stopping problem: solution theorem and its proof using reduction to absurdity | Artificial Life and Robotics Skip to main content
Springer Nature Link
Log in

Early structural change detection as an optimal stopping problem: solution theorem and its proof using reduction to absurdity

  • Original Article
  • Published:
Artificial Life and Robotics Aims and scope Submit manuscript

Abstract

The change point detection (CPD) problem in a time series is when it is found that the structure of the data being generated has changed at some time and for some reason. We have formulated structural change detection in a time series as an optimal stopping problem using the concept of dynamic programming (DP), and we present the optimal solution and its correctness by numerical calculations. In this article, we present the solution theorem and its proof using reduction to absurdity.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

References

  1. Jana R, Dey S (2000) Change detection in Teletraffic Models. IEEE Trans Signal Processing 48(3):846–853

    Article  Google Scholar 

  2. Kruegel C, Vigna G (2003) Anomaly detection of web-based attacks. In: Proceedings of ACM conference on computer and communication security, pp 27–31, October

  3. Hirose S, Yamanishi K (2008) Latent variable mining with its applications to abnormal behavior detection. In: Proceedings of 2008 SIAM conference on data mining, pp 231–242, July

  4. Julish K, Dacier M (2002) Mining intrusion detection alarms for actionable knowledge. In: Proceedings of the eighth ACM SIGKDD international conference on knowledge discovery and data mining, pp 366–375, July

  5. Yamanishi K, Maruyama Y (2005) Dynamic syslog mining for network failure monitoring. In: Proceedings of the eleventh ACM SIGKDD international conference on knowledge discovery and data mining, pp 499–508, August

  6. Kawano H, Hattori T, Nishimatsu K (2004) Novel method for structural change detection in time series using DP with an action cost. Proceedings of the IEEE international symposium on communications and information technologies 2004 (ISCIT 2004), October 26–29, pp 114–119, IEEE Catalog No. 04EX897C, Sapporo, Japan

  7. Hattori T, Takeda K, Tetsuya I, et al (2010) Early structural change detection as an optimal stopping problem. I. Formulation using dynamic programming with action cost. Proceedings of the 15th international symposium on artificial life and robotics (AROB15th’10), February 4–6, pp 763–766

Download references

Author information

Authors and Affiliations

  1. NTT Advanced Technology, 19-18 Nakamachi, Musashino, Tokyo, 180-0006, Japan

    Hiromichi Kawano

  2. Graduate School of Engineering, Kagawa University, Kagawa, Japan

    Tetsuo Hattori & Katsunori Takeda

  3. Micro Technica Co., Tokyo, Japan

    Tetsuya Izumi

Authors
  1. Hiromichi Kawano
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Tetsuo Hattori
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Katsunori Takeda
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Tetsuya Izumi
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Hiromichi Kawano.

Additional information

This work was presented in part at the 15th International Symposium on Artificial Life and Robotics, Oita, Japan, February 4–6, 201

About this article

Cite this article

Kawano, H., Hattori, T., Takeda, K. et al. Early structural change detection as an optimal stopping problem: solution theorem and its proof using reduction to absurdity. Artif Life Robotics 15, 425–430 (2010). https://doi.org/10.1007/s10015-010-0835-2

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10015-010-0835-2

Key words

Search

Navigation