Here is the result of my efforts for obtaining the Master of Science degree at the Université Laval in the Master's degree computer science program. My memoir is entitled: "Nouveaux algorithmes d'apprentissage pour classificateurs de type SCM". Its abstract is given in the frame below.
In the supervised machine learning field, one of the available tools for binary classification is the Set Covering Machine (SCM). Quickly built and generally having high performance, it's however not proven that they always give optimal results. There is still, to date, a margin for improvement.
This study presents two new ways of building SCM. Theses algorithms are described, explained and their performance is analyzed. The first way is to minimize an approximated bound on the risk with a branch-and-bound. The second is using bagging.
The new classifiers had the same test-set performance than the original SCM. We discovered that the latter are either already optimal according to the branch-and-bound criterion or having the same performance as the optimal SCM.
During my work, I've implemented the search in a text with the Boyer-Moore algorithm in C++.