論文の概要: Sequential Community Mode Estimation
- arxiv url: http://arxiv.org/abs/2111.08535v1
- Date: Tue, 16 Nov 2021 15:05:40 GMT
- ステータス: 処理完了
- システム内更新日: 2021-11-17 18:47:29.368659
- Title: Sequential Community Mode Estimation
- Title(参考訳): 逐次的コミュニティモード推定
- Authors: Shubham Anand Jain, Shreyas Goenka, Divyam Bapna, Nikhil
Karamchandani, Jayakrishnan Nair
- Abstract要約: 本研究では,集団内最大の集団を個体の連続的無作為なサンプリングによって同定する問題について検討する。
この問題に対する新しいアルゴリズムを提案し,解析し,任意のアルゴリズムの下でエラーの確率に関する情報理論の下限を確立する。
- 参考スコア(独自算出の注目度): 7.693649834261879
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We consider a population, partitioned into a set of communities, and study
the problem of identifying the largest community within the population via
sequential, random sampling of individuals. There are multiple sampling
domains, referred to as \emph{boxes}, which also partition the population. Each
box may consist of individuals of different communities, and each community may
in turn be spread across multiple boxes. The learning agent can, at any time,
sample (with replacement) a random individual from any chosen box; when this is
done, the agent learns the community the sampled individual belongs to, and
also whether or not this individual has been sampled before. The goal of the
agent is to minimize the probability of mis-identifying the largest community
in a \emph{fixed budget} setting, by optimizing both the sampling strategy as
well as the decision rule. We propose and analyse novel algorithms for this
problem, and also establish information theoretic lower bounds on the
probability of error under any algorithm. In several cases of interest, the
exponential decay rates of the probability of error under our algorithms are
shown to be optimal up to constant factors. The proposed algorithms are further
validated via simulations on real-world datasets.
- Abstract(参考訳): 我々は、集団を一組の共同体に分割し、個体の連続的無作為なサンプリングを通して、集団内の最大のコミュニティを特定する問題を研究する。
複数のサンプリングドメインがあり、これを 'emph{boxes} と呼び、人口を分割する。
各ボックスは異なるコミュニティの個人で構成され、各コミュニティは複数のボックスにまたがる可能性がある。
学習エージェントは、任意の選択されたボックスからランダムな個人を(置き換えて)サンプリングすることができる。
エージェントの目標は、サンプリング戦略と決定ルールの両方を最適化することで、最大のコミュニティを \emph{fixed budget} 設定で誤識別する可能性を最小限に抑えることである。
この問題に対する新しいアルゴリズムを提案し,解析し,任意のアルゴリズムの下でエラーの確率に関する情報理論の下限を確立する。
興味のある場合、アルゴリズムの下での誤差確率の指数的減衰速度は、定数因子まで最適であることが示されている。
提案アルゴリズムは実世界のデータセットのシミュレーションによってさらに検証される。
関連論文リスト
- Scalable Decentralized Algorithms for Online Personalized Mean Estimation [12.002609934938224]
本研究は,各エージェントが実数値分布からサンプルを収集し,その平均値を推定する,オーバーアーキシング問題の簡易版に焦点を当てた。
1つは信念の伝播からインスピレーションを得ており、もう1つはコンセンサスに基づくアプローチを採用している。
論文 参考訳(メタデータ) (2024-02-20T08:30:46Z) - Optimal Multi-Distribution Learning [88.3008613028333]
マルチディストリビューション学習は、$k$の異なるデータ分散における最悪のリスクを最小限に抑える共有モデルを学ぶことを目指している。
本稿では, (d+k)/varepsilon2の順に, サンプルの複雑さを伴って, ヴァレプシロン最適ランダム化仮説を導出するアルゴリズムを提案する。
論文 参考訳(メタデータ) (2023-12-08T16:06:29Z) - Bivariate Estimation-of-Distribution Algorithms Can Find an Exponential
Number of Optima [12.009357100208353]
本稿では,最適化アルゴリズムが大規模最適集合を処理する方法の研究を支援するために,テスト関数EqualBlocksOneMax(EBOM)を提案する。
EBOM は EBOM の理論的に理想的なモデルと非常によく似ており、このモデルは同じ最大確率で指数的に多くの最適値のそれぞれをサンプリングする。
論文 参考訳(メタデータ) (2023-10-06T06:32:07Z) - Factorization of Multi-Agent Sampling-Based Motion Planning [72.42734061131569]
現代のロボティクスは、共有環境内で複数のエンボディエージェントを動作させることが多い。
標準的なサンプリングベースのアルゴリズムは、ロボットの関節空間における解の探索に使用できる。
我々は、因子化の概念をサンプリングベースアルゴリズムに統合し、既存の手法への最小限の変更しか必要としない。
本稿では, PRM* のサンプル複雑性の観点から解析的ゲインを導出し, RRG の実証結果を示す。
論文 参考訳(メタデータ) (2023-04-01T15:50:18Z) - Is it easier to count communities than find them? [82.90505487525533]
コミュニティ構造が異なるモデル間の仮説テスト問題について考察する。
2つの選択肢間のテストは、コミュニティを見つけるのと同じくらい難しいことを示しています。
論文 参考訳(メタデータ) (2022-12-21T09:35:19Z) - BRIO: Bringing Order to Abstractive Summarization [107.97378285293507]
非決定論的分布を前提とした新しい学習パラダイムを提案する。
提案手法は, CNN/DailyMail (47.78 ROUGE-1) と XSum (49.07 ROUGE-1) のデータセット上で, 最新の結果が得られる。
論文 参考訳(メタデータ) (2022-03-31T05:19:38Z) - Optimal Clustering with Bandit Feedback [57.672609011609886]
本稿では,バンディットフィードバックを用いたオンラインクラスタリングの問題点について考察する。
これは、NPハード重み付きクラスタリング問題をサブルーチンとして解決する必要性を回避するための、シーケンシャルなテストのための新しい停止規則を含む。
合成および実世界のデータセットの広範なシミュレーションを通して、BOCの性能は下界と一致し、非適応的ベースラインアルゴリズムよりも大幅に優れることを示す。
論文 参考訳(メタデータ) (2022-02-09T06:05:05Z) - Population based change-point detection for the identification of
homozygosity islands [0.0]
本稿では,動的プログラミングアルゴリズムで効率的に計算したり,高速なグリーディ二分法アルゴリズムで近似できるペナル化最大可能性法を提案する。
両アルゴリズムは、確率ベクトルの分布と独立サンプリングに関する非常に一般的な仮定の下で、ほぼ確実に変化点の集合に収束することを示す。
この新しいアプローチは、集団内の個人のゲノム上のホモ接合性島を同定する問題によって動機付けられている。
論文 参考訳(メタデータ) (2021-11-19T12:53:41Z) - Local policy search with Bayesian optimization [73.0364959221845]
強化学習は、環境との相互作用によって最適な政策を見つけることを目的としている。
局所探索のための政策勾配は、しばしばランダムな摂動から得られる。
目的関数の確率モデルとその勾配を用いたアルゴリズムを開発する。
論文 参考訳(メタデータ) (2021-06-22T16:07:02Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。