論文の概要: Error Analysis and Correction for Weighted A*'s Suboptimality (Extended Version)

• arxiv url: http://arxiv.org/abs/1905.11346v3
• Date: Fri, 26 May 2023 08:56:36 GMT
• ステータス: 処理完了
• システム内更新日: 2023-05-30 01:18:41.797597
• Title: Error Analysis and Correction for Weighted A*'s Suboptimality (Extended Version)
• Title（参考訳）: 重み付きA*の準最適性の誤差解析と補正(拡張版)
• Authors: Robert C. Holte, Ruben Majadas, Alberto Pozanco, Daniel Borrajo
• Abstract要約: 重み付きA* (wA*) は計画問題や探索問題の解法として広く用いられているアルゴリズムである。 W は wA* の解の真の部分最適性からかけ離れていることを示す。
• 参考スコア（独自算出の注目度）: 4.112020427539586
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Weighted A* (wA*) is a widely used algorithm for rapidly, but suboptimally, solving planning and search problems. The cost of the solution it produces is guaranteed to be at most W times the optimal solution cost, where W is the weight wA* uses in prioritizing open nodes. W is therefore a suboptimality bound for the solution produced by wA*. There is broad consensus that this bound is not very accurate, that the actual suboptimality of wA*'s solution is often much less than W times optimal. However, there is very little published evidence supporting that view, and no existing explanation of why W is a poor bound. This paper fills in these gaps in the literature. We begin with a large-scale experiment demonstrating that, across a wide variety of domains and heuristics for those domains, W is indeed very often far from the true suboptimality of wA*'s solution. We then analytically identify the potential sources of error. Finally, we present a practical method for correcting for two of these sources of error and experimentally show that the correction frequently eliminates much of the error.
• Abstract（参考訳）: 重み付きA* (wA*) は計画問題や探索問題の解法として広く使われているアルゴリズムである。 生成する解のコストは、Wが開ノードの優先順位付けに使用する重量 wA* である最適解コストの少なくとも W 倍であることが保証されている。 したがって、W は wA* によって生成される解に対して準最適である。 この境界はそれほど正確ではなく、wA* の解の実際の準最適性は、しばしば W 倍の最適値よりもはるかに小さいという広い見解がある。 しかし、この見解を支持する証拠はほとんど発表されておらず、なぜ W が境界が弱いのかを説明できない。 この論文は文学におけるこれらのギャップを埋める。 我々は、これらの領域に対する様々な領域とヒューリスティックスにおいて、W が wA* の解の真の準最適性からかなり離れていることを示す大規模な実験から始める。 次に、潜在的なエラー源を解析的に同定する。 最後に,これら2つの誤り源を補正する実用的手法を提案し,その補正がエラーの多くを頻繁に除去することを示す。

関連論文リスト

• Optimal and Near-Optimal Adaptive Vector Quantization [16.628351691108687]
  量子化は、圧縮、モデルウェイトとアクティベーション、データセットを含む多くの機械学習ユースケースの基本的な最適化である。 本稿では,適応ベクトル量子化(AVQ)問題を再検討し,時間と空間の複雑さを改善した最適解を求めるアルゴリズムを提案する。 我々のアルゴリズムは、さまざまな機械学習アプリケーションでより広範囲にAVQを使用するための扉を開く可能性がある。
  論文  参考訳（メタデータ） (2024-02-05T16:27:59Z)
• A Dimensionality Reduction Method for Finding Least Favorable Priors with a Focus on Bregman Divergence [108.28566246421742]
  そこで本研究では,次元に明示的な有界な有限次元設定に最適化を移動させることができる次元削減法を開発した。 この問題を進展させるため、比較的大きな損失関数、すなわちブレグマンの発散によって引き起こされるベイズ的リスクに限定する。
  論文  参考訳（メタデータ） (2022-02-23T16:22:28Z)
• Learning Proximal Operators to Discover Multiple Optima [66.98045013486794]
  非家族問題における近位演算子を学習するためのエンドツーエンド手法を提案する。 本手法は,弱い目的と穏やかな条件下では,世界規模で収束することを示す。
  論文  参考訳（メタデータ） (2022-01-28T05:53:28Z)
• Fast Batch Nuclear-norm Maximization and Minimization for Robust Domain Adaptation [154.2195491708548]
  ランダムに選択されたデータバッチの分類出力行列の構造について検討し,予測可能性と多様性について検討した。 本稿では,目標出力行列上で核ノルムを行い,目標予測能力を向上するBatch Nuclear-norm Maximization and Minimizationを提案する。 実験により,本手法は3つの典型的なドメイン適応シナリオにおいて適応精度とロバスト性を高めることができることが示された。
  論文  参考訳（メタデータ） (2021-07-13T15:08:32Z)
• Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex Decentralized Optimization Over Time-Varying Networks [79.16773494166644]
  通信ネットワークのノード間を分散的に保存するスムーズで強い凸関数の和を最小化するタスクについて検討する。 我々は、これらの下位境界を達成するための2つの最適アルゴリズムを設計する。 我々は,既存の最先端手法と実験的な比較を行うことにより,これらのアルゴリズムの理論的効率を裏付ける。
  論文  参考訳（メタデータ） (2021-06-08T15:54:44Z)
• Instance Specific Approximations for Submodular Maximization [45.91235224228292]
  実世界のインスタンス上で最適な解に対して,アルゴリズムの性能をベンチマークする手法を模索する。 大きな疑問は、実際に遭遇したインスタンスの最適なソリューションと比較して、アルゴリズムのパフォーマンスを測定する方法です。 我々の主な貢献は、サブモジュラー最小化のための新しいアルゴリズムではなく、サブモジュラーインスタンスのアルゴリズムがいかに最適かを測定する分析手法である。
  論文  参考訳（メタデータ） (2021-02-23T19:39:32Z)
• Conservative Stochastic Optimization with Expectation Constraints [11.393603788068777]
  本稿では,データ指標や環境変数に関して,目的関数と制約関数が期待する凸最適化問題を考察する。 このような問題を解決するためのオンラインおよび効率的なアプローチは、広く研究されていない。 本稿では、制約違反をゼロとし、$Oleft(T-frac12right)$Optimity gapを実現する新しい保守的最適化アルゴリズム(CSOA)を提案する。
  論文  参考訳（メタデータ） (2020-08-13T08:56:24Z)
• Hardness of Random Optimization Problems for Boolean Circuits, Low-Degree Polynomials, and Langevin Dynamics [78.46689176407936]
  アルゴリズムの族は高い確率でほぼ最適な解を生成できないことを示す。 ブール回路の場合、回路複雑性理論で知られている最先端境界を改善する。
  論文  参考訳（メタデータ） (2020-04-25T05:45:59Z)
• Runtime Analysis of Evolutionary Algorithms with Biased Mutation for the Multi-Objective Minimum Spanning Tree Problem [12.098400820502635]
  我々は,Spanning Tree (MST) 問題を単目的および多目的バージョンで検討する。 我々は、低い支配数の観点から低いランクのエッジの選択に重点を置くバイアス付き突然変異を導入する。 我々は、非偏見または偏見のあるエッジ選択を決定する突然変異演算子の組み合わせが、最悪の場合、上界(unbiased mutation)を示すことを示した。
  論文  参考訳（メタデータ） (2020-04-22T07:47:00Z)
• Revisiting SGD with Increasingly Weighted Averaging: Optimization and Generalization Perspectives [50.12802772165797]
  平均化手法は、全ての反復解を一つの解に結合する。 実験は、他の平均化方式と比較して、トレードオフと平均化の有効性を示した。
  論文  参考訳（メタデータ） (2020-03-09T18:14:00Z)

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

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