Aplicaciones con técnicas de IA. - rvazquez.orgrvazquez.org/Misitio/ia2010_files/9aplicaciones.pdf · implementar el cerebro de un robot viernes 22 de mayo de 15. Problemas de la

Aplicaciones con técnicas de IA.

viernes 22 de mayo de 15

Temas

• Robótica.

• Redes Neuronales (RN).

• Visión artificial.

• Lógica difusa (Fuzzy Logic).

• Procesamiento de Lenguaje Natural (PLN).

• Algoritmos Genéticos.


Robótica

• Es la IA parte de la robótica o la robótica parte de la IA.

• La IA nos ofrece la posibilidad del implementar el cerebro de un robot


Problemas de la Robótica móvil

• De los manipuladores a los robots moviles


Esquema de Control General para un robot móvil.

Sensado

Extracción de

Información

Construcción del

Mapa de

Localización

Conocimiento para

la planeación de la

trayectoria

Actuador

Ejecución de la

Trayectoria

Medio

Ambiente, en

el mundo real

Datos Crudos

Mapa Local del modelo

del medio ambiente

Percepción

Conocimiento,

Base de datos

“Posición”

Mapa Global

Comandos

de misión

Trayectoria

Comandos del actuador

Control de

Movimiento


Visión artificial



• Lógica Difusa


• Entre los diversos cambios paradigmáticos en las ciencias y las matemáticas en este siglo, uno de estos se refiere al concepto de incertidumbre.

• En la ciencia, este cambio se ha manifestado por una transición gradual de la visión tradicional, que insiste en que la incertidumbre no es deseable y debe evitarse por todos los medios posibles, para una visión alternativa, dice que la incertidumbre es tolerable y que la ciencia no la puede evitar.

De los Conjuntos Ordinarios (Crisp)[Nitidos] a los Conjuntos Difusos (Fuzzy)


• Según el punto de vista tradicional, la ciencia debe luchar por la seguridad en todas sus manifestaciones (precisión, especificidad, la nitidez, la coherencia, etc), por lo que la incertidumbre (imprecisión, falta de especificidad, la vaguedad, la incoherencia, etc) es considerada como no científica.

• Según el punto de vista alternativo (o modernas), la incertidumbre se considera esencial para la ciencia, no sólo es una plaga inevitable, pero tiene, de hecho, una gran utilidad

De los Conjuntos Ordinarios (Crisp)[Nitidos] a los Conjuntos Difusos (Fuzzy)


Simbología general

Un repaso de Conjuntos Nítidos (Teoría de Conjuntos Clásica)

Z={...-2,-1,0,1,2,.....} Conjunto de enterosN={1,2,3,... } Conjunto números naturalesN0={0,1,2,3,... } Conjunto de enteros no negativosNn= {1,2,3,... ,n}N0,n= {0,1,2,3,... ,n}R: Conjunto de los números realesR+: Conjunto de los números reales no negativos[a,b] intervalo cerrado(a,b] intervalo abierto a la izquierda[a,b) intervalo abierto a la derecha(a,b) intervalo abierto de números reales abierto entre a y b⟨x1,x2,....,xn⟩ n-tupla ordenada de elementos x1,x2,....,xn



• iff es la expresión corta de si y solo si

• Los conjuntos los denotaremos con una letra mayúscula y con una minúscula cada uno de sus elementos.

• La letra X denota el universo en cuestión, o conjunto universal.

• Este conjunto contiene todos los posibles elementos que conciernen en cada contexto en particular o aplicación de los cuales se puede formar un conjunto.



• El conjunto que no contiene elementos se llama conjunto vacío y se denota por el símbolo ∅

• Para indicar que un objeto individual x es miembro o elemento de un conjunto A, escribimos:

x ∈ A

• Y si x no es miembro de A

x ∉ A



• Existen 3 métodos básicos por los cuales podemos definir un conjunto, dentro de un conjunto universal X

1. Un conjunto se define, mencionando a todos sus elementos (El método de la lista). Este método puede ser usado solamente por conjuntos finitos. El conjunto A cuyos miembros son a1,a2,....,an es usualmente escrito como:

A={a1,a2,....,an}



2. Un conjunto se define por una propiedad que satisface a sus miembros (El método de la regla). Donde una expresión común de un conjunto sería:

A={x| P(x)}

• Donde el símbolo | denota “tal que”, y P(x) una proposición de la forma “ x tiene la propiedad P”

