Глава 7. Экспертные системы. Краткий конспект (часть 1/2)
Ну кароч вот, ещё одна глава тов. Лорьера осилена. Мне показалось изложение довольно сумбурным - кроме прочего, часто перемежающееся примерами систем с их то подробным (классическое доказательство теорем и прочая), то кратким описанием (доставила система для изучения болезней томатов). Я попыталась собрать мысли в кучку один раз, но этого показалось мало. Прошу любить и жаловать вторую попытку (да не забросают меня тапками те, кто усомнится в истинности логических символов - ибо оные были заменены на аналоги, коие позволяет набрать клавиатура без лишних свистелок и перделок; мне и самой неприятно, но сил уже нет ничего править. Надеюсь, смысл не пострадал особо. В книге, понятное дело, всё как надо.). В конце, по традиции, интересненькое.
Проставлю тому, кто объяснит мне, зачем я всё это делаю.
Глава 7
Экспертные системы
БЗ - база знаний
ПП - процедурная программа
ЯП - язык программирования
ЭС - экспертная система
ЕЯ - естественный язык
КУ - коэффициент уверенности
КН - коэффициент надёжности
Основные свойства:
возможность обработки символьной информации,
использование неполных данных для построения логических выводов,
взаимодействие с человеком с помощью естественного языка.
Цель - достижение результатов, получаемых лучшими специалистами в своих областях.
Поэтому такие системы и получили название экспертных.
Задачи, которые стоят перед ЭС:
· Сбор знаний (обучение) сформулировать
· Хранение знаний (структурирование) запомнить
· Применение знаний (работа системы) использовать
Возникли два подхода к созданию ЭС: декларативный и процедурный (алсо программирование, холивары, кровь-кишки-расчленёнка - всё здесь). Сначала про внутреннюю кухню продукционных ЭС (из чего состоят и какие варианты возможны), а потом - про сравнение подходов, и в завершении - про преимущества и недостатки продукционных систем.
Продукционные системы
Продукционное правило представляет собой выражение вида: MG -> MD, в котором левая часть MG описывает определённую ситуацию, представленную в соответствии с формальными правилами рабочего пространства, а правая часть MD представляет собой действие, выполнение которого предполагается в случае обнаружения соответствующей ситуации.
Структура продукционной системы
Система в целом состоит из:
- БЗ, которая содержит множество продукционных правил,
- рабочего пространства (или БФ),
- программного интерпретатора (машина вывода).
Рабочее пространство
Рабочее пространство в начале работы содержит формулировку поставленной задачи, а затем в нём появляется множество фактов, которые программа смогла установить к текущему моменту времени.
Интерпретатор
Интерпретатор является основной частью системы и полностью управляет порядком выводов, выполнение которых всегда можно представить в виде последовательности похожих друг на друга элементарных циклов:
а) ОПРЕДЕЛЕНИЕ (Определить правила и относящиеся к ним факты путём унификации);
б) ВЫБОР (Выбрать такие правила, которые следует выполнить для эффективного решения задачи);
в) ВЫВОД (Выполнить действие, используя результаты этапа а). Построить новую БФ).
(Пополнение БФ) Различие между продукционными системами заключается в том, что в одних системах новая информация, полученная с помощью выводов, просто прибавляется к базе фактов, а в других - прибавляется с разрушением и замещением уже присутствовавших там фактов.
(Вывод) Движение к цели при работе системы происходит естественным образом (как и при доказательстве теоремы) и может быть легко представлено с помощью дерева И/ИЛИ. В действительности дерево может быть пройдено в одном из двух направлений: или от фактов к заключению, или от заключения, которое в этом случае рассматривается как предположение, к фактам. В первом случае говорят о движении по цепочке вперёд, во втором - о движении по цепочке назад. Чаще всего выбирают второе решение, дабы избежать комбинаторного взрыва.
В зависимости от используемой схемы вывода, системы можно разделить на:
- Системы с прямым выводом:
естественная дедукция, логика предикатов 1-го порядка;
- Системы с обратным выводом:
логика высказываний: модус поненс (из p и p->q следует q) или её вариант модус толлент (из !q и p->q следует !p);
- Системы с выводом в обе стороны:
логика предикатов 1-го порядка с выводом в виде метода резолюции - Пролог.
(Управление) Проблема управления, состоящая в разрешении конфликтов между правилами, готовыми к выполнению, имеет три варианта решения, в основе которых лежит:
· Исчерпывающий перебор (все варианты).
· Выбор правила с помощью оценки (упорядочивание правил при помощи приоритетов).
· Управление с помощью метаправил (самоорганизация системы: стратегии и формирование новых правил).
База знаний
(Типы знаний) Л. предлагает выделить 8 основных типов знаний
1) Базовые элементы, объекты реального мира. (Непосредственно воспринимаются)
2) Утверждения и определения. (Основаны на базовых элементах, заранее достоверны)
3) Концепции. (Перегруппировки или обобщения базовых объектов)
4) Отношения. («свойство - значение», как для свойств базовых элементов, так и отношения между концепциями)
5) Теоремы и правила перезаписи. (Частный случай продукционных правил)
6) Алгоритмы решения. (Решают определённые задачи)
7) Стратегии и эвристика. (Правила поведения, которые позволяют в данной конкретной ситуации принять решение о необходимых действиях. По типу «Я знаю, что А приведёт к Б, поэтому если я хочу получить Б, то мне следует сделать А»)
8) Метазнание.(Знание того, что известно + коэффициенты доверия к знанию)
(Коэффициент надёжности и коэффициент уверенности (на примере ЭС MYCIN)) С каждым правилом связан коэффициент надёжности (КН), принимающий значения от 0 до 1, который выражает большую или меньшую достоверность заключения эксперта. В самом деле, знание в этой области никогда не бывает абсолютно надёжным. Точно так же и наблюдаемые факты не являются чаще всего независимыми и надёжными.
Факты, относящиеся к внешнему миру, представляются в виде триплетов, оцененных коэффициентом уверенности (КУ), который может принимать значения от -1 до 1.
Коэффициент уверенности КУ, полученный из нового факта, выведенного из правила с коэффициентом надёжности КН, задаётся формулой КУ = КН Х min КУPj, где КУPj обозначает коэффициент уверенности для j-й посылки.
Если в процессе рассуждений два различных правила приводят к одному и тому же заключению, но с разными значениями КУ, равными КУ1 и КУ2, то они взаимно усиливают друг друга КУ = КУ1 + КУ2 - КУ1 Х КУ2.
Всякий факт, для которого абсолютное значение КУ меньше 0,2, рассматривается системой как малонадёжный и исключается из базы фактов.
(Способы представления знаний) От «закрытых» процедурных до «открытых», «неупорядоченных» декларативных:
1. Конечный автомат
2. Программа
3. Скрипт (схема) - описание стереотипного сценария действия с участием определённых объектов («Я вошёл в ресторан, официантка принесла мне меню»)
4. Семантическая сеть
5. Фрейм (прототип) - структуры данных, описывающие какую-либо типичную ситуацию (ожидание в аэропорту или участие в семейном обеде)
6. Графы, сети
7. Формальная спецификация
8. Исчисление предикатов
9. Теоремы, правила перезаписи
10. Продукционные правила
11. Предложения на языке
Хотя конечные автоматы, программы, исчисление предикатов и системы с продукционными правилами с теоретической точки зрения эквивалентны друг другу, поскольку их в принципе можно свести к универсальной машине Тьюринга, их «эксплуатационные характеристики» сильно различаются.
(Метазнание) Метазнание представляет собой любое знание о знании.
Можно выделить метазнание объектов окружающего мира и метазнание стратегий.
Окончание
Проставлю тому, кто объяснит мне, зачем я всё это делаю.
Глава 7
Экспертные системы
БЗ - база знаний
ПП - процедурная программа
ЯП - язык программирования
ЭС - экспертная система
ЕЯ - естественный язык
КУ - коэффициент уверенности
КН - коэффициент надёжности
Основные свойства:
возможность обработки символьной информации,
использование неполных данных для построения логических выводов,
взаимодействие с человеком с помощью естественного языка.
Цель - достижение результатов, получаемых лучшими специалистами в своих областях.
Поэтому такие системы и получили название экспертных.
Задачи, которые стоят перед ЭС:
· Сбор знаний (обучение) сформулировать
· Хранение знаний (структурирование) запомнить
· Применение знаний (работа системы) использовать
Возникли два подхода к созданию ЭС: декларативный и процедурный (алсо программирование, холивары, кровь-кишки-расчленёнка - всё здесь). Сначала про внутреннюю кухню продукционных ЭС (из чего состоят и какие варианты возможны), а потом - про сравнение подходов, и в завершении - про преимущества и недостатки продукционных систем.
Продукционные системы
Продукционное правило представляет собой выражение вида: MG -> MD, в котором левая часть MG описывает определённую ситуацию, представленную в соответствии с формальными правилами рабочего пространства, а правая часть MD представляет собой действие, выполнение которого предполагается в случае обнаружения соответствующей ситуации.
Структура продукционной системы
Система в целом состоит из:
- БЗ, которая содержит множество продукционных правил,
- рабочего пространства (или БФ),
- программного интерпретатора (машина вывода).
Рабочее пространство
Рабочее пространство в начале работы содержит формулировку поставленной задачи, а затем в нём появляется множество фактов, которые программа смогла установить к текущему моменту времени.
Интерпретатор
Интерпретатор является основной частью системы и полностью управляет порядком выводов, выполнение которых всегда можно представить в виде последовательности похожих друг на друга элементарных циклов:
а) ОПРЕДЕЛЕНИЕ (Определить правила и относящиеся к ним факты путём унификации);
б) ВЫБОР (Выбрать такие правила, которые следует выполнить для эффективного решения задачи);
в) ВЫВОД (Выполнить действие, используя результаты этапа а). Построить новую БФ).
(Пополнение БФ) Различие между продукционными системами заключается в том, что в одних системах новая информация, полученная с помощью выводов, просто прибавляется к базе фактов, а в других - прибавляется с разрушением и замещением уже присутствовавших там фактов.
(Вывод) Движение к цели при работе системы происходит естественным образом (как и при доказательстве теоремы) и может быть легко представлено с помощью дерева И/ИЛИ. В действительности дерево может быть пройдено в одном из двух направлений: или от фактов к заключению, или от заключения, которое в этом случае рассматривается как предположение, к фактам. В первом случае говорят о движении по цепочке вперёд, во втором - о движении по цепочке назад. Чаще всего выбирают второе решение, дабы избежать комбинаторного взрыва.
В зависимости от используемой схемы вывода, системы можно разделить на:
- Системы с прямым выводом:
естественная дедукция, логика предикатов 1-го порядка;
- Системы с обратным выводом:
логика высказываний: модус поненс (из p и p->q следует q) или её вариант модус толлент (из !q и p->q следует !p);
- Системы с выводом в обе стороны:
логика предикатов 1-го порядка с выводом в виде метода резолюции - Пролог.
(Управление) Проблема управления, состоящая в разрешении конфликтов между правилами, готовыми к выполнению, имеет три варианта решения, в основе которых лежит:
· Исчерпывающий перебор (все варианты).
· Выбор правила с помощью оценки (упорядочивание правил при помощи приоритетов).
· Управление с помощью метаправил (самоорганизация системы: стратегии и формирование новых правил).
База знаний
(Типы знаний) Л. предлагает выделить 8 основных типов знаний
1) Базовые элементы, объекты реального мира. (Непосредственно воспринимаются)
2) Утверждения и определения. (Основаны на базовых элементах, заранее достоверны)
3) Концепции. (Перегруппировки или обобщения базовых объектов)
4) Отношения. («свойство - значение», как для свойств базовых элементов, так и отношения между концепциями)
5) Теоремы и правила перезаписи. (Частный случай продукционных правил)
6) Алгоритмы решения. (Решают определённые задачи)
7) Стратегии и эвристика. (Правила поведения, которые позволяют в данной конкретной ситуации принять решение о необходимых действиях. По типу «Я знаю, что А приведёт к Б, поэтому если я хочу получить Б, то мне следует сделать А»)
8) Метазнание.(Знание того, что известно + коэффициенты доверия к знанию)
(Коэффициент надёжности и коэффициент уверенности (на примере ЭС MYCIN)) С каждым правилом связан коэффициент надёжности (КН), принимающий значения от 0 до 1, который выражает большую или меньшую достоверность заключения эксперта. В самом деле, знание в этой области никогда не бывает абсолютно надёжным. Точно так же и наблюдаемые факты не являются чаще всего независимыми и надёжными.
Факты, относящиеся к внешнему миру, представляются в виде триплетов, оцененных коэффициентом уверенности (КУ), который может принимать значения от -1 до 1.
Коэффициент уверенности КУ, полученный из нового факта, выведенного из правила с коэффициентом надёжности КН, задаётся формулой КУ = КН Х min КУPj, где КУPj обозначает коэффициент уверенности для j-й посылки.
Если в процессе рассуждений два различных правила приводят к одному и тому же заключению, но с разными значениями КУ, равными КУ1 и КУ2, то они взаимно усиливают друг друга КУ = КУ1 + КУ2 - КУ1 Х КУ2.
Всякий факт, для которого абсолютное значение КУ меньше 0,2, рассматривается системой как малонадёжный и исключается из базы фактов.
(Способы представления знаний) От «закрытых» процедурных до «открытых», «неупорядоченных» декларативных:
1. Конечный автомат
2. Программа
3. Скрипт (схема) - описание стереотипного сценария действия с участием определённых объектов («Я вошёл в ресторан, официантка принесла мне меню»)
4. Семантическая сеть
5. Фрейм (прототип) - структуры данных, описывающие какую-либо типичную ситуацию (ожидание в аэропорту или участие в семейном обеде)
6. Графы, сети
7. Формальная спецификация
8. Исчисление предикатов
9. Теоремы, правила перезаписи
10. Продукционные правила
11. Предложения на языке
Хотя конечные автоматы, программы, исчисление предикатов и системы с продукционными правилами с теоретической точки зрения эквивалентны друг другу, поскольку их в принципе можно свести к универсальной машине Тьюринга, их «эксплуатационные характеристики» сильно различаются.
(Метазнание) Метазнание представляет собой любое знание о знании.
Можно выделить метазнание объектов окружающего мира и метазнание стратегий.
Окончание