Fugu-MT 論文翻訳(概要): Stringological sequence prediction I: efficient algorithms for predicting highly repetitive sequences

論文の概要: Stringological sequence prediction I: efficient algorithms for predicting highly repetitive sequences

arxiv url: http://arxiv.org/abs/2603.26852v1
Date: Fri, 27 Mar 2026 11:53:45 GMT
ステータス: 翻訳完了
システム内更新日: 2026-03-31 23:18:44.667229
Title: Stringological sequence prediction I: efficient algorithms for predicting highly repetitive sequences
Title（参考訳）: 文字列的シーケンス予測I:高度反復配列予測のための効率的なアルゴリズム
Authors: Vanessa Kosoy,
Abstract要約: 本稿では,文字列学のアイデアに基づくシーケンス予測のための新しいアルゴリズムを提案する。これらのアルゴリズムは時間と空間の効率が良く、シーケンスの特定の文字列的複雑性尺度に関連する誤り境界を満たす。
参考スコア（独自算出の注目度）: 0.0
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: We propose novel algorithms for sequence prediction based on ideas from stringology. These algorithms are time and space efficient and satisfy mistake bounds related to particular stringological complexity measures of the sequence. In this work (the first in a series) we focus on two such measures: (i) the size of the smallest straight-line program that produces the sequence, and (ii) the number of states in the minimal automaton that can compute any symbol in the sequence when given its position in base k as input. These measures are interesting because multiple rich classes of sequences studied in combinatorics of words (automatic sequences, morphic sequences, Sturmian words) have low complexity and hence high predictability in this sense.
Abstract（参考訳）: 本稿では,文字列学のアイデアに基づくシーケンス予測のための新しいアルゴリズムを提案する。これらのアルゴリズムは時間と空間の効率が良く、シーケンスの特定の文字列的複雑性尺度に関連する誤り境界を満たす。本研究(シリーズ第1回)では,2つの対策に焦点を当てる。 i) シーケンスを生成する最小の直線プログラムのサイズ、および 2) 入力として基底 k の位置を与えられたとき、列内の任意のシンボルを計算できる最小のオートマトンにおける状態の数。これらの測度は、単語の組合せ論(オートマチックな列、モルフィックな列、ストゥルミアンな単語)で研究される複数の豊富な列のクラスは、複雑さが低く、したがってこの意味で高い予測可能性を持つため、興味深い。

関連論文リスト

Arithmetic sequences as quantum states [0.0]
ここでは、正の整数の順序リストとして定義される算術列を考える。そのような列は量子状態にキャストすることができ、フォン・ノイマンのエントロピーを通じてそのサプライズを定量化することができる。
論文参考訳（メタデータ） (2025-01-10T19:00:01Z)
Linear-Time Modeling of Linguistic Structure: An Order-Theoretic Perspective [97.57162770792182]
文字列内のトークンのペア間の関係をモデル化するタスクは、自然言語を理解する上で不可欠な部分である。これらの徹底的な比較は避けられ、さらに、トークン間の関係を文字列上の部分順序としてキャストすることで、複雑さを線形に減らすことができる。提案手法は,文字列中の各トークンの実際の数を並列に予測し,それに従ってトークンをソートすることで,文字列内のトークンの総順序を決定する。
論文参考訳（メタデータ） (2023-05-24T11:47:35Z)
Quantum algorithm for position weight matrix matching [0.9404723842159504]
バイオインフォマティクス, 位置重み行列(PWM)マッチングにおける問題に対する2つの量子アルゴリズムを提案する。提案した2つのアルゴリズム、ナイーブ法とモンテカルロ法は、生物学的配列のエントリへの分子アクセスを考慮し、一致したセグメントを出力する。
論文参考訳（メタデータ） (2023-03-07T00:34:16Z)
Towards Correlated Sequential Rules [4.743965372344134]
高実用性シーケンシャルルールマイニング(HUSRM)は、結果のシーケンシャルパターンの発生を予測できる信頼度や確率を調査するために設計された。 HUSRMと呼ばれる既存のアルゴリズムは、生成されたシーケンシャルルール間の相関を無視しながら、すべての許容ルールを抽出することに制限されている。本稿では,HUSRMに相関の概念を統合するために,CoUSR(Cocorlation High-utility Sequence Rule Minr)と呼ばれる新しいアルゴリズムを提案する。
論文参考訳（メタデータ） (2022-10-27T17:27:23Z)
A Non-monotonic Self-terminating Language Model [62.93465126911921]
本稿では,不完全復号アルゴリズムによる非終端列の問題に焦点をあてる。まず、グリーディ探索、トップ$kのサンプリング、核サンプリングを含む不完全確率復号アルゴリズムを定義する。次に,単調な終端確率の制約を緩和する非単調な自己終端言語モデルを提案する。
論文参考訳（メタデータ） (2022-10-03T00:28:44Z)
Quantum Algorithm for Anomaly Detection of Sequences [13.087762988229068]
振幅領域におけるPiecewise Aggregate(ADPAAD)を用いた異常検出のための量子アルゴリズムを提案する。我々の量子アルゴリズムは、その古典的手法よりもサブシーケンスの数とサブシーケンスの長さを高速化することができる。
論文参考訳（メタデータ） (2022-09-18T16:14:16Z)
Learning Temporal Point Processes for Efficient Retrieval of Continuous Time Event Sequences [24.963828650935913]
NEUROSEQRETは,あるクエリシーケンスに対して,関連する連続時間イベントシーケンスの検索とランク付けを学習する。精度と効率のトレードオフを提供する関係モデルの2つの変種を開発する。いくつかのデータセットを用いて行った実験では、NEUROSEQRETの精度がいくつかのベースラインを超えていることが示されている。
論文参考訳（メタデータ） (2022-02-17T11:16:31Z)
Searching for More Efficient Dynamic Programs [61.79535031840558]
本稿では,プログラム変換の集合,変換プログラムの効率を評価するための単純な指標,およびこの指標を改善するための探索手順について述べる。実際に、自動検索は初期プログラムの大幅な改善を見出すことができることを示す。
論文参考訳（メタデータ） (2021-09-14T20:52:55Z)
Determinantal Beam Search [75.84501052642361]
ビームサーチは、ニューラルシーケンスモデルをデコードするためのゴーツー戦略である。複数のソリューションを要求するユースケースでは、多様あるいは代表的なセットがしばしば望まれる。ビームサーチを一連の部分決定問題として繰り返し行うことにより、アルゴリズムを多種多様なサブセット選択プロセスに変換することができる。
論文参考訳（メタデータ） (2021-06-14T13:01:46Z)
Latent Programmer: Discrete Latent Codes for Program Synthesis [56.37993487589351]
プログラム合成や文書要約などの多くのシーケンス学習タスクにおいて、重要な問題は出力シーケンスの広い空間を探索することである。本稿では,検索対象とする出力の表現を学習することを提案する。本稿では,まず入力/出力サンプルから離散潜在コードを予測するプログラム合成手法であるemphLatent Programmerを紹介し,そのプログラムを対象言語で生成する。
論文参考訳（メタデータ） (2020-12-01T10:11:35Z)
Consistency of a Recurrent Language Model With Respect to Incomplete Decoding [67.54760086239514]
逐次言語モデルから無限長のシーケンスを受信する問題について検討する。不整合に対処する2つの対策として、トップkと核サンプリングの一貫性のある変種と、自己終端の繰り返し言語モデルを提案する。
論文参考訳（メタデータ） (2020-02-06T19:56:15Z)

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