Многоклассовая классификация

В машинном обучении и статистической классификации многоклассовая классификация или полиномиальная классификация — это проблема классификации экземпляров в один из трех или более классов (классификация экземпляров в один из двух классов называется бинарной классификацией ). Например, решение о том, показывает ли изображение банан, апельсин или яблоко, является проблемой многоклассовой классификации с тремя возможными классами (банан, апельсин, яблоко), в то время как решение о том, содержит ли изображение яблоко или нет, является проблемой бинарной классификации (с двумя возможными классами: яблоко, нет яблока).

Хотя многие алгоритмы классификации (в частности, полиномиальная логистическая регрессия ) естественным образом допускают использование более двух классов, некоторые из них по своей природе являются бинарными алгоритмами; однако их можно превратить в полиномиальные классификаторы с помощью различных стратегий.

Многоклассовую классификацию не следует путать с многометковой классификацией , когда для каждого экземпляра необходимо предсказать несколько меток (например, предсказать, что изображение содержит и яблоко, и апельсин, в предыдущем примере).

Общие стратегии

Существующие методы многоклассовой классификации можно разделить на следующие категории:

преобразование в двоичный код
расширение из двоичного
иерархическая классификация. ^[1]

Преобразование в двоичный код

В этом разделе обсуждаются стратегии сведения проблемы многоклассовой классификации к нескольким проблемам бинарной классификации. Их можно разделить на категории один против остальных и один против одного . Методы, разработанные на основе сведения многоклассовой проблемы к нескольким бинарным проблемам, также можно назвать методами преобразования проблем.

Один против остальных

Стратегия «один против всех» ^[2]^{: 182, 338} (OvR или один против всех , OvA или один против всех , OAA) подразумевает обучение одного классификатора на класс, причем образцы этого класса являются положительными, а все остальные образцы — отрицательными. Эта стратегия требует, чтобы базовые классификаторы выдавали реальную оценку для своего решения (см. также правило оценки ), а не просто метку класса; отдельные метки классов сами по себе могут приводить к неоднозначностям, когда для одного образца предсказываются несколько классов. ^[2]^{: 182}^{[примечание 1]}

В псевдокоде алгоритм обучения для обучающегося OvR, построенного на основе обучающегося двоичной классификации $L,$ выглядит следующим образом:

Входные данные:

$L$ , обучающийся (алгоритм обучения для бинарных классификаторов)
образцы $X$
метки $y$ , где $y i$ ∈ {1, … $K$ } — метка для выборки $X i$

Выход:

список классификаторов $f k$ для $k$ ∈ {1, …, $K$ }

Процедура:

Для каждого k из {1, …, K }
- Построить новый вектор меток $z$ , где $z i$ = $y i,$ если $y i = k,$ и $z i = 0$ в противном случае.
- Применить $L$ к $X$ , $z,$ чтобы получить $f k$

Принятие решений означает применение всех классификаторов к неизвестному образцу $x$ и прогнозирование метки $k,$ для которой соответствующий классификатор сообщает наивысшую оценку достоверности:

{\hat {y}}={\underset {k\in \{1\ldots K\}}{\arg \!\max }}\;f_{k}(x)

Хотя эта стратегия популярна, это эвристика , которая страдает от нескольких проблем. Во-первых, масштаб значений достоверности может различаться между бинарными классификаторами. Во-вторых, даже если распределение классов сбалансировано в обучающем наборе, обучающиеся бинарной классификации видят несбалансированные распределения, поскольку обычно набор отрицательных значений, которые они видят, намного больше набора положительных значений. ^[2]^{: 338}

Один на один

В сокращении один против одного (OvO) обучают $K (K - 1) / 2$ бинарных классификаторов для $K$ -way мультиклассовой проблемы; каждый получает образцы пары классов из исходного обучающего набора и должен научиться различать эти два класса. Во время прогнозирования применяется схема голосования: все $K (K - 1) / 2$ классификаторов применяются к невидимому образцу, и класс, получивший наибольшее количество предсказаний «+1», прогнозируется объединенным классификатором. ^[2]^{: 339}

Как и OvR, OvO страдает от неоднозначности, поскольку некоторые регионы его входного пространства могут получать одинаковое количество голосов. ^[2]^{: 183}

Расширение из двоичного файла

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

Нейронные сети

Многоклассовые персептроны обеспечивают естественное расширение многоклассовой проблемы. Вместо того, чтобы иметь только один нейрон в выходном слое с бинарным выходом, можно иметь N двоичных нейронов, что приводит к многоклассовой классификации. На практике последний слой нейронной сети обычно представляет собой слой функции softmax , который является алгебраическим упрощением N логистических классификаторов, нормализованных на класс суммой N-1 других логистических классификаторов. Классификация на основе нейронной сети принесла значительные улучшения и возможности для размышлений с разных точек зрения. ^[3]^[4]

