論文の概要: Algorithms for Acyclic Weighted Finite-State Automata with Failure Arcs
- arxiv url: http://arxiv.org/abs/2301.06862v1
- Date: Tue, 17 Jan 2023 13:15:44 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-18 14:10:07.381801
- Title: Algorithms for Acyclic Weighted Finite-State Automata with Failure Arcs
- Title（参考訳）: 故障アークを有する非巡回重み付き有限状態オートマタのアルゴリズム
- Authors: Anej Svete, Benjamin Dayan, Tim Vieira, Ryan Cotterell, Jason Eisner
- Abstract要約: Oleft(|E| + s |Sigma| |Q| T_textmax log|Sigma|right)$で実行される一般非巡回WFSAのアルゴリズムを提案する。
障害遷移トポロジーがCRFで実証された条件を満たすと、$T_textmax$ factorを落とすことができる。
後者の場合 (ring-weighted acyclic WFSAs) では、$style Oleft(|E| + |Sigma| |) を持つ別のアルゴリズムの複雑さを与える。
- 参考スコア（独自算出の注目度）: 66.47284608209692
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Weighted finite-state automata (WSFAs) are commonly used in NLP. Failure
transitions are a useful extension for compactly representing backoffs or
interpolation in $n$-gram models and CRFs, which are special cases of WFSAs.
The pathsum in ordinary acyclic WFSAs is efficiently computed by the backward
algorithm in time $O(|E|)$, where $E$ is the set of transitions. However, this
does not allow failure transitions, and preprocessing the WFSA to eliminate
failure transitions could greatly increase $|E|$. We extend the backward
algorithm to handle failure transitions directly. Our approach is efficient
when the average state has outgoing arcs for only a small fraction $s \ll 1$ of
the alphabet $\Sigma$. We propose an algorithm for general acyclic WFSAs which
runs in $O{\left(|E| + s |\Sigma| |Q| T_\text{max} \log{|\Sigma|}\right)}$,
where $Q$ is the set of states and $T_\text{max}$ is the size of the largest
connected component of failure transitions. When the failure transition
topology satisfies a condition exemplified by CRFs, the $T_\text{max}$ factor
can be dropped, and when the weight semiring is a ring, the $\log{|\Sigma|}$
factor can be dropped. In the latter case (ring-weighted acyclic WFSAs), we
also give an alternative algorithm with complexity $\displaystyle O{\left(|E| +
|\Sigma| |Q| \min(1,s\pi_\text{max}) \right)}$, where $\pi_\text{max}$ is the
size of the longest failure path.
- Abstract（参考訳）: 重み付き有限状態オートマトン(WSFA)は一般的にNLPで使用される。
障害遷移は、wfsasの特別なケースであるn$-gramモデルとcrfsのバックオフや補間をコンパクトに表現するための便利な拡張である。
通常の非巡回 wfsas のパスサムは、逆アルゴリズムで時刻 $o(|e|)$ で計算され、ここで $e$ は遷移の集合である。
しかし、これは障害遷移を許さず、WFSAを前処理して障害遷移をなくすことで、$|E|$が大幅に増加する可能性がある。
後方アルゴリズムを拡張して、障害遷移を直接処理します。
我々のアプローチは、平均状態がアルファベット$\Sigma$の小さな分数$s \ll 1$に対して弧を出力する場合に効率的である。
O{\left(|E| + s |\Sigma| |Q| T_\text{max} \log{|\Sigma|}\right)}$, $Q$は状態の集合であり、$T_\text{max}$は障害遷移の最大の連結成分のサイズである。
故障遷移位相がcrfsによって例示される条件を満たすとき、$t_\text{max}$ factor を落とすことができ、ウェイトセミリングが環であれば$\log{|\sigma|}$ factor を落とすことができる。
後者の場合 (ring-weighted acyclic wfsas) は、複雑性を$\displaystyle o{\left(|e| + |\sigma| |q| \min(1,s\pi_\text{max}) \right)} とする別のアルゴリズムを与える(ただし、$\pi_\text{max}$ は最長の障害パスの大きさである)。
関連論文リスト
- An Oblivious Stochastic Composite Optimization Algorithm for Eigenvalue
Optimization Problems [76.2042837251496]
相補的な合成条件に基づく2つの難解なミラー降下アルゴリズムを導入する。
注目すべきは、どちらのアルゴリズムも、目的関数のリプシッツ定数や滑らかさに関する事前の知識なしで機能する。
本稿では,大規模半確定プログラム上での手法の効率性とロバスト性を示す。
論文 参考訳（メタデータ） (2023-06-30T08:34:29Z) - Memory-Constrained Algorithms for Convex Optimization via Recursive
Cutting-Planes [23.94542304111204]
勾配降下法と切断平面法の間に正のトレードオフを与えるアルゴリズムの第一級は、$epsilonleq 1/sqrt d$である。
規則$epsilon leq d-Omega(d)$では、$p=d$のアルゴリズムが情報理論の最適メモリ利用を実現し、勾配降下のオラクル-複雑度を改善する。
論文 参考訳（メタデータ） (2023-06-16T17:00:51Z) - Parameterized Approximation for Robust Clustering in Discrete Geometric Spaces [2.687607197645453]
次元$Theta(log n)$ が $(sqrt3/2-o(1))$hard である場合でさえ、FPTアルゴリズムを近似する。
また、次元 $Theta(log n)$ が $(sqrt3/2-o(1))$hard であるような特別な場合でさえ、FPTアルゴリズムを近似することを示す。
論文 参考訳（メタデータ） (2023-05-12T08:43:28Z) - Eluder-based Regret for Stochastic Contextual MDPs [43.19667415823089]
文脈マルコフ決定過程(CMDP)における後悔最小化のためのE-UC$3$RLアルゴリズムを提案する。
我々のアルゴリズムは効率的であり(効率的なオフライン回帰オラクルを仮定すると)、$ widetildeO(H3 sqrtT |S| |A|d_mathrmE(mathcalP)$の後悔の保証を享受する。
論文 参考訳（メタデータ） (2022-11-27T20:38:47Z) - Near-Optimal Regret Bounds for Multi-batch Reinforcement Learning [54.806166861456035]
本研究では,有限水平マルコフ決定過程(MDP)によってモデル化されたエピソディック強化学習(RL)問題をバッチ数に制約を加えて検討する。
我々は,$tildeO(sqrtSAH3Kln (1/delta))$tildeO(cdot)をほぼ最適に後悔するアルゴリズムを設計し,$(S,A,H,K)$の対数項を$K$で隠蔽する。
技術的貢献は2つある: 1) 探索のためのほぼ最適設計スキーム
論文 参考訳（メタデータ） (2022-10-15T09:22:22Z) - Faster Sampling from Log-Concave Distributions over Polytopes via a
Soft-Threshold Dikin Walk [28.431572772564518]
我々は、$d$-dimensional log-concave distribution $pi(theta) propto e-f(theta)$からポリトープ$K$に制約された$m$不等式をサンプリングする問題を考える。
我々の主な成果は、少なくとも$O((md + d L2 R2) times MDomega-1) log(fracwdelta)$ arithmetic operation to sample from $pi$ の "soft-warm' variant of the Dikin walk Markov chain" である。
論文 参考訳（メタデータ） (2022-06-19T11:33:07Z) - Corralling a Larger Band of Bandits: A Case Study on Switching Regret
for Linear Bandits [99.86860277006318]
本稿では,一組の逆アルゴリズムを組み合わせ,学習することの問題点について考察する。
Agarwal et al. の CORRAL はこの目標を、$widetildeO(sqrtd S T)$ の残酷なオーバーヘッドで達成している。
この問題に触発されて、後悔のオーバーヘッドが百万ドルにしか依存しない大規模バンディットアルゴリズムのバンドを囲む新しいレシピを提案する。
論文 参考訳（メタデータ） (2022-02-12T21:55:44Z) - On Submodular Contextual Bandits [92.45432756301231]
作用が基底集合の部分集合であり、平均報酬が未知の単調部分モジュラ函数によってモデル化されるような文脈的包帯の問題を考える。
Inverse Gap Weighting 戦略により,提案アルゴリズムは推定関数の局所的最適度を効率よくランダム化することを示す。
論文 参考訳（メタデータ） (2021-12-03T21:42:33Z) - Faster quantum-inspired algorithms for solving linear systems [0.05076419064097732]
そこで本研究では,データ構造を$x$で出力する古典的アルゴリズムにより,エントリへのサンプリングとクエリが可能であることを示す。
この出力は、量子線型解法の出力の古典的なアナログと見なすことができる。
論文 参考訳（メタデータ） (2021-03-18T15:12:44Z) - Streaming Complexity of SVMs [110.63976030971106]
本稿では,ストリーミングモデルにおけるバイアス正規化SVM問題を解く際の空間複雑性について検討する。
両方の問題に対して、$frac1lambdaepsilon$の次元に対して、$frac1lambdaepsilon$よりも空間的に小さいストリーミングアルゴリズムを得ることができることを示す。
論文 参考訳（メタデータ） (2020-07-07T17:10:00Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。