Fugu-MT 論文翻訳(概要): Stringological sequence prediction II: Right-to-left automaticity and related complexity measures

論文の概要: Stringological sequence prediction II: Right-to-left automaticity and related complexity measures

arxiv url: http://arxiv.org/abs/2607.17369v1
Date: Sun, 19 Jul 2026 18:17:37 GMT
ステータス: 翻訳完了
システム内更新日: 2026-07-21 18:48:37.451881
Title: Stringological sequence prediction II: Right-to-left automaticity and related complexity measures
Title（参考訳）: 文字列的シーケンス予測 II: 右から左への自動性と関連する複雑性尺度
Abstract要約: 本稿では,その右から左(最重要なデジタルファースト)自動性に適応した統計的,計算学的に効率的なアルゴリズムを提案する。また、算術繰り返し複雑性と呼ばれるより表現力のある尺度の予測アルゴリズムを実証する。
参考スコア（独自算出の注目度）: 0.0
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: In a previous paper, we began the study of sequence prediction algorithms adapted to stringological word complexity measures. One measure we considered was left-to-right (most-significant-digit-first) automaticity. Here, we show a statistically and computationally efficient algorithm adapted to the ``dual'' right-to-left (least-significant-digit-first) automaticity, which turns out to be substantially different for our purpose. We also demonstrate a prediction algorithm for a more expressive measure that we call ``arithmetic repetition complexity''. In particular, the latter can be used for predicting the so-called mix-automatic sequences.
Abstract（参考訳）: 前報では,文字列的単語複雑性尺度に適応したシーケンス予測アルゴリズムの研究を始めた。ひとつは、左から右(最も重要なデジタルファースト)の自動化だと考えました。本稿では,'dual'' の右-左-左(最小値-デジタルファースト)自動性に適応した統計的,計算学的に効率的なアルゴリズムについて述べる。また、より表現力のある尺度の予測アルゴリズムを「算数的反復複雑性」と呼んでいる。特に後者は、ミックスオートマチックシーケンス(mix-automatic sequences)と呼ばれる予測に使用できる。

関連論文リスト

Stringological sequence prediction I: efficient algorithms for predicting highly repetitive sequences [0.0]
本稿では,文字列学のアイデアに基づくシーケンス予測のための新しいアルゴリズムを提案する。これらのアルゴリズムは時間と空間の効率が良く、シーケンスの特定の文字列的複雑性尺度に関連する誤り境界を満たす。
論文参考訳（メタデータ） (2026-03-27T11:53:45Z)
Self-Regularized Learning Methods [6.30853901017231]
本稿では,自己正規化の概念に基づいて学習アルゴリズムを解析するための一般的なフレームワークを提案する。我々は、minmax-optimal rateを含むそのようなアルゴリズムの詳細な統計分析を行う。
論文参考訳（メタデータ） (2026-03-17T21:45:50Z)
On the Statistical Query Complexity of Learning Semiautomata: a Random Walk Approach [59.589793281734636]
我々は,アルファベットサイズと入力長の両方が状態数である場合に,統計的クエリの硬さを確立することができることを示す。この結果は、半オートマタの内部状態遷移構造からのみ導かれる。
論文参考訳（メタデータ） (2025-10-05T09:35:35Z)
Bridging Classical and Quantum String Matching: A Computational Reformulation of Bit-Parallelism [0.0]
本稿では,ビット並列文字列マッチングアルゴリズムを量子フレームワークに変換する新しい経路を提案する。ビット並列モデルに量子探索を埋め込むことにより、文字列マッチングの時間的複雑さを低減する。また,Groverの探索による2次高速化を実現するため,性能の向上も図っている。
論文参考訳（メタデータ） (2025-03-07T17:24:00Z)
Reverse That Number! Decoding Order Matters in Arithmetic Learning [49.5504492920404]
本研究は,最少の桁から出力を優先順位付けすることで,桁順を再評価する新たな戦略を導入する。従来のSOTA法と比較すると,通常のトレーニングで使用するトークンの3分の1しか必要とせず,精度の全体的な改善が見られた。
論文参考訳（メタデータ） (2024-03-09T09:04:53Z)
The Search-and-Mix Paradigm in Approximate Nash Equilibrium Algorithms [9.037333651025351]
この研究は、理論計算機科学におけるよく研究された問題に対する近似解析の自動手法を提供する。我々は,このようなアルゴリズムを探索・混合パラダイムに再構成できることを観察する。これにより、混合相を設計・解析する手順を完全に自動化することができる。
論文参考訳（メタデータ） (2023-10-12T06:30:12Z)
Auto-Regressive Next-Token Predictors are Universal Learners [17.416520406390415]
線形次トーケン予測器のような単純なモデルでさえ、チューリングマシンによって効率的に計算される任意の関数を近似することができることを示す。また、線形ネットワークや浅層多層パーセプトロン(MLP)のような単純な次世代予測器が、テキスト生成や算術タスクにおいて非自明な性能を示すことを示す。
論文参考訳（メタデータ） (2023-09-13T14:15:03Z)
Compositional Generalization without Trees using Multiset Tagging and Latent Permutations [121.37328648951993]
まず、各入力トークンに複数の出力トークンをタグ付けします。次に、新しいパラメータ化法と置換予測法を用いて、トークンを出力シーケンスに配置する。我々のモデルは、事前訓練されたセq2seqモデルと、現実的なセマンティック解析タスクに関する先行研究より優れている。
論文参考訳（メタデータ） (2023-05-26T14:09:35Z)
Non-Clairvoyant Scheduling with Predictions Revisited [77.86290991564829]
非論理的スケジューリングでは、優先度不明な処理条件でジョブをスケジューリングするためのオンライン戦略を見つけることが課題である。我々はこのよく研究された問題を、アルゴリズム設計に(信頼できない)予測を統合する、最近人気の高い学習強化された設定で再検討する。これらの予測には所望の特性があり, 高い性能保証を有するアルゴリズムと同様に, 自然な誤差測定が可能であることを示す。
論文参考訳（メタデータ） (2022-02-21T13:18:11Z)
Searching for More Efficient Dynamic Programs [61.79535031840558]
本稿では,プログラム変換の集合,変換プログラムの効率を評価するための単純な指標,およびこの指標を改善するための探索手順について述べる。実際に、自動検索は初期プログラムの大幅な改善を見出すことができることを示す。
論文参考訳（メタデータ） (2021-09-14T20:52:55Z)
On a novel training algorithm for sequence-to-sequence predictive recurrent networks [0.0]
我々は、よく訓練された予測ネットワークのRNのパラメータが互いに独立ではないことを示す。従来のseq2seqアルゴリズムは、予測シーケンス長に比例したサイズの短期記憶を必要とする。本稿では,Seq2seq予測ネットワークのための新しいメモリレスアルゴリズムを提案し,時系列予測の文脈において従来のものと比較する。
論文参考訳（メタデータ） (2021-06-27T00:59:57Z)
Accelerated Message Passing for Entropy-Regularized MAP Inference [89.15658822319928]
離散値のランダムフィールドにおけるMAP推論の最大化は、機械学習の基本的な問題である。この問題の難しさから、特殊メッセージパッシングアルゴリズムの導出には線形プログラミング(LP)緩和が一般的である。古典的加速勾配の根底にある手法を活用することにより,これらのアルゴリズムを高速化するランダム化手法を提案する。
論文参考訳（メタデータ） (2020-07-01T18:43:32Z)

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