11institutetext: Luxembourg Institute of Science and Technology, Luxembourg
11email<EMAIL_ADDRESS>22institutetext: University of Geneva,
Switzerland
22email<EMAIL_ADDRESS>Luxembourg Institute of
Science and Technology, Luxembourg
11email<EMAIL_ADDRESS>22institutetext: University of Geneva,
Switzerland
22email<EMAIL_ADDRESS>
# Cold Start Active Learning Strategies in the Context of Imbalanced
Classification

Etienne Brangbour 1122 Pierrick Bruneau 11 Thomas Tamisier 11
Stéphane Marchand-Maillet 22

###### Abstract

We present novel active learning strategies dedicated to providing a solution
to the cold start stage, i.e. initializing the classification of a large set
of data with no attached labels. Moreover, proposed strategies are designed to
handle an imbalanced context in which random selection is highly inefficient.
Specifically, our active learning iterations address label scarcity and
imbalance using element scores, combining information extracted from a
clustering structure to a label propagation model. The strategy is illustrated
by a case study on annotating Twitter content w.r.t. testimonies of a real
flood event. We show that our method effectively copes with class imbalance,
by boosting the recall of samples from the minority class.

###### Keywords:

Active Learning Cold Start Imbalanced Data Label Propagation.

##  1 Introduction

Learning a classification model usually happens by fitting a model (e.g.
multilayer neural networks [14], SVM [19]) using independent labeled training
and validation data sets. Trained models are then used in a production
environment, where labels are unknown and to be predicted. However, in real
applications, while collecting and storing large amounts of unlabeled data has
become fairly straightforward, they come without supervision. The labels are
often implicit, i.e. only experts or users are able to tell to which class a
given data item belongs to. Also, this operation is time consuming and costly.

Methods from the active learning domain are aimed at supporting such
situations [20]. In brief, starting from an initial classification model
estimated using a small subset of labeled data (comparatively to the amount of
unlabeled data that has been collected), the core of active learning is to
design strategies for sampling data items from the large unlabeled collection
in a way that will be most likely to improve the classifier. Such data are
submitted to an oracle for annotation, per batches or one by one. Returned
labeled elements are integrated to the model training set and the
classification model is retrained. The procedure is iterated until some
convergence criterion is matched, or a predefined budget for annotation is
consumed.

Imbalanced training sets are problematic for learning classification models,
and are addressed with specific solutions [15]. However, in the context of
active learning, especially at the cold start stage where no labels are
available, this yields a _chicken and egg problem_ : sampling an initial
training set at random is highly likely to yield only negative elements. The
initial resulting classifier will hence be poor, harming any active learning
strategy. This leads to poor convergence, that contradicts the spirit of
active learning that aims at _efficient labeling_. This is critical especially
in a crowdsourcing context, where annotations are tied to a financial cost,
and labeling many redundant elements should be avoided.

As an answer to this typical _needle in the haystack_ problem, we propose
novel active learning strategies and algorithms that jointly exploit a
clustering structure and a semi-supervised label propagation model, as means
to increase chances to label minority class elements early in the process,
while sampling from the overall data distribution in a faithful way. After
recalling the related work, we expose the rationale of our methodology in
Section 3. Specifically, after emphasizing elements from the literature that
serve as our cluster cluster quality and label propagation step, we introduce
our contributed algorithms and strategies, that build upon these elements. A
real use case, along with data collection and preprocessing guidelines, are
then exposed in Section 4. The use case serves as experimental testbed to
evaluate the effectiveness of our approach, and the relative performance of
proposed algorithmic variants.

##  2 Related Work

Imbalance occurs when severe class distribution skew is observed in the
labeled data, or some classes are under-represented [15]. Without adaptation,
fitted models tend to reach 100% accuracy for the majority class, but close to
0% for the minority class. Most methods are based on oversampling the minority
class or undersampling the majority class. Informed undersampling is based on
model ensembling or kNN classification. For over-sampling, instead of basic
replacement, synthesis according to nearest neighbor information may be
considered [6], or be combined with boosting [7]. The authors define data set
complexity as its tendency to feature overlapping classes and multiple
subconcepts. In the case of imbalanced data, relevant metrics are precision
and recall, ROC curves, and cost curves.

Closely related to cold start situations, few-shot learning is presented as
the context where a limited number of labeled examples is available [25]. A
possible scenario is the reduction of labeled data gathering effort. In their
taxonomy, active learning and semi-supervised learning are known as two
instances of weakly supervised learning. To circumvent the difficulty to learn
with limited supervision, methods typically resort to prior knowledge. Semi-
supervised learning and active learning are based on the exploitation of
unlabeled data. Douze et al. apply a semi-supervised label propagation
algorithm [30] for few-shot learning with large image collections [9]. Few
labeled and many unlabeled images are embedded using a pre-trained
convolutional model. A semi-supervised model then extends the labeling to the
unlabeled data. They use large similarity graphs based on nearest neighbors
for propagation, with the claimed possibility to scale up to millions of
elements using an adapted algorithm and library [16].

When semi-supervised approaches aim at getting the most out of a small labeled
set, active learning considers a dynamic setup, where labels are acquired in
sequence [20]. Active learning iterations embody this setup, with batches of
elements queried for labels to an oracle. The active learning strategy defines
how these elements are chosen at each iteration. For instance, uncertainty
sampling strategies query elements in regions where a tentative classifier,
trained with the currently available labeled data, is the least confident
[18]. Query-by-committee uses ensembles of models to reduce disagreement among
models [21]. The semi-supervised approach by Wu et al. [26] exploits the most
confident predictions, and differs significantly from active learning schemes
such as uncertainty sampling, where elements are selected for query in the
most uncertain areas of the data space. This highlights that semi-supervised
approaches cannot be adapted to active learning contexts in a straightforward
way.

Ertekin et al. implement active learning in the context of a SVM [12]. They
implement a strategy inspired by uncertainty sampling, by querying elements in
the vicinity of the separating hyperplane characterizing the SVM model.
Specifically, they take a random sample of unlabeled data at each step, and
rank them according to their informativeness w.r.t. current hyperplane. They
disregard specific adaptations to class imbalance, by observing that imbalance
is less severe in the class separating regions, under the assumption of
locally Gaussian-distributed data classes. In a classical uncertainty sampling
scheme, imbalance is addressed using a boosting step [29]. However, the
technique works under the assumption that a sufficiently large labeled data
set is available initially, in order to train an acceptable initial model. As
fit with imbalanced problems, they use recall as a performance metric.

Observing that cold start situations remain mostly unaddressed by the active
learning literature, and are critical in the context of imbalanced problems,
in [3] the general idea is to use a clustering structure to guide batch
sampling. The underlying hypothesis is that the label information acquired in
high quality clusters would be more effectively propagated to unlabeled
elements using a semi-supervised algorithm. A cluster quality index is
combined to an impurity index, reflecting the entropy of per-cluster collected
ground truth labels. Clusters are ranked according to the index, and sampling
is performed in top clusters. Ranks are updated at each active learning
iteration.

##  3 Proposed Methodology

We assume the distribution skew characteristic of class imbalance is expected,
which is the case in many real-life contexts (e.g. biomedical applications,
fraud detection, network intrusion [15]). Combining a clustering structure to
partial supervision has been explored in a similar way ([3] and to some extent
[17]). However, with highly imbalanced and complex data sets (i.e. overlapping
classes, multiple subconcepts), the likelihood that only labels from the
majority class are returned for a sample of any cluster is high, which causes
the proposed impurity criterion [3] to discard clusters featuring more than
average minority class content too early. Alternatively, using a semi-
supervised model will allow to gracefully integrate label feedback.

