Manufacturing of free-form geometries using 5-axis Computer Numerically Controlled (CNC) machining brings challenges in path- and motion-planning as one typically wants to minimize the manufacturing time of the object under consideration, while keeping the machining error within fine machining tolerances that ranges in tens of microns. We propose an optimization-based pipeline that, for a given toroidal and/or cylindrical flat-end cutter, simultaneously optimizes its milling paths together with its local positioning represented by the rotation and tilt functions. The proposed strategy is validated on a variety of benchmark surfaces, with different hyperparameters for the objective function and initial conditions, showing that our results provide high-quality approximations of free-form geometries using by-construction non-colliding motions of the given tool. • Optimize toolpaths, rotation, and tilt together for 5-axis toroidal/flat tools. • Evolution-based framework (CMA-ES) for the multiobjective optimization problem. • Optimizes path distribution to improve accuracy and reduce overall length. • Validated on various benchmarks, including industrial free-form geometries.

Supervised learning with large-scale data usually leads to complex optimization problems, especially for classification tasks with multiple classes. Stochastic sub gradient methods can enable efficient learning with a large number of samples for classification techniques that minimize the average loss over the training samples. However, recent techniques, such as minimax risk classifiers (MRCs), minimize the maximum expected loss and are not amenable to stochastic sub gradient methods. In this paper, we present a learning algorithm based on the combination of constraint and column generation that enables efficient learning of MRCs with large-scale data for classification tasks with multiple classes. Experiments on multiple benchmark datasets show that the proposed algorithm provides upto a 10x speedup for general large-scale data and around a 100x speedup with a sizeable number of classes.

Population-based evolutionary algorithms are often considered when approaching computationally expensive black-box optimization problems. They employ a selection mechanism to choose the best solutions from a given population after comparing their objective values, which are then used to generate the next population. This iterative process explores the solution space efficiently, leading to improved solutions over time. However, one of the challenges of these algorithms is that they require a large number of evaluations to provide a quality solution, which might be computationally expensive when the evaluation cost is high. In some cases, it is possible to replace the original objective function with a less accurate approximation of lower cost. This introduces a trade-off between the evaluation cost and its accuracy. In this paper, we propose a technique capable of choosing an appropriate approximate function cost during the execution of the optimization algorithm. The proposal finds the minimum evaluation cost at which the solutions are still properly ranked, and consequently, more evaluations can be computed in the same amount of time with minimal accuracy loss. An experimental section on four very different problems reveals that the proposed approach can reach the same objective value in less than half of the time in certain cases.

We introduce a new PAC-Bayes oracle bound for unbounded losses that extends Cramér-Chernoff bounds to the PAC-Bayesian setting. The proof technique relies on controlling the tails of certain random variables involving the Cramér transform of the loss. Our approach naturally leverages properties of Cramér-Chernoff bounds, such as exact optimization of the free parameter in many PAC-Bayes bounds. We highlight several applications of the main theorem. Firstly, we show that our bound recovers and generalizes previous results. Additionally, our approach allows working with richer assumptions that result in more informative and potentially tighter bounds. In this direction, we provide a general bound under a new *model-dependent* assumption from which we obtain bounds based on parameter norms and log-Sobolev inequalities. Notably, many of these bounds can be minimized to obtain distributions beyond the Gibbs posterior and provide novel theoretical coverage to existing regularization techniques.

High-dimensional data is common in multiple areas, such as health care and genomics, where the number of features can be tens of thousands. In such scenarios, the large number of features often leads to inefficient learning. Constraint generation methods have recently enabled efficient learning of L1-regularized support vector machines (SVMs). In this paper, we leverage such methods to obtain an efficient learning algorithm for the recently proposed minimax risk classifiers (MRCs). The proposed iterative algorithm also provides a sequence of worst-case error probabilities and performs feature selection. Experiments on multiple high-dimensional datasets show that the proposed algorithm is efficient in high-dimensional scenarios. In addition, the worst-case error probability provides useful information about the classifier performance, and the features selected by the algorithm are competitive with the state-of-the-art.

Abstract The use of crowdsourcing for annotating data has become a popular and cheap alternative to expert labelling. As a consequence, an aggregation task is required to combine the different labels provided and agree on a single one per example. Most aggregation techniques, including the simple and robust majority voting—to select the label with the largest number of votes—disregard the descriptive information provided by the explanatory variable. In this paper, we propose domain-aware voting, an extension of majority voting which incorporates the descriptive variable and the rest of the instances of the dataset for aggregating the label of every instance. The experimental results with simulated and real-world crowdsourced data suggest that domain-aware voting is a competitive alternative to majority voting, especially when a part of the dataset is unlabelled. We elaborate on practical criteria for the use of domain-aware voting.

In recent years we have seen a handful of work on inference algorithms over non-stationary data streams. Given their flexibility, Bayesian non-parametric models are a good candidate for these scenarios. However, reliable streaming inference under the concept drift phenomenon is still an open problem for these models. In this work, we propose a variational inference algorithm for Dirichlet process mixture models. Our proposal deals with the concept drift by including an exponential forgetting over the prior global parameters. Our algorithm allows to adapt the learned model to the concept drifts automatically. We perform experiments in both synthetic and real data, showing that the proposed model outperforms state-of-the-art variational methods in density estimation, clustering and parameter tracking.

Weakly supervised learning is aimed to learn predictive models from partially supervised data, an easy-to-collect alternative to the costly standard full supervision. During the last decade, the research community has striven to show that learning reliable models in specific weakly supervised problems is possible. We present an empirical study that analyzes the value of weak information of supervision throughout its entire spectrum, from none to full supervision. Its contribution is assessed under the realistic assumption that a small subset of fully supervised data is available. Particularized in the problem of learning with candidate sets, we adapt Cozman and Cohen [1] key study to learning from weakly supervised data. Standard learning techniques are used to infer generative models from this type of supervision with both synthetic and real data. Empirical results suggest that weakly labeled data is helpful in realistic scenarios, where fully labeled data is scarce, and its contribution is directly related to both the amount of information of supervision and how meaningful this information is.

Abstract Statistical tests are a powerful set of tools when applied correctly, but unfortunately the extended misuse of them has caused great concern. Among many other applications, they are used in the detection of biomarkers so as to use the resulting p-values as a reference with which the candidate biomarkers are ranked. Although statistical tests can be used to rank, they have not been designed for that use. Moreover, there is no need to compute any p-value to build a ranking of candidate biomarkers. Those two facts raise the question of whether or not alternative methods which are not based on the computation of statistical tests that match or improve their performances can be proposed. In this paper, we propose two alternative methods to statistical tests. In addition, we propose an evaluation framework to assess both statistical tests and alternative methods in terms of both the performance and the reproducibility. The results indicate that there are alternative methods that can match or surpass methods based on statistical tests in terms of the reproducibility when processing real data, while maintaining a similar performance when dealing with synthetic data. The main conclusion is that there is room for the proposal of such alternative methods.

Probabilistic label learning is a challenging task that arises from recent real-world problems within the weakly supervised classification framework. In this task algorithms have to deal with datasets where each instance has associated a set of probabilities belonging to different class labels. In this paper, we propose a supervised univariate non-parametric discretization algorithm based on kernel density estimation that can deal with probabilistic labeled data. The algorithm takes advantage of the estimation of the class conditional densities to produce different sets of cut points according to different smoothing parameters of the kernel. Then, the best set of cut points is selected according to a given supervised classification performance measure. The computational complexity is O(NlogN), where N is the number of instances. The proposal is tested on simulated probabilistic labeled data, which allows assessing the behavior with different noise degrees. The results show that the algorithm outperforms other discretization algorithms and is robust to different degrees of uncertainty.

The maximum entropy principle advocates to evaluate events’ probabilities using a distribution that maximizes entropy among those that satisfy certain expectations’ constraints. Such principle can be generalized for arbitrary decision problems where it corresponds to minimax approaches. This paper establishes a framework for supervised classification based on the generalized maximum entropy principle that leads to minimax risk classifiers (MRCs). We develop learning techniques that determine MRCs for general entropy functions and provide performance guarantees by means of convex optimization. In addition, we describe the relationship of the presented techniques with existing classification methods, and quantify MRCs performance in comparison with the proposed bounds and conventional methods.

