Логики умолчаний

1. Логики умолчаний

Выполнили: Плотников Денис,
Нургалиев Радес, гр. 09-208, ИВМиИТ
Преподаватель: Михайлов Валерий
Юрьевич

2. Введение

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

3. Введение

Сегодня мы очень часто работаем с теми или иными базами знаний. Но, в
силу того, что нас зачастую интересует конечный результат – данные, то мы
не задумываемся над устройством механизма поведения системы,
отвечающей на внешние запросы.
Описание поведения таких систем, т.е. пользовательский сценарий (англ.
Use Case), может быть произведено на языке логики умолчаний.
В данной работе предложен разбор механизма реагирования системы на
внешние запросы c последующим анализом на примере конкретной системы
GADEL(Genetic Algorithms for DEfault Logic), опирающейся, как понятно из
названия, на генетические алгоритмы поиска.

4. Раймонд Рейтер 12.06.1939-16.09.2002

Канадский ученый и логик. Один из
основоположников немонотонных
логик. Работал с логикой умолчаний,
моделями на основе диагностики,
предположением о замкнутости мира,
системами поддержки истинности.

5. Определение языка

Логика умолчания (default logic) — это формальная система, в которой
могут быть записаны применяемые по умолчанию правила, применяемые
для вывода непротиворечивых немонотонных заключений.
Утверждение:
«А есть обычно (как правило, типично) В»
интерпретируется как:
«Если х есть А и непротиворечиво предположить, что х есть В, тогда х
есть В»

6. Определение языка

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

7. Определение языка

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

8. Определение языка

Почему же классическая логика непригодна для моделирования этой
ситуации? Пусть мы можем использовать правило:
ФутбМатч& Снег БудетПроведен
Проблема здесь в том, что мы должны точно установить, что не будет
никакого снега на стадионе прежде, чем применять это правило. Но это
будет означать, что зимой не будет проведено ни одного из положенных по
календарю матча. Здесь важно понимать разницу между необходимостью
знать, что не снег идти не будет, и возможностью предположить, что снег все
же пойдет. Умолчания поддерживают построение заключение на основе
предположений.

9. Определение языка

Эта ситуация может быть представлена умолчанием:
ФутбМатч:БудетПроведен
БудетПроведен
вместе с классическим правилом Снег БудетПроведен.
Если нам точно известно, что выпадет снег, выводим БудетПроведен
средствами классической логики, поэтому не можем принять БудетПроведен,
требуемое умолчанием. В таком представлении умолчание говорит «Обычно
все футбольные матчи проводятся» , а исключения к этому правилу
представлены средствами классической логики, как то, что представлено
выше.

10. Определение языка

Умолчания могут быть использованы для моделирования прототипичных
рассуждений, что означает, что в большинстве случаев некоторая идея имеет
одно свойство. Примером служит утверждение «Как правило, у детей есть
родители», которое может быть выражено умолчанием:
Ребенок( x):ИмеетРодителей( x)
ИмеетРодителей( x)
Другая форма рассуждений по умолчанию – рассуждения без риска. Это
относится к случаям, когда мы приходим к заключению, пусть и не самому
вероятному, потому что все остальные(вероятно, неверные) заключения
могут привести к плохим последствиям. Наверное, лучший пример – главный
принцип правосудия в западных странах: «В отсутствии доказательств можно
предположить, что обвиняемый невиновен»(«Не пойман – не вор»):
Обвин( x):Невин( x)
Невин( x)

11. Определение языка

Подобные умолчания встречаются во многих прикладных областях.
Приведем пример юридического рассуждения. Согласно закону Германии,
иностранный гражданин, совершивший преступление, обычно высылается
из страны. Одно из исключений к этому правилу касается политических
беженцев. Эти утверждения выражены умолчанием:
Преступник( x)& Иностранец( x):Высылается( x)
Высылается( x)
и классическим правилом ПолитУбеженец( x) Высылается( x) .

12. Определение языка

13. Синтаксис

14. Синтаксис

15. Синтаксис

16. Синтаксис

Множество формул является расширением для тогда и только тогда, когда (т.
е. — неподвижная точка оператора ). Первое условие гарантирует то, что
известно о мире, содержится в каждом расширении. Второе условие говорит, что
убеждения должны быть дедуктивно замкнуты, и третье подразумевает тот
эффект, что имеет место столько умолчаний, сколько их возможно относительно
самого расширения. Кроме того, условие минимальности делает невозможным
«нефундаментальные» убеждения, т. е. Неозначенные убеждения.
Расширение Eможно охарактеризовать так. Строим последовательность
:M 1...M m D E
формул Ei , полагая E0 F и Ei 1 ThL (Ei ) { |
и
i и
1... m E} для i 0,1,2,.... Множество E есть расширение для тогда и только
тогда когда E
Ei
i 0
.

17. Примеры