In the next section, we motivate the usage of the conductance criterion [1] as
a cluster quality score, that allows us to rank clusters according to the
information feedback expected if sampling elements from them in the next
active learning step. We then shortly review the soft-supervised model
proposed by Subramanya and Bilmes [22], that acts as the label propagation
model updated at each active learning step in view to estimate entropies
associated to unlabeled elements, and thus implement a per-element score used
for sampling elements to send to the oracle.

###  3.1 Cluster Quality Criterion

Let us consider a partially labeled data set
$\mathcal{X}=\\{x_{i}\\}_{i\in\llbracket 1,N\rrbracket}$. We also consider $C$
possible ground truth classes for elements, indexed with integers from 1 to
$C$. We build the set $\mathcal{T}=\\{t_{i}\\}_{i\in\llbracket 1,N\rrbracket}$
of partial labels, with 0 as the placeholder for missing labels, and
$t_{i}\in\llbracket 1,C\rrbracket$ otherwise. The set of labeled elements is
then $\mathcal{L}=\\{x_{i}\\}_{t_{i}>0}$. In the cold start context considered
in this paper, this set will be initially empty.

Let us also assume a clustering algorithm has been applied to the data set
$\mathcal{X}$, yielding $K$ clusters, and a set of $N$ cluster labels
$\mathcal{Y}=\\{y_{i}\\}_{i\in\llbracket 1,N\rrbracket}$ with
$y_{i}\in\llbracket 1,K\rrbracket$. Few unsupervised quality criteria can be
decomposed per-cluster in a straightforward manner [3], thus enabling the
computation of individual cluster quality scores. The conductance [1] offers
this possibility, while having been recognized as showing good agreement to
supervised criteria in the context of graph clustering [11], and no explicit
requirement of spherical clusters. Using it requires converting pairwise
Euclidean distances $d_{ij}$ between elements in $\mathcal{X}$ to edge weights
(or similarities) $w_{ij}$ scaled in $[0,1]$, which can be easily performed
e.g. using $w_{ij}=e^{-d_{ij}^{2}}$. Let $k\in\llbracket 1,K\rrbracket$ be a
cluster index. Let also $\mathcal{I}_{k}$ the set of members of cluster $k$,
i.e. the subset of $\mathcal{X}$ so that $x_{i}\in\mathcal{I}_{k}\text{ iif
}y_{i}=k$. The conductance of cluster $k$ is defined as:

$\Phi_{k}=1-\frac{\sum_{x_{i}\in\mathcal{I}_{k},x_{j}\not\in\mathcal{I}_{k}}w_{ij}}{\min(a_{k},a_{\bar{k}})}$
(1)

with $a_{k}=\sum_{x_{i}\in\mathcal{I}_{k},x_{j}\in\llbracket
1,N\rrbracket}w_{ij}$ and
$a_{\bar{k}}=\sum_{x_{i}\not\in\mathcal{I}_{k},x_{j}\in\llbracket
1,N\rrbracket}w_{ij}$. Maximal conductance means a dense and well separated
cluster. Per-cluster conductance already ranges in $[0,1]$, e.g. the overall
conductance of a clustering is obtained by averaging per-cluster conductance.
This means conductance can directly be used as a quality criterion to rank
clusters. Also, conductance accounts for cluster size, i.e. intrinsically to
its definition, small outlying but compact clusters will have low conductance.
We verified this is indeed the case with validation experiments using UCI data
sets [10].

###  3.2 Label Propagation Step

In this section we recall the semi-supervised label propagation model proposed
by Subramanya and Bilmes [22]. It is closely related to [30], but in addition
explicitly assigns class probability distributions to elements, on which our
algorithms proposed in the next section rely. Label probability distributions
$p_{i}$ and $q_{i}$ are hence defined for element $x_{i}\in\mathcal{X}$, so
that their $c^{\text{th}}$ element $p_{i}(c)=q_{i}(c)=P(t_{i}=c)$, with
$c\in\llbracket 1,C\rrbracket$. Also, probability distributions $r_{i}$ for
elements in the labeled set $\mathcal{L}$ are defined so that
$r_{i}(c)=1\text{ iif }t_{i}=c$, 0 else. For the consistency of definitions,
$r_{i}$ is defined for all elements in $\mathcal{X}$, but is always 0 for
unlabeled elements. Then they define and minimize the following objective
function:

$\mathcal{C}(p,q)=\sum_{x_{n}\in\mathcal{L}}\text{KL}(r_{i}||q_{i})+\mu\sum_{x_{i}\in\mathcal{X}}\sum_{x_{j}\in\mathcal{X}}w_{ij}^{\prime}KL(p_{i}||q_{j})-\nu\sum_{x_{i}\in\mathcal{X}}H(p_{i})$
(2)

with $KL(p||q)$ the Kullback-Leibler divergence of $p$ w.r.t. $q$, $H(p)$ the
entropy of $p$, $w_{ij}^{\prime}=w_{ij}+\alpha.\delta(i=j)$, and $\delta$ the
function equalling 1 if its parametrized condition is verified, 0 else.
Intuitively, the objective function pushes probability distributions of
neighboring points to be as similar as possible, while enforcing the labels
provided in $\mathcal{L}$ as much as possible. The last term ensures that
maximal entropy (i.e. $p_{i}(c)=\nicefrac{{1}}{{C}}\text{ }\forall c$) is set
by default when no neighboring information is available. We see that the
algorithm depends on 3 hyper-parameters: $\mu$, $\nu$ and $\alpha$. This
objective function is convex, and can be estimated with the alternating
minimization algorithm, that iterates the following closed form update
formulas until convergence:

$\displaystyle p^{(n)}_{i}(c)$
$\displaystyle\propto\exp\frac{\beta_{i}^{(n-1)}(c)}{\gamma_{i}}$
$\displaystyle q^{(n)}_{i}(c)$
$\displaystyle=\frac{r_{i}(c)+\mu\sum_{x_{j}\in\mathcal{X}}{w_{ji}^{\prime}p_{j}^{(n)}(c)}}{\delta(x_{i}\in\mathcal{L})+\mu\sum_{x_{j}\in\mathcal{X}}{w_{ji}^{\prime}}}$
(3) $\displaystyle\gamma_{i}$
$\displaystyle=\nu+\mu\sum_{x_{j}\in\mathcal{X}}{w_{ij}^{\prime}}$
$\displaystyle\beta_{i}^{(n-1)}(c)$
$\displaystyle=-\nu+\mu\sum_{x_{j}\in\mathcal{X}}{w_{ij}^{\prime}(\log
q_{j}^{(n-1)}(c)-1)}$

The $n$ superscript denotes estimates at iteration $n$. As means to be
consistent with the entropy term in Equation (2), all $p_{i}$ and $q_{i}$ are
initialized with $\nicefrac{{1}}{{C}}\text{ }\forall c$. Let us note that
$p_{i}$ and $q_{i}$ (instead of only $p_{i}$) are mathematical artifacts meant
to enable this algorithm. They prove that at convergence $p=q$, so both can be
used afterwards.

In the present paper, rather than predicting classes for unlabeled elements,
we are interested in selecting elements to be annotated by an oracle. The
entropy terms reflects to which extent we are uncertain about the label of an
element, so elements with high associated entropy are good candidates for
selection. Also, we note the semi-supervised model in this section does not
account for imbalance, so its usage for class prediction would be highly
biased in favor of the majority class in such a context. While incorporating
class frequency priors as in [28] could be studied, we emphasize our focus on
class entropy in an active learning context. Correction for imbalance is not
necessary as the ranking of elements w.r.t. estimated entropy will focus on
areas where classes are overlapping, regardless of imbalance. In the next
section, we discuss how the introduced cluster quality criterion and label
propagation step are combined into active learning strategies.

