論文の概要: Projected Model Counting: Beyond Independent Support

• arxiv url: http://arxiv.org/abs/2110.09171v1
• Date: Mon, 18 Oct 2021 10:40:22 GMT
• ステータス: 処理完了
• システム内更新日: 2021-10-19 17:42:41.947491
• Title: Projected Model Counting: Beyond Independent Support
• Title（参考訳）: Projected Model Counting: 独立したサポートを超えて
• Authors: Jiong Yang, Supratik Chakraborty, Kuldeep S. Meel
• Abstract要約: 現代のカウンタで使われる鍵となる考え方は、しばしば射影集合の小さな部分集合である指数依存的なサポートに射影されたモデルを数えることである。 本稿では直観とは対照的に、射影集合を超えた変数を射影することは有益であることを示す。
• 参考スコア（独自算出の注目度）: 27.606526752377615
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The past decade has witnessed a surge of interest in practical techniques for projected model counting. Despite significant advancements, however, performance scaling remains the Achilles' heel of this field. A key idea used in modern counters is to count models projected on an \emph{independent support} that is often a small subset of the projection set, i.e. original set of variables on which we wanted to project. While this idea has been effective in scaling performance, the question of whether it can benefit to count models projected on variables beyond the projection set, has not been explored. In this paper, we study this question and show that contrary to intuition, it can be beneficial to project on variables beyond the projection set. In applications such as verification of binarized neural networks, quantification of information flow, reliability of power grids etc., a good upper bound of the projected model count often suffices. We show that in several such cases, we can identify a set of variables, called upper bound support (UBS), that is not necessarily a subset of the projection set, and yet counting models projected on UBS guarantees an upper bound of the true projected model count. Theoretically, a UBS can be exponentially smaller than the smallest independent support. Our experiments show that even otherwise, UBS-based projected counting can be more efficient than independent support-based projected counting, while yielding bounds of very high quality. Based on extensive experiments, we find that UBS-based projected counting can solve many problem instances that are beyond the reach of a state-of-the-art independent support-based projected model counter.
• Abstract（参考訳）: 過去10年間、予測されたモデルカウントの実用技術への関心が高まっている。 しかし、著しい進歩にもかかわらず、パフォーマンス・スケーリングはこの分野のアキレスのヒールのままである。 現代のカウンターで使われる重要なアイデアは、射影集合の小さな部分集合、すなわち我々が射影したい元の変数の集合である \emph{independent support} 上に投影されたモデルを数えることである。 このアイデアはパフォーマンスのスケーリングに有効であるが、プロジェクションセットを超えて変数に投影されるモデルを数えることにメリットがあるかどうかという問題は検討されていない。 本稿では,この問題を考察し,直観に反し,射影集合を超えて変数を射影することは有益であることを示す。 二項化ニューラルネットワークの検証、情報フローの定量化、電力グリッドの信頼性などのアプリケーションでは、予測されたモデル数の上限が十分であることが多い。 いくつかの場合において、上界サポート (UBS) と呼ばれる変数の集合は、必ずしも射影集合の部分集合ではないが、UBS上に射影されたモデルを数えることは、真の射影されたモデル数の上界を保証する。 理論的には、UBSは最小の独立支持よりも指数的に小さくすることができる。 私たちの実験では、ubsベースの投影計数が独立したサポートベースの投影計数よりも効率的であると同時に、非常に高品質な境界が得られることが示されています。 広範な実験により、ubsベースの投影カウントは、最先端の独立サポートベースの投影モデルカウンタの範囲を超えた多くの問題インスタンスを解決できることが判明した。

関連論文リスト

• FoundationPose: Unified 6D Pose Estimation and Tracking of Novel Objects [55.77542145604758]
  FoundationPoseは、6Dオブジェクトのポーズ推定と追跡のための統合基盤モデルである。 我々のアプローチは、微調整なしで、テスト時に新しいオブジェクトに即座に適用できる。
  論文  参考訳（メタデータ） (2023-12-13T18:28:09Z)
