Perceptron learning algorithm with Pocket implementation with heuristic
#include <iostream> | |
#include <vector> | |
#include <random> | |
enum Halfspace {N, P}; | |
typedef double T; | |
class VectorWrongSizeException : public std::exception { | |
const char* what() const noexcept override { | |
return "Different vector sizes!"; | |
} | |
}; | |
class MissingDatapointsException : public std::exception { | |
const char* what() const noexcept override { | |
return "You need at least one datapoint for the negative halfspace and one for the positive halfspace!"; | |
} | |
}; | |
class Vector : public std::vector<T> { | |
public: | |
explicit Vector(size_t size) : std::vector<T>(size) { } | |
explicit Vector(const vector<T>& v) : std::vector<T>(v) { } | |
void operator+=(const Vector& o) { | |
if(size() != o.size()) { | |
throw VectorWrongSizeException(); | |
} | |
for (size_t i = 0; i < size(); i++) { | |
(*this)[i] += o[i]; | |
} | |
} | |
void operator-=(const Vector& o) { | |
if(size() != o.size()) { | |
throw VectorWrongSizeException(); | |
} | |
for (size_t i = 0; i < size(); i++) { | |
(*this)[i] -= o[i]; | |
} | |
} | |
T operator*(const Vector& o) const {//scalar product | |
T r = 0; | |
for (size_t i = 0; i < size(); i++) { | |
r += (*this)[i] * o[i]; | |
} | |
return r; | |
} | |
Vector operator/(T o) const { | |
Vector newV(size()); | |
for (size_t i = 0; i < size(); i++) { | |
newV[i] = (*this)[i] / o; | |
} | |
return newV; | |
} | |
friend Vector operator*(T o, const Vector& v); | |
Vector operator-() { | |
Vector newV(size()); | |
for (size_t i = 0; i < size(); ++i) { | |
newV[i] = -(*this)[i]; | |
} | |
return newV; | |
} | |
T length() { | |
T r = 0; | |
for (size_t i = 0; i < size(); ++i) { | |
r += (*this)[i]*(*this)[i]; | |
} | |
return static_cast<T>(sqrtl(r)); | |
} | |
friend std::ostream &operator<<(std::ostream& strm, const Vector& obj); | |
}; | |
Vector operator*(T o, const Vector& v) { | |
Vector newV(v.size()); | |
for (size_t i = 0; i < v.size(); i++) { | |
newV[i] = v[i] * o; | |
} | |
return newV; | |
} | |
class Perceptron { | |
Vector w; | |
public: | |
explicit Perceptron(std::vector<std::pair<Vector, Halfspace>>& inputs) : w(inputs[0].first.size()) { | |
Vector p(w.size()); int lengthP = 0; | |
Vector n(w.size()); int lengthN = 0; | |
for (auto &input : inputs) { | |
if(input.second == Halfspace::N) { | |
p += input.first; | |
lengthN++; | |
} else { | |
n += input.first; | |
lengthP++; | |
} | |
} | |
if(lengthP == 0 || lengthN == 0) { | |
throw MissingDatapointsException(); | |
} | |
w = (p/lengthP); | |
w -= (n/lengthN); | |
} | |
T compute(const Vector &x) { | |
if(x.size() != w.size()) { | |
throw VectorWrongSizeException(); | |
} | |
T sum = 0; | |
for (int i = 0; i < x.size(); ++i) { | |
sum += w[i] * x[i]; | |
} | |
return sum; | |
} | |
void operator+=(const Vector& o) { | |
w += o; | |
} | |
void operator-=(const Vector& o) { | |
w -= o; | |
} | |
Vector weights() { | |
return w; | |
} | |
friend std::ostream &operator<<(std::ostream& strm, const Perceptron& obj); | |
}; | |
std::ostream &operator<<(std::ostream& strm, const Perceptron& obj) { | |
strm << obj.w << "[Θ = " << obj.w.back() << "]"; | |
} | |
std::ostream &operator<<(std::ostream& strm, const Vector& obj) { | |
strm << "[" << obj.size() << "]{"; | |
for (int i = 0; i < obj.size(); i++) { | |
strm << obj[i]; | |
if(i < obj.size()-1) { | |
strm << ", "; | |
} | |
} | |
strm << "}"; | |
} | |
void andDatapoints(std::vector<std::pair<Vector, Halfspace>>& inputs) { | |
inputs.push_back(std::pair<Vector, Halfspace>(Vector({0, 0, 1}), Halfspace::N)); | |
inputs.push_back(std::pair<Vector, Halfspace>(Vector({0, 1, 1}), Halfspace::N)); | |
inputs.push_back(std::pair<Vector, Halfspace>(Vector({1, 0, 1}), Halfspace::N)); | |
inputs.push_back(std::pair<Vector, Halfspace>(Vector({1, 1, 1}), Halfspace::P)); | |
} | |
void orDatapoints(std::vector<std::pair<Vector, Halfspace>>& inputs) { | |
inputs.push_back(std::pair<Vector, Halfspace>(Vector({0, 0, 1}), Halfspace::N)); | |
inputs.push_back(std::pair<Vector, Halfspace>(Vector({0, 1, 1}), Halfspace::P)); | |
inputs.push_back(std::pair<Vector, Halfspace>(Vector({1, 0, 1}), Halfspace::P)); | |
inputs.push_back(std::pair<Vector, Halfspace>(Vector({1, 1, 1}), Halfspace::P)); | |
} | |
void firstParameterFunctionDatapoints(std::vector<std::pair<Vector, Halfspace>>& inputs) { | |
inputs.push_back(std::pair<Vector, Halfspace>(Vector({0, 0, 1}), Halfspace::N)); | |
inputs.push_back(std::pair<Vector, Halfspace>(Vector({0, 1, 1}), Halfspace::N)); | |
inputs.push_back(std::pair<Vector, Halfspace>(Vector({1, 0, 1}), Halfspace::P)); | |
inputs.push_back(std::pair<Vector, Halfspace>(Vector({1, 1, 1}), Halfspace::P)); | |
} | |
/** | |
* Random | |
*/ | |
void oDatapoints(std::vector<std::pair<Vector, Halfspace>>& inputs) { | |
inputs.push_back(std::pair<Vector, Halfspace>(Vector({0, 0, 1}), Halfspace::N)); | |
inputs.push_back(std::pair<Vector, Halfspace>(Vector({0.5, 1.4, 1}), Halfspace::N)); | |
inputs.push_back(std::pair<Vector, Halfspace>(Vector({1, 1.7, 1}), Halfspace::N)); | |
inputs.push_back(std::pair<Vector, Halfspace>(Vector({1, 1, 1}), Halfspace::N)); | |
inputs.push_back(std::pair<Vector, Halfspace>(Vector({2, 1.8, 1}), Halfspace::N)); | |
inputs.push_back(std::pair<Vector, Halfspace>(Vector({2.8, 1.55, 1}), Halfspace::P)); | |
inputs.push_back(std::pair<Vector, Halfspace>(Vector({3, 1.2, 1}), Halfspace::P)); | |
inputs.push_back(std::pair<Vector, Halfspace>(Vector({3, -0.5, 1}), Halfspace::P)); | |
inputs.push_back(std::pair<Vector, Halfspace>(Vector({1.5, -0.5, 1}), Halfspace::P)); | |
} | |
/** | |
* Impossible | |
*/ | |
void xorDatapoints(std::vector<std::pair<Vector, Halfspace>>& inputs) { | |
inputs.push_back(std::pair<Vector, Halfspace>(Vector({0, 0, 1}), Halfspace::N)); | |
inputs.push_back(std::pair<Vector, Halfspace>(Vector({0, 1, 1}), Halfspace::P)); | |
inputs.push_back(std::pair<Vector, Halfspace>(Vector({1, 0, 1}), Halfspace::P)); | |
inputs.push_back(std::pair<Vector, Halfspace>(Vector({1, 1, 1}), Halfspace::N)); | |
} | |
int main() { | |
using std::cout; | |
using std::cin; | |
using std::endl; | |
std::vector<std::pair<Vector, Halfspace>> inputs; | |
oDatapoints(inputs);//Change datapoints for different trainings | |
Perceptron p(inputs); | |
cout << p << endl; | |
T epsilon = 1; | |
Vector wS = p.weights(); | |
size_t hS = 0; | |
int total = 0; | |
restart: | |
size_t failed = 0; | |
for(size_t i = 0; i < inputs.size(); i++, total++) { | |
Vector x = inputs[i].first; | |
T delta = -p.weights() * x; | |
if(inputs[i].second == Halfspace::N) { | |
if (p.compute(x) >= 0) { | |
p += (delta-epsilon)/x.length()*x; | |
if(failed == 0 && i > hS) { | |
hS = i; | |
wS = p.weights(); | |
cout << "New best: " << wS << endl; | |
} | |
failed++; | |
} | |
} else { | |
if (p.compute(x) <= 0) { | |
p += (delta+epsilon)/x.length()*x; | |
if(failed == 0 && i > hS) { | |
hS = i; | |
wS = p.weights(); | |
cout << "New best: " << wS << endl; | |
} | |
failed++; | |
} | |
} | |
} | |
if(failed > 0) goto restart; | |
cout << p << endl; | |
cout << "Tries: " << total << endl; | |
for (const auto &x : inputs) { | |
cout << "(" << x.first[0] << ", " << x.first[1] << ") = " << p.compute(x.first) << endl; | |
} | |
return 0; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment