Interruptible Algorithms

Traditional data mining algorithms are exceptional at seeing patterns in data that humans cannot, but are often confused by details that are obvious to the organic eye. Algorithms that include humans "in-the-loop" have proved beneficial for accuracy by allowing a user to provide direction in these situations, but the slowness of human interactions causes execution times to increase exponentially. Thus, we seek to formalize frameworks that include humans "over-the-loop", giving the user an option to intervene when they deem it necessary while not having user feedback be an execution requirement. With this strategy, we hope to increase the accuracy of solutions with minimal losses in execution time. This paper describes our vision of this strategy and associated problems.

This project consists of two major components: deciding which learning algorithms are interruptible and designing a framework of implementation for which these algorithms may be interrupted. It is worth noting interruptibility is differs from interactivity in the way it makes available changes to execution. While interactivity requires the algorithm to pause execution and wait for the user to perform some input, interruptible algorithms allow for the user to provide input asynchronously to execution.

The interruptibility of an algorithm is measured by an interruptibility index defined as the ratio of complexities between the change the user wants to make and the algorithm itself. We also propose a framework providing this interruptibility to an arbitrary learning algorithm by posing the problem in the context of an operating system. That is, a kernel is responsible for execution of the algorithm and the handling of the data while providing a layer of interaction with a user via system calls. The information contained within the kernel is passed to the user space and visualized in a way that a human can easily digest and act on the information. This system is currently in development.

Publications

Austin Graham, Yan Liang, Le Gruenwald, Christan Grant. Formalizing Interruptible Algorithms for Human over-the-loop Analytics. The IEEE International Workshop on Human-Machine Collaboration in BigData (HMData 2017). Boston, Massachusetts. 2017.