一个支持向量机的新光滑函数及其性能分析

光滑函数在支持向量机中起着重要的作用,因此寻找新的光滑函数是研究支持向量机的关键。用求导方法分析了光滑函数的光滑性能,推导并证明了一个六阶光滑函数;同时还用二分法对其逼近性能进行了分析,结果表明：该光滑函数具有比一至五阶光滑函数更高/好的逼近性能,这就为进一步研究支持向量机提供了一个新的光滑函数。     

一个新的多项式光滑支持向量机

光滑支持向量机(SSVM)是支持向量机(SVM)的快速求解模型,拥有更快的求解速度和训练效果。基于光滑的分段多项式函数和插值思想推导出一个新的光滑函数,从而可以更好地逼近正号函数。通过所得到的新光滑函数改进多项式光滑支持向量机模型(PSSVM),得到了更新的光滑支持向量机模型。还给出了新光滑函数的逼近性能和精度分析以及新模型的收敛性证明和最优解的逼近上限。数值实验表明,所提出的新光滑支持向量机模型性能优于PSSVM模型。     

基于最佳一致光滑逼近的孪生支持向量机研究

孪生支持向量机本质为两个二次规划问题,对于其目标函数中约束变量取正号不可微特性,提出一种基于最佳一致逼近的多项式光滑函数构建方法。分别以Bernstain多项式和Chebyshev多项式进行正号函数最佳一致有效光滑逼近。重点突出Chebyshev多项式的最佳一致逼近过程,使用Remez算法构造最佳一致Chebyshev多项式,讨论各阶Chebyshev多项式逼近状况。最后综合最佳一致逼近多项式和样本适应度构建目标优化函数,采用快速Newton-Armijo算法求解目标优化函数,基于UCI数据验证了方法的优越性。     

支持向量机的5阶光滑函数及其性能分析

光滑函数在支持向量机中起着重要作用,熊金志等人用插值函数的方法导出了一个递推公式,得到了一类新的光滑函数,解决了一个关于是否存在以及如何寻求性能更好的光滑函数的问题。然而其中五阶光滑的多项式函数还未进行性能分析。首先推导出了该光滑函数的表达式,然后分析了它的若干性能。结果表明,该光滑函数具有良好的逼近性能,其逼近精度高于以往的光滑函数。     

广义支持向量机的多项式光滑函数法

为了求解广义支持向量机（GSVM）的优化问题,将带有不等式约束的原始优化问题转化为无约束优化问题,由于此无约束优化问题的目标函数不光滑,所以引入一族多项式光滑函数进行逼近,实验中可以根据不同的精度要求选择不同的逼近函数。用BFGS算法求解。实验结果表明,该算法和已有的GSVM的求解算法相比,更快地获得了更高的测试精度,更适合大规模数据集的训练。因此给出的GSVM的求解算法是有效的。     

一种多项式光滑的半监督支持向量机分类算法

为了处理半监督支持向量机优化中的非凸非光滑问题,引入一个多项式光滑函数来逼近非凸的目标函数,给出的多项式函数在样本的高密度区逼近精度高,逼近精度低时出现在样本的低密度区.采用共轭梯度法求解模型.在人工数据和UCI数据库中的4个数据集上的实验结果显示,算法不仅能保证标号数据很少时的分类精度,而且不因标号数据的增多而明显提高分类性能,因此给出的分类器性能是稳定的.     

双二次Hermite插值与双二次样条插值

在一维插值问题中,如果给定节点处的函数值和一阶导数值,我们来构造分段插值多项式,其整体具有连续的一阶导数,并且使多项式的次数尽可能低.众所周知,一般采用三次分段Hermite插值函数,其逼近阶对于足够光滑的函数为四阶.然而,对于光滑度较差的函数,三次Hermite插值不但达不到最高的逼近阶,而且容易出现多余的拐点.从保     

多项式光滑的支持向量回归机

光滑函数将不光滑的模型变为光滑模型,改善支持向量回归机的回归性能和效率,从而降低计算的复杂性.寻找性能更好的光滑函数是研究光滑向量回归机的一个关键问题.本文用级数展开的方法得出了ε–不敏感的支持向量回归机|x|ε2的一类新的光滑函数.证明了这类函数的性能,它能满足任意阶光滑的要求,也能达到任意给定的逼近精度.实验结果表明,随着光滑阶数的提高,逼近精度和回归性能也相应提高.从而为支持向量回归机和相关研究领域提供了一类新的、性能更好的多项式光滑函数.     

光滑分段孪生支持向量机

为了解决Sigmoid的积分函数对正号函数的逼近精度低的问题,引入一种具有更强逼近正号函数能力的光滑函数即分段函数,提出了光滑分段孪生支持向量机,并用快速Newton-Armijo算法对其求解.在NDC和UCI数据集上的实验结果表明:光滑分段孪生支持向量机能够有效地处理大规模和高维度数据,且分类精度和分类速度与光滑孪生支持向量机相比得到了改进.     

一族三次样条光滑半监督支持向量机

针对半监督支持向量分类优化中的非凸非光滑化问题,建立光滑半监督支持向量机模型,提出基于分段多项式函数和插值思想构造一个新的三次样条光滑函数,从而可以更好地逼近对半监督支持向量机中非光滑的对称铰链损失函数部分,构造出基于此光滑函数的具有二阶光滑的半监督支持向量机模型。进而可以用优化中的光滑算法来求解该模型,并分析所构造的三次样条函数对对称铰链损失函数的逼近精度。通过数据实验证明所构造的新的光滑半监督模型具有较好的分类效果和效率。     

多项式光滑的支持向量机一般模型研究

2005年袁玉渡等人用一个多项式函数作为光滑函数,提出了一个多项式光滑的支持向量机模型PSSVM(polynomial smooth support vector machine),使分类性能及效率得到了一定提高.2007年熊金志等人用插值函数的方法导出了一个递推公式,得到了一类新的光滑函数,解决了关于是否存在以及如何寻求性能更好的光滑函数的问题.然而,支持向量机是否存在其他多项式光滑模型,以及多项式光滑模型的一般形式是什么等问题依然存在.为此,将一类多项式函数作为新的光滑函数,使用光滑技术,提出了多项式光滑的支持向量机一般模型dPSSVM(dth-order polynomial smooth support vector machime).用数学归纳法证明了该一般模型的全局收敛性,并进行了数值实验.实验结果表明,当光滑阶数等于3时,一般模型的分类性能及效率为最好,并优于PSSVM模型;当光滑阶数大于3后,分类性能基本不变,效率会有所降低.成功解决了多项式光滑的支持向量机的一般形式问题.     

Computing the Maximum Degree of Minors in Mixed Polynomial Matrices via Combinatorial Relaxation

Mixed polynomial matrices are polynomial matrices with two kinds of nonzero coefficients: fixed constants that account for conservation laws and independent parameters that represent physical characteristics. The computation of their maximum degrees of minors is known to be reducible to valuated independent assignment problems, which can be solved by polynomial numbers of additions, subtractions, and multiplications of rational functions. However, these arithmetic operations on rational functions are much more expensive than those on constants. In this paper, we present a new algorithm of combinatorial relaxation type. The algorithm finds a combinatorial estimate of the maximum degree by solving a weighted bipartite matching problem, and checks if the estimate is equal to the true value by solving independent matching problems. The algorithm mainly relies on fast combinatorial algorithms and performs numerical computation only when necessary. In addition, it requires no arithmetic operations on rational functions. As a byproduct, this method yields a new algorithm for solving a linear valuated independent assignment problem.     

多项式函数的神经网络逼近: 网络的构造与逼近算法

该文作者先用构造性方法证明：对于给定的r阶多项式函数，可以具体地构造出一个三层前向神经网络，以任意精度逼近该多项式，所构造的网络的隐层节点个数仅与多项式的阶数r和网络的输入个数s有关，并能准确地用r表达；然后，给出一个实现这一逼近的具体算法；最后，给出两个数值算例进一步验证所得的理论结果．该文所获得的结果对前向神经网络逼近多项式函数类的网络具体构造以及实现逼近的方法等问题具有较为重要的指导意义．     

应用非单调线搜索求解一类互补问题

考虑一类含非Lipschtizian连续函数的非线性互补问题。引入plus函数的一类广义光滑函数,讨论其性质。应用所引入函数将互补问题重构为一系列光滑方程组,提出一个具有非单调线搜索的Newton算法求解重构的方程组以得到原问题的解。在很弱的条件下,该算法具有全局收敛性和局部二次收敛性。利用该算法求解一自由边界问题,其数值结果显示该算法是有效的。     

Boolean functions with long prime implicants

In this short note we introduce a hierarchy of classes of Boolean functions, where each class is defined by the minimum allowed length of prime implicants of the functions in the class. We show that for a given DNF and a given class in the hierarchy, it is possible to test in polynomial time whether the DNF represents a function from the given class. For the first class in the hierarchy we moreover present a polynomial time algorithm which for a given input DNF outputs a shortest logically equivalent DNF, i.e. a shortest DNF representation of the underlying function. This class is therefore a new member of a relatively small family of classes for which the Boolean minimization problem can be solved in polynomial time. For the second class and higher classes in the hierarchy we show that the Boolean minimization problem can be approximated within a constant factor.     

Structural Interval Reliability Algorithm Based on Bernstein Polynomials andEvidence Theory

Structural reliability is an important method to measure the safety performance of structures under the influence of uncertain factors. Traditional structural reliability analysis methods often convert the limit state function to the polynomial form to measure whether the structure is invalid. The uncertain parameters mainly exist in the form of intervals. This method requires a lot of calculation and is often difficult to achieve efficiently. In order to solve this problem, this paper proposes an interval variable multivariate polynomial algorithm based on Bernstein polynomials and evidence theory to solve the structural reliability problem with cognitive uncertainty. Based on the non-probabilistic reliability index method, the extreme value of the limit state function is obtained using the properties of Bernstein polynomials, thus avoiding the need for a lot of sampling to solve the reliability analysis problem. The method is applied to numerical examples and engineering applications such as experiments, and the results show that the method has higher computational efficiency and accuracy than the traditional linear approximation method, especially for some reliability problems with higher nonlinearity. Moreover, this method can effectively improve the reliability of results and reduce the cost of calculation in practical engineering problems.     

A Primal-Dual Approximation Algorithm for the Facility Location Problem with Submodular Penalties

We consider the facility location problem with submodular penalties (FLPSP), introduced by Hayrapetyan et?al. (Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 933–942, 2005), who presented a 2.50-approximation algorithm that is non-combinatorial because this algorithm has to solve the LP-relaxation of an integer program with exponential number of variables. The only known polynomial algorithm for this exponential LP is via the ellipsoid algorithm as the corresponding separation problem for its dual program can be solved in polynomial time. By exploring the properties of the submodular function, we offer a primal-dual 3-approximation combinatorial algorithm for this problem.