Мультиклассовая классификация

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

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

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

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

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

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

Преобразование в двоичный формат

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

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

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

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

Входы:

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

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

[1] Мохамед, Али (2005). «Обзор методов многоклассовой классификации» . Технический отчет, Калифорнийский технологический институт .

[bishop-2] Перейти обратно: ^а ^б ^с ^д ^и Бишоп, Кристофер М. (2006). Распознавание образов и машинное обучение . Спрингер.

[4] Экин, Чубук (2019). «Автодополнение: изучение стратегий увеличения на основе данных». Материалы конференции IEEE/CVF по компьютерному зрению и распознаванию образов .

[5] Кабир, Его Величество Дипу (2023 г.). «Уменьшение неопределенности активации класса с помощью справочной информации». arXiv : 2305.03238 [ cs.CV ].

[6] Венкатесан, Раджасекар; Мэн Джу, Эр (2016). «Новая прогрессивная методика обучения для многоклассовой классификации». Нейрокомпьютинг . 207 : 310–321. arXiv : 1609.00085 . дои : 10.1016/j.neucom.2016.05.006 . S2CID 12510650 .

[7] Венкатесан, Раджасекар. «Техника прогрессивного обучения» .

[8] Опиц, Юрий (2024). «Более пристальный взгляд на показатели классификационной оценки и критическое размышление об общей практике оценки» . Труды Ассоциации компьютерной лингвистики . 12 : 820–836. arXiv : 2404.16958 . дои : 10.1162/tacl_a_00675 .

[ 1 ]

[ 2 ]

[ примечание 1 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]