Résumé
Motivated by recent researches in metagenomic classification tasks, this paper investigates the problem of finding interpretable concepts from training data in which the number of features is larger than the number of samples. In this setting, the classification problem is modeled as a combinatorial optimization problem, in which the aim of the learner is to find a {−1, 0, +1}-weighted linear threshold function that minimizes the hinge loss induced from the training data. Two methods are analyzed and experimented: convex optimization that applies randomized rounding to the optimum in the convex hull of the concept class, and supermodular minimization that performs a local search in the concept class, with a guarantee on the approximate solution for the subclass of {0, 1}-weighted threshold functions.