Two-Stage Nested Partitions Method for Stochastic Optimization

We address the problem of optimizing over a large but finite set when the objective function does not have an analytical expression and is evaluated using noisy estimation. Building on the recently proposed nested partitions method for stochastic optimization, we develop a new approach that combines this random search method and statistical selection for guiding the search. We prove asymptotic convergence and analyze the finite time behavior of the new approach. We also report extensive numerical results to illustrate the benefits of the new approach.     

Nested Partitions Method for Stochastic Optimization

The nested partitions (NP) method is a recently proposed new alternative for global optimization. Primarily aimed at problems with large but finite feasible regions, the method employs a global sampling strategy that is continuously adapted via a partitioning of the feasible region. In this paper we adapt the original NP method to stochastic optimization where the performance is estimated using simulation. We prove asymptotic convergence of the new method and present a numerical example to illustrate its potential.     

A fast meta-heuristic approach for the $$(\alpha ,\beta )-k$$-feature set problem

The feature selection problem aims to choose a subset of a given set of features that best represents the whole in a particular aspect, preserving the original semantics of the variables on the given samples and classes. In 2004, a new approach to perform feature selection was proposed. It was based on a NP-complete combinatorial optimisation problem called (\(\alpha ,\beta \))-k-feature set problem. Although effective for many practical cases, which made the approach an important feature selection tool, the only existing solution method, proposed on the original paper, was found not to work well for several instances. Our work aims to cover this gap found on the literature, quickly obtaining high quality solutions for the instances that existing approach can not solve. This work proposes a heuristic based on the greedy randomised adaptive search procedure and tabu search to address this problem; and benchmark instances to evaluate its performance. The computational results show that our method can obtain high quality solutions for both real and the proposed artificial instances and requires only a fraction of the computational resources required by the state of the art exact and heuristic approaches which use mixed integer programming models.     

A partial order for the set of meanders

In this paper, we present a new approach for studying meanders in terms of noncrossing partitions. We show how this approach leads to a natural partial order on the set of meanders. In particular, meanders form a graded poset with regard to this partial order.     

An efficient method for feature selection in linear regression based on an extended Akaike’s information criterion

A method for feature selection in linear regression based on an extension of Akaike’s information criterion is proposed. The use of classical Akaike’s information criterion (AIC) for feature selection assumes the exhaustive search through all the subsets of features, which has unreasonably high computational and time cost. A new information criterion is proposed that is a continuous extension of AIC. As a result, the feature selection problem is reduced to a smooth optimization problem. An efficient procedure for solving this problem is derived. Experiments show that the proposed method enables one to efficiently select features in linear regression. In the experiments, the proposed procedure is compared with the relevance vector machine, which is a feature selection method based on Bayesian approach. It is shown that both procedures yield similar results. The main distinction of the proposed method is that certain regularization coefficients are identical zeros. This makes it possible to avoid the underfitting effect, which is a characteristic feature of the relevance vector machine. A special case (the so-called nondiagonal regularization) is considered in which both methods are identical.     

Note on enumeration of partitions contained in a given shape

Carlitz, Handa, and Mohanty proved determinantal formulas for counting partitions contained in a fixed bounding shape by area. Gessel and Viennot introduced a combinatorial method for proving such formulas by interpreting the determinants as counting suitable configurations of signed lattice paths. This note describes an alternative combinatorial approach that uses sign-reversing involutions to prove matrix inversion results. Combining these results with the classical adjoint formula for the inverse of a matrix, we obtain a new derivation of the Handa–Mohanty determinantal formula.     

Modeling defaults with nested Archimedean copulas

In 2001, Schönbucher and Schubert extended Li’s well-known Gaussian copula model for modeling dependent defaults to allow for tail dependence. Instead of the Gaussian copula, Schönbucher and Schubert suggested to use Archimedean copulas. These copulas are able to capture tail dependence and therefore allow a standard intensity-based default model to have a positive probability of joint defaults within a short time period. As can be observed in the current financial crisis, this is an indispensable feature of any realistic default model. Another feature, motivated by empirical observations but rarely taken into account in default models, is that modeled portfolio components affected by defaults show significantly different levels of dependence depending on whether they belong to the same industry sector or not. The present work presents an extension of the model suggested by Schönbucher and Schubert to account for this fact. For this, nested Archimedean copulas are applied. As an application, the pricing of collateralized debt obligations is treated. Since the resulting loss distribution is not analytical tractable, fast sampling algorithms for nested Archimedean copulas are developed. Such algorithms boil down to sampling certain distributions given by their Laplace-Stieltjes transforms. For a large range of nested Archimedean copulas, efficient sampling techniques can be derived. Moreover, a general transformation of an Archimedean generator allows to construct and sample the corresponding nested Archimedean copulas.     

On the discovery of events in EEG data utilizing information fusion

One way to tackle brain computer interfaces is to consider event related potentials in electroencephalography, like the well established P300 phenomenon. In this paper a multiple classifier approach to discover these events in the bioelectrical signal and with them whether or not a subject has recognized a particular pattern, is employed. Dealing with noisy data as well as heavily imbalanced target class distributions are among the difficulties encountered. Our approach utilizes partitions of electrodes to create robust and meaningful individual classifiers, which are then subsequently combined using decision fusion. Furthermore, a classifier selection approach using genetic algorithms is evaluated and used for optimization. The proposed approach utilizing information fusion shows promising results (over 0.8 area under the ROC curve).     

An efficient random forests algorithm for high dimensional data classification

In this paper, we propose a new random forest (RF) algorithm to deal with high dimensional data for classification using subspace feature sampling method and feature value searching. The new subspace sampling method maintains the diversity and randomness of the forest and enables one to generate trees with a lower prediction error. A greedy technique is used to handle cardinal categorical features for efficient node splitting when building decision trees in the forest. This allows trees to handle very high cardinality meanwhile reducing computational time in building the RF model. Extensive experiments on high dimensional real data sets including standard machine learning data sets and image data sets have been conducted. The results demonstrated that the proposed approach for learning RFs significantly reduced prediction errors and outperformed most existing RFs when dealing with high-dimensional data.     

The cross-entropy method with patching for rare-event simulation of large Markov chains

There are various importance sampling schemes to estimate rare event probabilities in Markovian systems such as Markovian reliability models and Jackson networks. In this work, we present a general state-dependent importance sampling method which partitions the state space and applies the cross-entropy method to each partition. We investigate two versions of our algorithm and apply them to several examples of reliability and queueing models. In all these examples we compare our method with other importance sampling schemes. The performance of the importance sampling schemes is measured by the relative error of the estimator and by the efficiency of the algorithm. The results from experiments show considerable improvements both in running time of the algorithm and the variance of the estimator.     

Possibilistic nested logic programs and strong equivalence

In this paper, the class of possibilistic nested logic programs is introduced. These possibilistic logic programs allow us to use nested expressions in the bodies and heads of their rules. By considering a possibilistic nested logic program as a possibilistic theory, a construction of a possibilistic logic programing semantics based on answer sets for nested logic programs and the proof theory of possibilistic logic is defined. In order to define a general method for computing the possibilistic answer sets of a possibilistic nested program, the idea of equivalence between possibilistic nested programs is explored. By considering properties of equivalence between possibilistic programs, a process of transforming a possibilistic nested logic program into a possibilistic disjunctive logic program is defined. Given that our approach is an extension of answer set programming, we also explore the concept of strong equivalence between possibilistic nested logic programs. To this end, we introduce the concept of poss SE-models. Therefore, we show that two possibilistic nested logic programs are strong equivalents whenever they have the same poss SE-models.The expressiveness of the possibilistic nested logic programs is illustrated by a scenario from the medical domain. In particular, we exemplify how possibilistic nested logic programs are expressive enough for capturing medical guidelines which are pervaded by vagueness and qualitative information.     

On criteria for rook equivalence of Ferrers boards

In Bloom and Saracino (2018) we introduced a new notion of Wilf equivalence of integer partitions and proved that rook equivalence implies Wilf equivalence. In the present paper we prove the converse and thereby establish a new criterion for rook equivalence. We also refine two of the standard criteria for rook equivalence and establish another new one involving what we call nested sequences of L’s.     

Feature Selection using Fuzzy Support Vector Machines

The feature selection consists of obtaining a subset of these features to optimally realize the task without the irrelevant ones. Since it can provide faster and cost-effective learning machines and also improve the prediction performance of the predictors, it is a crucial step in machine learning. The feature selection methods using support machines have obtained satisfactory results, but the noises and outliers often reduce the performance. In this paper, we propose a feature selection approach using fuzzy support vector machines and compare it with the previous work, the results of experiments on the UCI data sets show that feature selection using fuzzy SVM obtains better results than using SVM.     

基于BSTL与XGDT算法对多级别心理压力的评估

针对目前心理压力问题比较严重,收集生理数据评估心理压力存在成本高、主观性强等问题,提出了一种新的基于手机数据的压力评估方法BSTL+XGDT(Borderline1 SMOTE Tomeklinks+eXtreme Gradient Boosting),将压力水平精确划分为5个级别.首先从手机数据提取特征生成样本,对样本进行BSTL采样,然后用XGDT过滤特征和RFE(Recursive Feature Elimination)筛选特征,同时,利用采样前后的数据及特征筛选前后的数据训练XGDT、支持向量机(SVC)、随机森林(RF)、K近邻(KNN)、决策树(DT)、多层感知机(MLP)、标签传播(LS)方法,结果显示方法BSTL+XGDT优于其他方法.     

Framework for efficient feature selection in genetic algorithm based data mining

We present the design of more effective and efficient genetic algorithm based data mining techniques that use the concepts of feature selection. Explicit feature selection is traditionally done as a wrapper approach where every candidate feature subset is evaluated by executing the data mining algorithm on that subset. In this article we present a GA for doing both the tasks of mining and feature selection simultaneously by evolving a binary code along side the chromosome structure used for evolving the rules. We then present a wrapper approach to feature selection based on Hausdorff distance measure. Results from applying the above techniques to a real world data mining problem show that combining both the feature selection methods provides the best performance in terms of prediction accuracy and computational efficiency.     

基于GA-PLS和AdaBoost的故障诊断方法

提出一种基于GA-PLS和AdaBoost的液压系统故障诊断方法。该方法用遗传算法与偏最小二乘法相结合(Genetic algorithm-partial least squares,GA-PLS)的算法对初始特征向量进行筛选,提取出与故障信息相关程度高的特征向量,把该特征向量作为输入,运用AdaBoost(Adaptive Boost)方法建立分类器,以识别液压系统的工作状态和故障类型。对实验数据分析的结果说明,该方法能准确地选择出特征向量,并有效地应用于液压系统的故障诊断。     

q-Distributions on boxed plane partitions

We introduce elliptic weights of boxed plane partitions and prove that they give rise to a generalization of MacMahon’s product formula for the number of plane partitions in a box. We then focus on the most general positive degenerations of these weights that are related to orthogonal polynomials; they form three 2-D families. For distributions from these families, we prove two types of results. First, we construct explicit Markov chains that preserve these distributions. In particular, this leads to a relatively simple exact sampling algorithm. Second, we consider a limit when all dimensions of the box grow and plane partitions become large and prove that the local correlations converge to those of ergodic translation invariant Gibbs measures. For fixed proportions of the box, the slopes of the limiting Gibbs measures (that can also be viewed as slopes of tangent planes to the hypothetical limit shape) are encoded by a single quadratic polynomial.     

Feature extraction algorithms for constrained global optimization I. Mathematical foundation

Nonconvex mixed integer nonlinear programming problems arise quite frequently in engineering decision problems, in general, and in chemical process design synthesis and process scheduling applications, in particular. These problems are characterized by high dimensionality and multiple local optimal solutions. In this work, a novel approach is developed for determining the global optimum in nonlinear continuous and discrete domains. The mathematical foundations of the feature extraction algorithm are presented and the properties of the algorithm discussed in detail. The algorithm uses a partition and search strategy in which the problem domain is successively partitioned and a statistical approximation approach is used to characterize the objective function values and the constraint feasibility over a partition. Specifically, the general joint distribution function representing the objective function values is relaxed to a separable form and approximated using an expansion in terms of Bernstein functions. The coefficients of the expansion are determined by solving a small linear program. Feasibility is established by computing upper and lower bounds for the inequality constraint functions, while equality constraints are explicitly or numerically eliminated. Estimates of the volume averaged values of objective function and constraint feasibility are used to select efficient partitions for further investigation. These are refined successively so as to focus the search on the most promising decision regions. An alternative, constant resolution partitioning strategy is also developed using a suitably modified genetic search algorithm. Illustrative examples are used to demonstrate the key computational features of the method.     

Idempotent Block Splitting on Partial Partitions,I: Isotone Operators

Image segmentation algorithms can be modelled as image-guided operators (maps) on the complete lattice of partitions of space, or on the one of partial partitions (i.e., partitions of subsets of the space). In particular region-splitting segmentation algorithms correspond to block splitting operators on the lattice of partial partitions, in other words anti-extensive operators that act by splitting each block independently. This first paper studies in detail block splitting operators and their lattice-theoretical and monoid properties; in particular we consider their idempotence (a requirement in image segmentation). We characterize block splitting openings (kernel operators) as operators splitting each block into its connected components according to a partial connection; furthermore, block splitting openings constitute a complete sublattice of the complete lattice of all openings on partial partitions. Our results underlie the connective approach to image segmentation introduced by Serra. The second paper will study two classes of non-isotone idempotent block splitting operators, that are also relevant to image segmentation.     

区间型符号数据的特征选择方法

对区间型符号数据进行特征选择,可以降低数据的维数,提取数据的关键特征。针对区间型符号数据的特征选择问题,本文提出了一种新的特征选择方法。首先,该方法使用区间数Hausdorff距离和区间数欧氏距离度量区间数的相似性,通过建立使得样本点与样本类中心相似性最大的优化模型来估计区间型符号数据的特征权重。其次,基于特征权重构建相应的分类器来评价所估计特征权重的优劣。最后,为了验证本文方法的有效性,分别在人工生成数据集和真实数据集上进行了数值实验,数值实验结果表明,本文方法可以有效地去除无关特征,识别出与类标号有关的特征。