論文の概要: The expected sum of edge lengths in planar linearizations of trees. Theory and applications

• arxiv url: http://arxiv.org/abs/2207.05564v4
• Date: Mon, 18 Sep 2023 07:50:43 GMT
• ステータス: 処理完了
• システム内更新日: 2023-09-20 01:41:26.843824
• Title: The expected sum of edge lengths in planar linearizations of trees. Theory and applications
• Title（参考訳）: 木の平面線型化における辺長の期待和。 理論と応用
• Authors: Llu\'is Alemany-Puig and Ramon Ferrer-i-Cancho
• Abstract要約: 平面配置における期待和と射影配置における期待和の関係を示す。 エッジ長の和の期待値を計算するために,$O(n)$-timeアルゴリズムを導出する。 本研究は, 並列コーパスに適用し, 依存関係構造に対する公式制約の強度が増大するにつれて, 実際の依存性距離とランダムベースラインとのギャップが減少することを示した。
• 参考スコア（独自算出の注目度）: 0.16317061277456998
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Dependency trees have proven to be a very successful model to represent the syntactic structure of sentences of human languages. In these structures, vertices are words and edges connect syntactically-dependent words. The tendency of these dependencies to be short has been demonstrated using random baselines for the sum of the lengths of the edges or its variants. A ubiquitous baseline is the expected sum in projective orderings (wherein edges do not cross and the root word of the sentence is not covered by any edge), that can be computed in time $O(n)$. Here we focus on a weaker formal constraint, namely planarity. In the theoretical domain, we present a characterization of planarity that, given a sentence, yields either the number of planar permutations or an efficient algorithm to generate uniformly random planar permutations of the words. We also show the relationship between the expected sum in planar arrangements and the expected sum in projective arrangements. In the domain of applications, we derive a $O(n)$-time algorithm to calculate the expected value of the sum of edge lengths. We also apply this research to a parallel corpus and find that the gap between actual dependency distance and the random baseline reduces as the strength of the formal constraint on dependency structures increases, suggesting that formal constraints absorb part of the dependency distance minimization effect. Our research paves the way for replicating past research on dependency distance minimization using random planar linearizations as random baseline.
• Abstract（参考訳）: 依存木は人間の言語の文の構文構造を表現する非常に成功したモデルであることが証明されている。 これらの構造では、頂点は単語であり、辺は構文的に依存する単語を接続する。 これらの依存関係が短い傾向は、辺の長さまたはその変異の合計のランダムなベースラインを用いて実証されている。 ユビキタスベースライン(ユビキタスベースライン)は、射影順序付け(エッジが交差せず、文の根語が任意のエッジで覆われていない場合)において期待される和であり、時間$O(n)$で計算できる。 ここでは、より弱い形式的制約、すなわち計画性に焦点を当てます。 理論的領域では、文が与えられたとき、その単語の一様ランダムな平面の置換を生成するために、平面の置換数または効率的なアルゴリズムが生成される。 また,平面配置における期待和と射影配置における期待和との関係を示す。 アプリケーション領域では、エッジ長さの合計の期待値を計算するために$o(n)$-timeアルゴリズムを導出する。 また,本研究を並列コーパスに適用し,依存性構造に対する形式的制約の強さが増すにつれて,実際の依存関係距離とランダムベースラインとのギャップが減少し,依存関係距離最小化効果の一部を形式的制約が吸収することが示唆された。 本研究では,ランダム平面線形化をベースラインとする依存性距離最小化に関する過去の研究を再現する方法を提案する。

関連論文リスト

• Statistical Advantages of Oblique Randomized Decision Trees and Forests [0.0]
  リッジ関数のフレキシブル次元縮小モデルクラスに対して一般化誤差と収束率を求める。 軸方向のモンドリアン木のリスクに対する低い境界は、これらの線形次元減少モデルに対してこれらの推定値が最適であることを示す。
  論文  参考訳（メタデータ） (2024-07-02T17:35:22Z)
• Tightness of prescriptive tree-based mixed-integer optimization formulations [2.538209532048867]
  本稿では,入力特徴ベクトルと学習した決定木の予測結果との関係をモデル化することに注力する。 従来よりも厳密な混合整数最適化法を提案する。
  論文  参考訳（メタデータ） (2023-02-28T16:44:10Z)
