論文の概要: Approximate Weighted First-Order Model Counting: Exploiting Fast
Approximate Model Counters and Symmetry
- arxiv url: http://arxiv.org/abs/2001.05263v1
- Date: Wed, 15 Jan 2020 12:21:06 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-11 07:01:00.127065
- Title: Approximate Weighted First-Order Model Counting: Exploiting Fast
Approximate Model Counters and Symmetry
- Title（参考訳）: 近似重み付き一階モデルカウント:高速近似モデルカウンタと対称性の利用
- Authors: Timothy van Bremen, Ondrej Kuzelka
- Abstract要約: 本稿では,重み付き1次モデルカウントを効率的にバウンドする新手法であるApproxWFOMCを提案する。
このアルゴリズムは、様々な一階確率表現を推論する。
本稿では,このアルゴリズムが一階確率モデルにおいて,既存の近似的および高精度な推論手法よりも優れていることを示す。
- 参考スコア（独自算出の注目度）: 16.574508244279098
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the symmetric weighted first-order model counting task and present
ApproxWFOMC, a novel anytime method for efficiently bounding the weighted
first-order model count in the presence of an unweighted first-order model
counting oracle. The algorithm has applications to inference in a variety of
first-order probabilistic representations, such as Markov logic networks and
probabilistic logic programs. Crucially for many applications, we make no
assumptions on the form of the input sentence. Instead, our algorithm makes use
of the symmetry inherent in the problem by imposing cardinality constraints on
the number of possible true groundings of a sentence's literals. Realising the
first-order model counting oracle in practice using the approximate
hashing-based model counter ApproxMC3, we show how our algorithm outperforms
existing approximate and exact techniques for inference in first-order
probabilistic models. We additionally provide PAC guarantees on the generated
bounds.
- Abstract（参考訳）: 対称重み付き一階モデル計数タスクと,oracle を計数する非重み付き一階モデルが存在する場合に,重み付き一階モデル計数を効率的にバインドする新しいanytime法 approxwfomc について検討した。
このアルゴリズムは、マルコフ論理ネットワークや確率論理プログラムなど、様々な一階確率表現の推論に応用できる。
多くのアプリケーションにおいて、私たちは入力文の形式を仮定しません。
代わりに、我々のアルゴリズムは、文のリテラルの真基底数に基数制約を課すことにより、問題に固有の対称性を利用する。
近似ハッシュモデルカウンタ ApproxMC3 を用いて, 1次モデルカウントオラクルを実際に実現し, アルゴリズムが1次確率モデルにおける推定の既存の近似的および正確な手法よりも優れていることを示す。
また、生成された境界に対してPAC保証を提供する。
関連論文リスト
- Graph-Structured Speculative Decoding [52.94367724136063]
投機的復号化は、大規模言語モデルの推論を加速する有望な手法として登場した。
本稿では, 有向非巡回グラフ(DAG)を応用して, 起案された仮説を管理する革新的な手法を提案する。
我々は1.73$times$から1.96$times$に顕著なスピードアップを観察し、標準投機的復号法を大幅に上回った。
論文 参考訳（メタデータ） (2024-07-23T06:21:24Z) - Efficient Incremental Belief Updates Using Weighted Virtual Observations [2.7195102129095003]
モンテカルロ推論の文脈における漸進的信念更新問題に対するアルゴリズム的解を提案する。
このアプローチの効率性と堅牢性を示すために,多くの実践例とケーススタディにソリューションを実装し,適用する。
論文 参考訳（メタデータ） (2024-02-10T12:48:49Z) - Lifted Algorithms for Symmetric Weighted First-Order Model Sampling [7.007419073974192]
数量化器を用いた一階述語論理の2変数フラグメントのサンプリングにおけるドメインリフト性を証明する。
そして、この結果は、基数制約の存在下においても引き続き持続することを示す。
我々のアルゴリズムは、最先端のWMSサンプリングよりもかなりのマージンで優れています。
論文 参考訳（メタデータ） (2023-08-17T07:40:47Z) - Sampling from Arbitrary Functions via PSD Models [55.41644538483948]
まず確率分布をモデル化し,そのモデルからサンプリングする。
これらのモデルでは, 少数の評価値を用いて, 高精度に多数の密度を近似することが可能であることが示され, それらのモデルから効果的にサンプルする簡単なアルゴリズムが提示される。
論文 参考訳（メタデータ） (2021-10-20T12:25:22Z) - Structured Reordering for Modeling Latent Alignments in Sequence
Transduction [86.94309120789396]
本稿では,分離可能な置換の辺りを正確に推定する効率的な動的プログラミングアルゴリズムを提案する。
結果のSeq2seqモデルは、合成問題やNLPタスクの標準モデルよりも体系的な一般化が優れている。
論文 参考訳（メタデータ） (2021-06-06T21:53:54Z) - Community Detection in the Stochastic Block Model by Mixed Integer
Programming [3.8073142980733]
Degree-Corrected Block Model (DCSBM) は、コミュニティ構造を持つランダムグラフを生成する一般的なモデルである。
DCSBMに基づくコミュニティ検出の標準的なアプローチは、最大推定(MLE)により観測されたネットワークデータを生成する可能性が最も高いモデルパラメータを探索することである。
本稿では,モデルパラメータと最大確率のコミュニティ割当を観測グラフから確実に求める数学的計画式と厳密解法を提案する。
論文 参考訳（メタデータ） (2021-01-26T22:04:40Z) - A Bayesian Approach to Block-Term Tensor Decomposition Model Selection
and Computation [10.91885508254207]
いわゆるブロック項分解(BTD)テンソルモデル(特にランク=(L_r,L_r,1)$バージョン)は近年注目を集めている。
BTDモデル構造、すなわちブロック項の数とその個々のランクを推定するという課題は、最近になって注目され始めたばかりです。
ランク-$(L_r,L_r,1)$ BTDモデルの選択と計算の問題を、列の間隔を直交するアイデアに基づいて解くためのベイズ的アプローチが採られる。
論文 参考訳（メタデータ） (2021-01-08T09:37:21Z) - Bayes DistNet -- A Robust Neural Network for Algorithm Runtime
Distribution Predictions [1.8275108630751844]
ランダム化アルゴリズムは制約満足度問題 (CSP) やブール満足度問題 (SAT) の多くの最先端の解法で用いられている。
従来の最先端の手法は、入力インスタンスが従う固定パラメトリック分布を直接予測しようとする。
この新モデルは,低観測環境下での堅牢な予測性能と,検閲された観測処理を実現する。
論文 参考訳（メタデータ） (2020-12-14T01:15:39Z) - Control as Hybrid Inference [62.997667081978825]
本稿では、反復推論と償却推論のバランスを自然に仲介するCHIの実装について述べる。
連続的な制御ベンチマークでアルゴリズムのスケーラビリティを検証し、強力なモデルフリーおよびモデルベースラインを上回る性能を示す。
論文 参考訳（メタデータ） (2020-07-11T19:44:09Z) - Slice Sampling for General Completely Random Measures [74.24975039689893]
本稿では, 後続推定のためのマルコフ連鎖モンテカルロアルゴリズムについて, 補助スライス変数を用いてトランケーションレベルを適応的に設定する。
提案アルゴリズムの有効性は、いくつかの一般的な非パラメトリックモデルで評価される。
論文 参考訳（メタデータ） (2020-06-24T17:53:53Z) - Learning Gaussian Graphical Models via Multiplicative Weights [54.252053139374205]
乗算重み更新法に基づいて,Klivans と Meka のアルゴリズムを適用した。
アルゴリズムは、文献の他のものと質的に類似したサンプル複雑性境界を楽しみます。
ランタイムが低い$O(mp2)$で、$m$サンプルと$p$ノードの場合には、簡単にオンライン形式で実装できる。
論文 参考訳（メタデータ） (2020-02-20T10:50:58Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。