###  3.3 Active Learning Strategies

Input: $\mathcal{X}$, $\\{\mathcal{I}_{k}\\}$, $n_{\text{query}}$,
$n_{\text{pc}}$, $n_{\text{iter}}$, $\alpha$, $\nu$, $\mu$

Output: $n_{\text{query}}\times n_{\text{iter}}$ elements in $\mathcal{L}$

1 Compute similarities $\\{w_{ij}\\}$

2 Cluster scores $\leftarrow\\{\phi_{k}\\}$

3 Sort cluster scores in decreasing order

4 $q\leftarrow\emptyset$

5 for  _$k^{\prime}\in\nicefrac{{n_{\text{query}}}}{{n_{\text{pc}}}}$ first
clusters_ do

6 $q\leftarrow q\cup\\{$ sample $n_{\text{pc}}$ elements from
$\mathcal{I}_{k^{\prime}}\\}$

7

8$\mathcal{L}\leftarrow$ oracle feedback for $q$

9 Initialize semi-supervised model $\mathcal{M}$ with maximal $H(p_{i})$

10 Update $\mathcal{M}$ with $\mathcal{L}$

11

12for  _$t\in 1\dots n_{\text{iter}}$_ do

13 Update cluster scores using $H(p_{i})$

14 Sort cluster scores in decreasing order

15 $q\leftarrow\emptyset$

16 for  _$k^{\prime}\in\nicefrac{{n_{\text{query}}}}{{n_{\text{pc}}}}$ first
clusters_ do

17 $q\leftarrow q\cup\\{$ sample $n_{\text{pc}}$ elements from
$\mathcal{I}_{k^{\prime}}\\}$

18

19 $\mathcal{L}\leftarrow$ oracle feedback for $q$

20 Update $\mathcal{M}$ with $\mathcal{L}$

21

Algorithm 1 Strategy with cluster ranking

By contrast to other active learning models from the literature (e.g. [12]),
we aim at strategies focused on increasing the chances of querying elements
from the minority class. Our intuition is that when little or no label
information is available at the beginning of the active learning procedure,
sampling preferably from data space regions with higher density is likely to
yield more informative feedback for a label propagation model. A
classification model is maintained through the execution of the strategy, but
its main objective is to obtain a labeled set with less imbalance, but still
representative of the initial unlabeled data distribution. The algorithm will
then tend to ignore regions where a given (typically the majority) label can
be propagated easily, and focus on elements with high associated entropy.
These come either from yet unexplored regions in the data space, or regions
featuring overlapping classes. Updating an actual semi-supervised model,
instead of computing statistics from the oracle feedback, allows to rank
elements according to their specific estimated entropy, and avoids aggressive
discards. This design can be related to uncertainty sampling [18], as
unlabeled elements with maximal associated entropy can be thought as close to
implicit decision boundaries. We propose several ways to use models described
in Sections 3.1 and 3.2, summarized by Algorithms 1 and 2.

In particular, we emphasize that updates of model $\mathcal{M}$ at each active
learning step (lines 1 and 2 in Algorithms 1 and 2, respectively) use the
current estimates for $p$ and $q$ distributions (see Equations (3)). At each
step, $\mathcal{M}$ integrates the elements that have just been added to
$\mathcal{L}$ (materialized by $r_{i}$ distributions in Equation (2)).

Input: $\mathcal{X}$, $\\{\mathcal{I}_{k}\\}$, $n_{\text{query}}$,
$n_{\text{pc}}$, $n_{\text{iter}}$, $\alpha$, $\nu$, $\mu$

Output: $n_{\text{query}}\times n_{\text{iter}}$ elements in $\mathcal{L}$

1 Same as Algorithm 1 up to line 1

2 for  _$t\in 1\dots n_{\text{iter}}$_ do

3 Update element scores for $\mathcal{X}\setminus\mathcal{L}$ using $H(p_{i})$

4 $q\leftarrow n_{\text{query}}$ first elements in
$\mathcal{X}\setminus\mathcal{L}$ w.r.t. scores

5 $\mathcal{L}\leftarrow$ oracle feedback for $q$

6 Update $\mathcal{M}$ with $\mathcal{L}$

7

Algorithm 2 Strategy with element ranking

In our experiments in the next section, we test 3 alternative methods for
computing the similarities (Line 1 in Algorithm 1) that are used as input to
both conductance and label propagation steps:

  * •

The cluster (_C_) similarity: $w_{ij}=1$ if elements $x_{i}$ and $x_{j}$ are
in the same $\mathcal{I}_{k}$,

  * •

The nearest neighbor (_NN_) similarity: $w_{ij}=1$ if $x_{j}$ is among the
$\kappa$ nearest neighbors of $x_{i}$ w.r.t. Euclidean distance $d$, 0 else,

  * •

The Radial Basis Function (_RBF_) similarity with local scaling:
$w_{ij}=\frac{\exp{-d^{2}}}{\sigma_{i}\sigma_{j}}$. This local scaling was
proposed by Zelnik-Manor and Perona [27]. We used the 2% quantile of the
distribution of distances to $x_{i}$ as $\sigma_{i}$ [4].

Using _C_ will estimate the value of using cluster membership itself as a
similarity function. _RBF_ with local scaling accounts for the potential
variations of density in the data set. By focusing on neighborhoods without
explicit account of distances, we expect that using the _NN_ similarity in
Equation (2) will mechanically put less attention on the majority class, hence
effectively accounting for class imbalance. Also, we test 4 alternative
methods for computing cluster and element scores after the first algorithm
step (which always uses $\phi_{k}$, Line 1 in Algorithm 1):

  * •

Entropy only cluster (_EOC_) score for cluster $k$ is
$\frac{1}{|\mathcal{I}_{k}|}\sum_{x_{i}\in\mathcal{I}_{k}}{H(p_{i})}$,

  * •

Weighted entropy cluster (_WEC_) score for cluster $k$ is
$\phi_{k}.\textit{EOC}$,

  * •

Entropy only element (_EOE_) score for element $x_{i}$ is $H(p_{i})$,

  * •

Weighted entropy element (_WEE_) score for element $x_{i}\in\mathcal{I}_{k}$
is $\phi_{k}.H(p_{i})$

These score computation variants mainly differ by their usage of entropy
information alone, or combined to cluster quality scores. If entropy
information is used alone, then clusters are only used for the first active
learning step, when stricly no labels are known yet.

##  4 Experimental Section

###  4.1 Use Case Description

The proposed experimental use case focuses as detecting content posted by
people who have witnessed hurricane Harvey, that hit Texas and Louisiana in
August 2017111https://en.wikipedia.org/wiki/Hurricane_Harvey. The data we
collected are all Tweets with location fields overlapping an area of
approximately 40.000 $\text{km}^{2}$ around Houston, posted in between August
the nineteenth and September the twenty-first of 2017. For the experiments in
this section, we randomly extracted 10.000 elements among tweets featuring at
least 3 words, and a location field reflecting a surface smaller than 350
$\text{km}^{2}$.

