gum::prm::SVE< GUM_SCALAR > Class Template Reference

This class is an implementation of the Structured Variable Elimination algorithm on PRM<GUM_SCALAR>. More...

#include <agrum/PRM/SVE.h>

Inheritance diagram for gum::prm::SVE< GUM_SCALAR >:

Collaboration diagram for gum::prm::SVE< GUM_SCALAR >:

Public Member Functions
Constructors & destructor.
	SVE (const PRM< GUM_SCALAR > &prm, const PRMSystem< GUM_SCALAR > &system)
	Default Constructor. More...
	~SVE ()
	Destructor. More...
Getters & setters.
virtual std::string	name () const
	Returns the name of the current inference algorithm. More...
Query methods.
void	posterior (const Chain &chain, Potential< GUM_SCALAR > &m)
	Compute the posterior of the formal attribute pointed by chain and stores it in m. More...
void	joint (const std::vector< Chain > &chains, Potential< GUM_SCALAR > &j)
	Compute the joint probability of the formals attributes pointed by chains and stores it in m. More...
Evidence handling.
EMap &	evidence (const PRMInstance< GUM_SCALAR > &i)
	Returns EMap of evidences over i. More...
EMap &	evidence (const PRMInstance< GUM_SCALAR > *i)
	Returns EMap of evidences over i. More...
const EMap &	evidence (const PRMInstance< GUM_SCALAR > &i) const
	Returns EMap of evidences over i. More...
const EMap &	evidence (const PRMInstance< GUM_SCALAR > *i) const
	Returns EMap of evidences over i. More...
bool	hasEvidence (const PRMInstance< GUM_SCALAR > &i) const
	Returns true if i has evidence. More...
bool	hasEvidence (const PRMInstance< GUM_SCALAR > *i) const
	Returns EMap of evidences over i. More...
bool	hasEvidence (const Chain &chain) const
	Returns true if i has evidence on PRMAttribute<GUM_SCALAR> a. More...
bool	hasEvidence () const
	Returns true if i has evidence on PRMAttribute<GUM_SCALAR> a. More...
void	addEvidence (const Chain &chain, const Potential< GUM_SCALAR > &p)
	Add an evidence to the given instance's elt. More...
void	removeEvidence (const Chain &chain)
	Remove evidence on the given instance's elt. More...
void	clearEvidence ()
	Remove all evidences. More...

Public Types
typedef NodeProperty< const Potential< GUM_SCALAR > *>	EMap
	Code alias. More...
typedef NodeProperty< const Potential< GUM_SCALAR > *>::iterator_safe	EMapIterator
	Code alias. More...
typedef NodeProperty< const Potential< GUM_SCALAR > *>::const_iterator_safe	EMapConstIterator
	Code alias. More...

Protected Attributes
Protected members.
PRM< GUM_SCALAR > const *	prm_
	The PRM<GUM_SCALAR> on which inference is done. More...
PRMSystem< GUM_SCALAR > const *	sys_
	The Model on which inference is done. More...

Query methods.
typedef PRMInference< GUM_SCALAR >::Chain	Chain
	Code alias. More...
virtual void	evidenceAdded_ (const Chain &chain)
	See PRMInference<GUM_SCALAR>::evidenceAdded_(). More...
virtual void	evidenceRemoved_ (const Chain &chain)
	See PRMInference<GUM_SCALAR>::evidenceRemoved_(). More...
virtual void	posterior_ (const Chain &chain, Potential< GUM_SCALAR > &m)
	See PRMInference<GUM_SCALAR>::posterior_(). More...
virtual void	joint_ (const std::vector< Chain > &queries, Potential< GUM_SCALAR > &j)
	See PRMInference<GUM_SCALAR>::joint_(). More...

Detailed Description

template<typename GUM_SCALAR>
class gum::prm::SVE< GUM_SCALAR >

This class is an implementation of the Structured Variable Elimination algorithm on PRM<GUM_SCALAR>.

Definition at line 65 of file SVE.h.

Member Typedef Documentation

ArraySetIterator

template<typename GUM_SCALAR >

typedef Set< MultiDimArray< GUM_SCALAR >* >::iterator_safe gum::prm::SVE< GUM_SCALAR >::ArraySetIterator

private

Code alias.

Definition at line 120 of file SVE.h.

BucketSet

template<typename GUM_SCALAR >

typedef Set< Potential< GUM_SCALAR >* > gum::prm::SVE< GUM_SCALAR >::BucketSet

private

Code alias.

Definition at line 113 of file SVE.h.

BucketSetIterator

template<typename GUM_SCALAR >

typedef Set< Potential< GUM_SCALAR >* >::iterator_safe gum::prm::SVE< GUM_SCALAR >::BucketSetIterator

private

Code alias.

Definition at line 116 of file SVE.h.

Chain

template<typename GUM_SCALAR >

typedef PRMInference< GUM_SCALAR >::Chain gum::prm::SVE< GUM_SCALAR >::Chain

protected

Code alias.

Definition at line 95 of file SVE.h.

EMap

template<typename GUM_SCALAR>

typedef NodeProperty< const Potential< GUM_SCALAR >* > gum::prm::PRMInference< GUM_SCALAR >::EMap

inherited

Code alias.

Definition at line 59 of file PRMInference.h.

EMapConstIterator

template<typename GUM_SCALAR>

typedef NodeProperty< const Potential< GUM_SCALAR >* >::const_iterator_safe gum::prm::PRMInference< GUM_SCALAR >::EMapConstIterator

inherited

Code alias.

Definition at line 68 of file PRMInference.h.

EMapIterator

template<typename GUM_SCALAR>

