April 2021 - informatik-vortraege - lists.rwth-aachen.de

Einladung Informatik-Oberseminar Malte Nuhn
by Sekretariat I6 30 May '22

30 May '22

+********************************************************************** * * * Einladung * * * * Informatik-Oberseminar * * * +********************************************************************** Zeit: Freitag, 12. Juli 2019, 10.00 Uhr Ort: Informatikzentrum, E3, Raum 9222 Referent: Dipl.-Inform. Malte Nuhn Thema: Unsupervised Training with Applications in Natural Language Processing// Abstract: The state-of-the-art algorithms for various natural language processing tasks require large amounts of labeled training data. At the same time, obtaining labeled data of high quality is often the most costly step in setting up natural language processing systems.Opposed to this, unlabeled data is much cheaper to obtain and available in larger amounts.Currently, only few training algorithms make use of unlabeled data. In practice, training with only unlabeled data is not performed at all. In this thesis, we study how unlabeled data can be used to train a variety of models used in natural language processing. In particular, we study models applicable to solving substitution ciphers, spelling correction, and machine translation. This thesis lays the groundwork for unsupervised training by presenting and analyzing the corresponding models and unsupervised training problems in a consistent manner.We show that the unsupervised training problem that occurs when breaking one-to-one substitution ciphers is equivalent to the quadratic assignment problem (QAP) if a bigram language model is incorporated and therefore NP-hard. Based on this analysis, we present an effective algorithm for unsupervised training for deterministic substitutions. In the case of English one-to-one substitution ciphers, we show that our novel algorithm achieves results close to human performance, as presented in [Shannon 49]. Also, with this algorithm, we present, to the best of our knowledge, the first automatic decipherment of the second part of the Beale ciphers.Further, for the task of spelling correction, we work out the details of the EM algorithm [Dempster & Laird + 77] and experimentally show that the error rates achieved using purely unsupervised training reach those of supervised training.For handling large vocabularies, we introduce a novel model initialization as well as multiple training procedures that significantly speed up training without hurting the performance of the resulting models significantly.By incorporating an alignment model, we further extend this model such that it can be applied to the task of machine translation. We show that the true lexical and alignment model parameters can be learned without any labeled data: We experimentally show that the corresponding likelihood function attains its maximum for the true model parameters if a sufficient amount of unlabeled data is available. Further, for the problem of spelling correction with symbol substitutions and local swaps, we also show experimentally that the performance achieved with purely unsupervised EM training reaches that of supervised training. Finally, using the methods developed in this thesis, we present results on an unsupervised training task for machine translation with a ten times larger vocabulary than that of tasks investigated in previous work. Es laden ein: die Dozentinnen und Dozenten der Informatik _______________________________________________ -- -- Stephanie Jansen Faculty of Mathematics, Computer Science and Natural Sciences HLTPR - Human Language Technology and Pattern Recognition RWTH Aachen University Ahornstraße 55 D-52074 Aachen Tel. Frau Jansen: +49 241 80-216 06 Tel. Frau Andersen: +49 241 80-216 01 Fax: +49 241 80-22219 sek(a)i6.informatik.rwth-aachen.de www.hltpr.rwth-aachen.de Tel: +49 241 80-216 01/06 Fax: +49 241 80-22219 sek(a)i6.informatik.rwth-aachen.de www.hltpr.rwth-aachen.de

3 15

UnRAVeL "Behind the Scenes" Survey Lecture
by Tim Seppelt 26 Jul '21

26 Jul '21

Dear all, part of the programme of the research training group UnRAVeL is a series of introductory lectures on the topics of „randomness“ and „uncertainty“ in UnRAVeL’s research thrusts algorithms and complexity, verification, logic and languages, and their application scenarios. Each lecture is delivered by one of the researchers involved in UnRAVeL. The main aim is to provide doctoral researchers as well as master students a broad overview of the subjects of UnRAVeL. This year, 12 UnRAVeL professors will answer the following questions, based on one of their recent scientific results: * How did you get to this result? * How did you come up with certain key ideas? * How did you cope with obstacles on the way? Which ideas you had did not work out? Following these talks, PhD students will give an informal summary of their doctoral studies within UnRAVeL. All interested doctoral researchers and master students are invited to attend the UnRAVeL lecture series 2021 and engage in discussions with researchers and doctoral students. Details information can be found on https://www.unravel.rwth-aachen.de/cms/UnRAVeL/Studium/~pzix/Ringvorlesung-… All events take place on *Thursdays from 16:30 to 18:00 on Zoom* https://rwth.zoom.us/j/96043715437?pwd=U0dRczkyQjRCY21abW13TDNmUHlhUT09 * 15/04/2021 Survey Lecture: Erika Ábrahám: Probabilistic Hyperproperties * 22/04/2021 Jürgen Giesl: Inferring Expected Runtimes of Probabilistic Programs * 29/04/2021 Erich Grädel: Hidden Variables in Quantum Mechanics and Logics of Dependence and Independence * 06/05/2021 Christof Löding: Learning Automata for Infinite Words * 20/05/2021 Martin Grohe: The Logic of Graph Neural Networks * 10/06/2021 Britta Peis: Sensitivity Analysis for Submodular Function Optimization with Applications in Algorithmic Game Theory * 17/06/2021 Nils Nießen: Optimised Maintenance of Railway Infrastructure * 24/06/2021 Gerhard Lakemeyer: Uncertainty in Robotics * 01/07/2021 Joost-Pieter Katoen: The Surprises of Probabilistic Termination * 08/07/2021 Christina Büsing: Robust Minimum Cost Flow Problem Under Consistent Flow Constraints * 15/07/2021 Ringvorlesung: Gerhard Woeginger: Bilevel optimization * 22/07/2021 Ulrike Meyer: Malware Detection We are looking forward to seeing you at the lectures. Best regards, Tim Seppelt for the organisation committee https://www.unravel.rwth-aachen.de/global/show_picture.asp?id=aaaaaaaaaydoc…

1 13

Einladung: Informatik-Oberseminar Andrea Schnorr
by Andrea Schnorr 03 Jul '21

03 Jul '21

+********************************************************************** * * * Einladung * * * * Informatik-Oberseminar * * * +********************************************************************** Zeit: Freitag, 19. Februar 2021, 11.00 Uhr Zoom: https://rwth.zoom.us/j/2452218628 Referent: Andrea Schnorr, M.Sc. LuFG i12 Thema: Feature Tracking for Space-Filling Structures Abstract: Feature-based visualization is a proven strategy to deal with the massive amounts of data emerging from time-dependent simulations: the analysis focuses on meaningful structures, i.e., said features. Feature tracking algorithms aim at automatically finding corresponding objects in successive time steps of these time-dependent data sets in order to assemble the individual objects into spatio-temporal features. Classically, feature-based visualization has focused on sparse structures, i.e. structures which cover only a small portion of the data domain. Given a sufficiently high temporal resolution, existing tracking approaches are able to reliably resolve the correspondence between feature objects of successive time steps. Our research is motivated by our collaborators' work on the statistical analysis of structures that are space-filling by definition: dissipation elements. Space-filling structures partition the entire domain. Our collaborators aim at extending their statistical analysis to a time-dependent setting. Hence, we introduce an efficient approach for general feature tracking which handles both sparse and space-filling data. To this end, we develop a framework for automatic evaluation of tracking approaches, an algorithmic framework for feature tracking, and an efficient implementation of this framework. First, we propose a novel evaluation framework based on algorithmic data generators, which provide synthetic data sets and the corresponding ground truth data. This framework facilitates the structured quantitative analysis of an approach's feature tracking performance and the comparison of different approaches based on the resulting measurements. Second, we introduce a novel approach for tracking both sparse and space-filling features. The correspondence between neighboring time-steps is determined by successively solving two graph optimization problems. In the first phase, one-to-one assignments are resolved by computing a maximum-weight, maximum-cardinality matching on a bi-partite graph. In its second phase, the algorithm detects events by finding a maximum weight independent set in a graph of all possible, potentially conflicting event explanations. Third, we show an optimized version of the second stage of the tracking framework which exploits the model-specific graph structure arising for the tracking problem. The method's effectiveness is demonstrated by a set of case studies including the use of the evaluation framework as well as the analysis of miscellaneous real-world simulation data sets. Es laden ein: die Dozentinnen und Dozenten der Informatik

2 1

12.05.2021, 10:30: Guest Talk on Neural Termination Analysis by Mirco Giacobbe
by Bolke-Hermanns, Helene 30 Apr '21

