論文の概要: Stringological sequence prediction III: layered ziplines and a tradeoff between efficiency and expressivity
- arxiv url: http://arxiv.org/abs/2609.19940v1
- Date: Thu, 17 Sep 2026 09:15:29 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-09-20 08:55:54.196633
- Title: Stringological sequence prediction III: layered ziplines and a tradeoff between efficiency and expressivity
- Title（参考訳）: 弦学シーケンス予測III:層状ジップラインと効率と表現率のトレードオフ
- Abstract要約: 本稿では,特に効率的な予測アルゴリズムを有する算術的反復に関する複雑性尺度を示す。
複雑性尺度は「ジップラインプログラム」の制限クラスによって定義される
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In previous papers, we began the study of sequence prediction algorithms adapted to stringological word complexity measures. In particular, we defined a complexity measure called Arithmetic Repetition Complexity (ARC) which admits a polynomial-time prediction algorithm with a mistake bound quasilinear in the complexity. Here, we show a weaker complexity measure related to ARC that admits an especially efficient prediction algorithm: an algorithm that runs in quasilinear time and polylog space for appropriate highly-structured sequences. The complexity measure is defined via a restricted class of "zipline programs" (a variant of straight-line programs), which we call layered. We thus get a less expressive measure with a more efficient algorithm (compared to our results for ARC), demonstrating a possible tradeoff.
- Abstract（参考訳）: 前報では,文字列的単語複雑性尺度に適応したシーケンス予測アルゴリズムの研究を始めた。
特に,算術的反復複雑度 (ARC) と呼ばれる複雑性尺度を定義した。
ここでは、特に効率的な予測アルゴリズムである、準線形時間で実行されるアルゴリズムと、適切な高構造配列に対してポリログ空間を含むARCに関連するより弱い複雑性尺度を示す。
複雑性尺度は、私たちが階層化と呼ぶ「ジープラインプログラム」(ストレートラインプログラムの変種)の制限クラスによって定義される。
したがって、より効率的なアルゴリズム(ARCの結果と比較)で表現力の低い尺度を得ることができ、トレードオフの可能性を示している。
関連論文リスト
- Stringological sequence prediction II: Right-to-left automaticity and related complexity measures [0.0]
本稿では,その右から左(最重要なデジタルファースト)自動性に適応した統計的,計算学的に効率的なアルゴリズムを提案する。
また、算術繰り返し複雑性と呼ばれるより表現力のある尺度の予測アルゴリズムを実証する。
論文 参考訳（メタデータ） (2026-07-19T18:17:37Z) - Optimal Centered Active Excitation in Linear System Identification [48.09783075634403]
最適中心雑音励振を用いた線形システム同定のための能動学習アルゴリズムを提案する。
まず、任意の能動学習アルゴリズムに対して、所定の精度と信頼レベルを達成するために、サンプルの複雑さの低い境界を確立する。
論文 参考訳（メタデータ） (2026-04-07T07:16:16Z) - Stringological sequence prediction I: efficient algorithms for predicting highly repetitive sequences [0.0]
本稿では,文字列学のアイデアに基づくシーケンス予測のための新しいアルゴリズムを提案する。
これらのアルゴリズムは時間と空間の効率が良く、シーケンスの特定の文字列的複雑性尺度に関連する誤り境界を満たす。
論文 参考訳（メタデータ） (2026-03-27T11:53:45Z) - A dynamic programming algorithm for span-based nested named-entity
recognition in O(n^2) [5.228711636020665]
探索空間に補足的構造制約を加えることで、ネストされたNERは2次時間複雑性を持ち、これは非ネストの場合と同じ複雑さを持つことを示す。
提案アルゴリズムは、3つの標準英語ベンチマークの大部分をカバーし、同等の実験結果を提供する。
論文 参考訳（メタデータ） (2022-10-10T14:47:36Z) - Linear Bandit Algorithms with Sublinear Time Complexity [67.21046514005029]
既存の線形バンディットアルゴリズムを高速化し,arms $k$ でステップ毎の複雑性サブリニアを実現する。
提案するアルゴリズムは、いくつかの$alpha(t) > 0$ と $widetilde o(stt)$ regret に対して1ステップあたり$o(k1-alpha(t))$ の複雑さを達成することができる。
論文 参考訳（メタデータ） (2021-03-03T22:42:15Z) - Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。
問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。
本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-01-07T08:00:02Z) - Accelerated Message Passing for Entropy-Regularized MAP Inference [89.15658822319928]
離散値のランダムフィールドにおけるMAP推論の最大化は、機械学習の基本的な問題である。
この問題の難しさから、特殊メッセージパッシングアルゴリズムの導出には線形プログラミング(LP)緩和が一般的である。
古典的加速勾配の根底にある手法を活用することにより,これらのアルゴリズムを高速化するランダム化手法を提案する。
論文 参考訳（メタデータ） (2020-07-01T18:43:32Z) - Iterative Algorithm Induced Deep-Unfolding Neural Networks: Precoding
Design for Multiuser MIMO Systems [59.804810122136345]
本稿では,AIIDNN(ディープ・アンフォールディング・ニューラルネット)を一般化した,ディープ・アンフォールディングのためのフレームワークを提案する。
古典的重み付き最小二乗誤差(WMMSE)反復アルゴリズムの構造に基づく効率的なIAIDNNを提案する。
提案したIAIDNNは,計算複雑性を低減した反復WMMSEアルゴリズムの性能を効率よく向上することを示す。
論文 参考訳（メタデータ） (2020-06-15T02:57:57Z) - Beyond Worst-Case Analysis in Stochastic Approximation: Moment
Estimation Improves Instance Complexity [58.70807593332932]
近似問題に対する勾配に基づく手法のオラクル複雑性について検討する。
最悪のケースの複雑さではなく、インスタンス依存の複雑さに焦点を当てます。
提案アルゴリズムとその解析はモーメント推定の成功を理論的に正当化する。
論文 参考訳（メタデータ） (2020-06-08T09:25:47Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。