Tagtäglich werden mehrere Zettabyte an Daten generiert. Diese können schon seit langen nicht mehr von Menschen verarbeitet und verstanden werden, sondern werden zum Großteil automatisiert verarbeitet. Neben der maschinellen Verarbeitung ist es dennoch weiterhin wichtig, dass Menschen mit den Daten interagieren können um diese besser zu verstehen und schlussendlich die maschinelle Verarbeitung zu überwachen.

Mit Hilfe von Datenzusammenfassungen (e.g. Data Summaries) lassen sich die wesentlichen Inhalte eines Datensatzes auf einige wichtige Repräsentanten herunterbrechen, sodass diese dann durch Menschen inspiziert und interpretiert werden können. Bei Data Summaries handelt es sich um ein geschickt gewähltes Sample aus einer Grundgesamtheit, die z.B. den Informationsgehalt maximiert. Theoretisch beruhen Data Summaries auf submodularen Funktionen, welche sich aufgrund ihrer mathematischen Eigenschaften ideal zur Berechnung von Summaries eignen. Formal wird hier eine submodulare Funktion gewählt die jedem Summary einen score zuweist, sodass diese Scorefunktion dann maximiert werden kann. Zur Maximierung gibt es eine Reihe von Verfahren die bereits implementiert sind [1].

Im Rahmen einer Bachelor/Masterarbeit können diverse Aspekte zu submodularen Funktionen und Data Summaries untersucht werden:

• Berechnen von bessere Zusammenfassungen: Im Kern der Daenzusammenfassung steh die Maximierung der Scorefunktion. In der Literatur finden sich bereits einige Vorschläge für passende Scorefunktionen, welche jedoch immer auf die vorliegende Aufgabe angepasst werden müssen:
  • Finden einer besseren Datenrepräsentation: Die Repräsentation der Daten ist oft entscheidend für die Performance eines Verfahrens. Hierzu lassen sich die Originaldaten in einen niedrigdimensionalen Raum z.B. durch die Nutzung von sog. Autoencodern einbetten um bessere Datenzusammenfassungen zu berechnen.
  • Design neuer submodularer Funktionen: Submodulare Funktionen müssen diverse math. Eigenschaften erfüllen, sind aber ansonsten frei wählbare Funktionen. Welche spezielle Funktion für welche Aufgabe besser geeignet ist, ist aktuell unklar bzw. noch Teil der wissenschaftlichen Diskussion.
• Vergleich von Data Summaries: Wenn technische Systeme über mehrere Wochen / Monate / Jahre in Betrieb sind, so kommt es üblicherweise zu einer leichten Veränderung in den Daten (eng. Concept Drift). Ein solcher Drift sollte sich auch in der Veränderung von periodisch selektierten Data Summaries finden lassen. Ziel ist hier der (automatische) Vergleich mehrerer Data Summaries zum Auffinden von Concept Drift in Daten.

Several zettabytes of data are generated every day. For a long time now, this data can no longer be processed and understood by humans, but is largely processed automatically. In addition to automatic processing, it is still important that humans can interact with the data to better understand it and ultimately monitor the information processing system.

With the help of data summaries the essential content of a data set can be broken down to a few important representatives, so that these can then be inspected and interpreted by humans. Data Summaries are a cleverly chosen sample from a population that maximizes e.g. the information content. Theoretically, data summaries are based on submodular functions, which are ideal for computing summaries due to their mathematical properties. Formally, a submodular function is a set function which assigns a score to each summary and this score function is then maximized. There are a number of methods available for maximization that have already been implemented [1].

In the context of a bachelor/master thesis, various aspects of submodular functions and data summaries can be investigated:

• Finding better summarizes: At the heart of summary selection is the maximization of a score function. Literature contains some examples of score functions for certain tasks, but they need to be adopted for each application at hand.
  • Change the data representation: One way to find better data summaries is to find a better representation of the data by embedding the original features into lower-dimensional embedding space, e.g. by using Deep Autoencoders.
  • Design of new submodular functions: A submodular function must confirm to certain mathematical properties, but can be fine-tuned for each application at hand. There might be function better suited for summary selection than others.
• Concept Drift detection with Data Summaries: If technical systems are in operation over several weeks / months / years, there is usually a slight change in the data (= Concept Drift). Such a drift should also be found in the change of periodically selected data summaries. Thus, data summaries can theoretically be used to automatically find and detect concept drift.

[1] https://github.com/sbuschjaeger/SubmodularStreamingMaximization/

Literature

• General Introduction:
  • "Submodular Function Maximization" by Krause and Golovin (https://viterbi-web.usc.edu/~shanghua/teaching/Fall2019-670/krause12survey.pdf)
• Design of Submodular Functions
  • "Extractive Summarization using Continuous Vector Space Models" by Kagebäck etal. 2014 (https://www.aclweb.org/anthology/W14-1504.pdf)
  • "Im2Text: Describing Images Using 1 MillionCaptioned Photographs" by Ordonez etal. 2011 (http://www.cs.virginia.edu/~vicente/files/generation_nips2011.pdf)
  • "A Class of Submodular Functions for Document Summarization" by Lin etal. 2011 (https://www.aclweb.org/anthology/P11-1052.pdf)
  • "Deep Submodular Functions" by Bilmes and Bai 2017 (https://arxiv.org/pdf/1701.08939.pdf)
• Concept Drift Detection
  • "A Survey on Concept Drift Adaptation" by Gama etal. 2017 (https://dl.acm.org/doi/pdf/10.1145/2523813?casa_token=riWYoPBQ-RsAAAAA:ilL65Oy-e4JWgI8BXRNCPd5Lfkk23HBAzL79J8i0g4-yG-OgyJwio1gyWorKToGanQxi_w52hhs)
  • "OLINDDA: A cluster-based approach for detecting novelty and concept drift in data streams" by Spinosa et al. 2007 (https://dl.acm.org/doi/pdf/10.1145/1244002.1244107?casa_token=lEk3nDgKfPwAAAAA:8dOADUpYvCj62cLmVj1NZjx28YnD1fSM7LIKvMxDubMpW8iVF469Cfplz_PnaXVwGeyIIHGSARc)