We want to classify the tweets in 3 categories: Positively Relevant (PR) if
the tweet reveals that the user is currently in a flooded area, Negatively
Relevant (NR), if the tweet reveals that the user is not currently in a
flooded area, or Irrelevant (IR), if the tweet contains no information
regarding the flood. We manually annotated a random subset of 1820 elements
among which 1669 are irrelevant, 96 are negatively relevant and 55 positively
relevant. The remaining 8120 elements remained unlabeled. The annotated sample
has approximately 9% relevant (i.e. PR+NR) elements. A significant imbalance
is thus expected overall.

In order to estimate a label proxy of the remaining unlabeled set, we trained
a SVM classifier with 80% of the annotated dataset and tested it on the entire
annotated dataset. We compute the F1 score by considering IR as negative class
and PR+NR as positive class. Over 10 runs we obtained an average F1 of 0.74.
Then we used the classifier to predict the labels of the unlabeled dataset.
The resulting proxy label population is (IR: 9377, PR: 109, NR: 514), which
results in 6% relevant content. The disclosure of these proxy labels is used
as the oracle in our experiments.

###  4.2 Data Representation

We analyze Twitter posts from two perspectives: their textual content, and
their spatio-temporal coordinates. Applying classification or clustering
algorithms to textual content typically requires a preprocessing step, where
the piece of text is _embedded_ in a high-dimensional numerical space, hence
facilitating further calculations. For the experiments, we use a character-
based language model, specially adapted to Twitter content by using hashtag
prediction as proxy task [8]. Specifically, we use the 200-dimensional output
vectors of a Transformer network [23] trained as specified in [8] as textual
embedding, as we found it led to better performance and denser vectors.

A flood being a natural disaster tied to space and time, we also extracted a
spatio-temporal representation of the tweet, which consists in the latitude,
longitude and surface on the location field, and the number of hours between
the tweet and the first tweet from the dataset. We extracted clusters using
the two representation spaces taken independently. Hence, according to
definitions used in Section 3.1, we obtain two cluster label vectors,
$\mathcal{Y}_{\text{text}}$ and $\mathcal{Y}_{\text{st}}$ (where _st_ stands
for _spatio-temporal_). $\mathcal{Y}_{\text{st}}$ is extracted using Gaussian
mixtures estimated using the EM algorithm [2], with the number of cluster
chosen heuristically as the number of days that separates the first tweet from
the last in the dataset. $\mathcal{Y}_{\text{text}}$ is obtained using
Affinity Propagation [13] combined to local scaling [27] in order to cope with
local variations of data density in the language model space.
$\mathcal{Y}_{\text{text}}$ features 29 clusters, and
$\mathcal{Y}_{\text{st}}$ 28 clusters.

###  4.3 Combining Cluster Quality Scores

Combining heterogeneous representation spaces as described in the previous
section can be related to subspace clustering [24]. However, in our case the
aim is to use spatio-temporally homogeneous clusters, so we rather consider
the Cartesian product of two clustering structures. Formally, we build
$\mathcal{Y}_{\text{text}\times\text{st}}$ out of independent cluster label
vectors. 787 clusters result from this product, with many singletons or very
small clusters. Scores for clusters in
$\mathcal{Y}_{\text{text}\times\text{st}}$ average scores of respective
clusters in $\mathcal{Y}_{\text{text}}$ and $\mathcal{Y}_{\text{st}}$ computed
separately. The text representation being 200 dimensions and the spatio-
temporal 4 dimensions, we rescale their associated distance matrices w.r.t.
$\chi^{2}$ distributions [5] in order to have comparable conductance scores.

###  4.4 Results and Interpretation

As our goal is to boost chances of labeling minority class elements with a
limited annotation budget, we are evaluating our strategies by monitoring the
recall of minority classes throughout the active learning process. At each
iteration we keep the track of the acquired labels and update the metric. Let
$\mathcal{L}_{p}$ and $\mathcal{L}_{n}$ be the set of PR and NR proxy labels,
and $\mathcal{L}_{t}$ the set of all annotations returned by the oracle up to
iteration $t$. For each iteration we can compute the recall scores of minority
classes as
$r_{t}=\frac{|\mathcal{L}_{t}\bigcap(\mathcal{L}_{p}\bigcup\mathcal{L}_{n})|}{|(\mathcal{L}_{p}\bigcup\mathcal{L}_{n})|}$.

We ran Algorithms 1 and 2 with the following parameters:
$n_{\text{query}}=50$, $n_{\text{iter}}=50$, $n_{\text{pc}}=3$. $\alpha$,
$\nu$ and $\mu$ were set with 2, $10^{-3}$ and $10^{-3}$ as recommended by
Subramanya and Bilmes [22]. In Figure 1, we compare 6 algorithmic variants
named according to the nomenclature given in Section 3.3 (e.g. NN-EOE-2
designates Algorithm 2 with NN similarity and EOE score function). As a
reference, we also show the curves obtained if query elements are sampled
completely at random. Each experiment proceeds until
${\nicefrac{{1}}{{4}}}^{\text{th}}$ of the data set is annotated by the
oracle. The displayed curves average the results of 5 independent experiments.

Figure 1: Recall curves for minority classes as a function of active learning
iteration.

Strategies using the cluster similarity (i.e. prefixed by _C_) exhibit no
significant performance improvement compared to randomness. Cluster membership
hence does not appear to convey valuable information regarding the
classification task at hand, and Algorithm 1, based on sampling w.r.t. per-
cluster ranks is not revealed as effective. Algorithm 2 with WEE scores (i.e.
which weigh element-wise entropies with respective cluster conductances) also
yields disappointing results. With the _RBF_ similarity, this algorithmic
variant actually does not perform better than random. However, it becomes
significantly better than random performance when used in conjunction with the
_NN_ similarity, with almost twice more minority class elements retrieved by
the end of the active learning iterations.

The best performance is reached by Algorithm 2 when using only entropies
estimated by the semi-supervised model as scores for sample selection. Again,
the _NN_ similarity significantly outperforms the _RBF_ similarity. In the
end, _NN-EOE-2_ reaches more that 60% recall of the minority classes with
limited budget, which is approximately 3 times more than the random strategy.
Overall, it appears that ranking w.r.t. entropies returned by the semi-
supervised model already integrate the ability to effectively explore the data
set. Further weighting by cluster quality scores yields significant
degradation in the course of the algorithm, limiting its potential usefulness
to the starting stage. We also see that _NN_ -based variants systematically
overperform w.r.t. their _RBF_ -based counterpart, which confirms the adequacy
of _NN_ similarity in an imbalanced context.

##  5 Conclusion

A first important contribution in this paper has been to expose the
peculiarities when trying to combine active learning methods to imbalanced
cold-start classification problems. In this context, we designed active
learning strategies, where we hypothesized a synergy between the exploitation
of a clustering structure and a semi-supervised label propagation model.
Several similarity functions were tested as means to effectively address class
imbalance. We compared several algorithmic variants on a real-world imbalanced
classification problem related to detecting information related to floods on
Twitter. In particular, we disclosed a way to combine the information carried
by multiple subspaces, illustrated by our use case about extracting spatio-
temporally aware information from a Twitter corpus. In the end, despite the
absence of improvement brought by the clustering structure, an effective
algorithmic variant was highlighted, which tripled the recall of minority
class elements in a heavily imbalanced classification problem.

A possible reason for the ineffectiveness of using the clustering structure in
our experiments may be its poor alignment with the minority class density.
Ideally, we would like the granularity of the clustering structure guiding the
active learning strategy to adapt to the label feedback. An idea would be to
exploit the dendrogram resulting from a hierarchical clustering method, such
as Hierarchical Agglomerative Clustering (HAC).

##  6 Acknowledgements

