О введении метрик на высказываниях экспертов с вероятностями

В настоящее время проявляется все больший интерес к анализу экспертной информации, заданной в виде вероятностных логических высказываний экспертов. Интересны исследования о высказываниях экспертов, представленных формулами исчисления высказываний (ИВ) с вероятностями. Возникают задачи об алгоритмах распознавания закономерностей, согласования логических (экспертных) знаний и их кластеризации [1–6]. Для решения этих задач необходимы метрики на знаниях.

В данной статье рассматриваются логические высказывания экспертов, представленные формулами исчисления высказываний с вероятностями, предлагаются способы задания расстояний на формулах-высказываниях с вероятностями, а также устанавливаются свойства введенных расстояний, для чего используются вероятностный и теоретико-модельный подходы [2; 5; 7].

Основные определения. Будем рассматривать знания экспертов, представленные формулами ИВ с вероятностями (вероятностные высказывания), т. е. высказывания вида « ф с вероятностью p ф », где ф -формула ИВ. Для таких высказываний будем использовать следующую запись:

^в =(ф p ф) , B j =^ ,p _v)-

Пусть 2 - база знаний, состоящая из формул ИВ, т. е. в 2 содержатся все формулы, с которыми будут работать эксперты; S ( ф ) - носитель формулы ф , т. е. множество элементарных высказываний, используемых при написании формулы ф , S ( 2 ) = ^ S ( ф ) - но- фе2

ситель совокупности знаний.

Рассмотрим совокупность P ( S ( 2 )) = 2 S ^{( 2 )} - множество всевозможных подмножеств множества S ( 2 ). Для простоты обозначения примем, что |P ( S ( 2 ))| = 2' ^{S ( 2 )} = п. Элементы множества P ( S ( 2 )) называются моделями . Более подробно о теории моделей см. в [2–4].

Пусть эксперты говорят о вероятностях (частости) формул на множестве всех n моделей, и каждое высказывание присутствует только с одной вероятностью. Тогда будем интерпретировать вероятность, данную экспертом, следующим образом: B = ^ф, p ф^. Это означает, что высказывание ф истинно на п ф = [ п ■ p ф ] моделях, где п = 2' S ^{( 2 )} - число всех моделей.

Пусть имеется два вероятностных логических высказывания B i = ^ф, p ф и B j = ^у, p _у . Дадим способ вычисления расстояния р ( B i , B j ) между такими высказываниями.

Интерпретируя данные экспертами вероятности описанным выше способом, получаем, что высказывание ф истинно на n ф = [ n ■ p ф ] моделях, а высказывание у - на n _у = [ n ■ p _v ] моделях. Отметим, однако, что при таком подходе мы не знаем, на каких именно моделях каждое высказывание истинно, а также число моделей, на которых эти высказывания истинны одновременно.

Решим следующую задачу: пусть высказывание ф истинно на n ф моделях, высказывание у истинно на n _у моделях и к - число моделей, на которых эти высказывания истинны одновременно. Вычислим расстояние между высказываниями B i = ^ф, p ф ^ и B j Цу, p у У

Обозначим рассматриваемые далее расстояния через р _к ( B , B j -), где к = 0,1,2, ...,min( n ф , n у ).

Как и в [2-4], расстояние р _к ( B i , B j ) для каждого к = 0,1,2,. . , min( n ф , n _у ) определим через разность:

• n. - к + n, - к n. + n, - 2 к

ф у ф у р к(Bi, Bj) =-----------------=--------------.

nn

Теорема 1. Для расстояний р _к ( B i -, B j ) справедливы свойства:

• 1)    0 <р к ( B i , B j ) <  1;

• 2)    р к ( B„ B j ) = р к ( B j , B );

• 3)    р к ( B i , B j ) <р к ( B i , B s ) + р к ( B s , B j );

• 4)    B i = B j -ор к ( B , B j -) = 0  ( B i = B Оф у и

• pф = pу, т. е. формулы ф и у истинны на одних и тех же моделях);

• 5)    B    B j Oр к ( B , B j ) = 1;

• 6)    р к ( B , B j ) = 1 - р к ( B , ^- B j ) = р к ( ^- B , ^- B j );

• 7)    р к ( B„ B j ) = р к ( B i л B j -, B -v B j ).

Докажем неочевидное свойство 3. Определение р _к ( B , B j ) можно переписать следующим образом:

n ф + n у- 2 к = n фДу = n (-флу)v(фл-у) nnn рк (B, Bj) =

(по определению симметрической разности). Тогда для произвольного высказывания Bs = ^х, pх ^ нетрудно доказать, что nфДу < nфдх + nхДу, откуда р к (Д, Bj) = n^< ""' ■ n^ = nnn

= р к ( B - , B s ) + р к ( B s , B j -).

Докажем свойство 4 сначала слева направо (о). Если Bi ^ Bj, то ф = у и, значит, nф = nу = к. Следо- вательно, n + n, -2к рк (B-, Bj)     '     ------= 0.

n

