Search

With unlabeled and high-dimensional data explosion, unsupervised feature selection has become an essential step in many machine learning and data mining tasks. Many dictionary learning based models have been successfully developed for unsupervised feature selection in recent years. These models learn an over-complete dictionary to investigate more data distribution information. However, over-complete dictionary learning will generate redundancy in the latent representations for data. Moreover, if data contain noise, dictionary learning will also yield noise in the latent representations. In this paper, we propose a novel unsupervised feature selection framework, named dictionary learning for unsupervised feature selection via dual sparse regression. In this model, dictionary learning is first embedded into a sparse regression to learn an over-complete dictionary with sparse representations for data, in which the redundancy and noise are eliminated. The data are then projected to the representations to evaluate the significance of features using the other sparse regression. We also offer an efficient algorithm to solve this problem and theoretically analyze its convergence and computational complexity, which is proportional to the data dimensionality. Finally, the evaluation results with the k-means task utilizing the selected features on 9 benchmark datasets demonstrate the superiority of our approach in terms of effectiveness and efficiency. [ABSTRACT FROM AUTHOR]

Originally, tangles were invented as an abstract tool in mathematical graph theory to prove the famous graph minor theorem. In this paper, we showcase the practical potential of tangles in machine learning applications. Given a collection of cuts of any dataset, tangles aggregate these cuts to point in the direction of a dense structure. As a result, a cluster is softly characterized by a set of consistent pointers. This highly flexible approach can solve clustering problems in various setups, ranging from questionnaires over community detection in graphs to clustering points in metric spaces. The output of our proposed framework is hierarchical and induces the notion of a soft dendrogram, which can help explore the cluster structure of a dataset. The computational complexity of aggregating the cuts is linear in the number of data points. Thus the bottleneck of the tangle approach is to generate the cuts, for which simple and fast algorithms form a sufficient basis. In our paper we construct the algorithmic framework for clustering with tangles, prove theoretical guarantees in various settings, and provide extensive simulations and use cases. Python code is available on github. [ABSTRACT FROM AUTHOR]

One of the crucial challenges of solving many-objective optimization problems is uniformly well covering of the Pareto-front (PF). However, many the state-of-the-art optimization algorithms are capable of approximating the shape of many-objective PF by generating a limited number of non-dominated solutions. The exponential increase of the population size is an inefficient strategy that increases the computational complexity of the algorithm dramatically—especially when solving many-objective problems. In this paper, we introduce a machine learning-based framework to cover sparse PF surface which is initially generated by many-objective optimization algorithms; either by classical or meta-heuristic methods. The proposed method, called many-objective reverse mapping (MORM), is based on constructing a learning model on the initial PF set as the training data to reversely map the objective values to corresponding decision variables. Using the trained model, a set of candidate solutions can be generated by a variety of inexpensive generative techniques such as Opposition-based Learning and Latin Hypercube Sampling in both objective and decision spaces. Iteratively generated non-dominated candidate solutions cover the initial PF efficiently with no further need to utilize any optimization algorithm. We validate the proposed framework using a set of well-known many-objective optimization benchmarks and two well-known real-world problems. The coverage of PF is illustrated and numerically compared with the state-of-the-art many-objective algorithms. The statistical tests conducted on comparison measures such as HV, IGD, and the contribution ratio on the built PF reveal that the proposed collaborative framework surpasses the competitors on most of the problems. In addition, MORM covers the PF effectively compared to other methods even with the aid of large population size. [ABSTRACT FROM AUTHOR]