typedef NodeProperty< const Potential< GUM_SCALAR >* >::iterator_safe gum::prm::PRMInference< GUM_SCALAR >::EMapIterator

inherited

Code alias.

Definition at line 64 of file PRMInference.h.

Constructor & Destructor Documentation

SVE()

template<typename GUM_SCALAR >

INLINE gum::prm::SVE< GUM_SCALAR >::SVE	(	const PRM< GUM_SCALAR > &	prm,
		const PRMSystem< GUM_SCALAR > &	system
	)

Default Constructor.

Definition at line 657 of file SVE_tpl.h.

References gum::prm::ParamScopeData< GUM_SCALAR >::ParamScopeData().

                                                                         :
        PRMInference< GUM_SCALAR >(prm, system),
        class_elim_order__(0) {
      GUM_CONSTRUCTOR(SVE);
    }

Here is the call graph for this function:

~SVE()

template<typename GUM_SCALAR >

gum::prm::SVE< GUM_SCALAR >::~SVE

(

)

Destructor.

Definition at line 107 of file SVE_tpl.h.

References gum::prm::ParamScopeData< GUM_SCALAR >::ParamScopeData().

                            {
      GUM_DESTRUCTOR(SVE);

      for (const auto& elt: elim_orders__)
        delete elt.second;

      for (const auto& elt: lifted_pools__)
        delete elt.second;

      if (class_elim_order__ != nullptr) delete class_elim_order__;

      for (const auto trash: lifted_trash__)
        delete trash;

      for (auto set: delayedVariables__)
        delete set.second;
    }

Here is the call graph for this function:

Member Function Documentation

addDelayedVariable__()

template<typename GUM_SCALAR >

INLINE void gum::prm::SVE< GUM_SCALAR >::addDelayedVariable__ ( const PRMInstance< GUM_SCALAR > *  i, const PRMInstance< GUM_SCALAR > *  j, NodeId  id  )

private

When there is a loop in the references some variable elimination must be delayed, this methods add such variable to delayedVariables__ to keep track of them.

Parameters

i	An PRMInstance<GUM_SCALAR> with a child of j->get(id).
j	The PRMInstance<GUM_SCALAR> with the delayed variable.
id	The NodeId of the delayed variable.

Definition at line 716 of file SVE_tpl.h.

References gum::prm::ParamScopeData< GUM_SCALAR >::ParamScopeData().

                                                          {
      try {
        delayedVariables__[i]->insert(&(j->get(id).type().variable()));
      } catch (NotFound&) {
        delayedVariables__.insert(i, new Set< const DiscreteVariable* >());
        delayedVariables__[i]->insert(&(j->get(id).type().variable()));
      } catch (DuplicateElement&) {
        // happends if j->get(id) is parent of more than one variable in i
      }

      static std::string dot = ".";

      try {
        delayedVariablesCounters__[j->name() + dot + j->get(id).safeName()] += 1;
      } catch (NotFound&) {
        delayedVariablesCounters__.insert(j->name() + dot + j->get(id).safeName(),
                                          1);
      }
    }

Here is the call graph for this function:

addEvidence()

template<typename GUM_SCALAR>

void gum::prm::PRMInference< GUM_SCALAR >::addEvidence ( const Chain &  chain, const Potential< GUM_SCALAR > &  p  )

inherited

Add an evidence to the given instance's elt.

Parameters

chain	The variable being observed.
p	The Potential added (by copy) as evidence.

Exceptions

NotFound	Raised if elt does not belong to i.
OperationNotAllowed	Raised if p is inconsistent with elt.

Definition at line 108 of file PRMInference_tpl.h.

                                                                                 {
      if (chain.first->exists(chain.second->id())) {
        if ((p.nbrDim() != 1) || (!p.contains(chain.second->type().variable())))
          GUM_ERROR(OperationNotAllowed,
                    "illegal evidence for the given PRMAttribute.");

        Potential< GUM_SCALAR >* e = new Potential< GUM_SCALAR >();
        e->add(chain.second->type().variable());
        Instantiation i(*e);

        for (i.setFirst(); !i.end(); i.inc())
          e->set(i, p.get(i));

        PRMInference< GUM_SCALAR >::EMap& emap = EMap__(chain.first);

        if (emap.exists(chain.second->id())) {
          delete emap[chain.second->id()];
          emap[chain.second->id()] = e;
        } else {
          emap.insert(chain.second->id(), e);
        }

        evidenceAdded_(chain);
      } else {
        GUM_ERROR(NotFound,
                  "the given PRMAttribute does not belong to this "
                  "Instance<GUM_SCALAR>.");
      }
    }

checkElimOrder__()

template<typename GUM_SCALAR >

INLINE bool gum::prm::SVE< GUM_SCALAR >::checkElimOrder__ ( const PRMInstance< GUM_SCALAR > *  first, const PRMInstance< GUM_SCALAR > *  second  )

private

Returns true if second can be eliminated before first.

Definition at line 686 of file SVE_tpl.h.

References gum::prm::ParamScopeData< GUM_SCALAR >::ParamScopeData().

                                                {
      if (class_elim_order__ == 0) { initElimOrder__(); }

      auto first_name  = trim__(first->type().name());
      auto second_name = trim__(second->type().name());
      return (class_elim_order__->pos(first_name)
              <= class_elim_order__->pos(second_name));
    }

Here is the call graph for this function:

clearEvidence()

template<typename GUM_SCALAR >

void gum::prm::PRMInference< GUM_SCALAR >::clearEvidence ( )

inherited

Remove all evidences.

Definition at line 35 of file PRMInference_tpl.h.

                                                   {
      for (const auto& elt: evidences__) {
        for (const auto& elt2: *elt.second)
          delete elt2.second;

        delete elt.second;
      }

      evidences__.clear();
    }