The$K$-means algorithm is one of the most popular clustering methods. However, it is a well-known fact that its performance, in terms of quality of the obtained solution and computational load, highly depends upon its initialization phase. For this reason, different initialization techniques have been developed throughout the years to enable its fast convergence to competitive solutions. In this sense, it is common practice to re-start the$K$-means algorithm several times via one of these techniques and keep the solution with the lowest error. Unfortunately, such a choice is still likely to be a poor approximation of the optimal set of centroids. In this article, we introduce a cheap Split-Merge step that can be used to re-start the$K$-means algorithm after reaching a fixed point. Under some settings, one can show that this approach reduces the error of the given fixed point without requiring any further iteration of the$K$-means algorithm. Moreover, experimental results show that this strategy is able to generate approximations with an associated error that is hard to reach for different multi-start methods, such as multi-start Forgy$K$-means,$K$-means++ and Hartigan$K$-means, while also computing a lower amount of distances than the previous algorithms.

Nowadays, streaming data analysis has become a relevant area of research in machine learning. Most of the data streams available are unlabeled, and thus it is necessary to develop specific clustering techniques that take into account the particularities of the streaming data. In streaming data scenarios, the data is composed of an increasing sequence of batches of samples where the concept drift phenomenon may occur. In this work, we formally define the streaming K -means (SKM) problem, which implies a restart of the error function when a concept drift occurs. An approximated error function that does not rely on concept drift detection is proposed. We prove that such a surrogate is a good approximation of the SKM error. Then, we introduce an algorithm to deal with SKM problem by minimizing the surrogate error function each time a new batch arrives. Alternative initialization criteria are presented and theoretically analyzed for streaming data scenarios. Among them, we develop and analyze theoretically two initialization methods that search for the best trade-off between the importance that is given to the past and the current batches. The experiments show that the proposed algorithm with, the proposed initialization criteria, obtain the best results when dealing with the SKM problem without requiring to detect when concept drift takes place.

The increase in the number of features that need to be analyzed in a wide variety of areas, such as genome sequencing, computer vision, or sensor networks, represents a challenge for the K -means algorithm. In this regard, different dimensionality reduction approaches for the K -means algorithm have been designed recently, leading to algorithms that have proved to generate competitive clusterings. Unfortunately, most of these techniques tend to have fairly high computational costs and/or might not be easy to parallelize. In this article, we propose a fully parallelizable feature selection technique intended for the K -means algorithm. The proposal is based on a novel feature relevance measure that is closely related to the K -means error of a given clustering. Given a disjoint partition of the features, the technique consists of obtaining a clustering for each subset of features and selecting the m features with the highest relevance measure. The computational cost of this approach is just O(m·max{n·K,logm}) per subset of features. We additionally provide a theoretical analysis on the quality of the obtained solution via our proposal and empirically analyze its performance with respect to well-known feature selection and feature extraction techniques. Such an analysis shows that our proposal consistently obtains the results with lower K -means error than all the considered feature selection techniques: Laplacian scores, maximum variance, multicluster feature selection, and random selection while also requiring similar or lower computational times than these approaches. Moreover, when compared with feature extraction techniques, such as random projections, the proposed approach also shows a noticeable improvement in both error and computational time.

Different types of training data have led to numerous schemes for supervised classification. Current learning techniques are tailored to one specific scheme and cannot handle general ensembles of training samples. This paper presents a unifying framework for supervised classification with general ensembles of training samples, and proposes the learning methodology of generalized robust risk minimization (GRRM). The paper shows how current and novel supervision schemes can be addressed under the proposed framework by representing the relationship between examples at prediction and training via probabilistic transformations. The results show that GRRM can handle different types of training samples in a unified manner, and enable new supervision schemes that aggregate general ensembles of training samples.

Supervised classification techniques use training samples to find classification rules with small expected 0-1 loss. Conventional methods achieve efficient learning and out-of-sample generalization by minimizing surrogate losses over specific families of rules. This paper presents minimax risk classifiers (MRCs) that do not rely on a choice of surrogate loss and family of rules. MRCs achieve efficient learning and out-of-sample generalization by minimizing worst-case expected 0-1 loss w.r.t. uncertainty sets that are defined by linear constraints and include the true underlying distribution. In addition, MRCs' learning stage provides performance guarantees as lower and upper tight bounds for expected 0-1 loss. We also present MRCs' finite-sample generalization bounds in terms of training size and smallest minimax risk, and show their competitive classification performance w.r.t. state-of-the-art techniques using benchmark datasets.

