論文の概要: 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に含まれることを示す。
我々の多変量アプローチは特定の問題に限らず、単一指数アルゴリズムを得るのに一般的に有用なアプローチである。
関連論文リスト
- Approximating the Number of Relevant Variables in a Parity Implies Proper Learning [0.0]
パリティ関数の関連変数数を近似することはパリティを適切に学習するのと同じくらい難しいことを示す。
2つ目の結果では、任意の$T(n)$-timeアルゴリズムから、任意のパリティ$f$に対して、関連する変数の数を$gamma$-approximation($d(f)$ of $f$)を返すことを示す。
論文 参考訳（メタデータ） (2024-07-16T15:20:30Z) - A First Running Time Analysis of the Strength Pareto Evolutionary Algorithm 2 (SPEA2) [22.123838452178585]
本研究では, 強度進化アルゴリズム2 (SPEA2) の動作時間解析を行った。
具体的には、一般的に使用される3つの多目的問題、すなわち$m$OneMinMax、$m$LeadingOnesZeroes、$m$-OneZeroJumpを解決するためのSPEA2の実行時間が期待されていることを証明します。
論文 参考訳（メタデータ） (2024-06-23T14:12:22Z) - Efficient Solution of Point-Line Absolute Pose [52.775981113238046]
点や線である可能性のある特徴間の3D--2D対応に基づくポーズ推定の特定の問題を再検討する。
得られた解法は数値的に安定かつ高速であることを示す。
論文 参考訳（メタデータ） (2024-04-25T12:09:16Z) - Matching the Statistical Query Lower Bound for k-sparse Parity Problems with Stochastic Gradient Descent [83.85536329832722]
勾配勾配降下(SGD)は,$d$次元ハイパーキューブ上の$k$パリティ問題を効率的に解くことができることを示す。
次に、SGDでトレーニングされたニューラルネットワークがどのようにして、小さな統計的エラーで$k$-parityの問題を解決するかを実証する。
論文 参考訳（メタデータ） (2024-04-18T17:57:53Z) - 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) - 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) - Solving Infinite-Domain CSPs Using the Patchwork Property [17.101875753030754]
制約問題(CSP)は、コンピュータ科学とAIにおいて重要な応用である。
非常に成功したアプローチは、基礎となる原始グラフのツリー幅を束縛することである。
基本関係がパッチワーク特性を持つCSPに対して、これを$f(w)cdot nO(1)$に制限する。
論文 参考訳（メタデータ） (2021-07-03T13:04:41Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。