• How Predictable Are Large Language Model Capabilities? A Case Study on BIG-bench [52.11481619456093]
  実験記録におけるBIGベンチの性能予測問題について検討する。 95%以上のR2$スコアは、実験記録の中に学習可能なパターンが存在することを示している。 BIG-bench Hardのように新しいモデルファミリーを評価できるサブセットが3倍程度小さくなっています。
  論文  参考訳（メタデータ） (2023-05-24T09:35:34Z)
• Fast Converging Anytime Model Counting [34.295512073482186]
  本稿では、近似モデルカウントのための新しい時限アプローチであるPartialKCを設計する。 我々の経験的分析により、PartialKCは最先端の近似カウンタよりも高いスケーラビリティと精度を達成できることが示された。 興味深いことに、実験の結果は、PartialKCが多くのインスタンスに収束し、したがって、最先端の正確なカウンタに匹敵する正確なモデルカウント性能を提供することを示している。
  論文  参考訳（メタデータ） (2022-12-19T12:01:28Z)
• Multi-Target XGBoostLSS Regression [91.3755431537592]
  本稿では,複数の目標とその依存関係を確率論的回帰設定でモデル化するXGBoostLSSの拡張について述べる。 提案手法は,既存のGBMよりも実行時の方が優れており,精度も良好に比較できる。
  論文  参考訳（メタデータ） (2022-10-13T08:26:14Z)
• Sampling from Arbitrary Functions via PSD Models [55.41644538483948]
  まず確率分布をモデル化し,そのモデルからサンプリングする。 これらのモデルでは, 少数の評価値を用いて, 高精度に多数の密度を近似することが可能であることが示され, それらのモデルから効果的にサンプルする簡単なアルゴリズムが提示される。
  論文  参考訳（メタデータ） (2021-10-20T12:25:22Z)
• Deconfounding Scores: Feature Representations for Causal Effect Estimation with Weak Overlap [140.98628848491146]
  推定対象の偏りを伴わずに高い重なりを生じさせる,デコンファウンディングスコアを導入する。 分離スコアは観測データで識別可能なゼロ共分散条件を満たすことを示す。 特に,この手法が標準正規化の魅力的な代替となることを示す。
  論文  参考訳（メタデータ） (2021-04-12T18:50:11Z)
• MASSIVE: Tractable and Robust Bayesian Learning of Many-Dimensional Instrumental Variable Models [8.271859911016719]
  モデル不確実性を考慮した汎用的かつ効率的な因果推論アルゴリズムを提案する。 いくつかの候補が(近い)有効である限り、どの候補が先験的かを知ることなく、それらの集団が目標との相互作用に十分な制限を課し、信頼できる因果効果の推定を得る。
  論文  参考訳（メタデータ） (2020-12-18T10:06:55Z)
• A Complete Characterization of Projectivity for Statistical Relational Models [20.833623839057097]
  本稿では,射影関係モデルのクラスを正確に対応付ける,有向潜在変数モデルのクラスを導入する。 また、与えられた大きさ-$k$構造上の分布が、より大きい大きさ-$n$構造における大きさ-$k$部分構造の統計周波数分布であるときの特性も得られる。
  論文  参考訳（メタデータ） (2020-04-23T05:58:27Z)
• Learning Ising models from one or multiple samples [26.00403702328348]
  我々は一サンプル推定の保証を提供し、相互作用行列の族における計量エントロピーの観点から推定誤差を定量化する。 我々の技術的アプローチは、モデルの相互作用ネットワークをスパース化し、結果の条件分布への依存性を十分に弱める変数のサブセットを条件付けすることの恩恵を受ける。
  論文  参考訳（メタデータ） (2020-04-20T15:17:05Z)
• Particle-Gibbs Sampling For Bayesian Feature Allocation Models [77.57285768500225]
  最も広く使われているMCMC戦略は、特徴割り当て行列のギブス更新に頼っている。 単一移動で特徴割り当て行列の全行を更新できるギブスサンプリング器を開発した。 このサンプルは、計算複雑性が特徴数で指数関数的にスケールするにつれて、多数の特徴を持つモデルにとって実用的ではない。 我々は,行ワイズギブズ更新と同じ分布を目標としたパーティクルギブズサンプルの開発を行うが,特徴数でのみ線形に増大する計算複雑性を有する。
  論文  参考訳（メタデータ） (2020-01-25T22:11:51Z)

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

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