Przejdź do treści
Wróć do wyników wyszukiwania

Uzupełnianie macierzy

Autor metody
Emmanuel Candès & Benjamin Recht
Rok
2009
Typ
Convex low-rank recovery
Rodzina
Missing data

Ten tekst jest tłumaczeniem maszynowym i nie został jeszcze sprawdzony. Przeczytaj oryginał po angielsku

Rozmiar czcionki

Do czego służy?

Uzupełnianie macierzy to technika odzyskiwania macierzy niskiej rangi na podstawie małego, być może losowego podzbioru jej elementów.

Zaproponowana przez Emmanuela Candèsa i Benjamina Recht w 2009 roku, przekształca problem w minimalizację normy jądrowej – wypukłe zastępstwo minimalizacji rangi – i zapewnia teoretyczne gwarancje, że dokładne odzyskanie jest osiągalne, gdy elementy są obserwowane losowo i macierz spełnia warunek niespójności.

Intuicja stojąca za metodą

Wyobraźmy sobie częściowo wypełniony arkusz ocen użytkowników dla filmów, gdzie większość komórek jest pusta. Jeśli leżące u podstaw dane mają prostą strukturę – powiedzmy, że gust jest wyjaśniany przez zaledwie kilka ukrytych czynników, takich jak preferencje gatunkowe i epoka – to znajomość nawet niewielkiej części ocen wystarczy, aby z pewnością wypełnić resztę. Uzupełnianie macierzy wykorzystuje tę ukrytą niskowymiarową strukturę, podobnie jak składanie układanki, gdy wiemy, że obraz ma tylko kilka odrębnych kształtów.

Historia

Uzupełnianie macierzy wyłoniło się z literatury dotyczącej kompresji sensingu. Candès i Recht (2009) przedstawili pierwsze twierdzenie o dokładnym odzyskaniu za pomocą minimalizacji normy jądrowej, a wkrótce potem prace Candèsa i Tao na temat mocy niespójności. Metoda zyskała szeroką uwagę publiczną dzięki konkursowi Netflix Prize, w którym metody filtrowania kolaboracyjnego o niskiej randze osiągnęły najwyższą dokładność rekomendacji. Kolejne prace Recht, Fazel i Parrilo połączyły minimalizację normy jądrowej z regularyzacją normy śladu w uczeniu maszynowym.

Kiedy stosować

Używaj uzupełniania macierzy, gdy dane można zorganizować jako macierz z systematycznie brakującymi elementami i istnieje powód, by sądzić, że prawdziwy sygnał ma niską rangę – na przykład w systemach rekomendacyjnych, genomice, analizie sieci społecznościowych i odzyskiwaniu obrazów. Kluczowe założenia to losowość brakujących elementów i spełnienie przez macierz warunku niespójności. Nie nadaje się do macierzy ze strukturalnym lub nie-losowym brakiem danych, bardzo wysoką rangą lub gdy założenie o niskiej randze jest nieuzasadnione. Alternatywy obejmują imputację MICE dla ogólnych brakujących danych i NMF, gdy wymagana jest nieujemność.

Ograniczenia i uwagi

  • Koszt obliczeniowy programowania półokreślonego słabo skaluje się wraz z wymiarami macierzy
  • Założenie o niespójności może zawieść w rzeczywistych zbiorach danych ze strukturalnymi brakami lub wartościami odstającymi
  • Wydajność spada, gdy rzeczywista ranga nie jest znacznie mniejsza od wymiarów macierzy
  • Minimalizacja normy jądrowej może być wrażliwa na szum; odporne warianty dodają dodatkową złożoność

Warunki podane w źródle nie zastępują niezależnego przeglądu naukowego ani walidacji przez silnik analityczny.

Mocne strony

  • Dowodnie dokładne odzyskanie w łagodnych warunkach za pomocą wypukłego programu o czasie wielomianowym
  • Obsługuje bardzo wysokie wskaźniki braków danych, gdy macierz jest rzeczywiście niskiej rangi
  • Nie jest wymagana wcześniejsza znajomość rangi; minimalizacja normy jądrowej znajduje ją niejawnie
  • Silne gwarancje teoretyczne zakorzenione w teorii macierzy losowych i analizie wypukłej

Zastosowania

  • Filtrowanie kolaboracyjne i systemy rekomendacyjne (przewidywanie ocen użytkownik-element)
  • Genomika i bioinformatyka (odzyskiwanie macierzy ekspresji genów z brakującymi pomiarami)
  • Widzenie komputerowe (wypełnianie obrazów i odejmowanie tła wideo)
  • Lokalizacja sieci czujników (odzyskiwanie macierzy pozycji z częściowych pomiarów odległości)
  • Neuro nauka (uzupełnianie macierzy łączności funkcjonalnej z częściowych obserwacji fMRI)

Jak to działa

Jak to działa

1

Algorytm rozpoczyna się od macierzy M, której elementy są obserwowane tylko na zbiorze indeksów Omega. Te zaobserwowane wartości stanowią ograniczenia dla problemu odzyskiwania. Zakłada się, że wzorzec rzadkości jest próbkowany losowo, co stanowi teoretyczne ustawienie, w którym ustanowiono gwarancje dokładnego odzyskania.

