svm

支持向量机（Support Vector Machines）简称SVM,是AT&T Bell实验室的V. Vapnik等人根据统计学习理论提出的一种新的机器学习方法,它已初步表现出很多优于已有方法的分类性能，在解决小样本学习、非线性以及高维模式识别等问题中表现出许多特有的优势。
其基本思想可概括为:首先通过非线性变换将输入空间变换到一个高维空间,然后在这个新空间中求取最优线性分类面,而这种非线性变换是通过定义适当的内积函数实现的。根据结构风险最小化准则,在使训练样本分类误差极小化的前提下,尽量提高分类器的泛化推广能力。
从实施的角度看,训练支持向量机等价于解一个线性约束的二次规划问题,使得分隔特征空间中两类模式点的两个超平面之间距离最大,而且它能保证得到的解为全局最优点,使得基于支持向量机的手写汉字分类器能够吸收手写的变形,从而具有较好的泛化和推广能力。

some pictures

1. 语言模型(Language Model, LM)的目的是建立一个能够描述给定词序列在语言中的出现的概率的分布。
   语言模型最开始诞生在语音识别领域，识别给定的语音信号对应的词序列。语言模型的基本原理是
   hi表示历史信息。随着hi取值的不同，衍生出几个模型 [1] ：
   l 一元模型(Unigram)：
   l 二元模型(Bigram)：
   l 三元模型(Trigram)：
   在实际中应用模型的时候，有一个取舍问题：
   History
   short
   long
   modeling
   coarse
   refined
   Estimation
   easy
   difficult
   根据资源规模和模型细致程度选择。
   参数估计
   模型的参数估计一般采用极大似然估计(Maximum Likilihood Estimation, MLE)：
   不过MLE有一个问题，那就是对出现的项估计很好，对于没有出现的项，则认为是概率为0的实践。如果直接采用MLE估计参数，效果可能会很不好。平滑(smoothing)技术是为了解决类是MLE的问题而提出的。Smoothing技术思想就是调整一下概率的分布，给语料中没有出现的项(认为是“事件”)一个小但不为零概率，降低语料中出现次数比较多的项的概率。
   平滑技术
   平滑常用的方法有多种。
   调整出现概率的平滑方法：
   n Laplace smoothing( add-onesmoothing )
   n Good-Turing smoothing
   以低阶模型相结合的方法
   n Backoff (Katz)
   n Interpolation (Jelinek-Mercer)
   l 其他方法
   n Combined with corpus
   n Dirichlet
   n Two-stage
   
2. 语言模型在信息检索中的应用
   目前在IR(InformationRetrieval)中应用LM(LanguageModel)，基本原理有4个：
   l 原理 1
   Document D
   Language model P(wMD)
   Query Q
   sequence of words q1, q2,…, qn (uni-grams)
   Matching
   P(QMD)
   l 原理2
   Document D
   Language model P(wMQ)
   Query Q
   sequence of words d1, d2,…, dn
   Matching
   P(DMQ)
   l 原理3
   Document D
   Language model P(wMD)
   Query Q
   Language model P(wMQ)
   Matching
   comparison between P(wMD) and P(wMQ)
   l 原理4(翻译模型)
   Translate D to Q
   原理1是[Ponte&Croft 1998]提出的，为经典的LM模型在IR中的应用。平滑中可能出现的问题：
   l 文章太短(Short document)
   l MD模型粗糙(Coarse MD)
   l 没有出现的词(Unseen words)
   [Ponte&Croft 1998]提出的平滑方案：
   原理2应用不多，因为Query的包含信息太少，建立LM效果不好。
   原理4将信息检索过程看成一个翻译过程，建立噪声信道模型，由“信息”到“接受”。
   P(qiwj)是翻译模型的关键，表示两个词对应的翻译概率。估计参数的时候需要对齐的双语语料[Berger&Lafferty ]。
   
3. 语言模型小结
   l Can a query be generated from adocument model?
   l Does a document become morelikely when a query is submitted (or reverse)?
   l Is a query a"translation" of a document?
   l Smoothing is crucial
   l Often use uni-grams
   
4. 语言模型对信息检索的贡献
   l 有良好的理论框架(Well founded theoretical framework)
   l 有大量的可用数据(Exploit the mass of data available)
   l 概率估计的参数平滑技术(Techniques of smoothing for probability estimation)
   l 能够通过平滑解释一些经验和启发式方法(Explain some empirical and heuristic methods by smoothing)
   l 令人兴奋的试验结果(Interesting experimental results)
   l 使用LM的IR工具的诞生(Existing tools for IR using LM(Lemur))

Collaborative Filtering

标签：协同过滤 推荐系统 it
这方面挺有意思，就随便看了看。总结下看的东西~~~
协同过滤的主要目标：由于网络信息量的增多，用户往往被淹没在信息的海洋里，很难很轻易的找到自己感兴趣的topic。协同过滤就是为了把用户最可能感兴趣的信息推送给用户（Recommer system）。
协同过滤的方法： model-base，user-base，item-base，content-base。

• user-based：搜集用户profile。对于一个active user，找到跟其比较接近（或者相似）的几个neighbour。使用这些neibour对active user的interest进行预测，把那些潜在的interest推荐给active user。
• item-base:与user-based相对应。协同过滤推荐根据用户对相似项的评分预测该用户对目标项的评分，它基于这样一个假设：如果大部分用户对一些项的评分比较相似，则当前用户对这些项的评分也比较相似。对每个item寻找几个neighbour。譬如如果item A 与item B是一个neighbour pair，对于一个active user，如果其对A评价很高，或者有很高的兴趣，那么他极可能对B感兴趣,这样B就是一个潜在的inerest.
• content-based:根据item的内容与用户历史兴趣度进行分析关联，它的一个前提假设就是如果一个用户在过去一段时间对某item有较高的评价，那么在未来也会保持这种interest。这样就可以根据item之间的内容接近程度进行推荐。它有很大的缺陷，首先没有结合用户反馈，虽然一个item具有很高的可推荐性，但是如果大家都对其评价较差，那么这也许是一个不好的推荐item；其次就是其对item内容进行分析也只能是一个方面，不能全面深刻的描述一个item；再一个就是推荐的内容有限；当系统仅仅根据用户资料或项目描述来进行推荐的时候，用户被限制在只能得到与以往熟悉的内容相类似的项目。这样不利于挖掘用户潜在的兴趣。

协同过滤面临的问题：

• 数据稀疏问题（一个用户不可能对所有的商品都有过评价),例如：许多电子商务推荐系统要对大量的数据信息进行处理，而在这些系统中一般用户购买商品的总量占网站总商品量的1%左右，因此造成了评价矩阵(用户-项矩阵)非常稀疏。
• 再一个就是冷开始问题：cold start。它主要表现在一个新项目或者一个新用户的到来上。因为传统的协同过滤推荐是基于邻居用户资料得到目标用户的推荐，在一个新的项目首次出现的时候，因为没有用户对它作过评价，因此单纯的协同过滤无法对其进行预测评分和推荐。而且，由于新项目出现早期，用户评价较少，推荐的准确性也比较差。相似的，推荐系统对于新用户的推荐效果也很差。冷开始问题的极端的情况是：当一个协同过滤推荐系统刚开始运行的时候，每个用户在每个项目上都面临冷开始问题。

刘铁岩

08-10-30 通过 微软亚洲研究院 作者：微软亚洲研究院 作者：刘铁岩

在研究院工作快5年了，没想到电子工程出身的我会和SIGIR注1，这一信息检索领
域的顶级会议，结下如此的不解之缘。

从2004年到2008年，自己在信息检索这个方向上走过的道路，也是自己在微软亚洲
研究院不断成长的过程：从熟悉信息检索这个领域，量身定做地投出第一篇
SIGIR论文，到提高研究能力和写作技巧，到确定自己的主攻方向，到为引领一个
研究学派而努力。

期间的收获和感悟颇多，写下来愿与大家分享。

第一年：“发表第一篇SIGIR论文”

我毕业于清华大学电子工程系，博士论文工作是关于视频信号处理的，如视频切
割、关键帧抽取、视频总结等。2003年加入微软亚洲研究院，2004年转入互联网搜
索与挖掘组，从此开始了对信息检索这一全新领域的探索。

这次转行没有想象的那么艰难，因为微软亚洲研究院在信息检索领域已经有了很多
的成果，在SIGIR上也发表了不少论文。有这么好的一个平台，可以通过和同事们
的交流很快进入状态。

但是过程并不轻松，毕竟信息检索领域几十年的历史沉淀了很多的知识和经验，需
要一点点去体会和掌握。为了更快更好地掌握这些知识，我和我的实习生们一
起，在组内开展了一系列的讲座，包括《现代信息检索》、《最优化方法》、《统
计机器学习》等等。经验证明，这种方法十分有效：自己看书学习是一种感觉，要
能够在众人面前把东西透彻地讲出来，是另外一种境界。虽然不得不花很多的功
夫，但是这个过程为我和我的实习生日后在信息检索领域的研究打下了坚实的理论
基础。

在提高基础知识的同时，我们也开始通过阅读论文，以及和同事的交流来了解
SIGIR这个会议。当时的愿望很朴素：能够尽快地像其他同事一样，在SIGIR这个顶
级学术会议上有论文发表。通过阅读论文，我逐渐发现SIGIR其实是个很传统，很
重视经验结果的会议。SIGIR的论文通常都有很翔实的实验结果，因为只有这样才
能验证所提出的算法在海量信息处理中是否有上佳的表现。作为进入这个领域的第
一个尝试，我决定“投其所好”，为SIGIR“量身定做”一篇有关经验比较的论文。

当时研究院正在参加TREC注2比赛。这个比赛中有一个任务叫做Topic
Distillation，其目的是找到与所查询主题最相关的子网站入口，也就是说即便有
的时候子页面比父页面更加相关，我们还是希望返回父页面。为了解决这个问
题，我们提出把网页里的关键词按照网站结构向父页面进行传播。经过实验验
证，这个方法非常有效。于是我就想，是不是还有其他类似的做法呢？除了关键词
以外，我们是否可以把网页的相关性得分（relevance score）进行传播？除了沿
着网站结构以外，我们是否还可以沿着超级链接结构进行传播？有了这个想法以
后，我们对以往的相关文献进行了调研，发现确实有人做过把相关性得分沿着超级
链接进行传播的尝试。这就启发我对以上提及的各种传播方式进行系统的对比研
究。于是我把所有相关的方法进行列举、分类，并对其进行了大量的实验比较，并
最终得到了很多有意思的结果。我按照自己总结的SIGIR的“范式文本”，把这些比
较结果写成了一篇论文，提交给了SIGIR 2005。最终这篇文章被录用了。虽然有些
幸运的成分，但是不管怎么样，通过“模仿”，我的SIGIR之旅正式启航了。

第二年：“掌握扩大战果的本领”

发表第一篇文章固然重要，但是如何排除幸运的因素，真正具有持续发表SIGIR论
文的实力更加重要。这方面，微软亚洲研究院的国际化平台给了我很大的帮助。每
年，研究院都会吸引大量国外的知名学者来进行访问交流，我正是借助这样的机会
认识了杨益銘教授。

杨益銘教授是美国卡耐基梅隆大学的教授，是文本分类领域的专家。我有幸在她访
问研究院期间和她合作了的一篇论文。当我把初稿写出来让她修改的时候，她来来
回回和我讨论了5遍“引言”怎么写。其实她完全可以直接帮我把这一章改好，所花
的力气要少很多。但是杨老师耐心地给我提意见，让我自己一点一点修改。这个过
程使我意识到有了好的技术，还要清晰准确地表达出来，恰到好处地突出自己的贡
献。这对我日后的论文写作以及给学生改论文都有很大的帮助。至今仍然十分羡慕
杨老师的境界：“写论文其实是一件很享受的事情，写起来象清泉流水一样，禁不
住要把那么好的研究成果和别人分享”。

和杨老师合作在SIGKDD Explorations注3上发表了一篇关于大规模文本分类的论文
之后，我又开始了独立准备下一年度SIGIR论文的阶段。不过，这次明显感觉与以
往不同了：不再是为了量身定做一篇论文而找题目做，而是围绕着自己正在做的研
究题目写论文。

这次我准备的两篇文章一篇讲的是基于随机补的网络图排序，另外一篇则是关于文
档检索的新算法。它们都不是有关经验比较的论文，也没有像第一年那样按照
SIGIR的“范式文本”来写，但是这两篇文章也都被SIGIR 2006录用了。

经过这个过程，我感觉自己真的入门了：至少知道什么样的工作是SIGIR这个领域
真正认可的工作，也知道如何写出具有自己风格的论文来。

第三年：“找到属于自己的关键词”

入行两年发表了3篇SIGIR论文，其实并不是一件容易的事情，因为这个会议竞争非
常激烈，每年全球范围内只收录几十篇文章，而且无疑来自美国的论文占了绝大多
数。也因此，我慢慢被一些外面的学者认可，也接触到了更多的同行朋友。

一次开会的时候，和几个同行聚在一次聊天，各自介绍自己的研究方向。到我表达
的时候，发现只能用“信息检索”这样的大词来形容，因为自己做过的3篇SIGIR论文
相关性并不大，很难找到更贴切的描述。一个朋友说：你要有自己的关键词，比如
美国伊利诺斯大学香槟分校的翟老师的关键词就是语言模型，卡内基梅隆的杨老师
的关键词就是文本分类，你的关键词是什么？

这个问题给了我很大的触动。仔细想想，确实知名学者多半都有他们自己的成名之
作，有很集中的研究方向。而我目前的状态似乎还是有点为了发论文而发论文，没
有真正地去规划属于自己的研究方向。如果继续这样下去，可能接下来的几年里我
还会发表更多的SIGIR论文，但是当再次被别人问及同样的问题时，我仍然无法避
免这种尴尬。所以，我决定要集中火力，做有影响力的，可以作为自己关键词的研
究方向。

我和我的经理就此进行了一次长谈。谈话中，一方面他向我强调了微软亚洲研究院
开放的研究氛围，对我表示了极大的支持；另一方面，和我分享了“less is
more”的道理，并和我一起分析和确定了主攻的研究方向。考虑到我的数学基础比
较扎实，对机器学习和优化理论比较熟悉，同时考虑到不论对信息检索领域还是对
微软公司的搜索引擎而言，排序(ranking)都是一个核心的问题，我们最终把研究
的重点放在了排序学习（learning to rank）上。

在此基础上，我对自己和实习生的研究方向做了较大的调整：大家的研究方向都围
绕着排序学习展开，比如：排序学习的损失函数研究，基于多平面的排序学习方
法，排序学习中的特征选择问题，基于排序学习的序列融合等等。我们也再接再厉
在SIGIR 2007上发表了3篇论文。这三篇论文由于都是关于排序学习的，被安排在
了同一个分会上宣讲。这个分会上总共只有4篇文章，因此我们的表现受到了很大
的关注。我也从此有了自己的关键词：排序学习。

会后，我被邀请成为SIGIR 2008资深程序委员会的成员，以及国际期刊《信息检
索》的编委，从一个信息检索领域的参与者转变成了组织者。

