Intersección relajada

La intersección relajada de m conjuntos corresponde a la intersección clásica entre conjuntos, excepto que se permite relajar algunos conjuntos para evitar una intersección vacía. Esta noción se puede utilizar para resolver problemas de satisfacción de restricciones que son inconsistentes al relajar un pequeño número de restricciones . Cuando se considera un enfoque de error acotado para la estimación de parámetros , la intersección relajada permite ser robusto con respecto a algunos valores atípicos .

La intersección q -relajada de los m subconjuntos de , denotada por es el conjunto de todos los que pertenecen a todos los , excepto como máximo. Esta definición se ilustra en la Figura 1. ${\displaystyle X_{1},\puntos ,X_{m}}$$Estilo de visualización R^{n}}$${\displaystyle X^{\{q\}}=\bigcap ^{\{q\}}X_{i}}$${\displaystyle x\en R^{n}}$$Estilo de visualización X_{i}}$${\estilo de visualización q}$

Definir ${\displaystyle \lambda (x)={\text{tarjeta}}\left\{i\ |\ x\in X_{i}\right\}.}$

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

La caracterización de la intersección q-relajada es, por tanto, un problema de inversión de conjuntos . ^[1]

Consideremos 8 intervalos: $Estilo de visualización X_{1}=[1,4],}$ ${\displaystyle X_{2}=\ [2,4],}$ $Estilo de visualización X_{3}=[2,7],}$ $Estilo de visualización X_{4}=[6,9],}$ $Estilo de visualización X_{5}=[3,4],}$ ${\displaystyle X_{6}=[3,7].}$

Tenemos

${\displaystyle X^{\{0\}}=\conjunto vacío ,}$ ${\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 [.}$

La intersección relajada de intervalos no es necesariamente un intervalo. Por lo tanto, tomamos la envoltura de intervalos del resultado. Si son intervalos, la intersección relajada se puede calcular con una complejidad de m .log( m ) utilizando el algoritmo de Marzullo . Es suficiente ordenar todos los límites inferiores y superiores de los m intervalos para representar la función . Entonces, obtenemos fácilmente el conjunto $Estilo de visualización X_{i}}$${\estilo de visualización \lambda}$

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

que corresponde a una unión de intervalos. Luego devolvemos el intervalo más pequeño que contiene esta unión.

La figura 2 muestra la función asociada al ejemplo anterior. ${\displaystyle \lambda(x)}$

Para calcular la intersección q -relajada de m cajas de , proyectamos todas las m cajas con respecto a los n ejes. Para cada uno de los n grupos de m intervalos, calculamos la intersección q -relajada. Devolvemos el producto cartesiano de los n intervalos resultantes. ^[2] La Figura 3 proporciona una ilustración de la intersección 4-relajada de 6 cajas. Cada punto de la caja roja pertenece a 4 de las 6 cajas. $Estilo de visualización R^{n}}$

La unión q -relajada de se define por ${\displaystyle X_{1},\puntos ,X_{m}}$

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

Nótese que cuando q = 0, la unión/intersección relajada corresponde a la unión/intersección clásica. Más precisamente, tenemos

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

y

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

Si denota el conjunto complementario de , tenemos ${\displaystyle {\overline {X}}}$$Estilo de visualización 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}}}. }$

Como consecuencia

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

Sean m contratistas para los conjuntos , entonces ${\displaystyle C_{1},\puntos ,C_{m}}$ ${\displaystyle X_{1},\puntos ,X_{m}}$

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

es un contratista para y ${\displaystyle X^{\{q\}}}$

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

es un contratista para , donde ${\displaystyle {\overline {X}}^{\{q\}}}$

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

son contratistas para

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

Combinado con un algoritmo de ramificación y acotación como SIVIA (Set Inversion Via Interval Analysis), se puede calcular la intersección q -relajada de m subconjuntos de .${\displaystyle R^{n}}$

La intersección q -relajada se puede utilizar para localización robusta ^{[3] [4]} o para seguimiento. ^[5]

También se pueden implementar observadores robustos utilizando las intersecciones relajadas para que sean robustos con respecto a los valores atípicos. ^[6]

Proponemos aquí un ejemplo sencillo ^[7] para ilustrar el método. Consideremos un modelo cuya salida i -ésima viene dada por

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

donde . Supongamos que tenemos ${\displaystyle p\in R^{2}}$

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

donde y están dados por la siguiente lista ${\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])\}}$

Los conjuntos para los diferentes se representan en la Figura 4. ${\displaystyle \lambda ^{-1}(q)}$${\displaystyle q}$