論文の概要: Fast likelihood-based change point detection

• arxiv url: http://arxiv.org/abs/2301.08892v1
• Date: Sat, 21 Jan 2023 05:13:35 GMT
• ステータス: 処理完了
• システム内更新日: 2023-01-24 15:48:27.409498
• Title: Fast likelihood-based change point detection
• Title（参考訳）: 高速確率に基づく変化点検出
• Authors: Nikolaj Tatti
• Abstract要約: 変化を示す尺度として、2つのモデル間の確率比を用いる。 最適な分割を見つけることは、$O(n)$ timeで行うことができ、$n$は最後の変更点からエントリの数である。 我々は、O(epsilon-1 log2 n)$ timeで(1-epsilon)$ approximationを出力する近似スキームを提案する。
• 参考スコア（独自算出の注目度）: 0.949290364986276
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Change point detection plays a fundamental role in many real-world applications, where the goal is to analyze and monitor the behaviour of a data stream. In this paper, we study change detection in binary streams. To this end, we use a likelihood ratio between two models as a measure for indicating change. The first model is a single bernoulli variable while the second model divides the stored data in two segments, and models each segment with its own bernoulli variable. Finding the optimal split can be done in $O(n)$ time, where $n$ is the number of entries since the last change point. This is too expensive for large $n$. To combat this we propose an approximation scheme that yields $(1 - \epsilon)$ approximation in $O(\epsilon^{-1} \log^2 n)$ time. The speed-up consists of several steps: First we reduce the number of possible candidates by adopting a known result from segmentation problems. We then show that for fixed bernoulli parameters we can find the optimal change point in logarithmic time. Finally, we show how to construct a candidate list of size $O(\epsilon^{-1} \log n)$ for model parameters. We demonstrate empirically the approximation quality and the running time of our algorithm, showing that we can gain a significant speed-up with a minimal average loss in optimality.
• Abstract（参考訳）: 変更点検出は、データストリームの振る舞いを分析し監視することを目的として、多くの現実世界のアプリケーションで基本的な役割を果たす。 本稿では,バイナリストリームにおける変化検出について検討する。 このために、変化を示す尺度として、2つのモデル間の確率比を用いる。 第1モデルは単一のバーヌーリ変数であり、第2モデルは格納されたデータを2つのセグメントに分割し、各セグメントを独自のバーヌーリ変数でモデル化する。 最適な分割を見つけることは、$O(n)$ timeで行うことができ、$n$は最後の変更点からエントリの数である。 これは大きな$n$には高すぎる。 これに対抗するために、1- \epsilon)$O(\epsilon^{-1} \log^2n)$時間での近似を求める近似スキームを提案する。 まず、セグメント化問題から既知の結果を採用することにより、候補数を削減します。 次に、固定されたベルヌーリパラメータに対して、対数時間で最適な変化点を見つけることができることを示す。 最後に、モデルパラメータに対して$o(\epsilon^{-1} \log n)$の大きさの候補リストを構築する方法を示す。 我々はアルゴリズムの近似的な品質と実行時間を示し、最適性の平均損失を最小に抑えながら、大幅な高速化を達成できることを示した。

関連論文リスト

• Data subsampling for Poisson regression with pth-root-link [53.63838219437508]
  ポアソン回帰のためのデータサブサンプリング手法を開発し解析する。 特に,ポアソン一般化線形モデルと ID-および平方根リンク関数について考察する。
  論文  参考訳（メタデータ） (2024-10-30T10:09:05Z)
• Transfer Learning for Latent Variable Network Models [18.31057192626801]
  潜在変数ネットワークモデルにおける推定のための伝達学習について検討する。 潜伏変数が共有されている場合、エラーの消滅が可能であることを示す。 我々のアルゴリズムは、$o(1)$エラーを達成し、ソースやターゲットネットワーク上でパラメトリック形式を仮定しない。
  論文  参考訳（メタデータ） (2024-06-05T16:33:30Z)
