Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 8)

Здесь умножение, как вы знаете, соответствует логическому “И”, а сложение - “ИЛИ”.

Точно также для второго класса заболеваний получим следующее описание

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

Если распределение объектов распознавания, представляемых числовыми значениями их признаков по областям соответствующего пространства вероятностное, то для описания классов необходимо определить характеристики этих распределений. А из теории вероятности известно, что это

-функции ПРВ f_i (x₁,x₂,....,x_n), где x₁.....x_n - вероятностные признаки, I - номер класса;

-P(W_i) - априорная вероятность того, что объект, случайно выбранный из общей совокупности, окажется принадлежащим к классу W_i.

Как получить ПРВ классов системы распознавания? В распоряжении разработчика СР - три способа:

-экспериментальное определение по статистическим данным;

-теоретический вывод;

-моделирование.

То же касается априорной вероятности класса P(W_i).

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

ЗАДАЧА № 5

Выбор алгоритма классификации, обеспечивающего отнесение распознаваемого объекта или явления к соответствующему классу.

Непосредственное решение задачи распознавания на основе использования словаря признаков и алфавита классов объектов или явлений фактически заключается в разбиении пространства значений признаков распознавания на области D₁,D₂,...,D_n, соответствующие классам W₁,W₂,...,W_n (вспоминаем определение “образа”).

Указанное разбиение должно быть выполнено таким образом, чтобы обеспечивались минимальные значения ошибок отнесения классифицируемых объектов или явлений к “чужим” классам.

Результатом такой операции является отнесение объекта, имеющего набор признаков X₁,X₂,....,X_n (точка в n-мерном пространстве), к классу W_i, если указанная точка лежит в соответствующей классу области признаков - D_i.

Разбиение пространства признаков можно представлять как построение разделяющих функций f_i(x₁,x₂,....,x_n) между множествами (областями) признаков Di, принадлежащим разным классам.

Упомянутые функции должны обладать следующим свойством:

-если объект, имеющий вектор признаков фактически относится к классу , то значение разделяющей функции

должно быть большим, чем значение ее для класса - (здесь индекс q - означает номер класса, к которому принадлежит вектор признаков).

Отсюда легко определить выражение решающей границы между областями D_i, соответствующим классам W_i:

Для двух распознаваемых классов разбиение двумерного пространства выглядит так (рис 2.2). Физически распознавание основывается на сравнении значений той или иной меры близости распознаваемого объекта с каждым классом. При этом если значение выбранной меры близости (сходства) L данного объекта w с каким-либо классом W_g достигает экстремума относительно значений ее по другим классам, то есть

то принимается решение о принадлежности этого объекта классу W_g, то есть w W_g.

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

X₁ o o o o

xx x o o o

x o o F₂(X₁,X₂) > F₁(X₁,X₂)

x x x o o o o

x o o o o o

x x x x x o o o o o

F₁(X₁,X₂)>F₂(X₁,X₂) x o

x x x x x x x o o

x x x x x x

x x x x x

X₂

Рис.2.2

В алгоритмах распознавания, использующих детерминированные признаки в качестве меры близости, используется среднеквадратическое расстояние между данным объектом w и совокупностью объектов (w₁,w₂,....,w_n), представляющих (описывающих) каждый класс. Так для сравнения с классом W_g это выглядит так

где k_g - количество объектов, представляющих W_g-й класс.

При этом в качестве методов измерений расстояния между объектами d(w,w_g) могут использоваться любые методы (творческий процесс здесь не ограничивается).

Так, если сравнивать непосредственно координаты (признаки), то

где N - размерность признакового пространства.

Если сравнивать угловые отклонения, то рассматривая вектора, составляющими которых являются признаки распознаваемого объекта w и класса w_g, будем иметь:

где ||X_w|| и ||X_wg|| - нормы соответствующих векторов.

