2018年北京大学可视化暑期学校 – Day 3 (2018年7月19日)

可视化暑期学校的第三天授课的老师是来自新加坡国立大学的赵盛东教授和来自雅虎研究院的胡一凡研究员。上午,赵盛东教授为我们带来了主题为The Next Interaction Paradigm的课程。

赵盛东教授授课

课程的第一部分是Interaction Paradigm Shift – 交互范式的转变。赵老师给我们讲解了他对交互范式短期和中长期转变的预测。

赵教授认为,人机交互研究短期内的转变主要有:交互方式从被动响应人的操作(reaction)转变为主动与人交互(proactive);I/O方式从以文本为中心(text centric)转变到多模态(multi-modal)。以语音助手为例,以往的语音助手只对用户的要求做出响应,并且有时候会打扰到用户,具有较低的情商,未来的语音助手将会主动与用户沟通,提供及时的帮助,并且能够较好地理解用户的需求。

中长期的转变主要有:交互方式从以设备为中心(device-centric)转变为以人为中心(human-centric);I/O方式从多模态转变到全方位(holistic),这需要软件和硬件的共同发展;人类和工具将会共同进化,以人为中心的技术将会全面发展。

赵老师为我们描述了human-centered technology的前景,例如在将来的户外,人将只需要穿戴三种设备:头部设备(head piece),主要用于显示信息;手部设备和身体设备(hand / body piece),提供实时触感反馈;而在室内,各种传感器将会为人提供全方位的交互。

在课程的第二部分,赵老师为大家讲解了如何进行人机交互的研究:人机交互需要综合利用人和机器的优势,实现人和机器的平衡。人的优势有:感官非常发达,能够感受到微小的刺激,识别能力、推理能力强,能够发明各种策略,具有很好的适应能力等。而机器的优势在于,具有很强的计算、储存和回忆能力,能够重复做出响应,机器擅长于简单而且精确定义的事情。进行人机交互的设计需要综合考虑这些因素。

随后,赵老师给大家介绍了他的一些研究项目:Vignette[1],交互式的纹理设计和填充软件,可以帮助用户快速生成和填充纹理;Draco[2],一种高效生成动态纹理的交互软件;SandCanvas[3],基于多点触控的模拟沙画艺术媒介,可以帮助艺术家创作沙画;Magic Cards[4],一种新颖的人与家务机器人交互的方式,人在需要做家务的地方放置卡片来指示机器人完成对应的任务。在课程的最后,赵老师对人机交互的未来进行了展望:人机交互有着很好的发展前景,但要在人机交互领域有所成就,需要对人和计算机都有深刻的理解,并且需要有全方位的思考。

下午的讲者是来自雅虎研究院的资深可视化学者胡一凡研究员,他的授课题目是Graph and Map Visualization with Applications to Machine Learning.

雅虎研究院的资深可视化学者胡一凡研究员授课

首先,胡老师较为详细地介绍了一下图可视化的基本方法和前沿动态。对于有向图,一种基本的方法是Legered Layout. 而对于无向图,有两种常用的方法:

Force-directed layout 将图模型化为一个引力斥力系统,认为图中相邻的两点之间有类似弹簧拉力的引力,而任意两点间均有类似同性电荷间的斥力。最小化此系统的能量,即得到一个各点之间距离合适的布局[5]。

最小化能量的过程一般用迭代法求解(求解过程称为cooling)。在此过程中,步长的设置是非常重要的。传统的方法是每一步按比例(如0.9)减小步长,而胡老师提出了一种替代方法,主要思想为:若能量持续减小则增加步长,若能量增加则减小步长(详见[6])。

Force-directed layout对于大图可扩展性不佳,主要原因是:时间复杂度较大,为O(|V|)^2;容易落入local minima。为解决时间复杂度问题,主流方案是将距离较远的节点集合为一个supernode,同时用合适的数据结构(如quadtree)计算,时间复杂度可降为O(|V|log|V|). 为寻找global minima,使用一种multilevel方法,将图逐步简化(称为coarsening),先计算简化图的布局,再依据上一步的结果计算复杂图的布局。具体的coarsening方法主要分两种:第一种是寻找最大边匹配,合并所得边的两端点;第二种是寻找最大点独立集,作为简化后图的顶点集(同时只保留此顶点集中点之间的边)。

