рефераты конспекты курсовые дипломные лекции шпоры

Реферат Курсовая Конспект

ОБЩАЯ ХАРАКТЕРИСТИКА ПРОБЛЕМЫ РАСПОЗНАВАНИЯ ОБЪЕКТОВ И ЯВЛЕНИЙ

ОБЩАЯ ХАРАКТЕРИСТИКА ПРОБЛЕМЫ РАСПОЗНАВАНИЯ ОБЪЕКТОВ И ЯВЛЕНИЙ - раздел Философия, А. Л. Горелик ...

А. Л. Горелик

В. А. Скрипкин

Методы распознавания

 

1. ОБЩАЯ ХАРАКТЕРИСТИКА ПРОБЛЕМЫ РАСПОЗНАВАНИЯ ОБЪЕКТОВ И ЯВЛЕНИЙ

 

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

 

Качественное описание задачи распознавания i

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

Основные задачи построения систем распознавания

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

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

 

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

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

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

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

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

Одноуровневые сложные системы. В этих системах апостериорная информация о признаках распознаваемых объектов х1 ...,xN определяется прямыми измерениями непосредственно на основе обработки результатов экспериментов (рис. 1.2, где АИ — априорная информация; БАР — блок алгоритмов распознавания; БУРС — блок управления работой средств).

Многоуровневые сложные системы. В этих системах апостериорная информация о признаках определяется на основе косвенных измерений. Для таких измерений используются специализированные локальные распознающие системы (рис. 1.3, где АИ — априорная информация; БАР — блок алгоритмов распознавания; БУРС — блок управления работой средств).

В одноуровневых системах (см. рис. 1.2) по данным технических средств Т1, ..., Тр, ..., Тn, на основе обработки полученных реализаций непосредственно находят признаки х11, ..., хk1 х1p, ..., х1р; х1n, ..., хmn неизвестных объектов или явлений, которые используются для их распознавания.

В многоуровневых системах (рис. 1.3) по данным технических средств Т1 ..., Тр, ..., Тn, определяются признаки х11, ..., хk1 х1p, ..., х1р; х1n, ..., хmn (назовем их первичными), которые подразделяются на следующие группы.

 

 

Рис. 1.2

 

Группа 1. К ней относят признаки, используемые в локальных распознающих устройствах первого (нижнего) уровня (назовем эти признаки признаками первого уровня) для определения признаков второго уровня. На рис. 1.3 такими признаками являются х21, xlp, x2p, x1n, x2m, xnm. На основе этих признаков распознающие устройства первого уровня А, В, С определяют признаки второго уровня хA2, xB2, хC2.

Группа 2. К ней относят признаки, непосредственно используемые в распознающих устройствах второго уровня для определения признаков третьего уровня. На рис. 1.3 таким признаком является хk1, используемый наряду с признаками второго уровня xA2 и хB2 в распознающем устройстве второго уровня D для определения признака третьего уровня xD3.

Группа 3. К ней относят признаки, используемые в распознающих устройствах третьего уровня для определения признаков четвертого уровня, и т. д.

 

 

Рис. 1.3

 

К последней группе относят признаки, непосредственно используемые в процессе распознавания неизвестных объектов, т. е. признаки, входящие в рабочий словарь признаков системы распознавания. На рис. 1.3 такими признаками являются х11 и х1р (назовем эти признаки признаками верхнего уровня).

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

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

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

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

Будем считать, что для построения этого класса систем необходимо располагать полной первоначальной априорной информацией. На рис. 1.4 (где ТС — технические средства; АИ — априорная информация; БАР — блок алгоритмов распознавания) представлена структурная схема системы без обучения.

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

 

 

Рис. 1.4

 

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

 

(1.8)

 

Объекты w1 ..., wt представляют собой обучающие объекты (обучающая последовательность, обучающая выборка). Цель процедуры обучения — определение разделяющих функций Fi(x1, ..., xN), i = l, ..., m, путем многократного предъявления системе распознавания различных объектов с указанием классов, к которым эти объекты принадлежат.

