\section{Introduction}
\IEEEPARstart{S}{emantic} segmentation enables accurate scene understanding~\cite{cordts2016cityscapes}, which benefits a variety of downstream tasks such as autonomous driving, computer-aided diagnosis, and augmented reality~\cite{minaee2021image}.
Recently, semantic segmentation methods based on deep learning have been widely explored and have achieved remarkable progress.
However, these methods require large-scale pixel-level labeled data but pixel-level annotation is quite time-consuming.
Therefore, semi-supervised learning (SSL) is introduced into the semantic segmentation task to utilize cheap and large amounts of unlabeled data.

Consistency regularization and pseudo label are two popular techniques to deal with unlabeled data in SSL segmentation.
Consistency regularization aims to obtain invariant segmentation predictions for each unlabeled pixel under various perturbations, e.g., input perturbation~\cite{zou2020pseudoseg,yuan2021simple}, feature perturbation~\cite{ouali2020semi}, or network perturbation~\cite{chen2021semi}.
The pseudo label method produces an artificial label for each unlabeled pixel and then trains an SSL model by taking the pseudo label as the ground truth (GT) label~\cite{mendel2020semi,ibrahim2020semi,huo2021atso}.
Recently, methods combining consistency regularization and pseudo label have achieved the state-of-the-art (SOTA) performance in SSL segmentation~\cite{zou2020pseudoseg,yuan2021simple,chen2021semi,zeng2021reciprocal}, which compute the consistency loss by pseudo labels to train their models.

These methods rely on an \textbf{optimistic} assumption that they could generate correct pseudo labels based on the knowledge learned from labeled data.
Unfortunately, this assumption does not always hold in practice~\cite{hataya2019unifying,li2019dividemix} since the labeled data are usually sampled randomly from the whole data, and their distribution might be biased~\cite{li2017learning,oliver2018realistic}.
Some previous works observed that wrong pseudo labels force their models to predict wrong classes with high confidence~\cite{tarvainen2017mean}, which seriously degrades the performance of SSL models~\cite{lee2013pseudo,sohn2020fixmatch,xu2021dash}.
To mitigate this problem, some existing approaches propose to filter out low-confidence predictions and train their models by only high-confidence predictions~\cite{xu2021dash,zou2020pseudoseg}.
Some other works utilize low-confidence predictions by negative learning~\cite{rizve2021defense,wang2022semi}.
These methods are based on the basic fact that an uncertain prediction usually gets confused among only a few classes instead of all classes.
Hence, they use uncertain predictions as negative samples for those unlikely classes.
However, filter-based approaches cannot utilize all unlabeled pixels, resulting in insufficient pixel utilization and categorically imbalanced training~\cite{wang2022semi}.
For negative learning-based methods, we analyze that they still implicitly learn the pseudo-label, which means the errors in their models accumulate when the pseudo label is wrong.

\begin{figure*}[tbp]
\centerline{\includegraphics[scale=0.38]{intro_v11.jpg}}
\caption{
(a) Existing methods using top-1 prediction as pseudo-label to learn unlabeled data.
(b) Our proposed PCR, which selects K predictions into a candidate label set to learn unlabeled data.
}
\label{fig:intro}
\end{figure*}

In this paper, we propose a Pessimistic Consistency Regularization (PCR) method, which is based on a form of \textbf{pessimism} concerning the pseudo label, that is, pseudo labels are not always correct.
In order to make it possible for our model to learn the GT label in this pessimistic situation, we provide a candidate label set containing K label proposals for each pixel.
As shown in Figure~\ref{fig:intro}, our candidate label set covers GT labels better than the existing pseudo label~\cite{zou2020pseudoseg,yuan2021simple,chen2021semi,zeng2021reciprocal}, thus training a better SSL model than existing optimistic methods.
Specifically, our PCR contains two key components.
One is a candidate label proposal method, which adaptively provides $K$ pseudo label proposals for each pixel.
And the other one is a pessimistic consistency loss, which allows our model to learn the possible GT label from the candidate label set in a multi-label classification manner.

We evaluate the effectiveness of our PCR on SSL segmentation with VOC2012, Cityscapes, and VOC2012 LowData datasets using CPS~\cite{chen2021semi} and AEL~\cite{hu2021semi} as baselines.
Furthermore, we theoretically and empirically analyze that PCR outperforms existing methods since it revises the gradients of learning unlabeled data when the pseudo label is wrong.
The main contributions of this work are:
\begin{itemize}
  \item PCR provides a new idea for improving SSL segmentation methods, that is, learning the possible GT label from a multi-label classification manner.

  \item We propose a candidate label proposal algorithm to adaptively provide multiple possible labels for each pixel.
  In addition, we propose a pessimistic consistency loss which allows our model to learn the possible GT label in the candidate label set.

  \item PCR is easy to implement and could be applied to existing methods without changing their frameworks.
\end{itemize}

\section{Related work}
\subsection{Semi-supervised Learning}
The purpose of semi-supervised learning is to improve the performance of a model trained on limited labeled data by utilizing a large amount of unlabeled data.
Current deep SSL classification methods utilize entropy minimization and consistency regularization to learn the unlabeled data.
Entropy minimization based methods enforce the predictions of unlabeled data to be sharp which is commonly realized by training their model via pseudo labels~\cite{lee2013pseudo, xie2019unsupervised, berthelot2019mixmatch, berthelot2019remixmatch,sohn2020fixmatch,9703190}.
Consistency regularization based methods enforce their models to predict consistent results for the same image in different perturbations to make the classification boundaries pass through the data sparse region.
VAT~\cite{miyato2018virtual} leverages consistency regularization by adding adversarial noise on unlabeled images.
UDA~\cite{xie2019unsupervised}, MixMatch~\cite{berthelot2019mixmatch}, ReMixMatch~\cite{berthelot2019remixmatch}, and EnAET~\cite{9301261} employ data interpolation and weak and strong augmentation to computed the consistency loss.
Temporal Model~\cite{laine2016temporal} and Mean teacher~\cite{tarvainen2017mean} use a teacher model and a student model and compute the consistency of their predictions to train the student model.
And methods combining consistency regularization and entropy minimization have achieved SOTA performance currently~\cite{sohn2020fixmatch, zhang2021flexmatch}, whose common feature is computing consistency regularization using pseudo labels.
There are also some works that focus on improving existing methods.
Sinkhorn Label Allocation~\cite{tai2021sinkhorn} develops an annealing strategy for label assignment allowing for the inclusion of prior knowledge on class proportions via flexible upper-bound constraints.
Chen et al.~\cite{chen2020negative} introduce the thought of negative sampling into semi-supervised learning by simply adding a loss function.
Dash~\cite{xu2021dash} uses a dynamic threshold to generate accurate pseudo labels based on FixMatch.
Other Methods like SimPLE~\cite{hu2021simple} and CReST~\cite{wei2021crest} are proposed to utilize the information between classes and to solve the problem of category imbalance, respectively.
There are also some graph-based methods solving the semi-supervised problem through label propagation~\cite{kamnitsas2018semi,calder2020poisson,7931596}.

\subsection{Semi-supervised Semantic Segmentation}
Semantic segmentation is a basic task of computer vision that requires abundant high-quality pixel-level annotation.
Considering the expensive labor costs of pixel-level annotation, some works propose to explore the semi-supervised semantic segmentation problem and achieve promising results.
Some previous methods use Generative Adversarial Network (GAN) to train their models via a discriminative loss over unlabeled data~\cite{mittal2019semi}, or utilize consistency regularization~\cite{9662661,9843860} and entropy minimization~\cite{9910464} to learn unlabeled data referring to SSL classification algorithms.
More recently, SOTA semi-supervised segmentation methods combine both entropy minimization and consistency regularization to train their models.
PseudoSeg~\cite{zou2020pseudoseg}, AEL~\cite{hu2021semi} and Jianglong Yuan et al.~\cite{yuan2021simple} propose to use the pseudo label generated from weak augmented image to supervise the prediction of strong augmented image.
CPS~\cite{chen2021semi} designs a mutual learning mechanism that trains two student models with pseudo labels from each other.
U2PL~\cite{wang2022semi} proposes to utilize unreliable pixels by negative learning in a contrastive learning manner to make full use of the unlabeled pixels.
Yi et al.~\cite{9652059} propose to use label propagation to refine the pseudo labels.
In addition, some methods propose using pixel-level contrastive learning to utilize the information from unlabeled data~\cite{lai2021semi,zhong2021pixel}.
CAC~\cite{lai2021semi} uses contrastive learning to learn a model which is robust to changing backgrounds.
PC$^{2}$Seg~\cite{zhong2021pixel} proposes a new negative sampling technique that provides reliable negative samples for SSL segmentation.
Different from existing methods, we propose for the first time to pessimistically learn from unlabeled data using an adaptive candidate label set, which effectively reduces the errors brought by wrong pseudo-labels.

