論文の概要: Sequential Monte Carlo for Sampling Balanced and Compact Redistricting Plans

• arxiv url: http://arxiv.org/abs/2008.06131v5
• Date: Tue, 14 Feb 2023 22:40:57 GMT
• ステータス: 処理完了
• システム内更新日: 2023-03-25 04:04:31.151508
• Title: Sequential Monte Carlo for Sampling Balanced and Compact Redistricting Plans
• Title（参考訳）: サンプリングバランスとコンパクト再資源化計画のための逐次モンテカルロ
• Authors: Cory McCartan and Kosuke Imai
• Abstract要約: 本稿では,現実的な目標分布に収束する再限定計画のサンプルを生成する,SMC(Sequential Monte Carlo)アルゴリズムを提案する。 提案アルゴリズムの精度を,すべての再分割計画を列挙可能な小さなマップを用いて検証する。 次に、SMCアルゴリズムを用いて、ペンシルベニア州の最近の有名な再分権事件において、関係当事者が提出したいくつかの地図のパルチザン的含意を評価する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Random sampling of graph partitions under constraints has become a popular tool for evaluating legislative redistricting plans. Analysts detect partisan gerrymandering by comparing a proposed redistricting plan with an ensemble of sampled alternative plans. For successful application, sampling methods must scale to maps with a moderate or large number of districts, incorporate realistic legal constraints, and accurately and efficiently sample from a selected target distribution. Unfortunately, most existing methods struggle in at least one of these areas. We present a new Sequential Monte Carlo (SMC) algorithm that generates a sample of redistricting plans converging to a realistic target distribution. Because it draws many plans in parallel, the SMC algorithm can efficiently explore the relevant space of redistricting plans better than the existing Markov chain Monte Carlo (MCMC) algorithms that generate plans sequentially. Our algorithm can simultaneously incorporate several constraints commonly imposed in real-world redistricting problems, including equal population, compactness, and preservation of administrative boundaries. We validate the accuracy of the proposed algorithm by using a small map where all redistricting plans can be enumerated. We then apply the SMC algorithm to evaluate the partisan implications of several maps submitted by relevant parties in a recent high-profile redistricting case in the state of Pennsylvania. We find that the proposed algorithm converges faster and with fewer samples than a comparable MCMC algorithm. Open-source software is available for implementing the proposed methodology.
• Abstract（参考訳）: 制約下でのグラフ分割のランダムサンプリングは、規制緩和計画を評価する一般的なツールとなっている。 アナリストは、提案された再限定計画とサンプル化された代替計画のアンサンブルを比較することで、パルチザンジェリーマンディングを検出する。 適用を成功させるためには、サンプリング手法は適度または多数の地区の地図にスケールし、現実的な法的制約を取り入れ、選択された対象分布から正確に効率的にサンプリングする必要がある。 残念ながら、既存の手法のほとんどは、これらの領域の少なくとも1つで苦労しています。 本稿では,現実的目標分布に収束する再帰計画のサンプルを生成する新しい逐次モンテカルロ(smc)アルゴリズムを提案する。 多くの計画が並列に描画されるため、SMCアルゴリズムは、計画を逐次生成する既存のマルコフ連鎖モンテカルロ(MCMC)アルゴリズムよりも効率的に計画の再分割の空間を探索することができる。 提案アルゴリズムは, 人口平等, コンパクト性, 行政境界の保全など, 現実世界の再制限問題に共通するいくつかの制約を同時に組み込むことができる。 提案アルゴリズムの精度を,すべての再分割計画を列挙可能な小さなマップを用いて検証する。 次に,smcアルゴリズムを用いて,ペンシルバニア州における近年の高名な再帰事件において,関連当事者が提出した地図のパルチザン的意義を評価する。 提案アルゴリズムはMCMCアルゴリズムよりも高速かつ少ないサンプルで収束することがわかった。 提案手法の実装にはオープンソースソフトウェアが利用できる。

関連論文リスト

• Multiscale Parallel Tempering for Fast Sampling on Redistricting Plans [1.1233768932957773]
  説得力のある方法は、計画と中立に描画された再限定計画のアンサンブルを比較することである。 アンサンブルと所定の計画との党派差を監査するためには、非党派基準が一致していることを保証する必要がある。 本研究では,各スケールで局所移動を行うマルチスケール並列テンパリング手法を提案する。
  論文  参考訳（メタデータ） (2024-01-30T21:33:05Z)
