Диссертация (1149691), страница 14
Текст из файла (страница 14)
,(︃′)︃ℛ = ∪ ℰ ∪ { r⟨GInd( ) GInd(2 −1− )⟩ D = 1} Причем ′ =′D} ∪ {λP+c > D} а ℰ = {D > 0} ∪ {λ > 0} . Тогда конечноепри условиях{λP−c, ,′′′, ,,,.6,.решение второй задачи апостериорного вывода в случае стохастическогосвидетельства можно записать следующим образом [168]:′2 ∑︁−1′(︃)︃minT⟨GInd( ) GInd(2 −1− )⟩ D I Pevc [],′ℛ=0′(︃)︃′2−1∑︁⟨;⟩max⟨GInd()GInd(2−1−)⟩Pc=maxTD I Pevc []′=0 ℛP⟨c ; ⟩ min = ,, ,, ,, ,(3.25),Наконец, рассмотрим последний вид свидетельств — неточное. Неточ− ev +ное свидетельство ⟨ ,Pevc ,Pc ⟩ мы будем рассматривать как множество,,80всех стохастических свидетельств, оценки которых лежат в заданном ин− ev +тервале вероятностей [Pevc ,Pc ].
В данном случае решением первой ивторой задач апостериорного вывода будут накрывающие интервальныеоценки вероятностей [138; 156]. К сожалению, при решении первой задачиапостериорного вывода в случае фрагмента знаний над идеалом конъюнктов с интервальными оценками и неточных свидетельств (как и в случаестохастических) мы приходим к задачам нелинейного программирования;решение же построенных выше ЗЛП приводит лишь к накрывающим оценкам [123; 166]. Решением первой задачи будет интервал, ограниченныйследующими значениями:,′⎛2 −1⎜ ∑︁minev −Pc,⎜⎝ev,+6Pevc 6Pc2 −1⎜ ∑︁maxev −Pc,⎜⎝ev,+6Pevc 6Pcmin(r⟨GInd(=0 ∪ℰ′⎛,⎞′) GInd(2 −1− )⟩ ,P )I Pev []⎟c⎠ иc ⎟, ,,max r⟨GInd(=0 ∪ℰ(3.26)⎞′(︃)︃) GInd(2 −1− )⟩ ,P I Pev []⎟c⎠.c ⎟, ,,В случае фрагмента знаний со скалярными оценками вероятностейданные оценки будут точными, а не накрывающими.Решение второй задачи можно найти воспользовавшись следующимиформулами [168]:⎛Pc⟨ ; ⟩ min = ,′2 −1minev −Pc,evc⎜ ∑︁⎜⎝ev,+6P 6PcPc⟨ ; ⟩ max = ,=0 ℛ2 −1⎜ ∑︁maxev −Pc,evc⎜⎝ev,+6P 6Pc(︃maxT⟨GInd(′=0 ℛ)︃) GInd(2 −1− )⟩ D I Pev []⎟⎠,c ⎟, ,′⎛⟨GInd(min′ T⎞′(︃,⎞′)︃) GInd(2 −1− )⟩ D I Pev []⎟⎠.c ⎟, ,,(3.27)3.4.2Фрагмент знаний над множеством пропозиций-квантовПроведем аналогичные рассуждения для фрагмента знаний над множеством пропозиций-квантов.
Пусть нам непротиворечивый фрагмент+знаний с интервальными оценками вероятностей ⟨,P−q , Pq ⟩. Рассматривая последующие комбинации входных данных, мы не будем подробноприводить преобразования, а лишь дадим точные указания для решения81поставленных задач, поскольку рассуждения по большей части будут эквивалентны тем, что были приведены при рассмотрении фрагмента знанийнад идеалом конъюнктов.Предположим, что в данный фрагмент знаний поступило детерминированное свидетельство ⟨; ⟩. Решение первой задачи апостериорноговывода лежит внутри промежутка, границы которого являются решениемданной задачи [95; 168]:)︁(︁)︁(︁min s⟨ ; ⟩ , Pq и max s⟨ ; ⟩ ,Pq ,где∪ℰ+= {P−q 6 Pq 6 Pq } и (3.28) ∪ℰℰ = {Pq > 0} ∪ {(1 Pq) = 1}.,Вторую задачу апостериорного вывода можно свести к решению задачлинейного программирования — поиску минимума и максимума компонентследующего вектора [123; 137; 166]:s⟨ ; ⟩ ∘ D ,(3.29) где D = λPq , при ограничениях ℛ = ′(︃)︃∪ℰ ∪{ s⟨GInd( ) GInd(2 −1− )⟩ D′D} ∪ {λP+q > D} а ℰ = {D > 0} ∪ {λ′′′, ,,,=,>1}.
Причем = {λP−q 60} ∪ {(D,1) = λ}. В качестве переменных по которым ищутся максимуми минимум в данном уравнении выступают компоненты D и λ.Далее рассмотрим случай пропагации стохастического свидетельства.Аналогично фрагменту знаний над идеалом конъюнктов апостериорныевероятности квантов и вероятность свидетельства можно оценить лишьнакрывающим оценками.
Решение первой задачи будет ограничено минимумом и максимумом следующего выражения [168]:′′2 ∑︁−1 (︃ ⟨GInd( ) GInd(2 ′ −1− )⟩ )︃ evs,Pq Pq []=0, ,,(3.30)при условиях ∪ ℰ .Тогда конечное решение второй задачи апостериорного вывода вслучае стохастического свидетельства можно записать следующим образом [168]:′2 ∑︁−1′(︃)︃mins⟨GInd( ) GInd(2 −1− )⟩ ∘ D Pevq [],′=0 ℛ′(︃)︃′2−1∑︁⟨;⟩max⟨GInd()GInd(2−1−)⟩Pq=maxs∘D Pevq [].′=0 ℛP⟨q ; ⟩ min = ,, ,, ,, ,,(3.31)82Наконец рассмотрим наиболее трудоемкий с точки зрения вычисленийev + evслучай — пропагацию неточного свидетельства ⟨ ev , P−q , Pq ⟩ в фрагментзнаний с интервальными оценками вероятностей.Вероятность поступления неточного свидетельства будет лежать вследующих границах [168]:,,′⎛⎞2 ∑︁−1 (︃ ⟨GInd( ) GInd(2 ′ −1− )⟩ )︃ ev ⎟⎜s,Pq Pq []⎟min ev + ⎜⎝min⎠ иev −∪ℰPq 6Pev6Pq=0q, ,,,,′⎛⎞2 ∑︁−1 (︃ ⟨GInd( ) GInd(2 ′ −1− )⟩ )︃ ev ⎟⎜max ev + ⎜s,Pq Pq []⎟⎠.⎝maxev −ev∪ℰPq 6Pq 6Pq=0, ,,(3.32),,С учетом результатов, полученных для фрагмента знаний над идеалом конъюнктов [95; 168], апостериорные вероятности элементов фрагментазнаний над множеством пропозиций квантов в данном случае можно вычислить решим следующие ЗЛП [168]:′⎛Pq⟨ ; ⟩ min = ,2 −1⎜ ∑︁minev −Pq,⎜⎝ev,+evq6P 6Pq ,′Pq,⎜⎝ev,+6Pevq 6Pqmaxs⟨GInd(′=0 ℛ(︃)︃,⎞′)︃) GInd(2 −1− )⟩ ∘ D Pev []⎟⎠.q ⎟, ,⎞′) GInd(2 −1− )⟩ ∘ D Pev []⎟⎠,q ⎟, ,2 −1⎜ ∑︁maxev −⟨GInd(min′ s=0 ℛ⎛Pq⟨ ; ⟩ max =(︃,(3.33)3.4.3Фрагмент знаний над идеалом дизъюнктовНаконец рассмотрим последнюю из трех моделей фрагментов знаний— идеал дизъюнктов.
По аналогии с предыдущими двумя представлениями фрагментов знаний сперва рассмотрим наиболее тривиальный случай— пропагацию детерминированного свидетельства ⟨; ⟩. Напомним, чтоособенностью матрично-векторных уравнений над идеалом дизъюнктов является то, что мы оперируем не вектором вероятностей элементов идеала′Pd , а вектором Pd равному 1 − Pd .
Таким образом, говоря о фрагментезнаний с интервальными оценками вероятностей, мы будем иметь ввиду′+ ′−′структуру вида ⟨ , Pd ,Pd ⟩,,83Ниже рассмотрим решения задач апостериорного вывода для различных видов свидетельств. Начнем с детерминированного. Пусть в ФЗописанный выше поступило свидетельство ⟨; ⟩.По теореме 3.3.3 вероятность поступившего свидетельства можно бу(︁′ )︁дет вычислить по формуле (⟨ , ⟩) = d⟨ ; ⟩ ,Pd . Однако, поскольку′каждая из компонент вектора вероятностей Pd принимает значения из+интервала [P−d [],Pd []], то решение первой задачи апостериорного выводасводится к решению серии ЗЛП по нахождению максимума и миниму(︁′ )︁′ма значения d⟨ ; ⟩ ,Pd при условиях ℛ, где ℛ = {ℰ ∪ } = {L Pd >′−′+′0 ∪ Pd 6 Pd 6 Pd }.
Таким образом, решением первой задачи апостериорного вывода является замкнутый промежуток, ограниченный следующимизначениями [76; 91]: ,,(︁)︁(︁′ )︁min d⟨ ; ⟩ ,Pd ′ и max d⟨ ; ⟩ ,Pd .∪ℰ∪ℰ (3.34) Так как в данном фрагменте знаний нам заданы неточные оценки вероятности истинности дизъюнктов, то искомые во второй задаче апостериорныевероятности могут быть оценены лишь интервалом. Поиск верхней и ниж′⟨; ⟩ней границы Pdсводится к поиску минимума и максимума выражения′′⟨; ⟩M⟨ ; ⟩ Pd= d⟨ ; ⟩ P′ при ограничениях ℛ = ∪ ℰ . Стоит отметить, что здесьPd(d)и далее задача о поиске минимума и максимума решается независимо и′⟨; ⟩—отдельно для каждой целевой функции — компоненты вектора Pd′относительно переменных вектора Pd .Для сведения экстремальных задач по нахождению минимума имаксимума указанных целевых функций к ЗЛП нам нужно избавитьсяот множителя d⟨ ; 1⟩ P′ [154].
Воспользовавшись тем же приемом и обос(d)нованием, что и в случае ФЗ над идеалом конъюнктов и множествомпропозиций-квантов, зададим новый вектор переменных (и, таким образом,′произведем замену переменных) D = λPd , тогда, , ,, ,′′M⟨ ; ⟩ PdM⟨ ; ⟩ λPdM⟨ ; ⟩ D(︁)︁ = (︁)︁ = (︁)︁ .′′d⟨ ; ⟩ ,Pdd⟨ ; ⟩ ,λPdd⟨ ; ⟩ ,D Теперь положим d⟨ ;1⟩ D = 1. При новых переменных и введенных огра()ничениях исходные экстремальные задачи сведутся к поиску минимума и(︁)︁′′максимума компонент вектора M⟨ ; ⟩ D при условиях ∪ℰ ∪{ d⟨ ; ⟩ ,D = 1}.′′+Причем = {λP−d 6 D} ∪ {λPd > D}, а ℰ = {D > 0} ∪ {λ > 0}.
, 84Как и в решении первой задачи апостериорного вывода, данная совокупность линейных ограничений обеспечивает непротиворечивость ФЗ наддизъюнктами с новыми, апостериорными, оценками вероятностей. Здесь,аналогично предыдущему случаю, в качестве переменных выступают компоненты вектора D и λ.Перейдем ко второму виду свидетельств — стохастическому. Действуя аналогично предыдущим подразделам, будем рассматривать стохастическое свидетельство как ФЗ со скалярными оценками вероятностей⟨, Pd′ − ev,Pd′ + ev⟩, а значит и пропагацию такого свидетельства можнорассматривать как пропагацию серии детерминированных свидетельств.Ограничения, накладываемые на ЗЛП были введены при рассмотрениислучая детерминированного свидетельства, поэтому просто приведем выражение, вычисление минимума и максимума которого, даст границызамкнутого отрезка, ограничивающего вероятность поступления свидетельства [91; 112]:,,,,′2 ∑︁−1 (︃ ⟨GInd( ) GInd(2 ′ −1− )⟩ ′ )︃′ evd,Pd L Pd []=0, ,,,при условиях ∪ ℰ .Воспользовавшись преобразованиями знаменателя, проведеннымипри рассмотрении второй задачи апостериорного вывода для детерминированного свидетельства сформируем ЗЛП для решения второй задачи вслучае стохастического свидетельства:′ ,⟨; ⟩,min′2 ∑︁−1′(︃)︃⟨GInd( ) GInd(2 −1− )⟩ D L P′ ev [],minM=Pdd=0 ℛ′′(︃)︃′2 ∑︁−1′ ⟨ ; ⟩ max′ ev−1−)⟩⟨GInd()GInd(2Pd=maxMDLPd [].=0 ℛ′, ,,,, ,, ,(3.35),,′ ,ev,−′ ,ev,+Последним рассмотрим неточное свидетельство ⟨,Pd ,Pd ⟩.
Поаналогии с предыдущими случаями, неточное свидетельство будем рассматривать как множество всех стохастических свидетельств, оценки которых′ ev − ′ ev +лежат в заданном интервале вероятностей [Pd ,Pd ]. В данном случаерешением первой и второй задач апостериорного вывода будут накрывающие интервальные оценки вероятностей [91; 112]. Приведем уравнения для,,,,85их вычисления ниже:′⎛⎜⎜′ ev − min′ ev ′ ev + ⎝min∪ℰP6P 6P,,d,,dd2 ∑︁−1,⎜,d,,dd=02 ∑︁−1⎜′ ev − max′ ev ′ ev + ⎝max∪ℰP6P 6P,′⎛(︃(︃=0,d⟨GInd(⎞′)︃) GInd(2 −1− )⟩ ,P′ L P′ ev []⎟⎟⎠ иdd, ,,,d⟨GInd((3.36)⎞′)︃′ ,ev) GInd(2 −1− )⟩ ,P′ L P []⎟⎟⎠.dd, ,,Решение второй задачи можно найти воспользовавшись следующимиформулами [91; 112]:′⎛′ ,⟨; ⟩,minPd2 −1⎜ ∑︁⎜= ′min′ ev ′ ev + ⎝ev −P6P 6P,,d,,dd,′ ,⟨; ⟩,max′2 −1⎜ ∑︁⎜= ′max′ ev ′ ev + ⎝ev −P6P 6P,,d,,dd,⟨GInd(min′ M=0 ℛ⎛Pd(︃)︃) GInd(2 −1− )⟩ D L P′ ev []⎟⎟⎠,d, ,,,M⟨GInd(max′⎞′(︃=0 ℛ⎞′)︃) GInd(2 −1− )⟩ D L P′ ev []⎟⎟⎠.d, ,,,(3.37)3.5Отложенные вычисления компонент векторовИзложение в данном разделе основывается на результатах [93; 94; 165].Рассмотрим структуру вектора-селектора s⟨ ; ⟩ , полученное в разделе 3.3 данной главы.
Заметим, что на позиции вектора-селектора единицабудет стоять тогда и только тогда, когда квант согласован со свидетельством ⟨ , ⟩. Это, в частности, значит, что на всех позициях, где в двоичномпредставлении i стоит единица в m, также должна быть единица. В част˙ = ). С другой стороны, на всех позициях, вности, это значит, что (&которых содержит единичные биты, должно содержать нули. В противном случае квант не будет согласован с отрицательным свидетельством.˙ = .Это значит, что &Таким образом, любой элемент вектора-селектора s⟨ ; ⟩ можно выразить, воспользовавшись следующей формулой [93; 94]: ⎧⎪⎪⎨s⟨ ; ⟩ [] = ⎪ ⎪⎩1, если(︁0, иначе,)︁˙= и&(︁˙ =&)︁,(3.38)86где и — это числа, двоичное представление которых является характеристическими векторами конъюнктов, представляющих положительно иотрицательно означенные свидетельства соответственно в означенном алфавите.Аналогичный прием в отношении операций с битами в двоичном представлении индексов ,, может использоваться для выражения компонентвектора r⟨ ; ⟩ [94; 165; 168] : ⎧⎪⎪⎨˙ ̸= или&⟨;⟩r [] = ⎪bitscount( &˙ ) , иначе.⎪⎩(−1) 0, если(︁)︁(︁∨˙˙ ̸= 0&)︁,(3.39)Точка над знаками логических операций означает, что они выполняютсяпобитово.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