• Se lee, el conjunto A esta formado de todos los elementos de X, tales que la proposición P es verdadera



3. Un conjunto esta definido por una función, usualmente llamada función característica.

• La cual declara cuales elementos de X son miembros del conjunto y cuales no.

• El conjunto A esta definido por la función característica, XA como sigue:

XA(x)=⎨

1 para x ∈ A

0 para x ∉ A



• Esto es la función característica mapea los elementos del conjunto X a los elementos del conjunto {0,1}

XA: X → {0,1}

• Para cada x ∈ X, cuando XA(x)=1, x es declarado miembro del conjunto A



• A ⊆ B A es subconjunto de B

• A = B A es igual a B

• B - A Complemento relativo del conjunto A con respecto al B

• B-A= { x|x ∈ B y x ∉ A }

• Si el conjunto B es el conjunto universal entonces el resultado de la operación se llama complemento A



• A ⋃ B= {x|x ∈ A o x ∈ B } union

• A ⋂ B= {x|x ∈ A y x ∈ B } intersección

• A × B= {〈a,b〉| a∈ A ,b ∈ B } producto

cartesiano

• Si A={a,b} y B={1,2}

• A × B= {(a,1),(a,2),(b,1),(b,2)}


Un repaso de Conjuntos Nítidos (Teoría de Conjuntos Clásica)• Si A={a,b,c,d}

• |A|= 4 Cardinalidad de A

• Una relación R de A a B es un subconjunto de A × B

• R ⊆ A × B

• Si A={1,2} y B={3,2}

• R= {(1,2),(2,3)} es una relación de A a B

• R= {(1,3)} es también una relación de A a B


Un repaso de Conjuntos Nítidos ( Un ejemplo)Sea el conjunto universal X formado por los dígitos.

Definiremos el conjunto A

A={ x| P(x)=”sea un numero par” }

A={ 0,2,4,6,8 }

Definiremos el conjunto B

B={ x| P(x)=”sea múltiplo de 3” }

B={ 3,6,9 }


Un repaso de Conjuntos Nítidos ( Un ejemplo)

XA(0)= 1

XA(1)= 0

XA(2)= 1

XA(3)= 0

XA(4)= 1

XA(5)= 0

XA(6)= 1

XA(7)= 0

XA(8)= 1

XA(9)= 0

• Tomando en cuenta que el conjunto universal esX={0,1,2,3,4,5,6,7,8,9,0} y A={ 0,2,4,6,8 }entonces



• A ⋃ B= {x|x ∈ A o x ∈ B }

• A={ 0,2,4,6,8 } B={ 3,6,9 }• A ⋃ B ={0,2,3,4,6,8,9}

X

2

4

8

0

6

6

9

3

A B



• A ∩ B= {x|x ∈ A y x ∈ B }

• A={ 0,2,4,6,8 } B={ 3,6,9 }• A ∩ B ={6}

X

2

4

8

06

9

3

A B


Fuzzy Sets: Tipos Básicos

• La función característica de un conjunto nítido asigna un valor de 1 o 0 a cada individuo del conjunto universo.

• Discriminando así entre los miembros y no-miembros del conjunto nítido en consideración

• Esta función puede ser generalizada de tal manera que los valores asignados a los elementos del conjunto universal dentro de un rango especificado, indiquen el grado de pertenencia de estos elementos en el conjunto en cuestión



• Grandes valores denotan grandes grados de membresia al conjunto.

• Tal función es llamada función de membresía

• Y el conjunto definido por esa función se llama Fuzzy Set. (Conjunto Difuso)

• El rango de valores mas comúnmente usados, de funciones de membresía estan dentro del intervalo unitario [0,1]



• Existen 2 tipos de notaciones, que son mas comúnmente usadas para expresar funciones de membresía.

• Forma 1µA: X →[0,1] o

mA: X →[0,1]

• Forma 2A: X →[0,1]



• Los conjuntos difusos nos permiten representar conceptos vagos en lenguaje natural.

• La representación depende no solamente del concepto sino también del contexto en el cual será usado.

• Ejemplo: Sea el concepto “Temperatura Alta” en el contexto del clima y en el contexto de un reactor nuclear.

• Para trabajar esos conjuntos difusos habría que representarlos muy diferentes.


Un primer ejemplo de Fuzzy Set

