論文の概要: Learning a performance metric of Buchberger's algorithm

• arxiv url: http://arxiv.org/abs/2106.03676v1
• Date: Mon, 7 Jun 2021 14:57:57 GMT
• ステータス: 処理完了
• システム内更新日: 2021-06-08 18:18:08.945700
• Title: Learning a performance metric of Buchberger's algorithm
• Title（参考訳）: buchbergerアルゴリズムの性能指標の学習
• Authors: Jelena Mojsilovi\'c, Dylan Peifer, Sonja Petrovi\'c
• Abstract要約: Buchbergerのアルゴリズムが実行されている間に発生する加算の数を、開始入力だけで予測しようと試みる。 我々の研究は概念実証として機能し、Buchbergerのアルゴリズムの加算数を予測することは機械学習の観点からの問題であることを示した。
• 参考スコア（独自算出の注目度）: 2.1485350418225244
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: What can be (machine) learned about the complexity of Buchberger's algorithm? Given a system of polynomials, Buchberger's algorithm computes a Gr\"obner basis of the ideal these polynomials generate using an iterative procedure based on multivariate long division. The runtime of each step of the algorithm is typically dominated by a series of polynomial additions, and the total number of these additions is a hardware independent performance metric that is often used to evaluate and optimize various implementation choices. In this work we attempt to predict, using just the starting input, the number of polynomial additions that take place during one run of Buchberger's algorithm. Good predictions are useful for quickly estimating difficulty and understanding what features make Gr\"obner basis computation hard. Our features and methods could also be used for value models in the reinforcement learning approach to optimize Buchberger's algorithm introduced in [Peifer, Stillman, and Halpern-Leistner, 2020]. We show that a multiple linear regression model built from a set of easy-to-compute ideal generator statistics can predict the number of polynomial additions somewhat well, better than an uninformed model, and better than regression models built on some intuitive commutative algebra invariants that are more difficult to compute. We also train a simple recursive neural network that outperforms these linear models. Our work serves as a proof of concept, demonstrating that predicting the number of polynomial additions in Buchberger's algorithm is a feasible problem from the point of view of machine learning.
• Abstract（参考訳）: buchbergerのアルゴリズムの複雑さについて(機械)何を学べますか? 多項式の系が与えられたとき、Buchbergerのアルゴリズムは、多変量長分割に基づく反復的手順を用いてこれらの多項式が生成する理想のGr\"オブナー基底を計算する。 アルゴリズムの各ステップの実行は、典型的には一連の多項式加算によって支配され、これらの加算の総数は、様々な実装の選択を評価し最適化するためにしばしば使用されるハードウェアに依存しないパフォーマンス指標である。 本研究では,buchbergerアルゴリズムの1回の実行中に発生する多項式加算数を,開始入力のみを用いて予測する。 優れた予測は、難易度を素早く推定し、どの機能がgr\"obner基底計算を困難にするかを理解するのに役立つ。 当社の機能と手法は,[peifer, stillman, halpern-leistner, 2020]で導入されたbuchbergerのアルゴリズムを最適化するための強化学習アプローチにおけるバリューモデルにも利用できる。 計算が容易なイデアル生成統計量から構築した多重線形回帰モデルは、多項式付加数を、非形式モデルよりも幾分良く予測でき、計算が難しい直観的可換代数不変量に基づいて構築された回帰モデルよりも良いことを示す。 また、これらの線形モデルを上回る単純な再帰的ニューラルネットワークを訓練する。 我々の研究は概念実証として機能し、Buchbergerのアルゴリズムの多項式加算数を予測することは機械学習の観点から可能な問題であることを示した。

関連論文リスト

• A Simple Solution for Homomorphic Evaluation on Large Intervals [0.0]
  ホモモルフィック暗号化(HE)は、プライバシー保護計算に使用される有望な手法である。 非ポリノミカル関数の近似の同型評価は、プライバシ保存機械学習において重要な役割を果たす。 我々は,任意の関数を近似する簡単な解を導入する。
  論文  参考訳（メタデータ） (2024-05-24T04:13:22Z)