Системы распознавания, обучающиеся на стадии формирования, работают с «учителем». Эта работа заключается в том, что «учитель» многократно предъявляет системе обучающие объекты всех выделенных классов и указывает, к каким классам они принадлежат. Затем «учитель» начинает «экзаменовать» систему распознавания, корректируя ее ответы до тех пор, пока количество ошибок в среднем не достигнет желаемого уровня. На рис. 1.5 (где 00 — обучающие объекты; ТС — технические средства; БАО — блок алгоритмов обучения; АИ — априорная информация; БАР — блок алгоритмов распознавания; штриховые линии — режим обучения, сплошные линии — «экзамен») приведена схема обучающейся системы.

Самообучающиеся системы. В этих системах первоначальной априорной информации достаточно лишь для определения словаря признаков x1, ..., xN, но недостаточно для проведения классификации объектов. На стадии формирования системы ей предъявляют исходную совокупность объектов w1 ..., wl, заданных

 

 

Рис. 1.5

 

значениями своих признаков для w1 — (x11 ..., х1N); ...; для w1— (x11 ..., х1N). Однако из-за ограниченного объема первоначальной информации система при этом не получает указаний о том, к какому классу объекты исходной совокупности принадлежат. Эти указания заменяются набором правил, в соответствии с которыми на стадии самообучения система распознавания сама вырабатывает классификацию, которая, вообще говоря, может отличаться от естественной, и в дальнейшем ее придерживается. На рис. 1.6 (где ОС — объекты для самообучения; ТС — технические средства; БАР — блок алгоритмов распознавания; АИ — априорная информация; ПК — правила классификации; ФК — формирование классов; штриховые линии — режим самообучения; сплошные линии — распознавание неизвестных объектов) приведена схема самообучающейся системы.

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

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

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

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

 

 

Рис. 1.6

 

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

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

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

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

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

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

 

 

Рис. 1.7

 

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

 

Экспертные системы распознавания

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

Содержательная трактовка проблемы распознавания

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

Постановка задачи распознавания

