path: root/moses/src/FeatureVector.cpp

/*
 Moses - factored phrase-based language decoder
 Copyright (C) 2010 University of Edinburgh
 
 
 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.,
 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
 
 */

#include <algorithm>
#include <cmath>
#include <fstream>
#include <sstream>
#include <stdexcept>

#include "FeatureVector.h"

using namespace std;


namespace Moses {
  
  const string FName::SEP = "_";
  FName::Name2Id FName::name2id;
  vector<string> FName::id2name;
  FName::Id2Count FName::id2hopeCount;
  FName::Id2Count FName::id2fearCount;
#ifdef WITH_THREADS
  boost::shared_mutex FName::m_idLock;
#endif
  
  void FName::init(const string& name)  {
#ifdef WITH_THREADS
    //reader lock
    boost::shared_lock<boost::shared_mutex> lock(m_idLock);
#endif
    Name2Id::iterator i = name2id.find(name);
    if (i != name2id.end()) {
      m_id = i->second;
    } else {
#ifdef WITH_THREADS
      //release the reader lock, and upgrade to writer lock
      lock.unlock();
      boost::upgrade_lock<boost::shared_mutex> upgradeLock(m_idLock);
      boost::upgrade_to_unique_lock<boost::shared_mutex> uniqueLock(upgradeLock);
#endif
      //Need to check again if the id is in the map, as someone may have added
      //it while we were waiting on the writer lock.
      if (i != name2id.end()) {
        m_id = i->second;
      } else {
        m_id = name2id.size();
        name2id[name] = m_id;
        id2name.push_back(name);
      }
    }
  }
  
  size_t FName::getId(const string& name) {
	  Name2Id::iterator i = name2id.find(name);
	  assert (i != name2id.end());
	  return i->second;
  }
  
  size_t FName::getHopeIdCount(const string& name) {
	  Name2Id::iterator i = name2id.find(name);
	  if (i != name2id.end()) {
		  float id = i->second;
		  return id2hopeCount[id];
	  }
	  return 0;
  }

  size_t FName::getFearIdCount(const string& name) {
	  Name2Id::iterator i = name2id.find(name);
	  if (i != name2id.end()) {
		  float id = i->second;
		  return id2fearCount[id];
	  }
	  return 0;
  }
  
  void FName::incrementHopeId(const string& name) {
	  Name2Id::iterator i = name2id.find(name);
	  assert(i != name2id.end());
#ifdef WITH_THREADS
      // get upgradable lock and upgrade to writer lock
      boost::upgrade_lock<boost::shared_mutex> upgradeLock(m_idLock);
      boost::upgrade_to_unique_lock<boost::shared_mutex> uniqueLock(upgradeLock);
#endif
      id2hopeCount[i->second] += 1; 
  }

    void FName::incrementFearId(const string& name) {
	  Name2Id::iterator i = name2id.find(name);
	  assert(i != name2id.end());
#ifdef WITH_THREADS
      // get upgradable lock and upgrade to writer lock
      boost::upgrade_lock<boost::shared_mutex> upgradeLock(m_idLock);
      boost::upgrade_to_unique_lock<boost::shared_mutex> uniqueLock(upgradeLock);
#endif
      id2fearCount[i->second] += 1; 
  }
  
  void FName::eraseId(size_t id) {
#ifdef WITH_THREADS
      // get upgradable lock and upgrade to writer lock
      boost::upgrade_lock<boost::shared_mutex> upgradeLock(m_idLock);
      boost::upgrade_to_unique_lock<boost::shared_mutex> uniqueLock(upgradeLock);
#endif
      id2hopeCount.erase(id);
      id2fearCount.erase(id);
  }
   
  std::ostream& operator<<( std::ostream& out, const FName& name) {
    out << name.name();
    return out;
  }
  
  size_t FName::hash() const {
    return boost::hash_value(m_id);
  }
  
  const std::string& FName::name() const {
    return id2name[m_id];
  }
  
  
  bool FName::operator==(const FName& rhs) const {
    return m_id == rhs.m_id;
  }
  