第四年：“为引领一个学派而努力”

微软公司有一种内部导师制度，鼓励资深员工作为年轻员工的导师，对他们的成长
进行帮助和指导。我非常幸运，通过经理的引荐，Rakesh Agrawal注4，这个数据
挖掘领域最成功的学者，在2007年底成为了我的导师。我还清晰地记得在我和
Rakesh的面谈中，他对研究的看法给了我很大的震撼。比如，“写文章不是为了当
下被会议收录，而是为了要推动这个学术方向的发展，要形成一定的学派，至少在
10年之内都产生深远的影响”；再比如，“人们总是忘记你的好论文，而铭记着你不
好的论文，声望要用10年去积累但是可以毁于一旦，因此要非常严肃对待自己的每
一篇论文，确保质量”。

和Rakesh的交流让我认识到有个关键词还远远不够，这个关键词需要代表着我自己
主导的学派。带着这种想法，我在经理的帮助下对研究课题进行了重新的审视，并
且对研究过程进行了更好的质量控制。我和我的合作者们现在正在为了引领“列表
级别的排序学习(listwise approach to learning to rank)”这一属于我们自己的
学派而努力着。

可喜的是，我们在这个方向上已经取得了阶段性的成绩。比如，我们在SIGIR
2008上又发表了3篇相关的论文，还在ICML注5上发表了2篇关于“列表级别的排序学
习”的理论文章，讨论了列别级别排序学习的统计一致性和泛化性能。除了发表论
文以外，我们还通过在SIGIR上组织Workshop，发布Benchmark数据集，在SIGIR和
WWW注6等顶级会议上做专题讲座的方式推广“列表级别的排序学习”。

我们的研究成果受到了越来越多的关注，然而我们知道，前方要走的路还很长。不
过，在微软亚洲研究院这个平台上，我们有信心可以越走越远，推动排序学习领域
的进步，也为整个SIGIR的发展做出自己的贡献。

作者介绍

刘铁岩，2003年获得清华大学博士学位，同年加入微软亚洲研究院，现任信息检索
与挖掘组主管研究员。他的研究兴趣包括排序学习的理论，算法和系统。他已在国
际期刊和会议上发表了近70篇学术论文，拥有近40项专利或申请。他被国际期刊
“视觉通信和图像表达”授予2004～2006年度最高引用论文奖，被SIGIR2008授予最
佳学生论文奖。他是数十个国际会议的程序委员会成员及国际期刊编委。他的研究
风格是结合信息检索的应用需求，提出全新的研究方向，并给出有效的解决方案和
严谨的理论分析。

注1，SIGIR: Special Interest Group on Information Retrieval, 国际信息检
索大会

注2，TREC: Text REtrieval Conference, 国际文本检索大会。

注3，SIGKDD Explorations: 是ACM数据挖掘特别兴趣组出版的刊物，专注于数据
挖掘方面的前沿问题，一年一般出版两个专题。

注4，Rakesh Agrawal, 在1994年提出了Apriori算法之后，使得关联规则挖掘技术
的可用性得到了很大的提高。美国工程院院士、号称数据挖掘领域的教父，目前是
微软硅谷研究院的技术院士。

注5，ICML: International Conference on Machine Learning, 国际机器学习大
会，该领域内的顶级国际会议之一。

注6，WWW: World Wide Web, 国际万维网大会。2008年的第17届万维网大会首次在
北京举行。

Matlab两种方法进行聚类分析

Matlab提供了两种方法进行聚类分析

一种是利用 clusterdata函数对样本数据进行一次聚类，其缺点为可供用户选择的面较窄，不能更改距离的计算方法；

另一种是分步聚类：（1）找到数据集合中变量两两之间的相似性和非相似性，用pdist函数计算变量之间的距离；（2）用 linkage函数定义变量之间的连接；（3）用 cophenetic函数评价聚类信息；（4）用cluster函数创建聚类。

