TY - THES A1 - Shekhar, Sumit T1 - Image and video processing based on intrinsic attributes N2 - Advancements in computer vision techniques driven by machine learning have facilitated robust and efficient estimation of attributes such as depth, optical flow, albedo, and shading. To encapsulate all such underlying properties associated with images and videos, we evolve the concept of intrinsic images towards intrinsic attributes. Further, rapid hardware growth in the form of high-quality smartphone cameras, readily available depth sensors, mobile GPUs, or dedicated neural processing units have made image and video processing pervasive. In this thesis, we explore the synergies between the above two advancements and propose novel image and video processing techniques and systems based on them. To begin with, we investigate intrinsic image decomposition approaches and analyze how they can be implemented on mobile devices. We propose an approach that considers not only diffuse reflection but also specular reflection; it allows us to decompose an image into specularity, albedo, and shading on a resource constrained system (e.g., smartphones or tablets) using the depth data provided by the built-in depth sensors. In addition, we explore how on-device depth data can further be used to add an immersive dimension to 2D photos, e.g., showcasing parallax effects via 3D photography. In this regard, we develop a novel system for interactive 3D photo generation and stylization on mobile devices. Further, we investigate how adaptive manipulation of baseline-albedo (i.e., chromaticity) can be used for efficient visual enhancement under low-lighting conditions. The proposed technique allows for interactive editing of enhancement settings while achieving improved quality and performance. We analyze the inherent optical flow and temporal noise as intrinsic properties of a video. We further propose two new techniques for applying the above intrinsic attributes for the purpose of consistent video filtering. To this end, we investigate how to remove temporal inconsistencies perceived as flickering artifacts. One of the techniques does not require costly optical flow estimation, while both provide interactive consistency control. Using intrinsic attributes for image and video processing enables new solutions for mobile devices – a pervasive visual computing device – and will facilitate novel applications for Augmented Reality (AR), 3D photography, and video stylization. The proposed low-light enhancement techniques can also improve the accuracy of high-level computer vision tasks (e.g., face detection) under low-light conditions. Finally, our approach for consistent video filtering can extend a wide range of image-based processing for videos. N2 - Fortschritte im Bereich der Computer-Vision-Techniken, die durch Maschinelles Lernen vorangetrieben werden, haben eine robuste und effiziente Schätzung von Attributen wie Tiefe, optischer Fluss, Albedo, und Schattierung ermöglicht. Um all diese zugrundeliegenden Eigenschaften von Bildern und Videos zu erfassen, entwickeln wir das Konzept der intrinsischen Bilder zu intrinsischen Attributen weiter. Darüber hinaus hat die rasante Entwicklung der Hardware in Form von hochwertigen Smartphone-Kameras, leicht verfügbaren Tiefensensoren, mobilen GPUs, oder speziellen neuronalen Verarbeitungseinheiten die Bild- und Videoverarbeitung allgegenwärtig gemacht. In dieser Arbeit erforschen wir die Synergien zwischen den beiden oben genannten Fortschritten und schlagen neue Bild- und Videoverarbeitungstechniken und -systeme vor, die auf ihnen basieren. Zunächst untersuchen wir intrinsische Bildzerlegungsansätze und analysieren, wie sie auf mobilen Geräten implementiert werden können. Wir schlagen einen Ansatz vor, der nicht nur die diffuse Reflexion, sondern auch die spiegelnde Reflexion berücksichtigt; er ermöglicht es uns, ein Bild auf einem ressourcenbeschränkten System (z. B. Smartphones oder Tablets) unter Verwendung der von den eingebauten Tiefensensoren bereitgestellten Tiefendaten in Spiegelung, Albedo und Schattierung zu zerlegen. Darüber hinaus erforschen wir, wie geräteinterne Tiefendaten genutzt werden können, um 2D-Fotos eine immersive Dimension hinzuzufügen, z. B. um Parallaxen-Effekte durch 3D-Fotografie darzustellen. In diesem Zusammenhang entwickeln wir ein neuartiges System zur interaktiven 3D-Fotoerstellung und -Stylisierung auf mobilen Geräten. Darüber hinaus untersuchen wir, wie eine adaptive Manipulation der Grundlinie-Albedo (d.h. der Farbintensität) für eine effiziente visuelle Verbesserung bei schlechten Lichtverhältnissen genutzt werden kann. Die vorgeschlagene Technik ermöglicht die interaktive Bearbeitung von Verbesserungseinstellungen bei verbesserter Qualität und Leistung. Wir analysieren den inhärenten optischen Fluss und die zeitliche Konsistenz als intrinsische Eigenschaften eines Videos. Darüber hinaus schlagen wir zwei neue Techniken zur Anwendung der oben genannten intrinsischen Attribute zum Zweck der konsistenten Videofilterung vor. Zu diesem Zweck untersuchen wir, wie zeitliche Inkonsistenzen, die als Flackerartefakte wahrgenommen werden, entfernt werden können. Eine der Techniken erfordert keine kostspielige optische Flussschätzung, während beide eine interaktive Konsistenzkontrolle bieten. Die Verwendung intrinsischer Attribute für die Bild- und Videoverarbeitung ermöglicht neue Lösungen für mobile Geräte - ein visuelles Computergerät, das aufgrund seiner weltweiten Verbreitung von großer Bedeutung ist - und wird neuartige Anwendungen für Augmented Reality (AR), 3D-Fotografie und Videostylisierung ermöglichen. Die vorgeschlagenen Low-Light-Enhancement-Techniken können auch die Genauigkeit von High-Level-Computer-Vision-Aufgaben (z. B. Objekt-Tracking) unter schlechten Lichtverhältnissen verbessern. Schließlich kann unser Ansatz zur konsistenten Videofilterung eine breite Palette von bildbasierten Verarbeitungen für Videos erweitern. KW - image processing KW - image-based rendering KW - non-photorealistic rendering KW - image stylization KW - computational photography KW - Bildverarbeitung KW - bildbasiertes Rendering KW - Non-photorealistic Rendering KW - Computational Photography Y1 - 2023 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus4-620049 ER - TY - THES A1 - Najafi, Pejman T1 - Leveraging data science & engineering for advanced security operations T1 - Der Einsatz von Data Science & Engineering für fortschrittliche Security Operations N2 - The Security Operations Center (SOC) represents a specialized unit responsible for managing security within enterprises. To aid in its responsibilities, the SOC relies heavily on a Security Information and Event Management (SIEM) system that functions as a centralized repository for all security-related data, providing a comprehensive view of the organization's security posture. Due to the ability to offer such insights, SIEMS are considered indispensable tools facilitating SOC functions, such as monitoring, threat detection, and incident response. Despite advancements in big data architectures and analytics, most SIEMs fall short of keeping pace. Architecturally, they function merely as log search engines, lacking the support for distributed large-scale analytics. Analytically, they rely on rule-based correlation, neglecting the adoption of more advanced data science and machine learning techniques. This thesis first proposes a blueprint for next-generation SIEM systems that emphasize distributed processing and multi-layered storage to enable data mining at a big data scale. Next, with the architectural support, it introduces two data mining approaches for advanced threat detection as part of SOC operations. First, a novel graph mining technique that formulates threat detection within the SIEM system as a large-scale graph mining and inference problem, built on the principles of guilt-by-association and exempt-by-reputation. The approach entails the construction of a Heterogeneous Information Network (HIN) that models shared characteristics and associations among entities extracted from SIEM-related events/logs. Thereon, a novel graph-based inference algorithm is used to infer a node's maliciousness score based on its associations with other entities in the HIN. Second, an innovative outlier detection technique that imitates a SOC analyst's reasoning process to find anomalies/outliers. The approach emphasizes explainability and simplicity, achieved by combining the output of simple context-aware univariate submodels that calculate an outlier score for each entry. Both approaches were tested in academic and real-world settings, demonstrating high performance when compared to other algorithms as well as practicality alongside a large enterprise's SIEM system. This thesis establishes the foundation for next-generation SIEM systems that can enhance today's SOCs and facilitate the transition from human-centric to data-driven security operations. N2 - In einem Security Operations Center (SOC) werden alle sicherheitsrelevanten Prozesse, Daten und Personen einer Organisation zusammengefasst. Das Herzstück des SOCs ist ein Security Information and Event Management (SIEM)-System, welches als zentraler Speicher aller sicherheitsrelevanten Daten fungiert und einen Überblick über die Sicherheitslage einer Organisation geben kann. SIEM-Systeme sind unverzichtbare Werkzeuge für viele SOC-Funktionen wie Monitoring, Threat Detection und Incident Response. Trotz der Fortschritte bei Big-Data-Architekturen und -Analysen können die meisten SIEMs nicht mithalten. Sie fungieren nur als Protokollsuchmaschine und unterstützen keine verteilte Data Mining und Machine Learning. In dieser Arbeit wird zunächst eine Blaupause für die nächste Generation von SIEM-Systemen vorgestellt, welche Daten verteilt, verarbeitet und in mehreren Schichten speichert, damit auch Data Mining im großen Stil zu ermöglichen. Zudem werden zwei Data Mining-Ansätze vorgeschlagen, mit denen auch anspruchsvolle Bedrohungen erkannt werden können. Der erste Ansatz ist eine neue Graph-Mining-Technik, bei der SIEM-Daten als Graph strukturiert werden und Reputationsinferenz mithilfe der Prinzipien guiltby-association (Kontaktschuld) und exempt-by-reputation (Reputationsbefreiung) implementiert wird. Der Ansatz nutzt ein heterogenes Informationsnetzwerk (HIN), welches gemeinsame Eigenschaften und Assoziationen zwischen Entitäten aus Event Logs verknüpft. Des Weiteren ermöglicht ein neuer Inferenzalgorithmus die Bestimmung der Schädlichkeit eines Kontos anhand seiner Verbindungen zu anderen Entitäten im HIN. Der zweite Ansatz ist eine innovative Methode zur Erkennung von Ausreißern, die den Entscheidungsprozess eines SOC-Analysten imitiert. Diese Methode ist besonders einfach und interpretierbar, da sie einzelne univariate Teilmodelle kombiniert, die sich jeweils auf eine kontextualisierte Eigenschaft einer Entität beziehen. Beide Ansätze wurden sowohl akademisch als auch in der Praxis getestet und haben im Vergleich mit anderen Methoden auch in großen Unternehmen eine hohe Qualität bewiesen. Diese Arbeit bildet die Grundlage für die nächste Generation von SIEM-Systemen, welche den Übergang von einer personalzentrischen zu einer datenzentrischen Perspektive auf SOCs ermöglichen. KW - cybersecurity KW - endpoint security KW - threat detection KW - intrusion detection KW - apt KW - advanced threats KW - advanced persistent threat KW - zero-day KW - security analytics KW - data-driven KW - data mining KW - data science KW - anomaly detection KW - outlier detection KW - graph mining KW - graph inference KW - machine learning KW - Advanced Persistent Threats KW - fortschrittliche Angriffe KW - Anomalieerkennung KW - APT KW - Cyber-Sicherheit KW - Data-Mining KW - Data-Science KW - datengetrieben KW - Endpunktsicherheit KW - Graphableitung KW - Graph-Mining KW - Einbruchserkennung KW - Machine-Learning KW - Ausreißererkennung KW - Sicherheitsanalyse KW - Bedrohungserkennung KW - 0-day Y1 - 2023 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus4-612257 ER - TY - THES A1 - Quinzan, Francesco T1 - Combinatorial problems and scalability in artificial intelligence N2 - Modern datasets often exhibit diverse, feature-rich, unstructured data, and they are massive in size. This is the case of social networks, human genome, and e-commerce databases. As Artificial Intelligence (AI) systems are increasingly used to detect pattern in data and predict future outcome, there are growing concerns on their ability to process large amounts of data. Motivated by these concerns, we study the problem of designing AI systems that are scalable to very large and heterogeneous data-sets. Many AI systems require to solve combinatorial optimization problems in their course of action. These optimization problems are typically NP-hard, and they may exhibit additional side constraints. However, the underlying objective functions often exhibit additional properties. These properties can be exploited to design suitable optimization algorithms. One of these properties is the well-studied notion of submodularity, which captures diminishing returns. Submodularity is often found in real-world applications. Furthermore, many relevant applications exhibit generalizations of this property. In this thesis, we propose new scalable optimization algorithms for combinatorial problems with diminishing returns. Specifically, we focus on three problems, the Maximum Entropy Sampling problem, Video Summarization, and Feature Selection. For each problem, we propose new algorithms that work at scale. These algorithms are based on a variety of techniques, such as forward step-wise selection and adaptive sampling. Our proposed algorithms yield strong approximation guarantees, and the perform well experimentally. We first study the Maximum Entropy Sampling problem. This problem consists of selecting a subset of random variables from a larger set, that maximize the entropy. By using diminishing return properties, we develop a simple forward step-wise selection optimization algorithm for this problem. Then, we study the problem of selecting a subset of frames, that represent a given video. Again, this problem corresponds to a submodular maximization problem. We provide a new adaptive sampling algorithm for this problem, suitable to handle the complex side constraints imposed by the application. We conclude by studying Feature Selection. In this case, the underlying objective functions generalize the notion of submodularity. We provide a new adaptive sequencing algorithm for this problem, based on the Orthogonal Matching Pursuit paradigm. Overall, we study practically relevant combinatorial problems, and we propose new algorithms to solve them. We demonstrate that these algorithms are suitable to handle massive datasets. However, our analysis is not problem-specific, and our results can be applied to other domains, if diminishing return properties hold. We hope that the flexibility of our framework inspires further research into scalability in AI. N2 - Moderne Datensätze bestehen oft aus vielfältigen, funktionsreichen und unstrukturierten Daten, die zudem sehr groß sind. Dies gilt insbesondere für soziale Netzwerke, das menschliche Genom und E-Commerce Datenbanken. Mit dem zunehmenden Einsatz von künstlicher Intelligenz (KI) um Muster in den Daten zu erkennen und künftige Ergebnisse vorherzusagen, steigen auch die Bedenken hinsichtlich ihrer Fähigkeit große Datenmengen zu verarbeiten. Aus diesem Grund untersuchen wir das Problem der Entwicklung von KI-Systemen, die auf große und heterogene Datensätze skalieren. Viele KI-Systeme müssen während ihres Einsatzes kombinatorische Optimierungsprobleme lösen. Diese Optimierungsprobleme sind in der Regel NP-schwer und können zusätzliche Nebeneinschränkungen aufwiesen. Die Zielfunktionen dieser Probleme weisen jedoch oft zusätzliche Eigenschaften auf. Diese Eigenschaften können genutzt werden, um geeignete Optimierungsalgorithmen zu entwickeln. Eine dieser Eigenschaften ist das wohluntersuchte Konzept der Submodularität, das das Konzept des abnehmende Erträge beschreibt. Submodularität findet sich in vielen realen Anwendungen. Darüber hinaus weisen viele relevante An- wendungen Verallgemeinerungen dieser Eigenschaft auf. In dieser Arbeit schlagen wir neue skalierbare Algorithmen für kombinatorische Probleme mit abnehmenden Erträgen vor. Wir konzentrieren uns hierbei insbesondere auf drei Prob- leme: dem Maximum-Entropie-Stichproben Problem, der Videozusammenfassung und der Feature Selection. Für jedes dieser Probleme schlagen wir neue Algorithmen vor, die gut skalieren. Diese Algorithmen basieren auf verschiedenen Techniken wie der schrittweisen Vorwärtsauswahl und dem adaptiven sampling. Die von uns vorgeschlagenen Algorithmen bieten sehr gute Annäherungsgarantien und zeigen auch experimentell gute Leistung. Zunächst untersuchen wir das Maximum-Entropy-Sampling Problem. Dieses Problem besteht darin, zufällige Variablen aus einer größeren Menge auszuwählen, welche die Entropie maximieren. Durch die Verwendung der Eigenschaften des abnehmenden Ertrags entwickeln wir einen einfachen forward step-wise selection Optimierungsalgorithmus für dieses Problem. Anschließend untersuchen wir das Problem der Auswahl einer Teilmenge von Bildern, die ein bestimmtes Video repräsentieren. Dieses Problem entspricht einem submodularen Maximierungsproblem. Hierfür stellen wir einen neuen adaptiven Sampling-Algorithmus für dieses Problem zur Verfügung, das auch komplexe Nebenbedingungen erfüllen kann, welche durch die Anwendung entstehen. Abschließend untersuchen wir die Feature Selection. In diesem Fall verallgemeinern die zugrundeliegenden Zielfunktionen die Idee der submodularität. Wir stellen einen neuen adaptiven Sequenzierungsalgorithmus für dieses Problem vor, der auf dem Orthogonal Matching Pursuit Paradigma basiert. Insgesamt untersuchen wir praktisch relevante kombinatorische Probleme und schlagen neue Algorithmen vor, um diese zu lösen. Wir zeigen, dass diese Algorithmen für die Verarbeitung großer Datensätze geeignet sind. Unsere Auswertung ist jedoch nicht problemspezifisch und unsere Ergebnisse lassen sich auch auf andere Bereiche anwenden, sofern die Eigenschaften des abnehmenden Ertrags gelten. Wir hoffen, dass die Flexibilität unseres Frameworks die weitere Forschung im Bereich der Skalierbarkeit im Bereich KI anregt. KW - artificial intelligence KW - scalability KW - optimization KW - Künstliche Intelligenz KW - Optimierung Y1 - 2023 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus4-611114 ER - TY - THES A1 - Tan, Jing T1 - Multi-Agent Reinforcement Learning for Interactive Decision-Making T1 - Multiagenten Verstärkendes Lernen für Interaktive Entscheidungsfindung N2 - Distributed decision-making studies the choices made among a group of interactive and self-interested agents. Specifically, this thesis is concerned with the optimal sequence of choices an agent makes as it tries to maximize its achievement on one or multiple objectives in the dynamic environment. The optimization of distributed decision-making is important in many real-life applications, e.g., resource allocation (of products, energy, bandwidth, computing power, etc.) and robotics (heterogeneous agent cooperation on games or tasks), in various fields such as vehicular network, Internet of Things, smart grid, etc. This thesis proposes three multi-agent reinforcement learning algorithms combined with game-theoretic tools to study strategic interaction between decision makers, using resource allocation in vehicular network as an example. Specifically, the thesis designs an interaction mechanism based on second-price auction, incentivizes the agents to maximize multiple short-term and long-term, individual and system objectives, and simulates a dynamic environment with realistic mobility data to evaluate algorithm performance and study agent behavior. Theoretical results show that the mechanism has Nash equilibria, is a maximization of social welfare and Pareto optimal allocation of resources in a stationary environment. Empirical results show that in the dynamic environment, our proposed learning algorithms outperform state-of-the-art algorithms in single and multi-objective optimization, and demonstrate very good generalization property in significantly different environments. Specifically, with the long-term multi-objective learning algorithm, we demonstrate that by considering the long-term impact of decisions, as well as by incentivizing the agents with a system fairness reward, the agents achieve better results in both individual and system objectives, even when their objectives are private, randomized, and changing over time. Moreover, the agents show competitive behavior to maximize individual payoff when resource is scarce, and cooperative behavior in achieving a system objective when resource is abundant; they also learn the rules of the game, without prior knowledge, to overcome disadvantages in initial parameters (e.g., a lower budget). To address practicality concerns, the thesis also provides several computational performance improvement methods, and tests the algorithm in a single-board computer. Results show the feasibility of online training and inference in milliseconds. There are many potential future topics following this work. 1) The interaction mechanism can be modified into a double-auction, eliminating the auctioneer, resembling a completely distributed, ad hoc network; 2) the objectives are assumed to be independent in this thesis, there may be a more realistic assumption regarding correlation between objectives, such as a hierarchy of objectives; 3) current work limits information-sharing between agents, the setup befits applications with privacy requirements or sparse signaling; by allowing more information-sharing between the agents, the algorithms can be modified for more cooperative scenarios such as robotics. N2 - Die Verteilte Entscheidungsfindung untersucht Entscheidungen innerhalb einer Gruppe von interaktiven und eigennützigen Agenten. Diese Arbeit befasst sich insbesondere mit der optimalen Folge von Entscheidungen eines Agenten, der das Erreichen eines oder mehrerer Ziele in einer dynamischen Umgebung zu maximieren versucht. Die Optimierung einer verteilten Entscheidungsfindung ist in vielen alltäglichen Anwendungen relevant, z.B. zur Allokation von Ressourcen (Produkte, Energie, Bandbreite, Rechenressourcen etc.) und in der Robotik (heterogene Agenten-Kooperation in Spielen oder Aufträgen) in diversen Feldern wie Fahrzeugkommunikation, Internet of Things, Smart Grid, usw. Diese Arbeit schlägt drei Multi-Agenten Reinforcement Learning Algorithmen kombiniert mit spieltheoretischen Ansätzen vor, um die strategische Interaktion zwischen Entscheidungsträgern zu untersuchen. Dies wird am Beispiel einer Ressourcenallokation in der Fahrzeug-zu-X-Kommunikation (vehicle-to-everything) gezeigt. Speziell wird in der Arbeit ein Interaktionsmechanismus entwickelt, der auf Basis einer Zweitpreisauktion den Agenten zur Maximierung mehrerer kurz- und langfristiger Ziele sowie individueller und Systemziele anregt. Dabei wird eine dynamische Umgebung mit realistischen Mobilitätsdaten simuliert, um die Leistungsfähigkeit des Algorithmus zu evaluieren und das Agentenverhalten zu untersuchen. Eine theoretische Analyse zeigt, dass bei diesem Mechanismus das Nash-Gleichgewicht sowie eine Maximierung von Wohlfahrt und Pareto-optimaler Ressourcenallokation in einer statischen Umgebung vorliegen. Empirische Untersuchungen ergeben, dass in einer dynamischen Umgebung der vorgeschlagene Lernalgorithmus den aktuellen Stand der Technik bei ein- und mehrdimensionaler Optimierung übertrifft, und dabei sehr gut auch auf stark abweichende Umgebungen generalisiert werden kann. Speziell mit dem langfristigen mehrdimensionalen Lernalgorithmus wird gezeigt, dass bei Berücksichtigung von langfristigen Auswirkungen von Entscheidungen, als auch durch einen Anreiz zur Systemgerechtigkeit, die Agenten in individuellen als auch Systemzielen bessere Ergebnisse liefern, und das auch, wenn ihre Ziele privat, zufällig und zeitveränderlich sind. Weiter zeigen die Agenten Wettbewerbsverhalten, um ihre eigenen Ziele zu maximieren, wenn die Ressourcen knapp sind, und kooperatives Verhalten, um Systemziele zu erreichen, wenn die Ressourcen ausreichend sind. Darüber hinaus lernen sie die Ziele des Spiels ohne vorheriges Wissen über dieses, um Startschwierigkeiten, wie z.B. ein niedrigeres Budget, zu überwinden. Für die praktische Umsetzung zeigt diese Arbeit auch mehrere Methoden auf, welche die Rechenleistung verbessern können, und testet den Algorithmus auf einem handelsüblichen Einplatinencomputer. Die Ergebnisse zeigen die Durchführbarkeit von inkrementellem Lernen und Inferenz innerhalb weniger Millisekunden auf. Ausgehend von den Ergebnissen dieser Arbeit könnten sich verschiedene Forschungsfragen anschließen: 1) Der Interaktionsmechanismus kann zu einer Doppelauktion verändert und dabei der Auktionator entfernt werden. Dies würde einem vollständig verteilten Ad-Hoc-Netzwerk entsprechen. 2) Die Ziele werden in dieser Arbeit als unabhängig betrachtet. Es könnte eine Korrelation zwischen mehreren Zielen angenommen werden, so wie eine Zielhierarchie. 3) Die aktuelle Arbeit begrenzt den Informationsaustausch zwischen Agenten. Diese Annahme passt zu Anwendungen mit Anforderungen an den Schutz der Privatsphäre oder bei spärlichen Signalen. Indem der Informationsaustausch erhöht wird, könnte der Algorithmus auf stärker kooperative Anwendungen wie z.B. in der Robotik erweitert werden. KW - V2X KW - distributed systems KW - reinforcement learning KW - game theory KW - auction KW - decision making KW - behavioral sciences KW - multi-objective KW - V2X KW - Verteilte Systeme KW - Spieltheorie KW - Auktion KW - Entscheidungsfindung KW - Verhaltensforschung KW - verstärkendes Lernen KW - Multiziel Y1 - 2023 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus4-607000 ER - TY - THES A1 - Santuber, Joaquin T1 - Designing for digital justice T1 - Designing for Digital Justice T1 - Diseñar para la justicia digital BT - an entanglement of people, law, and technologies in Chilean courts BT - eine Verflechtung von Menschen, Recht und Technologien in chilenischen Gerichten BT - una maraña de personas, leyes y tecnologías en los tribunales chilenos N2 - At the beginning of 2020, with COVID-19, courts of justice worldwide had to move online to continue providing judicial service. Digital technologies materialized the court practices in ways unthinkable shortly before the pandemic creating resonances with judicial and legal regulation, as well as frictions. A better understanding of the dynamics at play in the digitalization of courts is paramount for designing justice systems that serve their users better, ensure fair and timely dispute resolutions, and foster access to justice. Building on three major bodies of literature —e-justice, digitalization and organization studies, and design research— Designing for Digital Justice takes a nuanced approach to account for human and more-than-human agencies. Using a qualitative approach, I have studied in depth the digitalization of Chilean courts during the pandemic, specifically between April 2020 and September 2022. Leveraging a comprehensive source of primary and secondary data, I traced back the genealogy of the novel materializations of courts’ practices structured by the possibilities offered by digital technologies. In five (5) cases studies, I show in detail how the courts got to 1) work remotely, 2) host hearings via videoconference, 3) engage with users via social media (i.e., Facebook and Chat Messenger), 4) broadcast a show with judges answering questions from users via Facebook Live, and 5) record, stream, and upload judicial hearings to YouTube to fulfil the publicity requirement of criminal hearings. The digitalization of courts during the pandemic is characterized by a suspended normativity, which makes innovation possible yet presents risks. While digital technologies enabled the judiciary to provide services continuously, they also created the risk of displacing traditional judicial and legal regulation. Contributing to liminal innovation and digitalization research, Designing for Digital Justice theorizes four phases: 1) the pre-digitalization phase resulting in the development of regulation, 2) the hotspot of digitalization resulting in the extension of regulation, 3) the digital innovation redeveloping regulation (moving to a new, preliminary phase), and 4) the permanence of temporal practices displacing regulation. Contributing to design research Designing for Digital Justice provides new possibilities for innovation in the courts, focusing at different levels to better address tensions generated by digitalization. Fellow researchers will find in these pages a sound theoretical advancement at the intersection of digitalization and justice with novel methodological references. Practitioners will benefit from the actionable governance framework Designing for Digital Justice Model, which provides three fields of possibilities for action to design better justice systems. Only by taking into account digital, legal, and social factors can we design better systems that promote access to justice, the rule of law, and, ultimately social peace. N2 - Durch COVID-19 mussten zu Beginn des Jahres 2020 die Gerichte weltweit, um ihren Dienst fortzusetzen, Onlinekommunikation und digitale Technologien nutzen. Die digitalen Technologien haben die Gerichtspraktiken in einer Weise verändert, die kurz vor der Pandemie noch undenkbar war, was zu Resonanzen mit der Rechtsprechung und der gesetzlichen Regelung sowie zu Reibungen führte. Ein besseres Verständnis der Dynamik, die bei der Digitalisierung von Gerichten im Spiel ist, ist von entscheidender Bedeutung für die Gestaltung von Justizsystemen, die ihren Nutzern besser dienen, faire und zeitnahe Streitbeilegung gewährleisten und den Zugang zur Justiz und zur Rechtsstaatlichkeit fördern. Aufbauend auf den drei großen Themenkomplexen E-Justiz, Digitalisierung und Organisationen sowie Designforschung verfolgt „Designing for Digital Justice“ einen nuancierten Ansatz, um menschliche und nicht-menschliche Akteure zu berücksichtigen. Mit Hilfe eines qualitativen Forschungsansatzes habe ich die Digitalisierung der chilenischen Gerichte während der Pandemie, insbesondere im Zeitraum von April 2020 und September 2022, eingehend untersucht. Auf der Grundlage einer umfassenden Quelle von Primär- und Sekundärdaten habe ich die Genealogie der neuartigen Materialisierung von Gerichtspraktiken zurückverfolgt, die durch die Möglichkeiten der digitalen Technologien strukturiert wurden. In fünf (5) Fallstudien zeige ich im Detail, wie die Gerichte 1) aus der Ferne arbeiten, 2) Anhörungen per Videokonferenz abhalten, 3) mit Nutzern über soziale Medien (beispielsweise Facebook und Chat Messenger) in Kontakt treten, 4) eine Sendung mit Richtern, die Fragen von Nutzern beantworten, über Facebook Live ausstrahlen und 5) Gerichtsverhandlungen aufzeichnen, streamen und auf YouTube hochladen, um die Anforderungen an die Öffentlichkeit von Strafverhandlungen zu erfüllen. Hierbei zeigt sich, dass digitale Technologien der Justiz zwar eine kontinuierliche Bereitstellung von Dienstleistungen ermöglichten. Sie bergen aber auch die Gefahr, dass sie die traditionelle gerichtliche und rechtliche Regulierung verdrängen. Als Beitrag zum Forschungsstrom zu „Liminal Innovation“ und Digitalisierung theoretisiert „Designing for Digital Justice“ vier Phasen: 1) Vor-Digitalisierung, die zur Entwicklung von Regulierung führt, 2) der Hotspot der Digitalisierung, der zur Ausweitung der Regulierung führt, 3) digitale Innovation, die die Regulierung neu entwickelt (Übergang zu einer neuen, provisorischen Phase) und 4) die Permanenz der temporären Praktiken, die die Regulierung verdrängt. Als Beitrag zur Designforschung bietet „Designing for Digital Justice“ neue Möglichkeiten für die Gestaltung von Justizsystemen, indem es Spannungen und Interventionsebenen miteinander verbindet. Forscherkolleg*innen finden auf diesen Seiten eine fundierte theoretische Weiterentwicklung an der Schnittstelle von Digitalisierung und Gerechtigkeit sowie neue methodische Hinweise. Praktiker sollen von dem Handlungsrahmen „Designing for Digital Justice Model“ profitieren, der drei Handlungsfelder für die Gestaltung besserer Justizsysteme bietet. Nur wenn wir die digitalen, rechtlichen und sozialen Akteure berücksichtigen, können wir bessere Systeme entwerfen, die sich für den Zugang zur Justiz, die Rechtsstaatlichkeit und letztlich den sozialen Frieden einsetzen. N2 - A principios de 2020, con la COVID-19, los tribunales de justicia de todo el mundo tuvieron que ponerse en línea para continuar con el servicio. Las tecnologías digitales materializaron las prácticas de los tribunales de formas impensables poco antes de la pandemia, creando resonancias con la regulación judicial y legal, así como fricciones. Comprender mejor las dinámicas en juego en la digitalización de los tribunales es primordial para diseñar sistemas de justicia que sirvan mejor a sus usuarios, garanticen una resolución de conflictos justa y oportuna y fomenten el acceso a la justicia. Sobre la base de tres grandes temas en la literatura -justicia electrónica, digitalización y organizaciones, e investigación del diseño-, Designing for Digital Justice adopta un enfoque matizado para tener en cuenta los organismos humanos y más que humanos. Utilizando un enfoque cualitativo, he estudiado en profundidad la digitalización de los tribunales chilenos durante la pandemia, concretamente entre abril de 2020 y septiembre de 2022. Aprovechando una amplia fuente de datos primarios y secundarios, he rastreado la genealogía de las nuevas materializaciones de las prácticas de los tribunales estructuradas por las posibilidades que ofrecen las tecnologías digitales. En cinco (5) estudios de caso, muestro en detalle cómo los tribunales llegaron a 1) trabajar a distancia, 2) celebrar audiencias por videoconferencia, 3) relacionarse con los usuarios a través de las redes sociales (es decir, Facebook y Chat Messenger), 4) emitir un espectáculo con jueces que responden a las preguntas de los usuarios a través de Facebook Live, y 5) grabar, transmitir y subir las audiencias judiciales a YouTube para cumplir con el requisito de publicidad de las audiencias penales. La digitalización de los tribunales durante la pandemia se caracteriza por una normatividad suspendida, que posibilita la innovación, pero presenta riesgos. Si bien las tecnologías digitales permitieron al poder judicial prestar servicios de forma continua, también crearon el riesgo de desplazar la normativa judicial y legal tradicional. Contribuyendo a la teoría de la innovación liminar y digitalización, Designing for Digital Justice teoriza cuatro fases: 1) la fase de pre-digitalización que da lugar al desarrollo de la regulación, 2) el hotspot de digitalización que da lugar a la ampliación de la regulación, 3) la innovación liminal que vuelve a desarrollar la regulación (pasando a una nueva fase preliminar), y 4) la permanencia de prácticas temporales que desplaza la regulación. Contribuyendo a la investigación sobre el diseño, Designing for Digital Justice ofrece nuevas posibilidades de intervención para el diseño de la justicia, conectando las tensiones y los niveles para intervenir en ellos. Los colegas investigadores encontrarán en estas páginas un sólido avance teórico en la intersección de la digitalización y la justicia y novedosas referencias metodológicas. Los profesionales se beneficiarán del marco de gobernanza Designing for Digital Justice Model, que ofrece tres campos de posibilidades de actuación para diseñar mejores sistemas de justicia. Sólo teniendo en cuenta las agencias digitales, jurídicas y sociales podremos diseñar mejores sistemas que se comprometan con el acceso a la justicia, el Estado de Derecho y, en última instancia, la paz social. KW - digitalisation KW - courts of justice KW - COVID-19 KW - Chile KW - online courts KW - design KW - law KW - organization studies KW - innovation KW - COVID-19 KW - Chile KW - Gerichtsbarkeit KW - Design KW - Digitalisierung KW - Innovation KW - Recht KW - Online-Gerichte KW - Organisationsstudien KW - COVID-19 KW - Chile KW - tribunales de justicia KW - diseño KW - digitalización KW - innovación KW - Derecho KW - tribunales en línea KW - estudios de organización Y1 - 2023 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus4-604178 ER - TY - THES A1 - Sakizloglou, Lucas T1 - Evaluating temporal queries over history-aware architectural runtime models T1 - Ausführung temporaler Anfragen über geschichtsbewusste Architektur-Laufzeitmodelle N2 - In model-driven engineering, the adaptation of large software systems with dynamic structure is enabled by architectural runtime models. Such a model represents an abstract state of the system as a graph of interacting components. Every relevant change in the system is mirrored in the model and triggers an evaluation of model queries, which search the model for structural patterns that should be adapted. This thesis focuses on a type of runtime models where the expressiveness of the model and model queries is extended to capture past changes and their timing. These history-aware models and temporal queries enable more informed decision-making during adaptation, as they support the formulation of requirements on the evolution of the pattern that should be adapted. However, evaluating temporal queries during adaptation poses significant challenges. First, it implies the capability to specify and evaluate requirements on the structure, as well as the ordering and timing in which structural changes occur. Then, query answers have to reflect that the history-aware model represents the architecture of a system whose execution may be ongoing, and thus answers may depend on future changes. Finally, query evaluation needs to be adequately fast and memory-efficient despite the increasing size of the history---especially for models that are altered by numerous, rapid changes. The thesis presents a query language and a querying approach for the specification and evaluation of temporal queries. These contributions aim to cope with the challenges of evaluating temporal queries at runtime, a prerequisite for history-aware architectural monitoring and adaptation which has not been systematically treated by prior model-based solutions. The distinguishing features of our contributions are: the specification of queries based on a temporal logic which encodes structural patterns as graphs; the provision of formally precise query answers which account for timing constraints and ongoing executions; the incremental evaluation which avoids the re-computation of query answers after each change; and the option to discard history that is no longer relevant to queries. The query evaluation searches the model for occurrences of a pattern whose evolution satisfies a temporal logic formula. Therefore, besides model-driven engineering, another related research community is runtime verification. The approach differs from prior logic-based runtime verification solutions by supporting the representation and querying of structure via graphs and graph queries, respectively, which is more efficient for queries with complex patterns. We present a prototypical implementation of the approach and measure its speed and memory consumption in monitoring and adaptation scenarios from two application domains, with executions of an increasing size. We assess scalability by a comparison to the state-of-the-art from both related research communities. The implementation yields promising results, which pave the way for sophisticated history-aware self-adaptation solutions and indicate that the approach constitutes a highly effective technique for runtime monitoring on an architectural level. N2 - In der modellgetriebenen Entwicklung wird die Adaptation großer Softwaresysteme mit dynamischer Struktur durch Architektur-Laufzeitmodelle ermöglicht. Ein solches Modell stellt einen abstrakten Zustand des Systems als einen Graphen von interagierenden Komponenten dar. Jede relevante Änderung im System spiegelt sich im Modell wider und löst eine Ausführung von Modellanfragen aus, die das Modell nach zu adaptierenden Strukturmustern durchsuchen. Diese Arbeit konzentriert sich auf eine Art von Laufzeitmodellen, bei denen die Ausdruckskraft des Modells und der Modellanfragen erweitert wird, um vergangene Änderungen und deren Zeitpunkt zu erfassen. Diese geschichtsbewussten Modelle und temporalen Anfragen ermöglichen eine fundiertere Entscheidungsfindung während der Adaptation, da sie die Formulierung von Anforderungen an die Entwicklung des Musters, das adaptiert werden soll, unterstützen. Die Ausführung von temporalen Anfragen während der Adaptation stellt jedoch eine große Herausforderung dar. Zunächst müssen Anforderungen an die Struktur sowie an die Reihenfolge und den Zeitpunkt von Strukturänderungen spezifiziert und evaluiert werden. Weiterhin müssen die Antworten auf die Anfragen berücksichtigen, dass das geschichtsbewusste Modell die Architektur eines Systems darstellt, dessen Ausführung fortlaufend sein kann, sodass die Antworten von zukünftigen Änderungen abhängen können. Schließlich muss die Anfrageausführung trotz der zunehmenden Größe der Historie hinreichend schnell und speichereffizient sein---insbesondere bei Modellen, die durch zahlreiche, schnelle Änderungen verändert werden. In dieser Arbeit werden eine Sprache für die Spezifikation von temporalen Anfragen sowie eine Technik für deren Ausführung vorgestellt. Diese Beiträge zielen darauf ab, die Herausforderungen bei der Ausführung temporaler Anfragen zur Laufzeit zu bewältigen---eine Voraussetzung für ein geschichtsbewusstes Architekturmonitoring und geschichtsbewusste Architekturadaptation, die von früheren modellbasierten Lösungen nicht systematisch behandelt wurde. Die besonderen Merkmale unserer Beiträge sind: die Spezifikation von Anfragen auf der Basis einer temporalen Logik, die strukturelle Muster als Graphen kodiert; die Bereitstellung formal präziser Anfrageantworten, die temporale Einschränkungen und laufende Ausführungen berücksichtigen; die inkrementelle Ausführung, die die Neuberechnung von Abfrageantworten nach jeder Änderung vermeidet; und die Option, Historie zu verwerfen, die für Abfragen nicht mehr relevant ist. Bei der Anfrageausführung wird das Modell nach dem Auftreten eines Musters durchsucht, dessen Entwicklung eine temporallogische Formel erfüllt. Neben der modellgetriebenen Entwicklung ist daher die Laufzeitverifikation ein weiteres verwandtes Forschungsgebiet. Der Ansatz unterscheidet sich von bisherigen logikbasierten Lösungen zur Laufzeitverifikation, indem er die Darstellung und Abfrage von Strukturen über Graphen bzw. Graphanfragen unterstützt, was bei Anfragen mit komplexen Mustern effizienter ist. Wir stellen eine prototypische Implementierung des Ansatzes vor und messen seine Laufzeit und seinen Speicherverbrauch in Monitoring- und Adaptationsszenarien aus zwei Anwendungsdomänen mit Ausführungen von zunehmender Größe. Wir bewerten die Skalierbarkeit durch einen Vergleich mit dem Stand der Technik aus beiden verwandten Forschungsgebieten. Die Implementierung liefert vielversprechende Ergebnisse, die den Weg für anspruchsvolle geschichtsbewusste Selbstadaptationslösungen ebnen und darauf hindeuten, dass der Ansatz eine effektive Technik für das Laufzeitmonitoring auf Architekturebene darstellt. KW - architectural adaptation KW - history-aware runtime models KW - incremental graph query evaluation KW - model-driven software engineering KW - temporal graph queries KW - Architekturadaptation KW - geschichtsbewusste Laufzeit-Modelle KW - inkrementelle Ausführung von Graphanfragen KW - modellgetriebene Softwaretechnik KW - temporale Graphanfragen Y1 - 2023 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus4-604396 ER - TY - THES A1 - Lindinger, Jakob T1 - Variational inference for composite Gaussian process models T1 - Variationelle Inferenz für zusammengesetzte Gauß-Prozess Modelle N2 - Most machine learning methods provide only point estimates when being queried to predict on new data. This is problematic when the data is corrupted by noise, e.g. from imperfect measurements, or when the queried data point is very different to the data that the machine learning model has been trained with. Probabilistic modelling in machine learning naturally equips predictions with corresponding uncertainty estimates which allows a practitioner to incorporate information about measurement noise into the modelling process and to know when not to trust the predictions. A well-understood, flexible probabilistic framework is provided by Gaussian processes that are ideal as building blocks of probabilistic models. They lend themself naturally to the problem of regression, i.e., being given a set of inputs and corresponding observations and then predicting likely observations for new unseen inputs, and can also be adapted to many more machine learning tasks. However, exactly inferring the optimal parameters of such a Gaussian process model (in a computationally tractable manner) is only possible for regression tasks in small data regimes. Otherwise, approximate inference methods are needed, the most prominent of which is variational inference. In this dissertation we study models that are composed of Gaussian processes embedded in other models in order to make those more flexible and/or probabilistic. The first example are deep Gaussian processes which can be thought of as a small network of Gaussian processes and which can be employed for flexible regression. The second model class that we study are Gaussian process state-space models. These can be used for time-series modelling, i.e., the task of being given a stream of data ordered by time and then predicting future observations. For both model classes the state-of-the-art approaches offer a trade-off between expressive models and computational properties (e.g. speed or convergence properties) and mostly employ variational inference. Our goal is to improve inference in both models by first getting a deep understanding of the existing methods and then, based on this, to design better inference methods. We achieve this by either exploring the existing trade-offs or by providing general improvements applicable to multiple methods. We first provide an extensive background, introducing Gaussian processes and their sparse (approximate and efficient) variants. We continue with a description of the models under consideration in this thesis, deep Gaussian processes and Gaussian process state-space models, including detailed derivations and a theoretical comparison of existing methods. Then we start analysing deep Gaussian processes more closely: Trading off the properties (good optimisation versus expressivity) of state-of-the-art methods in this field, we propose a new variational inference based approach. We then demonstrate experimentally that our new algorithm leads to better calibrated uncertainty estimates than existing methods. Next, we turn our attention to Gaussian process state-space models, where we closely analyse the theoretical properties of existing methods.The understanding gained in this process leads us to propose a new inference scheme for general Gaussian process state-space models that incorporates effects on multiple time scales. This method is more efficient than previous approaches for long timeseries and outperforms its comparison partners on data sets in which effects on multiple time scales (fast and slowly varying dynamics) are present. Finally, we propose a new inference approach for Gaussian process state-space models that trades off the properties of state-of-the-art methods in this field. By combining variational inference with another approximate inference method, the Laplace approximation, we design an efficient algorithm that outperforms its comparison partners since it achieves better calibrated uncertainties. N2 - Bei Vorhersagen auf bisher ungesehenen Datenpunkten liefern die meisten maschinellen Lernmethoden lediglich Punktprognosen. Dies kann problematisch sein, wenn die Daten durch Rauschen verfälscht sind, z. B. durch unvollkommene Messungen, oder wenn der abgefragte Datenpunkt sich stark von den Daten unterscheidet, mit denen das maschinelle Lernmodell trainiert wurde. Mithilfe probabilistischer Modellierung (einem Teilgebiet des maschinellen Lernens) werden die Vorhersagen der Methoden auf natürliche Weise durch Unsicherheiten ergänzt. Dies erlaubt es, Informationen über Messunsicherheiten in den Modellierungsprozess mit einfließen zu lassen, sowie abzuschätzen, bei welchen Vorhersagen dem Modell vertraut werden kann. Grundlage vieler probabilistischer Modelle bilden Gaußprozesse, die gründlich erforscht und äußerst flexibel sind und daher häufig als Bausteine für größere Modelle dienen. Für Regressionsprobleme, was heißt, von einem Datensatz bestehend aus Eingangsgrößen und zugehörigen Messungen auf wahrscheinliche Messwerte für bisher ungesehene Eingangsgrößen zu schließen, sind Gaußprozesse hervorragend geeignet. Zusätzlich können sie an viele weitere Aufgabenstellungen des maschinellen Lernens angepasst werden. Die Bestimmung der optimalen Parameter eines solchen Gaußprozessmodells (in einer annehmbaren Zeit) ist jedoch nur für Regression auf kleinen Datensätzen möglich. In allen anderen Fällen muss auf approximative Inferenzmethoden zurückgegriffen werden, wobei variationelle Inferenz die bekannteste ist. In dieser Dissertation untersuchen wir Modelle, die Gaußprozesse eingebettet in andere Modelle enthalten, um Letztere flexibler und/oder probabilistisch zu machen. Das erste Beispiel hierbei sind tiefe Gaußprozesse, die man sich als kleines Netzwerk von Gaußprozessen vorstellen kann und die für flexible Regression eingesetzt werden können. Die zweite Modellklasse, die wir genauer analysieren ist die der Gaußprozess-Zustandsraummodelle. Diese können zur Zeitreihenmodellierung verwendet werden, das heißt, um zukünftige Datenpunkte auf Basis eines nach der Zeit geordneten Eingangsdatensatzes vorherzusagen. Für beide genannten Modellklassen bieten die modernsten Ansatze einen Kompromiss zwischen expressiven Modellen und wunschenswerten rechentechnischen Eigenschaften (z. B. Geschwindigkeit oder Konvergenzeigenschaften). Desweiteren wird für die meisten Methoden variationelle Inferenz verwendet. Unser Ziel ist es, die Inferenz für beide Modellklassen zu verbessern, indem wir zunächst ein tieferes Verständnis der bestehenden Ansätze erlangen und darauf aufbauend bessere Inferenzverfahren entwickeln. Indem wir die bestehenden Kompromisse der heutigen Methoden genauer untersuchen, oder dadurch, dass wir generelle Verbesserungen anbieten, die sich auf mehrere Modelle anwenden lassen, erreichen wir dieses Ziel. Wir beginnen die Thesis mit einer umfassender Einführung, die den notwendigen technischen Hintergrund zu Gaußprozessen sowie spärlichen (approximativen und effizienten) Gaußprozessen enthält. Anschließend werden die in dieser Thesis behandelten Modellklassen, tiefe Gaußprozesse und Gaußprozess-Zustandsraummodelle, eingeführt, einschließlich detaillierter Herleitungen und eines theoretischen Vergleichs existierender Methoden. Darauf aufbauend untersuchen wir zuerst tiefe Gaußprozesse genauer und entwickeln dann eine neue Inferenzmethode. Diese basiert darauf, die wünschenswerten Eigenschaften (gute Optimierungseigenschaften gegenüber Expressivität) der modernsten Ansätze gegeneinander abzuwägen. Anschließend zeigen wir experimentell, dass unser neuer Algorithmus zu besser kalibrierten Unsicherheitsabschätzungen als bei bestehenden Methoden führt. Als Nächstes wenden wir uns Gaußprozess-Zustandsraummodelle zu, wo wir zuerst die theoretischen Eigenschaften existierender Ansätze genau analysieren. Wir nutzen das dabei gewonnene Verständnis, um ein neues Inferenzverfahren für Gaußprozess-Zustandsraummodelle einzuführen, welches Effekte auf verschiedenen Zeitskalen berücksichtigt. Für lange Zeitreihen ist diese Methode effizienter als bisherige Ansätze. Darüber hinaus übertrifft sie ihre Vergleichspartner auf Datensätzen, bei denen Effekte auf mehreren Zeitskalen (sich schnell und langsam verändernde Signale) auftreten. Zuletzt schlagen wir ein weiteres neues Inferenzverfahren für Gaußprozess-Zustandsraummodelle vor, das die Eigenschaften der aktuellsten Methoden auf diesem Gebiet gegeneinander abwägt. Indem wir variationelle Inferenz mit einem weiteren approximativen Inferenzverfahren, der Laplace- Approximation, kombinieren, entwerfen wir einen effizienten Algorithmus der seine Vergleichspartner dadurch übertrifft, dass er besser kalibrierte Unsicherheitsvorhersagen erzielt. KW - probabilistic machine learning KW - Gaussian processes KW - variational inference KW - deep Gaussian processes KW - Gaussian process state-space models KW - Gauß-Prozess Zustandsraummodelle KW - Gauß-Prozesse KW - tiefe Gauß-Prozesse KW - probabilistisches maschinelles Lernen KW - variationelle Inferenz Y1 - 2023 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus4-604441 ER - TY - THES A1 - Afifi, Haitham T1 - Wireless In-Network Processing for Multimedia Applications T1 - Drahtlose In-Network-Verarbeitung für Multimedia-Anwendungen N2 - With the recent growth of sensors, cloud computing handles the data processing of many applications. Processing some of this data on the cloud raises, however, many concerns regarding, e.g., privacy, latency, or single points of failure. Alternatively, thanks to the development of embedded systems, smart wireless devices can share their computation capacity, creating a local wireless cloud for in-network processing. In this context, the processing of an application is divided into smaller jobs so that a device can run one or more jobs. The contribution of this thesis to this scenario is divided into three parts. In part one, I focus on wireless aspects, such as power control and interference management, for deciding which jobs to run on which node and how to route data between nodes. Hence, I formulate optimization problems and develop heuristic and meta-heuristic algorithms to allocate wireless and computation resources. Additionally, to deal with multiple applications competing for these resources, I develop a reinforcement learning (RL) admission controller to decide which application should be admitted. Next, I look into acoustic applications to improve wireless throughput by using microphone clock synchronization to synchronize wireless transmissions. In the second part, I jointly work with colleagues from the acoustic processing field to optimize both network and application (i.e., acoustic) qualities. My contribution focuses on the network part, where I study the relation between acoustic and network qualities when selecting a subset of microphones for collecting audio data or selecting a subset of optional jobs for processing these data; too many microphones or too many jobs can lessen quality by unnecessary delays. Hence, I develop RL solutions to select the subset of microphones under network constraints when the speaker is moving while still providing good acoustic quality. Furthermore, I show that autonomous vehicles carrying microphones improve the acoustic qualities of different applications. Accordingly, I develop RL solutions (single and multi-agent ones) for controlling these vehicles. In the third part, I close the gap between theory and practice. I describe the features of my open-source framework used as a proof of concept for wireless in-network processing. Next, I demonstrate how to run some algorithms developed by colleagues from acoustic processing using my framework. I also use the framework for studying in-network delays (wireless and processing) using different distributions of jobs and network topologies. N2 - Mit der steigenden Anzahl von Sensoren übernimmt Cloud Computing die Datenverarbeitung vieler Anwendungen. Dies wirft jedoch viele Bedenken auf, z. B. in Bezug auf Datenschutz, Latenzen oder Fehlerquellen. Alternativ und dank der Entwicklung eingebetteter Systeme können drahtlose intelligente Geräte für die lokale Verarbeitung verwendet werden, indem sie ihre Rechenkapazität gemeinsam nutzen und so eine lokale drahtlose Cloud für die netzinterne Verarbeitung schaffen. In diesem Zusammenhang wird eine Anwendung in kleinere Aufgaben unterteilt, so dass ein Gerät eine oder mehrere Aufgaben ausführen kann. Der Beitrag dieser Arbeit zu diesem Szenario gliedert sich in drei Teile. Im ersten Teil konzentriere ich mich auf drahtlose Aspekte wie Leistungssteuerung und Interferenzmanagement um zu entscheiden, welche Aufgaben auf welchem Knoten ausgeführt werden sollen und wie die Daten zwischen den Knoten weitergeleitet werden sollen. Daher formuliere ich Optimierungsprobleme und entwickle heuristische und metaheuristische Algorithmen zur Zuweisung von Ressourcen eines drahtlosen Netzwerks. Um mit mehreren Anwendungen, die um diese Ressourcen konkurrieren, umgehen zu können, entwickle ich außerdem einen Reinforcement Learning (RL) Admission Controller, um zu entscheiden, welche Anwendung zugelassen werden soll. Als Nächstes untersuche ich akustische Anwendungen zur Verbesserung des drahtlosen Durchsatzes, indem ich Mikrofon-Taktsynchronisation zur Synchronisierung drahtloser Übertragungen verwende. Im zweiten Teil arbeite ich mit Kollegen aus dem Bereich der Akustikverarbeitung zusammen, um sowohl die Netzwerk- als auch die Anwendungsqualitäten (d.h. die akustischen) zu optimieren. Mein Beitrag konzentriert sich auf den Netzwerkteil, wo ich die Beziehung zwischen akustischen und Netzwerkqualitäten bei der Auswahl einer Teilmenge von Mikrofonen für die Erfassung von Audiodaten oder der Auswahl einer Teilmenge von optionalen Aufgaben für die Verarbeitung dieser Daten untersuche; zu viele Mikrofone oder zu viele Aufgaben können die Qualität durch unnötige Verzögerungen verringern. Daher habe ich RL-Lösungen entwickelt, um die Teilmenge der Mikrofone unter Netzwerkbeschränkungen auszuwählen, wenn sich der Sprecher bewegt, und dennoch eine gute akustische Qualität gewährleistet. Außerdem zeige ich, dass autonome Fahrzeuge, die Mikrofone mit sich führen, die akustische Qualität verschiedener Anwendungen verbessern. Dementsprechend entwickle ich RL-Lösungen (Einzel- und Multi-Agenten-Lösungen) für die Steuerung dieser Fahrzeuge. Im dritten Teil schließe ich die Lücke zwischen Theorie und Praxis. Ich beschreibe die Eigenschaften meines Open-Source-Frameworks, das als Prototyp für die drahtlose netzinterne Verarbeitung verwendet wird. Anschließend zeige ich, wie einige Algorithmen, die von Kollegen aus der Akustikverarbeitung entwickelt wurden, mit meinem Framework ausgeführt werden können. Außerdem verwende ich das Framework für die Untersuchung von netzinternen Verzögerungen unter Verwendung verschiedener Aufgabenverteilungen und Netzwerktopologien. KW - wireless networks KW - reinforcement learning KW - network optimization KW - Netzoptimierung KW - bestärkendes Lernen KW - drahtloses Netzwerk Y1 - 2023 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus4-604371 ER - TY - THES A1 - Traifeh, Hanadi T1 - Design Thinking in the Arab world T1 - Design Thinking in der Arabischen Welt BT - perspectives, challenges and opportunities BT - Perspektiven, Herausforderungen und Potentiale N2 - Design Thinking is a human-centered approach to innovation that has become increasingly popular globally over the last decade. While the spread of Design Thinking is well understood and documented in the Western cultural contexts, particularly in Europe and the US due to the popularity of the Stanford-Potsdam Design Thinking education model, this is not the case when it comes to non-Western cultural contexts. This thesis fills a gap identified in the literature regarding how Design Thinking emerged, was perceived, adopted, and practiced in the Arab world. The culture in that part of the world differs from that of the Western context, which impacts the mindset of people and how they interact with Design Thinking tools and methods. A mixed-methods research approach was followed in which both quantitative and qualitative methods were employed. First, two methods were used in the quantitative phase: a social media analysis using Twitter as a source of data, and an online questionnaire. The results and analysis of the quantitative data informed the design of the qualitative phase in which two methods were employed: ten semi-structured interviews, and participant observation of seven Design Thinking training events. According to the analyzed data, the Arab world appears to have had an early, though relatively weak, and slow, adoption of Design Thinking since 2006. Increasing adoption, however, has been witnessed over the last decade, especially in Saudi Arabia, the United Arab Emirates and Egypt. The results also show that despite its limited spread, Design Thinking has been practiced the most in education, information technology and communication, administrative services, and the non-profit sectors. The way it is being practiced, though, is not fully aligned with how it is being practiced and taught in the US and Europe, as most people in the region do not necessarily believe in all mindset attributes introduced by the Stanford-Potsdam tradition. Practitioners in the Arab world also seem to shy away from the 'wild side' of Design Thinking in particular, and do not fully appreciate the connection between art-design, and science-engineering. This questions the role of the educational institutions in the region since -according to the findings- they appear to be leading the movement in promoting and developing Design Thinking in the Arab world. Nonetheless, it is notable that people seem to be aware of the positive impact of applying Design Thinking in the region, and its potential to bring meaningful transformation. However, they also seem to be concerned about the current cultural, social, political, and economic challenges that may challenge this transformation. Therefore, they call for more awareness and demand to create Arabic, culturally appropriate programs to respond to the local needs. On another note, the lack of Arabic content and local case studies on Design Thinking were identified by several interviewees and were also confirmed by the participant observation as major challenges that are slowing down the spread of Design Thinking or sometimes hampering capacity building in the region. Other challenges that were revealed by the study are: changing the mindset of people, the lack of dedicated Design Thinking spaces, and the need for clear instructions on how to apply Design Thinking methods and activities. The concept of time and how Arabs deal with it, gender management during trainings, and hierarchy and power dynamics among training participants are also among the identified challenges. Another key finding revealed by the study is the confirmation of التفكير التصميمي as the Arabic term to be most widely adopted in the region to refer to Design Thinking, since four other Arabic terms were found to be associated with Design Thinking. Based on the findings of the study, the thesis concludes by presenting a list of recommendations on how to overcome the mentioned challenges and what factors should be considered when designing and implementing culturally-customized Design Thinking training in the Arab region. N2 - Design Thinking ist ein nutzerzentrierter Innovationsansatz, der in den letzten zehn Jahren weltweit an Bekanntheit gewonnen hat. Während die Verbreitung von Design Thinking im westlichen Kulturkreis – insbesondere in Europa und den USA – aufgrund der Bedeutung des Stanford-Potsdam Design Thinking-Ausbildungsmodells gut verstanden und dokumentiert ist, ist dies nicht der Fall, wenn es sich um nicht-westliche Kulturkreise handelt. Diese Arbeit schließt eine Lücke in der Literatur darüber, wie Design Thinking in der arabischen Welt entstanden ist, wahrgenommen, angenommen und praktiziert wurde. Die vorhandenen kulturellen Unterschiede zwischen der westlichen und der arabischen Welt wirken sich auch auf die Denkweise der Menschen aus, unddarauf, wie sie mit Design Thinking-Tools und -Methoden umgehen. Es wurde ein ‚Mixed Methods‘-Forschungsansatz verfolgt, d.h. sowohl quantitative als auch qualitative Methoden wurden eingesetzt. In der quantitativen Phase kamen zunächst zwei Methoden zum Einsatz: eine Social-Media-Analyse mit Twitter als Datenquelle und ein Online-Fragebogen. Die Ergebnisse und die Analyse der quantitativen Daten bildeten die Grundlage für die Gestaltung der qualitativen Phase, in der zwei Methoden angewendet wurden: zehn halbstrukturierte Interviews und die teilnehmende Beobachtung von sieben Design Thinking-Trainings. Den analysierten Daten zufolge scheint es in der arabischen Welt seit 2006 eine frühe, wenn auch relativ schwache und langsame Einführung von Design Thinking gegeben zu haben. In den letzten zehn Jahren ist jedoch eine zunehmende Akzeptanz zu beobachten, insbesondere in Saudi-Arabien, den Vereinigten Arabischen Emiraten und Ägypten. Die Ergebnisse zeigen auch, dass Design Thinking trotz seiner begrenzten Verbreitung am häufigsten im Bildungswesen, in der Informationstechnologie und Kommunikation, in der Verwaltung und im Non-Profit-Sektor angewandt wird. Die Art und Weise, wie Design Thinking praktiziert wird, stimmt jedoch nicht vollständig mit der Art und Weise überein, wie es in den USA und Europa praktiziert und gelehrt wird, da die meisten Menschen in der Region nicht unbedingt an alle Denkattribute glauben, die im Stanford-Potsdam-Modell eingeführt wurden. Die Praktiker in der arabischen Welt scheinen auch vor der "wilden Seite" des Design Thinking zurückzuschrecken und die Verbindung zwischen Kunst und Design auf der einen sowie Wissenschaft und Technik auf der anderen Seite nicht vollumfänglich zu schätzen. Dies wirft die Frage nach der Rolle von Bildungseinrichtungen in der Region auf, da sie - den Ergebnissen zufolge - die Bewegung zur Förderung und Entwicklung von Design Thinking in der arabischen Welt anzuführen scheinen. Nichtsdestotrotz ist es bemerkenswert, dass sich die Menschen der positiven Auswirkungen der Anwendung von Design Thinking in der Region und seines Potenzials, sinnvolle Veränderungen zu bewirken, bewusst zu sein scheinen. Sie scheinen jedoch auch besorgt zu sein über die aktuellen kulturellen, sozialen, politischen und wirtschaftlichen Herausforderungen, die diese Transformation in Frage stellen könnten. Daher fordern sie eine stärkere Sensibilisierung und die Schaffung von arabischen, kulturell angemessenen Programmen, um auf die lokalen Bedürfnisse einzugehen. Auch das Fehlen arabischer Inhalte und lokaler Fallstudien zu Design Thinking wurde von mehreren Befragten genannt und durch die teilnehmende Beobachtung bestätigt, da dies die Verbreitung von Design Thinking verlangsamt oder den Aufbau von Kapazitäten in der Region behindert. Weitere Herausforderungen, die sich aus der Studie ergaben, sind: die Veränderung des Mindsets der Menschen, das Fehlen spezieller Design-Thinking-Räume und der Bedarf an klaren Anweisungen zur Anwendung von Design-Thinking-Methoden und -Aktivitäten. Das Konzept von Zeit und der Umgang der arabischen Welt damit, Gender-Management während der Schulungen sowie Hierarchie und Machtdynamik unter den Schulungsteilnehmern gehören ebenfalls zu den identifizierten Herausforderungen. Ein weiteres wichtiges Ergebnis der Studie ist die Bestätigung von التفكير التصميمي als dem in der Region am weitesten verbreiteten arabischen Begriff für Design Thinking, da vier weitere arabische Begriffe mit Design Thinking in Verbindung gebracht werden konnten. Basierend auf den Ergebnissen der Studie schließt die Arbeit mit einer Liste von Empfehlungen, wie die genannten Herausforderungen überwunden werden können und welche Faktoren bei der Entwicklung und Implementierung von kulturell angepassten Design Thinking-Trainings in der arabischen Welt berücksichtigt werden sollten. KW - Design Thinking KW - human-centered design KW - the Arab world KW - emergence KW - adoption KW - implementation KW - culture KW - Design Thinking KW - Annahme KW - Kultur KW - Entstehung KW - menschenzentriertes Design KW - Implementierung KW - die arabische Welt Y1 - 2023 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus4-598911 ER - TY - THES A1 - Hagedorn, Christopher T1 - Parallel execution of causal structure learning on graphics processing units T1 - Parallele Ausführung von kausalem Strukturlernen auf Grafikprozessoren N2 - Learning the causal structures from observational data is an omnipresent challenge in data science. The amount of observational data available to Causal Structure Learning (CSL) algorithms is increasing as data is collected at high frequency from many data sources nowadays. While processing more data generally yields higher accuracy in CSL, the concomitant increase in the runtime of CSL algorithms hinders their widespread adoption in practice. CSL is a parallelizable problem. Existing parallel CSL algorithms address execution on multi-core Central Processing Units (CPUs) with dozens of compute cores. However, modern computing systems are often heterogeneous and equipped with Graphics Processing Units (GPUs) to accelerate computations. Typically, these GPUs provide several thousand compute cores for massively parallel data processing. To shorten the runtime of CSL algorithms, we design efficient execution strategies that leverage the parallel processing power of GPUs. Particularly, we derive GPU-accelerated variants of a well-known constraint-based CSL method, the PC algorithm, as it allows choosing a statistical Conditional Independence test (CI test) appropriate to the observational data characteristics. Our two main contributions are: (1) to reflect differences in the CI tests, we design three GPU-based variants of the PC algorithm tailored to CI tests that handle data with the following characteristics. We develop one variant for data assuming the Gaussian distribution model, one for discrete data, and another for mixed discrete-continuous data and data with non-linear relationships. Each variant is optimized for the appropriate CI test leveraging GPU hardware properties, such as shared or thread-local memory. Our GPU-accelerated variants outperform state-of-the-art parallel CPU-based algorithms by factors of up to 93.4× for data assuming the Gaussian distribution model, up to 54.3× for discrete data, up to 240× for continuous data with non-linear relationships and up to 655× for mixed discrete-continuous data. However, the proposed GPU-based variants are limited to datasets that fit into a single GPU’s memory. (2) To overcome this shortcoming, we develop approaches to scale our GPU-based variants beyond a single GPU’s memory capacity. For example, we design an out-of-core GPU variant that employs explicit memory management to process arbitrary-sized datasets. Runtime measurements on a large gene expression dataset reveal that our out-of-core GPU variant is 364 times faster than a parallel CPU-based CSL algorithm. Overall, our proposed GPU-accelerated variants speed up CSL in numerous settings to foster CSL’s adoption in practice and research. N2 - Das Lernen von kausalen Strukturen aus Beobachtungsdatensätzen ist eine allgegenwärtige Herausforderung im Data Science-Bereich. Die für die Algorithmen des kausalen Strukturlernens (CSL) zur Verfügung stehende Menge von Beobachtungsdaten nimmt zu, da heutzutage mit hoher Frequenz Daten aus vielen Datenquellen gesammelt werden. Während die Verarbeitung von höheren Datenmengen im Allgemeinen zu einer höheren Genauigkeit bei CSL führt, hindert die damit einhergehende Erhöhung der Laufzeit von CSL-Algorithmen deren breite Anwendung in der Praxis. CSL ist ein parallelisierbares Problem. Bestehende parallele CSL-Algorithmen eignen sich für die Ausführung auf Mehrkern-Hauptprozessoren (CPUs) mit Dutzenden von Rechenkernen. Moderne Computersysteme sind jedoch häufig heterogen. Um notwendige Berechnungen zu beschleunigen, sind die Computersysteme typischerweise mit Grafikprozessoren (GPUs) ausgestattet, wobei diese GPUs mehrere tausend Rechenkerne für eine massive parallele Datenverarbeitung bereitstellen. Um die Laufzeit von Algorithmen für das kausale Strukturlernen zu verkürzen, entwickeln wir im Rahmen dieser Arbeit effiziente Ausführungsstrategien, die die parallele Verarbeitungsleistung von GPUs nutzen. Dabei entwerfen wir insbesondere GPU-beschleunigte Varianten des PC-Algorithmus, der eine bekannte Constraint-basierte CSL-Methode ist. Dieser Algorithmus ermöglicht die Auswahl eines – den Eigenschaften der Beobachtungsdaten entsprechenden – statistischen Tests auf bedingte Unabhängigkeit (CI-Test). Wir leisten in dieser Doktorarbeit zwei wissenschaftliche Hauptbeiträge: (1) Um den Unterschieden in den CI-Tests Rechnung zu tragen, entwickeln wir drei GPU-basierte, auf CI-Tests zugeschnittene Varianten des PC-Algorithmus. Dadurch können Daten mit den folgenden Merkmalen verarbeitet werden: eine Variante fokussiert sich auf Daten, die das Gaußsche Verteilungsmodell annehmen, eine weitere auf diskrete Daten und die dritte Variante setzt den Fokus auf gemischte diskret-kontinuierliche Daten sowie Daten mit nicht-linearen funktionalen Beziehungen. Jede Variante ist für den entsprechenden CI-Test optimiert und nutzt Eigenschaften der GPU-Hardware wie beispielsweise ”Shared Memory” oder ”Thread-local Memory” aus. Unsere GPU-beschleunigten Varianten übertreffen die modernsten parallelen CPU-basierten Algorithmen um Faktoren von bis zu 93,4x für Daten, die das Gaußsche Verteilungsmodell annehmen, bis zu 54,3x für diskrete Daten, bis zu 240x für kontinuierliche Daten mit nichtlinearen Beziehungen und bis zu 655x für gemischte diskret-kontinuierliche Daten. Die vorgeschlagenen GPU-basierten Varianten sind dabei jedoch auf Datensätze beschränkt, die in den Speicher einer einzelnen GPU passen. (2) Um diese Schwachstelle zu beseitigen, entwickeln wir Ansätze zur Skalierung unserer GPU-basierten Varianten über die Speicherkapazität einer einzelnen GPU hinaus. So entwerfen wir beispielsweise eine auf einer expliziten Speicherverwaltung aufbauenden Out-of-Core-Variante für eine einzelne GPU, um Datensätze beliebiger Größe zu verarbeiten. Laufzeitmessungen auf einem großen Genexpressionsdatensatz zeigen, dass unsere Out-of-Core GPU-Variante 364-mal schneller ist als ein paralleler CPU-basierter CSL-Algorithmus. Insgesamt beschleunigen unsere vorgestellten GPU-basierten Varianten das kausale Strukturlernen in zahlreichen Situationen und unterstützen dadurch die breite Anwendung des kausalen Strukturlernens in Praxis und Forschung. KW - causal structure learning KW - GPU acceleration KW - causal discovery KW - parallel processing KW - GPU-Beschleunigung KW - kausale Entdeckung KW - kausales Strukturlernen KW - parallele Verarbeitung Y1 - 2023 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus4-597582 ER - TY - THES A1 - Doskoč, Vanja T1 - Mapping restrictions in behaviourally correct learning N2 - In this thesis, we investigate language learning in the formalisation of Gold [Gol67]. Here, a learner, being successively presented all information of a target language, conjectures which language it believes to be shown. Once these hypotheses converge syntactically to a correct explanation of the target language, the learning is considered successful. Fittingly, this is termed explanatory learning. To model learning strategies, we impose restrictions on the hypotheses made, for example requiring the conjectures to follow a monotonic behaviour. This way, we can study the impact a certain restriction has on learning. Recently, the literature shifted towards map charting. Here, various seemingly unrelated restrictions are contrasted, unveiling interesting relations between them. The results are then depicted in maps. For explanatory learning, the literature already provides maps of common restrictions for various forms of data presentation. In the case of behaviourally correct learning, where the learners are required to converge semantically instead of syntactically, the same restrictions as in explanatory learning have been investigated. However, a similarly complete picture regarding their interaction has not been presented yet. In this thesis, we transfer the map charting approach to behaviourally correct learning. In particular, we complete the partial results from the literature for many well-studied restrictions and provide full maps for behaviourally correct learning with different types of data presentation. We also study properties of learners assessed important in the literature. We are interested whether learners are consistent, that is, whether their conjectures include the data they are built on. While learners cannot be assumed consistent in explanatory learning, the opposite is the case in behaviourally correct learning. Even further, it is known that learners following different restrictions may be assumed consistent. We contribute to the literature by showing that this is the case for all studied restrictions. We also investigate mathematically interesting properties of learners. In particular, we are interested in whether learning under a given restriction may be done with strongly Bc-locking learners. Such learners are of particular value as they allow to apply simulation arguments when, for example, comparing two learning paradigms to each other. The literature gives a rich ground on when learners may be assumed strongly Bc-locking, which we complete for all studied restrictions. N2 - In dieser Arbeit untersuchen wir das Sprachenlernen in der Formalisierung von Gold [Gol67]. Dabei stellt ein Lerner, dem nacheinander die volle Information einer Zielsprache präsentiert wird, Vermutungen darüber auf, welche Sprache er glaubt, präsentiert zu bekommen. Sobald diese Hypothesen syntaktisch zu einer korrekten Erklärung der Zielsprache konvergieren, wird das Lernen als erfolgreich angesehen. Dies wird passenderweise als erklärendes Lernen bezeichnet. Um Lernstrategien zu modellieren, werden den aufgestellten Hypothesen Einschränkungen auferlegt, zum Beispiel, dass die Vermutungen einem monotonen Verhalten folgen müssen. Auf diese Weise können wir untersuchen, welche Auswirkungen eine bestimmte Einschränkung auf das Lernen hat. In letzter Zeit hat sich die Literatur in Richtung Kartographie verlagert. Hier werden verschiedene, scheinbar nicht zusammenhängende Restriktionen einander gegenübergestellt, wodurch interessante Beziehungen zwischen ihnen aufgedeckt werden. Die Ergebnisse werden dann in so genannten Karten dargestellt. Für das erklärende Lernen gibt es in der Literatur bereits Karten geläufiger Einschränkungen für verschiedene Formen der Datenpräsentation. Im Falle des verhaltenskorrekten Lernens, bei dem die Lerner nicht syntaktisch, sondern semantisch konvergieren sollen, wurden die gleichen Einschränkungen wie beim erklärenden Lernen untersucht. Ein ähnlich vollständiges Bild hinsichtlich ihrer Interaktion wurde jedoch noch nicht präsentiert. In dieser Arbeit übertragen wir den Kartographie-Ansatz auf das verhaltenskorrekte Lernen. Insbesondere vervollständigen wir die Teilergebnisse aus der Literatur für viele gut untersuchte Restriktionen und liefern Karten für verhaltenskorrektes Lernen mit verschiedenen Arten der Datenpräsentation. Wir untersuchen auch Eigenschaften von Lernern, die in der Literatur als wichtig eingestuft werden. Uns interessiert, ob die Lerner konsistent sind, das heißt ob ihre Vermutungen die Daten einschließen, auf denen sie aufgebaut sind. Während man beim erklärenden Lernen nicht davon ausgehen kann, dass die Lerner konsistent sind, ist beim verhaltenskorrekten Lernen das Gegenteil der Fall. Es ist sogar bekannt, dass Lerner, die verschiedenen Einschränkungen folgen, als konsistent angenommen werden können. Wir tragen zur Literatur bei, indem wir zeigen, dass dies für alle untersuchten Restriktionen der Fall ist. Wir untersuchen auch mathematisch interessante Eigenschaften von Lernern. Insbesondere interessiert uns, ob das Lernen unter einer gegebenen Restriktion mit stark Bc-sperrenden Lernern durchgeführt werden kann. Solche Lerner sind von besonderem Wert, da sie es erlauben, Simulationsargumente anzuwenden, wenn man zum Beispiel zwei Lernparadigmen miteinander vergleicht. Die Literatur bietet eine reichhaltige Grundlage dafür, wann Lerner als stark Bc-sperrend angenommen werden können, die wir auf alle untersuchten Einschränkungen erweitern. KW - language learning in the limit KW - behaviourally correct learning KW - maps KW - consistent learning KW - strongly behaviourally correct locking KW - verhaltenskorrektes Lernen KW - konsistentes Lernen KW - Sprachlernen im Limes KW - Karten KW - stark verhaltenskorrekt sperrend Y1 - 2023 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus4-593110 ER - TY - THES A1 - Koßmann, Jan T1 - Unsupervised database optimization BT - efficient index selection & data dependency-driven query optimization N2 - The amount of data stored in databases and the complexity of database workloads are ever- increasing. Database management systems (DBMSs) offer many configuration options, such as index creation or unique constraints, which must be adapted to the specific instance to efficiently process large volumes of data. Currently, such database optimization is complicated, manual work performed by highly skilled database administrators (DBAs). In cloud scenarios, manual database optimization even becomes infeasible: it exceeds the abilities of the best DBAs due to the enormous number of deployed DBMS instances (some providers maintain millions of instances), missing domain knowledge resulting from data privacy requirements, and the complexity of the configuration tasks. Therefore, we investigate how to automate the configuration of DBMSs efficiently with the help of unsupervised database optimization. While there are numerous configuration options, in this thesis, we focus on automatic index selection and the use of data dependencies, such as functional dependencies, for query optimization. Both aspects have an extensive performance impact and complement each other by approaching unsupervised database optimization from different perspectives. Our contributions are as follows: (1) we survey automated state-of-the-art index selection algorithms regarding various criteria, e.g., their support for index interaction. We contribute an extensible platform for evaluating the performance of such algorithms with industry-standard datasets and workloads. The platform is well-received by the community and has led to follow-up research. With our platform, we derive the strengths and weaknesses of the investigated algorithms. We conclude that existing solutions often have scalability issues and cannot quickly determine (near-)optimal solutions for large problem instances. (2) To overcome these limitations, we present two new algorithms. Extend determines (near-)optimal solutions with an iterative heuristic. It identifies the best index configurations for the evaluated benchmarks. Its selection runtimes are up to 10 times lower compared with other near-optimal approaches. SWIRL is based on reinforcement learning and delivers solutions instantly. These solutions perform within 3 % of the optimal ones. Extend and SWIRL are available as open-source implementations. (3) Our index selection efforts are complemented by a mechanism that analyzes workloads to determine data dependencies for query optimization in an unsupervised fashion. We describe and classify 58 query optimization techniques based on functional, order, and inclusion dependencies as well as on unique column combinations. The unsupervised mechanism and three optimization techniques are implemented in our open-source research DBMS Hyrise. Our approach reduces the Join Order Benchmark’s runtime by 26 % and accelerates some TPC-DS queries by up to 58 times. Additionally, we have developed a cockpit for unsupervised database optimization that allows interactive experiments to build confidence in such automated techniques. In summary, our contributions improve the performance of DBMSs, support DBAs in their work, and enable them to contribute their time to other, less arduous tasks. N2 - Sowohl die Menge der in Datenbanken gespeicherten Daten als auch die Komplexität der Datenbank-Workloads steigen stetig an. Datenbankmanagementsysteme bieten viele Konfigurationsmöglichkeiten, zum Beispiel das Anlegen von Indizes oder die Definition von Unique Constraints. Diese Konfigurations-möglichkeiten müssen für die spezifische Datenbankinstanz angepasst werden, um effizient große Datenmengen verarbeiten zu können. Heutzutage wird die komplizierte Datenbankoptimierung manuell von hochqualifizierten Datenbankadministratoren vollzogen. In Cloud-Szenarien ist die manuelle Daten-bankoptimierung undenkbar: Die enorme Anzahl der verwalteten Systeme (einige Anbieter verwalten Millionen von Instanzen), das fehlende Domänenwissen durch Datenschutzanforderungen und die Kom-plexität der Konfigurationsaufgaben übersteigen die Fähigkeiten der besten Datenbankadministratoren. Aus diesen Gründen betrachten wir, wie die Konfiguration von Datenbanksystemen mit der Hilfe von Unsupervised Database Optimization effizient automatisiert werden kann. Während viele Konfigura-tionsmöglichkeiten existieren, konzentrieren wir uns auf die automatische Indexauswahl und die Nutzung von Datenabhängigkeiten, zum Beispiel Functional Dependencies, für die Anfrageoptimierung. Beide Aspekte haben großen Einfluss auf die Performanz und ergänzen sich gegenseitig, indem sie Unsupervised Database Optimization aus verschiedenen Perspektiven betrachten. Wir leisten folgende Beiträge: (1) Wir untersuchen dem Stand der Technik entsprechende automatisierte Indexauswahlalgorithmen hinsichtlich verschiedener Kriterien, zum Beispiel bezüglich ihrer Berücksichtigung von Indexinteraktionen. Wir stellen eine erweiterbare Plattform zur Leistungsevaluierung solcher Algorithmen mit Industriestandarddatensätzen und -Workloads zur Verfügung. Diese Plattform wird von der Forschungsgemeinschaft aktiv verwendet und hat bereits zu weiteren Forschungsarbeiten geführt. Mit unserer Plattform leiten wir die Stärken und Schwächen der untersuchten Algorithmen ab. Wir kommen zu dem Schluss, dass bestehende Lösung häufig Skalierungsschwierigkeiten haben und nicht in der Lage sind, schnell (nahezu) optimale Lösungen für große Problemfälle zu ermitteln. (2) Um diese Einschränkungen zu bewältigen, stellen wir zwei neue Algorithmen vor. Extend ermittelt (nahezu) optimale Lösungen mit einer iterativen Heuristik. Das Verfahren identifiziert die besten Indexkonfigurationen für die evaluierten Benchmarks und seine Laufzeit ist bis zu 10-mal geringer als die Laufzeit anderer nahezu optimaler Ansätze. SWIRL basiert auf Reinforcement Learning und ermittelt Lösungen ohne Wartezeit. Diese Lösungen weichen maximal 3 % von den optimalen Lösungen ab. Extend und SWIRL sind verfügbar als Open-Source-Implementierungen. (3) Ein Mechanismus, der mittels automatischer Workload-Analyse Datenabhängigkeiten für die Anfrageoptimierung bestimmt, ergänzt die vorigen Beiträge. Wir beschreiben und klassifizieren 58 Techniken, die auf Functional, Order und Inclusion Dependencies sowie Unique Column Combinations basieren. Der Analysemechanismus und drei Optimierungstechniken sind in unserem Open-Source-Forschungsdatenbanksystem Hyrise implementiert. Der Ansatz reduziert die Laufzeit des Join Order Benchmark um 26 % und erreicht eine bis zu 58-fache Beschleunigung einiger TPC-DS-Anfragen. Darüber hinaus haben wir ein Cockpit für Unsupervised Database Optimization entwickelt. Dieses Cockpit ermöglicht interaktive Experimente, um Vertrauen in automatisierte Techniken zur Datenbankoptimie-rung zu schaffen. Zusammenfassend lässt sich festhalten, dass unsere Beiträge die Performanz von Datenbanksystemen verbessern, Datenbankadministratoren in ihrer Arbeit unterstützen und ihnen ermöglichen, ihre Zeit anderen, weniger mühsamen, Aufgaben zu widmen. KW - Datenbank KW - Datenbanksysteme KW - database KW - DBMS KW - Hyrise KW - index selection KW - database systems KW - RL KW - reinforcement learning KW - query optimization KW - data dependencies KW - functional dependencies KW - order dependencies KW - unique column combinations KW - inclusion dependencies KW - funktionale Abhängigkeiten KW - Anfrageoptimierung KW - Query-Optimierung KW - extend KW - SWIRL KW - unsupervised KW - database optimization KW - self-driving KW - autonomous Y1 - 2023 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus4-589490 ER - TY - THES A1 - Podlesny, Nikolai Jannik T1 - Quasi-identifier discovery to prevent privacy violating inferences in large high dimensional datasets T1 - Erkennung von Quasi-Identifikatoren zum Schutz der Privatsphäre vor Rückschlüssen in hochdimensionalen Datensätzen N2 - Personal data privacy is considered to be a fundamental right. It forms a part of our highest ethical standards and is anchored in legislation and various best practices from the technical perspective. Yet, protecting against personal data exposure is a challenging problem from the perspective of generating privacy-preserving datasets to support machine learning and data mining operations. The issue is further compounded by the fact that devices such as consumer wearables and sensors track user behaviours on such a fine-grained level, thereby accelerating the formation of multi-attribute and large-scale high-dimensional datasets. In recent years, increasing news coverage regarding de-anonymisation incidents, including but not limited to the telecommunication, transportation, financial transaction, and healthcare sectors, have resulted in the exposure of sensitive private information. These incidents indicate that releasing privacy-preserving datasets requires serious consideration from the pre-processing perspective. A critical problem that appears in this regard is the time complexity issue in applying syntactic anonymisation methods, such as k-anonymity, l-diversity, or t-closeness to generating privacy-preserving data. Previous studies have shown that this problem is NP-hard. This thesis focuses on large high-dimensional datasets as an example of a special case of data that is characteristically challenging to anonymise using syntactic methods. In essence, large high-dimensional data contains a proportionately large number of attributes in proportion to the population of attribute values. Applying standard syntactic data anonymisation approaches to generating privacy-preserving data based on such methods results in high information-loss, thereby rendering the data useless for analytics operations or in low privacy due to inferences based on the data when information loss is minimised. We postulate that this problem can be resolved effectively by searching for and eliminating all the quasi-identifiers present in a high-dimensional dataset. Essentially, we quantify the privacy-preserving data sharing problem as the Find-QID problem. Further, we show that despite the complex nature of absolute privacy, the discovery of QID can be achieved reliably for large datasets. The risk of private data exposure through inferences can be circumvented, and both can be practicably achieved without the need for high-performance computers. For this purpose, we present, implement, and empirically assess both mathematical and engineering optimisation methods for a deterministic discovery of privacy-violating inferences. This includes a greedy search scheme by efficiently queuing QID candidates based on their tuple characteristics, projecting QIDs on Bayesian inferences, and countering Bayesian network’s state-space-explosion with an aggregation strategy taken from multigrid context and vectorised GPU acceleration. Part of this work showcases magnitudes of processing acceleration, particularly in high dimensions. We even achieve near real-time runtime for currently impractical applications. At the same time, we demonstrate how such contributions could be abused to de-anonymise Kristine A. and Cameron R. in a public Twitter dataset addressing the US Presidential Election 2020. Finally, this work contributes, implements, and evaluates an extended and generalised version of the novel syntactic anonymisation methodology, attribute compartmentation. Attribute compartmentation promises sanitised datasets without remaining quasi-identifiers while minimising information loss. To prove its functionality in the real world, we partner with digital health experts to conduct a medical use case study. As part of the experiments, we illustrate that attribute compartmentation is suitable for everyday use and, as a positive side effect, even circumvents a common domain issue of base rate neglect. N2 - Der personenbezogene Datenschutz gilt als Grundrecht in der Europäischen Union. Dieser Schutz ist nicht nur Teil unserer höchsten ethischen Standards, sondern auch in diversen Gesetzgebungen, verschiedenen bewährten Praktiken und den höchsten Gerichtsentscheidungen verankert. In der jüngeren Vergangenheit gab es zunehmend mehr Zwischenfälle, bei dem der Datenschutz von Individuellen nicht gewahrt werden konnte. Berichterstattung zu diesen Ereignissen schließen ein, sind aber nicht beschränkt auf die Sektoren der Telekommunikation, Transport, Finanztransaktionen und Gesundheitswesen. Nach diesen Vorfällen ist die Freigabe datenschutzrechtlicher Datensätze mit Problemen behaftet. Eines dieser Probleme ist die zeitliche Komplexitätsbeschränkung syntaktischer Anonymisierungsmethoden, durch die ihre Erforschung weitgehend zum Erliegen kam. Ansätze wie k-anonymity, l-diversity oder t-closeness haben sich in Ihrer Rechenzeit als sehr komplex und zeitaufwändig erwiesen. Auch Methoden der differenziellen Privatsphäre ("differential privacy") als probabilistische Anonymisierungstechnik weisen essentielle Einschränkungen für den Schutz von personenbezogenen Daten auf. Die Kombination von mehreren, unscheinbaren Datenpunkten können Quasi-Identifikatoren bilden, welche wiederum Angreifern in Kombination mit Hilfsdaten Schlussforderungen ermöglichen um private Informationen abzuleiten. Solche beobachteten Muster entfalten ihr volles Potenzial in dünn besiedelten, hochdimensionalen Daten, da ihre große Informationsvielfalt eine extreme Vielfalt von Schlussfolgerungen fördert. Die Suche nach und Beseitigung von Schlussfolgerung-Faktoren, die als Quasi-Identifikatoren (QID) fungieren, sind für das Problem des datenschutzschonenden Datenaustauschs von wesentlicher Bedeutung. Technologische Verbesserungen wie tragbare Fitnessgeräte für Verbraucher und Sensoren, die das Alltagsverhalten verfolgen, beschleunigen die Existenz von Datensätzen mit vielen Attributen und großen Datenmengen. Diese zusätzlichen Datenquellen bieten ein enormes Versprechen, erschweren aber gleichzeitig die Anonymisierungsbemühungen aufgrund der zunehmenden Komplexität. Als Teil dieser Arbeit wird das Finden von Quasi-Identifikatoren als "Find-QID"-Problem formalisiert, mathematische und technische Optimierungsmethoden vorgestellt, implementiert und experimentell verglichen. Ferner werden Charakteristika von Quasi-Identifikatoren erforscht, neue Entdeckungsmethoden vorgestellt und experimentell abgewogen und ebenfalls neue Anonymisierungsverfahren entworfen um die Existenz selbiger Quasi-Identifikatoren nachhaltig auszuschließen. In Summe wird aufgezeigt, wie diese Neuerungen sogar eine nahezu Echtzeit-Laufzeit für derzeit un-praktizierbare Anwendungen ermöglicht. Gleichzeitig wir aufgezeigt, wie selbige Beiträge zweckentfremdet werden können, um beispielhaft Kristine A. und Cameron R. in einem öffentlichen Datensatz zur US-Präsidentschaftswahl 2020 wiederzufinden. KW - data privacy KW - quasi-identifier discovery KW - de-anonymisation KW - mpmUCC KW - Datenschutz KW - Deanonymisierung KW - Erkennung von Quasi-Identifikatoren KW - mpmUCC Y1 - 2023 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus4-587843 ER - TY - THES A1 - Perscheid, Cindy T1 - Integrative biomarker detection using prior knowledge on gene expression data sets T1 - Integrative Biomarker-Erkennung auf Genexpressions-Daten mithilfe von biologischem Vorwissen N2 - Gene expression data is analyzed to identify biomarkers, e.g. relevant genes, which serve for diagnostic, predictive, or prognostic use. Traditional approaches for biomarker detection select distinctive features from the data based exclusively on the signals therein, facing multiple shortcomings in regards to overfitting, biomarker robustness, and actual biological relevance. Prior knowledge approaches are expected to address these issues by incorporating prior biological knowledge, e.g. on gene-disease associations, into the actual analysis. However, prior knowledge approaches are currently not widely applied in practice because they are often use-case specific and seldom applicable in a different scope. This leads to a lack of comparability of prior knowledge approaches, which in turn makes it currently impossible to assess their effectiveness in a broader context. Our work addresses the aforementioned issues with three contributions. Our first contribution provides formal definitions for both prior knowledge and the flexible integration thereof into the feature selection process. Central to these concepts is the automatic retrieval of prior knowledge from online knowledge bases, which allows for streamlining the retrieval process and agreeing on a uniform definition for prior knowledge. We subsequently describe novel and generalized prior knowledge approaches that are flexible regarding the used prior knowledge and applicable to varying use case domains. Our second contribution is the benchmarking platform Comprior. Comprior applies the aforementioned concepts in practice and allows for flexibly setting up comprehensive benchmarking studies for examining the performance of existing and novel prior knowledge approaches. It streamlines the retrieval of prior knowledge and allows for combining it with prior knowledge approaches. Comprior demonstrates the practical applicability of our concepts and further fosters the overall development and comparability of prior knowledge approaches. Our third contribution is a comprehensive case study on the effectiveness of prior knowledge approaches. For that, we used Comprior and tested a broad range of both traditional and prior knowledge approaches in combination with multiple knowledge bases on data sets from multiple disease domains. Ultimately, our case study constitutes a thorough assessment of a) the suitability of selected knowledge bases for integration, b) the impact of prior knowledge being applied at different integration levels, and c) the improvements in terms of classification performance, biological relevance, and overall robustness. In summary, our contributions demonstrate that generalized concepts for prior knowledge and a streamlined retrieval process improve the applicability of prior knowledge approaches. Results from our case study show that the integration of prior knowledge positively affects biomarker results, particularly regarding their robustness. Our findings provide the first in-depth insights on the effectiveness of prior knowledge approaches and build a valuable foundation for future research. N2 - Biomarker sind charakteristische biologische Merkmale mit diagnostischer oder prognostischer Aussagekraft. Auf der molekularen Ebene sind dies Gene mit einem krankheitsspezifischen Expressionsmuster, welche mittels der Analyse von Genexpressionsdaten identifiziert werden. Traditionelle Ansätze für diese Art von Biomarker Detection wählen Gene als Biomarker ausschließlich anhand der vorhandenen Signale im Datensatz aus. Diese Vorgehensweise zeigt jedoch Schwächen insbesondere in Bezug auf die Robustheit und tatsächliche biologische Relevanz der identifizierten Biomarker. Verschiedene Forschungsarbeiten legen nahe, dass die Berücksichtigung des biologischen Kontexts während des Selektionsprozesses diese Schwächen ausgleichen kann. Sogenannte wissensbasierte Ansätze für Biomarker Detection beziehen vorhandenes biologisches Wissen, beispielsweise über Zusammenhänge zwischen bestimmten Genen und Krankheiten, direkt in die Analyse mit ein. Die Anwendung solcher Verfahren ist in der Praxis jedoch derzeit nicht weit verbreitet, da existierende Methoden oft spezifisch für einen bestimmten Anwendungsfall entwickelt wurden und sich nur mit großem Aufwand auf andere Anwendungsgebiete übertragen lassen. Dadurch sind Vergleiche untereinander kaum möglich, was es wiederum nicht erlaubt die Effektivität von wissensbasierten Methoden in einem breiteren Kontext zu untersuchen. Die vorliegende Arbeit befasst sich mit den vorgenannten Herausforderungen für wissensbasierte Ansätze. In einem ersten Schritt legen wir formale und einheitliche Definitionen für vorhandenes biologisches Wissen sowie ihre flexible Integration in den Biomarker-Auswahlprozess fest. Der Kerngedanke unseres Ansatzes ist die automatisierte Beschaffung von biologischem Wissen aus im Internet frei verfügbaren Wissens-Datenbanken. Dies erlaubt eine Vereinfachung der Kuratierung sowie die Festlegung einer einheitlichen Definition für biologisches Wissen. Darauf aufbauend beschreiben wir generalisierte wissensbasierte Verfahren, welche flexibel auf verschiedene Anwendungsfalle anwendbar sind. In einem zweiten Schritt haben wir die Benchmarking-Plattform Comprior entwickelt, welche unsere theoretischen Konzepte in einer praktischen Anwendung realisiert. Comprior ermöglicht die schnelle Umsetzung von umfangreichen Experimenten für den Vergleich von wissensbasierten Ansätzen. Comprior übernimmt die Beschaffung von biologischem Wissen und ermöglicht dessen beliebige Kombination mit wissensbasierten Ansätzen. Comprior demonstriert damit die praktische Umsetzbarkeit unserer theoretischen Konzepte und unterstützt zudem die technische Realisierung und Vergleichbarkeit wissensbasierter Ansätze. In einem dritten Schritt untersuchen wir die Effektivität wissensbasierter Ansätze im Rahmen einer umfangreichen Fallstudie. Mithilfe von Comprior vergleichen wir die Ergebnisse traditioneller und wissensbasierter Ansätze im Kontext verschiedener Krankheiten, wobei wir für wissensbasierte Ansätze auch verschiedene Wissens-Datenbanken verwenden. Unsere Fallstudie untersucht damit a) die Eignung von ausgewählten Wissens-Datenbanken für deren Einsatz bei wissensbasierten Ansätzen, b) den Einfluss verschiedener Integrationskonzepte für biologisches Wissen auf den Biomarker-Auswahlprozess, und c) den Grad der Verbesserung in Bezug auf die Klassifikationsleistung, biologische Relevanz und allgemeine Robustheit der selektierten Biomarker. Zusammenfassend demonstriert unsere Arbeit, dass generalisierte Konzepte für biologisches Wissen und dessen vereinfachte Kuration die praktische Anwendbarkeit von wissensbasierten Ansätzen erleichtern. Die Ergebnisse unserer Fallstudie zeigen, dass die Integration von vorhandenem biologischen Wissen einen positiven Einfluss auf die selektierten Biomarker hat, insbesondere in Bezug auf ihre biologische Relevanz. Diese erstmals umfassenderen Erkenntnisse zur Effektivität von wissensbasierten Ansätzen bilden eine wertvolle Grundlage für zukünftige Forschungsarbeiten. KW - gene expression KW - biomarker detection KW - prior knowledge KW - feature selection KW - Biomarker-Erkennung KW - Merkmalsauswahl KW - Gen-Expression KW - biologisches Vorwissen Y1 - 2023 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus4-582418 ER - TY - THES A1 - Bano, Dorina T1 - Discovering data models from event logs T1 - Entdecken von Datenmodellen aus Ereignisprotokollen N2 - In the last two decades, process mining has developed from a niche discipline to a significant research area with considerable impact on academia and industry. Process mining enables organisations to identify the running business processes from historical execution data. The first requirement of any process mining technique is an event log, an artifact that represents concrete business process executions in the form of sequence of events. These logs can be extracted from the organization's information systems and are used by process experts to retrieve deep insights from the organization's running processes. Considering the events pertaining to such logs, the process models can be automatically discovered and enhanced or annotated with performance-related information. Besides behavioral information, event logs contain domain specific data, albeit implicitly. However, such data are usually overlooked and, thus, not utilized to their full potential. Within the process mining area, we address in this thesis the research gap of discovering, from event logs, the contextual information that cannot be captured by applying existing process mining techniques. Within this research gap, we identify four key problems and tackle them by looking at an event log from different angles. First, we address the problem of deriving an event log in the absence of a proper database access and domain knowledge. The second problem is related to the under-utilization of the implicit domain knowledge present in an event log that can increase the understandability of the discovered process model. Next, there is a lack of a holistic representation of the historical data manipulation at the process model level of abstraction. Last but not least, each process model presumes to be independent of other process models when discovered from an event log, thus, ignoring possible data dependencies between processes within an organization. For each of the problems mentioned above, this thesis proposes a dedicated method. The first method provides a solution to extract an event log only from the transactions performed on the database that are stored in the form of redo logs. The second method deals with discovering the underlying data model that is implicitly embedded in the event log, thus, complementing the discovered process model with important domain knowledge information. The third method captures, on the process model level, how the data affects the running process instances. Lastly, the fourth method is about the discovery of the relations between business processes (i.e., how they exchange data) from a set of event logs and explicitly representing such complex interdependencies in a business process architecture. All the methods introduced in this thesis are implemented as a prototype and their feasibility is proven by being applied on real-life event logs. N2 - In den letzten zwei Jahrzehnten hat sich Process Mining von einer Nischendisziplin zu einem bedeutenden Forschungsgebiet mit erheblichen Auswirkungen auf Wissenschaft und Industrie entwickelt. Process Mining ermöglicht es Unternehmen, die laufenden Geschäftsprozesse anhand historischer Ausführungsdaten zu identifizieren. Die erste Voraussetzung für jede Process-Mining-Technik ist ein Ereignisprotokoll (Event Log), ein Artefakt, das konkrete Geschäftsprozessausführungen in Form einer Abfolge von Ereignissen darstellt. Diese Protokolle (Logs) können aus den Informationssystemen der Unternehmen extrahiert werden und ermöglichen es Prozessexperten, tiefe Einblicke in die laufenden Unternehmensprozesse zu gewinnen. Unter Berücksichtigung der Abfolge der Ereignisse in diesen Protokollen (Logs) können Prozessmodelle automatisch entdeckt und mit leistungsbezogenen Informationen erweitert werden. Neben verhaltensbezogenen Informationen enthalten Ereignisprotokolle (Event Logs) auch domänenspezifische Daten, wenn auch nur implizit. Solche Daten werden jedoch in der Regel nicht in vollem Umfang genutzt. Diese Arbeit befasst sich im Bereich Process Mining mit der Forschungslücke der Extraktion von Kontextinformationen aus Ereignisprotokollen (Event Logs), die von bestehenden Process Mining-Techniken nicht erfasst werden. Innerhalb dieser Forschungslücke identifizieren wir vier Schlüsselprobleme, bei denen wir die Ereignisprotokolle (Event Logs) aus verschiedenen Perspektiven betrachten. Zunächst befassen wir uns mit dem Problem der Erfassung eines Ereignisprotokolls (Event Logs) ohne hinreichenden Datenbankzugang. Das zweite Problem ist die unzureichende Nutzung des in Ereignisprotokollen (Event Logs) enthaltenen Domänenwissens, das zum besseren Verständnis der generierten Prozessmodelle beitragen kann. Außerdem mangelt es an einer ganzheitlichen Darstellung der historischen Datenmanipulation auf Prozessmodellebene. Nicht zuletzt werden Prozessmodelle häufig unabhängig von anderen Prozessmodellen betrachtet, wenn sie aus Ereignisprotokollen (Event Logs) ermittelt wurden. Dadurch können mögliche Datenabhängigkeiten zwischen Prozessen innerhalb einer Organisation übersehen werden. Für jedes der oben genannten Probleme schlägt diese Arbeit eine eigene Methode vor. Die erste Methode ermöglicht es, ein Ereignisprotokoll (Event Log) ausschließlich anhand der Historie der auf einer Datenbank durchgeführten Transaktionen zu extrahieren, die in Form von Redo-Logs gespeichert ist. Die zweite Methode befasst sich mit der Entdeckung des zugrundeliegenden Datenmodells, das implizit in dem jeweiligen Ereignisprotokoll (Event Log) eingebettet ist, und ergänzt so mit das entdeckte Prozessmodell mit wichtigen, domänenspezifischen Informationen. Bei der dritten Methode wird auf der Ebene des Prozess- modells erfasst, wie sich die Daten auf die laufenden Prozessinstanzen auswirken. Die vierte Methode befasst sich schließlich mit der Entdeckung der Beziehungen zwischen Geschäftsprozessen (d.h. deren Datenaustausch) auf Basis der jeweiligen Ereignisprotokolle (Event Logs), sowie mit der expliziten Darstellung solcher komplexen Abhängigkeiten in einer Geschäftsprozessarchitektur. Alle in dieser Arbeit vorgestellten Methoden sind als Prototyp implementiert und ihre Anwendbarkeit wird anhand ihrer Anwendung auf reale Ereignisprotokolle (Event Logs) nachgewiesen. KW - process mining KW - data models KW - business process architectures KW - Datenmodelle KW - Geschäftsprozessarchitekturen Y1 - 2023 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus4-585427 ER - TY - THES A1 - Katzmann, Maximilian T1 - About the analysis of algorithms on networks with underlying hyperbolic geometry T1 - Über die Analyse von Algorithmen auf Netzwerken mit zugrundeliegender hyperbolischer Geometrie N2 - Many complex systems that we encounter in the world can be formalized using networks. Consequently, they have been in the focus of computer science for decades, where algorithms are developed to understand and utilize these systems. Surprisingly, our theoretical understanding of these algorithms and their behavior in practice often diverge significantly. In fact, they tend to perform much better on real-world networks than one would expect when considering the theoretical worst-case bounds. One way of capturing this discrepancy is the average-case analysis, where the idea is to acknowledge the differences between practical and worst-case instances by focusing on networks whose properties match those of real graphs. Recent observations indicate that good representations of real-world networks are obtained by assuming that a network has an underlying hyperbolic geometry. In this thesis, we demonstrate that the connection between networks and hyperbolic space can be utilized as a powerful tool for average-case analysis. To this end, we first introduce strongly hyperbolic unit disk graphs and identify the famous hyperbolic random graph model as a special case of them. We then consider four problems where recent empirical results highlight a gap between theory and practice and use hyperbolic graph models to explain these phenomena theoretically. First, we develop a routing scheme, used to forward information in a network, and analyze its efficiency on strongly hyperbolic unit disk graphs. For the special case of hyperbolic random graphs, our algorithm beats existing performance lower bounds. Afterwards, we use the hyperbolic random graph model to theoretically explain empirical observations about the performance of the bidirectional breadth-first search. Finally, we develop algorithms for computing optimal and nearly optimal vertex covers (problems known to be NP-hard) and show that, on hyperbolic random graphs, they run in polynomial and quasi-linear time, respectively. Our theoretical analyses reveal interesting properties of hyperbolic random graphs and our empirical studies present evidence that these properties, as well as our algorithmic improvements translate back into practice. N2 - Viele komplexe Systeme mit denen wir tagtäglich zu tun haben, können mit Hilfe von Netzwerken beschrieben werden, welche daher schon jahrzehntelang im Fokus der Informatik stehen. Dort werden Algorithmen entwickelt, um diese Systeme besser verstehen und nutzen zu können. Überraschenderweise unterscheidet sich unsere theoretische Vorstellung dieser Algorithmen jedoch oft immens von derem praktischen Verhalten. Tatsächlich neigen sie dazu auf echten Netzwerken viel effizienter zu sein, als man im schlimmsten Fall erwarten würde. Eine Möglichkeit diese Diskrepanz zu erfassen ist die Average-Case Analyse bei der man die Unterschiede zwischen echten Instanzen und dem schlimmsten Fall ausnutzt, indem ausschließlich Netzwerke betrachtet werden, deren Eigenschaften die von echten Graphen gut abbilden. Jüngste Beobachtungen zeigen, dass gute Abbildungen entstehen, wenn man annimmt, dass einem Netzwerk eine hyperbolische Geometrie zugrunde liegt. In dieser Arbeit wird demonstriert, dass hyperbolische Netzwerke als mächtiges Werkzeug der Average-Case Analyse dienen können. Dazu werden stark-hyperbolische Unit-Disk-Graphen eingeführt und die bekannten hyperbolischen Zufallsgraphen als ein Sonderfall dieser identifiziert. Anschließend werden auf diesen Modellen vier Probleme analysiert, um Resultate vorangegangener Experimente theoretisch zu erklären, die eine Diskrepanz zwischen Theorie und Praxis aufzeigten. Zuerst wird ein Routing Schema zum Transport von Nachrichten entwickelt und dessen Effizienz auf stark-hyperbolischen Unit-Disk-Graphen untersucht. Allgemeingültige Effizienzschranken können so auf hyperbolischen Zufallsgraphen unterboten werden. Anschließend wird das hyperbolische Zufallsgraphenmodell verwendet, um praktische Beobachtungen der bidirektionalen Breitensuche theoretisch zu erklären und es werden Algorithmen entwickelt, um optimale und nahezu optimale Knotenüberdeckungen zu berechnen (NP-schwer), deren Laufzeit auf diesen Graphen jeweils polynomiell und quasi-linear ist. In den Analysen werden neue Eigenschaften von hyperbolischen Zufallsgraphen aufgedeckt und empirisch gezeigt, dass sich diese sowie die algorithmischen Verbesserungen auch auf echten Netzwerken nachweisen lassen. KW - graph theory KW - hyperbolic geometry KW - average-case analysis KW - Average-Case Analyse KW - Graphentheorie KW - hyperbolische Geometrie Y1 - 2023 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus4-582965 ER - TY - THES A1 - Roumen, Thijs T1 - Portable models for laser cutting N2 - Laser cutting is a fast and precise fabrication process. This makes laser cutting a powerful process in custom industrial production. Since the patents on the original technology started to expire, a growing community of tech-enthusiasts embraced the technology and started sharing the models they fabricate online. Surprisingly, the shared models appear to largely be one-offs (e.g., they proudly showcase what a single person can make in one afternoon). For laser cutting to become a relevant mainstream phenomenon (as opposed to the current tech enthusiasts and industry users), it is crucial to enable users to reproduce models made by more experienced modelers, and to build on the work of others instead of creating one-offs. We create a technological basis that allows users to build on the work of others—a progression that is currently held back by the use of exchange formats that disregard mechanical differences between machines and therefore overlook implications with respect to how well parts fit together mechanically (aka engineering fit). For the field to progress, we need a machine-independent sharing infrastructure. In this thesis, we outline three approaches that together get us closer to this: (1) 2D cutting plans that are tolerant to machine variations. Our initial take is a minimally invasive approach: replacing machine-specific elements in cutting plans with more tolerant elements using mechanical hacks like springs and wedges. The resulting models fabricate on any consumer laser cutter and in a range of materials. (2) sharing models in 3D. To allow building on the work of others, we build a 3D modeling environment for laser cutting (kyub). After users design a model, they export their 3D models to 2D cutting plans optimized for the machine and material at hand. We extend this volumetric environment with tools to edit individual plates, allowing users to leverage the efficiency of volumetric editing while having control over the most detailed elements in laser-cutting (plates) (3) converting legacy 2D cutting plans to 3D models. To handle legacy models, we build software to interactively reconstruct 3D models from 2D cutting plans. This allows users to reuse the models in more productive ways. We revisit this by automating the assembly process for a large subset of models. The above-mentioned software composes a larger system (kyub, 140,000 lines of code). This system integration enables the push towards actual use, which we demonstrate through a range of workshops where users build complex models such as fully functional guitars. By simplifying sharing and re-use and the resulting increase in model complexity, this line of work forms a small step to enable personal fabrication to scale past the maker phenomenon, towards a mainstream phenomenon—the same way that other fields, such as print (postscript) and ultimately computing itself (portable programming languages, etc.) reached mass adoption. N2 - Laserschneiden ist ein schnelles und präzises Fertigungsverfahren. Diese Eigenschaften haben das Laserschneiden zu einem starken Anwärter für die industrielle Produktion gemacht. Seitdem die Patente für die ursprüngliche Technologie begannen abzulaufen, nahm eine wachsende Gemeinschaft von Technikbegeisterten die Technologie an und begann, ihre Modelle online zu teilen. Überraschenderweise scheinen die gemeinsam genutzten Modelle größtenteils Einzelstücke zu sein (z.B. zeigten sie stolz, was eine einzelne Person an einem Nachmittag entwickeln kann). Damit das Laserschneiden zu einem relevanten Mainstream-Phänomen wird, ist es entscheidend, dass die Benutzer die Möglichkeit haben Modelle zu reproduzieren, die von erfahrenen Modellierern erstellt wurden, und somit auf der Arbeit anderer aufbauen zu können, anstatt Einzelstücke zu erstellen. Wir schaffen eine technologische Basis, die es Benutzern ermöglicht, auf der Arbeit anderer aufzubauen—eine Entwicklung, die derzeit gehemmt wird durch die Verwendung von Austauschformaten, die mechanische Unterschiede zwischen Maschinen außer Acht lassen und daher Auswirkungen darauf übersehen, wie gut Teile mechanisch zusammenpassen (aka Passung). Damit sich das Feld sich weiterentwickeln kann, brauchen wir eine maschinenunabhängige Infrastruktur für gemeinsame Nutzung. In dieser Dissertation präsentieren wir drei Ansätze, die uns zu diesem Ziel näherbringen: (1) 2D-Schnittpläne, die gegenüber Maschinenvariationen tolerant sind. Unser erster Ansatz ist ein minimalinvasiver Ansatz: Wir ersetzen maschinenspezifische Elemente in Schnittplänen durch tolerantere Elemente unter Verwendung mechanischer Hacks wie Federn und Keile. Die resultierenden Modelle können auf jedem handelsüblichen Laserschneider und in einer Reihe von Materialien hergestellt werden. (2) Teilen von Modellen in 3D. Um auf der Arbeit anderer aufbauen zu können, erstellen wir eine 3D-Modellierungsumgebung für das Laserschneiden (kyub). Nachdem die Benutzer ein Modell entworfen haben, exportieren sie ihre 3D-Modelle in 2D-Schnittpläne, die für die jeweilige Maschine und das vorhandene Material optimiert sind. Wir erweitern diese volumetrische Umgebung mit Werkzeugen zum Bearbeiten einzelner Platten, sodass Benutzer die Effizienz der volumetrischen Bearbeitung nutzen und gleichzeitig die detailliertesten Elemente beim Laserschneiden (Platten) steuern können. (3) Umwandlung von legacy 2D-Schnittplänen in 3D-Modelle. Um mit legacy Modellen umzugehen, entwickeln wir Software, um 3DModelle interaktiv aus 2D-Schnittplänen zu rekonstruieren. Dies ermöglicht Benutzern, die Modelle auf produktivere Weise wiederzuverwenden. Wir behandeln dies erneut, indem wir den Rekonstruierungsprozess für eine große Teilmenge von Modellen automatisieren. Die oben genannte Software ist in ein größeres System integriert (kyub, 140.000 Codezeilen). Diese Systemintegration ermöglicht es, den tatsächlichen Gebrauch voranzutreiben, was wir in einer Reihe von Workshops demonstrieren, in denen Benutzer komplexe Modelle wie voll funktionsfähige Gitarren bauen. Durch die Vereinfachung der gemeinsamen Nutzung und Wiederverwendung und die daraus resultierende Zunahme der Modellkomplexität wird diese Arbeitsrichtung und das daraus resultierende System letztendlich (teilweise) dazu beitragen, dass die persönliche Fertigung über das Maker-Phänomen hinausgeht und sich zu einem Mainstream-Phänomen entwickelt – genauso wie andere Bereiche, z.B. als Druck (Postscript) und schließlich selbst Computer (portable Programmiersprachen usw.), um eine Massenakzeptanz zu erreichen. KW - human computer interaction KW - digital fabrication KW - laser cutting KW - IT systems engineering KW - IT Softwarentwicklung KW - digitale Fabrikation KW - Mensch-Maschine Interaktion KW - Laserschneiden Y1 - 2023 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus4-578141 ER -