DeSR Dependency Parser

src/MlpParser.cpp

/*
**  DeSR
**  src/MlParser.cpp
**  ----------------------------------------------------------------------
**  Copyright (c) 2009  Giuseppe Attardi (attardi@di.unipi.it).
**  ----------------------------------------------------------------------
**
**  This file is part of DeSR.
**
**  DeSR is free software; you can redistribute it and/or modify it
**  under the terms of the GNU General Public License, version 3,
**  as published by the Free Software Foundation.
**
**  DeSR 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, see <http://www.gnu.org/licenses/>.
**  ----------------------------------------------------------------------
*/


#ifdef _WIN32
#include "lib/strtok_r.h"
#endif

#include "conf/conf_int.h"
#include "Parser.h"
#include "EventStream.h"
#include "State.h"

#include <boost/numeric/ublas/matrix.hpp>
#include <boost/numeric/ublas/matrix_proxy.hpp>

using namespace std;
using namespace boost::numeric::ublas;

namespace Parser {

#define BEAM

#define MAX_LINE_LEN 8196


typedef boost::numeric::ublas::vector<double>   Vector;
typedef matrix<double>  Matrix;

void softsign(Vector& x)
{
  for (int i = 0; i < x.size(); i++)
    x[i] /=  1.0 + fabs(x[i]);
}

#define READLINE(line, file)   if (!ifs.getline(line, MAX_LINE_LEN)) \
    throw IXE::FileError(string("Wrong file format: ") + file)

#define READ_WEIGHT(w, file) if (!ifs.read((char*)&w, sizeof(w)))       \
    throw IXE::FileError(string("Wrong file format: ") + file)

struct DlModel : public Classifier::Classifier
{
  DlModel() { }

  DlModel(int numFeatures, int numOutcomes, int numHidden) :
    w1(numFeatures, numHidden),
    b1(numHidden),
    w2(numHidden, numOutcomes),
    b2(numOutcomes)
  { }

  ~DlModel() {
    FOR_EACH (std::vector<char const*>, outcomeLabels, it)
      free((void*)*it);
  }

  int   crossentropy_softmax_argmax(Vector& x, double sm[]) {
    // get the maximum value of x for numerically safe softmax
    double m = 0.0;
    int am = 0;
    for (int i = 0; i < numOutcomes; i++)
      if (x[i] > m) {
        am = i;
        m = x[i];
      }
    // compute the unnormalized softmax, and normalization constant
    double sum_j = 0.0;
    for (int i = 0; i < numOutcomes; i++)
      sum_j += sm[i] = exp(x[i] - m);

    // normalized our softmax
    for (int i = 0; i < numOutcomes; i++)
      sm[i] /= sum_j;

    return am;
  }

  void          estimate(Tanl::Classifier::Context& features, double prob[]) {
    int numFeatures = predIndex.size();
    Vector xw1(numHidden);
    for (int i = 0; i < numHidden; i++)
      xw1[i] = 0.0;
    for (int f = 0; f < features.size(); f++)
      xw1 += row(w1, features[f]);
    xw1 += b1;
    softsign(xw1);
    Vector h(numOutcomes);
    h = prod(xw1, w2);
    h += b2;
    int argmax = crossentropy_softmax_argmax(h, prob);
  }

  void          load(ifstream& ifs, char const* file = "") {
    // load class labels
    char line[MAX_LINE_LEN];
    READLINE(line, file);
    int len = atoi(line);
    numOutcomes = len;
    outcomeLabels.resize(numOutcomes);
    int n = 0;
    while (len--) {
      READLINE(line, file);
      outcomeLabels[n] = strdup(line);
      outcomeIndex[(char const*)line] = n++;
    }
    // load feature labels
    READLINE(line, file);
    int numFeatures = len = atoi(line);
    predLabels.resize(numFeatures);
    n = 0;
    while (len--) {
      READLINE(line, file);
      predLabels[n] = line;
      predIndex[(char const*)line] = n++;
    }

    // read hidden size
    READLINE(line, file);
    numHidden = atoi(line);

    w1.resize(numFeatures, numHidden);
    // load weights

    // w1
    READLINE(line, file);
    len = atoi(line);           // numFeats * numHidden
    n = 0;
    double w;
    while (len--) {
      READ_WEIGHT(w, file);
      w1(n / numHidden, n % numHidden) = w;
      n++;
    }

    // b1
    b1.resize(numHidden);
    READLINE(line, file);
    len = atoi(line);           // numHidden
    n = 0;
    while (len--) {
      READ_WEIGHT(w, file);
      b1[n++] = w;
    }

    // w2
    w2.resize(numHidden, numOutcomes);
    READLINE(line, file);
    len = atoi(line);           // numHidden * numOutcomes
    n = 0;
    while (len--) {
      READ_WEIGHT(w, file);
      w2(n / numOutcomes, n % numOutcomes) = w;
      n++;
    }

    // b2
    b2.resize(numOutcomes);
    READLINE(line, file);
    len = atoi(line);           // numOutcomes
    n = 0;
    while (len--) {
      READ_WEIGHT(w, file);
      b2[n++] = w;
    }
  }

  Matrix        w1, w2;
  Vector        b1, b2;
  int           numHidden;
  WordIndex     outcomeIndex;
};

struct MlParser : public Parser
{
  MlParser(char const* modelFile);

  void          train(SentenceReader* sentenceReader, char const* modelFile);

  Sentence*     parse(Sentence* sentence);

  void          revise(SentenceReader* sentenceReader, char const* actionFile = 0);

  DlModel               model;
};

Parser* MlParserFactory(char const* modelFile = 0)
{
  return new MlParser(modelFile);
}

REGISTER_PARSER(MLP, MlParserFactory);

MlParser::MlParser(char const* modelFile) :
  Parser(model.PredIndex())
{
  if (!modelFile)
    return;                     // training
  ifstream ifs(modelFile);
  if (!ifs)
    throw IXE::FileError(string("Missing model file: ") + modelFile);
  // load header
  readHeader(ifs);
  model.load(ifs);
  // read entities
  info.load(ifs);
  ifs.close();
}

void MlParser::train(SentenceReader* sentenceReader, char const* modelFile)
{
  EventStream eventStream(sentenceReader, &info);
  cerr << "Training the Deep Learning is currently possible only with a Python script.\n"
       << "Generate the training examples with 'desr -d'\n"
       << "and then hadle them to the script train.py.\n"
       << "You then must convert the generated model into a DeSR model\n"
       << "using the script script/dumpPyModel.py" << endl;
  /*
  DeepLearn model(iterations, featureCutoff);
  model.verbose = verbose;
  model.read(eventStream);
  ofstream ofs(modelFile, ios::binary | ios::trunc);
  // dump configuration settings
  writeHeader(ofs);
  model.train();
  // cant do before train since outcomeLabels is created in train()
  model.writeHeader(ofs);
  model.writeData(ofs);
  // dump entities
  info.save(ofs);
  */
}

#ifdef BEAM
// FIXME: this is duplicated in MlParser.cpp
static double addState(ParseState* s, std::vector<ParseState*>& states)
{
  int size = states.size();
  if (size == 0) {
    states.push_back(s);
    return s->lprob;
  }
  double worst = states[size-1]->lprob;
  if (size == beam && s->lprob < worst)
    return worst;
  TO_EACH (std::vector<ParseState*>, states, it)
    if (s->lprob > (*it)->lprob) {
      if (size == beam) {
        delete states.back();
        states.pop_back();
      }
      states.insert(it, s);
      return states.back()->lprob;
    }
  if (size < beam)
    states.push_back(s);
  return states.back()->lprob;
}
#endif

Sentence* MlParser::parse(Sentence* sentence)
{
  int numOutcomes = model.NumOutcomes();
  int numFeatures = model.PredIndex().size();
  double params[numOutcomes];

# ifdef BEAM
  std::vector<ParseState*> currStates; currStates.reserve(beam);
  std::vector<ParseState*> nextStates; nextStates.reserve(beam);
  std::vector<ParseState*>* bestStates = &currStates;
  std::vector<ParseState*>* bestNextStates = &nextStates;
  ParseState* state = new ParseState(*sentence, &info, model.PredIndex());
  addState(state, *bestStates);

  while (true) {
    int finished = 0;
    int numBest = bestStates->size();
    //int numNext = 0;
    double worstProb = -numeric_limits<double>::infinity();
    for (int i = 0; i < numBest; i++) {
      state = (*bestStates)[i];
      if (state->hasNext()) {
        Tanl::Classifier::Context& features = *state->next();
        // build example
        model.estimate(features, params);
        for (int o = 0; o < numOutcomes; o++) {
          double prob = params[o];
          if (prob < 1e-4)
            continue;           // not worth considering
          double lprob = log(prob) + state->lprob;
          if (bestNextStates->size() == beam && lprob < worstProb)
            continue;           // not worth considering
          char const* outcome = model.OutcomeName(o);
          ParseState* next = state->transition(outcome);
          if (!next) {
            // dead end
            state->dispose();
            continue;
          }
          next->lprob = lprob;
          worstProb = addState(next, *bestNextStates);
        }
      } else {
        // already finished: promote to bestNextStates
        worstProb = addState(state, *bestNextStates);
        finished++;
      }
    }
    if (finished == numBest)
      break;
    // swap vectors
    std::vector<ParseState*>* tmp = bestStates;
    bestStates = bestNextStates;
    bestNextStates = tmp;
    bestNextStates->clear();
  }
  Sentence* s = (*bestStates)[0]->getSentence();
  FOR_EACH (std::vector<ParseState*>, *bestStates, it)
    delete *it;
  return s;
# else
  PyObject* pPredict = PyImport("predict");
  if (pPredict == 0)
    return 0;
  PyObject* predict = PyObject_GetAttrString(pPredict, "predict");
  ParseState* state = new ParseState(*sentence, &info, model.predIndex);

  while (state->hasNext()) {
    Tanl::Classifier::Context& features = *state->next();
    // build example
    PyObject* pFeatures = PyTuple_New(features.size());
    for (int i = 0; i < features.size(); i++)
      PyTuple_SetItem(pFeatures, i, PyInt_FromLong(features[i]));

    PyObject* pBest = PyObject_CallFunctionObjArgs(predict, pFeatures, pNumFeatures, model, 0);
    int best = PyInt_AsLong(pBest);
    Py_DECREF(pFeatures);
    Py_DECREF(pBest);
    char const* outcome = model.outcomeLabels[best];
    ParseState* nextState = state->transition(outcome);
    if (!nextState)
      nextState =state->transition("S");
    state = nextState;
  }
  Py_DECREF(pNumFeatures);
  Sentence* s = state->getSentence();
  delete state;
  return s;
# endif
}

void MlParser::revise(SentenceReader* sentenceReader, char const* actionFile)
{}

} // namespace Parser

 

Copyright © 2005-2007 G. Attardi. Generated on 13 Aug 2009 by doxygen 1.5.7.1.