U-过程集中不等式及其在学习理论中的应用

发布时间：2018-04-15 03:32

本文选题：U-过程 + 集中不等式　；参考：《华中科技大学》2015年博士论文

【摘要】：偏序学习和排序学习在机器学习、信息检索领域受到广泛的关注,在统计学习理论的框架下,我们基于U-过程的理论,对偏序学习和排序学习进行推广性的分析。本文面向两个紧密相连的研究领域：一是U-过程的最大值集中不等式,二是学习算法的推广性能的界。集中不等式描述一个随机变量是否集中在某个数值(如数学期望)附近。在统计学习理论中,一个主要的数学工具就是集中不等式,经验过程的集中不等式广泛的应用在学习算法的收敛速率的研究中。而一些学习问题又可以归结到U-统计的表达形式。这样促使我们研究U-过程最大值的集中不等式。U-过程与经验过程紧既有区别又有联系,这种紧密的联系使我们自然地想到用来证明经验过程的熵方法也能够用来证明U-过程。区别是U-过程具有弱的相关结构,所以我们使用退耦的技巧来分解这种复杂的结构。在本文中我们的主要贡献和创新点如下：首先,我们给出了三种类型的集中不等式： ·关于非退化核的集中不等式, ·关于退化核的集中不等式, ·关于相关随机变量的集中不等式。前两个是关于U-过程的,其实当我们把这种弱相关整体看成一个泛函时,这样仍然可以当做独立同分布的情形来证明,只是在证明过程中使用退耦不等式来分解这种非独立的结构。在证明第一个不等式时,我们分成了两步,先是证明非负核的U-过程的集中不等式,然后证明有界的核。我们使用非退化的不等式的研究了逐对损失的学习问题。第二个不等式的证明更复杂一些,我们证明的结果和经验过程有相同的结构。第三个是非独立的随机变量的泛函,可以看作是图上的数据,每一个随机变量是图的顶点,我们借助于分数覆盖的理论,把非独立的随机变量,分解成一些块的和,而每一块是独立同分布的随机变量之和,结合已有的结果和染色数的概念,我们就得到了非独立的集中不等式。此外,我们还推广了自有界函数的结构,定义了推广的自有界函数,并且给出了一个集中不等式。第二个是学习算法的推广性能的界。集中不等式和统计学习紧密的相连,二阶的U-过程是适用于逐对的损失的学习问题。在本文中我们主要集中于偏序学习和排序学习,采用两种分割假设空问的方法,一是基于相对风险的分割,二是基于方差的分割。采用我们新证明的不等式,应用到逐点损失学习,不同于已有的文献。在已有的结果中,作者采用了先把U-过程进行分解,然后分别用经验过程理论和退化的U-过程来界定。而我们的方法是统一的进行处理,然后再分解然后分别用Rademacher复杂度和Rademacher chaos复杂度来界定。这样做的好处是,对于基于U-过程的不同的经验风险最小化的学习问题,我们主要研究其损失函数的不同。我们分别提供了偏序学习的样本误差的上界和带惩罚的MP排序的风险的界。
[Abstract]:In the field of machine learning and information retrieval, partial order learning and ranking learning are paid more and more attention. Under the framework of statistical learning theory, we analyze the generalization of partial order learning and ranking learning based on U- process theory.This paper focuses on two closely connected research areas: one is the inequality of the maximum set of U- processes and the other is the bound of the generalized performance of the learning algorithm.A set inequality describes whether a random variable is concentrated near a numerical value, such as mathematical expectation.In statistical learning theory, one of the main mathematical tools is lumped inequality, which is widely used in the study of convergence rate of learning algorithm.Some learning problems can be attributed to the expression of U- statistics.This leads us to study the set inequality of the maximum value of U- process. U- process and empirical process are closely related and different. This close relation makes us naturally think that the entropy method used to prove the empirical process can also be used to prove the U- process.The difference is that U- processes have weak correlation structures, so we use decoupling techniques to decompose this complex structure.Our main contributions and innovations in this article are as follows:First, we give three types of set inequalities:On the set inequalities of nondegenerate kernels,On inequalities in sets of degenerate kernels,On the set inequality of correlated random variables.The first two are about U- processes, but when we look at this weakly correlated whole as a functional, we can still prove it as a case of independent co-distribution.It is only in the process of proof that decoupling inequalities are used to decompose this non-independent structure.When we prove the first inequality, we divide it into two steps: first, we prove the set inequality of the U-process with non-negative kernel, then we prove the bounded kernel.We study the learning problem of pair by pair loss by using nondegenerate inequalities.The proof of the second inequality is more complicated. The result of our proof has the same structure as the empirical process.The third is the functional of the dependent random variable, which can be regarded as the data on the graph, and each random variable is the vertex of the graph. We decompose the non-independent random variable into the sum of some blocks with the help of the fractional covering theory.And each block is the sum of random variables with independent and same distribution. Combined with the existing results and the concept of coloring number, we obtain an independent set inequality.In addition, we generalize the structure of the self-bounded function, define the generalized self-bounded function, and give a set inequality.The second is the bound of the generalized performance of the learning algorithm.Set inequality is closely related to statistical learning. Second order U- process is suitable for pair by pair loss learning problem.In this paper, we mainly focus on partial order learning and ranking learning. We use two segmentation methods, one is based on relative risk and the other is based on variance.By using our newly proved inequality, we apply it to point by point loss learning, which is different from the existing literature.In the existing results, the U- process is first decomposed and then defined by the empirical process theory and the degenerate U- process, respectively.Our method is unified, then decomposed and then defined by Rademacher complexity and Rademacher chaos complexity respectively.The advantage of this is that we mainly study the difference of loss function for different empirical risk minimization problems based on U- process.We provide the upper bound of the sample error of partial order learning and the bound of the risk of MP ordering with penalty, respectively.
【学位授予单位】：华中科技大学
【学位级别】：博士
【学位授予年份】：2015
【分类号】：TP18

【相似文献】