aGrUM 3.3.2
a C++ library for (probabilistic) graphical models
ShaferShenoyInference_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
51
53#include <agrum/BN/inference/ShaferShenoyInference.h> // to ease IDE parser
54#ifndef DOXYGEN_SHOULD_SKIP_THIS
55# include <algorithm>
56
64
65namespace gum {
66 // default constructor
67 template < GUM_Numeric GUM_SCALAR >
70 RelevantTensorsFinderType relevant_type,
71 FindBarrenNodesType barren_type,
72 bool use_binary_join_tree) :
73 JointTargetedInference< GUM_SCALAR >(BN), EvidenceInference< GUM_SCALAR >(BN),
74 _use_binary_join_tree_(use_binary_join_tree) {
75 // sets the relevant tensor and the barren nodes finding algorithm
76 _findRelevantTensors_
77 = &ShaferShenoyInference< GUM_SCALAR >::_findRelevantTensorsWithdSeparation2_;
78 setRelevantTensorsFinderType(relevant_type);
79 setFindBarrenNodesType(barren_type);
80
81 // create a default triangulation (the user can change it afterwards)
82 _triangulation_ = new DefaultTriangulation;
83
84 // for debugging purposes
85 GUM_CONSTRUCTOR(ShaferShenoyInference);
86 }
87
88 // destructor
89 template < GUM_Numeric GUM_SCALAR >
90 ShaferShenoyInference< GUM_SCALAR >::~ShaferShenoyInference() {
91 // remove all the tensors created during the last message passing
92 for (const auto& pot: _arc_to_created_tensors_)
93 delete pot.second;
94
95 // remove all the tensors in _clique_ss_tensor_ that do not belong
96 // to _clique_tensors_ : in this case, those tensors have been
97 // created by combination of the corresponding list of tensors in
98 // _clique_tensors_. In other words, the size of this list is strictly
99 // greater than 1.
100 for (auto pot: _clique_ss_tensor_) {
101 if (_clique_tensors_[pot.first].size() > 1) delete pot.second;
102 }
103
104 for (auto potset: _clique_tensors_) {
105 for (auto pot: potset.second)
106 delete pot;
107 }
108
109 // remove all the posteriors computed
110 for (const auto& pot: _target_posteriors_)
111 delete pot.second;
112 for (const auto& pot: _joint_target_posteriors_)
113 delete pot.second;
114
115 // remove the junction tree and the triangulation algorithm
116 if (_JT_ != nullptr) delete _JT_;
117 if (_junctionTree_ != nullptr) delete _junctionTree_;
118 delete _triangulation_;
119
120 // for debugging purposes
121 GUM_DESTRUCTOR(ShaferShenoyInference);
122 }
123
125 template < GUM_Numeric GUM_SCALAR >
126 void ShaferShenoyInference< GUM_SCALAR >::setTriangulation(
127 const Triangulation& new_triangulation) {
128 delete _triangulation_;
129 _triangulation_ = new_triangulation.newFactory();
130 _is_new_jt_needed_ = true;
131 this->setOutdatedStructureState_();
132 }
133
135 template < GUM_Numeric GUM_SCALAR >
136 const JoinTree* ShaferShenoyInference< GUM_SCALAR >::joinTree() {
137 if (_is_new_jt_needed_) _createNewJT_();
138
139 return _JT_;
140 }
141
143 template < GUM_Numeric GUM_SCALAR >
144 const JunctionTree* ShaferShenoyInference< GUM_SCALAR >::junctionTree() {
145 if (_is_new_jt_needed_) _createNewJT_();
146
147 return _junctionTree_;
148 }
149
151 template < GUM_Numeric GUM_SCALAR >
152 void ShaferShenoyInference< GUM_SCALAR >::setRelevantTensorsFinderType(
153 RelevantTensorsFinderType type) {
154 if (type != _find_relevant_tensor_type_) {
155 switch (type) {
156 case RelevantTensorsFinderType::DSEP_BAYESBALL_TENSORS :
157 _findRelevantTensors_
158 = &ShaferShenoyInference< GUM_SCALAR >::_findRelevantTensorsWithdSeparation2_;
159 break;
160
161 case RelevantTensorsFinderType::DSEP_BAYESBALL_NODES :
162 _findRelevantTensors_
163 = &ShaferShenoyInference< GUM_SCALAR >::_findRelevantTensorsWithdSeparation_;
164 break;
165
166 case RelevantTensorsFinderType::DSEP_KOLLER_FRIEDMAN_2009 :
167 _findRelevantTensors_
168 = &ShaferShenoyInference< GUM_SCALAR >::_findRelevantTensorsWithdSeparation3_;
169 break;
170
171 case RelevantTensorsFinderType::FIND_ALL :
172 _findRelevantTensors_ = &ShaferShenoyInference< GUM_SCALAR >::_findRelevantTensorsGetAll_;
173 break;
174
175 default :
177 "setRelevantTensorsFinderType for type " << (unsigned int)type
178 << " is not implemented yet");
179 }
180
181 _find_relevant_tensor_type_ = type;
182
183 // indicate that all messages need be reconstructed to take into account
184 // the change in d-separation analysis
185 _invalidateAllMessages_();
186 }
187 }
188
190 template < GUM_Numeric GUM_SCALAR >
191 void ShaferShenoyInference< GUM_SCALAR >::_setProjectionFunction_(
192 Tensor< GUM_SCALAR > (*proj)(const Tensor< GUM_SCALAR >&, const gum::VariableSet&)) {
193 _projection_op_ = proj;
194
195 // indicate that all messages need be reconstructed to take into account
196 // the change in of the projection operator
197 _invalidateAllMessages_();
198 }
199
201 template < GUM_Numeric GUM_SCALAR >
202 void ShaferShenoyInference< GUM_SCALAR >::_setCombinationFunction_(
203 Tensor< GUM_SCALAR > (*comb)(const Tensor< GUM_SCALAR >&, const Tensor< GUM_SCALAR >&)) {
204 _combination_op_ = comb;
205
206 // indicate that all messages need be reconstructed to take into account
207 // the change of the combination operator
208 _invalidateAllMessages_();
209 }
210
212 template < GUM_Numeric GUM_SCALAR >
213 void ShaferShenoyInference< GUM_SCALAR >::_invalidateAllMessages_() {
214 // remove all the messages computed
215 for (auto& pot: _separator_tensors_)
216 pot.second = nullptr;
217
218 for (auto& mess_computed: _messages_computed_)
219 mess_computed.second = false;
220
221 // remove all the created tensors kept on the arcs
222 for (const auto& pot: _arc_to_created_tensors_)
223 if (pot.second != nullptr) delete pot.second;
224 _arc_to_created_tensors_.clear();
225
226 // remove all the posteriors
227 for (const auto& pot: _target_posteriors_)
228 delete pot.second;
229 _target_posteriors_.clear();
230 for (const auto& pot: _joint_target_posteriors_)
231 delete pot.second;
232 _joint_target_posteriors_.clear();
233
234 // indicate that new messages need be computed
235 if (this->isInferenceReady() || this->isInferenceDone()) this->setOutdatedTensorsState_();
236 }
237
239 template < GUM_Numeric GUM_SCALAR >
240 void ShaferShenoyInference< GUM_SCALAR >::setFindBarrenNodesType(FindBarrenNodesType type) {
241 if (type != _barren_nodes_type_) {
242 // WARNING: if a new type is added here, method _createJT_ should certainly
243 // be updated as well, in particular its step 2.
244 switch (type) {
245 case FindBarrenNodesType::FIND_BARREN_NODES :
246 case FindBarrenNodesType::FIND_NO_BARREN_NODES : break;
247
248 default :
250 "setFindBarrenNodesType for type " << (unsigned int)type
251 << " is not implemented yet");
252 }
253
254 _barren_nodes_type_ = type;
255
256 // tensorly, we may need to reconstruct a junction tree
257 this->setOutdatedStructureState_();
258 }
259 }
260
262 template < GUM_Numeric GUM_SCALAR >
263 void ShaferShenoyInference< GUM_SCALAR >::onEvidenceAdded_(const NodeId id, bool isHardEvidence) {
264 // if we have a new hard evidence, this modifies the undigraph over which
265 // the join tree is created. This is also the case if id is not a node of
266 // of the undigraph
267 if (isHardEvidence || !_graph_.exists(id)) _is_new_jt_needed_ = true;
268 else {
269 try {
270 _evidence_changes_.insert(id, EvidenceChangeType::EVIDENCE_ADDED);
271 } catch (DuplicateElement const&) {
272 // here, the evidence change already existed. This necessarily means
273 // that the current saved change is an EVIDENCE_ERASED. So if we
274 // erased the evidence and added some again, this corresponds to an
275 // EVIDENCE_MODIFIED
276 _evidence_changes_[id] = EvidenceChangeType::EVIDENCE_MODIFIED;
277 }
278 }
279 }
280
282 template < GUM_Numeric GUM_SCALAR >
283 void ShaferShenoyInference< GUM_SCALAR >::onEvidenceErased_(const NodeId id,
284 bool isHardEvidence) {
285 // if we delete a hard evidence, this modifies the undigraph over which
286 // the join tree is created.
287 if (isHardEvidence) _is_new_jt_needed_ = true;
288 else {
289 try {
290 _evidence_changes_.insert(id, EvidenceChangeType::EVIDENCE_ERASED);
291 } catch (DuplicateElement const&) {
292 // here, the evidence change already existed and it is necessarily an
293 // EVIDENCE_ADDED or an EVIDENCE_MODIFIED. So, if the evidence has
294 // been added and is now erased, this is similar to not having created
295 // it. If the evidence was only modified, it already existed in the
296 // last inference and we should now indicate that it has been removed.
297 if (_evidence_changes_[id] == EvidenceChangeType::EVIDENCE_ADDED)
298 _evidence_changes_.erase(id);
299 else _evidence_changes_[id] = EvidenceChangeType::EVIDENCE_ERASED;
300 }
301 }
302 }
303
305 template < GUM_Numeric GUM_SCALAR >
306 void ShaferShenoyInference< GUM_SCALAR >::onAllEvidenceErased_(bool has_hard_evidence) {
307 if (has_hard_evidence || !this->hardEvidenceNodes().empty()) _is_new_jt_needed_ = true;
308 else {
309 for (const auto node: this->softEvidenceNodes()) {
310 try {
311 _evidence_changes_.insert(node, EvidenceChangeType::EVIDENCE_ERASED);
312 } catch (DuplicateElement const&) {
313 // here, the evidence change already existed and it is necessarily an
314 // EVIDENCE_ADDED or an EVIDENCE_MODIFIED. So, if the evidence has
315 // been added and is now erased, this is similar to not having created
316 // it. If the evidence was only modified, it already existed in the
317 // last inference and we should now indicate that it has been removed.
318 if (_evidence_changes_[node] == EvidenceChangeType::EVIDENCE_ADDED)
319 _evidence_changes_.erase(node);
320 else _evidence_changes_[node] = EvidenceChangeType::EVIDENCE_ERASED;
321 }
322 }
323 }
324 }
325
327 template < GUM_Numeric GUM_SCALAR >
328 void ShaferShenoyInference< GUM_SCALAR >::onEvidenceChanged_(const NodeId id,
329 bool hasChangedSoftHard) {
330 if (hasChangedSoftHard) _is_new_jt_needed_ = true;
331 else {
332 try {
333 _evidence_changes_.insert(id, EvidenceChangeType::EVIDENCE_MODIFIED);
334 } catch (DuplicateElement const&) {
335 // here, the evidence change already existed and it is necessarily an
336 // EVIDENCE_ADDED. So we should keep this state to indicate that this
337 // evidence is new w.r.t. the last inference
338 }
339 }
340 }
341
343 template < GUM_Numeric GUM_SCALAR >
344 void ShaferShenoyInference< GUM_SCALAR >::onModelChanged_(const GraphicalModel* bn) {}
345
347 template < GUM_Numeric GUM_SCALAR >
348 void ShaferShenoyInference< GUM_SCALAR >::onMarginalTargetAdded_(const NodeId id) {
349 // if the graph does not contain the node, either this is due to the fact that
350 // the node has received a hard evidence or because it was d-separated from the
351 // target nodes during the last inference. In the latter case, we should change
352 // the graph, hence we should recompute the JT
353 if (!_graph_.exists(id) && !_hard_ev_nodes_.contains(id)) { _is_new_jt_needed_ = true; }
354 }
355
357 template < GUM_Numeric GUM_SCALAR >
358 void ShaferShenoyInference< GUM_SCALAR >::onMarginalTargetErased_(const NodeId id) {}
359
361 template < GUM_Numeric GUM_SCALAR >
362 void ShaferShenoyInference< GUM_SCALAR >::onJointTargetAdded_(const NodeSet& set) {
363 // if there is no current joint tree, obviously, we need one.
364 if (_JT_ == nullptr) {
365 _is_new_jt_needed_ = true;
366 return;
367 }
368
369 // here, we will remove from set the nodes that received hard evidence and try
370 // to find a clique in the current _JT_ that can contain the resulting set. If
371 // we cannot find one, we must recompute the _JT_
372 NodeId first_eliminated_node = std::numeric_limits< NodeId >::max();
373 int elim_number = std::numeric_limits< int >::max();
374 const std::vector< NodeId >& JT_elim_order = _triangulation_->eliminationOrder();
375 NodeProperty< int > elim_order(Size(JT_elim_order.size()));
376 for (std::size_t i = std::size_t(0), size = JT_elim_order.size(); i < size; ++i)
377 elim_order.insert(JT_elim_order[i], (int)i);
378 NodeSet unobserved_set(set.size());
379 for (const auto node: set) {
380 if (!_graph_.exists(node)) {
381 if (!_hard_ev_nodes_.contains(node)) {
382 _is_new_jt_needed_ = true;
383 return;
384 }
385 } else {
386 unobserved_set.insert(node);
387 if (elim_order[node] < elim_number) {
388 elim_number = elim_order[node];
389 first_eliminated_node = node;
390 }
391 }
392 }
393
394 if (!unobserved_set.empty()) {
395 // here, first_eliminated_node contains the first var (node or one of its
396 // parents) eliminated => the clique created during its elimination
397 // should contain all the nodes in unobserved_set
398 const auto clique_id = _node_to_clique_[first_eliminated_node];
399 const auto& clique = _JT_->clique(clique_id);
400 for (const auto node: unobserved_set) {
401 if (!clique.contains(node)) {
402 _is_new_jt_needed_ = true;
403 return;
404 }
405 }
406 }
407 }
408
410 template < GUM_Numeric GUM_SCALAR >
411 void ShaferShenoyInference< GUM_SCALAR >::onJointTargetErased_(const NodeSet& set) {}
412
414 template < GUM_Numeric GUM_SCALAR >
415 void ShaferShenoyInference< GUM_SCALAR >::onAllMarginalTargetsAdded_() {
416 for (const auto node: this->BN().internalDag()) {
417 // if the graph does not contain the node, either this is due to the fact
418 // that the node has received a hard evidence or because it was d-separated
419 // from the target nodes during the last inference. In the latter case, we
420 // should change the graph, hence we should recompute the JT
421 if (!_graph_.exists(node) && !_hard_ev_nodes_.contains(node)) {
422 _is_new_jt_needed_ = true;
423 return;
424 }
425 }
426 }
427
429 template < GUM_Numeric GUM_SCALAR >
430 void ShaferShenoyInference< GUM_SCALAR >::onAllMarginalTargetsErased_() {}
431
433 template < GUM_Numeric GUM_SCALAR >
434 void ShaferShenoyInference< GUM_SCALAR >::onAllJointTargetsErased_() {}
435
437 template < GUM_Numeric GUM_SCALAR >
438 void ShaferShenoyInference< GUM_SCALAR >::onAllTargetsErased_() {}
439
440 // check whether a new junction tree is really needed for the next inference
441 template < GUM_Numeric GUM_SCALAR >
442 bool ShaferShenoyInference< GUM_SCALAR >::_isNewJTNeeded_() const {
443 // if we do not have a JT or if _new_jt_needed_ is set to true, then
444 // we know that we need to create a new join tree
445 if ((_JT_ == nullptr) || _is_new_jt_needed_) return true;
446
447 // if some targets do not belong to the join tree and, consequently, to the
448 // undirected graph that was used to construct the join tree, then we need
449 // to create a new JT. This situation may occur if we constructed the
450 // join tree after pruning irrelevant/barren nodes from the BN.
451 // However, note that the nodes that received hard evidence do not belong to
452 // the graph and, therefore, should not be taken into account
453 const auto& hard_ev_nodes = this->hardEvidenceNodes();
454 for (const auto node: this->targets()) {
455 if (!_graph_.exists(node) && !hard_ev_nodes.exists(node)) return true;
456 }
457
458 // now, do the same for the joint targets
459 const std::vector< NodeId >& JT_elim_order = _triangulation_->eliminationOrder();
460 NodeProperty< int > elim_order(Size(JT_elim_order.size()));
461 for (std::size_t i = std::size_t(0), size = JT_elim_order.size(); i < size; ++i)
462 elim_order.insert(JT_elim_order[i], (int)i);
463 NodeSet unobserved_set;
464
465 for (const auto& joint_target: this->jointTargets()) {
466 // here, we need to check that at least one clique contains all the
467 // nodes of the joint target.
468 NodeId first_eliminated_node = std::numeric_limits< NodeId >::max();
469 int elim_number = std::numeric_limits< int >::max();
470 unobserved_set.clear();
471 for (const auto node: joint_target) {
472 if (!_graph_.exists(node)) {
473 if (!hard_ev_nodes.exists(node)) return true;
474 } else {
475 unobserved_set.insert(node);
476 if (elim_order[node] < elim_number) {
477 elim_number = elim_order[node];
478 first_eliminated_node = node;
479 }
480 }
481 }
482 if (!unobserved_set.empty()) {
483 // here, first_eliminated_node contains the first var (node or one of its
484 // parents) eliminated => the clique created during its elimination
485 // should contain all the nodes in unobserved_set
486 const auto clique_id = _node_to_clique_[first_eliminated_node];
487 const auto& clique = _JT_->clique(clique_id);
488 for (const auto node: unobserved_set) {
489 if (!clique.contains(node)) return true;
490 }
491 }
492 }
493
494 // if some new evidence have been added on nodes that do not belong
495 // to _graph_, then we tensorly have to reconstruct the join tree
496 for (const auto& change: _evidence_changes_) {
497 if ((change.second == EvidenceChangeType::EVIDENCE_ADDED) && !_graph_.exists(change.first))
498 return true;
499 }
500
501 // here, the current JT is exactly what we need for the next inference
502 return false;
503 }
504
506 template < GUM_Numeric GUM_SCALAR >
507 void ShaferShenoyInference< GUM_SCALAR >::_createNewJT_() {
508 // to create the JT, we first create the moral graph of the BN in the
509 // following way in order to take into account the barren nodes and the
510 // nodes that received evidence:
511 // 1/ we create an undirected graph containing only the nodes and no edge
512 // 2/ if we take into account barren nodes, remove them from the graph
513 // 3/ if we take d-separation into account, remove the d-separated nodes
514 // 4/ add edges so that each node and its parents in the BN form a clique
515 // 5/ add edges so that joint targets form a clique of the moral graph
516 // 6/ remove the nodes that received hard evidence (by step 4/, their
517 // parents are linked by edges, which is necessary for inference)
518 //
519 // At the end of step 6/, we have our moral graph and we can triangulate it
520 // to get the new junction tree
521
522 // 1/ create an undirected graph containing only the nodes and no edge
523 const auto& bn = this->BN();
524 _graph_.clear();
525 for (const auto node: bn.internalDag())
526 _graph_.addNodeWithId(node);
527
528 // identify the target nodes
529 NodeSet target_nodes = this->targets();
530 for (const auto& nodeset: this->jointTargets()) {
531 target_nodes += nodeset;
532 }
533
534 // 2/ if we wish to exploit barren nodes, we shall remove them from the
535 // BN. To do so: we identify all the nodes that are not targets and have
536 // received no evidence and such that their descendants are neither
537 // targets nor evidence nodes. Such nodes can be safely discarded from
538 // the BN without altering the inference output
539 if ((this->nbrTargets() != bn.internalDag().size())
540 && (_barren_nodes_type_ == FindBarrenNodesType::FIND_BARREN_NODES)) {
541 // check that all the nodes are not targets, otherwise, there is no
542 // barren node
543 if (target_nodes.size() != bn.size()) {
544 BarrenNodesFinder finder(&bn.internalDag());
545 finder.setTargets(&target_nodes);
546
547 NodeSet evidence_nodes(this->evidence().size());
548 for (const auto& pair: this->evidence()) {
549 evidence_nodes.insert(pair.first);
550 }
551 finder.setEvidence(&evidence_nodes);
552
553 NodeSet barren_nodes = finder.barrenNodes();
554
555 // remove the barren nodes from the moral graph
556 for (const auto node: barren_nodes) {
557 _graph_.eraseNode(node);
558 }
559 }
560 }
561
562 // 3/ if we wish to exploit d-separation, remove all the nodes that are
563 // d-separated from our targets. Of course, if all the nodes are targets,
564 // no need to perform a d-separation analysis
565 if (this->nbrTargets() != bn.internalDag().size()) {
566 NodeSet requisite_nodes;
567 bool dsep_analysis = false;
568 switch (_find_relevant_tensor_type_) {
569 case RelevantTensorsFinderType::DSEP_BAYESBALL_TENSORS :
570 case RelevantTensorsFinderType::DSEP_BAYESBALL_NODES : {
571 BayesBall::requisiteNodes(bn.internalDag(),
572 target_nodes,
573 this->hardEvidenceNodes(),
574 this->softEvidenceNodes(),
575 requisite_nodes);
576 dsep_analysis = true;
577 } break;
578
579 case RelevantTensorsFinderType::DSEP_KOLLER_FRIEDMAN_2009 : {
580 dSeparationAlgorithm dsep;
581 dsep.requisiteNodes(bn.internalDag(),
582 target_nodes,
583 this->hardEvidenceNodes(),
584 this->softEvidenceNodes(),
585 requisite_nodes);
586 dsep_analysis = true;
587 } break;
588
589 case RelevantTensorsFinderType::FIND_ALL : break;
590
591 default : GUM_ERROR(FatalError, "not implemented yet")
592 }
593
594 // remove all the nodes that are not requisite
595 if (dsep_analysis) {
596 for (auto iter = _graph_.beginSafe(); iter != _graph_.endSafe(); ++iter) {
597 if (!requisite_nodes.contains(*iter) && !this->hardEvidenceNodes().contains(*iter)) {
598 _graph_.eraseNode(*iter);
599 }
600 }
601 }
602 }
603
604 // 4/ add edges so that each node and its parents in the BN form a clique
605 for (const auto node: _graph_) {
606 const NodeSet& parents = bn.parents(node);
607 for (auto iter1 = parents.cbegin(); iter1 != parents.cend(); ++iter1) {
608 // before adding an edge between node and its parent, check that the
609 // parent belongs to the graph. Actually, when d-separated nodes are
610 // removed, it may be the case that the parents of hard evidence nodes
611 // are removed. But the latter still exist in the graph.
612 if (_graph_.existsNode(*iter1)) {
613 _graph_.addEdge(*iter1, node);
614
615 auto iter2 = iter1;
616 for (++iter2; iter2 != parents.cend(); ++iter2) {
617 // before adding an edge, check that both extremities belong to
618 // the graph. Actually, when d-separated nodes are removed, it may
619 // be the case that the parents of hard evidence nodes are removed.
620 // But the latter still exist in the graph.
621 if (_graph_.existsNode(*iter2)) _graph_.addEdge(*iter1, *iter2);
622 }
623 }
624 }
625 }
626
627 // 5/ if there exist some joint targets, we shall add new edges
628 // into the moral graph in order to ensure that there exists a clique
629 // containing each joint
630 for (const auto& nodeset: this->jointTargets()) {
631 for (auto iter1 = nodeset.cbegin(); iter1 != nodeset.cend(); ++iter1) {
632 auto iter2 = iter1;
633 for (++iter2; iter2 != nodeset.cend(); ++iter2) {
634 _graph_.addEdge(*iter1, *iter2);
635 }
636 }
637 }
638
639 // 6/ remove all the nodes that received hard evidence
640 _hard_ev_nodes_ = this->hardEvidenceNodes();
641 for (const auto node: _hard_ev_nodes_) {
642 _graph_.eraseNode(node);
643 }
644
645
646 // now, we can compute the new junction tree. To speed-up computations
647 // (essentially, those of a distribution phase), we construct from this
648 // junction tree a binary join tree
649 if (_JT_ != nullptr) delete _JT_;
650 if (_junctionTree_ != nullptr) delete _junctionTree_;
651
652 _triangulation_->setGraph(&_graph_, &(this->domainSizes()));
653 const JunctionTree& triang_jt = _triangulation_->junctionTree();
654 if (_use_binary_join_tree_) {
655 BinaryJoinTreeConverterDefault bjt_converter;
656 NodeSet emptyset;
657 _JT_ = new CliqueGraph(bjt_converter.convert(triang_jt, this->domainSizes(), emptyset));
658 } else {
659 _JT_ = new CliqueGraph(triang_jt);
660 }
661 _junctionTree_ = new CliqueGraph(triang_jt);
662
663
664 // indicate, for each node of the moral graph, a clique in _JT_ that can
665 // contain its conditional probability table
666 _node_to_clique_.clear();
667 const std::vector< NodeId >& JT_elim_order = _triangulation_->eliminationOrder();
668 NodeProperty< int > elim_order(Size(JT_elim_order.size()));
669 for (std::size_t i = std::size_t(0), size = JT_elim_order.size(); i < size; ++i)
670 elim_order.insert(JT_elim_order[i], (int)i);
671 const DAG& dag = bn.internalDag();
672 for (const auto node: _graph_) {
673 // get the variables in the tensor of node (and its parents)
674 NodeId first_eliminated_node = node;
675 int elim_number = elim_order[first_eliminated_node];
676
677 for (const auto parent: dag.parents(node)) {
678 if (_graph_.existsNode(parent) && (elim_order[parent] < elim_number)) {
679 elim_number = elim_order[parent];
680 first_eliminated_node = parent;
681 }
682 }
683
684 // first_eliminated_node contains the first var (node or one of its
685 // parents) eliminated => the clique created during its elimination
686 // contains node and all of its parents => it can contain the tensor
687 // assigned to the node in the BN
688 _node_to_clique_.insert(node,
689 _triangulation_->createdJunctionTreeClique(first_eliminated_node));
690 }
691
692 // do the same for the nodes that received hard evidence. Here, we only store
693 // the nodes for which at least one parent belongs to _graph_ (otherwise
694 // their CPT is just a constant real number).
695 for (const auto node: _hard_ev_nodes_) {
696 NodeId first_eliminated_node = std::numeric_limits< NodeId >::max();
697 int elim_number = std::numeric_limits< int >::max();
698
699 for (const auto parent: dag.parents(node)) {
700 if (_graph_.exists(parent) && (elim_order[parent] < elim_number)) {
701 elim_number = elim_order[parent];
702 first_eliminated_node = parent;
703 }
704 }
705
706 // first_eliminated_node contains the first var (node or one of its
707 // parents) eliminated => the clique created during its elimination
708 // contains node and all of its parents => it can contain the tensor
709 // assigned to the node in the BN
710 if (elim_number != std::numeric_limits< int >::max()) {
711 _node_to_clique_.insert(node,
712 _triangulation_->createdJunctionTreeClique(first_eliminated_node));
713 }
714 }
715
716 // indicate for each joint_target a clique that contains it
717 _joint_target_to_clique_.clear();
718 for (const auto& set: this->jointTargets()) {
719 NodeId first_eliminated_node = std::numeric_limits< NodeId >::max();
720 int elim_number = std::numeric_limits< int >::max();
721
722 // do not take into account the nodes that received hard evidence
723 // (since they do not belong to the join tree)
724 for (const auto node: set) {
725 if (!_hard_ev_nodes_.contains(node)) {
726 // the clique we are looking for is the one that was created when
727 // the first element of nodeset was eliminated
728 if (elim_order[node] < elim_number) {
729 elim_number = elim_order[node];
730 first_eliminated_node = node;
731 }
732 }
733 }
734
735 if (elim_number != std::numeric_limits< int >::max()) {
736 _joint_target_to_clique_.insert(
737 set,
738 _triangulation_->createdJunctionTreeClique(first_eliminated_node));
739 }
740 }
741
742 // compute the roots of _JT_'s connected components
743 _computeJoinTreeRoots_();
744
745 // remove all the tensors stored into the cliques. Note that these include
746 // the CPTs resulting from the projections of hard evidence as well as the
747 // CPTs of the soft evidence
748 for (const auto& pot: _clique_ss_tensor_) {
749 if (_clique_tensors_[pot.first].size() > 1) delete pot.second;
750 }
751 _clique_ss_tensor_.clear();
752 for (const auto& potlist: _clique_tensors_)
753 for (const auto pot: potlist.second)
754 delete pot;
755 _clique_tensors_.clear();
756
757 // remove all the tensors created during the last inference
758 for (const auto& pot: _arc_to_created_tensors_)
759 delete pot.second;
760 _arc_to_created_tensors_.clear();
761
762 // remove all the tensors created to take into account hard evidence
763 // during the last inference (they have already been deleted from memory
764 // by the clearing of _clique_tensors_).
765 _node_to_hard_ev_projected_CPTs_.clear();
766
767 // remove all the soft evidence.
768 _node_to_soft_evidence_.clear();
769
770 // create empty tensor lists into the cliques of the joint tree as well
771 // as empty lists of evidence
772 _ScheduleMultiDimSet_ empty_set;
773 for (const auto node: *_JT_) {
774 _clique_tensors_.insert(node, empty_set);
775 _clique_ss_tensor_.insert(node, nullptr);
776 }
777
778 // remove all the constants created due to projections of CPTs that were
779 // defined over only hard evidence nodes
780 _constants_.clear();
781
782 // create empty messages and indicate that no message has been computed yet
783 _separator_tensors_.clear();
784 _messages_computed_.clear();
785 for (const auto& edge: _JT_->edges()) {
786 const Arc arc1(edge.first(), edge.second());
787 _separator_tensors_.insert(arc1, nullptr);
788 _messages_computed_.insert(arc1, false);
789 const Arc arc2(edge.second(), edge.first());
790 _separator_tensors_.insert(arc2, nullptr);
791 _messages_computed_.insert(arc2, false);
792 }
793
794 // remove all the posteriors computed so far
795 for (const auto& pot: _target_posteriors_)
796 delete pot.second;
797 _target_posteriors_.clear();
798 for (const auto& pot: _joint_target_posteriors_)
799 delete pot.second;
800 _joint_target_posteriors_.clear();
801
802 // here, we determine whether we should use schedules during the inference.
803 // the rule is: if the sum of the domain sizes of the cliques is greater
804 // than a threshold, use schedules
805 double overall_size = 0;
806 for (const auto clique: *_JT_) {
807 double clique_size = 1.0;
808 for (const auto node: _JT_->clique(clique))
809 clique_size *= this->domainSizes()[node];
810 overall_size += clique_size;
811 }
812 _use_schedules_ = (overall_size > _schedule_threshold_);
813
814 // we shall now add all the tensors of the soft evidence to the cliques
815 const NodeProperty< const Tensor< GUM_SCALAR >* >& evidence = this->evidence();
816 for (const auto node: this->softEvidenceNodes()) {
817 if (auto ptr_clique = _node_to_clique_.tryGet(node)) {
818 auto ev_pot = new ScheduleMultiDim< Tensor< GUM_SCALAR > >(*evidence[node], false);
819 _node_to_soft_evidence_.insert(node, ev_pot);
820 _clique_tensors_[*ptr_clique].insert(ev_pot);
821 }
822 }
823
824 // put all the CPTs of the Bayes net nodes into the cliques
825 // here, beware: all the tensors that are defined over some nodes
826 // including hard evidence must be projected so that these nodes are
827 // removed from the tensor
828 if (_use_schedules_) {
829 Schedule schedule;
830 _initializeJTCliques_(schedule);
831 } else {
832 _initializeJTCliques_();
833 }
834
835
836 // indicate that the data structures are up to date.
837 _evidence_changes_.clear();
838 _is_new_jt_needed_ = false;
839 }
840
842 template < GUM_Numeric GUM_SCALAR >
843 void ShaferShenoyInference< GUM_SCALAR >::_initializeJTCliques_() {
844 const auto& bn = this->BN();
845 const DAG& dag = bn.internalDag();
846
847 // put all the CPTs of the Bayes net nodes into the cliques
848 // here, beware: all the tensors that are defined over some nodes
849 // including hard evidence must be projected so that these nodes are
850 // removed from the tensor
851 const NodeProperty< const Tensor< GUM_SCALAR >* >& evidence = this->evidence();
852 const NodeProperty< Idx >& hard_evidence = this->hardEvidence();
853
854 for (const auto node: dag) {
855 if (_graph_.exists(node) || _hard_ev_nodes_.contains(node)) {
856 const Tensor< GUM_SCALAR >& cpt = bn.cpt(node);
857
858 // get the list of nodes with hard evidence in cpt
859 NodeSet hard_nodes;
860 const auto& variables = cpt.variablesSequence();
861 bool graph_contains_nodes = false;
862 for (const auto var: variables) {
863 NodeId xnode = bn.nodeId(*var);
864 if (_hard_ev_nodes_.contains(xnode)) hard_nodes.insert(xnode);
865 else if (_graph_.exists(xnode)) graph_contains_nodes = true;
866 }
867
868 // if hard_nodes contains hard evidence nodes, perform a projection
869 // and insert the result into the appropriate clique, else insert
870 // directly cpt into the clique
871 if (hard_nodes.empty()) {
872 auto sched_cpt = new ScheduleMultiDim< Tensor< GUM_SCALAR > >(cpt, false);
873 _clique_tensors_[_node_to_clique_[node]].insert(sched_cpt);
874 } else {
875 // marginalize out the hard evidence nodes: if the cpt is defined
876 // only over nodes that received hard evidence, do not consider it
877 // as a tensor anymore but as a constant
878 // TODO substitute constants by 0-dimensional tensors
879 if (hard_nodes.size() == variables.size()) {
880 Instantiation inst(cpt);
881 for (Size i = 0; i < hard_nodes.size(); ++i) {
882 inst.chgVal(*variables[i], hard_evidence[bn.nodeId(*(variables[i]))]);
883 }
884 _constants_.insert(node, cpt.get(inst));
885 } else {
886 // here, we have a CPT defined over some nodes that received hard
887 // evidence and other nodes that did not receive it. If none of the
888 // latter belong to the graph, then the CPT is useless for inference
889 if (!graph_contains_nodes) continue;
890
891 // prepare the projection with a combine and project instance
892 gum::VariableSet hard_variables;
893 _TensorSet_ marg_cpt_set(1 + hard_nodes.size());
894 marg_cpt_set.insert(&cpt);
895 for (const auto xnode: hard_nodes) {
896 marg_cpt_set.insert(evidence[xnode]);
897 hard_variables.insert(&(bn.variable(xnode)));
898 }
899
900 // perform the combination of those tensors and their projection
901 MultiDimCombineAndProjectDefault< Tensor< GUM_SCALAR > > combine_and_project(
902 _combination_op_,
903 _projection_op_);
904
905 _TensorSet_ new_cpt_list = combine_and_project.execute(marg_cpt_set, hard_variables);
906
907 // there should be only one tensor in new_cpt_list
908 if (new_cpt_list.size() != 1) {
909 for (const auto pot: new_cpt_list)
910 if (!marg_cpt_set.contains(pot)) delete pot;
911
913 "the projection of a tensor containing " << "hard evidence is empty!");
914 }
915 auto new_pot = const_cast< Tensor< GUM_SCALAR >* >(*(new_cpt_list.begin()));
916 auto projected_pot = new ScheduleMultiDim< Tensor< GUM_SCALAR > >(std::move(*new_pot));
917 delete new_pot;
918
919 _clique_tensors_[_node_to_clique_[node]].insert(projected_pot);
920 _node_to_hard_ev_projected_CPTs_.insert(node, projected_pot);
921 }
922 }
923 }
924 }
925
926 // now, in _clique_tensors_, for each clique, we have the list of
927 // tensors that must be combined in order to produce the Shafer-Shenoy's
928 // tensor stored into the clique. So, perform this combination and
929 // store the result in _clique_ss_tensor_
930 MultiDimCombinationDefault< Tensor< GUM_SCALAR > > fast_combination(_combination_op_);
931 for (const auto& xpotset: _clique_tensors_) {
932 const auto& potset = xpotset.second;
933 if (potset.size() > 0) {
934 // here, there will be an entry in _clique_ss_tensor_
935 // If there is only one element in potset, this element shall be
936 // stored into _clique_ss_tensor_, else all the elements of potset
937 // shall be combined and their result shall be stored
938 if (potset.size() == 1) {
939 _clique_ss_tensor_[xpotset.first] = *(potset.cbegin());
940 } else {
941 _TensorSet_ p_potset(potset.size());
942 for (const auto pot: potset)
943 p_potset.insert(
944 &(static_cast< const ScheduleMultiDim< Tensor< GUM_SCALAR > >* >(pot)->multiDim()));
945
946 Tensor< GUM_SCALAR >* joint
947 = const_cast< Tensor< GUM_SCALAR >* >(fast_combination.execute(p_potset));
948 _clique_ss_tensor_[xpotset.first]
949 = new ScheduleMultiDim< Tensor< GUM_SCALAR > >(std::move(*joint));
950 delete joint;
951 }
952 }
953 }
954 }
955
957 template < GUM_Numeric GUM_SCALAR >
958 void ShaferShenoyInference< GUM_SCALAR >::_initializeJTCliques_(Schedule& schedule) {
959 const auto& bn = this->BN();
960 const DAG& dag = bn.internalDag();
961
962 // put all the CPTs of the Bayes net nodes into the cliques
963 // here, beware: all the tensors that are defined over some nodes
964 // including hard evidence must be projected so that these nodes are
965 // removed from the tensor
966 const NodeProperty< const Tensor< GUM_SCALAR >* >& evidence = this->evidence();
967 const NodeProperty< Idx >& hard_evidence = this->hardEvidence();
968
969 for (const auto node: dag) {
970 if (_graph_.exists(node) || _hard_ev_nodes_.contains(node)) {
971 const Tensor< GUM_SCALAR >& cpt = bn.cpt(node);
972
973 // get the list of nodes with hard evidence in cpt
974 NodeSet hard_nodes;
975 const auto& variables = cpt.variablesSequence();
976 bool graph_contains_nodes = false;
977 for (const auto var: variables) {
978 NodeId xnode = bn.nodeId(*var);
979 if (_hard_ev_nodes_.contains(xnode)) hard_nodes.insert(xnode);
980 else if (_graph_.exists(xnode)) graph_contains_nodes = true;
981 }
982
983 // if hard_nodes contains hard evidence nodes, perform a projection
984 // and insert the result into the appropriate clique, else insert
985 // directly cpt into the clique
986 if (hard_nodes.empty()) {
987 auto sched_cpt = new ScheduleMultiDim< Tensor< GUM_SCALAR > >(cpt, false);
988 _clique_tensors_[_node_to_clique_[node]].insert(sched_cpt);
989 } else {
990 // marginalize out the hard evidence nodes: if the cpt is defined
991 // only over nodes that received hard evidence, do not consider it
992 // as a tensor anymore but as a constant
993 // TODO substitute constants by 0-dimensional tensors
994 if (hard_nodes.size() == variables.size()) {
995 Instantiation inst(cpt);
996 for (Size i = 0; i < hard_nodes.size(); ++i) {
997 inst.chgVal(*variables[i], hard_evidence[bn.nodeId(*(variables[i]))]);
998 }
999 _constants_.insert(node, cpt.get(inst));
1000 } else {
1001 // here, we have a CPT defined over some nodes that received hard
1002 // evidence and other nodes that did not receive it. If none of the
1003 // latter belong to the graph, then the CPT is useless for inference
1004 if (!graph_contains_nodes) continue;
1005
1006 // prepare the projection with a combine and project instance
1007 gum::VariableSet hard_variables;
1008 _ScheduleMultiDimSet_ marg_cpt_set(1 + hard_nodes.size());
1009 const IScheduleMultiDim* sched_cpt
1010 = schedule.insertTable< Tensor< GUM_SCALAR > >(cpt, false);
1011 marg_cpt_set.insert(sched_cpt);
1012
1013 for (const auto xnode: hard_nodes) {
1014 const IScheduleMultiDim* pot
1015 = schedule.insertTable< Tensor< GUM_SCALAR > >(*evidence[xnode], false);
1016 marg_cpt_set.insert(pot);
1017 hard_variables.insert(&(bn.variable(xnode)));
1018 }
1019
1020 // perform the combination of those tensors and their projection
1021 MultiDimCombineAndProjectDefault< Tensor< GUM_SCALAR > > combine_and_project(
1022 _combination_op_,
1023 _projection_op_);
1024
1025 _ScheduleMultiDimSet_ new_cpt_list
1026 = combine_and_project.schedule(schedule, marg_cpt_set, hard_variables);
1027
1028 // there should be only one tensor in new_cpt_list
1029 if (new_cpt_list.size() != 1) {
1031 "the projection of a tensor containing " << "hard evidence is empty!");
1032 }
1033 auto projected_pot = const_cast< ScheduleMultiDim< Tensor< GUM_SCALAR > >* >(
1034 static_cast< const ScheduleMultiDim< Tensor< GUM_SCALAR > >* >(
1035 *new_cpt_list.begin()));
1036 const_cast< ScheduleOperator* >(schedule.scheduleMultiDimCreator(projected_pot))
1037 ->makeResultsPersistent(true);
1038 _clique_tensors_[_node_to_clique_[node]].insert(projected_pot);
1039 _node_to_hard_ev_projected_CPTs_.insert(node, projected_pot);
1040 }
1041 }
1042 }
1043 }
1044 this->scheduler().execute(schedule);
1045
1046 // now, in _clique_tensors_, for each clique, we have the list of
1047 // tensors that must be combined in order to produce the Shafer-Shenoy's
1048 // tensor stored into the clique. So, perform this combination and
1049 // store the result in _clique_ss_tensor_
1050 schedule.clear();
1051 MultiDimCombinationDefault< Tensor< GUM_SCALAR > > fast_combination(_combination_op_);
1052 for (const auto& xpotset: _clique_tensors_) {
1053 const auto& potset = xpotset.second;
1054 if (potset.size() > 0) {
1055 // here, there will be an entry in _clique_ss_tensor_
1056 // If there is only one element in potset, this element shall be
1057 // stored into _clique_ss_tensor_, else all the elements of potset
1058 // shall be combined and their result shall be stored
1059 if (potset.size() == 1) {
1060 _clique_ss_tensor_[xpotset.first] = *(potset.cbegin());
1061 } else {
1062 // add the tables to combine into the schedule
1063 for (const auto pot: potset) {
1064 schedule.emplaceScheduleMultiDim(*pot);
1065 }
1066
1067 auto joint = const_cast< ScheduleMultiDim< Tensor< GUM_SCALAR > >* >(
1068 static_cast< const ScheduleMultiDim< Tensor< GUM_SCALAR > >* >(
1069 fast_combination.schedule(schedule, potset)));
1070 const_cast< ScheduleOperator* >(schedule.scheduleMultiDimCreator(joint))
1071 ->makeResultsPersistent(true);
1072 _clique_ss_tensor_[xpotset.first] = joint;
1073 }
1074 }
1075 }
1076 this->scheduler().execute(schedule);
1077 }
1078
1080 template < GUM_Numeric GUM_SCALAR >
1081 void ShaferShenoyInference< GUM_SCALAR >::updateOutdatedStructure_() {
1082 // check if a new JT is really needed. If so, create it
1083 if (_isNewJTNeeded_()) {
1084 _createNewJT_();
1085 } else {
1086 // here, we can answer the next queries without reconstructing all the
1087 // junction tree. All we need to do is to indicate that we should
1088 // update the tensors and messages for these queries
1089 updateOutdatedTensors_();
1090 }
1091 }
1092
1094 template < GUM_Numeric GUM_SCALAR >
1095 void ShaferShenoyInference< GUM_SCALAR >::_diffuseMessageInvalidations_(
1096 NodeId from_id,
1097 NodeId to_id,
1098 NodeSet& invalidated_cliques) {
1099 // invalidate the current clique
1100 invalidated_cliques.insert(to_id);
1101
1102 // invalidate the current arc
1103 const Arc arc(from_id, to_id);
1104 bool& message_computed = _messages_computed_[arc];
1105 if (message_computed) {
1106 message_computed = false;
1107 _separator_tensors_[arc] = nullptr;
1108 if (_arc_to_created_tensors_.exists(arc)) {
1109 delete _arc_to_created_tensors_[arc];
1110 _arc_to_created_tensors_.erase(arc);
1111 }
1112
1113 // go on with the diffusion
1114 for (const auto node_id: _JT_->neighbours(to_id)) {
1115 if (node_id != from_id) _diffuseMessageInvalidations_(to_id, node_id, invalidated_cliques);
1116 }
1117 }
1118 }
1119
1122 template < GUM_Numeric GUM_SCALAR >
1123 void ShaferShenoyInference< GUM_SCALAR >::updateOutdatedTensors_() {
1124 // for each clique, indicate whether the tensor stored into
1125 // _clique_ss_tensor_[clique] is the result of a combination. In this
1126 // case, it has been allocated by the combination and will need to be
1127 // deallocated if its clique has been invalidated
1128 NodeProperty< bool > ss_tensor_to_deallocate(_clique_tensors_.size());
1129 for (const auto& potset: _clique_tensors_) {
1130 ss_tensor_to_deallocate.insert(potset.first, (potset.second.size() > 1));
1131 }
1132
1133 // compute the set of CPTs that were projected due to hard evidence and
1134 // whose hard evidence have changed, so that they need a new projection.
1135 // By the way, remove these CPTs since they are no more needed
1136 // Here only the values of the hard evidence can have changed (else a
1137 // fully new join tree would have been computed).
1138 // Note also that we know that the CPTs still contain some variable(s) after
1139 // the projection (else they should be constants)
1140 NodeSet hard_nodes_changed(_hard_ev_nodes_.size());
1141 for (const auto node: _hard_ev_nodes_)
1142 if (_evidence_changes_.exists(node)) hard_nodes_changed.insert(node);
1143
1144 NodeSet nodes_with_projected_CPTs_changed;
1145 const auto& bn = this->BN();
1146 for (auto pot_iter = _node_to_hard_ev_projected_CPTs_.beginSafe();
1147 pot_iter != _node_to_hard_ev_projected_CPTs_.endSafe();
1148 ++pot_iter) {
1149 for (const auto var: bn.cpt(pot_iter.key()).variablesSequence()) {
1150 if (hard_nodes_changed.contains(bn.nodeId(*var))) {
1151 nodes_with_projected_CPTs_changed.insert(pot_iter.key());
1152 delete pot_iter.val();
1153 _clique_tensors_[_node_to_clique_[pot_iter.key()]].erase(pot_iter.val());
1154 _node_to_hard_ev_projected_CPTs_.erase(pot_iter);
1155 break;
1156 }
1157 }
1158 }
1159
1160
1161 // invalidate all the messages that are no more correct: start from each of
1162 // the nodes whose soft evidence has changed and perform a diffusion from
1163 // the clique into which the soft evidence has been entered, indicating that
1164 // the messages spreading from this clique are now invalid. At the same time,
1165 // if there were tensors created on the arcs over which the messages were
1166 // sent, remove them from memory. For all the cliques that received some
1167 // projected CPT that should now be changed, do the same.
1168 NodeSet invalidated_cliques(_JT_->size());
1169 for (const auto& pair: _evidence_changes_) {
1170 if (auto ptr_clique = _node_to_clique_.tryGet(pair.first)) {
1171 const auto clique = *ptr_clique;
1172 invalidated_cliques.insert(clique);
1173 for (const auto neighbor: _JT_->neighbours(clique)) {
1174 _diffuseMessageInvalidations_(clique, neighbor, invalidated_cliques);
1175 }
1176 }
1177 }
1178
1179 // now, add to the set of invalidated cliques those that contain projected
1180 // CPTs that were changed.
1181 for (const auto node: nodes_with_projected_CPTs_changed) {
1182 const auto clique = _node_to_clique_[node];
1183 invalidated_cliques.insert(clique);
1184 for (const auto neighbor: _JT_->neighbours(clique)) {
1185 _diffuseMessageInvalidations_(clique, neighbor, invalidated_cliques);
1186 }
1187 }
1188
1189 // now that we know the cliques whose set of tensors have been changed,
1190 // we can discard their corresponding Shafer-Shenoy tensor
1191 for (const auto clique: invalidated_cliques) {
1192 if (ss_tensor_to_deallocate[clique]) {
1193 delete _clique_ss_tensor_[clique];
1194 _clique_ss_tensor_[clique] = nullptr;
1195 }
1196 }
1197
1198
1199 // now we shall remove all the posteriors that belong to the
1200 // invalidated cliques. First, cope only with the nodes that did not
1201 // receive hard evidence since the other nodes do not belong to the
1202 // join tree
1203 for (auto iter = _target_posteriors_.beginSafe(); iter != _target_posteriors_.endSafe();
1204 ++iter) {
1205 if (_graph_.exists(iter.key())
1206 && (invalidated_cliques.exists(_node_to_clique_[iter.key()]))) {
1207 delete iter.val();
1208 _target_posteriors_.erase(iter);
1209 }
1210 }
1211
1212 // now cope with the nodes that received hard evidence
1213 for (auto iter = _target_posteriors_.beginSafe(); iter != _target_posteriors_.endSafe();
1214 ++iter) {
1215 if (hard_nodes_changed.contains(iter.key())) {
1216 delete iter.val();
1217 _target_posteriors_.erase(iter);
1218 }
1219 }
1220
1221 // finally, cope with joint targets. Notably, remove the joint posteriors whose
1222 // nodes have all received changed evidence
1223 for (auto iter = _joint_target_posteriors_.beginSafe();
1224 iter != _joint_target_posteriors_.endSafe();
1225 ++iter) {
1226 // a posterior without clique (e.g. its declared target has no clique) is computed again on
1227 // demand
1228 const auto clique = _joint_target_to_clique_.tryGet(iter.key());
1229 if (!clique || invalidated_cliques.exists(*clique)) {
1230 delete iter.val();
1231 _joint_target_posteriors_.erase(iter);
1232 } else {
1233 // check for sets in which all nodes have received evidence
1234 bool has_unevidenced_node = false;
1235 for (const auto node: iter.key()) {
1236 if (!hard_nodes_changed.exists(node)) {
1237 has_unevidenced_node = true;
1238 break;
1239 }
1240 }
1241 if (!has_unevidenced_node) {
1242 delete iter.val();
1243 _joint_target_posteriors_.erase(iter);
1244 }
1245 }
1246 }
1247
1248 // remove all the evidence that were entered into _node_to_soft_evidence_
1249 // and _clique_ss_tensor_ and add the new soft ones
1250 for (const auto& pot_pair: _node_to_soft_evidence_) {
1251 delete pot_pair.second;
1252 _clique_tensors_[_node_to_clique_[pot_pair.first]].erase(pot_pair.second);
1253 }
1254 _node_to_soft_evidence_.clear();
1255
1256 const auto& evidence = this->evidence();
1257 for (const auto node: this->softEvidenceNodes()) {
1258 auto ev_pot = new ScheduleMultiDim< Tensor< GUM_SCALAR > >(*evidence[node], false);
1259 _node_to_soft_evidence_.insert(node, ev_pot);
1260 _clique_tensors_[_node_to_clique_[node]].insert(ev_pot);
1261 }
1262
1263
1264 // Now add the projections of the CPTs due to newly changed hard evidence:
1265 // if we are performing updateOutdatedTensors_, this means that the
1266 // set of nodes that received hard evidence has not changed, only
1267 // their instantiations can have changed. So, if there is an entry
1268 // for node in _constants_, there will still be such an entry after
1269 // performing the new projections. Idem for _node_to_hard_ev_projected_CPTs_
1270 if (_use_schedules_) {
1271 Schedule schedule;
1272 for (const auto node: nodes_with_projected_CPTs_changed) {
1273 // perform the projection with a combine and project instance
1274 const Tensor< GUM_SCALAR >& cpt = bn.cpt(node);
1275 const auto& variables = cpt.variablesSequence();
1276 _ScheduleMultiDimSet_ marg_cpt_set;
1277 const auto sched_cpt = schedule.insertTable< Tensor< GUM_SCALAR > >(cpt, false);
1278 marg_cpt_set.insert(sched_cpt);
1279
1280 gum::VariableSet hard_variables;
1281 for (const auto var: variables) {
1282 NodeId xnode = bn.nodeId(*var);
1283 if (_hard_ev_nodes_.exists(xnode)) {
1284 const auto pot = schedule.insertTable< Tensor< GUM_SCALAR > >(*evidence[xnode], false);
1285 marg_cpt_set.insert(pot);
1286 hard_variables.insert(var);
1287 }
1288 }
1289
1290 // perform the combination of those tensors and their projection
1291 MultiDimCombineAndProjectDefault< Tensor< GUM_SCALAR > > combine_and_project(
1292 _combination_op_,
1293 _projection_op_);
1294
1295 _ScheduleMultiDimSet_ new_cpt_list
1296 = combine_and_project.schedule(schedule, marg_cpt_set, hard_variables);
1297
1298 // there should be only one tensor in new_cpt_list
1299 if (new_cpt_list.size() != 1) {
1301 "the projection of a tensor containing " << "hard evidence is empty!");
1302 }
1303 auto projected_pot = const_cast< ScheduleMultiDim< Tensor< GUM_SCALAR > >* >(
1304 static_cast< const ScheduleMultiDim< Tensor< GUM_SCALAR > >* >(*new_cpt_list.begin()));
1305 const_cast< ScheduleOperator* >(schedule.scheduleMultiDimCreator(projected_pot))
1306 ->makeResultsPersistent(true);
1307 _clique_tensors_[_node_to_clique_[node]].insert(projected_pot);
1308 _node_to_hard_ev_projected_CPTs_.insert(node, projected_pot);
1309 }
1310
1311 // here, the list of tensors stored in the invalidated cliques have
1312 // been updated. So, now, we can combine them to produce the Shafer-Shenoy
1313 // tensor stored into the clique
1314 MultiDimCombinationDefault< Tensor< GUM_SCALAR > > fast_combination(_combination_op_);
1315 for (const auto clique: invalidated_cliques) {
1316 const auto& potset = _clique_tensors_[clique];
1317
1318 if (potset.size() > 0) {
1319 // here, there will be an entry in _clique_ss_tensor_
1320 // If there is only one element in potset, this element shall be
1321 // stored into _clique_ss_tensor_, else all the elements of potset
1322 // shall be combined and their result shall be stored
1323 if (potset.size() == 1) {
1324 _clique_ss_tensor_[clique] = *(potset.cbegin());
1325 } else {
1326 for (const auto pot: potset)
1327 if (!schedule.existsScheduleMultiDim(pot->id()))
1328 schedule.emplaceScheduleMultiDim(*pot);
1329 auto joint = const_cast< ScheduleMultiDim< Tensor< GUM_SCALAR > >* >(
1330 static_cast< const ScheduleMultiDim< Tensor< GUM_SCALAR > >* >(
1331 fast_combination.schedule(schedule, potset)));
1332 const_cast< ScheduleOperator* >(schedule.scheduleMultiDimCreator(joint))
1333 ->makeResultsPersistent(true);
1334 _clique_ss_tensor_[clique] = joint;
1335 }
1336 }
1337 }
1338 this->scheduler().execute(schedule);
1339 } else {
1340 for (const auto node: nodes_with_projected_CPTs_changed) {
1341 // perform the projection with a combine and project instance
1342 const Tensor< GUM_SCALAR >& cpt = bn.cpt(node);
1343 const auto& variables = cpt.variablesSequence();
1344 _TensorSet_ marg_cpt_set(1 + variables.size());
1345 marg_cpt_set.insert(&cpt);
1346
1347 gum::VariableSet hard_variables;
1348 for (const auto var: variables) {
1349 NodeId xnode = bn.nodeId(*var);
1350 if (_hard_ev_nodes_.exists(xnode)) {
1351 marg_cpt_set.insert(evidence[xnode]);
1352 hard_variables.insert(var);
1353 }
1354 }
1355
1356 // perform the combination of those tensors and their projection
1357 MultiDimCombineAndProjectDefault< Tensor< GUM_SCALAR > > combine_and_project(
1358 _combination_op_,
1359 _projection_op_);
1360
1361 _TensorSet_ new_cpt_list = combine_and_project.execute(marg_cpt_set, hard_variables);
1362
1363 // there should be only one tensor in new_cpt_list
1364 if (new_cpt_list.size() != 1) {
1365 for (const auto pot: new_cpt_list)
1366 if (!marg_cpt_set.contains(pot)) delete pot;
1367
1369 "the projection of a tensor containing " << "hard evidence is empty!");
1370 }
1371 Tensor< GUM_SCALAR >* xprojected_pot
1372 = const_cast< Tensor< GUM_SCALAR >* >(*new_cpt_list.begin());
1373 auto projected_pot
1374 = new ScheduleMultiDim< Tensor< GUM_SCALAR > >(std::move(*xprojected_pot));
1375 delete xprojected_pot;
1376 _clique_tensors_[_node_to_clique_[node]].insert(projected_pot);
1377 _node_to_hard_ev_projected_CPTs_.insert(node, projected_pot);
1378 }
1379
1380 // here, the list of tensors stored in the invalidated cliques have
1381 // been updated. So, now, we can combine them to produce the Shafer-Shenoy
1382 // tensor stored into the clique
1383 MultiDimCombinationDefault< Tensor< GUM_SCALAR > > fast_combination(_combination_op_);
1384 for (const auto clique: invalidated_cliques) {
1385 const auto& potset = _clique_tensors_[clique];
1386
1387 if (potset.size() > 0) {
1388 // here, there will be an entry in _clique_ss_tensor_
1389 // If there is only one element in potset, this element shall be
1390 // stored into _clique_ss_tensor_, else all the elements of potset
1391 // shall be combined and their result shall be stored
1392 if (potset.size() == 1) {
1393 _clique_ss_tensor_[clique] = *(potset.cbegin());
1394 } else {
1395 _TensorSet_ p_potset(potset.size());
1396 for (const auto pot: potset)
1397 p_potset.insert(&(
1398 static_cast< const ScheduleMultiDim< Tensor< GUM_SCALAR > >* >(pot)->multiDim()));
1399
1400 Tensor< GUM_SCALAR >* joint
1401 = const_cast< Tensor< GUM_SCALAR >* >(fast_combination.execute(p_potset));
1402 _clique_ss_tensor_[clique]
1403 = new ScheduleMultiDim< Tensor< GUM_SCALAR > >(std::move(*joint));
1404 delete joint;
1405 }
1406 }
1407 }
1408 }
1409
1410 // update the constants
1411 const auto& hard_evidence = this->hardEvidence();
1412 for (auto& node_cst: _constants_) {
1413 const Tensor< GUM_SCALAR >& cpt = bn.cpt(node_cst.first);
1414 const auto& variables = cpt.variablesSequence();
1415 Instantiation inst;
1416 for (const auto var: variables)
1417 inst << *var;
1418 for (const auto var: variables) {
1419 inst.chgVal(*var, hard_evidence[bn.nodeId(*var)]);
1420 }
1421 node_cst.second = cpt.get(inst);
1422 }
1423
1424 // indicate that all changes have been performed
1425 _evidence_changes_.clear();
1426 }
1427
1429 template < GUM_Numeric GUM_SCALAR >
1430 void ShaferShenoyInference< GUM_SCALAR >::_computeJoinTreeRoots_() {
1431 // get the set of cliques in which we can find the targets and joint_targets.
1432 // Due to hard evidence, the cliques related to a given target node
1433 // might not exist, hence the if checks
1434 NodeSet clique_targets;
1435 for (const auto node: this->targets()) {
1436 if (auto ptr_clique = _node_to_clique_.tryGet(node)) { clique_targets.insert(*ptr_clique); }
1437 }
1438 for (const auto& set: this->jointTargets()) {
1439 if (auto ptr_clique = _joint_target_to_clique_.tryGet(set)) {
1440 clique_targets.insert(*ptr_clique);
1441 }
1442 }
1443
1444 // one root per connected component (every component needs one: its mass is required by
1445 // evidenceProbability), the cliques containing targets being preferred
1446 _roots_ = junctionTreeRoots(*_JT_, this->BN(), clique_targets);
1447 }
1448
1449 // find the tensors d-connected to a set of variables
1450 template < GUM_Numeric GUM_SCALAR >
1451 void ShaferShenoyInference< GUM_SCALAR >::_findRelevantTensorsGetAll_(
1452 Set< const IScheduleMultiDim* >& pot_list,
1453 gum::VariableSet& kept_vars) {}
1454
1455 // find the tensors d-connected to a set of variables
1456 template < GUM_Numeric GUM_SCALAR >
1457 void ShaferShenoyInference< GUM_SCALAR >::_findRelevantTensorsWithdSeparation_(
1458 Set< const IScheduleMultiDim* >& pot_list,
1459 gum::VariableSet& kept_vars) {
1460 // find the node ids of the kept variables
1461 NodeSet kept_ids(kept_vars.size());
1462 const auto& bn = this->BN();
1463 for (const auto var: kept_vars) {
1464 kept_ids.insert(bn.nodeId(*var));
1465 }
1466
1467 // determine the set of tensors d-connected with the kept variables
1468 NodeSet requisite_nodes;
1469 BayesBall::requisiteNodes(bn.internalDag(),
1470 kept_ids,
1471 this->hardEvidenceNodes(),
1472 this->softEvidenceNodes(),
1473 requisite_nodes);
1474 for (auto iter = pot_list.beginSafe(); iter != pot_list.endSafe(); ++iter) {
1475 const Sequence< const DiscreteVariable* >& vars = (*iter)->variablesSequence();
1476 bool found = false;
1477 for (const auto var: vars) {
1478 if (requisite_nodes.exists(bn.nodeId(*var))) {
1479 found = true;
1480 break;
1481 }
1482 }
1483
1484 if (!found) { pot_list.erase(iter); }
1485 }
1486 }
1487
1488 // find the tensors d-connected to a set of variables
1489 template < GUM_Numeric GUM_SCALAR >
1490 void ShaferShenoyInference< GUM_SCALAR >::_findRelevantTensorsWithdSeparation2_(
1491 Set< const IScheduleMultiDim* >& pot_list,
1492 gum::VariableSet& kept_vars) {
1493 // find the node ids of the kept variables
1494 NodeSet kept_ids(kept_vars.size());
1495 const auto& bn = this->BN();
1496 for (const auto var: kept_vars) {
1497 kept_ids.insert(bn.nodeId(*var));
1498 }
1499
1500 // determine the set of tensors d-connected with the kept variables
1501 BayesBall::relevantTensors(bn,
1502 kept_ids,
1503 this->hardEvidenceNodes(),
1504 this->softEvidenceNodes(),
1505 pot_list);
1506 }
1507
1508 // find the tensors d-connected to a set of variables
1509 template < GUM_Numeric GUM_SCALAR >
1510 void ShaferShenoyInference< GUM_SCALAR >::_findRelevantTensorsWithdSeparation3_(
1511 Set< const IScheduleMultiDim* >& pot_list,
1512 gum::VariableSet& kept_vars) {
1513 // find the node ids of the kept variables
1514 NodeSet kept_ids(kept_vars.size());
1515 const auto& bn = this->BN();
1516 for (const auto var: kept_vars) {
1517 kept_ids.insert(bn.nodeId(*var));
1518 }
1519
1520 // determine the set of tensors d-connected with the kept variables
1521 dSeparationAlgorithm dsep;
1522 dsep.relevantTensors(bn,
1523 kept_ids,
1524 this->hardEvidenceNodes(),
1525 this->softEvidenceNodes(),
1526 pot_list);
1527 }
1528
1529 // find the tensors d-connected to a set of variables
1530 template < GUM_Numeric GUM_SCALAR >
1531 void ShaferShenoyInference< GUM_SCALAR >::_findRelevantTensorsXX_(
1532 Set< const IScheduleMultiDim* >& pot_list,
1533 gum::VariableSet& kept_vars) {
1534 switch (_find_relevant_tensor_type_) {
1535 case RelevantTensorsFinderType::DSEP_BAYESBALL_TENSORS :
1536 _findRelevantTensorsWithdSeparation2_(pot_list, kept_vars);
1537 break;
1538
1539 case RelevantTensorsFinderType::DSEP_BAYESBALL_NODES :
1540 _findRelevantTensorsWithdSeparation_(pot_list, kept_vars);
1541 break;
1542
1543 case RelevantTensorsFinderType::DSEP_KOLLER_FRIEDMAN_2009 :
1544 _findRelevantTensorsWithdSeparation3_(pot_list, kept_vars);
1545 break;
1546
1547 case RelevantTensorsFinderType::FIND_ALL :
1548 _findRelevantTensorsGetAll_(pot_list, kept_vars);
1549 break;
1550
1551 default : GUM_ERROR(FatalError, "not implemented yet")
1552 }
1553 }
1554
1555 // remove barren variables using schedules
1556 template < GUM_Numeric GUM_SCALAR >
1557 Set< const IScheduleMultiDim* >
1558 ShaferShenoyInference< GUM_SCALAR >::_removeBarrenVariables_(Schedule& schedule,
1559 _ScheduleMultiDimSet_& pot_list,
1560 gum::VariableSet& del_vars) {
1561 // remove from del_vars the variables that received some evidence:
1562 // only those that did not receive evidence can be barren variables
1563 gum::VariableSet the_del_vars = del_vars;
1564 for (auto iter = the_del_vars.beginSafe(); iter != the_del_vars.endSafe(); ++iter) {
1565 NodeId id = this->BN().nodeId(**iter);
1566 if (this->hardEvidenceNodes().exists(id) || this->softEvidenceNodes().exists(id)) {
1567 the_del_vars.erase(iter);
1568 }
1569 }
1570
1571 // assign to each random variable the set of tensors that contain it
1572 HashTable< const DiscreteVariable*, _ScheduleMultiDimSet_ > var2pots(the_del_vars.size());
1573 _ScheduleMultiDimSet_ empty_pot_set;
1574 for (const auto pot: pot_list) {
1575 const auto& vars = pot->variablesSequence();
1576 for (const auto var: vars) {
1577 if (the_del_vars.exists(var)) {
1578 if (!var2pots.exists(var)) { var2pots.insert(var, empty_pot_set); }
1579 var2pots[var].insert(pot);
1580 }
1581 }
1582 }
1583
1584 // each variable with only one tensor is necessarily a barren variable
1585 // assign to each tensor with barren nodes its set of barren variables
1586 HashTable< const IScheduleMultiDim*, gum::VariableSet > pot2barren_var;
1587 gum::VariableSet empty_var_set;
1588 for (const auto& elt: var2pots) {
1589 if (elt.second.size() == 1) { // here we have a barren variable
1590 const IScheduleMultiDim* pot = *(elt.second.begin());
1591 if (!pot2barren_var.exists(pot)) { pot2barren_var.insert(pot, empty_var_set); }
1592 pot2barren_var[pot].insert(elt.first); // insert the barren variable
1593 }
1594 }
1595
1596 // for each tensor with barren variables, marginalize them.
1597 // if the tensor has only barren variables, simply remove them from the
1598 // set of tensors, else just project the tensor
1599 MultiDimProjection< Tensor< GUM_SCALAR > > projector(_projection_op_);
1600 _ScheduleMultiDimSet_ projected_pots;
1601 for (const auto& elt: pot2barren_var) {
1602 // remove the current tensor from pot_list as, anyway, we will change it
1603 const IScheduleMultiDim* pot = elt.first;
1604 pot_list.erase(pot);
1605
1606 // check whether we need to add a projected new tensor or not (i.e.,
1607 // whether there exist non-barren variables or not)
1608 if (pot->variablesSequence().size() != elt.second.size()) {
1609 const IScheduleMultiDim* new_pot = projector.schedule(schedule, pot, elt.second);
1610 // here, there is no need to enforce that new_pot is persistent since,
1611 // if this is needed, the function that called _removeBarrenVariables_ will
1612 // do it
1613 pot_list.insert(new_pot);
1614 projected_pots.insert(new_pot);
1615 }
1616 }
1617
1618 return projected_pots;
1619 }
1620
1621 // remove barren variables directly without schedules
1622 template < GUM_Numeric GUM_SCALAR >
1623 Set< const Tensor< GUM_SCALAR >* >
1624 ShaferShenoyInference< GUM_SCALAR >::_removeBarrenVariables_(_TensorSet_& pot_list,
1625 gum::VariableSet& del_vars) {
1626 // remove from del_vars the variables that received some evidence:
1627 // only those that did not receive evidence can be barren variables
1628 gum::VariableSet the_del_vars = del_vars;
1629 for (auto iter = the_del_vars.beginSafe(); iter != the_del_vars.endSafe(); ++iter) {
1630 NodeId id = this->BN().nodeId(**iter);
1631 if (this->hardEvidenceNodes().exists(id) || this->softEvidenceNodes().exists(id)) {
1632 the_del_vars.erase(iter);
1633 }
1634 }
1635
1636 // assign to each random variable the set of tensors that contain it
1637 HashTable< const DiscreteVariable*, _TensorSet_ > var2pots(the_del_vars.size());
1638 _TensorSet_ empty_pot_set;
1639 for (const auto pot: pot_list) {
1640 const Sequence< const DiscreteVariable* >& vars = pot->variablesSequence();
1641 for (const auto var: vars) {
1642 if (the_del_vars.exists(var)) {
1643 if (!var2pots.exists(var)) { var2pots.insert(var, empty_pot_set); }
1644 var2pots[var].insert(pot);
1645 }
1646 }
1647 }
1648
1649 // each variable with only one tensor is a barren variable
1650 // assign to each tensor with barren nodes its set of barren variables
1651 HashTable< const Tensor< GUM_SCALAR >*, gum::VariableSet > pot2barren_var;
1652 gum::VariableSet empty_var_set;
1653 for (const auto& elt: var2pots) {
1654 if (elt.second.size() == 1) { // here we have a barren variable
1655 const Tensor< GUM_SCALAR >* pot = *(elt.second.begin());
1656 if (!pot2barren_var.exists(pot)) { pot2barren_var.insert(pot, empty_var_set); }
1657 pot2barren_var[pot].insert(elt.first); // insert the barren variable
1658 }
1659 }
1660
1661 // for each tensor with barren variables, marginalize them.
1662 // if the tensor has only barren variables, simply remove them from the
1663 // set of tensors, else just project the tensor
1664 MultiDimProjection< Tensor< GUM_SCALAR > > projector(_projection_op_);
1665 _TensorSet_ projected_pots;
1666 for (const auto& elt: pot2barren_var) {
1667 // remove the current tensor from pot_list as, anyway, we will change it
1668 const Tensor< GUM_SCALAR >* pot = elt.first;
1669 pot_list.erase(pot);
1670
1671 // check whether we need to add a projected new tensor or not (i.e.,
1672 // whether there exist non-barren variables or not)
1673 if (pot->variablesSequence().size() != elt.second.size()) {
1674 const Tensor< GUM_SCALAR >* new_pot = projector.execute(*pot, elt.second);
1675 pot_list.insert(new_pot);
1676 projected_pots.insert(new_pot);
1677 }
1678 }
1679
1680 return projected_pots;
1681 }
1682
1683 // performs the collect phase of Shafer-Shenoy using schedules
1684 template < GUM_Numeric GUM_SCALAR >
1685 void ShaferShenoyInference< GUM_SCALAR >::_collectMessage_(Schedule& schedule,
1686 NodeId id,
1687 NodeId from) {
1688 for (const auto other: _JT_->neighbours(id)) {
1689 if ((other != from) && !_messages_computed_[Arc(other, id)])
1690 _collectMessage_(schedule, other, id);
1691 }
1692
1693 if ((id != from) && !_messages_computed_[Arc(id, from)]) {
1694 _produceMessage_(schedule, id, from);
1695 }
1696 }
1697
1698 // performs the collect phase of Shafer-Shenoy without schedules
1699 template < GUM_Numeric GUM_SCALAR >
1700 void ShaferShenoyInference< GUM_SCALAR >::_collectMessage_(NodeId id, NodeId from) {
1701 for (const auto other: _JT_->neighbours(id)) {
1702 if ((other != from) && !_messages_computed_[Arc(other, id)]) _collectMessage_(other, id);
1703 }
1704
1705 if ((id != from) && !_messages_computed_[Arc(id, from)]) { _produceMessage_(id, from); }
1706 }
1707
1708 // remove variables del_vars from the list of tensors pot_list
1709 template < GUM_Numeric GUM_SCALAR >
1710 const IScheduleMultiDim* ShaferShenoyInference< GUM_SCALAR >::_marginalizeOut_(
1711 Schedule& schedule,
1712 Set< const IScheduleMultiDim* > pot_list,
1713 gum::VariableSet& del_vars,
1714 gum::VariableSet& kept_vars) {
1715 // use d-separation analysis to check which tensors shall be combined
1716 //_findRelevantTensorsXX_(pot_list, kept_vars);
1717
1718 // if pot list is empty, do nothing. This may happen when there are only barren variables
1719 if (pot_list.empty()) {
1720 return new ScheduleMultiDim< Tensor< GUM_SCALAR > >(Tensor< GUM_SCALAR >());
1721 }
1722
1723 // now, let's guarantee that all the tensors to be combined and projected
1724 // belong to the schedule
1725 for (const auto pot: pot_list) {
1726 if (!schedule.existsScheduleMultiDim(pot->id())) schedule.emplaceScheduleMultiDim(*pot);
1727 }
1728
1729 // remove the tensors corresponding to barren variables if we want
1730 // to exploit barren nodes
1731 _ScheduleMultiDimSet_ barren_projected_tensors;
1732 if (_barren_nodes_type_ == FindBarrenNodesType::FIND_BARREN_NODES) {
1733 barren_projected_tensors = _removeBarrenVariables_(schedule, pot_list, del_vars);
1734 }
1735
1736 // Combine and project the tensors
1737 _ScheduleMultiDimSet_ new_pot_list;
1738 if (pot_list.size() == 1) { // only one tensor, so just project it
1739 MultiDimProjection< Tensor< GUM_SCALAR > > projector(_projection_op_);
1740 auto xpot = projector.schedule(schedule, *(pot_list.begin()), del_vars);
1741 new_pot_list.insert(xpot);
1742 } else if (pot_list.size() > 1) {
1743 // create a combine and project operator that will perform the
1744 // marginalization
1745 MultiDimCombineAndProjectDefault< Tensor< GUM_SCALAR > > combine_and_project(_combination_op_,
1746 _projection_op_);
1747 new_pot_list = combine_and_project.schedule(schedule, pot_list, del_vars);
1748 }
1749
1750 // remove all the tensors that were created due to projections of
1751 // barren nodes and that are not part of the new_pot_list: these
1752 // tensors were just temporary tensors
1753 for (auto barren_pot: barren_projected_tensors) {
1754 if (!new_pot_list.exists(barren_pot))
1755 schedule.emplaceDeletion(
1756 static_cast< const ScheduleMultiDim< Tensor< GUM_SCALAR > >& >(*barren_pot));
1757 }
1758
1759 // combine all the remaining tensors in order to create only one resulting tensor
1760 if (new_pot_list.empty())
1761 return new ScheduleMultiDim< Tensor< GUM_SCALAR > >(Tensor< GUM_SCALAR >());
1762 if (new_pot_list.size() == 1) return *(new_pot_list.begin());
1763 MultiDimCombinationDefault< Tensor< GUM_SCALAR > > fast_combination(_combination_op_);
1764 return fast_combination.schedule(schedule, new_pot_list);
1765 }
1766
1767 // remove variables del_vars from the list of tensors pot_list
1768 template < GUM_Numeric GUM_SCALAR >
1769 const IScheduleMultiDim* ShaferShenoyInference< GUM_SCALAR >::_marginalizeOut_(
1770 Set< const IScheduleMultiDim* >& pot_list,
1771 gum::VariableSet& del_vars,
1772 gum::VariableSet& kept_vars) {
1773 // if pot list is empty, do nothing. This may happen when there are only barren variables
1774 if (pot_list.empty()) {
1775 return new ScheduleMultiDim< Tensor< GUM_SCALAR > >(Tensor< GUM_SCALAR >());
1776 }
1777
1778 _TensorSet_ xpot_list(pot_list.size());
1779 for (auto pot: pot_list)
1780 xpot_list.insert(
1781 &(static_cast< const ScheduleMultiDim< Tensor< GUM_SCALAR > >* >(pot)->multiDim()));
1782
1783 // use d-separation analysis to check which tensors shall be combined
1784 // _findRelevantTensorsXX_(pot_list, kept_vars);
1785
1786 // remove the tensors corresponding to barren variables if we want
1787 // to exploit barren nodes
1788 _TensorSet_ barren_projected_tensors;
1789 if (_barren_nodes_type_ == FindBarrenNodesType::FIND_BARREN_NODES) {
1790 barren_projected_tensors = _removeBarrenVariables_(xpot_list, del_vars);
1791 }
1792
1793 // Combine and project the remaining tensors
1794 _TensorSet_ xnew_pot_list;
1795 if (xpot_list.size() == 1) {
1796 MultiDimProjection< Tensor< GUM_SCALAR > > projector(_projection_op_);
1797 auto xpot = projector.execute(**(xpot_list.begin()), del_vars);
1798 xnew_pot_list.insert(xpot);
1799 } else if (xpot_list.size() > 1) {
1800 // create a combine and project operator that will perform the
1801 // marginalization
1802 MultiDimCombineAndProjectDefault< Tensor< GUM_SCALAR > > combine_and_project(_combination_op_,
1803 _projection_op_);
1804 xnew_pot_list = combine_and_project.execute(xpot_list, del_vars);
1805 }
1806
1807 // combine all the remaining tensors in order to create only one resulting tensor
1808 const Tensor< GUM_SCALAR >* xres_pot;
1809 ScheduleMultiDim< Tensor< GUM_SCALAR > >* res_pot;
1810 if (xnew_pot_list.size() == 1) {
1811 xres_pot = *(xnew_pot_list.begin());
1812 } else if (xnew_pot_list.size() > 1) {
1813 // combine all the tensors that resulted from the above combine and
1814 // projet execution
1815 MultiDimCombinationDefault< Tensor< GUM_SCALAR > > fast_combination(_combination_op_);
1816 xres_pot = fast_combination.execute(xnew_pot_list);
1817 for (const auto pot: xnew_pot_list) {
1818 if (!xpot_list.contains(pot) && (pot != xres_pot)) delete pot;
1819 }
1820 } else {
1821 xres_pot = new Tensor< GUM_SCALAR >();
1822 }
1823
1824 // transform xres_pot into a ScheduleMultiDim
1825 if (xpot_list.contains(xres_pot))
1826 res_pot = new ScheduleMultiDim< Tensor< GUM_SCALAR > >(*xres_pot, false);
1827 else {
1828 res_pot = new ScheduleMultiDim< Tensor< GUM_SCALAR > >(
1829 std::move(const_cast< Tensor< GUM_SCALAR >& >(*xres_pot)));
1830 delete xres_pot;
1831 }
1832
1833 // remove all the tensors that were created due to projections of
1834 // barren nodes and that are not part of the new_pot_list: these
1835 // tensors were just temporary tensors
1836 for (const auto barren_pot: barren_projected_tensors) {
1837 if (!xnew_pot_list.exists(barren_pot)) delete barren_pot;
1838 }
1839
1840 return res_pot;
1841 }
1842
1843 // creates the message sent by clique from_id to clique to_id
1844 template < GUM_Numeric GUM_SCALAR >
1845 void ShaferShenoyInference< GUM_SCALAR >::_produceMessage_(Schedule& schedule,
1846 NodeId from_id,
1847 NodeId to_id) {
1848 // get the tensors of the clique.
1849 _ScheduleMultiDimSet_ pot_list;
1850 if (_clique_ss_tensor_[from_id] != nullptr) pot_list.insert(_clique_ss_tensor_[from_id]);
1851
1852 // add the messages sent by adjacent nodes to from_id.
1853 for (const auto other_id: _JT_->neighbours(from_id)) {
1854 if (other_id != to_id) {
1855 const auto separator_pot = _separator_tensors_[Arc(other_id, from_id)];
1856 if (separator_pot != nullptr) pot_list.insert(separator_pot);
1857 }
1858 }
1859
1860 // get the set of variables that need be removed from the tensors
1861 const NodeSet& from_clique = _JT_->clique(from_id);
1862 const NodeSet& separator = _JT_->separator(from_id, to_id);
1863 gum::VariableSet del_vars(from_clique.size());
1864 gum::VariableSet kept_vars(separator.size());
1865 const auto& bn = this->BN();
1866
1867 for (const auto node: from_clique) {
1868 if (!separator.contains(node)) {
1869 del_vars.insert(&(bn.variable(node)));
1870 } else {
1871 kept_vars.insert(&(bn.variable(node)));
1872 }
1873 }
1874
1875 // pot_list now contains all the tensors to multiply and marginalize
1876 // => combine the messages
1877 const IScheduleMultiDim* new_pot = _marginalizeOut_(schedule, pot_list, del_vars, kept_vars);
1878
1879 // keep track of the newly created tensor
1880 const Arc arc(from_id, to_id);
1881 if (!pot_list.exists(new_pot)) {
1882 if (!_arc_to_created_tensors_.exists(arc)) {
1883 _arc_to_created_tensors_.insert(arc, new_pot);
1884
1885 // do not forget to make the ScheduleMultiDim persistent
1886 auto op = schedule.scheduleMultiDimCreator(new_pot);
1887 if (op != nullptr) const_cast< ScheduleOperator* >(op)->makeResultsPersistent(true);
1888 }
1889 }
1890
1891 _separator_tensors_[arc] = new_pot;
1892 _messages_computed_[arc] = true;
1893 }
1894
1895 // creates the message sent by clique from_id to clique to_id
1896 template < GUM_Numeric GUM_SCALAR >
1897 void ShaferShenoyInference< GUM_SCALAR >::_produceMessage_(NodeId from_id, NodeId to_id) {
1898 // get the tensors of the clique.
1899 _ScheduleMultiDimSet_ pot_list;
1900 if (_clique_ss_tensor_[from_id] != nullptr) pot_list.insert(_clique_ss_tensor_[from_id]);
1901
1902 // add the messages sent by adjacent nodes to from_id.
1903 for (const auto other_id: _JT_->neighbours(from_id)) {
1904 if (other_id != to_id) {
1905 const auto separator_pot = _separator_tensors_[Arc(other_id, from_id)];
1906 if (separator_pot != nullptr) pot_list.insert(separator_pot);
1907 }
1908 }
1909
1910 // get the set of variables that need be removed from the tensors
1911 const NodeSet& from_clique = _JT_->clique(from_id);
1912 const NodeSet& separator = _JT_->separator(from_id, to_id);
1913 gum::VariableSet del_vars(from_clique.size());
1914 gum::VariableSet kept_vars(separator.size());
1915 const auto& bn = this->BN();
1916
1917 for (const auto node: from_clique) {
1918 if (!separator.contains(node)) {
1919 del_vars.insert(&(bn.variable(node)));
1920 } else {
1921 kept_vars.insert(&(bn.variable(node)));
1922 }
1923 }
1924
1925 // pot_list now contains all the tensors to multiply and marginalize
1926 // => combine the messages
1927 const IScheduleMultiDim* new_pot = _marginalizeOut_(pot_list, del_vars, kept_vars);
1928
1929 // keep track of the newly created tensor
1930 const Arc arc(from_id, to_id);
1931 if (!pot_list.exists(new_pot)) {
1932 if (!_arc_to_created_tensors_.exists(arc)) { _arc_to_created_tensors_.insert(arc, new_pot); }
1933 }
1934
1935 _separator_tensors_[arc] = new_pot;
1936 _messages_computed_[arc] = true;
1937 }
1938
1939 // performs a whole inference
1940 template < GUM_Numeric GUM_SCALAR >
1941 void ShaferShenoyInference< GUM_SCALAR >::makeInference_() {
1942 if (_use_schedules_) {
1943 Schedule schedule;
1944
1945 // collect messages for all single targets
1946 for (const auto node: this->targets()) {
1947 // perform only collects in the join tree for nodes that have
1948 // not received hard evidence (those that received hard evidence were
1949 // not included into the join tree for speed-up reasons)
1950 if (_graph_.exists(node)) {
1951 _collectMessage_(schedule, _node_to_clique_[node], _node_to_clique_[node]);
1952 }
1953 }
1954
1955 // collect messages for all set targets
1956 // by parsing _joint_target_to_clique_, we ensure that the cliques that
1957 // are referenced belong to the join tree (even if some of the nodes in
1958 // their associated joint_target do not belong to _graph_)
1959 for (const auto& set: _joint_target_to_clique_)
1960 _collectMessage_(schedule, set.second, set.second);
1961
1962 // really perform the computations
1963 this->scheduler().execute(schedule);
1964 } else {
1965 // collect messages for all single targets
1966 for (const auto node: this->targets()) {
1967 // perform only collects in the join tree for nodes that have
1968 // not received hard evidence (those that received hard evidence were
1969 // not included into the join tree for speed-up reasons)
1970 if (_graph_.exists(node)) {
1971 _collectMessage_(_node_to_clique_[node], _node_to_clique_[node]);
1972 }
1973 }
1974
1975 // collect messages for all set targets
1976 // by parsing _joint_target_to_clique_, we ensure that the cliques that
1977 // are referenced belong to the join tree (even if some of the nodes in
1978 // their associated joint_target do not belong to _graph_)
1979 for (const auto& set: _joint_target_to_clique_)
1980 _collectMessage_(set.second, set.second);
1981 }
1982 }
1983
1985 template < GUM_Numeric GUM_SCALAR >
1986 Tensor< GUM_SCALAR >*
1987 ShaferShenoyInference< GUM_SCALAR >::unnormalizedJointPosterior_(NodeId id) {
1988 if (_use_schedules_) {
1989 Schedule schedule;
1990 return _unnormalizedJointPosterior_(schedule, id);
1991 } else {
1992 return _unnormalizedJointPosterior_(id);
1993 }
1994 }
1995
1997 template < GUM_Numeric GUM_SCALAR >
1998 Tensor< GUM_SCALAR >*
1999 ShaferShenoyInference< GUM_SCALAR >::_unnormalizedJointPosterior_(Schedule& schedule,
2000 NodeId id) {
2001 const auto& bn = this->BN();
2002
2003 // hard evidence do not belong to the join tree
2004 // # TODO: check for sets of inconsistent hard evidence
2005 if (this->hardEvidenceNodes().contains(id)) {
2006 return new Tensor< GUM_SCALAR >(*(this->evidence()[id]));
2007 }
2008
2009 auto& scheduler = this->scheduler();
2010
2011 // if we still need to perform some inference task, do it (this should
2012 // already have been done by makeInference_)
2013 const NodeId clique_of_id = _node_to_clique_[id];
2014 _collectMessage_(schedule, clique_of_id, clique_of_id);
2015
2016 // now we just need to create the product of the tensors of the clique
2017 // containing id with the messages received by this clique and
2018 // marginalize out all variables except id
2019 _ScheduleMultiDimSet_ pot_list;
2020 if (_clique_ss_tensor_[clique_of_id] != nullptr)
2021 pot_list.insert(_clique_ss_tensor_[clique_of_id]);
2022
2023 // add the messages sent by adjacent nodes to targetClique
2024 for (const auto other: _JT_->neighbours(clique_of_id))
2025 pot_list.insert(_separator_tensors_[Arc(other, clique_of_id)]);
2026
2027 // get the set of variables that need be removed from the tensors
2028 const NodeSet& nodes = _JT_->clique(clique_of_id);
2029 gum::VariableSet kept_vars{&(bn.variable(id))};
2030 gum::VariableSet del_vars(nodes.size());
2031 for (const auto node: nodes) {
2032 if (node != id) del_vars.insert(&(bn.variable(node)));
2033 }
2034
2035 // pot_list now contains all the tensors to multiply and marginalize
2036 // => combine the messages
2037 auto resulting_pot = const_cast< ScheduleMultiDim< Tensor< GUM_SCALAR > >* >(
2038 static_cast< const ScheduleMultiDim< Tensor< GUM_SCALAR > >* >(
2039 _marginalizeOut_(schedule, pot_list, del_vars, kept_vars)));
2040 Tensor< GUM_SCALAR >* joint = nullptr;
2041
2042 scheduler.execute(schedule);
2043
2044 // if pot already existed, create a copy, so that we can put it into
2045 // the _target_posteriors_ property
2046 if (pot_list.exists(resulting_pot)) {
2047 joint = new Tensor< GUM_SCALAR >(resulting_pot->multiDim());
2048 } else {
2049 joint = resulting_pot->exportMultiDim();
2050 }
2051
2052 // check that the joint posterior is different from a 0 vector: this would
2053 // indicate that some hard evidence are not compatible (their joint
2054 // probability is equal to 0)
2055 bool nonzero_found = false;
2056 for (Instantiation inst(*joint); !inst.end(); ++inst) {
2057 if (joint->get(inst)) {
2058 nonzero_found = true;
2059 break;
2060 }
2061 }
2062 if (!nonzero_found) {
2063 // remove joint from memory to avoid memory leaks
2064 delete joint;
2066 "some evidence entered into the Bayes "
2067 "net are incompatible (their joint proba = 0)");
2068 }
2069 return joint;
2070 }
2071
2073 template < GUM_Numeric GUM_SCALAR >
2074 Tensor< GUM_SCALAR >*
2075 ShaferShenoyInference< GUM_SCALAR >::_unnormalizedJointPosterior_(NodeId id) {
2076 const auto& bn = this->BN();
2077
2078 // hard evidence do not belong to the join tree
2079 // # TODO: check for sets of inconsistent hard evidence
2080 if (this->hardEvidenceNodes().contains(id)) {
2081 return new Tensor< GUM_SCALAR >(*(this->evidence()[id]));
2082 }
2083
2084 // if we still need to perform some inference task, do it (this should
2085 // already have been done by makeInference_)
2086 NodeId clique_of_id = _node_to_clique_[id];
2087 _collectMessage_(clique_of_id, clique_of_id);
2088
2089 // now we just need to create the product of the tensors of the clique
2090 // containing id with the messages received by this clique and
2091 // marginalize out all variables except id
2092 _ScheduleMultiDimSet_ pot_list;
2093 if (_clique_ss_tensor_[clique_of_id] != nullptr)
2094 pot_list.insert(_clique_ss_tensor_[clique_of_id]);
2095
2096 // add the messages sent by adjacent nodes to targetClique
2097 for (const auto other: _JT_->neighbours(clique_of_id))
2098 pot_list.insert(_separator_tensors_[Arc(other, clique_of_id)]);
2099
2100 // get the set of variables that need be removed from the tensors
2101 const NodeSet& nodes = _JT_->clique(clique_of_id);
2102 gum::VariableSet kept_vars{&(bn.variable(id))};
2103 gum::VariableSet del_vars(nodes.size());
2104 for (const auto node: nodes) {
2105 if (node != id) del_vars.insert(&(bn.variable(node)));
2106 }
2107
2108 // pot_list now contains all the tensors to multiply and marginalize
2109 // => combine the messages
2110 auto resulting_pot = const_cast< ScheduleMultiDim< Tensor< GUM_SCALAR > >* >(
2111 static_cast< const ScheduleMultiDim< Tensor< GUM_SCALAR > >* >(
2112 _marginalizeOut_(pot_list, del_vars, kept_vars)));
2113 Tensor< GUM_SCALAR >* joint = nullptr;
2114
2115 // if pot already existed, create a copy, so that we can put it into
2116 // the _target_posteriors_ property
2117 if (pot_list.exists(resulting_pot)) {
2118 joint = new Tensor< GUM_SCALAR >(resulting_pot->multiDim());
2119 } else {
2120 joint = resulting_pot->exportMultiDim();
2121 delete resulting_pot;
2122 }
2123
2124 // check that the joint posterior is different from a 0 vector: this would
2125 // indicate that some hard evidence are not compatible (their joint
2126 // probability is equal to 0)
2127 bool nonzero_found = false;
2128 for (Instantiation inst(*joint); !inst.end(); ++inst) {
2129 if (joint->get(inst)) {
2130 nonzero_found = true;
2131 break;
2132 }
2133 }
2134 if (!nonzero_found) {
2135 // remove joint from memory to avoid memory leaks
2136 delete joint;
2138 "some evidence entered into the Bayes "
2139 "net are incompatible (their joint proba = 0)");
2140 }
2141 return joint;
2142 }
2143
2145 template < GUM_Numeric GUM_SCALAR >
2146 const Tensor< GUM_SCALAR >& ShaferShenoyInference< GUM_SCALAR >::posterior_(NodeId id) {
2147 // check if we have already computed the posterior
2148 if (_target_posteriors_.exists(id)) { return *(_target_posteriors_[id]); }
2149
2150 // compute the joint posterior and normalize
2151 auto joint = unnormalizedJointPosterior_(id);
2152 if (joint->sum() != 1) // hard test for ReadOnly CPT (as aggregator)
2153 joint->normalize();
2154 _target_posteriors_.insert(id, joint);
2155
2156 return *joint;
2157 }
2158
2160 template < GUM_Numeric GUM_SCALAR >
2161 Tensor< GUM_SCALAR >*
2162 ShaferShenoyInference< GUM_SCALAR >::unnormalizedJointPosterior_(const NodeSet& set) {
2163 if (_use_schedules_) {
2164 Schedule schedule;
2165 return _unnormalizedJointPosterior_(schedule, set);
2166 } else {
2167 return _unnormalizedJointPosterior_(set);
2168 }
2169 }
2170
2172 template < GUM_Numeric GUM_SCALAR >
2173 Tensor< GUM_SCALAR >*
2174 ShaferShenoyInference< GUM_SCALAR >::_unnormalizedJointPosterior_(Schedule& schedule,
2175 const NodeSet& set) {
2176 // hard evidence do not belong to the join tree, so extract the nodes
2177 // from targets that are not hard evidence
2178 NodeSet targets = set, hard_ev_nodes;
2179 for (const auto node: this->hardEvidenceNodes()) {
2180 if (targets.contains(node)) {
2181 targets.erase(node);
2182 hard_ev_nodes.insert(node);
2183 }
2184 }
2185
2186 auto& scheduler = this->scheduler();
2187
2188 // if all the nodes have received hard evidence, then compute the
2189 // joint posterior directly by multiplying the hard evidence tensors
2190 const auto& evidence = this->evidence();
2191 if (targets.empty()) {
2192 if (set.size() == 1) {
2193 return new Tensor< GUM_SCALAR >(*evidence[*set.begin()]);
2194 } else {
2195 _ScheduleMultiDimSet_ pot_list;
2196 for (const auto node: set) {
2197 auto new_pot_ev = schedule.insertTable< Tensor< GUM_SCALAR > >(*evidence[node], false);
2198 pot_list.insert(new_pot_ev);
2199 }
2200
2201 // combine all the tensors of the nodes in set
2202 MultiDimCombinationDefault< Tensor< GUM_SCALAR > > fast_combination(_combination_op_);
2203 const IScheduleMultiDim* pot = fast_combination.schedule(schedule, pot_list);
2204 auto schedule_pot = const_cast< ScheduleMultiDim< Tensor< GUM_SCALAR > >* >(
2205 static_cast< const ScheduleMultiDim< Tensor< GUM_SCALAR > >* >(pot));
2206 scheduler.execute(schedule);
2207 auto result = schedule_pot->exportMultiDim();
2208
2209 return result;
2210 }
2211 }
2212
2213
2214 // if we still need to perform some inference task, do it: so, first,
2215 // determine the clique on which we should perform collect to compute
2216 // the unnormalized joint posterior of a set of nodes containing "targets"
2217 NodeId clique_of_set;
2218 if (auto ptr_clique = _joint_target_to_clique_.tryGet(set)) {
2219 clique_of_set = *ptr_clique;
2220 } else {
2221 // here, the precise set of targets does not belong to the set of targets
2222 // defined by the user. So we will try to find a clique in the junction
2223 // tree that contains "targets":
2224
2225 // 1/ we should check that all the nodes belong to the join tree
2226 for (const auto node: targets) {
2227 if (!_graph_.exists(node)) {
2229 "The variable " << this->BN().variable(node).name() << "(" << node
2230 << ") does not belong to this optimized inference.")
2231 }
2232 }
2233
2234 // 2/ the clique created by the first eliminated node among target is the
2235 // one we are looking for
2236 const std::vector< NodeId >& JT_elim_order = _triangulation_->eliminationOrder();
2237
2238 NodeProperty< int > elim_order(Size(JT_elim_order.size()));
2239 for (std::size_t i = std::size_t(0), size = JT_elim_order.size(); i < size; ++i)
2240 elim_order.insert(JT_elim_order[i], (int)i);
2241 NodeId first_eliminated_node = *(targets.begin());
2242 int elim_number = elim_order[first_eliminated_node];
2243 for (const auto node: targets) {
2244 if (elim_order[node] < elim_number) {
2245 elim_number = elim_order[node];
2246 first_eliminated_node = node;
2247 }
2248 }
2249
2250 clique_of_set = _triangulation_->createdJunctionTreeClique(first_eliminated_node);
2251
2252
2253 // 3/ check that clique_of_set contains the all the nodes in the target
2254 const NodeSet& clique_nodes = _JT_->clique(clique_of_set);
2255 for (const auto node: targets) {
2256 if (!clique_nodes.contains(node)) {
2258 this->BN().names(set) << "(" << set << ")"
2259 << " is not addressable in this optimized inference.")
2260 }
2261 }
2262
2263 // add the discovered clique to _joint_target_to_clique_
2264 _joint_target_to_clique_.insert(set, clique_of_set);
2265 }
2266
2267 // now perform a collect on the clique
2268 _collectMessage_(schedule, clique_of_set, clique_of_set);
2269
2270 // now we just need to create the product of the tensors of the clique
2271 // containing set with the messages received by this clique and
2272 // marginalize out all variables except set
2273 _ScheduleMultiDimSet_ pot_list;
2274 if (_clique_ss_tensor_[clique_of_set] != nullptr) {
2275 auto pot = _clique_ss_tensor_[clique_of_set];
2276 if (!schedule.existsScheduleMultiDim(pot->id())) schedule.emplaceScheduleMultiDim(*pot);
2277 pot_list.insert(_clique_ss_tensor_[clique_of_set]);
2278 }
2279
2280 // add the messages sent by adjacent nodes to targetClique
2281 for (const auto other: _JT_->neighbours(clique_of_set)) {
2282 const auto pot = _separator_tensors_[Arc(other, clique_of_set)];
2283 if (pot != nullptr) pot_list.insert(pot);
2284 }
2285
2286
2287 // get the set of variables that need be removed from the tensors
2288 const NodeSet& nodes = _JT_->clique(clique_of_set);
2289 gum::VariableSet del_vars(nodes.size());
2290 gum::VariableSet kept_vars(targets.size());
2291 const auto& bn = this->BN();
2292 for (const auto node: nodes) {
2293 if (!targets.contains(node)) {
2294 del_vars.insert(&(bn.variable(node)));
2295 } else {
2296 kept_vars.insert(&(bn.variable(node)));
2297 }
2298 }
2299
2300 // pot_list now contains all the tensors to multiply and marginalize
2301 // => combine the messages
2302 const IScheduleMultiDim* new_pot = _marginalizeOut_(schedule, pot_list, del_vars, kept_vars);
2303 scheduler.execute(schedule);
2304 ScheduleMultiDim< Tensor< GUM_SCALAR > >* resulting_pot
2305 = const_cast< ScheduleMultiDim< Tensor< GUM_SCALAR > >* >(
2306 static_cast< const ScheduleMultiDim< Tensor< GUM_SCALAR > >* >(new_pot));
2307
2308 // if pot already existed, create a copy, so that we can put it into
2309 // the _target_posteriors_ property
2310 Tensor< GUM_SCALAR >* joint = nullptr;
2311 if (pot_list.exists(resulting_pot)) {
2312 joint = new Tensor< GUM_SCALAR >(resulting_pot->multiDim());
2313 } else {
2314 joint = resulting_pot->exportMultiDim();
2315 }
2316
2317 // check that the joint posterior is different from a 0 vector: this would
2318 // indicate that some hard evidence are not compatible
2319 bool nonzero_found = false;
2320 for (Instantiation inst(*joint); !inst.end(); ++inst) {
2321 if ((*joint)[inst]) {
2322 nonzero_found = true;
2323 break;
2324 }
2325 }
2326 if (!nonzero_found) {
2327 // remove joint from memory to avoid memory leaks
2328 delete joint;
2330 "some evidence entered into the Bayes "
2331 "net are incompatible (their joint proba = 0)");
2332 }
2333
2334 // if there exists some nodes in the set of targets that received hard evidence,
2335 // then the joint Tensor needs be multiplied by the evidence tensors of
2336 // these nodes
2337 if (!hard_ev_nodes.empty()) {
2338 _TensorSet_ pot_list;
2339 pot_list.insert(joint);
2340 const auto& hard_evidence = this->evidence();
2341 for (const auto node: hard_ev_nodes)
2342 pot_list.insert(hard_evidence[node]);
2343 MultiDimCombinationDefault< Tensor< GUM_SCALAR > > combine(_combination_op_);
2344 Tensor< GUM_SCALAR >* new_joint = combine.execute(pot_list);
2345 delete joint;
2346 joint = new_joint;
2347 }
2348
2349 return joint;
2350 }
2351
2353 template < GUM_Numeric GUM_SCALAR >
2354 Tensor< GUM_SCALAR >*
2355 ShaferShenoyInference< GUM_SCALAR >::_unnormalizedJointPosterior_(const NodeSet& set) {
2356 // hard evidence do not belong to the join tree, so extract the nodes
2357 // from targets that are not hard evidence
2358 NodeSet targets = set, hard_ev_nodes;
2359 for (const auto node: this->hardEvidenceNodes()) {
2360 if (targets.contains(node)) {
2361 targets.erase(node);
2362 hard_ev_nodes.insert(node);
2363 }
2364 }
2365
2366 // if all the nodes have received hard evidence, then compute the
2367 // joint posterior directly by multiplying the hard evidence tensors
2368 const auto& evidence = this->evidence();
2369 if (targets.empty()) {
2370 if (set.size() == 1) {
2371 return new Tensor< GUM_SCALAR >(*evidence[*set.begin()]);
2372 } else {
2373 _TensorSet_ pot_list;
2374 for (const auto node: set) {
2375 pot_list.insert(evidence[node]);
2376 }
2377
2378 // combine all the tensors of the nodes in set
2379 MultiDimCombinationDefault< Tensor< GUM_SCALAR > > fast_combination(_combination_op_);
2380 const Tensor< GUM_SCALAR >* pot = fast_combination.execute(pot_list);
2381
2382 return const_cast< Tensor< GUM_SCALAR >* >(pot);
2383 }
2384 }
2385
2386
2387 // if we still need to perform some inference task, do it: so, first,
2388 // determine the clique on which we should perform collect to compute
2389 // the unnormalized joint posterior of a set of nodes containing "targets"
2390 NodeId clique_of_set;
2391 if (auto ptr_clique = _joint_target_to_clique_.tryGet(set)) {
2392 clique_of_set = *ptr_clique;
2393 } else {
2394 // here, the precise set of targets does not belong to the set of targets
2395 // defined by the user. So we will try to find a clique in the junction
2396 // tree that contains "targets":
2397
2398 // 1/ we should check that all the nodes belong to the join tree
2399 for (const auto node: targets) {
2400 if (!_graph_.exists(node)) {
2402 node << " cannot be a query in the optimized inference (w.r.t the declared "
2403 "targets/evidence)")
2404 }
2405 }
2406
2407 // 2/ the clique created by the first eliminated node among target is the
2408 // one we are looking for
2409 const std::vector< NodeId >& JT_elim_order = _triangulation_->eliminationOrder();
2410
2411 NodeProperty< int > elim_order(Size(JT_elim_order.size()));
2412 for (std::size_t i = std::size_t(0), size = JT_elim_order.size(); i < size; ++i)
2413 elim_order.insert(JT_elim_order[i], (int)i);
2414 NodeId first_eliminated_node = *(targets.begin());
2415 int elim_number = elim_order[first_eliminated_node];
2416 for (const auto node: targets) {
2417 if (elim_order[node] < elim_number) {
2418 elim_number = elim_order[node];
2419 first_eliminated_node = node;
2420 }
2421 }
2422
2423 clique_of_set = _triangulation_->createdJunctionTreeClique(first_eliminated_node);
2424
2425 // 3/ check that clique_of_set contains the all the nodes in the target
2426 const NodeSet& clique_nodes = _JT_->clique(clique_of_set);
2427 for (const auto node: targets) {
2428 if (!clique_nodes.contains(node)) {
2430 this->BN().names(set) << "(" << set << ")"
2431 << " is not addressable in this optimized inference.")
2432 }
2433 }
2434
2435 // add the discovered clique to _joint_target_to_clique_
2436 _joint_target_to_clique_.insert(set, clique_of_set);
2437 }
2438
2439 // now perform a collect on the clique
2440 _collectMessage_(clique_of_set, clique_of_set);
2441
2442 // now we just need to create the product of the tensors of the clique
2443 // containing set with the messages received by this clique and
2444 // marginalize out all variables except set
2445 _ScheduleMultiDimSet_ pot_list;
2446 if (_clique_ss_tensor_[clique_of_set] != nullptr) {
2447 auto pot = _clique_ss_tensor_[clique_of_set];
2448 if (pot != nullptr) pot_list.insert(_clique_ss_tensor_[clique_of_set]);
2449 }
2450
2451 // add the messages sent by adjacent nodes to targetClique
2452 for (const auto other: _JT_->neighbours(clique_of_set)) {
2453 const auto pot = _separator_tensors_[Arc(other, clique_of_set)];
2454 if (pot != nullptr) pot_list.insert(pot);
2455 }
2456
2457 // get the set of variables that need be removed from the tensors
2458 const NodeSet& nodes = _JT_->clique(clique_of_set);
2459 gum::VariableSet del_vars(nodes.size());
2460 gum::VariableSet kept_vars(targets.size());
2461 const auto& bn = this->BN();
2462 for (const auto node: nodes) {
2463 if (!targets.contains(node)) {
2464 del_vars.insert(&(bn.variable(node)));
2465 } else {
2466 kept_vars.insert(&(bn.variable(node)));
2467 }
2468 }
2469
2470 // pot_list now contains all the tensors to multiply and marginalize
2471 // => combine the messages
2472 const IScheduleMultiDim* new_pot = _marginalizeOut_(pot_list, del_vars, kept_vars);
2473 ScheduleMultiDim< Tensor< GUM_SCALAR > >* resulting_pot
2474 = const_cast< ScheduleMultiDim< Tensor< GUM_SCALAR > >* >(
2475 static_cast< const ScheduleMultiDim< Tensor< GUM_SCALAR > >* >(new_pot));
2476
2477 // if pot already existed, create a copy, so that we can put it into
2478 // the _target_posteriors_ property
2479 Tensor< GUM_SCALAR >* joint = nullptr;
2480 if (pot_list.exists(resulting_pot)) {
2481 joint = new Tensor< GUM_SCALAR >(resulting_pot->multiDim());
2482 } else {
2483 joint = resulting_pot->exportMultiDim();
2484 delete new_pot;
2485 }
2486
2487 // check that the joint posterior is different from a 0 vector: this would
2488 // indicate that some hard evidence are not compatible
2489 bool nonzero_found = false;
2490 for (Instantiation inst(*joint); !inst.end(); ++inst) {
2491 if ((*joint)[inst]) {
2492 nonzero_found = true;
2493 break;
2494 }
2495 }
2496 if (!nonzero_found) {
2497 // remove joint from memory to avoid memory leaks
2498 delete joint;
2500 "some evidence entered into the Bayes "
2501 "net are incompatible (their joint proba = 0)");
2502 }
2503
2504 // if there exists some nodes in the set of targets that received hard evidence,
2505 // then the joint Tensor needs be multiplied by the evidence tensors of
2506 // these nodes
2507 if (!hard_ev_nodes.empty()) {
2508 _TensorSet_ pot_list;
2509 pot_list.insert(joint);
2510 const auto& hard_evidence = this->evidence();
2511 for (const auto node: hard_ev_nodes)
2512 pot_list.insert(hard_evidence[node]);
2513 MultiDimCombinationDefault< Tensor< GUM_SCALAR > > combine(_combination_op_);
2514 Tensor< GUM_SCALAR >* new_joint = combine.execute(pot_list);
2515 delete joint;
2516 joint = new_joint;
2517 }
2518
2519 return joint;
2520 }
2521
2523 template < GUM_Numeric GUM_SCALAR >
2524 const Tensor< GUM_SCALAR >&
2525 ShaferShenoyInference< GUM_SCALAR >::jointPosterior_(const NodeSet& set) {
2526 // check if we have already computed the posterior
2527 if (_joint_target_posteriors_.exists(set)) { return *(_joint_target_posteriors_[set]); }
2528
2529 // compute the joint posterior and normalize
2530 auto joint = unnormalizedJointPosterior_(set);
2531 joint->normalize();
2532 _joint_target_posteriors_.insert(set, joint);
2533
2534 return *joint;
2535 }
2536
2538 template < GUM_Numeric GUM_SCALAR >
2539 const Tensor< GUM_SCALAR >&
2540 ShaferShenoyInference< GUM_SCALAR >::jointPosterior_(const NodeSet& wanted_target,
2541 const NodeSet& declared_target) {
2542 // check if we have already computed the posterior of wanted_target
2543 if (_joint_target_posteriors_.exists(wanted_target))
2544 return *(_joint_target_posteriors_[wanted_target]);
2545
2546 // here, we will have to compute the posterior of declared_target and
2547 // marginalize out all the variables that do not belong to wanted_target
2548
2549 // check if we have already computed the posterior of declared_target
2550 if (!_joint_target_posteriors_.exists(declared_target)) { jointPosterior_(declared_target); }
2551
2552 // marginalize out all the variables that do not belong to wanted_target
2553 const auto& bn = this->BN();
2554 gum::VariableSet del_vars;
2555 for (const auto node: declared_target)
2556 if (!wanted_target.contains(node)) del_vars.insert(&(bn.variable(node)));
2557 auto pot
2558 = new Tensor< GUM_SCALAR >(_joint_target_posteriors_[declared_target]->sumOut(del_vars));
2559
2560 // save the result into the cache. wanted_target is a subset of declared_target: it belongs to
2561 // the same clique, which tells when the cached posterior is outdated
2562 _joint_target_posteriors_.insert(wanted_target, pot);
2563 if (auto clique = _joint_target_to_clique_.tryGet(declared_target)) {
2564 const NodeId clique_id = *clique; // copied: the insertion may resize the table
2565 if (!_joint_target_to_clique_.exists(wanted_target))
2566 _joint_target_to_clique_.insert(wanted_target, clique_id);
2567 }
2568
2569 return *pot;
2570 }
2571
2572 template < GUM_Numeric GUM_SCALAR >
2573 GUM_SCALAR ShaferShenoyInference< GUM_SCALAR >::evidenceProbability() {
2574 // here, we should check that _find_relevant_tensor_type_ is equal to
2575 // FIND_ALL. Otherwise, the computations could be wrong.
2576 RelevantTensorsFinderType old_relevant_type = _find_relevant_tensor_type_;
2577
2578 // if the relevant tensors finder is not equal to FIND_ALL, all the
2579 // current computations may lead to incorrect results, so we shall
2580 // discard them
2581 if (old_relevant_type != RelevantTensorsFinderType::FIND_ALL) {
2582 _find_relevant_tensor_type_ = RelevantTensorsFinderType::FIND_ALL;
2583 _is_new_jt_needed_ = true;
2584 this->setOutdatedStructureState_();
2585 }
2586
2587 // perform inference in each connected component
2588 this->makeInference();
2589
2590 // for each connected component, select a variable X and compute the
2591 // joint probability of X and evidence e. Then marginalize-out X to get
2592 // p(e) in this connected component. Finally, multiply all the p(e) that
2593 // we got and the elements in _constants_. The result is the probability
2594 // of evidence
2595
2596 GUM_SCALAR prob_ev = 1;
2597 for (const auto root: _roots_) {
2598 // get a node in the clique
2599 NodeId node = *(_JT_->clique(root).begin());
2600 Tensor< GUM_SCALAR >* tmp = unnormalizedJointPosterior_(node);
2601 prob_ev *= tmp->sum();
2602 delete tmp;
2603 }
2604
2605 for (const auto& projected_cpt: _constants_)
2606 prob_ev *= projected_cpt.second;
2607
2608 // put back the relevant tensor type selected by the user
2609 _find_relevant_tensor_type_ = old_relevant_type;
2610
2611 return prob_ev;
2612 }
2613
2614 template < GUM_Numeric GUM_SCALAR >
2615 Tensor< GUM_SCALAR > SSNewmultiTensor(const Tensor< GUM_SCALAR >& t1,
2616 const Tensor< GUM_SCALAR >& t2) {
2617 return t1 * t2;
2618 }
2619
2620 template < GUM_Numeric GUM_SCALAR >
2621 Tensor< GUM_SCALAR > SSNewprojTensor(const Tensor< GUM_SCALAR >& t1,
2622 const gum::VariableSet& del_vars) {
2623 return t1.sumOut(del_vars);
2624 }
2625
2626 template < GUM_Numeric GUM_SCALAR >
2627 void ShaferShenoyInference< GUM_SCALAR >::onStateChanged_() {}
2628
2629} /* namespace gum */
2630
2631#endif // DOXYGEN_SHOULD_SKIP_THIS
The BayesBall algorithm (as described by Schachter).
Implementation of Shafer-Shenoy's algorithm for inference in Bayesian networks.
Detect barren nodes for inference in Bayesian networks.
An algorithm for converting a join tree into a binary join tree.
Exception : a similar element already exists.
<agrum/BN/inference/evidenceInference.h>
Exception : fatal (unknown ?) error.
Class representing the minimal interface for Bayesian network with no numerical data.
Definition IBayesNet.h:79
Exception : several evidence are incompatible together (proba=0).
Exception: at least one argument passed to a function is not what was expected.
<agrum/BN/inference/jointTargetedInference.h>
bool exists(const Key &k) const
Indicates whether a given elements belong to the set.
Definition set_tpl.h:504
void insert(const Key &k)
Inserts a new element into the set.
Definition set_tpl.h:510
iterator_safe beginSafe() const
The usual safe begin iterator to parse the set.
Definition set_tpl.h:385
void erase(const Key &k)
Erases an element from the set.
Definition set_tpl.h:553
Size size() const noexcept
Returns the number of elements in the set.
Definition set_tpl.h:607
static const iterator_safe & endSafe() noexcept
The usual safe end iterator to parse the set.
Definition set_tpl.h:397
ShaferShenoyInference(const IBayesNet< GUM_SCALAR > *BN, RelevantTensorsFinderType=RelevantTensorsFinderType::DSEP_BAYESBALL_TENSORS, FindBarrenNodesType barren_type=FindBarrenNodesType::FIND_BARREN_NODES, bool use_binary_join_tree=true)
default constructor
Exception : a looked-for element could not be found.
d-separation analysis (as described in Koller & Friedman 2009)
#define GUM_ERROR(type, msg)
Definition exceptions.h:76
Set< NodeId > NodeSet
Some typdefs and define for shortcuts ...
GUM_SHARED_PUBLIC bool contains(std::string_view s, std::string_view needle)
true if needle in s
Header files of gum::Instantiation.
Selection of the roots of the connected components of a junction tree.
gum is the global namespace for all aGrUM entities
Definition agrum.h:46
FindBarrenNodesType
type of algorithm to determine barren nodes
Set< const DiscreteVariable * > VariableSet
NodeSet junctionTreeRoots(const JunctionTree &jt, const GraphicalModel &model, const NodeSet &preferred)
Returns one root for each connected component of a junction tree.
CliqueGraph JoinTree
a join tree is a clique graph satisfying the running intersection property (but some cliques may be i...
CliqueGraph JunctionTree
a junction tree is a clique graph satisfying the running intersection property and such that no cliqu...
RelevantTensorsFinderType
type of algorithm for determining the relevant tensors for combinations using some d-separation analy...