C++ and STL - Machine Learning Problem

Question

I would like to get some general comments on style and use of STL in particular. This is some code I wrote to do machine learning classification (logistic regression). Any suggestions would be very appreciated!

A record containing an individual training example:

/*
 * A class representing a single record to be used for training or evaluation
 * of a classifier. This record contains a vector of predictors which are
 * observations used to predict an outcome, together with a target outcome for
 * that observation. The machine learning algorithm's job is to learn to
 * generalize this predictor to target outcome relationship.
 */
#include "Record.h"
using namespace std;

/**
 * Construct a record from the provided predictor Vector and target outcome.
 */
Record::Record(const Vector& predictor, double target) :
    predictor_(predictor), target_(target) {
}

/**
 * Construct a record by parsing the provided string. The string must contain
 * a set of space seperated values, with the target outcome in column kTargetCol
 * and the predictor vector starting on column kPredictorCol. Note that each
 * element of the predictor vector is preceeded by an index and a colon. So
 * the string looks has the following form:
 * <label> <target_outcome> 1:<predictor_element1> 2:<predictor_element2> ...
 */
Record::Record(const string& line) {
  Init(line);
}

void Record::Init(const string& line) {
  stringstream line_stream(line);
  string token;
  for (int i = 0; getline(line_stream, token, ' '); ++i) {
    if (i == kTargetCol) {
      istringstream istream(token);
      double target;
      istream >> target;
      target_ = target;
    }
    if (i >= kPredictorCol) {
      istringstream istream(token.substr(token.find(':') + 1));
      double element;
      istream >> element;
      predictor_.push_back(element);
    }
  }
}

/** Convert a record into a string suitable for display */
string Record::String() const {
  ostringstream sstream;
  sstream << target_;
  return sstream.str() + ", " + predictor_.String();
}

A collection of training examples:

/*
 * A class representing a collection of records to be used for training or
 * evaluation of a classifier.
 */
#include "RecordList.h"
using namespace std;
/**
 * Initialize a list of training/test records from the provided filename.
 */
RecordList::RecordList(const string& filename) {
  input_file_.open(filename.c_str(), ios::in);
  Init();
}

void RecordList::Init() {
  for (string line; getline(input_file_, line);) {
    Record record(line);
    records_.push_back(record);
  }
}

RecordList::~RecordList() {
  input_file_.close();
}


/**
 * A constant version of an iterator pointing to the beginning of the record
 * list. Used for doing read only iterations through the list.
 */
vector<Record>::const_iterator RecordList::const_begin() const {
  return records_.begin();
}

/**
 * A constant version of an iterator pointing to the end of the record list.
 * Used for doing read only iterations through the list.
 */
vector<Record>::const_iterator RecordList::const_end() const {
  return records_.end();
}

/**
 * A regular version of an iterator pointing to the beginning of the record list.
 * Used for doing iterations through the list that modify records.
 */
vector<Record>::iterator RecordList::begin() {
  return records_.begin();
}

/**
 * A regular version of an iterator pointing to the end of the record list.
 * Used for doing iterations through the list that modify records.
 */
vector<Record>::iterator RecordList::end() {
  return records_.end();
}

/**
 * Get the number of elements in the predictor vectors. Note that this is the
 * same for all records;
 */
int RecordList::RecordSize() const {
  return records_[0].predictor().size();
}

/** Get the average of the predictors. */
Vector RecordList::Mean() const {
  Vector mean(RecordSize());
  for (vector<Record>::const_iterator itr = const_begin(); itr != const_end();
      ++itr) {
    mean = mean + itr->predictor();
  }
  return mean / records_.size();
}

/** Get the variance of the predictors. */
Vector RecordList::SqrtVar() const {
  Vector var(RecordSize());
  Vector mean = Mean();
  for (vector<Record>::const_iterator itr = const_begin(); itr != const_end();
      ++itr) {
    var = var + (itr->predictor() - mean).Square();
  }
  return (var / records_.size()).Sqrt();
}

/** Convert the record list into a string suitable for display. */
string RecordList::String() const {
  string result = "";
  int i = 0;
  for (vector<Record>::const_iterator itr = records_.begin();
      itr != records_.end(); ++itr) {
    if (i++ == 10) {
      return result + "...\n";
    }
    result += itr->String() + "\n";
  }
  return result;
}

A normalizer used to pre-process each training sample:

/**
 * A class for normalizing records.
 */
#include "Normalizer.h"

