CS156 HW1 (perceptron)

PLA.cpp

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