Skip to content

Instantly share code, notes, and snippets.

@luizfls
Last active October 8, 2017 19:44
Show Gist options
  • Save luizfls/24d3f8b5abdd31b0ffd540f72da4b5ba to your computer and use it in GitHub Desktop.
Save luizfls/24d3f8b5abdd31b0ffd540f72da4b5ba to your computer and use it in GitHub Desktop.
CS156 HW1 (perceptron)
#include <random>
#include <cmath>
#include <limits>
#include <vector>
#include <algorithm>
#include <iostream>
#define N 100
#define N_VALIDATION 100000
#define N_RUNS 1000
struct Point
{
double x1;
double x2;
};
std::random_device rd;
std::mt19937 rng(rd());
Point generateRandomPoint()
{
std::uniform_real_distribution<> dist(-1.0, std::nextafter(1.0, std::numeric_limits<double>::max()));
Point p;
p.x1 = dist(rng);
p.x2 = dist(rng);
return p;
}
int sign(double val)
{
if(val < 0)
return -1;
if(val > 0)
return +1;
return 0;
}
/**
* Classify points using the target function.
* The target function is a line, defined by two points: a and b.
* If a given point is above the line, it is classified with +1.
* If it is below the line, it is classified with -1.
*
* @param x Vector of points.
* @param a The first point of the line that represents the target function.
* @param b The second point of the line that represents the target function.
* @return Classified points (vector of -1s and +1s).
*/
std::vector<int> classify(const std::vector<Point>& x, const Point& a, const Point& b)
{
std::vector<int> y(x.size());
for(std::size_t i = 0; i < x.size(); ++i)
{
double targetx2 = a.x2 - (a.x1 - x[i].x1) / (a.x1 - b.x1) * (a.x2 - b.x2);
y[i] = x[i].x2 > targetx2 ? +1 : -1;
}
return y;
}
/**
* Classify points using the hypothesis.
*
* @param x Vector of points.
* @param w Perceptron weights.
* @return Classified points (vector of +1s, 0s or -1s).
*/
std::vector<int> classify(const std::vector<Point>& x, const std::vector<double>& w)
{
std::vector<int> y(x.size());
for(std::size_t i = 0; i < x.size(); ++i)
{
double dotp = w[0] + w[1] * x[i].x1 + w[2] * x[i].x2;
y[i] = sign(dotp);
}
return y;
}
/**
* Compares target classification with the hypothesis classification.
*
* @param y Points' classification according to target function.
* @param h Points' classification according to the hypothesis.
* @return Vector with indices of points where the classifications mismatch.
*/
std::vector<std::size_t> compare(const std::vector<int>& y, const std::vector<int>& h)
{
std::vector<std::size_t> mismatches;
for(std::size_t i = 0; i < y.size(); ++i)
if(y[i] != h[i])
mismatches.push_back(i);
return mismatches;
}
std::size_t getRandomIndex(const std::vector<std::size_t>& indices)
{
std::uniform_int_distribution<> dist(0, indices.size() - 1);
return indices[dist(rng)];
}
int main(void)
{
unsigned int runs = N_RUNS;
unsigned int totalIterations = 0;
double accMismatchRatio = 0.0;
while(runs-- > 0)
{
// target function points
Point a = generateRandomPoint();
Point b = generateRandomPoint();
// generate data set
std::vector<Point> x(N);
for(std::size_t i = 0; i < x.size(); ++i)
x[i] = generateRandomPoint();
// classify data set using target function
std::vector<int> y = classify(x, a, b);
// weights
std::vector<double> w(3, 0.0);
// learning
{
// perceptron learning algorithm
std::vector<int> h = classify(x, w);
std::vector<std::size_t> mismatches = compare(y, h);
while(!mismatches.empty())
{
totalIterations++;
std::size_t rnd_idx = getRandomIndex(mismatches);
w[0] += (y[rnd_idx]);
w[1] += (x[rnd_idx].x1 * y[rnd_idx]);
w[2] += (x[rnd_idx].x2 * y[rnd_idx]);
h = classify(x, w);
mismatches = compare(y, h);
}
}
// validating
{
// generate data set
std::vector<Point> x(N_VALIDATION);
for(std::size_t i = 0; i < x.size(); ++i)
x[i] = generateRandomPoint();
// classify data set using target function
std::vector<int> y = classify(x, a, b);
// classify data set using our final hypothesis, the trained perceptron.
std::vector<int> g = classify(x, w);
// compare results
double nMismatches = compare(y, g).size();
double mismatchRatio = nMismatches / x.size();
accMismatchRatio += mismatchRatio;
}
}
std::cout << (totalIterations / N_RUNS) << std::endl;
std::cout << (accMismatchRatio / N_RUNS) << std::endl;
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment