Перейти к содержанию

Выпуклость нечёткого множества

  • Статус: проектный контракт задачи #77
  • Решение: ADR-0009
  • Область действия: одномерные скалярные нечёткие множества
  • Публичный API: не реализован

Смысл выпуклости

Для нечёткого множества A на вещественном интервале X FuzzyRoutines использует условие выпуклости Заде:

mu_A(lambda*x + (1 - lambda)*y) >= min(mu_A(x), mu_A(y))

для любых x, y из X и любого lambda из [0, 1].

График mu_A не обязан быть графиком выпуклой функции. Условие означает квазивогнутость mu_A: на интервале она может возрастать, оставаться постоянной и убывать, но не может иметь впадину между двумя более высокими степенями принадлежности. Поэтому монотонные функции принадлежности также задают выпуклые нечёткие множества.

Нечёткая выпуклость не влечёт нормальности. Субнормальный холм, монотонное плечо и пустое нечёткое множество могут быть выпуклыми.

Эквивалентность через альфа-срезы

Нестрогий альфа-срез:

A_alpha = {x in X | mu_A(x) >= alpha}, 0 < alpha <= 1.

На непрерывном скалярном универсальном множестве эквивалентны следующие утверждения:

  1. A удовлетворяет неравенству принадлежности для каждой пары и каждой выпуклой комбинации.
  2. Каждый положительный нестрогий альфа-срез — выпуклое чёткое подмножество X.

Короткое доказательство определяет контракт реализации. Если две координаты входят в A_alpha, обе степени не меньше alpha; неравенство принадлежности помещает каждую координату между ними в тот же срез. Обратно, положим alpha = min(mu_A(x), mu_A(y)). При положительном alpha применяется выпуклость среза, а случай alpha = 0 уже покрывается диапазоном принадлежности.

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

Непрерывное представление

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

Принятые аналитические семейства MFunction допускают точное подтверждение по формулам:

Семейство Форма, доказывающая квазивогнутость
Hyperbolic постоянная часть, затем убывание
Bell возрастание, постоянная часть, убывание
Parabolic возрастающее плечо
Triangle возрастание, затем убывание
Trapezium возрастание, постоянная часть, убывание
Exponential возрастание и убывание относительно центра
Sigmoidal монотонная функция
Desirability монотонная функция

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

Произвольный Python-вычислитель принадлежности — другой случай. Для любого алгоритма с конечным числом вычислений можно построить второй вычислитель с теми же значениями в проверенных точках, но с узкой более низкой впадиной в другом месте. Следовательно, конечное вычисление может найти контрпример, но не подтвердить глобальную выпуклость. Точный положительный результат для такого представления требует аналитического подтверждения, символьной структуры или доказанного правила построения.

Дискретное представление

Пусть дискретное универсальное множество объявляет

x_0 < x_1 < ... < x_(n-1).

Его точное условие относительно порядка:

mu_A(x_j) >= min(mu_A(x_i), mu_A(x_k)) for every i <= j <= k.

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

Например, при X = {0, 2, 10}:

  • срез с {0, 2} порядково выпуклый;
  • срез с {0, 10}, но без 2, не является порядково выпуклым;
  • промежутки (0, 2) и (2, 10) не имеют семантики принадлежности, пока явная политика интерполяции не построит новое непрерывное нечёткое множество.

Проверка точна, поскольку вычисляются все объявленные координаты. Рабочая реализация может использовать эквивалентное правило унимодальной последовательности: степени не убывают до области максимума и не возрастают после неё. Тесты должны сохранять прямое неравенство для троек как независимый эталон.

Выборочные свидетельства для непрерывного случая

Выборка непрерывной функции принадлежности даёт свидетельства с объявленными областью и разрешением. Она не меняет универсальное множество или представление.

Отчёт может сообщать:

COUNTEREXAMPLE
    sampled coordinates exhibit a strict valley

NO_SAMPLED_VIOLATION
    no tested coordinate triple exhibits a strict valley

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

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

Соглашения о срезах и концах

  • Альфа-срезы нестрогие: равенство степени порогу включает координату.
  • Положительные уровни: 0 < alpha <= 1; срез уровня 1 — ядро.
  • Нестрогий нулевой срез — всё универсальное множество; для выпуклости он избыточен.
  • Пустые и одноточечные срезы выпуклы.
  • Концы срезов могут быть открытыми, если универсальное множество исключает конец или функция принадлежности разрывна. Выпуклость не влечёт замкнутости или верхней полунепрерывности.
  • Множество поддержки использует отдельное строгое условие mu_A(x) > 0.
  • Область интегрирования — рабочий численный интервал, который не ограничивает глобальное утверждение о выпуклости.

Будущая матрица исполняемых тестов

Представление Точный положительный результат Отрицательный результат Обязательная защита
Аналитическое проверенное подтверждение семейства явный аналитический контрпример неизвестные семейства остаются неизвестными
Дискретное полный перебор объявленных координат нарушающая неравенство объявленная тройка без утверждения об интерполяции
Выборочное никогда только из выборки нарушающая неравенство тройка выборки успех означает только NO_SAMPLED_VIOLATION
Вызываемый объект только отдельное подтверждение или правило замкнутости явный вычисленный контрпример конечные запросы никогда не возвращают PROVEN_CONVEX

Будущий набор тестов реализации должен:

  1. покрывать каждое каноническое аналитическое семейство и псевдоним на границах параметров;
  2. сравнивать оптимизированный дискретный алгоритм с полным перебором троек для всех коротких последовательностей из небольшого точного алфавита степеней принадлежности;
  3. сравнивать дискретные результаты со срезами на каждом различном положительном уровне;
  4. проверять детерминированные координаты и степени контрпримеров;
  5. проверять открытые, замкнутые, ограниченные и неограниченные непрерывные универсальные множества;
  6. включать узкую впадину между точками, не обнаруживаемую ни грубой, ни уточнённой сеткой;
  7. проверять сохранение сведений о выборке при сериализации и отображении;
  8. отклонять любое преобразование NO_SAMPLED_VIOLATION в доказанное булево утверждение.

Что не входит в контракт

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

Источники