| 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)
|
| 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)
|
