Skip to content

Instantly share code, notes, and snippets.

@EmmanuelMess
Created July 13, 2018 14:50
Show Gist options
  • Save EmmanuelMess/d8081fdd14daa17b7ca34f642eaf9688 to your computer and use it in GitHub Desktop.
Save EmmanuelMess/d8081fdd14daa17b7ca34f642eaf9688 to your computer and use it in GitHub Desktop.
Perceptron learning algorithm 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));
}
};
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.size() << "]{";
for (int i = 0; i < obj.w.size(); i++) {
if(i == obj.w.size()-1) {
strm << "(θ) ";
}
strm << obj.w[i];
if(i < obj.w.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));
}
/**
* 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;
andDatapoints(inputs);//Change datapoints for different trainings
Perceptron p(inputs);
cout << p << endl;
T epsilon = 1;
int total = 0;
restart:
for(int 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;
goto restart;
}
} else {
if (p.compute(x) <= 0) {
p += (delta+epsilon)/x.length()*x;
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