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