This work was performed in the context of the Publimape project, funded by the
CORE programme of the Luxembourgish National Research Fund (FNR).

## References

  * [1] Almeida, H., Guedes, D., Meira, W., Zaki, M.: Is There a Best Quality Metric for Graph Clusters? In: Machine Learning and Knowledge Discovery in Databases. pp. 44–59. Lecture Notes in Computer Science, Springer (2011)
  * [2] Bishop, C.: Pattern Recognition and Machine Learning. Springer (2006)
  * [3] Brangbour, E., Bruneau, P., Tamisier, T., Marchand-Maillet, S.: Active Learning with Crowdsourcing for the Cold Start of Imbalanced Classifiers. In: Cooperative Design, Visualization, and Engineering. pp. 192–201 (2020)
  * [4] Bruneau, P., Ojtacques, B.: Observations on latent distributions of graph Laplacians. In: EGC. pp. 93–104 (2016)
  * [5] Bruneau, P., Otjacques, B.: A probabilistic model selection criterion for spectral clustering. Intelligent Data Analysis 22(5), 1059–1077 (2018)
  * [6] Chawla, N., Bowyer, K., Hall, L., Kegelmeyer, W.: SMOTE: Synthetic Minority Over-sampling Technique. Journal of Artificial Intelligence Research 16, 321–357 (2002)
  * [7] Chawla, N.V., Lazarevic, A., Hall, L.O., Bowyer, K.W.: SMOTEBoost: Improving Prediction of the Minority Class in Boosting. In: Knowledge Discovery in Databases: PKDD 2003. pp. 107–119 (2003)
  * [8] Dhingra, B., Zhou, Z., Fitzpatrick, D., Muehl, M., Cohen, W.: Tweet2Vec: Character-Based Distributed Representations for Social Media. arXiv:1605.03481 [cs] (2016)
  * [9] Douze, M., Szlam, A., Hariharan, B., Jégou, H.: Low-Shot Learning With Large-Scale Diffusion. In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. pp. 3349–3358 (2018)
  * [10] Dua, D., Graff, C.: UCI machine learning repository (2017), http://archive.ics.uci.edu/ml
  * [11] Emmons, S., Kobourov, S., Gallant, M., Börner, K.: Analysis of Network Clustering Algorithms and Cluster Quality Metrics at Scale. PLOS ONE 11(7), e0159161 (2016)
  * [12] Ertekin, S., Huang, J., Bottou, L., Giles, L.: Learning on the border: active learning in imbalanced data classification. In: Proceedings of the sixteenth ACM conference on Conference on information and knowledge management. pp. 127–136 (2007)
  * [13] Frey, B., Dueck, D.: Clustering by Passing Messages Between Data Points. Science 315(5814), 972–976 (2007)
  * [14] Glorot, X., Bengio, Y.: Understanding the difficulty of training deep feedforward neural networks. In: AISTATS. pp. 249–256 (2010)
  * [15] He, H., Garcia, E.A.: Learning from Imbalanced Data. IEEE Transactions on Knowledge and Data Engineering 21(9), 1263–1284 (2009)
  * [16] Johnson, J., Douze, M., Jégou, H.: Billion-scale similarity search with GPUs. IEEE Transactions on Big Data pp. 1–1 (2019)
  * [17] Kang, J., Ryu, K., Kwon, H.: Using Cluster-Based Sampling to Select Initial Training Set for Active Learning in Text Classification. In: Advances in Knowledge Discovery and Data Mining. pp. 384–388 (2004)
  * [18] Lewis, D.D., Gale, W.A.: A Sequential Algorithm for Training Text Classifiers. In: ACM SIGIR. pp. 3–12 (1994)
  * [19] Scholkopf, B., Smola, A.: Learning with Kernels: Support Vector Machines, Regularization, Optimization, and Beyond. MIT Press, Cambridge, MA, USA (2001)
  * [20] Settles, B.: Active Learning Literature Survey. Technical Report, University of Wisconsin-Madison Department of Computer Sciences (2009), https://minds.wisconsin.edu/handle/1793/60660
  * [21] Seung, H.S., Opper, M., Sompolinsky, H.: Query by committee. In: Proceedings of the fifth annual workshop on Computational learning theory. pp. 287–294 (1992)
  * [22] Subramanya, A., Bilmes, J.: Soft-supervised learning for text classification. In: Proceedings of the Conference on Empirical Methods in Natural Language Processing. pp. 1090–1099 (2008)
  * [23] Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A.N., Kaiser, Ł., Polosukhin, I.: Attention is all you need. In: Advances in neural information processing systems. pp. 5998–6008 (2017)
  * [24] Vidal, R.: Subspace Clustering. IEEE Signal Processing Magazine 28(2), 52–68 (2011)
  * [25] Wang, Y., Yao, Q., Kwok, J.T., Ni, L.M.: Generalizing from a Few Examples: A Survey on Few-shot Learning. ACM Computing Surveys 53(3), 63:1–63:34 (2020)
  * [26] Wu, Y., Lin, Y., Dong, X., Yan, Y., Ouyang, W., Yang, Y.: Exploit the Unknown Gradually: One-Shot Video-Based Person Re-Identification by Stepwise Learning. In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. pp. 5177–5186 (2018)
  * [27] Zelnik-manor, L., Perona, P.: Self-Tuning Spectral Clustering. In: Advances in Neural Information Processing Systems 17, pp. 1601–1608 (2005)
  * [28] Zhou, D., Bousquet, O., Lal, T.N., Weston, J., Schölkopf, B.: Learning with Local and Global Consistency. In: Advances in Neural Information Processing Systems. vol. 16, pp. 321–328 (2003)
  * [29] Zhu, J., Hovy, E.: Active Learning for Word Sense Disambiguation with Methods for Addressing the Class Imbalance Problem. In: Proceedings of the 2007 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning (EMNLP-CoNLL). pp. 783–790 (2007)
  * [30] Zhu, X., Ghahramani, Z., Lafferty, J.: Semi-Supervised Learning Using Gaussian Fields and Harmonic Functions. In: International Conference on Machine Learning. pp. 912–919 (2003)


# Triple gear††thanks: This work is in the public domain.

Saul Schleimer Henry Segerman Mathematics Institute Department of Mathematics
University of Warwick Oklahoma State University Coventry CV4 7AL Stillwater,
OK 74078 United Kingdom USA<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

A relatively common sight in graphic designs is a planar arrangement of three
gears in contact. However, since neighboring gears must rotate in opposite
directions, none of the gears can move. We give a non-planar, and non-frozen,
arrangement of three linked gears.

##  1 Introduction

2pt meridian [Br] at 185 407 longitude [tr] at 10 190 $(1,1)$ curve at 310 160

Figure 1: Curves on a torus.

The mathematician’s _torus_ is simply the crust of a bagel: a surface with one
hole. There are two special kinds of curves on the torus called _meridians_
and _longitudes_. These are the curves obtained by slicing the bagel
vertically or horizontally, respectively. We call a curve on the torus a
_$(p,q)$ curve_ if it crosses a longitude $p$ times and a meridian $q$ times.
See Figure 1.

Helaman Ferguson’s _Umbilic Torus NC_ is a classic work of mathematical art;
topologically it is a torus with a ridge along a $(1,3)$ curve [4]. He has
also designed a complementary sculpture, called the _Umbilic Torus NIST_ ;
here we find a torus with a valley along a $(3,1)$ curve. These complementary
tori are mated in his piece _Umbilic Rolling Link_ , see Figure 2. Note that
the ridge of the NC torus meshes with the valley of the NIST torus. Thus if
one of the tori rotates along itself then so must the other, with speeds in a
ratio of $3:1$.