eliminateDelayedVariables__()

template<typename GUM_SCALAR >

void gum::prm::SVE< GUM_SCALAR >::eliminateDelayedVariables__ ( const PRMInstance< GUM_SCALAR > *  i, BucketSet &  pool, BucketSet &  trash  )

private

Returns true if second can be eliminated before first.

Definition at line 218 of file SVE_tpl.h.

References gum::prm::ParamScopeData< GUM_SCALAR >::ParamScopeData().

                                               {
      Set< Potential< GUM_SCALAR >* > toRemove;

      for (const auto var: *delayedVariables__[i]) {
        MultiDimBucket< GUM_SCALAR >* bucket = new MultiDimBucket< GUM_SCALAR >();

        for (const auto pot: pool)
          if (pot->contains(*var)) {
            bucket->add(*pot);
            toRemove.insert(pot);
          }

        for (const auto pot: toRemove)
          pool.erase(pot);

        for (const auto other: bucket->allVariables())
          if (other != var) bucket->add(*other);

        Potential< GUM_SCALAR >* bucket_pot = new Potential< GUM_SCALAR >(bucket);
        trash.insert(bucket_pot);
        pool.insert(bucket_pot);
      }
    }

Here is the call graph for this function:

eliminateNodes__()

template<typename GUM_SCALAR >

void gum::prm::SVE< GUM_SCALAR >::eliminateNodes__ ( const PRMInstance< GUM_SCALAR > *  query, NodeId  id, BucketSet &  pool, BucketSet &  trash  )

private

Returns true if second can be eliminated before first.

Definition at line 127 of file SVE_tpl.h.

References gum::prm::ParamScopeData< GUM_SCALAR >::ParamScopeData().

                                                             {
      Set< const PRMInstance< GUM_SCALAR >* > ignore, eliminated;
      Set< NodeId >                           delayedVars;
      // Downward elimination
      List< const PRMInstance< GUM_SCALAR >* > elim_list;
      ignore.insert(query);

      for (auto iter = query->beginInvRef(); iter != query->endInvRef(); ++iter) {
        for (auto child = (*(iter.val())).begin(); child != (*(iter.val())).end();
             ++child) {
          if (!ignore.exists(child->first)) {
            eliminateNodesDownward__(query,
                                     child->first,
                                     pool,
                                     trash,
                                     elim_list,
                                     ignore,
                                     eliminated);
          } else if (!eliminated.exists(child->first)) {
            addDelayedVariable__(child->first, query, iter.key());
            delayedVars.insert(iter.key());
          }
        }
      }

      // Eliminating all nodes in query instance, except query
      InstanceBayesNet< GUM_SCALAR > bn(*query);
      DefaultTriangulation           t(&(bn.moralGraph()), &(bn.modalities()));
      std::vector< const DiscreteVariable* > elim_order;

      if (this->hasEvidence(query)) { insertEvidence__(query, pool); }

      for (auto attr = query->begin(); attr != query->end(); ++attr) {
        pool.insert(
           &(const_cast< Potential< GUM_SCALAR >& >((*(attr.val())).cpf())));
      }

      for (size_t idx = 0; idx < t.eliminationOrder().size(); ++idx) {
        if ((t.eliminationOrder()[idx] != node)
            && (!delayedVars.exists(t.eliminationOrder()[idx]))) {
          auto        var_id = t.eliminationOrder()[idx];
          const auto& var    = bn.variable(var_id);
          elim_order.push_back(&var);
        }
      }

      eliminateNodes(elim_order, pool, trash);

      // Eliminating delayed variables, if any
      if (delayedVariables__.exists(query)) {
        eliminateDelayedVariables__(query, pool, trash);
      }

      eliminated.insert(query);
      // Eliminating instance in elim_list
      List< const PRMInstance< GUM_SCALAR >* > tmp_list;

      while (!elim_list.empty()) {
        if (checkElimOrder__(query, elim_list.front())) {
          if (!ignore.exists(elim_list.front())) {
            eliminateNodesDownward__(query,
                                     elim_list.front(),
                                     pool,
                                     trash,
                                     elim_list,
                                     ignore,
                                     eliminated);
          }
        } else {
          tmp_list.insert(elim_list.front());
        }

        elim_list.popFront();
      }

      // Upward elimination
      for (const auto chain: query->type().slotChains())
        for (const auto parent: query->getInstances(chain->id()))
          if (!ignore.exists(parent))
            eliminateNodesUpward__(parent,
                                   pool,
                                   trash,
                                   tmp_list,
                                   ignore,
                                   eliminated);
    }

Here is the call graph for this function:

eliminateNodesDownward__()

template<typename GUM_SCALAR >

void gum::prm::SVE< GUM_SCALAR >::eliminateNodesDownward__ ( const PRMInstance< GUM_SCALAR > *  from, const PRMInstance< GUM_SCALAR > *  i, BucketSet &  pool, BucketSet &  trash, List< const PRMInstance< GUM_SCALAR > * > &  elim_list, Set< const PRMInstance< GUM_SCALAR > * > &  ignore, Set< const PRMInstance< GUM_SCALAR > * > &  eliminated  )

private

Returns true if second can be eliminated before first.

Definition at line 246 of file SVE_tpl.h.

