Learning intersections of halfspaces with a margin

We give a new algorithm for learning intersections of halfspaces with a margin, i.e. under the assumption that no example lies too close to any separating hyperplane. Our algorithm combines random projection techniques for dimensionality reduction, polynomial threshold function constructions, and kernel methods. The algorithm is fast and simple. It learns a broader class of functions and achieves an exponential runtime improvement compared with previous work on learning intersections of halfspaces with a margin.     

Neural net algorithms that learn in polynomial time from examples and queries.

An algorithm which trains networks using examples and queries is proposed. In a query, the algorithm supplies a y and is told t(y) by an oracle. Queries appear to be available in practice for most problems of interest, e.g. by appeal to a human expert. The author's algorithm is proved to PAC learn in polynomial time the class of target functions defined by layered, depth two, threshold nets having n inputs connected to k hidden threshold units connected to one or more output units, provided k=/<4. While target functions and input distributions can be described for which the algorithm will fail for larger k, it appears likely to work well in practice. Tests of a variant of the algorithm have consistently and rapidly learned random nets of this type. Computational efficiency figures are given. The algorithm can also be proved to learn intersections of k half-spaces in R(n) in time polynomial in both n and k. A variant of the algorithm can learn arbitrary depth layered threshold networks with n inputs and k units in the first hidden layer in time polynomial in the larger of n and k but exponential in the smaller of the two.     

On encoding and enumerating threshold functions

In this paper, we deal with encoding and enumerating threshold functions defined on n-dimensional binary inputs. The paper specifies situations in which the unique characterization of functions from a given class is preserved by usage of an appropriate set of discrete moments. Moreover, sometimes such a characterization (coding) is optimal with respect to the number of necessary bit rate per coded function. By estimating the number of possible values of the discrete moments used, several upper bounds (for different classes of threshold functions) are derived, some of which are better than those previously known.     

On the random generation and counting of weak order extensions of a poset with given class cardinalities

In previous work, we have proposed a simple algorithm to generate random linear extensions of a partially ordered set (poset). A closely related problem is the random generation of so-called weak order extensions of a poset. Such an extension can be informally characterized as a linear order on the equivalence classes of a partition of the poset, not contradicting the underlying poset order. The generation of linear extensions can then be seen as a special case of the generation of weak order extensions where each equivalence class degenerates into a singleton. If no a priori knowledge about the underlying partition is available, time complexity increases tremendously. In first instance, we therefore restrict to the generation of weak order extensions with given class cardinalities, a problem encountered in the context of ranking algorithms. It will be shown that a first random weak order extension can be generated in O(w²(P)·|I(P)|) time, while every subsequent extension with the same class cardinalities can be obtained in O(w(P)·|P|) time, where |I(P)| denotes the number of ideals of the poset P, and w(P) the width of the poset P. Additionally, the number of weak order extensions obeying the specified class cardinalities can also be obtained in the stated O(w²(P)·|I(P)|) time.     

基于布尔函数正规性的广义Bent函数构造

基于广义Bent函数的正规性,结合子空间上的特征函数,分析广义正规Bent函数的Chrestenson谱特征。利用间接构造Bent函数的方法,在整数模m的剩余类环Zm以及 元域Zp上,给出2类新的 元广义Bent函数。理论分析结果表明,与传统构造方法相比,该方法可构造出更多的 元广义Bent函数。     

A set of new Chebyshev kernel functions for support vector machine pattern classification

In this study, we introduce a set of new kernel functions derived from the generalized Chebyshev polynomials. The proposed generalized Chebyshev polynomials allow us to derive different kernel functions. By using these polynomial functions, we generalize recently introduced Chebyshev kernel function for vector inputs and, as a result, we obtain a robust set of kernel functions for Support Vector Machine (SVM) classification. Thus in this study, besides clarifying how to apply the Chebyshev kernel functions on vector inputs, we also increase the generalization capability of the previously proposed Chebyshev kernels and show how to derive new kernel functions by using the generalized Chebyshev polynomials. The proposed set of kernel functions provides competitive performance when compared to all other common kernel functions on average for the simulation datasets. The results indicate that they can be used as a good alternative to other common kernel functions for SVM classification in order to obtain better accuracy. Moreover, test results show that the generalized Chebyshev kernel approaches to the minimum support vector number for classification in general.     

广义小波收缩消噪阈值选择及应用研究

