summaryrefslogtreecommitdiff
path: root/vest/line_optimizer.cc
blob: 70a00cbce95148eecfd0ace098ab5844138ead51 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
#include "line_optimizer.h"

#include <limits>
#include <algorithm>

#include "sparse_vector.h"
#include "scorer.h"

using namespace std;

typedef ErrorSurface::const_iterator ErrorIter;

// sort by increasing x-ints
struct IntervalComp {
  bool operator() (const ErrorIter& a, const ErrorIter& b) const {
    return a->x < b->x;
  }
};

double LineOptimizer::LineOptimize(
    const vector<ErrorSurface>& surfaces,
    const LineOptimizer::ScoreType type,
    float* best_score,
    const double epsilon) {
  // cerr << "MIN=" << MINIMIZE_SCORE << " MAX=" << MAXIMIZE_SCORE << "  MINE=" << type << endl;
  vector<ErrorIter> all_ints;
  for (vector<ErrorSurface>::const_iterator i = surfaces.begin();
       i != surfaces.end(); ++i) {
    const ErrorSurface& surface = *i;
    for (ErrorIter j = surface.begin(); j != surface.end(); ++j)
      all_ints.push_back(j);
  }
  sort(all_ints.begin(), all_ints.end(), IntervalComp());
  double last_boundary = all_ints.front()->x;
  ScoreP accp = all_ints.front()->delta->GetZero();
  Score *acc=accp.get();
  float& cur_best_score = *best_score;
  cur_best_score = (type == MAXIMIZE_SCORE ?
    -numeric_limits<float>::max() : numeric_limits<float>::max());
  bool left_edge = true;
  double pos = numeric_limits<double>::quiet_NaN();
  for (vector<ErrorIter>::iterator i = all_ints.begin();
       i != all_ints.end(); ++i) {
    const ErrorSegment& seg = **i;
    assert(seg.delta);
    if (seg.x - last_boundary > epsilon) {
      float sco = acc->ComputeScore();
      if ((type == MAXIMIZE_SCORE && sco > cur_best_score) ||
          (type == MINIMIZE_SCORE && sco < cur_best_score) ) {
        cur_best_score = sco;
	if (left_edge) {
	  pos = seg.x - 0.1;
	  left_edge = false;
	} else {
	  pos = last_boundary + (seg.x - last_boundary) / 2;
	}
	// cerr << "NEW BEST: " << pos << "  (score=" << cur_best_score << ")\n";
      }
      // string xx; acc->ScoreDetails(&xx); cerr << "---- " << xx;
      // cerr << "---- s=" << sco << "\n";
      last_boundary = seg.x;
    }
    // cerr << "x-boundary=" << seg.x << "\n";
    acc->PlusEquals(*seg.delta);
  }
  float sco = acc->ComputeScore();
  if ((type == MAXIMIZE_SCORE && sco > cur_best_score) ||
      (type == MINIMIZE_SCORE && sco < cur_best_score) ) {
    cur_best_score = sco;
    if (left_edge) {
      pos = 0;
    } else {
      pos = last_boundary + 1000.0;
    }
  }
  return pos;
}

void LineOptimizer::RandomUnitVector(const vector<int>& features_to_optimize,
                                     SparseVector<double>* axis,
                                     RandomNumberGenerator<boost::mt19937>* rng) {
  axis->clear();
  for (int i = 0; i < features_to_optimize.size(); ++i)
    axis->set_value(features_to_optimize[i], rng->next() - 0.5);
  (*axis) /= axis->l2norm();
}

void LineOptimizer::CreateOptimizationDirections(
     const vector<int>& features_to_optimize,
     int additional_random_directions,
     RandomNumberGenerator<boost::mt19937>* rng,
     vector<SparseVector<double> >* dirs
     , bool include_orthogonal
  ) {
  dirs->clear();
  typedef SparseVector<double> Dir;
  vector<Dir> &out=*dirs;
  int i=0;
  if (include_orthogonal)
    for (;i<features_to_optimize.size();++i) {
      Dir d;
      d.set_value(features_to_optimize[i],1.);
      out.push_back(d);
    }
  out.resize(i+additional_random_directions);
  for (;i<out.size();++i)
     RandomUnitVector(features_to_optimize, &out[i], rng);
  cerr << "Generated " << out.size() << " total axes to optimize along.\n";
}