1

Prctica0

Abordandolacreacindeunsistemainteligente(ProfesorJoseJesusGarcaRueda)

1. Objetivos.

Objetivosdidcticos:o Empezar a pensar en trminos de cmo abordar problemas que

involucreninteligenciaartificial.o Provocar lanecesidaddeprofundizarennuevastcnicas,msallde las

conocidas. Objetivosespecficos:

o Analizar mediante tcnicas de caja negra una aplicacin inteligente,tratandodeaveriguarcmofunciona.

o Disear una aplicacin similar, valorando el empleo de distintasestrategias.

Entregables:o Informe(entre2y4pginas)querecoja:

Elanlisisdelaaplicacindepartida. El proceso de diseo y de la nueva aplicacin y solucin

finalmenteadoptada. Lasmejorasfinales.

Estaprcticahabrderealizarseporparejas.

2. AnlisisdeAkinator.

Vamosatratardeaveriguar,osuponer,cmofuncionaAkinator,unodelosadivinosmspopularesdelaRed.Podisencontrarloaqu:

http://es.akinator.com/

Jugadunratoconl,pensadentresocuatropersonajes,ycuandooshayisfamiliarizadocon ladinmicade la aplicacin,proponed vuestraspropias respuestas a las siguientespreguntas:

Porqulasprimeraspreguntasnosonsiemprelasmismas?

2

Apartirdequpreguntaparecequeempiezaadirigirsemsalobjetivo? Son20preguntasmuchasopocasparadistinguiraunpersonaje? Cuandonoloadivina,proponeunpersonajemuydistintoalbuscado? Porquestinteresado,cuandofalla,ensaberqupersonajeera,peronopide

nuevaspreguntasparadistinguirlo?

Recordad que el nico medio del que disponis para responder a estas preguntas esseguir jugandocon laherramienta,perodemaneradirigida:vuestras interaccionesconellanohandeserfortuitassinoorientadasaaveriguarlainformacinquenecesitisparacrearvuestropropioadivino.

3. Abordandoelproblemadediseo.

Enprimerlugar,trataremosdedefinirnuestroproblemadeunaformasimplificada,afindepoderrazonarsobrelconmayorfacilidad:

Supongamosunnmero limitadoyconocido,peromuygrande,depersonajes,definidosporunconjuntotambinlimitado,peromayorde20,decaractersticas(llevagafas?usasombrero?). Nuestro problema consiste en disear una arquitectura lgica capaz delocalizaraunpersonajedenuestra coleccina travsde20preguntasquepuedan serrespondidas como S o NO (adicionalmente, trataremos de contemplar tambin casosdudosos,puedeques/puedequeno,opreguntasquenoapliquen).

Actividad: Plantead el algoritmo bsico de funcionamiento de la aplicacin (desde unpuntodevista funcional,noestructural,estoes, loqueescapazdehacer,nocmoescapazdehacerlo).Estoconsiste,bsicamente,endescribirsistematizadamenteelprocesodeinteraccindelusuarioconlaaplicacin.

Siosfijis,elprocesodediseodeunaherramientaquesecomportedelaformadescritaanteriormenteconsistir,fundamentalmente,enresponderlassiguientespreguntas:

Cmoelijoqupreguntahaceracontinuacin? Cmorelacionoelconjuntodepreguntasconeldepersonajes? Cmo voy limitando el conjunto de personajes posibles, segn avanzan las

preguntas?

4. Primerintento:estrategiasdebsqueda.

Lasprimeras tcnicasque intentaremosaplicarpara resolvernuestroproblema son lasvistasenelprimertemadelaasignatura,porserlasmejorconocidaspornosotroshastalafecha:lastcnicasdebsqueda.

3

Actividad 1: Definicin del problema en trminos de bsqueda de soluciones en unespaciodeestados.Elprimerpasoparaaplicaralgunadeestasestrategias, talycomovimos en teora, es tener descrito el problema en trminos de estados y reglas detransicin.Paraellotratadderesponderalassiguientespreguntas:

Culespodransernuestrosestados? Cmodefiniramoselestadoinicial? Yelestadofinal? Mediantequreglascambiaramosdeestado?

Actividad2:Establecimientodeunaestrategia.Unavezdescritoelproblema,hemosdeseleccionarunaestrategiadebsquedaqueaprioriparezcaadecuada,dadalanaturalezadenuestroproblema,en trminosde completitud,complejidad temporal ,complejidadespacial y calidad (es o no optima?). Podramos quiz considerar nuestro problemacomosisetratasedeunjuego,yemplearMinimax?Sermsconvenientetratarlocomounproblemadesatisfaccinderestricciones?Evaluadydiscutidlasdistintasopciones.

