Fugu-MT 論文翻訳(概要): Span-based discontinuous constituency parsing: a family of exact chart-based algorithms with time complexities from O(n^6) down to O(n^3)

論文の概要: Span-based discontinuous constituency parsing: a family of exact chart-based algorithms with time complexities from O(n^6) down to O(n^3)

arxiv url: http://arxiv.org/abs/2003.13785v1
Date: Mon, 30 Mar 2020 19:54:20 GMT
ステータス: 処理完了
システム内更新日: 2022-12-18 07:36:37.889699
Title: Span-based discontinuous constituency parsing: a family of exact chart-based algorithms with time complexities from O(n^6) down to O(n^3)
Title（参考訳）: Span-based discontinuous constituency parsing:O(n^6)からO(n^3)までの時間複雑さを持つ正確なチャートベースのアルゴリズム群
Authors: Caio Corro
Abstract要約: 本研究では,ブロック次数2の不連続な構成木をスパンベースで解析する新しいアルゴリズムを提案する。より小さな検索空間と、$mathcal O(n6)$ down から $mathcal O(n3)$ までの時間複雑度を持つ変種を構築できることを示します。
参考スコア（独自算出の注目度）: 5.228711636020665
License: http://creativecommons.org/licenses/by/4.0/
Abstract: We introduce a novel chart-based algorithm for span-based parsing of discontinuous constituency trees of block degree two, including ill-nested structures. In particular, we show that we can build variants of our parser with smaller search spaces and time complexities ranging from $\mathcal O(n^6)$ down to $\mathcal O(n^3)$. The cubic time variant covers 98\% of constituents observed in linguistic treebanks while having the same complexity as continuous constituency parsers. We evaluate our approach on German and English treebanks (Negra, Tiger and Discontinuous PTB) and report state-of-the-art results in the fully supervised setting. We also experiment with pre-trained word embeddings and \bert{}-based neural networks.
Abstract（参考訳）: 本研究では,ブロック次数2の不連続な構成木をスパンベースで解析する新しいアルゴリズムを提案する。特に、より小さな検索空間と、$\mathcal O(n^6)$から$\mathcal O(n^3)$までの時間複雑度を持つパーサの変種を構築することができることを示す。立方体時間変異は、言語木バンクで観察される成分の98 %をカバーし、連続した選挙区パーサーと同じ複雑さを持つ。我々は,ドイツ語と英語のツリーバンク (Negra, Tiger, Discontinuous PTB) に対するアプローチを評価し,完全な教師付き環境での最先端の成果を報告する。また,事前学習した単語埋め込みと,それに基づくニューラルネットワークの実験を行った。

関連論文リスト