References gum::prm::ParamScopeData< GUM_SCALAR >::ParamScopeData().

                                                             {
      Set< NodeId > delayedVars;
      ignore.insert(i);
      // Calling elimination over child instance
      List< const PRMInstance< GUM_SCALAR >* > my_list;

      for (auto iter = i->beginInvRef(); iter != i->endInvRef(); ++iter) {
        for (auto child = (*(iter.val())).begin(); child != (*(iter.val())).end();
             ++child) {
          if (!ignore.exists(child->first)) {
            eliminateNodesDownward__(i,
                                     child->first,
                                     pool,
                                     trash,
                                     my_list,
                                     ignore,
                                     eliminated);
          } else if (!eliminated.exists(child->first)) {
            addDelayedVariable__(child->first, i, iter.key());
            delayedVars.insert(iter.key());
          }
        }
      }

      // Eliminating all nodes in current instance
      variableElimination__(i,
                            pool,
                            trash,
                            (delayedVars.empty() ? 0 : &delayedVars));
      eliminated.insert(i);

      // Calling elimination over child's parents
      for (const auto node: my_list) {
        if (checkElimOrder__(i, node) && (node != from)) {
          if (!ignore.exists(node)) {
            eliminateNodesDownward__(i,
                                     node,
                                     pool,
                                     trash,
                                     elim_list,
                                     ignore,
                                     eliminated);
          }
        } else if (node != from) {
          elim_list.insert(node);
        }
      }

      // Adding parents instance to elim_list
      for (const auto chain: i->type().slotChains()) {
        for (const auto inst: i->getInstances(chain->id())) {
          if (inst != from) { elim_list.insert(inst); }
        }
      }
    }

Here is the call graph for this function:

eliminateNodesUpward__()

template<typename GUM_SCALAR >

void gum::prm::SVE< GUM_SCALAR >::eliminateNodesUpward__ ( const PRMInstance< GUM_SCALAR > *  i, BucketSet &  pool, BucketSet &  trash, List< const PRMInstance< GUM_SCALAR > * > &  elim_list, Set< const PRMInstance< GUM_SCALAR > * > &  ignore, Set< const PRMInstance< GUM_SCALAR > * > &  eliminated  )

private

Returns true if second can be eliminated before first.

Definition at line 353 of file SVE_tpl.h.

References gum::prm::ParamScopeData< GUM_SCALAR >::ParamScopeData().

                                                             {
      // Downward elimination
      ignore.insert(i);

      for (auto iter = i->beginInvRef(); iter != i->endInvRef(); ++iter) {
        for (auto child = (*(iter.val())).begin(); child != (*(iter.val())).end();
             ++child) {
          if (!ignore.exists(child->first)) {
            eliminateNodesDownward__(i,
                                     child->first,
                                     pool,
                                     trash,
                                     elim_list,
                                     ignore,
                                     eliminated);
          }
        }
      }

      // Eliminating all nodes in i instance
      variableElimination__(i, pool, trash);
      eliminated.insert(i);
      // Eliminating instance in elim_list
      List< const PRMInstance< GUM_SCALAR >* > tmp_list;

      while (!elim_list.empty()) {
        if (checkElimOrder__(i, elim_list.front())) {
          if (!ignore.exists(elim_list.front())) {
            eliminateNodesDownward__(i,
                                     elim_list.front(),
                                     pool,
                                     trash,
                                     elim_list,
                                     ignore,
                                     eliminated);
          }
        } else {
          tmp_list.insert(elim_list.front());
        }

        elim_list.popFront();
      }

      // Upward elimination
      for (const auto chain: i->type().slotChains()) {
        for (const auto parent: i->getInstances(chain->id())) {
          if (!ignore.exists(parent)) {
            eliminateNodesUpward__(parent,
                                   pool,
                                   trash,
                                   tmp_list,
                                   ignore,
                                   eliminated);
          }
        }
      }
    }

Here is the call graph for this function:

eliminateNodesWithEvidence__()

template<typename GUM_SCALAR >

void gum::prm::SVE< GUM_SCALAR >::eliminateNodesWithEvidence__ ( const PRMInstance< GUM_SCALAR > *  i, BucketSet &  pool, BucketSet &  trash, Set< NodeId > *  delayedVars = 0  )

private

Returns true if second can be eliminated before first.

Definition at line 418 of file SVE_tpl.h.

References gum::prm::ParamScopeData< GUM_SCALAR >::ParamScopeData().

                                                     {
      // First we check if evidences are on inner nodes
      bool inner = false;

      for (const auto& elt: this->evidence(i)) {
        inner = i->type().isInputNode(i->get(elt.first))
             || i->type().isInnerNode(i->get(elt.first));

        if (inner) { break; }
      }

      // Evidence on inner nodes
      if (inner) {
        BucketSet tmp_pool;
        insertEvidence__(i, tmp_pool);

        // We need a local to not eliminate queried inner nodes of the same
        // class
        for (const auto& elt: *i) {
          tmp_pool.insert(
             &(const_cast< Potential< GUM_SCALAR >& >(elt.second->cpf())));
        }

        InstanceBayesNet< GUM_SCALAR > bn(*i);
        DefaultTriangulation           t(&(bn.moralGraph()), &(bn.modalities()));
        const std::vector< NodeId >&   full_elim_order = t.eliminationOrder();
        // Removing Output nodes of elimination order
        std::vector< const DiscreteVariable* > inner_elim_order;
        std::vector< const DiscreteVariable* > output_elim_order;

        for (size_t idx = 0; idx < full_elim_order.size(); ++idx) {
          auto        var_id = full_elim_order[idx];
          const auto& var    = bn.variable(var_id);

          if (!i->type().isOutputNode(i->get(full_elim_order[idx]))) {
            inner_elim_order.push_back(&var);
          } else if (delayedVars != nullptr) {
            if (!delayedVars->exists(full_elim_order[idx])) {
              output_elim_order.push_back(&var);
            }
          } else {
            output_elim_order.push_back(&var);
          }
        }

        eliminateNodes(inner_elim_order, tmp_pool, trash);

        // Now we add the new potentials in pool and eliminate output nodes
        for (const auto pot: tmp_pool)
          pool.insert(pot);

        if (!output_elim_order.empty())
          eliminateNodes(output_elim_order, pool, trash);

      } else {
        InstanceBayesNet< GUM_SCALAR > bn(*i);
        insertEvidence__(i, pool);
        insertLiftedNodes__(i, pool, trash);

        for (const auto agg: i->type().aggregates())
          pool.insert(getAggPotential__(i, agg));

        try {
          std::vector< const DiscreteVariable* > elim;

          for (auto iter = getElimOrder__(i->type()).begin();
               iter != getElimOrder__(i->type()).end();
               ++iter) {
            const auto& var = bn.variable(*iter);
            if (delayedVars != nullptr) {
              if (!delayedVars->exists(*iter)) { elim.push_back(&var); }
            } else {
              elim.push_back(&var);
            }
          }

          eliminateNodes(elim, pool, trash);
        } catch (NotFound&) {
          GUM_ERROR(FatalError, "there should be at least one node here.");
        }
      }
    }

