Algorithmic Data Science (WS 2019/2020)

Titel Algorithmic Data Science
Veranstalter Dr. Nils Kriege
Veranstaltungsart Proseminar mit Präsentationskurs (INF-BSc-110, Elemente 1 und 2)
Veranstaltungsnummer 040609
SWS 3
Max. Teilnehmer 16
Moodle lsf-ADS-19_2

Inhalt

Die Veranstaltung besteht aus einem Proseminar mit integriertem Präsentationskurs.

Proseminar

Als Folge der Digitalisierung sind Daten in zunehmend großer Menge verfügbar und ihre automatisierte Analyse gewinnt an Bedeutung. Die Daten können sich dabei je nach Anwendungsgebiet in ihrer Art stark unterscheiden. Beispielsweise können soziale Netzwerke, Moleküle sowie Straßen- und Rechnernetze durch Graphen repräsentieren werden, während sich Häufigkeitsverteilungen von Ereignissen durch Histogramme beschreiben lassen. Im Rahmen der Analyse treten die unterschiedlichsten Probleme auf. Die Analyse von Graphen beruht auf graphentheoretischen Konzepten wie Graphisomorphie und Graphenalgorithmen. Zur Bestimmung der Ähnlichkeit von Verteilungen kann die Wasserstein-Metrik herangezogen werden, deren Berechnung wiederum in einem engen Zusammenhang mit Transport- und Flussproblemen in Graphen steht. Die effiziente Berechnung von Maßen für den Vergleich von Ranglisten erinnert an klassische Sortierverfahren, Methoden des hierarchischen Clustering an die Berechnung minimaler Spannbäume in Graphen.

Im Rahmen des Proseminars möchten wir uns mit Algorithmen für ausgewählte Probleme befassen, die im Data-Mining und Maschinellen Lernen auftreten.

Präsentationskurs

Der Kurs führt in grundlegende Präsentationstechniken ein. Es werden unter anderem die folgenden Themen behandelt:

  • Verfassen wissenschaftlicher Ausarbeitungen
  • Einführung in die Kommunikationstheorie
  • Mündliche Präsentation wissenschaftlicher Inhalte
  • Foliengestaltung

Darüber hinaus werden grundlegende Funktionen des Textsatzsystems LaTeX für die Erstellung von Ausarbeitungen und Vortragsfolien behandelt.

Themen

Nr. Thema Teilnehmer Quellen
Zuordnungsprobleme
1 Theoretische Grundlagen: Heiratssatz, perfekte Matchings Jan Schülling 1, Abschnitt 2.1
2 Theoretische Grundlagen: Das Assignment Polytop 1, Abschnitt 2.2
3 Matchings in bipartitten Graphen: Grundlagen Jin Ke 1, Abschnitt 3.1 und 3.2
4 Algorithmus von Hopcroft und Karp Rand Serjawi 1, Abschnitt 3.3
5 Matchings in konvexen bipartiten Graphen Andreas Rüb 1, Abschnitt 3.5
6 Das lineare Assignment Problem: Die ungarische Methode Hendrik Zemke 1, Abschnitt 4.1 und 4.2 (ohne 4.2.3)
7 Die ungarische Methode mittels kürzester Wege Burak Özkan 1, Abschnitt 4.4
8 Das quadratische Assignment Problem Daniel Lensker 1, Abschnitt 7.1
Transportprobleme
9 Die Probleme von Monge und Kantorovich Fatima Taleb 2, Abschnitt 2
10 Algorithmen: LP und Flußformulierungen Peter Tisoczki 2, Abschnitt 3
Optimale Spannbäume
11 Single-linkage Clustering George Mamar 9
12 Algorithmen von Borůvka und Jarnik Carsten Kellner 10
Spektren von Graphen
13 Graph-Spektrum Josef Schneider 11, Abschnitt 1.1-1.7
14 Eigenwerte und Eigenvektoren Jonathan Liening 11, Abschnitt 3.1-3.6
15 Anwendungen von Eigenvektoren 11, Abschnitt 3.13
Ausgewählte Themen
16 PageRank Mohamad Nassar 3
17 Network Alignment: IsoRank and NSD Benjamin Biehler 4
18 Kendal's Tau und seine Berechnung Roman Leis 5, 6
19 Die Softassign und Softmax Methode Jonas Grobe 7
20 Optimale Schnitte für Baummetriken 8
21 Locality-Sensitive Hashing Sergius Becker 3
  • [1] R.E. Burkard, M. Dell'Amico, and S. Martello. Assignment Problems. SIAM, 2012.
  • [2] G. Peyré, M. Cuturi. Computational Optimal Transport. Foundations and Trends in Machine Learning 11(5-6): 355-607, 2019.
  • [3] J. Leskovec, A. Rajaraman, J.D. Ullman. Mining of Massive Datasets, 2014.
  • [4] G. Kollias, S. Mohammadi, and A. Grama. Network similarity decomposition (NSD): A fast and scalable approach to network alignment. IEEE Tranactions on Knowledge and Data Engineering, 24(12), 2012.
  • [5] H. Abdi. Kendall rank correlation. Encyclopedia of Measurement and Statistics. Thousand Oaks (CA): Sage, 2007.
  • [6] W. Knight. A Computer Method for Calculating Kendall's Tau with Ungrouped Data. Journal of the American Statistical Association. 61 (314): 436–439, 1966.
  • [7] S. Gold, A. Rangarajan. Softassign versus Softmax: Benchmarks in Combinatorial Optimization. NIPS: 626-632, 1995.
  • [8] M. Karpinski, A. Lingas, D. Sledneu. Optimal cuts and partitions in tree metrics in polynomial time. Inf. Process. Lett. 113(12): 447-451, 2013.
  • [9] J.C. Gower, G.J. Ross. Minimum spanning trees and single linkage cluster analysis. Journal of the Royal Statistical Society, Series C. 18 (1): 54–64, 1969.
  • [10] J. Nešetřil, H. Nešetřilová. The Origins of Minimal Spanning Tree Algorithms - Borůvka und Jarnik, Documenta Mathematica, 2012
  • [11] A.E. Brouwer, W.H. Haemers: Spectra of Graphs - Monograph, Springer, 2011

