Tanl Linguistic Pipeline

tag/Tanlpos/linear_interpolated_lm.cpp

/*
**  Tanl
**  tag/TanlPos/linear_interpolated_lm.cpp
**  ----------------------------------------------------------------------
**  Copyright (c) 2005  Giuseppe Attardi (attardi@di.unipi.it).
**  ----------------------------------------------------------------------
**
**  This file is part of Tanl.
**
**  Tanl 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.
**
**  Tanl 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/>.
**  ----------------------------------------------------------------------
*/

#include "Tag.h"
#include <cmath>

namespace Tanl { namespace POS {

template <class CT>
void Context<CT>::add_word(std::vector<int>::const_iterator context, int n,
                           CT& word)
{
  //std::cerr << n << ' ' << word << std::endl;
  words[word]++;
  freq++;
  if (n > 0) {
    Context<CT>* cmap = childs[*context];
    if (!cmap) {
      cmap = new Context<CT>();
      childs[*context] = cmap;
    }
    cmap->add_word(++context, n-1, word);
  }
}

template <class CT>
void Context<CT>::serialize(std::ostream &out)
{
  POS::serialize(freq, out);
  POS::serialize(childs.size(), out);
  FOR_EACH (typename CMap, childs, cit) {
    POS::serialize(cit->first, out);
    cit->second->serialize(out);
  }
  POS::serialize(words.size(), out);
  FOR_EACH (typename WordFreq, words, wit) {
    POS::serialize(wit->first, out);
    POS::serialize(wit->second, out);
  }
}

template <class CT>
void Context<CT>::serialize(std::istream &in)
{
  POS::serialize(freq, in);
  size_t size;
  POS::serialize(size, in);
  for (size_t i = 0; i < size; i++) {
    int first;
    POS::serialize(first, in);
    Context<CT>* second = new Context<CT>;
    second->serialize(in);
    childs[first] = second;
  }
  POS::serialize(size, in);
  for (size_t i = 0; i < size; i++) {
    CT first;
    POS::serialize(first, in);
    double second;
    POS::serialize(second, in);
    words[first] = second;
  }
}

// ======================================================================
// FROM HERE: HANDLING PROBABILITES

template <class CT>
void Context<CT>::adjust_lambdas(std::vector<double>& lambdas,
                                 std::vector<Context<CT>*>& context_nodes,
                                 int max_level)
{
  if (context_nodes.size() < max_level) {
    // descend to leaves
    FOR_EACH (typename CMap, this->childs, it) {
      Context<CT>* child = it->second;
      std::vector<Context<CT>*> path1(context_nodes);
      path1.push_back(child);
      child->adjust_lambdas(lambdas, path1, max_level);
    }
    return;
  }
  // this is "for each trigram"
  WordFreq words = context_nodes[0]->get_words();
  FOR_EACH (typename WordFreq, words, wit) {
    CT const& word = wit->first;
    double freq = wit->second;
    double max = 0.0;
    int maxi = 0;
    // search max through context_nodes
    for (int i = 0; i < context_nodes.size(); ++i) {
      Context<CT>& node = *context_nodes[i];
      double word_freq = node.words[word];

      // note: Brants doesn't discuss the case of trigrams
      // with frequency 1. [I believe this is a mistake in 
      //  his paper]. We increment lambdas[0] in this case.
      double ratio = (node.freq == 1.0 || word_freq == 1.0)
        ? -1.0
        : (word_freq - 1.0) / (node.freq - 1.0);

      if (ratio > max) {
        max = ratio; maxi = i;
      }
    }
    lambdas[maxi] += freq;
  }
}

template <class CT>
std::vector<double> Context<CT>::calculate_lambdas(int level)
{
  std::vector<double> lambdas(level+2);
  std::vector<Context<CT>*> path;
  adjust_lambdas(lambdas, path, level);
  lambdas[0] = 0.0;

  // normalize lambdas
  double sum = 0.0;
  for (int i = 0; i < lambdas.size(); i++)
    sum += lambdas[i];
  for (int i = 0; i < lambdas.size(); i++)
    lambdas[i] /= sum;
  return lambdas;
}

template <class CT>
void Context<CT>::counts_to_prob(std::vector<double>& lambdas)
{
  if (words.empty())            // spec_lm may be empty
    return;
  if (lambdas.empty())
    throw ProbError("Context::counts_to_prob: empty lambdas");
  // first l0, then unigram...

  // the first level is a bit different from the others because of
  // programmer lazyness.
  TO_EACH (typename WordFreq, words, wit) {
    CT const& word = wit->first;
    double wfreq = wit->second;
    wit->second = lambdas[0] + lambdas[1] * (wfreq / freq);
  }
  std::vector<double>::const_iterator lit = lambdas.begin();
  lit += 2;                     // skip l0, l1
  FOR_EACH (typename CMap, childs, cit)
    cit->second->estimate_at_context(words, lit);
}

template <class CT>
void Context<CT>::estimate_at_context(WordFreq& parent_words,
                                      std::vector<double>::const_iterator lambdas)
{
  // if there are no more lambdas we can't calculate
  // the probs of larger ngrams. But could this solution cause errors?!
  double l = *lambdas;
  // calc prob of all words
  TO_EACH (typename WordFreq, words, wit) {
    CT const& word = wit->first;
    double wfreq = wit->second;
    wit->second = parent_words[word] + l * (wfreq / freq);
  }

  // walk down the tree
  FOR_EACH (typename CMap, childs, cit)
    cit->second->estimate_at_context(words, ++lambdas);
}

/* go down to the max level where the word can be found */
template <class CT>
double Context<CT>::wordprob(CT const& word, std::vector<int>& context)
{
  double prob = 0.0;
  Context<CT>* node = this;
  int i = 0;
  do {
    typename WordFreq::const_iterator wit = node->words.find(word);
    if (wit != node->words.end())
      prob = wit->second;
    // can we continue?
    if (i < context.size() &&
        node->childs.find(context[i]) != node->childs.end())
      node = node->childs[context[i++]];
    else
      break;
  } while (true);
  return log(prob);
}

} // namespace POS
} // namespace Tanl

 

Copyright © 2005-2011 G. Attardi. Generated on 3 Mar 2011 by doxygen 1.6.1.