1．Matlab中相关函数介绍

1.1 pdist函数

调用格式：Y=pdist(X,’metric’)

说明：用 ‘metric’指定的方法计算 X 数据矩阵中对象之间的距离。’

X：一个m×n的矩阵，它是由m个对象组成的数据集，每个对象的大小为n。

metric’取值如下：

‘euclidean’：欧氏距离（默认）；‘seuclidean’：标准化欧氏距离；

‘mahalanobis’：马氏距离；‘cityblock’：布洛克距离；

‘minkowski’：明可夫斯基距离；‘cosine’：

‘correlation’： ‘hamming’：

‘jaccard’： ‘chebychev’：Chebychev距离。

1.2 squareform函数

调用格式：Z=squareform(Y,..)

说明： 强制将距离矩阵从上三角形式转化为方阵形式，或从方阵形式转化为上三角形式。

1.3 linkage函数

调用格式：Z=linkage(Y,’method’)

说 明：用‘method’参数指定的算法计算系统聚类树。

Y：pdist函数返回的距离向量；

method：可取值如下：

‘single’：最短距离法（默认）； ‘complete’：最长距离法；

‘average’：未加权平均距离法； ‘weighted’： 加权平均法；

‘centroid’： 质心距离法； ‘median’：加权质心距离法；

‘ward’：内平方距离法（最小方差算法）

返回：Z为一个包含聚类树信息的（m-1）×3的矩阵。

1.4 dendrogram函数

调用格式：[H，T，…]=dendrogram(Z,p，…)

说明：生成只有顶部p个节点的冰柱图（谱系图）。

1.5 cophenet函数

调用格式：c=cophenetic(Z,Y)

说明：利用pdist函数生成的Y和linkage函数生成的Z计算cophenet相关系数。

1.6 cluster 函数

调用格式：T=cluster(Z,…)

说明：根据linkage函数的输出Z 创建分类。

1.7 clusterdata函数

调用格式：T=clusterdata(X,…)

说明：根据数据创建分类。

T=clusterdata(X,cutoff)与下面的一组命令等价：

Y=pdist(X,’euclid’);

Z=linkage(Y,’single’);

T=cluster(Z,cutoff);

2. Matlab程序

2.1 一次聚类法

X=[11978 12.5 93.5 31908;…;57500 67.6 238.0 15900];

T=clusterdata(X,0.9)

2.2 分步聚类

Step1 寻找变量之间的相似性

用pdist函数计算相似矩阵，有多种方法可以计算距离，进行计算之前最好先将数据用zscore函数进行标准化。

X2=zscore(X); %标准化数据

Y2=pdist(X2); %计算距离

Step2 定义变量之间的连接

Z2=linkage(Y2);

Step3 评价聚类信息

C2=cophenet(Z2,Y2); //0.94698

Step4 创建聚类，并作出谱系图

T=cluster(Z2,6);

H=dendrogram(Z2);

分类结果：{加拿大}，{中国，美国，澳大利亚}，{日本，印尼}，{巴西}，{前苏联}

剩余的为一类。

虾仁腰果

虾仁腰果，也是做了比较久的一个菜了，从前那个“一周的便当”里也有，做法、配料和那个几乎完全一样，味道好，就愿意去重复。

主料：虾、腰果、豌豆辅料：葱、姜、蒜、色拉油、料酒、盐、糖、醋、淀粉各少许

1、 虾去头、皮，并把虾线剔除清洗干净；豌豆入沸水汆8成熟；腰果入油炒至金黄，酥脆盛出备用。

2、 葱、姜、蒜切末；整理好的虾加淀粉、盐、料酒码10分钟。

3、 锅入油，爆香葱、姜、蒜，加虾仁翻炒。

4、 而后依次加腰果、豌豆，再加盐、糖、醋调味，最后水淀粉勾芡。