論文の概要: On Finding the $K$-best Non-projective Dependency Trees

• arxiv url: http://arxiv.org/abs/2106.00780v1
• Date: Tue, 1 Jun 2021 20:23:41 GMT
• ステータス: 処理完了
• システム内更新日: 2021-06-05 08:59:43.223629
• Title: On Finding the $K$-best Non-projective Dependency Trees
• Title（参考訳）: K$-best非射影依存ツリーの探索について
• Authors: Ran Zmigrod, Tim Vieira, Ryan Cotterell
• Abstract要約: 我々はCamerini et al. (1980) の$K$-bestスパンニングツリーアルゴリズムを単純化する。 ルート制約を受けるグラフの$K$-best依存木を復号するアルゴリズムを新たに拡張する。
• 参考スコア（独自算出の注目度）: 39.5549669100436
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The connection between the maximum spanning tree in a directed graph and the best dependency tree of a sentence has been exploited by the NLP community. However, for many dependency parsing schemes, an important detail of this approach is that the spanning tree must have exactly one edge emanating from the root. While work has been done to efficiently solve this problem for finding the one-best dependency tree, no research has attempted to extend this solution to finding the $K$-best dependency trees. This is arguably a more important extension as a larger proportion of decoded trees will not be subject to the root constraint of dependency trees. Indeed, we show that the rate of root constraint violations increases by an average of $13$ times when decoding with $K\!=\!50$ as opposed to $K\!=\!1$. In this paper, we provide a simplification of the $K$-best spanning tree algorithm of Camerini et al. (1980). Our simplification allows us to obtain a constant time speed-up over the original algorithm. Furthermore, we present a novel extension of the algorithm for decoding the $K$-best dependency trees of a graph which are subject to a root constraint.
• Abstract（参考訳）: 有向グラフにおける最大スパンニングツリーと文の最高の依存ツリーとの接続は、NLPコミュニティによって活用されている。 しかし、多くの依存性解析スキームにおいて、このアプローチの重要な詳細は、スパンニングツリーがルートからちょうど1つのエッジを持つ必要があることである。 一流の依存性ツリーを見つけるために、この問題を効率的に解決する作業が行われているが、k$-best依存性ツリーを見つけるためにこのソリューションを拡張する研究は行われていない。 これはおそらくより重要な拡張であり、デコードされた木の割合が依存性ツリーのルート制約の対象にならないためである。 実際、ルート制約違反の率は、$K\!=\!50$でデコードした場合、$K\!=\!1$とは対照的に平均13ドルずつ増加する。 本稿では,camerini et al の $k$-best spaning tree アルゴリズムの単純化について述べる。 (1980). 我々の単純化により、元のアルゴリズム上で一定の時間短縮が得られる。 さらに、ルート制約を受けるグラフの$k$-best依存性木を復号するアルゴリズムの新たな拡張を提案する。

関連論文リスト

• Unbiased and Efficient Sampling of Dependency Trees [0.0]
  ほとんどのツリーバンクは、すべての有効な依存ツリーがROOTノードから出てくる単一のエッジを持つ必要がある。 Zmigrodらは最近、単一ルート依存ツリーの分布から置き換えることなくサンプリングするアルゴリズムを提案している。 我々は、Wilson-RCを置換したサンプリングアルゴリズムが実際にバイアスを受けていることを示す。
  論文  参考訳（メタデータ） (2022-05-25T09:57:28Z)
• Shallow decision trees for explainable $k$-means clustering [1.2891210250935146]
  決定木内の葉の深さに関連する指標を考慮に入れた効率的なアルゴリズムを提案する。 16個のデータセットの実験において,本アルゴリズムは決定木クラスタリングアルゴリズムよりも優れた結果が得られる。
  論文  参考訳（メタデータ） (2021-12-29T18:22:28Z)
• Efficient Sampling of Dependency Structures [39.5549669100436]
  ルート制約を受けるグラフから依存木を忠実にサンプリングするために、2つのスパンニングツリーサンプリングアルゴリズムを適用する。 我々はColbournのアルゴリズムに基づいて、$mathcalO(K N3 + K2 N)$ timeで置き換えることなく$K$木をサンプリングできる新しい拡張を示す。
  論文  参考訳（メタデータ） (2021-09-14T08:33:12Z)
• Properly learning decision trees in almost polynomial time [25.763690981846125]
  我々は,決定木を適切に,不可知的に学習するための$nO(loglog n)$-timeメンバシップクエリアルゴリズムを提案する。 我々のアルゴリズムは、決定木を学習するための実践と類似点を共有している。 すべての決定木がどのようにして「刈り取られる」かを示し、結果のツリーのすべての変数が影響を受けます。
  論文  参考訳（メタデータ） (2021-09-01T22:12:47Z)
• SGA: A Robust Algorithm for Partial Recovery of Tree-Structured Graphical Models with Noisy Samples [75.32013242448151]
  ノードからの観測が独立しているが非識別的に分散ノイズによって破損した場合、Ising Treeモデルの学習を検討する。 Katiyarら。 (2020) は, 正確な木構造は復元できないが, 部分木構造を復元できることを示した。 統計的に堅牢な部分木回復アルゴリズムであるSymmetrized Geometric Averaging(SGA)を提案する。
  論文  参考訳（メタデータ） (2021-01-22T01:57:35Z)
• An Efficient Adversarial Attack for Tree Ensembles [91.05779257472675]
  傾斜促進決定木(DT)や無作為林(RF)などの木に基づくアンサンブルに対する敵対的攻撃 提案手法は,従来のMILP (Mixed-integer linear programming) よりも数千倍高速であることを示す。 私たちのコードはhttps://chong-z/tree-ensemble- attackで利用可能です。
  論文  参考訳（メタデータ） (2020-10-22T10:59:49Z)
• Please Mind the Root: Decoding Arborescences for Dependency Parsing [67.71280539312536]
  我々はUniversal Dependency Treebankから多くの言語における最先端の出力を分析する。 最悪の制約違反率は24%です。
  論文  参考訳（メタデータ） (2020-10-06T08:31:14Z)
• On $\ell_p$-norm Robustness of Ensemble Stumps and Trees [83.81523991945018]
  我々は,アンサンブルスタンプの音響検証のための効率的なプログラムベースアルゴリズムを開発した。 我々は,アンサンブル・スタンプや木を訓練するための最初の認証された防御法を,$ell_p$ノルム摂動に関して実証した。
  論文  参考訳（メタデータ） (2020-08-20T03:42:40Z)
• MurTree: Optimal Classification Trees via Dynamic Programming and Search [61.817059565926336]
  動的プログラミングと探索に基づいて最適な分類木を学習するための新しいアルゴリズムを提案する。 当社のアプローチでは,最先端技術が必要とする時間のごく一部しか使用せず,数万のインスタンスでデータセットを処理することが可能です。
  論文  参考訳（メタデータ） (2020-07-24T17:06:55Z)

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

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