  Weakly supervised learning generally faces challenges in applicability to
various scenarios with diverse weak supervision and in scalability due to the
complexity of existing algorithms, thereby hindering the practical deployment.
This paper introduces a general framework for learning from weak supervision
(GLWS) with a novel algorithm. Central to GLWS is an Expectation-Maximization
(EM) formulation, adeptly accommodating various weak supervision sources,
including instance partial labels, aggregate statistics, pairwise observations,
and unlabeled data. We further present an advanced algorithm that significantly
simplifies the EM computational demands using a Non-deterministic Finite
Automaton (NFA) along with a forward-backward algorithm, which effectively
reduces time complexity from quadratic or factorial often required in existing
solutions to linear scale. The problem of learning from arbitrary weak
supervision is therefore converted to the NFA modeling of them. GLWS not only
enhances the scalability of machine learning models but also demonstrates
superior performance and versatility across 11 weak supervision scenarios. We
hope our work paves the way for further advancements and practical deployment
in this field.
