Размещено на http://www.allbest.ru/

Харківський національний університет радіоелектроніки

УДК 519.816:004.827

БАГАТОРІВНЕВІ ЙМОВІРНІСНІ МЕРЕЖІ

ДЛЯ МОДЕЛЮВАННЯ СКЛАДНИХ ІНФОРМАЦІЙНИХ

СИСТЕМ В УМОВАХ НЕВИЗНАЧЕНОСТІ

01.05.04 - системний аналіз і теорія оптимальних рішень

Автореферат

дисертації на здобуття наукового ступеня

кандидата технічних наук

Вітько Олександра Валеріївна

Харків - 2003

АНОТАЦІЯ

Вітько О.В. Багаторівневі ймовірнісні мережі для моделювання складних інформаційних систем в умовах невизначеності. - Рукопис.

Дисертація на здобуття наукового ступеня кандидата технічних наук за спеціальністю 01.05.04 - системний аналіз та теорія оптимальних рішень. Харківський національний університет радіоелектроніки, Харків, 2003.

Дисертаційна робота присвячена розробці багаторівневих ймовірнісних мереж, що дозволяють враховувати зміни у контексті, а також методів їх автоматичної побудови за навчальними даними для аналізу та моделювання складних інформаційних систем, що функціонують в умовах невизначеності. Розроблено нову архітектуру багаторівневої ймовірнісної метамережі. Метарівень дозволяє аналізувати і моделювати різновиди одного ймовірнісного процесу, що описується ймовірнісною мережею, в різних контекстах також за допомогою ймовірнісної мережі. На основі архітектури ймовірнісної метамережі розроблено три моделі ймовірнісних метамереж: С_метамережу, R-метамережу та комбіновану RC-метамережу, що відрізняються впливом контекстних атрибутів на прогнозуючу мережу. Модифіковані правила ймовірнісного виведення для розроблених метамереж. Набули подальшого розвитку методи відбудови ймовірнісних мереж з даних для багаторівневих моделей. Надано застосування ймовірнісних метамереж для задач фільтрації змісту Web та передбачення переваг користувача мобільної комерції, моделювання радіаційного ризику населення.

Ключові слова: ймовірнісні мережі, невизначеність, ймовірнісні метамережі, атрибут, релевантність, контекст, ймовірнісне виведення, навчання мереж, моделювання систем.

АННОТАЦИЯ

Витько А.В. Многоуровневые вероятностные сети для моделирования сложных информационных систем в условиях неопределенности. - Рукопись.

Диссертация на соискание ученой степени кандидата технических наук по специальности 01.05.04 - системный анализ и теория оптимальных решений, Харьковский национальный университет радиоэлектроники. Харьков, 2003.

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

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

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

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

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

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

Ключевые слова: вероятностные сети, неопределенность, вероятностные метасети, атрибут, релевантность, контекст, вероятностный вывод, обучение сетей, моделирование систем.

ABSTRACT

Vitko O.V. Multilevel probabilistic networks for modelling complex information systems with uncertainty. - Manuscript.

Thesis for a candidate's degree of technical sciences on the speciality 01.05.04 - system analysis and theory of the optimal decisions, Kharkiv National University of Radioelectronics, Kharkiv, 2003.

This work is devoted to development of Bayesian probabilistic metanetworks and their learning methods for analysis and modelling of the complex information systems. The formalism of multilevel probabilistic metanetwork is developed. The extra metalevel in a metanetwork is used to select appropriate parameters and substructure from the basic network level based on contextual features. Dependencies within contextual level are also described by Bayesian network. Based on the metanetwork formalism three models are developed: C-metanetwork for management of conditional dependencies, R-metanetwork for management of feature selection, combined RC-metanetwork. The rules for probabilistic inference in Bayesian metanetwork are given. The learning methods for the three models are proposed. The use of probabilistic metanetworks for tasks of filtering of the Web content and prediction of mobile user's preferences is given. Also the radiation risk modelling is implemented by probabilistic metanetwork.

Keywords: probabilistic network, uncertainty, probabilistic metanetwork, attribute, relevance, context, probabilistic inference, learning of network, system modelling.

Дисертацією є рукопис.

Роботу виконано в Харківському національному університеті радіоелектроніки Міністерства освіти і науки України.

Науковий керівник: доктор технічних наук, професор Терзіян Ваган Якович, Харківський національний університет радіоелектроніки, завідувач кафедри штучного інтелекту

Офіційний опоненти: - доктор технічних наук, професор Євдокімов Анатолій Гаврилович, Харківська державна академія міського господарства, завідувач кафедри прикладної математики, м. Харків;

- кандидат технічних наук, Подоляка Оксана Олександрівна, Харківський національний автомобільно-дорожній університет, доцент кафедри інформатики, м. Харків.

Провідна установа: Національний технічний університет України “Київський політехнічний інститут”, кафедра прикладної математики, Міністерство освіти і науки України, м. Київ.

Захист відбудеться 4 червня 2003 р. о 13 годині на засіданні спеціалізованої вченої ради Д 64.052.01 в Харківському національному університеті радіоелектроніки за адресою: 61166, м. Харків, пр. Леніна, 14.

З дисертацією можна ознайомитися у бібліотеці Харківського національного університету радіоелектроніки за адресою: 61166, м. Харків, пр. Леніна, 14.

