論文の概要: Robust Estimation of Tree Structured Markov Random Fields
- arxiv url: http://arxiv.org/abs/2102.08554v1
- Date: Wed, 17 Feb 2021 03:47:26 GMT
- ステータス: 処理完了
- システム内更新日: 2021-02-18 18:03:36.608299
- Title: Robust Estimation of Tree Structured Markov Random Fields
- Title（参考訳）: 木構造マルコフ確率場のロバスト推定
- Authors: Ashish Katiyar, Soumya Basu, Vatsal Shah, Constantine Caramanis
- Abstract要約: 木構造マルコフ確率場(MRF)を未知の雑音で観測した場合に共通の支持を持つ離散確率変数で学習する問題について検討する。
一般的なノイズモデルでは、基礎となる木の構造は、葉のノードのそれぞれが親や兄弟と区別できない同値クラスまでしか回復できず、葉のクラスターを形成することが示されています。
葉クラスタの回復性に必要かつ十分な条件を導出することにより、回収可能性の正確な評価を行う。
- 参考スコア（独自算出の注目度）: 25.467380816216824
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study the problem of learning tree-structured Markov random fields (MRF)
on discrete random variables with common support when the observations are
corrupted by unknown noise. As the presence of noise in the observations
obfuscates the original tree structure, the extent of recoverability of the
tree-structured MRFs under noisy observations is brought into question.
We show that in a general noise model, the underlying tree structure can be
recovered only up to an equivalence class where each of the leaf nodes is
indistinguishable from its parent and siblings, forming a leaf cluster. As the
indistinguishability arises due to contrived noise models, we study the natural
k-ary symmetric channel noise model where the value of each node is changed to
a uniform value in the support with an unequal and unknown probability. Here,
the answer becomes much more nuanced. We show that with a support size of 2,
and the binary symmetric channel noise model, the leaf clusters remain
indistinguishable. From support size 3 and up, the recoverability of a leaf
cluster is dictated by the joint probability mass function of the nodes within
it. We provide a precise characterization of recoverability by deriving a
necessary and sufficient condition for the recoverability of a leaf cluster. We
provide an algorithm that recovers the tree if this condition is satisfied, and
recovers the tree up to the leaf clusters failing this condition.
- Abstract（参考訳）: 木構造マルコフ確率場(MRF)を未知の雑音で観測した場合に共通の支持を持つ離散確率変数で学習する問題について検討する。
観測におけるノイズの存在が本来の木構造を難解にするため、ノイズ観測時の木構造mcfの回復可能性の程度に疑問が持たれる。
一般的なノイズモデルでは、基礎となる木の構造は、葉のノードのそれぞれが親や兄弟と区別できない同値クラスまでしか回復できず、葉のクラスターを形成することが示されています。
コントリブドノイズモデルによる識別不能性が生じると、各ノードの値が不平等で未知の確率を持つ支持部で一様値に変化する自然k-ary対称チャネルノイズモデルが研究される。
ここで、答えはもっと微妙なものになる。
2 の支持サイズと二進対称チャネル雑音モデルにより,葉のクラスターは識別不能であることを示す。
支持サイズ3以上から、葉クラスタの回復可能性は、その中のノードのジョイント確率質量関数によって決定される。
葉クラスタの回復性に必要かつ十分な条件を導出することにより、回収可能性の正確な評価を行う。
この条件が満たされると木を回復するアルゴリズムを提供し、この条件に失敗した葉のクラスタまで木を回復する。
関連論文リスト
- Identifying General Mechanism Shifts in Linear Causal Representations [58.6238439611389]
我々は,未知の潜在因子の線形混合を観測する線形因果表現学習環境について考察する。
近年の研究では、潜伏要因の復元や、それに基づく構造因果モデルの構築が可能であることが示されている。
非常に穏やかな標準仮定の下では、シフトしたノードの集合を識別することが可能である。
論文 参考訳（メタデータ） (2024-10-31T15:56:50Z) - Probabilistic Tree-of-thought Reasoning for Answering
Knowledge-intensive Complex Questions [93.40614719648386]
大規模言語モデル(LLM)は、知識集約的な複雑な質問にチェーン・オブ・シント(CoT)推論で答えることができる。
最近の研究は、CoT推論を強化するための外部知識の回収に向けられている。
確率的ツリー・オブ・シント推論(ProbTree)という新しいアプローチを提案する。
論文 参考訳（メタデータ） (2023-11-23T12:52:37Z) - Hierarchical clustering with dot products recovers hidden tree structure [53.68551192799585]
本稿では,階層構造の回復に着目した凝集クラスタリングアルゴリズムの新しい視点を提案する。
クラスタを最大平均点積でマージし、例えば最小距離やクラスタ内分散でマージしないような、標準的なアルゴリズムの単純な変種を推奨する。
このアルゴリズムにより得られた木は、汎用確率的グラフィカルモデルの下で、データ中の生成的階層構造をボナフェイド推定することを示した。
論文 参考訳（メタデータ） (2023-05-24T11:05:12Z) - 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) - Exact Recovery in the General Hypergraph Stochastic Block Model [92.28929858529679]
本稿では,d-uniform hypergraph block model(d-HSBM)の正確な回復の基本的な限界について検討する。
精度の高いしきい値が存在し、正確な回復がしきい値の上に達成でき、その下には不可能であることを示す。
論文 参考訳（メタデータ） (2021-05-11T03:39:08Z) - Spectral Top-Down Recovery of Latent Tree Models [13.681975313065477]
スペクトルトップダウン・リカバリ (STDR) は、大きな潜在木モデルを推定するための分割・コンカレントアプローチである。
STDRの分割ステップは非ランダムです。
代わりに、観測されたノードに関連する適切なラプラシア行列のFiedlerベクトルに基づいている。
私達はSTDRが統計的に一貫性があることを証明し、高い確率で木を正確に回復するために必要なサンプルの数を縛ります。
論文 参考訳（メタデータ） (2021-02-26T02:47:42Z) - Robust estimation of tree structured models [0.0]
ノイズの多い二分データから、可能な木の小さな等価クラスまで、木を復元できることが示される。
また、Chow-Liuアルゴリズムがノイズデータから根本木を継続的に学習する際の特徴付けも提供する。
論文 参考訳（メタデータ） (2021-02-10T14:58:40Z) - 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) - Robust Estimation of Tree Structured Ising Models [20.224160348675422]
我々は、異なる確率変数の符号が、おそらく不等で未知の確率で独立に反転するときに、イジングモデルを学習するタスクを考える。
しかし, この不同一性は, 葉ノードが近傍と位置を交換して形成する小さな同値類に限られる。
論文 参考訳（メタデータ） (2020-06-10T01:32:45Z) - Spectral neighbor joining for reconstruction of latent tree models [5.229354894035374]
我々は,潜在木図形モデルの構造を復元する新しい手法であるSpectral Neighbor Joiningを開発した。
我々はSNJが一貫したものであることを証明し、推定された類似性行列から木回復を正すのに十分な条件を導出する。
SNJは,他の再建法と比較して,多数の葉や長い縁を持つ樹木を正確に復元するために,サンプルを少なくする。
論文 参考訳（メタデータ） (2020-02-28T05:13:08Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。