（信号与信息处理专业论文）个性化信息推荐服务和机器翻译自动评测关键技术的研究.pdf

个性化信息推荐服务和机器翻译自动评测关键技术的研究 摘要 基于互联网的各种应用，包括信息获取，在本质上可以抽象为基于用 户需求的信息传递，信息推荐的目的是将信息传递到真正需要这些信息的 用户手中，同时尽可能地避免用户因盲目寻找信息时却往往要面对大量“垃 圾信息”的尴尬境地。随着互联网的不断发展，这种推荐服务必将成为互 联网应用的基础性研究。 在自然语言研究领域中，评测问题越来越受到广泛的重视，可以说， 评测是整个自然语言领域最核心和关键的部分。对于科研工作者和研究人 员来说，借助自动评测工具，不仅能够缩短应用系统的研发周期，还能够 i 司其他系统进行性能比较，权衡利弊。 本文对这两个领域的一些关键问题进行了研究。第一部分是基于合作 的网络信息推荐。从解决信息推荐的及时性和有效性两个方面入手。在提 高信息推荐的响应速度的同时，提供最可靠的信息给用户；第二部分是自 动评测技术在自然语言理解领域中尤其是在机器翻译领域中的研究和应 用，在深入分析评测标准的同时，也提出了新的改进标准，并实现了个 完整的测试平台，对我们的想法进行了验证。 本文在个性化信息服务推荐和机器翻译的自动评测这两个领域的应用 进行了研究和探索。取得的成果包括： ( 一)在深入研究b l e u 和n i s t 两种机器翻译自动评测标准的基础上， 提出了基于t f i d f 权重信息的评测标准和相似度计算模型，设计并完 成了一个开放性的机器翻译自动评测系统； ( 二)在分析了传统k - m e a n s 聚类算法的基础上，利用空间数据结构 模型，提出了一种基于k d 树的快速聚类算法改进方案，取得了显著 的效果： ( 三1在合作信息推荐中，为计算用户之间的潜在相似度，给出了e v s ( 增强矢量相似度) 算法，仿真实验表明，e v s 算法在计算用户之间 相似度方面明显优于传统算法； ( 四)为了提高合作式推荐系统的运行性能，提出了基于特征项的推荐 算法，这科，方法就是从信息项之间的关联度挖掘入手，提取对用，、具 有推荐价值的信息项，对于提高系统的推荐性能是种很好的解决方 案； ( 五)提出多a g e n t 生态进化算法来解决创新性和适应性的问题，为避 免盲目变异产，t 有价值个体的概率太低的问题，给出r 基于语义网络 的生态进化算法，以提高系统的有效性。 关键词：个性化信息推荐合作信息推荐基于项目信息推荐自动评测 t h er e s e a r c ho fp e r s o n a l i z e d r e c o m m e n d a t i o ns e r v i c ea n da u t o m a t i c e v a l u a t i o no fm a c h i n et r a n s l a t i o n a b s t r a c t a l m o s ta l lo ft h e 。a p p l i c a t i o n sb a s e do ni n t e m e t ，i n c l u d i n gi n f o r m a t i o n r e t r i e v a l c a nb er e d u c e d t ot h ec u s t o m e r - o r i e n t e dt r a n s m i s s i o no f i n f o r m a t i o n t h ea i mo fi n f o r m a t i o nr e c o m m e n d a t i o ni s - - j 2 0 wc op r e s e n t t h e r i g h ti n f o r m a t i o nt o t h er i g h tp e r s o n t h i sa p p l i c a t i o nt r i e st om a k e u s e r sa v o i dt ob ee m b a r r a s s e db yt h eh u g eu s e l e s si n f o r m a t i o nw h e n t h e y s e a r c hi n t e r n e t w i t ht h e r a p i dg r o w t h o fi n t e r n e t ，i n f o r m a t i o n r e c o m m e n d a t i o nw i l lb eo n eo ft h ef u n d a m e n t a lr e s e a r c h e s i nt h ea r e ao fn a t u r a ll a n g u a g ep r o c e s s i n g ，e v a l u a t i o np l a y sac r i t i c a l r o l ei nt h em a c h i n et r a n s l a t i o n t h cr e s e a r c ho fa u t o m a t i cm a c h i n et r a n s l a t i o n e v a l u a t i o ni sa l lu r g e n tn e e df o rt h en a t u r a ll a n g u a g ep r o c e s s i n gr e s e a r c h e r sa n d d e v e l o p e r s w i t hs u c ht o o l s 。d e v e l o p e r sw i l lf i n do u tt l l e d e f i c i e n c i e so ft h e s y s t e m s w h i c h c o m p a r e d w i t ho t h e r p r o d u c t i o n s i t a l s oc a nf e s o l v et h e p r o b l e m s o ft h et i m e c o n s u m i n ga n dl a b o r i o u sw o r kb ye x e c u t i n gh u m a n j u d g m e n t s t h i s p a d e r d o e sa c o m p r e h e n s i v e r e s e a r c ho nt h ea r e a so fi n d i v i d u a l i n f o r m a t i o nr e c o m m e n d a t i o na n da u t o m a t i cm a c h i n et r a n s l a t i o ne v a l u a t i o n i n t h ef i r s tp a r t i ti n t r o d u c e st h ec o i l a b o m t i v e - t i a s e di n f o r m a t i o nr e c o m m e n d a t i o n a n dp u t se m p h a s i so nt h ee f f i c i e n c ya n de f f e c t i v i t y w et 哕t op r o v i d et h eb e t t e r r e c o m m e n d a t i o ns e r v i c ea sw e l la sm a k et h er e s f o n s et i m es h o r t e r ；i nt h e s e c o n dp a r t i td e s c r i b e st h ea p p l i c a t i o n so fa u t o m a t i ce v a l u a t i o ni nt h en a t u r a l l a n g u a g ep r o c e s s i n g ，e s p e c i a l l y i nt h ea r e ao fm a c h i n et r a n s l a t i o n w es t u d yt h e m e t r i c so fe v a l u a t i o na n dm a k es o m ei m p r o v e m e n t s w ea l s o t e s tt h en e w c r i t e r i ab yt h ea u t o m a t i ce v a l u a t i o np l a t f o r mw h i c hj so p e na n df e a t u r ed y n a m i c c o n f i g u r a b l e mt h el a s tp a r t 。u n d e rt h eg u i d a n c eo ft h em e t h o d o l o g yo f n a t u r a l l a n g u a g eu n d e r s t a n d i n gb a s e do nc o m p r e h e n s i v ei n f o r m a t i o n ，w ee x p l o r e dt h e n a t u r a ll a n g u a g ep r o c e s s i n gt e c h n o t o g yi nt ka b o v et w o p r a c t i c a lf i e l d s t h em a i nr e s u l t sa r e ： 1 ) b a s e d o nt h es t u d y i n gt h eb l e um e t r i ca n dn i s tc r i t e r i a ，w ep r o p o s et h e t f i d f w e i g h t e de v a l u a t i o nm e t h o da n ds i m i l a r i t ym o d e lb yt h ei d e a sf r o m t e x tr e t r i e v e a sar e s u l t ，i tc a ng i v ear e m a r k a h l ee f f e c to rt h ea u t o m a t i c e v a l u a t i o no fm a c h i n et r a n s l a t i o n w ea l s od e s c r i b ea ne v a l u a t i o np l a t f o r m w h i c hc a nt a k em o r ec o n v e n i e n c et ot h er e s e a r c h e sa n d d e v e l o p e r s 2 ) t i m er e q u i r e di n ad i r e c ta l g o r i t h mo fk - m e a n sm e t h o di ss e n s i t i v et ot h e n u m b e ro f p a t t e r n s ，t or e s o l v et h i sp r o b l e m ，w ep r e s e n tan e w a l g o r i t h m t o p e r f o r m k - - n - l e a n sc l u s t e r i n g ：k - r dt r e eb a s e dc l u s t e r a l g o r i t h m ： 3 ) t h ei m p o r t a n ts t e po f c o l l a b o r a t i v e b a s e di n f o r m a t i o nr e c o m m e n d a t i o ni st o c o m p u t e t h es i m i l a r i t i e sb e t w e e n u s e r s p r o f i l e s w eg i v e 幽e e v s ( e n h a n c e dv e c t o rs i m i l a r i t y ) m e t h o d t h es i m u l a t i o ne x p e r i m e n t ss h o wt h a t e v sc a nr e f l e c tt h e1 a t e n ts i m i l a r i t i e sb e t w e e nu s e r s t h ep e r f o r m a n c ei s b e t t e rt h a nt h et r a d i t i o n a lm e t h o d s 4 ) w ei n t r o d u c ed i f f e r e n ti t e m b a s e dr e c o m m e n d a t i o ng t a e r a t i o n a l g o r i t h m s w h i c hc a nq u i c k l yp r o d u c eh i g hq u a l i t yr e c o m m e n d a t i o n s ，e v e nf o rv e r y l a r g es c a l ep r o b l e m s ， 5 、w 8 p r o p o s et h es e m a n t i c n e t w o r k b a s e dm u l t i - a g e n tg e n e t i ca l g o r i t h m t o r e s o l v et h ec r e a t i v ea n d a d a p t i v ep r o b l e m s w h i c ha r ea b s e n ti nt h e c o n t e n t b a s e dr e c o m m e n d a t i o ns y s t e m k e yw o r d s ：p e r s o n a l i z e di n f o r m a t i o nr e c o m m e n d a t i o n ，c o l l a b o r a t i v e i n f o r m a t i o nf i l t e r i n g ，i t e m b a s e di n f o r m a t i o nr e c o m m e n d a t i o n ，a u t o m a t i c e v a l u a t i o n 儿j ，t l ：“i u 人学博i 学位论义铺 晕慨述 1 课题研究总体思路 第一章概述 语言文字是承载和传播信息的主要载体。而随着计算机和互联网的高速发展，以文 字为主体的形式多样的数字化媒体信息已经深入到人们的生活和工作中的各个领域。 蕊对浩如烟海的巨大信息资源，如何对信息进行有效地查询和获取，是提高人们学 习和工作效率的关键问题。虽然基于互联网的各种应用技术也在不断涌现，但无论 其表现形式如何变化，归根结底，这些应用在本质上可以抽象为对信息的有效获取 和利用。当信息从信息源经过信息通道传输后最终到达具有需求的用户的手中时，信 息的价值才能够得到真正的体现，相应的应用也隧之成立。所以，信息的个性化服务， 即如何将信息传递到真正需要这些信息的用户手中，已经成为互联网应用的一个关键的 基础性研究。 另一方面，制约着互联网应用发展的瓶颈就是自然语言处理问题，这个问题的解决 程度也在根本上限制了网络应用的智能水平。而在实际的研究和开发过程中，往往由于 自然语言理解系统的高复杂性，实验缩果的评测所需要的人力和时间等因素的制约，使 得一个问题的研究和解决周期过长，这与实际应用中对高效的智能系统的迫切需求形成 了一个非常尖锐突出的矛盾。因此，自动评测技术在自然语言处理问题中的各种应用也 是一个非常具有实用价值的研究课题。 在攻读搏士学位期间，作者有幸跟随钟义信教授从事自然诱富镫理却静能信息处理 方面的研究。以全信息自然语言理解方法论为指导，结合统计与规则两种研究手段，在 个性化服务与自动评测技术这两个智能信息处理领域进行了广泛而深入的探索和研究， 并取初步得了些研究成果。理论来源予实践，又反过来指导实践，这是一条颠扑不破 的真毽。我希望通过对个性化信息服务和自动评测技术豹智能业务的研究，能够在自然 语言处理的理论和实用关键技术方面取得一点进展。本文就是作者近三年的研究工作汇 报。 北京邮电大学智能研究中心承担的多语富智能信息服务网络系统被北京奥组委 接受为北京2 0 0 8 奥运会“科技奥运”的项目，同时列入了“奥运行动规划”，并成为“规 划”中的亮点。这个课题的研究也同时得到了国家8 6 3 计划的支持，本人所做的研究工 作也在此项目中得到了直接应用。 豫啦概述 2 个性化的信息推荐服务 忆l _ j 删的是人们进行信息共享的一一个最有效【：具。而随着恻络中的信息爆炸式的增 长，让用户丌始困惑的已经不是有没有所需要的信息，而是如何能够获耿自己真正所需 要的信窟、。为帮助用户获取信息，首先产生了信息获取的研究。它可以让用户根据自己 的信息需求，方便地找到在信息内容上与之匹配的网络资源，例如数据库的网络检索系 统、网络目录、网络搜索引擎等。用户每次进行信息获取时，都要明确地表达出个人| 勺 需求，目前，最主要的表达形式就是关键字词所构成的查询式。这种简啦而有效的信 息获取方式曾经一度给用户带来了极大便利，y a h o o ! ，搜狐等门户网站的兴起就是这种 应用的典型代表。但随着网络信息内容的极度膨胀这种方式的弊端也日益显现：一方 蕊，基于关键词的检索方式难以满足用户不同层次的查询需求，用户往往陷入无法用合 适的关键词表达自己需求的尴尬境地之中；另一方面随着网络信息资源的同益膨胀， 检索结果中存在越来越多的非相关信息，信息获取的精度不足。 信息获取主要关注用户的短期信息需求，为提高信息获取的质量和使用的方便性， 就要关注用户的长线信息需求，因此出现了信息过滤技术。信息过滤技术在假设用户兴 趣将维持段时间基本不变的前提下，根据相关用户的兴趣信息，建立用户模型，从大 量的历史信息流中，借助用户模型析取用户感兴趣的信息。 通常，我们把经过信息过滤的结果主动推送到用户手中，从而形成基于个性化的主 动信息推荐服务。通过信息推荐技术，从根本改变了传统的信息获取方式，获取过程的 重点转移到人这个对象上。计算机从被动地接受查询关键词变为主动向用户推荐信息， 满足用户的信息需求。这将节省用户的时间，大大提尚学习和工作的效率。 通过个性化的信息推荐服务，各种网络应用也可以把信息主动发送到相应的用户面 前，这即实现了网络应用的价值，又改善了用户的工作和生活质量。例如在电子商务中， 对书籍或影像产品等购物信息的推荐：在学术研究资料检索应用中，推荐相关的论文和 资料，能够给科研工作者以极大的便利。高性能的网络应用建立在高性能的信息推荐基 础上，这式网络应用提供者和网络应用用户双方的共同需求。 高性能的个性化信息推荐包括如下内涵： ( 1 ) 推荐信息的准确性：信息推荐系统提供的信息要尽可能地满足用户的需求， 这就需要对用户需求的准确把握、对信息内容的准确把握、对信息内容和用 户需求之f b j $ 目关性的准确把握； ( 2 ) 推荐信息响应的及时性：网络应用面对的服务客户是数以l 万计的。面对大 鞋用户的信息需求推荐系统要及时地对用户作吐；有效的反馈： 锵；髯慨迷 3 ) _ = j ，。为中心：信息推荐系统要以用户为中心进行服务 7 】，这就要方便用户的 使用，例如，系统主动将信息推荐给用户：用户可以方便地表达自己的需求； 系统要及时适应用户需求的变化。 3 自动评测技术在自然语言理解中的应用 近年来，在自然语言研究领域中，评测问题越来越受到广泛的重视，可以说，评测 是整个自然语言领域最核心和关键的部分。比如，对于某一个算法，要说明算法是有效 且可靠的，就必须给出对算法的评测结果，除了理论上的证明，还要有实验的评测结果 束说明。对于系统开发或者是研制产品来说，评测也是至关重要的。通过自我评测，来 说明版本升级带来的性能变化：通过横向评测，说明自己和竞争产品的性能，比较得失， 权衡利弊。国际上为了推动自然语言研究的评测，在过去的几年中，进行了若干次有影 响的评测活动，如m u c 评测专名识别问题，t r e c 评测信息检索的发展，还有许多机 器黼译和语音技术的评测活动，所有这些评价活动都有力地促进了相关学科的发展。 作者在文中首先全面地介绍了最近出现的而且受到极大关注的机器翻译评测技术， 即b l e u 机器翻译评测标准和n i s t 采用的机器翻译评测技术。实验表明，自动翻译评 测技术能够接近人工评价，评测结果也是可接受的。因此，采用自动翻译评测技术能够 给自然语言处理的研究人员和开发人员带来很大的便利性。 在理论研究的基础上，我们开发出了一个开放式的可扩展的自动翻译评测的平台， 完全实现了b l e u 和n i s t 评测标准，并在此基础上提出了毅的改进评测标准，通过实 验表明得该系统具有良好的使用性和可扩展性。 另外，除了将自动评测理论和技术在机器翻译领域的研究和应用进行探讨之外，我 们还针对文摘领域的自动评测技术的可行性和方案进行了设想，在今后的研究工作中作 为进一步的研究目标不断努力。 论文安排 本篇论文的内容是由三个部分的研究工作构成，各个部分的章节安排如下： 笫。章：概述。介绍了课题研究的总体思路并对每一部分的研究内容进行了简簟介 绍： 筘錾：个性化推荐服务简介。这一章对信息推荐的研究现状进行了综述，主要内 容包括：信息轶取与信息推荐的背景及研究现状：个性化推荐胀务简介；基于内容分析 此豪1 u 人学博i 。学位论义筇一母概述 的信息推荐的研究背景及现状；基于合作的信息推荐的研究背景及现状等内容。 第三章：基于k - d 树的快速聚类算法。本章针对信息推荐服务中的效率问题，在传 统的聚类算法基础上提出了一种改进方案，并通过实验证明了这种新算法的有效性。 第四章：基于合作的个性化信息推荐。单纯基于内容的信息推荐存在其不足之处， 所以在这一章我们从e v s 算法，i t e m b a s e d 算法和a g e n t 等不同角度实现了基于合作的 个性化信息推荐模式。希望能够给个性化信息推荐服务中遇到的一些难点给出有效的解 决方案。 第五章：自动评测技术在自然语言理解中的应用。以机器翻译的自动评测技术为重 点，介绍了当前存在的主要自动评测技术，并提出了新的评测规则和技术。我们还介绍 了实验室开发实现的一个开放式自动评测平台，实验证明，该平台对于自然语言理解的 研究人员来说是一个非常有效的辅助工具平台。 图1 1 论文内容示意图 第二章个性化推荐服务简介 随羞因特网及其相关技术的迅速发展，人们寻找资源和获取信息方面享受到了前所 未有的便利。但时至今同，人们却为如何从信息的海洋中找到自己真正感兴趣的，有价 值的信息而渐感力不从心。另方面，随着基于因特网的电子商务业务的蓬勃发展，如 何给用户提供更为准确、合理的信息成为了赢得用户的一个重要手段。因此，有效地帮 助用户克服“信息过剩”问题，提供基于用户兴趣特征的个性化服务已经成为进一步提 高网络内容服务质量的亟待解决的重要课题之一，而提供个性化的服务机制也是未来网 络内容眼务的一个发展方向。 2 1 用户建模简介 用户模型是包含用户所有与系统运行相关的特征描述的系统知识库 1 1 1 2 。每一个用 户模型都包含三个基本功能模块： 1 ) 存储和表达模块：管理有关用户的知识。 2 ) 更新模块：向用户模型添加新的知识。 3 ) 连接功能模块：支持和四应用户模型所在的整个系统的要求。 用户模型一般来说分为通用模型和个人模型。通用模型是对于某一组用户有效的知 识；个人模型则是每一个人区别于其他人的特殊知识。信息推荐系统可以根据自身的不 同选用通用模型或者个人模型。 通用模型又被称作固定规则( s t e r e o t y p e r u l e s ) 3 】，它通常包含一些用户分组信息， 例如，一组用户的兴趣是计算机科学，另一组是文学；或者，一组用户是专家，另一组 是初学者。这些信息的表示方式有关键词、一般描述等。它们通常以分层目录结构、表 格、超链接或规则的形式存储。 个人模型又被称作用户描述( u s e rp r o f i l e ) 。它主要用于个性化信息推荐系统中，用 来表示用户特有的背景知识或兴趣。用户描述分为两种： 1 ) 知识库的表达方式：记录用户的职业、爱好等知识； 2 ) 问接的表达方式：例如由一组关键词( 往往是带权重的) 组成。或者使用用户 评价为感兴趣或不感兴趣的一些文章来描述用户的兴趣，这种方法常用于基于 文本的信息推荐中。也可以用一组和用户兴趣相近的其他用户来描述用户的兴 趣这种方法常用于合作推荐中。 北京l 】| | 5 u 入学博i 。学位论上 如t 1 个性化推荐服务简介 相应的，获取用户模型的方法通常有如下两种方式： 1 ) 在用户初次使用系统时，填写初始化表格，使系统了解用户的基本情况。 2 ) 在系统运行时，通过用户对系统返回的结果的反馈，了解用户信息。 在撼r 内容的信息推荐中，有两种常用的方法来预测用户埘新文章是西感兴趣：关 键词匹配法和向量空间法。 2 2 关键词匹配法 表示用户兴趣的关键词有一部分会在初始化时得到，而其它则斋要根据崩尸一0 一些 文章的评价得到。信息推荐系统应该能够根据用户评价为感兴趣或不感兴趣的文章抽取 出表示用户兴趣的关键词。 调频的计算一般采用t f i d f 法。文章i 中词k 的权重d w , k 由下式计算： d w i k = 矿；+ ( 1 0 9 2 ( n ) 一l 0 9 2 ( 田：+ 1 ) ) 式( 2 - 1 ) 其中，m 是词k 在文章i 中的频率；d i 是包含有词k 的文章数： 在提取关键词时，根据公式( 2 1 ) ，计算用户感兴趣的文章中出现的词k 的权重。： 地= 饥一毗t 式( 2 _ 2 ) 其中l 为用户感兴趣的文章集答，u 为剧户不感兴趣的文章集合。选出权重最大的 n 个词，作为代表用户兴趣的关键词。而后可以根据新文章包含这些关键词的多少来预 测它是否是用户感兴趣的文章。 2 3 向量空间法 出于系统记录了每个用户感兴趣的文章和不感兴趣的文章我们可以将每篇文章映 射为向量空间中的一个向量，这样，样本空间就分为了两类。可以根据这些样本向量计 算新文章对应的向量在向量空间中的分类，从而确定用户对新文章感兴趣还是不感兴 趣。 向量空问法的实现分为文章的向量表示、词汇一文章空问的降维、文章自动分类这 二三个步骤。 2 3 1 文章的向量表示 在文章表示成向量之前首先要对文章进行预处理，对待英义，预处理的步骤为 l t j 1 、；。：mt 、，他沧艾 1 ) 丘掉文章一 i 不含有分类信息的阋( s t o p w o r d ) ，如t h e 、t h a t 等： 2 ) 将些变形后的词恢复原形( s t e m m i n g ) ，如将p l a y e d ，p l a y i n g 变为p l a y 。 刈待中文，预处理的步骤为： 1 ) 根据分词词典对中文进行分词； 2 ) 去掉文章中不含有分类信息的词( s t o p w o r d ) ，如“已经”，“不过”等。 文章的向量表示主要有以下两种方法： 1 ) 如尔型：取出文章集中所有的词，每一个词对应向量的一维，文章含有这个词， 则这一维的数值为1 ，不含则为0 。 2 ) t f i d f 型：取出文章集中所有的词，每一个词对应向量的一维，数值的大小为 这个词的t f i d f 值。 2 3 2 词, e - 文章空问的降维 由于2 3 1 中形成的向量维数很高，很难进行分类计算，因此在进行训算前要降维。 在这里介绍基于信息熵的方法和l s i ( l a t e n t s e m a n t i ci n d e x i n g ) 方法。 2 321 基于信息熵( i n f o r m a t i 0 1 3g a i n ) 的降维方法 信息熵是计算一个词在某种分类下表示信息量多少的方法，它能找到那些在好样本 中出现频率高丽在坏样本中出现频率低的词，以及那些在坏样本中出现频率高而在好样 本中出现频率低的词。这是通过计算信息熵的期望e ( w s ) 得到的。计算公式如下： e ( w ，s ) = ，( s ) 一【p ( w = p r e s e n t ) i ( s 。) + p ( 即7 = a b s e n t ) l ( s 。，) 式( 2 3 ) ，( s ) = 一p ( s , ) l o g z ( p ( 疋) ) 其中 一( h 0 7 x o t d ) 式( 2 - 4 ) oa p ( w = p r e s e n t ) 是单词w 在一篇文章中出现的概率；o ，是包含w 的文章集：o c 是属于类别c 的文章集。 在具体计算时，若共有n 篇文章，其中”i 篇文章为用户感兴趣的文章，”2 篇文章为 用户不感兴趣的文章；共有m 篇文章含有关键词，其中用户感兴趣的文章中共舀”l 篇 文章含有关键词w ，用户不感兴趣的文章中共有肌z 篇文章含有关键词w 。 这时，式( 2 4 ) 中，p ( s m 。，) ：玉，p ( s 。“) = n _ l 。式( 2 4 ) 可写成 竹n 北- ：i i i4 ： l 人学博1 学位论史 耶) ：一n l o g ：( 生) hn 由此，式( 2 3 ) 中耶。，) 一m l o g ：( 堕) 一生l 。g ! ( 生) mmm 2 l ( s 。，) = 一生= _ 堕i o g ：( 生= _ 堕) 一兰2 二生l o g ：( 旦堕) 胛一坍n m胛一m月一研 式( 2 3 ) 可写成 p ( w = p r e s e n t ) = 一m ，e ( w = a b s e 刖1 ：尘竺。 n r 式( 2 - 5 ) e ( w ，j ) 2 【s ) 一【p ( w2 p r e s e n t ) l ( s 。，) 十p ( w2 a b s e n t ) l ( s 6 。) 】 = 一n l 0 9 2 ( 旦l ) 一n 2l 0 9 2 ( 生) 一i r a ( 一m ，l 0 9 2 ( 堕) 一生l 0 9 2 ( 生) ) + 兰二竺( 一生旦l 。g ：( 生旦) 一笠二堕i 0 9 2 ( ! 生旦) ) ( 26 ) f ln 一，hh h t一，hi i l i = 一n , l o g ：( 鱼) 一n 2 1 0 9 2 ( 鱼) nhhh + 堕l 0 9 2 ( 堕) + 堕l 0 9 2 ( 生) nr hhf h + 生= _ 竺l i 0 9 2 ( 生丑) + 生二生l 0 9 2 ( 竺2 二堕) 通常我们可以选择e ( w ，s ) 最大的词，组成降维之后的向量。 2 3 2 2 l s l 方法 l s i 模型最初应用于信息获取的研究，它利用奇异值分解技术s v d ( s i n g u l a r v a l u e d e c o m p o s i t i o n ) 对词汇一文章向量空间进行降维，劳保持文章渊的语义关系。l s i 模型 认为，通过使用s v d 对词汇一文章空间降维，文章间隐含的语义关系被展示出来，而那 些噪声( 由选词的不确定性和不代表文章意义的词汇产生) 则被降低了。这使得降维之 后，语义相同的文章在向量空间中的位置相近【4 】【5 】。下面对s v d 进行简介： 令a 是一个m * n 维的实数矩阵，则存在m + m 和n * n 的正交阵u m x m 和v n x n ，使 得a = u z v t ，是m * n 的对角阵，其主对角线上的元素。1 1 o2 2 oh h ，o ： h = m i n ( m ，n ) 【6 。 ok k 称为矩阵a 的奇异值，u 和v 分别叫做矩阵a 的左奇异阵和右奇异阵。奇异 值0k k 包含了有关矩阵a 秩的特性。 设矩阵a m x n 为一个t e r m d o c 矩阵。通过奇异值分解可以有效地将矩阵a 进行压缩， 并保持各文档间的相似度基本不变。 两篇文档的相似度可以用代表这两篇文档的向量夹角的余弦值来描述，对于列归一 化( 指任意列的向量的模为1 ) 的矩阵a 来说，文档的相似度j n 奠由觚1 a 来表示，这样 s = a t a 中的任何一一个元素s 1 1 都表示文档i 和文档j 的相似性。 由奇异值分解得a = u v t ，令c = e v t ，u 为正交阵，所以c t c = a t a 。由于 的元素满足ol l o2 2 o l l l o ：h = m i n ( m ，n ) ，即越靠后的奇异值对于整体的 影响越小，可以考虑只取矩阵的前k ( i o 一_ h ) 个奇异值构成矩阵l 来代替矩阵，l 为 k * n 的矩阵，满足 ( o1 1 2 + o2 2 2 + + ok k 2 y ( o1 1 2 + o2 2 2 + + oh h 2 ) 接近l 【6 。 这样，仓一d = e 1 v t 代替矩阵a 将可以很好地保持文档之间的相似度，同时实现了 对t e r m d o c 矩阵a 的压缩，产生的矩阵d 为k * n 维，这样篇文档本来用m 维向量表 示，压缩为k 维，经验表明，m 通常大于1 0 0 0 0 ，k 通常小于5 0 0 ，因此压缩率显著。 2 3 3 ，文章的分类 在降维之后，我们就可以使用样本文章集合对瓤文章进行分类了。分类方法包括： r o c c h i o 中心向量法 7 】、贝叶斯分类器( b a y e s i a nc l a s s i f i e r ) 8 】、k 近邻法f n e a r e s t n e i g h b o r ) 9 、决策树【8 、神经网【1 0 】、s v m ( s u p p o r tv e c t o rm a c h i n e ) 1 l 】等等。下面只 对r o c c h i o 中心向量法和交互s v m 法进行介绍。 2 3 3 1 r o c c h i 0 中心向量法 r o c c h i o 中心向量法利用样本文章集生成一个代表用户兴趣的向量p ，而后判断新文 章向量与p 的相似度，相似度高的文章分入用户感兴趣的文章集，其余分入用户不感兴 趣的文章集。 r o c c h i o 中心向量法是种相关反馈( r e l e v a n c ef e e d b a c k ) 方法，即利用人对分类结 果的评价来修改代表用户兴趣的向量p ，在与人交互的过程中不断提高分类精度。 r o c c h i o 中心向量法的公式为： 刚艺k = l 址n ir 善毒 柳， 其c tr k 为第k 篇用，、感兴趣的文章的向量，s t 为第k 篇用户不感兴趣的文章的向 咀z l ，n - 为用户感兴趣的文章数，2 2 为用户不感兴趣的文章数，卢、，为控制参数。实验 表明：、鸶卢：07 5 ，= 0 2 5 时，效果较好。 得到代表用户兴趣的向量p 后，我们定义新文章向量与p 的相似度。向量问的相似 度通常利用向量之问的夹角余弦来衡量。我们设w 为新文章向量，p 与w 的相似度r ，w 表示为： p ，m r 矿8 0 ，w ) 2 肃 加固 集。 若r 。火丁某一阂值r ，则w 属丁刚户感兴趣的文章集，否则w 属下用户不感兴趣的文章 2 3 3 2 交互s v h 法 用户通常只评价少量资源，为此，一方面需要设计好的学习算法，充分利用用户的 评价信息；另方面，根据文本信息推荐问题的特点，我们可以将用户的评价引导到最 关键的地方。 交互s v m 法以s v m 法为基础，在候选的样本空间s 中，根据已有学习样本的信 息，设计分类器，并主动选择对于当前分类器不确定度最大的新样本进行评价，再进一 步设计新的分类器，将设计分类器变成一个交互的过程。即：恨据对已知样本进k e y w o r d s 行的s v m 分类器设计，主动采样选择“有用”的新样本并进行下一步s v m 分 类器的设计。与普通s v m 法相比，该方法所需的样本量大大降低，而且具有更好的推 广能力。 对于两类问题，设当前分类器对未知样本x 的预测后验概率分别为h o ( x ) 、h ，( x ) h o ( x ) + p ( x ) = l ：则x 对于原系统的不确定度可用香农熵表示为： h 。= 一h 。( x ) l o g 。( x ) 一a ( x ) l o g 。( x ) 。容易得出：选择i 氐( x ) 一多( x 】越小的样本，原系 统的不确定度越大。 交h ：s v m 学习算法就是用s v m 实现主动学习的方法。由s v m 的原理可以看出： 决策【自是只与s v 有关的超平面，s v m 通过使分类问隙最大来设汁决策超平面，以获 得最好的推广能力，样本点到决策超平面的距离则是判断该点分类性质的主要因素。设 第章个性化排柠u h 务尚介 样本点x 到决策| f ；| 1q 的距离为d i s t ( x ，q ) ，则：l 风( x ) 多。( x 】o cd i s l ( x ，9 ) 。刈交互s v m 法 的新样本选择的策略为： x = a r g m i n ( d i s t ( x ，g j 】 x s 式( 2 9 ) 其中a r g m i n ( a ( x ) ) 为取使a ( x ) 最小的x ，即采样点应该尽量靠近当前+ 的分类边界。 关于线性可分的问题，算法要处理两种情况： i ) 评价s v m 分类缝隙中的未知样本点时，即选择在分类缝隙中的样本点进行下一 步分类器设计时，分类边界将会改变，如图2 1 ( a ) ： 2 ) 当分类缝隙中不存在样本点时，采样后所设计的分类器的分类边界也可能改变， 如图2 1 ( b ) ，当采样点( 灰点) 为“白”时，边界将改变。 ( a ) 未知样本点在分类缝隙中( b ) 未知样本点不在分类缝隙申 图2 1 未知样本选择的不同情况 此外，交互s v m 法还需要一些初始样本进行最初分类器的设计，这一般可以通过 先验知识或随机采样得到。在文本分类中，可以通过关键词匹配的方法进行挑选。 算法步骤如下： 1 ) 根据初始条件构造初始训练样本集： 2 ) 根据已知训练样本集设计s v m 分类器q ； 3 ) 如果分类器q 邻近的缝隙中仍有样本点，则根据( 2 9 ) 式选择新的x 进行评价， 将x 加入训练样本集，并回到第2 步； 4 ) 从全部训练样本中重复随机选择一个样本x 进行评价，并将x 加入训练集( 对 已评价过的样本只计数，不用再次评价) ，利用分类器对样本进行评价，若分类 器的评价结果与真实评价不一致，则回到第2 步： 5 ) 重复第4 步，若连续n 次正确，算法停止。 算法的分析 当n 足够大时，交互s v m 算法将与普通s v m 相同。普通s v m 算法的自：理沦垫础 北京1 1 1 1 f 1 u 人学博i 学位论文鸲母 十，| i t t t 椎荐眦务简介 源于统计学习理论，其主要思想是使结构风险最小化s r m ( s t r u c t u r er i s km i m m i z a t t o n ) 。 引入表示分类器复杂度的参数v c 维h ，关于分类器的推广能力有以卜关系： r o ) r e i n p 缸) + 、堑塑掣尘蚴1 却- l o ) v 1 其中，靠( 口) 为实际风险，宾一【球) 为经验风险，h 为v c 维，l 为训练集样本数，1 - 叩 为。靛信度。 s r m 的目标是使实际风险兄忸j 最小。2 1 0 式给出了在l 一蹿概率下分类器实际错误 率的上界，便其上界最小化能间接地达到实际风险最小的目的，由2 ，1 0 式右边可以看 i = _ ，除将经验风险最小化外，极小化h 也是一个重要方面。因此，构造s v m 的思路为： 使21 0 式右边第一项不变( 趋于零) 作为限制条件，优化结构使第二项最小。具体方 法是通过受限寻优方法使分类闷隙极大化，从而使h 极小化，这与传统方法的固定结构 ( 固定h ) 使经验风险最小有本质的不同。 交互s v m 法的风险分析如图2 ，2 所示： 竭2 2 交互s 张法风险分析示意圈 图2 2 中，h 0 点是普通s v m 所选择的点。由于分类间隙不断减小，极小化的结构 风险( 2 i o 式中第二项) 成上升趋势，随训练样本的增加，经验胍睑逐渐减，j 、。因此， 可能存在这样的情况：在经验风险m 7 降为最小( 即使用全部样本进行s v m 分类器 设计所能达到的经验风险) 之前，实际风险上界m j 可能比h o 点更小。例如，选择部 分训练样本，使经验风险下降到a 时，学习机的实际风险上界在h l 点。也就是说，交 互s v m 法所能达到的推广能力有可能超过使用全部样本进行学习的普通s v m 法。 j l l ：i i l ；l _ j 、：；4 # 1 一论t 2 4 个性化信息推荐服务 个性化在很多领域中同益受到重视，如服装、汽车等，信息的需求更加需要个性化， 个人化服务是提高网络信息服务质量的必然发展方向。 由于网络用户的背景不同、喜好不同、目的不同，导致对信息的需求也不同。如果 不关汴这种不