Автореферат розісланий 29 квітня 2003 р.

Вчений секретар спеціалізованої вченої ради В.І. Саєнко

ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ

Актуальність теми. Ринок інтелектуальних комерційних систем, що стрімко розширюється, потребує нових методологій обробки та управління знаннями. Промисловості бракує саме готових рішень, прототипів, за якими можливо налагодити випуск систем із підтримкою штучного інтелекту.

Інтенсивне зростання розподілених інформаційних ресурсів в Україні і в цілому світі потребує якісно нових моделей складних інформаційних систем, методів їх аналізу, управління інформацією, методів прийняття рішень. Прийняття оптимальних рішень у сучасній складній інформаційній системі неможливе без фільтрації та адаптації масштабних інформаційних ресурсів під специфіку конкретних користувачів або інтелектуальних агентів. Таким чином, виникає потреба в адаптивних інформаційних системах, що можуть змінювати модель обробки інформації в залежності від контексту. Наявність децентралізації інформаційних ресурсів також додає невизначеності у даних. Сучасні інформаційні системи повинні обробляти невизначеність розподілених ресурсів з можливістю прогнозування майбутнього стану та динаміки даних з високою продуктивністю. Отже, найбільш актуальними вимогами до системного аналізу, моделювання та прийняття рішень для нового покоління складних інформаційних систем є можливість динамічно адаптувати параметри і структуру системи під різні (можливо непередбачені) контексти і можливість забезпечити прийняття рішення в умовах невизначеності. Відомими фахівцями у галузі теорії прийняття рішень в умовах невизначеності є провідні вчені Ю.П. Зайченко, М.Г. Загоруйко, І.Б. Сіроджа, В.І. Васильєв та ін.

Актуальність роботи підтверджується існуванням широкого спектру задач аналізу складних інформаційних систем, що функціонують в умовах зміни контексту. Це задачі виявлення ймовірнісних залежностей у параметрах складних систем, в яких присутній суб'єктивний людський фактор; задачі прогнозування поведінки користувача інформаційних систем у реальному часі; побудова інтелектуальних Web-систем, що адаптуються під поведінку користувача. Ефективне розв'язання таких задач неможливе без створення гнучких моделей обробки знань із механізмом врахування ймовірнісних змін контексту. Технічна задача постановки на комерційну основу систем підтримки прийняття рішень та проблема відставання існуючих методологій також обумовили дисертаційну роботу.

Математичний апарат ймовірнісних мереж дозволяє ефективно моделювати ймовірнісні залежності між параметрами складних систем та розв'язувати задачі прогнозування, діагностики, класифікації та прийняття оптимальних рішень в умовах невизначеності. Дослідження ймовірнісних мереж останнім часом набули актуальності. Галузь застосування ймовірнісних мереж поширюється від систем медичної та технічної діагностики до прогнозуючих систем в економіці. Вагомий внесок в теорію ймовірнісних мереж зробили вчені J. Perl, G. Cooper, F. Jensen, S. Lauritzen, D. Spiegelhalter, D. Heckerman, M. Chickering, D. Madigan, J. Friedman та ін.

Недоліком класичних ймовірнісних мереж є те, що при реєстрації збою у точності прогнозу чи класифікації мережу потрібно перебудовувати, параметри мережі змінювати і пристосовувати до нової ситуації. Таким чином, актуальною є задача розробки гнучких інструментальних засобів для врахування контексту при прийнятті рішень в умовах ймовірнісної невизначеності.

Зв'язок роботи з науковими програмами, планами, темами. Роботу виконано на кафедрі штучного інтелекту Харківського національного університету радіоелектроніки відповідно до плану науково-дослідної роботи у рамках держбюджетної теми № 106-1 “Розробка концепцій, методів і моделей підтримки систем з розподіленим штучним інтелектом”, № ДР 0100U001341, на якій здобувачка Вітько О.В. працювала виконавцем (акт від 10.01.2003).

Мета і задачі дослідження. Метою дисертаційної роботи є розробка багаторівневих ймовірнісних мереж, що дозволяють враховувати зміни у контексті, а також методів їх автоматичної побудови (навчання) для аналізу та моделювання складних інформаційних систем, що функціонують в умовах ймовірнісної невизначеності. мережа моделювання інформаційний

Для досягнення поставленої мети на підставі системного підходу до аналізу сучасного стану проблеми в дисертаційній роботі сформульовані і вирішені наступні задачі:

розробка нової багаторівневої архітектури ймовірнісної мережі для моделювання складної системи з причинно-наслідковими залежностями серед параметрів системи в умовах контексту, що змінюється;

розробка моделей багаторівневих ймовірнісних мереж для керування параметрами прогнозуючої ймовірнісної мережі в умовах контексту, що змінюється, для керування структурою і комбінованої моделі;

модифікація правил ймовірнісного виведення на розроблених моделях багаторівневих ймовірнісних мереж;

розробка методів навчання (методів автоматичного моделювання за навчальною вибіркою) для створених моделей;

дослідження галузей можливого застосування багаторівневих ймовірнісних мереж.

Об'єкт дослідження - інструментальні засоби діагностики, прогнозування, класифікації та прийняття рішень в складних інформаційних системах, що функціонують в умовах невизначеності, з причинно-наслідковими ймовірнісними залежностями між параметрами. Складність систем, що досліджуються, полягає в змінюванні залежностей між параметрами за умов зміни контексту.

