Метод модификации посылок

В статье предложен метод модификации посылок, позволяющий придавать системам логического вывода свойст-во адаптивности. Рассмотрен пример системы логического вывода для распознавания символов на основе метода модификации посылок. Метод является перспективным для ряда приложений, таких как системы распознавания образов, системы управления и др.
Интеллектуальные системы получают в настоящее время широкое распространение. Приведем некоторые, самые распространенные виды таких систем [1]:
 экспертные системы, ставшие за последние двадцать лет необходимым инстру-ментом во многих сферах интеллектуальной деятельности. В качестве общеизве-стного примера можно привести системы диагностики неисправностей компьюте-ра, входящие в состав операционных систем Windows;
 системы управления различными устройствами, алгоритм работы которых можно описать терминами логического следования. Например, правило для комнатного кондиционера: «Если температура воздуха ниже 200С, то включить обогрев».
 системы поддержки принятия решений, без которых не обходятся современные менеджеры и руководители. Примером такой системы может служить крайне ак-туальная для Кировской области система поддержки принятия решений по управ-лению промышленной безопасностью химических производств;
 интеллектуальные базы данных, отличающиеся от традиционных возможностью обобщения фактов и выработки знаний, изначально не заложенных. Например, ин-теллектуальная база данных магазина вырабатывает правила, отражающие зависи-мость покупательского спроса от некоторых факторов («Если йогурт произведен менее одной недели назад и цена менее 7 рублей, то спрос велик»);
 наконец, системы распознавания образов. Одна из областей применения таких систем – это распознавание текстовой информации. Самый известный в России пример подобной системы – программа FineReader фирмы ABBYY.
Лучшим подтверждением успешности интеллектуальных систем может служить тот факт, что многие подобные системы перешли в разряд повседневных программ.
Но, несмотря на имеющиеся успехи, остаются и проблемы в разработке интеллектуаль-ных систем. В частности, если система претендует на «интеллектуальность», то она должна обладать «гибкостью мышления» или свойством адаптивности базы знаний. Под адаптивностью понимается возможность модификации структуры правил под влиянием вновь полученных знаний.
Большинство современных систем логического вывода, применяемых в интеллектуаль-ных программах, позволяют модифицировать (т. е. добавлять и удалять правила) свою базу знаний только в ручном режиме. Пользователь может вносить новые правила и уда-лять старые, при этом система осуществляет только контроль непротиворечивости ин-формации. Никак не учитывается существующая информация. Возможны ситуации, ко-гда вместо добавления пяти новых правил без учета уже существующих, требуется доба-вить всего одно, которое дополняет имеющуюся информацию.
Таким образом, актуальной задачей при разработке систем логического вывода является автоматическая модификация правил (посылок) средствами самой системы. Пользова-тель при этом не изменяет базу знаний, а лишь предлагает системе новую информацию.
Перед изложением предлагаемого метода модификации, рассмотрим основные виды ло-гического вывода.
Основные виды логического вывода
Из классической логики известно, что существует три вида логического вывода [2]: де-дукция, индукция и абдукция. Традиционно, разница между этими видами рассматрива-ется на простом примере.
Пусть имеются следующие предложения:
1) «Если Х является студентом пятого курса факультета информатики, то Х – хоро-ший программист». Это общее правило, действительное для любого Х.
2) «Преображенский является студентом пятого курса факультета информатики». Данное предложение является частным случаем или фактом.
3) «Преображенский – хороший программист». В примере это предложение играет роль заключения или цели.
Допустим, есть уверенность в истинности правила 1 и известен факт 2. Тогда с помощью логического вывода, называемого дедуктивным, можно вывести заключение 3. То есть дедукция – это вывод заключения из общих правил и частных фактов.
Теперь, предположим, что известны только два факта 2 и 3. Тогда по индукции можно предположить, что истинно общее правило 1. То есть индукция – это получение общих правил или закономерностей из известных фактов. Индукция, в отличие от дедукции, не является строгим правилом вывода – на основании двух фактов можно лишь предполо-жить, что любой студент пятикурсник факультета информатики является хорошим про-граммистом. Чтобы говорить об этом с уверенностью, следует проверить всех пятикурс-ников факультета на знание программирования.
Третий вид логического вывода – абдукция – заключается в том, что при наличии общего правила 1 и заключения 3, можно вывести факт 2. Как и в случае с индукцией, абдукция позволяет только выдвинуть обоснованное предположение – объяснение заключения. Ведь если Преображенский является хорошим программистом, то вовсе необязательно он студент пятого курса. Хотя при наличии правила 1, такое объяснение его таланта вполне возможно.
Важно отметить, что традиционное понимание абдукции, как вывода исключительно фактов, является ограниченным. Предлагаемый метод модификации посылок основыва-ется на расширенном понимании абдукции, предложенном в [3]. В указанной моногра-фии абдуктивный вывод позволяет находить не только факты объяснения заключения, но и порождать частные правила, недостающие для успешного дедуктивного вывода.
Постановка задачи и структура метода
Задача модификации посылок формулируется следующим образом.
Задано исходное множество посылок M и множество выводимых заключений m. Мно-жество m состоит из двух подмножеств – подмножества mp (positive) заключений, кото-рые должны выводиться из посылок и подмножества mn (negative) заключений, которые не должны выводиться из посылок. Требуется модифицировать исходное множество по-сылок M таким образом, чтобы заключения из обоих подмножеств mp и mn удовлетворя-ли заданным условиям выводимости.
Следует отметить, что в такой постановке задача модификации посылок раньше не ста-вилась. В традиционной абдукции требуется находить недостающие звенья цепочки вы-вода для того, чтобы заключение выводилось из исходных посылок,
В рассматриваемом методе модификации посылок применяется два вида логического вывода – дедуктивный и абдуктивный. Они реализуются в четырех методах, показанных на рис. 1.

