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

作者: 日期: 2018年10月8日

本篇工作[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

论文报告, ,

评论关闭。