# Local Boosting for Weakly-Supervised Learning

Rongzhi Zhang  Georgia Institute of TechnologyAtlantaGAUSA
<EMAIL_ADDRESS>,  Yue Yu  Georgia Institute of
TechnologyAtlantaGAUSA<EMAIL_ADDRESS>,  Jiaming Shen  Google ResearchNew
York CityNYUSA<EMAIL_ADDRESS>,  Xiquan Cui  The Home DepotAtlantaGAUSA
<EMAIL_ADDRESS>and  Chao Zhang  Georgia Institute of
TechnologyAtlantaGAUSA<EMAIL_ADDRESS>
(2023)

###### Abstract.

Boosting is a commonly used technique to enhance the performance of a set of
base models by combining them into a strong ensemble model. Though widely
adopted, boosting is typically used in supervised learning where the data is
labeled accurately. However, in weakly supervised learning, where most of the
data is labeled through weak and noisy sources, it remains nontrivial to
design effective boosting approaches. In this work, we show that the standard
implementation of the convex combination of base learners can hardly work due
to the presence of noisy labels. Instead, we propose LocalBoost, a novel
framework for weakly-supervised boosting. LocalBoost iteratively boosts the
ensemble model from two dimensions, _i.e., intra-source and inter-source_. The
intra-source boosting introduces locality to the base learners and enables
each base learner to focus on a particular feature regime by training new base
learners on granularity-varying error regions. For the inter-source boosting,
we leverage a conditional function to indicate the weak source where the
sample is more likely to appear. To account for the weak labels, we further
design an estimate-then-modify approach to compute the model weights.
Experiments on seven datasets show that our method significantly outperforms
vanilla boosting methods and other weakly-supervised methods.

Boosting Methods, Weak Supervision, Classification

††price: 15.00††journalyear: 2023††copyright: rightsretained††conference:
Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data
Mining; August 6–10, 2023; Long Beach, CA, USA††booktitle: Proceedings of the
29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD ’23),
August 6–10, 2023, Long Beach, CA, USA††doi: 10.1145/3580305.3599417††isbn:
979-8-4007-0103-0/23/08††ccs: Computing methodologies Boosting

##  1\. Introduction

_Weakly-supervised learning_ (WSL) has gained significant attention as a
solution to the challenge of label scarcity in machine learning. WSL leverages
weak supervision signals, such as labeling functions or other models, to
generate a large amount of weakly labeled data, which is easier to obtain than
complete annotations. Despite achieving promising results in various tasks
including text classification (Awasthi et al., 2020), sequence tagging
(Safranchik et al., 2020), and e-commerce (Zhang et al., 2022a), an empirical
study (Zhang et al., 2021a) reveals that even state-of-the-art WSL methods
still underperform fully-supervised methods by significant margins, where the
average performance discrepancy is 18.84%, measured by accuracy or F1 score.

Figure 1. Heatmap of base learner weights in model ensembles. Suffix “-FS”
indicates fully-supervised settings using clean labels and suffix “-WS”
indicates weakly-supervised settings. Each model ensemble consists of 10 base
learners, and their weights are shown by color in the heatmap.

On the other hand, boosting algorithm is one of the most commonly used
approaches to enhance the performance of machine learning models by combining
multiple base models (Freund and Schapire, 1995; Freund et al., 1996; Mason et
al., 1999; Chen and Guestrin, 2016; Rätsch et al., 2005). For example,
AdaBoost (Freund and Schapire, 1995) dynamically adjusts the importance weight
of each training example to learn multiple base models and uses a weighted
combination to aggregate these base models’ predictions. XGBoost (Chen and
Guestrin, 2016) iteratively computes the gradients and hessians defined on a
clean training set to fit base learners and combines their predictions via
weighted summation. Despite the encouring performance, these boosting
algorithms usually assume the availability of a clean labeled dataset. In WSL,
however, the imperfect supervision signals interfere with the training data
importance reweighting which further prevents us from computing an accurate
weight of each base learner. If we naively apply these supervised boosting
methods using a weakly labeled dataset, we observe a phenomenon called “
_weight domination_ ” where the assigned weight of the initial base model is
too large and dominates the ensemble model prediction, as shown in Figure 1.

A key challenge of adapting boosting methods to the WSL setting is to
accurately compute the importance of each example in the weakly labeled
training data for each base learner. Previously, when a clean dataset is
provided, the goal of data importance reweighing process is to prioritize
instances with large errors for subsequent base learner training. This
effectively localizes the base learner to the error region in the label space.
However, in WSL, the noisy labels hinder the accurate identification of error
instances and thus we need to shift our focus from the label space to the
training data space. One potential approach is to partition the weakly-labeled
training data into subsets and constructs a mixture of expert models (MoE)
(Jacobs et al., 1991) where each expert is localized for one training data
subset. Along this line, Tsai et al. (2021) propose partitioning the unlabeled
dataset into latent semantics subsets and using multiple expert models to
discriminate instances. However, this approach assumes the input data
naturally reside in a homogeneous feature space and requires a hyper-parameter
search to appropriately localize the expert models. Additionally, the off-the-
shelf clusters do not adapt during the learning process, which conflicts with
the philosophy of boosting methods.

We investigate the problem of boosting in the context of weakly supervised
learning, where most of the data are labeled by weak sources and only a
limited number of data points have accurate labels. To address the
difficulties posed by this setting, we introduce LocalBoost, a novel iterative
and adaptive framework for WSL boosting. LocalBoost retains the essential
concepts of the traditional boosting approach while incorporating adaptations
specifically designed for the WSL scenario, described as follows:

  * •

_Base Learner Locality_. Motivated by the challenges posed by the data
reweighting approach in AdaBoost for WSL and the limitations of hard
clustering in MoE methods, we propose a new approach to base learner
localization. In AdaBoost, large-error instances are assigned with larger
weights for model training, however, this approach does not account for the
fact that error instances exist in multiple feature regimes that are difficult
to capture with weak labels. Additionally, the rigid clusters and fixed expert
models in MoE cannot adapt in the iterative learning process, hindering the
framework’s ability to dynamically target weak feature regimes and build upon
preceding models. To address these issues, our proposed framework LocalBoost
assigns base learners to adaptively updated local regions in the embedding
space, thereby introducing locality to the base learners.

  * •

_Two-dimension Boosting_. Effective aggregation of localized base learners in
WSL goes beyond the simple convex combination in supervised settings (as shown
in Sec. 4.2). To account for potential label noises from weak sources, we aim
to learn multiple complementary base learners in LocalBoost. To fulfill this
goal, we introduce a weighting function to compute the conditional probability
of weak sources that are more likely to annotate a given data instance. We
further design a two-dimensional boosting framework in LocalBoost, where
inter-source boosting and intra-source boosting are performed alternately. The
former improves the base learners within a given weak source, while the latter
complements the base learners with additional models trained from other weak
sources.

  * •

_Interactions between Weak and Clean Labels_. We incorporate the interactions
between weak and clean labels into LocalBoost framework in two steps: (1) We
compute a mapping between the small clean dataset and the large weakly labeled
dataset to localize base learners in the data embedding space. We first
identify the errors made by the current model ensemble, and then sample
corresponding clusters from the large weak dataset to form the training set
for the next base learner. (2) We propose a novel estimate-then-modify
approach for computing base learner weights. Initially, the weights are
estimated on the large weakly labeled dataset. Then, we refine these estimates
by generating multiple perturbations of the model weights and selecting the
one that results in the lowest error rate on the small clean dataset as the
modified weights.

We evaluate LocalBoost on seven datasets including sentiment analysis, topic
classification and relation classification from WRENCH (Zhang et al., 2021a),
the standard benchmark for weakly supervised learning. The results indicate
that LocalBoost achieves superior performance compared with other state-of-
the-art methods. Moreover, our analysis further confirms the effectiveness of
boosting in two dimensions and incorporating interactions between weak and
clean labels. We summarize our key contributions as follows:

  1. (1)

We present LocalBoost111The implementation is available at
https://github.com/rz-zhang/local_boost, a novel weakly-supervised boosting
framework that implements progressive inter-source and intra-source boosting.

  2. (2)

We incorporate explicit locality into the base learners of the boosting
framework, allowing them to specialize in finer-grained data regions and
perform well in specific feature regimes.

  3. (3)

We leverage the interactions between weak and clean labels for effective base
learner localization and weight estimation.

  4. (4)

We conduct extensive experiments on seven benchmark datasets and demonstrate
the superiority of LocalBoost over WSL and ensemble baselines.

##  2\. Related Work

Weakly Supervised Learning. Weakly supervised learning (WSL) focuses on
training machine learning models with a variety of weaker, often programmatic
supervision sources (Zhang et al., 2021a). Specifically, in WSL, users provide
_weak supervision sources_ , e.g., heuristics rules (Zhuang et al., 2022; Xu
et al., 2023), knowledge bases (Hoffmann et al., 2011), and pre-trained models
(Smith et al., 2022; Yu et al., 2023; Zhang et al., 2022b), in the form of
_labeling functions (LFs)_ , which provide labels for some subset of the data
to create the training set.

The main challenge in WSL is incorrect or conflicting labels produced by
labeling functions (Zhang et al., 2022c). To address this, recent research has
explored two solutions. The first is to create label models, which aggregate
the noisy votes of labeling functions using different dependency assumptions.
This approach has been used in various studies, including (Ratner et al.,
2017, 2019; Fu et al., 2020; Zhang et al., 2022d; Stephan et al., 2022). The
second solution involves designing end models that use noise-robust learning
techniques to prevent overfitting to label noise, as seen in studies by (Yu et
al., 2021; Wu et al., 2020; Li and Zhang, 2021). This current work belongs to
the first category.

For label models, several recent works attempt to better aggregate the noisy
labeling functions via better modeling the distribution between LF and ground
truth labels (Ratner et al., 2019; Fu et al., 2020), Zhang et al. (2022d)
incorporate the instance features with probabilistic models, while (Rühling
Cachay et al., 2021; Ren et al., 2020; Sam and Kolter, 2022) learn the label
aggregation using supervision from the target task. Besides, (Safranchik et
al., 2020; Shin et al., 2022; Wu et al., 2022) adapt the WSL to a broader
range of applications such as regression and structural prediction, and (Zhang
et al., 2020; Biegel et al., 2021; Yu et al., 2022a, b) design active learning
approaches to strategically solicit human feedbacks to refine weak supervision
models.

So far, only a few works have attempted to integrate the boosting or ensemble
methods with WSL. Guan et al. (2018) learn an individual weight for each
labeler and aggregate the prediction results for prediction. Zhang et al.
(2022b) leverage boosting-style ensemble strategy to identify difficult
instances and adaptively solicit new rules from human annotators and Zhang et
al. (2022a) leverage rules from multiple views to further enhance the
performance. Very recently, Zhao et al. (2022) use mixture-of-experts (MoE) to
route noisy labeling functions to different experts for achieving specialized
and scalable learning. However, these works directly combine existing
ensembling techniques with noisy labels. Instead, we first identify the key
drawback of adopting boosting for WSL (Fig. 1) and then design two-dimension
boosting to resolve this issue, which provides a more effective and flexible
way for learning with multi-source weak labels.

Boosting. The boosting methods are prevailing to improve machine learning
models via the combination of base learners. Research in this area begins in
the last century (Freund and Schapire, 1995) and numerous variants have been
proposed (Breiman, 1999; Mason et al., 1999; Friedman, 2001; Chen and
Guestrin, 2016). AdaBoost (Freund and Schapire, 1995) incorporates base
learners to the model ensemble via iterative data reweighting and model
weights computation that minimizes the total error on the training set, to
improve the model ensemble for binary classification. XGBoost (Chen and
Guestrin, 2016) presents an advanced implementation of boosting by using a
more regularized model formalization to control over-fitting, and it has the
virtue of being accurate and fast. However, these methods are discussed in the
context of fully-supervised learning, and their principal derivation or
implementation relies on clean data. This results in issues with its adaption
to weakly-supervised settings as it is challenging to obtain reliable
computation from weakly labeled data.

Recent works explore multi-class boosting (Brukhim et al., 2021; Cortes et
al., 2021a) and the application side of boosting (Zhang et al., 2022e; Huang
et al., 2018; Nitanda and Suzuki, 2018; Suggala et al., 2020). Brukhim et al.
(2021) study the resources required for boosting and present how the learning
cost of boosting depends on the number of classes. Zhang et al. (2022e)
explore boosting in the context of adversarial robustness and propose a robust
ensemble approach via margin boosting. For the application with deep neural
networks, Taherkhani et al. (2020) integrate AdaBoost with a convolutional
neural network to deal with the data imbalance. Among these works, the most
related one to ours is MultiBoost (Cortes et al., 2021a), where the authors
study boosting in the presence of multiple source domains. They put forward a
Q-ensemble to compute the conditional probability of different domains given
the input data. This formulation can be traced back to multi-source learning
in fully supervised settings (Mansour et al., 2008; Hoffman et al., 2018;
Cortes et al., 2021b). In this work, we draw inspiration from such formulation
and present an adaptation to the WSL setting – we design a weighting function
to compute the conditional probability of weak sources. In this way, we
modulate the base learners to highly relevant weak sources and present a two-
dimension boosting accordingly.

