論文の概要: Expected Runtime Comparisons Between Breadth-First Search and Constant-Depth Restarting Random Walks
- arxiv url: http://arxiv.org/abs/2406.16697v1
- Date: Mon, 24 Jun 2024 15:00:59 GMT
- ステータス: 処理完了
- システム内更新日: 2024-06-25 14:25:06.444565
- Title: Expected Runtime Comparisons Between Breadth-First Search and Constant-Depth Restarting Random Walks
- Title（参考訳）: Breadth-First SearchとConstant-Depth Restarting Random Walksの比較
- Authors: Daniel Platnick, Richard Anthony Valenzano,
- Abstract要約: 広帯域探索(BrFS)と一定深度再起動ランダムウォーク(RRW)の性能解析を行った。
RRW が BrFS よりも高速であることは,その目標深度に十分な目標がある場合に証明する。
我々の境界線は、木の分岐係数、ゴール深さ、ランダムウォーク深さの誤差とともに、交差点が直線的に成長することを示している。
- 参考スコア（独自算出の注目度）: 1.9735829027026905
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: When greedy search algorithms encounter a local minima or plateau, the search typically devolves into a breadth-first search (BrFS), or a local search technique is used in an attempt to find a way out. In this work, we formally analyze the performance of BrFS and constant-depth restarting random walks (RRW) -- two methods often used for finding exits to a plateau/local minima -- to better understand when each is best suited. In particular, we formally derive the expected runtime for BrFS in the case of a uniformly distributed set of goals at a given goal depth. We then prove RRW will be faster than BrFS on trees if there are enough goals at that goal depth. We refer to this threshold as the crossover point. Our bound shows that the crossover point grows linearly with the branching factor of the tree, the goal depth, and the error in the random walk depth, while the size of the tree grows exponentially in branching factor and goal depth. Finally, we discuss the practical implications and applicability of this bound.
- Abstract（参考訳）: グリージー検索アルゴリズムが局所的なミニマや高原に遭遇すると、検索は通常、幅優先探索(BrFS)に変換される。
本研究では,BrFSと一定深度再起動型ランダムウォーク(RRW)の性能を,高原/地方ミニマへの出口を見つけるためによく使用される2つの手法で解析し,それぞれが適しているタイミングをよりよく理解する。
特に,所定の目標深度で一様に分散された目標セットの場合,BrFSの予測ランタイムを正式に導出する。
そして、そのゴール深さに十分な目標がある場合、RRWがBrFSよりも高速であることを証明します。
我々はこのしきい値をクロスオーバーポイントと呼ぶ。
我々の境界線は、木の分岐係数、ゴール深さ、ランダムウォーク深さの誤差と交叉点が線形に成長し、一方、木の大きさは分岐係数とゴール深さで指数関数的に成長することを示している。
最後に、この境界の実用的意味と適用性について論じる。
関連論文リスト
- Depth-Bounded Epistemic Planning [50.42592219248395]
本稿では,動的てんかん論理に基づく新しい計画法を提案する。
新規性は、計画エージェントの推論の深さを上界bに制限することである。
推論深度の境界b内における解を持つ計画タスクに関して、完全なものであることを示す。
論文 参考訳（メタデータ） (2024-06-03T09:30:28Z) - Hierarchical Clustering via Local Search [0.0]
階層クラスタリングのための局所探索アルゴリズムを提案する。
任意の局所最適木は少なくとも$fracn-23sum_i jw(i,j)$の収益を保証し、そこでは$n$はオブジェクトの数で、$w: [n] times [n] mathbbR+$は関連する類似関数である。
論文 参考訳（メタデータ） (2024-05-24T23:46:24Z) - Lookback for Learning to Branch [77.32867454769936]
Bipartite Graph Neural Networks (GNN) は、ディープラーニングに基づくMixed-Integer Linear Program (MILP) の重要コンポーネントであることが示されている。
近年の研究では、分岐とバウンド(B&B)の解法における分岐(可変選択)を置き換える上で、そのようなGNNの有効性が実証されている。
論文 参考訳（メタデータ） (2022-06-30T02:33:32Z) - Stagnation Detection in Highly Multimodal Fitness Landscapes [0.0]
局所最適化から逃れるためのランダム化探索のメカニズムとして,定常検出法が提案されている。
本稿では,探索半径をより注意深く制御するために,静止検出に付加できる半径メモリと呼ばれる新しい機構について検討する。
このアイデアはSD-RLS$textm$と呼ばれるアルゴリズムで実装され、それまでのステージング検出の変種と比較して高速化された。
論文 参考訳（メタデータ） (2021-04-09T14:33:52Z) - Trees, Forests, Chickens, and Eggs: When and Why to Prune Trees in a
Random Forest [8.513154770491898]
木深度はプロセス全体にわたって自然な正規化の形式と見なされるべきである。
特に,データの信号対雑音比が低ければ,樹木が浅いランダムな森林が有利であることが示唆された。
論文 参考訳（メタデータ） (2021-03-30T21:57:55Z) - Uncovering Feature Interdependencies in High-Noise Environments with
Stepwise Lookahead Decision Forests [0.0]
ランダムフォレストアルゴリズムの「Stepwise lookahead」変異は、二項特徴相互依存性をよりよく発見する能力を示す。
銅先物取引の長期的戦略は、毎日の物価リターンの兆候を予測するために、欲望と無作為な森林の両方を訓練することで実証される。
論文 参考訳（メタデータ） (2020-09-30T11:31:10Z) - Efficient Computation of Expectations under Spanning Tree Distributions [67.71280539312536]
本稿では,エッジファクター,非プロジェクティブ・スパンニングツリーモデルにおいて,一階期待と二階期待の重要なケースに対する統一アルゴリズムを提案する。
我々のアルゴリズムは勾配と期待の基本的な関係を利用しており、効率的なアルゴリズムを導出することができる。
論文 参考訳（メタデータ） (2020-08-29T14:58:26Z) - Best-First Beam Search [78.71330480725668]
本研究では,ビームサーチの標準実装を10倍高速に実現可能であることを示す。
ダウンストリーム性能の面でも同様に有益な探索バイアスを有するBest-First Beam Searchのメモリ再生版を提案する。
論文 参考訳（メタデータ） (2020-07-08T05:56:01Z) - Optimal Lottery Tickets via SubsetSum: Logarithmic Over-Parameterization
is Sufficient [9.309655246559094]
幅$d$と深さ$l$の任意のターゲットネットワークは、幅$O(log(dl))$の2倍、幅$O(log(dl))$のランダムネットワークを切断することで近似できることを示す。
解析は、プルーニングランダムなReLUネットワークをtextscSubset問題のランダムなインスタンスに接続することに依存する。
論文 参考訳（メタデータ） (2020-06-14T19:32:10Z) - Learning to Accelerate Heuristic Searching for Large-Scale Maximum
Weighted b-Matching Problems in Online Advertising [51.97494906131859]
バイパルタイトbマッチングはアルゴリズム設計の基本であり、経済市場や労働市場などに広く適用されている。
既存の正確で近似的なアルゴリズムは、通常そのような設定で失敗する。
我々は、以前の事例から学んだ知識を活用して、新しい問題インスタンスを解決するtextttNeuSearcherを提案する。
論文 参考訳（メタデータ） (2020-05-09T02:48:23Z) - Parameterizing Branch-and-Bound Search Trees to Learn Branching Policies [76.83991682238666]
Branch and Bound (B&B) は、Mixed-Integer Linear Programming Problem (MILP) の解法として一般的に用いられる木探索法である。
本稿では,新しい模倣学習フレームワークを提案し,分岐を表現するための新しい入力機能とアーキテクチャを提案する。
論文 参考訳（メタデータ） (2020-02-12T17:43:23Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。