Экстремальные обучающиеся машины

Машины экстремального обучения (ELM) — это особый случай нейронных сетей с прямым распространением с одним скрытым слоем (SLFN), в которых входные веса и смещения скрытых узлов могут выбираться случайным образом. Для многоклассовой классификации в ELM внесено множество изменений и разработок.

k-ближайших соседей

k-ближайших соседей kNN считается одним из старейших непараметрических алгоритмов классификации. Для классификации неизвестного примера измеряется расстояние от этого примера до каждого другого обучающего примера. Определяются k наименьших расстояний, и наиболее представленный класс этими k ближайшими соседями считается меткой выходного класса.

Наивный Байес

Наивный Байес — это успешный классификатор, основанный на принципе максимума апостериори (MAP). Этот подход естественным образом расширяется на случай наличия более двух классов и, как было показано, хорошо работает, несмотря на базовое упрощающее предположение об условной независимости .

Деревья решений

Обучение дерева решений — это мощный метод классификации. Дерево пытается вывести разделение обучающих данных на основе значений доступных признаков для получения хорошего обобщения. Алгоритм может естественным образом обрабатывать проблемы бинарной или многоклассовой классификации. Конечные узлы могут ссылаться на любой из соответствующих классов K.

Машины опорных векторов

Машины опорных векторов основаны на идее максимизации маржи, т.е. максимизации минимального расстояния от разделяющей гиперплоскости до ближайшего примера. Базовый SVM поддерживает только бинарную классификацию, но были предложены расширения для обработки случая многоклассовой классификации. В этих расширениях к задаче оптимизации добавляются дополнительные параметры и ограничения для обработки разделения различных классов.

Программирование с несколькими выражениями

Программирование с несколькими выражениями (MEP) — это эволюционный алгоритм для генерации компьютерных программ (которые также могут использоваться для задач классификации). MEP имеет уникальную особенность: он кодирует несколько программ в одну хромосому. Каждая из этих программ может использоваться для генерации выходных данных для класса, что делает MEP естественным образом подходящим для решения задач классификации нескольких классов.

Иерархическая классификация

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

Парадигмы обучения

На основе парадигм обучения существующие методы многоклассовой классификации можно разделить на пакетное обучение и онлайн-обучение . Алгоритмы пакетного обучения требуют, чтобы все образцы данных были доступны заранее. Он обучает модель, используя все обучающие данные, а затем предсказывает тестовый образец, используя найденную взаимосвязь. С другой стороны, алгоритмы онлайн-обучения постепенно строят свои модели в последовательных итерациях. На итерации t онлайн-алгоритм получает образец x _t и предсказывает его метку ŷ _t, используя текущую модель; затем алгоритм получает y _t , истинную метку x _{t ,} и обновляет свою модель на основе пары образец-метка: (x _t , y _t ). Недавно была разработана новая парадигма обучения, называемая прогрессивным методом обучения. ^[5] Прогрессивный метод обучения способен не только обучаться на новых образцах, но и способен обучаться новым классам данных и при этом сохранять знания, полученные на данный момент. ^[6]

Оценка

Производительность многоклассовой системы классификации часто оценивается путем сравнения прогнозов системы с эталонными метками с оценочной метрикой. Обычные оценочные метрики — это точность или макро F1 . ^[7]

Смотрите также

Примечания

^ В многоклассовой классификации OvR известен как бинарная релевантность , а предсказание нескольких классов считается признаком, а не проблемой.

Ссылки

^ Мохамед, Али (2005). «Обзор методов многоклассовой классификации». Технический отчет, Калтех .
^ abcde Бишоп, Кристофер М. (2006). Распознавание образов и машинное обучение . Springer.
^ Экин, Кубук (2019). «Автодополнение: изучение стратегий дополнения на основе данных». Труды конференции IEEE/CVF по компьютерному зрению и распознаванию образов .
^ Кабир, Х. М. Дипу (2023). «Снижение неопределенности активации класса с помощью фоновой информации». arXiv : 2305.03238 [cs.CV].
^ Венкатесан, Раджасекар; Менг Джу, Эр (2016). «Новый прогрессивный метод обучения для многоклассовой классификации». Neurocomputing . 207 : 310–321. arXiv : 1609.00085 . doi : 10.1016/j.neucom.2016.05.006. S2CID 12510650.
^ Венкатесан, Раджасекар. «Техника прогрессивного обучения».
^ Опиц, Юри (2024). «Более пристальный взгляд на метрики оценки классификации и критическое отражение общей практики оценки». Труды Ассоциации компьютерной лингвистики . 12 : 820–836. arXiv : 2404.16958 . doi : 10.1162/tacl_a_00675.