May 2022 - 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

TODAY UnRAVeL Survey Lecture "What's New in UnRAVeL?"
by Tim Seppelt 24 May '22

24 May '22

Dear all, this is a reminder for Erika Ábrahám's talk on The Challenge of Compositionality for Stochastic Hybrid Systems <https://www.unravel.rwth-aachen.de/go/id/taysw?lidx=1#aaaaaaaaaatayto> taking place *today at 16:30* in room 5053.2 and on Zoom. Please find the details below. > Hybrid systems are systems, whose behavior is composed from continuous > evolution interrupted by discrete state changes. Hybrid automata are > one of the most well-known formalisms to specify hybrid systems. > > Also different extensions of hybrid automata have been proposed in the > literature to model uncertainties. In this talk we will focus on > modeling stochasticity regarding the time point of discrete steps in a > compositional framework. The main aim of this talk is not to present a > modeling language, but rather to discuss the challenges that come with > the design of a compositional modeling language for stochastic hybrid > systems. 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. The main aim is to provide doctoral researchers as well as master students a broad overview of the subjects of UnRAVeL. Science undergoes continuous change and lives from the constant quest for novel and better results, which are presented at conferences and in journals. This year, 10 UnRAVeL professors will present some of their most recent research successes. Everyone interested, in particular doctoral researchers and master students, are invited to attend the UnRAVeL lecture series 2022 and engage in discussions with the researchers. The talks take place on Tuesdays, 16:30–18:00 in room 5053.2 in the ground floor of building E2. All events are hybrid. To join remotely, please use https://rwth.zoom.us/j/96003885007?pwd=aUczMVdVU0ZXVGtQUFpwQnJHQUFhUT09 / Meeting ID: 960 0388 5007 / Passcode: 273710 Please find a list of all upcoming talks on the UnRAVeL website <https://www.unravel.rwth-aachen.de/cms/UnRAVeL/Studium/~pzix/Ringvorlesung-…> and below: * 24/05/2022 Erika Ábrahám: The Challenge of Compositionality for Stochastic Hybrid Systems * 21/06/2022 Sebastian Trimpe: Uncertainty Bounds for Gaussian Process Regression with Applications to Safe Control and Learning * 28/06/2022 Britta Peis: Stackelberg Network Pricing Games * 05/07/2022 Gerhard Lakemeyer: Tractable Reasoning in First-Order Knowledge Bases We are looking forward to seeing many of you in the UnRAVeL survey lecture "What's New in UnRAVeL?". Best regards, Andreas Klinger, Birgit Willms, and Tim Seppelt Logo

1 0

CANCELLED UnRAVeL Survey Lecture "What's New in UnRAVeL?"
by Tim Seppelt 17 May '22

17 May '22

Dear all, unfortunately, Christina Büsing's talk today had to be cancelled. I'm looking forward to seeing many of you for next week's talk by Erika Ábrahám on The Challenge of Compositionality for Stochastic Hybrid Systems. 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. The main aim is to provide doctoral researchers as well as master students a broad overview of the subjects of UnRAVeL. Science undergoes continuous change and lives from the constant quest for novel and better results, which are presented at conferences and in journals. This year, 10 UnRAVeL professors will present some of their most recent research successes. Everyone interested, in particular doctoral researchers and master students, are invited to attend the UnRAVeL lecture series 2022 and engage in discussions with the researchers. The talks take place on Tuesdays, 16:30–18:00 in room 5053.2 in the ground floor of building E2. All events are hybrid. To join remotely, please use https://rwth.zoom.us/j/96003885007?pwd=aUczMVdVU0ZXVGtQUFpwQnJHQUFhUT09 / Meeting ID: 960 0388 5007 / Passcode: 273710 Please find a list of all upcoming talks on the UnRAVeL website <https://www.unravel.rwth-aachen.de/cms/UnRAVeL/Studium/~pzix/Ringvorlesung-…> and below: * 24/05/2022 Erika Ábrahám: The Challenge of Compositionality for Stochastic Hybrid Systems * 21/06/2022 Sebastian Trimpe: Uncertainty Bounds for Gaussian Process Regression with Applications to Safe Control and Learning * 28/06/2022 Britta Peis: Stackelberg Network Pricing Games * 05/07/2022 Gerhard Lakemeyer: Tractable Reasoning in First-Order Knowledge Bases We are looking forward to seeing many of you in the UnRAVeL survey lecture "What's New in UnRAVeL?". Best regards, Andreas Klinger, Birgit Willms, and Tim Seppelt Logo