Actividad3:Planteamientodeunalgoritmodebsqueda.Unavezquetengisunprimermodelo de solucin, tratad de detallarlo en un algoritmo de bsqueda concreto, queexploreyrecorraelrboldeestadosdelproblemahastaencontrarunasolucin.

Actividad 4: Anticipacin de problemas. Parece este camino el ptimo de cara amodelarnuestraaplicacin?Qudificultadesconceptualesnossurgen,yquproblemasprcticosnospuedensurgir?Seprevunasolucinrazonableparaellos?

5. Segundointento:rbolesdedecisin.

NOTA: El tema de los rboles de decisin se tratar con detalle ms adelante en laasignatura.Noesobjetivodeestaprcticaprofundizarenellos.

Unrboldedecisin,definidodemaneramuysencillaypor lotanto incompleta,esunaestructuraquepermiteclasificaruneventoinicialatravsdelacomprobacinsecuencialdeuna seriede condiciones sobre l: en cadanododel rbol seplanteauna cuestinsobreeleventodepartida,ydependiendodelarespuestaseevolucionaporunaramauotra del rbol. Aqu tenis un ejemplo sencillo extrado dehttp://ants.dif.um.es/staff/juanbot/ml/files/20022003/tema3.pdf:

4

Como veis, un rbol de decisin es bsicamente una herramienta clasificadora.As lascosas,noresultadisparatadoimaginarquepodramosusarunadetalesestructurasparacrearnuestroadivinosinmsque,porejemplo,situarlaspreguntasenlasramasdelrbolylospersonajesenlashojas.

Actividad 1: Respuesta a las preguntas del apartado 3. Para que esta solucin seaaplicable en nuestro caso, habremos de analizar cmo responde a las cuestionesfundamentalesqueelproblemaplantea:

Cmoelijoqupreguntahaceracontinuacin? Cmorelacionoelconjuntodepreguntasconeldepersonajes? Cmovoylimitandoelconjuntodepersonajesposibles?

Actividad 2: Planteamiento de un algoritmo. Una vez que tengamos definida laestructuradenuestrorbol,deberemosconcebirelalgoritmodefuncionamientointernode laaplicacinde formaqueempleeadecuadamente la informacinrecogidaendichorbol para encontrar el personaje buscado. Podis proponer un algoritmo de estandole?

Actividad3:Problemasdeestasolucin.Denuevo,estasolucin,quedeentradapareceadaptarse muy bien a nuestro problema, plantea a poco que nos fijemos algunasdificultadesquearrojanciertassombrassobresu idoneidad.Quproblemasospareceque esta estrategiapuedeplantear? Resulta estauna solucin fcilmente escalable siaumenta el nmero de personajes? Y si aumenta el nmero de preguntas? Es unaestrategia flexible, en cuanto a que me permite realizar las preguntas en distintosrdenes?

5

6. Tercerintento:Tablacruzada.

Sinosdamos cuenta,hayunaasociacinbsicaenelproblemaque cualquier solucinadoptadadeberaabordar: laasociacinentrepreguntasypersonajes.Sepuedepensarenvariasformasderesolveresaasociacin,siendounadelasmsdirectaslasiguiente:

Paracadapregunta,hedesaberqupersonajeslarespondenafirmativamente.Estainformacinpodrarepresentarlamedianteunatablacomolasiguiente:

Personaje1 Personaje2 Personaje3 Personajem

Pregunta1 x x Pregunta2 x x x. x x x xPreguntan x

En esta tabla, una casilla marcada con una x indica que un personaje responderaafirmativamente a una pregunta: por ejemplo, la interseccin entre la pregunta Esmujer?yelpersonajeIsabelAllendeestaramarcadaconunax.

Sinos fijamos,una tablacomostano slonospermite resolver laasociacinanterior(Paracadapregunta,hedesaberqupersonajes larespondenafirmativamente),sinoquetambinnosresuelvelaasociacincomplementaria,locualnosvaaresultarmuytil,apocoquelopensemos:paracadapersonaje,podemosfcilmentesaberqupreguntasresponderaafirmativamente.

Actividad1:Respuestaa laspreguntasdelapartado3.Denuevo, laprimeracuestinaplantearnosessiestaestructuranospermitirencontrarunarespuestasencillapara lascuestionesquedefinenlaesenciadenuestroproblema.Qurespuestasnosofreceestasolucinalaspreguntasdeantes?

Cmoelijoqupreguntahaceracontinuacin? Cmorelacionoelconjuntodepreguntasconeldepersonajes? Cmovoylimitandoelconjuntodepersonajesposibles?

