2o parcial - 2a parte (2017)

Resumen Catalán
Universidad Universidad Autónoma de Barcelona (UAB)
Grado Gestión Aeronáutica - 2º curso
Asignatura IA - Inteligencia Artificial
Año del apunte 2017
Páginas 15
Fecha de subida 10/06/2017
Descargas 0
Subido por

Vista previa del texto

TEMA 4: RECONEIXEMENT DE PATRONS 1. Espai de característiques Espai de característiques à Sistema de coordenades on tenim un determinat nº d’eixos i cada eix representarà les característiques del problema. A través de la funció de decisió es decideix si és, per exemple, de classe 1 o de classe 2. En resum, és una representació de coneixement que definim com: • Lèxic: Característiques, eixos, punts, sistemes de coordenades, classes, partició de l’espai, funció de decisió. • Estructural: o Els punts són vectors de tantes dimensions com l’espai. o Les característiques van associades a cadascun dels eixos de l’espai. o Una classe vindrà donada per una part de la partició de l’espai. • Semàntic: o Els punts representen objectes. o Les coordenades dels punts representen la descripció dels objectes en base a les seves característiques. o Una part de l’espai representarà tots els objectes semblants o una classe. • Procedimental: o Procediment que extreuen les característiques que descriuen un objecte o Procediment que permeten dividir l’espai en una partició. o Procediment que decideixen a quina classe pertany un punt. 2. Metodologia de solució de problemes Passos a seguir en un problema: 2.1 Definició de l’espai de característiques 1. Selecció de característiques interessants (depèn del problema) En l’espai de característiques cada eix representa una característica dels objectes del problema. Volem tenir unes classes (tipus d’objectes, dades, etc.) definides segons algun criteri. Davant una mostra nova (objecte, dada, etc.) de la qual no sabem a quina classe pertany, volem classificar-la en una de les classes definides. Per definir un bon espai de característiques que permeti una bona representació de les classes i les mostres a classificar hem de tenir en compte que: • Cal triar aquelles característiques dels objectes que millor representen les diferències entre les classes • Les característiques a triar depenen del problema Exemple: Construcció d’un OCR (Optical Character Recognigtion) à Serveix per reconèixer de forma automàtica el text d’un document escanejat. A partir d’una imatge escanejada d’un document, ‘objectiu és identificar cada caràcter del document per a poder obtenir el text que hi ha al document. 2.Exploració de l’espai de característiques Treballar amb moltes característiques vol dir que representem el problema en un espai de dimensió alta (una dimensió per cada característica). A vegades, hi ha característiques de l’espai (dimensions de l’espai) que no aporten molta informació. Objectiu à Reduir la dimensió de l’espai a una dimensió menor minimitzant la pèrdua d’informació. Eina: Transformada de Karhunen-Loeve (Anàlisi de components principals) Per a n punts, en un espai de dimensió d, representats a la matriu: Busquem una transformació de l’espai (canvi de base) que permeti acumular la màxima informació en un nombre menor de dimensions: essencialment 1, 2 o 3 per a que pugui ser més observable, i ens informi sobre l’eficàcia de cada característica. Algorisme: • Construir, R, la matriu de covariància de X: • Calculem els valors propis de R: i els vectors propis de R es poden calcular trobant la solució de l’equació: • Apliquem el canvi de base sobre la mostra, de manera que ara les primeres dimensions poden concentrar la major part de la informació, i permeten construir representacions més observables: Exemples: La característica x2 no aporta informació: la major part de la informació està representada en l’eix x1 La informació es reparteix entre les dues característiques per igual (mirar exemple real diapositiva 8) Les mostres es poden representar en un pla (dimensió 2) en lloc de en un espai de 3 dimensions 2.2 Partició de l’espai de característiques 1. Definició de la funció de decisió Funció de decisió à Ens defineix una partició de l’espai de característiques, on cadascuna de les parts definides correspon a una de les classes del problema. • Lineal: Adequades quan les classes es poden separar amb un hiperplà (recta, pla, ...). • No lineal: Adequades quan les classes no es poden separar amb una funció lineal i es pot definir una funció no lineal que les separi. • Probabilística: Adequades quan les dades presenten una estructura probabilística amb un funció de densitat coneguda. • Veí més proper: Es basen en assignar la mostra a la classe de la mostra o del representant més proper a la mostra a classificar. 2. Aprenentatge Podem fer l’aprenentatge de dues formes: • Supervisat: Existeix un conjunt de mostres d’aprenentatge de les que es coneix a quina classe pertany cada una. Problema: Definir funcions de decisió adequades. Objectiu: Estimar els paràmetres de la funció de decisió triada, a partir de les mostres d’aprenentatge proporcionades. Funció de decisió lineal: Trobar els paràmetres wi de l’equació: Funció de decisió no lineal: Trobar els paràmetres de la funció no lineal definida. Paràmetre = Radi de l’equació • Estimació de la densitat de probabilitat: Si al densitat és assumida normal, aleshores s’han d’estimar dos paràmetres: No supervisat: No existeix un conjunt de mostres d’aprenentatge de les que es coneix a quina classe pertany cada una. Problema: Buscar automàticament l’estructura de les dades per agrupaments (algorismes Clustering à K-means). Passos Algorisme K-means: Exemple: Volem classificar les següents mostres en 5 classes amb l’algorisme K-means (classificació no supervisada) 2.3 Presa de decisions o Classificació Presa de decisió (Classificació) à Una vegada tenim les funcions de decisió que defineixen una partició de l’espai de característiques en dues o més classes, podem classificar qualsevol nova mostra representada en l’espai de característiques. Passos: 1. Representació de la mostra 2. Aplicació de les funcions de decisió a classificar en l’espai de característiques TEMA 5: SISTEMES MULTI-AGENT I INTEL·LIGÈNCIA ARTIFICIAL DISTRIBUÏDA 1. Introducció Intel·ligència artificial distribuïda (històricament) à Creació de sistemes formats per múltiples agents. Àrea dividida en dos camps: • Solució de problemes distribuïts: Centrat en com es poden solucionar problemes concrets a partir d’un conjunt de mòduls (divisió del problema, assignació de tasques, etc.). • Sistemes multi-agent: Centrat en l’estudi del comportament d’un conjunt d’agents autònoms que intenten resoldre un problema conjuntament. Sistemes multi-agent à Sistemes formats per múltiples agents intel·ligents que interactuen entre ells en un mateix entorn. S’estudia com es relacionen entre ells per resoldre problemes treballant de forma conjunta. Motivació à Tot i l’avenç de la tecnologia, hi ha tasques complexes que un agent individual no pot resoldre de forma eficient, per exemple, el control del tràfic aeri. Idea à Realitzar una tasca a partir de la interacció entre agents autònoms i relativament independents que operen en un mateix entorn i que estableixen relacions entre ells per tal de complir els seus objectius. Objectiu à Construir sistemes complexos formats per agents autònoms que: • Tenen capacitats limitades i operen amb un coneixement local • Són capaços d’aconseguir el comportament global desitjat Elements d’un sistema multi-agent • • • • • • • Coneixements a priori sobre l’entorn i sobre els altres agents Percepcions sobre l’entorn que reben els agent Accions que poden dur a terme els agents Entorn compartit per tots els agents del sistema Criteri d’èxit que avalua el rendiment global del sistema Recursos que els agents han de compartir Comunicació entre els agents que els permet establir relacions entre ells Exemple: Robots jugadors de futbol. Elements que formen aquest sistema multi-agent? • Agents: Cada “jugador” (robot) • Coneixement a priori: Forma del camp de joc, estratègies, jugades, etc. • Accions: passar, xutar, frenar, canviar direcció, etc. • Entorn compartir: camp de joc • Criteri d’èxit: resultat del partit • Recursos compartits: pilota, espai • Comunicació: missatges marcant una jugada, avís de passada, etc. 2. Característiques dels sistemes multi-agent Característiques bàsiques dels agents (a nivell individual en un sistema multi-agent) • • • Autonomia: els agents són autònoms, és a dir, no són dirigits per l’usuari o per altres agents. Visió local: els agents no tenen una visió global del sistema, sinó que només tenen accés a la informació d’una part de l’entorn. Descentralització: no hi ha un agent que controli el sistema. Característiques bàsiques dels agents (a nivell global) • Capacitat de comunicació: Els agents han de disposar d’un mecanisme comú per compartir informació (coneixement) entre ells. • Flexibilitat: Són molt flexibles donat que es poden modificar, afegir i reconstruir sense la necessitat de redefinir tots els seus components. • Auto-organització: poden manifestar capacitat d’auto-organització que emergeix a partir del funcionament individual dels agents, i tendeixen a trobar la millor solució del problema amb poca o cap intervenció de l’usuari. • Comportaments complexos: poden tenir comportaments complexos globals, encara que les estratègies individuals de tots els agents siguin simples. Consideracions a fer en el disseny de sistemes multi-agent El disseny de sistemes multi-agent comporta uns problemes que no es donen en els sistemes monoagent i que cal tenir en compte. • Representació del coneixement: o Com fer que els agents tinguin una representació del coneixement dels altres agents? o Com fer que raonin sobre les accions dels altres agents? • • • • Definició del sistema multi-agent: o Com dividir els problemes entre els agents? o Com fusionar els resultats individuals d’un grup d’agents? Comunicació i interacció: o Com es comuniquen els agents? o Què i quan es comuniquen? Interacció i conflictes: o Quin tipus d’interacció s’estableix entre els agents? o Com detectar accions contraposades entre els agents que estan intentant col·laborar o Com tractar els conflictes quan apareixen? Efectes no desitjats: o Com evitar o mitigar efectes globals no desitjats (ex.- comportaments caòtics o oscil·lants) derivats de les accions individuals dels agents? o Com tractar els events imprevistos? Exemple: Sistema de pintat de camions (The Flavors Paint Shop) 3. Comunicació entre agents • Permet que els agents cooperin, coordinin les seves accions i portin a terme tasques conjuntament à Sense comunicació els agents són elements aïllats Normalment basada en l’esquema clàssic de la comunicació: • Comunicació = intercanvi de missatges que, un cop interpretats pels agents, afecten el seu comportament Punts importants en la definició de la comunicació entre agents: • Canal de comunicació: xarxa (ex. Internet), sistemes propis, etc. • Llenguatge de comunicació: existeixen estàndards de comunicació entre agents Tipus de comunicació entre els agents: 1. En funció de la relació emissor – receptor: • Comunicació punt-a-punt à El missatge té un destinatari concret. • Comunicació en difusió (broadcasting) à L’emissor no coneix el receptor. El missatge s’adreça a múltiples destinataris (tots els que estan a menys d’una certa distància). 2. En funció de la naturalesa del canal de comunicació: • • Enviament directe à El missatge s’adreça directament al/s destinatari/s i la resta d’agents no poden accedir al missatge. Enviament per propagació à El missatge es llença al canal amb una “intensitat” associada que decreix amb la distància a l’emissor. • Enviament per nota pública à El missatge s’envia a un espai comú (“tauler d’anuncis”) que és accessible per tots els agents. 3. En funció de la intenció de la comunicació: • • Comunicació intencional à L’emissor envia el missatge perquè vol que el receptor realitzi alguna acció o que el receptor incorpori alguna informació al seu coneixement. Requereix que emissor i receptor comparteixin el significat del missatge. Exemple: Un agent envia un missatge a un altre agent demanant que faci un moviment Comunicació incidental à L’emissor envia el missatge però no espera que el receptor realitzi cap acció. El significat del missatge només depèn de l’emissor. Molts cops el receptor ha d’interpretar el missatge si en vol extreure informació. Exemple: Un agent envia la seva posició en l’entorn a la resta d’agents però sense demanar que facin res amb aquesta informació En general, els sistemes multi-agent NO implementen tots els possibles sistemes de comunicació que es deriven de la classificació anterior. Les formes més habituals d’implementar les comunicacions són: 4. Interacció entre agents Els agents d'un sistema multi-agent es relacionen amb l'entorn i també amb els altres agents. La interacció entre agents es dóna quan dos o més agents es relacionen a través d'un conjunt d’accions recíproques. Les conseqüències de les accions tenen una influència en el comportament futur dels agents. Exemples d'interacció entre agents: • Un robot que ajuda a un altre a fer una tasca. • Un intercanvi de dades entre servidors. • Agents especialistes compartint el seu coneixement per detectar errors en un sistema. • Dos vehicles autònoms que xoquen. La interacció entre agents pot ser de diferents tipus depenent de tres factors bàsics: En funció dels 3 factors bàsics es poden donar diferents situacions: Hi ha 3 tipus d’interacció: 1. Indiferència 2. Competició 3. Cooperació à El més interessant pels sistemes multi-agent. Cooperació La cooperació és necessària quan es tenen objectius compatibles i els recursos o les capacitats dels agents són insuficients.. En general, existeix un objectiu global que es vol aconseguir, però els agents del sistema tenen objectius individuals. El resultat de la cooperació sorgeix com a resultat de les accions dels agents, no com a resultat de les seves intencions. El problema de la cooperació d’agents es resumeix en determinar: • quin agent fa cada acció • quan es fa cada acció • com es fa cada acció • amb qui es fa cada acció Exemple: Sistema per evitar col·lisions entre avions ...