論文の概要: Lower Bounds for Approximate Knowledge Compilation
- arxiv url: http://arxiv.org/abs/2011.13721v1
- Date: Fri, 27 Nov 2020 13:11:32 GMT
- ステータス: 処理完了
- システム内更新日: 2022-09-20 02:03:53.791030
- Title: Lower Bounds for Approximate Knowledge Compilation
- Title（参考訳）: 近似知識コンパイルのための下限
- Authors: Alexis de Colnet and Stefan Mengel
- Abstract要約: 我々は、決定論的分解可能な否定正規形(d-DNNF)の回路に焦点をあてる。
我々は近似の弱い近似と強い近似という2つの概念を定式化する。
D-DNNFによる近似値の低い値を示し,文献の正の結果を補完する。
- 参考スコア（独自算出の注目度）: 7.538482310185135
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Knowledge compilation studies the trade-off between succinctness and
efficiency of different representation languages. For many languages, there are
known strong lower bounds on the representation size, but recent work shows
that, for some languages, one can bypass these bounds using approximate
compilation. The idea is to compile an approximation of the knowledge for which
the number of errors can be controlled. We focus on circuits in deterministic
decomposable negation normal form (d-DNNF), a compilation language suitable in
contexts such as probabilistic reasoning, as it supports efficient model
counting and probabilistic inference. Moreover, there are known size lower
bounds for d-DNNF which by relaxing to approximation one might be able to
avoid. In this paper we formalize two notions of approximation: weak
approximation which has been studied before in the decision diagram literature
and strong approximation which has been used in recent algorithmic results. We
then show lower bounds for approximation by d-DNNF, complementing the positive
results from the literature.
- Abstract（参考訳）: 知識コンパイルは、異なる表現言語の簡潔性と効率のトレードオフを研究する。
多くの言語では、表現サイズには強い下限が知られているが、最近の研究は、いくつかの言語では、近似コンパイルを用いてこれらの境界をバイパスできることを示している。
その考え方は、エラーの数をコントロールすることができる知識の近似をコンパイルすることである。
効率的なモデルカウントと確率的推論をサポートするため,確率的推論などの文脈に適したコンパイル言語d-dnnf(decomposable negation normal form)の回路に焦点を当てた。
さらに、d-DNNF には、近似に緩和することで回避できるような、既知のサイズの低い境界が存在する。
本稿では,従来研究されてきた弱い近似と,近年のアルゴリズム的な結果に用いられている強い近似という,近似の2つの概念を定式化する。
次に、d-DNNFによる近似の下位境界を示し、文献の正の結果を補完する。
関連論文リスト
- Efficient Nearest Neighbor based Uncertainty Estimation for Natural Language Processing Tasks [26.336947440529713]
$k$-Nearest Neearbor Uncertainty Estimation (k$NN-UE) は、隣人からの距離と、隣人のラベル存在率を利用する不確実性推定手法である。
実験の結果,提案手法は信頼性校正,選択予測,分布外検出において,ベースラインや最近の密度に基づく手法よりも優れていることがわかった。
論文 参考訳（メタデータ） (2024-07-02T10:33:31Z) - Eliminating Unintended Stable Fixpoints for Hybrid Reasoning Systems [5.208405959764274]
本稿では,AFTに類似した手法を導入し,事前計算した上界を利用して意味をより正確に把握する手法を提案する。
我々は、最先端の近似器を拡張することで、MKNF(最小限の知識と失敗を否定する)の知識ベースへのフレームワークの適用性を実証する。
論文 参考訳（メタデータ） (2023-07-21T01:08:15Z) - Differentially-Private Hierarchical Clustering with Provable
Approximation Guarantees [79.59010418610625]
階層クラスタリングのための微分プライベート近似アルゴリズムについて検討する。
例えば、$epsilon$-DPアルゴリズムは入力データセットに対して$O(|V|2/epsilon)$-additiveエラーを示さなければならない。
本稿では,ブロックを正確に復元する1+o(1)$近似アルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-01-31T19:14:30Z) - A deep learning approach to the probabilistic numerical solution of
path-dependent partial differential equations [1.09650651784511]
PPDEの解は確率的表現によって近似することができ、回帰を用いた条件予測の推定によって文献に実装されている。
我々は,この制限をディープラーニング手法を用いて克服し,条件付き期待値の近似に対する誤差境界の導出を可能にすることを示す。
他のディープラーニングアプローチと比較して、我々のアルゴリズムは、特に大きな次元において、より正確であるように見える。
論文 参考訳（メタデータ） (2022-09-28T14:34:58Z) - Posterior and Computational Uncertainty in Gaussian Processes [52.26904059556759]
ガウスのプロセスはデータセットのサイズとともに違法にスケールする。
多くの近似法が開発されており、必然的に近似誤差を導入している。
この余分な不確実性の原因は、計算が限られているため、近似後部を使用すると完全に無視される。
本研究では,観測された有限個のデータと有限個の計算量の両方から生じる組合せ不確実性を一貫した推定を行う手法の開発を行う。
論文 参考訳（メタデータ） (2022-05-30T22:16:25Z) - Reasoning Through Memorization: Nearest Neighbor Knowledge Graph
Embeddings [29.94706167233985]
kNN-KGEは、事前訓練された言語モデルを用いた新しい知識グラフ埋め込みアプローチである。
我々は、知識ストアからのエンティティ埋め込み空間内の距離に基づいて、最も近い隣人を計算する。
論文 参考訳（メタデータ） (2022-01-14T17:35:16Z) - On the Minimal Adversarial Perturbation for Deep Neural Networks with
Provable Estimation Error [65.51757376525798]
敵の摂動の存在は、証明可能な堅牢性に関する興味深い研究ラインを開いた。
検証可能な結果は、コミットしたエラーを見積り、バウンドするものではない。
本稿では,最小対向摂動を求めるための2つの軽量戦略を提案する。
その結果, 提案手法は, 分類に近い試料の理論的距離とロバスト性を近似し, 敵攻撃に対する確実な保証が得られた。
論文 参考訳（メタデータ） (2022-01-04T16:40:03Z) - Amortized Conditional Normalized Maximum Likelihood: Reliable Out of
Distribution Uncertainty Estimation [99.92568326314667]
本研究では,不確実性推定のための拡張性のある汎用的アプローチとして,償却条件正規化最大値(ACNML)法を提案する。
提案アルゴリズムは条件付き正規化最大度(CNML)符号化方式に基づいており、最小記述長の原理に従って最小値の最適特性を持つ。
我々は、ACNMLが、分布外入力のキャリブレーションの観点から、不確実性推定のための多くの手法と好意的に比較することを示した。
論文 参考訳（メタデータ） (2020-11-05T08:04:34Z) - Lower bounds in multiple testing: A framework based on derandomized
proxies [107.69746750639584]
本稿では, 各種コンクリートモデルへの適用例を示す, デランドマイズに基づく分析戦略を提案する。
これらの下界のいくつかを数値シミュレーションし、Benjamini-Hochberg (BH) アルゴリズムの実際の性能と密接な関係を示す。
論文 参考訳（メタデータ） (2020-05-07T19:59:51Z) - Lagrangian Decomposition for Neural Network Verification [148.0448557991349]
ニューラルネットワーク検証の基本的なコンポーネントは、出力が取ることのできる値のバウンダリの計算である。
ラグランジアン分解に基づく新しい手法を提案する。
ランニングタイムのごく一部で、既成の解法に匹敵するバウンダリが得られることを示す。
論文 参考訳（メタデータ） (2020-02-24T17:55:10Z) - Proximity Preserving Binary Code using Signed Graph-Cut [27.098042566421963]
本稿では,PPC(Proximity Preserving Code)と呼ばれるバイナリ埋め込みフレームワークを紹介し,データポイント間の類似性と相似性を学習し,コンパクトで親和性に配慮したバイナリコードを生成する。
提案手法は, 精度と複雑性の両面において, 一般的なスペクトル法よりも優れていることを示す。
論文 参考訳（メタデータ） (2020-02-05T13:58:41Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。