ε-net (beräkningsgeometri)

Ett ε -net (uttalas epsilon -net) i beräkningsgeometri är approximationen av en generell mängd av en samling enklare delmängder. I sannolikhetsteorin är det approximationen av en sannolikhetsfördelning av en annan.

Bakgrund

Ett ε-net med ε = 1/4 av enhetskvadraten i intervallutrymmet där intervallen är slutna fyllda rektanglar.

Låt X vara en mängd och R vara en mängd delmängder av X ; ett sådant par kallas avståndsutrymme eller hypergraf , och elementen i R kallas intervall eller hyperkanter . Ett ε-net av en delmängd P av X är en delmängd N av P så att vilket område som helst r ∈ R med | r ∩ P | ≥ ε | P | skär N . Med andra ord, varje område som skär åtminstone en andel ε av elementen i P måste också skära ε -net N .

Anta till exempel att X är mängden punkter i det tvådimensionella planet, R är mängden slutna fyllda rektanglar (produkter av slutna intervall) och P är kvadraten [0, 1] × [0, 1]. Då är mängden N som består av de 8 punkterna som visas i det intilliggande diagrammet en 1/4-netto av P, eftersom varje sluten fylld rektangel som skär minst 1/4 av enhetens kvadrat måste skära en av dessa punkter. Faktum är att varje (axelparallell) kvadrat, oavsett storlek, kommer att ha ett liknande 8-punkts 1/4-net.

För varje avståndsutrymme med ändlig VC-dimension d , oavsett valet av P, finns det ett ε-net av P av storlek

O\left({\frac {d}{\varepsilon }}\log {\frac {d}{\varepsilon }}\right)\!;

eftersom storleken på denna uppsättning är oberoende av P , kan vilken uppsättning P som helst beskrivas med en uppsättning med fast storlek.

Detta underlättar utvecklingen av effektiva approximationsalgoritmer . Anta till exempel att vi vill uppskatta en övre gräns för arean av en given region, som faller inuti en viss rektangel P . Man kan uppskatta detta till en additiv faktor på ε gånger arean av P genom att först hitta ett ε -net av P , räkna andelen element i ε-nettet som faller inom området med avseende på rektangeln P , och sedan multiplicera av området P . Algoritmens körtid beror endast på ε och inte P . Ett enkelt sätt att beräkna ett ε-nät med hög sannolikhet är att ta ett tillräckligt antal slumpmässiga punkter, där antalet slumpmässiga punkter också bara beror på ε . Till exempel, i det visade diagrammet, har varje rektangel i enhetskvadraten som innehåller högst tre punkter i 1/4-net en area på högst 3/8 + 1/4 = 5/8.

ε-nät tillhandahåller också approximationsalgoritmer för NP-komplett träffuppsättning och set täckningsproblem .

Sannolikhetsteori

Låt $P$ vara en sannolikhetsfördelning över någon mängd $X$ . Ett $\varepsilon$ -net för en klass $H\subseteq 2^{X}$ av delmängder av $X$ är vilken delmängd som helst $S\subseteq X$ så att för någon $h\in H$

P(h)\geq \varepsilon \quad \Longrightarrow \quad S\cap h\neq \varnothing .

Intuitivt approximerar $S$ sannolikhetsfördelningen.

En starkare föreställning är $\varepsilon$ -approximation. En $\varepsilon$ -approximation för klass $H$ är en delmängd $S\subseteq X$ så att den för varje $h\in H$ gäller

\left|P(h)-{\frac {|S\cap h|}{|S|}}\right|<\varepsilon .