Cerca i Anàlisi de la Informació

Crèdits
6
Tipus
Obligatòria
Requisits
Aquesta assignatura no té requisits , però té capacitats prèvies
Departament
CS
Els grans respositoris de dades semi-estructurades com ara text, i en especial la web, necessiten tècniques especialitzades per ser cercades i analitzades eficientment. L'assignatura cobreix tècniques de cerca i anàlisi de textos i altra informació semi-estructurada, d'estructurs enllaçades i en particular la web i les xarxes socials, els sistemes recomanadors com a manera de complementar la cerca a iniciativa de l'usuari, i algunes tècniques algorísmiques i estructures de dades particularment útils amb dades massives.

Professorat

Responsable

  • Marta Arias Vicente (marias@cs.upc.edu)

Altres

  • Jordi Turmo Borrás (turmo@cs.upc.edu)
  • Juan Luis Esteban Ángeles (esteban@cs.upc.edu)

Hores setmanals

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

Competències

Competències Tècniques

Competències tècniques

  • CE1 - Utilitzar amb destresa els conceptes i mètodes matemàtics subjacents els problemes de la ciència i l'enginyeria de les dades.
  • CE4 - Utilitzar els sistemes de computació actuals, inclosos els sistemes d'alt rendiment, per al procés de grans volums de dades des del coneixement de la seva estructura, funcionament i particularitats.
  • CE6 - Construir o utilitzar sistemes de processat i comprensió del llenguatge escrit, integrant-lo en altres sistemes dirigits per les dades. Dissenyar sistemes de recerca d'informació textual o hipertextual i d'anàlisi de xarxes socials.
  • CE7 - Demostrar coneixement i capacitat d'aplicació de les eines necessàries per a l'emmagatzematge, el processament i l'accés a les dades.

    • Competències Transversals

    Transversals

  • CT4 - Treball en equip. Ser capaç de treballar com a membre d'un equip interdisciplinari, ja sigui com un membre més o realitzant tasques de direcció, amb la finalitat de contribuir a desenvolupar projectes amb pragmatisme i sentit de la responsabilitat, assumint compromisos tenint en compte els recursos disponibles.
  • CT5 - Ús solvent dels recursos d'informació. Gestionar l'adquisició, l'estructuració, l'anàlisi i la visualització de dades i informació en l'àmbit de l'especialitat i valorar de forma crítica els resultats d'aquesta gestió.
  • CT6 [Avaluable] - Aprenentatge autònom. Detectar deficiències en el propi coneixement i superar-les mitjançant la reflexió crítica i l'elecció de la millor actuació per ampliar aquest coneixement.
  • CT7 - Tercera llengua. Conèixer una tercera llengua, preferentment l'anglès, amb un nivell adequat oral i escrit i d'acord amb les necessitats que tindran els titulats i titulades.

    • Bàsiques

  • CB2 - Que els estudiants sàpiguen aplicar els seus coneixements al seu treball o vocació d'una manera professional i posseeixin les competències que solen demostrar-se mitjançant l'elaboració i defensa d'arguments i la resolució de problemes dins la seva àrea d'estudi.
  • CB3 - Que els estudiants tinguin la capacitat de reunir i interpretar dades rellevants (normalment dins la seva àrea d'estudi) per emetre judicis que incloguin una reflexió sobre temes rellevants d'índole social, científica o ètica.
  • CB4 - Que els estudiants puguin transmetre informació, idees, problemes i solucions a un públic tant especialitzat com no especialitzat.

    • Competències Tècniques Generals

    Genèriques

  • CG2 - Elegir i aplicar els mètodes i tècniques més adequats a un problema definit per dades que representin un repte pel seu volum, velocitat, varietat o heterogeneïtat, inclosos mètodes informàtics, matemàtics, estadístics i de processament del senyal.
  • CG3 - Treballar en equips i projectes multidisciplinaris relacionats amb el processat i explotació de dades complexes, interactuant fluidament amb enginyers i professionals d'altres disciplines.
  • CG4 - Identificar oportunitats per a aplicacions innovadores orientades a dades en entorns tecnològics en contínua evolució.
  • CG5 - Poder recórrer a coneixements fonamentals i metodologies de treball sòlides adquirits durant els estudis per adaptar-se als nous escenaris tecnològics del futur.

    • Objectius

    1. Descriure diferents models per avaluar similaritat entre textos, i com s'apliquen a la cerca textual. Decidir quin dels models és el més adequat a un escenari concret que involucra cerca de textos. Implementar els models des de zero (en un sistema molt bàsic) o damunt un sistema d'indexació de textos que sigui altament escalable.
      Competències relacionades: CB2, CB3, CT5, CT6, CT7, CE1, CE4, CE6, CE7, CG2, CG4, CG5,
    2. Descriure els avantatges, de cara a efectuar cerques efectives, d'utilitzar la informació donada pels enllaços en estructures hiperenllaçades, com ara la web, les xarxes socials digitals, i la web semàntica. Descriure els principals paràmetres que s'usen per caracteritzar aquestes estructures enllaçades. Reproduir els algorismes més utilitzats per establir importància en aquestes estructures (p.ex. pagerank), per descobrir estructura en elles (p.ex., descobriment de comunitats) i per millorar els resultats de cerques proposades per un usuari. Implementar aquests algorismes des de zero en un sistema molt bàsic, o damunt de sistemes de processament de dades massives de manera que puguin escalar.
      Competències relacionades: CB2, CB3, CT5, CT6, CT7, CE1, CE4, CE6, CE7, CG2, CG4, CG5,
    3. Avaluar l'efectivitat de sistemes de cerca en sistemes complexos, descrivint-la en termes de mesures dures com ara "recall" i "precision" però també en termes de mesures toves com ara la satisfació dels usuaris, la novetat i la finalització de tasques. Adaptar el funcionament i la presentació de sistemes de cerca d'informació amb el feedback de l'experiència d'usuaris metòdicament recollida.
      Competències relacionades: CB2, CB3, CB4, CT4, CT5, CT6, CT7, CE1, CG3, CG4, CG5,
    4. Definir el problema de la recomanació i les diferències amb altres problemes relacionats amb informació prèviament emmagatzemada (cerca, aprenentatge, ...). Descriure els principals abordatges al problema de la recomanació d'items i els avantatges i inconvenients de cadascun. Descriure els principals algorismes de cadascun dels abordatges. Ser capaç d'implementar-ne versions bàsiques des de zero, o versions avançades damunt de sistemes de processament massius de dades. Avaluar l'efectivitat de sistemes de recomanació, tant en termes de mesures dures com de mesures toves com ara la satisfacció de l'usuari. Decidir les formes de recomanació més adequades a escenaris reals simples, incloent la caracterització dels usuaris potencials.
      Competències relacionades: CB2, CB3, CB4, CT5, CT6, CT7, CE1, CE4, CE7, CG2, CG4, CG5,
    5. Recórrer de manera a paradigmes algorísmics coneguts per tractar amb problemes de dades caracteritzats per alt volum i alta velocitat. S'inclouen: algorismes de "streaming" que tracten fluxos de dades amb poc temps per element, i poca memòria. Algorismes per respondre preguntes de proximitat, en particular amb informació geolocalitzada. Algorismes que utilitzen mostreig per extreure conclusions fiables sobre grans volums de dades. Integració de les tècniques vistes a la resta del curs amb tècniques algorísmiques d'altres assignatures, com ara "machine learning", "clustering" i "pattern mining". Tècniques per tractar amb dades sensibles, com ara anonimització i "privacy-preserving machine learning". "Caching" consistent i distribuït.
      Competències relacionades: CB2, CB3, CT5, CT6, CT7, CE1, CE4, CE7, CG2, CG4, CG5,
    6. Integrar les tècniques descrites als anteriors objectius en un projecte petit però realista. Tenir la capacitat per dissenyar l'arquitectura d'un sistema complex i triar les tècniques, i les tecnologies vistes amb anterioritat durant el curs que s'hi aplicarien. L'objectiu no és finalitzar la implementació del sistema, sinó arribar a un nivell de detall del disseny que permetés encarregar a un equip de programació la seva finalització.
      Competències relacionades: CB2, CB4, CT4, CT5, CT7, CE1, CE4, CE6, CE7, CG2, CG3, CG4, CG5,
    7. Avaluar de manera elemental les implicacions dels sistemes que s'aprenen a construir en l'assignatura pel que fa a privacitat, seguretat, ètica i drets de les persones. S'enten per "de manera elemental" ser capaç de detectar que aquestes implicacions són prou significatives com per buscar l'opinió d'un experts en la matèria, en particular en relació al RGPD i la necessitat de dur a terme anàlisis de risc i impacte.
      Competències relacionades: CB2, CB3, CB4, CT5, CE7, CG4,

    Continguts

    1. Cerca i anàlisi d'informació textual
      Models booleà i vectorial. Cerca basada en paraules clau. Preprocés dels textos. Indexació. Avaluació d'estratègies de cerca. Formació de grups i classificació de textos. Models generatius (LSI, LDA).
    2. Cerca i anàlisi en estructures enllaçades
      La web: Algorísmes d'avaluació en estructures hiperenllaçades. "Crawling" i "scraping". Xarxes socials: Mesures de centralitat. Comunitats. Influència. Web semàntica.
    3. Recomanació
      Sistemes recomanadors. Recomanació basada en contingut i recomanació basada en la comunitat ("collaborative filtering"). Consideracions pràctiques.
    4. Algorismes per a dades massives
      Resums (sketches) i fluxos de dades (streaming). Mostratge (sampling). Preguntes de proximitat. Dades geolocalitzades. "Caching" consistent i distribuït. Tractament de dades sensibles: anonimització, "end-to-end encryption" i "privacy-preserving machine learning"

    Activitats

    Activitat Acte avaluatiu


    Activitat sobre el contingut "Cerca i anàlisi d'informació textual"

    A teoria, el professor presenta les motivacions i principals conceptes, i en acabar professor i estudiants resolen conjuntament 2-3 problemes de consolidació. A laboratori, els estudiants resolen un cas relacionat amb el contingut.
    • Teoria: Format classe magistral + resolució grupal de problemes
    • Laboratori: Els estudiants treballen en un cas pràctic relacionat amb el contingut, que pot incloure tasques de disseny, implementació, avaluació. La feina pot ser individual o grupal.
    Objectius: 1 3 6 7
    Continguts:
    Teoria
    6h
    Problemes
    0h
    Laboratori
    6h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    12h

    Activitat sobre el contingut "Cerca i anàlisi en estructures enllaçades"

    A teoria, el professor presenta les motivacions i principals conceptes, i en acabar professor i estudiants resolen conjuntament 2-3 problemes de consolidació. A laboratori, els estudiants resolen un cas relacionat amb el contingut.
    • Laboratori: Els estudiants treballen en un cas pràctic relacionat amb el contingut, que pot incloure tasques de disseny, implementació, avaluació. La feina pot ser individual o grupal.
    Objectius: 2 6 7
    Teoria
    6h
    Problemes
    0h
    Laboratori
    6h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    12h

    Activitat sobre el tema "Recomanació"

    A teoria, el professor presenta les motivacions i principals conceptes, i en acabar professor i estudiants resolen conjuntament 2-3 problemes de consolidació. A laboratori, els estudiants resolen un cas relacionat amb el contingut.
    • Teoria: Format classe magistral + resolució grupal de problemes
    • Laboratori: Els estudiants treballen en un cas pràctic relacionat amb el contingut, que pot incloure tasques de disseny, implementació, avaluació. La feina pot ser individual o grupal.
    Objectius: 4 6 7
    Continguts:
    Teoria
    4h
    Problemes
    0h
    Laboratori
    4h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    8h

    Activitat sobre el contingut "Algorismes per a dades massives"

    A teoria, el professor presenta les motivacions i principals conceptes, i en acabar professor i estudiants resolen conjuntament 2-3 problemes de consolidació. A laboratori, els estudiants resolen un cas relacionat amb el contingut.
    • Teoria: Format classe magistral + resolució grupal de problemes
    • Laboratori: Els estudiants treballen en un cas pràctic relacionat amb el contingut, que pot incloure tasques de disseny, implementació, avaluació. La feina pot ser individual o grupal.
    Objectius: 5 6 7
    Continguts:
    Teoria
    8h
    Problemes
    0h
    Laboratori
    8h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    18h

    Integració. Construcció de sistemes reals. Implicacions en privacitat, seguretat i drets de les persones.

    A teoria, el professor presenta les motivacions i principals conceptes, i en acabar professor i estudiants resolen conjuntament 2-3 problemes de consolidació. A laboratori, els estudiants resolen un cas relacionat amb el contingut.
    • Teoria: Plantejament de diferents aspectes sobre el contingut per part del professor. Resolució conjunta dels alumnes d'alguns casos pràctics, i posada en comú de les conclusions.
    • Laboratori: Resolució de casos de disseny a partir d'una especificació difusa, incloent tria de tecnologies i la identificació de problemes de privacitat i seguretat.
    Objectius: 6 7
    Teoria
    4h
    Problemes
    0h
    Laboratori
    4h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    8h

    Examen parcial

    Examen a resoldre de forma presencial durant la setmana de parcials.
    Objectius: 1 2 3
    Setmana: 7
    Teoria
    0h
    Problemes
    0h
    Laboratori
    0h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    0h

    Examen final

    Resolució de l'examen final, un cop acabat el període de docència, en una aula i un temps determinat.
    Objectius: 1 2 3 4 5 7
    Setmana: 15 (Fora d'horari lectiu)
    Teoria
    0h
    Problemes
    0h
    Laboratori
    0h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    0h

    Metodologia docent

    Classes "de teoria" expositives per part del professor. Es proposaran un cert nombre d'exercicis a resoldre fora de classe per a la propera sessió.

    Classes "de teoria" dedicades a la resolució. Es comentaran en comú les solucions dels exercicis proposats a la/les sessions precedents. S'esperarà que els estudiants hagin intentat resoldre'ls.

    Classes "de laboratori": A partir d'un guió que rebran al principi de la sessió, els estudiants duran a terme alguna tasca amb ordinador per consolidar els conceptes vistos a les classes de "teoria". Típicament serà l'implementació i experimentació amb algun algorisme, o l'anàlisi d'algun conjunt de dades.

    Mètode d'avaluació

    P = nota d'un examen parcial
    F = nota d'un examen final fet a final de curs.
    L = nota dels informes a lliurar sobre les sessions de laboratori.

    La nota final es calcularà com 25% P + 50% F + 25% L.

    La nota de la competència transversal CT6 "aprenentatge autònom" es calcularà en base a un tema proposat durant el curs que els i les estudiants hauran d'estudiar pel seu compte. S'avaluarà si s'han assimilat els conceptes d'aquest tema a partir de preguntes als examens i/o a informació plasmada als informes de les pràctiques.

    Bibliografia

    Bàsic

    Capacitats prèvies

    Les donades per les assignatures dels Quadrimestres 1 a 4 del grau. L'assignatura és en bona part "comprensiva" de molt el fet anteriorment, i especialment conceptes de matemàtica (discreta, àlgebra, una mica de càlcul), probabilitat i estadística, algorísmia general (en particular, de grafs), aprenentatge automàtic i anàlisi de dades, bases de dades, i sistemes de computadors distribuïts i paral·lels. Els laboratoris es fan en el llenguatge de programació python.