論文の概要: Testing properties of trees in graphical models with covariance queries

• arxiv url: http://arxiv.org/abs/2605.15996v1
• Date: Fri, 15 May 2026 14:26:19 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-05-18 21:22:26.317285
• Title: Testing properties of trees in graphical models with covariance queries
• Title（参考訳）: 共分散クエリを用いたグラフィカルモデルにおける木の試験特性
• Authors: Sofiya Burova, Francisco Calvillo, Gábor Lugosi, Piotr Zwiernik,
• Abstract要約: 基礎となるグラフが木である場合について検討する。 木全体の再構築にはコストがかかるかもしれないが、特定のグローバルな構造特性を効率的にテストすることができる。
• 参考スコア（独自算出の注目度）: 2.8582274879786684
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We consider the problem of testing properties of graphs underlying high-dimensional graphical models. We adopt the model of covariance queries introduced by Lugosi, Truszkowski, Velona, and Zwiernik (2021). We study the case when the underlying graph is a tree. The main results of the paper show that, while reconstructing the entire tree may be costly, certain global structural properties can be tested efficiently. In particular, we design randomized tests for global structural properties that use a sub-quadratic number of queries. We develop testing procedures for several fundamental properties, including the number of leaves, the maximum degree, the typical distance, and the diameter of the tree. For each property, we obtain explicit query complexity bounds that depend on the target threshold and tolerance parameters.
• Abstract（参考訳）: 本研究では,高次元グラフィカルモデルに基づくグラフの特性試験の問題点について考察する。 我々はLugosi, Truszkowski, Velona, Zwiernik (2021)によって導入された共分散クエリのモデルを採用する。 基礎となるグラフが木である場合について検討する。 本研究の主な成果は, 木全体の再構築には費用がかかるが, 一定のグローバルな構造特性を効率的に検証できることである。 特に、サブクアドラティックなクエリ数を用いたグローバルな構造特性のランダム化試験を設計する。 葉の数, 最大度, 典型的な距離, 木の直径など, いくつかの基本特性の試験方法を開発した。 各特性に対して、ターゲットしきい値と許容パラメータに依存する明示的なクエリ複雑性境界を得る。

関連論文リスト

• Learning Order Forest for Qualitative-Attribute Data Clustering [52.612779710298526]
  本稿では,属性内定性値間の局所的な順序関係を柔軟に表現する木のような距離構造を探索する。 より適切な木構造とクラスタを反復的に獲得するために,共同学習機構を提案する。 実験により、共同学習は森林をクラスタリングタスクに適応させ、正確な結果を得ることを示した。
  論文  参考訳（メタデータ） (2026-03-03T07:49:50Z)
• Efficient Testing Implies Structured Symmetry [4.110863713353763]
  少ないサンプルから効率的に検証できる性質と、構造化対称性を持つ性質の同値性を示す。 この結果は任意の領域上での高エントロピー分布試験に一般化される。
  論文  参考訳（メタデータ） (2025-11-05T17:10:10Z)
• Graph-based Complexity for Causal Effect by Empirical Plug-in [56.14597641617531]
  本稿では、因果効果クエリに対する経験的プラグイン推定の計算複雑性に焦点を当てる。 計算は、推定値のハイパーグラフに依存するため、データサイズにおいて、潜在的に線形な時間で効率的に行うことができることを示す。
  論文  参考訳（メタデータ） (2024-11-15T07:42:01Z)
• Individualized and Global Feature Attributions for Gradient Boosted Trees in the Presence of $\ell_2$ Regularization [0.0]
  本稿では,プレデコン(PreDecomp)を提案する。プレデコン(PreDecomp,PreDecomp,PreDecomp)は,正規化を$ell$で訓練した場合に,増木に対する新規な個別化特徴属性である。 また、各ツリーのアウトサンプルデータに個々の特徴属性とラベルの内積で定義される、偏りのないグローバルな特徴属性のファミリーであるTreeInnerを提案する。
  論文  参考訳（メタデータ） (2022-11-08T17:56:22Z)
• 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)
• Large Scale Prediction with Decision Trees [9.917147243076645]
  本稿では,分類・回帰木(CART)とC4.5手法を用いて構築した決定木が,回帰・分類タスクに一貫性があることを示す。 この分析における重要なステップは、不平等の確立であり、不特定モデルの適合性と複雑性のトレードオフを正確に評価することができる。
  論文  参考訳（メタデータ） (2021-04-28T16:59:03Z)
• 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)
• Linguistically Driven Graph Capsule Network for Visual Question Reasoning [153.76012414126643]
  我々は「言語的に駆動されるグラフカプセルネットワーク」と呼ばれる階層的構成推論モデルを提案する。 具体的には,各カプセルを最下層に結合させ,元の質問に1つの単語を埋め込んだ言語的埋め込みを視覚的証拠で橋渡しする。 CLEVRデータセット、CLEVR合成生成テスト、およびFinalQAデータセットの実験は、我々のエンドツーエンドモデルの有効性と構成一般化能力を示す。
  論文  参考訳（メタデータ） (2020-03-23T03:34:25Z)

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

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