Actividad2:Planteamientodeunalgoritmo.Lospasosserepiten:unavezevaluada,demanera inicial, laadecuacindeestasolucinanuestroproblema, lasiguiente laboresconcebirunalgoritmoque,empleandolatabladedobleentradadescrita,consigaadivinarelpersonajepensado.Comosiempretambin,esmuyposiblequenecesitisalmacenarinformacinadicional.

Actividad 3: Problemas. De nuevo, toca completar el anlisis tratando de descubrirposiblespuntosdbilesaestasolucin.Porejemplo,puedeserunproblema lalentitud

6

cuando tengamos varios centenares de miles de personajes y varios centenares depreguntas?

7. Propuestafinaldesolucin.

Tras analizar las tres posibles estrategias a seguir, llegar el momento de pararse unmomentoyelegirunaovarias.

Paraempezar,seosocurrealgunaotraestrategiaque,unavezconocidoenprofundidadelproblema,podraresultaradecuadayquenosehayamencionadoaqu?

Sinoesas,habrque seleccionarentre lasyaanalizadas,y seguir trabajandoconellallegandoamayoresnivelesdedetalle.Aunquecomoacabamosdemencionarexisteotraopcin:emplearvarias.Porejemplo,sepuedepensarenutilizarunaestrategiapara lasprimeraspreguntas(que,porejemplo,permitahacerunaseleccinentrevariosconjuntosdisjuntosdepersonajes),yotradiferenteparalasltimas(que,siguiendoconelejemploanterior,vayaorientadaabuscardentrodelconjuntopreseleccionado).

Pensad un poco sobre el asunto, e incluid en el entregable de la prctica una brevedescripcindevuestrasolucinfinal.

8. Otrosaspectosaincluir.

Hayunpardeelementosquesernmuydeseablesennuestroadivino,yalosquehabrqueprestarunadebidaatencinsiesquenosehahechoya.

El primero de estos aspectos es el aprendizaje: va a ser capaz nuestro sistema deaprendersobrelamarcha,refinandosuspreguntas,personajes,etc.?

Actividad 1: Preguntas iniciales sobre el aprendizaje. Meditad un poco sobre lassiguientescuestiones:

Cuandonuestroadivinofalle,quinformacindeberapedirlealusuarioycmodeberaemplearla?

Cundodeberanuestroadivinoaadirunnuevopersonaje?Esnecesarioquepidapreguntasparacaracterizardeentradaadichonuevopersonaje?

Cundodeberaelsistemapedirnuevaspreguntas?Actividad 2: Algoritmo de aprendizaje. A la luz de lo respondido a las anteriorescuestiones,elaboradunpequeoalgoritmodeaprendizajeparaeladivino,enunciandocadaunodesuspasos.

7

Otro aspecto a considerares laescalabilidad: loquehacepopular aAkinatornoes sucapacidadparaadivinarpersonajescon tansloveintepreguntas (eso,comoyahemosido viendo, no ha de resultar tan espectacular), sino su habilidad para adivinar casicualquier personaje, lo cual traducido a trminos ms concretos significa que puedediscriminar,probablemente,entrevarioscientosdemilesdeellos.

Vamosatratardeincluiresacapacidadennuestroadivinocasero.

Actividad3:Preguntas inicialessobreescalabilidad.Comoenelcasoanterior,vamosatratar de identificar los aspectos ms importantes que definen este nuevo problema,comoantesalahaciasusolucin.

En teora, y en el mejor de los casos, qu poder de discriminacin tienen npreguntas?

Tienesentidoquehayaunnmerodepreguntasmayorqueveinteasociadasaunpersonajedeterminado,a findemejorarnuestracapacidadparadistinguirlodeotroparecido?

Si suponemos entonces que hacer crecer indefinidamente el nmero depreguntas no es el mejor camino para aumentar, a partir de cierto punto, lascapacidadesdenuestroadivino,quinformacinadicionalpodramosemplear?CuleslaquepareceutilizarAkinator?

Actividad 4: Modificaciones para una mayor escalabilidad. Modifica la estrategia deadivinacindiseadahastaahorapara incluireltratamientodeestanueva informacin,incluyendocmohadeemplearseycundoduranteelprocesodeadivinacin.

9. Paralosquenotenganbastantetodava

Osatreviso implementarunpequeosoftwarebasadoeneldiseorealizadohastaelmomento?Estoes,osatrevisaprogramarvuestroadivino?

Porsupuesto,podisemplearellenguajedeprogramacinquedeseis