Разработка и оценки числа шагов алгоритмов решения задач распознавания образов при логико-аксиоматическом подходе

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

Существенной чертой задач искусственного интеллекта является большая размерность как исходных данных, так и математических описаний поставленных задач. В современной научной литературе имеется достаточно мало работ, посвященных оценке числа шагов решения задач искусственного интеллекта, связанных с конкретным выбором средств их решения. Математические работы, как правило, посвящены доказательству сходимости предложенных алгоритмов [2, 29, 36] или доказательству условий применимости рассматриваемого метода решения задач [12, 13]. Работы, посвященные практической реализации имеющихся алгоритмов, решают конкретные задачи, зачастую используя те или иные эвристики, мало применимые к решению другой конкретной задачи [17].

В то же время усилия многих ученых, работающих в области математических основ информатики, посвящены доказательству не только правильности работы алгоритма, решающего поставленную задачу, но и оценок числа шагов его работы [1, 7, 41]. Это особенно актуально для алгоритмов, решающих задачи искусственного интеллекта, прежде всего в связи с огромным объемом информации, которую необходимо обработать на компьютере.

Особое место занимают задачи, относительно которых доказаны их ЫР-полнота или КР-трудность [7, 41, 42]. Широко распространено мнение, что такие задачи не предназначены для их реализации па компьютере с большим объемом исходных данных в силу огромного времени их решения. Выделение подзадач таких задач, имеющих полиномиальные верхние оценки числа шагов решения, — одно из направлений, имеющих целью выделить границы практической применимости создаваемых моделей [19, 21, 43]. Одним из способов выделения таких подзадач является не только доказательство КР-пол ноты или КР-трудности исходной задачи, но и установление достаточно точных верхних оценок числа шагов алгоритмов, решающих исходную задачу.

Неформальное описание задач распознавания. Под задачей распознавания образов в разной литературе зачастую понимают разные задачи. В частности, в [5] к ним относят, например, следующие.

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

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

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

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

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

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

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

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

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

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

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

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

Обзор имеющихся результатов по теме диссертации. Первое, с чем сталкивается теория распознавания образов — это выбор набора признаков, на основании которых будет производиться распознавание. В работе [5] определены четыре класса таких признаков: детерминированные (принимающие конкретные числовые значения) — вероятностные (случайные значения которых распределены по всем классам объектов) — логические (принимающие два значения &bdquo-истина" или &bdquo-ложь") — структурные (являющиеся непроизводными элементами структуры объекта).

В соответствии с тем, па языке каких признаков производится описание объектов, системы распознавания могут быть подразделены на детерминированные, вероятностные, логические, структурные и комбинированные [5]. В работах Ю. И. Журавлева [10, 11, 12, 13] и его учеников рассматриваются алгебраические распознающие системы, представляющие собой комбинацию детерминированных и логических систем распознавания.

В каждом из этих подходов описания классов являются аналогом понятия фрейм, введенного Н. Минским [26].

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

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

Методы построения рабочего набора признаков по известному исходному набору изложены, например, в [2, 5, 29].

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

В теории построения систем распознавания образов наряду с другими широкое распространение получили и логические методы [30, 13, 15]. Рассматриваемые в литературе логические методы описаний классов сводятся к представлению связей между отдельными признаками объекта в виде булевых функций или булевых уравнений. Решение булевых уравнений равносильно доказательству истинности (или выводимости) формул исчисления высказываний, перед которыми стоят кванторы существования по пропозициональным переменным. Методы получения и представления знаний, в частности, в виде продукций, хорошо приспособленных для доказательства целевых условий методом резолюций, рассмотрены, например, в [3].

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

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

Идея существенного использования исчисления предикатов и построения терма (последовательности функций, воздействующих на объект), задающего последовательность действий в задачах планирования движения, использовалась Нильсоном Н. [27], Хантом Э. [37] и многими другими. Однако применение этих идей к решению задач распознавания образов автору диссертации неизвестны.

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

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

В работах [17] рассматривается подход к распознаванию геометрических фигур, образованных конечными множествами точек на плоскости или в пространстве, существенным образом опирающийся на внутреннюю кодировку фигур, инвариантную к афинным преобразованиям. Эта кодировка основана на рассмотрении всех симплексов, образованных точками фигуры и введении меры таких симплексов.

В диссертации аналогом таких инвариантов выступают описания преобразований.

