network.cpp

基于稀疏网络的精选机器学习模型

//===========================================================
//=     University of Illinois at Urbana-Champaign          =
//=     Department of Computer Science                      =
//=     Dr. Dan Roth - Cognitive Computation Group          =
//=                                                         =
//=  Project: SNoW                                          =
//=                                                         =
//=   Module: Network.cpp                                   =
//=  Version: 3.2.0                                         =
//=  Authors: Jeff Rosen, Andrew Carlson, Nick Rizzolo      =
//=     Date: xx/xx/99                                      =
//=                                                         =
//= Comments:                                               =
//===========================================================

//#define TRAIN_WITH_NORMALIZED_ACTIVATION
// Uncomment the previous line if you want the constraint classification
// decision to be based on normalized activations as opposed to regular
// activations.  By default, the line is commented.

#define INITIAL_WEIGHT_FACTOR 3

#include "GlobalParams.h"
#include "Network.h"
#include "Winnow.h"
#include "Perceptron.h"
#include "NaiveBayes.h"
#include "Cloud.h"
#include <string>
#include <typeinfo>
#include <algorithm>
#include <float.h>

bool Network::CreateStructure()
{
  bool result = true;

  char* networkSpec =
    new char[globalParams.algorithmSpecification.length() + 1];
  if (networkSpec != NULL)
  {
    // Make a working copy
    strcpy(networkSpec, globalParams.algorithmSpecification.c_str());
    if (globalParams.verbosity != VERBOSE_QUIET)
      cout << "Network Spec -> " << networkSpec << endl;

    char* token = strtok(networkSpec, ":(, \t\n\r");
    char* delim;
    int index = 0;

    while (token != NULL)
    {
      // token must now be an algorithm type
      if (tolower(*token) == 'w')
      {
        double alpha = 1.35;
        double beta = 0.8;
        double threshold = 4.0;
#ifdef AVERAGE_EXAMPLE_SIZE
        double defaultWeight = (globalParams.rawMode)
                                 ? 1
                                 : (INITIAL_WEIGHT_FACTOR * threshold
                                     / globalParams.averageExampleSize);
#else
        double defaultWeight = (globalParams.rawMode)
                                 ? 1
                                 : (INITIAL_WEIGHT_FACTOR * threshold
                                     / globalParams.maxExampleSize);
#endif

        token = token + strlen(token) + 1;

        // if only a target set is specified, keep defaults
        if ((*token) == ':') delim = token;
        else
        {
          // look for commas to see what parameters the user gave
          alpha = strtod(token, &delim);
          token = delim + strspn(delim, ":, \t\n\r");
          beta = strtod(token, &delim);

          if (*delim == ',')
          {
            token = delim + strspn(delim, ":, \t\n\r");
            threshold = strtod(token, &delim);

            if (*delim == ',')
            {
              token = delim + strspn(delim, ":, \t\n\r");
              defaultWeight = strtod(token, &delim);
            }
#ifdef AVERAGE_EXAMPLE_SIZE
            else
              defaultWeight = (globalParams.rawMode)
                               ? 1
                               : (INITIAL_WEIGHT_FACTOR * threshold
                                   / globalParams.averageExampleSize);
#else
            else
              defaultWeight = (globalParams.rawMode)
                               ? 1
                               : (INITIAL_WEIGHT_FACTOR * threshold
                                   / globalParams.maxExampleSize);
#endif
          }
        }

        // make sure a target set was specified
        if (*delim == ':')
        {
          token = delim + strspn(delim, ":, \t\n\r");
          if (*token == ')')
          {
            cerr << "Error: No target IDs specified for Winnow.\n";
            return false;
          }

          token = strtok(token, ")");
          delim += strlen(token) + 2;
        }
        else
        {
          delim += strspn(delim, ":) \t\n\r");
          cerr << "Error: No target set given for Winnow.\n";
          return false;
        }

        if (*delim == ',')
        {
          Winnow* pWin = new Winnow(globalParams, alpha, beta, threshold, 
				    defaultWeight);
          pWin->targetIds.Parse(token);
          pWin->index = index;

          algorithms.push_back(pWin);
        }
        else
        {
          delim = token;
          token = strtok(NULL, ")");
          cerr << "Failed to parse Winnow spec '" << delim << '(' << token
               << ")'\n\n";
          result = false;
        }
      }
      else if (tolower(*token) == 'p')
      {
        token = token + strlen(token) + 1;

        double learningRate = 0.1;
        double threshold = 4.0;
#ifdef AVERAGE_EXAMPLE_SIZE
        double defaultWeight = (globalParams.rawMode)
                                ? 0
                                : (INITIAL_WEIGHT_FACTOR * threshold
                                    / globalParams.averageExampleSize);
#else
        double defaultWeight = (globalParams.rawMode)
                                ? 0
                                : (INITIAL_WEIGHT_FACTOR * threshold
                                    / globalParams.maxExampleSize);
#endif

        if ((*token) == ':') delim = token;
        else
        {
          learningRate = strtod(token, &delim);

          if (*delim == ',')
          {
            token = delim + strspn(delim, ", \t\n\r");
            threshold = strtod(token, &delim);

            if (*delim == ',')
            {
              token = delim + strspn(delim, ", \t\n\r");
              defaultWeight = strtod(token, &delim);
            }
#ifdef AVERAGE_EXAMPLE_SIZE
            else
              defaultWeight = (globalParams.rawMode)
                               ? 0
                               : (INITIAL_WEIGHT_FACTOR * threshold
                                   / globalParams.averageExampleSize);
#else
            else
              defaultWeight = (globalParams.rawMode)
                               ? 0
                               : (INITIAL_WEIGHT_FACTOR * threshold
                                   / globalParams.maxExampleSize);
#endif
          }
        }

        if (*delim == ':')
        {
          token = delim + strspn(delim, ":, \t\n\r");
          if (*token == ')')
          {
            cerr << "Error: No target IDs specified for Perceptron.\n";
            return false;
          }

          token = strtok(token, ")");
          delim += strlen(token) + 2;
        }
        else
        {
          delim += strspn(delim, ":) \t\n\r");
          cerr << "Error: No target IDs specified for Perceptron.\n";
          return false;
        }

        if (*delim == ',')
        {
          Perceptron* pPer = new Perceptron(globalParams, learningRate, 
					    threshold, defaultWeight);
          pPer->targetIds.Parse(token);
          pPer->index = index;

          algorithms.push_back(pPer);
        }
        else
        {
          delim = token;
          token = strtok(NULL, ")");
          cerr << "Failed to parse Perceptron spec '" << delim << '('
               << token << ")'\n\n";
          result = false;
        }
      }
      else if (tolower(*token) == 'b')
      {
        delim = token + strlen(token) + 1;
        token = delim + strspn(delim, ":, \t\n\r");
        if (*token == ')')
        {
          cerr << "Error: No target IDs specified for Naive Bayes.\n";
          return false;
        }

        token = strtok(token, ")");
        delim += strlen(token) + 2;

        if (*delim == ',')
        {
          NaiveBayes* pBay = new NaiveBayes(globalParams);
          pBay->targetIds.Parse(token);
          pBay->index = index;

          algorithms.push_back(pBay);
        }
        else
        {
          delim = token;
          token = strtok(NULL, ")");
          cerr << "Failed to parse Naive Bayes spec '" << delim << '('
               << token << ")'\n\n";
          result = false;
        }
      }

      ++index;
      token = strtok(delim, " (),\t\n\r");
    }

    CreateClouds();
    if (globalParams.constraintClassification)
    {
      globalParams.targetIdsArray = new FeatureID[clouds.size()];
      CloudVector::iterator it;
      CloudVector::iterator end = clouds.end();
      int i;
      for (i = 0, it = clouds.begin(); it != end; ++it, ++i)
      {
        TargetIDToCloud[it->Id()] = VectorCloudIterator_Bool(it);
        globalParams.targetIdsArray[i] = it->Id();
      }
    }
  }
  else
  {
    cerr << "Error:\n";
    cerr << "Failed to allocate work buffer for parsing network specification"
         << "\n";
    result = false;
  }

  return result;
}


void Network::CreateClouds()
{
  AlgorithmVector activeAlgorithms;

  TargetIdSet::const_iterator it = globalParams.targetIds.begin();
  TargetIdSet::const_iterator end = globalParams.targetIds.end();

  // Create one new Cloud for each TargetId
  for (; it != end; ++it)
  {
    activeAlgorithms.clear();
    AlgorithmVector::iterator algIt = algorithms.begin();
    AlgorithmVector::iterator algEnd = algorithms.end();

    for (; algIt != algEnd; ++algIt)
    {
      if ( (*algIt)->targetIds.find(*it) != ( (*algIt)->targetIds.end() ) )
        activeAlgorithms.push_back(*algIt);
    }

    clouds.push_back(Cloud(*it, activeAlgorithms, globalParams));
    clouds.back().SetMistakes(0);
  }
}


bool Network::PresentExample( Example& ex )
{
  CloudVector::iterator it = clouds.begin();
  CloudVector::iterator clouds_end = clouds.end();
  TargetIdSet::iterator targets_end = ex.targets.end();
  bool targets_empty = ex.targets.empty();
  bool mistakes = false;

  for (; it != clouds_end; ++it)
  {
    if (targets_empty || ex.targets.find(it->Id()) != targets_end)
      // The following call to PresentExample will always return false if
      // globalParams.constraintClassification = true
      if (it->PresentExample(ex)) mistakes = true;
  }

  if (globalParams.constraintClassification
      && (globalParams.currentCycle > 1 || !globalParams.noFirstCycleUpdate
        || globalParams.currentCycle == 0))
  { // Make the update decision based on relative activation levels
    int i, currentID = 0, subordinateID, targets = ex.features.Targets();
    CloudVector::iterator currentCloud, subordinateCloud;

    if (globalParams.conservativeCC)
    {
      double highestActivation = DBL_MIN;
      for (it = clouds.begin(); it != clouds_end; ++it)
#ifdef TRAIN_WITH_NORMALIZED_ACTIVATION
        if (it->NormalizedActivation() > highestActivation)
#else
        if (it->Activation() > highestActivation)
#endif
        {
#ifdef TRAIN_WITH_NORMALIZED_ACTIVATION
          highestActivation = it->NormalizedActivation();
#else
          highestActivation = it->Activation();
#endif
          subordinateCloud = it;
        }

      currentCloud =
        TargetIDToCloud[ex.features[currentID].id].VCIterator;
      if (subordinateCloud->Id() != ex.features[0].id
          && ConstraintClassificationUpdate(ex, currentCloud,
                                            subordinateCloud,
                                            ex.features[currentID].id,
                                            subordinateCloud->Id()))
        mistakes = true;
    }
    else
    {
      // For all target IDs whose activations should be higher than another
      // target ID's
      for (subordinateID = 1; subordinateID < targets;
           ++currentID, ++subordinateID)
      {
        currentCloud =
          TargetIDToCloud[ex.features[currentID].id].VCIterator;
        subordinateCloud =
          TargetIDToCloud[ex.features[subordinateID].id]