論文の概要: Towards Practical First-Order Model Counting

• arxiv url: http://arxiv.org/abs/2502.12278v1
• Date: Mon, 17 Feb 2025 19:28:06 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-02-19 14:06:12.114723
• Title: Towards Practical First-Order Model Counting
• Title（参考訳）: 実用的1次モデルカウントに向けて
• Authors: Ananth K. Kidambi, Guramrit Singh, Paulius Dilkas, Kuldeep S. Meel,
• Abstract要約: 1次モデルカウント(英: First-order model counting、FOMC)とは、一階述語論理における文のモデル数をカウントする問題である。 1次知識コンパイルに基づく新しい手法が提案された。 この研究の主な貢献は、関数定義を任意の精度演算を備えたC++コードに変換するGantryと呼ばれる完全自動コンパイルアルゴリズムである。
• 参考スコア（独自算出の注目度）: 25.295313268611217
• License:
• Abstract: First-order model counting (FOMC) is the problem of counting the number of models of a sentence in first-order logic. Since lifted inference techniques rely on reductions to variants of FOMC, the design of scalable methods for FOMC has attracted attention from both theoreticians and practitioners over the past decade. Recently, a new approach based on first-order knowledge compilation was proposed. This approach, called Crane, instead of simply providing the final count, generates definitions of (possibly recursive) functions that can be evaluated with different arguments to compute the model count for any domain size. However, this approach is not fully automated, as it requires manual evaluation of the constructed functions. The primary contribution of this work is a fully automated compilation algorithm, called Gantry, which transforms the function definitions into C++ code equipped with arbitrary-precision arithmetic. These additions allow the new FOMC algorithm to scale to domain sizes over 500,000 times larger than the current state of the art, as demonstrated through experimental results.
• Abstract（参考訳）: 1次モデルカウント(英: First-order model counting, FOMC)は、一階述語論理における文のモデル数をカウントする問題である。 昇降推論技術はFOMCの変種への還元に依存しているため、FOMCのスケーラブルな手法の設計は過去10年間に理論家と実践家の両方から注目を集めてきた。 近年,1次知識コンパイルに基づく新しい手法が提案されている。 このアプローチはクレーンと呼ばれ、単に最終カウントを提供するのではなく、異なる引数で評価できる(再帰的かもしれない)関数の定義を生成して、任意のドメインサイズのモデルカウントを計算する。 しかし、構築された関数を手動で評価する必要があるため、このアプローチは完全には自動化されていない。 この研究の主な貢献は完全自動コンパイルアルゴリズムであるGantryで、関数定義を任意の精度演算を備えたC++コードに変換する。 これらの追加により、実験結果から示すように、新しいFOMCアルゴリズムは現在の最先端技術の50万倍以上のドメインサイズにスケールすることができる。

関連論文リスト

• Inference-Time Alignment in Diffusion Models with Reward-Guided Generation: Tutorial and Review [59.856222854472605]
  このチュートリアルは、拡散モデルにおける下流の報酬関数を最適化するための推論時ガイダンスとアライメント方法に関する詳細なガイドを提供する。 生物学のような分野における実践的な応用は、しばしば特定の指標を最大化するサンプル生成を必要とする。 本稿では,(1)推論時と組み合わせた微調整手法,(2)モンテカルロ木探索などの探索アルゴリズムに基づく推論時アルゴリズム,(3)言語モデルと拡散モデルにおける推論時アルゴリズムの接続について論じる。
  論文  参考訳（メタデータ） (2025-01-16T17:37:35Z)
• Scalable Inference for Bayesian Multinomial Logistic-Normal Dynamic Linear Models [0.5735035463793009]
  この記事では、$textitFenrir$と呼ばれる、後続状態推定に対する効率的で正確なアプローチを開発します。 我々の実験から、フェンリルはスタンよりも3桁効率が良いことが示唆された。 当社のメソッドは,C++で記述されたユーザフレンドリなソフトウェアライブラリとして,Rインターフェースを備えたコミュニティで利用可能です。
  論文  参考訳（メタデータ） (2024-10-07T23:20:14Z)
