aGrUM 3.3.2
a C++ library for (probabilistic) graphical models
ShaferShenoyLIMIDInference_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
49
50#include <agrum/ID/inference/ShaferShenoyLIMIDInference.h> // to ease IDE parser
51#ifndef DOXYGEN_SHOULD_SKIP_THIS
52
53// to ease parsing by IDE
54# include <limits>
55
59
60# define GUM_SSLI_TRACE_ON(x) // GUM_TRACE(x)
61# define GUM_SSLI_TENSOR_TRACE_ON(x) // GUM_TRACE(x)
62
63namespace gum {
64
65 template < GUM_Numeric GUM_SCALAR >
67 const InfluenceDiagram< GUM_SCALAR >* infDiag) :
68 InfluenceDiagramInference< GUM_SCALAR >(infDiag) {
69 GUM_CONSTRUCTOR(ShaferShenoyLIMIDInference);
70 createReduced_();
71 }
72
73 template < GUM_Numeric GUM_SCALAR >
74 ShaferShenoyLIMIDInference< GUM_SCALAR >::~ShaferShenoyLIMIDInference() {
75 GUM_DESTRUCTOR(ShaferShenoyLIMIDInference);
76 }
77
78 template < GUM_Numeric GUM_SCALAR >
79 void ShaferShenoyLIMIDInference< GUM_SCALAR >::clear() {
80 GraphicalModelInference< GUM_SCALAR >::clear();
81 noForgettingOrder_.clear();
82 reduced_.clear();
83 reducedJunctionTree_.clear();
84 solvabilityOrder_.clear();
85 posteriors_.clear();
86 unconditionalDecisions_.clear();
87 strategies_.clear();
88 reversePartialOrder_.clear();
89 }
90
91 template < GUM_Numeric GUM_SCALAR >
92 void ShaferShenoyLIMIDInference< GUM_SCALAR >::onStateChanged_() {}
93
94 template < GUM_Numeric GUM_SCALAR >
95 void ShaferShenoyLIMIDInference< GUM_SCALAR >::onEvidenceAdded_(const NodeId id,
96 bool isHardEvidence) {
97 const InfluenceDiagram< GUM_SCALAR >& infdiag = this->influenceDiagram();
98 if (infdiag.isUtilityNode(id)) { GUM_ERROR(InvalidNode, "No evidence on a utility node.") }
99 if (infdiag.isDecisionNode(id)) {
100 if (!isHardEvidence) GUM_ERROR(InvalidNode, "No soft evidence on a decision node.")
101 }
102 }
103
104 template < GUM_Numeric GUM_SCALAR >
105 void ShaferShenoyLIMIDInference< GUM_SCALAR >::onEvidenceErased_(const NodeId id,
106 bool isHardEvidence) {}
107
108 template < GUM_Numeric GUM_SCALAR >
109 void ShaferShenoyLIMIDInference< GUM_SCALAR >::onAllEvidenceErased_(bool contains_hard_evidence) {
110 }
111
112 template < GUM_Numeric GUM_SCALAR >
113 void ShaferShenoyLIMIDInference< GUM_SCALAR >::onEvidenceChanged_(const NodeId id,
114 bool hasChangedSoftHard) {}
115
116 template < GUM_Numeric GUM_SCALAR >
117 void ShaferShenoyLIMIDInference< GUM_SCALAR >::onModelChanged_(const GraphicalModel* model) {
118 createReduced_();
119 }
120
121 template < GUM_Numeric GUM_SCALAR >
122 void ShaferShenoyLIMIDInference< GUM_SCALAR >::updateOutdatedStructure_() {
123 createReduced_();
124 }
125
126 template < GUM_Numeric GUM_SCALAR >
127 void ShaferShenoyLIMIDInference< GUM_SCALAR >::updateOutdatedTensors_() {}
128
129 template < GUM_Numeric GUM_SCALAR >
130 void ShaferShenoyLIMIDInference< GUM_SCALAR >::makeInference_() {
131 if (!isSolvable()) { GUM_ERROR(FatalError, "This LIMID/Influence Diagram is not solvable.") }
132
133 PhiNodeProperty phi;
134 PsiArcProperty psi;
135
136 GUM_SSLI_TRACE_ON("\n\n")
137
138 initializingInference_(phi, psi);
139 // message passing (using reverse order of solvabilityOrder)
140 // first collect of phis into root
141 const auto firstRootIndice = 0;
142 collectingMessage_(phi, psi, node_to_clique_[solvabilityOrder_[firstRootIndice]]);
143 deciding_(phi, psi, solvabilityOrder_[firstRootIndice]);
144
145 for (Idx nextRootIndice = 1; nextRootIndice < solvabilityOrder_.size(); nextRootIndice++) {
146 if (node_to_clique_[solvabilityOrder_[nextRootIndice - 1]]
147 != node_to_clique_[solvabilityOrder_[nextRootIndice]]) {
148 collectingToFollowingRoot_(phi,
149 psi,
150 node_to_clique_[solvabilityOrder_[nextRootIndice - 1]],
151 node_to_clique_[solvabilityOrder_[nextRootIndice]]);
152 }
153 deciding_(phi, psi, solvabilityOrder_[nextRootIndice]);
154 }
155
156 // last distribution
157 distributingMessage_(phi,
158 psi,
159 node_to_clique_[solvabilityOrder_[solvabilityOrder_.size() - 1]]);
160 computingPosteriors_(phi, psi);
161 }
162
163 template < GUM_Numeric GUM_SCALAR >
164 void ShaferShenoyLIMIDInference< GUM_SCALAR >::initializingInference_(PhiNodeProperty& phi,
165 PsiArcProperty& psi) {
166 const auto& jt = *junctionTree();
167 const auto& infdiag = this->influenceDiagram();
168 // init JT tensors and separators
169
170 for (const auto node: jt.nodes()) {
171 phi.insert(node, DecisionTensor< GUM_SCALAR >());
172 for (const auto nei: jt.neighbours(node)) {
173 psi.insert(Arc(node, nei), DecisionTensor< GUM_SCALAR >());
174 if (node < nei) { // to do it only once by edge
175 // we create the set of vars in node and nei (cached in varsSeparators_)
176 for (const auto n: jt.clique(node) * jt.clique(nei))
177 varsSeparator_.getWithDefault(Edge(node, nei), SetOfVars())
178 .insert(&(infdiag.variable(n)));
179 }
180 }
181 }
182 for (const auto node: infdiag.nodes()) {
183 const auto clik = node_to_clique_[node];
184 if (this->hasEvidence(node)) {
185 auto q = *(this->evidence()[node]);
186 phi[clik].insertProba(q.normalize());
187 }
188
189 if (infdiag.isDecisionNode(node)) {
190 if (!this->hasEvidence(node)) {
191 auto p = (Tensor< GUM_SCALAR >() << infdiag.variable(node)).fillWith(1).normalize();
192 phi[clik].insertProba(p); // WITHOUT NORMALIZATION !!!
193 }
194 } else if (infdiag.isChanceNode(node)) phi[clik].insertProba(infdiag.cpt(node));
195 else if (infdiag.isUtilityNode(node)) phi[clik].insertUtility(infdiag.utility(node));
196 else GUM_ERROR(FatalError, "Node " << node << " has no type.")
197 }
198 }
199
200 template < GUM_Numeric GUM_SCALAR >
201 void ShaferShenoyLIMIDInference< GUM_SCALAR >::_creatingJunctionTree_() {
202 const auto& infdiag = this->influenceDiagram();
203 auto moral = reduced_.moralGraph();
204
205 // once the moral graph is completed, we remove the utility nodes before
206 // triangulation
207 NodeProperty< Size > modalities;
208 for (const auto node: infdiag.nodes())
209 if (infdiag.isUtilityNode(node)) {
210 moral.eraseNode(node);
211 } else {
212 modalities.insert(node, infdiag.variable(node).domainSize());
213 }
214 DefaultTriangulation triangulation(&moral, &modalities);
215 reducedJunctionTree_ = triangulation.junctionTree();
216 _findingCliqueForEachNode_(triangulation);
217 }
218
219 template < GUM_Numeric GUM_SCALAR >
220 void ShaferShenoyLIMIDInference< GUM_SCALAR >::_findingCliqueForEachNode_(
221 DefaultTriangulation& triangulation) {
222 // indicate, for each node of the moral graph a clique in _JT_ that can
223 // contain its conditional probability table
224 const auto& infdiag = this->influenceDiagram();
225 NodeId first_eliminated_node;
226 Idx elim_number;
227 node_to_clique_.clear();
228 const std::vector< NodeId >& JT_elim_order = triangulation.eliminationOrder();
229 NodeProperty< Idx > elim_order(Size(JT_elim_order.size()));
230 for (Idx i = Idx(0), size = JT_elim_order.size(); i < size; ++i)
231 elim_order.insert(JT_elim_order[i], (int)i);
232 for (const auto node: reduced_.nodes()) {
233 if (infdiag.isUtilityNode(node)) {
234 // utility nodes are not in the junction tree but we want to associate a
235 // clique as well
236 first_eliminated_node = node;
237 elim_number = std::numeric_limits< NodeId >::max(); // an impossible elim_number;
238 } else {
239 // get the variables in the tensor of node (and its parents)
240 first_eliminated_node = node;
241 elim_number = elim_order[first_eliminated_node];
242 }
243
244 for (const auto parent: reduced_.parents(node)) {
245 if (elim_order[parent] < elim_number) {
246 elim_number = elim_order[parent];
247 first_eliminated_node = parent;
248 }
249 }
250
251 // first_eliminated_node contains the first var (node or one of its
252 // parents) eliminated => the clique created during its elimination
253 // contains node and all of its parents => it can contain the tensor
254 // assigned to the node in the BN
255 node_to_clique_.insert(node, triangulation.createdJunctionTreeClique(first_eliminated_node));
256 }
257 }
258
259 template < GUM_Numeric GUM_SCALAR >
260 std::pair< GUM_SCALAR, GUM_SCALAR > ShaferShenoyLIMIDInference< GUM_SCALAR >::MEU() {
261 if (!this->isInferenceDone()) GUM_ERROR(OperationNotAllowed, "Call MakeInference first")
262
263 const InfluenceDiagram< GUM_SCALAR >& infdiag = this->influenceDiagram();
264 const auto& jt = *junctionTree();
265
266 // the factors of the ID with the optimal strategies, as moments, in their cliques
267 NodeProperty< _UtilityMoments_ > moments;
268 for (const auto clique: jt.nodes())
269 moments.insert(clique, _UtilityMoments_());
270 auto addProba = [&](NodeId node, const Tensor< GUM_SCALAR >& p) {
271 _UtilityMoments_ m;
272 m.proba = p;
273 m.hasProba = true;
274 _combineMoments_(moments[node_to_clique_[node]], m);
275 };
276 for (const auto node: infdiag.nodes()) {
277 if (this->hasEvidence(node)) addProba(node, *(this->evidence()[node]));
278
279 if (infdiag.isChanceNode(node)) addProba(node, infdiag.cpt(node));
280 else if (infdiag.isDecisionNode(node)) addProba(node, strategies_[node]);
281 else if (infdiag.isUtilityNode(node)) {
282 _UtilityMoments_ m;
283 m.util = infdiag.utility(node);
284 m.util2 = m.util * m.util;
285 m.hasUtility = true;
286 _combineMoments_(moments[node_to_clique_[node]], m);
287 }
288 }
289
290 // collect in each connected component of the junction tree. The traversal is iterative (no
291 // recursion depth bounded by the diameter of the junction tree): the cliques are listed in
292 // pre-order, then each clique, in reverse pre-order (its children come first), sends its
293 // message to its parent
294 _UtilityMoments_ total;
295 NodeProperty< NodeId > parent; // also the set of the visited cliques
296 std::vector< NodeId > order;
297 std::vector< NodeId > stack;
298 for (const auto root: jt.nodes()) {
299 if (parent.exists(root)) continue;
300 order.clear();
301 parent.insert(root, root);
302 stack.push_back(root);
303 while (!stack.empty()) {
304 const NodeId clique = stack.back();
305 stack.pop_back();
306 order.push_back(clique);
307 for (const auto nei: jt.neighbours(clique))
308 if (!parent.exists(nei)) {
309 parent.insert(nei, clique);
310 stack.push_back(nei);
311 }
312 }
313
314 for (auto iter = order.rbegin(); iter != order.rend(); ++iter) {
315 const NodeId clique = *iter;
316 const NodeId father = parent[clique];
317 if (clique == father) {
318 _combineMoments_(total, _marginalizeMoments_(moments[clique], SetOfVars()));
319 } else {
320 _combineMoments_(
321 moments[father],
322 _marginalizeMoments_(moments[clique], varsSeparator_[Edge(clique, father)]));
323 }
324 }
325 }
326
327 const GUM_SCALAR phi = total.hasProba ? total.proba.sum() : GUM_SCALAR(1);
328 const GUM_SCALAR mean = total.hasUtility ? total.util.sum() / phi : GUM_SCALAR(0);
329 const GUM_SCALAR mean2 = total.hasUtility ? total.util2.sum() / phi : GUM_SCALAR(0);
330 GUM_SCALAR var = mean2 - mean * mean;
331 if (var < 0) var = 0; // var is a small negative number due to rounding errors
332 return std::pair< GUM_SCALAR, GUM_SCALAR >(mean, var);
333 }
334
335 template < GUM_Numeric GUM_SCALAR >
336 void ShaferShenoyLIMIDInference< GUM_SCALAR >::_combineMoments_(
337 _UtilityMoments_& moments,
338 const _UtilityMoments_& other) const {
339 if (!other.hasProba && !other.hasUtility) return;
340 if (!moments.hasProba && !moments.hasUtility) {
341 moments = other;
342 return;
343 }
344
345 // (p1, a1, b1) x (p2, a2, b2) = (p1.p2, p1.a2 + p2.a1, p1.b2 + p2.b1 + 2.a1.a2)
346 auto times = [](const _UtilityMoments_& m, const Tensor< GUM_SCALAR >& t) {
347 return m.hasProba ? m.proba * t : t;
348 };
349 _UtilityMoments_ res;
350 if (moments.hasUtility && other.hasUtility) {
351 res.util = times(moments, other.util) + times(other, moments.util);
352 res.util2 = times(moments, other.util2) + times(other, moments.util2)
353 + (moments.util * other.util).scale(2);
354 } else if (moments.hasUtility) {
355 res.util = times(other, moments.util);
356 res.util2 = times(other, moments.util2);
357 } else if (other.hasUtility) {
358 res.util = times(moments, other.util);
359 res.util2 = times(moments, other.util2);
360 }
361 res.hasUtility = moments.hasUtility || other.hasUtility;
362
363 if (other.hasProba) res.proba = times(moments, other.proba);
364 else if (moments.hasProba) res.proba = moments.proba;
365 res.hasProba = moments.hasProba || other.hasProba;
366
367 moments = std::move(res);
368 }
369
370 template < GUM_Numeric GUM_SCALAR >
371 typename ShaferShenoyLIMIDInference< GUM_SCALAR >::_UtilityMoments_
372 ShaferShenoyLIMIDInference< GUM_SCALAR >::_marginalizeMoments_(
373 const _UtilityMoments_& moments,
374 const SetOfVars& kept) const {
375 auto marginalize = [&kept](const Tensor< GUM_SCALAR >& t) {
376 SetOfVars del;
377 for (const auto var: t.variablesSequence())
378 if (!kept.contains(var)) del.insert(var);
379 return t.sumOut(del);
380 };
381 _UtilityMoments_ res;
382 res.hasProba = moments.hasProba;
383 res.hasUtility = moments.hasUtility;
384 if (res.hasProba) res.proba = marginalize(moments.proba);
385 if (res.hasUtility) {
386 res.util = marginalize(moments.util);
387 res.util2 = marginalize(moments.util2);
388 }
389 return res;
390 }
391
392 template < GUM_Numeric GUM_SCALAR >
394 ShaferShenoyLIMIDInference< GUM_SCALAR >::optimalDecision(NodeId decisionId) {
395 if (!this->isInferenceDone()) GUM_ERROR(OperationNotAllowed, "Call MakeInference first")
396
397 const InfluenceDiagram< GUM_SCALAR >& infdiag = this->influenceDiagram();
398 if (!infdiag.isDecisionNode(decisionId))
400 infdiag.variable(decisionId).name()
401 << "(" << decisionId << ") is not a decision node.")
402
403 return strategies_[decisionId];
404 }
405
406 template < GUM_Numeric GUM_SCALAR >
407 bool ShaferShenoyLIMIDInference< GUM_SCALAR >::isSolvable() const {
408 return (!solvabilityOrder_.empty());
409 }
410
411 template < GUM_Numeric GUM_SCALAR >
412 void ShaferShenoyLIMIDInference< GUM_SCALAR >::createReduced_() {
413 // from LIMIDS of decision Problems, Lauritzen et Nilsson, 1999
414 reduced_.clear();
415 reducedJunctionTree_.clear();
416 solvabilityOrder_.clear();
417 reversePartialOrder_.clear();
418 posteriors_.clear();
419 unconditionalDecisions_.clear();
420 strategies_.clear();
421 const InfluenceDiagram< GUM_SCALAR >& infdiag = this->influenceDiagram();
422
423 NodeSet utilities;
424
425 // build reduced_
426 for (auto node: infdiag.nodes()) {
427 reduced_.addNodeWithId(node);
428 if (infdiag.isUtilityNode(node)) { utilities.insert(node); }
429 }
430
431 for (const auto& arc: infdiag.arcs())
432 reduced_.addArc(arc.tail(), arc.head());
433
434 _completingNoForgettingAssumption_();
435 _creatingPartialOrder_(utilities);
436 _checkingSolvability_(utilities);
437 if (isSolvable()) {
438 _reducingLIMID_();
439 _creatingJunctionTree_();
440 }
441
442 this->setState_(GraphicalModelInference< GUM_SCALAR >::StateOfInference::OutdatedStructure);
443 }
444
445 template < GUM_Numeric GUM_SCALAR >
446 void ShaferShenoyLIMIDInference< GUM_SCALAR >::_completingNoForgettingAssumption_() {
447 // force no forgetting if necessary
448 if (hasNoForgettingAssumption()) {
449 auto last = *(noForgettingOrder_.begin());
450 for (auto node: noForgettingOrder_)
451 if (node == last) // first one
452 continue;
453 else { // we deal with last->node
454 // adding the whole family of last as parents of node
455 if (!reduced_.existsArc(last, node)) { reduced_.addArc(last, node); }
456 for (auto par: reduced_.parents(last)) {
457 if (!reduced_.existsArc(par, node)) reduced_.addArc(par, node);
458 }
459 last = node;
460 }
461 }
462 }
463
464 template < GUM_Numeric GUM_SCALAR >
465 void ShaferShenoyLIMIDInference< GUM_SCALAR >::_checkingSolvability_(const NodeSet& utilities) {
466 if (hasNoForgettingAssumption()) {
467 solvabilityOrder_ = noForgettingOrder_;
468 std::reverse(solvabilityOrder_.begin(), solvabilityOrder_.end());
469 return;
470 }
471
472 solvabilityOrder_.clear();
473 for (const auto& sen: reversePartialOrder()) {
474 NodeSet tobetested = sen;
475 while (!tobetested.empty()) {
476 bool foundOne = false;
477 for (const auto& node: tobetested) {
478 const auto us = utilities * reduced_.descendants(node);
479 NodeSet decs;
480 for (const auto dec: tobetested)
481 if (dec != node) decs += reduced_.family(dec);
482 if (reduced_.dSeparation(decs, us, reduced_.family(node))) {
483 solvabilityOrder_.push_back(node);
484 foundOne = true;
485 tobetested.erase(node);
486 break;
487 }
488 }
489 if (!foundOne) { // no solvability
490 solvabilityOrder_.clear();
491 return;
492 }
493 }
494 }
495 }
496
497 template < GUM_Numeric GUM_SCALAR >
498 void ShaferShenoyLIMIDInference< GUM_SCALAR >::_reducingLIMID_() {
499 for (const auto& sen: reversePartialOrder_) {
500 for (auto n: sen) {
501 for (auto p: nonRequisiteNodes_(n))
502 reduced_.eraseArc(Arc(p, n));
503 }
504 }
505 }
506
507 template < GUM_Numeric GUM_SCALAR >
508 void ShaferShenoyLIMIDInference< GUM_SCALAR >::_creatingPartialOrder_(const NodeSet& utilities) {
509 const InfluenceDiagram< GUM_SCALAR >& infdiag = this->influenceDiagram();
510 NodeProperty< Size > level;
511
512 for (const auto& node: utilities)
513 level.insert(node, 0); // utility node is level 0
514
515 // creating the partial order
516 Size max_level = 0;
517 reversePartialOrder_.clear();
518 reversePartialOrder_.resize(infdiag.size());
519 NodeSet currents;
520 for (auto node: infdiag.nodes()) {
521 if (infdiag.isUtilityNode(node)) continue;
522 if (reduced_.children(node).isSubsetOrEqual(utilities)) {
523 currents.clear();
524 currents.insert(node);
525 level.insert(node, 0);
526 while (!currents.empty()) {
527 NodeId elt = *(currents.begin());
528 currents.erase(elt);
529
530 if (infdiag.isDecisionNode(elt)) reversePartialOrder_[level[elt]].insert(elt);
531
532 for (auto parent: reduced_.parents(elt)) {
533 Size lev = 0;
534 Size newl;
535 bool ok_to_add = true;
536 for (auto child: reduced_.children(parent)) {
537 if (!level.exists(child)) {
538 ok_to_add = false;
539 break;
540 }
541 newl = level[child];
542 if (infdiag.isDecisionNode(child)) newl += 1;
543 if (lev < newl) lev = newl;
544 }
545 if (ok_to_add) {
546 currents.insert(parent);
547 if (level.exists(parent)) {
548 if (level[parent] != lev)
550 "Trying to set level[" << parent << "] to level=" << lev
551 << " but already is " << level[parent]);
552 } else {
553 level.insert(parent, lev);
554 }
555
556 if (max_level < lev) max_level = lev;
557 }
558 }
559 }
560 }
561 }
562 Size levmax = 0;
563 for (const auto& k: reversePartialOrder_) {
564 if (k.empty()) break;
565 levmax++;
566 }
567 reversePartialOrder_.resize(levmax);
568 }
569
570 template < GUM_Numeric GUM_SCALAR >
571 std::vector< NodeSet > ShaferShenoyLIMIDInference< GUM_SCALAR >::reversePartialOrder() const {
572 return reversePartialOrder_;
573 }
574
575 template < GUM_Numeric GUM_SCALAR >
576 bool ShaferShenoyLIMIDInference< GUM_SCALAR >::hasNoForgettingAssumption() const {
577 return !noForgettingOrder_.empty();
578 }
579
580 template < GUM_Numeric GUM_SCALAR >
581 void ShaferShenoyLIMIDInference< GUM_SCALAR >::addNoForgettingAssumption(
582 const std::vector< std::string >& names) {
583 addNoForgettingAssumption(this->influenceDiagram().ids(names));
584 }
585
586 template < GUM_Numeric GUM_SCALAR >
587 void ShaferShenoyLIMIDInference< GUM_SCALAR >::addNoForgettingAssumption(
588 const std::vector< NodeId >& ids) {
589 const auto& infdiag = this->influenceDiagram();
590 for (const auto node: ids) {
591 if (!infdiag.exists(node)) GUM_ERROR(NotFound, node << " is not a NodeId")
592 if (!infdiag.isDecisionNode(node))
594 "Node " << node << " (" << infdiag.variable(node).name()
595 << ") is not a decision node");
596 }
597 if (infdiag.decisionNodeSize() != ids.size())
598 GUM_ERROR(SizeError, "Some decision nodes are missing in the sequence " << ids)
599
600 noForgettingOrder_ = ids;
601 createReduced_();
602 }
603
604 template < GUM_Numeric GUM_SCALAR >
605 NodeSet ShaferShenoyLIMIDInference< GUM_SCALAR >::nonRequisiteNodes_(NodeId d) const {
606 const InfluenceDiagram< GUM_SCALAR >& infdiag = this->influenceDiagram();
607
608 if (!infdiag.isDecisionNode(d)) GUM_ERROR(TypeError, d << " is not a decision node")
609
610 NodeSet res;
611 if (reduced_.parents(d).empty()) return res;
612
613 NodeSet descUs;
614 for (const auto n: reduced_.descendants(d))
615 if (infdiag.isUtilityNode(n)) descUs.insert(n);
616
617 NodeSet cumul{descUs};
618 cumul << d;
619 auto g = reduced_.moralizedAncestralGraph(cumul);
620
621 NodeSet family{reduced_.parents(d)};
622 family << d;
623 bool notReq;
624 for (const auto p: reduced_.parents(d)) {
625 notReq = true;
626 for (const auto u: descUs) {
627 if (g.hasUndirectedPath(p, u, family)) {
628 notReq = false;
629 break;
630 }
631 }
632 if (notReq) res << p;
633 }
634 return res;
635 }
636
637 template < GUM_Numeric GUM_SCALAR >
638 InfluenceDiagram< GUM_SCALAR > ShaferShenoyLIMIDInference< GUM_SCALAR >::reducedLIMID() const {
639 const auto& infdiag = this->influenceDiagram();
640 InfluenceDiagram< GUM_SCALAR > res;
641 for (auto node: infdiag.nodes()) {
642 if (infdiag.isChanceNode(node)) res.addChanceNode(infdiag.variable(node), node);
643 else if (infdiag.isDecisionNode(node)) res.addDecisionNode(infdiag.variable(node), node);
644 else // (infdiag.isUtilityNode(node))
645 res.addUtilityNode(infdiag.variable(node), node);
646 }
647
648 for (const auto& arc: reduced_.arcs()) {
649 res.addArc(arc.tail(), arc.head());
650 }
651
652 for (auto node: infdiag.nodes()) {
653 if (infdiag.isChanceNode(node)) res.cpt(node).fillWith(infdiag.cpt(node));
654 else if (infdiag.isUtilityNode(node)) res.utility(node).fillWith(infdiag.utility(node));
655 }
656
657 // Tensors !!!
658 return res;
659 }
660
661 template < GUM_Numeric GUM_SCALAR >
662 const JunctionTree* ShaferShenoyLIMIDInference< GUM_SCALAR >::junctionTree() const {
663 if (!isSolvable()) { GUM_ERROR(FatalError, "This LIMID/Influence Diagram is not solvable.") }
664 return &reducedJunctionTree_;
665 }
666
667 template < GUM_Numeric GUM_SCALAR >
668 void ShaferShenoyLIMIDInference< GUM_SCALAR >::collectingMessage_(PhiNodeProperty& phi,
669 PsiArcProperty& psi,
670 const NodeId rootClique) {
671 const auto& jt = *junctionTree();
672 GUM_SSLI_TRACE_ON("COLLECTING TO " << rootClique << ":"
673 << this->influenceDiagram().names(jt.clique(rootClique)))
674
675 std::function< void(NodeId, NodeId) > parcours = [&](NodeId node, NodeId toRoot) {
676 for (const auto nei: jt.neighbours(node)) {
677 if (nei != toRoot) parcours(nei, node);
678 }
679 transmittingMessage_(phi, psi, node, toRoot);
680 GUM_SSLI_TRACE_ON(" " << node << "->" << toRoot << " transmitted")
681 };
682
683 for (const auto nei: jt.neighbours(rootClique)) {
684 parcours(nei, rootClique);
685 }
686 }
687
688 template < GUM_Numeric GUM_SCALAR >
689 void ShaferShenoyLIMIDInference< GUM_SCALAR >::collectingToFollowingRoot_(PhiNodeProperty& phi,
690 PsiArcProperty& psi,
691 NodeId fromClique,
692 NodeId toClique) {
693 GUM_SSLI_TRACE_ON("COLLECTING FROM ROOT " << fromClique << " TO FOLLOWING ROOT " << toClique)
694 const auto& jt = *junctionTree();
695
696 std::function< bool(NodeId, NodeId, NodeId) > revparcours
697 = [&](NodeId node, NodeId from, NodeId target) {
698 if (node == target) return true;
699
700 bool found = false;
701 NodeId prec;
702 for (const auto nei: jt.neighbours(node)) {
703 if (nei != from)
704 if (revparcours(nei, node, target)) {
705 prec = nei;
706 found = true;
707 break;
708 }
709 }
710 if (found) { transmittingMessage_(phi, psi, prec, node); }
711 return found;
712 };
713
714 revparcours(toClique, std::numeric_limits< NodeId >::max(), fromClique);
715 }
716
717 template < GUM_Numeric GUM_SCALAR >
718 void ShaferShenoyLIMIDInference< GUM_SCALAR >::deciding_(PhiNodeProperty& phi,
719 PsiArcProperty& psi,
720 NodeId decisionNode) {
721 const auto& infdiag = this->influenceDiagram();
722 GUM_SSLI_TRACE_ON("DECIDING for " << infdiag.variable(decisionNode).name())
723
724 auto& decision = strategies_.getWithDefault(decisionNode, Tensor< GUM_SCALAR >());
725
726 if (this->hasHardEvidence(decisionNode)) {
727 decision = *(this->evidence()[decisionNode]);
728 } else {
729 DecisionTensor< double > dp;
730 dp = integrating_(phi, psi, node_to_clique_[decisionNode]);
731 GUM_SSLI_TENSOR_TRACE_ON(dp)
732
733 SetOfVars sev;
734 sev.insert(&infdiag.variable(decisionNode));
735 for (const auto parent: reduced_.parents(decisionNode)) {
736 sev.insert(&infdiag.variable(parent));
737 }
738 dp = dp ^ sev;
739 GUM_SSLI_TENSOR_TRACE_ON(dp)
740
741 // SPECIAL CASE FOR DETERMINISTIC DECISION
742 sev.erase(&infdiag.variable(decisionNode)); // only the parents in sev
743 if (sev.size() == 0) { // deterministic decision node
744 unconditionalDecisions_.set(decisionNode, dp);
745 } else if (dp.probPot.sumIn(sev).normalize().max()
746 == 1) { // with deterministic posterior probability
747 // we can use marginalization because we know that dp is deterministic
748 unconditionalDecisions_.set(
749 decisionNode,
750 DecisionTensor< double >(dp.probPot.sumOut(sev), dp.utilPot.sumOut(sev)));
751 }
752 decision = dp.utilPot.putFirst(&infdiag.variable(decisionNode));
753
754 binarizingMax_(decision, dp.probPot);
755 GUM_SSLI_TENSOR_TRACE_ON(decision)
756 }
757 GUM_SSLI_TENSOR_TRACE_ON(phi[node_to_clique_[decisionNode]])
758 phi[node_to_clique_[decisionNode]].insertProba(decision);
759 GUM_SSLI_TENSOR_TRACE_ON(phi[node_to_clique_[decisionNode]])
760 }
761
762 template < GUM_Numeric GUM_SCALAR >
763 void ShaferShenoyLIMIDInference< GUM_SCALAR >::binarizingMax_(
764 const Tensor< GUM_SCALAR >& decision,
765 const Tensor< GUM_SCALAR >& proba) const { // compute the decisions (as maxEU)
766 Instantiation I(decision);
767 const auto& firstvar = decision.variable(0);
768 for (I.setFirst(); !I.end(); I.incNotVar(firstvar)) {
769 I.setFirstVar(firstvar);
770 while (proba[I] == 0) {
771 I.incVar(firstvar);
772 if (I.end()) { // for non valid proba, we keep the first value (by
773 // default)²
774 I.setFirstVar(firstvar);
775 break;
776 }
777 }
778 // we found a non null value of proba
779 Idx argm = I.val(firstvar);
780 GUM_SCALAR umax = decision[I];
781 GUM_SCALAR pmax = proba[I];
782 for (I.incVar(firstvar); !I.end(); I.incVar(firstvar)) {
783 // lexicographical order on (u,p)
784 if (proba[I] > 0) {
785 if ((umax < decision[I]) || ((umax == decision[I]) && (pmax < proba[I]))) {
786 umax = decision[I];
787 pmax = proba[I];
788 argm = I.val(firstvar);
789 }
790 }
791 }
792 for (I.setFirstVar(firstvar); !I.end(); I.incVar(firstvar))
793 decision.set(I, 0);
794 I.chgVal(firstvar, argm);
795 decision.set(I, 1);
796 }
797 }
798
799 template < GUM_Numeric GUM_SCALAR >
800 void ShaferShenoyLIMIDInference< GUM_SCALAR >::distributingMessage_(PhiNodeProperty& phi,
801 PsiArcProperty& psi,
802 NodeId rootClique) {
803 const auto& jt = *junctionTree();
804 GUM_SSLI_TRACE_ON("DISTRIBUTING FROM " << rootClique << ":"
805 << this->influenceDiagram().names(jt.clique(rootClique)))
806
807 std::function< void(NodeId, NodeId) > parcours = [&](NodeId node, NodeId from) {
808 transmittingFinalMessage_(phi, psi, from, node);
809 auto res = integrating_(phi, psi, node);
810
811 res.probPot
813 psi[gum::Arc(node, from)].probPot);
814 res.utilPot = res.utilPot - psi[gum::Arc(node, from)].utilPot;
815
816 phi.set(node, res);
817 GUM_SSLI_TRACE_ON(" -> phi[" << node << "] updated")
818 for (const auto nei: jt.neighbours(node)) {
819 if (nei != from) parcours(nei, node);
820 }
821 };
822
823 phi.set(rootClique, integrating_(phi, psi, rootClique));
824 GUM_SSLI_TRACE_ON(" -> phi[" << rootClique << "] updated")
825 GUM_SSLI_TENSOR_TRACE_ON(phi[rootClique])
826
827 for (const auto nei: jt.neighbours(rootClique)) {
828 parcours(nei, rootClique);
829 }
830 }
831
832 template < GUM_Numeric GUM_SCALAR >
833 void ShaferShenoyLIMIDInference< GUM_SCALAR >::transmittingFinalMessage_(PhiNodeProperty& phi,
834 PsiArcProperty& psi,
835 NodeId fromClique,
836 NodeId toClique) {
837 GUM_SSLI_TRACE_ON(fromClique << "->" << toClique << " [final]")
838 // no need to integrate phi : already done
839 psi.set(Arc(fromClique, toClique),
840 phi[fromClique] ^ varsSeparator_[Edge(fromClique, toClique)]);
841 }
842
843 template < GUM_Numeric GUM_SCALAR >
844 void ShaferShenoyLIMIDInference< GUM_SCALAR >::transmittingMessage_(PhiNodeProperty& phi,
845 PsiArcProperty& psi,
846 NodeId fromClique,
847 NodeId toClique) {
848 GUM_SSLI_TRACE_ON(fromClique << "->" << toClique)
849 psi.set(Arc(fromClique, toClique),
850 integrating_(phi, psi, fromClique, toClique)
851 ^ varsSeparator_[Edge(fromClique, toClique)]);
852 }
853
854 template < GUM_Numeric GUM_SCALAR >
855 DecisionTensor< double >
856 ShaferShenoyLIMIDInference< GUM_SCALAR >::integrating_(const PhiNodeProperty& phi,
857 const PsiArcProperty& psi,
858 NodeId inClique,
859 NodeId except) const {
860 const auto& jt = *junctionTree();
861 GUM_SSLI_TRACE_ON(" integrating (except from "
862 << except << ") in " << inClique << ":"
863 << this->influenceDiagram().names(jt.clique(inClique)))
864 DecisionTensor< double > res = phi[inClique];
865 for (const auto nei: jt.neighbours(inClique))
866 if (nei != except) res *= psi[Arc(nei, inClique)];
867
868 return res;
869 }
870
871 template < GUM_Numeric GUM_SCALAR >
872 DecisionTensor< double >
873 ShaferShenoyLIMIDInference< GUM_SCALAR >::integrating_(const PhiNodeProperty& phi,
874 const PsiArcProperty& psi,
875 NodeId inClique) const {
876 const auto& jt = *junctionTree();
877 GUM_SSLI_TRACE_ON(" integrating in " << inClique << ":"
878 << this->influenceDiagram().names(jt.clique(inClique)))
879 DecisionTensor< double > res = phi[inClique];
880
881 for (const auto nei: jt.neighbours(inClique))
882 res *= psi[Arc(nei, inClique)];
883
884 return res;
885 }
886
887 template < GUM_Numeric GUM_SCALAR >
888 void ShaferShenoyLIMIDInference< GUM_SCALAR >::computingPosteriors_(const PhiNodeProperty& phi,
889 const PsiArcProperty& psi) {
890 NodeProperty< DecisionTensor< double > > finalphis;
891
892 const auto& infdiag = this->influenceDiagram();
893 posteriors_.clear();
894 strategies_.clear();
895 for (const auto node: infdiag.nodes()) {
896 const auto clik = node_to_clique_[node];
897 // if (!finalphis.exists(clik)) finalphis.insert(clik, integrating_(phi, psi, clik));
898 // const auto& finalphi = finalphis[clik];
899 const auto& finalphi = phi[clik];
900 GUM_SSLI_TRACE_ON("posterior for " << infdiag.variable(node).name())
901
902 DecisionTensor< GUM_SCALAR > res;
903
904 if (infdiag.isChanceNode(node)) {
905 SetOfVars sev;
906 sev.insert(&infdiag.variable(node));
907 res = finalphi ^ sev;
908 const auto f = res.probPot.sum();
909 res.probPot.scale(1 / f);
910 } else if (infdiag.isDecisionNode(node)) {
911 SetOfVars sev;
912 sev.insert(&infdiag.variable(node));
913 SetOfVars family = sev;
914 for (const auto par: reduced_.parents(node)) {
915 family.insert(&infdiag.variable(par));
916 }
917 // GCC 16 false positive: deep inlining confuses heap-allocated internals
918 // of DecisionTensor with the stack object bounds
919# ifdef __GNUC__
920# pragma GCC diagnostic push
921# pragma GCC diagnostic ignored "-Warray-bounds"
922# endif
923 const auto dp = finalphi ^ family;
924
925 gum::Tensor< double > decision = dp.utilPot.putFirst(&infdiag.variable(node));
926 binarizingMax_(decision, dp.probPot);
927 strategies_.insert(node, decision);
928 res = dp ^ sev;
929# ifdef __GNUC__
930# pragma GCC diagnostic pop
931# endif
932 res.probPot.normalize();
933 if (unconditionalDecisions_.exists(node)) {
934 res.utilPot = unconditionalDecisions_[node].utilPot;
935 }
936 } else { // utility
937 SetOfVars family;
938
939 family.insert(&infdiag.variable(node));
940 for (const auto par: reduced_.parents(node)) {
941 family.insert(&infdiag.variable(par));
942 }
943 res = finalphi ^ family;
944
945 res.probPot.normalize();
946 res.utilPot = infdiag.utility(node);
947 }
948
949 posteriors_.set(node, res);
950 }
951 }
952
953 template < GUM_Numeric GUM_SCALAR >
954 const Tensor< GUM_SCALAR >& ShaferShenoyLIMIDInference< GUM_SCALAR >::posterior(NodeId node) {
955 return posteriors_[node].probPot;
956 }
957
958 template < GUM_Numeric GUM_SCALAR >
959 const Tensor< GUM_SCALAR >&
960 ShaferShenoyLIMIDInference< GUM_SCALAR >::posteriorUtility(NodeId node) {
961 return posteriors_[node].utilPot;
962 }
963
964 template < GUM_Numeric GUM_SCALAR >
965 std::pair< GUM_SCALAR, GUM_SCALAR >
966 ShaferShenoyLIMIDInference< GUM_SCALAR >::meanVar(NodeId node) {
967 return posteriors_[node].meanVar();
968 }
969
970 template < GUM_Numeric GUM_SCALAR >
971 DAG ShaferShenoyLIMIDInference< GUM_SCALAR >::reducedGraph() const {
972 return reduced_;
973 }
974
975 template < GUM_Numeric GUM_SCALAR >
977 ShaferShenoyLIMIDInference< GUM_SCALAR >::optimalDecision(std::string_view decisionName) {
978 return optimalDecision(this->influenceDiagram().idFromName(decisionName));
979 }
980
981 template < GUM_Numeric GUM_SCALAR >
982 const Tensor< GUM_SCALAR >&
983 ShaferShenoyLIMIDInference< GUM_SCALAR >::posterior(std::string_view name) {
984 return posterior(this->influenceDiagram().idFromName(name));
985 }
986
987 template < GUM_Numeric GUM_SCALAR >
988 const Tensor< GUM_SCALAR >&
989 ShaferShenoyLIMIDInference< GUM_SCALAR >::posteriorUtility(std::string_view name) {
990 return posteriorUtility(this->influenceDiagram().idFromName(name));
991 }
992
993 template < GUM_Numeric GUM_SCALAR >
994 std::pair< GUM_SCALAR, GUM_SCALAR >
995 ShaferShenoyLIMIDInference< GUM_SCALAR >::meanVar(std::string_view name) {
996 return meanVar(this->influenceDiagram().idFromName(name));
997 }
998
999} /* namespace gum */
1000
1001#endif /* DOXYGEN_SHOULD_SKIP_THIS */
Implementation of an influence diagram inference algorithm based upon Shaffer-Shenoy's one for bayes ...
The base class for all directed edges.
static Tensor< GUM_SCALAR > divideEvenZero(const Tensor< GUM_SCALAR > &p1, const Tensor< GUM_SCALAR > &p2)
Exception : fatal (unknown ?) error.
<agrum/ID/inference/influenceDiagramInference.h>
Class representing an Influence Diagram.
Exception : node does not exist.
Exception : the element we looked for cannot be found.
Exception : operation not allowed.
void resize(Size new_capacity)
Changes the size of the underlying hash table containing the set.
Definition set_tpl.h:439
void insert(const Key &k)
Inserts a new element into the set.
Definition set_tpl.h:510
ShaferShenoyLIMIDInference(const InfluenceDiagram< GUM_SCALAR > *infDiag)
Default constructor.
Exception : problem with size.
aGrUM's Tensor is a multi-dimensional array with tensor operators.
Definition tensor.h:85
Exception : wrong type for this operation.
This file contains abstract class definitions influence diagrams inference classes.
#define GUM_ERROR(type, msg)
Definition exceptions.h:76
Set< NodeId > NodeSet
Some typdefs and define for shortcuts ...
NodeSet family(const G &g, NodeId id)
Returns the family of id : { id } ∪ parents(id).
gum is the global namespace for all aGrUM entities
Definition agrum.h:46
template class GUM_SHARED_PUBLIC Tensor< double >
Definition tensor.cpp:53
CliqueGraph JunctionTree
a junction tree is a clique graph satisfying the running intersection property and such that no cliqu...
Header of the Tensor class.