群体智能系统的计算机理、行为分析与软件方法研究

作者: 时间:2017-06-27 点击数:

上世纪90年代末,李未院士首先倡导对因特网上的海量信息开展研究,实验室承担了国内首个关于海量信息的973项目,在该项目及项目的滚动支持下,取得了丰硕成果。2012年以来,李未院士提出从研究因特网上客观存在的“海量信息系统”转为研究基于人机物融合的“群体智能系统”。实验室积极参与了人工智能国家重大专项的论证,并使得群体智能被列为该专项的重要组成部分。

具体而言,群体智能系统是指大量具有智能的个体交互作用形成的系统。典型的群体智能系统包括众包系统、社交网络系统等。在国家重大基础研究规划973项目、国家自然科学基金项目和国家重点实验室自选课题等项目的支持下,实验室综合运用理论分析、模拟验证、实际部署等手段,对群体智能系统计算机理、行为分析与软件开发方法进行了深入的研究,并取得了一系列原创性成果。具体成果介绍如下:

1.群体智能系统的计算机理

群体智能系统的一类典型代表是各类众包计算平台,而任务分配问题是众包计算研究中的核心问题之一。其早期研究着眼于静态离线场景中众包任务分配策略,但随着移动互联网等技术的发展,当前的众包计算平台通常需要面向动态在线场景。因此基于静态离线场景所提出的任务分配策略无法适用。为解决上述问题,实验室在国际上首创了众包动态任务分配理论,证明了平均情况分析下双侧动态在线二分图匹配问题的竞争比为常数。特别的是,针对在线最小化二分图匹配问题,现存研究通常采用最差情况分析证明贪心算法的竞争比为指数阶,并认为简单的贪心算法不实用。实验室的研究揭示了采用平均情况竞争分析的方法贪心算法的竞争比为常数而非指数阶,而且最差情况发生的概率仅为1/n!,n为全部众包任务的数量。从而澄清了一个25年来令算法理论与应用实践相悖的误解,该研究成果被大数据领域顶级会议VLDB的审稿人评价为将在未来产生实质性影响”

综上所述,实验室以众包计算平台为代表研究了群体智能系统中任务分配与质量控制的计算机理,一系列的研究成果主要发表于TKDE等数据库领域国际顶级(CCF A类)期刊和VLDB、ICDE等数据库领域国际顶级(CCF A类)会议。此外,实验室一项关于众包任务分配的研究还获得了数据库领域国际重要会议WAIM 2016的唯一最佳论文奖。

2.群体智能系统的行为分析

此外,实验室以群体行为受群体情绪的影响为切入点,以新浪微博系统为例研究了社交网络情绪的传播机理。为此,实验室主持设计和开发了国际上第一个针对中文微博的在线情绪分析系统MoodLens。于MoodLens系统,实验室分析了20万新浪微博用户的7000万条微博数据,利用信息转发关系,抽取出一个由交互频繁的用户组成的交互网络。通过将微博情绪分为高兴、愤怒、低落和厌恶四类情绪进行大数据分析,发现了“愤怒是社交网络上最容易传播的情绪”这一规律。如图所示,左图为网络拓扑,点表示用户,边表示用户间的交互。基于用户情绪对该拓扑图中的点着色,结果如右图,红色代表愤怒,绿色代表高兴,蓝色代表低落,黑色代表厌恶。计算结果发现社交网络中愤怒和高兴的相关性显著地高于低落和厌恶,其中愤怒的相关性最高,这意味着包含愤怒情绪的信息可能会在网络中传播得更快。

该项研究成果被《麻省理工技术评论》评价为这一发现可能对我们理解社交网络上信息的传播产生重大影响”随后该成果被来自90多个国家的数百家媒体报道,并被写入英中法德意等5种语言的10多本书籍,包括国外小学教材、本科教材、畅销书,以及计算机、政治、经济、新闻、心理学和金融等领域的专著。此外,实验室还不断探索更有效的适用不同场景的情绪分类模型和算法。以上研究成果主要发表于TKDE、TPDS、TOIS等国际顶级(CCF A类)期刊和SIGMOD、AAAI、ACL等国际顶级(CCF A类)会议。

3.群体智能系统的软件方法

另外,针对互联网软件开发大众化和开放性特征,基于群体智能的理论与方法,实验室开创了群体软件工程这一新方向,重点研究群体软件开发的理论和过程模型、群体交互行为模式和演化规律、支撑工具和开发环境等。系统地提出了群体软件的理论框架和过程模型。实验室在国际上率先举办Dagstuhl国际群体软件研讨会,并组织了两次群体软件的国际会议,系统地提出了群体软件的理论框架和过程模型,构造了群体软件社区的软件项目影响力传播模型,在国际上首次出版了关于群体软件理论和工程方法的英文专著《Crowdsourcing: Cloud-Based Software Development》。

特别针对先进网络环境下超大规模系统中传统软件开发方法所遇到挑战性问题,即精英化、计划性和封闭式等局限性,实验室首次提出“使用者即设计者,使用者即开发者,使用者即维护者”的软件开发新思路,定义了群体软件工程的基本要素,建立群体软件工程的理论基础,并给出了“群体软件工程”的全新软件开发模式。特别在群体软件理论的指导下,实验室设计开发出面向高校应用的群体智能系统“众智北航”,在北京航空航天大学进行了实际部署和应用,并获得国际开源软件联盟OW2 程序设计竞赛一等奖。

软件开发环境国家重点实验室 地址:北京市海淀区学院路37号北京航空航天大学新主楼G座
邮编:100191 联系电话:010-82338092 邮箱:nlsde@nlsde.buaa.edu.cn