Losowe projekcje Metody, algorytmy i wybrane zastosowania

Losowe projekcje (losowe rzutowania) są jednym z narzędzi redukcj wymiaru, które pozwalają rozwiązywać w efektywny sposób problemy oryginalnie sformułowane w bardzo wysokowynmiarowych przestrzeniach.

Problemy te nie dotyczą tylko teorii aproksymacji, asymptotycznej teorii skończeniewymiarowych przestrzeni unormowanych, analizy funkcjonalnej, geometrii, teorii prawdopodobieństwa, statystyki, ale również przetwarzania sygnałów, dyskretnej optymalizacji, przetwarzania strumieni danych, ekstracji wiedzy z dużych baz danych i bardzo wielu innych.

Oparte na losowych projekcjach zastosowania lematu Johnsona-Lindenstraussa sięgają od zadań wyznaczania najbliższych sąsiadów, dyskretnej optymalizacji, problemów przetwarzania obrazów, a w szczególności ich komprsji, zagadnień klasyfikacji w przestrzeniach wysokowymiarowych po problemy uczenia maszynowego.

Spis treści:

1. Przedmowa

2. Przetwarzanie wielowymiarowych danych i redukcja wymiaru
2.1. Wiele wymiarów
2.2. Wielowymiarowość. Przekleństwo czy błogosławieństwo?
2.3. Analiza danych - zadania
2.4. Metody redukcji wymiaru

3. Zanurzenia, lemat Johnsona-Lindenstraussa i koncentracja miary
3.1. Zanurzenia
3.2. Lemat Johnsona-Lindenstraussa
3.3. Koncentracja miary
3.4. Uwagi

4. Losowe liniowe projekcje
4.1. Losowe liniowe normalne projekcje
4.2. Dowód lematu Johnsona-Lindenstrausa 4.3. Losowe ortogonalne projekcje
4.4. Losowe projekcje z rzadkimi macierzami przekształcenia
4.5. Własności iloczynu skalarnego i współczynnika korelacji
4.6. Projekcje Cauchego
4.7. Uwagi

5. Metody losowych projekcji w rozpoznawaniu na podstawie najbliższych sąsiadów
5.1. Wyznaczanie najbliższych sąsiadów w przestrzeni wysokowymiarowej
5.2. Przybliżeni najbliżsi sąsiedzi a redukcja wymiaru metodą liniowych projekcji
5.3. Algorytm M najbliższych sąsiadów
5.4. Metody grupy klasyfikatorów z udziałem losowych projekcji
5.5. Uwagi bibliograficzne i inne

6. Losowe projekcje rozkładów normalnych
6.1. Liniowe losowe projekcje wielowymiarowych zmiennych losowych o rozkładzie normalnym
6.2. Macierz kowariancji projekcji rozkładu normalnego
6.3. Uwagi o projekcjach danych z innych rozkładów

7. Wykrywanie zmian w procesie
7.1. Wykrywanie zmian w strumieniu danych
7.2. Losowe projekcje w statystycznym monitorowaniu procesu
7.3. Wielowymiarowa karta kontrolna Hotellinga
7.4. Losowe projekcje w monitorowaniu danych z rozkładów normalnych o dużym wymiarze
7.5. Własności statystyki Hotellinga w kontekście losowych projekcji
7.6. Skuteczność wykrywania zmian w rozkładzie przez k wymiarową kartę
7.7. Eksperymenty symulacyjne
7.8. Porównanie redukcji wymiaru metodą losowych projekcji z metodą komponentów głównych
7.9. Uwagi bibliograficzne i komentarze

8. Losowe projekcje w sieciach neuronowych
8.1. Sieci samoorganizujące SOM
8.2. Własności jednokierunkowych sieci sigmoidalnych z wyjściową warstwą losową
8.3. Sieci radialne
8.4. Uwagi bibliograficzne

9. Losowe projekcje w przetwarzaniu obrazów
9.1. Metody korelacyjne w przetwarzaniu obrazów
9.2. Losowe projekcje wektorów obrazów

10. Dodatek I. Macierze i ich własności
10.1. Podstawowe definicje i własności związane z macierzami
10.2. Rozkład macierzy według wartości osobliwych
10.3. Rozkład spektralny macierzy
10.4. Normy macierzy
10.5. Pseudoodwrotność macierzy Moore-Penorse

11. Dodatek II. Probabilistyka
11.1. Oszacowanie Bonferroni
11.2. Rozkłady prawdopodobieństwa
11.3. Funkcja generująca momenty formy kwadratowej wektora losowego o rozkładzie normalnym
11.4. Rozkład równomierny na wielowymiarowej sferze
11.5. Nierówności
11.6. Rozkłady subgaussowskie