論文の概要: Levin Tree Search with Context Models

• arxiv url: http://arxiv.org/abs/2305.16945v3
• Date: Tue, 12 Nov 2024 16:23:50 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-11-13 13:18:26.719356
• Title: Levin Tree Search with Context Models
• Title（参考訳）: 文脈モデルを用いた木探索
• Authors: Laurent Orseau, Marcus Hutter, Levi H. S. Lelis,
• Abstract要約: Levin Tree Search (LTS)は、ポリシー(アクション上の確率分布)を利用する検索アルゴリズムである。 ニューラルネットワークは、オンライン圧縮文献(LTS+CM)から派生したパラメータ化コンテキストモデルに代用可能であることを示す。 LTS+CMがルービックキューブを数百の展開で解く政策を学習できることを示す。
• 参考スコア（独自算出の注目度）: 28.0272050696211
• License:
• Abstract: Levin Tree Search (LTS) is a search algorithm that makes use of a policy (a probability distribution over actions) and comes with a theoretical guarantee on the number of expansions before reaching a goal node, depending on the quality of the policy. This guarantee can be used as a loss function, which we call the LTS loss, to optimize neural networks representing the policy (LTS+NN). In this work we show that the neural network can be substituted with parameterized context models originating from the online compression literature (LTS+CM). We show that the LTS loss is convex under this new model, which allows for using standard convex optimization tools, and obtain convergence guarantees to the optimal parameters in an online setting for a given set of solution trajectories -- guarantees that cannot be provided for neural networks. The new LTS+CM algorithm compares favorably against LTS+NN on several benchmarks: Sokoban (Boxoban), The Witness, and the 24-Sliding Tile puzzle (STP). The difference is particularly large on STP, where LTS+NN fails to solve most of the test instances while LTS+CM solves each test instance in a fraction of a second. Furthermore, we show that LTS+CM is able to learn a policy that solves the Rubik's cube in only a few hundred expansions, which considerably improves upon previous machine learning techniques.
• Abstract（参考訳）: Levin Tree Search (LTS) は、ポリシー(アクション上の確率分布)を利用する検索アルゴリズムであり、ポリシーの質に応じてゴールノードに到達する前に展開の回数を理論的に保証する。 この保証は、LTS損失と呼ばれる損失関数として使用することができ、ポリシー(LTS+NN)を表すニューラルネットワークを最適化する。 本研究では,ニューラルネットワークをオンライン圧縮文献(LTS+CM)から派生したパラメータ化コンテキストモデルに代用できることを示す。 この新モデルでは、LTS損失は凸であり、標準的な凸最適化ツールを使用でき、与えられたソリューショントラジェクトリのオンライン設定における最適パラメータへの収束保証が得られる。 新しいLTS+CMアルゴリズムは、ソコバン(Boxoban)、The Witness、24-Sliding Tile puzzle(STP)といったいくつかのベンチマークでLTS+NNと好意的に比較する。 LTS+NNはテストインスタンスのほとんどを解決できず、LTS+CMは各テストインスタンスを1秒で解決する。 さらに、LTS+CMは、これまでの機械学習技術で大幅に改善された、数百の展開でルービックキューブを解くポリシーを学習できることを示す。

関連論文リスト

• LinSATNet: The Positive Linear Satisfiability Neural Networks [116.65291739666303]
  本稿では,ニューラルネットワークに人気の高い正の線形満足度を導入する方法について検討する。 本稿では,古典的なシンクホーンアルゴリズムを拡張し,複数の辺分布の集合を共同で符号化する,最初の微分可能満足層を提案する。
  論文  参考訳（メタデータ） (2024-07-18T22:05:21Z)
• Sparsity-Constraint Optimization via Splicing Iteration [1.3622424109977902]
  我々は sPlicing itEration (SCOPE) を用いたスペーサリティ制約最適化アルゴリズムを開発した。 SCOPEはパラメータをチューニングせずに効率的に収束する。 SCOPEを用いて2次最適化を解き、スパース分類器を学習し、バイナリ変数のスパースマルコフネットワークを復元する。 C++実装に基づいたオープンソースのPythonパッケージskscopeがGitHubで公開されている。
  論文  参考訳（メタデータ） (2024-06-17T18:34:51Z)
• Differentially Private Non-convex Learning for Multi-layer Neural Networks [35.24835396398768]
  本稿では,単一出力ノードを持つ(多層)完全連結ニューラルネットワークに対する差分的タンジェント最適化の問題に焦点をあてる。 ニューラルカーネル理論の最近の進歩を利用して、サンプルサイズとネットワーク幅の両方が十分に大きい場合に、最初の過剰人口リスクを提供する。
  論文  参考訳（メタデータ） (2023-10-12T15:48:14Z)
• Probabilistic Modeling: Proving the Lottery Ticket Hypothesis in Spiking Neural Network [30.924449325020767]
  Lottery Ticket hypothesis (LTH) は、ランダムにdの大きいニューラルネットワークは小さなサブネットワークを含んでいると述べている。 LTHはプルーニングネットワークのための新しいパスを開く。
  論文  参考訳（メタデータ） (2023-05-20T09:27:34Z)
• On Model Compression for Neural Networks: Framework, Algorithm, and Convergence Guarantee [21.818773423324235]
  本稿では,低ランク近似と重み近似の2つのモデル圧縮手法に焦点を当てた。 本稿では,非最適化の新たな視点から,モデル圧縮のための全体論的なフレームワークを提案する。
  論文  参考訳（メタデータ） (2023-03-13T02:14:42Z)
• A Unified Algebraic Perspective on Lipschitz Neural Networks [88.14073994459586]
  本稿では,様々なタイプの1-Lipschitzニューラルネットワークを統一する新しい視点を提案する。 そこで本研究では,SDP(Common semidefinite Programming)条件の解析解を求めることによって,既存の多くの手法を導出し,一般化することができることを示す。 SDPベースのLipschitz Layers (SLL) と呼ばれる我々のアプローチは、非自明で効率的な凸ポテンシャル層の一般化を設計できる。
  論文  参考訳（メタデータ） (2023-03-06T14:31:09Z)
• Learning To Dive In Branch And Bound [95.13209326119153]
  グラフニューラルネットワークを用いて特定の潜水構造を学習するためのL2Diveを提案する。 我々は、変数の割り当てを予測するために生成モデルを訓練し、線形プログラムの双対性を利用して潜水決定を行う。
  論文  参考訳（メタデータ） (2023-01-24T12:01:45Z)
• Sample-Then-Optimize Batch Neural Thompson Sampling [50.800944138278474]
  我々はトンプソンサンプリング(TS)ポリシーに基づくブラックボックス最適化のための2つのアルゴリズムを提案する。 入力クエリを選択するには、NNをトレーニングし、トレーニングされたNNを最大化してクエリを選択するだけです。 我々のアルゴリズムは、大きなパラメータ行列を逆転する必要性を助長するが、TSポリシーの妥当性は保たれている。
  論文  参考訳（メタデータ） (2022-10-13T09:01:58Z)
• Algorithms for Efficiently Learning Low-Rank Neural Networks [12.916132936159713]
  低ランクニューラルネットワークの学習アルゴリズムについて検討する。 単層ReLUネットワークに最適な低ランク近似を学習するアルゴリズムを提案する。 低ランク$textitdeep$ネットワークをトレーニングするための新しい低ランクフレームワークを提案する。
  論文  参考訳（メタデータ） (2022-02-02T01:08:29Z)
• Communication-Efficient Distributed Stochastic AUC Maximization with Deep Neural Networks [50.42141893913188]
  本稿では,ニューラルネットワークを用いた大規模AUCのための分散変数について検討する。 我々のモデルは通信ラウンドをはるかに少なくし、理論上はまだ多くの通信ラウンドを必要としています。 いくつかのデータセットに対する実験は、我々の理論の有効性を示し、我々の理論を裏付けるものである。
  論文  参考訳（メタデータ） (2020-05-05T18:08:23Z)

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

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