Figure 2: _Umbilic Rolling Link_ , by Helaman Ferguson.

A closely related piece by Oskar van Deventer inspired this project. His
_Knotted Gear_ 111See http://www.youtube.com/watch?v=ZqiHHlE1SD8 for a video
of the knotted gear in motion. consist of two rings, a thickened $(-3,2)$
curve (a left-handed trefoil) linked with a thickened $(2,-3)$ curve. See
Figure 3. The two rings mesh with speeds in a ratio of $3:2$. We quickly
decided that by varying $p$ and $q$ any rational ratio could, in principle, be
achieved. We next asked “Can this be done with three or more rings?”

Figure 3: _Knotted Gear_ , by Oskar van Deventer.

To formalize this problem we begin with some examples and definitions. An
example of a rigid body is a wheel. An example of a rigid motion is a rotation
of the wheel about its center through some angle. A _movement_ is a one-
parameter family of rigid motions $\\{g_{t}\\}_{t\in\mathbb{R}}$. For example,
consider spinning the wheel about its center with constant angular velocity
$\omega$: then at time $t$, the motion $g_{t}$ is a rotation through $\omega
t$ degrees. Given two motions $m_{1}$ and $m_{2}$, the _composition of $m_{1}$
with $m_{2}$_, denoted $m_{2}\circ m_{1}$, is the motion we get by performing
$m_{1}$ followed by $m_{2}$. A movement $g$ is _simple_ if for any times $s$
and $t$ we have $g_{s+t}=g_{s}\circ g_{t}$. Note that the simple movements are
either stationary, translational, rotational or screw movement. These
movements get their name from the classical simple machines: the lever, the
wheel, the screw, and so on. For example, the spinning wheel is a simple
movement.

Next, a _design_ is a union of rigid bodies in space, with disjoint interiors.
As an example of a design, we may take a wheel on an axle as shown in Figure
4. We add two flanges to the axle to stop the wheel from moving along the
length of the axle.

A _compound movement_ $M$, of $D$, is a collection of movements, one for each
rigid body, which together keep the interiors of the bodies disjoint. In the
example, spin the wheel in one direction while spinning the axle in the other.
As this happens we may additionally translate both through space to give a new
compound movement. In other words, if $M$ is a compound movement of $D$ and
$g$ is any movement then we define a new compound movement $g\circ M$ by
composing all of the movements of $M$ with $g$, moment by moment.

Two compound movements $M$ and $N$ are _equivalent_ if there is a movement $g$
so that $g\circ M=N$. Thus, the two compound movements of wheel plus axle
discussed above are equivalent.

We now restrict the degrees of freedom of $D$ via the following axiom.

  * _Tracked_ : There is a compound movement $M$ of $D$ so that every compound movement of $D$ is equivalent to a time-reparameterization of $M$.

Figure 4: A wheel on an axle.

The wheel plus axle satisfies tracked: we can rotate the wheel on the axle and
there is essentially no other way that they can move relative to each other.
However, an axle with two wheels (again with flanges holding them in place)
does not satisfy tracked. This axiom implies that in $D$, as in many geared
machines, the bodies may move relative to each other in an essentially unique
fashion. We now distinguish the wheel and axle from the designs of Ferguson
and Van Deventer.

  * _Epicyclic_ : For any bodies $A$ and $B$ in the design $D$, if $A$ and $B$ are in contact at some moment then the given movement of $B$, in the frame of reference of $A$, is not simple.

Fixing the axle pointwise, the wheel can only spin about its center, which is
a simple movement. Hence the wheel plus axle is not epicyclic. Note that in
ordinary mechanisms, the parts in contact with the gear-box have simple
movements, in the frame of reference of the box. Such mechanisms are not
epicyclic. In view of this axiom we will refer to _all_ of the rigid bodies in
our design as _gears_.

To simplify our search for a tracked, epicyclic three-component design, we add
the following axiom.

  * _Symmetry_ : Any gear of $D$ may be taken to any other by a rigid motion preserving $D$.

To ensure that $D$ is tracked, we will make a series of assumptions, at each
stage reducing the possible compound movements of the design. To ensure that
$D$ is epicyclic we must do this without using any kind of framework or gear-
box, following Ferguson and Van Deventer. Departing from their work, symmetry
implies that all of our gears must be identical.

##  2 Topology

In this section we prevent compound movements that move the gears arbitrarily
far from each other. We first assume that each gear is a circular ring. Now,
if no pair of rings is linked, then $D$ is globally unlinked [5, Lemma 3.2].
Thus we assume that some pair of rings is linked. For example, this rules out
the Borromean rings.

Figure 5: The three component Hopf link, lying on a torus.

As suggested above, we further restrict our attention to designs with only
three rings. The symmetry condition now implies that all three pairs of rings
are linked. A geometric argument given in Appendix B proves the design $D$ is,
topologically, the three-component Hopf link. Note that this rules out another
natural candidate: the minimally twisted three chain link [6].

Examining cases, the symmetry axiom implies that there is a rigid motion,
$g_{0}$, that acts via an order three permutation222That is, if we apply
$g_{0}$ three times then we are back to where we started. on the components of
$D$. It follows that $g_{0}$ is a rotation about a line in three-space of
order three (i.e. by $120^{\circ}$ in one or the other direction). Our three-
component Hopf link has just two symmetries of order three. Thus, we may
assume that the rings of $D$ are equally spaced $(1,1)$ curves on a torus, as
shown in Figure 5.

Consider the compound movement $M$ that rotates each of the rings about its
center, all with the same speed and handedness. Note that $M$ preserves the
design and obeys the symmetry axiom. Also, in the frame of reference of any
one ring, the movements of the other two are not simple, so a design with this
movement would be epicyclic. In the rest of the paper, we seek a shape for the
individual rings that will satisfy the tracked axiom, using essentially this
compound movement $M$.

##  3 Maximal tori

In any design satisfying the tracked axiom, the gears must remain in contact.
To arrange this we take three congruent rings, linked as in Figure 5, and
gradually increase their thickness; think of blowing up three tubular
balloons. Their orientations may change as the rings bump each other, but we
always maintain the $3$–fold symmetry. Eventually the rings will reach some
maximum thickness, giving an arrangement as in Figure 6a.

To find the positions of the rings at the maximal thickness we solve an
optimization problem. The three circles, each of radius $1$, are arranged so
that rotation by $120^{\circ}$ around the $z$–axis permutes them. We assume
that one of the circles has center on the $x$–axis, at distance $r$ from the
origin. The plane containing this circle is spanned by the vectors
$U=(\cos(\phi),\sin(\phi),0)$ and
$V=(-\sin(\phi)\sin(\theta),\cos(\phi)\sin(\theta),\cos(\theta))$. These
parameters are displayed in Figure 6b.

(a) Three rings arranged as a Hopf link, maximizing thickness among
arrangements with 3–fold rotational symmetry.

2pt $C$ at 129 94 $U$ at 170 140 $V$ at 105 193 $x$ at 253 112 $y$ at 8 200
$z$ at 83 243 $r$ at 96 82 $\theta$ at 115 150 $\phi$ at 183 123.5

(b) Variables for the optimization problem. $U$ is perpendicular to $V$ and
lies in the $x,y$ plane. The line emanating from $C$ is parallel to the $z$
axis.

Figure 6:

