論文の概要: Quotient Tree Arithmetic: Deferred-Division Computation with Bounded Symbolic Depth and Cross-Subtree Cancellation
- arxiv url: http://arxiv.org/abs/2607.22612v1
- Date: Mon, 15 Jun 2026 05:09:59 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-08-02 22:55:38.984747
- Title: Quotient Tree Arithmetic: Deferred-Division Computation with Bounded Symbolic Depth and Cross-Subtree Cancellation
- Title（参考訳）: 定性木算術:有界シンボリック深さとクロスサブツリーキャンセラによるデファーレッドディビジョン計算
- Abstract要約: 本稿では,値が遅延商対として表される計算基板を提案する。
3つの構造定理がQTAを下支えする。
機械学習トレーニングでは、QTAは勾配下フローをゼロにする構造的防止を提供する。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We introduce Quotient Tree Arithmetic (QTA), a computational substrate in which values are represented as deferred quotient pairs (N, D) whose ratio is evaluated lazily at a designated materialization boundary. The framework applies to any domain: IEEE 754 doubles used as exact integer containers give exact rational arithmetic within the 2^53 exactness window; arbitrary IEEE doubles extend coverage to transcendental values including machine learning activations such as exp(x) and sqrt(x). Three structural theorems underpin QTA. (1) Bounded Depth Growth: each arithmetic operation increases tree depth by at most 1, giving O(m) tree size after m operations with no combinatorial explosion. (2) Cross-Subtree Cancellation: subtrees appearing in both numerator and denominator positions cancel via reference identity without arithmetic, including transcendental values computed once and shared. (3) Deferred Stability: a single IEEE division at the materialization boundary introduces at most one-half ULP of rounding error, versus O(m) ULP for eager evaluation. For machine learning training, QTA provides: structural prevention of gradient underflow to zero; O(1)-cost gradient computation via chain-rule tape collapse when intermediate activations are reference-identical; shared-weight batch compression reducing DAG storage from O(BLd) to O(L+Bd) for a batch of B examples through L layers; and tracked factor cancellation replacing O(log n) GCD with O(1) trial division when denominators are known. We propose a vectorized hardware normalization instruction (RatCleanup) for SIMD-parallel rational pair reduction. The algebraic foundation is the localization of a ring at its multiplicative set, connecting QTA to algebraic structure theory while grounding it in hardware-native IEEE arithmetic.
- Abstract（参考訳）: 本稿では,定性化境界で遅延的に評価される遅延商対 (N, D) として値を表す計算基板であるQuotient Tree Arithmetic (QTA) を紹介する。
IEEE 754は正確な整数コンテナとして使われ、2^53の正確性ウィンドウ内で正確な有理算術を与え、任意のIEEEはexp(x)やsqrt(x)のような機械学習のアクティベーションを含む超越値にまでカバー範囲を広げる。
3つの構造定理がQTAを下支えする。
1)境界深さ成長:各算術演算が木深を少なくとも1で増加させ、Oを与える
(m) 複合爆発のないm操作後の木の大きさ。
2)クロスサブツリーキャンセラ: 数値と分母の両方に現れるサブツリーは、算術なしで参照IDを介してキャンセルされ、一度計算して共有される超越値を含む。
(3) デフォルト安定性: 物質化境界における1つのIEEE分割は、Oに対して、少なくとも1/半の丸め誤差のUDPを導入する
(m) 熱心に評価するためのULP。
機械学習トレーニングにおいて、QTAは、0への勾配下フローの構造的防止、中間アクティベーションが参照IDである場合のチェーンルールテープ崩壊によるO(1)コスト勾配計算、L層を経由した一連のB例のバッチに対して、DAGストレージをO(BLd)からO(L+Bd)に還元する共有重み付きバッチ圧縮、O(log)を代替する追跡因子のキャンセルを提供する。
n) 分母が知られている場合、O(1)裁判区分によるGCD
SIMD-並列有理対還元のためのベクトル化ハードウェア正規化命令(RatCleanup)を提案する。
代数的基礎は環の乗法集合での局所化であり、QTAをハードウェアネイティブなIEEE算術で基礎づけながら代数構造理論に接続する。
関連論文リスト
- A Constant-Competitive Algorithm for Dynamic Mixture-of-Experts Serving [0.0]
Huang, Lou, and XiaoはDynamic Mixture-of-Experts Servingを導入し、その積分原始問題に対してO(sqrt(log k))競合ランダム化アルゴリズムを与えた。
ランダム化された原始競合比は、実際には、任意の数の専門家に対して Theta(1) であることを示す。
論文 参考訳（メタデータ） (2026-08-15T03:51:27Z) - Rake-Compress Riccati Recursions for Parallel Scenario-Tree Model Predictive Control [0.0]
そこで本研究では, レーク圧縮木収縮に基づく並列解法を提案する。
レークは葉とその親エッジを除去し、親ノードデータへの寄与を減少させる。
圧縮は、一意ノードを排除し、2つの隣接するエッジを1つのエッジで置き換える。
論文 参考訳（メタデータ） (2026-08-02T15:52:43Z) - MergeLLL: A Hierarchical Divide-and-Conquer Framework for LLL-Based Lattice Reduction [0.0]
格子基底還元アルゴリズムは、計算数理論や格子ベースの暗号に様々な応用がある。
マージソートにおける分割・分散戦略に動機づけられたMergeLLLを提案する。
メソッドは自然に並列化可能で、効率的なマルチコアと分散実行を可能にします。
論文 参考訳（メタデータ） (2026-06-25T09:20:03Z) - Hierarchical Attention via Domain Decomposition [0.0]
2レベル重なり合うシュワルツ領域分解に基づく階層的注意機構を提案する。
この手法は、2レベルシュワルツ領域分解法が局所的なサブドメイン補正と大域的、長距離的な情報を伝達する粗いレベルを組み合わせるという観察によって動機づけられた。
同次ディリクレ境界条件を持つ単純な1次元拡散問題を用いて有限次元作用素学習の文脈でその有用性を検証した。
論文 参考訳（メタデータ） (2026-06-16T22:40:40Z) - Transformers Provably Learn to Internalize Chain-of-Thought [65.41010769606844]
Implicit Chain-of-Thought (ICoT) は、隠れた状態の中で中間段階を内部化するモデルを訓練する。
Log-ICoTはシンキングトークンを一度に削除し、$k$のリニアから対数へのステージ数を削減します。
多層変圧器の実験により理論が確認され、より深い層に段階的に推論がどのように吸収されるかが可視化される。
論文 参考訳（メタデータ） (2026-05-27T15:17:06Z) - NOETHER: A Constructive Framework for Metamorphic Pattern Discovery from Operator Algebras [6.691613382732758]
メタモルフィックテストはIEEE/ISOソフトウェアテスト標準で認識され、AIシステムに対してますます推奨される。
既存のアプローチでは,3つの基本的疑問が残る帰納的根拠を共有している。
本稿では,演算子代数からメタパタン集合への下流ステップが機械的かつ証明可能なフレームワークを提案する。
論文 参考訳（メタデータ） (2026-05-17T11:18:35Z) - Circuit Complexity of Hierarchical Knowledge Tracing and Implications for Log-Precision Transformers [2.688207424884465]
経験的に、再帰不変木で訓練されたトランスフォーマーエンコーダは、置換不変ショートカットに収束する。
これらの知見は, 階層構造に基づく事前知識追跡のための構造認識的目的と反復的メカニズムを動機付けている。
論文 参考訳（メタデータ） (2026-03-25T01:10:42Z) - Wave-Attractor-Tree: A Hierarchical Binary Tree Reduction Architecture for Efficient Sequence Modeling [0.0]
作業は階層的なバイナリツリーベースのリダクションを導入し、通常の自己アテンションを置き換える。
このモデルは、コンバージェンス速度と長距離構造上の依存関係の精度の両方において、標準トランスフォーマーを著しく上回っている。
論文 参考訳（メタデータ） (2026-02-28T21:17:27Z) - On the Constant Depth Implementation of Pauli Exponentials [49.48516314472825]
任意の長さの $Zotimes n$指数を$mathcalO(n)$ ancillae と 2体 XX と ZZ の相互作用を用いて一定深さの回路に分解する。
クビットリサイクルの恩恵を受ける回路の書き直し規則を導入し,本手法の正しさを実証する。
論文 参考訳（メタデータ） (2024-08-15T17:09:08Z) - Stable Nonconvex-Nonconcave Training via Linear Interpolation [51.668052890249726]
本稿では,ニューラルネットワークトレーニングを安定化(大規模)するための原理的手法として,線形アヘッドの理論解析を提案する。
最適化過程の不安定性は、しばしば損失ランドスケープの非単調性によって引き起こされるものであり、非拡張作用素の理論を活用することによって線型性がいかに役立つかを示す。
論文 参考訳（メタデータ） (2023-10-20T12:45:12Z) - Tractable Bounding of Counterfactual Queries by Knowledge Compilation [51.47174989680976]
本稿では, パール構造因果モデルにおいて, 因果関係などの部分的特定可能なクエリのバウンダリングの問題について議論する。
最近提案された反復EMスキームは初期化パラメータをサンプリングしてそれらの境界を内部近似する。
シンボルパラメータを実際の値に置き換えた回路構造を,単一のシンボル知識コンパイルによって得られることを示す。
論文 参考訳（メタデータ） (2023-10-05T07:10:40Z) - Efficient Computation of Counterfactual Bounds [44.4263314637532]
我々は,構造因果モデルのサブクラスにおけるクレダルネットのアルゴリズムを用いて,正確な反ファクト境界を計算する。
近似の精度を信頼性のある間隔で評価する。
論文 参考訳（メタデータ） (2023-07-17T07:59:47Z) - Detection-Recovery Gap for Planted Dense Cycles [72.4451045270967]
期待帯域幅$n tau$とエッジ密度$p$をエルドホス=R'enyiグラフ$G(n,q)$に植え込むモデルを考える。
低次アルゴリズムのクラスにおいて、関連する検出および回復問題に対する計算しきい値を特徴付ける。
論文 参考訳（メタデータ） (2023-02-13T22:51:07Z) - Gradient Boosted Binary Histogram Ensemble for Large-scale Regression [60.16351608335641]
本研究では,2値ヒストグラム分割とアンサンブル学習に基づくテキストグラディエント2値ヒストグラムアンサンブル(GBBHE)と呼ばれる大規模回帰問題に対する勾配向上アルゴリズムを提案する。
実験では, 勾配向上回帰木 (GBRT) などの他の最先端アルゴリズムと比較して, GBBHEアルゴリズムは大規模データセット上での実行時間が少なく, 有望な性能を示す。
論文 参考訳（メタデータ） (2021-06-03T17:05:40Z) - Lagrangian Decomposition for Neural Network Verification [148.0448557991349]
ニューラルネットワーク検証の基本的なコンポーネントは、出力が取ることのできる値のバウンダリの計算である。
ラグランジアン分解に基づく新しい手法を提案する。
ランニングタイムのごく一部で、既成の解法に匹敵するバウンダリが得られることを示す。
論文 参考訳（メタデータ） (2020-02-24T17:55:10Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。