Пусть задано множество объектов или явлений Ω={w1 ..., ..., wz}, а также множество возможных решений L={l1, ..., lk}, которые могут быть… Пусть первоначальная информация позволяет построить априорное признаковое… Пусть первоначальная информация позволяет построить априорное признаковое пространство (составить априорный словарь…

Метод решения задачи распознавания

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

Глава 3 ОБРАБОТКА АПРИОРНОЙ ИНФОРМАЦИИ

 

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

 

Системы распознавания без обучения

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

Обучающиеся системы распознавания

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

Самообучающиеся системы распознавания

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

Некоторые сведения из теории статистических решений

Рассмотрим основные результаты теории статистических решений на следующем примере. Пусть совокупность объектов подразделена на классы Ω1 и… Чтобы определить, к какому классу отнести объект, обозначим х0 некоторое, пока…  

Критерий Байеса

Критерий Байеса — правило, в соответствии с которым стратегия решений выбирается таким образом, чтобы обеспечить минимум среднего риска. Применение… Минимум риска, усредненного по множеству решений задачи распознавания… Стратегию, основанную на этом правиле, называют байесовской стратегией, а минимальный средний риск — байесовским…

Минимаксный критерий

При построении систем распознавания возможны такие ситуации, когда априорные вероятности появления объектов соответствующих классов неизвестны.… Минимаксная стратегия состоит в том, что решение о принадлежности неизвестного… При наличии классов Ω1 и Ω2 байесовский риск с учетом того, что P(Ω2) = 1 —P(Ω1), c11 = c22 =…

Критерий Неймана—Пирсона

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

Процедура последовательных решений

Ранее предполагалось, что решение о принадлежности распознаваемого объекта w соответствующему классу Ωi, i=l, ..., m, принимается после… Последовательное и многократное решение задачи распознавания с использованием… Рассмотрим суть последовательной процедуры распознавания. Пусть множество объектов подразделено на классы Ω1 и…

Регуляризация задачи распознавания

В соответствии со стратегией Байеса, если у распознаваемого объекта со измеренное значение признака х = х0 , то  

Задача селекции объектов и явлений

 

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

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

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

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

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

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

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

Постановку задачи селекции рассмотрим сначала применительно к простейшей, довольно распространенной на практике ситуации, когда в выборке из и объектов находится ровно один объект первого класса, который и надлежит отселектировать, а все остальные (n—1) объекты относятся к нулевому фоновому классу [20].

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

Пусть в результате измерения значений признака х для каждого из n объектов получены значения xi где i — номер объекта (i=1, ..., n). При наличии этой информации проверяемые статистические гипотезы сформулируем следующим образом: гипотеза Hi состоит в том, что именно i-й объект относится к первому классу и, следовательно, все остальные объекты относятся к нулевому классу. Задача синтеза алгоритма селекции состоит в том, чтобы определить наилучшее с точки зрения некоторого критерия эффективности решающее правило, в соответствии с которым следует принимать одну из гипотез Нi.

При распознавании в качестве критериев эффективности обычно рассматривают условные вероятности ошибочных решений. Так, в двухальтернативном варианте — это ошибки первого и второго рода. Например, при решении задачи обнаружения это «пропуск цели», если она есть, и «ложная тревога», когда цели нет. В общем случае при числе альтернатив n количество видов ошибочных решений составляет n (n — 1). При селекции правильное и все виды ошибочных решений образуют полную группу несовместных событий, причем, какой именно из объектов фоновой группы принять в качестве истинного объекта, существенного значения не имеет. Вероятности правильного и всех видов ошибочных решений в сумме составляют единицу. Отсюда следует, что полный апостериорный средний риск при любом соотношении между стоимостями правильного и ошибочных решений будет минимальным, если решения в пользу той или иной из гипотез приняты по критерию максимума апостериорной вероятности.

Рассмотрим задачу синтеза алгоритмов селекции.

Плотность вероятности получения выборки х^{х1, ..., хi, ..., хn} при условии, что гипотеза Hi верна, можно представить в виде

 

(4.57)

 

где li=f1(xi)/f0(xi) — отношение правдоподобия.

Апостериорную вероятность гипотезы Hi при условии получения выборки х‚ рассчитывают по формуле Байеса:

 

(4.58)

 

Если решения принимают по критерию максимума апостериорной вероятности, то решающее правило имеет вид

 

(4.59)

 

Это правило в отличие от решающего правила, применяемого при распознавании, пороговым не является.

В более общем случае, когда наблюдателю известны априорные вероятности Рi гипотез Hi решающее правило имеет вид:

 

(4.60)

 

Приведем два примера применения правила (4.59). Пусть измеренные значения признака х для обоих классов объектов распределены по нормальному или экспоненциальному закону, т. е.

 

(4.61)

 

или

 

(4.62)

 

Тогда с точностью до независящих от х сомножителей

 

 

или

 

 

соответственно.

Если m1>m0, то из-за монотонности экспоненциальной функции

 

(4.63)

 

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

Иногда для решения задачи селекции достаточно располагать данными о параметрах распределения признаков только одного из классов — селектируемого.

Пусть, как и ранее,

 

 

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

 

 

Тогда с точностью до независящих от х множителей

 

 

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

 

(4.64)

 

При этом параметры Dm и s2 существенного значения не имеют.

Решение задачи селекции оказывается возможным даже тогда, когда вообще отсутствуют какие бы то ни было априорные сведения о виде и параметрах распределений f1(х) и f0(х). Постулируется лишь сам факт существования отличий между ними. Если провести ранжировку выборки х‚{х1 ..., xi ..., хn} в порядке возрастания значений xi то при m1>m0 в соответствии с правилом (4.59) наиболее вероятной будет гипотеза Нn, а при m1<m0 — гипотеза Н1. Можно показать, что из двух гипотез Нn и Н1 более вероятна та, для которой измеренное значение признака х дальше отстоит от центра рассеяния остальных элементов выборки. Соответствующее этому случаю решающее правило имеет вид

 

(4.65)

 

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

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

Характер статистических решающих правил при селекции определяет методологию оценки эффективности. Адекватным математическим аппаратом оценки эффективности селекции является теория порядковых статистик [21].

Вычислим вероятность Фn-1(х) того, что все (n— 1) случайных величин с плотностью распределения f0(x) окажутся меньше некоторого значения х¢. Если — функция распределения, то

 

(4.66)

 

Это следует непосредственно из определения функции распределения. Заметим, что Фn-1(х¢) представляет собой функцию распределения наибольшей из (n—1) случайных величин, распределенных по закону f0(x), т. е. функцию распределения так называемой наибольшей порядковой статистики.

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

 

(4.67)

 

Для распределений вида (4.62) в результате вычеслений по формуле (4.67) имеем

 

(4.68)

 

где Г(х) — гамма-функция.

 

Проверить это можно методом математической индукции.

При m0/m1®1 распределения f0(х) и f1(x) сближаются между собой, селекция становится невозможной и Р(n)®1/n. При m1/m0®0 отличия между указанными распределениями становятся существенными Р(n)®1. Эти факты согласуются с интуитивно ожидаемыми результатами.

Для распределений вида (4.61) при n = 2 по формуле (4.67) имеем

 

 

где

 

 

В справедливости последнего результата можно убедиться, рассматривая случайную величину z=y—x=y + (—х), где у и х имеют плотности распределения:

 

 

Тогда распределение величины z является композицией распределений f1(у) и f0(х) и, следовательно, имеет плотность распределения

 

 

Правильное решение по селекции будет принято при условии z>0, т. е.

 

 

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

 

 

откуда Ррасп<Р(2).

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

 

 

где z=y-x;

 

(4.69)

 

композиция распределений f1(y) и jn-1(—x); jn-1 (x)=Фn-1 (х) — плотность распределения наибольшей порядковой статистики в выборке объема (n— 1) из распределения f0(x).

Математическое ожидание `z и дисперсию D{z} величины z рассчитаем по формулам:

 

(4.70)

(4.71)

 

Само распределение g(z) мало отличается от нормального.

В (4.70) и (4.71) mn-1 и S2n-1— математическое ожидание и дисперсия наибольшей порядковой статистики в выборке объема (n— 1) из распределения с плотностью

Значения параметров mn и S2n приведены в табл. 4.1.

 

Таблица 4.1

 

При сделанных допущениях

 

(4.72)

 

Результаты расчетов, проведенных по точной (4.69) и приближенной (4.72) формулам, приведены в табл. 4.2.

 

Таблица 4.2

 

Сопоставление этих результатов показывает, что абсолютная погрешность вычислений по формуле (4.72) не превышает 3 • 10-3Этого вполне достаточно для практических приложений.

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

 

Глава 5 РАБОЧИЙ СЛОВАРЬ ПРИЗНАКОВ СИСТЕМ РАСПОЗНАВАНИЯ ОБЪЕКТОВ И ЯВЛЕНИЙ

 

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

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

 

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

 

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

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

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

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

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

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

 

(5.1)

 

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

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

 

(5.2)

 

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

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

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

 

(5.3)

 

(5.4)

 

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

 

(5.5)

 

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

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

 

(5.6)

 

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

 

(5.7)

 

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

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

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

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

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

 

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

 

(5.8)

 

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

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

 

(5.9)

 

при

 

 

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

 

(5.10)

 

при

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

 

(5.11)

 

при

 

 

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

Метод решения задачи.

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

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

 

(5.12)

 

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

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

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

 

(5.13)

 

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

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

 

(5.14)

 

при

 

 

где

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

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

 

(5.15)

 

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

Если условия связи выполнены, то F(х) = Ф(х), в противном случае второе слагаемое в правой части (5.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. Математическое ожидание квадрата среднеквадратичного расстояния между всеми парами классов

 

(5.16)

 

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

 

(5.17)

 

при

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

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

 

§ 5.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, Рjj= ¥) = 1 и Pj(Cj)<1 для любого конечного значения затрат Сj.

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

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

 

(5.18)

 

где

 

 

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

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

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

 

(5.19)

 

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

 

(5.20)

 

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

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

 

(5.21)

 

 

 

Рис. 5.1

 

Доказательство утверждений, содержащихся в (5.21), фактически приведено в [22]. Введение в рассмотрение скаляра l и вектора m увеличивает количество неизвестных C0j, mr и l до величины Np + n + l. Однако число уравнений равно числу неизвестных, так как для любого r либо mr = 0, либо

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

 

(5.22)

 

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

 

Игровой подход к построению

Рабочего словаря признаков

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

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

Выше были рассмотрены достаточно общие методы выбора совокупности признаков, которые целесообразно и доступно использовать при построении системы… Сравнение апостериорных вероятностей. Пусть задан алфавит классов Ωi,… То же проделаем и с признаком xs, т. е. определим интервалы D1i(xs); D2i(xs)...; Dmi(xs). Вероятность получить…

Глава 6 ВЫЧИСЛИТЕЛЬНЫЕ МЕТОДЫ АЛГЕБРЫ ЛОГИКИ

 

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

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

 

 

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

 

Алгебра логики — не пустое множество элементов, являющееся ее областью, вместе с некоторым заданным набором операций, которые можно совершать над элементами, не выходя за пределы области. Область алгебры логики состоит из множества высказываний — законченных предложений, которые могут иметь одно из двух значений истинности: либо быть истинными, либо быть ложными. Например, высказывание «пять — четное число» — ложное, а высказывание «логика — наука о законах мышления» — истинное. Высказывания обозначаются буквами А, В, С, ..., К, X, Y; А1 А2, ..., В1, В2, ... .

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

Конъюнкция. Операция логического умножения совершается, по крайней мере, над двумя высказываниями, соответствует комбинации этих высказываний с помощью слова «и» и обозначается знаком «×», например А × В читается «А и В». Высказывание А × В истинно тогда и только тогда, когда истинны высказывания А и В одновременно. Например, конъюнкция двух высказываний (самолет — это летательный аппарат) × (прямое попадание мощного снаряда в цель приводит к поражению цели) истинна, тогда как конъюнкция (три — четное число) • (применение танков целесообразно) ложна.

Дизъюнкция. Операция логического сложения совершается, по крайней мере, над двумя высказываниями, соответствует объединению этих высказываний с помощью слова «или» и обозначается знаком «+», например А + В читается «А или B». Высказывание А + В истинно, когда истинно либо только высказывание А, либо только высказывание В, либо истинны высказывания А и В одновременно. Например, дизъюнкция (танки могут остановить наступление пехоты) + (собака — насекомое) истинна. Высказывание А+В ложно тогда и только тогда, когда высказывание А ложно и высказывание В ложно.

Отрицание. Операция отрицания может совершаться над одним высказыванием, обозначается чертой над буквой, например `А, читается «не А». Высказывание `A истинно тогда и только тогда, когда высказывание А ложно *.

* Высказывания — элементы области алгебры логики, и поэтому наряду со словом «высказывание» далее часто будет употребляться термин «элемент».

 

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

*Алгебра логики впервые была исследована Дж. Булем (1815—1864).

 

Рассмотрим две особо важные булевы функции: `А + В и А× В+`А`×В, выражающие определенные связи между элементами А и В.

Импликация (следование). Пусть высказывание `А + В истинно. Тогда в соответствии с определением дизъюнкции и отрицания заключаем, что если А истинно, то В тоже истинно, если В ложно, то А тоже ложно. Однако если В истинно, то А может быть как истинно, так и ложно. Такая зависимость между А и В называется импликацией, записывается в виде А® В и читается «если А, то В» или «из А следует В».

Эквивалентность. Пусть высказывание А×В+`А×`В истинно. Тогда из определения операций над высказываниями следует, что А та. В имеют одинаковые значения истинности, т. е. либо оба истинны, либо оба ложны. Такая зависимость между А и В называется эквивалентностью, записывается в виде А — В и читается «А эквивалентно В». Если А = В, то, какова бы ни была булева функция f(A, U, V, ...), справедливо соотношение f(B, U, V, ...) =f(B, U, V, ...), что можно записать в виде

 

(6.1)

 

Среди всех булевых функций можно выделить функции, остающиеся истинными, безотносительно к тому, какие значения истинности принимают входящие в эти функции элементы, например а также (6.1). Такие функции называют универсально истинными или тавтологиями. Так как все тавтологии не различаются между собой с точки зрения значений истинности, то их обозначают I. Следовательно, можно записать и т. д. Отрицание 1, т. е. `1 — универсально ложный элемент; обозначается 0. Для любых X соотношения — тавтологии, так как не зависят от значения истинности X.

Необходимо отличать тавтологически истинные элементы от функций, которые истинны вследствие сделанных предположений или физических законов. Первые не несут никакой полезной информации, в то время как вторые накладывают определенные связи на входящие в них элементы. Например, если применительно к некоторой проблеме утверждается, что функция `А + В должна рассматриваться как истинная, т. е. `А + В= `1, то, как указывалось, это эквивалентно связи А®В. Аналогичный пример дает соотношение эквивалентности (А•В+`А• `В=`1) = (А = В). В дальнейшем будут рассматриваться другие возможные формы связей.

