//===========================================================================
/*!
*
*
* \brief One-versus-one Classifier.
*
*
*
* \author T. Glasmachers
* \date 2012
*
*
* \par Copyright 1995-2017 Shark Development Team
*
*
* This file is part of Shark.
*
*
* Shark is free software: you can redistribute it and/or modify
* it under the terms of the GNU Lesser General Public License as published
* by the Free Software Foundation, either version 3 of the License, or
* (at your option) any later version.
*
* Shark 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 Lesser General Public License for more details.
*
* You should have received a copy of the GNU Lesser General Public License
* along with Shark. If not, see .
*
*/
//===========================================================================
#ifndef SHARK_MODELS_ONEVERSUSONE_H
#define SHARK_MODELS_ONEVERSUSONE_H
#include
namespace shark {
///
/// \brief One-versus-one Classifier.
///
/// \par
/// The one-versus-one classifier combines a number of binary
/// classifiers to form a multi-class ensemble classifier.
/// In the one-versus-one model, there exists one binary
/// classifier for each pair of classes. The predictions of
/// all binary machines are combined with a simple voting
/// scheme.
///
/// \par
/// The classifier can be extended to handle more classes on
/// the fly, without a need for re-training the existing
/// binary models.
///
template
class OneVersusOneClassifier : public AbstractModel
{
public:
typedef AbstractModel base_type;
typedef AbstractModel binary_classifier_type;
typedef LabeledData dataset_type;
typedef typename base_type::BatchInputType BatchInputType;
typedef typename base_type::BatchOutputType BatchOutputType;
/// \brief Constructor
OneVersusOneClassifier()
: m_classes(1)
{ }
/// \brief From INameable: return the class name.
std::string name() const
{ return "OneVersusOneClassifier"; }
/// get internal parameters of the model
virtual VectorType parameterVector() const{
std::size_t total = numberOfParameters();
VectorType ret(total);
std::size_t used = 0;
for (std::size_t i=0; inumberOfParameters();
noalias(subrange(ret, used, used + n)) = m_binary[i]->parameterVector();
used += n;
}
return ret;
}
/// set internal parameters of the model
virtual void setParameterVector(VectorType const& newParameters) {
SHARK_RUNTIME_CHECK(numberOfParameters() == newParameters.size(),"Invalid number of parameters");
std::size_t used = 0;
for (std::size_t i=0; inumberOfParameters();
m_binary[i]->setParameterVector(subrange(newParameters, used, used + n));
used += n;
}
}
/// return the size of the parameter vector
virtual std::size_t numberOfParameters() const{
std::size_t ret = 0;
for (std::size_t i=0; inumberOfParameters();
return ret;
}
/// return number of classes
unsigned int numberOfClasses() const
{ return m_classes; }
Shape inputShape() const{
return m_binary.empty()? Shape() : m_binary[0]->inputShape();
}
Shape outputShape() const{
return Shape({m_classes});
}
/// \brief Obtain binary classifier.
///
/// \par
/// The method returns the binary classifier used to distinguish
/// class_one from class_zero. The convention class_one > class_zero
/// is used (the inverse classifier can be constructed from this one
/// by flipping the labels). The binary classifier outputs a value
/// of 1 for class_one and a value of zero for class_zero.
binary_classifier_type const& binary(unsigned int class_one, unsigned int class_zero) const{
SHARK_ASSERT(class_zero < class_one);
SHARK_ASSERT(class_one < m_classes);
unsigned int index = class_one * (class_zero - 1) / 2 + class_zero;
return *m_binary[index];
}
/// \brief Add binary classifiers for one more class to the model.
///
/// The parameter binmodels holds a vector of n binary classifiers,
/// where n is the current number of classes. The i-th model is this
/// list is supposed to output a value of 1 for class n and a value
/// of 0 for class i when faced with the binary classification problem
/// of separating class i from class n. Afterwards the model can
/// predict the n+1 classes {0, ..., n}.
void addClass(std::vector const& binmodels)
{
SHARK_RUNTIME_CHECK(binmodels.size() == m_classes, "[OneVersusOneClassifier::addClass] wrong number of binary models");
m_classes++;
m_binary.insert(m_binary.end(), binmodels.begin(), binmodels.end());
}
boost::shared_ptr createState()const{
return boost::shared_ptr(new EmptyState());
}
using base_type::eval;
/// One-versus-one prediction: evaluate all binary classifiers,
/// collect their votes, and return the class with most votes.
void eval(
BatchInputType const & patterns, BatchOutputType& output, State& state
)const{
std::size_t numPatterns = batchSize(patterns);
output.resize(numPatterns);
output.clear();
//matrix storing the class histogram for all patterns
UIntMatrix votes(numPatterns,m_classes);
votes.clear();
//stores the votes of a classifier distinguishing between classes c and e
//for all patterns
UIntVector bin(numPatterns);
//accumulate histograms
for (unsigned int i=0, c=0; ceval(patterns,bin);
for(std::size_t p = 0; p != numPatterns; ++p){
if (bin[p] == 0)
votes(p,e)++;
else
votes(p,c)++;
}
}
}
//find the maximum class for ever pattern
for(std::size_t p = 0; p != numPatterns; ++p){
for (unsigned int c=1; c < m_classes; c++){
if (votes(p,c) > votes(p,output(p)))
output(p) = c;
}
}
}
/// from ISerializable, reads a model from an archive
void read(InArchive& archive)
{
archive & m_classes;
archive & m_binary;
}
/// from ISerializable, writes a model to an archive
void write(OutArchive& archive) const
{
archive & m_classes;
//TODO: O.K. might be leaking memory!!!
archive & m_binary;
}
protected:
unsigned int m_classes; ///< number of classes to be distinguished
std::vector m_binary; ///< list of binary classifiers
};
}
#endif