ML: Нечёткая логика


Введение

Иногда о некотором утверждении всё известно, однако его нельзя отнести к абсолютно истинному или ложному. Обычно это оценочные, сравнительные суждения: "Маша красивая", "Кофе горячий и крепкий". Действительно: "Маша, конечно, красивая" (но всё же не Анджелина Джоли); "кофе - горячий" (но пить уже можно). Оценочный характер имеют также оппозиционные нечёткие квантификаторы:

далеко-близко, давно-недавно, много-мало, большой-маленький
и размытые порядковые шкалы:
никогда, очень редко, редко, не часто, часто, очень часто, почти всегда, всегда.

Одним из инструментов для работы с подобными утверждениями являются нечёткая логика и теория нечётких множеств.

Логические связки

Будем считать, что любое высказывание $A$ характеризуется его степенью истинности $T_A$. Это вещественное число из диапазона $[0...1]$. Значение $T_A=0$ соответствует абсолютно ложному высказыванию, а $T_A =1$ - истинному. При, например, $T_A=0.7$ - высказывание скорее истинно, чем ложно.

Степень истинности логического отрицания "НЕ $A$" естественно определить следующим образом:

$$ \neg A:~~1-T_A. $$

Для логических И, ИЛИ чаще всего берутся минимум и максимум степеней истинности высказываний: $$ A\,\&\,B:~~~\min(T_A,T_B),~~~~~~~~~~~~~A\vee B:~~~\max(T_A,T_B). $$ Несложно видеть, что все эти операции для крайних значений воспроизводят таблицы истинности булевой логики: $$ \begin{array}{ccссc} A & B & A \,\&\, B & A\vee B\\ \hline 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 1 \\ 1 & 0 & 0 & 1 \\ 1 & 1 & 1 & 1 \\ \end{array} $$

Таким образом определённые логические связки удовлетворяют всем аксиомам булевой алгебры, за исключением закона исключения третьего: $$ A\vee \neg A = 1,~~~~~~~~~~~~~~~A\,\&\,\neg A = 0. $$ Стоит это проверить, например, для $T_A=0.5$. Нарушение этого закона типично для многозначных логик
(в них требование, чтобы утверждение было или истинным, или ложным уже, очевидно, теряет свой смысл).


Нечёткие множества

Нечёткая логика тесно связана с теорией нечётких множеств. В последней вводится функция принадлежности $\mu_A(x)$ того, что некий объект $x$ принадлежит множеству $A$: $x\in A$. Значения этой функции лежат в интервале $[0...1]$, где $1$ означает точно принадлежит, а $0$ - точно не принадлежит.

Объединение $A\cup B$ нечётких множеств $A$, $B$ соответствует дизъюнкции (ИЛИ), а пересечение $A\cap B$ - конъюнкции (И). Их функции принадлежности равны: $$ \begin{array}{lll} \mu_{A\cap B}(x) = \min\{ \mu_A(x),~\mu_B(x)\}\\ \mu_{A\cup B}(x) = \max\{ \mu_A(x),~\mu_B(x)\}. \end{array} $$ Справа на рисунке в виде прямой $x$ изображено множество различных чашек с кофе (эти объекты не упорядочены и обычно рисуются областями на плоскости). Каждой чашке соответствует то или иное значение её принадлежности множествам "горячий" и "крепкий". Пунктиры - это границы чётких множеств. Красная линия является функцией принадлежности пересечения множеств ($\min$).


Нечёткие переменные

Кроме нечётких высказываний вводятся нечёткие переменные, степень истинности которых зависит от одного или нескольких вещественных чисел. Это частный случай нечёткого множества в котором каждый элемент нумеруется вектором вещественных чисесл. Например, говоря о кофе, можно определить следующие нечёткие переменные, зависящие от его температуры $t$:

$C(t)$ - "холодный",      $W(t)$ - "тёплый",      $H(t)$ - "горячий".

Другие примеры: медленный, быстрый (функции скорости); лёгкий, тяжёлый (функции массы); молодой, старый (функции возраста) и т.д.

К нечётким переменным можно применять различные модификаторы: $$ \text{очень}:~~~~A^2(x),~~~~~~~~~~~~\text{не очень}:~~~~\sqrt{A(x)}. $$ Так "очень горячий" $H^2(t)$ усиливает функцию $H(t)$, а "не очень горячий" $\sqrt{H(t)}$ её ослабляет.


Логический вывод Мамдани

Логический вывод Мамдани используется для набора утверждений (правил) относительно нечётких переменных. Пусть, например, есть два правила, зависящих от 6 нечётких переменных $A_i,B_i,C_i$, определяемых тремя параметрами $x,y,z$: $$ \begin{array}{llll} A_1(x) \,\&\,B_1(y) \to C_1(z),\\ A_2(x) \,\&\,B_2(y) \to C_2(z).\\ \end{array} $$ Предположим, что значения вещественных параметров $x,y$ известны и равны $x_0,y_0$.
Задача состоит в определении наиболее подходящего значения параметра $z$, удовлетворяющего этим правилам.

На первом этапе поиска $z$ проводится фаззификация (получение значений нечётких переменных $A_1(x_0)$ и т.д.) и вычисление значений посылок на основе формул нечёткой логики ($\min$ для $\&$ и $\max$ для $\vee$): $$ \left\{ \begin{array}{llll} \alpha_1 = \min\bigr(A_1(x_0),~B_1(y_0)\bigr) \\ \alpha_2 = \min\bigr(A_2(x_0),~B_2(y_0)\bigr) \end{array}\right., ~~~~~~~~~~~~~~ \left\{ \begin{array}{llll} \alpha_1 \to C_1(z)\\ \alpha_2 \to C_2(z)\\ \end{array}\right. $$ Затем "активизируются" следствия правил, в предположении, что их истинность не должна превышать истинности посылок (справа на рисунке уровни $\alpha_i$ отсекают высокие значения истинности следствий): $$ ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~C'_i(z) = \min (\alpha_i, C(z)). $$ Эти модифицированные следствия объединяются (логическое ИЛИ) по всем правилам, в результате чего получается функция распределения $\mu(z)\in[0...1]$ для переменной $z$: $$ \mu(z) = \max_i C'_i(z).~~~~~~ $$ На последнем этапе проводится дефаззификация, в результате которой выбирается конкретное значение для $z$. Для этого можно, например, взять точку центра тяжести функции $\mu(z)$: $$ z_0 =\int z\,\mu(z)\,dz ~\Bigr/~ \int \mu(z)\,dz. $$ Обратим внимание, что, как на этапе активизации, так и при дефаззификации посылки с низкой истинностью дают слабый вклад в результат (совсем ложные посылки вообще на него не влияют). Поэтому при активизации вместо функции $\min$ можно также использовать произведение: $C'_i(z)=\alpha_i\,C_i(z)$ (алгоритм Ларсена).

Существует модификация этого метода - вывод Цукамото. На этапе активизации следствий решаются уравнения: $C_i(z) = \alpha_i$, дающие единственные решения $z_i$. Такой подход возможен только, когда нечёткие переменные $C_i(z)$ в правилах являются монотонными функциями $z$ (растущими или убывающими), иначе решений будет несколько. На этапе дефаззификации также вычисляется центр тяжести по полученным решениям $z_1,z_2,...$: $$ z= \sum_i \alpha_i z_i~\Bigr/~\sum_i\alpha_i. $$

Существует также подход Сугено, в котором в правилах следствия записываются в виде инструкций для значений $z=F(x,y)$, где $F$ - некоторые функции (обычно линейные). После фаззификации мы сразу получаем значения $z_i$, по которым, как и выше, при помощи истинностей посылок $\alpha_i$ вычисляется центр тяжести.


Импликация

Нет единого мнения какое выражение для импликации следует использовать в нечёткой логике. Ниже приведены варианты, предлагавшиеся различными авторами:

\begin{array}{lll} \text{Гёдель} & \neg A \vee B & ~~~~~ & \max(1-T_A,~T_B) \\ \text{Заде} & \neg A \vee (A\,\&\,B)& & \max(1-T_A,~\min(T_A,T_B)) \\ \text{Лукасевич} & & & \min(1-T_A+T_B,~1)\\ \text{Вади} & & & \max(T_AT_B,~1-T_A)\\ \text{Брауэр} & & & T_B~~\text{if}~~T_A\gt T_B~~\text{else}~~1 \\ \text{Гоген} & & & \min(T_B/T_A,~1)\\ \end{array}

Напомним, что в бинарной логике импликация ложна только для $1\to 0$ (из истины нельзя получить ложь).
Во всех остальных случаях $0\to 0$, $0\to 1$, $1\to 1$ она истинна.

Так, в арифметике при любом $x$ истинна формула: $(x<2) \to (x<4)$. Когда посылка истинна ($x=1$), истинно и следствие. Если же посылка ложна, то следствие может быть как истинным (при $x=3$), так и ложным ($x=5$). Во всех этих случаях импликация истинна. "Менее правильное" утверждение $(x > 2) \to (x < 4)$ ложно при $x=5$.

Все приведенные выше определения воспроизводят булеву импликацию для значений $0,1$.


Норма и конорма

Выбор функций $\min$ для конъюнкции и $\max$ для дизъюнкцмм не является единственно возможным. Обозначим логическое И в виде функции $T(x,y)$ (норма), а логическое $ИЛИ$ как $S(x,y)$ (конорма). Потребуем, чтобы они были симметричны и ассоциативны: $$ \begin{array}{lll} T(x,y) = T(y,x) &~~~~~ &T(x, T(y,z)) = T(T(x, y),z)\\ S(x,y) = S(y,x) &~~~~~ &S(x, S(y,z)) = S(S(x, y),z)\\ \end{array} $$ Кроме этого наложим свойства ограниченности и монотонности (выполняющиеся для $\&, \vee$ и в бинарной логике): $$ \begin{array}{llll} \&:~~~ & T(0,0) = 0, & T(1,x) = x, &~~~~~ & x_1 \le x_2,~~~ y_1 \le x_2~~~\Rightarrow~~~~~T(x_1, y_1) \le T(x_2, y_2)\\ \vee\,:~~~ &S(1,1) = 1, & S(0,x) = x, &~~~~~ & x_1 \ge x_2,~~~ y_1 \ge x_2~~~\Rightarrow~~~~~S(x_1, y_1) \ge S(x_2, y_2)\\ \end{array} $$ Будем также предполагать, что выполняются законы де-Моргана $\neg(X\,\&\,Y) = \neg X\vee \neg Y$ и $\neg(X\vee Y) = \neg X\,\&\, \neg Y$, связывающие эти две операции: $$ \begin{array}{llll} 1-T(x,y) = S(1-x,1-y), & ~~~~~ & 1-S(x,y) = T(1-x,1-y). \\ \end{array} $$ Возможны, например, следующие функции, удовлетворяющие этим аксиомам: $$ \begin{array}{l|c|c|l|l} & высказывания & множества & \text{логические} & \text{алгебраические} \\ \hline \text{И} & A\,\&\,B & A \cap B & \min(\mu_A,\mu_B) & \mu_A\,\mu_B & \max(\mu_A+\mu_B-1,~ 0)\\ \text{ИЛИ} & A \vee B & A \cup B & \max(\mu_A,\mu_B) & \mu_A+\mu_B - \mu_A\mu_B & \min(\mu_A+\mu_B,~ 1) \end{array} $$

Естественно для всех них не выполняются законы исключения третьего. Кроме этого только для "логического" варианта $\min,\max$ справедливы свойства идемпотентности: $$ A\,\&\,A = A,~~~~~~~~~~~~A\vee A = A. $$ Это очень естественные свойства как для логических величин, так и для множеств ($A\cap A=A$ и $A\cup A=A$). Поэтому их выполнение крайне желательно. Отметим также, что для остальных определений нарушаются законы дистрибутивности: $$ \begin{array}{lcl} A\,\&\,(B\vee C) &=& (A\,\&\,B)\vee (A\,\&\,B)\\ A\vee(B\,\&\,C) &=& (A\vee B)\,\&\, (A\vee B). \end{array} $$ Это не так критично, но не вполне соответствует обыденному пониманию смысла логических операций.


Нечёткие числа

Нечёткое число $X$, это функция принадлежности $\mu_X(x)$ от вещественного числа $x$, имеющая единственный единичный максимум при $x=X$. На рисунке справа $\mu_0(x)$ - это "примерно ноль", а $\mu_3(x)$ - примерно три.

Пусть есть вещественная функция двух (обычных) чисел $z=f(x,y)$ и два нечётких числа $A(x), B(y)$. Нас интересует функция принадлежности $\mu_{f(A,B)}(z)$, равная степени уверенности в том, что конкретное число $z$ является результатом операции (функции) $f$.

Переберём все возможные значения $x,y$ для которых $z=f(x,y)$ и выясним степени уверенности того, что это нечёткие числа $A(x), B(y)$. Тогда по принципу расширения Заде функция принадлежности операции равна: $$ \mu_{f(A,B)}(z) = \sup_{x,y: f(x,y)=z}\min\bigr\{\mu_A(x),\,\mu_B(y)\bigr\}. $$ Таким образом, из всех возможных "чётких" способов получить $z$ выбираем то, которое даёт наибольшее ($\sup$) значение минимума функций принадлежности нечётких чисел аргументов функции.

Часто для нечётких чисел используют функции принадлежности $L-R$ типа $$ \mu_A(x) = \left\{ \begin{array}{lll} L(a-x) & x \ge a \\ R(x-a) & x \ge a \\ \end{array} \right. ~~~~~~~ \begin{array}{lll} L(0)=R(0) = 1 \\ L,R \text{ - не возрастают} \\ \end{array} $$ Простейшим примером является треугольная функция принадлежности $\langle a;\, \alpha, \beta \rangle$, приведенная на рисунке. При помощи принципа расширения для треугольных чисел можно получить следующие результаты для стандартных арифметических операций: $$ \begin{array}{lll} \langle a_1;\, \alpha_1,\beta_1 \rangle \pm \langle a_2;\, \alpha_2,\beta_2 \rangle = \langle a_1\pm a_2;\, \alpha_1+\alpha_2,\beta_1+\beta_2 \rangle\\ \langle a_1;\, \alpha_1,\beta_1 \rangle \cdot \langle a_2;\, \alpha_2,\beta_2 \rangle = \langle a_1\cdot a_2;\, \alpha_1 a_2+\alpha_2 a_1,\beta_1 b_2+\beta_2 b_1\rangle\\ \langle a;\, \alpha,\beta \rangle^{-1} = \langle 1/a;\, \beta/a^2,\alpha/a^2 \rangle \\ \end{array} $$

Другой способ задания функций принадлежности $\langle a,b; \alpha, \beta \rangle$ - это трапеция c максимумом на интервале $[a,b]$ и граничными точками $\alpha,\beta$.


Нечёткие отношения

Нечёткое отношение $R(x,y)$ данной пары сущностей $x,y$ (предметных констант) равно вещественному числу в диапазоне $[0...1]$ (степень истинности отношения). Например, отношение "почти совпадают" $x\approx y$ будет равно 1, если $x=y$ и близкие к 1 значения в окрестности диагонали матрицы $R(x,y)$.

В бинарной логике отношение $R(x,y)$ является подмножеством множества пар (декартово произведение) $X\times Y$. Соответственно нечёткое отношение является нечётким множеством и все определения (объединение, пересечение, дополнение отношений и т.д.) переносятся без изменений.

В частности, композиция двух отношений $A(x,y)$ и $B(x,y)$ по определению равна их max-min свёртке: $$ (A\odot B)(x,y) = [A(x,z_1)\,\&\,B(z_1,y)]~\vee~[A(x,z_2)\,\&\,B(z_2,y)]~\vee~..., $$ где для $\&$, как обычно, используется $\min$, а для $\vee$ - $\max$.

Часто встречаются следующие аксиомы для отношений: $$ \begin{array}{lllll} \text{рефлексивное} & R(x,x) = 1 \\ \text{антирефлексивное} & R(x,x) = 0 \\ \text{симметричное} & R(x,y) = R(y,x) \\ \text{асимметричное} & \min\bigr\{R(x,y),\,R(y,x)\bigr\} = 0 \\ \text{антисимметричное} & x\neq y ~\Rightarrow~ \min\bigr\{R(x,y),\,R(y,x)\bigr\} = 0 \\ \text{транзитивное} & \min\bigr\{R(x,y),\,R(y,z)\bigr\} \le R(x,z) \\ \end{array} $$