Finite-round confidence-threshold pseudo-labeling

Let $q\ge 2$, let $\mathcal{C}=\{1,\dots ,q\}$, and let $(\mathcal{X},d)$ be a finite metric space, meaning $d:\mathcal{X}\times \mathcal{X}\to [0,\mathrm{\infty })$ is symmetric, $d(x,y)=0$ iff $x=y$, and $d(x,z)\le d(x,y)+d(y,z)$ for all $x,y,z$. The input is a nonempty ordered list $S_0=((x_i,y_i){)}_{i=1}^m$ of labeled examples with $y_i\in \mathcal{C}$, a finite ordered set $U_0\subseteq \mathcal{X}\setminus \{x_1,\dots ,x_m\}$ of unlabeled examples, an integer $k$ with $1\le k\le m$, a confidence threshold $\tau \in [1\mathrm{/}q,1]$, a pseudo-label weight $\lambda >0$, and a round cap $T\in {\mathbb{N}}_0$. A true labeled record has weight $1$; a pseudo-labeled record has weight $\lambda$.

Maintain an ordered training list $R_t$, initially $S_0$, a remaining unlabeled set $U_t$, initially $U_0$, and an initially empty pseudo-label log. To predict at $x\in U_t$, order all records $(x_i,y_i,w_i)\in R_t$ by increasing $(d(x,x_i),i)$, where $i$ is their stable record index, and take the first $k$ records $N_t(x)$. For $c\in \mathcal{C}$, put $V_{t,c}(x)={\sum }_{(x_i,y_i,w_i)\in N_t(x)}{w}_i\mathbf{1}\{y_i=c\}$. Let ${\widehat{y}}_t(x)$ be the smallest class index attaining ${\max }_c{V}_{t,c}(x)$, and define confidence ${\kappa }_t(x)={\max }_c{V}_{t,c}(x)\mathrm{/}{\sum }_c{V}_{t,c}(x)$. The denominator is positive because $k\ge 1$ and every record weight is positive.

If $U_0=\mathrm{\varnothing }$, set status $\mathtt{\text{no-unlabeled-inputs}}$ and skip the round loop. Otherwise, for rounds $t=0,\dots ,T-1$, compute all predictions from the same current list $R_t$. Let $A_t=\{x\in U_t:{\kappa }_t(x)\ge \tau \}$. If $A_t=\mathrm{\varnothing }$, set status $\mathtt{\text{no-additions}}$ and leave the loop. Otherwise append one pseudo-labeled record for each $x\in A_t$, in the supplied order on $U_0$, using its predicted class and weight $\lambda$; append $(t,x,{\widehat{y}}_t(x),\lambda )$ to the pseudo-label log, and remove all points in $A_t$ from $U_t$. A pseudo-label is never revised. If the updated $U_t=\mathrm{\varnothing }$, set status $\mathtt{\text{all-labelled}}$ and leave the loop. If all $T$ rounds finish without an earlier stop and points remain in $U_t$, set status $\mathtt{\text{round-cap}}$; this includes the case $T=0$.

For any query $x\in \mathcal{X}$, define the returned classifier by the same nearest-record ordering and weighted vote using the final training list, with the smallest-index vote tie rule. In every case return that classifier, the pseudo-label log, the remaining unlabeled set, and the status. The procedure makes no population-risk or pseudo-label-correctness guarantee.

Chapelle, Schölkopf, and Zien, Semi-Supervised Learning, Chapter 1 §1.3.2: iterative prediction-and-retraining context; the finite weighted k-nearest-neighbor procedure above is specified locally.