布尔函数线性等价的分析与应用

对于g(x) =f(xA +b) +l·x +c ,给定f(x) ,g(x) ,如何求取等价关系A ,b ,l,c是一个有用的问题 .该文利用Walsh谱和自相关函数谱作为工具 ,给出的算法 1可以求取g(x) =f(xA)型的等价关系 .针对g(x) =f(xA +b)+l·x +c类型的等价关系 ,当b已知时 ,基于Fuller Millan算法给出的算法 2比Fuller Millan算法至少要快k - 1倍 ,其中k为函数绝对自相关函数谱含有的谱类个数 .应用于AES的S 盒的 8个布尔函数间等价关系的求取 ,算法 2比Fuller Millan算法提高速度近 2 0倍 .应用于IP (IsomorphismofPolynomials)问题的分析 ,指出Patarin所给参数的IP问题是可解的 ,因此基于IP问题的密码体制是不安全的 .     

任意分布随机变量抽样的通用算法与程序

本文给出任意单变量离散或连续分布抽样的通用算法与程序．对于离散分布,将根据其分布率从三个算法(逆变换、罐子法和别名法)中自动选出最合适的一个．在连续分布场合,使用如下的复合抽样方法:f(x)=pafa(x) (1-pa)fb(x),式中fa(x)是密度f(x)的近似,并有fa(x)=L(x)／pa,而L(x)(≤f(x))是阶梯函数,其面积pa→1．在连续分布抽样中,也借助罐子法、别名法和近似的舍选法,且阶梯函数中的阶梯数目和非等距的阶梯划分等都由程序根据f(x)的特性自动确定．多于20个分布的数值试验表明,我们的通用算法很有效,可与为某些特定分布专门设计的最佳算法媲美．     

求非光滑规划全局极小点的一类改进的填充函数法

本文考虑优化问题limF(x),其中F(x)为非光滑函数,引入了求解该优化问题的一类改进的双参数填充函数,给出了相应的算法及收敛域估计,理论分析及数值结果均表明该方法是行之有效的.     

Julia分形

近年来分形理论和它的构造方法受到极大关注.Julia集是使用非线性复映射f(z)=zm c为迭代函数生成的一类著名分形,而逃逸时间算法是生成Julia集最常用的算法.本文在给出逃逸时间算法的算法步骤之后,针对迭代函数fmc(z)=zm c中参数m,c变化的不同情况,给出了Julia集的实验图例,并分析了二次表达式的常规Julia集(m=2)和高阶的广义Julia集(m＞2)的一些特点.     

训练集容量对决策树分类错误率的影响研究

数据挖掘算法必须在实际数据集上进行验证,而数据集容量是有限的,训练集比例过低会导致训练不足,训练集比例过高会导致算法评价过于乐观。针对训练集容量对评价效果的影响问题,对25个UCI数据集的不同比例训练集运用决策树算法C4.5,得出不同训练集容量对决策树分类错误率的影响关系。实验结果表明,训练集比例至少为50%时才能使分类错误率达到相对平稳。     

不平衡多分类问题的连续AdaBoost算法研究

现有AdaBoost系列算法一般没有考虑类的先验分布.针对该问题,基于最小化训练错误率,通过把符号函数表示的训练错误率的极值问题转变成一种指数函数的极值问题,提出了不平衡分类问题连续 AdaBoost算法,给出了该算法的近似误差估计.基于同样的方法,对二分类问题连续AdaBoost算法的合理性给出了一种全新的解释和证明,并推广到多分类问题,得到了多分类问题连续AdaBoost算法,其具有与二分类连续AdaBoost算法完全类似的算法流程.经分析该算法与Bayes统计推断方法等价,并且其训练错误率随着训练的分类器个数增加而减小.理论分析和基于UCI数据集的实验结果表明了不平衡多分类算法的有效性.在连续AdaBoost算法中,不平衡分类问题常被转换成平衡分类问题来处理,但当先验分布极度不平衡时,使用提出的不平衡分类问题连续AdaBoost算法比一般连续AdaBoost算法有更好效果.     

基于锥函数逼近上的自适应拟牛顿无约束极小化方法

本文提出的算法,当f(x)的“二次性”较强时,能自动转为DFP公式,当f(x)为一锥函数时,算法具有n步终止性,对检验函数进行计算的结果表明,本算法优于DFP公式。     

Z_N上离散对数量子计算算法

文中通过多次量子Fourier变换和变量代换,给出了一个ZN上离散对数量子计算算法,刻画了元素的阶r与算法成功率的关系,当r为素数时,算法成功的概率接近于1,新算法所需基本量子门数的规模为O(L3),且不需要执行函数|f(x1,x2)〉的量子Fourier变换的反演变换,优于已有的ZN上离散对数量子计算算法,其中L=[log N]+1.     