Wzór
\text{Given } M \in \mathbb{R}^{n_1 \times n_2},\; \text{observe entries } \{M_{ij}\}_{(i,j)\in\Omega}
2

Ponieważ bezpośrednia minimalizacja rangi macierzy jest problemem NP-trudnym, Candès i Recht proponują minimalizację normy jądrowej – sumy wartości osobliwych – jako wypukłe rozluźnienie. Norma jądrowa odgrywa taką samą rolę dla macierzy, jaką norma L1 odgrywa dla wektorów w kompresji sensingu: promuje rozwiązania niskiej rangi, jednocześnie utrzymując problem w zasięgu programowania półokreślonego.

Wzór
\min_{X} \|X\|_* \quad \text{subject to} \quad X_{ij} = M_{ij},\; \forall (i,j)\in\Omega
3

Aby odzyskanie było możliwe, wektory osobliwe prawdziwej macierzy nie mogą być zbyt wyrównane ze standardową bazą, co jest kwantyfikowane przez parametr niespójności mu. Macierze, które koncentrują swoją energię w tylko kilku wierszach lub kolumnach, są niespójne; wysoce zlokalizowane macierze naruszają ten warunek i nie mogą zostać odzyskane z losowej próbki, ponieważ zbyt wiele informacji jest zakodowanych w niezaobserwowanych elementach.

Wzór
\max_{i} \|U^\top e_i\|^2 \leq \frac{\mu r}{n_1},\quad \max_{j} \|V^\top e_j\|^2 \leq \frac{\mu r}{n_2}
4

Gdy liczba zaobserwowanych elementów przekracza próg proporcjonalny do mu razy r razy n log n, minimalizator problemu normy jądrowej odzyskuje prawdziwą macierz z dużą dokładnością i wysokim prawdopodobieństwem. Wynik ten pokazuje, że wymagany rozmiar próbki jest tylko logarytmicznie większy od wewnętrznych stopni swobody macierzy rangi r, co czyni podejście bliskim optymalnemu z punktu widzenia teorii informacji.

Wzór
\text{If } |\Omega| \geq C \cdot \mu r n \log n,\; \text{then } \hat{X} = M \text{ with high probability}

Częste pułapki

  • Założenie o losowym braku danych, gdy rzeczywiste obserwacje są wybierane przez użytkownika lub są obciążone (np. oceniane są tylko wysoko oceniane elementy), co narusza teoretyczny model próbkowania
  • Zaniedbanie sprawdzenia warunku niespójności, prowadzące do słabego odzyskania nawet przy wystarczającej liczbie obserwacji
  • Używanie minimalizacji normy jądrowej bez skalowania lub regularyzacji w ustawieniu z szumem, gdzie formuła dokładnego odzyskania jest nieodpowiednia
  • Mylenie uzupełniania macierzy z heurystykami faktoryzacji macierzy: naprzemienne najmniejsze kwadraty mogą zbiegać do minimów lokalnych i brakuje im gwarancji odzyskania minimalizacji normy jądrowej

Najczęściej zadawane pytania

Czy minimalizacja normy jądrowej jest jedynym sposobem rozwiązania problemu uzupełniania macierzy?

Nie. Naprzemienne najmniejsze kwadraty (ALS) i spadek gradientu na postaciach rozłożonych (np. SGD na U i V takich, że M ≈ UV^T) są szeroko stosowane w praktyce ze względu na skalowalność. Jednak te niewypukłe podejścia nie mają gwarancji dokładnego odzyskania minimalizacji normy jądrowej i mogą zbiegać do minimów lokalnych bez starannej inicjalizacji.

Ile danych jest potrzebnych do dokładnego odzyskania?

Candès i Recht pokazali, że wystarcza około C·mu·r·n·log(n) zaobserwowanych elementów dla macierzy n×n rangi r z parametrem niespójności mu. W praktyce oznacza to, że macierz niskiej rangi można często odzyskać z próbki, która jest tylko niewielkim wielokrotnością jej wewnętrznych stopni swobody, które wynoszą r(2n−r) dla macierzy n×n.

Czym jest warunek niespójności i dlaczego ma znaczenie?

Niespójność mierzy, jak bardzo wektory osobliwe są rozłożone w bazie współrzędnych. Macierz ze skoncentrowanymi wektorami osobliwymi – taka jak macierz rangi 1, która jest niezerowa tylko w jednym wierszu – przechowuje większość swoich informacji w małym zbiorze elementów. Jeśli te elementy okażą się niezaobserwowane, odzyskanie jest niemożliwe, niezależnie od tego, ile innych elementów jest znanych.

Pokrewne metody

Źródła

  1. Candès, E. J., & Recht, B. (2009). Exact matrix completion via convex optimization. Foundations of Computational Mathematics, 9(6), 717–772.

    Otwórz odnośnik DOI
    Skopiowano.