/**
 * Construct a normalizer suitable for the provided RecordList by calculating
 * the mean and square root of the underlying predictor Vectors.
 */
Normalizer::Normalizer(const RecordList& recordList)
    : mean_(recordList.Mean()), sqrt_var_(recordList.SqrtVar()) {}

/**
 * Normalize a RecordList by subtracting the mean from each predictor Vector
 * and dividing by the square root of the variance.
 */
void Normalizer::Normalize(RecordList& recordList) const {
  for (vector<Record>::iterator itr = recordList.begin();
      itr != recordList.end(); ++itr) {
    itr->set_predictor(Normalize(itr->predictor()));
  }
}

/**
 * Normalize an individual predictor Vector.
 */
Vector Normalizer::Normalize(const Vector& v) const {
  return (v - mean_) / sqrt_var_;
}

The classifier itself:

/**
 * A class representing a logistic regression classifier. This classifier can
 * predict the target outcome for any given predictor Vector. It can also be
 * trained by the Trainer class given a suitable training RecordList.
 */
#include "Classifier.h"
using namespace std;

/**
 * Construct a classifier for the provided training set and normalizer. This
 * initializes the weight Vector to have all zero. A Trainer must be applied
 * to the Classifier before it can be used.
 */
Classifier::Classifier(const RecordList& training_set,
    const Normalizer& normalizer) :
    normalizer_(normalizer),
    weights_(Vector(training_set.RecordSize())) {}

/**
 * Classify the provided predictor Vector. This provides an estimate of the
 * target outcome.
 */
double Classifier::Classify(const Vector& v) const {
  Vector vn = normalizer_.Normalize(v);
  return 2.0 * Sigmoid(weights_.InnerProduct(vn)) - 1.0;
}

/**
 * Calculate the sigmoid (logistic function) of the given value.
 */
double Classifier::Sigmoid(double x) const {
  return 1.0 / (1.0 + exp(-x));
}

/**
 * Evaluate performance of the classifier using the provided test RecordList.
 */
int Classifier::EvaluatePerformance(const RecordList& test_set) const {
  int total = 0;
  int correct = 0;
  for (vector<Record>::const_iterator itr = test_set.const_begin();
      itr != test_set.const_end(); ++itr) {
    double result = Classify(itr->predictor());
    total++;
    if ((result < 0 && itr->target() < 0)
        || (result > 0 && itr->target() > 0)) {
      correct++;
    }
  }
  return (100*correct) / total;
}

A class for training the classifier:

/**
 * A class for training a classifier.
 */
#include "Trainer.h"
using namespace std;
static const double kTrainingRate = 0.01;
static const string kTrainingFile = "data/training.txt";
static const string kTestFile = "data/test.txt";

/**
 * Construct a Trainer using the provided training rate. Higher training rates
 * will lead to faster convergence but higher asymptotic error.
 */
Trainer::Trainer(double training_rate) : training_rate_(training_rate) {}

/**
 * Train a classifier using stochastic gradient descent. At each iteration
 * the classifier weights are updated based on the delta between the estimate
 * from the classifier and the target outcome.
 */
void Trainer::Train(const RecordList& training_records,
    Classifier& classifier) {
  Vector delta;
  for (vector<Record>::const_iterator itr = training_records.const_begin();
      itr != training_records.const_end(); ++itr) {
    double estimate = classifier.Classify(itr->predictor());
    double estimation_error = estimate - itr->target();
    delta = itr->predictor() * (training_rate_ * estimation_error);
    classifier.set_weights(classifier.weights() - delta);
  }
}

/**
 * The main program. Loads a set of training records and normalizes them. It
 * then uses these records to train a classifier before evaluating the
 * classifier's performance on a second set of test records.
 */
int main() {
  RecordList training_records(kTrainingFile);
  Normalizer normalizer(training_records);
  Classifier classifier(training_records, normalizer);
  Trainer trainer(kTrainingRate);
  trainer.Train(training_records, classifier);
  RecordList test_records(kTestFile);
  printf("Percentage of correct classifications: %d%%\n",
      classifier.EvaluatePerformance(test_records));
}

And finally a class for representing mathematical vectors (essentially just arrays of doubles):

/**
 * A class to represent a vector which is an array of doubles. Supports various
 * calculations like addition, subtraction and inner product.
 */
#include "Vector.h"
using namespace std;

Vector::Vector() : elements(vector<double>()) {}

Vector::Vector(int size) : elements(vector<double>(size, 0)) {}

Vector::Vector(const vector<double>& values) : elements(values) {}

int Vector::size() const {
  return elements.size();
}

