МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РЕСПУБЛИКИ КАЗАХСТАН ВОСТОЧНО-КАЗАХСТАНСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ им. С. АМАНЖОЛОВА Сафонкина С.А. лекция по дисциплине Основы искусственного интеллекта ПРАВИЛА. УНИФИКАЦИЯ НА ПРОЛОГЕ Регистрационный номер: МП Рекомендовано: МСФ и МОУ г. Усть-Каменогорск, 2010

Основы искусственного интеллекта

ПРАВИЛА.УНИФИКАЦИЯ НА ПРОЛОГЕ лекция ТЕМА:

Аннотация Работа над содержанием лекции позволит методически грамотно, профессионально изучить тему «Правила. Унификация на Прологе» в курсе «Основы искусственного интеллекта»

Сафонкина Светлана Алексеевна, старший преподаватель кафедры «Математического моделирования и информационных технологий»

ПЛАН ЛЕКЦИИ ПЛАН ЛЕКЦИИ Классификация языков программирования ПРАВИЛА на ПРОЛОГЕ УНИФИКАЦИЯ Применение правил и унификации

Логическое программирование язык программирования Prolog (Programming in logic) Языки программирования Алгоритмические (процедурные) языки (Fortran, Pascal, C, …) Декларативные (неалгоритмические) языки Языки логического программирования (Prolog, …) Языки функционального программирования (Lisp, …)

Области применения декларативных языков –Создание систем искусственного интеллекта –Разработка экспертных систем и оболочек экспертных систем –Создание систем помощи принятия решений –Разработка систем обработки естественного языка –Построение планов действий роботов ОБЛАСТИ ПРИМЕНЕНИЯ

Visual Prolog 7.2 Разработкой языка занимается фирма PDC Prolog Development Center Версии Prologа –Turbo Prolog –PDC Prolog –Visual Prolog СОВРЕМЕННОЕ СОСТОЯНИЕ

Особенности языка –Описание проблемы и правил ее решения –Нахождение всех возможных решений с помощью механизма поиска с возвратом (backtracking) –Простой синтаксис ЯЗЫК ПРОГРАММИРОВАНИЯ ПРОЛОГ

ПРЕДЛОЖЕНИЕ (clause) Факт (fact) Правило (rule) Вопрос (goal) Head. Head : - body. ? - body. ?-sister(pat, pat). mother(X, Y):-parent(X, Y), female(X). male(tom). СТРУКТУРА ПРОЛОГ - ПРОГРАММЫ

ПРАВИЛА на ПРОЛОГЕ «Анне нравятся все люди»Пример: «Анне нравятся все люди» База данных уже содержит список людей: человек(sasha). человек(masha). человек(glasha). человек(kostja). человек(denis). человек(timur). Можно записать для каждого человека отдельный факт: нравится(anna, sasha). нравится(anna, masha). нравится(anna, glasha). нравится(anna, kostja). нравится(anna, denis). нравится(anna, timur). А если упоминается несколько сот человек?А если упоминается несколько сот человек?

Определение правила и примеры использования Другой способ выразить факт, что «Анне нравятся все люди », – это сказать «Анне нравится любой объект, если этот объект является человеком». Факт представлен в форме правила.

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

Пример: Человек пользуется зонтом, если идет дождь. Сократ может ошибаться, если Сократ - человек.

Правила используются также для выражения определений Пример: Х является сестрой У, если: Х является женщиной и Х и У имеют одних и тех же родителей.

Пример: Х бабушка У, если Х мама мамы У. Х бабушка У, если Х мама папы У.

Каждое вхождение переменной в правило обозначает один и тот же объект Правило – это некоторое общее утверждение об объектах и об отношениях между ними.

Запись правила на Прологе:Запись правила на Прологе: человек(sasha). человек(masha). человек(glasha). человек(kostja). человек(denis). человек(timur). нравится(anna, sasha). нравится(anna, masha). нравится(anna, glasha). нравится(anna, kostja). нравится(anna, denis). нравится(anna, timur). нравится( anna, X ) :- человек ( X )нравится( anna, X ) :- человек ( X )

Определение ПРАВИЛА на ПРОЛОГЕ,Xнравится(anna,X):-человек (X) Правило - это утверждение вида: B1, B2,...,BnA :- B1, B2,...,Bn где A - заголовок правила, B1, B2,...,Bn - тело правила.

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

Пример программы: Анне нравятся все однокурсники Анне нравятся все студенты группы «ИС» В виде правила:В виде правила: Анне нравятся все люди, студенты группы «ИС»Анне нравятся все люди, если они студенты группы «ИС» Вопрос: Кто нравится Анне?

clauses человек (sasha). человек (masha). человек (glasha). человек (kostja). человек (denis). студент (glasha,is). студент (denis,is). студент(kostjа,at). человек (X),student(X,is). нравится(anna,X):- человек (X),student(X,is).

Унификация

Основная операция на ПРОЛОГЕ – это унификация (отождествление) и конкретизация переменных во время доказательства целевого утверждения

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

Пример: Заданы факты Сократ человек. Все люди способны ошибаться. Перепишем второе утверждение в виде правила: Если объект человек, то объект способен ошибаться

На Прологе: человек(сократ). ошибается(Х):-человек(Х) Вопрос: ?ошибается(сократ)

ошибается (сократ) ошибается (Х) :- человек (Х) Х = сократ человек (Х) человек (сократ) YES Составной терм унифицируется с другим составным термом, если их имена и количество аргументов совпадает

Унификация Пролог пытается сопоставить термы при доказательстве или согласовании целевого утверждения

ПРОЦЕДУРА ВЫЧИСЛЕНИЯ ПРОЦЕДУРА ВЫЧИСЛЕНИЯ СПИСОК ЦЕЛЕЙ ПРОГРАММА КОНКРЕТИЗАЦИЯ ПЕРЕМЕННЫХ ПРИЗНАК : УСПЕХ, НЕУДАЧА

Сопоставляются два терма – структура данных, объединенная одним именем ТЕРМ 1 ТЕРМ 2 НЕУДАЧА УДАЧА КОНКРЕТИЗАЦИЯ СОПОСТАВЛЕНИЕ

УНИФИКАЦИЯ УНИФИКАЦИЯ - (отождествление) - механизм сопоставления целевого предиката с базой данных и конкретизации (сопоставления) переменных.

ПРАВИЛА КОНКРЕТИЗАЦИИ (СОПОСТАВЛЕНИЯ) ТЕРМОВ при согласовании целей: Атомы и числа 1) Атомы и числа могут быть унифицированы только сами с собой.

ПРАВИЛА КОНКРЕТИЗАЦИИ (СОПОСТАВЛЕНИЯ) ТЕРМОВ при согласовании целей: Свободные переменные 2) Свободные переменные могут быть унифицированы с любым термом.

ПРАВИЛА КОНКРЕТИЗАЦИИ (СОПОСТАВЛЕНИЯ) ТЕРМОВ при согласовании целей: Структурный терм одинаковые функторыравное число компонент. 3 ) Структурный терм может быть унифицирован с другим структурным термом, если оба они имеют одинаковые функторы и равное число компонент.

ПРАВИЛА КОНКРЕТИЗАЦИИ (СОПОСТАВЛЕНИЯ) ТЕРМОВ при согласовании целей: Предикат - 4)Предикат - частный случай структурного терма. Посимвольно сравнивается имя предиката и если имя совпадает, то сравнивается арность. Затем идет процесс сопоставления переменных конкретным объектам

Предложения трех видов: факты, правила, запросы. Все предложения строятся из термов

ТЕРМЫ ПЕРЕМЕННЫЕ ПРОСТЫЕ КОНСТАНТЫ АТОМЫ ЧИСЛА СТРУКТУРЫ

Применение правила и унификации. Конкретный пример

Пример программы: clauses человек (sasha). человек (masha). человек (glasha). человек (kostja). человек (denis). студент (glasha, is). студент (denis, is). студент (kostjа, at). нравится(anna, X):- человек (X),student(X,is). ? нравится (anna, X)

Алгоритм работы машины вывода языка Пролог

Поиск с возвратом (backtracking) Рекурсия Вход

