Методы распознавания (стр. 1 )

Рабочий учебник

Фамилия, имя, отчество обучающегося___________________________________________________

Направление подготовки_______________________________________________________________

Номер контракта______________________________________________________________________

МЕТОДЫ РАСПОЗНАВАНИЯ

ГЛАВА 2

Рабочий словарь признаков систем распознавания.
Методы алгебры логики в распознавании.
Логические системы распознавания

МОСКВА 2006

Разработано , д-ром техн. наук, проф.

КУРС: МЕТОДЫ РАСПОЗНАВАНИЯ

Глава 1. Общая постановка проблемы распознавания. Вероятностные системы распознавания.

Глава 2. Рабочий словарь признаков систем распознавания. Методы алгебры логики в рас-познавании. Логические системы распознавания.

Глава 3. Структурные методы распознавания. Управление процессом распознавания и оцен-ка эффективности систем распознавания.

ГЛАВА 2

Изложены методы построения словаря признаков и рабочего словаря. Рассмотрены основные понятия алгебры логики, методы решения логических задач распознавания, алгоритмы распозна-вания, основанные на вычислении оценок (АВО).

ОБ АВТОРЕ

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

Лауреат Государственной премии СССР.

Заслуженный деятель науки РФ.

Действительный член Международной Академии информатизации.

Почетный академик Академии космонавтики им. .

Полковник в отставке. Участник Великой Отечественной войны.

Начальник лаборатории «Методы распознавания»

Стаж научно-педагогической работы 45 лет.

Опубликовал свыше 100 печатных работ, в том числе 6 научных монографий и 4 учебных пособия. Под его научным руководством защищено 20 кандидатских и 5 докторских диссертаций.

ОГЛАВЛЕНИЕ

Стр.

ДИДАКТИЧЕСКИЙ ПЛАН.. 5

ЛИТЕРАТУРА.. 6

ТЕМАТИЧЕСКИЙ ОБЗОР. 7

1. РАБОЧИЙ СЛОВАРЬ ПРИЗНАКОВ СИСТЕМ РАСПОЗНАВАНИЯ
ОБЪЕКТОВ И ЯВЛЕНИЙ.. 7

1.1. Построение рабочего словаря детерминированных признаков
при ограниченных ресурсах. 7

1.2. Построение рабочего словаря признаков с учетом вероятности их определения. 12

1.3. Игровой подход к построению рабочего словаря признаков. 15

1.4. Построение рабочего словаря признаков при вероятностном описании классов. 17

1.5. Сравнительная оценка признаков. 19

1.6. Построение рабочего словаря признаков при отсутствии
априорного словаря признаков. 24

2. ВЫЧИСЛИТЕЛЬНЫЕ МЕТОДЫ АЛГЕБРЫ ЛОГИКИ.. 26

2.1. Основные понятия алгебры логики. 27

2.2. Изображающие числа и базис. 29

2.3. Восстановление булевой функции по изображающему числу. 31

2.4. Зависимость и независимость высказываний. 33

2.5. Булевы уравнения. 34

2.6. Замена переменных. 39

2.7. Решение логических задач распознавания. 47

3. ЛОГИЧЕСКИЕ СИСТЕМЫ РАСПОЗНАВАНИЯ ОБЪЕКТОВ И ЯВЛЕНИЙ.. 51

3.1. Решение задач распознавания при большом числе элементов. 51

3.2. Алгоритм построения сокращенного базиса. 57

3.3. Распознавание состояний научно-технического прогресса. 59

3.4. Распознавание объектов в условиях их маскировки. 66

3.5. Распознавание в условиях противодействия. 68

3.6. Алгоритмы распознавания, основанные на вычислении оценок. 72

ЗАДАНИЯ ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ... 78

ГЛОССАРИЙ.. 80

ДИДАКТИЧЕСКИЙ ПЛАН

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

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

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

ЛИТЕРАТУРА

Основная

1. Васильев обучения распознаванию образов. Принципы, алгоритмы реализа-ции. – Киев: Высшая школа, 1989.

2. , , Родзин -методическое пособие для самосто-ятельной работы по курсам: «Система искусственного интеллекта», «Методы распознавания образов». – Таганрог: ТРТУ, 1999.

3. , , Скрипкин состояние проблемы распозна-вания. – М.: Радио и связь, 1985.

4. , Скрипкин распознавания: Учеб. пособие для вузов. – 4-е изд., испр. – М.: Высшая школа, 2004.

