論文の概要: CCDD: A Tractable Representation for Model Counting and Uniform Sampling

• arxiv url: http://arxiv.org/abs/2202.10025v1
• Date: Mon, 21 Feb 2022 07:44:44 GMT
• ステータス: 処理完了
• システム内更新日: 2022-02-23 09:50:38.560319
• Title: CCDD: A Tractable Representation for Model Counting and Uniform Sampling
• Title（参考訳）: CCDD: モデルカウントと一様サンプリングのためのトラクタブル表現
• Authors: Yong Lai, Kuldeep S. Meel, Roland H. C. Yap
• Abstract要約: トラクタブルなターゲットコンパイル言語は通常、NNFの内部ノードの制限によって達成される。 等価リテラルをキャプチャするために,接続ノードに新たな制約を導入する新しい表現言語CCDDを提案する。
• 参考スコア（独自算出の注目度）: 34.295512073482186
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Knowledge compilation concerns with the compilation of representation languages to target languages supporting a wide range of tractable operations arising from diverse areas of computer science. Tractable target compilation languages are usually achieved by restrictions on the internal nodes of the NNF. In this paper, we propose a new representation language CCDD, which introduces new restrictions on conjunction nodes to capture equivalent literals. We show that CCDD supports two key queries, model counting and uniform samping, in polytime. We present algorithms and a compiler to compile propositional formulas expressed in CNF into CCDD. Experiments over a large set of benchmarks show that our compilation times are better with smaller representation than state-of-art Decision-DNNF, SDD and OBDD[AND] compilers. We apply our techniques to model counting and uniform sampling, and develop model counter and uniform sampler on CNF. Our empirical evaluation demonstrates the following significant improvements: our model counter can solve 885 instances while the prior state of the art solved only 843 instances, representing an improvement of 43 instances; and our uniform sampler can solve 780 instances while the prior state of the art solved only 648 instances, representing an improvement of 132 instances.
• Abstract（参考訳）: 知識コンパイルは、コンピュータ科学の様々な領域から生じる幅広いトラクタブルな操作をサポートする対象言語への表現言語のコンパイルに関する懸念である。 トラクタブルなターゲットコンパイル言語は通常、NNFの内部ノードの制限によって達成される。 本稿では,等価リテラルをキャプチャするために結合ノードに新たな制約を導入する新しい表現言語ccddを提案する。 CCDDはモデルカウントと一様サンプリングという2つのキークエリをポリ時間でサポートする。 CNFで表現された命題式をCCDDにコンパイルするアルゴリズムとコンパイラを提案する。 大規模なベンチマークに対する実験では、我々のコンパイル時間は最先端のDNNF、SDD、OBDD[AND]コンパイラよりも小さく表現されている。 本手法をモデルカウントと一様サンプリングに適用し,CNF上のモデルカウンタと一様サンプリング器を開発する。 我々のモデルカウンタは885のインスタンスを解けるのに対し、先行状態は43のインスタンスの改善を表す843のインスタンスのみを解き、統一標本作成者は780のインスタンスを解けるのに対し、先行状態は648のインスタンスのみを解き、132のインスタンスの改善を示す。

関連論文リスト

• Fine-Tuning with Divergent Chains of Thought Boosts Reasoning Through Self-Correction in Language Models [63.36637269634553]
  本稿では,複数の推論連鎖を比較するためにモデルを必要とすることによって,性能を向上する新しい手法を提案する。 DCoTデータセットの命令チューニングにより、より小さく、よりアクセスしやすい言語モデルの性能が向上することがわかった。
  論文  参考訳（メタデータ） (2024-07-03T15:01:18Z)
• CharED: Character-wise Ensemble Decoding for Large Language Models [24.993790740335243]
  本稿では,複数の大規模言語モデルから出力を"出力する"ことを目的とした推論時アンサンブルアルゴリズムを提案する。 提案モデルでは,語彙,トークン化,モデルサイズに関わらず,複数のLLMの補完的強度を組み合わせることができる。
  論文  参考訳（メタデータ） (2024-06-25T22:35:07Z)
