Архитектуры систем искусственного интеллекта (лекция 2)

1.

Архитектуры систем искусственного интеллекта
Лекция 2. Дедукция
Бессмертный Игорь Александрович
[email protected]
дд.мм.гггг
ОБРАЗОВАТЕЛЬНЫЕ ПРОГРАММЫ В ОБЛАСТИ
ТЕХНОЛОГИЙ ИСКУССТВЕННОГО ИНТЕЛЛЕКТА
1

2.

Название данного слайда
План
1. Определение.
2. Как реализуется дедукция.
3. База данных и база знаний.
4. Поиск решений Prolog.
5. Ограничения дедукции.
ВИДЕО ДОКЛАДЧИКА
2

3.

Название
слайда
Что
такоеданного
дедукция?
ДЕДУКЦИЯ
(от лат. deductio — выведение) — переход от посылок к заключению,
опирающийся на логический закон, в силу чего заключение с логической
необходимостью следует из принятых посылок. Характерная особенность
дедукции заключается в том, что от истинных посылок она всегда ведет
только к истинному заключению.
(Философская энциклопедия)
Если лёд нагревается, он тает.
Лёд нагревается.
↓
Лёд тает
ВИДЕО ДОКЛАДЧИКА
3

4.

Названиедедукция?
данного слайда
Почему
История (интеллект ≡ логика):
• 33х до н.э. Аристотель (силлогизмы).
• 1848. Джордж Буль (математическая логика).
• 189х. Джузеппе Пеано (логика высказываний).
• 1971. Ален Колмероэ (язык Prolog).
Идея: Исчисление высказываний может быть
возложено на машину.
4

5.

Название
данногодедуктивный
слайда
Как
реализовать
вывод
Почему не заводится мотор?
– Или нечему гореть, или нечем поджечь.
Начало
нет
Бензин
есть?
да
Алгоритм:
Искра
есть?
нет
да
Вывод:
Нечему гореть
Вывод:
Тогда не знаю
Вывод:
Нечем поджечь
Конец
Чем плох такой подход?
5
ВИДЕО ДОКЛАДЧИКА

6.

Название
слайда
Чем
плох данного
такой подход?
1. Алгоритм простейший, но нужно программировать.
2. Носитель знаний и программист – разные люди.
3. Любое
изменение
/
дополнение
данных
требует
перепрограммирования.
4. Изменение одного факта может потребовать изменений во многих
частях программы.
5. Программист нынче дорог.
Решение заимствуем из баз данных:
• База знаний.
• Машина вывода.
• Пользовательский интерфейс.
• Интерфейс инженера по знаниям.
6
ВИДЕО ДОКЛАДЧИКА

7.

Название
данного слайда
База
знаний
ЕСЛИ бензин = true И искра = true ТО старт = true.
ЕСЛИ бензобак ≠ empty И бензонасос_исправен = true ТО бензин = true.
ЕСЛИ аккумулятор_заряжен = true И катушка_исправна = true И
свеча_исправна = true ТО искра = true.
ВИДЕО ДОКЛАДЧИКА
7

8.

Название
данного
слайда
База
знаний
Prolog
% Правила
engine_start :- fuel, spark.
fuel :- tank, pump.
spark :- battery, coil, spark_plug.
% Откуда мы возьмем исходные данные?
% Факты
tank.
pump.
coil.
ВИДЕО ДОКЛАДЧИКА
8

9.

Название
данногонаслайда
Поиск
решения
Prolog
% Правила
engine_start :fuel, spark.
fuel :- tank, pump.
spark :- battery, coil,
spark_plug.
% Факты
tank.
pump.
coil.
9
start
1
4
spark
fuel
2
tank
5
3
pump
battery
coil
plug

10.

Название данные
данного слайда
Входные
в Prolog
% Правила
engine_start :- fuel, spark.
fuel :- tank, pump.
spark :- battery, coil, spark_plug.
% Факты
tank.
Польза от такой
pump.
программы → 0
coil.
ВИДЕО ДОКЛАДЧИКА
1
0

11.

