Доклады Российской академии наук. Математика, информатика, процессы управления, 2020, T. 493, № 1, стр. 90-94

ВВЕДЕНИЕ

В проблематику искусственного интеллекта (ИИ), управления и принятия решений при неполной или недостоверной информации входит широкий класс задач так называемого объяснения на основе моделей и методов абдуктивных рассуждений (Explanation by abductive reasoning), в том числе в терминах “причина–эффект”.

Понятие абдукции введено логиком и философом Ч.С. Пирсом (C.S.Peirce, 1839–1914) в форме логических рассуждений, сравнимых, но отличных от дедукции и индукции. Сегодня абдукция чаще всего определяется следующим образом: на основе заданной теории Т предметной области и утверждения G о наблюдаемом эффекте, подлежащем объяснению, найти такую, не противоречащую теории Т, гипотезу-объяснение Δ, что из Т и Δ выводимо G (модификации см., например, в [1–3]).

В работах по абдуктивному гипотезированию на теорию Т предметной области часто накладываются ограничения, при которых дедукция максимально упрощается, например, содержание теории должно иметь форму “if-and-only-if”, т.е. форму семейства эквивалентностей ${{c}_{i}} \leftrightarrow {{E}_{{i1}}} \vee $ ... $ \vee {{E}_{{in}}}$, где в пропозициональном случае ${{c}_{i}}$ – переменные-причины, а ${{E}_{{ij}}}$, $j = 1,\; \ldots ,\;n$, – элементарные конъюнкции (ЭК), составленные из переменных-эффектов и их отрицаний, возможно, при дополнительных требованиях к множеству задействованных переменных, частично упорядоченному импликацией [1, 2].

В данной работе не предполагается какой-либо предварительной трансформации теории Т, а в качестве языка представления знаний в разделе 1 вводится S-язык L_S как подмножество стандартного пропозиционального языка, но без ослабления его выразительной силы. Он шире пропозиционального варианта языка позитивно-образованных формул [4], допуская использование отрицательных литералов. Благодаря подстановочности формул языка L_S (см. раздел 1), они обладают свойствами, не все из которых справедливы для произвольных пропозициональных формул. Свойства языка L_S и вводимых в нем исчислений ${{\mathbb{C}}_{\alpha }}$, ${{\mathbb{C}}_{\beta }}$ обеспечивают удобное сочетание дедукции с гипотезированием.

Вывод в ${{\mathbb{C}}_{\beta }}$ наблюдаемого эффекта $G$ выполняется вместе с синтезом формулы $P$, называемой гипотезой-минорантой и объясняющей эффект $G$ лишь формально. С точностью до эквивалентности гипотеза $P$ логически минимальна (любая гипотеза-причина Δ, объясняющая $G$, должна быть не слабее $P$: $\Delta \to P$). Гипотеза-миноранта выступает контрольным условием и опорным средством формирования достоверных гипотез Δ, а в случае наличия сверхтеории $T$ также эмпирических знаний, то и правдоподобных гипотез Δ. Эмпирические знания – это знания об априорном множестве потенциально возможных причин-кандидатов и/или о правдоподобных причинно-следственных связях. Из гипотезы P переходом к достаточным условиям, например, путем упрощения или использования эмпирических знаний, получаются либо причины Δ эффекта G (достоверные или правдоподобные), либо поначалу лишь релевантные обстоятельства (факты, события, “улики”), из которых в рамках теории Т средствами исчислений ${{\mathbb{C}}_{\alpha }}$ и ${{\mathbb{C}}_{\beta }}$ оказываются выводимыми и сами причины.

Заметим, что в проблематике интеллектуализации автономных (беспилотных) агентов с реактивными правилами “условие–действие” понятие “эффект” может иметь также смысл целевого состояния агента [5]. Эта тема абдуктивной информационной поддержки планирования действий агентов с распространением полученных в данной работе результатов на первопорядковые логики – актуальная задача на будущее, в части представления знаний, решаемая, как видится, с сохранением в языке свойства подстановочности позитивно-образованных формул [4, 6] и требований позитивности.

В разделе 1 вводится язык представления знаний, в разделе 2 – правила преобразования его формул. В разделе 3 вводятся исчисления ${{\mathbb{C}}_{\alpha }}$, ${{\mathbb{C}}_{\beta }}$ и рассматриваются их свойства, а в разделе 4 применение этих исчислений иллюстрируется примерами из техники и медицины.

1. ПРЕДСТАВЛЕНИЕ ЗНАНИЙ

В пропозициональном языке L стандартной (классической) семантики выделим подмножество ${{L}_{S}}$. Ввиду свойства подстановочности его формул, определяемой ниже, будем называть его S-языком (от английского Substitutability). Далее конъюнктами называем ЭК литералов (пропозициональных переменных и/или их отрицаний) и пропозициональные константы false, true (ЭК – это конъюнкции литералов; т.е. если в ЭК входит пара контрарных литералов (переменная и ее отрицание), то по умолчанию такие ЭК заменяются на константу false. Логические связки $ \vee $, $ \wedge $, $\neg $, $ \to $ в S-языке понимаются стандартно.

Определение 1 (формулы языка ${{L}_{S}}$ и их типы).

1) ЭК $A$ или константа false, – S-формулы; им приписывается тип ∧; это простейшие S‑формулы;

2) если ${{F}_{i}}$, $i = 1,\; \ldots ,\;m$, – S-формулы типа ∧, а G – ЭК или true, то $G \to \left( {\mathop \vee \limits_{i = 1}^m {{F}_{i}}} \right)$ – S-формулы типа →;

3) если ${{F}_{i}}$, $i = 1,\; \ldots ,\;m$, – S-формулы типа →, а G – ЭК или true, то $G \wedge \left( {\mathop \wedge \limits_{i = 1}^m {{F}_{i}}} \right)$ – S-формулы типа ∧;

4) других формул в языке ${{L}_{S}}$ нет.

Семантика S-формул очевидна. Их возможные упрощения в случае появления ${{F}_{i}} = false$ (кроме случаев, когда $m = 1$ в формуле типа $ \to $) также очевидны и такие упрощения будут подразумеваться. Формулы языка L вне ${{L}_{S}}$ понимаем стандартно. Например, если ${{F}_{1}},\;{{F}_{2}} \in {{L}_{S}}$, то выражение ${{F}_{1}} \to {{F}_{2}}$, вообще говоря, не принадлежащее ${{L}_{S}}$, понимается как в $L$.

Подформулы S-формулы $F$, образуемые в соответствии с индуктивным определением S-формул, называются главными подформулами (ГП). Выражение ${{F}_{1}} \subseteq F$ означает, что ${{F}_{1}}$ – ГП S-формулы $F$. Каждая вершина древовидной структуры S-формулы имеет тип, соответствующий типу ГП, корнем которой эта вершина является. Типы ∧, → вершин вдоль ветви структуры S-формулы $F$ чередуются.

Для S-формул $F$, ${{F}_{1}}$, ${{F}_{2}}$ справедливо свойство подстановочности: если ${{F}_{1}} \subseteq F$ и ${{F}_{2}} \to {{F}_{1}}$, то $F({{F}_{2}}{\text{/}}{{F}_{1}}) \to F$, где $F({{F}_{2}}{\text{/}}{{F}_{1}})$ – результат подстановки в $F$ вместо ${{F}_{1}}$ не менее сильной формулы ${{F}_{2}}$. Язык ${{L}_{S}}$ полон относительно выразительной силы языка $L$.

2. ПРЕОБРАЗОВАНИЯ S-ФОРМУЛ

Каноническим представлением S‑формулы F называем ее запись в виде формулы с конъюнктом $true$ в корневой вершине ее структуры:

где $m \geqslant 1$, ${{n}_{i}} \geqslant 0$ (если ${{n}_{i}} = 0$, то ${{\Omega }_{i}} = {{A}_{i}}$). Конъюнкт ${{A}_{i}}$ называется  базой,  а конъюнкты ${{B}_{{ij}}}$ (когда ${{n}_{i}} \ne 0$) – вопросами к базе ${{A}_{i}}$. Если ${{B}_{{ij}}} \subseteq {{A}_{i}}$, то называем вопрос ${{B}_{{ij}}}$ к базе ${{A}_{i}}$ уместным. Тождественно ложную S-формулу true → → $false$ далее для краткости обозначаем ⊥.

Пусть в (1) $F \ne \bot $, ${{n}_{i}} \ne 0$ и ${{\Phi }_{{ij}}}$ имеют вид

где ${{l}_{{ij}}} \ne 0$, иначе ${{\Phi }_{{ij}}} = false$. Предположим, что т.е. вопрос ${{B}_{{i*j*}}}$ к базе ${{A}_{{i*}}}$ уместен.

Определение 2 (α-преобразование). Если S-формула F имеет вид (1)–(3), то α-преобразованием называется такое отображение $\alpha {\text{:}}{{L}_{S}} \to {{L}_{S}}$, что

если ${{\Phi }_{{i*j*}}} \ne false$, иначе при $m > 1$ ГП $\Omega _{{i*j*k}}^{ * }$ удаляются, а при $m = 1$  $\alpha (F) = \, \bot $.

Здесь и далее, когда это не вызывает коллизий, конъюнкты рассматриваются как множества входящих в эти конъюнкты элементов. В случае появления в конъюнкте $\{ {{A}_{{i*}}} \cup {{С}_{{i*j*k}}}\} $ из (4) контрарных литералов, формула $\alpha (F)$ упрощается заменой на ⊥ при $m = {{l}_{{1j*}}} = 1$, иначе удалением $\Omega _{{i*j*k}}^{ * }$. Удаляются и дубли ГП при совпадении $\Omega _{{i*}}^{ * }$ с Ω_i, $i \ne i{\text{*}}$.

Пусть $\alpha (F) \ne \bot $ и выполняется условие типа (3). Применяя α-преобразование к $\alpha (F)$, получим S-формулу ${{\alpha }^{2}}(F)$ и т.д. до тех пор, пока очередной результат еще отличен от ⊥ и выполняется (3). Пусть на некотором шаге ${{r}_{1}}$ (${{r}_{1}} \geqslant 0$) ${{\alpha }^{{{{r}_{1}}}}}(F) \ne \bot $, но α-преобразование уже не применимо ввиду невыполнения (3), т.е. $\forall i \in 1, \ldots ,{{m}^{1}}$, где m¹ – количество баз в ${{\alpha }^{{{{r}_{1}}}}}(F)$, база A_i будет:

1) либо висячей (${{n}_{i}} = 0$) и, ввиду упомянутых упрощений, отличной от false, либо

2) невисячей (${{n}_{i}} \geqslant 1$) и такой, что $\forall j \in 1, \ldots ,{{n}_{i}}$ вопросы ${{B}_{{ij}}}$ к базе A_i неуместны (под выражениями ${{A}_{i}}$, ${{B}_{{ij}}}$ понимаются новые конъюнкты в формуле ${{\alpha }^{{{{r}_{1}}}}}(F)$).

Определение 3 (β-преобразование). Пусть ${{I}_{1}}$, ${{I}_{2}}$ – множества индексов $i \in 1, \ldots ,{{m}^{1}}$, для которых базы ${{A}_{i}}$ удовлетворяют условиям 1) и 2) соответственно, и

где

Назовем β-преобразованием такое отображение $\beta $: ${{L}_{S}} \to {{L}_{S}}$, что

Формирование условия

называем далее (α,β)-гипотезированием.

3. S-ИСЧИСЛЕНИЯ И ИХ СВОЙСТВА

На основе α- и β-преобразований формул языка ${{L}_{S}}$ введем два исчисления.

Пусть ${{F}^{1}} = \beta ({{\alpha }^{{{{r}_{1}}}}}(F))$. Применим к ${{F}^{1}}$ α-преобразование максимально возможное число раз ${{r}_{2}}$ (${{r}_{2}} \geqslant 1$). Если ${{\alpha }^{{{{r}_{2}}}}}({{F}^{1}}) \ne \bot $, то применим β-преобразование, получив ${{F}^{2}} = \beta ({{\alpha }^{{{{r}_{2}}}}}({{F}^{1}}))$ и т.д. Пусть F ⁿ = = $\beta ({{\alpha }^{{{{r}_{n}}}}}({{F}^{{n - 1}}}))$ и впервые ${{\alpha }^{{{{r}_{{n + 1}}}}}}({{F}^{n}}) = \, \bot $. В результате n-кратного (α, β)-гипотезирования получили условие

именуемое гипотезой-минорантой (ГМ).

Определение 4 (S-исчисления ${{\mathbb{C}}_{\alpha }}$, ${{\mathbb{C}}_{\beta }}$). S-исчисления ${{\mathbb{C}}_{\alpha }} = ( \bot ,\{ \alpha \} )$ и ${{\mathbb{C}}_{\beta }} = ( \bot $, {α, β}) – это исчисления в языке ${{L}_{S}}$ c аксиомой ⊥ и указанными преобразованиями в качестве правил вывода. Здесь выводы формулы F – это конечные последовательности формул, начинающиеся с F, заканчивающиеся формулой ⊥ и с промежуточными формулами, получаемыми в ${{\mathbb{C}}_{\alpha }}$ с помощью только α-преобразований, а в ${{\mathbb{C}}_{\beta }}$ – с помощью преобразований α и β, как в построенной ранее для формулы $F$ последовательности: F⁰, ${{F}^{1}},{{F}^{2}}, \ldots ,{{F}^{{n + 1}}}$, где ${{F}^{0}} = F$. Вывод S-формулы F суть ее опровержение.

Теорема 1. Формула F ⁰языка ${{L}_{S}}$ противоречива тогда и только тогда, когда F ⁰выводима в ${{\mathbb{C}}_{\alpha }}$.

Пусть $\{ T,G,\Delta \} \subset {{L}_{S}}$, $T$ – теория предметной области (контент некоторой базы знаний), $G$ – наблюдаемый эффект. Объяснением наблюдаемого признается гипотеза Δ, удовлетворяющая требованиям:

а) из $T \wedge \Delta $ в исчислении ${{\mathbb{C}}_{\beta }}$ выводимо $G$ и

б) $T \wedge \Delta $ – непротиворечиво.

С использованием теоремы 1 доказуема следующая

Теорема 2. Пусть ${{F}^{0}} = {{(T \wedge \neg G)}^{{{{L}_{S}}}}}$ – образ отрицания формулы $(T \to G)$ в языке ${{L}_{S}}$. Пусть также $P \in {{L}_{S}}$ и $P$ построено (α, β)-гипотезированиями в процессе вывода формулы F ⁰в исчислении ${{\mathbb{C}}_{\beta }}$. Тогда $P \leftrightarrow (T \to G)$ и для любой гипотезы Δ, объясняющей $G$, cправедливо $\Delta \to P$.

В разделе 4 демонстрируется переход от гипотез-минорант $P$ к достаточным условиям путем удаления элементов, несовместимых с теорией $T$ (примеры 1 и 2), или путем привлечения эмпирических знаний (пример 2). При этом получаются либо сами причины Δ эффекта $G$ (достоверные или правдоподобные), либо релевантные обстоятельства (пример 1), из которых в рамках теории $T$ средствами исчислений ${{\mathbb{C}}_{\alpha }}$ или ${{\mathbb{C}}_{\beta }}$ оказываются выводимыми и сами причины.

4. ПРИМЕРЫ ПРИМЕНЕНИЯ ИСЧИСЛЕНИЙ

Пример 1. Рассмотрим простой пример из области диагностики автомобиля (знания рассматриваемого ниже типа сформулированы в [1] в первом приближении для иллюстрации концепции экспертных систем в ИИ).

1) Пусть некоторые пропозициональные переменные языка ${{L}_{S}}$ имеют следующий смысл: Ф – Фары горят; Б – в Баке топливо есть; К – топливо поступает в Карбюратор; Д – топливо поступает в Двигатель; В – двигатель Вращается; И – автомобиль Исправен; З, А, С – проблемы, соответственно, в свечах Зажигания, в Аккумуляторе и в Стартере.

2) Пусть на фоне неисправности автомобиля выявлены следующие факты: Фары горят, двигатель вращается и топливо поступает в карбюратор.

3) Предположим, что, помимо этих фактов, базовая теория T включает знания: Если топливо поступает в двигатель и двигатель вращается, то проблема в свечах зажигания. Если в баке топливо есть и топливо поступает в карбюратор, то топливо поступает в двигатель. Если двигатель не вращается, то при горящих фарах проблема в стартере, при негорящих – в аккумуляторе. Если автомобиль исправен, то проблем в свечах зажигания, стартере и аккумуляторе нет.

Базовая теория $T$ представима следующей S‑формулой вида

Наблюдаемое G состоит в неисправности автомобиля: $G = \neg И$, а вывод объяснения в S-исчислении ${{\mathbb{C}}_{\beta }}$ начинается с формулы ${{F}^{0}} = {{(T \wedge \neg G)}^{{{{L}_{S}}}}}$. Ее база $\{ Ф,В,Б,И\} $ при получении F ¹ (однократным применением α-преобразования к F ⁰) дополняется элементами множества $\{ \neg З,\;\neg С,\;\neg А\} $.

Применением β-преобразования получается гипотеза-миноранта

После представления ее в форме элементарной дизъюнкции и удаления из нее членов, $\neg Ф$, $\neg В$, $\neg Б$, $\neg И$, контрарных элементам базы из F¹, а также тривиального члена $З \vee С \vee А$ получается объяснение $Д \vee К$ в классе релевантных обстоятельств. Действительно, далее в рамках исчисления ${{\mathbb{C}}_{\alpha }}$ промежуточным элементом вывода формулы ${{(T \wedge \neg G \wedge (Д \vee К))}^{{{{L}_{S}}}}}$, включившей полученное обстоятельство, оказывается факт $З$ как причина неисправности.

Пример 2. Рассмотрим другой иллюстративный пример из области медицины [1], для краткости не приводя детальной семантики переменных (cтатья [1] посвящена представлению знаний в диагностике с достоверными и эмпирическими знаниями).

Пусть $e$, $h$ – симптомы заболевания. Известны болезни $t$, $d$, $a$. Пусть $\{ t \to e,\;a \to h\} $ – множество достоверных причинно-следственных связей базовой теории $T$ в терминах симптомов $e$, $h$ и болезней $t$, $a$. Пусть $\{ d \to h,\;a \to e\} $ – правдоподобные (недостоверные) причинно-следственные связи (ППСС) (эмпирические данные “прошлого опыта”). Пример интересен, в частности, и тем, что словарь базовой теории $T$ не охватывает словаря эмпирических ППСС (нет болезни $d$). Тем не менее, из гипотезы-миноранты, выводимой средствами (α, β)-гипотезирования, получаются все логически возможные в рассматриваемом контексте диагнозы.

Если наблюдается симптом $G = e$, то

В исчислении ${{\mathbb{C}}_{\beta }}$ при выводе F ⁰ формируется гипотеза-миноранта

При этом ${{r}_{1}} = 0$, ${{r}_{2}} = 3$, ${{r}_{3}} = 2$ и ${{\alpha }^{{{{r}_{3}}}}}({{F}^{2}}) = \, \bot $. Все элементарные дизъюнкции конъюнктивной нормальной формы (КНФ) $(e \vee t \vee a) \wedge (e \vee t \vee \neg a \vee \neg h)$ гипотезы-миноранты P следуют из причины $t$. По теореме 2 причина $t$ объясняет симптом $e$.

Это объяснение не использует ППСС. С учетом же последних и того, что оба члена КНФ следуют из $a$ и $a \to e$ соответственно, выводится еще одно (теперь только правдоподобное) объяснение: “причина – в болезни $a$, если верна ППСС $a \to e$”.

Пусть теперь наблюдаются одновременно два симптома: $G = e \wedge h$. Выявление причин использует вывод формулы

При этом формируется гипотеза-миноранта

и на ее основе три следующих объяснения. Два из них:

1) “комплекс из двух причин $\{ t,a\} $” как достоверное объяснение,

2) “если верна ППСС $a \to e$, то причина в $a$” (правдоподобное объяснение).

Третье объяснение получается из (5) использованием второй ППСС после расширения сигнатуры (5) переменной $d$ путем замены каждой элементарной дизъюнкции на две других, получающихся добавлением в одну – переменной $d$, а во вторую – литералы $\neg d$. Каждая из элементарных дизъюнкций расширенной КНФ будет следовать из причин $d$, $t$ и ППСС $d \to h$, что и явится третьим объяснением наблюдаемого комплекса симптомов $G = e \wedge h$.