論文の概要: Learning Combinatorial Structures via Markov Random Fields with Sampling
through Lov\'asz Local Lemma
- arxiv url: http://arxiv.org/abs/2212.00296v1
- Date: Thu, 1 Dec 2022 06:06:25 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-02 15:12:22.088656
- Title: Learning Combinatorial Structures via Markov Random Fields with Sampling
through Lov\'asz Local Lemma
- Title(参考訳): Lov\'asz局所補題を用いたマルコフランダムフィールドによる組合せ構造学習
- Authors: Nan Jiang, Yi Gu, Yexiang Xue
- Abstract要約: Lov'asz Local Lemma (LLL) に基づくニューラルネットワーク NEural Lovasz Sampler (Nelson) を開発した。
制約付きマルコフランダム場モデル(MRF)の分布から制約を満たすサンプルを生成することを保証する。
また、制約付きMRF(Nelson-CD)上で、完全に微分可能なコントラスト分割に基づく学習フレームワークを提案する。
- 参考スコア(独自算出の注目度): 20.66120585984511
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Generative models for learning combinatorial structures have transformative
impacts in many applications. However, existing approaches fail to offer
efficient and accurate learning results. Because of the highly intractable
nature of the gradient estimation of the learning objective subject to
combinatorial constraints. Existing gradient estimation methods would easily
run into exponential time/memory space, or incur huge estimation errors due to
improper approximation. We develop NEural Lovasz Sampler (Nelson), a neural
network based on Lov\'asz Local Lemma (LLL). We show it guarantees to generate
samples satisfying combinatorial constraints from the distribution of the
constrained Markov Random Fields model (MRF) under certain conditions. We
further present a fully differentiable contrastive-divergence-based learning
framework on constrained MRF (Nelson-CD). Meanwhile, Nelson-CD being fully
differentiable allows us to take advantage of the parallel computing power of
GPUs, resulting in great efficiency. Experimental results on three real-world
combinatorial problems reveal that Nelson learns to generate 100% valid
structures. In comparison, baselines either time out on large-size data sets or
fail to generate valid structures, whereas Nelson scales much better with
problem size. In addition, Nelson outperforms baselines in various learning
metrics, such as log-likelihood and MAP scores.
- Abstract(参考訳): 組合せ構造を学習するための生成モデルは、多くの応用において変換的影響を持つ。
しかし、既存のアプローチは効率的で正確な学習結果を提供していない。
組合せ制約を受ける学習対象の勾配推定の非常に難解な性質のためである。
既存の勾配推定法は指数時間/メモリ空間に容易に適用でき、不適切な近似による巨大な推定誤差を生じさせる。
Lov\'asz Local Lemma (LLL) に基づくニューラルネットワークである NEural Lovasz Sampler (Nelson) を開発した。
制約付きマルコフ確率場モデル(mrf)の特定の条件下での分布から組合せ制約を満たすサンプルを生成することが保証される。
さらに,制約付きmrf(nelson-cd)を用いた完全微分可能なコントラスト・ダイバージェンスに基づく学習フレームワークを提案する。
一方、nelson-cdは完全に微分可能であり、gpuの並列計算能力を利用することができ、非常に効率が良い。
3つの実世界の組合せ問題の実験結果から、ネルソンは100%有効な構造を作り出すことを学んでいることが分かる。
対照的に、ベースラインは大規模なデータセットにタイムアウトするか、有効な構造を生成できないかのいずれかである。
さらに,log-likelihoodやmap scoreなど,さまざまな学習指標のベースラインを上回っている。
関連論文リスト
- Probabilistic Contrastive Learning for Long-Tailed Visual Recognition [78.70453964041718]
細長い分布は、少数の少数派が限られた数のサンプルを含む実世界のデータにしばしば現れる。
近年の研究では、教師付きコントラスト学習がデータ不均衡を緩和する有望な可能性を示していることが明らかになっている。
本稿では,特徴空間の各クラスからのサンプルデータ分布を推定する確率論的コントラスト学習アルゴリズムを提案する。
論文 参考訳(メタデータ) (2024-03-11T13:44:49Z) - Collaborative Learning with Different Labeling Functions [8.53926206853583]
我々は、$n$のデータ分布ごとに正確な分類器を学習することを目的とした、協調型PAC学習の亜種について研究する。
データ分布がより弱い実現可能性の仮定を満たす場合、サンプル効率の学習は依然として可能であることを示す。
論文 参考訳(メタデータ) (2024-02-16T04:32:22Z) - Pareto Frontiers in Neural Feature Learning: Data, Compute, Width, and
Luck [35.6883212537938]
オフラインスパースパリティ学習は,多層パーセプトロンの勾配に基づくトレーニングにおいて,統計的クエリの下限を許容する教師付き分類問題である。
理論上, 実験上, 疎初期化とネットワーク幅の増大がサンプル効率を著しく向上させることを示す。
また,合成スパースパリティタスクは,軸方向の特徴学習を必要とする現実的な問題のプロキシとして有用であることを示す。
論文 参考訳(メタデータ) (2023-09-07T15:52:48Z) - BatchFormer: Learning to Explore Sample Relationships for Robust
Representation Learning [93.38239238988719]
本稿では,各ミニバッチからサンプル関係を学習可能なディープニューラルネットワークを提案する。
BatchFormerは各ミニバッチのバッチ次元に適用され、トレーニング中のサンプル関係を暗黙的に探索する。
我々は10以上のデータセットに対して広範な実験を行い、提案手法は異なるデータ不足アプリケーションにおいて大幅な改善を実現する。
論文 参考訳(メタデータ) (2022-03-03T05:31:33Z) - Unrolling Particles: Unsupervised Learning of Sampling Distributions [102.72972137287728]
粒子フィルタリングは複素系の優れた非線形推定を計算するために用いられる。
粒子フィルタは様々なシナリオにおいて良好な推定値が得られることを示す。
論文 参考訳(メタデータ) (2021-10-06T16:58:34Z) - Fully differentiable model discovery [0.0]
ニューラルネットワークに基づくサロゲートとスパースベイズ学習を組み合わせたアプローチを提案する。
我々の研究は、PINNを様々なタイプのニューラルネットワークアーキテクチャに拡張し、ニューラルネットワークベースのサロゲートをベイズパラメータ推論のリッチフィールドに接続する。
論文 参考訳(メタデータ) (2021-06-09T08:11:23Z) - Network Classifiers Based on Social Learning [71.86764107527812]
空間と時間に対して独立に訓練された分類器を結合する新しい手法を提案する。
提案したアーキテクチャは、ラベルのないデータで時間とともに予測性能を改善することができる。
この戦略は高い確率で一貫した学習をもたらすことが示され、未訓練の分類器に対して頑健な構造が得られる。
論文 参考訳(メタデータ) (2020-10-23T11:18:20Z) - Random Vector Functional Link Networks for Function Approximation on
Manifolds [9.886853561672249]
ランダムな入力-隠蔽層重みとバイアスを持つ単一層ニューラルネットが実際に成功していることを示す。
さらに、このランダム化されたニューラルネットワークアーキテクチャをユークリッド空間の滑らかでコンパクトな部分多様体上の近似関数に適用する。
論文 参考訳(メタデータ) (2020-07-30T23:50:44Z) - Belief Propagation Reloaded: Learning BP-Layers for Labeling Problems [83.98774574197613]
最も単純な推論手法の1つとして、切り詰められた最大積のBelief伝播を取り上げ、それをディープラーニングモデルの適切なコンポーネントにするために必要となるものを加えます。
このBP-Layerは畳み込みニューラルネットワーク(CNN)の最終ブロックまたは中間ブロックとして使用できる
このモデルは様々な密集予測問題に適用可能であり、パラメータ効率が高く、ステレオ、光フロー、セマンティックセグメンテーションにおける堅牢な解を提供する。
論文 参考訳(メタデータ) (2020-03-13T13:11:35Z) - Embedding Propagation: Smoother Manifold for Few-Shot Classification [131.81692677836202]
本稿では, 組込み伝搬を非教師なし非パラメトリック正規化器として, 数ショット分類における多様体平滑化に用いることを提案する。
埋め込み伝播がより滑らかな埋め込み多様体を生み出すことを実証的に示す。
複数の半教師付き学習シナリオにおいて,埋め込み伝搬によりモデルの精度が最大16%向上することを示す。
論文 参考訳(メタデータ) (2020-03-09T13:51:09Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。