Active Semi-Supervised Learning using Submodular Functions

Understand

We consider active, semi-supervised learning in an offline transductive setting.

• We show that a previously proposed error bound for active learning on undirected weighted graphs can be generalized by replacing graph cut with an arbitrary symmetric submodular function.
• Arbitrary non-symmetric submodular functions can be used via symmetrization.
• Different choices of submodular functions give different versions of the error bound that are appropriate for different kinds of problems.