Докажем свойство 4 в обратную сторону (о). Если рк (B, Bj) = 0, то nф+ nу- 2к = 0. Так как к может принимать значения 0,1, 2, ., K, min(nф, nу), то (nф + nу - 2к = 0 о nф = nу = к).       Следовательно, фон, значит, Bi ^ Bj.

Докажем свойство 5 слева направо (о). Если Bt = "Bj, то ф =-у. Тогда nф= n - nу и к = 0, следовательно n + n,„ - 0 и рк (B-, Bj) = ф у = n = 1.

nn

Докажем свойство 5 в обратную сторону ( о ). Если р _к ( B_i , B j ) = 1, то n ф + n _у - 2 к = n . Так как к может принимать значения 0,1, 2, . , K , min( n ф , n _у ), то ( n ф + n _у - 2 к = n о n ф + n _у = n и к = 0). Следовательно, ф ^ у и B_i = ^- B j .

Докажем свойство 6:

n + n, - 2 к р к ( B i , B j ) =        ------,

n

-D4 ^П ф⁺ n -у - ^{2( n} ф^{- к} )   ⁿ ф^{+ ( n - n} у ) ^{- 2( n} ф^{- к} )

рк(Bi, Bj)=-------------------=----------------------- nn n - n ф- n у

2 k

,  ⁿ ф^{+ n} у^{- 2 к}

1-- n

= 1 -р к ( B i , B j ),

Откуда нетрудно доказать, что

1 -р к ( B - , ^- B j ) = р к ( ^- B - , ^- B j ).

Докажем свойство 7.

Легко доказать, что n(флу)Д(фvу) = nфДу . Тогда nn гч л R т> х , Т> \ _  (флу)Д(фvу) _ фДу) _    / D D \ рк(BiлBj,Biv Bj) =-----------= = рк(Bi,Bj).

nn

Далее предложим несколько способов вычисления расстояния р ( B_i , B j ) между вероятностными высказываниями B i =(ф , p ф) и B j =(у , p у у

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

Предположим, что все значения числа k равновероятны. Тогда расстояние между вероятностными высказываниями B = ^ф, p ф ^ и B j = ^у, p _у ^ определим как усреднение расстояний р _к ( B , B j ) по всем значениям k :

min( n _φ , n _ψ )

∑ ρ k ( B i , B j ) ρ ( B_i , B_j ) = ^{k = 0}                 .

min( n _φ , n _ψ ) + 1

Для этого расстояния также справедлива теорема 1, и слагаемые под знаком суммы можно взять с весами, в которых учтены мнения экспертов.

Если экспертами указано, какое значение k предпочтительнее, то в качестве ρ ( B_i , B_j ) берется расстояние ρ _k ( B_i , B_j ). Это возможно в случае, когда мы знаем, что пересечение состоит из k моделей.

Можно подойти к вопросу определения расстояния ρ _k ( B_i , B_j ) и с вероятностно-статистической точки зрения и для каждого k вычислить частоту того, что высказывания φ и ψ одновременно истинны на k моделях.

Найдем частоту (вероятность) p_k того, что в выбранных n _φ и n _ψ моделях (они выбираются из n моделей) будет k моделей, на которых высказывания φ и у истинны одновременно, где к = 0,1,2, .., K , min( n _φ , n _ψ ).

Сначала определим вероятностное пространство Ω , A , p , где Ω – пространство элементарных исходов - моделей, Q = { 0,1, 2, _ , K , min( n _ф , n _у ) } -число возможных совпадений моделей в наборах из n _φ и n _ψ моделей; A – система пар подмножеств множества моделей Ω , образующая σ -алгебру событий; p – вероятность на Ω , A .

Определим для к = 0,1, 2, ^ , K , min( n _ф , n _у ) на декартовом произведении Ω ⊗ A случайную величину ξ :

ξ ( k ) = ρ k ( B i , B j ),

• т. е. функция ξ каждому k из Ω будет ставить в соответствие число – расстояние ρ _k ( B_i , B_j ).

Вероятность этого события (с пересечением k ) на классе из n моделей можно вычислить так:

k n _φ - k n _ψ - k n n - k n - n p =                ^φ ,

• ^k       C^{n φ} C^{n ψ}

nn где Cnnφ – число способов выбрать nφ моделей из n моделей.

Действительно, любой набор, состоящий из nφ моделей, может сочетаться с любым набором, состоящим из nψ моделей, значит число (Cnnφ ⋅ Cnnψ ) определяет количество всех способов выбрать два набора, один из которых состоит из nφ моделей, а другой – из nψ моделей. Выбрать k моделей, которые будут общими в этих наборах, из n моделей можно Cnk способами. Тогда остальные (nφ - k) и (nψ - k) моделей должны быть дизъюнктными. Следовательно, остальные (nφ -k) моделей для пополнения набора, состоящего из k, до nφ моделей можно выбрать Cnnφ--kk способами, а (nψ - k) моделей для получения набора, состоящего из nψ моделей, с учетом наших предположений, – Cnn-ψn-k способами. Итак, имеется всего (n -k n -k

C_n^kC_{n -} ^φ _k C_{n -} ^ψ _n ) способов выбрать два набора, один из которых состоит из n _φ моделей, а другой – из n _ψ моделей, и k моделей в этих наборах моделей совпадут. Поэтому вероятность того, что k моделей совпадет в наборах из n _φ и n _ψ элементных моделей, составит

C k C n _φ - k C n _ψ - k n n - k n - n _φ p =                .

• ^k       C^{n φ} C^{n ψ}

nn

В результате получим, что расстояния n + n - 2k ρk(Bi,Bj)= φ ψ n будут появляться с вероятностями

C k C n _φ - k C n _ψ - k n n - k n - n _φ p =                ^φ ,

• k        C n φ C n ψ

nn где к = 0,1, 2,. ^, K, min(nф, nу). Эти вероятности (и близкие к ним числа) можно использовать в качестве весов-коэффициентов расстояний для получения результирующего расстояния для данных формул с вероятностями (подробнее об этом см. дальше).

Заметим, что при таком подходе главную роль играют не сами формулы, а числа, определяющие количество моделей и их пересечения. Не имея другой информации, мы рассмотрели все возможные подмножества для подсчета частости (вероятности) появления расстояния для конкретного k . Используя свойство инвариантности расстояний между формулами и вероятностей высказываний (формул) [2–4], можно получить аналогичный результат, но с меньшим носителем знаний, включающим только те, которые встречаются в двух формулах, для которых и ищется расстояние. Будем считать, что мы так и сделали с самого начала. И тогда наш расчет будет оптимальным.

Зная вероятности pk для каждого расстояния ρk(Bi,Bj), в качестве расстояния между вероятностными высказываниями Bi = φ, pφ   и Bj = ψ, pψ можно взять, например, наиболее вероятное расстояние ρ(Bi,Bj) =ρm(Bi,Bj), где pm =maxpk, для кото-k рого справедлива теорема 1.

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

Если мы возьмем произвольные веса p_k (исходя из экспертных оценок или дополнительных сведений экспертов, которые могут и не совпадать!) для расстояний ρ _k ( B_i , B_j ) таким образом, чтобы они подчинялись закону распределения, то получим общий случай для адаптивного поиска нужного расстояния между формулами с вероятностями. Тогда в качестве расстояния между вероятностными высказываниями B i = φ , p _φ и B_j = ψ , p _ψ можно взять величину, равную математическому ожиданию (центру тяжести) или среднему значению случайной величины ξ :

min( n _φ , n _ψ )

ρ ( B i , B j ) = M ξ= ∑ ρ k ( B i , B j ) ⋅ p k .

k = 0

Теорема 2. Для расстояния ρ ( B_i , B_j ) справедливы свойства:

• 1)    0 ≤ρ ( B i , B j ) ≤ 1;