Рис. 1. Методы, применяемые для модификации посылок
Метод модификации посылок является методом верхнего уровня и опирается на резуль-таты работы четырех методов нижнего уровня.
Каждый метод нижнего уровня решает определенную задачу. Метод дедуктивного вы-вода позволяет установить, выводится ли заданное заключение из набора исходных по-сылок. Метод дедуктивного вывода с поиском всех решений находит все возможные пу-ти вывода заключения из исходных посылок. Метод удаления посылок на основе дедук-тивного вывода проверяет, выводится ли заключение из множества исходных правил, и если выводится, то удаляет некоторые посылки так, чтобы заключение перестало быть выводимым. Метод добавления посылок на основе абдукции решает обратную задачу. В этом методе для заключения, которое не выводится, во множество исходных правил до-бавляются такие правила, чтобы заключение выводилось.
Модификация посылок
В методе модификации посылок можно выделить пять шагов.
На первом шаге модификации посылок все заключения, принадлежащие множеству m, с помощью проверочного дедуктивного вывода делятся на четыре класса:
1) p/p – логический вывод успешен / должен быть успешен;
2) n/p – логический вывод неудачен / должен быть успешен;
3) p/n – логический вывод успешен / должен быть неудачен;
4) n/n – логический вывод неудачен / должен быть неудачен.
Вводится также счетчик числа итераций h, который на первом шаге принимает единич-ное значение (h=1).
На втором шаге находятся три множества посылок, соответствующие классам p/p, n/p, p/n:
• с помощью метода дедуктивного вывода с поиском всех решений находится мно-жество Mpp исходных посылок, которые участвуют в выводе заключений класса p/p. Это множество нельзя удалять;
• для класса n/p генерируется множество посылок Mnp, при добавлении которых за-ключения данного класса становятся выводимыми. Генерация осуществляется ме-тодом добавления посылок на основе абдукции;
• метод удаления посылок на основе дедуктивного вывода применяется для нахож-дения множества правил Mpn, при удалении которых из множества исходных по-сылок вывод заключений класса p/n заканчивается неудачно.
Найденные множества можно представить следующим образом (рис. 2).

Рис. 2. Множества посылок для классов p/p, p/n, n/p.
На третьем шаге находится множество посылок Mpn–Mpp. Это множество таких правил, которые можно удалить без влияния на класс p/p. Посылки, входящие в найденную раз-ность множеств, удаляются из множества М исходных посылок, а соответствующие за-ключения из класса p/n переходят в класс n/n. Остальные дизъюнкты остаются в классе p/n до следующего цикла или до окончания решения – на текущем шаге их удаление вступает в противоречие с требованием выводимости заключений класса p/p.
На четвертом шаге с помощью проверочного дедуктивного вывода определяются по-сылки из множества Mnp, которые можно включить во множество исходных посылок без влияния на отсутствие выводимости заключений класса n/n. Если такие посылки найде-ны, то они добавляются во множество М исходных посылок, а соответствующие заклю-чения из класса n/p переходят в класс p/p. Остальные заключения остаются в классе n/p до следующего цикла или до окончания решения – на текущем шаге добавление посылок из множества Mnp вступает в противоречие с требованием отсутствия выводимости за-ключений класса n/n.
На пятом шаге счетчик числа итераций h увеличивается на единицу. Проверяется, име-ются ли заключения в классах p/n и n/p и меньше ли счетчик заданного максимального значения: hТаким образом, метод не гарантирует полный положительный результат, т. е. перевод всех заключений из класса p/n в класс n/n и из класса n/p в класс p/p, но позволяет мак-симально к нему приблизиться. Кроме того, наличие максимального числа итераций Hmax предотвращает зацикливание.
Пример модификации посылок
В качестве примера модификации посылок рассмотрим часть системы распознавания символов. На вход такой системы подается оцифрованное изображение символа (напри-мер, графический файл). В процессе распознавания символ проходит процедуру скелети-зации (выделения контура толщиной в один пиксель). Далее производится обход полу-ченного контура с целью получения геометрических характеристик символа. На послед-нем этапе распознавания геометрические характеристики входного символа сравнивают-ся с эталонными и происходит классификация символа, т. е. собственно определение, ка-кой это символ. Если первые из названных этапов являются достаточно исследованными и традиционными, то выбор методов классификации символов меняется от системы к системе и часто является определяющим для эффективности распознавания.
В рассматриваемой системе в качестве признаков, на основе которых осуществляется классификация, выбран набор импликативных правил, а метод классификации основан на логическом выводе. В такой системе, если ставится задача введение адаптивности (настройки на меняющийся вид символов), целесообразно применение метода модифи-кации посылок.
Предположим, что осуществляется распознавание печатных цифр. Цифры имеют сле-дующий вид (рис. 3).

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