Integrating Supertag Features into Neural Discontinuous Constituent Parsing [0.0]
伝統的な選挙区の見解では、構成要素は隣接した単語で構成されており、ドイツ語のような言語で一般的である。トランジションベースの構文解析は、大きな注釈付きコーパス上で教師あり学習を用いて生のテキストを入力した木を生成する。
論文参考訳（メタデータ） (2024-10-11T12:28:26Z)
Perturb-and-Project: Differentially Private Similarities and Marginals [73.98880839337873]
差分プライバシーのための入力摂動フレームワークを再検討し、入力にノイズを付加する。まず、ペアワイズ・コサイン類似性をプライベートにリリースするための新しい効率的なアルゴリズムを設計する。我々は,$k$の辺縁クエリを$n$の機能に対して計算する新しいアルゴリズムを導出する。
論文参考訳（メタデータ） (2024-06-07T12:07:16Z)
Tree-Averaging Algorithms for Ensemble-Based Unsupervised Discontinuous Constituency Parsing [23.091613114955543]
予測木を平均化することにより,既存の不連続な動作の異なるアンサンブルを構築することを提案する。次に、タスクに取り組むための効率的な正確なアルゴリズムを開発し、全てのサンプルに対して妥当な時間で実行します。 3つのデータセットの結果は、我々のメソッドがすべてのメトリクスですべてのベースラインを上回っていることを示している。
論文参考訳（メタデータ） (2024-02-29T21:49:31Z)
Scalable network reconstruction in subquadratic time [0.0]
本稿では,この2次ベースラインを大幅に上回る広範囲の再構成問題に適用可能な一般アルゴリズムを提案する。我々のアルゴリズムは、高い確率で最適なエッジ候補を生成する第2の隣人探索に依存している。本アルゴリズムは2次ベースラインよりも桁違いに高速な性能を実現する。
論文参考訳（メタデータ） (2024-01-02T19:00:13Z)
Unsupervised Chunking with Hierarchical RNN [62.15060807493364]
本稿では,非階層的手法で単語をグループ化する構文的タスクであるチャンキングに対する教師なしアプローチを紹介する。本稿では,単語-チャンク・チャンク-文合成をモデル化した2層階層型階層型リカレントニューラルネットワーク(HRNN)を提案する。 CoNLL-2000データセットの実験では、既存の教師なし手法よりも顕著な改善が見られ、フレーズF1スコアが最大6ポイント向上した。
論文参考訳（メタデータ） (2023-09-10T02:55:12Z)
A dynamic programming algorithm for span-based nested named-entity recognition in O(n^2) [5.228711636020665]
探索空間に補足的構造制約を加えることで、ネストされたNERは2次時間複雑性を持ち、これは非ネストの場合と同じ複雑さを持つことを示す。提案アルゴリズムは、3つの標準英語ベンチマークの大部分をカバーし、同等の実験結果を提供する。
論文参考訳（メタデータ） (2022-10-10T14:47:36Z)
Can RNNs learn Recursive Nested Subject-Verb Agreements? [4.094098809740732]
言語処理にはネストした木構造を抽出する機能が必要である。リカレントニューラルネットワーク(RNN)の最近の進歩は、いくつかの言語タスクでほぼ人間に近いパフォーマンスを実現します。
論文参考訳（メタデータ） (2021-01-06T20:47:02Z)
Strongly Incremental Constituency Parsing with Graph Neural Networks [70.16880251349093]
文を構文木にパースすることは、NLPの下流アプリケーションに恩恵をもたらす。トランジッションベースは、状態遷移システムでアクションを実行することでツリーを構築する。既存のトランジションベースは主にシフト・リデュース・トランジション・システムに基づいている。
論文参考訳（メタデータ） (2020-10-27T19:19:38Z)
RNNs can generate bounded hierarchical languages with optimal memory [113.73133308478612]
RNNは、自然言語構文の足場を反映した境界階層言語を効率的に生成できることを示す。 Dyck-($k$,$m$)は、よくネストされた括弧($k$型)と$m$バウンドされたネスト深さの言語である。明示的な構成により,$O(m log k)$ hidden units の RNN がメモリの指数的削減に十分であることを示す。
論文参考訳（メタデータ） (2020-10-15T04:42:29Z)
Recursive Top-Down Production for Sentence Generation with Latent Trees [77.56794870399288]
自然および合成言語に対する文脈自由文法の生成特性をモデル化する。潜伏二分木構造にN$の葉を持つ動的プログラミングアルゴリズムを提案する。また,Multi30kデータセットを用いたドイツ語と英語の翻訳実験を行った。
論文参考訳（メタデータ） (2020-10-09T17:47:16Z)
Span-based Semantic Parsing for Compositional Generalization [53.24255235340056]
SpanBasedSPは入力発話上のスパンツリーを予測し、部分的なプログラムが入力内のスパンをどのように構成するかを明示的に符号化する。 GeoQuery、SCAN、CLOSUREでは、SpanBasedSPはランダムスプリットの強いseq2seqベースラインと似ているが、構成一般化を必要とするスプリットのベースラインに比べて劇的に性能が向上する。
論文参考訳（メタデータ） (2020-09-13T16:42:18Z)

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