• Efficient Model-Free Exploration in Low-Rank MDPs [76.87340323826945]
  低ランクマルコフ決定プロセスは、関数近似を持つRLに対して単純だが表現力のあるフレームワークを提供する。 既存のアルゴリズムは、(1)計算的に抽出可能であるか、または(2)制限的な統計的仮定に依存している。 提案手法は,低ランクMPPの探索のための最初の実証可能なサンプル効率アルゴリズムである。
  論文  参考訳（メタデータ） (2023-07-08T15:41:48Z)
• Provably Efficient Representation Learning with Tractable Planning in Low-Rank POMDP [81.00800920928621]
  部分的に観測可能なマルコフ決定過程(POMDP)における表現学習の研究 まず,不確実性(OFU)に直面した最大推定(MLE)と楽観性を組み合わせた復調性POMDPのアルゴリズムを提案する。 次に、このアルゴリズムをより広範な$gamma$-observable POMDPのクラスで機能させる方法を示す。
  論文  参考訳（メタデータ） (2023-06-21T16:04:03Z)
• Synthesising Recursive Functions for First-Order Model Counting: Challenges, Progress, and Conjectures [12.47276164048813]
  1次モデルカウント(英: First-order model counting、FOMC)は、有限領域の1次論理において文のモデルを数えるように要求する計算問題である。 私たちは、典型的にドメイン再帰に伴う制限を緩和し、サイクルを含むかもしれない有向グラフを扱う。 これらの改良により、アルゴリズムはそれまで到達範囲を超えていた問題を数えるための効率的な解を見つけることができる。
  論文  参考訳（メタデータ） (2023-06-07T06:49:01Z)
• A General Framework for Sample-Efficient Function Approximation in Reinforcement Learning [132.45959478064736]
  モデルベースとモデルフリー強化学習を統合した汎用フレームワークを提案する。 最適化に基づく探索のための分解可能な構造特性を持つ新しい推定関数を提案する。 本フレームワークでは,OPERA (Optimization-based Exploration with Approximation) という新しいサンプル効率アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-09-30T17:59:16Z)
• Formalization of a Stochastic Approximation Theorem [0.22940141855172028]
  近似アルゴリズムは、ターゲットが不明な環境でターゲット値を近似するために使用される反復的な手順である。 もともとは1951年にRobinsとMonroによって発表された論文で、近似の分野は飛躍的に成長し、応用領域に影響を与えている。
  論文  参考訳（メタデータ） (2022-02-12T02:31:14Z)
• Causality-based Counterfactual Explanation for Classification Models [11.108866104714627]
  本稿では,プロトタイプに基づく対実的説明フレームワーク(ProCE)を提案する。 ProCEは、カウンターファクトデータの特徴の根底にある因果関係を保存することができる。 さらに,提案手法を応用した多目的遺伝的アルゴリズムを考案した。
  論文  参考訳（メタデータ） (2021-05-03T09:25:59Z)
• Slice Sampling for General Completely Random Measures [74.24975039689893]
  本稿では, 後続推定のためのマルコフ連鎖モンテカルロアルゴリズムについて, 補助スライス変数を用いてトランケーションレベルを適応的に設定する。 提案アルゴリズムの有効性は、いくつかの一般的な非パラメトリックモデルで評価される。
  論文  参考訳（メタデータ） (2020-06-24T17:53:53Z)
• Approximate Weighted First-Order Model Counting: Exploiting Fast Approximate Model Counters and Symmetry [16.574508244279098]
  本稿では,重み付き1次モデルカウントを効率的にバウンドする新手法であるApproxWFOMCを提案する。 このアルゴリズムは、様々な一階確率表現を推論する。 本稿では,このアルゴリズムが一階確率モデルにおいて,既存の近似的および高精度な推論手法よりも優れていることを示す。
  論文  参考訳（メタデータ） (2020-01-15T12:21:06Z)
• Polynomial-Time Exact MAP Inference on Discrete Models with Global Dependencies [83.05591911173332]
  ジャンクションツリーアルゴリズムは、実行時の保証と正確なMAP推論のための最も一般的な解である。 本稿では,ノードのクローン化による新たなグラフ変換手法を提案する。
  論文  参考訳（メタデータ） (2019-12-27T13:30:29Z)

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

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