iti_tpl.h

Go to the documentation of this file.

/*********************************************************************************
 * Copyright (C) 2005 by Pierre-Henri WUILLEMIN et Christophe GONZALES *
 * {prenom.nom}_at_lip6.fr *
 *                                                                               *
 * This program is free software; you can redistribute it and/or modify *
 * it under the terms of the GNU General Public License as published by *
 * the Free Software Foundation; either version 2 of the License, or *
 * (at your option) any later version. *
 *                                                                               *
 * This program is distributed in the hope that it will be useful, *
 * but WITHOUT ANY WARRANTY; without even the implied warranty of *
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the *
 * GNU General Public License for more details. *
 *                                                                               *
 * You should have received a copy of the GNU General Public License *
 * along with this program; if not, write to the *
 * Free Software Foundation, Inc., *
 * 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. *
 *********************************************************************************/
// =======================================================
#include <agrum/core/math/math.h>
#include <agrum/core/priorityQueue.h>
#include <agrum/core/types.h>
// =======================================================
#include <agrum/FMDP/learning/core/chiSquare.h>
#include <agrum/FMDP/learning/datastructure/iti.h>
// =======================================================
#include <agrum/variables/labelizedVariable.h>
// =======================================================


namespace gum {

  // ==========================================================================
  // ==========================================================================

  // ###################################################################
  // ###################################################################
  template < TESTNAME AttributeSelection, bool isScalar >
  ITI< AttributeSelection, isScalar >::ITI(
     MultiDimFunctionGraph< double >* target,
     double                           attributeSelectionThreshold,
     Set< const DiscreteVariable* >   attributeListe,
     const DiscreteVariable*          learnedValue) :
      IncrementalGraphLearner< AttributeSelection, isScalar >(
         target, attributeListe, learnedValue),
      __nbTotalObservation(0),
      __attributeSelectionThreshold(attributeSelectionThreshold) {
    GUM_CONSTRUCTOR(ITI);
    __staleTable.insert(this->_root, false);
  }

  // ###################################################################
  // ###################################################################
  template < TESTNAME AttributeSelection, bool isScalar >
  ITI< AttributeSelection, isScalar >::ITI(
     MultiDimFunctionGraph< double >* target,
     double                           attributeSelectionThreshold,
     Set< const DiscreteVariable* >   attributeListe) :
      IncrementalGraphLearner< AttributeSelection, isScalar >(
         target, attributeListe, new LabelizedVariable("Reward", "", 2)),
      __nbTotalObservation(0),
      __attributeSelectionThreshold(attributeSelectionThreshold) {
    GUM_CONSTRUCTOR(ITI);
    __staleTable.insert(this->_root, false);
  }


  // ==========================================================================
  // ==========================================================================

  // ############################################################################
  // ############################################################################
  template < TESTNAME AttributeSelection, bool isScalar >
  void
     ITI< AttributeSelection, isScalar >::addObservation(const Observation* obs) {
    __nbTotalObservation++;
    IncrementalGraphLearner< AttributeSelection, isScalar >::addObservation(obs);
  }

  // ############################################################################
  // ############################################################################
  template < TESTNAME AttributeSelection, bool isScalar >
  void ITI< AttributeSelection, isScalar >::_updateNodeWithObservation(
     const Observation* newObs, NodeId currentNodeId) {
    IncrementalGraphLearner< AttributeSelection,
                             isScalar >::_updateNodeWithObservation(newObs,
                                                                    currentNodeId);
    __staleTable[currentNodeId] = true;
  }


  // ============================================================================
  // ============================================================================

  // ############################################################################
  // ############################################################################
  template < TESTNAME AttributeSelection, bool isScalar >
  void ITI< AttributeSelection, isScalar >::updateGraph() {
    std::vector< NodeId > filo;
    filo.push_back(this->_root);
    HashTable< NodeId, Set< const DiscreteVariable* >* > potentialVars;
    potentialVars.insert(this->_root,
                         new Set< const DiscreteVariable* >(this->_setOfVars));


    while (!filo.empty()) {
      NodeId currentNodeId = filo.back();
      filo.pop_back();

      // First we look for the best var to install on the node
      double                         bestValue = __attributeSelectionThreshold;
      Set< const DiscreteVariable* > bestVars;

      for (auto varIter = potentialVars[currentNodeId]->cbeginSafe();
           varIter != potentialVars[currentNodeId]->cendSafe();
           ++varIter)
        if (this->_nodeId2Database[currentNodeId]->isTestRelevant(*varIter)) {
          double varValue =
             this->_nodeId2Database[currentNodeId]->testValue(*varIter);
          if (varValue >= bestValue) {
            if (varValue > bestValue) {
              bestValue = varValue;
              bestVars.clear();
            }
            bestVars.insert(*varIter);
          }
        }

      // Then We installed Variable a test on that node
      this->_updateNode(currentNodeId, bestVars);

      // The we move on the children if needed
      if (this->_nodeVarMap[currentNodeId] != this->_value) {
        for (Idx moda = 0; moda < this->_nodeVarMap[currentNodeId]->domainSize();
             moda++) {
          Set< const DiscreteVariable* >* itsPotentialVars =
             new Set< const DiscreteVariable* >(*potentialVars[currentNodeId]);
          itsPotentialVars->erase(this->_nodeVarMap[currentNodeId]);
          NodeId sonId = this->_nodeSonsMap[currentNodeId][moda];
          if (__staleTable[sonId]) {
            filo.push_back(sonId);
            potentialVars.insert(sonId, itsPotentialVars);
          }
        }
      }
    }

    for (HashTableIteratorSafe< NodeId, Set< const DiscreteVariable* >* >
            nodeIter = potentialVars.beginSafe();
         nodeIter != potentialVars.endSafe();
         ++nodeIter)
      delete nodeIter.val();
  }