This paper considers the offline assignment of fixed priorities in partitioned preemptive real-time systems where tasks have precedence constraints. This problem is crucial in this type of systems, as having a good fixed priority assignment allows for an efficient use of the processing resources while meeting all the deadlines. In the literature, we can find several proposals to solve this problem, which offer varying trade-offs between the quality of their results and their computational complexities. In this paper , we propose a new approach, leveraging existing algorithms that are widely exploited in the field of Machine Learning: Gradient Descent, the Adam Optimizer, and Gradient Noise. We show how to adapt these algorithms to the problem of fixed priority assignment in conjunction with existing worst-case response time analyses. We demonstrate the performance of our proposal on synthetic task-sets with different sizes. This evaluation shows that our proposal is able to find more schedulable solutions than previous heuristics, approximating optimal but intractable algorithms such as MILP or brute-force, while requiring reasonable execution times. [ABSTRACT FROM AUTHOR]

This paper addresses the problem of open shop scheduling on two machines with resources constraints. In the context of our study, in order to be executed, a job requires first, for its preparation for a given period of time, a number of resources which cannot exceed a given resource capacity. Then, it goes onto its execution while the resources allocated to it become available again. We seek a schedule that minimizes the makespan. We first prove the $\mathcal{N}\mathcal{P}$ -hardness of several versions of this problem. Then, we present a well solvable case, lower bounds, and heuristic algorithms along with an experimental study. [ABSTRACT FROM AUTHOR]

Bottom-up saliency detection aims to detect salient areas within natural images usually without learning from labeled images. Typically, the saliency map of an image is inferred by only using the information within this image (referred to as the “current image”). While efficient, such single-image-based methods may fail to obtain reliable results, because the information within a single image may be insufficient for defining saliency. In this paper, we investigate how saliency detection can benefit from the nearest neighbor structure in the image space. First, we show that existing methods can be improved by extending them to include the visual neighborhood information. This verifies the significance of the neighbors. Next, a solution of multitask sparsity pursuit is proposed to integrate the current image and its neighbors to collaboratively detect saliency. The integration is done by first representing each image as a feature matrix, and then seeking the consistently sparse elements from the joint decompositions of multiple matrices into pairs of low-rank and sparse matrices. The computational procedure is formulated as a constrained nuclear norm and \ell2,1-norm minimization problem, which is convex and can be solved efficiently with the augmented Lagrange multiplier method. Besides the nearest neighbor structure in the visual feature space, the proposed model can also be generalized to handle multiple visual features. Extensive experiments have clearly validated its superiority over other state-of-the-art methods. [ABSTRACT FROM PUBLISHER]

The traditional vector-based classifiers, such as support vector machine (SVM) and twin support vector machine (TSVM), cannot handle tensor data directly and may not utilize the data informations effectively. In this paper, we propose a novel classifier based on tensor data, called twin bounded support tensor machine (TBSTM) which is an extension of twin bounded support vector machine (TBSVM). Similar to TBSVM, TBSTM gets two hyperplanes and obtains the solution by solving two quadratic programming problems (QPPs). The computational complexity of each QPPs is smaller than that of support tensor machine (STM). TBSTM not only retains the advantage of TBSVM, but also has its unique superior characteristics: (1) it makes full use of the structure information of data; (2) it has acceptable or better classification accuracy compared to STM, TBSVM and SVM; (3) the computational cost is basically less than STM; (4) it can deal with large data that TBSVM is not easy to achieve, especially for small-sample-size (S3) problems; (5) it adopts alternating successive over relaxation iteration (ASOR) method to solve optimization problems which accelerates the pace of training. Finally, we demonstrate the effectiveness and superiority by the experiments based on vector and tensor data. [ABSTRACT FROM AUTHOR]

Object detection in outdoor environments is a challenging task. One is not only confronted with the problem of acquiring a sufficient amount of training images, but also the issue of huge variation in the objects appearance due to changing weather and light conditions. When using appearance-based object detection algorithms, such as in this paper, dimensional reduction of input data is an integral component to reduce computational costs and improve reliability. Based on the probabilistic classification method of Gaussian classifiers this paper examines the effect different dimensional reduction approaches have on the classification performance of thermal infra-red object images with respect to incomplete training data. It is shown that in the detection task at hand, which is to find the rear end of a truck in a thermal infra-red image, a reduction approach that combines principal component analysis (PCA) and linear discriminant analysis (LDA) is less sensitive to missing data. [ABSTRACT FROM AUTHOR]

