論文の概要: Phase Transition Behavior in Knowledge Compilation
- arxiv url: http://arxiv.org/abs/2007.10400v1
- Date: Mon, 20 Jul 2020 18:36:27 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-08 14:25:26.662924
- Title: Phase Transition Behavior in Knowledge Compilation
- Title（参考訳）: 知識コンパイルにおける相転移挙動
- Authors: Rahul Gupta, Subhajit Roy, Kuldeep S. Meel
- Abstract要約: 知識コンパイルの文脈におけるランダムk-CNF式のサイズとコンパイル時の挙動について検討する。
我々の研究は、SAT/CSPの相転移挙動に関するCSPコミュニティの初期の研究と精神的に類似している。
- 参考スコア（独自算出の注目度）: 52.68422776053012
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The study of phase transition behaviour in SAT has led to deeper
understanding and algorithmic improvements of modern SAT solvers. Motivated by
these prior studies of phase transitions in SAT, we seek to study the behaviour
of size and compile-time behaviour for random k-CNF formulas in the context of
knowledge compilation.
We perform a rigorous empirical study and analysis of the size and runtime
behavior for different knowledge compilation forms (and their corresponding
compilation algorithms): d-DNNFs, SDDs and OBDDs across multiple tools and
compilation algorithms. We employ instances generated from the random k-CNF
model with varying generation parameters to empirically reason about the
expected and median behavior of size and compilation-time for these languages.
Our work is similar in spirit to the early work in CSP community on phase
transition behavior in SAT/CSP. In a similar spirit, we identify the
interesting behavior with respect to different parameters: clause density and
solution density, a novel control parameter that we identify for the study of
phase transition behavior in the context of knowledge compilation. Furthermore,
we summarize our empirical study in terms of two concrete conjectures; a
rigorous study of these conjectures will possibly require new theoretical
tools.
- Abstract（参考訳）: SATにおける相転移挙動の研究は、現代のSATソルバの深い理解とアルゴリズム的改善につながった。
SATにおける相転移に関するこれらの先行研究に触発され、我々は知識コンパイルの文脈におけるランダムk-CNF式のサイズとコンパイル時の挙動について研究する。
複数のツールとコンパイルアルゴリズムをまたいだd-dnnfs、sds、obddといった異なる知識コンパイル形式(およびそれに対応するコンパイルアルゴリズム)のサイズと実行時の振る舞いに関する厳密な実証研究と分析を行う。
我々は,様々な生成パラメータを持つランダムk-CNFモデルから生成されたインスタンスを用いて,これらの言語に対するサイズとコンパイル時間の予測と中央値の挙動を実証的に推論する。
我々の研究は、SAT/CSPの相転移挙動に関するCSPコミュニティの初期の研究と精神的に類似している。
類似の精神では、異なるパラメータに関する興味深い振る舞いを識別する:節密度と解密度、知識コンパイルの文脈における相転移の振る舞いの研究のために識別される新しい制御パラメータ。
さらに、我々は2つの具体的な予想の観点から経験的研究を要約し、これらの予想の厳密な研究はおそらく新しい理論ツールを必要とするだろう。
関連論文リスト
- Process Variant Analysis Across Continuous Features: A Novel Framework [0.0]
本研究は, 業務プロセスにおけるケースの効果的セグメンテーションの課題に対処する。
本研究では,スライディングウインドウ手法と地球移動器の距離を併用して制御流の挙動変化を検出する手法を提案する。
オランダの保険会社UWVと共同で実生活事例研究を行い,その方法論を検証した。
論文 参考訳（メタデータ） (2024-05-06T16:10:13Z) - Exploring Continual Learning of Compositional Generalization in NLI [24.683598294766774]
本稿では,C2Gen NLI(Continuous Composal Generalization in Inference)の課題を紹介する。
モデルは、合成推論の基礎として原始推論タスクを構成する知識を継続的に取得する。
分析の結果,依存関係を観察しながらサブタスクを継続的に学習し,難易度を増大させることで,連続学習が構成一般化能力を高めることが示唆された。
論文 参考訳（メタデータ） (2024-03-07T10:54:27Z) - Rethinking Distribution Shifts: Empirical Analysis and Inductive Modeling for Tabular Data [30.518020409197767]
5つのデータセットと6万のメソッド構成にまたがる自然なシフトを含む実験的なテストベッドを構築します。
ML文献のX$(co)シフトに重きを置いているのとは対照的に、Y|X$-shiftsはテストベッドでもっとも一般的です。
論文 参考訳（メタデータ） (2023-07-11T14:25:10Z) - iSCAN: Identifying Causal Mechanism Shifts among Nonlinear Additive
Noise Models [48.33685559041322]
本稿では,同一変数集合上の2つ以上の関連するデータセットにおける因果メカニズムシフトの同定に焦点をあてる。
提案手法を実装したコードはオープンソースであり、https://github.com/kevinsbello/iSCAN.comで公開されている。
論文 参考訳（メタデータ） (2023-06-30T01:48:11Z) - A Mechanistic Interpretation of Arithmetic Reasoning in Language Models
using Causal Mediation Analysis [128.0532113800092]
算数問題に対するトランスフォーマーに基づくLMの機械的解釈を提案する。
これにより、算術に関連する情報がLMによってどのように処理されるかについての洞察が得られる。
論文 参考訳（メタデータ） (2023-05-24T11:43:47Z) - Amortized Inference for Causal Structure Learning [72.84105256353801]
因果構造を学習することは、通常、スコアまたは独立テストを使用して構造を評価することを伴う探索問題を引き起こす。
本研究では,観測・干渉データから因果構造を予測するため,変分推論モデルを訓練する。
我々のモデルは、実質的な分布シフトの下で頑健な一般化能力を示す。
論文 参考訳（メタデータ） (2022-05-25T17:37:08Z) - Schr\"odinger's Tree -- On Syntax and Neural Language Models [10.296219074343785]
言語モデルは、NLPのワークホースとして登場し、ますます流動的な生成能力を示している。
我々は、多くの次元にまたがる明瞭さの欠如を観察し、研究者が形成する仮説に影響を及ぼす。
本稿では,構文研究における様々な研究課題の意義について概説する。
論文 参考訳（メタデータ） (2021-10-17T18:25:23Z) - Did the Cat Drink the Coffee? Challenging Transformers with Generalized
Event Knowledge [59.22170796793179]
Transformers Language Models (TLMs) を数学的適合のテクトダイナミックな評価のためのベンチマークで検証した。
以上の結果から, TLM は SDM に匹敵する性能が得られることが示された。
しかし、さらなる分析は、TLMがイベント知識の重要な側面を捉えていないことを一貫して示唆している。
論文 参考訳（メタデータ） (2021-07-22T20:52:26Z) - A Constraint-Based Algorithm for the Structural Learning of
Continuous-Time Bayesian Networks [70.88503833248159]
連続時間ベイズネットワークの構造を学習するための制約に基づく最初のアルゴリズムを提案する。
我々は,条件付き独立性を確立するために提案した,異なる統計的テストと基礎となる仮説について論じる。
論文 参考訳（メタデータ） (2020-07-07T07:34:09Z) - Structure learning for CTBN's via penalized maximum likelihood methods [2.997206383342421]
我々は,より困難な課題である構造学習問題について検討し,その課題に関する既存の研究は限られている。
我々のアルゴリズムは、穏やかな規則性条件下で、高い確率でグラフの依存構造を認識することを証明している。
論文 参考訳（メタデータ） (2020-06-13T14:28:19Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。