Generalization errors of Laplacian regularized least squares regression

Semi-supervised learning is an emerging computational paradigm for machine learning,that aims to make better use of large amounts of inexpensive unlabeled data to improve the learning performance.While various methods have been proposed based on different intuitions,the crucial issue of generalization performance is still poorly understood.In this paper,we investigate the convergence property of the Laplacian regularized least squares regression,a semi-supervised learning algorithm based on manifold regularization.Moreover,the improvement of error bounds in terms of the number of labeled and unlabeled data is presented for the first time as far as we know.The convergence rate depends on the approximation property and the capacity of the reproducing kernel Hilbert space measured by covering numbers.Some new techniques are exploited for the analysis since an extra regularizer is introduced.     

Unsupervised and semi-supervised extreme learning machine with wavelet kernel for high dimensional data

Extreme learning machine (ELM) not only is an effective classifier in supervised learning, but also can be applied on unsupervised learning and semi-supervised learning. The model structure of unsupervised extreme learning machine (US-ELM) and semi-supervised extreme learning machine (SS-ELM) are same as ELM, the difference between them is the cost function. We introduce kernel function to US-ELM and propose unsupervised extreme learning machine with kernel (US-KELM). And SS-KELM has been proposed. Wavelet analysis has the characteristics of multivariate interpolation and sparse change, and Wavelet kernel functions have been widely used in support vector machine. Therefore, to realize a combination of the wavelet kernel function, US-ELM, and SS-ELM, unsupervised extreme learning machine with wavelet kernel function (US-WKELM) and semi-supervised extreme learning machine with wavelet kernel function (SS-WKELM) are proposed in this paper. The experimental results show the feasibility and validity of US-WKELM and SS-WKELM in clustering and classification.     

关于ε不敏感损失函数推广误差的界

本文研究了学习理论中推广误差的界的问题.利用ε不敏感损失函数的性质,分别获得r逼近误差和估计(样本)误差的界,并在特定的假设空间上得到了学习算法推广误差的界.     

基于扩散矩阵的半监督回归学习

半监督学习算法用到标记和未标记的样本.大量的实验表明,利用无标记样本可以改进学习算法的逼近性能.然而,当样本数增加时,逼近性能的定量分析几乎没有.本文构造基于扩散矩阵的一种半监督学习算法,建立逼近阶.结果还量化地说明,未标记样本的使用可以减少逼近误差.     

Learning errors of linear programming support vector regression

In this paper, we give several results of learning errors for linear programming support vector regression. The corresponding theorems are proved in the reproducing kernel Hilbert space. With the covering number, the approximation property and the capacity of the reproducing kernel Hilbert space are measured. The obtained result (Theorem 2.1) shows that the learning error can be controlled by the sample error and regularization error. The mentioned sample error is summarized by the errors of learning regression function and regularizing function in the reproducing kernel Hilbert space. After estimating the generalization error of learning regression function (Theorem 2.2), the upper bound (Theorem 2.3) of the regularized learning algorithm associated with linear programming support vector regression is estimated.     

ERM learning algorithm for multi-class classification

The multi-class classification problem is considered by an empirical risk minimization (ERM) approach. The hypothesis space for the learning algorithm is taken to be a ball of a Banach space of continuous functions. When the regression function lies in some interpolation space, satisfactory learning rates for the excess misclassification error are provided in terms of covering numbers of the unit ball of the Banach space. A comparison theorem is proved and is used to bound the excess misclassification error by means of the excess generalization error.     

基于相近原则的半指导直推学习机及其增量算法

半指导问题是近来机器学习研究中的备受关注一个重要内容．本文以满足“在输入空间中相近的对象其输出也相近”这一源于直观事实的原则(相近原则)去解决半指导学习问题,给出在这个原则下的一个一般的直接推理方法—基于相近原则的半指导问题直推学习机,得到了这个问题的解析解及迭代算法,用模式分类实例验证该方法的有效性,并给出适于在线处理的增量学习算法,这些增量算法尤其还适于新增了有指导的信息的场合．     

鲁棒半监督ν-支持向量分类机

支持向量机在近十年成为机器学习的主要学习技术,而且已经成功应用到有监督学习问题中。Fung和Mangasarian利用支持向量机对于既有已标类别样本又有未知类别样本的训练集进行训练,方法主要是利用少量已标明类别的样本进行训练得到一个分类器的同时对于未标明类别的样本进行分类,使得间隔最大化。此优化问题中假定样本是精确的,而在现实生活中,样本通常带有统计误差。因此,考虑样本带有扰动信息的半监督两类分类问题,给出鲁棒半监督v-支持向量分类算法。该算法的参数v易于选择,而数值试验也表明该算法具有良好的稳定性和较好的分类结果。     

带有变量选择过程的分类模型误差分析

偏倚一方差分析方法是在模型选择过程中权衡模型对现有样本解释程度和未知样本估计准确度的分析方法,目的是使选定的模型检验误差尽量小.在分类或回归过程中进行有效的变量筛选可以获得更准确的模型表达,但也会因此带来一定误差.提出"选择误差"的概念,用于刻画带有变量选择的分类问题中由于变量的某种选择方法所引起的误差.将分类问题的误差分解为偏倚—方差—选择误差进行研究,考察偏倚、方差和选择误差对分类问题的总误差所产生的影响.     

A kernel-free quadratic surface support vector machine for semi-supervised learning

