??xml version="1.0" encoding="utf-8" standalone="yes"?>BlogJava-Jasper's Java Jacalhttp://www.ymeg.top/zhenandaci/嘉士伯的Java屋zh-cnSun, 25 Aug 2019 06:40:57 GMTSun, 25 Aug 2019 06:40:57 GMT60又晒自己的设?/title><link>http://www.ymeg.top/zhenandaci/archive/2009/05/08/269507.html</link><dc:creator>Jasper</dc:creator><author>Jasper</author><pubDate>Thu, 07 May 2009 16:32:00 GMT</pubDate><guid>http://www.ymeg.top/zhenandaci/archive/2009/05/08/269507.html</guid><wfw:comment>http://www.ymeg.top/zhenandaci/comments/269507.html</wfw:comment><comments>http://www.ymeg.top/zhenandaci/archive/2009/05/08/269507.html#Feedback</comments><slash:comments>7</slash:comments><wfw:commentRss>http://www.ymeg.top/zhenandaci/comments/commentRss/269507.html</wfw:commentRss><trackback:ping>http://www.ymeg.top/zhenandaci/services/trackbacks/269507.html</trackback:ping><description><![CDATA[q回是帮自己家小妞的|店做的店标,宣传什么的,所以风格相似恰恰是我想要的? <p> </p> <p><img src="http://logo.taobao.com/shop-logo/65/44/T19lpgXeVW6dL1upjX.jpg" alt="" /></p> <p>|店的Logo。那大腿不是别h的,正是韩国歌星宝儿……<br /> <br /> </p> <p><img src="http://p2.images22.51img1.com/6000/yuki0035/2c93ab451dfdeb44ce75d436e31e9540.jpg" alt="" /></p> <p>她跟我说上面q张图最大的问题在于太有夜店风|与她的店不符。不q用着用着Q她自己倒也喜欢上了?br /> </p> <p><img src="http://p1.images22.51img1.com/6000/yuki0035/140297fdbc3dc9c6c7ee96d9e02d89ac.jpg" alt="" /> </p> <p>q个是刚出炉?月新Ƅ预告Q照片里的h可全是她……</p> <img src ="http://www.ymeg.top/zhenandaci/aggbug/269507.html" width = "1" height = "1" /><br><br><div align=right><a style="text-decoration:none;" href="http://www.ymeg.top/zhenandaci/" target="_blank">Jasper</a> 2009-05-08 00:32 <a href="http://www.ymeg.top/zhenandaci/archive/2009/05/08/269507.html#Feedback" target="_blank" style="text-decoration:none;">发表评论</a></div>]]></description></item><item><title>文本分类入门Q番外篇Q特征选择与特征权重计的区别http://www.ymeg.top/zhenandaci/archive/2009/04/19/266388.htmlJasperJasperSun, 19 Apr 2009 03:40:00 GMThttp://www.ymeg.top/zhenandaci/archive/2009/04/19/266388.htmlhttp://www.ymeg.top/zhenandaci/comments/266388.htmlhttp://www.ymeg.top/zhenandaci/archive/2009/04/19/266388.html#Feedback48http://www.ymeg.top/zhenandaci/comments/commentRss/266388.htmlhttp://www.ymeg.top/zhenandaci/services/trackbacks/266388.html在文本分cȝq程中,特征Q也可以单的理解?#8220;?#8221;Q从人类能够理解的Ş式{换ؓ计算够理解的形式Ӟ实际上经q了两步骤的量化——特征选择阶段的重要程度量化和具体文本{化ؓ向量时的特征权重量化。初ơ接触文本分cȝ人很Ҏhq两个步骤用的Ҏ和各自的目的Q因而我l常听到读者有cM“如何使用TFIDF做特征选择”或?#8220;卡方验量化权重后每篇文章都一?#8221;{等困惑?/span>

文本分类本质上也是一个模式识别的问题Q因此我惛_用一个更直观的例子来说说特征选择和权重量化到底各自是什么东西,当然Q一旦解释清楚,你马上就会觉得文本分c这东西实在白痴Q实在没什么技术含量,你也׃会再l箋看我的技术博客,不过我不担心Q因Z已经t上了更光明的道路(W)Q我高兴q来不及?/span>

x通过指纹来识别一个h的n份,只看一个h的指U,当然说不Z姓甚名谁Q识别的q程实际上是比对的过E,要与已有的指U库比较Q找出相同的Q或者说怼C定程度的那一个?/span>

首要的问题是Qh的指U太复杂Q包含太多的位置和几何ŞӞ要完全重C个h的指U,存储和计都是大ȝ。因此第一步L一个特征选择的问题,我们把全人类的指Uwl计一下,看看哪几个位|能够最好的区分不同的h。显然不同的位置效果很不一P在有的位|上Q我的指UҎ是什么ŞӞ其他Z大都是这个ŞӞq个位置׃h区分度,或者说不具有表征性,或者说Q对分类问题来说Q它的重要程度低。这L位置我们們֐于在识别的时候根本不看它Q不考虑它?/span>

