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