論文の概要: Efficient Semiring-Weighted Earley Parsing

• arxiv url: http://arxiv.org/abs/2307.02982v1
• Date: Thu, 6 Jul 2023 13:33:59 GMT
• ステータス: 処理完了
• システム内更新日: 2023-07-07 13:54:28.230701
• Title: Efficient Semiring-Weighted Earley Parsing
• Title（参考訳）: 効率的なセミリング重み付きearleyパース
• Authors: Andreas Opedal, Ran Zmigrod, Tim Vieira, Ryan Cotterell, Jason Eisner
• Abstract要約: 本稿では,様々なスピードアップを伴うEarey (1970) の文脈自由構文解析アルゴリズムの,推論システムという形での参照記述を提供する。 私たちのプレゼンテーションには、Earey氏の$O(N3|GR|)$から、既知の最悪のランタイム改善が含まれています。 半重み付き推論への一般化を扱い、Stolcke (1995)のような文法を前処理して推論サイクルを排除し、さらに文プレフィックスの重みを計算するStolckeの手法を一般化する。
• 参考スコア（独自算出の注目度）: 71.77514972816347
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: This paper provides a reference description, in the form of a deduction system, of Earley's (1970) context-free parsing algorithm with various speed-ups. Our presentation includes a known worst-case runtime improvement from Earley's $O (N^3|G||R|)$, which is unworkable for the large grammars that arise in natural language processing, to $O (N^3|G|)$, which matches the runtime of CKY on a binarized version of the grammar $G$. Here $N$ is the length of the sentence, $|R|$ is the number of productions in $G$, and $|G|$ is the total length of those productions. We also provide a version that achieves runtime of $O (N^3|M|)$ with $|M| \leq |G|$ when the grammar is represented compactly as a single finite-state automaton $M$ (this is partly novel). We carefully treat the generalization to semiring-weighted deduction, preprocessing the grammar like Stolcke (1995) to eliminate deduction cycles, and further generalize Stolcke's method to compute the weights of sentence prefixes. We also provide implementation details for efficient execution, ensuring that on a preprocessed grammar, the semiring-weighted versions of our methods have the same asymptotic runtime and space requirements as the unweighted methods, including sub-cubic runtime on some grammars.
• Abstract（参考訳）: 本稿では,様々なスピードアップを伴うEarey (1970) の文脈自由解析アルゴリズムの,推論システムという形での参照記述を提供する。 私たちのプレゼンテーションでは、Earey氏の$O(N^3|G|R|)$から、自然言語処理で発生する大きな文法では動作不能な$O(N^3|G|)$から、CKYのランタイムを二項化された文法の$G$にマッチさせる$O(N^3|G|)$まで、既知の最悪のランタイム改善が含まれている。 ここで$N$は文の長さ、$|R|$は$G$のプロダクションの数、$|G|$はそれらのプロダクションの総の長さである。 また、文法が単一の有限状態オートマトン$m$としてコンパクトに表現されるときに、$|m| \leq |g|$で$o (n^3|m|)$のランタイムを実現するバージョンも提供します。 半重み付き推論への一般化を慎重に扱い、Stolcke (1995)のような文法を前処理して推論サイクルを排除し、さらに文プレフィックスの重みを計算するStolckeの手法を一般化する。 プリプロセスされた文法では、メソッドのセミリング重み付けバージョンは、非重み付けメソッドと同じ漸近ランタイムとスペース要件を持ち、いくつかの文法上のサブキュービックランタイムを含む。

関連論文リスト

• Superposed Decoding: Multiple Generations from a Single Autoregressive Inference Pass [72.07642648108849]
  Superposed Decodingは、1つの自己回帰推論パスのコストで$k$のドラフトを生成する新しい復号アルゴリズムである。 Superposed Decodingは、他のデコード戦略と組み合わせることで、推論時間計算のスケーリング時に普遍的なカバレッジが向上する。
  論文  参考訳（メタデータ） (2024-05-28T17:40:48Z)
