論文の概要: A Multivariate Complexity Analysis of Qualitative Reasoning Problems
- arxiv url: http://arxiv.org/abs/2209.15275v1
- Date: Fri, 30 Sep 2022 07:29:53 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-03 16:18:11.323275
- Title: A Multivariate Complexity Analysis of Qualitative Reasoning Problems
- Title(参考訳): 質的推論問題の多変量複雑性解析
- Authors: Leif Eriksson, Victor Lagerkvist
- Abstract要約: 我々は、それぞれ$f(k) cdot 2O(n)$, $f(k)n$, timeで解ける問題のクラス FPE と XE を紹介する。
有効幅$k$の部分順序時間問題は16kn$時間で解決可能であり,XEに含まれることを示す。
また、アレンの区間代数のネットワーク整合性問題は、$k$以上と重複しないが、$(2nk)2k cdot 2n$ timeで解決可能であり、その中に含まれることを示す。
- 参考スコア(独自算出の注目度): 9.594432031144716
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Qualitative reasoning is an important subfield of artificial intelligence
where one describes relationships with qualitative, rather than numerical,
relations. Many such reasoning tasks, e.g., Allen's interval algebra, can be
solved in $2^{O(n \cdot \log n)}$ time, but single-exponential running times
$2^{O(n)}$ are currently far out of reach. In this paper we consider
single-exponential algorithms via a multivariate analysis consisting of a
fine-grained parameter $n$ (e.g., the number of variables) and a coarse-grained
parameter $k$ expected to be relatively small. We introduce the classes FPE and
XE of problems solvable in $f(k) \cdot 2^{O(n)}$, respectively $f(k)^n$, time,
and prove several fundamental properties of these classes. We proceed by
studying temporal reasoning problems and (1) show that the Partially Ordered
Time problem of effective width $k$ is solvable in $16^{kn}$ time and is thus
included in XE, and (2) that the network consistency problem for Allen's
interval algebra with no interval overlapping with more than $k$ others is
solvable in $(2nk)^{2k} \cdot 2^{n}$ time and is included in FPE. Our
multivariate approach is in no way limited to these to specific problems and
may be a generally useful approach for obtaining single-exponential algorithms.
- Abstract(参考訳): 定性的推論は、数値ではなく定性的関係を記述する人工知能の重要なサブフィールドである。
例えば、アレンの区間代数(英語版)のような多くの推論タスクは 2^{O(n \cdot \log n)} の時間で解けるが、単指数ランニング時間 2^{O(n)}$ は今のところ到達できない。
本稿では,小粒度パラメータ$n$(変数数など)と粗粒度パラメータ$k$が比較的小さいと期待される粗粒度パラメータ$k$からなる多変量解析による単一指数アルゴリズムを考える。
f(k) \cdot 2^{o(n)}$,それぞれ$f(k)^n$, time で解ける問題のクラス fpe と xe を導入し、これらのクラスの基本特性を証明した。
我々は時間的推論問題を研究し、(1)有効幅$k$の部分順序時間問題が16^{kn}$時間で解け、XEに含まれることを示し、(2)$k$以上で重なり合う間隔を持たないアレンの区間代数のネットワーク整合性問題は、$(2nk)^{2k} \cdot 2^{n}$時間で解け、FPEに含まれることを示す。
我々の多変量アプローチは特定の問題に限らず、単一指数アルゴリズムを得るのに一般的に有用なアプローチである。
関連論文リスト
- Agnostically Learning Multi-index Models with Queries [54.290489524576756]
本稿では,ガウス分布下での非依存学習の課題に対するクエリアクセスのパワーについて検討する。
クエリアクセスは、MIMを不可知的に学習するためのランダムな例よりも大幅に改善されていることを示す。
論文 参考訳(メタデータ) (2023-12-27T15:50:47Z) - A polynomial quantum computing algorithm for solving the dualization
problem [75.38606213726906]
2つの単調素関数 $f:0,1n to 0,1$ と $g:0,1n to 0,1$ が与えられたとき、双対化問題は$g$が$f$の双対かどうかを決定することである。
本稿では,双対化問題の決定版を時間内に解く量子コンピューティングアルゴリズムを提案する。
論文 参考訳(メタデータ) (2023-08-28T18:12:54Z) - Improved Algorithms for Allen's Interval Algebra by Dynamic Programming
with Sublinear Partitioning [9.594432031144716]
アレンの区間代数は質的時間的推論において最もよく知られた計算の1つである。
NPハードな定性推論問題を解くための新しい枠組みを提案する。
我々はアレンの区間代数に対して$O*((fraccnlogn)n)$の大きな改善を得る。
論文 参考訳(メタデータ) (2023-05-25T11:45:12Z) - Fast Attention Requires Bounded Entries [19.17278873525312]
内部製品注意計算はTransformer, GPT-1, BERT, GPT-2, GPT-3, ChatGPTなどの大規模言語モデルを訓練するための基本的なタスクである。
行列を暗黙的に$A$とすることで、より高速なアルゴリズムが可能かどうかを検討する。
このことは、入力行列がより小さいエントリを持つ場合、注意計算の方がはるかに効率的である、実際に観察された現象の理論的な説明を与える。
論文 参考訳(メタデータ) (2023-02-26T02:42:39Z) - Near-Optimal Regret Bounds for Multi-batch Reinforcement Learning [54.806166861456035]
本研究では,有限水平マルコフ決定過程(MDP)によってモデル化されたエピソディック強化学習(RL)問題をバッチ数に制約を加えて検討する。
我々は,$tildeO(sqrtSAH3Kln (1/delta))$tildeO(cdot)をほぼ最適に後悔するアルゴリズムを設計し,$(S,A,H,K)$の対数項を$K$で隠蔽する。
技術的貢献は2つある: 1) 探索のためのほぼ最適設計スキーム
論文 参考訳(メタデータ) (2022-10-15T09:22:22Z) - TURF: A Two-factor, Universal, Robust, Fast Distribution Learning
Algorithm [64.13217062232874]
最も強力で成功したモダリティの1つは、全ての分布を$ell$距離に近似し、基本的に最も近い$t$-piece次数-$d_$の少なくとも1倍大きい。
本稿では,この数値をほぼ最適に推定する手法を提案する。
論文 参考訳(メタデータ) (2022-02-15T03:49:28Z) - Computational Complexity of Normalizing Constants for the Product of
Determinantal Point Processes [12.640283469603357]
正規化定数の計算における計算複雑性について検討する。
例えば、$sum_Sdet(bf A_S,S)p$は、すべての(固定された)正の偶数に対して、$p$ が UP-hard で Mod$_3$P-hard であることを示す。
論文 参考訳(メタデータ) (2021-11-28T14:08:25Z) - Solving Infinite-Domain CSPs Using the Patchwork Property [17.101875753030754]
制約問題(CSP)は、コンピュータ科学とAIにおいて重要な応用である。
非常に成功したアプローチは、基礎となる原始グラフのツリー幅を束縛することである。
基本関係がパッチワーク特性を持つCSPに対して、これを$f(w)cdot nO(1)$に制限する。
論文 参考訳(メタデータ) (2021-07-03T13:04:41Z) - Learning a Latent Simplex in Input-Sparsity Time [58.30321592603066]
我々は、$AinmathbbRdtimes n$へのアクセスを考えると、潜入$k$-vertex simplex $KsubsetmathbbRdtimes n$を学習する問題を考える。
実行時間における$k$への依存は、トップ$k$特異値の質量が$a$であるという自然な仮定から不要であることを示す。
論文 参考訳(メタデータ) (2021-05-17T16:40:48Z) - The Sparse Hausdorff Moment Problem, with Application to Topic Models [5.151973524974052]
我々は$m=2k$iid二進確率変数のサンプルを用いて$k$-mixtureを同定するアルゴリズムを提案する。
加法精度$w_mincdotzetaO(k)$のモーメントを知るだけで十分である。
論文 参考訳(メタデータ) (2020-07-16T04:23:57Z) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳(メタデータ) (2020-07-07T17:10:00Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。