1 0

TOMORROW UnRAVeL Survey Lecture "What's New in UnRAVeL?"
by Tim Seppelt 16 May '22

16 May '22

Dear all, this is a reminder for Christina Büsing's talk on A Branch & Bound Algorithm for Robust Binary Optimization with Budget Uncertainty <https://www.unravel.rwth-aachen.de/cms/UnRAVeL/Das-Graduiertenkolleg/Aktuel…> taking place *tomorow at 16:30* in room 5053.2 and on Zoom. Please find the details below. > Since its introduction in the early 2000s, robust optimization with > budget uncertainty has received a lot of attention. This is due to the > intuitive construction of the uncertainty sets and the existence of a > compact robust reformulation for (mixed-integer) linear programs. > > However, despite its compactness, the reformulation performs poorly > when solving robust integer problems due to its weak linear relaxation. > > To overcome the problems arising from the weak formulation, we propose > a bilinear formulation for robust binary programming, which is as > strong as theoretically possible. From this bilinear formulation, we > derive strong linear formulations as well as structural properties for > robust binary optimization problems, which we use within a tailored > branch & bound algorithm. > > We test our algorithm’s performance together with other approaches > from the literature on a diverse set of “robustified” real-world > instances from the MIPLIB 2017. Our computational study, which is the > first to compare many sophisticated approaches on a broad set of > instances, shows that our algorithm outperforms existing approaches by > far. Furthermore, we show that the fundamental structural properties > proven in this paper can be used to substantially improve the > approaches from the literature. > > This highlights the relevance of our findings, not only for the tested > algorithms but also for future research on robust optimization. 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. The main aim is to provide doctoral researchers as well as master students a broad overview of the subjects of UnRAVeL. Science undergoes continuous change and lives from the constant quest for novel and better results, which are presented at conferences and in journals. This year, 10 UnRAVeL professors will present some of their most recent research successes. Everyone interested, in particular doctoral researchers and master students, are invited to attend the UnRAVeL lecture series 2022 and engage in discussions with the researchers. The talks take place on Tuesdays, 16:30–18:00 in room 5053.2 in the ground floor of building E2. All events are hybrid. To join remotely, please use https://rwth.zoom.us/j/96003885007?pwd=aUczMVdVU0ZXVGtQUFpwQnJHQUFhUT09 / Meeting ID: 960 0388 5007 / Passcode: 273710 Please find a list of all upcoming talks on the UnRAVeL website <https://www.unravel.rwth-aachen.de/cms/UnRAVeL/Studium/~pzix/Ringvorlesung-…> and below: * 17/05/2022 Christina Büsing: A Branch & Bound Algorithm for Robust Binary Optimization with Budget Uncertainty * 24/05/2022 Erika Ábrahám: The Challenge of Compositionality for Stochastic Hybrid Systems * 21/06/2022 Sebastian Trimpe: Uncertainty Bounds for Gaussian Process Regression with Applications to Safe Control and Learning * 28/06/2022 Britta Peis: Stackelberg Network Pricing Games * 05/07/2022 Gerhard Lakemeyer: Tractable Reasoning in First-Order Knowledge Bases We are looking forward to seeing many of you in the UnRAVeL survey lecture "What's New in UnRAVeL?". Best regards, Andreas Klinger, Birgit Willms, and Tim Seppelt Logo

