Perceptron learning algorithm with Pocket implementation with heuristic

main.cpp

#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;
}