Sistemas basados en el conocimiento

Dra. Karin supo gavanchoSistemas basados en el conocimientoSistemas basados en el conocimientoLos SBCs (tambin conocidos como sistemas expertos) son programas para interrogar o extender una base de conocimiento (BC):Capacitad de resolucin similar a las de los humanos y utilizacin de las mismas fuentes de conocimiento Dominios especficosOntologa de propsito general para organizar y unir varios dominios de conocimiento especficos.2Caractersticas de BCs y SBCsSeparacin entre el conocimiento y los elementos de control (meta-conocimiento)Incorporacin de la experticia humana en un cierto dominioElevada interactividadInterfaz agradable para el usuario Compatibilidad con informacin no numricaTratamiento de informacin inexactaCapacidad de autoexplicacin y autojustificacin3Caractersticas de los SBCsResuelven un tipo especfico de tareas: requieren una especializacin para realizarlas con competencia (experticia).Llevan a cabo tareas cognitivas.Pueden tomar decisiones aunque el conocimiento sea incierto, impreciso o incompleto.4Tareas cognitivas en las BCs y los SBCsAdquisicin del conocimientoRepresentacin del conocimientoRazonamiento e inferenciaResolucin de problemas y bsquedaInteraccin con el usuario AprendizajeExplicacin5SBCs: definicinSistemas que resuelven problemas:muy especializados (dominio restringido) complejosbasndose en una representacin formal del conocimiento

Problemas para cuya resolucin se confa habitualmente en expertos humanos6Por qu surgieron los sistemas expertos y los SBCs?Necesidades econmicasDisponer de expertos humanos altamente cualificados es caro y no siempre posible.Uso como herramientas baratas de aprendizaje para otros expertos / no expertosPreservacin del conocimiento de los expertosNecesidades de eficiencia computacionalLos mtodos generales de resolucin de problemas son muy ineficientes (mtodos dbiles).7Caractersticas de los problemas resolubles con SBCsNecesidad de que la complejidad del problema justifique el desarrollo del SBCNecesidad de una resolucin expertaProblema bien dimensionado y definidoNo necesidad de razonamiento de sentido comnProblema no fcilmente resoluble con mtodos tradicionalesExistencia de expertos cooperativos (para el desarrollo)8SBCs para tareas de anlisisOrientados a diagnosisDiagnosis mdica, diagnosis de averasOrientados a clasificacinIdentificacin de perfiles de clientes Identificacin de especies animalesOrientados a supervisin/controlSupervisin de procesos en tiempo realOrientados a prediccinPrediccin meteorolgica, de bolsa, de quinielas 9SBCs para tareas de sntesisOrientados a planificacinPlanificacin de trayectorias de robotsOrientados a diseo Diseo de planos de edificios, pisosOrientados a configuracinConfiguracin de redes de ordenadoresConfiguracin de equipos informticosOrientados a construccin de especificacionesConstruccin de especificaciones software10Ventajas ms comunes de los SBCsMuy eficaces en tareas de anlisis: diagnosis, clasificacin, interpretacinCon capacidad de autoexplicacinCon facilidad de comunicacin con el usuarioFcilmente extensibles Con capacidad de razonamiento aproximado11Inconvenientes ms comunes de los SBCsProblemtica de la adquisicin del conocimiento Fragilidad / sensibilidadDificultad con el control del razonamiento Problemtica de la validacin de las reglasBajo coeficiente de reutilizacin de las reglasIncapacidad de aprender12Historia de los sistemas expertos y de los SBCsLos ms antiguos 1965DENDRAL (1965-1970)Interpretacin de espectrografa de masa y resonancia magntica de molculas orgnicasMETA-DENDRAL (1970)Construccin de regles heursticas a partir de datosMACSYMA (1971-1977) @ MITManipulacin de frmulas algebraicas13Historia de los sistemas expertos y de los SBCsMYCIN (1972-1976)Diagnosis de enfermedades infecciosas en la sangre400 reglasRazonamiento con incertidumbre HEARSAY-II (1975) @ Carnegie-MellonInterpretacin del LN (hear + say)1000 palabrasEMYCIN (1980)Generaliza el sistema de control de MYCINPrimer entorno de SE (shell)14Historia de los sistemas expertos y de los SBCsPROSPECTOR (1977)Prospecciones minerasOtro mtodo de razonamiento con incertidumbreR1/XCON (1980) @ DECSistema de configuracin de entornos computacionales en Digital Equipment Corporation200.000 reglasINTERNIST (1982)Diagnosis en medicina interna1.000.000 reglas15Historia de los sistemas expertos y de los SBCsCENTAUR (1983)Diagnosis de infecciones pulmonaresMOLE (1986)Entorno de SE para clasificacinTEST (1987)Localizador de averas (Troubleshooting Expert System Tool)Diagnosis / clasificacinVT (1988)Diseo de sistemas elevadores (Vertical Transportation)16Historia de los sistemas expertos y de los SBCsGuerra del Golfo Prsico (1990-1991)Cargamento de aviones de transporteProgramacin y coordinacin de la operacin Tormenta del Desierto Proyecto Pilot's Associate (copiloto electrnico)Proyecto Battle Management System (sistema experto militar) Ingeniera gentica (90s)Manipulacin de BCs gigantescas para hacer mapas del ADN humano (bioinformtica)Deep Blue (1997) @ IBMIBM RS/6000 SP de 32 nodos con computacin altamente paralela gana a Gary Kasparov.17Historia de los sistemas expertos y de los SBCsRemote Agent (1999)Control primario de una nave espacial (Deep Space 1) por primera vezAplicaciones de sistemas expertos (00s)Software de ordenacin de tareas para crear automticamente mejores planificaciones de proyectoPrograma de reconocimiento continuo del discurso que transforman exactamente el habla en textoSoftware para gestionar la informacin, que encuentren slo los documentos necesitados en cada momento entre millones de documentos y automticamente los resumanSistemas de reconocimiento facialLavadoras que se ajustan automticamente a diferentes condiciones de lavadoSistemas automticos de evaluacin de hipotecas18Componentes de SBCHechosReglasPlanAgendaSolucionExplicacinIntrpretePlanificadorMantenimientoconsistenciaInterfazusuariopizarraBase de conocimientousuarioInterfaz de usuario: El usuario interactua con el SE en un lenguage prpio del tipo de problema, con frecuencia un espaol restringido y en algunos casos mediante algn grfico o formularioLa pizarra: almacena hiptesis y decisiones intermedios que el sistema mani- pula. Pocos sistemas representan de forma explcita estos elementos - Plan:Plan general de solucin del problema. Ejemplo primero procesar todos los sensores, 2) Formular un nmero pequeo de hiptesis, 3) Refinar y elaborar cada una de las hiptesis hasta que una sea la ms prometedora. - Agenda : Reglas relevantes para la situacin en curso.- Solucin: Hiptesis candidatas y decisiones generadas hasta el momentoEl planificador: Determina cual es la accin pendiente que se ejecutar a continuacin. Da a cada elemento de la agenda una prioridad e acuerdo con el plan y las soluciones alcanzadas.El intrprete: Ejecuta la regla escogida por el planificador.Manteniemiento de la consistencia: Mantiene una representacin consistente de la solucin medianteRevisin de la probabilidad de una solucin cuando se introducen nuevos hechosSistemas de mantenimiento de la verdad cuando las soluciones son deducciones logicas El modulo de explicacin: Explica el porque de las acciones del sistema al usuario.Reglas y hechos: Registran reglas, hecho e informacin del problema.

