Multi-label classification (MLC) is an ML task of predictive modeling in which a data instance can simultaneously belong to multiple classes. MLC is increasingly gaining interest in different application domains such ...
详细信息
ISBN:
(纸本)9781665487689
Multi-label classification (MLC) is an ML task of predictive modeling in which a data instance can simultaneously belong to multiple classes. MLC is increasingly gaining interest in different application domains such as text mining, computer vision, and bioinformatics. Several MLC algorithms have been proposed in the literature, resulting in a meta-optimization problem that the user needs to address: which MLC approach to select for a given dataset? To address this algorithmselection problem, we investigate in this work the quality of an automated approach that uses characteristics of the datasets - so-called features - and a trained algorithm selector to choose which algorithm to apply for a given task. For our empirical evaluation, we use a portfolio of 38 datasets. We consider eight MLC algorithms, whose quality we evaluate using six different performance metrics. We show that our automatedalgorithm selector outperforms any of the single MLC algorithms, and this is for all evaluated performance measures. Our selection approach is explainable, a characteristic that we exploit to investigate which meta-features have the largest influence on the decisions made by the algorithm selector. Finally, we also quantify the importance of the most significant metafeatures for various domains.
Answer-set programming (ASP) is a truly declarative programming paradigm proposed in the area of non-monotonic reasoning and logic programming, which has been recently employed in many applications. The development of...
详细信息
Answer-set programming (ASP) is a truly declarative programming paradigm proposed in the area of non-monotonic reasoning and logic programming, which has been recently employed in many applications. The development of efficient ASP systems is, thus, crucial. Having in mind the task of improving the solving methods for ASP, there are two usual ways to reach this goal: (i) extending state-of-the-art techniques and ASP solvers or (ii) designing a new ASP solver from scratch. An alternative to these trends is to build on top of state-of-the-art solvers, and to apply machine learning techniques for choosing automatically the "best" available solver on a per-instance basis. In this paper, we pursue this latter direction. We first define a set of cheap-to-compute syntactic features that characterize several aspects of ASP programs. Then, we apply classification methods that, given the features of the instances in a training set and the solvers' performance on these instances, inductively learn algorithmselection strategies to be applied to a test set. We report the results of a number of experiments considering solvers and different training and test sets of instances taken from the ones submitted to the "System Track" of the Third ASP Competition. Our analysis shows that by applying machine learning techniques to ASP solving, it is possible to obtain very robust performance: our approach can solve more instances compared with any solver that entered the Third ASP Competition.
The Travelling Salesperson Problem (TSP) is one of the best-studied NP-hard problems. Over the years, many different solution approaches and solvers have been developed. For the first time, we directly compare five st...
详细信息
The Travelling Salesperson Problem (TSP) is one of the best-studied NP-hard problems. Over the years, many different solution approaches and solvers have been developed. For the first time, we directly compare five state-of-the-art inexact solvers-namely, LKH, EAX, restart variants of those, and MAOS-on a large set of well-known benchmark instances and demonstrate complementary performance, in that different instances may be solved most effectively by different algorithms. We leverage this complementarity to build an algorithm selector, which selects the best TSP solver on a per-instance basis and thus achieves significantly improved performance compared to the single best solver, representing an advance in the state of the art in solving the Euclidean TSP. Our in-depth analysis of the selectors provides insight into what drives this performance improvement.
The heterogeneity among objectives in multi-objective optimization can be viewed from several perspectives. In this paper, we are interested in the heterogeneity arising in the underlying landscape of the objective fu...
详细信息
The heterogeneity among objectives in multi-objective optimization can be viewed from several perspectives. In this paper, we are interested in the heterogeneity arising in the underlying landscape of the objective functions, in terms of multi-modality and search difficulty. Building on recent efforts leveraging the so-called single- objective NK-landscapes to model such a setting, we conduct a three-fold empirical analysis on the impact of objective heterogeneity on the landscape properties and search difficulty of bi-objective optimization problems. Firstly, for small problems, we propose two techniques based on studying the distribution of the solutions in the objective space. Secondly, for large problems, we investigate the ability of existing landscape features to capture the degree of heterogeneity among the two objectives. Thirdly, we study the behavior of two state-of-the-art multi-objective evolutionary algorithms, namely MOEA/D and NSGA-II, when faced with a range of problems with different degrees of heterogeneity. Although one algorithm is found to consistently outperform the other, the dynamics of both algorithms vary similarly with respect to objective heterogeneity. Our analysis suggests that novel approaches are needed to understand the fundamental properties of heterogeneous bi-objective optimization problems and to tackle them more effectively.
The recent application of Machine Learning techniques to the Answer Set Programming (ASP) field proved to be effective. In particular, the multi-engine ASP solver ME-ASP is efficient: it is able to solve more instance...
详细信息
The recent application of Machine Learning techniques to the Answer Set Programming (ASP) field proved to be effective. In particular, the multi-engine ASP solver ME-ASP is efficient: it is able to solve more instances than any other ASP system that participated to the 3rd ASP Competition on the 'System Track' benchmarks. In the ME-ASP approach, classification methods inductively learn offline algorithmselection policies starting from both a set of features of instances in a training set, and the solvers performance on such instances. In this article we present an improvement to the multi-engine framework of ME-ASP, in which we add the capability of updating the learned policies when the original approach fails to give good predictions. An experimental analysis, conducted on training and test sets of ground instances obtained from the ones submitted to the 'System Track' of the 3rd ASP Competition, shows that the policy adaptation improves the performance of ME-ASP when applied to test sets containing domains of instances that were not considered for training.
The herein proposed Python package pflacco provides a set of numerical features to characterize single-objective continuous and constrained optimization problems. Thereby, pflacco addresses two major challenges in the...
详细信息
The herein proposed Python package pflacco provides a set of numerical features to characterize single-objective continuous and constrained optimization problems. Thereby, pflacco addresses two major challenges in the area of optimization. Firstly, it provides the means to develop an understanding of a given problem instance, which is crucial for designing, selecting, or configuring optimization algorithms in general. Secondly, these numerical features can be utilized in the research streams of automated algorithm selection and configuration. While the majority of these landscape features are already available in the R package flacco, our Python implementation offers these tools to an even wider audience and thereby promotes research interests and novel avenues in the area of optimization.
This paper is concerned with the job shop scheduling problem, a well-known, NP-hard problem that has been extensively studied in the literature, but for which, despite its age and popularity, there has been relatively...
详细信息
This paper is concerned with the job shop scheduling problem, a well-known, NP-hard problem that has been extensively studied in the literature, but for which, despite its age and popularity, there has been relatively little work done towards understanding the landscape of instances. We provide a systematic analysis of the instance space for this problem. For this purpose, the benchmark instances commonly used in the literature were analyzed and extended by a set of newly generated instances of various sizes with processing times drawn from different probability distributions. A number of different state-of-the-art algorithms were evaluated on the extended instance set to analyze their performance patterns and highlight the differences to the current set of benchmark instances. It was found that the existing instances cover a significantly smaller area than the generated ones and did in fact result in different conclusions regarding the algorithms' performances. Furthermore, different algorithms have been shown to excel on distinct subsets of the extended instance set. This has been utilized to train machine learning models to predict the best algorithm for a given instance, the best of which was able to obtain the best solution for 90% of the instances, whereas the best individual algorithm only obtained the best solution for 64%.
Black-box optimization is a very active area of research, with many new algorithms being developed every year. This variety is needed, on the one hand, since different algorithms are most suitable for different types ...
详细信息
ISBN:
(纸本)9783030726980;9783030726997
Black-box optimization is a very active area of research, with many new algorithms being developed every year. This variety is needed, on the one hand, since different algorithms are most suitable for different types of optimization problems. But the variety also poses a meta-problem: which algorithm to choose for a given problem at hand? Past research has shown that per-instance algorithmselection based on exploratory landscape analysis (ELA) can be an efficient mean to tackle this meta-problem. Existing approaches, however, require the approximation of problem features based on a significant number of samples, which are typically selected through uniform sampling or Latin Hypercube Designs. The evaluation of these points is costly, and the benefit of an ELA-based algorithmselection over a default algorithm must therefore be significant in order to pay off. One could hope to by-pass the evaluations for the feature approximations by using the samples that a default algorithm would anyway perform, i.e., by using the points of the default algorithm's trajectory. We analyze in this paper how well such an approach can work. Concretely, we test how accurately trajectory-based ELA approaches can predict the final solution quality of the CMA-ES after a fixed budget of function evaluations. We observe that the loss of trajectory-based predictions can be surprisingly small compared to the classical global sampling approach, if the remaining budget for which solution quality shall be predicted is not too large. Feature selection, in contrast, did not show any advantage in our experiments and rather led to worsened prediction accuracy. The inclusion of state variables of CMA-ES only has a moderate effect on the prediction accuracy.
Finding the optimal solution for a given problem has always been an intriguing goal and a key for reaching this goal is sound knowledge of the problem at hand. In case of single-objective, continuous, global optimizat...
详细信息
ISBN:
(纸本)9781450349390
Finding the optimal solution for a given problem has always been an intriguing goal and a key for reaching this goal is sound knowledge of the problem at hand. In case of single-objective, continuous, global optimization problems, such knowledge can be gained by Exploratory Landscape Analysis (ELA), which computes features that quantify the problem's landscape prior to optimization. Due to the various backgrounds of researches that developed such features, there nowadays exist numerous implementations of feature sets across multiple programming languages, which is a blessing and burden at the same time. The recently developed R-package flacco takes multiple of these feature sets (from the different packages and languages) and combines them within a single R-package. While this is very beneficial for R-users, users of other programming languages are left out. Within this paper, we introduce flaccogui, a graphical user interface that does not only make flacco more user-friendly, but due to a platform-independent web-application also allows researchers that are not familiar with R to perform ELA and benefit of the advantages of flacco.
automated algorithm selection has proven to be effective to improve optimization performance by using machine learning to select the best-performing algorithm for the particular problem being solved. However, doing so...
详细信息
ISBN:
(纸本)9783031700675;9783031700682
automated algorithm selection has proven to be effective to improve optimization performance by using machine learning to select the best-performing algorithm for the particular problem being solved. However, doing so requires the ability to describe the landscape of optimization problems using numerical features, which is a difficult task. In this work, we analyze the synergies and complementarity of recently proposed feature sets TransOpt and Deep ELA, which are based on deep-learning, and compare them to the commonly used classical ELA features. We analyze the correlation between the feature sets as well as how well one set can predict the other. We show that while the feature sets contain some shared information, each also contains important unique information. Further, we compare and benchmark the different feature sets for the task of automated algorithm selection on the recently proposed affine black-box optimization problems. We find that while classical ELA is the best-performing feature set by itself, using selected features from a combination of all three feature sets provides superior performance, and all three sets individually substantially outperform the single best solver.
暂无评论