Belief propagation (original) (raw)
Алгоритм распространения доверия (англ. belief propagation, trust propagation algorithm, также алгоритм «sum-product») — алгоритм маргинализации с помощью двунаправленной передачи сообщений на графе, применяемый для вывода на графических вероятностных моделях (таких как байесовские и марковские сети). Предложен Дж. Перлом в 1982 году.
| Property | Value |
|---|---|
| dbo:abstract | Belief propagation, also known as sum–product message passing, is a message-passing algorithm for performing inference on graphical models, such as Bayesian networks and Markov random fields. It calculates the marginal distribution for each unobserved node (or variable), conditional on any observed nodes (or variables). Belief propagation is commonly used in artificial intelligence and information theory, and has demonstrated empirical success in numerous applications, including low-density parity-check codes, turbo codes, free energy approximation, and satisfiability. The algorithm was first proposed by Judea Pearl in 1982, who formulated it as an exact inference algorithm on trees, later extended to polytrees. While the algorithm is not exact on general graphs, it has been shown to be a useful approximate algorithm. (en) Kredo-disigo, aŭ Sumo-Oblo-Mesaĝado estas algoritmo por fari rezonadon per grafemodelo, ekzemple kaj . Ĝi komputas kondiĉan probablon de ne-observataj vertikoj per aliaj observataj vertikoj. Oni ofte uzas Kredo-disigon por artefarita inteligenteco kaj . Ĝi montras sukceson por aplikado kiel , , libera energio-proksimado, kaj -problemo. La algoritmon unue proponis Judea Pearl en 1982 por arboj. Sekve li ĝeneraligis la algoritmon al plurradikaj arboj.Ĝi sinpruvis kiel sukcesa proksimuma algoritmo por ĝenerala grafeo. X={Xi} estu aro da diskretaj hazardaj variabloj kun masa funkcio p, la de unu Xi estas simple la sumo de p super ĉiuj aliaj variabloj. Tamen, ĉi tio rapide iĝas nekomputebla por multe da variabloj. Por 100 duumaj hazardaj variabloj necesas sumi 299 ≈ 6.338 × 1029 eblaj valoroj. Kredo-disigo ebligas tre rapidan komputadon de randa probablo per utiligi la arban strukturon. (eo) El algoritmo de propagación de creencias (en inglés, belief propagation algorithm), también conocido como el algoritmo suma-producto, es un algoritmo de paso de mensajes para realizar inferencia sobre modelos gráficos tales como redes bayesianas, campos aleatorios de Markov y . Es ampliamente utilizado en los campos de inteligencia artificial y teoría de la información y ha mostrado cierto éxito experimental en aplicaciones tan diferentes como: , aproximaciones de energía libre, coloreado de grafos y satisfacibilidad booleana. Las ecuaciones de propagación de creencias han sido redescubiertas varias veces. Fueron desarrolladas por Pearl en 1988 como un algoritmo exacto para realizar inferencia probabilística sobre Redes Bayesianas acíclicas y como una aproximación útil en Redes Bayesianas con ciclos. En los inicios de los 60 Gallager las introdujo como un procedimiento iterativo para la recuperación de códigos de paridad. Sea un conjunto de variables aleatorias discretas, denotaremos con la realización de la variable aleatoria . Con usualmente escrita como donde . Es posible expresar como un producto de funciones: Donde es un índice sobre las funciones en que se descomponen , la función posee como argumento que es un subconjunto de las variables aleatorias . Entonces la distribución marginal de una variable dada es simplemente la suma de sobre todas las restantes variables. Este enfoque se vuelve computacionalmente prohibitivo (en sistemas de tamaños relativamente pequeños), suponiendo que y las variables son binarias. Entonces para obtener el valor marginal de computar valores posibles. Explotando la estructura de poliárboles, el algoritmo de propagación de creencias permite el cálculo de los marginales de manera más eficiente en tiempo lineal respecto al tamaño del sistema. (es) La propagation des convictions (Belief Propagation ou BP en anglais), aussi connu comme la transmission de message somme-produit, est un algorithme à passage de message pour effectuer des inférences sur des modèles graphiques, tels que les réseaux Bayésiens et les champs de Markov. Il calcule la distribution marginale de chaque nœud « non-observé » conditionnée sur les nœuds observés. La propagation des convictions est couramment utilisée dans l'intelligence artificielle et la théorie de l'information et a fait la preuve empirique de son succès dans de nombreuses applications, y compris le décodage des codes LDPC ou des turbo codes, l'approximation de l'énergie libre, et les modèles de satisfaisabilité. Cet algorithme fut proposé pour la première fois par Judea Pearl, en 1982. L'algorithme a été initialement formulé sur les arbres, et a ensuite été étendu aux arbres orientés. Il s'est depuis montré utile comme algorithme approximatif sur les graphes plus généraux. Si X={Xi} est un ensemble de variables aléatoires discrètes avec une loi de probabilité conjointe p, la distribution marginale d'un seul élément Xi est simplement la somme de p sur toutes les autres variables : Cependant, ce calcul devient vite prohibitif : s'il y a 100 variables binaires, alors, on somme sur les 299 ≈ 6.338 × 1029 valeurs possibles. En exploitant la structure en arbre, la propagation des convictions permet de calculer les marginaux de manière beaucoup plus efficace. (fr) 신뢰전파(Belief Propagation) 또는 Sum-product 메시지 전달 (sum-product message passing)은 베이즈 네트워크 또는 마르코프 네트워크 등의 상에 작용하는 메시지 전달 알고리즘이다. 이 알고리즘은 이미 관측한 노드의 상태를 토대로 아직 관측하지 않은 노드의 주변분포를 각각 계산한다. 신뢰전파는 주로 인공지능이나 정보이론의 분야에서 널리 사용되고 있으며 , , 자유에너지 근사, 충족 가능성 문제를 포함하며 응용에 다수 성공함이 경험적으로 확인된 상태다. 이 알고리즘은 1982년 주디아 펄에 의해 제안된것으로 당초에는 트리 구조상의 그래프 모델에서 작용되는 알고리즘을 후에 일반적인 트리 구조 모델에서도 작용할 수 있도록 확장하였다. 현재는 이 알고리즘이 일반 그래프 구조에서도 근사치를 주는 것으로 알려져있다. 한 가지 예를 들어 X=(Xv)를 결합확률질량함수p를 갖는 확률변수의 집합이라하면 특정 노드의 확률을 가리키는 주변분포 Xi는 단순히 p를Xi이외의 모든 노드에 대한 합을 구하는 것으로 포현가능하다: 그러나 이 계산방식은 만일 확률변수들이100개의 이진변수라 한다하여도 이 확률수 전체의 수는 299 ≈ 6.338 × 1029라는 엄청난 수에 달하며 컴퓨터상으로 계산하는 것은 매우 힘들어진다. 신뢰전파를 이용함으로써 대상 확률변수의 그래프 구조를 이용함으로써 주변분포의 계산을 보다 효율적으로 실행할 수 있다. (ko) 確率伝搬法 (かくりつでんぱんほう、英: belief propagation) あるいはSum-productメッセージ伝達法 (英: sum-product message passing) とは、ベイジアンネットワークやマルコフ確率場などのグラフィカルモデル上で作用する、メッセージ伝達のアルゴリズムである。このアルゴリズムは、既に観測されているノードの状態を基に、観測されていないノードの周辺分布をそれぞれ計算する。確率伝搬法は主に人工知能や情報理論の分野で広く用いられており、低密度パリティ検査符号、ターボ符号、自由エネルギー近似、充足可能性問題を含む、数多くの応用の成功が経験的に確かめられている。 確率伝搬法という表記について、一般に「伝搬は誤りで、伝播が正しい」と言われることがあるが、工学分野では電波法において「電波伝搬」という用語が正式に採用されており、情報分野においても「ループ伝搬」という用語が用いられている例がある。確率伝搬法についても、伝播ではなく伝搬の語が用いられてきた歴史的経緯があるため、本稿では「伝播」ではなく「伝搬」に統一する。 このアルゴリズムは1982年にジューディア・パールにより提案されたもので、当初は木構造上のグラフィカルモデルで作用するアルゴリズムであったものを、後に一般的な構造のモデルにおいても作用できるように拡張した。現在では、このアルゴリズムがループを含む一般のグラフ構造においても良い近似を与えることが示されている。 一例を示す。X=(Xv)を結合確率質量関数pをもつ離散的な確率変数の集合とすると、単体のノードの確率を表す周辺分布Xiは、単純にpをXi以外のノードについて和をとることで表現できる: しかし、この計算は仮に確率変数が100個の二値変数であったとしても、この確率変数全体の場合の数は299 ≈ 6.338 × 1029と非常に多くなるため、コンピュータ上で計算することは相当な困難を伴うものである。確率伝搬法では対象の確率変数のグラフ構造を利用することによって、この周辺分布の計算をより効率的に行う。 (ja) Алгоритм распространения доверия (англ. belief propagation, trust propagation algorithm, также алгоритм «sum-product») — алгоритм маргинализации с помощью двунаправленной передачи сообщений на графе, применяемый для вывода на графических вероятностных моделях (таких как байесовские и марковские сети). Предложен Дж. Перлом в 1982 году. (ru) 置信度传播（英語：belief propagation），又称为乘积和信息传递（sum-product message passing），是在贝叶斯网络、马尔可夫随机场等概率图模型中用于推断的一种信息传递算法。在给定已观测节点时，可以用该算法高效地计算未观测节点的边缘分布。置信度传播在人工智能、信息论中十分常见，已成功应用于低密度奇偶检查码、Turbo码、自由能估计、等不同领域。 置信度传播由美国计算机科学家朱迪亚·珀尔于1982年提出。最初该算法的运用范围仅限于树，不久则扩展到。此后，研究者发现在一般的图中该算法是一种十分有用的近似算法。 (zh) |
| dbo:wikiPageExternalLink | http://www.merl.com/publications/TR2001-022/ http://research.microsoft.com/en-us/um/people/cmbishop/prml/pdf/Bishop-PRML-sample.pdf https://web.archive.org/web/20171013161235/http:/computerrobotvision.org/2009/tutorial_day/crv09_belief_propagation_v2.pdf https://www.cs.cmu.edu/~bickson/gabp/index.html''Gaussian http://www.merl.com/publications/TR2004-040/ http://www.cambridge.org/us/catalogue/catalogue.asp%3Fisbn=9780521873154 https://www.newscientist.com/article/mg18725071-400-communication-speed-nears-terminal-velocity/ |
| dbo:wikiPageID | 800010 (xsd:integer) |
| dbo:wikiPageLength | 29328 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1123546486 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Bayesian_network dbr:Algorithm dbr:Approximation_error dbr:Arg_max dbr:Judea_Pearl dbr:Cycle_(graph_theory) dbr:EXIT_chart dbr:Inference dbr:Conjugate_gradient_method dbc:Graphical_models dbr:Mathematical_induction dbr:Gauss–Seidel_method dbr:Low-density_parity-check_codes dbr:Graph_(discrete_mathematics) dbr:Graph_coloring dbr:Monte_Carlo_method dbr:NP-complete dbr:NP-hard dbr:Thermodynamic_free_energy dbr:Statistical_inference dbr:Partition_function_(mathematics) dbr:Viterbi_algorithm dbc:Graph_algorithms dbr:Tree_(graph_theory) dbr:Junction_tree_algorithm dbc:Coding_theory dbr:Normal_distribution dbr:Bayesian_networks dbr:Diameter_(graph_theory) dbr:Graphical_model dbr:Island_algorithm dbr:Thermodynamics dbr:Random_variable dbr:Artificial_intelligence dbr:Binary_data dbr:Bipartite_graph dbr:Directed_acyclic_graph dbr:Marginal_distribution dbr:Polytree dbr:Positive-definite_matrix dbr:Spectral_radius dbr:Information_theory dbr:Internal_energy dbr:New_Scientist dbr:Markov_random_field dbr:Probability_mass_function dbr:Satisfiability dbr:Successive_over-relaxation dbr:Variational_Bayesian_methods dbr:Factor_graph dbr:Discrete_probability_distribution dbr:IEEE_Transactions_on_Information_Theory dbr:Sharp-P-complete dbr:Maximum_A_Posteriori dbr:Turbo_codes dbr:Joint_distribution dbr:Markov_random_fields dbr:Diagonally_dominant dbr:Cluster_variation_method dbr:Generalized_survey_propagation dbr:Ryoichi_Kikuchi dbr:Survey_propagation |
| dbp:date | February 2022 (en) |
| dbp:reason | Uniform distribution over what? (en) |
| dbp:wikiPageUsesTemplate | dbt:Cite_book dbt:Cite_journal dbt:Clarify dbt:More_footnotes dbt:Reflist dbt:Short_description dbt:Use_dmy_dates |
| dcterms:subject | dbc:Graphical_models dbc:Graph_algorithms dbc:Coding_theory |
| rdf:type | yago:Assistant109815790 yago:CausalAgent100007347 yago:LivingThing100004258 yago:Model110324560 yago:Object100002684 yago:Organism100004475 yago:Person100007846 yago:PhysicalEntity100001930 yago:WikicatGraphicalModels yago:Worker109632518 yago:YagoLegalActor yago:YagoLegalActorGeo yago:Whole100003553 |
| rdfs:comment | Алгоритм распространения доверия (англ. belief propagation, trust propagation algorithm, также алгоритм «sum-product») — алгоритм маргинализации с помощью двунаправленной передачи сообщений на графе, применяемый для вывода на графических вероятностных моделях (таких как байесовские и марковские сети). Предложен Дж. Перлом в 1982 году. (ru) 置信度传播（英語：belief propagation），又称为乘积和信息传递（sum-product message passing），是在贝叶斯网络、马尔可夫随机场等概率图模型中用于推断的一种信息传递算法。在给定已观测节点时，可以用该算法高效地计算未观测节点的边缘分布。置信度传播在人工智能、信息论中十分常见，已成功应用于低密度奇偶检查码、Turbo码、自由能估计、等不同领域。 置信度传播由美国计算机科学家朱迪亚·珀尔于1982年提出。最初该算法的运用范围仅限于树，不久则扩展到。此后，研究者发现在一般的图中该算法是一种十分有用的近似算法。 (zh) Belief propagation, also known as sum–product message passing, is a message-passing algorithm for performing inference on graphical models, such as Bayesian networks and Markov random fields. It calculates the marginal distribution for each unobserved node (or variable), conditional on any observed nodes (or variables). Belief propagation is commonly used in artificial intelligence and information theory, and has demonstrated empirical success in numerous applications, including low-density parity-check codes, turbo codes, free energy approximation, and satisfiability. (en) Kredo-disigo, aŭ Sumo-Oblo-Mesaĝado estas algoritmo por fari rezonadon per grafemodelo, ekzemple kaj . Ĝi komputas kondiĉan probablon de ne-observataj vertikoj per aliaj observataj vertikoj. Oni ofte uzas Kredo-disigon por artefarita inteligenteco kaj . Ĝi montras sukceson por aplikado kiel , , libera energio-proksimado, kaj -problemo. La algoritmon unue proponis Judea Pearl en 1982 por arboj. Sekve li ĝeneraligis la algoritmon al plurradikaj arboj.Ĝi sinpruvis kiel sukcesa proksimuma algoritmo por ĝenerala grafeo. (eo) El algoritmo de propagación de creencias (en inglés, belief propagation algorithm), también conocido como el algoritmo suma-producto, es un algoritmo de paso de mensajes para realizar inferencia sobre modelos gráficos tales como redes bayesianas, campos aleatorios de Markov y . Es ampliamente utilizado en los campos de inteligencia artificial y teoría de la información y ha mostrado cierto éxito experimental en aplicaciones tan diferentes como: , aproximaciones de energía libre, coloreado de grafos y satisfacibilidad booleana. Es posible expresar como un producto de funciones: (es) La propagation des convictions (Belief Propagation ou BP en anglais), aussi connu comme la transmission de message somme-produit, est un algorithme à passage de message pour effectuer des inférences sur des modèles graphiques, tels que les réseaux Bayésiens et les champs de Markov. Il calcule la distribution marginale de chaque nœud « non-observé » conditionnée sur les nœuds observés. La propagation des convictions est couramment utilisée dans l'intelligence artificielle et la théorie de l'information et a fait la preuve empirique de son succès dans de nombreuses applications, y compris le décodage des codes LDPC ou des turbo codes, l'approximation de l'énergie libre, et les modèles de satisfaisabilité. (fr) 確率伝搬法 (かくりつでんぱんほう、英: belief propagation) あるいはSum-productメッセージ伝達法 (英: sum-product message passing) とは、ベイジアンネットワークやマルコフ確率場などのグラフィカルモデル上で作用する、メッセージ伝達のアルゴリズムである。このアルゴリズムは、既に観測されているノードの状態を基に、観測されていないノードの周辺分布をそれぞれ計算する。確率伝搬法は主に人工知能や情報理論の分野で広く用いられており、低密度パリティ検査符号、ターボ符号、自由エネルギー近似、充足可能性問題を含む、数多くの応用の成功が経験的に確かめられている。 確率伝搬法という表記について、一般に「伝搬は誤りで、伝播が正しい」と言われることがあるが、工学分野では電波法において「電波伝搬」という用語が正式に採用されており、情報分野においても「ループ伝搬」という用語が用いられている例がある。確率伝搬法についても、伝播ではなく伝搬の語が用いられてきた歴史的経緯があるため、本稿では「伝播」ではなく「伝搬」に統一する。 一例を示す。X=(Xv)を結合確率質量関数pをもつ離散的な確率変数の集合とすると、単体のノードの確率を表す周辺分布Xiは、単純にpをXi以外のノードについて和をとることで表現できる: (ja) 신뢰전파(Belief Propagation) 또는 Sum-product 메시지 전달 (sum-product message passing)은 베이즈 네트워크 또는 마르코프 네트워크 등의 상에 작용하는 메시지 전달 알고리즘이다. 이 알고리즘은 이미 관측한 노드의 상태를 토대로 아직 관측하지 않은 노드의 주변분포를 각각 계산한다. 신뢰전파는 주로 인공지능이나 정보이론의 분야에서 널리 사용되고 있으며 , , 자유에너지 근사, 충족 가능성 문제를 포함하며 응용에 다수 성공함이 경험적으로 확인된 상태다. 이 알고리즘은 1982년 주디아 펄에 의해 제안된것으로 당초에는 트리 구조상의 그래프 모델에서 작용되는 알고리즘을 후에 일반적인 트리 구조 모델에서도 작용할 수 있도록 확장하였다. 현재는 이 알고리즘이 일반 그래프 구조에서도 근사치를 주는 것으로 알려져있다. 한 가지 예를 들어 X=(Xv)를 결합확률질량함수p를 갖는 확률변수의 집합이라하면 특정 노드의 확률을 가리키는 주변분포 Xi는 단순히 p를Xi이외의 모든 노드에 대한 합을 구하는 것으로 포현가능하다: (ko) |
| rdfs:label | Kredo-elsendo (eo) Belief propagation (en) Algoritmo de propagación de creencias (es) Propagation des convictions (fr) 신뢰전파 (ko) 確率伝搬法 (ja) Алгоритм распространения доверия (ru) 置信度传播 (zh) |
| owl:sameAs | freebase:Belief propagation yago-res:Belief propagation wikidata:Belief propagation dbpedia-eo:Belief propagation dbpedia-es:Belief propagation dbpedia-fa:Belief propagation dbpedia-fr:Belief propagation dbpedia-ja:Belief propagation dbpedia-ko:Belief propagation dbpedia-ru:Belief propagation dbpedia-zh:Belief propagation https://global.dbpedia.org/id/3mGHP |
| prov:wasDerivedFrom | wikipedia-en:Belief_propagation?oldid=1123546486&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Belief_propagation |
| is dbo:wikiPageRedirects of | dbr:Loopy_belief_propagation dbr:Generalized_belief_propagation dbr:Max-sum_algorithm dbr:Sum-product_algorithm dbr:Sum_product_algorithm dbr:Sum_product_rule dbr:Generalised_belief_propagation dbr:Generalised_belief_propogation dbr:Generalized_belief_propogation |
| is dbo:wikiPageWikiLink of | dbr:Bayesian_programming dbr:Belief_revision dbr:Protein_design dbr:Rumelhart_Prize dbr:List_of_algebraic_coding_theory_topics dbr:Message_passing_(disambiguation) dbr:NBP dbr:Moral_graph dbr:Stochastic_computing dbr:Approximate_inference dbr:Judea_Pearl dbr:EXIT_chart dbr:Influence_diagram dbr:Jacobi_method dbr:List_of_probability_topics dbr:Conditional_random_field dbr:Conjugate_gradient_method dbr:Gauss–Seidel_method dbr:Generalized_distributive_law dbr:Low-density_parity-check_code dbr:TrueSkill dbr:Glossary_of_artificial_intelligence dbr:Loopy_belief_propagation dbr:Cluster_analysis dbr:Community_structure dbr:Kernel_embedding_of_distributions dbr:Viterbi_algorithm dbr:Tree_decomposition dbr:GP5_chip dbr:Jump_flooding_algorithm dbr:Junction_tree_algorithm dbr:Optical_flow dbr:Numbers_(season_5) dbr:Cavity_method dbr:Direct_coupling_analysis dbr:Forward_algorithm dbr:Forward–backward_algorithm dbr:Graphical_model dbr:Island_algorithm dbr:Iterated_conditional_modes dbr:Generalized_belief_propagation dbr:Hierarchical_temporal_memory dbr:Social_navigation dbr:Collective_classification dbr:Turbo_code dbr:Polytree dbr:Claude_Berrou dbr:Max-sum_algorithm dbr:Catalog_of_articles_in_probability_theory dbr:Markov_logic_network dbr:Markov_random_field dbr:Stochastic_block_model dbr:Successive_over-relaxation dbr:Expectation_propagation dbr:Factor_graph dbr:List_of_statistics_articles dbr:Sudoku_code dbr:Sum-product_algorithm dbr:Sum_product_algorithm dbr:Sum_product_rule dbr:Generalised_belief_propagation dbr:Generalised_belief_propogation dbr:Generalized_belief_propogation |
| is foaf:primaryTopic of | wikipedia-en:Belief_propagation |