View
1
Download
0
Category
Preview:
Citation preview
TECNICAS INTELIGENTES EN BIOINFORMATICA
Modelos graficos probabilısticosRedes Bayesianas y Modelos ocultos de Markov
Carmen Graciani DıazMario de J. Perez Jimenez
Luis Valencia CabreraGrupo de investigacion en Computacion Natural
Dpto. Ciencias de la Computacion e Inteligencia ArtificialUniversidad de Sevilla
Master Universitario en Logica, Computacion e Inteligencia Artificial
Curso 2015-2016
Contents
Conceptos preliminaresRepaso de Teorıa de grafosRepaso de Probabilidad
Redes bayesianas
Cadenas de Markov
Modelos ocultos de Markov
2 / 132
Contents
Conceptos preliminaresRepaso de Teorıa de grafosRepaso de Probabilidad
Redes bayesianas
Cadenas de Markov
Modelos ocultos de Markov
3 / 132
Grafos
4 / 132
Grafos
5 / 132
Grafos
6 / 132
Grafos
7 / 132
Grafos
8 / 132
Grafos
9 / 132
Grafos
10 / 132
Grafos
11 / 132
Grafos
12 / 132
Contents
Conceptos preliminaresRepaso de Teorıa de grafosRepaso de Probabilidad
Redes bayesianas
Cadenas de Markov
Modelos ocultos de Markov
13 / 132
Eventos
14 / 132
Variables aleatorias discretas: ejemplo
15 / 132
Espacio de eventos: ejemplo
16 / 132
Eventos: ejemplo
17 / 132
Probabilidades
18 / 132
Propiedades de la funcion de probabilidad
19 / 132
Funcion de probabilidad: ejemplo
20 / 132
Probabilidades condicionadas
21 / 132
Probabilidades condicionadas: ejemplo
Dado este conjunto de ejemplos:
I P(Si) =9
14, P(Circulo) =
4
14
I P(Si ,Circulo) =4
14
I P(Si |Circulo) =P(Si ,Circulo)
P(Circulo)=
4/14
4/14= 1
22 / 132
Regla de Bayes
23 / 132
Regla de Bayes: ejemplo
24 / 132
Distribuciones de probabilidad
25 / 132
Distribuciones de probabilidad: ejemplo
26 / 132
Marginalizacion sobre una variable
27 / 132
Marginalizacion: ejemplo
28 / 132
Independencia
29 / 132
Independencia: ejemplo
30 / 132
Independencia condicional: ejemplo
31 / 132
Independencia condicional: ejemplo
32 / 132
Regla de la cadena
33 / 132
Regla de la cadena: ejemplo
34 / 132
Contents
Conceptos preliminares
Redes bayesianas
Cadenas de Markov
Modelos ocultos de Markov
35 / 132
Sistemas expertos
36 / 132
Representacion del conocimiento
37 / 132
Conocimiento incierto
38 / 132
Componentes de una red bayesiana
39 / 132
Modelo de la alarma
40 / 132
Modelo de la alarma: DAG
41 / 132
Modelo de la alarmaDistribuciones de Probabilidad Condicionada (PCs) I
42 / 132
Modelo de la alarmaDistribuciones de Probabilidad Condicionada (PCs) II
43 / 132
Evidencias
44 / 132
Flujo de informacion
45 / 132
Conexiones en serie
46 / 132
Conexiones en serie
47 / 132
Conexiones divergentes
48 / 132
Conexiones divergentes
49 / 132
Conexiones convergentes
50 / 132
Conexiones convergentes
51 / 132
Conexiones convergentes
52 / 132
Razonamientos en redes bayesianas
53 / 132
Razonamientos en redes bayesianas
54 / 132
Razonamientos en redes bayesianas
55 / 132
d-separacion
56 / 132
d-separacion: ejemplos
57 / 132
d-separacion: ejemplos
57 / 132
d-separacion: ejemplos
57 / 132
d-separacion: ejemplos
57 / 132
d-separacion: ejemplos
57 / 132
d-separacion: ejemplos
57 / 132
d-separacion: ejemplos
57 / 132
d-separacion: ejemplos
57 / 132
d-separacion: ejemplos
57 / 132
d-separacion: ejemplos
57 / 132
d-separacion: ejemplos
57 / 132
d-separacion: ejemplos
57 / 132
d-separacion: ejemplos
57 / 132
Criterios para d-separacion
58 / 132
Criterios para d-separacion: ejemplo
59 / 132
Criterios para d-separacion: ejemplo
60 / 132
Mapas de dependencia e independencia
61 / 132
Limitacion expresiva de los DAGs
62 / 132
Redes bayesianas
63 / 132
Descomposicion de la distribuion conjunta
64 / 132
Construccion de redes bayesianas
65 / 132
Construccion de redes bayesianasOrden de las variables
66 / 132
Construccion de redes bayesianasOrden de las variables
67 / 132
Trabajando graficamente con redes bayesianas
Tenemos software disponible para redes bayesianas. Por ejemplo, elprograma Elvira (OpenSource):
I Instalacion y descarga de Elvira
68 / 132
Ejercicio de redes bayesianas
69 / 132
Ejercicio de redes bayesianas
70 / 132
Contents
Conceptos preliminares
Redes bayesianas
Cadenas de Markov
Modelos ocultos de Markov
71 / 132
Tiempo e incertidumbre
72 / 132
Cadenas de Markov
73 / 132
Propiedad de Markov
74 / 132
Cadenas de Markov y redes bayesianas
75 / 132
Componentes de una cadena de Markov
76 / 132
Ejemplo de cadena de Markov
77 / 132
Ejemplo de cadena de Markov - Excel
78 / 132
Representacion grafica de una cadena de Markov
79 / 132
Calculando probabilidades en una cadena de Markov
80 / 132
Probabilidad de una secuencia de estados
81 / 132
Probabilidad de una secuencia de estados - Excel
82 / 132
Probabilidad de una secuencia de estados - Ejemplo 2
83 / 132
Probabilidad de una secuencia de estados - Excel 2
84 / 132
Probabilidad de llegar a un estado
85 / 132
Probabilidad de llegar a un estado - Calculo
86 / 132
Probabilidad de llegar a un estado - Excel
87 / 132
Contents
Conceptos preliminares
Redes bayesianas
Cadenas de Markov
Modelos ocultos de Markov
88 / 132
Utilidades
I Segmentacion: Separar trozos de secuencias de nucleotidospor sus caracterısticas biologicas.
Separacion exon - intron
I Alineamiento multiple: Comparando cada secuencia con unmodelo estadıstico.
I Predicciones sobre funcionalidad: relacionar proteınas yfuncionalidades.
I Localizacion de genes: En celulas eucariotas.Composicion de un gen
89 / 132
Puntos de cambio
Enterobacteria phage lambda (48502 b.)
90 / 132
Segmentacion
Enterobacteria phage lambda (48502 b.)
91 / 132
Alineamiento multiple
R K R – – – R T GT K R R K T R T KR K R K – – R G KR G R – – – R T KR K K G – – R T K︸︷︷︸ ︸︷︷︸ ︸︷︷︸ ︸ ︷︷ ︸ ︸︷︷︸ ︸︷︷︸ ︸︷︷︸
M1 M2 M3 I M4 M5 M6
R .2
K .4
G .2
T .2
.4
I
R .8
K .2GT
.6M3
R 1KGT
.6
.4
M4
RK
G .2
T .8
1
M5
R
K .8
G .2T
1
M6
R
K .8
G .2T
1
M2
R .8KG
T .2
1
M1
¿ R K G G R T G ?
92 / 132
Modelos ocultos de Markov
I Para cada instante de tiempo o posicion t en una secuenciatenemos:
I una variable aleatoria Xt , con posibles valores {s1, . . . , sn}(estados, no observable directamente)
I otra variable aleatoria Et , con posibles valores {v1, . . . , vm}(observaciones)
I Propiedades asumidas:I Propiedad de Markov: (En cada posicion, el estado solo
depende del estado en la posicion inmediatamente anterior)
P(Xt |Y ,Xt−1) = P(Xt |Xt−1)
I Independencia de las observaciones: (En cada posicion, loobservado depende solo del estado en esa posicion)
P(Et |Y ,Xt) = P(Et |Xt)
93 / 132
Modelos ocultos de Markov
En definitiva...
I De las propiedades anteriores, se entiende que el modelo es elmismo para cualquier t, se refiera a instante de tiempo oposicion en una secuencia.
I En definitiva, tenemos que:I En cada instante/posicion de la secuencia, el estado depende
solo del estado en el instante/posicion inmediatamenteanterior
I En cada instante/posicion, lo observado depende solo delestado en ese instante/posicion
94 / 132
I Los estados ocultos pueden representar diferentes tipos desecuencias:
I Rica en GC, rica en ATI Region reguladora, region codificadora, intron, . . .
Probabilidad de que se produzca un cambio de estado
I Lo unico que se observa es la sucesion de sımbolos generados apartir de una distribucion multinomial que depende del estado.
Probabilidad de que aparezca cada uno de los sımbolos en cada uno
de los posibles estados
95 / 132
Modelos ocultos de Markov y redes bayesianas
Vista como red bayesiana, una modelo oculto de Markov tiene lasiguiente estructura:
I Cada nodo Xt tiene una tabla de probabilidad correspondientea P(Xt |Xt−1) (la misma tabla en todos los nodos)
I Excepto en el instante/posicion inicial X1, cuya tabla esP(X1)
I Cada nodo Et tiene una tabla de probabilidad correspondientea P(Et |Xt) (la misma tabla en todos los nodos)
96 / 132
Componentes de un MOM (o HMM) I
La cadena de Markov de los estados (modelo de transicion):I Una variable Xt con posibles valores {s1, . . . , sn} (estados
ocultos)
En cada posicion t, Xt toma exactamente uno de sus estados.
I P(Xt |Xt−1): viene dada por una matriz A = (aij), dondeaij = P(Xt = sj |Xt−1 = si ) (probabilidad de pasar de si a sj)
El estado en una posicion solo depende del estado en la posicion
anterior. El modelo probabilıstico que describe la manera de
transitar entre una posicion y la siguiente, no cambia a lo largo de
la secuencia.
Se cumple que∑n
j=1 aij = 1
I Vector π = (πi ), donde πi = P(X1 = si )(probabilidades a priori para cada estado).
97 / 132
Componentes de un MOM (o HMM) II
Por otro lado, la parte correspondiente a las observaciones(modelo sensor):
I Una variable aleatoria Et , con posibles valores {v1, . . . , vm}(observaciones)
En cada posicion t, Et toma exactamente una de sus observaciones.
I La tabla de probabilidad P(Et |Xt), dada por una matriz deprobabilidades de observacion B = (bij), dondebij = P(Et = vj |Xt = si ) (probabilidad de observar vj cuandoel estado es si )
La observacion en una posicion solo depende del estado en dicha
posicion. El modelo probabilıstico que describe la emision de la
observacion en cada estado, no cambia a lo largo de la secuencia.
Se cumple que∑n
j=1 bij = 1
98 / 132
Ejemplo
Disponemos de dos dados, uno equilibrado y el otro cargado. Unacadena de Markov modela la eleccion del dado en cada tirada. Ysegun el dado utilizado se genera el valor de la tirada segun unadistribucion de probabilidad distinta.Escogido uno de los lados existe un 90% de probabilidad de volvera usar el mismo para la siguiente tirada.Con el dado equilibrado la probabilidad de obtener cada uno de losvalores es siempre la misma: 0.1667Con el dado cargado la probabilidad de obtener un 6 es 0.5, muchomas que la probabilidad de obtener cualquiera del resto de losvalores: 0.1 para todos ellos.
99 / 132
Representacion grafica
b be6 c6= P(6 | e)=0.1667 = P(6 | c)=0.5
b
0.9 0.90.1
0.1
e c
b
0.5 0.5
e1 c1= P(1 | e)=0.1667 = P(1 | c)=0.1
... ...
b be5 c5= P(5 | e)=0.1667 = P(5 | c)=0.1
100 / 132
Problema
Vemos la sucesion de resultados de las distintas tiradas (aunquedesconocemos el dado utilizado para cada una de ellas)
4553653163363555133362665132141636651666
Segmentacion: ¿Podemos adivinar el dado utilizado en cadaocasion?
Para la secuencia anterior se ha usado en cada caso el siguientedado
eeeeeeeeeeeeeeeeeeeecccceeeeeeeccccccccc
Observese el aumento del valor 6 cuando se utiliza el dado cargado.
101 / 132
Probabilidad de una secuencia de estados
¿P(X1 = q1,X2 = q2, . . . ,Xt = qt)?I Aplicando la regla de la cadena, es igual a:
P(Xt = qt |X1 = q1, . . . ,Xt−1 = qt−1) · . . . · P(X2 = q2|X1 = q1) · P(X1 = q1)
I Por la propiedad de Markov, eso es igual a:
P(Xt = qt |Xt−1 = qt−1) · . . . · P(X2 = q2|X1 = q1) · P(X1 = q1)
I Luego P(X1 = q1,X2 = q2, . . . ,Xt = qt) = πq1 · aq1q2 · . . . · aqt−1qt
I Es decir, la probabilidad de una secuencia de estados es elproducto de las correspondientes probabilidades de transitarde cada estado al siguiente.
Ejemplo:
I P(e e e c) = 0.5 · 0.9 · 0.9 · 0.1 = 0.0405
102 / 132
Problemas principales a resolver en MOMs
Dada una secuencia de observaciones o1 · · · otI Filtrado: ¿cual es la probabilidad de que Xt = q?
I Ejemplo: si sabemos que la secuencia de valores hasta lacuarta tirada es 1, 1, 2, 1 ¿cual es la probabilidad de que en lacuarta tirada se haya utilizado el dado cargado?
I Explicacion mas verosımil: (o Decodificacion) ¿cual es lacorrespondiente secuencia de estados mas probable?
I Ejemplo: si sabemos que la secuencia de valores hasta laquinta tirada es 6, 6, 1, 1, 3 ¿cual es la secuencia mas probablede dados utilizados?
I Aprendizaje: conociendo los estados del modelo, pero no lasmatrices de transicion y de observaciones, establecer dichasprobabilidades
103 / 132
Filtrado
I Supongamos un modelo oculto de Markov:I Con variables aleatorias Xt (estado) y Et (observacion)I Con n estados {s1, . . . , sn} y m posibles observaciones{v1, . . . , vm}
I Con vector de probabilidades iniciales π, matriz de transicion Ay matriz de observacion B
I Supongamos que tenemos una secuencia O = o1o2 · · · ot ,observaciones
I Filtrado: dado un estado q, queremos calcular la probabilidadde, habiendo observado la secuencia O, que el estado delsistema en la posicion t sea q
I Es decir, queremos calcular
P(Xt = q|E1 = o1,E2 = o2, . . . ,Et = ot)
104 / 132
Filtrado: una primera simplificacion
I Tengase en cuenta que:
P(Xt |o1o2 · · · ot) = β · P(Xt , o1o2 · · · ot)
I Luego bastara calcular P(Xt = si , o1o2 · · · ot) para todos losestados si (1 ≤ i ≤ n), y luego normalizar
I Es decir, la probabilidad de observar la secuencia O y que,ademas, el estado en la posicion t sea si
I ¿Como se calcula β?
105 / 132
Una manera ineficiente de hacer filtrado
I Supongamos dada una secuencia de estados Q = q1 · · · qt yuna secuencia de observaciones O = o1 · · · ot
I Entonces (¿por que?):
P(Q,O) = P(O|Q)P(Q) = bq1o1 · . . . · bqtot · πq1 · aq1q2 · . . . · aqt−1qt
I Podrıamos entonces calcular P(Xt = q,O) haciendo∑Q P(Q,O), donde tenemos un sumando por cada secuencia
de estados Q, de longitud t, que acaba en el estado q
I Ineficiente: ¡¡ nt−1 sumandos !!I Alternativa eficiente
I Calcular P(Xt = sj , o1 · · · ot) de manera recursiva, en funcionde los P(Xt−1 = si , o1 · · · ot−1)
106 / 132
Calculo recursivo para filtrado
Llamamos αk(sj) a P(Xk = sj , o1 · · · ok), 1 ≤ k ≤ t:
I Inicio: 1 ≤ j ≤ nα1(sj) = P(X1 = sj , o1) = P(o1|X1 = sj) · P(X1 = sj) = bjo1 · πj ,
I Recursion (conocidos los valores de αk−1(sj)): 1 ≤ j ≤ n
αk(sj) = P(Xk = sj , o1 · · · ok)
= P(ok |Xk = sj , o1 · · · ok−1) · P(Xk = sj , o1 · · · ok−1)
= P(ok |Xk = sj) ·n∑
i=1
P(Xk = sj ,Xk−1 = si , o1 · · · ok−1)
= P(ok |Xk = sj) ·n∑
i=1
(P(Xk = sj |Xk−1 = si , o1 · · · ok−1) ·P(Xk−1 = si , o1 · · · ok−1) )
= P(ok |Xk = sj) ·n∑
i=1
(P(Xk = sj |Xk−1 = si )P(Xk−1 = si , o1 · · · ok−1) )
= bjok
n∑i=1
(aij · αk−1(si ))
107 / 132
Algoritmo de Avance
I Entrada:I Un modelo oculto de MarkovI Una secuencia de observaciones O = o1 · · · ot
I Salida:I El conjunto de probabilidades P(Xt = sj ,O) : 1 ≤ j ≤ n
I Procedimiento:I Inicio: α1(sj) = bjo1 · πj , (1 ≤ j ≤ n)I Para k desde 2 a t:
I αk(sj) = bjok
n∑i=1
(aij · αk−1(si )), (1 ≤ j ≤ n)
I Devolver el conjunto de valores: αt
108 / 132
¿Como usamos los αt(sj)? (I)
I Recordar que αt(sj) = P(Xt = sj , o1 · · · ot)I Calculo de la probabilidad de una secuencia de observaciones:
P(o1 · · · ot) =n∑
j=1
P(Xt = sj , o1 · · · ot) =n∑
j=1
αt(sj)
I Es decir, sumando los αt(sj), 1 ≤ j ≤ n, se obtiene laprobabilidad de la secuencia de observaciones
109 / 132
¿Como usamos los αt(sj)? (II)
I Calculo de la probabilidad de que en la posicion t estemos enun estado q, condicionado a que se ha observado la secuenciao1 · · · ot (filtrado):
I P(Xt |o1 · · · ot) se obtiene normalizando el conjunto deprobabilidades P(Xt = sj , o1 · · · ot) (1 ≤ j ≤ n)
I Es decir, normalizando los αt(si ), 1 ≤ j ≤ n, se obtienen lascorrespondientes probabilidades de filtrado
110 / 132
Ejemplo
Si sabemos que la secuencia de valores hasta la quinta tirada es1, 1, 2, 1 ¿cual es la probabilidad de que en la cuarta tirada se hayautilizado el dado cargado?
α1(e) = be1 · πe = 16· 0.5 = 0.08333
α1(c) = bc1 · πc = 0.1 · 0.5 = 0.05
α2(e) = be1 · (aee ·α1(e) +ace ·α1(c)) = 16· (0.9 ·0.08333 + 0.1 ·0.05) = 0.01333
α2(c) = bc1 ·(aec ·α1(e)+acc ·α1(c)) = 0.1 ·(0.1 ·0.08333+0.9 ·0.05) = 0.00533
α3(e) = be2 ·(aee ·α2(e)+ace ·α2(c)) = 16·(0.9·0.01333+0.1·0.00533) = 0.00209
α3(c) = bc2·(aec ·α2(e)+acc ·α2(c)) = 0.1·(0.1·0.01333+0.9·0.00533) = 0.00061
α4(e) = be1 ·(aee ·α3(e)+ace ·α3(c)) = 16·(0.9·0.00209+0.1·0.00061) = 0.00032
α4(c) = bc1·(aec ·α3(e)+acc ·α3(c)) = 0.1·(0.1·0.00209+0.9·0.00061) = 0.00008
Normalizando los valores de α4 se tiene que:
P(X4 = c |1121) = 0.2
111 / 132
Ejemplos adicionales
112 / 132
Ejemplos adicionales
113 / 132
Ejemplos adicionales
114 / 132
Ejemplos adicionales
115 / 132
Ejemplos adicionales
116 / 132
Ejemplos adicionales
117 / 132
Decodificacion (explicacion mas verosımil)
I Nuevamente, tenemos un modelo oculto de Markov y unasecuencia de observaciones O = o1 · · · ot
I Se trata ahora de calcular la secuencia de estadosQ = q1 · · · qt que mejor explica las observaciones
I Es decir, buscamos:
argmaxQ
P(Q|O)
I Podrıamos calcular P(Q|O) (o P(Q,O)) para todas lassecuencias posibles de estados Q, y tomar aquella que da elmaximo
I Ineficiente (del orden O(nt))
I Como con el filtrado, emplearemos un metodo mas eficiente,basado en recursion
118 / 132
Decodificacion: metodo recursivo
I Dada una secuencia de estados q1 · · · qt tal que qt = sj ,podemos calcular la probabilidad de pasar por esa secuenciade estados, habiendo ademas observado o1 · · · ot .
I Notaremos νt(sj) a la maxima de esas probabilidades, entretodas esas secuencias de estados. Es decir:
νt(sj) = maxq1q2···qt−1
P(o1 · · · ot , q1 · · · qt−1,Xt = sj)
I Cada νt(sj) se puede calcular recursivamente, en funcion delos νt−1(si ), 1 ≤ i ≤ n del instante anterior
119 / 132
Decodificacion: metodo recursivo
I La idea principal de la recursion es que la secuencia mas probable de
estados hasta llegar a Xt = sj , se compone de la secuencia mas probable
de llegar hasta un cierto estado si en el instante t − 1, seguido de un paso
de transicion desde tal si a sj . Por tanto, solo hay que “buscar” entre los
caminos mas probables hasta el instante t − 1 y ver desde cual se obtiene
la probabilidad maxima dando un paso mas:
2s2s 2s
o1 o1
s
sn
1
3s
s
sn
1
3s
s
sn
1
3s
sj
ks
1 2 t−1
ot−1
t
otObservaciones:
Tiempo:
estados
Posibles
120 / 132
Decodificacion: metodo recursivo
I Inicio: 1 ≤ j ≤ nν1(sj) = P(o1,X1 = sj) = P(o1|X1 = sj) · P(X1 = sj) = bjo1πj
I Recursion (conocidos los valores de νk−1(sj)): 1 ≤ j ≤ n
νk(sj) = maxq1q2···qk−1
P(o1 · · · ok , q1 · · · qk−1,Xk = sj)
= maxq1q2···qk−1
( P(ok |o1 · · · ok−1, q1 · · · qk−1,Xk = sj) ·P(o1 · · · ok−1, q1 · · · qk−1,Xk = sj) )
= P(ok |Xk = sj) · maxq1q2···qk−1
P(o1 · · · ok−1, q1 · · · qk−1,Xk = sj)
= P(ok |Xk = sj) ·max
i=1,...,n( P(Xk = sj |Xk−1 = si ) ·
maxq1q2···qk−2
P(o1 · · · ok−1, q1 · · · qk−2,Xk−1 = si ) )
= bjok maxi=1,...,n
(aij · νk−1(si ))
121 / 132
Decodificacion: metodo recursivo
I Se trata de un esquema recursivo analogo al del algoritmo deavance usado para filtrado, excepto que en lugar desumatorios, se toman maximos
I En este caso, ademas de calcular las probabilidades maximas,debemos llevar la cuenta de la secuencia de estados que secorresponden con esas probabilidades
I Se consigue almacenando, para cada estado e instante detiempo, un puntero prt(sj) al estado inmediatamente anterioren la secuencia mas probable
I El metodo descrito se denomina algoritmo de Viterbi
122 / 132
Algoritmo de Viterbi
I Entrada:I Un modelo oculto de MarkovI Una secuencia de observaciones O = o1 · · · ot
I Salida:I La secuencia de estados Q que maximiza P(Q|O)
I Procedimiento:I Inicio: ν1(sj) = bjo1 · πj , (1 ≤ j ≤ n)I Para k desde 2 a t:
I νk(sj) = bjok maxi=1,...,n
(aij · νk−1(si )), (1 ≤ j ≤ n)
I prk(sj) = argmaxi=1,...,n
(aij · νk−1(si )), (1 ≤ j ≤ n)
I Devolver la secuencia de estados:qt = argmax
i=1,...,nνt(si )
qk = prk+1(qk+1), (1 ≤ k ≤ t − 1)
123 / 132
EjemploSi sabemos que la secuencia de valores hasta la septima tirada es6, 6, 1, 1, 3 ¿cual es la secuencia mas probable de dados utilizados?
ν1(e) = be6 · πe = 16· 0.5 = 0.08333
ν1(c) = bc6 · πc = 0.5 · 0.5 = 0.25
ν2(e) = be6 ·max(aee · ν1(e), ace · ν1(c)) = 16·max(0.9 · 0.08333, 0.1 · 0.25) =
16·max(0.075, 0.025) = 0.0125
pr1(e) = eν2(c) = bc6 ·max(aec · ν1(e), acc · ν1(c)) = 0.5 ·max(0.1 · 0.08333, 0.9 · 0.25) =0.5 ·max(0.00833, 0.225) = 0.1125pr2(c) = c
ν3(e) = be1 ·max(aee · ν2(e), ace · ν2(c)) = 16·max(0.9 · 0.0125, 0.1 · 0.1125) =
16·max(0.01125, 0.01125) = 0.001875
pr3(e) = c
ν3(c) = bc1 ·max(aec · ν2(e), acc · ν2(c)) =
0.1 ·max(0.1 · 0.0125, 0.9 · 0.1125) = 0.1 ·max(0.00125, 0.10125) = 0.010125
pr3(c) = c
ν4(e) = be1 ·max(aee ·ν3(e), ace ·ν3(c)) = 16·max(0.9·0.001875, 0.1·0.010125) =
16·max(0.0016875, 0.0010125) = 0.00028125
pr4(e) = eν4(c) = bc1·max(aec ·ν3(e), acc ·ν3(c)) = 0.1·max(0.1·0.001875, 0.9·0.010125) =0.1 ·max(0.0001875, 0.0091125) = 0.00091125pr4(c) = c
ν5(e) = be3 ·max(aee · ν4(e), ace · ν4(c)) = 16·max(0.9 · 0.00028125, 0.1 ·
0.00091125) = 16·max(0.000253125, 0.000091125) = 0.0000421875
pr5(e) = eν5(c) = bc3 ·max(aec · ν4(e), acc · ν4(c)) = 0.1 ·max(0.1 · 0.00028125, 0.9 ·0.00091125) = 0.1 ·max(0.000028125, 0.000820125) = 0.0000820125pr5(c) = c
Por ultimo
q5 = c, q4 = pr5(q5) = c, q3 = pr4(c) = c, q2 = pr3(c) = c, q1 = pr2(c) = c
124 / 132
Ejemplo
Si sabemos que la secuencia de valores hasta la septima tirada es6, 6, 1, 1, 3 ¿cual es la secuencia mas probable de dados utilizados?
ν4(e) = be1 ·max(aee ·ν3(e), ace ·ν3(c)) = 16·max(0.9·0.001875, 0.1·0.010125) =
16·max(0.0016875, 0.0010125) = 0.00028125
pr4(e) = eν4(c) = bc1·max(aec ·ν3(e), acc ·ν3(c)) = 0.1·max(0.1·0.001875, 0.9·0.010125) =0.1 ·max(0.0001875, 0.0091125) = 0.00091125pr4(c) = c
ν5(e) = be3 ·max(aee · ν4(e), ace · ν4(c)) = 16·max(0.9 · 0.00028125, 0.1 ·
0.00091125) = 16·max(0.000253125, 0.000091125) = 0.0000421875
pr5(e) = eν5(c) = bc3 ·max(aec · ν4(e), acc · ν4(c)) = 0.1 ·max(0.1 · 0.00028125, 0.9 ·0.00091125) = 0.1 ·max(0.000028125, 0.000820125) = 0.0000820125pr5(c) = c
Por ultimo
q5 = c, q4 = pr5(q5) = c, q3 = pr4(c) = c, q2 = pr3(c) = c, q1 = pr2(c) = c
124 / 132
Ejemplos adicionales
125 / 132
Ejemplos adicionales
126 / 132
Ejemplos adicionales
127 / 132
Ejemplos adicionales
128 / 132
Ejemplos adicionales
129 / 132
Ejemplos adicionales
130 / 132
Ejemplos adicionales
131 / 132
Ejemplos adicionales
132 / 132
Ejemplos adicionales
133 / 132
Recommended