論文の概要: 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)$の係数でエンコードするトークンの数を減らす。
我々の学習アプローチは、データ効率が高く、安定であり、従来の計算機代数アルゴリズムや記号計算の実践的な拡張である。
関連論文リスト
- Discovering Algorithms with Computational Language Processing [0.7062238472483737]
本稿では,トークンとして表現された操作列を概念化し,アルゴリズム発見を自動化するフレームワークを提案する。
これらの計算トークンは文法を用いてチェーン化され、より洗練された手続きの形成を可能にする。
我々のアンサンブルであるモンテカルロ木探索(MCTS)は、強化学習(RL)によって導かれ、トークン連鎖を探索し、新しいトークンの作成を促進する。
論文 参考訳（メタデータ） (2025-07-03T21:45:17Z) - 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) - Evolving Reinforcement Learning Algorithms [186.62294652057062]
メタラーニング強化学習アルゴリズムの手法を提案する。
学習アルゴリズムはドメインに依存しないため、トレーニング中に見えない新しい環境に一般化することができる。
従来の制御タスク、gridworld型タスク、atariゲームよりも優れた一般化性能を得る2つの学習アルゴリズムに注目した。
論文 参考訳（メタデータ） (2021-01-08T18:55:07Z) - Quantum-Inspired Algorithms from Randomized Numerical Linear Algebra [53.46106569419296]
我々は、リコメンダシステムと最小二乗回帰のためのクエリをサポートする古典的な(量子でない)動的データ構造を作成する。
これらの問題に対する以前の量子インスパイアされたアルゴリズムは、レバレッジやリッジレベレッジスコアを偽装してサンプリングしていると我々は主張する。
論文 参考訳（メタデータ） (2020-11-09T01:13:07Z) - Quantum-Inspired Classical Algorithm for Principal Component Regression [1.9105479266011323]
本研究では,データ点数に対して時間的多元対数で動作する主成分回帰のアルゴリズムを開発する。
この指数的なスピードアップは、より大きなデータセットにおける潜在的な応用を可能にする。
論文 参考訳（メタデータ） (2020-10-16T20:50:48Z) - Berrut Approximated Coded Computing: Straggler Resistance Beyond
Polynomial Computing [34.69732430310801]
本稿では,ストラグラー効果に対処する代替手法として,Berrut Approximated Coded Computing (BACC)を提案する。
BACCは計算複雑性が低い数値的に安定であることが証明されている。
特に、BACCは、サーバのクラスタ上でディープニューラルネットワークをトレーニングするために使用される。
論文 参考訳（メタデータ） (2020-09-17T14:23:38Z) - Approximation Algorithms for Sparse Principal Component Analysis [57.5357874512594]
主成分分析(PCA)は、機械学習と統計学において広く使われている次元削減手法である。
スパース主成分分析(Sparse principal Component Analysis)と呼ばれる,スパース主成分負荷を求める様々な手法が提案されている。
本研究では,SPCA問題に対するしきい値の精度,時間,近似アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-06-23T04:25:36Z) - Decomposed Quadratization: Efficient QUBO Formulation for Learning Bayesian Network [0.0]
目的関数で使用されるバイナリ変数の数を最小限にすることが不可欠である。
そこで本研究では,従来の二次化手法よりもビット容量に有利なQUBOの定式化を提案する。
論文 参考訳（メタデータ） (2020-06-12T03:19:48Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。