論文の概要: Computational Algebra with Attention: Transformer Oracles for Border Basis Algorithms

• arxiv url: http://arxiv.org/abs/2505.23696v1
• Date: Thu, 29 May 2025 17:35:25 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-05-30 18:14:08.040434
• Title: Computational Algebra with Attention: Transformer Oracles for Border Basis Algorithms
• Title（参考訳）: 注意を伴う計算代数: 境界基底アルゴリズムのためのトランスフォーマーオラクル
• Authors: Hiroshi Kera, Nico Pelleriti, Yuki Ishihara, Max Zimmer, Sebastian Pokutta,
• Abstract要約: 我々は、計算コストのかかる削減ステップを特定し、排除するTransformerベースのオラクルを設計し、訓練する。 ベースアルゴリズムと比較して, 最大3.5倍の高速化率を実現した。 我々の学習アプローチは、データ効率が高く、安定であり、従来の計算機代数アルゴリズムや記号計算の実践的な拡張である。
• 参考スコア（独自算出の注目度）: 22.546453748805025
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Solving systems of polynomial equations, particularly those with finitely many solutions, is a crucial challenge across many scientific fields. Traditional methods like Gr\"obner and Border bases are fundamental but suffer from high computational costs, which have motivated recent Deep Learning approaches to improve efficiency, albeit at the expense of output correctness. In this work, we introduce the Oracle Border Basis Algorithm, the first Deep Learning approach that accelerates Border basis computation while maintaining output guarantees. To this end, we design and train a Transformer-based oracle that identifies and eliminates computationally expensive reduction steps, which we find to dominate the algorithm's runtime. By selectively invoking this oracle during critical phases of computation, we achieve substantial speedup factors of up to 3.5x compared to the base algorithm, without compromising the correctness of results. To generate the training data, we develop a sampling method and provide the first sampling theorem for border bases. We construct a tokenization and embedding scheme tailored to monomial-centered algebraic computations, resulting in a compact and expressive input representation, which reduces the number of tokens to encode an $n$-variate polynomial by a factor of $O(n)$. Our learning approach is data efficient, stable, and a practical enhancement to traditional computer algebra algorithms and symbolic computation.
• Abstract（参考訳）: 多項式方程式の解系、特に有限個の解を持つ方程式は、多くの科学分野において決定的な課題である。 Gr\"オブナーやボーダーベースのような伝統的な手法は基本的なものであるが、高い計算コストに悩まされている。 本研究では,出力保証を維持しつつ,境界基底計算を高速化する最初のディープラーニング手法であるOracle Border Basis Algorithmを導入する。 この目的のために我々は,アルゴリズムのランタイムを支配下に置く計算コストの削減ステップを特定し,排除するトランスフォーマーベースのオラクルを設計し,訓練する。 計算の重要なフェーズにおいて、このオラクルを選択的に呼び出すことにより、結果の正しさを損なうことなく、ベースアルゴリズムと比較して3.5倍の大幅な高速化係数を達成できる。 トレーニングデータを生成するために,境界ベースに対するサンプリング法を開発し,最初のサンプリング定理を提供する。 我々は、単項中心の代数計算に合わせたトークン化と埋め込み方式を構築し、コンパクトで表現豊かな入力表現を実現し、$n$-variate多項式を$O(n)$の係数でエンコードするトークンの数を減らす。 我々の学習アプローチは、データ効率が高く、安定であり、従来の計算機代数アルゴリズムや記号計算の実践的な拡張である。

関連論文リスト

• A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
  そこで本研究では,未知の信号の復元を課題とする,ロバストな位相探索問題を提案する。 提案するオラクルは、単純な勾配ステップと外れ値を用いて、計算学的スペクトル降下を回避している。
  論文  参考訳（メタデータ） (2024-09-07T06:37:23Z)
• Algorithmic Language Models with Neurally Compiled Libraries [16.284360949127723]
  大規模言語モデルには真のアルゴリズム能力がない。 本稿では,基本的な操作と高度な微分可能プログラムのライブラリによるLLMの拡張を提案する。 微分可能なコンピュータを用いたLLaMA3の拡張可能性について検討する。
  論文  参考訳（メタデータ） (2024-07-06T00:27:05Z)
• From Decoding to Meta-Generation: Inference-time Algorithms for Large Language Models [63.188607839223046]
  この調査は、推論中に計算をスケールするメリットに焦点を当てている。 我々はトークンレベルの生成アルゴリズム、メタジェネレーションアルゴリズム、効率的な生成という3つの領域を統一的な数学的定式化の下で探索する。
  論文  参考訳（メタデータ） (2024-06-24T17:45:59Z)
• Reverse That Number! Decoding Order Matters in Arithmetic Learning [49.5504492920404]
  本研究は,最少の桁から出力を優先順位付けすることで,桁順を再評価する新たな戦略を導入する。 従来のSOTA法と比較すると,通常のトレーニングで使用するトークンの3分の1しか必要とせず,精度の全体的な改善が見られた。
  論文  参考訳（メタデータ） (2024-03-09T09:04:53Z)
• Automatic and effective discovery of quantum kernels [41.61572387137452]
  量子コンピューティングは、カーネルマシンが量子カーネルを利用してデータ間の類似度を表現できるようにすることで、機械学習モデルを強化することができる。 本稿では,ニューラルアーキテクチャ検索やAutoMLと同じような最適化手法を用いて,この問題に対するアプローチを提案する。 その結果、高エネルギー物理問題に対する我々のアプローチを検証した結果、最良のシナリオでは、手動設計のアプローチに関して、テストの精度を一致または改善できることが示された。
  論文  参考訳（メタデータ） (2022-09-22T16:42:14Z)
• Quantum-Inspired Algorithms from Randomized Numerical Linear Algebra [53.46106569419296]
  我々は、リコメンダシステムと最小二乗回帰のためのクエリをサポートする古典的な(量子でない)動的データ構造を作成する。 これらの問題に対する以前の量子インスパイアされたアルゴリズムは、レバレッジやリッジレベレッジスコアを偽装してサンプリングしていると我々は主張する。
  論文  参考訳（メタデータ） (2020-11-09T01:13:07Z)
• Berrut Approximated Coded Computing: Straggler Resistance Beyond Polynomial Computing [34.69732430310801]
  本稿では,ストラグラー効果に対処する代替手法として,Berrut Approximated Coded Computing (BACC)を提案する。 BACCは計算複雑性が低い数値的に安定であることが証明されている。 特に、BACCは、サーバのクラスタ上でディープニューラルネットワークをトレーニングするために使用される。
  論文  参考訳（メタデータ） (2020-09-17T14:23:38Z)
• Decomposed Quadratization: Efficient QUBO Formulation for Learning Bayesian Network [0.0]
  目的関数で使用されるバイナリ変数の数を最小限にすることが不可欠である。 そこで本研究では,従来の二次化手法よりもビット容量に有利なQUBOの定式化を提案する。
  論文  参考訳（メタデータ） (2020-06-12T03:19:48Z)

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

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