A comparison of some approaches to classification problems,and possibilities to construct optimal solutions efficiently

We consider sequential linear (binary) classifiers for the case of many classes along with the linear classifiers based on determining the maximum discriminant function. It is shown that the capabilities of sequential binary classifiers are wider than those of linear classifiers. For the case of linearly non-separable training samples there are considered approaches based on minimizing the margin of misclassification and minimizing empirical risk. It is shown that problem of minimizing the margin of misclassification is polynomially solvable for a certain choice of the norm in the feature space. A refined model of the empirical risk minimization problem and its continuous relaxation are considered, a comparison with the mathematical model of SVM is done. The results of numerical experiments comparing different approaches are discussed.