结构化学习的噪声可学习性分析及其应用

噪声可学习性理论指出,有监督学习方法的性能会受到训练样本标记噪声的严重影响.然而,已有相关理论研究仅针对二类分类问题.致力于探究结构化学习问题受噪声影响的规律性.首先,注意到在结构化学习问题中,标注数据的噪声会在训练过程中被放大,使得训练过程中标记样本的噪声率高于标记样本的错误率.传统的噪声可学习性理论并未考虑结构化学习中的这一现象,从而低估了问题的复杂性.从结构化学习问题的噪声放大现象出发,提出了新的结构化学习问题的噪声可学习性理论.在此基础上,提出了有效训练数据规模的概念,这一指标可用于在实践中描述噪声学习问题的数据质量,并进一步分析了实际应用中的结构化学习模型在高噪声环境下向低阶模型回退的情况.实验结果证明了该理论的正确性及其在跨语言映射和协同训练方法中的应用价值和指导意义.

基于误差截尾假设的时序预测可学习性理论与算法

在收集和处理时间序列数据的过程中,难免会产生误差,而在很多现实情形中误差是自相关非独立的.已有的预测理论在分析误差自相关的时序数据时,往往需要知道预测算法所输出假设空间的显式表达,而对于一些假设空间不明确的模型,比如神经网络,尚未有系统的求解方法和理论保障来分析其在非平稳且误差自相关时序数据上的预测能力.本文基于误差截尾的假设,提出了时间序列的预测PAC可学习理论,并给出了数据依赖情形下的泛化误差界.该界限包含一个时序复杂度度量和一个差异度量,前者描述了序列数据的非平稳性,后者可在适当情形下从数据中估计得到.因此,该误差界并不依赖于假设空间的显式表达,具有较强的普适性.根据上述理论,本文提出了一种基于自回归模型的交替优化算法用于预测非平稳的时间序列数据.我们在真实数据集上进行实验,验证了本文提出算法的有效性.

分类超曲面算法复杂度研究

分类超曲面算法是一种简单的基于覆盖的分类算法.实验证明该算法具有分类正确率高、速度快的优点.但是,关于该算法的相关理论问题需要深入研究.文中对该算法的几个相关理论问题进行了研究.首先给出并证明了在分割的最大层数给定时算法假设空间的VC维,在此基础上结合可能近似正确(Probably Approximately Correct,PAC)学习框架,得出了对算法样本复杂度的估计,使得分类超曲面算法保证可PAC学习到任意目标概念.其次,分析了算法的时间复杂度和空间复杂度.最后,给出了无矛盾样本集的概念,并证明当输入样本集是有限无矛盾样本集的条件下,算法一定是收敛的.