In the field of evolutionary computation, it is usual to generate artificial benchmarks of instances that are used as a test-bed to determine the performance of the algorithms at hand. In this context, a recent work on permutation problems analyzed the implications of generating instances uniformly at random (u.a.r.) when building those benchmarks. Particularly, the authors analyzed instances as rankings of the solutions of the search space sorted according to their objective function value. Thus, two instances are considered equivalent when their objective functions induce the same ranking over the search space. Based on the analysis, they suggested that, when some restrictions hold, the probability to create easy rankings is higher than creating difficult ones. In this paper, we continue on that research line by adopting the framework of local search algorithms with the best improvement criterion. Particularly, we empirically analyze, in terms of difficulty, the instances (rankings) created u.a.r. of three popular problems: Linear Ordering Problem, Quadratic Assignment Problem and Flowshop Scheduling Problem. As the neighborhood system is critical for the performance of local search algorithms three different neighborhood systems have been considered: swap, interchange and insert. Conducted experiments reveal that (1) by sampling the parameters uniformly at random we obtain instances with a non-uniform distribution in terms of difficulty, (2) the distribution of the difficulty strongly depends on the pair problem-neighborhood considered, and (3) given a problem, the distribution of the difficulty seems to depend on the smoothness of the landscape induced by the neighborhood and on its size.

The applicability of time series data mining in many different fields has motivated the scientific community to focus on the development of new methods towards improving the performance of the classifiers over this particular class of data. In this context the related literature has extensively shown that dynamic time warping is the similarity measure of choice when univariate time series are considered. However, possible statistical coupling among different dimensions make the generalization of this metric to the multivariate case all but obvious. This has ignited the interest of the community in new distance definitions capable of capturing such inter-dimension dependences. In this paper we propose a simple dynamic time warping based distance that finds the best weighted combination between the dependent - where multivariate time series are treated as whole - and independent approaches - where multivariate time series are just a collection of unrelated univariate time series - of the time series to be classified. A benchmark of four heuristic wrappers, namely, simulated annealing, particle swarm optimization, estimation of distribution algorithms and genetic algorithms are used to evolve the set of weighting coefficients towards maximizing the cross-validated predictive score of the classifiers. In this context one of the most recurring classifiers is nearest neighbor. This classifier is couple with a distance that as afore mentioned, in most cases, have been dynamic time warping. The performance of the proposed approach is validated over datasets widely utilized in the related literature, from which it is concluded that the obtained performance gains can be enlarged by properly decoupling the influence of each dimension in the definition of the dependent dynamic time warping distance.

Multiple sclerosis is an autoimmune disorder of the central nervous system and potentially the most common cause of neurological disability in young adults. The clinical disease course is highly variable and different multiple sclerosis subtypes can be defined depending on the progression of the severity of the disease. In the early stages, the disease subtype is unknown, and there is no information about how the severity is going to evolve. As there are different treatment options available depending on the progression of the disease, early identification has become highly relevant. Thus, given a new patient, it is important to diagnose the disease subtype. Another relevant information to predict is the expected time to reach a severity level indicating that assistance for walking is required. Given that we have to predict two correlated class variables: disease subtype and time to reach certain severity level, we use multidimensional Bayesian network classifiers because they can model and exploit the relations among both variables. Besides, the obtained models can be validated by the physicians using their expert knowledge due to the interpretability of Bayesian networks. The learning of the classifiers is made by means of a novel multiobjective approach which tries to maximize the accuracy of both class variables simultaneously. The application of the methodology proposed in this paper can help a physician to identify the expected progression of the disease and to plan the most suitable treatment.

In the machine learning field, the performance of a classifier is usually measured in terms of prediction error. In most real-world problems, the error cannot be exactly calculated and it must be estimated. Therefore, it is important to choose an appropriate estimator of the error. This paper analyzes the statistical properties, bias and variance, of the kappa-fold cross-validation classification error estimator (kappa-cv). Our main contribution is a novel theoretical decomposition of the variance of the kappa-cv considering its sources of variance: sensitivity to changes in the training set and sensitivity to changes in the folds. The paper also compares the bias and variance of the estimator for different values of kappa. The experimental study has been performed in artificial domains because they allow the exact computation of the implied quantities and we can rigorously specify the conditions of experimentation. The experimentation has been performed for two classifiers (naive Bayes and nearest neighbor), different numbers of folds, sample sizes, and training sets coming from assorted probability distributions. We conclude by including some practical recommendation on the use of kappa-fold cross validation.

This article reviews machine learning methods for bioinformatics. It presents modelling methods, such as supervised classification, clustering and probabilistic graphical models for knowledge discovery, as well as deterministic and stochastic heuristics for optimization. Applications in genomics, proteomics, systems biology, evolution and text mining are also shown.