Todo sistema de aprendizaje lleva asociada una serie de limitaciones que restringen su ámbito de aplicación a problemas concretos, en los que los datos de entrada deben estar expresados de una forma característica y los resultados se ajustan a cierto formato.
Entre los lenguajes empleados por los sistemas de aprendizaje simbólico destaca la lógica de predicados de primer orden, pues su gran potencia descriptiva y su flexibilidad la hacen adecuada para describir, de una forma sencilla, estructuras y relaciones complejas existentes en gran número de problemas. Por ello, sistemas como FOIL y FZFOIL, que siguen el enfoque simbólico, inducen reglas que son adecuadas para describir soluciones complejas de problemas muy diversos. Sin embargo, hay que destacar dos limitaciones importantes en la utilización de la lógica de predicados en estos sistemas:
Realmente se utiliza una versión limitada de la lógica de predicados, tanto en FOIL como en su versión borrosa FZFOIL. De hecho, no se permite la utilización de funciones ni en las definiciones lógicas que se construyen, ni en la definición de los predicados intensionales de entrada. Además, como es habitual en programación lógica, la semántica de la negación en las cláusulas de Horn es distinta de la semántica de la lógica de predicados.
Por otro lado, existen limitaciones intrínsecas al propio algoritmo de inducción:
FOIL y FZFOIL son sistemas de adquisición de conceptos, pero no de descubrimiento o formación de conceptos. Es decir, es necesario especificar la relación objetivo para la que se quiere inducir una definición, pues estos sistemas no son capaces de formar conceptos existentes entre los datos, pero desconocidos de antemano.
La extensión de la lógica de predicados hacia una lógica borrosa de predicados es un paso adelante en la flexibilidad y potencia descriptiva, tanto en la entrada de datos (mediante relaciones borrosas) como en la representación del conocimiento inducido (reglas borrosas). Esto aumenta el campo de aplicación de FZFOIL respecto de FOIL, especialmente al manejar conceptos borrosos, como los utilizados habitualmente por los humanos, ya que se facilita el modelado del problema y resulta más fácil de entender la solución del mismo (la definición del mismo). Sin embargo, existen otros tipos de incertidumbre, distintos de la borrosidad, que no se pueden representar en FZFOIL:
Existen diferentes métodos para representar la incertidumbre; en FZFOIL sólo se utiliza uno de ellos: la teoría de conjuntos borrosos, aplicada a la construcción de BD relacionales.
Por otro lado, las reglas que se inducen representan conocimiento borroso (mediante literales borrosos) que, además, pueden tener asociado un factor de probabilidad.
Entre las aplicaciones más inmediatas de FZFOIL se encuentra la construcción de definiciones lógicas para relaciones de una BD, al igual que ocurre en FOIL. En FZFOIL se amplía el campo de aplicación al permitir manejar relaciones borrosas, es decir, puede ser aplicado tanto sobre las tradicionales BD relacionales como sobre BD relacionales borrosas.
La utilidad de esta aplicación cada vez es más evidente, dado el interés que están adquiriendo los sistemas de control borrosos, sistemas expertos borrosos, etc.
Por otro lado, también resulta interesante simplemente para analizar datos y extraer conocimiento de los mismos. La utilización de la lógica borrosa de predicados en FZFOIL facilita la comprensión del conocimiento inducido, al manejar relaciones borrosas, más parecidas a los conceptos utilizados en lenguaje natural.
Aunque la introducción de la lógica borrosa en FZFOIL aumenta la complejidad de la búsqueda, resulta aplicable no sólo sobre pequeños conjuntos de entrenamiento, sino también sobre un conjunto voluminoso de datos reales, como se muestra a continuación.
En este apartado se presentan algunos resultados obtenidos por FZFOIL en el Proyecto SEIC (Servicio de Información Ciudadana, PC-183), dentro de la línea de "Acciones Especiales PASO", gestionada por el C.D.T.I. y cofinanciada por la Unión Europea y el Ministerio de Industria de España. Este proyecto ha estado coordinado por EnWare, S.A., y en él han participado también, además del DIT, el Consorcio Regional de Transportes de Madrid, el Colegio Oficial de Farmacéuticos de Madrid y Genasys II Spain.
El proyecto SEIC ha servido como motor y campo de pruebas para nuestro sistema FZFOIL, al aportar no sólo un objetivo concreto (aunque no el principal) para el desarrollo del trabajo realizado, sino también una valiosa fuente de datos reales, con los que evaluar los resultados de manera más objetiva.
El objetivo del proyecto SEIC consiste en la construcción de un sistema de información de carácter general, orientado a los ciudadanos, que podrán acceder al mismo a través de unos puestos de información ciudadana (PICs) situados en la vía pública, normalmente en estaciones de Metro o en lugares de interés turístico. La información que se ofrecerá inicialmente será sobre transportes públicos y sobre farmacias, aunque, virtualmente, podrá extenderse a otros tipos de información.
Dentro del proyecto existen diferentes módulos, para cubrir los diferentes requisitos del mismo: base de datos sobre transportes, datos sobre farmacias, comunicaciones entre el módulo central y los PICs, sistema de alarmas, interfaz gráfica, etc. La participación del Departamento de Ingeniería de Sistemas Telemáticos (DIT) se centró en uno de los módulos, denominado Módulo de Usos y Demandas, situado funcionalmente como un elemento anexo al conjunto, que no afecta directamente al funcionamiento general, pero que puede aportar información muy valiosa sobre el sistema.
El objetivo de este Módulo de Usos y Demandas es bastante genérico y, a la vez, ambicioso. Se pretende que analice de un modo inteligente las consultas realizadas por los usuarios desde los PICs. De este análisis se pueden extraer conclusiones (conocimiento) sobre posibles patrones de comportamiento por parte de los usuarios, relaciones entre diferentes entidades (averías, fallos en las comunicaciones, consultas, momento del día, etc.) o cualquier otra información de interés, tanto para los suministradores de las bases de datos (Consorcio de Transportes de Madrid y Colegio de Farmacéuticos de Madrid) como para la empresa que se encargue del mantenimiento y explotación del sistema.
Desde un principio se confió en la posibilidad de aplicar el trabajo que se estaba desarrollando para esta Tesis, dentro del Módulo de Usos y Demandas del SEIC.
Por su propia naturaleza, para realizar pruebas exhaustivas en el Módulo de Usos y Demandas se requiere un volumen de datos grande que, por otro lado, no podrá recopilarse hasta que se construya el resto del sistema y se ponga en funcionamiento. Es decir, la calidad y relevancia de las reglas inducidas sólo se podrá valorar tras meses de pruebas de campo del sistema SEIC.
Por fortuna, el Consorcio Regional de Transportes de Madrid nos proporcionó desde el principio varios ficheros de datos, recopilados durante los meses de Julio a Noviembre de 1994 en diferentes puntos de Madrid, dentro del proyecto SIT (Sistema de Información de Transportes), precursor del actual SEIC. Estos datos representan diferentes características de las consultas que se realizaron en varios PICs, y con ellos se han podido realizar diferentes pruebas del sistema descrito en esta Tesis.
A continuación se describe el formato de los datos disponibles y los pasos de selección, preprocesado y transformación previos a la inducción de conocimiento (minería de datos), dentro del proceso global de KDD. También se presentan algunos de los resultados obtenidos alimentando el Módulo de Usos y Demandas con estos datos, así como algunas conclusiones derivadas de la interpretación y evaluación de los resultados.
El volumen de datos disponible (del proyecto SIT) corresponde a más de 40000 consultas, cada una de ellas caracterizada por 14 atributos, como se verá a continuación.
Estos ficheros de datos de entrada (de nombre XXXM.dat) vienen ordenados por el PIC en el que se han generado (XXX) y el mes (M) correspondiente. Existen datos de 8 diferentes localizaciones de PICs:
y de los meses de Julio a Noviembre de 1994:
Dentro de cada fichero, los datos tienen un formato plano, correspondiendo cada línea a una única consulta. Dentro de cada línea, cada uno de los atributos se almacena en una columna fija, del siguiente modo:
Para trabajar con estos datos iniciales del SIT es necesario preprocesarlos y transformarlos, para convertirlos a formato relacional, en diferentes tablas que puedan ser manejadas por el algoritmo de aprendizaje.
A partir de los ficheros de datos de partida, se pueden identificar los siguientes dominios, para los diferentes atributos:
Id_consulta: Entero que identifica de forma unívoca cada una de las consultas. Los posibles valores varían desde 1, para la primera consulta, hasta n (para n consultas almacenadas).
Cambio_fecha: Indica si se ha cambiado la fecha/hora actual para realizar la consulta. Los posibles valores son: {"SI", "NO"}
Tipo_lugar: Identifica el origen o destino de una consulta. Puede tomar los valores: {"Aquí", "Calle_Edif_singular", "Cruce", "Metro"}
Tipo_rest_tte: Restricción impuesta por el usuario respecto al medio de transporte que se debe emplear. Su dominio es: {"Cualquiera", "Sólo_bus", "Sólo_metro"}
Tipo_rest_optim: Restricción impuesta por el usuario respecto al criterio que se debe optimizar: {"Camino_óptimo", "Min_transbordos", "Min_tiempo"}
Localización: Lugar en que se encuentra un PIC (corresponde a la localización indicada por el fichero de entrada): {"Al_Martínez", "Av_América", "At_renfe", "Callao", "CI_Princesa", "C_Caminos", "P_Castilla", "Sol"}
Mes: Mes del año en que se realizó la consulta (corresponde al mes indicado por el fichero de entrada correspondiente): {"Enero", "Febrero", "Marzo", "Abril", "Mayo", "Junio", "Julio", "Agosto", "Septiembre", "Octubre", "Noviembre", "Diciembre"}
Día_semana: Día de la semana en que se realizó la consulta: {"Domingo", "Lunes", "Martes", "Miércoles", "Jueves" "Viernes", "Sábado"}
Hora_día: Hora del día en que se hizo la consulta: {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24}.
Duración: Indica la duración en segundos de la consulta. Sus valores varían de 60 en 60 segundos, desde 0 hasta 216000.
Se han suprimido algunos atributos existentes en los ficheros originales, dada su irrelevancia para nuestro módulo inductivo. Así, por ejemplo, se ha eliminado el año de cada consulta, ya que todas se realizaron en 1994.
En algunas de las pruebas realizadas se han introducido dominios borrosos nuevos, generados a partir de algunos de los dominios originales. En concreto, se ha introducido borrosidad en los valores de Hora_día y los de Duración, del siguiente modo ( See Subconjuntos borrosos para Hora_día y See Subconjuntos borrosos para Duración ):
Hora_día_borrosa: Momento del día en que se hizo la consulta: {"Noche", "Mañana", "Tarde"}
Duración_borrosa: Indica la duración de la consulta. Sus valores son: {"Corta", "Media", "Larga"}
Dado el volumen de datos disponible, es conveniente aplicar técnicas de muestreo sobre los mismos. Para obtener los resultados mostrados en el apartado 5.3.4 se utilizó una muestra aleatoria con el 5% del total de consultas existentes. Esta muestra se mantuvo constante en todas las pruebas realizadas.
Las relaciones construidas a partir de los datos iniciales son las siguientes (con los atributos indicados):
En las pruebas realizadas con datos borrosos se han introducido tres relaciones nuevas, una para cada uno de los valores borrosos definidos en el dominio Hora_día_borrosa:
cuando_noche (Id_consulta, Mes, Día_semana)
cuando_noche(X, Y, Z) ¤ cuando(X, Y, Z, W) W = Noche
Del mismo modo, para los valores borrosos del dominio Duración_borrosa se han definido tres relaciones borrosas:
Mediante el uso de relaciones intensionales ( apartado 4.3.5 ) se ofrece la posibilidad de que el operador introduzca conocimiento de base en el sistema. Estas relaciones intensionales permiten seleccionar el subconjunto de datos para el que se desea inducir una descripción lógica (en sí mismas, también pueden considerarse como descripciones lógicas). Por ejemplo, para seleccionar las "consultas que tuvieron lugar en la estación de metro Sol durante el mes de Noviembre" se puede introducir la relación intensional:
I_sol_noviembre (a: Id_consulta) :-
realizada_en(a, b), =(b, Sol), cuando(a, c, d, e), =(c, Noviembre).
Estas relaciones intensionales se introducen en un fichero ascii, pudiendo coexistir varias. Al generarse la BD relacional (conjunto de entrenamiento para nuestro algoritmo), se añaden al final de la misma, detrás de las relaciones extensionales definidas anteriormente.
A continuación se muestran diferentes resultados obtenidos a partir de los datos del SIT, con la versión actual de FZFOIL. Para la obtención de los mismos se ha utilizado una estación de trabajo SUN Ultra-1, con sistema operativo Solaris 2.5. El tiempo de ejecución máximo para cada ejemplo se ha fijado en 60 minutos (si en ese tiempo no se llega a una definición consistente y completa, se para la ejecución en el punto en que se encuentre y se muestran los resultados, sin aplicar ningún mecanismo de poda de definiciones).
En todos los ejemplos se ha utilizado la función Interés* para evaluación de literales.
Se han seleccionado 6 relaciones objetivo diferentes, introducidas mediante relaciones intensionales 1 . Para cada una de ellas se han construido dos ejemplos, uno con relaciones ordinarias (caso a, en los siguientes apartados) y otro con relaciones ordinarias y borrosas (caso b), lo que hace un total de 12 ejemplos.
La selección, preprocesado y transformación de los datos de partida ha sido igual para todos los ejemplos, tal como se explica en los apartados anteriores. Las únicas diferencias entre ellos son, por tanto, la relación objetivo seleccionada y la existencia o no de relaciones borrosas (dependiendo de si se trata de un ejemplo de tipo b o del tipo a respectivamente).
La relación objetivo utilizada para estos ejemplos corresponde a la siguiente relación intensional:
El tiempo de ejecución finaliza durante la construcción de la tercera cláusula (C3), que no llega a ser consistente. Resulta, por tanto, una definición incompleta e inconsistente, que puede describirse como 2 :
"El 20.17% de las consultas en las que se quiere minimizar el tiempo del viaje cumplen:
Las cláusulas de Horn construidas son:
[C1] {9.910 bits} [694.00/1694.00]Æ [1.00/1.00]
[C2] {61.163 bits} [693.00/1693.00]Æ [4.00/4.00]
[C3] {52.547 bits} [689.00/1689.00]Æ [135.00/220.00]
Los valores de los parámetros a comparar son los siguientes:
k-completitud = 140 / 694 = 20.17% k-completitud / LDI = 0.0017
k-consistencia = 140 / 225 = 62.22% k-consistencia / LDI = 0.0051
La definición parcialmente construida consta, en este caso de una única cláusula, inconsistente e incompleta, que puede interpretarse como:
"El 49.90% de las consultas en las que se quiere minimizar el tiempo del viaje cumplen que, con un 44.81% de probabilidad, se realizaron por la tarde un día que no era Viernes".
[C1] {17.062 bits} [694.00/1694.00]Æ [346.28/772.71]
k-completitud = 346.28 / 694 = 49.90% k-completitud / LDI = 0.0293
k-consistencia = 346.28 / 772.71 = 44.81% k-consistencia / LDI = 0.0263
Relación intensional objetivo:
La definición parcialmente construida consta, en este caso, de cuatro cláusulas, que pueden interpretarse del siguiente modo:
"El 58.45% de las consultas en las que se quiere minimizar el número de transbordos cumplen:
[C1] {36.203 bits} [1119.00/2049.00]Æ [217.00/217.00]
[C2] {31.087 bits} [902.00/1832.00]Æ [88.00/88.00]
[C3] {46.703 bits} [814.00/1744.00]Æ [50.00/52.00]
=_const ( C Calle_Edif_singular ).
[C4] {42.003 bits} [764.00/1692.00]Æ [299.00/542.00]
k-completitud = 654 / 1119 = 58.45% k-completitud / LDI =0.0039
k-consistencia = 654 / 899 = 72.75% k-consistencia / LDI = 0.0048
De nuevo resulta una definición más sencilla para el caso de relaciones borrosas:
"El 24.43% de las consultas en las que se quiere minimizar el número de transbordos se realizan (con una probabilidad del 62.54%) por la mañana, un día que no es Martes ni en Octubre ni en Julio".
[C1] {31.291 bits} [1119.00/2049.00]Æ [273.35/437.05]
k-completitud = 273.35 / 1119 = 24.43% k-completitud / LDI = 0.0078
k-consistencia = 273.35 / 437.05 = 62.54% k-consistencia / LDI = 0.0200
[C1] {38.016 bits} [232.00/1232.00]Æ [6.00/12.00]
¬ =_const ( C Calle_Edif_singular ),
k-completitud = 6 / 232 = 2.59% k-completitud / LDI = 0.0007
k-consistencia = 6 / 12 = 50.00% k-consistencia / LDI = 0.0131
[C1] {31.291 bits} [232.00/1232.00]Æ [92.83/405.23]
k-completitud = 92.83 / 232 = 40.01% k-completitud / LDI = 0.0128
k-consistencia = 92.83 / 405.23 = 22.91% k-consistencia / LDI = 0.0073
Relación intensional objetivo:
[C1] {18.195 bits} [70.00/1070.00]Æ [8.00/13.00]
k-completitud = 8 / 70 = 11.43% k-completitud / LDI = 0.0063
k-consistencia = 8 / 13 = 61.54% k-consistencia / LDI = 0.0338
[C1] {65.925 bits} [70.00/1070.00]Æ [38.34/331.05]
k-completitud = 38.34 / 70 = 54.77% k-completitud / LDI = 0.0083
k-consistencia = 38.34 / 331.05 = 11.58% k-consistencia / LDI = 0.0018
Relaciones intensionales 3 :
I_bus_mintransbordos(Id_consulta)
En este caso se obtiene una definición consistente y completa, formada por una única cláusula, que utiliza una de las relaciones intensionales como antecedente: "todas las consultas realizadas en las que se desea utilizar sólo el autobús, quieren también minimizar el número de transbordos".
[C1] {4.907 bits} [232.00/1232.00]Æ [232.00/232.00]
k-completitud = 232 / 232 = 100% k-completitud / LDI = 0.2038
k-consistencia = 232 / 232 = 100% k-consistencia / LDI = 0.2038
La definición inducida en el caso de tener relaciones borrosas es la misma que en el caso de sólo relaciones ordinarias, ya que se obtiene una definición consistente y completa sin necesidad de utilizar literales borrosos:
[C1] {5.392 bits} [232.00/1232.00]Æ [232.00/232.00]
La LDI calculada para la definición en este caso borroso es mayor que la calculada en el caso a, aunque ambas definiciones son iguales. Esto se debe a que la longitud de codificación de los literales depende del número de relaciones en la BD ( apartado 4.3.2.9 ), y en los ejemplos de tipo b se están considerando 6 relaciones borrosas más que en los ejemplos de tipo a (sin relaciones borrosas).
k-completitud = 232 / 232 = 100% k-completitud / LDI = 0.1854
k-consistencia = 232 / 232 = 100% k-consistencia / LDI = 0.1854
Relación intensional objetivo usada con relaciones ordinarias:
Relación intensional objetivo usada con relaciones borrosas:
[C1] {53.234 bits} [172.00/1166.00]Æ [2.00/2.00]
[C2] {61.952 bits} [170.00/1164.00]Æ [50.00/196.00]
k-completitud = 52 / 172 = 30.23% k-completitud / LDI =0.0026
k-consistencia = 52 / 198 = 26.26% k-consistencia / LDI = 0.0023
La comparación la realizaremos a partir de los cinco parámetros calculados para cada ejemplo:
Puede observarse que, para este conjunto de ejemplos, la longitud de descripción intensional tiende a ser mayor en el caso de sólo relaciones ordinarias (hasta 12.5 veces mayor en el ejemplo 6), aunque en algunos casos ocurre lo contrario 4 (ejemplo 4). En media, con las definiciones borrosas se ha conseguido un ahorro de más del 60% del total de bits.
Esto se traduce en descripciones borrosas más cortas y, por tanto, más fáciles de entender.
El máximo valor de k-completitud (para el que se satisface la condición de k-completitud) es, normalmente mayor en el caso B (definiciones borrosas), aunque con algunas excepciones (ejemplo 2). Esto puede interpretarse como que las descripciones borrosas son más generales que las construidas sólo con relaciones ordinarias.
El máximo valor de k-consistencia (para el que se satisface la condición de k-consistencia) es, en los ejemplos anteriores, siempre mayor para el caso A (sólo relaciones ordinarias). Esto se traduce en unas definiciones borrosas menos precisas que las construidas sólo con relaciones ordinarias.
Al comparar los valores de k-completitud y k-consistencia por unidad de LDI, se observa que, en los ejemplos considerados:
Este resultado puede interpretarse como que, para longitudes de descripción fijas, las definiciones borrosas son más completas y, algunas veces, más consistentes que las definiciones ordinarias. O dicho de otro modo, las definiciones borrosas generalizan mejor los conceptos y, en ocasiones, son también más precisas que las definiciones sin relaciones borrosas.
La complejidad asociada a la inducción de una definición lógica viene determinada por la búsqueda de los literales que constituyen sus cláusulas. A su vez, esta búsqueda depende de:
Ambos valores vienen determinados por factores como el grado de las relaciones existentes en la BD, el predicado elegido como objetivo o la longitud de la cláusula resultante.
Para realizar un estudio formal de la complejidad de FOIL, utilizaremos el enfoque seguido por [Pazzani y Kibler, 92] , en el que descomponen el coste de la búsqueda de un nuevo antecedente Li en una cláusula en construcción Ci-1 con u variables, en el producto de dos parámetros:
El coste resultante para la búsqueda del antecedente i-ésimo Li, en una cláusula, será el producto de ambos parámetros:
Para estudiar la complejidad del nuevo sistema FZFOIL seguiremos un proceso paralelo, en el que se calcularán los correspondientes valores CT y CE, y se compararán con los obtenidos para FOIL.
Como ya se ha definido, el coste teórico (CT) mide el tamaño del espacio de búsqueda, expresado en número de literales.
Para cada literal que se añade a una cláusula existe un espacio de búsqueda diferente. Supongamos que queremos añadir un nuevo antecedente Li a una cláusula en la que existen u variables diferentes. ¿Cuántos candidatos deberemos evaluar hasta elegir Li?
NumLit(m,u) = número de literales afirmativos que existen por cada predicado qm de grado m de la BD, candidatos a ser antecedentes de una cláusula en construcción con u variables usadas.
NumPr(m) = número de predicados de grado m (un predicado para cada relación de grado m de la BD)
MaxG = máximo grado de las relaciones de la BD
podemos obtener ya una expresión para el tamaño del espacio de búsqueda o coste teórico:
El factor 2 de esta expresión se debe a que por cada literal afirmativo se considera otro literal negativo.
En la tabla 5-8 se muestran algunos valores de NumLit(m,u) que, como se ve, crecen rápidamente tanto con el grado m del predicado candidato como con el número u de variables usadas en la cláusula.
La expresión exacta de NumLit(m,u) no es sencilla (véase apartado B.2 ), pero se puede acotar fácilmente por su valor máximo, para cualquier predicado de la BD, durante la búsqueda de cualquier antecedente de la cláusula. Si denominamos
TotalPr al número de relaciones de la BD
MaxG al máximo grado de las relaciones existentes
MaxU al número máximo de variables diferentes que pueden ser usadas en cualquier cláusula en construcción
tendremos, en el caso peor, que todos los predicados de la BD son de grado MaxG y que la cláusula en construcción tienen MaxU variables diferentes. En este caso el número de literales afirmativos para cada relación sería
NumLit(MaxG, MaxU) £ (MaxU + MaxG - 1)MaxG[EC. 5.4]
De este modo, se puede obtener una cota superior para el valor de CT asociado a la búsqueda de un literal Li:
CT £ 2 TotalPr (MaxU + MaxG -1)MaxG[EC. 5.5]
Se pueden deducir varias conclusiones de esta expresión:
El mayor valor de CT se alcanza durante la construcción de las cláusulas más largas de una definición (midiendo la longitud por el número de variables que utiliza), especialmente cuando los literales candidatos usan predicados de grado alto. Por ejemplo, en una BD con los predicados lista, vacía y componentes, cuyos grados son 1, 1 y 3 respectivamente, los valores de CT durante la construcción de la regla:
son (según [EC. 5.2] y tabla 5-8 ):
Por tanto, el CT asociado a la construcción de una definición D (número de literales evaluados durante la construcción de sus cláusulas) se puede aproximar por el CT asociado a la búsqueda del último literal de la cláusula más larga, suponiendo que los únicos predicados de la BD son los de mayor grado:
NumPr(MaxG) el número de predicados de la BD con grado MaxG (máximo)
MaxV el mayor número de variables distintas que existen en alguna de las cláusulas de la definición, excluyendo las introducidas por el último antecedente
En el ejemplo anterior, la aproximación [EC. 5.6] daría CTD ª 2 72 = 144 literales, mientras que el valor real es CTD = 24 + 24 + 156 = 204.
Una vez obtenido el tamaño del espacio de búsqueda de literales, se puede calcular el Coste de Evaluación (CE), asociado a la evaluación de cada literal candidato. El CE dependerá del tamaño Ni del conjunto intermedio de tuplas Ti que se considera para la selección del literal Li de una cláusula.
El tamaño de cada conjunto intermedio de tuplas, para la búsqueda de los sucesivos literales antecedentes de una cláusula, depende de los literales seleccionados anteriormente (del predicado con el que se construyen y del número de variables nuevas que introducen). Para estimar el tamaño Ni de estos conjuntos Ti, [Pazzani y Kibler, 92] definen algunos conceptos:
Por ejemplo, para el predicado menor_que, definido sobre los pares de valores <a, b>, donde a y b pertenecen al dominio de los enteros del 1 al 10, valdrá densidad(menor_que) = 45/100 = 0.45
Para un literal Li = q(V1, ..., Vm) que no introduzca variables nuevas, el tamaño del conjunto Ti+1 se podrá estimar como:
Por ejemplo, para el predicado menor_que definido anteriormente, este valor será potencia(menor_que) = 9, y se alcanza para los literales: menor_que(1, V2) y menor_que(V1, 10).
La potencia de un predicado q permite acotar el tamaño del nuevo Ti+1 generado por un literal Li=q(V1, ..., Vm) que introduce nuevas variables:
Por ejemplo, para el predicado menor_que definido anteriormente, la potencia media será potencia_med(menor_que) = 45/10 = 4.5 (aunque menor_que(1, V2) se satisface en 9 casos y menor_que(10, V2) nunca).
Se puede estimar el tamaño Ni+1 del conjunto Ti+1, generado por un literal Li=q(V1,..., Vm) que introduzca nuevas variables:
Haciendo uso de las anteriores definiciones, podremos estimar el tamaño del conjunto de entrenamiento Ti (usado para la búsqueda de Li en una cláusula Ci-1) como:
El tamaño del espacio de búsqueda de literales determina el coste teórico, asociado a la búsqueda de un literal. Este espacio de búsqueda crece del siguiente modo:
El tamaño del conjunto de entrenamiento también puede crecer durante la construcción de una cláusula, pero su tamaño máximo vendrá dado por la potencia de los literales que introducen nuevas variables.
El coste asociado a la evaluación de todos los literales candidatos dependerá del tamaño del espacio de búsqueda y del tamaño del conjunto de entrenamiento.
En algunos casos, especialmente durante la construcción de cláusulas con muchas variables distintas, puede ser necesario explorar espacios de búsqueda muy grandes, resultando muy costosa una búsqueda exhaustiva. Aunque en FOIL se aplican algunos heurísticos de poda ( apartado 2.5.4.3 ), muchas veces no son suficientes para reducir la búsqueda de forma notable, por lo que resulta de interés el estudio de otros heurísticos de búsqueda más eficientes ( apartado 6.2.1.2 ).
Para comparar la complejidad del algoritmo FZFOIL respecto de FOIL, nos fijaremos en los dos parámetros con que se midió la complejidad en FOIL:
Para calcular el coste teórico de FZFOIL, hay que distinguir entre literales ordinarios y borrosos:
Por tanto, la expresión para el coste teórico en FZFOIL es la siguiente:
NumPrOrdinarios(m) = número de predicados ordinarios de grado m (un predicado para cada relación ordinaria de grado m de la BD)
NumPrBorrosos(m) = número de predicados borrosos de grado m (un predicado para cada relación borrosa de grado m de la BD)
NumLit(m,u) = número de literales sin calificador de verdad (sin negar y sin etiqueta lingüística) que pueden construirse por cada predicado de grado m de la BD, con un máximo de u variables usadas (véase apartado B.2 )
MaxG = máximo grado de las relaciones de la BD
NumEtiquetas = número de etiquetas lingüísticas a considerar para cada literal borroso.
Si denominamos CTFOIL al valor de CT obtenido en la expresión [EC. 5.2] , y CTFZFOIL al valor de CT obtenido para FZFOIL ( [EC. 5.16] ), se puede encontrar la siguiente relación entre ambas:
Como el número de etiquetas lingüísticas (NumEtiquetas) que se consideran para cada literal borroso suele ser mayor que dos (el valor 2 correspondería a un literal afirmativo y a su negado), entonces, resulta que el coste teórico es superior en FZFOIL que en FOIL.
La utilización de conjuntos proyectados de tuplas, tal como se hace con el heurístico Interés* en FZFOIL. permite, en algunos casos, no tener que evaluar cada literal Li con todas las tuplas del conjunto Ti. Esto es así porque los parámetros de evaluación se miden en el conjunto proyectado T1[i], en el que cada tupla puede tener varias extensiones en Ti. Si cualquiera de las extensiones de una tupla de T1[i] satisface un literal candidato Li, entonces no será necesario evaluar con el resto de extensiones de la misma tupla. Esta idea es aplicable sólo para literales ordinarios aplicados sobre conjuntos de tuplas no borrosas, pero no para literales y/o conjuntos de tuplas borrosas (la existencia de tuplas y/o relaciones borrosas obliga a evaluar con todas las tuplas, por lo que el CE es el indicado en la [EC. 5.14] ).
Por cada tupla de T1 existirán, en media,
tuplas expandidas en Ti, tal como se deduce de la expresión [EC. 5.14] .
En un conjunto de Ni tuplas, el número medio de tuplas que satisfacen un literal Li, construido con el predicado q, puede calcularse como el producto de la densidad de q ( [EC. 5.8] ) multiplicada por Ni:
En el subconjunto de tuplas expandidas a partir de una concreta de T1, el literal Li será satisfecho, en media, por:
de estas tuplas. Por tanto, si se miden los parámetros de evaluación en el conjunto proyectado, bastará con que Li sea satisfecho por una de estas tuplas para que no sea necesario evaluar con las restantes tuplas expandidas de la misma tupla original.
El número medio de tuplas expandidas a partir de una misma tupla de T1, que deben usarse para evaluar un literal Li (construido con el predicado q) será (puede verse la demostración en el apartado B.3 ):
Partiendo de un conjunto T1 con N1 tuplas, la evaluación de cada literal Li (con el predicado q) se realizará, en media, con un número de tuplas indicado por la siguiente expresión:
Puede obtenerse una estimación del valor de CE medio a partir de la densidad media ponderada por el número de literales candidatos:
qi representa un predicado de la BD
Grado(qi) el grado del predicado qi
NumLit(m,u) el número de literales que pueden construirse para un predicado de grado m con un máximo de u variables usadas ( apartado B.2 )
densidad(qi) la densidad del predicado qi ( [EC. 5.8] )
para la evaluación de cada literal candidato durante la búsqueda del antecedente i-ésimo de una cláusula en construcción, usando el heurístico Interés* con el conjunto proyectado T1[i].
El CE de FZFOIL para literales ordinarios sobre conjunto de tuplas no borrosas nunca puede ser mayor que el calculado para FOIL ( [EC. 5.14] ), ya que el caso peor es la evaluación de todas las tuplas (como ocurre en FOIL).
Para los literales borrosos (o sobre conjuntos de tuplas borrosas) es necesario evaluar con todas las tuplas, por lo que el coste de evaluación es el mismo que se calculó para FOIL ( [EC. 5.14] ). Esto es así porque el grado se satisfacción del literal candidato para una tupla proyectada (del conjunto T1[i]) vendrá dado por el máximo grado de satisfacción con todas las correspondientes tuplas expandidas (del conjunto Ti).
El coste teórico (asociado al tamaño del espacio de búsqueda de literales) de FZFOIL es algo superior al obtenido en FOIL. El crecimiento de este CT se produce del siguiente modo:
La diferencia de CT entre FOIL y FZFOIL consiste en que, en FZFOIL, el factor de crecimiento lineal asociado al número de predicados ordinarios es menor que el asociado al número de predicados borrosos.
El máximo coste de evaluación posible para FZFOIL es el mismo que se calculó para FOIL, por tanto viene limitado por la potencia de los literales que introducen variables nuevas. En el caso particular de que el conjunto local de tuplas sea no borroso y se evalúen literales ordinarios, el coste de evaluación decrece con la densidad de los predicados de la BD.
1. En el caso de seleccionar como relación objetivo una relación definida intensionalmente, es necesario realizar pequeñas modificaciones en el fichero de entrada, para evitar que FZFOIL induzca la misma definición utilizada para construir la relación intensional.
Una forma de conseguirlo es prohibir como "constantes de la teoría" ( apartado C.3.1 ) todos los valores de los dominios utilizados en la construcción de la relación intensional objetivo.
2. Hay que hacer notar que sobre estas definiciones parcialmente construidas no se ha aplicado ningún mecanismo de poda de descripciones, ni ningún mecanismo para eliminar literales redundantes, por lo que no pueden considerarse como los resultados finales del FZFOIL. El objetivo de mostrar estos resultados parciales (después de 60 minutos de ejecución) es el de comparar el proceso de aprendizaje con y sin relaciones borrosas.
Si se ejecutase el algoritmo hasta el final, se aplicarían los mecanismos de poda y, posiblemente, el resultado sería que no existe ninguna definición suficientemente completa y consistente para muchas de estas relaciones objetivo.
3. En este ejemplo se utilizan tres relaciones intensionales pero sólo la primera es relación objetivo. Por tanto, para evitar definiciones infructuosas (tal como se indica en la nota 1. , a pie de página 101. ), basta con prohibir como constantes de la teoría los valores de los dominios utilizados en la construcción de dicha relación objetivo intensional: Id_consulta, Tipo_rest_tte y Tipo_rest_optim.
4. El ejemplo número 5 tiene una LDI algo mayor para el caso borroso, aunque, como ya se ha dicho, no se debe a que la definición borrosa que se construye sea más compleja (realmente es la misma), sino a que cambia la BD de entrada (se consideran 6 relaciones borrosas más).
Esta penalización en la LDI debida al número de relaciones de la BD se está aplicando en todos los ejemplos de tipo b (todos tienen 6 relaciones más que sus equivalentes de tipo a).
5. Con la excepción del ejemplo 5, tal como se explica en la nota a pie de pág. 110.