НАУКА и ОБРАЗОВАНИЕ

Г. Н. Зверев, д-р техн. наук, Уфимский государственный технический университет

Логические аппроксимации, лапласовы оценки и корреляционная логика

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

Современные информационные технологии и их программно-аппаратные средства основаны на формализме классической логики с двоичной шкалой различимости {да, нет} и истинности {истина, ложь} → {1, 0}. Однако реальные информационные процессы оперируют искаженными, неполными, противоречивыми фактическими и априорными данными, которым вряд ли возможно приписать однозначную оценку 0 или 1 двоичной шкалы. В таких ситуациях более адекватным описанием является формализм частотной логики [1—3], в котором двоичная истинность заменяется частотной истинностью, а логические связи двоичных признаков, свойств и предикатов представлены различными частотными связями. Последние в пределе могут сколь угодно приближаться к строгим логическим оценкам и зависимостям.

Переход от предельных, недостижимых оценок истинности в двоичной шкале {1, 0} к числовым оценкам истинности в открытом интервале (0, 1) позволяет построить логические аппроксимации, которые учитывают искажения и неопределенности фактов и априорики. Целью данной статьи является построение оценок истинности логических методов и погрешностей истинности в корреляционном приближении.

Частотная истинность произвольного высказывания а (аргумента, предиката, логической функции) определяется как частость (доля, шанс, вероятность) значения а = 1 в конечном множестве информационных ситуаций:  (где N_a — численность единичных значений, N — численность универсума ситуаций), а редкость значения a = 1 определяет частотную меру ложности

 или частость значения a = 0.

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

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

Корреляционные методы, широко распространенные при решении задач с непрерывными количественными переменными, предполагают знание первых двух моментов распределения векторных величин. Для дискретно-логических задач также полагаем известными только первый  либо второй  моменты распределения вектора двоичных признаков z = (z₁, z₂,…, z_n)^T, где N — число ситуаций (или объектов) предметной области; n — число двоичных признаков объектов, известных, искомых, вычисляемых; Т — знак транспонирования.

Первый момент M(z) есть вектор размерности n, компоненты которого определяют "объемы" q_j признаков z_i = 1 переменных z_i, принимающих в одной из N ситуаций значение 0 или 1: . Величина q_i - есть частость единичного значения z_i, мера истинности высказывания "объект предметики обладает свойством .

Второй момент M(zz^T) есть симметричная квадратная матрица порядка n, в диагонали которой стоит первый момент, так как 0² = 0, 1² = 1, а недиагональные элементы выражают объемы парных пересечений  мера истинности высказывания “объект обладает свойствами z_i и z_j”, q_ij = q_ji.

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

Обозначим входные признаки двоичной логической операции f через z_i и z_j объемами q_i, q_j и пересечением q_ij, а новый составной признак z = f(z_i, z_j) будет иметь объем q_z и пересечения q_iz, q_ij. Здесь f — одна из шестнадцати возможных бинарных логических операций, из них девять функций выражают особенности остальных: , — отрицание; z_i + z_j — сложение (дизъюнкция); z_i,z_j — умножение (конъюнкция); z_i → z_j — импликация; z_i - z_j— вычитание; z_i  z_j — эквиваленция; z_i  z_j — сложение по модулю 2 (антиэквиваленция); z_i |z_j — И-НЕ (штрих Шеффера); z_i ↓ z_j - ИЛИ-НЕ (стрелка Пирса). Признак, отличный от z_i,z_j обозначим z_k, его объем q_k и парные пересечения q_ik, q_jk, q_kz тройное пересечение — третий момент q_ijk. Выражения частотной истинности составных признаков представлены в таблице.

В первой колонке добавлены полиномиальные (дизъюнктивные) формы логических операций. Используя эти формулы, можно последовательно наращивать логические структуры и получать моменты все более сложных составных признаков. Однако в последнем столбце присутствует неизвестный объем тройного пересечения q_ijk признаков z_i, z_j, z_k, который выводит оценки истинности из корреляционной теории. Чтобы остаться в рамках корреляционного приближения и избежать вычисления многомерных матриц и интегралов, необходимо найти оценки третьего момента по первым двум и выразить достигаемую точность приближения. В этом и заключается суть корреляционной логики при построении оценок истинности в частотной шкале, их погрешностей и последующем применении их в дискретно-логических задачах принятия оптимальных решений.

Если удастся достаточно точно оценить третий момент по двум первым, то алгоритмы поиска оптимальной или субоптимальной аппроксимации существенно упрощаются, так как не требуется вычислять многомерные интегралы и матрицы моментов, перемножать логические полиномы и их отрицания, а достаточно последовательно наращивать матрицу вторых моментов M(zz^T) составными аппроксимирующими признаками и информативными импликатами и коррелятами.

Найдем граничные значения неизвестного тройного пересечения — момента третьего порядка q = q_ijk = M(z_i • z_j • z_k) исходя из априорного значения моментов первого и второго порядка: q_i, q_j, q_k, q_ij, q_ik, q_jk и пусть для определенности q_i, ≤ q_j, ≤ q_k. Параметры априорики должны быть согласованы между собой и удовлетворять естественным ограничениям:

0 ≤ q_i,…,q_k ≤ 1, b_ij ≤ q_ij ≤ q_i, b_ik ≤ q_ik ≤ q_i, b_jk ≤ q_jk ≤ q_j.

где b_ij = max(0, q_i + q_j - 1), b_ik = max(0, q_i + q_k - 1), b_jk = max(0, q_j + q_k — 1) — параметры зазоров между универсумом ситуаций и суммой объемов двух признаков.

Для вывода этих выражений воспользуемся одномерной диаграммой Эйлера с интервалами — признаками в единичном универсуме и разместим объекты универсума, обладающие признаком z_k = 1, в начале универсума [0, 1], а затем объекты со свойством z_j = 1, тогда минимально возможное значение второго момента q_jk при известных q_j и q_k определяется предельным правым положением интервала Эйлера признака z_j (рис. 1, показано штрихом) и равно либо 0 для малых признаков при q_k ≤ 1 - q_j, либо q_j + q_k - 1 для больших признаков при q_k > 1 - q_j.

Отсюда следует ограничение значений второго момента по известным первым моментам: q_jk, ≤ q_jk ≤ q_j и в качестве оценки q_jk берется середина интервала неопределенности  с предельной ошибкой этой оценки .

Такого типа оценки частостей являются наилучшими по точности, если вариации неизвестных априорных данных симметричны в допустимом интервале, и называются лапласовыми оценками при равномерном распределении частостей q_jk, .... Если ошибка  меньше допустимой, то более точный расчет второго момента q_jk становится излишним.

Рис. 1

Граничные значения неизвестного третьего момента q = q_ijk в одномоментном приближении отыскиваются по той же схеме. Прежде найдем оценки верхнего и нижнего пределов объема тройного пересечения q_min, ≤ q ≤ q_max из априорного знания только первых моментов. Добавим в одномерной диаграмме Эйлера наименьший признак z_i, его необходимо представить в общем случае двумя несвязными интервалами суммарной длиной q_i. Верхняя граница q_max определяется объемом минимального признака при вложенности трех признаков, а нижняя граница — таким размещением в универсуме объектов со свойством z_i = 1, которое по возможности не образует тройного пересечения в интервалах [0,1 - q_j] и [q_k, 1]. Отсюда при q_i > 1 - q_j + 1 - q_k обязательно возникнет тройное пересечение q > 0, следовательно, первые моменты ограничивают искомую величину q снизу, если признаки большие, при S₁ = q_i + q_j + q_k > 2, значит, q_min = max(0, S₁ - 2), q_max = q_i лапласова оценка третьего момента  с ошибкой .

Рис. 2

Для определения границ q в корреляционном, двухмоментном приближении по известным первым и вторым моментам трех признаков представим на двумерной диаграмме Эйлера (рис. 2) случай общего положения, при котором признаки разбивают универсум на максимальное число 2³ = 8 классов объектов, различимых по этим свойствам и занумеруем эти классы в соответствии с двоичным представлением числа z_j z_j z_k от 0 = 000 до 7 = 111. Объемы элементарных классов выражаются через трехмоментную априори ку так:

q₀ = 1 – S₁ + S₂ – q;                             q₁ = q_k – q_ik – q_jk + q;

q₃ = q_jk – q;                                          q₂ = q_j – q_ij – q_jk + q;

q₅ = q_ik – q;                                          q₄ = q_i – q_ij – q_ik + q;

q₆ = q_ij – q;                                          q₇ = q,

где суммы первых и вторых моментов есть S₁ = q_i + q_j + q_k, S₂ = q_ij + q_ik + q_jk. В эти формулы входит неизвестная величина q слева со знаком минус, справа — со знаком плюс. Объемы классов q₀, q₁,..., q₇ не могут быть отрицательными, поэтому из левой группы получаем четыре ограничения величины тройного пересечения снизу, а из правой группы — ограничения сверху, и из них выбираем наиболее сильные ограничения: q_min = max(0, b_i, b_j, b_k), где зазоры q_max = min(q_ij, q_ik, q_jk, S₀), сумма . В этих формулах не предполагается упорядоченность признаков z_i, z_j, z_k по их объемам.

