論文の概要: A Constant-per-Iteration Likelihood Ratio Test for Online Changepoint
Detection for Exponential Family Models
- arxiv url: http://arxiv.org/abs/2302.04743v1
- Date: Thu, 9 Feb 2023 16:24:12 GMT
- ステータス: 処理完了
- システム内更新日: 2023-02-10 15:17:35.101383
- Title: A Constant-per-Iteration Likelihood Ratio Test for Online Changepoint
Detection for Exponential Family Models
- Title（参考訳）: 指数型家族モデルにおけるオンライン切替点検出のための定点差分比検定
- Authors: Kes Ward, Gaetano Romano, Idris Eckley, Paul Fearnhead
- Abstract要約: FOCuSはガウスデータにおける平均値の変化を検出するために導入され、その値が1回あたりのコストを$O(log T)$に下げる。
アルゴリズムの最大化ステップを適応的に実行し、これらの可能性のある場所の小さな部分集合に対してテスト統計を最大化するだけでよいことを示す。
- 参考スコア（独自算出の注目度）: 1.376408511310322
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Online changepoint detection algorithms that are based on likelihood-ratio
tests have been shown to have excellent statistical properties. However, a
simple online implementation is computationally infeasible as, at time $T$, it
involves considering $O(T)$ possible locations for the change. Recently, the
FOCuS algorithm has been introduced for detecting changes in mean in Gaussian
data that decreases the per-iteration cost to $O(\log T)$. This is possible by
using pruning ideas, which reduce the set of changepoint locations that need to
be considered at time $T$ to approximately $\log T$. We show that if one wishes
to perform the likelihood ratio test for a different one-parameter exponential
family model, then exactly the same pruning rule can be used, and again one
need only consider approximately $\log T$ locations at iteration $T$.
Furthermore, we show how we can adaptively perform the maximisation step of the
algorithm so that we need only maximise the test statistic over a small subset
of these possible locations. Empirical results show that the resulting online
algorithm, which can detect changes under a wide range of models, has a
constant-per-iteration cost on average.
- Abstract（参考訳）: 確率比テストに基づくオンライン変更点検出アルゴリズムは、優れた統計特性を有することが示されている。
しかし、単純なオンライン実装は計算上不可能であり、時折$t$の場合、変更の場所として$o(t)$を考える必要がある。
近年, FOCuSアルゴリズムはガウス平均値の変化を検出するために導入され, 定位当たりのコストを$O(\log T)$に下げている。
これは、プランニング(pruning ideas)を使用することによって実現される。これにより、t$から約$\log t$までの時に考慮する必要がある変更点の場所のセットが削減される。
異なる1パラメータの指数関数的ファミリーモデルに対して確率比テストを実行したい場合、正確に同じプルーニング規則が使用できることを示し、繰り返して、イテレーション$t$で約$\log t$の位置を考慮すればよいことを示す。
さらに、アルゴリズムの最大化ステップを適応的に実行して、これらの可能な場所の小さな部分集合に対してテスト統計を最大化するだけでよいことを示す。
実験結果から,様々なモデルで変化を検出可能なオンラインアルゴリズムは,平均的に定値化コストがかかることがわかった。
関連論文リスト
- Adaptive $k$-nearest neighbor classifier based on the local estimation of the shape operator [49.87315310656657]
我々は, 局所曲率をサンプルで探索し, 周辺面積を適応的に定義する適応型$k$-nearest(kK$-NN)アルゴリズムを提案する。
多くの実世界のデータセットから、新しい$kK$-NNアルゴリズムは、確立された$k$-NN法と比較してバランスの取れた精度が優れていることが示されている。
論文 参考訳（メタデータ） (2024-09-08T13:08:45Z) - Online non-parametric likelihood-ratio estimation by Pearson-divergence
functional minimization [55.98760097296213]
iid 観測のペア $(x_t sim p, x'_t sim q)$ が時間の経過とともに観測されるような,オンラインな非パラメトリック LRE (OLRE) のための新しいフレームワークを提案する。
本稿では,OLRE法の性能に関する理論的保証と,合成実験における実証的検証について述べる。
論文 参考訳（メタデータ） (2023-11-03T13:20:11Z) - Modified Step Size for Enhanced Stochastic Gradient Descent: Convergence
and Experiments [0.0]
本稿では,$frac1sqrtttをベースとした変形ステップサイズを改良することにより,勾配降下法(SGD)アルゴリズムの性能向上に新たなアプローチを提案する。
提案されたステップサイズは対数的なステップ項を統合し、最終イテレーションでより小さな値を選択する。
提案手法の有効性について,FashionMNISTとARARを用いて画像分類タスクの数値実験を行った。
論文 参考訳（メタデータ） (2023-09-03T19:21:59Z) - Fast likelihood-based change point detection [0.949290364986276]
変化を示す尺度として、2つのモデル間の確率比を用いる。
最適な分割を見つけることは、$O(n)$ timeで行うことができ、$n$は最後の変更点からエントリの数である。
我々は、O(epsilon-1 log2 n)$ timeで(1-epsilon)$ approximationを出力する近似スキームを提案する。
論文 参考訳（メタデータ） (2023-01-21T05:13:35Z) - Sequential Gradient Descent and Quasi-Newton's Method for Change-Point
Analysis [0.348097307252416]
変更点を検出するための一般的なアプローチは、変更点の数と位置に関するコスト関数を最小化することである。
本稿では, 勾配降下法 (SeGD) と準ニュートン法 (SeN) とを結合し, コストを効果的に求める新しいシーケンシャル手法 (SE) を提案する。
論文 参考訳（メタデータ） (2022-10-21T20:30:26Z) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳（メタデータ） (2022-08-11T04:12:50Z) - Exact Paired-Permutation Testing for Structured Test Statistics [67.71280539312536]
構造化されたテスト統計群のペア置換テストに対して,効率的な正確なアルゴリズムを提案する。
我々の正確なアルゴリズムはモンテカルロ近似よりも10ドル速く、共通のデータセットに20000ドルのサンプルがある。
論文 参考訳（メタデータ） (2022-05-03T11:00:59Z) - Optimal network online change point localisation [73.93301212629231]
オンラインネットワーク変化点検出の問題点について検討する。
この設定では、独立したベルヌーイネットワークの集合が順次収集され、基礎となる変化点が生じる。
目的は、虚偽のアラームの数または確率の制約に応じて、それが存在する場合、変更点をできるだけ早く検出することです。
論文 参考訳（メタデータ） (2021-01-14T07:24:39Z) - Improved Sample Complexity for Incremental Autonomous Exploration in
MDPs [132.88757893161699]
我々は $epsilon$-optimal 目標条件付きポリシーのセットを学び、$ L$ ステップ内で段階的に到達可能なすべての状態を達成します。
DisCoは、コストに敏感な最短経路問題に対して$epsilon/c_min$-optimalポリシーを返すことができる最初のアルゴリズムです。
論文 参考訳（メタデータ） (2020-12-29T14:06:09Z) - Convergence of Online Adaptive and Recurrent Optimization Algorithms [0.0]
我々は、機械学習で使用されるいくつかの顕著な降下アルゴリズムの局所収束を証明した。
我々は確率的視点ではなく「エルゴディック」を採用し、確率分布の代わりに経験的な時間平均で作業する。
論文 参考訳（メタデータ） (2020-05-12T09:48:52Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。