論文の概要: 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) に対するアプローチを評価し,完全な教師付き環境での最先端の成果を報告する。 また,事前学習した単語埋め込みと,それに基づくニューラルネットワークの実験を行った。

関連論文リスト

• Scalable network reconstruction in subquadratic time [0.0]
  本稿では,幅広い再構成問題に適用可能な汎用アルゴリズムを提案する。 我々のアルゴリズムは、高い確率で最適なエッジ候補を生成する第2の隣人探索に依存している。
  論文  参考訳（メタデータ） (2024-01-02T19:00:13Z)
• Unsupervised Chunking with Hierarchical RNN [62.15060807493364]
  本稿では,非階層的手法で単語をグループ化する構文的タスクであるチャンキングに対する教師なしアプローチを紹介する。 本稿では,単語-チャンク・チャンク-文合成をモデル化した2層階層型階層型リカレントニューラルネットワーク(HRNN)を提案する。 CoNLL-2000データセットの実験では、既存の教師なし手法よりも顕著な改善が見られ、フレーズF1スコアが最大6ポイント向上した。
  論文  参考訳（メタデータ） (2023-09-10T02:55:12Z)
• Differentially-Private Hierarchical Clustering with Provable Approximation Guarantees [79.59010418610625]
  階層クラスタリングのための微分プライベート近似アルゴリズムについて検討する。 例えば、$epsilon$-DPアルゴリズムは入力データセットに対して$O(|V|2/epsilon)$-additiveエラーを示さなければならない。 本稿では,ブロックを正確に復元する1+o(1)$近似アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-01-31T19:14:30Z)
• 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)
• The Long, the Short and the Random [0.0]
  アルゴリズムは、サブ指数時間における満足な割り当ての正確なカウントを計算する。 このアルゴリズムは、すべてのCNF式が持つ優れた性質を使い、不満足な代入の個数をモノトーン部分形式の空間に関連付けている。
  論文  参考訳（メタデータ） (2020-11-03T12:00:07Z)
• 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)

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

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