論文の概要: Learning selection strategies in Buchberger's algorithm
- arxiv url: http://arxiv.org/abs/2005.01917v3
- Date: Mon, 17 Aug 2020 22:01:54 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-06 13:59:24.474627
- Title: Learning selection strategies in Buchberger's algorithm
- Title(参考訳): Buchbergerアルゴリズムにおける学習選択戦略
- Authors: Dylan Peifer, Michael Stillman, Daniel Halpern-Leistner
- Abstract要約: 我々は、強化学習エージェントを用いてSペア選択を行うBuchbergerのアルゴリズムに新しいアプローチを導入する。
次に、問題の難易度がSペアの領域選択と分布に依存するかを研究する。
我々はポリシー最適化(PPO)を用いてポリシーモデルを訓練し、近似二項方程式のランダムシステムに対するSペア選択戦略を学習する。
- 参考スコア(独自算出の注目度): 3.4376560669160394
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Studying the set of exact solutions of a system of polynomial equations
largely depends on a single iterative algorithm, known as Buchberger's
algorithm. Optimized versions of this algorithm are crucial for many computer
algebra systems (e.g., Mathematica, Maple, Sage). We introduce a new approach
to Buchberger's algorithm that uses reinforcement learning agents to perform
S-pair selection, a key step in the algorithm. We then study how the difficulty
of the problem depends on the choices of domain and distribution of
polynomials, about which little is known. Finally, we train a policy model
using proximal policy optimization (PPO) to learn S-pair selection strategies
for random systems of binomial equations. In certain domains, the trained model
outperforms state-of-the-art selection heuristics in total number of polynomial
additions performed, which provides a proof-of-concept that recent developments
in machine learning have the potential to improve performance of algorithms in
symbolic computation.
- Abstract(参考訳): 多項式方程式の系の厳密解の集合の研究は、ブッチベルガーのアルゴリズムとして知られる1つの反復アルゴリズムに大きく依存する。
このアルゴリズムの最適化版は、多くの計算機代数学システム(例えば、mathematica, maple, sage)にとって重要である。
本稿では,強化学習エージェントを用いてSペア選択を行うBuchbergerのアルゴリズムに新たなアプローチを導入する。
次に、問題の難易度は、ほとんど知られていない多項式の領域の選択と分布に依存するかを研究する。
最後に、近似ポリシ最適化(PPO)を用いてポリシーモデルをトレーニングし、二項方程式のランダムシステムに対するSペア選択戦略を学習する。
特定の領域において、トレーニングされたモデルは、実行された多項式加算の総数において最先端の選択ヒューリスティックよりも優れており、近年の機械学習の発展は、シンボリック計算におけるアルゴリズムの性能を向上させる可能性があるという概念実証を提供する。
関連論文リスト
- Accelerating Cutting-Plane Algorithms via Reinforcement Learning
Surrogates [49.84541884653309]
凸離散最適化問題に対する現在の標準的なアプローチは、カットプレーンアルゴリズムを使うことである。
多くの汎用カット生成アルゴリズムが存在するにもかかわらず、大規模な離散最適化問題は、難易度に悩まされ続けている。
そこで本研究では,強化学習による切削平面アルゴリズムの高速化手法を提案する。
論文 参考訳(メタデータ) (2023-07-17T20:11:56Z) - Learning the Markov Decision Process in the Sparse Gaussian Elimination [0.0]
スパースガウス除去のための学習に基づくアプローチを提案する。
スパースソルバの主モジュールに対するQ-Learningアルゴリズムを提案する。
論文 参考訳(メタデータ) (2021-09-30T08:56:39Z) - Algorithm Selection on a Meta Level [58.720142291102135]
本稿では,与えられたアルゴリズムセレクタの組み合わせに最適な方法を求めるメタアルゴリズム選択の問題を紹介する。
本稿では,メタアルゴリズム選択のための一般的な方法論フレームワークと,このフレームワークのインスタンス化として具体的な学習手法を提案する。
論文 参考訳(メタデータ) (2021-07-20T11:23:21Z) - Learning a performance metric of Buchberger's algorithm [2.1485350418225244]
Buchbergerのアルゴリズムが実行されている間に発生する加算の数を、開始入力だけで予測しようと試みる。
我々の研究は概念実証として機能し、Buchbergerのアルゴリズムの加算数を予測することは機械学習の観点からの問題であることを示した。
論文 参考訳(メタデータ) (2021-06-07T14:57:57Z) - Polygonal Unadjusted Langevin Algorithms: Creating stable and efficient
adaptive algorithms for neural networks [0.0]
本稿では,Langevinベースのアルゴリズムを新たに導入し,一般的な適応的消滅アルゴリズムの欠点の多くを克服する。
特に、この新しいクラスのアルゴリズムの収束性についての漸近解析と完全な理論的保証を提供し、TH$varepsilon$O POULA(あるいは単にTheoPouLa)と名付けた。
論文 参考訳(メタデータ) (2021-05-28T15:58:48Z) - Safe Learning and Optimization Techniques: Towards a Survey of the State
of the Art [3.6954802719347413]
安全な学習と最適化は、できるだけ安全でない入力ポイントの評価を避ける学習と最適化の問題に対処します。
安全強化学習アルゴリズムに関する包括的な調査は2015年に発表されたが、アクティブラーニングと最適化に関する関連研究は考慮されなかった。
本稿では,強化学習,ガウス過程の回帰と分類,進化的アルゴリズム,アクティブラーニングなど,様々な分野のアルゴリズムについて概説する。
論文 参考訳(メタデータ) (2021-01-23T13:58:09Z) - Evolving Reinforcement Learning Algorithms [186.62294652057062]
メタラーニング強化学習アルゴリズムの手法を提案する。
学習アルゴリズムはドメインに依存しないため、トレーニング中に見えない新しい環境に一般化することができる。
従来の制御タスク、gridworld型タスク、atariゲームよりも優れた一般化性能を得る2つの学習アルゴリズムに注目した。
論文 参考訳(メタデータ) (2021-01-08T18:55:07Z) - Model-free optimal control of discrete-time systems with additive and
multiplicative noises [1.656520517245166]
本稿では,加法的および乗法的雑音を受ける離散時間系のクラスに対する最適制御問題について検討する。
システム状態と入力のデータを用いて最適許容制御ポリシーを学習するために,モデルフリー強化学習アルゴリズムを提案する。
学習アルゴリズムは最適許容制御ポリシーに収束することが証明された。
論文 参考訳(メタデータ) (2020-08-20T02:18:00Z) - Model Selection in Contextual Stochastic Bandit Problems [51.94632035240787]
基本アルゴリズムを選択できるメタアルゴリズムを開発した。
基本アルゴリズムの1つが$O(sqrtT)$後悔している場合でも、一般的には$Omega(sqrtT)$後悔よりも良いものを得ることはできません。
論文 参考訳(メタデータ) (2020-03-03T18:46:34Z) - Optimal Randomized First-Order Methods for Least-Squares Problems [56.05635751529922]
このアルゴリズムのクラスは、最小二乗問題に対する最も高速な解法のうち、いくつかのランダム化手法を含んでいる。
我々は2つの古典的埋め込み、すなわちガウス射影とアダマール変換のサブサンプリングに焦点を当てる。
得られたアルゴリズムは条件数に依存しない最小二乗問題の解法として最も複雑である。
論文 参考訳(メタデータ) (2020-02-21T17:45:32Z) - Extreme Algorithm Selection With Dyadic Feature Representation [78.13985819417974]
我々は,数千の候補アルゴリズムの固定セットを考慮に入れた,極端なアルゴリズム選択(XAS)の設定を提案する。
我々は、XAS設定に対する最先端のAS技術の適用性を評価し、Dyadic特徴表現を利用したアプローチを提案する。
論文 参考訳(メタデータ) (2020-01-29T09:40:58Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。