ОЦЕНКА ЧУВСТВИТЕЛЬНОСТИ РЕЗУЛЬТАТА ЛОКАЛЬНОГО АПРИОРНОГО ЛОГИКО-ВЕРОЯТНОСТНОГО ВЫВОДА В ИНТЕЛЛЕКТУАЛЬНЫХ ИНФОРМАЦИОННЫХ СИСТЕМАХ
ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ И СИСТЕМЫ
УДК 004.8
А. Л. ТУЛУПЬЕВ
ОЦЕНКА ЧУВСТВИТЕЛЬНОСТИ РЕЗУЛЬТАТА ЛОКАЛЬНОГО АПРИОРНОГО ЛОГИКО-ВЕРОЯТНОСТНОГО ВЫВОДА
В ИНТЕЛЛЕКТУАЛЬНЫХ ИНФОРМАЦИОННЫХ СИСТЕМАХ
Рассматривается способ оценки зависимости вариации результатов (чувствительности) априорного вывода от допустимой вариации исходных данных во фрагменте знаний алгебраической байесовской сети. Предлагаемый способ основан на решении совокупности задач линейного программирования. Получена верхняя оценка характеристики чувствительности, линейно зависящая от радиуса вариации исходных данных.
Ключевые слова: оценка чувствительности, логико-вероятностный вывод, алгебраические байесовские сети.
В базах знаний интеллектуальных систем вследствие определенных причин [1, 2] накапливаются не только достоверные знания, но также и знания, отличающиеся неопределенностью, неточностью, нечеткостью. Эти знания нельзя исключить, поскольку перечисленные „отрицательные“ факторы не означают абсолютного отсутствия сведений о предметной области, а лишь характеризуют неполноту доступных знаний о ней [3]. Зачастую даже в условиях информационного дефицита [4] (т.е. неполноты знаний и/или их неопределенности) можно принять обоснованное решение, учтя все доступные сведения.
Представить неопределенность знаний можно различными способами — например, приписать утверждению меру его истинности, в качестве которой будем рассматривать вероятностную меру. Небольшие совокупности утверждений с вероятностными оценками их истинности могут быть организованы во фрагменты знаний (ФЗ). Набор фрагментов знаний, в свою очередь, образует базу фрагментов знаний с неопределенностью. Представлением этой базы для разработки как структур данных в программном коде, так и самого кода являются, в частности, алгебраические байесовские сети (АБС) [2, 5, 6]. Предложенные в работах [7, 8] алгоритмы позволяют проверять непротиворечивость АБС (поддержание непротиворечивости), выводить новые оценки истинности утверждений на основе известных (априорный вывод), учитывать влияние поступивших свидетельств на вероятность истинности элементов АБС (апостериорный вывод).
Цель настоящей статьи — исследовать чувствительность априорного вывода локально, т.е. когда он осуществляется в отдельном фрагменте знаний. Под чувствительностью понимается зависимость результата вывода от точности указания исходных данных. Исследовать чувствительность — значит оценить характеристики зависимости вариации результата от вариации исходных данных. Для каждой предметной области известны конкретные определения указанных вариаций и зависимости между ними, а также сформированы наборы характеристик последних.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2009. Т. 52, № 9
4 А. Л. Тулупьев
Обозначения. Согласно работам [2, 5—8] введем следующие обозначения: P — вектор вероятностей истинности элементов фрагмента знаний, упорядоченных специальным образом [5];
P — вектор скалярных (точечных) оценок этих вероятностей, здесь индекс „◦“ ука-
зывает на использование исходных данных; Pˆ — вектор проварьированных вероятностей истинности элементов фрагмента
знаний, а ∆ = Pˆ − P — собственно вариация исходных данных, которая пред-
полагается допустимой, т.е. проварьированные вероятности непротиворечивы: IPˆ ≥ 0 ;
f — утверждение, составленное из атомарных утверждений, вошедших во фраг-
мент знаний; в силу этого вероятность f выражается в виде скалярного про-
изведения через вероятности истинности элементов ФЗ: p = p( f ) = L ⋅ P ; с
учетом вышеописанной допустимой вариации изменившаяся оценка вероятности f будет иметь вид pˆ = pˆ ( f ) = L ⋅ Pˆ .
Для соблюдения требования аксиоматики вероятностной логики должна выполняться
система
неравенств,
записанная
в
векторном
виде:
IP ≥ 0 ,
матрица
I
=
⎡1 ⎣⎢0
−1⎤[n] 1⎦⎥
—
степень
Кронекера [5], здесь n — число атомарных утверждений, вошедших во фрагмент знаний.
Предполагается, что набор исходных данных непротиворечив: IP ≥ 0 .
Для измерения вариаций исходных данных и результата необходимы две метрики: метрика r , аргументы которой есть векторы вероятностей истинности элементов ФЗ: r(Pˆ , P);
метрика d , аргументы которой — оценки вероятности истинности утверждения f : d ( pˆ , p).
Постановка задачи. Пусть известно положительное число — радиус вариации δ > 0 , которое ограничивает вариацию исходных данных: r(Pˆ , P) ≤ δ. Требуется с учетом данных и
ограничений, перечисленных выше, исследовать величину d ( pˆ, p) : либо определить ее
функциональную зависимость d ( pˆ, p) = V (Pˆ , P, δ, …) , либо найти ее верхнюю границу (точ-
ную верхнюю границу, максимум) ε . При этом процесс вычислений должен опираться на хо-
рошо изученные и реализованные алгоритмы.
При анализе чувствительности особую значимость имеет выбор метрик: именно им оп-
ределяется сложность, разрешимость и „алгоритмизуемость“ возникающих в процессе иссле-
дования экстремальных задач. В рассматриваемом случае предлагается выбрать следующие
метрики:
r(Pˆ , P) = max
i=0, ..., 2n −1
pˆ i
−
pi
и d ( pˆ, p) = pˆ − p . Использование таких метрик, как бу-
дет видно в дальнейшем, приведет к решению задач линейного программирования (ЗЛП);
евклидова же метрика, например, потребовала бы решения задач с более сложным множест-
вом квадратичных ограничений.
Предлагаемый подход к решению задачи. Рассмотрим экстремальные задачи, кото-
рые позволяют вычислить характеристики чувствительности результата априорного вывода
p к допустимой вариации исходных данных. Вычислим величины
ε = sup {d ( pˆ , p)} и ε(P ) = sup {d ( pˆ , p)} ,
IPˆ ≥0,IP≥0,
IPˆ ≥0, IP≥0,
r(Pˆ ,P)≤δ
r(Pˆ ,P)≤δ, P=P
при этом величина ε(P ) необходима для исследования ситуации в случае с конкретным на-
бором исходных оценок P = P .
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2009. Т. 52, № 9
Оценка чувствительности результата локального априорного логико-вероятностного вывода 5
В первую очередь, сведем ограничения экстремальных задач к набору линейных ра-
венств и неравенств. Очевидно, что ограничения IPˆ ≥ 0 , IP ≥ 0 и P = P изначально линейны, их изменять
не требуется. Неравенство
r(Pˆ , P) ≤ δ
раскрывается как
max
i=0, ..., 2n −1
pˆi
−
pi
≤ δ , что эквива-
лентно
системе
линейных
неравенств
{−δ ≤
pˆi
−
pi
}≤ δ
i=2n i=0
−1
.
Таким
образом,
все
ограниче-
ния в рассмотренных экстремальных задачах линейные.
По определению целевая функция d ( pˆ, p) = pˆ − p . Чтобы свести экстремальную задачу
к двум ЗЛП, достаточно решить последние отдельно для разности pˆ − p и разности p − pˆ .
Таким образом, процесс оценивания характеристик чувствительности сводится к реше-
нию совокупности задач линейного программирования:
ε
=
{max pˆ
IPˆ ≥0,IP≥0,
−
p,
p
−
pˆ}
,
ε(P ) =
max
IPˆ ≥0, IP≥0,
{ pˆ − p, p − pˆ} .
r(Pˆ ,P)≤δ
r(Pˆ ,P)≤δ, P=P
Алгоритмы решения ЗЛП известны, хорошо изучены, а также реализованы в библиоте-
ках, рассчитанных на ряд систем программирования.
Верхняя оценка. Можно оценить характеристики чувствительности и не прибегая к
решению ЗЛП, пусть и несколько потеряв в точности оценки. В соответствии с полученной
оценкой можно предъявить обоснованные требования к точности измерения, определения
или расчета исходных данных.
Учитывая, что pˆ0 = p0 = 1 [2, 5], оценим
d ( pˆ, p) = pˆ − p = L ⋅ Pˆ − L ⋅ P = L ⋅ (Pˆ − P) =
2n −1
2n −1
2n −1
2n −1
= ∑ li ( pˆi − pi ) ≤ ∑ li ⋅ ( pˆi − pi ) ≤ ∑ li δ = δ ∑ li .
i=0
i=1 ≤δ i=1
i=1
Таким образом, установлена легко вычисляемая верхняя граница для оценки чувстви-
2n −1
тельности — ε ≤ δ ∑ li . Вопрос о том, точна ли эта верхняя граница, остается открытым. i=1
Некоторые результаты, представленные в данной статье, получены в рамках проекта, под-
держанного Российским фондом фундаментальных исследований (грант № 09-01-00861-а).
СПИСОК ЛИТЕРАТУРЫ
1. Крейнович В. Я., Нгуен Т. Х., Городецкий В. И. и др. Применение интервальных степеней доверия: аналитический обзор // Информационные технологии и интеллектуальные методы: Сб. трудов СПИИРАН. СПб.: СПИИРАН, 1999. Вып. 3. С. 6—61.
2. Тулупьев А. Л., Николенко С. И., Сироткин А. В. Байесовские сети: логико-вероятностный подход. СПб.: Наука, 2006. 607 с.
3. Нариньяни А. С. НЕ-факторы: неточность и недоопределенность — различие и взаимосвязь // Изв. РАН. Сер. Теория и системы управления. 2000. № 5. С. 44—56.
4. Хованов Н. В. Анализ и синтез показателей при информационном дефиците. СПб.: Изд-во С.-Петербург . ун-та, 1996. 196 с.
5. Тулупьев А. Л. Алгебраические байесовские сети: локальный логико-вероятностный вывод: Учеб. пособие. СПб.: СПбГУ — ООО Изд-во „Анатолия“, 2007. 80 с.
6. Тулупьев А. Л. Алгебраические байесовские сети: глобальный логико-вероятностный вывод в деревьях смежности: Учеб. пособие. СПб.: СПбГУ — ООО Изд-во „Анатолия“, 2007. 40 с.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2009. Т. 52, № 9
6 С. А. Алексеев
7. Тулупьев А. Л., Сироткин А. В., Николенко С. И. Синтез согласованных оценок истинности утверждений в интеллектуальных информационных системах // Изв. вузов. Приборостроение. 2006. Т. 49, № 7. С. 20—26.
8. Тулупьев А. Л., Николенко С. И., Никитин Д. А., Сироткин А. В. Синтез апостериорных оценок истинности суждений в интегрированных базах знаний: детерминированный вариант // Там же. 2006. Т. 49, № 11. С. 35—39.
Александр Львович Тулупьев
Сведения об авторе — канд. физ.-мат. наук, доцент; Санкт-Петербургский институт инфор-
матики и автоматизации РАН, лаборатория прикладной информатики; E-mail: alt@iias.spb.su
Рекомендована кафедрой технологий программирования СПбГУ ИТМО
Поступила в редакцию 15.02.08 г.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2009. Т. 52, № 9
УДК 004.8
А. Л. ТУЛУПЬЕВ
ОЦЕНКА ЧУВСТВИТЕЛЬНОСТИ РЕЗУЛЬТАТА ЛОКАЛЬНОГО АПРИОРНОГО ЛОГИКО-ВЕРОЯТНОСТНОГО ВЫВОДА
В ИНТЕЛЛЕКТУАЛЬНЫХ ИНФОРМАЦИОННЫХ СИСТЕМАХ
Рассматривается способ оценки зависимости вариации результатов (чувствительности) априорного вывода от допустимой вариации исходных данных во фрагменте знаний алгебраической байесовской сети. Предлагаемый способ основан на решении совокупности задач линейного программирования. Получена верхняя оценка характеристики чувствительности, линейно зависящая от радиуса вариации исходных данных.
Ключевые слова: оценка чувствительности, логико-вероятностный вывод, алгебраические байесовские сети.
В базах знаний интеллектуальных систем вследствие определенных причин [1, 2] накапливаются не только достоверные знания, но также и знания, отличающиеся неопределенностью, неточностью, нечеткостью. Эти знания нельзя исключить, поскольку перечисленные „отрицательные“ факторы не означают абсолютного отсутствия сведений о предметной области, а лишь характеризуют неполноту доступных знаний о ней [3]. Зачастую даже в условиях информационного дефицита [4] (т.е. неполноты знаний и/или их неопределенности) можно принять обоснованное решение, учтя все доступные сведения.
Представить неопределенность знаний можно различными способами — например, приписать утверждению меру его истинности, в качестве которой будем рассматривать вероятностную меру. Небольшие совокупности утверждений с вероятностными оценками их истинности могут быть организованы во фрагменты знаний (ФЗ). Набор фрагментов знаний, в свою очередь, образует базу фрагментов знаний с неопределенностью. Представлением этой базы для разработки как структур данных в программном коде, так и самого кода являются, в частности, алгебраические байесовские сети (АБС) [2, 5, 6]. Предложенные в работах [7, 8] алгоритмы позволяют проверять непротиворечивость АБС (поддержание непротиворечивости), выводить новые оценки истинности утверждений на основе известных (априорный вывод), учитывать влияние поступивших свидетельств на вероятность истинности элементов АБС (апостериорный вывод).
Цель настоящей статьи — исследовать чувствительность априорного вывода локально, т.е. когда он осуществляется в отдельном фрагменте знаний. Под чувствительностью понимается зависимость результата вывода от точности указания исходных данных. Исследовать чувствительность — значит оценить характеристики зависимости вариации результата от вариации исходных данных. Для каждой предметной области известны конкретные определения указанных вариаций и зависимости между ними, а также сформированы наборы характеристик последних.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2009. Т. 52, № 9
4 А. Л. Тулупьев
Обозначения. Согласно работам [2, 5—8] введем следующие обозначения: P — вектор вероятностей истинности элементов фрагмента знаний, упорядоченных специальным образом [5];
P — вектор скалярных (точечных) оценок этих вероятностей, здесь индекс „◦“ ука-
зывает на использование исходных данных; Pˆ — вектор проварьированных вероятностей истинности элементов фрагмента
знаний, а ∆ = Pˆ − P — собственно вариация исходных данных, которая пред-
полагается допустимой, т.е. проварьированные вероятности непротиворечивы: IPˆ ≥ 0 ;
f — утверждение, составленное из атомарных утверждений, вошедших во фраг-
мент знаний; в силу этого вероятность f выражается в виде скалярного про-
изведения через вероятности истинности элементов ФЗ: p = p( f ) = L ⋅ P ; с
учетом вышеописанной допустимой вариации изменившаяся оценка вероятности f будет иметь вид pˆ = pˆ ( f ) = L ⋅ Pˆ .
Для соблюдения требования аксиоматики вероятностной логики должна выполняться
система
неравенств,
записанная
в
векторном
виде:
IP ≥ 0 ,
матрица
I
=
⎡1 ⎣⎢0
−1⎤[n] 1⎦⎥
—
степень
Кронекера [5], здесь n — число атомарных утверждений, вошедших во фрагмент знаний.
Предполагается, что набор исходных данных непротиворечив: IP ≥ 0 .
Для измерения вариаций исходных данных и результата необходимы две метрики: метрика r , аргументы которой есть векторы вероятностей истинности элементов ФЗ: r(Pˆ , P);
метрика d , аргументы которой — оценки вероятности истинности утверждения f : d ( pˆ , p).
Постановка задачи. Пусть известно положительное число — радиус вариации δ > 0 , которое ограничивает вариацию исходных данных: r(Pˆ , P) ≤ δ. Требуется с учетом данных и
ограничений, перечисленных выше, исследовать величину d ( pˆ, p) : либо определить ее
функциональную зависимость d ( pˆ, p) = V (Pˆ , P, δ, …) , либо найти ее верхнюю границу (точ-
ную верхнюю границу, максимум) ε . При этом процесс вычислений должен опираться на хо-
рошо изученные и реализованные алгоритмы.
При анализе чувствительности особую значимость имеет выбор метрик: именно им оп-
ределяется сложность, разрешимость и „алгоритмизуемость“ возникающих в процессе иссле-
дования экстремальных задач. В рассматриваемом случае предлагается выбрать следующие
метрики:
r(Pˆ , P) = max
i=0, ..., 2n −1
pˆ i
−
pi
и d ( pˆ, p) = pˆ − p . Использование таких метрик, как бу-
дет видно в дальнейшем, приведет к решению задач линейного программирования (ЗЛП);
евклидова же метрика, например, потребовала бы решения задач с более сложным множест-
вом квадратичных ограничений.
Предлагаемый подход к решению задачи. Рассмотрим экстремальные задачи, кото-
рые позволяют вычислить характеристики чувствительности результата априорного вывода
p к допустимой вариации исходных данных. Вычислим величины
ε = sup {d ( pˆ , p)} и ε(P ) = sup {d ( pˆ , p)} ,
IPˆ ≥0,IP≥0,
IPˆ ≥0, IP≥0,
r(Pˆ ,P)≤δ
r(Pˆ ,P)≤δ, P=P
при этом величина ε(P ) необходима для исследования ситуации в случае с конкретным на-
бором исходных оценок P = P .
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2009. Т. 52, № 9
Оценка чувствительности результата локального априорного логико-вероятностного вывода 5
В первую очередь, сведем ограничения экстремальных задач к набору линейных ра-
венств и неравенств. Очевидно, что ограничения IPˆ ≥ 0 , IP ≥ 0 и P = P изначально линейны, их изменять
не требуется. Неравенство
r(Pˆ , P) ≤ δ
раскрывается как
max
i=0, ..., 2n −1
pˆi
−
pi
≤ δ , что эквива-
лентно
системе
линейных
неравенств
{−δ ≤
pˆi
−
pi
}≤ δ
i=2n i=0
−1
.
Таким
образом,
все
ограниче-
ния в рассмотренных экстремальных задачах линейные.
По определению целевая функция d ( pˆ, p) = pˆ − p . Чтобы свести экстремальную задачу
к двум ЗЛП, достаточно решить последние отдельно для разности pˆ − p и разности p − pˆ .
Таким образом, процесс оценивания характеристик чувствительности сводится к реше-
нию совокупности задач линейного программирования:
ε
=
{max pˆ
IPˆ ≥0,IP≥0,
−
p,
p
−
pˆ}
,
ε(P ) =
max
IPˆ ≥0, IP≥0,
{ pˆ − p, p − pˆ} .
r(Pˆ ,P)≤δ
r(Pˆ ,P)≤δ, P=P
Алгоритмы решения ЗЛП известны, хорошо изучены, а также реализованы в библиоте-
ках, рассчитанных на ряд систем программирования.
Верхняя оценка. Можно оценить характеристики чувствительности и не прибегая к
решению ЗЛП, пусть и несколько потеряв в точности оценки. В соответствии с полученной
оценкой можно предъявить обоснованные требования к точности измерения, определения
или расчета исходных данных.
Учитывая, что pˆ0 = p0 = 1 [2, 5], оценим
d ( pˆ, p) = pˆ − p = L ⋅ Pˆ − L ⋅ P = L ⋅ (Pˆ − P) =
2n −1
2n −1
2n −1
2n −1
= ∑ li ( pˆi − pi ) ≤ ∑ li ⋅ ( pˆi − pi ) ≤ ∑ li δ = δ ∑ li .
i=0
i=1 ≤δ i=1
i=1
Таким образом, установлена легко вычисляемая верхняя граница для оценки чувстви-
2n −1
тельности — ε ≤ δ ∑ li . Вопрос о том, точна ли эта верхняя граница, остается открытым. i=1
Некоторые результаты, представленные в данной статье, получены в рамках проекта, под-
держанного Российским фондом фундаментальных исследований (грант № 09-01-00861-а).
СПИСОК ЛИТЕРАТУРЫ
1. Крейнович В. Я., Нгуен Т. Х., Городецкий В. И. и др. Применение интервальных степеней доверия: аналитический обзор // Информационные технологии и интеллектуальные методы: Сб. трудов СПИИРАН. СПб.: СПИИРАН, 1999. Вып. 3. С. 6—61.
2. Тулупьев А. Л., Николенко С. И., Сироткин А. В. Байесовские сети: логико-вероятностный подход. СПб.: Наука, 2006. 607 с.
3. Нариньяни А. С. НЕ-факторы: неточность и недоопределенность — различие и взаимосвязь // Изв. РАН. Сер. Теория и системы управления. 2000. № 5. С. 44—56.
4. Хованов Н. В. Анализ и синтез показателей при информационном дефиците. СПб.: Изд-во С.-Петербург . ун-та, 1996. 196 с.
5. Тулупьев А. Л. Алгебраические байесовские сети: локальный логико-вероятностный вывод: Учеб. пособие. СПб.: СПбГУ — ООО Изд-во „Анатолия“, 2007. 80 с.
6. Тулупьев А. Л. Алгебраические байесовские сети: глобальный логико-вероятностный вывод в деревьях смежности: Учеб. пособие. СПб.: СПбГУ — ООО Изд-во „Анатолия“, 2007. 40 с.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2009. Т. 52, № 9
6 С. А. Алексеев
7. Тулупьев А. Л., Сироткин А. В., Николенко С. И. Синтез согласованных оценок истинности утверждений в интеллектуальных информационных системах // Изв. вузов. Приборостроение. 2006. Т. 49, № 7. С. 20—26.
8. Тулупьев А. Л., Николенко С. И., Никитин Д. А., Сироткин А. В. Синтез апостериорных оценок истинности суждений в интегрированных базах знаний: детерминированный вариант // Там же. 2006. Т. 49, № 11. С. 35—39.
Александр Львович Тулупьев
Сведения об авторе — канд. физ.-мат. наук, доцент; Санкт-Петербургский институт инфор-
матики и автоматизации РАН, лаборатория прикладной информатики; E-mail: alt@iias.spb.su
Рекомендована кафедрой технологий программирования СПбГУ ИТМО
Поступила в редакцию 15.02.08 г.
ИЗВ. ВУЗОВ. ПРИБОРОСТРОЕНИЕ. 2009. Т. 52, № 9