Об алгоритме Козинца

Аннотация

В 1964 г., на заре машинного обучения, Б.Н. Козинец предложил простой численный метод (алгоритм) для решения следующей экстремальной задачи. "В $n$-мерном евклидовом пространстве заданы два конечных множества $P_1$ и $P_2$. Предполагается, что соответствующие выпуклые оболочки $C_1$ и $C_2$ этих множеств не имеют общих точек. Требуется построить гиперплоскость, разделяющую множества $P_1$ и $P_2$, т.е. такую гиперплоскость, которая не имеет общих точек со множествами $C_1$ и $C_2$ и, кроме того, множества $C_1$ и $C_2$ лежат по разные стороны этой гиперплоскости. На самом деле, желательно среди всех гиперплоскостей, разделяющих множества $P_1$ и $P_2$, найти такую гиперплоскость, расстояние от которой до множества P1 ∪P2 имеет максимальную величину. Очевидно, что такой гиперплоскостью будет гиперплоскость, проходящая через середину отрезка, соединяющего какие-нибудь две ближайшие точки множеств $C_1$ и $C_2$, перпендикулярно к нему". В дальнейшем эту задачу стали называть задачей жесткого SVM-отделения (Support Vector Machine) двух конечных множеств. В алгоритме Козинца используется естественный геометрический вариант критерия оптимальности для рассматриваемой задачи. В данной статье приводится детальный анализ алгоритма Козинца с современных позиций. В частности, дано корректное доказательство его сходимости. Предложена рабочая схема алгоритма. Рассмотрены два примера, в которых сравнивается эффективность принципиальной и рабочей схем.

Ключевые слова:

машинное обучение, жесткое SVM-отделение, алгоритм Козинца, усеченные итерации