Министерство образования и науки российской федерации федеральное агентство по образованию санктпетербургский государственный университет
 Скачать 1.41 Mb.
|
|
Данный формат не предназначен для чтения человеком. Редакторы семантических документов, например, наиболее распространенный редактор онтологий Protégé ( http://protege.stanford.edu/ ), дают возможность вводить и редактировать факты в экранных формах (фреймах), как показано ниже. В настоящее время создание RDF/OWL документов ведется отдельными энтузиастами. Количество документов в Интернете невелико, и их можно найти 87 с помощью специального поискового сервера, например, SWOOGLE ( http://swoogle.umbc.edu/ ). Развитие проекта сдерживается по многим причинам. В основном это отсутствие быстрой и прямой выгоды от создания семантических ресурсов, сложность формализации знаний и отсутствие универсальных агентов для извлечения знаний. Представленные в Интернете реализации интеллектуальных агентов ограничиваются студенческими разработками вроде путеводителя по пивным города Саутхемптон ( http://www.twine.com/item/11by40gxk-p1/southampton-pub-guide-in-rdf ) и винного агента, советующего, какое вино лучше употребить с каждым из блюд ( http://ksl.stanford.edu/people/dlm/webont/wineAgent/ ). 88 8. Домашние задания и лабораторные работы 8.1. Домашнее задание №1. Изучение работы Prolog программы Цель домашнего задания: изучение работы Prolog программы на примере решения задачи сортировки двумя методами: сортировка методом вставки и так называемая «быстрая» сортировка. Текст обоих программ приведен ниже. /************** Сортировка методом вставки **************/ insrtsort([],[]). insrtsort([Head|Tail], ListSorted) :- insrtsort(Tail,TailSorted), insrt(Head,TailSorted,ListSorted). insrt(X, [Y | ListSorted], [Y | ListSorted1]) :- X > Y, !, insrt(X, ListSorted, ListSorted1). insrt(X,ListSorted, [X | ListSorted]). /************** Быстрая сортировка *****************/ fastsort([],[]). fastsort([Head | Tail], ListSorted) :- split(Head, Tail, TailLess, TailGreater), fastsort(TailLess,TailLessSorted), fastsort(TailGreater,TailGreaterSorted), append(TailLessSorted, [Head | TailGreaterSorted], ListSorted). split(_, [], [], []). split(X, [H | T], [H | TL], TG) :- H < X, !, split(X, T, TL, TG). split(X, [H | T], TL, [H | TG]) :- split(X, T, TL, TG). В качестве исходных данных использовать собственную дату рождения в следующем виде: [D,D,M,M,Y,Y,Y,Y], например, дата рождения 20.09.1984. Сортируемый список будет [2,0,0,9,1,9,8,4]. Требуется: 1) запустить каждую из программ на выполнение в режиме трассировки; 2) записать структурированную трассу программы, отражающую рекурсивную вложенность предикатов; 3) описать логику предикатов в каждой из программ; 4) выбрать критерии и сравнить два метода сортировки. Содержание отчета: 1) исходный текст программы с комментариями; 2) структурированная трасса хода выполнения каждой из двух программы; 3) описание логики каждого из методов сортировки; 4) сравнение рассмотренных методов сортировки. 89 8.2. Домашнее задание №2. Изучение алгоритмов поиска Цель задания: Исследование алгоритмов решения задач методом поиска. Описание предметной области. Имеется транспортная сеть, связывающая города СНГ. Сеть представлена в виде таблицы связей между городами. Связи являются двусторонними, т.е. допускают движение в обоих направлениях. Необходимо проложить маршрут из одной заданной точки в другую. Этап 1. Неинформированный поиск. На этом этапе известна только топология связей между городами. Выполнить: 1) поиск в ширину; 2) поиск глубину; 3) поиск с ограничением глубины; 4) поиск с итеративным углублением; 5) двунаправленный поиск. Отобразить движение по дереву на его графе с указанием сложности каждого вида поиска. Сделать выводы. Этап 2. Информированный поиск. Воспользовавшись информацией о протяженности связей от текущего узла, выполнить: 1) жадный поиск по первому наилучшему соответствию; 2) затем, использую информацию о расстоянии до цели по прямой от каждого узла, выполнить поиск методом минимизации суммарной оценки А*. Отобразить на графе выбранный маршрут и сравнить его сложность с неинформированным поиском. Сделать выводы. Таблица связей между городами Город 1 Город 2 Расстояние, км Вильнюс Брест 531 Витебск Брест 638 Витебск Вильюс 360 Воронеж Витебск 869 Воронеж Волгоград 581 Волгоград Витебск 1455 Витебск Ниж.Новгород 911 Вильнюс Даугавпилс 211 Калининград Брест 699 Калиниград Вильнюс 333 Каунас Вильнюс 102 Киев Вильнюс 734 Киев Житомир 131 Житомир Донецк 863 90 Житомир Волгоград 1493 Кишинев Киев 467 Кишинев Донецк 812 С.Петербург Витебск 602 С.Петербург Калининград 739 С.Петербург Рига 641 Москва Казань 815 Москва Ниж.Новгород 411 Москва Минск 690 Москва Донецк 1084 Москва С.Петербург 664 Мурманск С.Петербург 1412 Мурманск Минск 2238 Орел Витебск 522 Орел Донецк 709 Орел Москва 368 Одесса Киев 487 Рига Каунас 267 Таллинн Рига 308 Харьков Киев 471 Харьков Симферополь 639 Ярославль Воронеж 739 Ярославль Минск 940 Уфа Казань 525 Уфа Самара 461 Варианты заданий: Номер варианта Исходный пункт Пункт назначения 1 Мурманск Одесса 2 С.Петербург Житомир 3 Самара Ярославль 4 Рига Уфа 5 Казань Таллин 6 Симферополь Мурманск 7 Рига Одесса 8 Вильнюс Одесса 9 Брест Казань 10 Харьков Ниж.Новгород 91 Расстояние до цели по прямой взять из подходящей географической карты. Правило выбора варианта задания. Дату рождения подвергнуть следующей свертке: (ДД + ММ) mod 10 + 1 = номер варианта. 8.3. Домашнее задание №4. Расчет сети Байеса Цель: Расчет полных и условных вероятностей для различных событий. Предметная область: характеристики студентов Вашего потока. Исходные данные. Выбрать 4 атрибута, характеризующих студентов, и заполнить таблицу следующего вида: Ф.И.О. Получает стипендию Живет в общежитии Подрабатывает Занимается спортом Иванов Нет Да Нет Нет … … … … … Вместо приведенных в качестве примера атрибутов (получает стипендию, живет в общежитии,…) подставить атрибуты, выбранные самостоятельно. Объем таблицы – не менее 25 строк. Заполнение таблицы строго индивидуально. У каждого должен быть свой вариант заполнения. Провести расчеты с использованием сети Байеса. 1. Выбрать зависимые и независимые переменные. Составить сеть Байеса для данного набора переменных. Вычислить все априорные, условные и полные вероятности. 2. Вычислить информативность каждого атрибута по формуле Шеннона. Построить дерево решений, как в разд. 5.3, руководствуюсь данными об информативности атрибутов. Сравнить полученное дерево с выбранным в п.1. разбиением на зависимые и независимые переменные. 3. Добавить в таблицу 5 строк. Пересчитать. Сделать выводы о достаточности (недостаточности) данных. Содержание отчета: 1. Исходная таблица. 2. Граф сети Байеса со всеми вероятностями. 3. Показатели информативности по Шеннону 4. Дерево решений с вероятностями. 5. Выводы. 92 8.4. Лабораторная работа №1. Прогнозирование с помощью нейронной сети Цель работы: Исследование программы NeuroGenetic Optimizer (NGO). Задание: Загрузить в программу NGO котировки акций в соответствии с вариантом: Номер варианта Код Наименование 1 GAZP АО Газпром 2 ГМКНорНик Норильский никель 3 ЛУКОЙЛ НК Лукойл 4 МТС-ао Компания МТС – обыкн. акции 5 Роснефть Роснефть 6 Ростел-ао Ростелеком – обыкн.акции 7 Сбербанк Сбербанк – обыкн.акции 8 Сургнфгс Сургутнефтегаз 9 УРалСвИ-ао Уралсвязинформ – обыкн.акции 10 Уралкалий-ао АО Уралкалий – обыкн.акции Номер варианта выбирается так же, как в домашнем задании №2. Для получения исходных данных войти на сайт http://www.finam.ru/analysis/export/default.asp Выбрать контракт (эмитента акций) в соответствии с вариантом, период не менее полугода, имя файла – на свое усмотрение. Остальные параметры задать, как указано на следующем снимке экрана. 93 Экспортированный файл будет иметь следующий вид (на примере Газпрома). , 94 Экспортированный файл за полгода должен иметь около 1000 строк (8 часов * 5 дней * 25 недель). Для целей прогнозирования использовать только последнее поле (цена закрытия). Выполнить обучение нейронной сети для прогнозирования котировок на следующий час. Использовать временной лаг для порождения массива котировок таким образом, чтобы входными переменными для нейронной сети были значения котировок С i , C i-1 , C i-2 , …, а прогнозироваться должно значение С i+1 . В приведенной ниже таблице показан фрагмент массива данных для обучения, полученный из файла котировок акций Газпрома. Входные переменные Выход C i-4 C i-3 C i-2 C i-1 С i С i+1 277.80 278.20 275.89 274.44 273.90 272.05 278.20 275.89 274.44 273.90 272.05 275.50 275.89 274.44 273.90 272.05 275.50 273.22 274.44 273.90 272.05 275.50 273.22 269.70 Таким образом, прогноз на следующий час строится на основе последовательности котировок за предыдущие пять часов. Содержание отчета: 1. Описание проблемы. 2. График изменения котировок. 3. Выбор способа деления массива данных на наборы для обучения и для тестирования. 3. Скриншоты работы программы NGO в процессе обучения. 4. Описание построенной нейронной сети (число нейронов, количество слоев, типы функций активации). 5.Анализ точности построения и валидация (оценка практической применимости) полученной нейросетевой модели. 8.5. Лабораторная работа № 2. «Создание информационной системы на базе семантической сети» Цель работы: изучение семантической сети как инструмента создания информационных и обучающих систем? А также исследование методов логического вывода на основе правил. Содержание работы: Выбрать предметную область. 95 1. Выбрать способ представления знаний в семантической сети – реляционный граф или граф с центром в глаголе, а также язык представления знаний, русский или иной. Возможно многоязычное представление знаний. 2. Записать факты, составляющие предметную область в нотации программы “Semantic”. Рекомендуемый объем базы знаний – не менее 50 фактов. 3. Снабдить базу знаний онтологиями, в т.ч. правилами (не менее 20), позволяющими извлекать новые факты, а также словарями для поддержки диалога на упрощенном естественном языке. 4. Провести тестирование базы знаний, т.е. убедиться в том, что все правила корректно создают новые факты. Содержание отчета: Цель и назначение разработанной информационной системы. Описание предметной области и словарей. Распечатки файлов базы знаний. Снимки экранов одного из вариантов развития диалога. 96 Литература 1. Стюарт Рассел, Питер Норвиг. Искусственный интеллект:Современный подход. 2-е изд.: пер. с англ. – М.: Изд.дом «Вильямс», 2006. – 1408с.: ил. Парал.тит.англ. 2. www.swi-prolog.org . Официальный сайт разработчиков транслятора SWI- Prolog. 3. www.pdc.dk . Официальный сайт компании Prolog Development Center. 4. http://ru.wikipedia.org/wiki/Семантическая_сеть 5. http://compzed.narod.ru/semseti.htm 6. McDermott, Drew. “Artificial Intelligence Meets Natural Stupidity”, SIGART Newsletter, No.57 (April, 1976), pp. 4-9. 7. T. Berners-Lee, J. Hendler, and O. Lassila, “The Semantic Web,” Scientific American, May, 2001, pp. 34–43. 97 Приложение 1. Описание программы SWI-Prolog Исполняемый файл программы SWI-Prolog размещается в ..\bin\plwin.exe. После запуска появляется окно следующего вида: Для загрузки программы следует вызвать пункт меню “File / Consult…” и выбрать файл с текстом программы, который может быть создан в текстовом редакторе Notepad. Расширение файла по умолчанию .PL. Файл можно создавать и в оболочке программы SWI-Prolog пунктом меню “File / New…”. По умолчанию вызывается редактор Notepad (Блокнот). В составе пакета SWI- Prolog имеется более продвинутый редактор (PCE_EMAX), анализирующий синтаксис Пролог-программы, позволяющий устанавливать точки прерываний и т.п. Чтобы включить редактор PCE_EMAX, необходимо в файле pl.ini удалить комментарии в строке :- set_prolog_flag(editor, pce_emacs). Сделать это можно любым текстовым редактором, либо вызвав пункт меню “Settings / User init file…”. После загрузки в командной строке можно вводить цели. Рассмотрим работу оболочки SWI-Prolog на примере программы вычисления факториала: fact(0,1). fact(N,F) :- N1 is N-1, fact(N1,F1), F is N*F1. Введем в основном окне программы цель: fact(4,F). Программа выдаст ответ: А = 24. В случае ошибок на этапе трансляции либо выполнения Пролог в этом же окне выдает диагностические сообщения. Пользоваться таким 98 режимом неудобно. Лучше воспользоваться отладчиком. Для этого необходимо включить опцию графического отладчика “Debug / Graphical debugger”, затем с помощью пункта меню “Debug / Edit spy points…” включить точку перехвата на интересующий нас предикат, например, в нашем случае на предикат fact, и нажать кнопку с изображением шпиона. После этого нужно в окне Пролога задать цель, и появится окно отладки, которое выглядит следующим образом: Панель Bindings отображает текущие значения переменных, Call Stack – состояние стека, т.е. глубину вложенности рекурсий, наконец, нижняя панель – текст программы, где зеленым цветом выделяется выполняемый предикат. Для пошагового выполнения программы нужно нажимать на кнопку со стрелкой вправо. После максимального углублению в рекурсию стек выглядит следующим образом: 99 После этого Пролог начинает выполнять собирать факториал из запомненных в стеке значений 1!, 2! и 3!. Таким образом, мы можем отслеживать логику работы предикатов и выявлять ошибки. 100 Приложение 2. Описание программы NGO (NeuroGenetic Optimizer) Программа NGO предназначена для нейросетевого моделирования на основе обучения. На вход может подаваться до 500 переменных (в зависимости от лицензии). Бесплатный вариант программы поддерживает до пяти входных переменных. Программа состоит из двух компонентов: программы обучения NGO32260.EXE и программы прогнозирования PRE32150.EXE. Для начала работы с программой обучения необходимо загрузить данные. Рассмотрим порядок подготовки работы NGO на примере ее обучения на вычисление функции синуса. Для этого мы должны подготовить файл, содержащий данные в таком виде (разделители – табуляция): X Sin(X) 0,01 0,01 0,02 0,019999 0,03 0,029996 0,04 0,039989 Пусть такой файл содержит 500 строк и охватывает значения Х от 0 до 5. Чтобы его загрузить, необходимо выбрать пункты меню File / Open / Data / Train/Test… и местоположение текстового файла. Появится окно следующего вида: 101 Необходимо указать, что разделителями являются символы табуляции (Delimiters), а также указать назначение переменных (Input, Output). Если переменные не используются, например, их необходимо игнорировать (Ignore). Если в таблице в нижней части окна первые строки данных пустые, значит, NGO не понимает данный формат. Нужно проверить исходный файл. Важное замечание. Входные данные не подвергаются полному контролю. В частности, NGO не допускает наличия пустых строк в исходном файле, но не диагностирует эту ситуацию. В этом случае программа аварийно завершается на этапе обучения. После ввода исходных данных необходимо настроить программу. Для этого нужно вызвать пункт меню Option / Data… Здесь следует определить, как исходные данные будут делиться на набор для обучения и набор для тестирования. На снимке экрана показано, что для тестирования будет использоваться каждая вторая строка данных. Тестовый набор данных позволяет убедиться в том, что обученная нейронная сеть функционирует правильно, поскольку данные тестового набора в обучении не использовались. В условиях недостаточного количества наблюдений выбор объема тестового набора является критичным: слишком много данных для тестирования (как в данном случае 50 на 50) слишком уменьшает набор для обучения. Если мы сделаем упор на обучение, например, 10 к 1, то результаты тестирования будут ненадежными. Можно для тестирования брать не прореженный набор, а определенное число последних записей. Все зависит от 102 характера исходных данных. Далее, необходимо настроить параметры нейронной сети и генетического алгоритма (Option / NeuroGenetic…): Слева вверху нам предлагается выбрать типы нейронных сетей, которые NGO будет пытаться применить к данной задаче. Лучше всего не ограничивать программу в выборе, исключив только два типа сетей для обучения без учителя (SOM и TSOM – самоорганизующиеся карты Кохонена). Следующий важный параметр – число нейронов в скрытых слоях. Значение 8 установлено по умолчанию. Чем больше нейронов, тем выше возможная точность моделирования, но дольше время обучения. Сложность сети должна быть согласована с числом входных векторов данных: Если у нас 50 строк на входе, то бесполезно задавать 256 нейронов. Справа внизу есть три свойства сети, которые мы можем выбрать как предпочтительные: построить маленькую сеть, использовать как можно меньше входных переменных, использовать все переменные, но оптимизировать структуру сети. Второй пункт следует выбирать, когда число входных переменных очень велико, что будет вызывать проблемы с использованием обученной сети. Теперь необходимо установить параметры обучения (Option / System): 103 Слева вверху нам предлагается выбрать, как измерять точность. Можно установить абсолютную погрешность, среднеквадратичную ошибку и т.д. Наиболее понятной является относительная точность в процентах (как показано на снимке). Следующая группа параметров определяет, как оценивать точность обученной сети. Точность оценивается параметром Fitness, который учитывает в показанном примере 20% погрешности, полученной на данных обучения и 80% - точность, показанную на этапе тестирования. Иными словами, погрешность на тестировании в 5 раз важнее погрешности обучения. Следующая группа параметров – критерии завершения обучения. По умолчанию устанавливается завершение после 10 поколений «генетически модифицированных» сетей. Если не устанавливать критерий, то процесс обучения будет бесконечным, и остановить его нужно будет с помощью пункта меню Run / Halt. Теперь можно запускать обучение сети (Run / Start). Процесс обучения можно контролировать (View / Status) или с помощью кнопки S на панели инструментов. Появится окно следующего вида, в котором отображаются характеристики текущей конфигурации сети (верхняя панель) и характеристики лучшей сети их всех, сгенерированных на данный момент. 104 Можно также наблюдать на графике процесс подгонки модели (View / Predicted vs. Desired - предсказанные и желаемые значения), 105 а также процесс изменения ошибок (View / Accuracy/Error Trend) Процесс обучения можно завершить, когда точность модели будет удовлетворительной. Теперь можно приступить к предсказанию. Для этого надо выбрать View / Best Networks или нажать кнопку B на панели инструментов. Появится следующее окно: 106 Нужно выбрать одну из сетей и нажать кнопку “Make Predictions with selected network…”. Запускается программа Predictor, которая предлагает посмотреть график с результатами обучения, сделать быстрый прогноз путем ввода входных данных с клавиатуры, либо сделать прогноз на основе файла с данными. Если мы выберем быстрый прогноз, то в появившуюся пустую таблицу нужно ввести входной вектор и нажать кнопку Predict: |