Perfilado de sección

  • Partidos de fútbol a en función de los años

    IMPORTANTE: Esta versión intensiva de una semana del curso se dictó por única vez en 2021. Una versión extendida de todo el semestre se puede encontrar [aquí]

    Los grafos (o redes) son una estructura de datos presente en muchísimas áreas de conocimiento: redes de telecomunicaciones, sistemas de recomendación, redes de regulación genética, estructuturas de proteínas o movilidad urbana son solo algunos ejemplos. Básicamente, son entidades (nodos) que interactúan entre sí (aristas).

    Sobre estos datos existen muchos problemas interesantes de aprendizaje automático, donde básicamente se busca realizar predicciones o descubrir cierta estructura en los datos: detección de anomalías en una red inalámbrica, recomendación de libros a partir de clasificaciones anteriores y de otros usuarios, o clasificación del rol de ciertas proteínas en redes de interacción biológica. Sin embargo, está claro que técnicas de aprendizaje “tradicionales” (donde los datos son básicamente un vector o una matriz) que no toman en cuenta las relaciones entre las distintas entidades tendrán menor poder de generalización (y por lo tanto mucho peor desempeño) que aquellas que sí lo tomen en cuenta.

    El objetivo general del curso es que los estudiantes puedan afrontar un problema de aprendizaje automático donde los datos se encuentran en forma de grafos. Se brindarán los conceptos teóricos fundamentales y las herramientas prácticas necesarias para ello. Al finalizar el curso los estudiantes serán capaces de implementar y entender distintas técnicas del estado del arte en inferencia y predicción en grafos.

    Docente: Prof. Gonzalo Mateos (Universidad de Rochester, EEUU).
    Docente invitado: Fernando Gama (Universidad de California Berkeley, EEUU).
    Otros docentes: Marcelo Fiori y Federico La Rocca.
    Fechas: Lunes 1º de febrero al viernes 5 jueves 4 de febrero, y jueves 11 de febrero.
    Horario: 9hs a 12hs15 (lunes a jueves) y 14hs a 17hs15 el jueves 11/2.
    Lugar: remoto via zoom
    IMPORTANTE
    Inscripciones como curso de posgrado en: https://bedelias.udelar.edu.uy/
    Inscripciones como Educación Permanente en: https://www.fing.edu.uy/bedelia/inscripciones/actualizacion
    De todas formas quienes planean inscribirse deben matricularse en este EVA para recibir los anuncios y demás información.

    • Charla dictada por Federico La Rocca en el marco de las Tech Meetings de Tryolabs. Puede servir como introducción al curso.

    • Repaso de teoria de grafos, probabilidad e inferencia estadística

      Conceptos básicos de teoria de grafos e inferencia estadística  que usaremos recurrentemente durante el curso. Este material no sera presentado en clase. A modo de repaso recomendamos su lectura previa al comienzo del curso.  


    • Se cubren las nociones y definiciones básicas relacionadas con los grafos dirigidos y no dirigidos, el movimiento en un grafo y la conectividad, así como la aparición de una componente conexa gigante en muchas redes reales. A continuación, describimos familias de grafos clásicas que incluyen grafos completos, regulares, bipartitos, árboles y planares. Nos resultaran de gran utilidad las nociones de teoría algebraica de grafos, como la matriz adyacencia, la matriz de incidencia y el Laplaciano de un grafo, sus relaciones y propiedades espectrales. Terminamos con algoritmos y estructuras de datos para grafos y describimos breadth-first-search (BFS) para, por ejemplo, calcular distancias desde un vértice determinado.

    • Se repasan elementos básicos de inferencia estadística tales como los modelos paramétricos y no paramétricos, y los problemas fundamentales de estimación, predicción y test de hipótesis. Esbozaremos los conceptos de estimación puntual, intervalos de confianza y estadístico de prueba, ademas de estimadores clásicos como el método de los momentos, máxima verosimilitud, mínimos cuadrados y máximo a posteriori (MAP). Todos estos métodos se discutirán en el contexto de dos problemas clásicos: inferencia de la media de una distribución y regresión (mas predicción) con modelos lineales.

    • En esta clase introductoria comenzamos con una presentación de los aspectos administrativos del curso. Se introduce el concepto fundamental de red (así como su abstracción mediante un grafo) y desde una perspectiva histórica motivamos la “ciencia de datos de redes”. A través de ejemplos en múltiples disciplinas intentamos justificar la importancia e impacto del aprendizaje automático para datos en grafos. El resto de la clase se divide en cuatro “cuentos cortos” sobre problemas prototípicos del aprendizaje automático para datos en grafos.  Durante esta recorrida resaltaremos el nuevo paradigma necesario para atacar problemas de inferencia estadística con datos irregulares, es decir donde no hay un dominio Euclideo subyacente como en series temporales o imágenes. También delineamos los principales desafíos técnicos (metodológicos y computacionales) de esta área emergente donde las oportunidades son cada vez mayores, motivando el camino a seguir en el resto del curso.

    • Los laboratorios son actividades para que los estudiantes exploren distintas herramientas y bajen a tierra los conceptos manejados en clase. En cada laboratorio habrá algunas preguntas cuyas respuestas deberán ser entregadas en un único PDF. De todas formas, la idea es que éstas sean una excusa para que el estudiante explore las herramientas (y tenga algunos ejemplos de cómo usarlas), datasets y conceptos.

    • Un primer laboratorio para familiarizarse con algunas herramientas para procesar grafos.

    • Un laboratorio para repasar algunos modelos clásicos de grafos, y sobre cómo usar espacios latentes para detectar comunidades en grafos.

    • Un laboratorio sobre sistemas de recomendación para afianzar conceptos de GNNs.

    • Entregar un único pdf con las respuestas a los tres laboratorios. Hay tiempo hasta el domingo 28 de febrero a las 23:55.

    • El plazo para entregar la propuesta de trabajo final es el viernes 19/2 a las 23:55. 

    • Entregar un único pdf con el informe. Material extra, como código o demos en google colab, deben referirse desde este pdf. La fecha límite para la entrega del informe final es el lunes 5 de abril a las 23:55.

    • Sobre el trabajo final

      Se trata de un pequeño proyecto de investigación (unas 35 horas de dedicación según el programa) en el que pueda investigar y aplicar herramientas y algoritmos de análisis de grafos/redes de última generación a una aplicación de su preferencia.

      Debe seleccionar un tema específico relacionado con el aprendizaje automático en grafos/redes y realizar un survey relativamente profundo del tema. Esto incluye encontrar buenas fuentes en la literatura (artículos de investigación, libros de texto, diapositivas de presentación, etc.), posiblemente realizar algún análisis y/o simulaciones numéricas para experimentar con conjuntos de datos de red interesantes y proporcionar un resumen detallado de las ideas principales. El proyecto es un estudio en profundidad de un tema específico; no es solo un resumen de algunos trabajos de investigación. Si desea ser más ambicioso, también puede realizar investigación original sobre el tema seleccionado además del survey del tema (posiblemente resultando en una publicación de conferencia), pero esto no es obligatorio.

      Somos bastante flexibles con el tipo de estudio que se puede realizar. Típicamente estos pueden ser de los siguientes dos tipos (o una combinación de ambos):

      • Una evaluación experimental de algoritmos y modelos sobre datos de red interesantes, implementando su propio código y/o investigando software existente para el análisis de redes.
      • Un proyecto analítico que considera un modelo, un algoritmo o una propiedad de red y deriva un resultado teórico riguroso al respecto.

      Pero también se pueden realizar trabajos sobre implementaciones escalables / más eficientes de algoritmos para el procesamiento de datos de red a gran escala, o podría pensar en recopilar sus propios datos de la web, redes sociales, etc. para el análisis posterior.

      Para los estudiantes de posgrado, se sugiere que hable con su director de tesis (si tiene uno) sobre un posible tema relacionado con redes/grafos. Si no es estudiante de posgrado, no tiene DT o simplemente desea feedback, puede consultar con los docentes. Podemos coordinar una reunión para hacer sugerencias, lluvia de ideas, ayudar a refinar sus ideas iniciales o indicarle conjuntos de datos, código, documentos y otros recursos (además de los disponibles en la web del curso). En todo caso, es importante elegir un área de aplicación que esté relacionada con su investigación actual o futura.

      Se le recomienda que forme equipo con otro estudiante para trabajar en su proyecto (es decir, trabajar en parejas). Aún así, si lo desea, puede trabajar solo. 

      Evaluación

      Los trabajos se evaluarán en función de los siguientes criterios:

      • Calidad técnica. ¿Es el proyecto técnicamente sólido? ¿Son razonables las suposiciones de modelado y los algoritmos probados? ¿Las conclusiones sugieren un pensamiento crítico en profundidad sobre el tema elegido, posiblemente transmitiendo ideas novedosas sobre el problema y / o algoritmos elegidos?
      • Importancia. ¿Es este un problema interesante y oportuno para trabajar? ¿Es útil este trabajo y es probable que el área de investigación subyacente tenga impacto?
      • Claridad de presentación. ¿Con qué eficacia se transmiten los resultados de la investigación?

      Sobre la propuesta del trabajo

      La propuesta de proyecto debe resumir lo que planea hacer para su proyecto. El informe no debe exceder las 3 páginas y debe incluir:

      • Una descripción clara del problema que abordará.
      • Ideas preliminares sobre cómo planea abordarlo (modelos / algoritmos / técnicas).
      • Referencias bibliográficas básicas que consultará.
      • Si corresponde, qué herramientas de software necesitará para su trabajo (o si planea escribir su propio código, qué lenguaje usará).
      • Conjunto(s) de datos con los que trabajará.
      • Lo que espera producir como resultado de su trabajo y cómo juzgará el éxito del proyecto.
      • Cualquier otra cosa que crea que deberíamos saber para evaluar sus planes.


      Sobre el informe del trabajo final.

      El informe final debe proporcionar una descripción clara y detallada de lo que hizo, los resultados que obtuvo y lo que ha aprendido y concluido de su trabajo. El informe no debe exceder las 12 páginas y debe incluir:

      • Una introducción motivadora, revisión de la literatura de trabajos anteriores relevantes y una declaración clara del problema en forma finalizada.
      • Si recopiló sus propios datos para construir un grafo, describa ese proceso.
      • Para todos los que correspondan, proporcione derivaciones matemáticas, descripciones detalladas de modelos y algoritmos que haya utilizado, adaptado o desarrollado.
      • Descripción de sus experimentos, mostrando los resultados obtenidos y una discusión relevante basada en sus observaciones.
      • Conclusiones que indiquen las metas logradas y lo que aprendió, así como posibles extensiones o direcciones futuras.
      • Una lista de referencias relevantes.

      Se recomienda fuertemente usar LaTeX para ambas entregas. Puede usar cualquier template de paper con letra tamaño 10 con el que se sienta cómodo, overleaf ya trae varios pre-cargados (ver por ejemplo https://www.overleaf.com/gallery/tagged/ieee-official o https://www.overleaf.com/gallery/tagged/conference-paper). Para consejos de redacción, puede consultar la siguiente guía: https://iie.fing.edu.uy/personal/flarroca/teaching/recomendaciones-para-la-redaccion-de-una-tesis/.

    • Listamos a continuación algunos recursos que pueden ser de utilidad:

    • Bibliotecas y software

    • Uno de los paquetes de análisis de grafos más populares para Python. Muy fácil de usar y se integra con otras bibliotecas.

    • El equipo dirigido por Jure Leskovec comparte una biblioteca (en C++ y Python), además de varios dataset.

    • Una biblioteca bastante popular para aprendizaje en grafos.

    • Una biblioteca para implementar GNNs con el gran plus de que es agnóstico al framework (PyTorch o TensorFlow).

    • Una biblioteca basada en TensorFlow para implementar GNNs.

    • Una biblioteca libre y gratuita básicamente para GNNs.
    • Una biblioteca en python para signal processing en grafos.

    • Similar a networkx, pero más eficiente.

    • Otra biblioteca similar a networkx, pero disponible en varios lenguajes (C, python y R), y también más rápida. 

    • Otra biblioteca similar a networkx, pero también más rápida.

    • Un scikit específico para grafos.

    • El grupo de Alejandro Ribeiro comparte implementaciones basadas en Pytorch de casi todos sus trabajos en este repo.

    • Datasets

    • El equipo dirigido por Jure Leskovec comparte una biblioteca (en C++ y Python), además de varios dataset.

    • Un catálogo de grafos del grupo del creador de graph-tools.

    • Un catálogo de grafos, que además pueden visualizarse en línea.

    • Varios datasets de la Universidad de Harvard. No es específico de grafos, pero varios se pueden analizar desde esa perspectiva.

    • El grupo Grouplens de la Universidad de Minnesota tiene varios datasets disponibles.

    • Es un catálogo de datos abiertos a nivel gubernamental del Uruguay. Tiene varios datasets que pueden interpretarse como grafos. Por ejemplos, viajes de ómnibus (https://catalogodatos.gub.uy/dataset/intendencia-montevideo-viajes-realizados-en-los-omnibus-del-stm).

    • Varios datasets para hacer benchmark. Incluye métodos para cargarlos desde PyTorch Geometric o DGL, además de Leaderboards (con código asociado).

    • Kaggle ofrece varios datasets, códigos de ejemplo y turoriales. El link es para la sección de datasets.