Легко проверить, что одномоментные ограничения q снизу и сверху в двухмоментном приближении становятся излишними, но все величины, входящие в q_min и q_max, являются значимыми и определяют лапласову оценку третьего момента и его максимальной ошибки

Найдем условия, при которых интервал [q_min, q_max] неопределенности q_ijk стягивается в точку. Во-первых, это случай отрицательной логической связи хотя бы одной пары признаков, например r_ij=-1, тогда q_ij = 0, b_i ≤ 0, q_min = q_max = q_ijk = 0. Во-вторых, при сильной положительной связи любой пары признаков, скажем, r_ij → 1, интервал неопределенности также стягивается в точку. В самом деле, при вложении меньшего признака в больший два элементарных класса из восьми исчезают, например, при вложении z_i → z_j сразу следует q₄ = q₅ = 0, отсюда q_jk = q_ik. Следовательно, сильные положительные и отрицательные корреляционные связи могут, не уменьшая третьи моменты, резко повышать точность логических аппроксимаций в корреляционном приближении.

Итак, если хотя бы один из коэффициентов корреляции r_ij, r_ik, r_jk по модулю равен единице, то третий момент вычисляется точно: q_ijk = q_min = q_max. Максимальная погрешность корреляционной логики проявляется в ситуациях с попарной независимостью признаков r_ij = r_ik = r_jk = 0. При полной независимости признаков справедлива точная оценка  которая служит простейшей аппроксимацией третьего момента. Были предложены и другие аппроксимации, например, в [1]. В двухмоментном приближении простой вид имеет формула , которая в случае попарной независимости совпадает с предыдущим выражением, основанным на гипотезе полной независимости признаков. Точность этих приближений зависит от размеров признаков и уровня тернарной и парных связей между ними.

Найдем предельные ошибки оценок тройного пересечения признаков в наиболее неблагоприятном случае попарной независимости признаков: r_ij = r_ik = r_jk = 0; полагая упорядоченность их объемов q_i ≤ q_j ≤ q_k. Учитывая соотношения некоррелированности q_ij = q_iq_j, q_ik =q_iq_k, q_ik = q_jq_k легко найти минимальное значение третьего момента q_min = max(0, b_j); максимальное значение q_ijk находится по минимуму q_ij и S₀. Найдем разность этих величин:

q_ij – S₀ = q_ij – 1 + q_i +q_j + q_k – q_ij – q_ik – q_jk = (1 - q_k) (q_i = q_j - 1),

значит, q_min = q_iq_j для малых признаков (q_i + q_j < 1) и q_min = S₀ для больших признаков. В результате получаем три интервала неопределенности тройного пересечения попарно независимых признаков, определяемые по точно заданным моментам первого и второго порядка:

0 ≤ q_ijk ≤q_ij                   при                  q_j + q_k ≤ 1;

b_i ≤ q_ijk ≤ q_ij                 при                  q_i + q_j ≤ 1≤ q_j +q_k;

q_i ≤ q_ijk ≤S₀                  при                  q_i + q_j >1.

В итоге получаем оценки сверху точности двухмоментного приближения, q_i ≤ q_j ≤ q_k.

которые определяют границы применимости чистой корреляционной логики без привлечения иных оценок высших моментов. В ситуациях с недопустимо высоким уровнем погрешности  момент q_ijk должен оцениваться внелогическими методами. Следует заметить, что погрешность приближения не зависит от способа кодировки номинативных признаков, и переход от признаков к их отрицаниям, скажем, от больших позитивных к малым негативным, не изменяет точность аппроксимации, в то время как коэффициент корреляции признаков может сильно измениться при переходе к другой арифметизации номинативных признаков. Это обусловлено характером зависимости q_ijk от априорики J, определяющей фактически семь независимых уравнений от восьми неизвестных объемов элементарных классов.

С ростом числа признаков экспоненциально увеличивается сложность дискретно-логических задач, но одновременно экспоненциально возрастает и частотная зависимость между признаками и уменьшение их совокупной информативности, что увеличивает возможности логических аппроксимаций. Мера зависимости определяется гиперкорреляцией и частотной связностью.