Предмет дослідження - моделі багаторівневих ймовірнісних мереж та методи їх навчання (методи автоматичного моделювання за навчальною вибіркою).

Методи дослідження. Основними методами досліджень є методи системного аналізу, машинного навчання, теорії ймовірностей, ймовірнісні методи інтелектуального аналізу даних, методи теорії прийняття рішень, методи виявлення контексту і методи визначення релевантності атрибутів.

Наукова новизна отриманих результатів:

1) Вперше розроблено архітектуру ймовірнісної метамережі, яка відрізняється від існуючих архітектур додаванням керуючого метарівня (метарівнів) і дозволяє аналізувати і моделювати поведінку системи в різних контекстах, а також ймовірнісні зміни самого контексту за допомогою єдиного апарату ймовірнісних мереж. Це підвищує точність прогнозування, діагностики, прийняття рішень за рахунок використання контекстної інформації, а також швидкість обробки даних за рахунок декомпозиції однієї складної моделі системи на дві або більше простих.

2) Вперше розроблено формальні моделі багаторівневих ймовірнісних метамереж, що відрізняються між собою керуючим впливом контексту: ймовірнісна С-метамережа, що керує умовними залежностями між атрибутами системи; ймовірнісна R-метамережа, що керує добором атрибутів; комбінована ймовірнісна RC-метамережа. Розроблені моделі метамереж, на відміну від існуючих однорівневих, дозволяють гнучко та ефективно обробляти неповні дані системи, коли деякі параметри недоступні для вимірювання, та надлишкові дані, коли в зазначеному контексті вимірювання деяких параметрів повертає шумові дані.

3) Модифіковано правила ймовірнісного виведення на ймовірнісних мережах для багаторівневих моделей С-метамережі, R-метамережі та RC-метамережі. Існуючі правила ймовірнісного виведення вперше розширені для урахування атрибутів контексту як керуючих параметрів для підвищення точності прогнозування або класифікації в умовах невизначеності.

4) Набули подальшого розвитку методи навчання ймовірнісних мереж -методи розширені для багаторівневих моделей. Для навчання багаторівневих метамереж додається новий етап: навчання міжрівневих зв'язків, а також для методів навчання був розроблений гібридний класифікатор. Методи надають можливість будувати гнучкі метамережі з отриманих навчальних даних.

Практичне значення отриманих результатів полягає в тому, що запропоновані багаторівневі ймовірнісні моделі і методи їх навчання дають можливість підвищити точність прогнозування, діагностики або прийняття рішень при наявності неповних і/або надлишкових даних в умовах ймовірнісної невизначеності. Розглянуто застосування ймовірнісних мереж для задач моделювання інформаційних систем, що функціонують в умовах ймовірнісної невизначеності. Зокрема, розроблено методику застосування ймовірнісних метамереж для задач моделювання переваг користувача в системах електронної і мобільної комерції. Застосування розроблених моделей для вивчення радіаційного ризику для населення впроваджено в Українському науково-дослідному інституті екологічних проблем (акт від 10.12.2002). Розроблено метод адаптації структури Web-сайтів на основі застосування ймовірнісних метамереж. Для проведення експериментальних досліджень розроблено програмний пакет BMNLearner та одержано підвищення точності класифікації за навчальними вибірками.

Результати дисертаційної роботи впроваджено у навчальному процесі на кафедрі штучного інтелекту ХНУРЕ у курсі “Машинне навчання” для студентів спеціальності “Інтелектуальні системи прийняття рішень” (акт від 14.01.2003).

Особистий внесок здобувача. Усі результати дисертації отримані автором особисто. У наукових працях, опублікованих у співавторстві, йому належать: в роботі [1] - формалізм ймовірнісної метамережі, моделі ймовірнісних метамереж, правила виведення на ймовірнісних метамережах; у роботі [2] - багаторівнева структура профайлів користувачів в електронній комерції, підхід до моделювання профайлів за допомогою метамереж, ймовірнісний підхід до складання профайлу переваг, метод оцінювання відстані між профайлами; у роботі [3] - застосування ймовірнісних мереж для розробки методу адаптації структури посилань Web-сайту; у роботі [7] - аналіз і порівняння ймовірнісної мережі і “наївного” байєсівського класифікатора.

Апробація результатів дисертації. Результати дисертаційної роботи доповідалися і обговорювалися на:

4-му Міжнародному молодіжному форумі “Радиоэлектроника и молодежь в XXI веке” (м. Харків, 2000 р.);

Російсько-українському науковому семінарі “Интеллектуальный анализ информации ИАИ-2001” (м. Київ, 2001 р.);

X Міжнародній науково-практичній конференції MicroCAD'2002 “Информационные технологии: наука, техника, технология, образование, здоровье” (м. Харків, 2002 р.);

III Міжнародній науково-практичній конференції “Искусственный интеллект 2002” (с. Кацивелі, Крим, 2002 р.) - в рішенні конференції доповідь відзначена як одна з кращих доповідей молодих вчених.

Публікації. Результати досліджень опубліковані у 8 роботах (2 статті в журналах, 5 статей у збірниках наукових праць, 1 публікація у матеріалах конференції), у тому числі 6 у виданнях, що входять до переліку ВАК України.

