890 research outputs found
A Solution to Wiehagen's Thesis
No full textWiehagen's Thesis in Inductive Inference (1991) essentially states that, for each learning criterion, learning can be done in a normalized, enumerative way. The thesis was not a formal statement and thus did not allow for a formal proof, but support was given by examples of a number of different learning criteria that can be learned enumeratively.
Building on recent formalizations of learning criteria, we are now able to formalize Wiehagen's Thesis. We prove the thesis for a wide range of learning criteria, including many popular criteria from the literature. We also show the limitations of the thesis by giving four learning criteria for which the thesis does not hold (and, in two cases, was probably not meant to hold). Beyond the original formulation of the thesis, we also prove stronger versions which allow for many corollaries relating to strongly decisive and conservative learning
Towards an Atlas of Computational Learning Theory
No full textA major part of our knowledge about Computational Learning stems from comparisons of the learning power of different learning criteria. These comparisons inform about trade-offs between learning restrictions and, more generally, learning settings; furthermore, they inform about what restrictions can be observed without losing learning power.
With this paper we propose that one main focus of future research in Computational Learning should be on a structured approach to determine the relations of different learning criteria. In particular, we propose that, for small sets of learning criteria, all pairwise relations should be determined; these relations can then be easily depicted as a map, a diagram detailing the relations. Once we have maps for many relevant sets of learning criteria, the collection of these maps is an Atlas of Computational Learning Theory, informing at a glance about the landscape of computational learning just as a geographical atlas informs about the earth.
In this paper we work toward this goal by providing three example maps, one pertaining to partially set-driven learning, and two pertaining to strongly monotone learning. These maps can serve as blueprints for future maps of similar base structure
Analysis of the (1+1) EA on Subclasses of Linear Functions under Uniform and Linear Constraints
No full textLinear functions have gained a lot of attention in the area of run time analysis of evolutionary computation methods and the corresponding analyses have provided many effective tools for analyzing more complex problems. In this paper, we consider the behavior of the classical (1+1) Evolutionary Algorithm for linear functions under linear constraint. We show tight bounds in the case where both the objective and the constraint function is given by the OneMax function and present upper bounds as well as lower bounds for the general case. We also consider the LeadingOnes fitness function.Tobias Friedrich, Timo Kötzing, Gregor Lagodzinski, Frank Neumann, Martin Schirnec
The Spoken Wikipedia Corpora
No full textThe Spoken Wikipedia project unites volunteer readers of Wikipedia articles. Hundreds of spoken articles in multiple languages are available to users who are – for one reason or another – unable or unwilling to consume the written version of the article. Our resource, the Spoken Wikipedia Corpus, consolidates the Spoken Wikipediae, adding text segmentation, normalization, time-alignment and further annotations, making it accessible for research and fostering new ways of interacting with the material.
Timo Baumann and Arne Köhn and Felix Hennig. 2018. The Spoken Wikipedia Corpus Collection: Harvesting, Alignment and an Application to Hyperlistening, in Language Resources and Evaluation, Special Issue representing significant contributions of LREC 2016.
Arne Köhn, Florian Stegen, Timo Baumann. 2016. Mining the Spoken Wikipedia for Speech Data and Beyond, in Proceedings of the Tenth International Conference on Language Resources and Evaluation (LREC 2016).
CLARIN Metadata summary for The Spoken Wikipedia Corpora (CMDI-based)
Title: The Spoken Wikipedia Corpora
Description: The Spoken Wikipedia project unites volunteer readers of Wikipedia articles. Hundreds of spoken articles in multiple languages are available to users who are – for one reason or another – unable or unwilling to consume the written version of the article. Our resource, the Spoken Wikipedia Corpus, consolidates the Spoken Wikipediae, adding text segmentation, normalization, time-alignment and further annotations, making it accessible for research and fostering new ways of interacting with the material.
Publication date: 2017
Data owner: Timo Baumann - Universität Hamburg
Contributors: Timo Baumann (author), Arne Köhn (author), Florian Stegen (author)
Languages: English (eng), German (deu), Dutch (nld)
Size: 5397 article, 1005 hour
Segmentation units: other
Genre: encyclopedia
Modality: spoken
References: Timo Baumann; Arne Köhn; Felix Hennig (2018) The Spoken Wikipedia Corpus Collection: Harvesting, Alignment and an Application to Hyperlistening References: Arne Köhn; Florian Stegen; Timo Baumann (2016) Mining the Spoken Wikipedia for Speech Data and Beyon
Replication Data for: Efficient Application of Accelerator Cards for the Coupling Library preCICE
No full textThis dataset contains all testcase setup files and result files for the measurements presented in the Master's thesis with the title "Efficient Application of Accelerator Cards for the Coupling Library preCICE" (Author: Timo Pierre Schrader).
Furthermore, it contains the version of preCICE used throughout this thesis.
The thesis revolves around GPU acceleration of RBF data mapping in preCICE. See the README for more information how to build and run the testcase
More effective crossover operators for the all-pairs shortest path problem
No full textThe all-pairs problem is the first non-artificial problem for which it was shown that adding crossover can significantly speed up a mutation-only evolutionary algorithm. Recently, the analysis of this algorithm was refined and it was shown to have an expected optimization time of Θ(n 3.25(logn)0.25). In this work, we study two variants of the algorithm. These are based on two central concepts in recombination, repair mechanisms and parent selection. We show that repairing infeasible offspring leads to an improved expected optimization time of O(n3 2(logn)0 2). Furthermore, we prove that choosing parents that guarantee feasible offspring results in an optimization time of O(n3logn).Benjamin Doerr, Daniel Johannsen, Timo Kötzing, Frank Neumann and Madeleine Theil
Analysis of the (1 + 1) EA on subclasses of linear functions under uniform and linear constraints
No full textLinear functions have gained great attention in the run time analysis of evolutionary computation methods. The corresponding investigations have provided many effective tools for analyzing more complex problems. So far, the runtime analysis of evolutionary algorithms has mainly focused on unconstrained problems, but problems occurring in applications frequently involve constraints. Therefore, there is a strong need to extend the current analyses and used methods for analyzing unconstrained problems to a setting involving constraints. In this paper, we consider the behavior of the classical Evolutionary Algorithm on linear functions under linear constraint. We show tight bounds in the case where the constraint is given by the OneMax function and the objective function is given by either the OneMax or the BinVal function. For the general case we present upper and lower bounds.Tobias Friedrich, Timo Kötzing, J.A. Gregor Lagodzinski, Frank Neumann, Martin Schirnec
Reoptimization Time Analysis of Evolutionary Algorithms on Linear Functions Under Dynamic Uniform Constraints
No full textRigorous runtime analysis is a major approach towards understanding evolutionary computing techniques, and in this area linear pseudo-Boolean objective functions play a central role. Having an additional linear constraint is then equivalent to the NP-hard Knapsack problem, certain classes thereof have been studied in recent works. In this article, we present a dynamic model of optimizing linear functions under uniform constraints. Starting from an optimal solution with respect to a given constraint bound, we investigate the runtimes that different evolutionary algorithms need to recompute an optimal solution when the constraint bound changes by a certain amount. The classical (1+1) EA and several population-based algorithms are designed for that purpose, and are shown to recompute efficiently. Furthermore, a variant of the (1+(λ,λ)) GA for the dynamic optimization problem is studied, whose performance is better when the change of the constraint bound is small.Feng Shi, Martin Schirneck, Tobias Friedrich, Timo Kötzing, Frank Neuman
Analysis of the (1+1) EA on LeadingOnes with Constraints
No full textUnderstanding how evolutionary algorithms perform on constrained problems has gained increasing attention in recent years. In this paper, we study how evolutionary algorithms optimize constrained versions of the classical LeadingOnes problem. We first provide a run time analysis for the classical (1+1) EA on the LeadingOnes problem with a deterministic cardinality constraint, giving Θ((-) log() + ²) as the tight bound. Our results show that the be- haviour of the algorithm is highly dependent on the constraint bound of the uniform constraint. Afterwards, we consider the prob- lem in the context of stochastic constraints and provide insights tudies on how the (+1) EA is able to deal with se constraints in a sampling-based setting.Tobias Friedrich, Timo Kötzing, Aneta Neumann, Frank Neumann, Aishwarya Radhakrishna
Analysis of the (1+1) EA on LeadingOnes with Constraints
No full textPublished online: 19 February 2025.
Part of a collection: GECCO 2023Understanding how evolutionary algorithms perform on constrained problems has gained increasing attention in recent years. In this paper, we study how evolutionary algorithms optimize constrained versions of the classical LeadingOnes problem. We first provide a run time analysis for the classical (1+1) EAon the LeadingOnes problem with a deterministic cardinality constraint, giving Θ(n(n−B) log(B)+nB) as the tight bound. Our results show that the behaviour of the algorithm is highly dependent on the constraint bound of the uniform constraint. Afterwards, we consider the problem in the context of stochastic constraints and provide insights using theoretical and experimental studies on how the (μ+1) EA is able to deal with these constraints in a sampling-based setting.Tobias Friedrich, Timo Kötzing, Aneta Neumann, Frank Neumann, Aishwarya Radhakrishna
- …