三类布尔函数的相关函数研究

布尔函数的相关函数能刻画其扩散特征和线性结构特征,所以研究相关函数的性质对于布尔函数理论具有重要作用。为此,根据自相关和互相关函数的定义,分析通过迹表示的二次布尔函数f(x)=Tr_1~n(x~(2~i+1)+x(2~′+1))的自相关函数值,给出互相关函数平方的一个表达式C_(f,g)~2(α)=(?)(-1)~(D_(f,g)(a)+D_(f,g)(a+ω)),利用该表达式给出任意三次布尔函数的自相关函数平方和的上界,并借助该上界进一步研究两类迹表示的三次布尔函数的绝对值指标上界问题。     

求解无约束全局优化的改进的单填充函数法

填充函数法是一种求解多变量、多极值函数全局最优化的有效方法,这种方法的关键是构造填充函数.为此文中根据文献[1]的思想,考虑优化问题minf(x)x∈Rn,针对f(x)为局部Lipschitz连续函数,构造了一种简单的单填充函数,容易证明相对于传统的填充函数,该填充函数在参数较小时就能保持其填充性质,且全局收敛速度快.根据这个填充函数还提出了一个求解无约束优化问题的填充函数算法,对4个基准测试函数的数值试验表明该方法是有效的.     

Positional error modeling for line simplification based on automatic shape similarity analysis in GIS

Automatic generalization is a process for representing geographical objects with different degrees of detail on a digital map. The positional error for each geographical object is propagated through the process and a generalization error is also introduced by the generalization. Previous research has focused mainly on measuring the generalization error. This paper presents an analytical model for assessing the positional error in the generalized object by considering both error propagation from the original data and the generalization error. The analytical model provides a shape dissimilarity value that indicates the shape difference between the original data with a positional error and its simplified version. This model is able to objectively and automatically determine the applicability of the generalized data for further applications to geographical information system (GIS) problems. It can also deal with a large amount of data in GIS. Therefore, the analytical model presented, which provides a more comprehensive shape measure for assessing positional error in data derived from the generalization, is valuable in the development of automatic generalization.     

Data representations and generalization error in kernel based learning machines

This paper focuses on the problem of how data representation influences the generalization error of kernel based learning machines like support vector machines (SVM) for classification. Frame theory provides a well founded mathematical framework for representing data in many different ways. We analyze the effects of sparse and dense data representations on the generalization error of such learning machines measured by using leave-one-out error given a finite amount of training data. We show that, in the case of sparse data representations, the generalization error of an SVM trained by using polynomial or Gaussian kernel functions is equal to the one of a linear SVM. This is equivalent to saying that the capacity of separating points of functions belonging to hypothesis spaces induced by polynomial or Gaussian kernel functions reduces to the capacity of a separating hyperplane in the input space. Moreover, we show that, in general, sparse data representations increase or leave unchanged the generalization error of kernel based methods. Dense data representations, on the contrary, reduce the generalization error in the case of very large frames. We use two different schemes for representing data in overcomplete systems of Haar and Gabor functions, and measure SVM generalization error on benchmarked data sets.     

Generalization Bounds of Regularization Algorithm with Gaussian Kernels

In many practical applications, the performance of a learning algorithm is not actually affected only by an unitary factor just like the complexity of hypothesis space, stability of the algorithm and data quality. This paper addresses in the performance of the regularization algorithm associated with Gaussian kernels. The main purpose is to provide a framework of evaluating the generalization performance of the algorithm conjointly in terms of hypothesis space complexity, algorithmic stability and data quality. The new bounds on generalization error of such algorithm measured by regularization error and sample error are established. It is shown that the regularization error has polynomial decays under some conditions, and the new bounds are based on uniform stability of the algorithm, covering number of hypothesis space and data information simultaneously. As an application, the obtained results are applied to several special regularization algorithms, and some new results for the special algorithms are deduced.     

Kernel CMAC with improved capability.

The cerebellar model articulation controller (CMAC) has some attractive features, namely fast learning capability and the possibility of efficient digital hardware implementation. Although CMAC was proposed many years ago, several open questions have been left even for today. The most important ones are about its modeling and generalization capabilities. The limits of its modeling capability were addressed in the literature, and recently, certain questions of its generalization property were also investigated. This paper deals with both the modeling and the generalization properties of CMAC. First, a new interpolation model is introduced. Then, a detailed analysis of the generalization error is given, and an analytical expression of this error for some special cases is presented. It is shown that this generalization error can be rather significant, and a simple regularized training algorithm to reduce this error is proposed. The results related to the modeling capability show that there are differences between the one-dimensional (1-D) and the multidimensional versions of CMAC. This paper discusses the reasons of this difference and suggests a new kernel-based interpretation of CMAC. The kernel interpretation gives a unified framework. Applying this approach, both the 1-D and the multidimensional CMACs can be constructed with similar modeling capability. Finally, this paper shows that the regularized training algorithm can be applied for the kernel interpretations too, which results in a network with significantly improved approximation capabilities.     

