Статистическая обучаемость стратегических линейных классификаторов: Пошаговое доказательство

Статья исследует понятие стратегического размера VC (SVC) и его связь с Основной Теоремой Стратегического Обучения. SVC используется для оценки выразительной силы класса гипотез в контексте стратегической классификации. В линейной классификации размер VC класса гипотез конечен, что делает его обучаемым по PAC. Однако, когда вводятся функции стоимости для отдельных экземпляров, SVC расходится со своим каноническим аналогом, и линейная классификация становится не общей PAC-обучаемой. В статье доказывается, что при использовании функции стоимости для отдельных экземпляров SVC становится бесконечным, что делает линейную классификацию в стратегическом контексте не PAC-обучаемой. Доказательство включает в себя построение выпуклого многоугольника для каждой точки данных, который представляет собой маркировки, в которых она положительно классифицируется. Многоугольник используется для определения функции стоимости для отдельных экземпляров, которая определяет поведение точек данных относительно линейных классификаторов. Функция стоимости спроектирована так, чтобы точка данных всегда хотела манипулировать своим вектором признаков, чтобы гарантировать, что она попадает на положительную сторону границы решений. Статья заключает, что стратегическая линейная классификация не является PAC-обучаемой, даже в самых простых случаях, из-за функции стоимости для отдельных экземпляров.