Искусственный интеллект – Севастополь

Искусственный интеллект – Севастополь – День 07, лекции № 21, № 22, № 23 и № 24

Проблема знаний - центральная проблема ИИ
Метод представления знаний – совокупность взаимосвязанных средств формального описания знаний и оперирования (манипулирования) этими описаниями.

(аналог модели данных в теории Баз Данных – понятие концептуального уровня)

Логические методы (язык предикатов)

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

Факт – формула в некоторой логике.

Система знаний – совокупность формул.

База знаний – система знаний в компьютерном представлении.
Основные операции: логический вывод (доказательство теорем)
Примеры:

иметь (Саша, книга) «Саша имеет книгу»

иметь (Саша, книги) иметь (Саша, книга) «Если Саша имеет книги, то он имеет книгу»

(x) [человек (x) иметь (x, книга)] «Каждый человек имеет книгу»

(x) [свободен (x) (y) (на (y,x))] «Если кубик x свободен, то нет такого кубика y,

который находится на кубике x»

Достоинства:

формальный аппарат вывода (новых фактов/знаний из известных фактов/знаний),
возможность контроля целостности,
простая и ясная нотация.

Недостатки:

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

Семантические сети

Знания, необходимые для решения задач и организации взаимодействия с пользователем, – объекты/события и связи между ними.

Статические семантические сети - сети с объектами.

Динамические семантические сети (сценарии) - сети с событиями.

Система знаний – совокупность сетей (или одна общая сеть).

База знаний – система знаний в компьютерном представлении.

Для представления семантических сетей используются графы:

вершина - атомарный объект (событие),

подграф - структурно сложный объект (событие),

дуга - отношение или действие.

Примеры отношений:

род-вид («компьютер» – «персональный_компьютер»)

целое-часть («компьютер» – «память»)

понятие-пример («компьютер» – «конкретный компьютер . . . »)

Основные операции: сопоставление с образцом, поиск, замена, взятие копии
Пример сети:

<описание компьютера>
Достоинства:

знания хорошо структурированы, структура понятна человеку.

Недостатки:

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

Фреймы

Знания, необходимые для решения задач и организации взаимодействия с пользователем, – фреймы.

Фрейм-понятие – отношение/действие + связанные этим отношением/участвующие в этом действии объекты.

Фрейм-пример – конкретный экземпляр отношения/действия + конкретные объекты (связанные этим отношением/участвующие в этом действии).

Система знаний – совокупность фреймов-понятий и фреймов-примеров.

База знаний – система знаний в компьютерном представлении.

Фрейм: ИМЯ - отношение/действие

СЛОТЫ - объекты или другие фреймы

С каждым слотом может быть связана такая информация:

УСЛОВИЕ НА ЗАПОЛНЕНИЕ (тип, «по умолчанию», связь с другими слотами)

АССОЦИИРОВАННЫЕ ПРОЦЕДУРЫ (действия, выполняемые, например, при заполнении этого слота)
Основные операции: поиск фрейма/слота, замена значения слота, взятие копии фрейма-понятия
Примеры:

Фрейм-понятие «Перемещать»

ПЕРЕМЕЩАТЬ (кто?, что?, откуда?, куда?, когда?, . . .)

Условия: кто? – человек, робот, . . .

откуда? – место

. . .

Фрейм-пример

ПЕРЕМЕЩАТЬ (Саша, Саша, Главное_Здание_МГУ, Факультет_ВМК, вчера в 15-30, . . .)

Фрейм-понятие «Персональный_компьютер»

ПЕРСОНАЛЬНЫЙ_КОМПЬЮТЕР (процессор?, тактовая_частота?, память?, монитор?, . . .)

Фрейм-пример

ПЕРСОНАЛЬНЫЙ_КОМПЬЮТЕР (Pentium-IV, 5 ГГц, 512Мб, SONY, . . .)

Достоинства:

знания хорошо структурированы, структура понятна человеку.

Недостатки:

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

Продукции

Знания, необходимые для решения задач и организации взаимодействия с пользователем, – продукции (продукционные правила).

Продукция – правило вида: p: (где: p – предусловие, - антецедент, - консеквент).

Система знаний – система продукционных правил + стратегия выбора правил.

База знаний – система знаний в компьютерном представлении.
Основные операции: вывод (применение правила, определение правила-преемника и т.д.)
Примеры:

True: T > 200C & P > 5 кПа открыть клапан № 3

True: Х - башня Х имеет_часть У1 & У1 есть КРЫША & . . .
Достоинства:

простая и ясная нотация.

Недостатки:

при большом количестве правил вывод идет очень долго,
при большом количестве правил их совокупность трудно обозрима.

Терминологические замечания:
1. Из психологии и педагогики нам известна триада: знания – умения – навыки.

Знания – усвоенные Понятия.

Умения – способность выполнять новые действия в новых условиях.

Навыки – действия, автоматизировавшиеся в процессе их усвоения и выполнения.

В работах по ИИ знаниями обычно называют и собственно знания, и умения, и навыки.

Поэтому говорят о: базах понятий, базах фактов, базах правил и т.п.

Чтобы не вступать в противоречие с литературными источниками, мы согласимся с такой трактовкой (расширенной) термина знания.

2.Базы знаний (БЗ) в работах по ИИ часто не совсем корректно противопоставляются базам данных (утверждается, например, что базы знаний в отличие от баз данных имеют встроенный дедуктивный механизм вывода следствий из известных фактов и т.п.).

Для нас это феномены разноплановых уровней:

База знаний – (у нас) – совокупность «знаний» системы ИИ в компьютерном представлении. Средством представления «знаний» может быть, в частности, та или иная штатная база данных (в обычном смысле).
Остановимся на некоторых острых аспектах проблемы знаний:

Проблема извлечения знаний

(рассмотрим в связи с экспертными системами – ЭС)

Проблема приобретения знаний

(рассмотрим в связи с экспертными системами – ЭС)

Проблема открытости знаний

Совокупность «знаний» системы ИИ неизбежно должна быть открыта для включения в нее новой информации, отражающей динамику проблемной среды и динамику поручаемых системе ИИ заданий.
Открытость может быть реализована по-разному:

- пополнение БЗ «хирургическим путем» (программист/администратор вносят изменения в тексты БЗ),

- обучение системы пользователем в рабочем режиме,

- самообучение системы (приспособление ее к новым условиям/задачам).

В дальнейшем (в этом разделе) мы будем рассматривать задачу создания универсальных Адаптивных диалоговых систем ИИ широкой ориентации (АДИС).

Это означает, что система:

- может работать с различными пользователями (группами пользователей) – уровень подготовки

профессия, и др.;

- может работать в различных Проблемных областях – в каждой из которых свои объекты, задачи и др.;

- может настраиваться при этом на Сеанс (работа i-го пользователя в j-й Проблемной области);

- может самостоятельно уточнять (если это требуется) условия задач;

- демонстрирует способность к:

С-адаптации – сиюминутному изменению совокупности «знаний» в новых условиях – и

С-обучению – запоминанию результатов адаптации для использования в дальнейшем.
Здесь и далее мы будем добавлять префикс «С-» к терминам, характеризующим структурные элементы АДИС и ее функциональные возможности.
Предметная область – «срез» действительности, со своими объектами, отношениями.

Проблемная область – Предметная область + характерные задачи.

Примеры:

Предметная область – Лисп как язык для обработки списков

Проблемные области: автоматический синтез программ на Лиспе,

автоматизированное обучение приемам программирования на Лиспе.
Структуризация С-знаний (по нескольким независимым критериям):

базовые - встроенные в АДИС ее разработчиками

открытые - пополняемые на различных этапах жизненного цикла АДИС

общие - используемые при работе в разных проблемных областях и с разными пользователями,

поблемно-ориентированные - специфичные для конкретных проблемных областей,

личностно-ориентированные - специфичные для различных пользователей

лингвистические - описывающие язык/языки общения с АДИС

предметные - описывающие особенности конкретных предметных/проблемных областей

коммуникативные - описывающие особенности общения в различных сеансах

знания АДИС о ее окружении - описывающие «внешний мир» АДИС

метазнания - знания о С-знаниях
Принцип полноты базовых знаний. Возможность/невозможность «обучения с нуля».
Проблемы полноты и репрезентативности обучающей выборки (при пополнении С-знаний).

Система С-знаний – динамически меняющаяся модель АДИС и ее окружения

Метазнания – средства разрешения конфликта между наличными С-знаниями и входной информацией.

Примеры конфликтов:

- не удается завершить анализ текста условия задачи, т.к. в нем встретилось незнакомое АДИС слово;

