MATHS + AI

Topología aplicada · Tema 04

Estabilidad

Si los datos cambian poco, el diagrama cambia poco: la homología persistente es estable, y por eso tiene sentido aplicarla a datos reales.

Distancia bottleneck
Distancias de Wasserstein
Teoremas de estabilidad

Avanza con → espacio · retrocede con ← · índice con O · pantalla completa con F

Hoja de ruta

La estabilidad relaciona la distancia entre datos con la distancia entre diagramas

datos
$\|f-g\|_\infty\le\varepsilon$ o $d_H(P,Q)\le\varepsilon$

estabilidad

diagramas
$d_B\le\varepsilon$

Objetivo del capítulo

Establecer que dato $\mapsto$ diagrama es 1-lipschitziana: hay que medir cuánto difieren dos datos y cuánto difieren dos diagramas.

Resultados de aprendizaje

Al terminar, debemos poder responder tres preguntas

¿Cómo se mide la distancia entre dos diagramas de persistencia (bottleneck y Wasserstein)?
¿Qué afirma el teorema de estabilidad para funciones y qué consecuencias tiene frente al ruido?
¿Qué garantiza la estabilidad para nubes de puntos, y qué no garantiza?

Hilo conductor: los puntos alejados de la diagonal sobreviven a las perturbaciones pequeñas; el ruido solo puede crear o destruir puntos próximos a ella.

Motivación

Los datos nunca son exactos

Medidas con error, ruido del sensor, muestras finitas. Si el diagrama pudiera cambiar de forma arbitraria con una perturbación pequeña, no diría nada fiable sobre el objeto estudiado.

Las dos respuestas típicas que obtendremos

Si $f,g$ son funciones sobre un mismo complejo con $\|f-g\|_\infty\le\varepsilon$, sus diagramas están a distancia bottleneck a lo sumo $\varepsilon$.
Si dos nubes $P,Q$ cumplen $d_H(P,Q)\le\varepsilon$, los diagramas de sus filtraciones de Čech y de Vietoris–Rips están a distancia bottleneck a lo sumo $\varepsilon$.

Consecuencia: justifica la lectura de los diagramas del tema 3.

01

Sección primera

Distancias entre diagramas

Diagramas y diagonal, distancia de un punto a la diagonal, distancia bottleneck y distancias de Wasserstein.

Distancias entre diagramas

Un diagrama es un multiconjunto de puntos del plano extendido

Definición (diagrama de persistencia)

Un multiconjunto finito $D$ de puntos $x=(b,d)\in\overline{\R}^2=\R\times(\R\cup\{+\infty\})$ con $b<d$. Los puntos con $d=+\infty$ son esenciales, y la persistencia de $x$ es $\pers(x)=d-b\in(0,+\infty]$.

Entre puntos, la norma del máximo: $\|x-y\|_\infty=\max\{|b-b'|,|d-d'|\}$, con $|(+\infty)-(+\infty)|=0$ y $|d-(+\infty)|=+\infty$ si $d\in\R$.

Diagonal: a todo diagrama se le añade $\Delta=\{(a,a):a\in\R\}$ con multiplicidad infinita, como pareja de los puntos sin correspondiente.

Distancias entre diagramas

La distancia de un punto a la diagonal es la mitad de su persistencia

Lema (distancia a la diagonal)

Si $x=(b,d)$ es finito, \[ \inf_{a\in\R}\|x-(a,a)\|_\infty=\frac{\pers(x)}{2}, \] alcanzado solo en $a=\frac{b+d}{2}$. Si $x$ es esencial, la distancia es $+\infty$.

Lectura: un rasgo efímero desaparece con una perturbación pequeña; uno persistente, solo pagando un coste grande.

Distancias entre diagramas

La distancia bottleneck mide la peor pareja del mejor emparejamiento

Definición (distancia bottleneck)

Un emparejamiento entre $D$ y $E$ es una biyección $\gamma:D\cup\Delta\to E\cup\Delta$, con la diagonal contada con multiplicidad infinita en ambos lados. \[ d_B(D,E)=\inf_{\gamma}\ \sup_{x\in D\cup\Delta}\|x-\gamma(x)\|_\infty. \]

«Cuello de botella»: de cada emparejamiento solo cuenta su pareja más costosa.
Para cada punto solo hay que decidir: pareja en el otro diagrama, o la diagonal (coste $\tfrac12\pers(x)$).

Distancias entre diagramas

El cálculo se reduce a un problema finito

Definición (emparejamiento parcial)

Conjunto $M$ de pares $(x,y)\in D\times E$ en los que cada punto aparece a lo sumo una vez; los demás son libres. \[ c(M)=\max\Bigl(\bigl\{\|x-y\|_\infty:(x,y)\in M\bigr\}\cup\bigl\{\tfrac12\pers(z):z\text{ libre}\bigr\}\Bigr). \]

Lema

$d_B(D,E)=\min_M c(M)$, un mínimo sobre una cantidad finita de emparejamientos parciales. Es finita si y solo si $D$ y $E$ tienen el mismo número de puntos esenciales.

$d_B$ es una distancia (que puede valer $+\infty$), y se calcula en tiempo polinómico.

Distancias entre diagramas

Ejemplo: cálculo de una distancia bottleneck

\[ \begin{aligned} D&=\{(0,+\infty),\,(1,5),\,(6,8)\},\\ E&=\{(0{,}3;\,+\infty),\,(1{,}4;\,5{,}2),\,(9,10)\}. \end{aligned} \]

Esenciales entre sí: coste $0{,}3$. Costes de los puntos finitos:

\[ \begin{array}{c|cc|c} & (1{,}4;\ 5{,}2) & (9,10) & \Delta \\ \hline (1,5) & 0{,}4 & 8 & 2 \\ (6,8) & 4{,}6 & 3 & 1 \\ \hline \Delta & 1{,}9 & 0{,}5 & \end{array} \]

$M=\{((1,5),(1{,}4;\,5{,}2))\}$ deja libres $(6,8)$ y $(9,10)$: $c(M)=\max\{0{,}4;\,1;\,0{,}5\}=1$, y ninguno es mejor. Luego $d_B(D,E)=\max\{0{,}3;\,1\}=1$.

Distancias entre diagramas

Un emparejamiento óptimo, dibujado

Continuas: parejas; discontinuas: envío a la diagonal (más barato que emparejar $(6,8)$ con $(9,10)$). Los cuadrados de lado $2d_B=2$ centrados en los puntos finitos de $D$ contienen su pareja.

Distancias entre diagramas

Las distancias de Wasserstein acumulan todos los costes

La bottleneck solo ve la peor pareja; las de Wasserstein suman todos los costes (transporte óptimo).

Definición (distancia de Wasserstein de orden $q$, $1\le q<\infty$)

\[ d_{W,q}(D,E)=\inf_{\gamma}\Bigl(\sum_{x\in D\cup\Delta}\|x-\gamma(x)\|_\infty^{\,q}\Bigr)^{1/q}, \] y, como antes, es un mínimo sobre los emparejamientos parciales $M$: se suman las potencias $q$ de los costes $\|x-y\|_\infty$ de los pares y $\tfrac12\pers(z)$ de los puntos libres, y se toma la raíz $q$-ésima.

Distancias entre diagramas

Bottleneck frente a Wasserstein

Proposición

Para $1\le q\le q'<\infty$: $\ d_B\le d_{W,q'}\le d_{W,q}\ $ y $\ \lim_{q\to\infty}d_{W,q}=d_B$.

El ejemplo anterior

Costes $0{,}3$, $0{,}4$, $1$ y $0{,}5$: \[ \begin{gathered} d_B=1\le d_{W,2}\approx1{,}22\\ \le d_{W,1}=2{,}2. \end{gathered} \]

Acumulación de ruido

$N$ puntos de persistencia $2\varepsilon$ frente a $\varnothing$: \[ d_B=\varepsilon,\qquad d_{W,q}=N^{1/q}\varepsilon. \]

Ninguna es mejor: peor rasgo frente a cantidad total de diferencias.

02

Sección segunda

Estabilidad para funciones

El teorema de estabilidad, la cota alcanzada, la supervivencia de los rasgos persistentes y el caso de Wasserstein.

Estabilidad para funciones

Perturbar la función en $\varepsilon$ mueve el diagrama a lo sumo $\varepsilon$

$\Dgm_p(f)$: diagrama de la filtración de subnivel $K_t=f^{-1}\bigl((-\infty,t]\bigr)$, y $\|f-g\|_\infty=\max_{\sigma\in K}|f(\sigma)-g(\sigma)|$.

Teorema (estabilidad para funciones monótonas)

Si $f,g:K\to\R$ son monótonas sobre un complejo finito, para todo $p\ge0$ \[ d_B\bigl(\Dgm_p(f),\Dgm_p(g)\bigr)\le\|f-g\|_\infty. \]

Cohen-Steiner, Edelsbrunner y Harer.
Imágenes (estrella inferior): $d_B\le$ error máximo por píxel.

Estabilidad para funciones

Ejemplo: la cota puede alcanzarse

Sobre el camino $a$—$b$—$c$:

\[ \begin{array}{c|ccccc} \sigma & a & b & ab & c & bc \\ \hline f(\sigma) & 0 & 2 & 3 & 4 & 5 \\ g(\sigma) & 0{,}2 & 1{,}8 & 3{,}4 & 4{,}3 & 4{,}8 \end{array} \qquad \|f-g\|_\infty=0{,}4. \]

El máximo se alcanza en $ab$. Pares $(b,ab)$ y $(c,bc)$; $a$ es esencial:

\[ \begin{aligned} \Dgm_0(f)&=\{(0,+\infty),\,(2,3),\,(4,5)\},\\ \Dgm_0(g)&=\{(0{,}2;\,+\infty),\,(1{,}8;\,3{,}4),\,(4{,}3;\,4{,}8)\}. \end{aligned} \]

Costes $0{,}2$, $0{,}4$ y $0{,}3$; las alternativas son peores. Así $d_B=0{,}4=\|f-g\|_\infty$: la cota es óptima.

Estabilidad para funciones

Los rasgos de persistencia mayor que $2\varepsilon$ sobreviven al ruido

Corolario (supervivencia de los rasgos persistentes)

Si $d_B(D,E)\le\varepsilon$, cada $x=(b,d)\in D$ con $\pers(x)>2\varepsilon$ tiene un correspondiente $y=(b',d')\in E$, distinto para cada $x$, con \[ |b-b'|\le\varepsilon,\qquad |d-d'|\le\varepsilon,\qquad \pers(y)\ge\pers(x)-2\varepsilon>0. \]

Estabilidad para funciones

Wasserstein no es estable respecto de la norma uniforme

$f\equiv0$ y $g(x)=\varepsilon\cos(2\pi Nx)$ sobre $[0,1]$: $\|f-g\|_\infty=\varepsilon$.

$\Dgm_0(f)$ (círculo) y $\Dgm_0(g)=\{(-\varepsilon,+\infty)\}\cup\{(-\varepsilon,\varepsilon)\}^{N-1}$ (cuadrados).

\[ d_B=\varepsilon\ \text{ para todo } N,\qquad d_{W,q}=N^{1/q}\varepsilon\xrightarrow[N\to\infty]{}\infty. \]

No hay ninguna cota de $d_{W,q}$ en términos de $\|f-g\|_\infty$ válida para todas las funciones.

Estabilidad para funciones

Dos maneras de recuperar la estabilidad de Wasserstein

Teorema (Skraba y Turner): medir con una norma que acumule

Si $f,g:K\to\R$ son monótonas y $1\le q<\infty$, $\ d_{W,q}\bigl(\Dgm_p(f),\Dgm_p(g)\bigr)\le\|f-g\|_q=\bigl(\sum_{\sigma\in K}|f(\sigma)-g(\sigma)|^q\bigr)^{1/q}$.

Teorema (Cohen-Steiner, Edelsbrunner, Harer y Mileyko): funciones lipschitzianas

$X$ compacto triangulable con triangulaciones de crecimiento polinómico; $f,g$ lipschitzianas y dóciles. Existen $C$ y $k\ge1$, según $X$ y las constantes de Lipschitz, con un exponente $1-k/q<1$ (más débil): \[ d_{W,q}\bigl(\Dgm_p(f),\Dgm_p(g)\bigr)\le C\,\|f-g\|_\infty^{\,1-k/q}\qquad(q\ge k). \]

03

Sección tercera

Estabilidad para nubes de puntos

Distancia de Hausdorff, estabilidad de Čech y de Vietoris–Rips, un ejemplo con datos y distancia de Gromov–Hausdorff.

Nubes de puntos

La distancia de Hausdorff compara las propias nubes

Definición (distancia de Hausdorff)

\[ d_H(A,B)=\max\Bigl\{\sup_{a\in A}d(a,B),\ \sup_{b\in B}d(b,A)\Bigr\}. \] Equivale al menor $r\ge0$ con $A\subseteq B^r$ y $B\subseteq A^r$ (engrosamientos de radio $r$).

$d_H\le\varepsilon$ si cada punto está a distancia $\le\varepsilon$ de la otra nube. Aquí $d_H(P,Q)=d(q_7,p_6)$.

Nubes de puntos

Mover la nube $\varepsilon$ en Hausdorff mueve el diagrama a lo sumo $\varepsilon$

Teorema (estabilidad de las filtraciones de nubes de puntos)

Si $P,Q$ son finitos en un espacio métrico, para todo $p\ge0$ \[ d_B\bigl(\Dgm_p(\mathcal{VR}(P)),\Dgm_p(\mathcal{VR}(Q))\bigr)\le d_H(P,Q). \] En $\R^n$, lo mismo para Čech y alpha.

No depende del número de puntos ni de la dimensión.

Nubes de puntos

Un ejemplo con datos: una muestra perturbada de una circunferencia

$40$ puntos sobre $\mathbb S^1$, cada uno desplazado menos de $0{,}15$: $d_H(P,Q)\approx0{,}147$.

Nube P de 40 puntos sobre la circunferencia unidad, con círculos, y su perturbación Q, con triángulos; la distancia de Hausdorff es 0,147

Diagramas de H0 de las filtraciones de Vietoris–Rips de P y de Q, todos los puntos con nacimiento 0; distancia bottleneck 0,045

Diagramas de H1: P tiene un punto en (0,340; 0,871) y Q uno en (0,334; 0,797) y otro, efímero, junto a la diagonal; distancia bottleneck 0,074

$d_B=0{,}045$ en $H_0$ y $0{,}074$ en $H_1$, ambas $\le d_H$. En $H_1$, el ciclo pasa de $(0{,}340;\,0{,}871)$ a $(0{,}334;\,0{,}797)$.

Nubes de puntos

Sin un ambiente común: la distancia de Gromov–Hausdorff

Redes, moléculas, formas: espacios métricos finitos sin coordenadas comunes.

Definición (distancia de Gromov–Hausdorff)

Para correspondencias $C\subseteq X\times Y$ (todo punto aparece en algún par): \[ d_{GH}(X,Y)=\tfrac12\min_C\ \max_{(x,y),(x',y')\in C}|d_X(x,x')-d_Y(y,y')|. \]

Teorema (Chazal, Cohen-Steiner, Guibas, Mémoli y Oudot)

\[ d_B\bigl(\Dgm_p(\mathcal{VR}(X)),\Dgm_p(\mathcal{VR}(Y))\bigr)\le d_{GH}(X,Y). \]

Síntesis

Resumen de los teoremas (cotas en cada dimensión $p$)

Datos	Perturbación	Filtración	Garantía
función monótona en $K$	$\\|f-g\\|_\infty$	subnivel	$d_B\le\\|f-g\\|_\infty$
función monótona en $K$	$\\|f-g\\|_q$	subnivel	$d_{W,q}\le\\|f-g\\|_q$
imagen, campo escalar	error máximo por píxel	estrella inferior	$d_B\le$ error máximo
nube en $\R^n$	$d_H(P,Q)$	Čech, alpha	$d_B\le d_H(P,Q)$
nube en un espacio métrico	$d_H(P,Q)$	Vietoris–Rips	$d_B\le d_H(P,Q)$
espacio métrico finito	$d_{GH}(X,Y)$	Vietoris–Rips	$d_B\le d_{GH}(X,Y)$

Síntesis

Qué garantiza la estabilidad, y qué no

Garantiza

Errores pequeños, cambios pequeños.
Los rasgos de persistencia $>2\varepsilon$ sobreviven al ruido.
Muestras más densas, diagramas convergentes.
Se hereda: paisajes e imágenes de persistencia.

No garantiza

Es continuidad, no significación.
No dice cuál es el nivel de ruido $\varepsilon$.
$d_H$ es sensible a valores atípicos.
$d_B$ ignora la acumulación de discrepancias.

Autoevaluación

Preguntas para comprobar la comprensión

¿Por qué la distancia de un punto a la diagonal es la mitad de su persistencia, y qué papel tiene en $d_B$?
¿Por qué es infinita la distancia bottleneck entre diagramas con distinto número de puntos esenciales?
Si cada píxel de una imagen se mide con error $\le0{,}02$, ¿qué puede afirmarse de las barras observadas de longitud mayor que $0{,}04$? ¿Y de las de longitud menor?
¿Por qué no puede haber una cota de $d_{W,q}$ que dependa solo de $\|f-g\|_\infty$?

Topología aplicada · Tema 04

Si los datos se mueven $\varepsilon$, el diagrama se mueve a lo sumo $\varepsilon$.

Lo que persiste más de $2\varepsilon$ sobrevive al ruido.