A Discrete Chebyshev Approximation Problem by Means of Several Polynomials

The problem of approximation of a given function on a given set by a polynomial of a fixed degree in the Chebyshev metric (the Chebyshev polynomial approximation problem) is a typical problem of Nonsmooth Analysis (to be more precise, it is a convex nonsmooth problem). It has many important applications, both in mathematics and in practice. The theory of Chebyshev approximations enjoys very nice properties (the most famous being the Chebyshev alternation rule). In the present article the problem of approximation of a given function on a given finite set of points by several polynomials is studied. As a criterion function, the maximin deviation is taken. The resulting functional is nonsmooth and nonconvex and therefore the problem becomes multiextremal and may have local minimizers which are not global ones. A necessary and sufficient condition for a point to be a local minimizer is proved. It is shown that a generalized alternation rule is still valid. Sufficient conditions for a point to be a strict local minimizer are established as well. These conditions are also formulated in terms of alternants. An exchange algorithm for finding a local minimizer is constructed. An k -exchange algorithm, allowing to find a "better" local minimizer is stated. Numerical examples illustrating the theory are presented.     

A classification rule reduction algorithm based on significance domains

Many rule systems generated from decision trees (like CART, ID3, C4.5, etc.) or from direct counting frequency methods (like Apriori) are usually non-significant or even contradictory. Nevertheless, most papers on this subject demonstrate that important reductions can be made to generate rule sets by searching and removing redundancies and conflicts and simplifying the similarities between them. The objective of this paper is to present an algorithm (RBS: Reduction Based on Significance) for allocating a significance value to each rule in the system so that experts may select the rules that should be considered as preferable and understand the exact degree of correlation between the different rule attributes. Significance is calculated from the antecedent frequency and rule frequency parameters for each rule; if the first one is above the minimal level and rule frequency is in a critical interval, its significance ratio is computed by the algorithm. These critical boundaries are calculated by an incremental method and the rule space is divided according to them. The significance function is defined for these intervals. As with other methods of rule reduction, our approach can also be applied to rule sets generated from decision trees or frequency counting algorithms, in an independent way and after the rule set has been created. Three simulated data sets are used to carry out a computational experiment. Other standard data sets from UCI repository (UCI Machine Learning Repository) and two particular data sets with expert interpretation are used too, in order to obtain a greater consistency. The proposed method offers a more reduced and more easily understandable rule set than the original sets, and highlights the most significant attribute correlations quantifying their influence on consequent attribute.     

Integrating noisy data

Suppose the parametric form of a curve is not known, but only a set of observations. Quadrature formulae can be used to integrate a function only known from a set of data points. However, the results will be unreliable if the data contains measurement errors (noise). The method presented here fits an even degree piecewise polynomial to the data where all the data points are being used as knot points and the smoothing parameter is optimal for the indefinite integral of the curve which happens to be a smoothing spline. After the smoothing parameter has been chosen, this approach is less computationally expensive than fitting a smoothing spline and integrating.     

A simple proof of Hwang's theorem for rectilinear Steiner minimal trees

We present a simple, direct proof of Hwang's characterization of rectilinear Steiner minimal trees [3]: LetS be a set of at least five terminals in the plane. If no rectilinear Steiner minimal tree forS has a terminal of degree two or more, there is a tree in which at most one of the Steiner points does not lie on a straight linel, and the tree edges incident to the Steiner points onl appear on alternate sides. This theorem has been found useful in proving other results for rectilinear Steiner minimal trees.     

空气中PM2.5的扩散和衰减模型

PM2.5的时空分布及其演变规律十分复杂.为刻画PM2.5的发生、扩散和衰减规律,提出点源、线源和面源叠加的多源模型描述区域内的多污染源对某一监测点的影响.考虑风力风速、太阳辐射强度、湿度等天气和季节因素以及重力、湍流扩散、分子扩散等对源强强度的影响,提出源衰减、湿沉积、化学迁移叠加衰减模型,用监测点的PM2.5浓度数据对污染源强度和衰减系数进行反演求解.针对西安市某些监测点处的PM2.5浓度突然增至数倍且延续数小时,建立污染扩散预测与评估方法,对提升前后污染源源强进行分析,给出重度污染区域,并用数据的人工统计定性验证模型的合理性.     

Output-Sensitive Algorithms for Computing Nearest-Neighbour Decision Boundaries

Given a set R of red points and a set B of blue points, the nearest-neighbour decision rule classifies a new point q as red (respectively, blue) if the closest point to q in R B comes from R (respectively, B). This rule implicitly partitions space into a red set and a blue set that are separated by a red-blue decision boundary. In this paper we develop output-sensitive algorithms for computing this decision boundary for point sets on the line and in ². Both algorithms run in time O(n log k), where k is the number of points that contribute to the decision boundary. This running time is the best possible when parameterizing with respect to n and k.     

The Space of Unordered Real Line Arrangements

The set of all unordered real line arrangements of given degree in the real projective plane is known to have a natural semialgebraic structure. The nonreduced arrangements are singular points of this structure. We show that the set of all unordered real line arrangements of given degree also has a natural structure of a smooth compact connected affine real algebraic variety. In fact, as such, it is isomorphic to a real projective space. As a consequence, we get a projectively linear structure on the set of all real line arrangements of given degree. We also show that the universal family of unordered real line arrangements of given degree is not algebraic.     

Transformation of chaotic nonlinear polynomial difference systems through Newton iterations

Chaotic sequences generated by nonlinear difference systems or ‘maps’ where the defining nonlinearities are polynomials, have been examined from the point of view of the sequential points seeking zeroes of an unknown functionf following the rule of Newton iterations. Following such nonlinear transformation rule, alternative sequences have been constructed showing monotonie convergence. Evidently, these are maps of the original sequences. For second degree systems, another kind of possibly less chaotic sequences have been constructed by essentially the same method. Finally, it is shown that the original chaotic system can be decomposed into a fast monotonically convergent part and a principal oscillatory part showing sharp oscillations. The methods are exemplified by the well-known logistic map, delayed-logistic map and the Hénon map.     

An estimation of distribution algorithm for nurse scheduling

Schedules can be built in a similar way to a human scheduler by using a set of rules that involve domain knowledge. This paper presents an Estimation of Distribution Algorithm (EDA) for the nurse scheduling problem, which involves choosing a suitable scheduling rule from a set for the assignment of each nurse. Unlike previous work that used Genetic Algorithms (GAs) to implement implicit learning, the learning in the proposed algorithm is explicit, i.e. we identify and mix building blocks directly. The EDA is applied to implement such explicit learning by building a Bayesian network of the joint distribution of solutions. The conditional probability of each variable in the network is computed according to an initial set of promising solutions. Subsequently, each new instance for each variable is generated by using the corresponding conditional probabilities, until all variables have been generated, i.e. in our case, a new rule string has been obtained. Another set of rule strings will be generated in this way, some of which will replace previous strings based on fitness selection. If stopping conditions are not met, the conditional probabilities for all nodes in the Bayesian network are updated again using the current set of promising rule strings. Computational results from 52 real data instances demonstrate the success of this approach. It is also suggested that the learning mechanism in the proposed approach might be suitable for other scheduling problems.     

Bi-criteria optimization problems for decision rules

We consider bi-criteria optimization problems for decision rules and rule systems relative to length and coverage. We study decision tables with many-valued decisions in which each row is associated with a set of decisions as well as single-valued decisions where each row has a single decision. Short rules are more understandable; rules covering more rows are more general. Both of these problems—minimization of length and maximization of coverage of rules are NP-hard. We create dynamic programming algorithms which can find the minimum length and the maximum coverage of rules, and can construct the set of Pareto optimal points for the corresponding bi-criteria optimization problem. This approach is applicable for medium-sized decision tables. However, the considered approach allows us to evaluate the quality of various heuristics for decision rule construction which are applicable for relatively big datasets. We can evaluate these heuristics from the point of view of (i) single-criterion—we can compare the length or coverage of rules constructed by heuristics; and (ii) bi-criteria—we can measure the distance of a point (length, coverage) corresponding to a heuristic from the set of Pareto optimal points. The presented results show that the best heuristics from the point of view of bi-criteria optimization are not always the best ones from the point of view of single-criterion optimization.     

The Superconvergence of the Composite Trapezoidal Rule for Hadamard Finite Part Integrals

The composite trapezoidal rule has been well studied and widely applied for numerical integrations and numerical solution of integral equations with smooth or weakly singular kernels. However, this quadrature rule has been less employed for Hadamard finite part integrals due to the fact that its global convergence rate for Hadamard finite part integrals with (p+1)-order singularity is p-order lower than that for the Riemann integrals in general. In this paper, we study the superconvergence of the composite trapezoidal rule for Hadamard finite part integrals with the second-order and the third-order singularity, respectively. We obtain superconvergence estimates at some special points and prove the uniqueness of the superconvergence points. Numerical experiments confirm our theoretical analysis and show that the composite trapezoidal rule is efficient for Hadamard finite part integrals by noting the superconvergence phenomenon. The work of this author was partially supported by the National Natural Science Foundation of China(No.10271019), a grant from the Research Grants Council of the Hong Kong Special Administractive Region, China (Project No. City 102204) and a grant from the Laboratory of Computational Physics The work of this author was supported in part by a grant from the Research Grants Council of the Hong Kong Special Administrative Region, China (Project No. CityU 102204).     

已知拓扑下的最短网络

在平面上给定一个有n个固定点的集合S和一个含有m个可动点的集合M及连接这些点的边的集合T(T也称之为拓扑),确定M中点的位置,使点集V=SM的互联网络最短.本文证明了n是偶数m=-1及在满4度Steiner拓扑下最短网络的结构是4度Steiner树.     

Julia集的淹没分支

In this note,it is shown that if a rational function fofdegree≥2 has a nonempty set of buried points ,then for a generic choice of the point z in the Julia set ,z is a buried point ,and if the Julia set is disconnected,it has uncountably many buried components.     

A brief proof of a maximal rank theorem for generic double points in projective space

We give a simple proof of the following theorem of J. Alexander and A. Hirschowitz: Given a general set of points in projective space, the homogeneous ideal of polynomials that are singular at these points has the expected dimension in each degree of 4 and higher, except in 3 cases.

     

Differential evolution with preferential crossover

We study the mutation operation of the differential evolution algorithm. In particular, we study the effect of the scaling parameter of the differential vector in mutation. We derive the probability density function of points generated by mutation and thereby identify some drawbacks of the scaling parameter. We also visualize the drawbacks using simulation. We then propose a crossover rule, called the preferential crossover rule, to reduce the drawbacks. The preferential crossover rule uses points from an auxiliary population set. We also introduce a variable scaling parameter in mutation. Motivations for these changes are provided. A numerical study is carried out using 50 test problems, many of which are inspired by practical applications. Numerical results suggest that the proposed modification reduces the number of function evaluations and cpu time considerably.     

解整数线性规划中选择割平面的一个方法

本指出了[4]的一个错误。用最速下降规则，给出了选择割平面的一个新方法。一个复杂的例子说明，该方法有一定的实用价值。     

Interpretability assessment of fuzzy knowledge bases: A cointension based approach

Computing with words (CWW) relies on linguistic representation of knowledge that is processed by operating at the semantical level defined through fuzzy sets. Linguistic representation of knowledge is a major issue when fuzzy rule based models are acquired from data by some form of empirical learning. Indeed, these models are often requested to exhibit interpretability, which is normally evaluated in terms of structural features, such as rule complexity, properties on fuzzy sets and partitions. In this paper we propose a different approach for evaluating interpretability that is based on the notion of cointension. The interpretability of a fuzzy rule-based model is measured in terms of cointension degree between the explicit semantics, defined by the formal parameter settings of the model, and the implicit semantics conveyed to the reader by the linguistic representation of knowledge. Implicit semantics calls for a representation of user’s knowledge which is difficult to externalise. Nevertheless, we identify a set of properties - which we call “logical view” - that is expected to hold in the implicit semantics and is used in our approach to evaluate the cointension between explicit and implicit semantics. In practice, a new fuzzy rule base is obtained by minimising the fuzzy rule base through logical properties. Semantic comparison is made by evaluating the performances of the two rule bases, which are supposed to be similar when the two semantics are almost equivalent. If this is the case, we deduce that the logical view is applicable to the model, which can be tagged as interpretable from the cointension viewpoint. These ideas are then used to define a strategy for assessing interpretability of fuzzy rule-based classifiers (FRBCs). The strategy has been evaluated on a set of pre-existent FRBCs, acquired by different learning processes from a well-known benchmark dataset. Our analysis highlighted that some of them are not cointensive with user’s knowledge, hence their linguistic representation is not appropriate, even though they can be tagged as interpretable from a structural point of view.     

Topological degree and number of Nash equilibrium points of bimatrix games

In this paper, using the topological degree, we give a new proof of a well-known result: the number of Nash equilibrium points of a nondegenerate bimatrix game is odd. The calculation of the topological degree allows the localization of the whole set of non-degenerate equilibrium points.     

n值Lukasiewicz命题逻辑系统中公式的随机真度及近似推理

利用赋值集的随机化方法,在n值Lukasiewicz命题逻辑系统中引入公式的随机真度,证明了随机真度的MP规则、HS规则及交推理规则;同时引入公式间的随机相似度和随机伪距离,建立了随机逻辑度量空间,推导出随机相似度的若干性质,证明了随机逻辑度量空间中逻辑运算的连续性;并在随机逻辑度量空间中提出了三种不同类型的近似推理模式,证明了三种近似推理模式的等价性.     

基于模糊集相容性的模糊控制规则优化方法

在简要介绍模糊模型的完备性和相容性的基础上 ,根据模糊集贴近度 ,提出模糊集相容性的概念 ;通过对模糊控制规则表特征的分析 ,进一步完善规则相容性概念及其定量评价方法 ;最后给出模糊控制规则模型自寻优优化方法。仿真结果表明 ,该方法可以大大提高控制系统的控制性能。