Рис. 4. Обозначение линий в символах
Кроме того, выделим ряд часто встречающихся комбинаций линий и введем для них специальные обозначения (рис. 5).

Рис. 5. Часто встречающиеся комбинации линий
При использовании таких обозначений, описание цифры «1» будет выглядеть следую-щим образом:
BC→Y
YH→«1»
А для распознавания цифры «9» имеются следующие правила:
BC→Y
AGD→Z
YZF→«9»
Распознавание символа «9» происходит следующим образом. На вход системы подается графическая форма цифры. Она преобразуется в набор фактов динамической базы дан-ных системы. Например, для «9» такими фактами будут литералы: A, B, C, D, F, G. Затем производится проверочный логический вывод для всех символов, которые система в со-стоянии распознать. Проверяемые заключения имеют следующий вид:
ABCDFG→«0»
ABCDFG→«1»
ABCDFG→«2»
…
ABCDFG→«9»
Если какой либо вывод заканчивается успешно, это говорит о том, что система распозна-ла соответствующую цифру.
Допустим, в ходе работы системы распознавания выяснилось, что эталонную графиче-скую форму цифры «9» следует изменить (рис. 6.).

Рис. 6. Изменение графической формы цифры «9»
Тогда на вход модуля, реализующего метод модификации посылок, подаются следую-щие заключения:
ABCDFG→«9» – вывод данного заключения должен заканчиваться неудачно (класс p/n).
ABCFG→«9» – вывод данного заключения должен заканчиваться успешно (класс n/p).
Модуль модифицирует множество исходных посылок:
BC→Y
AGD→Z
YZF→«9».
Произойдет удаление посылки AGD→Z, вследствие чего нарушится выводимость первого заключения (оно перейдет в класс n/n), и добавление посылки AG→Z, в ре-зультате второе заключение будет выводиться (перейдет в класс p/p). Множество исход-ных посылок преобразуется к виду:
BC→Y
AG→Z
YZF→«9».
Таким образом, система автоматически настроила свою базу правил на новую информа-цию.
Заключение
В отличие от известных методов логического вывода в методе модификации посылок решается задача обеспечения выводимости одной группы заключений при одновремен-ном обеспечении отсутствия выводимости у другой группы заключений. В результате появляется возможность автоматической модификации базы знаний (посылок) средства-ми интеллектуальной системы в процессе ее работы.
Достоинством метода модификации посылок является возможность автоматического до-бавления и удаления посылок с учетом существующей в базе знаний информации. Сис-тема логического вывода на основе этого метода способна взять на себя работу по на-стройке базы знаний на требуемый результат.
Интеллектуальные системы, использующие метод модификации посылок, могут приме-няться в тех областях, где изначально сформированная база знаний претерпевает изме-нения в ходе работы. В частности, интеллектуальные системы, примеры которых приве-дены во введении, нуждаются в модификации базы знаний по мере поступления новой информации, следовательно, в таких системах возможно применение предложенного ме-тода.
Примечания
1. Люгер, Дж.Ф. Искусственный интеллект: стратегии и методы решения сложных проблем [Текст] / Дж.Ф. Люгер. – М.: Изд. дом «Вильямс», 2003. – 864 с.
2. Вагин, В.Н. Достоверный и правдоподобный вывод в интеллектуальных системах [Текст] / В. Н. Вагин, Е.Ю. Головина, А.А. Загорянская, М.В. Фомина. – М.: Физматлит, 2004. – 520 с.
3. Страбыкин, Д.А. Логический вывод в системах обработки знаний [Текст] / Д. А. Страбыкин; под ред. Д. В. Пузанкова; СПбГЭТУ. – СПб., 1998. – 164 с.

Сыграйте покер онлайн и поймайте удачу

Ссуды под залог машин - выгодно и удобно

Курсы имиджмейкеров для тех, кто хочет знать толк в стиле