以下は、提示された論文「Noise-contrastive Online Change Point Detection」の技術的な要約です。

論文要約：Noise-contrastive Online Change Point Detection

1. 問題設定

本論文は、**オンライン（逐次）変化点検出（Online Change Point Detection）**の問題に焦点を当てています。

• 状況: 観測者 $X_1, X_2, \dots$ が逐次的に到来します。ある未知の時刻 $\tau^*$ を境に、事前分布 $p$ から事後分布 $q$ へと分布が変化します（$\tau^*$ は統計家には不明）。
• 目的: 偽警報（False Alarm）の発生頻度を許容可能なレベルに抑えつつ、変化点 $\tau^*$ の発生を可能な限り速く検知し、停止時刻 $\hat{\tau}$ を報告することです。
• 既存手法の限界:
  • 多くの既存手法は、平均シフト検出やパラメトリックなモデル（正規分布族など）に依存しており、実世界の複雑な非パラメトリックな分布変化には適用が困難です。
  • 非パラメトリック手法（密度比推定など）の多くは「スライディングウィンドウ」方式を採用しており、オフライン解析では優れていますが、オンライン検出においては検出遅延（Detection Delay）が大きくなる傾向があります。
  • 非漸近的な高確率での検出遅延の理論的保証が不足しているケースが多いです。

2. 提案手法：ノイズ対照的アプローチ（Noise-Contrastive Approach）

著者らは、事前分布と事後分布の間の不一致度を最大化するアイデアに基づき、ノイズ対照的アプローチを用いた新しいアルゴリズム（FALCON）を提案しました。

2.1 核心的なアイデア

• 識別子（Discriminator）の学習:
  事前分布 $p$ と事後分布 $q$ を区別する関数 $D: \mathcal{X} \to (0, 1)$ を学習します。これは、生成モデルや密度推定で用いられる「ノイズ対照的学習」の概念を応用しています。
• 統計量の定義:
  候補となる変化点 $\tau$ に対して、クロスエントロピーを最大化する関数 $D$ を選び、その値を統計量として利用します。具体的には、以下の対数尤度比のような量を最大化します：
  $$\frac{\tau(t-\tau)}{t} \left[ \frac{1}{\tau}\sum_{s=1}^\tau \log(2D(X_s)) + \frac{1}{t-\tau}\sum_{s=\tau+1}^t \log(2 - 2D(X_s)) \right]$$
  この最大化問題は、$D$ をパラメトリックな関数族（例：$\theta^T \psi(x)$ をシグモイド関数に通したもの）で近似することで、**オンライン凸最適化（Online Convex Optimization, OCO）**の枠組みに帰着されます。

2.2 アルゴリズムの概要（Algorithm 2.2: FALCON）

1. 入力: OCO アルゴリズム $A$（例：ONS, FTAL）、決定領域 $\Theta$、閾値 $z$。
2. 逐次処理:
   • 各時刻 $t$ で新しい観測 $X_t$ を受け取る。
   • 各候補変化点 $\tau \in \{1, \dots, t-1\}$ に対して、OCO アルゴリズムを用いて損失関数 $\phi_{\tau, t}(\theta)$ を最小化（または統計量を最大化）するパラメータ $\hat{\theta}_{\tau, t}$ を更新する。
   • 統計量 $\hat{S}_t = \max_{1 \le \tau \le t-1} \hat{T}_{\tau, t}$ を計算する。ここで $\hat{T}_{\tau, t}$ は OCO による近似最大化値です。
   • もし $\hat{S}_t > z$ なら変化点を検知して停止。そうでなければパラメータを更新し続ける。
3. 計算効率の向上:
   従来の方法では各ステップで全 $\tau$ に対して最適化を最初から行う必要があり計算コストが高かったが、OCO を用いることで前回の結果を再利用する再帰的な更新が可能となり、計算量が大幅に削減されます。また、$\tau$ の探索範囲を制限する（$\tau \ge t - 2\tau_{\min}$）ことでさらに高速化できます。

3. 主な貢献と理論的保証

本論文の最大の貢献は、非漸近的な理論的保証の提供にあります。

• 非漸近的な大偏差 bound の導出:
  • 平均走行長（Average Running Length）: 偽警報が発生するまでの期待ステップ数について、高確率で下界を与える定理（Theorem 3.1, 3.3）を証明しました。これにより、閾値 $z$ の適切な設定が可能になります。
  • 検出遅延（Detection Delay）: 変化が発生した場合、検出までの遅延 $\hat{\tau} - \tau^*$ について、高確率での上界を導出しました。
• 理論的性質:
  • 検出遅延は、分布間のジェンセン・シャノンダイバージェンス（JS 発散）と、関数族 $\{\theta^T \psi(x)\}$ による $\log(p/q)$ の近似精度に依存することが示されました。
  • OCO アルゴリズムの「後悔（Regret）」が検出性能に直接影響を与えることを明らかにし、ONS（Online Newton Step）や FTAL（Follow the Approximate Leader）などのアルゴリズムが有効であることを示唆しました。
• 汎用性:
  パラメトリックなモデル（平均シフトなど）から非パラメトリックな複雑な分布変化まで、関数 $\psi$ の選択次第で柔軟に対応可能です。

4. 数値実験結果

合成データおよび実データを用いた実験で、提案手法（FALCON）の性能を KLIEP（密度比推定ベース）、M-statistic（カーネル法）、CUSUM（パラメトリック）と比較しました。

• 合成データ（ガウス分布）:
  • 平均シフト検出: CUSUM に次ぐ、あるいは同等の性能を示しました。
  • 分散変化検出: CUSUM は適用不可ですが、FALCON は他の非パラメトリック手法（KLIEP, M-statistic）を大幅に上回る検出遅延の短さを実現しました。
• 実データ:
  • 音声データ（CENSREC-1-C）: 雑音混入下でも安定して変化を検知し、KLIEP よりも優れた性能を示しました。
  • 活動認識（WISDM）: スマートフォンの加速度データからユーザーの活動変化を検知。FALCON は偽警報数が少なく、検出遅延も最短またはそれに準ずる性能でした。
  • 部屋 occupancy 検出: 温度、湿度、CO2 などの多変量データにおいて、FALCON は他の手法よりも短い検出遅延と低い偽警報率を達成しました。

5. 意義と結論

本論文は、オンライン変化点検出の分野において以下の点で重要な意義を持っています。

1. 理論的厳密性: 非漸近的な高確率 bound を提供し、実用的な閾値設定と性能予測を可能にしました。
2. 計算効率と精度の両立: オンライン凸最適化を活用することで、従来の非パラメトリック手法が抱えていた「計算コストの高さ」と「検出遅延の大きさ」というトレードオフを解決しました。
3. 汎用性の高さ: 分布の仮定を最小限に抑えつつ、多様なデータタイプ（単変量、多変量、パラメトリック、非パラメトリック）に対してロバストな検出を実現しました。

結論として、提案された FALCON アルゴリズムは、理論的な保証と実データでの高い性能を兼ね備えた、オンライン変化点検出のための強力な手法です。