1 0

TODAY UnRAVeL Survey Lecture "What's New in UnRAVeL?"
by Andreas Klinger 10 May '22

10 May '22

Dear all, this is a reminder for Martin Grohe's talk on Graph Representations Based on Homomorphisms <https://www.unravel.rwth-aachen.de/go/id/tazps?lidx=1#aaaaaaaaaatazrl> taking place *today at 16:30* in room 5053.2 and on Zoom. Please find the details below. > Representations in terms of homomorphism counts provide a surprisingly rich > view on graphs with applications ranging from logic to machine learning. > Lovász (1967) showed that two graphs G and H are isomorphic if and only if > they are homomorphism indistinguishable over the class of all graphs, i.e., > for every graph F, the number of homomorphisms from F to G equals the number > of homomorphisms from F to H. Recently, homomorphism indistinguishability > over restricted classes of graphs such as bounded treewidth, bounded > treedepth and planar graphs, has emerged as a surprisingly powerful > framework for capturing diverse equivalence relations on graphs arising > from logical equivalences and algebraic equation systems. > > In this talk, I will introduce an algebraic framework for such results > drawing from linear algebra and representation theory. > > The talk is based on recent joint work with Gaurav Rattan and Tim Seppelt > (to appear in ICALP 2022). 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. The main aim is to provide doctoral researchers as well as master students a broad overview of the subjects of UnRAVeL. Science undergoes continuous change and lives from the constant quest for novel and better results, which are presented at conferences and in journals. This year, 10 UnRAVeL professors will present some of their most recent research successes. Everyone interested, in particular doctoral researchers and master students, are invited to attend the UnRAVeL lecture series 2022 and engage in discussions with the researchers. The talks take place on Tuesdays, 16:30–18:00 in room 5053.2 in the ground floor of building E2. All events are hybrid. To join remotely, please use https://rwth.zoom.us/j/96003885007?pwd=aUczMVdVU0ZXVGtQUFpwQnJHQUFhUT09 / Meeting ID: 960 0388 5007 / Passcode: 273710 Please find a list of all upcoming talks on the UnRAVeL website <https://www.unravel.rwth-aachen.de/cms/UnRAVeL/Studium/~pzix/Ringvorlesung-…> and below: * 10/05/2022 Martin Grohe: Graph Representations Based on Homomorphisms * 17/05/2022 Christina Büsing: A Branch & Bound Algorithm for Robust Binary Optimization with Budget Uncertainty * 24/05/2022 Erika Ábrahám: The Challenge of Compositionality for Stochastic Hybrid Systems * 21/06/2022 Sebastian Trimpe: Uncertainty Bounds for Gaussian Process Regression with Applications to Safe Control and Learning * 28/06/2022 Britta Peis: Stackelberg Network Pricing Games * 05/07/2022 Gerhard Lakemeyer: Tractable Reasoning in First-Order Knowledge Bases We are looking forward to seeing many of you in the UnRAVeL survey lecture "What's New in UnRAVeL?". Best regards, Tim Seppelt, Birgit Willms, and Andreas Klinger

1 0

TODAY UnRAVeL Survey Lecture "What's New in UnRAVeL?"
by Tim Seppelt 03 May '22

03 May '22

