Refine
Year of publication
Document Type
- Preprint (759)
- Article (402)
- Working Paper (119)
- Doctoral Thesis (93)
- Diploma Thesis (47)
- Conference Proceeding (41)
- Book (37)
- Bachelor Thesis (36)
- diplomthesis (28)
- Report (25)
Has Fulltext
- yes (1619)
Is part of the Bibliography
- no (1619)
Keywords
Institute
- Informatik (1619) (remove)
Die wahrscheinlich beste Entscheidung : wie Online-Algorithmen mit der unsicheren Zukunft rechnen
(2018)
Lohnt es sich, als Skianfänger in einem schneeunsicheren Jahr Skier zu kaufen? Oder ist es günstiger, sie zu mieten? Oft müssen wir Entscheidungen treffen, ohne genügend Informationen über die Zukunft zu haben. Das gilt in noch größerem Maße für Rechnersysteme, die große Datenmengen verarbeiten und schnelle Entscheidungen treffen müssen. Damit sie trotz einer Vielzahl von Unsicherheiten erfolgreich arbeiten können, entwickeln Informatiker OnlineAlgorithmen.
Large language models have become widely available to the general public, especially due to ChatGPT's release. Consequently, the AI community has invested much effort into recreating language models of the same caliber as ChatGPT, since the latter is still a technical blackbox. This thesis aims to contribute to that cause by proposing R.O.B.E.R.T., a Robotic Operating Buddy for Efficiency, Research and Teaching. In doing so, it presents a first implementation of a lightweight environment which produces tailor-made, instruction-following language models with a heavy focus on conversational capabilities that instruct themselves into a given domain-context. Within this environment, the generation of datasets, the fine-tuning process and finally the inference of a unique R.O.B.E.R.T. instance are all carried out as part of an automated pipeline.
Interacting with the environment to process sensory information, generate perceptions, and shape behavior engages neural networks in brain areas with highly varied representations, ranging from unimodal sensory cortices to higher-order association areas. Recent work suggests a much greater degree of commonality across areas, with distributed and modular networks present in both sensory and non-sensory areas during early development. However, it is currently unknown whether this initially common modular structure undergoes an equally common developmental trajectory, or whether such a modular functional organization persists in some areas—such as primary visual cortex—but not others. Here we examine the development of network organization across diverse cortical regions in ferrets of both sexes using in vivo widefield calcium imaging of spontaneous activity. We find that all regions examined, including both primary sensory cortices (visual, auditory, and somatosensory—V1, A1, and S1, respectively) and higher order association areas (prefrontal and posterior parietal cortices) exhibit a largely similar pattern of changes over an approximately 3 week developmental period spanning eye opening and the transition to predominantly externally-driven sensory activity. We find that both a modular functional organization and millimeter-scale correlated networks remain present across all cortical areas examined. These networks weakened over development in most cortical areas, but strengthened in V1. Overall, the conserved maintenance of modular organization across different cortical areas suggests a common pathway of network refinement, and suggests that a modular organization—known to encode functional representations in visual areas—may be similarly engaged in highly diverse brain areas.
Significance Different areas of the mature brain encode vastly different representations of the world. This study shows that a modular functional organization where nearby neurons participate in similar functional networks is shared across different brain areas not only during early development, but also as the brain matures where it remains a shared feature that shapes neural activity. The largely conserved trajectory of developmental changes across brain areas suggests that similar circuit mechanisms may drive this maturation. This implies that the large literature on developing cortical circuits, which is largely focused on sensory areas, may also apply more broadly, and that perturbations during development that impinge on any such shared mechanisms may produce deficits that extend across multiple brain systems.
This thesis will first introduce in more detail the Bayesian theory and its use in integrating multiple information sources. I will briefly talk about models and their relation to the dynamics of an environment, and how to combine multiple alternative models. Following that I will discuss the experimental findings on multisensory integration in humans and animals. I start with psychophysical results on various forms of tasks and setups, that show that the brain uses and combines information from multiple cues. Specifically, the discussion will focus on the finding that humans integrate this information in a way that is close to the theoretical optimal performance. Special emphasis will be put on results about the developmental aspects of cue integration, highlighting experiments that could show that children do not perform similar to the Bayesian predictions. This section also includes a short summary of experiments on how subjects handle multiple alternative environmental dynamics. I will also talk about neurobiological findings of cells receiving input from multiple receptors both in dedicated brain areas but also primary sensory areas. I will proceed with an overview of existing theories and computational models of multisensory integration. This will be followed by a discussion on reinforcement learning (RL). First I will talk about the original theory including the two different main approaches model-free and model-based reinforcement learning. The important variables will be introduced as well as different algorithmic implementations. Secondly, a short review on the mapping of those theories onto brain and behaviour will be given. I mention the most in uential papers that showed correlations between the activity in certain brain regions with RL variables, most prominently between dopaminergic neurons and temporal difference errors. I will try to motivate, why I think that this theory can help to explain the development of near-optimal cue integration in humans. The next main chapter will introduce our model that learns to solve the task of audio-visual orienting. Many of the results in this section have been published in [Weisswange et al. 2009b,Weisswange et al. 2011]. The model agent starts without any knowledge of the environment and acts based on predictions of rewards, which will be adapted according to the reward signaling the quality of the performed action. I will show that after training this model performs similarly to the prediction of a Bayesian observer. The model can also deal with more complex environments in which it has to deal with multiple possible underlying generating models (perform causal inference). In these experiments I use di#erent formulations of Bayesian observers for comparison with our model, and find that it is most similar to the fully optimal observer doing model averaging. Additional experiments using various alterations to the environment show the ability of the model to react to changes in the input statistics without explicitly representing probability distributions. I will close the chapter with a discussion on the benefits and shortcomings of the model. The thesis continues whith a report on an application of the learning algorithm introduced before to two real world cue integration tasks on a robotic head. For these tasks our system outperforms a commonly used approximation to Bayesian inference, reliability weighted averaging. The approximation is handy because of its computational simplicity, because it relies on certain assumptions that are usually controlled for in a laboratory setting, but these are often not true for real world data. This chapter is based on the paper [Karaoguz et al. 2011]. Our second modeling approach tries to address the neuronal substrates of the learning process for cue integration. I again use a reward based training scheme, but this time implemented as a modulation of synaptic plasticity mechanisms in a recurrent network of binary threshold neurons. I start the chapter with an additional introduction section to discuss recurrent networks and especially the various forms of neuronal plasticity that I will use in the model. The performance on a task similar to that of chapter 3 will be presented together with an analysis of the in uence of different plasticity mechanisms on it. Again benefits and shortcomings and the general potential of the method will be discussed. I will close the thesis with a general conclusion and some ideas about possible future work.
Programmable hardware in the form of FPGAs found its place in various high energy physics experiments over the past few decades. These devices provide highly parallel and fully configurable data transport, data formatting, and data processing capabilities with custom interfaces, even in rigid or constrained environments. Additionally, FPGA functionalities and the number of their logic resources have grown exponentially in the last few years, making FPGAs more and more suitable for complex data processing tasks. ALICE is one of the four main experiments at the LHC and specialized in the study of heavy-ion collisions. The readout chain of the ALICE detectors makes use of FPGAs at various places. The Read-Out Receiver Cards (RORCs) are one example of FPGA-based readout hardware, building the interface between the custom detector electronics and the commercial server nodes in the data processing clusters of the Data Acquisition (DAQ) system as well as the High Level Trigger (HLT). These boards are implemented as server plug-in cards with serial optical links towards the detectors. Experimental data is received via more than 500 optical links, already partly pre-processed in the FPGAs, and pushed towards the host machines. Computer clusters consisting of a few hundred nodes collect, aggregate, compress, reconstruct, and prepare the experimental data for permanent storage and later analysis. With the end of the first LHC run period in 2012 and the start of Run 2 in 2015, the DAQ and HLT systems were renewed and several detector components were upgraded for higher data rates and event rates. Increased detector link rates and obsolete host interfaces rendered it impossible to reuse the previous RORCs in Run 2.
This thesis describes the development, integration, and maintenance of the next generation of RORCs for ALICE in Run 2. A custom hardware platform, initially developed as a joint effort between the ALICE DAQ and HLT groups in the course of this work, found its place in the Run 2 readout systems of the ALICE and ATLAS experiments. The hardware fulfills all experiment requirements, matches its target performance, and has been running stable in the production systems since the start of Run 2. Firmware and software developments for the hardware evaluation, the design of the board, the mass production hardware tests, as well as the operation of the final board in the HLT, were carried out as part of this work. 74 boards were integrated into the HLT hardware and software infrastructure, with various firmware and software developments, to provide the main experimental data input and output interface of the HLT for Run 2. The hardware cluster finder, an FPGA-based data pre-processing core from the previous generation of RORCs, was ported to the new hardware. It has been improved and extended to meet the experimental requirements throughout Run 2. The throughput of this firmware component could be doubled and the algorithm extended, providing an improved noise rejection and an increased overall mean data compression ratio compared to its previous implementation. The hardware cluster finder forms a crucial component in the HLT data reconstruction and compression scheme with a processing performance of one board equivalent to around ten server nodes for comparable processing steps in software.
The work on the firmware development, especially on the hardware cluster finder, once more demonstrated that developing and maintaining data processing algorithms with the common low-level hardware description methods is tedious and time-consuming. Therefore, a high-level synthesis (HLS) hardware description method applying dataflow computing at an algorithmic level to FPGAs was evaluated in this context. The hardware cluster finder served as an example of a typical data processing algorithm in a high energy physics readout application. The existing and highly optimized low-level implementation provided a reference for comparisons in terms of throughput and resource usage. The cluster finder algorithm could be implemented in the dataflow description with comparably little effort, providing fast development cycles, compact code and at, the same time, simplified extension and maintenance options. The performance results in terms of throughput and resource usage are comparable to the manual implementation. The dataflow environment proved to be highly valuable for design space explorations. An integration of the dataflow description into the HLT firmware and software infrastructure could be demonstrated as a proof of concept. A high-level hardware description could ease both the design space exploration, the initial development, the maintenance, and the extension of hardware algorithms for high energy physics readout applications.
Particle identification is an important feature of the ALICE detector at the LHC. In particular, for particle identification via the time-of-flight technique, the precise determination of the event collision time represents an important ingredient of the quality of the measurement. In this paper, the different methods used for such a measurement in ALICE by means of the T0 and the TOF detectors are reviewed. Efficiencies, resolution and the improvement of the particle identification separation power of the methods used are presented for the different LHC colliding systems (pp , p-Pb and Pb-Pb) during the first period of data taking of LHC (Run 1).
Particle identification is an important feature of the ALICE detector at the LHC. In particular, for particle identification via the time-of-flight technique, the precise determination of the event collision time represents an important ingredient of the quality of the measurement. In this paper, the different methods used for such a measurement in ALICE by means of the T0 and the TOF detectors are reviewed. Efficiencies, resolution and the improvement of the particle identification separation power of the methods used are presented for the different LHC colliding systems (pp , p-Pb and Pb-Pb) during the first period of data taking of LHC (Run 1).
Particle identification is an important feature of the ALICE detector at the LHC. In particular, for particle identification via the time-of-flight technique, the precise determination of the event collision time represents an important ingredient of the quality of the measurement. In this paper, the different methods used for such a measurement in ALICE by means of the T0 and the TOF detectors are reviewed. Efficiencies, resolution and the improvement of the particle identification separation power of the methods used are presented for the different LHC colliding systems (pp , p-Pb and Pb-Pb) during the first period of data taking of LHC (Run 1).
Future operation of the CBM detector requires ultra-fast analysis of the continuous stream of data from all subdetector systems. Determining the inter-system time shifts among individual detector systems in the existing prototype experiment mCBM is an essential step for data processing and in particular for stable data taking. Based on the input of raw measurements from all detector systems, the corresponding time correlations can be obtained at digital level by evaluating the differences in time stamps. If the relevant systems are stable during data taking and sufficient digital measurements are available, the distribution of time differences should display a clear peak. Up to now, the outcome of the processed time differences is stored in histograms and the maximum peak is considered, after the evaluation of all timeslices of a run leading to significant run times. The results presented here demonstrate the stability of the synchronicity of mCBM systems. Furthermore it is illustrated that relatively small amounts of raw measurements are sufficient to evaluate corresponding time correlations among individual mCBM detectors, thus enabling fast online monitoring of them in future online data processing.
Poster presentation: The analysis of neuronal processes distributed across multiple cortical areas aims at the identification of interactions between signals recorded at different sites. Such interactions can be described by measuring the stability of phase angles in the case of oscillatory signals or other forms of signal dependencies for less regular signals. Before, however, any form of interaction can be analyzed at a given time and frequency, it is necessary to assess whether all potentially contributing signals are present. We have developed a new statistical procedure for the detection of coincident power in multiple simultaneously recorded analog signals, allowing the classification of events as 'non-accidental co-activation'. This method can effectively operate on single trials, each lasting only for a few seconds. Signals need to be transformed into time-frequency space, e.g. by applying a short-time Fourier transformation using a Gaussian window. The discrete wavelet transform (DWT) is used in order to weight the resulting power patterns according to their frequency. Subsequently, the weighted power patterns are binarized via applying a threshold. At this final stage, significant power coincidence is determined across all subgroups of channel combinations for individual frequencies by selecting the maximum ratio between observed and expected duration of co-activation as test statistic. The null hypothesis that the activity in each channel is independent from the activity in every other channel is simulated by independent, random rotation of the respective activity patterns. We applied this procedure to single trials of multiple simultaneously sampled local field potentials (LFPs) obtained from occipital, parietal, central and precentral areas of three macaque monkeys. Since their task was to use visual cues to perform a precise arm movement, co-activation of numerous cortical sites was expected. In a data set with 17 channels analyzed, up to 13 sites expressed simultaneous power in the range between 5 and 240 Hz. On average, more than 50% of active channels participated at least once in a significant power co-activation pattern (PCP). Because the significance of such PCPs can be evaluated at the level of single trials, we are confident that this procedure is useful to study single trial variability with sufficient accuracy that much of the behavioral variability can be explained by the dynamics of the underlying distributed neuronal processes.
Human lymph nodes play a central part of immune defense against infection agents and tumor cells. Lymphoid follicles are compartments of the lymph node which are spherical, mainly filled with B cells. B cells are cellular components of the adaptive immune systems. In the course of a specific immune response, lymphoid follicles pass different morphological differentiation stages. The morphology and the spatial distribution of lymphoid follicles can be sometimes associated to a particular causative agent and development stage of a disease. We report our new approach for the automatic detection of follicular regions in histological whole slide images of tissue sections immuno-stained with actin. The method is divided in two phases: (1) shock filter-based detection of transition points and (2) segmentation of follicular regions. Follicular regions in 10 whole slide images were manually annotated by visual inspection, and sample surveys were conducted by an expert pathologist. The results of our method were validated by comparing with the manual annotation. On average, we could achieve a Zijbendos similarity index of 0.71, with a standard deviation of 0.07.
Paging is one of the most prominent problems in the field of online algorithms. We have to serve a sequence of page requests using a cache that can hold up to k pages. If the currently requested page is in cache we have a cache hit, otherwise we say that a cache miss occurs, and the requested page needs to be loaded into the cache. The goal is to minimize the number of cache misses by providing a good page-replacement strategy. This problem is part of memory-management when data is stored in a two-level memory hierarchy, more precisely a small and fast memory (cache) and a slow but large memory (disk). The most important application area is the virtual memory management of operating systems. Accessed pages are either already in the RAM or need to be loaded from the hard disk into the RAM using expensive I/O. The time needed to access the RAM is insignificant compared to an I/O operation which takes several milliseconds.
The traditional evaluation framework for online algorithms is competitive analysis where the online algorithm is compared to the optimal offline solution. A shortcoming of competitive analysis consists of its too pessimistic worst-case guarantees. For example LRU has a theoretical competitive ratio of k but in practice this ratio rarely exceeds the value 4.
Reducing the gap between theory and practice has been a hot research issue during the last years. More recent evaluation models have been used to prove that LRU is an optimal online algorithm or part of a class of optimal algorithms respectively, which was motivated by the assumption that LRU is one of the best algorithms in practice. Most of the newer models make LRU-friendly assumptions regarding the input, thus not leaving much room for new algorithms.
Only few works in the field of online paging have introduced new algorithms which can compete with LRU as regards the small number of cache misses.
In the first part of this thesis we study strongly competitive randomized paging algorithms, i.e. algorithms with optimal competitive guarantees. Although the tight bound for the competitive ratio has been known for decades, current algorithms matching this bound are complex and have high running times and memory requirements. We propose the algorithm OnlineMin which processes a page request in O(log k/log log k) time in the worst case. The best previously known solution requires O(k^2) time.
Usually the memory requirement of a paging algorithm is measured by the maximum number of pages that the algorithm keeps track of. Any algorithm stores information about the k pages in the cache. In addition it can also store information about pages not in cache, denoted bookmarks. We answer the open question of Bein et al. '07 whether strongly competitive randomized paging algorithms using only o(k) bookmarks exist or not. To do so we modify the Partition algorithm of McGeoch and Sleator '85 which has an unbounded bookmark complexity, and obtain Partition2 which uses O(k/log k) bookmarks.
In the second part we extract ideas from theoretical analysis of randomized paging algorithms in order to design deterministic algorithms that perform well in practice. We refine competitive analysis by introducing the attack rate
parameter r, which ranges between 1 and k. We show that r is a tight bound on the competitive ratio of deterministic algorithms.
We give empirical evidence that r is usually much smaller than k and thus r-competitive algorithms have a reasonable performance on real-world traces. By introducing the r-competitive priority-based algorithm class OnOPT we obtain a collection of promising algorithms to beat the LRU-standard. We single out the new algorithm RDM and show that it outperforms LRU and some of its variants on a wide range of real-world traces.
Since RDM is more complex than LRU one may think at first sight that the gain in terms of lowering the number of cache misses is ruined by high runtime for processing pages. We engineer a fast implementation of RDM, and compare it
to LRU and the very fast FIFO algorithm in an overall evaluation scheme, where we measure the runtime of the algorithms and add penalties for each cache miss.
Experimental results show that for realistic penalties RDM still outperforms these two algorithms even if we grant the competitors an idealistic runtime of 0.
The thesis in general deals with CORBA, the Common Object Request Broker Architecture. More specifically, it takes a look at the server-side, where object adapters exist to aid the developer in implementing objects and in dealing with request processing. The new Portable Object Adapter was recently added to the CORBA 2.2 standard. My task was the implementation of the POA in MICO and the examination if (a) the POA specification is sensible and (b) in which areas it improves over the old Basic Object Adapter. After introducing distributed platforms in general and CORBA in particular, the thesis' main two chapters are a detailed abstract examination ("Design") of the POA design and their relization ("Implementation"), highlighting the potential trouble spots, persistence and collocation.
Syntactic coindexing restrictions are by now known to be of central importance to practical anaphor resolution approaches. Since, in particular due to structural ambiguity, the assumption of the availability of a unique syntactic reading proves to be unrealistic, robust anaphor resolution relies on techniques to overcome this deficiency.
This paper describes the ROSANA approach, which generalizes the verification of coindexing restrictions in order to make it applicable to the deficient syntactic descriptions that are provided by a robust state-of-the-art parser. By a formal evaluation on two corpora that differ with respect to text genre and domain, it is shown that ROSANA achieves high-quality robust coreference resolution. Moreover, by an in-depth analysis, it is proven that the robust implementation of syntactic disjoint reference is nearly optimal. The study reveals that, compared with approaches that rely on shallow preprocessing, the largely nonheuristic disjoint reference algorithmization opens up the possibility/or a slight improvement. Furthermore, it is shown that more significant gains are to be expected elsewhere, particularly from a text-genre-specific choice of preference strategies.
The performance study of the ROSANA system crucially rests on an enhanced evaluation methodology for coreference resolution systems, the development of which constitutes the second major contribution o/the paper. As a supplement to the model-theoretic scoring scheme that was developed for the Message Understanding Conference (MUC) evaluations, additional evaluation measures are defined that, on one hand, support the developer of anaphor resolution systems, and, on the other hand, shed light on application aspects of pronoun interpretation.
We study the descriptional complexity of cellular automata (CA), a parallel model of computation. We show that between one of the simplest cellular models, the realtime-OCA. and "classical" models like deterministic finite automata (DFA) or pushdown automata (PDA), there will be savings concerning the size of description not bounded by any recursive function, a so-called nonrecursive trade-off. Furthermore, nonrecursive trade-offs are shown between some restricted classes of cellular automata. The set of valid computations of a Turing machine can be recognized by a realtime-OCA. This implies that many decidability questions are not even semi decidable for cellular automata. There is no pumping lemma and no minimization algorithm for cellular automata.
Mit der Smart Learning Infrastruktur wurde ein neuartiges didaktisches Konzept für Kurse in der Weiterbildung entwickelt. Diese Infrastruktur ist vielfältig anwendbar. Erste Analysen von Kursen zeigen, dass TeilnehmerInnen, die alle Übungen korrekt abgearbeitet haben, eine bessere Note erreichen als die Durchschnittsnote. Dieser Beitrag beschreibt ein Konzept für ein Gamification-Modul, welches mit spielerischen Elementen möglichst frühzeitig dazu animiert, alle Übungen eines Kurses korrekt und mit Verstand abzuarbeiten.
Wie eine "Heilslehre" überzieht der Begriff "Digitalisierung" fast alle Lebensbereiche – natürlich auch den Bildungsbereich. Gerade wir Informatiker*innen sind gefordert, diese Wege der Bildungstransformation mitzugestalten. Wir zusammen mit den Erziehungswissenschaftler*innen und Psychologen*innen müssen identifizieren, aufzeigen und vorbildlich umsetzen, was sinnvoll und möglich ist. Wir sind diejenigen, die die Bedingungen des Gelingens und auch die der Irrwege erforschen und aufzeigen müssen. Digitalisierungswahnsinn brauchen wir nicht!
Die 16. Jahrestagung DeLFI 2018 der Fachgruppe eLearning der Gesellschaft für Informatik e. V. findet vom 10. bis 13.September 2018 an der Johann Wolfgang Goethe – Universität, Frankfurt am Main statt, gemeinsam mit der 8. Tagung für Hochschuldidaktik der Informatik HDI 2018. ...
Algorithms for the Maximum Cardinality Matching Problem which greedily add edges to the solution enjoy great popularity. We systematically study strengths and limitations of such algorithms, in particular of those which consider node degree information to select the next edge. Concentrating on nodes of small degree is a promising approach: it was shown, experimentally and analytically, that very good approximate solutions are obtained for restricted classes of random graphs. Results achieved under these idealized conditions, however, remained unsupported by statements which depend on less optimistic assumptions.
The KarpSipser algorithm and 1-2-Greedy, which is a simplified variant of the well-known MinGreedy algorithm, proceed as follows. In each step, if a node of degree one (resp. at most two) exists, then an edge incident with a minimum degree node is picked, otherwise an arbitrary edge is added to the solution.
We analyze the approximation ratio of both algorithms on graphs of degree at most D. Families of graphs are known for which the expected approximation ratio converges to 1/2 as D grows to infinity, even if randomization against the worst case is used. If randomization is not allowed, then we show the following convergence to 1/2: the 1-2-Greedy algorithm achieves approximation ratio (D-1)/(2D-3); if the graph is bipartite, then the more restricted KarpSipser algorithm achieves the even stronger factor D/(2D-2). These guarantees set both algorithms apart from other famous matching heuristics like e.g. Greedy or MRG: these algorithms depend on randomization to break the 1/2-barrier even for paths with D=2. Moreover, for any D our guarantees are strictly larger than the best known bounds on the expected performance of the randomized variants of Greedy and MRG.
To investigate whether KarpSipser or 1-2-Greedy can be refined to achieve better performance, or be simplified without loss of approximation quality, we systematically study entire classes of deterministic greedy-like algorithms for matching. Therefore we employ the adaptive priority algorithm framework by Borodin, Nielsen, and Rackoff: in each round, an adaptive priority algorithm requests one or more edges by formulating their properties---like e.g. "is incident with a node of minimum degree"---and adds the received edges to the solution. No constraints on time and space usage are imposed, hence an adaptive priority algorithm is restricted only by its nature of picking edges in a greedy-like fashion. If an adaptive priority algorithm requests edges by processing degree information, then we show that it does not surpass the performance of KarpSipser: our D/(2D-2)-guarantee for bipartite graphs is tight and KarpSipser is optimal among all such "degree-sensitive" algorithms even though it uses degree information merely to detect degree-1 nodes. Moreover, we show that if degrees of both nodes of an edge may be processed, like e.g. the Double-MinGreedy algorithm does, then the performance of KarpSipser can only be increased marginally, if at all. Of special interest is the capability of requesting edges not only by specifying the degree of a node but additionally its set of neighbors. This enables an adaptive priority algorithm to "traverse" the input graph. We show that on general degree-bounded graphs no such algorithm can beat factor (D-1)/(2D-3). Hence our bound for 1-2-Greedy is tight and this algorithm performs optimally even though it ignores neighbor information. Furthermore, we show that an adaptive priority algorithm deteriorates to approximation ratio exactly 1/2 if it does not request small degree nodes. This tremendous decline of approximation quality happens for graphs on which 1-2-Greedy and KarpSipser perform optimally, namely paths with D=2. Consequently, requesting small degree nodes is vital to beat factor 1/2.
Summarizing, our results show that 1-2-Greedy and KarpSipser stand out from known and hypothetical algorithms as an intriguing combination of both approximation quality and conceptual simplicity.
In this talk we presented a novel technique, based on Deep Learning, to determine the impact parameter of nuclear collisions at the CBM experiment. PointNet based Deep Learning models are trained on UrQMD followed by CBMRoot simulations of Au+Au collisions at 10 AGeV to reconstruct the impact parameter of collisions from raw experimental data such as hits of the particles in the detector planes, tracks reconstructed from the hits or their combinations. The PointNet models can perform fast, accurate, event-by-event impact parameter determination in heavy ion collision experiments. They are shown to outperform a simple model which maps the track multiplicity to the impact parameter. While conventional methods for centrality classification merely provide an expected impact parameter distribution for a given centrality class, the PointNet models predict the impact parameter from 2–14 fm on an event-by-event basis with a mean error of −0.33 to 0.22 fm.
FIFO is the most prominent queueing strategy due to its simplicity and the fact that it only works with local information. Its analysis within the adversarial queueing theory however has shown, that there are networks that are not stable under the FIFO protocol, even at arbitrarily low rate. On the other hand there are networks that are universally stable, i.e., they are stable under every greedy protocol at any rate r < 1. The question as to which networks are stable under the FIFO protocol arises naturally. We offer the first polynomial time algorithm for deciding FIFO stability and simple-path FIFO stability of a directed network, answering an open question posed in [1, 4]. It turns out, that there are networks, that are FIFO stable but not universally stable, hence FIFO is not a worst case protocol in this sense. Our characterization of FIFO stability is constructive and disproves an open characterization in [4].
Various static analyses of functional programming languages that permit infinite data structures make use of set constants like Top, Inf, and Bot, denoting all terms, all lists not eventually ending in Nil, and all non-terminating programs, respectively. We use a set language that permits union, constructors and recursive definition of set constants with a greatest fixpoint semantics in the set of all, also infinite, computable trees, where all term constructors are non-strict. This internal report proves decidability, in particular DEXPTIME-completeness, of inclusion of co-inductively defined sets by using algorithms and results from tree automata and set constraints, and contains detailed proofs. The test for set inclusion is required by certain strictness analysis algorithms in lazy functional programming languages and could also be the basis for further set-based analyses.
Static analysis of different non-strict functional programming languages makes use of set constants like Top, Inf, and Bot denoting all expressions, all lists without a last Nil as tail, and all non-terminating programs, respectively. We use a set language that permits union, constructors and recursive definition of set constants with a greatest fixpoint semantics. This paper proves decidability, in particular EXPTIMEcompleteness, of subset relationship of co-inductively defined sets by using algorithms and results from tree automata. This shows decidability of the test for set inclusion, which is required by certain strictness analysis algorithms in lazy functional programming languages.
It is well known that first order uni cation is decidable, whereas second order and higher order unification is undecidable. Bounded second order unification (BSOU) is second order unification under the restriction that only a bounded number of holes in the instantiating terms for second order variables is permitted, however, the size of the instantiation is not restricted. In this paper, a decision algorithm for bounded second order unification is described. This is the fist non-trivial decidability result for second order unification, where the (finite) signature is not restricted and there are no restrictions on the occurrences of variables. We show that the monadic second order unification (MSOU), a specialization of BSOU is in sum p s. Since MSOU is related to word unification, this is compares favourably to the best known upper bound NEXPTIME (and also to the announced upper bound PSPACE) for word unification. This supports the claim that bounded second order unification is easier than context unification, whose decidability is currently an open question.
The knowledge of the material budget with a high precision is fundamental for measurements of direct photon production using the photon conversion method due to its direct impact on the total systematic uncertainty. Moreover, it influences many aspects of the charged-particle reconstruction performance. In this article, two procedures to determine data-driven corrections to the material-budget description in ALICE simulation software are developed. One is based on the precise knowledge of the gas composition in the Time Projection Chamber. The other is based on the robustness of the ratio between the produced number of photons and charged particles, to a large extent due to the approximate isospin symmetry in the number of produced neutral and charged pions. Both methods are applied to ALICE data allowing for a reduction of the overall material budget systematic uncertainty from 4.5% down to 2.5%. Using these methods, a locally correct material budget is also achieved. The two proposed methods are generic and can be applied to any experiment in a similar fashion.
The knowledge of the material budget with a high precision is fundamental for measurements of direct photon production using the photon conversion method due to its direct impact on the total systematic uncertainty. Moreover, it influences many aspects of the charged-particle reconstruction performance. In this article, two procedures to determine data-driven corrections to the material-budget description in ALICE simulation software are developed. One is based on the precise knowledge of the gas composition in the Time Projection Chamber. The other is based on the robustness of the ratio between the produced number of photons and charged particles, to a large extent due to the approximate isospin symmetry in the number of produced neutral and charged pions. Both methods are applied to ALICE data allowing for a reduction of the overall material budget systematic uncertainty from 4.5% down to 2.5%. Using these methods, a locally correct material budget is also achieved. The two proposed methods are generic and can be applied to any experiment in a similar fashion.
The knowledge of the material budget with a high precision is fundamental for measurements of direct photon production using the photon conversion method due to its direct impact on the total systematic uncertainty. Moreover, it influences many aspects of the charged-particle reconstruction performance. In this article, two procedures to determine data-driven corrections to the material-budget description in ALICE simulation software are developed. One is based on the precise knowledge of the gas composition in the Time Projection Chamber. The other is based on the robustness of the ratio between the produced number of photons and charged particles, to a large extent due to the approximate isospin symmetry in the number of produced neutral and charged pions. Both methods are applied to ALICE data allowing for a reduction of the overall material budget systematic uncertainty from 4.5% down to 2.5%. Using these methods, a locally correct material budget is also achieved. The two proposed methods are generic and can be applied to any experiment in a similar fashion.
Data structures and advanced models of computation on big data : report from Dagstuhl seminar 14091
(2014)
This report documents the program and the outcomes of Dagstuhl Seminar 14091 "Data Structures and Advanced Models of Computation on Big Data". In today's computing environment vast amounts of data are processed, exchanged and analyzed. The manner in which information is stored profoundly influences the efficiency of these operations over the data. In spite of the maturity of the field many data structuring problems are still open, while new ones arise due to technological advances.
The seminar covered both recent advances in the "classical" data structuring topics as well as new models of computation adapted to modern architectures, scientific studies that reveal the need for such models, applications where large data sets play a central role, modern computing platforms for very large data, and new data structures for large data in modern architectures.
The extended abstracts included in this report contain both recent state of the art advances and lay the foundation for new directions within data structures research.
Data driven automatic model selection and parameter adaptation – a case study for septic shock
(2004)
In bioinformatics, biochemical pathways can be modeled by many differential equations. It is still an open problem how to fit the huge amount of parameters of the equations to the available data. Here, the approach of systematically learning the parameters is necessary. This paper propose as model selection criterion the least complex description of the observed data by the model, the minimum description length. For the small, but important example of inflammation modeling the performance of the approach is evaluated.
Dancing is an activity that positively enhances the mood of people that consists of feeling the music and expressing it in rhythmic movements with the body. Learning how to dance can be challenging because it requires proper coordination and understanding of rhythm and beat. In this paper, we present the first implementation of the Dancing Coach (DC), a generic system designed to support the practice of dancing steps, which in its current state supports the practice of basic salsa dancing steps. However, the DC has been designed to allow the addition of more dance styles. We also present the first user evaluation of the DC, which consists of user tests with 25 participants. Results from the user test show that participants stated they had learned the basic salsa dancing steps, to move to the beat and body coordination in a fun way. Results also point out some direction on how to improve the future versions of the DC.
Background: In the context of the investigation of the quark gluon plasma produced in heavy-ion collisions, hadrons containing heavy (charm or beauty) quarks play a special role for the characterization of the hot and dense medium created in the interaction. The measurement of the production of charm and beauty hadrons in proton–proton collisions, besides providing the necessary reference for the studies in heavy-ion reactions, constitutes an important test of perturbative quantum chromodynamics (pQCD) calculations. Heavy-flavor production in proton–nucleus collisions is sensitive to the various effects related to the presence of nuclei in the colliding system, commonly denoted cold-nuclear-matter effects. Most of these effects are expected to modify open-charm production at low transverse momenta (pT) and, so far, no measurement of D-meson production down to zero transverse momentum was available at mid-rapidity at the energies attained at the CERN Large Hadron Collider (LHC).
Purpose: The measurements of the production cross sections of promptly produced charmed mesons in p-Pb collisions at the LHC down to pT=0 and the comparison to the results from pp interactions are aimed at the assessment of cold-nuclear-matter effects on open-charm production, which is crucial for the interpretation of the results from Pb-Pb collisions.
Methods: The prompt charmed mesons D0,D+,D*+, and D+s were measured at mid-rapidity in p-Pb collisions at a center-of-mass energy per nucleon pair √sNN=5.02 TeV with the ALICE detector at the LHC. D mesons were reconstructed from their decays D0→K−π+,D+→K−π+π+, D*+→D0π+,D+s→ϕπ+→K−K+π+, and their charge conjugates, using an analysis method based on the selection of decay topologies displaced from the interaction vertex. In addition, the prompt D0 production cross section was measured in pp collisions at √s=7 TeV and p-Pb collisions at √sNN=5.02 TeV down to pT=0 using an analysis technique that is based on the estimation and subtraction of the combinatorial background, without reconstruction of the D0 decay vertex.
Results: The production cross section in pp collisions is described within uncertainties by different implementations of pQCD calculations down to pT=0. This allowed also a determination of the total c¯c production cross section in pp collisions, which is more precise than previous ALICE measurements because it is not affected by uncertainties owing to the extrapolation to pT=0. The nuclear modification factor RpPb(pT), defined as the ratio of the pT-differential D meson cross section in p-Pb collisions and that in pp collisions scaled by the mass number of the Pb nucleus, was calculated for the four D-meson species and found to be compatible with unity within uncertainties. The results are compared to theoretical calculations that include cold-nuclear-matter effects and to transport model calculations incorporating the interactions of charm quarks with an expanding deconfined medium.
Conclusions: These measurements add experimental evidence that the modification of the D-meson transverse momentum distributions observed in Pb–Pb collisions with respect to pp interactions is due to strong final-state effects induced by the interactions of the charm quarks with the hot and dense partonic medium created in ultrarelativistic heavy-ion collisions. The current precision of the measurement does not allow us to draw conclusions on the role of the different cold-nuclear-matter effects and on the possible presence of additional hot-medium effects in p-Pb collisions. However, the analysis technique without decay-vertex reconstruction, applied on future larger data samples, should provide access to the physics-rich range down to pT=0.
The production cross sections of the prompt charmed mesons D0, D+, D∗+ and Ds were measured at mid-rapidity in p-Pb collisions at a centre-of-mass energy per nucleon pair sNN−−−√=5.02 TeV with the ALICE detector at the LHC. D mesons were reconstructed from their decays D0→K−π+, D+→K−π+π+, D∗+→D0π+, D+s→ϕπ+→K−K+π+, and their charge conjugates. The pT-differential production cross sections were measured at mid-rapidity in the interval 1<pT<24 GeV/c for D0, D+ and D∗+ mesons and in 2<pT<12 GeV/c for Ds mesons, using an analysis method based on the selection of decay topologies displaced from the interaction vertex. The production cross sections of the D0, D+ and D∗+ mesons were also measured in three pT intervals as a function of the rapidity ycms in the centre-of-mass system in −1.26<ycms<0.34. In addition, the prompt D0 cross section was measured in pp collisions at s√=7 TeV and p-Pb collisions at sNN−−−√=5.02 TeV down to pT=0 using an analysis technique that is based on the estimation and subtraction of the combinatorial background, without reconstruction of the D0 decay vertex. The nuclear modification factor RpPb(pT), defined as the ratio of the pT-differential D-meson cross section in p-Pb collisions and that in pp collisions scaled by the mass number of the Pb nucleus, was calculated for the four D-meson species and found to be compatible with unity within experimental uncertainties. The results are compared to theoretical calculations that include cold-nuclear-matter effects and to transport model calculations incorporating the interactions of charm quarks with an expanding deconfined medium.
The production cross sections of the prompt charmed mesons D0, D+, D∗+ and Ds were measured at mid-rapidity in p-Pb collisions at a centre-of-mass energy per nucleon pair sNN−−−√=5.02 TeV with the ALICE detector at the LHC. D mesons were reconstructed from their decays D0→K−π+, D+→K−π+π+, D∗+→D0π+, D+s→ϕπ+→K−K+π+, and their charge conjugates. The pT-differential production cross sections were measured at mid-rapidity in the interval 1<pT<24 GeV/c for D0, D+ and D∗+ mesons and in 2<pT<12 GeV/c for Ds mesons, using an analysis method based on the selection of decay topologies displaced from the interaction vertex. The production cross sections of the D0, D+ and D∗+ mesons were also measured in three pT intervals as a function of the rapidity ycms in the centre-of-mass system in −1.26<ycms<0.34. In addition, the prompt D0 cross section was measured in pp collisions at s√=7 TeV and p-Pb collisions at sNN−−−√=5.02 TeV down to pT=0 using an analysis technique that is based on the estimation and subtraction of the combinatorial background, without reconstruction of the D0 decay vertex. The nuclear modification factor RpPb(pT), defined as the ratio of the pT-differential D-meson cross section in p-Pb collisions and that in pp collisions scaled by the mass number of the Pb nucleus, was calculated for the four D-meson species and found to be compatible with unity within experimental uncertainties. The results are compared to theoretical calculations that include cold-nuclear-matter effects and to transport model calculations incorporating the interactions of charm quarks with an expanding deconfined medium.
The azimuthal anisotropy coefficient v2 of prompt D0, D+, D∗+ and D+s mesons was measured in mid-central (30-50% centrality class) Pb-Pb collisions at a centre-of-mass energy per nucleon pair sNN−−−√=5.02 TeV, with the ALICE detector at the LHC. The D mesons were reconstructed via their hadronic decays at mid-rapidity, |y|<0.8, in the transverse momentum interval 1<pT<24 GeV/c. The measured D-meson v2 has similar values as that of charged pions. The D+s v2, measured for the first time, is found to be compatible with that of non-strange D mesons. The measurements are compared with theoretical calculations of charm-quark transport in a hydrodynamically expanding medium and have the potential to constrain medium parameters.
The azimuthal anisotropy coefficient v2 of prompt D0, D+, D∗+ and D+s mesons was measured in mid-central (30-50% centrality class) Pb-Pb collisions at a centre-of-mass energy per nucleon pair sNN−−−√=5.02 TeV, with the ALICE detector at the LHC. The D mesons were reconstructed via their hadronic decays at mid-rapidity, |y|<0.8, in the transverse momentum interval 1<pT<24 GeV/c. The measured D-meson v2 has similar values as that of charged pions. The D+s v2, measured for the first time, is found to be compatible with that of non-strange D mesons. The measurements are compared with theoretical calculations of charm-quark transport in a hydrodynamically expanding medium and have the potential to constrain medium parameters.
The azimuthal anisotropy coefficient v2 of prompt D0, D+, D∗+ and D+s mesons was measured in mid-central (30-50% centrality class) Pb-Pb collisions at a centre-of-mass energy per nucleon pair sNN−−−√=5.02 TeV, with the ALICE detector at the LHC. The D mesons were reconstructed via their hadronic decays at mid-rapidity, |y|<0.8, in the transverse momentum interval 1<pT<24 GeV/c. The measured D-meson v2 has similar values as that of charged pions. The D+s v2, measured for the first time, is found to be compatible with that of non-strange D mesons. The measurements are compared with theoretical calculations of charm-quark transport in a hydrodynamically expanding medium and have the potential to constrain medium parameters.e
We present new concepts to integrate logic synthesis and physical design. Our methodology uses general Boolean transformations as known from technology-independent synthesis, and a recursive bi-partitioning placement algorithm. In each partitioning step, the precision of the layout data increases. This allows effective guidance of the logic synthesis operations for cycle time optimization. An additional advantage of our approach is that no complicated layout corrections are needed when the netlist is changed.
CRFVoter : gene and protein related object recognition using a conglomerate of CRF-based tools
(2019)
Background: Gene and protein related objects are an important class of entities in biomedical research, whose identification and extraction from scientific articles is attracting increasing interest. In this work, we describe an approach to the BioCreative V.5 challenge regarding the recognition and classification of gene and protein related objects. For this purpose, we transform the task as posed by BioCreative V.5 into a sequence labeling problem. We present a series of sequence labeling systems that we used and adapted in our experiments for solving this task. Our experiments show how to optimize the hyperparameters of the classifiers involved. To this end, we utilize various algorithms for hyperparameter optimization. Finally, we present CRFVoter, a two-stage application of Conditional Random Field (CRF) that integrates the optimized sequence labelers from our study into one ensemble classifier.
Results: We analyze the impact of hyperparameter optimization regarding named entity recognition in biomedical research and show that this optimization results in a performance increase of up to 60%. In our evaluation, our ensemble classifier based on multiple sequence labelers, called CRFVoter, outperforms each individual extractor’s performance. For the blinded test set provided by the BioCreative organizers, CRFVoter achieves an F-score of 75%, a recall of 71% and a precision of 80%. For the GPRO type 1 evaluation, CRFVoter achieves an F-Score of 73%, a recall of 70% and achieved the best precision (77%) among all task participants.
Conclusion: CRFVoter is effective when multiple sequence labeling systems are to be used and performs better then the individual systems collected by it.
The prevention of credit card fraud is an important application for prediction techniques. One major obstacle for using neural network training techniques is the high necessary diagnostic quality: Since only one financial transaction of a thousand is invalid no prediction success less than 99.9% is acceptable. Due to these credit card transaction proportions complete new concepts had to be developed and tested on real credit card data. This paper shows how advanced data mining techniques and neural network algorithm can be combined successfully to obtain a high fraud coverage combined with a low false alarm rate.
This note shows that in non-deterministic extended lambda calculi with letrec, the tool of applicative (bi)simulation is in general not usable for contextual equivalence, by giving a counterexample adapted from data flow analysis. It also shown that there is a flaw in a lemma and a theorem concerning finite simulation in a conference paper by the first two authors.
Correlated event-by-event fluctuations of flow harmonics in Pb–Pb collisions at √sNN = 2.76 TeV
(2016)
We report the measurements of correlations between event-by-event fluctuations of amplitudes of anisotropic flow harmonics in nucleus-nucleus collisions, obtained for the first time using a new analysis method based on multiparticle cumulants in mixed harmonics. This novel method is robust against systematic biases originating from non-flow effects and by construction any dependence on symmetry planes is eliminated. We demonstrate that correlations of flow harmonics exhibit a better sensitivity to medium properties than the individual flow harmonics. The new measurements are performed in Pb-Pb collisions at the centre-of-mass energy per nucleon pair of sNN−−−√=2.76 TeV by the ALICE experiment at the Large Hadron Collider (LHC). The centrality dependence of correlation between event-by-event fluctuations of the elliptic, v2, and quadrangular, v4, flow harmonics, as well as of anti-correlation between v2 and triangular, v3, flow harmonics are presented. The results cover two different regimes of the initial state configurations: geometry-dominated (in mid-central collisions) and fluctuation-dominated (in the most central collisions). Comparisons are made to predictions from MC-Glauber, viscous hydrodynamics, AMPT and HIJING models. Together with the existing measurements of individual flow harmonics the presented results provide further constraints on initial conditions and the transport properties of the system produced in heavy-ion collisions.
Correlated event-by-event fluctuations of flow harmonics in Pb–Pb collisions at √sNN = 2.76 TeV
(2016)
We report the measurements of correlations between event-by-event fluctuations of amplitudes of anisotropic flow harmonics in nucleus-nucleus collisions, obtained for the first time using a new analysis method based on multiparticle cumulants in mixed harmonics. This novel method is robust against systematic biases originating from non-flow effects and by construction any dependence on symmetry planes is eliminated. We demonstrate that correlations of flow harmonics exhibit a better sensitivity to medium properties than the individual flow harmonics. The new measurements are performed in Pb-Pb collisions at the centre-of-mass energy per nucleon pair of sNN−−−√=2.76 TeV by the ALICE experiment at the Large Hadron Collider (LHC). The centrality dependence of correlation between event-by-event fluctuations of the elliptic, v2, and quadrangular, v4, flow harmonics, as well as of anti-correlation between v2 and triangular, v3, flow harmonics are presented. The results cover two different regimes of the initial state configurations: geometry-dominated (in mid-central collisions) and fluctuation-dominated (in the most central collisions). Comparisons are made to predictions from MC-Glauber, viscous hydrodynamics, AMPT and HIJING models. Together with the existing measurements of individual flow harmonics the presented results provide further constraints on initial conditions and the transport properties of the system produced in heavy-ion collisions.
Correlated event-by-event fluctuations of flow harmonics in Pb–Pb collisions at √sNN = 2.76 TeV
(2016)
We report the measurements of correlations between event-by-event fluctuations of amplitudes of anisotropic flow harmonics in nucleus-nucleus collisions, obtained for the first time using a new analysis method based on multiparticle cumulants in mixed harmonics. This novel method is robust against systematic biases originating from non-flow effects and by construction any dependence on symmetry planes is eliminated. We demonstrate that correlations of flow harmonics exhibit a better sensitivity to medium properties than the individual flow harmonics. The new measurements are performed in Pb-Pb collisions at the centre-of-mass energy per nucleon pair of sNN−−−√=2.76 TeV by the ALICE experiment at the Large Hadron Collider (LHC). The centrality dependence of correlation between event-by-event fluctuations of the elliptic, v2, and quadrangular, v4, flow harmonics, as well as of anti-correlation between v2 and triangular, v3, flow harmonics are presented. The results cover two different regimes of the initial state configurations: geometry-dominated (in mid-central collisions) and fluctuation-dominated (in the most central collisions). Comparisons are made to predictions from MC-Glauber, viscous hydrodynamics, AMPT and HIJING models. Together with the existing measurements of individual flow harmonics the presented results provide further constraints on initial conditions and the transport properties of the system produced in heavy-ion collisions.
This paper extends the internal frank report 28 as follows: It is shown that for a call-by-need lambda calculus LRCCP-Lambda extending the calculus LRCC-Lambda by por, i.e in a lambda-calculus with letrec, case, constructors, seq and por, copying can be done without restrictions, and also that call-by-need and call-by-name strategies are equivalent w.r.t. contextual equivalence.
Call-by-need lambda calculi with letrec provide a rewritingbased operational semantics for (lazy) call-by-name functional languages. These calculi model the sharing behavior during evaluation more closely than let-based calculi that use a fixpoint combinator. In a previous paper we showed that the copy-transformation is correct for the small calculus LR-Lambda. In this paper we demonstrate that the proof method based on a calculus on infinite trees for showing correctness of instantiation operations can be extended to the calculus LRCC-Lambda with case and constructors, and show that copying at compile-time can be done without restrictions. We also show that the call-by-need and call-by-name strategies are equivalent w.r.t. contextual equivalence. A consequence is correctness of all the transformations like instantiation, inlining, specialization and common subexpression elimination in LRCC-Lambda. We are confident that the method scales up for proving correctness of copy-related transformations in non-deterministic lambda calculi if restricted to "deterministic" subterms.
A concurrent implementation of software transactional memory in Concurrent Haskell using a call-by-need functional language with processes and futures is given. The description of the small-step operational semantics is precise and explicit, and employs an early abort of conflicting transactions. A proof of correctness of the implementation is given for a contextual semantics with may- and should-convergence. This implies that our implementation is a correct evaluator for an abstract specification equipped with a big-step semantics.
A concurrent implementation of software transactional memory in Concurrent Haskell using a call-by-need functional language with processes and futures is given. The description of the small-step operational semantics is precise and explicit, and employs an early abort of conflicting transactions. A proof of correctness of the implementation is given for a contextual semantics with may- and should-convergence. This implies that our implementation is a correct evaluator for an abstract specification equipped with a big-step semantics.