aGrUM 3.3.2
a C++ library for (probabilistic) graphical models
loopyBeliefPropagation_tpl.h
Go to the documentation of this file.
1/****************************************************************************
2 * This file is part of the aGrUM/pyAgrum library. *
3 * *
4 * Copyright (c) 2005-2026 by *
5 * - Pierre-Henri WUILLEMIN(_at_LIP6) *
6 * - Christophe GONZALES(_at_AMU) *
7 * *
8 * The aGrUM/pyAgrum library is free software; you can redistribute it *
9 * and/or modify it under the terms of either : *
10 * *
11 * - the GNU Lesser General Public License as published by *
12 * the Free Software Foundation, either version 3 of the License, *
13 * or (at your option) any later version, *
14 * - the MIT license (MIT), *
15 * - or both in dual license, as here. *
16 * *
17 * (see https://agrum.gitlab.io/articles/dual-licenses-lgplv3mit.html) *
18 * *
19 * This aGrUM/pyAgrum library is distributed in the hope that it will be *
20 * useful, but WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, *
21 * INCLUDING BUT NOT LIMITED TO THE WARRANTIES MERCHANTABILITY or FITNESS *
22 * FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE *
23 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER *
24 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, *
25 * ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR *
26 * OTHER DEALINGS IN THE SOFTWARE. *
27 * *
28 * See LICENCES for more details. *
29 * *
30 * SPDX-FileCopyrightText: Copyright 2005-2026 *
31 * - Pierre-Henri WUILLEMIN(_at_LIP6) *
32 * - Christophe GONZALES(_at_AMU) *
33 * SPDX-License-Identifier: LGPL-3.0-or-later OR MIT *
34 * *
35 * Contact : info_at_agrum_dot_org *
36 * homepage : http://agrum.gitlab.io *
37 * gitlab : https://gitlab.com/agrumery/agrum *
38 * *
39 ****************************************************************************/
40
41#pragma once
42
43
48#include <agrum/BN/inference/loopyBeliefPropagation.h> // to ease IDE parser
49#ifndef DOXYGEN_SHOULD_SKIP_THIS
50
51# include <algorithm>
52# include <sstream>
53# include <string>
54
55// to ease parsing for IDE
57
58namespace gum {
59
61 template < GUM_Numeric GUM_SCALAR >
63 ApproximateInference< GUM_SCALAR >(bn) {
64 // for debugging purposes
65 GUM_CONSTRUCTOR(LoopyBeliefPropagation)
66
67 // epsilon, minimal epsilon rate, maximum number of iterations, period size and verbosity (no
68 // timeout)
69 this->setFromConfiguration_("lbp", false);
70
71 _init_messages_();
72 }
73
75 template < GUM_Numeric GUM_SCALAR >
76 LoopyBeliefPropagation< GUM_SCALAR >::~LoopyBeliefPropagation() {
77 GUM_DESTRUCTOR(LoopyBeliefPropagation)
78 }
79
80 template < GUM_Numeric GUM_SCALAR >
81 void LoopyBeliefPropagation< GUM_SCALAR >::_init_messages_() {
82 _messages_.clear();
83 for (const auto& tail: this->BN().nodes()) {
84 Tensor< GUM_SCALAR > p;
85 p.add(this->BN().variable(tail));
86 p.fill(static_cast< GUM_SCALAR >(1));
87
88 for (const auto& head: this->BN().children(tail)) {
89 _messages_.insert(Arc(head, tail), p);
90 _messages_.insert(Arc(tail, head), p);
91 }
92 }
93 }
94
95 template < GUM_Numeric GUM_SCALAR >
96 void LoopyBeliefPropagation< GUM_SCALAR >::updateOutdatedStructure_() {
97 _init_messages_();
98 }
99
100 template < GUM_Numeric GUM_SCALAR >
101 Tensor< GUM_SCALAR > LoopyBeliefPropagation< GUM_SCALAR >::_computeProdPi_(NodeId X) {
102 const auto& varX = this->BN().variable(X);
103
104 auto piX = this->BN().cpt(X);
105 for (const auto& U: this->BN().parents(X)) {
106 piX *= _messages_[Arc(U, X)];
107 }
108 piX = piX.sumIn({&varX});
109
110 return piX;
111 }
112
113 template < GUM_Numeric GUM_SCALAR >
114 Tensor< GUM_SCALAR > LoopyBeliefPropagation< GUM_SCALAR >::_computeProdPi_(NodeId X,
115 NodeId except) {
116 const auto& varX = this->BN().variable(X);
117 const auto& varExcept = this->BN().variable(except);
118 auto piXexcept = this->BN().cpt(X);
119 for (const auto& U: this->BN().parents(X)) {
120 if (U != except) { piXexcept *= _messages_[Arc(U, X)]; }
121 }
122 piXexcept = piXexcept.sumIn({&varX, &varExcept});
123 return piXexcept;
124 }
125
126 template < GUM_Numeric GUM_SCALAR >
127 Tensor< GUM_SCALAR > LoopyBeliefPropagation< GUM_SCALAR >::_computeProdLambda_(NodeId X) {
128 Tensor< GUM_SCALAR > lamX;
129 if (this->hasEvidence(X)) {
130 lamX = *(this->evidence()[X]);
131 } else {
132 lamX.add(this->BN().variable(X));
133 lamX.fill(1);
134 }
135 for (const auto& Y: this->BN().children(X)) {
136 lamX *= _messages_[Arc(Y, X)];
137 }
138
139 return lamX;
140 }
141
142 template < GUM_Numeric GUM_SCALAR >
143 Tensor< GUM_SCALAR > LoopyBeliefPropagation< GUM_SCALAR >::_computeProdLambda_(NodeId X,
144 NodeId except) {
145 Tensor< GUM_SCALAR > lamXexcept;
146 if (this->hasEvidence(X)) { //
147 lamXexcept = *this->evidence()[X];
148 } else {
149 lamXexcept.add(this->BN().variable(X));
150 lamXexcept.fill(1);
151 }
152 for (const auto& Y: this->BN().children(X)) {
153 if (Y != except) { lamXexcept *= _messages_[Arc(Y, X)]; }
154 }
155
156 return lamXexcept;
157 }
158
159 template < GUM_Numeric GUM_SCALAR >
160 GUM_SCALAR LoopyBeliefPropagation< GUM_SCALAR >::_updateNodeMessage_(NodeId X) {
161 auto piX = _computeProdPi_(X);
162 auto lamX = _computeProdLambda_(X);
163
164 GUM_SCALAR KL = 0;
165 Arc argKL(0, 0);
166
167 // update lambda_par (for arc U->x)
168 for (const auto& U: this->BN().parents(X)) {
169 auto newLambda = (_computeProdPi_(X, U) * lamX).sumIn({&this->BN().variable(U)});
170 newLambda.normalize();
171 auto ekl = static_cast< GUM_SCALAR >(0);
172 try {
173 ekl = _messages_[Arc(X, U)].KL(newLambda);
174 } catch (InvalidArgument const&) {
175 GUM_ERROR(InvalidArgument, "Not compatible pi during computation")
176 } catch (FatalError const&) { // 0 misplaced
177 ekl = std::numeric_limits< GUM_SCALAR >::infinity();
178 }
179 if (ekl > KL) {
180 KL = ekl;
181 argKL = Arc(X, U);
182 }
183 _messages_.set(Arc(X, U), newLambda);
184 }
185
186 // update pi_child (for arc x->child)
187 for (const auto& Y: this->BN().children(X)) {
188 auto newPi = (piX * _computeProdLambda_(X, Y));
189 newPi.normalize();
190 GUM_SCALAR ekl = KL;
191 try {
192 ekl = _messages_[Arc(X, Y)].KL(newPi);
193 } catch (InvalidArgument const&) {
194 GUM_ERROR(InvalidArgument, "Not compatible pi during computation")
195 } catch (FatalError const&) { // 0 misplaced
196 ekl = std::numeric_limits< GUM_SCALAR >::infinity();
197 }
198 if (ekl > KL) {
199 KL = ekl;
200 argKL = Arc(X, Y);
201 }
202 _messages_.set(Arc(X, Y), newPi);
203 }
204
205 return KL;
206 }
207
208 template < GUM_Numeric GUM_SCALAR >
209 void LoopyBeliefPropagation< GUM_SCALAR >::_initStats_() {
210 _init_messages_();
211 for (const auto& node: this->BN().topologicalOrder()) {
212 _updateNodeMessage_(node);
213 }
214 }
215
217 template < GUM_Numeric GUM_SCALAR >
218 void LoopyBeliefPropagation< GUM_SCALAR >::makeInference_() {
219 _initStats_();
220 this->initApproximationScheme();
221
222 std::vector< NodeId > shuffleIds;
223 for (const auto& node: this->BN().nodes())
224 shuffleIds.push_back(node);
225
226 auto engine = std::default_random_engine{};
227
228 GUM_SCALAR error = 0.0;
229 do {
230 error = 0.0; // error of the current sweep only
231 std::shuffle(std::begin(shuffleIds), std::end(shuffleIds), engine);
232 this->updateApproximationScheme();
233 for (const auto& node: shuffleIds) {
234 GUM_SCALAR e = _updateNodeMessage_(node);
235 if (e > error) error = e;
236 }
237 } while (this->continueApproximationScheme(error));
238 }
239
241 template < GUM_Numeric GUM_SCALAR >
242 const Tensor< GUM_SCALAR >& LoopyBeliefPropagation< GUM_SCALAR >::posterior_(NodeId id) {
243 auto p = _computeProdPi_(id) * _computeProdLambda_(id);
244 p.normalize();
245 _posteriors_.set(id, p);
246
247 return _posteriors_[id];
248 }
249
250 template < GUM_Numeric GUM_SCALAR >
251 void LoopyBeliefPropagation< GUM_SCALAR >::onStateChanged_() {}
252
253 template < GUM_Numeric GUM_SCALAR >
254 void LoopyBeliefPropagation< GUM_SCALAR >::onEvidenceAdded_(const NodeId id,
255 bool isHardEvidence) {}
256
257 template < GUM_Numeric GUM_SCALAR >
258 void LoopyBeliefPropagation< GUM_SCALAR >::onEvidenceErased_(const NodeId id,
259 bool isHardEvidence) {}
260
261 template < GUM_Numeric GUM_SCALAR >
262 void LoopyBeliefPropagation< GUM_SCALAR >::onAllEvidenceErased_(bool contains_hard_evidence) {}
263
264 template < GUM_Numeric GUM_SCALAR >
265 void LoopyBeliefPropagation< GUM_SCALAR >::onEvidenceChanged_(const NodeId id,
266 bool hasChangedSoftHard) {}
267
268 template < GUM_Numeric GUM_SCALAR >
269 void LoopyBeliefPropagation< GUM_SCALAR >::onModelChanged_(const GraphicalModel* bn) {}
270
271 template < GUM_Numeric GUM_SCALAR >
272 void LoopyBeliefPropagation< GUM_SCALAR >::updateOutdatedTensors_() {}
273
274 template < GUM_Numeric GUM_SCALAR >
275 void LoopyBeliefPropagation< GUM_SCALAR >::onMarginalTargetAdded_(const NodeId id) {}
276
277 template < GUM_Numeric GUM_SCALAR >
278 void LoopyBeliefPropagation< GUM_SCALAR >::onMarginalTargetErased_(const NodeId id) {}
279
280 template < GUM_Numeric GUM_SCALAR >
281 void LoopyBeliefPropagation< GUM_SCALAR >::onAllMarginalTargetsAdded_() {}
282
283 template < GUM_Numeric GUM_SCALAR >
284 void LoopyBeliefPropagation< GUM_SCALAR >::onAllMarginalTargetsErased_() {}
285
286} /* namespace gum */
287
288#endif // DOXYGEN_SHOULD_SKIP_THIS
KL is the base class for KL computation betweens 2 BNs.
Exception : fatal (unknown ?) error.
Class representing the minimal interface for Bayesian network with no numerical data.
Definition IBayesNet.h:79
Exception: at least one argument passed to a function is not what was expected.
LoopyBeliefPropagation(const IBayesNet< GUM_SCALAR > *bn)
Default constructor.
#define GUM_ERROR(type, msg)
Definition exceptions.h:76
This file contains gibbs sampling (for BNs) class definitions.
Sequence< NodeId > topologicalOrder(const G &g)
Returns a topological ordering of the nodes of g (Kahn's algorithm).
gum is the global namespace for all aGrUM entities
Definition agrum.h:46