Here is the call graph for this function:

evidence() [1/4]

template<typename GUM_SCALAR>

INLINE PRMInference< GUM_SCALAR >::EMap & gum::prm::PRMInference< GUM_SCALAR >::evidence ( const PRMInstance< GUM_SCALAR > &  i )

inherited

Returns EMap of evidences over i.

Exceptions

NotFound

if i has no evidence.

Definition at line 156 of file PRMInference_tpl.h.

                                                                              {
      try {
        return *(evidences__[&i]);
      } catch (NotFound&) {
        GUM_ERROR(NotFound, "this instance has no evidence.");
      }
    }

evidence() [2/4]

template<typename GUM_SCALAR>

INLINE PRMInference< GUM_SCALAR >::EMap & gum::prm::PRMInference< GUM_SCALAR >::evidence ( const PRMInstance< GUM_SCALAR > *  i )

inherited

Returns EMap of evidences over i.

Exceptions

NotFound

if i has no evidence.

Definition at line 177 of file PRMInference_tpl.h.

                                                                              {
      try {
        return *(evidences__[i]);
      } catch (NotFound&) {
        GUM_ERROR(NotFound, "this instance has no evidence.");
      }
    }

evidence() [3/4]

template<typename GUM_SCALAR>

INLINE const PRMInference< GUM_SCALAR >::EMap & gum::prm::PRMInference< GUM_SCALAR >::evidence ( const PRMInstance< GUM_SCALAR > &  i ) const

inherited

Returns EMap of evidences over i.

Exceptions

NotFound

if i has no evidence.

Definition at line 166 of file PRMInference_tpl.h.

                                                    {
      try {
        return *(evidences__[&i]);
      } catch (NotFound&) {
        GUM_ERROR(NotFound, "this instance has no evidence.");
      }
    }

evidence() [4/4]

template<typename GUM_SCALAR>

INLINE const PRMInference< GUM_SCALAR >::EMap & gum::prm::PRMInference< GUM_SCALAR >::evidence ( const PRMInstance< GUM_SCALAR > *  i ) const

inherited

Returns EMap of evidences over i.

Exceptions

NotFound

if i has no evidence.

Definition at line 187 of file PRMInference_tpl.h.

                                                    {
      try {
        return *(evidences__[i]);
      } catch (NotFound&) {
        GUM_ERROR(NotFound, "this instance has no evidence.");
      }
    }

evidenceAdded_()

template<typename GUM_SCALAR >

INLINE void gum::prm::SVE< GUM_SCALAR >::evidenceAdded_ ( const Chain &  chain )

protectedvirtual

See PRMInference<GUM_SCALAR>::evidenceAdded_().

Implements gum::prm::PRMInference< GUM_SCALAR >.

Definition at line 705 of file SVE_tpl.h.

                                                                    {
      // Do nothing
    }

evidenceRemoved_()

template<typename GUM_SCALAR >

INLINE void gum::prm::SVE< GUM_SCALAR >::evidenceRemoved_ ( const Chain &  chain )

protectedvirtual

See PRMInference<GUM_SCALAR>::evidenceRemoved_().

Implements gum::prm::PRMInference< GUM_SCALAR >.

Definition at line 710 of file SVE_tpl.h.

                                                                      {
      // Do nothing
    }

getAggPotential__()

template<typename GUM_SCALAR >

INLINE Potential< GUM_SCALAR > * gum::prm::SVE< GUM_SCALAR >::getAggPotential__ ( const PRMInstance< GUM_SCALAR > *  i, const PRMAggregate< GUM_SCALAR > *  agg  )

private

Returns true if second can be eliminated before first.

Definition at line 698 of file SVE_tpl.h.

References gum::prm::ParamScopeData< GUM_SCALAR >::ParamScopeData().

                                              {
      return &(const_cast< Potential< GUM_SCALAR >& >(i->get(agg->id()).cpf()));
    }

Here is the call graph for this function:

getElimOrder__()

template<typename GUM_SCALAR >

INLINE std::vector< NodeId > & gum::prm::SVE< GUM_SCALAR >::getElimOrder__ ( const PRMClass< GUM_SCALAR > &  c )

private

Returns true if second can be eliminated before first.

Definition at line 674 of file SVE_tpl.h.

References gum::prm::ParamScopeData< GUM_SCALAR >::ParamScopeData().

                                                                            {
      return *(elim_orders__[&c]);
    }

Here is the call graph for this function:

hasEvidence() [1/4]

template<typename GUM_SCALAR>

INLINE bool gum::prm::PRMInference< GUM_SCALAR >::hasEvidence ( const PRMInstance< GUM_SCALAR > &  i ) const

inherited

Returns true if i has evidence.

Definition at line 197 of file PRMInference_tpl.h.

                                                 {
      return evidences__.exists(&i);
    }

hasEvidence() [2/4]

template<typename GUM_SCALAR>

INLINE bool gum::prm::PRMInference< GUM_SCALAR >::hasEvidence ( const PRMInstance< GUM_SCALAR > *  i ) const

inherited

Returns EMap of evidences over i.

Definition at line 203 of file PRMInference_tpl.h.

                                                 {
      return evidences__.exists(i);
    }

hasEvidence() [3/4]

template<typename GUM_SCALAR>

INLINE bool gum::prm::PRMInference< GUM_SCALAR >::hasEvidence ( const Chain &  chain ) const

inherited

Returns true if i has evidence on PRMAttribute<GUM_SCALAR> a.

Definition at line 209 of file PRMInference_tpl.h.

                                                                                {
      return (hasEvidence(chain.first))
              ? evidence(chain.first).exists(chain.second->id())
              : false;
    }

hasEvidence() [4/4]

template<typename GUM_SCALAR>

INLINE bool gum::prm::PRMInference< GUM_SCALAR >::hasEvidence ( ) const

inherited

Returns true if i has evidence on PRMAttribute<GUM_SCALAR> a.

Definition at line 216 of file PRMInference_tpl.h.

                                                              {
      return (evidences__.size() != (Size)0);
    }

initElimOrder__()

template<typename GUM_SCALAR >

void gum::prm::SVE< GUM_SCALAR >::initElimOrder__ ( )

private

Returns true if second can be eliminated before first.

Definition at line 581 of file SVE_tpl.h.

References gum::prm::ParamScopeData< GUM_SCALAR >::ParamScopeData().

                                            {
      ClassDependencyGraph< GUM_SCALAR >                        cdg(*(this->prm_));
      Sequence< const PRMClassElementContainer< GUM_SCALAR >* > class_elim_order;
      std::list< NodeId >                                       l;

      for (const auto node: cdg.dag().nodes()) {
        if (cdg.dag().parents(node).empty()) { l.push_back(node); }
      }

      Set< NodeId > visited_node;

      while (!l.empty()) {
        visited_node.insert(l.front());

        if (!class_elim_order.exists(cdg.get(l.front()).first)) {
          class_elim_order.insert(cdg.get(l.front()).first);
        }

        for (const auto child: cdg.dag().children(l.front())) {
          if (!visited_node.contains(child)) { l.push_back(child); }
        }

        l.pop_front();
      }

      class_elim_order__ = new Sequence< std::string >();
      for (auto c: class_elim_order) {
        std::string name = c->name();
        auto        pos  = name.find_first_of("<");
        if (pos != std::string::npos) { name = name.substr(0, pos); }
        try {
          class_elim_order__->insert(name);
        } catch (DuplicateElement&) {}
      }
    }

Here is the call graph for this function:

initLiftedNodes__()

template<typename GUM_SCALAR >

void gum::prm::SVE< GUM_SCALAR >::initLiftedNodes__ ( const PRMClass< GUM_SCALAR > &  c )

private

Returns true if second can be eliminated before first.

Definition at line 526 of file SVE_tpl.h.

References gum::prm::ParamScopeData< GUM_SCALAR >::ParamScopeData().

                                                                             {
      BucketSet* lifted_pool = new BucketSet();
      lifted_pools__.insert(&c, lifted_pool);
      NodeSet inners, outers;

      for (const auto node: c.containerDag().nodes())
        if (PRMClassElement< GUM_SCALAR >::isAttribute(c.get(node))) {
          if (c.isOutputNode(c.get(node)))
            outers.insert(node);
          else if (!outers.exists(node))
            inners.insert(node);

          lifted_pool->insert(
             const_cast< Potential< GUM_SCALAR >* >(&(c.get(node).cpf())));
        } else if (PRMClassElement< GUM_SCALAR >::isAggregate(c.get(node))) {
          outers.insert(node);

          // We need to put in the output_elim_order aggregator's parents which
          // are
          // innner nodes
          for (const auto par: c.containerDag().parents(node))
            if (PRMClassElement< GUM_SCALAR >::isAttribute(c.get(par))
                && c.isInnerNode(c.get(par))) {
              inners.erase(par);
              outers.insert(par);
            }
        }

      // Now we proceed with the elimination of inner attributes
      ClassBayesNet< GUM_SCALAR > bn(c);
      List< NodeSet >             partial_ordering;

      if (inners.size()) partial_ordering.push_back(inners);

      if (outers.size()) partial_ordering.push_back(outers);

      PartialOrderedTriangulation t(&(bn.moralGraph()),
                                    &(bn.modalities()),
                                    &partial_ordering);

      for (size_t idx = 0; idx < inners.size(); ++idx)
        eliminateNode(&(c.get(t.eliminationOrder()[idx]).type().variable()),
                      *lifted_pool,
                      lifted_trash__);

      // If there is not only inner and input Attributes
      if (outers.size()) {
        elim_orders__.insert(
           &c,
           new std::vector< NodeId >(t.eliminationOrder().begin() + inners.size(),
                                     t.eliminationOrder().end()));
      }
    }

Here is the call graph for this function:

insertEvidence__()

template<typename GUM_SCALAR >

INLINE void gum::prm::SVE< GUM_SCALAR >::insertEvidence__ ( const PRMInstance< GUM_SCALAR > *  i, BucketSet &  pool  )

private

Returns true if second can be eliminated before first.

Definition at line 666 of file SVE_tpl.h.