  bool FName::operator!=(const FName& rhs) const {
    return ! (*this == rhs);
  }
  
  FVector::FVector(size_t coreFeatures) : m_coreFeatures(coreFeatures) {}

  void FVector::resize(size_t newsize) {
      valarray<FValue> oldValues(m_coreFeatures);
      m_coreFeatures.resize(newsize);
      for (size_t i = 0; i < min(m_coreFeatures.size(), oldValues.size()); ++i) {
        m_coreFeatures[i] = oldValues[i];
      }
    }
	
	void FVector::clear() {
	  m_coreFeatures.resize(0);
	  m_features.clear();
	}
	
	bool FVector::load(const std::string& filename) {
    clear();
		ifstream in (filename.c_str());
		if (!in) {
      return false;
		}
		string line;
		while(getline(in,line)) {
			if (line[0] == '#') continue;
			istringstream linestream(line);
			string namestring;
			FValue value;
			linestream >> namestring;
			linestream >> value;
			FName fname(namestring);
			cerr << "Setting sparse weight " << fname << " to value " << value << "." << endl;
			set(fname,value);
		}
    return true;
  }

  void FVector::save(const string& filename) const {
    ofstream out(filename.c_str());
    if (!out) {
      ostringstream msg;
      msg << "Unable to open " << filename;
      throw runtime_error(msg.str());
    }
    write(out);
    out.close();
  }

  void FVector::write(ostream& out) const {
    for (const_iterator i = cbegin(); i != cend(); ++i) {
      out << i->first << " " << i->second << endl;
    }
  }

  static bool equalsTolerance(FValue lhs, FValue rhs) {
    if (lhs == rhs) return true;
    static const FValue TOLERANCE = 1e-4;
    FValue diff = abs(lhs-rhs);
    FValue mean = (abs(lhs)+abs(rhs))/2;
    //cerr << "ET " << lhs << " " << rhs << " " << diff << " " << mean << " " << endl;
    return diff/mean < TOLERANCE ;
  }
  
  bool FVector::operator== (const FVector& rhs) const {
    if (this == &rhs) {
      return true;
    }
    if (m_coreFeatures.size() != rhs.m_coreFeatures.size()) {
      return false;
    }
    for (size_t i = 0; i < m_coreFeatures.size(); ++i) {
      if (!equalsTolerance(m_coreFeatures[i], rhs.m_coreFeatures[i])) return false;
    }
    for (const_iterator i  = cbegin(); i != cend(); ++i) {
      if (!equalsTolerance(i->second,rhs.get(i->first))) return false;
    }
    for (const_iterator i = rhs.cbegin(); i != rhs.cend(); ++i) {
      if (!equalsTolerance(i->second, get(i->first))) return false;
    }
    return true;
  }
  
  bool FVector::operator!= (const FVector& rhs) const {
    return ! (*this == rhs);
  }
	
  ProxyFVector FVector::operator[](const FName& name) {
	  // At this point, we don't know whether operator[] was called, so we return
	  // a proxy object and defer the decision until later
	  return ProxyFVector(this, name);
  }

  /** Equivalent for core features. */
  FValue& FVector::operator[](size_t index) {
    return m_coreFeatures[index];
  }

	
  FValue FVector::operator[](const FName& name) const {
	  return get(name);
  }

  FValue FVector::operator[](size_t index) const {
    return m_coreFeatures[index];
  }

  ostream& FVector::print(ostream& out) const {
    out << "core=(";
    for (size_t i = 0; i < m_coreFeatures.size(); ++i) {
      out << m_coreFeatures[i];
      if (i + 1 < m_coreFeatures.size()) {
        out << ",";
      }
    }
    out << ") ";
    for (const_iterator i = cbegin(); i != cend(); ++i) {
      if (i != cbegin())
	out << " ";
      out << i->first << "=" << i->second;
    }
    return out;
  }
  