Дополнительная

1. Горелик задачи распознавания объектов и явлений // Кибернетика. 1986. № 5.

2. , С. Об условиях аддитивности информации в задачах распознавания объектов и явлений // Кибернетика. 1983. № 6.

3. Классификация и кластер: Пер. с англ. / Под ред. . – М.: Мир, 1980.

4. А. Методы оптимальных решений в распознавании изображений. – М.:
Наука, 1976.

5. Распознавание. Классификация. Прогноз / Под. ред. – М.: Наука, 1989.

6. Словарь по кибернетике. – Киев: Гл. ред. Украинской советской энциклопедии, 1979.

7. Восприятие и распознавание образов: Пер. с фр. – М.: Машиностроение, 1989.

8. Экспертные системы / Под ред. Р. Форсайта: Пер. с англ. – М.: Радио и связь, 1987.

ТЕМАТИЧЕСКИЙ ОБЗОР*

1. рАБОЧИЙ СЛОВАРЬ ПРИЗНАКОВ СИСТЕМ РАСПОЗНАВАНИЯ
ОБЪЕКТОВ И ЯВЛЕНИЙ

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

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

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

Постановка задачи. Пусть в результате классификации все множество объектов Ω = {ω} разбито на непересекающиеся подмножества Ω1, Ω2, ..., Ωm, каждое из которых и будет составлять соответствующий класс. Обозначим объекты, относящиеся к каждому классу, следующим образом:

Ω1 = {ω11, ω12, ω1k1}; Ω2 = {ω21, ω22, ...,ω2k2}; ...; Ωp = {ωp1, ωp2, ..., ωpk}; ...; Ωm = {ωm1, ωm2, ..., ωmkm}.

Если признаки объектов обозначить xj, j = l, 2, ..., N, то каждый объект в N-мерном пространстве признаков может быть представлен в виде вектора х = (x1, х2, ..., xN), координаты которого характеризуют свойства объекта.

Для определения сходства между объектами вводится метрика - мера близости или подобия между объектами в N-мерном векторном пространстве признаков. Выбор метрики произволен,

необходимо лишь, чтобы она удовлетворяла обычным аксиомам расстояний d(a, b) = d(b, a);
d(a, c)£d(a, b)+d(b, с); d(a, b)³0; d(a, b) = 0 тогда и только тогда, когда а = b. Далее, не нарушая общности рассуждений, будем пользоваться эвклидовой метрикой

где xjpk есть значения j-гo признака k-го объекта р-гo класса, т. е. объекта ωpk; xjql — значение j-гo признака l-го объекта q-го класса, т. е. объекта ωql.

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

В качестве меры близости между объектами данного класса Ωp, р = 1, 2, ..., m, будем использовать величину

(1.1)

которую назовем среднеквадратичным разбросом класса - мерой близости между объектами данного класса ΩР.

В качестве меры близости между объектами данной пары классов ΩР и Ωq, p, q = 1, ..., m, будем использовать величину

(1.2)

которую назовем среднеквадратичным разбросом объектов классов Ωр и Ωq - мерой близости между объектами данной пары классов.

Совокупность признаков объектов, используемых в рабочем словаре, можно описать
N-мерным вектором (l=l1, l2, ..., ln), компоненты которого принимают значения 1 или 0 в зависимости от того, имеется или отсутствует возможность определения соответствующего признака объекта, т. е. lj= . С учетом l квадрат расстояния между объектами wрк и wql составит

Следовательно, среднеквадратичные разбросы класса Ωр и объектов классов Ωр и Ωq могут быть записаны соответственно так:

(1.3)

(1.4)

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

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

(1.5)

где Сj — затраты на создание технического средства, обеспечивающего определение j-го признака.

В качестве критерия эффективности проектируемой системы распознавания рассмотрим функционал, зависящий в общем случае от функций S(Ωp), R(Ωp, Ωq) и решающего правила
L(ω, {ωg}), т. е.

(1.6)

Пусть величина L(ω, {ωg}) — мера близости между распознаваемым объектом ω и классом Ωg, g = l, 2, ..., m, заданным своими объектами {ωg}:

(1.7)

Эта величина является среднеквадратичным расстоянием между объектом ω и объектами класса Ωg.

Решающее правило состоит в следующем ω Î Ωg, если L(ω, {ωg}) =

