image

Вы когда-нибудь подумывали написать такой алгоритм, в соответствии с которым приложение само принимало бы решения, либо справлялось с какими-нибудь странными действиями, при помощи которых клиент отчаянно пытается его сломать?

Создавая такой алгоритм, вы заметите, что просто замусориваете ваш код логикой if-else (пока он не превратится в кашу), а самим вам начинает казаться, что вот так просто не прокатит.

Итак, если только вас не пробирает дрожь от математики – читайте дальше. Здесь в дело вступает нечёткая логика! Немного контекста: слово «нечёткий» (англ. «fuzzy») в данном случае означает «труднопонимаемый» — таков может быть, например, код вашего коллеги.

В этом посте я постараюсь объяснить нечёткую логику и объяснить, как она работает.

Что такое нечёткая логика?


Если просто – это логика, имитирующая мышление живого человека. Теперь представьте, чего можно добиться нечёткой логикой, помноженной на вычислительную мощность вашего ЦП – совершенно очевидно, что такой алгоритм сможет принимать решения быстрее вас.

Это просто расширение булевой логики – той самой, что оперирует 0 и 1.

image

С какой же целью она создавалась?


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

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

  1. Если сейчас в комнате холодно, и вы ставите кондиционер на обогрев, то он должен поднять температуру в комнате.
  2. Если сейчас в комнате тепло, а вы ставите кондиционер на поддержание тепла, то температура в комнате не должна измениться.
  3. Если сейчас в комнате жарко, а вы ставите кондиционер на охлаждение, то постепенно кондиционер должен снизить температуру в помещении.

Ниже мы разберём такие правила подробнее.

Использование нечёткой логики


Если вы заинтересовались, может ли нечёткая логика применяться в программировании для решения каких-либо задач кроме использования кондиционера, который мог бы заморозить офис – вот вам примеры:

1. Проверка правописания


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

…а вы взяли и выбрали Миссисипи. Конечно, это хорошо, но вы не знали, как именно пишется «Миссисипи», поэтому, берясь за домашнее задание, вы попробовали просто угадать.

image

К счастью, поисковик умеет предлагать правильную орфографию, подбирая её при помощи нечёткого соответствия (fuzzy matching) и функции проверки правописания.

2. Поиск


Итак, домашнюю работу вы сделали, и готовы отправиться в кроватку – но случайно споткнулись о сетевой кабель, и он оборвался. На родительском компьютере пропал Интернет.

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

Берёте ноутбук брата, выходите с него в любимый интернет-магазин и вводите в поисковой строке «Провод для интернета». Поскольку не знаете, что такое Ethernet-кабель.

image

Тадам! Вашему вниманию представлены разнообразные Ethernet-кабели и, даже если вы задали ключевое слово «интернет», алгоритм нечёткого поиска, действующий в магазине, «догадывается», что вам нужно.

3. Рекомендации


Вы оформили покупку и просто ждёте, пока вам доставят новый Ethernet-кабель, а тем временем решили полистать раздел с одеждой, вот так вам хочется. Через несколько секунд натыкаетесь на раздел «Recommend Items» («Рекомендуемые товары»).

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

Теперь, чтобы вам было проще разобраться в том, как устроена нечёткая логика, давайте углубимся в тему и начнём с основ. Вы готовы?

Классическая теория множеств


Для начала обратимся к простому разделу математики, в котором изучаются множества –это классическая теория множеств.

В классической трактовке множество – это совокупность определённых вполне различаемых объектов. Рассмотрим следующее изображение:

image

У нас есть множество чисел от 1 до 5, множество символов от A до E и даже множество слов, например, HTML, JavaScript, CSS и PHP.

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


Нечёткие множества могут рассматриваться как продолжение классических. В классическом случае элемент может относиться либо не относиться к множеству, тогда как к нечёткому множеству элемент может относиться как целиком, так и на половину, на четверть или на крошечную долю.

Например, говоря: «сейчас холодно» мы не имеем в виду страшный мороз, а говоря: «сейчас жарко» не имеем в виду испепеляющий зной. Обычно мы указываем, в какой степени сейчас жарко или холодно, обычно выражая это значение как температуру в градусах Цельсия.

Разумеется, именно от вас зависит, как вы расположите реальные значения в диапазоне от 0 до 1. Считайте, что 0 и 1 – это процентные значения, записанные в десятичной системе. 1 соответствует 100% и присваивается наилучшему значению, тогда как 0 соответствует 0% и присваивается наихудшему значению.

Лингвистические переменные и значения


Лингвистическими называются такие переменные, в которых слова и даже выражения берутся из обычного разговорного языка. Лингвистические значения – это, в сущности, значения лингвистических переменных.

temperature (t) = {cold, warm, hot}

В вышеприведённом примере temperature – это наша лингвистическая переменная, а cold, warm и hot – это лингвистические значения.

Функция принадлежности и нечёткие правила


В нечётком множестве функция принадлежности определяет значение или точку.

image

В данном примере мы подаём на ввод три функции принадлежности, скажем:

  1. Холодно
  2. Тепло
  3. Жарко

На вывод также имеем три функции принадлежности:

  1. 1. Холодно
  2. 2. Без изменений
  3. 3. Жарко

Нечёткая логика основана на простом правиле IF-THEN с условием и заключением.

Если сопоставить функции принадлежности с правилами нечёткой логики, то получим следующие инструкции:

IF (temperature is COLD) AND (target is COLD) THEN command is NO-CHANGE
IF (temperature is COLD) AND (target is WARM) THEN command is HEAT
IF (temperature is COLD) AND (target is HOT) THEN command is HEAT
IF (temperature is WARM) AND (target is COLD) THEN command is COOL
IF (temperature is WARM) AND (target is WARM) THEN command is NO-CHANGE
IF (temperature is WARM) AND (target is HOT) THEN command is HEAT
IF (temperature is HOT) AND (target is COLD) THEN command is COOL
IF (temperature is HOT) AND (target is WARM) THEN command is COOL
IF (temperature is HOT) AND (target is HOT) THEN command is NO-CHANGE


В следующей таблице в формате 3 x 3 представлены правила нечёткой логики:

image

Операции с нечёткими множествами


Вычисления в соответствии с правилами нечёткой логики и комбинирование результатов выполнения отдельных правил – это особый набор операций над нечёткими множествами.

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

1. Объединение
В данном случае вывод содержит все элементы обоих множеств.

2. Пересечение
В данном случае вывод содержит только общую часть обоих множеств.

3. Отрицание
В данном случае вывод содержит всё то, что не нашлось в множестве.

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

Дефаззификация


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

Нечёткое значение можно дефаззифицировать разными способами. Вот некоторые из них:

  • Сумма центров
  • Центроидный метод
  • Метод центра площади
  • Средневзвешенный метод
  • Метод максимума функции принадлежности


Применение нечёткой логики в PHP


Однажды к нам в отдел разработки обратились из HR-отдела и попросили написать приложение, которое позволило бы выбирать наилучшего кандидата из всех, претендующих на позицию веб-разработчика.

В данном посте я опишу эту задачу в упрощённом виде и перечислю только следующие критерии, по которым предполагалось судить о кандидатах:

  • Опыт соискателя – сколько лет он занимается разработкой веб-приложений.
  • Балл, набранный соискателем при практическом тестировании.
  • Балл, набранный соискателем на собеседованиях с командой и с HR.

Допустим, у нас есть следующий список соискателей с соответствующими признаками:

image

Пишем код


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

/**
 * Получить среднее арифметическое всех признаков
 * @param array $aParams
 * @return float|int
 */
private function getArithmeticMean(array $aParams)
{
    $mCount = (float)count($aParams);
    $mSum = (float)array_sum($aParams);

    return $mSum / $mCount;
}

Функция агрегации – среднее арифметическое

Затем воспользуемся треугольной функцией в качестве функции принадлежности.

/**
 * Треугольная функция принадлежности
 * @param $fApplicantValue
 * @param $aTrimfValues
 * @return float|int
 */
private function getTrimf(float $fApplicantValue, array $aTrimfValues)
{
    $aTrimfValues[0] = (float)$aTrimfValues[0];
    $aTrimfValues[1] = (float)$aTrimfValues[1];
    $aTrimfValues[2] = (float)$aTrimfValues[2];


    if ($fApplicantValue < $aTrimfValues[0]) {
        return 0;
    }

    if ($fApplicantValue >= $aTrimfValues[0] && $fApplicantValue <= $aTrimfValues[1]) {
        return ($fApplicantValue - $aTrimfValues[0]) / ($aTrimfValues[1] - $aTrimfValues[0]);
    }

    if ($fApplicantValue > $aTrimfValues[1] && $fApplicantValue <= $aTrimfValues[2]) {
        return ($aTrimfValues[1] - $fApplicantValue) / ($aTrimfValues[2] - $aTrimfValues[1]) + 1;
    }


    return 0;
}

Треугольная функция в качестве функции принадлежности

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

/**
 * Анализируем следующие функции и соискателей
 * @param array $aSetFeatures
 * @param array $aApplicants
 * @return array
 */
public function analyzeItems(array $aSetFeatures, array $aApplicants): array
{
    $aResults = [];

    for ($iCount = 0, $iCountMax = count($aApplicants); $iCount < $iCountMax; $iCount++) {
        $aResults[$iCount]['identifier'] = $aApplicants[$iCount]['identifier'];
        $aResults[$iCount]['score'] = $this->aggregateSet($aApplicants[$iCount], $aSetFeatures);
    }

    return $aResults;
}

/**
 * @param array $aApplicant
 * @param array $aSetFeatures
 * @return float|int
 */
private function aggregateSet(array $aApplicant, array $aSetFeatures)
{
    $aFeatureScores = [];

    for ($iCount = 0, $iCountMax = count($aSetFeatures); $iCount < $iCountMax; $iCount++) {
        $aFeatureScores[$iCount] = $this->getTrimf($aApplicant['features'][$aSetFeatures[$iCount]['identifier']], $aSetFeatures[$iCount]['values']);
    }

    return $this->getArithmeticMean($aFeatureScores);
}

Анализируем элементы и функции агрегации множеств

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

Например, в experience_years у нас следующие значения: 0, 3, 5. Таким образом, для нас предпочтительны люди с 3 годами опыта на фоне тех, у кого нет и года опыта и тех, чей опыт уже составляет 5 лет и более.

$this->aSetFeatures = [
    [
        'identifier' => 'experience_years',
        'values'     => [0, 3, 5]
    ], [
        'identifier' => 'practical_test_score',
        'values'     => [0, 100, 100]
    ], [
        'identifier' => 'team_interview_score',
        'values'     => [0, 5, 5]
    ], [
        'identifier' => 'hr_interview_score',
        'values'     =>  [0, 10, 10]
    ]
];

Массив признаков

Теперь необходимо указать входные значения для каждого соискателя:

$this->aApplicants = [
    [
        'identifier' => 'Applicant A',
        'features' => [
            'experience_years'     => 3,
            'practical_test_score' => 87.30,
            'team_interview_score' => 5,
            'hr_interview_score'   => 9
        ]
    ], [
        'identifier' => 'Applicant B',
        'features' => [
            'experience_years'     => 4,
            'practical_test_score' => 88.25,
            'team_interview_score' => 3,
            'hr_interview_score'   => 8
        ]
    ], [
        'identifier' => 'Applicant C',
        'features' => [
            'experience_years'     => 4,
            'practical_test_score' => 81.67,
            'team_interview_score' => 5,
            'hr_interview_score'   => 7
        ]
    ], [
        'identifier' => 'Applicant D',
        'features' => [
            'experience_years'     => 1,
            'practical_test_score' => 91.90,
            'team_interview_score' => 4,
            'hr_interview_score'   => 7
        ]
    ], [
        'identifier' => 'Applicant E',
        'features' => [
            'experience_years'     => 1,
            'practical_test_score' => 89.58,
            'team_interview_score' => 4,
            'hr_interview_score'   => 8
        ]
    ], [
        'identifier' => 'Applicant F',
        'features' => [
            'experience_years'     => 2,
            'practical_test_score' => 89.49,
            'team_interview_score' => 4,
            'hr_interview_score'   => 7
        ]
    ], [
        'identifier' => 'Applicant G',
        'features' => [
            'experience_years'     => 4,
            'practical_test_score' => 98.94,
            'team_interview_score' => 4,
            'hr_interview_score'   => 8
        ]
    ], [
        'identifier' => 'Applicant H',
        'features' => [
            'experience_years'     => 4,
            'practical_test_score' => 80.80,
            'team_interview_score' => 4,
            'hr_interview_score'   => 8
        ]
    ], [
        'identifier' => 'Applicant I',
        'features' => [
            'experience_years'     => 2,
            'practical_test_score' => 82.97,
            'team_interview_score' => 4,
            'hr_interview_score'   => 8
        ]
    ], [
        'identifier' => 'Applicant J',
        'features' => [
            'experience_years'     => 2,
            'practical_test_score' => 81.91,
            'team_interview_score' => 3,
            'hr_interview_score'   => 7
        ]
    ]
];

Массив соискателей

Наконец, остаётся добавить код, который запускал бы анализатор и выводил результаты на экран.

/**
 * Запустить анализатор и отобразить результаты
 * @return Factory|View
 */
public function index()
{
    $aResults = $this->analyzeItems($this->aSetFeatures, $this->aApplicants);
    return view('index', compact($aResults));
}

Функция индекса

Вывод


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

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

Подробнее эта тема разобрана в репозитории на Github. Именно на его основе написана большая часть представленного здесь демо-кода. Также можете познакомиться со ссылками, приведёнными ниже.
Всем мира! ✌

Ссылки:


  1. Нечёткие множества в изложении Лотфи Заде
  2. Краткое руководство по нечёткой логике
  3. Что такое нечёткая логика?
  4. Введение в нечёткую логику
  5. Контроль температуры с использованием нечёткой логики
  6. Искусственный интеллект – системы нечёткой логики
  7. ketili/fuzzydm


Комментарии (19)


  1. NickDoom
    30.01.2023 17:44
    +11

    Извините. Извините. Извините.

    Я просто не могу не оставить это тут.

    Два паунда навоза.

    Извините ещё раз.


    1. NickDoom
      30.01.2023 18:59
      +3

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

      Я не просто так несколько лет избегал здесь регистрироваться, да вот на свою голову поддался. Хорошо, инвайт не принял, не придётся никому за меня краснеть. Вы упоротые. Невозможно существовать на минном поле, не зная, какой снежинке на триггер сейчас наступишь. А сидеть на ресурсе, чтобы молчать и бояться что-то не то сказать — такое себе.

      Это просто смешная история о человеке, интерпретировавшем теорию нечётких множеств через один паунд навоза и один — мёда.

      Люди, вы сошли с ума.

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

      Да, вы правильно поняли, за карму я не беспокоюсь. Смысла больше нет.


      1. vkni
        30.01.2023 20:19
        +2

        Да, вы правильно поняли, за карму я не беспокоюсь. Смысла больше нет.

        Подправил карму. Ну, понимаете, невозможно жить в обществе и быть свободным от него. Сейчас, фактически в мире идёт/начинается гражданская война (эгалитаризм против элитаризма, если в 2 словах). И никуда вы от неё не денетесь. Увы и ах. :-(

        Да, лирический герой вашей ссылки — откровенный нацист. Раньше это сходило с рук, сейчас режет настолько, что я её не захотел дочитать, несмотря на хороший слог.


        1. medstrax
          01.02.2023 22:55

          А в чем там нацизм?

          И почему сейчас внезапно стало резать, а раньше не резало?


  1. 0xd34df00d
    30.01.2023 18:43
    +1

    Как определяется понятие функции между двумя нечеткими множествами? Что такое, например, декартово произведение двух нечетких множеств?


    1. vkni
      30.01.2023 20:16

      А вот тут и должен помочь подход с полурешётками, который я попытался описывать в недавней статье. То есть, ты пишешь совершенно чёткую полурешётку для примера из статьи:

      1. Холодно

      2. Тепло

      3. Жарко

      Которая выглядит так:
      Непонятно-Top

      Холодно||Тепло Тепло||Жарко

      Холодно Тепло Жарко

      Дальше с этой полурешётки ты можешь строить так называемые монотонные функции на другие полурешётки. И аналогично, подозреваю, с тензорным произведением (правда тут подозреваю несколько неотчётливо).


      1. 0xd34df00d
        30.01.2023 20:56

        Окей, давай начнём с кое-чего попроще.


        Как определяется равенство элемента самому себе в нечётком множестве?


        1. vkni
          30.01.2023 21:43

          Вот ни одну статью из тутошних про «нечёткие множества» я не понимаю. Вернее, они только наводят тень на плетень. Скажем эта вываливает простыню из if'ов.

          Если на решётках, то там простые множества. И равенство элемента самому себе определяется легко.


          1. 0xd34df00d
            30.01.2023 21:43

            Если на решётках, то там простые множества. И равенство элемента самому себе определяется легко.

            Как? :]


            1. vkni
              30.01.2023 21:45

              Как обычно: если это он, то он себе равен, иначе не равен.


            1. vkni
              30.01.2023 21:46

              Ты, возможно, имел ввиду равенство результатов двух измерений?


              1. 0xd34df00d
                31.01.2023 20:10

                Нет, именно двух элементов.


                Есть такая прикольная тема, как Heyting-valued sets. Если ты фиксируешь какую-то гейтингову алгебру Ω (так что про решётки ты очень в тему вспомнил), то такое множество A — это обычное множество A и некоторая обычная функция d_A: A × A → Ω, которая говорит, насколько два элемента «похожи». Функции тоже можно определять аналогично — например, функция f из A в B — это на самом деле функция f: A × B → Ω с некоторыми дополнительными условиями вроде того, что f(a, b) ⊓ d_A(a, a') ≤ f(a', b) (конкретно это можно читать как то, что функция на одинаковых аргументах даёт не менее одинаковые значения) или f(a, b) ⊓ f(a, b') ≤ d_B(b, b') (а это — что одинаковость функциональной связи a-b и a-b' не больше, чем одинаковость b и b').


                Вот интересно, насколько эти все нечёткие множества отличаются.


                1. vkni
                  01.02.2023 18:08

                  Вот интересно, насколько эти все нечёткие множества отличаются.

                  Ну на язык решёток я могу перевести достаточно легко. Вообще, если хочешь, могу попробовать описать, как оно соотносится — Heyting-valued sets (про которые я только сейчас от тебя узнал) и полурешётки, и то, что тут описано. Но это пара дней и статья тутова.


            1. Refridgerator
              31.01.2023 07:21

              Как? :]
              Сказано — легко. Нечёткая логика же. В этом её и прелесть — любой ответ правильный, даже если на первый взгляд лишен смысла. Исполнитель же тоже нечёткий. Он может монетку подбросить, или карты Таро кинуть, или ещё что.


        1. AVX
          30.01.2023 22:50

          Весь мульт тут - нечёткая логика: "то вроде лепится, то не лепится" ))


    1. funca
      31.01.2023 14:45

      Как определяется понятие функции между двумя нечеткими множествами

      Может только как функтор? В общем случае на вкус и цвет фломастеры разные.


  1. alexhott
    31.01.2023 07:38
    +2

    В разное время работал в разных компаниях, у каждой было свое доморощенное ПО дико большое в виде монолита, потом куча сервисов появилась вокруг.
    Так я вам скажу там все построено на нечеткой логике, чуть тронешь в одном месте в десяти вылазит поведение которого никто не ожидал!


    1. funca
      31.01.2023 14:50

      fuzzy это не то же самое, что nondeterministic - в плане логики в ней как раз все довольно четко.


  1. synchronized
    02.02.2023 05:56

    Доброго времени суток. Статья вызвала у меня когнитивный диссонанс. Конечно я давно (20 лет тому назад) читал:

    Заде Л.А. Принятие решений в расплывчатых условиях, 1970
    Тэрано Т., Асаи К., Сугэно М. Прикладные нечеткие системы. 1993 и др.

    в книгах «fuzzy» - расплывчатый или нечеткий, т.е. недостоверный на 100%. Например. Проводя выбор кандидатов, Вы не доверяете результатам собеседований. Но в этих не достоверных условиях вам нужно принять четкое и правильное решение. Ваш вариант перевода - «труднопонимаемый» кем?

    Далее. Не увидел классики - фазификации (или "размытия"). Метода перевода реальных сущностей в нечеткие множества (в мир fuzzy). Например. На графике "Функция принадлежности и нечёткие правила" реальная температура ~7,5 Celsius будет соответствовать 0,2 Cold и 0,2 Warm.

    Далее. ЛП - лингвистические правила, правила которые с помощью "человеческого языка" (не понятного технике) описать правила поведения человеческой логики в данной ситуации. Например. IF (temperature is COLD) AND (target is WARM) THEN command is HEAT где HEAT нечеткое множество лингвистической переменной command. А чтобы технике ее понять (техника понимает только числа) , нужно перевести в реальный мир посредством дефазификации.

    Далее. Практическое применение. На практике у Вас 4 лингвистических переменных. А где выходная лингвистическая переменная "годность"? Где ЛП отражающие условия выбора "человека".

    Может быть проще (линейно). Например.

    годность = Опыт соискателя * (тестировании * коэфф. важности 1 + собеседование с командой * коэфф. важности 2 + собеседование с HR * коэфф. важности 3) - Опыт соискателя * (1 - собеседование с командой) * коэфф. важности 4?