ε-сеть (вычислительная геометрия)

В вычислительной геометрии ε- сеть ( произносится как эпсилон -сеть) — это аппроксимация общего множества набором более простых подмножеств. В теории вероятностей это аппроксимация одного распределения вероятностей другим.

Пусть X — множество, а R — множество подмножеств X ; такая пара называется пространством диапазонов или гиперграфом , а элементы R называются диапазонами или гиперребрами . ε-сеть подмножества P множества X — это подмножество N множества P , такое что любой диапазон r  ∈ R с | r  ∩  P | ≥  ε | P | пересекает  N . ^[1] Другими словами, любой диапазон, пересекающий по крайней мере часть ε элементов P, должен также пересекать ε -сеть  N .

Например, предположим, что X — это множество точек на двумерной плоскости, R — множество замкнутых заполненных прямоугольников (произведения замкнутых интервалов), а P — единичный квадрат [0, 1] × [0, 1]. Тогда множество N, состоящее из 8 точек, показанных на соседней диаграмме, является 1/4-сеткой P, поскольку любой замкнутый заполненный прямоугольник, пересекающий по крайней мере 1/4 единичного квадрата, должен пересекать одну из этих точек. Фактически, любой (параллельный оси) квадрат, независимо от размера, будет иметь похожую 8-точечную 1/4-сетку.

Для любого пространства диапазонов с конечной размерностью VC d , независимо от выбора P, существует ε-сеть P размера

${\displaystyle O\left({\frac {d}{\varepsilon }}\log {\frac {d}{\varepsilon }}\right)\!;}$^[1]

Поскольку размер этого множества не зависит от P , любое множество P можно описать с помощью множества фиксированного размера.

Это облегчает разработку эффективных алгоритмов аппроксимации . Например, предположим, что мы хотим оценить верхнюю границу площади заданной области, которая попадает внутрь конкретного прямоугольника P. Можно оценить это с точностью до аддитивного множителя ε, умноженного на площадь P , сначала найдя ε -сеть P , подсчитав долю элементов в ε-сети, попадающих внутрь области относительно прямоугольника P , а затем умножив на площадь  P. Время выполнения алгоритма зависит только от ε , а не от  P. Один простой способ вычислить ε-сеть с высокой вероятностью — взять достаточное количество случайных точек, где количество случайных точек также зависит только от  ε . Например, на показанной диаграмме любой прямоугольник в единичном квадрате, содержащий не более трех точек в 1/4-сети, имеет площадь не более 3/8 + 1/4 = 5/8.

ε-сети также предоставляют алгоритмы аппроксимации для NP-полных задач попадания и покрытия множеств . ^[2]

Пусть будет распределением вероятностей по некоторому множеству . Сеть для класса подмножеств — это любое подмножество такое, что для любого${\displaystyle P}$${\displaystyle X}$${\displaystyle \varepsilon}$${\displaystyle H\subseteq 2^{X}}$${\displaystyle X}$${\displaystyle S\subseteq X}$${\displaystyle h\in H}$

${\displaystyle P(h)\geq \varepsilon \quad \Longrightarrow \quad S\cap h\neq \varnothing.}$

Интуитивно аппроксимирует распределение вероятностей.${\displaystyle S}$

Более сильным понятием является -аппроксимация. -аппроксимация для класса - это подмножество, такое что для любого оно выполняется${\displaystyle \varepsilon}$${\displaystyle \varepsilon}$${\displaystyle H}$${\displaystyle S\subseteq X}$${\displaystyle h\in H}$

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