Структура й обсяг дисертаційної роботи. Дисертація складається із вступу, чотирьох розділів, висновків, списку використаних джерел, що містить 86 найменувань, і трьох додатків. Основний текст викладений на 149 сторінках, дисертація містить 4 таблиці і 40 рисунків.

ОСНОВНИЙ ЗМІСТ РОБОТИ

У вступі обґрунтовано актуальність дисертаційної роботи, сформульовано основну мету і задачі дослідження, наведено відомості щодо наукової новизни отриманих у дисертації результатів, визначено їх практичну цінність, наведено відомості про апробацію та впровадження результатів.

Перший розділ містить огляд предметної області і постановку задачі дисертаційного дослідження. Для опису закономірностей стохастичної поведінки інформаційних систем використовуються методи стохастичного моделювання, до яких належать марківські моделі та ймовірнісні мережі. Розглянуто і проаналізовано байєсівський підхід до інтелектуального аналізу даних та прийняття оптимальних рішень. Байєсівські моделі і методи інтелектуального аналізу мають ряд переваг:

можуть з легкістю обробляти неповні набори даних;

дозволяють навчатися причинно-наслідковим відносинам;

байєсівські методи полегшують об'єднання апріорних знань про проблемну область з даними;

байєсівські методи пропонують ефективний і принциповий відхід від зайвого припасування моделей під дані навчальної вибірки.

Проведено аналіз байєсівських класифікаторів, надано їх узагальнюючі характеристики.

Для моделювання причинно-наслідкових відносин серед параметрів системи стохастичні моделі подаються у вигляді ймовірнісних мереж - графів, що кодують умовні залежності (і незалежності) серед множини випадкових змінних. Наведено дослідження ймовірнісних мереж. Проаналізовані проблеми ймовірнісного виведення на ймовірнісних мережах; проблеми навчання ймовірнісних мереж; наведено аналіз різних підходів і методів вибору моделі ймовірнісної мережі. Наведено основні галузі застосування ймовірнісних мереж. Наведено дослідження аналізу стохастичної поведінки складних систем з урахуванням контексту, що змінюється.

Найскладнішою задачею є динамічний вибір моделі і параметрів ймовірнісної мережі. При реєстрації збою в ефективності аналізу мережу перебудовують, параметри мережі змінюють і припасовують до нової ситуації. Існуючі моделі байєсівських мереж спрямовані на випадок, коли умовні залежності та релевантність атрибутів залишаються незмінними. У той же час існує ряд задач, у яких контекст ситуації впливає на умовні залежності між змінними в проблемній області. На основі проведеного аналізу сучасного стану проблеми відповідно до мети дисертаційної роботи були поставлені вищевказані задачі дисертаційного дослідження.

У другому розділі розроблена архітектура багаторівневої ймовірнісної метамережі для керування змінами байєсівської мережі в умовах контексту, що змінюється.

Вимоги, що були висунуті до архітектури: 1) архітектура має поділяти атрибути на прогнозуючі атрибути системи та контекстні атрибути, а також окремо їх обробляти; 2) має бути реалізований механізм керування параметрами ймовірнісної мережі при зміні значень контекстних атрибутів; 3) має бути реалізований механізм керування структурою ймовірнісної мережі при зміні значень контекстних атрибутів; 4) архітектура має бути багаторівневою і надавати можливість моделювати не тільки зміни прогнозуючої ймовірнісної мережі, але і можливі зміни в контекстній мережі у випадку вкладених контекстів.

Архітектура багаторівневої ймовірнісної метамережі:

MBN: BN₁ {R_1,2} BN₂ {R_2,3} BN₃ … {R_n-1,n} BN _n , (1)

де BN_1, BN_{2, …} BN_n - набір ймовірнісних мереж, що є n рівнями (прогнозуючий рівень та наступні метарівні); {R_1,2}, …{R_n-1,n} - набір множин міжрівневих зв'язків. Міжрівневі зв'язки існують між вершинами мережі метарівня та вершинами і/або дугами мережі попереднього рівня.

Множина {R_i-1,i} містить два типи зв'язків:

1) R_v-e - зв'язок “вершина-дуга”, стохастичним значенням вершини v_ik у мережі BN_i відповідають різні таблиці умовних ймовірностей P_k(v_i-1,j|v_i-1,pj) у мережі BN_i-1;

2) R_v-v - зв'язок “вершина-вершина”, стохастичним значенням вершини v_ir у мережі BN_i відповідають різні значення релевантності вершин v_i-1,r у мережі BN_i-1.

Багаторівнева ймовірнісна мережа (ймовірнісна метамережа) - це набір ймовірнісних мереж, що накладаються одна на одну таким чином: елементи (параметри і/або структура) кожної попередньої ймовірнісної мережі залежать від локальних розподілів ймовірностей, пов'язаних з вершинами наступного рівня метамережі.

На підставі нової архітектури розроблено три моделі ймовірнісних метамереж.

Багаторівнева ймовірнісна мережа, що керує умовними залежностями, (ймовірнісна С-метамережа) - це набір ймовірнісних мереж, що накладаються одна на одну таким чином: значенням вершин наступного рівня відповідають можливі матриці ймовірностей (можливі умовні залежності) попередньої ймовірнісної мережі.

Формальна модель С-метамережі:

С-MBN = (BN, R_v-e, P), (2)

де BN = {BN₁, BN₂, …BN_n} - набір ймовірнісних мереж, що входять до архітектури; R_v-e= {R_1,2, …R_n-1,n} - набір множин міжрівневих зв'язків; R_i-1,i - множина зв'язків типу R_v-e між умовними залежностями (дугами) ймовірнісної мережі (i-1)-го рівня та змінними (вершинами) ймовірнісної мережі i-го рівня; P - набір локальних розподілів ймовірностей.

На рис. 1 наведені варіанти зображення С-метамережі.



а)

б)

Рис. 1. Тривимірне зображення дворівневої С-метамережі (а) і проекційне зображення фрагмента С-метамережі (б)

Для фрагмента С-метамережі на рис. 1б маємо:

- атрибути прогнозуючого рівня A, B, X, Y та їх можливі значення;

- безумовні ймовірності P(A), P(X) на прогнозуючому рівні;

- умовні ймовірності на прогнозуючому рівні: P(B|A), що є випадковою змінною з набором значень {p₁(B|A), p₂(B|A),…, p_mp(B|A)}, P(Y|X), що є випадковою змінною з набором значень {p₁(Y|X), p₂(Y|X),…, p_np(Y|X)}. Ці умовні ймовірності є атрибутами на контекстному рівні;

- умовна ймовірність на контекстному рівні P(P(Y|X),P(B|A)) між двома атрибутами метарівня P(B|A) і P(Y|X).

Будемо говорити, що матриця ймовірностей P(Y|X) умовно метазалежна від матриці ймовірностей P(B|A) тоді, і тільки тоді, коли хоча б для однієї пари матриць P_i(B|A) і P_j(Y|X) ймовірність P(P_j(Y|X)|P_i(B|A)) істотно відрізняється від ймовірності P(P_j(Y|X)).

Були розроблені правила ймовірнісного виведення у ймовірнісній С_метамережі. Ймовірнісне виведення ймовірності цільового атрибута здійснюється застосуванням ймовірнісного виведення на метарівні, а потім на прогнозуючому рівні метамережі, як показано формулами (3) та (4):

(3)

(4)

Дворівнева метамережа може бути легко розширена до багаторівневої (багатоконтекстної) метамережі. Кількість рівнів ймовірнісної метамережі залежить від кількості рівнів контексту, що розглядаються, або від ступеня вкладеності контекстів.

Розроблена багаторівнева модель має ряд переваг у порівнянні з однорівневою ймовірнісною мережею, що були підтверджені рядом проведених експериментальних досліджень. Перевагами моделі є: зниження рівня складності за рахунок декомпозиції однієї складної моделі системи на дві або більше простих, швидкість обробки, гнучкість. Порівняно із звичайною ймовірнісною мережею модель дозволяє підвищити точність прогнозування, коли деякі параметри системи недоступні для вимірювання, за рахунок використання додаткової інформації - контекстних параметрів і умовних залежностей між ними.

Багаторівнева ймовірнісна мережа, що керує добором атрибутів (R_метамережа) - це набір ймовірнісних мереж, що накладаються одна на одну таким чином, що значенням вершин наступного рівня відповідають можливі значення релевантностей атрибутів мережі попереднього рівня.

У дисертаційній роботі релевантність розглядається як ймовірність важливості значень атрибута для виведення значення цільового атрибута в заданому контексті. Релевантність може бути: 1) задана експертом на підставі апріорних знань про проблемну область; 2) отримана за результатами методів добору атрибутів.

Формальна модель R-метамережі:

R-MBN = (BN, R_v-v, P), (5)

де BN = {BN₁, BN₂, …BN_n} - набір ймовірнісних мереж, що входять до архітектури; R_v-v= {R_1,2, …R_n-1,n} - набір множин міжрівневих зв'язків; R_i-1,i - множина зв'язків типу R_v-v між релевантностями атрибутів (вершин) ймовірнісної мережі (i-1)-го рівня та атрибутами (вершинами) ймовірнісної мережі i-го рівня; P - набір локальних розподілів ймовірностей.

На рис. 2 наведено варіанти тривимірного і проекційного зображення дворівневої R-метамережі. Ідея введення метарівня полягає в тому, що релевантність атрибутів прогнозуючої ймовірнісної метамережі може змінюватись в залежності від контексту.

Для фрагмента R-метамережі на рис. 2б маємо:

- атрибути прогнозуючого рівня A, X, Y та їх можливі значення;

- безумовні ймовірності P(A), P(X) на прогнозуючому рівні;

- умовні ймовірності на прогнозуючому рівні: P(X|A), P(Y|X);

- предикати релевантностей атрибутів прогнозуючого рівня: (X)=“yes”, якщо атрибут X є релевантним; (X)=“no”, якщо атрибут X не є релевантним; аналогічно (A);

- атрибути контекстного рівня: _X = P((X)=“yes”), _A = P((A)=“yes”);

- умовна ймовірність на контекстному рівні P(_X,_A) між двома атрибутами метарівня _X і _A .

Були розроблені правила ймовірнісного виведення у ймовірнісній R_метамережі. Ймовірнісне виведення ймовірності цільового атрибута здійснюється застосуванням ймовірнісного виведення на метарівні, а потім на прогнозуючому рівні метамережі, як показано співвідношеннями (6) та (7).