В алгоритме распознавания, использующем детерминированные признаки можно учитывать и их веса V_j (устанавливать степень доверия или важности). Тогда рассмотренное среднеквадратическое расстояние принимает следующий вид:

В алгоритмах распознавания, использующих вероятностные признаки, в качестве меры близости используется риск, связанный с решением о принадлежности объекта к классу W_i, где i - номер класса. (i=1,2,..,m.).

Описания классов, как мы недавно рассмотрели

В рассматриваемом случае к исходным данным для расчета меры близости относится платежная матрица вида:

Здесь на главной диагонали - потери при правильных решениях. Обычно принимают С_ii=0 или C_ii<0.

По обеим сторонам от главной диагонали - потери при ошибочных решениях. В каждой системе эти потери свои, свойственные только ей. Однако назначение их - творчество разработчика системы распознавания.

Если вектор признаков распознаваемого объекта w - , то риск, связанный с принятием решения о принадлежности этого объекта к классу W_g, когда на самом деле он может принадлежать классам W₁,W₂,...,W_m, наиболее целесообразно определять как среднее значение потерь

С_1g, C_2g,...,C_mg ,

то есть, потерь, стоящих в g-ом столбце платежной матрицы.

Тогда этот средний риск можно записать как определение МОЖ

Здесь P(W_i/X_w) - апостериорная вероятность того, что w W_i.

Для исходных данных, а именно описаний классов эта вероятность легко может быть определена в соответствии с теоремой гипотез или по формуле Байеса

Вероятности и плотности, входящие в формулу - ни что иное как характеристики описания классов в вероятностной системе.

Для алгоритмов, основанных на логических признаках, понятие “мера близости” не имеет смысла. Вспомним упрощенный пример, рассмотренный нами для логических признаков заболеваний (простой простуды и ангины).

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

Действительно, пусть признаки приняли следующие значения:

-Ïîâûøåííàÿ òåìïåðàòóðà: A=1

-Насморк: B=0

-Нарывы в горле: C=1

Тогда подстановка их в булевы соотношения даст следующий результат:

То есть, истинным является второе соотношение, соответствующее распознаванию ангины как диагностируемого класса из двух заболеваний.

Для алгоритмов, основанных на структурных (лингвистических) признаках, понятие “меры близости” более специфично.

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

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

Рассмотрев задачу №5 , мы фактически завершили рассмотрение круга задач создания СР. В то же время уже отмечалось, что создание СР осуществляется последовательными приближениями по мере получения дополнительной информации. В этом ряду последовательных приближений главную роль играют признаки распознавания. От эффективности их набора зависит, эффективность системы в целом. В процессе совершенствования системы указанный набор пополняется, неэффективные признаки исключаются. Поэтому одной из задач создания СР должна быть и задача перехода от априорного словаря признаков к рабочему. То же касается и априорного алфавита классов.

ЗАДАЧА № 6

Определение рабочего алфавита классов и рабочего словаря признаков системы распознавания.

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

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

Указанное существо задачи заставляет снова обратить внимание на возможность получения оценки эффективности системы распознавания путем ее моделирования. Об этом мы говорили при создании априорного словаря признаков. К этому мы вернемся при специальном рассмотрении вопросов моделирования систем распознавания.

Что же касается приемов, обеспечивающих отбор в процессе оптимизации систем распознавания, то они являются также предметом отдельного рассмотрения.

Ò å ì à 3

Êëàññèôèêàöèÿ ñèñòåì ðàñïîçíàâàíèÿ

Л Е К Ц И Я 3.1

Принципы классификации и типы систем распознавания

