論文の概要: Learning to Compute Gröbner Bases

• arxiv url: http://arxiv.org/abs/2311.12904v3
• Date: Wed, 06 Nov 2024 15:39:05 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-11-07 19:20:26.959983
• Title: Learning to Compute Gröbner Bases
• Title（参考訳）: コンピューティングのGröbnerベースを学ぶ
• Authors: Hiroshi Kera, Yuki Ishihara, Yuta Kambe, Tristan Vaccon, Kazuhiro Yokoyama,
• Abstract要約: 本稿では,トランスフォーマーを用いたGr"オブザーバベース学習について,初めて述べる。 トレーニングには、システムの多くのペアと関連するGr"オブナーベースが必要です。 本稿では,トークンを連続バイアスで処理し,語彙集合の成長を回避するためのハイブリッド入力を提案する。
• 参考スコア（独自算出の注目度）: 3.8214695776749013
• License:
• Abstract: Solving a polynomial system, or computing an associated Gr\"obner basis, has been a fundamental task in computational algebra. However, it is also known for its notorious doubly exponential time complexity in the number of variables in the worst case. This paper is the first to address the learning of Gr\"obner basis computation with Transformers. The training requires many pairs of a polynomial system and the associated Gr\"obner basis, raising two novel algebraic problems: random generation of Gr\"obner bases and transforming them into non-Gr\"obner ones, termed as backward Gr\"obner problem. We resolve these problems with 0-dimensional radical ideals, the ideals appearing in various applications. Further, we propose a hybrid input embedding to handle coefficient tokens with continuity bias and avoid the growth of the vocabulary set. The experiments show that our dataset generation method is a few orders of magnitude faster than a naive approach, overcoming a crucial challenge in learning to compute Gr\"obner bases, and Gr\"obner computation is learnable in a particular class.
• Abstract（参考訳）: 多項式系を解くこと、あるいは関連するGr\"オブナー基底を計算することは、計算代数学の基本的な課題である。 しかし、最悪の場合の変数数の2倍の指数時間複雑性でも知られている。 本稿では,変換器を用いたGr\"オブザーバ基底計算の学習について述べる。 トレーニングには多項式系と関連する Gr\ オブナー基底の多くのペアが必要であり、Gr\ オブナー基底のランダムな生成と非 Gr\ オブナー基底への変換という2つの新しい代数的問題を提起する。 我々はこれらの問題を、様々な応用に現れる0-次元根基イデアル(イデアル)で解決する。 さらに,連続性バイアスで係数トークンを処理し,語彙集合の成長を回避するためのハイブリッド入力埋め込みを提案する。 実験の結果,我々のデータセット生成手法は単純アプローチよりも数桁高速であり,Gr\"オブナーベースを学習する上で重要な課題を克服し,Gr\"オブナー計算は特定のクラスで学習可能であることがわかった。

関連論文リスト

• Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
  最近提案された量子アルゴリズムarXiv:2206.14999は半定値プログラミング(SDP)に基づいている SDPにインスパイアされた量子アルゴリズムを2乗和に一般化する。 この結果から,本アルゴリズムは大きな問題に適応し,最もよく知られた古典学に近似することが示唆された。
  論文  参考訳（メタデータ） (2024-08-14T19:04:13Z)
• Gröbner Basis Cryptanalysis of Ciminion and Hydra [0.0]
  二次システム解決攻撃は、CiminionやHydraのような対称鍵プリミティブに対して深刻な脅威となる。 シミニオンに対しては、アフィン変換による反復モデルに対する次数逆レキシコグラフィ(DRL)Gr"オブナー基底を構築する。 Hydra に対して、Sage のコンピュータ支援による証明として、2次 DRL Gr" 基底が Hydra ヘッドの反復系にすでに含まれていることを示す。
  論文  参考訳（メタデータ） (2024-05-08T13:14:04Z)