这种方法也有其局限性,对于以Gupta1 Matrix为例的含有少量度数超大结点的图,无法产生令人满意的布局(可以先从相似性出发,合并部分较小的结点)。甚至有些时候,对于较大的树得到的结果也不好,相似叶结点可能会collapse

Stress model (multi-dimensional scaling, MDS) 这种方法将图模型化为一个有初始长度弹簧连接的结点系统,同样用最小化能量的解法。[7]如果我们希望边的长度尽量接近一个预设值,这种方法比较合适。对于预设了距离的结点对,其间弹簧的初始长度也随之确定,其他结点对之间的弹簧初始长度则设置为两结点之间的最短路径长度。由于需要计算每一对结点之间的最短路径,所以此算法时间复杂度较大。胡老师在讲座中提到了几种解决这一问题的方法。

第二部分中,胡一凡老师解释了可视化与机器学习之间的相关性,并且提出可视化就是一种无监督学习的论点。他用Isomapword2vec的例子分别解释了这一观点。Isomap是一种基于MDS的降维策略,主要是为解决高维空间中的流形结构在低维空间中的可视化问题。而word2vec是一种词向量表示法,基于文本中意思相近的词其上下文也相似的思想。这两个算法都是机器学习领域的知名算法,而其目标与上面介绍的(图)可视化问题相似。

最后,胡老师介绍了自己用可视化方法解释机器学习的一些工作。第一个工作是用virtual map理解推荐系统。首先利用用户的评分将待推荐的电影映射为图中结点,然后做clustering,区分出不同类型的电影,并将图用Voronoi graph转化为地图的形式呈现。值得注意的是,为了表现出各电影的重要程度或推荐程度不同,算法中在代表电影的结点周围添加若干结点,使得最终地图上的面积能够反映这一差异(同时也使voronoi图生成的边界变得圆滑)。第二个工作是Name embedding。此工作的应用场景类似微信异地登录的好友验证,需要从多个名字中选出自己好友的名字。假名字应从与真名字相似的名字中选取,而同一个人联系人列表中的名字应在种族和性别上具有相似性,所以可用类似word2vec算法的方式算出名字间的相似性。进一步,可以将名字映射为图中结点,然后类似地用地图的方式展现不同性别和种族人名的分布情况。

参考资料:
[1]Kazi, Rubaiat Habib, et al. “Vignette: interactive texture design and manipulation with freeform gestures for pen-and-ink illustration.” Proceedings of the SIGCHI Conference on Human Factors in Computing Systems. ACM, 2012.
[2]Kazi, Rubaiat Habib, et al. “Draco: bringing life to illustrations with kinetic textures.” Proceedings of the SIGCHI Conference on Human Factors in Computing Systems. ACM, 2014.
[3]Kazi, Rubaiat Habib, et al. “SandCanvas: a multi-touch art medium inspired by sand animation.” Proceedings of the SIGCHI Conference on Human Factors in Computing Systems. ACM, 2011.
[4]Zhao, Shengdong, et al. “Magic cards: a paper tag interface for implicit robot control.” Proceedings of the SIGCHI Conference on Human Factors in Computing Systems. ACM, 2009.
[5]T. M. J. Fruchterman and E. M. Reigold, “Graph Drawing by Force-Directed Placement,”
Software—Practice and Experience, 21(11), 1991 pp. 1129–1164.
[6]HU, Y. F. 2005. Efficient and high-quality force-directed graph drawing. Mathematica J. 10, 37–71.
[7]T. Kamada and S. Kawai, “An Algorithm for Drawing General Undirected Graphs,” Information Processing Letters, vol. 31, pp. 7-15, 1989.

评论关闭。