Fugu-MT 論文翻訳(概要): Sample Complexity of Learning Heuristic Functions for Greedy-Best-First and A* Search

論文の概要: Sample Complexity of Learning Heuristic Functions for Greedy-Best-First and A* Search

arxiv url: http://arxiv.org/abs/2205.09963v3
Date: Tue, 24 May 2022 01:31:01 GMT
ステータス: 処理完了
システム内更新日: 2022-05-25 12:04:34.798265
Title: Sample Complexity of Learning Heuristic Functions for Greedy-Best-First and A* Search
Title（参考訳）: グリーディベストファーストとA*検索のための学習ヒューリスティック関数のサンプル複雑性
Authors: Shinsaku Sakaue, Taihei Oki
Abstract要約: Greedy best-first search (GBFS) と A* search (A*) は、大きなグラフ上でパスフィニングを行うための一般的なアルゴリズムである。 GBFS と A* の学習関数のサンプル複雑性について検討した。整数重み条件下でのGBFS と A* の境界は、$lg n$ factor まで厳密であることを示す。
参考スコア（独自算出の注目度）: 15.191184049312467
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: Greedy best-first search (GBFS) and A* search (A*) are popular algorithms for path-finding on large graphs. Both use so-called heuristic functions, which estimate how close a vertex is to the goal. While heuristic functions have been handcrafted using domain knowledge, recent studies demonstrate that learning heuristic functions from data is effective in many applications. Motivated by this emerging approach, we study the sample complexity of learning heuristic functions for GBFS and A*. We build on a recent framework called \textit{data-driven algorithm design} and evaluate the \textit{pseudo-dimension} of a class of utility functions that measure the performance of parameterized algorithms. Assuming that a vertex set of size $n$ is fixed, we present $\mathrm{O}(n\lg n)$ and $\mathrm{O}(n^2\lg n)$ upper bounds on the pseudo-dimensions for GBFS and A*, respectively, parameterized by heuristic function values. The upper bound for A* can be improved to $\mathrm{O}(n^2\lg d)$ if every vertex has a degree of at most $d$ and to $\mathrm{O}(n \lg n)$ if edge weights are integers bounded by $\mathrm{poly}(n)$. We also give $\Omega(n)$ lower bounds for GBFS and A*, which imply that our bounds for GBFS and A* under the integer-weight condition are tight up to a $\lg n$ factor. Finally, we discuss a case where the performance of A* is measured by the suboptimality and show that we can sometimes obtain a better guarantee by combining a parameter-dependent worst-case bound with a sample complexity bound.
Abstract（参考訳）: greedy best-first search (gbfs) と a* search (a*) は大きなグラフ上の経路探索のための一般的なアルゴリズムである。どちらもいわゆるヒューリスティック関数を使い、頂点が目標にどれだけ近いかを推定する。ヒューリスティック関数はドメイン知識を用いて手作りされているが、近年の研究では、データからのヒューリスティック関数の学習が多くのアプリケーションで有効であることが示されている。そこで本研究では,GBFS と A* の学習ヒューリスティック関数のサンプル複雑性について検討した。我々は最近のフレームワークである \textit{data-driven algorithm design} をベースに構築し,パラメータ化アルゴリズムの性能を測定するユーティリティ関数のクラスである \textit{pseudo-dimension} を評価する。 n$ の大きさの頂点集合が固定されていると仮定すると、gbfs と a* の擬次元に対して $\mathrm{o}(n\lg n)$ と $\mathrm{o}(n^2\lg n)$ 上界をそれぞれヒューリスティック関数の値でパラメータ化したものである。 A* の上界が $\mathrm{O}(n^2\lg d)$ に改善できるのは、すべての頂点が少なくとも $d$ の次数を持ち、さらに $\mathrm{O}(n \lg n)$ が $\mathrm{poly}(n)$ で有界な整数であればである。また、GBFS と A* に対する$\Omega(n)$下界を与え、これは整数重み条件下での GBFS と A* の有界が $\lg n$ factor に固であることを意味する。最後に,パラメータ依存の最悪のケースとサンプルの複雑性のバウンドとを組み合わせることで,A*の性能を最適以下で測定し,より良い保証が得られることを示す。

関連論文リスト