Ablauf

Diese Veranstaltung ist ein Proseminar für Studierende im Grundstudium. Sie umfasst 3SWS und beinhaltet einen Präsentationskurs. Die Themenverteilung erfolgt während der Vorbesprechung. Im weiteren Verlauf des Semesters haben die Teilnehmer Zeit, die Ausarbeitung zu schreiben und den Vortrag vorzubereiten. In dieser Zeit wird es regelmäßigen Treffen im Rahmen des Präsentationskurses geben und ggf. themenbezogene Einzelgespräche.

Die schriftliche Ausarbeitung soll 10-12 Seiten umfassen und mit LaTeX erstellt werden (Vorlage). Die Abgabe erfolgt per E-Mail als PDF. Es wird empfohlen, rechtzeitig vor der Abgabe der schriftlichen Ausarbeitung dem Betreuer ein kurzes Konzeptpapier vorzulegen, in dem der Inhalt und Aufbau der Ausarbeitung stichpunktartig erläutert wird. Denn eine Aufgabe der Teilnehmer/innen besteht auch darin, den zu präsentierenden Stoff aus der Literaturquelle sorgsam auszuwählen. Es geht nicht darum, den ganzen Inhalt zu präsentieren, sondern die interessanten Aspekte. Hierbei ist eine frühzeitige Rückmeldung oft hilfreich. Der Inhalt der Ausarbeitung stimmt im Allgemeinen mit dem Inhalt der späteren Präsentation überein.

Jede Ausarbeitung wird von zwei Teilnehmer/innen korrigiert. Dabei sollen insbesondere die im Präsentationskurs besprochenen Kriterien berücksichtigt werden. Die Teilnehmer/innen senden die korrigierte Versionen zu einem festgelegten Zeitpunkt an den Betreuer und den Verfasser. Nach einer gemeinsamen Diskussion, haben die Teilnehmer/innen die Gelegenheit, ihre Ausarbeitung noch einmal zu überarbeiteten und endgültig abzugeben.

Im Januar halten alle Teilnehmer/innen einen 5-minütigen Vortrag zur Vorstellung ihres Themas sowie dem geplanten Inhalt. Dieser dient dazu, die Umsetzung der im Präsentationskurs gelernten Techniken zu kontrollieren und häufige Fehler bei den Abschlussvorträgen zu vermeiden. Die dabei genutzten Folien könne als Grundlage für den Abschlussvortrag dienen und erweitert werden. Um die vorbereiteten Abschlussvorträge zu perfektionieren, treffen sich die Teilnehmer/innen ggf. in kleineren Gruppen um sich gegenseitig zu unterstützen. Der Betreuer steht für Fragen zur Verfügung.