Dear all, this is a reminder for Jürgen Giesl's talk on Improving Automatic Complexity Analysis of Probabilistic and Non-Probabilistic Integer Programs <https://www.unravel.rwth-aachen.de/cms/UnRAVeL/Das-Graduiertenkolleg/Aktuel…> taking place *today at 16:30* in room 5053.2 and on Zoom. Please find the details below. > We present an approach for automatic complexity analysis of integer > programs, based on an alternating modular inference of upper runtime > and size bounds for program parts. While our approach was originally > developed for non-probabilistic programs, we show how we extended it > to also infer upper bounds on the expected runtimes of probabilistic > integer programs automatically. > > Moreover, for the non-probabilistic case, we show how recent > techniques to improve automated termination analysis of integer > programs can be integrated into our approach for the inference of > runtime bounds. > > To evaluate its power, we implemented our approach in a new version of > our tool KoAT. 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. The main aim is to provide doctoral researchers as well as master students a broad overview of the subjects of UnRAVeL. Science undergoes continuous change and lives from the constant quest for novel and better results, which are presented at conferences and in journals. This year, 10 UnRAVeL professors will present some of their most recent research successes. Everyone interested, in particular doctoral researchers and master students, are invited to attend the UnRAVeL lecture series 2022 and engage in discussions with the researchers. The talks take place on Tuesdays, 16:30–18:00 in room 5053.2 in the ground floor of building E2. All events are hybrid. To join remotely, please use https://rwth.zoom.us/j/96003885007?pwd=aUczMVdVU0ZXVGtQUFpwQnJHQUFhUT09 / Meeting ID: 960 0388 5007 / Passcode: 273710 Please find a list of all upcoming talks on the UnRAVeL website <https://www.unravel.rwth-aachen.de/cms/UnRAVeL/Studium/~pzix/Ringvorlesung-…> and below: * 03/05/2022 Jürgen Giesl: Improving Automatic Complexity Analysis of Probabilistic and Non-Probabilistic Integer Programs * 10/05/2022 Martin Grohe: Graph Representations Based on Homomorphisms * 17/05/2022 Christina Büsing: A Branch & Bound Algorithm for Robust Binary Optimization with Budget Uncertainty * 24/05/2022 Erika Ábrahám: The Challenge of Compositionality for Stochastic Hybrid Systems * 21/06/2022 Sebastian Trimpe: Uncertainty Bounds for Gaussian Process Regression with Applications to Safe Control and Learning * 28/06/2022 Britta Peis: Stackelberg Network Pricing Games * 05/07/2022 Gerhard Lakemeyer: Tractable Reasoning in First-Order Knowledge Bases We are looking forward to seeing many of you in the UnRAVeL survey lecture "What's New in UnRAVeL?". Best regards, Andreas Klinger, Birgit Willms, and Tim Seppelt Logo

1 0

[Informatik-assistenten] Einladung: Informatik-Oberseminar Jonathan Hüser
by Hüser, Jonathan 02 May '22

02 May '22

+********************************************************************** * * * Einladung * * * * Informatik-Oberseminar * * * +********************************************************************** Zeit: Montag, 9. Mai 2022, 15:00 Uhr Zoom: https://rwth.zoom.us/j/98637141061?pwd=Qkw3blFhWEIrelduWmpPSGNtQnN4dz09 Meeting ID: 986 3714 1061 Passcode: 618965 Referent: Jonathan Hüser, M.Sc. Lehrstuhl Informatik 12 Thema: Discrete Tangent and Adjoint Sensitivity Analysis for Discontinuous Solutions of Hyperbolic Conservation Laws Abstract: We consider the discrete tangent and adjoint sensitivities computed via algorithmic differentiation of shock capturing numerical methods for hyperbolic conservation laws which are widely used for models of fluid dynamics such as those based on the Euler equations. For discontinuous solutions the discrete sensitivities do not generally converge to the correct sensitivities of the analytical solution as the discretization grid is refined because the analytical sensitivities are singular at the discontinuities of the solution. In this thesis we propose a convergent numerical approximation of the correct sensitivities of shock discontinuities in discontinuous solutions of hyperbolic conservations laws with respect to the parameters of the initial data. We compute the shock sensitivities by approximating the Rankine-Hugoniot condition taking into consideration the numerical viscosity of shock capturing numerical methods in a way that can be computed by algorithmic differentiation tools. The resulting discrete sensitivities enable for example the gradient-based parameter optimization of optimization problems constrained by a hyperbolic conservation law. Es laden ein: die Dozentinnen und Dozenten der Informatik

1 0