論文の概要: Spanning tree methods for sampling graph partitions
- arxiv url: http://arxiv.org/abs/2210.01401v1
- Date: Tue, 4 Oct 2022 06:18:33 GMT
- ステータス: 処理完了
- システム内更新日: 2023-02-19 11:28:25.419617
- Title: Spanning tree methods for sampling graph partitions
- Title（参考訳）: グラフ分割をサンプリングするためのスパンディングツリー法
- Authors: Sarah Cannon, Moon Duchin, Dana Randall, and Parker Rule
- Abstract要約: 分割プランはグラフの連結部分集合へのバランスの取れた分割と見なすことができる。
RevReComは、ReComが元々近似するために設計された単純で自然な分布に収束する。
- 参考スコア（独自算出の注目度）: 0.7658085223797904
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In the last decade, computational approaches to graph partitioning have made
a major impact in the analysis of political redistricting, including in U.S.
courts of law. Mathematically, a districting plan can be viewed as a balanced
partition of a graph into connected subsets. Examining a large sample of valid
alternative districting plans can help us recognize gerrymandering against an
appropriate neutral baseline. One algorithm that is widely used to produce
random samples of districting plans is a Markov chain called recombination (or
ReCom), which repeatedly fuses adjacent districts, forms a spanning tree of
their union, and splits that spanning tree with a balanced cut to form new
districts. One drawback is that this chain's stationary distribution has no
known closed form when there are three or more districts. In this paper, we
modify ReCom slightly to give it a property called reversibility, resulting in
a new Markov chain, RevReCom. This new chain converges to the simple, natural
distribution that ReCom was originally designed to approximate: a plan's
stationary probability is proportional to the product of the number of spanning
trees of each district. This spanning tree score is a measure of district
"compactness" (or shape) that is also aligned with notions of community
structure from network science. After deriving the steady state formally, we
present diagnostic evidence that the convergence is efficient enough for the
method to be practically useful, giving high-quality samples for full-sized
problems within several hours. In addition to the primary application of
benchmarking of redistricting plans (i.e., describing a normal range for
statistics), this chain can also be used to validate other methods that target
the spanning tree distribution.
- Abstract（参考訳）: 過去10年間、グラフ分割に対する計算的アプローチは、米国法裁判所を含む政治再編成の分析に大きな影響を与えてきた。
数学的には、分割計画(英語版)はグラフの連結部分集合への平衡分割と見なすことができる。
有効な代替地区計画の大規模なサンプルを調べることは、適切な中立ベースラインに対するジェリーマンダーの認識に役立ちます。
リコンビネーション (recombination, ReCom) と呼ばれるマルコフ連鎖は、隣接する地区を何度も融合させ、それらのユニオンのスパンニングツリーを形成し、バランスの取れたカットで木を分割して新しい地区を形成する。
1つの欠点は、このチェーンの定常分布が3つ以上の地区がある場合、閉形式が知られていないことである。
本稿では、ReComを少し修正して可逆性(reversibility)と呼ばれる特性を与え、その結果、新しいマルコフチェーンRevReComが誕生する。
この新しい連鎖は、もともとReComが近似するために設計された単純で自然な分布に収束する: 計画の定常確率は、各地区の散在木数の積に比例する。
このスパンニングツリースコアは、ネットワーク科学からのコミュニティ構造の概念とも一致している地区の「コンパクト性」(または形)の尺度である。
定常状態の導出後, 本手法が実用に有用であることを示す診断的証拠を提示し, フルサイズの問題に対する高品質な試料を数時間以内に提供した。
再制限計画のベンチマーク(統計の通常の範囲を記述する)の第一の応用に加えて、この連鎖は、散在する木の分布を狙う他の方法を検証するためにも用いられる。
関連論文リスト
- The Traveling Mailman: Topological Optimization Methods for User-Centric Redistricting [0.0]
本研究では,US Postal Service ネットワークを用いた地域間接続性評価手法を提案する。
我々は、地域境界がコミュニティの整合性に与える影響を評価するために、トポロジカルデータ分析とマルコフ・チェイン・モンテカルロ法を組み合わせる。
論文 参考訳（メタデータ） (2024-07-28T16:50:45Z) - Multiscale Parallel Tempering for Fast Sampling on Redistricting Plans [1.1233768932957773]
説得力のある方法は、計画と中立に描画された再限定計画のアンサンブルを比較することである。
アンサンブルと所定の計画との党派差を監査するためには、非党派基準が一致していることを保証する必要がある。
本研究では,各スケールで局所移動を行うマルチスケール並列テンパリング手法を提案する。
論文 参考訳（メタデータ） (2024-01-30T21:33:05Z) - Region Rebalance for Long-Tailed Semantic Segmentation [89.84860341946283]
まず、ピクセル再バランスによってこの問題に対処する主な課題を調査し、特定する。
そして,本分析に基づいて,単純かつ効果的な領域再バランス方式を導出する。
提案された領域再均衡スキームでは、最先端のBEiTはADE20K val集合上のmIoUで+0.7%上昇する。
論文 参考訳（メタデータ） (2022-04-05T03:47:47Z) - Compact Redistricting Plans Have Many Spanning Trees [39.779544988993294]
政治的再分権マップの設計と分析において、国勢調査ブロックのグラフのすべての分割の空間から同じ人口の連結部分グラフにサンプリングできることがしばしば有用である。
本稿では,境界分割領域の総長さと,そのような写像がサンプリングされる確率との間には,逆指数関係が成立する。
論文 参考訳（メタデータ） (2021-09-27T23:36:01Z) - Direct Measure Matching for Crowd Counting [59.66286603624411]
そこで本研究では,予測密度マップを散乱点付基底真理に直接回帰する測度に基づく新しい計数手法を提案する。
本稿では, シンクホーンの測位損失を計測するために設計した, 半平衡型のシンクホーン発散を導出する。
論文 参考訳（メタデータ） (2021-07-04T06:37:33Z) - Improved Branch and Bound for Neural Network Verification via Lagrangian
Decomposition [161.09660864941603]
ニューラルネットワークの入出力特性を公式に証明するためのブランチとバウンド(BaB)アルゴリズムのスケーラビリティを改善します。
活性化に基づく新しい分岐戦略とBaBフレームワークであるブランチとデュアルネットワーク境界(BaDNB)を提案する。
BaDNBは、従来の完全検証システムを大きなマージンで上回り、対数特性で平均検証時間を最大50倍に削減した。
論文 参考訳（メタデータ） (2021-04-14T09:22:42Z) - Compactness statistics for spanning tree recombination [0.0]
レコム法は、他の方法よりもコンパクトな地区で計画を作成する。
2つの格子グラフとボルダー郡管区グラフの2分割計画のアンサンブルを構築した。
これはReCom法による分割計画のコンパクト性を理解するための重要なステップである。
論文 参考訳（メタデータ） (2021-03-03T21:39:51Z) - SGA: A Robust Algorithm for Partial Recovery of Tree-Structured
Graphical Models with Noisy Samples [75.32013242448151]
ノードからの観測が独立しているが非識別的に分散ノイズによって破損した場合、Ising Treeモデルの学習を検討する。
Katiyarら。
(2020) は, 正確な木構造は復元できないが, 部分木構造を復元できることを示した。
統計的に堅牢な部分木回復アルゴリズムであるSymmetrized Geometric Averaging(SGA)を提案する。
論文 参考訳（メタデータ） (2021-01-22T01:57:35Z) - Convex Polytope Trees [57.56078843831244]
コンベックスポリトープ木(CPT)は、決定境界の解釈可能な一般化によって決定木の系統を拡張するために提案される。
木構造が与えられたとき,木パラメータに対するCPTおよび拡張性のあるエンドツーエンドトレーニングアルゴリズムを効率的に構築する。
論文 参考訳（メタデータ） (2020-10-21T19:38:57Z) - Sequential Monte Carlo for Sampling Balanced and Compact Redistricting
Plans [0.0]
本稿では,現実的な目標分布に収束する再限定計画のサンプルを生成する,SMC(Sequential Monte Carlo)アルゴリズムを提案する。
提案アルゴリズムの精度を,すべての再分割計画を列挙可能な小さなマップを用いて検証する。
次に、SMCアルゴリズムを用いて、ペンシルベニア州の最近の有名な再分権事件において、関係当事者が提出したいくつかの地図のパルチザン的含意を評価する。
論文 参考訳（メタデータ） (2020-08-13T23:26:34Z) - Convolutional Ordinal Regression Forest for Image Ordinal Estimation [52.67784321853814]
我々は、画像の順序性評価のために、コンボリューショナル・オーディショナル・レグレッション・フォレスト(CORF)と呼ばれる新しいオーディショナル・レグレッション・アプローチを提案する。
提案したCORFは、順序回帰と微分可能な決定木を畳み込みニューラルネットワークと統合し、正確なグローバル順序関係と安定なグローバル順序関係を得る。
提案手法の有効性は,2つの画像順序推定課題において検証され,最先端の順序回帰法に対する大幅な改善と安定性が示された。
論文 参考訳（メタデータ） (2020-08-07T10:41:17Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。