Semi-supervised graph propagation and pseudo-labeling limits

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.

Let $n\ge 1$ and let $M\in {\mathbb{R}}^{n\times n}$ be symmetric positive definite, meaning $x^{T}Mx>0$ for every nonzero $x\in {\mathbb{R}}^n$. Initialize $R$ as the zero $n\times n$ matrix. For $j=1,\dots ,n$ in order, set $p_j=M_{jj}-{\sum }_{k<j}{R}_{jk}^2,R_{jj}=\sqrt{p_j},$ and then, for $i=j+1,\dots ,n$ in order, set $R_{ij}=\frac{M_{ij}-{\sum }_{k<j}{R}_{ik}{R}_{jk}}{R_{jj}}\mathrm{.}$ Every pivot $p_j$ is positive, so the recurrence is well-defined and returns a lower-triangular matrix $R$ with positive diagonal satisfying $M=R{R}^T$.

Hermitian positive-definite matrices and Cholesky factorisation A = LL* with positive diagonal: over the real numbers, positive definiteness means $x^{T}Mx>0$ for every nonzero vector, and the Cholesky factor has the form $R{R}^T$ with $R$ lower triangular and positive diagonal.

Rank-nullity: ${\dim }_{F}V=\mathrm{nullity}T+\mathrm{rank}T$: a linear map with finite-dimensional domain satisfies dimension equals nullity plus rank; in particular, a square map with zero kernel is invertible.

David Bindel, CS 4220: Numerical Analysis, “Cholesky factorization”: complete block-recursion discussion; it leaves positivity of the Schur complement as an exercise, which the proof below supplies.

Tobin A. Driscoll and Richard J. Braun, Fundamentals of Numerical Computation, §2.9.3: symmetric positive-definite matrices, the positive-diagonal Cholesky factor, and the LDLᵀ square-root construction.

Let $n\ge 1$, $V=\{1,\dots ,n\}$, and let $W=(w_{ij})\in {\mathbb{R}}^{n\times n}$ be symmetric, entrywise nonnegative, and zero-diagonal. Put $d_i={\sum }_j{w}_{ij}$, $D=\mathrm{diag}(d_1,\dots ,d_n)$, and $L=D-W$. The support graph has edge $\{i,j\}$ exactly when $w_{ij}>0$; two vertices lie in the same connected component exactly when a finite path of support edges joins them; connected components include isolated singleton vertices. Let $B\subseteq V$ be nonempty, put $U=V\setminus B$, and prescribe $y_B\in {\mathbb{R}}^B$. Call the boundary anchored when every connected component meeting $U$ also meets $B$. For $f\in {\mathbb{R}}^V$ with $f{\mathrm{\mid }}_B=y_B$, define the Dirichlet graph energy $E(f)=\frac{1}{2}{f}^{T}Lf$. A function is harmonic on $U$ when $(Lf{)}_u=0$ for every $u\in U$. A graph-harmonic label extension is any minimizer of $E$ over the affine set of functions with the prescribed boundary values; the definition itself makes no uniqueness assertion.

Finite weighted graph Laplacian: fixes the degree matrix, combinatorial Laplacian, support edges, and isolated-component convention used above.

Zhu, Ghahramani, and Lafferty, Semi-Supervised Learning Using Gaussian Fields and Harmonic Functions, §2

Chapelle, Schölkopf, and Zien, Semi-Supervised Learning, Chapter 11

Let $\mathcal{X}$ be a finite nonempty feature set with its discrete sigma-algebra, and let $\mu :\mathcal{X}\to [0,1]$ satisfy ${\sum }_{x\in \mathcal{X}}\mu (x)=1$. Let $\mathcal{S}⊊\mathcal{X}$ be a nonempty set of observed labeled inputs, and choose $x_{\star }\in \mathcal{X}\setminus \mathcal{S}$ with $q=\mu (x_{\star })>0$. Let $h_0,h_1:\mathcal{X}\to \{0,1\}$ agree on $\mathcal{X}\setminus \{x_{\star }\}$ and differ at $x_{\star }$. For $j\in \{0,1\}$, let $P_j$ be the joint law assigning mass $\mu (x)$ to $(x,h_j(x))$. Both laws have the same feature marginal and the same observed labels on $\mathcal{S}$. Let $\mathcal{H}=\{g:\mathcal{X}\to \{0,1\}\}$, and let $Q:\mathcal{H}\to [0,1]$ satisfy ${\sum }_{g\in \mathcal{H}}Q(g)=1$, so it is a probability vector; take the same $Q$ under both laws, as a predictor rule using their common information must do. For the zero-one population risk $R_{P_j}(g)={\sum }_{x\in \mathcal{X}}\mu (x)\mathbf{1}\{g(x)\mathrm{\ne }{h}_j(x)\},$ the expected risks satisfy ${\max }_{j\in \{0,1\}}{\sum }_{g\in \mathcal{H}}Q(g)R_{P_j}(g)\ge \frac{q}{2}\mathrm{.}$