double Vector::operator[](int index) const {
  return elements[index];
}

/**
 * A constant version of an iterator pointing ot the beginning of the vector.
 * Used for doing a read only iteration through the vector.
 */
vector<double>::const_iterator Vector::const_begin() const {
  return elements.begin();
}

/**
* A constant version of an iterator pointing ot the end of the vector.
* Used for doing a read only iteration through the vector.
*/
vector<double>::const_iterator Vector::const_end() const {
  return elements.end();
}

/**
 * A regular version of an iterator pointing to the beginning of the vector.
 * Used for doing iterations through the vector that modify elements.
 */
vector<double>::iterator Vector::begin() {
  return elements.begin();
}

/**
 * A regular version of an iterator pointing to the end of the vector.
 * Used for doing iterations through the vector that modify elements.
 */
vector<double>::iterator Vector::end() {
  return elements.end();
}

/** Convert a Vector into a string suitable for display. */
string Vector::String() const {
  string result = "[ ";
  for (vector<double>::const_iterator itr = elements.begin();
      itr != elements.end(); ++itr) {
    ostringstream sstream;
    sstream << *itr;
    result += sstream.str() + " ";
  }
  result += ("]");
  if (result.size() > 50) {
    return result.substr(0, 47) + " ... ]";
  }
  return result;
}

void Vector::push_back(double value) {
  elements.push_back(value);
}

/**
 * Calculate the inner product of two Vectors by taking the sum of the products
 * of the corresponding elements.
 */
double Vector::InnerProduct(const Vector& operand) const {
  return inner_product(const_begin(), const_end(), operand.const_begin(), 0);
}

Vector Vector::operator+(const Vector& operand) const {
  Vector result(size());
  transform(const_begin(), const_end(), operand.const_begin(), result.begin(),
      plus<double>());
  return result;
}

Vector Vector::operator-(const Vector& operand) const {
  Vector result(size());
  transform(const_begin(), const_end(), operand.const_begin(), result.begin(),
      minus<double>());
  return result;
}

/** Functor for multiplying a Vector by a scalar. */
struct MultiplyScalar {
public:
  MultiplyScalar(double scalar) : scalar(scalar) {}
  double operator()(double x) {
    return x * scalar;
  }
private:
  double scalar;
};

Vector Vector::operator*(double multiplier) const {
  Vector result(size());
  transform(elements.begin(), elements.end(), result.elements.begin(),
      MultiplyScalar(multiplier));
  return result;
}

Vector Vector::operator/(const Vector& divisor) const {
  Vector result(size());
  transform(const_begin(), const_end(), divisor.const_begin(), result.begin(),
      divides<double>());
  return result;
}

/** Functor for dividing a Vector by a scalar. */
struct DivideScalar {
public:
  DivideScalar(double scalar) : scalar(scalar) {}
  double operator()(double x) {
    return x / scalar;
  }
private:
  double scalar;
};

Vector Vector::operator/(double divisor) const {
  Vector result(size());
  transform(elements.begin(), elements.end(), result.elements.begin(),
      DivideScalar(divisor));
  return result;
}

double OpSquare(double x) {
  return x*x;
}

/** Calculate the element-wise square of a Vector. */
Vector Vector::Square() const {
  Vector result(size());
  transform(elements.begin(), elements.end(), result.elements.begin(),
      OpSquare);
  return result;
}

/** Calculate the element-wise square root of a Vector. */
Vector Vector::Sqrt() const {
  Vector result(size());
  transform(elements.begin(), elements.end(), result.elements.begin(),
      sqrt);
  return result;
}

double OpSigmoid(double z) {
  return 1.0 / (1.0 + exp(-z));
}

/** Calculate the element-wise sigmoid of a Vector. */
Vector Vector::Sigmoid() const{
  Vector result(size());
  transform(elements.begin(), elements.end(), result.elements.begin(),
      OpSigmoid);
  return result;
}

Answer 1

Edit (based on the large number of additions) I am re-writing this:

General Notes:

You should add header guards to all your *.h files.

Vector.h

Don't like your use of string conversion methods. Very Java like and not C++ like at all. Prefer to write stream operators which are much more versatile.

  string String() const;

  // Prefer

  friend std::ostream& operator<<(std::ostream stream, Vector const& data)
  {
      return stream;
  }

