aGrUM 3.3.2
a C++ library for (probabilistic) graphical models
ShaferShenoyMRFInference.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
49#ifndef GUM_SHAFER_SHENOY_MN_INFERENCE_H
50#define GUM_SHAFER_SHENOY_MN_INFERENCE_H
51
52#include <optional>
53#include <utility>
54
55#include <agrum/agrum.h>
56
61
62namespace gum {
63
64
65 // the function used to combine two tables
66 template < GUM_Numeric GUM_SCALAR >
67 INLINE static Tensor< GUM_SCALAR > SSNewMNmultiTensor(const Tensor< GUM_SCALAR >& t1,
68 const Tensor< GUM_SCALAR >& t2);
69
70 // the function used to combine two tables
71 template < GUM_Numeric GUM_SCALAR >
72 INLINE static Tensor< GUM_SCALAR > SSNewMNprojTensor(const Tensor< GUM_SCALAR >& t1,
73 const gum::VariableSet& del_vars);
74
82 template < GUM_Numeric GUM_SCALAR >
84 public JointTargetedMRFInference< GUM_SCALAR >,
85 public EvidenceMRFInference< GUM_SCALAR >,
86 public ScheduledInference {
87 public:
88 // ############################################################################
90 // ############################################################################
92
95 bool use_binary_join_tree = true);
96
99
101
102
103 // ############################################################################
105 // ############################################################################
107
109 void setTriangulation(const Triangulation& new_triangulation);
110
112
116
118
123
125
130 GUM_SCALAR evidenceProbability() final;
131
133
134
135 protected:
138 bool isExactJointComputable_(const NodeSet& vars) final;
140
142 void onEvidenceAdded_(const NodeId id, bool isHardEvidence) final;
143
145 void onEvidenceErased_(const NodeId id, bool isHardEvidence) final;
146
148 void onAllEvidenceErased_(bool has_hard_evidence) final;
149
157 void onEvidenceChanged_(const NodeId id, bool hasChangedSoftHard) final;
158
160
161 void onMarginalTargetAdded_(const NodeId id) final;
162
164
165 void onMarginalTargetErased_(const NodeId id) final;
166
168 void onModelChanged_(const GraphicalModel* mn) final;
169
171 virtual void onMRFChanged_(const IMarkovRandomField< GUM_SCALAR >* mn) final;
172
174
175 void onJointTargetAdded_(const NodeSet& set) final;
176
178
179 void onJointTargetErased_(const NodeSet& set) final;
180
183
186
189
192
194 void onStateChanged_() final;
195
197
201
203
207
209
210 void makeInference_() final;
211
212
214
215 const Tensor< GUM_SCALAR >& posterior_(NodeId id) final;
216
218
220 const Tensor< GUM_SCALAR >& jointPosterior_(const NodeSet& set) final;
221
229 const Tensor< GUM_SCALAR >& jointPosterior_(const NodeSet& wanted_target,
230 const NodeSet& declared_target) final;
231
233 Tensor< GUM_SCALAR >* unnormalizedJointPosterior_(NodeId id) final;
234
236 Tensor< GUM_SCALAR >* unnormalizedJointPosterior_(const NodeSet& set) final;
237
238
239 private:
241 GUM_SCALAR _evidenceMass_();
242
244 std::optional< GUM_SCALAR > _partition_function_;
245
246 using _TensorSet_ = Set< const Tensor< GUM_SCALAR >* >;
248 using _TensorSetIterator_ = SetIteratorSafe< const Tensor< GUM_SCALAR >* >;
249
251 Tensor< GUM_SCALAR > (*_projection_op_)(const Tensor< GUM_SCALAR >&, const gum::VariableSet&)
253
255 Tensor< GUM_SCALAR > (*_combination_op_)(const Tensor< GUM_SCALAR >&,
256 const Tensor< GUM_SCALAR >&) = SSNewMNmultiTensor;
257
260
264
266
269
271 JoinTree* _JT_{nullptr};
272
275
277
281
283
290
292
297
300
302
305
308
310
318
320
325
327
331
333
340
342
344
346
348
354
356
360
362
369
371
376
379
382
386
388 bool _use_schedules_{false};
389
391 static constexpr double _schedule_threshold_{1000000.0};
392
394 static constexpr GUM_SCALAR _one_minus_epsilon_{GUM_SCALAR(1.0 - 1e-6)};
395
396
398 bool _isNewJTNeeded_() const;
399
402
405
408
410 void _setProjectionFunction_(Tensor< GUM_SCALAR > (*proj)(const Tensor< GUM_SCALAR >&,
411 const gum::VariableSet&));
412
414 void _setCombinationFunction_(Tensor< GUM_SCALAR > (*comb)(const Tensor< GUM_SCALAR >&,
415 const Tensor< GUM_SCALAR >&));
416
418 void _diffuseMessageInvalidations_(NodeId from_id, NodeId to_id, NodeSet& invalidated_cliques);
419
422
425
429 _ScheduleMultiDimSet_ pot_list,
430 gum::VariableSet& del_vars,
431 gum::VariableSet& kept_vars);
432
436 gum::VariableSet& del_vars,
437 gum::VariableSet& kept_vars);
438
440 void _produceMessage_(Schedule& schedule, NodeId from_id, NodeId to_id);
441
443 void _produceMessage_(NodeId from_id, NodeId to_id);
444
446 void _collectMessage_(Schedule& schedule, NodeId id, NodeId from);
447
450
452 Tensor< GUM_SCALAR >* _unnormalizedJointPosterior_(Schedule& schedule, NodeId id);
453
455 Tensor< GUM_SCALAR >* _unnormalizedJointPosterior_(NodeId id);
456
458 Tensor< GUM_SCALAR >* _unnormalizedJointPosterior_(Schedule& schedule, const NodeSet& set);
459
461 Tensor< GUM_SCALAR >* _unnormalizedJointPosterior_(const NodeSet& set);
462
463
466
469 = delete;
470 };
471
472
473#ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
474 extern template class GUM_PUBLIC_MRF ShaferShenoyMRFInference< double >;
475#endif
476
477
478} /* namespace gum */
479
481
482#endif /* SHAFER_SHENOY_INFERENCE_H */
Implementation of Shafer-Shenoy's propagation for inference in Markov random fields.
EvidenceMRFInference(const IMarkovRandomField< GUM_SCALAR > *mn)
default constructor
Virtual base class for probabilistic graphical models.
The class for generic Hash Tables.
Definition hashTable.h:640
Class representing the minimal interface for Markov random field.
The Table-agnostic base class of scheduleMultiDim.
JointTargetedMRFInference(const IMarkovRandomField< GUM_SCALAR > *mn)
default constructor
Class containing a schedule of operations to perform on multidims.
Definition schedule.h:79
ScheduledInference(Size max_nb_threads=0, double max_megabyte_memory=0.0)
default constructor
Safe iterators for the Set class.
Definition set.h:592
Representation of a set.
Definition set.h:129
void onAllJointTargetsErased_() final
fired before all the joint targets are removed
HashTable< const Tensor< GUM_SCALAR > *, GUM_SCALAR > _constants_
the constants resulting from the projections of CPTs defined over only hard evidence nodes @TODO remo...
void _setProjectionFunction_(Tensor< GUM_SCALAR >(*proj)(const Tensor< GUM_SCALAR > &, const gum::VariableSet &))
sets the operator for performing the projections
UndiGraph _graph_
the undigraph extracted from the MRF and used to construct the join tree
bool _use_binary_join_tree_
indicates whether we should transform junction trees into binary join trees
void onAllEvidenceErased_(bool has_hard_evidence) final
fired before all the evidence are erased
Triangulation * _triangulation_
the triangulation class creating the junction tree used for inference
void updateOutdatedTensors_() final
prepares inference when the latter is in OutdatedTensors state
NodeProperty< EvidenceChangeType > _evidence_changes_
indicates which nodes of the MRF have evidence that changed since the last inference
void setTriangulation(const Triangulation &new_triangulation)
use a new triangulation algorithm
std::optional< GUM_SCALAR > _partition_function_
the partition function Z of the MRF (cache for evidenceProbability)
void _setCombinationFunction_(Tensor< GUM_SCALAR >(*comb)(const Tensor< GUM_SCALAR > &, const Tensor< GUM_SCALAR > &))
sets the operator for performing the combinations
ShaferShenoyMRFInference< GUM_SCALAR > & operator=(const ShaferShenoyMRFInference< GUM_SCALAR > &)=delete
avoid copy operators
NodeProperty< const IScheduleMultiDim * > _clique_ss_tensor_
the tensors stored into the cliques by Shafer-Shenoy
NodeProperty< _ScheduleMultiDimSet_ > _clique_tensors_
the list of all tensors stored in the cliques
HashTable< const Tensor< GUM_SCALAR > *, const IScheduleMultiDim * > _hard_ev_projected_factors_
the factors that were projected due to hard evidence nodes
bool _is_new_jt_needed_
indicates whether a new join tree is needed for the next inference
void _initializeJTCliques_(Schedule &schedule)
put all the CPTs into the cliques when creating the JT using a schedule
Tensor< GUM_SCALAR >(*) _projection_op_(const Tensor< GUM_SCALAR > &, const gum::VariableSet &)
the operator for performing the projections
void makeInference_() final
called when the inference has to be performed effectively
void onStateChanged_() final
fired when the state of the inference engine is changed
JoinTree * _JT_
the join (or junction) tree used to answer the last inference query
const JoinTree * joinTree()
returns the current join tree used
void _initializeJTCliques_()
put all the CPTs into the cliques when creating the JT without using a schedule
void onAllMarginalTargetsAdded_() final
fired after all the nodes of the MRF are added as single targets
const Tensor< GUM_SCALAR > & jointPosterior_(const NodeSet &set) final
returns the posterior of a declared target set
bool isExactJointComputable_(const NodeSet &vars) final
check if the vars form a possible computable joint (can be redefined by subclass)
Tensor< GUM_SCALAR > * _unnormalizedJointPosterior_(Schedule &schedule, NodeId id)
computes the unnormalized posterior of a node using schedules
const IScheduleMultiDim * _marginalizeOut_(_ScheduleMultiDimSet_ &pot_list, gum::VariableSet &del_vars, gum::VariableSet &kept_vars)
removes variables del_vars from a list of tensors and returns the resulting list directly without sch...
void _createNewJT_()
create a new junction tree as well as its related data structures
HashTable< NodeSet, const Tensor< GUM_SCALAR > * > _joint_target_posteriors_
the set of set target posteriors computed during the last inference
void onMarginalTargetAdded_(const NodeId id) final
fired after a new single target is inserted
HashTable< NodeSet, NodeId > _joint_target_to_clique_
for each set target, assign a clique in the JT that contains it
ArcProperty< bool > _messages_computed_
indicates whether a message (from one clique to another) has been computed
NodeProperty< _TensorSet_ > _node_to_factors_
assign to each node the set of factors containing it
Set< const IScheduleMultiDim * > _ScheduleMultiDimSet_
void _invalidateAllMessages_()
invalidate all messages, posteriors and created tensors
GUM_SCALAR _evidenceMass_()
returns the unnormalized mass Z(e) of the evidence (the partition function without evidence)
void updateOutdatedStructure_() final
prepares inference when the latter is in OutdatedStructure state
void onJointTargetAdded_(const NodeSet &set) final
fired after a new joint target is inserted
void _produceMessage_(NodeId from_id, NodeId to_id)
creates the message sent by clique from_id to clique to_id without schedules
void _collectMessage_(Schedule &schedule, NodeId id, NodeId from)
perform the collect phase using schedules
HashTable< const Tensor< GUM_SCALAR > *, NodeId > _factor_to_clique_
assign to each factor in the MRF the clique that will contain it
GUM_SCALAR evidenceProbability() final
returns the probability of evidence
bool _use_schedules_
indicates whether we should use schedules for inference
static constexpr double _schedule_threshold_
minimal number of operations to perform in the JT to use schedules
NodeSet _hard_ev_nodes_
the hard evidence nodes which were projected in factors
Tensor< GUM_SCALAR > * _unnormalizedJointPosterior_(NodeId id)
computes the unnormalized posterior of a node without using schedules
void onModelChanged_(const GraphicalModel *mn) final
fired after a new Markov net has been assigned to the inference engine
NodeProperty< NodeId > _node_to_clique_
for each node of graph (~ in the Markov net), associate an ID in the JT
~ShaferShenoyMRFInference() override
destructor
void onAllMarginalTargetsErased_() final
fired before all the single targets are removed
void onEvidenceChanged_(const NodeId id, bool hasChangedSoftHard) final
fired after an evidence is changed, in particular when its status (soft/hard) changes
const Tensor< GUM_SCALAR > & posterior_(NodeId id) final
returns the posterior of a given variable
Tensor< GUM_SCALAR > * unnormalizedJointPosterior_(NodeId id) final
returns a fresh tensor equal to P(argument,evidence)
void onEvidenceErased_(const NodeId id, bool isHardEvidence) final
fired before an evidence is removed
void onMarginalTargetErased_(const NodeId id) final
fired before a single target is removed
EvidenceChangeType
the possible types of evidence changes
void onEvidenceAdded_(const NodeId id, bool isHardEvidence) final
fired after a new evidence is inserted
void _diffuseMessageInvalidations_(NodeId from_id, NodeId to_id, NodeSet &invalidated_cliques)
invalidate all the messages sent from a given clique
Tensor< GUM_SCALAR >(*) _combination_op_(const Tensor< GUM_SCALAR > &, const Tensor< GUM_SCALAR > &)
the operator for performing the combinations
void _computeJoinTreeRoots_()
compute a root for each connected component of JT
void onJointTargetErased_(const NodeSet &set) final
fired before a joint target is removed
Set< const Tensor< GUM_SCALAR > * > _TensorSet_
SetIteratorSafe< const Tensor< GUM_SCALAR > * > _TensorSetIterator_
const IScheduleMultiDim * _marginalizeOut_(Schedule &schedule, _ScheduleMultiDimSet_ pot_list, gum::VariableSet &del_vars, gum::VariableSet &kept_vars)
removes variables del_vars from a list of tensors and returns the resulting list using schedules
ArcProperty< const IScheduleMultiDim * > _arc_to_created_tensors_
the set of tensors created for the last inference messages
NodeSet superForJointComputable_(const NodeSet &vars) final
NodeSet _roots_
a clique node used as a root in each connected component of JT
void onAllTargetsErased_() final
fired before all single and joint targets are removed
bool _isNewJTNeeded_() const
check whether a new join tree is really needed for the next inference
void _collectMessage_(NodeId id, NodeId from)
actually perform the collect phase directly without schedules
Tensor< GUM_SCALAR > * _unnormalizedJointPosterior_(const NodeSet &set)
returns a fresh tensor equal to P(argument,evidence) without using schedules
ArcProperty< const IScheduleMultiDim * > _separator_tensors_
the list of all tensors stored in the separators after inferences
void _produceMessage_(Schedule &schedule, NodeId from_id, NodeId to_id)
creates the message sent by clique from_id to clique to_id using schedules
NodeProperty< const IScheduleMultiDim * > _node_to_soft_evidence_
the soft evidence stored in the cliques per their assigned node in the MRF
JunctionTree * _junctionTree_
the junction tree to answer the last inference query
Tensor< GUM_SCALAR > * _unnormalizedJointPosterior_(Schedule &schedule, const NodeSet &set)
returns a fresh tensor equal to P(argument,evidence) using schedules
ShaferShenoyMRFInference(const IMarkovRandomField< GUM_SCALAR > *MN, bool use_binary_join_tree=true)
default constructor
const JunctionTree * junctionTree()
returns the current junction tree
NodeProperty< const Tensor< GUM_SCALAR > * > _target_posteriors_
the set of single posteriors computed during the last inference
virtual void onMRFChanged_(const IMarkovRandomField< GUM_SCALAR > *mn) final
fired after a new Markov net has been assigned to the inference engine
static constexpr GUM_SCALAR _one_minus_epsilon_
for comparisons with 1 - epsilon
ShaferShenoyMRFInference(const ShaferShenoyMRFInference< GUM_SCALAR > &)=delete
avoid copy constructors
aGrUM's Tensor is a multi-dimensional array with tensor operators.
Definition tensor.h:85
Interface for all the triangulation methods.
Base class for undirected graphs.
Definition undiGraph.h:134
Class for computing default triangulations of graphs.
This file contains the abstract class definition for computing the probability of evidence entered in...
Size NodeId
Type for node ids.
HashTable< Arc, VAL > ArcProperty
Property on graph elements.
HashTable< NodeId, VAL > NodeProperty
Property on graph elements.
Set< NodeId > NodeSet
Some typdefs and define for shortcuts ...
This file contains the abstract inference class definition for computing (incrementally) joint poster...
gum is the global namespace for all aGrUM entities
Definition agrum.h:46
template class GUM_PUBLIC_MRF ShaferShenoyMRFInference< double >
Set< const DiscreteVariable * > VariableSet
CliqueGraph JoinTree
a join tree is a clique graph satisfying the running intersection property (but some cliques may be i...
static INLINE Tensor< GUM_SCALAR > SSNewMNmultiTensor(const Tensor< GUM_SCALAR > &t1, const Tensor< GUM_SCALAR > &t2)
CliqueGraph JunctionTree
a junction tree is a clique graph satisfying the running intersection property and such that no cliqu...
static INLINE Tensor< GUM_SCALAR > SSNewMNprojTensor(const Tensor< GUM_SCALAR > &t1, const gum::VariableSet &del_vars)
STL namespace.
The class enabling flexible inferences using schedules.