Расслабленный перекресток

Ослабленное пересечение m множеств соответствует классическому пересечению между множествами, за исключением того, что разрешено ослабить несколько множеств, чтобы избежать пустого пересечения. Это понятие может быть использовано для решения проблем удовлетворения ограничений , которые являются несогласованными, путем ослабления небольшого числа ограничений . Когда для оценки параметров рассматривается подход с ограниченной ошибкой , ослабленное пересечение позволяет быть устойчивым по отношению к некоторым выбросам .

Q - релаксированное пересечение m подмножеств , обозначенное как , представляет собой множество всех , которые принадлежат всем 's, за исключением не более. Это определение иллюстрируется рисунком 1.${\displaystyle X_{1},\точки ,X_{м}}$${\displaystyle R^{n}}$${\displaystyle X^{\{q\}}=\bigcap ^{\{q\}}X_{i}}$${\displaystyle x\in R^{n}}$${\displaystyle X_{i}}$${\displaystyle д}$

Определять${\displaystyle \lambda (x)={\text{card}}\left\{i\ |\ x\in X_{i}\right\}.}$

У нас есть${\displaystyle X^{\{q\}}=\lambda ^{-1}([mq,m]).}$

Характеристика q-релаксированного пересечения представляет собой, таким образом, задачу обращения множества . ^[1]

Рассмотрим 8 интервалов:${\displaystyle X_{1}=[1,4],}$${\displaystyle X_{2}=\ [2,4],}$${\displaystyle X_{3}=[2,7],}$${\displaystyle X_{4}=[6,9],}$${\displaystyle X_{5}=[3,4],}$${\displaystyle X_{6}=[3,7].}$

У нас есть

${\displaystyle X^{\{0\}}=\emptyset ,}$${\displaystyle X^{\{1\}}=[3,4],}$${\displaystyle X^{\{2\}}=[3,4],}$${\displaystyle X^{\{3\}}=[2,4]\cup [6,7],}$${\displaystyle X^{\{4\}}=[2,7],}$${\displaystyle X^{\{5\}}=[1,9],}$${\displaystyle X^{\{6\}}=]-\infty ,\infty [.}$

Расслабленное пересечение интервалов не обязательно является интервалом. Таким образом, мы берем интервальную оболочку результата. Если 's являются интервалами, расслабленное пересечение можно вычислить со сложностью m .log( m ) с помощью алгоритма Марзулло . Достаточно отсортировать все нижние и верхние границы m интервалов, чтобы представить функцию . Затем мы легко получаем множество${\displaystyle X_{i}}$${\displaystyle \лямбда}$

${\displaystyle X^{\{q\}}=\lambda ^{-1}([mq,m])}$

что соответствует объединению интервалов. Затем мы возвращаем наименьший интервал, который содержит это объединение.

На рисунке 2 показана функция , связанная с предыдущим примером.${\displaystyle \лямбда (x)}$

Чтобы вычислить q -релаксированное пересечение m ящиков , мы проецируем все m ящиков относительно n осей. Для каждой из n групп из m интервалов мы вычисляем q -релаксированное пересечение. Мы возвращаем декартово произведение n полученных интервалов. ^[2] На рисунке 3 представлена ​​иллюстрация 4-релаксированного пересечения 6 ящиков. Каждая точка красного ящика принадлежит 4 из 6 ящиков.${\displaystyle R^{n}}$

Q -релаксированное объединение определяется как${\displaystyle X_{1},\точки ,X_{м}}$

${\displaystyle {\overset {\{q\}}{\bigcup }}X_{i}=\bigcap ^{\{m-1-q\}}X_{i}}$

Обратите внимание, что когда q = 0, расслабленное объединение/пересечение соответствует классическому объединению/пересечению. Точнее, мы имеем

${\displaystyle \bigcap ^{\{0\}}X_{i}=\bigcap X_{i}}$

и

${\displaystyle {\overset {\{0\}}{\bigcup }}X_{i}=\bigcup X_{i}}$

Если обозначает дополнительный набор , то имеем${\displaystyle {\overline {X}}}$${\displaystyle X_{i}}$

${\displaystyle {\overline {\bigcap ^{\{q\}}X_{i}}}={\overset {\{q\}}{\bigcup }}{\overline {X_{i}}}}$

${\displaystyle {\overline {{\overset {\{q\}}{\bigcup }}X_{i}}}=\bigcap ^{\{q\}}{\overline {X_{i}}}.}$

Как следствие

${\displaystyle {\overline {\bigcap \limits ^{\{q\}}X_{i}}}={\overline {{\overset {\{m-q-1\}}{\bigcup }}X_{i}}}=\bigcap ^{\{m-q-1\}}{\overline {X_{i}}}}$

Пусть будет m подрядчиков для множеств , тогда${\displaystyle C_{1},\dots ,C_{m}}$ ${\displaystyle X_{1},\dots ,X_{m}}$

${\displaystyle C([x])=\bigcap ^{\{q\}}C_{i}([x]).}$

является подрядчиком и${\displaystyle X^{\{q\}}}$

${\displaystyle {\overline {C}}([x])=\bigcap ^{\{m-q-1\}}{\overline {C}}_{i}([x])}$

является подрядчиком для , где${\displaystyle {\overline {X}}^{\{q\}}}$

${\displaystyle {\overline {C}}_{1},\dots ,{\overline {C}}_{m}}$

являются подрядчиками для

${\displaystyle {\overline {X}}_{1},\dots ,{\overline {X}}_{m}.}$

В сочетании с алгоритмом ветвей и границ, таким как SIVIA (Set Inversion Via Interval Analysis), можно вычислить q -релаксированное пересечение m подмножеств .${\displaystyle R^{n}}$

Q -релаксированное пересечение можно использовать для надежной локализации ^{[3] [4]} или для отслеживания. ^[5]

Надежные наблюдатели также могут быть реализованы с использованием ослабленных пересечений, чтобы быть надежными по отношению к выбросам. ^[6]

Мы предлагаем здесь простой пример ^[7] для иллюстрации метода. Рассмотрим модель, выход i -й модели которой задается как

${\displaystyle f_{i}(p)={\frac {1}{\sqrt {2\pi p_{2}}}}\exp(-{\frac {(t_{i}-p_{1})^{2}}{2p_{2}}})}$

где . Предположим, что у нас есть${\displaystyle p\in R^{2}}$

${\displaystyle f_{i}(p)\in [y_{i}]}$

где и задаются следующим списком${\displaystyle t_{i}}$${\displaystyle [y_{i}]}$

${\displaystyle \{(1,[0;0.2]),(2,[0.3;2]),(3,[0.3;2]),(4,[0.1;0.2]),(5,[0.4;2]),(6,[-1;0.1])\}}$

Наборы для разных показаны на рисунке 4.${\displaystyle \lambda ^{-1}(q)}$${\displaystyle q}$