In this paper, we use shape grammars (SGs) for facade parsing, which amounts to segmenting 2D building facades into balconies, walls, windows, and doors in an architecturally meaningful manner. The main thrust of our work is the introduction of reinforcement learning (RL) techniques to deal with the computational complexity of the problem. RL provides us with techniques such as Q-learning and state aggregation which we exploit to efficiently solve facade parsing. We initially phrase the 1D parsing problem in terms of a Markov Decision Process, paving the way for the application of RL-based tools. We then develop novel techniques for the 2D shape parsing problem that take into account the specificities of the facade parsing problem. Specifically, we use state aggregation to enforce the symmetry of facade floors and demonstrate how to use RL to exploit bottom-up, image-based guidance during optimization. We provide systematic results on the Paris building dataset and obtain state-of-the-art results in a fraction of the time required by previous methods. We validate our method under diverse imaging conditions and make our software and results available online. [ABSTRACT FROM AUTHOR]

A large class of problems of sequential decision making under uncertainty, of which the underlying probability structure is a Markov process, can be modeled as stochastic dynamic programs (referred to, in general, as Markov decision problems or MDPs). However, the computational complexity of the classical MDP algorithms, such as value iteration and policy iteration, is prohibitive and can grow intractably with the size of the problem and its related data. Furthermore, these techniques require for each action the one step transition probability and reward matrices, and obtaining these is often unrealistic for large and complex systems. Recently, there has been much interest in a simulation-based stochastic approximation framework called reinforcement learning (RL), for computing near optimal policies for MDPs. RL has been successfully applied to very large problems, such as elevator scheduling, and dynamic channel allocation of cellular telephone systems. In this paper, we extend RL to a more general class of decision tasks that are referred to as semi-Markov decision problems (SMDPs). In particular, we focus on SMDPs under the average-reward criterion. We present a new model-free RL algorithm called SMART (Semi-Markov Average Reward Technique). We present a detailed study of this algorithm on a combinatorially large problem of determining the optimal preventive maintenance schedule of a production inventory system. Numerical results from both the theoretical model and the RL algorithm are presented and compared. [ABSTRACT FROM AUTHOR]

Even though evolutionary algorithm (EA) has now become the standard and paradigm for solving multi-objective design problems, the complexity of its genetic operation is, however, limiting its popularity in engineering applications. Hitherto, there has been insufficient research that addresses the inadequacy of EAs in extracting the characteristic landscape features of an objective function. However, increasing attentions have now been devoted to EAs based on probabilistic models (EAPMs) in computational intelligence studies. A real coded scalar population-based incremental learning algorithm, an EAPM, is proposed for multi-objective optimizations of electromagnetic devices. Major improvements include the design of a generating mechanism for new intermediate solutions, the selection of elite solutions to update the probability matrix, matrix updating formulations, and refinement mechanism for intervals to precisely generate intermediate solution. Also, a methodology to consider quantitatively both the number of improved objectives and the amount of improvements in a specified objective of multi-objective design problems is introduced in fitness assignments. Numerical results on a high frequency and a low inverse problem are reported to showcase the merits of the proposed algorithm. [ABSTRACT FROM AUTHOR]

Advances in mathematical models and optimization introduce powerful tools for solving the visual object tracking problem, but this fundamental problem remains unsolved due to various challenges such as illumination variation, deformation and occlusion. Recent progress in correlation filter based models has provided an effective and efficient tracking solution. This type of trackers exploits the property of convolution theorem to significantly speed up their computational processes. However, their scheme of training correlation filters restricts them to use only a few negative examples to train their model, consequently lowers their performance. Therefore, in this paper, we propose to combine the fast calculation advantage of correlation filter with an online discriminative learning model, which can fully exploit the negative examples in the context around the target. The proposed tracker proceeds in a coarse-to-fine scheme: the proposed tracker will first employ a correlation filter to generate a coarse estimation of the location of the target, and then employ a translating model to refine its estimation and calculate the scale variation of the target via a scaling model. Both the translating model and the scaling model are formulated in the framework of our online discriminative model. Besides, we also propose an effective offline representation learning method to generate robust image feature for our correlation filter. Extensive experiments on the online Object Tracking Benchmark against the state-of-the-art methods validate the effectiveness of the proposed tracker. [ABSTRACT FROM AUTHOR]

The Job shop Scheduling Problem (JSP) is one of the most known problems in the domain of the production task scheduling. The Dual-Resource Constrained Job shop Scheduling Problem (DRCJSP) and the Dual-Resource Constrained Flexible Job shop Scheduling Problem (DRCFJSP) are two extensions of the classical JSP consisting of three sub-problems: (i) Assigning operations to resources of machines, (ii) Assigning operations to resources of workers; (iii) Sequencing the operations on the machines considering workers in order to optimize the performance measure. In this paper, we make a state-of-the-art review of the different works proposed for the DRCJSP and DRCFJSP, where we present a new classification schema according to six criteria such as the used method, the machine flexibility, the worker flexibility, the optimization criteria, the implemented approaches, and the structure of the approach. [ABSTRACT FROM AUTHOR]

The detection and location of objects concealed under clothing is a very challenging task that has crucial applications in security. In this domain, passive millimeter-wave images (PMMWIs) can be used. However, the quality of the acquired images, and the unknown position, shape, and size of hidden objects render this task difficult. In this paper, we propose a machine learning-based solution to this detection/localization problem. Our method outperforms currently used approaches. The effect of non-stationary noise on different classification algorithms is analyzed and discussed, and a detailed experimental comparative study of classification techniques is presented using a new and comprehensive PMMWI database. The low computational testing cost of this solution allows for its use in real-time applications. [ABSTRACT FROM AUTHOR]

The article presents an approach based on machine learning with symbolic regression for the synthesis of a stabilization system for a mobile robot. This approach is universal and allows you to numerically solve the synthesis problem in a general setting without the need to form a training sample, instead relying only on the value of the functional. The synthesis is implemented to stabilize the mobile robot Rosbot in the Gazebo simulation environment. The feedback stabilization system is received by the network operator method. The advantage of the method is that it can be applied to a control object of any complexity and linearity. [ABSTRACT FROM AUTHOR]

Skeleton-based action recognition can achieve a relatively high performance by transforming the human skeleton structure in an image into a graph and applying action recognition based on structural changes in the body. Among the many graph convolutional network (GCN) approaches used in skeleton-based action recognition, semantic-guided neural networks (SGNs) are fast action recognition algorithms that hierarchically learn spatial and temporal features by applying a GCN. However, because an SGN focuses on global feature learning rather than local feature learning owing to the structural characteristics, there is a limit to an action recognition in which the dependency between neighbouring nodes is important. To solve these problems and simultaneously achieve a real-time action recognition in low-end devices, in this study, a single head attention (SHA) that can overcome the limitations of an SGN is proposed, and a new SGN-SHA model that combines SHA with an SGN is presented. In experiments on various action recognition benchmark datasets, the proposed SGN-SHA model significantly reduced the computational complexity while exhibiting a performance similar to that of an existing SGN and other state-of-the-art methods. [ABSTRACT FROM AUTHOR]

In distributed computing/storage/machine learning system, the method of encoding and decoding combing shift-and-addition (SA) and zigzag decoding (ZD) is proposed to solve the problem of high computational complexity. However, in each encoded packet, one element takes part in the encoding only once, so the obtained overhead is extremely high. In this work, based on the idea of multidimensional encoding/modulation, we propose to employ one element of the encoding process multiple times when constructing one encoded packet based on the Cauchy matrix, thereby leveraging the favourable properties of the code based on Cauchy matrix. The overhead is reduced from square to logarithmic in certain parameters. Compared with the overhead of the existing square computational complexity, it is greatly reduced. [ABSTRACT FROM AUTHOR]

As the size and service requirements of today's networks gradually increase, large numbers of proprietary devices are deployed, which leads to network complexity, information security crises and makes network service and service provider management increasingly difficult. Network function virtualization (NFV) technology is one solution to this problem. NFV separates network functions from hardware and deploys them as software on a common server. NFV can be used to improve service flexibility and isolate the services provided for each user, thus guaranteeing the security of user data. Therefore, the use of NFV technology includes many problems worth studying. For example, when there is a free choice of network path, one problem is how to choose a service function chain (SFC) that both meets the requirements and offers the service provider maximum profit. Most existing solutions are heuristic algorithms with high time efficiency, or integer linear programming (ILP) algorithms with high accuracy. It's necessary to design an algorithm that symmetrically considers both time efficiency and accuracy. In this paper, we propose the Q-learning Framework Hybrid Module algorithm (QLFHM), which includes reinforcement learning to solve this SFC deployment problem in dynamic networks. The reinforcement learning module in QLFHM is responsible for the output of alternative paths, while the load balancing module in QLFHM is responsible for picking the optimal solution from them. The results of a comparison simulation experiment on a dynamic network topology show that the proposed algorithm can output the approximate optimal solution in a relatively short time while also considering the network load balance. Thus, it achieves the goal of maximizing the benefit to the service provider. [ABSTRACT FROM AUTHOR]

Decomposition hybrid algorithms with the recursive framework which recursively decompose the structural task into structural subtasks to reduce computational complexity are employed to learn Bayesian network (BN) structure. Merging rules are commonly adopted as the combination method in the combination step. The direction determination rule of merging rules has problems in using the idea of keeping v-structures unchanged before and after combination to determine directions of edges in the whole structure. It breaks down in one case due to appearances of wrong v-structures, and is hard to operate in practice. Therefore, we adopt a novel approach for direction determination and propose a two-stage combination method. In the first-stage combination method, we determine nodes, links of edges by merging rules and adopt the idea of permutation and combination to determine directions of contradictory edges. In the second-stage combination method, we restrict edges between nodes that do not satisfy the decomposition property and their parent nodes by determining the target domain according to the decomposition property. Simulation experiments on four networks show that the proposed algorithm can obtain BN structure with higher accuracy compared with other algorithms. Finally, the proposed algorithm is applied to the thickening process of gold hydrometallurgy to solve the practical problem. [ABSTRACT FROM AUTHOR]

For blended data, the robustness of extreme learning machine (ELM) is so weak because the coefficients (weights and biases) of hidden nodes are set randomly and the noisy data exert a negative effect. To solve this problem, a new framework called "RMSEELM" is proposed in this paper. It is a two-layer recursive model. In the first layer, the framework trains lots of ELMs in different ensemble groups concurrently and then employs selective ensemble approach to pick out an optimal set of ELMs in each group, which can be merged into a large group of ELMs called candidate pool. In the second layer, selective ensemble approach is recursively used on candidate pool to acquire the final ensemble. In the experiments, we apply UCI blended datasets to confirmthe robustness of our new approach in two key aspects (mean square error and standard deviation). The space complexity of ourmethod is increased to some degree, but the result has shown that RMSE-ELM significantly improves robustness with a rapid learning speed compared to representative methods (ELM, OP-ELM, GASEN-ELM, GASEN-BP, and E-GASEN). It becomes a potential framework to solve robustness issue of ELM for high-dimensional blended data in the future. [ABSTRACT FROM AUTHOR]

• A framework of building energy modeling for data predictive control is developed. • The framework integrates active learning strategy with feature selection technique. • The framework is demonstrated in a virtual testbed (EnergyPlus and BCVTB). • The case study shows improvement in energy modeling accuracy and DPC performance. Three gaps impede the development of cost-effective and accurate data-driven building energy modeling/models (DBEM) for energy forecasting and predictive control strategies. Gap 1: data bias is common in building operation data, but this topic is hardly studied in DBEM; Gap 2: high data dimensionality is common in DBEM, but a systematic and scalable methodology is lacking to solve the problem; Gap 3: the interactions between data bias and high dimensionality have not been systematically studied for DBEM and predictive control in buildings. In this paper, to address the three gaps mentioned above, we develop a framework that integrates active learning and feature selection for DBEM used for whole building data predictive control (or DPC, which is a branch of model predictive control). The framework provides a systematic methodology and automatic workflow that starts with raw data from building automation systems to the establishment of data-driven energy models for DPC controllers. The developed strategies and framework are evaluated in a virtual testbed based on EnergyPlus and BCVTB. Improved performance and reduced computational complexity are observed from the DBEM built with the developed framework, as well as the DPC controller based on that DBEM, indicating the effectiveness of the developed framework. [ABSTRACT FROM AUTHOR]

Stochastic Gradient Descent (SGD) has become popular for solving large scale supervised machine learning optimization problems such as SVM, due to their strong theoretical guarantees. While the closely related Dual Coordinate Ascent (DCA) method has been implemented in various software packages, it has so far lacked good convergence analysis. This paper presents a new analysis of Stochastic Dual Coordinate Ascent (SDCA) showing that this class of methods enjoy strong theoretical guarantees that are comparable or better than SGD. This analysis justifies the effectiveness of SDCA for practical applications. [ABSTRACT FROM AUTHOR]

Abstract: In previous works we found necessary conditions for a cellular automaton (CA) in order to be intrinsically universal (a CA is said to be intrinsically universal if it can simulate any other). The idea was to introduce different canonical communication problems, all of them parameterized by a CA. The necessary condition was the following: if is an intrinsically universal CA then the communication complexity of all the canonical problems, when parameterized by , must be maximal. In this paper, instead of introducing a new canonical problem, we study the setting where they can all be used simultaneously. Roughly speaking, when and –the two parties of the communication complexity model–receive their inputs they may choose online which canonical problem to solve. We give results showing that such freedom makes this new problem, that we call , a very strong filter for ruling out CAs from being intrinsically universal. More precisely, there are some CAs having high complexity in all the canonical problems but have much lower complexity in . [Copyright &y& Elsevier]

Echo state networks are a relatively new type of recurrent neural networks that have shown great potentials for solving nonlinear, temporal problems. The basic idea is to transform the low dimensional temporal input into a higher dimensional state, and then train the output connection weights to make the system output the target information. Because only the output weights are altered, training is typically quick and computationally efficient compared to training of other recurrent neural networks. This paper investigates using an echo state network to learn the inverse kinematics model of a robot simulator with feedback-error-learning. In this scheme teacher forcing is not perfect, and joint constraints on the simulator makes the feedback error inaccurate. A novel training method which is less influenced by the noise in the training data is proposed and compared to the traditional ESN training method. [ABSTRACT FROM AUTHOR]

This paper presents novel algorithms and applications for a particular class of mixed-norm regularization based Multiple Kernel Learning (MKL) formulations. The formulations assume that the given kernels are grouped and employ l1 norm regularization for promoting sparsity within RKHS norms of each group and ls, s ≥ 2 norm regularization for promoting non-sparse combinations across groups. Various sparsity levels in combining the kernels can be achieved by varying the grouping of kernels--hence we name the formulations as Variable Sparsity Kernel Learning (VSKL) formulations. While previous attempts have a non-convex formulation, here we present a convex formulation which admits efficient Mirror-Descent (MD) based solving techniques. The proposed MD based algorithm optimizes over product of simplices and has a computational complexity of O(m²ntot log nmax/ε² where m is no. training data points, nmax, ntot are the maximum no. kernels in any group, total no. kernels respectively and e is the error in approximating the objective. A detailed proof of convergence of the algorithm is also presented. Experimental results show that the VSKL formulations are well-suited for multi-modal learning tasks like object categorization. Results also show that the MD based algorithm outperforms state-of-the-art MKL solvers in terms of computational efficiency. [ABSTRACT FROM AUTHOR]

Incremental learning is a methodology that continuously uses the sequential input data to extend the existing network's knowledge. The layer sharing algorithm is one of the representative methods which leverages general knowledge by sharing some initial layers of the existing network. To determine the performance of the incremental network, it is critical to estimate how much the initial convolutional layers in the existing network can be shared as the fixed feature extractors. However, the existing algorithm selects the sharing configuration through improper optimization strategy but a brute force manner such as searching for all possible sharing layers case. This is a non-convex and non-differential problem. Accordingly, this can not be solved using powerful optimization techniques such as the gradient descent algorithm or other convex optimization problem, and it leads to high computational complexity. To solve this problem, we firstly define this as a discrete combinatorial optimization problem, and propose a novel efficient incremental learning algorithm-based Bayesian optimization, which guarantees the global convergence in a non-convex and non-differential optimization. Additionally, our proposed algorithm can adaptively find the optimal number of sharing layers via adjusting the threshold accuracy parameter in the proposed loss function. With the proposed method, the global optimal sharing layer can be found in only six or eight iterations without searching for all possible layer cases. Hence, the proposed method can find the global optimal sharing layers by utilizing Bayesian optimization, which achieves both high combined accuracy and low computational complexity. [ABSTRACT FROM AUTHOR]

Proofs of strong NP-hardness of single machine and two-machine flowshop scheduling problems with learning or aging effect given in Rudek (Computers & Industrial Engineering 61:20-31, ; Annals of Operations Research 196(1):491-516, ; International Journal of Advanced Manufacturing Technology 59:299-309, ; Applied Mathematics and Computations 218:6498-6510, ; Applied Mathematical Modelling 37:1523-1536, ) contain a common mistake that make them incomplete. We reveal the mistake and provide necessary corrections for the problems in Rudek (Computers & Industrial Engineering 61:20-31, ; Annals of Operations Research 196(1):491-516, ; Applied Mathematical Modelling 37:1523-1536, ). NP-hardness of problems in Rudek (International Journal of Advanced Manufacturing Technology 59:299-309, ; Applied Mathematics and Computations 218:6498-6510, ) remains unknown because of another mistake which we are unable to correct. [ABSTRACT FROM AUTHOR]

The NP-hard maximum monomial agreement problem consists of finding a single logical conjunction that is most consistent with or "best fits" a weighted data set of "positive" and "negative" binary vectors. Computing weighted voting classifiers using boosting methods involves a maximum agreement subproblem at each iteration, although such subproblems are typically solved in practice by heuristic methods. Here, we describe an exact branch-and-bound method for maximum agreement over Boolean monomials, improving on the earlier work of Goldberg and Shan [Goldberg, N., C. Shan. 2007. Boosting optimal logical patterns. Proc. 7th SIAM Internat. Conf. Data Mining, SIAM, Philadelphia, 228-236]. Specifically, we develop a tighter upper bounding function and an improved branching procedure that exploits knowledge of the bound and the particular data set, while having a lower branching factor. Experimental results show that the new method is able to solve larger problem instances and runs faster within a linear programming boosting procedure applied to medium-sized data sets from the UCI Machine Learning Repository. The new algorithm also runs much faster than applying a commercial mixed-integer programming solver, which uses linear programming relaxation-based bounds, to an integer linear programming formulation of the problem. [ABSTRACT FROM AUTHOR]