Hierarchies of concepts are useful in many applications from navigation to organization of objects. Usually, a hierarchy is created in a centralized manner by employing a group of domain experts, a time-consuming and expensive process. The experts often design one single hierarchy to best explain the semantic relationships among the concepts, and ignore the natural uncertainty that may exist in the process. In this paper, we propose a crowdsourcing system to build a hierarchy and furthermore capture the underlying uncertainty. Our system maintains a distribution over possible hierarchies and actively selects questions to ask using an information gain criterion. We evaluate our methodology on simulated data and on a set of real world application domains. Experimental results show that our system is robust to noise, efficient in picking questions, cost-effective, and builds high quality hierarchies.

This video shows the corresponding MAP tree (the most probable tree) after each update.

The same method can be applied to build very large hierarchies.

The following video demonstrates how the model parameters, adjacency matrix of the graph, evolves after getting more information from workers.

Publication

Building Hierarchies of Concepts via Crowdsourcing, Yuyin Sun, Adish Singla, Dieter Fox, Andreas Krause, IJCAI 2015
NEOL: Toward Never-Ending Object Learning, Yuyin Sun, Dieter Fox, ICRA 2016

Acknowledgement

This material is based upon work supported in part by the Intel Science and Technology Center for Pervasive Computing, ONR grant N00014-13-1-0720, and ARO grant W911NF-12-1-0197.