  ostream& operator<<(ostream& out, const FVector& fv) {
    return fv.print(out);
  }
	
  const FValue& FVector::get(const FName& name) const {
    static const FValue DEFAULT = 0;
    const_iterator fi = m_features.find(name);
    if (fi == m_features.end()) {
      return DEFAULT;
    } else {
      return fi->second;
    }
  }

  const FValue& FVector::getBackoff(const FName& name, float backoff) const {
    const_iterator fi = m_features.find(name);
    if (fi == m_features.end()) {
      return backoff;
    } else {
      return fi->second;
    }
  }

  void FVector::thresholdScale(FValue maxValue ) {
    FValue factor = 1.0;
    for (const_iterator i = cbegin(); i != cend(); ++i) {
      FValue value = i->second;
      if (abs(value)*factor > maxValue) {
        factor = abs(value) / maxValue;
      }
    }
    operator*=(factor);
  }

  void FVector::capMax(FValue maxValue) {
    for (const_iterator i = cbegin(); i != cend(); ++i)
      if (i->second > maxValue)
         set(i->first, maxValue);
  }

  void FVector::capMin(FValue minValue) {
    for (const_iterator i = cbegin(); i != cend(); ++i)
      if (i->second < minValue)
         set(i->first, minValue);
  }

  void FVector::set(const FName& name, const FValue& value) {
    m_features[name] = value;
  }
  
  void FVector::printCoreFeatures() {
    cerr << "core=(";
    for (size_t i = 0; i < m_coreFeatures.size(); ++i) {
      cerr << m_coreFeatures[i];
      if (i + 1 < m_coreFeatures.size()) {
	cerr << ",";
      }
    }
    cerr << ") ";
  }

  FVector& FVector::operator+= (const FVector& rhs) {
    if (rhs.m_coreFeatures.size() > m_coreFeatures.size())
      resize(rhs.m_coreFeatures.size());
    for (const_iterator i = rhs.cbegin(); i != rhs.cend(); ++i)
        set(i->first, get(i->first) + i->second);
    for (size_t i = 0; i < rhs.m_coreFeatures.size(); ++i)
      m_coreFeatures[i] += rhs.m_coreFeatures[i];
    return *this;
  }
  
  // add only sparse features
  void FVector::sparsePlusEquals(const FVector& rhs) {
    for (const_iterator i = rhs.cbegin(); i != rhs.cend(); ++i)
	  set(i->first, get(i->first) + i->second);
  }
  
  void FVector::incrementSparseHopeFeatures() {
    for (const_iterator i = cbegin(); i != cend(); ++i) 
      FName::incrementHopeId((i->first).name());
  }

  void FVector::incrementSparseFearFeatures() {
    for (const_iterator i = cbegin(); i != cend(); ++i) 
      FName::incrementFearId((i->first).name());
  }
  
  void FVector::printSparseHopeFeatureCounts(std::ofstream& out) {
    for (const_iterator i = cbegin(); i != cend(); ++i) 
      out << (i->first).name() << ": " << FName::getHopeIdCount((i->first).name()) << std::endl;
  }

  void FVector::printSparseFearFeatureCounts(std::ofstream& out) {
    for (const_iterator i = cbegin(); i != cend(); ++i) 
      out << (i->first).name() << ": " << FName::getFearIdCount((i->first).name()) << std::endl;
  }
  
  void FVector::printSparseHopeFeatureCounts() {
    for (const_iterator i = cbegin(); i != cend(); ++i)
      std::cerr << (i->first).name() << ": " << FName::getHopeIdCount((i->first).name()) << std::endl;
  }

  void FVector::printSparseFearFeatureCounts() {
    for (const_iterator i = cbegin(); i != cend(); ++i)
      std::cerr << (i->first).name() << ": " << FName::getFearIdCount((i->first).name()) << std::endl;
  }

  size_t FVector::pruneSparseFeatures(size_t threshold) {
    size_t count = 0;
    vector<FName> toErase;
    for (const_iterator i = cbegin(); i != cend(); ++i) {
      const std::string& fname = (i->first).name();
      if (FName::getHopeIdCount(fname) < threshold && FName::getFearIdCount(fname) < threshold) {
        toErase.push_back(i->first);
        std::cerr << "pruning: " << fname << " (" << FName::getHopeIdCount(fname) << ", " << FName::getFearIdCount(fname) << ")" << std::endl;
        FName::eraseId(FName::getId(fname));
    	++count;
      }
    }
    
    for (size_t i = 0; i < toErase.size(); ++i) 
    	m_features.erase(toErase[i]);	
        
    return count;
  }
  
  size_t FVector::pruneZeroWeightFeatures() {
	size_t count = 0;
	vector<FName> toErase;
    for (const_iterator i = cbegin(); i != cend(); ++i) {
      const std::string& fname = (i->first).name();
      if (i->second == 0) {
        toErase.push_back(i->first);
        //std::cerr << "prune: " << fname << std::endl;
        FName::eraseId(FName::getId(fname));
    	++count;
      }
    }
    
    for (size_t i = 0; i < toErase.size(); ++i)
    	m_features.erase(toErase[i]);
    
    return count;
  }

  void FVector::updateConfidenceCounts(const FVector& weightUpdate, bool signedCounts) {
    for (size_t i = 0; i < weightUpdate.m_coreFeatures.size(); ++i) {
      if (signedCounts) {
	int sign = weightUpdate.m_coreFeatures[i] >= 0 ? 1 : -1;
	m_coreFeatures[i] += (weightUpdate.m_coreFeatures[i] * weightUpdate.m_coreFeatures[i]) * sign;
      }
      else
	m_coreFeatures[i] += (weightUpdate.m_coreFeatures[i] * weightUpdate.m_coreFeatures[i]);
    }
    
    for (const_iterator i = weightUpdate.cbegin(); i != weightUpdate.cend(); ++i) {
      if (weightUpdate[i->first] == 0)
	continue;
      float value = get(i->first);
      if (signedCounts) {
	int sign = weightUpdate[i->first] >= 0 ? 1 : -1;
	value += (weightUpdate[i->first] * weightUpdate[i->first]) * sign;
      }
      else 
	value += (weightUpdate[i->first] * weightUpdate[i->first]);
      set(i->first, value);
    }
  }

  void FVector::updateLearningRates(float decay, const FVector &confidenceCounts, float core_r0, float sparse_r0) {
    for (size_t i = 0; i < confidenceCounts.m_coreFeatures.size(); ++i) {
      m_coreFeatures[i] = 1.0/(1.0/core_r0 + decay * abs(confidenceCounts.m_coreFeatures[i]));     
    }

    for (const_iterator i = confidenceCounts.cbegin(); i != confidenceCounts.cend(); ++i) {
      float value = 1.0/(1.0/sparse_r0 + decay * abs(i->second));
      set(i->first, value);
    }
  }

  // count non-zero occurrences for all sparse features
  void FVector::setToBinaryOf(const FVector& rhs) {
    for (const_iterator i = rhs.cbegin(); i != rhs.cend(); ++i)
    	if (rhs.get(i->first) != 0)
        	set(i->first, 1);
    for (size_t i = 0; i < rhs.m_coreFeatures.size(); ++i)
    	m_coreFeatures[i] = 1;
  }

  // divide only core features by scalar
  FVector& FVector::coreDivideEquals(float scalar) {
    for (size_t i = 0; i < m_coreFeatures.size(); ++i)
    	m_coreFeatures[i] /= scalar;
	  return *this;
  }

  // lhs vector is a sum of vectors, rhs vector holds number of non-zero summands
  FVector& FVector::divideEquals(const FVector& rhs) {
	  assert(m_coreFeatures.size() == rhs.m_coreFeatures.size());
	    for (const_iterator i = rhs.cbegin(); i != rhs.cend(); ++i)
	    	set(i->first, get(i->first)/rhs.get(i->first)); // divide by number of summands
	    for (size_t i = 0; i < rhs.m_coreFeatures.size(); ++i)
	    	m_coreFeatures[i] /= rhs.m_coreFeatures[i]; // divide by number of summands
	  return *this;
  }

