gms | German Medical Science

49. Jahrestagung der Deutschen Gesellschaft für Medizinische Informatik, Biometrie und Epidemiologie (gmds)
19. Jahrestagung der Schweizerischen Gesellschaft für Medizinische Informatik (SGMI)
Jahrestagung 2004 des Arbeitskreises Medizinische Informatik (ÖAKMI)

Deutsche Gesellschaft für Medizinische Informatik, Biometrie und Epidemiologie
Schweizerische Gesellschaft für Medizinische Informatik (SGMI)

26. bis 30.09.2004, Innsbruck/Tirol

Change point estimation by template matching: some basic aspects

Meeting Abstract (gmds2004)

Suche in Medline nach

  • presenting/speaker Heiko Hofer - Universität der Bundeswehr München, Neubiberg, Deutschland
  • Gerhard Staude - Universität der Bundeswehr München, Neubiberg, Deutschland
  • corresponding author Werner Wolf - Universität der Bundeswehr München, Neubiberg, Deutschland

Kooperative Versorgung - Vernetzte Forschung - Ubiquitäre Information. 49. Jahrestagung der Deutschen Gesellschaft für Medizinische Informatik, Biometrie und Epidemiologie (gmds), 19. Jahrestagung der Schweizerischen Gesellschaft für Medizinische Informatik (SGMI) und Jahrestagung 2004 des Arbeitskreises Medizinische Informatik (ÖAKMI) der Österreichischen Computer Gesellschaft (OCG) und der Österreichischen Gesellschaft für Biomedizinische Technik (ÖGBMT). Innsbruck, 26.-30.09.2004. Düsseldorf, Köln: German Medical Science; 2004. Doc04gmds339

Die elektronische Version dieses Artikels ist vollständig und ist verfügbar unter: http://www.egms.de/de/meetings/gmds2004/04gmds339.shtml

Veröffentlicht: 14. September 2004

© 2004 Hofer et al.
Dieser Artikel ist ein Open Access-Artikel und steht unter den Creative Commons Lizenzbedingungen (http://creativecommons.org/licenses/by-nc-nd/3.0/deed.de). Er darf vervielfältigt, verbreitet und öffentlich zugänglich gemacht werden, vorausgesetzt dass Autor und Quelle genannt werden.


Gliederung

Text

Introduction

Change point detection and estimation are important signal processing functions in system monitoring, which includes the area of patient monitoring as well as rehabilitation supervision etc. An excellent overview about the general issue of change detection is given by [1]. In monitoring, the robust detection of a change in signal characteristics is the core task, since an undetected change cannot be further analysed. As detection algorithms usually run online and give alarm when a change has occurred, due to causality this alarm time is delayed with the respect to the real change time per se. But the change alarm can trigger the estimation algorithm which analyses the signal segment from the present alarm time t a back to the previous alarm, in order to estimate the exact time when the detected change really happened (step-like change) or started (ramp change). Usually, the maximum likelihood (ML) method is used by the estimation unit; it computes the likelihood of a change for each time instant and the most likely one is taken as the estimate of change onset time. The reliability of this method is widely discussed in literature for step-like changes.

But in practical applications, those ideal abrupt changes do not happen, since due to the limited energy which is instantaneously available (e.g., peak current of a battery during a impulse-like shortcut), the dynamics of a system is limited. But those non-abrupt changes, i.e. the ramp-step functions, need an additional parameter to be estimated, namely the rise time of the change. The contribution of this paper is to show how the rise time influences the estimate of the change point depending on the change model, namely the step, the ramp-step and the ramp profile model.

Methods and Results

The signal is assumed a sequence of independent random variables X 1 , X 2 , ... , X t a which are (μ(i,Θ),σ2) distributed, with an unknown but constant variance σ2. Furthermore, the parameters Θi of the underlying stochastic processes are unknown. The density function of the whole sequence f θ (x 1 , x 2 , ... , x t a) with x 1 , x 2 , ... , x t a being samples of the processes X 1 , X 2 , ... , X t a depends on these deterministic parameters. Since the random variables X i are independent, the density function can be simplified to the product of the single density functions:

(1) Equation 1

The maximum likelihood method now tries to estimate θ from a concrete sample process x 1 , x 2 , ... , x t a of the sequence.

[Fig. 1]

Hence, the estimation of the change point using the ramp-step template is a maximization over t0 and rt. [Fig. 2]

(2) Equation 2

An algorithm with two combined maximizations is quite expensive, since computational complexity follows a quadratic law in this case. But this template based algorithm can easily be extended to more complex profiles of change templates (e.g. sigmoid).

Figure 3 [Fig. 3] displays the estimation error Δt 0 = t 0 est - t 0 versus the rise time rt of the used change template; i.e. for every rise time value rt , maximization of Equ (2) is done for t 0 and α. A bias free estimation is obtained at the optimal rise time rt opt , where the rise time of the template and the rise time of the signal match. If the change slope of the template is steeper rt < rt opt , a positive bias Δt 0 is obtained and v.v. The location of the change template is determined by the ML such that the mean square Euclidean distance between template and signal is minimal. As a consequence, also the estimated scaling factor (template magnitude) α matches the real step magnitude in the case rt = rt opt , but is underestimated for rt < rt opt, and overestimated for rt > rt opt, according to Figure 3 [Fig. 3] (right diagram).

Figure 4 [Fig. 4] displays the likelihood together with the estimation error Δt 0. Obviously, the lowest likelihood found for templates with rt rt ramp does not correspond to the maximum error Δt 0 which is obtained for templates with rt * < rt < rt ramp. Even if this finding is astonishing, the reason is clear: the interdependence of both estimated parameters t 0 and α through the limitation given by t a. But the likelihood can certainly be used for the change point estimation, since both parameters are correctly estimated in the case rt opt .

Discussion

Certainly, the results of the deterministic (noise free) case shown serves to demonstrate the behavior of the algorithm analytically, but of more practical evidence are noisy signals which are to be investigated in future. But a recent corresponding report [2] focusing on signals that change from an initial state to a different (active) state with an unknown but constant velocity indicate the relevance of this topic for future work.


References

1.
M. Basseville, I. Nikiforov Detection of abrupt changes: theory and application. Prentice-Hall, Englewood-Cliffs, N.J. 1993
2.
V.K. Jandhyala, S.B. Fotopoulos, N.E. Evaggelopoulos A comparison of unconditional and conditional solutions to the maximum likelihood estimation of a change-point. Comput Stat Data An,34, 315-334, 2000.