In this paper, we propose a kernel-free semi-supervised quadratic surface support vector machine model for binary classification. The model is formulated as a mixed-integer programming problem, which is equivalent to a non-convex optimization problem with absolute-value constraints. Using the relaxation techniques, we derive a semi-definite programming problem for semi-supervised learning. By solving this problem, the proposed model is tested on some artificial and public benchmark data sets. Preliminary computational results indicate that the proposed method outperforms some existing well-known methods for solving semi-supervised support vector machine with a Gaussian kernel in terms of classification accuracy.     

基于算法稳定的ERM原则一致性的研究

通过对变一误差估计下算法稳定的研究,提出了不依赖于样本分布的CO稳定的概念,证明了CO稳定不仅是变一误差估计条件下ERM原则一致性的充要条件,而且也是学习算法具有推广性的充分条件.     

支持向量机及其在提高采收率潜力预测中的应用

提高采收率潜力分析的基础是进行提高采收率方法的潜力预测 .建立提高采收率潜力预测模型从统计学习的角度来看 ,实质是属于函数逼近问题 .本文首次将统计学习理论及支持向量机方法引入提高采收率方法的潜力预测中 .根据 Vapnik结构风险最小化原则 ,应尽量提高学习机的泛化能力 ,即由有效的训练集样本得到的小的误差能够保证对独立的测试集仍保持小的误差 .在本文所用较少样本条件下 ,支持向量机方法能够兼顾模型的通用性和推广性 ,具有较好的应用前景 .研究中采用的是综合正交设计法、油藏数值模拟和经济评价等方法生成的理论样本集     

半监督距离度量学习内蕴加速投影梯度算法

考虑求解一类半监督距离度量学习问题. 由于样本集(数据库)的规模与复杂性的激增, 在考虑距离度量学习问题时, 必须考虑学习来的距离度量矩阵具有稀疏性的特点. 因此, 在现有的距离度量学习模型中, 增加了学习矩阵的稀疏约束. 为了便于模型求解, 稀疏约束应用了Frobenius 范数约束. 进一步, 通过罚函数方法将Frobenius范数约束罚到目标函数, 使得具有稀疏约束的模型转化成无约束优化问题. 为了求解问题, 提出了正定矩阵群上加速投影梯度算法, 克服了矩阵群上不能直接进行线性组合的困难, 并分析了算法的收敛性. 最后通过UCI数据库的分类问题的例子, 进行了数值实验, 数值实验的结果说明了学习矩阵的稀疏性以及加速投影梯度算法的有效性.     

半监督度量学习内蕴最速下降算法的收敛性分析

主要研究对称正定矩阵群上的内蕴最速下降算法的收敛性问题.首先针对一个可转化为对称正定矩阵群上无约束优化问题的半监督度量学习模型,提出对称正定矩阵群上一种自适应变步长的内蕴最速下降算法.然后利用李群上的光滑函数在任意一点处带积分余项的泰勒展开式,证明所提算法在对称正定矩阵群上是线性收敛的.最后通过在分类问题中的数值实验说明算法的有效性.     

Mock threshold graphs

Mock threshold graphs are a simple generalization of threshold graphs that, like threshold graphs, are perfect graphs. Our main theorem is a characterization of mock threshold graphs by forbidden induced subgraphs. Other theorems characterize mock threshold graphs that are claw-free and that are line graphs. We also discuss relations with chordality and well-quasi-ordering as well as algorithmic aspects.     

Learning a function from noisy samples at a finite sparse set of points

In learning theory the goal is to reconstruct a function defined on some (typically high dimensional) domain Ω, when only noisy values of this function at a sparse, discrete subset ω⊂Ω are available.In this work we use Koksma–Hlawka type estimates to obtain deterministic bounds on the so-called generalization error. The resulting estimates show that the generalization error tends to zero when the noise in the measurements tends to zero and the number of sampling points tends to infinity sufficiently fast.     

Powers of cycles, powers of paths, and distance graphs

In 1988, Golumbic and Hammer characterized the powers of cycles, relating them to circular arc graphs. We extend their results and propose several further structural characterizations for both powers of cycles and powers of paths. The characterizations lead to linear-time recognition algorithms of these classes of graphs. Furthermore, as a generalization of powers of cycles, powers of paths, and even of the well-known circulant graphs, we consider distance graphs. While the colorings of these graphs have been intensively studied, the recognition problem has been so far neglected. We propose polynomial-time recognition algorithms for these graphs under additional restrictions.     

Learning from uniformly ergodic Markov chains

Evaluation for generalization performance of learning algorithms has been the main thread of machine learning theoretical research. The previous bounds describing the generalization performance of the empirical risk minimization (ERM) algorithm are usually established based on independent and identically distributed (i.i.d.) samples. In this paper we go far beyond this classical framework by establishing the generalization bounds of the ERM algorithm with uniformly ergodic Markov chain (u.e.M.c.) samples. We prove the bounds on the rate of uniform convergence/relative uniform convergence of the ERM algorithm with u.e.M.c. samples, and show that the ERM algorithm with u.e.M.c. samples is consistent. The established theory underlies application of ERM type of learning algorithms.     

Continuum Limit of Lipschitz Learning on Graphs

Foundations of Computational Mathematics - Tackling semi-supervised learning problems with graph-based methods has become a trend in recent years since graphs can represent all kinds of data and...