論文の概要: TreeDQN: Learning to minimize Branch-and-Bound tree

• arxiv url: http://arxiv.org/abs/2306.05905v1
• Date: Fri, 9 Jun 2023 14:01:26 GMT
• ステータス: 処理完了
• システム内更新日: 2023-06-12 13:10:08.434854
• Title: TreeDQN: Learning to minimize Branch-and-Bound tree
• Title（参考訳）: TreeDQN: 分岐境界木を最小化する学習
• Authors: Dmitry Sorokin, Alexander Kostin
• Abstract要約: Branch-and-Boundは、Mixed Linear Programsという形で最適化タスクを解決するための便利なアプローチである。 解法の効率は、分割する変数を選択するのに使用される分岐に依存する。 分岐を効率的に学習できる強化学習法を提案する。
• 参考スコア（独自算出の注目度）: 78.52895577861327
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Combinatorial optimization problems require an exhaustive search to find the optimal solution. A convenient approach to solving combinatorial optimization tasks in the form of Mixed Integer Linear Programs is Branch-and-Bound. Branch-and-Bound solver splits a task into two parts dividing the domain of an integer variable, then it solves them recursively, producing a tree of nested sub-tasks. The efficiency of the solver depends on the branchning heuristic used to select a variable for splitting. In the present work, we propose a reinforcement learning method that can efficiently learn the branching heuristic. We view the variable selection task as a tree Markov Decision Process, prove that the Bellman operator adapted for the tree Markov Decision Process is contracting in mean, and propose a modified learning objective for the reinforcement learning agent. Our agent requires less training data and produces smaller trees compared to previous reinforcement learning methods.
• Abstract（参考訳）: 組合せ最適化問題は最適解を見つけるために徹底的な探索を必要とする。 組合せ最適化タスクを混合整数線形プログラムの形で解くための便利なアプローチは分岐と境界である。 Branch-and-Boundソルバは、タスクを整数変数のドメインを分割する2つの部分に分割し、再帰的に解決し、ネストしたサブタスクのツリーを生成する。 解法の効率は、分割する変数を選択するのに使用される分岐ヒューリスティックに依存する。 本研究では,分岐ヒューリスティックを効率的に学習できる強化学習手法を提案する。 可変選択タスクを木マルコフ決定プロセスとして捉え,木マルコフ決定プロセスに適応したベルマン演算子が平均的に収縮していることを証明するとともに,強化学習エージェントに対する修正学習目標を提案する。 エージェントは,前回の強化学習法に比べて,トレーニングデータが少なく,より小さな木を生成できる。

関連論文リスト

• Terminating Differentiable Tree Experts [77.2443883991608]
  本稿では,変圧器と表現生成器の組み合わせを用いて木操作を学習するニューラルシンボリック微分木機械を提案する。 まず、専門家の混在を導入することで、各ステップで使用される一連の異なるトランスフォーマーレイヤを取り除きます。 また,モデルが自動生成するステップ数を選択するための新しい終端アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-07-02T08:45:38Z)
• Learning accurate and interpretable decision trees [27.203303726977616]
  我々は、同じドメインから繰り返しデータにアクセスして決定木学習アルゴリズムを設計するためのアプローチを開発する。 本研究では,ベイズ決定木学習における事前パラメータのチューニングの複雑さについて検討し,その結果を決定木回帰に拡張する。 また、学習した決定木の解釈可能性について検討し、決定木を用いた説明可能性と精度のトレードオフを最適化するためのデータ駆動型アプローチを提案する。
  論文  参考訳（メタデータ） (2024-05-24T20:10:10Z)
• Tree Prompting: Efficient Task Adaptation without Fine-Tuning [112.71020326388029]
  Tree Promptingはプロンプトの決定ツリーを構築し、複数のLMコールをリンクしてタスクを解決する。 分類データセットの実験により、Tree Promptingは競合するメソッドよりも精度が向上し、微調整と競合することが示された。
  論文  参考訳（メタデータ） (2023-10-21T15:18:22Z)
• Interpretable Decision Tree Search as a Markov Decision Process [8.530182510074983]
  教師付き学習タスクに最適な決定木を見つけることは、大規模に解決する上で難しい問題である。 近年、マルコフ決定問題 (MDP) としてこの問題の枠組みを定め、深層強化学習を用いてスケーリングに取り組むことが提案されている。 そこで我々は,全ての状態に対して生成する情報理論テスト生成関数を用いて,MDPの分解能を拡大する手法を提案する。
  論文  参考訳（メタデータ） (2023-09-22T08:18:08Z)
• Mixture of Decision Trees for Interpretable Machine Learning [4.180840853105103]
  この研究は、Mixture of Decision Trees (MoDT)と呼ばれる新しい解釈可能な機械学習手法を導入する。 MoDTは、それぞれの決定を理解可能で、人間に追跡可能とすることで、解釈可能性を維持しながらパフォーマンスを向上させる方法とみなすことができる。
  論文  参考訳（メタデータ） (2022-11-26T17:09:51Z)
• Quant-BnB: A Scalable Branch-and-Bound Method for Optimal Decision Trees with Continuous Features [5.663538370244174]
  本稿では,分岐とバウンド(BnB)に基づく新たな離散最適化手法を提案する。 提案アルゴリズムのQuant-BnBは,様々な実データセット上での浅い最適木に対する既存手法と比較して,大幅な高速化を示す。
  論文  参考訳（メタデータ） (2022-06-23T17:19:29Z)
• Reinforcement Learning for Branch-and-Bound Optimisation using Retrospective Trajectories [72.15369769265398]
  機械学習は分岐のための有望なパラダイムとして登場した。 分岐のための単純かつ効果的なRLアプローチであるレトロ分岐を提案する。 我々は現在最先端のRL分岐アルゴリズムを3～5倍に上回り、500の制約と1000の変数を持つMILP上での最高のILメソッドの性能の20%以内である。
  論文  参考訳（メタデータ） (2022-05-28T06:08:07Z)
• Learning Pseudo-Backdoors for Mixed Integer Programs [48.36587539004464]
  そこで我々は,Mixed Programs (MIP) の解法として,擬似バックドア(擬似バックドア)と呼ばれる一連の決定変数の優先順位付けを学習し,解時間を短縮する機械学習手法を提案する。 我々のアプローチは、これらの変数の分岐のみが最適積分解と最適性の証明となるような、小さな変数の集合に対応する強いバックドアの概念から着想を得ている。 強力なバックドアに対する擬似バックドアの重要な利点は、データ駆動の識別や予測に非常に適している点である。
  論文  参考訳（メタデータ） (2021-06-09T13:59:53Z)
• Learning Binary Decision Trees by Argmin Differentiation [34.9154848754842]
  ダウンストリームタスクのためにデータを分割するバイナリ決定木を学びます。 離散パラメータの混合整数プログラムを緩和する。 我々は、前方と後方のパスを効率的に計算するアルゴリズムを考案した。
  論文  参考訳（メタデータ） (2020-10-09T15:11:28Z)
• Generalized and Scalable Optimal Sparse Decision Trees [56.35541305670828]
  様々な目的に対して最適な決定木を生成する手法を提案する。 また,連続変数が存在する場合に最適な結果が得られるスケーラブルなアルゴリズムも導入する。
  論文  参考訳（メタデータ） (2020-06-15T19:00:11Z)

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

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