論文の概要: Strong Admissibility, a Tractable Algorithmic Approach (proofs)
- arxiv url: http://arxiv.org/abs/2204.03551v1
- Date: Thu, 7 Apr 2022 16:22:52 GMT
- ステータス: 処理完了
- システム内更新日: 2022-04-08 18:07:35.633271
- Title: Strong Admissibility, a Tractable Algorithmic Approach (proofs)
- Title（参考訳）: 強い許容性, 扱いやすいアルゴリズム的アプローチ(証明)
- Authors: Martin Caminada, Sri Harikrishnan
- Abstract要約: 比較的小さな許容可能なラベリングを、特定の引数に対してmin-maxナンバリングで構築するアルゴリズムを2つ提案する。
我々のアルゴリズムは、議論に対して絶対最小限の強い許容可能なラベルを与える保証はないが、我々の最高の性能のアルゴリズムは、わずかに大きい結果をもたらす。
- 参考スコア（独自算出の注目度）: 1.3706331473063877
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Much like admissibility is the key concept underlying preferred semantics,
strong admissibility is the key concept underlying grounded semantics, as
membership of a strongly admissible set is sufficient to show membership of the
grounded extension. As such, strongly admissible sets and labellings can be
used as an explanation of membership of the grounded extension, as is for
instance done in some of the proof procedures for grounded semantics. In the
current paper, we present two polynomial algorithms for constructing relatively
small strongly admissible labellings, with associated min-max numberings, for a
particular argument. These labellings can be used as relatively small
explanations for the argument's membership of the grounded extension. Although
our algorithms are not guaranteed to yield an absolute minimal strongly
admissible labelling for the argument (as doing do would have implied an
exponential complexity), our best performing algorithm yields results that are
only marginally bigger. Moreover, the runtime of this algorithm is an order of
magnitude smaller than that of the existing approach for computing an absolute
minimal strongly admissible labelling for a particular argument. As such, we
believe that our algorithms can be of practical value in situations where the
aim is to construct a minimal or near-minimal strongly admissible labelling in
a time-efficient way.
- Abstract（参考訳）: 許容性が優先的意味論の根底にある重要な概念であるのと同様に、強許容性は基底的意味論の根底にある重要な概念であり、強許容性集合の成員は基底的拡張の成員を示すのに十分である。
したがって、強許容集合とラベルリングは、例えば接地意味論の証明手順のいくつかでなされるように、接地拡張のメンバシップの説明として用いられる。
本稿では,特定の引数に対するmin-max数を含む比較的小さな強許容ラベリングを構成する2つの多項式アルゴリズムを提案する。
これらのラベルは、議論の接地拡大のメンバーシップの比較的小さな説明として使うことができる。
我々のアルゴリズムは、議論に対して絶対最小限の許容可能なラベルを与えるという保証はないが(そうすることで指数関数的な複雑さが示唆される)、我々の最高のアルゴリズムは、わずかに大きい結果をもたらす。
さらに、このアルゴリズムの実行時間は、特定の引数に対する絶対最小限の許容可能なラベル付けを計算するための既存のアプローチよりも桁違いに小さい。
このように、我々のアルゴリズムは、時間効率のよい方法で最小または最小の強許容ラベリングを構築することを目的としている状況において、実用的価値を持つことができると信じている。
関連論文リスト
- SemStamp: A Semantic Watermark with Paraphrastic Robustness for Text Generation [72.10931780019297]
既存の透かしアルゴリズムはトークンレベルの設計のため、パラフレーズ攻撃に弱い。
局所性に敏感なハッシュ(LSH)に基づく頑健な文レベルのセマンティック透かしアルゴリズムSemStampを提案する。
実験結果から,本アルゴリズムは従来手法に比べて,従来手法よりも頑健であるだけでなく,生成品質の維持にも有効であることが示唆された。
論文 参考訳（メタデータ） (2023-10-06T03:33:42Z) - From Robustness to Explainability and Back Again [0.685316573653194]
本稿では,形式的説明可能性のスケーラビリティの限界に対処し,形式的説明性を計算するための新しいアルゴリズムを提案する。
提案アルゴリズムは、その代わりに多数のロバストネスクエリに応答して説明を計算し、そのようなクエリの数は、機能数に対して最も線形である。
提案手法の有効性を検証する実験を行った。
論文 参考訳（メタデータ） (2023-06-05T17:21:05Z) - On Computing Probabilistic Abductive Explanations [30.325691263226968]
最も広く研究されているAI(XAI)アプローチは正しくない。
PI説明は重要な欠点も示しており、最も目に見えるものはおそらくその大きさである。
本稿では,多くの広く使用されている分類器に対して,関連する集合を計算するための実践的アプローチについて検討する。
論文 参考訳（メタデータ） (2022-12-12T15:47:10Z) - Admissibility in Strength-based Argumentation: Complexity and Algorithms
(Extended Version with Proofs) [1.5828697880068698]
我々は、適応性に基づく意味論の強度に基づく論証フレームワーク(StrAF)への適応について研究する。
特に文献で定義された強い許容性は望ましい性質、すなわちDungの基本的な補題を満たさないことを示す。
計算(強弱)拡張に対する擬ブール制約の翻訳を提案する。
論文 参考訳（メタデータ） (2022-07-05T18:42:04Z) - Provable Benefits of Actor-Critic Methods for Offline Reinforcement
Learning [85.50033812217254]
アクター批判法はオフラインの強化学習に広く用いられているが、理論的にはそれほどよく理解されていない。
ペシミズムの原理を自然に取り入れた新しいオフラインアクター批判アルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-08-19T17:27:29Z) - Improved Algorithms for Agnostic Pool-based Active Classification [20.12178157010804]
プールに依存しない環境でのバイナリ分類のためのアクティブラーニングを検討する。
我々のアルゴリズムは、画像分類データセットにおけるアートアクティブな学習アルゴリズムの状況よりも優れている。
論文 参考訳（メタデータ） (2021-05-13T18:24:30Z) - Learning Implicitly with Noisy Data in Linear Arithmetic [94.66549436482306]
PAC-セマンティックスにおける暗黙学習を拡張し、線形算術の言語における間隔としきい値の不確実性を扱う。
最適線形プログラミング対象制約の学習に対する我々の暗黙的アプローチは、実際的な明示的アプローチよりも著しく優れていることを示す。
論文 参考訳（メタデータ） (2020-10-23T19:08:46Z) - Adaptive Sampling for Best Policy Identification in Markov Decision
Processes [79.4957965474334]
本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。
最先端アルゴリズムの利点を論じ、解説する。
論文 参考訳（メタデータ） (2020-09-28T15:22:24Z) - Refined bounds for algorithm configuration: The knife-edge of dual class
approximability [94.83809668933021]
トレーニングセットが、トレーニングセット上でのパラメータの平均メトリックのパフォーマンスが、予想される将来的なパフォーマンスに最も近いことを保証するために、どの程度の規模が必要かを調査する。
この近似が L-無限ノルムの下で成り立つなら、強いサンプル複雑性境界を与えることができる。
我々は、コンピュータ科学において最も強力なツールの一つである整数プログラミングの文脈において、我々の限界を実証的に評価する。
論文 参考訳（メタデータ） (2020-06-21T15:32:21Z) - Ranking a set of objects: a graph based least-square approach [70.7866286425868]
同一労働者の群集によるノイズの多いペアワイズ比較から始まる$N$オブジェクトのランク付けの問題について考察する。
品質評価のために,最小二乗内在的最適化基準に依存する非適応的ランキングアルゴリズムのクラスを提案する。
論文 参考訳（メタデータ） (2020-02-26T16:19:09Z) - Entropy Regularized Power k-Means Clustering [21.013169939337583]
本稿では、クローズドフォーム更新と収束保証を享受できるスケーラブルな大規模化最小化アルゴリズムを提案する。
我々の手法は、$k$-meansと$k$-meansと同じ計算量を維持しているが、どちらも大幅に改善されている。
論文 参考訳（メタデータ） (2020-01-10T14:05:44Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。