Learning by canonical smooth estimation. II. Learning and choice ofmodel complexity

This paper analyzes the properties of a procedure for learning from examples. This “canonical learner” is based on a canonical error estimator developed in Part I. In learning problems one can observe data that consists of labeled sample points, and the goal is to find a model or “hypothesis” from a set of candidates that will accurately predict the labels of new sample points. The expected mismatch between a hypothesis prediction and the actual label of a new sample point is called the hypothesis “generalization error”. We compare the canonical learner with the traditional technique of finding hypotheses that minimize the relative frequency-based empirical error estimate. It is shown that for a broad class of learning problems, the set of cases for which such empirical error minimization works is a proper subset of the cases for which the canonical learner works. We derive bounds to show that the number of samples required by these two methods is comparable. We also address the issue of how to determine the appropriate complexity for the class of candidate hypotheses     

Residual variance estimation in machine learning

The problem of residual variance estimation consists of estimating the best possible generalization error obtainable by any model based on a finite sample of data. Even though it is a natural generalization of linear correlation, residual variance estimation in its general form has attracted relatively little attention in machine learning.In this paper, we examine four different residual variance estimators and analyze their properties both theoretically and experimentally to understand better their applicability in machine learning problems. The theoretical treatment differs from previous work by being based on a general formulation of the problem covering also heteroscedastic noise in contrary to previous work, which concentrates on homoscedastic and additive noise.In the second part of the paper, we demonstrate practical applications in input and model structure selection. The experimental results show that using residual variance estimators in these tasks gives good results often with a reduced computational complexity, while the nearest neighbor estimators are simple and easy to implement.     

On classification of signals represented with data-dependent overcomplete dictionaries

This paper focuses on the problem of how data representation influences the generalization error of kernel-based learning machines like support vector machines (SVMs). We analyse the effects of sparse and dense data representations on the generalization error of SVM. We show that using sparse representations the performances of classifiers belonging to hypothesis spaces induced by polynomial or Gaussian kernel functions reduce to the performances of linear classifiers. Sparse representations reduce the generalization error as long as the representation is not too sparse as with very large dictionaries. Dense data representations reduce the generalization error also using very large dictionaries. We use two schemes for representing data in data-independent overcomplete Haar and Gabor dictionaries, and measure the generalization error of SVMs on benchmark datasets. We study sparse and dense representations in the case of data-dependent overcomplete dictionaries and we show how this leads to principal component analysis.     

On the problem in model selection of neural network regression in overrealizable scenario

In considering a statistical model selection of neural networks and radial basis functions under an overrealizable case, the problem of unidentifiability emerges. Because the model selection criterion is an unbiased estimator of the generalization error based on the training error, this article analyzes the expected training error and the expected generalization error of neural networks and radial basis functions in overrealizable cases and clarifies the difference from regular models, for which identifiability holds. As a special case of an overrealizable scenario, we assumed a gaussian noise sequence as training data. In the least-squares estimation under this assumption, we first formulated the problem, in which the calculation of the expected errors of unidentifiable networks is reduced to the calculation of the expectation of the supremum of the chi2 process. Under this formulation, we gave an upper bound of the expected training error and a lower bound of the expected generalization error, where the generalization is measured at a set of training inputs. Furthermore, we gave stochastic bounds on the training error and the generalization error. The obtained upper bound of the expected training error is smaller than in regular models, and the lower bound of the expected generalization error is larger than in regular models. The result tells us that the degree of overfitting in neural networks and radial basis functions is higher than in regular models. Correspondingly, it also tells us that the generalization capability is worse than in the case of regular models. The article may be enough to show a difference between neural networks and regular models in the context of the least-squares estimation in a simple situation. This is a first step in constructing a model selection criterion in an overrealizable case. Further important problems in this direction are also included in this article.     

应用递归神经网络学习周期运动吸引子轨迹

采用递归神经网络学习非线性周期运动的吸引子轨迹．网络的拓扑结构基于非线性系统的状态空间表达式,网络权值通过时序反向传播算法调整．探讨了不同样本轨迹和网络结构对递归神经网络预测性能的影响．神经网络的性能评估建立在多条测试样本轨迹的基础上,可以更为客观地评价递归神经网络预测性能．对van der Pol方程的仿真结果表明:网络的泛化能力对训练样本轨迹的依赖性较强,从不同训练轨迹上得到的递归神经网络性能差异较大;需要选择合适的递归神经网络结构参数以提高神经网络的泛化能力．