• Efficient Algorithms for Recognizing Weighted Tree-Adjoining Languages [104.90415092306219]
  4つの形式は、ツリー随伴文法(TAG)、線形指数文法(LIG)、プッシュダウン随伴オートマトン(PAA)、組込みプッシュダウンオートマトン(EPDA)に相当する。 我々は,文字列の導出量(文字列のすべてのオートマトン重み)と全導出量(全ての導出量重み)を計算するための新しいアルゴリズムを設計する。 EPDA の場合、我々のアルゴリズムは、$mathcalO(|Gamma|2)$ および $ の因子による Alonso et al. (2001) のアルゴリズムよりも空間効率と時間効率が良い。
  論文  参考訳（メタデータ） (2023-10-23T18:26:00Z)
• Breaking the cubic barrier in the Solovay-Kitaev algorithm [0.0]
  我々は、一般有限で逆閉生成集合がクーディットに作用するようなソロヴィ・キタエフの定理とアルゴリズムを改善する。 我々の結果はより一般的に、連結半単純実リー群を密に生成する任意の有限集合に対して成り立つ。
  論文  参考訳（メタデータ） (2023-06-22T18:35:06Z)
• Projection-free Online Exp-concave Optimization [21.30065439295409]
  LOOをベースとしたONSスタイルのアルゴリズムを提案する。これは全体$O(T)$コールを使用して,$widetildeO(n2/3T2/3)$でバウンドされた最悪のケースを保証します。 我々のアルゴリズムは、重要かつ確実な低次元データシナリオにおいて最も興味深い。
  論文  参考訳（メタデータ） (2023-02-09T18:58:05Z)
• Scalable Differentially Private Clustering via Hierarchically Separated Trees [82.69664595378869]
  我々は,最大$O(d3/2log n)cdot OPT + O(k d2 log2 n / epsilon2)$,$epsilon$はプライバシ保証であることを示す。 最悪の場合の保証は、最先端のプライベートクラスタリング手法よりも悪いが、提案するアルゴリズムは実用的である。
  論文  参考訳（メタデータ） (2022-06-17T09:24:41Z)
• Nearly Optimal Policy Optimization with Stable at Any Time Guarantee [53.155554415415445]
  citetshani 2020optimisticのポリシーベースのメソッドは、$tildeO(sqrtSAH3K + sqrtAH4K)$である。$S$は状態の数、$A$はアクションの数、$H$は地平線、$K$はエピソードの数、$sqrtSH$は情報理論の下限の$tildeOmega(sqrtSAH)と比べてギャップがある。
  論文  参考訳（メタデータ） (2021-12-21T01:54:17Z)
• Higher-order Derivatives of Weighted Finite-state Machines [68.43084108204741]
  本研究では、重み付き有限状態機械の正規化定数に関する高次微分の計算について検討する。 文献に記載されていないすべての順序の導関数を評価するための一般アルゴリズムを提案する。 我々のアルゴリズムは以前のアルゴリズムよりもはるかに高速である。
  論文  参考訳（メタデータ） (2021-06-01T19:51:55Z)
• The Trimmed Lasso: Sparse Recovery Guarantees and Practical Optimization by the Generalized Soft-Min Penalty [14.85926834924458]
  本稿では,古典ラッソと一般パターンを補間するスパース近似あるいは最良部分集合の解法を提案する。 我々は、一般的なソフトミンペナルティを計算するためにスパースタイムを導出する。
  論文  参考訳（メタデータ） (2020-05-18T18:43:06Z)
• Efficient and Robust Algorithms for Adversarial Linear Contextual Bandits [13.32560004325655]
  古典的な$K$武器の線形文脈包帯問題の逆変法を考える。 $d$-dimensionalコンテキストがランダムに生成されるという仮定の下で、古典的なExp3アルゴリズムに基づいて効率的なアルゴリズムを開発する。
  論文  参考訳（メタデータ） (2020-02-01T22:49:46Z)

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

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。