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 - Möhring, Jan T1 - Stochastic inversion for core field modeling using satellite data N2 - Magnetfeldmodellierung mit Kugelflächenfunktionen basiert auf der Inversion nach hunderten bis tausenden von Parametern. Dieses hochdimensionale Problem kann grundsätzlich als ein Optimierungsproblem formuliert werden, bei dem ein globales Minimum einer gewissen Zielfunktion berechnet werden soll. Um dieses Problem zu lösen, gibt es eine Reihe bekannter Ansätze, dazu zählen etwa gradientenbasierte Verfahren oder die Methode der kleinsten Quadrate und deren Varianten. Jede dieser Methoden hat verschiedene Vor- und Nachteile, beispielsweise bezüglich der Anwendbarkeit auf nicht-differenzierbare Funktionen oder der Laufzeit zugehöriger Algorithmen. In dieser Arbeit verfolgen wir das Ziel, einen Algorithmus zu finden, der schneller als die etablierten Verfahren ist und sich auch für nichtlineare Probleme anwenden lässt. Solche nichtlinearen Probleme treten beispielsweise bei der Abschätzung von Euler-Winkeln oder bei der Verwendung der robusteren L_1-Norm auf. Dazu untersuchen wir die Anwendbarkeit stochastischer Optimierungsverfahren aus der CMAES-Familie auf die Modellierung des geomagnetischen Feldes des Erdkerns. Es werden sowohl die Grundlagen der Kernfeldmodellierung und deren Parametrisierung anhand einiger Beispiele aus der Literatur besprochen, als auch die theoretischen Hintergründe der stochastischen Verfahren gegeben. Ein CMAES-Algorithmus wurde erfolgreich angewendet, um Daten der Swarm-Satellitenmission zu invertieren und daraus das Magnetfeldmodell EvoMag abzuleiten. EvoMag zeigt gute Übereinstimmung mit etablierten Modellen, sowie mit Observatoriumsdaten aus Niemegk. Wir thematisieren einige beobachtete Schwierigkeiten und präsentieren und diskutieren die Ergebnisse unserer Modellierung. N2 - Geomagnetic field modeling using spherical harmonics requires the inversion for hundreds to thousands of parameters. This large-scale problem can always be formulated as an optimization problem, where a global minimum of a certain cost function has to be calculated. A variety of approaches is known in order to solve this inverse problem, e.g. derivative-based methods or least-squares methods and their variants. Each of these methods has its own advantages and disadvantages, which affect for example the applicability to non-differentiable functions or the runtime of the corresponding algorithm. In this work, we pursue the goal to find an algorithm which is faster than the established methods and which is applicable to non-linear problems. Such non-linear problems occur for example when estimating Euler angles or when the more robust L_1 norm is applied. Therefore, we will investigate the usability of stochastic optimization methods from the CMAES family for modeling the geomagnetic field of Earth's core. On one hand, basics of core field modeling and their parameterization are discussed using some examples from the literature. On the other hand, the theoretical background of the stochastic methods are provided. A specific CMAES algorithm was successfully applied in order to invert data of the Swarm satellite mission and to derive the core field model EvoMag. The EvoMag model agrees well with established models and observatory data from Niemegk. Finally, we present some observed difficulties and discuss the results of our model. T2 - Stochastische Inversion für Kernfeldmodellierung mit Satellitendaten KW - Geomagnetismus KW - Kernfeldmodellierung KW - Optimierung KW - Evolutionsstrategien KW - Inverse Probleme KW - Geomagnetism KW - Core Field Modeling KW - Optimization KW - Evolution Strategies KW - Inverse Problems Y1 - 2021 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus4-498072 ER - TY - THES A1 - Höllerer, Reinhard T1 - Modellierung und Optimierung von Bürgerdiensten am Beispiel der Stadt Landshut T1 - Modeling and optimization of civil services on the example of the city of Landshut N2 - Die Projektierung und Abwicklung sowie die statische und dynamische Analyse von Geschäftsprozessen im Bereich des Verwaltens und Regierens auf kommunaler, Länder- wie auch Bundesebene mit Hilfe von Informations- und Kommunikationstechniken beschäftigen Politiker und Strategen für Informationstechnologie ebenso wie die Öffentlichkeit seit Langem. Der hieraus entstandene Begriff E-Government wurde in der Folge aus den unterschiedlichsten technischen, politischen und semantischen Blickrichtungen beleuchtet. Die vorliegende Arbeit konzentriert sich dabei auf zwei Schwerpunktthemen: • Das erste Schwerpunktthema behandelt den Entwurf eines hierarchischen Architekturmodells, für welches sieben hierarchische Schichten identifiziert werden können. Diese erscheinen notwendig, aber auch hinreichend, um den allgemeinen Fall zu beschreiben. Den Hintergrund hierfür liefert die langjährige Prozess- und Verwaltungserfahrung als Leiter der EDV-Abteilung der Stadtverwaltung Landshut, eine kreisfreie Stadt mit rund 69.000 Einwohnern im Nordosten von München. Sie steht als Repräsentant für viele Verwaltungsvorgänge in der Bundesrepublik Deutschland und ist dennoch als Analyseobjekt in der Gesamtkomplexität und Prozessquantität überschaubar. Somit können aus der Analyse sämtlicher Kernabläufe statische und dynamische Strukturen extrahiert und abstrakt modelliert werden. Die Schwerpunkte liegen in der Darstellung der vorhandenen Bedienabläufe in einer Kommune. Die Transformation der Bedienanforderung in einem hierarchischen System, die Darstellung der Kontroll- und der Operationszustände in allen Schichten wie auch die Strategie der Fehlererkennung und Fehlerbehebung schaffen eine transparente Basis für umfassende Restrukturierungen und Optimierungen. Für die Modellierung wurde FMC-eCS eingesetzt, eine am Hasso-Plattner-Institut für Softwaresystemtechnik GmbH (HPI) im Fachgebiet Kommunikationssysteme entwickelte Methodik zur Modellierung zustandsdiskreter Systeme unter Berücksichtigung möglicher Inkonsistenzen (Betreuer: Prof. Dr.-Ing. Werner Zorn [ZW07a, ZW07b]). • Das zweite Schwerpunktthema widmet sich der quantitativen Modellierung und Optimierung von E-Government-Bediensystemen, welche am Beispiel des Bürgerbüros der Stadt Landshut im Zeitraum 2008 bis 2015 durchgeführt wurden. Dies erfolgt auf Basis einer kontinuierlichen Betriebsdatenerfassung mit aufwendiger Vorverarbeitung zur Extrahierung mathematisch beschreibbarer Wahrscheinlichkeitsverteilungen. Der hieraus entwickelte Dienstplan wurde hinsichtlich der erzielbaren Optimierungen im dauerhaften Echteinsatz verifiziert. [ZW07a] Zorn, Werner: «FMC-QE A New Approach in Quantitative Modeling», Vortrag anlässlich: MSV'07- The 2007 International Conference on Modeling, Simulation and Visualization Methods WorldComp2007, Las Vegas, 28.6.2007. [ZW07b] Zorn, Werner: «FMC-QE, A New Approach in Quantitative Modeling», Veröffentlichung, Hasso-Plattner-Institut für Softwaresystemtechnik an der Universität Potsdam, 28.6.2007. N2 - The project development and implementation as well as the static and dynamic analysis of business processes in the context of administration and governance on a municipal, federal state or national level by information and communication technology, has concerned the media along with politicians and strategists for information technology as well as the general public for a long time. The here-from defined term of E-Government has been examined as the focal point of discussion from most diverse technical, political and semantic perspectives. The present work focuses on two main topics: • The first main topic approaches the development of a hierarchical architecture model for which seven hierarchical layers can be identified. These seem to be necessary as well as sufficient to describe the general case. The background is provided by the long-term processual and administrative experience as head of the IT department at the municipality of Landshut, an independent city with 69.000 inhabitants located in the north-east of Munich. It is representative of many administrative processes in the Federal Republic of Germany, but nonetheless still manageable concerning its complexity and quantity of processes. Therefore, static and dynamic structures can be extracted from the analysis of all core workflows and modelled abstractly. The emphases lie on the description of the existing operating procedures in a municipality. The transformation of the operating requirements in a hierarchical system, the modeling of the control and operational states within all layers, as well as the strategy of error recognition and troubleshooting create a transparent basis for extensive restructuring and optimisation. For modeling was used FMC-eCS, a methodology for the description of state discrete systems, developed at the Hasso-Plattner-Institute for Software Systems Engineering (HPI) in the subject area of communication systems. Furthermore inconsistent system statuses are taken into consideration (advisor: Prof. Dr.-Ing. Werner Zorn [ZW02, …, ZW10]). • The second main topic focuses on the quantitative modeling and optimisation of the E-Government process chain at Landshut´s Citizens Advice Bureau (2008 up to 2015). This is based on a continuous data acquisition with sophisticated pre-processing to extract mathematically describable probability distributions. The derivation of a duty roster for actual application and a quality control conclusively verify the developed stochastic method. KW - E-Government KW - Modellierung KW - Optimierung KW - eGovernment KW - modeling KW - optimization Y1 - 2016 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus4-425986 ER - TY - THES A1 - Kubas, Daniel T1 - Applications of Galactic Microlensing T1 - Anwendungen des Galaktischen Mikrolinseneffektes N2 - Subject of this work is the study of applications of the Galactic Microlensing effect, where the light of a distant star (source) is bend according to Einstein's theory of gravity by the gravitational field of intervening compact mass objects (lenses), creating multiple (however not resolvable) images of the source. Relative motion of source, observer and lens leads to a variation of deflection/magnification and thus to a time dependant observable brightness change (lightcurve), a so-called microlensing event, lasting weeks to months. The focus lies on the modeling of binary-lens events, which provide a unique tool to fully characterize the lens-source system and to detect extra-solar planets around the lens star. Making use of the ability of genetic algorithms to efficiently explore large and intricate parameter spaces in the quest for the global best solution, a modeling software (Tango) for binary lenses is developed, presented and applied to data sets from the PLANET microlensing campaign. For the event OGLE-2002-BLG-069 the 2nd ever lens mass measurement has been achieved, leading to a scenario, where a G5III Bulge giant at 9.4 kpc is lensed by an M-dwarf binary with total mass of M=0.51 solar masses at distance 2.9 kpc. Furthermore a method is presented to use the absence of planetary lightcurve signatures to constrain the abundance of extra-solar planets. N2 - Thema der Arbeit ist das Studium von Anwendungen des Galaktischen Mikrolinseneffektes bei dem das Licht eines entfernten Sternes (Quelle) nach Einstein's Theorie der Gravitation im Schwerefeld eines sich hinreichend nahe der Sichlinie zur Quelle befindlichen massereichen kompakten Objektes (Linse) abgelenkt wird und Mehrfachbilder der Quelle erzeugt werden (welche jedoch nicht aufgelöst werden können). Die Relativbewegung von Quelle, Beobachter und Linse führt zur einer Änderung der Ablenk-und Verstärkungswirkung und somit zu einer beobachtbaren Helligkeitsänderung der Quelle (Lichtkurve), einem sogenannten Mikrolinsenereignis, welches Wochen bis Monate andauert. Der Schwerpunkt liegt in der Modelierung von Doppellinsen-Ereignissen, welche die einzigartige Möglichkeit bieten das Linsen-Quelle System vollständig zu charakterisieren und extra-solare Planeten um den Linsenstern zu detektieren. Unter Verwendung der Eigenschaft genetischer Algorithmen hoch-dimensionale und komplizierte Parameterräume effizient nach dem besten globalen Model zu durchsuchen, wird eine Modelier-Software (Tango) entwickelt, präsentiert und auf Daten der PLANET Mikrolinsen Beobachtungskampagne angewandt. Dabei konnte für das Ereignis OGLE-2002-BLG-069 zum zweitenmal überhaupt die Linsenmasse bestimmt werden, in einem Szenario bei dem ein G5III Bulge Riese, 9.4 kpc entfernt, von einem M-Zwerg Binärsystem mit einer Gesamtmasse von M=0.51 Sonnenmassen in einer Entfernung von 2.9 kpc gelinst wird. Darüberhinaus wird ein Verfahren vorgestellt mit dem man die Abwesenheit planetarer Lichtkurvensignaturen nutzen kann, um Aussagen über die Häufigkeit extrasolarer Planeten zu treffen. KW - Planeten KW - Gravitation KW - Milchstrasse KW - Genetik KW - Gravitationslinsen KW - Mikrolinsen KW - OGLE KW - PLANET KW - Optimierung KW - microlensing KW - planet KW - OGLE KW - gravity KW - genetics Y1 - 2005 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:kobv:517-opus-5179 ER -