大规模核方法的随机假设空间方法

大规模核方法是大规模数据分析与挖掘的基本机器学习方法。核方法在再生核希尔伯特空间中训练线性学习器求解样本空间中的非线性问题,求解时间复杂度关于数据规模是平方级的,预测也依赖于整个训练数据,因而不适用于大规模学习问题。针对这些问题,提出了大规模核方法的有效随机假设空间方法。首先,在关于样本维度对数时间复杂度内,应用循环随机特征映射显式构造假设空间,该空间称之为循环随机假设空间。然后,在循环随机假设空间中应用线性或亚线性学习算法训练线性模型。理论上,给出了循环随机假设空间的一致泛化误差上界及其相对于最优泛化误差的收敛性。实验结果表明,大规模核方法的随机假设空间方法不仅能够显著地提高非线性核方法的训练与预测效率,而且能够保持与非线性核方法相当的预测精度。该方法有理论保障,计算复杂度低,运行效率高,是当前最高效的大规模核方法实现方法。     

基于近似高斯核显式描述的大规模SVM求解

大规模数据集上非线性支持向量机(support vector machine,SVM)的求解代价过高,然而对于线性SVM却存在高效求解算法.为了应用线性SVM高效求解算法求解非线性SVM,并保证非线性SVM的精确性,提出一种基于近似高斯核显式描述的大规模SVM求解方法.首先,定义近似高斯核并建立其与高斯核的关系,推导近似高斯核与高斯核的偏差上界.然后给出近似高斯核对应的再生核希尔伯特空间(reproducing kernel Hilbert space,RKHS)的显式描述,由此可精确刻画SVM解的结构,增强SVM方法的可解释性.最后显式地构造近似高斯核对应的特征映射,并将其作为线性SVM的输入,从而实现了用线性SVM算法高效求解大规模非线性SVM.实验结果表明,所提出的方法能提高非线性SVM的求解效率,并得到与标准非线性SVM相近的精确性.     

高斯核选择的线性性质检测方法*

核选择直接影响核方法的性能.已有高斯核选择方法的计算复杂度为Ω(n²),阻碍大规模核方法的发展.文中提出高斯核选择的线性性质检测方法,不同于传统核选择方法,询问复杂度为O(ln(1/δ)/ ^{2),计算复杂度独立于样本规模.文中首先给出函数 线性水平的定义,证明可使用 线性水平近似度量一个函数与线性函数类之间的距离,并以此为基础提出高斯核选择的线性性质检测准则.然后应用该准则,在随机傅里叶特征空间中有效评价并选择高斯核.理论分析与实验表明,应用性质检测以实现高斯核选择的方法有效可行.}     

一种大规模支持向量机的高效求解算法

现有大规模支持向量机求解算法需要大量的内存资源和训练时间,通常在大集群并行环境下才能实现。提出了一种大规模支持向量机(SVM)的高效求解算法,以在个人PC机求解大规模SVM。它包括3个步骤:首先对大规模样本进行子采样来降低数据规模;然后应用随机傅里叶映射显式地构造随机特征空间,使得可在该随机特征空间中应用线性SVM来一致逼近高斯核SVM;最后给出线性SVM在多核环境下的并行实现方法以进一步提高求解效率。标准数据集的对比实验验证了该求解算法的可行性与高效性。     

随机特征上一致中心调节的支持向量机

支持向量机（SVM）是最为流行的分类工具,但处理大规模的数据集时,需要大量的内存资源和训练时间,通常在大集群并行环境下才能实现。提出一种新的并行SVM算法,RF-CCASVM,可在有限计算资源上求解大规模SVM。通过随机傅里叶映射,应用低维显示特征映射一致近似高斯核对应的无限维隐式特征映射,从而用线性SVM一致近似高斯核SVM。提出一致中心调节的并行化方法。具体地,将数据集划分成若干子数据集,多个进程并行地在各自的子数据集上独立训练SVM。当各个子数据集上的最优超平面即将求出时,用由各个子集上获得的一致中心解取代当前解,继续在各子集上训练直到一致中心解在各个子集上达到最优。标准数据集的对比实验验证了RF-CCASVM的正确性和有效性。     

核空间的LMS自适应多用户检测技术

提出一种核空间的LMS(KLMS)多用户检测算法,将直接序列扩频码分多址(Direct-sequence code division multiple access,DS-CDMA)接收机收到的信号通过高斯核函数映射到高维特征空间(核空间),再进行线性检测.由于采用了核技巧,所有的计算都在原空间进行,避免了特征空间的复杂运算.KLMS本质是对原空间的信号进行非线性检测,性能更接近最优检测算法.在高斯信道下,仿真结果表明,通过选择合适的核参数,在获得较好稳态误差的同时,KLMS算法具有比其他变步长LMS算法更快的收敛速度.     

基于核自适应的近邻传播聚类算法

近邻传播聚类(AP)方法是近年来出现的一种广受关注的聚类方法,在处理多类、大规模数据集时,能够在较短的时间得到较理想的结果,因此与传统方法相比具有很大的优势。但是对于一些聚类结构复杂的数据集,往往不能得到很好的聚类结果。通过分析数据的聚类特性,设计了一种可以根据数据结构自动调整参数的核函数,数据集在其映射得到的核空间中线性可分或几乎线性可分,对该核空间中的数据集进行近邻传播聚类,有效提高了AP聚类的精确度和速度。算法有效性分析以及仿真实验验证了所提算法在处理大规模复杂结构数据集上的性能优于原始AP算法。     

基于核线性分类分析的三维模型检索算法

为提高检索精确度,提出了一种利用核线性分类分析来对模型特征进行优化的新方法。其主要思想是通过满足Mercer条件的非线性映射将低维空间下线性不可分的样本映射到高维空间,在高维空间中利用线性分类分析将原有的三维模型特征投影到特定的子空间。该方法能够在保持类间距离基础上得到具有鉴别信息的低维特征用于三维模型检索。实验结果表明,核线性分类分析方法速度较快,可在秒级完成三维特征优化,同时优化特征在本文测试数据集上可平均提高搜索准确度15%。     

结合核方法的选择性各向异性扩散去噪算法

在低信噪比图像噪声抑制处理中,为了有效地保持图像边缘,在基于多相位分层分割算法的各向异性扩散模型的基础上,提出一个基于核方法的选择性各向异性扩散去噪算法。该算法根据图像数据的线性不可分特点,首先利用核方法把多相位分层分割算法中的数据项从线性不可分的低维空间推广到可实现线性可分的高维特征空间,在特征空间中实现图像分割;然后根据分割得到的同质区域的梯度信息改进了P-M模型中的扩散系数;最后,在同质区域中采用改进的P-M模型平滑噪声。实验结果表明,该算法无论在噪声去除还是边缘保持上都具较好的效果。     

基于Chernoff上界的多类问题特征选择优化迭代算法

本文提出正态分布条件下面向不同分布的多类问题基于Chernoff上界的特征选择优化迭代算法.该算法由两重迭代组成首先在设定的原始空间和特征空间Chernoff参数s条件下,通过解矩阵方程的迭代算法求得变换矩阵的最优解;然后,在变换矩阵确定的特征空间中搜索最佳的参数s使错误概率上界最小;最后采用折半法修正设定的Chernoff参数s及其迭代步长.通过分析和实例可见基于Chernoff上界特征选择是面向不同分布的多类问题的最佳特征选择方法.     

普适性核度量标准比较研究

核方法是一类应用较为广泛的机器学习算法,已被应用于分类、聚类、回归和特征选择等方面.核函数的选择与参数优化一直是影响核方法效果的核心问题,从而推动了核度量标准,特别是普适性核度量标准的研究.对应用最为广泛的5种普适性核度量标准进行了分析与比较研究,包括KTA,EKTA,CKTA,FSM和KCSM.发现上述5种普适性度量标准的度量内容为特征空间中线性假设的平均间隔,与支持向量机最大化最小间隔的优化标准存在偏差.然后,使用模拟数据分析了上述标准的类别分布敏感性、线性平移敏感性、异方差数据敏感性,发现上述标准仅是核度量的充分非必要条件,好的核函数可能获得较低的度量值.最后,在9个UCI数据集和20Newsgroups数据集上比较了上述标准的度量效果,发现CKTA是度量效果最好的普适性核度量标准.     

内核脱钩技术在检测rootkit木马信息隐藏中的应用

简要讨论了Windows内核系统服务调用机制,分析了基于rootkit技术的木马通过内核态挂钩SystemServiceDispatch-Table隐藏各种敏感信息的一般原理.在检测SystemServiceDispatchTable挂钩隐藏注册表键值的基础上,提出两种内核检测脱钩方法,实现了对rootkit挂钩的有效检测与脱钩,确保了系统荻取注册表等敏感信息的完整性.     

一种新的混合核函数支持向量机

针对单核函数支持向量机性能的局限性问题,提出将sigmoid核函数与高斯核函数组成一种新的混合核函数支持向量机.高斯核是典型的局部核;sigmoid核在神经网络中被证明具有良好的全局分类性能.新混合核函数结合二者的优点,其支持向量机的分类性能优于由单核函数构成的支持向量机,实验结果表明该方法的有效性.     

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.     