• Supongamos que vamos a crear 3 conjuntos difusos, dentro de un conjunto universal que consiste en los niveles de educación mostrados a continuación:

0.- Sin educación

1.- Nivel Básico

2.- Nivel Medio Superior

3.- Técnico Superior Universitario

4.- Nivel Superior

5.- Nivel Maestría

6.- Nivel Doctorado



• Los conjuntos difusos que queremos crear son:

• Poca educación

• Altamente educado

• Muy altamente educado

• Para lo cual definiremos las funciones de membresía de los 3 conjuntos.

• Para lo cual utilizaremos la siguiente gráfica, donde



0

0.1

0.2

0.3

0.4

0.6

0.7

0.8

0.9

1.0

0 1 2 3 4 5 6

Mem

bres

ia

Nivel de educación

“Poco educado”



0

0.1

0.2

0.3

0.4

0.6

0.7

0.8

0.9

1.0

0 1 2 3 4 5 6

Mem

bres

ia

Nivel de educación

“Poco educado”,”Altamente educado”



0

0.1

0.2

0.3

0.4

0.6

0.7

0.8

0.9

1.0

0 1 2 3 4 5 6

Mem

bres

ia

Nivel de educación

“Poco educado”,”Altamente educado”,”Muy Altamente Educado”



• Luego entonces, una persona con una carrera a nivel profesional (nivel superior) pero sin una maestría o doctorado de acuerdo a estas definiciones cuenta con los siguiente grados de membresia a los conjuntos difusos en cuestion:

• Altamente educado = 0.8

• Muy Altamente educado = 0.5

• Poco educado = ¿ ?


Ejemplos

• Algunos conjuntos difusos representan conceptos como bajo, medio, alto que frecuentemente se usan para definir estados de una variable

• Tales variables se les llama Variables difusas.

• Por ejemplo una temperatura en el rango [T1,T2] se caracteriza como una variable difusa como se muestra en la siguiente figura


Ejemplos

Temperatura, ºCT1 T2

Mem

bresia

bajo medio alto muy altomuy bajo

1


Ejemplo 2• Del siguiente conjunto de datos, considerarlo

como el conjunto universal para construir el conjunto difuso “alto”

Nombre EstaturaEdgar 1.73Tania 1.58

Ruben 1.72Marco 1.81Juan 1.70Jose 1.79

Alejandro 1.78Omar 1.98Rafael 1.80



Ejemplo 2

• Según el articulo en 2008

• estatura mexicano alto 1.87

• estatura mexicana alta 1.71

• Promedio 1.79


Ejemplo 2 - El conjunto difuso “alto”

0

0.1

0.2

0.3

0.4

0.6

0.7

0.8

0.9

1.0

Tania Juan Ruben Edgar Alexandro Jose Rafael Marco Omar

Mem

bres

ia

Estatura


Ejemplo

• Una forma de representar los conjuntos difusos es:

E= 0/tania+0.1/juan+0.2/ruben+0.3/edgar+0.4/alexandro+0.5/jose+0.6/rafael+0.7/marco+1/omar


Conjunto difusos (continuación)

• Otra forma de expresar conjuntos difusos es directamente con las funciones de membresia.

• Pensando en los conceptos joven, adulto, mayor. Para el conjunto difuso “adulto”.

0 si x≤18 o x≥60(x-18)/17 si 18<x<35(60-x)/15 si 45<x<601 si 35≤x≤45

A(x)


Conjunto difusos (continuación)

18 60

A(x)

1

edad x


• Procesamiento de Lenguaje Natural


• Gano Jeopardy el 16 de Febrero de 2011

Ques%on Answering: Watson de IBM

La obra de William Wilkinson “Un relato de los principados de

Valaquia y Moldavia” inspiró a este autor en su novela más

famosa

Bram Stoker


Diseño de Watson


Extracción de Información

Subject: reunion de trabajoDate: Enero 15, 2012

To: Rafael Vazquez

Hola Rafael, hemos calendarizado la reunión de trabajo en el salón B1 mañana de 10:00-11:30

-Ruben

Create new Calendar entry

Event: reunion trabajoDate: Ene-15-2012Start: 10:00amEnd: 11:30am


Extracción de Información y análisis de sentimientos


Traducción de Maquina

Traducción del software Phrasal de la U. de Standford:

Introduzca el texto fuente:

Totalmente automática Traducción auxiliada por humanos


