Incremental Quality Inference in Crowdsourcing

Presentation on theme: "Incremental Quality Inference in Crowdsourcing"— Presentation transcript:

1 Incremental Quality Inference in Crowdsourcing
众包环境下多谓词查询优化 冯剑红 胡卉芪 翁学平 冯建华 Jianhong Feng (Tsinghua, China) Guoliang Li (Tsinghua, China) Henan Wang (Tsinghua, China) Jianhua Feng (Tsinghua, China)

2 概览 研究动机 框架 基于随机序列的最优选择算法 基于过滤的序列选择算法 实验 结论

3 众包环境下的查询优化 研究动机 研究现状 不同的谓词顺序代价不同 传统查询优化技术不适用众包环境 不考虑谓词顺序生成的代价
Query: 图片中的人物是“男性” 并且“棕色头发” 并且“带眼镜” 研究动机 不同的谓词顺序代价不同 传统查询优化技术不适用众包环境 不考虑谓词顺序生成的代价 研究现状 利用人类本能设计问题 [A. Marcus, PVLDB-13]

4 众包环境下多谓词查询优化 研究挑战 研究思路 如何获得高质量的谓词顺序 如何控制谓词顺序生成代价 基于采样的众包多谓词选择查询
利用随机序列获得谓词顺序 利用谓词选择性筛选序列

5 基于采样的众包多谓词选择查询 谓词顺序生成

6 谓词顺序生成问题 输入 输出 样本集合规模直接影响谓词顺序质量 R：样本集合 ：选择查询 减少谓词顺序生成代价， 同时获得高质量的谓词顺序
例如: 查询 {性别=男性，头发=棕色，眼镜=是} 最优谓词顺序：眼镜，头发，性别 减少谓词顺序生成代价， 同时获得高质量的谓词顺序

7 基于随机序列的最优选择算法 算法框架 第1步：生成m个随机序列： 第2步：人工验证随机序列并计算序列代价
例如：序列1{头发，眼镜，性别}，所有图片的头发已经获得验证结果，序列2{眼镜，头发，性别}，头发不需要再次验证 辅助矩阵记录已经验证过的问题 =1，-1 第3步：比较序列代价，选择最小代价的序列

8 基于随机序列的最优选择算法 通过随机序列数量m控制谓词顺序质量 确保 能够以大于 的概率位于k个最好的谓词顺序中 满足该公式的最小m

9 基于过滤的序列选择算法 观察 基本思路 谓词数量较多，基于随机序列的选择算法代价难以保证 质量较差的后续随机序列增加代价
过滤质量较差的谓词序列 利用辅助矩阵计算谓词选择性 当 =1， =1 质量较差序列： 并且Aj 位于Ai 的前面 设置阈值保证谓词选择性的有效性

10 基于过滤的序列选择算法 序列数量 OS-m: 采用基于随机序列方法的序列数量 在生成第i+1个序列的时候开始筛选序列
基于过滤的序列选择算法得到的结果 位于k 个最好的谓词顺序中的概率： 基于随机序列的最优选择算法 OS ：动态确定序列数量 只需要在 个较优的序列中选择一个序列 ：已经获得谓词选择性分值的谓词数量 产生序列的终止条件：

11 实验评测 数据集 对比方法 People Cloth 1,000张人物图片 5个属性 Crowdflower 1,856张衣服图片 8个属性
Amazon Mechanical Turk 对比方法 暴力方法，真实最优谓词顺序

12 评测谓词顺序生成代价 People人物 Cloth衣服 样本代价：获得谓词序列产生的问题数量
基于过滤的方法样本代价少于基于随机序列的方法，谓词数量较少时，基于随机序列的方法样本代价少于暴力方法 随着k增加，基于随机序列的方法样本代价下降明显

13 评测谓词顺序质量 People人物 Cloth衣服 总体代价：采用谓词序列实现选择查询所需要的问题数量
基于过滤的方法始终优于基于随机序列的方法，非常接近真实最优谓词顺序 随着k增加，基于随机序列的方法总体代价上升明显

14 结论 众包环境下多谓词查询优化 提出了基于随机序列的最优选择算法 提出了基于过滤的序列选择算法
显著减少查询序列生成的代价，同时获得高质量的查询序列

15 Thanks! Q&A