Распознавание образов — это задача присвоения класса наблюдению на основе образов, извлеченных из данных. Несмотря на схожесть, распознавание образов (PR) не следует путать с машинами по распознаванию образов (PM), которые могут обладать возможностями (PR), но их основная функция — различать и создавать возникающие образы. PR применяется в статистическом анализе данных , обработке сигналов , анализе изображений , поиске информации , биоинформатике , сжатии данных , компьютерной графике и машинном обучении . Распознавание образов берет свое начало в статистике и инженерии; некоторые современные подходы к распознаванию образов включают использование машинного обучения из-за возросшей доступности больших данных и нового изобилия вычислительной мощности .
Системы распознавания образов обычно обучаются на основе помеченных «тренировочных» данных. Когда помеченные данные недоступны, можно использовать другие алгоритмы для обнаружения ранее неизвестных образов. KDD и интеллектуальный анализ данных больше фокусируются на неконтролируемых методах и более тесно связаны с бизнес-использованием. Распознавание образов больше фокусируется на сигнале, а также учитывает сбор и обработку сигнала . Оно возникло в инженерии , и этот термин популярен в контексте компьютерного зрения : ведущая конференция по компьютерному зрению называется Conference on Computer Vision and Pattern Recognition .
В машинном обучении распознавание образов — это назначение метки заданному входному значению. В статистике дискриминантный анализ был введен для этой же цели в 1936 году. Примером распознавания образов является классификация , которая пытается назначить каждое входное значение одному из заданного набора классов (например, определить, является ли заданное электронное письмо «спамом»). Распознавание образов — более общая проблема, которая охватывает и другие типы выходных данных. Другими примерами являются регрессия , которая назначает действительное выходное значение каждому входному значению; [1] маркировка последовательностей , которая назначает класс каждому члену последовательности значений [2] (например, разметка частей речи , которая назначает часть речи каждому слову во входном предложении); и синтаксический анализ , который назначает дерево синтаксического анализа входному предложению, описывающее синтаксическую структуру предложения. [3]
Алгоритмы распознавания образов обычно нацелены на предоставление разумного ответа для всех возможных входных данных и выполнение «наиболее вероятного» сопоставления входных данных с учетом их статистической вариации. Это противоположно алгоритмам сопоставления образов , которые ищут точные совпадения во входных данных с уже существующими образами. Распространенным примером алгоритма сопоставления образов является сопоставление регулярных выражений , которое ищет образцы заданного вида в текстовых данных и включено в возможности поиска многих текстовых редакторов и текстовых процессоров .
Современное определение распознавания образов:
Область распознавания образов занимается автоматическим обнаружением закономерностей в данных с помощью компьютерных алгоритмов и использованием этих закономерностей для выполнения таких действий, как классификация данных по различным категориям. [4]
Распознавание образов обычно классифицируется в соответствии с типом процедуры обучения, используемой для генерации выходного значения. Контролируемое обучение предполагает, что был предоставлен набор обучающих данных ( обучающий набор ), состоящий из набора экземпляров, которые были правильно помечены вручную с правильным выходом. Затем процедура обучения генерирует модель, которая пытается достичь двух иногда противоречивых целей: выполнять как можно лучше на обучающих данных и как можно лучше обобщать на новые данные (обычно это означает быть настолько простым, насколько это возможно, для некоторого технического определения «простого», в соответствии с бритвой Оккама , обсуждаемой ниже). Неконтролируемое обучение , с другой стороны, предполагает обучающие данные, которые не были помечены вручную, и пытается найти присущие им закономерности в данных, которые затем можно использовать для определения правильного выходного значения для новых экземпляров данных. [5] Комбинация этих двух методов, которая была изучена, — это полуконтролируемое обучение , которое использует комбинацию маркированных и немаркированных данных (обычно небольшой набор маркированных данных в сочетании с большим количеством немаркированных данных). В случаях неконтролируемого обучения обучающие данные могут вообще отсутствовать.
Иногда для описания соответствующих контролируемых и неконтролируемых процедур обучения для одного и того же типа выходных данных используются разные термины. Неконтролируемый эквивалент классификации обычно известен как кластеризация , основанная на общем восприятии задачи как не включающей в себя обучающие данные, о которых можно было бы говорить, и группировании входных данных в кластеры на основе некоторой присущей меры сходства (например, расстояния между экземплярами, рассматриваемыми как векторы в многомерном векторном пространстве ), а не назначения каждого входного экземпляра одному из набора предопределенных классов. В некоторых областях терминология отличается. В экологии сообществ термин классификация используется для обозначения того, что обычно известно как «кластеризация».
Часть входных данных, для которой генерируется выходное значение, формально называется экземпляром . Экземпляр формально описывается вектором признаков , которые вместе составляют описание всех известных характеристик экземпляра. Эти векторы признаков можно рассматривать как определяющие точки в соответствующем многомерном пространстве , и к ним можно соответствующим образом применять методы манипулирования векторами в векторных пространствах , такие как вычисление скалярного произведения или угла между двумя векторами. Признаки обычно являются либо категориальными (также известными как номинальные , т. е. состоящими из одного из набора неупорядоченных элементов, таких как пол «мужской» или «женский» или группа крови «A», «B», «AB» или «O»), порядковыми (состоящими из одного из набора упорядоченных элементов, например, «большой», «средний» или «маленький»), целочисленными (например, подсчет количества вхождений определенного слова в электронном письме) или вещественными (например, измерение артериального давления). Часто категориальные и порядковые данные группируются вместе, и это также касается целочисленных и действительных данных. Многие алгоритмы работают только с категориальными данными и требуют, чтобы действительные или целочисленные данные были дискретизированы в группы (например, меньше 5, от 5 до 10 или больше 10).
Многие распространенные алгоритмы распознавания образов являются вероятностными по своей природе, поскольку они используют статистический вывод для поиска лучшей метки для данного экземпляра. В отличие от других алгоритмов, которые просто выводят «лучшую» метку, часто вероятностные алгоритмы также выводят вероятность того , что экземпляр будет описан данной меткой. Кроме того, многие вероятностные алгоритмы выводят список N -лучших меток с соответствующими вероятностями для некоторого значения N , а не просто одну лучшую метку. Когда количество возможных меток довольно мало (например, в случае классификации ), N может быть установлено так, чтобы выводилась вероятность всех возможных меток. Вероятностные алгоритмы имеют много преимуществ перед невероятностными алгоритмами:
Алгоритмы выбора признаков пытаются напрямую отсечь избыточные или нерелевантные признаки. Было дано общее введение в выбор признаков , которое суммирует подходы и проблемы. [6] Сложность выбора признаков, из-за его немонотонного характера, является проблемой оптимизации , где задано общее количество признаков, powerset, состоящий из всех подмножеств признаков, должен быть исследован. Алгоритм Branch-and-Bound [7] действительно уменьшает эту сложность, но является неразрешимым для средних и больших значений количества доступных признаков
Методы преобразования необработанных векторов признаков ( извлечение признаков ) иногда используются до применения алгоритма сопоставления с образцом. Алгоритмы извлечения признаков пытаются сократить вектор признаков большой размерности до вектора меньшей размерности, с которым проще работать и который кодирует меньше избыточности, используя математические методы, такие как анализ главных компонент (PCA). Различие между выбором признаков и извлечением признаков заключается в том, что полученные после извлечения признаков признаки отличаются от исходных признаков и могут быть нелегко интерпретируемыми, в то время как признаки, оставшиеся после выбора признаков, являются просто подмножеством исходных признаков.
Проблему распознавания образов можно сформулировать следующим образом: задана неизвестная функция ( основная истина ), которая сопоставляет входные экземпляры с выходными метками , вместе с обучающими данными, которые, как предполагается, представляют точные примеры сопоставления, создать функцию , которая максимально точно аппроксимирует правильное сопоставление . (Например, если проблема заключается в фильтрации спама, то является некоторым представлением электронной почты и является либо «спамом», либо «не спамом»). Для того чтобы это была четко определенная проблема, необходимо строго определить «максимально точно аппроксимирует». В теории принятия решений это определяется путем указания функции потерь или функции затрат, которая присваивает определенное значение «потерям», возникающим в результате создания неправильной метки. Цель состоит в том, чтобы минимизировать ожидаемые потери, при этом ожидание принимается по распределению вероятностей . На практике ни распределение , ни функция истинности не известны точно, но могут быть вычислены только эмпирически путем сбора большого количества образцов и ручной маркировки их с использованием правильного значения (процесс, требующий много времени, который обычно является ограничивающим фактором в количестве данных такого рода, которые могут быть собраны). Конкретная функция потерь зависит от типа прогнозируемой метки. Например, в случае классификации часто достаточно простой функции потерь «ноль-один» . Это соответствует простому назначению потери 1 любой неправильной маркировке и подразумевает, что оптимальный классификатор минимизирует частоту ошибок на независимых тестовых данных (т. е. подсчитывает долю случаев, которые обученная функция маркирует неправильно, что эквивалентно максимизации числа правильно классифицированных случаев). Цель процедуры обучения тогда состоит в минимизации частоты ошибок (максимизации правильности ) на «типичном» тестовом наборе.
Для вероятностного распознавателя образов проблема заключается в оценке вероятности каждой возможной выходной метки при заданном входном экземпляре, т.е. в оценке функции вида
где входной вектор признаков — , а функция f обычно параметризуется некоторыми параметрами . [8] В дискриминативном подходе к проблеме f оценивается напрямую. Однако в генеративном подходе вместо этого оценивается обратная вероятность и объединяется с априорной вероятностью с использованием правила Байеса следующим образом:
Когда метки распределены непрерывно (например, в регрессионном анализе ), знаменатель включает интеграцию , а не суммирование:
Значение обычно изучается с использованием оценки максимального апостериорного значения (MAP). Это находит наилучшее значение, которое одновременно удовлетворяет двум конфликтующим целям: максимально эффективно на обучающих данных (наименьшая частота ошибок ) и нахождение максимально простой возможной модели. По сути, это объединяет оценку максимального правдоподобия с процедурой регуляризации , которая отдает предпочтение более простым моделям по сравнению с более сложными. В байесовском контексте процедуру регуляризации можно рассматривать как размещение априорной вероятности на различных значениях . Математически:
где — значение, используемое в последующей процедуре оценки, а апостериорная вероятность определяется как
В байесовском подходе к этой проблеме вместо выбора одного вектора параметров вероятность заданной метки для нового экземпляра вычисляется путем интегрирования по всем возможным значениям , взвешенным в соответствии с апостериорной вероятностью:
Первый классификатор шаблонов — линейный дискриминант, представленный Фишером — был разработан в частотной традиции. Частотный подход подразумевает, что параметры модели считаются неизвестными, но объективными. Затем параметры вычисляются (оцениваются) из собранных данных. Для линейного дискриминанта этими параметрами являются именно средние векторы и ковариационная матрица . Также вероятность каждого класса оценивается из собранного набора данных. Обратите внимание, что использование « правила Байеса » в классификаторе шаблонов не делает подход к классификации байесовским.
Байесовская статистика берет свое начало в греческой философии, где уже было сделано различие между знанием « априори » и знанием « апостериори ». Позднее Кант определил свое различие между тем, что известно априори — до наблюдения — и эмпирическим знанием, полученным из наблюдений. В байесовском шаблонном классификаторе вероятности классов могут быть выбраны пользователем, которые затем являются априорными. Более того, опыт, количественно определенный как априорные значения параметров, может быть взвешен с помощью эмпирических наблюдений — с использованием, например, бета- ( сопряженного априорного ) и распределения Дирихле . Байесовский подход способствует бесшовному смешиванию экспертных знаний в форме субъективных вероятностей и объективных наблюдений.
Вероятностные классификаторы шаблонов могут использоваться в соответствии с частотным или байесовским подходом.
В медицинской науке распознавание образов является основой для систем компьютерной диагностики (САПР). САПР описывает процедуру, которая поддерживает интерпретации и выводы врача. Другие типичные применения методов распознавания образов — это автоматическое распознавание речи , идентификация говорящего , классификация текста по нескольким категориям (например, спам или не спам-сообщения электронной почты), автоматическое распознавание рукописного текста на почтовых конвертах, автоматическое распознавание изображений человеческих лиц или извлечение изображений рукописного текста из медицинских форм. [9] [10] Последние два примера образуют подтему анализа изображений распознавания образов, которая имеет дело с цифровыми изображениями в качестве входных данных для систем распознавания образов. [11] [12]
Оптическое распознавание символов является примером применения классификатора шаблонов. Метод подписи имени человека был зафиксирован с помощью стилуса и наложения, начиная с 1990 года. [ необходима цитата ] Штрихи, скорость, относительный минимум, относительный максимум, ускорение и давление используются для уникальной идентификации и подтверждения личности. Банкам впервые предложили эту технологию, но они были согласны взимать с FDIC за любое банковское мошенничество и не хотели причинять неудобства клиентам. [ необходима цитата ]
Распознавание образов имеет множество реальных применений в обработке изображений. Вот некоторые примеры:
В психологии распознавание образов используется для понимания и идентификации объектов и тесно связано с восприятием. Это объясняет, как сенсорные входы, которые получают люди, становятся осмысленными. Распознавание образов можно рассматривать двумя разными способами. Первый касается сопоставления шаблонов, а второй касается обнаружения признаков. Шаблон — это шаблон, используемый для создания элементов тех же пропорций. Гипотеза сопоставления шаблонов предполагает, что входящие стимулы сравниваются с шаблонами в долговременной памяти. Если есть совпадение, стимул идентифицируется. Модели обнаружения признаков, такие как система классификации букв Pandemonium (Selfridge, 1959), предполагают, что стимулы разбиваются на составные части для идентификации. Одно наблюдение — заглавная буква E, имеющая три горизонтальные линии и одну вертикальную линию. [22]
Алгоритмы распознавания образов зависят от типа выходных данных метки, от того, является ли обучение контролируемым или неконтролируемым, и от того, является ли алгоритм статистическим или нестатистическим по своей природе. Статистические алгоритмы могут быть далее классифицированы как генеративные или дискриминационные .
Параметрический: [23]
Непараметрический: [24]
Без присмотра:
{{cite journal}}
: CS1 maint: multiple names: authors list (link).{{cite book}}
: CS1 maint: multiple names: authors list (link){{cite journal}}
: Цитировать журнал требует |journal=
( помощь )