Проблема знаний - центральная проблема ИИ

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

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

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

Примеры:
иметь (Саша, книга)				«Саша имеет книгу»
иметь (Саша, книги)  иметь (Саша, книга)	«Если Саша имеет книги, то он имеет книгу»
(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-й Проблемной области);
- может самостоятельно уточнять (если это требуется) условия задач;
- демонстрирует способность к:
С-адаптации – сиюминутному изменению совокупности «знаний» в новых условиях – и
С-обучению – запоминанию результатов адаптации для использования в дальнейшем.

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

Предметная область – «срез» действительности, со своими объектами, отношениями.
Проблемная область – Предметная область + характерные задачи.

Примеры:
Предметная область –  Лисп как язык для обработки списков
Проблемные области:	автоматический синтез программ на Лиспе,
автоматизированное обучение приемам программирования на Лиспе.

Структуризация С-знаний (по нескольким независимым критериям):
1.
базовые	- встроенные в АДИС ее разработчиками
открытые	- пополняемые на различных этапах жизненного цикла АДИС
2.
общие		- используемые при работе в разных проблемных областях и с разными пользователями,
поблемно-ориентированные	- специфичные для конкретных проблемных областей,
личностно-ориентированные	- специфичные для различных пользователей
3.
лингвистические	- описывающие язык/языки общения с АДИС
предметные		- описывающие особенности конкретных предметных/проблемных областей
коммуникативные	- описывающие особенности общения в различных сеансах
4.
знания АДИС о ее окружении	- описывающие «внешний мир» АДИС
метазнания			- знания о С-знаниях

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

Проблемы полноты и репрезентативности обучающей выборки (при пополнении С-знаний).

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

Метазнания – средства разрешения конфликта между наличными С-знаниями и входной информацией.
Примеры конфликтов:
- не удается завершить анализ текста условия задачи, т.к. в нем встретилось незнакомое АДИС слово;
- не удается продолжить планирование решения, т.к. ни один оператор к очередной вершине дерева поиска неприменим;
- новый факт формально противоречит одному из ранее известных.

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

Пример обучаемой программы (М.Вайнцвайг)
Внешняя постановка задачи:
Программа получает на вход цепочку символов в некотором алфавите А (вопрос),
Генерирует ответ (цепочка символов над этим алфавитом),
Получает оценку Обучающего (+ - ответ верен, - - ответ неверен).
В процессе обучения программа должна научиться всегда строить правильные ответы (всегда получать оценку +).

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

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

Понятие о генетических алгоритмах
Генетические алгоритмы (ГА) - это стохастические, эвристические оптимизационные методы, впервые предложенные Холландом (1975). Они основываются на идее эволюции с помощью естественного отбора, выдвинутой Дарвином.
ГА работают с совокупностью "особей" - популяцией, каждая из которых представляет возможное решение данной проблемы. Каждая особь оценивается мерой ее "приспособленности" согласно тому, насколько "хорошо" соответствующее ей решение задачи. В природе это эквивалентно оценке того, насколько эффективен организм при конкуренции за ресурсы. Наиболее приспособленные особи получают возможность "воспроизводить" потомство с помощью "перекрестного скрещивания" с другими особями популяции. Это приводит к появлению новых особей, которые сочетают в себе некоторые характеристики, наследуемые ими от родителей. Наименее приспособленные особи с меньшей вероятностью смогут воспроизвести потомков, так что те свойства, которыми они обладали, будут постепенно исчезать из популяции в процессе эволюции. Иногда происходят мутации, или спонтанные изменения в генах. 
Таким образом, из поколения в поколение, хорошие характеристики распространяются по всей популяции. Скрещивание наиболее приспособленных особей приводит к тому, что исследуются наиболее перспективные участки пространства поиска. В конечном итоге популяция будет сходиться к оптимальному решению задачи. Преимущество ГА состоит в том, что он находит приблизительные оптимальные решения за относительно короткое время.
ГА состоит из следующих компонентов: 1) Хромосома (Решение рассматриваемой проблемы. Состоит из генов); 2) Начальная популяция хромосом; 3) Набор операторов для генерации новых решений из предыдущей популяции; 4) Целевая функция для оценки приспособленности (fitness) решений. 
Чтобы применять ГА к задаче, сначала выбирается метод кодирования решений в виде строки. Фиксированная длина (l-бит) двоичной кодировки означает, что любая из 2l возможных бинарных строк представляет возможное решение задачи.
Стандартные операторы для всех типов генетических алгоритмов это: селекция, скрещивание и мутация.
 Селекция
Оператор селекции (reproduction, selection) осуществляет отбор хромосом в соответствии со значениями их функции приспособленности. Существуют как минимум два популярных типа оператора селекции: рулетка и турнир. 
•	Метод рулетки (roulette-wheel selection) - отбирает особей с помощью n "запусков" рулетки. Колесо рулетки содержит по одному сектору для каждого члена популяции. Размер i-ого сектора пропорционален некоторой величине вычисляемой по формуле.
При таком отборе члены популяции с более высокой приспособленностью с большей вероятностью будут чаще выбираться, чем особи с низкой приспособленностью. 

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

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

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

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