homología persistente - ix jornadas matemáticas - umss
Post on 18-Jul-2015
364 Views
Preview:
TRANSCRIPT
HomologíaPersistente
RolandoEspinoza
Introducción
ComplejosSimpliciales
HomologíaSimplicial
HomologíaPersistente
Experimentación
Conclusiones
Homología Persistente
Rolando Espinoza La fuentedarkrho@gmail.com
IX Jornadas MatemáticasCarrera de Ingeniería Matemática
FCyT – UMSS
28 de Noviembre 2014
1 / 68
HomologíaPersistente
RolandoEspinoza
Introducción
ComplejosSimpliciales
HomologíaSimplicial
HomologíaPersistente
Experimentación
Conclusiones
Introducción
Problema: Dado un conjunto finito A ⊂ Rd, llamado nube depuntos, muestra de un espacio topológico X ⊂ Rd,queremos estudiar las características topológicas de X soloutilizando la información de A.
X A
Figura 1: Ejemplo de un espacio X y una muestra A de X.
2 / 68
HomologíaPersistente
RolandoEspinoza
Introducción
ComplejosSimpliciales
HomologíaSimplicial
HomologíaPersistente
Experimentación
Conclusiones
Introducción
Estrategia: Representamos A como un complejo simplicialfiltrado, calculamos su homología persistente y estudiamosel código de barras asociado, que son la vida de los gruposde homología (y números de Betti) asociados a cadacomplejo simplicial en la filtración.
H0
H1
β0=9,β1=0 β0=1,β1=1 β0=1,β1=1 β0=1,β1=1 β0=1,β1=0
t0 t1 t2 t3 t4 t5
A1 A2 A3 A4 A5
⊂ ⊂ ⊂ ⊂
Figura 2: Una filtración de A y su respectivo código de barras.
3 / 68
HomologíaPersistente
RolandoEspinoza
Introducción
ComplejosSimpliciales
HomologíaSimplicial
HomologíaPersistente
Experimentación
Conclusiones
Primera ParteComplejos Simpliciales y Homología Simplicial
Complejos Simpliciales
4 / 68
HomologíaPersistente
RolandoEspinoza
Introducción
ComplejosSimpliciales
HomologíaSimplicial
HomologíaPersistente
Experimentación
Conclusiones
SimplicialesSimplex
DefiniciónUn simplex (o simpliciales) de dimensión k o k-simplex σ esla cápsula convexa de una colección de k + 1 puntosafínmente independientes.
0-simplicial 1-simplicial 2-simplicial 3-simplicial
Figura 3: k-simpliciales básicos.
5 / 68
HomologíaPersistente
RolandoEspinoza
Introducción
ComplejosSimpliciales
HomologíaSimplicial
HomologíaPersistente
Experimentación
Conclusiones
SimplicialesSimplex
Proposición(i) Todo k-simplex σ = 〈x0, . . . , xk〉 es la unión de los
segmentos que unen x0 con los puntos del simplexτ = 〈x1, . . . , xk〉.
(ii) Dado un simplex σ, existe uno y sólo un conjuntoafínmente independiente de puntos que lo generan. Esdecir, los vértices de un simplex quedan unívocamentedeterminados por el simplex.
6 / 68
HomologíaPersistente
RolandoEspinoza
Introducción
ComplejosSimpliciales
HomologíaSimplicial
HomologíaPersistente
Experimentación
Conclusiones
SimplicialesSimplex – Caras
DefiniciónSea σ = 〈x0, . . . , xk〉. Todo simplex generado por unsubconjunto no vacío de {x0, . . . , xk } se dice que es unacara (o faceta) de σ. Las caras de σ distintas de σ se llamancaras propias. Las caras inmediatas de σ son las carasgeneradas por k − 1 vértices de σ.
7 / 68
HomologíaPersistente
RolandoEspinoza
Introducción
ComplejosSimpliciales
HomologíaSimplicial
HomologíaPersistente
Experimentación
Conclusiones
SimplicialesSimplex – Caras
Figura 4: Caras inmediatas de un 3-simplex.
8 / 68
HomologíaPersistente
RolandoEspinoza
Introducción
ComplejosSimpliciales
HomologíaSimplicial
HomologíaPersistente
Experimentación
Conclusiones
Complejo Simplicial
DefiniciónUn complejo simplicial (geométrico) K, es un conjunto finitode simpliciales que cumplen:(i) Si σ ∈ K y τ es una cara de σ, entonces τ ∈ K.(ii) Si σ, τ ∈ K y σ ∩ τ 6= ∅, entonces σ ∩ τ es una cara de
σ y τ .
9 / 68
HomologíaPersistente
RolandoEspinoza
Introducción
ComplejosSimpliciales
HomologíaSimplicial
HomologíaPersistente
Experimentación
Conclusiones
Complejo Simplicial
(a) (b)
Figura 5: Ejemplo de un complejo simplicial (a) y un no complejo(b)
10 / 68
HomologíaPersistente
RolandoEspinoza
Introducción
ComplejosSimpliciales
HomologíaSimplicial
HomologíaPersistente
Experimentación
Conclusiones
Complejo Simplicial
TeoremaSea K un conjunto de simpliciales. Entonces K es uncomplejo simplicial si y sólo si:(i) Si σ ∈ K y τ es una cara de σ, entonces τ ∈ K.(ii) Para todo par σ, τ ∈ K, si σ 6= τ , entonces ◦σ ∩ ◦τ = ∅.
11 / 68
HomologíaPersistente
RolandoEspinoza
Introducción
ComplejosSimpliciales
HomologíaSimplicial
HomologíaPersistente
Experimentación
Conclusiones
Complejo Simplicial Abstracto
DefiniciónUn complejo simplicial abstracto K es un par (VK , SK)donde
VK es un conjunto finito de elementos llamados vérticesy,SK es una colección de subconjuntos finitos no vacíosde VK llamados símplices,
y satisfacen(i) cada elemento de VK pertenece a algún elemento de
SK y,(ii) si σ es un elemento en SK , entonces todo subconjunto
no vacío de σ también es un elemento de SK .
12 / 68
HomologíaPersistente
RolandoEspinoza
Introducción
ComplejosSimpliciales
HomologíaSimplicial
HomologíaPersistente
Experimentación
Conclusiones
Complejo Simplicial Abstracto
EjemploUn tetraedro sin el interior:
VK = { a, b, c, d }SK = {{ a } , { b } , { c } , { d } ,
{ a, b } , { a, c } , { a, d } , { b, c } , { b, d } , { c, d } ,{ a, b, c } , { a, b, d } , { a, c, d } , { b, c, d }}
13 / 68
HomologíaPersistente
RolandoEspinoza
Introducción
ComplejosSimpliciales
HomologíaSimplicial
HomologíaPersistente
Experimentación
Conclusiones
Realización Geométrica
Si K es un complejo simplicial geométrico en Rm, estedetermina un complejo simplicial abstracto tomando losvértices de K como conjunto de vértices del complejoabstracto.
Recíprocamente, si K es un complejo simplicial abstracto,este determina un complejo simplicial geométrico de lasiguiente manera:
Si n es la dimensión de K, elegimos un conjunto depuntos (uno por cada vértice deK en posición generalen Rm, con m ≥ 2n+ 1, y definimos por cada simplexabstracto de K el simplex geométrico que se obtienetomando la cápsula convexa de los puntos correspon-dientes al simplex.
14 / 68
HomologíaPersistente
RolandoEspinoza
Introducción
ComplejosSimpliciales
HomologíaSimplicial
HomologíaPersistente
Experimentación
Conclusiones
Realización Geométrica
a a a a
b b b
c c
d
{a} {a, b} {a, b, c} {a, b, c, d}
Figura 6: Correspondencia entre simpliciales geométricos yabstractos.
15 / 68
HomologíaPersistente
RolandoEspinoza
Introducción
ComplejosSimpliciales
HomologíaSimplicial
HomologíaPersistente
Experimentación
Conclusiones
Realización Geométrica
TeoremaUn complejo simplicial (abstracto) K de dimensión n tieneuna realización geométrica R2n+1.
16 / 68
HomologíaPersistente
RolandoEspinoza
Introducción
ComplejosSimpliciales
HomologíaSimplicial
HomologíaPersistente
Experimentación
Conclusiones
Lema del Nervio
DefiniciónSea F una colección finita de conjuntos. El nervio consisteen todas las subcolecciones cuya intersección de conjuntosno es vacía,
NrvF ={G ⊂ F :
⋂G 6= ∅
}.
17 / 68
HomologíaPersistente
RolandoEspinoza
Introducción
ComplejosSimpliciales
HomologíaSimplicial
HomologíaPersistente
Experimentación
Conclusiones
Lema del Nervio
ProposiciónEl nervio de F es un complejo simplicial abstracto.
U
V
Nervio
U
U∩VNervio
UU
V
NervioU
V
W
U∩V
U
V
WU∩W
V∩W
Figura 7: Construcciones de nervio del espacio S1.
18 / 68
HomologíaPersistente
RolandoEspinoza
Introducción
ComplejosSimpliciales
HomologíaSimplicial
HomologíaPersistente
Experimentación
Conclusiones
Lema del Nervio
Teorema (Lema del Nervio)Sea F una colección finita de conjuntos cerrados tal quecada intersección entre sus elementos es vacía o contraíble.Entonces NrvF tiene el mismo tipo de homotopía de
⋃F .
RemarcaSupongamos que queremos representar algún espaciotopológico X de manera combinatoria. Cubrimos X poralguna colección de conjuntos F y luego construimos sunervio.
19 / 68
HomologíaPersistente
RolandoEspinoza
Introducción
ComplejosSimpliciales
HomologíaSimplicial
HomologíaPersistente
Experimentación
Conclusiones
Lema del Nervio
'
Figura 8: Ilustración del Lema del Nervio.
20 / 68
HomologíaPersistente
RolandoEspinoza
Introducción
ComplejosSimpliciales
HomologíaSimplicial
HomologíaPersistente
Experimentación
Conclusiones
Construcción de Complejos Simpliciales
Estos son algunos complejos que han sido construidos paradiferentes aplicaciones:
Complejo de C̆echComplejo de Vietoris–RipsComplejo de Delaunay*Complejo Alpha*Complejo Witness*Complejo Inducido por Grafo*
21 / 68
HomologíaPersistente
RolandoEspinoza
Introducción
ComplejosSimpliciales
HomologíaSimplicial
HomologíaPersistente
Experimentación
Conclusiones
Complejo de C̆ech
C̆echS(r) = {σ ⊆ S : ∩x∈σ B(x, r) 6= ∅ }
Figura 9: Complejo de C̆ech.
22 / 68
HomologíaPersistente
RolandoEspinoza
Introducción
ComplejosSimpliciales
HomologíaSimplicial
HomologíaPersistente
Experimentación
Conclusiones
Complejo de Vietoris–Rips
VRipsS(r) = {σ ⊆ S : B(x, r) ∩B(y, r) 6= ∅, ∀x, y ∈ σ }
Figura 10: Complejo de Vietoris–Rips.
23 / 68
HomologíaPersistente
RolandoEspinoza
Introducción
ComplejosSimpliciales
HomologíaSimplicial
HomologíaPersistente
Experimentación
Conclusiones
Complejo de Vietoris–Rips
Teorema (Lema de Vietoris–Rips)Sea S un conjunto finito de puntos y r ≥ 0, entonces
C̆echS(r) ⊆ VRipsS(r) ⊆ C̆echS(√
2r).
RemarcaEl Complejo de C̆ech satisface el Lema del Nervio mientrasque el Complejo de Vietoris–Rips no.
24 / 68
HomologíaPersistente
RolandoEspinoza
Introducción
ComplejosSimpliciales
HomologíaSimplicial
HomologíaPersistente
Experimentación
Conclusiones
Complejo de Delaunay
El Complejo de Delaunay es isomorfo al nervio del diagramade Voronoi.
DelaunayS = {σ ⊆ S : ∩x∈σ Vx 6= ∅ } .
Figura 11: Complejo de Delaunay.
25 / 68
HomologíaPersistente
RolandoEspinoza
Introducción
ComplejosSimpliciales
HomologíaSimplicial
HomologíaPersistente
Experimentación
Conclusiones
Complejo Alpha
AlphaS(r) = {σ ⊆ S : ∩x∈σ {B(x, r) ∩ Vx} 6= ∅ } .
Figura 12: Complejo Alpha.
26 / 68
HomologíaPersistente
RolandoEspinoza
Introducción
ComplejosSimpliciales
HomologíaSimplicial
HomologíaPersistente
Experimentación
Conclusiones
Complejo Alpha
RemarcaEl complejo Alpha es isomorfo al nervio de las celdas deVoronoi.El complejo Alpha es un subcomplejo del complejo deDelaunay, y en consecuencia un subcomplejo delcomplejo de C̆ech.El complejo Alpha tiene el mismo tipo de homotopía quela unión de las bolas B(x, r).El complejo Alpha es muy utilizado en aplicacionesdurante los últimos años.
27 / 68
HomologíaPersistente
RolandoEspinoza
Introducción
ComplejosSimpliciales
HomologíaSimplicial
HomologíaPersistente
Experimentación
Conclusiones
Complejo Witness
Complejo desarrollado por Vin de Silva y GunnarCarlsson. Tiene una construcción más elaborada,enfocada en reducir la complejidad computacional alcalcular la homología persistente.De una muestra puntual A de un espacio métrico,tomamos una submuestra L ⊆ A y construimos elcomplejo sobre L en lugar de A.Dado un k-simplex σ con vértices L y unos puntosw ∈W , decimos que w es un α-testigo (witness) de σ silos vértices de σ estan dentro todos dentro dk(w) + α dew, donde dk(w) es la distancia de w a sus k + 1-ésimosvecinos más cercanos en L. Luego se hace unaexpansión de Vietoris–Rips.
28 / 68
HomologíaPersistente
RolandoEspinoza
Introducción
ComplejosSimpliciales
HomologíaSimplicial
HomologíaPersistente
Experimentación
Conclusiones
Complejo Inducido por Grafo
El complejo inducido por grafo, desarrollado por Dey,Fan y Wang, también utiliza la idea del submuestreo yes más útil para capturar la topología e inclusogeometría de una variedad.La ventaja sobre el complejo Witness es que estecomplejo no es necesariamente un subcomplejo delcomplejo de Delaunay y por lo tanto contiene mássimpliciales que ayudan en la inferencia de la topología.Dado el grafo vecindad de una nube de puntos Pequipado con una métrica, podemos construir sucomplejo inducido por un grafo en una submuestraQ ⊆ P armando un simplejo de un conjunto de vérticesV ⊆ Q si un conjunto de puntos en P , cada uno siendoel más cercano a un vértice de V , forman un clique (todopar de puntos en P estan conectados por una arista).
29 / 68
HomologíaPersistente
RolandoEspinoza
Introducción
ComplejosSimpliciales
HomologíaSimplicial
HomologíaPersistente
Experimentación
Conclusiones
Primera ParteComplejos Simpliciales y Homología Simplicial
Homología Simplicial
30 / 68
HomologíaPersistente
RolandoEspinoza
Introducción
ComplejosSimpliciales
HomologíaSimplicial
HomologíaPersistente
Experimentación
Conclusiones
Complejos de cadenas
Definición (simplicial orientado)Un simplicial orientado es una ordenación de los vértices delsimplicial. Dos simpliciales tienen la misma orientación si lapermutación de sus índices tiene signo positivo.
Definición (p-cadena)Sea K un complejo simplicial y p una dimensión. Unap-cadena c es la combinación lineal de simplicialesorientados, c =
∑aiσi donde σi son p-simpliciales
orientados y ai ∈ Z son coeficientes. DenotamosCp = Cp(K) al grupo de p-cadenas en K.
31 / 68
HomologíaPersistente
RolandoEspinoza
Introducción
ComplejosSimpliciales
HomologíaSimplicial
HomologíaPersistente
Experimentación
Conclusiones
Complejos de cadenas
Definición (operador frontera)Definimos el operador ∂p : Cp(K)→ Cp−1(K) por
∂p[v0, . . . , vp] =
p∑i=0
(−1)i[v0, . . . , v̂i, . . . , vp]
para un simplicial orientado [v0, . . . , vp].
ProposiciónPara cualquier λ, µ ∈ Z,
∂p(λx+ µy) = λ∂p(x) + µ∂p(y).
32 / 68
HomologíaPersistente
RolandoEspinoza
Introducción
ComplejosSimpliciales
HomologíaSimplicial
HomologíaPersistente
Experimentación
Conclusiones
Complejos de cadenas
∂2
v0
v1
v2 v0
v1
v2
Figura 13: Frontera de un simplicial.
33 / 68
HomologíaPersistente
RolandoEspinoza
Introducción
ComplejosSimpliciales
HomologíaSimplicial
HomologíaPersistente
Experimentación
Conclusiones
Complejos de cadenas
Ejemplo
∂2[v0, v1, v2] = [v1, v2]− [v0, v2] + [v0, v1]
∂1[v0, v1] = v1 − v0
Ejemplo
(∂1 ◦ ∂2)[v0, v1, v2] = ∂1[v1, v2]− ∂1[v0, v2] + ∂1[v0, v1]
= (v2 − v1)− (v2 − v0) + (v1 − v0)= 0
34 / 68
HomologíaPersistente
RolandoEspinoza
Introducción
ComplejosSimpliciales
HomologíaSimplicial
HomologíaPersistente
Experimentación
Conclusiones
Complejos de cadenas
Definición (complejo de cadenas)El complejo de cadenas es una secuencia de grupos decadenas conectados por homomorfismos de frontera.
· · · ∂p+2−→ Cp+1∂p+1−→ Cp
∂p−→ Cp−1∂p−1−→ · · ·
Teorema (Lema fundamental de la Homología)Para cada entero p ≥ 1, la composición
∂p ◦ ∂p+1 : Cp+1 → Cp
es el homomorfismo nulo.
35 / 68
HomologíaPersistente
RolandoEspinoza
Introducción
ComplejosSimpliciales
HomologíaSimplicial
HomologíaPersistente
Experimentación
Conclusiones
Ciclos y Fronteras
Definición (p-ciclo)Un p-ciclo c es una p-cadena con frontera vacía, es decir,∂ c = 0. Denotamos por Zp = Zp(K) al grupo de p-ciclos.
Definición (p-frontera)Una p-frontera c es una p-cadena que es una frontera de una(p+ 1)-cadena, es decir, c = ∂ d con d ∈ Cp+1. Denotamospor Bp = Bp(K) al grupo de fronteras.
ProposiciónSe tiene que Zp = Ker ∂p y Bp = Im ∂p+1.
36 / 68
HomologíaPersistente
RolandoEspinoza
Introducción
ComplejosSimpliciales
HomologíaSimplicial
HomologíaPersistente
Experimentación
Conclusiones
Ciclos y Fronteras
RemarcaTodo p-frontera es tambien un p-ciclo, o equivalentemente,Bp es un subgrupo de Zp.
Figura 14: La secuencia de complejos de cadena, ciclos y gruposde frontera conectados por homomorfismos.
37 / 68
HomologíaPersistente
RolandoEspinoza
Introducción
ComplejosSimpliciales
HomologíaSimplicial
HomologíaPersistente
Experimentación
Conclusiones
Grupos de Homología
DefiniciónLos p-ésimo grupos de homología es el p-ésimo grupo deciclos módulo el p-ésimo grupo de fronteras,
Hp = Zp/Bp.
El p-ésimo número de Betti es el rango del grupo,
βp = rangoHp.
38 / 68
HomologíaPersistente
RolandoEspinoza
Introducción
ComplejosSimpliciales
HomologíaSimplicial
HomologíaPersistente
Experimentación
Conclusiones
Grupos de Homología
EjemploEl círculo se puede representar como un complejo simplicialde dimensión 1 de vértices v0, v1, v2. Escogemos laorientación [v0, v1], [v1, v2], [v2, v0], entonces
∂1(c) = ∂1(λ0[v0, v1] + λ1[v1, v2] + λ2[v2, v0])
= λ0(v1 − v0) + λ1(v2 − v1) + λ2(v0 − v2)= (λ2 − λ0)v0 + (λ0 − λ1)v1 + (λ1 − λ2)v2.
es nulo si solo si λ0 = λ1 = λ2.
39 / 68
HomologíaPersistente
RolandoEspinoza
Introducción
ComplejosSimpliciales
HomologíaSimplicial
HomologíaPersistente
Experimentación
Conclusiones
Grupos de Homología
Ejemplo (cont’d)Por lo tanto
Ker ∂1 = {λ([v0, v1] + [v1, v2] + [v2, v0]) : λ ∈ Z } ≈ Z
Por otro lado, Im ∂2 = 0. Luego
H1(K) = Z1/B1 = Ker ∂1/ Im ∂2 ≈ Z.
40 / 68
HomologíaPersistente
RolandoEspinoza
Introducción
ComplejosSimpliciales
HomologíaSimplicial
HomologíaPersistente
Experimentación
Conclusiones
Grupos de Homología
Ejemplo (cont’d)Dado que ∂0 = 0, entonces Ker ∂0 ≈ Z3.Además
Im ∂1 = {µ0v0 + µ1v1 + µ2v2 : µ2 = −(µ0 + µ1) y µ0, µ1 ∈ Z }
Por lo tanto Im ∂1 ≈ Z2. Luego
H0(K) = Z0/B0 = Ker ∂0/ Im ∂1 ≈ Z
41 / 68
HomologíaPersistente
RolandoEspinoza
Introducción
ComplejosSimpliciales
HomologíaSimplicial
HomologíaPersistente
Experimentación
Conclusiones
Grupos de Homología
Ejemplo (cont’d)Concluimos que los grupos de homología del círculo son
H0(K) = Z,H1(K) = Z,Hp(K) = 0, p ≥ 2.
RemarcaPara complejos de dimensión mayor, el problema se reducea calcular el rango de la matriz asociada al homomorfismode frontera.
42 / 68
HomologíaPersistente
RolandoEspinoza
Introducción
ComplejosSimpliciales
HomologíaSimplicial
HomologíaPersistente
Experimentación
Conclusiones
Segunda ParteHomología Persistente y Experimentación
Homología Persistente
43 / 68
HomologíaPersistente
RolandoEspinoza
Introducción
ComplejosSimpliciales
HomologíaSimplicial
HomologíaPersistente
Experimentación
Conclusiones
Filtración
Definición (filtración)Sea K un complejo simplicial, una función f : K → Rmonótona creciente, es decir, f(σ) ≤ f(τ) si σ es una carade τ . Definimos el conjunto de nivel, K(a) = f−1(−∞, a], unsubcomplejo de K para cada a ∈ R. Sea m el número desimpliciales en K, obtenemos n+ 1 ≤ m+ 1 diferentessubcomplejos, que ordenamos como una secuenciacreciente
∅ ⊆ K0 ⊆ K1 ⊆ · · · ⊆ Kn = K.
Llamamos a esta secuencia de complejos una filtración de f .
44 / 68
HomologíaPersistente
RolandoEspinoza
Introducción
ComplejosSimpliciales
HomologíaSimplicial
HomologíaPersistente
Experimentación
Conclusiones
Filtración
Definición (aplicación de inclusión)Para cada i ≤ j definimos una aplicación de inclusión de elespacio subyacente Ki al espacio Kj
f i,jp : Hp(Ki)→ Hp(Kj),
para cada dimensión p.
RemarcaPor lo tanto a cada filtración le corresponde una secuenciade grupos de homología conectados por homomorfismos
0 = Hp(K0)f0,1p−→ Hp(K1)
f1,2p−→ · · · fn−1,np−→ Hp(Kn) = Hp(K),
para cada dimensión p.45 / 68
HomologíaPersistente
RolandoEspinoza
Introducción
ComplejosSimpliciales
HomologíaSimplicial
HomologíaPersistente
Experimentación
Conclusiones
Persistencia
Definición (Grupos de homología persistente)Los p-ésimo grupos de homología persistente son lasimágenes de los homomorfismos inducidos por la inclusión,H i,jp = Im f i,jp , para 0 ≤ i ≤ j ≤ n. Los correspondientes
p-ésimo números de Betti persistente son los rangos deestos grupos, βi,jp = rangoH i,j
p .
RemarcaNotese que H i,i
p = Hp(Ki) y H i,jp ⊆ Hp(Kj).
46 / 68
HomologíaPersistente
RolandoEspinoza
Introducción
ComplejosSimpliciales
HomologíaSimplicial
HomologíaPersistente
Experimentación
Conclusiones
Persistencia
Definición (nacimiento y muerte de clases)Sea γ una clase en Hp(Ki), decimos que nace en Ki siγ /∈ H i−1,i
p . Si γ nace en Ki entonces muere entrando en Kj
si se une con una clase anterior avanzando de Kj−1 a Kj , esdecir, f i,j−1p (γ) /∈ H i−1,j−1
p pero f i,jp (γ) ∈ H i−1,jp .
Figura 15: La clase γ nace en Ki y muere entrando en Kj .47 / 68
HomologíaPersistente
RolandoEspinoza
Introducción
ComplejosSimpliciales
HomologíaSimplicial
HomologíaPersistente
Experimentación
Conclusiones
Persistencia
Definición (persistencia)Si γ nace en Ki y muere entrando en Kj entonces llamamosa la diferencía, en el valor de la función, la persistencia,pers(γ) = aj − ai. A la diferencia de los índices j − illamamos el índice de persistencia. Si γ nace en Ki peronunca muere entonces su persistencia es infinito.
48 / 68
HomologíaPersistente
RolandoEspinoza
Introducción
ComplejosSimpliciales
HomologíaSimplicial
HomologíaPersistente
Experimentación
Conclusiones
Diagramas de persistencia
Definición (nacimiento y muerte de clases depersistencia)Definimos µi,jp el número de clases p-dimensionales nacidasen Ki y que mueren entrando en Kj , es decir,
µi,jp = (βi,j−1p − βi,jp )− (βi−1,j−1p − βi−1,jp ),
para todo i < j y todo p.
Definición (diagrama de persistencia)Dibujando cada punto (ai, aj) con multiplicidad µi,jp ,obtenemos el p-ésimo diagrama de persistencia de lafiltración, denotado por Dgmp(f).
49 / 68
HomologíaPersistente
RolandoEspinoza
Introducción
ComplejosSimpliciales
HomologíaSimplicial
HomologíaPersistente
Experimentación
Conclusiones
Diagramas de persistencia
(ai, aj)
ai
aj
Figura 16: Un diagrama de persistencia con un solo par (ai, aj).
50 / 68
HomologíaPersistente
RolandoEspinoza
Introducción
ComplejosSimpliciales
HomologíaSimplicial
HomologíaPersistente
Experimentación
Conclusiones
Diagramas de persistencia
Teorema (Lema fundamental de la HomologíaPersistente)Sea ∅ = K0 ⊆ K1 ⊆ · · · ⊆ Kn = K una filtración. Para cadapar de índices 0 ≤ k ≤ l ≤ n y cada dimensión p, el p-ésimonúmero de Betti persistente es
βk,lp = βk,np +∑i≤k
∑j>l
µi,jp .
RemarcaEl diagrama codifica toda la información de los grupos dehomología persistente.
51 / 68
HomologíaPersistente
RolandoEspinoza
Introducción
ComplejosSimpliciales
HomologíaSimplicial
HomologíaPersistente
Experimentación
Conclusiones
Espacio de Códigos de Barras
Definición (código de barras)Un código de barras es un conjunto finito de intervalosacotados por abajo. Para un diagrama de persistencia, losintervalos estan definidos por los pares (ai, aj).
H0
H1
β0=9,β1=0 β0=1,β1=1 β0=1,β1=1 β0=1,β1=1 β0=1,β1=0
t0 t1 t2 t3 t4 t5
A1 A2 A3 A4 A5
⊂ ⊂ ⊂ ⊂
Figura 17: Una filtración y su respectivo código de barras.
52 / 68
HomologíaPersistente
RolandoEspinoza
Introducción
ComplejosSimpliciales
HomologíaSimplicial
HomologíaPersistente
Experimentación
Conclusiones
Segunda ParteHomología Persistente y Experimentación
Casos de Estudio
Homología del ToroCuarteto de AnscombeFisher’s Iris Dataset
53 / 68
HomologíaPersistente
RolandoEspinoza
Introducción
ComplejosSimpliciales
HomologíaSimplicial
HomologíaPersistente
Experimentación
Conclusiones
Experimentación: Homología del Toro
−40 −30 −20 −10 0 10 20 30 40−10
−5
0 5
10
−40−30
−20−10
0 10
20 30
40
x
y
z
●●●
●
●● ●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●● ●●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●● ●
● ●
●
●
●
●
●● ●●●
● ●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
● ●
●
●
●
●
●
● ●
● ●
●
●
●
●
●● ●●●
●
●
●
●
●
●
●●
●
●
●
●
●
● ●
● ●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●
●
●
●●
●
● ●
● ●
●● ●●
● ●
● ●
●
●
●
●
●
●
●
●
●
●
●
●
● ●
● ●●
●
●
●●
●
●
●
●
●
●
●
●
●
● ●
● ●●
●
●
●
●
● ●
●
●
●
●
●●
●
●
●●
●●
● ●
●
● ●
● ●
● ●
● ●●
● ●
●
●
●
●
●●
●
●
●
●● ●●●
●
●
●
●
●
●
●
●
●
●
●
●
●● ●
● ●
●
●
●
●
●
●
●
●●
●
●
●
●
●
●
●
●
● ●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
● ●
●●
●
●
●●
●
●
●
●
●
●
●
●
●
● ●
● ●
●
●
●
●
●
●
●
●
●
● ●
●●
●
●
●
●
●
● ●
● ●
●
●
●
●
● ●
● ●●
● ●
●
●
●●
●
●
●
●
●
●
●
●
●
●
●
●● ●●●
●
●
●
●
●
●
●
●
● ●
●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●● ●
● ●
●
●
●
●
●
●●
● ●
●
●● ●
● ●● ●
●
●
●
●
●
●
●
●
●
● ●
●● ●
● ●
●
●
●
●
●
●
●
●
●
●
●
●
● ●
●
● ●
●
●
●
●
●
●
●
●
●
● ●
● ●
●
●
●
●
●
● ●
●
●
●
●
●
● ●
●
●
●
●
●
●
●
●
●
●
●
●
●
● ●
●
● ●
● ●●
●
●
●● ●
●
●
●
●
●
●
●
●
●
●
●
●●
●
●
●
●
●
●
●
●
● ●
●
●
●
●
●
●● ●●●
●
●
●●
● ●
●●
●
●
●
●
●
●
●
● ●
●
● ●
●
●
●
●
●
●
● ●
●
●
● ●
●
● ●
● ●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●
●
●
●
●
● ●
●●
●
●
●● ●
●
●
●
●●
●
●
●
●
●
●
●
●
● ●
●
●
●
●
●
●
●
●
●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●● ●
●
● ●
●●
●
●
●
●
●
●
●
●
●
●
●
●● ●●●
● ●
●
●
●
●
●
●
●
●
●●
●
●
●●
●
●
●●
●
●
●
●
●
●
●
●
● ●
●
●
●
●
●
●
●
●
●● ●
●
●
●
●
●
● ●
●●
●
●
●●
●
●
●
●
● ●
●●
● ●
●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●
●
●
●●
●
●
●
●
●
●
●● ●●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●
●
●
●
●
●
●
●
●
●
●
●●
●
●
●●
●●
●
●
●
●
●● ●
●●●
●●
●●●●●●●●
●●
●●●●●●●●●●●●●●●●●●
●●●●●●●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●●● ●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
● ●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●● ●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
● ●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
● ●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
● ●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●● ●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
● ●●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
● ●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
● ●
●
●
●
●
● ●
● ●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
● ●● ●
● ●●
●
●
●
●
● ●
● ●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●● ●●
●
●
●
●
● ●
● ●
● ●
● ●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●
●●
●
●
● ●
● ●
●●
● ●
●
●
●
●
●
●
●
●
●●
● ●
●
●
●
●
●
●
●
●
●
●
● ●
● ●
●●
● ●
●
●
●
●
●
●
●
●
● ●
●●
●
●
●
●
●
●
●
●
●
●
● ●
● ●
● ●
● ●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●● ●●
●
●
●
●
● ●
● ●
●
●
●
●
●
●
●
●
● ●
● ●
●
●
●
●
●
●
●
●
●
●
● ●
● ●
●
●
●
●
●
●
●
●
● ●
● ●
●
●
●
●
●
●
● ●
● ●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
● ●
● ●
●● ●●
●
●
●
●
●
●
●
●
●
●
● ●
● ●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
● ●
● ●
●
●
●
●
●
●
●
●
● ●
● ●
● ●
● ●
●
●
●
●
●
●
● ●
● ●
●
●
●
●●● ●●
●
●
●
●
●●
● ●
● ●
● ●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●● ●●
● ●
● ●
● ●
● ●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●
●●● ●●
●
●
●
●
●
●
●
●
●
●
● ●
●●
●
●
●●●●
●
●●●
Figura 18: Una nube de puntos sobre la superficie del Toro.
54 / 68
HomologíaPersistente
RolandoEspinoza
Introducción
ComplejosSimpliciales
HomologíaSimplicial
HomologíaPersistente
Experimentación
Conclusiones
Experimentación: Homología del Toro (cont’d)
0.00 0.78 1.56 2.34 3.12 3.90
H0
Figura 19: Código de barras correspondiente al grupo dehomología H0 del Toro.
55 / 68
HomologíaPersistente
RolandoEspinoza
Introducción
ComplejosSimpliciales
HomologíaSimplicial
HomologíaPersistente
Experimentación
Conclusiones
Experimentación: Homología del Toro (cont’d)
0.00 0.78 1.56 2.34 3.12 3.90
H1
Figura 20: Código de barras correspondiente al grupo dehomología H1 del Toro.
56 / 68
HomologíaPersistente
RolandoEspinoza
Introducción
ComplejosSimpliciales
HomologíaSimplicial
HomologíaPersistente
Experimentación
Conclusiones
Experimentación: Homología del Toro (cont’d)
0.00 0.78 1.56 2.34 3.12 3.90
H2
Figura 21: Código de barras correspondiente al grupo dehomología H2 del Toro.
57 / 68
HomologíaPersistente
RolandoEspinoza
Introducción
ComplejosSimpliciales
HomologíaSimplicial
HomologíaPersistente
Experimentación
Conclusiones
Experimentación: Homología del Toro (cont’d)
●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●
●
0 1 2 3 4
01
23
4
Persistence Diagram
Interval Start
Inte
rval
End
● 012
Figura 22: Diagrama de persistencia de la nube de puntos.
58 / 68
HomologíaPersistente
RolandoEspinoza
Introducción
ComplejosSimpliciales
HomologíaSimplicial
HomologíaPersistente
Experimentación
Conclusiones
Experimentación: El Cuarteto de Anscombe
2
4
6
8
10
12
14
y
dataset = I dataset = II
2 4 6 8 10 12 14 16 18 20x
2
4
6
8
10
12
14
y
dataset = III
2 4 6 8 10 12 14 16 18 20x
dataset = IV
Figura 23: El Cuarteto de Anscombe
59 / 68
HomologíaPersistente
RolandoEspinoza
Introducción
ComplejosSimpliciales
HomologíaSimplicial
HomologíaPersistente
Experimentación
Conclusiones
Experimentación: El Cuarteto de Anscombe(cont’d)
0.0 2.4 4.8 7.2 9.6 12.0
Dataset I − H0
0.0 2.4 4.8 7.2 9.6 12.0
Dataset I − H1
0.0 2.4 4.8 7.2 9.6 12.0
Dataset II − H0
0.0 2.4 4.8 7.2 9.6 12.0
Dataset III − H0
0.0 2.4 4.8 7.2 9.6 12.0
Dataset IV − H0
Figura 24: Códigos de barras asociados al Cuarteto de Anscombe60 / 68
HomologíaPersistente
RolandoEspinoza
Introducción
ComplejosSimpliciales
HomologíaSimplicial
HomologíaPersistente
Experimentación
Conclusiones
Experimentación: El Cuarteto de Anscombe(cont’d)
●●●●●●●●●●
●
0 2 4 6 8 10 120
24
68
12
Dataset I
Interval Start
Inte
rval
End
● 01
●●●●●●●●●●
●
0 2 4 6 8 10 12
02
46
812
Dataset II
Interval Start
Inte
rval
End
● 01
●●●●●●●●
●
●
●
0 2 4 6 8 10 12
02
46
812
Dataset III
Interval Start
Inte
rval
End
● 01 ●●●●●●
●●●
●●
0 2 4 6 8 10 120
24
68
12
Dataset IV
Interval Start
Inte
rval
End
● 01
Figura 25: Diagramas de persistencia asociados al Cuarteto deAnscombe
61 / 68
HomologíaPersistente
RolandoEspinoza
Introducción
ComplejosSimpliciales
HomologíaSimplicial
HomologíaPersistente
Experimentación
Conclusiones
Experimentación: Fisher’s Iris dataset
Figura 26: Matriz de dispersión del dataset Iris.
62 / 68
HomologíaPersistente
RolandoEspinoza
Introducción
ComplejosSimpliciales
HomologíaSimplicial
HomologíaPersistente
Experimentación
Conclusiones
Experimentación: Fisher’s Iris dataset (cont’d)
0.00 0.34 0.68 1.02 1.36 1.70
H0 Barcode for Iris Data
0.00 0.34 0.68 1.02 1.36 1.70
H1 Barcode for Iris Data
Figura 27: Códigos de barras del dataset Iris.
63 / 68
HomologíaPersistente
RolandoEspinoza
Introducción
ComplejosSimpliciales
HomologíaSimplicial
HomologíaPersistente
Experimentación
Conclusiones
Experimentación: Fisher’s Iris dataset (cont’d)
●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●●
●●
0.0 0.5 1.0 1.5
0.0
0.5
1.0
1.5
Persistence Diagram of Iris Data
Interval Start
Inte
rval
End
● 01
Figura 28: Diagrama de persistencia del dataset Iris.
64 / 68
HomologíaPersistente
RolandoEspinoza
Introducción
ComplejosSimpliciales
HomologíaSimplicial
HomologíaPersistente
Experimentación
Conclusiones
Conclusiones
Conclusiones
65 / 68
HomologíaPersistente
RolandoEspinoza
Introducción
ComplejosSimpliciales
HomologíaSimplicial
HomologíaPersistente
Experimentación
Conclusiones
Conclusiones
De manera general, el método se aplica de la siguientemanera:
1 obtenemos los datos a analizar;2 asociamos una estructura topológica para generar una
filtración de complejos simpliciales;3 estudiamos las propiedades topológicas mediante la
homología persistente;4 intepretamos las propiedes topológicas: ¿qué significa
tener agujeros de dimensión 2 en nuestros datos? ¿haydiferencias topológicas entre dos conjuntos datos? ¿cómo la evolucación de las propiedades topológicos enel tiempo?
66 / 68
HomologíaPersistente
RolandoEspinoza
Introducción
ComplejosSimpliciales
HomologíaSimplicial
HomologíaPersistente
Experimentación
Conclusiones
Conclusiones (cont’d)
No siempre se pueden sacar conclusiones directas delcódigo de barras y diagrama de persistencia cuandoaplicamos el método a un conjunto de datos reales.Es necesario complementar con otras técnicasadicionales de análisis de datos, por ejempo: análisismultivariante, reconocimiento de patrones, aprendizajeautomático, etc.
67 / 68
HomologíaPersistente
RolandoEspinoza
Introducción
ComplejosSimpliciales
HomologíaSimplicial
HomologíaPersistente
Experimentación
Conclusiones
Gracias por su atención.
68 / 68
top related