OneVersusOneClassifier.h
Go to the documentation of this file.
1 //===========================================================================
2 /*!
3  *
4  *
5  * \brief One-versus-one Classifier.
6  *
7  *
8  *
9  * \author T. Glasmachers
10  * \date 2012
11  *
12  *
13  * \par Copyright 1995-2015 Shark Development Team
14  *
15  * <BR><HR>
16  * This file is part of Shark.
17  * <http://image.diku.dk/shark/>
18  *
19  * Shark is free software: you can redistribute it and/or modify
20  * it under the terms of the GNU Lesser General Public License as published
21  * by the Free Software Foundation, either version 3 of the License, or
22  * (at your option) any later version.
23  *
24  * Shark is distributed in the hope that it will be useful,
25  * but WITHOUT ANY WARRANTY; without even the implied warranty of
26  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
27  * GNU Lesser General Public License for more details.
28  *
29  * You should have received a copy of the GNU Lesser General Public License
30  * along with Shark. If not, see <http://www.gnu.org/licenses/>.
31  *
32  */
33 //===========================================================================
34 
35 #ifndef SHARK_MODELS_ONEVERSUSONE_H
36 #define SHARK_MODELS_ONEVERSUSONE_H
37 
38 
40 
41 
42 namespace shark {
43 
44 
45 ///
46 /// \brief One-versus-one Classifier.
47 ///
48 /// \par
49 /// The one-versus-one classifier combines a number of binary
50 /// classifiers to form a multi-class ensemble classifier.
51 /// In the one-versus-one model, there exists one binary
52 /// classifier for each pair of classes. The predictions of
53 /// all binary machines are combined with a simple voting
54 /// scheme.
55 ///
56 /// \par
57 /// The classifier can be extended to handle more classes on
58 /// the fly, without a need for re-training the existing
59 /// binary models.
60 ///
61 template <class InputType>
62 class OneVersusOneClassifier : public AbstractModel<InputType, unsigned int>
63 {
64 public:
70 
71  /// \brief Constructor
73  : m_classes(1)
74  { }
75 
76  /// \brief From INameable: return the class name.
77  std::string name() const
78  { return "OneVersusOneClassifier"; }
79 
80 
81  /// get internal parameters of the model
82  virtual RealVector parameterVector() const
83  {
84  std::size_t total = numberOfParameters();
85  RealVector ret(total);
86  std::size_t used = 0;
87  for (std::size_t i=0; i<m_binary.size(); i++)
88  {
89  std::size_t n = m_binary[i]->numberOfParameters();
90  RealVectorRange(ret, Range(used, used + n)) = m_binary[i]->parameterVector();
91  used += n;
92  }
93  return ret;
94  }
95 
96  /// set internal parameters of the model
97  virtual void setParameterVector(RealVector const& newParameters) {
98  std::size_t used = 0;
99  for (std::size_t i=0; i<m_binary.size(); i++)
100  {
101  std::size_t n = m_binary[i]->numberOfParameters();
102  m_binary[i]->setParameterVector(ConstRealVectorRange(newParameters, Range(used, used + n)));
103  used += n;
104  }
105  SHARK_CHECK(used == newParameters.size(),
106  "[OneVersusOneClassifier::setParameterVector] invalid number of parameters");
107  }
108 
109  /// return the size of the parameter vector
110  virtual std::size_t numberOfParameters() const
111  {
112  std::size_t ret = 0;
113  for (std::size_t i=0; i<m_binary.size(); i++)
114  ret += m_binary[i]->numberOfParameters();
115  return ret;
116  }
117 
118  /// return number of classes
119  unsigned int numberOfClasses() const
120  { return m_classes; }
121 
122  /// \brief Obtain binary classifier.
123  ///
124  /// \par
125  /// The method returns the binary classifier used to distinguish
126  /// class_one from class_zero. The convention class_one > class_zero
127  /// is used (the inverse classifier can be constructed from this one
128  /// by flipping the labels). The binary classifier outputs a value
129  /// of 1 for class_one and a value of zero for class_zero.
130  binary_classifier_type const& binary(unsigned int class_one, unsigned int class_zero) const
131  {
132  SHARK_ASSERT(class_zero < class_one);
133  SHARK_ASSERT(class_one < m_classes);
134  unsigned int index = class_one * (class_zero - 1) / 2 + class_zero;
135  return m_binary[index];
136  }
137 
138  /// \brief Add binary classifiers for one more class to the model.
139  ///
140  /// The parameter binmodels holds a vector of n binary classifiers,
141  /// where n is the current number of classes. The i-th model is this
142  /// list is supposed to output a value of 1 for class n and a value
143  /// of 0 for class i when faced with the binary classification problem
144  /// of separating class i from class n. Afterwards the model can
145  /// predict the n+1 classes {0, ..., n}.
146  void addClass(std::vector<binary_classifier_type*> const& binmodels)
147  {
148  SHARK_CHECK(binmodels.size() == m_classes, "[OneVersusOneClassifier::addClass] wrong number of binary models");
149  m_classes++;
150  m_binary.insert(m_binary.end(), binmodels.begin(), binmodels.end());
151  }
152 
153  boost::shared_ptr<State> createState()const{
154  return boost::shared_ptr<State>(new EmptyState());
155  }
156 
157  using base_type::eval;
158  /// One-versus-one prediction: evaluate all binary classifiers,
159  /// collect their votes, and return the class with most votes.
160  void eval(
161  BatchInputType const & patterns, BatchOutputType& output, State& state
162  )const{
163  std::size_t numPatterns = size(patterns);
164  output.resize(numPatterns);
165  output.clear();
166 
167  //matrix storing the class histogram for all patterns
168  UIntMatrix votes(numPatterns,m_classes);
169  votes.clear();
170 
171  //stores the votes of a classifier distinguishing between classes c and e
172  //for all patterns
173  UIntVector bin(numPatterns);
174  //accumulate histograms
175  for (unsigned int i=0, c=0; c<m_classes; c++)
176  {
177  for (std::size_t e=0; e<c; e++, i++)
178  {
179  m_binary[i]->eval(patterns,bin);
180  for(std::size_t p = 0; p != numPatterns; ++p){
181  if (bin[p] == 0)
182  votes(p,e)++;
183  else
184  votes(p,c)++;
185  }
186 
187  }
188  }
189  //find the maximum class for ever pattern
190  for(std::size_t p = 0; p != numPatterns; ++p){
191  for (unsigned int c=1; c < m_classes; c++){
192  if (votes(p,c) > votes(p,output(p)))
193  output(p) = c;
194  }
195  }
196  }
197 
198  /// from ISerializable, reads a model from an archive
199  void read(InArchive& archive)
200  {
201  archive & m_classes;
202  archive & m_binary;
203  }
204 
205  /// from ISerializable, writes a model to an archive
206  void write(OutArchive& archive) const
207  {
208  archive & m_classes;
209  //TODO: O.K. mit be leaking memory!!!
210  archive & m_binary;
211  }
212 
213 protected:
214  unsigned int m_classes; ///< number of classes to be distinguished
215  std::vector<binary_classifier_type*> m_binary; ///< list of binary classifiers
216 };
217 
218 
219 }
220 #endif