自动可视化生成系统:Draco(Formalizing Visualization Design Knowledge as Constraints: Actionable and Extensible Models in Draco)

本篇工作[1]介绍了一个自动生成可视化的系统Draco。用户需要输入数据集和简单的数据描述,然后根据自己的任务,输入需要编码的数据,可以指定编码的方式,Draco通过计算,得到一个优化的结果,最后通过Vege-Lite生成可视化。下图为一个简单示例。

Q1:为什么Draco生成的可视化是最优的?

根据J.Mackinlay在1986年提出的APT[2]系统,评价可视化可以从两个方面进行。表达性(Expressiveness)以及有效性(effectiveness)。expressive:能正确表现数据中的所有事实,同时也只表现数据中的事实。effective:被表达的事实更能被用户接受。J.Mackinlay根据有效性提出了约200条规则,如下图所示。


本篇工作认为,可以将每条规则视为一个约束(Constraint),在这些约束的作用下,可以获取最优的可视化方案。

Q2:如何利用约束来获取可视化方案?

整体思路:将可视化设计问题转化为约束空间优化问题(ASP),而ASP类问题有很好的优化求解方法(Clingo)。

背景知识

ASP类问题需要使用逻辑编程。这里简单介绍一下逻辑编程。

  • 基本约束表现形式:
    • A :- B, C. 如果B且C为真,即A为真。所有:-表示的约束都称作硬约束,即必须遵守。
  • 特殊表现形式:
    • A:-. 无前提A为真,即要求A永真。
    • :- B, C. 如果B且C为真,无论结果是什么都能为真。明显不可能,所以推出前提不能为真,即B且C为假。本工作将主要采取该表现形式。
  • l {A, B, C, …} k 即至少l个,至多k个为真。
  • 软约束:
    • :~ B, C. [w] 不同于硬约束,可称为软约束(soft constraints)。该约束可以不被遵守,只不过会造成w的损失。
  • 给定一个求解空间,且给定硬约束和软约束,可通过Clingo[3]求解器获取最优结果。

Draco的主要工作:
1.将所有规则重写为约束的形式,将可视化设计问题转为ASP问题;
2.通过Clingo求解ASP,获取最优解;
3.使用Vega-Lite生成可视化。

Q3:如何获取约束?

  1. 用户提供的数据描述以及主要任务
    数据描述会告知Draco不同属性的数据类型,主要任务包括可视化编码的对象,以及一些指定的编码方式,mark、channel等。
  2. 硬约束
    硬约束在本工作中也可称作完整性约束。由两个部分组成:

    1. 来自编码的约束
      1. 编码方式本身的约束,如mark和channel的匹配性,若用户指定采用shape作为视觉通道,那么mark只能是point。
      2. Vega-Lite的限制,Vega-Lite至多只能生成8种shape,所以shape编码的数据基数不能超过8。
    2. 来自表达性的约束,若用户编码的数据为定类型数据,Draco将不会分配size作为通道(size本身有等级,一般用来编码定序型数据,编码定类型数据会造成用户的误解)。
  3. 软约束
    软约束一般用来表达可视化设计的有效性,比如在很多情况下,位置都是一个非常的视觉通道,位置优于面积,所以这些情况下,违反位置编码的损失将小于违反面积编码的损失。由全部软约束构成的模型,在本工作中,也被称作为偏好模型(preference model)。
    来自两个成熟的工作:

    1. APT system。 约200条规则,可重写为约束。
    2. CompassQL[4]。 本文作者之前的工作,也是一个自动生成可视化的系统,其中约含有70条硬约束,110条软约束,其中软约束的损失w由可视化专家制定。
      因为CompassQL和本文工作思路比较接近(都是采取约束求解的处理方式,使用的约束也有很大的相似性),我们将在最后讨论两者的不同(Q6)。

硬约束与软约束如何共同协作

Q4:如何决定软约束中的损失

首先,由专家来指定损失是一个很大的挑战,特别是在软约束比较复杂的情况下,专家需要对全局有很深的了解,才能决定不同约束的损失值。
作者希望采用机器学习的方式来确定不同的cost。
作者认为偏好模型是一个马尔科夫逻辑网络(MLN),所以决定采用RankSVM的方法进行处理。
有关RankSVM如何具体工作的部分,在此不做赘述。

Q5:既然采用的是机器学习的方法,那么训练数据如何获取?

两个相关工作

  1. Kim et al.[5] 作者之前的工作,内含1,920个被试,总共185,000个针对不同可视化设计的结果。作者将这些结果按照不同数据类型,以及不同可视化任务进行分类,然后将同一类的可视化两两配对,若该两者在正确率和使用时间上都有显著性差异(p<0.01),即可作为训练数据。根据此工作,最后找到约1100对训练数据。
  2. Saket et al.[6] 该工作中的数据只有很少部分有显著性差异,共只找到10对训练数据。

Q6:CompassQL和Draco的不同

  1. 编码方式不一样。CompassQL没有采用逻辑编程,而是采用JavaScript,造成编码效率上的巨大差异。代码量约3400行。
  2. 求解方式不一样。CompassQL没有采用ASP优化求解的方法,而是选择使用深度优先进行搜索。CompassQL的工作流程:
    1. 使用硬约束来减少设计空间
    2. 生成所有符合设计空间的可视化编码
    3. 利用偏好模型(即软约束)为所有可视化编码进行评分
    4. 挑选得分最高的可视化编码,利用Vega-Lite生成最后的可视化设计
      因为CompassQL相当于采用枚举的方式去评判每一个可能的结果,所以造成了时间上的巨额浪费。详细对比结果参考下图。

Pipeline

总结

该工作有两个非常大的亮点

  1. 可扩展性
    因为偏好模型可以随时添加新的软约束,同时也可根据不同的数据利用RankSVM来调整损失值。随着新的可视化有效性工作的开展,随着新的可视化用户研究的深入,Draco都可以进行相应的跟进。
  2. 问题的转化
    本工作采用逻辑编程的方式,将规则重写为约束,大大增加了编写程序的效率。同时又将可视化问题转化为优化求解领域的ASP问题,利用另一个领域成熟的计算方法,来求解可视化领域的问题。真的非常厉害!

参考文献

[1] Moritz D, Wang C, Nelson G L, et al. Formalizing visualization design knowledge as constraints: Actionable and extensible models in draco[J]. IEEE transactions on visualization and computer graphics, 2018.

[2] J. Mackinlay. Automating the design of graphical presentations of relational information. ACM Transactions on Graphics, 5(2):110–141, 1986. doi: 10.1145/22949.22950

[3] M. Gebser, R. Kaminski, B. Kaufmann, and T. Schaub. Clingo = ASP + control: Preliminary report. CoRR, abs/1405.3694, 2014.

[4] K. Wongsuphasawat, D. Moritz, A. Anand, J. Mackinlay, B. Howe, and J. Heer. Towards a general-purpose query language for visualization recommendation. In Proceedings of the Workshop on Human-In-the-Loop Data Analytics – HILDA ’16, pp. 1–6, 2016. doi: 10.1145/2939502.2939506

[5] Y. Kim and J. Heer. Assessing effects of task and data distribution on the effectiveness of visual encodings. Computer Graphics Forum (Proc. EuroVis), 2018.

[6] B. Saket, A. Endert, and C. Demiralp. Task-based effectiveness of basic visualizations. IEEE Vis (Proc. InfoVis), 2018. doi: 10.1109/TVCG.2018.2829750

发表评论?

0 条评论。

发表评论


注意 - 你可以用以下 HTML tags and attributes:
<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>