阈值函数的选取以及阈值的确定是小波收缩消噪的关键问题.首先建立了小波收缩消噪的统一框架:提出小波阈值消噪的广义阈值函数,推导了广义阈值函数阈值选取方法.其次在此框架下研究了如何选取最优阈值函数以及最优阈值.用6种具有不同特性不同信噪比的模拟信号,研究了具有代表性的阈值函数以及阈值的去噪性能,得到了优化的阈值函数以及阈值选取方案.最后将这种优化的消噪方法用于实际心电信号,取得了较好的效果.     

Some properties of equivalence soft set relations

The soft set theory is a new mathematical tool for dealing with uncertainties that is free from the difficulties that have troubled the usual theoretical approaches. Babitha and Sunil [Soft set relations and function, Computers and Mathematics with Applications 60 (2010) 1840–1849] introduced the notion of soft set relations as a soft subset of the Cartesian product of soft sets and discussed many related concepts such as equivalence soft set relations, partitions and functions. In this paper, we further study the equivalence soft set relations and obtain soft analogues of many results concerning ordinary equivalence relations and partitions. Furthermore, we introduce and discuss the transitive closure of a soft set relation and prove that the poset of the equivalence soft set relations on a given soft set is a complete lattice with the least element and greatest element.     

广义特征值多类分类算法

提出了一个新的多类分类算法,该算法的目标是寻找[M]个相互不平行的超平面,使得第[m(m=1,2,?,M)]类的各点到第[m]个超平面的距离之和尽可能小,而其余类的所有点到该超平面的距离之和尽可能大。基于这个思想,寻求第[m]个超平面的优化模型最终可转化为一个广义特征值问题。该方法编程简单,易于实现。在数值试验部分,该算法与一些经典的基于支持向量机的多类分类算法进行比较,表明了该算法的优越性。     

Learning intersections and thresholds of halfspaces

We give the first polynomial time algorithm to learn any function of a constant number of halfspaces under the uniform distribution on the Boolean hypercube to within any constant error parameter. We also give the first quasipolynomial time algorithm for learning any Boolean function of a polylog number of polynomial-weight halfspaces under any distribution on the Boolean hypercube. As special cases of these results we obtain algorithms for learning intersections and thresholds of halfspaces. Our uniform distribution learning algorithms involve a novel non-geometric approach to learning halfspaces; we use Fourier techniques together with a careful analysis of the noise sensitivity of functions of halfspaces. Our algorithms for learning under any distribution use techniques from real approximation theory to construct low-degree polynomial threshold functions. Finally, we also observe that any function of a constant number of polynomial-weight halfspaces can be learned in polynomial time in the model of exact learning from membership and equivalence queries.     

An extension of Wolovich's definition of equivalence of linearsystems

Wolovich's classical definition of equivalence for linear systems (1974) is extended to the generalized study of linear systems. It is shown that the resulting equivalence is an alternative characterization of the notion of full system equivalence underlying its fundamental role in the generalized study of linear systems     

Identification of partial disjunction, parity, and threshold functions

Let F be a class of functions obtained by replacing some inputs of a Boolean function of a fixed type with some constants. The problem considered in this paper, which is called attribute efficient learning, is to identify “efficiently” a Boolean function g out of F by asking for the value of g at chosen inputs, where “efficiency” is measured in terms of the number of essential variables. We study the query complexity of attribute-efficient learning for three function classes that are, respectively, obtained from disjunction, parity, and threshold functions. In many cases, we obtain almost optimal upper and lower bound on the number of queries.     

On a new method for finding generalized equivalence transformations for differential equations involving arbitrary functions

A new efficient method for finding generalized equivalence transformations for a class of differential equation systems via its related extended classical symmetries is presented. This technique can be further adapted to find the equivalence transformations for the mathematical model. It applies to classes of differential systems whose arbitrary functions involve all equations’ independent variables. As a consequence, any symbolic manipulation program designed to find classical Lie symmetries can also be used to determine generalized equivalence transformations and equivalence transformations, respectively, without any modification of the program. The method has been implemented as the maple routine gendefget and is based on the maple package desolv(by Carminati and Vu). The nonlinear stationary heat conduction parameter identification problem is considered as an example.     

非均衡数据的支持向量机新方法*

