Data-Driven Quickest Change Detection in Hidden Markov Models

Qi Zhang; Zhongchang Sun; Luis C. Herrera; Shaofeng Zou

doi:10.1109/ISIT54713.2023.10206588

Data-Driven Quickest Change Detection in Hidden Markov Models

Qi Zhang
, Zhongchang Sun
, Luis C. Herrera
, Shaofeng Zou

SUNY Buffalo

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

5 Scopus citations

Abstract

The problem of quickest change detection in hidden Markov models (HMMs) is investigated. A sequence of samples are generated from a HMM, and at some unknown time, the transition kernel and/or the emission probability of the HMM changes. The goal is to detect the change as soon as possible subject to false alarm constraints. The data-driven setting is investigated, where none of the pre-, post-change Markov transition kernels or the emission probabilities are known. In this paper, a kernel based data-driven algorithm is developed. Performance bounds on its average running length (ARL) to false alarm and worst-case average detection delay (WADD) are theoretically characterized, where the WADD is at most of the order of the logarithm of the ARL. Numerical results are provided to validate the performance of the proposed algorithm.

Original language	English
Title of host publication	2023 IEEE International Symposium on Information Theory, ISIT 2023
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	2643-2648
Number of pages	6
ISBN (Electronic)	9781665475549
DOIs	https://doi.org/10.1109/ISIT54713.2023.10206588
State	Published - 2023
Event	2023 IEEE International Symposium on Information Theory, ISIT 2023 - Taipei, Taiwan, Province of China Duration: Jun 25 2023 → Jun 30 2023

Publication series

Name	IEEE International Symposium on Information Theory - Proceedings
Volume	2023-June
ISSN (Print)	2157-8095

Conference

Conference	2023 IEEE International Symposium on Information Theory, ISIT 2023
Country/Territory	Taiwan, Province of China
City	Taipei
Period	06/25/23 → 06/30/23

Keywords

Kernel Method
Maximum Mean Discrepancy
Non-i.i.d
Sequential Change Detection

Access to Document

10.1109/ISIT54713.2023.10206588

Cite this

Zhang, Q., Sun, Z., Herrera, L. C., & Zou, S. (2023). Data-Driven Quickest Change Detection in Hidden Markov Models. In 2023 IEEE International Symposium on Information Theory, ISIT 2023 (pp. 2643-2648). (IEEE International Symposium on Information Theory - Proceedings; Vol. 2023-June). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ISIT54713.2023.10206588

@inproceedings{eb713934656c468a91a13c03392b34c4,

title = "Data-Driven Quickest Change Detection in Hidden Markov Models",

abstract = "The problem of quickest change detection in hidden Markov models (HMMs) is investigated. A sequence of samples are generated from a HMM, and at some unknown time, the transition kernel and/or the emission probability of the HMM changes. The goal is to detect the change as soon as possible subject to false alarm constraints. The data-driven setting is investigated, where none of the pre-, post-change Markov transition kernels or the emission probabilities are known. In this paper, a kernel based data-driven algorithm is developed. Performance bounds on its average running length (ARL) to false alarm and worst-case average detection delay (WADD) are theoretically characterized, where the WADD is at most of the order of the logarithm of the ARL. Numerical results are provided to validate the performance of the proposed algorithm.",

keywords = "Kernel Method, Maximum Mean Discrepancy, Non-i.i.d, Sequential Change Detection",

author = "Qi Zhang and Zhongchang Sun and Herrera, \{Luis C.\} and Shaofeng Zou",

note = "Publisher Copyright: {\textcopyright} 2023 IEEE.; 2023 IEEE International Symposium on Information Theory, ISIT 2023 ; Conference date: 25-06-2023 Through 30-06-2023",

year = "2023",

doi = "10.1109/ISIT54713.2023.10206588",

language = "English",

series = "IEEE International Symposium on Information Theory - Proceedings",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "2643--2648",

booktitle = "2023 IEEE International Symposium on Information Theory, ISIT 2023",

address = "United States",

}

Zhang, Q, Sun, Z, Herrera, LC & Zou, S 2023, Data-Driven Quickest Change Detection in Hidden Markov Models. in 2023 IEEE International Symposium on Information Theory, ISIT 2023. IEEE International Symposium on Information Theory - Proceedings, vol. 2023-June, Institute of Electrical and Electronics Engineers Inc., pp. 2643-2648, 2023 IEEE International Symposium on Information Theory, ISIT 2023, Taipei, Taiwan, Province of China, 06/25/23. https://doi.org/10.1109/ISIT54713.2023.10206588

Data-Driven Quickest Change Detection in Hidden Markov Models. / Zhang, Qi; Sun, Zhongchang; Herrera, Luis C. et al.
2023 IEEE International Symposium on Information Theory, ISIT 2023. Institute of Electrical and Electronics Engineers Inc., 2023. p. 2643-2648 (IEEE International Symposium on Information Theory - Proceedings; Vol. 2023-June).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Data-Driven Quickest Change Detection in Hidden Markov Models

AU - Zhang, Qi

AU - Sun, Zhongchang

AU - Herrera, Luis C.

AU - Zou, Shaofeng

PY - 2023

Y1 - 2023

N2 - The problem of quickest change detection in hidden Markov models (HMMs) is investigated. A sequence of samples are generated from a HMM, and at some unknown time, the transition kernel and/or the emission probability of the HMM changes. The goal is to detect the change as soon as possible subject to false alarm constraints. The data-driven setting is investigated, where none of the pre-, post-change Markov transition kernels or the emission probabilities are known. In this paper, a kernel based data-driven algorithm is developed. Performance bounds on its average running length (ARL) to false alarm and worst-case average detection delay (WADD) are theoretically characterized, where the WADD is at most of the order of the logarithm of the ARL. Numerical results are provided to validate the performance of the proposed algorithm.

AB - The problem of quickest change detection in hidden Markov models (HMMs) is investigated. A sequence of samples are generated from a HMM, and at some unknown time, the transition kernel and/or the emission probability of the HMM changes. The goal is to detect the change as soon as possible subject to false alarm constraints. The data-driven setting is investigated, where none of the pre-, post-change Markov transition kernels or the emission probabilities are known. In this paper, a kernel based data-driven algorithm is developed. Performance bounds on its average running length (ARL) to false alarm and worst-case average detection delay (WADD) are theoretically characterized, where the WADD is at most of the order of the logarithm of the ARL. Numerical results are provided to validate the performance of the proposed algorithm.

KW - Kernel Method

KW - Maximum Mean Discrepancy

KW - Non-i.i.d

KW - Sequential Change Detection

UR - https://www.scopus.com/pages/publications/85171432753

U2 - 10.1109/ISIT54713.2023.10206588

DO - 10.1109/ISIT54713.2023.10206588

M3 - Conference contribution

AN - SCOPUS:85171432753

T3 - IEEE International Symposium on Information Theory - Proceedings

SP - 2643

EP - 2648

BT - 2023 IEEE International Symposium on Information Theory, ISIT 2023

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 2023 IEEE International Symposium on Information Theory, ISIT 2023

Y2 - 25 June 2023 through 30 June 2023

ER -

Data-Driven Quickest Change Detection in Hidden Markov Models

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this