- •Лекция 1: Введение
- •Основные понятия и определения.
- •Область применения.
- •Краткий исторический обзор развития работ в области ии.
- •Функциональная структура использования сии.
- •Литература
- •Сетевые модели
- •Продукционные модели.
- •Сценарии.
- •Интеллектуальный интерфейс
- •Классификация уровней понимания
- •Методы решения задач.
- •Решение задач методом поиска в пространстве состояний.
- •Решение задач методом редукции.
- •Решение задач дедуктивного выбора
- •Решение задач, использующие немонотонные логики, вероятностные логики.
- •Данные и знания. Основные определения.
- •Особенности знаний. Переход от Базы Данных к Базе Знаний.
- •Модели представления знаний. Неформальные (семантические) модели.
- •Например, структура табл. 1.1, записанная в виде протофрейма, имеет вид
- •Формальные модели представления знаний.
- •Компоненты продукционных систем
- •Стратегии решений организации поиска
- •Представление простых фактов
- •- Описание состояния человека
- •- Описание размещения персонала предприятия
- •Примеры применения логики для представления знаний.
- •Литература
- •Лекция 6: Планирование задач
- •Основные определения
- •Комплексная схема нечеткого планирования
- •Особенности планирования целенаправленных действий
- •Оценки сложности задачи планирования
- •Литература
- •Структура экспертных систем
- •Этапы разработки экспертных систем
- •Интерфейс с конечным пользователем
- •Представление знаний в экспертных системах
- •Уравни представления и уровни детальности
- •Организация знаний в рабочей системе
- •Организация знаний в базе данных
- •Методы поиска решений в экспертных системах
- •Средства представления знаний и стратегии управления
- •Подготовительный этап
- •Основной этап
- •Системы приобретения знаний от экспертов
- •Формализация качественных знаний
- •Пример формализации качественных знаний
- •Понимание в диалоге
- •Примеры системы обработки естественного языка
- •Методы озвучивания речи
- •Наиболее распространенные системы синтеза речи
- •Речевой вывод информации
- •Методы синтеза речи
- •Обобщенная функциональная структура синтезатора
- •Модуль лингвистической обработки
- •Лингвистический анализ
- •Формирование просодических характеристик
- •Cинтезатор русской речи
- •Язык формальной записи правил синтеза
- •Интонационное обеспечение
- •Аллофонная база данных
- •Лингвистический анализ
- •Инструментарий синтеза русской речи
- •Cистема распознавания речи
- •Акустическая модель
- •Лингвистическая модель
- •Классификация систем распознавания речи
- •-Простейшие (корреляционные) детекторы
- •Заключение
- •Литература
- •Основные принципы или целостность восприятия
- •Распознавание символов
- •Шаблонные системы
- •Структурные системы
- •Признаковые системы
- •Структурно-пятенный эталон
- •Уроки машинного чтения от Cognitive Technologies
- •Распознавание рукописных текстов
- •В этой статье я хотел бы затронуть некоторые из последних научных работ в области искусственной жизни и искусственного интеллекта.
- •Состояние и тенденции развития искусственного интеллекта
- •Успехи систем искусственного интеллекта и их причины
- •Экспертные системы реального времени - основное направление искусственного интеллекта
- •Основные производители
- •Архитектура экспертной системы реального времени
- •Жизненный цикл приложения
- •Основные компоненты
- •Базы знаний
- •Машина вывода, подсистема моделирования и планировщики
- •Заключение
- •Литература
Оценки сложности задачи планирования
Приведем ряд результатов, касающихся сложности решения задач планирования.
1. Анализ вычислительных задач оказывается PSPACE-полной проблемой даже при условии, что «пустых» величин нет .
2. Для вычислительных моделей без функциональных величин, т. е. с пустыми Db и F, проблема анализа вычислительных задач оказывается: а) PSPACE-полной для Н, содержащих функциональные и операторные зависимости без ; б) NP-полной для Н, содержащих только функциональные и вариантные зависимости без «пустой» величины ; в) полиномиальной (по времени работы планировщика) для Н, содержащих только функциональные и неявные зависимости; г) можно построить планировщики с линейным временем работы для Н только с функциональными зависимостями без и для Н с функциональными и неявными зависимостями .
В системе ПГИЗ Db и F пусты, а в Н имеются только функциональные и операторные зависимости без «пустой» величины . В системе автоматического синтеза программ СПОРА используется исчисление предикатов, для которого разработана специальная стратегия вывода .
Дерево анализа для вычислительной задачи - это дерево из формул используемого исчисления, в корне которого находится формула, представляющая исходную задачу, каждая нетерминальная вершина дерева может быть получена по одному из правил вывода «исчисления вычислительных задач» из формул, расположенных в дереве непосредственно ниже, а терминальные (висячие) вершины не являются заключением ни одного из правил вывода «исчисления вычислительных задач».
Планировщик в таком исчислении работает следующим образом: для заданной задачи конструируется какое-нибудь дерево анализа. Если все его висячие вершины являются аксиомами, то по этому дереву «собирается» программа. В противном случае формируется обоснование того, что задача неразрешима. Отсутствие детерминизма при логическом выводе в исчислениях стандартного типа приводит к экспоненциальному перебору возможных ветвей. Обнаружение при таком переборе тупика оказывается бесполезным (или почти бесполезным) для поиска на других ветвях дерева вывода. В «исчислении вычислительных задач» для полного решения задачи планировщику достаточно располагать каким-нибудь деревом анализа. При разумной стратегии построения деревьев анализа это позволяет получать сравнительно быстрые процедуры планирования .
В общем случае планировщику приходится решать PSPACE-полную задачу. Это означает, что все известные сейчас планировщики на почти всех вычислительных задачах работают экспоненциальное время. В реальности ситуация не столь плоха. Практически интересные задачи, как правило, допускают эффективное планирование. И хотя доля подобных задач с ростом параметров, определяющих их, стремится к нулю, именно они представляют интерес с точки зрения эффективности автоматического синтеза программ. Показателем практически интересных задач может служить степень взаимодействия подзадач в процессе решения исходной задачи . Понятия «подзадача» и «условия подзадачи» возникают уже на стадии наивной интерпретации следующих зависимостей.
Функциональной зависимости (F->Y1), где F -функциональная величина типа (X->-Y), предполагающей предварительный синтез процедуры вычисления F, входными параметрами которой являются величины из списка X.
Операторных зависимостей, предполагающих синтез т процедур с входами «условиями подзадач» X1, Х2, ..., Хь-
Вариантных зависимостей, предполагающих, что создаются две ветви вычислений: для первой известны значения всех величин из списка Y1, для второй - из списка У2.
Рассмотрим простой (но типичный) пример. Пусть имеют место функциональная зависимость D1: (A, В, С Е) и операторные зависимости D2: ((С Е ) Е1), D3:(( B Е1)) Е2)), D4: ((A Е2 ) Е3). Необходимо найти Ез. Для этого следует решить подзадачу (A Е2 ). Если воспользоваться зависимостью D3, то придем к поиску решения новой подзадачи ( B Е1). Если использовать зависимость D2, то придем к необходимости решения подзадачи ( C Е), которая согласно D1 разрешима только тогда, когда A и В известны. Степень взаимодействия подзадач в этом примере равна трем. Процесс является типичной схемой планирования в пространстве задач .
Для планировщиков, работающих в «исчислении вычислительных задач;», синтез решения вычислительной задачи происходит за время hqrl/r!, где h - константа, l-длина записи задачи, определяемая как суммарное число вхождений имен используемых величин в F и H, q- общее число «различных» аргументов величин из «условия подзадач» в операторных зависимостях из H и «условий вариантов» в вариантных зависимостях из H, r-минимальная степень взаимодействия подзадач в исходной задаче . Эта оценка носит квазиоптимальный характер. Планировщик работает долго только на тех задачах, которые не являются естественными, так как требуют предельного переплетения между собой всех подзадач, на которые разбивается исходная задача. Эксперименты показывают, что для задач, встречающихся на практике, время работы планировщика является полиномиальным. Память, необходимая для работы планировщика в «исчислении вычислительных задач», оценивается величиной bl2, где Ь - константа. Если в Н нет вариантных зависимостей, то требуется линейный объем памяти dl, где d-константа .
В известных сейчас планировщиках получаемые программы далеки от оптимальных. Наблюдается тенденция ухудшения качества программ при уменьшении времени работы планировщика. При этом синтезировать оптимальные последовательные программы труднее, чем оптимальные параллельные программы. Это обстоятельство в связи с развитием ЭВМ новой архитектуры, ориентированной на параллельные процессы, может оказаться выгодным. Например, задача поиска минимальных по времени последовательного исполнения программ для решения вычислительных задач, у которых Db пусто, а Н состоит только из функциональных зависимостей , оказывается NP-полной в сильном смысле . С другой стороны, в «исчислении вычислительных задач» при условии, что Db пусто, а Н состоит из функциональных и неявных зависимостей, можно за линейное время kl (k - константа) синтезировать программу, параллельное выполнение которой требует минимального для данной задачи времени .
В системе ПРИЗ и ее модификациях вычислительная задача считается разрешимой, если соответствующая ей формула выводима в позитивном фрагменте интуиционистского исчисления высказываний , т. е. в том и только том случае, когда достигается успех планировщиком системы ПРИЗ. Для «исчисления вычислительных задач» возможны две семантики для разрешимости .
Предельно неконструктивная; вычислительная задача считается разрешимой, если в любой базе данных (любой интерпретации), удовлетворяющей всем ограничениям вычислительной модели, имеет место некоторая функция типа (X Y);
предельно конструктивная: обобщенная стандартная схема программы считается решением вычислительной задачи, если в любой интерпретации, удовлетворяющей всем ограничениям вычислительной модели, имеет место функция типа (X Y), вычисляемая программой П, получающейся из обобщенной стандартной схемы программы соответствующей конкретизацией предикатных и функциональных символов.
«Исчисление вычислительных задач» корректно и полно относительно обеих семантик. При первой семантике планировщик всегда выдает решение исходной задачи в виде правильной программы, при второй - класс всех пропозициональных формул, описывающих разрешимые вычислительные задачи, совпадает с классом всех формул, выводимых в интуиционистском исчислении высказываний. Это показывает, что «исчисление вычислительных задач» можно рассматривать как один из вариантов формализации предложенной в интерпретации интуиционистской логики как логики «задач».
Во многих ИС используются планировщики, возможности которых существенно шире, чем у планировщика системы ПРИЗ, или того, который применяется в «исчислении вычислительных задач». Исчисления, с которыми имеют дело многие планировщики систем автоматизированного проектирования, планирования и управления, шире интуиционистских исчислений высказываний. При этом используются эвристические соображения, не имеющие аналогов в тех соотношениях, в которых описывались вычислительные модели. Примером может служить планировщик системы МАВР, предназначенной для ИС автоматизированного проектирования . При его работе возникают ситуации, не разрешимые в теории, которая описывалась выше. Такие случаи заставляют искать иные пути построения системы для поиска планов действий.