Hide your implementation details by using local typedefs. Also it is more traditional to just call the method to get a const iterator begin() rather than const_begin() etc.

  vector<double>::const_iterator const_begin() const;
  vector<double>::iterator begin();

  // Prefer
  typedef std::vector<double>       Container;
  typedef Container::iterator       iterator;
  typedef Container::const_iterator const_iterator;

  iterator       begin();
  const_iterator begin() const;

This works but it also allows some expressions that don't do much;

  double operator[](int index) const;

  // Now the compiler will allow:

  Vector  x;
  x[5] = 6;   // Will compile but not do anything.
              // I would prefer this fails to compile so that the
              // user of the class will know that they have done
              // something wrong immediately.

  // Thus I would prefer this declaration:
  double const& operator[](std::size_t index) const;

Not totally convinced that setting up these operators will make using the class easier to read.

  Vector operator+(const Vector& operand) const;
  Vector operator-(double scalar) const;
  Vector operator-(const Vector& operand) const;
  Vector operator*(double scalar) const;
  Vector operator/(double scalar) const;
  Vector operator/(const Vector& operand) const;

Surprised this compiles at all here:

private:
  vector<double> elements;

The header file should include all the header files it need to make the required types available. There is no #include <vector> in this file. Also you do not prefix vector with std:: so how does it know where it is defined.

There are a couple of explanations to both these problems none of them good.

NEVER put using namespace std; in a header file.
NEVER make a header file depend on being included in the correct order.

Vector.cpp

Vector::Vector() : elements(vector<double>()) {}
// Easier to write:
Vector::Vector() : elements() {}


Vector::Vector(int size) : elements(vector<double>(size, 0)) {}    
// Easier to write
Vector::Vector(int size) : elements(size) {} // Value defaults to 0    

I would use the correct type. here.

int Vector::size() const {return elements.size();}
// I would use:
std::size_t Vector::size() const {return elements.size();}

As described above I would return by const reference.

double Vector::operator[](int index) const {
  return elements[index];
}

Here I would not convert to a string.
I would a stream operator (then use some algorithms inside to make it cleaner).

/** Convert a Vector into a string suitable for display. */
string Vector::String() const {

friend std::ostream& operator<<(std::ostream& stream, Vector const& data)
{
   stream << "[ ";
   std::copy(elements.begin(), elements.end(), std::ostream_iterator<double>(stream," "));
   
   stream << "] ";
   return stream;
}

I will add more when I get some time.

Old review.

Rather than write a to_string() method:

string Record::String() const {
  ostringstream sstream;
  sstream << target_;
  return sstream.str() + ", " + predictor_.String();
}

Write a stream operator.

std::ostream& operator<<(std::stream& stream, Record const& data)
{
     return stream << data.target_ << ", " << data.predictor_;
}

If you really just want a string use lexical cast:

Record  record(/* Initialization*/);

// lexical_cast use the stream operator.
std::string data = boost::lexical_cast<std::string>(record);

I don't see the need for a file-stream member that is kept open for the life of the object. Open it use it then let it fall out of scope:

RecordList::RecordList(const string& filename) {
  input_file_.open(filename.c_str(), ios::in);
  Init();
}

void RecordList::Init() {
  for (string line; getline(input_file_, line);) {
    Record record(line);
    records_.push_back(record);
  }
}

RecordList::~RecordList() {
  input_file_.close();
}

I would just do:

RecordList::RecordList(const string& filename) {
  Init(filename);
}

void RecordList::Init(std::string const& filename) {
  std::ifstream  input_file(filename.c_str());
  for (string line; getline(input_file, line);) {
    Record record(line);
    records_.push_back(record);
  }
}

RecordList::~RecordList() {}

Here you are exposing an implementation detail:

 vector<Record>::const_iterator RecordList::const_begin() const {

The user of your class should not need to know that you are using a vector internal to your class

class RecordList
{
    public:
      typedef  std::vector<Record>        Container;
      typedef  Container::iterator        iterator;
      typedef  Container::const_iterator  const_iterator;

      const_iterator   RecordList::const_begin() const;
};

Where you can try and use standard algorithms rather than loops:

Vector mean(RecordSize());
for (vector<Record>::const_iterator itr = const_begin(); itr != const_end();
    ++itr) {
  mean = mean + itr->predictor();
}

I would try and do t for you but I can tell what the type Vector really is. It looks like it should be some container type but you use it like a scaler type on the next line.

return mean / records_.size();

Answer 2

Have you considered passing output arguments using pointers instead of by reference?

That way it's clearer in your method call what the input and output arguments are, e.g instead of

trainer.Train(training_records, classifier);

you would have

trainer.Train(training_records, &classifier);