Основные правила алгебры логики следующие:

 

 

Данные формулы должны рассматриваться как тавтологии. Их справедливость может быть проверена вычислением значений истинности сложных высказываний в левой и правой частях равенства. Некоторые из этих формул могут быть выведены из других формул, например 19 устанавливается с помощью 3, 4, 6, 7, 12, 15 и 17 следующим образом:

 

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

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

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

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

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

Условия независимости. Поскольку каждая булева функция может иметь два значения истинности, n булевых функций могут образовывать 2n комбинаций…  

Булевы уравнения

Решение многих задач, связанных с распознаванием объектов, может быть сведено к нахождению решений булевых алгебраических уравнений с одним (или… Перейдем от элементов X, А, В, С к их изображающим числам. Относительно базиса… Таким образом, рассматриваемое уравнение имеет четыре решения, соответствующие изображающим числам 0000 0001,

Замена переменных

Понятие замены переменных в алгебре логики аналогично понятию замены переменных в обычной алгебре. Если А, В, С, ... — элементарные высказывания и…  

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

В логических системах распознавания классы и признаки объектов рассматриваются как логические переменные. Чтобы подчеркнуть эту особенность, для… Пусть множество объектов подразделено на классы Ω1 ..., Ωm, а для… Предположим, что все сведения априорного характера о классах объектов, выражающие, с одной стороны, связь между…

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

Приложение изложенных в предыдущих параграфах методов построения сокращенного базиса и решения логических задач существенно ограничивается объемом…  

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

В § 7.1 было показано, как с помощью ЭВМ, опираясь на сокращенный базис b´ [А1, А2, ...Ω1, Ω2,...], находить решение специальной… Алгоритм получения произведения двух булевых функций. Пусть требуется найти… 1. Сравним поразрядно колонку a таблицы (f1) с колонкой b таблицы (f2):

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

Маскировка — один из основных методов снижения эффективности разведки противника в общем комплексе мероприятий по противодействию. Решение проблемы… Предположим, что требуется замаскировать объекты классов Ω1 и Ω2…  

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

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

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

Логические алгоритмы распознавания, рассмотренные выше, в ряде случаев не позволяют получить однозначное решение о принадлежности распознаваемого… Пусть множество объектов {w} подразделено на классы Ωi, i=1, ..., m, и… Опыт решения задач распознавания свидетельствует о том, что часто основная информация заключена не в отдельных…

Глава 8 СТРУКТУРНЫЕ МЕТОДЫ РАСПОЗНАВАНИЯ

 

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

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

 

Общая характеристика структурных методов распознавания

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

Основные элементы аппарата структурных методов распознавания

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

Реализация процесса распознавания на основе структурных методов

Для распознавания неизвестного объекта на основе структурных методов необходимо прежде всего найти его непроизводные элементы и отношения между… Для формирования соответствующей грамматики можно воспользоваться либо… Допустим, что имеем дело с двумя классами объектов (Ω1 и Ω2) и объекты, входящие в эти классы, можно…

Постановка задачи оптимизации процесса распознавания

Прежде всего покажем, что с увеличением числа признаков, используемых при распознавании, вероятность правильного распознавания неизвестных объектов… Вероятность получить однозначное решение по одному признаку xj, j=1, ..., N… Допустим, что все признаки независимы между собой. Тогда события а1, а2, ... также будут независимы. Вероятность…

Алгоритм управления процессом распознавания

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

Частные подходы к принятию решений при распознавании

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

Алгебраический подход к задаче распознавания

Выше рассмотрены алгоритмы распознавания: детерминированные алгоритмы, основанные на проведении в признаковом пространстве решающей границы… Наличие различных алгоритмов распознавания поставило вопрос о выборе в каждой… Этап 1. Вычисляется мера близости неизвестного объекта с каждым классом (в логических алгоритмах значения поизнаков…

Глава 10 ЭФФЕКТИВНОСТЬ СИСТЕМ РАСПОЗНАВАНИЯ

 

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

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

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

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

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

 

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

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

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

При построении логических систем распознавания приходится сталкиваться с ситуацией, когда значения истинности элементов А1..., Аn, выражающих… К каждой проектируемой системе распознавания, как правило, предъявляются… Из множества допускаемых данной системой решений j(Ωl, ..., Ωm) практически полезными могут быть лишь…

– Конец работы –

Используемые теги: Общая, характеристика, проблемы, распознавания, объектов, явлений0.092

Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: ОБЩАЯ ХАРАКТЕРИСТИКА ПРОБЛЕМЫ РАСПОЗНАВАНИЯ ОБЪЕКТОВ И ЯВЛЕНИЙ

Что будем делать с полученным материалом:

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

Еще рефераты, курсовые, дипломные работы на эту тему:

Характеристика РЭСИ как объекта теории надежности. Основные показатели безотказности для невосстанавливаемых объектов
При расчетах и анализе надежности широко используются термины «элемент» и «система». Под элементом понимается часть сложного объекта, которая имеет… В соответствии с ГОСТ 27.002-89 надежность трактуется как свойство объекта… Исправное состояние. Состояние объекта, при котором он соответствует всем требованиям нормативно-технической и (или)…

Общая характеристика безопасности проектируемого объекта
На сайте allrefs.net читайте: "Общая характеристика безопасности проектируемого объекта"

Общая характеристика проблемы, распространенность
Аллергия типический патологический процесс точнее это собирательное... АЛЛЕРГИЯ ЭТО КАЧЕСТВЕННО ИЗМЕНЕННАЯ ИМУННАЯ РЕАКЦИЯ ОРГАНИЗМА НА ВОЗДЕЙСТВИЕ ВЕЩЕСТВ АНТИГЕННОЙ ПРИРОДЫ...

Характеристика металлического состояния. Общая характеристика свойств металлов
На основе железа изготавливают не менее 90% всех конструкционных и инструментальных материалов. Металлическое состояние.Металлы в твердом и,… Физические свойства. К физическим свойствам металлов и сплавов относится температура плавления, плотность, температурный коэфициет…

Предмет и задачи дисциплины. Правовое и нормативно- методическое обеспечение классификации объектов недвижимости. Общая классификация объектов недвижимости
Предмет и задачи дисциплины Правовое и нормативно методическое обеспечение классификации объектов недвижимости... Общая классификация объектов недвижимости... Теоретические и методологические основы типологии недвижимости...

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

Анализ внешней среды как начальный этап в формировании стратегии предприятия. Функциональные стратегии: типы и общая характеристика
Слово стратегия произошло от греческого strategos, искусство генерала. Военное происхождение этого термина не должно вызывать удивления.Именно… Цели вырабатываются для осуществления этой миссии.Миссия детализирует статус… После установления своей миссии и целей руководство должно начать диагностический этап процесса стратегического…

Общая характеристика современной транспортной травмы
К транспортным травмам относят механические повреждения, при¬чиняемые частями транспорта, которые отличаются большим конст¬руктивным разнообразием,… В зависимости от вида транспорта, причинившего повреждения, транспортную… Несмотря на то, что автотранспортные происшествия по времени протекают очень быстро, каждый случай автотравмы проходит…

Классификация методов обучения. Общая характеристика методов мотивации и осуществления учебного процесса
Классификация методов обучения Общая характеристика методов мотивации и...

Юриспруденция: общая характеристика, функции, система
Классификация функций государства... Функции государства основные направления деятельности государства по управлению главными сферами социальной жизни и...

0.038
Хотите получать на электронную почту самые свежие новости?
Education Insider Sample
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Реклама
Соответствующий теме материал
  • Похожее
  • По категориям
  • По работам