Kernel Quantum Probability Library
The KQP library aims at providing tools for working with quantums probabilities
rank_selector.hpp
1 /*
2  This file is part of the Kernel Quantum Probability library (KQP).
3 
4  KQP is free software: you can redistribute it and/or modify
5  it under the terms of the GNU General Public License as published by
6  the Free Software Foundation, either version 3 of the License, or
7  (at your option) any later version.
8 
9  KQP is distributed in the hope that it will be useful,
10  but WITHOUT ANY WARRANTY; without even the implied warranty of
11  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12  GNU General Public License for more details.
13 
14  You should have received a copy of the GNU General Public License
15  along with KQP. If not, see <http://www.gnu.org/licenses/>.
16  */
17 
18 #ifndef __KQP_RANK_SELECTOR_H__
19 #define __KQP_RANK_SELECTOR_H__
20 
21 #include <kqp/picojson.hpp>
22 #include <kqp/feature_matrix.hpp>
23 #include <kqp/kqp.hpp>
24 
25 namespace kqp {
29  template<typename Scalar>
30  class EigenList {
31  public:
32  virtual ~EigenList();
33 
37  virtual Scalar get(Index i) const = 0;
38 
42  virtual void remove(Index i) = 0;
43 
47  virtual Index size() const = 0;
48 
52  virtual Index getRank() const = 0;
53 
57  virtual bool isSelected(size_t i) const = 0;
58  };
59 
60 
61  template<typename Scalar, bool absolute>
63  const EigenList<Scalar> &list;
64  EigenListComparator(const EigenList<Scalar> &list) : list(list) {}
65  bool operator() (int i1, int i2) {
66  if (absolute) return std::abs(list.get(i1)) < std::abs(list.get(i2));
67  return list.get(i1) < list.get(i2);
68  }
69  };
70 
71 
72 
73  template<typename Scalar>
74  class DecompositionList : public EigenList<Scalar> {
75  public:
76  typedef Eigen::Matrix<Scalar,Dynamic,Dynamic> Matrix;
77  typedef Eigen::Matrix<Scalar,Dynamic,1> Vector;
78 
79 
80  DecompositionList(const Vector &eigenvalues)
81  : eigenvalues(eigenvalues), selected(eigenvalues.size(), true), rank(eigenvalues.size()) {
82 
83  }
84 
88  virtual Scalar get(Index i) const override {
89  return eigenvalues[i];
90  }
91 
95  virtual void remove(Index i) override {
96  if (selected[i]) {
97  selected[i] = false;
98  rank--;
99  }
100  }
101 
105  virtual Index size() const override {
106  return eigenvalues.size();
107  }
108 
112  virtual Index getRank() const override {
113  return rank;
114  }
115 
119  virtual bool isSelected(size_t i) const override {
120  return selected[i];
121  }
122 
123  const std::vector<bool> &getSelected() const override {
124  return selected;
125  }
126 
127  private:
128 
129  Vector eigenvalues;
130  std::vector<bool> selected;
131  Index rank;
132  };
133 
134 
138  template<typename Scalar>
139  class Selector {
140  public:
141  virtual ~Selector() {}
142 
147  virtual void selection(EigenList<Scalar>& eigenvalues) const = 0;
148 
150  virtual picojson::object save() const = 0;
151  };
152 
156  template<typename Scalar>
157  class ChainSelector : public Selector<Scalar> {
158  std::vector<boost::shared_ptr<Selector<Scalar> > > selectors;
159  public:
160  ChainSelector() {}
161  virtual ~ChainSelector() {}
162 
163  void add(const boost::shared_ptr<Selector<Scalar> > &selector) {
164  selectors.push_back(selector);
165  }
166 
167  virtual void selection(EigenList<Scalar>& eigenvalues) const override {
168  for(auto i = selectors.begin(), end = selectors.end(); i != end; i++)
169  (*i)->selection(eigenvalues);
170  }
171 
172  virtual picojson::object save() const {
173  picojson::object json;
174  json["name"] = picojson::value("chain");
175  json["scalar"] = picojson::value(ScalarInfo<Scalar>::name());
176  picojson::array array;
177  for(auto selector: this->selectors) {
178  array.push_back(picojson::value(selector->save()));
179  }
180  json["list"] = picojson::value(array);
181  return json;
182  }
183 
184  };
185 
186 
187  template<typename Scalar>
188  class Aggregator {
189  public:
190  Aggregator() { }
191  virtual ~Aggregator() {}
192 
193  virtual void reset() = 0;
194  virtual void add(Scalar value) = 0;
195  virtual Scalar get() const = 0;
196  virtual picojson::value save() const = 0;
197  };
198 
199  template<typename Scalar>
200  class Max : public Aggregator<Scalar> {
201  void reset() {
202  max = -std::numeric_limits<float>::infinity();
203  }
204 
205  void add(Scalar value) {
206  max = std::max(value, max);
207  }
208 
209  Scalar get() const {
210  return max;
211  }
212 
213  virtual picojson::value save() const {
214  return picojson::value("max");
215  }
216  private:
217  Scalar max;
218  };
219 
220  template<typename Scalar>
221  class Mean : public Aggregator<Scalar> {
222  void reset() {
223  sum = 0;
224  count = 0;
225  }
226 
227  void add(Scalar value) {
228  sum += value;
229  count++;
230  }
231 
232  Scalar get() const {
233  return sum / (Scalar)count;
234  }
235 
236  virtual picojson::value save() const {
237  return picojson::value("mean");
238  }
239  private:
240  Scalar sum;
241  long count;
242  };
243 
244 
248  template<typename Scalar>
249  class RatioSelector : public Selector<Scalar> {
250  public:
251  typedef boost::shared_ptr< Aggregator<Scalar> > AggregatorPtr;
252 
253  RatioSelector(Scalar threshold, const AggregatorPtr &aggregator)
254  : minRatio(threshold), m_aggregator(aggregator) {}
255  virtual ~RatioSelector() {}
256 
257  virtual void selection(EigenList<Scalar>& eigenvalues) const override {
258  // Computes the maximum of eigenvalues
259  m_aggregator->reset();
260  for(Index i = 0; i < eigenvalues.size(); i++)
261  if (eigenvalues.isSelected(i))
262  m_aggregator->add(std::abs(eigenvalues.get(i)));
263 
264  // Remove those above the maximum * ratio
265  Scalar threshold = m_aggregator->get() * minRatio;
266  for(Index i = 0; i < eigenvalues.size(); i++)
267  if (eigenvalues.isSelected(i))
268  if (std::abs(eigenvalues.get(i)) < threshold)
269  eigenvalues.remove(i);
270 
271  }
272 
273  virtual picojson::object save() const override {
274  picojson::object json;
275  json["name"] = picojson::value("ratio");
276  json["scalar"] = picojson::value(ScalarInfo<Scalar>::name());
277  json["minRatio"] = picojson::value(minRatio);
278  json["aggregator"] = picojson::value(m_aggregator->save());
279  return json;
280  }
281 
282  private:
283  Scalar minRatio;
284  AggregatorPtr m_aggregator;
285  };
286 
290  template<typename Scalar, bool byMagnitude>
291  class RankSelector : public Selector<Scalar> {
293  Index maxRank;
294 
296  Index resetRank;
297  public:
298  virtual ~RankSelector() {}
299 
305  RankSelector(Index maxRank) : maxRank(maxRank), resetRank(maxRank) {}
306 
307 
311  RankSelector(Index maxRank, Index resetRank) : maxRank(maxRank), resetRank(resetRank) {
312  if (resetRank > maxRank)
313  KQP_THROW_EXCEPTION_F(out_of_bound_exception, "The maximum rank (%d) should be greater or equal to the reset rank (%d)", %maxRank %resetRank);
314  }
315 
316  void selection(EigenList<Scalar>& eigenvalues) const override {
317  // exit if we have nothing to do
318  if (eigenvalues.getRank() <= maxRank) return;
319 
320  // Copy the values
321  std::vector<Scalar> values;
322  values.reserve(eigenvalues.getRank());
323  for(Index i = 0; i < eigenvalues.size(); i++)
324  if (eigenvalues.isSelected(i))
325  values.push_back(i);
326 
327  // Sort and select
328  std::sort(values.begin(), values.end(), EigenListComparator<Scalar, byMagnitude>(eigenvalues));
329 
330  // Select the rank highest eigenvalues
331  for(Index i = 0; i < eigenvalues.size() - resetRank; i++)
332  eigenvalues.remove(values[i]);
333  }
334 
335  virtual picojson::object save() const {
336  picojson::object json;
337  json["name"] = picojson::value("rank");
338  json["scalar"] = picojson::value(ScalarInfo<Scalar>::name());
339  json["max"] = picojson::value(maxRank);
340  json["reset"] = picojson::value(resetRank);
341  return json;
342  }
343 
344  };
345 }
346 
347 #endif