論文の概要: Efficient Algorithms for Recognizing Weighted Tree-Adjoining Languages
- arxiv url: http://arxiv.org/abs/2310.15276v1
- Date: Mon, 23 Oct 2023 18:26:00 GMT
- ステータス: 処理完了
- システム内更新日: 2023-10-25 22:11:55.542867
- Title: Efficient Algorithms for Recognizing Weighted Tree-Adjoining Languages
- Title（参考訳）: 重み付き木隣接言語認識のための効率的なアルゴリズム
- Authors: Alexandra Butoi, Tim Vieira, Ryan Cotterell, David Chiang
- Abstract要約: 4つの形式は、ツリー随伴文法(TAG)、線形指数文法(LIG)、プッシュダウン随伴オートマトン(PAA)、組込みプッシュダウンオートマトン(EPDA)に相当する。
我々は,文字列の導出量(文字列のすべてのオートマトン重み)と全導出量(全ての導出量重み)を計算するための新しいアルゴリズムを設計する。
EPDA の場合、我々のアルゴリズムは、$mathcalO(|Gamma|2)$ および $ の因子による Alonso et al. (2001) のアルゴリズムよりも空間効率と時間効率が良い。
- 参考スコア（独自算出の注目度）: 104.90415092306219
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The class of tree-adjoining languages can be characterized by various
two-level formalisms, consisting of a context-free grammar (CFG) or pushdown
automaton (PDA) controlling another CFG or PDA. These four formalisms are
equivalent to tree-adjoining grammars (TAG), linear indexed grammars (LIG),
pushdown-adjoining automata (PAA), and embedded pushdown automata (EPDA). We
define semiring-weighted versions of the above two-level formalisms, and we
design new algorithms for computing their stringsums (the weight of all
derivations of a string) and allsums (the weight of all derivations). From
these, we also immediately obtain stringsum and allsum algorithms for TAG, LIG,
PAA, and EPDA. For LIG, our algorithm is more time-efficient by a factor of
$\mathcal{O}(n|\mathcal{N}|)$ (where $n$ is the string length and
$|\mathcal{N}|$ is the size of the nonterminal set) and more space-efficient by
a factor of $\mathcal{O}(|\Gamma|)$ (where $|\Gamma|$ is the size of the stack
alphabet) than the algorithm of Vijay-Shanker and Weir (1989). For EPDA, our
algorithm is both more space-efficient and time-efficient than the algorithm of
Alonso et al. (2001) by factors of $\mathcal{O}(|\Gamma|^2)$ and
$\mathcal{O}(|\Gamma|^3)$, respectively. Finally, we give the first PAA
stringsum and allsum algorithms.
- Abstract（参考訳）: 木に隣接する言語のクラスは、文脈自由文法(CFG)またはプッシュダウンオートマトン(PDA)が他のCFGまたはPDAを制御するような、様々な2段階の形式主義によって特徴づけられる。
これら4つの形式は、tree-adjoining grammars (tag)、linear indexed grammars (lig)、pushdown-adjoining automata (paa)、embedded pushdown automata (epda)と等価である。
上述の2階形式論の半環重み付きバージョンを定義し、それらの弦和(弦のすべての導出の重み)とアリサム(すべての導出の重み)を計算するための新しいアルゴリズムを設計する。
これらの結果から,TAG,LIG,PAA,EPDAの文字列とアロームのアルゴリズムを瞬時に取得した。
lig に対して、このアルゴリズムは、$\mathcal{o}(n|\mathcal{n}|)$(ここで $n$ は文字列の長さ、$|\mathcal{n}|$ は非終端集合のサイズ)と$\mathcal{o}(|\gamma|)$(ここで $|\gamma|$ はスタックアルファベットの大きさ)のアルゴリズムよりも時間効率が高い。
EPDAの場合、我々のアルゴリズムは、それぞれ$\mathcal{O}(|\Gamma|^2)$と$\mathcal{O}(|\Gamma|^3)$の因子によるAlonso et al. (2001)のアルゴリズムよりも空間効率と時間効率が良い。
最後に,最初のPAA文字列とAllsumアルゴリズムを提案する。
関連論文リスト
- Efficiently Learning One-Hidden-Layer ReLU Networks via Schur
Polynomials [50.90125395570797]
正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。
本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
論文 参考訳（メタデータ） (2023-07-24T14:37:22Z) - Efficient Semiring-Weighted Earley Parsing [71.77514972816347]
本稿では,様々なスピードアップを伴うEarey (1970) の文脈自由構文解析アルゴリズムの,推論システムという形での参照記述を提供する。
私たちのプレゼンテーションには、Earey氏の$O(N3|GR|)$から、既知の最悪のランタイム改善が含まれています。
半重み付き推論への一般化を扱い、Stolcke (1995)のような文法を前処理して推論サイクルを排除し、さらに文プレフィックスの重みを計算するStolckeの手法を一般化する。
論文 参考訳（メタデータ） (2023-07-06T13:33:59Z) - On Computing Optimal Tree Ensembles [7.424944196676223]
ランダム林や、より一般的には(決定ノブレイクダッシュ-)ツリーアンサンブルは、分類と回帰の方法として広く使われている。
最近のアルゴリズムの進歩は、そのサイズや深さなどの様々な測定に最適な決定木を計算することができる。
2つの新しいアルゴリズムと対応する下位境界を提供する。
論文 参考訳（メタデータ） (2023-06-07T13:30:43Z) - Fast and Efficient Matching Algorithm with Deadline Instances [7.613259578185218]
まず、$mathrmdeadline$の市場モデルを紹介します。
最適化された2つのアルゴリズム(textscFastGreedy と textscFastPostponedGreedy)を提示する。
同時に、我々のアルゴリズムは元の2つのアルゴリズムよりも高速に動作します。
論文 参考訳（メタデータ） (2023-05-15T05:21:20Z) - Fully-Dynamic Decision Trees [3.0058005235097114]
ラベル付き例の挿入と削除の任意のシーケンス上で決定木を維持するための,最初の完全動的アルゴリズムを開発した。
実数値機能の場合、このアルゴリズムは挿入/削除毎に$Obig(fracd log3 nepsilon2big)$.amortized run timeを持つ。
同様の保証を持つアルゴリズムは、amortized run time $Omega(d)$と space $tildeOmega (n d)$を使用する。
論文 参考訳（メタデータ） (2022-12-01T18:58:19Z) - Algorithms for Weighted Pushdown Automata [118.67634716230025]
重み付きプッシュダウンオートマトン(WPDA)は多くの自然言語処理タスクの中核にある。
WPDA上で直接動作する新しいアルゴリズムを開発した。
論文 参考訳（メタデータ） (2022-10-13T10:21:31Z) - Provably Faster Algorithms for Bilevel Optimization [54.83583213812667]
バイレベル最適化は多くの重要な機械学習アプリケーションに広く適用されている。
両レベル最適化のための2つの新しいアルゴリズムを提案する。
両アルゴリズムが$mathcalO(epsilon-1.5)$の複雑さを達成し,既存のアルゴリズムを桁違いに上回っていることを示す。
論文 参考訳（メタデータ） (2021-06-08T21:05:30Z) - Higher-order Derivatives of Weighted Finite-state Machines [68.43084108204741]
本研究では、重み付き有限状態機械の正規化定数に関する高次微分の計算について検討する。
文献に記載されていないすべての順序の導関数を評価するための一般アルゴリズムを提案する。
我々のアルゴリズムは以前のアルゴリズムよりもはるかに高速である。
論文 参考訳（メタデータ） (2021-06-01T19:51:55Z) - Well Separated Pair Decomposition and power weighted shortest path
metric algorithm fusion [0.0]
私たちは、あるポイントセットで$s$-wellの分離ペアを$mathbbrn$, $n$$$>$$1で計算するアルゴリズムを考えています。
また、ダイクストラのアルゴリズムの置換であるアルゴリズムについても検討し、特定のパワー重み付き最短経路メトリックを用いてk$-nearestの隣人を計算し、$mathbbrn$,$n$$$$$$$$$$で計算する。
論文 参考訳（メタデータ） (2021-03-20T17:38:13Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。