Explicacin componentesInterfaz de usuario: El usuario interacta con el SE en un lenguaje propio del tipo de problemaPizarra: almacena hiptesis y decisiones intermedios que manipula el SE Plan: Plan general de solucin del problema. Agenda : Reglas relevantes para la situacin en curso.Solucin: Hiptesis candidatas y decisiones generadas hasta el momentoPlanificador: Determina cual es la accin pendiente que se ejecutar a continuacin. El intrprete: Ejecuta la regla escogida.Mantenimiento de la consistencia: Mantiene una representacin consistente de la solucin mediante:Revisin de la probabilidad de una solucin cuando se introducen nuevos hechos.Sistemas de mantenimiento de la verdad cuando las soluciones son deducciones lgicas El modulo de explicacin: Explica el porqu de las acciones del sistemaReglas y hechos: Registran reglas, hecho e informacin del dominioComponente de ExplicacinUn SE debe contar con una componente de explicacin La respuesta puede ser potencialmente dainaEs una forma comprensible de chequear el comportamientoTutores

Una componente de SE debe idealmentePoder responder a preguntas como las siguienteCmo se tom o no cierta decisin? Cuando, cmo y porqu se utiliza una informacin determinada? Qu decisin se tomo ante un subproblema? Ser fcil de usarDar respuestas comprensibles y completasR.I.P.SEProgramas convencionales y SBCProgramas: Sentencias sobre datos que se realizan en un orden predeterminado.Solucin nicaPara el usuario el programa es una caja negraSBC = Conocimiento + ControlProgramas = Estructuras de Datos + AlgoritmosSBC: Se distingue el conocimiento del dominio de la estrategia de controlEsto permite la incorporacin de ms conocimiento sin manipular la estructura global del sistemaSe pueden obtener varias solucionesEl programa puede explicar como llega a su solucin.Desarrollo de un SBCSe pueden clasificar las aplicaciones de SEs sobre la base de caractersticas de las tareas o del dominio?Se pueden identificar mtodos de resolucin de problemas bien diferenciados que sean tiles para ciertas clases de aplicaciones de SEs?Podemos identificar estilos de representacin e inferencia ms adecuados para un mtodo de resolucin de problemas dado?Definicin delProblemaSolucinEspecificacinDiagnsticoConfiguracinClasificacin...Objetivosy datosAbstraccionesSimulacincualitativa...HeursticasRelacionescausalesCuantitativaOrientada a ObjetoBasada enreglas..Niveles de descripcinEspecificacinTareaMtodo de resolucinBase de conocimientoHerramientaSeleccionartipo de problemaSeleccionarmtodoSeleccionarRepresentacinSeleccionarparadigma Niveles de descripcin El desarrollo de un SBC puede verse como un proceso de transformacin desde el nivel de especificacin al de herramientaNivel de Especificacin: Se describe el problema, las restricciones sobre el problema y la solucin. Nivel de Tarea: Se describe los tipos de problemas, como diagnstico, planificacin, etc.Nivel de resolucin del Problema: Estrategias de resolucin que se utilizan para resolver las diferentes tareasNivel de Base de conocimiento: Heursticas, asociaciones causales, relaciones matemticas describiendo fenmenos fsicos.Nivel de Herramienta: Implementacin del SBCClasificacin de las tareas Clasificacin de Hayes-Roth y col (1983)Interpretacin: Anlisis de datos para determinar su significado. Con frecuencia la informacin lleva asociada incertidumbrePrediccin: Inferir el futuro a partir de situaciones o eventos. Por ejemplo, prediccin del tiempo o prediccin financiera.Diagnstico: Deduce fallos a partir de sntomas. Incluye un amplio espectro de aplicaciones mdicas, mecnicas, y electrnicas.Diseo: Desarrolla configuraciones de objetos que satisfacen ciertas restricciones. Por ejemplo, diseo de circuitos, o disposicin de maquinaria en un espacio reducido.Planificacin: Genera secuencias de acciones para lograr objetivos.Monitorizacin: Observacin del comportamiento del sistema.Depuracin y Reparacin: Generar remedios para fallos de sistemas. Instruccin: Sistemas tutoresControl: Se anticipa a problemas, planifica soluciones y monitoriza.Clasificacin por operaciones genricasClancey (1985) Propone un anlisis alternativo en trmino de operaciones genricas sobre el sistema:Operaciones sintticas que construyen un sistemaOperaciones analticas que interpretan un sistemaDiagnsticoInterpretacinPlanificacinControlMonitorizacinEducacinSimulacinDiseoanalticasConstructivasClasificacinDatosDatos AbstraidosSolucionesAbstraidasSolucionesAbstraccinDatosEmparejamientoRefinamientoSolucinClasificacin: Proceso que selecciona soluciones, entre un conjunto de soluciones preestablecidas, a partir de datos reconocidos. Se utiliza en gran cantidad de tareas como diagnstico de enfermedades o evaluacin prospectiva de depsistos de minales.ConfiguracinEspecificacionesSubmodelofuncionalidadesEmparejamiento especificacin/estructuraConfiguracin:Selecciona partes y los junta. Se utiliza para construir planes de fabricacin o recomendaciones de terpiasSubmodelode PartesSolucionesAbstraidas y parcialesSolucionesRefinadas y ExpandidasSubmodelode configuracinEspecificacionesAdicionalesEspecificacionesEspacio de configuracinNivel de resolucin de ProblemasTcnicas de resolucin y arquitecturasBasadas en BsquedaSimple*Profundidad*Anchura*Genete-and-Test*Satisfaccin restricciones*AleatoriaJuegosNo Estoctica

*Escalada*Primero el mejor* A*EvaluacinEstoctica

*Simulated Annealing*Algo. Genticos*FC*Bayes*Fuzzy*Dempster-Shaper

InexactoOtrosBasadas en el Conocimiento*Forward Chainig*Backward Chainig*Prueba Teoremas*GPS (MEA + OS)Objetivos y datos*TMS*Manejo restriccionesMantenimientoconsistencia*Refinamiento Jerrquico*Heuristic-inc- generate&test

AbstraccionesNivel de resolucin de ProblemasBsquedasBsquedas ciegaDireccin: Dirigida por objetivo, Dirigida por datos, BidireccionalOrden sistemtico de visita de nodos: Profundidad y AnchuraBsqueda heursticaInformacin especfica del dominio que gua la bsqueda Funcin de evaluacin que da una estimacin del esfuerzo que supone seguir un camino.Las funciones de evaluacin deben caracterizar el espacio de estados adecuadamente Es engaoso pensar que una simple funcin aritmtica como estilo de representacin del conocimiento es suficiente. Los sistemas expertos utilizan grandes cantidades de conocimiento simblico..f(n) = d(n) + h(n)Razonamiento Basado en el ConocimientoRazonamiento basado en el conocimientoEl razonamiento basado en el conocimiento suele ser no montonoRequiere razonar con conocimiento imprecisoConsiderar Justificaciones y hacer tentativas sobre creenciasEste razonamiento dinmico requiere gran cantidad de conocimiento

regla 101Si huele a queso por aqui y no veo trampasentonces merodear cerca

regla 103Si ya he pasado por aqui entonces intentar otra alternativa

comida queso Emmental BolaRazonamiento BC (cont.)Suposiciones y compromisosLos expertos actan con recursos de tiempo y conocimiento limitadoEl sentido comn permite extraer conclusiones a partir de informaciones parciales, y la gente acepta conclusiones aceptables para las cuales no tiene prueba.El sentido comn requiere que el sistema sea capaz de revisar sus creencias a la luz de nueva informacin=> Razonamiento No monoto

Sistema de razonamiento no montonoDependencias y JustificacionesPara revisar sus creencias frente a nuevas informaciones, el resolutor debe razonar sobre dependencias entre sus creencias.Estas tcnicas son una extensin del backtraking en bsqueda Un fallo en la bsqueda da lugar a backtracking: Eliminacin de todas las acciones e inferencias desde el punto de eleccin ms reciente y continuar con la siguiente alternativa.Debido al orden LIFO del backtraking la memoria de las creencias activas se puede implementar como una pila.Backtraking cronolgico es ineficiente porque la razn del fallo se olvidan cuando se abandona el caminoEjemplo del robot RobieEl robot tiene como objetivo coger un bloque. Levanta la mano derecha. Se mueve hasta donde est el bloque. Coge el bloque con su mano derecha, pero est muy calienta y se quema la mano. Deja el bloque, baja la mano y retrocede. Levanta la mano izquierda, se mueve hasta donde est el bloque. Coge el bloque con su mano izquierda, pero ...Desafortunadamente, en muchos dominios de problemas no es posible crear modelos completos, consistentes e inalterablesLa historia del asesino ABC ilustra con claridad muchos aspectos fundamentales que estas tcnicas deben proporciona [The Web of Belief de Quine y Ullian 1978]:

Sean Abbott, Babbitt y Cabot los sospechosos en un caso de asesinato. Abbott tiene una coartada en el registro de un respetable hotel de Albany. Babbitt tambin tiene una coartada, la de su cuado, al cual estaba viendo en Brooklyn en el momento del crimen. Cabbott defiende tambin su coartada, asegurando que se encontraba viendo un campeonato de esqu en Catskills, pero slo puede aportar su propio testimonio. Por lo tanto, creemos:(1) Que Abbot no cometi el crimen(2) Que Babbit no lo hizo(3) Que o Abbott o Babbitt o Cabot lo hizo Sistema de razonamiento no montonoEn principio el sospechoso principal es Cabot, pero ... ... Cabot puede posteriormente presentar pruebas de su coartada. Tuvo muy buena suerte y fue captado por las cmaras de TV en las gradas de la pista. De esta forma aparece una nueva creencia que es:

(4) Cabot no lo hizo.Las creencias (1) a (4) son inconsistentes, por lo que una debe desestimarse. Cul es la evidencia ms dbil?La base de (1) en un hotel es buena, ya que se trata de un hotel prestigioso.La base (2) es ms dbil, ya que puede ser que el cuado de Babbitt est mintiendo.La base de (3) es doble: No existen signos de robo y slo Abbott, Babbitt y Cabot parecen salir beneficiados con el asesinato.La base de (4) es concluyenteSistema de razonamiento no montonoDependencias y JustificacionesSe debe seguir la pista de los pasos de inferencia que dieron lugar a errores e inconsistenciasRegistro de los paso inferenciales => Registros de dependencia Un mtodo de bsqueda que analice dependencias y decide qu invalidar se llama no cronolgica o dirigida por dependencias.Elementos de los registros de dependencia: Creencias, reglas de inferencia y justificacionesSi se encuentra que q es falso el sistema permitir eliminar p o ( p v q)qjustificacinverdadv p v qreglavpvqvp v qjustificacinverdadvpjustificacinverdadvTcnicas de razonamiento AvanzadasRazonamiento basado en el modeloRepresentan los sistmas fsicos mediante su estructura y funcionalidad. Razona utilizando principios bsicos de ingeniera y cienciasTipos de modelos: Ecuaciones, Estocsticos, y modelos causales (Centrados en dispositivos).Conocimiento profundo en lugar de conocimiento superficial sobre el comportamiento del sistema.EJEMPLO Aplicacin tpica: Diagnstico de circuitos digitales. Un tcnico de reparacin de televisores expertimentado utiliza: *Unas pocas medidas en los dispositivos * Con su conocimiento de dispositivos puede mirar un esquema de la televisin e identificar el componente que fallaTcnicas de razonamiento AvanzadasRazonamiento CualitativoSimulacin cuantitativa: Modelado del comportamiento exacto mediante la descripcin completa y determinista de sus parmetros.Simulacin cualitativa de un sistema: Determina slo sus posibles estados generales basndose en algunas restricciones.Razonamiento basado en casosObjetivo: Reemplazar el conocimiento de un experto con una base de datos de casos Proceso de desarrolloAdecuacin de una aproximacin basada en el conocimientoNo hay una solucin algortmicaLa tarea del dominio la realizan expertosLos expertos no son simples aficionadosLa tarea no debe ser ni muy difcil ni muy complicada para el expertoEl problema no debe requerir sentido comnLa utilizacin del SBC reportar beneficiosProceso de desarrolloIDENTIFICACINCules son las caractersticas del dominio?Cul es su mbito?Quienes participarn y con que recursos?CONCEPTUALIZACINQu informacin y tcnicas utiliza el experto?FORMALIZACINCmo encajan estas tcnicas en las estructurasy estrategias de los sistemas expertos?IMPLEMENTACINAcquiere y comprueba iterativamente las habilidades del sistemaCHEQUEOTest de comprobacin finalProceso de desarrolloPasos principales:Identificacin: Caracterizacin de los aspectos ms importantes del dominio del problema Conceptualizacin: Se extraen los conceptos, subtareas y restricciones necesarias para resolver el problema.Ingeniero del Conocimiento: Persona que traslada el conocimiento de un experto a algn formalismo.Es til un modelo conceptual (mental) entre el experto y el implementador.ConocimientodelExpertoif p(x) ^ q(x, y)then r(y)

if u(x) ^ v(x, y)then s(y)

if r(x) ^ sq(x, y)then t(y)motor de inferenciaModeloConceptualSistema ImplementadoAdquisicin del conocimientoProgramacinProceso de desarrolloFormalizacin: Los conceptos de la etapa de conceptualizacin se representan con las herramientas y esquemas de representacin disponibles.Herramienta de adquisicin?, chequeos de la base de datos?, Reglas? Redes semnticas?, Frames?, Esquema de razonamiento?, Mdulo de explicacin? ...Implementacin:Desarrollo de una herramienta de propsito especficoUtilizacin de algn shell para el desarrollo de SEs.Verificacin y refinamiento:El prototipo es comprobado con el experto.Proceso de desarrolloDos aproximacionesPrototipado:Es el mtodo ms popular para el desarrollo de SBC- Depende mucho ms de la involucracin de los usuarios- Necesidad de comprobar el comportamiento del sistema segn se desarrolla- Adquisicin del conocimiento y desarrollo del software se pueden combinar en el prototipadoProblemas: Desarrollo ad hoc e indisciplinadoEstructurado:KADS (Knowledge Acquisition and Design process): - Metodologa de modelado, con una fase rigurosa de anlisis antes del diseo- El prototipado se utiliza para experimentar, no como metodoga

HerramientasCmo hacer una tareaQu tarea hacerLispCAdaReglas OPS5Lgica: PROLOGObjetos: Smalltalk-80 C++ JavaLenguajes tradicionalesUn paradigma de programacinIntegran distintosparadigmasLOOPSCLIPSK-CRAFTARTNEXPERTKAPPACLOS

KEEVPEXPERTPC+Shells