/* This is a simple implementation of a linear Support Vector Machine for educational purposes. The algorithm bares a striking resemblance to a single-layer neural net, with the Support Vector Machine being called "the Perceptron of optimal stability." */ #include using namespace std; // DEFINE DOT FUNCTION :: F(X,W) = SUM(Xi * Wi) float dot(int x[], float w[], const int n) { float sum; for (int i = 0; i < n; i++) { sum += x[i] * w[i]; } return sum; } // DEFINE SIGN FUNCTION :: F(X) = 1 IF X > 0; 0 IF X = 0; -1 IF X < 0 int sign(float x) { if (x > 0) { return 1; } else if (x < 0) { return -1; } else { return 0; } } // DEFINE CLASSIFICATION FUNCTION (FOR USE AFTER TRAINING MODEL) int classify(int x[], float w[], const int n) { return sign(dot(x, w, n)); } // DEFINE PRINT FUNCTION (USING TEMPLATES, WE ARE ABLE TO PRINT ANY DATA TYPE WITH ONE FUNCTION) template void print(type x) { cout << x << endl; } // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - int main() { // INITIALIZE TRAINING DATA const int nsamples = 10; // THERE ARE 10 TRAINING SAMPLES (5 POSITIVE & 5 NEGATIVE) const int nfeatures = 10; // EACH SAMPLE CONTAINS 10 FEATURES (ATTRIBUTES OF A GIVEN CLASS) // POSITIVE SAMPLES int x[nsamples][nfeatures] = { {1,0,0,1,0,0,0,0,1,0}, // EACH (1) REPRESENTS THE PRESENCE OF A GIVEN FEATURE (eg. nose, eyes, lips, etc.) {1,1,0,0,0,1,1,0,0,1}, // EACH (0) REPRESENTS THE ABSENCE OF A GIVEN FEATURE {1,0,1,0,1,0,0,0,0,1}, {1,1,0,0,1,1,1,1,0,0}, {1,0,1,0,0,1,1,0,1,0}, /* IN THIS TRAINING SET, THE FIRST FEATURE IS OF MOST RELEVANCE. THE WEIGHTS SHOULD REFLECT THAT AFTER TRAINING. */ // NEGATIVE SAMPLES {0,1,1,0,0,1,1,0,0,1}, {0,0,1,0,1,1,1,0,1,0}, {0,1,0,0,0,1,1,0,0,0}, {0,0,1,1,1,0,0,1,0,1}, {0,1,1,1,0,1,1,0,1,1} }; // TARGET SIGN (ASSOCIATED OUTPUT / LABEL / CLASS) int y[nsamples][1] = { {1},{1},{1},{1},{1}, {-1},{-1},{-1},{-1},{-1} }; // INITIALIZE PARAMETERS float w[nfeatures] = { -0.07, 0.02, 0.1, -0.5, -0.07, 0.02, 0.1, -0.5, 0.01, -0.22 }; // WEIGHTS (ASSIGN RELEVANCE TO A GIVEN FEATURE) int epochs = 3000; // NUMBER OF TRAINING ITERATIONS float a = 0.001; // LEARNING RATE (a>0) // INITIALIZE PROCESS VARIABLES float pred; // VARIABLE TO HOLD CLASSIFIER PREDICTION DURING TRAINING float eval; // VARIABLE FOR COMPARING A PREDICTION TO ITS TARGET // INITIALIZE LEARNING PROCESS for (int c = 0; c < epochs; c++) { // RUN THROUGH EACH SAMPLE IN THE TRAINING SET for (int j = 0; j < nsamples; j++) { // CLASSIFIER PREDICTION pred = dot(x[j], w, nfeatures); // EVALUATE FOR SAME SIGN (+X * +1) & (-X * -1) eval = pred * y[j][0]; // IF CORRECTLY CLASSIFIED if (eval >= 1) { // FOR EACH INPUT FEATURE AND ITS CORRESPONDING WEIGHT for (int k = 0; k < nfeatures; k++) { // WEIGHT - (LEARNING_RATE * WEIGHT) w[k] -= a * w[k]; } } // IF MISCLASSIFIED else { // FOR EACH INPUT FEATURE AND ITS CORRESPONDING WEIGHT for (int k = 0; k < nfeatures; k++) { // WEIGHT + (LEARNING_RATE * INPUT_FEATURE * TARGET_SIGN) w[k] += a * x[j][k] * y[j][0]; } } } } // PRINT CLASSIFICATION OF TRAINING DATA for (int i = 0; i < nsamples; i++) { print(classify(x[i], w, nfeatures)); } print("\n"); // PRINT CLASSIFICATION OF TEST DATA (UNSEEN SAMPLE NOT INCLUDED IN TRAINING SET) int test[nfeatures] = { 0,1,0,0,1,0,0,1,0 }; print(classify(test, w, nfeatures)); print("\n"); // PRINT LEARNED WEIGHT VALUES (THE FIRST WEIGHT SHOULD BE LARGEST AS THE FIRST INPUT FEATURE IS THE MOST RELEVANT) for (int i = 0; i < nfeatures; i++) { print(w[i]); } return 0; }