• An Efficient Algorithm for Clustered Multi-Task Compressive Sensing [60.70532293880842]
  クラスタ化マルチタスク圧縮センシングは、複数の圧縮センシングタスクを解決する階層モデルである。 このモデルに対する既存の推論アルゴリズムは計算コストが高く、高次元ではうまくスケールしない。 本稿では,これらの共分散行列を明示的に計算する必要をなくし,モデル推論を大幅に高速化するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-09-30T15:57:14Z)
• Exploring and Learning in Sparse Linear MDPs without Computationally Intractable Oracles [39.10180309328293]
  本稿では,特徴選択の観点から線形MDPを再考する。 我々の主な成果は、この問題に対する最初のアルゴリズムである。 コンベックスプログラミングによって効率よく計算できることを示す。
  論文  参考訳（メタデータ） (2023-09-18T03:35:48Z)
• Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials [50.90125395570797]
  正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。 本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
  論文  参考訳（メタデータ） (2023-07-24T14:37:22Z)
• Exponential Hardness of Reinforcement Learning with Linear Function Approximation [20.066210529358177]
  指数時間仮説に基づく線形強化学習において,特徴・地平線で指数関数的な計算下界を示す。 また、地平線依存に最適化された下界が$exp(sqrtH)$の最もよく知られた上界とほぼ一致することを示す。
  論文  参考訳（メタデータ） (2023-02-25T00:19:49Z)
• What learning algorithm is in-context learning? Investigations with linear models [87.91612418166464]
  本稿では,トランスフォーマーに基づくインコンテキスト学習者が標準学習アルゴリズムを暗黙的に実装する仮説について検討する。 訓練された文脈内学習者は、勾配降下、隆起回帰、および正確な最小二乗回帰によって計算された予測値と密に一致していることを示す。 文脈内学習者がこれらの予測器とアルゴリズム的特徴を共有するという予備的証拠。
  論文  参考訳（メタデータ） (2022-11-28T18:59:51Z)
• Structure learning in polynomial time: Greedy algorithms, Bregman information, and exponential families [12.936601424755944]
  DAGを学習するための一般的なグリーディスコアに基づくアルゴリズムについて検討する。 DAGモデルを学習するための最近のアルゴリズム時間アルゴリズムが,このアルゴリズムの特別な例であることを示す。 この観測は、ブレグマン発散と指数族との双対性に基づく新しいスコア関数と最適条件を示唆する。
  論文  参考訳（メタデータ） (2021-10-10T06:37:51Z)
• Quantum-Inspired Algorithms from Randomized Numerical Linear Algebra [53.46106569419296]
  我々は、リコメンダシステムと最小二乗回帰のためのクエリをサポートする古典的な(量子でない)動的データ構造を作成する。 これらの問題に対する以前の量子インスパイアされたアルゴリズムは、レバレッジやリッジレベレッジスコアを偽装してサンプリングしていると我々は主張する。
  論文  参考訳（メタデータ） (2020-11-09T01:13:07Z)
• Learning selection strategies in Buchberger's algorithm [3.4376560669160394]
  我々は、強化学習エージェントを用いてSペア選択を行うBuchbergerのアルゴリズムに新しいアプローチを導入する。 次に、問題の難易度がSペアの領域選択と分布に依存するかを研究する。 我々はポリシー最適化(PPO)を用いてポリシーモデルを訓練し、近似二項方程式のランダムシステムに対するSペア選択戦略を学習する。
  論文  参考訳（メタデータ） (2020-05-05T02:27:00Z)
• The data-driven physical-based equations discovery using evolutionary approach [77.34726150561087]
  与えられた観測データから数学的方程式を発見するアルゴリズムについて述べる。 このアルゴリズムは遺伝的プログラミングとスパース回帰を組み合わせたものである。 解析方程式の発見や偏微分方程式(PDE)の発見にも用いられる。
  論文  参考訳（メタデータ） (2020-04-03T17:21:57Z)
• Learning Gaussian Graphical Models via Multiplicative Weights [54.252053139374205]
  乗算重み更新法に基づいて,Klivans と Meka のアルゴリズムを適用した。 アルゴリズムは、文献の他のものと質的に類似したサンプル複雑性境界を楽しみます。 ランタイムが低い$O(mp2)$で、$m$サンプルと$p$ノードの場合には、簡単にオンライン形式で実装できる。
  論文  参考訳（メタデータ） (2020-02-20T10:50:58Z)

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

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