Download Bases Formales de la Computación: Sesión 1. Probabilidad Discreta

Bases Formales de la Computación: Sesión 1. Probabilidad Discreta
Bases Formales de la Computación:
Sesión 1. Probabilidad Discreta
Prof. Gloria Inés Alvarez V.
Departamento de Ciencias e Ingenierı́a de la Computación
Pontificia Universidad Javeriana Cali
11 de abril de 2008
Bases Formales de la Computación: Sesión 1. Probabilidad Discreta
Contenido
1
Presentación del Curso
2
Repaso de Teorı́a de Probabilidad Discreta
Teorı́a de Probabilidad
Probabilidad Condicional
Variables Aleatorias
Estadı́stica Bayesiana
Bases Formales de la Computación: Sesión 1. Probabilidad Discreta
Presentación del Curso
Bases Formales de la Computación
Fecha
abril 11
abril 18
abril 25
abril 26
mayo 2
mayo 9
mayo 16
mayo 23
mayo 30
junio 6
junio 13
junio 20
junio 27
julio 4
julio 11
Tema
Probabilidad discreta
Redes de Petri
Autómatas etiquetados
Álgebras de procesos
Redes de Bayes
Modelos Ocultos de Markov
Modelos Ocultos de Markov
Gramáticas Estocásticas
Evaluación
Trabajo dirigido
Trabajo dirigido
Estructuras algebraicas y cálculo de predicados
Lógicas modales
Verificación: transformadores de predicados
Evaluación
Profesor
G. Alvarez
E. Motato
F. Valencia
F. Valencia
C. Rueda
G. Alvarez
G. Alvarez
G. Alvarez
G. Alvarez
F. Valencia
F. Valencia
C. Rueda
C. Rueda
C. Rueda
C. Rueda
Bases Formales de la Computación: Sesión 1. Probabilidad Discreta
Repaso de Teorı́a de Probabilidad Discreta
Teorı́a de Probabilidad
Teorı́a elemental de probabilidad
Tiene por objetivo establecer qué tan posible es que algo ocurra.
Por ejemplo: si lanzamos tres monedas, qué tan posible es que
salga las tres veces cara.
Definición
Un experimento ó ensayo es el proceso por el cual se realiza una
observación
Bases Formales de la Computación: Sesión 1. Probabilidad Discreta
Repaso de Teorı́a de Probabilidad Discreta
Teorı́a de Probabilidad
Teorı́a elemental de probabilidad
Definición
Un espacio muestral Ω es un conjunto de observaciones. Puede ser
discreto si el número de muestras es contable o continuo si no lo es.
Definición
Un evento es un subconjunto del espacio muestral Ω.
Bases Formales de la Computación: Sesión 1. Probabilidad Discreta
Repaso de Teorı́a de Probabilidad Discreta
Teorı́a de Probabilidad
Teorı́a elemental de probabilidad
Definición
El espacio de eventos F es el conjunto potencia del espacio
muestral 2F
Las probabilidades son números reales entre 0 y 1 donde cero
significa imposibilidad y 1 certeza.
Definición
Una función ó distribución de probabilidad distribuye una masa de
probabilidad a través del espacio muestral Ω
Bases Formales de la Computación: Sesión 1. Probabilidad Discreta
Repaso de Teorı́a de Probabilidad Discreta
Teorı́a de Probabilidad
Distribución de Probabilidad
Definición
Una función o distribución de probabilidad es una función
P : F → [0, 1] tal que:
P(Ω) = 1
Si Aj , Ak ∈ F,P
j 6= k, Aj ∩ Ak = ∅ entonces
∞
P(∪j=1 Aj ) = ∞
j=1 P(Aj )
Llamamos P(A) a la probabilidad del evento A.
Definición
Una distribución que asigna igual probabilidad a todas las salidas,
|A|
se llama distribución uniforme. Y se calcula |Ω|
Bases Formales de la Computación: Sesión 1. Probabilidad Discreta
Repaso de Teorı́a de Probabilidad Discreta
Teorı́a de Probabilidad
Ejemplo
Se lanza una moneda tres veces, cuál es la probabilidad de obtener
dos caras?
Ω = {HHH, HHT , HTH, HTT , THH, THT , TTH, TTT }
Cada salida es igualmente probable (cara o sello)
El evento de interés es {HHT , HTH, THH} es decir, 3
opciones de 8, en otras palabras: 38
Bases Formales de la Computación: Sesión 1. Probabilidad Discreta
Repaso de Teorı́a de Probabilidad Discreta
Probabilidad Condicional
Probabilidad Condicional
Definición
La probabilidad condicional es la probabilidad actualizada de un
evento, dado que se tiene algún conocimiento previo. La
probabilidad antes de ese conocimiento previo se llama
probabilidad a priori.
Por ejemplo, si de los tres lanzamientos de moneda, ya se ha
realizado uno que salió cara, en los dos restantes hay dos
posibilidades de obtener otra cara, por lo tanto ahora la
probabilidad de obtener tres caras es de 12
Bases Formales de la Computación: Sesión 1. Probabilidad Discreta
Repaso de Teorı́a de Probabilidad Discreta
Probabilidad Condicional
Definición formal de probabilidad condicional
Definición
La probabilidad de un evento A, dado que ha ocurrido un evento B
(P(B) > 0) es: P(A|B) = P(A∩B)
P(B)
Notar que P(A ∩ B) = P(B)(P(A|B)) = P(A)P(B|A)
Definición
Dos eventos A, B son independientes si P(A ∩ B) = P(A)P(B)
Bases Formales de la Computación: Sesión 1. Probabilidad Discreta
Repaso de Teorı́a de Probabilidad Discreta
Probabilidad Condicional
Teorema de Bayes
Permite invertir la condicionalidad de dos eventos, es decir, permite
calcular P(B|A) en términos de P(A|B) esto es de utilidad cuando
no se puede calcular P(B|A), pero si se puede calcular P(A|B)
P(B|A) =
P(B ∩ A)
P(A)
=
P(A|B)P(B)
P(A)
El denominador es una constante de normalización, sirve para
garantizar que el resultado sea una función de probabilidad.
Bases Formales de la Computación: Sesión 1. Probabilidad Discreta
Repaso de Teorı́a de Probabilidad Discreta
Probabilidad Condicional
Teorema de Bayes
El denominador se puede obviar si sólo se quiere saber cuál evento
de un conjunto es el más probable dado A:
P(A|B)P(B)
argMaxB
= argMaxB P(A|B)P(B)
P(A)
Sin embargo, también se puede estimar el denominador para
completar la expresión.
Bases Formales de la Computación: Sesión 1. Probabilidad Discreta
Repaso de Teorı́a de Probabilidad Discreta
Probabilidad Condicional
Teorema de Bayes
Sabemos que:
P(A ∩ B) = P(A|B)P(B)
P(A ∩ B) = P(A|B̄)P(B̄)
Entonces tenemos:
P(A) = P(A ∩ B) + p(A ∩ B̄)
= P(A|B)P(B) + P(A|B̄)P(B̄)
Bases Formales de la Computación: Sesión 1. Probabilidad Discreta
Repaso de Teorı́a de Probabilidad Discreta
Probabilidad Condicional
Teorema de Bayes
Generalizando:
P(A) =
X
P(A|Bi )P(Bi )
i
Siempre y cuando existan conjuntos Bi que causen una partición
en A, es decir, A ⊆ ∩i Bi y los Bi sean disyuntos.
Bases Formales de la Computación: Sesión 1. Probabilidad Discreta
Repaso de Teorı́a de Probabilidad Discreta
Probabilidad Condicional
Ejemplo
Sea G una enfermedad que aparece 1 vez en 100.000 nacimientos.
Y sea T una prueba que diagnostica dicha enfermedad. Si una
persona tiene la enfermedad, la prueba lo descubrirá con una
probabilidad de 0,95, pero si no la tiene, la prueba dirá que
está enfermo con una probabilidad de 0,005. Suponiendo que la
prueba dice que la persona tiene la enfermedad, cuál es la
probabilidad de que realmente esté enferma?
P(T |G )P(G )
P(T |G )P(G ) + P(T |Ḡ )P(Ḡ )
0,95 · 0,00001
=
0,95 · 0,00001 + 0,005 · 0,99999
≈ 0,002
P(G |T ) =
Bases Formales de la Computación: Sesión 1. Probabilidad Discreta
Repaso de Teorı́a de Probabilidad Discreta
Variables Aleatorias
Variables Aleatorias
Definición
Una variable aleatoria es una función X : Ω → Rn (comúnmente n
= 1).
Sirven para representar un proceso estocástico que genera números
con cierta distribución de probabilidad.
Definición
Una variable aleatoria discreta es una función X : Ω → S donde S
es un subconjunto contable de R.
Si X : Ω → {0, 1} se le llama variable indicador aleatorio ó ensayo
de Bernoulli
Bases Formales de la Computación: Sesión 1. Probabilidad Discreta
Repaso de Teorı́a de Probabilidad Discreta
Variables Aleatorias
Ejemplo
Evento: lanzar dos dados.
Variable aleatoria X: la suma del valor de las caras obtenida
S = {2, . . . , 12}
Como la variable tiene rango numérico, a veces es más cómodo
hacer cálculos a partir de la variable que a partir del evento.
Definición
La función de masa de probabilidad (pmf) para una variable
aleatoria X , da la probabilidad de que la variable aleatoria tenga
diferentes valores numéricos
Bases Formales de la Computación: Sesión 1. Probabilidad Discreta
Repaso de Teorı́a de Probabilidad Discreta
Variables Aleatorias
Función de masa de probabilidad
La función de masa de probabilidad (pmf) se calcula como:
p(x) = p(X = x) = P(Ax )
Donde Ax = {w ∈ Ω | X (w ) = x} Si una variable aleatoria X
está distribuida de acuerdo a la pmf p(x), se denota X ∼ p(x).
Notar que p(x) > 0 sólo en un número contable de puntos.
Bases Formales de la Computación: Sesión 1. Probabilidad Discreta
Repaso de Teorı́a de Probabilidad Discreta
Variables Aleatorias
Función de masa para variables aleatorias discretas
La función de masa de probabilidad (pmf) para una variable
aleatoria discreta, se calcula como:
X
X
p(xi ) =
P(Ai ) = P(Ω) = 1
i
i
Conversamente, cualquier función que cumpla estas condiciones,
se puede ver como una función de masa de probabilidad
Bases Formales de la Computación: Sesión 1. Probabilidad Discreta
Repaso de Teorı́a de Probabilidad Discreta
Variables Aleatorias
Valor esperado
Definición
El valor esperado es la media o promedio de una variable aleatoria.
Si
P X es una variable aleatoria con pmf p(x) tal que
P
x |x|p(x) < ∞, entonces el valor esperado es: E (X ) =
x xp(x)
Ejemplo:
Si se lanza un dado y Y es el número que sale, entonces:
E (Y ) =
6
X
y =1
6
yp(y ) =
21
1
1X
y=
=3
6
6
2
y =1
Este es el promedio esperado resultante de lanzar muchas veces el
dado y dividir por el número de lanzamientos.
Bases Formales de la Computación: Sesión 1. Probabilidad Discreta
Repaso de Teorı́a de Probabilidad Discreta
Variables Aleatorias
Valor esperado
Definición
Si Y ∼ p(y ) es una variable aleatoria, cualquier función g(Y )
define una nueva variable aleatoria y su valor esperado se define
como:
X
E (g (Y )) =
g (y )p(y )
y
Bases Formales de la Computación: Sesión 1. Probabilidad Discreta
Repaso de Teorı́a de Probabilidad Discreta
Variables Aleatorias
Varianza
Es una medida de si los valores de una variable aleatoria tienden a
ser consistentes en muchos ensayos o varı́an. Se mide averiguando
qué tanto se desvı́an los valores del valor esperado.
Var (X ) = E ((X − E (X ))2 )
= E (X 2 ) − E 2 (X )
La desviación estandar es la raiz cuadrada de la varianza.
Bases Formales de la Computación: Sesión 1. Probabilidad Discreta
Repaso de Teorı́a de Probabilidad Discreta
Variables Aleatorias
Distribuciones Multivariadas
Cuando se definen varias variables aleatorias en un mismo espacio
muestral, se obtiene una distribución multivariada
Definición
La función de masa de la distribución multivariada para dos
variables aleatorias discretas es: P(x, y ) = P(X = x, Y = y ). Si
X , Y son independientes, p(x, y ) = PX (x)PY (y ).
Bases Formales de la Computación: Sesión 1. Probabilidad Discreta
Repaso de Teorı́a de Probabilidad Discreta
Variables Aleatorias
Determinación de la función de probabilidad
En problemas prácticos lo normal es que no se conozca la
función de probabilidad, por lo tanto es necesario estimarla
Esto se puede hacer a partir de la evidencia sobre P contenida
en datos.
Llamamos frecuencia relativa al número de veces que aparece
un dato en la colección disponible. se calcula CN(u) donde C (u)
es el número de veces que aparece u y N el número total de
ensayos.
La frecuencia relativa tiende a estabilizarse a medida que el
tamaño de los datos disponibles aumenta. Esto permite
calcular probabilidades estimadas
Bases Formales de la Computación: Sesión 1. Probabilidad Discreta
Repaso de Teorı́a de Probabilidad Discreta
Variables Aleatorias
Determinación de la función de probabilidad
Los métodos de estimación suelen estimar P suponiendo que
su comportamiento se parece al de alguna familia conocida de
distribuciones de probabilidad. Por ejemplo: binomial,
Gaussiana, etc.
Este enfoque se llama paramétrico porque la estimación
consiste en fijar valores apara los parámetros especı́ficos
dentro de la familia de distribuciones elegida. Ventajas:
Se deben estimar pocos parámetros
Se requiere poca información para hacer la estimación
La desventaja es que si el comportamiento real de la función
se aleja mucho del comportamiento de la familia de
distribuciones, las estimaciones serán malas.
Bases Formales de la Computación: Sesión 1. Probabilidad Discreta
Repaso de Teorı́a de Probabilidad Discreta
Variables Aleatorias
Determinación de la función de probabilidad
Existe otra opción que es realizar la estimación por métodos no
paramétricos, en ellos no se presupone una familia de
distribuciones, pero en cambio es necesario disponer de una mayor
cantidad de datos.
Un ejemplo de método no paramétrico, el vecino más próximo.
Bases Formales de la Computación: Sesión 1. Probabilidad Discreta
Repaso de Teorı́a de Probabilidad Discreta
Variables Aleatorias
Distribución binomial
Es una distribución discreta
Resulta de una serie de experimentos con sólo dos valores de
salida posibles (ensayos de bernoulli), siendo cada ensayo
independiente de los otros. Ejemplo: lanzar repetidamente una
moneda.
La familia de las distribuciones binomiales calcula el número r
de éxitos en n ensayos, dado que la probabilidad de éxito en
un ensayo es p.
n r
b(r ; n, p) =
p (1 − p n−r )
r
n!
,0 ≤ r ≤ n
Donde nr = m!(n−m)!
El valor esperado es np y la varianza es np(1 − p)
Bases Formales de la Computación: Sesión 1. Probabilidad Discreta
Repaso de Teorı́a de Probabilidad Discreta
Estadı́stica Bayesiana
Estadı́stica Bayesiana
No todos coinciden en que los fundamentos filosóficos de la la
estadı́stica basada en frecuencia sean sólidos.
El principal rival es el enfoque Bayesiano...
Supongamos que uno lanza una moneda 10 veces y sale cara 8
veces. Si la moneda no está trucada, uno dirı́a que el estimativo no
es correcto.
La probabilidad frecuencialista dirı́a que los datos revelan que
8
la probabilidad de obtener cara es 10
Los Bayesianos dirı́an que si se hubieran realizado más ensayos
la cantidad de caras y sellos habrı́a terminado por equilibrarse
y que la probabilidad de obtener cara es 21
Bases Formales de la Computación: Sesión 1. Probabilidad Discreta
Repaso de Teorı́a de Probabilidad Discreta
Estadı́stica Bayesiana
Estadı́stica Bayesiana
8
10
es un estimativo de máxima verosimilitud
El enfoque Bayesiano parte de una creencia a priori que se va
refinando con las observaciones que se realizan. notar que
estas creencias a priori influencias aquello que creemos y lo
que estamos dispuestos a creer, aun ante la existencia de
datos contra evidentes.
Bases Formales de la Computación: Sesión 1. Probabilidad Discreta
Repaso de Teorı́a de Probabilidad Discreta
Estadı́stica Bayesiana
Estadı́stica Bayesiana
La estadı́stica Bayesiana mide el grado de credibilidad y se
calcula comenzando con una probabilidad a priori y
actualizándola en la presencia de evidencia por medio del
teorema de Bayes.
La teorı́a de decisiones Bayesiana permite evaluar cuál modelo
o familia explica mejor un conjunto de datos. Se calcula el
teorema de Bayes para cada modelo, se dividen los valores
obtenidos, eso se llama rata de verosimilitud, si da > 1 el
modelo del numerador es mejor y sinó el del denominador es
mejor. Elegir el que gane con esta medida es tomar una
decisión óptima de Bayes.