Ïðè ðàññìîòðåíèè çàäà÷, ðåøàåìûõ â ïðîöåññå ñîçäàíèÿ ñèñòåì ðàñïîçíàâàíèÿ (òåìà 2) , ìû ãîâîðèëè î ïðèçíàêàõ îáúåêòîâ (ÿâëåíèé), î ñïîñîáàõ èõ ïîëó÷åíèÿ â ïðîöåññå ðàáîòû ÑÐ, îá èñïîëüçîâàíèè àïðèîðíîé èíôîðìàöèè, íå çàòðàãèâàÿ âîïðîñîâ âçàèìîñâÿçåé â ñèñòåìå. Èíîãäà òîëüêî óïîìèíàëè îá ýòîì .

 òî æå âðåìÿ, ÷òîáû ëåã÷å, ñîçíàòåëüíåå ðåøàòü çàäà÷ó âûáîðà ïðèçíàêîâ (à ýòî, êàê ìû ïîìíèì, - ïðîöåññ ýâðèñòè÷åñêèé), à òàêæå äëÿ ïëàíèðîâàíèÿ èñïîëüçîâàíèÿ êàê àïðèîðíîé èíôîðìàöèè (îïèñàíèå êëàññîâ), òàê è àïîñòåðèîðíûõ äàííûõ (èçìåðåíèÿ ïî äàííîìó íåèçâåñòíîìó ïîäëåæàùåìó êëàññèôèêàöèè îáúåêòó) ýòè âçàèìîñâÿçè íåîáõîäèìî õîðîøî ïðåäñòàâëÿòü.

Однако, как оказывается, упоминаемые взаимосвязи могут принимать различные формы, иметь свои особенности. Простое перечисление здесь не подходит. Поэтому представляется необходимым классифицировать сначала сами системы распознавания. Это позволит понять взаимосвязи в них и решать те задачи, о которых мы сейчас говорили.

Начнем с уточнения того, что такое классификация. Классификация - это распределение предметов, явлений по классам, отделам, разрядам в зависимости от их общих свойств.

В основе классификации лежат определенные принципы.

Для классификации СР будем использовать следующие принципы:

1.Однородность информации для описания распознаваемых объектов или явлений.

2.Способ получения апостериорной информации.

3.Количество первоначальной априорной информации.

4.Характер информации о признаках распознавания.

А. Рассмотрим 1-й принцип.

(Однородность информации)

Здесь под однородностью следует понимать - различную или единую физическую природу информации (признаков).

По этому принципу СР делятся на:

-простые;

-сложные.

Простые СР характеризуются единой физической природой признаков. Например:

1) только масса - для систем распознавания жетонов, монет в автоматах таких, как междугородный телефон, турникет метро;

2) геометрические размеры - для таких СР, как всякого рода замки.

Ясно, что для простых систем распознавания не обязательно иметь компьютер. Достаточно их реализовать в виде механических или электромеханических устройств. Хотя компьютерные реализации в принципе не противопоказаны, если наряду с этой в системе решаются и другие более достойные задачи.

Сложные СР характеризуются физической неоднородностью признаков.

В рассмотренном нами в теме № 2 перечне признаков самолетов такая неоднородность просматривается невооруженным глазом. Там имели:

-и численность экипажей;

-и высоты полета;

-и взлетный вес;

-и геометрические размеры и т.д.

Точно также в медицинской практике для диагностики может оказаться необходимым привлекать:

-и температуру;

-и данные анализа крови;

-и данные кровяного давления;

-и кардиограммы и т.п.

Конечно, простота всегда предпочтительнее. Хорошо иметь всего 1 - 2 признака и при этом желательно однородных, чтобы решать задачу компьютерного распознавания, например, заболеваний печени. Но не всегда, как и в этом случае, так получается. Сравните распознавания ключа замком и распознавание преступника по словесному портрету (набору признаков).

Б. Второй принцип классификации СР.

(Способ получения апостериорной информации).

По этому принципу сложные системы ( а мы уже знаем, что они собой представляют) распознавания делятся на:

-одноуровневые;

-многоуровневые.

На рис. 1 изображена одноуровневая система распознавания.

Здесь:

И₁, И₂,.....,И_n - разнородные по физической природе измерители.

АО - априорное описание классов распознаваемых объектов;

АК - алгоритм классификации;

САУ- система автоматического управления (алгоритм) распознаванием.

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

Здесь на основе объединения признаков нескольких измерителей и соответствующей обработки могут быть получены вторичные признаки, которые могут как использоваться в АК, так и сами в свою очередь служить основой для объединения. То есть, получаем 2-й, 3-й и др. уровни признаков, определяющие многоуровневость СР. Причем подсистемы, которые осуществляют объединение признаков, в свою очередь могут представлять собой также устройства распознавания (локальные СР).

Схема здесь в целом подобна предыдущей (для одноуровневой системы), а отличается лишь усложнением связей от признаков к АК.(Рис.2)

W

È 1 È 2 ............................. È n

X11 X12 .... X1k X21 X22 .... X2p Xn1 Xn2 .... Xnr

A K

Ñ À Ó

Ðåøåíèå î ïðèíàäëåæíîñòè

A O

Ðèñ. 1

W

È 1 È 2 ......................... È n

X11 X12 .... X1k X21 X22 ....X2p Xn1 Xn2 . Xnr

A B C

D

À Ê

Ñ À Ó

À Î Ðåøåíèå î ïðèíàäëåæíîñòè

Ðèñ. 2

Таким образом:

в одноуровневых СР информация о признаках распознаваемого объекта (апостериорная информация) формируется непосредственно на основе обработки прямых измерений;

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

В. Третий принцип классификации.

(Количество первоначальной априорной информации).

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

Соответственно этому СР делятся на:

-системы без обучения;

-обучающиеся (ОСР) и самообучающиеся системы (ССР).

Сразу заметим, что многоуровневые сложные СР однозначно нельзя разделить на указанные классы, так как каждая из локальных СР, входящих в их состав, сама может представлять как систему без обучения, так и систему обучающуюся или самообучающуюся.

Системы без обучения.

Для построения таких систем необходимо располагать полной первоначальной априорной информацией. Предыдущие, рассмотренные нами схемы СР фактически изображали такие системы.

Обучающиеся системы.

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

Исходная информация для обучающихся СР (ОСР) представляется в виде набора объектов w₁, w₂,....,w_l ,распределенных по m классам:

(w₁ ,w₂ ,...,w_r ) W₁

(w _r+1 ,w _r+2 ,...,w_q ) W₂

..................

(w_g+1 ,w_g+2 ,...,w_l ) W_m

Цель обучения и ее достижение заключаются для ОСР в определении разделяющих функций

F_i(X₁ ,X₂ ,.....,X_n),

где i = 1,2,....,m (номер класса).

Определение этой функции осуществляется путем многократного предъявления системе указанных объектов (из набора w₁,w₂,....,w_l ) с указанием, какому классу они принадлежат.

То есть, на стадии формирования ОСР работают с “учителем”, осуществляющим указание о принадлежности предъявленного для обучения объекта. И прежде, чем система будет применяться, должен пройти этап обучения.

О разделяющих функциях мы уже вели речь, когда рассматривали задачи построения систем распознавания. Теперь мы вернулись к этому понятию, определив СР, в которых указанные функции применяются.

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

Теперь же мы уже в состоянии изобразить ОСР (Рис. 3).

Y - учитель;

ОО - обучающие объекты;

АРФ - алгоритм построения разделяющих функций;

ТС - под общим названием “Технические средства”

объединены измерители признаков распознавания;

АО - априорное описание классов распознаваемых об’ектов;

АК - алгоритм классификации;

САУ - система автоматического управления (алгоритм) распознавания;

w - неизвестные, распознаваемые объекты.

Ïóíêòèðíûå ëèíèè íà ðèñóíêå ñîîòâåòñòâóþò âçàèìîñâÿçÿì â ïðîöåññå îáó÷åíèÿ.

W

Ò Ñ ÎÁÎ Ó

À Ð Ô

À Î

Ñ À Ó

À Ê

Ðåøåíèå î ïðèíàäëåæíîñòè

Ðèñ. 3

Л Е К Ц И Я 3.2

Принципы классификации и типы систем распознавания

(Продолжение)

Самообучающиеся системы.

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

Для ССР также, как для ОСР существует период обучения, характерно наличие периода самообучения, когда ей предъявляются объекты обучающей последовательности. Только при этом не указывается принадлежность их к каким-либо классам.

Соответствующая функциональная схема ССР приведена на рис.4.

Здесь дополнительно к обозначениям рис.2,3 имеем:

ОС - объекты самообучения;

ПК - правила классификации;

АФК - алгоритм формирования классов.

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

В другой широко применяемой терминологии ССР - это система автоматического кластерного анализа или таксономии (taxis - порядок, nomos - закон).

Завершая рассмотрение классификации СР по количеству первоначальной априорной информации, заметим, что СР, в которых недостаточно информации для назначения словаря признаков, не существует. Без этого не создается никакая система.

W

Ò Ñ ÎÁÑ

À Ô Ê Ï Ê

À Î

Ñ À Ó

À Ê

Ðåøåíèå î ïðèíàäëÅÆíÎñòè

Ðèñ. 4

Г. Четвертый принцип классификации.

(Характер информации о признаках распознавания).

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

-детерминированные;

-вероятностные;

-логические;

-структурные (лингвистические);

-комбинированные.

Подытоживая пройденное, отметим характерные особенности этих систем, а именно: метод решения задачи распознавания и метод априорного описания классов.

Детерминированные системы.

а) Метод решения задачи распознавания: использование геометрических мер близости;

б) Метод априорного описания классов: координаты векторов-эталонов по каждому из классов или координаты всех объектов, принадлежащих классам (наборы эталонов по каждому классу).

Вероятностные системы.

а) Метод решения задачи распознавания: вероятностный, основанный на вероятностной мере близости (средний риск);

б) Метод априорного описания классов: вероятностные зависимости между признаками и классами.

Логические системы.

а) Метод решения задачи распознавания: логический, основанный на дискретном анализе и исчислении высказываний;

б) Метод априорного описания классов: логические связи, выражаемые через систему булевых уравнений, где признаки - переменные, классы - неизвестные величины.

Структурные (лингвистические) системы.

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

б) Метод априорного описания классов: подмножества предложений, описывающих объекты каждого класса.

Комбинированные системы.

а) Метод решения задачи распознавания: специальные методы вычисления оценок;

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

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

В целом рассмотренная классификация СР может быть представлена следующей схемой (рис.5)

После проведенной классификации возвратимся для дополнительного рассмотрения функциональных схем СР. И обратим внимание именно на термин "достаточное" или "недостаточное" количество информации. С этой меркой мы походили к разделению СР на два большие класса: СР без обучения, обучающиеся и самообучающиеся СР. То есть, для СР без обучения имели дело с полной информацией, а для ОСР - с неполной (нет описания классов на языке признаков), а для ССР - еще с большей неполнотой (отсутствует даже алфавит классов).

Однако заметим, что само понятие “неполнота информации” - качественное, относительное. Для СР без обучения при прочих равных условиях этой информации просто больше. Это означает, что результативность СР при имеющемся объеме априорной информации значительно выше, чем имеем в той ситуации, которая требует создания ОСР. О результативности СР, для которой невозможно априорно назначит алфавит классов говорить вообще нельзя. Что же касается примененного здесь выражения "результативность значительно выше", то из последующего изучения курса будет понятно, что этому казалось бы опять-таки качественному утверждению соответствуют вполне конкретные количественные показатели.

Ñ Ð

Ïðîñòûå Ñëîæíûå

Áåç îáó÷åíèÿ Ñ îáó÷åíèåì Ñ ñàìîîáó÷åíèåì

Äåòåðìèíè

ðîâàííûå Âåðîÿòíîñòíûå Ëîãè÷åñêèå Ñòðóêòóðíûå

Êîìáèíèðîâàííûå

Ðèñ. 5

Таким образом, отсюда следует, что информацией никогда пренебрегать не стоит. Поэтому при построении как ОСР, ССР и просто СР необходимо всегда использовать принцип обратной связи для расширения объема информации. То есть, результаты решения задачи распознавания неизвестных объектов после апостериорного подтверждения правильности их классификации необходимо использовать для уточнения описания классов в простых СР без обучения и для дополнительного обучения в ОСР и ССР.

Для решения таких задач приведенные схемы СР должны быть дополнены соответствующими функциональными связями дообучения.

* * *

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

Как вы уже знаете, эти системы основываются на методах искусственного интеллекта.

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

Указанные знания при этом могут быть как заслуживающими доверия и опробированными многочисленными независимыми применениями, так и сомнительными.

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

Изучение экспертных систем - это отдельный предмет с его методами и подходами.

Ò å ì à 4

Îïòèìèçàöèÿ ýâðèñòè÷åñêèõ âûáîðîâ ïðè ñîçäàíèè ñèñòåì ðàñïîçíàâàíèÿ îáðàçîâ

Л е к ц и я 4.1

Оптимизация алфавита классов и словаря признаков

4.1.1. Уточнение назначения и цели создания СР

Как нами уже установлено, процесс распознавания включает такую последовательность операций:

- прием на входе СР образа распознаваемого объекта;

-cопоставление апостериорной информации поступившего объекта с имеющимся в СР априорным описанием классов всех объектов, подлежащих распознаванию (объектов, на которые рассчитана система);

- принятие решения об отнесении объекта, образ которого был принят, к одному из классов.

Правило, согласно которому объекту, образ которого принят, ставится в соответствие наименование класса, называется решающим правилом.

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

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

1. Непосредственное предварительное определение при достаточном количестве априорной информации (СР без обучения).

2.Постепенное уточнение в ходе работы СР по назначению при наборе достаточного количества информации (обучающиеся СР).

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

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

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

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

При этом реализация решающего правила - это алгоритмическая задача, решение которой отодвигается на второй план сложностью и ценой задачи создания измерительных средств.

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

В результате представляется возможным сформулировать назначение любой СР.

Назначение СР - получение информации, необходимой для принятия решения о принадлежности неизвестных объектов (явлений) к тому или иному классу.

Такое определение наиболее плодотворно для сложных систем.

Оно заставляет сосредоточить усилия в создании СР на главном направлении.

(Примером главенства информации могут служить медицинские СР, геологические, метеорологические, криминалистические, системы контроля космического пространства страны).

Но и принятие решений о принадлежности - не самоцель. Поэтому второй момент, на который нам необходимо обратить внимание до перехода к теоретическим описаниям рассматриваемых в этой теме задач, - это необходимость понимания того, что любая СР является частью какой-либо системы управления ( автоматической или автоматизированной).

Отсюда легко формируется цель создания СР.

Цель создания СР - обеспечение высокой эффективности принимаемых решений в управлении.

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

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

Поэтому очень важно найти объективные методы оценки такого рода человеческой деятельности.

На это мы и направим последующий анализ.

1. Взаимосвязь размерности алфавита классов и эффективности СР

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

Оказывается, что отмеченные особенности и приведенные определения назначения и цели создания СР уже определяют взаимосвязи между классами и принимаемыми решениями.

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

Отсюда можно утверждать, что в управлении высокая эффективность решений достигается:

1)Увеличением числа классов в принятом алфавите, то есть, повышением степени детализации распознаваемых объектов (явлений) по назначению и характеру. При этом чем детальнее классификация, тем легче предпринять адекватное управление. ( Вполне понятно, что распознать просто отказ двигателя автомобиля менее привлекательно, чем указать на выход из строя клапана или масляного насоса).

2)Повышением точности определения признаков распознавания, а значит снижением возможности ошибочных решений, часто опасных для управления (снижение ошибок классификации).

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

В то же время увеличение числа классов в любой задаче, как можно понять только из соображений здравого смысла

( в дальнейшем мы это опишем более строго математически) не всегда просто, а иногда оказывается и невозможно.

Но существует одна ситуация, когда это увеличение всего на один класс бесспорно важно. Так для того, чтобы результаты распознавания были более приемлемы для последующего управления, приходится дополнительно к имеющимся m классам вводить (m+1)-ый, когда отказываются от распознавания, а значит и от управления. Отказ от управления лучше, чем управление при ошибочности распознанной ситуации (если это возможно по назначению системы).

Теперь постараемся понять имеющиеся связи, рассматривая отношения между числом классов и ошибками распознавания. Для удобства рассматриваем одномерный случай (вместо вектора признаков без ущерба для задачи, но для ясности физических представлений, имеем один признак.

Пусть заданы три класса объектов W₁, W₂, W₃

- распределениями вероятностей f(x/W₁), f(x/W₂ ), f(x/W₃ ), где x - вероятностный признак распознавания ;

- априорными вероятностями P(W₁), P(W₂), P(W₃);

- матрицей потерь при решениях

Теперь поймем, что если априорная вероятность отнесения объекта к i-му классу, в то время как он принадлежит к j-му классу (то есть, априорная вероятность ошибки) равна

P(Wi /Wj ),

то среднее значение платы за ошибочную классификацию всех m объектов в системе распознавания определяется как условное МОЖ потерь (зависимость от Wj

В целом средние потери классификации (то есть, потери по всем классам) определяются как среднее

Остается определить вероятность P(Wi /Wj ), так как априорное описание классов напрямую не дает ее значений.

Изобразим ситуацию классификации в рассматриваемом нами примере в виде функций ПРВ параметра распознавания для трех классов (Рис 4.1.1)

f (x/W_i)

f(x/W₁) f(x/W₂) f(x/W₃)

a b X

Рис. 4.1.1

Если теперь определить области возможного разброса параметра распознавания каждого класса как G_i ,то легко определить записанную нами вероятность ошибки так

Обозначим указанные области Gi на рисунке. Здесь эти области в силу одномерности случая должны представлять собой отрезки. Поэтому достаточно указать границы

а - граница между 1-ым и 2-ым классами;

b - граница между 2-ым и 3-им классами

Соответственно отрезки:

1-го класса ]- ¥ +a];

2-го класса ]+a +b];

3-го класса ]+b + ¥[ .

Теперь можно записать в соответствии с приведенной формулой условные риски ошибочных решений

Отсюда средний риск ошибочных решений в системе распознавания (то есть, риск ошибочной классификации всех классов):

Для простоты рассмотрения принимаем С_ii = 0, C_ij = C, P_i = P и, пользуясь рисунком, получим

Здесь обозначен средний риск индексом "1", так как теперь рассмотрим вторую ситуацию, для которой постараемся уменьшить число классов, объединяя первый и второй классы в один - четвертый.

Определим по правилам теории вероятностей ПРВ четвертого класса по ПРВ первого и второго классов

До этого мы упрощали представление вероятностей и плат за ошибки для трех классов. Добавим к этому и четвертый класс

C₄₄=0; C₁₄ =C₄₁ = C.

На рисунке ПРВ классов изобразим ПРВ четвертого класса (пунктир).

Теперь можно записать, как и в первом случае (три класса), условные риски ошибочных решений для оставшихся 3-го и 4-го классов

(Условные риски R₁ и R₂ здесь отсутствуют, так как произошло объединение 1-го и 2-го классов в 4-ый. Кроме того, матрица плат за ошибки с учетом четвертого класса приняла сначала следующий вид

а затем из нее за счет того же объединения исключили столбцы и строки, имевшие индексы "1" и "2". В результате получили:

Средний риск для случая двух оставшихся классов W₃ и W₄ обозначим индексом "2" и также, как для первого случая, после простых преобразований получим

.

Теперь, если подставим сюда вместо ПРВ f(x/W₄) его выражение, определенное уже нами, то получим

Наконец мы можем сравнить средний риск R₁ и R₂

__ __

R₁ > R₂

Вывод:

При заданном признаковом пространстве и прочих равных условиях уменьшение числа классов приводит к меньшению ошибок распознавания.

Следствие:

При увеличении числа классов для уменьшения среднего риска (через уменьшение вероятности ошибочных решений) необходимо включать в состав словаря признаков такие, которые имеют меньший разброс.

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

Л е к ц и я 4.2

Оптимизация алфавита классов и словаря признаков

(продолжение)

4.2.1. Взаимосвязь размерности вектора признаков и эффективности СР

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

Итак, докажем, что с увеличением числа признаков вероятность правильного распознавания неизвестных объектов также увеличивается.

Рассмотрим такое доказательство, допуская, что

- для каждого k-го признака распознавания существует некоторая вероятность такого события A_k, когда решение о принадлежности объектов к W_i классу принимается однозначно.

-признаки распознавания независимы между собой.

Независимость признаков означает и независимость событий A_k (событий принятия однозначных решений о принадлежности).

Обратимся к теории вероятностей. Вероятность наступления двух совместных или несовместных событий A₁ и A₂

P (A₁ + A₂ ) = P (A₁ ) + P (A₂ ) - P (A₁ A₂ )

Отсюда для трех событий получим

P (A₁ + A₂ + A₃ ) = P [A₁+ (A₂ + A₃ )] = P (A₁ ) + P (A₂ + A₃ ) - P [A₁ (A₂ + A₃ )] = P (A₁ ) + P (A₂ ) + P (A₃ ) - P (A₂A₃ ) - P (A₁A₂ + A₁A₃ ) =

=P (A₁ ) + P (A₂ ) + P (A₃ ) - P (A₂ A₃ ) -[ P(A₁A₂ ) + P (A₁A₃ ) - P (A₁A₂A₃ )]

или

Точно также для четырех событий

Теперь образуем разность между вероятностями суммы 4-х и 3-х событий, состоящих в рассматриваемом нами случае в принятии однозначного решения о принадлежности по 4-м и 3-м признакам распознавания соответственно:

=

(Наиболее просто эту разность получить, не доводя уменьшаемое до конечного вида

Теперь по индукции можно записать:

Из приведенного выражения следует, что если не достигнута предельная вероятность правильного распознавания, то есть:

то при любом n имеем

Это является доказательством возрастания вероятности при увеличении числа признаков.

Таким образом, последовательность

при является монотонно возрастающей, а значит и сходящейся, так как предел возрастания - “1”.

Для сходящейся последовательности

а значит

что и требовалось доказать.

Следствие:

Снижение эффективности распознавания за счет увеличения числа классов может быть скомпенсировано увеличением размерности вектора признаков.

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

4.2.2. Формализация задачи оптимального взаимосвязанного выбора алфавита классов и словаря признаков

Решая задачу повышения эффективности СР за счет увеличения размерности вектора признаков, мы не обращали внимания на то, что указанное увеличение - это часто возрастание числа технических средств измерений, каждое из которых обеспечивает определение одного или группы признаков. Значит при этом растут расходы на построение СР. А ресурсы часто ограничены.

Поэтому в условиях ограниченных ресурсов на создание СР только некоторый компромисс между размерами алфавита классов и объемом рабочего словаря признаков обеспечивает решение задачи оптимальным образом. Для обеспечения этого компромисса требуется предварительная формализация задачи. Начнем с общей формулировки задачи.

4.2.2.1. Формализация исходных данных

Пусть задано множество объектов или явлений

Характеристики

Список файлов реферата