Our aim is to maximize the distance between this circle and one of its
rotates, while preserving the topology. Note that there is no closed form for
the minimal distance between two general circles [8]. Thus, a closed form
solution for the optimal values of $r$, $\phi$, and $\theta$ seems unlikely.
However, for our purposes a numerical approximation is good enough.

Ian Agol [1] points out that the optimal configuration should have dihedral
symmetry, and thus $\phi=0$. Here is the heuristic explanation. First, at the
maximal thickness, each ring touches each of the other two in at least two
points. This is because if there is only one point of contact, then the rings
can be rotated to remove that point of contact and allow further thickening.
Second, two linked congruent tori that are tangent to each other at two points
should be related by a rotation of $180^{\circ}$ that exchanges the two
points. This extra symmetry property seems to hold (although we do not know a
proof) and implies the dihedral symmetry, which implies that $\phi=0$.

We numerically obtain, for the other variables, values of $r=0.4950197$ and
$\theta=-0.8560281$. At the maximum, the ring has thickness of $0.3228837$ and
the distance between two core circles is twice this. We set up a coordinate
system on the surface of each ring, a torus, as follows. Each torus is
parameterized by $(\alpha,\beta)\in(-\pi,\pi]\times(-\pi,\pi]$. The parameter
$\alpha$ is in the longitude direction, with $0$ at the vector $U$ and $V$
nearest in the positive direction. The parameter $\beta$ is in the meridian
direction, with $0$ at the biggest longitude (i.e. on the outside of the
torus), and the direction $U\times V$ closest in the positive direction. In
these coordinates the points of contact of this torus with the others are at

$(\alpha,\beta)=(-2.9419218,-1.2298655),\,(-1.9117269,2.9419218),(1.9117269,-2.9419218),\,(2.9419218,1.2298655).$

(a) Three rings arranged with 3–fold rotational symmetry.

(b) If the three rings move out of the symmetrical position, then one or more
of the six points of contact disappears.

Figure 7:

Note there are two points of contact with each of the other tori. By symmetry,
the same is true for the other two tori as well.

Some of the symmetries in these four points come from the dihedral symmetry of
the configuration, but we currently do not know why the number $2.9419218$
appears both as a value for $\alpha$ and for $\beta$, nor why the sum of
$1.2298655$ and $1.9117269$ appears to be $\pi$.

If, at maximal thickness, the rings could move only along their core circles,
then the symmetry axiom would completely determine the compound movement
required by the tracked axiom. Unfortunately this is not the case: if we relax
the $3$–fold symmetry then we can further increase the thickness of the rings;
see Figures 7a and 7b333We expect that maximizing the thickness of the rings
in Figure 7b would restrict them to move only along their core circles. An
interesting future direction is to explore gearing in this configuration..

##  4 Cutting teeth

We now add gear-teeth to the rings; this enforces the 3–fold rotational
symmetry, preventing the configuration of Figure 7b. Recall that symmetry
requires our rings to all rotate at the same speed.

For unlinked gears with parallel axes, the tracked axiom (implied by the
fundamental law of gearing444The fundamental law of gearing states that the
angular velocity ratio between two gears should remain constant as the gears
rotate.) can be obtained using involutes of a circle for the shapes of the
teeth; this was first proposed by Euler [2]. The version of this problem for
skew axes is an area of active research. We looked in particular at work of
Phillips [9, 10] on spatial involute gearing. We implemented his system, but
ran into a serious problem. For any pair of axes, he gives a pair of surfaces
that are tangent at the contact point and curve away from the contact point
towards the two axes. This nicely suits the case when the gear lies on the
side of the flank surface towards the axis, as in most applications. However,
our gears link each other. Thus, it can happen that the gear may lie on the
opposite side of Phillips’ tooth flank. It can even happen that the flank
surfaces are roughly cylindrical, tangent at a point, curving in the same
direction, and with different axes — in this case the two surfaces intersect
in an ‘X’ shape.

So we instead use an ad hoc method. We use one gear to _carve_ the shape of
the mating gear. In hindsight, our method is similar to techniques going back
at least to 1896 [3, Figures 12–19]. Here are the details. We know the
compound movement of the two meshing gears. We choose a point $p$ on the
boundary of the first gear. We consider the path of $p$ in the frame of
reference of the second gear. This path must be outside of, or on the boundary
of, the second gear; so we imagine this path (and many other similar paths)
carving the shape of the second gear, as if from a block of clay.

Note that this process transforms a point of one gear into a excluded path for
the other gear; that is, the dimension increases by one. If we have a proposed
$2$–parameter tooth flank for the first gear, then this carves a $3$–parameter
volume in the frame of reference of the second gear. The appropriate tooth
flank for the second gear would then be part of the boundary of that volume.
In practice, we start with one set of gear teeth on the inside of one ring,
and use it to carve a set of gear teeth for a second. See the steps outlined
in Figure 8. The shapes of the first set of teeth are given by linear
functions in the toroidal coordinates; the exact parameters were chosen with a
fair amount of trial and error to work well with the carving process.

Note that the $\beta$ values of the points of contact on the torus determine
longitudes of the torus that must have gearing on them. The two values
$\beta=-2.9419218$ and $\beta=2.9419218$ are very close to each other near the
smallest longitude on the inside of the ring. These are so close that gear
teeth from the other two rings intended to mesh with one longitude will most
likely interfere with the other. For this reason, we merged these two
longitudes into one gearing pattern, as seen in Figure 8a555The closeness of
these two longitudes may cause problems in producing three gears that rotate
at different speeds.. We follow the steps shown in Figure 8 to produce the
tooth flanks. As is usual in gear design, we truncate to ensure a non-zero
“top land” for the gear teeth. We transport the tooth flanks using the various
symmetries of the design. The flanks are joined to each other with connecting
patches, and the final closed surface is hollowed out; this allows recovery of
unused material from the 3D printing process.

This completes our construction; Figure 8f displays the final result666See
http://www.youtube.com/watch?v=I9IBQVHFeQs for a video of the triple gear in
motion. It can be purchased at http://shpws.me/mQ6F. An STL file is available
at http://www.thingiverse.com/thing:66708.. The gear teeth on each ring are
arranged in three groups, one along the inside longitude of the ring and two
along longitudes towards the outside of the ring. There are the same number of
teeth on each of these, so in principle it might be possible to connect all of
these together into a single twisting gearing pattern wrapping around the
torus. This would have to be done very carefully, to avoid any unintended
collisions between the added parts and the existing gear teeth.

The 3-fold symmetric three-component Hopf link is one of many other
arrangements of linked circles that could lead to tracked, epicyclic designs.
In addition to the configuration shown in Figure 7b, rotationally symmetric
Hopf links with four or five components should be possible. We have also
considered a design based on the minimally twisted six chain link [6], where
neighboring rings are geared while rings two steps around the chain from each
other are in contact but slide smoothly against each other.

(a) Core circles of two of the tori, together with a set of gear teeth on the
inside of the first ring.

(b) A curve offset from a gear tooth, in order to leave a gap between the
eventual gears. Without this, the 3D printing process would produce a single
merged object.

(c) Transforms of the curve in the frame of reference of the second ring.
Points on these curves closest to the core circle of the second ring are
marked.

(d) A curve fitted through these points. By construction, this curve is on the
boundary of the region carved out by the first gear.

(e) Surfaces swept out along curves defined as in the previous steps give the
tooth flanks for the second ring. The curve from Figure 8d is the lower
boundary of the left flank of the gear tooth.

(f) The 3D printed triple gear.

Figure 8: All but the last of these diagrams are screenshots from Rhinoceros,
the CAD software we used. We also relied extensively on Rhinoceros’ Python
scripting interface.