PREDICATES tens (string) ones (string) start CLAUSES tens («Двадцать»). tens («Тридцать»). ones («два»). ones («три»). start :- tens (X), ones (Y), write (X, « », Y), nl, fail. GOAL start. Решение Двадцать два Двадцать три Тридцать два Тридцать три

Нахождение значения факториала n! = 1 * 2 * 3 * … * (n – 1) * n 0! = 1 Рекурсивная формула для расчета факториала n! = (n – 1)! * n

PREDICATES factorial (integer, real) CLAUSES factorial (0, 1). factorial (N, FactN) :- M = N – 1, factorial (M, FactM), FactN = FactM*N. GOAL factorial (3, FactN), write («FactN=», FactN).

Списки [1, 2, 3] Деревья (бинарные, упорядоченные)

Предложение, удовлетворяющее цели найдено?

Доказательство цели Для доказательства некоторой цели – предложения просматриваются в том порядке, в каком они появляются в тексте программы.

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

Цель считается доказанной, если с помощью соответствующих фактов доказаны все подцели

nravitsa (anna, x) chelovek (sasha) student (sasha, is) возврат chelovek (masha) student (masha, is) возврат chelovek (glasha) student (glasha, is) успех chelovek (kostja) student (kostja, is) возврат chelovek (denis) student (denis, is) успех

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

Для выполнения цели nravitsa(anna,X) должны быть удовлетворены две подцели: chelovek(X) и student(X,is).

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

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

Для выполнения цели nravitsa(anna,X) должны быть удовлетворены две подцели: chelovek(X) и student(X,is). Чтобы проследить процесс работы Пролог -системы при поиске ответа на наш вопрос, включаем трассировку, записав в начале программ директиву компилятору trace. В окне редактирования курсор указывает подцель, которая выполняется на данном шаге. В окне трассировки отображается дополнительная информация.

Первая подцель унифицируется с первым предложением. При этом переменная Х конкретизируется именем «Саша»

В окне трассировки в этот момент результат вычисления текущей подцели (chelovek(sasha)), выводящийся после слова Return, сопровождается звездочкой (*), которая показывает, что у подцели есть альтернативные решения. Это то место, указатель на которое Пролог заносит в стек точек возврата для возможного последующего возвращения.

Затем делается попытка удовлетворить вторую подцель student(sasha,is).

Затем делается попытка удовлетворить вторую подцель student(sasha,is). Попытка унифицировать эту подцель с одним из фактов, имеющих отношение к предикату student, оказывается неудачной.

78 Цель Цель основная характеристика системы ИИ. Система искусственного интеллекта (интеллектуальная программа) отличается от традиционных программ свойством целеустремленности.

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

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

domains st=string predicates chelovek(st) student(st,st) nravitsa(st,st) clauses chelovek(sasha). chelovek(masha). chelovek(glasha). chelovek(kostja). chelovek(denis). student(glasha,is). student(denis,is). student(kostj,at). nravitsa(anna,X):-chelovek(X),student(X,is). goal nravitsa(anna,X),write("imena odnokursnikov-",X),nl, fail

ЛИТЕРАТУРА Клоксин У., Меллиш К. Программирование на языке Пролог : Пер. с англ. -М.: Мир,. С Братко И. Программирование на языке Пролог для искусственного интеллекта/Пер. с англ. - М.: Мир. Стерлинг Л., Шапиро Э. Искусство программирования на языке Пролог. /Пер. с англ. - М.: Мир.

Учебники

Учебники:

Интернет

Спасибо за внимание!

Глоссарий Информационный ресурс часть имеющихся в обществе знаний, которая отчуждена от своих создателей и материализована в виде документов, компьютерных баз данных и знаний, алгоритмов и программ, произведений науки, искусства, т. е. знаний, подготовленных для использования без участия автора Искусственный интеллект научное направление, в рамках которого ставятся и решаются задачи технического или программного моделирования тех видов человеческой деятельности, которые традиционно считаются интеллектуальными Искусственный интеллект часть информатики, занимающаяся разработкой методов решения задач, для которых не удается разработать фор-мальных алгоритмов Китайская комната эксперимент, описанный Джоном Сёрлем, в котором критикуется возможность моделирования человеческого понимания естественного языка, в частности является критикой теста Тьюринга. Суть эксперимента заключается в следующем. Человека, непонимающего китайский язык, поместили в комнату с корзинками полными китайских иероглифов. Ему также дается учебник на его родном языке, в котором приводятся правила сочетания символов китайского языка, причём правила эти можно применять, зная лишь форму символов, понимать значение символов совсем необязательно. Например, правила могут гласить: «Возьмите такой-то иероглиф из корзинки номер один и поместите его рядом с таким-то иероглифом из корзинки номер два». Находящиеся за дверью комнаты люди, понимающие китайский язык, передают в комнату наборы символов, на которые человек в ответ манипулируя

Глоссарий символами согласно правилам передает обратно другие наборы символов. В данном случае книга правил есть не что иное, как «компьютерная программа». Люди, написавшие её, - «программисты», а человек в комнате играет роль «компьютера». Корзинки, наполненные символами, - это «база данных»; наборы символов, передаваемых в комнату, это «вопросы», а наборы, выходящие из комнаты, это «ответы». Таким образом, «компьютер» выдержит тест Тьюринга на понимание китайского языка, но на самом деле он не знает ни слова по-китайски. К тому же он никак не может научиться этому языку в рассматриваемой системе, поскольку не существует никакого способа, с помощью которого он мог бы узнать смысл хотя бы одного символа. Подобно компьютеру, он манипулируя символами, но не может придать им какого бы то ни было смысла Классификация система группировки множества объектов, составленная на основе учета общих признаков этих объектов и закономерных связей между ними Кластер группа схожих между собой объектов. Сходство основано на общих признаках и закономерных связях между объектами Кластерный анализ совокупность методов, позволяющих классифицировать многомерные наблюдения, каждое из которых описывается набором исходных переменных x1, x2, …, xm. Кластерный анализ приводит к разбиению на группы с учетом всех группировочных признаков одновременно Комплекс средств автоматизации совокупность технического, программного и информационного видов обеспечения автоматизированной системы управления, разрабатываемая как продукция промышленного назначения

Хронология В 1971 году было предсказано создание основной части мозга искусственного интеллекта – памяти. Это произошло после того, как Леон Чуа обнаружил разрыв в возможностях электрических компонент. Первым шагом к созданию искусственной памяти – стало создание мемристора (от англ. «memory» - память и «resistor» - электрическое сопротивление) который был сделан из диоксида титана в 2008 году Стенли Уильямсоном из Hewlett-Packard Labs. Мемристор – это устройство имеющее память и противостоящее прохождению тока. Он имитирует переходы между нейронами головного мозга. Поведение мемристора может быть самым различным, так как его сопротивление зависит от последнего пережитого напряжения.

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

Хронология Компания IBM всерьез планирует закончить разработку искусственного интеллекта к 2029 году. Проект получил название Blue Brain Project. В настоящее время ученые с помощью суперкомпьютера работают над конструированием искусственной коры головного мозга, способы хранения и обработки информации в которой будут такие же, как и в живом аналоге. При удачном исходе проекта Blue Brain Project разработанные искусственные имплантаты смогут быть вживлены в живой мозг, и человек сможет получать доступ как к естественной, так и искусственной памяти. Одновременно с этим ученые планируют создание и автономного от людей искусственного интеллекта. Но перед тем как все это станет возможным, требуется решить целую череду сложных инженерных задач.

Для исторического момента, когда будет изобретен искусственный интеллект, превосходящий по своим возможностям человеческий, ученые уже придумали специальный термин – «точка сингулярности». Пока неясно когда этот момент наступит, но участники проекта Blue Brain Project считают, что создадут серьезные предпосылки для его наступления. Как объясняют инженеры проекта Blue Brain Project, искусственный интеллект необходим не только для создания высокоавтономных и умных роботов, но и для повышения возможностей человеческого мозга за счет увеличения объема памяти и скорости работы с информацией. Все эти перспективы вместе с новыми возможностями несут и массу новых проблем. Так если часть памяти человека будет храниться в цифровом мозге, то она будет подвержена всем тем же угрозам, что и обычный компьютер. А это различные троянские вирусы, программы-шпионы, вирусы-разрушители Хронология