• Online Stability Improvement of Groebner Basis Solvers using Deep Learning [29.805408457645886]
  異なる変数や単項順序が異なる消去テンプレートにつながることを示す。 次に、元の係数の集合が、優れた解法の選択を訓練するのに十分な情報を含むことを証明した。
  論文  参考訳（メタデータ） (2024-01-17T16:51:28Z)
• Predicting the cardinality and maximum degree of a reduced Gr\"obner basis [0.0]
  ニューラルネットワーク回帰モデルを構築し、二項イデアルの「オブナーベース」の複雑性の鍵となる指標を予測する。 この研究は、Gr"オブザーバ計算によるニューラルネットワークによる予測が簡単なプロセスではない理由を説明している。
  論文  参考訳（メタデータ） (2023-02-10T16:33:58Z)
• A Strongly Polynomial Algorithm for Approximate Forster Transforms and its Application to Halfspace Learning [56.86097988183311]
  フォースター変換(フォースターりゅう、英: Forster transform)は、データセットを放射等方性位置に配置し、その性質のいくつかを維持しながら、データセットを正規化する方法である。
  論文  参考訳（メタデータ） (2022-12-06T14:32:02Z)
• Transformers Learn Shortcuts to Automata [52.015990420075944]
  低深度変換器は任意の有限状態オートマトンを計算できる。 我々は,$O(log T)$レイヤを持つ変換器が,長さ$T$の入力シーケンス上で,オートマトンを正確に再現可能であることを示す。 さらに、これらの解の脆性について検討し、潜在的な緩和を提案する。
  論文  参考訳（メタデータ） (2022-10-19T17:45:48Z)
• JiuZhang: A Chinese Pre-trained Language Model for Mathematical Problem Understanding [74.12405417718054]
  本稿では,中国初の数学的事前学習言語モデル(PLM)を提示することにより,機械の数学的知性向上を目指す。 他の標準のNLPタスクとは異なり、数学的テキストは問題文に数学的用語、記号、公式を含むため理解が難しい。 基礎課程と上級課程の両方からなる数学PLMの学習を改善するための新しいカリキュラム事前学習手法を設計する。
  論文  参考訳（メタデータ） (2022-06-13T17:03:52Z)
• Learning Polynomial Transformations [41.30404402331856]
  ガウスの高次元二次変換を学習する問題を考察する。 我々の結果はガウス分布だけでなく、任意の不変な入力分布にまで拡張される。 また、テンソル環分解の証明可能な保証を持つ最初の分解時間アルゴリズムを与える。
  論文  参考訳（メタデータ） (2022-04-08T17:59:31Z)
• Learning Algebraic Recombination for Compositional Generalization [71.78771157219428]
  合成一般化のための代数的組換え学習のためのエンドツーエンドニューラルモデルLeARを提案する。 主要な洞察は、意味解析タスクを潜在構文代数学と意味代数学の間の準同型としてモデル化することである。 2つの現実的・包括的構成一般化の実験は、我々のモデルの有効性を実証している。
  論文  参考訳（メタデータ） (2021-07-14T07:23:46Z)
• Learning a performance metric of Buchberger's algorithm [2.1485350418225244]
  Buchbergerのアルゴリズムが実行されている間に発生する加算の数を、開始入力だけで予測しようと試みる。 我々の研究は概念実証として機能し、Buchbergerのアルゴリズムの加算数を予測することは機械学習の観点からの問題であることを示した。
  論文  参考訳（メタデータ） (2021-06-07T14:57:57Z)
• Recognizing and Verifying Mathematical Equations using Multiplicative Differential Neural Units [86.9207811656179]
  メモリ拡張ニューラルネットワーク(NN)は、高次、メモリ拡張外挿、安定した性能、より高速な収束を実現することができることを示す。 本モデルでは,現在の手法と比較して1.53%の精度向上を達成し,2.22%のtop-1平均精度と2.96%のtop-5平均精度を達成している。
  論文  参考訳（メタデータ） (2021-04-07T03:50:11Z)

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

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