Решение всех задач, рассматриваемых в диссертации, сведено к решению задач доказательства теорем простого подмножества формул исчисления высказываний и исчисления предикатов [16]. Доказательство таких теорем может быть проведено, например, посредством применения метода резолюций [31, 27, 30] (и даже линейных стратегий метода резолюций [23], или в секвенциальных исчислениях высказываний и предикатов [16, 20]. Поскольку метод резолюций и секвенциальные исчисления хорошо приспособлены для их компьютерной реализации, то оценки числа шагов алгоритмов построения вывода в диссертации приводятся именно для этих методов доказательства.

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

В диссертации рассматривается логико-аксиоматический подход к решению задач распознавания образов, основанный на сведении некоторых задач распознавания образов к задачам поиска вывода в логических исчислениях. Термин «логико-аксиоматический метод решения задач распознавания образов» был предложен совместно автором диссертации и A.B. Тимофеевым ещё в 80-ые годы [45] в связи с тем, что описание класса представляет собой формализацию утверждений об объектах, безусловно истинные для каждого объекта из этого класса и, следовательно, могут рассматриваться как аксиомы этого класса. При этом рассматриваются задачи, в которых объекты могут быть описаны с помощью логических формул. При использовании пропозициональных формул такой подход является достаточно представительным частным случаем логико-алгебраического подхода, подробно обоснованного и развитого в работах Ю. И. Журавлева [13]и его учеников .

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

Логико-предметный подход к решению задач распознавания образов представляется удобным также в случаях, когда параметры распознаваемого объекта имеют интервальный характер или описания объекта содержат взаимоисключающие признаки, например, цвет объекта. В первом случае можно ввести предикат, зависящий дополнительно от трех аргументов х, а, Ь, истинный на тех значениях переменной х, для которых, а < х < Ъ. Во втором случае можно рассматривать предикат, дополнительно зависящий от параметра г, являющегося номером соответствующего бинарного признака. Например, если рассматриваемые объекты могут иметь один из девяти цветов (черный, белый и 7 цветов радуги), то для того, чтобы указать, что объект белый, вместо набора значений (0,1,0,0,0,0,0,0,0) достаточно записать р (2).

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

В [45] рассматриваемые в диссертации задачи распознавания образов сведены к задаче проверки выводимости формул описанного ниже вида из заданного множества атомарных формул. В этой работе автору диссертации принадлежит основная идея и детальная проработка подхода, Тимофееву A.B. — общая постановка задачи и научное руководство.

Как уже было сказано, одним из важных направлений в создании алгоритмических моделей решения тех или иных задач является доказательство оценок числа шагов таких алгоритмов. В общей постановке задача проверки истинности (или выполнимости) формул вызывает значительные трудности. Так, например, для исчисления высказываний задача проверки выполнимости формулы в КНФ является МР-полной [7].

Для формул исчисления предикатов различного вида можно получить разрешимые фрагменты. В [52] сформулированы серии задач, для которых доказаны их КР-полнота, в то время как для каждой задачи этой серии имеется полиномиальный разрешающий алгоритм.

В диссертации для решения задач распознавания образов для каждого конкретного описания классов доказаны линейные (от длины записи описания распознаваемого объекта) по времени оценки числа шагов алгоритмов, решающих эти задачи для пропозиционального случая [46, 66]. Рассмотрен разрешимый фрагмент исчисления предикатов, в котором могут быть формализованы задачи распознавания образов. Доказано, что если описания классов являются исходными данными алгоритмов, то задачи распознавания образов с признаками-предикатами являются ЫР-трудными. При этом, так же как и в [52], для каждого конкретного описания классов эти задачи имеют полиномиальный (со степенью полинома, зависящей от длины записи описания классов) алгоритм решения.

В [64] предложены многоуровневые описания классов, при использовании которых в диссертации доказаны условия уменьшения числа шагов работы алгоритмов, решающих рассматриваемые задачи распознавания образов [47, 49, 69, 65]. Многоуровневые описания классов являются также удобным средством анализа составных сложных объектов.

Введение

предикатов различных уровней оказалось полезным при создании искусственных нейронных сетей [48, 67].

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

ЗАКЛЮЧЕНИЕ

.

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

1. Доказаны оценки числа шагов алгоритмов решения задач распознавания:

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

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

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

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

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

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

Предложено применение многоуровневого описания классов к построению искусственных нейронных сетей с логическими нейронами.

Показано, что многоуровневые описания классов обеспечивают естественное распараллеливание вычислений, отличное от классического И/ИЛИ параллелизма.

4. Неполный вывод как средство адаптации распознающей системы к неполной информации и оценки числа шагов его реализации.

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

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

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

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

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

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