Supervised prediction problems: a prediction problem supplies a joint law, measurable predictors, and a measurable loss.

Population and empirical risk: population risk is the integral of the loss under the joint law; for these finite discrete laws it is the displayed finite sum.

Chapelle, Schölkopf, and Zien, Semi-Supervised Learning, Chapter 1 §§1.3.2–1.3.3

Let $n\ge 1$, $V=\{1,\dots ,n\}$, and let $W=(w_{ij})\in {\mathbb{R}}^{n\times n}$ be symmetric, entrywise nonnegative, and zero-diagonal. Put $d_i={\sum }_j{w}_{ij}$, $D=\mathrm{diag}(d_1,\dots ,d_n)$, and $L=D-W$. The support graph has edge $\{i,j\}$ exactly when $w_{ij}>0$. Two vertices lie in the same connected component exactly when a finite path of support edges joins them. Let $B\subseteq V$ be nonempty, $U=V\setminus B$, and prescribe $y_B\in {\mathbb{R}}^B$. For index sets $S,T\subseteq V$, let $L_{ST}$ denote the submatrix with rows in $S$ and columns in $T$, in increasing index order. Assume every support-graph component meeting $U$ also meets $B$. Then the energy $E(f)=\frac{1}{2}{f}^{T}Lf$, minimized over $f{\mathrm{\mid }}_B=y_B$, has exactly one minimizer. If $U=\mathrm{\varnothing }$, it is $f=y_B$. If $U\mathrm{\ne }\mathrm{\varnothing }$, the principal block $L_{UU}$ is real symmetric positive definite, meaning $v^T{L}_{UU}v>0$ for every nonzero $v\in {\mathbb{R}}^U$, and the minimizer is $f_U=-L_{UU}^{-1}{L}_{UB}{y}_B$. Each $u\in U$ has $d_u>0$ and $f_u={\sum }_j{w}_{uj}{f}_j\mathrm{/}{d}_u$; hence ${\min }_{b\in B}{y}_b\le f_u\le {\max }_{b\in B}{y}_b$. For $C\ge 2$, if each boundary value is one-hot (one coordinate equals 1 and all others equal 0) in ${\mathbb{R}}^C$, the coordinatewise energy minimizers have every row in the probability simplex ${\mathrm{\Delta }}_C=\{p\in [0,1{]}^C:{\sum }_{c=1}^C{p}_c=1\}$.

Zhu, Ghahramani, and Lafferty, Semi-Supervised Learning Using Gaussian Fields and Harmonic Functions, §2

Chapelle, Schölkopf, and Zien, Semi-Supervised Learning, Chapter 11 §§11.2–11.3

Inputs are $n\ge 1$, $V=\{1,\dots ,n\}$, a matrix $W\in {\mathbb{R}}^{n\times n}$, a nonempty labeled subset $B\subseteq V$, a boundary-label matrix $Y_B\in {\mathbb{R}}^{\mathrm{\mid }B\mathrm{\mid }\times r}$ with $r\ge 1$, an operation cap $K\in {\mathbb{N}}_0$ per label coordinate, and a residual tolerance $\epsilon \ge 0$. Use exact real arithmetic in the mathematical specification. Reject with status $\mathtt{\text{invalid-input}}$ unless $W$ is symmetric, entrywise nonnegative, and zero-diagonal. Set $U=V\setminus B$, $d_i={\sum }_j{w}_{ij}$, $D=\mathrm{diag}(d_1,\dots ,d_n)$, and $L=D-W$. The support graph has edge $\{i,j\}$ exactly when $w_{ij}>0$; two vertices are in the same connected component exactly when a finite path of support edges joins them. Use increasing vertex order for every submatrix, boundary vector, and returned output coordinate.

Inspect every connected component in increasing vertex order. If some component meeting $U$ misses $B$, return status $\mathtt{\text{unanchored-component}}$ and the unanchored components before forming a solve. If $U=\mathrm{\varnothing }$, return $Y_B$, an empty unlabeled output, and status $\mathtt{\text{no-unlabeled-vertices}}$. Otherwise set $M=L_{UU}$.

For each column $c=1,\dots ,r$ in order, start a fresh counter at zero and form $b_c=-L_{UB}(Y_B{)}_{:,c}$, evaluating the matrix-vector product in increasing vertex order. Recompute a fresh lower-triangular Cholesky factor $R$ of $M$ for this column by the recurrence: initialize $R$ to zero; in increasing order $j=1,\dots ,\mathrm{\mid }U\mathrm{\mid }$, compute $p_j=M_{jj}-{\sum }_{k<j}{R}_{jk}^2$, return status $\mathtt{\text{factorization-failure}}$ if $p_j\le 0$, set $R_{jj}=\sqrt{p_j}$, and for $i>j$ set $R_{ij}=(M_{ij}-{\sum }_{k<j}{R}_{ik}{R}_{jk})\mathrm{/}{R}_{jj}$. Recompute $R$ for each column so that the factorization cost is part of that column's cap.

