論文の概要: Higher-order Derivatives of Weighted Finite-state Machines
- arxiv url: http://arxiv.org/abs/2106.00749v2
- Date: Wed, 27 Sep 2023 18:02:34 GMT
- ステータス: 処理完了
- システム内更新日: 2023-09-29 23:34:02.232645
- Title: Higher-order Derivatives of Weighted Finite-state Machines
- Title（参考訳）: 重畳有限状態機械の高次微分
- Authors: Ran Zmigrod, Tim Vieira, Ryan Cotterell
- Abstract要約: 本研究では、重み付き有限状態機械の正規化定数に関する高次微分の計算について検討する。
文献に記載されていないすべての順序の導関数を評価するための一般アルゴリズムを提案する。
我々のアルゴリズムは以前のアルゴリズムよりもはるかに高速である。
- 参考スコア（独自算出の注目度）: 68.43084108204741
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Weighted finite-state machines are a fundamental building block of NLP
systems. They have withstood the test of time -- from their early use in noisy
channel models in the 1990s up to modern-day neurally parameterized conditional
random fields. This work examines the computation of higher-order derivatives
with respect to the normalization constant for weighted finite-state machines.
We provide a general algorithm for evaluating derivatives of all orders, which
has not been previously described in the literature. In the case of
second-order derivatives, our scheme runs in the optimal $\mathcal{O}(A^2 N^4)$
time where $A$ is the alphabet size and $N$ is the number of states. Our
algorithm is significantly faster than prior algorithms. Additionally, our
approach leads to a significantly faster algorithm for computing second-order
expectations, such as covariance matrices and gradients of first-order
expectations.
- Abstract（参考訳）: 重み付き有限状態機械はNLPシステムの基本的な構成要素である。
彼らは、1990年代にノイズの多いチャネルモデルで初期の使用から、現代のニューラルなパラメータ化条件付きランダムフィールドまで、時間の試験を再考した。
本研究では,重み付き有限状態機械の正規化定数に関する高次導関数の計算について検討する。
文献に記載されていないすべての順序の導関数を評価するための一般アルゴリズムを提案する。
2階微分の場合、我々のスキームは最適な$\mathcal{O}(A^2 N^4)$時間で実行され、$A$はアルファベットサイズ、$N$は状態の数である。
我々のアルゴリズムは以前のアルゴリズムよりはるかに高速である。
さらに,本手法により,共分散行列や一階期待勾配などの2階期待値を計算するアルゴリズムが大幅に高速化される。
関連論文リスト
- Fast Minimization of Expected Logarithmic Loss via Stochastic Dual
Averaging [8.990961435218544]
本稿では,対数障壁を用いたB$-sample双対平均化法を提案する。
Poisson逆問題に対して、我々のアルゴリズムは$smashtildeO(d3/varepsilon2)$ timeで$varepsilon$解を得る。
量子状態トモグラフィーの最大線量推定を計算するとき、我々のアルゴリズムは $smashtildeO(d3/varepsilon2)$ time で $varepsilon$-optimal Solution を得る。
論文 参考訳（メタデータ） (2023-11-05T03:33:44Z) - On adaptive low-depth quantum algorithms for robust multiple-phase
estimation [11.678822620192438]
We present robust multiple-phase estimation (RMPE) algorithm with Heisenberg-limited scaling。
これらのアルゴリズムは、初期のフォールトトレラント量子コンピュータに特に適している。
論文 参考訳（メタデータ） (2023-03-14T17:38:01Z) - Accelerated First-Order Optimization under Nonlinear Constraints [73.2273449996098]
我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。
これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
論文 参考訳（メタデータ） (2023-02-01T08:50:48Z) - Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
2つの分布間の最適な輸送距離の効率的な計算は、様々な応用を促進するアルゴリズムとして機能する。
本稿では,$varepsilon$加法精度で最適な輸送を計算できるスケーラブルな一階最適化法を提案する。
論文 参考訳（メタデータ） (2023-01-30T15:46:39Z) - Improved Rate of First Order Algorithms for Entropic Optimal Transport [2.1485350418225244]
本稿では,エントロピー正規化最適輸送を解くための1次アルゴリズムの最先端性を改善する。
そこで本研究では,差分低減による初期2次元ミラー降下アルゴリズムを提案する。
我々のアルゴリズムは、OTを解くために$widetildeO(n2/epsilon)$の速度を持つ加速された原始双対アルゴリズムを開発するためにより多くの研究を刺激するかもしれない。
論文 参考訳（メタデータ） (2023-01-23T19:13:25Z) - Private estimation algorithms for stochastic block models and mixture
models [63.07482515700984]
効率的なプライベート推定アルゴリズムを設計するための一般的なツール。
最初の効率的な$(epsilon, delta)$-differentially private algorithm for both weak recovery and exact recovery。
論文 参考訳（メタデータ） (2023-01-11T09:12:28Z) - Quantum Algorithms for Sampling Log-Concave Distributions and Estimating
Normalizing Constants [8.453228628258778]
我々は,対数凹分布をサンプリングし,正規化定数を推定するための量子アルゴリズムを開発した。
我々はモンテカルロ法と量子ウォークの量子アナログを利用する。
また、正規化定数を推定するための1/epsilon1-o(1)$量子下界も証明する。
論文 参考訳（メタデータ） (2022-10-12T19:10:43Z) - Scheduling with Speed Predictions [10.217102227210669]
本稿では,ジョブの処理時間ではなく,マシンの速度が不明な速度ロスのスケジューリング問題について検討する。
我々の主な結果は、$mineta2 (1+epsilon)2 (1+epsilon)(2+2/alpha)$近似を達成するアルゴリズムである。
予測が正確であれば、この近似は以前最もよく知られた2-1/m$の近似よりも改善される。
論文 参考訳（メタデータ） (2022-05-02T23:39:41Z) - Provably Faster Algorithms for Bilevel Optimization [54.83583213812667]
バイレベル最適化は多くの重要な機械学習アプリケーションに広く適用されている。
両レベル最適化のための2つの新しいアルゴリズムを提案する。
両アルゴリズムが$mathcalO(epsilon-1.5)$の複雑さを達成し,既存のアルゴリズムを桁違いに上回っていることを示す。
論文 参考訳（メタデータ） (2021-06-08T21:05:30Z) - Correcting Momentum with Second-order Information [50.992629498861724]
最適積に$O(epsilon)$epsilon点を求める非臨界最適化のための新しいアルゴリズムを開発した。
我々は、さまざまな大規模ディープラーニングベンチマークとアーキテクチャで結果を検証する。
論文 参考訳（メタデータ） (2021-03-04T19:01:20Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。