Tecnología del lenguaje


La ambigüedad hace difícil el procesamiento del lenguaje natural

• Lourdes no quiere a su tía por que es muy envidiosa

• El pez esta listo para comer

• El Pachuca le ganó al Leon en su campo

• Tengo una maestra muy buena

• Estuve esperándote en el banco

• Se debe limpiar aquí

• ¿Me diste la mesa?

• Alejandro es noble

• Estaré de vacaciones solo unos días


¿ Porque es tan difícil comprender el lenguaje natural ?


¿ Que progresos hemos hecho en estos problemas ?• La tarea es muy difícil! ¿ Que herramientas necesitamos ?

• Conocimiento sobre el lenguaje

• Conocimiento sobre el mundo

• Una forma de combinar esas fuentes de conocimiento

• Como se hace generalmente esto:

• Modelos probabilisticos que construyan datos del lenguaje

• P(“rouge” → “rojo”) alta

• P(“L’avocat général” → “El general avocado”) baja


NLP• Procesamiento Básico de

Texto

• Distancia de Edición

• Modelado del Lenguaje

• Corrección de Vocabulario

• Clasificación de Texto

• Análisis de Sentimientos

• Clasificadores Discriminativos

• Reconocimiento de Entidades con Nombre y Modelos de Entropía

• Extracción Relacional

• Tagging Posicional

• Introducción al Parsing

• Parsing Probabilistico

• Information Retrieval

• Semántica

• Question-Answering

• Resúmenes Automáticos


• Algoritmos Genéticos


OptimizaciónPrimera aproximación

“Es el proceso de hacer algo mejor”

• La optimización consiste del tratamiento de las variaciones de un concepto inicial y usar la información obtenida para mejorar la idea.


Optimización

• Vamos a hacer un programa para un dispositivo móvil

------------------

.

.---------

programa

Parámetros Iniciales delprograma-Tamaño (T) - Memoria requerida (M)- Tiempo de Ejecución (TX)

Resultado:Ejecución muy lenta


Optimización

• Analizamos y reducimos tamaño, eliminamos variables, etc (T,M,TX)

------------------

.

.---------

programanuevo

Parámetros nuevos delprograma-Tamaño (T)- Memoria requerida (M)- Tiempo de Ejecución (TX)

Resultado:Ejecución

Ok


Optimización

• El termino “mejor” solución implica que hay mas de una solución y que cada solución no tiene valores iguales.

• La definición de “mejor” es relativa al problema que se esta manejando, su método de solución y las tolerancias permitidas.

• Luego entonces la solución optima depende de la formulación personal del problema


Optimización• Existen innumerables oportunidades de problemas de

optimización con diferentes grados de complejidad.

• ¿ Por cual ruta debo irme para llegar al tecnológico ?

• ¿ Que arreglo hago de los muebles de la sala para que me quede el mayor espacio posible ?

• ¿ Que rutas debo tomar para no consumir tanta gasolina ?

• ¿ Cuales acciones debo comprar para maximizar mis ganancias ?

• ¿ Cuales son los parámetros óptimos de una turbina de viento para maximizar la potencia de salida ?


Optimización• La optimización es el proceso de ajustar las

entradas a las características de un dispositivo, proceso matemático o experimento para encontrar la salida con un resultado mínimo o máximo.

función oproceso

Entrada

x

Salida

parámetros⟨x1,x2,...xn⟩


Optimización

• La entrada consiste en un conjunto de parámetros. Se le conoce también como vector de entrada.

• Al proceso o función se le conoce como la función costo, función objetivo o función fitness

• La salida es el costo


Optimización

• Otro enfoque

• Se requiere medir la optimización

• Usualmente modelada por una función matemática

• Encontrar la solución que cumpla globalmente el mejor valor de nuestra medida.


Optimización• ¿Y luego ? ¿ Cual es el problema ?• Nike: Just do it• No es tan simple

• Existen problemas que son simples para describirlos formalmente que pueden ser intratables

• Depende del enfoque• La teoría de la complejidad es una herramienta

que usamos para describir y reconocer problemas intratables.


OptimizaciónEl problema general de optimización se puede definir como:

min f0(x)x∈Rn

sujeto a m restriccionesfi(x)≤0

i=1,2,.....,m


Consideraciones Importantes

• Optimización Global vs Local

• Optimización Convexa vs No Convexa