• 2)    ρ ( B i , B j ) =ρ ( B j , B i );

• 3)    ρ ( B i , B j ) ≤ρ ( B i , B s ) +ρ ( B s , B j );

• 4)    если ρ ( B_i , B_j ) = 0, то B_i ≡ B_j ;

• 5)    ρ ( B i , B j ) = 1 -ρ ( B i , B j ) =ρ ( B i , B j );

• 6)    ρ ( B i , B j ) =ρ ( B i ∧ B j , B i ∨ B j ).

Докажем неочевидное свойство 3. Для расстояния B i = φ , p _φ по свойству 3 теоремы 1 имеем ρ _k ( B_i , B_j ) ≤ ρ _k ( B_i , B_s ) +ρ _k ( B_s , B_j ). Тогда по свойствам математического ожидания:

• а)    ξ ≤ η ⇒ M ξ ≤ M η;

• б)    M ( ξ+η ) = M ξ+ M η , откуда получаем требуемое свойство для расстояния.

Докажем свойство 4. Пусть ξ ( k ) = ρ _k ( B_i , B_j ) ≥ 0 и M ξ = 0. Тогда по свойству математического ожидания ξ ( k ) = ρ _k ( B_i , B_j ) = 0 с вероятностью, равной 1, а по свойству 4 теоремы 1 B_i ≡ B_j .

Докажем свойство 5. Так как для расстояния ρ _k ( B_i , B_j ) по свойству 6 теоремы 1 справедливо равенство

ρk(Bi,Bj)=1-ρk(Bi,Bj)=ρk(Bi,Bj), тогда по свойствам математического ожидания:

• а)    если p ( ξ = η ) = 1 и ∃ M ξ (математическое ожидание существует), то M ξ = M η ;

• б)    M ( a + b ξ ) = a + bM ξ , откуда получаем требуемое свойство для расстояния ρ ( B_i , B_j ).

Таким образом, в данной статье исследованы способы введения метрик на классах эквивалентных высказываний экспертов, заданных формулами ИВ с вероятностями. Такое исследование необходимо для решения задач согласования вероятностных высказываний экспертов, кластеризации и для построения баз знаний и экспертных систем. Результаты переносятся на формулы над бесконечными носителям и формулы с переменными языка первого порядка с использованием измеримых (для фиксированной теории) подклассов измеримых (в том числе и метрических) моделей.