Error-tolerant version space algebra

Application customization has been extensively researched in the field of Programming by Demonstration (PBD), and Version Space Algebra has proven itself to be a viable means of quickly learning precise action sequences from user demonstrations. However, this technique is not capable of handling user error in domains with actions that depend on parameters that accept myriad values. Activities such as image, audio and video editing require user actions that are difficult for users to precisely replicate in different circumstances. Demonstrations that are off by a single pixel or a split-second cause traditional composite Version Spaces to collapse. We present a method of incorporating error tolerance into Version Space algebra. This approach, termed Error-Tolerant Version Spaces, adapts Version Space Algebra to domains where the tactile capabilities of the user have a much greater chance of prematurely collapsing the hypothesis space that is being learned. The resulting framework is capable of quickly learning in domains where perfectly consistent user input can not be expected. We have successfully applied our technique in the domain of image redaction, allowing our users to quickly specify redactions that can be reliably applied to many images without the entry of explicit parameters.