論文の概要: Efficient Explanations for Knowledge Compilation Languages
- arxiv url: http://arxiv.org/abs/2107.01654v1
- Date: Sun, 4 Jul 2021 14:45:32 GMT
- ステータス: 処理完了
- システム内更新日: 2021-07-07 02:09:50.638147
- Title: Efficient Explanations for Knowledge Compilation Languages
- Title(参考訳): 知識コンパイル言語のための効率的な説明
- Authors: Xuanxiang Huang and Yacine Izza and Alexey Ignatiev and Martin C.
Cooper and Nicholas Asher and Joao Marques-Silva
- Abstract要約: 本稿では、最もよく知られているKC言語の多くに対して、よく知られた説明のクラスを時間内に計算できることを示す。
また,説明文をd-DNNFよりも簡潔なKC言語に拡張できる条件についても検討した。
- 参考スコア(独自算出の注目度): 17.82645653054042
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Knowledge compilation (KC) languages find a growing number of practical uses,
including in Constraint Programming (CP) and in Machine Learning (ML). In most
applications, one natural question is how to explain the decisions made by
models represented by a KC language. This paper shows that for many of the best
known KC languages, well-known classes of explanations can be computed in
polynomial time. These classes include deterministic decomposable negation
normal form (d-DNNF), and so any KC language that is strictly less succinct
than d-DNNF. Furthermore, the paper also investigates the conditions under
which polynomial time computation of explanations can be extended to KC
languages more succinct than d-DNNF.
- Abstract(参考訳): 知識コンパイル(KC)言語は、制約プログラミング(CP)や機械学習(ML)など、実用的な用途が増えている。
ほとんどのアプリケーションにおいて、自然な疑問は、KC言語で表されるモデルによる決定をどのように説明するかである。
本稿では、最もよく知られたkc言語の多くにおいて、よく知られた説明クラスを多項式時間で計算できることを示す。
これらのクラスには、決定論的分解可能な否定正規形式(d-DNNF)が含まれ、したがって、d-DNNFよりも厳密に簡潔でない任意のKC言語が含まれる。
さらに,説明の多項式時間計算を,d-DNNFよりも簡潔なKC言語に拡張できる条件についても検討した。
関連論文リスト
- Executing Natural Language-Described Algorithms with Large Language Models: An Investigation [48.461999568129166]
自然言語で概説したアルゴリズムを理解・実行するための,今日の大規模言語モデルの能力について検討する。
我々は、30個のアルゴリズムを選択し、300個のランダムサンプリングされたインスタンスを生成し、人気のあるLCMがこれらのアルゴリズムを理解し実行できるかを評価した。
この結果から,LLM,特にGPT-4は,重数値計算を伴わない限り,自然言語で記述されたプログラムを効果的に実行できることが判明した。
論文 参考訳(メタデータ) (2024-02-23T05:31:36Z) - Natural Language Embedded Programs for Hybrid Language Symbolic
Reasoning [86.92053166457116]
本研究では,数学・記号的推論,自然言語理解,後続の課題に対処するための統合フレームワークとして,自然言語組み込みプログラム(NLEP)を提案する。
我々のアプローチは,構造化知識の自然言語表現を含むデータ構造上の関数を定義する完全なPythonプログラムを生成するよう,言語モデルに促す。
Pythonインタープリタが生成されたコードを実行し、出力をプリントする。
論文 参考訳(メタデータ) (2023-09-19T17:54:21Z) - Top-Down Knowledge Compilation for Counting Modulo Theories [11.086759883832505]
入力式が決定論的分解可能な否定正規形(d-DNNF)である場合、仮説モデルカウントは効率的に解ける。
トップダウン知識コンパイルは#SAT問題を解決する最先端技術である。
我々は,DPLL(T)探索の痕跡に基づくトップダウンコンパイラを提唱する。
論文 参考訳(メタデータ) (2023-06-07T15:46:28Z) - A Survey of Knowledge Enhanced Pre-trained Language Models [78.56931125512295]
我々は、知識強化事前学習言語モデル(KE-PLMs)の包括的なレビューを行う。
NLUでは、言語知識、テキスト知識、知識グラフ(KG)、ルール知識の4つのカテゴリに分類する。
NLGのKE-PLMは、KGベースと検索ベースに分類される。
論文 参考訳(メタデータ) (2022-11-11T04:29:02Z) - The Surprising Computational Power of Nondeterministic Stack RNNs [20.996069249108224]
従来のリカレントニューラルネットワーク(RNN)は、固定された有限個のメモリセルを持つ。
本稿では,非決定論とニューラルコントローラが相互作用して,より予期せぬ2つの能力を生み出すことを示す。
まず、非決定論的スタック RNN は CFL だけでなく、多くの非文脈自由言語を認識できる。
第二に、スタックアルファベットのサイズを考えると、予想されるよりもはるかに大きなアルファベットサイズを持つ言語を認識できる。
論文 参考訳(メタデータ) (2022-10-04T03:18:19Z) - Machine Reading, Fast and Slow: When Do Models "Understand" Language? [59.897515617661874]
本稿では,2つの言語スキル(コア参照の解決と比較)に関して,理解モデルを読み取る行動について検討する。
比較のため(コアではない)、より大きなエンコーダに基づくシステムは、より「正しい」情報に依存する傾向にあることがわかった。
論文 参考訳(メタデータ) (2022-09-15T16:25:44Z) - LISA: Learning Interpretable Skill Abstractions from Language [85.20587800593293]
言語条件による実演から多種多様な解釈可能なスキルを学習できる階層型模倣学習フレームワークを提案する。
本手法は, 逐次的意思決定問題において, 言語に対するより自然な条件付け方法を示す。
論文 参考訳(メタデータ) (2022-02-28T19:43:24Z) - On Deciding Feature Membership in Explanations of SDD & Related
Classifiers [0.685316573653194]
この論文は、幅広い分類器のクラスに対してSigmaP$に対して、特徴メンバシップ問題(FMP)が難しいことを示している。
本稿では,SDD(Sentential Decision Diagrams)と他の命題言語に代表される分類器の命題符号化を提案する。
論文 参考訳(メタデータ) (2022-02-15T16:38:53Z) - On Efficiently Explaining Graph-Based Classifiers [16.199563506727316]
本稿では,決定木 (DT) が解釈可能であるだけでなく,DT の 1 つのPI-Explanation を計算するためのリアルタイムアルゴリズムを提案する。
さらに,1つの対照的な説明を計算するためのリアルタイムアルゴリズムを提案する。
論文 参考訳(メタデータ) (2021-06-02T17:55:41Z) - Lower Bounds for Approximate Knowledge Compilation [7.538482310185135]
我々は、決定論的分解可能な否定正規形(d-DNNF)の回路に焦点をあてる。
我々は近似の弱い近似と強い近似という2つの概念を定式化する。
D-DNNFによる近似値の低い値を示し,文献の正の結果を補完する。
論文 参考訳(メタデータ) (2020-11-27T13:11:32Z) - X-FACTR: Multilingual Factual Knowledge Retrieval from Pretrained
Language Models [103.75890012041366]
言語モデル(LM)は、事実の知識を捉えるのに驚くほど成功した。
しかし、LMの実際の表現能力の研究は、ほぼ間違いなく英語で行われている。
我々は23の語型的多様言語に対するクローゼスタイルプローブのベンチマークを作成する。
論文 参考訳(メタデータ) (2020-10-13T05:29:56Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。