We consider the problem of quickest change detection (QCD) in a signal where its observations are obtained using a set of actions, and switching from one action to another comes with a cost. The objective is to design a stopping rule consisting of a sampling policy to determine the sequence of actions used to observe the signal and a stopping time to quickly detect for the change, subject to a constraint on the average observation-switching cost. We propose an open-loop sampling policy of finite window size and a generalized likelihood ratio (GLR) Cumulative Sum (CuSum) stopping time for the QCD problem. We show that the GLR CuSum stopping time is asymptotically optimal with a properly designed sampling policy and formulate the design of this sampling policy as a quadratic programming problem. We prove that it is sufficient to consider policies of window size not more than one when designing policies of finite window size and propose several algorithms that solve this optimization problem with theoretical guarantees. For observation-dependent policies, we propose a $2$-threshold stopping time and an observation-dependent sampling policy. We present a method to design the observation-dependent sampling policy based on open-loop sampling policies. Finally, we apply our approach to the problem of QCD of a partially observed graph signal and empirically demonstrate the performance of our proposed stopping times.


翻译:我们在一个信号中考虑最快速变化探测(QCD)的问题,该信号的观测是通过一套行动获得的,而从一种行动转换到另一种行动则需要一定的成本。我们的目标是设计一个停止规则,由抽样政策组成,以确定用于观察信号的行动顺序和为变化快速探测的停止时间,但以平均观测开关费用为限制条件。我们提出一个开放环抽样政策,即窗口的有限尺寸和普遍可能性比率(GLR)累积总和(Cusum)停止QCD问题的时间。我们表明,GLR Cusum停止时间与适当设计的取样政策相比是极其理想的。我们提出一种方法,用以设计基于观察-CD的取样政策,作为四面形规划问题。我们证明,在设计有限的窗口规模政策时,只要考虑一个不大于一个的窗口尺寸的政策就足够了,并提出若干算法,用理论保证解决这一最优化问题。关于观察依赖的政策,我们提出一个$$2$-小时的停止时间和观察依赖抽样的政策。我们提出了一个方法,用以设计我们所观察到的基于观测-Q检验的抽样政策,最后展示我们所观察到的检验的进度。

0
下载
关闭预览

相关内容

Python编程基础,121页ppt
专知会员服务
48+阅读 · 2021年1月1日
专知会员服务
50+阅读 · 2020年12月14日
【干货书】机器学习速查手册,135页pdf
专知会员服务
125+阅读 · 2020年11月20日
【经典书】C语言傻瓜式入门(第二版),411页pdf
专知会员服务
51+阅读 · 2020年8月16日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
【新书】Python编程基础,669页pdf
专知会员服务
193+阅读 · 2019年10月10日
已删除
将门创投
4+阅读 · 2019年11月20日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
在清华入党的那些事
清华大学研究生教育
14+阅读 · 2019年3月20日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
无监督元学习表示学习
CreateAMind
27+阅读 · 2019年1月4日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
Soft-NMS – Improving Object Detection With One Line of Code
统计学习与视觉计算组
6+阅读 · 2018年3月30日
Focal Loss for Dense Object Detection
统计学习与视觉计算组
11+阅读 · 2018年3月15日
Arxiv
0+阅读 · 2021年3月12日
Arxiv
0+阅读 · 2021年3月12日
Implicit Maximum Likelihood Estimation
Arxiv
7+阅读 · 2018年9月24日
VIP会员
相关VIP内容
Python编程基础,121页ppt
专知会员服务
48+阅读 · 2021年1月1日
专知会员服务
50+阅读 · 2020年12月14日
【干货书】机器学习速查手册,135页pdf
专知会员服务
125+阅读 · 2020年11月20日
【经典书】C语言傻瓜式入门(第二版),411页pdf
专知会员服务
51+阅读 · 2020年8月16日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
【新书】Python编程基础,669页pdf
专知会员服务
193+阅读 · 2019年10月10日
相关资讯
已删除
将门创投
4+阅读 · 2019年11月20日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
在清华入党的那些事
清华大学研究生教育
14+阅读 · 2019年3月20日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
无监督元学习表示学习
CreateAMind
27+阅读 · 2019年1月4日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
Soft-NMS – Improving Object Detection With One Line of Code
统计学习与视觉计算组
6+阅读 · 2018年3月30日
Focal Loss for Dense Object Detection
统计学习与视觉计算组
11+阅读 · 2018年3月15日
Top
微信扫码咨询专知VIP会员