##  5 Driving the triple gear

It is an interesting dexterity challenge to move the triple gear using your
hands. Printed in PA 2200 nylon plastic by selective laser sintering, friction
wins over weight; if you hold two of the gears and rotate them then the third
is pushed out of the 3-fold symmetry position until the mechanism seizes. A
finger positioned against the third gear stops it moving out of place; then
the design moves as intended.

We have also designed a driving mechanism. As shown in Figure 9b, it consists
of a central helical axle, powered by a motor, and a baseplate upon which the
triple gear rests777See http://www.youtube.com/watch?v=QhXjevOY_uk for a video
of the powered triple gear. We thank Adrian Goldwaser for initial prototyping
and Stuart Young for further prototyping and construction of the motorized
base. The baseplate and axle can be purchased at http://shpws.me/nIjE. An STL
file is available at http://www.thingiverse.com/thing:78218.. The tooth cross-
section for the helical axle is designed using essentially the same carving
technique as in Section 4. Since the helix is invariant under a screw motion
it can be inserted into the the triple gear without having to move the gears;
it need not be printed in place.

The axle, with a rotational movement, can be added to the design $D$ with its
original movement; this combination is again epicyclic. However, in reality
this new design tends to prefer the compound movement where all of the
circular gears are at rest with respect to the axle: that is, everything
rotates about the axle at the same speed. This is definitely not epicyclic!
The three cradles on the baseplate prevent this trivial compound motion.

Since rotational and translational movement of the helical axle are
equivalent, we can also drive the triple gear by translating the axle through
it. Thus we can place the triple gear at the top of a long axle and let it
fall downwards under gravity. However, without the baseplate the triple gear
only sometimes moves in the desired epicyclic fashion. It should be possible
to produce a very large circular axle by gently bending the long axle into a
ring. Holding the circular axle vertically and, pulling the axle hand-over-
hand, the triple gear falls endlessly down the other side.

(a) The helical axle screws into the triple gear.

(b) The baseplate and driving axle.

(c) The triple gear with baseplate and driving axle.

Figure 9:

## References

  * [1] Ian Agol, _Maximum thickness of three linked Euclidean solid tori_ , MathOverflow, http://mathoverflow.net/questions/83586 (version: 2011-12-17).
  * [2] Leonhard Euler, _Supplementum de figura dentium rotarum_ , Novi Commentarii academiae scientiarum imperialis Petropolitanae 11 (1767), 207–231.
  * [3] Edwin R. Fellows, _Gear-shaping machine_ , Patent (1896), US 579708, http://www.google.com/patents/US579708.
  * [4] Helaman Ferguson and Claire Ferguson, _Celebrating Mathematics in Stone and Bronze: Umbilic Torus NC vs SC_ , Proceedings of Bridges 2012, (2012) 17–24.
  * [5] Michael H. Freedman and Richard Skora, _Strange actions of groups on spheres_ , Journal of Differential Geometry 25 (1987), 75–98.
  * [6] J. Kaiser and J. S. Purcell and C. Rollins, _Volumes of chain links_ , http://arxiv.org/abs/1107.2865.
  * [7] F. E. Lindsay, _An interesting gear_ , The Engineer 135 (1923), 660, http://www.gracesguide.co.uk/images/c/cf/Er19230622.pdf.
  * [8] C. Andrew Neff, _Finding the distance between two circles in three-dimensional space_ , IBM Journal of Research and Development 34 (1990), no. 5, 770–775.
  * [9] Jack Phillips, _General spatial involute gearing_ , Springer, 2003.
  * [10] Hellmuth Stachel, _On Jack Phillip’s spatial involute gearing_ , The 11th International Conference on Geometry and Graphics, 1-5 August, 2004, Guangzhou, China.

##  Appendix A Postscript on paradoxes

After submission, but before publication, we stumbled across the work of
Jacques Maurel888See http://www.jacquesmaurel.com/gears. His video
http://www.youtube.com/watch?v=AwzL7Z_50zc inspired this appendix.. He
explains, via many beautiful videos, Lindsay’s _paradoxical gears_ [7]. We
adapt these to find three gears with parallel axes, all in contact and all
rotating in the same direction. However, these gears are not in fact planar;
thus they narrowly avoid contradicting the second sentence of our abstract.

Figure 10: Horizontal slices of the paradoxical parallel axis gears.

The three gear are helical screws, similar to the driving axle shown in Figure
9a. Their axes meet each horizontal plane at the vertices of an equilateral
triangle. Each horizontal cross-section of each screw is an involute planar
gear, as discussed in Section 4, but with only three teeth. See Figure 10 for
a sequence of cross-sectional views. Descending, the cross-sections rotate,
all in the same direction. Alternatively we can view the three pictures as an
animation of a cross-section at a fixed height.

Note that in ordinary planar gearing, teeth of meshing gears meet close to the
_center line_ $L$: the straight line between the gear centers. The normal to
the teeth at the point of contact is roughly perpendicular to $L$. Thus, using
the cross-product to compute the torque on the follower, we find that the
driver and follower rotate in opposite directions.

Consider the first cross-section of the paradoxical gears, shown in Figure 10.
Again there is a triple of involute gears, in point contact. However, the
point of contact of the upper two gears is much further from their center
line, $L$. At the point of contact the common normal to the teeth is parallel
to $L$. Thus the follower rotates in the same direction as the driver.

By the time we get to the third picture in the animation, the gears are no
longer in contact. However, there are horizontal slices of the screws at other
heights which have come into contact, reproducing the first picture. So the
helical screws, as a whole, remain in contact and produce the desired
paradoxical behavior.

##  Appendix B The three-component Hopf link

######  Theorem.

Let $L$ be a three-component link where every component is a round circle and
every pair of circles is linked. Then $L$ is the three-component Hopf link.

###### Proof.

We work in $S^{3}=\\{(z,w)\in\mathbb{C}^{2}:|z|^{2}+|w|^{2}=1\\}$. Let
$Z=\\{(z,0):|z|=1\\}$ and $W=\\{(0,w):|w|=1\\}$ be the $z$– and $w$–axes.
After a Möbius transformation, we may assume that the first and second
components of the link $L$ are the axes $Z$ and $W$. Let $L_{3}$ be the third
component of $L$ and note that this is again a round circle.

Consider the set of great spheres that contain $Z$. Each such sphere is
divided into two hemispheres by $Z$. Each sphere meets $W$ in two points, one
in each hemisphere. So the set of hemispheres $\\{H_{w}:|w|=1\\}$ is indexed
by the points of $W$.

Since $L_{3}$ is round, and since it links $Z$, we deduce that $L_{3}$
intersects each great sphere containing $Z$ in precisely two points, once in
each hemisphere. Thus, as we go around $L_{3}$, we hit every hemisphere
$H_{w}$ in cyclic order. Similarly, as we go around $L_{3}$, we hit the
hemispheres $H_{z}$ in cyclic order. Note that $H_{z}\cap H_{w}$ is the
geodesic segment from $(z,0)$ to $(0,w)$, parameterized by
$(z\cdot\cos(\theta),w\cdot\sin(\theta))$ for $\theta\in[0,\pi/2]$. We can
deform $L_{3}$ by sliding each point along its respective geodesic segment
until it is at $\frac{\sqrt{2}}{2}(z,w)$. Thus $L_{3}$ becomes the $(1,1)$
curve on the torus $|w|=|z|$. So $Z$, $W$ and $L_{3}$ are three fibers of the
Hopf fibration of $S^{3}$, and our link is the three-component Hopf link. ∎