Fugu-MT 論文翻訳(概要): Learning Juntas under Markov Random Fields

論文の概要: 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)
Private estimation algorithms for stochastic block models and mixture models [63.07482515700984]
効率的なプライベート推定アルゴリズムを設計するための一般的なツール。最初の効率的な$(epsilon, delta)$-differentially private algorithm for both weak recovery and exact recovery。
論文参考訳（メタデータ） (2023-01-11T09:12:28Z)
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)
The Bayesian Learning Rule [14.141964578853262]
我々は、多くの機械学習アルゴリズムが、emphBayesian Learning Ruleと呼ばれる単一のアルゴリズムの特定の例であることを示した。この規則はベイズ原理から派生したもので、最適化、ディープラーニング、グラフィカルモデルといった分野から幅広いアルゴリズムが得られる。
論文参考訳（メタデータ） (2021-07-09T17:28:55Z)
A Sharp Analysis of Model-based Reinforcement Learning with Self-Play [49.88233710867315]
マルチエージェントマルコフゲームのためのモデルベースセルフプレイアルゴリズムのシャープな解析を行う。我々は,2プレイヤーゼロサムマルコフゲームのための最適化ナッシュ値イテレーション(Nash-VI)を設計する。我々はさらに、ゼロサムマルコフゲームに対する証明可能な効率的なタスク認識アルゴリズムの設計に我々の分析を適用した。
論文参考訳（メタデータ） (2020-10-04T15:27:39Z)
Efficient Computation of Expectations under Spanning Tree Distributions [67.71280539312536]
本稿では,エッジファクター,非プロジェクティブ・スパンニングツリーモデルにおいて,一階期待と二階期待の重要なケースに対する統一アルゴリズムを提案する。我々のアルゴリズムは勾配と期待の基本的な関係を利用しており、効率的なアルゴリズムを導出することができる。
論文参考訳（メタデータ） (2020-08-29T14:58:26Z)
Meta-learning with Stochastic Linear Bandits [120.43000970418939]
我々は、よく知られたOFULアルゴリズムの正規化バージョンを実装するバンディットアルゴリズムのクラスを考える。我々は,タスク数の増加とタスク分散の分散が小さくなると,タスクを個別に学習する上で,我々の戦略が大きな優位性を持つことを理論的および実験的に示す。
論文参考訳（メタデータ） (2020-05-18T08:41:39Z)
Learning Gaussian Graphical Models via Multiplicative Weights [54.252053139374205]
乗算重み更新法に基づいて,Klivans と Meka のアルゴリズムを適用した。アルゴリズムは、文献の他のものと質的に類似したサンプル複雑性境界を楽しみます。ランタイムが低い$O(mp2)$で、$m$サンプルと$p$ノードの場合には、簡単にオンライン形式で実装できる。
論文参考訳（メタデータ） (2020-02-20T10:50:58Z)

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