Bienvenidos a la materia Inteligencia Artificial
|
|
Los objetivos de la materia son:
Introducir a los alumnos en los
conceptos básicos de la IA vinculados con la resolución de problemas y la
representación de conocimiento y razonamiento. Estos conceptos se describen más abajo y
constituyen, como allí se señala, un subconjunto de los conceptos más
importantes de la disciplina.
Introducir a los
alumnos en los métodos de trabajo típicos de una ciencia empírica. Se
introducirán los conceptos y métodos de la investigación empírica exploratoria y
experimental, y se aplicarán al estudio de un conjunto de problemas y
algoritmos. Se emplearán también métodos analíticos para la exploración y
experimentación de esos mismos problemas y algoritmos, y para el estudio de
algunos problemas de representación de conocimiento y razonamiento.
La materia se basa en uno de los dos enfoques o "paradigmas" extremos de la IA. Estos enfoques extremos son el simbólico y el no simbólico. El primero privilegia la definición y operación con símbolos como forma esencial de trabajar en IA y el segundo utiliza una aproximación no simbólica (en general numérica) hacia más o menos los mismos problemas. Existen también algunas otras posturas intermedias. En la materia adoptaremos el paradigma simbólico. La asignatura Redes Neuronales, también del área, es un claro ejemplo del enfoque opuesto. Resulta bastante enriquecedor para quien se interese por la problemática de la IA cursar ambas materias, aunque quizá no simultáneamente.
Los temas que trataremos en la materia corresponden a dos de sus subdisciplinas básicas, la Resolución de Problemas y la Representación de Conocimiento y Razonamiento. La tercera subdisciplina básica, el aprendizaje automático, se trata en una materia separada con ese mismo nombre.
Resolución de problemas
La IA estudia problemas considerados computacionalmente difíciles. Pero no debe confundirse el estudio de esos problemas (en muchos casos realizado por distintas "ramas" de la IA), que más que problemas son "áreas problemáticas" (o dominios) conformadas por múltiples problemas relacionados, con la subdisciplina particular de la IA denominada "resolución de problemas" (Problem Solving, PS), cuyo objeto de estudio es la resolución de problemas en sus cuestiones generales haciendo abstracción, tanto como sea posible, de los dominios particulares. En este sentido, PS pretende resolver el problema de "cómo resolver problemas". Esta subdisciplina plantea un equilibrio difícil porque se reconoce que una de las pocas maneras de resolver problemas difíciles, y una manera que la IA privilegia, es la incorporación y utilización de conocimientos específicos del problema y del área a la que pertenece. Sin embargo, en el estudio abstracto de la resolución de problemas importa estudiar los modos de utilizar conocimiento pero haciendo la mayor abstracción posible de conocimientos determinados de áreas específicas, trabajando, a lo sumo, con propiedades de esos conocimientos y su relación con la representación y resolución.
La resolución de problemas es uno de los temas de estudio fundamentales de la IA y uno de los primeros históricamente. Puede decirse que, dentro de la IA, los términos "resolución de problemas" o también "búsqueda" refieren a un gran cuerpo de ideas centrales que otras áreas características de esta misma disciplina, como la representación de conocimiento y razonamiento, la planificación, el aprendizaje y otras, tienen en común. Un investigador fundador de la IA y premio Nobel en economía, Herbert Simon, dijo en 1983 lo siguiente respecto de la relación entre búsqueda y razonamiento: “Una lógica, tomada en sí misma, puede ser considerada un algoritmo no determinístico para encontrar todas las consecuencias de un conjunto de premisas... a la lógica debe proporcionársele algún tipo de estructura de control. Debe agregársele una estrategia de búsqueda... En este sentido, los procesos de razonamiento son un subconjunto de los procesos de búsqueda; el subconjunto que utiliza reglas de inferencia como los únicos operadores”. Podemos adoptar la misma concepción de Simon para otras “tareas” de la IA: el aprendizaje consiste básicamente en buscar la representación general más apropiada (hipótesis) dentro de un espacio de hipótesis alternativas, la planificación consiste en buscar un plan satisfactorio dentro de un espacio de planes, la comprensión del lenguaje natural en encontrar el significado más probable o verosímil de la emisión de un hablante dentro de un espacio de significados posibles, etcétera. Las aplicaciones de las ideas generales de búsqueda pueden verse en cualquier área de la IA y también más allá (en otras disciplinas): en aplicaciones como el procesamiento del lenguaje natural, la identificación de secuencias moleculares, la criptografía, el diseño industrial, el reconocimiento de patrones, y muchas otras.
Dos investigadores italianos definieron la resolución de problemas como tema de investigación de la IA del siguiente modo: “El objetivo de la resolución de problemas es el desarrollo de métodos eficientes que proporcionan a la máquina la capacidad de obtener, por medio de un proceso mecánico, la solución de un problema propuesto a la computadora de un modo apropiado”. (Vincentelli y Somalvico, 1979, p. 16).
Un prerrequisito para tratar con el mundo real es tener la capacidad de manipular un arsenal de técnicas de resolución de problemas. Estos son algoritmos que fueron desarrollados para una variedad de condiciones. Pero debe recordarse que el mundo real siempre presenta situaciones que son, en alguna medida (mayor o menor), diferentes de las requeridas por los métodos. Por lo tanto, para juzgar la aplicabilidad de uno u otro método es preciso conocer lo que cada método de resolución de problemas presupone, sus propiedades computacionales y otras.
La tarea de resolución de problemas implica, además de los métodos para representar y resolver problemas, una tercera cuestión importante que involucra al sistema que concretamente realiza la resolución. Cualquier sistema real (una persona o un sistema computacional) posee recursos de diverso tipo (tiempo, memoria, atención, etc.) que puede asignar o no (y según alguna modalidad) a la tarea de resolución de problemas. En cualquier situación real de resolución de problemas no se puede desconocer este tema (no hay resolución posible sino). Sin embargo, con fines didácticos, vamos a separar esta última cuestión de las anteriores.
Vamos a suponer inicialmente una situación “ideal” (recursos no limitados o sistemas “universales”) y dentro de este marco estudiaremos un enfoque particular de la resolución de problemas. Este consiste en descomponer la resolución de problemas en dos tareas: representación + búsqueda. En el contexto de esta materia introductoria nos vamos a restringir a familias de problemas definibles de un modo más o menos natural mediante un grafo rotulado ordinario. Los algoritmos de búsqueda planteados serán fundamentalmente algoritmos heurísticos de optimización o semioptimización definidos sobre grafos ordinarios. Esta área es lo que tradicionalmente se denomina "búsqueda en espacio de estados". Si bien esta restricción reduce considerablemente el conjunto de problemas, métodos y algoritmo disponibles en IA (temas importantes como los problemas de satisfacción de restricciones, los problemas multiobjetivo, las búsquedas en hipergrafos, y otros tantos quedan afuera) todavía nos permite presentar y estudiar los conceptos y métodos fundamentales que están presentes también en las otras áreas.
En el contexto de la restricción planteada vamos a estudiar un conjunto de problemas típicos de la IA y del área de optimización combinatoria: n-puzzle, TSP simétrico y asimétrico, y satisfacibilidad booleana máxima. También introduciremos algunos otros problemas, principalmente en las prácticas. Los algoritmos que estudiaremos pertenecen a la clase de algoritmos "branch and bound" y a distintas subclases, como los algoritmos de soluciones exactas vs. aproximadas, globales vs. locales y "anytime". Posteriormente estudiaremos las principales propiedades de los problemas y algoritmos tratados, haciendo uso de herramientas de las teorías de complejidad analítica y empírica. Vamos a poner especial énfasis en el estudio de las transiciones de complejidad computacional. Posteriormente se tratarán tres temas importantes para la utilización práctica de los algoritmos de búsqueda: la selección de un algoritmo apropiado a un problema, la transformación de la representación de problemas, y la aplicación de la computación flexible y de recursos limitados a la resolución de problemas. Para el desarrollo de estos temas se utilizará como bibliografía básica obligatoria el texto de Weixiong Zhang, State-Space Search - Algorithms, Complexity, Extensions and Applications. Springer, Nueva York, 1999.
Para los trabajos prácticos, en particular la exploración y experimentación con conceptos y algoritmos utilizaremos la familia de problemas denominada de "pequeño mundo" (small world) y como software MATLAB. Como bibliografía de consulta para los aspectos metodológicos podrá utilizarse el texto de Paul R. Cohen, Empirical Methods for Artificial Intelligence. MIT Press, 1995.
Representación de conocimiento y razonamiento
El área de representación de conocimiento y razonamiento (KR&R) trata fundamentalmente del problema de desarrollar principios, conceptos y técnicas, tanto generales como específicas, para representar, mantener y manipular conocimiento en dominios particulares. Es una de las subdisciplinas históricamente más importantes de la IA, junto con la resolución de problemas. Se cree en general que para que un agente pueda actuar de forma inteligente debe tener el conocimiento apropiado y debe poder razonar con él.
Además de su centralidad en IA, KR&R tuvo una influencia importante en la computación en general. El desarrollo de los lenguajes orientados a objetos y los lenguajes de especificación diseñados con Prolog como modelo son dos ejemplos de esta influencia. Morgenstern y Thomason (2000) dicen que “Un buen curso de KR puede ser un “abridor de ojos” intelectual. Ofrece a los estudiantes una excelente oportunidad – frecuentemente única – de ver cómo interactúan las ideas de la ciencia de la computación con el desarrollo de sistemas. Los estudiantes típicos de ciencia de la computación llegan a su primer curso de IA con buenas destrezas de programación y una razonable cantidad de experiencia en proyectos de pequeña escala. Pero sin KR, es improbable que comprendan la importancia de analizar la tarea de razonamiento que enfrentan, de separar los elementos declarativos, o de modularizar el diseño del sistema. KR no solo sirve como un tema importante por derecho propio, al introducir los temas de investigación tradicionalmente cubiertos por KR, sino que también hace posible la transición de una comprensión ingenua a una más sofisticada del diseño de sistemas”. Sandewall (2000) compara el papel de la representación de conocimiento en IA y la ciencia de la computación en general con el del análisis matemático en ingeniería: ambos serían herramientas conceptuales y notacionales para modelizar fenómenos. Morgenstern y Thomason (2000) sostienen que KR&R es importante para un currículo equilibrado y exitoso de ciencia de la computación, principalmente debido a que sería uno de los modos más eficientes de ilustrar la importancia de las ideas científicas en el desarrollo de software.
Una cuestión central de KR&R es la representación del conocimiento mediante algún lenguaje formal que permita controlar efectivamente qué conocimiento se representa y de qué forma se lo procesa, es decir, se produce nuevo conocimiento mediante la utilización de alguna forma de razonamiento (inferencia). Es por esto que las herramientas y conceptos de la lógica son instrumental y conceptualmente muy importantes en KR&R. Sin embargo, no deben confundirse las teorías y programas de investigación de cada una de estas disciplinas.
Luego de la revisión de algunos conceptos y herramientas lógicas fundamentales, y de una formulación de cuestiones generales de representación de conocimiento, se planteará la necesidad de utilizar lenguajes "fuertes", es decir, lenguajes formales con un contenido semántico fijo vinculado a conceptos generales necesarios para cualquier teoría de KR&R. Para ello estudiaremos algunas propuestas y conceptos vinculados a la incorporación de teorías ontológicas. Luego se plantearán las características del llamado conocimiento y razonamiento de "sentido común" que es particularmente difícil de formalizar mediante las herramientas lógicas clásicas. Para el estudio de esta cuestión se adoptará la perspectiva de la programación lógica aplicada al llamado "razonamiento no monotónico". Se estudiará la solución de compromiso entre expresividad y complejidad computacional, y las características sintácticas y especialmente semánticas de distintas extensiones del lenguaje clausal definido como formas de tratar con algunas características importantes del razonamiento de sentido común. Finalmente se considerarán algunas aplicaciones de esta problemática a situaciones más "realistas" (menos idealizadas) con sistemas de recursos limitados. Debido a que no existe un texto que reúna el conjunto de los temas planteados, usaremos como bibliografía algunos artículos citados en el cronograma y en el listado bibliográfico.
Para los trabajos prácticos nos concentraremos en la familia de problemas llamada de "sentido común" (common-sense problems) y utilizaremos el lenguaje Prolog para la experimentación sobre la formalización de esa clase de problemas y el razonamiento no monotónico.
La materia es promocional, lo que significa que para aprobarla debe tener como mínimo 7 en cada una de las evaluaciones parciales. Las evaluaciones parciales son cuatro: dos exámenes parciales y dos trabajos prácticos que deberán entregar.
Quien haya obtenido una nota en el intervalo [4,7) en los exámenes parciales podrá examinarse nuevamente en el recuperatorio correspondiente a fin de alcanzar un 7 o más para promocionar.
Quien no satisfaga las condiciones de arriba deberá aprobar los TP con un mínimo de 4 en ambos exámenes parciales, 7 en los trabajos a entregar y deberá rendir un examen final.
Quien no reúna las condiciones anteriores le restan dos alternativas: rendir la asignatura libre o recursarla. Para rendir la asignatura como libre deberá, como es tradicional, rendir un examen escrito y, de aprobarlo, rendir un examen oral, pero previamente deberá haber entregado los dos trabajos prácticos. En los dos exámenes (escrito y oral) el contenido a evaluar es toda la materia; el examen escrito tiene un carácter algo más práctico que el examen oral.
En cuanto a los que optan por recursar la materia. se recomienda que no asuma que en su recursada se dictarán exactamente los mismos temas, del mismo modo, con las mismas prácticas, etcétera. Es fundamental que se mantenga actualizado respecto de los temas, etc. del nuevo curso, sobre los que, en definitiva, se lo examinará.
Clases teóricas: Las teóricas se dictarán los
jueves de 19 a 22 hrs. La asistencia no es obligatoria. En ellas se explicarán
los conceptos fundamentales, se aclararán temas de índole teórica y se
complementarán los temas de la bibliografía. En la medida de lo posible suele
ser beneficioso una primera lectura de la bibliografía correspondiente al tema
de la clase antes de la misma
Clases prácticas: Las clases prácticas se realizarán los martes de 19 a 22, en lo posible en
laboratorio. Se tratarán temas prácticos, se ejercitará en la representación y
resolución de problemas, se realizará ejercitación y experimentación utilizando
el software apropiado (en principio Matlab y Prolog).
Correo electrónico: Pueden utilizar la lista de correo electrónico de la materia (ia-alu@listas.dc.uba.ar) para hacer consultas de
cualquier tipo en cualquier momento.
Las evaluaciones son las siguientes: exámenes parciales, trabajos prácticos a entregar, exámenes recuperatorios, exámenes finales.
Exámenes parciales: Existen dos exámenes parciales, el
primero sobre la primera parte de la materia (resolución de problemas) y el
segundo sobre la segunda parte (representación de conocimiento y
razonamiento). Son de carácter teórico-práctico. Algunas evaluaciones
típicas consisten en la demostración de alguna propiedad o resultado, algún
multiple-choice con justificación de respuesta, la ejecución manual de
algoritmos, etcétera. Puede ser a libro abierto o cerrado según se indique en
el momento oportuno. En el
Cronograma de la materia podrán encontrarse links a muestras de
parciales de años anteriores.
Trabajos prácticos a entregar: Estos trabajos tienen el objetivo de suministrar una experiencia
práctica en algunos de los grandes temas y métodos de la materia. También son útiles para
reforzar la comprensión teórica. Existen dos trabajos, uno para cada gran tema.
Cada entrega debe estar acompañada de la
documentación apropiada.
Exámenes recuperatorios: Existen dos recuperatorios, uno por cada parcial. Los temas
y modalidad de evaluación son similares a los de los parciales y suelen
realizarse a fines del cuatrimestre.
Los exámenes
finales pueden ser de dos tipos: exámenes para alumnos regulares y
exámenes para alumnos libres. Los primeros son escritos y cubren la totalidad
de la materia. Los exámenes para alumnos libres son dos: uno escrito y otro
oral. Todos los exámenes finales escritos tienen características formales
similares entre sí y semejantes a las de los exámenes parciales. El examen oral
está constituido por una exposición sobre temas solicitados.
La bibliografía, tanto la de lectura obligatoria como de lectura optativa, se encuentra detallada en el Cronograma.
Docentes a cargo de la materia
Profesor
a cargo: José Angel Alvarez
(jalvarez@dc.uba.ar)
Auxiliares docentes: Martín Irigoyen
(emirigoyen@hotmail.com) y Angeles Grieco (agrieco@nap.com.ar)