Uvolněná křižovatka - Relaxed intersection - Wikipedia

The uvolněná křižovatka z m množiny odpovídá klasickému průsečíku mezi množinami kromě toho, že je povoleno uvolnit několik množin, aby se zabránilo prázdné křižovatce. tento pojem lze použít k řešení Omezuje problémy spokojenosti které jsou v rozporu s uvolnění malého počtu omezení.Když přístup s omezenou chybou je považován za odhad parametrů, uvolněná křižovatka umožňuje být vůči některým robustní odlehlé hodnoty.

Definice

The q-relaxovaná křižovatka m podmnožiny${ displaystyle X_ {1}, tečky, X_ {m}}$z ${ displaystyle R ^ {n}}$, označeno${ displaystyle X ^ { {q }} = bigcap ^ { {q }} X_ {i}}$je množina všech${ displaystyle x v R ^ {n}}$které patří všem${ displaystyle X_ {i}}$s výjimkou${ displaystyle q}$Tuto definici ilustruje obrázek 1.

Obrázek 1. q- průsečík 6 sad pro q= 2 (červená), q= 3 (zelená), q= 4 (modrá), q= 5 (žlutá).

Definovat${ displaystyle lambda (x) = { text {karta}} vlevo {i | x v X_ {i} vpravo }.}$

My máme${ displaystyle X ^ { {q }} = lambda ^ {- 1} ([m-q, m]).}$

Charakterizace Q-uvolněné křižovatky je tedy a nastavit inverzi problém.^[1]

Příklad

Zvažte 8 intervalů:${ 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].}$

My máme

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

Uvolněná křižovatka intervalů

Uvolněná křižovatka intervalů není nutný interval. Vezmeme tedy intervalový trup výsledku. Li ${ displaystyle X_ {i}}$Jsou to intervaly, uvolněnou křižovatku lze vypočítat se složitostí m.log (m) pomocí Marzullov algoritmus. Stačí roztřídit všechny dolní a horní meze m intervaly představující funkci ${ displaystyle lambda}$. Pak sadu snadno získáme

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

což odpovídá sjednocení intervalů. Potom vrátíme ten nejmenší interval, který toto sjednocení obsahuje.

Obrázek 2 ukazuje funkci${ displaystyle lambda (x)}$spojené s předchozím příkladem.

Obrázek 2. Funkce Set-Membership spojená s 6 intervaly.

Uvolněná křižovatka krabic

Vypočítat q-relaxovaná křižovatka m krabice${ displaystyle R ^ {n}}$, promítáme vše m krabice s ohledem na n osy. Pro každou z n skupiny m intervaly vypočítáme q-relaxovaná křižovatka. Vracíme kartézský součin n výsledné intervaly.^[2]Obrázek 3 poskytuje ilustraci 4-uvolněného průniku 6 polí. Každý bod tered boxu patří 4 ze 6 boxů.

Obrázek 3. Červený rámeček odpovídá 4-uvolněnému průsečíku 6 rámečků

Uvolněná unie

The q-relaxed union of ${ displaystyle X_ {1}, tečky, X_ {m}}$ je definováno

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

Všimněte si, že když q= 0, uvolněná unie / křižovatka odpovídá klasickému spojení / křižovatce. Přesněji, máme

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

a

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

De Morganův zákon

Li ${ displaystyle { overline {X}}}$ označuje doplňkovou sadu ${ displaystyle X_ {i}}$, my máme

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

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

Jako následek

${ displaystyle { overline { bigcap limity ^ { {q }} X_ {i}}} = { overline {{ nadměrné { {mq-1 }} { bigcup}} X_ {i }}} = bigcap ^ { {mq-1 }} { overline {X_ {i}}}}$

Uvolnění dodavatelů

Nechat ${ displaystyle C_ {1}, tečky, C_ {m}}$ být m dodavatelé pro sady ${ displaystyle X_ {1}, tečky, X_ {m}}$,pak

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

je dodavatelem společnosti ${ displaystyle X ^ { {q }}}$a

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

je dodavatelem společnosti ${ displaystyle { overline {X}} ^ { {q }}}$, kde

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

jsou dodavateli pro

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

V kombinaci s a rozvětvené a vázané algoritmus jako např SIVIA (Nastavit inverzi pomocí intervalové analýzy), q-relaxedintersection of m podmnožiny ${ displaystyle R ^ {n}}$ lze vypočítat.

Aplikace na odhad omezené chyby

The q-relaxovanou křižovatku lze použít pro robustní lokalizaci^[3][4]nebo pro sledování.^[5]

Robustní pozorovatelé mohou být také implementováni pomocí uvolněných křižovatek, aby byli robustní vzhledem k odlehlým hodnotám.^[6]

Navrhujeme zde jednoduchý příklad^[7]pro ilustraci metody. Zvažte model ijehož výstup je dán vztahem

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

kde ${ displaystyle p v R ^ {2}}$. Předpokládejme, že máme

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

kde ${ displaystyle t_ {i}}$ a ${ displaystyle [y_ {i}]}$ jsou uvedeny v následujícím seznamu

${ 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]) }}$

Sady ${ displaystyle lambda ^ {- 1} (q)}$ pro různé ${ displaystyle q}$ jsou zobrazeny na obrázku 4.

Obrázek 4. Sada všech vektorů parametrů v souladu s přesně 6-q datovými pruhy (červeně zbarvené), pro q = 1,2,3,4,5.

Reference