• An Optimal Algorithm for the Real-Valued Combinatorial Pure Exploration of Multi-Armed Bandit [65.268245109828]
  多武装バンディット(R-CPE-MAB)の真価純探査問題について検討する。 既存のR-CPE-MABの手法は、いわゆるトランスダクティブ線形帯域の特殊な場合と見なすことができる。 本稿では,差分探索アルゴリズム (CombGapE) を提案する。
  論文  参考訳（メタデータ） (2023-06-15T15:37:31Z)
• Continuous Monte Carlo Graph Search [61.11769232283621]
  連続モンテカルログラフサーチ(Continuous Monte Carlo Graph Search, CMCGS)は、モンテカルログラフサーチ(MCTS)のオンラインプランニングへの拡張である。 CMCGSは、計画中、複数の州で同じ行動方針を共有することで高いパフォーマンスが得られるという洞察を生かしている。 並列化によってスケールアップすることができ、学習力学モデルによる連続制御においてクロスエントロピー法(CEM)よりも優れている。
  論文  参考訳（メタデータ） (2022-10-04T07:34:06Z)
• Measuring Geometric Similarity Across Possible Plans for Automated Redistricting [0.0]
  本稿では,2つの計画の間に同一の選挙区に留まる州の面積や人口の比率に対応する,類似性の解釈的尺度とそれに対応する代入行列を簡潔に紹介する。 次に、直感的な時間でこの測度を計算する方法を示し、潜在的なユースケースを簡潔に示す。
  論文  参考訳（メタデータ） (2021-11-17T03:37:25Z)
• Compact Redistricting Plans Have Many Spanning Trees [39.779544988993294]
  政治的再分権マップの設計と分析において、国勢調査ブロックのグラフのすべての分割の空間から同じ人口の連結部分グラフにサンプリングできることがしばしば有用である。 本稿では,境界分割領域の総長さと,そのような写像がサンプリングされる確率との間には,逆指数関係が成立する。
  論文  参考訳（メタデータ） (2021-09-27T23:36:01Z)
• Compactness statistics for spanning tree recombination [0.0]
  レコム法は、他の方法よりもコンパクトな地区で計画を作成する。 2つの格子グラフとボルダー郡管区グラフの2分割計画のアンサンブルを構築した。 これはReCom法による分割計画のコンパクト性を理解するための重要なステップである。
  論文  参考訳（メタデータ） (2021-03-03T21:39:51Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。 最先端アルゴリズムの利点を論じ、解説する。
  論文  参考訳（メタデータ） (2020-09-28T15:22:24Z)
• Making Affine Correspondences Work in Camera Geometry Computation [62.7633180470428]
  局所的な特徴は、ポイント・ツー・ポイント対応ではなく、リージョン・ツー・リージョンを提供する。 本稿では,全モデル推定パイプラインにおいて,地域間マッチングを効果的に活用するためのガイドラインを提案する。 実験により、アフィンソルバはより高速な実行時にポイントベースソルバに匹敵する精度を達成できることが示された。
  論文  参考訳（メタデータ） (2020-07-20T12:07:48Z)
• The Essential Role of Empirical Validation in Legislative Redistricting Simulation [0.0]
  提案手法は,計画の再分割を効率的に行うことのできる計算手法である。 このアルゴリズムは,数百の地理的単位を持つ状態に拡張可能であることを示す。
  論文  参考訳（メタデータ） (2020-06-17T20:51:43Z)
• Planning in Markov Decision Processes with Gap-Dependent Sample Complexity [48.98199700043158]
  マルコフ決定過程における計画のための新しいトラジェクトリに基づくモンテカルロ木探索アルゴリズム MDP-GapE を提案する。 我々は, MDP-GapE に要求される生成モデルに対する呼び出し回数の上限を証明し, 確率の高い準最適動作を同定する。
  論文  参考訳（メタデータ） (2020-06-10T15:05:51Z)
• Decentralized MCTS via Learned Teammate Models [89.24858306636816]
  本稿では,モンテカルロ木探索に基づくトレーニング可能なオンライン分散計画アルゴリズムを提案する。 深層学習と畳み込みニューラルネットワークを用いて正確なポリシー近似を作成可能であることを示す。
  論文  参考訳（メタデータ） (2020-03-19T13:10:20Z)

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

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