Главная
База знаний "Allbest"
Программирование, компьютеры и кибернетика
Методы распознавания образов при идентификации объектов бинарного класса в автоматизированных телекоммуникационных комплексах систем управления
Методы распознавания образов при идентификации объектов бинарного класса в автоматизированных телекоммуникационных комплексах систем управления
Основные цели и задачи построения систем распознавания. Построение математической модели системы распознавания образов на примере алгоритма идентификации объектов военной техники в автоматизированных телекоммуникационных комплексах систем управления.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | дипломная работа |
| Язык | русский |
| Дата добавления | 30.11.2012 |
| Размер файла | 332,2 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Линейная разделяющая функция, минимизирующая вероятность ошибки решения.
Линейные классификаторы представляют собой простейшие классификаторы, поскольку их реализация непосредственно связана со многими известными методами классификации, такими, как корреляционные методы или методы, основанные на вычислении евклидовых расстояний. Однако линейные классификаторы оптимальны в байесовском смысле только для нормальных распределений с равными корреляционными матрицами. Для некоторых приложений, таких, как выделение полезного сигнала в системах связи, равенство корреляционных матриц является приемлемым предположением, так как при изменении сигнала свойства шума существенно не изменяются. Однако во многих других приложениях распознавания образов предположение о равенстве ковариаций не оправдано.
Предпринимались различные попытки разработки линейных классификаторов для нормальных распределений с неравными корреляционными матрицами и для распределений, отличных от нормального. Разумеется, эти классификаторы не являются оптимальными, однако во многих случаях их простота служит достаточной компенсацией ухудшения качества классификации.
Рассмотрим методы создания линейных классификаторов для этих более сложных случаев. Так как оговорено, что независимо то вида распределений используется линейный классификатор, то решающее правило должно иметь вид
. (1.33)
Выражение h(x) есть линейная разделяющая функция относительно x. Задача синтеза классификатора заключается в том, чтобы для заданных распределений определить коэффициенты VT=[v1, v2, …, vn] и значение порога v0, оптимальные по различным критериям.
Если случайная величина h(x) распределена по нормальному или близкому к нему закону, то для вычисления вероятности ошибки можно использовать её математическое ожидание и дисперсию для классов C1 и C2, а затем выбрать параметры V и v0 так, чтобы минимизировать ошибку решения. Так как h(x) является суммой, состоящей из n слагаемых xi, приходим к выводу [3]:
1) если векторы x имеют нормальное распределение, то величина h(x) также имеет нормальное распределение;
2) даже если векторы x распределены не по нормальному закону, но при большом n выполнены условия центральной предельной теоремы, то распределение величины h(x) может быть близко к нормальному.
Математические ожидания и дисперсии величины h(x) в классах C1 и C2 равны
Mi = VTmi + v0, (1.34)
у2i = VTУiV. (1.35)
Поэтому вероятность ошибки можно записать следующим образом:
. (1.36)
Если требуется минимизировать риск R, то вместо вероятностей P(C1) и P(C2) в формуле (1.36) должны быть использованы величины r12P(C1) и r21P(C2). При такой замене предполагается, что r11 = r22 = 0.
Продифференцировав выражение (1.36) по параметрам V и v0, получим, что
, (1.37)
при этом h=0 и M2-M1 = [(m2/у22)У2-(m1/у21)У1].
Кусочно-линейные разделяющие функции.
Линейные разделяющие функции находят широкое применение в задачах распознавания образов для случая двух классов, хотя при этом неизбежна некоторая потеря качества распознавания. Однако при трёх или более классах качество распознавания с использованием линейной разделяющей функции часто оказывается неприемлемым.
Если в этих случаях воспользоваться совокупностью линейных разделяющих функций, т.е. воспользоваться кусочно-линейной разделяющей функцией, то появляются дополнительные возможности улучшения качества распознавания [3]. На рис. 6 изображён пример задачи распознавания для случая четырёх классов.
- 4 -
Размещено на http://www.allbest.ru/
Размещено на http://www.allbest.ru/
В задачах со многими классами критерии проверки многих гипотез дают наилучшее в байесовском смысле решающее правило, обеспечивающее минимум риска или вероятности ошибки. В соответствии с критерием проверки гипотез плотность вероятности или её логарифм следует сравнивать с плотностями вероятности других классов, как следует из (1.11). На рис. 6,а изображены полученные таким образом границы. Если оценивание плотностей вероятности является слишком сложной задачей или границы, определяемые в соответствии с критерием проверки гипотез, слишком “вычурные”, то можно заменить эти сложные границы множеством простых линейных границ. Такая замена, конечно, приводит к некоторому ухудшению качества распознавания. Однако использование линейных границ особенно эффективно для задач распознавания многих классов, т.е. в тех случаях, когда сложность границ быстро возрастает с увеличением числа классов, и является желательным некоторое упрощение процедуры синтеза классификатора [3]. На рис. 6,б показана замена байесовских границ кусочно-линейными границами.
Множество линейных функций, соответствующее кусочно-линейной разделяющей функции, определяется следующим образом:
hij(x) = VTijx + vi0, i, j = 1, 2, …, M, i ? j, (1.38)
где M - число классов. Знаки Vij выбираются так, чтобы распределение класса i находилось в области положительных значений линейной функции hij(x), а распределение класса j - в области отрицательных значений. Из этого требования следует, что
hij(x) = hji(x). (1.39)
Предположим, что для каждого класса соответствующая область является выпуклой, как изображено на рис. 6,б, тогда область класса i может быть просто определена следующим образом:
hi1(x) > 0, hi2(x) > 0, …, hiM(x) > 0 > xC1 (1.40)
(функция hii(x) исключена из рассмотрения). Наличие тёмной области на рисунке 6,б показывает, что M областей, определяемые условиями (390), не обязательно покрывают всё пространство. Если объект попадает в эту область, то кусочно-линейный классификатор не может принять решение о его принадлежности к определённому классу; эту область называют областью отказов. Решающее правило состоит из M-1 линейных разделяющих функций и логического элемента AND с M-1 входами, которые принимают значения sign{hij(x)}. Соответствующая блок-схема изображена на рис. 7. Поскольку каждая из параллельных цепей состоит из двух последовательно соединённых элементов, то такой кусочно-линейный классификатор иногда называют двухслойной машиной.
Если предположение о выпуклости областей не выполняется, то необходимо определить взаимные пересечения M-1 гиперплоскостей и строить решающее правило в соответствии с этими пересечениями. Однако при этом классификатор становится весьма сложным для решения практических задач.
- 4 -
Размещено на http://www.allbest.ru/
Размещено на http://www.allbest.ru/
Вероятность ошибки решения для каждого класса еi можно выразить через (M-1)-мерную функцию распределения вероятности:
(1.41)
(функция hii исключена из рассмотрения.). Тогда общая ошибка решения
. (1.42)
Задача теперь состоит в том, чтобы определить значения V и v0 для данного множества M распределений при наличии информации о структуре кусочно-линейного классификатора. Вследствие сложности этой задачи её решение не является таким наглядным, как для линейного классификатора.
Кратко отметим несколько приближённых методов решения задачи [3].
1) Можно подстраивать коэффициенты V и v0 так, чтобы минимизировать вероятность ошибки решения е, определяемую формулой (1.41).
2) Линейная разделяющая функция между парой классов строится с помощью одного из методов, рассмотренных ранее для случая распознавания двух классов. Вычисляются M(M-1)/2 разделяющих функций. Эти функции без дальнейшей коррекции используются в качестве кусочно-линейной разделяющей функции. Если распределения являются нормальными с равными корреляционными матрицами, то описанная процедура эквивалентна применению байесовского решающего правила. Если распределения существенно отличаются между собой, то дальнейшая коррекция решающего правила может привести к уменьшению ошибки. Однако часто оказывается, что уменьшение ошибки за счёт подстройки параметров V и v0 относительно невелико.
Обобщенные линейные разделяющие функции.
До сих пор были рассмотрены линейные разделяющие функции. Одна из причин этого заключается в том, что при высокой размерности наблюдаемых векторов только линейные или кусочно-линейные разделяющие функции дают приемлемый компромисс между качеством распознавания и простотой реализации.
Другая важная причина состоит в том, что даже нелинейная разделяющая функция может быть интерпретирована в функциональном пространстве как линейная, т.е. выражение
(1.43)
представляет собой в функциональном пространстве линейную разделяющую функцию, где r переменных gi(x) заменяют n переменных x в исходном пространстве.
Другим важным случаем является использование квадратичных поверхностей, где r переменных gi(x) задают так, что первыми n переменными являются x2i, i=1, 2, …, n, следующими n(n-1)/2 - все пары xixj, i, j=1, 2, …, n, i?j, а последние n переменных представляют собой xi, i=1, 2, …, n. Относительно этого преобразования можно сказать, что для каждой квадратичной разделяющей функции в пространстве x существует соответствующая линейная разделяющая функция в пространстве функций gj(x).
Переменные gi(x) являются признаками. Выбор эффективной системы признаков представляет собой самостоятельный раздел теории распознавания образов.
1.4.5 Оценивание параметров
Как говорилось выше, если известны плотности вероятности классов, то для классификации объектов можно определить граничную поверхность, разделяющую пространство признаков на области. Следующий вопрос заключается в том, как по имеющейся выборке объектов оценить эти плотности вероятности? Эта задача является очень сложной, если нельзя сделать предположение о структуре многомерной плотности вероятности. Однако если можно задать вид этой функции, то задача сводится к определению конечного числа параметров. Для этого можно использовать известные статистические методы оценки параметров. Оценивание параметров плотностей вероятности известного вида и классификацию объектов на основе этих плотностей называют параметрическим методом классификации [3].
Первая задача, которая здесь возникает, заключается в оценке основных параметров плотностей вероятности, таких, как вектор математического ожидания, корреляционная матрица и т.д., в предположении, что эти параметры не являются случайными величинами. Далее следует рассмотреть случай, когда эти параметры - случайные величины. Такие задачи называют точечным оцениванием [3].
Другой важный вопрос в распознавании образов - оценка вероятности ошибок решения и отношения правдоподобия. Поскольку вероятности ошибок и отношение правдоподобия представляют собой сложные функции относительно параметров, непосредственное применение для них стандартных методов оценивания не даёт приемлемых результатов. Поэтому имеет смысл рассмотреть методы оценивания этих величин по имеющимся выборочным данным.
Оценивание неслучайных параметров.
Пусть И и - соответственно истинный вектор параметров и его оценка. Значение есть функция от наблюдаемых случайных векторов x1, x2, …, xN, т.е.
, (1.44)
где .
Оценка называется несмещённой оценкой параметра И, если её математическое ожидание равно истинному значению параметра, т.е.
. (1.45)
Оценка называется состоятельной оценкой параметра И, если сходится по вероятности к И, т.е.
. (1.46)
Оценка называется эффективной оценкой параметра И, если для всех возможных оценок
. (1.47)
Оценка называется достаточной оценкой параметра И, если она содержит всю информацию о И, содержащуюся в наблюдаемых объектах, т.е. - достаточная оценка тогда и только тогда, когда для любых других оценок (для которых якобиан соответствующего преобразования не равен нулю) условная плотность вероятности оценок при фиксированной оценке не зависит от параметра И:
. (1.48)
Таким образом, наилучшая оценка из тех, которые можно найти, должна быть несмещённой, состоятельной, эффективной и достаточной.
Оценки моментов.
Основными параметрами, характеризующими плотность вероятности, являются моменты. В качестве их оценок используют выборочные моменты.
Общий выборочный момент порядка i1+i2+…+in определяется как среднее от моментов порядка i1+i2+…+in отдельных случайных выборочных объектов
, (1.49)
где - k-я компонента j-го объекта.
Математическое ожидание оценки (1.49) вычислить нетрудно, оно равно истинному значению искомого момента распределения, а дисперсия (1.49) равна
, (1.50)
где - дисперсия отдельного случайного объекта (в предположении, что наблюдаемые объекты независимы и одинаково распределены).
Таким образом, выборочный момент представляет собой несмещённую состоятельную оценку.
В большинстве приложений внимание сосредоточено на моментах первого и второго порядка - выборочном векторе средних значений и выборочной автокорреляционной матрице, которые определяются соответственно следующим образом:
, (1.51)
. (1.52)
Формулы (1.51) и (1.52) - частные случаи формулы (1.49), поэтому оценки математического ожидания и автокорреляционной матрицы являются несмещёнными и состоятельными.
Ситуация несколько меняется, когда рассматривают центральные моменты, такие, как дисперсии и корреляционные матрицы. Определим оценку корреляционной матрицы следующим образом:
. (1.53)
Математическое ожидание оценки равно , отсюда видно, что такая оценка корреляционной матрицы является смещённой. Это смещение можно устранить с помощью следующей модифицированной оценки корреляционной матрицы:
. (1.54)
Нижнюю границу дисперсии любой несмещённой оценки можно определить с помощью следующего неравенства, называемого границей Крамера - Рао:
(1.55)
(в предположении, что обе производные существуют и абсолютно интегрируемы).
Любая несмещённая оценка, при которой в (1.55) имеет место равенство, является эффективной оценкой.
Оценка максимального правдоподобия.
Более общим методом точечного оценивания является выбор при наблюдаемой величине Z такой оценки, которая максимизирует условную плотность вероятности p(Z/И), или ln p(Z/И). Иначе говоря, выбирается значение параметра И, при котором Z является наиболее правдоподобным результатом. Ясно, что эта оценка есть функция вектора Z. Логарифмическая функция рассматривается для удобства вычислений и, будучи монотонной, не изменяет точки максимума. Эту оценку называют оценкой максимального правдоподобия. Она представляет собой решение следующих эквивалентных уравнений:
,
или
(1.56)
Эти уравнения называют уравнениями правдоподобия.
Можно показать, что если существует эффективная оценка (т.е. выполняется условие (1.55)), то она будет оценкой максимального правдоподобия.
Оценивание случайных параметров.
Когда оценивание параметры представляют собой случайные величины, делается попытка минимизировать математическое ожидание функции ошибки между случайными параметрами и их оценками.
Байесовская оценка.
Пусть И и - соответственно оцениваемый параметр и случайная оценка, основанная на наблюдениях . Тогда можно ввести функцию штрафа так, чтобы средний риск оценки выражался следующим образом:
, (1.57)
где r(*) - функция штрафа, зависящая от случайного параметра И и его оценки . Величину R называют байесовским риском, а оценку, минимизирующую байесовский риск - байесовской оценкой.
Хотя байесовская оценка является весьма общей и обладает свойством оптимальности в смысле минимума среднего риска, получить её в явном виде, как правило, нелегко. Поэтому такие оценки получены для некоторых функций штрафа.
1) Оценка, минимизирующая среднеквадратичную ошибку
В качестве функции штрафа можно использовать величину
. (1.58)
При этом байесовский риск (1.57) превращается в среднеквадратичную ошибку оценки . Минимизируя выражение (1.57) при условии (1.58) и при фиксированном векторе наблюдений Z, получим
. (1.59)
Таким образом, оценка минимизирующая среднеквадратичную ошибку, представляет собой вектор математического ожидания апостериорной плотности вероятности.
Вообще говоря, выражение (1.59) справедливо для всех функций штрафа, обладающих свойствами симметричности и выпуклости, если апостериорная плотность вероятности является симметричной функцией относительно условного математического ожидания, т.е.
, (1.60)
где И'=И-M{И/Z}.
2) Оценка, максимизирующая апостериорную вероятность.
Пусть функция штрафа имеет следующий вид:
(1.61)
где параметр д и область ДЦ выбраны достаточно малыми так, чтобы условную плотность вероятности p(И/Z) можно было считать постоянной в данной области. Пусть ДV - объём области ДЦ. Тогда выражение (1.57) можно переписать в виде
. (1.62)
Подынтегральное выражение в (1.62) является неотрицательным. Поэтому риск R можно минимизировать, если оценку выбрать равной значению параметра И, которое максимизирует апостериорную плотность вероятности p(И/Z). Другими словами, эта оценка есть решение уравнения
или
. (1.63)
Такую оценку называют оценкой, максимизирующей апостериорную вероятность.
1.5.6 Оценивание вероятности ошибки
Вероятность ошибки является основным показателем качества распознавания образов, и поэтому её оценивание представляет собой очень важную задачу. Вероятность ошибки есть сложная функция, представляющая собой n-кратный интеграл от плотности вероятности при наличии сложной границы. Поэтому при её вычислении часто приходится обращаться к экспериментальным методам.
При оценке вероятности ошибки рассматривают две задачи. Первая из них состоит в оценивании вероятности ошибки по имеющейся выборке в предположении, что задан классификатор [3].
Вторая задача заключается в оценке вероятности ошибки при заданных распределениях. Для этой ошибки вероятность ошибки зависит как от используемого классификатора, так и от вида распределения. Поскольку в распоряжении имеется конечное число объектов, нельзя построить оптимальный классификатор. Поэтому параметры такого классификатора представляют собой случайные величины [3].
Оценка вероятности ошибки для заданного классификатора.
1) Неизвестны априорные вероятности - случайная выборка.
Предположим, что заданы распределения обоих классов и классификатор. Задача заключается в оценивании вероятности ошибки по N объектам, полученным в соответствии с этими распределениями.
Когда неизвестны априорные вероятности P(Ci), i=1, 2, то можно случайно извлечь N объектов и проверить, даёт ли данный классификатор правильные решения для этих объектов. Такие объекты называют случайной выборкой.
Пусть ф - число объектов, неправильно классифицированных в результате этого эксперимента. Величина ф есть дискретная случайная величина. Обозначим истинную вероятность ошибки через е. Распределение значений величины ф является биномиальным:
. (1.64)
Оценка максимального правдоподобия из уравнения (1.56) равна
, (1.65)
т.е. оценка максимального правдоподобия равна отношению числа неправильно классифицированных объектов к общему числу объектов.
Математическое ожидание и дисперсия биномиального распределения соответственно равны
, (1.66)
. (1.67)
Таким образом, оценка является несмещённой.
2) Известны априорные вероятности - селективная выборка.
Если известны априорные вероятности классов P(Ci), i=1, 2, то можно извлечь N1=P(C1)N и N2=P(C2)N объектов соответственно и проверить их с помощью заданного классификатора. Такой процесс известен как селективная выборка. Пусть ф1 и ф2 - число неправильно классифицированных объектов соответственно из классов C1 и C2. Поскольку ф1 и ф2 взаимно независимы, то совместная плотность вероятности ф1 и ф2 будет равна
, (1.68)
где еi - истинная вероятность ошибки для класса Ci. В этом случае оценка максимального правдоподобия равна
. (1.69)
Математическое ожидание и дисперсия оценки соответственно
, (1.70)
. (1.71)
Таким образом, оценка (1.69) также несмещённая.
Нетрудно показать, что дисперсия (1.71) меньше, чем дисперсия (1.67). Это естественный результат, поскольку в случае селективной выборки используется априорная информация.
Изложенное выше легко обобщить на случай M классов. Для этого надо лишь изменить верхние пределы у сумм и произведений в формулах (1.68) - (1.71) с 2 на M.
Оценка вероятности ошибки, когда классификатор заранее не задан.
Когда даны N объектов в случае отсутствия классификатора, то можно использовать эти объекты как для проектирования классификатора, так и для проверки его качества. Очевидно, оцениваемая вероятность ошибки зависит от данных распределений и используемого классификатора.
Предположим, что всегда используется байесовский классификатор, минимизирующий вероятность ошибки. Тогда минимальную вероятность ошибки байесовского классификатора, которую необходимо оценить, можно рассматривать как фиксированный параметр при заданных распределениях. Кроме того, эта вероятность является минимальной для данных распределений.
Как правило, вероятность ошибки есть функция двух аргументов:
е (И1, И2), (1.72)
где И1 - множество параметров распределений, используемых для синтеза байесовского классификатора, а И2 - множество параметров распределений, используемых для проверки его качества.
Оптимальная классификация объектов, характеризуемых распределением с параметром И2, осуществляется байесовским классификатором, который построен для распределения с параметром И2. Поэтому
е (И2, И2) ? е (И1, И2). (1.73)
Пусть для данной задачи И - вектор истинных параметров, а - его оценка. Таким образом, оценка является случайным вектором и е0=е (И, И). Для любого конкретного значения оценки на основании (1.73) справедливы неравенства
, (1.74)
. (1.75)
Выполнив над обеими частями неравенств (1.74) и (1.75) операцию математического ожидания, получим
, (1.76)
. (1.77)
Если
, (1.78)
то для вероятности ошибки байесовского классификатора имеет место двустороннее ограничение
. (1.79)
Левое неравенство (1.79) основано на предположении (1.78) и не доказано для произвольных истинных плотностей вероятности. Однако это неравенство можно проверить многими экспериментальными способами. Из выражения (1.5) видно, что равенство (1.78) выполняется тогда, когда оценка проверяемой плотности вероятности, основанная на N наблюдениях, является несмещённой и классификатор заранее фиксирован. Следует отметить, что нижняя граница менее важна, чем верхняя.
Обе границы вероятности ошибки можно интерпретировать следующим образом:
1) : одни и те же N объектов используются и для синтеза байесовского классификатора, и для последующей классификации. Этот случай назовём C-методом. Из (1.79) следует, что C-метод даёт, вообще говоря, заниженную оценку вероятности ошибки.
2) : для синтеза байесовского классификатора используются N объектов, а классифицируются объекты из истинных распределений. Эту процедуру называют U-методом. U-метод также даёт смещённую оценку вероятности ошибки е0. Это смещение таково, что его математическое ожидание является верхней границей вероятности ошибки. Объекты из истинного распределения могут быть заменены объектами, которые не были использованы для синтеза классификатора и независимы от объектов, по которым классификатор был синтезирован. Когда число классифицируемых объектов увеличивается, их распределение стремится к истинному распределению.
Для реализации U-метода имеется много возможностей. Рассмотрим две типовые процедуры.
1. Метод разбиения выборки. Вначале имеющиеся объекты разбивают на две группы и используют одну из них для синтеза классификатора, а другую - для проверки его качества. Основной вопрос, характерный для этого метода, заключается в том, как разделить объекты.
2. Метод скользящего распознавания. Во втором методе попытаемся использовать имеющиеся объекты более эффективно, чем в методе разбиения выборки. Для оценки необходимо, вообще говоря, извлечь много выборок объектов и синтезировать большое количество классификаторов, проверить качество каждого классификатора с помощью неиспользованных объектов и определить среднее значение показателя качества. Подобная процедура может быть выполнена путём использования только имеющихся N объектов следующим образом. Исключая один объект, синтезируется классификатор по имеющимся N-1 объектам, и классифицируется неиспользованный объект. Затем эту процедуру повторяют N раз и подсчитывают число неправильно классифицированных объектов. Этот метод позволяет более эффективно использовать имеющиеся объекты и оценивать . Один из недостатков этого метода заключается в том, что приходится синтезировать N классификаторов.
Метод разбиения выборки.
Для того, чтобы разбить имеющиеся объекты на обучающую и экзаменационную выборки, изучим, как это разбиение влияет на дисперсию оценки вероятности ошибки.
Вначале предположим, что имеется бесконечное число объектов для синтеза классификатора и N объектов для проверки его качества. При бесконечном числе объектов синтезируемый классификатор является классификатором для истинных распределений, и его вклад в дисперсию равен нулю. Для фиксированного классификатора организуем селективную выборку. В этом случае распределение оценки подчиняется биномиальному закону с дисперсией
, (1.80)
где еi - истинная вероятность ошибки для i-го класса.
С другой стороны, если имеется N объектов для синтеза классификатора и бесконечное число экзаменационных объектов, то оценка вероятности ошибки выражается следующим образом:
, (1.81)
где Гi - область пространства признаков, соответствующая i-му классу. В этом случае подынтегральные выражения постоянны, но граница этих областей изменяется в зависимости от выборки из N объектов.
Дисперсию оценки вычислить сложно. Однако в случае нормальных распределений с равными корреляционными матрицами интегралы в (1.81) можно привести к одномерным интегралам
,(1.81)
где зi и у2i определяются условными математическими ожиданиями:
,(1.82)
,(1.83)
. (1.84)
Это преобразование основано на том, что для нормальных распределений с равными корреляционными матрицами байесовский классификатор - линейный, а распределение отношения правдоподобия также является нормальным распределением.
Следует заметить, что даже если две истинные корреляционные матрицы равны, то оценки их различны. Однако для простоты предположим, что обе эти оценки равны и имеют вид
, (1.85)
где Ni - число объектов x(i)j класса i, используемых для синтеза классификатора.
Выражение для математического ожидания оценки достаточно громоздкое, здесь приводится простейший случай, когда P(C1)=P(C2) и N1=N2:
, (1.86)
, (1.87)
где d - расстояние между двумя векторами математических ожиданий, определяемое по формуле
. (1.88)
Величина е0 является минимальной вероятностью ошибки байесовского классификатора. Так как е0 - минимальное значение оценки , то распределение для является причинным Причинным распределением называется распределение p(x)=д(x-о), где д(x-о) - дельта-функция.. Поэтому можно определить оценку дисперсии величины, основанную на её математическом ожидании. Предположим, что плотность вероятности является плотностью вероятности гамма-распределения, которое включает в себя широкий класс причинных распределений. Тогда
(1.89)
при Де>0 (b?0 и c>0).
Математическое ожидание и дисперсия плотности вероятности (1.89) соответственно равны
, (1.90)
. (1.91)
Исключив c, получим верхнюю границу дисперсии , т.е.
(1.91)
при b ? 0.
Таким образом, степень влияния числа обучающих объектов на оценку вероятности ошибки е0 в случае нормальных распределений с равными корреляционными матрицами и равными априорными вероятностями равна
. (1.92)
Величину sэксп следует сравнивать с величиной sтеор, которая характеризует влияние числа объектов в экзаменационной выборке на оценку вероятности ошибки. Значение sтеор получается подстановкой в формулу (1.80) значений P(C1) = P(C2) =0.5 и е1 = е2 = е0:
. (1.93)
Исключение задания класса для объектов экзаменационной выборки.
Для того, чтобы оценить вероятность ошибки как при обучении, так и на экзамене, требуются выборки объектов, в которых известно, какой объект к какому конкретному классу принадлежит. Однако в некоторых случаях получение такой информации связано с большими затратами.
Рассмотрим метод оценки вероятности ошибки, не требующий информации о принадлежности объектов экзаменационной выборки к конкретному классу. Применение этого метода наиболее эффективно в случае, когда при оптимальном разбиении выборки на обучающую и экзаменационную число объектов в экзаменационной выборке больше, чем в обучающей.
Введём критическую область для задач классификации M классов:
,(1.94)
где P(x) - плотность вероятности смеси, t - критический уровень, 0 ? t ? 1. Условие (1.94) устанавливает, что если для данного объекта x значения P(C1)p(x/C1), вычисленные для каждого класса Mi, не превышают величины (1-t)p(x), то объект х не классифицируют вообще; в противном случае объект x классифицируют и относят его к i-му классу. Таким образом, вся область значений x делится на критическую область Гr(t) и допустимую область Гa(t), причём размеры обеих областей являются функциями критического уровня t.
При таком решающем правиле вероятность ошибки е(t), коэффициент отклонения r(t) и коэффициент правильного распознавания c(t) будут равны
, (1.95)
, (1.96)
е(t) = 1 - c(t) - r(t). (1.97)
Предположим, что область отклонения увеличивается на Гr(t) за счёт замены значения t на t-Дt. Тогда те x, которые раньше классифицировались правильно, теперь отклоняются:
(1.98)
при xДГr(t). Интегрируя (1.98) в пределах области ДГr(t), получим
(1 - t)Дr(t) ? -Дc(t) < (1 - t+Дt)Дr(t), (1.99)
где Дr(t) и Дc(t) - приращения r(t) и c(t), вызванные изменениями t. Из формулы (1.97) следует, что неравенство (1.99) можно переписать следующим образом:
- tДr(t) ? Де(t) < -У(t - Дt)Дr(t). (1.100)
Полагая Дt>0, получаем интеграл Стилтьеса
. (1.101)
Уравнение (1.101) показывает, что вероятность ошибки е(t) может быть вычислена после того, как установлена зависимость между значениями t и r(t). Из решающего правила (1.94) следует, что при t = 1-1/M область отклонения отсутствует, так что байесовская ошибка е0= е(1-1/M). Кроме того, из формулы (1.101) можно установить взаимосвязь между вероятностью ошибки и коэффициентом отклонения, так как изменение вероятности ошибки можно вычислить как функцию от изменения коэффициента отклонения.
Воспользуемся выражением (1.94) для исключения задания класса объектов экзаменационной выборки. Для этого поступим следующим образом.
1. Для определения ДГr(kt0) при t = kt0, k = 0, 1, …, m = (1-1/M)t0, где t0 - дискретный шаг переменной t, будем использовать относительно дорогостоящие классифицируемые объекты.
2. Подсчитаем число неклассифицированных объектов экзаменационной выборки, которые попали в область ДГr(kt0), разделим это число на общее число объектов и обозначим полученное соотношение через Дr(kt0).
3. Тогда из выражения (1.94) следует, что оценка вероятности ошибки
. (1.102)
В описанной процедуре использовалось то, что коэффициент отклонения является функцией от плотности вероятности смеси, а не от плотностей вероятности отдельных классов. Поэтому после того, как по классифицированным объектам найдены расширенные области отклонения, в дальнейшем для оценивания Дr(t) и вероятности ошибки е(t) нет необходимости использовать классифицированные объекты.
1.5. Структурные методы в распознавании образов
1.5.1 Введение
Структурный (синтаксический) подход был предложен для того, чтобы представлять иерархическую информацию, содержащуюся в каждом образе, т.е. описывать образ при помощи более простых подобразов, а каждый подобраз снова описывать ещё более простыми подобразами и т.д. [4]. Разумеется, применение этого подхода оправдано только в том случае, когда распознавать выбранные простейшие подобразы, называемые непроизводными элементами, легче, чем сами образы. Язык, обеспечивающий структурное описание образов в терминах непроизводных элементов, иногда называют языком описания образов. Правила композиции непроизводных элементов обычно задают при помощи так называемой грамматики языка описания образов. Процесс распознавания осуществляется после идентификации непроизводных элементов и составления описания объекта и состоит в грамматическом разборе (синтаксическом анализе) предложения, описывающего объект.
Структурный подход к распознаванию образов даёт возможность описывать большое число сложных объектов путём использования небольшого множества непроизводных элементов и грамматических правил (правил подстановки). Грамматическое правило может быть применено любое число раз, так что оказывается возможным очень компактно выразить основные структурные характеристики бесконечного множества предложений. Различные отношения, определённые между подобразами, обычно могут быть выражены логическими и (или) математическими операциями [4].
Система синтаксического распознавания образов.
Систему синтаксического распознавания образов можно считать состоящей из трёх основных частей: блока предварительной обработки, блока описания (представления) объекта и блока синтаксического анализа. Обычно предполагается, что объекты на выходе блока предобработки представлены в “достаточно хорошем” качестве. Затем каждый подвергнутый предобработке объект представляют в виде структуры языкового типа. Этот процесс представления объекта состоит, во-первых, из сегментации, и, во-вторых, из выделения непроизводных элементов (признаков). Иными словами, каждый объект после предобработки делится на части и непроизводные элементы на основе заранее заданных синтаксических операций (или операций композиции) и получает своё представление через множество непроизводных элементов и определённые синтаксические операции. Решение о том, является ли представление объекта синтаксически правильным (т.е. принадлежит ли он к классу объектов, описываемых данным синтаксисом или данной грамматикой), принимается блоком синтаксического анализа. По ходу синтаксического анализа этот блок может давать полное синтаксическое описание объекта в терминах грамматических единиц или дерева синтаксического анализа (если представление объекта синтаксически правильное). В противном случае объект либо исключают из рассмотрения, либо анализируют на основе других заданных грамматик, которые, может быть, описывают другие возможные классы рассматриваемых образов [4].
Для того, чтобы получить грамматику, описывающую структурную информацию класса образов, необходимо устройство вывода грамматики, позволяющее восстановить её по заданному множеству объектов в виде, подобном языковому. Функции этого устройства аналогичны процессу обучения в дискриминационных системах распознавания образов. В результате обучения на рассматриваемых объектах формируется структурное описание этого класса. Затем полученное в виде грамматики описание используется для описания образов и синтаксического анализа.
Блок-схема системы синтаксического распознавания образов изображена на рис.8.
- 4 -
Размещено на http://www.allbest.ru/
Размещено на http://www.allbest.ru/
1.5.2 Введение в формальные языки
Языки и порождающие грамматики.
Порождающая грамматика есть четвёрка G=(VN, VT, P, S), где VN и VT - основной и вспомогательный словари (или множества переменных) соответственно, P - конечное множество правил вывода или правил подстановки, символ - начальный символ. Объединение VT и VN составляет полный словарь V грамматики G, VT?VN=O. Правила подстановки из P обозначаются как б>в, где б и в - цепочки символов из V,причём б содержит хотя бы один символ из VN.
Часто используются следующие обозначения [4]:
1. У* - множество всех конечных цепочек символов из конечного множества У, включая л - цепочку нулевой длины, У+= У*-л.
2. xn - цепочка, состоящая из n раз написанной цепочки x.
3. |x| - длина цепочки, т.е. число символов в цепочке.
4. - цепочка з непосредственно порождает цепочку г, если з=щ1бщ2, г=щ1вщ2 и б>в - элемент P.
5. - цепочка з порождает цепочку г, если существует такая последовательность цепочек ж1, ж2, …, жN, что з= ж1, г= жN и жi жi+1.
Язык, порождаемый грамматикой G, есть
L(G) = {x / xV*T, x - такая цепочка, что }. (2.1)
Если G - порождающая грамматика, то L(G) называется формальным языком.
Типы порождающих грамматик (по Хомскому).
1) Грамматики типа 1 (грамматики непосредственно составляющих).
Правила подстановки грамматик типа 1 имеют следующий вид:
ж1Aж2>ж1вж2, (2.2)
где AVN, ж1, ж2, вV* и в?л.
Это означает, что цепочку A можно заменить на в в контексте ж1, ж2.
Языки, порождаемые грамматиками типа 1, называются языками типа 1 или языками непосредственно составляющих.
2) Грамматики типа 2(бесконтекстные грамматики).
Правила подстановки таких грамматик имеют вид:
A>в, (2.3)
где AVN и вV+. Следует заметить, что такие правила подстановки позволяют заменять вспомогательный символ A на цепочку в независимо от контекста, в котором встречается A.
Языки, порождаемые грамматиками типа 2, называются языками типа 2 или бесконтекстными языками.
3) Грамматики типа 3 (автоматные или регулярные).
Правила подстановки грамматик типа 3 имеют вид
A>aB или A>b, (2.4)
где A, BVN и a, bVT. Заметим, что A, B, a, b - одиночные символы V.
Языки, порождаемые грамматиками типа 3, называются языками типа 3 или автоматными (регулярными).
Кроме этих трёх типов грамматик, существует ещё один тип грамматик - грамматики типа 0 (неограниченные). Этот тип характеризуется отсутствием каких-либо ограничений на вид правил подстановки: любые цепочки могут стоять как слева, так и справа от стрелки. Однако для использования этот класс слишком широк, так как даже вопрос о том, порождается ли некоторая цепочка данной грамматикой типа 0, вообще говоря, неразрешим.
1.5.3 Типы распознающих устройств в системах синтаксического распознавания образов
Автоматные языки и конечные автоматы.
Конечный (детерминированный) автомат - пятёрка A=(У, Q, д, q0, F), где У - конечное множество входных символов (алфавит), Q - конечное множество состояний, д - функция, определяющая следующее состояние, т.е. отображение Q?У в Q, q0Q - начальное состояние и FQ - множество заключительных состояний. Функция д(q, a) интерпретируется следующим образом: автомат A в состоянии q читает входной символ a, переходит в состояние q' и сдвигает устройство считывания на один символ вперёд. Отображение д можно распространить с одного входного символа на цепочку, если определить
д (q, л) = q, д (q, xa) = д (д (q, x),a), xУ*,aУ. (2.5)
Таким образом, д (q, л) = q' понимается так: находясь в состоянии q, автомат A просматривает цепочку x на входной ленте и переходит в состояние q', а считывающее устройство смещается вперёд с той части входного потока, которая содержит x. Говорят, что цепочка, или предложение x, допускается автоматом A, если
д (q, л) = p для некоторого pF. (2.6)
Множество цепочек, допускаемых A, определяется как
T (A) = {x| д (q0, x) F}. (2.7)
Недетерминированный конечный автомат есть пятёрка A = (У, Q, д, q0, F), где У - конечное множество входных символов (алфавит), Q - конечное множество состояний, д - отображение Q?У во множество подмножеств множества Q, q0 - начальное состояние и F - множество заключительных состояний.
Подобные документы
Основные понятия теории распознавания образов и ее значение. Сущность математической теории распознавания образов. Основные задачи, возникающие при разработке систем распознавания образов. Классификация систем распознавания образов реального времени.
курсовая работа [462,2 K], добавлен 15.01.2014Оптико-электронная система идентификации объектов подвижного состава железнодорожного транспорта. Автоматический комплекс распознавания автомобильных номеров. Принципы и этапы работы систем оптического распознавания. Особенности реализации алгоритмов.
дипломная работа [887,3 K], добавлен 26.11.2013Распознавание образов - задача идентификации объекта или определения его свойств по его изображению или аудиозаписи. История теоретических и технических изменений в данной области. Методы и принципы, применяемые в вычислительной технике для распознавания.
реферат [413,6 K], добавлен 10.04.2010Появление технических систем автоматического распознавания. Человек как элемент или звено сложных автоматических систем. Возможности автоматических распознающих устройств. Этапы создания системы распознавания образов. Процессы измерения и кодирования.
презентация [523,7 K], добавлен 14.08.2013Понятие системы распознавания образов. Классификация систем распознавания. Разработка системы распознавания формы микрообъектов. Алгоритм для создания системы распознавания микрообъектов на кристаллограмме, особенности его реализации в программной среде.
курсовая работа [16,2 M], добавлен 21.06.2014Теоретические основы распознавания образов. Функциональная схема системы распознавания. Применение байесовских методов при решении задачи распознавания образов. Байесовская сегментация изображений. Модель TAN при решении задачи классификации образов.
дипломная работа [1019,9 K], добавлен 13.10.2017Обзор задач, возникающих при разработке систем распознавания образов. Обучаемые классификаторы образов. Алгоритм персептрона и его модификации. Создание программы, предназначенной для классификации образов методом наименьшей среднеквадратической ошибки.
курсовая работа [645,2 K], добавлен 05.04.2015Методы распознавания образов (классификаторы): байесовский, линейный, метод потенциальных функций. Разработка программы распознавания человека по его фотографиям. Примеры работы классификаторов, экспериментальные результаты о точности работы методов.
курсовая работа [2,7 M], добавлен 15.08.2011Выбор типа и структуры нейронной сети. Подбор метода распознавания, структурная схема сети Хопфилда. Обучение системы распознавания образов. Особенности работы с программой, ее достоинства и недостатки. Описание интерфейса пользователя и экранных форм.
курсовая работа [3,0 M], добавлен 14.11.2013Описание структурной схемы искусственного нейрона. Характеристика искусственной нейронной сети как математической модели и устройств параллельных вычислений на основе микропроцессоров. Применение нейронной сети для распознавания образов и сжатия данных.
презентация [387,5 K], добавлен 11.12.2015
