日本フィジカルAI新聞

世界のフィジカルAIを、日本語で。

サンプリングarXiv:2509.24089

系統的エイリアスサンプリング:離散分布からの効率的で低分散なサンプリング手法

Systematic Alias Sampling: an efficient and low-variance way to sample from a discrete distribution

シェア:XThreadsFacebookLINEはてブBluesky

エイリアス法と系統的サンプリングを組み合わせ、離散分布から高速かつ低分散にサンプリングする手法を提案。粒子フィルタのリサンプリングなどに応用可能。

詳しい要約

1. どんなもの?

- 離散分布からの効率的・低分散なサンプリング手法の提案 - Alias method と systematic sampling(particle filter で使われる低分散リサンプリング)を組み合わせた手法 - 離散分布を対象とするが、連続分布の近似にも使えるため particle filter の proposal distribution(例:ロボティクスの motion model)への応用を想定 - ライブラリで一般的な cdf からの binary search や inversion 法より高速なサンプリングを狙う

2. 先行研究と比べてどこがすごい?

- 既存の cdf からの binary search や inversion 法と比較し、k サンプル抽出が最大で一桁(order of magnitude)高速 - multinomial sampling と比較して、経験分布関数の適合度で非常に有利な結果 - Alias method 単体ではなく systematic sampling と組み合わせる点が新規性 - particle filter のリサンプリングで使われる systematic sampling の低分散性を、離散分布サンプリング全般に持ち込む点が先行研究との違い

3. 技術・手法の肝は?

- Alias method の構造(各カテゴリを確率に応じて分割し O(1) でサンプル可能にする)を基盤とする - systematic sampling の考え方を用い、k サンプルを効率的かつ低分散に生成 - 生成された経験分布関数を modified Cramér-Von Mises goodness-of-fit statistic で評価 - 連続分布を離散近似することで、particle filter の proposal distribution からのサンプリングにも適用可能

4. どうやって有効だと検証した?

- 提案手法で生成した経験分布関数を modified Cramér-Von Mises goodness-of-fit statistic で評価 - multinomial sampling との比較で非常に有利な結果を示す - cdf からの binary search や inversion 法と比較し、k サンプル抽出が最大で一桁高速であることを示す - 具体的なベンチマーク条件や実験設定の詳細は要旨からは不明

5. 議論はある?

- 連続分布を離散近似して使う一般性と、particle filter の motion model などロボティクスへの応用可能性に言及 - 低分散性が empirical distribution function の適合度で示される点を主張 - 計算コストやメモリ、離散近似誤差、高次元やカテゴリ数増加時の挙動などの限界については要旨からは不明 - 具体的な議論や制約条件は要旨からは不明

6. 次に読むべき論文は?

- Alias method(Walker の Alias sampling)に関する原論文 - particle filter における systematic resampling の原論文・関連研究 - multinomial resampling と systematic resampling の比較研究 - Cramér-Von Mises goodness-of-fit statistic および modified 版の統計文献 - particle filter の proposal distribution 設計や motion model に関するロボティクス文献

※ AIが要旨から生成した要約です。正確性は原文をご確認ください。

著者: Ilari Vallivaara, Katja Poikselkä, Pauli Rikula, Juha Röning

分類: cs.DS, cs.MS, cs.RO

原文アブストラクト

In this paper we combine the Alias method with the concept of systematic sampling, a method commonly used in particle filters for efficient low-variance resampling. The proposed method allows very fast sampling from a discrete distribution: drawing k samples is up to an order of magnitude faster than binary search from the cumulative distribution function (cdf) or inversion methods used in many libraries. The produced empirical distribution function is evaluated using a modified Cram\'er-Von Mises goodness-of-fit statistic, showing that the method compares very favourably to multinomial sampling. As continuous distributions can often be approximated with discrete ones, the proposed method can be used as a very general way to efficiently produce random samples for particle filter proposal distributions, e.g. for motion models in robotics.

  1. 1Boston Dynamics、車輪付きAtlasの研究試作機を紹介研究・技術
  2. 2newmoとKDDIが資本業務提携 2028年に堺市で自動運転タクシー商用化目指す提携・買収
  3. 3NVIDIA、CoRLでGR00T 2とIsaac Lab 3.0を発表新製品・発表
  4. 4GXOとApptronik、Apolloの物流現場試験を拡大 最大1,000台の展開を構想量産・展開
  5. 5Google DeepMind、ロボット向けAIを発表新製品・発表

PR・アフィリエイト広告

MINISFORUM(ミニPC)

MINISFORUM(ミニPC)の公式広告バナーMINISFORUM公式ストアを見る ↗
PR本紙発行元 EmplifAI