論文の概要: Learning Juntas under Markov Random Fields

• arxiv url: http://arxiv.org/abs/2506.00764v1
• Date: Sun, 01 Jun 2025 00:43:46 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-06-05 01:42:09.220176
• Title: Learning Juntas under Markov Random Fields
• Title（参考訳）: マルコフ確率場下でのユンタの学習
• Authors: Gautam Chandrasekaran, Adam Klivans,
• Abstract要約: 我々はマルコフランダム場(MRFs)に関して、$O(log n)$ juntasをリアルタイムで学習するアルゴリズムを提供する。 これは、非方向性のグラフィカルモデルの構造を学習するアルゴリズムが、教師あり学習のための証明可能なアルゴリズムをもたらす最初の例である。
• 参考スコア（独自算出の注目度）: 7.2963746224601085
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We give an algorithm for learning $O(\log n)$ juntas in polynomial-time with respect to Markov Random Fields (MRFs) in a smoothed analysis framework where only the external field has been randomly perturbed. This is a broad generalization of the work of Kalai and Teng, who gave an algorithm that succeeded with respect to smoothed product distributions (i.e., MRFs whose dependency graph has no edges). Our algorithm has two phases: (1) an unsupervised structure learning phase and (2) a greedy supervised learning algorithm. This is the first example where algorithms for learning the structure of an undirected graphical model lead to provably efficient algorithms for supervised learning.
• Abstract（参考訳）: 我々は,外部フィールドのみをランダムに摂動させた滑らかな解析フレームワークにおいて,マルコフ確率場(MRF)に対して多項式時間で$O(\log n)$ juntasを学習するアルゴリズムを提案する。 これはカライとテンの業績の広範な一般化であり、彼は滑らかな積分布(すなわち、依存グラフが辺を持たない MRF )に関して成功したアルゴリズムを与えた。 本アルゴリズムは,(1)教師なし構造学習フェーズと(2)厳密な教師付き学習アルゴリズムの2つのフェーズを有する。 これは、非方向性のグラフィカルモデルの構造を学習するアルゴリズムが、教師あり学習のための証明可能なアルゴリズムをもたらす最初の例である。

関連論文リスト

• Learning Arithmetic Formulas in the Presence of Noise: A General Framework and Applications to Unsupervised Learning [4.10375234787249]
  教師なし学習問題に対する効率的なアルゴリズム設計のための枠組みを提案する。 我々のフレームワークは,雑音の存在下で演算回路を学習するメタアルゴリズムに基づいている。
  論文  参考訳（メタデータ） (2023-11-13T12:26:25Z)
• On Universally Optimal Algorithms for A/B Testing [49.429419538826444]
  ベルヌーイ報奨を伴う多腕バンディットにおける固定予算によるベストアーム識別の問題について検討する。 A/Bテスト問題としても知られる2つのアームの問題に対して,各アームを等しくサンプリングするアルゴリズムが存在しないことを証明した。
  論文  参考訳（メタデータ） (2023-08-23T08:38:53Z)
• Differentially-Private Hierarchical Clustering with Provable Approximation Guarantees [79.59010418610625]
  階層クラスタリングのための微分プライベート近似アルゴリズムについて検討する。 例えば、$epsilon$-DPアルゴリズムは入力データセットに対して$O(|V|2/epsilon)$-additiveエラーを示さなければならない。 本稿では,ブロックを正確に復元する1+o(1)$近似アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-01-31T19:14:30Z)
• Structure learning in polynomial time: Greedy algorithms, Bregman information, and exponential families [12.936601424755944]
  DAGを学習するための一般的なグリーディスコアに基づくアルゴリズムについて検討する。 DAGモデルを学習するための最近のアルゴリズム時間アルゴリズムが,このアルゴリズムの特別な例であることを示す。 この観測は、ブレグマン発散と指数族との双対性に基づく新しいスコア関数と最適条件を示唆する。
  論文  参考訳（メタデータ） (2021-10-10T06:37:51Z)
• A Clustering and Demotion Based Algorithm for Inductive Learning of Default Theories [4.640835690336653]
  正および負の例から非単調論理プログラムを誘導するクラスタリングとデモーションに基づくアルゴリズムKmeans-FOLDを提案する。 本アルゴリズムは,FOLDアルゴリズムと比較して,より簡潔な論理プログラムを生成する。 UCIデータセットの実験では、K-Meansクラスタリングと当社のデモーション戦略の組み合わせによって、複数の肯定的な例のクラスタを持つデータセットに対して、大幅な改善が達成されている。
  論文  参考訳（メタデータ） (2021-09-26T14:50:18Z)
• Learning Gaussian Graphical Models via Multiplicative Weights [54.252053139374205]
  乗算重み更新法に基づいて,Klivans と Meka のアルゴリズムを適用した。 アルゴリズムは、文献の他のものと質的に類似したサンプル複雑性境界を楽しみます。 ランタイムが低い$O(mp2)$で、$m$サンプルと$p$ノードの場合には、簡単にオンライン形式で実装できる。
  論文  参考訳（メタデータ） (2020-02-20T10:50:58Z)

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

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