Weak supervision

Weak supervision is a branch of machine learning where noisy, limited, or imprecise sources are used to provide supervision signal for labeling large amounts of training data in a supervised learning setting. This approach alleviates the burden of obtaining hand-labeled data sets, which can be costly or impractical. Instead, inexpensive weak labels are employed with the understanding that they are imperfect, but can nonetheless be used to create a strong predictive model.

Problem of labeled training data

Machine learning models and techniques are increasingly accessible to researchers and developers; the real-world usefulness of these models, however, depends on access to high-quality labeled training data. This need for labeled training data often proves to be a significant obstacle to the application of machine learning models within an organization or industry. This bottleneck effect manifests itself in various ways, including the following examples:

Insufficient quantity of labeled data

When machine learning techniques are initially used in new applications or industries, there is often not enough training data available to apply traditional processes. Some industries have the benefit of decades' worth of training data readily available; those that do not are at a significant disadvantage. In such cases, obtaining training data may be impractical, expensive, or impossible without waiting years for its accumulation.

Insufficient subject-matter expertise to label data

When labeling training data requires specific relevant expertise, creation of a usable training data set can quickly become prohibitively expensive. This issue is likely to occur, for example, in biomedical or security-related applications of machine learning.

Insufficient time to label and prepare data

Most of the time required to implement machine learning is spent in preparing data sets. When an industry or research field deals with problems that are, by nature, rapidly evolving, it can be impossible to collect and prepare data quickly enough for results to be useful in real-world applications. This issue could occur, for example, in fraud detection or cybersecurity applications.

Other areas of machine learning exist that are likewise motivated by the demand for increased quantity and quality of labeled training data but employ different high-level techniques to approach this demand. These other approaches include active learning, semi-supervised learning, and transfer learning.

Types of weak labels

Weak labels are intended to decrease the cost and increase the efficiency of human efforts expended in hand-labeling data. They can take many forms, and might be categorized into three types:

• Global statistics on groups of inputs: This setting consists in accessing global information on bags of samples — e.g. knowing that half of the labels of a given subset of samples. Examples of global statistics supervision include multiple-instance learning and learning from label proportion.
• Weak classifiers: A second approach consists in assuming the access to many weak classifiers that weakly correlate with the function to learn. Those classifiers might model labelers from a crowdsourcing platform, experts, noisy measurements or heuristic rules. More generally, developers may take advantage of existing resources (such as knowledge bases, alternative data sets, or pre-trained models) to create labels that are helpful, though not perfectly suited for the given task.
• Incomplete annotation: Finally, weak supervision might be understood as the access to partial knowledge on each label. This partial knowledge can be thought of as a corruption process. In some instances, partial observation can be cast as a set of potential labels that are compatible with this partial observation, which is the setting of partial supervision. Partial supervision is a generalization of semi-supervised learning, which has been the classical approach to overcome the bottleneck of data annotation.

Beyond those three settings, limitations that motivates weakly supervised learning might be tackled by leveraging human knowledge under the form of priors or of function architectures, reviving old approaches of artificial intelligence such as inductive logic programming.

Applications of weak supervision

Applications of weak supervision are numerous and varied within the machine learning research community.

In 2014, researchers from UC Berkeley made use of the principles of weak supervision to propose an iterative learning algorithm that solely depends on labels generated by heuristics and alleviates the need of collecting any ground-truth labels. The algorithm was applied to smart meter data to learn about the household's occupancy without ever asking for the occupancy data, which has raised issues of privacy and security as covered by an article in IEEE Spectrum.

In 2018, researchers from UC Riverside proposed a method to localize actions/events in videos using only weak supervision, i.e., video-level labels, without any information about the start and end time of the events while training. Their work introduced an attention-based similarity between two videos, which acts as a regularizer for learning with weak labels. Thereafter in 2019, they introduced a new problem of event localization in videos using text queries from users, but with weak annotations while training. Later in a collaboration with NEC Laboratories America a similar attention-based alignment mechanism with weak labels was introduced for adapting a source semantic segmentation model to a target domain. When the weak labels of the target images are estimated using the source model, it is unsupervised domain adaptation, requiring no target annotation cost, and when the weak labels are acquired from an annotator, it incurs a very small amount of annotation cost and falls under the category of weakly-supervised domain adaptation, which is first introduced in this work for semantic segmentation.

Stanford University researchers created Snorkel, an open-source system for quickly assembling training data through weak supervision. Snorkel employs the central principles of the data programming paradigm, in which developers create labeling functions, which are then used to programmatically label data, and employs supervised learning techniques to assess the accuracy of those labeling functions. In this way, potentially low-quality inputs can be used to create high-quality models. Afterward, the Stanford AI Lab researchers created Snorkel AI, which originated from the Snorkel project, using state-of-the-art programmatic data labeling and weak supervision approaches, successfully decreasing AI development costs and time significantly.

In a joint work with Google, Stanford researchers showed that existing organizational knowledge resources could be converted into weak supervision sources and used to significantly decrease development costs and time.

In 2019, Massachusetts Institute of Technology and Google researchers released cleanlab, the first standardized Python package for machine learning and deep learning with noisy labels. Cleanlab implements confident learning, a framework of theory and algorithms for dealing with uncertainty in dataset labels, to (1) find label errors in datasets, (2) characterize label noise, and (3) standardize and simplify research in weak supervision and learning with noisy labels.

Researchers at University of Massachusetts Amherst propose augmenting traditional active learning approaches by soliciting labels on features rather than instances within a data set.

Researchers at Johns Hopkins University propose reducing the cost of labeling data sets by having annotators provide rationales supporting each of their data annotations, then using those rationales to train both discriminative and generative models for labeling additional data.

Researchers at University of Alberta propose a method that applies traditional active learning approaches to enhance the quality of the imperfect labels provided by weak supervision.

Semi-supervised learning

An example of the influence of unlabeled data in semi-supervised learning. The top panel shows a decision boundary we might adopt after seeing only one positive (white circle) and one negative (black circle) example. The bottom panel shows a decision boundary we might adopt if, in addition to the two labeled examples, we were given a collection of unlabeled data (gray circles). This could be viewed as performing clustering and then labeling the clusters with the labeled data, pushing the decision boundary away from high-density regions, or learning an underlying one-dimensional manifold where the data reside.

Semi-supervised learning is a special instance of weak supervision that combines a small amount of labeled data with a large amount of unlabeled data during training. Semi-supervised learning falls between unsupervised learning (with no labeled training data) and supervised learning (with only labeled training data).

Unlabeled data, when used in conjunction with a small amount of labeled data, can produce considerable improvement in learning accuracy. The acquisition of labeled data for a learning problem often requires a skilled human agent (e.g. to transcribe an audio segment) or a physical experiment (e.g. determining the 3D structure of a protein or determining whether there is oil at a particular location). The cost associated with the labeling process thus may render large, fully labeled training sets infeasible, whereas acquisition of unlabeled data is relatively inexpensive. In such situations, semi-supervised learning can be of great practical value. Semi-supervised learning is also of theoretical interest in machine learning and as a model for human learning.

A set of $l$ independently identically distributed examples $x_{1},\dots ,x_{l}\in X$ with corresponding labels $y_{1},\dots ,y_{l}\in Y$ and $u$ unlabeled examples $x_{l+1},\dots ,x_{l+u}\in X$ are processed. Semi-supervised learning combines this information to surpass the classification performance that can be obtained either by discarding the unlabeled data and doing supervised learning or by discarding the labels and doing unsupervised learning.

Semi-supervised learning may refer to either transductive learning or inductive learning. The goal of transductive learning is to infer the correct labels for the given unlabeled data $x_{l+1},\dots ,x_{l+u}$ only. The goal of inductive learning is to infer the correct mapping from $X$ to $Y$.

Intuitively, the learning problem can be seen as an exam and labeled data as sample problems that the teacher solves for the class as an aid in solving another set of problems. In the transductive setting, these unsolved problems act as exam questions. In the inductive setting, they become practice problems of the sort that will make up the exam.

It is unnecessary (and, according to Vapnik's principle, imprudent) to perform transductive learning by way of inferring a classification rule over the entire input space; however, in practice, algorithms formally designed for transduction or induction are often used interchangeably.

Assumptions

In order to make any use of unlabeled data, some relationship to the underlying distribution of data must exist. Semi-supervised learning algorithms make use of at least one of the following assumptions:

Continuity / smoothness assumption

Points that are close to each other are more likely to share a label. This is also generally assumed in supervised learning and yields a preference for geometrically simple decision boundaries. In the case of semi-supervised learning, the smoothness assumption additionally yields a preference for decision boundaries in low-density regions, so few points are close to each other but in different classes.

Cluster assumption

The data tend to form discrete clusters, and points in the same cluster are more likely to share a label (although data that shares a label may spread across multiple clusters). This is a special case of the smoothness assumption and gives rise to feature learning with clustering algorithms.

Manifold assumption

Main article: Manifold hypothesis

The data lie approximately on a manifold of much lower dimension than the input space. In this case learning the manifold using both the labeled and unlabeled data can avoid the curse of dimensionality. Then learning can proceed using distances and densities defined on the manifold.

The manifold assumption is practical when high-dimensional data are generated by some process that may be hard to model directly, but which has only a few degrees of freedom. For instance, human voice is controlled by a few vocal folds, and images of various facial expressions are controlled by a few muscles. In these cases, it is better to consider distances and smoothness in the natural space of the generating problem, rather than in the space of all possible acoustic waves or images, respectively.

History

The heuristic approach of self-training (also known as self-learning or self-labeling) is historically the oldest approach to semi-supervised learning, with examples of applications starting in the 1960s.

The transductive learning framework was formally introduced by Vladimir Vapnik in the 1970s. Interest in inductive learning using generative models also began in the 1970s. A probably approximately correct learning bound for semi-supervised learning of a Gaussian mixture was demonstrated by Ratsaby and Venkatesh in 1995.

Semi-supervised learning has recently become more popular and practically relevant due to the variety of problems for which vast quantities of unlabeled data are available—e.g. text on websites, protein sequences, or images.

Methods

Generative models

Generative approaches to statistical learning first seek to estimate $p(x|y)$, the distribution of data points belonging to each class. The probability $p(y|x)$ that a given point $x$ has label $y$ is then proportional to $p(x|y)p(y)$ by Bayes' rule. Semi-supervised learning with generative models can be viewed either as an extension of supervised learning (classification plus information about $p(x)$) or as an extension of unsupervised learning (clustering plus some labels).

Generative models assume that the distributions take some particular form $p(x|y,\theta )$ parameterized by the vector $\theta$. If these assumptions are incorrect, the unlabeled data may actually decrease the accuracy of the solution relative to what would have been obtained from labeled data alone. However, if the assumptions are correct, then the unlabeled data necessarily improves performance.

The unlabeled data are distributed according to a mixture of individual-class distributions. In order to learn the mixture distribution from the unlabeled data, it must be identifiable, that is, different parameters must yield different summed distributions. Gaussian mixture distributions are identifiable and commonly used for generative models.

The parameterized joint distribution can be written as $p(x,y|\theta )=p(y|\theta )p(x|y,\theta )$ by using the chain rule. Each parameter vector $\theta$ is associated with a decision function $f_{\theta }(x)={\underset {y}{\operatorname {argmax} }}\ p(y|x,\theta )$. The parameter is then chosen based on fit to both the labeled and unlabeled data, weighted by $\lambda$:

${\underset {\Theta }{\operatorname {argmax} }}\left(\log p(\{x_{i},y_{i}\}_{i=1}^{l}|\theta )+\lambda \log p(\{x_{i}\}_{i=l+1}^{l+u}|\theta )\right)$

Low-density separation

Another major class of methods attempts to place boundaries in regions with few data points (labeled or unlabeled). One of the most commonly used algorithms is the transductive support vector machine, or TSVM (which, despite its name, may be used for inductive learning as well). Whereas support vector machines for supervised learning seek a decision boundary with maximal margin over the labeled data, the goal of TSVM is a labeling of the unlabeled data such that the decision boundary has maximal margin over all of the data. In addition to the standard hinge loss $(1-yf(x))_{+}$ for labeled data, a loss function $(1-|f(x)|)_{+}$ is introduced over the unlabeled data by letting $y=\operatorname {sign} {f(x)}$. TSVM then selects $f^{*}(x)=h^{*}(x)+b$ from a reproducing kernel Hilbert space ${\mathcal {H}}$ by minimizing the regularized empirical risk:

$f^{*}={\underset {f}{\operatorname {argmin} }}\left(\displaystyle \sum _{i=1}^{l}(1-y_{i}f(x_{i}))_{+}+\lambda _{1}\|h\|_{\mathcal {H}}^{2}+\lambda _{2}\sum _{i=l+1}^{l+u}(1-|f(x_{i})|)_{+}\right)$

An exact solution is intractable due to the non-convex term $(1-|f(x)|)_{+}$, so research focuses on useful approximations.

Other approaches that implement low-density separation include Gaussian process models, information regularization, and entropy minimization (of which TSVM is a special case).

Laplacian regularization

Laplacian regularization has been historically approached through graph-Laplacian. Graph-based methods for semi-supervised learning use a graph representation of the data, with a node for each labeled and unlabeled example. The graph may be constructed using domain knowledge or similarity of examples; two common methods are to connect each data point to its $k$ nearest neighbors or to examples within some distance $\epsilon$. The weight $W_{ij}$ of an edge between $x_{i}$ and $x_{j}$ is then set to $e^{\frac {-\|x_{i}-x_{j}\|^{2}}{\epsilon }}$.

Within the framework of manifold regularization, the graph serves as a proxy for the manifold. A term is added to the standard Tikhonov regularization problem to enforce smoothness of the solution relative to the manifold (in the intrinsic space of the problem) as well as relative to the ambient input space. The minimization problem becomes

${\underset {f\in {\mathcal {H}}}{\operatorname {argmin} }}\left({\frac {1}{l}}\displaystyle \sum _{i=1}^{l}V(f(x_{i}),y_{i})+\lambda _{A}\|f\|_{\mathcal {H}}^{2}+\lambda _{I}\int _{\mathcal {M}}\|\nabla _{\mathcal {M}}f(x)\|^{2}dp(x)\right)$

where ${\mathcal {H}}$ is a reproducing kernel Hilbert space and ${\mathcal {M}}$ is the manifold on which the data lie. The regularization parameters $\lambda _{A}$ and $\lambda _{I}$ control smoothness in the ambient and intrinsic spaces respectively. The graph is used to approximate the intrinsic regularization term. Defining the graph Laplacian $L=D-W$ where $D_{ii}=\sum _{j=1}^{l+u}W_{ij}$ and $\mathbf {f}$ is the vector $[f(x_{1})\dots f(x_{l+u})]$, we have

$\mathbf {f} ^{T}L\mathbf {f} =\displaystyle \sum _{i,j=1}^{l+u}W_{ij}(f_{i}-f_{j})^{2}\approx \int _{\mathcal {M}}\|\nabla _{\mathcal {M}}f(x)\|^{2}dp(x)$.

The graph-based approach to Laplacian regularization is to put in relation with finite difference method.

The Laplacian can also be used to extend the supervised learning algorithms: regularized least squares and support vector machines (SVM) to semi-supervised versions Laplacian regularized least squares and Laplacian SVM.

Heuristic approaches

Some methods for semi-supervised learning are not intrinsically geared to learning from both unlabeled and labeled data, but instead make use of unlabeled data within a supervised learning framework. For instance, the labeled and unlabeled examples $x_{1},\dots ,x_{l+u}$ may inform a choice of representation, distance metric, or kernel for the data in an unsupervised first step. Then supervised learning proceeds from only the labeled examples. In this vein, some methods learn a low-dimensional representation using the supervised data and then apply either low-density separation or graph-based methods to the learned representation. Iteratively refining the representation and then performing semi-supervised learning on said representation may further improve performance.

Self-training is a wrapper method for semi-supervised learning. First a supervised learning algorithm is trained based on the labeled data only. This classifier is then applied to the unlabeled data to generate more labeled examples as input for the supervised learning algorithm. Generally only the labels the classifier is most confident in are added at each step.

Co-training is an extension of self-training in which multiple classifiers are trained on different (ideally disjoint) sets of features and generate labeled examples for one another.

In human cognition

Human responses to formal semi-supervised learning problems have yielded varying conclusions about the degree of influence of the unlabeled data. More natural learning problems may also be viewed as instances of semi-supervised learning. Much of human concept learning involves a small amount of direct instruction (e.g. parental labeling of objects during childhood) combined with large amounts of unlabeled experience (e.g. observation of objects without naming or counting them, or at least without feedback).

Human infants are sensitive to the structure of unlabeled natural categories such as images of dogs and cats or male and female faces. Infants and children take into account not only unlabeled examples, but the sampling process from which labeled examples arise.

See also

• PU learning

Sources

• Chapelle, Olivier; Schölkopf, Bernhard; Zien, Alexander (2006). Semi-supervised learning. Cambridge, Mass.: MIT Press. ISBN 978-0-262-03358-9.

External links

• Manifold Regularization A freely available MATLAB implementation of the graph-based semi-supervised algorithms Laplacian support vector machines and Laplacian regularized least squares.
• KEEL: A software tool to assess evolutionary algorithms for Data Mining problems (regression, classification, clustering, pattern mining and so on) KEEL module for semi-supervised learning.
• Semi-Supervised Learning Software Semi-Supervised Learning Software
• 1.14. Semi-Supervised — scikit-learn 0.22.1 documentation Semi-Supervised algorithms in scikit-learn .