Download Selección y generación de modelos gráficos markovianos para

ALGORITMO PARA ESTIMAR LOS PARÁMETROS Y CALCULAR EL AJUSTE DE MODELOS
PROBABILÍSTICOS JERÁRQUICOS DESCOMPONIBLES PARA VARIABLES DISCRETAS
MC ELVA DÍAZ DÍAZ (DOCTORANTE)
DRA. EUNICE PONCE DE LEÓN SENTÍ (DIRECTORA TESIS)
DR. FELIPE PADILLA DÍAZ (ASESOR)
DRA. LUZ VIANNEY VELA ARÉVALO (ASESORA)
INTRODUCCIÓN
Los problemas de la estimación y del cálculo del
ajuste de los modelos jerárquicos descomponibles para
variables discretas son puntos cruciales para la
selección de modelos, y a su vez para los algoritmos
evolutivos del tipo conocido como EDA (Larrañaga y
Lozano, 2002). La complejidad del problema crece
exponencialmente con el número de variables, y con el
total de hiperlados que definen el modelo (Berge,
1989); también la tabla de datos crece
exponencialmente con el número de variables. Por
otro lado para los modelos jerárquicos sin
restricciones hay que utilizar el algoritmo iterativo
conocido como IPF (Darroch y Ratchliff, 1972) cuya
complejidad es exponencial. Estos dos hechos hacen
que estos problemas pertenezcan a la clase de los
problemas NP completos (Gary y Johnson, 1979). Los
modelos descomponibles tienen las propiedades de
que la estimación del modelo se puede calcular sin
algoritmo iterativo, y el ajuste del modelo se puede
calcular sin guardar los cálculos intermedios en la
memoria interna de la computadora, esto permite
escalar en el problema de selección de modelos, así
como en la aplicación a los algoritmos evolutivos del
tipo EDA (Ponce de León et al, 2004).
OBJETIVOS
El objetivo de este trabajo es encontrar algoritmos que
permitan utilizar menos memoria que los algoritmos
para modelos irrestrictos y con esto poder escalar los
algoritmos de selección de modelos y su aplicación a
los algoritmos evolutivos del tipo EDA.
MATERIAL Y MÉTODO
Se diseña y pone a punto un algoritmo de estimación
(EMD) y otro de medida del ajuste (AMD) para
modelo descomponible, utilizando la representación
del modelo por medio de hipergrafos (Berge, 1973). El
EMD calcula la estimación de las casillas de la tabla
sin necesidad de iteraciones. Se da un algoritmo para
calcular la familia de intersecciones del hipergrafo (FI)
El AMD calcula el ajuste del modelo en función de
sus márgenes y de la familia de intersecciones, y no
utiliza memoria interna de la máquina, ya que se
obtiene paso por paso al ir leyendo cada una de las
casillas de las tablas de los márgenes y de la familia de
intersección Se hacen pruebas con modelos de
complejidad definida por número de variables y de
tipo de interacciones. Se comparan las estimaciones y
el cálculo de ajuste, propuestos en este trabajo, con los
obtenidos por el IPF y la forma convencional de
calcular el ajuste. Las muestras utilizadas se generan al
azar a partir de modelos dados, por medio del
simulador IPF (Díaz, Ponce de León, 2003).
RESULTADOS
Los estimadores obtenidos por los dos algoritmos, IPF
y EMD, producen valores iguales para cada casilla de
la tabla. El EMD utiliza la tercera parte de la memoria
que ocupa el IPF utilizado en general para modelos no
descomponibles. El ajuste de los modelos por medio
del algoritmo propuesto tiene el mismo valor que el
calculado por el método convencional y los cálculos
intermedios no ocupan memoria interna de la
máquina.
CONCLUSIONES Y RECOMENDACIONES
Los resultados obtenidos son importantes porque el
EMD ocupa la tercera parte de la memoria que ocupa
el IPF y el AMD permite calcular el ajuste de un
modelo descomponible sin utilizar memoria. Se
recomienda probar el algoritmo de selección de
modelos propuesto anteriormente (Díaz y Ponce de
León, 2005) utilizando modelos descomponibles y
calculando el ajuste del modelo por el algoritmo que
aquí se propone lo cuál permitirá escalar el algoritmo
tanto en el problema de la selección de modelos como
en la aplicación a la computación evolutiva.
BIBLIOGRAFÍA
Berge, C. (1989) Hypergraphs. Noth-Holland
Darroch, J.N., Ratchliff, D. (1972) Generalizad
iterative scaling for log-linear models. Annals of
Mathematical Statistics, 43:1470-1480.
Díaz, E., Ponce de León, E. (2003) Generación
alatoria de muestras a partir de un modelo gráfico
Markoviano. Resúmenes del Décimo Simposio de
Investigación y Desarrollo Tecnológico. Ags.
Díaz, E., Ponce de León, E. (2005) Discrete Graphic
Markov Models selection by a Genetic Algorithm
based on different estimation of distribution
algorithms.
WSEAS
TRANSACTIONS
ON
MATHEMATICS. Isue 2.Volume 4.
Gary, M.R., Johnson, D.S. (1979) Computers and
Intractability. Library of Congreso.
Larrañaga, P. Lozano, J.A., (2002) Estimation of
Distributions
Algorithms.
Kluwer
Academia
Publishers.
Ponce de León, E. Díaz, E. Padilla, F. (2004)
Evolutionary Algorithm based on a Markov graphical
model selection of promising solutions. Advances in:
Artificial Intelligence, Computing
Science and
Computing Ingeneering. Vol 10