• The distribution of syntactic dependency distances [0.7614628596146599]
  我々は,構文的依存距離の実際の分布のキャラクタリゼーションに寄与する。 ブレークポイント後の確率の減衰を許容する新しい二重指数モデルを提案する。 2つの登録モデルが、私たちが検討した20言語の中で、最も可能性の高いモデルであることが分かりました。
  論文  参考訳（メタデータ） (2022-11-26T17:31:25Z)
• Near-optimal estimation of smooth transport maps with kernel sums-of-squares [81.02564078640275]
  滑らかな条件下では、2つの分布の間の正方形ワッサーシュタイン距離は、魅力的な統計的誤差上界で効率的に計算できる。 生成的モデリングのような応用への関心の対象は、基礎となる最適輸送写像である。 そこで本研究では,地図上の統計的誤差であるL2$が,既存のミニマックス下限値とほぼ一致し,スムーズな地図推定が可能となる最初のトラクタブルアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-12-03T13:45:36Z)
• Implicit Generative Copulas [0.0]
  我々は、暗黙的な生成ニューラルネットワークに基づく柔軟な、しかし概念的には単純な代替案を提案する。 ファイナンス、物理、画像生成の合成および実データに関する実験は、このアプローチの性能を実証している。
  論文  参考訳（メタデータ） (2021-09-29T17:05:30Z)
• Unfolding Projection-free SDP Relaxation of Binary Graph Classifier via GDPA Linearization [59.87663954467815]
  アルゴリズムの展開は、モデルベースのアルゴリズムの各イテレーションをニューラルネットワーク層として実装することにより、解釈可能で類似のニューラルネットワークアーキテクチャを生成する。 本稿では、Gershgorin disc perfect alignment (GDPA)と呼ばれる最近の線形代数定理を利用して、二進グラフの半定値プログラミング緩和(SDR)のためのプロジェクションフリーアルゴリズムをアンロールする。 実験結果から,我々の未学習ネットワークは純粋モデルベースグラフ分類器よりも優れ,純粋データ駆動ネットワークに匹敵する性能を示したが,パラメータははるかに少なかった。
  論文  参考訳（メタデータ） (2021-09-10T07:01:15Z)
• Linear-time calculation of the expected sum of edge lengths in random projective linearizations of trees [1.2944868613449219]
  構文的に関連付けられた単語間の距離の合計は、過去数十年間、ライムライトの中にあった。 言語に関する関連する定量的研究を行うために、様々なランダムベースラインが定義されている。 ここでは、文の単語のランダムな射影置換という、一般的なベースラインに焦点を当てる。
  論文  参考訳（メタデータ） (2021-07-07T15:11:53Z)
• A Parallelizable Lattice Rescoring Strategy with Neural Language Models [62.20538383769179]
  自動音声認識のためのニューラルネットワークモデル(LM)を用いた効率的な格子相関のための後部格子拡張アルゴリズムを提案する。 スイッチボードデータセットにおける実験により,提案手法が同等の認識性能を得た。 PyTorchで訓練されたニューラル LM をKaldi との格子再構成に簡単に統合することで、並列再描画法により柔軟性が向上する。
  論文  参考訳（メタデータ） (2021-03-08T21:23:12Z)
• Partition-based formulations for mixed-integer optimization of trained ReLU neural networks [66.88252321870085]
  本稿では,訓練されたReLUニューラルネットワークのための混合整数式について紹介する。 1つの極端な場合、入力毎に1つのパーティションがノードの凸殻、すなわち各ノードの最も厳密な可能な定式化を回復する。
  論文  参考訳（メタデータ） (2021-02-08T17:27:34Z)
• Convex Polytope Trees [57.56078843831244]
  コンベックスポリトープ木(CPT)は、決定境界の解釈可能な一般化によって決定木の系統を拡張するために提案される。 木構造が与えられたとき,木パラメータに対するCPTおよび拡張性のあるエンドツーエンドトレーニングアルゴリズムを効率的に構築する。
  論文  参考訳（メタデータ） (2020-10-21T19:38:57Z)
• A General Framework for Consistent Structured Prediction with Implicit Loss Embeddings [113.15416137912399]
  構造化予測のための理論的・アルゴリズム的な枠組みを提案し,解析する。 問題に対して適切な幾何を暗黙的に定義する、損失関数の大規模なクラスについて検討する。 出力空間を無限の濃度で扱うとき、推定子の適切な暗黙の定式化が重要であることが示される。
  論文  参考訳（メタデータ） (2020-02-13T10:30:04Z)

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

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