Dear all,
this is a reminder for Michael Schaub's talk with the title "Learning from Networks with Unobserved Edges" taking place today at 12:30 in the B-IT room 5053.2. Please find the details below
In many applications we are confronted with the following system identification scenario: we observe a dynamical process that describes the state of a system at particular times. Based on these observations we want to infer the (dynamical) interactions between the entities we observe. In the context of a distributed system, this typically corresponds to a "network identification" task: find the (weighted) edges of the graph of interconnections. However, often the number of samples we can obtain from such a process are far too few to identify the edges of the network exactly. Can we still reliably infer some aspects of the underlying system? Motivated by this question we consider the following identification problem: instead of trying to infer the exact network, we aim to recover a (low-dimensional) statistical model of the network based on the observed signals on the nodes. More concretely, here we focus on observations that consist of snapshots of a diffusive process that evolves over the unknown network. We model the (unobserved) network as generated from an independent draw from a latent stochastic blockmodel (SBM), and our goal is to infer both the partition of the nodes into blocks, as well as the parameters of this SBM. We present simple spectral algorithms that provably solve the partition and parameter inference problems with high-accuracy. We further discuss some possible variations and extensions of this problem setup.
Part of the programme of the research training group UnRAVeL is a series of lectures on the topics of UnRAVeL’s research thrusts algorithms and complexity, verification, logic and languages, and their application scenarios. Each lecture is given by one of the researchers involved in UnRAVeL.
This years topic is "Biggest Milestones - Research at Its Peak", UnRAVeL professors will present the most important milestone of their respective research.
All interested doctoral researchers and master students are invited to attend the UnRAVeL lecture series 2023 and engage in discussions with researchers and doctoral students.
Next week, Erika Ábrahám is going to give a talk with the title "Building Bridges between Symbolic Computation and Satisfiability Checking"
We are looking forward to seeing you at the lectures.
Kind regards,
Jan-Christoph for the organisation committee
Dear all,
part of the programme of the research training group UnRAVeL is a series of lectures on the topics of UnRAVeL’s research thrusts algorithms and complexity, verification, logic and languages, and their application scenarios. Each lecture is given by one of the researchers involved in UnRAVeL.
This years topic is "Biggest Milestones - Research at Its Peak", UnRAVeL professors will present the most important milestone of their respective research.
This is not only about outstanding or astonishing results for the respective community, but also about their very own scientific milestones, for example a paper or result that the presenter particularly likes and is very proud of.
We get answers to the following questions:
* Which of their papers/results would never be allowed to be deleted if they could keep just one?
* Which paper/result had the greatest influence, on science or on themselfs?
* Why and in what context is it a milestone?
All interested doctoral researchers and master students are invited to attend the UnRAVeL lecture series 2023 and engage in discussions with researchers and doctoral students.
All events take place on Thursdays 12:30 to 14:00, Computer Science Center, Building E2, ground floor, B-IT room 5053.2. The schedule is as following:
* 06.04. Michael Schaub - Learning from Networks with Unobserved Edges
* 13.04. Erika Ábrahám - Building Bridges between Symbolic Computation and Satisfiability Checking
* 20.04. Martin Grohe - The Quest for a Logic Capturing PTIME
* 27.04. Christina Büsing - Robust Strategic Planning for Mobile Medical Units
* 04.05. Sebastian Trimpe - Event-Triggered Learning
* 11.05. Nils Nießen - Can Trains Be on Time?
* 25.05. Jürgen Giesl - Proving Termination with Dependency Pairs
* 15.06. Britta Peis - Ascending Auctions and Matroids
* 22.06. Gerhard Lakemeyer - The Situation Calculus as Lingua Franca for Reasoning about Action
* 29.06. Christopher Morris - Weisfeiler and Leman Go Machine Learning: Expressivity and Generalization of Graph Neural Networks
* 13.07. Joost-Pieter Katoen - Can we meet the deadline? Most probably: yes
We are looking forward to seeing you at the lectures.
Kind regards,
Jan-Christoph for the organisation committee
+**********************************************************************
*
*
* Einladung
*
*
*
* Informatik-Oberseminar
*
*
*
+**********************************************************************
Zeit: Montag, 17. April 2023, 10.00 Uhr
Ort: Gebäude E3, Seminarraum 118, Ahornstr. 55
Referent: Max Lyon M.Sc.
Lehrstuhl für Informatik 8
Thema: Quad Mesh Layout Structure Optimization
Abstract:
Quad meshes are very useful in many applications such as modeling and animation in the entertainment industry, simulation in the construction industry, or as intermediate representation to form easily editable spline surfaces. Some of the interesting properties of quad meshes compared to triangular meshes are natural alignment of edges to the surface's principal curvature directions and their ability to form highly anisotropic elements without the need of excessively small angles.
Therefore, the computer aided or fully automatic generation of quad meshes has been a research focus for many years and is probably going to remain as such for the foreseeable future.
One set of methods that have proven to be particularly well suited for the generation of high quality quad meshes are centered around the creation of an integer-grid map, i.e. a parametrization of the surface into the 2D domain whose parametric integer iso-lines induce a quad mesh structure on the input mesh. These methods offer a high degree of control over the desired sizing and alignment of the resulting quads and generally achieve high element quality. Unfortunately, they disregard the high level structure, i.e. how the irregular vertices of the resulting quad mesh are connected by edge strips. Ideally, these edges form a coarse quad layout, enabling the use of highly efficient multigrid solvers or the manual editing of a small number of spline patches.
In this thesis we give an overview of current state-of-the-art quad meshing algorithms which we then improve upon in different aspects:
We show how a valid quad mesh can always be extracted for the given layout via careful re-embedding of a so called motorcycle graph combined with patchwise harmonic parametrizations followed by a global optimization. We extend the motorcycle graph construction in order to lift the constraints of layouts having to exactly follow the boundaries of the mesh leading to meshes with less distortion whose quads can be cut off by the boundary at an arbitrary angle.
Further, we present a method that is guaranteed to yield a coarse quad layout that adheres to a minimum quality as defined by the user defined maximal allowed deviation of layout arcs from desired direction. For cases where strict adherence to the input field is not required we show how singularities may be moved to better locations or removed entirely to further improve the resulting layout structure.
Finally, we discuss how a quad mesh or layout may be refined in order to achieve a locally increased resolution or anisotropy.
Es laden ein: die Dozentinnen und Dozenten der Informatik
+**********************************************************************
*
*
* Einladung
*
*
*
* Informatik-Oberseminar
*
*
*
+**********************************************************************
Zeit: Mittwoch, 12. April 2023, 15.00 Uhr
Ort: 9222, E3, Ahornstr. 55
und hybrid via Zoom (https://rwth.zoom.us/j/92145754381?pwd=TmhOOXBDc3RITGl1L0NwdGhLTEVKUT09)
Referent: René Röpke M.Sc.
Lehr- und Forschungsgebiet Informatik 9 (Lerntechnologien)
Thema: Extending Game-Based Anti-Phishing Education using Personalization
Abstract:
Phishing poses an imminent and wide-ranging threat to Internet users worldwide, in which attackers use methods of deception to lure victims into disclosing information. Recent reports state high numbers of phishing incidents and, so far, technical solutions fail to stop the threat completely. As a complementary approach, user education using anti-phishing learning games has been explored to raise awareness and teach the necessary knowledge and skills to detect and protect against phishing attacks. A common game mechanic used in existing games requires learners to classify URLs as either legitimate or phishing in a binary decision scheme. Here, a problem can occur if learners do not know the service of a given URL and are unable to classify the URL due to a lack of reference. As such, learners may revert to guessing which may weaken the game's potential for practice, since learners cannot relate between correct classifications and the applied knowledge. Furthermore, the possibilities for feedback are limited since the binary decision mechanic does not provide any insights into learners' decision processes and possible misconceptions. In this dissertation, the limitations for feedback as well as the problem with classifying unknown URLs in anti-phishing learning games are addressed as follows: First, a review of existing learning games provides insights into their design and covered learning content. Its results are used in guiding the design and implementation of two new game prototypes. Here, the first game extends the before-mentioned binary decision mechanic and requires learners to sort URLs into one of many categories, depending on which manipulation technique was applied to a distinct part of the URL. The second game requires learners to apply different manipulation techniques and create their own malicious URLs using a puzzle mechanic. Next, the means of personalization for anti-phishing learning games are explored and a personalization pipeline is developed. By considering the learners' familiarity with different services and dynamically creating benign and phishing URLs, the content of anti-phishing learning games can be personalized. To evaluate the new game prototypes as well as the application of the personalization pipeline, two comparative user studies are conducted in a between-group design with pre-, post- and longitudinal testing. In the first user study with 133 participants, both games are evaluated and compared to a baseline implementation. While participants of the new games did not perform significantly better than the control group, results show significant improvements in the participants' performance and confidence between pre- and post-tests for all games, as well as notable differences when classifying URLs of unknown and known services. In the second user study with 49 participants, the personalization pipeline is integrated into one of the games, in order to compare its personalized and non-personalized version. Here, personalization enables the control of service familiarity and allows insights into how URLs of unknown services are handled within the game. While participants of the personalized game did not outperform the participants of its non-personalized version, the evaluation of in-game behavior provides insights into learners' decision processes and possible problems or misconceptions. Furthermore, results of a longitudinal evaluation of all games and versions show that knowledge is retained since the participants perform still significantly better than in the pre-test. In all, this dissertation presents first approaches and research results in the domain of personalized anti-phishing learning games. Future work may entail redesigning anti-phishing learning games to incorporate further means of personalization and to understand how learner characteristics can be utilized in anti-phishing learning games.
Es laden ein: die Dozentinnen und Dozenten der Informatik
**********************************************************************
*
*
* Einladung
*
*
*
* Informatik-Oberseminar
*
*
*
***********************************************************************
Zeit: Mittwoch, 15. März 2023, 14:00 Uhr
Zoom:
https://rwth.zoom.us/j/93749104715?pwd=bEFSR0lsR1o1Tzl2enVMSzM0aTE2Zz09
Meeting-ID: 937 4910 4715
Kenncode: 743829
Referent: Weiyue Wang, M.Sc.
Thema: Neural Hidden Markov Model for Machine Translation
Abstract:
Recently, neural machine translation systems have shown promising
performance. One of the key components that almost all modern neural
machine translation systems contain is the attention mechanism, which
helps an encoder-decoder model attend to specific positions on the
source side to produce a translation. However, recent studies have found
that using attention weights straight out of the box to align words
results in poor alignment quality. This inspires us to introduce an
explicit alignment model into the neural architecture in order to
improve the alignment and thus also the translation quality of the
overall system. To this end, we propose a novel neural hidden Markov
model consisting of neural network-based lexicon and alignment models
trained jointly with the forward-backward algorithm.
Various neural network architectures are used to model the lexicon and
the alignment probabilities. We start with feedforward neural networks
and apply our first model to re-rank n-best lists generated by
phrase-based systems and observe significant improvements. In order to
build a monolithic neural hidden Markov model, the more powerful
recurrent neural networks are applied to the architecture, and a
standalone decoder is implemented. By replacing the attention mechanism
with an alignment model, we achieve comparable performance to the
baseline attention model while significantly improving the alignment
quality. We also apply the state-of-the-art transformer architecture to
the neural hidden Markov model and the experimental results show that
the transformer-based hidden Markov model outperforms the standard
self-attentive transformer model in terms of TER scores.
In addition to the work on the neural hidden Markov model, we propose
two novel metrics for machine translation evaluation, called CHARACTER
and EED. These are easy-to-use and perform promisingly in the annual WMT
metrics shared tasks.
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
Theaterstraße 35-39
D-52062 Aachen
Tel: +49 241 80-21601
sek(a)hltpr.rwth-aachen.de
www.hltpr.rwth-aachen.de
+**********************************************************************
*
*
* Einladung
*
*
*
* Informatik-Oberseminar
*
*
*
+**********************************************************************
Zeit: Montag, 13.03.2023, 15:00-16:00 Uhr
Der öffentliche Vortrag findet hybrid statt:
Raum: Raum 5053.2 (großer B-IT-Hörsaal)/Informatikzentrum, Ahornstraße 55
Zoom: https://rwth.zoom.us/j/94314167045?pwd=VWt3TTUrUjQrbTRQcDUzYm8yMVcydz09
Meeting-ID: 943 1416 7045
Kenncode: 239326
Referent: Herr Arnab Chakrabarti, M. Sc.
Lehrstuhl Informatik 5
Thema: Exploratory Pipeline for Analysis and Visualization of Large Information Spaces
Abstract:
Visual exploration of datasets having excessive data points and features leads to over-plotting and visual clutter, resulting in the loss of interpretability. This problem has been termed as "visual noise" in the field of high-dimensional data exploration. Our work in this thesis centers around the question of reducing visual noise and improving data interpretability in the quest to find interesting patterns within high-dimensional datasets.
In this thesis, we present algorithms and workflows to tackle the so-called "curse-of-dimensionality". We proposed a visualization ranking model capable of comparing diverse visual structures within a unified framework. Finally, we present a novel visualization recommendation system capable of the process of generating meaningful visualizations that help users to explore and understand their data more efficiently.
To evaluate the effectiveness of our solutions in a high-dimensional setting, we present a data exploration pipeline and test it within the Internet of Production (IoP) settings.
Es laden ein: die Dozentinnen und Dozenten der Informatik
_______________________________
Leany Maaßen
RWTH Aachen University
Lehrstuhl Informatik 5, LuFG Informatik 5
Prof. Dr. Stefan Decker, Prof. Dr. Matthias Jarke,
Prof. Gerhard Lakemeyer Ph.D., JunProf. Dr. Sandra Geisler
Ahornstrasse 55
D-52074 Aachen
Tel: 0241-80-21509
Fax: 0241-80-22321
E-Mail: maassen(a)dbis.rwth-aachen.de
+**********************************************************************
*
*
* Einladung
*
*
*
* Informatik-Oberseminar
*
*
*
+**********************************************************************
Zeit: Donnerstag, 4. Mai 2023, 13.30 Uhr
Ort: Seminarraum 2202, Hauptbau, Ahornstr. 55
Referent: Hendrik Simon M.Sc.
Lehrstuhl Informatik 11
Thema: Automatic Test Case Generation for PLC Software
Abstract:
Automatic test case generation for the purpose of bug finding or achieving coverage goals has recently evolved to a scalable technique that is nowadays used to find highly critical security bugs, e. g. by Microsoft.
However, in the domain of Programmable Logic Controllers (PLCs), applications of this technique are rare and usually rely on tools and mechanisms that were not initially designed for this domain.
In fact, a discussion on how to design such techniques with the peculiarities of PLC software in mind, is missing.
At the same time, PLC software is typically used in safety critical environments where software errors pose significant threats to the environment or humans and may additionally result in significant financial losses.
Mature automatic testing techniques for the PLC domain would, thus, be highly beneficial to further support software quality in this area.
PLC software typically follows a cyclic execution scheme that involves a repeated process of reading input values, executing a (often state machine based) control program that relies on local variables and writing computed values to outputs.
Although the cyclic execution resembles only a small change in the execution semantics, the impact on automatic testing techniques is significant.
This dissertation provides insights and mechanisms to transfer automatic test case generation into the domain of PLC software. We conduct an in-depth discussion on related approaches and point out strengths and weaknesses in order to provide baseline knowledge that can be utilised in future developments in this field of research.
Further, we introduce our own automatic test case generation approaches and exemplify their effectiveness on PLC software. We are able to show that the generation of branch coverage tests can be achieved significantly faster than with existing techniques, rendering our approaches more applicable for larger software.
The focus of our techniques lies in the exploitation of state-machine based execution behaviour and the preservation of structural information in Sequential Function Chart.
For the latter, our presented algorithm can achieve full coverage in a few seconds for programs that could only partly be covered within an hour by related approaches.
Es laden ein: die Dozentinnen und Dozenten der Informatik
+**********************************************************************
*
*
* Einladung
*
*
*
* Informatik-Oberseminar
*
*
*
+**********************************************************************
Zeit: Freitag, 10. März 2023, 11.00 Uhr
Ort: Raum 9222, Gebäude E3, Ahornstr. 55
Zoom:
https://rwth.zoom.us/j/95679484581?pwd=Q0N4SUFZQ21jVERZMDAwc2cyQXpzZz09
Referent: Steffen van Bergerem, M.Sc.
Lehrstuhl für Informatik 7
Thema: Descriptive Complexity of Learning
Abstract:
Supervised learning is a field in machine learning that strives to
classify data based on labelled training examples. In the Boolean
setting, each input is to be assigned to one of two classes, and there
are several fruitful machine-learning methods to obtain a classifier.
However, different algorithms usually come with different types of
classifiers, e.g. decision trees, support-vector machines, or neural
networks, and this is cumbersome for a unified study of the intrinsic
complexity of learning tasks.
This thesis aims at strengthening the theoretical foundations of
machine learning in a consistent framework. In the setting due to
Grohe and Turán (2004), the inputs for the classification are tuples
from a relational structure and the search space for the classifiers
consists of logical formulas. The framework separates the definition
of the class of potential classifiers (the hypothesis class) from the
precise machine-learning algorithm that returns a classifier. This
facilitates an information-theoretic analysis of hypothesis classes
as well as a study of the computational complexity of learning
hypotheses from a specific hypothesis class.
As a first step, Grohe and Ritzert (2017) proved that hypotheses
definable in first-order logic (FO) can be learned in sublinear time
over structures of small degree. We generalise this result to two
extensions of FO that provide data-aggregation methods similar to
those in commonly used relational database systems. First, we study
the extension FOCN of FO with counting quantifiers. Then, we analyse
logics that operate on weighted structures, which can model relational
databases with numerical values. For that, we introduce the new logic
FOWA, which extends FO by weight aggregation. We provide locality
results and prove that hypotheses definable in a fragment of the logic
can be learned in sublinear time over structures of small degree.
To better understand the complexity of machine-learning tasks on
richer classes of structures, we then study the parameterised
complexity of these problems. On arbitrary relational structures and
under common complexity-theoretic assumptions, learning hypotheses
definable in pure first-order logic turns out to be intractable.
In contrast to this, we show that the problem is fixed-parameter
tractable if the structures come from a nowhere dense class.
This subsumes numerous classes of sparse graphs. In particular,
we obtain fixed-parameter tractability for planar graphs, graphs of
bounded treewidth, and classes of graphs excluding a minor.
Es laden ein: die Dozentinnen und Dozenten der Informatik
+**********************************************************************
*
*
* Einladung
*
*
*
* Informatik-Oberseminar
*
*
*
+**********************************************************************
Zeit: Montag, 30.01.2023, 13:00-14:00 Uhr
Ort: Informatikzentrum, Ahornstraße 55, Raum 5053.2 (B-IT-Hörsaal)
Referent: Herr Aleksandar Mitrevski, M. Sc.
LuFG Informatik 5
Thema: Skill Generalisation and Experience Acquisition for Predicting and Avoiding Execution Failures
Abstract:
For performing tasks in their target environments, autonomous robots usually execute and combine skills. Robot skills in general and learning-based skills in particular are usually designed so that flexible skill acquisition is possible, but without an explicit consideration of execution failures, the impact that failure analysis can have on the skill learning process, or the benefits of introspection for effective coexistence with humans. Particularly in human-centered environments, the ability to understand, explain, and appropriately react to failures can affect a robot's trustworthiness and, consequently, its overall acceptability. Thus, in this dissertation, we study the questions of how parameterised skills can be designed so that execution-level decisions are associated with semantic knowledge about the execution process, and how such knowledge can be utilised for avoiding and analysing execution failures.
The first major segment of this work is dedicated to developing a representation for skill parameterisation whose objective is to improve the transparency of the skill parameterisation process and enable a semantic analysis of execution failures. We particularly develop a hybrid learning-based representation for parameterising skills, called an execution model, which combines qualitative success preconditions with a function that maps parameters to predicted execution success. The second major part of this work focuses on applications of the execution model representation to address different types of execution failures. We first present a diagnosis algorithm that, given parameters that have resulted in a failure, finds a failure hypothesis by searching for violations of the qualitative model, as well as an experience correction algorithm that uses the found hypothesis to identify parameters that are likely to correct the failure. Furthermore, we present an extension of execution models that allows multiple qualitative execution contexts to be considered so that context-specific execution failures can be avoided. Finally, to enable the avoidance of model generalisation failures, we propose an adaptive ontology-assisted strategy for execution model generalisation between object categories that aims to combine the benefits of model-based and data-driven methods; for this, information about category similarities as encoded in an ontology is integrated with outcomes of model generalisation attempts performed by a robot. The proposed methods are evaluated in multiple experiments performed with a Toyota Human Support Robot.
The main contributions of this work include a formalisation of the skill parameterisation problem by considering execution failures as an integral part of the skill design and learning process, a demonstration of how a hybrid representation for parameterising skills can contribute towards improving the introspective properties of robot skills, as well as an extensive evaluation of the proposed methods in various experiments. We believe that this work constitutes a small first step towards more failure-aware robots that are suitable to be used in human-centered environments.
Es laden ein: die Dozentinnen und Dozenten der Informatik
_______________________________
Leany Maaßen
RWTH Aachen University
Lehrstuhl Informatik 5, LuFG Informatik 5
Prof. Dr. Stefan Decker, Prof. Dr. Matthias Jarke,
Prof. Gerhard Lakemeyer Ph.D., JunProf. Dr. Sandra Geisler
Ahornstrasse 55
D-52074 Aachen
Tel: 0241-80-21509
Fax: 0241-80-22321
E-Mail: maassen(a)dbis.rwth-aachen.de
+**********************************************************************
*
*
* Einladung
*
*
*
* Informatik-Oberseminar
*
*
*
+**********************************************************************
Zeit: Montag, 06. März 2023, 14:00 Uhr
Ort: Raum 2202 (HBau, 2. Stock), Ahornstr. 55
Hybrid über Zoom:
https://rwth.zoom.us/j/99712637671?pwd=U0UzV1JiL1hwWnlzNW5pUC9hVDdOUT09
Referent: Marcus Völker, M.Sc. RWTH
Informatik 11 Embedded Software
Thema: Policy Iteration for Value Set Analysis of PLC Programs
Abstract:
Ensuring the correct behaviour of computing systems is an important task to
prevent danger to the users of such systems. To do this, many analysis
techniques have been developed that can find bugs in software, or prove that
it complies to some specification of correct behaviour.
Among these techniques, a fundamental analysis is value set analysis (VSA),
which can determine an approximation of the program variables' values at
each point of the program. This is very important information, as many
faulty behaviours can be traced back to variables taking unexpected values,
such as division by zero, access to uninitialised memory or outside a
buffer, or unreachable code.
While classically, value set analysis is performed with the algorithm of
Kleene iteration, another approach called policy iteration has been
developed in recent years that provides an alternative with the potential of
finding similar or better results than Kleene iteration in less time.
Policy iteration works by using a heuristic to simplify the program in a
certain way, finding the value sets of that program, and then checking
whether the result is applicable to the original program. If yes, the
results are used, otherwise different simplifications have to be checked,
until a usable result is found.
As policy iteration is a heuristic algorithm, it makes certain assumptions
about program behaviour in order to achieve good results. It turns out,
however, that these assumptions are not guaranteed if the program contains
errors which cause it to behave differently than expected. As we use program
analysis to find errors such as this, assuming an error-free program is not
necessarily a good assumption.
In this thesis, we show several ways to improve the original heuristic by
focusing on program loops. First, we present a way to use a pre-analysis to
determine some aspect of the loops' behaviours, and use this information in
order to build a heuristic that leads to more accurate solutions than the
standard heuristic in many cases, at the cost of additional running time
necessary to perform this pre-analysis.
Then, we show a way to reinterpret branches as loops if they occur in
cyclical code, which is typical for programs in reactive systems, such as
the systems used for factory automation. This allows us to use our loop
heuristic on a wider variety of programs, even though the cost becomes even
greater, and it is useful only in specific cases.
Afterwards, we show how to remove the pre-analysis to gain back the lost
time, while still retaining similarly good results to the expensive version
introduced before. This has the additional benefit of allowing usage of the
algorithms on branches as in the second approach, without incurring any
additional costs. We motivate that this is the version of policy iteration
that should be used in general with an extensive evaluation of generated
programs.
Finally, we show a way to analyse polynomial inequalities with value set
analysis by reinterpreting them as conjunctions of simpler inequalities.
This not only allows us to improve value set analysis results on programs
that feature such inequalities, but also makes these programs accessible to
policy iteration.
Es laden ein: die Dozentinnen und Dozenten der Informatik