Стандартная статья о нечеткой логике обычно грешит двумя вещами:
Все это грустно, потому что нечеткая логика — это одно из величайших достижений математики XX-ого века, если критерием брать практическую пользу. В этой статье я попытаюсь показать, насколько это простой и мощный инструмент программирования — настолько же простой, но гораздо более мощный, чем система обычных логических операций.
Самым замечательным фактом о нечеткой логике является то, что это прежде всего логика. Из начал мат-логики известно, что любая логическая функция может быть представлена дизъюнктивной или конъюнктивной нормальной формой, из чего следует, что для реализации исчисления высказываний достаточно всего трех операций: конъюнкции (&&), дизъюнкции (||) и отрицания (!). В классической логике каждая из этих операций задана таблицей истинности:
В нечеткой логике, в отличие от классической, вместо величин истина и ложь используется величина степень истинности, принимающая любые значения из бесконечного множества от 0 до 1 включительно. Следовательно логические операции уже нельзя представить таблично. В нечеткой логике они задаются фукнциями.
Есть два способа реализации дизъюнкции и конъюнкции:
Отрицание задается единственным способом (не трудно догадаться):
Легко проверить, что для крайних случаев — когда значения переменных исключительно 1 или 0 — приведенные выше функции дают таблицы истинности операций классической логики. Готово! Теперь у нас есть расширенная логика, обладающая невероятной мощью, простотой и при этом полностью совместимая с классической логикой в предельных случаях. Значит везде, где мы [программисты] используем логические выражения, мы можем использовать выражения нечеткой логики? Не совсем.
Дело в том, что все операторы языков программирования требуют четких условий, поэтому в какой-то момент всегда приходится из нечеткой степени истинности получать четкий критерий срабатывания. Это похоже на то, что происходит в квантовом мире: до тех пор, пока система эволюционирует в соответствии с уравнением Шредингера, ее квантовое состояние изменяется детерминированно и непрерывно, но как только мы прикасаемся к системе, происходит квантовый скачок, и система сваливается в одно из дискретных состояний. В нечеткой логике это называется дефаззификацией. Природа просто превращает квантовое состояние в вероятность и бросает кости, но вообще говоря методы дефаззификации бывают разные. Я не буду углубляться в эту тему, потому что объем ее тянет на отдельную статью. Упомяну лишь только, что метод дефаззификации следует выбирать, учитывая семантику задачи.
Для примера представим себе систему управления ракетой, использующую нечеткую логику для обхода препятствий. Представим себе, что ракета летит точно в гору, и система управления вычисляет решение: лететь вправо — 0.5, лететь влево — 0.5. Если использовать дефаззификацию методом центра масс, то система управления даст команду — лететь прямо. Бум! Очевидно, что в этом случае правильное решение — бросить кости и получить команду «влево» или «вправо» с вероятностью 50%.
В простейшем случае, когда нужно принять решение на основании степени истинности, можно разбить множество [0,1] на интервалы и использовать if-else-if.
Если нечеткая логика используется для поиска по нечеткому критерию, то дефаззификация вообще может быть не нужна. Производя сравнения, мы будем получать некоторое значение степени равенства для каждого элемента пространства поиска. Мы можем определить некоторую минимальную степень равенства, значения ниже которой нас не интересуют; для оставшихся элементов степень равенства будет релевантностью, по убыванию которой мы будем сортировать результаты, и пускай пользователь решит, какой результат правильный.
В качестве примера приведу использование нечеткой логики для решения задачи, которой я развлекался еще в институте — это задача поиска китайского иероглифа по изображению.
Я сразу отбросил идею распознавать любой каракуль, нарисованный пользователем на экране (тогда это был экран КПК). Вместо этого программа предлагала выбрать тип черты из порядка 23-х, определенных правилами японской каллиграфии. Выбрав тип черты, пользователь рисовал прямоугольник, в который вписывалась черта. Фактически, иероглиф — и введенный, и хранимый в словаре — представлялся в виде множества прямоугольников, для которых был определен тип.
Как определить равенство иероглифов в таком представлении? Для начала сформулируем критерий в четкой постановке:
Иероглифы A и B равны тогда и только тогда, когда для каждой черты в A существует равная ей черта в B и для каждой черты в B существует равная ей черта в A.
Неявно предполагается, что иероглифы не содержат черт-дубликатов, то есть, если некоторая черта совпала с чертой в другом иероглифе, то ни с одной другой чертой в том же иероглифе она совпасть не может.
Равенство черт можно определить следующим образом:
Черты равны тогда и только тогда, когда относятся к одному типу и их прямоугольники занимают одну и ту же площадь.
Эти два определения дают нам систему утверждений, которой достаточно для реализации алгоритма поиска.
Для начала построим матрицу E[n,n] следующим образом:
Затем сомкнем эту матрицу в вектор M[n]:
Я использую максиминный подход, потому что, на практике, колорометрический дает слишком маленькие значения для конъюнкций. Если вспомнить, что max — это дизъюнкция, то получается, что мы вычисляем утверждение, что i-я черта A равна первой черте B или второй или третьей и т.д. Таким образом M — это вектор совпадений черт A с чертами B.
Далее, нам нужно превратить вектор совпадений в одно единственное значение, и это можно сделать двумя способами:
Оба способа работают, но по-разному, причем второй способ работает даже если сравнивать черты четко. Какой из них правильней — вопрос философский.
Еще пару слов стоит сказать о сравнении черт. В соответствии с определением, равенство черт — это конъюнкция двух условий: равенства типов и равенства прямоугольников. Черты некоторых типов очень похожи. Вводя, пользователь легко может их перепутать, поэтому стоит иметь таблицу похожести, значения которой будут отражать насколько черта i похожа на черту j (на главной диагонали, естественно, будут единицы). Как степень равенства прямоугольников можно брать отношение площади их пересечения к площади большего из прямоугольников.
Вобщем, область применения нечеткой логики весьма обширна. В любом алгоритме, в любой системе правил попробуйте заменить истину и ложь на степень истинности и, возможно, эта система правил или алгоритм станут более точно отражать реальность. В конце концов, мы живем в мире, который фундаментально нечеток.
- В 99% случаев статья касается исключительно применения нечеткой логики в контексте нечетких множеств, а точнее нечеткого вывода, а еще точнее алгоритма Мамдани. Складывается впечатление, что только этим способом нечеткая логика может быть применена, однако это не так.
- Почти всегда статья написана на математическом языке. Замечательно, но программисты пользуются другим языком с другими обозначениями. Поэтому оказывается, что статья просто непонятна тем, кому, казалось бы, должна быть полезна.
Все это грустно, потому что нечеткая логика — это одно из величайших достижений математики XX-ого века, если критерием брать практическую пользу. В этой статье я попытаюсь показать, насколько это простой и мощный инструмент программирования — настолько же простой, но гораздо более мощный, чем система обычных логических операций.
Самым замечательным фактом о нечеткой логике является то, что это прежде всего логика. Из начал мат-логики известно, что любая логическая функция может быть представлена дизъюнктивной или конъюнктивной нормальной формой, из чего следует, что для реализации исчисления высказываний достаточно всего трех операций: конъюнкции (&&), дизъюнкции (||) и отрицания (!). В классической логике каждая из этих операций задана таблицей истинности:
a b || a b && a ! -------- -------- ---- 0 0 0 0 0 0 0 1 0 1 1 0 1 0 1 0 1 0 1 1 0 0 1 1 1 1 1 1
В нечеткой логике, в отличие от классической, вместо величин истина и ложь используется величина степень истинности, принимающая любые значения из бесконечного множества от 0 до 1 включительно. Следовательно логические операции уже нельзя представить таблично. В нечеткой логике они задаются фукнциями.
Есть два способа реализации дизъюнкции и конъюнкции:
#Максиминный подход: a || b => max(a, b) a && b => min(a, b) #Колорометрический подход: a || b => a + b - a * b a && b => a * b
Отрицание задается единственным способом (не трудно догадаться):
!a => 1 - a
Легко проверить, что для крайних случаев — когда значения переменных исключительно 1 или 0 — приведенные выше функции дают таблицы истинности операций классической логики. Готово! Теперь у нас есть расширенная логика, обладающая невероятной мощью, простотой и при этом полностью совместимая с классической логикой в предельных случаях. Значит везде, где мы [программисты] используем логические выражения, мы можем использовать выражения нечеткой логики? Не совсем.
Дело в том, что все операторы языков программирования требуют четких условий, поэтому в какой-то момент всегда приходится из нечеткой степени истинности получать четкий критерий срабатывания. Это похоже на то, что происходит в квантовом мире: до тех пор, пока система эволюционирует в соответствии с уравнением Шредингера, ее квантовое состояние изменяется детерминированно и непрерывно, но как только мы прикасаемся к системе, происходит квантовый скачок, и система сваливается в одно из дискретных состояний. В нечеткой логике это называется дефаззификацией. Природа просто превращает квантовое состояние в вероятность и бросает кости, но вообще говоря методы дефаззификации бывают разные. Я не буду углубляться в эту тему, потому что объем ее тянет на отдельную статью. Упомяну лишь только, что метод дефаззификации следует выбирать, учитывая семантику задачи.
Для примера представим себе систему управления ракетой, использующую нечеткую логику для обхода препятствий. Представим себе, что ракета летит точно в гору, и система управления вычисляет решение: лететь вправо — 0.5, лететь влево — 0.5. Если использовать дефаззификацию методом центра масс, то система управления даст команду — лететь прямо. Бум! Очевидно, что в этом случае правильное решение — бросить кости и получить команду «влево» или «вправо» с вероятностью 50%.
В простейшем случае, когда нужно принять решение на основании степени истинности, можно разбить множество [0,1] на интервалы и использовать if-else-if.
Если нечеткая логика используется для поиска по нечеткому критерию, то дефаззификация вообще может быть не нужна. Производя сравнения, мы будем получать некоторое значение степени равенства для каждого элемента пространства поиска. Мы можем определить некоторую минимальную степень равенства, значения ниже которой нас не интересуют; для оставшихся элементов степень равенства будет релевантностью, по убыванию которой мы будем сортировать результаты, и пускай пользователь решит, какой результат правильный.
В качестве примера приведу использование нечеткой логики для решения задачи, которой я развлекался еще в институте — это задача поиска китайского иероглифа по изображению.
Я сразу отбросил идею распознавать любой каракуль, нарисованный пользователем на экране (тогда это был экран КПК). Вместо этого программа предлагала выбрать тип черты из порядка 23-х, определенных правилами японской каллиграфии. Выбрав тип черты, пользователь рисовал прямоугольник, в который вписывалась черта. Фактически, иероглиф — и введенный, и хранимый в словаре — представлялся в виде множества прямоугольников, для которых был определен тип.
Как определить равенство иероглифов в таком представлении? Для начала сформулируем критерий в четкой постановке:
Иероглифы A и B равны тогда и только тогда, когда для каждой черты в A существует равная ей черта в B и для каждой черты в B существует равная ей черта в A.
Неявно предполагается, что иероглифы не содержат черт-дубликатов, то есть, если некоторая черта совпала с чертой в другом иероглифе, то ни с одной другой чертой в том же иероглифе она совпасть не может.
Равенство черт можно определить следующим образом:
Черты равны тогда и только тогда, когда относятся к одному типу и их прямоугольники занимают одну и ту же площадь.
Эти два определения дают нам систему утверждений, которой достаточно для реализации алгоритма поиска.
Для начала построим матрицу E[n,n] следующим образом:
for i in 1..n
for j in 1..n
E[i,j] = A[i] == B[j]
end
end
#A и B - это иероглифы; A[i] и B[j] - это их черты, и оператор '==' вычисляет их нечеткое равенство.
#Предполагается, что оба иероглифа имеют одинаковое количество черт - n.Затем сомкнем эту матрицу в вектор M[n]:
for i in 1..n M[i] = E.max_in_row(i) end #Метод max_in_row вычисляет максимальное значение в строке матрицы.
Я использую максиминный подход, потому что, на практике, колорометрический дает слишком маленькие значения для конъюнкций. Если вспомнить, что max — это дизъюнкция, то получается, что мы вычисляем утверждение, что i-я черта A равна первой черте B или второй или третьей и т.д. Таким образом M — это вектор совпадений черт A с чертами B.
Далее, нам нужно превратить вектор совпадений в одно единственное значение, и это можно сделать двумя способами:
#Просто нечеткой конъюнкцией. e = M.min #Либо так: e = M.sum / M.length #(отношение суммы элементов к длине вектора).
Оба способа работают, но по-разному, причем второй способ работает даже если сравнивать черты четко. Какой из них правильней — вопрос философский.
Еще пару слов стоит сказать о сравнении черт. В соответствии с определением, равенство черт — это конъюнкция двух условий: равенства типов и равенства прямоугольников. Черты некоторых типов очень похожи. Вводя, пользователь легко может их перепутать, поэтому стоит иметь таблицу похожести, значения которой будут отражать насколько черта i похожа на черту j (на главной диагонали, естественно, будут единицы). Как степень равенства прямоугольников можно брать отношение площади их пересечения к площади большего из прямоугольников.
Вобщем, область применения нечеткой логики весьма обширна. В любом алгоритме, в любой системе правил попробуйте заменить истину и ложь на степень истинности и, возможно, эта система правил или алгоритм станут более точно отражать реальность. В конце концов, мы живем в мире, который фундаментально нечеток.
