論文の概要: Learning Broadcast Protocols
- arxiv url: http://arxiv.org/abs/2306.14284v1
- Date: Sun, 25 Jun 2023 16:26:48 GMT
- ステータス: 処理完了
- システム内更新日: 2023-06-27 15:55:24.732262
- Title: Learning Broadcast Protocols
- Title（参考訳）: 放送プロトコルの学習
- Authors: Dana Fisman, Noa Izsak, Swen Jacobs
- Abstract要約: 任意の数のプロセスで分散システムを学習する問題に初めて注目する。
微細なBPと整合したサンプルを与えられた場合、正しいBPを推測できる学習アルゴリズムを提供する。
細かなBPのクラスは教えられるので、各BPに$mathcalS_B$という有限個の単語を関連付けることができる。
- 参考スコア（独自算出の注目度）: 3.4806267677524896
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The problem of learning a computational model from examples has been
receiving growing attention. Models of distributed systems are particularly
challenging since they encompass an added succinctness. While positive results
for learning some models of distributed systems have been obtained, so far the
considered models assume a fixed number of processes interact. In this work we
look for the first time (to the best of our knowledge) at the problem of
learning a distributed system with an arbitrary number of processes, assuming
only that there exists a cutoff. Specifically, we consider fine broadcast
protocols, these are broadcast protocols (BPs) with a finite cutoff and no
hidden states. We provide a learning algorithm that given a sample consistent
with a fine BP, can infer a correct BP, with the help of an SMT solver.
Moreover we show that the class of fine BPs is teachable, meaning that we can
associate a finite set of words $\mathcal{S}_B$ with each BP $B$ in the class
(a so-called characteristic set) so that the provided learning algorithm can
correctly infer a correct BP from any consistent sample subsuming
$\mathcal{S}_B$. On the negative size we show that (a) characteristic sets of
exponential size are unavoidable, (b) the consistency problem for fine BPs is
NP hard, and (c) fine BPs are not polynomially predictable.
- Abstract（参考訳）: 実例から計算モデルを学習する問題は注目されている。
分散システムのモデルは、簡潔さの追加を含むため、特に難しい。
分散システムのモデルを学ぶためのポジティブな結果が得られたが、これまで検討されたモデルは、一定の数のプロセスが相互作用していると仮定している。
この作業では、任意の数のプロセスで分散システムを学習する問題において、カットオフが存在することのみを前提として、初めて(私たちの知識を最大限に活用するために)探しています。
具体的には、細かなブロードキャストプロトコルを考慮し、これらは有限カットオフと隠蔽状態のないブロードキャストプロトコル(BP)である。
SMTソルバの助けを借りて,微細BPと整合したサンプルを正しいBPを推定できる学習アルゴリズムを提案する。
さらに、細かなBPのクラスが教えられることを示し、つまり、与えられた学習アルゴリズムが$\mathcal{S}_B$という一貫したサンプルから正しいBPを正しく推測できるように、クラス内の各BP$B$(いわゆる特徴集合)と有限個の単語の集合を関連付けることができる。
負のサイズの場合、
(a)指数サイズの特性集合は避けられない。
b)微細BPの整合性問題はNP困難であり、
(c)微細BPは多項式的に予測できない。
関連論文リスト
- Circular Belief Propagation for Approximate Probabilistic Inference [0.07282584715927627]
Belief Propagation (BP) は、確率分布を表すグラフのノード間でメッセージを渡す単純な確率的推論アルゴリズムである。
本稿では,BPの拡張であるCircular Belief Propagation (CBP)を提案する。
CBP が BP をはるかに上回り,従来提案したアルゴリズムと比較して優れた性能を示すバイナリ確率グラフを含む数値実験を行った。
論文 参考訳（メタデータ） (2024-03-17T15:59:39Z) - Probabilistic Contrastive Learning for Long-Tailed Visual Recognition [78.70453964041718]
細長い分布は、少数の少数派が限られた数のサンプルを含む実世界のデータにしばしば現れる。
近年の研究では、教師付きコントラスト学習がデータ不均衡を緩和する有望な可能性を示していることが明らかになっている。
本稿では,特徴空間の各クラスからのサンプルデータ分布を推定する確率論的コントラスト学習アルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-03-11T13:44:49Z) - Deep Attentive Belief Propagation: Integrating Reasoning and Learning
for Solving Constraint Optimization Problems [24.63675651321079]
BP(Breief Propagation)は、グラフィカルモデル上の様々な推論タスクのための重要なメッセージパッシングアルゴリズムである。
本研究では, DABP をスムーズなソリューションコストで自己教師付き学習する手法を提案する。
我々のモデルは最先端のベースラインを大きく上回る。
論文 参考訳（メタデータ） (2022-09-24T13:03:46Z) - Generalization of Neural Combinatorial Solvers Through the Lens of
Adversarial Robustness [68.97830259849086]
ほとんどのデータセットは単純なサブプロブレムのみをキャプチャし、おそらくは突発的な特徴に悩まされる。
本研究では, 局所的な一般化特性である対向ロバスト性について検討し, 厳密でモデル固有な例と突発的な特徴を明らかにする。
他のアプリケーションとは異なり、摂動モデルは知覚できないという主観的な概念に基づいて設計されているため、摂動モデルは効率的かつ健全である。
驚くべきことに、そのような摂動によって、十分に表現力のあるニューラルソルバは、教師あり学習で共通する正確さと悪質さのトレードオフの限界に悩まされない。
論文 参考訳（メタデータ） (2021-10-21T07:28:11Z) - Predictive Coding Can Do Exact Backpropagation on Convolutional and
Recurrent Neural Networks [40.51949948934705]
予測符号化ネットワーク(PCN)は、脳内の情報処理に影響を及ぼすモデルである。
BPは現代の機械学習において最も成功した学習方法と考えられている。
生物学的に妥当なアルゴリズムは複雑なアーキテクチャ上でBPの精度を正確に再現できることを示す。
論文 参考訳（メタデータ） (2021-03-05T14:57:01Z) - Belief Propagation Neural Networks [103.97004780313105]
信念伝播ニューラルネットワーク(BPNN)を紹介する。
BPNNは因子グラフ上で動作し、信念伝播(BP)を一般化する
BPNNはIsingモデル上で1.7倍高速に収束し、より厳密な境界を提供することを示す。
挑戦的なモデルカウント問題に関して、BPNNは最先端の手作り手法の100倍の速さを推定する。
論文 参考訳（メタデータ） (2020-07-01T07:39:51Z) - $\alpha$ Belief Propagation for Approximate Inference [16.258304175469917]
BP(Belief propagation)アルゴリズムは、グラフィカルモデルにおける推論のためのメッセージパッシング手法として広く用いられている。
局所化$alpha$-divergenceの最小化によって動機付けられた解釈可能な信念伝播アルゴリズムを導出する。
その結果、$alpha$-BPは標準BPを一般化することがわかった。
論文 参考訳（メタデータ） (2020-06-27T13:32:06Z) - Sample-Efficient Reinforcement Learning of Undercomplete POMDPs [91.40308354344505]
この研究は、これらの硬度障壁が、部分観測可能決定過程(POMDP)の豊かで興味深いサブクラスに対する効率的な強化学習を妨げないことを示している。
提案手法は, 観測回数が潜伏状態の数よりも大きく, 探索が学習に不可欠であり, 先行研究と区別できるような, エピソード有限不完全POMDPに対するサンプル効率アルゴリズムOOM-UCBを提案する。
論文 参考訳（メタデータ） (2020-06-22T17:58:54Z) - Breaking the Sample Size Barrier in Model-Based Reinforcement Learning
with a Generative Model [50.38446482252857]
本稿では、生成モデル(シミュレータ)へのアクセスを想定して、強化学習のサンプル効率について検討する。
最初に$gamma$-discounted infinite-horizon Markov decision process (MDPs) with state space $mathcalS$ and action space $mathcalA$を考える。
対象の精度を考慮すれば,モデルに基づく計画アルゴリズムが最小限のサンプルの複雑さを実現するのに十分であることを示す。
論文 参考訳（メタデータ） (2020-05-26T17:53:18Z) - Belief Propagation Reloaded: Learning BP-Layers for Labeling Problems [83.98774574197613]
最も単純な推論手法の1つとして、切り詰められた最大積のBelief伝播を取り上げ、それをディープラーニングモデルの適切なコンポーネントにするために必要となるものを加えます。
このBP-Layerは畳み込みニューラルネットワーク(CNN)の最終ブロックまたは中間ブロックとして使用できる
このモデルは様々な密集予測問題に適用可能であり、パラメータ効率が高く、ステレオ、光フロー、セマンティックセグメンテーションにおける堅牢な解を提供する。
論文 参考訳（メタデータ） (2020-03-13T13:11:35Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。