  FVector& FVector::operator-= (const FVector& rhs) {
    if (rhs.m_coreFeatures.size() > m_coreFeatures.size())
      resize(rhs.m_coreFeatures.size());
    for (const_iterator i = rhs.cbegin(); i != rhs.cend(); ++i)
    	set(i->first, get(i->first) -(i->second));
    for (size_t i = 0; i < m_coreFeatures.size(); ++i) {
      if (i < rhs.m_coreFeatures.size()) {
        m_coreFeatures[i] -= rhs.m_coreFeatures[i];
      }
    }
    return *this;
  }
  
  FVector& FVector::operator*= (const FVector& rhs) {
    if (rhs.m_coreFeatures.size() > m_coreFeatures.size()) {
      resize(rhs.m_coreFeatures.size());
    }
    for (iterator i = begin(); i != end(); ++i) {
      FValue lhsValue = i->second;
      FValue rhsValue = rhs.get(i->first);
      set(i->first,lhsValue*rhsValue);
    }
    for (size_t i = 0; i < m_coreFeatures.size(); ++i) {
      if (i < rhs.m_coreFeatures.size()) {
        m_coreFeatures[i] *= rhs.m_coreFeatures[i];
      } else {
        m_coreFeatures[i] = 0;
      }
    }
    return *this;
  }
  
  FVector& FVector::operator/= (const FVector& rhs) {
    if (rhs.m_coreFeatures.size() > m_coreFeatures.size()) {
      resize(rhs.m_coreFeatures.size());
    }
    for (iterator i = begin(); i != end(); ++i) {
      FValue lhsValue = i->second;
      FValue rhsValue = rhs.get(i->first);
      set(i->first, lhsValue / rhsValue) ;
    }
    for (size_t i = 0; i < m_coreFeatures.size(); ++i) {
      if (i < rhs.m_coreFeatures.size()) {
        m_coreFeatures[i] /= rhs.m_coreFeatures[i];
      } else {
        if (m_coreFeatures[i] < 0) {
          m_coreFeatures[i] = -numeric_limits<FValue>::infinity();
        } else if (m_coreFeatures[i] > 0) {
          m_coreFeatures[i] = numeric_limits<FValue>::infinity();
        }
      }
    }
    return *this;
  }
  
  FVector& FVector::operator*= (const FValue& rhs) {
    //NB Could do this with boost::bind ?
    for (iterator i = begin(); i != end(); ++i) {
      i->second *= rhs;
    }
    m_coreFeatures *= rhs;
    return *this;
  }
  
  FVector& FVector::operator/= (const FValue& rhs) {
    for (iterator i = begin(); i != end(); ++i) {
      i->second /= rhs;
    }
    m_coreFeatures /= rhs;
    return *this;
  }

  FVector& FVector::multiplyEqualsBackoff(const FVector& rhs, float backoff) {
    if (rhs.m_coreFeatures.size() > m_coreFeatures.size()) {
      resize(rhs.m_coreFeatures.size());
    }
    for (iterator i = begin(); i != end(); ++i) {
      FValue lhsValue = i->second;
      FValue rhsValue = rhs.getBackoff(i->first, backoff);
      set(i->first,lhsValue*rhsValue);
    }
    for (size_t i = 0; i < m_coreFeatures.size(); ++i) {
      if (i < rhs.m_coreFeatures.size()) {
        m_coreFeatures[i] *= rhs.m_coreFeatures[i];
      } else {
        m_coreFeatures[i] = 0;
      }
    }
    return *this;
  }
  
  FVector& FVector::multiplyEquals(float core_r0, float sparse_r0) {
    for (size_t i = 0; i < m_coreFeatures.size(); ++i) {
      m_coreFeatures[i] *= core_r0;
    }
    for (iterator i = begin(); i != end(); ++i) 
      set(i->first,(i->second)*sparse_r0);   
    return *this;
  }
  