  // ############################################################################
  // ############################################################################
  template < TESTNAME AttributeSelection, bool isScalar >
  NodeId ITI< AttributeSelection, isScalar >::_insertNode(
     NodeDatabase< AttributeSelection, isScalar >* nDB,
     const DiscreteVariable*                       boundVar) {
    NodeId n =
       IncrementalGraphLearner< AttributeSelection, isScalar >::_insertNode(
          nDB, boundVar);
    __staleTable.insert(n, true);
    return n;
  }


  // ############################################################################
  // ############################################################################
  template < TESTNAME AttributeSelection, bool isScalar >
  void ITI< AttributeSelection, isScalar >::_chgNodeBoundVar(
     NodeId currentNodeId, const DiscreteVariable* desiredVar) {
    if (this->_nodeVarMap[currentNodeId] != desiredVar) {
      __staleTable[currentNodeId] = true;
      IncrementalGraphLearner< AttributeSelection, isScalar >::_chgNodeBoundVar(
         currentNodeId, desiredVar);
    }
  }


  // ############################################################################
  // ############################################################################
  template < TESTNAME AttributeSelection, bool isScalar >
  void ITI< AttributeSelection, isScalar >::_removeNode(NodeId currentNodeId) {
    IncrementalGraphLearner< AttributeSelection, isScalar >::_removeNode(
       currentNodeId);
    __staleTable.erase(currentNodeId);
  }


  // ============================================================================
  // ============================================================================

  // ############################################################################
  // ############################################################################
  template < TESTNAME AttributeSelection, bool isScalar >
  void ITI< AttributeSelection, isScalar >::updateFunctionGraph() {
    this->_target->clear();
    this->_target->manager()->setRootNode(
       this->__insertNodeInFunctionGraph(this->_root));
  }


  // ############################################################################
  // ############################################################################
  template < TESTNAME AttributeSelection, bool isScalar >
  NodeId ITI< AttributeSelection, isScalar >::__insertNodeInFunctionGraph(
     NodeId currentNodeId) {
    if (this->_nodeVarMap[currentNodeId] == this->_value) {
      NodeId nody = __insertTerminalNode(currentNodeId);
      return nody;
    }

    if (!this->_target->variablesSequence().exists(
           this->_nodeVarMap[currentNodeId])) {
      this->_target->add(*(this->_nodeVarMap[currentNodeId]));
    }

    NodeId nody =
       this->_target->manager()->addInternalNode(this->_nodeVarMap[currentNodeId]);
    for (Idx moda = 0; moda < this->_nodeVarMap[currentNodeId]->domainSize();
         ++moda) {
      NodeId son = this->__insertNodeInFunctionGraph(
         this->_nodeSonsMap[currentNodeId][moda]);
      this->_target->manager()->setSon(nody, moda, son);
    }

    return nody;
  }


  // ############################################################################
  // ############################################################################
  template < TESTNAME AttributeSelection, bool isScalar >
  NodeId ITI< AttributeSelection, isScalar >::__insertTerminalNode(
     NodeId currentNodeId, Int2Type< false >) {
    if (!this->_target->variablesSequence().exists(this->_value))
      this->_target->add(*(this->_value));

    Size tot = this->_nodeId2Database[currentNodeId]->nbObservation();
    if (tot == Size(0)) return this->_target->manager()->addTerminalNode(0.0);

    NodeId* sonsMap = static_cast< NodeId* >(
       SOA_ALLOCATE(sizeof(NodeId) * this->_value->domainSize()));
    for (Idx modality = 0; modality < this->_value->domainSize(); ++modality) {
      double newVal = 0.0;
      newVal = (double)this->_nodeId2Database[currentNodeId]->effectif(modality)
               / (double)tot;
      sonsMap[modality] = this->_target->manager()->addTerminalNode(newVal);
    }
    NodeId nody = this->_target->manager()->addInternalNode(this->_value, sonsMap);
    return nody;
  }


  // ############################################################################
  // ############################################################################
  template < TESTNAME AttributeSelection, bool isScalar >
  NodeId ITI< AttributeSelection, isScalar >::__insertTerminalNode(
     NodeId currentNodeId, Int2Type< true >) {
    double value = 0.0;
    for (auto valIter = this->_nodeId2Database[currentNodeId]->cbeginValues();
         valIter != this->_nodeId2Database[currentNodeId]->cendValues();
         ++valIter) {
      value += (double)valIter.key() * valIter.val();
    }
    if (this->_nodeId2Database[currentNodeId]->nbObservation())
      value /= (double)this->_nodeId2Database[currentNodeId]->nbObservation();
    NodeId nody = this->_target->manager()->addTerminalNode(value);
    return nody;
  }
}   // namespace gum