Project Title

This repository contains the implementation of OLLAWV, an online Support Vector Machine solver. Copyright (C) 2018-2020 Gabriella Melki ([email protected]), Vojislav Kecman ([email protected]), All Rights Reserved. If you find this code useful, please cite the folowing:

@article{melki2018ollawv,
  title={OLLAWV: online learning algorithm using worst-violators},
  author={Melki, Gabriella and Kecman, Vojislav and Ventura, Sebastian and Cano, Alberto},
  journal={Applied Soft Computing},
  volume={66},
  pages={384--393},
  year={2018},
  publisher={Elsevier}
}

Introduction

To address the limitations presented by current popular SVM solvers, we developed novel OnLine Learning Algorithm using Worst-Violators (OLLAWV). The key contributions of OLLAWV include:

• A unique iterative procedure for solving the L1-SVM problem, as well as a novel method for identifying support vectors, or worst-violators. Rather than randomly iterating over the data samples, OLLAWV aims to reduce training time by selecting and updating the samples that are most incorrectly classified with respect to the current decision hyper-plane.

• A novel stopping criteria by utilizing the worst-violator identification method. This aims to eliminate the added parameterization that is included with most online methods, where the number of iterations of the algorithm needs to be set in advance. Once there are no incorrectly classified samples left, the algorithm terminates.

Getting Started

These instructions will get you a copy of the project up and running on your local machine for development and testing purposes. The project uses VSCode as it's IDE and CMake for building and running.

Installs

• CMake install

• VSCode install

  • Extension C/C++ - ms-vscode.cpptools
  • Extension CMake - ms-vscode.cmake-tools

• Boost install

  • Windows getting-started | cmake-test

    1. Download and extract Boost

    2. Add the following path to your environment variables C:\Boost

    3. Navigate to the newly extracted Boost folder within your terminal/cmd

    4. Run the following:

       bootstrap.bat
       .\b2 address-model=32 architecture=x86 --build-type=complete --with-program_options --with-test --with-log toolset=msvc link=shared install

  • Linux

    wget https://dl.bintray.com/boostorg/release/1.73.0/source/boost_1_73_0.tar.gz
    tar -xvzf boost_1_73_0.tar.gz
    cd boost_1_73_0
    ./bootstrap.sh
    sudo ./b2 --toolset=gcc --build-type=complete --layout=versioned --with-program_options --with-test --with-log --with-date_time link=shared install
    vim ~/.bashrc
    # add the following and save the file
    export LD_LIBRARY_PATH="/usr/local/lib:$LD_LIBRARY_PATH"
    # restart the terminal
    rm -rf boost_1_73_0.tar.gz

• GSL windows | linux

  • Windows:

    • git clone https://github.com/microsoft/vcpkg.git
    • cd vcpkg
    • .\bootstrap-vcpkg.bat
    • .\vcpkg integrate install
    • .\vcpkg install gsl gsl:x64-windows
    • Add environment variable GSL_ROOT with value: C:path\to\vcpkg\packages\gsl_x64-windows
    • For more information on vcpkg visit here.

  • Linux:

    libgsl-dev/focal,now 2.5+dfsg-6build1 amd64 [installed]
    libgsl-dev/focal 2.5+dfsg-6build1 i386

Configure

Configure VSCode with your preferred C++ IDE settings.

Setup

1. Clone this repository.
2. Build Ctrl+Shift+B or use the VSCode CMake extension.
   1. Be sure to select your config. These are already set up in the Launch.json file or CMakeLists.txt
3. Debug, Run, or Test
   1. Debug: F5
   2. Run: enter the following in the terminal

bin/Release/osvm -i 5 -o 5 /path/to/data # Run
test/bin/Debug/osvm_unit_tests -i 5 -i 5 -d true -t /path/to/output/json /path/to/data # Test

Project Details

.
├── bin                   # Debug/osvm and Release/osvm executables
├── build                 # cmake dir
├── src                   # source code files
│   ├── data
│   ├── feature
│   ├── logging
│   ├── math
│   ├── model
│   ├── svm
│   ├── time
│   ├── configuration.cc
│   ├── configuration.h
│   ├── launcher.cc
│   ├── launcher.h
│   ├── osvm.cc           # main file
│   └── osvm.h
├── test                  # boost unit tests
│   ├── bin               # Debug/osvm and Release/osvm test executables
│   ├── examples          # json files with true example outputs
│   ├── CMakeLists.txt    # test cmake config
│   ├── osvm_test.cc      # main test file
│   └── osvm_test.h
├── .vscode               # vscode configurations
│   ├── c_cpp_properties.json # c++ configurations (edit to your liking)
│   ├── launch.json       # launch/attach configurations for debugging
│   ├── settings.json     # general vscode settings 
│   └── tasks.json        # build instructions for each release (debug,release,test)
├── CMakeLists.txt        # cmake config for main project
├── .gitattributes
├── .gitignore
├── IssueTemplate.md
└── README.md

Authors

• Gabriella Melki

See also the list of contributors who participated in this project.

Acknowledgments

• Hat tip to Robert Strack.
• All the love for Vojo.
• Inspiration from Andrew Ritz.