(6)

де n_x - кількість значень прогнозуючого атрибута X.

(7)

Модель дозволяє підвищити точність прогнозування, коли в контекстах вимірювання кількох параметрів системи повертає шумові дані, тобто параметри стають нерелевантними і надлишковими. Перевагами моделі також є зниження рівня складності, швидкість обробки, гнучкість.

У загальному випадку при зміні контекстів у проблемній області можуть змінюватися як умовні залежності (параметри) мережі, що передбачається, так і релевантні атрибути (структура). Отже, необхідна комбінована модель, що включає в себе два рівні керування для мережі, що передбачається.

Багаторівнева комбінована ймовірнісна мережа (ймовірнісна RС_метамережа) - це набір ймовірнісних мереж, що накладаються одна на одну таким чином, що над кожною мережею може розташовуватися один чи два метарівня - рівень управління умовними залежностями і/чи рівень керування добором атрибутів (рівень релевантностей).

Правила ймовірнісного виведення для комбінованої RC-метамережі будуються на основі правил виведення для С-метамережі та R-метамережі.

У третьому розділі запропоновані методи навчання (автоматичної побудови за навчальними даними) багаторівневих ймовірнісних метамереж в умовах контексту, що змінюється. Методи навчання звичайних ймовірнісних мереж були модифіковані та розширені для метамоделей: додається етап вилучення рівнів метамережі та етап навчання міжрівневих зв'язків, який дозволяє ефективно будувати метамережу з даних в умовах невизначеності.

Метод навчання ймовірнісної метамережі складається з чотирьох етапів, етапи 2, 3, 4 реалізуються ітеративно для всіх рівнів ймовірнісної метамережі, починаючи з прогнозуючого рівня.

На першому етапі реалізується процедура поділу атрибутів на прогнозуючі і контекстні, а також вилучення кластерів даних для кожного контексту. Етап 1 ідентичний для усіх трьох моделей метамереж. Навчання структурі мережі на поточному рівні (етап 2) здійснюється методом Ченга_Грейнера визначення незалежних вершин у графі на основі коефіцієнтів сумісної інформації та умовної сумісної інформації:

(8)

(9)

У методі навчання С-метамережі на етапі 2 відновлюється структура мережі кожного рівня метамережі. У методах навчання R-метамережі та RC_метамережі для прогнозуючого рівня відновлюється тільки загальна структура, з якої при виведенні ймовірностей цільового атрибута буде відбиратись менша підструктура за рахунок відкидання нерелевантних атрибутів у заданому контексті.

На етапі 3 здійснюється формування метавершин для контекстного рівня і винесення їх на наступний рівень метамережі (наукова новизна дисертаційних досліджень).

Навчання міжрівневим зв'язкам С-метамережі. Припустимо, у мережі присутня четвірка випадкових величин A, B, X, Y і явно виражена залежність (B від A) та (Y від X). Звичайний алгоритм навчання, використовуючи усі вхідні дані (наприклад, результати спостережень вектора <A, B, X, Y>), дає матрицю ймовірностей P(B|A): P_ik(B = b_i | A = a_k ). Аналогічно отримуємо матрицю P(Y|X): P_rs(Y = y_r | X = x_s ). При існуванні кількох контекстів, у яких спостерігається ймовірнісна мережа, слід досліджувати кожний контекст і обчислити більш точні параметри мережі в кожному контексті, а не обмежуватися “середніми” по всіх контекстах параметрами P_ik і P_rs.

Вектор <A, B, X, Y> навчальних даних розбивається на n кластерів відповідно до значень контекстних атрибутів для обчислення залежності B від А і m кластерів для обчислення залежності Y від X. Окремо отримуємо n матриць ймовірностей P_j (B|A) і m матриць P_t (Y|X):

(10)

(11)

Отримані дві множини матриць для двох спрямованих дуг у мережі першого рівня {P_j(B|A)} і {P_t(Y|X)} можна вважати випадковими величинами U і W мережі другого рівня відповідно. Вершина U буде мати стільки значень, скільки контекстів розглядається для зв'язку B від А на першому рівні. Кожному значенню u_j буде відповідати матриця P_j(B|A). Вершина W буде мати стільки значень, скільки контекстів розглядається для зв'язку Y від X на першому рівні. Кожному значенню w_t буде відповідати матриця P_t(Y|X). Таким чином, отримуємо метарівень з вершинами U і W і відповідною умовною байєсівською ймовірністю P(W|U).

Метаматрицю P(W|U) на контекстному рівні надано виразом (12):

(12)

Навчання міжрівневим зв'язкам R-метамережі. Розглянемо два прогнозуючих атрибути A, X для цільового атрибута Y. Метод добору релевантних атрибутів, використовуючи усі вихідні дані (наприклад, результати спостережень вектора <A, X, Y>), дає оцінки релевантності кожного з прогнозуючих атрибутів (A), (X). Якщо існує кілька контекстів, у яких спостерігається дана ймовірнісна мережа, релевантність атрибутів може бути різною у кожному контексті. Слід досліджувати кожний контекст і вибрати релевантність атрибутів в кожному, а не обмежуватися “середніми” значеннями (A), (X) по всіх контекстах. Різні релевантності в різних контекстах призводять до різних структур прогнозуючої мережі.