References gum::prm::ParamScopeData< GUM_SCALAR >::ParamScopeData().

                                                                                  {
      for (const auto& elt: this->evidence(i))
        pool.insert(const_cast< Potential< GUM_SCALAR >* >(elt.second));
    }

Here is the call graph for this function:

insertLiftedNodes__()

template<typename GUM_SCALAR >

void gum::prm::SVE< GUM_SCALAR >::insertLiftedNodes__ ( const PRMInstance< GUM_SCALAR > *  i, BucketSet &  pool, BucketSet &  trash  )

private

Returns true if second can be eliminated before first.

Definition at line 506 of file SVE_tpl.h.

References gum::prm::ParamScopeData< GUM_SCALAR >::ParamScopeData().

                                                                  {
      SVE< GUM_SCALAR >::BucketSet* lifted_pool = 0;

      try {
        lifted_pool = lifted_pools__[&(i->type())];
      } catch (NotFound&) {
        initLiftedNodes__(i->type());
        lifted_pool = lifted_pools__[&(i->type())];
      }

      for (const auto lifted_pot: *lifted_pool) {
        Potential< GUM_SCALAR >* pot = copyPotential(i->bijection(), *lifted_pot);
        pool.insert(pot);
        trash.insert(pot);
      }
    }

Here is the call graph for this function:

joint()

template<typename GUM_SCALAR>

INLINE void gum::prm::PRMInference< GUM_SCALAR >::joint ( const std::vector< Chain > &  chains, Potential< GUM_SCALAR > &  j  )

inherited

Compute the joint probability of the formals attributes pointed by chains and stores it in m.

Parameters

chains	A Set of strings of the form instance.attribute.
j	An empty CPF which will be filed by the joint probability over chains.

Exceptions

NotFound	Raised if some chain in chains does not point to a formal attribute.
OperationNotAllowed	Raise if m is not empty.

Definition at line 264 of file PRMInference_tpl.h.

                                                                           {
      if (j.nbrDim() > 0) {
        GUM_ERROR(OperationNotAllowed, "the given Potential is not empty.");
      }

      for (auto chain = chains.begin(); chain != chains.end(); ++chain) {
        j.add(chain->second->type().variable());
      }

      joint_(chains, j);
    }

joint_()

template<typename GUM_SCALAR >

void gum::prm::SVE< GUM_SCALAR >::joint_ ( const std::vector< Chain > &  queries, Potential< GUM_SCALAR > &  j  )

protectedvirtual

See PRMInference<GUM_SCALAR>::joint_().

Implements gum::prm::PRMInference< GUM_SCALAR >.

Definition at line 651 of file SVE_tpl.h.

References gum::prm::ParamScopeData< GUM_SCALAR >::ParamScopeData().

                                                                  {
      GUM_ERROR(FatalError, "Not implemented.");
    }

Here is the call graph for this function:

name()

template<typename GUM_SCALAR >

INLINE std::string gum::prm::SVE< GUM_SCALAR >::name ( ) const

virtual

Returns the name of the current inference algorithm.

Implements gum::prm::PRMInference< GUM_SCALAR >.

Definition at line 739 of file SVE_tpl.h.

                                                   {
      return "SVE";
    }

posterior()

template<typename GUM_SCALAR>

INLINE void gum::prm::PRMInference< GUM_SCALAR >::posterior ( const Chain &  chain, Potential< GUM_SCALAR > &  m  )

inherited

Compute the posterior of the formal attribute pointed by chain and stores it in m.

Parameters

chain	A string of the form instance.attribute.
m	An empty CPF which will be filed by the posterior of chain.

Exceptions

NotFound	Raised if chain is invalid.
TypeError	Raised if chain does not point to an PRMAttribute<GUM_SCALAR>.
OperationNotAllowed	Raise if m is not empty.

Definition at line 234 of file PRMInference_tpl.h.

                                                            {
      if (m.nbrDim() > 0) {
        GUM_ERROR(OperationNotAllowed, "the given Potential is not empty.");
      }

      if (hasEvidence(chain)) {
        m.add(chain.second->type().variable());
        const Potential< GUM_SCALAR >& e
           = *(evidence(chain.first)[chain.second->id()]);
        Instantiation i(m), j(e);

        for (i.setFirst(), j.setFirst(); !i.end(); i.inc(), j.inc())
          m.set(i, e.get(j));
      } else {
        if (chain.second != &(chain.first->get(chain.second->safeName()))) {
          typename PRMInference< GUM_SCALAR >::Chain good_chain
             = std::make_pair(chain.first,
                              &(chain.first->get(chain.second->safeName())));
          m.add(good_chain.second->type().variable());
          posterior_(good_chain, m);
        } else {
          m.add(chain.second->type().variable());
          posterior_(chain, m);
        }
      }
    }

posterior_()

template<typename GUM_SCALAR >

void gum::prm::SVE< GUM_SCALAR >::posterior_ ( const Chain &  chain, Potential< GUM_SCALAR > &  m  )

protectedvirtual

See PRMInference<GUM_SCALAR>::posterior_().

Implements gum::prm::PRMInference< GUM_SCALAR >.

Definition at line 618 of file SVE_tpl.h.

