aGrUM 3.3.2
a C++ library for (probabilistic) graphical models
ShaferShenoyMRFInference_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/MRF/inference/ShaferShenoyMRFInference.h> // to ease IDE parser
54#ifndef DOXYGEN_SHOULD_SKIP_THIS
55# include <algorithm>
56
62
63namespace gum {
64 // default constructor
65 template < GUM_Numeric GUM_SCALAR >
68 bool use_binary_join_tree) :
69 JointTargetedMRFInference< GUM_SCALAR >(MN), EvidenceMRFInference< GUM_SCALAR >(MN),
70 _use_binary_join_tree_(use_binary_join_tree) {
71 // create a default triangulation (the user can change it afterwards)
72 _triangulation_ = new DefaultTriangulation;
73
74 // for each node in the MRF, assign the set of factors that contain it
75 const auto& graph = this->MRF().internalGraph();
76 _node_to_factors_.resize(graph.size());
77 _TensorSet_ empty;
78 for (const auto node: graph)
79 _node_to_factors_.insert(node, empty);
80 for (const auto& factor: this->MRF().factors()) {
81 for (const auto node: factor.first) {
82 _node_to_factors_[node].insert(factor.second);
83 }
84 }
85
86 // for debugging purposes
87 GUM_CONSTRUCTOR(ShaferShenoyMRFInference);
88 }
89
90 // destructor
91 template < GUM_Numeric GUM_SCALAR >
92 ShaferShenoyMRFInference< GUM_SCALAR >::~ShaferShenoyMRFInference() {
93 // remove all the tensors created during the last message passing
94 for (const auto& pot: _arc_to_created_tensors_)
95 delete pot.second;
96
97 // remove all the tensors in _clique_ss_tensor_ that do not belong
98 // to _clique_tensors_: in this case, those tensors have been
99 // created by combination of the corresponding list of tensors in
100 // _clique_tensors_. In other words, the size of this list is strictly
101 // greater than 1.
102 for (auto pot: _clique_ss_tensor_) {
103 if (_clique_tensors_[pot.first].size() > 1) delete pot.second;
104 }
105
106 for (auto potset: _clique_tensors_) {
107 for (auto pot: potset.second)
108 delete pot;
109 }
110
111 // remove all the posteriors computed
112 for (const auto& pot: _target_posteriors_)
113 delete pot.second;
114 for (const auto& pot: _joint_target_posteriors_)
115 delete pot.second;
116
117 // remove the junction tree and the triangulation algorithm
118 if (_JT_ != nullptr) delete _JT_;
119 if (_junctionTree_ != nullptr) delete _junctionTree_;
120 delete _triangulation_;
121
122 // for debugging purposes
123 GUM_DESTRUCTOR(ShaferShenoyMRFInference);
124 }
125
127 template < GUM_Numeric GUM_SCALAR >
128 void ShaferShenoyMRFInference< GUM_SCALAR >::setTriangulation(
129 const Triangulation& new_triangulation) {
130 delete _triangulation_;
131 _triangulation_ = new_triangulation.newFactory();
132 _is_new_jt_needed_ = true;
133 this->setOutdatedStructureState_();
134 }
135
137 template < GUM_Numeric GUM_SCALAR >
138 const JoinTree* ShaferShenoyMRFInference< GUM_SCALAR >::joinTree() {
139 if (_is_new_jt_needed_) _createNewJT_();
140
141 return _JT_;
142 }
143
145 template < GUM_Numeric GUM_SCALAR >
146 const JunctionTree* ShaferShenoyMRFInference< GUM_SCALAR >::junctionTree() {
147 if (_is_new_jt_needed_) _createNewJT_();
148
149 return _junctionTree_;
150 }
151
153 template < GUM_Numeric GUM_SCALAR >
154 void ShaferShenoyMRFInference< GUM_SCALAR >::_setProjectionFunction_(
155 Tensor< GUM_SCALAR > (*proj)(const Tensor< GUM_SCALAR >&, const gum::VariableSet&)) {
156 _projection_op_ = proj;
157
158 // indicate that all messages need be reconstructed to take into account
159 // the change in of the projection operator
160 _invalidateAllMessages_();
161 }
162
164 template < GUM_Numeric GUM_SCALAR >
165 void ShaferShenoyMRFInference< GUM_SCALAR >::_setCombinationFunction_(
166 Tensor< GUM_SCALAR > (*comb)(const Tensor< GUM_SCALAR >&, const Tensor< GUM_SCALAR >&)) {
167 _combination_op_ = comb;
168
169 // indicate that all messages need be reconstructed to take into account
170 // the change of the combination operator
171 _invalidateAllMessages_();
172 }
173
175 template < GUM_Numeric GUM_SCALAR >
176 void ShaferShenoyMRFInference< GUM_SCALAR >::_invalidateAllMessages_() {
177 // remove all the messages computed
178 for (auto& pot: _separator_tensors_)
179 pot.second = nullptr;
180
181 for (auto& mess_computed: _messages_computed_)
182 mess_computed.second = false;
183
184 // remove all the created tensors kept on the arcs
185 for (const auto& pot: _arc_to_created_tensors_)
186 if (pot.second != nullptr) delete pot.second;
187 _arc_to_created_tensors_.clear();
188
189 // remove all the posteriors
190 for (const auto& pot: _target_posteriors_)
191 delete pot.second;
192 _target_posteriors_.clear();
193 for (const auto& pot: _joint_target_posteriors_)
194 delete pot.second;
195 _joint_target_posteriors_.clear();
196
197 // indicate that new messages need be computed
198 if (this->isInferenceReady() || this->isInferenceDone()) this->setOutdatedTensorsState_();
199 }
200
202 template < GUM_Numeric GUM_SCALAR >
203 void ShaferShenoyMRFInference< GUM_SCALAR >::onEvidenceAdded_(const NodeId id,
204 bool isHardEvidence) {
205 // if we have a new hard evidence, this modifies the undigraph over which
206 // the join tree is created. This is also the case if id is not a node of
207 // of the undigraph
208 if (isHardEvidence || !_graph_.exists(id)) _is_new_jt_needed_ = true;
209 else {
210 try {
211 _evidence_changes_.insert(id, EvidenceChangeType::EVIDENCE_ADDED);
212 } catch (DuplicateElement const&) {
213 // here, the evidence change already existed. This necessarily means
214 // that the current saved change is an EVIDENCE_ERASED. So if we
215 // erased the evidence and added some again, this corresponds to an
216 // EVIDENCE_MODIFIED
217 _evidence_changes_[id] = EvidenceChangeType::EVIDENCE_MODIFIED;
218 }
219 }
220 }
221
223 template < GUM_Numeric GUM_SCALAR >
224 void ShaferShenoyMRFInference< GUM_SCALAR >::onEvidenceErased_(const NodeId id,
225 bool isHardEvidence) {
226 // if we delete a hard evidence, this modifies the undigraph over which
227 // the join tree is created.
228 if (isHardEvidence) _is_new_jt_needed_ = true;
229 else {
230 try {
231 _evidence_changes_.insert(id, EvidenceChangeType::EVIDENCE_ERASED);
232 } catch (DuplicateElement const&) {
233 // here, the evidence change already existed and it is necessarily an
234 // EVIDENCE_ADDED or an EVIDENCE_MODIFIED. So, if the evidence has
235 // been added and is now erased, this is similar to not having created
236 // it. If the evidence was only modified, it already existed in the
237 // last inference and we should now indicate that it has been removed.
238 if (_evidence_changes_[id] == EvidenceChangeType::EVIDENCE_ADDED)
239 _evidence_changes_.erase(id);
240 else _evidence_changes_[id] = EvidenceChangeType::EVIDENCE_ERASED;
241 }
242 }
243 }
244
246 template < GUM_Numeric GUM_SCALAR >
247 void ShaferShenoyMRFInference< GUM_SCALAR >::onAllEvidenceErased_(bool has_hard_evidence) {
248 if (has_hard_evidence || !this->hardEvidenceNodes().empty()) _is_new_jt_needed_ = true;
249 else {
250 for (const auto node: this->softEvidenceNodes()) {
251 try {
252 _evidence_changes_.insert(node, EvidenceChangeType::EVIDENCE_ERASED);
253 } catch (DuplicateElement const&) {
254 // here, the evidence change already existed and it is necessarily an
255 // EVIDENCE_ADDED or an EVIDENCE_MODIFIED. So, if the evidence has
256 // been added and is now erased, this is similar to not having created
257 // it. If the evidence was only modified, it already existed in the
258 // last inference and we should now indicate that it has been removed.
259 if (_evidence_changes_[node] == EvidenceChangeType::EVIDENCE_ADDED)
260 _evidence_changes_.erase(node);
261 else _evidence_changes_[node] = EvidenceChangeType::EVIDENCE_ERASED;
262 }
263 }
264 }
265 }
266
268 template < GUM_Numeric GUM_SCALAR >
269 void ShaferShenoyMRFInference< GUM_SCALAR >::onEvidenceChanged_(const NodeId id,
270 bool hasChangedSoftHard) {
271 if (hasChangedSoftHard) _is_new_jt_needed_ = true;
272 else {
273 try {
274 _evidence_changes_.insert(id, EvidenceChangeType::EVIDENCE_MODIFIED);
275 } catch (DuplicateElement const&) {
276 // here, the evidence change already existed and it is necessarily an
277 // EVIDENCE_ADDED. So we should keep this state to indicate that this
278 // evidence is new w.r.t. the last inference
279 }
280 }
281 }
282
284 template < GUM_Numeric GUM_SCALAR >
285 void ShaferShenoyMRFInference< GUM_SCALAR >::onMarginalTargetAdded_(const NodeId id) {}
286
288 template < GUM_Numeric GUM_SCALAR >
289 void ShaferShenoyMRFInference< GUM_SCALAR >::onMarginalTargetErased_(const NodeId id) {}
290
292 template < GUM_Numeric GUM_SCALAR >
293 void ShaferShenoyMRFInference< GUM_SCALAR >::onJointTargetAdded_(const NodeSet& set) {}
294
296 template < GUM_Numeric GUM_SCALAR >
297 void ShaferShenoyMRFInference< GUM_SCALAR >::onJointTargetErased_(const NodeSet& set) {}
298
300 template < GUM_Numeric GUM_SCALAR >
301 void ShaferShenoyMRFInference< GUM_SCALAR >::onAllMarginalTargetsAdded_() {}
302
304 template < GUM_Numeric GUM_SCALAR >
305 void ShaferShenoyMRFInference< GUM_SCALAR >::onAllMarginalTargetsErased_() {}
306
308 template < GUM_Numeric GUM_SCALAR >
309 void ShaferShenoyMRFInference< GUM_SCALAR >::onMRFChanged_(
310 const IMarkovRandomField< GUM_SCALAR >* mn) {}
311
313 template < GUM_Numeric GUM_SCALAR >
314 void ShaferShenoyMRFInference< GUM_SCALAR >::onAllJointTargetsErased_() {}
315
317 template < GUM_Numeric GUM_SCALAR >
318 void ShaferShenoyMRFInference< GUM_SCALAR >::onAllTargetsErased_() {}
319
320 // check whether a new junction tree is really needed for the next inference
321 template < GUM_Numeric GUM_SCALAR >
322 bool ShaferShenoyMRFInference< GUM_SCALAR >::_isNewJTNeeded_() const {
323 // if we do not have a JT or if _new_jt_needed_ is set to true, then
324 // we know that we need to create a new join tree
325 if ((_JT_ == nullptr) || _is_new_jt_needed_) return true;
326
327 // if some targets do not belong to the join tree and, consequently, to the
328 // undirected graph that was used to construct the join tree, then we need
329 // to create a new JT: this may happen due to the nodes that received hard
330 // evidence (which do not belong to the graph).
331 const auto& hard_ev_nodes = this->hardEvidenceNodes();
332 for (const auto node: this->targets()) {
333 if (!_graph_.exists(node) && !hard_ev_nodes.exists(node)) return true;
334 }
335
336 // now, do the same for the joint targets
337 const std::vector< NodeId >& JT_elim_order = _triangulation_->eliminationOrder();
338 NodeProperty< int > elim_order(Size(JT_elim_order.size()));
339 for (std::size_t i = std::size_t(0), size = JT_elim_order.size(); i < size; ++i)
340 elim_order.insert(JT_elim_order[i], (int)i);
341 NodeSet unobserved_set;
342
343 for (const auto& joint_target: this->jointTargets()) {
344 // here, we need to check that at least one clique contains all the
345 // nodes of the joint target.
346 NodeId first_eliminated_node = std::numeric_limits< NodeId >::max();
347 int elim_number = std::numeric_limits< int >::max();
348 unobserved_set.clear();
349 for (const auto node: joint_target) {
350 if (!_graph_.exists(node)) {
351 if (!hard_ev_nodes.exists(node)) return true;
352 } else {
353 unobserved_set.insert(node);
354 if (elim_order[node] < elim_number) {
355 elim_number = elim_order[node];
356 first_eliminated_node = node;
357 }
358 }
359 }
360 if (!unobserved_set.empty()) {
361 // here, first_eliminated_node contains the first var (node or one of its
362 // parents) eliminated => the clique created during its elimination
363 // should contain all the nodes in unobserved_set
364 const auto clique_id = _node_to_clique_[first_eliminated_node];
365 const auto& clique = _JT_->clique(clique_id);
366 for (const auto node: unobserved_set) {
367 if (!clique.contains(node)) return true;
368 }
369 }
370 }
371
372 // if some new evidence have been added on nodes that do not belong
373 // to _graph_, then we tensorly have to reconstruct the join tree
374 for (const auto& change: _evidence_changes_) {
375 if ((change.second == EvidenceChangeType::EVIDENCE_ADDED) && !_graph_.exists(change.first))
376 return true;
377 }
378
379 // here, the current JT is exactly what we need for the next inference
380 return false;
381 }
382
384 template < GUM_Numeric GUM_SCALAR >
385 void ShaferShenoyMRFInference< GUM_SCALAR >::_createNewJT_() {
386 // to create the JT, we first create the required subgraph of the MRF in the
387 // following way, in order to take into account the nodes that received
388 // evidence:
389 // 1/ we copy the graph of the MRF
390 // 2/ add edges so that joint targets form a clique of the graph
391 // 3/ remove the nodes that received hard evidence
392 //
393 // At the end of step 3/, we have our required graph and we can triangulate
394 // it to get the new junction tree
395
396 // 1/ copy the undirected graph of the MRF
397 const auto& mn = this->MRF();
398 _graph_ = mn.internalGraph();
399
400 // 2/ if there exist some joint targets, we shall add new edges into the
401 // undirected graph in order to ensure that there exists a clique containing
402 // each joint target
403 for (const auto& nodeset: this->jointTargets()) {
404 for (auto iter1 = nodeset.cbegin(); iter1 != nodeset.cend(); ++iter1) {
405 auto iter2 = iter1;
406 for (++iter2; iter2 != nodeset.cend(); ++iter2) {
407 _graph_.addEdge(*iter1, *iter2);
408 }
409 }
410 }
411
412 // 3/ remove all the nodes that received hard evidence
413 _hard_ev_nodes_ = this->hardEvidenceNodes();
414 for (const auto node: _hard_ev_nodes_) {
415 _graph_.eraseNode(node);
416 }
417
418
419 // now, we can compute the new junction tree. To speed-up computations
420 // (essentially, those of a distribution phase), we construct from this
421 // junction tree a binary join tree
422 if (_JT_ != nullptr) delete _JT_;
423 if (_junctionTree_ != nullptr) delete _junctionTree_;
424
425 const auto& domain_sizes = this->domainSizes();
426 _triangulation_->setGraph(&_graph_, &domain_sizes);
427 const JunctionTree& triang_jt = _triangulation_->junctionTree();
428 if (_use_binary_join_tree_) {
429 BinaryJoinTreeConverterDefault bjt_converter;
430 NodeSet emptyset;
431 _JT_ = new CliqueGraph(bjt_converter.convert(triang_jt, domain_sizes, emptyset));
432 } else {
433 _JT_ = new CliqueGraph(triang_jt);
434 }
435 _junctionTree_ = new CliqueGraph(triang_jt);
436
437
438 // assign to each node the order in which it was eliminated by the triangulation
439 const std::vector< NodeId >& JT_elim_order = _triangulation_->eliminationOrder();
440 Size size_elim_order = JT_elim_order.size();
441 NodeProperty< int > elim_order(size_elim_order);
442 for (Idx i = Idx(0); i < size_elim_order; ++i)
443 elim_order.insert(JT_elim_order[i], (int)i);
444
445 // assign to each factor of the Markov random field a clique in _JT_
446 // that can contain its conditional probability table
447 _factor_to_clique_.clear();
448 _factor_to_clique_.resize(mn.factors().size());
449 for (const auto& factor: mn.factors()) {
450 const auto& nodes = factor.first; // factor.second is the Tensor()
451 NodeId first_eliminated_node = std::numeric_limits< NodeId >::max();
452 int elim_number = std::numeric_limits< int >::max();
453 for (const auto node: nodes) {
454 if (_graph_.exists(node) && (elim_order[node] < elim_number)) {
455 elim_number = elim_order[node];
456 first_eliminated_node = node;
457 }
458 }
459
460 if (elim_number != std::numeric_limits< int >::max()) {
461 // first_eliminated_node contains the first var/node eliminated => the
462 // clique created during its elimination must contain node and all of its
463 // neighbors => it necessarily contains all the nodes of factor
464 _factor_to_clique_.insert(
465 factor.second,
466 _triangulation_->createdJunctionTreeClique(first_eliminated_node));
467 }
468 }
469
470 // assign to each node that did not receive some hard evidence the smallest
471 // clique that contains it
472 _node_to_clique_.clear();
473 _node_to_clique_.resize(_graph_.size());
474 NodeProperty< double > node_to_clique_size(_graph_.size());
475 for (const auto node: _graph_) {
476 _node_to_clique_.insert(node, std::numeric_limits< NodeId >::max());
477 node_to_clique_size.insert(node, std::numeric_limits< double >::max());
478 }
479 double overall_size = 0;
480 for (const auto clique_id: *_JT_) {
481 // determine the size of clique_id
482 const auto& clique_nodes = _JT_->clique(clique_id);
483 double clique_size = 1.0;
484 for (const auto node: clique_nodes)
485 clique_size *= double(domain_sizes[node]);
486 overall_size += clique_size;
487
488 // assign the clique to the nodes if its size is smaller than that of the
489 // current cliques assigned to them
490 for (const auto node: clique_nodes) {
491 if (clique_size < node_to_clique_size[node]) {
492 _node_to_clique_[node] = clique_id;
493 node_to_clique_size[node] = clique_size;
494 }
495 }
496 }
497
498 // indicate for each joint_target a clique that contains it
499 _joint_target_to_clique_.clear();
500 for (const auto& set: this->jointTargets()) {
501 NodeId first_eliminated_node = std::numeric_limits< NodeId >::max();
502 int elim_number = std::numeric_limits< int >::max();
503
504 // do not take into account the nodes that received hard evidence
505 // (since they do not belong to the join tree)
506 for (const auto node: set) {
507 if (!_hard_ev_nodes_.contains(node)) {
508 // the clique we are looking for is the one that was created when
509 // the first element of nodeset was eliminated
510 if (elim_order[node] < elim_number) {
511 elim_number = elim_order[node];
512 first_eliminated_node = node;
513 }
514 }
515 }
516
517 if (elim_number != std::numeric_limits< int >::max()) {
518 _joint_target_to_clique_.insert(
519 set,
520 _triangulation_->createdJunctionTreeClique(first_eliminated_node));
521 }
522 }
523
524 // compute the roots of _JT_'s connected components
525 _computeJoinTreeRoots_();
526
527 // remove all the tensors stored into the cliques. Note that these include
528 // the factors resulting from the projections of hard evidence as well as the
529 // CPTs of the soft evidence
530 for (const auto& pot: _clique_ss_tensor_) {
531 if (_clique_tensors_[pot.first].size() > 1) delete pot.second;
532 }
533 _clique_ss_tensor_.clear();
534 for (const auto& potlist: _clique_tensors_)
535 for (const auto pot: potlist.second)
536 delete pot;
537 _clique_tensors_.clear();
538
539 // remove all the tensors created during the last inference
540 for (const auto& pot: _arc_to_created_tensors_)
541 delete pot.second;
542 _arc_to_created_tensors_.clear();
543
544 // remove all the tensors created to take into account hard evidence
545 // during the last inference (they have already been deleted from memory
546 // by the clearing of _clique_tensors_).
547 _hard_ev_projected_factors_.clear();
548
549 // remove all the soft evidence.
550 _node_to_soft_evidence_.clear();
551
552 // create empty tensor lists into the cliques of the joint tree as well
553 // as empty lists of evidence
554 _ScheduleMultiDimSet_ empty_set;
555 for (const auto node: *_JT_) {
556 _clique_tensors_.insert(node, empty_set);
557 _clique_ss_tensor_.insert(node, nullptr);
558 }
559
560 // remove all the constants created due to projections of CPTs that were
561 // defined over only hard evidence nodes
562 _constants_.clear();
563
564 // create empty messages and indicate that no message has been computed yet
565 _separator_tensors_.clear();
566 _messages_computed_.clear();
567 for (const auto& edge: _JT_->edges()) {
568 const Arc arc1(edge.first(), edge.second());
569 _separator_tensors_.insert(arc1, nullptr);
570 _messages_computed_.insert(arc1, false);
571 const Arc arc2(edge.second(), edge.first());
572 _separator_tensors_.insert(arc2, nullptr);
573 _messages_computed_.insert(arc2, false);
574 }
575
576 // remove all the posteriors computed so far
577 for (const auto& pot: _target_posteriors_)
578 delete pot.second;
579 _target_posteriors_.clear();
580 for (const auto& pot: _joint_target_posteriors_)
581 delete pot.second;
582 _joint_target_posteriors_.clear();
583
584 // here, we determine whether we should use schedules during the inference.
585 // the rule is: if the sum of the domain sizes of the cliques is greater
586 // than a threshold, use schedules
587 _use_schedules_ = (overall_size > _schedule_threshold_);
588
589 // we shall now add all the tensors of the soft evidence to the cliques
590 const NodeProperty< const Tensor< GUM_SCALAR >* >& evidence = this->evidence();
591 for (const auto node: this->softEvidenceNodes()) {
592 if (auto p = _node_to_clique_.tryGet(node)) {
593 auto ev_pot = new ScheduleMultiDim< Tensor< GUM_SCALAR > >(*evidence[node], false);
594 _node_to_soft_evidence_.insert(node, ev_pot);
595 _clique_tensors_[*p].insert(ev_pot);
596 }
597 }
598
599 // put all the factors of the MRF into the cliques
600 // here, beware: all the tensors that are defined over some nodes
601 // including hard evidence must be projected so that these nodes are
602 // removed from the tensor
603 if (_use_schedules_) {
604 Schedule schedule;
605 _initializeJTCliques_(schedule);
606 } else {
607 _initializeJTCliques_();
608 }
609
610
611 // indicate that the data structures are up to date.
612 _evidence_changes_.clear();
613 _is_new_jt_needed_ = false;
614 }
615
617 template < GUM_Numeric GUM_SCALAR >
618 void ShaferShenoyMRFInference< GUM_SCALAR >::_initializeJTCliques_() {
619 const auto& mn = this->MRF();
620
621 // put all the factors of the MRF into the cliques
622 // here, beware: all the tensors that are defined over some nodes
623 // including hard evidence must be projected so that these nodes are
624 // removed from the tensor
625 const NodeProperty< const Tensor< GUM_SCALAR >* >& evidence = this->evidence();
626 const NodeProperty< Idx >& hard_evidence = this->hardEvidence();
627
628 for (const auto& factor: mn.factors()) {
629 const auto& factor_nodes = factor.first;
630 const auto& pot = *(factor.second);
631 const auto& variables = pot.variablesSequence();
632
633 // get the list of nodes with hard evidence in the factor
634 NodeSet hard_nodes(factor_nodes.size());
635 bool graph_contains_nodes = false;
636 for (const auto node: factor_nodes) {
637 if (_hard_ev_nodes_.contains(node)) hard_nodes.insert(node);
638 else if (_graph_.exists(node)) graph_contains_nodes = true;
639 }
640
641 // if hard_nodes contains hard evidence nodes, perform a projection
642 // and insert the result into the appropriate clique, else insert
643 // directly pot into the clique
644 if (hard_nodes.empty()) {
645 auto sched_cpt = new ScheduleMultiDim< Tensor< GUM_SCALAR > >(pot, false);
646 _clique_tensors_[_factor_to_clique_[&pot]].insert(sched_cpt);
647 } else {
648 // marginalize out the hard evidence nodes: if factor_nodes is defined
649 // only over nodes that received hard evidence, do not consider it
650 // as a tensor anymore but as a constant
651 // TODO substitute constants by 0-dimensional tensors
652 if (hard_nodes.size() == factor_nodes.size()) {
653 Instantiation inst(pot);
654 for (Size i = 0; i < hard_nodes.size(); ++i) {
655 inst.chgVal(*variables[i], hard_evidence[mn.nodeId(*(variables[i]))]);
656 }
657 _constants_.insert(&pot, pot.get(inst));
658 } else {
659 // here, we have a factor defined over some nodes that received hard
660 // evidence and other nodes that did not receive it. If none of the
661 // latter belong to the graph, then the factor is useless for inference
662 if (!graph_contains_nodes) continue;
663
664 // prepare the projection with a combine and project instance
665 gum::VariableSet hard_variables;
666 _TensorSet_ marg_factor_set(1 + hard_nodes.size());
667 marg_factor_set.insert(&pot);
668 for (const auto node: hard_nodes) {
669 marg_factor_set.insert(evidence[node]);
670 hard_variables.insert(&(mn.variable(node)));
671 }
672
673 // perform the combination of those tensors and their projection
674 MultiDimCombineAndProjectDefault< Tensor< GUM_SCALAR > > combine_and_project(
675 _combination_op_,
676 _projection_op_);
677
678 _TensorSet_ new_factor_list
679 = combine_and_project.execute(marg_factor_set, hard_variables);
680
681 // there should be only one tensor in new_factor_list
682 if (new_factor_list.size() != 1) {
683 for (const auto pot: new_factor_list) {
684 if (!marg_factor_set.contains(pot)) delete pot;
685 }
687 "the projection of a tensor containing " << "hard evidence is empty!");
688 }
689 auto new_factor = const_cast< Tensor< GUM_SCALAR >* >(*(new_factor_list.begin()));
690 auto projected_factor
691 = new ScheduleMultiDim< Tensor< GUM_SCALAR > >(std::move(*new_factor));
692 delete new_factor;
693
694 _clique_tensors_[_factor_to_clique_[&pot]].insert(projected_factor);
695 _hard_ev_projected_factors_.insert(&pot, projected_factor);
696 }
697 }
698 }
699
700 // now, in _clique_tensors_, for each clique, we have the list of
701 // tensors that must be combined in order to produce the Shafer-Shenoy's
702 // tensor stored into the clique. So, perform this combination and
703 // store the result in _clique_ss_tensor_
704 MultiDimCombinationDefault< Tensor< GUM_SCALAR > > fast_combination(_combination_op_);
705 for (const auto& xpotset: _clique_tensors_) {
706 const auto& potset = xpotset.second;
707 if (potset.size() > 0) {
708 // here, there will be an entry in _clique_ss_tensor_
709 // If there is only one element in potset, this element shall be
710 // stored into _clique_ss_tensor_, else all the elements of potset
711 // shall be combined and their result shall be stored
712 if (potset.size() == 1) {
713 _clique_ss_tensor_[xpotset.first] = *(potset.cbegin());
714 } else {
715 _TensorSet_ p_potset(potset.size());
716 for (const auto pot: potset)
717 p_potset.insert(
718 &(static_cast< const ScheduleMultiDim< Tensor< GUM_SCALAR > >* >(pot)->multiDim()));
719
720 Tensor< GUM_SCALAR >* joint
721 = const_cast< Tensor< GUM_SCALAR >* >(fast_combination.execute(p_potset));
722 _clique_ss_tensor_[xpotset.first]
723 = new ScheduleMultiDim< Tensor< GUM_SCALAR > >(std::move(*joint));
724 delete joint;
725 }
726 }
727 }
728 }
729
731 template < GUM_Numeric GUM_SCALAR >
732 void ShaferShenoyMRFInference< GUM_SCALAR >::_initializeJTCliques_(Schedule& schedule) {
733 const auto& mn = this->MRF();
734
735 // put all the factors of the MRF into the cliques
736 // here, beware: all the tensors that are defined over some nodes
737 // including hard evidence must be projected so that these nodes are
738 // removed from the tensor
739 const NodeProperty< const Tensor< GUM_SCALAR >* >& evidence = this->evidence();
740 const NodeProperty< Idx >& hard_evidence = this->hardEvidence();
741
742 for (const auto& factor: mn.factors()) {
743 const auto& factor_nodes = factor.first;
744 const auto& pot = *(factor.second);
745 const auto& variables = pot.variablesSequence();
746
747 // get the list of nodes with hard evidence in the factor
748 NodeSet hard_nodes;
749 bool graph_contains_nodes = false;
750 for (const auto node: factor_nodes) {
751 if (_hard_ev_nodes_.contains(node)) hard_nodes.insert(node);
752 else if (_graph_.exists(node)) graph_contains_nodes = true;
753 }
754
755 // if hard_nodes contains hard evidence nodes, perform a projection
756 // and insert the result into the appropriate clique, else insert
757 // directly pot into the clique
758 if (hard_nodes.empty()) {
759 auto sched_cpt = new ScheduleMultiDim< Tensor< GUM_SCALAR > >(pot, false);
760 _clique_tensors_[_factor_to_clique_[&pot]].insert(sched_cpt);
761 } else {
762 // marginalize out the hard evidence nodes: if factor_nodes is defined
763 // only over nodes that received hard evidence, do not consider it
764 // as a tensor anymore but as a constant
765 // TODO substitute constants by 0-dimensional tensors
766 if (hard_nodes.size() == factor_nodes.size()) {
767 Instantiation inst(pot);
768 for (Size i = 0; i < hard_nodes.size(); ++i) {
769 inst.chgVal(*variables[i], hard_evidence[mn.nodeId(*(variables[i]))]);
770 }
771 _constants_.insert(&pot, pot.get(inst));
772 } else {
773 // here, we have a factor defined over some nodes that received hard
774 // evidence and other nodes that did not receive it. If none of the
775 // latter belong to the graph, then the factor is useless for inference
776 if (!graph_contains_nodes) continue;
777
778 // prepare the projection with a combine and project instance
779 gum::VariableSet hard_variables;
780 _ScheduleMultiDimSet_ marg_factor_set(1 + hard_nodes.size());
781 const IScheduleMultiDim* sched_pot
782 = schedule.insertTable< Tensor< GUM_SCALAR > >(pot, false);
783 marg_factor_set.insert(sched_pot);
784
785 for (const auto node: hard_nodes) {
786 const IScheduleMultiDim* pot
787 = schedule.insertTable< Tensor< GUM_SCALAR > >(*evidence[node], false);
788 marg_factor_set.insert(pot);
789 hard_variables.insert(&(mn.variable(node)));
790 }
791
792 // perform the combination of those tensors and their projection
793 MultiDimCombineAndProjectDefault< Tensor< GUM_SCALAR > > combine_and_project(
794 _combination_op_,
795 _projection_op_);
796
797 _ScheduleMultiDimSet_ new_factor_list
798 = combine_and_project.schedule(schedule, marg_factor_set, hard_variables);
799
800 // there should be only one tensor in new_factor_list
801 if (new_factor_list.size() != 1) {
803 "the projection of a tensor containing " << "hard evidence is empty!");
804 }
805 auto projected_factor = const_cast< ScheduleMultiDim< Tensor< GUM_SCALAR > >* >(
806 static_cast< const ScheduleMultiDim< Tensor< GUM_SCALAR > >* >(
807 *new_factor_list.begin()));
808 const_cast< ScheduleOperator* >(schedule.scheduleMultiDimCreator(projected_factor))
809 ->makeResultsPersistent(true);
810
811 _clique_tensors_[_factor_to_clique_[&pot]].insert(projected_factor);
812 _hard_ev_projected_factors_.insert(&pot, projected_factor);
813 }
814 }
815 }
816 this->scheduler().execute(schedule);
817
818 // now, in _clique_tensors_, for each clique, we have the list of
819 // tensors that must be combined in order to produce the Shafer-Shenoy's
820 // tensor stored into the clique. So, perform this combination and
821 // store the result in _clique_ss_tensor_
822 schedule.clear();
823 MultiDimCombinationDefault< Tensor< GUM_SCALAR > > fast_combination(_combination_op_);
824 for (const auto& xpotset: _clique_tensors_) {
825 const auto& potset = xpotset.second;
826 if (potset.size() > 0) {
827 // here, there will be an entry in _clique_ss_tensor_
828 // If there is only one element in potset, this element shall be
829 // stored into _clique_ss_tensor_, else all the elements of potset
830 // shall be combined and their result shall be stored
831 if (potset.size() == 1) {
832 _clique_ss_tensor_[xpotset.first] = *(potset.cbegin());
833 } else {
834 // add the tables to combine into the schedule
835 for (const auto pot: potset) {
836 schedule.emplaceScheduleMultiDim(*pot);
837 }
838
839 auto joint = const_cast< ScheduleMultiDim< Tensor< GUM_SCALAR > >* >(
840 static_cast< const ScheduleMultiDim< Tensor< GUM_SCALAR > >* >(
841 fast_combination.schedule(schedule, potset)));
842 const_cast< ScheduleOperator* >(schedule.scheduleMultiDimCreator(joint))
843 ->makeResultsPersistent(true);
844 _clique_ss_tensor_[xpotset.first] = joint;
845 }
846 }
847 }
848 this->scheduler().execute(schedule);
849 }
850
852 template < GUM_Numeric GUM_SCALAR >
853 void ShaferShenoyMRFInference< GUM_SCALAR >::updateOutdatedStructure_() {
854 // check if a new JT is really needed. If so, create it
855 if (_isNewJTNeeded_()) {
856 _createNewJT_();
857 } else {
858 // here, we can answer the next queries without reconstructing all the
859 // junction tree. All we need to do is to indicate that we should
860 // update the tensors and messages for these queries
861 updateOutdatedTensors_();
862 }
863 }
864
866 template < GUM_Numeric GUM_SCALAR >
867 void ShaferShenoyMRFInference< GUM_SCALAR >::_diffuseMessageInvalidations_(
868 NodeId from_id,
869 NodeId to_id,
870 NodeSet& invalidated_cliques) {
871 // invalidate the current clique
872 invalidated_cliques.insert(to_id);
873
874 // invalidate the current arc
875 const Arc arc(from_id, to_id);
876 bool& message_computed = _messages_computed_[arc];
877 if (message_computed) {
878 message_computed = false;
879 _separator_tensors_[arc] = nullptr;
880 if (_arc_to_created_tensors_.exists(arc)) {
881 delete _arc_to_created_tensors_[arc];
882 _arc_to_created_tensors_.erase(arc);
883 }
884
885 // go on with the diffusion
886 for (const auto node_id: _JT_->neighbours(to_id)) {
887 if (node_id != from_id) _diffuseMessageInvalidations_(to_id, node_id, invalidated_cliques);
888 }
889 }
890 }
891
894 template < GUM_Numeric GUM_SCALAR >
895 void ShaferShenoyMRFInference< GUM_SCALAR >::updateOutdatedTensors_() {
896 // for each clique, indicate whether the tensor stored into
897 // _clique_ss_tensor_[clique] is the result of a combination. In this
898 // case, it has been allocated by the combination and will need to be
899 // deallocated if its clique has been invalidated
900 NodeProperty< bool > ss_tensor_to_deallocate(_clique_tensors_.size());
901 for (const auto& potset: _clique_tensors_) {
902 ss_tensor_to_deallocate.insert(potset.first, (potset.second.size() > 1));
903 }
904
905 // compute the set of factors that were projected due to hard evidence and
906 // whose hard evidence have changed, so that they need a new projection.
907 // By the way, remove these factors since they are no more needed
908 // Here only the values of the hard evidence can have changed (else a
909 // fully new join tree would have been computed).
910 // Note also that we know that the factors still contain some variable(s) after
911 // the projection (else they should be constants)
912 const auto& mn = this->MRF();
913 NodeSet hard_nodes_changed(_hard_ev_nodes_.size());
914 Set< const Tensor< GUM_SCALAR >* > hard_projected_factors_changed(mn.factors().size());
915 for (const auto node: _hard_ev_nodes_) {
916 if (_evidence_changes_.exists(node)) {
917 hard_nodes_changed.insert(node);
918 for (const auto pot: _node_to_factors_[node]) {
919 if (_hard_ev_projected_factors_.exists(pot)
920 && !hard_projected_factors_changed.exists(pot)) {
921 hard_projected_factors_changed.insert(pot);
922 }
923 }
924 }
925 }
926
927 NodeSet hard_cliques_changed(hard_projected_factors_changed.size());
928 for (const auto pot: hard_projected_factors_changed) {
929 const auto chgPot = _hard_ev_projected_factors_[pot];
930 const NodeId chgClique = _factor_to_clique_[pot];
931 _clique_tensors_[chgClique].erase(chgPot);
932 _hard_ev_projected_factors_.erase(pot);
933 if (!hard_cliques_changed.contains(chgClique)) hard_cliques_changed.insert(chgClique);
934 delete chgPot;
935 }
936
937
938 // invalidate all the messages that are no more correct: start from each of
939 // the nodes whose soft evidence has changed and perform a diffusion from
940 // the clique into which the soft evidence has been entered, indicating that
941 // the messages spreading from this clique are now invalid. At the same time,
942 // if there were tensors created on the arcs over which the messages were
943 // sent, remove them from memory. For all the cliques that received some
944 // projected factors that should now be changed, do the same.
945 NodeSet invalidated_cliques(_JT_->size());
946 for (const auto& pair: _evidence_changes_) {
947 if (auto p = _node_to_clique_.tryGet(pair.first)) {
948 const auto clique = *p;
949 invalidated_cliques.insert(clique);
950 for (const auto neighbor: _JT_->neighbours(clique)) {
951 _diffuseMessageInvalidations_(clique, neighbor, invalidated_cliques);
952 }
953 }
954 }
955
956 // now, add to the set of invalidated cliques those that contain projected
957 // factors that were changed.
958 for (const auto clique: hard_cliques_changed) {
959 invalidated_cliques.insert(clique);
960 for (const auto neighbor: _JT_->neighbours(clique)) {
961 _diffuseMessageInvalidations_(clique, neighbor, invalidated_cliques);
962 }
963 }
964
965 // now that we know the cliques whose set of tensors have been changed,
966 // we can discard their corresponding Shafer-Shenoy tensor
967 for (const auto clique: invalidated_cliques) {
968 if (ss_tensor_to_deallocate[clique]) {
969 delete _clique_ss_tensor_[clique];
970 _clique_ss_tensor_[clique] = nullptr;
971 }
972 }
973
974
975 // now we shall remove all the posteriors that belong to the
976 // invalidated cliques.
977 if (!_target_posteriors_.empty()) {
978 for (auto iter = _target_posteriors_.beginSafe(); iter != _target_posteriors_.endSafe();
979 ++iter) {
980 // first, cope only with the nodes that did not receive hard evidence
981 // since the other nodes do not belong to the join tree
982 if (_graph_.exists(iter.key())
983 && (invalidated_cliques.exists(_node_to_clique_[iter.key()]))) {
984 delete iter.val();
985 _target_posteriors_.erase(iter);
986 }
987 // now cope with the nodes that received hard evidence
988 else if (hard_nodes_changed.contains(iter.key())) {
989 delete iter.val();
990 _target_posteriors_.erase(iter);
991 }
992 }
993 }
994
995 // finally, cope with joint targets. Notably, remove the joint posteriors whose
996 // nodes have all received changed evidence
997 for (auto iter = _joint_target_posteriors_.beginSafe();
998 iter != _joint_target_posteriors_.endSafe();
999 ++iter) {
1000 // a posterior without clique (e.g. its declared target has no clique) is computed again on
1001 // demand
1002 const auto clique = _joint_target_to_clique_.tryGet(iter.key());
1003 if (!clique || invalidated_cliques.exists(*clique)) {
1004 delete iter.val();
1005 _joint_target_posteriors_.erase(iter);
1006 } else {
1007 // check for sets in which all nodes have received evidence
1008 bool has_unevidenced_node = false;
1009 for (const auto node: iter.key()) {
1010 if (!hard_nodes_changed.exists(node)) {
1011 has_unevidenced_node = true;
1012 break;
1013 }
1014 }
1015 if (!has_unevidenced_node) {
1016 delete iter.val();
1017 _joint_target_posteriors_.erase(iter);
1018 }
1019 }
1020 }
1021
1022 // remove all the evidence that were entered into _node_to_soft_evidence_
1023 // and _clique_ss_tensor_ and add the new soft ones
1024 for (const auto& pot_pair: _node_to_soft_evidence_) {
1025 delete pot_pair.second;
1026 _clique_tensors_[_node_to_clique_[pot_pair.first]].erase(pot_pair.second);
1027 }
1028 _node_to_soft_evidence_.clear();
1029
1030 const auto& evidence = this->evidence();
1031 for (const auto node: this->softEvidenceNodes()) {
1032 auto ev_pot = new ScheduleMultiDim< Tensor< GUM_SCALAR > >(*evidence[node], false);
1033 _node_to_soft_evidence_.insert(node, ev_pot);
1034 _clique_tensors_[_node_to_clique_[node]].insert(ev_pot);
1035 }
1036
1037
1038 // Now add the projections of the factors due to newly changed hard evidence:
1039 // if we are performing updateOutdatedTensors_, this means that the
1040 // set of nodes that received hard evidence has not changed, only
1041 // their instantiations can have changed. So, if there is an entry
1042 // for node in _constants_, there will still be such an entry after
1043 // performing the new projections. Idem for _hard_ev_projected_factors_
1044 if (_use_schedules_) {
1045 Schedule schedule;
1046 for (const auto pot: hard_projected_factors_changed) {
1047 _ScheduleMultiDimSet_ marg_pot_set;
1048 const auto sched_pot = schedule.insertTable< Tensor< GUM_SCALAR > >(*pot, false);
1049 marg_pot_set.insert(sched_pot);
1050 const auto& variables = pot->variablesSequence();
1051 gum::VariableSet hard_variables(variables.size());
1052 for (const auto var: variables) {
1053 NodeId xnode = mn.nodeId(*var);
1054 if (_hard_ev_nodes_.exists(xnode)) {
1055 const auto ev_pot
1056 = schedule.insertTable< Tensor< GUM_SCALAR > >(*evidence[xnode], false);
1057 marg_pot_set.insert(ev_pot);
1058 hard_variables.insert(var);
1059 }
1060 }
1061
1062 // perform the combination of those tensors and their projection
1063 MultiDimCombineAndProjectDefault< Tensor< GUM_SCALAR > > combine_and_project(
1064 _combination_op_,
1065 _projection_op_);
1066
1067 _ScheduleMultiDimSet_ new_pot_list
1068 = combine_and_project.schedule(schedule, marg_pot_set, hard_variables);
1069
1070 // there should be only one tensor in new_cpt_list
1071 if (new_pot_list.size() != 1) {
1073 "the projection of a tensor containing " << "hard evidence is empty!");
1074 }
1075 auto projected_pot = const_cast< ScheduleMultiDim< Tensor< GUM_SCALAR > >* >(
1076 static_cast< const ScheduleMultiDim< Tensor< GUM_SCALAR > >* >(*new_pot_list.begin()));
1077 const_cast< ScheduleOperator* >(schedule.scheduleMultiDimCreator(projected_pot))
1078 ->makeResultsPersistent(true);
1079 _clique_tensors_[_factor_to_clique_[pot]].insert(projected_pot);
1080 _hard_ev_projected_factors_.insert(pot, projected_pot);
1081 }
1082
1083 // here, the list of tensors stored in the invalidated cliques have
1084 // been updated. So, now, we can combine them to produce the Shafer-Shenoy
1085 // tensor stored into the clique
1086 MultiDimCombinationDefault< Tensor< GUM_SCALAR > > fast_combination(_combination_op_);
1087 for (const auto clique: invalidated_cliques) {
1088 const auto& potset = _clique_tensors_[clique];
1089
1090 if (potset.size() > 0) {
1091 // here, there will be an entry in _clique_ss_tensor_
1092 // If there is only one element in potset, this element shall be
1093 // stored into _clique_ss_tensor_, else all the elements of potset
1094 // shall be combined and their result shall be stored
1095 if (potset.size() == 1) {
1096 _clique_ss_tensor_[clique] = *(potset.cbegin());
1097 } else {
1098 for (const auto pot: potset)
1099 if (!schedule.existsScheduleMultiDim(pot->id()))
1100 schedule.emplaceScheduleMultiDim(*pot);
1101 auto joint = const_cast< ScheduleMultiDim< Tensor< GUM_SCALAR > >* >(
1102 static_cast< const ScheduleMultiDim< Tensor< GUM_SCALAR > >* >(
1103 fast_combination.schedule(schedule, potset)));
1104 const_cast< ScheduleOperator* >(schedule.scheduleMultiDimCreator(joint))
1105 ->makeResultsPersistent(true);
1106 _clique_ss_tensor_[clique] = joint;
1107 }
1108 }
1109 }
1110 this->scheduler().execute(schedule);
1111 } else {
1112 for (const auto pot: hard_projected_factors_changed) {
1113 _TensorSet_ marg_pot_set;
1114 marg_pot_set.insert(pot);
1115 const auto& variables = pot->variablesSequence();
1116
1117 gum::VariableSet hard_variables(variables.size());
1118 for (const auto var: variables) {
1119 NodeId xnode = mn.nodeId(*var);
1120 if (_hard_ev_nodes_.exists(xnode)) {
1121 marg_pot_set.insert(evidence[xnode]);
1122 hard_variables.insert(var);
1123 }
1124 }
1125
1126 // perform the combination of those tensors and their projection
1127 MultiDimCombineAndProjectDefault< Tensor< GUM_SCALAR > > combine_and_project(
1128 _combination_op_,
1129 _projection_op_);
1130
1131 _TensorSet_ new_pot_list = combine_and_project.execute(marg_pot_set, hard_variables);
1132
1133 // there should be only one tensor in new_cpt_list
1134 if (new_pot_list.size() != 1) {
1136 "the projection of a tensor containing " << "hard evidence is empty!");
1137 }
1138 Tensor< GUM_SCALAR >* xprojected_pot
1139 = const_cast< Tensor< GUM_SCALAR >* >(*new_pot_list.begin());
1140 auto projected_pot
1141 = new ScheduleMultiDim< Tensor< GUM_SCALAR > >(std::move(*xprojected_pot));
1142 delete xprojected_pot;
1143 _clique_tensors_[_factor_to_clique_[pot]].insert(projected_pot);
1144 _hard_ev_projected_factors_.insert(pot, projected_pot);
1145 }
1146
1147 // here, the list of tensors stored in the invalidated cliques have
1148 // been updated. So, now, we can combine them to produce the Shafer-Shenoy
1149 // tensor stored into the clique
1150 MultiDimCombinationDefault< Tensor< GUM_SCALAR > > fast_combination(_combination_op_);
1151 for (const auto clique: invalidated_cliques) {
1152 const auto& potset = _clique_tensors_[clique];
1153
1154 if (potset.size() > 0) {
1155 // here, there will be an entry in _clique_ss_tensor_
1156 // If there is only one element in potset, this element shall be
1157 // stored into _clique_ss_tensor_, else all the elements of potset
1158 // shall be combined and their result shall be stored
1159 if (potset.size() == 1) {
1160 _clique_ss_tensor_[clique] = *(potset.cbegin());
1161 } else {
1162 _TensorSet_ p_potset(potset.size());
1163 for (const auto pot: potset)
1164 p_potset.insert(&(
1165 static_cast< const ScheduleMultiDim< Tensor< GUM_SCALAR > >* >(pot)->multiDim()));
1166
1167 Tensor< GUM_SCALAR >* joint
1168 = const_cast< Tensor< GUM_SCALAR >* >(fast_combination.execute(p_potset));
1169 _clique_ss_tensor_[clique]
1170 = new ScheduleMultiDim< Tensor< GUM_SCALAR > >(std::move(*joint));
1171 delete joint;
1172 }
1173 }
1174 }
1175 }
1176
1177 // update the constants
1178 const auto& hard_evidence = this->hardEvidence();
1179 for (auto& node_cst: _constants_) {
1180 const Tensor< GUM_SCALAR >& pot = *(node_cst.first);
1181 Instantiation inst(pot);
1182 for (const auto var: pot.variablesSequence()) {
1183 inst.chgVal(*var, hard_evidence[mn.nodeId(*var)]);
1184 }
1185 node_cst.second = pot.get(inst);
1186 }
1187
1188 // indicate that all changes have been performed
1189 _evidence_changes_.clear();
1190 }
1191
1193 template < GUM_Numeric GUM_SCALAR >
1194 void ShaferShenoyMRFInference< GUM_SCALAR >::_computeJoinTreeRoots_() {
1195 // get the set of cliques in which we can find the targets and joint_targets.
1196 // Due to hard evidence, the cliques related to a given target node
1197 // might not exist, hence the if checks
1198 NodeSet clique_targets;
1199 for (const auto node: this->targets()) {
1200 if (auto p = _node_to_clique_.tryGet(node)) { clique_targets.insert(*p); }
1201 }
1202 for (const auto& set: this->jointTargets()) {
1203 if (auto p = _joint_target_to_clique_.tryGet(set)) { clique_targets.insert(*p); }
1204 }
1205
1206 // one root per connected component (every component needs one: its mass is required by
1207 // evidenceProbability), the cliques containing targets being preferred
1208 _roots_ = junctionTreeRoots(*_JT_, this->MRF(), clique_targets);
1209 }
1210
1211 // performs the collect phase of Shafer-Shenoy using schedules
1212 template < GUM_Numeric GUM_SCALAR >
1213 void ShaferShenoyMRFInference< GUM_SCALAR >::_collectMessage_(Schedule& schedule,
1214 NodeId id,
1215 NodeId from) {
1216 for (const auto other: _JT_->neighbours(id)) {
1217 if ((other != from) && !_messages_computed_[Arc(other, id)])
1218 _collectMessage_(schedule, other, id);
1219 }
1220
1221 if ((id != from) && !_messages_computed_[Arc(id, from)]) {
1222 _produceMessage_(schedule, id, from);
1223 }
1224 }
1225
1226 // performs the collect phase of Shafer-Shenoy without schedules
1227 template < GUM_Numeric GUM_SCALAR >
1228 void ShaferShenoyMRFInference< GUM_SCALAR >::_collectMessage_(NodeId id, NodeId from) {
1229 for (const auto other: _JT_->neighbours(id)) {
1230 if ((other != from) && !_messages_computed_[Arc(other, id)]) _collectMessage_(other, id);
1231 }
1232
1233 if ((id != from) && !_messages_computed_[Arc(id, from)]) { _produceMessage_(id, from); }
1234 }
1235
1236 // remove variables del_vars from the list of tensors pot_list
1237 template < GUM_Numeric GUM_SCALAR >
1238 const IScheduleMultiDim* ShaferShenoyMRFInference< GUM_SCALAR >::_marginalizeOut_(
1239 Schedule& schedule,
1240 Set< const IScheduleMultiDim* > pot_list,
1241 gum::VariableSet& del_vars,
1242 gum::VariableSet& kept_vars) {
1243 // let's guarantee that all the tensors to be combined and projected
1244 // belong to the schedule
1245 for (const auto pot: pot_list) {
1246 if (!schedule.existsScheduleMultiDim(pot->id())) schedule.emplaceScheduleMultiDim(*pot);
1247 }
1248
1249 // create a combine and project operator that will perform the
1250 // marginalization
1251 MultiDimCombineAndProjectDefault< Tensor< GUM_SCALAR > > combine_and_project(_combination_op_,
1252 _projection_op_);
1253 _ScheduleMultiDimSet_ new_pot_list = combine_and_project.schedule(schedule, pot_list, del_vars);
1254
1255 // combine all the remaining tensors in order to create only one resulting tensor
1256 if (new_pot_list.size() == 1) return *(new_pot_list.begin());
1257 MultiDimCombinationDefault< Tensor< GUM_SCALAR > > fast_combination(_combination_op_);
1258 return fast_combination.schedule(schedule, new_pot_list);
1259 }
1260
1261 // remove variables del_vars from the list of tensors pot_list
1262 template < GUM_Numeric GUM_SCALAR >
1263 const IScheduleMultiDim* ShaferShenoyMRFInference< GUM_SCALAR >::_marginalizeOut_(
1264 Set< const IScheduleMultiDim* >& pot_list,
1265 gum::VariableSet& del_vars,
1266 gum::VariableSet& kept_vars) {
1267 _TensorSet_ xpot_list(pot_list.size());
1268 for (auto pot: pot_list)
1269 xpot_list.insert(
1270 &(static_cast< const ScheduleMultiDim< Tensor< GUM_SCALAR > >* >(pot)->multiDim()));
1271
1272 // create a combine and project operator that will perform the
1273 // marginalization
1274 MultiDimCombineAndProjectDefault< Tensor< GUM_SCALAR > > combine_and_project(_combination_op_,
1275 _projection_op_);
1276 _TensorSet_ xnew_pot_list = combine_and_project.execute(xpot_list, del_vars);
1277
1278 // combine all the remaining tensors in order to create only one resulting tensor
1279 const Tensor< GUM_SCALAR >* xres_pot;
1280 if (xnew_pot_list.size() == 1) {
1281 xres_pot = *(xnew_pot_list.begin());
1282 } else {
1283 // combine all the tensors that resulted from the above combine and
1284 // projet execution
1285 MultiDimCombinationDefault< Tensor< GUM_SCALAR > > fast_combination(_combination_op_);
1286 xres_pot = fast_combination.execute(xnew_pot_list);
1287 for (const auto pot: xnew_pot_list) {
1288 if (!xpot_list.contains(pot) && (pot != xres_pot)) delete pot;
1289 }
1290 }
1291
1292 // transform xres_pot into a ScheduleMultiDim
1293 ScheduleMultiDim< Tensor< GUM_SCALAR > >* res_pot;
1294 if (xpot_list.contains(xres_pot))
1295 res_pot = new ScheduleMultiDim< Tensor< GUM_SCALAR > >(*xres_pot, false);
1296 else {
1297 res_pot = new ScheduleMultiDim< Tensor< GUM_SCALAR > >(
1298 std::move(const_cast< Tensor< GUM_SCALAR >& >(*xres_pot)));
1299 delete xres_pot;
1300 }
1301
1302 return res_pot;
1303 }
1304
1305 // creates the message sent by clique from_id to clique to_id
1306 template < GUM_Numeric GUM_SCALAR >
1307 void ShaferShenoyMRFInference< GUM_SCALAR >::_produceMessage_(Schedule& schedule,
1308 NodeId from_id,
1309 NodeId to_id) {
1310 // get the tensors of the clique.
1311 _ScheduleMultiDimSet_ pot_list;
1312 if (_clique_ss_tensor_[from_id] != nullptr) pot_list.insert(_clique_ss_tensor_[from_id]);
1313
1314 // add the messages sent by adjacent nodes to from_id.
1315 for (const auto other_id: _JT_->neighbours(from_id)) {
1316 if (other_id != to_id) {
1317 const auto separator_pot = _separator_tensors_[Arc(other_id, from_id)];
1318 if (separator_pot != nullptr) pot_list.insert(separator_pot);
1319 }
1320 }
1321
1322 // get the set of variables that need be removed from the tensors
1323 const NodeSet& from_clique = _JT_->clique(from_id);
1324 const NodeSet& separator = _JT_->separator(from_id, to_id);
1325 gum::VariableSet del_vars(from_clique.size());
1326 gum::VariableSet kept_vars(separator.size());
1327 const auto& mn = this->MRF();
1328
1329 for (const auto node: from_clique) {
1330 if (!separator.contains(node)) {
1331 del_vars.insert(&(mn.variable(node)));
1332 } else {
1333 kept_vars.insert(&(mn.variable(node)));
1334 }
1335 }
1336
1337 // pot_list now contains all the tensors to multiply and marginalize
1338 // => combine the messages
1339 const IScheduleMultiDim* new_pot = _marginalizeOut_(schedule, pot_list, del_vars, kept_vars);
1340
1341 // keep track of the newly created tensor
1342 const Arc arc(from_id, to_id);
1343 if (!pot_list.exists(new_pot)) {
1344 if (!_arc_to_created_tensors_.exists(arc)) {
1345 _arc_to_created_tensors_.insert(arc, new_pot);
1346
1347 // do not forget to make the ScheduleMultiDim persistent
1348 auto op = schedule.scheduleMultiDimCreator(new_pot);
1349 if (op != nullptr) const_cast< ScheduleOperator* >(op)->makeResultsPersistent(true);
1350 }
1351 }
1352
1353 _separator_tensors_[arc] = new_pot;
1354 _messages_computed_[arc] = true;
1355 }
1356
1357 // creates the message sent by clique from_id to clique to_id
1358 template < GUM_Numeric GUM_SCALAR >
1359 void ShaferShenoyMRFInference< GUM_SCALAR >::_produceMessage_(NodeId from_id, NodeId to_id) {
1360 // get the tensors of the clique.
1361 _ScheduleMultiDimSet_ pot_list;
1362 if (_clique_ss_tensor_[from_id] != nullptr) pot_list.insert(_clique_ss_tensor_[from_id]);
1363
1364 // add the messages sent by adjacent nodes to from_id.
1365 for (const auto other_id: _JT_->neighbours(from_id)) {
1366 if (other_id != to_id) {
1367 const auto separator_pot = _separator_tensors_[Arc(other_id, from_id)];
1368 if (separator_pot != nullptr) pot_list.insert(separator_pot);
1369 }
1370 }
1371
1372 // get the set of variables that need be removed from the tensors
1373 const NodeSet& from_clique = _JT_->clique(from_id);
1374 const NodeSet& separator = _JT_->separator(from_id, to_id);
1375 gum::VariableSet del_vars(from_clique.size());
1376 gum::VariableSet kept_vars(separator.size());
1377 const auto& mn = this->MRF();
1378
1379 for (const auto node: from_clique) {
1380 if (!separator.contains(node)) {
1381 del_vars.insert(&(mn.variable(node)));
1382 } else {
1383 kept_vars.insert(&(mn.variable(node)));
1384 }
1385 }
1386
1387 // pot_list now contains all the tensors to multiply and marginalize
1388 // => combine the messages
1389 const IScheduleMultiDim* new_pot = _marginalizeOut_(pot_list, del_vars, kept_vars);
1390
1391 // keep track of the newly created tensor
1392 const Arc arc(from_id, to_id);
1393 if (!pot_list.exists(new_pot)) {
1394 if (!_arc_to_created_tensors_.exists(arc)) { _arc_to_created_tensors_.insert(arc, new_pot); }
1395 }
1396
1397 _separator_tensors_[arc] = new_pot;
1398 _messages_computed_[arc] = true;
1399 }
1400
1401 // fired after a new Markov net has been assigned to the inference engine
1402 template < GUM_Numeric GUM_SCALAR >
1403 void ShaferShenoyMRFInference< GUM_SCALAR >::onModelChanged_(const GraphicalModel* mn) {
1404 JointTargetedMRFInference< GUM_SCALAR >::onModelChanged_(mn);
1405 _partition_function_.reset();
1406 }
1407
1408 // performs a whole inference
1409 template < GUM_Numeric GUM_SCALAR >
1410 void ShaferShenoyMRFInference< GUM_SCALAR >::makeInference_() {
1411 if (_use_schedules_) {
1412 Schedule schedule;
1413
1414 // collect messages for all single targets
1415 for (const auto node: this->targets()) {
1416 // perform only collects in the join tree for nodes that have
1417 // not received hard evidence (those that received hard evidence were
1418 // not included into the join tree for speed-up reasons)
1419 if (_graph_.exists(node)) {
1420 _collectMessage_(schedule, _node_to_clique_[node], _node_to_clique_[node]);
1421 }
1422 }
1423
1424 // collect messages for all set targets
1425 // by parsing _joint_target_to_clique_, we ensure that the cliques that
1426 // are referenced belong to the join tree (even if some of the nodes in
1427 // their associated joint_target do not belong to _graph_)
1428 for (const auto& set: _joint_target_to_clique_)
1429 _collectMessage_(schedule, set.second, set.second);
1430
1431 // really perform the computations
1432 this->scheduler().execute(schedule);
1433 } else {
1434 // collect messages for all single targets
1435 for (const auto node: this->targets()) {
1436 // perform only collects in the join tree for nodes that have
1437 // not received hard evidence (those that received hard evidence were
1438 // not included into the join tree for speed-up reasons)
1439 if (_graph_.exists(node)) {
1440 _collectMessage_(_node_to_clique_[node], _node_to_clique_[node]);
1441 }
1442 }
1443
1444 // collect messages for all set targets
1445 // by parsing _joint_target_to_clique_, we ensure that the cliques that
1446 // are referenced belong to the join tree (even if some of the nodes in
1447 // their associated joint_target do not belong to _graph_)
1448 for (const auto& set: _joint_target_to_clique_)
1449 _collectMessage_(set.second, set.second);
1450 }
1451 }
1452
1454 template < GUM_Numeric GUM_SCALAR >
1455 Tensor< GUM_SCALAR >*
1456 ShaferShenoyMRFInference< GUM_SCALAR >::unnormalizedJointPosterior_(NodeId id) {
1457 if (_use_schedules_) {
1458 Schedule schedule;
1459 return _unnormalizedJointPosterior_(schedule, id);
1460 } else {
1461 return _unnormalizedJointPosterior_(id);
1462 }
1463 }
1464
1466 template < GUM_Numeric GUM_SCALAR >
1467 Tensor< GUM_SCALAR >*
1468 ShaferShenoyMRFInference< GUM_SCALAR >::_unnormalizedJointPosterior_(Schedule& schedule,
1469 NodeId id) {
1470 const auto& mn = this->MRF();
1471
1472 // hard evidence do not belong to the join tree
1473 // # TODO: check for sets of inconsistent hard evidence
1474 if (this->hardEvidenceNodes().contains(id)) {
1475 return new Tensor< GUM_SCALAR >(*(this->evidence()[id]));
1476 }
1477
1478 auto& scheduler = this->scheduler();
1479
1480 // if we still need to perform some inference task, do it (this should
1481 // already have been done by makeInference_)
1482 const NodeId clique_of_id = _node_to_clique_[id];
1483 _collectMessage_(schedule, clique_of_id, clique_of_id);
1484
1485 // now we just need to create the product of the tensors of the clique
1486 // containing id with the messages received by this clique and
1487 // marginalize out all variables except id
1488 _ScheduleMultiDimSet_ pot_list;
1489 if (_clique_ss_tensor_[clique_of_id] != nullptr)
1490 pot_list.insert(_clique_ss_tensor_[clique_of_id]);
1491
1492 // add the messages sent by adjacent nodes to targetClique
1493 for (const auto other: _JT_->neighbours(clique_of_id))
1494 pot_list.insert(_separator_tensors_[Arc(other, clique_of_id)]);
1495
1496 // get the set of variables that need be removed from the tensors
1497 const NodeSet& nodes = _JT_->clique(clique_of_id);
1498 gum::VariableSet kept_vars{&(mn.variable(id))};
1499 gum::VariableSet del_vars(nodes.size());
1500 for (const auto node: nodes) {
1501 if (node != id) del_vars.insert(&(mn.variable(node)));
1502 }
1503
1504 // pot_list now contains all the tensors to multiply and marginalize
1505 // => combine the messages
1506 auto resulting_pot = const_cast< ScheduleMultiDim< Tensor< GUM_SCALAR > >* >(
1507 static_cast< const ScheduleMultiDim< Tensor< GUM_SCALAR > >* >(
1508 _marginalizeOut_(schedule, pot_list, del_vars, kept_vars)));
1509 Tensor< GUM_SCALAR >* joint = nullptr;
1510
1511 scheduler.execute(schedule);
1512
1513 // if pot already existed, create a copy, so that we can put it into
1514 // the _target_posteriors_ property
1515 if (pot_list.exists(resulting_pot)) {
1516 joint = new Tensor< GUM_SCALAR >(resulting_pot->multiDim());
1517 } else {
1518 joint = resulting_pot->exportMultiDim();
1519 }
1520
1521 // check that the joint posterior is different from a 0 vector: this would
1522 // indicate that some hard evidence are not compatible (their joint
1523 // probability is equal to 0)
1524 bool nonzero_found = false;
1525 for (Instantiation inst(*joint); !inst.end(); ++inst) {
1526 if (joint->get(inst)) {
1527 nonzero_found = true;
1528 break;
1529 }
1530 }
1531 if (!nonzero_found) {
1532 // remove joint from memory to avoid memory leaks
1533 delete joint;
1535 "some evidence entered into the Markov "
1536 "net are incompatible (their joint proba = 0)");
1537 }
1538 return joint;
1539 }
1540
1542 template < GUM_Numeric GUM_SCALAR >
1543 Tensor< GUM_SCALAR >*
1544 ShaferShenoyMRFInference< GUM_SCALAR >::_unnormalizedJointPosterior_(NodeId id) {
1545 const auto& mn = this->MRF();
1546
1547 // hard evidence do not belong to the join tree
1548 // # TODO: check for sets of inconsistent hard evidence
1549 if (this->hardEvidenceNodes().contains(id)) {
1550 return new Tensor< GUM_SCALAR >(*(this->evidence()[id]));
1551 }
1552
1553 // if we still need to perform some inference task, do it (this should
1554 // already have been done by makeInference_)
1555 NodeId clique_of_id = _node_to_clique_[id];
1556 _collectMessage_(clique_of_id, clique_of_id);
1557
1558 // now we just need to create the product of the tensors of the clique
1559 // containing id with the messages received by this clique and
1560 // marginalize out all variables except id
1561 _ScheduleMultiDimSet_ pot_list;
1562 if (_clique_ss_tensor_[clique_of_id] != nullptr)
1563 pot_list.insert(_clique_ss_tensor_[clique_of_id]);
1564
1565 // add the messages sent by adjacent nodes to targetClique
1566 for (const auto other: _JT_->neighbours(clique_of_id))
1567 pot_list.insert(_separator_tensors_[Arc(other, clique_of_id)]);
1568
1569 // get the set of variables that need be removed from the tensors
1570 const NodeSet& nodes = _JT_->clique(clique_of_id);
1571 gum::VariableSet kept_vars{&(mn.variable(id))};
1572 gum::VariableSet del_vars(nodes.size());
1573 for (const auto node: nodes) {
1574 if (node != id) del_vars.insert(&(mn.variable(node)));
1575 }
1576
1577 // pot_list now contains all the tensors to multiply and marginalize
1578 // => combine the messages
1579 auto resulting_pot = const_cast< ScheduleMultiDim< Tensor< GUM_SCALAR > >* >(
1580 static_cast< const ScheduleMultiDim< Tensor< GUM_SCALAR > >* >(
1581 _marginalizeOut_(pot_list, del_vars, kept_vars)));
1582 Tensor< GUM_SCALAR >* joint = nullptr;
1583
1584 // if pot already existed, create a copy, so that we can put it into
1585 // the _target_posteriors_ property
1586 if (pot_list.exists(resulting_pot)) {
1587 joint = new Tensor< GUM_SCALAR >(resulting_pot->multiDim());
1588 } else {
1589 joint = resulting_pot->exportMultiDim();
1590 delete resulting_pot;
1591 }
1592
1593 // check that the joint posterior is different from a 0 vector: this would
1594 // indicate that some hard evidence are not compatible (their joint
1595 // probability is equal to 0)
1596 bool nonzero_found = false;
1597 for (Instantiation inst(*joint); !inst.end(); ++inst) {
1598 if (joint->get(inst)) {
1599 nonzero_found = true;
1600 break;
1601 }
1602 }
1603 if (!nonzero_found) {
1604 // remove joint from memory to avoid memory leaks
1605 delete joint;
1607 "some evidence entered into the Markov "
1608 "net are incompatible (their joint proba = 0)");
1609 }
1610 return joint;
1611 }
1612
1614 template < GUM_Numeric GUM_SCALAR >
1615 const Tensor< GUM_SCALAR >& ShaferShenoyMRFInference< GUM_SCALAR >::posterior_(NodeId id) {
1616 // check if we have already computed the posterior
1617 if (auto p = _target_posteriors_.tryGet(id)) { return *(*p); }
1618
1619 // compute the joint posterior and normalize
1620 auto joint = unnormalizedJointPosterior_(id);
1621 if (joint->sum() != 1) // hard test for ReadOnly CPT (as aggregator)
1622 joint->normalize();
1623 _target_posteriors_.insert(id, joint);
1624
1625 return *joint;
1626 }
1627
1629 template < GUM_Numeric GUM_SCALAR >
1630 Tensor< GUM_SCALAR >*
1631 ShaferShenoyMRFInference< GUM_SCALAR >::unnormalizedJointPosterior_(const NodeSet& set) {
1632 if (_use_schedules_) {
1633 Schedule schedule;
1634 return _unnormalizedJointPosterior_(schedule, set);
1635 } else {
1636 return _unnormalizedJointPosterior_(set);
1637 }
1638 }
1639
1641 template < GUM_Numeric GUM_SCALAR >
1642 Tensor< GUM_SCALAR >*
1643 ShaferShenoyMRFInference< GUM_SCALAR >::_unnormalizedJointPosterior_(Schedule& schedule,
1644 const NodeSet& set) {
1645 // hard evidence do not belong to the join tree, so extract the nodes
1646 // from targets that are not hard evidence
1647 NodeSet targets = set, hard_ev_nodes;
1648 for (const auto node: this->hardEvidenceNodes()) {
1649 if (targets.contains(node)) {
1650 targets.erase(node);
1651 hard_ev_nodes.insert(node);
1652 }
1653 }
1654
1655 auto& scheduler = this->scheduler();
1656
1657 // if all the nodes have received hard evidence, then compute the
1658 // joint posterior directly by multiplying the hard evidence tensors
1659 const auto& evidence = this->evidence();
1660 if (targets.empty()) {
1661 if (set.size() == 1) {
1662 return new Tensor< GUM_SCALAR >(*evidence[*set.begin()]);
1663 } else {
1664 _ScheduleMultiDimSet_ pot_list;
1665 for (const auto node: set) {
1666 auto new_pot_ev = schedule.insertTable< Tensor< GUM_SCALAR > >(*evidence[node], false);
1667 pot_list.insert(new_pot_ev);
1668 }
1669
1670 // combine all the tensors of the nodes in set
1671 MultiDimCombinationDefault< Tensor< GUM_SCALAR > > fast_combination(_combination_op_);
1672 const IScheduleMultiDim* pot = fast_combination.schedule(schedule, pot_list);
1673 auto schedule_pot = const_cast< ScheduleMultiDim< Tensor< GUM_SCALAR > >* >(
1674 static_cast< const ScheduleMultiDim< Tensor< GUM_SCALAR > >* >(pot));
1675 scheduler.execute(schedule);
1676 auto result = schedule_pot->exportMultiDim();
1677
1678 return result;
1679 }
1680 }
1681
1682
1683 // if we still need to perform some inference task, do it: so, first,
1684 // determine the clique on which we should perform collect to compute
1685 // the unnormalized joint posterior of a set of nodes containing "targets"
1686 NodeId clique_of_set;
1687 if (auto p_clique = _joint_target_to_clique_.tryGet(set)) {
1688 clique_of_set = *p_clique;
1689 } else {
1690 // here, the precise set of targets does not belong to the set of targets
1691 // defined by the user. So we will try to find a clique in the junction
1692 // tree that contains "targets":
1693
1694 // 1/ we should check that all the nodes belong to the join tree
1695 for (const auto node: targets) {
1696 if (!_graph_.exists(node)) {
1698 "The variable " << this->MRF().variable(node).name() << "(" << node
1699 << ") does not belong to this optimized inference.")
1700 }
1701 }
1702
1703 // 2/ the clique created by the first eliminated node among target is the
1704 // one we are looking for
1705 const std::vector< NodeId >& JT_elim_order = _triangulation_->eliminationOrder();
1706 NodeProperty< int > elim_order(Size(JT_elim_order.size()));
1707 for (std::size_t i = std::size_t(0), size = JT_elim_order.size(); i < size; ++i)
1708 elim_order.insert(JT_elim_order[i], (int)i);
1709 NodeId first_eliminated_node = *(targets.begin());
1710 int elim_number = elim_order[first_eliminated_node];
1711 for (const auto node: targets) {
1712 if (elim_order[node] < elim_number) {
1713 elim_number = elim_order[node];
1714 first_eliminated_node = node;
1715 }
1716 }
1717
1718 clique_of_set = _triangulation_->createdJunctionTreeClique(first_eliminated_node);
1719
1720
1721 // 3/ check that clique_of_set contains the all the nodes in the target
1722 const NodeSet& clique_nodes = _JT_->clique(clique_of_set);
1723 for (const auto node: targets) {
1724 if (!clique_nodes.contains(node)) {
1726 this->MRF().names(set) << "(" << set << ")"
1727 << " is not addressable in this optimized inference.")
1728 }
1729 }
1730
1731 // add the discovered clique to _joint_target_to_clique_
1732 _joint_target_to_clique_.insert(set, clique_of_set);
1733 }
1734
1735 // now perform a collect on the clique
1736 _collectMessage_(schedule, clique_of_set, clique_of_set);
1737
1738 // now we just need to create the product of the tensors of the clique
1739 // containing set with the messages received by this clique and
1740 // marginalize out all variables except set
1741 _ScheduleMultiDimSet_ pot_list;
1742 if (_clique_ss_tensor_[clique_of_set] != nullptr) {
1743 auto pot = _clique_ss_tensor_[clique_of_set];
1744 if (!schedule.existsScheduleMultiDim(pot->id())) schedule.emplaceScheduleMultiDim(*pot);
1745 pot_list.insert(_clique_ss_tensor_[clique_of_set]);
1746 }
1747
1748 // add the messages sent by adjacent nodes to targetClique
1749 for (const auto other: _JT_->neighbours(clique_of_set)) {
1750 const auto pot = _separator_tensors_[Arc(other, clique_of_set)];
1751 if (pot != nullptr) pot_list.insert(pot);
1752 }
1753
1754
1755 // get the set of variables that need be removed from the tensors
1756 const NodeSet& nodes = _JT_->clique(clique_of_set);
1757 gum::VariableSet del_vars(nodes.size());
1758 gum::VariableSet kept_vars(targets.size());
1759 const auto& mn = this->MRF();
1760 for (const auto node: nodes) {
1761 if (!targets.contains(node)) {
1762 del_vars.insert(&(mn.variable(node)));
1763 } else {
1764 kept_vars.insert(&(mn.variable(node)));
1765 }
1766 }
1767
1768 // pot_list now contains all the tensors to multiply and marginalize
1769 // => combine the messages
1770 const IScheduleMultiDim* new_pot = _marginalizeOut_(schedule, pot_list, del_vars, kept_vars);
1771 scheduler.execute(schedule);
1772 ScheduleMultiDim< Tensor< GUM_SCALAR > >* resulting_pot
1773 = const_cast< ScheduleMultiDim< Tensor< GUM_SCALAR > >* >(
1774 static_cast< const ScheduleMultiDim< Tensor< GUM_SCALAR > >* >(new_pot));
1775
1776 // if pot already existed, create a copy, so that we can put it into
1777 // the _target_posteriors_ property
1778 Tensor< GUM_SCALAR >* joint = nullptr;
1779 if (pot_list.exists(resulting_pot)) {
1780 joint = new Tensor< GUM_SCALAR >(resulting_pot->multiDim());
1781 } else {
1782 joint = resulting_pot->exportMultiDim();
1783 }
1784
1785 // check that the joint posterior is different from a 0 vector: this would
1786 // indicate that some hard evidence are not compatible
1787 bool nonzero_found = false;
1788 for (Instantiation inst(*joint); !inst.end(); ++inst) {
1789 if ((*joint)[inst]) {
1790 nonzero_found = true;
1791 break;
1792 }
1793 }
1794 if (!nonzero_found) {
1795 // remove joint from memory to avoid memory leaks
1796 delete joint;
1798 "some evidence entered into the Markov "
1799 "net are incompatible (their joint proba = 0)");
1800 }
1801
1802 return joint;
1803 }
1804
1806 template < GUM_Numeric GUM_SCALAR >
1807 Tensor< GUM_SCALAR >*
1808 ShaferShenoyMRFInference< GUM_SCALAR >::_unnormalizedJointPosterior_(const NodeSet& set) {
1809 // hard evidence do not belong to the join tree, so extract the nodes
1810 // from targets that are not hard evidence
1811 NodeSet targets = set, hard_ev_nodes;
1812 for (const auto node: this->hardEvidenceNodes()) {
1813 if (targets.contains(node)) {
1814 targets.erase(node);
1815 hard_ev_nodes.insert(node);
1816 }
1817 }
1818
1819 // if all the nodes have received hard evidence, then compute the
1820 // joint posterior directly by multiplying the hard evidence tensors
1821 const auto& evidence = this->evidence();
1822 if (targets.empty()) {
1823 if (set.size() == 1) {
1824 return new Tensor< GUM_SCALAR >(*evidence[*set.begin()]);
1825 } else {
1826 _TensorSet_ pot_list;
1827 for (const auto node: set) {
1828 pot_list.insert(evidence[node]);
1829 }
1830
1831 // combine all the tensors of the nodes in set
1832 MultiDimCombinationDefault< Tensor< GUM_SCALAR > > fast_combination(_combination_op_);
1833 const Tensor< GUM_SCALAR >* pot = fast_combination.execute(pot_list);
1834
1835 return const_cast< Tensor< GUM_SCALAR >* >(pot);
1836 }
1837 }
1838
1839
1840 // if we still need to perform some inference task, do it: so, first,
1841 // determine the clique on which we should perform collect to compute
1842 // the unnormalized joint posterior of a set of nodes containing "targets"
1843 NodeId clique_of_set;
1844 if (auto p_clique = _joint_target_to_clique_.tryGet(set)) {
1845 clique_of_set = *p_clique;
1846 } else {
1847 // here, the precise set of targets does not belong to the set of targets
1848 // defined by the user. So we will try to find a clique in the junction
1849 // tree that contains "targets":
1850
1851 // 1/ we should check that all the nodes belong to the join tree
1852 for (const auto node: targets) {
1853 if (!_graph_.exists(node)) {
1855 "The variable " << this->MRF().variable(node).name() << "(" << node
1856 << ") does not belong to this optimized inference.")
1857 }
1858 }
1859
1860 // 2/ the clique created by the first eliminated node among target is the
1861 // one we are looking for
1862 const std::vector< NodeId >& JT_elim_order = _triangulation_->eliminationOrder();
1863 NodeProperty< int > elim_order(Size(JT_elim_order.size()));
1864 for (std::size_t i = std::size_t(0), size = JT_elim_order.size(); i < size; ++i)
1865 elim_order.insert(JT_elim_order[i], (int)i);
1866 NodeId first_eliminated_node = *(targets.begin());
1867 int elim_number = elim_order[first_eliminated_node];
1868 for (const auto node: targets) {
1869 if (elim_order[node] < elim_number) {
1870 elim_number = elim_order[node];
1871 first_eliminated_node = node;
1872 }
1873 }
1874
1875 clique_of_set = _triangulation_->createdJunctionTreeClique(first_eliminated_node);
1876
1877
1878 // 3/ check that clique_of_set contains the all the nodes in the target
1879 const NodeSet& clique_nodes = _JT_->clique(clique_of_set);
1880 for (const auto node: targets) {
1881 if (!clique_nodes.contains(node)) {
1882 GUM_ERROR(UndefinedElement, set << " is not a joint target")
1883 }
1884 }
1885
1886 // add the discovered clique to _joint_target_to_clique_
1887 _joint_target_to_clique_.insert(set, clique_of_set);
1888 }
1889
1890 // now perform a collect on the clique
1891 _collectMessage_(clique_of_set, clique_of_set);
1892
1893 // now we just need to create the product of the tensors of the clique
1894 // containing set with the messages received by this clique and
1895 // marginalize out all variables except set
1896 _ScheduleMultiDimSet_ pot_list;
1897 if (_clique_ss_tensor_[clique_of_set] != nullptr) {
1898 auto pot = _clique_ss_tensor_[clique_of_set];
1899 if (pot != nullptr) pot_list.insert(_clique_ss_tensor_[clique_of_set]);
1900 }
1901
1902 // add the messages sent by adjacent nodes to targetClique
1903 for (const auto other: _JT_->neighbours(clique_of_set)) {
1904 const auto pot = _separator_tensors_[Arc(other, clique_of_set)];
1905 if (pot != nullptr) pot_list.insert(pot);
1906 }
1907
1908
1909 // get the set of variables that need be removed from the tensors
1910 const NodeSet& nodes = _JT_->clique(clique_of_set);
1911 gum::VariableSet del_vars(nodes.size());
1912 gum::VariableSet kept_vars(targets.size());
1913 const auto& mn = this->MRF();
1914 for (const auto node: nodes) {
1915 if (!targets.contains(node)) {
1916 del_vars.insert(&(mn.variable(node)));
1917 } else {
1918 kept_vars.insert(&(mn.variable(node)));
1919 }
1920 }
1921
1922 // pot_list now contains all the tensors to multiply and marginalize
1923 // => combine the messages
1924 const IScheduleMultiDim* new_pot = _marginalizeOut_(pot_list, del_vars, kept_vars);
1925 ScheduleMultiDim< Tensor< GUM_SCALAR > >* resulting_pot
1926 = const_cast< ScheduleMultiDim< Tensor< GUM_SCALAR > >* >(
1927 static_cast< const ScheduleMultiDim< Tensor< GUM_SCALAR > >* >(new_pot));
1928
1929 // if pot already existed, create a copy, so that we can put it into
1930 // the _target_posteriors_ property
1931 Tensor< GUM_SCALAR >* joint = nullptr;
1932 if (pot_list.exists(resulting_pot)) {
1933 joint = new Tensor< GUM_SCALAR >(resulting_pot->multiDim());
1934 } else {
1935 joint = resulting_pot->exportMultiDim();
1936 delete new_pot;
1937 }
1938
1939 // check that the joint posterior is different from a 0 vector: this would
1940 // indicate that some hard evidence are not compatible
1941 bool nonzero_found = false;
1942 for (Instantiation inst(*joint); !inst.end(); ++inst) {
1943 if ((*joint)[inst]) {
1944 nonzero_found = true;
1945 break;
1946 }
1947 }
1948 if (!nonzero_found) {
1949 // remove joint from memory to avoid memory leaks
1950 delete joint;
1952 "some evidence entered into the Markov "
1953 "net are incompatible (their joint proba = 0)");
1954 }
1955
1956 return joint;
1957 }
1958
1960 template < GUM_Numeric GUM_SCALAR >
1961 const Tensor< GUM_SCALAR >&
1962 ShaferShenoyMRFInference< GUM_SCALAR >::jointPosterior_(const NodeSet& set) {
1963 // check if we have already computed the posterior
1964 if (auto p = _joint_target_posteriors_.tryGet(set)) { return *(*p); }
1965
1966 // compute the joint posterior and normalize
1967 auto joint = unnormalizedJointPosterior_(set);
1968 joint->normalize();
1969 _joint_target_posteriors_.insert(set, joint);
1970
1971 return *joint;
1972 }
1973
1975 template < GUM_Numeric GUM_SCALAR >
1976 const Tensor< GUM_SCALAR >&
1977 ShaferShenoyMRFInference< GUM_SCALAR >::jointPosterior_(const NodeSet& wanted_target,
1978 const NodeSet& declared_target) {
1979 // check if we have already computed the posterior of wanted_target
1980 if (auto p = _joint_target_posteriors_.tryGet(wanted_target)) return *(*p);
1981
1982 // here, we will have to compute the posterior of declared_target and
1983 // marginalize out all the variables that do not belong to wanted_target
1984
1985 // check if we have already computed the posterior of declared_target
1986 if (!_joint_target_posteriors_.exists(declared_target)) { jointPosterior_(declared_target); }
1987
1988 // marginalize out all the variables that do not belong to wanted_target
1989 const auto& mn = this->MRF();
1990 gum::VariableSet del_vars;
1991 for (const auto node: declared_target)
1992 if (!wanted_target.contains(node)) del_vars.insert(&(mn.variable(node)));
1993 auto pot
1994 = new Tensor< GUM_SCALAR >(_joint_target_posteriors_[declared_target]->sumOut(del_vars));
1995
1996 // save the result into the cache. wanted_target is a subset of declared_target: it belongs to
1997 // the same clique, which tells when the cached posterior is outdated
1998 _joint_target_posteriors_.insert(wanted_target, pot);
1999 if (auto clique = _joint_target_to_clique_.tryGet(declared_target)) {
2000 const NodeId clique_id = *clique; // copied: the insertion may resize the table
2001 if (!_joint_target_to_clique_.exists(wanted_target))
2002 _joint_target_to_clique_.insert(wanted_target, clique_id);
2003 }
2004
2005 return *pot;
2006 }
2007
2008 template < GUM_Numeric GUM_SCALAR >
2009 GUM_SCALAR ShaferShenoyMRFInference< GUM_SCALAR >::evidenceProbability() {
2010 // P(e) = Z(e) / Z where Z is the partition function, i.e., the mass without evidence
2011 if (!this->hasEvidence()) return GUM_SCALAR(1);
2012
2013 // Z depends neither on the evidence nor on the targets
2014 if (!_partition_function_) {
2015 ShaferShenoyMRFInference< GUM_SCALAR > no_evidence(&this->MRF());
2016 _partition_function_ = no_evidence._evidenceMass_();
2017 }
2018 return _evidenceMass_() / *_partition_function_;
2019 }
2020
2021 template < GUM_Numeric GUM_SCALAR >
2022 GUM_SCALAR ShaferShenoyMRFInference< GUM_SCALAR >::_evidenceMass_() {
2023 // perform inference in each connected component
2024 this->makeInference();
2025
2026 // for each connected component, select a variable X and compute the
2027 // joint probability of X and evidence e. Then marginalize-out X to get
2028 // p(e) in this connected component. Finally, multiply all the p(e) that
2029 // we got and the elements in _constants_. The result is the probability
2030 // of evidence
2031
2032 GUM_SCALAR prob_ev = 1;
2033 for (const auto root: _roots_) {
2034 // get a node in the clique
2035 NodeId node = *(_JT_->clique(root).begin());
2036 Tensor< GUM_SCALAR >* tmp = unnormalizedJointPosterior_(node);
2037 prob_ev *= tmp->sum();
2038 delete tmp;
2039 }
2040
2041 for (const auto& projected_cpt: _constants_)
2042 prob_ev *= projected_cpt.second;
2043
2044 return prob_ev;
2045 }
2046
2047 template < GUM_Numeric GUM_SCALAR >
2048 bool ShaferShenoyMRFInference< GUM_SCALAR >::isExactJointComputable_(const NodeSet& vars) {
2049 if (JointTargetedMRFInference< GUM_SCALAR >::isExactJointComputable_(vars)) return true;
2050
2051 this->prepareInference();
2052
2053 for (const auto& node: this->_JT_->nodes()) {
2054 const auto clique = _JT_->clique(node);
2055 if (vars == clique) return true;
2056 }
2057 return false;
2058 }
2059
2060 template < GUM_Numeric GUM_SCALAR >
2061 NodeSet ShaferShenoyMRFInference< GUM_SCALAR >::superForJointComputable_(const NodeSet& vars) {
2062 const auto superset = JointTargetedMRFInference< GUM_SCALAR >::superForJointComputable_(vars);
2063 if (!superset.empty()) return superset;
2064
2065 this->prepareInference();
2066
2067 for (const auto& node: _JT_->nodes()) {
2068 const auto clique = _JT_->clique(node);
2069 if (vars.isStrictSubsetOf(clique)) return clique;
2070 }
2071
2072
2073 return NodeSet();
2074 }
2075
2076 // the function used to combine two tables
2077 template < GUM_Numeric GUM_SCALAR >
2078 static Tensor< GUM_SCALAR > SSNewMNmultiTensor(const Tensor< GUM_SCALAR >& t1,
2079 const Tensor< GUM_SCALAR >& t2) {
2080 return t1 * t2;
2081 }
2082
2083 // the function used to project (marginalize) a table
2084 template < GUM_Numeric GUM_SCALAR >
2085 static Tensor< GUM_SCALAR > SSNewMNprojTensor(const Tensor< GUM_SCALAR >& t1,
2086 const gum::VariableSet& del_vars) {
2087 return t1.sumOut(del_vars);
2088 }
2089
2090 template < GUM_Numeric GUM_SCALAR >
2091 void ShaferShenoyMRFInference< GUM_SCALAR >::onStateChanged_() {}
2092
2093} /* namespace gum */
2094
2095#endif // DOXYGEN_SHOULD_SKIP_THIS
Implementation of Shafer-Shenoy's algorithm for inference in Markov random fields.
An algorithm for converting a join tree into a binary join tree.
Exception : a similar element already exists.
<agrum/MRF/inference/evidenceMRFInference.h>
Exception : fatal (unknown ?) error.
Class representing the minimal interface for Markov random field.
Exception : several evidence are incompatible together (proba=0).
<agrum/MRF/inference/jointTargetedMRFInference.h>
void insert(const Key &k)
Inserts a new element into the set.
Definition set_tpl.h:510
ShaferShenoyMRFInference(const IMarkovRandomField< GUM_SCALAR > *MN, bool use_binary_join_tree=true)
default constructor
Exception : a looked-for element could not be found.
#define GUM_ERROR(type, msg)
Definition exceptions.h:76
Set< NodeId > NodeSet
Some typdefs and define for shortcuts ...
GUM_SHARED_PUBLIC bool contains(std::string_view s, std::string_view needle)
true if needle in s
Header files of gum::Instantiation.
Selection of the roots of the connected components of a junction tree.
gum is the global namespace for all aGrUM entities
Definition agrum.h:46
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...