Уменьшение S(Ωp), т. е. «сжатие» объектов, принадлежащих каждому данному классу, при одновременном увеличении R(Ωp, Ωq), т. е. «разведении» объектов, принадлежащих разным классам, обеспечивает в конечном счете улучшение эффективности системы распознавания. Поэтому повышение эффективности системы будем связывать с достижением экстремума функционала J.

Задача может быть сформулирована следующим образом. Пусть все множество объектов подразделено на классы Ωi, i = 1, ..., m, априорно описаны все классы на языке признаков xj,
j = 1,..., n, и на создание технических средств наблюдений выделены ресурсы С0. Требуется, не превышая величины С0, построить рабочий словарь признаков, обеспечивающий максимально возможную эффективность системы.

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

(1.8)

Изложенная постановка задачи имеет геометрический смысл. Однако если учесть, что функция S(Ωp) характеризует эмпирический ряд распределения объектов в р-м классе, а функция R (Ωp, Ωq) — взаимное расположение эмпирических статистических рядов, соответствующих классам р и q (p, q = 1, ..., m), то обнаруживается связь рассматриваемого подхода со статисти-ческим подходом к распознаванию объектов.

Частные виды функционала (1.6). Если требуемая эффективность системы распознавания

может быть достигнута за счет более компактного расположения объектов каждого класса при соблюдении некоторых условий относительно R (Ωp, Ωq), то задача сводится к нахождению

(1.9)

при

Если требуемое значение критерия эффективности системы может быть достигнуто за счет «удаления» друг от друга объектов, принадлежащих разным классам при соблюдении некоторых условий относительно S(Ωi), i=1, ..., m, то задача сводится к нахождению

(1.10)

при

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

(1.11)

при

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

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

Квадрат расстояния между парой классов

(1.12)

где lj= 1, если j-й признак используется в словаре признаков, или lj= 0 в противном случае.

Все пары из m классов можно перенумеровать, вводя индекс r = 1, ..., n, где

Если выражение в квадратных скобках (1.12) обозначить pjr (где r — номер пары классов, j — номер признака), то квадрат расстояния для r-й пары

(1.13)

где рjr — информативность j-го признака для r-й пары классов.

Теперь задачу можно записать в следующем виде:

(1.14)

при

где

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

2. Метод штрафных функций состоит в замене задачи отыскания относительного максимума функции F(x) при условиях ji(х) = 0, i = l, ..., m, задачей отыскания абсолютного максимума функции

(1.15)

где Li — некоторые положительные постоянные; — штрафные функции.

Если условия связи выполнены, то F(х) = Ф(х), в противном случае второе слагаемое в правой части (1.15) характеризует меру отклонения точки от поверхности ji(х) = 0.

Если для отыскания максимума функции Ф(х) применить градиентный метод, т. е. использовать рекуррентное соотношение

где t — шаг, то второе слагаемое будет компенсировать дефект в выполнении условий связи. Чем больше Li, тем больше штраф за нарушение условий связи.

В рассмотренной постановке задачи определения оптимального словаря признаков предполагалось, что априорная вероятность появления объектов различных классов неизвестна. Если Р(Ωi), i=l, ..., m, известна, то естественно считать оптимальным такой набор признаков рабочего словаря системы распознавания, который обеспечивает не максимальное гарантированное значение критерия эффективности системы, а максимальное значение математического ожидания критерия эффективности.

Пусть априорные вероятности появления объектов классов Ωp и Ωq, р, q = l, ..., m, соответственно равны F(Ωp) и P(Ωq). Тогда априорная вероятность появления объектов обоих классов в предположении независимости этих событий Pr = P(Ωp)P(Ωq), r = 1, ..., n, и n = С2m. Математическое ожидание квадрата среднеквадратичного расстояния между всеми парами классов

(1.16)

Условие задачи, записанное в виде (1.14), при наличии дополнительной информации относительно величины P(Ωi), может быть сформулировано следующим образом: в условиях заданных ограничений на ресурсы, выделяемые для разработки измерительной аппаратуры, реализующей признаковое пространство, необходимо определить такой состав рабочего словаря признаков системы распознавания, который обеспечивает максимальное значение критерия эффективности — математического ожидания величины Rr2, т. е. следует найти такой вектор l0[Р(Ωi)], который обеспечивает

(1.17)

при

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

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

1.2. Построение рабочего словаря признаков с учетом вероятности
их определения

Реализация предложенного выше метода построения пространства признаков системы распоз-навания обеспечивает в пределах выделенных ресурсов на создание технических средств, с по-мощью которых должно осуществляться определение признаков, максимальное значение крите-рия качества функционирования системы распознавания. Одно из предположений, на котором базируется данный метод, заключается в том, что создание каждого технического средства наблю-дения системы распознавания автоматически обеспечивает определение соответствующего приз-нака объекта или явления. Метод, таким образом, не предусматривает учета того факта, что любое техническое средство лишь с определенной вероятностью (отличной от единицы) обеспечивает измерение соответствующих признаков распознаваемых объектов или явлений. При этом под вероятностью определения j-го признака, распознаваемого объекта или явления Pj, j=1,…, N, будем подразумевать вероятность факта измерения значения этого признака при данных условиях проведения эксперимента (опыта).

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

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

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

Постановка задачи. Пусть все множество объектов, для распознавания которых предназначается проектируемая система, подразделено на классы Ω1 ..., Ωm, в априорном словаре системы содержатся признаки хj, j = 1, ..., Na, ресурсы на создание технических средств измерения признаков составляют С0. Обозначим Cj затраты на создание технического средства Tj, предназначенного для определения j-го признака, а Рj(Cj) — вероятность определения этого признака с помощью данного средства. При этом будем исходить из естественного предположения о том, что Pj(Cj) монотонно возрастает, т. е. [dPj(Cj)/(dCj)] > 0. Кроме того, Pj(Cj = 0) = 0, Рj(Сj = ¥) = 1 и Pj(Cj) < 1 для любого конечного значения затрат Сj.

Признаки объектов, принадлежащие множеству признаков априорного словаря системы распознавания, определение которых становится возможным благодаря созданию соответствую-щих технических средств, образуют рабочий словарь признаков xj, j=1, ..., Np, системы распоз-навания. При построении реальных систем распознавания объем рабочего словаря существенно меньше объема априорного словаря, т. е. Np £ Nt. При создании сложных систем распознавания после определения признакового пространства основное — это разработка и создание технических средств — аппаратуры, предназначенной для измерения признаков. Например, при построении систем медицинской диагностики едва ли не самая сложная задача — создание высококачест-венной диагностирующей аппаратуры (электрокардиографов, электроэнцефалографов, рентгенов-ской аппаратуры и т. д.).

В качестве критерия качества системы распознавания используем математическое ожидание квадрата среднеквадратичного; расстояния между объектами классов Ωр, Ωq, p, q=1, ..., m. Все пары из m классов перенумеруем, вводя индекс r = 1, ..., n. Тогда с учетом зависимости Рj=Рj(Сj) квадрат расстояния для r-й пары классов

(1.18)

где

Здесь xjpk — значение j-го признака у k-го объекта р-го класса, xjql — значение j-го признака у l-го объекта q-гo класса, kр и kq — количество объектов в р- и q-м классах объектов соответственно.

Величина pjr характеризует разделительные свойства (разрешающую способность) j-го признака для r-й пары классов. Легко заметить, что R2r — математическое ожидание квадрата среднеквадратичного расстояния между объектами данной пары классов в признаковом пространстве (х1 ..., ).

Пусть компоненты вектора С = (C1...,) определяют затраты ресурсов на создание каждого технического средства Tj. Тогда критерий качества функционирования системы распознавания

(1.19)

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

(1.20)

При этом стратегия С, для которой заведомо неоптимальна.

Метод решения задачи. Рассмотренная задача — обобщение задачи нелинейного программирования. Условия оптимальности для нее можно сформулировать следующим образом: для того чтобы вектор С0 являлся оптимальной стратегией, необходимо, а в случае вогнутости функции W(C) и достаточно, чтобы существовали скаляр l ³ 0 и вектор m = {m1 ..., mn}, такие, что

(1.21)

Введение в рассмотрение скаляра l и вектора m увеличивает количество неизвестных C0j, mr и l до величины Np + n + l. Однако число уравнений равно числу неизвестных, так как для любого r либо mr = 0, либо

Таким образом, решение системы уравнений (1.21) и дает возможность определить состав признаков рабочего словаря и оптимальное распределение затрат на создание средств наблюдений системы распознавания в условиях предположения о зависимости Pj = Pj(Cj) и ограничений на величину ресурсов, выделенных для разработки этих средств. Достаточное условие вогнутости функции W(C) по вектору С — вогнутость по Cj функций Pj = Pj(Cj), "j (рис. 1.1), т. е.

(1.22)

Рис. 1.1. Вогнутость функций Pj по Cj

Вогнутость функций Pj = Pj(Cj), j = 1, ..., Np, имеет естественную физическую интерпретацию: с ростом вкладов Сj и приближением Pj к единице эффективность вкладов, т. е. отношение прираще-ния Pj к приращению Сj, уменьшается, а добиться равенства Pj = 1 практически невозможно.

1.3. Игровой подход к построению рабочего словаря признаков

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

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

Возможны различные случаи информированности сторон. Будем предполагать следующее: сторона А, при создании системы распознавания, знает всю совокупность объектов или явлений стороны В, но не знает системы ее противодействия, сторона В, при выборе системы противодействия, знает систему распознавания стороны А.

Стратегия стороны А — N-мерный вектор l, компоненты которого принимают значения 1 или 0 в зависимости от того, используется или не используется признак объекта хj, j = 1, 2,..., N, стороны В. На множество стратегий стороны А наложено ограничение — затраты ресурсов на создание технического средства, предназначенного для определения j-го признака, СA — общая величина ресурсов, ассигнованных на разработку технических средств.

Стратегия стороны В — N-мерный вектор m, компоненты которого принимают значения 0 или 1 в зависимости от того, противодействует или не противодействует сторона В определению соответствующего признака. Будем считать, что если сторона В противодействует определению данного признака, то его измерение становится полностью невозможным, даже если соответствующее техническое средство измерения создано стороной А. На стратегию стороны В наложено ограничение где — затраты на противодействие определению j-гo признака создаваемых объектов, СB — общая сумма ресурсов, ассигнованных на создание системы противодействия распознаванию объектов.

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

(1.23)

где r — номер пары классов объектов или явлений; n — число пар классов; рjr — характеризует информативность j-ro признака при классификации объектов, принадлежащих r-й паре классов.

Сторона А стремится к максимизации W(l, m), а сторона В — к его минимизации. В условиях заданной информированности сторон оптимальная стратегия стороны А — максминная стратегия, т. е. такое l0 = (l01, ..., l0N), что

(1.24)

где

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

Задача заключается в определении стратегии l0.

В описанной постановке задачи о противодействии системе распознавания предполагается следующее. Если сторона В выполняет некоторые мероприятия, препятствующие стороне А в определении j-го признака, j = 1, ..., N, то это приводит к тому, что технические средства наблю-дения системы распознавания полностью лишаются возможности определять данный j-й признак. Рассмотренная задача может быть обобщена на случай, когда мероприятия стороны В, связанные с противодействием системе распознавания, приводят к тому, что признаки хj объектов средствами системы распознавания определяются с некоторыми вероятностями Pjопр, j= 1, ..., N.

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

(1.25)

где L — см. пояснение к (1.24), а или 1,

Предполагается, что затраты на проведение мер противодействия определению j-го признака зависят от значения Pjопр, т. е. СBj = СBj(Pjопр).

Таким образом, и в данном случае возникает дискретная максминная задача с ограничениями на переменные l и m, а ее решение может быть получено также на основе применения метода штрафных функций, подобно тому, как это выполнено выше. При этом если мероприятия стороны В полностью исключают возможность определения j-го признака, то Pjопр = 0 и (1.25) преобразуется к виду (1.24).

Построение технических средств наблюдения системы распознавания в соответствии с найденным значением l0 = {l01, ..., l0N}, при любой схеме противодействия избранной стороной В, обеспечивает системе распознавания максимальную гарантированную эффективность.

1.4. Построение рабочего словаря признаков при вероятностном описании классов

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

Рассмотрим ту же задачу при наличии вероятностного описания классов. Пусть заданы алфавит классов Ωi, i = 1, ..., m, априорный словарь признаков хa = {х1 ..., хN}, априорные вероят-ности Р(Ωi), условные плотности распределения вероятности fj(x) и платежная матрица вида (1.4). Будем полагать также, что известны условные плотности вероятности значений любого наперед заданного подмножества признаков, принадлежащего множеству признаков априорного словаря, т. е. функции fi(xj1..., хjk), где {j1, ..., jk}Î{l, 2, ..., N}, jk £ N, и ограничения, накладываемые на харак-теристики Gr0, r = 1, 2, 3, ..., комплекса измерительной аппаратуры, предназначенной для определения признаков распознаваемых объектов. Пусть G10 — допустимая стоимость комплекса аппаратуры, G20 — предельная допустимая масса комплекса, G30 — предельный объем, занимаемый комплексом, G40 — предельная потребляемая мощность и т. д.