Динамический отбор прецедентов в интеллектуальной системе «Муссон»

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

Ausführliche Beschreibung

Gespeichert in:

Bibliographische Detailangaben
Veröffentlicht in:	Штучний інтелект
Datum:	2012
1. Verfasser:	Шерстюк, В.Г.
Format:	Artikel
Sprache:	Russisch
Veröffentlicht:	Інститут проблем штучного інтелекту МОН України та НАН України 2012
Schlagworte:	Интеллектуальные системы планирования, управления, моделирования и принятия решений
Online Zugang:	https://nasplib.isofts.kiev.ua/handle/123456789/57744
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Zitieren:	Динамический отбор прецедентов в интеллектуальной системе «Муссон» / В.Г. Шерстюк // Штучний інтелект. — 2012. — № 4. — С. 392-403. — Бібліогр.: 13 назв. — рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

_version_	1859683850327687168
author	Шерстюк, В.Г.
author_facet	Шерстюк, В.Г.
citation_txt	Динамический отбор прецедентов в интеллектуальной системе «Муссон» / В.Г. Шерстюк // Штучний інтелект. — 2012. — № 4. — С. 392-403. — Бібліогр.: 13 назв. — рос.
collection	DSpace DC
container_title	Штучний інтелект
description	В статье предложены методы извлечения и отбора уместных прецедентов, представляющих собой потоки событий, в реальном времени для динамической сценарно-прецедентной системы «Муссон», предназначенной для управления динамическими объектами. Предложенные методы основаны на формировании гипотез и дальнейшем их уточнении с целью либо подтверждения, либо опровержения: подтвержденная гипотеза становится заключением и используется для последующего принятия решений оператором. У статті запропоновані методи вилучення та відбору доречних прецедентів, що представляють собою потоки подій, в реальному часі для динамічної сценарно-прецедентної системи «Муссон», призначеної для управління динамічними об’єктами. Запропоновані методи засновано на формуванні гіпотез та їх уточнення надалі з метою або підтвердження, або спростування: підтверджена гіпотеза стає висновком і використовується для подальшого прийняття рішень оператором. The article suggests the real-time relevant cases retrieving and selecting methods for the dynamic scenario-case system '‘Monsoon" designed to the dynamic objects control. The proposed methods are based on the hypotheses formation of and their refinement in order to either confirm or disprove: the hypothesis becomes confirmed by the conclusion and used for operator's decision-making.
first_indexed	2025-11-30T21:37:54Z
format	Article
fulltext	«Искусственный интеллект» 4’2012 392 4Ш УДК 656.612 В.Г. Шерстюк Херсонский национальный технический университет, Украина Украина, 73008, г. Херсон, Бериславское шоссе, 24, v_sherstyuk@bigmir.net Динамический отбор прецедентов в интеллектуальной системе «Муссон» V.G. Sherstyuk Herson National Technical University, Ukraine Ukraine, 73008, с. Herson, Berislavskoye highway, 24, v_sherstyuk@bigmir.net Dynamic Case Selection in the “Monsoon” Intelligent System В.Г. Шерстюк Херсонський національний технічний університет, Україна Україна, 73008, м. Херсон, Бериславське шосе, 24, v_sherstyuk@bigmir.net Динамічний відбір прецедентів в інтелектуальній системі «Мусон» В статье предложены методы извлечения и отбора уместных прецедентов, представляющих собой потоки событий, в реальном времени для динамической сценарно-прецедентной системы «Муссон», предназначенной для управления динамическими объектами. Предложенные методы основаны на формировании гипотез и дальнейшем их уточнении с целью либо подтверждения, либо опровержения: подтвержденная гипотеза становится заключением и используется для последующего принятия решений оператором. Ключевые слова: прецедент, подобие, событие, поток, ситуация, отбор, гипотеза, заключение, опровержение The article suggests the real-time relevant cases retrieving and selecting methods for the dynamic scenario- case system “Monsoon” designed to the dynamic objects control. The proposed methods are based on the hypotheses formation of and their refinement in order to either confirm or disprove: the hypothesis becomes confirmed by the conclusion and used for operator’s decision-making. Key words: case, similarity, event, stream, situation, selection, hypothesis, conclusion, negation. У статті запропоновані методи вилучення та відбору доречних прецедентів, що представляють собою потоки подій, в реальному часі для динамічної сценарно-прецедентної системи «Муссон», призначеної для управління динамічними об’єктами. Запропоновані методи засновано на формуванні гіпотез та їх уточнення надалі з метою або підтвердження, або спростування: підтверджена гіпотеза стає висновком і використовується для подальшого прийняття рішень оператором. Ключові слова: прецедент, подібність, подія, потік, ситуація, відбір, гіпотеза, висновок, спростування. Введение Целенаправленно управляемые оператором или группой операторов динамические объекты (ДО) при взаимодействии с другими ДО в пределах некоторого ограниченного пространства формируют открытую полиэргатическую сложную динамическую сис- тему (СДС). Динамический отбор прецедентов в интеллектуальной системе «Муссон» «Штучний інтелект» 4’2012 393 4Ш В полиэргатических СДС знания операторов ДО о текущей ситуации, как правило, неполны и неточны, действия операторов взаимодействующих ДО непредсказуемы, нормативные правила, регулирующие взаимодействие ДО, являются противоречивыми и недостаточно определенными, управляющие воздействия не всегда приводят к тре- буемому результату вследствие стохастических воздействий внешней среды. При наличии в СДС стесненных условий и множественных ситуационных воз- мущений складываются информационно сложные для оператора ситуации [1], обу- словленные неполнотой и неточностью исходной информации, значительными объе- мами требуемых вычислений, а также серьезными ограничениями во времени, что существенно усложняет принятие оператором адекватных решений по управлению ДО, а в некоторых случаях приводит к инцидентам и авариям, которые принято класси- фицировать как «воздействие человеческого фактора» [2]. Актуальным способом снижения зависимости от «человеческого фактора» явля- ется автоматизация процессов принятия решений с использованием современных методов искусственного интеллекта. В [3] предложено с целью компенсации влияния «человеческого фактора» на процесс управления ДО в информационно-сложных ситуациях использовать динамическую сценарно-прецедентную интеллектуальную систему (ДСПИС). Исследование формальных моделей и методов функционирования ДСПИС является на сегодня одной из актуальных и важных научно-технических задач. Постановка задачи исследования Сценарно-прецедентные интеллектуальные системы являются классом систем автоматизированного вывода решений, основанным на принципах: а) повторяемости ситуаций; б) возможности использования ранее принятых решений в случае возник- новения сходных проблемных ситуаций; в) представления решений в форме планов и сценариев [4]. Как показано в [5], ДСПИС управления ДО должна: а) функциони- ровать в реальном времени; б) автоматически генерировать уместные в сложившейся ситуации решения. Для решения задач управления ДО в информационно сложных ситуациях пред- назначена ДСПИС «Муссон» [6], получающая на входе поток наблюдаемых событий от подсистемы мониторинга, оценивающая на основе потока событий возможные действия операторов окружающих ДО и предоставляющая оператору план наиболее уместных действий в сложившейся ситуации. Основой ДСПИС «Муссон» является представление информации о динамике ситуаций в виде потоков событий в рамках правдоподобной древовидной сети собы- тий (ПДСС) [7]. Ранее в [8] представлен также метод динамической оценки подобия потоков событий, позволяющий соотнести наблюдаемый поток событий с эталонными потоками событий, составляющими хранилище прецедентов (ХП). Вопросы разработки методов извлечения и отбора уместных прецедентов для ДСПИС, функционирующих в реальном времени, ранее не рассматривались. Наиболее близкой к ДСПИС «Муссон» является концепция «беспрерывной» прецедентной ИС (Ceaseless CBR) [9], работающей в квазиреальном времени. Общий анализ состояния работ в области синтеза ДСПИС реального времени показывает, что методы извлечения и отбора прецедентов, представляющих собой потоки событий, исследованы фрагментарно, адекватные решения задач извлечения и отбора прецедентов практически отсутствуют. Цель данной работы состоит в теоретическом исследовании ДСПИС как класса ситуационных ИС, разработке и обосновании используемых в ДСПИС методов извле- чения и отбора прецедентов. Шерстюк В.Г. «Искусственный интеллект» 4’2012 394 4Ш Прецеденты и гипотезы Пусть S – пространство возможных ситуаций, R – пространство возможных решений, G – пространство возможных целей. В ДСПИС «Муссон» прецедент e представляет собой тройку , ,s r g S R G   , состоящую из описания ситуации s S , содержащего поток событий  R , называемый эталонным потоком событий, и контекст, заданный как множество переменных    1 2, ,... 1..n i e e e e i n v v v , v E.v, ; связанного с s решения r R , содержащего план дей- ствий  , и связанной с r цели g G , на достижение которой направлен план r . Цель g отражает предполагаемый результат выполнения решения r прецедента e в ситуации s . Инициирующий прецедент Ie представляет собой описание проблемной ситуа- ции Is , содержащее наблюдаемый поток событий  S и контекст, представляющий собой множество переменных    1 2, ,... 1.. I I I I n i e e e e i n v v v , v E.v, , отражающих условия наблюдения. Множество прецедентов, хранимых в ДСПИС, представлено в виде сложной структуры данных – ПДСС G . Первый (нижний) уровень ПДСС 1 G ассоциирован с моделью событий и содержит множество эталонных потоков событий    1 2, ,... , 1..n i i n      R R R , R E.z . Второй уровень 2 G содержит таксономическую стру- ктуру контекстов ситуаций 2ieCtx  Gе , где    1 2, ,... 1.. i i i i i n j e e e e e j n  Ctx v v v , v E.v, . Активным в момент времени t прецедентом является прецедент Xe , эталонный поток событий которого Xe  R имеет моментальную оценку подобия с наблюдаемым потоком  S , значение которой в t выше заданного порога  , т.е.   SIM ,   S R t . Гипотезой h называется результат распространения входного (наблюдаемого) потока событий  S на эталонный поток событий  R активного прецедента Xe , пред- ставленный в виде кортежа , , , , , ,th C , где C  указатель на рассматриваемый прецедент  X Se e ;  куст прецедента C , представляющий собой префикс эталонного потока событий 1 2, ,... , m          R R R R Ry y y C , включающий суффикс наблюдаемого потока собы- тий 1, ,...i i i m         S S S Sy y y , такой что   S Rф ;  суффикс (остаток) эталонного потока событий 1 2, ,... , m m m l            R R R R Ry y y C , содержащий события, которые на момент времени t еще не наблюдались, но пред- полагаются исходя из динамической оценки подобия потоков событий  S и  R ;  нормализованная динамическая оценка подобия потоков событий  S и  R ,  SIM   S,R= ;  степень уверенности в том, что последующие наблюдаемые события 1 2, ,...i m i m i m l             S S S Sy y y вложены в суффикс эталонного потока событий 1 2, ,... , m m m l            R R R R Ry y y C (оценка правдоподобия гипотезы); Динамический отбор прецедентов в интеллектуальной системе «Муссон» «Штучний інтелект» 4’2012 395 4Ш  степень уверенности в наступлении ожидаемого события 1t  y , такого, что   1 t t i    prefixy h . ; t  момент времени, в который наблюдалось последнее событие i m  Sy . Таким образом, соответствует той части активного прецедента Xe , события которой уже случились (наблюдаемы), и является основанием для вывода с уверен- ностью , что остаток является частью прецедента Xe , события которой еще не случились, но предполагаются в будущем. Соответственно, C , е C ,  C ,  Доказательством j h гипотезы jh является событие 1i    S Sy , изменяющее дина- мическую оценку подобия потоков     ,SIM suffix prefix   S R в сторону увеличения, так что          1,..., , ,..., ,t m t t m t  SIM prefix SIM prefix   R Ry y y y . Заключением m  Sy для потока событий  S называется подмножество активных гипотез  t H H , объясняющих все наблюдаемые в точке t события наблюдаемого потока 1 2, ,... m        S S S Sy y y , так что i m i     S S SS °y yy . Извлечение прецедентов и формирование гипотез Задача извлечения подобных прецедентов заключается в непрерывном сравнении наблюдаемого потока событий в СДС  S с эталонными потоками событий  R , содер- жащимися в ХП, и обнаружении тех прецедентов, эталонные потоки событий которых подобны наблюдаемому потоку с оценкой, превышающей заданный порог  . Задача формирования гипотез заключается в создании и непрерывном обновлении множества гипотез, представляющих описание текущего состояния СДС. Обе задачи в рамках ДСПИС решаются совместно и параллельно. Метод извлечения подобных прецедентов основан на последовательно-парал- лельном выполнении четырех функций: – кластеризации ХП относительно контекста инициирующего прецедента    1 2, ,... 1.. I I I I I n i e e e e e i n  Ctx v v v , v E.v, ; – классификации каждого очередного события наблюдаемого потока t  y S отно- сительно заданной иерархии классов ,C  ; – динамической оценки подобия эталонных потоков событий прецедентов  R относительно наблюдаемого потока событий  S ; – формирования множества правдоподобных гипотез H . Кластеризация хранилища прецедентов. Кластеризация ХП производится независимо для каждого наблюдаемого потока событий  S . Целью кластеризации является сужение пространства поиска подобных прецедентов исключением из поиска тех прецедентов je , контекст которых jeCtx не соответствует контексту инициирую- щего прецедента IeCtx , т.е. I je eCtx Ctx . Для выполнения кластеризации используем подход, основанный на теории приближенных множеств [10]. Шерстюк В.Г. «Искусственный интеллект» 4’2012 396 4Ш Пусть кортеж  ,S S IND  является пространством приближения, а  1 2, ,..., iIND E E E является набором классов эквивалентности заданного отношения неразличимости IND . Тогда функция принадлежности класса эквивалентности E некоторому подмножеству множества ситуаций Y имеет вид: ( )E Y Y E Y   . Пусть показатель точности ( )Y определяет отношение между числом элементов множества Y , которые необходимо являются элементами Y , к тем, которые возможно являются элементами Y . Данное отношение описывается через нижнее ( )IND Y и верхнее ( )IND Y приближение Y и показывает, насколько близко приближение ( ), ( )IND Y IND Y к исходному множеству Y . Соответственно, позитивный класс ( )POS E может быть задан как объединение тех элементарных множеств, чьи критерии классификации гарантируют, что точ- ность ( )Y будет больше E Y :    : ( ) E YPOS E E IND Y    . (1) Негативный класс ( )NEG E определен как объединение тех элементарных мно- жеств, чьи критерии классификации гарантируют, что точность ( )Y будет меньше E Y :  ( ) : ( ) E YNEG E E IND Y    . (2) Граничная область ( )BND E представлена объединением тех элементарных множеств, чья классификация не принадлежит позитивной и негативной областям множества Y :    : ,BND E E IND E POS NEG    , (3) Поскольку отношение неразличимости IND разбивает исходное множество прецедентов ХП на кластеры, рассматривая контекст инициирующего прецедента Ie как некоторый класс IE IND  , на основании IND можно ограничить дальнейший поиск множества подобных прецедентов пространством поиска, принадлежащим  IPOS E -области, либо  IBND E -области при условии ( )IPOS E  , полностью иск- лючив из рассмотрения область  INEG E . Результатом сужения пространства поиска подобных прецедентов является огра- ничение множества перебора для динамической оценки подобия потоков событий, что значительно повышает быстродействие поиска и предотвращает «комбинатор- ный взрыв». Классификация событий. Классификация каждого очередного события наб- людаемого потока t  y S производится относительно заданной иерархии классов ,C  . Для классификации событий используется дедуктивный механизм правдопо- добной дескрипционной логики (ПДЛ) Λ , основными методами дедуктивного вывода в которой являются классификация и извлечение экземпляров. Классификация объектов – механизм системы фактов A ПДЛ Λ , определяющий для некоторого заданного экземпляра oA множество наиболее конкретных концеп- тов    1,... no C C C , которым данный экземпляр принадлежит, такое что      \| : mini i io o     I TC C T A C C . Механизм классификации основан на алгоритме нахождения наиболее узкого по вложению (конкретного) концепта LS, экземпляром которого является t  y S [11], и Динамический отбор прецедентов в интеллектуальной системе «Муссон» «Штучний інтелект» 4’2012 397 4Ш используется таким образом, что для каждого очередного наблюдаемого события t  y S (экземпляра) производится поиск наименьшего по вложению класса c C (концепта), такого что либо t c  y S , либо t c  y S ( t c  фy S ) и выполняется множество ограничений, связанных с c C , т.е.  c k • . В результате классификации каждое событие t  y S получает настолько точную (конкретную) классификацию, насколько позволяют полнота и точность наблюдения его параметров. Соответственно, определяется функция  root y как возвращающая класс заданного события y относительно иерархии ,C  ,   , c c C root y . Извлечение экземпляров – механизм системы фактов A ПДЛ Λ , который для некоторого заданного в терминологии T концепта cC находит множество экземп- ляров    1 ,... mc O o o , таких, что  , 1.. i ii m c  o o . Поскольку формализм ПДСС позволяет вводить оценки правдоподобности l , а используемая ПДЛ Λ допускает нечеткие и приближенные оценки концептов, соот- ветственно механизм извлечения экземпляров может быть ослаблен до некоторой степени правдоподобия  sup   . Слабое извлечение экземпляров – механизм A ПДЛ Λ , который для некоторого заданного в терминологии T концепта cC находит множество экземпляров    1 ,... mO c  o o , возможно являющихся экземплярами класса cC , т.е.    , 1.. i ii m l c    o o . Соответственно, определяется функция слабого извлечения экземпляров    , : , i ic o o creturn ф , возвращающая события заданного класса c с определенным порогом правдоподобия  . Формирование множества гипотез. Введем функцию   :j tget  y SS , возвраща- ющую очередное событие t  y S j -го сегмента наблюдаемого потока событий  S в резуль- тате мониторинга событий СДС. Предположим, что  t H H содержит множество рассматриваемых (активных) гипотез в момент времени t ,  0  H ;  tA содержит множество новых (активиро- ванных) гипотез, порожденных в момент времени t ;  tP обозначает множество пото- ков событий активированных в момент времени t прецедентов,  tC – множество указателей на активированные в момент времени t прецеденты. Исходя из потока классов событий, возвращаемых функцией root , найдем с помощью функции retrieve прецедент  tC , содержащий поток событий вида        1, ,t tj  retrieve root get  CP S , (4) исходя из нормированных оценок подобия           1 : , ,t t j i i i i   SIM root get SIM  SP C C C C C . (5) Далее в отношении каждого  tP , исходя из вновь полученного события t  y S , генерируется новая гипотеза   , , , , ,t i i i i i i ih C t с использованием ссылки на соот- ветствующий активированный прецедент iC . Все сгенерированные в момент времени t гипотезы  t ih проверяются, и произ- водится их слияние (композиция) с множеством активированных в момент времени t гипотез  tA :       :t t t i i i A A h h .Cв P . (6) Шерстюк В.Г. «Искусственный интеллект» 4’2012 398 4Ш Покрытие    t t  D y S гипотезы  t ih относительно вновь полученного события t  y S является подмножеством множества ссылок на прецеденты  tC , каждый из которых включает событие класса, абстрактного  troot  y S :         1 :t t t j t j    root   D C C Cy yS S , (7) Множество  tD может быть получено с использованием дедуктивного механи- зма ПДЛ Λ как       ,t t t  return root   D y yS S . (8) Вновь полученное событие t  y S считается непокрытым гипотезами, если    t t   D y S . Наличие непокрытого гипотезой события означает, что сегментация j -го сег- мента наблюдаемого потока событий  S произведена неправильно, поэтому происходит перестройка суффикса наблюдаемого потока, участвующего в сравнении с префиксами эталонных потоков согласно (6):   1 ,...t n t n t      suffix    = y y yS S SS , (9) после чего выполнение функции retrieve (4) повторяется циклически до тех пор, пока существуют непокрытые гипотезы. Когда достигается отсутствие непокрытых гипотез, производится слияние мно- жества гипотез  tA , порожденных в момент времени t , с множеством активных гипотез  1tH :      1t t tH = H Aв . (10) Сформированное множество  tH проверяется на предмет выполнения уста- новленных ограничений .: 2 X j i k v E.z с помощью функции  i jConst? v k, . Все гипотезы, ограничения которых не удовлетворяются, исключаются из даль- нейшего рассмотрения:          \| t t t i i j   Const?H h H v k ^, ,    t t i h H   .t i i hv ,     .t j ih .k k,      t t tH = H H (11) Таким образом, в результате извлечения подобных прецедентов формируется актуальное на момент времени t множество удовлетворяющих всем наложенным ограничениям k гипотез  tH , далее производится отбор уместных прецедентов. Отбор уместных прецедентов Задача отбора уместных прецедентов заключается в непрерывном анализе сфор- мированного множества гипотез, и получении на их основе множества заключений, объясняющих процесс, наблюдаемый с помощью потока событий  S . Множество сформированных правдоподобных заключений  tE ранжируется по их уместности (согласованности) относительно  S . Поскольку процесс наблюдения в СДС ведется непрерывно, с поступлением каждого очередного события множество гипотез  tH динамически изменяется, в частности, в активных гипотезах    t t i h H изменению подвергаются кусты  .t ih и  .t ih , оценки   .t ih и  .t ih . Динамический отбор прецедентов в интеллектуальной системе «Муссон» «Штучний інтелект» 4’2012 399 4Ш Метод отбора уместных прецедентов основан на последовательно-параллельном выполнении пяти функций: – динамической перестройки активных гипотез    t t i h H при наступлении очередного события 1ty ; – динамической переоценки правдоподобия каждой активной гипотезы    t t i h H и степени уверенности в наступлении события 1ty ; – разбиения множества гипотез  tH на множество интерпретируемых гипотез  t UH и множество отложенных гипотез  t PH , таких что      t t t U P H H H ; – формирования на основании множества интерпретируемых гипотез  t UH множества заключений  tE ; – ранжирования множества заключений  tE относительно отношения релеван- тности  REL [12]. Динамическая перестройка множества активных гипотез. При появлении в потоке  S каждого нового события 1t  y S необходимо просмотреть множество активных гипотез    t t i h H , при этом для каждой гипотезы: 1) проверяется, соответствует ли событие 1t  y S ожидаемому для данной гипотезы событию 1t  y . Если 1 1t t     хy y S , переходим на шаг 2) и обрабатываем событие, если 1 1t t     хy y S , гипотеза  t ih исключается из множества активных гипотез  tH :      1t t t i  H =H h ; 2) перестраивается куст наблюдаемых событий  1 .t i h , представляющий собой префикс эталонного потока событий прецедента ie :    1 1. .t t i i t   h h y ,   1 2. , ,...t i t   h y y y , ,  1 1 2 1. , ,...t i t t     h y y y , y ; (12) 3) перестраивается куст  1 .t i h , содержащий события, которые на момент вре- мени t еще не наблюдались,    1 1. .t t i i t    h h y ,   1 2. , , ...t i t t t l         h y y y ,  1 2. ,...t i t t l        h y y , 1 1t t     хy y S ; (13) 4) перестраивается суффикс наблюдаемого потока событий  suffix  S :     1t  su ffix su ffix   yS S ,    1 2, , ... t t    suffix    y y yS S SS ,   1 1 2 1, , ... t t t      suffix     y y y , yS S S SS ; (14) 4) пересчитывается нормализованная динамическая оценка подобия потоков  1 .t i h :       11 1. , . tt t i i        SIM suffix  h hS ; (15) 5) пересчитывается оценка правдоподобия гипотезы  1 .t i h ; 6) пересчитывается оценка степени уверенности  1 .t i h в наступлении ожидае- мого события 1t  y ; 7) рассчитывается производная по времени для оценки правдоподобия гипо- тезы  1 .t i h . Рассмотрим принцип формирования оценок правдоподобия в операциях 5) и 6). Шерстюк В.Г. «Искусственный интеллект» 4’2012 400 4Ш Динамическая переоценка правдоподобия активных гипотез. Для каждой гипотезы    t t i h H на основании ее куста , соответствующего наблюдаемым собы- тиям, может быть получена оценка правдоподобия i lh , соответствующая заданному отображению i в модели правдоподобия  [7]:          . , . 1 1 t t j i j i i t i e l l e                 h h C h y y . (16) Исходя из (12), чем длиннее путь  , приведший от наблюдаемых событий jy к вершине куста , тем выше оценка правдоподобия гипотезы i lh , что соответствует интуитивным ожиданиям повышения доверия к гипотезе по мере ее подтверждения. Далее, обладая оценкой   t il h , можно оценить степень уверенности в наступ- лении ожидаемого события 1t  y , такого что   1 t t i    prefix h .y :                 1 1 ., . , . \| 1 1 tt t j ij i i j i i t t i t e e l l l e l e                                      yy y y y hh C h C h . (17) По результатам расчета значение   t il h записывается в  1 .t i h , а   1 \| t t il   hy – в  1 .t i h :     1 .t t i il h h ,     1 1. \|t t i t il  h = hy . (18) Имея оценку   t il h , можно ранжировать множество гипотез  tH по правдопо- добию и исключать при наличии значительного числа гипотез  t H из рассмо- трения те гипотезы, оценка правдоподобия которых лежит ниже определенного порога  :           \| t t t t i il   H H h h , (19) что позволяет исключить возможность комбинаторного взрыва. Отбор множества интерпретируемых гипотез. В процессе рассмотрения гипотез и формирования заключений по каждой гипотезе    t t i h H , оценка правдоподобия которой растет с получением очередных наблюдаемых событий, существует дилемма – перевести ли данную гипотезу в множество интерпретируемых гипотез  t UH и сфор- мировать заключение, или отсрочить процесс формирования заключения, переведя гипотезу в множество отложенных гипотез  t PH , ожидая дальнейшего повышения оценки правдоподобия по мере поступления новых событий. Если интерпретировать гипотезу  t ih слишком поздно, можно пропустить момент достижения растущим кустом   .t ih целевой вершины, тогда поступление нового события, такого, что   1t t i  prefix h .y , резко снижает оценку правдоподобия   t il h . Соответственно, необходимо произвести откат до предыдущего события 1ty , закрыть текущий сегмент наблюдаемого потока j  S , начать новый сегмент 1j  S и вновь рас- смотреть событие ty . Указанная последовательность действий связана с перерасчетом динамических оценок подобия потоков событий, формированием нового множества гипотез  tH , нахождением для него покрытия  tD , перепроверкой ограничений гипотез  .t ih k, пересчетом оценок правдоподобия гипотез   t il h . Динамический отбор прецедентов в интеллектуальной системе «Муссон» «Штучний інтелект» 4’2012 401 4Ш Чтобы избежать высоких накладных расходов на откаты событий, необходимо оценить приращение оценки правдоподобия гипотезы, т.е. найти ее производную по времени:      t it i l l t    h h . (20) Тогда можно задать следующую функцию разбиения множества гипотез  tH :                            \| 0 \| 0 t t t t t U i U i i ht t t t t t P i U i i h l l l l                 partition H h H h h H H h H h h , (21) где h – ожидаемая оценка правдоподобия гипотезы  t ih . Ожидаемая оценка правдоподобия h может либо задаваться статически в про- цессе разработки ДСПИС, либо определяться динамически на основе нарабатываемой ДСПИС статистики откатов событий для каждого класса гипотез. Множество отложенных гипотез  t PH становится множеством гипотез на сле- дующей итерации, т.е.    1t t P H H , множество интерпретируемых гипотез  t UH передается дальше на стадию формирования заключений. Формирование множества заключений. Гипотеза  t ih называется объясняющей событие ty , если соответствующий прецедент  .t i Ch включает ty , т.е.    .t t i Croot  hy (  .t i tCh ф y ). Каждое событие t   y S в момент времени t может объясняться множе- ством гипотез   th . Задача формирования заключения в отношении события t   y S состоит в нахож- дении единственной активной гипотезы   tj h h , такой что j th ° y . Тогда задача формирования заключения m  yS в отношении наблюдаемого потока событий  S сводится к нахождению множества активных гипотез   tm   y hS , таких, что для каждого собы- тия i  y S наблюдаемого потока событий 1 ,... ,...i m        y y yS S SS каждая гипотеза   ti h h является заключением относительно события i  y S , т.е. i i  h ° y S . Соответственно, заключение  te представляет собой конъюнкцию вида   1 ... ...t i m    e h h h , i m  h yS (22) Множество заключений  tE строится из элементов множества  t UH с исполь- зованием принципа максимальной объясняющей способности [13]: чем больше конъ- юнктов содержит заключение  te , тем больше его объясняющая способность. Таким образом, если два потенциальных заключения   1 te и   2 te содержат в каче- стве конъюнкта одну и ту же гипотезу ih , в множество  tE добавляется лишь одна из них – та, число конъюнктов в которой больше:     1 1 : : .t t U i i i iC       E e H h e h фy yS ,  1 1 i me     h ... h ... h ,  2 1 j ne     h ... h ... h , 1 2e e   , m n . (23) Полученное таким образом множество заключений  tE на следующем этапе ранжируется соответственно оценке релевантности. Шерстюк В.Г. «Искусственный интеллект» 4’2012 402 4Ш Ранжирование множества заключений по релевантности. Для нахождения степени близости заключения  te наблюдаемому потоку событий  S используется модель уместности (релевантности) ДСС, на основании которой выводится соответ- ствующая оценка  REL [12]. Для этого каждое заключение    t t i e E , представляющее собой куст ПДСС   1 t i e Gе , сопоставляется с контекстом текущей ситуации 2IeCtx  Gе , также представляющим собой куст ПДСС. Оценка релевантности может быть получена как ( , ) ( , ) ( , ) I I I i ji R ji Re RII R i i i e e ji ji e E EEe E G                Rel Ctx Rel Rel Ctx h E h E e h h v v v , (24) где    1 2, ,... 1.. I I I I I n i e e e e e i n  Ctx v v v , v E.v, , 1 ... ...i i ji mi    e h h h , R i IE e e  . В свою очередь,   1 1 1( , ) e iI I e i e ji ji i jji       Ctx RelRel h h h v ,   1 1 1( , ) eIi I I I e i i ji e e i je      Ctx RelRel Ctx h v v . (25) Для повышения эффективности правдоподобного вывода в ДСПИС оценки релевантности сохраняются в ПДСС, при этом оценки релевантности кустов ПДСС 1 G , представляющих собой прецеденты, выводятся относительно узлов ПДСС 2 G , соот- ветствующих контекстам ситуаций. Вычисленная оценка релевантности прецедента некоторому контексту ситуации сохраняется в ПДСС и может эффективно использо- ваться в последующем без произведения новых расчетов. Выводы Основу ДСПИС «Муссон» составляет ядро, выполняющее задачи поиска и извле- чения прецедентов, поток событий в которых подобен наблюдаемому потоку событий, и отбора тех прецедентов, которые наиболее уместны в контексте сложившейся ситуации. В статье предложены методы извлечения и отбора прецедентов, включающих динамические потоки событий, работоспособные в динамических интеллектуальных системах в реальном времени. Предложенные методы, основанные на формировании гипотез и дальнейшем их уточнении с целью либо подтверждения, либо опровержения, предназначены для использования в ДСПИС «Муссон», предназначенной для управ- ления динамическими объектами. Подтвержденные гипотезы становятся заключениями и используются для последующего принятия решений оператором. Применение ДСПИС «Муссон» в информационно сложных для оператора ДО ситуациях приводит к снижению влияния человеческого фактора на качество и сво- евременность принятия решений. Литература 1. Сиек Ю.Л. Принципы синтеза интеллектуальных систем управления морскими динамическими объектами / Ю.Л. Сиек, Соэ Мин Лвин // Искусственный интеллект. – 2009. – № 4. – С. 448-456. 2. Топалов В.П. К проблеме человеческого фактора в судоходстве / В.П. Топалов, В.Г. Торский, Ю.В. Торский // Судовождение. – 2004. – Вып. 8. – C. 94-102. 3. Шерстюк В.Г. Принципы интеллектуальной поддержки принятия решений по управлению движением судна // В.Г. Шерстюк / Вестник Херсонского национального технического университета. – 2009. – № 3 (36). – С. 133-141. 4. Шерстюк В.Г. Сценарно-прецедентный подход к формированию управляющих воздействий в системе управления морского подвижного объекта / В.Г. Шерстюк // Проблемы информационных техно- логий. – 2009. – № 2 (6). – С. 69-77. Динамический отбор прецедентов в интеллектуальной системе «Муссон» «Штучний інтелект» 4’2012 403 4Ш 5. Liu Y. A CBR-based Approach for Ship Collision Avoidance / Y. Liu, C. Yang, X. Du // Proceedings of the 21st International Conference IEA/AIS-2008, Wroclaw, Poland. – Lecture Notes In Artificial Intelligence. – 2008. – Vol. 5027. – P. 687-697. 6. Шерстюк В.Г. Гибридная интеллектуальная СППР для управления судном / В.Г. Шерстюк, А.П. Бень // Искусственный интеллект. – 2008. – № 3. – С. 490-500. 7. Шерстюк В.Г. Использование деревьев событий для представления знаний в динамических преце- дентных интеллектуальных системах / В.Г. Шерстюк // Вестник Херсонского национального тех- нического университета. – 2011. – № 2 (41). – С. 100-111. 8. Шерстюк В.Г. Динамическая оценка подобия двух потоков событий / В.Г. Шерстюк // Вестник Херсонского национального технического университета. – 2011. – № 3 (42). – С. 491-496. 9. Martin F.J. Case-Based Sequence Analysis in Dynamic, Imprecise, and Adversarial Domains / F.J. Martin // Tesi doctoral by Universitat Politecnica De Catalunya, 2004. – 285 р. 10. Pawlak Z. Rough Sets / Z. Pawlak, W. Jerzy, R. Slowinski, W. Ziarko // Comm. of ACM. – 1995. – Vol. 38. – №. 11. – P. 88-95. 11. Baader F. The Description Logic Handbook: Theory, Implementation, Applications / F. Baader, D. Calvanese, D.L. McGuinness, D. Nardi, P.F. Patel-Schneider. – Cambridge University Press, Cambridge, UK, 2003. – 574 p. 12. Шерстюк В.Г. Отбор прецедентов на основе отношения релевантности в гибридной сценарно- прецедентной СППР / В.Г. Шерстюк // Моделювання та керування станом еколого-економічних систем регіону. – 2006. – Вип. 3. – С. 313-333. 13. Peng Y. Abductive Inference Models for Diagnostic Problem-Solving / Yung Peng, James A. Reggia. – NY : Springer-Verlag, 1990. – 284 p. Literatura 1. Siek Ju.L. Iskusstvennyj intellekt. 2009. №4. S. 448-456. 2. Topalov V.P. Sudovozhdenie. 2004. Vyp. 8. S. 94-102. 3. Sherstjuk V.G. Vestnik Hersonskogo nacional’nogo tehnicheskogo universiteta. 2009. №3 (36). S.133- 141. 4. Sherstjuk V.G. Problemy informacionnyh tehnologij. 2009. №2(6). S. 69-77. 5. Liu Y. Proceedings of the 21st International Conference IEA/AIS-2008, Wroclaw, Poland. Lecture Notes In Artificial Intelligence. 2008. Vol. 5027. P. 687-697. 6. Sherstjuk V.G. Iskusstvennyj intellekt. 2008. №3. S. 490-500. 7. Sherstjuk V.G. Vestnik Hersonskogo nacional’nogo tehnicheskogo universiteta. 2011. №2 (41). S. 100-111. 8. Sherstjuk V.G. Vestnik Hersonskogo nacional’nogo tehnicheskogo universiteta. 2011. №3 (42). S. 491-496. 9. Martin F.J. Case-Based Sequence Analysis in Dynamic, Imprecise, and Adversarial Domains. Tesi doctoral by Universitat Politecnica De Catalunya. 2004. 285 P. 10. Pawlak Z. Comm. of ACM. 1995. Vol. 38. № 11. P. 88-95. 11. Baader F. The Description Logic Handbook: Theory, Implementation, Applications. Cambridge University Press. Cambridge. UK. 2003. 574 p. 12. Sherstjuk V.G. Modeljuvannja ta keruvannja stanom ekologo-ekonomіchnyh system regіonu. 2006. Vyp. 3. S. 313-333. 13. Peng Y. Abductive Inference Models for Diagnostic Problem-Solving. NY: Springer-Verlag. 1990. 284 p. V.G. Sherstyuk Dynamic Case Selection in the "Monsoon” Intelligent System This article is devoted to theoretical investigation of the one class of intelligent systems – dynamic scenario-case systems, including the used case extraction and selection methods design and justification for “Monsoon” intelligent system. Dynamic intelligent system “Monsoon” is intended to dynamic objects control problems in informational complex situations. “Monsoon” intelligent system is based on the plausible event tree-like net, which is the situ- ation dynamics information storage formed by the event streams. The observed event stream correlates by the similarity degree in respect to the model event flows stored in the event tree-like net, based on the dynamic events stream similarity assessment method. The method proposed in this paper has a low computational complexity and can be used in dynamic real-time intelligent systems. Статья поступила в редакцию 05.06.2012.
id	nasplib_isofts_kiev_ua-123456789-57744
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
issn	1561-5359
language	Russian
last_indexed	2025-11-30T21:37:54Z
publishDate	2012
publisher	Інститут проблем штучного інтелекту МОН України та НАН України
record_format	dspace
spelling	Шерстюк, В.Г. 2014-03-14T13:09:39Z 2014-03-14T13:09:39Z 2012 Динамический отбор прецедентов в интеллектуальной системе «Муссон» / В.Г. Шерстюк // Штучний інтелект. — 2012. — № 4. — С. 392-403. — Бібліогр.: 13 назв. — рос. 1561-5359 https://nasplib.isofts.kiev.ua/handle/123456789/57744 656.612 В статье предложены методы извлечения и отбора уместных прецедентов, представляющих собой потоки событий, в реальном времени для динамической сценарно-прецедентной системы «Муссон», предназначенной для управления динамическими объектами. Предложенные методы основаны на формировании гипотез и дальнейшем их уточнении с целью либо подтверждения, либо опровержения: подтвержденная гипотеза становится заключением и используется для последующего принятия решений оператором. У статті запропоновані методи вилучення та відбору доречних прецедентів, що представляють собою потоки подій, в реальному часі для динамічної сценарно-прецедентної системи «Муссон», призначеної для управління динамічними об’єктами. Запропоновані методи засновано на формуванні гіпотез та їх уточнення надалі з метою або підтвердження, або спростування: підтверджена гіпотеза стає висновком і використовується для подальшого прийняття рішень оператором. The article suggests the real-time relevant cases retrieving and selecting methods for the dynamic scenario-case system '‘Monsoon" designed to the dynamic objects control. The proposed methods are based on the hypotheses formation of and their refinement in order to either confirm or disprove: the hypothesis becomes confirmed by the conclusion and used for operator's decision-making. ru Інститут проблем штучного інтелекту МОН України та НАН України Штучний інтелект Интеллектуальные системы планирования, управления, моделирования и принятия решений Динамический отбор прецедентов в интеллектуальной системе «Муссон» Динамічний відбір прецедентів в інтелектуальній системі «Мусон» Dynamic Case Selection in the “Monsoon” Intelligent System Article published earlier
spellingShingle	Динамический отбор прецедентов в интеллектуальной системе «Муссон» Шерстюк, В.Г. Интеллектуальные системы планирования, управления, моделирования и принятия решений
title	Динамический отбор прецедентов в интеллектуальной системе «Муссон»
title_alt	Динамічний відбір прецедентів в інтелектуальній системі «Мусон» Dynamic Case Selection in the “Monsoon” Intelligent System
title_full	Динамический отбор прецедентов в интеллектуальной системе «Муссон»
title_fullStr	Динамический отбор прецедентов в интеллектуальной системе «Муссон»
title_full_unstemmed	Динамический отбор прецедентов в интеллектуальной системе «Муссон»
title_short	Динамический отбор прецедентов в интеллектуальной системе «Муссон»
title_sort	динамический отбор прецедентов в интеллектуальной системе «муссон»
topic	Интеллектуальные системы планирования, управления, моделирования и принятия решений
topic_facet	Интеллектуальные системы планирования, управления, моделирования и принятия решений
url	https://nasplib.isofts.kiev.ua/handle/123456789/57744
work_keys_str_mv	AT šerstûkvg dinamičeskiiotborprecedentovvintellektualʹnoisistememusson AT šerstûkvg dinamíčniivídbírprecedentívvíntelektualʹníisistemímuson AT šerstûkvg dynamiccaseselectioninthemonsoonintelligentsystem

Динамический отбор прецедентов в интеллектуальной системе «Муссон»

Institution

Ähnliche Einträge