30 Apr '21

Dear all, on Wednesday, May 12, at 10:30 am, Mirco Giacobbe from the University of Oxford will give a talk on his recent work of applying neural networks to perform termination analysis. Wednesday, 12.05.2021, 10:30 am https://rwth.zoom.us/j/99669198425?pwd=NTNzTGNnYjNrQUc0ZDFTTVdiWjY4UT09 Meeting-ID: 996 6919 8425, Passcode: 878733 Everybody is welcome! Best regards Helen Bolke-Hermanns ----------------------------------------------------------------------------------------- Mirco Giacobbe (University of Oxford, UK): Neural Termination Analysis Termination analysis answers the question of whether a program always responds or, dually, never gets stuck in an infinite loop. This is unsolvable in general, yet tools that work in practice have been developed in industry and academia. The major existing methods construct termination proofs via symbolic reasoning from the source code. I will talk about a novel method for learning termination proofs from execution traces. We let neural networks fit termination witnesses over execution traces and then use satisfiability modulo theories for checking whether they generalise to all possible executions. Thanks to the ability of neural networks to generalise well, neural termination analysis succeeds over a wide variety of programs. Moreover, it is extremely simple to implement. I will talk about how we apply neural termination analysis to the termination analysis of Java programs that use data structures, to the almost-sure termination analysis of probabilistic programs, and to the stability analysis of cyber-physical systems. More information: https://www.unravel.rwth-aachen.de/go/id/nyoee

1 0

Ankündigung: Informatik-Oberseminar
by Schweigler, Martin 21 Apr '21

21 Apr '21

+********************************************************************** * * * Einladung * * * * Informatik-Oberseminar * * * +********************************************************************** Zeit: Mittwoch, 5. Mai 2021, 11.00 Uhr Ort: Videokonferenz (Zoom-Meeting, Information siehe unten) Referent: Martin Schweigler, M.Sc. RWTH Informatik 11 - Embedded Software Thema: Ground Surface Pattern Recognition for Enhanced Navigation Abstract: With the continuous increase in sales of electrical assisted bicycles over the last decade, the number of bicycle accidents across Europe has simultaneously grown significantly. At the same time the technology lacks on active safety systems, even though the electrification of the so-called Pedelecs would allow their development. This dissertation can be seen as the first step in the process of developing position and situation dependent active safety systems by improving the position determination accuracy of bicycle navigation systems. In the core of this work a position estimation system is developed, which uses road sections with significant surface conditions to improve the positioning accuracy of a conventional GNSS/INS. Based on the vertical accelerations acting on the moving Pedelec, the system recognizes individual spots in the road surface, e.g. manholes or potholes. To be more precise, the individual acceleration profiles that occur when passing different spots, are recorded with a smartphone and statistically modeled offline with the help of continuous hidden Markov models during the training phase. In online mode, the trained models are then used to recognize the spots by the acceleration profiles of the revisited road sections. The absolute positions of the Pedelec, relative to the global coordinates of the recognized spots, are subsequently determined by an inertial calculation of the distances traveled in the time between their detection and classification. The system thus uses statistical models to estimate the absolute position of the Pedelec and is consequently called Statistical Absolute Position Estimator, or SAPE. In the second part of this work, SAPE is used to develop a navigation system, which shows the potential of the ground surface pattern recognition. For this purpose the SAPE and GNSS position determinations are fused with an inertial navigation system using an extended Kalman filter. Since the inertial sensors provided by the chosen smartphone are not accurate enough to realize a stand-alone INS, an odometry is developed and implemented to support the navigation solution. The resulting GNSS, SAPE and odometry supported INS is finally evaluated using an RTK GNSS and its accuracy is compared to that of a conventional odometry supported GNSS/INS created with the same low-cost hardware. Es laden ein: die Dozentinnen und Dozenten der Informatik ******************************** Thema: Promotionsvortrag Martin Schweigler Uhrzeit: 05. Mai 2021 11:00 AM Amsterdam, Berlin, Stockholm, Wien Zoom-Meeting beitreten https://rwth.zoom.us/j/96325334175?pwd=R2o3TWNKYk9kS0hWN3k3UHVhblNYZz09 Meeting-ID: 963 2533 4175 Kenncode: 988764

1 0