Alle Teilnehmer halten kurz nach Ende der Vorlesungszeit einen 30-minütigen Vortrag über das festgelegte Thema im Rahmen eines Blockseminars. Im Anschluss folgt eine Diskussion über Thema und Vortrag. Es herrscht Anwesenheitspflicht bei allen Vorträgen. Bitte beachten Sie auch die Hinweise zur Foliengestaltung!

Mangelhafte Ausarbeitungen, Plagiate und 1:1-Übersetzungen sowie mangelhafte Vorträge führen zum Nicht-Bestehen des Proseminars. Auch nicht rechtzeitig abgegebene Ausarbeitungen können zum Nicht-Bestehen führen.

Termine

Termin Datum Zeit Ort
Vorbesprechung 08.10.2019 14:15 – 15:45 R202, OH14
Präsentationskurs 22.10.2019 14:15 – 17:45 R202, OH14
Abgabe eines Ausarbeitungskonzepts optional, nach Bedarf
Abgabe der Ausarbeitung 17.11.2019 23:59
Besprechung der Ausarbeitungen 26.11.2019 14:15 – 17:45 R202, OH14
Präsentationskurs 10.12.2019 14:15 – 17:45 R202, OH14
Präsentationskurs 17.12.2019 14:15 – 17:45 R202, OH14
Abgabe der Ausarbeitung (finale Version) 06.01.2020 23:59
Kurzvorträge zur Probe 07.01.2020 14:15 – 17:45 R202, OH14
Abgabe der Folien 22.01.2020 23:59
Besprechung der Folien 28.01.2020 14:15 – 17:45 R202, OH14
Vorträge 05.–07.02.2020 R202, OH14

Zeitplan

Donnerstag, 06.02.2020 Freitag, 07.02.2020
10:15 – 11:00 Zuordnungsprobleme:
Heiratssatz, perfekte Matchings

Jan Schülling
Eigenwerte und Eigenvektoren
Jonathan Liening
11:00 – 11:45 Zuordnungsprobleme:
Matchings in bipartitten Graphen

Jin Ke
PageRank
Mohamad Nassar
11:45 – 12:30 Das lineare Assignment Problem:
Die ungarische Methode

Hendrik Zemke
Network Alignment:
IsoRank and NSD

Benjamin Biehler
12:30 – 13:30 Mittagspause Mittagspause
13:30 – 14:15 Die ungarische Methode
mittels kürzester Wege

Burak Özkan
Die Softassign und Softmax Methode
Jonas Grobe
14:15 – 15:00 Algorithmen von Borůvka und Jarnik
Carsten Kellner
Locality-Sensitive Hashing
Sergius Becker
15:00 – 15:45 Kendal's Tau und seine Berechnung
Roman Leis
Abschlussrunde

Korrekturgruppen

Teilnehmer Arbeiten
Jan Schülling (3) Matchings in bipartitten Graphen: Grundlagen
(7) Die ungarische Methode mittels kürzester Wege
Hendrik Zemke (3) Matchings in bipartitten Graphen: Grundlagen
(7) Die ungarische Methode mittels kürzester Wege
Jin Ke (1) Theoretische Grundlagen: Heiratssatz, perfekte Matchings
(6) Das lineare Assignment Problem: Die ungarische Methode
Burak Özkan (1) Theoretische Grundlagen: Heiratssatz, perfekte Matchings
(6) Das lineare Assignment Problem: Die ungarische Methode
Benjamin Biehler (14) Eigenwerte und Eigenvektoren
(16) PageRank
Mohamad Nassar (14) Eigenwerte und Eigenvektoren
(17) Network Alignment: IsoRank and NSD
Jonathan Liening (16) PageRank
(17) Network Alignment: IsoRank and NSD
Carsten Kellner (18) Kendal's Tau und seine Berechnung
(19) Die Softassign und Softmax Methode
Sergius Becker (18) Kendal's Tau und seine Berechnung
(19) Die Softassign und Softmax Methode
Roman Leis (12) Algorithmen von Borůvka und Jarnik
(21) Locality-Sensitive Hashing
Jonas Grobe (12) Algorithmen von Borůvka und Jarnik
(21) Locality-Sensitive Hashing

Materialien

Materialien zu dieser Veranstaltung werden auf der zugehörigen Moodle-Seite angeboten.

 
Last modified: 2020-02-05 09:54 (external edit)
DokuWikiRSS-Feed