• Sin restricciones o con restricciones o casos especiales

• Clases especiales de funciones (lineales o no lineales)

• Funciones diferenciables vs no diferenciables

• Existen millones de algoritmos diferentes registrados para problemas de optimización


¿ Para que optimizar ?• En la mayoría de los casos, todos los diseños de

ingeniería son optimización; seleccionar los parámetros de diseño para mejorar algún objetivo.

• Mucho del análisis de datos es también optimización; extraer parámetros del modelo de datos, mientras se minimiza el error de medición.

• La mayoría de las decisiones de negocios = optimización; variación de algunos parámetros de la decisión para maximizar ganancias.


Caracterización de problemas de optimización

• No olvidemos los elementos típicos de un problema de optimización

• Entrada.- Formada por un grupo de parámetros o variables. Los cuales se van a extraer del modelo o del problema real.

• Función Fitness.- Es la función con la que podremos evaluar una combinación de parámetros de entrada.

• Salida.- El costo de una solución del problema



• Ejemplo: La empresa que produce la cerveza Vudweiser le solicita a su equipo de diseño de productos, diseñar una lata de cerveza que minimice la perdida de calor después que se saque del refrigerador.

• La perdida de calor es proporcional a la superficie del cilindro (k constante valor de 1)

• Perdida de Calor = k*(Superficie del Cilindro)



Primero, identificaremos la entrada de problema de optimización, es decir identificar los parámetros

Parámetro 1 = radio del cilindro en cms, rParámetro 2 = altura del cilindro en cms, h



• Función Fitnessfitness(r,h){ const pi=3.1416 k=1 /* superficie=superficietapas+superficiecilindro */ supericietapas=2*pi*r*r; superficiecilindro=h*pi*r*2; superficie=superficietapas+superficiecilindro; perdida=k*superficie; return perdida;}



• Salida

• suponiendo una entrada r=2 cm y h=6 cm

• f(2,6)=100.53 (el costo)


Conceptos Básicos de Algoritmos Genéticos

Ejemplo: Sea la función matemática f(x)= -x2sen(x)Calcular el valor mínimo f(x)Restricción0≤x≤π



• Entrada x

• Función Costo = f(x)

• Salida = depende del valor de x



• Los algoritmos genéticos son un subconjunto de los algoritmos evolutivos que modelan procesos biológicos para optimización de funciones costo altamente complejas.

• Un algoritmo genético permite a una población compuesta de muchos individuos, evolucionar a un estado bajo reglas de selección especificas que maximizan la función ”fitness”



• Ventajas de los Algoritmos Genéticos

• Optimizan con parámetros continuos o discretos

• No requieren información de derivadas.

• La búsqueda es simultánea en un amplio muestreo de la superficie del costo.

• Pueden saltar mínimos locales

• Nos ofrecen una lista de parámetros óptimos, no solo una solución.

•



• Algoritmos Genéticos Binarios (su representación es con números binarios)

• Algoritmos Genéticos No Binarios


Paso siguienteviernes 22 de mayo de 15







• El algoritmo genético empieza como cualquier otro algoritmo de optimización, definiendo los parámetros de la optimización, la función costo y estimar el costo.

• El algoritmo genético termina como cualquier otro algoritmo de optimización, con las pruebas de convergencia.



• Caso 1: La empresa productora de la cerveza vudweiser les encarga el diseño de una lata con capacidad de 1 litro, ¿ Cuales deben ser las dimensiones para minimizar la cantidad de metal ?

• A) Definir la entrada

• B) Definir la función costo

• C) Calcular un costo para 10 entradas propuestas



• Caso 2: Hallar las dimensiones que hacen mínimo el costo de un contenedor que tiene forma de paralelepípedo rectangular sabiendo que su volumen ha de ser 9 m3 , su altura 1 m y el costo de su construcción por m2 es de $1000.00 para la base; 1200 para la etapa y 800 para cada pared lateral.






• Caso 3: Una hoja de papel debe tener 18 cm2 de texto impreso, márgenes superior e inferior de 2 cm de altura y márgenes laterales de 1 cm de anchura. Obtener las dimensiones que maximizan la superficie del papel.





Documents

Aplicaciones con técnicas de IA. - rvazquez.orgrvazquez.org/Misitio/ia2010_files/9aplicaciones.pdf · implementar el cerebro de un robot viernes 22 de mayo de 15. Problemas de la