- не удается продолжить планирование решения, т.к. ни один оператор к очередной вершине дерева поиска неприменим;

- новый факт формально противоречит одному из ранее известных.
Разрешение конфликта:

поиск возможных причин (незнакомое слово – это либо действительно новое слово, либо слово с орфографической ошибкой);
их динамическое (в текущем С-сеансе) упорядочение;
выбор наилучшего способа устранения конфликта;
необходимая коррекция С-знаний (С-адаптация) или изменение входных данных (исправление орфографической ошибки);
С-обучение (факультативно), например, запись в словарь системы нового слова.

Пример обучаемой программы (М.Вайнцвайг)

Внешняя постановка задачи:

Программа получает на вход цепочку символов в некотором алфавите А (вопрос),

Генерирует ответ (цепочка символов над этим алфавитом),

Получает оценку Обучающего (+ - ответ верен, - - ответ неверен).

В процессе обучения программа должна научиться всегда строить правильные ответы (всегда получать оценку +).

Базовые знания программы:

Несколько универсальных эвристик, используемых человеком в случае столь же неопределенных (не имеющих смысловой интерпретации) задач. В числе таких эвристик:

Не выходить за пределы А.

Давать на очередной вопрос ответ, совпадающий с ответом на предыдущий вопрос.

Давать на очередной вопрос ответ, совпадающий с ответом на предыдущий вопрос, если этот ответ был оценен +.

Правильность ответа на некоторый вопрос не зависит от контекста (хода диалога).

В последние годы определенную популярность в работах по ИИ получил подход к моделированию процессов обучения/развития на основе так называемых генетических алгоритмов.

Понятие о генетических алгоритмах

Генетические алгоритмы (ГА) - это стохастические, эвристические оптимизационные методы, впервые предложенные Холландом (1975). Они основываются на идее эволюции с помощью естественного отбора, выдвинутой Дарвином.

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

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

ГА состоит из следующих компонентов: 1) Хромосома (Решение рассматриваемой проблемы. Состоит из генов); 2) Начальная популяция хромосом; 3) Набор операторов для генерации новых решений из предыдущей популяции; 4) Целевая функция для оценки приспособленности (fitness) решений.

Чтобы применять ГА к задаче, сначала выбирается метод кодирования решений в виде строки. Фиксированная длина (l-бит) двоичной кодировки означает, что любая из 2^l возможных бинарных строк представляет возможное решение задачи.

Стандартные операторы для всех типов генетических алгоритмов это: селекция, скрещивание и мутация.

Селекция

Оператор селекции (reproduction, selection) осуществляет отбор хромосом в соответствии со значениями их функции приспособленности. Существуют как минимум два популярных типа оператора селекции: рулетка и турнир.

Метод рулетки (roulette-wheel selection) - отбирает особей с помощью n "запусков" рулетки. Колесо рулетки содержит по одному сектору для каждого члена популяции. Размер i-ого сектора пропорционален некоторой величине вычисляемой по формуле.

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

Турнирный отбор (tournament selection) реализует n турниров, чтобы выбрать n особей. Каждый турнир построен на выборке k элементов из популяции, и выбора лучшей особи среди них. Наиболее распространен турнирный отбор с k=2.

Скрещивание

Оператор скрещивания (crossover) осуществляет обмен частями хромосом между двумя (может быть и больше) хромосомами в популяции. Может быть одноточечным или многоточечным. Одноточечный кроссовер работает следующим образом. Сначала, случайным образом выбирается одна из l-1 точек разрыва. Точка разрыва - участок между соседними битами в строке. Обе родительские структуры разрываются на два сегмента по этой точке. Затем, соответствующие сегменты различных родителей склеиваются и получаются два генотипа потомков.

Одноточечный оператор скрещивания (точка разрыва равна трем)

Мутация

Мутация (mutation) - стохастическое изменение части хромосом. Каждый ген строки, которая подвергается мутации, с вероятностью P_mut (обычно очень маленькой) меняется на другой ген.

Схема работы ГА

Работа ГА представляет собой итерационный процесс, который продолжается до тех пор, пока не выполнятся заданное число поколений или какой-либо иной критерий останова. На каждом поколении ГА реализуется отбор пропорционально приспособленности, кроссовер и мутация.

Схема работы простого ГА выглядит следующим образом: