Cerca i Anàlisi d'Informació Massiva

Crèdits
6
Tipus
Complementària d'especialitat (Sistemes d'informació)
Requisits
Departament
CS
Mail
caim@cs.upc.edu
La quantitat d'informació emmagatzemada digitalment en moltes organitzacions, o col·lectivament en la web, és avui dia prou gran perquè trobar allò que es busca sigui generalment complicat. El camp conegut com a "Information Retrieval" tracta dels mètodes per organitzar informació i permetre després als usuaris trobar-la de manera còmoda i eficient. Cobrirem les tècniques bàsiques de cerca de documentació textual basada en paraules clau. Examinarem després el cas de la cerca en la web, on la presència d'hiperenllaços pot usar-se no sols per dirigir la cerca sinó per valorar l'interès de cada pàgina - és el cas del conegut algorisme PageRank. Veurem l'extensió d'aquestes tècniques al cas de les xarxes socials on el graf d'interaccions entre usuaris proporciona molta informació de què pot interessar a cadascun. Finalment, estudiarem algorismes aleatoris eficients per a fluxos de dades massives.

Professorat

Responsable

  • David Garcia Soriano (david.garcia.soriano@upc.edu)
  • Marta Arias Vicente (marias@cs.upc.edu)

Hores setmanals

Teoria
1.5
Problemes
0.5
Laboratori
2
Aprenentatge dirigit
0
Aprenentatge autònom
6

Competències

Competències Tècniques de cada especialitat

Especialitat sistemes d'informació

  • CSI2 - Integrar solucions de Tecnologies de la Informació i les Comunicacions, i processos empresarials per a satisfer les necessitats d'informació de les organitzacions, permetent que assoleixin els seus objectius de forma efectiva.
    • CSI2.3 - Demostrar coneixement i capacitat d'aplicació dels sistemes d'extracció i de gestió del coneixement.
    • CSI2.6 - Demostrar coneixement i capacitat d'aplicació dels sistemes d'ajuda a la presa de decisions i de bussines intelligence.

    • Especialitat computació

  • CCO2 - Desenvolupar de forma efectiva i eficient els algorismes i el software apropiats per a resoldre problemes complexos de computació.
    • CCO2.5 - Implementar software de cerca d'informació (information retrieval).

    • Competències Transversals

    Aprenentatge autònom

  • G7 [Avaluable] - Detectar carències en el coneixement propi i superar-les mitjançant la reflexió crítica i l'elecció de la millor actuació per ampliar aquest coneixement. Capacitat per a l'aprenentatge de nous mètodes i tecnologies, i versatilitat per a adaptar-se a noves situacions.
    • G7.3 - Aprenentatge autònom: capacitat de planificació i organització del treball personal. Aplicar els coneixements adquirits a la realització d'una tasca en funció de la pertinença i de la importància, decidir la manera de dur-la a terme i el temps que se li ha de dedicar, i seleccionar les fonts d'informació més adients. Identificar la importància d'establir i mantenir contactes amb els companys d'estudis, amb el professorat i amb els professionals (networking). Identificar fòrums d'informació sobre enginyeria TIC, els seus avenços i el seu impacte en la societat (IEEE, associacions, etc.).

    • Objectius

    1. Conèixer els problemes associats a l'emmagatzemament i recuperació de la informació, sobretot de tipus textual.
      Competències relacionades: CCO2.5,
    2. Entendre que l'efectivitat en la cerca i recuperació de la informació està molt relacionada amb l'organització i descripció d'aquesta informació.
      Competències relacionades: CCO2.5, G7.3,
    3. Conèixer i entendre l'estructura, arquitectura i funcionament de la web, i els elements relacionats amb ella: índexos, cercadors, crawlers, entre altres.
      Competències relacionades: CSI2.3, G7.3,
    4. Conèixer i entendre els paràmetres de descripció de xarxes complexes, així com els algorismes principals d'anàlisi de la seva estructura.
      Competències relacionades: CSI2.3, CSI2.6, G7.3,
    5. Reconèixer les oportunitats d'ús de la informació massiva per als fins d'una organització, i triar els mètodes, eines i procediments més adients.
      Competències relacionades: CSI2.6, G7.3,
    6. Poder decidir les tècniques de recuperació de la informació que poden ser efectives en un sistema d'informació concret, sobretot de tipus textual.
      Competències relacionades: CSI2.3, CSI2.6, CCO2.5, G7.3,
    7. Poder avaluar l'efectivitat i utilitat, d'acord amb diversos criteris, d'un sistema de recuperació de la informació.
      Competències relacionades: CSI2.3, CSI2.6, CCO2.5, G7.3,
    8. Poder implementar les principals tècniques vistes a l'assignatura
      Competències relacionades: CCO2.5, G7.3,
      Subcompetences
      • Poder implementar les tècniques bàsiques (algorismes i estuctures de dades) de recuperació de la informació.
      • Poder implementar els algorismes bàsics d'anàlisi de xarxes.
    9. Saber utilitzar, adaptar i extendre software obert.
      Competències relacionades: G7.3,
      Subcompetences
      • Per exemple: Lucene, base de dades DEX, WIRE crawler, entre altres.

    Continguts

    1. Introducció
      Necessitat de les tècniques de cerca i anàlisi d'informació massiva. Cerca i anàlisi vs. bases de dades. Procés de recuperació de la
      informació. Preprocés i anàlisi lèxica
    2. Cerca en grans volums de dades
      Ranking i relevància per a models web. Algorisme PageRank. Crawling. Arquitectura de un sistema simple de cerca a la web.
      Tècniques basades en taules de dispersió sensibles a la proximitat (LSH).
    3. Models de recuperació de la informació
      Definició formal i conceptes bàsics: Models abstractes de documents i llenguatges d'interrogació. Model booleà. Model vectorial.
      Fitxers invertits i fitxers de signatures. Compressió d'índexos. Exemple: Implementació eficient de la regla del cosinus amb mesura tf-idf.
      Recall i precisió. Altres mesures de rendiment. Col·leccions de referència. "Relevance feedback" i "query expansion".
    4. Arquitectura de sistemes pera la gestió d'informació massiva
      Escalabilitat, alt rendiment i tolerància a fallides: el cas de cercadors web massius. Arquitectures distribuïdes. Exemple: Hadoop.
    5. Anàlisi de xarxes
      Paràmetres descriptius i característiques de les xarxes: grau, diàmetre, xarxes "small-world", entre altres. Algorismes sobre xarxes: clustering, detecció de comunitats i de nodes influents, reputació, entre altres.
    6. Algorismes per a dades massives
      Resums (sketches) i fluxos de dades (streaming). Mostratge (sampling). Es veuran algorismes com a RESERVOIR SAMPLING, count-min sketch, hyper-log-log, etc.

    Activitats

    Activitat Acte avaluatiu


    Introducció i Models de Recuperació de la Informació


    Objectius: 1 2 6
    Continguts:
    Teoria
    4.5h
    Problemes
    3h
    Laboratori
    10h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    16h

    Cerca en grans volums de dades


    Objectius: 3 5 9
    Continguts:
    Teoria
    3.5h
    Problemes
    1h
    Laboratori
    6h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    12.5h

    Primer examen parcial

    Examen parcial de la primera part de l'assignatura.
    Objectius: 1 2 3 5 6 7
    Setmana: 9
    Teoria
    0h
    Problemes
    0h
    Laboratori
    0h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    0h

    Arquitectura de sistemes de cerca a la web


    Objectius: 3 6 8 9
    Continguts:
    Teoria
    4h
    Problemes
    1h
    Laboratori
    4h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    8.5h

    Anàlisi de xarxes


    Objectius: 4 6 7 8 9
    Continguts:
    Teoria
    3.5h
    Problemes
    1.5h
    Laboratori
    4h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    12.5h

    Algorismes per a dades massives


    Objectius: 5 8
    Continguts:
    Teoria
    2h
    Problemes
    1h
    Laboratori
    4h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    12h

    Segon examen parcial


    Objectius: 1 2 3 4 5 6 7 8 9
    Setmana: 15 (Fora d'horari lectiu)
    Teoria
    0h
    Problemes
    0h
    Laboratori
    0h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    0h

    Primera prova laboratori


    Objectius: 1 2 3 4 5 6 7 8 9
    Setmana: 6
    Teoria
    0h
    Problemes
    0h
    Laboratori
    0h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    0h

    Segona prova de laboratori


    Objectius: 1 2 3 4 5 6 7 8 9
    Setmana: 14
    Teoria
    0h
    Problemes
    0h
    Laboratori
    0h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    0h

    Metodologia docent

    - Classes de teoria. Abans de cada classe, l'estudiant haurà d'haver llegit els apunts o materials del tema a desenvolupar, anunciat amb temps. L'estudiant tindrà també a la seva disposició un qüestionari de preguntes bàsiques del tema, per comprovar si el grau de comprensió que ha assolit. A la classe, el professor exposarà els punts principals, donant per suposat que l'estudiant ha fet la feina indicada i intentat respondre el qüestionari, i es discutiran en comú els dubtes que puguin haver trobat els estudiants.

    - Classes de problemes. Professors i estudiants comentaran i compararan les solucions dels problemes que el professor haurà indicat amb temps suficient abans de cada classe. Les discussions poden fer-se en comú entre tota la classe o particularment entre el professor i un alumne. El professor donarà per suposat que els estudiants han passat un temps raonable intentant resoldre aquests exercicis, i prioritzarà l'atenció a aquells que ho hagin fet així.

    - Classes de laboratori: Abans de cada classe, l'estudiant haurà d'haver llegit el guió de la feina pràctica a desenvolupar en la sessió. Durant la classe, l'estudiant durà a terme la feina indicada en el guió amb el guiatge del professor. En moltes de les sessions, el guió contindrà feina que, probablement, calgui acabar com a treball personal després de la sessió de laboratori. Per a la majoria de sessions de laboratori caldrà redactar un informe curt de la feina feta o lliurar aquesta feina (p.ex., fitxers de resultats i programes escrits).

    - Treball personal: Així doncs, cada tipus d'activitat presencial implica una certa quantitat de treball personal abans o després. Addicionalment, algun tema o temes de l'assignatura poden no tenir classes de teoria o d'exercicis associats, i els estudiants hauran d'estudiar-lo pel seu compte, i usar les sessions d'activitats dirigides si ho desitgen per avaluar que han fet el progrés suficient.

    Mètode d'avaluació

    L'assignatura comprendrà els següents actes avaluatius:

    - Un primer examen parcial, fet cap a meitat del curs, de la matèria vista fins llavors. Sigui P1 la nota obtinguda en aquest examen.

    - Un segon examen parcial, enfocat a la segona meitat del curs, però on pot entrar qualsevol part de l'assignatura. Sigui P2 la nota obtinguda en aquest examen.

    - Dues proves presencials de laboratori. Sigui L la nota mitjana obtinguda d'aquestes dues proves.

    Les tres notes L, P1 i P2 són entre 0 i 10.
    La nota final de l'assignatura serà el resultat de la fórmula 20% L + 40% P1 + 40% P2.

    Pel que fa a la nota de la competència associada a Aprenentatge Autònom, es calcularà una nota numèrica així:

    - Algunes de les preguntes de les proves presencials avaluatòries, marcades especialment, versaran total o parcialment sobre temes que l'estudiant haurà de preparar pel seu compte, amb poca o cap cobertura a classe de teoria i problemes, que s'hauran indicat durant el curs. Sigui S la mitjana d'aquestes preguntes en els exàmens aplicables a l'estudiant, i escalada a l'interval [0,1].

    La nota de la competència serà:
    - D si S és inferior a 0.3
    - C si S és entre 0.3 i 0.499
    - B si S és entre 0.5 i 0.699
    - A si S és 0.7 o més.

    Bibliografia

    Bàsic

    Complementari

    Capacitats prèvies

    Genèricament, les que s'adquireixen a les assignatures del grau que són requisits d'aquesta.

    Específicament:

    - Usar amb comodidat els conceptes bàsics d'àlgebra lineal, matemàtica discreta, probabilitat i estadística.

    - Programar amb comoditat en llenguatges orientats a objectes, incloent herència entre classes.

    - Conèixer les principals estructures de dades per a l'accés eficient a informació i les seves implementacions (llistes, hashing, arbres, grafs, heaps). Ser capaç d'usar-les per a construir programes eficients. Poder analitzar el temps d'execució i memòria usat per un algorisme de dificultat mitjana. Tenir una certa idea de la diferència en temps d'accés entre memòria principal i memòria secundària.

    - Conèixer els elements principals d'una base de dades relacional i de llenguatges d'accés tipus SQL.