文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > 自然科学 > adaboost算法
侵权投诉

adaboost算法

Arbitrary-Norm Separating Plane O. L. Mangasarian

y

A plane separating two point sets in n-dimensional real space is constructed such that it minimizes the sum of arbitrary-norm distances of misclassi ed points to the plane. In contrast to previous approaches that used surrogates for distance-minimization, the present work is based on a precise norm-dependent explicit closed form for the projection of a point on a plane. This projection is used to formulate the separating-plane problem as a minimization of a convex function on a unit sphere in a norm dual to that of the arbitrary norm used. For the 1-norm, the problem can be solved in polynomial time by solving 2n linear programs or by solving a bilinear program. For a general p-norm, the minimization problem can be transformed via an exact penalty formulation to minimizing the sum of a convex function and a bilinear function on a convex set. For the one and in nity norms, a nite successive linearization algorithm can be used for solving the exact penalty formulation.

Abstract

1 Introduction One of the fundamental problems of machine learning is that of discriminating between two nite point sets in n-dimensional real space Rn . When the convex hulls of the two sets do not intersect, a single linear program can construct a strict separating plane such that each of the two open halfspaces generated by the plane contains one of the two sets 6, 12, 2]. Such a plane corresponds to a perceptron and can also be obtained by the iterative perceptron learning algorithm 22, 10] which can be interpreted as the Motzkin-Schoenberg iterative scheme for solving consistent linear inequalities 21]. When the convex hulls of the two sets intersect the iterative scheme fails because the underlying linear inequalities are inconsistent, while the linear programming approach must be provided with an error criterion to be minimized. We propose as a criterion here the sum of arbitrary-norm distances to the separating plane of points lying on the wrong side of the plane. Unfortunately, if precise distances are used, linearity of the objective function is lost, as will be shown in this work. What many of the previous approaches have tended to use, are distance surrogates that maintained linearity of the problem 9, 8, 20, 2] but did not measure distances of violating points to the separating plane. Invariably such approaches have to contend with the null solution that does not generate any separating plane. In contrast, our approach here excludes the null solution and depends on a closed form formula given in Theorem 2.1 below for the projection of a point in Rn onto a given plane using an arbitrary norm. In Section 3 we formulate the problem of obtaining a separating plane that minimizes the sum of distances of points on the wrong side of the plane, as that of minimizing a convex function on a unit sphere in a norm dual to that Mathematical Programming Technical Report 97-07, May 1997. Revised April 1998. This material

is based on research supported by NSF Grant CCR-9322479 and AFOSR Grant F49620-97-1-0326. y Computer Sciences Department, University of Wisconsin, 1210 West Dayton Street, Madison, WI 53706, olvi@cs.wisc.edu. The author gratefully acknowledges the gracious hospitality of the Mathematics Department of the University of California at San Diego during his sabbatical leave January-May 1997.

第1页

你可能喜欢

热门文档

相关文档

  • AdaBoost算法

    11 Adaboost 算法步骤 Adaboost算法是经过调整的Boosting算法,其能够对 弱学习得到的弱分类器的错误进行适应性(Adaptive)调整。上述算法中迭代了T次的主循环,每一次...

  • Adaboost 算法及原理

    Adaboost 算法及原理 3.1.2 AdaBoost 算法原理 AdaBoost 算法针对不同的训练集训练同一个基本分类器(弱分类器),然后 把这些在不同训练集上得到的分类器集合起来...

  • Adaboost算法入门详解_20130309

    (Strong classifier): sign ∑ 简单来说,Adaboost 有很多优点: 1)adaboost 是一种有很高精度的分类器 2)可以使用各种方法构建子分类器,adaboost 算法提供的是框架...

  • 关于adaboost算法的课件

    AdaBoost算法 算法 Adaboost算法是机器学习中一种比较重 要的特征分类算法,已被广泛应用人脸表 情识别、图像检索等应用中。就目前而言, 对Adaboost算法的研究以及应用...

  • ADABOOST算法

    ADABOOST算法_电力/水利_工程科技_专业资料。HARR-LIKE介绍目前因为做人脸识别的一个小项目,用到了 AdaBoost 的人脸识别算法,因为在 网上找到的所有的 AdaBoost 的...

  • adaboost算法

    Adaboost 算法分析 AdaBoost算法是Freund和Schapire根据在线分 配算法提出的,他们详细分析了AdaBoost算法错 误率的上界,以及为了使强分类器达到错误率, 算法所需要的...

  • adaboost算法

    AdaBoost算法简介 ? Adaboost是一种迭代算法,其核心思想是针对同 一个训练集训练不同的分类器(弱分类器),然后 把这些弱分类器集合起来,构成一个更强的最终 分类...

  • AdaBoost算法及应用

    Viola THE VIOLA/JONES FACE DETECTOR 2001年,Viola和Jones利用类Haar特征构造弱分类器,使用AdaBoost算法把弱分类器组合成强分类器,采用 Cascade结构把强分类器串联...

  • adaboost算法

    ///C/Users/ZJJ/AppData/Local/Temp/Rar$DI00.358/adaboost算法.txt[2012/3/22 11:04:10] fori=1:sectNum %第iter次迭代的搜索次数 thresh=minFea+(i-...

  • AdaBoost算法简介

    Adaboost 算法 1、AdaBoost 算法简介 AdaBoost 算法是 Freund 和 Schapire 根据在线分配算法提出的,他们详细分析了 AdaBoost 算法错误率的上界,以及为了使强分类器达到...

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email