\section{Method}\label{sec:method}
We first describe the semi-supervised learning (SSL) segmentation formally.
In particular, for the SSL segmentation task, we have a small labeled data set $D_{l} = \{(x_{l},y_{l})\}_{l=1}^{L}$ and a large unlabeled data set $D_{u} = \{x_{u}\}_{u=1}^{U}$, where $L$ is the size of labeled dataset, and $U$ is the size of unlabeled dataset ($L\ll U$).
The $x_{s},y_{s},x_{u}$ are the image and label of the $s$-th labeled data and the image of the $u$-th unlabeled data, respectively.

The purpose of SSL segmentation is to learn the parameters $\theta$ of a segmentation model $\mathbb{F}(\bullet;\theta)$ by optimizing a loss function that contains both supervised and unsupervised loss:
\begin{equation}
  \begin{aligned}
    \mathcal{L} = \frac{1}{|L|}\sum_{l=1}^{L}\mathcal{L}_{sup}(\mathbb{F}(x_{l};\theta))+\frac{\beta}{|U|}\sum_{u=1}^{U} \mathcal{L}_{uns}(\mathbb{F}(x_{u};\theta)),
  \end{aligned} \label{eq:original_object}
\end{equation}
where $\mathcal{L}_{sup}$ and $\mathcal{L}_{uns}$ are supervised loss and unsupervised loss, and $\beta$ is the regularization weight.

\subsection{Motivation and preliminaries}\label{sec:motivation}
The unsupervised loss in Eq.~\ref{eq:original_object} is formulated as the cross-entropy loss between model output and a pseudo label in current SOTA methods~\cite{zou2020pseudoseg,chen2021semi,yuan2021simple,hu2021semi}.
And the pseudo label is also predicted by their models, whose paradigm is:
\begin{equation}
\begin{aligned}
\overline{\bm{y_{u}}} &= \bm{1}(\arg \max(\mathbb{F}(x_{u}))),~~~\bm{z_{u}} = \hat{\mathbb{F}}(\hat{x}_{u})\\
\mathcal{L}_{u}^{o} &= \frac{1}{|S|}\sum_{s=1}^{S} \mathcal{L}^{o}_{us} (\bm{z_{us}},\overline{\bm{y_{us}}}) \\
&= \frac{1}{|S|}\sum_{s=1}^{S} \sum_{c=1}^{C} -\overline{y_{us}^{c}}\log (\frac{\exp(z_{us}^{c})}{\sum_{n=1}^{C} \exp(z_{us}^{n})}),
\end{aligned} \label{eq:top1 consistency loss}
\end{equation}
where the $\overline{\bm{y_{u}}}$ is the one-hot encoding of the pseudo label generated from a segmentation model $\mathbb{F}$.
The $\bm{1}$ is the one-hot-encoding function.
The $\bm{z}_{u}$ is the output of disturbed model $\hat{\mathbb{F}}$ with disturbed input $\hat{x}_{u}$.
The disturbed model is often realized by adding dropout layers~\cite{laine2016temporal, ouali2020semi} into the model structure, or injecting random noises into the feature maps~\cite{ouali2020semi, liu2022perturbed}.
And the disturbed input is usually realized by data augmentations~\cite{zou2020pseudoseg,chen2021semi,yuan2021simple,hu2021semi}.
The $S$ is the number of pixels in image $x_{u}$ and $C$ is the number of categories, and $\overline{y_{us}^{c}}$ and $z_{us}^{c}$ are the elements of $\overline{\bm{y_{u}}}$ and $\bm{z_{u}}$ for the $c$-th class of the $s$-th pixel.
We name this loss in Eq.~\ref{eq:top1 consistency loss} as optimistic consistency loss $\mathcal{L}^{o}_{u}$ since it optimistically uses the pseudo label as the target.

We see the $\mathcal{L}^{o}_{u}$ is the average of the losses computed on each pixel.
Hence, for simplicity, we next discuss our method using a single pixel as an example.
Without loss of generality, our method works on all pixels.
By the definition of $\mathcal{L}^{o}_{us}$ in Eq.~\ref{eq:top1 consistency loss}, we compute its gradient for the $s$-th pixel in backpropagation:
\begin{equation}
\begin{aligned}
&\frac{\partial \mathcal{L}^{o}_{us}}{\partial z_{us}^{c}}= \left\{\begin{aligned} &p_{us}^{c}-1,~~~if~~\overline{y_{us}^{c}} = 1 \\ &p_{us}^{c},~~~else \end{aligned}\right. \\
&p_{us}^{c} = \frac{\exp(z_{us}^{c})}{\sum_{n=1}^{C} \exp(z_{us}^{n})},
\end{aligned} \label{eq:gradient of top1 consistency loss}
\end{equation}
where the $p_{us}^{c}$ is the predicted probability for the $c$-th class computed by softmax.

According to the gradient descent algorithm, the output $z_{us}^{c}$ for a category $c$ will increase if its gradient is less than 0, and vice versa.
In other words, only the output for the pseudo label category  ($\overline{y_{us}^{c}}=1$) is optimized to increase, and the outputs for other categories ($\overline{y_{us}^{c}}=0$) are optimized to decrease.
This shows that when the pseudo label is correct, $\mathcal{L}_{us}^{o}$ increases the output for the GT category and decreases the outputs for other categories, thus effectively learning unlabeled data.
However, once the pseudo label is wrong, it increases the output for the pseudo label category while decreasing the output for the GT category, which leads to learning unlabeled data incorrectly.

The limitation of the optimistic loss comes from that it optimistically assumes the pseudo label is correct.
In practice, models often confront a pessimistic situation, that is, the pseudo label is not always correct.
To address this issue, we propose pessimistic consistency regularization (PCR) which assumes that the GT category exists in a provided candidate label set that contains K candidate labels including the top-1 pseudo label.
Compared with the existing optimistic assumption, our assumption is more pessimistic and prone to occur.
This is because when the pseudo label is correct, both two assumptions hold.
When the pseudo label is wrong, the optimistic assumption fails, but our assumption may still hold as long as the GT label appears in our candidate label set.
\subsection{Pessimistic Consistency Loss} \label{sec:pessimistic consistency loss}
In our PCR, we generate a candidate label set $\mathbb{Y}_{us} = \{y_{us}^{1},y_{us}^{2},...,y_{us}^{K}\}$ which contains K label proposals for each unlabeled pixel instead of only one pseudo label as in previous works.
Hence we propose a new loss function to learn the possible GT label from $\mathbb{Y}_{us}$.

Different from optimistic methods which assume the top-1 pseudo label is correct, our PCR pessimistically thinks each category in the candidate label set $\mathbb{Y}_{us}$ has the probability to be the GT category.
But the categories outside the candidate set cannot be the GT category, which is in line with optimistic methods.
Hence, we hope that the predictions of our model for the $K$ categories in the candidate label set are larger than the predictions for the rest $C-K$ categories.
We refer to some works in metric learning~\cite{liu2017sphereface,wang2018additive,wang2018cosface,sun2020circle} and formulate our optimization objective for each pixel as:
\begin{equation}
  \begin{aligned}
  \underset{i \in \mathbb{Y}_{us}} \min(z_{us}^{i})~~ >~~ \underset{j \notin \mathbb{Y}_{us}} \max(z_{us}^{j}),
\end{aligned} \label{eq:purpose}
\end{equation}
where $z_{us}^{i}$ represents the output of our model for the $i$-th category.
Eq.~\ref{eq:purpose} means we force the minimum of the outputs for categories in $\mathbb{Y}_{us}$ to be larger than the maximum of the outputs for other categories.
In other words, we enforce all the outputs for categories in $\mathbb{Y}_{us}$ to be larger than those for other categories.
From Eq.~\ref{eq:purpose}, a straightforward loss function is formulated as:
\begin{equation}
  \begin{aligned}
  \mathcal{L}^{p}_{us} = ReLU( \underset{j \notin \mathbb{Y}_{us}} \max(z_{us}^{j}) - \underset{i \in \mathbb{Y}_{us}} \min(z_{us}^{i}) ).
\end{aligned} \label{eq:loss function}
\end{equation}
However, this $\mathcal{L}_{us}^{p}$ is globally non-differentiable with respect to $\bm{z}_{us} = \{z_{us}^{1},z_{us}^{2},...,z_{us}^{C}\}$ since the $\max$ and $\min$ functions in Eq.~\ref{eq:loss function} are globally non-differentiable~\cite{pinter2001globally, mcelreath2018statistical}.
And the \textit{ReLU} function also has a singularity at $x=0$.
Thanks to some existing functional approximation~\cite{nielsen2017guaranteed,mcelreath2018statistical,dugas2001incorporating,glorot2011deep}, we approximate the functions in Eq.~\ref{eq:loss function} to make $\mathcal{L}_{us}^{p}$ differentiable:
\begin{equation}
  \begin{aligned}
  &\max (z^{1},z^{2},...,z^{n}) \approx \log(\sum_{i=1}^{n} \exp{(z^{i})}) \\
  &\min (z^{1},z^{2},...,z^{n}) \approx -\log(\sum_{i=1}^{n} \exp{(-z^{i})}) \\
  &ReLU(z) = \max(z,0) \approx \log(1+\exp(z)).
\end{aligned} \label{eq:functional approximation}
\end{equation}
Based on these functional approximations, our pessimistic consistency loss $\mathcal{L}^{p}$ for one pixel $x_{us}$ (i.e. the $s$-th pixels of the $u$-th unlabeled image) could be converted to:
\begin{equation}
  \begin{aligned}
  \mathcal{L}^{p}(x_{us})=\mathcal{L}_{us}^{p} = \log(1+\sum_{i \in \mathbb{Y}_{us}} e^{-z_{us}^{i}} \times \sum_{j \notin \mathbb{Y}_{us}} e^{z_{us}^{j}}).
\end{aligned} \label{eq:topk consistency loss}
\end{equation}

Next, we analyze the behavior of $\mathcal{L}_{us}^{p}$ in backpropagation.
For simplicity, we denote the categories that belong to $\mathbb{Y}_{us}$ as positive categories, and the categories that do not belong to $\mathbb{Y}_{us}$ as negative categories.
In backpropagation, we compute the gradient of $\mathcal{L}_{us}^{p}$ with respect to the output $\bm{z}_{us}$ of our model:
\begin{equation}
  \begin{aligned}
    &\frac{\partial \mathcal{L}_{us}^{p}}{\partial z_{us}^{i}} = \frac{-\sum_{j \notin \mathbb{Y}_{us}}{e^{z_{us}^{j}}} \times e^{-z_{us}^{i}}}{1+\sum_{j \notin \mathbb{Y}_{us}}{e^{z_{us}^{j}}} \times \sum_{i \in \mathbb{Y}_{us}}{e^{-z_{us}^{i}}}},~~i\in \mathbb{Y}_{us}\\
    &\frac{\partial \mathcal{L}_{us}^{p}}{\partial z_{us}^{j}} = \frac{\sum_{i \in \mathbb{Y}_{us}}{e^{-z_{us}^{i}}} \times e^{z_{us}^{j}}}{1+\sum_{j \notin \mathbb{Y}_{us}}{e^{z_{us}^{j}}} \times \sum_{i \in \mathbb{Y}_{us}}{e^{-z_{us}^{i}}}},~~j\notin \mathbb{Y}_{us},
  \end{aligned} \label{eq:topk_gradient}
\end{equation}
where the $\frac{\partial \mathcal{L}_{us}^{p}}{\partial z_{us}^{i}}$ and $\frac{\partial \mathcal{L}_{us}^{p}}{\partial z_{us}^{j}}$ denote the derivatives with respect to outputs for positive categories and negative categories, respectively.
From Eq.~\ref{eq:topk_gradient}, we see that our $\mathcal{L}_{us}^{p}$ has following characteristics:

(1). The output for the GT category increases when it appears in $\mathbb{Y}_{us}$.
This is because outputs for positive categories have negative gradients and are optimized to increase by gradient descent.

(2). The existing $\mathcal{L}_{us}^{o}$ is a special case of our $\mathcal{L}_{us}^{p}$ when we set $K=1$, as shown in Eq.~\ref{eq:special case}.
\begin{equation}
  \begin{aligned}
    \mathcal{L}_{us}^{o} = -\log \frac{e^{z_{us}^{i}}}{e^{z_{us}^{i}}+\sum_{j \neq i}e^{z_{us}^{j}}} = \log(1+e^{-z_{us}^{i}} \times \sum_{j \neq i}e^{z_{us}^{j}}),
  \end{aligned} \label{eq:special case}
\end{equation}
where $i$ is the index of top-1 predicted pseudo label.

(3). The gradients of $\mathcal{L}_{us}^{p}$ are balanced, which is reflected in that the absolute value of the sum on positive gradients $|\sum_{i\in \mathbb{Y}_{us}} \frac{\partial \mathcal{L}_{us}^{p}}{\partial z_{us}^{i}}|$ is equal to the sum on negative gradients $\sum_{j \notin \mathbb{Y}_{us}} \frac{\partial \mathcal{L}_{us}^{p}}{\partial z_{us}^{j}}$, as Eq.~\ref{eq:pos_neg_gradient}:
\begin{equation}
  \begin{aligned}
    &|\sum_{i\in \mathbb{Y}_{us}} \frac{\partial \mathcal{L}_{us}^{p}}{\partial z_{us}^{i}}| = \sum_{j \notin \mathbb{Y}_{us}} \frac{\partial \mathcal{L}_{us}^{p}}{\partial z_{us}^{j}}\\
    &= \frac{\sum_{j \notin \mathbb{Y}_{us}}{e^{z_{us}^{j}}} \times \sum_{i \in \mathbb{Y}_{us}}e^{-z_{us}^{i}}}{1+\sum_{j \notin \mathbb{Y}_{us}}{e^{z_{us}^{j}}} \times \sum_{i \in \mathbb{Y}_{us}}{e^{-z_{us}^{i}}}}.
  \end{aligned} \label{eq:pos_neg_gradient}
\end{equation}

\subsection{Candidate Label Proposal}\label{sec:candidate label proposal}
In this section, we introduce how we adaptively provide the candidate label proposals for each pixel.
Note that the number of proposals is important since too many labels will make our model predict multiple categories for one pixel, while too few labels (i.e. $K=1$) will make our model degenerate into the existing optimistic method.

We first propose to use the categories with top-K predicted probabilities as candidate labels since high-confidence predictions are prone to be correct~\cite{berthelot2019mixmatch}.
We then design an easy but effective K value selection strategy to adaptively determine the K value for each pixel, as shown in Algorithm~\ref{alg:K value selection strategy}.
In particular, we set a hyperparameter $T$ which represents
the upper bound of cumulative probability.
For one pixel, we then compute the cumulative probability of its
top-n predictions and record the value of $n$ where the cumulative probability exceeds $T$ for the first time.
Finally, the K value for this pixel is set as $\max(n-1,1)$.

\begin{algorithm}[tb]
   \caption{K value selection strategy}
   \label{alg:K value selection strategy}
\begin{algorithmic}
    \STATE \textbf{Input:} sorted prediction $\textbf{p}=(p^{1},p^{2},...,p^{C})$
    \STATE \textbf{Output:} K value
    \STATE \textbf{Initialize:} cumulative probability upper bound $T$, category numbers $C$, cumulative probability vector  $\textbf{V}=\textbf{p}$

    \STATE \textbf{Compute cumulative probability:} \\
    \FOR{$n=1$ \textbf{to} $C$}
        \IF{$V^{n} > T$ \textbf{or} $n = C$}
        \STATE return $n$
        \ENDIF
    \STATE $V^{n+1} = V^{n}+p^{n+1}$
    \ENDFOR
   \STATE \textbf{Determine K value:}\\
   \STATE $K=\max(n-1,1)$
   \STATE \textbf{Return} K
\end{algorithmic}
\end{algorithm}

Selecting the top-n predictions whose cumulative probability exceeds $T$ guarantees that the GT category has a high probability of being selected.

An counter-intuitive design in our Algorithm~\ref{alg:K value selection strategy} is that we choose $K=n-1$ instead of $K=n$.
This is because setting $K=n-1$ alleviates the problem of gradient vanishing in training.
To explain this, we convert the gradients of $\mathcal{L}_{us}^{p}$ in Eq.~\ref{eq:topk_gradient} to probabilistic form:
\begin{equation}
\begin{aligned}
  &\frac{\partial \mathcal{L}_{us}^{p}}{\partial z_{us}^{i}} = \frac{-\sum_{j \notin \mathbb{Y}_{us}}p_{us}^{j}}{1+\sum_{j \notin \mathbb{Y}_{us}}p_{us}^{j} \times \sum_{i \in \mathbb{Y}_{us}}{\frac{1}{p_{us}^{i}}}} \times \frac{1}{p_{us}^{i}}\\
  &\frac{\partial \mathcal{L}_{us}^{p}}{\partial z_{us}^{j}} = \frac{\sum_{i \in \mathbb{Y}_{us}}\frac{1}{p_{us}^{i}}}{1+\sum_{j \notin \mathbb{Y}_{us}}p_{us}^{j} \times \sum_{i \in \mathbb{Y}_{us}}{\frac{1}{p_{us}^{i}}}} \times p_{us}^{j}.
\end{aligned} \label{eq:topk_gradient_in_p_pos}
\end{equation}
Here we only need to analyze the gradients of positive categories, because characteristic (3) in Eq.~\ref{eq:pos_neg_gradient} shows that the absolute value of the gradient sum on the positive and negative categories are equal.
From Eq.~\ref{eq:topk_gradient_in_p_pos}, we see that the $\frac{\partial \mathcal{L}_{us}^{p}}{\partial z_{us}^{i}}$ is close to 0 when its numerator (i.e. $\sum_{j \notin \mathbb{Y}_{us}}p_{us}^{j}$) is close to 0.
If we choose $K_{us}=n$, then the range of the cumulative probability sum $\sum_{i \in \mathbb{Y}_{us}}p_{us}^{i}$ is $(T,1)$, correspondingly, the range of $\sum_{j \notin \mathbb{Y}_{us}}p_{us}^{j}$ will be $(0,1-T)$.
This means that it is possible for $\sum_{j \notin \mathbb{Y}_{us}}p_{us}^{j}$ to approach 0 causing the problem of gradient vanishing.
When setting $K_{us}=n-1$, we derive $\sum_{j \notin \mathbb{Y}_{us}}p_{us}^{j}>1-T$, which provides a lower bound for the numerator of $\frac{\partial \mathcal{L}_{us}^{p}}{\partial z_{us}^{i}}$.
Hence, we alleviate the problem of gradient vanishing.

\subsection{Adaptive weight for each pixel}\label{sec:adaptive weight}
Our PCR is implemented based on the assumption that the GT category exists in the candidate label set $\mathbb{Y}_{us}$.
Here we propose to integrate the confidence of our assumption into the training of our method.
When our assumption is not tenable, the GT label will appear in the negative categories of which the largest predicted probability is $\underset{j \notin \mathbb{Y}_{us}} \max(p_{us}^{j})$.
Hence, the $\underset{j \notin \mathbb{Y}_{us}} \max(p_{us}^{j})$ could reflect the confidence of our assumption.
Specifically, $\underset{j \notin \mathbb{Y}_{us}} \max(p_{us}^{j})$ is negatively correlated with assumption confidence since high $\underset{j \notin \mathbb{Y}_{us}} \max(p_{us}^{j})$ means that GT label has a high probability outside $\mathbb{Y}_{us}$, and vice versa.

Formulately, the range of $\underset{j \notin \mathbb{Y}_{us}} \max(p_{us}^{j})$ is derived as:

\begin{equation}
  \begin{aligned}
    \frac{1-T}{C-K_{us}}<\underset{j \notin \mathbb{Y}_{us}} \max(p_{us}^{j}) < \frac{\sum_{i \in \mathbb{Y}_{us}}{p_{us}^{i}}}{K_{us}}.
  \end{aligned} \label{eq:constraint2}
\end{equation}
In practice, $T$ is close to 1 (e.g. 0.9), thus $\frac{1-T}{C-K_{us}}$ is close to 0.
For simplicity, we obtain the approximate range of $\underset{j \notin \mathbb{Y}_{us}} \max(p_{us}^{j})$ as $(0, \frac{\sum_{i \in \mathbb{Y}_{us}}{p_{us}^{i}}}{K_{us}})$.
We then define our adaptive weight as a monotonically decreasing concave function as:
\begin{equation}
  \begin{aligned}
    w_{us} = \frac{\log{[1+A \times (\frac{\sum_{i \in \mathbb{Y}_{us}}{p_{us}^{i}}}{K_{us}}-\underset{j \notin \mathbb{Y}_{us}} \max(p_{us}^{j}))}]}{\log{[1+A \times (\frac{\sum_{i \in \mathbb{Y}_{us}}{p_{us}^{i}}}{K_{us}})]}},
  \end{aligned} \label{eq:weight}
\end{equation}
where $A$ is a scalar used to control the radian of this function, which is fixed as 50 in our experiments.
It is worth noting that our adaptive weight is different from the weights computed by top-1 confidence used to filter out low-confidence pixels~\cite{french2019semi,ouali2020semi,ke2020guided}.
Those weights are small for pixels with low top-1 probability, which results in those pixels not being sufficiently used in training~\cite{wang2022semi}.
But our weight is only small when the prediction of a pixel is confused in the top-(K+1) categories, thus our model still uses the information that its prediction should not belong to the other C-K-1 categories.

\subsection{Overall training}\label{sec:overall training}
As discussed above, our unsupervised loss is the weighted pessimistic consistency loss, as follows:
\begin{equation}
  \begin{aligned}
  \mathcal{L}_{uns} = \frac{1}{|U||S|}\sum_{u=1}^{U}\sum_{s=1}^{S}  w_{us} \times \mathcal{L}_{us}^{p},
\end{aligned} \label{eq:weighted topk consistency loss}
\end{equation}
where the $w_{us}$ is the adaptive weight described in Section~\ref{sec:adaptive weight}.
For labeled pixels, our goal is to minimize the standard cross-entropy loss, which is the same as existing works~\cite{tarvainen2017mean,ouali2020semi,french2019semi,ke2020guided,tu2022guidedmix,chen2021semi,hu2021semi}.
The only optimization object of our method is to minimize the `supervised loss + pessimistic consistency loss', as follows:
\begin{equation}
  \begin{aligned}
    \mathcal{L} = \mathcal{L}_{sup} + \beta \mathcal{L}_{uns},~
    \mathcal{L}_{sup} = \frac{1}{|L||S|}\sum_{l=1}^{L}\sum_{s=1}^{S}\mathcal{L}_{CE}(p_{ls},y_{ls})
  \end{aligned} \label{eq:optimization object}
\end{equation}
where $\mathcal{L}_{CE}$ is the cross-entropy loss function, $\beta$ is the regularization weight, $p_{ls}$ and $y_{ls}$ are the prediction and groundtruth of the $s$-th pixel in $l$-th labeled image.

\section{Why PCR works?}
In this section, we provide an analysis of why pessimistic consistency regularization could improve the learning of unlabeled data, especially for mispredicted pixels.

\subsection{The perspective of gradient ratio} \label{sec:gradient ratio}
In the SSL segmentation task, we always hope to increase the output for the GT category (named GT output in the following text) to provide a correct prediction.
But in practice, previous optimistic methods only increase the output for the pseudo label category and decrease the outputs for all other categories, as derived in Section~\ref{sec:motivation}.
For our PCR, we could only increase the outputs for positive categories (i.e. categories in the candidate label set) and decrease the outputs for the negative categories by optimizing our pessimistic consistency loss, as analyzed in Section~\ref{sec:pessimistic consistency loss}.
Therefore, we propose a \textit{gradient ratio} $R$ to measure how properly the GT output is optimized.
The gradient ratio for the $s$-th pixel in $u$-th unlabeled image is computed as:
\begin{equation}
  \begin{aligned}
  R_{us} = \frac{\partial \mathcal{L}_{us}}{\partial z_{us}^{gt}} ~~/~~ \sum_{i \in Y_{us}} \frac{\partial \mathcal{L}_{us}}{\partial z_{us}^{i}},
  \end{aligned} \label{eq:ce_gradient}
\end{equation}
where the $Y_{us}$ represents the candidate label set $\mathbb{Y}_{us}$ when $\mathcal{L}_{us}$ is $\mathcal{L}_{us}^{p}$, and $Y_{us}$ represents the pseudo label when $\mathcal{L}_{us}$ is $\mathcal{L}_{us}^{o}$.
The gradient ratio $R_{us}$ is the ratio of the gradient for the GT category to the sum of the gradients for the positive categories.
It ranges from [-1,1] and a positive $R_{us}$ means the GT output is optimized to increase, while a negative $R_{us}$ means the GT output is incorrectly optimized to decrease.
Based on the prediction of each pixel, we consider $R_{us}$ in three cases:

\textbf{Case 1}. The pseudo label is correct, that is, the GT category is the top-1 prediction.
In this case, the gradient ratio $R_{us}$ computed by $\mathcal{L}_{us}^{o}$ and $\mathcal{L}_{us}^{p}$ are:
\begin{equation}
  \begin{aligned}
    R_{us}^{o} = \frac{p_{us}^{gt}-1}{p_{us}^{pse}-1}=1,~~R_{us}^{p} = \frac{e^{-z_{us}^{gt}}}{\sum_{i \in \mathbb{Y}_{us}} e^{-z_{us}^{i}}} \in [0,1],
  \end{aligned} \label{eq:case1_score_ratio}
\end{equation}
where $p_{us}^{gt}$ and $p_{us}^{pse}$ are the predicted probability for GT category and pseudo label category.
We see that $R_{us}^{p}$ and $R_{us}^{o}$ are both greater than 0.
This means they both encourage the GT output to increase in this case.

\textbf{Case 2}. The top-1 prediction is wrong, but the GT category is in the categories with top-K probabilities, where K is computed by our K value selection strategy in Algorithm~\ref{alg:K value selection strategy}.
That is, the pseudo label is wrong but the GT label is in our candidate label set $\mathbb{Y}_{us}$.
For case 2, the gradient ratio $R_{us}^{o}$ and $R_{us}^{p}$ are computed as:
\begin{equation}
  \begin{aligned}
    R_{us}^{o} = \frac{p_{us}^{gt}}{p_{us}^{pse}-1} \in [-1,0],~~R_{us}^{p} = \frac{e^{-z_{us}^{gt}}}{\sum_{i \in \mathbb{Y}_{us}} e^{-z_{us}^{i}}} \in [0,1].
  \end{aligned} \label{eq:case2_score_ratio}
\end{equation}
We see that $R_{us}^{p}$ is larger than 0 while $R_{us}^{o}$ is less than 0.
This means that $\mathcal{L}_{us}^{o}$ erroneously reduces GT output, but our $\mathcal{L}_{us}^{p}$ increases GT output, which indicates that $\mathcal{L}_{us}^{p}$ has a great advantage over $\mathcal{L}_{us}^{o}$ in this case.

\textbf{Case 3}. The pseudo label is wrong, and the GT category is outside the candidate label set $\mathbb{Y}_{us}$.
In this case, the gradient ratio $R^{o}_{us}$ and $R^{p}_{us}$ are:
\begin{equation}
  \begin{aligned}
    R_{us}^{o} = \frac{p_{us}^{gt}}{p_{us}^{pse}-1} \in [-1,0],~~R_{p} = -\frac{e^{z_{us}^{gt}}}{\sum_{j \notin \mathbb{Y}_{us}} e^{z_{us}^{j}}} \in [-1,0].
  \end{aligned} \label{eq:case3_score_ratio}
\end{equation}
It is obvious that $R_{us}^{p}$ and $R_{us}^{o}$ are both less than 0.
This means that neither $\mathcal{L}_{us}^{o}$ nor $\mathcal{L}_{us}^{p}$ is beneficial for training the model to predict the GT category in this case.
We plot the gradient ratio $R$ for pixels in these three cases with our experiments on VOC2012 with 1/8 labeled data using the CPS~\cite{chen2021semi} as the baseline.
As shown in Figure~\ref{fig:gradient_ratio}, $\mathcal{L}_{us}^{p}$ significantly outperforms the existing $\mathcal{L}_{us}^{o}$ in Case 2, and they perform similarly in Case 1 and Case 3.

\begin{figure}[tbp]
\centerline{\includegraphics[scale=0.32]{gradient_ratio.jpg}}
\caption{
The gradient ratio $R$.
The OCR here is the existing optimistic consistency regularization.
}
\label{fig:gradient_ratio}
\end{figure}

\subsection{The perspective of gradient similarity}
In Case 2 above, though $\mathcal{L}_{us}^{p}$ encourages the output for the GT category to increase which is better than $\mathcal{L}_{us}^{o}$, it also encourages the outputs for other positive categories to become larger.
Ideally, the cross-entropy loss using the unavailable GT label only increases the GT output and decreases the outputs for all other categories.
We name the gradient computed using the unavailable GT label with cross-entropy loss as the ideal gradient $\bm{G^{ide}}$.

Here, we propose to use the cosine similarity between the ideal gradient vector $\bm{G^{ide}}$ and pessimistic gradient vector $\bm{G^{p}}$ brought by $\mathcal{L}_{us}^{p}$ to further analyze our PCR in Case 2.
If the cosine similarity is greater than 0, it means the projection of $\bm{G^{p}}$ on $\bm{G^{ide}}$ is positive, which indicates $\bm{G^{p}}$ is beneficial to our model since it makes our model go further in the ideal direction.
For comparison, we also calculated the cosine similarity between the gradient vector of the existing optimistic method $\bm{G^{o}}$ and the ideal gradient $\bm{G^{ide}}$.

Based on Eq.~\ref{eq:gradient of top1 consistency loss} and Eq.~\ref{eq:topk_gradient_in_p_pos}, we then compute the three gradient vectors $\bm{G^{o}}$, $\bm{G^{p}}$ and $\bm{G^{ide}}$ as:
\begin{equation}
\begin{aligned}
  \bm{G^{ide}} &=  (p^{1},p^{2},...,p^{gt}-1,p^{K},0,...,0)\\
  &+(0,...,0,p^{K+1},...,p^{C}) = \bm{G^{ide}_{+}}+\bm{G^{ide}_{-}}\\
  \bm{G^{o}} &=  (p^{1}-1,p^{2},...,p^{K},0,...,0)\\
  &+(0,...,0,p^{K+1},...,p^{C}) = \bm{G^{o}_{+}}+\bm{G^{o}_{-}}\\
  \bm{G^{p}} &= -C_{p} \cdot (\frac{1}{p^{1}},...,\frac{1}{p^{gt}},...,\frac{1}{p^{K}},0,...,0)\\
  &+C_{n} \cdot (0,...,0,p^{K+1},...,p^{C}) = \bm{G^{p}_{+}}+\bm{G^{p}_{-}},
\end{aligned} \label{eq:vector_topk}
\end{equation}
where $C_{p}$ and $C_{n}$ are the first terms of the two expressions in Eq.~\ref{eq:topk_gradient_in_p_pos}.
The $\bm{G^{ide}_{+}}$, $\bm{G^{o}_{+}}$ and $\bm{G^{p}_{+}}$ are gradients for positive categories, while $\bm{G^{ide}_{-}}$, $\bm{G^{o}_{-}}$ and $\bm{G^{p}_{-}}$ are gradients for negative categories.
Due to the complexity of predicted probability, the relationship between the cosine similarity $sim (\bm{G^{p}}, \bm{G^{ide}}) = \frac{\bm{G^{p}} \cdot \bm{G^{ide}}}{|\bm{G^{p}}| |\bm{G^{ide}}|}$ and 0 is not mathematically absolute.
Hence we compute $sim (\bm{G^{p}}, \bm{G^{ide}})$ and $sim (\bm{G^{o}}, \bm{G^{ide}})$ quantitatively in Fig~\ref{fig:analysis_cos_sim} (a).
We additionally present $sim (\bm{G^{p}_{+}}, \bm{G^{ide}_{+}})$ and $sim (\bm{G^{o}_{+}}, \bm{G^{ide}_{+}})$ in Fig~\ref{fig:analysis_cos_sim} (b) since the $\bm{G^{ide}_{-}}$, $\bm{G^{o}_{-}}$ and $\bm{G^{p}_{-}}$ are collinear, thus only the difference between $\bm{G^{ide}_{+}}$, $\bm{G^{o}_{+}}$ and $\bm{G^{p}_{+}}$ matters training.

As shown in Fig.~\ref{fig:analysis_cos_sim} (a), we first observe that the positive rates of $sim (\bm{G^{p}}, \bm{G^{ide}})$ are more than 90\% in all minibatchs, which indicates that $\bm{G^{p}}$ makes our model go further in the ideal direction in most minibatchs.
Second, we see that the $sim (\bm{G^{p}}, \bm{G^{ide}})$ is greater than the $sim (\bm{G^{o}}, \bm{G^{ide}})$, which means our pessimistic gradient $\bm{G^{p}}$ is closer to the ideal gradient $\bm{G^{ide}}$ than the gradient obtained by existing optimistic method $\bm{G^{o}}$.
Fig.~\ref{fig:analysis_cos_sim} (b) has a similar trend to Fig.~\ref{fig:analysis_cos_sim} (a) but lower values, because we remove the effect of collinear gradients $\bm{G^{ide}_{-}}$, $\bm{G^{p}_{-}}$ and $\bm{G^{o}_{-}}$.
These figures show that, in Case 2, PCR is beneficial (cosine similarly larger than 0) in most mini-batches and outperforms the existing optimistic method.

It is worth noting that $sim (\bm{G^{p}}, \bm{G^{ide}})$ only reflects that the angle between our gradient and the ideal gradient is a mostly acute angle.
But the norms of $\bm{G^{p}}$ and $\bm{G^{ide}}$ also affects optimization of our model.
If the norm of $\bm{G^{p}}$ is much larger than that of $\bm{G^{ide}}$, it will cause $\bm{G^{p}}$ over-optimize our model, hence even if their angle is small, it will also be detrimental to optimization.
We prove that the norms of $\bm{G^{p}}$ and $\bm{G^{ide}}$ are both range of $[0,\sqrt{2}]$ in Proof~\ref{sec:proof 2}.
In addition, we also count their norms in Figure~\ref{fig:norms}.
We see that the two norms are close and the norm of $\bm{G^{p}}$ is smaller than that of $\bm{G^{ide}}$, which means that our PCR won't bring the problem of over-optimization.

\begin{figure*}[htbp]
\vspace{-0.5em}
\centerline{\includegraphics[scale=0.29]{cos_sim.jpg}}
\caption{
(a) is the cosine similarity between ideal gradient $\bm{G^{ide}}$, pessimistic gradient $\bm{G^{p}}$, and optimistic gradient $\bm{G^{o}}$.
Also we present the positive rate of the similarity between $\bm{G^{ide}}$ and $\bm{G^{p}}$ computed on pixels in each minibatch.
(b) has a similar meaning to (a), but computes the similarity and positive rate only using the gradients for positive categories ($\bm{G^{ide}_{+}}$,$\bm{G^{p}_{+}}$,$\bm{G^{o}_{+}}$).
The lines in (a) and (b) represent the mean value and the shading represents the standard deviation.
(a) and (b) are all computed on VOC2012 with 1/8 labeled data using the CPS~\cite{chen2021semi} framework.
}
\label{fig:analysis_cos_sim}
\vspace{-1.0em}
\end{figure*}

\begin{figure}[htbp]

\includegraphics[scale=0.36]{grad_norm4.jpg}
\caption{
The norms of $\bm{G^{ide}}$ and $\bm{G^{p}}$ computed on VOC2012 with 1/8 labeled data using the CPS~\cite{chen2021semi} framework.
}\label{fig:norms}
\end{figure}

\begin{figure*}[htbp]
\centerline{\includegraphics[scale=0.4]{result_map.jpg}}
\caption{
The segmentation results obtained on the VOC2012 dataset with 1/16 labeled data.
For clarity, we show groundtruth (GT) in the form of instance label, and the predictions of CPS and CPS+PCR are presented in the form of semantic label.
}
\label{fig:result_map}
\end{figure*}

\section{Experiments}
\subsection{Implementation details}
\textbf{Frameworks and Dataset:}
We evaluate the effectiveness of our PCR on two SOTA frameworks CPS~\cite{chen2021semi} and AEL~\cite{hu2021semi}, and two data sets \textit{PASCAL VOC 2012} and \textit{Cityscapes}.
The CPS~\cite{chen2021semi} is an easy but effective SSL segmentation framework, which have been verified effective in training both with and without CutMix~\cite{yun2019cutmix} data augmentation.
The AEL~\cite{hu2021semi} is a strong framework which considers the pseudo-label imbalance problem in SSL segmentation.

Cityscapes is a large-scale data set designed for urban street scene segmentation which consists of 19 semantic classes containing 2,975 images for training, 500 for validation, and 1,525 for testing.
The PASCAL VOC 2012 is a generic object segmentation benchmark that consists of 20 object classes and 1 background class.
It is divided into training, validation, and test sets including 1,464, 1,449, and 1,456 images, respectively.
And there is also an augmented set~\cite{hariharan2011semantic} adding 10,582 images into the standard training set.
Following the setting of previous works~\cite{zou2020pseudoseg,chen2021semi}, we implement two splits on VOC2012: the standard split (with augmented set) and the low data split (without augmented set).

\textbf{Experimental Setting:}
Our experiments are implemented on the official code of CPS\footnote{https://github.com/charlesCXK/TorchSemiSeg.git} and AEL\footnote{https://github.com/hzhupku/SemiSeg-AEL.git} using Deeplab v3+ with pre-trained ResNet-101 as backbones.
Specifically, on Cityscapes using CPS as the baseline, we use SGD optimizer with a weight decay of 1e-4.
The initial learning rate is set to 0.02 and the momentum is fixed at 0.9.
We use the default ‘poly’ learning rate decay policy to scale the learning rate by $(1-iter/max~iter)^{0.9}$, and this policy is used in all our experiments.
The input images are cropped to $800 \times 800$ and we train our model for 160 epochs with a batchsize of 64.
The cumulative probability upperbound $T$ are set as 0.95 for models w/o cutmix and 0.9, 0.85, 0.85 for models w/ cutmix on the data splits of 1/32, 1/16, 1/8, respectively.
When using AEL as baseline, the batchsize, learning rate, epoch, and image size are changed to 16, 0.01, 150, and $769 \time 769$.
The cumulative probability upperbound $T$ are set as 0.9, 0.9, 0.85 on the data splits of 1/32, 1/16, 1/8, respectively.
On VOC2012 using CPS as the baseline, we use SGD optimizer with a weight decay of 1e-4.
The initial learning rate is set to 0.01 and the momentum is fixed at 0.9.
The input images are cropped to $512 \times 512$ and we train our model for 40 epochs with a batchsize of 32.
The cumulative probability upperbound $T$ are set as 0.95 for the model w/o cutmix on 1/16 data split, and 0.9 for all other models.
When using AEL as the baseline, the batchsize and epoch are changed to 16 and 50.
And $T$ are set as 0.95, 0.9, 0.9 on the data splits of 1/16, 1/8, 1/4, respectively.
On VOC2012 LowData, $T$ are set as 0.95, 0.85, 0.85, 0.85 on the data splits of 1/16, 1/8, 1/4 and 1/2 labeled data, respectively.
And other hyperparameters are the same as used on standard VOC2012.

\subsection{Quantitative results}
In our experiments, the PCR model is trained using the same hyperparameters as the baseline model, only replacing the unsupervised loss with our weighted pessimistic consistency loss.
The segmentation results on VOC2012, Cityscapes, and VOC2012 LowData are presented in Table~\ref{tab:voc standard results}, Table~\ref{tab:cityscapes results}, and Table~\ref{tab:voc lowdata results}, respectively.
We see that PCR improves the CPS baseline under both with and without CutMix settings, this indicates that the improvement brought by PCR and the improvement brought by data augmentation (i.e., CutMix) can be accumulated.
In addition, we see PCR is effective on various baselines, i.e., CPS and AEL, which means PCR is universal for various existing SSL frameworks.

\begin{table}[htbp]
  \setlength{\tabcolsep}{2.0mm}
  \centering
  \caption{\textbf{The mIoU on VOC2012.} The results marked by $\dag$ are reported in previous works~\cite{chen2021semi,lai2021semi,french2019semi}.}
  \label{tab:voc standard results}
\begin{tabular}{l|ccc}
\hline
Method             & 1/16       & 1/8        & 1/4        \\ \hline
MT$^{\dag}$~\cite{tarvainen2017mean}                 & 70.59      & 73.20      & 76.62      \\
CCT$^{\dag}$~\cite{ouali2020semi}                & 67.94      & 73.00      & 76.17      \\
CutMix-Seg$^{\dag}$~\cite{french2019semi}         & 72.56      & 72.69      & 74.25      \\
GCT$^{\dag}$~\cite{ke2020guided}                & 69.77      & 73.30      & 72.25      \\
GuidedMix-Net$^{\dag}$~\cite{tu2022guidedmix}      & -          & 73.40      & 75.50      \\
CAC$^{\dag}$~\cite{lai2021semi}                & 72.40      & 74.60      & 76.30      \\ \hline
CPS w/o cutmix~\cite{chen2021semi}     & 72.50      & 74.97      & 77.14      \\
CPS w/ cutmix~\cite{chen2021semi}      & 74.48      & 76.44      & 77.68      \\
AEL~\cite{hu2021semi}                & 74.20      & 76.58      & 77.98      \\ \hline
CPS+PCR w/o cutmix & 73.18(\textcolor{red}{+0.68}) & 75.74(\textcolor{red}{+0.77}) & 77.47(\textcolor{red}{+0.33}) \\
CPS+PCR w/ cutmix  & 74.98(\textcolor{red}{+0.50}) & \textbf{77.75}(\textcolor{red}{+1.31}) & 78.30(\textcolor{red}{+0.62}) \\
AEL+PCR            & \textbf{74.98}(\textcolor{red}{+0.78}) & 76.73(\textcolor{red}{+0.15}) & \textbf{78.35}(\textcolor{red}{+0.37}) \\ \hline
\end{tabular}
\end{table}

\begin{table}[htbp]
  \setlength{\tabcolsep}{2.0mm}
  \centering
  \caption{\textbf{The mIoU on Cityscapes.} The results marked by $\dag$ are reported in previous works~\cite{chen2021semi,lai2021semi,wang2022semi}.}
  \label{tab:cityscapes results}
\begin{tabular}{l|ccc}
\hline
Method             & 1/32         & 1/16         & 1/8          \\ \hline
MT$^{\dag}$~\cite{tarvainen2017mean}                 & -            & 68.08        & 73.71        \\
CCT$^{\dag}$~\cite{ouali2020semi}                & -            & 69.64        & 74.48        \\
GCT$^{\dag}$~\cite{ke2020guided}                & -            & 66.90        & 72.96        \\
U2PL$^{\dag}$~\cite{wang2022semi}               & -            & 74.90        & 76.48        \\ \hline
CPS w/o cutmix~\cite{chen2021semi}     & 59.70        & 71.22        & 74.98        \\
CPS w/ cutmix~\cite{chen2021semi}      & 72.51        & 74.72        & 77.62        \\
AEL~\cite{hu2021semi}                & 73.00        & 75.26        & 78.07        \\ \hline
CPS+PCR w/o cutmix & 61.00(\textcolor{red}{+1.30}) & 72.05(\textcolor{red}{+0.83}) & 75.67(\textcolor{red}{+0.69}) \\
CPS+PCR w/ cutmix  & 73.20(\textcolor{red}{+0.69}) & 75.01(\textcolor{red}{+0.29}) & \textbf{78.47}(\textcolor{red}{+0.85}) \\
AEL+PCR            & \textbf{75.01}(\textcolor{red}{+2.01}) & \textbf{76.58}(\textcolor{red}{+1.32}) & 78.19(\textcolor{red}{+0.12}) \\ \hline
\end{tabular}
\end{table}

\begin{table}[htbp]
  \setlength{\tabcolsep}{0.8mm}

  \caption{\textbf{The mIoU on VOC2012 LowData}. Results marked by $\dag$ are from~\cite{chen2021semi,zhong2021pixel,wang2022semi}. The `cm' is cutmix.}
  \label{tab:voc lowdata results}
\begin{tabular}{lcccc}
\hline
\multicolumn{5}{c}{VOC2012 LowData}                                                                      \\ \hline
\multicolumn{1}{l|}{Method}                        & 1/16         & 1/8          & 1/4          & 1/2          \\ \hline
\multicolumn{1}{l|}{AdvSemSeg$^{\dag}$~\cite{hung2018adversarial}}              & 39.69        & 47.58        & 59.97        & 65.27        \\
\multicolumn{1}{l|}{CCT$^{\dag}$~\cite{ouali2020semi}}              & 33.10        & 47.60        & 58.80        & 62.10        \\
\multicolumn{1}{l|}{VAT$^{\dag}$~\cite{miyato2018virtual}}              & 36.92        & 49.35        & 56.88        & 63.34        \\
\multicolumn{1}{l|}{MT$^{\dag}$~\cite{tarvainen2017mean}}              & 48.70        & 55.81        & 63.01        & 69.16        \\
\multicolumn{1}{l|}{GCT$^{\dag}$~\cite{ke2020guided}}              & 46.04        & 54.98        & 64.71        & 70.67        \\
\multicolumn{1}{l|}{CutMix$^{\dag}$-Seg~\cite{french2019semi}}              & 52.16        & 63.47        & 69.46        & 73.73        \\
\multicolumn{1}{l|}{PseusoSeg$^{\dag}$~\cite{zou2020pseudoseg}}               & 57.60        & 65.50        & 69.14        & 72.41        \\
\multicolumn{1}{l|}{PC$^{2}$Seg$^{\dag}$~\cite{zhong2021pixel}}                    & 57.00        & 66.28        & 69.78        & 73.05        \\
\multicolumn{1}{l|}{U2PL$^{\dag}$~\cite{wang2022semi}}                    & 67.98        & 69.15        & 73.66        & 76.16        \\ \hline
\multicolumn{1}{l|}{CPS w/ cm~\cite{chen2021semi}}           & 67.53        & 70.41        & 75.27        & 78.69        \\
\multicolumn{1}{l|}{CPS+PCR w/ cm}       & \textbf{69.30}(\textcolor{red}{+1.77}) & \textbf{71.72}(\textcolor{red}{+1.31}) & \textbf{75.73}(\textcolor{red}{+0.46}) & \textbf{78.95}(\textcolor{red}{+0.26}) \\ \hline
\end{tabular}
\end{table}

\subsection{Ablation Study}

\subsubsection{Adaptive Weight}
In section~\ref{sec:adaptive weight}, we propose an adaptive weight function to weigh the pessimistic loss of each pixel.
In our discussion in section~\ref{sec:adaptive weight}, we show that the adaptive weight function should be inversely proportional to $\underset{j \notin \mathbb{Y}_{u}} \max(\textbf{p}_{u}^{j})$.
This is because low $\underset{j \notin \mathbb{Y}_{u}} \max(\textbf{p}_{u}^{j})$ means the GT label has a high probability to exist in our candidate label set.
Here we provide an experiment showing that the used concave decreasing function performs better than linear or convex decreasing functions.
The function curves are illustrated in Figure~\ref{fig:adaptive_weight_function}, which are plotted in the setting of $T=0.95$, $K=2$, and cumulative probability $=T$.
And the formulas of convex and linear functions are expressed as:
\begin{equation}
  \begin{aligned}
    &w_{convex} = \frac{\frac{\sum_{i \in \mathbb{Y}_{us}}{p_{us}^{i}}}{K_{us}} - \underset{j \notin \mathbb{Y}_{us}} \max(p_{us}^{j})}{\frac{\sum_{i \in \mathbb{Y}_{us}}{p_{us}^{i}}}{K_{us}}+4*\underset{j \notin \mathbb{Y}_{us}} \max(p_{us}^{j})} \\
    &w_{linear} = \frac{\frac{\sum_{i \in \mathbb{Y}_{us}}{p_{us}^{i}}}{K_{us}} - \underset{j \notin \mathbb{Y}_{us}} \max(p_{us}^{j})}{\frac{\sum_{i \in \mathbb{Y}_{us}}{p_{us}^{i}}}{K_{us}}}.
  \end{aligned} \label{eq:other weight function}
\end{equation}
The segmentation performances are shown in Figure~\ref{fig:adaptive_weight_result}, which are obtained on VOC2012 with 1/8 labeled data using CPS+PCR w/ CutMix as the training method.
We think the superiority of the concave function comes from that, for small values of $\underset{j \notin \mathbb{Y}_{us}} \max(p_{us}^{j})$, concave function provides higher weight than convex and linear functions, demonstrating high utilization of high-confidence pixels.
\begin{figure}[htbp]
\centerline{\includegraphics[scale=0.54]{adaptive_weight_function.jpg}}
\caption{
Examples of convex, linear and concave decreasing functions.
These examples are plotted in the setting of $T=0.95$, $K=2$, and cumulative probability $=T$.
}
\label{fig:adaptive_weight_function}
\end{figure}

\begin{figure}[htbp]
\centerline{\includegraphics[scale=0.48]{adaptive_weight.jpg}}
\caption{
Performance of our CPS+PCR w/ CutMix model using different adaptive weights.
The `baseline' represents the baseline CPS model.
}
\label{fig:adaptive_weight_result}
\end{figure}

\subsubsection{The hyperparameter $T$}
The $T$ is a key hyperparameter in our method, which controls how pessimistic our PCR is.
Specifically, when $T$ is low, the cumulative probability is easy to exceed $T$, hence the K values for pixels are small.
This means that the degree of pessimism in PCR is low at this time, and it is close to the existing optimistic methods.
When $T$ is high, the cumulative probability is hard to exceed $T$, meaning the degree of pessimism in PCR is high.
Here we summarize two rules for setting a proper $T$ value.
First, a $T$ value around 0.9 (e.g. 0.85, 0.9, 0.95) is usually a promising setting.
Second, the value of $T$ is negatively correlated to the number of labeled data.

\textbf{The effect of $T$ on the training behaviors.}
In the training process, $T$ affects the number of candidate labels for each pixel, that is, the K value.
In addition, $T$ also affects the impurity of the candidate label set, which is defined as the proportion of pixels that do not contain the GT label in the candidate set to all pixels.
Statistically, we formulate the average $K$ value and the impurity as:
\begin{equation}
  \centering
  \begin{aligned}
    \overline{K} &= \frac{1}{U \times S} \times \sum_{u=1}^{U} \sum_{s=1}^{S} K_{us} \\
    impurity &= \frac{1}{U\times S} \times \sum_{u=1}^{U} \sum_{s=1}^{S} \mathbbm{1}(y_{us} \notin \mathbb{Y}_{us}),
  \end{aligned} \label{eq:avg K and purity}
\end{equation}
where $K_{us}$, $y_{us}$, and $\mathbb{Y}_{us}$ are the K value, GT label, and candidate label set for the $s$-th pixel of the $u$-th image.
The $U$ is the size of the unlabeled dataset, and $S$ is the number of pixels contained in each image.

In Table~\ref{tab:cumulative probability upperbound T}, we provide the average $K$ value and impurity in the first two columns, and we also provide the average $K$ value and impurity computed on pixels of $K>1$ in the last two columns.
All results in this section are implemented on Cityscapes using ResNet 50 as backbone
We see that small $T$ values lead to small K values, meaning the size of the candidate label set is small.
Accordingly, it causes high impurity of the candidate label set since a small candidate label set has a relatively large possibility of missing the GT label.
High impurity brings noise to the learning process, which is known as confirmation bias~\cite{arazo2020pseudo}.
In contrast, using a large value of $T$ builds a large candidate label set, effectively reducing the impurity.
However, too large $T$ value (e.g. 0.99) makes our model learn from multiple labels, which is also not suitable for a single-label classification task.
In Table~\ref{tab:cumulative probability upperbound T mIoU}, we present the mIoU of our PCR models trained with various $T$ values.
Given our observation on the trade-off between the impurity and the size of the candidate label set, we find a $T$ value around 0.9 always provides promising results.
In our experiments, the $T$ value is set from \{0.85, 0.9, 0.95\}.
\begin{table}[bhtp]
\setlength{\tabcolsep}{3.5mm}
\centering
\caption{\textbf{The ablation study about our cumulative probability upperbound $T$.} The results are obtained on VOC2012 with 1/16 labeled data trained by CPS+PCR (ResNet 50). The subscript `$>1$' means the statistics are only computed on pixels of $K>1$.
\label{tab:cumulative probability upperbound T}}
\begin{tabular}{l|cccc}
\hline
$T$ value    & $\overline{K}$ & Impurity & $\overline{K}_{>1}$ & Impurity$_{>1}$ \\ \hline
0.5  & 1.0005           & 0.2210    & 2.0258       & 0.6250 \\
0.75 & 1.0179           & 0.2181    & 2.1940       & 0.4829 \\
0.85 & 1.0499           & 0.2134    & 2.3167       & 0.3985 \\
0.9  & 1.0974           & 0.2058    & 2.4166       & 0.3332 \\
0.95 & 1.1932           & 0.1878    & 2.5755       & 0.2638 \\
0.99 & 1.4959           & 0.1757    & 2.9208       & 0.1561 \\ \hline
\end{tabular}
\end{table}
\begin{table}[bhtp]
\setlength{\tabcolsep}{3.0mm}
\centering
\caption{\textbf{The performances of CPS+PCR models trained with various $T$ }\label{tab:cumulative probability upperbound T mIoU}}
\begin{tabular}{l|cccccc}
\hline
T value & 0.5   & 0.75  & 0.85  & 0.9   & 0.95  & 0.99  \\ \hline
mIoU    & 68.80 & 68.97 & \textcolor{red}{69.34} & \textcolor{red}{\textbf{69.71}} & \textcolor{red}{69.08} & 67.52 \\ \hline
\end{tabular}
\end{table}
\begin{table}[htbp]
\setlength{\tabcolsep}{4.0mm}
\centering
\caption{\textbf{The relationship between cumulative probability upperbound $T$ and the amount of labeled data.} The results are obtained on Cityscapes using CPS as baseline.\label{tab:cumulative probability upperbound labeled amount}}
\begin{tabular}{l|ccc}
\hline
T    & 1/32          & 1/16          & 1/8           \\ \hline
base & 54.40 & 68.68 & 73.06 \\
0.85 & 55.22 (\textcolor{red}{+0.82}) & 69.34 (\textcolor{red}{+0.66}) & 74.37 (\textcolor{red}{+1.31}) \\
0.9  & 55.40 (\textcolor{red}{+1.00}) & 69.71 (\textbf{\textcolor{red}{+1.03}}) & 74.43 (\textbf{\textcolor{red}{+1.37}}) \\
0.95 & 55.77 (\textbf{\textcolor{red}{+1.37}}) & 69.08 (\textcolor{red}{+0.40}) & 74.03 (\textcolor{red}{+0.97}) \\ \hline
\end{tabular}
\end{table}

\textbf{The relationship between $T$ and the amount of labeled data.}
As the number of labeled data increases, the difficulty of the semi-supervised segmentation task decreases.
We find a high $T$ usually obtains good performance when labeled data are limited, while a low $T$ usually performs better when labeled data are sufficient.
As shown in Table~\ref{tab:cumulative probability upperbound labeled amount}, in the 1/32 labeled data setting, $T=0.95$ obtains the highest improvement about 1.37\%, while $T=0.85$ and $T=0.9$ only obtain improvements about 1\%.
In the 1/16 labeled data setting, $T=0.9$ obtains the best performance which improves baseline by 1.03\%, and the other two $T$ values improve baseline by about 0.5\%.
In the 1/8 labeled data setting, $T=0.9$ and $T=0.85$ obtains close performances which improve baseline by 1.3\%, while $T=0.95$ performs not as good as the previous two $T$ settings.
These empirical results show that setting the $T$ value negatively corresponding to the amount of labeled data in PCR could obtain promising performances.

\subsection{K Values in Training}
We record the number of pixels with different $K$ values during the training process in Figure~\ref{fig:k num pixel}.
We see that the K values of most pixels are 1.
During training, the number of pixels with $K > 1$ decreases, and the number of pixels with $K = 1$ increases.
This shows that with training, our K value selection strategy provides K value of 1 for most pixels and $K>1$ for a few uncertain pixels.
At the late stage of training, the K values for more than 93.75\% (i.e. 600000~/~640000) pixels are 1,
which means our model output low-entropy predictions in the late stage of training.

\begin{figure}[tbp]
\centerline{\includegraphics[scale=0.21]{k_nums_v2.jpg}}
\caption{
This figure is plotted on the Cityscapes with 1/32 labeled data using CPS+PCR w/ CutMix as training method. The input size is 800 × 800 which means there are 640000 pixels in total.
}
\label{fig:k num pixel}
\end{figure}

In addition, we also illustrate the K value map of some images during training in Figure~\ref{fig:k map half}.
We see that the K values of most pixels in the background are 1 since background pixels are usually easy to classify.
In the early stage of training, the pixels with $K > 1$ are mainly located on objects, since the classification of objects for our model is uncertain at early training.
As the training progresses, the number of pixels with $K > 1$ gradually decreases and these pixels are mainly distributed at the boundary of objects.
This is because our model has certain predictions for most pixels in the later stage of training.
But for pixels located at the object boundary, their categories are fuzzy, for which our model makes uncertain predictions for them.
Our PCR provides multiple candidate labels (i.e. $K>1$) for these uncertain pixels to learn, which is in line with their fuzzy property.
From this figure, we find that the experimental behavior of K value is consistent with the design of our Algorithm~\ref{alg:K value selection strategy}, that is, PCR provides small K values for certainly predicted pixels and provides large K values for uncertainly predicted pixels.

\begin{figure*}[htbp]
\centerline{\includegraphics[scale=0.4]{k_map_2.jpg}}
\caption{
The visualization of K values.
This figure is plotted on the VOC2012 with 1/16 labeled data using CPS+PCR w/ CutMix as training method.
}
\label{fig:k map half}
\end{figure*}

\begin{table}[htbp]
  \setlength{\tabcolsep}{5mm}
  \caption{\textbf{Seconds per epoch.} These statistics are measured using 8 Tesla V100 GPUs under the 1/8 labeled data setting.}
  \centering
\begin{tabular}{l|cc}
\hline
Method  & Cityscapes & VOC2012  \\ \hline
AEL~\cite{hu2021semi}     & 730s              & 835s         \\
AEL+PCR & 820s             & 985s           \\ \hline
\end{tabular}\label{tab:time limitation}
\end{table}

\section{Limitations}
Though PCR works well, it has the limitation of high time complexity.
PCR alleviates the errors in wrong pseudo labels by letting the model learn the possible GT category that appears in the candidate label set, which requires assigning a K value to each pixel.
This leads to high time complexity for pessimistic consistency loss.

From Eq.~\ref{eq:topk consistency loss}, we see that the time complexity of computing $\mathcal{L}_{p}$ is $O(C)$ when the $\mathbb{Y}_{u}$ is determined, where $C$ is the number of classes.
For original $\mathcal{L}_{o}$, it is a special case of $\mathcal{L}_{p}$ when the $K$ is fixed to 1, hence the time complexity of original $\mathcal{L}_{o}$ for one pixel is $O(C)$.
When it comes to $\mathcal{L}_{p}$, we additionally need to decide the K value for each pixel of which the time complexity is $O(K)$ since it needs K times additions and K times comparisons.
Hence, the time complexity of computing $\mathcal{L}_{p}$ is $O(KC)$ which is K times of computing the original $\mathcal{L}_{o}$.
We also quantitatively provide the time of training our PCR in practice.
As shown in Table~\ref{tab:time limitation}, PCR brings about 10\% additional training cost.

\section{Conclusion}
In this paper, we propose a PCR that learns the unlabeled data in a pessimistic case where the pseudo label is not always correct.
It provides K candidate label proposals for each sample to learn the possible GT in them and could be easily integrated with existing SSL methods.
Theoretical analysis and experiments show that PCR effectively outperforms the existing optimistic methods especially when the pseudo label is wrong but the GT category exists in our candidate label set.
There are still some unexplored problems in PCR, e.g., ``a more effective pessimistic consistency loss function" and ``a better candidate label-proposal method to reduce the number of samples in Case 3."

{
\appendices

\section{The proof that the norms of $G_{ide}$ and $G_{p}$ are both range of [0,$\sqrt{2}$].}\label{sec:proof 2}
To provide this, we need to draw on two other conclusions.
First, the absolute value of the sum on gradients for positive categories $|\sum_{i\in \mathbb{Y}_{us}} \frac{\partial \mathcal{L}_{us}^{p}}{\partial z_{us}^{i}}|$ is equal to the sum on negative gradients $\sum_{j \notin \mathbb{Y}_{us}} \frac{\partial \mathcal{L}_{us}^{p}}{\partial z_{us}^{j}}$, which holds for both $\mathcal{L}_{us}^{p}$ and $\mathcal{L}_{us}^{o}$, as shown in Eq.~\ref{eq:pos_neg_gradient}.
Second, the sum on negative gradients $\sum_{j \notin \mathbb{Y}_{us}} \frac{\partial \mathcal{L}_{us}^{p}}{\partial z_{us}^{j}}$ is less than 1, which has also been shown in Eq.~\ref{eq:pos_neg_gradient} since the denominator is always 1 greater than the numerator.
With the above two conclusions, we compute the norms of $\bm{G^{ide}}$ and $\bm{G^{p}}$ in Eq.~\ref{eq:norms_ide} and Eq.~\ref{eq:norms_p}:
\begin{equation}
  \begin{aligned}
    |N^{ide}| &= \sqrt{(g^{1})^{2} + (g^{2})^{2} + ... + (g^{C})^{2}}\\
    & = \sqrt{(g^{y})^{2}+\sum_{i \neq y}(g^{i})^{2}}\\
    &= \sqrt{(\sum_{i \neq y}g^{i})^{2} + \sum_{i \neq y}(g^{i})^{2}} \\
    & \leq\sqrt{ 2 (\sum_{i \neq y}g^{i})^{2}} \leq \sqrt{2}
  \end{aligned} \label{eq:norms_ide}
\end{equation}
\begin{equation}
  \begin{aligned}
    |N^{p}| &= \sqrt{(g^{1})^{2} + (g^{2})^{2} + ... + (g^{C})^{2}}\\
    & = \sqrt{\sum_{i \in \mathbb{Y}} (g^{i})^{2}+\sum_{i \notin \mathbb{Y}}(g^{j})^{2}}\\
    &\leq \sqrt{(\sum_{i \in \mathbb{Y}} g^{i})^{2} + (\sum_{i \notin \mathbb{Y}}g^{j})^{2}}\\
    & = \sqrt{2 \times (\sum_{i \notin \mathbb{Y}}g^{j})^{2}} \leq \sqrt{2}.
  \end{aligned} \label{eq:norms_p}
\end{equation}

 }

\bibliographystyle{plain}
\small