Archive for the ‘Ciencias Computacion’ Category:
Goal-Driven y Busqueda a lo ancho
Conducida por el objetivo (goal driven – backward chaining)
- Tomar el objetivo que queremos resolver, establecer que reglas o movimientos legales podrían usarse para generar este objetivo y determinar que condiciones deben ser verdaderas para ser usadas.
- Estas condiciones constituyen los nuevos objetivos de la búsqueda y la búsqueda continua hacia atrás hasta encontrar los hechos del problema
BREATH FIRST.- Busqueda a lo ancho. La busqueda se realiza a lo largo del arbol o grafo, recorriendo todos los nodos de una correspondiente fila antes de pasar a la siguiente:
Este es una implementacion en pseudocodigo el cual representa el comportamiento de esta estrategia de busqueda:
Begin
open := [Start];
closed := [ ];
while open ? [ ] do
begin
remove leftmost state from open, call it X;
if X is a goal then returns SUCCESS
else begin
generate children of X;
put X on closed;
discard children of X if already on open or closed;
put remaining children on right end of open
end
end
return FAIL
end
Aplicacion en un arbol, donde el objetivo a encontrar es U
1. open = [A]; closed = [ ]
2. open = [B,C,D]; closed = [A]
3. open = [C,D,E,F]; closed = [B,A]
4. open = [D,E,F,G,H]; closed = [C,B,A]
5. open = [E,F,G,H,I,J]; closed = [D,C,B,A]
6. open = [F,G,H,I,J,K,L]; closed = [E,D,C,B,A]
7. open = [G,H,I,J,K,L,M] L ya esta en open; closed =[F,E,D,C,B,A]
8. open = [H,I,J,K,L,M,N]; closed = [G,F,E,D,C,B,A]
9. Continua hasta encontrar U, o open = [ ].
Estrategias de Busqueda
Tipos de búsqueda según estrategias de control:
- ALGORITMO.-Disponemos de información segura sobre qué operación aplicar
- BUSQUEDA EXHAUSTIVA (A CIEGAS).- Exploración del árbol de búsqueda sistemáticamente pero sin información
- BUSQUEDA HEURÍSTICA (INFORMADA).- información sobre el problema (información del dominio) que permite reducir la búsqueda.
Estrategias de búsqueda a ciegas
- Generar y Probar
- Búsqueda primero a lo ancho
- Búsqueda primero a lo profundo
- Búsqueda de costo uniforme
- Búsqueda en profundidad limitada
- Búsqueda en profundidad iterativa
- Búsqueda bidireccional
Comenzemos con el primer tipo de búsqueda:
GENERATE-AND-TEST
- Generar una posible solución. (estado o camino)
- Comprobar para ver si es una solución, mediante comparación con los elementos del conjunto de objetivos aceptables.
- Si la solución ha sido encontrada salir, de otra manera, retornar al paso 1
Para muestra esta imagen
Estrategias y Algoritmos de Busqueda de Informacion
Existen diferencia de estrategias de búsqueda de información:
- Algoritmo Primero a lo Ancho (BREATH-FIRST)
- Algoritmo Primero en Profundidad (DEPTH-FIRST)
- Búsqueda Heurística:
- Ascenso a Colina
- Recocido Simulado
- Búsqueda Primero el Mejor (BEST-FIRST)
- Teorema de Admisibilidad
- Algoritmo Guiado por Agenda
Las técnicas de solución de problemas en IA, en general, incorporan un proceso de búsqueda.
Todo proceso de búsqueda puede ser visualizado como el recorrido por un árbol en el que cada nodo representa un estado y cada rama representa las relaciones entre los estados cuyos nodos conecta.
En general, las reglas contienen en forma implícita el árbol, y se genera en forma explícita sólo aquellas partes que se decide explorar.
La dirección en la cual se conduce la búsqueda (hacia adelante o hacia atrás).
La estrategia de control, o forma de seleccionar las reglas que pueden ser aplicables. Los principales requerimientos de una buena estrategia de control son: que cause desplazamiento en el espacio de estado; y, que sea sistemático.
La forma de representar cada nodo del proceso de búsqueda (representación del conocimiento).
Muchas veces, tratar el proceso como búsqueda en un grafo en lugar de una búsqueda en un árbol, puede reducir el esfuerzo que se gasta en explorar senderos, esencialmente iguales, varias veces. Sin embargo, los requisitos asociados, son:
Cada vez que se genere un nodo se debe chequear para ver si ha sido generado antes.
Se deben introducir procedimientos especiales para que la búsqueda no quede atrapada en algún lazo.
Existen dos formas de conducer las busquedas:
Conducida por el objetivo (goal driven – backward chaining)
Tomar el objetivo que queremos resolver, establecer que reglas o movimientos legales podrían usarse para generar este objetivo y determinar que condiciones deben ser verdaderas para ser usadas.Estas condiciones constituyen los nuevos objetivos de la búsqueda y la búsqueda continua hacia atrás hasta encontrar los hechos del problema.
Conducida por los datos (data driven – forward chaining)
Búsqueda empieza con los hechos o datos conocidos y un conjunto de movimientos legales o reglas para cambiar de estado.La búsqueda se realiza aplicando las reglas a los datos o hechos, produciendo nuevos datos o hechos. Este proceso continua hasta generar una ruta que satisfaga la condición del objetivo.
Introduccion a técnicas de de resolucion de problemas usando IA
Uno de los resultados que surgieron de las primeras investigaciones en IA fue que la inteligencia necesita conocimiento. El conocimiento posee algunas propiedades poco deseables como:
- Es voluminoso
- Es difícil caracterizarlo
- Cambia
- Se organiza de manera que tiene correspondencia con la forma en que va a ser usado
Una técnica de IA es un método que explota el conocimiento representado de manera que:
- Representa generalizaciones, es decir, no es necesario representar cada situación individual, sino que las situaciones que comparten propiedades importantes se agrupan.
- Debe ser entendido por las personas que lo provean.
- Puede ser modificado para corregir errores y reflejar cambios en el mundo
- Puede usarse en muchas situaciones aun sin ser totalmente exacto o completo
- Puede usarse para superar su propio volumen, y disminuir el rango de posibilidades que normalmente deben considerarse
Se pueden caracterizar las técnicas de IA con independencia del problema a tratar.
Para solucionar problemas complicados, los programas que utilizan las técnicas de IA presentan numerosas ventajas con respecto a los que no lo hacen:
- Son menos frágiles, es decir, que no se “caen” frente a una perturbación en la entrada
- El conocimiento del programa es comprendido fácilmente por la gente
- Usa generalizaciones
- Tiene facilidad de extensión
Las técnicas de solución de problemas en IA, en general, incorporan un proceso de búsqueda.
Todo proceso de búsqueda puede ser visualizado como el recorrido por un árbol en el que cada nodo representa un estado y cada rama representa las relaciones entre los estados cuyos nodos conecta.
En general, las reglas contienen en forma implícita el árbol, y se genera en forma explícita sólo aquellas partes que se decide explorar.
La dirección en la cual se conduce la búsqueda (hacia adelante o hacia atrás).
La estrategia de control, o forma de seleccionar las reglas que pueden ser aplicables. Los principales requerimientos de una buena estrategia de control son: que cause desplazamiento en el espacio de estado; y, que sea sistemático.
La forma de representar cada nodo del proceso de búsqueda (representación del conocimiento).
Muchas veces, tratar el proceso como búsqueda en un grafo en lugar de una búsqueda en un árbol, puede reducir el esfuerzo que se gasta en explorar senderos, esencialmente iguales, varias veces. Sin embargo, los requisitos asociados, son:
- Cada vez que se genere un nodo se debe chequear para ver si ha sido generado antes.
Breve reseña historica de la IA
El desarrollo de la IA ha sido bien documentada a travez del tiempo. Con una excelente herramienta como es el Internet, resulta muy sencillo entender el desarrollo de la misma, gracias personajes muy como Turing.
Empero existen otros personajes importantes en el desarrollo de esta rama de la ciencia de la computación, que no son muy conocidos, más no por ello menos importantes de resaltar. Hea qui en breve resumen por períodos del desarrollo de la IA:
- 1950-1965. Periodo “clásico…”
Resolvedor general de problemas (GPS) [Newell, Simon]. Resolución de problemas de sentido común, los cuales incluyen razonamiento de objetos físicos y sus relaciones, como también razonamiento de acciones y sus consecuencias. Solo se resolvieron tareas simples, pues no se pudo crear un programa con la cantidad suficiente de conocimiento de un dominio específico.
Principal énfasis en la implementación de juegos (ajedrez, damas, etc.) así como en la demostración de teoremas matemáticos.
- 1965-1975. Periodo “romántico”
Representación “general” del conocimiento.
Redes semánticas [Quillian]
Prototipos (frames) [Minsky]
Perceptrón [Minsky y Papert]
Lógica [Kowalski]
Mundo de bloques [Winograd]
Percepción (visión y habla), compresión de lenguaje natural, robótica.
Dificultades de representación “general”, problemas de “juguete”.
- 1975-actualidad. Periodo “moderno”, inteligencia “especifica” vs. “general”.
Se identifica la necesidad de trabajar en sociedad con profesionales de otras áreas de conocimiento
Representación explícita del conocimiento específico del dominio.
Sistema experto médico MYCIN (experto en enfermedades infecciosas de la sangre) iniciado en la Universidad de Stanford
Sistemas expertos o basados en conocimiento.
Regreso de redes neuronales [Hopfield, Rumelhart, Hinton], algoritmos genéticos [Holland, Goldberg]
Reconocimiento de voz , incertidumbre (Lógica difusa), planeación, aprendizaje
Aplicaciones “reales” (medicina, finanzas, ingeniería, exploración, etc.).
Comercialización de la IA, etapa de conocimiento general de la misma
Estos son breves rasgos de la historia actual de la IA. Para mayor informacion , aqui.
Aplicaciones y Fundamentos de la IA
El trailer IRobot, lo publico porque esta película da una buena aproximacion, bastante realista, de los alcances la IA tendra en el futuro. Les recomiendo ver esta pelicula. Si pudiera la subiria completa, de todas maneras les dejo un link para el correspondiente torrent.
Primeramente, veamos algunos fundamentos teóricos sobre los cuales se apoya actualmente este medio de represetnacion del la inteligencia humana.
Durante más de 2000 años de tradición en filosofía han surgido diversas teorías del razonamiento y del aprendizaje, simultáneamente con el punto de vista de que la mente se reduce al funcionamiento de un sistema físico
Esto , aunado con un estudio matemático, han permitido el surgmiento de teorías formales relacionadas con la lógica, probabilidad, teoría de decisiones y la computación. Las matemáticas nos han provisto de las herramientas para manipular las aseveraciones de certeza lógica, así como las inciertas de tipo probabilista. Así mismo prepararon el terreno para el manejo del razonamiento con algoritmos
La Psicología ofrece herramientas que permiten la investigación de la mente humana, así como un lenguaje científico para expresar las teorías que se van creando. Los psicólogos reforzaron la idea de que los humanos y otros animales podían ser considerados como máquinas para el procesamiento de información.
La Lingüística ofrece teorías sobre la estructura y significado del lenguaje. Los lingüistas demostraron que el uso de un lenguaje se ajusta dentro de estas estructuras.
Las Ciencias de la Computación, proveen herramientas que permiten que la inteligencia artificial sea una realidad. Dentro de esta rama,la ingeniería en computación ofreció el dispositivo que permite hacer realidad las aplicaciones de la inteligencia artificial. Los programas de inteligencia artificial por lo general son extensos y no funcionarían sin los grandes avances de velocidad y memoria aportadas por la industria de cómputo.
En conclusión, las ciencias que aportan a la Inteligencia Artificial son:
- Filosofía
- Medicina
- Matemáticas
- Psicología
- Lingüística
- Ciencias de la Computaciòn
Aplicaciones de la IA
Hoy en dia, muchos instrumentos y dispositivos que rodean nuestra vida, y que realmente forman parte importante de la misma, tiene a mayor o menor grado, una inteligencia inplícita. Es por ello que para clasificar las aplicaciones, podemos hacerlo por medio de tareas:
Tareas de la vida diaria
- Percepción (visión y habla)
- Lenguaje natural (comprensión, generación, traducción)
- Control de un robot
Tareas formales
- Juegos (ajedrez, damas)
- Matemáticas (geometría, lógica, cálculo, demostración de propiedades)
Tareas de los expertos
- Ingeniería (diseño, detección de fallas, planificación de manufactura)
- Análisis científico
- Diagnóstico médico
- Análisis financiero …
Podemos tambien clasificarlas segun el proposito para el cual va a ser utilizada:
Aprendizaje:
- Captación automática de conocimiento.
Razonamiento:
- Sistemas basados en conocimiento.
- Bases de datos inteligentes.
- Prueba de teoremas y juegos.
Percepción:
- Comprensión de lenguaje natural.
- Interpretación de escenas visuales (Visión por computadora).
Locomoción y Manipulación:
- Realizar procesos mecánicos y tareas manuales (Robótica).
Creación:
- Generación, verificación, depuración y optimización automática de programas.
Estas son clasficaciones muy generales. Mas adelante, con mayor informacion daremos ejemplos específicos de su correcta aplicacion.
Próximamente:
Un resumen historico de los avances de la IA
Complejidad, automatas y Computabilidad
El campo de la Teoría de la computación en Ciencias de la computacion involucra las subareas de
- Teoría de la computación
- Teoría de autómatas: estudia matemáticamente máquinas abstractas y problemas que éstas son capaces de resolver
- Teoria de la computabilidad: estudia los problemas de decisión que pueden ser resueltos con un algoritmo o equivalentemente con una máquina de Turing.
- Teoría de la complejidad computacional: Estudia teoricamente los recursos requeridos durante el cálculo para resolver un problema (tiempo y espacio)
Ciencias de la COmputacion: Historia
La historia es anterio a que se inventara la computadora
Antes de 1920 , el término computador habalaba de un ser humano que realizaba cálculos
Los primeros investigadores en la cuestión de la computabilidad querian saber
- Qué cosas pueden ser computadas por un ser humano (siguiendo una lista de instrucciones por escrito)l, sin conocer el problema con anterioridad durante el tiempo que fuesea necesario
La motivación para este trabajo era realiza máquinas que computaran, y que pudieran automatizar labores y tareas largas y tediosas para una persona (que ademas podias tener errores)
En década de 1940 mientras se realizaban computadoras, el término computador se comenzó a utilizar para las máquinas en lugar de las personas.
El campo de las ciencias de la computación se fue ampliando mientras se veia que se podan realizar mas cosas que calculos matematicos para estudiar a la informática) en general.
La ciencia de la computación se establecio como una disciplina académica en la década del 60, con los primeros departamentos de ciencias de la computación en las universidad y las licenciaturas respectivas. (Fuente Wikipedia)
Tags: Computador