論文の概要: Adversarially-Robust Inference on Trees via Belief Propagation
- arxiv url: http://arxiv.org/abs/2404.00768v1
- Date: Sun, 31 Mar 2024 18:47:57 GMT
- ステータス: 処理完了
- システム内更新日: 2024-04-04 01:51:24.319644
- Title: Adversarially-Robust Inference on Trees via Belief Propagation
- Title（参考訳）: 確率伝搬による樹木の逆回転推論
- Authors: Samuel B. Hopkins, Anqi Li,
- Abstract要約: 木構造図形モデルにおける悪意ある敵の存在下での後方推論の問題について検討する。
まず,選択した葉の逆ポリノミアルな割合を汚す悪意のある敵が,この推論を不可能にする,という民間伝承の信念を確認した。
- 参考スコア（独自算出の注目度）: 13.354859329580023
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We introduce and study the problem of posterior inference on tree-structured graphical models in the presence of a malicious adversary who can corrupt some observed nodes. In the well-studied broadcasting on trees model, corresponding to the ferromagnetic Ising model on a $d$-regular tree with zero external field, when a natural signal-to-noise ratio exceeds one (the celebrated Kesten-Stigum threshold), the posterior distribution of the root given the leaves is bounded away from $\mathrm{Ber}(1/2)$, and carries nontrivial information about the sign of the root. This posterior distribution can be computed exactly via dynamic programming, also known as belief propagation. We first confirm a folklore belief that a malicious adversary who can corrupt an inverse-polynomial fraction of the leaves of their choosing makes this inference impossible. Our main result is that accurate posterior inference about the root vertex given the leaves is possible when the adversary is constrained to make corruptions at a $\rho$-fraction of randomly-chosen leaf vertices, so long as the signal-to-noise ratio exceeds $O(\log d)$ and $\rho \leq c \varepsilon$ for some universal $c > 0$. Since inference becomes information-theoretically impossible when $\rho \gg \varepsilon$, this amounts to an information-theoretically optimal fraction of corruptions, up to a constant multiplicative factor. Furthermore, we show that the canonical belief propagation algorithm performs this inference.
- Abstract（参考訳）: 本研究では, 木構造図形モデルにおいて, 観測ノードを破損させる悪意のある敵の存在下での後方推論の問題を紹介し, 検討する。
外部磁場がゼロの$d$正則木上の強磁性イジングモデルに対応する木モデル上のよく研究された放送では、自然信号対雑音比が1(ケステン・スティグム閾値)を超えると、葉が与えられた根の後方分布が$\mathrm{Ber}(1/2)$から切り離され、根の符号に関する非自明な情報を運ぶ。
この後続分布は動的プログラミングによって正確に計算することができる。
まず,選択した葉の逆ポリノミアルな割合を汚す悪意のある敵が,この推論を不可能にする,という民間伝承の信念を確認した。
我々の主な結果は、信号対雑音比が$O(\log d)$ と $\rho \leq c \varepsilon$ を超える限り、敵がランダムな葉の頂点の$$\rho$-fraction で汚職をするように制約された場合に、葉を与えられた根頂点に関する正確な後部推論が可能であることである。
推論が$\rho \gg \varepsilon$の場合に情報理論上不可能になるので、これは情報理論上最適な汚職の分数であり、一定の乗法係数になる。
さらに、標準信念伝播アルゴリズムがこの推論を行うことを示す。
関連論文リスト
- Identifying General Mechanism Shifts in Linear Causal Representations [58.6238439611389]
我々は,未知の潜在因子の線形混合を観測する線形因果表現学習環境について考察する。
近年の研究では、潜伏要因の復元や、それに基づく構造因果モデルの構築が可能であることが示されている。
非常に穏やかな標準仮定の下では、シフトしたノードの集合を識別することが可能である。
論文 参考訳（メタデータ） (2024-10-31T15:56:50Z) - Impossibility of latent inner product recovery via rate distortion [1.1510009152620668]
d gtrsim n h(p)$ ここで、$h(p)$ が二元エントロピー函数であれば、内部積を回復することは不可能である。
この証明は、確立された速度歪曲理論に従う。
論文 参考訳（メタデータ） (2024-07-16T17:23:29Z) - Information-Theoretic Thresholds for Planted Dense Cycles [52.076657911275525]
本研究では,社会科学や生物科学においてユビキタスな小世界ネットワークのランダムグラフモデルについて検討する。
植え込み高密度サイクルの検出と回復の両面において、情報理論の閾値を$n$, $tau$、エッジワイド信号対雑音比$lambda$で特徴づける。
論文 参考訳（メタデータ） (2024-02-01T03:39:01Z) - Probabilistic Tree-of-thought Reasoning for Answering
Knowledge-intensive Complex Questions [93.40614719648386]
大規模言語モデル(LLM)は、知識集約的な複雑な質問にチェーン・オブ・シント(CoT)推論で答えることができる。
最近の研究は、CoT推論を強化するための外部知識の回収に向けられている。
確率的ツリー・オブ・シント推論(ProbTree)という新しいアプローチを提案する。
論文 参考訳（メタデータ） (2023-11-23T12:52:37Z) - Probability Distribution on Rooted Trees [1.3955252961896318]
根付き木の階層的表現能力は、データ圧縮、画像処理、機械学習など、さまざまな領域の統計モデルを表現するために応用される。
これを解決するための統一的なアプローチはベイズ的アプローチであり、ルート木をランダム変数とみなし、選択されたモデルや新しいデータポイントの予測値に対して直接損失関数を仮定することができる。
本稿では,最大子ノード数と最大深さのみを固定したルート木に対して,一般化された確率分布を提案する。
論文 参考訳（メタデータ） (2022-01-24T05:13:58Z) - 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) - Probability Distribution on Full Rooted Trees [2.1506382989223782]
データ圧縮、画像処理、機械学習では、完全なルートツリーはランダム変数ではない。
これを解決する方法の1つは、全根木上の事前分布を仮定することである。
本稿では,全根樹群における確率分布を提案する。
論文 参考訳（メタデータ） (2021-09-27T06:51:35Z) - 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) - Causal Expectation-Maximisation [70.45873402967297]
ポリツリーグラフを特徴とするモデルにおいても因果推論はNPハードであることを示す。
我々は因果EMアルゴリズムを導入し、分類的表現変数のデータから潜伏変数の不確かさを再構築する。
我々は、反事実境界が構造方程式の知識なしにしばしば計算できるというトレンドのアイデアには、目立たずの制限があるように思える。
論文 参考訳（メタデータ） (2020-11-04T10:25:13Z) - Fairness constraints can help exact inference in structured prediction [37.76221231305701]
直交連結グラフ$G$と2進ラベルの真のベクトルを持つ生成モデルについて検討する。
フェアネスとモデル性能の間の既知のトレードオフとは対照的に、フェアネス制約の追加は正確なリカバリの確率を向上させる。
論文 参考訳（メタデータ） (2020-07-01T04:11:29Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。