Задача классификации

В формальной постановке задачи классификации имеется множество объектов ${\displaystyle X}$ и множество ответов ${\displaystyle Y}$. Предполагается, что существует функциональная зависимость ${\displaystyle f:X\rightarrow Y}$ между объектами и ответами, но она неизвестна. Известна лишь совокупность ${\displaystyle S}$ пар вида (объект, ответ), называемая обучающей выборкой:

${\displaystyle S=\left\{(x_{i},{y_{x}}_{i}=f(x_{i}))\in \;X\times Y\ |\ i=1,\ldots ,l\right\}}$.

При этом множество ответов ${\displaystyle Y}$ является конечным, а каждый ответ ${\displaystyle y\in Y}$ соответствует некоторому классу объектов.

Задача классификации заключается в вычислении для каждого объекта соответствующего ему класса. Качество алгоритма решения задачи классификации измеряют с помощью метрик на тестовой выборке, которая не использовалась для обучения.

В 1960-х гг. оформилась область прикладной статистики, посвящённая методам классификации. Алгоритмы классификации в машинном обучении развивались в несколько этапов.

В 1957 г. Ф. Розенблаттом разработан перцептрон – первый основанный на искусственной нейронной сети алгоритм классификации.

В 1988 г. Я. Лекун применил метод обратного распространения ошибки для обучения глубоких нейронных сетей. Такие алгоритмы требовали больших вычислительных мощностей. Известная задача классификации тех лет – классификация изображений символов MNIST.

Метод опорных векторов (англ. Support Vector Machine) разработан в компании AT&T группой учёных во главе с В. Н. Вапником в 1995 г. Метод оказался эффективен для простых задач классификации, но при использовании больших данных работал хуже.

В 1995 г. исследователь компании IBM Тин Кан Хо (Хо Тхинькхам) предложил объединять несколько алгоритмов «решающее дерево». Так началось развитие семейства алгоритмов под устоявшимся названием «случайный лес». Американский статистик Джером Фридман в 1999 г. создал т. н. градиентный бустинг – алгоритм, основанный на использовании «деревьев». Подобные алгоритмы востребованы в задаче классификации доныне.

С развитием технологий, улучшением камер смартфонов и удешевлением цифровых фотоаппаратов становилось доступно всё больше данных для обучения. Одновременно росли и вычислительные возможности: процессоры становились мощнее, в качестве вычислительного инструмента стали использоваться графические процессоры. Нейросетевые алгоритмы снова начали активно развиваться. В 2009 г. было опубликовано соревнование ImageNet, где одной из задач была классификация изображений. На тот момент в нём было представлено 3,2 млн изображений различных объектов. В течение многих лет исследователи обновляли рекорд по качеству классификации на ImageNet с помощью нейросетей. Ныне, в 2020-х гг., именно нейросети наиболее эффективно решают задачу классификации для изображений, текста и аудио.

Примеры задач, которые могут быть поставлены как задача классификации, приведены в таблице.

Примеры задач классификации