##  3\. Preliminaries

Let $\mathcal{X}$ denote the input space and $\mathcal{Y}=\\{1,\cdots,C\\}$
represent the output space, where $C$ is the number of classes. We have a
large weakly labeled dataset $\mathcal{D}_{l}$ and a small clean dataset
$\mathcal{D}_{c}$. The weak labels of $\mathcal{D}_{l}$ are generated by a set
of weak sources $\mathcal{R}$, and the number of weak sources
$|\mathcal{R}|=p$.

###### Definition 3.1 (Weak sources).

In the context of WSL, the weak sources refer to labeling functions (LFs),
which are constructed via keywords or semantic rules. In this work, we will
use the term “weak source” and “labeling function” interchangeably. Given an
unlabeled data sample $\boldsymbol{x}_{u}$, a weak source $r(\cdot)$ maps it
into the label space: $r(\boldsymbol{x}_{u})\rightarrow
y\in\mathcal{Y}\cup\\{0\\}$. Here $\mathcal{Y}$ is the original label set for
the task and $\\{0\\}$ is a special label indicating $\boldsymbol{x}_{u}$ is
unmatchable by $r(\cdot)$. Given a set of $N$ samples and $p$ labeling
functions, we can obtain a LF matching matrix $A_{N\times p}$, where each
entry $a_{i,j}\in\\{0,1\\}$ denotes whether the $i$-th sample is matched by
the $j$-th LF.

###### Definition 3.2 (Base learner).

Let $S=\left\\{\left(\mathbf{x}_{i},y_{i}\right)\right\\}_{i=1}^{n}$ be $n$
i.i.d samples drawn from IP, and $\text{I\kern-1.49994ptP}_{n}$ be the
empirical distribution of $\mathcal{S}$. We let
$h:\mathcal{X}\rightarrow\mathcal{Y}$ denote a base learner that predicts the
label of $\mathbf{x}$ as $h(\mathbf{x})$. For a base learner $h$ and a
distribution $\mathcal{S}$, we denote the expected loss of $h$ as
$\mathcal{L}(\mathcal{S},h)=\mathbb{E}_{(x,y)\sim\mathcal{S}}[\ell(h(x),y)]$,
where $\ell$ is cross entropy loss.

###### Definition 3.3 (Ensemble).

Let $\mathcal{H}$ be the set of base learners, and
$h:\mathcal{X}\rightarrow\mathcal{Y},\forall h\in\mathcal{H}$. In ensembling,
we place a probability distribution $\text{I\kern-1.49994ptP}_{q}$ over
$\mathcal{H}$ to assign weights of base learners. It leads to a score-based
base learner
$h_{\text{I\kern-1.04996ptP}_{q}}:\mathcal{X}\rightarrow\mathbb{R}^{C}$ with
$\left[h_{\text{I\kern-1.04996ptP}_{q}}(\mathbf{x})\right]_{j}=\mathbb{E}_{h\sim{\text{I\kern-1.04996ptP}_{q}}}[\mathbb{I}(h(\mathbf{x})=j)]$,
and we convert it into a base learner in the form of a standard classifier
with the argmax function:
$f(\mathbf{x})=\operatorname{argmax}_{j\in\mathcal{Y}}\left[h_{\text{I\kern-1.04996ptP}_{q}}(\mathbf{x})\right]_{j}$.
Given the score-based $\mathcal{H}_{f}=\left\\{f_{1},f_{2},\ldots\right\\}$,
where $f:\mathcal{X}\rightarrow\mathbb{R}^{C},\forall f\in\mathcal{H}_{f}$, we
can have a convex combination of the base learners via a set of real-valued
weights $W$ over $\mathcal{H}_{f}$, and define the weighted ensemble $F$ as
$F_{j}(\mathbf{x})=\sum_{f\in\mathcal{H}_{f}}W(f)f_{j}(\mathbf{x})$, where
$W(f)\in\mathbb{R}$ is the weight of the base learner $f$.

##### Problem Formulation.

Given a large weakly labeled dataset $\mathcal{D}_{l}$, a small clean dataset
$\mathcal{D}_{c}$, and $p$ weak sources, we aim to iteratively obtain base
learners $f_{j}$ to boost the performance of the ensemble model
$F_{j}(\mathbf{x})=\sum_{f\in\mathcal{H}_{f}}W(f)f_{j}(\mathbf{x})$.

##  4\. Methodology

###  4.1. Learning Procedure Overview

LocalBoost iteratively implements inter-source boosting and intra-source
boosting in the WSL setting. For weak source $l:1,\cdots,p$ and iteration
$t:1,\cdots,T$, we have a base learner $f_{t,l}(x)$ with a model weight
$\alpha_{t,l}$. As we will illustrate in Sec. 4.2, the straightforward convex
combination may not work for the WSL setting. To this end, we introduce a
conditional probability function $Q(l|x)$ to account for the fact that the
weak labels are generated from different weak sources. For a given sample
$\mathbf{x}$, the base learners from the weak source where $\mathbf{x}$ is
more likely to be labeled are allocated higher weights in the voted
combination.

Given a large weakly labeled dataset $\mathcal{D}_{l}$ and a small clean
dataset $\mathcal{D}_{c}$, the overall learning procedure runs as follows: In
iteration $(t,l)$, the preceding ensemble model $F_{t-1,l}(\mathbf{x})$ or
$F_{t,l-1}(\mathbf{x})$ accumulated errors on $\mathcal{D}_{c}$, say the
large-error instances are $s_{1},\cdots,s_{k}$. Then we sample $k$ clusters
$S_{1},\cdots,S_{k}$ in $\mathcal{D}_{l}$ near $s_{1},\cdots,s_{k}$, these
clusters form a training set $\mathcal{S}_{t,l}=\\{S_{1},\cdots,S_{k}\\}$ for
the base learner $f_{t,l}(\mathbf{x})$ and we fit $f_{t,l}(\mathbf{x})$ on
$\mathcal{S}_{t,l}$. Next, we estimate the model weights $\alpha_{t,l}$ on
$\mathcal{D}_{l}$ and modify it on $\mathcal{D}_{c}$. After $T$ iterations, we
obtain the final ensemble:

(1) $F(x)=\sum_{t=1}^{T}\sum_{l=1}^{p}\alpha_{t,l}\mathrm{Q}(l\mid
x)f_{t,l}(x).$

The key components presented in the above model ensemble, including the model
weights $\alpha_{t,l}$, the conditional function $Q(l|x)$, and the local base
learner $f_{t,l}(x)$, are specially designed for the WSL setting. Different
from the formulation of Adaboost (Freund and Schapire, 1995) and Q-ensemble
(Cortes et al., 2021a, b) that are solely based on the clean labels,
LocalBoost relieves such reliance on fully accurate supervision via the
interaction between weak labels and clean labels, and localizes the base
learners to adaptively complement the preceding ensemble.

Algorithm 1 Pseudo-code of LocalBoost Framework

Large weakly-labeled dataset $\mathcal{D}_{l}$, Small clean dataset
$\mathcal{D}_{c}$, $p$ weak sources, Source-index dataset $D_{s}$

$\triangleright$ Initialization

Learn $Q(l|x)$ on $\mathcal{D}_{s}$ (Sec. 4.2)

Fit $f_{1,1}$ on $\mathcal{D}_{l}$, $\alpha_{1,1}\leftarrow 1$

$F_{1,1}(x)\leftarrow\alpha_{1,1}Q(l|x)f_{1,1}(x)$

for $t=1$ $\leftarrow$ $T$ do $\triangleright$ Intra-source boosting

for $l=1$ $\leftarrow$ $p$ do $\triangleright$ Inter-source boosting

$F_{t,l}(x)$ inference on $\mathcal{D}_{c}$

$\triangleright$ Localize the base learner (Sec. 4.3)

Identify the large-error instances $s_{1},\cdots,s_{k}$ on $\mathcal{D}_{c}$

Sample $k$ clusters $S_{1},\cdots,S_{k}$ on $\mathcal{D}_{l}$ based on
$s_{1},\cdots,s_{k}$

Fit $f_{t,l}(x)$ on $\mathcal{D}_{t,l}=\\{S_{1}\cup\cdots\cup S_{k}\\}$

$\triangleright$ Weights estimate and correction Sec. 4.4)

Estimate $\alpha_{t,l}$ on $\mathcal{D}_{l}$

Generate a group of perturbed
$\mathbf{v}_{t,l}=[\alpha_{1,1},\cdots,\alpha_{t,l}]$

Normalize each of them

Select
$\operatorname*{arg\,min}_{\mathbf{v}_{t,l}\in\mathcal{V}_{t,l}}\operatorname{err}_{\mathcal{D}_{c}}$
as the corrected weight

$\triangleright$ Update the ensemble

$F_{t,l}(x)=\sum_{t}\sum_{l}\alpha_{t,l}\mathrm{Q}(l\mid x)f_{t,l}(x)$

end for

end for

return Ensemble model $F(x)$

The learning algorithm is presented in Algorithm 1. In the initialization
stage, we prepare a source-index dataset $\mathcal{D}_{s}$ using the LF
matching matrix (Sec. 4.2) to learn the conditional function, and fit the
first base learner on the large weakly labeled dataset $\mathcal{D}_{l}$. Then
we iteratively perform the two-dimension boosting. The inner loop over $p$
weak sources corresponds to the inter-source boosting, while the outside loop
over $T$ iterations corresponds to the intra-source boosting. In each
iteration $(t,l)$, we start from the ensemble inference on $\mathcal{D}_{c}$
to identify the accumulated large-error instances $s_{1},\cdots,s_{k}$. These
error instances based on the ground-truth labels can accurately reflect the
feature regimes where the current ensemble performs poorly.

Fig. 2 presents an illustrative visualization of the base learner
localization. To localize the subsequent base learners, we sample $k$ clusters
from the large weakly labeled dataset $\mathcal{D}_{l}$ based on the
identified large-error instances $s_{1},\cdots,s_{k}$. In other words, these
instances from $\mathcal{D}_{c}$ guide the localization of the base learner
via a mapping between the instances on the small clean dataset and the regions
on the large weakly labeled dataset. To complement the previous ensemble, we
fit the new base learner $f_{t,l}(x)$ on the dataset $\mathcal{D}_{t,l}$
consisting of instances from clusters $S_{1},\cdots S_{k}$.

For the model weights computation, we propose an estimate-then-modify paradigm
(as shown in Fig. 3) to leverage both the weak labels and clean labels. On the
large weak dataset $\mathcal{D}_{l}$, we retain the AdaBoost principles to
compute the weighted error and yield an estimate of $\alpha_{t,l}$.
Considering the labels are obtained from weak sources, the estimated
$\alpha_{t,l}$ on $\mathcal{D}_{l}$ can hardly guarantee the boosting
progress, so we further modify it on the small clean validation dataset
$\mathcal{D}_{c}$. Specifically, we generate a group of the _perturbed_ weight
vectors $\mathcal{V}_{p}=\\{\mathbf{v}_{t,l}\\}^{n_{p}}$ and compute the
weighted error on $\mathcal{D}_{c}$. Among the perturbations, we select the
one that achieves the lowest error as the modified model weights.

In the following sections, we will first introduce the conditional function
designed for the weak sources (Section 4.2), then illustrate how we introduce
locality to base learners (Section 4.3), and finally discuss the estimate-
then-modify paradigm for the computation of the model weights in WSL settings
(Section 4.4).

###  4.2. Conditional Function for Weak Sources Localization

In the WSL setting, the weak labels are generated by weak sources such as
labeling functions. We first pinpoint that the standard convex combination of
the base learners can lead to a poor ensemble without taking the weak sources
into account. Being aware of this, we propose to use a conditional function to
account for the weak sources. Given an input instance, the conditional
function represents the probability of the instance being labeled by each weak
source. In this way, the ensemble model is modulated by this conditional
function, while being weighted by a series of base learner weights, to deal
with the weak sources in the WSL setting.

###### Proposition 1.

There exist weak sources $LF_{1}$ and $LF_{2}$ with corresponding
distributions $\mathcal{D}_{1}$ and $\mathcal{D}_{2}$, and base learners
$f_{1}$ and $f_{2}$ with $\mathcal{L}\left(\mathcal{D}_{1},f_{1}\right)=0$ and
$\mathcal{L}\left(\mathcal{D}_{2},f_{2}\right)=0$ such that

(2)
$\forall\alpha\in[0,1],\quad\mathcal{L}\left(\frac{1}{2}\left(\mathcal{D}_{1}+\mathcal{D}_{2}\right),\alpha
f_{1}+(1-\alpha)f_{2}\right)\geq\frac{1}{2},$

where $\alpha$ is the model weights in the ensemble, $\mathcal{L}()$
quantifies the loss.

The proof is given in Appendix C.

The above proposition states that even if the base learner fits well to the
weakly labeled data provided by the weak sources, the convex combination of
them can still perform poorly. Therefore, we consider the new ensemble form to
account for the presence of weak sources. Inspired by (Mansour et al., 2008;
Hoffman et al., 2018; Zhang et al., 2021b; Cortes et al., 2021a, b), we
introduce a conditional function to compute the probability of the sample
being labeled by each weak source. The major difference is that the mentioned
works discuss the conditional probability in the context of domain adaption or
multi-source learning and are designed for the fully supervised settings, we
instead present a conditional function to account for the weak sources in the
WSL settings to modulate the base learners, and naturally introduce the inter-
source boosting.

###### Proposition 2.

By plugging a conditional function regarding the weak sources into the
standard convex combination, there exists an ensemble in the WSL setting such
that

(3) $\mathcal{L}\left(\mathcal{D}_{\lambda},\left(\alpha\mathbf{Q}(l\mid
x)f_{1}(x)+(1-\alpha)\mathbf{Q}(l\mid x)f_{2}(x)\right)\right)=0,$

where $\mathcal{D}_{\lambda}$ is a mixture of the weak sources such that
$\mathcal{D}_{\lambda}=\sum_{k=1}^{p}\lambda_{k}\mathcal{D}_{k}$,
$\sum_{k=1}^{p}\lambda_{k}=1$, and $\forall k\in[p],\lambda_{k}>0$.

###### Proof.

Consider the case of conditional function indicating the matching between the
samples and the weak sources:

(4) $Q(LF_{1}|x_{1})=Q(LF_{2}|x_{2})=1,\quad
Q(LF_{2}|x_{1})=Q(LF_{1}|x_{2})=0.$

Plug it into the standard convex combination, we get the ensemble as

(5) $F(x)=\sum_{i}\alpha Q(l|x)f_{i}(x).$

Then the ensemble admits no loss for the case mentioned in Prop. 1:

(6) $\displaystyle\forall\alpha\in[0,1],$
$\displaystyle\mathcal{L}\left(\frac{1}{2}\left(\mathcal{D}_{1}+\mathcal{D}_{2}\right),F(x)\right)$
$\displaystyle=$ $\displaystyle\frac{1}{2}\mathbb{I}(\alpha Q(1\mid
x_{1})f_{1}(x_{1})+(1-\alpha)Q(2\mid x_{1})f_{2}(x_{1}))$ $\displaystyle+$
$\displaystyle\frac{1}{2}\mathbb{I}(\alpha Q(1\mid
x_{2})f_{1}(x_{2})+(1-\alpha)Q(2\mid x_{2})f_{2}(x_{2}))=0.$

This can be extended to a general mixture of weak sources as

(7) $\displaystyle\mathcal{L}\left(\mathcal{D}_{\lambda},F(x)\right)$
$\displaystyle=\left(\lambda\mathbb{I}\left(F\left(x_{1}\right)\leq
0\right)+(1-\lambda)\mathbb{I}\left(-F\left(x_{2}\right)\leq 0\right)\right)$
$\displaystyle=\lambda(\mathbb{I}(\alpha\leq
0)+(1-\lambda)\mathbb{I}((1-\alpha)\leq 0))=0.$

∎

In practice, we use an MLP to learn the conditional function on a source-index
dataset $\mathcal{D}_{s}$ using the instance features. Given $p$ weak sources
and $N_{l}$ unlabeled data, we can easily construct a matching matrix in the
shape of $N_{l}\times p$ to represent the matching results, where each entry
takes a binary value from $\\{0,1\\}$ to indicate if it gets matched with a
specific weak source. For the $p$ weak sources, we have
$\sum_{l=1}^{p}Q(l|x)=1$.

In the inference stage, the advantage of the learned conditional function is
more evident compared to the direct LF matching. As a straightforward
substitution of the learned conditional function, we can implement an LF
matching for each test sample to modulate the base learners to specific weak
sources. The major problem with such a hard matching is the potential labeling
conflict among multiple LFs, as it is often quite challenging to identify the
correct labeling functions based on the voting or aggregation (Ratner et al.,
2017, 2019) approaches with matching matrix only. For the learned conditional
function, it can generalize better than the hard matching after training on
the source-index dataset. By the output of a probability vector, it assigns
different weights to the base learners according to their source relevance and
thus enables better modulating.

###  4.3. Base Learner Localization

Figure 2. An illustrative example of base learner localization on a 2D plane.
To localize the base learner $f_{t,l}(x)$, we first implement an ensemble
inference on the clean dataset $\mathcal{D}_{c}$ to identify $k$ large error
instances $s_{1},\cdots,s_{k}$. Next, we sample $k$ clusters
$S_{1},\cdots,S_{k}$ on the weakly labeled dataset $\mathcal{D}_{l}$. Then the
base learner $f_{t,l}(x)$ is trained on the local regions consisting of
$S_{1},\cdots,S_{k}$. Here we emphasize the clean dataset $\mathcal{D}_{c}$ is
only for validation use. It guides the base learner localization but is not
involved in the training. This figure takes $F_{t,l-1}(x)$ as the preceding
ensemble, it could also be $F_{t-1,l}(x)$ when the loop over $p$ weak sources
is completed.

The core idea of LocalBoost is to allocate the base learners to local regions
in the input embedding space. To illustrate this point clearly, we present a
2D visualization in Fig. 2. Such a locality differs from both the focus on
large-error data in supervised boosting which does not explicitly account for
information from feature space and the task-agnostic pre-clustering in the MoE
approach. For _traditional boosting approaches_ such as AdaBoost, the learning
framework iteratively computes the weighted error and each base learner is
trained on a reweighted training set. The issues are two folds for the WSL
setting: 1) First, there are not enough clean data and the noisy labels in the
weakly labeled dataset cannot underpin an accurate estimation of the weighted
error. 2) Second, the base learner is granted access to the entire training
set. Although the training set has been reweighted to emphasize the
accumulated errors, the imperfect weak labels from multiple feature regimes
poses specific challenges for base learner fitting, as the boosted model is
still easy to overfit the noise. For the _MoE approach_ , although it
constructs clusters in the embedding space and deploys expert models to learn
specialized patterns, the clusters are often assigned in a static way with
instance features (Yu et al., 2022c). Such a rigid scheme fails to explicitly
model the training dynamics of the existing base learners, often resulting in
suboptimal performance.

To this end, we harness the small, clean validation set to guide the
localization of the base learners to introduce locality for these base
learners via a mapping between the error instance and the error regions. We
first identify the large-error instances on the small clean dataset
$\mathcal{D}_{c}$, then sample clusters on $\mathcal{D}_{l}$ based on the
identified instances. Denote the model ensemble at iteration $(t,l)$ as
$F_{t,l}(x)$, and its prediction vector as $\mathcal{G}(F_{t,l}(x))$. We
maintain an error matrix $m_{t,l}$ to record the accumulated error, which is
initialized as $m_{t,l}\leftarrow[0]^{N_{c}}$ at the beginning, where
$N_{c}=|\mathcal{D}_{c}|$. By the ensemble inference on $\mathcal{D}_{c}$, we
update $m_{t,l}$ as

(8) $m_{t,l}\leftarrow
m_{t,l}+[1]^{N_{c}}-\mathbf{y}^{T}\mathcal{G}(F_{t,l}(x)),$

so the entries with accumulated errors get larger in the iterative process.
Then we pick the top-$k$ error instances by

(9)
$\\{s_{j_{1}},\cdots,s_{j_{k}}|\operatorname*{arg\,max}_{j_{1},\cdots,j_{k}\in
N_{c}}\sum_{j}^{j_{1},\cdots,j_{k}}[m_{t,l}]_{j}\\}.$

Based on these identified error instances, we back to $\mathcal{D}_{l}$ and
sample $k$ clusters with a hyper-radius inversely proportional to the
accumulated error:

(10) $\forall s_{j}\in\\{s_{j_{1}},\cdots,s_{j_{k}}\\},\quad
S_{j}=\\{x|\|x-s_{j}\|\leq c_{1}d/[m_{t,l}]_{j}\\},$

where $c_{1}$ is a parameter, $d$ is the average distance of all data samples
in $\mathcal{D}_{l}$:

(11) $d=\frac{2}{N_{l}(N_{l}-1)}\sum_{p}\sum_{q}\|x_{p}-x_{q}\|,\quad p\neq
q.$

In this way, we form a training set

(12) $\mathcal{D}_{t,l}=S_{1}\cup\cdots\cup S_{k},$

which is the _local region_ for the fitting of the to-be-added base learner
$f_{t,l}$. We deploy the base learner $f_{t,l}$ to the local region
$\mathcal{D}_{t,l}$ and fit it on $\mathcal{D}_{t,l}$ by optimizing:

(13)
$\min_{\theta}\frac{1}{\left|\mathcal{D}_{t,l}\right|}\sum\limits_{\left(\boldsymbol{x}_{i},\hat{y}_{i}\right)\in\mathcal{D}_{t,l}}\ell_{\operatorname{CE}}\left(f_{t,l}(\boldsymbol{x}_{i}),\hat{y}_{i}\right),$

where $\hat{y}_{i}$ is the weak label for instance $\boldsymbol{x}_{i}$, and
$\ell_{\operatorname{CE}}$ is the cross entropy loss.

The above process reflects the interactive nature of LocalBoost, _i.e.,_ the
error instances identified on the clean dataset guide the base learner
training on the weakly labeled dataset. If we use the clean dataset alone, the
limited number of samples are insufficient to support the model fitting
(Brukhim et al., 2021). If we use the weakly labeled dataset alone, we cannot
distinguish the false positive when updating the error matrix due to the
presence of noisy labels. Instead, our approach first accurately identifies
the large-error instances on the small clean dataset $\mathcal{D}_{c}$, then
sample regions on the large weakly labeled dataset $\mathcal{D}_{l}$ based on
these instances to gather sufficient supervision for the base learner
training. Compared to the data reweighting approach in supervised boosting
(Freund and Schapire, 1995), LocalBoost targets only local regions in each
iteration so that the base learners can be trained on more specific feature
regimes, which is suitable for WSL setting because it is more difficult to
directly learn from the imperfect noisy labels. Besides, LocalBoost explicitly
inherits the boosting philosophy compared to the MoE approach–the local
regions evolve iteratively and adaptively to reflect the weakness of the
preceding ensemble, thereby the new base learner serves as a complement.

###  4.4. Estimate-then-Modify Weighting Scheme with Perturbation

Figure 3. The illustration of Estimate-then-Modify scheme for model weight
calculation. We first estimate the base learner weight $\alpha_{t,l}$ on
$\mathcal{D}_{l}$ and form the new ensemble $F_{t,l}(x)$. Next, we generate a
group of perturbed weight vectors $\mathcal{V}_{t,l}$ by adding Gaussian and
normalizing each of them. Finally, we select the weight vector that achieves
the lowest total error on $\mathcal{D}_{c}$.

For the weight computation, we present an adaptive design for boosting in the
WSL setting, namely the _estimate-then-modify_ paradigm. In supervised
boosting, it is easy to compute the model weights by the principle of
minimizing the total error. This implementation builds upon access to a full
clean dataset. In WSL, however, we only have a large weakly labeled dataset,
along with a clean validation dataset with only limited examples. Therefore,
we propose an estimate-then-modify paradigm for the model weights computation,
in which a large number of weak labels are leveraged for the weight estimate,
then the limited clean labels are used to rectify the estimated weights.

In particular, we first follow the AdaBoost procedure to estimate the weight
$\alpha_{t,l}$ on the weakly labeled dataset $\mathcal{D}_{l}$, this starts
from the data weights initialization on $\mathcal{D}_{l}$:

(14) $w_{i}=1/N_{l},i=1,2,\cdots,N_{l},$

where $N_{l}=|\mathcal{D}_{l}|$. Then we calculate the weighted error rate of
the current base learner $f_{t,l}$ by

(15)
$\operatorname{err}_{\mathcal{D}_{l}}=\sum_{i}^{N_{l}}w_{i}\mathbb{I}\left(y_{i}\neq
f_{t,l}(x_{i})\right).$

It follows the weight calculation of $\alpha_{t,l}$ for the base learner
$f_{t,l}$:

(16)
$\alpha_{t,l}=\log\frac{1-\operatorname{err}_{\mathcal{D}_{l}}}{\operatorname{err}_{\mathcal{D}_{l}}}.$

This expression is based on the principle that given the to-be-added base
learner, the desired weight should minimize the total error defined on the
training set $\mathcal{D}_{l}$. Finally, we update the data weights:

(17) $w_{i}\leftarrow w_{i}\cdot e^{\alpha_{t,l}\mathbb{I}\left(y_{i}\neq
F_{t,l}\left(\boldsymbol{x}_{i}\right)\right)},i=1,2,\ldots,N_{l},,$

and normalize it such that $\sum_{i}w_{i}=1$. Till now, we have obtained an
estimated weight of the base learner, the ensemble model can be updated by:

(18) $\displaystyle F_{t,l}(x)=F_{t,l-1}(x)+\alpha_{t,l}Q(l|x)f_{t,l}(x),\quad
l>1$ or $\displaystyle
F_{t,l}(x)=F_{t-1,l}(x)+\alpha_{t,l}Q(l|x)f_{t,l}(x),\quad t>1$

Note that in the above derivation, we directly use the weak labels in
$\mathcal{D}_{l}$ for the error rate computation and the total error
minimization. However, one key difference for weakly-supervised learning is
the absence of a large amount of clean labels. Merely using the noisy weak
labels can hardly guarantee the boosting progress due to the fact that
calculating error rates involves weak labels, which are less unreliable and
can negatively affect the weight estimation.

To address this issue, we further calibrate such estimated weights using the
small clean dataset $\mathcal{D}_{c}$ with a perturbation-based approach.
Specifically, for the iteration $(t,l)$, we have the weight vector
$\mathbf{v}_{t,l}=[\alpha_{1,1},\cdots,\alpha_{t,l}]$. We then add Gaussian
perturbation to the weight vector by

(19)
$\forall\alpha_{i,j}\in\mathbf{v}_{t,l},\quad\alpha_{i,j}\leftarrow\alpha_{i,j}+\tilde{\alpha},\quad\textit{s.t.,}\quad\tilde{\alpha}\sim\mathcal{N}(\mu,\sigma^{2}),$

and normalize the sum of weights to 1 for getting a group of perturbed weight
vectors $\mathcal{V}_{t,l}=\\{\mathbf{v}_{t,l}\\}^{n_{p}}$, where $n_{p}$ is
the number of perturbations.

The $\mathcal{V}_{t,l}$ enables us to validate different combinations of the
base learners. We define the clean error on the small clean dataset
$\mathcal{D}_{c}$ as

(20)
$\operatorname{err}_{\mathcal{D}_{c}}=\sum_{i}^{N_{c}}\exp(-y_{i}F_{t,l}\left(x_{i}\right)),$

where $y_{i}$ is the clean label on $\mathcal{D}_{c}$, and
$N_{c}=|\mathcal{D}_{c}|$. We select the weight vector with the lowest
validation error (Zhang et al., 2023)

(21)
$\mathbf{v}_{t,l}=\operatorname*{arg\,min}_{\mathbf{v}_{t,l}\in\mathcal{V}_{t,l}}\operatorname{err}_{\mathcal{D}_{c}}$

as the modified base learner weights.

The weights computation for the base learners manifests another aspect of the
interaction between weak labels and clean labels. There are two natural
alternatives to compute the weights, either using the weak labels or the clean
labels alone. We have demonstrated that using only weak labels is suboptimal
due to the unreliable computation caused by the noise in the weak labels. On
the other hand, if we use clean labels alone, the base learner can easily
overfit on the limited number of samples. Another alternative is to integrate
both the weak labels and clean labels by fitting the base learner on the
weakly labeled dataset, while computing the weights using the clean labels.
However, we argue that the error made on the clean dataset could be caused
either by the distribution shifts between the weak labels and the clean labels
due to the limited and biased labeling functions, or by the base learner
overfitting to the label noise. If we decouple the two steps of base learner
fitting and weight computation, it equivalently forces the boosting process to
the clean dataset only. This ignores the fact that an ensemble well-performed
on a large dataset, though weakly labeled, can generalize better than an
overfitted one. We empirically validate the above statement in Sec. 5.5.

##  5\. Experiments

Table 1. Main Results. ∗: Results are copied from the corresponding paper.

| IMDb (Acc.) | Yelp (Acc.) | Youtube (Acc.) | AGNews (Acc.) | TREC (Acc.) | CDR (F1) | SemEval (F1) | Mean
---|---|---|---|---|---|---|---|---
Gold | 91.58 $\pm$ 0.31 | 95.48 $\pm$ 0.53 | 97.52 $\pm$ 0.64 | 90.78 $\pm$ 0.49 | 96.24 $\pm$ 0.61 | 65.39 $\pm$ 1.18 | 95.43 $\pm$ 0.65 | 90.35
Majority Voting | 77.14 $\pm$ 0.13 | 84.91 $\pm$ 0.13 | 90.16 $\pm$ 0.13 | 63.88 $\pm$ 0.13 | 66.56 $\pm$ 1.20 | 58.89 $\pm$ 0.50 | 85.53 $\pm$ 0.13 | 75.30
Weighted Voting | 76.90 $\pm$ 0.24 | 85.45 $\pm$ 1.21 | 92.48 $\pm$ 0.16 | 83.54 $\pm$ 0.18 | 66.00 $\pm$ 2.33 | 57.53 $\pm$ 0.46 | 83.77 $\pm$ 2.93 | 77.95
Dawid-Skene | 80.25 $\pm$ 2.23 | 88.59 $\pm$ 1.25 | 92.88 $\pm$ 0.78 | 86.69 $\pm$ 0.35 | 48.40 $\pm$ 0.95 | 50.49 $\pm$ 0.48 | 71.70 $\pm$ 0.81 | 74.14
Data Programming | 80.82 $\pm$ 1.29 | 82.90 $\pm$ 3.69 | 93.60 $\pm$ 0.98 | 86.55 $\pm$ 0.08 | 68.64 $\pm$ 3.57 | 58.48 $\pm$ 0.73 | 83.93 $\pm$ 0.83 | 79.27
MeTaL | 81.23 $\pm$ 1.23 | 88.29 $\pm$ 1.57 | 92.48 $\pm$ 0.99 | 86.82 $\pm$ 0.23 | 62.44 $\pm$ 2.96 | 58.48 $\pm$ 0.90 | 71.47 $\pm$ 0.57 | 77.32
FlyingSquid | 82.26 $\pm$ 1.41 | 88.86 $\pm$ 0.92 | 91.84 $\pm$ 2.10 | 86.29 $\pm$ 0.49 | 30.96 $\pm$ 4.04 | 35.25 $\pm$ 5.75 | 31.83 $\pm$ 0.00 | 63.90
EBCC∗ | 67.99 | 72.87 | 86.57 | 55.94 | 46.94 | 23.89 | 33.80 | 55.43
FABLE∗ | 73.96 | 72.50 | 88.86 | 62.74 | 53.20 | 62.15 | 74.32 | 69.68
Denoise | 76.22 $\pm$ 0.37 | 71.56 $\pm$ 0.00 | 76.56 $\pm$ 0.00 | 83.45 $\pm$ 0.11 | 56.20 $\pm$ 6.73 | 56.54 $\pm$ 0.37 | 80.83 $\pm$ 1.31 | 71.62
WeaSEL | 84.99 $\pm$ 1.17 | 86.67 $\pm$ 2.23 | 76.80 $\pm$ 15.20 | 85.30 $\pm$ 0.72 | 62.50 $\pm$ 7.40 | 46.20 $\pm$ 12.30 | 44.30 $\pm$ 2.65 | 69.54
LocalBoost | 85.74 $\pm$ 1.12 | 91.50 $\pm$ 0.83 | 94.93 $\pm$ 0.79 | 88.92 $\pm$ 0.44 | 69.72 $\pm$ 1.47 | 60.29 $\pm$ 0.24 | 86.35 $\pm$ 0.57 | 82.49

###  5.1. Experiment Setup

####  5.1.1. Datasets

We conduct main experiments on seven public datasets from the WRENCH benchmark
(Zhang et al., 2021a), including 1) IMDb (Maas et al., 2011) for movie review
classification; 2) Yelp (Zhang et al., 2015) for sentiment analysis; 3)
YouTube (Alberto et al., 2015) for spam classification; 4) AGNews (Zhang et
al., 2015) for news topic classification; 5) TREC (Li and Roth, 2002) for web
query classification; 6) CDR (Davis et al., 2017) for biomedical relation
classification; and 7) SemEval (Hendrickx et al., 2010) for web text relation
classification. The details for these datasets are exhibited in table 4.

####  5.1.2. Metrics

We strictly follow the evaluation protocol in WRENCH benchmark. Specifically,
for text classification, we use _Accuracy_ as the metric. For relation
classification, we use _F1_ score as the metric.

####  5.1.3. Baselines

We compare LocalBoost with the following baselines:

  * •

Majority voting: It predicts the label of each data point using the most
common prediction from LFs.

  * •

Weighted majority voting: It extends the majority voting by reweighting the
final votes using the label prior.

  * •

Dawid-Skene (Dawid and Skene, 1979): It estimates the accuracy of each LF by
assuming a naive Bayes distribution over the LFs’ votes and models the ground
truth as the latent variable.

  * •

Data Programming (Ratner et al., 2017): It models the distributions between
label and LFs as a factor graph to reflect the dependency between any subset
of random variables. It uses Gibbs sampling for maximum likelihood
optimization.

  * •

MeTaL (Ratner et al., 2019): It models the distribution via a Markov Network
and estimates the parameters via matrix completion.

  * •

FlyingSquid (Fu et al., 2020): It models the distribution between LF and
labels as a binary Ising model and uses a Triplet Method to recover the
parameters.

  * •

EBCC (Li et al., 2019): It is a method originally proposed for crowdsourcing,
which models the relation between workers’ annotation and the ground truth
label by independent assumption.

  * •

FABLE (Zhang et al., 2022d): It incorporates instance features into a
statistical label model for better label aggregation.

  * •

Denoise (Ren et al., 2020): It uses an attention-based mechanism for
aggregating over weak labels, and co-trains an additional neural classifier to
encode the instance embeddings.

  * •

WeaSEL (Rühling Cachay et al., 2021): It is an end-to-end approach for WSL,
which maximizes the agreement between the neural label model and end model for
better performance.

####  5.1.4. Implementation Details

We keep the number of iterations $T=5$ for all the experiments, the number of
weak sources $p$ varies based on the number of LFs as shown in Table 4.
Specifically, we set $p=\\#LF$ for IMDb, Yelp, YouTube, and AGNews. For the
other datasets, it will bring a redundant ensemble if we implement inter-
source boosting for all the LFs. Instead, for TREC and SemEval, we group the
LFs based on the labels. For CDR, we manually divide the LFs to 6 groups (3
groups for each label). The source-index datasets are constructed accordingly,
in which the index of LFs or LF groups are used as labels. To learn the
conditional function, we deploy a multi-layer perceptron with 2 hidden layers,
the shape of the output layer varies according to the number of weak sources
for different datasets. We use the training set shown in Table 4 as the weakly
labeled datasets $\mathcal{D}_{l}$, where the labels are generated by their
LFs. We use a subset of the validation set as the small clean dataset
$\mathcal{D}_{c}$. For YouTube and SemEval, we set the $|\mathcal{D}_{c}|$ as
$120$ and $200$. For AGNews, we set the $|\mathcal{D}_{c}|=1000$. For the
other datasets, we keep $|\mathcal{D}_{c}|=500$. The clean data are only for
the usage of weights computation and error instance identification, not
involved in the base learner training. We use BERT-base (Devlin et al., 2018)
with 110M parameters as the backbone model and AdamW (Loshchilov and Hutter,
2017) as the optimizer. More details on hyperparameters are introduced in
Appendix B.

###  5.2. Main Results

The results in Table 1 compare the performance of our method LocalBoost with
the baselines. On all datasets, LocalBoost consistently outperforms these
strong baselines, with performance improvements ranging from 1.08% to 3.48%
compared to the strongest baselines. On average across the seven datasets,
LocalBoost reaches 91.3% of the performance obtained with fully-supervised
learning, significantly reducing the gap between weakly-supervised learning
and fully-supervised learning.

The performance of our method is significantly better compared to the voting
methods. This demonstrates that our conditional function can effectively boost
the performance of the base learners by computing the conditional probability
of weak sources given an input sample. Unlike the voting methods, which simply
average or weight-average the predictions from different sources, the
conditional function allows the base learners to emphasize on most reliable
labeling functions when combined.