У процедурі добору релевантних атрибутів запропоновано гібридний класифікатор, що є ансамблем класифікаторів k-NN, Naive Bayes і модифікованого k-NN, удосконаленого за рахунок застосування різниці ймовірностей як функції відстані замість різниці значень атрибутів. Експериментальні дослідження гібридного класифікатору показали виграш у точності класифікації на тестових вибірках.

Застосовуючи метод добору атрибутів у кожному кластері навчальних даних, отримаємо n значень релевантності _j(A) і m значень _t(X). Дві множини {_j (A)}, {_t (X)} можна вважати випадковими величинами U, W контекстного рівня. Між контекстними атрибутами логічно виявляються причинно-наслідкові зв'язки, а отже, можливе існування метазалежності W від U, для якої алгоритм навчання може побудувати метаматрицю P(W|U):

(13)

Таким чином, отримуємо метарівень з вершинами U, W і відповідною умовною байєсівською ймовірністю P(W|U).

Навчання міжрівневим зв'язкам комбінованої RС-метамережі складається з етапів навчання міжрівневим зв'язкам С-метамережі та R_метамережі.

На етапі 4 здійснюється обчислення параметрів (таблиць безумовних та умовних залежностей) мережі поточного рівня на основі результатів, отриманих на етапі 2 і етапі 3.

У четвертому розділі розглянуто практичні застосування ймовірнісних метамереж. На прикладі інформаційної системи для вивчення радіаційного ризику для населення, програмний модуль якої було реалізовано в дисертаційній роботі, розглянуто використання ймовірнісних метамереж для задач моделювання складних систем. Ймовірнісною метамережею було змодельоване багатофакторне поняття радіаційного ризику і вивчено відносний вплив на його розподіл об'єктивних та суб'єктивних параметрів. Об'єктивні параметри інформаційної системи радіаційного моніторингу утворюють ймовірнісну мережу, розташовану на першому рівні метамережі, а суб'єктивні фактори розглядаються як контекстні атрибути і винесені на другий рівень мережі (метарівень). Вони керують ймовірнісними причинно-наслідковими зв'язками прогнозуючої мережі. Отримані ймовірнісні залежності оцінок радіаційного ризику для різних категорій населення збігаються з оцінками експертів. Урахування в єдиній моделі фізичних, соціальних і психологічних факторів дозволяє застосувати на практиці вимоги Норм радіаційної безпеки України (НРБУ-97) до використання багатофакторного поняття ризику в протирадіаційному захисті населення.

Розглянуто застосування ймовірнісних метамереж для задач моделювання переваг користувача в системах електронної і мобільної комерції. Розроблено багаторівневу модель профайлів користувачів, яку ефективно моделювати ймовірнісною метамережею. Прогнозуючі атрибути - вивчені чи задані переваги користувача - розташовуються на основному прогнозуючому рівні метамережі. Вони використовуються для прогнозування поведінки користувача. Контекстні атрибути формують рівень керування. Вони використовуються для прогнозування умовних залежностей між атрибутами переваги конфігурації користувача (перший мережений рівень) відповідно до поточного контексту, або для визначення, яка підмножина прогнозуючих атрибутів є релевантною у дійсному контексті. Таким ефективним способом постачальник мобільних послуг може пропонувати найкращі товари/послуги користувачу.

Також розроблений метод адаптації структури Web-сайтів на основі застосування ймовірнісних метамереж. Якщо структуру Web-сайту представити у вигляді ймовірнісної мережі, то маємо справу зі сторінками сайту як вершинами, спрямованими дугами як посиланнями між окремими сторінками, а також ймовірностями відвідування користувачем одних сторінок за умови відвідування інших. Як контекстні атрибути пропонується використовувати переваги користувача чи групи користувачів, до якої віднесли користувача на підставі профілювання. Експериментальні дослідження доводять ефективність застосування розробленого методу.

Розроблено програмний пакет BMNLearner, у якому реалізовані методи побудови ймовірнісних метамереж за навчальними вибірками і методи ймовірнісного виведення на метамережах. Проведено ряд експериментальних досліджень та одержано підвищення точності класифікації за навчальними вибірками.

У висновках сформульовані основні теоретичні та практичні результати роботи.

У додатках наведені результати імітаційного моделюванняnf nf і акти впровадження.

ВИСНОВКИ

На основі проведеного аналізу сучасного стану моделювання складних інформаційних систем з причинно-наслідковими ймовірнісними залежностями серед параметрів, у дисертаційній роботі наведено теоретичне узагальнення і нове вирішення наукового завдання, що полягає в розробці моделей ймовірнісних метамереж і методів їх побудови за отриманими даними системи, що аналізується. На відміну від існуючих однорівневих ймовірнісних мереж розроблені метамережі дозволяють керувати параметрами і структурою прогнозуючої мережі і, таким чином, дозволяють обробляти неповні і надлишкові дані. Результати роботи є внеском у подальший розвиток інтелектуального аналізу даних у складних системах і теорії прийняття оптимальних рішень в умовах ймовірнісної невизначеності. Застосування на практиці розроблених моделей і методів дозволяє підвищити ефективність аналізу і моделювання складних інформаційних систем, що функціонують в умовах невизначеності. У зв'язку з цим у дисертаційній роботі:

Розглянуто і проаналізовано байєсівський підхід до обробки даних стохастичної природи, зокрема, до вирішення задачі класифікації. Розглянуто переваги байєсівських моделей і методів інтелектуального аналізу даних. Проведено дослідження представлення даних у вигляді ймовірнісних мереж. Проведено аналіз проблеми ймовірнісного виведення. Розглянуто основні задачі і проблеми навчання ймовірнісних мереж. Проведено аналіз існуючих підходів і методів вибору моделі ймовірнісної мережі.

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

Розроблено ймовірнісну метамережу, що керує умовними залежностями (C-метамережу). В основі моделі лежить формалізм ймовірнісної метамережі з визначенням зв'язків між рівнями, як відповідністю значень вершини верхнього рівня можливим таблицям умовних ймовірностей для байєсівського зв'язку в мережі нижнього рівня. Порівняно із звичайною ймовірнісною мережею модель дозволяє підвищити точність прогнозування, коли деякі параметри системи недоступні для вимірювання, за рахунок використання додаткової інформації - контекстних параметрів і умовних залежностей між ними.

Розроблено ймовірнісну метамережу, що керує добором атрибутів (R-метамережу). В основі моделі лежить формалізм ймовірнісної метамережі з визначенням зв'язків між рівнями, як відповідністю значень вершини верхнього рівня можливим релевантностям атрибута у вершині мережі нижнього рівня. Модель дозволяє підвищити точність прогнозування, коли в контекстах вимірювання кількох параметрів системи надає шумові дані, тобто параметри стають надлишковими.

Розроблено комбіновану ймовірнісну метамережу (RC-метамережу), що у загальному випадку має два верхніх рівні управління для кожного нижнього рівня і дозволяє обробляти і неповні дані, і надлишкові.

Модифіковано правила виведення у ймовірнісних мережах для багаторівневих моделей, що дає можливість ефективно здійснювати ймовірнісне виведення в умовах змінного контексту. Існуючі правила ймовірнісного виведення вперше розширені для урахування атрибутів контексту як керуючих параметрів для підвищення точності прогнозування або класифікації в умовах невизначеності. Ймовірнісне виведення ймовірностей цільового атрибута здійснюється застосуванням ймовірнісного виведення на метарівні, а потім на прогнозуючому рівні метамережі

Набули подальшого розвитку методи навчання ймовірнісних мереж для багаторівневих моделей. Для навчання багаторівневих метамереж додається етап навчання міжрівневих зв'язків, який дозволяє ефективно будувати метамережу з даних в умовах невизначеності; а також було запропоновано гібридний класифікатор, що є ансамблем класифікаторів k_NN, Naive Bayes і модифікованого k-NN, удосконаленого за рахунок застосування різниці ймовірностей як функції відстані замість різниці значень атрибутів.

Використання розробленої архітектури, моделей і методів дозволяє підвищити точність прогнозування, діагностики, прийняття рішень за рахунок використання контекстної інформації, а також підвищити швидкість обробки даних за рахунок декомпозиції однієї складної моделі системи на дві або більше простих.

Для проведення експериментальних досліджень розроблено програмний пакет BMNLearner та одержано підвищення точності класифікації за навчальними вибірками. Запропоновано вирішення ряду практичних задач з використанням багаторівневих ймовірнісних мереж. На прикладі інформаційної системи для вивчення радіаційного ризику для населення розглянуте використання ймовірнісних метамереж для задач моделювання складних систем. Розглянуто застосування ймовірнісних метамереж для задач моделювання переваг користувача в системах електронної і мобільної комерції, розроблено багаторівневу модель профайлів користувачів. Розроблено метод адаптації структури Web-сайтів на основі застосування ймовірнісних метамереж.

ПУБЛІКАЦІЇ ЗА ТЕМОЮ ДИСЕРТАЦІЇ

1. Терзиян В.Я., Витько А.В. Вероятностные метасети для решения задач интеллектуального анализа данных // Искусственный интеллект. - 2002. - № 3. - С. 188-197.

2. Витько А.В., Омелаенко Б.А. Стохастические модели машинного обучения // Вестник Харьковского государственного политехнического университета.- 1999.-Вып. № 47. - С. 9-10.

3. Витько А.В. Классификаторы k-Nearest Neighbours и Naive Bayes: построение гибридных методов // Вестник Харьковского государственного политехнического университета.- 1999. - Вып. № 58. - С. 28-30.

4. Витько А.В. Базовый алгоритм вероятностного вывода на байесовых сетях // Вестник Харьковского государственного политехнического университета.- 1999. - Вып. № 75. - С. 23-26.

5. Vitko O. Bayesian model averaging strategy for the class of linear models // Вестник Харьковского государственного политехнического университета. - 2000. - Вып. № 119. - С. 4-5.

6. Витько А.В. , Кузин Ю.В., Легеза А.В. Разработка метода адаптации ссылочной структуры Web-сайта на основе вероятностных сетей // Вестник НТУ “ХПИ”. Сборник научных трудов. Тематический выпуск: Новые решения в современных технологиях. - Харьков: НТУ “ХПИ”. - 2002. - № 20. - С. 31-38.

7. Терзиян В.Я., Витько А.В. Интеллектуальное управление информацией в мобильной электронной коммерции // Новости искусственного интеллекта. - 2001. - № 5-6. - С. 26-33.

Размещено на Allbest.ru

...