  FValue FVector::l1norm() const {
    FValue norm = 0;
    for (const_iterator i = cbegin(); i != cend(); ++i) {
      norm += abs(i->second);
    }
    for (size_t i = 0; i < m_coreFeatures.size(); ++i) {
      norm += abs(m_coreFeatures[i]);
    }
    return norm;
  }

  FValue FVector::l1norm_coreFeatures() const {
    FValue norm = 0;
    // ignore Bleu score feature (last feature)
    for (size_t i = 0; i < m_coreFeatures.size()-1; ++i) 
      norm += abs(m_coreFeatures[i]);
    return norm;
  }
  
  FValue FVector::l2norm() const {
    return sqrt(inner_product(*this));
  }

  FValue FVector::linfnorm() const {
    FValue norm = 0;
    for (const_iterator i = cbegin(); i != cend(); ++i) {
      float absValue = abs(i->second);
      if (absValue > norm)
	norm = absValue;
    }
    for (size_t i = 0; i < m_coreFeatures.size(); ++i) {
      float absValue = abs(m_coreFeatures[i]);
      if (absValue > norm)
	norm = absValue;
    }
    return norm;
  }

  void FVector::l1regularize(float lambda) {
    for (size_t i = 0; i < m_coreFeatures.size(); ++i) {
      float value = m_coreFeatures[i];
      if (value > 0) {
        m_coreFeatures[i] = max(0.0f, value - lambda);
      }
      else {
        m_coreFeatures[i] = min(0.0f, value + lambda);
      }
    }

    for (iterator i = begin(); i != end(); ++i) {
      float value = i->second;
      if (value > 0) {
        i->second = max(0.0f, value - lambda);
      }
      else {
        i->second = min(0.0f, value + lambda);
      }
    }
  }

  void FVector::l2regularize(float lambda)  {
    for (size_t i = 0; i < m_coreFeatures.size(); ++i) {
      m_coreFeatures[i] *= (1 - lambda);
    }

    for (iterator i = begin(); i != end(); ++i) {
      i->second *= (1 - lambda);            
    }
  }

  FValue FVector::sum() const {
    FValue sum = 0;
    for (const_iterator i = cbegin(); i != cend(); ++i) {
      sum += i->second;
    }
    sum += m_coreFeatures.sum();
    return sum;
  }
    
  FValue FVector::inner_product(const FVector& rhs) const {
    CHECK(m_coreFeatures.size() == rhs.m_coreFeatures.size());
    FValue product = 0.0;
    for (const_iterator i = cbegin(); i != cend(); ++i) {
        product += ((i->second)*(rhs.get(i->first)));
    }
    for (size_t i = 0; i < m_coreFeatures.size(); ++i) {
      product += m_coreFeatures[i]*rhs.m_coreFeatures[i];
    }
    return product;
  }

  const FVector operator+(const FVector& lhs, const FVector& rhs) {
    return FVector(lhs) += rhs;
  }
  
  const FVector operator-(const FVector& lhs, const FVector& rhs) {
    return FVector(lhs) -= rhs;
  }
  
	const FVector operator*(const FVector& lhs, const FVector& rhs) {
    return FVector(lhs) *= rhs;
  }
  
  const FVector operator/(const FVector& lhs, const FVector& rhs) {
    return FVector(lhs) /= rhs;
  }
  
  
  const FVector operator*(const FVector& lhs, const FValue& rhs) {
    return FVector(lhs) *= rhs;
  }
  
  const FVector operator/(const FVector& lhs, const FValue& rhs) {
    return FVector(lhs) /= rhs;
  }

  FValue inner_product(const FVector& lhs, const FVector& rhs) {
    if (lhs.size() >= rhs.size()) {
      return rhs.inner_product(lhs);
    } else {
      return lhs.inner_product(rhs);
    }
  }
}