• Turnstile $\ell_p$ leverage score sampling with applications [56.403488578703865]
  我々は,行列$AinmathbbRntimes d$の行をサンプリングする新しいアルゴリズムを開発した。 我々のアルゴリズムはサンプル行インデックスのセットを返すだけでなく、わずかに乱れた行を $tildea_i approx a_i$ で返却し、サンプリング確率を $varepsilon$ の相対誤差に近似する。 ロジスティック回帰のために、我々のフレームワークは$を達成した最初のアルゴリズムを得る。
  論文  参考訳（メタデータ） (2024-06-01T07:33:41Z)
• A statistical perspective on algorithm unrolling models for inverse problems [2.7163621600184777]
  観測値の条件分布が$bf y$で、興味のある変数が$bf x$であるような逆問題では、アルゴリズムのアンローリングを考える。 GDNsの最適統計性能に必要なアンローリング深さは、$log(n)/log(varrho_n-1)$で、$n$はサンプルサイズである。 また、潜伏変数 $bf x$ の負の対数密度が単純な近位演算子を持つとき、GDN は深さ $ でアンロールされることを示す。
  論文  参考訳（メタデータ） (2023-11-10T20:52:20Z)
• Data Structures for Density Estimation [66.36971978162461]
  p$のサブリニア数($n$)が与えられた場合、主な結果は$k$のサブリニアで$v_i$を識別する最初のデータ構造になります。 また、Acharyaなどのアルゴリズムの改良版も提供します。
  論文  参考訳（メタデータ） (2023-06-20T06:13:56Z)
• A Constant-per-Iteration Likelihood Ratio Test for Online Changepoint Detection for Exponential Family Models [1.376408511310322]
  FOCuSはガウスデータにおける平均値の変化を検出するために導入され、その値が1回あたりのコストを$O(log T)$に下げる。 アルゴリズムの最大化ステップを適応的に実行し、これらの可能性のある場所の小さな部分集合に対してテスト統計を最大化するだけでよいことを示す。
  論文  参考訳（メタデータ） (2023-02-09T16:24:12Z)
• Best Policy Identification in Linear MDPs [70.57916977441262]
  縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。 複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
  論文  参考訳（メタデータ） (2022-08-11T04:12:50Z)
• TURF: A Two-factor, Universal, Robust, Fast Distribution Learning Algorithm [64.13217062232874]
  最も強力で成功したモダリティの1つは、全ての分布を$ell$距離に近似し、基本的に最も近い$t$-piece次数-$d_$の少なくとも1倍大きい。 本稿では,この数値をほぼ最適に推定する手法を提案する。
  論文  参考訳（メタデータ） (2022-02-15T03:49:28Z)
• Optimal network online change point localisation [73.93301212629231]
  オンラインネットワーク変化点検出の問題点について検討する。 この設定では、独立したベルヌーイネットワークの集合が順次収集され、基礎となる変化点が生じる。 目的は、虚偽のアラームの数または確率の制約に応じて、それが存在する場合、変更点をできるだけ早く検出することです。
  論文  参考訳（メタデータ） (2021-01-14T07:24:39Z)
• SoS Degree Reduction with Applications to Clustering and Robust Moment Estimation [3.6042575355093907]
  我々は,新しい変数を導入することにより,二乗証明の総和の程度を大幅に減少させる汎用フレームワークを開発した。 クラスタリングとロバストモーメント推定という2つの重要な推定問題に対して,2乗和に基づくアルゴリズムを高速化する。
  論文  参考訳（メタデータ） (2021-01-05T13:49:59Z)
• Fair and Representative Subset Selection from Data Streams [4.53279507109072]
  ストリーム内のデータ項目が複数の不随意群に属する設定について検討する。 ストリーミングサブモジュラー問題の公平性を考慮した変種に対する効率的なアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-10-09T07:49:13Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。