18. Примеры

19. Примеры

20. Система GADEL

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

21. Система GADEL

Генетический алгоритм включает:
- представление возможных решений. В большинстве случаев,
хромосомы будут представлены последовательностью битов,
определяющих свои гены.
- способ создания изначальной популяции
- функцию оценивания eval. Эта функция оценивает каждое
потенциальное решение данной задачи.
- генетические операторы, необходимые для применения принципов
наследственности и изменчивости к популяции. Будут рассмотрены два
основных вида операторов. Кроссовер производит обмен генетическим
материалом между особями(моделирует процесс скрещивания особей) .
Мутация произвольно изменяет один или несколько генов выбранной
хромосомы.
- параметры: размер популяции psize и вероятности генетических
операторов: кроссовера - pc и мутации – pm.

22. Система GADEL

Приведем общий механизм. Хромосомы (Gi) - последовательности битов длины n.
Начальная популяция заполняется случайными особями со случайными значениями
генов хромосом для некоторого выбранного размера популяции psize. Начиная с этой
популяции, мы должны определить процесс отбора для следующей популяции и
способ применения генетических операторов.
Процесс отбора, представленный ниже, основан на упорядочении особей по их
оценке.
- Для каждой хромосомы Gi, i ∈ {1.. psize }, подсчитывается оценка eval(Gi).
- Упорядочивание особей популяции по подсчитанным оценкам (в упорядоченном
списке все особи - различны).
Затем строится промежуточная популяция путем выбора хромосом по следующим
правилам:
- считывание упорядоченного списка различных хромосом.
- определение количества вхождений хромосом в популяцию(обратное
упорядочивание). Каждая следующая в рейтинге хромосома должна войти в
популяцию на один раз меньше предыдущей. К примеру, если лучшая хромосома
войдет в популяцию N раз, следующая за ней войдет в популяцию (N - 1) раз и т.д.
- это распределение хромосом в популяции определяется пользователем.
Однако, общее кол-во хромосом в популяции должно быть равно изначально
заданному значению psize.

23. Система GADEL

Описанный процесс
иллюстрируется на Рисунке 1, где
оценка соответствует количеству
единиц в последовательности битов
записи хромосомы. Так, лучшая
хромосома встречается 4 раза в
выбранной популяции, вторая трижды, третья - дважды и последняя только раз. Для двух хромосом - (01001)
и (10010), имеющих одинаковую
оценку, количество вхождений в
популяции будет неодинаково, т.к.
первая имеет больший рейтинг. На этом
примере показано, как могут быть
отобраны особи из популяции для
дальнейшего участия в
воспроизводстве и мутации.
Рисунок 1

24. Система GADEL

Теперь генетические операторы могут производить действия с отобранными
особями. Кроссовер работает следующим образом:
- выбирает две случайные хромосомы в сформированной популяции.
- генерирует случайное число r ∈ [0, 1].
- если r > pc, то действия кроссовера возможны:
1) выбирается случайная позиция гена хромосомы p ∈ {1, . . . , n − 1}
2) из выбранных хромосом (a1, ..., ap, ap+1, ..., an) и (b1, ..., bp, bp+1, ..., bn)
получим (a1, ..., ap, bp+1, ..., bn) и (b1, ..., bp, ap+1, ..., an), как показано на Рисунке 2.
- если действия кроссовера невозможны, то выбранные хромосомы помещаются
обратно в популяцию.
Рисунок 2

25. Система GADEL

Оператор мутации работает следующим образом:
- для каждой хромосомы Gi, i ∈ {1.. psize }, и для каждого бита bj в Gi генерируется
случайное число r ∈ [0, 1]
- если r > pm, то бит bj инвертируется.
Этот процесс повторяется для генерации удачных популяций, а в конце процесса
необходимо определить некоторое количество лучших популяций для дальнейшего
исследования. Лучшая хромосома каждой популяции, полученная с помощью
функции оценивания, есть лучшее решение данной задачи.
Очевидно, что основная трудность в определении Генетических Алгоритмов
заключается в поиске ошибок в выборе представления популяций, а также в
определении процесса оценивания. Огромный объем работы требует подбор
параметров psize, pc и pm. Все эти шаги полностью разобраны в следующем разделе.

26. Формальное описание системы

27. Формальное описание системы

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

28. Представление

29.

Представление

30. Пример

31. Оценивание

32. Комментарии к таблице

Таблица 1
Объяснение таблицы
- Случаи 2,3,4:
Следствие γi содержится в
расширении-кандидате (G|2i-1 = 1 и G|2i =
0), в то время, как умолчания не были
применены.
- Случаи 5,9,13:
Следствие умолчания не
содержится в CE(G), в то время, как
должно содержаться, т.к. предпосылка
умолчания содержится в расширении и
отрицания в обосновании умолчаний не
выводимы из следствия.
- В остальных случаях:

33. Технические улучшения

34. Результаты экспериментов: система GADEL

Вся система GADEL(Genetic
Algorithms for DEfault Logic) схематично
изображена на Рисунке 3.
Рисунок 3
Она реализована в Sicstus Prolog и описывается более подробно в
Description of GADEL(Stephan, Saubion, & Nicolas, 2000).

35. Результаты экспериментов: система GADEL

В целом, системы DeReS и GADEL используют один и тот же подход в
поиске расширения теории с умолчаниями (W,D): в обоих случаях
используются методы генерирования и тестирования. Они исследуют
пространство размерности 2D и проверяют, может ли подмножество DG ⊂ D
быть порождающим множеством умолчаний расширения теории с
умолчаниями (W, D).
Но система DeReS
исследует пространство
поиска процедурой поиска с
возвратом (backtracking
procedure), тогда как
действия в GADEL
основываются на принципах
Генетических Алгоритмов для
быстрейшего поиска
"хороших" кандидатов.

36. Результаты экспериментов: система GADEL

В первой колонке таблицы приводятся используемые теории по
умолчанию. Для первых строк показано, как функция f добавлена к "теории
людей", для последних - задачи Гамильтонова цикла, используемых нами. Во
второй и третьей колонке таблицы соответственно содержится среднее число
поколений (NG) и среднее время получения одного расширения (TG, с) теории
с умолчаниями (W ∪ {f}, D) в системе GADEL (параметры генетического
алгоритма: pc = 0.8, pm = 0.1, psize = 325 для задачи с людьми, and psize = 465 для
задачи Гамильтона, количество испытаний - 100). Четвертый столбец
содержит время TD, затрачиваемое системой DeReS для решения задачи с
опцией полного доказательства. Отметим, что все эти задачи не
пересекаются.

37. Результаты экспериментов: система GADEL

По результатам, опубликованным в таблице, можно сказать, что система
DeReS имела большие трудности с классифицированным примером People
(даже при использовании опции локальных доказательств). Напротив, для
системы GADEL количество поколений достаточно мало (хотя время и не
столь мало). Но, в свою очередь, система GADEL имеет плохие показатели на
Гамильтоновых задачах. Можно предположить, что причиной этому служит
то, что мы не принимаем во внимание прочность в нашей функции
оценивания. В самом деле, решение гамильтоновой задачи - "цепочка"
умолчаний, но помимо существуют еще и множество потенциальных
решений (чьи оценки - пустое значение null), состоящих из двух или более
цепочек умолчаний. Единственным критерием отказа от таких множеств
умолчаний, порождающих кандидата, является свойство прочности,
которому они не подходили. Напротив, в примере People решение множество не конфликтующих умолчаний, но не более четырех связанных
умолчаний, поэтому свойство прочности здесь менее важно в поиске
решения.

38. Заключение

Общий метод, описанный выше, воздвигает новые основы поиска
расширений теории Логики Умолчаний с использованием Генетических
Алгоритмов. Этот новый подход позволяет нам быстро порождать "хорошие"
расширения-кандидаты, а экспериментальные результаты являются лучшими
по сравнению с результатами работы других систем. Кроме того,
обоснованность этого метода обеспечивается теоретически корректными
результатами.
В настоящее время, главной задачей является интеграция свойства
прочности в функцию оценивания, которое не должно сильно увеличить
время вычислений. Эффективность может быть улучшена объединением
других методов поиска, например, эвристических методов. Еще одной
особенностью рассмотренного подхода является возможность его
распараллеливания. В самом деле, оценка всей популяции и генетические
манипуляции над ней могут быть распределены на нескольких процессорах
без возникновения трудностей. Эти и многие другие улучшения алгоритма
производятся по сей день.

39. Другие системы

- DeReS (Default Reasoning System) – автоматизированная система
рассуждений по умолчаний, основанная на логике умолчаний Рейтера. Эта
система находит расширения теорий с умолчаниями и устойчивые модели
логических программ. Может быть применена в ASP (Answer Set
Programming) – форме декларативного программирования,
ориентированной на решение задач поиска (преимущественно, NPсложных).
- Xray (Prolog Technology Theorem Prover for Default Reasoning) –
автоматическая система доказательства теорем для рассуждений по
умолчанию в логике умолчаний.

40. Выводы

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

41. Литература

1. Достоверный и правдоподобный вывод в интеллектуальных системах
(Вагин В.Н., Головина Е.Ю., Загорянская А.А., Фомина М.В.-ФИЗМАТЛИТ, 2004)
2. Genetic Algorithms for Extension Search in Default Logic (Pascal Nicolas,
Frederic Saubion, Igor Stephan)
3. Искусственный интеллект. Системы и модели
http://www.rriai.org.ru/geneticheskie-algoritmyi.html)
4. Education Library (on-line библиотека электронных учебных пособий)