Гиперковариацию трех признаков определим так же, как парную ковариацию: если признаки независимы, то q_ijk = q_iq_jq_k, поэтому тернарная ковариация K_ijk = q_ijk - q_iq_jq_k. Минимальное значение она приобретает при нулевом третьем моменте (q_ijk = 0), тогда K_ijk = - q_iq_jq_k, для этого достаточно (но не необходимо), чтобы одна из трех парных связей стала предельной отрицательной, скажем, r_ij = -1. Максимального значения тройная ковариация достигает при вложении меньшего признака z_i в пересечение z_jz_k оставшихся больших z_i ≤ z_jz_k, тогда q_ijk = q_i = q_ij = q_ik ≤ q_jk, и наибольшая гиперковариация есть maxK_ijk = q_ijk – q_iq_jq_k = q_i(1 - q_jq_k). Следовательно, множественный коэффициент корреляции трех битовых признаков — гиперкорреляция, удовлетворяющая условию нормировки -1 ≤ r_ijk ≤1, определяется формулой

где q_i ≤ q_j ≤ q_k. Эта формула легко переносится на произвольное число признаков и моменты высших порядков; в частности, при q_k = 1 она воспроизводит парную корреляцию r_ij.

Введенная гиперкорреляция, как и в случае парных связей, обладает тем недостатком, что не всегда отражает близость к предельной логической зависимости признаков, например, мера r_ijk = 0 — признаки некоррелированы, но существует логическая связь — импликация z_iz_j → z_k, когда пересечение двух признаков целиком лежит в третьем признаке. Логическая связь между двоичными признаками или их отрицаниями возникает в случае, если хотя бы один из моментов  произведения признаков равен нулю, т. е. признаки не пересекаются и удовлетворяют уравнению , здесь . Аналогом корреляционного отношения для качественных признаков является их максимальная частотная связность , которая при  принимает значения предельной (логической) связности s_m = 1. Максимальная связность трех признаков лежит в интервале , а в общем случае k признаков предельный уровень момента , отсюда 1 – 2^-k ≤ s_m ≤ 1, т. е. с ростом числа признаков экспоненциально уменьшается добавочная полезная информация.

Рассмотрим пример использования аппарата корреляционной логики для оценки достоверности логического вывода по схеме отделения модус поненс: a, a → b|- b — "если истинны высказывания "а" и "из а следует b", то высказывание "b" также истинно". В реальности факт а и правило a → b не бывают абсолютно истинными, поэтому интересно оценить ошибки  заключения b по известным ожидаемым искажениям факта и правила. Пусть задан информационный процесс выявления ВИЧ инфицированных b = 1 пациентов по результатам анализа крови a — по наличию антител в крови пациента a = 1. Ошибки посылки a связаны с лабораторными погрешностями v, влияющими на результат анализа:  — при отсутствии ошибки лабораторного анализа (v = 0) оценка , а при ее наличии (v = 1) оценка . Ошибки идеального логического правила a → b по формулам частотной логики (см. таблицу) равны ошибке импликации  в ситуациях a = 1, b = 1. В реальной импликации а заменяется на оценку: . Истинность этого логического полинома по формулам частотной логики равна , остальные произведения признаков равны нулю.

Ошибка логического вывода .

В корреляционном приближении последнее слагаемое неизвестно и оценивается по объемам признаков и их парных пересечений. Например, a = 0,55, b = 0,5, ab = 0,45, v = 0,06, av = 0,04, bv = 0,03, тогда оценка тройного пересечения по формулам корреляционной логики лежит в интервале 0,01 ≤ abv ≤ 0,03, т. е. q_ijk = 0,02 + 0,01. Ошибка чистой позитивной импликации a → b — "если в крови есть антитела, то пациент поражен СПИДом" равна  = a - ab= 10%, оценка ошибки реальной импликации в корреляционном приближении , т. е. ошибки наблюдений v частично скомпенсируют ошибку чистой импликации, а ошибка обратной импликации b → a, равной чистой негативной импликации  — "если в крови нет антител, то пациент не поражен СПИДом", равна b — ab = 5%.

Список литературы

1. Зверев Г. Н. Оценка надежности и оптимизация качественной интерпретации // Техника и технология геофизических исследований скважин. Уфа: Изд. БашНИПИнефть, 1979. С. 145-155.

2. Зверев Г. Н. Основания теоретической информатики. Разд. 1—7 Уфа: УГАТУ, 1997. 97 с.

3. Зверев Г. Н. Точные и аппроксимационные логики в машинных рассуждениях // Тр. V нац. конференции по искусственному интеллекту. Т. 1. Казань. 1996. С. 62—66.

ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ, № 2, 1999

ИНТЕЛЛЕКТУАЛЬНЫЕ СИСТЕМЫ

Ключевые слова: Дискретная логика, частотная логика, методы корреляции, частотная связность признаков, корреляция моментов высших порядков.