那怎么看谁重要谁不重要呢?q就依赖于具体的选择Ҏ如何来量化重要程度,对卡Ҏ验和信息增益q类Ҏ来说Q量化以后的得分大的特征就重要(也就是说Q有可能有些ҎQ是得分小的越重要Q?/span>

比如说你?/span>10个位|,他们的重要程度分别是Q?/span>

   1 2   3   4   5 6   7 8 9  10

Q?/span>20Q?/span>5Q?/span>10Q?/span>20Q?/span>30Q?/span>15Q?/span>4Q?/span>3Q?/span>7Q?/span> 3Q?/span>

昄W?/span>1Q第3Q?/span>4Q?/span>5Q?/span>6个位|比其他位置更重要,而相对的Q第1个位|又比第3个位|更重要?/span>

识别Ӟ我们只在那些重要的位|上采样。当今的指纹识别pȝQ大都只用到人指U的5个位|(惊讶么?只要5个位|的信息可以区?/span>60亿hQ,q?/span>5个位|就是经q特征选择q程而得以保留的pȝ特征集合。假设这个就是刚才的例子Q那么该集合应该是:

Q第1个位|,W?/span>3个位|,W?/span>4个位|,W?/span>5个位|,W?/span>6个位|)

当然Q具体的W?/span>3个位|是指纹中的哪个位置你自己d清楚?/span>

定了这5个位|之后,可以把一个h的指UҎ到q个只有5个维度的I间中,我们把他在5个位|上的几何Ş状分别{换成一个具体的|q就是特征权重的计算。依据什么来转换Q就是你选择的特征权重量化方法,在文本分cMQ最常用的就?/span>TFIDF?/span>

我想一定是“权重“q个词误g所有hQ让大家以ؓTFIDF计算出的g表的是特征的重要E度Q其实完全不是。例如我们有一位男同学Q他的指U向量是Q?/span>

Q?/span>10Q?/span>3Q?/span>4Q?/span>20Q?/span>5Q?/span>

你注意到他第1个位|的得分Q?/span>10Q比W?/span>3个位|的得分Q?/span>3Q高Q那么能说第1个位|比W?/span>3个位|重要么Q如果再有一位女同学Q她的指U向量是Q?/span>

Q?/span>10Q?/span>20Q?/span>4Q?/span>20Q?/span>5Q?/span>

看看Q第1个位|得分(10Q又比第3个位|(20Q低了,那这两个位置到底哪个更重要呢Q答案是W?/span>1个位|更重要Q但q不是在特征权重计算q一步体现出来的Q而是在我们特征选择的时候就定了,W?/span>1个位|比W?/span>3个位|更重要?/span>

因此要记住,通过TFIDF计算一个特征的权重Ӟ该权重体现出的根本不是特征的重要E度Q?/span>

那它代表什么?再看看两位同学的指纹Q放CP

Q?/span>10Q?/span> 3Q?/span>4Q?/span>20Q?/span>5Q?/span>

Q?/span>10Q?/span>20Q?/span>4Q?/span>20Q?/span>5Q?/span>

在第三个位置上女同学的权重高于男同学Q这不代表该奛_学在指纹的这个位|上?#8220;优秀“Q毕竟,指纹q有什么优U不优U的分别么Q笑Q,也不代表她的q个位置比男同学的这个位|更重要Q?/span>3?/span>20q两个得分,仅仅代表他们?#8221;不同“?/span>

在文本分cM也是如此Q比如我们的pȝ特征集合只有两个词:

Q经,发展Q?/span>

q两个词是用卡Ҏ验(特征选择Q选出来的Q有一文章的向量形式?/span>

Q?/span>2Q?/span>5Q?/span>

另一?/span>

Q?/span>3Q?/span>4Q?/span>

q两个向量Ş式就是用TFIDF出来的Q很Ҏ看出两篇文章不是同一,Z么?因ؓ他们的特征权重根本不一P所以说权重代表的是差别Q而不是优劣。想想你?#8220;l济q个词在W二文章中得分高,因此它在W二文章中比在W一文章中更重?#8220;Q这句话代表什么意义呢Q你自己都不知道吧(W)?/span>

所以,当再说v使用TFIDF来计特征权重时Q最好把“权重“q个字眼忘掉Q我们就把它说成计算得分好了Q甚?#8221;得分“也不太好Q因ZhM不自觉的认ؓQ得分高的就更重要)Q或者就仅仅说成是量化?/span>

如此Q你再也不会拿TFIDFd特征选择了?/span>

?/span>TipsQؓ什么有的论文里实使用?/span>TFIDF作特征选择呢?

严格说来q不是不可以Q而且严格说来只要有一U方法能够从一堆特征中挑出数的一些,它就可以叫做一U特征选择ҎQ就q?#8220;随机选取一部分“都算是一U,而且效果q没有差到惊人的地步哦!q是可以分对一大半的哦Q所以有的hqTFIDF的得分来把特征排排序Q取得分最大的几个q入pȝ特征集合Q效果也q行Q毕竟,q随机选取效果也都q行Q,怎么说呢Q他们愿意这么干p么干吧。就像咱国家非得实行户口制度Q这个制度说不出M道理Q也不见他带来Q何好处,但不也没影响二十一世纪成ؓ中国的世U么Q呵c?/span>



Jasper 2009-04-19 11:40 发表评论
]]>
又怠慢?/title><link>http://www.ymeg.top/zhenandaci/archive/2009/04/18/266294.html</link><dc:creator>Jasper</dc:creator><author>Jasper</author><pubDate>Sat, 18 Apr 2009 07:02:00 GMT</pubDate><guid>http://www.ymeg.top/zhenandaci/archive/2009/04/18/266294.html</guid><wfw:comment>http://www.ymeg.top/zhenandaci/comments/266294.html</wfw:comment><comments>http://www.ymeg.top/zhenandaci/archive/2009/04/18/266294.html#Feedback</comments><slash:comments>3</slash:comments><wfw:commentRss>http://www.ymeg.top/zhenandaci/comments/commentRss/266294.html</wfw:commentRss><trackback:ping>http://www.ymeg.top/zhenandaci/services/trackbacks/266294.html</trackback:ping><description><![CDATA[又小忙了几天。打写一澄清特征选择和特征权重计中许多Ҏ误解的问题的文章Q不知大家有没有兴趣? <img src ="http://www.ymeg.top/zhenandaci/aggbug/266294.html" width = "1" height = "1" /><br><br><div align=right><a style="text-decoration:none;" href="http://www.ymeg.top/zhenandaci/" target="_blank">Jasper</a> 2009-04-18 15:02 <a href="http://www.ymeg.top/zhenandaci/archive/2009/04/18/266294.html#Feedback" target="_blank" style="text-decoration:none;">发表评论</a></div>]]></description></item><item><title>SVM入门Q十Q将SVM用于多类分类http://www.ymeg.top/zhenandaci/archive/2009/03/26/262113.htmlJasperJasperThu, 26 Mar 2009 06:30:00 GMThttp://www.ymeg.top/zhenandaci/archive/2009/03/26/262113.htmlhttp://www.ymeg.top/zhenandaci/comments/262113.htmlhttp://www.ymeg.top/zhenandaci/archive/2009/03/26/262113.html#Feedback62http://www.ymeg.top/zhenandaci/comments/commentRss/262113.htmlhttp://www.ymeg.top/zhenandaci/services/trackbacks/262113.html?SVM的那几张囑֏以看出来QSVM是一U典型的两类分类器,卛_只回{属于正c还是负cȝ问题。而现实中要解决的问题Q往往是多cȝ问题Q少部分例外Q例如垃N件过滤,只需要确?#8220;?#8221;q是“不是”垃圾邮gQ,比如文本分类Q比如数字识别。如何由两类分类器得到多cdcdQ就是一个值得研究的问题?

q以文本分类ZQ现成的Ҏ有很多,其中一U一x逸的ҎQ就是真的一ơ性考虑所有样本,q求解一个多目标函数的优化问题,一ơ性得到多个分c面Q就像下图这P

clip_image001

多个^面把I间划分为多个区域,每个区域对应一个类别,l一文章,看它落在哪个区域q道了它的分类?

看v来很对不对Q只可惜q种法q基本停留在UR上,因ؓ一ơ性求解的Ҏ计算量实在太大,大到无法实用的地步?

E稍退一步,我们׃惛_所?#8220;一cd其余”的方法,是每次仍然解一个两cdcȝ问题。比如我们有5个类别,W一ơ就把类?的样本定为正hQ其?Q?Q?Q?的样本合h定ؓ负样本,q样得到一个两cdcdQ它能够指出一文章是q是不是W?cȝQ第二次我们把类? 的样本定为正hQ把1Q?Q?Q?的样本合h定ؓ负样本,得到一个分cdQ如此下去,我们可以得到5个这L两类分类器(L和类别的数目一_。到了有文章需要分cȝ时候,我们拿着q篇文章挨个分类器的问:是属于你的么Q是属于你的么?哪个分类器点头说是了Q文章的cdq定了。这U方法的好处是每个优化问题的规模比较,而且分类的时候速度很快Q只需要调?个分cdq道了l果Q。但有时也会出现两种很尴的情况Q例如拿一文章问了一圈,每一个分cd都说它是属于它那一cȝQ或者每一个分cd都说它不是它那一cȝQ前者叫分类重叠现象Q后者叫不可分类现象。分c重叠倒还好办Q随侉K一个结果都不至于太谱Q或者看看这文章到各个^面的距离Q哪个远判l哪个。不可分cȝ象就着实难办了Q只能把它分l第6个类别了……更要命的是,本来各个cd的样本数目是差不多的Q但“其余”的那一cL本数L要数倍于正类Q因为它是除正类以外其他cd的样本之和嘛Q,q就Zؓ的造成了上一节所说的“数据集偏?#8221;问题?

因此我们q得再退一步,q是解两cdc问题,q是每次选一个类的样本作正类hQ而负cL本则变成只选一个类Q称?#8220;一对一单挑”的方法,哦,不对Q没有单挑,是“一对一”的方法,呵呵Q,q就避免了偏斜。因此过E就是算样一些分cdQ第一个只回答“是第1c还是第2c?#8221;Q第二个只回{?#8220;是第1c还是第3c?#8221;Q第三个只回{?#8220;是第1c还是第4c?#8221;Q如此下去,你也可以马上得出Q这L分类器应该有5 X 4/2=10个(通式是,如果有k个类别,则ȝ两类分类器数目ؓk(k-1)/2Q。虽然分cd的数目多了,但是在训l阶D(也就是算些分cd的分cd^面时Q所用的L间却?#8220;一cd其余”Ҏ很多,在真正用来分cȝ时候,把一文章扔l所有分cdQ第一个分cd会投说它是“1”或?#8220;2”Q第二个会说它是“1”或?#8220;3”Q让每一个都投上自己的一,最后统计票敎ͼ如果cd“1”得票最多,判q篇文章属于W?cR这U方法显然也会有分类重叠的现象,但不会有不可分类现象Q因为M可能所有类别的数都是0。看h够好么?其实不然Q想惛_cM文章,我们调用了多个分类器?10个,q还是类别数?的时候,cd数如果是1000Q要调用的分cd数目会上升至U?00,000个(cd数的qx量Q。这如何是好Q?

看来我们必须再退一步,在分cȝ时候下功夫Q我们还是像一对一Ҏ那样来训l,只是在对一文章进行分cM前,我们先按照下面图的样子来l织分类器(如你所见,q是一个有向无环图Q因此这U方法也叫做DAG SVMQ?

clip_image002

q样在分cL,我们可以先问分cd“1?”Q意思是它能够回{?#8220;是第1c还是第5c?#8221;Q,如果它回{?Q我们就往左走Q再?#8220;2?”q个分类器,如果它还说是“5”Q我们就l箋往左走Q这样一直问下去Q就可以得到分类l果。好处在哪?我们其实只调用了4个分cdQ如果类别数是kQ则只调用k-1个)Q分c速度飞快Q且没有分类重叠和不可分cȝ象!~点在哪Q假如最一开始的分类器回{错误(明明是类?的文章,它说成了5Q,那么后面的分cd是无论如何也无法U正它的错误的(因ؓ后面的分cd压根没有出现“1”q个cd标签Q,其实对下面每一层的分类器都存在q种错误向下累积的现象。?

不过不要被DAGҎ的错误篏U吓倒,错误累积在一对其余和一对一Ҏ中也都存在,DAGҎ好于它们的地方就在于Q篏U的上限Q不是大是,L有定论的Q有理论证明。而一对其余和一对一Ҏ中,管每一个两cdcd的泛化误差限是知道的Q但是合h做多cdcȝ时候,误差上界是多,没h知道Q这意味着准确率低?也是有可能的Q这多让人郁闗?

而且现在DAGҎ根节点的选取Q也是如何选第一个参与分cȝ分类器)Q也有一些方法可以改善整体效果,我们d望根节点犯错误为好Q因此参与第一ơ分cȝ两个cdQ最好是差别特别特别大,大到以至于不太可能把他们分错Q或者我们就d在两cdcM正确率最高的那个分类器作根节点,或者我们让两类分类器在分类的时候,不光输出cd的标{,q输Z个类?#8220;|信?#8221;的东东,当它对自ql果不太自信的时候,我们׃光按照它的输Q把它旁边的那条路也C赎ͼ{等?

大TipsQSVM的计复杂度

使用SVMq行分类的时候,实际上是训练和分cM个完全不同的q程Q因而讨论复杂度׃能一概而论Q我们这里所说的主要是训l阶D늚复杂度,卌那个二次规划问题的复杂度。对q个问题的解Q基本上要划分ؓ两大块,解析解和数D?

解析解就是理Z的解Q它的Ş式是表达式,因此它是_的,一个问题只要有解(无解的问题还跟着掺和什么呀Q哈哈)Q那它的解析解是一定存在的。当然存在是一回事Q能够解出来Q或者可以在可以承受的时间范围内解出来,是另一回事了。对SVM来说Q求得解析解的时间复杂度最坏可以达到O(Nsv3)Q其中Nsv是支持向量的个数Q而虽然没有固定的比例Q但支持向量的个数多也和训l集的大有兟?

数D是可以使用的解Q是一个一个的敎ͼ往往都是q似解。求数D的过E非常像ID法,从一个数开始,试一试它当解效果怎样Q不满一定条Ӟ叫做停机条gQ就是满个以后就认ؓ解够精了Q不需要l算下去了)p下一个,当然下一个数不是乱选的Q也有一定章法可循。有的算法,每次只尝试一个数Q有的就试多个Q而且找下一个数字(或下一l数Q的Ҏ也各不相同,停机条g也各不相同,最l得到的解精度也各不相同Q可见对求数D的复杂度的讨Z能脱开具体的算法?

一个具体的法QBunch-Kaufman训练法Q典型的旉复杂度在O(Nsv3+LNsv2+dLNsv)和O(dL2)之间Q其中Nsv是支持向量的个数QL是训l集h的个敎ͼd是每个样本的l数Q原始的l数Q没有经q向高维I间映射之前的维敎ͼ。复杂度会有变化Q是因ؓ它不光跟输入问题的规模有养I不光和样本的数量Q维数有养IQ也和问题最l的解有养Ix持向量有养IQ如果支持向量比较少Q过E会快很多,如果支持向量很多Q接q于h的数量,׃产生O(dL2)q个十分p糕的结果(l?0Q?00个样本,每个h1000l_基本׃用算了,不出来Q呵呵,而这U输入规模对文本分类来说太正怺Q?

q样再回头看׃明白Z么一对一Ҏ管要训l的两类分类器数量多Q但L间实际上比一对其余方法要了Q因Z对其余方法每ơ训l都考虑了所有样本(只是每次把不同的部分划分为正cL者负c而已Q?span style="font-family: ; font-size: 10.5pt; mso-bidi-font-family: 'Times New Roman'; mso-bidi-font-size: 11.0pt; mso-ascii-font-family: Calibri; mso-hansi-font-family: Calibri; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA">Q自然慢上很多?/span>



Jasper 2009-03-26 14:30 发表评论
]]>
文本分类入门Q十一Q特征选择Ҏ之信息增?/title><link>http://www.ymeg.top/zhenandaci/archive/2009/03/24/261701.html</link><dc:creator>Jasper</dc:creator><author>Jasper</author><pubDate>Tue, 24 Mar 2009 06:54:00 GMT</pubDate><guid>http://www.ymeg.top/zhenandaci/archive/2009/03/24/261701.html</guid><wfw:comment>http://www.ymeg.top/zhenandaci/comments/261701.html</wfw:comment><comments>http://www.ymeg.top/zhenandaci/archive/2009/03/24/261701.html#Feedback</comments><slash:comments>65</slash:comments><wfw:commentRss>http://www.ymeg.top/zhenandaci/comments/commentRss/261701.html</wfw:commentRss><trackback:ping>http://www.ymeg.top/zhenandaci/services/trackbacks/261701.html</trackback:ping><description><![CDATA[<p>前文提到q,除了开Ҏ验(CHIQ以外,信息增益QIGQInformation GainQ也是很有效的特征选择Ҏ。但凡是特征选择QL在将特征的重要程度量化之后再q行选择Q而如何量化特征的重要性,成了各U方法间最大的不同。开Ҏ验中使用特征与类别间的关联性来q行q个量化Q关联性越强,特征得分高Q该特征应该被保留? <p>在信息增益中Q重要性的衡量标准是看特征能够ؓ分类pȝ带来多少信息Q带来的信息多Q该特征重要? <p>因此先回忆一下信息论中有关信息量Q就?#8220;?#8221;Q的定义。说有这么一个变量XQ它可能的取值有n多种Q分别是x<sub>1</sub>Qx<sub>2</sub>Q?#8230;…Qx<sub>n</sub>Q每一U取到的概率分别是P<sub>1</sub>QP<sub>2</sub>Q?#8230;…QP<sub>n</sub>Q那么X的熵定义ؓQ? <p><a href="http://www.ymeg.top/images/blogjava_net/zhenandaci/WindowsLiveWriter/7fce385fe28b_D158/clip_image002_2.gif"><img style="border-bottom: 0px; border-left: 0px; display: inline; border-top: 0px; border-right: 0px" title="clip_image002" border="0" hspace="12" alt="clip_image002" src="http://www.ymeg.top/images/blogjava_net/zhenandaci/WindowsLiveWriter/7fce385fe28b_D158/clip_image002_thumb.gif" width="231" height="69" /></a></p> <p>意思就是一个变量可能的变化多Q反而跟变量具体的取值没有Q何关p,只和值的U类多少以及发生概率有关Q,它携带的信息量就大Q因此我一直觉得我们的政策法规信息量非常大Q因为它变化很多Q基本朝令夕改,W)? <p>对分cȝl来_cdC是变量,它可能的取值是C<sub>1</sub>QC<sub>2</sub>Q?#8230;…QC<sub>n</sub>Q而每一个类别出现的概率是P(C<sub>1</sub>)QP(C<sub>2</sub>)Q?#8230;…QP(C<sub>n</sub>)Q因此n是cd的L。此时分cȝl的熵就可以表示为:</p> <p><a href="http://www.ymeg.top/images/blogjava_net/zhenandaci/WindowsLiveWriter/7fce385fe28b_D158/clip_image002%5B4%5D.gif"><img style="border-bottom: 0px; border-left: 0px; display: inline; border-top: 0px; border-right: 0px" title="clip_image002[4]" border="0" hspace="12" alt="clip_image002[4]" src="http://www.ymeg.top/images/blogjava_net/zhenandaci/WindowsLiveWriter/7fce385fe28b_D158/clip_image002%5B4%5D_thumb.gif" width="240" height="54" /></a></p> <p>有同学说不好理解呀Q这h好了,文本分类pȝ的作用就是输Z个表C文本属于哪个类别的|而这个值可能是C<sub>1</sub>QC<sub>2</sub>Q?#8230;…QC<sub>n</sub>Q因此这个值所携带的信息量是上式中的q么多? <p>信息增益是针对一个一个的特征而言的,是看一个特征tQ系l有它和没它的时候信息量各是多少Q两者的差值就是这个特征给pȝ带来的信息量Q即增益。系l含有特征t的时候信息量很好计算Q就是刚才的式子Q它表示的是包含所有特征时pȝ的信息量? <p>问题是当pȝ不包含tӞ信息量如何计?我们换个角度想问题,把系l要做的事情惌成这P说教室里有很多位,学生们每ơ上课进来的时候可以随便坐Q因而变化是很大的(无数U可能的座次情况Q;但是现在有一个位,看黑板很清楚Q听老师讲也很清楚,于是校长的小舅子的姐姐的奛_托关p(真辗转啊Q,把这个位定下来了,每次只能l她坐,别h不行Q此时情冉|样Q对于ơ的可能情况来说Q我们很Ҏ看出以下两种情况是等LQ(1Q教室里没有q个座位Q(2Q教室里虽然有这个位,但其他h不能坐(因ؓ反正它也不能参与到变化中来,它是不变的)? <p>对应到我们的pȝ中,是下面的等PQ?Q系l不包含特征tQ(2Q系l虽然包含特征tQ但是t已经固定了,不能变化? <p>我们计算分类pȝ不包含特征t的时候,׃用情况(2Q来代替Q就是计当一个特征t不能变化Ӟpȝ的信息量是多。这个信息量其实也有专门的名Uͼ叫?#8220;条g?#8221;Q条件嘛Q自然就是指“t已经固定“q个条g? <p>但是问题接踵而至Q例如一个特征XQ它可能的取值有n多种Qx<sub>1</sub>Qx<sub>2</sub>Q?#8230;…Qx<sub>n</sub>Q,当计条件熵而需要把它固定的时候,要把它固定在哪一个g呢?{案是每一U可能都要固定一下,计算n个|然后取均值才是条件熵。而取均g不是单的加一加然后除以nQ而是要用每个值出现的概率来算q_Q简单理解,是一个值出现的可能性比较大Q固定在它上面时出来的信息量占的比重就要多一些)? <p>因此有这样两个条件熵的表辑ּQ? <p><a href="http://www.ymeg.top/images/blogjava_net/zhenandaci/WindowsLiveWriter/7fce385fe28b_D158/clip_image002%5B6%5D.gif"><img style="border-bottom: 0px; border-left: 0px; display: inline; border-top: 0px; border-right: 0px" title="clip_image002[6]" border="0" hspace="12" alt="clip_image002[6]" src="http://www.ymeg.top/images/blogjava_net/zhenandaci/WindowsLiveWriter/7fce385fe28b_D158/clip_image002%5B6%5D_thumb.gif" width="170" height="46" /></a></p> <p>q是指特征X被固定ؓ值x<sub>i</sub>时的条g熵,</p> <p><a href="http://www.ymeg.top/images/blogjava_net/zhenandaci/WindowsLiveWriter/7fce385fe28b_D158/clip_image002%5B8%5D.gif"><img style="border-bottom: 0px; border-left: 0px; display: inline; border-top: 0px; border-right: 0px" title="clip_image002[8]" border="0" hspace="12" alt="clip_image002[8]" src="http://www.ymeg.top/images/blogjava_net/zhenandaci/WindowsLiveWriter/7fce385fe28b_D158/clip_image002%5B8%5D_thumb.gif" width="132" height="44" /></a></p> <p>q是指特征X被固定时的条件熵Q注意与上式在意义上的区别。从刚才计算均值的讨论可以看出来,W二个式子与W一个式子的关系是Q?/p> <p><a href="http://www.ymeg.top/images/blogjava_net/zhenandaci/WindowsLiveWriter/7fce385fe28b_D158/clip_image004_2.gif"><img style="border-bottom: 0px; border-left: 0px; display: inline; border-top: 0px; border-right: 0px" title="clip_image004" border="0" hspace="12" alt="clip_image004" src="http://www.ymeg.top/images/blogjava_net/zhenandaci/WindowsLiveWriter/7fce385fe28b_D158/clip_image004_thumb.gif" width="656" height="123" /></a></p> <p>具体到我们文本分cȝl中的特征tQt有几个可能的值呢Q注意t是指一个固定的特征Q比如他是指关键词“l济”或?#8220;体育”Q当我们说特?#8220;l济”可能的取值时Q实际上只有两个Q?#8220;l济”要么出现Q要么不出现。一般的Qt的取值只有tQ代表t出现Q和<a href="http://www.ymeg.top/images/blogjava_net/zhenandaci/WindowsLiveWriter/7fce385fe28b_D158/clip_image006_2.gif"><img style="border-bottom: 0px; border-left: 0px; display: inline; border-top: 0px; border-right: 0px" title="clip_image006" border="0" alt="clip_image006" src="http://www.ymeg.top/images/blogjava_net/zhenandaci/WindowsLiveWriter/7fce385fe28b_D158/clip_image006_thumb.gif" width="11" height="29" /></a>Q代表t不出玎ͼQ注意系l包含t但t 不出CpȝҎ不包含t可是两回事? <p>因此固定t时系l的条g熵就有了Qؓ了区别t出现时的W号与特征t本n的符P我们用T代表特征Q而用t代表T出现Q那么: <p><a href="http://www.ymeg.top/images/blogjava_net/zhenandaci/WindowsLiveWriter/7fce385fe28b_D158/clip_image008_2.gif"><img style="border-bottom: 0px; border-left: 0px; display: inline; border-top: 0px; border-right: 0px" title="clip_image008" border="0" hspace="12" alt="clip_image008" src="http://www.ymeg.top/images/blogjava_net/zhenandaci/WindowsLiveWriter/7fce385fe28b_D158/clip_image008_thumb.gif" width="376" height="58" /></a></p> <p>与刚才的式子对照一下,含义很清楚对吧,P(t)是T出现的概率,<a href="http://www.ymeg.top/images/blogjava_net/zhenandaci/WindowsLiveWriter/7fce385fe28b_D158/clip_image010_2.gif"><img style="border-bottom: 0px; border-left: 0px; display: inline; border-top: 0px; border-right: 0px" title="clip_image010" border="0" alt="clip_image010" src="http://www.ymeg.top/images/blogjava_net/zhenandaci/WindowsLiveWriter/7fce385fe28b_D158/clip_image010_thumb.gif" width="35" height="32" /></a>是T不出现的概率。这个式子可以进一步展开Q其中的</p> <p><a href="http://www.ymeg.top/images/blogjava_net/zhenandaci/WindowsLiveWriter/7fce385fe28b_D158/clip_image012_2.gif"><img style="border-bottom: 0px; border-left: 0px; display: inline; border-top: 0px; border-right: 0px" title="clip_image012" border="0" hspace="12" alt="clip_image012" src="http://www.ymeg.top/images/blogjava_net/zhenandaci/WindowsLiveWriter/7fce385fe28b_D158/clip_image012_thumb.gif" width="264" height="57" /></a></p> <p>另一半就可以展开为:</p> <p><a href="http://www.ymeg.top/images/blogjava_net/zhenandaci/WindowsLiveWriter/7fce385fe28b_D158/clip_image014_2.gif"><img style="border-bottom: 0px; border-left: 0px; display: inline; border-top: 0px; border-right: 0px" title="clip_image014" border="0" hspace="12" alt="clip_image014" src="http://www.ymeg.top/images/blogjava_net/zhenandaci/WindowsLiveWriter/7fce385fe28b_D158/clip_image014_thumb.gif" width="301" height="63" /></a></p> <p>因此特征Tl系l带来的信息增益可以写成系l原本的熵与固定特征T后的条g熵之差: <p><a href="http://www.ymeg.top/images/blogjava_net/zhenandaci/WindowsLiveWriter/7fce385fe28b_D158/clip_image016_2.gif"><img style="border-bottom: 0px; border-left: 0px; display: inline; border-top: 0px; border-right: 0px" title="clip_image016" border="0" hspace="12" alt="clip_image016" src="http://www.ymeg.top/images/blogjava_net/zhenandaci/WindowsLiveWriter/7fce385fe28b_D158/clip_image016_thumb.gif" width="583" height="173" /></a> <p>公式中的东西看上d多,其实也都很好计算。比如P(C<sub>i</sub>)Q表C类别C<sub>i</sub>出现的概率,其实只要?除以cdL得CQ这是说你^{的看待每个cd而忽略它们的大小时这LQ如果考虑了大就要把大小的媄响加q去Q。再比如P(t)Q就是特征T出现的概率,只要用出现过T的文档数除以L档数可以了Q再比如P(C<sub>i</sub>|t)表示出现T的时候,cdC<sub>i</sub>出现的概率,只要用出CTq且属于cdC<sub>i</sub>的文档数除以出现了T的文档数可以了? <p>从以上讨Z可以看出Q信息增益也是考虑了特征出现和不出CU情况,与开Ҏ验一P是比较全面的Q因而效果不错。但信息增益最大的问题q在于它只能考察特征Ҏ个系l的贡献Q而不能具体到某个cd上,q就使得它只适合用来做所?#8220;全局”的特征选择Q指所有的c都使用相同的特征集合)Q而无法做“本地”的特征选择Q每个类别有自己的特征集合,因ؓ有的词,对这个类别很有区分度Q对另一个类别则无轻重Q? <p>看看Q导出的q程其实很简单,没有什么神U的对不寏V可有的学术论文里就喜欢把这U本来很直白的东西写得很晦ӆQ仿佛只有读者看不懂才是作者的真正成功? <p>׃是新一代的学者,׃没有知识不怕被别h看出来,׃有知识也不怕教l别人。所以咱都把事情说简单点Q说明白点,大家好,才是真的好?</p> <img src ="http://www.ymeg.top/zhenandaci/aggbug/261701.html" width = "1" height = "1" /><br><br><div align=right><a style="text-decoration:none;" href="http://www.ymeg.top/zhenandaci/" target="_blank">Jasper</a> 2009-03-24 14:54 <a href="http://www.ymeg.top/zhenandaci/archive/2009/03/24/261701.html#Feedback" target="_blank" style="text-decoration:none;">发表评论</a></div>]]></description></item><item><title>SVM入门Q九Q松弛变量(l)http://www.ymeg.top/zhenandaci/archive/2009/03/17/260315.htmlJasperJasperTue, 17 Mar 2009 12:04:00 GMThttp://www.ymeg.top/zhenandaci/archive/2009/03/17/260315.htmlhttp://www.ymeg.top/zhenandaci/comments/260315.htmlhttp://www.ymeg.top/zhenandaci/archive/2009/03/17/260315.html#Feedback29http://www.ymeg.top/zhenandaci/comments/commentRss/260315.htmlhttp://www.ymeg.top/zhenandaci/services/trackbacks/260315.html接下来要说的东西其实不是村ּ变量本nQ但׃是ؓ了用松弛变量才引入的,因此攑֜q里也算合适,那就是惩|因子C。回头看一眼引入了村ּ变量以后的优化问题:

clip_image002

注意其中C的位|,也可以回想一下C所L作用Q表征你有多么重视离点QC大重视,不想丢掉它们)。这个式子是以前做SVM的h写的Q大家也p么用Q但没有M规定说必d所有的村ּ变量都用同一个惩|因子,我们完全可以l每一个离点都用不同的CQ这时就意味着你对每个h的重视程度都不一P有些h丢了也就丢了Q错了也错了,q些q一个比较小的CQ而有些样本很重要Q决不能分类错误Q比如中央下辄文g啥的Q笑Q,q一个很大的C?

当然实际使用的时候ƈ没有q么极端Q但一U很常用的变形可以用来解军_c问题中h?#8220;偏斜”问题?

先来说说h的偏斜问题,也叫数据集偏斜(unbalancedQ,它指的是参与分类的两个类别(也可以指多个cdQ样本数量差异很大。比如说正类?0Q?00个样本,而负cdl了100个,q会引v的问题显而易见,可以看看下面的图Q?/p>image

方Ş的点是负cRHQH1QH2是根据给的样本算出来的分c面Q由于负cȝh很少很少Q所以有一些本来是负类的样本点没有提供Q比如图中两个灰色的方Ş点,如果q两个点有提供的话,那算出来的分c面应该是H’QH2’和H1Q他们显然和之前的结果有出入Q实际上负类l的h点越多,pҎ出现在灰色点附近的点Q我们算出的l果也就接q于真实的分c面。但现在׃偏斜的现象存在,使得数量多的正类可以把分c面向负cȝ方向“?#8221;Q因而媄响了l果的准性?

对付数据集偏斜问题的Ҏ之一是在惩|因子上作文章,惛_大家也猜CQ那是l样本数量少的负cL大的惩罚因子Q表C我们重视这部分hQ本来数量就,再抛弃一些,那h家负c还zMzMQ,因此我们的目标函C因松弛变量而损q部分变成了Q?

 

clip_image002[5]

其中i=1…p都是正样本,j=p+1…p+q都是负样本。libSVMq个法包在解决偏斜问题的时候用的就是这U方法?

那C+和C-怎么定呢?它们的大是试出来的Q参数调优)Q但是他们的比例可以有些Ҏ来确定。咱们先假定说C+?q么大,那确定C-的一个很直观的方法就是用两cL本数的比来算Q对应到刚才丄例子QC-可以定?00q么大(因ؓ10Q?00Q?00=100Q?嘛)?

但是q样q不够好Q回看刚才的图,你会发现正类之所以可?#8220;”负类Q其实ƈ不是因ؓ负类h,真实的原因是负类的样本分布的不够q(没扩充到负类本应该有的区域)。说一个具体点的例子,现在想给政治cd体育cȝ文章做分c,政治cL章很多,而体育类只提供了几篇关于球的文章,q时分类会明昑ց向于政治c,如果要给体育cL章增加样本,但增加的h仍然全都是关于篮球的Q也是_没有球Q排球,赛RQ游泳等{)Q那l果会怎样呢?虽然体育cL章在数量上可以达C政治cM样多Q但q于集中了,l果仍会偏向于政ȝQ所以给C+和C-定比例更好的方法应该是衡量他们分布的程度。比如可以算他们在I间中占据了多大的体U,例如l负cL一个超球——就是高l空间里的球啦——它可以包含所有负cȝhQ再l正cL一个,比比两个球的半径Q就可以大致定分布的情c显然半径大的分布就比较q,q一点的惩罚因子?

但是q样q不够好Q因为有的类别样本确实很集中Q这不是提供的样本数量多的问题Q这是类别本w的特征Q就是某些话题涉及的面很H,例如计算机类的文章就明显不如文化cȝ文章那么“天马行空”Q,q个时候即便超球的半径差异很大Q也不应该赋予两个类别不同的惩罚因子?

看到q里读者一定疯了,因ؓ说来说去Q这岂不成了一个解决不了的问题Q然而事实如此,完全的方法是没有的,Ҏ需要,选择实现单又合用的就好(例如libSVMq接用样本数量的比)?

Jasper 2009-03-17 20:04 发表评论
]]>
SVM入门Q八Q松弛变?/title><link>http://www.ymeg.top/zhenandaci/archive/2009/03/15/259786.html</link><dc:creator>Jasper</dc:creator><author>Jasper</author><pubDate>Sat, 14 Mar 2009 16:57:00 GMT</pubDate><guid>http://www.ymeg.top/zhenandaci/archive/2009/03/15/259786.html</guid><wfw:comment>http://www.ymeg.top/zhenandaci/comments/259786.html</wfw:comment><comments>http://www.ymeg.top/zhenandaci/archive/2009/03/15/259786.html#Feedback</comments><slash:comments>52</slash:comments><wfw:commentRss>http://www.ymeg.top/zhenandaci/comments/commentRss/259786.html</wfw:commentRss><trackback:ping>http://www.ymeg.top/zhenandaci/services/trackbacks/259786.html</trackback:ping><description><![CDATA[<p>现在我们已经把一个本来线性不可分的文本分c问题,通过映射到高l空间而变成了U性可分的。就像下图这P </p> <p> </p> <p><a href="http://www.ymeg.top/images/blogjava_net/zhenandaci/WindowsLiveWriter/SVM_D32/image_2.png"><img style="border: 0px none ; display: inline;" title="image" alt="image" src="http://www.ymeg.top/images/blogjava_net/zhenandaci/WindowsLiveWriter/SVM_D32/image_thumb.png" width="485" border="0" height="308" /></a> </p> <p>圆Ş和方形的点各有成千上万个Q毕竟,q就是我们训l集中文档的数量嘛,当然很大了)。现在想象我们有另一个训l集Q只比原先这个训l集多了一文章,映射到高l空间以后(当然Q也使用了相同的核函敎ͼQ也多了一个样本点Q但是这个样本的位置是这LQ?/p> <a href="http://www.ymeg.top/images/blogjava_net/zhenandaci/WindowsLiveWriter/SVM_D32/image_4.png"><img style="border: 0px none ; display: inline;" title="image" alt="image" src="http://www.ymeg.top/images/blogjava_net/zhenandaci/WindowsLiveWriter/SVM_D32/image_thumb_1.png" width="485" border="0" height="308" /></a> <p> </p> <p>是图中黄色那个点,它是方Ş的,因而它是负cȝ一个样本,q单独的一个样本,使得原本U性可分的问题变成了线性不可分的。这L似的问题Q仅有少数点U性不可分Q叫?#8220;q似U性可?#8221;的问题?</p> <p>以我们hcȝ常识来判断,说有一万个炚wW合某种规律Q因而线性可分)Q有一个点不符合,那这一个点是否׃表了分类规则中我们没有考虑到的斚w呢(因而规则应该ؓ它而做Z改)Q?</p> <p>其实我们会觉得,更有可能的是Q这个样本点压根是错误Q是噪声Q是提供训练集的同学人工分类时一打瞌睡错放进ȝ。所以我们会单的忽略q个h点,仍然使用原来的分cdQ其效果丝毫不受影响?</p> <p>但这U对噪声的容错性是人的思维带来的,我们的程序可没有。由于我们原本的优化问题的表辑ּ中,实要考虑所有的h点(不能忽略某一个,因ؓE序它怎么知道该忽略哪一个呢Q)Q在此基上寻找正负类之间的最大几何间隔,而几何间隔本w代表的是距,是非负的Q像上面q种有噪声的情况会得整个问题无解。这U解法其实也叫做“间?#8221;分类法,因ؓ他硬性的要求所有样本点都满_分类q面间的距离必须大于某个倹{?</p> <p>因此׃面的例子中也可以看出Q硬间隔的分cL其结果容易受数点的控制Q这是很危险的(管有句话说真理L掌握在少Ch手中Q但那不q是那一撮以自慰的词句|了Q咱q是得民主)?</p> <p>但解x法也很明显,是仿照人的思\Q允怸些点到分cd^面的距离不满_先的要求。由于不同的训练集各点的间距度不太一P因此用间隔(而不是几何间隔)来衡量有利于我们表达形式的简z。我们原先对h点的要求是: </p> <p> </p> <p><a href="http://www.ymeg.top/images/blogjava_net/zhenandaci/WindowsLiveWriter/SVM_D32/clip_image002_2.gif"><img style="border: 0px none ; display: inline;" title="clip_image002" alt="clip_image002" src="http://www.ymeg.top/images/blogjava_net/zhenandaci/WindowsLiveWriter/SVM_D32/clip_image002_thumb.gif" width="394" border="0" height="34" hspace="12" /></a></p> <p>意思是说离分类面最q的h点函数间隔也要比1大。如果要引入定w性,q1q个性的阈值加一个松弛变量,卛_?/p> <p><a href="http://www.ymeg.top/images/blogjava_net/zhenandaci/WindowsLiveWriter/SVM_D32/clip_image002%5B5%5D.gif"><img style="border: 0px none ; display: inline;" title="clip_image002[5]" alt="clip_image002[5]" src="http://www.ymeg.top/images/blogjava_net/zhenandaci/WindowsLiveWriter/SVM_D32/clip_image002%5B5%5D_thumb.gif" width="448" border="0" height="70" hspace="12" /></a></p> <p>因ؓ村ּ变量是非负的Q因此最l的l果是要求间隔可以比1。但是当某些点出现这U间隔比1的情况Ӟq些点也叫离点Q,意味着我们攑ּ了对q些点的_分类Q而这Ҏ们的分类器来说是U损失。但是放弃这些点也带来了好处Q那是使分c面不必向这些点的方向移动,因而可以得到更大的几何间隔Q在低维I间看来Q分c边界也更^滑)。显然我们必L衡这U损失和好处。好处很明显Q我们得到的分类间隔大Q好处就多。回我们原始的间隔分cd应的优化问题Q?/p> <p><a href="http://www.ymeg.top/images/blogjava_net/zhenandaci/WindowsLiveWriter/SVM_D32/clip_image002%5B7%5D.gif"><img style="border: 0px none ; display: inline;" title="clip_image002[7]" alt="clip_image002[7]" src="http://www.ymeg.top/images/blogjava_net/zhenandaci/WindowsLiveWriter/SVM_D32/clip_image002%5B7%5D_thumb.gif" width="454" border="0" height="82" hspace="12" /></a></p> <p>||w||<sup>2</sup>是我们的目标函敎ͼ当然pL可有可无Q,希望它越越好,因而损失就必然是一个能使之变大的量Q能使它变小׃叫损׃Q我们本来就希望目标函数D越好)。那如何来衡量损失,有两U常用的方式Q有人喜Ƣ用</p> <p><a href="http://www.ymeg.top/images/blogjava_net/zhenandaci/WindowsLiveWriter/SVM_D32/clip_image002%5B9%5D.gif"><img style="border: 0px none ; display: inline;" title="clip_image002[9]" alt="clip_image002[9]" src="http://www.ymeg.top/images/blogjava_net/zhenandaci/WindowsLiveWriter/SVM_D32/clip_image002%5B9%5D_thumb.gif" width="75" border="0" height="70" hspace="12" /></a></p> <p>而有人喜Ƣ用</p> <p><a href="http://www.ymeg.top/images/blogjava_net/zhenandaci/WindowsLiveWriter/SVM_D32/clip_image002%5B11%5D.gif"><img style="border: 0px none ; display: inline;" title="clip_image002[11]" alt="clip_image002[11]" src="http://www.ymeg.top/images/blogjava_net/zhenandaci/WindowsLiveWriter/SVM_D32/clip_image002%5B11%5D_thumb.gif" width="71" border="0" height="68" hspace="12" /></a></p> <p>其中l都是h的数目。两U方法没有大的区别。如果选择了第一U,得到的方法的叫做二阶Y间隔分类器,W二U就叫做一阶Y间隔分类器。把损失加入到目标函数里的时候,需要一?span style="color: #5f48ff;">惩罚因子</span>QcostQ也是libSVM的诸多参C的CQ,原来的优化问题就变成了下面这P</p> <p><a href="http://www.ymeg.top/images/blogjava_net/zhenandaci/WindowsLiveWriter/SVM_D32/clip_image002%5B13%5D.gif"><img style="border: 0px none ; display: inline;" title="clip_image002[13]" alt="clip_image002[13]" src="http://www.ymeg.top/images/blogjava_net/zhenandaci/WindowsLiveWriter/SVM_D32/clip_image002%5B13%5D_thumb.gif" width="523" border="0" height="116" hspace="12" /></a></p> <p>q个式子有这么几点要注意Q?</p> <p>一是ƈ非所有的h炚w有一个松弛变量与其对应。实际上只有“ȝ?#8221;才有Q或者也可以q么看,所有没ȝ的点村ּ变量都等?Q对负类来说Q离点是在前面图中,跑到H2右侧的那些负h点,ҎcL_是跑到H1左侧的那些正h点)?</p> <p>二是村ּ变量的值实际上标示Z对应的点到底ȝ有多q,D大,点就远?</p> <p>三是惩罚因子C军_了你有多重视ȝ点带来的损失Q显然当所有离点的松弛变量的和一定时Q你定的C大Q对目标函数的损׃大Q此时就暗示着你非怸愿意攑ּq些ȝ点,最极端的情冉|你把C定ؓ无限大,q样只要E有一个点ȝQ目标函数的值马上变成无限大Q马上让问题变成无解Q这退化成了硬间隔问题?</p> <p>四是惩罚因子C<span style="color: #ff0000;">?/span>是一个变量,整个优化问题在解的时候,C是一个你必须事先指定的|指定q个g后,解一下,得到一个分cdQ然后用试数据看看l果怎么P如果不够好,换一个C的|再解一ơ优化问题,得到另一个分cdQ再看看效果Q如此就是一个参数寻优的q程Q但q和优化问题本n决不是一回事Q优化问题在解的q程中,C一直是定|要记住?</p> <p>五是管加了村ּ变量q么一_但这个优化问题仍然是一个优化问题(汗,q不废话么)Q解它的q程比v原始的硬间隔问题来说Q没有Q何更加特D的地方?</p> <p>从大的方面说优化问题解的q程Q就是先试着定一下wQ也是定了前面图中的三条直线Q这时看看间隔有多大Q又有多点ȝQ把目标函数的值算一,再换一l三条直U(你可以看刎ͼ分类的直U位|如果移动了Q有些原来离的点会变得不再ȝQ而有的本来不ȝ的点会变成离点Q,再把目标函数的值算一,如此往复(q代Q,直到最l找到目标函数最时的w?</p> <p>啰嗦了这么多Q读者一定可以马上自己ȝ出来Q松弛变量也是个解决线性不可分问题的方法Ş了,但是回想一下,核函数的引入不也是ؓ了解决线性不可分的问题么Qؓ什么要Z一个问题用两U方法呢Q?</p> <p>其实两者还有微妙的不同。一般的q程应该是这Pq以文本分类Z。在原始的低l空间中Q样本相当的不可分,无论你怎么扑ֈcd^面,M有大量的ȝ点,此时用核函数向高l空间映一下,虽然l果仍然是不可分的,但比原始I间里的要更加接q线性可分的状态(是辑ֈ了近似线性可分的状态)Q此时再用松弛变量处理那些少?#8220;冥顽不化”的离点Q就单有效得多啦?</p> <p>本节中的Q式1Q也实是支持向量机最最常用的Ş式。至此一个比较完整的支持向量机框架就有了Q简单说来,支持向量机就是用了核函数的软间隔线性分cL?</p> <p>下一节会说说村ּ变量剩下的一点点东西Q顺便搞个读者调查,看看大家q想侃侃SVM的哪些方面? </p> <img src ="http://www.ymeg.top/zhenandaci/aggbug/259786.html" width = "1" height = "1" /><br><br><div align=right><a style="text-decoration:none;" href="http://www.ymeg.top/zhenandaci/" target="_blank">Jasper</a> 2009-03-15 00:57 <a href="http://www.ymeg.top/zhenandaci/archive/2009/03/15/259786.html#Feedback" target="_blank" style="text-decoration:none;">发表评论</a></div>]]></description></item><item><title>SVM入门Q七Qؓ何需要核函数http://www.ymeg.top/zhenandaci/archive/2009/03/06/258288.htmlJasperJasperFri, 06 Mar 2009 10:36:00 GMThttp://www.ymeg.top/zhenandaci/archive/2009/03/06/258288.htmlhttp://www.ymeg.top/zhenandaci/comments/258288.htmlhttp://www.ymeg.top/zhenandaci/archive/2009/03/06/258288.html#Feedback54http://www.ymeg.top/zhenandaci/comments/commentRss/258288.htmlhttp://www.ymeg.top/zhenandaci/services/trackbacks/258288.html生存Q还是毁灭?——哈姆雷?

可分Q还是不可分Q——支持向量机

之前一直在讨论的线性分cd,器如其名Q汗Q这是什么说法啊Q,只能对线性可分的h做处理。如果提供的hU性不可分Q结果很单,U性分cd的求解程序会无限循环Q永q也解不出来。这必然使得它的适用范围大大~小Q而它的很多优Ҏ们实在不原意攑ּQ怎么办呢Q是否有某种ҎQ让U性不可分的数据变得线性可分呢Q?

有!其思想说来也简单,来用一个二l^面中的分c问题作例子Q你一看就会明白。事先声明,下面q个例子是网l早有的,我一时找不到原作者的正确信息Q在此借用Qƈ加进了我自己的解说而已?

例子是下面这张图Q?

clip_image001

我们把横轴上端点a和b之间U色部分里的所有点定ؓ正类Q两边的黑色部分里的点定cR试问能扑ֈ一个线性函数把两类正确分开么?不能Q因Zl空间里的线性函数就是指直线Q显然找不到W合条g的直Uѝ?

但我们可以找C条曲U,例如下面q一条:

clip_image002

昄通过点在q条曲线的上方还是下方就可以判断Ҏ属的cdQ你在横轴上随便找一点,算q一点的函数|会发现负cȝ点函数g定比0大,而正cȝ一定比0)。这条曲U就是我们熟知的二次曲线Q它的函数表辑ּ可以写ؓQ?

clip_image002[5]

问题只是它不是一个线性函敎ͼ但是Q下面要注意看了Q新Z个向量y和aQ?

clip_image002[7]

q样g(x)可以{化ؓf(y)=<a,y>Q你可以把y和a分别回带一下,看看{不{于原来的g(x)。用内积的Ş式写你可能看不太清楚Q实际上f(y)的Ş式就是:

g(x)=f(y)=ay

在Q意维度的I间中,q种形式的函数都是一个线性函敎ͼ只不q其中的a和y都是多维向量|了Q,因ؓ自变量y的次C大于1?

看出妙在哪了么?原来在二l空间中一个线性不可分的问题,映射到四l空间后Q变成了U性可分的Q因此这也Ş成了我们最初想解决U性不可分问题的基本思\——向高维I间转化Q其变得线性可分?

而{化最关键的部分就在于扑ֈx到y的映方法。遗憄是,如何扑ֈq个映射Q没有系l性的ҎQ也是_U靠猜和凑)。具体到我们的文本分c问题,文本被表CZؓ上千l的向量Q即使维数已l如此之高,也常常是U性不可分的,q要向更高的I间转化。其中的隑ֺ可想而知?/p>

Tips:Z么说f(y)=ay是四l空间里的函?
大家可能一时没看明白。回想一下我们二l空间里的函数定?/span>
  g(x)=ax+b
变量x是一l的Qؓ什么说它是二维I间里的函数呢?因ؓq有一个变量我们没写出来,它的完整形式其实?/span>
  y=g(x)=ax+b
?br />   y=ax+b

看看Q有几个变量Q两个。那是几l空间的函数Q(作者五岁的弟弟{:五维的。作者:……Q?/span>
再看?br /> f(y)=ay
里面的y是三l的变量Q那f(y)是几l空间里的函敎ͼQ作者五岁的弟弟{:q是五维的。作者:……Q?br />

用一个具体文本分cȝ例子来看看这U向高维I间映射从而分cȝҎ如何q作Q想象一下,我们文本分类问题的原始空间是1000l的Q即每个要被分类的文档被表示Z?000l的向量Q,在这个维度上问题是线性不可分的。现在我们有一?000l空间里的线性函?

f(x)=<w,x>+b

注意向量的右上角有个 ’哦。它能够原问题变得可分。式中的 w和x都是2000l的向量Q只不过w是定|而x是变量(好吧,严格说来q个函数?001l的,哈哈Q,现在我们的输入呢Q是一?000l的向量xQ分cȝq程是先把x变换?000l的向量xQ然后求q个变换后的向量x与向量w的内U,再把q个内积的值和b相加Q就得到了结果,看结果大于阈D是小于阈值就得到了分cȝ果?

你发C什么?我们其实只关心那个高l空间里内积的|那个值算出来了,分类l果q出来了。而从理论上说Q?x是经由x变换来的Q因此广义上可以把它叫做x的函敎ͼ有一个xQ就定了一个xQ对吧,定不出W二个)Q而w是常量,它是一个低l空间里的常量wl过变换得到的,所以给了一个w 和x的|有一个确定的f(x)g其对应。这让我们惻I是否能有q样一U函数K(w,x),他接受低l空间的输入|却能出高维I间的内U?lt;w,x>Q?

如果有这L函数Q那么当l了一个低l空间的输入x以后Q?

g(x)=K(w,x)+b

f(x)=<w,x>+b

q两个函数的计算l果完全一P我们也就用不着费力N个映关p,直接拿低l的输入往g(x)里面代就可以了(再次提醒Q这回的g(x)׃是线性函数啦Q因Z不能保证K(w,x)q个表达式里的xơ数不高?哦)?

万幸的是Q这LK(w,x)实存在Q发现凡是我们hc能解决的问题,大都是y得不能再巧,Ҏ得不能再Ҏ的问题,L恰好有些能投机取巧的地方才能解决Q由此感Chcȝ渺小Q,它被UC核函?/span>Q核QkernelQ,而且q不止一个,事实上,只要是满了Mercer条g的函敎ͼ都可以作为核函数。核函数的基本作用就是接受两个低l空间里的向量,能够计算出经q某个变换后在高l空间里的向量内U倹{几个比较常用的核函敎ͼ俄,教课书里都列q,我就不敲了(懒!Q?

回想我们上节说的求一个线性分cdQ它的Ş式应该是Q?

clip_image002[9]

现在q个是高维I间里的U性函敎ͼZ区别低维和高l空间里的函数和向量Q我改了函数的名字,q且lw和x都加上了 ’Q,我们可以用一个低l空间里的函敎ͼ再一ơ的Q这个低l空间里的函数就不再是线性的啦)来代替,

clip_image002[11]

又发C么了Qf(x’) 和g(x)里的αQyQb全都是一样一LQ这是_管l的问题是线性不可分的,但是我们q当它是线性问题来求解Q只不过求解q程中,凡是要求内积的时候就用你选定的核函数来算。这h出来?#945;再和你选定的核函数一l合Q就得到分类器啦Q?

明白了以上这些,会自然的问接下来两个问题Q?

1Q?既然有很多的核函敎ͼ针对具体问题该怎么选择Q?

2Q?如果使用核函数向高维I间映射后,问题仍然是线性不可分的,那怎么办?

W一个问题现在就可以回答你:Ҏ函数的选择Q现在还~Z指导原则Q各U实验的观察l果Q不光是文本分类Q的表明,某些问题用某些核函数效果很好Q用另一些就很差Q但是一般来Ԍ径向基核函数是不会出太大偏差的一U,首选。(我做文本分类pȝ的时候,使用径向基核函数Q没有参数调优的情况下,l大部分cd的准和召回都在85%以上Q可见。虽然libSVM的作者林Z认ؓ文本分类用线性核函数效果更佳Q待考证Q?

对第二个问题的解军_引出了我们下一节的主题Q松弛变量?



Jasper 2009-03-06 18:36 发表评论
]]>
SVM入门Q六Q线性分cd的求?amp;mdash;&mdash;问题的{化,直观角度http://www.ymeg.top/zhenandaci/archive/2009/03/01/257237.htmlJasperJasperSun, 01 Mar 2009 12:48:00 GMThttp://www.ymeg.top/zhenandaci/archive/2009/03/01/257237.htmlhttp://www.ymeg.top/zhenandaci/comments/257237.htmlhttp://www.ymeg.top/zhenandaci/archive/2009/03/01/257237.html#Feedback24http://www.ymeg.top/zhenandaci/comments/commentRss/257237.htmlhttp://www.ymeg.top/zhenandaci/services/trackbacks/257237.html让我再一ơ比较完整的重复一下我们要解决的问题:我们有属于两个类别的h点(q不限定q些点在二维I间中)若干Q如图,

image

圆Ş的样本点定ؓ正样本(q带着Q我们可以把正样本所属的cd做正c)Q方形的点定例。我们想求得q样一个线性函敎ͼ在nl空间中的线性函敎ͼQ?

g(x)=wx+b

使得所有属于正cȝ?a name="OLE_LINK1">x+代入以后有g(x+)≥1Q而所有属于负cȝ点x-代入后有g(x-)≤-1Q之所以总跟1比较Q无论正一q是负一Q都是因为我们固定了间隔?Q注意间隔和几何间隔的区别)。代入g(x)后的值如果在1?1之间Q我们就拒绝判断?

求这Lg(x)的过E就是求wQ一个nl向量)和bQ一个实敎ͼ两个参数的过E(但实际上只需要求wQ求得以后找某些h点代入就可以求得bQ。因此在求g(x)的时候,w才是变量?

你肯定能看出来,一旦求ZwQ也求ZbQ,那么中间的直UHq道了Q因为它是wx+b=0嘛,哈哈Q,那么H1和H2也就知道了(因ؓ三者是q的,而且盔R的距还是||w||军_的)。那么w是谁军_的?昄是你l的h军_的,一旦你在空间中l出了那些个h点,三条直线的位|实际上唯一定了(因ؓ我们求的是最优的那三条,当然是唯一的)Q我们解优化问题的过E也只不q是把这个确定了的东西算出来而已?

h定了wQ用数学的语a描述Q就是w可以表示为样本的某种l合Q?

w=α1x12x2+…+αnxn

式子中的αi是一个一个的敎ͼ在严格的证明q程中,q些α被称?span style="color: #3844ff;">拉格朗日乘子Q,而xi是样本点Q因而是向量Qn是L本点的个数。ؓ了方便描qͼ以下开始严格区别数字与向量的乘U和向量间的乘积Q我会用α1x1表示数字和向量的乘积Q而用<x1,x2>表示向量x1,x2的内U(也叫点积Q注意与向量叉积的区别)。因此g(x)的表辑ּ严格的Ş式应该是Q?

g(x)=<w,x>+b

但是上面的式子还不够好,你回头看看图中正h和负h的位|,惛_一下,我不动所有点的位|,而只是把其中一个正h点定h点(也就是把一个点的Ş状从圆Ş变ؓ方ŞQ,l果怎么P三条直线都必ȝ动(因ؓ对这三条直线的要求是必须把方形和圆Ş的点正确分开Q!q说明w不仅跟样本点的位|有养Iq跟h的类别有养I也就是和h?#8220;标签”有关Q。因此用下面q个式子表示才算完整Q?

w=α1y1x12y2x2+…+αnynxn Q式1Q?

其中的yi是Wi个样本的标签Q它{于1或?1。其实以上式子的那一堆拉格朗日乘子中Q只有很的一部分不等?Q不{于0才对w起决定作用)Q这部分不等?的拉格朗日乘子后面所乘的h点,其实都落在H1和H2上,也正是这部分hQ而不需要全部样本)唯一的确定了分类函数Q当Ӟ更严格的_q些h的一部分可以确定,因ؓ例如定一条直U,只需要两个点可以,即便有三五个都落在上面,我们也不是全都需要。这部分我们真正需要的h点,叫?span style="color: #3844ff;">支持Q撑Q向?/span>Q(名字q挺形象吧,他们“?#8221;起了分界U)

式子也可以用求和W号写一下:

 

clip_image002

因此原来的g(x)表达式可以写为:

clip_image002[4]

注意式子中x才是变量Q也是你要分类哪篇文档Q就把该文档的向量表CZ入到 x的位|,而所有的xil统都是已知的样本。还注意到式子中只有xi和x是向量,因此一部分可以从内U符号中拿出来,得到g(x)的式子ؓQ?/p>

clip_image002[6]

发现了什么?w不见啦!从求w变成了求α?

但肯定有Z_qƈ没有把原问题化呀。嘿嘿,其实化了Q只不过在你看不见的地方Q以q样的Ş式描q问题以后,我们的优化问题少了很大一部分不等式约束(记得q是我们解不了极值问题的万恶之源Q。但是接下来先蟩q线性分cd求解的部分,来看?SVM在线性分cd上所做的重大改进—?span style="color: #3844ff;">核函?/span>?



Jasper 2009-03-01 20:48 发表评论
]]>
SVM入门Q五Q线性分cd的求?amp;mdash;&mdash;问题的描qPart2http://www.ymeg.top/zhenandaci/archive/2009/02/14/254630.htmlJasperJasperFri, 13 Feb 2009 17:34:00 GMThttp://www.ymeg.top/zhenandaci/archive/2009/02/14/254630.htmlhttp://www.ymeg.top/zhenandaci/comments/254630.htmlhttp://www.ymeg.top/zhenandaci/archive/2009/02/14/254630.html#Feedback15http://www.ymeg.top/zhenandaci/comments/commentRss/254630.htmlhttp://www.ymeg.top/zhenandaci/services/trackbacks/254630.html从最一般的定义上说Q一个求最值的问题是一个优化问题(也叫M问题Q更文绉l的叫法?span style="color: #505bff;">规划——ProgrammingQ,它同L两部分组成,目标函数和约束条Ӟ可以用下面的式子表示Q?

clip_image002Q式1Q?

U束条g用函数c来表C,是constrain的意思啦。你可以看出一共有p+q个约束条Ӟ其中p个是不等式约?/span>Qq?span style="color: #505bff;">{式U束?

关于q个式子可以q样来理解:式中的x是自变量Q但不限定它的维数必Mؓ1Q视乎你解决的问题空间维敎ͼҎ们的文本分类来说Q那可是成千上万啊)。要求f(x)在哪一点上取得最|反倒不太关心这个最值到底是多少Q关键是哪一点)Q但不是在整个空间里找,而是在约束条件所划定的一个有限的I间里找Q这个有限的I间是优化理论里所说的可行?/span>。注意可行域中的每一个点都要求满x有p+q个条Ӟ而不是满_中一条或几条可以(切记Q要满每个U束Q,同时可行域边界上的点有一个额外好的特性,它们可以?span style="color: #ff0000;">不等式约?/span>取得{号Q而边界内的点不行?

关于可行域还有个概念不得不提Q那是凔RQ凸集是指有q么一个点的集合,其中d两个点连一条直U,q条U上的点仍然在这个集合内部,因此?#8220;?#8221;是很形象的(一个反例是Q二l^面上Q一个月牙Ş的区域就不是凔RQ你随便可以找C个点q反了刚才的规定Q?

回头再来看我们线性分cd问题的描qͼ可以看出更多的东ѝ?

clip_image002[5]Q式2Q?

在这个问题中Q自变量是wQ而目标函数是w的二ơ函敎ͼ所有的U束条g都是w的线性函敎ͼ哎,千万不要把xi当成变量Q它代表hQ是已知的)Q这U规划问题有个很有名气的U呼—?span style="color: #505bff;">二次规划QQuadratic ProgrammingQQPQ,而且可以更进一步的_׃它的可行域是一个凸集,因此它是一?span style="color: #505bff;">怺ơ规?/span>?

一下子提了q么多术语,实在不是Z让大家以后能向别人炫耀学识的渊博,q其实是我们l箋下去的一个重要前提,因ؓ在动手求一个问题的解之前(好吧Q我承认Q是动计机?#8230;…Q,我们必须先问自己Q这个问题是不是有解Q如果有解,是否能找刎ͼ

对于一般意义上的规划问题,两个问题的答案都是不一定,但凸二次规划让h喜欢的地方就在于Q它有解Q教U书里面Z严}Q常常加限定成分Q说它有全局最优解Q由于我们想扄本来是全局最优的解,所以不加也|)Q而且可以扑ֈQ(当然Q依据你使用的算法不同,扑ֈq个解的速度Q行话叫收敛速度Q会有所不同Q?

ҎQ式2Q和Q式1Q还可以发现Q我们的U性分cd问题只有不等式约束,因此形式上看g比一般意义上的规划问题要单,但解h却ƈ非如此?

因ؓ我们实际上ƈ不知道该怎么解一个带U束的优化问题。如果你仔细回忆一下高{数学的知识Q会记得我们可以L的解一个不带Q何约束的优化问题Q实际上是当年背得烂熟的函数求极值嘛Q求导再?点呗Q谁不会啊?W)Q我们甚臌会解一个只带等式约束的优化问题Q也是背得烂熟的Q求条g极|记得么,通过d拉格朗日乘子Q构造拉格朗日函敎ͼ来把q个问题转化为无U束的优化问题云云(如果你一时没想通,我提醒一下,构造出的拉格朗日函数就是{化之后的问题形式Q它昄没有带Q何条Ӟ?

读者问Q如果只带等式约束的问题可以转化为无U束的问题而得以求解,那么可不可以把带不等式约束的问题向只带等式约束的问题转化一下而得以求解呢Q?

聪明Q可以,实际上我们也正是q么做的。下一节就来说说如何做q个转化Q一旦{化完成,求解对Q何学q高{数学的人来_都是菜一啦?



Jasper 2009-02-14 01:34 发表评论
]]>
׼ƽФ
    <nobr id="rub96"><optgroup id="rub96"></optgroup></nobr>

    <bdo id="rub96"></bdo>

      1. <track id="rub96"><div id="rub96"></div></track>
        <nobr id="rub96"><optgroup id="rub96"></optgroup></nobr>

            <nobr id="rub96"><address id="rub96"><big id="rub96"></big></address></nobr>
          1. <menuitem id="rub96"><strong id="rub96"><menu id="rub96"></menu></strong></menuitem>
            <dl id="rub96"><source id="rub96"><tr id="rub96"></tr></source></dl>
            1. <tbody id="rub96"><div id="rub96"></div></tbody>
              1. <bdo id="rub96"><optgroup id="rub96"></optgroup></bdo>
              2. <bdo id="rub96"><dfn id="rub96"><dd id="rub96"></dd></dfn></bdo>
                1. <option id="rub96"><source id="rub96"></source></option>
                2. <bdo id="rub96"></bdo>

                    <p id="rub96"><tr id="rub96"></tr></p>
                  1. <tbody id="rub96"></tbody>

                    <bdo id="rub96"></bdo>

                  2. <option id="rub96"><source id="rub96"></source></option>

                    <bdo id="rub96"><optgroup id="rub96"><dd id="rub96"></dd></optgroup></bdo>
                      <track id="rub96"></track>

                        <bdo id="rub96"></bdo>
                      1. <option id="rub96"><p id="rub96"><tr id="rub96"></tr></p></option>

                          <bdo id="rub96"></bdo>
                          1. <track id="rub96"></track>
                            1. <track id="rub96"></track>
                                  <bdo id="rub96"></bdo>
                                  <option id="rub96"></option>

                                      1. <track id="rub96"><span id="rub96"></span></track>

                                          <option id="rub96"></option>

                                          1. 
                                            
                                              <option id="rub96"><span id="rub96"></span></option>
                                              <bdo id="rub96"><address id="rub96"></address></bdo>
                                              <option id="rub96"><source id="rub96"></source></option>
                                                <nobr id="rub96"><address id="rub96"></address></nobr>
                                              1. <nobr id="rub96"><optgroup id="rub96"><big id="rub96"></big></optgroup></nobr>
                                                <track id="rub96"></track>

                                                <nobr id="rub96"><optgroup id="rub96"></optgroup></nobr>
                                                  <nobr id="rub96"><optgroup id="rub96"></optgroup></nobr>

                                                  <bdo id="rub96"></bdo>

                                                    1. <track id="rub96"><div id="rub96"></div></track>
                                                      <nobr id="rub96"><optgroup id="rub96"></optgroup></nobr>

                                                          <nobr id="rub96"><address id="rub96"><big id="rub96"></big></address></nobr>
                                                        1. <menuitem id="rub96"><strong id="rub96"><menu id="rub96"></menu></strong></menuitem>
                                                          <dl id="rub96"><source id="rub96"><tr id="rub96"></tr></source></dl>
                                                          1. <tbody id="rub96"><div id="rub96"></div></tbody>
                                                            1. <bdo id="rub96"><optgroup id="rub96"></optgroup></bdo>
                                                            2. <bdo id="rub96"><dfn id="rub96"><dd id="rub96"></dd></dfn></bdo>
                                                              1. <option id="rub96"><source id="rub96"></source></option>
                                                              2. <bdo id="rub96"></bdo>

                                                                  <p id="rub96"><tr id="rub96"></tr></p>
                                                                1. <tbody id="rub96"></tbody>

                                                                  <bdo id="rub96"></bdo>

                                                                2. <option id="rub96"><source id="rub96"></source></option>

                                                                  <bdo id="rub96"><optgroup id="rub96"><dd id="rub96"></dd></optgroup></bdo>
                                                                    <track id="rub96"></track>

                                                                      <bdo id="rub96"></bdo>
                                                                    1. <option id="rub96"><p id="rub96"><tr id="rub96"></tr></p></option>

                                                                        <bdo id="rub96"></bdo>
                                                                        1. <track id="rub96"></track>
                                                                          1. <track id="rub96"></track>
                                                                                <bdo id="rub96"></bdo>
                                                                                <option id="rub96"></option>

                                                                                    1. <track id="rub96"><span id="rub96"></span></track>

                                                                                        <option id="rub96"></option>

                                                                                        1. 
                                                                                          
                                                                                            <option id="rub96"><span id="rub96"></span></option>
                                                                                            <bdo id="rub96"><address id="rub96"></address></bdo>
                                                                                            <option id="rub96"><source id="rub96"></source></option>
                                                                                              <nobr id="rub96"><address id="rub96"></address></nobr>
                                                                                            1. <nobr id="rub96"><optgroup id="rub96"><big id="rub96"></big></optgroup></nobr>
                                                                                              <track id="rub96"></track>

                                                                                              <nobr id="rub96"><optgroup id="rub96"></optgroup></nobr>
                                                                                              1. ÷777 ˷ͧ72ѩ߼ƻ ƶְ׿1.8.0 б Ʊ1966APP ʮֲʿ ǺϷ pkʰֱ ʱʱƵֱ pkʰѼƻ 캽pk10ƻ׼ ʱʱǶ벻λ