論文の概要: Efficient Sampling of Dependency Structures
- arxiv url: http://arxiv.org/abs/2109.06521v1
- Date: Tue, 14 Sep 2021 08:33:12 GMT
- ステータス: 処理完了
- システム内更新日: 2021-09-16 00:57:44.488792
- Title: Efficient Sampling of Dependency Structures
- Title（参考訳）: 依存性構造の効率的なサンプリング
- Authors: Ran Zmigrod, Tim Vieira, Ryan Cotterell
- Abstract要約: ルート制約を受けるグラフから依存木を忠実にサンプリングするために、2つのスパンニングツリーサンプリングアルゴリズムを適用する。
我々はColbournのアルゴリズムに基づいて、$mathcalO(K N3 + K2 N)$ timeで置き換えることなく$K$木をサンプリングできる新しい拡張を示す。
- 参考スコア（独自算出の注目度）: 39.5549669100436
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Probabilistic distributions over spanning trees in directed graphs are a
fundamental model of dependency structure in natural language processing,
syntactic dependency trees. In NLP, dependency trees often have an additional
root constraint: only one edge may emanate from the root. However, no sampling
algorithm has been presented in the literature to account for this additional
constraint. In this paper, we adapt two spanning tree sampling algorithms to
faithfully sample dependency trees from a graph subject to the root constraint.
Wilson (1996)'s sampling algorithm has a running time of $\mathcal{O}(H)$ where
$H$ is the mean hitting time of the graph. Colbourn (1996)'s sampling algorithm
has a running time of $\mathcal{O}(N^3)$, which is often greater than the mean
hitting time of a directed graph. Additionally, we build upon Colbourn's
algorithm and present a novel extension that can sample $K$ trees without
replacement in $\mathcal{O}(K N^3 + K^2 N)$ time. To the best of our knowledge,
no algorithm has been given for sampling spanning trees without replacement
from a directed graph.
- Abstract（参考訳）: 有向グラフにおける木にまたがる確率分布は、自然言語処理や構文依存木における依存構造の基本モデルである。
NLPでは、依存木は、しばしば追加のルート制約を持ち、一方のエッジだけがルートから発散する。
しかし、この追加制約を考慮に入れたサンプリングアルゴリズムは文献には示されていない。
本稿では,2つのスパンディングツリーサンプリングアルゴリズムを用いて,根の制約を受けるグラフから依存性ツリーを忠実にサンプリングする。
wilson (1996)のサンプリングアルゴリズムは、実行時間は$\mathcal{o}(h)$であり、ここで$h$はグラフの平均ヒット時間である。
colbourn (1996) のサンプリングアルゴリズムの実行時間は$\mathcal{o}(n^3)$であり、これはしばしば有向グラフの平均ヒット時間よりも大きい。
さらに、colbournのアルゴリズムに基づいて、$\mathcal{o}(k n^3 + k^2 n)$ timeで置き換えることなく$k$木をサンプリングできる新しい拡張を提供する。
我々の知る限りでは、有向グラフから置き換えることなく木々をサンプリングするアルゴリズムは与えられていない。
関連論文リスト
- On Computing Optimal Tree Ensembles [7.424944196676223]
ランダム林や、より一般的には(決定ノブレイクダッシュ-)ツリーアンサンブルは、分類と回帰の方法として広く使われている。
最近のアルゴリズムの進歩は、そのサイズや深さなどの様々な測定に最適な決定木を計算することができる。
2つの新しいアルゴリズムと対応する下位境界を提供する。
論文 参考訳（メタデータ） (2023-06-07T13:30:43Z) - Detection-Recovery Gap for Planted Dense Cycles [72.4451045270967]
期待帯域幅$n tau$とエッジ密度$p$をエルドホス=R'enyiグラフ$G(n,q)$に植え込むモデルを考える。
低次アルゴリズムのクラスにおいて、関連する検出および回復問題に対する計算しきい値を特徴付ける。
論文 参考訳（メタデータ） (2023-02-13T22:51:07Z) - Random graph matching at Otter's threshold via counting chandeliers [16.512416293014493]
そこで本研究では,各木に根付いた重み付き木を数えることで構築した類似度スコアに基づく,グラフマッチングの効率的なアルゴリズムを提案する。
これは、明示的な一定の相関で成功し、スパースグラフと密度グラフの両方に適用する最初のグラフマッチングアルゴリズムである。
論文 参考訳（メタデータ） (2022-09-25T20:00:28Z) - Unbiased and Efficient Sampling of Dependency Trees [0.0]
ほとんどのツリーバンクは、すべての有効な依存ツリーがROOTノードから出てくる単一のエッジを持つ必要がある。
Zmigrodらは最近、単一ルート依存ツリーの分布から置き換えることなくサンプリングするアルゴリズムを提案している。
我々は、Wilson-RCを置換したサンプリングアルゴリズムが実際にバイアスを受けていることを示す。
論文 参考訳（メタデータ） (2022-05-25T09:57:28Z) - Active-LATHE: An Active Learning Algorithm for Boosting the Error
Exponent for Learning Homogeneous Ising Trees [75.93186954061943]
我々は、$rho$が少なくとも0.8$である場合に、エラー指数を少なくとも40%向上させるアルゴリズムを設計し、分析する。
我々の分析は、グラフの一部により多くのデータを割り当てるために、微小だが検出可能なサンプルの統計的変動を巧みに活用することに基づいている。
論文 参考訳（メタデータ） (2021-10-27T10:45:21Z) - Robustifying Algorithms of Learning Latent Trees with Vector Variables [92.18777020401484]
Recursive Grouping (RG) と Chow-Liu Recursive Grouping (CLRG) のサンプル複雑性について述べる。
RG,CLRG,Neighbor Joining (NJ) およびSpectral NJ (SNJ) をトラッピングした内積を用いて強化する。
我々は、潜在木の構造学習において、最初の既知のインスタンス依存の不合理性の結果を導出する。
論文 参考訳（メタデータ） (2021-06-02T01:37:52Z) - On Finding the $K$-best Non-projective Dependency Trees [39.5549669100436]
我々はCamerini et al. (1980) の$K$-bestスパンニングツリーアルゴリズムを単純化する。
ルート制約を受けるグラフの$K$-best依存木を復号するアルゴリズムを新たに拡張する。
論文 参考訳（メタデータ） (2021-06-01T20:23:41Z) - 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) - Please Mind the Root: Decoding Arborescences for Dependency Parsing [67.71280539312536]
我々はUniversal Dependency Treebankから多くの言語における最先端の出力を分析する。
最悪の制約違反率は24%です。
論文 参考訳（メタデータ） (2020-10-06T08:31:14Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。