11institutetext: National Taiwan University, Taipei, Taiwan
11email<EMAIL_ADDRESS>
# Reduction from Complementary-Label Learning to Probability Estimates

Wei-I Lin  Hsuan-Tien Lin

###### Abstract

Complementary-Label Learning (CLL) is a weakly-supervised learning problem
that aims to learn a multi-class classifier from only complementary labels,
which indicate a class to which an instance does not belong. Existing
approaches mainly adopt the paradigm of reduction to ordinary classification,
which applies specific transformations and surrogate losses to connect CLL
back to ordinary classification. Those approaches, however, face several
limitations, such as the tendency to overfit. In this paper, we sidestep those
limitations with a novel perspective–reduction to probability estimates of
complementary classes. We prove that accurate probability estimates of
complementary labels lead to good classifiers through a simple decoding step.
The proof establishes a reduction framework from CLL to probability estimates.
The framework offers explanations of several key CLL approaches as its special
cases and allows us to design an improved algorithm that is more robust in
noisy environments. The framework also suggests a validation procedure based
on the quality of probability estimates, offering a way to validate models
with only CLs. The flexible framework opens a wide range of unexplored
opportunities in using deep and non-deep models for probability estimates to
solve CLL. Empirical experiments further verified the framework’s efficacy and
robustness in various settings. 111The full paper can be accessed at
https://arxiv.org/abs/2209.09500.

###### Keywords:

complementary-label learning weakly-supervised learning

##  1 Introduction

In real-world machine learning applications, high-quality labels may be hard
or costly to collect. To conquer the problem, researchers turn to the _weakly-
supervised learning_ (WSL) framework, which seeks to learn a good classifier
with incomplete, inexact, or inaccurate data [14]. This paper focuses on a
very weak type of WSL, called _complementary-label learning_ (CLL) [3]. For
the multi-class classification task, a complementary label (CL) designates a
class to which a specific instance does not belong. The CLL problem assumes
that the learner receives complementary labels rather than ordinary ones
during training, while wanting the learner to correctly predict the ordinary
labels of the test instances. Complementary labels can be cheaper to obtain.
For example, when labeling with many classes, selecting the correct label is
time-consuming for data annotators, while selecting a complementary label
would be less costly [3]. In this case, fundamental studies on CLL models can
potentially upgrade multi-class classification models and make machine
learning more realistic. CLL’s usefulness also attracts researchers to study
its interaction with other tasks, such as generative-discriminative learning
[10, 7] and domain-adaptation [13].

[3, 4] proposed a pioneering model for CLL based on replacing the ordinary
classification error with its unbiased risk estimator (URE) computed from only
complementary labels assuming that the CLs are generated uniformly. [1]
unveiled the overfitting tendency of URE and proposed the surrogate
complementary loss (SCL) as an alternative design. [11] studied the situation
where the CLs are not generated uniformly, and proposed a loss function that
includes a transition matrix for representing the non-uniform generation. [2]
argued that the non-uniform generation shall be tackled by being agnostic to
the transition matrix instead of including the matrix in the loss function.

The methods mentioned above mainly focused on applying transformation and
specific loss functions to the ordinary classifiers. Such a “reduction to
ordinary classification” paradigm, however, faces some limitations and is not
completely analyzed. For instance, so far most of the methods in the paradigm
require differentiable models such as neural networks in their design. It is
not clear whether non-deep models could be competitive or even superior to
deep ones. It remains critical to correct the overfitting tendency caused by
the stochastic relationship between complementary and ordinary labels, as
repeatedly observed on URE-related methods [1]. More studies are also needed
to understand the potential of and the sensitivity to the transition matrix in
the non-uniform setting, rather than only fixing the matrix in the loss
function [11] or dropping it [2].

The potential limitations from reduction to ordinary classification motivate
us to sidestep them by taking a different perspective—reduction to
complementary probability estimates. Our contribution can be summarized as
follows.

  1. 1.

We propose a framework that only relies on the probability estimates of CLs,
and prove that a simple decoding method can map those estimates back to
correct ordinary labels with theoretical guarantees.

  2. 2.

The proposed framework offers explanations of several key CLL approaches as
its special cases and allows us to design an improved algorithm that is more
robust in noisy environments.

  3. 3.

We propose a validation procedure based on the quality of probability
estimates, providing a novel approach to validate models with only CLs along
with theoretical justifications.

  4. 4.

We empirically verify the effectiveness of the proposed framework under
broader scenarios than previous works that cover various assumptions on the CL
generation (uniform/non-uniform; clean/noisy) and models (deep /non-deep). The
proposed framework improves the SOTA methods in those scenarios, demonstrating
the effectiveness and robustness of the framework.

##  2 Problem Setup

In this section, we first introduce the problem of ordinary multi-class
classification, then formulate the CLL problem, and introduce some common
assumption.

###  2.1 Ordinary-label learning

We start by reviewing the problem formulation of ordinary multi-class
classification. In this problem, we let $K$ with $K>2$ denote the number of
classes to be classified, and use $\mathcal{Y}=[K]=\\{1,2,\dotsc,K\\}$ to
denote the label set. Let $\mathcal{X}\subset\mathbb{R}^{d}$ denote the
feature space. Let $D$ be an unknown joint distribution over
$\mathcal{X}\times\mathcal{Y}$ with density function $p_{D}(x,y)$. Given $N$
i.i.d. training samples $\\{(x_{i},y_{i})\\}_{i=1}^{N}$ and a hypothesis set
$\mathcal{H}$, the goal of the learner is to select a classifier
$f\colon\mathcal{X}\to\mathbb{R}^{K}$ from the hypothesis set $\mathcal{H}$
that predicts the correct labels on unseen instances. The prediction $\hat{y}$
of an unseen instance $x$ is determined by taking the argmax function on $f$,
i.e. $\hat{y}=\operatorname*{argmax}_{i}f_{i}(x)$, where $f_{i}(x)$ denote the
$i$-th output of $f(x)$. The goal of the learner is to learn an $f$ from
$\mathcal{H}$ that minimizes the following classification risk:
$\operatorname*{\mathbb{E}}_{(x,y)\sim D}\big{[}\ell(f(x),e_{y})\big{]}$,
where $\ell\colon\mathbb{R}^{K}\times\mathbb{R}^{K}\to\mathbb{R}^{+}$ denotes
the loss function, and $e_{y}$ denote the one-hot vector of label $y$.

###  2.2 Complementary-label learning

In complementary-label learning, the goal for the learner remains to find an
$f$ that minimizes the ordinary classification risk. The difference lies in
the dataset to learn from. The complementary learner does not have access to
the ground-truth labels $y_{i}$. Instead, for each instance $x_{i}$, the
learner is given a complementary label $\bar{y}_{i}$. A complementary label is
a class that $x_{i}$ does not belong to; that is,
$\bar{y}_{i}\in[K]\backslash\\{y_{i}\\}$. In CLL, it is assumed that the
complementary dataset is generated according to an unknown distribution
$\bar{D}$ over $\mathcal{X}\times\mathcal{Y}$ with density function
$\bar{p}_{\bar{D}}(x,y)$. Given access to i.i.d. samples
$\\{x_{i},\bar{y}_{i}\\}_{i=1}^{N}$ from $\bar{D}$, the complementary-label
learner aims to find a hypothesis that classifies the correct ordinary labels
on unseen instances.

Next, we introduce the _class-conditional complementary transition assumption_
, which is used by many existing work [3, 4, 11, 2]. It assumes that the
generation of complementary labels only depends on the ordinary labels; that
is, $P(\bar{y}\,|\,y,x)=P(\bar{y}\,|\,y)$. The transition probability
$P(\bar{y}\,|\,y)$ is often represented by a $K\times K$ matrix, called
_transition matrix_ , with $T_{ij}=P(\bar{y}=j\,|\,y=i)$. It is commonly
assumed to be all-zeros on the diagonals, i.e., $T_{ii}=0$ for all $i\in[K]$
in CLL because complementary labels are not ordinary. The transition matrix is
further classified into two categories: (a) _Uniform:_ In uniform
complementary generation, each complementary label is sampled uniformly from
all labels except the ordinary one. The transition matrix in this setting is
accordingly $T=\frac{1}{K-1}(\mathbf{1}_{k}-\mathbf{I}_{k})$. This is the most
widely researched and benchmarked setting in CLL. (b) _Biased:_ A biased
complementary generation is one that is not uniform. Biased transition
matrices could be further classified as invertible ones and noninvertible ones
based on its invertibility. The invertibility of a transition matrix comes
with less physical meaning in the context of CLL; however, it plays an
important role in some theoretical analysis in previous work [11, 1].

Following earlier approaches, we assume that the generation of complementary
labels follows class-conditional transition in the rest of the paper and that
the transition matrix is given to the learning algorithms. What is different
is that we do not assume the transition matrix to be uniform nor invertible.
This allows us to make comparison in broader scenarios. In real-world
scenario, the true transition matrix may be impossible to access. To loosen
the assumption that the true transition matrix is given, we will analyze the
case that the given matrix is _inaccurate_ later. This analysis can
potentially help us understand the CLL in a more realistic environment.

##  3 Proposed Framework

In this section, we propose a framework for CLL based on _complementary
probability estimates_ (CPE) and _decoding_. We first motivate the proposed
CPE framework in Section 3.1. Then, we describe the framework and derive its
theoretical properties in Section 3.2. In Section 3.3, we explain how earlier
approaches can be viewed as special cases in CPE. We further draw insights for
earlier approaches through CPE and propose improved algorithms based on those
insights.

Table 1: Comparison of recent approaches to CLL. $f(x)$ is the probability estimates of $x$, and $\ell$ is an arbitrary multi-class loss. Method | Transformation | Loss Function
---|---|---
URE [3, 4] | $\phi=I$ | $-(K-1)\ell(f(x),\bar{y})+\sum_{k=1}^{K}\ell(f(x),k)$
SCL-NL [1] | $\phi=I$ | $-\log(1-f_{\bar{y}}(x))$
Fwd [11] | $\phi(f)(x)=T^{\top}f(x)$ | $\ell(\phi(f)(x),\bar{y})$
DM [2] | $\phi(f)(x)=\operatorname*{\mathrm{sm}}(1-f(x))$ | $\ell(\phi(f)(x),\bar{y})$

###  3.1 Motivation

To conquer CLL, recent approaches [3, 11, 4, 1, 2] mainly focus on applying
different transformation and surrogate loss functions to the ordinary
classifier, as summarized in Table 1. This paradigm of reduction to _ordinary_
, however, faces some limitations. For instance, as [1] points out, the URE
approach suffers from the large variance in the gradients. Besides, it remains
unclear how some of them behave when the transition matrix is biased. Also,
those methods only studied using neural networks and linear models as base
models. It is unclear how to easily cast other traditional models for CLL.
These limitations motivate us to sidestep them with a different
perspective—reduction to _complementary_ probability estimates.

###  3.2 Methodology

####  3.2.1 Overview

The proposed method consists of two steps: In training phase, we aim to find a
hypothesis $\bar{f}$ that predicts the distribution of complementary labels
well, i.e., an $\bar{f}$ that approximates $P(\bar{y}\,|\,x)$. This step is
motivated by [11, 2], which involve modeling the conditional distribution of
the complementary labels $P(\bar{y}\,|\,x)$, and [12], which uses similar idea
on noisy-label learning. What is different in our framework is the decoding
step during prediction. In inference phase, we propose to predict the label
with the closest transition vector to the predicted complementary probability
estimates. Specifically, we propose to predict
$\hat{y}=\operatorname*{argmin}_{k\in[K]}d\left(\bar{f}(x),T_{k}\right)$ for
an unseen instance $x$, where $d$ denotes a loss function. It is a natural
choice to decode with respect to $T$ because the transition vector
$T_{k}=(P(\bar{y}=1\,|\,y=k),\dotsc,P(\bar{y}=K\,|\,y=k))^{\top}$ is the
ground-truth distribution of the complementary labels if the ordinary label is
$k$. In the following paragraph, we provide further details of our framework.

####  3.2.2 Training Phase: Probability Estimates

In this phase, we aim to find a hypothesis $\bar{f}$ that predicts
$P(\bar{y}\,|\,x)$ well. To do so, given a hypothesis $\bar{f}$ from
hypothesis set $\bar{\mathcal{H}}$, we set the following _complementary
estimation loss_ to optimize:

$R(\bar{f};\ell)=\mathbb{E}_{(x,y)\sim\mathcal{D}}\left(\ell(\bar{f}(x),P(\bar{y}\,|\,x,y))\right)$
(1)

where $\ell$ can be any loss function defined between discrete probability
distributions. By the assumption that complementary labels are generated with
respect to the transition matrix $T$, the ground-truth distribution for
$P(\bar{y}\,|\,x,y)$ is $T_{y}$, so we can rewrite Equation (1) as follows:

$R(\bar{f};\ell)=\mathbb{E}_{(x,y)\sim\mathcal{D}}\left(\ell(\bar{f}(x),T_{y})\right)$
(2)

The loss function above is still hard to optimize for two reasons: First, the
presence of ordinary label $y$ suggests that it cannot be accessed from the
complementary dataset. Second, as we only have _one_ complementary label per
instance, it becomes questionable to directly use the empirical density, i.e.,
the one-hot vector of the complementary label $e_{\bar{y}}$ to approximate
$T_{y}$ as it may change the objective.

Here we propose to use the Kullback-Leibler divergence for the loss function
to solve the two issues mentioned above with the following property:

###### Proposition 1

There is a constant $C$ such that

$\operatorname*{\mathbb{E}}_{(x,\bar{y})\sim\bar{\mathcal{D}}}\ell(\bar{f}(x),e_{\bar{y}})+C=\operatorname*{\mathbb{E}}_{(x,y)\sim\mathcal{D}}\ell(\bar{f}(x),T_{y})$
(3)

holds for all hypothesis $\bar{f}\in\bar{\mathcal{H}}$ if $\ell$ is the KL
divergence, i.e., $\ell(\hat{y},y)=\sum_{k=1}^{K}-y_{k}(\log\hat{y}_{k}-\log
y_{k})$.

The result is well-known in the research of proper scoring rules [5, 9]. It
allows us to replace the $T_{y}$ by $e_{\bar{y}}$ in Equation (2) because the
objective function only differs by a constant after the replacement. This
suggests that minimizing the two objectives is equivalent. Moreover, the
replacement makes the objective function accessible through the complementary
dataset because it only depends on the complementary label $\bar{y}$ rather
than the ordinary one.

Formally speaking, minimizing Equation $\eqref{eq:Rf}$ becomes equivalent to
minimizing the following _surrogate complementary estimation loss (SCEL)_ :

$\bar{R}(\bar{f};\ell)=\mathbb{E}_{(x,\bar{y})\sim\bar{\mathcal{D}}}\left(\ell(\bar{f}(x),e_{\bar{y}})\right)$
(4)

By using KL divergence as the loss function, we have that

$\bar{R}(\bar{f};\ell)=\mathbb{E}_{(x,\bar{y})\sim\bar{\mathcal{D}}}\left(-\log\bar{f}_{\bar{y}}(x)\right)$
(5)

with $\bar{f}_{\bar{y}}(x)$ being the $\bar{y}$-th output of $\bar{f}(x)$.
Next, we can use the following empirical version as the training objective:
$\frac{1}{N}\sum_{i=1}^{N}-\log\bar{f}_{\bar{y}_{i}}(x_{i})$. According to the
empirical risk minimization (ERM) principle, we can estimate the distribution
of complementary labels $P(\bar{y}\,|\,x)$ by minimizing the log loss on the
complementary dataset. That is, by choosing $\bar{f}^{*}$ with
$\bar{f}^{*}=\operatorname*{argmin}_{\bar{f}\in\bar{\mathcal{H}}}\frac{1}{N}\sum_{i=1}^{N}-\log\bar{f}_{\bar{y}_{i}}(x_{i})$,
we can get an estimate of $P(\bar{y}\,|\,x)$ with $\bar{f}^{\ast}$.

In essence, we reduce the task of learning from complementary labels into
learning probability estimates for multi-class classification (on the
_complementary label space_). As the multi-class probability estimates is a
well-researched problem, our framework becomes flexible on the choice of the
hypothesis set. For instance, one can use K-Nearest Neighbor or Gradient
Boosting with log loss to estimate the distribution of complementary labels.
The flexibility becomes superior to the previous methods, who mainly focus on
using neural networks to minimize specific surrogate losses. It makes them
hard to optimize for non-differentiable models. In contrast, the proposed
methods directly enable existing ordinary models to learn from complementary
labels.

####  3.2.3 Inference Phase: Decoding

After finding a complementary probability estimator $\bar{f}^{*}$ during the
training phase, we propose to predict the ordinary label by decoding: Given an
unseen example $x$, we predict the label $\hat{y}$ whose transition vector
$T_{\hat{y}}$ is closest to the predicted complementary probability estimates.
That is, the label is predicted by

$\hat{y}=\operatorname*{argmin}_{k\in[K]}d\left(\bar{f}^{*}(x),T_{k}\right)$
(6)

where $d$ could be an arbitrary loss function on the probability simplex and
$T_{k}$ is the $k$-th row vector of $T$. We use
$\operatorname*{\mathrm{dec}}(\bar{f};d)$ to denote the function that decodes
the output from $\bar{f}$ according to the loss function $d$. The next problem
is whether the prediction of the decoder can guarantee a small out-sample
classification error
$R_{01}(f)=\operatorname*{\mathbb{E}}_{(x,y)\sim\mathcal{D}}I_{f(x)\neq y}$.

We propose to use a simple decoding step by setting $L_{1}$ distance as the
loss function for decoding:

$\operatorname*{\mathrm{dec}}(\bar{f};L_{1})\,(x)=\operatorname*{argmin}_{y\in[K]}\;\lVert
T_{y}-\bar{f}(x)\rVert_{1}$ (7)

This choice of $L_{1}$ distance makes the decoding step easy to perform and
provides the following bound that quantifies the relationship between the
error rate and the quality of probability estimator:

###### Proposition 2

For any $\bar{f}\in\bar{\mathcal{H}}$, and distance function $d$ defined on
the probability simplex $\Delta^{K}$, it holds that

$R_{01}\big{(}\operatorname*{\mathrm{dec}}(\bar{f};d)\big{)}\leq\frac{2}{\gamma_{d}}R(\bar{f};d)$
(8)

where $\gamma_{d}=\min_{i\neq j}d(T_{i},T_{j})$ is the minimal distance
between any pair of transition vector. Moreover, if $d$ is the $L_{1}$
distance and $\ell$ is the KL divergence, then with $\gamma=\min_{i\neq
j}\lVert T_{i}-T_{j}\rVert_{1}$, it holds that

$R_{01}\big{(}\operatorname*{\mathrm{dec}}(\bar{f};L_{1})\big{)}\leq\frac{4\sqrt{2}}{\gamma}\sqrt{R(\bar{f};\ell)}$
(9)

The proof is in Appendix 0.A.2. In the realizable case, where there is a
target function $g$ that satisfies $g(x)=y$ for all instances, the term
$R(\bar{f};\ell_{\text{KL}})$ can be minimized to zero with
$\bar{f}^{\star}:x\mapsto T_{g(x)}$. This indicates that for a sufficiently
rich complementary hypothesis set, if the complementary probability estimator
is consistent ($\bar{f}\to\bar{f}^{\star}$) then the $L_{1}$ decoded
prediction is consistent
($R_{01}\big{(}\operatorname*{\mathrm{dec}}(\bar{f};L_{1})\big{)}\to 0$). The
result suggests that the performance of the $L_{1}$ decoder can be bounded by
the accuracy of the probability estimates of complementary labels measured by
the KL divergence. In other words, to obtain an accurate ordinary classifier,
it suffices to find an accurate complementary probability estimator followed
by the $L_{1}$ decoding. Admittedly, in the non-realizable case,
$R(\bar{f};\ell_{\text{KL}})$ contains irreducible error. We leave the
analysis of the error bound in this case for the future research.

Another implication of the Proposition 2 is related to the inaccurate
transition matrix. Suppose the complementary labels are generated with respect
to the transition matrix $T^{\prime}$, which may be different from $T$, the
one provided to the learning algorithm. In the proposed framework, the only
affected component is the decoding step. This allows us to quantify the effect
of inaccuracy as follows:

###### Corollary 1

For any $\bar{f}\in\bar{\mathcal{H}}$, if $d$ is the $L_{1}$ distance and
$\ell$ is the KL divergence, then

$R_{01}\big{(}\operatorname*{\mathrm{dec}}(f;L_{1})\big{)}\leq\frac{4\sqrt{2}}{\gamma}\sqrt{R(\bar{f};\ell)}+\frac{2\epsilon}{\gamma}.$
(10)

where $\gamma=\min_{i\neq j}\lVert T_{i}-T_{j}\rVert_{1}$ is the minimal
$L_{1}$ distance between pairs of transition vectors, and
$\epsilon=\max_{k\in[K]}\lVert T_{k}^{\prime}-T_{k}\rVert_{1}$ denotes the
difference between $T^{\prime}$ and $T$.

####  3.2.4 Validation Phase: Quality of Probability Estimates

The third implication of Proposition 2 is an alternative validation procedure
to the unbiased risk estimation (URE) [3]. According to Proposition 2,
selecting the best-performing parameter minimizes the right hand side of Eq.
(9) among all hyper-parameter choices minimizes the ordinary classification
error. This suggests an alternative metric for parameter selection: using the
surrogate complementary estimation loss (SCEL) on the validation dataset.

Although the proposed validation procedure does not directly estimate the
ordinary classification error, it provides benefits in the scenarios where URE
does not work well. For instance, when the transition matrix is non-
invertible, the behavior of URE is ill-defined due to the presence of $T^{-1}$
in the formula of URE:
$\operatorname*{\mathbb{E}}_{x,\bar{y}}e_{\bar{y}}T^{-1}\ell(f(x))$. Indeed,
replacing $T^{-1}$ with $T$’s pseudo-inverse can avoid the issue; however, it
remains unclear whether the unbiasedness of URE still holds after using
pseudo-inverse. In contrast, the quality of complementary probability
estimates sidesteps the issue because it does not need to invert the
transition matrix. This prevents the proposed procedure from the issue of an
ill-conditioned transition matrix.

###  3.3 Connection to Previous Methods

The proposed framework also explains several earlier approaches as its special
cases, including (1) Forward Correction (Fwd) [11], (2) Surrogate
Complementary Loss (SCL) with log loss [1], and (3) Discriminative Model (DM)
[2], which are explained in Table 2 and Appendix 0.B. By viewing those earlier
approaches in the proposed framework, we provide additional benefits for them.
First, the novel validation process can be applied for parameter selection.
This provides an alternative to validate those approaches. Also, we fill the
gap on the theoretical explanation to help understand those approaches in the
realizable case.

Table 2: A unifying view of earlier approaches and proposed algorithms through the lens of reduction to probability estimates, where $U$ denote the uniform transition matrix. Two versions of Forward Correction are considered: General $T$ denotes the original version in [11], and the Uniform denotes the case when the transition layer is fixed to be uniform. Proof of the equivalence is in Appendix 0.B. Method | Hypothesis set | Decoder
---|---|---
Fwd (general $T$) [11] | $\\{x\mapsto T^{\top}f(x;\theta):\theta\in\Theta\\}$ | $\operatorname*{argmax}_{k}((T^{\top})^{-1}\bar{f}(x))_{k}$
Fwd (uniform) [11] | $\\{x\mapsto U^{\top}f(x;\theta):\theta\in\Theta\\}$ | $\operatorname*{argmin}_{k}\lVert\bar{f}(x)-U_{k}\rVert_{1}$
SCL [1] | $\\{x\mapsto U^{\top}f(x;\theta):\theta\in\Theta\\}$ | $\operatorname*{argmin}_{k}\lVert\bar{f}(x)-U_{k}\rVert_{1}$
DM [2] | $\\{x\mapsto\operatorname*{\mathrm{sm}}(1-f(x;\theta)):\theta\in\Theta\\}$ | $\operatorname*{argmin}_{k}\lVert\bar{f}(x)-U_{k}\rVert_{1}$
CPE-I (no transition) | $\\{x\mapsto f(x;\theta):\theta\in\Theta\\}$ | $\operatorname*{argmin}_{k}\lVert\bar{f}(x)-T_{k}\rVert_{1}$
CPE-F (fixed transition) | $\\{x\mapsto T^{\top}f(x;\theta):\theta\in\Theta\\}$ | $\operatorname*{argmin}_{k}\lVert\bar{f}(x)-T_{k}\rVert_{1}$
CPE-T (trainable transition) | $\\{x\mapsto T(W)^{\top}f(x;\theta):\theta\in\Theta,W\in\mathbb{R}^{K\times K}\\}$ | $\operatorname*{argmin}_{k}\lVert\bar{f}(x)-T_{k}\rVert_{1}$

On the other hand, the success of Fwd inspires us to reconsider the role of
transition layers in the framework. As the base model’s output $f(x;\theta)$
is in the probability simplex $\Delta^{K}$, the model’s output
$T^{\top}f(x;\theta)$ lies in the convex hull formed by the row vectors of
$T$. If the transition matrix $T$ provided to the learning algorithm is
accurate, then such transformation helps control the model’s complexity by
restricting its output. The restriction may be wrong, however, when the given
transition matrix $T$ is inaccurate. To address this issue, we propose to
allow the transition layer to be _trainable_. This technique is also used in
label-noise learning, such as [6]. Specifically, we propose three methods in
our Complementary Probability Estimates framework: (a) CPE-I denotes a model
_without_ a transition layer (b) CPE-F denotes a model with a _fixed_
additional layer to $T$ (c) CPE-T denotes a model with a _trainable_
transition layer. To make the transition layer trainable, we considered a
$K\times K$ matrix $W$. A softmax function was applied to each row of $W$ to
transform it into a valid transition matrix
$T(W)=\big{(}\operatorname*{\mathrm{sm}}(W_{1}),\operatorname*{\mathrm{sm}}(W_{2}),\dotsc,\operatorname*{\mathrm{sm}}(W_{K})\big{)}^{\top}$.
For a base model $f$, the complementary probability estimates of CPE-T for a
given instance $x$ would be $T(W)^{\top}f(x;\theta)$. Note that we use the
$L_{1}$ decoder for CPE-I, CPE-F, and CPE-T.

##  4 Experiments

In this section, we benchmark the proposed framework to the state-of-the-art
baselines and discuss the following questions: (a) Can the transition layers
improve the model’s performance? (b) Is the proposed $L_{1}$ decoding
competitive to Max? (c) Does the transition matrix provide information to the
learning algorithms even if it is inaccurate? We further demonstrate the
flexibility of incorporating traditional models in CPE in Section 4.3 and
verify the effectiveness of the proposed validation procedure in the Appendix.

###  4.1 Experiment Setup

####  4.1.1 Baseline and setup

We first evaluate CPE with the following state-of-the-art methods: (a) URE-GA:
Gradient Ascent applied on the unbiased risk estimator [3, 4], (b) Fwd:
Forward Correction [11], (c) SCL: Surrogate Complementary Loss with negative
log loss [1], and (d) DM: Discriminative Models with Weighted Loss [2].
Following the previous work, we test those methods on MNIST, Fashion-MNIST,
and Kuzushiji-MNIST, and use one-layer mlp model (d-500-c) as base models. All
models are optimized using Adam with learning rate selected from {1e-3, 5e-4,
1e-4, 5e-5, 1e-5} and a fixed weight decay 1e-4 for 300 epochs. The learning
rate for CPE is selected with the Surrogate Complementary Estimation Loss
(SCEL) on the validation dataset. For the baseline method, it is selected with
unbiased risk estimator (URE) of the zero-one loss. It is worth noting that
the validation datasets consist of only complementary labels, which is
different from some previous works.

Table 3: Comparison of the testing classification accuracies with different transition matrices (upper part) and different noise levels (lower part). | MNIST | Fashion-MNIST | Kuzushiji-MNIST
---|---|---|---
| Unif. | Weak | Strong | Unif. | Weak | Strong | Unif. | Weak | Strong
URE-GA |  90.3$\pm$ 0.2 |  87.8$\pm$ 0.9 |  33.8$\pm$ 8.1 |  79.4$\pm$ 0.7 |  75.7$\pm$ 2.0 |  32.3$\pm$ 4.5 |  65.6$\pm$ 0.8 |  62.5$\pm$ 1.1 |  23.3$\pm$ 5.4
SCL |  94.3$\pm$ 0.4 | 93.8$\pm$ 0.4 |  27.5$\pm$ 19.8 |  82.6$\pm$ 0.4 |  81.2$\pm$ 0.1 |  28.5$\pm$ 10.8 | 73.7$\pm$ 1.4 | 71.2$\pm$ 2.9 |  20.7$\pm$ 4.8
DM |  91.9$\pm$ 0.6 |  90.2$\pm$ 0.3 |  26.7$\pm$ 4.6 |  82.5$\pm$ 0.3 |  80.3$\pm$ 1.1 |  24.8$\pm$ 5.0 |  65.6$\pm$ 2.9 |  64.5$\pm$ 2.7 |  20.1$\pm$ 3.2
Fwd | 94.4$\pm$ 0.2 |  91.9$\pm$ 0.3 |  95.3$\pm$ 0.4 |  82.6$\pm$ 0.6 | 83.0$\pm$ 1.0 |  85.5$\pm$ 0.3 |  73.5$\pm$ 1.6 |  63.1$\pm$ 2.6 |  74.1$\pm$ 4.8
CPE-I |  90.2$\pm$ 0.2 |  88.4$\pm$ 0.3 |  92.7$\pm$ 0.8 |  81.1$\pm$ 0.3 |  79.2$\pm$ 0.5 |  81.9$\pm$ 1.4 |  66.2$\pm$ 1.0 |  62.5$\pm$ 0.9 |  73.7$\pm$ 1.0
CPE-F | 94.4$\pm$ 0.2 |  92.0$\pm$ 0.2 | 95.5$\pm$ 0.3 | 83.0$\pm$ 0.1 | 83.0$\pm$ 0.3 | 85.8$\pm$ 0.3 |  73.5$\pm$ 1.6 |  64.6$\pm$ 0.5 | 75.3$\pm$ 2.6
CPE-T |  92.8$\pm$ 0.6 |  92.1$\pm$ 0.2 |  95.2$\pm$ 0.5 | 83.0$\pm$ 0.1 | 83.0$\pm$ 0.3 | 85.8$\pm$ 0.3 |  63.6$\pm$ 0.4 |  64.6$\pm$ 0.4 |  74.2$\pm$ 2.8
| $\lambda=0.1$ | $\lambda=0.2$ | $\lambda=0.5$ | $\lambda=0.1$ | $\lambda=0.2$ | $\lambda=0.5$ | $\lambda=0.1$ | $\lambda=0.2$ | $\lambda=0.5$
URE-GA |  31.8$\pm$ 6.4 |  27.8$\pm$ 8.2 |  28.1$\pm$ 4.1 |  27.3$\pm$ 5.5 |  28.6$\pm$ 4.1 |  26.3$\pm$ 2.0 |  24.5$\pm$ 4.6 |  21.1$\pm$ 2.2 |  19.8$\pm$ 2.1
SCL |  25.1$\pm$ 11.7 |  24.7$\pm$ 8.9 |  23.8$\pm$ 2.7 |  26.6$\pm$ 9.2 |  20.6$\pm$ 6.7 |  23.2$\pm$ 5.7 |  20.4$\pm$ 4.6 |  17.3$\pm$ 2.9 |  16.8$\pm$ 1.6
DM |  26.5$\pm$ 9.1 |  24.6$\pm$ 6.5 |  22.6$\pm$ 1.3 |  24.1$\pm$ 5.1 |  23.6$\pm$ 6.7 |  22.6$\pm$ 2.9 |  20.0$\pm$ 3.0 |  19.2$\pm$ 3.1 |  18.2$\pm$ 1.6
Fwd |  88.3$\pm$ 8.7 |  83.9$\pm$ 10.7 |  71.6$\pm$ 18.4 | 84.8$\pm$ 0.6 |  80.2$\pm$ 6.2 |  62.9$\pm$ 20.1 |  72.8$\pm$ 5.6 |  67.6$\pm$ 7.5 |  54.7$\pm$ 12.4
CPE-I |  92.4$\pm$ 0.7 |  92.0$\pm$ 0.8 |  87.6$\pm$ 1.4 |  81.7$\pm$ 1.4 |  81.3$\pm$ 1.4 |  78.2$\pm$ 1.5 |  73.0$\pm$ 0.7 |  71.6$\pm$ 0.9 |  62.7$\pm$ 1.6
CPE-F |  94.3$\pm$ 0.5 |  93.6$\pm$ 0.5 |  89.0$\pm$ 1.4 |  84.1$\pm$ 0.8 |  83.0$\pm$ 1.1 |  78.4$\pm$ 2.5 | 76.1$\pm$ 1.3 |  73.7$\pm$ 1.5 |  63.7$\pm$ 1.5
CPE-T | 94.4$\pm$ 0.5 | 93.7$\pm$ 0.5 | 89.6$\pm$ 0.9 |  84.1$\pm$ 0.8 | 83.2$\pm$ 1.1 | 78.9$\pm$ 2.0 | 76.1$\pm$ 1.3 | 73.9$\pm$ 1.6 | 64.2$\pm$ 1.2
Table 4: Comparison of testing accuracies of decoders when the baseline models use fixed transition layers. The parameters are selected from the one with smallest SCEL on the validation dataset. | MNIST | Fashion-MNIST | Kuzushiji-MNIST
---|---|---|---
| Unif. | Weak | Strong | Unif. | Weak | Strong | Unif. | Weak | Strong
Max |  94.4$\pm$ 0.2 |  92.0$\pm$ 0.2 |  95.5$\pm$ 0.2 |  83.0$\pm$ 0.1 | 83.3$\pm$ 0.2 | 86.1$\pm$ 0.5 |  73.5$\pm$ 1.6 | 64.8$\pm$ 0.5 |  75.3$\pm$ 2.6
$L_{1}$ |  94.4$\pm$ 0.2 |  92.0$\pm$ 0.2 |  95.5$\pm$ 0.3 |  83.0$\pm$ 0.1 |  83.0$\pm$ 0.3 |  85.8$\pm$ 0.3 |  73.5$\pm$ 1.6 |  64.6$\pm$ 0.5 |  75.3$\pm$ 2.6
| $\lambda=0.1$ | $\lambda=0.2$ | $\lambda=0.5$ | $\lambda=0.1$ | $\lambda=0.2$ | $\lambda=0.5$ | $\lambda=0.1$ | $\lambda=0.2$ | $\lambda=0.5$
Max | 94.4$\pm$ 0.3 |  93.5$\pm$ 0.3 |  84.5$\pm$ 4.1 | 85.0$\pm$ 0.3 | 84.0$\pm$ 0.5 |  76.5$\pm$ 2.5 | 76.4$\pm$ 1.1 | 73.8$\pm$ 1.2 |  59.9$\pm$ 3.4
$L_{1}$ |  94.3$\pm$ 0.5 | 93.6$\pm$ 0.5 | 89.0$\pm$ 1.4 |  84.1$\pm$ 0.8 |  83.0$\pm$ 1.1 | 78.4$\pm$ 2.5 |  76.1$\pm$ 1.3 |  73.7$\pm$ 1.5 | 63.7$\pm$ 1.5
Table 5: Comparison of testing accuracies of CPE with traditional models. Boldfaced ones outperform the baseline methods based on single-layer deep models. | MNIST | Fashion-MNIST | Kuzushiji-MNIST
---|---|---|---
Model | Unif. | Weak | Strong | Unif. | Weak | Strong | Unif. | Weak | Strong
CPE-KNN |  93.1$\pm$ 0.1 |  92.6$\pm$ 0.1 |  94.5$\pm$ 0.4 |  79.1$\pm$ 0.4 |  77.8$\pm$ 0.6 |  79.0$\pm$ 1.7 | 74.9$\pm$ 0.8 | 73.7$\pm$ 0.8 | 80.4$\pm$ 1.3
CPE-GBDT |  86.9$\pm$ 0.4 |  86.0$\pm$ 0.3 |  90.3$\pm$ 0.9 |  79.8$\pm$ 0.4 |  78.0$\pm$ 0.4 |  81.4$\pm$ 1.1 |  60.6$\pm$ 0.4 |  56.6$\pm$ 1.8 |  68.4$\pm$ 2.1
| $\lambda=0.1$ | $\lambda=0.2$ | $\lambda=0.5$ | $\lambda=0.1$ | $\lambda=0.2$ | $\lambda=0.5$ | $\lambda=0.1$ | $\lambda=0.2$ | $\lambda=0.5$
CPE-KNN |  93.7$\pm$ 0.4 |  93.4$\pm$ 0.4 | 91.9$\pm$ 1.1 |  78.7$\pm$ 1.9 |  78.5$\pm$ 1.9 |  76.6$\pm$ 1.9 | 77.2$\pm$ 1.1 | 75.9$\pm$ 1.6 | 73.2$\pm$ 1.7
CPE-GBDT |  89.7$\pm$ 1.0 |  88.6$\pm$ 1.2 |  84.0$\pm$ 1.7 |  80.6$\pm$ 1.7 |  80.0$\pm$ 1.6 |  76.0$\pm$ 2.2 |  66.7$\pm$ 2.4 |  64.7$\pm$ 2.4 |  55.8$\pm$ 3.1

####  4.1.2 Transition matrices

In the experiment of _clean_ transition matrices, three types of transition
matrices are benchmarked in the experiment. Besides the uniform transition
matrix, following [11, 2], we generated two biased ones as follows: For each
class $y$, the complementary classes $\mathcal{Y}\backslash\\{y\\}$ are first
randomly split into three subsets. Within each subset, the probabilities are
set to $p_{1}$, $p_{2}$ and $p_{3}$, respectively. We consider two cases for
$(p_{1},p_{2},p_{3})$: (a) _Strong_ :
$(\frac{0.75}{3},\frac{0.24}{3},\frac{0.01}{3})$ to model stronger deviation
from uniform transition matrices. (b) _Weak_ :
$(\frac{0.45}{3},\frac{0.30}{3},\frac{0.25}{3})$ to model milder deviation
from uniform transition matrices. In the experiment of _noisy_ transition
matrices, we consider the _Strong_ deviation transition matrix
$T_{\text{strong}}$ to be the ground-truth transition matrix, and a uniform
noise transition matrix $\frac{1}{K}\mathbf{1}_{K}$ to model the noisy
complementary label generation. We generated complementary labels with the
transition matrix
$(1-\lambda)T_{\text{strong}}+\lambda\frac{1}{K}\mathbf{1}_{K}$, but provided
$T_{\text{strong}}$ and the generated complementary dataset to the learners.
The parameter $\lambda$ controls the proportion of the uniform noise in the
complementary labels. The results are reported in Table 3.

###  4.2 Discussion

####  4.2.1 Can Transition Layers Improve Performance?

The answer is positive in both clean and noisy experiments. We observe that
CPE-F and CPE-T outperform CPE-I in both settings, demonstrating that the
transition layer help achieve higher performances, no matter the provided
transition matrix is clean or not. Also, we observe that CPE-T outperforms
CPE-F in the noisy setting, especially when the noise factor $\lambda$ is
large. It demonstrates that by making transition layers trainable, the model
can potentially fit the distribution of complementary labels better by
altering the transition layer. In contrast, CPE-F is restricted to a wrong
output space, making it underperform CPE-T. The difference makes CPE-T a
better choice for noisy environment.

####  4.2.2 Is $L_{1}$ competitive with Max?

As analyzed in Section 3.3, Fwd and CPE-F only differ in the decoding step,
with the former using Max and the latter using $L_{1}$. We provide the testing
accuracies of these decoders when the base models are CPE-F in Table 4. It is
displayed that the Max decoder outperform $L_{1}$ in most noiseless settings;
however, when the transition matrix is highly inaccurate ($\lambda=0.5$), we
observe that the $L_{1}$ decoder outperform the Max decoder. This suggests
that $L_{1}$ could be more tolerant to an inaccurate transition matrix. These
results reveal that a deeper sensitivity analysis of different decoders, both
empirically and theoretically, would be desired. We leave this as future
studies.

####  4.2.3 Discussion of $T$-agnostic models

Among the baseline methods, URE-GA, SCL and DM are ones that does not take $T$
as inputs or assumes $T$ is uniform, which we called $T$-agnostic models.
Those models perform well when the transition matrix is just slightly deviated
from the uniform one, but their performances all dropped when the deviation
from uniform becomes larger. As we discussed in Section 3.3, the result can be
interpreted to be caused by their implicit assumption on uniform transition
matrices, which brings great performance on uniform transition matrices but
worse performance on biased ones. In contrast, we observed that all variations
of CPE have similar testing accuracies across different transition matrices,
demonstrating that CPE does exploit the information from the transition matrix
that helps the models deliver better performance.

###  4.3 Learn from CL with Traditional Methods

As discussed in Section 3, the proposed framework is not constrained by deep
models. We explored the possibility of applying traditional methods to learn
from CL, including (a) $k$-Nearest Neighbor ($k$-NN) and (b) Gradient Boosting
Decision Tree (GBDT). We benchmarked those models in the same settings and
reported the restuls in Table 5. It displays that traditional models,
specifically, $k$-NN, outperform all the methods using deep models in
Kuzushiji-MNIST, indicating the benefit of the proposed CPE’s flexibility in
using non-deep models.

##  5 Conclusion

In this paper, we view the CLL problem from a novel perspective, reduction to
complementary probability estimates. Through this perspective, we propose a
framework that only requires complementary probability estimates and prove
that a simple decoding step can map the estimates to ordinary labels. The
framework comes with a theoretically justified validation procedure, provable
tolerance in noisy environment, and flexibility of incorporating non-deep
models. Empirical experiments further verify the effectiveness and robustness
of the proposed framework under broader scenarios, including non-uniform and
noisy complementary label generation. We expect the realistic elements of the
framework to keep inspiring future research towards making CLL practical.

## References

  * [1] Chou, Y.T., Niu, G., Lin, H.T., Sugiyama, M.: Unbiased risk estimators can mislead: A case study of learning with complementary labels. In: International Conference on Machine Learning. pp. 1929–1938. PMLR (2020)
  * [2] Gao, Y., Zhang, M.L.: Discriminative complementary-label learning with weighted loss. In: International Conference on Machine Learning. pp. 3587–3597. PMLR (2021)
  * [3] Ishida, T., Niu, G., Hu, W., Sugiyama, M.: Learning from complementary labels. In: Proceedings of the 31st International Conference on Neural Information Processing Systems. pp. 5644–5654 (2017)
  * [4] Ishida, T., Niu, G., Menon, A., Sugiyama, M.: Complementary-label learning for arbitrary losses and models. In: International Conference on Machine Learning. pp. 2971–2980. PMLR (2019)
  * [5] Kull, M., Flach, P.: Novel decompositions of proper scoring rules for classification: Score adjustment as precursor to calibration. In: Joint European Conference on Machine Learning and Knowledge Discovery in Databases. pp. 68–85. Springer (2015)
  * [6] Li, X., Liu, T., Han, B., Niu, G., Sugiyama, M.: Provably end-to-end label-noise learning without anchor points. In: Meila, M., Zhang, T. (eds.) Proceedings of the 38th International Conference on Machine Learning. Proceedings of Machine Learning Research, vol. 139, pp. 6403–6413. PMLR (18–24 Jul 2021)
  * [7] Liu, J., Hang, H., Wang, B., Li, B., Wang, H., Tian, Y., Shi, Y.: Gan-cl: Generative adversarial networks for learning from complementary labels. IEEE Transactions on Cybernetics (2021)
  * [8] Wang, D.B., Feng, L., Zhang, M.L.: Learning from complementary labels via partial-output consistency regularization. In: IJCAI. pp. 3075–3081 (2021)
  * [9] Williamson, R.C., Vernet, E., Reid, M.D.: Composite multiclass losses. Journal of Machine Learning Research 17(222), 1–52 (2016)
  * [10] Xu, Y., Gong, M., Chen, J., Liu, T., Zhang, K., Batmanghelich, K.: Generative-discriminative complementary learning. In: Proceedings of the AAAI Conference on Artificial Intelligence. vol. 34, pp. 6526–6533 (2020)
  * [11] Yu, X., Liu, T., Gong, M., Tao, D.: Learning with biased complementary labels. In: Proceedings of the European conference on computer vision (ECCV). pp. 68–83 (2018)
  * [12] Zhang, M., Lee, J., Agarwal, S.: Learning from noisy labels with no change to the training process. In: International Conference on Machine Learning. pp. 12468–12478. PMLR (2021)
  * [13] Zhang, Y., Liu, F., Fang, Z., Yuan, B., Zhang, G., Lu, J.: Learning from a complementary-label source domain: Theory and algorithms. IEEE Transactions on Neural Networks and Learning Systems (2021)
  * [14] Zhou, Z.H.: A brief introduction to weakly supervised learning. National science review 5(1), 44–53 (2018)

#### Acknowlegements.

We thank the anonymous reviewers and the members of NTU CLLab for valuable
suggestions. The work is partially supported by the National Science and
Technology Council via the grants 110-2628-E-002-013 and 111-2628-E-002-018.
We also thank the National Center for High-performance Computing (NCHC) of
National Applied Research Laboratories (NARLabs) in Taiwan for providing
computational resources.

##  Appendix 0.A Proofs

This section provides the proofs for the propositions, theorems claimed in the
main text.

###  0.A.1 Proof of Proposition 1

First, set
$C=\operatorname*{\mathbb{E}}_{(x,y)\sim\mathcal{D}}\sum_{k=1}^{K}T_{yk}\log(T_{yk})$,
then

$\operatorname*{\mathbb{E}}_{(x,y)\sim\mathcal{D}}\ell(\bar{f}(x),T_{y})=\operatorname*{\mathbb{E}}_{(x,y)\sim\mathcal{D}}\sum_{k=1}^{K}-T_{yk}\log\left(\frac{\bar{f}_{k}(x)}{T_{yk}}\right)=C+\operatorname*{\mathbb{E}}_{(x,y)\sim\mathcal{D}}\sum_{k=1}^{K}-T_{yk}\log(\bar{f}_{k}(x))$
(11)

Next, as $P(\bar{y}\,|\,y)=T_{y\bar{y}}$, then

$\operatorname*{\mathbb{E}}_{(x,y)\sim\mathcal{D}}\sum_{k=1}^{K}-T_{yk}\log(\bar{f}_{k}(x))=\operatorname*{\mathbb{E}}_{(x,y)\sim\mathcal{D}}\left(\operatorname*{\mathbb{E}}_{\bar{y}\,|\,y}-\log(\bar{f}_{\bar{y}}(x))\right)=\operatorname*{\mathbb{E}}_{(x,\bar{y})\sim\bar{\mathcal{D}}}\ell(\bar{f}(x),e_{\bar{y}})$
(12)

Hence,
$\operatorname*{\mathbb{E}}_{(x,y)\sim\mathcal{D}}\ell(\bar{f}(x),T_{y})=C+\operatorname*{\mathbb{E}}_{(x,\bar{y})\sim\bar{\mathcal{D}}}\ell(\bar{f}(x),e_{\bar{y}})$.

###  0.A.2 Proof of Proposition 2

Let $I_{A}$ denote the indicator function of event $A$, then using Markov’s
inequality on the random variable $d(\bar{f}(x),T_{y})$, we have

$R_{01}\big{(}\operatorname*{\mathrm{dec}}(\bar{f};d)\big{)}\leq
P\Big{(}d(\bar{f}(x),T_{y})\geq\frac{\gamma_{d}}{2}\Big{)}\leq\frac{2}{\gamma_{d}}\operatorname*{\mathbb{E}}\Big{[}d(\bar{f}(x),T_{y})\Big{]}=\frac{2}{\gamma_{d}}R(\bar{f};d)$
(13)

To see the first inequality holds, note that if
$d(\bar{f}(x),T_{y})<\frac{\gamma_{d}}{2}$, then for any incorrect class
$y^{\prime}\neq y$, we have

$d(\bar{f}(x),T_{y^{\prime}})\geq
d(T_{y},T_{y^{\prime}})-d(T_{y},\bar{f}(x))\geq\frac{\gamma_{d}}{2}$ (14)

by triangular inequality and the definition of $\gamma_{d}$. As a result, the
decoder decodes $\bar{f}(x)$ to the correct class $y$ if
$d(\bar{f}(x),T_{y})<\frac{\gamma_{d}}{2}$. This completes the first part of
the Proposition.

Next, by Pinsker’s inequality and Jensen’s inequality, we have that

$\displaystyle R(\bar{f};L_{1})$
$\displaystyle=\operatorname*{\mathbb{E}}_{(x,y)\sim\mathcal{D}}\big{\lVert}\bar{f}(x)-T_{y}\big{\rVert}_{1}$
(15) $\displaystyle\leq
2\operatorname*{\mathbb{E}}_{(x,y)\sim\mathcal{D}}\sqrt{2\ell_{\text{KL}}\big{(}\bar{f}(x),T_{y}\big{)}}$
(16) $\displaystyle\leq
2\sqrt{2\operatorname*{\mathbb{E}}_{(x,y)\sim\mathcal{D}}\ell_{\text{KL}}\big{(}\bar{f}(x),T_{y}\big{)}}=2\sqrt{2R(\bar{f};\ell_{\text{KL}})}$
(17)

According to the above inequality and the results of the first part, the proof
for the second part is now complete.

###  0.A.3 Proof of Corollary 1

The decoding step remains the same when $T^{\prime}\neq T$ because the decoder
uses the same transition matrix $T$ to decode. The only difference is in the
complementary probability estimates. Specifically, we have that the
complementary estimation loss becomes
$R(\bar{f};\ell)=\mathbb{E}_{(x,y)\sim\mathcal{D}}\left(\ell(\bar{f}(x),T^{\prime}_{y})\right)$
as the complementary labels are generated with respect to $T^{\prime}$.

Hence, the last equality in Equation (13) is no longer correct. Instead, we
use the following:

$\operatorname*{\mathbb{E}}\Big{[}d(\bar{f}(x),T_{y})\Big{]}\leq\operatorname*{\mathbb{E}}\Big{[}d(\bar{f}(x),T^{\prime}_{y})+d(T^{\prime}_{y},T_{y})\Big{]}\leq\operatorname*{\mathbb{E}}\Big{[}d(\bar{f}(x),T^{\prime}_{y})\Big{]}+\epsilon$
(18)

to obtain that
$R_{01}\big{(}\operatorname*{\mathrm{dec}}(\bar{f};d)\big{)}\leq\frac{2}{\gamma_{d}}R(\bar{f};d)+\frac{2\epsilon}{\gamma_{d}}$.
Then, we can use Pinsker’s inequality and Jensen’s inequality as in (15) to
get

$R_{01}\big{(}\operatorname*{\mathrm{dec}}(f;L_{1})\big{)}\leq\frac{4\sqrt{2}}{\gamma}\sqrt{R(\bar{f};\ell)}+\frac{2\epsilon}{\gamma}.$
(19)

##  Appendix 0.B Details of the Connections between Proposed Framework and
Previous Methods

In this section, we provide further details about how our framework can
explain several previous methods as its special cases. Across this section, we
let $f(\cdot;\theta)$ denote the base model parametrized by $\theta\in\Theta$.
We also provide some insights drawn from viewing these previous methods using
the proposed framework.

##### Forward Correction

In the training phase, Forward Correction optimizes the following loss
functions:

$L_{\text{Fwd}}(\theta)=\frac{1}{N}\sum_{i=1}^{N}-\log\big{(}T^{\top}f(x_{i};\theta)\big{)}_{\bar{y}_{i}}$
(20)

In the inference phase, Forward Correction predicts
$\hat{y}=\operatorname*{argmax}_{k}f_{k}(x)$ for an unseen instance $x$. We
claim that Forward Correction is equivalent to CPE with the following
parameters when $T$ is invertible:

  * •

Hypothesis Set: $\\{x\mapsto T^{\top}f(x;\theta):\theta\in\Theta\\}$

  * •

Decoder:
$\operatorname*{argmax}_{k}\big{(}(T^{\top})^{-1}\bar{f}(x;\theta)\big{)}_{k}$.

###### Proof

First, by setting the hypothesis set as above and plugging in the surrogate
complementary estimation loss, we get the training objective function for CPE:

$L_{\text{CPE}}(\theta)=\frac{1}{N}\sum_{i=1}^{N}-\log\big{(}T^{\top}f(x_{i};\theta)\big{)}_{\bar{y}_{i}}$
(21)

Equation (21) matches Equation (20), implying that in the training phase they
select the same parameter $\theta$. Next, in the inference phase, it is clear
that
$(T^{\top})^{-1}\bar{f}(x;\theta)=(T^{\top})^{-1}T^{\top}f(x;\theta)=f(x;\theta)$,
so both methods predict the same label for an instance $x$.

Next, we further show that when $T$ is the uniform transition matrix $U$, the
decoder is equivalent to the $L_{1}$ decoder, i.e.,
$\operatorname*{argmax}_{k}((U^{\top})^{-1}\bar{f}(x))_{k}=\operatorname*{argmin}_{k}\lVert
U_{k}-\bar{f}(x)\rVert_{1}$:

###### Proof

First, as

$((U^{\top})^{-1}\bar{f}(x))_{k}=-(K-1)\bar{f}_{k}(x)+\sum_{k=1}^{K}\bar{f}_{k}(x)=-(K-1)\bar{f}_{k}(x)+1,$

we have that
$\operatorname*{argmax}_{k}((U^{\top})^{-1}\bar{f}(x))_{k}=\operatorname*{argmin}_{k}\bar{f}_{k}(x)$.
Next, set $\hat{y}=\operatorname*{argmin}_{k}\bar{f}_{k}(x)$. For any
$y\neq\hat{y}$, we want to show

$|U_{y\hat{y}}-\bar{f}_{\hat{y}}(x)|+|U_{yy}-\bar{f}_{y}(x)|\geq|U_{\hat{y}\hat{y}}-\bar{f}_{\hat{y}}(x)|+|U_{\hat{y}y}-\bar{f}_{y}(x)|.$
(22)

As $\bar{f}_{\hat{y}}(x)\leq\frac{1}{K}\leq\frac{1}{K-1}=U_{y\hat{y}}$,

$\displaystyle|U_{y\hat{y}}-\bar{f}_{\hat{y}}(x)|+|U_{yy}-\bar{f}_{y}(x)|$
$\displaystyle=|U_{y\hat{y}}-\bar{f}_{\hat{y}}(x)|+\bar{f}_{\hat{y}}(x)+|U_{yy}-\bar{f}_{y}(x)|-f_{\hat{y}}(x)$
(23)
$\displaystyle=|U_{\hat{y}\hat{y}}-\bar{f}_{\hat{y}}(x)|+|U_{y\hat{y}}-\bar{f}_{\hat{y}}(x)|+|U_{yy}-\bar{f}_{y}(x)|-\bar{f}_{\hat{y}}(x)$
(24)
$\displaystyle=|U_{\hat{y}\hat{y}}-\bar{f}_{\hat{y}}(x)|+\frac{1}{K-1}-\bar{f}_{\hat{y}}(x)+\bar{f}_{y}(x)-\bar{f}_{\hat{y}}(x)$
(25)

If $\bar{f}_{y}(x)\leq\frac{1}{K-1}$, as
$\bar{f}_{\hat{y}}(x)\leq\bar{f}_{y}(x)$,

$\frac{1}{K-1}-\bar{f}_{\hat{y}}(x)+\bar{f}_{y}(x)-\bar{f}_{\hat{y}}(x)\geq\frac{1}{K-1}-\bar{f}_{\hat{y}}(x)\geq\frac{1}{K-1}-\bar{f}_{y}(x)=|U_{\hat{y}y}-\bar{f}_{y}(x)|$

Otherwise, as $\bar{f}_{\hat{y}}(x)\leq\frac{1}{K}$,

$\frac{1}{K-1}-\bar{f}_{\hat{y}}(x)+\bar{f}_{y}(x)-\bar{f}_{\hat{y}}(x)\geq\bar{f}_{y}(x)-\bar{f}_{\hat{y}}(x)\geq\frac{1}{K-1}-\bar{f}_{y}(x)=|U_{\hat{y}y}-\bar{f}_{y}(x)|.$

Hence, Equation (22) holds. Now,

$\displaystyle\sum_{k=1}^{K}\left|U_{yk}-\bar{f}_{k}(x)\right|$
$\displaystyle=\left|U_{y\hat{y}}-\bar{f}_{\hat{y}}(x)\right|+\left|U_{yy}-\bar{f}_{y}(x)\right|+\sum_{k\neq
y,\hat{y}}\left|U_{yk}-\bar{f}_{k}(x)\right|$ (26)
$\displaystyle\geq\left|U_{\hat{y}y}-\bar{f}_{y}(x)\right|+\left|U_{\hat{y}\hat{y}}-\bar{f}_{\hat{y}}(x)\right|+\sum_{k\neq
y,\hat{y}}\left|U_{\hat{y}k}-\bar{f}_{k}(x)\right|=\sum_{k=1}^{K}\left|U_{\hat{y}k}-\bar{f}_{k}(x)\right|$
(27)

As a result, $\hat{y}$ minimizes $k\mapsto\lVert U_{k}-\bar{f}(x)\rVert_{1}$.
Hence, we conclude that
$\operatorname*{argmin}_{k}\bar{f}_{k}(x)=\bar{y}=\operatorname*{argmin}_{k}\lVert
U_{k}-\bar{f}_{k}(x)\rVert_{1}$. Then the proof is complete.

As the two decoders are equivalent, we have that Forward Correction is
equivalent to CPE with

  * •

Hypothesis Set: $\\{x\mapsto U^{\top}f(x;\theta):\theta\in\Theta\\}$

  * •

Decoder: $\operatorname*{argmin}_{k}\lVert\bar{f}(x;\theta)-U_{k}\rVert_{1}$.

when the transition layer is fixed to the uniform transition matrix.

##### Surrogate Complementary Loss

In the training phase, Surrogate Complementary Loss with Log Loss optimizes
the following loss functions:

$L_{\text{SCL}}(\theta)=\frac{1}{N}\sum_{i=1}^{N}-\log(1-f(x_{i};\theta))_{\bar{y}_{i}}$
(28)

In the inference phase, this method predicts the ordinary labels by
$\hat{y}=\operatorname*{argmax}_{k}f_{k}(x)$ for an unseen instance $x$. We
claim that this method is equivalent CPE with:

  * •

Hypothesis Set: $\\{x\mapsto U^{\top}f(x;\theta):\theta\in\Theta\\}$

  * •

Decoder: $\operatorname*{argmin}_{k}\lVert\bar{f}(x;\theta)-U_{k}\rVert_{1}$.

###### Proof

Observe that the training objective function for CPE with the hypothesis set
has the following property:

$\displaystyle L_{\text{CPE}}(\theta)$
$\displaystyle=\frac{1}{N}\sum_{i=1}^{N}-\log\left(U^{\top}f(x_{i};\theta)_{\bar{y}_{i}}\right)=\frac{1}{N}\sum_{i=1}^{N}-\log\Bigg{(}\frac{1}{K-1}\sum_{k\neq\bar{y}_{i}}f_{k}(x_{i};\theta)\Bigg{)}$
(29)
$\displaystyle=\frac{1}{N}\sum_{i=1}^{N}-\log\big{(}1-f_{\bar{y}_{i}}(x_{i};\theta)\big{)}+\log(K-1)=L_{\text{SCL}}(\theta)+\log(K-1)$
(30)

That is, the objective function only differs by a constant. As a result, the
two methods match during the training phase.

In inference phase, SCL predicts
$\hat{y}=\operatorname*{argmax}_{k}f(x;\theta)$ for unseen instance $x$ as in
Forward Correction. In addition, they have the same hypothesis set
$\\{x\mapsto U^{\top}f(x;\theta):\theta\in\Theta\\}$ if the transition layer
of Forward Correction is fixed to uniform. Hence, SCL is equivalent to Forward
Correction with uniform transition layer. It implies that they have the same
decoder: $\hat{y}=\operatorname*{argmin}_{k}\lVert\bar{f}(x)-U_{k}\rVert_{1}$.

##### Discriminative Model

In the training phase, Discriminative Model with unweighted loss optimizes the
following loss functions:

$L_{\text{DM}}(\theta)=\frac{1}{N}\sum_{i=1}^{N}-\log\big{(}\operatorname*{\mathrm{sm}}(1-f(x_{i};\theta))\big{)}_{\bar{y}_{i}}$
(31)

In the inference phase, this method predicts the ordinary labels by
$\hat{y}=\operatorname*{argmax}_{k}f_{k}(x)$ for an unseen instance $x$. We
claim that this method is equivalent CPE with:

  * •

Hypothesis Set:
$\\{x\mapsto\operatorname*{\mathrm{sm}}(1-f(x;\theta)):\theta\in\Theta\\}$

  * •

Decoder: $\operatorname*{argmin}_{k}\lVert\bar{f}(x;\theta)-U_{k}\rVert_{1}$.

###### Proof

The equivalence in the training phase is clear by plugging in the hypothesis
to the surrogate complementary estimation loss. During inference phase, first
observe that

$\bar{f}_{k}(x)=\frac{1}{Z}\exp\big{(}1-f_{k}(x_{i};\theta)\big{)}=\frac{e}{Z}\exp\big{(}-f_{k}(x_{i};\theta)\big{)},$
(32)

where $Z=\sum_{k=1}^{K}\exp\big{(}1-f_{k}(x_{i};\theta)\big{)}$ is the
normalization term. As $x\mapsto\exp(-x)$ is monotonic decreasing, we have
that
$\operatorname*{argmin}_{k}\bar{f}_{k}(x;\theta)=\operatorname*{argmax}_{k}f_{k}(x;\theta)$.
Next, as we have shwon
$\operatorname*{argmin}_{k}\bar{f}_{k}(x)=\operatorname*{argmin}_{k}\lVert
U_{k}-\bar{f}_{k}(x)\rVert_{1}$, so
$\operatorname*{argmax}_{k}f_{k}(x;\theta)=\operatorname*{argmin}_{k}\lVert
U_{k}-\bar{f}_{k}(x)\rVert_{1}$, implying that both methods predict the same
label for all instances.

##### Observations by viewing earlier approaches with the proposed framework

We also draw the following observations by viewing earlier approaches with the
proposed CPE framework:

  1. 1.

By viewing Fwd with the proposed framework, the equivalent decoder essentially
converts the complementary probability estimates back to the ordinary
probability estimates and predicts the largest one. We name it Max decoding
for future reference.

  2. 2.

If the transition matrix is uniform, then Fwd and SCL with log loss match,
suggesting that they are the same in this situation. It explains why those two
methods have similar performances in [1], which is also reproduced in our
experiment, reported in Table 3.

  3. 3.

DM was proposed to lift the generation assumption of complementary labels [2],
but from the view of the CPE framework, DM implicitly assumes the
complementary labels are generated uniformly, as we can see from the decoder.
This provides an alternative explanation why its performance deteriorates as
the transition matrix deviates from the uniform matrix, as shown in [2].

##  Appendix 0.C Experiment Details

In this section, we provide missing details of the experiments in Section 4.

###  0.C.1 Setup

##### Datasets

Across the experiments, we use the following datasets:

  * •

MNIST

  * •

Fashion-MNIST

  * •

Kuzushiji-MNIST

For the above dataset, the size of the training set is 60000, and the size of
the testing set is 10000. To perform the hyperparameter selection, in each
trial, we split 10 percent of the training dataset randomly as the validation
dataset. We performed five trials with different random seeds for all the
experiments in this paper. To ensure a fair comparison, the dataset split and
the generated complementary labels are the same for the benchmark algorithms.
Also, we did not include data augmentation or consistency regularization [8]
in the experiment to prevent introducing extra factors and simplify the
comparison.

##### Models

We implemented the deep models in PyTorch. The base models considered in the
experiment are linear and one-layer mlp model (d-500-c) with 500 hidden units.
In CPE-T, the parameter of the transition layer is initialized such that it
matches the provided transition matrix, i.e. it is initialized to $W_{0}$ such
that $T(W_{0})=T$. All models are optimized using Adam with learning rate
selected from {1e-3, 5e-4, 1e-4, 5e-5, 1e-5} and a fixed weight decay 1e-4 for
300 epochs. We used the default parameters in PyTorch for other parameters in
Adam. The experiments are run with Nvidia Tesla V100 GPUs.

For the two traditional models, we used the K nearest neighbor (KNN)
classifier from scikit-learn with the number of neighbors selected from
$\\{10,20,\dotsc,250\\}$ based on the complementary estimation loss on the
validation dataset. We performed PCA on the dataset to map the feature to a
$32$-dimension space for KNN to reduce the training/inference time. We used
Gradient Boosting Decision Tree from LightGBM, and set the objective to
“multiclass” to optimize the log loss. The hyperparameters include the number
of trees $\\{5,10,\dotsc,500\\}$ and learning rate
$\\{0.01,0.025,0.05,0.1\\}$. Those parameters are also selected based on the
complementary estimation loss on the validation dataset.

###  0.C.2 Additional Results

This section provides figures and tables that are helpful in analyzing the
experiment results.

##### Benchmark results of linear models

Table 6 and 7 provide the the noiseless and noisy benchmark results using
linear models as base models, using the same setting in Section 4.1. We can
see that the proposed CPE performs slightly better or is competitive with the
baseline methods in most scenarios. When the transition matrix is highly
inaccurate ($\lambda=0.5$), CPE outperforms the baselines and is more stable
in terms of testing accuracies. These are consistent with our observation when
using mlp as base models.

Table 6: Comparison of the testing classification accuracies with different transition matrices. | MNIST | Fashion-MNIST | Kuzushiji-MNIST
---|---|---|---
| Unif. | Weak | Strong | Unif. | Weak | Strong | Unif. | Weak | Strong
URE-GA |  81.7$\pm$ 0.5 |  73.4$\pm$ 1.4 |  23.7$\pm$ 2.9 |  76.2$\pm$ 0.3 |  70.8$\pm$ 1.5 |  21.3$\pm$ 5.5 |  51.0$\pm$ 1.0 |  43.7$\pm$ 1.0 |  16.7$\pm$ 2.5
SCL | 90.5$\pm$ 0.2 |  90.2$\pm$ 0.2 |  25.0$\pm$ 17.9 |  82.0$\pm$ 0.4 |  79.6$\pm$ 2.2 |  26.2$\pm$ 8.7 |  59.9$\pm$ 0.9 |  58.9$\pm$ 0.7 |  16.4$\pm$ 2.2
DM |  89.7$\pm$ 0.5 |  89.1$\pm$ 0.2 |  22.7$\pm$ 8.5 |  81.8$\pm$ 0.3 |  78.2$\pm$ 3.1 |  23.6$\pm$ 5.5 | 61.0$\pm$ 1.5 |  59.4$\pm$ 1.4 |  17.7$\pm$ 3.0
Fwd | 90.5$\pm$ 0.2 |  90.6$\pm$ 0.4 |  91.6$\pm$ 0.7 |  82.0$\pm$ 0.4 |  81.6$\pm$ 1.2 | 83.4$\pm$ 0.7 |  59.9$\pm$ 0.9 |  60.4$\pm$ 0.9 |  62.6$\pm$ 0.7
CPE-I |  80.4$\pm$ 0.3 |  73.5$\pm$ 1.3 |  76.1$\pm$ 1.6 |  74.6$\pm$ 0.5 |  71.0$\pm$ 1.5 |  74.7$\pm$ 2.3 |  49.7$\pm$ 0.6 |  42.8$\pm$ 0.8 |  46.8$\pm$ 1.4
CPE-F | 90.5$\pm$ 0.2 | 90.7$\pm$ 0.1 | 91.8$\pm$ 0.4 | 82.2$\pm$ 0.3 | 82.4$\pm$ 0.4 |  83.1$\pm$ 1.0 |  60.4$\pm$ 0.6 | 60.8$\pm$ 0.4 |  62.8$\pm$ 0.2
CPE-T | 90.5$\pm$ 0.2 |  90.6$\pm$ 0.1 | 91.8$\pm$ 0.4 |  82.0$\pm$ 0.3 |  82.1$\pm$ 0.5 |  83.2$\pm$ 1.2 |  60.3$\pm$ 0.5 |  60.6$\pm$ 0.5 | 63.0$\pm$ 0.3
Table 7: Comparison of the testing classification accuracies with different levels of noise. | MNIST | Fashion-MNIST | Kuzushiji-MNIST
---|---|---|---
| $\lambda=0.1$ | $\lambda=0.2$ | $\lambda=0.5$ | $\lambda=0.1$ | $\lambda=0.2$ | $\lambda=0.5$ | $\lambda=0.1$ | $\lambda=0.2$ | $\lambda=0.5$
URE-GA |  22.8$\pm$ 2.0 |  21.1$\pm$ 4.4 |  21.4$\pm$ 1.6 |  20.2$\pm$ 6.7 |  23.5$\pm$ 3.9 |  22.6$\pm$ 3.1 |  16.8$\pm$ 2.1 |  16.4$\pm$ 2.8 |  15.2$\pm$ 2.2
SCL |  25.6$\pm$ 13.8 |  23.9$\pm$ 10.3 |  23.7$\pm$ 4.3 |  23.9$\pm$ 7.8 |  24.5$\pm$ 5.2 |  26.0$\pm$ 3.2 |  17.8$\pm$ 2.5 |  17.8$\pm$ 3.2 |  17.4$\pm$ 1.3
DM |  23.3$\pm$ 7.4 |  22.4$\pm$ 8.7 |  23.4$\pm$ 2.9 |  24.1$\pm$ 7.1 |  24.3$\pm$ 5.0 |  25.6$\pm$ 3.9 |  18.1$\pm$ 2.6 |  17.6$\pm$ 2.4 |  16.5$\pm$ 1.4
Fwd |  91.1$\pm$ 0.7 |  89.6$\pm$ 1.0 |  82.5$\pm$ 3.6 |  82.4$\pm$ 0.9 |  81.4$\pm$ 0.9 |  72.0$\pm$ 7.5 | 62.7$\pm$ 1.0 |  60.9$\pm$ 0.9 |  52.1$\pm$ 6.2
CPE-I |  75.7$\pm$ 2.0 |  75.4$\pm$ 2.0 |  73.8$\pm$ 2.2 |  74.6$\pm$ 2.3 |  73.9$\pm$ 2.2 |  71.1$\pm$ 2.0 |  47.0$\pm$ 1.4 |  46.5$\pm$ 1.3 |  43.4$\pm$ 1.1
CPE-F |  91.2$\pm$ 0.7 |  90.2$\pm$ 1.0 |  85.2$\pm$ 1.7 |  82.2$\pm$ 1.2 |  81.0$\pm$ 1.5 |  75.4$\pm$ 3.3 |  61.9$\pm$ 0.9 | 61.1$\pm$ 2.2 | 53.4$\pm$ 1.5
CPE-T | 91.3$\pm$ 0.7 | 90.5$\pm$ 0.8 | 85.7$\pm$ 1.6 | 82.6$\pm$ 1.3 | 81.6$\pm$ 1.3 | 78.0$\pm$ 1.6 |  62.2$\pm$ 0.8 | 61.7$\pm$ 1.7 | 55.0$\pm$ 1.1

##### Comparison of validation processes

Table 8: Comparison of CPE-T’s testing accuracies using different validation procedures. | MNIST | Fashion-MNIST | Kuzushiji-MNIST
---|---|---|---
| Unif. | Weak | Strong | Unif. | Weak | Strong | Unif. | Weak | Strong
linear |  |  |  |  |  |  |  |  |
URE |  90.3$\pm$ 0.6 |  90.4$\pm$ 0.3 |  91.8$\pm$ 0.5 | 82.1$\pm$ 0.3 |  81.5$\pm$ 1.2 |  82.6$\pm$ 1.3 |  59.9$\pm$ 0.4 |  60.0$\pm$ 0.9 |  62.5$\pm$ 0.5
SCEL | 90.5$\pm$ 0.2 | 90.6$\pm$ 0.1 |  91.8$\pm$ 0.4 |  82.0$\pm$ 0.3 | 82.1$\pm$ 0.5 | 83.2$\pm$ 1.2 | 60.3$\pm$ 0.5 | 60.6$\pm$ 0.5 | 63.0$\pm$ 0.3
mlp |  |  |  |  |  |  |  |  |
URE |  92.7$\pm$ 0.5 |  91.8$\pm$ 0.7 |  90.4$\pm$ 6.5 |  82.9$\pm$ 0.1 |  83.0$\pm$ 0.3 |  84.3$\pm$ 1.5 | 63.8$\pm$ 0.7 |  63.8$\pm$ 1.9 | 74.5$\pm$ 2.7
SCEL | 92.8$\pm$ 0.6 | 92.1$\pm$ 0.2 | 95.2$\pm$ 0.5 | 83.0$\pm$ 0.1 |  83.0$\pm$ 0.3 | 85.8$\pm$ 0.3 |  63.6$\pm$ 0.4 | 64.6$\pm$ 0.4 |  74.2$\pm$ 2.8
| $\lambda=0.1$ | $\lambda=0.2$ | $\lambda=0.5$ | $\lambda=0.1$ | $\lambda=0.2$ | $\lambda=0.5$ | $\lambda=0.1$ | $\lambda=0.2$ | $\lambda=0.5$
linear |  |  |  |  |  |  |  |  |
URE |  90.9$\pm$ 1.0 |  90.2$\pm$ 0.8 | 86.1$\pm$ 1.3 |  82.2$\pm$ 1.3 |  81.2$\pm$ 1.4 |  77.1$\pm$ 1.8 | 62.3$\pm$ 0.8 |  60.6$\pm$ 0.9 | 55.3$\pm$ 2.3
SCEL | 91.3$\pm$ 0.7 | 90.5$\pm$ 0.8 |  85.7$\pm$ 1.6 | 82.6$\pm$ 1.3 | 81.6$\pm$ 1.3 | 78.0$\pm$ 1.6 |  62.2$\pm$ 0.8 | 61.7$\pm$ 1.7 |  55.0$\pm$ 1.1
mlp |  |  |  |  |  |  |  |  |
URE |  83.7$\pm$ 9.7 |  90.8$\pm$ 4.7 |  82.9$\pm$ 9.4 |  83.0$\pm$ 3.2 |  74.8$\pm$ 10.1 |  74.3$\pm$ 10.1 |  68.5$\pm$ 11.4 |  67.1$\pm$ 7.7 |  57.2$\pm$ 16.3
SCEL | 94.4$\pm$ 0.5 | 93.7$\pm$ 0.5 | 89.6$\pm$ 0.9 | 84.1$\pm$ 0.8 | 83.2$\pm$ 1.1 | 78.9$\pm$ 2.0 | 76.1$\pm$ 1.3 | 73.9$\pm$ 1.6 | 64.2$\pm$ 1.2
Table 9: Comparison of Fwd’s testing accuracies using different validation procedures. | MNIST | Fashion-MNIST | Kuzushiji-MNIST
---|---|---|---
| Unif. | Weak | Strong | Unif. | Weak | Strong | Unif. | Weak | Strong
linear |  |  |  |  |  |  |  |  |
URE |  90.5$\pm$ 0.2 |  90.6$\pm$ 0.4 |  91.6$\pm$ 0.7 |  82.0$\pm$ 0.4 |  81.6$\pm$ 1.2 |  83.4$\pm$ 0.7 |  59.9$\pm$ 0.9 |  60.4$\pm$ 0.9 |  62.6$\pm$ 0.7
SCEL |  90.5$\pm$ 0.2 | 90.7$\pm$ 0.2 | 91.9$\pm$ 0.4 | 82.2$\pm$ 0.3 | 82.6$\pm$ 0.3 | 83.8$\pm$ 0.2 | 60.4$\pm$ 0.6 | 61.2$\pm$ 0.3 | 63.2$\pm$ 0.2
mlp |  |  |  |  |  |  |  |  |
URE |  94.4$\pm$ 0.2 |  91.9$\pm$ 0.3 |  95.3$\pm$ 0.4 |  82.6$\pm$ 0.6 |  83.0$\pm$ 1.0 |  85.5$\pm$ 0.3 |  73.5$\pm$ 1.6 |  63.1$\pm$ 2.6 |  74.1$\pm$ 4.8
SCEL |  94.4$\pm$ 0.2 | 92.0$\pm$ 0.2 | 95.5$\pm$ 0.2 | 83.0$\pm$ 0.1 | 83.3$\pm$ 0.2 | 86.1$\pm$ 0.5 |  73.5$\pm$ 1.6 | 64.8$\pm$ 0.5 | 75.3$\pm$ 2.6
| $\lambda=0.1$ | $\lambda=0.2$ | $\lambda=0.5$ | $\lambda=0.1$ | $\lambda=0.2$ | $\lambda=0.5$ | $\lambda=0.1$ | $\lambda=0.2$ | $\lambda=0.5$
linear |  |  |  |  |  |  |  |  |
URE |  91.1$\pm$ 0.7 |  89.6$\pm$ 1.0 |  82.5$\pm$ 3.6 |  82.4$\pm$ 0.9 |  81.4$\pm$ 0.9 |  72.0$\pm$ 7.5 | 62.7$\pm$ 1.0 |  60.9$\pm$ 0.9 |  52.1$\pm$ 6.2
SCEL | 91.4$\pm$ 0.5 | 90.5$\pm$ 0.5 | 83.9$\pm$ 2.6 | 83.2$\pm$ 0.3 | 82.4$\pm$ 0.4 | 76.3$\pm$ 2.8 |  62.5$\pm$ 0.9 | 62.5$\pm$ 1.6 | 55.6$\pm$ 2.0
mlp |  |  |  |  |  |  |  |  |
URE |  88.3$\pm$ 8.7 |  83.9$\pm$ 10.7 |  71.6$\pm$ 18.4 |  84.8$\pm$ 0.6 |  80.2$\pm$ 6.2 |  62.9$\pm$ 20.1 |  72.8$\pm$ 5.6 |  67.6$\pm$ 7.5 |  54.7$\pm$ 12.4
SCEL | 94.4$\pm$ 0.3 | 93.5$\pm$ 0.3 | 84.5$\pm$ 4.1 | 85.0$\pm$ 0.3 | 84.0$\pm$ 0.5 | 76.5$\pm$ 2.5 | 76.4$\pm$ 1.1 | 73.8$\pm$ 1.2 | 59.9$\pm$ 3.4

Table 8 and 9 provide comparison of validation process using URE and the
proposed SCEL. In Table 8, we observe that SCEL selects better parameters in
most cases. We also observe that when the transition matrix is inaccurate, the
parameters selected by SCEL tends to be more stable, especially when the base
models are mlp. This demonstrates the superiority of SCEL despite not being an
unbiased estimator of the classification accuracies. In Table 9, we further
apply SCEL to Fwd. Similarly, we observe that SCEL selects better parameters
in most cases. This suggests that the proposed validation procedure can not
only be applied to CPE but also earlier approaches. It enables a more robust
approach to validate earlier methods.

Figure 1: Comparison of the training and validation loss of CPE with different
transition layers in MNIST under different transition matrices. CPE-F and
CPE-T perform almost identically, so the red lines and blue lines overlap in
the figures. The shaded area denotes the standard deviation of five random
trials.

Figure 2: Comparison of the training and validation loss of CPE with different
transition layers in MNIST under different noise level. CPE-F and CPE-T
perform almost identically when $\lambda$ is small, so the red lines and blue
lines overlap in those figures. The shaded area denotes the standard deviation
of five random trials.

##### Training and validation loss curves

Figure 2 and 2 demonstrate the loss curve of the proposed CPE framework.


11institutetext: Md. Fahim Sikder 22institutetext: Department of Computer
Science & Engineering, Jahangirnagar University, Savar, Bangladesh, 22email:
<EMAIL_ADDRESS>
# Bangla Handwritten Digit Recognition and Generation

Md Fahim Sikder

###### Abstract

Handwritten digit or numeral recognition is one of the classical issues in the
area of pattern recognition and has seen tremendous advancement because of the
recent wide availability of computing resources. Plentiful works have already
done on English, Arabic, Chinese, Japanese handwritten script. Some work on
Bangla also have been done but there is space for development. From that
angle, in this paper, an architecture has been implemented which achieved the
validation accuracy of 99.44% on BHAND dataset and outperforms Alexnet and
Inception V3 architecture. Beside digit recognition, digit generation is
another field which has recently caught the attention of the researchers
though not many works have been done in this field especially on Bangla. In
this paper, a Semi-Supervised Generative Adversarial Network or SGAN has been
applied to generate Bangla handwritten numerals and it successfully generated
Bangla digits.

##  1 Introduction

Recognizing handwritten numerals is one of the emerging problems in the sector
of computer vision. Automation of the banking system, postal services, form
processing are the practical example of handwritten character recognition Pal
et al (2009, 2012); Yacoubi (2001); Bunke et al (2004); Madhvanath et al
(1995); Srihari et al (1995); Bhowmik et al (2018). A lot of work already has
been done with great accuracy in the recognition of English handwritten digits
Bengio et al (2007); LeCun et al (1995). Researchers used support vector
machine, histogram of gradient oriented, neural network etc algorithm to solve
these problems. Recently, a lot of focus has been drawn to the neural network
architecture due to the wide availability of high-performance computing
systems Abir et al (2019). ANNs are computing system which is influenced by
the organic neural network. Convolutional Neural Network is one of the
architectures of neural network which makes it easy to recognize image with
great accuracy. Besides English, a lot of work also done in Arabic, Chinese,
Japanese and Roman scripts Broumandnia et al (2008); El Qacimy et al (2015);
Dehghan et al (2001); Liu et al (2002); Su (2013); Srihari et al (2007);
Koerich et al (2005); Bunke (2003); Bozinovic and Srihari (1989). But in the
case of Bangla, not many works have been done and there is a chance for
improvement.

On the other hand, generating images is another outstanding image processing
field recently caught the attention of researchers. Image generation can be
used in art creation, fraudulent detection also can be applied in law
enforcement. Generative Adversarial Network or GAN, another architecture of
neural network is been used to generate the image. Researchers also applied
GAN to generate MNIST dataset but not much work has been done in other
datasets. To mend this research gap on Bangla, we have implemented an
architecture which recognizes Bangla handwritten digits at 99.44% accuracy
using BHAND dataset which contains 70000 images of Bangla handwritten digits
which are collected from 1750 persons. At the same time, we have implemented a
semi-supervised generative adversarial network or SGAN to generate Bangla
digits. The paper is arranged as follows: Section 2 reviews the relevant
works, Section 3 describes the proposed solution, Section 4 describes the
result and lastly, Section 5 concludes the paper.

##  2 Related Works

A lot of research works have been done on Bangla handwritten digit recognition
using SVM Bhowmik et al (2009), HOG Bhattacharya and Chaudhuri (2009) etc.
Recently loads of attention is being given on deep learning because of easy
access to GPU (graphics processing unit). Using multilayer convolutional
layer, pooling layer increases the performance of accuracy. Some of the
legendary deep learning based architecture such as Alexnet Krizhevsky et al
(2012), LeNet LeCun et al (1990), Inception V3 Szegedy et al (2015) took the
accuracy of image recognition to the next level. MNIST recognition LeCun et al
(1989), CIFAR-10 database recognition Krizhevsky et al (2012) are some example
of that architecture. For Bangla handwritten recognition numerous work has
been done. But initially, it was troublesome for the researcher because of the
limitation of a dataset Akhand et al (2015). But now some great datasets are
available for Bangla digit recognition. A deep belief network is being
introduced where the author first used unsupervised feature learning then it’s
followed by a supervised fine-tuning Sazal et al (2014). In Chowdhury and
Rahman (December 2016), the author removed overfitting problem and has an
error rate of 1.22%.

Besides digit recognition, few works have been done on digit generation.
Researchers used different kinds of generative adversarial networks (GAN) to
generate digits or characters. Auxiliary Classifier GAN Odena et al (2016),
Bidirectional GAN Donahue et al (2016), Deep Convolutional GAN Radford et al
(2015), Semi-Supervised GAN Odena (2016) were used on MNIST dataset to
generate digits.

##  3 Proposed Work

In this work, we have proposed a architecture for digit recognition which
outperforms Alexnet Krizhevsky et al (2012) and Inception V3 Szegedy et al
(2015) model at validation accuracy and error on the BHAND Chowdhury and
Rahman (December 2016) dataset. Also, we have implemented Semi-Supervised
Generative Adversarial Network (SGAN) for digit generation for the same
dataset.

###  3.1 Dataset Description

For recognition and generation, BHAND dataset has been used which contains
70000 handwritten Bangla digits. This is one of the biggest datasets of
handwritten Bangla digits. This dataset is divided into three sets: Training
set (50000), Testing set (10000) and Validation set (10000). These 70000 data
is collected from 1750 persons. The images are gray-scale and the dimension is
$32*32$.

###  3.2 Network Architecture

For recognizing handwritten digit, we have proposed an architecture which
consists several convolutional layers, pooling layers, normalization layers,
and dense or fully connected layers. In the first convolutional layer, we took
the $32*32$ images as input from the dataset. As mentioned earlier the images
are grayscale, so it has $1$ channel. In this layer, we have taken $32$ filter
which has the filter size of $2*2$.

Figure 1: Blocks of the architecture

The output of this layer then goes into a second convolutional layer which
also has $32$ filters and the size of those filters is $2*2$. Then the outcome
of the second convolutional layer feed into max pooling layer which has the
filter size of $2*2$ and the stride size is $2$. This outcome then goes into a
normalization layer. These convolutional layers, pooling layer and
normalization layer, together we named it $block$. In a single block the
number of these layers could vary. The second block is composed of three
convolutional layers, one max pooling layer, and another normalization layer.
The amount of filters in the second block’s convolutional layers are $64$ and
the filter size is $3*3$. This max pooling layer has also $2*2$ filter size
and stride of $2$. Then the third to sixth block consists of two convolutional
layers, one pooling layer and one normalization layer. Third block’s
convolutional layer has $128$ filters and the size of the filters is $5*5$,
fourth block’s convolutional layer has $256$ filters which has $5*5$ filter
size, fifth block’s convolutional layer has $384$ filters, sixth block’s
convolutional layer has $512$ filters and their filter size is $5*5$. And all
the blocks have the same pooling layer architecture. It has $2*2$ filter size
and stride size $2$. Figure 1 shows the blocks used in this architecture.

The outcome of the sixth block then feed into a fully connected layer which
has $1024$ units then we drop the $50\%$ of the neuron for avoiding
overfitting then the output is fed on the second fully connected layer which
has $5120$ units. Here we also drop the $50\%$ of the neuron. Till now every
layer used $relu$ activation function. The following equation Sharma (2018) is
how $relu$ works.

$R(z)=max(0,z)$

Now the output is then fed into the last fully connected layer which has $10$
units because we have $10$ class as output and here we have used $softmax$
activation function. The following equation Sharma (2018) is how $softmax$
works.

$s(z)_{j}=\frac{e^{z_{j}}}{\sum_{k=1}^{K}e^{z_{k}}}$

The complete architecture of the recognizing part is shown in figure 2.

Figure 2: Our architecture for digit recognition

Now for the digit generation part, here Semi-Supervised Generative Adversarial
Network (SGAN) Odena (2016) is used for this task. Here we have a generator
and discriminator. We took random noise as input, then the noise goes to the
generator, at the same time we took a sample from training dataset. The
generator attempts to forge the sample from training dataset and both the real
and fake data goes to the discriminator then the discriminator attempts to
distinguish between the genuine and the fabricated one. Usually, in GAN we
train generator and discriminator concurrently and after training, we could
discard discriminator because its only used for training the generator. In
SGAN we alter the discriminator into a classifier and we discard the generator
after the training. Here generator is used to aid the discriminator during
training. Figure 3 shows the complete architecture of the SGAN.

In the generator, first, we took a random vector as input then we reshape it
and then batch normalize it. Then we $upsample$ the output. After that, we
took a convolutional layer and pass the output through it. The convolutional
layer has $128$ filters and the filter size is $3*3$ also we used the $same$
padding. We again use batch normalize and upsample in it. After that, we use
another convolutional layer which has the same filter size and padding but it
has only 64 filters and we again batch normalize it. The last two
convolutional layers used $relu$ activation function. Now the output is passed
through the last convolutional layer which has one filter and the filter size
and padding are like the same as others and it used $tanh$ activation
function. Now for the discriminator part, it is a multiclass classifier. We
have used four convolutional layers. First convolutional layer takes $32*32$
images and it has $32$ filters which have the size of $3*3$ also the strides
of 2 to reduce the dimension of the feature vectors. Here we have used
$LeakyRectifiedLinearUnit$ activation functions.

Figure 3: Architecture of SGAN

Then we drop 25% of neurons for avoiding overfitting. Then the output goes to
the next convolutional layers which have 64 filters and the size and strides
are same as the last one. Then again, we drop 25% of neuron and use batch
normalization. In the third and fourth convolutional layer, the filter size is
the same but has 128 and 256 filters respectively. Then we flatten the output.
In the end, we used two dense or fully connected layers. The last layer takes
$N+1$ units because discriminator could generate $N+1$ outputs because of the
fake label. Here is $N$ is the number of total class and we used $softmax$
activation function. We used $binary-crossentropy$ loss function and $Adam$
optimizer.

##  4 Experimental Analysis & Result

We have implemented our architecture using BHAND dataset which has $50000$
training image, $10000$ testing image and $10000$ validating images of
handwritten Bangla numerals. It has $32*32$ image dimension and the number of
the channel was $1$. For recognizing the digit, we have also applied this
dataset in popular alexnet and inception v3 model. We have run a total of
$19550$ steps in the training and achieved $99.44\%$ validation accuracy. We
have used $rmsprop$ optimizer and $categorical-crossentropy$ as loss function.
The learning rate in our architecture was $0.001$. A detailed analysis of our
experiments is shown in table 1.

Table 1: Comparison of our model with others for recognizing digit Model Name | Steps | Validation Accuracy | Validation Error
---|---|---|---
Alexnet | 19550 | 97.74% | 0.1032
Inception V3 | 19550 | 98.13% | 0.07203
Our Model | 19550 | 99.44% | 0.04524

The validation accuracy and the validation error of our model is shown
respectively in figure 4 and 5.

Figure 4: Validation Accuracy of our model for recognizing digit Figure 5:
Validation Error of our model for recognizing digit

For generating the Bangla handwritten image we also used the same dataset. For
generating an image, we have used the Semi-Supervised Generative Adversarial
Network (SGAN). Here we have built our model using generator and
discriminator. Generator took a random vector as input. On the other hand from
the real train dataset, an image goes to the discriminator. Generator tries to
fool the discriminator by mimicking the real image. Then the discriminator
discriminates the real and forges image. For our generator, we have used a
combination of a fully connected layer, convolutional

Figure 6: Output of our generation model at step 0, 100000, 200000 and 300000

layer. Also, we need to normalize and upsample our data. For the
discriminator, it also has a series of a convolutional layer and fully
connected layer. Discriminator took the image as input to the input dimension
is $32*32$. It used two loss function: $binary-crossentropy$ and $categorical-
crossentropy$ whereas generator used $binary-crossentropy$. Here we have used
Adam optimizer

Figure 7: Training Loss of our model for digit generation

where the learning rate is $0.002$. We have also reshaped our data to $-1$ to
$1$ because of the usage of $sigmoid$ and $tanh$ activation function. After
$300000$ steps of training, we have got $0.368$ loss of discriminator and
$0.694$ generator loss. From figure 6 we can see the output of our SGAN. The
first image (a) is from $0$ step, the second image (b) is after $100000$ and
(c) and (d) image are after respectively $200000$ and $300000$ steps. The
training loss is shown in figure 7.

##  5 Conclusion

Loads of work have been done in the area of handwritten numeral recognition
but still, there is an opportunity to improve and only a few works has been
done in the area of digit generation. From that motivation, in this paper, we
have proposed a architecture for recognizing Bangla handwritten digits which
outperforms popular alexnet and inception v3 architecture using BHAND dataset.
By adding a more convolutional layer and hyperparameter tuning could result in
a better performance. Also, we have implemented the Semi-Supervised Generative
Adversarial Network (SGAN) using the same dataset and successfully generate
Bangla digits. In the future, we will try to reduce the discriminator’s
training loss on SGAN.

## Acknowledgment

The author is grateful to the anonymous reviewers for their comments that
improved the quality of this paper, also thankful to Md. Rokonuzzaman Sir from
ISTT and Umme Habiba Islam for their support and help.

## References

  * Abir et al (2019) Abir B, Mahal SN, Islam MS, Chakrabarty A (2019) Bangla handwritten character recognition with multilayer convolutional neural network. In: Advances in Data and Information Sciences, Springer, pp 155–165
  * Akhand et al (2015) Akhand M, Rahman MM, Shill P, Islam S, Rahman MH (2015) Bangla handwritten numeral recognition using convolutional neural network. In: Electrical Engineering and Information Communication Technology (ICEEICT), 2015 International Conference on, IEEE, pp 1–5
  * Bengio et al (2007) Bengio Y, Lamblin P, Popovici D, Larochelle H (2007) Greedy layer-wise training of deep networks. In: Advances in neural information processing systems, pp 153–160
  * Bhattacharya and Chaudhuri (2009) Bhattacharya U, Chaudhuri BB (2009) Handwritten numeral databases of indian scripts and multistage recognition of mixed numerals. IEEE transactions on pattern analysis and machine intelligence 31(3):444–457
  * Bhowmik et al (2018) Bhowmik S, Malakar S, Sarkar R, Basu S, Kundu M, Nasipuri M (2018) Off-line bangla handwritten word recognition: a holistic approach. Neural Computing and Applications pp 1–16
  * Bhowmik et al (2009) Bhowmik TK, Ghanty P, Roy A, Parui SK (2009) Svm-based hierarchical architectures for handwritten bangla character recognition. International Journal on Document Analysis and Recognition (IJDAR) 12(2):97–108
  * Bozinovic and Srihari (1989) Bozinovic RM, Srihari SN (1989) Off-line cursive script word recognition. IEEE Transactions on pattern analysis and machine intelligence 11(1):68–83
  * Broumandnia et al (2008) Broumandnia A, Shanbehzadeh J, Varnoosfaderani MR (2008) Persian/arabic handwritten word recognition using m-band packet wavelet transform. Image and Vision Computing 26(6):829–842
  * Bunke (2003) Bunke H (2003) Recognition of cursive roman handwriting: past, present and future. In: Document Analysis and Recognition, 2003. Proceedings. Seventh International Conference on, IEEE, pp 448–459
  * Bunke et al (2004) Bunke H, Bengio S, Vinciarelli A (2004) Offline recognition of unconstrained handwritten texts using hmms and statistical language models. IEEE transactions on Pattern analysis and Machine intelligence 26(6):709–720
  * Chowdhury and Rahman (December 2016) Chowdhury AMS, Rahman MS (December 2016) Towards optimal convolutional neural network parameters for bengali handwritten numerals recognition. In: Proceedings of 19th International Conference on Computer and Information Technology (ICCIT), Dhaka, pp 431–436
  * Dehghan et al (2001) Dehghan M, Faez K, Ahmadi M, Shridhar M (2001) Handwritten farsi (arabic) word recognition: a holistic approach using discrete hmm. Pattern Recognition 34(5):1057–1065
  * Donahue et al (2016) Donahue J, Krähenbühl P, Darrell T (2016) Adversarial feature learning. arXiv preprint arXiv:160509782
  * El Qacimy et al (2015) El Qacimy B, Kerroum MA, Hammouch A (2015) Word-based arabic handwritten recognition using svm classifier with a reject option. In: Intelligent Systems Design and Applications (ISDA), 2015 15th International Conference on, IEEE, pp 64–68
  * Koerich et al (2005) Koerich AL, Sabourin R, Suen CY (2005) Recognition and verification of unconstrained handwritten words. IEEE Transactions on Pattern Analysis and Machine Intelligence 27(10):1509–1522
  * Krizhevsky et al (2012) Krizhevsky A, Sutskever I, Hinton GE (2012) Imagenet classification with deep convolutional neural networks. In: Advances in neural information processing systems, pp 1097–1105
  * LeCun et al (1989) LeCun Y, Boser B, Denker JS, Henderson D, Howard RE, Hubbard W, Jackel LD (1989) Backpropagation applied to handwritten zip code recognition. Neural computation 1(4):541–551
  * LeCun et al (1990) LeCun Y, Boser BE, Denker JS, Henderson D, Howard RE, Hubbard WE, Jackel LD (1990) Handwritten digit recognition with a back-propagation network. In: Advances in neural information processing systems, pp 396–404
  * LeCun et al (1995) LeCun Y, Jackel L, Bottou L, Brunot A, Cortes C, Denker J, Drucker H, Guyon I, Muller U, Sackinger E, et al (1995) Comparison of learning algorithms for handwritten digit recognition. In: International conference on artificial neural networks, Perth, Australia, vol 60, pp 53–60
  * Liu et al (2002) Liu CL, Koga M, Fujisawa H (2002) Lexicon-driven segmentation and recognition of handwritten character strings for japanese address reading. IEEE Transactions on Pattern Analysis & Machine Intelligence (11):1425–1437
  * Madhvanath et al (1995) Madhvanath S, Govindaraju V, Ramanaprasad V, Lee DS, Srihari SN (1995) Reading handwritten us census forms. In: Document Analysis and Recognition, 1995., Proceedings of the Third International Conference on, IEEE, vol 1, pp 82–85
  * Odena (2016) Odena A (2016) Semi-supervised learning with generative adversarial networks. arXiv preprint arXiv:160601583
  * Odena et al (2016) Odena A, Olah C, Shlens J (2016) Conditional image synthesis with auxiliary classifier gans. arXiv preprint arXiv:161009585
  * Pal et al (2009) Pal U, Roy K, Kimura F (2009) A lexicon-driven handwritten city-name recognition scheme for indian postal automation. IEICE transactions on information and systems 92(5):1146–1158
  * Pal et al (2012) Pal U, Roy RK, Kimura F (2012) Multi-lingual city name recognition for indian postal automation. In: 2012 International Conference on Frontiers in Handwriting Recognition (ICFHR 2012), IEEE, pp 169–173
  * Radford et al (2015) Radford A, Metz L, Chintala S (2015) Unsupervised representation learning with deep convolutional generative adversarial networks. arXiv preprint arXiv:151106434
  * Sazal et al (2014) Sazal MMR, Biswas SK, Amin MF, Murase K (2014) Bangla handwritten character recognition using deep belief network. In: Electrical Information and Communication Technology (EICT), 2013 International Conference on, IEEE, pp 1–5
  * Sharma (2018) Sharma S (2018) Activation functions: Neural networks
  * Srihari et al (1995) Srihari SN, Shin YC, Ramanaprasad V, Lee DS (1995) Name and address block reader system for tax form processing. In: Document Analysis and Recognition, 1995., Proceedings of the Third International Conference on, IEEE, vol 1, pp 5–10
  * Srihari et al (2007) Srihari SN, Yang X, Ball GR (2007) Offline chinese handwriting recognition: an assessment of current technology. Frontiers of Computer Science in China 1(2):137–155
  * Su (2013) Su T (2013) Chinese handwriting recognition: an algorithmic perspective. Springer Science & Business Media
  * Szegedy et al (2015) Szegedy C, Liu W, Jia Y, Sermanet P, Reed S, Anguelov D, Erhan D, Vanhoucke V, Rabinovich A (2015) Going deeper with convolutions. In: Proceedings of the IEEE conference on computer vision and pattern recognition, pp 1–9
  * Yacoubi (2001) Yacoubi AE (2001) Handwritten month word recognition on brazilian bank checks. In: Proceedings of the Sixth International Conference on Document Analysis and Recognition, IEEE Computer Society, p 972