ГОУ ВПО «Дагестанский государственный институт

ГОУ ВПО «Дагестанский
государственный
институт народного
хозяйства Правительства
РД»
Кафедра «Информационные технологии»
Галяев Владимир Сергеевич
Победа Александр Павлович
Учебное пособие
по дисциплине
«Функциональное программирование и интеллектуальные системы»
для направления подготовки 080500 «Бизнес-информатика»
Профилей подготовки «Электронный бизнес» и «Архитектура
предприятия»
Махачкала – 2011
Составители: Галяев Владимир Сергеевич, кандидат физикоматематических наук, зав.кафедрой «Информационные технологии»
ДГИНХ; Победа Александр Павлович, преподаватель кафедры «Информационные технологии» ДГИНХ
Внутренний рецензент: Галяев Владимир Сергеевич, кандидат физико-математических наук, заведующий кафедрой «Информационные
технологии» ДГИНХ
Внешний рецензент: Газимагомедов Ахмед Абдуллаевич, кандидат
экономических наук, главный специалист научно – организационного отдела ДНЦ РАН.
Учебное пособие разработано с учетом требований п.41 Типового положения об образовательном учреждении высшего профессионального образования (высшем учебном заведении) РФ, Утвержденного постановлением Правительства РФ от 14.02.2008 №71.
Галяев В.С., Победа А.П. Учебное пособие по дисциплине «Функциональное программирование и интеллектуальные системы» для направления подготовки «Бизнес-информатика» – Махачкала: ДГИНХ, 2011. –
92 с.
Рекомендовано к утверждению и к
изданию Учебно-методическим советом ДГИНХ
Проректор по учебной работе
ДГИНХ, председатель Учебнометодического совета, доктор экономических наук, профессор
Казаватова Н.Ю.
20 июня 2011 г.
Одобрено
кафедрой «Информационные
технологии»,
протокол № 9 от 14 мая 2011 г.
зав. кафедрой,
к.ф.-м.н., Галяев В.С.
Одобрено
Советом факультета
«Прикладная информатика (в экономике)»
Председатель Совета, к.э.н.,
доцент Раджабов К.Я.
11 июня 2011 г.
Печатается по решению Учебно-методического совета Дагестанского государственного института народного хозяйства.
2
Содержание
№
п/п
1.
2.
3.
4.
5.
6.
7.
8.
Тема и план лекций
Введение
Тема 1. Введение в предмет.
1. Понятие "искусственный интеллект". Основные термины и
определения.
2. Предпосылки и история возникновения интеллектуальных
информационных систем.
3. Правила формулировки условий задач и выбор модели решения.
Тема 2. Классификация интеллектуальных информационных систем.
1. Типизация и примеры информационных систем, основанных на использовании "искусственного интеллекта".
2. Функции интеллектуальных систем и их функциональная
классификация.
Тема 3. Представление знаний в интеллектуальных информационных системах.
1. Традиционные задачи искусственного интеллекта.
2. Классификация моделей представления знаний.
3. Языки представления знаний.
Тема 4. Представление знаний правилами: продукционная
модель.
1. Концепция продукционных систем.
2. Графы правил. Поиск на графе.
3. Управление выводом в продукционной системе.
Тема 5. Представление знаний фреймами и выводы.
1. Основы теории фреймов.
2. Свойства и основные параметры фреймов.
Тема 6. Семантические сети и онтологии.
1. Понятие семантической сети.
2. Онтологии.
3. Семантическая паутина.
Тема 7. Представление и использование нечётких знаний.
1. Нечёткость знаний.
2. Ненадёжные знания и выводы.
3. Неполные знания, немотонная логика и нечёткие выводы.
Тема 8. Работа со знаниями, представленными в текстовом
виде.
3
1. Гипертекстовые информационные технологии.
2. Информационно-поисковые системы.
3. Системы распознавания образов.
9. Тема 9. Понятие экспертной системы.
1. Определение экспертной системы.
2. Общая архитектура экспертных систем.
3. Классификация экспертных систем.
4. Характеристики экспертных систем
10. Тема 10. Этапы реализации экспертной системы.
1. Этапы разработки экспертных систем.
2. Участники процесса проектирования экспертной системы.
3. Особенности эксплуатации и режимы работы экспертной
системы.
Тема 11. Типы и инструментарий разработок экспертных
систем
1. Типы разработок ЭС
2. Основные инструментальные средства проектирования
экспертных систем.
11 Тема 12. Общие сведения о функциональном подходе к
программированию
1. История возникновения функционального программирования
2. Основы функционального программирования
Тема 13. История возникновения и классификация функциональных языков программирования
1. История функциональных языков
2. Классификация функциональных языков
Тема 14. Языки функционального программирования, их
свойства и решаемые задачи.
1 Языки функционального программирования
2 Свойства функциональных языков
3 Задачи, решаемые с использованием функциональных
языков
4
Введение
Учебное пособие по дисциплине «Функциональное программирование и интеллектуальные системы» предназначен для студентов, обучающихся по направлению «Бизнес-информатика», для ознакомления с проблематикой и областями использования искусственного интеллекта в
экономических информационных системах, освещения теоретических и
организационно-методических вопросов построения и функционирования систем, основанных на знаниях, привития навыков практических работ по проектированию баз знаний. В результате изучения учебного
пособия студенты получат знания по архитектуре и классификации
ИИС, методам представления знаний, областям применения, а также
научатся выбирать адекватные проблемные области, инструментальные
средства разработки ИИС и методы проектировании базы знаний.
«Функциональное программирование и интеллектуальные системы»
тесно взаимосвязан с такими дисциплинами учебного плана, как «Общая
теория систем», «Вычислительные системы, сети, телекоммуникации»,
«Программирование». Освоение данной дисциплины необходимо обучающемуся для успешного изучения следующих дисциплин: «Системы
поддержки принятия решений», «Управление жизненным циклом информационных систем», «Управление разработкой информационных систем»
и др. Все они совместно со специальными курсами предметной области
позволяют сформировать комплекс знаний и умений, необходимый для
решения его профессиональных задач.
Данная дисциплина преподается студентам 2 курса факультета
«Прикладная информатика (в экономике)», направления подготовки
080500 «Бизнес-информатика».
Трудоемкость дисциплины – 7 з.е. (252 часа):
Лекционная часть – 33 часа (17ч. + 16ч.);
Лабораторные занятия – 49 часов (17ч. + 32ч.);
Самостоятельная работа – 98 часов;
Курсовой проект;
Экзамен – 7.
Формы контроля.
Выполнение лабораторных и промежуточных контрольных работ;
Семестровая аттестация;
Подготовка и защита курсового проекта во 4-ом семестре;
Итоговый экзамен в конце 3-го и 4-го семестров.
Тема 1. Введение в предмет
План:
1.
Понятие "искусственный интеллект". Основные термины
и определения.
5
2.
3.
шения.
Предпосылки и история развития ИИС.
Правила формулировки условий задач и выбор модели ре-
1. Понятие "искусственный интеллект". Основные термины и
определения.
Понятие "искусственный интеллект" многогранно, и разные авторы
дают разные определения.
Искусственный интеллект – это метафорическое понятие для обозначения системы созданных людьми средств, воспроизводящих определенные функции человеческого мышления. (Философский словарь)
Искусственный интеллект – это искусственная система, имитирующая решение человеком сложных задач. (Энциклопедический словарь по
информатике)
Определение, которого мы будем придерживаться в нашем курсе:
Искусственный интеллект – это программная система, имитирующая на
компьютере мышление человека.
Программы, реализующие элементы искусственный интеллекта, называют интеллектуальными информационными системами (ИИС).
Система считается интеллектуальной, если в ней реализованы следующие три базовые функции.
1.
Функция представления и обработки знаний. Интеллектуальная система должна быть способна накапливать знания об окружающем
мире, классифицировать и оценивать их с точки зрения прагматики и непротиворечивости, инициировать процессы получения новых знаний, соотносить новые знания со знаниями, хранящимися в базе знаний.
2.
Функция рассуждения. Интеллектуальная система должна быть
способна формировать новые знания с помощью логического вывода и
механизмов выявления закономерностей в накопленных знаниях, получать обобщенные знания на основе частных знаний и логически планировать свою деятельность.
3.
Функция общения. Интеллектуальная система должна быть
способна общаться с человеком на языке, близком к естественному языку
(ЕЯ) и получать информацию через каналы, аналогичные тем, которые
использует человек при восприятии окружающего мира (прежде всего,
зрительный и звуковой). Также система должна уметь формировать «для
себя» или по просьбе человека объяснения собственной деятельности (т. е.
отвечать на вопросы типа «Как я это сделал?»), оказывать человеку помощь за счет знаний, которые хранятся в ее памяти, и логических средств
рассуждения.
Основная цель ИИС – это реализовать информационный процесс
максимально приближено к мыслительному процессу человека. Целями
6
интеллектуальных информационных технологий являются, во-первых,
расширение круга задач, решаемых с помощью компьютеров, особенно в
слабоструктурированных предметных областях, и, во-вторых, повышение
уровня интеллектуальной информационной поддержки современного специалиста.
Так как интеллект присущ только человеку, а интеллект – это есть
совокупность знаний и навыков их обработки, то для создания ИИС мыслительные процессы формализуются, раскладываются на простейшие
операции и их связки, а затем программируются исходя из особенностей
задачи и выбранного языка программирования.
2. Предпосылки и история развития ИИС.
Искусственный интеллект (ИИ) как научное направление, связанное
с попытками формализовать мышление человека, имеет длительную историю. Еще Платон, Аристотель, Р. Декарт, Г.В. Лейбниц, Дж. Буль и многие другие исследователи на уровне современных им знаний стремились
описать мышление как совокупность некоторых элементарных операций,
правил и процедур. Перечислим самые значимые вехи в эволюции научной мысли, оказавшие влияние на развитие идей интеллектуальных информационных систем. В начале XVII века Рене Декарт предположил, что
животное – некий сложный механизм, тем самым сформулировав механистическую теорию. В 1910-1913 гг. Бертран Рассел и А. Н. Уайтхед опубликовали работу «Принципы математики», которая произвела революцию
в формальной логике. В 1941 Конрад Цузе построил первый работающий
программно-контролируемый компьютер. Качественно новый период развития искусственного интеллекта связан с появлением в научных лабораториях ЭВМ и с публикацией книги Н. Винера "Кибернетика или управление и связь в животном и машине" появившейся еще ранее книги У.
Росс Эшби "Введение в кибернетику".Уоррен Маккалок и Валтер Питтс в
1943 опубликовали A Logical Calculus of the Ideas Immanent in Nervous
Activity, который заложил основы нейронных сетей.
В нашей стране идеи создания ИИ получили признание после выхода целой серии переводных работ Н. Винера, У. Росс Эшби, Ст. Бира и Э.
Беркли в конце 1950-х – начале 1960-х годов прошлого века и нашего соотечественника Берга.
Большинство работ на этапе зарождения систем искусственного интеллекта было посвящено исследованию моделирования рассуждений, это
одно из самых развитых направлений. Моделирование рассуждений подразумевает создание символьных систем, на входе которых поставлена
некая задача, а на выходе требуется её решение. Как правило, предлагаемая задача уже формализована, то есть переведена в математическую
форму, но либо не имеет алгоритма решения, либо он слишком сложен,
7
трудоёмок и т. п. В это направление входят: доказательство теорем, принятие решений и теория игр, планирование и диспетчеризация, прогнозирование.
Также весьма развитым направлением, которому придаётся большое
значение, является обработка естественного языка, в рамках которого
проводится анализ возможностей понимания, обработки и генерации текстов на «человеческом» языке. Первоначально это направление связано с
проблемой качественного машинного перевода текстов с одного языка на
другой. С развитием информационных технологий, и в частности Internet,
большое значение получила разработка методов информационного поиска.
В последние годы на первый план выходит инженерия знаний, объединяющая задачи получения знаний из простой информации, их систематизации и использования. Это направление охватывает большой спектр
задач, самым важными являются две из них, решению которых посвящено
большое количество теоретических и практических работ. Первая – машинное обучение – касается процесса самостоятельного получения знаний
интеллектуальной системой в процессе её работы. Вторая – создание экспертных систем – программ, использующих специализированные базы
знаний для получения достоверных заключений по какой-либо проблеме.
Большие и интересные достижения имеются в области моделирования биологических (имеющих биологические аналоги) систем. Нейронные
сети используются для решения нечётких и сложных проблем, таких как
распознавание геометрических фигур или кластеризация объектов. Генетический подход основан на идее, что некий алгоритм может стать более
эффективным, если позаимствует лучшие характеристики у других алгоритмов («родителей»). Относительно новый подход, где ставится задача
создания автономной программы — агента, взаимодействующего с внешней средой, называется агентным подходом, одним из подтипов которого
является "муравьиный интеллект", когда совокупность агентов с "низким"
интеллектом образует высокоинтеллектуальную систему.
На стыке робототехники и искусственного интеллекта также возникает ряд интересных задач, направленных на создание интеллектуальных
роботов. Сюда, в частности входят, задачи распознавания образов: текстов, звуков, символов и компьютерное зрение.
Отдельным направлением является "машинное творчество", здесь
поставлены проблемы написания компьютером музыки, литературных
произведений (стихов, сказок), художественное творчество.
Огромное количество практических приложений, таких как, программирование интеллекта в компьютерных играх, нелинейное управление, интеллектуальные системы безопасности, порождает отдельные в исследованиях искусственного интеллекта. Таким образом, эта наука про8
должает интенсивно развиваться, появляются новые направления исследований, разрабатываются прикладные задачи и приложения.
Пока ни одна исследовательская группа ни в одном из направлений
не подошла в плотную к воплощению искусственного интеллекта на
практике, но исследования в области искусственного интеллекта влились
в общий поток технологий сингулярности (видового скачка), таких как
нанотехнология, молекулярная биоэлектроника, квантовая теория и т. д.
Приведём примеры наиболее впечатляющих систем искусственного
интеллекта, реализованных на практике, информация о которых не является засекреченной:
Deep Blue – суперкомпьютер со специальной архитектурой и
ПО – победил чемпиона мира по шахматам. Оригинальные компактные
шахматные программы прочно завоевали рынок интеллектуальных игр.
На основе этой линий суперкомпьютеров IBM были созданы системы молекулярное моделирование и моделирование системы пирамидальных
клеток в швейцарском центре Blue Brain.
Mycin — одна из ранних экспертных систем, которая могла диагностировать небольшой набор заболеваний, причем часто так же точно,
как и доктора. Получила большую популярность, стала примером грамотного воплощения идей искусственного интеллекта на практике.
ViaVoice – система распознавания речи – способна обслуживать потребителей. В последнее время появляется большое количество
коммерческих аналогов.
Роботы в ежегодном турнире RoboCup соревнуются в упрощённой форме футбола. Самым известным является робот японских производителей Akme.
Банки применяют системы искусственного интеллекта в страховой
деятельности (актуарная математика) при игре на бирже и управлении
собственностью. В августе 2001 года роботы выиграли у людей в импровизированном соревновании по трейдингу. Методы распознавания образов, (включая, как более сложные и специализированные, так и нейронные
сети) широко используют при оптическом и акустическом распознавании
(в том числе текста и речи), медицинской диагностике, спам-фильтрах, в
системах ПВО (определение целей), а также для обеспечения ряда других
задач национальной безопасности.
Разработчики компьютерных игр вынуждены применять ИИ той или
иной степени проработанности. Стандартными задачами ИИ в играх являются нахождение пути в двухмерном или трёхмерном пространстве,
имитация поведения боевой единицы, расчёт верной экономической стратегии и так далее.
На текущем этапе развития информационных технологий намечены
2 стратегических направления развития систем искусственного интеллек9
та:
1.
решение проблем, связанных с приближением специализированных систем ИИ к возможностям человека и их интеграции, которая будет реализована на основе закономерностей природы человека;
2.
создание искусственного разума, представляющего интеграцию
уже созданных систем ИИ в единую систему, способную решать проблемы человечества.
3. Правила формулировки условий задач и выбор модели решения.
При проектировании модели представления знаний следует учитывать такие факторы, как однородность представления и простота понимания. Однородное представление приводит к упрощению механизма управления логическим выводом и упрощению управления знаниями. Представление знаний должно быть понятным экспертам и пользователям системы. А противном случае затрудняются приобретение знаний и их оценка. Однако выполнить это требование в равной степени как для простых,
так и сложных задач довольно трудно. Обычно для несложных задач останавливаются на некотором среднем (компромиссном) представлении, но
для решения сложных и больших задач необходимы структурирование и
модульное представление.
В современной теории интеллектуальных информационных систем
выделены девять ключевых требований к эффективным моделям представления знаний:
1.
общность (универсальность);
2.
«психологичность», наглядность представления знаний;
3.
однородность;
4.
реализация в модели свойства активности знаний;
5.
открытость базы знаний;
6.
возможность отражения в базы знаний структурных отношений
объектов предметной области;
7.
наличие механизма «проецирования» знаний на систему семантических шкал;
8.
возможность оперирования нечеткими знаниями;
9.
использование многоуровневых представлений (данные, модели, метамодели и т.д.).
Тема 2. Классификация интеллектуальных информационных
систем
План:
1.
Типизация и примеры применения информационных систем, основанных на использовании "искусственного интеллекта".
10
2.
Функции интеллектуальных систем и их функциональная
классификация.
1. Типизация и примеры применения информационных систем,
основанных на использовании "искусственного интеллекта".
Применение искусственного интеллекта для усиления коммуникативных способностей информационных систем привело к появлению систем с интеллектуальным интерфейсом, среди которых можно выделить
следующие типы разработок:
1. Разработка интеллектуальных информационных систем или систем, основанных на знаниях. Это одно из главных направлений ИИ. Основной целью построения таких систем являются выявление, исследование и применение знаний высококвалифицированных экспертов для решения сложных задач, возникающих на практике. При построении систем,
основанных на знаниях, используются знания, накопленные экспертами в
виде конкретных правил решения тех или иных задач. Это направление
преследует цель имитации человеческого искусства анализа неструктурированных и слабоструктурированных проблем. В данной области исследований осуществляется разработка моделей представления, извлечения и
структурирования знаний, а также изучаются проблемы создания баз знаний, образующих ядро интеллектуальной информационной системы. Частным случаем систем, основанных на знаниях, являются экспертные системы.
2. Естественно-языковой интерфейс. Применяется для доступа к
интеллектуальным базам данных, контекстного поиска документальной
текстовой информации, голосового ввода команд в системах управления,
машинного перевода с иностранных языков. Для реализации естественноязыкового интерфейса необходимо решить проблемы морфологического,
синтаксического и семантического анализа, а также задачу синтеза высказываний на естественном языке. При морфологическом анализе осуществляются распознавание и проверка правильности написания слов в словаре.
Синтаксический контроль предполагает разложение входных сообщений
на отдельные компоненты, проверку соответствия грамматическим правилам внутреннего представления знаний и выявление недостающих частей.
Семантический анализ обеспечивает установление смысловой правильности синтаксических конструкций. В отличие от анализа синтез высказываний заключается в преобразовании цифрового представления информации
в представление на естественном языке.
3. Гипертекстовые системы. Используются для реализации поиска
по ключевым словам в базах данных с текстовой информацией. Для более
полного отражения различных смысловых отношений терминов требуется
сложная семантическая организация ключевых слов. Решение этих задач
11
осуществляется с помощью интеллектуальных гипертекстовых систем, в
которых механизм поиска сначала работает с базой знаний ключевых
слов, затем – с самим текстом. Аналогичным образом проводится поиск
мультимедийной информации, включающей кроме текста графическую
информацию, аудио- и видеообразы.
4. Системы контекстной помощи. Относятся к классу систем распространения знаний. Такие системы являются, как правило, приложениями к документации. Системы контекстной помощи – частный случай
гипертекстовых и естественно-языковых систем. В них пользователь описывает проблему, а система на основе дополнительного диалога конкретизирует ее и выполняет поиск относящихся к ситуации рекомендаций. В
обычных гипертекстовых системах наоборот, компьютерные приложения
навязывают пользователям схему поиска требуемой информации.
5. Обработка визуальной информации и системы когнитивной графики. В этом научном направлении решаются задачи обработки, анализа и
синтеза изображений. Задача обработки изображений связана с трансформированием графических образов, результатом которого являются новые
изображения. В задаче анализа исходные изображения преобразуются в
данные другого типа, например в текстовые описания. При синтезе изображений на вход системы поступает алгоритм построения изображения, а
выходными данными являют графические объекты (системы машинной
графики). Системы когнитивной графики ориентированы на общение с
пользователем ИИС посредством графических образов, которые генерируются в соответствии с изменениями параметров моделируемых или наблюдаемых процессов. Когнитивная графика позволяет в наглядном и выразительном виде представить множество параметров, характеризующих
изучаемое явление, освобождает пользователя от анализа тривиальных ситуаций, способствует быстрому освоению программных средств и повышению конкурентоспособности разрабатываемых ИИС. Применение когнитивной графики особенно актуально в системах мониторинга и оперативного управления, в обучающих и тренажерных системах, в оперативных системах принятия решений, работающих в режиме реального времени.
6. Генерация и распознавание речи. Системы речевого общения создаются в целях повышения скорости ввода информации ЭВМ, разгрузки
зрения и рук, а также для реализации речевого общения на значительном
расстоянии. В таких системах под текстом понимают фонемный текст (как
слышится).
7. Распознавание образов. Это одно из самых ранних направлений
ИИ, в котором распознавание объектов осуществляется на основании
применения специального математического аппарата обеспечивающего
отнесение объектов к классам, а классы описываются совокупностями оп12
ределенных значений признаков.
8. Обучение и самообучение. Эта актуальная область ИИ включает
модели, методы и алгоритмы, ориентированные на автоматическое накопление и формирование знаний с использованием процедур анализа и
обобщения данных. К данному направлению относятся не так давно появившиеся системы добычи данных: системы поиска закономерностей в
компьютерных базах данных.
9. Игры и машинное творчество. Машинное творчество охватывает
сочинение компьютерной музыки, стихов, интеллектуальные системы для
изобретения новых объектов. Создание интеллектуальных компьютерных
игр является одним из самых развитых коммерческих направлений в сфере разработки программного обеспечения. Кроме того, компьютерные игры предоставляют мощный арсенал разнообразных средств, используемых
для обучения.
2. Функции интеллектуальных систем и их функциональная
классификация.
Коммуникативная функция характеризует способность и способ
взаимодействия (интерфейса) конечного пользователя с системой, в частности, возможность формулирования произвольного запроса в диалоге с
ИИС на языке, максимально приближение к естественному. По степени
реализации коммуникативной функции ИИС классифицируются следующим образом:
а) Интеллектуальные базы данных;
б) Естественно-языковой интерфейс;
в) Гипертекстовые системы;
г) Системы контекстной помощи;
д) Когнитивная графика.
Экспертная функция, когда ИИС заменяет специалиста-человека в
некоторой узконаправленной области. Такие системы называют экспертными системами, они требуют построения оригинального алгоритма решения в зависимости от конкретной ситуации, характеризующейся неопределенностью и динамичностью исходных данных и знаний. По степени
реализации этой функции выделяют следующие системы.
а) Классифицирующие;
б) Доопределяющие;
в) Трансформирующие;
г) Мультиагентные.
Функция самообучения – это заложенное в систему умение извлекать знания из накопленного опыта и применять их для решения задачи.
а) Индуктивные системы;
б) Нейронные сети;
13
в) Системы, основанные на прецедентах;
г) Информационные хранилища.
Адаптивная функция – способность системы к развитию в соответствии с объективными изменениями области знаний.
а) САSЕ-технологии;
б) Компонентные технологии.
Одна и та же ИИС может быть классифицирована по каждой из
функций. Чаще всего в ИИС могут быть реализованы лишь некоторые
функции.
Тема 3. Представление знаний в интеллектуальных информационных системах
План:
1.
Традиционные задачи ИИ.
2.
Классификация моделей представления знаний.
3.
Языки представления знаний.
1. Традиционные задачи ИИ.
1. Программы решения отдельных интеллектуальных задач
1.1. Программы компьютерного доказательства теорем
1.2. Игровые программы
1.3. Распознающие и узнающие программы
1.4. Программы для семантического анализа и обработки естественно-языковой информации
a)
Машинный поиск в базах данных естественно-языковых документов
b)
Машинный перевод
c)
Автоматическое реферирование
d)
Автоматическая классификация документов
e)
Генерация (синтез) текста
f)
Генерация (синтез) речи
1.5. Программы, моделирующие поведение
1.6. Программы для анализа и синтеза музыкальных произведений
2. Работа со знаниями
2.1. Реализация методов и средств представления знаний, используя
различные модели знаний. Составление систем представления знаний и
баз знаний.
2.2. Реализация методы и средств извлечения знаний (приобретение
знаний от экспертов, извлечение знаний из документов, согласование и
интеграция знаний)
2.3. Реализация методы обработки знаний (поиск и верификация
знаний, систематизация знаний. вывод на знаниях, обработка нечетких
14
знаний, аргументация и объяснение на основе знаний)
3. Интеллектуальное программирование
3.1. Автоматический синтез программ
3.2. Интеллектуальные интерфейсы и инструментальные средства
4. Интеллектуальные автоматизированные системы
4.1. Нейропакеты или нейросети
4.2. Интеллектуальные информационные системы
4.3. Экспертные системы
4.4. Интеллектуальные автоматизированные системы управления
4.5. Интеллектуальные системы автоматизированного проектирования
4.6. Интеллектуальные автоматизированные системы научных исследований
4.7. Интеллектуальные компьютерные средства обучения
4.8. Интеллектуальные роботы
4.9. Интеллектуальные консультирующие системы
4.10. Системы управления знаниями
4.11. Системы виртуальной реальности
2. Классификация моделей представления знаний.
Для решения сложных задач с привлечением искусственного интеллекта, в каждом конкретном случае выбирается собственное представление данных и знаний. Но подавляющее большинство интеллектуальных
систем имеют в своей основе некоторую базовую модель представления
данных и знаний. Типичными базовыми моделями представления знаний
являются: логическая, продукционная, фреймовая, семантическая сеть.
Логическая модель использует представления знаний в системе логики предикатов первого порядка и выведения заключений с помощью
силлогизма. Другими словами используются правильно построенные логические формулы, содержащие одну или несколько неизвестных, при
подстановке значений которых формула принимает значение "ложь" или
"истина". Силлогизм – это такое объединение двух логических формул,
при котором можно сделать новый вывод на основе двух уже имеющихся.
Отличительной чертой логических моделей является однозначность теоретического обоснования и возможность реализации системы формально
точных определений и выводов. По этой причине логические модели являются удобным инструментом в теоретических исследованиях по построению искусственного интеллекта. Однако, на практике большинство
воплощённых систем реализуют неформальную логику, которая может
противоречить здравому смыслу, но при этом сохраняет возможность саморазвития и самообучения. Другими словами, для реализации "человеческой" логики используются методы четкой логики, но с различными эле15
ментами неформальной логики (модальная логика, многозначная и т.д.)
Продукционные системы – это модели представления знаний, основанные на совокупности правил вида "Если – То". В свою очередь, продукционные системы делятся на два класса: с прямыми выводами (например, медицинские, диагностические системы) и обратными выводами
(системы проектирования). В системе продукции с помощью правил строится дерево И/ИЛИ, связывающее в единое целое факты и заключения.
Оценка этого дерева на основании фактов, имеющихся в базе данных, и
есть логический вывод. Логические выводы бывают прямыми, обратными
и двунаправленными. При прямом выводе отправной точкой служат предоставленные данные, процесс оценки приостанавливается в узлах с отрицанием. Для такого подхода характерно большое количество данных, а
также оценок дерева, не имеющих прямого отношения к заключению, что
приводит к излишним машинным затратам. Преимущество обратных выводов в том, что оцениваются только те части дерева, которые имеют
отношение к заключению, однако если отрицание или утверждение
невозможны, то порождение дерева лишено смысла. В двунаправленных
выводах сначала оценивается небольшой объем полученных данных и
выбирается гипотеза (по примеру прямых выводов), а затем запрашиваются данные, необходимые для принятия решения о пригодности данной
гипотезы. На основе этих выводов можно реализовать более мощную и
гибкую систему.
Продукционные системы включают три компонента: базу правил,
состоящую из набора продукций (правил вывода), базу данных, содержащую множество фактов, и интерпретатор для получения логического
вывода на основании этих знаний. База правил и база данных образуют
базу знаний, а интерпретатор соответствует механизму логического вывода. Вывод выполняется в виде цикла «понимание – выполнение», причем в каждом цикле выполняемая часть выбранного правила обновляет
базу данных. В результате содержимое базы данных преобразуется от
первоначального к целевому, т. е. целевая система синтезируется в базе
данных. Однако, многократные проходы по дереву рассуждений и сравнение с образцами в базе правил, существенно замедляют процесс принятия решения, поэтому продукционные системы не годятся для решения
крупномасштабных задач.
Достоинства продукционных систем: простота создания и понимания отдельных правил; простота пополнения и модификации; простота
механизма логического вывода. Недостатки: неясность взаимного отношения правил; сложность оценки целостного образа знаний; крайне низкая эффективность обработки; существенное отличие от человеческой
структуры знаний; отсутствие гибкости в логическом выводе.
Для устранения недостатков продукционной модели при разработке
16
сложных задач используется группировка знаний и структурирование базы данных. При этом связанные правила группируются и для них формируются ограниченные диапазоны значений, что существенно снижает вероятностный перебор.
Расширенным вариантом модели правил является модель доски
объявлений (blackboard – классная доска), которая наиболее активно используется в системах распознавания разговорной речи. В центральной
части, называемой доской объявлений, иерархически определены гипотезы: на самом верхнем уровне находятся заключения, на самом нижнем –
факты, на промежуточных уровнях – промежуточные гипотезы. Для речевых полнотекстовых анализаторов, использующих ввод речи в виде
сигналов временного ряда, определяются следующие уровни гипотез
(сверху вниз0: "предложение" – "часть предложения" – "отдельное слово"
– "слог" – "фонема". Вокруг доски объявлений расположены сгруппированные правила продукций, которые называются источниками знаний,
они действуют на соответствующих уровнях гипотез или между уровнями. Действие модели происходит в двух направлениях. Снизу вверх
формируются гипотезы верхних уровней, которые затем на самом верхнем уровне формируют полное предложение системы. Сверху вниз могут
использоваться семантические знания исследуемой области, чтобы отсекать ошибочные гипотезы, которые имеют большой уровень достоверности из-за возможных ошибок в исходных фактах или нечеткости промежуточных правил продукции и не могут быть отсечены прямым путем.
Таким образом, модель доски объявлений играет роль своеобразного канала связи между источниками знаний. Преимуществом модели является
четкость определения функций каждого источника знаний, что позволяет
систематизировать знания и повысить эффективность их использования.
Основной проблемой модели является проблема запуска источника знаний, т.е. в какой очередности источники знаний должны быть использованы на исходном наборе фактов. Эта проблема решается двумя методами:
1.
"планировщик" – специальный модуль отслеживает положение дел на доске объявлений и вызывает определенный источник знаний;
2.
"цепочка" – когда завершивший работу источник знаний сам
выбирает следующего "исполнителя".
В обоих случаях существует ряд проблем, математического характера о правилах выбора, поэтому довольно часто доску объявлений комбинируют с фреймовой моделью.
Фреймовая модель основывается на фреймовой теории М.Минского
и представляет собой систематизированную в виде единой теории психологическую модель памяти человека и его сознания. Модель представляет
собой единую систему, в которой объединены декларативные и процедур17
ные знания, которые распределены по взаимосвязанным фреймам. В свою
очередь фреймы разбиваются на конкретные слоты, содержащие узкоспециализированные знания.
На практике фреймовая модель часто реализуется в виде иерархической структуры данных с модульным представлением знаний в виде определенных форматов. Каждый модуль-фрейм описывает один концептуальный объект, конкретные свойства этого объекта и факты, относящиеся
к нему, описываются в слотах. В слот могут быть подставлены различные
данные соответствующего формата. Вывод осуществляется специальной
процедурой вывода, которая называется присоединённой процедурой и
используется как отдельный слот. Работа фреймовой системы организуется следующим образом: сначала запускается одна из присоединённых
процедур выбранного фрейма, затем, исходя из алгоритма обработки знаний, посылаются сообщения следующему фрейму, которые запускают
очередную присоединённую процедуру, и так далее по цепочке.
Преимуществом фреймовой модели является то, что позволяет применять различные способы вывода полученных знаний, в зависимости от
ситуации. Также модель позволяет описывать сложно-структурированные
понятия и задачи. К недостаткам следует отнести высокую трудоемкость
подготовки данных, а также сложность управления завершенностью и сохранения целостности, так как есть высокая вероятность нарушения присоединённых процедур даже при незначительных ошибках в начальных
данных.
Модель семантической сети – это модель представления знаний на
основе метода семантической сети. Семантической сетью называется
структура данных, которая имеет определённый смысл именно как целостный образ сети, узлы которой соответствуют понятиям и объектам, а дуги – отношениям между объектами. Вершинам и дугам присваиваются
имена (идентификаторы) и описания, характеризующие значения объектов и отношений внутри предметной области.
Учет особенностей объектов и отношений, заданных их типами,
обеспечивает возможность применения тех или иных классов выводов на
сети и получения конкретного результата на одном и том же наборе фактов. Приведем несколько примеров различно направленных сетевых моделей:
1.
Если дуги сети выражают родовидовые отношения, то такая
сеть определяет классификацию объектов предметной области.
2.
Если в сети дуги образуют причинно-следственные отношения,
то сеть можно интерпретировать как сценарий.
3.
Построение сети на ассоциативных отношениях формирует ассоциативную структуру понятий рассматриваемого фрагмента предметной
области.
18
При практическом использовании семантических сетей для представления знаний решающее значение имеют унификация типов объектов
и выделение базовых видов отношений между ними.
К достоинствам сетевой модели можно отнести ее высокую общность, наглядность отображения системы знаний о предметной области, а
также легкость понимания подобного представления.
Недостатки сетевой модели являются прямым продолжением её достоинств: так как в семантической сети имеет место смешение групп знаний, относящихся к различным ситуациям, то это существенно усложняет
интерпретацию знаний. Другая проблема, присущая сетевой модели, которая зачастую ограничивает её практическое применение, состоит в
трудности унификации процедур вывода и механизмов управления выводами на сети.
Перспективным направлением повышения эффективности сетевого
представления, развиваемым в настоящее время, является использование
онтологии и параллельных выводов на семантических сетях. Быстрое развитие онтологического подхода в последние годы обусловлено распространением Intemet-технологий, использующих онтологические модели.
Объектно-ориентированная модель знаний получила широкое применение в современных технологиях проектирования разнообразных программных и информационных систем. В настоящее время существуют два
основных подхода к моделированию знаний, базирующихся на объектных
технологиях. Это модель MDA (Model Driven Architecture) консорциума
Object Management Group (OMG) и модель ODP (Model of Open Distributed
Processing), зафиксированная в стандарте ISO/ITU.
Модель MDA включает четыре концептуальных уровня: На нижнем,
нулевом, уровне представляются данные об объектах моделируемой
предметной области. На первом уровне на базе знаний об объектах нулевого уровня располагаются модели, каждая из которых соответствует определенной точке зрения на предметную область – так называемые области интересов. Второй уровень занимают метамодели, которые определяют
методики и способы описания моделей первого уровня. На третьем уровне
находится единственная метаметамодель, не зависящая от областей интересов.
Модель ODP включает три уровня. Нулевой уровень содержит данные об объектах моделируемой предметной области. На следующем уровне располагаются модели, определяющие способ описания объектов нулевого уровня. Все модели первого уровня построены с помощью одних и
тех же средств моделирования, которые определяются метамоделью второго уровня, которая содержит единственную метамодель. Помимо моделей первый уровень содержит представления (viewpoints), соответствующие различным точкам зрения на предметную область. Стандарт ODP оп19
ределяет пять возможных видов представлений: корпоративное
(enterprise),
информационное
(information),
вычислительное
(computational), разработчиков (engineering), технологическое (technology).
Вся структура этого стандарта имеет строгую унификацию, т.е. правила
представления всех объектов и связей между ними.
Таким образом, модель MDA описывает предметную область непосредственно, а модель ODP – опосредовано, через связь представлений и
моделей. Преимуществом второго подхода является возможность установления связей между разными представлениями для одной предметной
области. Недостатком – относительно высокая вероятность потери данных
при переходе от моделей к представлениям.
Класс специальных моделей знаний объединяет модели, отражающие особенности представления знаний и решения задач в отдельных, относительно узких предметных областей. В качестве примера подобного
способа формализации знаний можно привести модель представления
предметной области «объект-признак», используемую в автоматизированных системах поиска аналогов и построения классификаций.
Применение на практике того или иного способа формализации обусловливается спецификой задачи, для решения которой планируется использовать БЗ. По мнению специалистов наиболее перспективны смешанные или комплексные модели, интегрирующие преимущества рассмотренных выше базовых моделей представления предметной области. Особенно это актуально для корпоративных и промышленных систем искусственного интеллекта.
Ни одна из рассмотренных моделей знаний не удовлетворяет всем
девяти требованиям, предъявляемым к интеллектуальным информационным системам, поэтому ведутся активные исследования по вопросу разработки методики построения комплексных многоуровневых моделей представления предметной области, обеспечивающих возможность реализации
свойств, соответствующих указанным требованиям.
3. Языки представления знаний.
Языки представления знаний являются узкоспециализированными.
Они занимают промежуточное положение между моделями представления
данных и универсальными языками программирования. В теории языки
представления данных строятся по специальным правилам, в зависимости
от модели представления данных, для которой они разрабатываются. Однако, на практике такой подход достаточно сложно реализовать, та как
многие языки подразумевают семантическое и синтаксическое наполнение, которые трудно поддаются формализации и перенос в машинные команды. Поэтому на практике реализуются следующие 3 подхода:
1 подход. Метод прямой разработки с использованием универсаль20
ного языка программирования. При этом сначала разрабатываются специальные механизмы управления базами знаний, затем конструирование и
внедрение специфических функций, характерных для выбранной предметной области, а затем реализация всей системы в целом. Такой подход
требует больших затрат времени и ресурсов, он подходит для относительно простых систем.
2 подход. Предполагает использование языка представления знаний
или языка разработки экспертных систем. Подразумевает наличие специальной оболочки языка, которая позволяет существенно сократить время
разработки системы. Наиболее часто применяется при создании экспертных систем на основе систем продукции.
3 подход. Метод с использованием языка представления знаний
фреймового типа. Так как фреймовая модель обладает большой гибкостью
и объединяет в себе процедурные и декларативные знаний в совокупности
информационных единиц – фреймов, то в этом подходе основной решаемой задачей является выбор и построение правильной иерархической
структуры. В связи с тем, что при составлении программы требуется обладать специфическими знаниями по исследуемой проблематике, то ещё
одной проблемой этого метода является то, что языки этого типа ориентированы на специалистов в области инженерии знаний. Эти языки являются специфичными в работе и имеют характер универсальных языков более
высокого типа, чем обычные языки программирования искусственного
интеллекта.
Системы обработки знаний в большинстве своём бывают написаны
на специальных языках искусственного интеллекта типа LISP или
PROLOG. Однако, в последнее время для сокращения времени исполнения экспертных систем используются универсальные высокоуровневые
языки: C, Delphi, Java (для распределенных систем). Уровень взаимодействия современных языков высокого уровня с базами данных, их гибкость
и возможности объектно-ориентированного программирования позволяет
реализовать на практике достаточно сложные системы. В данном случае
особую роль приобретает их правильное концептуальное проектирование.
Тема 4. Представление знаний правилами: продукционная модель.
План:
1.
Концепция продукционных систем.
2.
Графы правил. Поиск на графе.
3.
Управление выводом в продукционной системе.
1. Концепция продукционных систем.
Продукционные системы являются наиболее распространёнными
21
среди интеллектуальных информационных систем. Они встречаются не
только в чистом виде, но и локально в составе информационных систем,
которые в целом построены по другой технологии, например, как составная часть описания фреймов.
Популярность продукционных систем обусловлена следующими
факторами:
1.
С точки зрения человека: всем элементам системы можно придать четкий, ясный смысл;
2.
С точки зрения вычислительной машины: имеется возможность
определения простого и точного механизма использования знаний с высокой однородностью представления с единым синтаксисом.
3.
С точки зрения алгоритма работы: простота дополнения, модификации и аннулирования правил.
Продукционная модель состоит из трёх основных компонент:
1.
База правил – это база знаний, содержащая наборы правил, составленных с использованием определенного синтаксиса;
2.
Рабочая память (память кратковременного хранения) содержит
предпосылки (данные, наборы фактов), касающиеся конкретных задач
предметной области, а также результаты выводов, полученных на этих
данных.
3.
Механизм логического вывода использует правила в соответствии с содержимым рабочей памяти.
Данные, записанные с соблюдением синтаксиса и содержащие некоторые утверждения, называются образцами. Правила, накапливаемые на
основе базы правил, отражают содержимое рабочей памяти. В их условной части (ЕСЛИ) находятся либо одиночные образцы, либо несколько
условий, соединённых предлогом "И", а в заключительной части (ТО) –
образцы, дополнительно регистрируемые в рабочей памяти.
Продукционная система предусматривает два различных алгоритма
работы механизма вывода.
Прямой алгоритм. Исходные данные переводятся в формат образцов
и записываются в рабочую память. Механизм вывода сопоставляет образцы из условной части правила с образцами, хранимыми в рабочей памяти.
Если все образцы имеются в рабочей памяти, то условная часть считается
истинной, в противном случае – ложной. Последовательно проверяя все
правила, определяются истинные, их заключительные части заносятся в
рабочую память. Затем повторяется повтор проверки правил, при этом
правила уже прошедшие отбор, не проверяются (и не заносятся) второй
раз. В итоге приходим к ситуации, когда правил, которые можно применить, не остаётся – система останавливается. Также в качестве точки останова используется проверка достижения некоторого условия (т.е. попадание в рабочую память некоторого образца).
22
Обратный алгоритм. Исходные факты также записываются в рабочую память в формате образцов. После этого в виде образца записывается
конечная цель. При этом исследуется возможность, применяя правила,
чтобы подтвердить имеющиеся факты, и на основе заключений придти к
конечной цели. В этом случае система останавливается либо когда достигается первоначальная цель (цель подтверждена), либо когда кончаются
правила, которые можно применить (цель не достигнута). Во многих случаях обратный метод позволяет исключать в процессе перебора правила,
не имеющие отношения к заданной цели, что повышает эффективность
системы.
Также применяют смешанный или двунаправленный метод, включающий прямой метод для нахождения всевозможных достижимых целей
и выбора некоторой гипотезы, и обратный метод для подтверждения выбранной гипотезы.
Методика выбора очередного правила при их переборе существенно
влияет на эффективность системы. Множество правил, удовлетворяющих
текущему набору образцов, называют конфликтным набором, а выбор одного из них – разрешением конфликта. Для разрешения конфликта выбирается или разрабатывается математический аппарат на основе теории
графов.
На практике очень часто применяются системы, построенные не
простых образцах, а на триплетах "объект-атрибут-значение", которые позволяют уточнить смысл того или иного рассматриваемого объекта. Такой
подход получил ещё большее распространение в рамках объектноориентированного программирования. При таком подходе можно применять правила, касающиеся как всех объектов данного типа, так и правила,
затрагивающие только определённые подвиды, характеризуемые значениям атрибутов. В этом случае каждое правило применяется не один раз за
всю сессию работы системы, а не более одного раза для каждого объекта.
Учет использованных для каждого объекта правил называется проблемой
контекста применения. Так как в системах продукций для оценки условной части правил необходим поиск содержимого рабочей памяти, а применение триплетов позволяет его существенно облегчить, то возрастает
общая эффективность системы.
Триплеты могут быть дополнены ещё одним показателем – коэффициентом уверенности. Это позволяет создавать системы с нечеткой логикой или системы с показателем нечеткости.
В системах, где необходимо не только определить наличие определенного образца или объекта, соответствующего ему, но и найти значение
атрибута этого объекта или проверить принадлежность значения атрибута
некоторой категории, вводятся так называемые предикаты – специальные
структуры, для описания указанных условий.
23
В практической реализации продукционных системах особенно важную роль играет реализация функций ввода исходных данных, а также
возможности получения промежуточных ответов. Это позволяет организовать удобный диалог между человеком и машиной, что особенно важно,
например, в консультационных системах.
2. Графы правил. Поиск на графе.
Как было сказано выше, по определению классические правила являются конструкциями ЕСЛИ-ТО с простыми (одинарными) условиями
или с условиями, соединёнными связкой И. На практике это требование
расширяют введением связки ИЛИ, дополнительными вычислениями в
условной части, а также заключительная часть может достигаться без дополнения рабочей памяти. Классические правила представляют собой отношение вывода, установленное между содержимым рабочей памяти,
ссылка на которое осуществляется из условной части, и содержимым, указываемым в заключительной части. Визуально такое отношение можно
представить в виде графа с древовидной структурой. Расширенные правила представляют в виде одного графа И/ИЛИ. В самом нижнем узле этого
графа будут располагаться основные системные данные, а в самом верхнем узле – заключения, выводимые системой.
С помощью такого графа можно решить проблему поиска пути в
продукционной системе. В таком случае задача сводится к поиску пути
(оптимального пути) на графе. Она решается с помощью алгоритмов перебора всевозможных путей на графе. В сложных многовариативных системах (например, в компьютерной версии игры шахматы или в консультационных системах оценки развития бизнеса) проблема поиска на графе,
показывающего возможности разворачивания ситуации, является существенной проблемой. В подобных случаях необходимы эффективные способы поиска пути. В различных ситуациях могут быть применены следующие методы:
1.
Метод минимизации запросов – наиболее распространённый.
При этом вводятся ограничения на широту и глубину поиска решения, а
также на суммарный объём начальных данных.
2.
Метод приоритетного поиска. Этот метод вывода применяется
для задания естественной последовательности запросов, при этом используются правила с жёстким условием.
3.
α-β алгоритм. Один из методов поиска на графе, наиболее подходящий для компьютерных игр.
4.
Эвристические методы – на основе особенностей предметной
области в систему вводятся некоторые предположения и возможном решении.
Реальные системы могут работать с нечеткой информацией. Нечет24
кость делится на две категории: нечеткость непосредственных данных и
нечёткость выводов. Для преодоления этой проблемы вводят понятие
"степень достоверности", которое отражает насколько далеко высказывание от истины. При движении по графу решения степени достоверности
синтезируются и определяют степени достоверности промежуточных гипотез. При этом в зависимости от типа связки степени достоверности могут увеличиваться или уменьшаться. В случаи связок ИЛИ возможны варианты устранения нечёткости.
Использование графов имеет ряд преимуществ, наиболее важным из
которых являются: возможность устранения тупиковых ветвей решения и
выявления ошибочных правил.
3. Управление выводом в продукционной системе.
Выбор последовательности применения правил – это основная задача механизма управления выводом. От её решения зависит эффективность
всей системы. Особенно она важна в системах с запросом пользователя,
так как в этом случае необходимо дополнительно обеспечивать естественный порядок запросов и минимизацию объёма запрашиваемых данных.
Для управления выводом используют два метода:
1.
Устанавливают ряд ограничений на генерацию конфликтного
набора. При этом вводятся категории правил и метаправила – правила, содержащие условия, касающиеся содержания правил. Использую метаправила для выбора очередного правила в определенных ситуациях либо некоторые категории вообще не рассматриваются, либо в зависимости от
дополнительных правил рассматриваются только правила из одной определенной категории.
2.
Определяют алгоритм разрешения конфликта. В этом случае
вводятся дополнительные атрибуты, которые позволяют устанавливать
порядок применения правил. Наиболее простым примером является применение правил в той же последовательности, в какой они определялись.
Проблема управления выводом характерна для систем и прямого, и
обратного вывода. Однако в первом случае все алгоритмы проще, а в случае систем обратного вывода появляется дополнительная проблема последовательности оценки условий в условной части правил. При этом вводятся дополнительные атрибуты, которые определяют "близость" правила к
основным данным.
Применяемые различные методы разбиений правил на группы привело к разработке модели доски объявлений.
Тема 5. Представление знаний фреймами и выводы.
План:
1.
Основы теории фреймов.
25
2.
Свойства и основные параметры фреймов.
1. Основы теории фреймов.
Для фреймовой модели характерно представление знаний сравнительно большими единицами информации, использование иерархической
структуры зависимостей единиц информации, определяемой уровнем абстракции, а также возможность комбинации декларативных и процедурных подходов при обработке информации. Чтобы наиболее полно использовать возможности фреймовой модели вводятся специальные языки
представления данных, которые позволяют, как исследовать представление знаний, так строить многоцелевые базы знаний. Такой подход особенно актуален в САПР (системах автоматического проектирования).
Теория фреймов относится к психологическим понятиям, касающимся понимания того, что мы видим и слышим. Она была разработана и
опубликована М.Минским в 1975 г. Эта теория основывается на следующих основных правилах:
1.
Фрейм – это единица представления знаний созданная (или запомненная) на основе прошлых данных. Каждый фрейм может быть дополнен различной информацией в зависимости от ситуации его использования.
2.
Фрейм представляет собой сеть из нескольких вершин и отношений, их соединяющих. На самом верхнем уровне фрейма представлена
фиксированная информация: истинные факты, касающиеся объекта. На
последующих расположены объединения фактов, на основе правил соответствия (которые задаются на уровне фрейма) – так называемые терминальные слоты или терминалы. Таким образом, каждый фрейм представляет собой иерархическую структур отношений типа "абстрактное - конкретное".
3.
Обычно каждый терминал содержит не только данные, но и
процедуры позволяющие обрабатывать эти данные, а также передавать результаты другим терминалам.
4.
Каждый фрейм содержит специальную процедуру вывода, которая позволяет ему выполнять запросы к другим пользователям (или
пользователю).
5.
Несколько терминалов каждого фрейма обязательно заранее
определяются и заполняются значениями по умолчанию. Это обеспечивает информативность фрейма даже в случае отсутствия конкретных данных, а также позволяет изменить целевую направленность фрейма, просто
заменив данные по умолчанию. Также подобные данные могут использоваться для введения логических ограничений в систему.
2. Свойства и основные параметры фреймов.
26
На основе фреймов могут быть составлены информационнопоисковые сети. Фрейм-кандидат исследуется на соответствие данной
проблеме, если он не отвечает требованиям, то осуществляется переход к
следующему фрейму по специальной метке. При этом информация согласования может пополнять фрейм.
К основным свойствам фреймов относят следующие:
1.
Базовый тип. В качества базовых фреймов запоминаются только важнейшие свойства объекта, которые являются постоянными для
большинства объектов данного типа.
2.
Имя фрейма. Это идентификатор, присваиваемый фрейму,
фрейм должен иметь имя, единственное в данной фреймовой системе
(уникальное имя).
3.
Имя слота. Это идентификатор, присваиваемый слоту; слот
должен иметь уникальное имя во фрейме, к которому он принадлежит.
Каждый фрейм состоит из произвольного числа слотов, причем несколько
из них обычно определяются самой системой для выполнения специфических функций, а остальные определяются пользователем. Обычно имя
слота не несет никакой смысловой нагрузки и является лишь идентификатором данного слота, но в некоторых случаях оно может иметь специфический смысл. К таким именам помимо IS-А (отношение IS-А),
DDESENDANTS (указатель прямого дочернего фрейма), FINEDBY (пользователь, определяющий фрейм), DEFINEDON (дата определения фрейма), MODIFIEDON (дата модификации фрейма), COMMENT (комментарий) и т. п. относятся имена, используемые для представления структурированных объектов, например HASPART, RELATIONS и другие. Эти слоты называются системными и используются при редактировании базы
знаний и управлении выводом.
4.
Указатели наследования. Эти указатели касаются только фреймовых систем иерархического типа, основанных на отношениях “абстрактное – конкретное”, они показывают, какую информацию об атрибутах
слотов во фрейме верхнего уровня наследуют слоты с такими же именами
во фрейме нижнего уровня. Типичные указатели наследования Unique (U:
уникальный), Same (S: такой же), Range (R: установление границ),
Override (O: игнорировать) и т. п.
5.
Указание типа данных. Указывается, что слот имеет численное
значение, либо служит указателем другого фрейма (т.е. показывает имя
фрейма). К типам данных относятся FRAME (указатель), INTEGER (целый), REAL (действительный), BOOL (булев), LISP (присоединенная процедура), ТЕХТ (текст), LIST (список), TABLE (таблица), ЕXРRESSION
(выражение) и другие.
27
6.
Значение слота. Пункт ввода значения слота. Значение слота
должно совпадать с указанным типом данных этого слота, кроме того,
должно выполняться условие наследования.
7.
Демон. Здесь дается определение демонов типа IF-NEEDED,
IF-ADDED, IF-REMOVED и т. д. Демоном называется процедура, автоматически запускаемая при выполнении некоторого условия. Демоны запускаются при обращении к соответствующему слоту. Например, демон IFNEEDED запускается, если в момент обращения к слоту его значение не
было установлено, IF-ADDED запускается при подстановке в слот значения, IF-REMOVED запускается при стирании значения слота. Кроме того,
демон является разновидностью присоединенной процедуры.
8.
Присоединенная процедура. В качестве значения слота можно
использовать программу процедурного типа, называемую служебной
(servant) (в языке Лисп) или методом (в языке Смолток). В данном случае
присоединенная процедура запускается по сообщению, переданному из
другого фрейма. Когда мы говорим, что в моделях представления знаний
фреймами объединяются процедурные и декларативные знания, то считаем демоны и присоединенные процедуры процедурными знаниями. Кроме
того, в языке представления знаний фреймами отсутствует специальный
механизм управления выводом, поэтому пользователь должен реализовать
данный механизм с помощью присоединенной процедуры. Следовательно,
язык представления знаний фреймами можно назвать языком, ориентированным на специалистов по искусственному интеллекту, а также языком,
ориентированным на сложные прикладные проблемы.
Тема 6. Семантические сети и онтологии.
План:
1. Понятие семантической сети.
2. Онтологии.
3. Семантическая паутина.
1. Понятие семантической сети.
Семантические сети разрабатывались как модель представления
структуры долговременной памяти в психологии. Сейчас они используются для представления знаний в инженерии знаний.
Семантическая сеть – информационная модель предметной области, имеющая вид ориентированного графа, вершины которого соответствуют объектам предметной области, а дуги (рёбра) задают отношения между ними. Объектами могут быть понятия, события, свойства, процессы.
Компьютерные семантические сети были детально разработаны Ричардом Риченсом в 1956 году в рамках проекта Кембриджского центра
изучения языка по машинному переводу. Процесс машинного перевода
28
подразделяется на 2 части: перевод исходного текста в промежуточную
форму представления, а затем эта промежуточная форма транслируется на
нужный язык. Такой промежуточной формой как раз и были семантические сети.
Одной из разновидностей семантической сети, получившей большое
распространение, является модель TLC (Teachable Language Comprehended
– доступный механизм понимания языка), предложенная Куиллианом и
носящая его имя. В данной модели для описания структуры долговременной памяти была использована сетевая структура, в которой особое внимание уделяется понятию "класс". Класс ассоциируется с различными
свойствами и примерами, что позволяет точно определять значение понятия. Причём определение каждого объекта происходит в своей понятийной плоскости (как предметной, так и уровневой), переход с одной плоскости на другую позволяет уточнить или даже видоизменить понятие объекта. Дана модель используется в качестве базисной в компьютерных онтологиях.
Для семантических сетей используют следующие классификации:
По количеству типов, сети могут быть однородными и неоднородными. Однородные сети обладают только одним типом отношений (стрелок), например, классификация биологических видов. В неоднородных сетях количество типов отношений больше двух. Неоднородные сети представляют больший интерес для практических целей, но и большую сложность для исследования.
По арности, типичными являются сети с бинарными отношениями
(связывающими ровно два понятия). Бинарные отношения очень просты и
удобно выглядят на графе в виде стрелки между двух концептов. Кроме
того, они играют исключительную роль в математике. На практике, однако, могут понадобиться отношения, связывающие более двух объектов –
N-арные. При этом возникает сложность – как изобразить подобную связь
на графе, чтобы не запутаться. Концептуальные графы снимают это затруднение, представляя каждое отношение в виде отдельного узла.
Помимо концептуальных графов существуют и другие модификации
семантических сетей, это является ещё одной основой для классификации
(по реализации).
Виды отношений в семантической сети.
Наиболее часто возникает потребность в описании отношений между элементами, множествами и частями объектов. Отношение между объектом и множеством, обозначающим, что объект принадлежит этому
множеству, называется отношением классификации (ISA). Говорят, что
множество (класс) классифицирует свои экземпляры. Название произошло
от английского "IS A" ("суть"). Иногда это отношение именуют также
29
MemberOf. Связь ISA предполагает, что свойства объекта наследуются от
множества. Обратное к ISA отношение используется для обозначения
примеров, поэтому так и называется – "Example" ("например").
Отношение между надмножеством и подмножеством называется
AKO – "A Kind Of" ("разновидность"). Элемент подмножества называется
гипонимом, а надмножества – гиперонимом, а само отношение называется
отношением гипонимии. Альтернативные названия – "SubsetOf" ("подмножество"). Это отношение определяет, что каждый элемент первого
множества входит и во второе, что первое не больше второго, и свойства
первого множества наследуются вторым.
Важным отношением является HasPart, описывающее части/целые
объекты (отношение меронимии). Мероним – это объект, являющийся частью для другого. Холоним – это объект, который включает в себя другое.
Также в конкретных системах могут быть рассмотрены следующие
типы отношений (наиболее употребительные):
1.
Функциональные (глагольные) – "производить", "влиять" …;
2.
Количественные – "больше", "меньше" …;
3.
Пространственные – "далеко", "за", "под", …;
4.
Временные – "раньше", "в течение", …;
5.
Логические – "И", "Или", …;
6.
Лингвистические – значения слов в конкретной области.
В этом случае сеть строится на основе класса (понятия), а вершины,
дуги (отношения) и процедуры представлены как объекты. Процедуры делятся на два подтипа
1.
Действия над дугами – связями:
- установление связи,
- аннулирование связи,
- подсчёт числа вершин, соединённых заданной дугой,
- проверка наличия/отсутствия связи между заданными вершинами.
2.
Действия над вершинами:
- определение экземпляра связи;
- аннулирование экземпляра,
- подсчёт числа экземпляров, принадлежащих классу,
- проверка принадлежности экземпляра к некоторому классу.
Благодаря такому подходу с помощью семантических сетей можно
представить процедурные знания.
2. Онтологии
Онтология (в информатике) – это попытка всеобъемлющей и детальной формализации некоторой области знаний с помощью концептуальной
схемы. Обычно такая схема состоит из иерархической структуры данных,
содержащей все классы объектов, их связи и правила (теоремы, ограниче30
ния), принятые в этой области.
Современные онтологии строятся по большей части одинаково, независимо от языка написания. Обычно они состоят из экземпляров, понятий, атрибутов и отношений.
Экземпляры (instances) (или индивиды – individuals) – это основные,
нижнеуровневые компоненты онтологии. Экземпляры могут представлять
собой как физические объекты (люди, дома, планеты), так и абстрактные
(числа, слова). Однако одной из главных целей онтологии является классификация таких объектов.
Понятия (concepts) (или классы – classes) – это абстрактные группы,
коллекции или наборы объектов. Они могут включать в себя экземпляры,
другие классы, либо же сочетания и того, и другого.
Объекты в онтологии могут иметь атрибуты. Каждый атрибут имеет,
по крайней мере, имя и значение, и используется для хранения информации, которая специфична для объекта и привязана к нему. Значение атрибута может быть сложным типом данных.
Важная роль атрибутов заключается в том, чтобы определять зависимости (отношения) между объектами онтологии. Обычно отношением
является атрибут, значением которого является другой объект.
Онтологии делятся на специализированные и общие. Специализированные (предметно-ориентированные) онтологии – это представление какой-либо области знаний или части реального мира. В такой онтологии
содержатся специальные для этой области значения терминов. Общие онтологии используются для представления понятий, общих для большого
числа областей. Такие онтологии содержат базовый набор терминов, глоссарий или тезаурус, используемый для описания терминов предметных
областей.
Если использующая специализированные онтологии система развивается, то может потребоваться их объединение. Это серьёзная задача, так
как онтологии часто несовместимы друг с другом, хотя могут представлять близкие области. Разница может появляться из-за особенностей местной культуры, идеологии и т. п., или вследствие использования другого
языка описания.
Сегодня объединение онтологий приходится выполнять вручную,
это трудоёмкий, медленный и дорогостоящий процесс. Использование базисной онтологии – единого глоссария – несколько упрощает эту работу.
Языки описания онтологий – формальные языки, используемые для
кодирования онтологии. Перечислим наиболее распространённые:
1.
OWL – ontology web language, стандарт W3C, язык для семантических утверждений, разработанный как расширение RDF и RDFS;
2.
KIF (Knowledge Interchange Format или формат обмена знаниями) – основанный на S-выражениях синтаксис для логики;
31
3.
CycL – онтологический язык, использующийся в проекте Cyc,
основан на исчислении предикатов с некоторыми расширениями более
высокого порядка.
Для работы с языками онтологий существует несколько видов технологий: редакторы онтологий (для создания онтологий), DBMS онтологий (для хранения и обращения к онтологии) и хранилища онтологий (для
работы с несколькими онтологиями).
3. Семантическая паутина.
Семантическая паутина – это надстройка над существующей Всемирной паутиной, которая призвана сделать размещённую в ней информацию более понятной для компьютеров. Данная концепция предложена и
продвигается Консорциумом W3 (её основателем сэром Тимом Бернерсом-Ли в мае 2001 года). Она основывается на двух идеях:
1.
Повсеместное использование универсальных идентификаторов
ресурсов (URI). Традиционная схема использования таких идентификаторов в современном Интернете сводится к установке ссылок, ведущих на
объект, основным свойством которого является возможность его "закачки" (веб-страница, файл произвольного содержания, физическому ресурсу
по протоколу и т.п.). Концепция семантической паутины расширяет это
понятие, включая в него ресурсы, недоступные для скачивания. Адресуемыми с помощью URI ресурсами могут быть, например, отдельные люди,
города и другие географические сущности, художественные артефакты и
т. д. К идентификатору предъявляются несколько простых требований: он
должен быть строкой определённого формата, уникальной, а также адресующей реально существующий объект.
2.
Повсеместное использование онтологий и языков описания метаданных. Современные методы автоматической обработки данных, доступных в Интернете, в большинстве своём, основаны на частотном и лексическом анализе текстового содержимого, которое прежде всего предназначено для восприятия человеком. В семантической паутине предлагается использовать форматы описания, доступные для машинной обработки, в свою очередь, использующие URI для адресации описываемых и
описывающих объектов, а также онтологии и дескриптивные логики в качестве базовых математических инструментов.
Проблемами реализации семантической паутины являются:
1.
Человеческий фактор – дополнительные трудозатраты и психологические сложности перехода на форматы метаданных;
2.
Философский фактор – утверждение о том, что не возможно
построить метаданные самого верхнего уровня, что критично для концепции семантической паутины;
32
3.
Дублирование информации – она должна быть представлена
двумя способами: удобным для восприятия человеком и для восприятия
компьютером.
Сейчас ведутся активные разработки по внедрению и апробации новых форматов. Одним из известных проектов является "Дублинское ядро"
– он направлен на внедрение новых форматов метаданных и разработке на
них создающихся Web-приложений.
Тема 7. Представление и использование нечётких знаний.
План:
1.
Нечёткость знаний.
2.
Ненадёжные знания и выводы.
3.
Неполные знания, немотонная логика и нечёткие выводы.
1. Нечёткость знаний.
Во многих областях использования интеллектуальных информационных систем встречаются некорректно поставленные задачи, т.е. задачи,
не имеющие четкого алгоритма решения из-за недостаточности входных
данных или ограниченности логических правил. Чтобы интеллектуальные
информационные системы приблизились к человеческому мышлению, необходимо реализовать возможность решения некорректно поставленных
задач, т.е. реализовать обработку нечетких знаний. Однако, эта задача
входит в противоречие с основной идей программирования, согласно которой все знания должны быть формализованы и описаны. Поэтому все
нечеткости, которые встречаются в инженерии знаний, классифицируются, и для каждого класса разрабатывается своя концепция преодоления
указанного противоречия. Основными нечёткостями являются:
1.
Недетерминированность управления выводами;
2.
Многозначность;
3.
Ненадёжность;
4.
Неполнота;
5.
Неточность.
Недетерминированность управления выводами означает, что нельзя
заранее определить цепочку логических выводов, приводящих к результату. Это связанно с тем, что знания накапливаются в системе фрагментарно, и определение следующего логического шага происходит только во
время работы системы. Другими словами, методом перебора определяется
некая цепочка выводов, причем она может быть неудачной, в этом случае
организуется перебор с возвратами.
Так как эффективность простого поиска или полного перебора является очень низкой, то разрабатываются всевозможные методы улучшенного поиска, при котором выбирается приоритетный путь решения. К таким
33
методам относятся:
1.
алгоритм А* или метод оценочных функций – когда каждому
отрезку пути присваивается определенная стоимость, позволяющая выбирать оптимальный путь;
2.
эвристический поиск – отсутствие строгих правил поиска, программа самостоятельно определяет приоритет поиска и обучается выбирать следующее на основе первоначально заложенных эвристических правил;
3.
методы поиска пути на графе;
4.
механизм "список заявок" – когда продвижение по дереву путей по выбранной ветке сначала оформляется в виде заявки, а затем обрабатывается дополнительным механизмом, который выстраивает список
заявок, в зависимости от текущей ситуации.
Многозначность интерпретации чаще всего возникает в задачах распознавания образов (тестов, изображений) и при обработке естественных
языков (переводе, автореферировании). Многозначность характеризуется
неоднозначностью выводов по текущим данным (например, многозначный смысл слов или их связей), что затрудняет построение дальнейших
выводов. В общем случае многозначность помогает устранить расширение
границ семантических ограничений, т.е. такое доопределение данных, которые помогает различать похожие объекты. Одним из методов является
метод релаксации. Этот механизм основывается на методике решения
дифференциальных уравнений в частных производных. Его суть в следующем: в начале работы системы уточняется семантический смысл всех
данных, при необходимости они доопределяются с помощью так называемых начальных или граничных условий (например, каждая линия рисунка объекта получает свой физический смысл: граничная, невидимая,
срез и т.п.). Затем совершаются переходы от простейших выводов к более
сложным (от символов – к словам, от слов – к предложениям), на каждом
уровне устраняется многозначность путем обращения к предыдущим
уровням за дополнительными данными и к верхним уровням – за уточнением, какие данные могут понадобиться выше. Обычно системы распознавания речи выполняются в виде многоуровневых "досок объявлений",
где на нижнем уровне распознаются акустические сигналы, а на самом
верхнем – смысл фразы.
2. Ненадёжные знания и выводы.
Во многих задачах невозможно однозначно охарактеризовать определенные факты только словами "истинно" или "ложно". Данные факт
может быть не подтвержден или опровергнут полностью или подтверждаться только в некоторых случаях. В этом случае говорят о ненадёжных
знаниях. В самом простейшем случае ненадежные знания определяются
34
как вероятность истинности каждого факта. Но обычная теория вероятностей имеет ряд недостатков, которые не позволяют её использовать напрямую, в частности невозможно представить полное незнание по определенному вопросу.
Для преодоления нечёткости в виде ненадёжности знаний применяются различные усовершенствованные методики на основе теории вероятностей. К ним относятся:
1.
Коэффициенты уверенности – знания рассматриваются как
предпосылки, при этом каждая предпосылка может выполняться с некоторой вероятностью. Вероятности для предпосылок на верхних уровнях определяются согласно правилам вывода конструкций И и ИЛИ.
2.
Субъективный баесовский подход. В этой методике не оговариваются правила вывода, но для каждой предпосылки устанавливается
минимальная и максимальная вероятность, а затем они обрабатываются с
помощью специальных формул сочетания предпосылок.
3.
Метод выводов на основе теории Демпстера-Шафера. В этой
методике определяется нижняя вероятность – функция доверия, и верхняя
вероятность – мера правдоподобия. Такое разделение позволяет не только
отражать степень достоверности знаний, но и выражать на языке вероятности незнание фактов.
4.
Нечёткая логика. Объединяет в себе приемы теории нечетких
множеств и непрерывной логики. Степень истинности – некоторое число
от 0 до 1, которое приписывается как предпосылкам (фактам), так и правилам вывода. При этом при связи И выбирается минимальное из значений истинности предпосылок, а при связи ИЛИ – максимальное. Степень
истинности правила также отражается не результате.
5.
Вероятностная логика (логика Нильсона). Вероятность предпосылок рассчитывается по классическим формулам, но все логические
формулы получают собственную вероятность, которая зависит от особенностей предметной области.
Во всех методиках предполагается общий подход разбиения задачи.
Он состоит в следующем: задача разбивается на подзадачи, те в свою очередь также разбиваются на подзадачи и так далее, пока не будут выделены
простейшие подзадачи. Затем на основании разбиения строится дерево
объединения подзадач. При этом могут использоваться связки И, ИЛИ, а
также КОМБ (комбинация). Самым сложной является связка КОМБ. Для
неё вероятности выводов на основании комбинирования предпосылок
приходится либо определять, либо вводить соответствующие правила, которыми и различаются изложенные выше методики. При этом возможно
как увеличение вероятности, по сравнению с составляющими, так и своеобразное усреднение, все зависит от входных данных.
35
3. Неполные знания, немонотонная логика и нечёткие выводы.
При разработке большинства систем искусственного интеллекта
считается, что все верные правила в определенной предметной области
внесены в систему. Если же правило отсутствует в системе, то оно считается всегда ложным. Это называют гипотезой закрытого мира.
Второй рабочей гипотезой является полнота правил, то есть если некий вывод был сделан на основании имеющихся правил, то он не изменится, если добавить новое правило. Это называют гипотезой монотонности логики.
Однако на практике встречаются ситуации, когда человек, в процессе размышлений делает определённые выводы, но, получив новую информацию, он определяет для себя новые правила и корректирует выводы.
Такой подход пытаются реализовать в системах искусственного интеллекта. Подобные системы называют системами неполных знаний. Они строятся на математическом аппарате обработки неполных знаний и немонотонной логики. Типичными подходами, реализующими эти идеи являются: немонотонная логика Макдермотта и Доула, логика умолчания Рейтера, окружение (ограничение) Маккарти. Указанные системы реализуются
прежде всего во фреймовых системах, в которых для доопределения правил используются слоты фреймов.
Ещё одним, типично человеческим приёмом рассуждений, является
нечёткое определение границ некоторого множества. Нечётким множеством называют такое множество элементов, для каждого из которых указывается степень принадлежности данному множеству, т.е. в какой степени
этот элемент удовлетворяет определяющим множество правилам. Например, понятие "старый человек" задаёт нечёткое множество, так как невозможно строго определить возраст или другие биологические данные человека, подходящего под это понятие.
Если определить правила вывода отношений на нечетких множествах, то можно построить логику, позволяющую делать выводы на нечетких множествах. Подобные рассуждения называют нечеткими выводами,
и они присущи большей части человеческих рассуждений. Их характеризуют обороты "мне кажется", "скорее всего" и т.п. Для компьютерного варианта подобные рассуждения будут характеризоваться некой числовой
функцией, выражающей степень принадлежности каждого конкретного
элемента нечёткому множеству.
Тема 8. Работа со знаниями, представленными в текстовом виде.
План:
1.
Гипертекстовые информационные технологии.
2.
Информационно-поисковые системы.
3.
Системы распознавания образов.
36
1. Гипертекстовые информационные технологии
Текст является универсальным средством представления, накопления и передачи знаний в человеческом обществе. Поэтому технологии работы с естественно-языковыми текстами (а также с текстами на ограниченном естественном языке) всегда считались важнейшими для ИИ.
Гипертекст – одна из фундаментальных моделей представления знаний, выраженных в текстовом виде. Под гипертекстом понимается форма
организации семантической информации, предусматривающая ее разделение на фрагменты, для каждого из которых заданы переходы к родственным фрагментам. В настоящее время под ГТ также понимают многоцелевой информационный фонд, характеризующийся полнотой изложения
сведений по определенной тематике и наличием ссылок между статьями.
В основе ГТ лежат следующие основные идеи.
1.
Текст разбивается на фрагменты, представляющие его семантические единицы (сеты). Между ними устанавливаются связи, которые
могут наделяться именами.
2.
В отличие от обычного текста, который читается последовательно (в порядке, определенном его автором), ГТ можно читать, двигаясь
по разным траекториям, образованным связанными сетами.
3.
Активируемые переходы выбираются читателем (пользователем). Имена (типы) связей облегчают решение задачи выбора перехода.
Гипертекстовая информационная технология – технология обработки семантической информации, основанная на использовании ГТ. Она относится к проблематике ИИ, так как ее содержанием является представление, поиск и обработка семантической информации, выраженной в текстах. Области применения гипертекстовой технологии весьма разнообразны: информационные ресурсы и технологии Internet; гипертекстовые информационно-поисковые системы; гипертекстовые информационные модели экономических систем; базы данных с гипертекстовой организацией;
обучающие системы; экспертные системы и т.д.
В соответствии с протоколом передачи гипертекста HyperText
Transport Protocol (HTTP) минимальной неделимой единицей данных,
предназначенной для межмашинного обмена, является текст, записанный
на языке разметки гипертекста HyperText Markup Language (HTML). Логически единая система HTML-страниц может быть физически рассредоточена по сети. Система URL позволяет как размещать, так и собирать ресурсы, на которые ссылается ГТ.
В основе моделей ГТ лежит понятие информационно-справочной
статьи, выступающей в качестве информационной единицы ГТ. В конкретных технологиях они называются по-разному: страница, статья, тема
и др. Статья может включать информацию, представленную в разных
37
формах: текст, таблицы, фрагменты программного кода (макросы, скрипты), внедренные цифровые объекты, а также ссылки на подобные объекты
(графика, звук, видео, управляющие элементы пользовательского интерфейса и т. д.), включаемые в ИСС при ее загрузке.
2. Информационно-поисковые системы
Гипертекстовая информационная технология используется при организации больших массивов текстовых документов и реализации методов
поиска информации в них.
Информационный поиск – совокупность операций, методов и процедур, направленных на отбор данных, хранящихся в ИС и соответствующих заданным условиям.
Информационно-поисковые системы (ИПС) подразделяются на три
класса: документальные; фактографические; гипертекстовые.
Документальные ИПС хранят и выдают сведения о документах, основное содержимое которых представлено в виде связанного текста на ЕЯ.
Признаки документа, отражающие его содержание в ИПС, называют поисковым образом, а признаки запроса к ИПС — поисковым предписанием.
Процедура перевода документа и запроса в форму представления, принятую в ИПС, называется индексированием.
В фактографических ИПС хранятся не документы, а собственно сведения (факты) об объектах ПрО. Подобные ИПС реализуются, в частности, на основе реляционных БД.
В гипертекстовых ИПС кроме содержимого документов отражается
их семантическая структура. Поэтому по глубине формализации ГИПС
занимают промежуточное положение между документальными и фактографическими ИПС.
Гипертекст расширяет возможности человека, связанные с поиском
и обработкой информации, за счет установления ассоциаций, построения
обобщений, формирования целостного представления о содержании документа и т. д. В настоящее время существует тенденция интеграции гипертекстовых ИС со специализированными пакетами прикладных программ. При этом возникают гибридные ИС, предназначенные для решения
различных классов трудноформализуемых задач.
В информационно-поисковых системах применяются следующие
методы поиска:
1.
индексирование текстов и поиск по ключевым словам (по индексу);
2.
поиск, включающий морфологический разбор и отождествление различных грамматических форм слов;
3.
поиск с ранжированием документов по степени релевантности
запросу;
38
4.
использование формальных поисковых языков;
5.
комплексные методы.
В технологиях БД и БЗ наряду с перечисленными применяются следующие методы поиска:
1.
использование формальных языков запросов, позволяющих
описывать условия совместного вхождения ключевых слов в документ
(это направление представляют SQL-подобные языки);
2.
методы семантического анализа текста.
Средства автоматического извлечения знаний из текстовых ресурсов
Internet реализуются в поисковых машинах. При этом различают:
1.
методы итеративного поиска;
2.
методы поиска по выборке;
3.
методы, использующие каталоги (рубрикаторы и классификаторы, организующие множество документов в деревья);
4.
семантические методы поиска, использующие подходы ИИ.
Количество информации, представленной в Internet, постоянно увеличивается, поэтому необходимы автоматизированные средства поиска.
Наиболее распространёнными являются каталоги ресурсов и поисковые
машины. Каталог ресурсов Internet – постоянно обновляемая и пополняемая система ссылок на ресурсы, распределенные по иерархической структуре категорий. Поисковые машины (или поисковые системы) позволяют
находить ресурсы Internet непосредственно по их текстовому содержимому. Функционирование поисковой машины включает два базовых процесса: 1) индексирование ресурсов Internet (автоматическое построение и обновление индекса); 2) поиск по индексу по запросам пользователей.
3. Системы распознавания образов
Методы автоматического распознавания образов и их реализация в
системах оптического чтения текстов (OCR-системах – Optical Character
Recognition) – одна из самых востребованных технологий искусственного
интеллекта. OCR понимается как автоматическое распознавание с помощью специальных программ изображений символов печатного или рукописного текста (например, введенного в компьютер с помощью сканера) и
преобразование его в формат, пригодный для обработки текстовыми процессорами. Автоматическое чтение печатных и рукописных текстов является частным случаем автоматического визуального восприятия сложных
изображений. Многочисленные исследования показали, что для полного
решения этой задачи необходимо интеллектуальное распознавание, т. е.
«распознавание с пониманием». Однако, в настоящее время в технически
реализуемых OCR-системах рассматриваемая проблема значительно упрощена и сведена к задаче классификации по признакам простых объектов. Эта задача описывается хорошо разработанным математическим ап39
паратом пороговых отделителей – разделяющими плоскостями
В лучших OCR-системах используется технология распознавания,
свойственная человеку, реализуемая по схеме: обработка контекста – грубое выделение признаков – выдвижение гипотезы об объекте – выделение
составных частей – проверка правильности – переход от гипотезы к утверждению (перевод предположения в заключение).
Выделяются три принципа, на которых основаны все OCR-системы
1.
Принцип целостности образа: в исследуемом объекте всегда
есть значимые части, между которыми существуют отношения.
2.
Принцип целенаправленности: распознавание является целенаправленным процессом выдвижения и проверки гипотез (поиска того, что
ожидается от объекта).
3.
Принцип адаптивности: распознающая система должна быть
способна к самообучению.
Графический образ символа на выходе сканера имеет вид шейпа,
представляющего собой матрицу из точек, которую можно редактировать
поэлементно. Реализация соответствующих механизмов связана с решением проблемы понимания текста на естественном языке. Общее решение
задачи автоматического распознавания образов должно основываться на
организации процесса с такими интеллектуальными составляющими, как
целостность восприятия, целенаправленность, предвидение (выдвижение
гипотез), максимальное использование контекста и знаний о среде (в пределе — использование модели мира), т. е. учете и реализации интеллектуальных механизмов зрительного восприятия человека.
Автоматическое зрительное восприятие на сегодняшний день не
достигает совершенства человеческого восприятия образов. Главная причина этого заключается в неумении строить достаточно полные и семантически выразительные компьютерные модели ПрО.
Среди OCR-технологий важное значение имеют специальные технологии решения отдельных классов задач автоматического распознавания
образов:
1.
поиск людей по фотографиям;
2.
поиск месторождений полезных ископаемых и прогнозирование погоды по данным аэрофотосъемки и снимкам со спутников в различных диапазонах светового излучения;
3.
составление географических карт по исходной информации,
используемой в предыдущей задаче;
4.
анализ отпечатков пальцев и рисунков радужной оболочки глаза в криминалистике, охранных и медицинских системах.
Для решения этих задач созданы специальные методы и алгоритмы,
объединенные в специализированные интеллектуальные информационные
системы.
40
Тема 9. Понятие экспертной системы.
План:
1.
Определение экспертной системы.
2.
Общая архитектура экспертных систем.
3.
Классификация экспертных систем.
4.
Характеристики экспертных систем
1. Определение экспертной системы.
В начале 80-х годов в исследованиях по искусственному интеллекту
сформировалось самостоятельное направление, получившее название
"экспертные системы" (ЭС), которое также называют "инженерия знаний".
Экспертная система – это программное средство, использующее знания и опыт экспертов для обеспечения высокоэффективного решения неформализованных задач в узкой предметной области. Основу ЭС составляет база знаний о предметной области, которая содержит факты (статические сведения о предметной области) и правила - набор инструкций,
применяя которые к известным фактам можно получать новые факты.
Экспертные системы отличаются от систем обработки данных тем,
что в них используется символьный (а не числовой) способ представления
и вывода знаний, а также эвристический поиск решения вместо следования жестко заданному алгоритму. ЭС используются для решения так называемых неформализованных задач, общим для которых является то, что
1.
ошибочностью, неоднозначностью, неполнотой и противоречивостью исходных данных;
2.
ошибочностью, неоднозначностью, неполнотой и противоречивостью знаний о проблемной области и решаемой задаче;
3.
большой размерностью пространства решения, т.е. перебор при
поиске решения весьма велик;
4.
динамически изменяющимися данными и знаниями;
5.
не существует алгоритмического решения задачи, а если алгоритмическое решение есть, то его нельзя использовать из-за ограниченности ресурсов (время, память).
Использование систем искусственного интеллекта и, в частности,
экспертных систем, имеет ряд преимуществ:
1.
технология экспертных систем существенно расширяет круг
задач (в частности, социально-экономических), решаемых на компьютерах;
2.
объединение технологии ЭС с технологией традиционного
программирования позволяет конечным пользователям, а не специали41
стам-программистам, динамично модифицировать приложения под текущие задачи;
3.
так как в большинстве ЭС знания хранятся на ограниченном
естественном языке, то упрощается обучение персонала и сопровождение
системы;
4.
применение для решения проблем высококачественного опыта,
который представляет уровень мышления наиболее квалифицированных
экспертов в данной области, что ведёт к решениям творческим, точным и
эффективным;
5.
наличие прогностических возможностей, при которых ЭС выдаёт ответы не только для конкретной ситуации, но и показывает, как изменяются эти ответы в новых ситуациях, с возможностью подробного
объяснения каким образом новая ситуация привела к изменениям;
6.
обеспечение институциональной памяти, за счёт входящей в
состав ЭС базы знаний, которая разработана в ходе взаимодействий со
специалистами организации, и представляет собой текущую политику
этой группы людей, что позволяет накапливать и концентрировать опыт
лучших сотрудников организации;
7.
постоянство системы с точки зрения профессиональной подготовки, т.к. человеческая компетенция ослабевает со временем;
8.
лёгкость передачи или воспроизведения накопленных знаний,
т.к. это простой процесс копирования программы или файла данных;
9.
минимизация влияния человеческого фактора (эмоционального
и психолого-физического состояния эксперта);
10. разработка большинства ЭС дорога, но они дёшевы в эксплуатации, тогда как и подготовка, и использование экспертов очень дороги.
2. Общая архитектура экспертных систем.
Архитектура экспертных систем включает в себя 2 основных компонента:
базу знаний (хранилище единиц знаний) – совокупность единиц знаний, которые представляют собой формализованное с помощью
некоторого метода представления знаний отражение объектов предметной
области и их взаимосвязь, действия над объектами и, возможно, неопределённости, с которыми эти действия осуществляются;
программный инструмент доступа и обработки знаний, состоящий из механизма логического вывода заключений и механизма приобретения знаний.
Главной особенностью, характеризующей экспертные системы как
отдельный класс информационных систем, является модуль объяснения
полученного результата. Его работа строится на основе механизма логи42
ческого вывода решения, с фиксированием каким образом на каждом из
шагов был получен результат.
Эксперт
Пользователь
Инженер знаний
Интеллектуальный
интерфейс
Механизм
приобретения знаний
Механизм объяснения
Механизм логического
вывода
Рабочая область
База знаний
База данных
БП + БФ
Интеллектуальный интерфейс ориентирован на организацию дружественного общения с пользователем, как в ходе решения задач, так и в
процессе объяснения результатов работы. Основная задача интеллектуального интерфейса – преобразовывать запросы пользователя с естественного языка во внутреннее представление этих запросов.
Механизм логического вывода – программный инструмент, который
получает от интеллектуального интерфейса преобразованные запросы,
формирует из базы знаний конкретный алгоритм решения задачи, выполняет его, а полученный результат предоставляется интеллектуальному интерфейсу для выдачи ответа на запрос пользователя. В основе использования механизма логического вывода лежит процесс нахождения в соответствии с поставленной целью и описанием конкретной ситуации (исходных
данных) относящихся к решению единиц знаний (правил, объектов, прецедентов и т.д.) и связыванию их при необходимости в цепочку рассуждений, приводящую к определённому результату. Для представления знаний
в форме правил используется одна из моделей представления знаний.
Механизм объяснения – в процессе или по результатам решения задач пользователь может запросить объяснение или обоснование хода решения. С этой целью экспертная система должна предоставить механизм
объяснения.
Рабочая область – часть экспертной системы, связанная с механизмом вывода и предназначенная для хранения вновь полученных правил
43
или фактов. Также в рабочей области происходит непосредственно обработка цепочки вывода решений.
Механизм приобретения знаний – это база знаний, которая отражает
знания экспертов, специалистов в данной проблемной области, о действиях в различных ситуациях или процессах решения характерных (типовых)
задач. Выявлением подобных знаний и последующим их представлением
в базе знаний занимаются специалисты, называемые инженерами знаний.
В простейшем случае в качестве механизма приобретения знаний может
выступать интеллектуальный редактор, который позволяет вводить единицы знаний в базу знаний и проводить их синтаксический и семантический контроль (к примеру, на непротиворечивость). В более сложных случаях можно извлекать знания путём специальных сценариев интервьюирования экспертов, из вводимых примеров реальных ситуаций, из опыта
работы самой интеллектуальной системы.
3. Классификация экспертных систем.
По степени сложности решаемых задач ЭС можно классифицировать
так:
1. По способу формирования решений ЭС разделяются на 2 класса:
1.1. Аналитические – выбор решения из множества существующих
альтернатив (определение характеристик объекта);
1.2. Синтетические – генерация неизвестных решений (формирование ответа).
2. По способу учёта временного признака ЭС могут быть:
2.1. Статические – решают задачи при неизменяемых в процессе
решения данных и знаний. Статические системы осуществляют монотонное, непрерываемое решение задачи от ввода исходных данных до конечного результата;
2.2. Динамические – допускают изменения в процессе работы, т.е. в
системе существует возможность пересмотра и корректировки полученных данных и знаний.
3. По видам используемых знаний ЭС могут быть:
3.1. С детерминированными знаниями;
3.2. С неопределёнными данными (качественная оценка).
4. По числу используемых источников данных; ЭС могут быть построены
с использованием одного или нескольких источников данных.
Наиболее употребительной классификацией является функциональная:
1.
Классифицирующие. Являются одним из важнейших подклассов аналитических систем, решают задачи распознавания различных си44
туаций (классификации задач) и по набору признаков (факторов) выбирают определённую последовательность действий (алгоритм решения).
2.
Доопределяющие. Применяются при решении задач с неполными или неопределёнными данными. В этом случае ЭС доопределяет
знания с помощью эвристических приёмов или обращения к нескольким
источникам данных. Типичными представителями доопределяющих систем являются доски объявлений.
3.
Трансформирующие. Используются, когда динамично видоизменяются исходные данные или предметная область в целом. В качестве
методов решения задач здесь могут быть: генерация и тестирование гипотез, предположения и использование общих закономерностей предметной
области.
4.
Многоагентные. Основной особенностью является интегрирование разнородных источников знаний в рамках одной системы, динамически обменивающихся данными. Для многоагентных систем характерны
обработка больших объёмов информации и распределённое решение поставленной задачи.
5.
Самообучающиеся. В их основе лежат методы автоматической
классификации реальных ситуаций, примеры которых накапливаются за
определённый период и составляют обучающую выборку. Самообучающиеся системы могут быть "с учителем", когда пользователь (инженер по
знаниям) непосредственно задаёт, к какому классу принадлежит определяемая ситуаций, и «без учителя», когда по степени близости значений
классифицирующих признаков система сама выделяет классы ситуаций
4. Характеристики экспертных систем
Экспертная система должна иметь следующие характеристики:
o Компетентность, ЭС должна демонстрировать такой же уровень профессионализма в конкретной предметной области, что и экспертылюди. Она должна быть умелой, т.е. применять знания для получения
решений эффективно и быстро. Для того, чтобы по-настоящему подражать поведению эксперта-человека, ЭС должна быть робастной. Это
подразумевает не только глубокое, но и широкое понимание предмета
(т.е. при некорректных или неполных знаниях уметь рассуждать, используя общие знания и методы нахождения решений).
o Символьные рассуждения. Эксперты решают задачи, используют эвристики с помощью символов и составляющих из них понятий. Знания
в основном содержат символьную информацию, соответствующую содержанию некоторого понятия реального мира. Кроме того, ЭС должна
уметь манипулировать этими понятиями в произвольной форме, для
того чтобы получить самое рациональное решение.
o Глубина. ЭС должна иметь глубокие знания в узкоспециализирован45
ной предметной области, содержащей трудные задачи. Поэтому правила должны быть сложными. Рекомендации, методы представления знаний, организация знаний, необходимых для нахождения решений часто
связаны с объёмом и сложностью пространства поиска. Пространство –
это много промежуточных и окончательных решений задачи.
o Самосознание. ЭС имеют знания, позволяющие им рассуждать о своих действиях, и структуру, упрощающую эти рассуждения. Например,
если ЭС основана на правилах, то ей легко рассмотреть цепочки выводов, которые она порождает, чтобы прийти к решению задачи. Если
заданы ещё и специальные правила, указывающие, что можно сделать
с этими цепочками, то можно использовать эти знания для проверки
точности, устойчивости решений задачи. Эти знания системы о том,
как она рассуждает, называются метазнаниями, т.е. знаниями о знаниях. У большинства ЭС существует так называемый механизм объяснения. Большинство объяснений включает демонстрацию цепочек выводов, объясняющих, на каком основании было применено каждое правило в цепочке. Это нужно для того, чтобы:
- Пользователи больше доверяли результатам.
- Ускорить развитие системы.
- Предположения становились явными, а не подразумеваемыми.
- Легче предсказать и выявить влияние изменений.
ЭС решают следующие задачи:
• Интерпретация – построение описаний ситуаций по наблюдаемым
данным. Применение: распознавание и понимание речи, анализ изображений, определение химической структуры вещества.
• Прогноз – вывод вероятных следствий из заданной ситуации.
Прогноз погоды, дорожно-транспортных происшествий, будущего урожая, военной обстановки.
• Диагностика – заключение о нарушениях в системе исходя из наблюдений.
• Проектирование – построение конфигурации системы при ограничениях.
• Планирование – построение плана действий.
• Мониторинг – сравнение наблюдений с критическими точками
плана.
• Отладка – выработка рекомендаций по устранению неисправностей.
• Ремонт – выполнение плана применения выработанной рекомендации.
46
• Обучение – диагностика, отладка и исправление поведения ученика.
• Управление – интерпретация, прогноз, ремонт и мониторинг поведения системы.
Примерами решения вышеприведенных задач могут быть:
• Диагностика – в медицине, электронных схемах, в системах ПО.
• Проектирование – синтез и компоновка электронных схем, проектировка зданий, составление бюджета и т.д.
• Планирование – относится к объектам, способным выполнять некоторые функции.
• Мониторинг – (предупредительные системы) важны для успешного планирования. Выявление опасных мест плана.
• Система отладки – дает рекомендации относительно ликвидации
плохого функционирования системы.
• Ремонт – системы строят и выполняют планы исправления некоторых обнаруженных дефектов. Встречаются в машинной промышленности, эксплуатации инженерных сетей, авиации, работе
компьютеров.
• Обучение – АОС – описывают знания обучаемых и планируют
акт общения с обучаемыми с целью передачи им необходимых
сведений.
• Управляющие системы – управление воздушным транспортом,
ж/д, телефонной связью, боем, деловой активностью. Обеспечивает адаптивное управление всей системой.
Тема 10. Этапы реализации экспертной системы.
План:
1. Этапы разработки экспертных систем.
2. Участники процесса проектирования экспертной системы.
3. Особенности эксплуатации и режимы работы экспертной
системы.
1. Этапы разработки экспертных систем.
В отличие от большинства программных продуктов, при создании
которых определяющую роль играют разработчики-программисты, для
экспертных систем характерно участие трёх сторон: экспертов в предметной области, инженеров по знаниям и разработчиков-программистов.
Участие экспертов является определяющим, так как они определяют,
"что" следует вносить в систему. Инженеры по знаниям решают "как" это
47
будет сделано. Программисты технически реализуют разработанную схему экспертной системы в рамках программного обеспечения. Не смотря на
то, что создание экспертной системы является сложным, итерационным
процессом, этапы разработки укладываются в следующую схему:
1) На этапе идентификации необходимо выполнить следующие действия:
- определить задачи, подлежащие решению и цели разработки,
- определить экспертов и тип пользователей.
2) На этапе концептуализации:
- проводится содержательный анализ предметной области,
- выделяются основные понятия и их взаимосвязи,
- определяются методы решения задач.
3) На этапе формализации:
- выбираются программные средства разработки ЭС,
- определяются способы представления всех видов знаний,
- формализуются основные понятия.
4) На этапе реализации (наиболее важном и трудоёмком) осуществляется наполнение экспертом БЗ, при котором процесс приобретения знаний разделяют:
- на "извлечение" знаний из эксперта,
48
- на организацию знаний, обеспечивающую эффективную работу
ЭС,
- на представление знаний в виде, понятном для ЭС.
Процесс приобретения знаний осуществляется инженером по знаниям на основе деятельности эксперта.
5) На этапе тестирования эксперт и инженер по знаниям с использованием диалоговых и объяснительных средств проверяют компетентность
ЭС. Процесс тестирования продолжается до тех пор, пока эксперт не решит, что система достигла требуемого уровня компетентности.
6) На этапе опытной эксплуатации проверяется пригодность ЭС для
конечных пользователей. По результатам этого этапа возможна существенная модернизация ЭС.
Процесс создания ЭС не сводится к строгой последовательности
этих этапов, так как в ходе разработки приходится неоднократно возвращаться на более ранние этапы и пересматривать принятые там решения.
2. Участники процесса проектирования экспертной системы.
Эксперт – это человек, способный ясно выражать свои мысли и
пользующийся репутацией специалиста, умеющего находить правильные
решения проблем в конкретной предметной области. Эксперт использует
свои приёмы и ухищрения, чтобы сделать поиск решения более эффективным, и ЭС моделирует все его стратегии.
Инженер знаний – человек, как правило, имеющий познания в информатике и искусственном интеллекте и знающий, как надо строить ЭС.
Инженер знаний опрашивает экспертов, организует знания, решает, каким
образом они должны быть представлены в ЭС, и может помочь программисту в написании программ.
Средство построения ЭС – это программное средство, используемое
инженером знаний или программистом для построения ЭС. Этот инструмент отличается от обычных языков программирования тем, что обеспечивает удобные способы представления сложных высокоуровневых понятий.
Пользователь – это человек, который использует уже построенную
ЭС. Так, пользователем может быть юрист, использующий её для квалификации конкретного случая; студент, которому ЭС помогает изучать информатику и т. д. Термин пользователь несколько неоднозначен. Обычно
он обозначает конечного пользователя.
49
Однако из схемы следует, что пользователем может быть:
- создатель инструмента, отлаживающий средство построения ЭС;
- инженер знаний, уточняющий существующие в ЭС знания;
- эксперт, добавляющий в систему новые знания;
- клерк, заносящий в систему текущую информацию.
3. Особенности эксплуатации и режимы работы экспертной системы.
ЭС обладает двумя отличительными чертами:
1. Прозрачность: ЭС должна быть понятна как разработчику, так и
пользователю. В ЭС часто для повышения прозрачности предметноориентированные знания отделяются от знаний, обеспечивающих получение решения и носящих универсальный характер. Это позволяет исследовать и модифицировать базу знаний, содержащую предметные знания.
2. Качество работы, которое зависит от объема и ценности знаний,
заложенных в программе, т.е. ЭС должна накапливать предельно детализированные и выверенные предметно-ориентированные знания. Знания,
которые должны быть получены, представляют набор специальных фактов, процедур, оценок и правил принятия решений в определенной узкой
предметной области.
В работе ЭС можно выделить два основных режима: режим приобретения знаний и режим решения задачи (режим консультации или режим
использования). В режиме приобретения знаний общение с ЭС осуществляет эксперт (при помощи инженера знаний).
Используя компонент приобретения знаний, эксперт описывает проблемную область в виде совокупности фактов и правил. Другими словами,
"наполняет" ЭС знаниями, которые позволяют ей самостоятельно решать
задачи из проблемной области. Таким образом, если для традиционной
информационной системы характерны этапы алгоритмизации, программирования и отладки, которые реализует программист, то в экспертных
50
системах конечный продукт создаёт эксперт, вообще говоря, не владеющий программированием.
В режиме консультаций общение с ЭС осуществляет конечный
пользователь, которого интересует результат и (или) способ его получения. Необходимо отметить, что в зависимости от назначения ЭС пользователь может:
* не быть специалистом в данной предметной области, и в этом случае он обращается к ЭС за результатом, который не умеет получить сам;
* быть специалистом, и в этом случае он обращается к ЭС с целью
ускорения получения результата, возлагая на ЭС рутинную работу.
Следует отметить, что в отличие от традиционных программ ЭС при
решении задачи не только исполняют предписанную алгоритмом последовательность операций, но и сама предварительно формирует её.
Хорошо построенная ЭС имеет возможность самообучаться на решаемых задачах, пополняя автоматически свою БЗ результатами полученных выводов и решений.
Тема 11. Типы и инструментарий разработок экспертных систем
1. Типы разработок ЭС
2. Основные инструментальные средства проектирования экспертных систем.
1. Типы разработок ЭС
ЭС должна быть опробована, усовершенствована и протестирована в
лабораторных условиях, прежде чем будет передана в опытную эксплуатацию.
ЭС развиваются как и их средства построения от экспериментальных
до коммерческих. Но разделяют 5 уровней разработки ЭС.
1.
Демонстрационный прототип решает некоторую основную
часть задачи. Создается для двух целей: 1. Убедить финансирующую организацию, что данная ЭС может быть эффективно использована для решения данных задач. 2. Проверить концепции постановки задачи, и представление данных из предметной области. Обычно содержит 50-100
правил, работает на 2-3 пробных случаях и требует до 3 месяцев на его
разработку.
2.
Большинство ЭС доведены до уровня исследовательского прототипа. Это программы среднего размера, способные показать качество
работы ЭС на ряде пробных случаев. Но они легко уязвимы, терпят провал, когда задача находится вблизи границы ее разрешения. Могут возникать и ошибки из-за недостаточного тестирования. Типичный исследовательский прототип содержит 200-500 правил, хорошо работает на большом числе пробных случаев, требует на разработку 1-2 года.
51
3.
Уровень опытной эксплуатации. Это достаточно большие программы, которые не один раз пересматривались. Они умеренно надежны,
имеют удобный и дружественный интерфейс и ориентированы на нужды
конкретного пользователя. Содержат 500-1000 правил, опробованы на
всех тестах и требуют на разработку 2-3 года.
4.
Промышленный прототип – эти системы представляют большие программы, подвергнутые интенсивной проверке в условиях опытной
эксплуатации, переписанные на более высоком эффективном языке с целью увеличения скорости работы и уменьшения необходимой машинной
памяти. Типичный промышленный тип – это программы, охватывающие
500-1500 правил, обеспечивающих точное, быстрое и эффективное решение. Требует на разработку 2-4 года.
5.
Коммерческая система – это немногие ЭС, эксплуатируемые на
регулярной коммерческой основе. Такие системы содержат свыше 3000
правил, частота правильных заключений 90-95% и требует на разработку
4-6 лет.
2. Основные инструментальные средства проектирования экспертных систем.
Языки программирования, применяемые для работы в области ЭС, –
это, как правило, проблемно-ориентированные языки как PASCAL, FORTRAN или языки обработки текстов – LISP и PROLOG. Проблемноориентированные языки разработаны для специального класса задач: например в научных, математических и статистических исследованиях.
Языки обработки текстов разработаны для прикладных областей искусственного интеллекта. Например, LISP имеет механизмы для манипулирования символами в форме списковых структур. LISP и PROLOG неуклонно завоевывают популярность. Популярность языков основывается на нескольких их свойствах: легком манипулировании символами, автоматическим управлением памятью, развитом редактировании и средств отладки,
едином подходе в представлении программ.
Лисп существует в двух вариантах: Интерлисп, Мэклисп (имеют
различные средства поддержки).
Языки программирования подобные Лиспу предоставляют гибкость
разработчику ЭС, но никак не подсказывают ему, как представлять знания
или как построить механизм доступа к базе знаний.
Языки инженерии знаний обладают меньшей гибкостью, поскольку
разработчик системы должен пользоваться схемой управления с помощью
механизма выводов.
Языки инженерии можно разделить на скелетные и универсальные.
52
Скелетный язык – это ‘раздетые’ ЭС без специальных предметных
знаний.
Скелетные системы обеспечивают структуризацию знаний и готовые
механизмы выводов. Но им не хватает общности и гибкости. Они приложены только к узкому классу проблем и сильно ограничивают возможности разработчика ЭС.
Универсальные языки могут быть применены к проблемам различного типа в различных прикладных областях. Они обеспечивают большие
возможности управления поиском данных и доступом к ним, чем скелетные системы, но их труднее использовать.
Вспомогательные средства построения ЭС: состоят из программ,
оказывающих помощь в приобретении знаний у эксперта и представление
их, а также программ, которые помогают разработать проекты ЭС. Этих
средств значительно меньше и они делятся на две группы:
−
средства проектирования систем;
−
средства приобретения знаний.
Системы AGE, TIMM, EXPERTEASE – это примеры средств проектирования системы. TEIRESIAS ROGET – это пример средства приобретения знаний.
Система TEIRESIAS оказывает помощь в приобретении знаний от
эксперта в БЗ.
Система приобретает новые правила из предметной области через
диалог с экспертом.
Система AGE состоит из набора компонент, которые могут быть
смонтированы, чтобы образовалась часть ЭС.
Вспомогательные средства включают также средства поддержки –
вспомогательные программы, которые прилагаются к средствам построения ЭС, чтобы упростить его.
Рассмотрим подробнее средства объяснения. Некоторые системы
имеют встроенный механизм объяснения, такие как ENYCIN. В других
нет этого механизма рассуждения, а надо его использовать. Существует
несколько типов механизма объяснения:
−
ретроспективное распределение;
−
гипотетическое распределение;
−
контрафактическое распределение.
При первом случае объясняется, как система достигла конкретного
состояния. Система может описать правило, которое привело к заключению или часть цепочки правил. Во втором случае - система объясняет, что
получилось, если бы конкретный факт или правило были другими. В
третьем случае система объясняет, почему ожидаемое заключение не получилось.
53
В качестве инструментария для создания ЭС могут служить:
−
процедурные языки программирования, ориентированные на
обработку символьной информации (LISP, INTERLISP и др.);
−
языки инженерии знаний, т.е. языки ориентированные на разработку любой ЭС (PROLOG, OPS-5, KRL, LOOPS, ПЛЭНЕР и др.);
−
средства автоматизации процесса конструирования, использования и модификации ЭС (RLL, HEARSAY-III, TEIRESIAS и др.);
−
пустые базовые ЭС, не содержащие знаний конкретной области
(EMYCIN, KAS, GURU, ЭКСПЕРТ-МИКРО).
Под инструментарием понимается также и специализации участников создания ЭС. Это:
1)
эксперт той предметной области;
2)
инженер по знаниям – специалист по разработке ЭС;
3)
программист, осуществляющий модификацию и согласование
инструментальных средств.
Тема 12. Общие сведения о функциональном подходе к программированию
1.
История возникновения функционального программирования
2.
Основы функционального программирования
1 История возникновения функционального программирования
Традиционное программирование родилось в 40-х годах 20 века, когда велась разработка первых электронно-вычислительных машин (ЭВМ).
Его основой послужила концепция фон Неймана о хранимой программе
автоматических вычислений по заданному алгоритму. Существенными
чертами такой программы служили, во-первых, строгая последовательность в выполнении ее элементарных шагов и, во-вторых, возможность
хранения и изменения программы наряду с данными для вычислений в
общей с ними памяти. Таким образом, программа сама становилась объектом обработки вместе с арифметическими значениями, над которыми,
собственно, и должны были производиться все действия.
Когда появились первые компьютеры, то их устройство следовало
принципам, сформулированным фон Нейманом (архитектура фон Неймана). Исполнение программ в первых электронно-вычислительных машинах сводилось к выполнению арифметическим устройством (позже оно
стало называться процессором) элементарных шагов, называемых коман54
дами, которые строго последовательно производили определенные действия над арифметическими значениями или другими командами, хранящимися в оперативной памяти компьютера. Изменять команды нужно было
для того, чтобы организовать циклическое повторение участков программы и своевременное завершение таких повторений.
В конце 50-х годов 20 века появились первые языки программирования высокого уровня, в них уже произошел существенный отход от принципов фон Неймана. Во-первых, программа раз и навсегда была отделена
от данных. Во-вторых, во время исполнения программы ее текст оставался
неизменным, а организация циклического повторения команд в ходе
исполнения программы была возложена на систему программирования, которая уже и должна была перевести (транслировать) текст программы в систему команд компьютера так, чтобы ее исполнение происходило в соответствии с написанным текстом. Единственный принцип, остававшийся неизменным, был принцип последовательного исполнения, в
соответствии с которым исполнение программы можно было разложить на
строго последовательные элементарные шаги алгоритма. Поэтому до сих
пор программирование в традиционном стиле часто называют «фонНеймановским».
Со временем принцип последовательного исполнения стал серьезным препятствием для развития компьютерной техники. Самым узким местом вычислительных систем уже долгое время остается тот самый процессор, который последовательно исполняет элементарные команды. Конечно, скорость работы современных процессоров не сравнить со скоростью работы арифметических устройств первых ЭВМ, однако, производительность компьютеров сейчас, как и раньше, ограничена, в основном,
именно этим центральным устройством. Именно скорость работы центрального процессора имеет решающее значение при определении общей
производительности компьютера.
Скорость работы процессора стала зависеть уже не столько от его
архитектуры и технологических элементов, сколько просто от его размеров, потому что на скорость работы решающее влияние стала оказывать
скорость прохождения сигналов по цепям процессора, которая, как известно, не может превысить скорости света. Чем меньше процессор, тем
быстрее смогут внутри него проходить сигналы, и тем больше оказывается конечная производительность процессора. Размеры процессора уменьшились многократно, однако, все труднее стало отводить от такого миниатюрного устройства вырабатываемое при работе его элементов тепло.
Перед производителями вычислительной аппаратуры встал очень серьезный вопрос: дальнейшее повышение производительности стало почти невозможным без изменения основополагающего принципа всего современного программирования -последовательного исполнения команд.
55
Конечно, можно так спроектировать вычислительную систему, чтобы в ней могли одновременно работать несколько процессоров, но, к сожалению, это почти не дает увеличения производительности, потому что
все программы, написанные на традиционных языках программирования,
предполагают последовательное выполнение элементарных шагов алгоритма почти так же, как это было во времена фон Неймана. Время от времени предпринимаются попытки ввести в современные языки программирования конструкции для параллельного выполнения фрагментов кода,
однако языки "сопротивляются". Оказывается, думать об организации параллельного выполнения фрагментов программы – это довольно сложная
задача, которая успешно решается человеком только для весьма ограниченных случаев.
Проблему можно решать различными способами. Во-первых, можно
попробовать написать специальную программу, которая могла бы проанализировать имеющийся программный текст и автоматически выделить в
ней фрагменты, которые можно выполнять параллельно. К сожалению,
такой анализ произвольного программного кода очень труден. Последовательность выполнения шагов алгоритма очень трудно предсказать по
внешнему виду программы, даже если программа «хорошо структурирована». Второй способ перейти к параллельным вычислениям -это создать
такой язык программирования, в котором сам алгоритм имел бы не последовательную структуру, а допускал бы независимое исполнение отдельных частей алгоритма. Но против этого восстает весь накопленный программистами опыт написания программ.
Тем не менее, оказалось, что опыт написания программ, не имеющих
строго последовательной структуры, на самом деле есть. Почти одновременно с первым "традиционным" языком программирования -Фортраном
появился еще один совершенно непохожий на него язык программирования - Лисп, для которого последовательность выполнения отдельных частей написанной программы была несущественной. Ветвь программирования, начатая созданием Лиспа, понемногу развивалась с начала 60-х годов
20 века и привела к появлению целой плеяды очень своеобразных языков
программирования, которые удовлетворяли всем требованиям, необходимым для исполнения программ несколькими параллельными процессорами. Во-первых, алгоритмы, записанные с помощью этих языков, допускают сравнительно простой анализ и формальные преобразования программ,
а во-вторых, отдельные части программ могут исполняться независимо
друг от друга. Языки, обладающие такими замечательными свойствами это и есть языки функционального программирования.
Помимо своей хорошей приспособленности к параллельным вычислениям языки функционального программирования обладают еще рядом
приятных особенностей. Программы на этих языках записываются корот56
ко, часто много короче, чем в любом другом традиционном (императивном) языке. Описание алгоритмов в функциональном стиле сосредоточено
не на том, как достичь нужного результата (в какой последовательности
выполнять шаги алгоритма), а больше на том, что должен представлять
собой этот результат.
Пожалуй, единственный серьезный недостаток функционального
стиля программирования состоит в том, что этот стиль не универсальный.
Многие действительно последовательные процессы, такие как поведение
программных моделей в реальном времени, игровые и другие программы,
организующие взаимодействие компьютера с человеком, не выразимы в
функциональном стиле. Тем не менее, функциональное программирование заслуживает изучения хотя бы еще и потому, что позволяет несколько
по-иному взглянуть вообще на процесс программирования, а некоторые
приемы программирования, которые, вообще говоря, предназначены для
написания программ в чисто функциональном стиле, могут с успехом использоваться и в традиционном программировании.
2 Основы функционального программирования
Функциональное программирование - это ветвь программирования,
при котором программирование ведется с помощью определения функций.
Функциональное программирование обладает рядом очень существенных преимуществ, которые не только позволяют ему существовать наряду с традиционным программированием, но и иметь своих поклонников, свою нишу задач и хорошие перспективы на будущее.
Функциональное программирование — представляет собой раздел
дискретной математики, а также парадигму программирования, в которой
выполнение программы представляет собой процесс вычисления какого
либо выражения, которое описывает применение функции к входным
данным.
В Функциональном программировании не предполагается хранения
состояния программы, а механизм решения основывается на вычислении
результатов функции, которая опирается на начальные, исходные данные
и результаты других функций. Следовательно, не предполагает оно и изменяемость этого состояния (в этом и заключается главное отличие от императивного программирования, где переменная, хранящая и позволяющая менять свое значение по мере выполнения заданного алгоритма).
Императивное программирование — это описание процесса вычисления в виде инструкций, которые и изменяют состояние программы.
Структура императивной программы похожа на приказы, которые должен
выполнять компьютер.
Императивные языки программирования противопоставляются
57
функциональным и логическим языкам программирования. Функциональные языки, например, Haskell, не представляют собой последовательность
инструкций и не имеют глобального состояния. Логические языки программирования, такие как Prolog, обычно определяют, что надо вычислить, а не как это надо делать.
Основной концепцией Функционального программирования является представление информации для компьютерной обработки в виде набора
символов. Информация представляется символами, смысл которых может
быть восстановлен по заранее известным правилам. Методы функционального программирования основаны на формальном математическом
языке преобразования и представления формул.
Функциональное программирование отличается от большинства
подходов к программированию тремя важными принципами:
1. Природа данных
Все возможные данные представляются в виде символьных выражений. В LISP Дж. Мак-Карти называл их S-выражениями. Состав выражений и типы их элементов не ограничиваются, и это позволяет использовать его в виде древообразной структуры. Это позволяет локализовать
любые важные подвыражения.
2. Описание обработки символьных выражений
Вторая особенность функционального программирования заключается в том, что описание способов обработки S-выражений предоставляются программами, которые рассматриваются как символьные данные.
Программы состоят из рекурсивных функций над S-выражениями. Определения и вызовы этих функций, так же как и любая информация, представлены в виде S-выражений.
3.Подобие машинным языкам
Система функционального программирования допускает, что программа может интерпретировать и/или компилировать программы, представленные в виде S-выражений. Это сближает методы функционального
программирования с методами низкоуровневое программирования и отличает от традиционной методики применения языков высокого уровня.
Основные следствия из выбранных принципов:
процесс создания и разработки программ разбивается на две
фазы: построение и пошаговое расширение базиса.
рассмотрение программы как реализации алгоритма естественно дополняется табличной реализацией функций, т.е. допустимо исполь58
зование хранимых графиков функций в виде структур из аргументов и соответствующих результатов наряду с процедурами.
прозрачность ссылок обеспечена совпадением значений одинаково выглядящих формул, вычисляемых в одинаковом контексте.
нацеленность на универсальные функции и функционально
полные системы, трудоемкость первичной реализации которых компенсируется надежностью определений и простотой применения.
ФП активно применяется для генерации и выполнения программ,
динамически конструируемых прототипов программ, а также для систем,
применяемых в областях с низкой кратностью повторения отлаженных
решений (в проектировании, в учебе, творчестве) которые ориентируются
на оперативные изменения, улучшения, адаптацию, уточнения и т.д.
Тема 13. История возникновения и классификация функциональных
языков программирования
1.
История функциональных языков
2.
Классификация функциональных языков
1 История функциональных языков
Теоретические тезисы императивного программирования закладывались еще в 30-х годах Джоном фон Нейманом и Аланом Тьюрингом.
Теория которая в последствии стала основой функционального подхода
также зародилась в 20-х 30-х годах. Основными разработчиками функционального программирования можно рассматривать Германского ученого — Мозеса Шёнфинкеля, Английского — Хаскелла Карри, а также
Алонзо Чёрча из США.
Теория так и была бы теорией, если бы в 50-х годах Джон МакКарти не разработал первый почти функциональный язык программирования—Lisp, стоит отметить что на протяжении длительного времени оставался единственным языком функционального программирования.
Хоть в настоящее время Lisp все еще продолжает использоваться в
решении задач ФП, его доля с каждым годом падает поскольку Lisp не
может удовлетворить часть современных запросов. Во многом следствием
этого стала постоянно возрастающая сложность программного обеспечения.
Благодаря этому, типизации стали отводить все большую роль. Начиная с конца 70-х – начала 80-х годов ведется активная разработка моделей типизации которая подходила бы к функциональным языкам. Эти
годы отмечены появлением множества типизированных функциональных
языков: таких как Scheme, ML, Miranda, Hope, Clean и многие другие.
Вдобавок к этому постоянно расширяется число диалектов.
59
Но вместе с тем бурное развитие новых языков и диалектов привело
к тому, что практически каждая группа, которая занималась функциональным программированием, использовала свой язык программирования.
Что естественно препятствовало и тормозило дальнейшее развитие, и распространение этих языков, а также порождало более мелкие проблемы.
Для исправления ситуации, объединенная группа ведущих исследователей
в области функционального программирования решила соединить достоинства различных языков в новом универсальном функциональном языке.
Первая реализация этого языка, была создана в начале 90-х годов и был
назван в честь Карри Хаскелла. Последним действующим стандартом
этого языка является Haskell 98.
Программирование с использованием математических понятий
функций вызывает трудности, из за этого функциональные языки, в какой
то степени предоставляют и возможности реализованные в императивных
языка, что ухудшает дизайн программы.
Тексты программ функциональных языков программирования описывают «как решить задачу», однако не определяют последовательность
действий выполняемых для решения.
К наиболее известным языкам функционального программирования
можно отнести следующие:
LISP — (разработал Джон МакКарти в 1958 году) язык ФП и
множество его диалектов.
Erlang — (разработал Joe Armstrong в 1986году) язык функционального программирования с поддержкой процессов.
F# — функциональный язык из семейства ML предназначенный для платформы .NET.
Miranda (разработал Дэвид Тёрнер в 1985 году). Данный язык
впоследствии дал развитие языку Haskell.
Nemerle — гибридный язык функционального/императивного
программирования.
Haskell — чисто функциональный язык. Который был назван в
честь Хаскелла Карри.
Ещё не полностью функциональные изначальные версии и Lisp и
APL внесли значимый вклад в создание, а также развитие функционального программирования. Более поздние версии языка Lisp, такие как, например Scheme, а также различные варианты APL могли поддерживать
все возможные свойства и концепции функционального языка.
Обычно, интерес к языкам функционального программирования,
особенно к чисто функциональным, был скорее научный, нежели коммерческий. Однако, такие языки как Haskel, lErlang, OCaml и Scheme нашли
60
применение в индустрии коммерческого программирования.
2 Классификация функциональных языков
В качестве яркого примера чисто функционального языка можно
взять Haskell. Однако стоит отметить, что большинство из функциональных языков программирования являются гибридными и содержат свойства, как функциональных языков, так и императивных.
Еще функциональные языки можно разделить на строгие и нестрогие. К нестрогим относят те, которые могут поддерживать отложенные
вычисления (F#), иными словами аргументы функции будут вычисляться
в том случае, когда они действительно понадобятся при вычислении
функции.
Концепции
Некоторые концепции и парадигмы специфичны для функционального программирования и в основном чужды императивному программированию. Тем не менее, языки программирования обычно представляют
собой гибрид нескольких парадигм программирования.
Функции высших порядков
Функции высших порядков — это такие функции, которые в качестве аргументов могут принимать и возвращать другие функции. В математике такие функции чаще всего называют оператором, (интегральный
оператор).
Чистые функции
Чистые — это функции, не имеющие побочных эффектов вводавывода информации, а так же памяти (такие функции зависят исключительно от своих параметров и возвращают только свой результат).
Чистые функции обладают несколькими полезными свойствами, которые можно использовать для оптимизации кода:
•
Когда результат чистой функции не используется он может
быть удален без вреда для остальных выражений.
•
Результат вызова чистой функции можно сохранить в таблице
значений вместе с аргументами вызова. Если же в дальнейшем функции
вызываются с этими же аргументами, то ее результат можно взять напрямую из таблицы, а не вычислять.
Хотя большинство из компиляторов императивных языков программирования распознают чистые функции и удаляют общие подвыражения для вызовов чистых функций, они не могут делать это всегда для
61
предварительно скомпилированных библиотек, которые, не предоставляют эту информацию.
Рекурсия
В языках функционального программирования для реализации цикла
обычно используется рекурсия. Строго говоря, функциональное программирования не располагает таким понятия, как цикл. Рекурсивные функции осуществляют вызов самих себя, что позволяет операции выполняться
снова и снова. Для применения рекурсии может понадобиться большой
стек, но это можно избежать в случае хвостовой рекурсии.
Рекурсивные функции можно обобщать с помощью функций высших порядков, используя, например, анаморфизм и ката морфизм. Функции такого рода играют роль такого понятия как цикл в императивных
языках программирования.
Особенности
Основной особенностью ФП, которая определяет как преимущества,
так и недостатки данной парадигмы, является реализации в ней модели
вычисления без состояния. Если императивная программа на любом этапе
выполнения имеет свое состояние, и производит побочные эффекты, то
чисто функциональная программа ни целиком, ни частями состояния не
имеет и побочных эффектов.
Сильные стороны функциональных языков программирования
Повышение надёжности кода
Повышенная надёжность кода — выполняющаяся за счёт чёткой
структуризации и отсутствия необходимости отслеживания побочных эффектов является сильной стороной программирования. Все функции работают исключительно с локальными данными, и работают с ними всегда
одинаково, независимо от того, как, где и при каких обстоятельствах она
вызывается.
Удобство организации модульного тестирования
Поскольку функция в ФП не порождает побочные эффекты, менять
объекты нельзя как внутри области видимости, так и снаружи. Единственным эффектом от вычисления функции является возвращаемый ей результат, а единственный фактор, который оказывает влияние на результат —
это значения аргументов.
Возможности оптимизации при компиляции
Еще одной положительной особенностью ФП является возможность
описывать программу в «декларативном» виде, когда жесткая последовательность выполнения многих операций, необходимых для вычисления
62
результата, в явном виде не задаётся, а формируется автоматически в процессе вычисления функций.
Возможности параллелизма
Ещё одним из преимуществ функциональных программ является то,
что они предоставляют широчайшие возможности для автоматического
распараллеливания вычислений.
Недостатки
Недостатки ФП вытекают из его же особенностей. Отсутствие присваиваний приводит к необходимости постоянного выделения и автоматического освобождения памяти, поэтому в системе исполнения функциональных программы обязательным компонентом становится высокоэффективный сборщик “мусора”. Нестрогая модель приводит к непредсказуемому порядку вызова функций, что создает неудобства при вводевыводе информации, где важен порядок выполнения операций. Кроме того, не являются чистыми, поскольку способны вернуть различные значения для одних и тех же аргументов, и для решения этой проблемы требуются определенные ухищрения.
Тема 14. Языки функционального программирования, их свойства и решаемые задачи.
1
Языки функционального программирования
2
Свойства функциональных языков
3
Задачи, решаемые с использованием функциональных
языков
1 Языки функционального программирования
Lisp (List processor). Считается первым функциональным языком
программирования. Нетипизирован. Содержит массу императивных
свойств, однако в общем поощряет именно функциональный стиль программирования. При вычислениях использует вызов-по-значению. Существует объектно-ориентированный диалект языка — CLOS.
ISWIM (If you See What I Mean). - императивный язык программирования с функциональным ядром. Разработан Питером Лэндином в 1956
году для демонстрации того, каким может быть язык функционального
программирования. Вместе с языком Лэндин разработал и специальную
виртуальную машину для исполнения программ на ISWIM'е. Эта виртуальная машина, основанная на вызове-по-значению, получила название
SECD-машины. На синтаксисе языка ISWIM базируется синтаксис многих
функциональных языков. На синтаксис ISWIM похож синтаксис ML, особенно Caml.
63
Scheme. Диалект Lisp'а, предназначенный для научных исследований в области компьютерных технологий. При разработке Scheme был
сделан упор на элегантность и простоту языка. Благодаря этому язык получился намного меньше, чем Common Lisp.
ML (Meta Language). Семейство строгих языков с развитой полиморфной системой типов и параметризуемыми модулями. ML преподается во многих западных университетах (в некоторых даже как первый язык
программирования).
Standard ML. Один из первых типизированных языков функционального программирования. Содержит некоторые императивные свойства, такие как ссылки на изменяемые значения и поэтому не является чистым. При вычислениях использует вызов-по-значению. Очень интересная
реализация модульности. Мощная полиморфная система типов. Последний стандарт языка — Standard ML-97, для которого существует формальные математические определения синтаксиса, а также статической и динамической семантик языка.
CAML
(Caml
Light и Objective
Caml)
это объектноориентированный язык программирования, разработанный для создания
более безопасных и защищенных программ. Как и Standard ML принадлежит к семейству ML. Objective Caml отличается от Caml Light в основном
поддержкой классического объектно-ориентированного программирования. Также как и Standard ML строгий, но имеет некоторую встроенную
поддержку отложенных вычислений.
Miranda. Разработан Дэвидом Тернером, в качестве стандартного
функционального языка, использовавшего отложенные вычисления. Имеет строгую полиморфную систему типов. Как и ML преподаётся во многих университетах. Оказал большое влияние на разработчиков языка
Haskell.
Haskell. Один из самых распространённых нестрогих языков. Имеет
очень развитую систему типизации. Несколько хуже разработана система
модулей. Последний стандарт языка — Haskell 98.
Gofer (GOod For Equational Reasoning). Упрощённый диалект
Haskell'а. Предназначен для обучения функциональному программированию.
Clean. Специально предназначен для параллельного и распределённого программирования. По синтаксису напоминает Haskell. Чистый. Использует отложенные вычисления. С компилятором поставляется набор
библиотек (I/O libraries), позволяющих программировать графический
пользовательский интерфейс под Win32 или MacOS.
2 Свойства функциональных языков
В качестве основных свойств функциональных языков кратко рас64
смотрим следующие:
•
краткость и простота;
•
строгая типизация;
•
модульность;
•
функции — это значения;
•
чистота (отсутствие побочных эффектов);
•
отложенные (ленивые) вычисления.
Краткость и простота
Программы на функциональных языках обычно намного короче и
проще, чем те же самые программы на императивных языках.
Кроме того, все операции с памятью выполняются автоматически.
При создании какого-либо объекта под него автоматически выделяется
память. После того как объект выполнит своё предназначение, он вскоре
будет также автоматически уничтожен сборщиком мусора, который является частью любого функционального языка.
Ещё одним полезным свойством позволяющим сократить программу
является встроенный механизм сопоставления с образцом. Это позволяет
описывать функции как индуктивные определения.
Строгая типизация
Практически все современные языки программирования являются
строго типизированными языками (возможно, за исключением JavaScript и
его диалектов, не существует императивных языков без понятия "тип").
Строгая типизация обеспечивает безопасность. Программа, прошедшая
проверку типов просто не может выпасть в операционную систему с сообщением, подобным "access violation", особенно это касается таких языков, как C/C++ и Object Pascal, где применение указателей является типичным способом использования языка. В функциональных языках большая часть ошибок может быть исправлена на стадии компиляции, поэтому
стадия отладки и общее время разработки программ сокращаются. Вдобавок к этому строгая типизация позволяет компилятору генерировать более
эффективный код и тем самым ускорять выполнение программ.
Ещё одной разновидностью полиморфизма является перегрузка
функций, позволяющая давать различным, но в чём-то схожим функциям
одинаковые имена. Типичным примером перегруженной операции является обычная операция сложения. Функции сложения для целых чисел и чисел с плавающей точкой различны, однако для удобства они носят одно и
то же имя. Некоторые функциональные языки помимо параметрического
полиморфизма, поддерживают и перегрузку операций.
В языке C++ имеется такое понятие, как шаблон, которое позволяет
программисту определять полиморфные функции, подобные quickSort. В
стандартную библиотеку C++ STL входит такая функция и множество
65
других полиморфных функций. Но шаблоны C++, как и родовые функции
Ada, на самом деле порождают множество перегруженных функций, которые, кстати, компилятор должен каждый раз компилировать, что неблагоприятно сказывается на времени компиляции и размере кода. А в функциональных языках полиморфная функция quickSort — это одна единственная функция.
В некоторых языках, например в Ada, строгая типизация вынуждает
программиста явно описывать тип всех значений и функций. Чтобы избежать этого, в строго типизированные функциональные языки встроен специальный механизм, позволяющий компилятору определять типы констант, выражений и функций из контекста. Этот механизм называется механизмом вывода типов. Известно несколько таких механизмов, однако
большинство из них являются разновидностями модели типизации Хиндли-Милнера, разработанной в начале 80-х годов XX века. Таким образом,
в большинстве случаев можно не указывать типы функций.
Модульность
Механизм модульности позволяет разделять программы на несколько сравнительно независимых частей (модулей) с чётко определёнными
связями между ними. Тем самым облегчается процесс проектирования и
последующей поддержки больших программных систем. Поддержка модульности не является свойством именно функциональных языков программирования, однако поддерживается большинством таких языков. Существуют очень развитые модульные императивные языки. В качестве
примеров подобных языков можно привести Modula-2 и Ada-95.
Функции — это значения
В функциональных языках (равно как и вообще в языках программирования и математике) функции могут быть переданы другим функциям в качестве аргумента или возвращены в качестве результата. Функции,
принимающие функциональные аргументы, называются функциями высших порядков или функционалами.
Чистота (отсутствие побочных эффектов)
В императивных языках функция в процессе своего выполнения может читать и модифицировать значения глобальных переменных и осуществлять операции ввода/вывода. Поэтому, если вызвать одну и ту же
функцию дважды с одним и тем же аргументом, может случиться так, что
в качестве результата посчитаются два различных значения. Такая функция называется функцией с побочными эффектами.
Описывать функции без побочных эффектов позволяет практически
любой язык. Однако некоторые языки поощряют или даже требуют от
функции побочных эффектов. Например, во многих объектноориентированных языках в функцию член класса передаётся скрытый параметр (чаще он называется this или self), который эта функция неявно
66
модифицирует.
В чистом функциональном программировании оператор присваивания отсутствует, объекты нельзя изменять и уничтожать, можно только
создавать новые путем декомпозиции и синтеза существующих. О ненужных объектах позаботится встроенный в язык сборщик мусора. Благодаря
этому в чистых функциональных языках все функции свободны от побочных эффектов. Однако это не мешает этим языкам имитировать некоторые
полезные императивные свойства, такие как исключения и изменяемые
массивы. Для этого существуют специальные методы.
Каковы же преимущества чистых функциональных языков? Помимо
упрощения анализа программ есть ещё одно весомое преимущество — параллелизм. Раз все функции для вычислений используют только свои параметры, мы можем вычислять независимые функции в произвольном порядке или параллельно, на результат вычислений это не повлияет. Причём
параллелизм этот может быть организован не только на уровне компилятора языка, но и на уровне архитектуры. В нескольких научных лабораториях уже разработаны и используются экспериментальные компьютеры,
основанные на подобных архитектурах. В качестве примера можно привести Lisp-машину.
Отложенные вычисления
В традиционных языках программирования (например, C++) вызов
функции приводит к вычислению всех аргументов. Этот метод вызова
функции называется вызов-по-значению. Если какой-либо аргумент не
использовался в функции, то результат вычислений пропадает, следовательно, вычисления были произведены впустую. В каком-то смысле противоположностью вызова-по-значению является вызов-по-необходимости.
В этом случае аргумент вычисляется, только если он нужен для вычисления результата. Примером такого поведения можно взять оператор конъюнкции всё из того же C++ (&&), который не вычисляет значение второго
аргумента, если первый аргумент имеет ложное значение.
Если функциональный язык не поддерживает отложенные вычисления, то он называется строгим. На самом деле, в таких языках порядок
вычисления строго определен. В качестве примера строгих языков можно
привести Scheme, Standard ML и Caml.
Языки, использующие отложенные вычисления, называются нестрогими. Haskell — нестрогий язык, так же как, например, Gofer и Miranda.
Нестрогие языки зачастую являются чистыми.
Очень часто строгие языки включают в себя средства поддержки некоторых полезных возможностей, присущих нестрогим языкам, например
бесконечных списков. В поставке Standard ML присутствует специальный
модуль для поддержки отложенных вычислений. А Objective Caml помимо
этого поддерживает дополнительное зарезервированное слово lazy и кон67
струкцию для списков значений, вычисляемых по необходимости.
3 Задачи, решаемые с использованием функциональных языков
В качестве задач, традиционно рассматриваемых в курсах функционального программирования, можно выделить следующие:
1. Получение остаточной процедуры.
Если даны следующие объекты:
P (x1, x2, ..., xn) — некоторая процедура.
x1 = a1, x2 = a2 — известные значения параметров.
x3, ..., xn — неизвестные значения параметров.
Требуется получить остаточную процедуру P1 (x3, ..., xn). Эта задача
решается только на узком классе программ.
2. Построение математического описания функций.
Пусть имеется программа P. Для неё определены входные значения и выходные значения . Требуется построить математичекое описание
функции
f : Dx1, ..., Dxn -> Dy1, ..., Dym.
3. Определение формальной семантики языка программирования.
4. Описание динамических структур данных.
5. Автоматическое построение "значительной" части программы по описанию структур данных, которые обрабатываются создаваемой программой.
6. Доказательство наличия некоторого свойства программы.
7. Эквивалентная трансформация программ.
Все эти задачи достаточно легко решаются средствами функционального программирования, но практически неразрешимы в императивных языках.
68
Дополнительная литература
1. Галяев В.С. Учебно-методический комплекс по дисциплине "Интеллектуальные информационные системы". Махачкала: ДГИНХ. 2006.
64 с.
2. Рыбина Г.В. Основы построения интеллектуальных систем: учебное
пособие. Издательство: Финансы и статистика; ИНФРА-М, 2010 г.,
431 с.
3. Глухих И. Н. Интеллектуальные информационные системы. Издательство: Академия, 2010 г., 112 стр.
4. Андрейчиков А. В., Андрейчикова О. Н. Интеллектуальные информационные системы. Издательство: Академия, 2010 г., 112 стр.
5. Буреш О. В., Жук М. А. Интеллектуальные информационные системы управления социально-экономическими объектами. Издательство: Красанд, 2011 г., 192 стр.
69