Экспертные системы: лекция №2
•
1 like•1,708 views
Представление знаний (knowledge representation)
Экспертные системы: лекция №2
- 1. Представление знаний (knowledge representation) Лекция 2 муромцевди.рф dimour.spb.ru mouromtsev@mail.ifmo.ru Часть 1
- 2. ©2014МуромцевД.И.Лекция2 Представление знаний (1) Представление знаний — это множество синтаксических и семантических соглашений, которое делает возможным описание знаний о каком-либо предмете или задаче в памяти вычислительной машины. 2
- 3. ©2014МуромцевД.И.Лекция2 Неоднозначность представления «Молотком стукнули по графину, и он разбился» «Графином стукнули по кирпичу, и он разбился» Что именно разбилось? 3
- 4. ©2014МуромцевД.И.Лекция2 Сложные рассуждения 4 α∧ β → γ( )( )→ δ ∨α( )∧ ¬α → ¬β( )( ). Является ли теоремой логики высказываний эта формула?
- 5. ©2014МуромцевД.И.Лекция2 Соглашения о представлении Что же все-таки разбилось, X или Y? «X-ом стукнули по Y-ку, и он разбился» 5
- 6. ©2014МуромцевД.И.Лекция2 Представление знаний (2) Представление знаний — это высокоуровневое описание понятий, их взаимосвязи и действий, необходимых для решения проблемы на формальном языке, пригодном для построения компьютерной системы с одной стороны, и легком для понимания человеком, с другой. 6
- 7. ©2014МуромцевД.И.Лекция2 Табличные формы представления знаний 7 http://decisiontables.wikispaces.com/Software+History
- 8. ©2014МуромцевД.И.Лекция2 Таблицы решений (decision table) логические таблицы отображают соотношения между комбинациями условий и комбинациями действий 8 Условия Ситуации с1 с2 ... c4 У1 1 0 1 ... У2 1 1 0 Действия Д1 0 1 1 ... Д2 1 0 1
- 9. ©2014МуромцевД.И.Лекция2 Компоненты таблицы решений 9 Столбец условий Матрица соответствия условий Столбец действий Матрица возможных действий в ячейках таблицы решений могут использоваться любые символы (обычно 1/0, Да/Нет, Y/ N) можно использовать символ «—» («не имеет значения») структура таблицы модифицируется под задачу, т.к. в процессе использования добавление новых строк (условий и действий) затруднительно Алгоритм поиска решения прост в реализации
- 10. ©2014МуромцевД.И.Лекция2 Методика формализации знаний с помощью таблиц решений 1. Описание всех требуемых действий. 2. Выявление перечня условий, необходимых для выполнения указанных действий. 3. Определение ключевого набора условий при решении проблемы. 4. Поочередное описание ситуаций для частных решений проблемы. 10 1 2 3 4 5 6 … Есть движущаяся машина (1 – да, 0 – нет) 1 1 1 0 0 1 Расстояние до машины (1 – близко, 2 – далеко) 1 2 2 2 Свет светофора (1 – зеленый, 2 – желтый, 3 – красный) 3 не 1 1 2 Пешеход спешит (1 – да, 0 – нет) 1 Пешеход склонен к риску (1 – да, 0 – нет) 1 Стоять на месте 1 1 1 Перейти дорогу 1 1 1
- 11. ©2014МуромцевД.И.Лекция2 Пример таблицы решений “Чем заняться сегодня” 11 1 2 3 4 5 6 7 8 Сегодня рабочий день? 1 1 1 1 0 0 0 0 Сегодня выходной? 0 0 1 1 1 1 0 0 Идет дождь? 1 0 1 0 1 0 1 0 Отправиться на работу 1 1 Поехать на пикник 1 1 1 Смотреть телевизор 1 1 1 Пример таблицы решений со всеми возможными сочетаниями вариантов условий
- 12. ©2014МуромцевД.И.Лекция2 Избыточность примера Первая и вторая ситуации рекомендуют одно и то же, а отличаются только одним условием: идет или не идет дождь аналогично ситуации 3 и 5, 4 и 6, условия можно объединить символом “-” (не имеет значения) 12
- 13. ©2014МуромцевД.И.Лекция2 Оптимизированный пример 13 1 2 3 4 5 6 7 8 Сегодня рабочий день? 1 - - 0 0 Сегодня выходной? 0 1 1 0 0 Идет дождь? - 1 0 1 0 Отправиться на работу 1 Поехать на пикник 1 1 Смотреть телевизор 1 1 Таблица решений из примера после оптимизации (устранения дублирующихся рекмендаций)
- 14. ©2014МуромцевД.И.Лекция2 Пример таблицы решений для проектирования объективов Условия — параметры объектива, описываемые обобщенными значениями 1, 2 и 3 Действия — рекомендации по установке конкретных линз (оптических элементов), представленных обозначениями оптических поверхностей 14 1 2 3 … J - светосила системы W - угловое поле F - фокусное расстояние, L – хроматический диапазон Q – качество изображения, S - задний фокальный отрезок, D - положение входного зрачка не 2 не 2 - - - - не 2 - не 0 - - - - 2 - - - - - не 2 не 1 Оптический элемент B 1P1А Оптический элемент K 303I Оптический элемент C Оптический элемент Y 2P2P
- 15. ©2014МуромцевД.И.Лекция2 Достоинства и недостатки таблиц решений высокая степень формализации, наглядности процесса принятия решений, строятся регулярным образом и могут наращиваться практически до бесконечности, являются универсальным средством решения задач, для которых возможно описание ситуаций с помощью ограниченного набора условий, если различные ситуации характеризуются разными условиями, то таблицы решений становятся сильно разреженными и малоэффективными. 15
- 18. ©2014МуромцевД.И.Лекция2 Таблицы операторов Предложены в системе STRIPS (сокр. от STanford Research Institute Problem Solver). Разработаны в 1971 году: Ричардом Файксом (Fikes) и Нильсом Нильсоном (Nilsson)*. Предназначались для решения проблемы формирования плана поведения мобильного робота Shakey 18 * Fikes R.E. and Nilson N.J. (1971). STRIPS: a new approach to the application of theorem proving to problem solving. Artificial Intelligence, 2, 1971, p. 189-208 (Русский перевод: Файкс Р., Нильсое Н., Система STRIPS – новый подход к применению методов доказательства теорем при решении задач. – в сб. Интеллектуальные роботы, вып. 1. Под. Ред. Г.Е. Поздняка. – с. 382 – 403.)
- 20. ©2014МуромцевД.И.Лекция2 Shakey за работой. 1969 20
- 21. ©2014МуромцевД.И.Лекция2 Shakey передан в музей, 1983 21 http://www.computerhistory.org/
- 22. ©2014МуромцевД.И.Лекция2 Формализация задачи I Текущее состояние окружающей среды — помещений и предметов в них — представляется набором выражений предикат-аргумент: <предикат> ::= <предикатный символ> (<аргумент1>, …, <аргументn>); at(robot, roomA). 22
- 23. ©2014МуромцевД.И.Лекция2 Формализация задачи II совокупность (список или множество) предикатов образуют модель мира: W1 = {at(robot, roomA), at(box1, roomB), at(box2, roomC)}; Конечная ситуация также задается множеством предикатов: WK = { at(box1, roomА), at(box2, roomВ) }. 23
- 24. ©2014МуромцевД.И.Лекция2 Пример таблицы операторов 24 Оператор: move(X, Y) push(X, Y, Z) Предварительные условия: { at(robot, X) } { at(robot, Y), at(X, Y) } Список удалений: { at(robot, X) } { at(robot, Y), at(X, Y) } Список добавлений: { at(robot, Y) } { at(robot, Z), at(X, Z) }
- 25. ©2014МуромцевД.И.Лекция2 Метод «анализа целей и средств» Последовательный перебор операторов таблице невозможен из-за экспоненциального роста числа вариантов перебора. На каждом шаге отличие между текущим состоянием и целевым должно уменьшаться. 25 at(box1, roomА) { at(box1, roomB), at(robot, roomA) } { at(box1, roomB), at(robot, roomC) } { at(box1, roomB), at(robot, roomB) } { at(box1, roomA), at(robot, roomA) } W1 W2 push(X, Y, Z)
- 26. ©2014МуромцевД.И.Лекция2 Достоинства и недостатки таблиц операторов Таблица операторов, модель мира и цели представлены с помощью одного и того же синтаксиса в виде конструкций предикат–аргумент. Простой алгоритм поиска необходимых для достижения цели операций. Однако существуют ситуации, в которых система STRIPS оказывается не способной решать поставленные задачи. Одна из таких ситуаций получила название аномалия Зюссмана (Sussman Anomaly). 26