Count each real addition, subtraction, multiplication, division, comparison, and square root as one scalar operation. Evaluate every finite sum left-to-right in increasing index order, with an empty sum equal to zero. For each coordinate of $b_c$, implement the unary negation as one subtraction from zero and include that subtraction in the count. Input validation, degree/Laplacian construction, component scans, loop-control comparisons, and budget checks are outside the per-column count. The count for column $c$ includes forming $b_c$, its Cholesky recurrence, both triangular substitutions, and its residual calculation. Before each counted operation, if it would make the counter exceed $K$, return status $\mathtt{\text{budget-exhausted}}$ with outputs and residuals for only the fully completed columns before $c$. If a Cholesky pivot satisfies $p_j\le 0$, return status $\mathtt{\text{factorization-failure}}$ with outputs and residuals for only the fully completed columns before $c$.

Solve $R{v}_c=b_c$ by $v_{c,i}=((b_c{)}_i-{\sum }_{j<i}{R}_{ij}{v}_{c,j})\mathrm{/}{R}_{ii}$ in increasing $i$, and solve $R^T{z}_c=v_c$ by $z_{c,i}=(v_{c,i}-{\sum }_{j>i}{R}_{ji}{z}_{c,j})\mathrm{/}{R}_{ii}$ in decreasing $i$, using the same counter and sum convention. Compute $e_{c,i}={\sum }_{j=1}^{\mathrm{\mid }U\mathrm{\mid }}{M}_{ij}{z}_{c,j}-(b_c{)}_i$ in increasing $i$, then ${\rho }_c=({\sum }_{i=1}^{\mathrm{\mid }U\mathrm{\mid }}{e}_{c,i}^2{)}^{1\mathrm{/}2}$, again using the same counter. If ${\rho }_c>\epsilon$, return status $\mathtt{\text{residual-failure}}$ with candidate coordinates and residuals through column $c$. If all columns pass, return $Y_U=(z_1,\dots ,z_r)$, the residuals, and status $\mathtt{\text{residual-passed}}$.

Graph-harmonic label extension on a finite weighted graph: fixes the finite support graph, boundary data, componentwise anchor condition, and energy.

Anchored graph-harmonic extensions are unique and obey a maximum principle: proves that the anchored principal block is positive definite and gives the exact harmonic solution.

The real Cholesky recurrence computes the positive-diagonal factor: proves the displayed deterministic recurrence returns the real positive-diagonal Cholesky factor for the anchored positive-definite block.

Forward and backward substitution are correct, unique, and quadratic in scalar operations: supplies the unique triangular substitutions used to solve each column.

Zhu, Ghahramani, and Lafferty, Semi-Supervised Learning Using Gaussian Fields and Harmonic Functions, §2

Chapelle, Schölkopf, and Zien, Semi-Supervised Learning, Chapter 11 §§11.2–11.3

Here semi-supervised input means labeled examples together with unlabeled examples or their feature marginal $P_X$. The finite harmonic extension uses the supplied graph weights to prefer scores that vary little across large-weight edges; it does not identify the ground-truth conditional label law $P(Y\mid X)$. A cluster assumption posits that points in the same cluster are likely to share a class; low-density separation posits that a classifier boundary lies in a region of small $P_X$-mass; graph smoothness favors scores that vary little across edges with large supplied weights. These are additional modeling assumptions relating $P_X$ and $P(Y\mid X)$, not consequences of observing $P_X$. The pseudo-label procedure is also a training heuristic. This batch states no general population-risk improvement, consistency, minimax, calibration, or graph-limit theorem. The exact harmonic maximum principle concerns the supplied boundary labels, not unknown true labels.

Finite-round confidence-threshold pseudo-labeling: the finite pseudo-label procedure returns a fixed training assignment and makes no risk guarantee.

Finite graph-harmonic label propagation with a residual status: the finite graph solver returns score candidates and residual statuses; only zero-residual exact solutions are the harmonic extension, and neither certifies true labels.

The unlabeled marginal alone does not identify labels: identical feature marginals and observed labels can leave positive-mass labels unidentified.

Zhu, Ghahramani, and Lafferty, Semi-Supervised Learning Using Gaussian Fields and Harmonic Functions, §2

Chapelle, Schölkopf, and Zien, Semi-Supervised Learning, Chapter 1 §1.2.2 and §§1.3.2–1.3.3, and Chapter 11 §11.6