___________ (Лекции 2010 года (rtf)), страница 2

XCON (R1) - выбор оптимальной конфигурации аппаратных средств (VAX).

Наблюдение - сравнение результатов наблюдения с ожидаемыми результатами.

VM - наблюдение за состоянием больного в палате интенсивной терапии.

Обучение - диагностика, отладка и ремонт поведения обучаемого.

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

Управление - управление поведением системы как целого.

VM

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

То, что нужно для решения задач (правила вывода, ...) хранится в базе знаний.

Поскольку ЭС предполагает такой режим работы с ней, что предполагается диалог с пользователем, должен быть пользовательский интерфейс. Если система управляет роботом, агентом, то пользовательский интерфейс может отсутствовать.

Должен быть интерфейс администратора. Мы говорили, что открытость БЗ может быть достигнута хирургическим путём --- все обновления вносит вручную администратор.

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

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

Основной цикл работы решателя ЭСистемы:

1. Выборка (правил-кандидатов, которые могут понадобиться при решении исходной задачи (ex. По предусловию);

2. Сопоставление (означивание переменных) (Пусть “фи” – реальный факт. Надо проверить, применимо ли к нему правило p: a->b);

3. Выполнить разрешение конфликтов – выбираем из всех полностью применимых правил одно по каким-то критериям (например, выбираем более дешёвое правило);

4. Выполнение действия.

Методы генерации текста:

1. caned-based methods

Неизменяющийся шаблон – просто печать строки символов без каких-либо изменений.

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

1 file copied

3 files copied

1. Template-based methods

Изменяющийся шаблон – бесконтекстная вставка слов в образец-строку.

Шаблон: <Число> file(s) copied.

0 file(s) copied

2 file(s) copied

1. Phrase-based methods

Контекстная вставка.

В зависимости от вида сообщения (контекста) шаблон может быть несколько изменён.

Шаблон: <Число> <Определение> <file/files при =1, >1 ><Глагол: время – прош.>

1 file copied

2 marked files copied

1. Feature-based methods

Синтез сообщения на основе набора свойств (грамматических признаков). Предложения определяется набором характеристик составляющих его слов и правилами их сочетаемости.

Шаблон: <Число> <Определение> <file/files при =1, >1 ><Глагол: время – любое>

1 file should be copied

2 marked files were copied

Перечислите коммерчески значимые сферы применения систем автоматической обработки текста (АОТ).

1. Machine Translation and Translation Aids - машинный перевод;

2. Text Generation - генерация текста;

3. Localization and Internationalization - локализация и интернационализация;

4. Controlled Language - работа на ограниченном языке;

5. Word Processing and Spelling Correction - создание текстовых документов (ввод, редактирование, исправление ошибок)

6. Information Retrieval - информационный поиск и связанные с ним задачи.

	Язык входного текста	Язык выходного текста
1	Естественный-1	Естественный-2
2	Искусственный	Естественный
3	Естественный	Искусственный / Естественный
4	Естественный	Естественный + { Искусственный}

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

Классификация методов поиска в пространстве решений:

1. Использование эвристической информации (слепые, эвристические);

2. Порядок раскрытия (перебора) вершин (поиск вширь, поиск вглубь);

3. Полнота просмотра пространства состояний (полные, неполные);

4. Направление поиска (прямые, обратные, двунаправленные).

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

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

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

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

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

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

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

Подчеркнем, что основной механизм системы GPS не был проблемно-ориентированным: он представлял собой реализацию универсального эвристического метода решения задач, часто применяемого человеком, и известного как анализ целей и средств (means-ends analysis). Ключевая идея этой эвристики такова:

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

2. последовательное устранение найденных различий с помощью подходящих средств–операций.

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

A* алгоритм:

Предположим, что эвристическая оценочная функция Est(V) построена таким образом, чтобы оценивать стоимость оптимального решающего пути, идущего из начальной вершины к одной из целевой вершин, при условии, что этот путь проходит через вершину V. Тогда значение оценочной функции можно представить в виде суммы двух слагаемых:

Est(V) = g(V) + h(V) (*)

где g(V) – оценка оптимального пути от начальной вершины до вершины V,

а h(V) – оценка оптимального пути от вершины V до целевой вершины.

Вариант алгоритма эвристического поиска, применяемого для поиска оптимального решающего пути и использующего при этом оценочную функцию указанного выше вида (*), известен в литературе как А-алгоритм. Были доказаны важные свойства этого алгоритма, прежде всего, утверждение о его допустимости.

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

Пусть h*(V) – стоимость оптимального пути из произвольной вершины V в целевую вершину. Верна следующая теорема о допустимости А-алгоритма:

А-алгоритм, использующий некоторую эвристическую функцию вида (*), где

g(V) – стоимость пути от начальной вершины до вершины V в дереве перебора, а

h(V) – эвристическая оценка оптимального пути из вершины V в целевую вершину,

является допустимым, если h(V) £ h*(V) для всех вершин V пространства состояний.

А-алгоритм эвристического поиска, применяющий функцию h(V), удовлетворяющую этому условию, получил название А*-алгоритма.

Практическое значение этой теоремы в том, что для допустимости А-алгоритма достаточно найти какую-либо нижнюю грань функции h*(V) и использовать ее в качестве h(V) – тогда оптимальность найденного алгоритмом решения будет гарантирована.

Если взять тривиальную нижнюю грань, т.е. установить h(V) = 0 для всех вершин пространства состояний, то допустимость будет обеспечена. Однако этот случай соответствует полному отсутствию какой-нибудь эвристической информации о задаче, и оценочная функция Est не имеет никакой эвристической силы, т.е. не сокращает возникающий перебор. А*-алгоритм ведет себя при этом аналогично поиску вширь.

Точнее, при Est(V) = g(V) (где g(V) – стоимость пути от начальной вершины до вершины V ), мы получаем алгоритм, известный как алгоритм равных цен (или Алгоритм Дейкстры). Алгоритм равных цен представляет собой более общий вариант метода перебора в ширину, при котором вершины раскрываются в порядке возрастания стоимости g(V) , т.е. в первую очередь раскрывается вершина из списка нераскрытых вершин, для которой величина g имеет наименьшее значение.

Обе предложенные для игры в восемь эвристические функции Est1(V) и Est2(V) удовлетворяют условию допустимости А*-алгоритма. Первое их слагаемое d(V) есть стоимость пути к вершине V при стоимости всех дуг с(V_A, V_B) = 1. Функции отличаются лишь вторым слагаемым, и можно показать, что значение второй функции всегда (т.е. для всех состояний), больше значения первой функции: Est1(V) £ Est2(V) , что равнозначно k (V) £ s (V) .

Из последнего неравенства следует, что условие допустимости достаточно доказать только для второй функции Est2. Справедливость нужного условия s(V) £ h*(V) следует из такого соображения. Если бы фишки не мешали друг другу и могли двигаться до «своего» места по кратчайшему пути, как если бы других фишек на квадрате не было, то сумма длин таких путей для всех фишек была бы в точности равна значению s(V) . На самом же деле фишки редко когда могут двигаться по кратчайшей траектории из-за того, что на ней расположены другие фишки, поэтому длина (стоимость) оптимального решения h*(V) будет не меньше s(V).

Минимаксный принцип:

1. ИЛИ-вершине дерева игры приписывается оценка, равная максимуму оценок ее дочерних вершин;

2. И-вершине игрового дерева приписывается оценка, равная минимуму оценок ее дочерних вершин.

Минимаксный принцип положен в основу минимаксной процедуры, предназначенной для определения наилучшего (более точно, достаточно хорошего) хода игрока исходя из заданной конфигурации игры S при фиксированной глубине поиска N в игровом дереве. Предполагается, что игрок ПЛЮС ходит первым (т.е. начальная вершина есть ИЛИ-вершина). Основные этапы этой процедуры таковы:

1. Дерево игры строится (просматривается) одним из известных алгоритмов перебора (как правило, алгоритмом поиска вглубь) от исходной позиции S до глубины N;

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

3. В соответствии с минимаксным принципом вычисляются оценки всех остальных вершин: сначала вычисляются оценки вершин, родительских для концевых, затем родительских для этих родительских вершин и так далее; таким образом оценивание вершин происходит при движении снизу вверх по дереву поиска  до тех пор, пока не будут оценены вершины, дочерние для начальной вершины, т.е. для исходной конфигурации S;

4. Среди вершин, дочерних к начальной, выбирается вершина с наибольшей оценкой: ход, который к ней ведет, и есть искомый наилучший ход в игровой конфигурации S.

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

• концевая вершина игрового дерева оценивается статической оценочной функцией сразу, как только она построена;

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

• предварительная оценка ИЛИ-вершины (альфа-величина) полагается равной наибольшей из вычисленных к текущему моменту оценок ее дочерних вершин;

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

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

Сформулируем теперь правила прерывания перебора, или отсечения ветвей игрового дерева:.

1. Перебор можно прервать ниже любой И-вершины, бета-величина которой не больше, чем альфа-величина одной из предшествующих ей ИЛИ-вершин (включая корневую вершину дерева);

2. Перебор можно прервать ниже любой ИЛИ-вершины, альфа-величина которой не меньше, чем бета-величина одной из предшествующих ей И-вершин.

При этом в случае А говорят, что имеет место альфа-отсечение, поскольку отсекаются ветви дерева, начиная с ИЛИ-вершин, которым приписана альфа-величина, а в случае В  бета-отсечение, поскольку отсекаются ветви, начинающиеся с бета-величин).