Название данные
данного слайда
Входные
в Prolog(2)
% Входные данные
tank :- dialog(“Is the fuel tank empty? (yes/no)”,Answer),!,
Answer = no.
pump :- dialog(“Does the fuel pump buzz? (yes/no)”, Answer),!,
Answer = yes.
coil :- dialog(“Does the high voltage coil sparkle? (yes/no)”, Answer),!,
Answer = yes.
battery :- dialog(“Is the battery voltage higher than 12V? (yes/no)”, Answer),!,
Answer = yes.
…
dialog(Question, Answer) :- repeat, writeln(Question),
read(Answer), valid_answer(Answer).
valid_answer(yes).
ВИДЕО ДОКЛАДЧИКА
valid_answer(no).
1
1

12.

Название данного
Результат
работыслайда
программы
?- engine_start.
Is the fuel tank empty? (yes/no)
no
Does the fuel pump buzz? (yes/no)
yes
Does the high voltage coil sparkle? (yes/no)
yes
Is the battery voltage higher than 12V? (yes/no)
no
Польза от такой
программы
fail
1
2
по-прежнему → 0.
Мы и так знаем, что
мотор не заводится, а
причина здесь не
раскрывается.
ВИДЕО ДОКЛАДЧИКА

13.

Названиетакая
данного
Почему
базаслайда
знаний бесполезна?
● Логика безупречна.
● Результат известен и без дедуктивного вывода.
Нам нужен не результат (он известен), а его предпосылки (причины).
Мотор не заводится не потому, что бензин есть И аккумулятор разряжен, а
только потому, что аккумулятор разряжен.
ВИДЕО ДОКЛАДЧИКА
1
3

14.

Названиели
данного
Полезна
такая слайда
база знаний?
ЕСЛИ бензобак = empty ТО бензин = false.
ЕСЛИ бензонасос = false ТО бензин = false.
ЕСЛИ аккумулятор_заряжен = false ТО искра = false.
ЕСЛИ катушка_исправна = false ТО искра = false.
ЕСЛИ свеча_исправна = false ТО искра = false.
ЕСЛИ бензин = false ТО старт = false.
ЕСЛИ искра = false ТО старт = false.
Недостатки:
1. Отсутствие универсальности. На каждую
неисправность нужен свой набор правил.
2. Не выявляются сочетания причин.
1
4
ВИДЕО ДОКЛАДЧИКА

15.

Название логического
данного слайда
Порядок
поиска на основе дедукции
● Поиск сверху вниз – от гипотез к известным фактам.
start
1
4
spark
fuel
2
5
3
tank
pump
7
6
battery
plug
coil
● Поиск снизу вверх – от известных фактов к гипотезам.
.
start
6
7
spark
fuel
1
1
5
tank
2
3
pump
battery
ВИДЕО ДОКЛАДЧИКА
5
4
coil
plug

16.

Название логического
данного слайда
Порядок
поиска на основе дедукции
● Поиск сверху вниз – от гипотез к известным фактам.
Pros:
1. Хорошо согласуется с аппаратом математической логики.
2. Проверяется только истинность фактов, непосредственно участвующих в
правилах.
Cons: Проблема комбинаторной сложности поиска при вложенных правилах.
● Поиск снизу вверх – от известных фактов к гипотезам.
Pros:
1. Нет необходимости выбирать гипотезы.
2. Нет вложенных правил.
Cons: Число проверяемых фактов может быть очень большим.
ВИДЕО ДОКЛАДЧИКА
1
6

17.

Название
слайда
Нужен
лиданного
Prolog для
интеллектуальных систем?
• В 198х на Prolog возлагали большие надежды.
• Prolog действительно позволяет изящно решать
некоторые интеллектуальные задачи.
• Prolog – язык программирования, причем
экзотический. Требуется высокая квалификация
программиста.
• Машина вывода Prolog решает задачи методом
прямого перебора – крайне неэффективно. Без
применения специальных технологий решение
практических задач на Prolog невозможно.
1
7
ВИДЕО ДОКЛАДЧИКА

18.

Название данного
слайда
Особенность
дедукции
Дедукция → логическое следование → импликация.
ЕСЛИ не b ТО не a.
a
0
0
1
1
b
0
1
0
1
Все бедные люди счастливы.
Иван счастлив. Беден ли Иван? – не факт.
Олег богатый. Несчастен ли Олег? – не факт.
1
8
a→b
1
1
0
1
ВИДЕО ДОКЛАДЧИКА

19.

Название данного
слайда(2)
Особенность
дедукции
Характерная особенность дедукции заключается в том, что от
истинных посылок она всегда ведет только к истинному заключению.
ЕСЛИ собаку ударить, ТО собака убежит ИЛИ укусит.
В рамках дедукции такие умозаключения невозможны.
Решение:
ЕСЛИ собаку ударить И собака НЕ укусила, ТО она убежит.
ЕСЛИ собаку ударить И собака НЕ убежала, ТО она укусит.
ВИДЕО ДОКЛАДЧИКА
Однако здесь смешиваются исходные посылки и заключения.
1
9

20.

Название данного
слайдав бинарной логике
Особенность
дедукции
Отрицание как неудача (negation as failure).
Может_преподавать(X) ЕСЛИ Ученая_степень(X) И НЕ Судимость(X).
Может_преподавать(Петров)?
Ученая_степень(Петров) = true.
Судимость(Петров) = нет данных → false.
Может_преподавать(Петров) = true.
А может быть плохо искали?
2
0
ВИДЕО ДОКЛАДЧИКА

21.

Название данного
слайдаи открытого мира
Допущения
замкнутого
Closed World Assumption – На нет и суда нет.
Отсутствие данных о факте равносильно отсутствию факта.
Open World Assumption – То, что Вы на свободе - не ваше
достоинство, а наша недоработка.
Возможно всё, что не отрицается в явном виде.
.
ВИДЕО ДОКЛАДЧИКА
2
1

22.

Название данного
слайда логике в дедукции
Альтернативы
бинарной
Нечеткая логика (мягкие вычисления - soft computing)
– количественное измерение неопределенностей
Троичная логика (ternary logic)
– качественное измерение неопределенностей.
И та и другая плохо работают с отрицанием.
Завтра возможен дождь (достоверность 50%)
Отрицание этого факта (снятие неопределенности) равносильно самому
ВИДЕО ДОКЛАДЧИКА
факту.
2
2

23.

Название данного
слайда систем
Архитектура
дедуктивных
ВИДЕО ДОКЛАДЧИКА
2
3

24.

Название данного
слайда систем: Кто?
Архитектура
дедуктивных
Пользователь:
Источник запросов.
Оценщик
результатов.
Эксперт:
Обновление базы
знаний.
Исправление
ошибок.
ВИДЕО ДОКЛАДЧИКА
2
4

25.

Название данного
слайда
Источники
ошибок
в базах знаний
Почему в базах данных ошибок гораздо меньше?
-- БД формируются на основе первичных документов.
-- Возможны только ошибки ввода.
Базы знаний создаются экспертами. Источники ошибок:
-- Эксперты могут ошибаться.
-- Классификация зачастую неочевидна.
-- Немонотонность. Добавление новых фактов может
привести к неактуальности других фактов.
2
5
ВИДЕО ДОКЛАДЧИКА
-- Появление новых или изменение старых правил.

26.

Название
данного
слайда
Как
выявлять
ошибки
в базах знаний?
Признаки ошибки:
-- Отсутствие решения, когда оно заведомо существует.
-- Наличие противоречий в результатах.
ВИДЕО ДОКЛАДЧИКА
2
6

27.

Название данного
слайда к дедуктивной системе
Проблема
ввода запросов
Базы данных:
-- Схема базы данных стабильна.
-- Простая трансляция запросов в SQL.
Базы знаний:
-- Схема БЗ сложная и эволюционирующая.
-- Без знания схемы сформулировать запрос очень сложно.
-- Темпоральность сущностей.
-- Логика умолчания.
2
7
ВИДЕО ДОКЛАДЧИКА

28.

Названиесложного
данного слайда
Пример
запроса
Последний адрес А.С. Пушкина.
-- Ожидаемый ответ: С.-Петербург, наб. р. Мойки, д.12.
Что нужно сделать:
1. Идентифицировать субъект (А.С. Пушкин – русский поэт
Александр Сергеевич Пушкин, годы жизни 1799-1837). Но как
это сделать?
2. Найти все адреса проживания субъекта.
3. Выбрать последний адрес.
2
8
ВИДЕО ДОКЛАДЧИКА

29.

Название данного
слайда систем: Базы данных и знаний
Архитектура
дедуктивных
База знаний:
Правила.
База знаний:
Факты.
ВИДЕО ДОКЛАДЧИКА
2
9

30.

Название
данного
слайда
Базы
фактов
Vs. Базы
правил
База фактов:
База правил:
father(sergey, nikita).
father(X, Y) :- parent(X,Y), male(X).
mother(natalia, nikita).
mother(X, Y) :- parent(X,Y), female(X).
father(sergey, andrey).
brother(X,Y) :- sibling(X,Y), male(X).
mother(natalia, andrey).
sibling(X,Y) :- parent(Z,X), parent(Z,Y), X\=Y.
brother(nikita, andrey).
ВИДЕО ДОКЛАДЧИКА
3
0

31.

Название
данного
слайда
Базы
фактов
Vs. Базы
правил (2)
База фактов:
База правил:
Трудоемкость ввода
Трудоемкость ввода фактов
Объем баз знаний
Трудоемкость создания правил
Время поиска
Объем базы знаний
Время поиска
Память постоянно дешевеет.
Комбинаторную сложность поиска не устранить.
3
1
ВИДЕО ДОКЛАДЧИКА

32.

Название
данного
слайда
Базы
фактов
Vs. Базы
правил (3)
Решение:
-- Сохранять результаты вывода из правил в виде вторичных
фактов.
Множество неиспользуемых фактов → Разрастание БЗ.
Замедление. Возможное устаревание.
Новая задача: Управление вторичными фактами. Удаление
неиспользуемых и неактуальных фактов.
ВИДЕО ДОКЛАДЧИКА
3
2

33.

Название данного
слайда систем: Интерфейс
Архитектура
дедуктивных
Интеллектуальный
вывод
Интеллектуальный
ввод
3
3
ВИДЕО ДОКЛАДЧИКА

34.

Название данного слайда
Интеллектуальный
интерфейс
Требует мощных ресурсов.
Целесообразно использовать WEB-сервисы.
KIA Optima 2013.
Речевой ввод: Распознавание небольшого набора фиксированных
фраз. Высокий процент ошибок.
KIA Optima 2018.
Речевой ввод: Okey, Google.
ВИДЕО ДОКЛАДЧИКА
3
4

35.

Название данного
слайда систем: Машина вывода
Архитектура
дедуктивных
Машина вывода
Поиск решений.
Объяснение.
Как решение
получено
ВИДЕО ДОКЛАДЧИКА
3
5

36.

Название вывода
данного слайда
Машина
Наивный вывод невозможен для любой задачи реального мира.
Решения:
• Алгоритмы ускорения (префиксные деревья RETE и др.).
• Эвристики.
• Индексы.
ВИДЕО ДОКЛАДЧИКА
3
6

37.

Название данного
слайда
Объяснение
результатов
• Решение принимает человек.
• Ответственность за ошибки несёт ЛПР.
• Принятие важных решений требует уверенности в истинности
результатов поиска (прогнозов, рекомендаций).
ВИДЕО ДОКЛАДЧИКА
3
7

38.

Название данного слайда
Дескрипционная
логика и логика первого порядка
• Дескрипционная
логика
оперирует
с
атомарными
высказываниями.
• Логика первого порядка оперирует с предикатами.
• Кванторы существования и всеобщности.
В дескрипционной логике:
Если А то В.
В логике первого порядка:
Для всех А истинно В.
Существует А, для которого В истинно.
3
8
ВИДЕО ДОКЛАДЧИКА

39.

Название данного слайда
Заключение
• Дедукция привлекательна как способ моделировать
рассуждения.
• Дедукция не может порождать новые знания.
• Реализация дедукции на больших базах знаний приводит к
высокой сложности.
• В силу этого дедуктивные интеллектуальные системы
возможны только для узкого домена.
ВИДЕО ДОКЛАДЧИКА
3
9

40.

Спасибо за внимание!
ОБРАЗОВАТЕЛЬНЫЕ ПРОГРАММЫ В ОБЛАСТИ
ТЕХНОЛОГИЙ ИСКУССТВЕННОГО ИНТЕЛЛЕКТА