Pipeline-generated

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

Nearest neighbors and learned metrics — Examples

1 · Prerequisites

2 · Logical flowchart

3 · Definitions, theorems and proofs

None yet.

4 · Examples, counterexamples and false statements

ExampleConstruction: AI-generatedVerification: AI-generatedjudge pass (gpt-6-luna)Open item page →

A rank-deficient Mahalanobis matrix identifies distinct points

Example

On $R^{2}$ , let $M = (\begin{array}{cc} 1 & 0 \\ 0 & 0 \end{array})$ , $u = (0, 0)$ , and $v = (0, 1)$ . The matrix is symmetric, positive semidefinite, and singular, while $u \neq v$ . Its Mahalanobis pseudometric satisfies $d_{M} (u, v) = 0$ . Thus the pseudometric need not separate distinct points, whereas a metric requires distance zero only for equal points.

Example references

Definition of the squared Mahalanobis distance and its square root

Pseudometric properties and linear-feature representation

Facts & Assumptions

Given: The matrix $M$ and points $u, v$ in the Example.

[F1]

For $M ⪰ 0$ , $q_{M} (x, x^{'}) = (x - x^{'})^{T} M (x - x^{'})$ and $d_{M} (x, x^{'}) = \sqrt{q_{M} (x, x^{'})}$ . A pseudometric need not separate distinct points (Mahalanobis pseudometric induced by a positive-semidefinite matrix).

[F2]

The square-root distance associated with a positive-semidefinite matrix satisfies the pseudometric axioms (The Mahalanobis distance is a pseudometric and comes from a linear feature map).

Verification

1.1givenalgebra

The matrix $M$ is symmetric, and for every $(a, b) \in R^{2}$ , $(a, b) M (a, b)^{T} = a^{2} \geq 0$ ; its rank is one, so it is singular. Also $u \neq v$ .

1.2givenF1algebra

The difference $u - v = (0, - 1)$ satisfies $(u - v)^{T} M (u - v) = 0$ , hence $q_{M} (u, v) = 0$ and $d_{M} (u, v) = \sqrt{0} = 0$ by [F1].

2.1step 1.2F2∎

Step 1.2 exhibits zero distance between distinct points, so this valid Mahalanobis pseudometric fails the separation property required of a metric; [F2] confirms its other pseudometric axioms.

ExampleConstruction: AI-generatedVerification: AI-generatedjudge pass (gpt-6-luna)Open item page →

A fixed LMNN target triplet can retain a positive margin loss

Example

Take $d = 1$ , $n = 3$ , $C = 2$ , inputs $x_{1} = 0$ , $x_{2} = 1$ , $x_{3} = - 1$ , labels $y_{1} = y_{2} = 1$ , $y_{3} = 2$ , fixed target sets $N_{1} = {2}$ , $N_{2} = {1}$ , $N_{3} = \emptyset$ , and $μ = \frac{1}{2}$ . Every positive-semidefinite matrix is a scalar $M = [m]$ with $m \geq 0$ . For the anchor $i = 1$ , target $j = 2$ , and impostor $l = 3$ , the LMNN hinge term is exactly $[1 + q_{M} (x_{1}, x_{2}) - q_{M} (x_{1}, x_{3})]_{+} = 1$ for every feasible $M$ ; therefore the fixed target triplet cannot attain zero margin loss.

Example references

Fixed target sets and the LMNN push hinge

Facts & Assumptions

Given: The sample, labels, fixed target sets, and weighting parameter in the Example.

[F1]

For $M ⪰ 0$ , every $q_{M} (x, x^{'})$ is nonnegative; the push terms are positive parts, and the full objective is the nonnegative weighted sum of the pull and push terms (Fixed-target large-margin nearest-neighbor objective).

Verification

1.1givenF1algebra

A scalar matrix $M = [m]$ is feasible exactly when $m \geq 0$ . For the designated triplet, $q_{M} (x_{1}, x_{2}) = (0 - 1)^{2} m = m$ and $q_{M} (x_{1}, x_{3}) = (0 - (- 1))^{2} m = m$ , so the hinge argument is $1 + m - m = 1$ and its value is $[1]_{+} = 1$ .

2.1step 1.1F1algebra∎

Every squared distance and every hinge term in $F_{1 / 2}$ is nonnegative. The designated hinge contributes $\frac{1}{2}$ , so $F_{1 / 2} (M) \geq \frac{1}{2}$ for every feasible $M$ , and this triplet's margin loss cannot be zero.

ExampleConstruction: AI-generatedVerification: AI-generatedjudge pass (gpt-6-luna)Open item page →

One decreasing LMNN projection step is not a convergence certificate

Example

Take $d = 1$ , $n = 2$ , one class with labels $y_{1} = y_{2} = 1$ , sample points $x_{1} = 0$ , $x_{2} = 1$ , fixed target sets $N_{1} = {2}$ and $N_{2} = {1}$ , and $μ = 0$ . For every feasible scalar matrix $M = [m]$ with $m \geq 0$ , the fixed-target objective is $F_{0} ([m]) = 2 m$ and has minimum $0$ at $M = [0]$ . Start from $M_{0} = [2]$ , use one update $T = 1$ and step size $η_{0} = \frac{1}{4}$ . The finite projected-subgradient method returns $M_{1} = [\frac{3}{2}]$ and reduces the objective from $4$ to $3$ , but the returned point is still strictly suboptimal. Thus a decreasing finite step does not certify convergence or optimality.

Example references

Fixed-target LMNN objective

LMNN subgradient at the selected iterate

Finite projected-subgradient update

Facts & Assumptions

Given: The two-point sample, the target sets, $μ = 0$ , the initial matrix, and the single stepsize in the Example.

[F1]

The pull term is the sum of squared Mahalanobis distances over fixed targets, the push term sums only over differently labeled impostors, and $F_{μ} = (1 - μ) ϵ_{p u l l} + μ ϵ_{p u s h}$ (Fixed-target large-margin nearest-neighbor objective).

[F2]

At an exact projected-subgradient step, use the explicit formula for $G (M)$ , taking hinge coefficient zero at a kink (LMNN hinge subgradient formula and a uniform data-dependent bound).

[F3]

The update is $M_{t + 1}$ equal to Frobenius projection of $M_{t} - η_{t} G_{t}$ onto the PSD cone, equivalently eigenvalue clipping (Finite-budget projected-subgradient training for fixed-target LMNN).

Verification

1.1givenF1algebra

For a scalar feasible matrix $M = [m]$ , $q_{M} (0, 1) = q_{M} (1, 0) = m$ . Since the labels agree, there are no impostor terms; hence $F_{0} ([m]) = 2 m$ , which is minimized over $m \geq 0$ at $m = 0$ . Therefore $F_{0} (M_{0}) = 4$ .

1.2givenF2F3algebra

The two pull matrices are both $[1]$ , and $μ = 0$ , so the selected subgradient is $G_{0} = [2]$ by [F2]. The update [F3] clips $M_{0} - η_{0} G_{0} = [2 - \frac{1}{4} \cdot 2] = [\frac{3}{2}]$ to the PSD cone, leaving $M_{1} = [\frac{3}{2}]$ .

2.1step 1.1step 1.2algebra∎

Then $F_{0} (M_{1}) = 3 < 4 = F_{0} (M_{0})$ , but $F_{0} (M_{1}) = 3 > 0 = F_{0} ([0])$ . Thus the step decreases the objective while the finite returned iterate is still suboptimal, so this step supplies no convergence or optimality certificate.