When comparing with the label aggregation methods, the significant improvement
demonstrates the advantage of boosting methods over the single end model. Take
the strongest baseline (Data Programming) for instance. On the IMDb and Yelp
datasets, LocalBoost achieves a performance gain of 4.92% and 8.60%,
respectively. Although label aggregation methods can model the distributions
between labels and weak sources, the single end model trained on the entire
weakly labeled dataset fails to obtain a locality to enhance itself. Instead,
we introduce locality to the base learners while retaining the boosting
nature, so the ensemble model in LocalBoost can self-strengthen by adding
complementary base learners iteratively.

((a)) IMDb

((b)) Yelp

((c)) TREC

Figure 4. Iterative performance of the two-dimension boosting. For the intra-
source boosting, we show its performance change in the first $t=1$ loop. For
the inter-source boosting, we show the ensemble at the end of each outer
iteration, where $l=p$.

###  5.3. Two-dimension Boosting

Fig. 4 shows the iterative results in the two-dimension boosting process. For
inter-source boosting, we plot its performance change at iteration $(t,l)$
such that $t=1,l\in[p]$. For intra-source boosting, we plot its performance
change at iteration $(t,l)$ such that $l=p,t\in[T]$. We observe a consistent
improvement in performance through inter-source boosting, indicating that the
base learners can complement each other and build upon the models trained from
other weak sources. In the early stages of inter-source boosting, there is a
significant improvement in performance, demonstrating that the weak regions of
the previous ensemble model are effectively learned by the following base
learners. However, the performance gains become relatively modest towards the
end, as the ensemble model has already combined sufficient base learners, and
the remaining error regions may not be well learned due to the limitations of
weak supervision, even with the addition of more base learners.

###  5.4. Study of the Conditional Function

In this set of experiments, we study the effect of the conditional function
$Q(l|x)$ as described in Sec. 4.2. We considered two baselines, one where the
conditional function is disabled, and another where the conditional function
is replaced with labeling function (LF) matching. The first baseline simply
ensembles the base learners without distinguishing between intra-source and
inter-source boosting. For the second baseline, the direct LF matching is a
natural alternative to the learned conditional function. Specifically, to
represent the conditional probability of weak sources given a data sample, we
replace the $Q(l|x)$ in the LocalBoost framework with the entries in a
normalized LF matching vector.

Table 2. Study of the conditional function | LocalBoost | w/o. cond. func. | w/ LF matching
---|---|---|---
IMDb | 85.74 $\pm$ 1.12 | 80.37 $\pm$ 1.23 | 84.92 $\pm$ 1.63
Yelp | 91.50 $\pm$ 0.83 | 88.07 $\pm$ 2.45 | 88.89 $\pm$ 2.10
Youtube | 94.93 $\pm$ 0.79 | 93.31 $\pm$ 1.14 | 93.23 $\pm$ 1.27
AGNews | 88.92 $\pm$ 0.44 | 87.19 $\pm$ 0.54 | 88.45 $\pm$ 0.24
TREC | 69.72 $\pm$ 1.47 | 67.78 $\pm$ 2.19 | 68.42 $\pm$ 1.31
CDR | 60.29 $\pm$ 0.24 | 56.19 $\pm$ 2.56 | 58.79 $\pm$ 1.43
SemEval | 86.35 $\pm$ 0.57 | 85.64 $\pm$ 0.76 | 86.23 $\pm$ 0.48
Mean | 82.49 | 79.79 | 81.28

Table 2 compares the learning framework variants and demonstrates the
advantages of LocalBoost. It is consistently better on all seven datasets,
with average performance gains of 2.70% and 1.21%. The comparison with the
baseline without $Q(l|x)$ highlights the superiority of introducing a
conditional function to account for weak sources. Disabling $Q(l|x)$ results
in a standard convex combination, which is not suitable for the WSL scenario.
The baseline using direct LF matching instead of the conditional function
shows improved performance over the original baseline, supporting the need to
modulate base learners for weak sources. However, it still falls behind
LocalBoost by 1.21%, as LF labeling conflicts undermine the proper assignment
of base learners to weak sources. The conditional function learned on the
source-index dataset can generalize better during inference, benefiting the
entire ensemble, compared to hard LF matching.

###  5.5. Study of the Estimate-then-Modify Scheme

In this set of experiments, we examine the benefits of our estimate-then-
modify scheme for calculating weights in the WSL setting and the importance of
the interaction between weak labels and clean labels. We compare with two
baselines, both of which are variants of LocalBoost that use different weight
calculation methods. The first baseline uses the AdaBoost approach to compute
base learner weights on the weakly labeled dataset, while the second
integrates both weak and clean labels but only uses weak labels for base
learner training and calculates weights solely on the clean dataset.

Table 3. Study of the estimate-then-modify weighting | LocalBoost | only weak labels | integrated mode
---|---|---|---
IMDb | 85.74 $\pm$ 1.12 | 79.55 $\pm$ 1.78 | 80.86 $\pm$ 1.53
Yelp | 91.50 $\pm$ 0.83 | 87.78 $\pm$ 2.46 | 88.34 $\pm$ 1.20
Youtube | 94.93 $\pm$ 0.79 | 92.81 $\pm$ 0.95 | 93.07 $\pm$ 0.89
AGNews | 88.92 $\pm$ 0.44 | 85.60 $\pm$ 1.16 | 88.12 $\pm$ 0.42
TREC | 69.72 $\pm$ 1.47 | 57.93 $\pm$ 4.85 | 66.30 $\pm$ 2.66
CDR | 60.29 $\pm$ 0.24 | 54.62 $\pm$ 1.69 | 58.75 $\pm$ 0.34
SemEval | 86.35 $\pm$ 0.57 | 82.86 $\pm$ 1.03 | 84.76 $\pm$ 0.71
Mean | 82.49 | 77.31 | 80.03

Table 3 shows that LocalBoost outperforms the two variants by significant
margins. LocalBoost has a performance improvement of 5.18% compared to the
baseline using only weak labels, supporting our hypothesis that weak labels
are unreliable for weight computation. Despite the integration of both weak
and clean labels in the second baseline, LocalBoost still leads by 2.46%. We
believe that the disconnected training of base learners and weight calculation
weakens the learning framework, as it cannot provide an appropriate
combination of base learners when the weakly labeled data deviates from the
clean data. On the other hand, LocalBoost leverages the estimate-then-modify
paradigm to consider both weak and clean labels, which results in a more
generalizable model due to the interaction between the two types of labels.

##  6\. Conclusion

We presented a novel iterative and adaptive learning framework, LocalBoost to
boost the ensemble model in the setting of weakly supervised learning. While
preserving the key concepts of traditional boosting methods, we introduced
locality to base learners and designed an interaction between weak labels and
clean labels to adapt to the WSL setting. The adaptations included the use of
local base learners, the incorporation of a conditional function to account
for weak sources, and the application of the estimate-then-modify scheme for
weight computation. Specifically, we localized the base learners to the
iteratively updated error regions in the embedding space, thereby overcoming
the issues of weight domination in vanilla boosting for WSL and the challenges
of hard clustering in the MoE approach. To handle weak sources such as
labeling functions in WSL settings, we designed a conditional function to
modulate the base learners towards weak sources with high relevance. This
addressed the issue of poor ensemble performance in the standard convex
combination approach in WSL settings. Finally, we proposed an estimate-then-
modify scheme for weight computation. Our comprehensive empirical study on
seven datasets demonstrated the effectiveness and advantages of LocalBoost
compared to standard ensemble methods and WSL baselines.

###### Acknowledgements.

This work was supported by NSF IIS-2008334, IIS-2106961, CAREER IIS-2144338,
as well as a generous gift from The Home Depot.

## References

  * Awasthi et al. [2020] Abhijeet Awasthi, Sabyasachi Ghosh, Rasna Goyal, and Sunita Sarawagi.  Learning from rules generalizing labeled exemplars.  In _International Conference on Learning Representations_ , 2020.
  * Safranchik et al. [2020] Esteban Safranchik, Shiying Luo, and Stephen Bach.  Weakly supervised sequence tagging from noisy rules.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 34, pages 5570–5578, 2020.
  * Zhang et al. [2022a] Rongzhi Zhang, Rebecca West, Xiquan Cui, and Chao Zhang.  Adaptive multi-view rule discovery for weakly-supervised compatible products prediction.  In _KDD_ , pages 4521–4529, 2022a.
  * Zhang et al. [2021a] Jieyu Zhang, Yue Yu, Yinghao Li, Yujing Wang, Yaming Yang, Mao Yang, and Alexander Ratner.  WRENCH: A comprehensive benchmark for weak supervision.  In _NeurIPS_ , 2021a.
  * Freund and Schapire [1995] Yoav Freund and Robert E Schapire.  A desicion-theoretic generalization of on-line learning and an application to boosting.  In _Computational Learning Theory: Second European Conference_ , pages 23–37. Springer, 1995.
  * Freund et al. [1996] Yoav Freund, Robert E Schapire, et al.  Experiments with a new boosting algorithm.  In _icml_ , volume 96, pages 148–156. Citeseer, 1996.
  * Mason et al. [1999] Llew Mason, Jonathan Baxter, Peter Bartlett, and Marcus Frean.  Boosting algorithms as gradient descent.  _Advances in neural information processing systems_ , 12, 1999.
  * Chen and Guestrin [2016] Tianqi Chen and Carlos Guestrin.  Xgboost: A scalable tree boosting system.  In _Proceedings of the 22nd acm sigkdd international conference on knowledge discovery and data mining_ , pages 785–794, 2016.
  * Rätsch et al. [2005] Gunnar Rätsch, Manfred K Warmuth, and John Shawe-Taylor.  Efficient margin maximizing with boosting.  _Journal of Machine Learning Research_ , 6(12), 2005.
  * Jacobs et al. [1991] Robert A Jacobs, Michael I Jordan, Steven J Nowlan, and Geoffrey E Hinton.  Adaptive mixtures of local experts.  _Neural computation_ , 3(1):79–87, 1991.
  * Tsai et al. [2021] Tsung Wei Tsai, Chongxuan Li, and Jun Zhu.  Mice: Mixture of contrastive experts for unsupervised image clustering.  In _International conference on learning representations_ , 2021.
  * Zhuang et al. [2022] Yuchen Zhuang, Yinghao Li, Jerry Junyang Cheung, Yue Yu, Yingjun Mou, Xiang Chen, Le Song, and Chao Zhang.  Resel: N-ary relation extraction from scientific text and tables by learning to retrieve and select.  _arXiv preprint arXiv:2210.14427_ , 2022.
  * Xu et al. [2023] Ran Xu, Yue Yu, Joyce C Ho, and Carl Yang.  Weakly-supervised scientific document classification via retrieval-augmented multi-stage training.  In _the 46th International ACM SIGIR Conference on Research and Development in Information Retrieval_ , 2023.
  * Hoffmann et al. [2011] Raphael Hoffmann, Congle Zhang, Xiao Ling, Luke Zettlemoyer, and Daniel S Weld.  Knowledge-based weak supervision for information extraction of overlapping relations.  In _Proceedings of the 49th annual meeting of the association for computational linguistics: human language technologies_ , pages 541–550, 2011\.
  * Smith et al. [2022] Ryan Smith, Jason A Fries, Braden Hancock, and Stephen H Bach.  Language models in the loop: Incorporating prompting into weak supervision.  _arXiv preprint arXiv:2205.02318_ , 2022.
  * Yu et al. [2023] Yue Yu, Yuchen Zhuang, Rongzhi Zhang, Yu Meng, Jiaming Shen, and Chao Zhang.  Regen: Zero-shot text classification via training data generation with progressive dense retrieval.  In _Findings of ACL_ , 2023.
  * Zhang et al. [2022b] Rongzhi Zhang, Yue Yu, Pranav Shetty, Le Song, and Chao Zhang.  Prboost: Prompt-based rule discovery and boosting for interactive weakly-supervised learning.  In _Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 745–758, 2022b.
  * Zhang et al. [2022c] Jieyu Zhang, Cheng-Yu Hsieh, Yue Yu, Chao Zhang, and Alexander Ratner.  A survey on programmatic weak supervision.  _arXiv preprint arXiv:2202.05433_ , 2022c.
  * Ratner et al. [2017] Alexander Ratner, Stephen H Bach, Henry Ehrenberg, Jason Fries, Sen Wu, and Christopher Ré.  Snorkel: Rapid training data creation with weak supervision.  In _VLDB_ , volume 11, page 269, 2017.
  * Ratner et al. [2019] Alexander Ratner, Braden Hancock, Jared Dunnmon, Frederic Sala, Shreyash Pandey, and Christopher Ré.  Training complex models with multi-task weak supervision.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , pages 4763–4771, 2019.
  * Fu et al. [2020] Daniel Y. Fu, Mayee F. Chen, Frederic Sala, Sarah M. Hooper, Kayvon Fatahalian, and Christopher Ré.  Fast and three-rious: Speeding up weak supervision with triplet methods.  In _Proceedings of the 37th International Conference on Machine Learning_ , 2020.
  * Zhang et al. [2022d] Jieyu Zhang, Linxin Song, and Alexander Ratner.  Leveraging instance features for label aggregation in programmatic weak supervision.  _arXiv preprint arXiv:2210.02724_ , 2022d.
  * Stephan et al. [2022] Andreas Stephan, Vasiliki Kougia, and Benjamin Roth.  SepLL: Separating latent class labels from weak supervision noise.  In _Findings of EMNLP_ , December 2022.
  * Yu et al. [2021] Yue Yu, Simiao Zuo, Haoming Jiang, Wendi Ren, Tuo Zhao, and Chao Zhang.  Fine-tuning pre-trained language model with weak supervision: A contrastive-regularized self-training approach.  In _NAACL_ , pages 1063–1077, 2021.
  * Wu et al. [2020] Yiquan Wu, Kun Kuang, Yating Zhang, Xiaozhong Liu, Changlong Sun, Jun Xiao, Yueting Zhuang, Luo Si, and Fei Wu.  De-biased court’s view generation with causality.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP)_ , pages 763–780, 2020.
  * Li and Zhang [2021] Dongyue Li and Hongyang Zhang.  Improved regularization and robustness for fine-tuning in neural networks.  In _NeurIPS_ , 2021.
  * Rühling Cachay et al. [2021] Salva Rühling Cachay, Benedikt Boecking, and Artur Dubrawski.  End-to-end weak supervision.  _Advances in Neural Information Processing Systems_ , 34:1845–1857, 2021.
  * Ren et al. [2020] Wendi Ren, Yinghao Li, Hanting Su, David Kartchner, Cassie Mitchell, and Chao Zhang.  Denoising multi-source weak supervision for neural text classification.  In _Findings of the Association for Computational Linguistics: EMNLP 2020_ , pages 3739–3754, 2020.
  * Sam and Kolter [2022] Dylan Sam and J Zico Kolter.  Losses over labels: Weakly supervised learning via direct loss construction.  _arXiv preprint arXiv:2212.06921_ , 2022.
  * Shin et al. [2022] Changho Shin, Winfred Li, Harit Vishwakarma, Nicholas Carl Roberts, and Frederic Sala.  Universalizing weak supervision.  In _International Conference on Learning Representations_ , 2022.
  * Wu et al. [2022] Yiquan Wu, Yifei Liu, Weiming Lu, Yating Zhang, Jun Feng, Changlong Sun, Fei Wu, and Kun Kuang.  Towards interactivity and interpretability: A rationale-based legal judgment prediction framework.  In _Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing_ , pages 4787–4799, 2022.
  * Zhang et al. [2020] Rongzhi Zhang, Yue Yu, and Chao Zhang.  Seqmix: Augmenting active sequence labeling via sequence mixup.  In _EMNLP_ , pages 8566–8579, 2020.
  * Biegel et al. [2021] Samantha Biegel, Rafah El-Khatib, Luiz Otavio Vilas Boas Oliveira, Max Baak, and Nanne Aben.  Active weasul: Improving weak supervision with active learning.  _arXiv preprint arXiv:2104.14847_ , 2021.
  * Yu et al. [2022a] Yue Yu, Lingkai Kong, Jieyu Zhang, Rongzhi Zhang, and Chao Zhang.  Actune: Uncertainty-based active self-training for active fine-tuning of pretrained language models.  In _NAACL_ , pages 1422–1436, 2022a.
  * Yu et al. [2022b] Yue Yu, Rongzhi Zhang, Ran Xu, Jieyu Zhang, Jiaming Shen, and Chao Zhang.  Cold-start data selection for few-shot language model fine-tuning: A prompt-based uncertainty propagation approach.  _arXiv preprint arXiv:2209.06995_ , 2022b.
  * Guan et al. [2018] Melody Guan, Varun Gulshan, Andrew Dai, and Geoffrey Hinton.  Who said what: Modeling individual labelers improves classification.  In _Proceedings of the AAAI conference on artificial intelligence_ , 2018.
  * Zhao et al. [2022] Yue Zhao, Guoqing Zheng, Subhabrata Mukherjee, Robert McCann, and Ahmed Awadallah.  Admoe: Anomaly detection with mixture-of-experts from noisy labels.  _arXiv preprint arXiv:2208.11290_ , 2022.
  * Breiman [1999] Leo Breiman.  Prediction games and arcing algorithms.  _Neural computation_ , 11(7):1493–1517, 1999\.
  * Friedman [2001] Jerome H Friedman.  Greedy function approximation: a gradient boosting machine.  _Annals of statistics_ , pages 1189–1232, 2001.
  * Brukhim et al. [2021] Nataly Brukhim, Elad Hazan, Shay Moran, Indraneel Mukherjee, and Robert E Schapire.  Multiclass boosting and the cost of weak learning.  _Advances in Neural Information Processing Systems_ , 34:3057–3067, 2021.
  * Cortes et al. [2021a] Corinna Cortes, Mehryar Mohri, Dmitry Storcheus, and Ananda Theertha Suresh.  Boosting with multiple sources.  _Advances in Neural Information Processing Systems_ , 34:17373–17387, 2021a.
  * Zhang et al. [2022e] Dinghuai Zhang, Hongyang Zhang, Aaron Courville, Yoshua Bengio, Pradeep Ravikumar, and Arun Sai Suggala.  Building robust ensembles via margin boosting.  In _International Conference on Machine Learning_ , pages 26669–26692. PMLR, 2022e.
  * Huang et al. [2018] Furong Huang, Jordan Ash, John Langford, and Robert Schapire.  Learning deep resnet blocks sequentially using boosting theory.  In _International Conference on Machine Learning_ , pages 2058–2067. PMLR, 2018.
  * Nitanda and Suzuki [2018] Atsushi Nitanda and Taiji Suzuki.  Functional gradient boosting based on residual network perception.  In _International Conference on Machine Learning_ , pages 3819–3828. PMLR, 2018.
  * Suggala et al. [2020] Arun Suggala, Bingbin Liu, and Pradeep Ravikumar.  Generalized boosting.  _Advances in neural information processing systems_ , 33:8787–8797, 2020.
  * Taherkhani et al. [2020] Aboozar Taherkhani, Georgina Cosma, and T Martin McGinnity.  Adaboost-cnn: An adaptive boosting algorithm for convolutional neural networks to classify multi-class imbalanced datasets using transfer learning.  _Neurocomputing_ , 404:351–366, 2020.
  * Mansour et al. [2008] Yishay Mansour, Mehryar Mohri, and Afshin Rostamizadeh.  Domain adaptation with multiple sources.  _Advances in neural information processing systems_ , 21, 2008.
  * Hoffman et al. [2018] Judy Hoffman, Mehryar Mohri, and Ningshan Zhang.  Algorithms and theory for multiple-source adaptation.  _Advances in Neural Information Processing Systems_ , 31, 2018.
  * Cortes et al. [2021b] Corinna Cortes, Mehryar Mohri, Ananda Theertha Suresh, and Ningshan Zhang.  A discriminative technique for multiple-source adaptation.  In _International Conference on Machine Learning_ , pages 2132–2143. PMLR, 2021b.
  * Zhang et al. [2021b] Ningshan Zhang, Mehryar Mohri, and Judy Hoffman.  Multiple-source adaptation theory and algorithms.  _Annals of Mathematics and Artificial Intelligence_ , 89:237–270, 2021b.
  * Yu et al. [2022c] Yue Yu, Chenyan Xiong, Si Sun, Chao Zhang, and Arnold Overwijk.  Coco-dr: Combating distribution shifts in zero-shot dense retrieval with contrastive and distributionally robust learning.  _arXiv preprint arXiv:2210.15212_ , 2022c.
  * Zhang et al. [2023] Rongzhi Zhang, Jiaming Shen, Tianqi Liu, Jialu Liu, Michael Bendersky, Marc Najork, and Chao Zhang.  Do not blindly imitate the teacher: Using perturbed loss for knowledge distillation.  _arXiv preprint arXiv:2305.05010_ , 2023.
  * Maas et al. [2011] Andrew L. Maas, Raymond E. Daly, Peter T. Pham, Dan Huang, Andrew Y. Ng, and Christopher Potts.  Learning word vectors for sentiment analysis.  In _Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies_ , pages 142–150, Portland, Oregon, USA, June 2011.
  * Zhang et al. [2015] Xiang Zhang, Junbo Zhao, and Yann LeCun.  Character-level convolutional networks for text classification.  In _NeurIPS_ , pages 649–657, 2015.
  * Alberto et al. [2015] T. C. Alberto, J. V. Lochter, and T. A. Almeida.  Tubespam: Comment spam filtering on youtube.  In _ICMLA_ , pages 138–143, 2015.
  * Li and Roth [2002] Xin Li and Dan Roth.  Learning question classifiers.  In _COLING_ , 2002.
  * Davis et al. [2017] Allan Peter Davis, Cynthia J Grondin, Robin J Johnson, Daniela Sciaky, Benjamin L King, Roy McMorran, Jolene Wiegers, Thomas C Wiegers, and Carolyn J Mattingly.  The comparative toxicogenomics database: update 2017.  _Nucleic acids research_ , 45:D972–D978, 2017.
  * Hendrickx et al. [2010] Iris Hendrickx, Su Nam Kim, Zornitsa Kozareva, Preslav Nakov, Diarmuid Ó Séaghdha, Sebastian Padó, Marco Pennacchiotti, Lorenza Romano, and Stan Szpakowicz.  Semeval-2010 task 8: Multi-way classification of semantic relations between pairs of nominals.  In _Semeval_ , pages 33–38, 2010.
  * Dawid and Skene [1979] Alexander Philip Dawid and Allan M Skene.  Maximum likelihood estimation of observer error-rates using the em algorithm.  _Journal of the Royal Statistical Society: Series C (Applied Statistics)_ , 28(1):20–28, 1979.
  * Li et al. [2019] Yuan Li, Benjamin Rubinstein, and Trevor Cohn.  Exploiting worker correlation for label aggregation in crowdsourcing.  In _International conference on machine learning_ , pages 3886–3895. PMLR, 2019.
  * Devlin et al. [2018] Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova.  Bert: Pre-training of deep bidirectional transformers for language understanding.  _arXiv preprint arXiv:1810.04805_ , 2018.
  * Loshchilov and Hutter [2017] Ilya Loshchilov and Frank Hutter.  Decoupled weight decay regularization.  _arXiv preprint arXiv:1711.05101_ , 2017.

Table 4. Detailed statistics of classification datasets.

|  | Avr. over LFs | Train | Valid | Test
---|---|---|---|---|---
Task | Domain | Dataset | #Label | #LF | Ovr. %Coverage | %Coverage | %Overlap | %Conflict | %Accuracy | #Data | #Data | #Data
Sentiment Classification | Movie | IMDb [Maas et al., 2011] | 2 | 5 | 87.58 | 23.60 | 11.60 | 4.50 | 69.88 | 20,000 | 2,500 | 2,500
Review | Yelp [Zhang et al., 2015] | 2 | 8 | 82.78 | 18.34 | 13.58 | 4.94 | 73.05 | 30,400 | 3,800 | 3,800
Spam Classification | Review | Youtube [Alberto et al., 2015] | 2 | 10 | 87.70 | 16.34 | 12.49 | 7.14 | 83.16 | 1,586 | 120 | 250
Topic Classification | News | AGNews [Zhang et al., 2015] | 4 | 9 | 69.08 | 10.34 | 5.05 | 2.43 | 81.66 | 96,000 | 12,000 | 12,000
Question Classification | Web Query | TREC [Li and Roth, 2002] | 6 | 68 | 95.13 | 2.55 | 1.82 | 0.84 | 75.92 | 4,965 | 500 | 500
Relation Classification | Biomedical | CDR [Davis et al., 2017, Ratner et al., 2017] | 2 | 33 | 90.72 | 6.27 | 5.36 | 3.21 | 75.27 | 8,430 | 920 | 4,673
Web Text | SemEval [Hendrickx et al., 2010] | 9 | 164 | 100.00 | 0.77 | 0.32 | 0.14 | 97.69 | 1,749 | 200 | 692

##  Appendix A Data Statistics

In Table 4, we provide detailed information about datasets used in our
experiments, encompassing statistics related to the labeling functions for
each dataset.

##  Appendix B Implementation Details

The hyperparameters involved in this study includes the $k$ in Eq. (9) and
$c_{1}$ in Eq. (10). The value for these two hyperparameters is listed in the
Table 5.

Table 5. Hyper-parameter Settings. | IMDb | Yelp | Youtube | AGNews | TREC | CDR | SemEval
---|---|---|---|---|---|---|---
Max Length | 150 | 256 | 256 | 512 | 64 | 128 | 128
Learning Rate | 1e-4 | 1e-4 | 1e-4 | 2e-5 | 5e-6 | 5e-6 | 3e-5
Batch Size | 64 | 32 | 32 | 16 | 64 | 32 | 32
$k$ | 10 | 10 | 5 | 10 | 5 | 5 | 5
$c_{1}$ | 4.0 | 4.0 | 8.0 | 4.0 | 10.0 | 10.0 | 10.0

###  B.1. Computational Environment

All of the experiments are conducted on _CPU_ : Intel(R) Core(TM) i7-5930K CPU
@ 3.50GHz and _GPU_ : NVIDIA GeForce RTX A5000 GPUs with 24 GB memory using
python 3.6 and Pytorch 1.10.

##  Appendix C Proof

Here, we provide evidence for Proposition 1, which highlights that a good fit
with weakly labeled data doesn’t guarantee strong performance from their
convex combination.

###### Proof.

Consider the weak sources $LF_{1}$ and $LF_{2}$, a dataset
$X=\left\\{x_{1},x_{2}\right\\}$, and the label space $Y=\\{+1,-1\\}$. The
data samples get matched $LF_{1}$ and $LF_{2}$, respectively, and the weak
labels given by the weak sources are

(22) $LF_{1}(x_{1})=+1,\quad LF_{2}(x_{2})=-1.$

From each weak source, we have base learner

(23) $f_{1}(x)=LF_{1}(x)=+1,\quad f_{2}(x)=LF_{2}(x)=-1.$

We have the convex combination of the two base learners

(24)
$\displaystyle\mathcal{L}\left(\frac{1}{2}\left(\mathcal{D}_{1}+\mathcal{D}_{2}\right),\alpha
f_{1}+(1-\alpha)f_{2}\right)$ $\displaystyle=$
$\displaystyle\frac{1}{2}\mathbb{I}(\alpha
f_{1}(x_{1})+(1-\alpha)f_{2}(x_{1}))+\frac{1}{2}\mathbb{I}(\alpha
f_{1}(x_{2})+(1-\alpha)f_{2}(x_{2}))$ $\displaystyle=$
$\displaystyle\frac{1}{2}\mathbb{I}(2\alpha-1\leq
0)+\frac{1}{2}\mathbb{I}(1-2\alpha\leq 0)\geq\frac{1}{2}.$

That is to say, even if the base learners perform well for the corresponding
weak source such that

(25)
$\displaystyle\mathcal{L}\left(\mathcal{D}_{1},f_{1}\right)=\mathbb{I}\left(f_{1}\left(x_{1}\right)LF_{1}\left(x_{1}\right)\leq
0\right)=0,$
$\displaystyle\mathcal{L}\left(\mathcal{D}_{2},f_{2}\right)=\mathbb{I}\left(f_{2}\left(x_{2}\right)LF_{2}\left(x_{2}\right)\leq
0\right)=0,$

the standard convex combination of them can still lead to a poor ensemble as
$\mathcal{L}\left(\frac{1}{2}\left(\mathcal{D}_{1}+\mathcal{D}_{2}\right),\alpha
f_{1}+(1-\alpha)f_{2}\right)\geq\frac{1}{2}$ shown in Eq. 24. ∎


# Knot intensity distribution: a local measure of entanglement

Agnese Barbensi1 and Daniele Celoria1 1 School of Mathematics and Statistics,
University of Melbourne, 3010 VIC, Australia

###### Abstract

The problem of finding robust and effective methods for locating entanglement
in embedded curves is relevant to both applications and theoretical
investigations. Rather than focusing on an exact determination, we introduce
the knot intensity distribution, a local quantifier for the contribution of a
curve’s region to global entanglement. The integral of the distribution yields
a measure of tightness for knots. We compute the distribution for ideal knots,
and study its behaviour on prime and composite random knots. Intensity
distributions provide an effective method to locate entanglement. In
particular, they identify regions in knots that accommodate passages leading
to topological changes.

##  1 Introduction

Everyone has an intuitive idea of what it means for a piece of rope to be
knotted. A more challenging task is to pinpoint regions in the rope that are
actively contributing in creating the knot. This is often relevant in
applications; as an example, the folding and stability of knotted proteins is
known to be influenced by the geometry and localisation of the entanglement in
their native states [1, 2, 3].

A knotted arc is called tight if its entanglement is highly localised, so that
the portion involved in the knot is small when compared to the length of the
whole curve. To give a precise quantification of tightness, it is necessary to
pinpoint the entanglement’s location. The most straightforward strategy is to
analyse the topology of all the curve’s sub-arcs; this procedure determines
the shortest knotted portion [4, 5], which is often called the arc’s knot
core. Tightness can then be measured as a function of length and position of
the knot core, relative to the entire curve.

While being mainly motivated by applications in the open setting, similar
ideas generalise to the problem of measuring tightness of closed curves, i.e.
mathematical knots. Standard approaches to this question rely on extending the
open arc setting to identify a specific portion of a knot as its knotted core
[5, 6, 7, 8, 9, 10].

Despite the obvious appeal of looking for an exact identification of the knot
core, the concept of the “shortest knotted portion” is problematic in general.
Indeed, in some cases, the shortest knotted portion might not contain a
curve’s entire entanglement, and different notions might be better suited to
localise it [4], see also Figure 1(A). Here, we explore an alternative point
of view; we develop a mathematical framework to quantify the local intensity
of the entanglement. To a given a knotted configuration, specified by an
embedding $\gamma\colon S^{1}\rightarrow\mathbb{R}^{3}$, we associate a
function $f_{\gamma}\colon S^{1}\longrightarrow\mathbb{R}_{\geq 0}$, called
the _knot intensity distribution_. This function assigns a value to each point
in a curve, measuring the amount of local contribution to the overall
topology, computed from a superposition of knot cores.

The key advantage of this strategy is to remove some intrinsic ambiguities
present in previous methodologies, while encoding nuanced information on the
topology and geometry of the embedding. This information can be extracted
using a number of techniques, including a coarea approach. In this case, the
resulting fingerprint functions can be used to create a coordinate-free
statistical summary of the distributions. As another example, the integral of
$f_{\gamma}$ yields a non-negative number $\mathcal{D}(\gamma)$. We call this
number the _knot density_ of $\gamma$, and show that it provides a reliable
measure of tightness. Indeed, high values of $\mathcal{D}$ arise when the
intrinsically knotted component of a knot is evenly distributed throughout the
embedding, while small values indicate localised entanglement. The maximal
value of this integral among all representatives of a given knot type $K$ is a
knot invariant $\mathcal{D}(K)$; it would be interesting to understand its
discriminatory power (_cf_. the discussion in Section 3).

An explicit computation of $f_{\gamma}$ and related quantities is not feasible
for a generic smooth embedding. We therefore extend the framework to the
piece-wise linear (PL) setting, where $f_{\gamma}$ can be approximated
computationally. As a first analysis, we compute the knot intensities
distributions for PL representations of ideal [11, 12] embeddings of prime and
composite knots with low crossing number. We then examine the behaviour of the
knot intensity distributions for random equilateral PL embeddings of low-
crossing number knots, as a function of their length. The resulting statistics
show a clear stratified behaviour with respect to crossing number, and a
tendency of composite knots towards less tight conformations.

As the distribution quantifies the intensity of knottiness for each sub-arc,
it induces a hierarchical classification of points in the curves based on
their contribution to global entanglement. We show that this information can
be used to discriminate regions based on whether they allocate strand passages
leading to topology changes.

##  2 Methods

Our goal is to associate a point-wise measure of entanglement to a knotted
embedding. The method we propose is based on considering a closed curve as the
superposition of all of its openings, and on identifying a knot core candidate
for each of the openings, using standard methods for open curves [5]. The knot
intensity is then computed based on this information. The use of linear chains
to characterise the topology of closed knots was also explored in [10] using
the so-called disk matrices, that encode the entanglement of all of a knot’s
sub-chains.

###  2.1 Mathematical framework

The definition of the knot intensity distribution follows three steps. First,
(1) we identify the knot type of a smooth embedding of an arc
$\alpha\colon[0,1]\longrightarrow\mathbb{R}^{3}$. Standard methods for this
task rely on artificially “closing” the curve to transform it into a knot.
This closure operation can be done in a number of different ways, each coming
with strengths and weaknesses [6, 7, 8, 9, 5]. Once such a choice is made, (2)
the _knot core_ $\mathcal{C}(\alpha)$ of $\alpha$ can be determined by
computing the knot type of each sub-arc. Specifically, for every $t\in[0,1]$,
we consider the embeddings
$\alpha^{t}\colon[\frac{t}{2},1-\frac{t}{2}]\longrightarrow\mathbb{R}^{3}$
obtained by restricting the domain of $\alpha$. Then $\mathcal{C}(\alpha)$ is
the image of the restriction $\alpha^{t_{0}}$, where $t_{0}$ is the minimal
value of $t$ such that the closure of $\alpha^{t}$ has the same associated
knot type as $\alpha$ (with respect to the fixed closure choice). Finally, (3)
let $\gamma\colon S^{1}\hookrightarrow\mathbb{R}^{3}$ be a smooth embedding
representing a non-trivial knot, with arclength parametrisation. For
$\theta\in S^{1}$, the _knot intensity distribution_ of $\gamma$ at the point
$\gamma(\theta)$ is defined as the measure of the set

$\\{\phi\in
S^{1}\,|\,\gamma(\theta)\in\mathcal{C}(\gamma(S^{1}\setminus(\phi-\epsilon,\phi+\epsilon)))\\},$

for some $\epsilon\ll 0$, renormalised by dividing by $2\pi$. The output of
this construction is a function $f_{\gamma}\colon S^{1}\longrightarrow[0,1]$.
We note that the choice of a sufficiently small $\epsilon$ does not affect the
following discussion.

Figure 1: (A) On the left, an embedding of the trefoil knot. On the right, the
knot cores obtained from two different opening points. (B) On the left, the
knot intensity distribution is plotted on the embedding, using colour and
thickness. The colour scale will be maintained throughout the paper. On the
right, a radar plot of the distribution with the corresponding density value.
Note that the three maxima highlight the presence of the embedding’s
“essential” crossings.

Figure 1(A) shows an example of an embedding $\gamma$ where different openings
result in different knot cores; one corresponds to the shortest arc with the
same topology as $\gamma$, while the other to the shortest knotted arc with
trivial complement, whose topology doesn’t change if extended (cf. [4]). Part
(B) of the same figure conveys instead why our methodology is independent of
these issues, while retaining the information contained in previous
constructions. Indeed, the two choices of knot core are recovered as a
weighted superposition.

Given a function $f\colon S^{1}\longrightarrow[0,1]$, obtained through the
procedure detailed above, define its _fingerprint_ as the coarea function
$\overline{f}\colon[0,1]\longrightarrow[0,1]$, with

$\overline{f}(t)=\int_{S^{1}}\min\\{f(s),t\\}\,\mathrm{d}s.$

In other words, $\overline{f}$ is constructed from the integral of the level
sets of $f$. The fingerprint doesn’t unique determine $f$, but gives a
coordinate-independent way of examining the behaviour of the distributions;
fingerprints can be added and averaged, and thus can be used to study the
statistical behaviour of the knot intensities we are interested in. The
fingerprint has the following elementary properties: $\overline{f}(0)=0$,
$\overline{f}(1)=\int_{S^{1}}f\,\mathrm{d}s$, $0\leq\overline{f}^{\prime}\leq
1$ and $\overline{f}^{\prime\prime}\leq 0$. A knot invariant is extracted from
the intensity distributions by considering the maximal value of the integral
among all embeddings representing a fixed knot type; more precisely, define

$\mathcal{D}(K)=\sup\left\\{\int_{S^{1}}f_{\gamma}(\theta)\mathrm{d}\theta\,\Big{|}\,[\gamma(S^{1})]=K\right\\},$

where square brackets denote the topological type represented by the curve.

###  2.2 The PL setting

An explicit computation of $f_{\gamma}$ and all related quantities is not
feasible for a generic smooth embedding. We therefore extend the framework to
PL curves, as it allows performing computations and statistical analysis. We
consider equilateral PL curves, that is, closed chains whose segments have the
same length. Taking each segment to be of length one, the length of the curve
is the number of edges.