• To token or not to token: A Comparative Study of Text Representations for Cross-Lingual Transfer [23.777874316083984]
  ゼロショットと少数ショットの両方の評価を重み付けして表現できるスコアリング言語クオシアン計量を提案する。 解析の結果,言語が密接に関連し,視覚的に類似したスクリプトを共有する場合,画像ベースモデルは言語間移動に優れることがわかった。 単語関係が重要な役割を果たす依存性解析タスクでは、キャラクタレベルに焦点を当てたモデルが他よりも優れています。
  論文  参考訳（メタデータ） (2023-10-12T06:59:10Z)
• Tractable Bounding of Counterfactual Queries by Knowledge Compilation [51.47174989680976]
  本稿では, パール構造因果モデルにおいて, 因果関係などの部分的特定可能なクエリのバウンダリングの問題について議論する。 最近提案された反復EMスキームは初期化パラメータをサンプリングしてそれらの境界を内部近似する。 シンボルパラメータを実際の値に置き換えた回路構造を,単一のシンボル知識コンパイルによって得られることを示す。
  論文  参考訳（メタデータ） (2023-10-05T07:10:40Z)
• Tokenization with Factorized Subword Encoding [2.538209532048867]
  本稿では,VQ-VAEモデルを用いて,サブワードを離散三重項に分解する新しいトークン化手法を提案する。 その結果, この手法は, 一般的に使用されるバイトペア符号化(BPE)トークン化アルゴリズムよりも, 形態的タスクに適しており, 頑健であることが示唆された。
  論文  参考訳（メタデータ） (2023-06-13T13:27:34Z)
• Compressing Sentence Representation with maximum Coding Rate Reduction [0.0]
  ほとんどの自然言語推論問題では、文表現は意味検索タスクに必要である。 スペースとハードウェアの制限のため、より小さなモデルを使用する場合には、同等の結果を得る必要がある。 複雑性と文埋め込みサイズを低減した新しい言語モデルは,セマンティック検索ベンチマークにおいて同等の結果が得られることを実証した。
  論文  参考訳（メタデータ） (2023-04-25T09:23:43Z)
• BenchCLAMP: A Benchmark for Evaluating Language Models on Syntactic and Semantic Parsing [55.058258437125524]
  本稿では,制約付きLanguage Model Parsingを評価するベンチマークであるBenchCLAMPを紹介する。 APIを通じてのみ利用可能な2つのGPT-3変種を含む8つの言語モデルをベンチマークする。 実験により,エンコーダ-デコーダ事前学習言語モデルでは,モデル出力が有効であると制約された場合に,構文解析や意味解析の最先端手法を超えることができることがわかった。
  論文  参考訳（メタデータ） (2022-06-21T18:34:11Z)
• Low-Rank Constraints for Fast Inference in Structured Models [110.38427965904266]
  この研究は、大規模構造化モデルの計算とメモリの複雑さを低減するための単純なアプローチを示す。 言語モデリング,ポリフォニック・ミュージック・モデリング,教師なし文法帰納法,ビデオ・モデリングのためのニューラルパラメータ構造モデルを用いた実験により,我々の手法は大規模状態空間における標準モデルの精度と一致することを示した。
  論文  参考訳（メタデータ） (2022-01-08T00:47:50Z)
• Coreferential Reasoning Learning for Language Representation [88.14248323659267]
  本稿では,コンテキスト内でコアファーデンシャル関係をキャプチャ可能な新しい言語表現モデルCorefBERTを提案する。 実験の結果,既存のベースラインモデルと比較して,CorefBERTは下流のNLPタスクにおいて一貫した大幅な改善を達成できることがわかった。
  論文  参考訳（メタデータ） (2020-04-15T03:57:45Z)

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

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