Inne

Sinkhorn–Knopp

1967AktywnyOpublikowano: 29 września 2026Aktualizacja: 29 września 2026Opublikowany

Naprzemienna normalizacja wierszy i kolumn macierzy nieujemnej do macierzy podwójnie stochastycznej; rdzeń szybkiego transportu optymalnego (Sinkhorn distances).

Kluczowa innowacja

Iteracyjny algorytm skalowania macierzy do postaci podwójnie stochastycznej przez naprzemienną normalizację wierszy i kolumn — podstawa entropijnego transportu optymalnego w ML.

Kategoria

Inne

Poziom abstrakcji

Primitive

Poziom operacji

TreningInferencja

Zastosowania

Entropijny transport optymalny (Sinkhorn distances)Routing w mieszankach ekspertów (MoE)Klasteryzacja samonadzorowana (SwAV)Różniczkowalne dopasowania i przypisaniaNormalizacja macierzy do podwójnie stochastycznych

Jak działa

Startując od macierzy jądra K = exp(−C/ε) (C — koszt, ε — regularyzacja), algorytm naprzemiennie skaluje wiersze i kolumny wektorami u, v tak, by marginesy zgadzały się z zadanymi rozkładami. Po zbieżności iloczyn diag(u)·K·diag(v) jest macierzą transportu. Iteracje to proste mnożenia macierz–wektor, idealne dla GPU i różniczkowalne.

Rozwiązany problem

Dokładny transport optymalny jest kosztowny (programowanie liniowe). Sinkhorn–Knopp daje szybkie, różniczkowalne, zrównoleglalne przybliżenie przez entropijną regularyzację.