For a given PL embedding of length $N$, we consider the $N$ open curves
obtained by cyclically removing a single edge from the embedding. The
corresponding knot cores are then computed via a probabilistic closure method,
combined with a top-down approach to sub-chain analysis. Specifically, we use
Knoto-ID’s [5] knot core identification algorithm with probabilistic closures.
For each opening, the output consists of the shortest sub-chain obtained by
progressively trimming the open PL curve without changing the dominant knot
type. Once the knot cores are determined, we compute the distribution as
follows: to each vertex in the curve, we associate a value equal to the number
of openings containing it in their core. These values are then normalised by
dividing by the length.

##  3 Results

In our analysis, we consider prime knot types up to $6$ crossings, and non-
trivial connected sums up to $7$ crossings. As a first experiment, we compute
the knot intensity distributions of PL curves closely approximating ideal
embeddings. Then, we analyse randomly generated knotted configurations, and
study the statistical behaviour of distribution, density, and fingerprint by
knot type and as the length of the configurations increases. Lastly, we show
that there is a strong correlation between peaks of the distribution and
strand passages disrupting an embedding’s topology.

###  3.1 Ideal knots

Ideal knots are a special type of knot embeddings, arising in the context of
biologically inspired constructions [11, 12]. A knot embedding is _ideal_ if
it minimises the length over diameter ratio within its isotopy class. It is
still unknown whether there is a unique ideal representative for any given
knot type; in this context, it is noteworthy to recall that in general, ideal
embeddings do not necessarily maximise symmetries [12, Ch. 1.5] nor minimise
occupied volume [13].

Figure 2: (A) Ideal embeddings of the left trefoil $3_{1}$ (top) and
$3_{1}\\#4_{1}$ (bottom). Colour and thickness are proportional to knot
intensity. (B) Radar plots of the knot intensity distributions for ideal
embeddings of prime knots up to $6$ crossings and connected sums (up to
mirroring) up to $7$ crossings. The maxima of the distributions correspond to
crossings. Values of the knot density are recorded below each plot.

Equilateral PL embeddings of ideal knots can be generated using the software
Ridgerunner [14]; outputs are high-resolution approximations of their smooth
counterparts. As a first application of our method, we compute the knot
intensity distribution on this dataset. Results are shown in Figure 2. The
value attained by the knot density on ideal knots, shown in Figure 2(B), is
rather high (cf. Section 3.2). This is due to the fact that, by definition,
ideal embeddings are optimally using their length to form the knot. That
implies that the entanglement is evenly distributed, and even large sub-arcs
will likely possess a topology different from the whole embedding.

###  3.2 Random knots

Next, we consider a dataset consisting of $10^{3}$ random configurations, for
each of the knot types considered above, and lengths between $50$ and $250$
(with a $50$ step increase). The knotted curves are generated as self-avoiding
walks using the Python software Topoly [15].

Figure 3: (A) A random knotted configuration of length $100$ with $3_{1}$
topology. Vertices and edges are coloured by the knot intensity. In the middle
and right columns, the associated radar plots and knot density values. The
entanglement is localised in a small portion of the curve. (B) A random
knotted configuration of length $100$ with $3_{1}$ topology. Vertices and
edges are coloured by the knot intensity. In the middle and right columns, the
associated radar plots and knot density values. The entanglement is spread
throughout a long portion of the embedding.

Figure 3 shows two examples of generated configurations, with trefoil topology
and length 100. The configuration in the top of Figure 3(A) presents a highly
localised entanglement, while the one on the bottom is an example of a shallow
trefoil. The knot intensity distributions correctly identify both cases.
Indeed, high values of the distribution computed from the curve on the top are
concentrated in a short region (see left of (A) and (B)), while the bottom
distribution shows a more homogeneous behaviour. Similarly, the density is
much higher for the curve on the bottom. In both cases, the fingerprint
(Figure 3(C)) is linear with slope $1$ until it reaches the minimal value of
the distribution.

Figure 4: The results of the statistical analysis on our random knot
population. (A) Box plots of the distributions of knot density, by knot type
and length. (B) Average fingerprints for each knot type. As in (A), there is a
clear clustering with respect to crossing number, and separation of the
averages densities (_i.e._ the maxima of the fingerprints). Further, it is
apparent from the plots that this stratification persists even when
restricting to the (possibly disconnected) sub-chains whose intensity
distribution less than a given threshold.

To investigate on the behaviour of the knot intensity distribution for
different knot types, we subsequently compute the distribution, density and
fingerprint of each configuration in the dataset. Results are shown in Figure
4. The plot shows a dependency of knot densities on the crossing number. More
precisely, prime knots with the same crossing number exhibit very similar knot
density distributions, and those distributions are ranked by crossing number,
consistently throughout the range of lengths considered. This validates the
intuitive idea that more complex knots “occupy” longer regions at fixed
length. Note that the average density is inversely proportional to the
embedding’s length; this is consistent with the idea that knot domains tend to
be very tight [16]. For composite knots, we observe a clear narrowing of the
densities with respect to prime knots with the same crossing number, as well
as an increase in median values. Again, this is in line with previous studies
[17] and suggests that prime factors in composite knots tend to spread out
rather than merge, leading to a more homogeneous distribution of intensities
and a reduced density variation.

Similarly, the averaged fingerprints shown in Figure 4(B) confirm the presence
of a clear division by crossing number, which persists at all knot lengths;
the same figure implies that the same conclusion holds when restricting to
those sub-chains whose intensity distribution values are below a fixed
threshold. We also report the absence of correlation between knot density and
average writhe, and only a small ($\leq$ 0.3) positive correlation with the
average crossing number.

The average values of $\mathcal{D}$ on the knots within our population are
contained in the plot in Figure 4(B), as they correspond to the fingerprints’
maxima. The maximal values computed do not present a consistent behaviour for
varying length, likely due to noise. It would be interesting to understand to
what extent the maximal knot density can distinguish knots; it is reasonable
to assume that the values of $\mathcal{D}(K)$ should increase in an
approximately monotonic fashion, as a function of the minimal crossing number
of $K$. The computations performed in this paper are however not sufficient to
support this claim.

We also note that the minimum of the knot density for any given knot type
tends to $0$; indeed, it is possible to generate configurations minimising the
value of $\mathcal{D}$ within a fixed knot type: namely, consider a PL
embedding for a knot $K$ realising its _equilateral stick number_ $esn(K)$
[18]. This quantity is an integer valued invariant of knots, defined to be the
minimal number of straight segments of the same length needed to represent a
given knot type. Modify this embedding by adding a sequence of $N-est(K)$
further edges in an unknotted fashion; in this modified embedding, the only
part contributing to the intensity distribution is entirely concentrated in
the portion entailed by the minimal embedding. Therefore, the knot density
will be close to $\frac{esn(K)}{N}$, which converges to $0$ for
$N\rightarrow\infty$.

###  3.3 Knot intensity locates entanglement and non-cosmetic strand passages

The knot intensity of low crossing number ideal knots has peaks in bijection
with crossings, see Figure 2(B); a similar behaviour can be observed in Figure
1(B). A natural question is whether this is a special case of a more general
phenomenon. Namely, we hypothesise that higher knot intensity values correlate
with regions in the knot whose alteration leads to a change in topology. We
test this hypothesis as follows; starting from a random PL trefoil of length
$40$, we perform successive random crankshaft moves, allowing non-phantom
moves as well. At each strand passage, we record the starting and ending PL
curves, and their corresponding knot types. We label as cosmetic the strand
passages preserving the topology, and discard cosmetic changes between trivial
knots.

Figure 5: (A) The superposition of two PL embeddings, differing by a single
non-phantom and non-cosmetic crankshaft move. The two associated knot types
are the trefoil and the trivial knot. (A) Bar plots for the normalised values
of the intensity distribution (pink), and the same values restricted to
crossing change sites in the cosmetic (light blue) and non-cosmetic (dark
blue) cases.

Each such pair of embeddings identifies two points, corresponding to the
centre of the crankshaft move in each embedding, and to the other segment
where the self-intersection occurs. The value of the intensity distribution is
then computed at each of these points. We keep the highest among these two
values, and normalise it by the maximum of the corresponding distribution. The
idea is that if the initial assumption is correct, then the values on non-
cosmetic crossing changes should be on average higher than the cosmetic ones.
The results of this analysis, displayed in Figure 5, strongly confirm the
hypothesis. Indeed, while cosmetic values are distributed similarly to the
total distribution, the non-cosmetic ones present a strong bias towards being
localised at the maximum. In other words, moves leading to passages altering a
knot’s topology are identified by maximal values of the knot intensity
distribution.

##  4 Availability and implementation

The GitHub repository
https://github.com/agnesebarbensi/knot_intensity_distribution contains the
code to compute the knot intensity distribution for a given PL knot embedding,
as well as the data and code needed to reproduce the results and figures in
the paper.

### Acknowledgements

AB gratefully acknowledges funding through a MACSYS Centre Development
initiative from the School of Mathematics and Statistics, the Faculty of
Science and the Deputy Vice Chancellor Research, University of Melbourne. DC
was supported by Hodgson-Rubinstein’s ARC grant DP190102363 “Classical And
Quantum Invariants Of Low-Dimensional Manifolds”.

## References

## References

  * [1] Pawel Dabrowski-Tumanski, Andrzej Stasiak, and Joanna I Sulkowska.  In search of functional advantages of knots in proteins.  PloS one, 11(11):e0165986–e0165986, 11 2016.
  * [2] Maciej Piejko, Szymon Niewieczerzal, and Joanna I Sulkowska.  The folding of knotted proteins: Distinguishing the distinct behavior of shallow and deep knots.  Israel Journal of Chemistry, 60(7):713–724, 2020.
  * [3] Agnese Barbensi, Naya Yerolemou, Oliver Vipond, Barbara I. Mahler, Pawel Dabrowski-Tumanski, and Dimos Goundaroulis.  A topological selection of folding pathways from native states of knotted proteins.  Symmetry, 13:1670, 2021.
  * [4] Luca Tubiana, Enzo Orlandini, and Cristian Micheletti.  Multiscale entanglement in ring polymers under spherical confinement.  Physical review letters, 107(18):188302, 2011.
  * [5] Julien Dorier, Dimos Goundaroulis, Fabrizio Benedetti, and Andrzej Stasiak.  Knoto-id: a tool to study the entanglement of open protein chains using the concept of knotoids.  Bioinformatics, 34(19):3402–3404, 2018.
  * [6] DW Sumners and SG Whittington.  Detecting knots in self-avoiding walks.  Journal of Physics A: Mathematical and General, 23(8):1471, 1990\.
  * [7] B Marcone, E Orlandini, AL Stella, and F Zonta.  What is the length of a knot in a polymer?  Journal of Physics A: Mathematical and General, 38(1):L15, 2004\.
  * [8] Kenneth Millett, Akos Dobay, and Andrzej Stasiak.  Linear random knots and their scaling behavior.  Macromolecules, 38(2):601–606, 2005.
  * [9] Luca Tubiana, Enzo Orlandini, and Cristian Micheletti.  Probing the entanglement and locating knots in ring polymers: a comparative study of different arc closure schemes.  Progress of Theoretical Physics Supplement, 191:192–204, 2011.
  * [10] Eric J Rawdon, Kenneth C Millett, and Andrzej Stasiak.  Subknots in ideal knots, random knots and knotted proteins.  Scientific reports, 5(1):1–8, 2015.
  * [11] Vsevolod Katritch, Jan Bednar, Didier Michoud, Robert G Scharein, Jacques Dubochet, and Andrzej Stasiak.  Geometry and physics of knots.  Nature, 384(6605):142–145, 1996.
  * [12] Andrzej Stasiak and Vsevolod Katritch.  Ideal knots, volume 19.  World Scientific, 1998.
  * [13] Alexander R Klotz.  The tightest knot is not necessarily the smallest.  arXiv preprint arXiv:2111.08218, 2021.
  * [14] Ted Ashton, Jason Cantarella, Michael Piatek, and Eric J Rawdon.  Knot tightening by constrained gradient descent.  Experimental Mathematics, 20(1):57–90, 2011.
  * [15] Pawel Dabrowski-Tumanski, Pawel Rubach, Wanda Niemyska, Bartosz Ambrozy Gren, and Joanna Ida Sulkowska.  Topoly: Python package to analyze topology of polymers.  Briefings in Bioinformatics, 22(3):bbaa196, 2021.
  * [16] Xiaozhong Zheng and Alexander Vologodskii.  Tightness of knots in a polymer chain.  Physical Review E, 81(4):041806, 2010.
  * [17] Luca Tubiana.  Computational study on the progressive factorization of composite polymer knots into separated prime components.  Physical Review E, 89(5):052602, 2014.
  * [18] Eric J Rawdon and Robert G Scharein.  Upper bounds for equilateral stick numbers.  Contemporary Mathematics, 304:55–76, 2002.