Refine
Year of publication
- 2021 (43) (remove)
Document Type
- Article (18)
- Doctoral Thesis (13)
- Monograph/Edited Volume (6)
- Postprint (5)
- Conference Proceeding (1)
Language
- English (43) (remove)
Is part of the Bibliography
- yes (43) (remove)
Keywords
- MOOC (3)
- blockchain (3)
- business process management (3)
- machine learning (3)
- smart contracts (3)
- 3D-Visualisierung (2)
- Feature selection (2)
- Gene expression (2)
- OptoGait (2)
- Prior knowledge (2)
- Reproducible benchmarking (2)
- Zebris (2)
- business processes (2)
- cyber-physical systems (2)
- data pipeline (2)
- deep learning (2)
- deferred choice (2)
- formal semantics (2)
- gait analysis algorithm (2)
- inertial measurement unit (2)
- maschinelles Lernen (2)
- memory (2)
- oracles (2)
- probabilistic timed systems (2)
- public dataset (2)
- qualitative Analyse (2)
- qualitative analysis (2)
- quantitative Analyse (2)
- quantitative analysis (2)
- workflow patterns (2)
- 3D Visualization (1)
- 3D point cloud (1)
- 3D visualization (1)
- 3D-Punktwolke (1)
- Algebraic methods (1)
- Anomaly detection (1)
- Artificial Intelligence (1)
- Autoimmune (1)
- BIM (1)
- BPMN (1)
- Binary Classification (1)
- Binäre Klassifikation (1)
- Blockchain (1)
- Bounded Model Checking (1)
- Building Management (1)
- Business process modeling (1)
- Car safety management (1)
- Circular economy (1)
- Clinical Data (1)
- Clinical predictive modeling (1)
- Complexity (1)
- Compound Values (1)
- Conceptual modeling (1)
- Curex (1)
- Data Analytics (1)
- Data Structure Optimization (1)
- Data modeling (1)
- Data warehouse (1)
- Daten-Analytik (1)
- Datenstrukturoptimierung (1)
- Datenvisualisierung (1)
- Decision support (1)
- Deduplikation (1)
- Deep Kernel Learning (1)
- Deep Learning (1)
- Dezentrale Applikationen (1)
- Differential Expression Analysis (1)
- Digital Twin (1)
- Digitaler Zwilling (1)
- Duplikaterkennung (1)
- Durchsetzbarkeit (1)
- Dynamic pricing (1)
- E-Learning (1)
- Entitätsauflösung (1)
- Entitätsverknüpfung (1)
- European reference networks (1)
- Facility Management (1)
- Formal modelling (1)
- Forschungskolleg (1)
- Gebäudeinformationsmodellierung (1)
- Gebäudemanagement (1)
- General demand function (1)
- Geschäftsprozessmanagement (1)
- Graph logic (1)
- Graphentransformationssysteme (1)
- Hasso Plattner Institute (1)
- Hasso-Plattner-Institut (1)
- Heart Valve Diseases (1)
- Herzklappenerkrankungen (1)
- Human Computer Interaction (1)
- Häkeln (1)
- Immobilien 4.0 (1)
- Indoor Point Clouds (1)
- Indoor-Punktwolken (1)
- Interpretability (1)
- Interval Timed Automata (1)
- Interventionen (1)
- Klausurtagung (1)
- Klinische Daten (1)
- Kollaboration (1)
- Konstruktion von Wissensbasen (1)
- Kunstanalyse (1)
- Künstliche Intelligenz (1)
- Learning Analytics (1)
- MOOCs (1)
- Machine Learning (1)
- Maschinelles Lernen (1)
- Medien Bias (1)
- Mensch Computer Interaktion (1)
- Mixed Reality (1)
- Mobile Mapping (1)
- Mobile applications (1)
- Modellprüfung (1)
- Motion Mapping (1)
- Nachrichten (1)
- Natural language processing (1)
- Nephrology (1)
- Objects (1)
- Objekte (1)
- Online Learning Environments (1)
- Optimal control (1)
- Patient (1)
- Peer-feedback (1)
- Ph.D. retreat (1)
- Point Clouds (1)
- Politik (1)
- Popular matching (1)
- Predictive Modeling (1)
- Predictive models (1)
- Primary biliary cholangitis (1)
- Primary sclerosing cholangitis (1)
- Process mining (1)
- Programmierung (1)
- Proteom (1)
- Proteomics (1)
- Prädiktive Modellierung (1)
- Punktwolken (1)
- Real Estate 4.0 (1)
- Real Walking (1)
- Recursion (1)
- Recycling investments (1)
- Rekursion (1)
- Self-Regulated Learning (1)
- Semantic Enrichment (1)
- Semantische Anreicherung (1)
- Sensor Analytics (1)
- Sensor-Analytik (1)
- Service-Oriented Architecture (1)
- Service-Oriented Systems (1)
- Service-Orientierte Systeme (1)
- Service-oriented Systems Engineering (1)
- Siamesische Neuronale Netzwerke (1)
- Simulation (1)
- Smalltalk (1)
- Smart Contracts (1)
- Software (1)
- Specification (1)
- Stable marriage (1)
- Stable matching (1)
- Storytelling (1)
- Supervised Learning (1)
- Supervised deep neural (1)
- Systemmedizin (1)
- Systems Medicine (1)
- Tiefes Lernen (1)
- Time series analysis (1)
- Timed Automata (1)
- Transferlernen (1)
- U-Förmiges Lernen (1)
- U-Shaped-Learning (1)
- Validation (1)
- Verbundwerte (1)
- Virtual Machines (1)
- Virtuelle Maschinen (1)
- Visualisierung (1)
- Visualisierungskonzept-Exploration (1)
- Visualization (1)
- Vorhersagemodellierung (1)
- Walking (1)
- Werkzeuge (1)
- Wissensbasis (1)
- Wissensgraph (1)
- Wissenstransfer (1)
- Wissensvalidierung (1)
- acyclic preferences (1)
- art analysis (1)
- bounded model checking (1)
- collaboration (1)
- computer vision (1)
- computer-aided design (1)
- crochet (1)
- cultural heritage (1)
- curex (1)
- cyber-physikalische Systeme (1)
- cyber-physische Systeme (1)
- data visualization (1)
- decentralized applications (1)
- deduplication (1)
- deep kernel learning (1)
- demografische Informationen (1)
- demographic information (1)
- digital education (1)
- duplicate detection (1)
- e-learning (1)
- enforceability (1)
- entity linking (1)
- entity resolution (1)
- erzeugende gegnerische Netzwerke (1)
- experience (1)
- formal testing (1)
- generative adversarial networks (1)
- geospatial data (1)
- graph conditions (1)
- graph transformation systems (1)
- hepatitis (1)
- higher education (1)
- human activity recognition (1)
- image processing (1)
- interval probabilistic timed systems (1)
- interval probabilistische zeitgesteuerte Systeme (1)
- interval timed automata (1)
- intervention (1)
- intransitivity (1)
- knowledge base (1)
- knowledge base construction (1)
- knowledge graph (1)
- knowledge transfer (1)
- knowledge validation (1)
- kulturelles Erbe (1)
- literature review (1)
- logic rules (1)
- logische Regeln (1)
- maschinelles Sehen (1)
- media bias (1)
- methods (1)
- metric temporal graph logic (1)
- microcredential (1)
- mobile mapping (1)
- model checking (1)
- named entity recognition (1)
- natural language processing (1)
- networks (1)
- news (1)
- online course creation (1)
- online course design (1)
- patent analysis (1)
- peer assessment (1)
- peer evaluation (1)
- peer feedback (1)
- peer review (1)
- politics (1)
- poset (1)
- probabilistische gezeitete Systeme (1)
- probabilistische zeitgesteuerte Systeme (1)
- programming (1)
- rechnerunterstütztes Konstruieren (1)
- reported out-come measures (1)
- research school (1)
- räumliche Geodaten (1)
- semantic classification (1)
- semantische Klassifizierung (1)
- sensor data (1)
- service-oriented systems engineering (1)
- siamese neural networks (1)
- social interaction (1)
- stable matching (1)
- strongly stable matching (1)
- super stable matching (1)
- text mining (1)
- tiefes Lernen (1)
- timed automata (1)
- timed graph (1)
- tools (1)
- transfer learning (1)
- transformation (1)
- typed attributed symbolic graphs (1)
- visual language (1)
- visualization concept exploration (1)
- visuelle Sprache (1)
- weakly (1)
- web-based development environment (1)
- web-basierte Entwicklungsumgebung (1)
- Überwachtes Lernen (1)
Institute
- Hasso-Plattner-Institut für Digital Engineering GmbH (43) (remove)
Embedded real-time systems generate state sequences where time elapses between state changes. Ensuring that such systems adhere to a provided specification of admissible or desired behavior is essential. Formal model-based testing is often a suitable cost-effective approach. We introduce an extended version of the formalism of symbolic graphs, which encompasses types as well as attributes, for representing states of dynamic systems. Relying on this extension of symbolic graphs, we present a novel formalism of timed graph transformation systems (TGTSs) that supports the model-based development of dynamic real-time systems at an abstract level where possible state changes and delays are specified by graph transformation rules. We then introduce an extended form of the metric temporal graph logic (MTGL) with increased expressiveness to improve the applicability of MTGL for the specification of timed graph sequences generated by a TGTS. Based on the metric temporal operators of MTGL and its built-in graph binding mechanics, we express properties on the structure and attributes of graphs as well as on the occurrence of graphs over time that are related by their inner structure. We provide formal support for checking whether a single generated timed graph sequence adheres to a provided MTGL specification. Relying on this logical foundation, we develop a testing framework for TGTSs that are specified using MTGL. Lastly, we apply this testing framework to a running example by using our prototypical implementation in the tool AutoGraph.
Which event happened first?
(2021)
First come, first served: Critical choices between alternative actions are often made based on events external to an organization, and reacting promptly to their occurrence can be a major advantage over the competition. In Business Process Management (BPM), such deferred choices can be expressed in process models, and they are an important aspect of process engines. Blockchain-based process execution approaches are no exception to this, but are severely limited by the inherent properties of the platform: The isolated environment prevents direct access to external entities and data, and the non-continual runtime based entirely on atomic transactions impedes the monitoring and detection of events. In this paper we provide an in-depth examination of the semantics of deferred choice, and transfer them to environments such as the blockchain. We introduce and compare several oracle architectures able to satisfy certain requirements, and show that they can be implemented using state-of-the-art blockchain technology.
Recent trends in ubiquitous computing have led to a proliferation of studies that focus on human activity recognition (HAR) utilizing inertial sensor data that consist of acceleration, orientation and angular velocity. However, the performances of such approaches are limited by the amount of annotated training data, especially in fields where annotating data is highly time-consuming and requires specialized professionals, such as in healthcare. In image classification, this limitation has been mitigated by powerful oversampling techniques such as data augmentation. Using this technique, this work evaluates to what extent transforming inertial sensor data into movement trajectories and into 2D heatmap images can be advantageous for HAR when data are scarce. A convolutional long short-term memory (ConvLSTM) network that incorporates spatiotemporal correlations was used to classify the heatmap images. Evaluation was carried out on Deep Inertial Poser (DIP), a known dataset composed of inertial sensor data. The results obtained suggest that for datasets with large numbers of subjects, using state-of-the-art methods remains the best alternative. However, a performance advantage was achieved for small datasets, which is usually the case in healthcare. Moreover, movement trajectories provide a visual representation of human activities, which can help researchers to better interpret and analyze motion patterns.
As part of our everyday life we consume breaking news and interpret it based on our own viewpoints and beliefs. We have easy access to online social networking platforms and news media websites, where we inform ourselves about current affairs and often post about our own views, such as in news comments or social media posts. The media ecosystem enables opinions and facts to travel from news sources to news readers, from news article commenters to other readers, from social network users to their followers, etc. The views of the world many of us have depend on the information we receive via online news and social media. Hence, it is essential to maintain accurate, reliable and objective online content to ensure democracy and verity on the Web. To this end, we contribute to a trustworthy media ecosystem by analyzing news and social media in the context of politics to ensure that media serves the public interest. In this thesis, we use text mining, natural language processing and machine learning techniques to reveal underlying patterns in political news articles and political discourse in social networks.
Mainstream news sources typically cover a great amount of the same news stories every day, but they often place them in a different context or report them from different perspectives. In this thesis, we are interested in how distinct and predictable newspaper journalists are, in the way they report the news, as a means to understand and identify their different political beliefs. To this end, we propose two models that classify text from news articles to their respective original news source, i.e., reported speech and also news comments. Our goal is to capture systematic quoting and commenting patterns by journalists and news commenters respectively, which can lead us to the newspaper where the quotes and comments are originally published. Predicting news sources can help us understand the potential subjective nature behind news storytelling and the magnitude of this phenomenon. Revealing this hidden knowledge can restore our trust in media by advancing transparency and diversity in the news.
Media bias can be expressed in various subtle ways in the text and it is often challenging to identify these bias manifestations correctly, even for humans. However, media experts, e.g., journalists, are a powerful resource that can help us overcome the vague definition of political media bias and they can also assist automatic learners to find the hidden bias in the text. Due to the enormous technological advances in artificial intelligence, we hypothesize that identifying political bias in the news could be achieved through the combination of sophisticated deep learning modelsxi and domain expertise. Therefore, our second contribution is a high-quality and reliable news dataset annotated by journalists for political bias and a state-of-the-art solution for this task based on curriculum learning. Our aim is to discover whether domain expertise is necessary for this task and to provide an automatic solution for this traditionally manually-solved problem. User generated content is fundamentally different from news articles, e.g., messages are shorter, they are often personal and opinionated, they refer to specific topics and persons, etc. Regarding political and socio-economic news, individuals in online communities make use of social networks to keep their peers up-to-date and to share their own views on ongoing affairs. We believe that social media is also an as powerful instrument for information flow as the news sources are, and we use its unique characteristic of rapid news coverage for two applications. We analyze Twitter messages and debate transcripts during live political presidential debates to automatically predict the topics that Twitter users discuss. Our goal is to discover the favoured topics in online communities on the dates of political events as a way to understand the political subjects of public interest. With the up-to-dateness of microblogs, an additional opportunity emerges, namely to use social media posts and leverage the real-time verity about discussed individuals to find their locations.
That is, given a person of interest that is mentioned in online discussions, we use the wisdom of the crowd to automatically track her physical locations over time. We evaluate our approach in the context of politics, i.e., we predict the locations of US politicians as a proof of concept for important use cases, such as to track people that
are national risks, e.g., warlords and wanted criminals.
Compound values are not universally supported in virtual machine (VM)-based programming systems and languages. However, providing data structures with value characteristics can be beneficial. On one hand, programming systems and languages can adequately represent physical quantities with compound values and avoid inconsistencies, for example, in representation of large numbers. On the other hand, just-in-time (JIT) compilers, which are often found in VMs, can rely on the fact that compound values are immutable, which is an important property in optimizing programs. Considering this, compound values have an optimization potential that can be put to use by implementing them in VMs in a way that is efficient in memory usage and execution time. Yet, optimized compound values in VMs face certain challenges: to maintain consistency, it should not be observable by the program whether compound values are represented in an optimized way by a VM; an optimization should take into account, that the usage of compound values can exhibit certain patterns at run-time; and that necessary value-incompatible properties due to implementation restrictions should be reduced.
We propose a technique to detect and compress common patterns of compound value usage at run-time to improve memory usage and execution speed. Our approach identifies patterns of frequent compound value references and introduces abbreviated forms for them. Thus, it is possible to store multiple inter-referenced compound values in an inlined memory representation, reducing the overhead of metadata and object references. We extend our approach by a notion of limited mutability, using cells that act as barriers for our approach and provide a location for shared, mutable access with the possibility of type specialization. We devise an extension to our approach that allows us to express automatic unboxing of boxed primitive data types in terms of our initial technique. We show that our approach is versatile enough to express another optimization technique that relies on values, such as Booleans, that are unique throughout a programming system. Furthermore, we demonstrate how to re-use learned usage patterns and optimizations across program runs, thus reducing the performance impact of pattern recognition.
We show in a best-case prototype that the implementation of our approach is feasible and can also be applied to general purpose programming systems, namely implementations of the Racket language and Squeak/Smalltalk. In several micro-benchmarks, we found that our approach can effectively reduce memory consumption and improve execution speed.
Modern knowledge bases contain and organize knowledge from many different topic areas. Apart from specific entity information, they also store information about their relationships amongst each other. Combining this information results in a knowledge graph that can be particularly helpful in cases where relationships are of central importance. Among other applications, modern risk assessment in the financial sector can benefit from the inherent network structure of such knowledge graphs by assessing the consequences and risks of certain events, such as corporate insolvencies or fraudulent behavior, based on the underlying network structure. As public knowledge bases often do not contain the necessary information for the analysis of such scenarios, the need arises to create and maintain dedicated domain-specific knowledge bases.
This thesis investigates the process of creating domain-specific knowledge bases from structured and unstructured data sources. In particular, it addresses the topics of named entity recognition (NER), duplicate detection, and knowledge validation, which represent essential steps in the construction of knowledge bases.
As such, we present a novel method for duplicate detection based on a Siamese neural network that is able to learn a dataset-specific similarity measure which is used to identify duplicates. Using the specialized network architecture, we design and implement a knowledge transfer between two deduplication networks, which leads to significant performance improvements and a reduction of required training data.
Furthermore, we propose a named entity recognition approach that is able to identify company names by integrating external knowledge in the form of dictionaries into the training process of a conditional random field classifier. In this context, we study the effects of different dictionaries on the performance of the NER classifier. We show that both the inclusion of domain knowledge as well as the generation and use of alias names results in significant performance improvements.
For the validation of knowledge represented in a knowledge base, we introduce Colt, a framework for knowledge validation based on the interactive quality assessment of logical rules. In its most expressive implementation, we combine Gaussian processes with neural networks to create Colt-GP, an interactive algorithm for learning rule models. Unlike other approaches, Colt-GP uses knowledge graph embeddings and user feedback to cope with data quality issues of knowledge bases. The learned rule model can be used to conditionally apply a rule and assess its quality.
Finally, we present CurEx, a prototypical system for building domain-specific knowledge bases from structured and unstructured data sources. Its modular design is based on scalable technologies, which, in addition to processing large datasets, ensures that the modules can be easily exchanged or extended. CurEx offers multiple user interfaces, each tailored to the individual needs of a specific user group and is fully compatible with the Colt framework, which can be used as part of the system.
We conduct a wide range of experiments with different datasets to determine the strengths and weaknesses of the proposed methods. To ensure the validity of our results, we compare the proposed methods with competing approaches.
3D point clouds are a universal and discrete digital representation of three-dimensional objects and environments. For geospatial applications, 3D point clouds have become a fundamental type of raw data acquired and generated using various methods and techniques. In particular, 3D point clouds serve as raw data for creating digital twins of the built environment.
This thesis concentrates on the research and development of concepts, methods, and techniques for preprocessing, semantically enriching, analyzing, and visualizing 3D point clouds for applications around transport infrastructure. It introduces a collection of preprocessing techniques that aim to harmonize raw 3D point cloud data, such as point density reduction and scan profile detection. Metrics such as, e.g., local density, verticality, and planarity are calculated for later use. One of the key contributions tackles the problem of analyzing and deriving semantic information in 3D point clouds. Three different approaches are investigated: a geometric analysis, a machine learning approach operating on synthetically generated 2D images, and a machine learning approach operating on 3D point clouds without intermediate representation.
In the first application case, 2D image classification is applied and evaluated for mobile mapping data focusing on road networks to derive road marking vector data. The second application case investigates how 3D point clouds can be merged with ground-penetrating radar data for a combined visualization and to automatically identify atypical areas in the data. For example, the approach detects pavement regions with developing potholes. The third application case explores the combination of a 3D environment based on 3D point clouds with panoramic imagery to improve visual representation and the detection of 3D objects such as traffic signs.
The presented methods were implemented and tested based on software frameworks for 3D point clouds and 3D visualization. In particular, modules for metric computation, classification procedures, and visualization techniques were integrated into a modular pipeline-based C++ research framework for geospatial data processing, extended by Python machine learning scripts. All visualization and analysis techniques scale to large real-world datasets such as road networks of entire cities or railroad networks.
The thesis shows that some use cases allow taking advantage of established image vision methods to analyze images rendered from mobile mapping data efficiently. The two presented semantic classification methods working directly on 3D point clouds are use case independent and show similar overall accuracy when compared to each other. While the geometry-based method requires less computation time, the machine learning-based method supports arbitrary semantic classes but requires training the network with ground truth data. Both methods can be used in combination to gradually build this ground truth with manual corrections via a respective annotation tool.
This thesis contributes results for IT system engineering of applications, systems, and services that require spatial digital twins of transport infrastructure such as road networks and railroad networks based on 3D point clouds as raw data. It demonstrates the feasibility of fully automated data flows that map captured 3D point clouds to semantically classified models. This provides a key component for seamlessly integrated spatial digital twins in IT solutions that require up-to-date, object-based, and semantically enriched information about the built environment.
First come, first served: Critical choices between alternative actions are often made based on events external to an organization, and reacting promptly to their occurrence can be a major advantage over the competition. In Business Process Management (BPM), such deferred choices can be expressed in process models, and they are an important aspect of process engines. Blockchain-based process execution approaches are no exception to this, but are severely limited by the inherent properties of the platform: The isolated environment prevents direct access to external entities and data, and the non-continual runtime based entirely on atomic transactions impedes the monitoring and detection of events. In this paper we provide an in-depth examination of the semantics of deferred choice, and transfer them to environments such as the blockchain. We introduce and compare several oracle architectures able to satisfy certain requirements, and show that they can be implemented using state-of-the-art blockchain technology.
Smart contracts promise to reform the legal domain by automating clerical and procedural work, and minimizing the risk of fraud and manipulation. Their core idea is to draft contract documents in a way which allows machines to process them, to grasp the operational and non-operational parts of the underlying legal agreements, and to use tamper-proof code execution alongside established judicial systems to enforce their terms. The implementation of smart contracts has been largely limited by the lack of an adequate technological foundation which does not place an undue amount of trust in any contract party or external entity. Only recently did the emergence of Decentralized Applications (DApps) change this: Stored and executed via transactions on novel distributed ledger and blockchain networks, powered by complex integrity and consensus protocols, DApps grant secure computation and immutable data storage while at the same time eliminating virtually all assumptions of trust.
However, research on how to effectively capture, deploy, and most of all enforce smart contracts with DApps in mind is still in its infancy. Starting from the initial expression of a smart contract's intent and logic, to the operation of concrete instances in practical environments, to the limits of automatic enforcement---many challenges remain to be solved before a widespread use and acceptance of smart contracts can be achieved.
This thesis proposes a model-driven smart contract management approach to tackle some of these issues. A metamodel and semantics of smart contracts are presented, containing concepts such as legal relations, autonomous and non-autonomous actions, and their interplay. Guided by the metamodel, the notion and a system architecture of a Smart Contract Management System (SCMS) is introduced, which facilitates smart contracts in all phases of their lifecycle. Relying on DApps in heterogeneous multi-chain environments, the SCMS approach is evaluated by a proof-of-concept implementation showing both its feasibility and its limitations.
Further, two specific enforceability issues are explored in detail: The performance of fully autonomous tamper-proof behavior with external off-chain dependencies and the evaluation of temporal constraints within DApps, both of which are essential for smart contracts but challenging to support in the restricted transaction-driven and closed environment of blockchain networks. Various strategies of implementing or emulating these capabilities, which are ultimately applicable to all kinds of DApp projects independent of smart contracts, are presented and evaluated.
We investigate models for incremental binary classification, an example for supervised online learning. Our starting point is a model for human and machine learning suggested by E.M.Gold.
In the first part, we consider incremental learning algorithms that use all of the available binary labeled training data in order to compute the current hypothesis. For this model, we observe that the algorithm can be assumed to always terminate and that the distribution of the training data does not influence learnability. This is still true if we pose additional delayable requirements that remain valid despite a hypothesis output delayed in time. Additionally, we consider the non-delayable requirement of consistent learning. Our corresponding results underpin the claim for delayability being a suitable structural property to describe and collectively investigate a major part of learning success criteria. Our first theorem states the pairwise implications or incomparabilities between an established collection of delayable learning success criteria, the so-called complete map. Especially, the learning algorithm can be assumed to only change its last hypothesis in case it is inconsistent with the current training data. Such a learning behaviour is called conservative.
By referring to learning functions, we obtain a hierarchy of approximative learning success criteria. Hereby we allow an increasing finite number of errors of the hypothesized concept by the learning algorithm compared with the concept to be learned. Moreover, we observe a duality depending on whether vacillations between infinitely many different correct hypotheses are still considered a successful learning behaviour. This contrasts the vacillatory hierarchy for learning from solely positive information.
We also consider a hypothesis space located between the two most common hypothesis space types in the nearby relevant literature and provide the complete map.
In the second part, we model more efficient learning algorithms. These update their hypothesis referring to the current datum and without direct regress to past training data. We focus on iterative (hypothesis based) and BMS (state based) learning algorithms. Iterative learning algorithms use the last hypothesis and the current datum in order to infer the new hypothesis.
Past research analyzed, for example, the above mentioned pairwise relations between delayable learning success criteria when learning from purely positive training data. We compare delayable learning success criteria with respect to iterative learning algorithms, as well as learning from either exclusively positive or binary labeled data. The existence of concept classes that can be learned by an iterative learning algorithm but not in a conservative way had already been observed, showing that conservativeness is restrictive. An additional requirement arising from cognitive science research %and also observed when training neural networks is U-shapedness, stating that the learning algorithm does diverge from a correct hypothesis. We show that forbidding U-shapes also restricts iterative learners from binary labeled data.
In order to compute the next hypothesis, BMS learning algorithms refer to the currently observed datum and the actual state of the learning algorithm. For learning algorithms equipped with an infinite amount of states, we provide the complete map. A learning success criterion is semantic if it still holds, when the learning algorithm outputs other parameters standing for the same classifier. Syntactic (non-semantic) learning success criteria, for example conservativeness and syntactic non-U-shapedness, restrict BMS learning algorithms. For proving the equivalence of the syntactic requirements, we refer to witness-based learning processes. In these, every change of the hypothesis is justified by a later on correctly classified witness from the training data. Moreover, for every semantic delayable learning requirement, iterative and BMS learning algorithms are equivalent. In case the considered learning success criterion incorporates syntactic non-U-shapedness, BMS learning algorithms can learn more concept classes than iterative learning algorithms.
The proofs are combinatorial, inspired by investigating formal languages or employ results from computability theory, such as infinite recursion theorems (fixed point theorems).