論文の概要: Linear-time calculation of the expected sum of edge lengths in random
projective linearizations of trees
- arxiv url: http://arxiv.org/abs/2107.03277v1
- Date: Wed, 7 Jul 2021 15:11:53 GMT
- ステータス: 処理完了
- システム内更新日: 2021-07-08 13:59:59.093439
- Title: Linear-time calculation of the expected sum of edge lengths in random
projective linearizations of trees
- Title（参考訳）: 木のランダム射影線形化における辺長の期待和の線形時間計算
- Authors: Llu\'is Alemany-Puig and Ramon Ferrer-i-Cancho
- Abstract要約: 構文的に関連付けられた単語間の距離の合計は、過去数十年間、ライムライトの中にあった。
言語に関する関連する定量的研究を行うために、様々なランダムベースラインが定義されている。
ここでは、文の単語のランダムな射影置換という、一般的なベースラインに焦点を当てる。
- 参考スコア（独自算出の注目度）: 1.2944868613449219
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The syntactic structure of a sentence is often represented using syntactic
dependency trees. The sum of the distances between syntactically related words
has been in the limelight for the past decades. Research on dependency
distances led to the formulation of the principle of dependency distance
minimization whereby words in sentences are ordered so as to minimize that sum.
Numerous random baselines have been defined to carry out related quantitative
studies on languages. The simplest random baseline is the expected value of the
sum in unconstrained random permutations of the words in the sentence, namely
when all the shufflings of the words of a sentence are allowed and equally
likely. Here we focus on a popular baseline: random projective permutations of
the words of the sentence, that is, permutations where the syntactic dependency
structure is projective, a formal constraint that sentences satisfy often in
languages. Thus far, the expectation of the sum of dependency distances in
random projective shufflings of a sentence has been estimated approximately
with a Monte Carlo procedure whose cost is of the order of $Zn$, where $n$ is
the number of words of the sentence and $Z$ is the number of samples; the
larger $Z$, the lower the error of the estimation but the larger the time cost.
Here we present formulae to compute that expectation without error in time of
the order of $n$. Furthermore, we show that star trees maximize it, and devise
a dynamic programming algorithm to retrieve the trees that minimize it.
- Abstract（参考訳）: 文の構文構造は、しばしば構文依存木を用いて表現される。
構文的に関連した単語間の距離の合計は、過去数十年間、軽視されてきた。
依存距離の研究は、その和を最小化するために文中の単語を順序づける依存距離最小化の原理の定式化につながった。
言語に関する関連する定量的研究を行うために、多数のランダムベースラインが定義されている。
最も単純なランダムベースラインは、文中の単語の非制約ランダムな置換における和の期待値である。
ここでは、一般的なベースラインである、文の単語のランダムな投影的置換、すなわち構文依存構造が射影的である置換、文が言語でしばしば満足する形式的制約に焦点を当てる。
これまでのところ、文のランダムな射影シャッフルにおける依存関係距離の総和は、コストがZn$のモンテカルロ手順で推定されており、$n$は文の語数であり、$Z$はサンプル数である。
ここでは、その期待値を$n$のオーダー時にエラーなく計算する式を示す。
さらに、スターツリーが最大化できることを示し、それを最小化する木を検索するための動的プログラミングアルゴリズムを考案する。
関連論文リスト
- Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic
Shortest Path [80.60592344361073]
線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。
エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。
既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
論文 参考訳（メタデータ） (2024-02-14T07:52:00Z) - Revisiting the Optimality of Word Lengths [92.70590105707639]
通信コストは、さまざまな方法で運用できる。
Zipf (1935) は、単語形式は発話のコミュニケーションコストを最小限に抑えるために最適化されていると仮定した。
論文 参考訳（メタデータ） (2023-12-06T20:41:47Z) - Variance-Aware Regret Bounds for Stochastic Contextual Dueling Bandits [53.281230333364505]
本稿では, 一般化線形モデル(GLM)から, デュエルアームのバイナリ比較を生成するコンテキストデュエルバンド問題について検討する。
本稿では,SupLinUCB型アルゴリズムを提案する。このアルゴリズムは,計算効率と分散を意識したリセットバウンド$tilde Obig(dsqrtsum_t=1Tsigma_t2 + dbig)$を提案する。
我々の後悔は、比較が決定論的である場合の直感的な期待と自然に一致し、アルゴリズムは$tilde O(d)$ regretにのみ悩まされる。
論文 参考訳（メタデータ） (2023-10-02T08:15:52Z) - The distribution of syntactic dependency distances [0.7614628596146599]
我々は,構文的依存距離の実際の分布のキャラクタリゼーションに寄与する。
ブレークポイント後の確率の減衰を許容する新しい二重指数モデルを提案する。
2つの登録モデルが、私たちが検討した20言語の中で、最も可能性の高いモデルであることが分かりました。
論文 参考訳（メタデータ） (2022-11-26T17:31:25Z) - Truncation Sampling as Language Model Desmoothing [115.28983143361681]
ニューラルネットワークモデルからのテキストの長いサンプルは、品質が劣る可能性がある。
トランケーションサンプリングアルゴリズムは、各ステップでいくつかの単語の確率を0に設定する。
本稿では,単語をエントロピーに依存した確率閾値以下に切り詰める$eta$-samplingを導入する。
論文 参考訳（メタデータ） (2022-10-27T05:52:35Z) - The expected sum of edge lengths in planar linearizations of trees.
Theory and applications [0.16317061277456998]
平面配置における期待和と射影配置における期待和の関係を示す。
エッジ長の和の期待値を計算するために,$O(n)$-timeアルゴリズムを導出する。
本研究は, 並列コーパスに適用し, 依存関係構造に対する公式制約の強度が増大するにつれて, 実際の依存性距離とランダムベースラインとのギャップが減少することを示した。
論文 参考訳（メタデータ） (2022-07-12T14:35:07Z) - Shallow decision trees for explainable $k$-means clustering [1.2891210250935146]
決定木内の葉の深さに関連する指標を考慮に入れた効率的なアルゴリズムを提案する。
16個のデータセットの実験において,本アルゴリズムは決定木クラスタリングアルゴリズムよりも優れた結果が得られる。
論文 参考訳（メタデータ） (2021-12-29T18:22:28Z) - Dependency distance minimization predicts compression [1.2944868613449219]
依存性距離最小化(DDm)は、単語順序の確立された原理である。
これは、原理と他の原理とを結び付けるためであり、一階予測のように原則と宣言を結び付けるためである。
最近導入されたスコアは、広く使われている依存性距離の和に関して、数学的、統計的に多くの利点がある。
論文 参考訳（メタデータ） (2021-09-18T10:53:39Z) - List-Decodable Mean Estimation in Nearly-PCA Time [50.79691056481693]
高次元におけるリストデコタブル平均推定の基本的な課題について検討する。
我々のアルゴリズムは、すべての$k = O(sqrtd) cup Omega(d)$に対して$widetildeO(ndk)$で実行されます。
我々のアルゴリズムの変種は、すべての$k$に対してランタイム$widetildeO(ndk)$を持ち、リカバリ保証の$O(sqrtlog k)$ Factorを犠牲にしている。
論文 参考訳（メタデータ） (2020-11-19T17:21:37Z) - Estimating decision tree learnability with polylogarithmic sample
complexity [16.832966312395126]
トップダウン決定木学習は,高効率な学習可能性推定に有効であることを示す。
決定木仮説のラベル $T(xstar$)$ が多対数的に多くのラベル付き例で計算可能であることを示す。
論文 参考訳（メタデータ） (2020-11-03T09:26:27Z) - Stochastic Linear Bandits Robust to Adversarial Attacks [117.665995707568]
我々はロバスト位相除去アルゴリズムの2つの変種を提供し、その1つは$C$を知っており、もう1つはそうでない。
いずれの変種も、倒壊しない場合には、それぞれ$C = 0$ となり、それぞれ追加の加法項が生じる。
文脈的設定では、単純な欲求的アルゴリズムは、明示的な探索を行わず、C$を知らないにもかかわらず、ほぼ最適加法的後悔項で証明可能な堅牢性を示す。
論文 参考訳（メタデータ） (2020-07-07T09:00:57Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。