Perceptron learning algorithm with Pocket implementation with heuristic
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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