为了弥补支持向量机对非均衡样本集分类时倾向于较大类的不足,提出一种平衡策略。基于Fisher判别思想,计算出两类样本在分类超平面法向量上投影后的均值和方差,再依据两类错分概率相等准则,给出新的阈值计算方法对超平面进行调整。该方法可补偿非平衡数据分类的倾向性,提高预测分类精度。最后在非均衡的人工和真实数据集上的数值实验表明了该方法的可行性与有效性。     

State space construction for continuous time transfer function matrices via Nerode equivalence

In this paper, we show that a minimal state space realization in Jordan canonical form for linear multivariable continuous-time systems described by rational transfer function matrices could be obtained in a natural and basic way by using the concept of Nerode equivalence. While the minimal state space realization is known, the contribution of this note is to provide an alternative realization procedure which is directly introduced in a simple and self-contained manner. Both scalar and multivariable cases in the continuous-time setting are discussed. The presentation also provides a concrete construction of rational vector function with preassigned poles to interpolate any 2-norm bounded analytical vector function in the open left-half of the complex plane. The basic idea of Nerode equivalence is that the state can be identified with a corresponding equivalence class of inputs. For a linear finite dimensional time-invariant continuous-time system, the zero state is identified with the kernel of certain Hankel operator. This characterization via Nerode equivalence class sheds light on the construction of state for general nonlinear input–output systems.     

Support vector machines for speaker and language recognition

Support vector machines (SVMs) have proven to be a powerful technique for pattern classification. SVMs map inputs into a high-dimensional space and then separate classes with a hyperplane. A critical aspect of using SVMs successfully is the design of the inner product, the kernel, induced by the high dimensional mapping. We consider the application of SVMs to speaker and language recognition. A key part of our approach is the use of a kernel that compares sequences of feature vectors and produces a measure of similarity. Our sequence kernel is based upon generalized linear discriminants. We show that this strategy has several important properties. First, the kernel uses an explicit expansion into SVM feature space—this property makes it possible to collapse all support vectors into a single model vector and have low computational complexity. Second, the SVM builds upon a simpler mean-squared error classifier to produce a more accurate system. Finally, the system is competitive and complimentary to other approaches, such as Gaussian mixture models (GMMs). We give results for the 2003 NIST speaker and language evaluations of the system and also show fusion with the traditional GMM approach.     

基于差分的特殊权限下(m+n,t1+t2)门限秘密共享

在秘密共享案中,一般研究(n,t)门限秘密共享方案。我们给出的是具有特殊权限的(m+n,t1+t2)门限秘密共享方案,它是(n,t)门限秘密共享方案推广形式的门限秘密共享方案。基于差分给出(m+n,t1+t2)门限秘密共享方案,又基于Shamir方案给出(m+n,t1+t2)门限秘密共享的另一方案。     

相对化One-Way函数的存在性

One-Way函数在计算复杂性和密码技术中均有重要的应用.将Grollmann和Selman的结果推广到相对化和非一致复杂类的情形,证明了复杂类UP/poly,UP,P/poly等之间的包含关系与强相对化one-way函数、弱相对化one-way函数存在问题的等价性.     

UNCERTAINTY AND COMPLEMENTARITY PRINCIPLES IN ECOLOGICAL MODELS

Literature about models and modelling is very extensive, but the linguistic aspect of ecological models is not so popular. In this paper, the authors develop a linguistic theory of ecological models from the mathematical linguistic theory and its semantic background. From the equivalence relationship defined upon the language L(M), which describes an ecological model in mathematical terms, it will be possible to statistically determine the semantic component associated to each sentence. The authors also propose an uncertainty principle for the equations (called flow equations) that are used to model ecological processes. The following hypothesis will be considered: a) The first-order vocabulary associated to a variable, a transformed function, is a sememe; b) The flow equation is a complex sentence; c) There is a synonymy relationship among sentences that describe the same process; d) The synonymy relationship forms classes of equivalence. The following results will be reported: a) The cardinal of each class of equivalence is a dimension of the process complexity; b) Each sentence can be defined through a pair of numbers (r,m)ER, 0 &lt; =r &lt; =1, 0 &lt; =m &lt; =1, where r defines the coefficient of determination and m the emotional component of meaning (semantics) of the equation; c) The meaning m can be calculated approximately by statistical methods; d) An uncertainty principle (Delta r . Delta m &lt; =0) and a semantic complementarity principle are proposed.