Pràctica d'Aprenentatge - Q1-2005/06


Data límit d'entrega: 2/12/2005, 14.00h

En aquesta pràctica treballareu un tema d'aprenentatge automàtic amb més profunditat del que hem fet a classe. L'objectiu és que, a partir de la informació que trobeu a llibres i articles de recerca sigueu capaços d'aprofundir en un tema en particular, entendre els aspectes bàsics de la seva motivació i desenvolupament, realitzar un estudi experimental seriós i sintetitzar els aspectes més rellevants i els resultats en un document.

Les pràctiques s'hauran de fer en grups de 3 persones.

Hi han dos grups de propostes, un de pràctiques en les que utilitzareu Weka o alguna altra implementació existent dels algorismes que necessiteu i un altre de pràctiques que requereixen un petit desenvolupament de codi. Obviament es tindrà en compte la feina requerida per les implementacions i, per tant, l'exigència de recopilació i comprensió de bibliografia i/o obtenció de resultats experimentals serà una mica més elevada per a les pràctiques que no la requereixen per tal de compensar la feina adicional.

Si teniu una idea de pràctica alternativa, poseu-vos en contacte amb mí i ho podem discutir. Teniu en compte que no ha de ser una proposta basada únicament en aplicar aprenentatge a un conjunt de dades concret, sino que ha de focalitzar-se sobre un tema/metodologia específic (tot i que després l'apliqueu sobre algun conjunt que us sembli d'interés).

Normes d'entrega de la pràctica (MOLT IMPORTANT)

L'entrega de la pràctica constarà de tres fases obligatòries. No s'acceptarà cap pràctica que no hagi passat les dues primeres fases (i tot formarà part de la nota final):
  1. Recollida d'informació sobre el tema escollit a llibres, articles o Internet i presentació d'una proposta dels mètodes/algorismes que heu decidit provar/implementar, i les referències que fareu servir. Heu de parlar amb mí (en persona) per validar la proposta i decidir quina és la tasca mínima que heu de fer i si hi ha feina adicional que us pot proporcionar punts extra.
  2. Presentació d'un pla d'avaluació que contingui quins factors voleu estudiar (diferents paràmetres, diferents tipus de dades, complexitat dels resultats, etc.) i quins conjunts de dades utilitzareu. Igualment l'heu de presentar en persona i haurà de ser validat.
  3. Entrega de la documentació final de la pràctica.

PROPOSTES

Cada proposta només pot ser escollida per un grup. L'assignació es farà per ordre d'arribada de la petició.

(EN VERMELL LES QUE JA ESTAN ESCOLLIDES)

Sense implementació

La presència d'atributs irrellevants i/o redundants pot afectar el rendiment i la eficiència de molts mètodes d'aprenentatge. Per solucionar aquest problema s'han desenvolupat mètodes de selecció automàtica d'atributs (feature selection). L'objectiu d'aquesta pràctica és escollir alguns d'aquests mètodes (només entre els supervisats) i realitzar un estudi experimental del seu rendiment.
En la seva formulació mes simple, els algorismes IBL, també coneguts com a nearest neighbor (NN), han de emmagatzemar tot el conjunt d'instàncies per posteriorment fer prediccions recuperant la instància o instàncies més propera/es. Per grans volums de dades, els requeriments de memòria d'aquests algorismes poden ser massa elevats, per la qual cosa s'han desenvolupat mètodes que només guarden un conjunt seleccionat d'instàncies. L'objectiu d'aquesta pràctica és escollir alguns d'aquests mètodes i realitzar un estudi experimental del seu rendiment.
Les tècnicas d'aprenentatge d'ensembles construeixen una col.lecció de classificadors a partir d'un classificador base i manipulant les dades per tal de que els classificadors mostrin una certa diversitat. Els ensembles obtenen una predicció a partir de la combinació de les prediccions individuals de cadascun dels components, resultant, sota certes condicions una tècnica efectiva de reduïr l'error. L'objectiu d'aquesta pràctica és escollir alguns d'aquests mètodes i realitzar un estudi experimental del seu rendiment.
La classificació de textos (text categorization/classification) és l'assignació de textos en llenguatge natural a un conjunt de categories predefinides segons el seu contingut. Aquesta tasca es pot resoldre mitjançant l'aprenentatge d'un classificador a partir de documents etiquetats, però això implica que s'ha d'obtenir una representació en termes de parelles <atribut, valor> a partir de cada document. L'objectiu d'aquesta pràctica és estudiar els mètodes de preprocés per obtenir una representació dels documents adient per a l'aprenentatge i realitzar un estudi experimental del rendiment obtingut combinant alguns d'aquests mètodes i un classificador.
La regressió és una tasca d'aprenentatge semblant a la classificació però on els valors a predir no són discrets, sino numèrics. L'objectiu d'aquesta pràctica és escollir alguns mètodes de regressió i realitzar un estudi experimental del seu rendiment.
El mètode separate-and-conquer és molt popular entre els sistemes d'aprenentatge de regles disjuntives. Però tot i que molts sistemes estiguin basats en aquest concepte, existeixen molts aspectes que poden variar com la direcció de la cerca, les heurístiques per avaluar hipòtesi o els mecanismes de poda. L'objectiu d'aquesta pràctica és escollir alguns mètodes d'aprenentatge de regles disjuntives i realitzar un estudi experimental del seu rendiment.

Amb implementació

Aquestes propostes són de mètodes que no es troben o costen de trobar en les implementacions públiques d'algorismes d'aprenentatge, algunes perquè són mètodes relativament recents i sobre temes encara molt oberts (t'animes a fer una petita intro a la recerca?). La primera proposta és més genèrica per a qui estigui especialment interessat en algun algorisme/mètode en concret i vulgui implementar-lo.
Podeu escollir un o més algorismes d'aprenentatge i/o alguna técnica de millora o preprocés (per exemple, selecció d'atributs) similar a les proposades abans sense implementació i implementar-la vosaltres. En aquest cas heu de parlar amb mi per validar la proposta.
Una alternativa a la construcció d'ensembles mencionada abans, és la combinació de classificadors intentant aprendre quines són les regions de decisió en que cada classificador rendeix millor de manera que es pugui escollir el classificador més adient per a cada instància que s'hagi de predir. Concretament hi han tècniques de selecció dinàmica (Dynamic Selection, DS) o d'utilització de àrbitres (arbiters o referees). L'objectiu d'aquesta pràctica és escollir alguns mètodes de combinació de classificadors d'aquests tipus, implementar-los i realitzar un estudi experimental del seu rendiment. La idea és no haver d'implementar els classificadors que formen part de la combinació i utilitzar per això alguna implementació ja existent.
Els algorismes iteratius de clustering que utilitzen una estratègia hill climbing tendeixen a donar diferents resultats, més o menys óptims, segons la inicialització que es faci dels clusters. Una solució és escollir les instàncies per a inicialitzar els clusters a l'atzar i repetir el procés varies vegades seleccionant el millor resultat. Una altra, és utilitzar mètodes més elaborats per decidir quines instàncies seleccionar. L'objectiu d'aquesta pràctica és escollir alguns mètodes d'inicialització i un o més algorismes de clustering, implementar-los i realitzar un estudi experimental del seu rendiment.
De manera similar que a l'aprenentatge supervisat (classificació), la presència d'atributs irrellevants pot dificultar l'obtenció de bons resultats quan apliquem tècniques de clustering. Desenvolupar mètodes de selecció d'atributs (feature selection) per a algoritmes de clustering es, però, força més complicat ja que no existeix una idea clara del concepte de rellevància per a aquests problemes. L'objectiu d'aquesta pràctica és escollir algun mètode de selecció d'atributs per clustering i un o més algorismes, implementar-los i realitzar un estudi experimental del seu rendiment.
Els mètodes de discretització transformen els atributs numèrics en discrets obtenint un conjunt d'intervals en els quals particionar els seus valors. Quan és necessari discretitzar atributs per a tasques d'aprenentatge no supervisat, com ara clustering, s'han d'utilitzar mètodes de discretització que no facin servir informació sobre las classes (o sigui, també no supervisats). L'objectiu d'aquesta pràctica és escollir alguns mètodes de discretització d'atributs no supervisats i un o més algorismes de clustering, implementar-los i realitzar un estudi experimental del seu rendiment.
El clustering conceptual (conceptual clustering) és una denominació utilitzada des de la IA per descriure algoritmes que no només obtenien una partició de les instàncies en grups, sino que també obtenien descripcions per a cadascun d'aquests grups. En realitat, la diferència amb altres aproximacions al clustering és en com enfocar el problema però els algorismes resultants són molt semblants. Tot i així, per raons potser més aviat històriques hi ha una sèrie d'algorismes etiquetats com a conceptual clustering. L'objectiu d'aquesta pràctica és escollir un o més algorismes de conceptual clustering, implementar-los i realitzar un estudi experimental del seu rendiment.