In this paper, we present an L^∗-style algorithm for actively learning a bidirectional deterministic finite automaton (biDFA) in polynomial time using three types of oracles. We show how the W-method for the equivalence oracle can be adapted to our algorithm and present a novel heuristic for choosing the orientation of states. With this algorithm, one can identify automata for a subset of the linear languages that includes but is not limited to the regular languages. Since the equivalence oracle is an important part of the algorithm, we also discuss complexity bounds for different versions of the language equivalence problem for biDFAs. These results, together with our algorithm, also prove complexity bounds for the biDFA minimisation problem. Finally, we provide an implementation of the algorithm and experimentally show its performance with different approximation heuristics.

We present the efficient implementations of probabilistic deterministic finite automaton learning methods available in FlexFringe. These are well-known strategies for state merging, including several modifications to improve their performance in practice. We show experimentally that these algorithms obtain competitive results and significant improvements over a default implementation. We also demonstrate how to use FlexFringe to learn interpretable models from software logs and use these for anomaly detection. Although less interpretable, we show that learning smaller, more convoluted models improves the performance of FlexFringe on anomaly detection, making it competitive with an existing solution based on neural nets.

The project “Real-time data-driven maintenance logistics” was initiated with the purpose of bringing innovations in data-driven decision making to maintenance logistics, by bringing problem owners in the form of three innovative companies together with researchers at two leading knowledge institutions. This paper reviews innovations in three related areas: How the innovations were inspired by practice, how they materialized, and how the results impact practice.

This paper reports on the first international competition on AI for the traveling salesman problem (TSP) at the International Joint Conference on Artificial Intelligence 2021 (IJCAI-21). The TSP is one of the classical combinatorial optimization problems, with many variants inspired by real-world applications. This first competition asked the participants to develop algorithms to solve an orienteering problem with stochastic weights and time windows (OPSWTW). It focused on two learning approaches: surrogate-based optimization and deep reinforcement learning. In this paper, we describe the problem, the competition setup, and the winning methods, and give an overview of the results. The winning methods described in this work have advanced the state-of-the-art in using AI for stochastic routing problems. Overall, by organizing this competition we have introduced routing problems as an interesting problem setting for AI researchers. The simulator of the problem has been made open-source and can be used by other researchers as a benchmark for new learning-based methods. The instances and code for the competition are available at https://github.com/paulorocosta/ai-for-tsp-competition.

Decision trees are popular models for their interpretation properties and their success in ensemble models for structured data. However, common decision tree learning algorithms produce models that suffer from adversarial examples. Recent work on robust decision tree learning mitigates this issue by taking adversarial perturbations into account during training. While these methods generate robust shallow trees, their relative quality reduces when training deeper trees due the methods being greedy. In this work we propose robust relabeling, a post-learning procedure that optimally changes the prediction labels of decision tree leaves to maximize adversarial robustness. We show this can be achieved in polynomial time in terms of the number of samples and leaves. Our results on 10 datasets show a significant improvement in adversarial accuracy both for single decision trees and tree ensembles. Decision trees and random forests trained with a state-of-the-art robust learning algorithm also benefited from robust relabeling.

Interpretability of reinforcement learning policies is essential for many real-world tasks but learning such interpretable policies is a hard problem. Particularly, rule-based policies such as decision trees and rules lists are difficult to optimize due to their non-differentiability. While existing techniques can learn verifiable decision tree policies, there is no guarantee that the learners generate a policy that performs optimally. In this work, we study the optimization of size-limited decision trees for Markov Decision Processes (MPDs) and propose OMDTs: Optimal MDP Decision Trees. Given a user-defined size limit and MDP formulation, OMDT directly maximizes the expected discounted return for the decision tree using Mixed-Integer Linear Programming. By training optimal tree policies for different MDPs we empirically study the optimality gap for existing imitation learning techniques and find that they perform sub-optimally. We show that this is due to an inherent shortcoming of imitation learning, namely that complex policies cannot be represented using size-limited trees. In such cases, it is better to directly optimize the tree for expected return. While there is generally a trade-off between the performance and interpretability of machine learning models, we find that on small MDPs, depth 3 OMDTs often perform close to optimally.

Surrogate algorithms such as Bayesian optimisation are especially designed for black-box optimisation problems with expensive objectives, such as hyperparameter tuning or simulation-based optimisation. In the literature, these algorithms are usually evaluated with synthetic benchmarks which are well established but have no expensive objective, and only on one or two real-life applications which vary wildly between papers. There is a clear lack of standardisation when it comes to benchmarking surrogate algorithms on real-life, expensive, black-box objective functions. This makes it very difficult to draw conclusions on the effect of algorithmic contributions and to give substantial advice on which method to use when. A new benchmark library, EXPObench, provides first steps towards such a standardisation. The library is used to provide an extensive comparison of six different surrogate algorithms on four expensive optimisation problems from different real-life applications. This has led to new insights regarding the relative importance of exploration, the evaluation time of the objective, and the used model. We also provide rules of thumb for which surrogate algorithm to use in which situation. A further contribution is that we make the algorithms and benchmark problem instances publicly available, contributing to more uniform analysis of surrogate algorithms. Most importantly, we include the results of the six algorithms on all evaluated problem instances. This unique new dataset lowers the bar for researching new methods as the number of expensive evaluations required for comparison and for the creation of new surrogate models is significantly reduced.

These days more companies are shifting towards using cloud environments to provide their services to their client. While it is easy to set up a cloud environment, it is equally important to monitor the system's runtime behaviour and identify anomalous behaviours that occur during its operation. In recent years, the utilisation of Recurrent Neural Networks (RNNs) and Deep Neural Networks (DNNs) to detect anomalies that might occur during runtime has been a trending approach. However, it is unclear how to explain the decisions made by these networks and how these networks should be interpreted to understand the runtime behaviour that they model. On the contrary, state machine models provide an easier manner to interpret and understand the behaviour that they model. In this work, we propose an approach that learns state machine models to model the runtime behaviour of a cloud environment that runs multiple microservice applications. To the best of our knowledge, this is the first work that tries to apply state machine models to microservice architectures. The state machine model is used to detect the different types of attacks that we launch on the cloud environment. From our experiment results, our approach can detect the attacks very well, achieving a balanced accuracy of 99.2% and a F1 score of 0.982.

The 5G Radio Access Network (RAN) virtualization aims to improve network quality and lower the operator's costs. One of its main features is the functional split, i.e., dividing the instantiation of RAN baseband functions into different units over metro-network nodes. However, its optimal placement is non-trivial: it depends on the application requirements and on the expected traffic volume, whose daily variation highly impacts the total power consumption. Current optimization solutions fail to provide a placement solution capable of handling traffic fluctuations. In fact, the standard machine learning algorithms used in the literature for planning the network resources in advance result in an allocation that is inadequate to carry the actual traffic at all the time-slots. Hence, we must reserve an artificial buffer capacity in the nodes to ensure feasibility. Instead, our proposed method exploits a fine-grained two-step multi-task algorithm that predicts the mean and quantile traffic, making the artificial capacity no longer necessary. The subsequent placement uses mixed-integer linear programming and a heuristic. The former considers the expected traffic in the objective function (to estimate costs) and the quantile in the constraints (to enforce capacity limits). The heuristic combines the mean and quantile results to minimize the power and comply with the requirements. While using sufficiently large artificial buffers guarantees robustness with a mild power increase compared to the oracle, the fine-grained multi-task model improves the results, reducing the power consumption compared to the mean and meets all constraints. The heuristic enables significant computational time reduction.