Эффективность логических систем распознавания

 

При построении логических систем распознавания приходится сталкиваться с ситуацией, когда значения истинности элементов А₁..., А_n, выражающих признаки объектов, принадлежащих классам Ω_l, ..., Ω_m и связанных с элементами А₁ ..., А_n соотношениями Е(А₁ ..., А_n; Ω_l, ..., Ω_m) = l, устанавливаются в процессе эксперимента или по данным наблюдений не достоверно, а с известной неопределенностью. Это случается либо когда элементы A_{i ,} i=l, ..., n, обозначают высказывания «истинное значение x_i, параметра X_i лежит в пределах интервала (a_i, b_i)», причем результат измерения X_i есть случайная величина, либо когда определение признаков элементов А₁, ..., А_n производится в условиях естественных или искусственных помех, благодаря чему создаются предпосылки для ошибочных заключений.

К каждой проектируемой системе распознавания, как правило, предъявляются требования, касающиеся степени определенности ответов, выдаваемых системой в форме булевых функций j(Ω_l, ..., Ω_m), которые в общем случае удовлетворяют соотношению импликации где f(A₁ ..., А_n) — известная в результате эксперимента функция, А₁ ..., А_n и Ω_l, ..., Ω_m — элементы, связанные зависимостями вида E(A_i Ω_j)= 1.

Из множества допускаемых данной системой решений j(Ω_l, ..., Ω_m) практически полезными могут быть лишь некоторые. Вид решения j(Ω_l, ..., Ω_m) помимо априорных соотношений существенно зависит от полноты сведений об объекте, которые представляются функцией f(A₁, ..., А_n).

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

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

Пусть есть множество всех простых импликант функции j_i(Ω_l, ..., Ω_m), так что каждая функция f_i из множества {f_i} удовлетворяет соотношению Вследствие условия j_i × j_j=0 при i¹j функции f₁ ..., f_N должны удовлетворять соотношениям f_i×f_j®0 при i¹j или соотношениям f_i×f_j=0.

Если при всех i= 1, ..., N функции то, согласно сделанным предположениям, выбранный способ описания объектов позволяет различать между собой все N классов как с точки зрения их представления функциям так и с точки зрения их представления функциями f_i(A₁, ..., А_n), т. е. через наблюдаемые или оцениваемые в опыте признаки А₁ ..., А_n. При этих условиях ошибочные или неопределенные решения могут возникать только из-за того, что значения истинности элементов А₁ ..., А_n устанавливаются во время опыта с ошибками или же вообще не устанавливаются.

Обозначим ру вероятность получить решение j_i(Ω_l, ..., Ω_m), т. е. j(Ω_l, ..., Ω_m)® j_i(Ω_l, ..., Ω_m), i=1, ..., N, при условии, что распознаваемый объект является объектом j-го типа, т. е. функция f(A₁, ..., А_n) в соотношении f(A₁, ..., А_n)®j_i(Ω_l, ..., Ω_m) задается как f=f_j(A₁, ..., А_n)

Чтобы количественно описать процесс искажения информации об объектах во время опыта, введем в рассмотрение следующие величины:

— вероятность того, что в результате опыта будет установлено A_i=1, когда фактически A_i = 1;

— вероятность того, что значение истинности элемента A_i не будет установлено (A_i = ´), когда в действительности A_i = 1;

— вероятность того, что ошибочно будет принято A_i=0, тогда как на самом деле A_i= 1, и аналогичные по смыслу вероятности при условии, что фактически значением истинности элемента A_i является A_i =0.

Очевидно, что величины q_i удовлетворяют условиям

 

(10.2)

 

Установим зависимость величин р_ij от вероятностей q_i(1|1),

Пусть наблюдаемый в процессе эксперимента конкретный объект характеризуется каким-либо определенным набором признаков, выраженных через значения истинности элементов А₁ ..., ..., А_n. Устанавливаемые в результате опыта значения истинности элементов A_i могут отличаться от тех значений, которые присущи данному объекту. Будем предполагать, что события, состоящие в установлении значений истинности элементов А₁ ..., А_n, в результате эксперимента — независимые, так что вероятность одновременного наступления каких-либо событий равна произведению вероятностей этих событий.

При заданных фактических значениях истинности элементов А₁ ..., А_n у наблюдаемого объекта все возможные исходы эксперимента, производимого над данным объектом, определяются вероятностями Множество 3ⁿ несовместных исходов эксперимента вместе с отнесенными им вероятностями образует пространство элементарных событий рассматриваемого опыта.

Выберем из пространства элементарных событий точки, которые совпадают с множеством {f_i(A₁ ..., А_n)} всех импликант функции j_i(Ω_l, ..., Ω_m). Сумма вероятностей, отнесенных к этим точкам пространства элементарных событий, равна вероятности P[j_i|f(A₁ ..., А_n)] получить решение вида j_i(Ω_l, ..., Ω_m) при условии, что распознаваемый объект характеризуется определенным набором признаков, выраженных через фиксированные значения истинности элементов А₁ ..., А_n как булева функция f(A₁ ..., А_n)=1. Множество всех типов объектов, принадлежащих каждому классу описываемых функциями j_i(Ω_l, ..., Ω_m), определяется суммой импликант записанной в СДНФ.

Если ввести в рассмотрение вероятности r^aj_j появления объектов различных типов aj внутри каждого класса j_i(Ω_l, ..., Ω_m),), то величины р_ij выразятся как

Обозначим С_ij, i, j=l, ..., N, выигрыш (штраф), выплачиваемый при отнесении объекта го класса к i-му классу, a C_N+_1j — выигрыш (штраф), выплачиваемый в случае, когда об объекте из j-го класса не удается получить определенного решения вида j_i(Ω_l, ..., Ω_m). Тогда

 

(10.3)

 

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

Пусть, наконец, Q_j обозначает априорную вероятность появления объекта из j-го класса. Тогда

 

(10.4)

 

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

Различные системы, предназначенные для распознавания одних и тех же объектов, но отличающиеся либо способами определения значений истинности признаков А₁ ..., А_n и, следовательно, значениями вероятностей либо самой совокупностью признаков A_i привлекаемых для описания объектов, можно сравнивать между собой по значению величины R. Величина R характеризует степень приспособленности системы для решения стоящих перед ней задач в тех практических условиях, которые определяются вероятностями r^aj_j, Q_j и стоимостями С_ij, C_N+lj, и потому может быть принята в качестве критерия эффективности системы распознавания.

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

Пример. Требуется оценить эффективность системы распознавания объектов, описываемых признаками A₁¸A₄, связанными с классами Ω₁, Ω₂, Ω₃ зависимостью :

 

(10.5)

 

Пусть заданы функции

 

(10.6)

 

Допустим, что элемент А₁ обозначает высказывание «истинное значение x_i измеряемого параметра X_i принадлежит интервалу (a_i,b _i)»:

 

(10.7)

 

a `A_i есть утверждение

 

 

причем отрезки (a_i,b _i) и (l_i,g_i) не имеют общих точек (рис. 10.2).

Измеряемые параметры X_i представляются в виде

 

 

где x_i равномерно распределена либо в (a_i,b _i), либо в (l_ji,d_i), a x_i¢ имеет нормальное распределение с нулевым математическим ожиданием с среднеквадратичным отклонением s_i, т. е. плотность случайной величины x_i¢

 

(10.8)

 

Рис. 10.2

 

Обозначим a¢_i, b¢_i граничные точки некоторого интервала, охватывающего (a_i,b _i), a (g¢_i,d¢_i) — граничные точки другого интервала, охватывающего g_i, d_i (рис. 10.2), и примем следующее решающее правило: будем считать, что х_iÎ(a_i,b_i), если измеренное значение XÎ(a¢_i,b¢_i), и x_iÎ(g_i,d_i), если измеренное значение X_iÎ(g¢_i,d¢_i). В соответствии с этим из (10.7) и (10.8) найдем

 

(10.9)

 

где — функция Лапласа.

Точно так же

 

(10.10)

 

где — внешние части отрезков

И аналогично,

 

(10.11)

 

При заданных a_i,b _i, g_i,l_i можно варьировать значения a¢_i,b_¢i, g¢_i,d¢_i так, чтобы вероятности q_i(1|1), ..., q_i(´|0) соответствовали экстремальному значению показателя эффективности системы распознавания.

Найдем первые импликанты функций j_1, j₂, j₃, j₄ заданных (10.6). Соотношение (10.5) трансформируется в следующую таблицу сокращенного базиса b_´[A₁,A₂,A₃,A₄;Ω₁,Ω₂,Ω₃]:

 

(10.12)

 

Совершив переход от базиса b_´[A₁,A₂,A₃,A₄;Ω₁,Ω₂,Ω₃] к базису b_с[A₁,A₂,A₃,A₄;Ω₁,Ω₂,Ω₃] получим

 

(10.13)

 

Последние три строки базиса (10.13) — изображающие числа функции Ω₁(A₁,A₂,A₃,A₄), Ω₂(А₁, А₂, А₃, А₄), Ω₃(A₁,A₂,A₃,A₄) относительно полного стандартного базиса b[A₁,A₂,A₃,A₄]юПереходя от изображающих чисел к функциям, найдем

 

(10.14)

 

Так как то

 

(10.15)

 

и, кроме того,

 

(10.16)

 

Для определения первых импликант функций j_j можно было бы воспользоваться базисом (10.12) без перехода (10.13), что существенно при большом числе элементов A_i. Например, покажем, как найти первые импликанты функции j₁=`Ω<sub>1</sub>,`Ω₂,`Ω_3.

Перейдем к отрицанию j₁ т.е С колонкой отвечающей `Ω₁, сравнимы пять последних правых колонок базиса (10.12), поэтому или после преобразования

Аналогично с помощью оазиса (10.12) находим

 

 

откуда После обращения

 

(10.17)

 

Левая часть (10.17) совпадает с правой частью первого соотношения (10.14). Представим суммы (10.15) первых импликант функций в СДНФ:

 

(10.18)

 

Каждое слагаемое в (10.18) — конкретный тип f^aj j-то объекта из соответствующего класса j_j,j,= 1, 2, 3, 4, а значения индекса о,-— номера типов объектов в пределах каждого класса.

Рассмотрим объект класса j₁ первого типа:

 

(10.19)

 

Найдем вероятность P(j₁|f¹₁), с которой объект (10.19) будет отнесен при распознавании к классу j₁. Для этого в соответствии с (9.18) выпишем полный набор импликант функции

 

(10.20)

 

Вероятность P(j₁|f¹₁)равна вероятности воспринять на опыте признаки объектаf¹₁=А₁×А₂×A₃×`A₄ как какую-либо импликанту из набора (10.20):

 

 

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

 

 

Так как то в соответствии с формулой для вероятности суммы нескольких событий найдем

 

(10.21)

 

Учитывая (10.15) и (10.16), по аналогии с (10.21) получим

 

(10.22)

 

Точно так же могут быть определены и все оставшиеся 15´4=60 величин P(j₁|f^aj_j), где f^aj_j обозначает a_j-й объект в классе j_j.

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

 

 

Значения средних условных выигрышей на одно решение будут равны:

 

 

где C_ij,j= 1, 2, 3, 4 — выигрыш, когда объект из j-го класса принимается за объект из i-го класса; С₅j — размер платежа, когда об объекте из j-го класса не принимается никакого решения.

Безусловный средний выигрыш на одно решение

 

 

Как уже отмечалось, величина R существенно зависит от значений a¢_i,b_¢i, g¢_i,d¢_i, i=1, 2, 3, 4, входящих в вероятности q_i(1|1), ..., q_i(х|0), определенные (10.9) — (10.11). Параметры a¢_i,b_¢i, g¢_i,d¢_i могут быть связаны рядом условий вида

 

(10.23)

 

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

Когда число признаков А₁ ..., А_n объектов велико, вычисление значений критерия эффективности системы распознавания R представляет собой, как правило, трудную задачу. Основные трудности — в множественном переборе объектов различных классов f^aj_j при подсчете вероятностей P(j_i|f^aj_j) и применении формулы для вероятности суммы большого числа совместных событий. Для преодоления этих трудностей также можно использовать метод Монте — Карло (метод статистических испытаний). Общая идея этого метода — в моделировании и многократном повторении условий опыта по определению признаков A₁, ..., А_n известных типов объектов и применению решающего правила для установления класса испытываемого объекта. Подсчитав число N^aj_i решений, приводящих к заключению j_i(Ω₁ ,... Ω_m) при фиксированном типе объекта f^aj_j, можно дать оценку значения вероятности P(j_i|f^aj_j), если разделить N^aj_j на общее число N^aj испытаний, проведенных с объектом типа f^aj_j, т. е.

Число испытаний N, необходимое для того, чтобы вероятность отклонения оценки величины от своего истинного значения меньше чем на 2d превышала 1-e, определяется по формуле [34]

 

(10.24)

 

Исходными данными для метода Монте — Карло в задаче служат:

1. Таблица сокращенного базиса b_с[А₁ ..., А_n; Ω₁ ..., Ω_m], представляющая собой различные типы объектов. Каждый столбец сокращенного базиса с точки зрения системы признаков А₁ ..., А_n и классов Ω₁ ..., Ω_m можно рассматривать как определенный тип объекта f^aj_j(А₁ ..., А_n), входящий в рассматриваемое множество.

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

3. Запрограммированный на ЭВМ алгоритм нахождения решения j(Ω₁ ..., Ω_m) системы булевых уравнений:

 

(10.25)

 

где Е(А_i; Ω_j) — функция, представляющая собой наложенные на элементы A_i, и Ω_j, связи; f(A_1, ..., А_n) — функция, определяемая в результате опыта над классифицируемым объектом.

Построенная по этим исходным данным стохастическая модель распознавания объектов зависит от конкретных физических условий, при которых проводится опыт, а также от характеристик аппаратуры, предназначенной для определения признаков объектов через вероятности q_i(1|1), ..., q_i(´|0).

Опишем алгоритм работы рассматриваемой модели. Предположим, что указанные исходные данные занесены в память ЭВМ. Обозначим x_m m-ю реализацию случайной велияины x, равномерно распределенной в интервале [0, 1]. Величина вырабатывается соответствующим датчиком случайных чисел каждый раз независимо.

Предположим, что произведено разбиение отрезка (0, 1) и раз на три части, пропорциональные и еще n раз на три части, пропорциональные , i=l, 2, ..., n.

Испытания проводятся последовательно для каждого типа объекта f^aj_j(А₁ ..., А_n). Пусть объекту типа f^aj_j(А₁ ..., А_n)соответствует некоторая колонка сокращенного базиса b_c[А₁ ..., А_n; Ω₁ ..., Ω_m]. Перенесем эту колонку в v-ю рабочую ячейку памяти ЭВМ. В этой ячейке значения истинности признаков А₁ ..., А_n, равные 0 или 1, случайным образом подвергаются изменению в соответствии со значениями вероятностейи Для колонки с номером v процедура изменения значений истинности признаков А_i производится в такой последовательности. С помощью операции сравнения устанавливают содержимое i-го разряда v-й ячейки. Если A_i=l, то переходят к проверке условий

 

(10.26)

 

если A_i=0, то проверяют условия

 

(10.27)

 

где x_m — реализация случайной величины x, равномерно распределенной в [0, 1].

Если А_i= 1 и выполняется первое условие (10.26), содержимое i-го разряда v-й ячейки не изменяется, если выполняется второе условие (10.26), то А_i = 1 заменяется на А_i =0, если имеет место последнее неравенство (10.26), то A_i= 1 заменяется на А_i = ´.

Если А_i =0 и удовлетворяется первое из условий (10.27), то A_i=0 сохраняется неизменным; если выполняется второе условие (10.27), то A_i=0 заменяется на A_i= 1, если выполняется последнее условие (10.27), то содержимое i-го разряда v-й ячейки заменяется на A_i= ´.

Переходят к следующему (i+ 1)-му разряду v-й ячейки и для очередной (m+ 1)-й реализации x_m+1 случайной величины x проверяются условия (10.26) или (10.27).

Измененная в соответствии с данными правилами v-я ячейка поступает на вход алгоритма решения задачи (10.25). После получения решения j(Ω₁ ..., Ω_m) устанавливается, какой из случаев

 

(10.28)

 

реализуется при заданном типе распознаваемого объекта f^aj_j(А₁ ..., А_n). В результате многократного повторения описанного процесса по дочитываются количества N^aj_i выпадений каждого из N^ajслучаев (10.28) и определяются оценки величин P(j_i|f^aj_j).