論文の概要: A Cover Time Study of a non-Markovian Algorithm
- arxiv url: http://arxiv.org/abs/2306.04902v2
- Date: Fri, 11 Aug 2023 05:27:05 GMT
- ステータス: 処理完了
- システム内更新日: 2023-08-14 16:41:13.257101
- Title: A Cover Time Study of a non-Markovian Algorithm
- Title（参考訳）: 非マルコフアルゴリズムのカバータイム研究
- Authors: Guanhua Fang, Gennady Samorodnitsky, Zhiqiang Xu
- Abstract要約: 提案手法は,無作為なランダムウォークサーチよりも負のフィードバック戦略(カウントベース探索法)が優れていることを示す。
また、クリッドグラフやツリーグラフなど、特別なが重要なグラフのカバータイムも小さくする。
- 参考スコア（独自算出の注目度）: 18.23492383352517
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: Given a traversal algorithm, cover time is the expected number of steps
needed to visit all nodes in a given graph. A smaller cover time means a higher
exploration efficiency of traversal algorithm. Although random walk algorithms
have been studied extensively in the existing literature, there has been no
cover time result for any non-Markovian method. In this work, we stand on a
theoretical perspective and show that the negative feedback strategy (a
count-based exploration method) is better than the naive random walk search. In
particular, the former strategy can locally improve the search efficiency for
an arbitrary graph. It also achieves smaller cover times for special but
important graphs, including clique graphs, tree graphs, etc. Moreover, we make
connections between our results and reinforcement learning literature to give
new insights on why classical UCB and MCTS algorithms are so useful. Various
numerical results corroborate our theoretical findings.
- Abstract（参考訳）: トラバーサルアルゴリズムが与えられた場合、カバータイムは、与えられたグラフの全ノードを訪問するために必要なステップ数である。
カバータイムが小さくなると、トラバースアルゴリズムの探索効率が向上する。
ランダムウォークアルゴリズムは既存の文献で広く研究されているが、非マルコフ法ではカバータイムは得られていない。
本研究では,理論的な視点から,負のフィードバック戦略(数に基づく探索法)がナイーブなランダムウォーク探索より優れていることを示す。
特に、前者の戦略は任意のグラフの探索効率を局所的に改善することができる。
また、クライクグラフやツリーグラフなど、特別なが重要なグラフのカバータイムも短縮する。
さらに,従来の UCB アルゴリズムと MCTS アルゴリズムがなぜ有用かという新たな知見を提供するため,本研究の結果と強化学習文献の関連付けを行う。
様々な数値結果が理論的知見を裏付ける。
関連論文リスト
- SLOPE: Search with Learned Optimal Pruning-based Expansion [2.0618817976970103]
SLOPE(Learned Optimal Pruning-based Expansion)を用いた探索手法を提案する。
ノードの距離を最適経路から学習し、その結果、オープンリストのサイズを小さくする。
これにより、探索は最適な経路に近い領域のみを探索し、メモリと計算コストを削減できる。
論文 参考訳（メタデータ） (2024-06-07T13:42:15Z) - Learning-Based Algorithms for Graph Searching Problems [6.923787372512553]
本稿では,Banerjeeらによって最近導入された予測付きグラフ探索の問題点について考察する。
この問題では、ある$r$から始まるエージェントは、隠れたゴールノード$g$を見つけるために、(潜在的に未知の)グラフ$G$をトラバースしなければならない。
我々は未知のグラフ上でこの探索タスクのアルゴリズムを設計する。
論文 参考訳（メタデータ） (2024-02-27T18:12:58Z) - A Theoretical Analysis Of Nearest Neighbor Search On Approximate Near
Neighbor Graph [51.880164098926166]
グラフベースのアルゴリズムは、近隣探索(NN-Search)問題において最先端の性能を示す。
グラフベースのNN-Searchアルゴリズムには実践と理論のギャップがある。
低次元および高密度ベクトルに対する ANN-Graph 上の欲求探索による NN-Search の解法を理論的に保証する。
論文 参考訳（メタデータ） (2023-03-10T21:18:34Z) - Causal Bandits without Graph Learning [28.021500949026766]
我々は,原子間干渉を用いた報酬ノードの親ノード探索のための効率的なアルゴリズムを開発した。
報奨ノードが複数の親を持つ場合にアルゴリズムを拡張します。
論文 参考訳（メタデータ） (2023-01-26T20:27:14Z) - Learning Graph Search Heuristics [48.83557172525969]
本稿では,新しいニューラルネットワークと学習アルゴリズムであるPHIL(Path Heuristic with Imitation Learning)について述べる。
我々の関数は、ノード距離の推測に有用なグラフ埋め込みを学習し、グラフサイズに依存しない一定時間で実行し、テスト時にA*のようなアルゴリズムに容易に組み込むことができる。
実験の結果、PHILはベンチマークデータセットの最先端の手法と比較して平均58.5%の探索ノード数を削減している。
論文 参考訳（メタデータ） (2022-12-07T22:28:00Z) - Learning heuristics for A* [9.701208207491879]
我々は,近年のニューラル推論の進歩と,グラフ上の経路探索問題に対する効率的な関数の学習を組み合わせる。
我々はマルチタスク学習を利用してDijkstraのアルゴリズムとA*探索アルゴリズムの一貫性のある関数を学習する。
その結果、学習した値上でA*を実行すると、Dijkstraと比較してターゲットノード探索が大幅に高速化されることがわかった。
論文 参考訳（メタデータ） (2022-04-11T10:13:53Z) - Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。
問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。
本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-01-07T08:00:02Z) - Efficient Computation of Expectations under Spanning Tree Distributions [67.71280539312536]
本稿では,エッジファクター,非プロジェクティブ・スパンニングツリーモデルにおいて,一階期待と二階期待の重要なケースに対する統一アルゴリズムを提案する。
我々のアルゴリズムは勾配と期待の基本的な関係を利用しており、効率的なアルゴリズムを導出することができる。
論文 参考訳（メタデータ） (2020-08-29T14:58:26Z) - Online Dense Subgraph Discovery via Blurred-Graph Feedback [87.9850024070244]
我々は高密度サブグラフ発見のための新しい学習問題を導入する。
まず,確率の高いほぼ最適解を求めるエッジ時間アルゴリズムを提案する。
そして、理論的保証のあるよりスケーラブルなアルゴリズムを設計する。
論文 参考訳（メタデータ） (2020-06-24T11:37:33Z) - Adversarial Online Learning with Changing Action Sets: Efficient
Algorithms with Approximate Regret Bounds [48.312484940846]
睡眠の専門家やバンドイットによるオンライン学習の問題を再考する。
各タイムステップにおいて、アルゴリズムが選択できるアクションのサブセットのみが利用可能である。
我々は、一般的な睡眠専門家/バンド問題に対して、アポキシマ-レグレット保証を提供するアルゴリズムを提供する。
論文 参考訳（メタデータ） (2020-03-07T02:13:21Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。