References gum::prm::ParamScopeData< GUM_SCALAR >::ParamScopeData().

                                                                   {
      const PRMInstance< GUM_SCALAR >*  i   = chain.first;
      const PRMAttribute< GUM_SCALAR >* elt = chain.second;
      SVE< GUM_SCALAR >::BucketSet      pool, trash;

      eliminateNodes__(i, elt->id(), pool, trash);

      std::vector< Potential< GUM_SCALAR >* > result;

      for (const auto pot: pool) {
        if (pot->contains(elt->type().variable())) { result.push_back(pot); }
      }

      while (result.size() > 1) {
        auto& p1 = *(result.back());
        result.pop_back();
        auto& p2 = *(result.back());
        result.pop_back();
        auto mult = new Potential< GUM_SCALAR >(p1 * p2);
        trash.insert(mult);
        result.push_back(mult);
      }

      m = *(result.back());
      m.normalize();

      for (const auto pot: trash) {
        delete pot;
      }
    }

Here is the call graph for this function:

removeEvidence()

template<typename GUM_SCALAR >

INLINE void gum::prm::PRMInference< GUM_SCALAR >::removeEvidence ( const Chain &  chain )

inherited

Remove evidence on the given instance's elt.

Parameters

chain

The variable being observed.

Exceptions

NotFound	Raised if the given names are not found.
TypeError	Raised if the elt is not an PRMAttribute<GUM_SCALAR>.

Definition at line 221 of file PRMInference_tpl.h.

                                                                             {
      try {
        if (EMap__(chain.first).exists(chain.second->id())) {
          evidenceRemoved_(chain);
          delete EMap__(chain.first)[chain.second->id()];
          EMap__(chain.first).erase(chain.second->id());
        }
      } catch (NotFound&) {
        // Ok, we are only removing
      }
    }

trim__()

template<typename GUM_SCALAR >

INLINE std::string gum::prm::SVE< GUM_SCALAR >::trim__ ( const std::string &  s )

private

Returns true if second can be eliminated before first.

Definition at line 679 of file SVE_tpl.h.

References gum::prm::ParamScopeData< GUM_SCALAR >::ParamScopeData().

                                                                 {
      auto pos = s.find_first_of("<");
      if (pos != std::string::npos) { return s.substr(0, pos); }
      return s;
    }

Here is the call graph for this function:

variableElimination__()

template<typename GUM_SCALAR >

void gum::prm::SVE< GUM_SCALAR >::variableElimination__ ( const PRMInstance< GUM_SCALAR > *  i, BucketSet &  pool, BucketSet &  trash, Set< NodeId > *  delayedVars = 0  )

private

Returns true if second can be eliminated before first.

Definition at line 311 of file SVE_tpl.h.

References gum::prm::ParamScopeData< GUM_SCALAR >::ParamScopeData().

                                                                            {
      if (this->hasEvidence(i)) {
        eliminateNodesWithEvidence__(i, pool, trash, delayedVars);
      } else {
        insertLiftedNodes__(i, pool, trash);

        for (const auto agg: i->type().aggregates())
          pool.insert(getAggPotential__(i, agg));

        try {
          InstanceBayesNet< GUM_SCALAR > bn(*i);

          std::vector< const DiscreteVariable* > elim;

          for (const auto node: getElimOrder__(i->type())) {
            const auto& var = bn.variable(node);
            if (delayedVars != nullptr) {
              if (!delayedVars->exists(node)) {
                const auto& var = bn.variable(node);
                elim.push_back(&var);
              }
            } else {
              elim.push_back(&var);
            }
          }

          eliminateNodes(elim, pool, trash);
        } catch (NotFound&) {
          // Raised if there is no inner nodes to eliminate
        }
      }

      // Eliminating delayed variables, if any
      if (delayedVariables__.exists(i)) {
        eliminateDelayedVariables__(i, pool, trash);
      }
    }

Here is the call graph for this function:

Member Data Documentation

class_elim_order__

template<typename GUM_SCALAR >

Sequence< std::string >* gum::prm::SVE< GUM_SCALAR >::class_elim_order__

private

Definition at line 127 of file SVE.h.

delayedVariables__

template<typename GUM_SCALAR >

HashTable< const PRMInstance< GUM_SCALAR >*, Set< const DiscreteVariable* >* > gum::prm::SVE< GUM_SCALAR >::delayedVariables__

private

Definition at line 131 of file SVE.h.

delayedVariablesCounters__

template<typename GUM_SCALAR >

HashTable< std::string, Size > gum::prm::SVE< GUM_SCALAR >::delayedVariablesCounters__

private

Some variable must be delayed for more than one PRMInstance<GUM_SCALAR>, when the delayed variable counter reach 0 it can be eliminated.

Definition at line 138 of file SVE.h.

elim_orders__

template<typename GUM_SCALAR >

HashTable< const PRMClass< GUM_SCALAR >*, std::vector< NodeId >* > gum::prm::SVE< GUM_SCALAR >::elim_orders__

private

Definition at line 123 of file SVE.h.

lifted_pools__

template<typename GUM_SCALAR >

HashTable< const PRMClass< GUM_SCALAR >*, BucketSet* > gum::prm::SVE< GUM_SCALAR >::lifted_pools__

private

Definition at line 125 of file SVE.h.

lifted_trash__

template<typename GUM_SCALAR >

BucketSet gum::prm::SVE< GUM_SCALAR >::lifted_trash__

private

Definition at line 140 of file SVE.h.

prm_

template<typename GUM_SCALAR>

PRM< GUM_SCALAR > const* gum::prm::PRMInference< GUM_SCALAR >::prm_

protectedinherited

The PRM<GUM_SCALAR> on which inference is done.

Definition at line 213 of file PRMInference.h.

sys_

template<typename GUM_SCALAR>

PRMSystem< GUM_SCALAR > const* gum::prm::PRMInference< GUM_SCALAR >::sys_

protectedinherited

The Model on which inference is done.

Definition at line 216 of file PRMInference.h.

---

The documentation for this class was generated from the following files:

• agrum/PRM/inference/SVE.h
• agrum/PRM/inference/SVE_tpl.h