多核模糊聚类

针对单核聚类的性能局限性问题,提出将高斯核、Sigmoid核以及多项式核等多种核组成一种新的多核函数,并利用于模糊核进行聚类。高斯核在聚类中有广泛应用,同时Sigmoid核在神经网络中被证明具有很好的全局分类性能。将不同的核函数组合起来的多核函数将结合各种核函数的优点,其聚类性能优于利用单核的模糊核聚类（KFCM）,实验结果表明了该方法的有效性。     

基于多核融合的中文领域实体关系抽取

针对传统径向基核函数的训练矩阵中所有元素都十分接近零而不利于分类的问题,该文提出了一种融合了改进的径向基核函数及其他核函数的多核融合中文领域实体关系抽取方法。利用径向基核函数的数学特性,提出一种改进的训练矩阵,使训练矩阵中的向量离散化,并以此改进的径向基核函数融合多项式核函数及卷积树核函数,通过枚举的方式寻找最优的复合核函数参数,并以上述多核融合方法与支持向量机结合进行中文领域实体关系抽取。在旅游领域的语料上测试,相对于单一核方法及传统多核融合方法,关系抽取性能得到提高。     

基于连通核的鲁棒模糊C-均值聚类算法

提出一种新的鲁棒核模糊C-均值聚类算法.将连通核与AFCM(Alternative fuzzy C-means)聚类算法相结合,给出基于连通核的核AFCM:CRKFCM(Connectivity kernel based robust fuzzy C-means).CRKFCM一方面有效地利用了连通核,可以对任意形状数据聚类,且避免了核参数的选取问题;另一方面在特征空间使用非欧氏距离,可以有效地处理含噪声数据的聚类问题.实验结果表明,与原有的AFCM和连通核硬C-均值(CKHCM,Connectivity kernel based hard C-means)聚类算法相比,新算法在处理噪声环境中的任意形状聚类问题方面更有效.     

Intra-sentence segmentation based on support vector machines in English–Korean machine translation systems

This work is about intra-sentence segmentation performed before syntactic analysis of long sentences composed of at least 20 words in an English–Korean machine translation system. A long sentence has been known to spend enormous computational time and space when it is analyzed syntactically. It can also produce poor translation results. To resolve this problem, we partitioned a long sentence into a few segments to analyze each segment separately. To partition the sentence, firstly, we tried to find candidates for each segment position in the sentence. We then generated input vectors representing lexical contexts of the corresponding candidates and also used the support vector machines (SVM) algorithm to learn and recognize the appropriate segment positions. We used three kernel functions, the linear kernel, the polynomial kernel and the Gaussian kernel, to find optimal hyperplanes classifying proper positions and we compared results obtained from each kernel function. As a result of the experiments, we acquired 0.81, 0.83, and 0.79 f-measure values from the linear, polynomial and Gaussian kernel, respectively.     

基于欧式距离的一种新的核函数

支持向量机表现的好坏很大程度上取决于核函数的选取,因此最近几年关于核函数的研究有许多。越来越多的核函数也被提了出来!但是选取合适的核函数往往却不容易,因为数据的特征往往不知道。文中利用函数的Taylor展开思想,提出了一种新的核函数,叫T—KMOD,基于KMOD提出的。该核函数的灵活性更好,可以处理很多分类的问题。用网络入侵的数据对该核函数进行了仿真,从仿真的结果可以看出,和一些常用的核函数相比,它的鲁棒性更好,有更强的分类能力。同时该函数的分类效果更好。所以该核函数和一般常用的核函数相比,可能更具有一般选择性。     

Learning state machine-based string edit kernels

During the past few years, several works have been done to derive string kernels from probability distributions. For instance, the Fisher kernel uses a generative model M (e.g. a hidden Markov model) and compares two strings according to how they are generated by M. On the other hand, the marginalized kernels allow the computation of the joint similarity between two instances by summing conditional probabilities. In this paper, we adapt this approach to edit distance-based conditional distributions and we present a way to learn a new string edit kernel. We show that the practical computation of such a kernel between two strings x and x^′ built from an alphabet Σ requires (i) to learn edit probabilities in the form of the parameters of a stochastic state machine and (ii) to calculate an infinite sum over Σ^* by resorting to the intersection of probabilistic automata as done for rational kernels. We show on a handwritten character recognition task that our new kernel outperforms not only the state of the art string kernels and string edit kernels but also the standard edit distance used by a neighborhood-based classifier.