Two-Timescale Gradient Descent Ascent Algorithms for Nonconvex Minimax Optimization [77.3396841985172]
我々は、構造化された非極小最適化問題の解法として、2時間勾配上昇(TTGDA)を統一的に解析する。我々の貢献はTTGDAアルゴリズムを設計することであり、設定を超えて効果的です。
論文参考訳（メタデータ） (2024-08-21T20:14:54Z)
On the instance optimality of detecting collisions and subgraphs [7.055459105099637]
グラフや関数における部分構造検出問題のラベルなしインスタンス最適性について検討する。アルゴリズムが任意の入力に対して満足する$A$を許容すれば、問題は$g(n)$-instanceOptimationである。この結果から,グラフや関数のサブ構造検出問題において,ラベルなしのインスタンス最適性を三分したことが示唆された。
論文参考訳（メタデータ） (2023-12-15T20:50:03Z)
ReSQueing Parallel and Private Stochastic Convex Optimization [59.53297063174519]
本稿では,BFG凸最適化(SCO: Reweighted Query (ReSQue) 推定ツールを提案する。我々はSCOの並列およびプライベート設定における最先端の複雑さを実現するアルゴリズムを開発した。
論文参考訳（メタデータ） (2023-01-01T18:51:29Z)
Lower Bounds on the Worst-Case Complexity of Efficient Global Optimization [11.523746174066702]
我々は、その対応する再生核ヒルベルト空間(RKHS)における球の計量エントロピーの観点から、効率的な大域最適化の複雑さに対する統一された下界を導出する。この下界は、一般に使用される2乗指数核とマタン核の非適応探索アルゴリズムによって達成された上界にほぼ一致することを示す。
論文参考訳（メタデータ） (2022-09-20T11:57:13Z)
Small Covers for Near-Zero Sets of Polynomials and Learning Latent Variable Models [56.98280399449707]
我々は、s$ of cardinality $m = (k/epsilon)o_d(k1/d)$ に対して $epsilon$-cover が存在することを示す。構造的結果に基づいて,いくつかの基本的高次元確率モデル隠れ変数の学習アルゴリズムを改良した。
論文参考訳（メタデータ） (2020-12-14T18:14:08Z)
Hybrid Stochastic-Deterministic Minibatch Proximal Gradient: Less-Than-Single-Pass Optimization with Nearly Optimal Generalization [83.80460802169999]
HSDMPGは、学習モデル上で過大なエラーの順序である$mathcalObig(1/sttnbig)$を達成可能であることを示す。損失係数について、HSDMPGは学習モデル上で過大なエラーの順序である$mathcalObig(1/sttnbig)$を達成できることを示す。
論文参考訳（メタデータ） (2020-09-18T02:18:44Z)
Exact Quantum Query Algorithms Outperforming Parity -- Beyond The Symmetric functions [3.652509571098291]
まず、$Omega left(2fracsqrtn2 right)$非対称関数の直和に基づくクラスに対して、最適な正確な量子クエリアルゴリズム(Q_algo(f)$)を得る。 Q_algo$のクエリ複雑性は$lceil frac3n4 rceil$であるのに対して、$D_oplus(f)$は$n-1$と$lceil frac3n4 rceの間で異なる。
論文参考訳（メタデータ） (2020-08-14T12:17:48Z)
Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文参考訳（メタデータ） (2020-07-07T17:10:00Z)
Provable guarantees for decision tree induction: the agnostic setting [16.784355746717562]
我々は、広く採用され、実証的に成功したトップダウン決定木学習の性能に関する証明可能な保証を与える。すべてのモノトン関数に対して$f$とパラメータ$sin MathN$は、stildeO((log s)/varepsilon2)$でエラーを発生させる決定木を構成する。アルゴリズムの保証は、ほぼ一致する$stildeOmega(log s)$ lower boundで補います。
論文参考訳（メタデータ） (2020-06-01T06:44:07Z)
Agnostic Q-learning with Function Approximation in Deterministic Systems: Tight Bounds on Approximation Error and Sample Complexity [94.37110094442136]
本稿では,決定論的システムにおける関数近似を用いたQ$学習の問題について検討する。もし$delta = Oleft(rho/sqrtdim_Eright)$なら、$Oleft(dim_Eright)$を使って最適なポリシーを見つけることができる。
論文参考訳（メタデータ） (2020-02-17T18:41:49Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。