1 /**
2  *
3  *   Copyright (c) 2005-2021 by Pierre-Henri WUILLEMIN(_at_LIP6) & Christophe GONZALES(_at_AMU)
4  *   info_at_agrum_dot_org
5  *
6  *  This library is free software: you can redistribute it and/or modify
7  *  it under the terms of the GNU Lesser General Public License as published by
8  *  the Free Software Foundation, either version 3 of the License, or
9  *  (at your option) any later version.
10  *
11  *  This library is distributed in the hope that it will be useful,
12  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
13  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14  *  GNU Lesser General Public License for more details.
15  *
16  *  You should have received a copy of the GNU Lesser General Public License
17  *  along with this library.  If not, see <http://www.gnu.org/licenses/>.
18  *
19  */
20 
21 
22 /**
23  * @file
24  * @brief Implementation of Shafer-Shenoy's algorithm for inference
25  * in Markov Networks.
26  */
27 #ifndef GUM_SHAFER_SHENOY_MN_INFERENCE_H
28 #define GUM_SHAFER_SHENOY_MN_INFERENCE_H
29 
30 #include <utility>
31 
32 #include <agrum/agrum.h>
33 #include <agrum/tools/core/math/math_utils.h>
34 #include <agrum/MN/inference/tools/evidenceMNInference.h>
35 #include <agrum/MN/inference/tools/jointTargetedMNInference.h>
36 #include <agrum/tools/graphs/algorithms/triangulations/defaultTriangulation.h>
37 
38 namespace gum {
39 
40 
41   // the function used to combine two tables
42   template < typename GUM_SCALAR >
SSNewMNmultiPotential(const Potential<GUM_SCALAR> & t1,const Potential<GUM_SCALAR> & t2)43   INLINE static Potential< GUM_SCALAR >* SSNewMNmultiPotential(const Potential< GUM_SCALAR >& t1,
44                                                                const Potential< GUM_SCALAR >& t2) {
45     return new Potential< GUM_SCALAR >(t1 * t2);
46   }
47 
48   // the function used to combine two tables
49   template < typename GUM_SCALAR >
50   INLINE static Potential< GUM_SCALAR >*
SSNewMNprojPotential(const Potential<GUM_SCALAR> & t1,const Set<const DiscreteVariable * > & del_vars)51      SSNewMNprojPotential(const Potential< GUM_SCALAR >&        t1,
52                           const Set< const DiscreteVariable* >& del_vars) {
53     return new Potential< GUM_SCALAR >(t1.margSumOut(del_vars));
54   }
55 
56 
57   /**
58    * @class ShaferShenoyMNInference ShaferShenoyMNInference.h
59    * <agrum/MN/inference/ShaferShenoyMNInference.h>
60    * @brief Implementation of Shafer-Shenoy's propagation algorithm
61    * for inference in Markov Networks
62    * @ingroup mn_inference
63    */
64   template < typename GUM_SCALAR >
65   class ShaferShenoyMNInference:
66       public JointTargetedMNInference< GUM_SCALAR >,
67       public EvidenceMNInference< GUM_SCALAR > {
68     public:
69     // ############################################################################
70     /// @name Constructors / Destructors
71     // ############################################################################
72     /// @{
73 
74     /// default constructor
75     explicit ShaferShenoyMNInference(const IMarkovNet< GUM_SCALAR >* MN,
76                                      bool                            use_binary_join_tree = true);
77 
78     /// destructor
79     ~ShaferShenoyMNInference();
80 
81     /// @}
82 
83 
84     // ############################################################################
85     /// @name Accessors / Modifiers
86     // ############################################################################
87     /// @{
88 
89     /// use a new triangulation algorithm
90     void setTriangulation(const Triangulation& new_triangulation);
91 
92     /// returns the current join tree used
93     const JoinTree* joinTree();
94 
95     /// returns the current junction tree
96     const JunctionTree* junctionTree();
97 
98     /// returns the probability of evidence
99     GUM_SCALAR evidenceProbability();
100 
101     /// @}
102 
103 
104     protected:
105     /// check if the vars form a possible computable joint (can be redefined by
106     /// subclass)
107     virtual bool    isExactJointComputable_(const NodeSet& vars) final;
108     virtual NodeSet superForJointComputable_(const NodeSet& vars) final;
109 
110     /// fired when the stage is changed
onStateChanged_()111     void onStateChanged_() final{};
112 
113     /// fired after a new evidence is inserted
114     void onEvidenceAdded_(const NodeId id, bool isHardEvidence) final;
115 
116     /// fired before an evidence is removed
117     void onEvidenceErased_(const NodeId id, bool isHardEvidence) final;
118 
119     /// fired before all the evidence are erased
120     void onAllEvidenceErased_(bool contains_hard_evidence) final;
121 
122     /** @brief fired after an evidence is changed, in particular when its status
123      * (soft/hard) changes
124      *
125      * @param nodeId the node of the changed evidence
126      * @param hasChangedSoftHard true if the evidence has changed from Soft to
127      * Hard or from Hard to Soft
128      */
129     void onEvidenceChanged_(const NodeId id, bool hasChangedSoftHard) final;
130 
131     /// fired after a new single target is inserted
132     /** @param id The target variable's id. */
133     void onMarginalTargetAdded_(const NodeId id) final;
134 
135     /// fired before a single target is removed
136     /** @param id The target variable's id. */
137     void onMarginalTargetErased_(const NodeId id) final;
138 
139     /// fired after a new Markov net has been assigned to the engine
140     virtual void onMarkovNetChanged_(const IMarkovNet< GUM_SCALAR >* mn) final;
141 
142     /// fired after a new joint target is inserted
143     /** @param set The set of target variable's ids. */
144     void onJointTargetAdded_(const NodeSet& set) final;
145 
146     /// fired before a joint target is removed
147     /** @param set The set of target variable's ids. */
148     void onJointTargetErased_(const NodeSet& set) final;
149 
150     /// fired after all the nodes of the MN are added as single targets
151     void onAllMarginalTargetsAdded_() final;
152 
153     /// fired before a all the single targets are removed
154     void onAllMarginalTargetsErased_() final;
155 
156     /// fired before a all the joint targets are removed
157     void onAllJointTargetsErased_() final;
158 
159     /// fired before a all single and joint_targets are removed
160     void onAllTargetsErased_() final;
161 
162     /// prepares inference when the latter is in OutdatedStructure state
163     /** Note that the values of evidence are not necessarily
164      * known and can be changed between updateOutdatedStructure_ and
165      * makeMNInference_. */
166     void updateOutdatedStructure_() final;
167 
168     /// prepares inference when the latter is in OutdatedPotentials state
169     /** Note that the values of evidence are not necessarily
170      * known and can be changed between updateOutdatedStructure_ and
171      * makeMNInference_. */
172     void updateOutdatedPotentials_() final;
173 
174     /// called when the inference has to be performed effectively
175     /** Once the inference is done, fillPosterior_ can be called. */
176     void makeInference_() final;
177 
178 
179     /// returns the posterior of a given variable
180     /** @param id The variable's id. */
181     const Potential< GUM_SCALAR >& posterior_(NodeId id) final;
182 
183     /// returns the posterior of a declared target set
184     /** @param set The set of ids of the variables whose joint posterior is
185      * looked for. */
186     const Potential< GUM_SCALAR >& jointPosterior_(const NodeSet& set) final;
187 
188     /** @brief asks derived classes for the joint posterior of a set of
189      * variables not declared as a joint target
190      *
191      * @param wanted_target The set of ids of the variables whose joint
192      * posterior is looked for.
193      * @param declared_target the joint target declared by the user that
194      * contains set */
195     const Potential< GUM_SCALAR >& jointPosterior_(const NodeSet& wanted_target,
196                                                    const NodeSet& declared_target) final;
197 
198     /// returns a fresh potential equal to P(argument,evidence)
199     Potential< GUM_SCALAR >* unnormalizedJointPosterior_(NodeId id) final;
200 
201     /// returns a fresh potential equal to P(argument,evidence)
202     Potential< GUM_SCALAR >* unnormalizedJointPosterior_(const NodeSet& set) final;
203 
204 
205     private:
206     typedef Set< const Potential< GUM_SCALAR >* >             _PotentialSet_;
207     typedef SetIteratorSafe< const Potential< GUM_SCALAR >* > _PotentialSetIterator_;
208 
209     /// the operator for performing the projections
210     Potential< GUM_SCALAR >* (*_projection_op_)(const Potential< GUM_SCALAR >&,
211                                                 const Set< const DiscreteVariable* >&){
212        SSNewMNprojPotential};
213 
214     /// the operator for performing the combinations
215     Potential< GUM_SCALAR >* (*_combination_op_)(const Potential< GUM_SCALAR >&,
216                                                  const Potential< GUM_SCALAR >&){
217        SSNewMNmultiPotential};
218 
219     /// the triangulation class creating the junction tree used for inference
220     Triangulation* _triangulation_;
221 
222     /** @brief indicates whether we should transform junction trees into
223      * binary join trees */
224     bool _use_binary_join_tree_{true};
225 
226     /// the undigraph extracted from the MN and used to construct the join tree
227     /** If all nodes are targets, this graph corresponds to the graph
228      * of the MN. Otherwise, it may be a subgraph of this moral graph. */
229     UndiGraph _reduced_graph_;
230 
231     /// the join (or junction) tree used to answer the last inference query
232     JoinTree* _propagator_{nullptr};
233 
234     /// the junction tree to answer the last inference query
235     JunctionTree* _junctionTree_{nullptr};
236 
237     /// indicates whether a new join tree is needed for the next inference
238     /** when modifying the set of hard evidence, we can determine that
239      * the current JT is no more appropriate for inference. This variable
240      * enables us to keep track of this. */
241     bool _is_new_jt_needed_{true};
242 
243     /// a clique node used as a root in each connected component of  _propagator_
244     /** For usual probabilistic inference, roots is useless. This is useful
245      * when computing the probability of evidence. In this case, we need to
246      * compute this probability in every connected component and multiply
247      * them to get the overall probability of evidence.
248      * @warning  _roots_ should be computed only when evidenceProbability
249      * is called. */
250     NodeSet _roots_;
251 
252     /// for each node of  _reduced_graph_ (~ in the Markov net), associate an ID in
253     /// the JT
254     HashTable< NodeSet, NodeId > _factor_to_clique_;
255 
256     NodeProperty< NodeId > _node_to_clique_;
257 
258     /// for each joint target, assign a clique in the JT that contains it
259     HashTable< NodeSet, NodeId > _joint_target_to_clique_;
260 
261     /// the list of all potentials stored in the cliques
262     /** This structure contains a list for each clique in the join tree. If
263      * a clique did not received any potential, then its list is empty but
264      * the entry for the clique does exist. Note that clique potentials
265      * contain also soft evidence and the factors that were projected to
266      * remove their variables that received hard evidence. The product of all
267      * these potentials is precisely the potential stored into
268      *  _clique_potentials_ */
269     NodeProperty< _PotentialSet_ > _clique_potentials_list_;
270 
271     /// the potentials stored into the cliques by Shafer-Shenoy
272     /** For a given clique, there is an entry in  _clique_potentials_ if and
273      * only if the clique received some potential(s). In this case, the
274      * potential stored is the combination of all the corresponding list of
275      * potentials in  _clique_potentials_list_. */
276     NodeProperty< const Potential< GUM_SCALAR >* > _clique_potentials_;
277 
278     /// the list of all potentials stored in the separators after inferences
279     /** This structure contains all the arcs of the join tree (edges in both
280      * directions) whether the arc received any potential or not. */
281     ArcProperty< _PotentialSet_ > _separator_potentials_;
282 
283     /// the set of potentials created for the last inference messages
284     /** This structure contains only the arcs on which potentials have
285      * been created.
286      * @warning Note that the factors that were projected due to hard
287      * evidence do not belong to this structure, they are kept in
288      *  _hard_ev_projected_factors_. */
289     ArcProperty< _PotentialSet_ > _created_messages_;
290 
291     /// the set of single posteriors computed during the last inference
292     /** the posteriors are owned by ShaferShenoyMNInference. */
293     NodeProperty< const Potential< GUM_SCALAR >* > _target_posteriors_;
294 
295     /// the set of set target posteriors computed during the last inference
296     /** the posteriors are owned by ShaferShenoyMNInference. */
297     HashTable< NodeSet, const Potential< GUM_SCALAR >* > _joint_target_posteriors_;
298 
299     /** @brief the constants resulting from the projections of CPTs defined
300      * over only hard evidence nodes
301      * @TODO remove this constant and insert the notion of a constant into
302      * potentials/multidim arrays */
303     // NodeProperty< GUM_SCALAR >  _constants_;
304 
305     /// indicates whether a message (from one clique to another) has been
306     /// computed
307     /** Here, all the messages, computed or not, are put into the property, only
308      * the Boolean makes the difference between messages computed and those that
309      * were not computed */
310     ArcProperty< bool > _messages_computed_;
311 
312     /// the soft evidence stored in the cliques per their assigned node in the MN
313     /** This variable is useful for method updateOutdatedPotentials_: it
314      * enables to know which soft evidence should be removed/added into the
315      * cliques of the join tree.
316      * @warning These potentials are not owned by ShaferShenoyMNInference,
317      * they are only referenced by it. Only the cliques that contain evidence
318      * are filled in this structure. */
319     NodeProperty< const Potential< GUM_SCALAR >* > _node_to_soft_evidence_;
320 
321     /// the factors that were projected due to hard evidence nodes
322     /** For each factor containing the nodes that contain some
323      * hard evidence, assigns a new projected factor that does not contain
324      * these nodes anymore.
325      * @warning These potentials are owned by the inference class. */
326     HashTable< NodeSet, const Potential< GUM_SCALAR >* > _hard_ev_projected_factors_;
327 
328     /// the hard evidence nodes which were projected in factors
329     NodeSet _hard_ev_nodes_;
330 
331     /// the possible types of evidence changes
332     enum EvidenceChangeType
333     {
334       EVIDENCE_ADDED,
335       EVIDENCE_ERASED,
336       EVIDENCE_MODIFIED
337     };
338 
339     /** @brief indicates which nodes of the MN have evidence that changed
340      * since the last inference */
341     NodeProperty< EvidenceChangeType > _evidence_changes_;
342 
343     /// for comparisons with 1 - epsilon
344     const GUM_SCALAR _one_minus_epsilon_{GUM_SCALAR(1.0 - 1e-6)};
345 
346 
347     /// check whether a new join tree is really needed for the next inference
348     bool _isNewJTNeeded_() const;
349 
350     /// create a new junction tree as well as its related data structures
351     void _createNewJT_();
352 
353     /// sets the operator for performing the projections
354     void _setProjectionFunction_(Potential< GUM_SCALAR >* (
355        *proj)(const Potential< GUM_SCALAR >&, const Set< const DiscreteVariable* >&));
356 
357     /// sets the operator for performing the combinations
358     void _setCombinationFunction_(Potential< GUM_SCALAR >* (*comb)(const Potential< GUM_SCALAR >&,
359                                                                    const Potential< GUM_SCALAR >&));
360 
361     /// invalidate all the messages sent from a given clique
362     void _diffuseMessageInvalidations_(NodeId from, NodeId to, NodeSet& cliques_invalidated);
363 
364     /// invalidate all messages, posteriors and created potentials
365     void _invalidateAllMessages_();
366 
367     /// compute a root for each connected component of  _propagator_
368     void _computeJoinTreeRoots_();
369 
370     /** @brief removes variables del_vars from a list of potentials and
371      * returns the resulting list */
372     _PotentialSet_ _marginalizeOut_(_PotentialSet_                  pot_list,
373                                     Set< const DiscreteVariable* >& del_vars,
374                                     Set< const DiscreteVariable* >& kept_vars);
375 
376     /// creates the message sent by clique from_id to clique to_id
377     void _produceMessage_(NodeId from_id, NodeId to_id);
378 
379     /// actually perform the collect phase
380     void _collectMessage_(NodeId id, NodeId from);
381 
382     /// avoid copy constructors
383     ShaferShenoyMNInference(const ShaferShenoyMNInference< GUM_SCALAR >&);
384 
385     /// avoid copy operators
386     ShaferShenoyMNInference< GUM_SCALAR >& operator=(const ShaferShenoyMNInference< GUM_SCALAR >&);
387   };
388 
389 
390 #ifndef GUM_NO_EXTERN_TEMPLATE_CLASS
391   extern template class ShaferShenoyMNInference< double >;
392 #endif
393 
394 } /* namespace gum */
395 
396 #include <agrum/MN/inference/ShaferShenoyMNInference_tpl.h>
397 
398 #endif /* SHAFER_SHENOY_INFERENCE_H */
399