Johnson – Lindenstraussovo lemma - Johnson–Lindenstrauss lemma - Wikipedia

V matematice je Johnson – Lindenstraussovo lemma je výsledek pojmenovaný po William B. Johnson a Joram Lindenstrauss týkající se nízkého zkreslení vložení bodů z vysoce dimenzionálních do nízkodimenzionálních Euklidovský prostor. Lemma říká, že množinu bodů ve vysokodimenzionálním prostoru lze vložit do prostoru mnohem nižší dimenze takovým způsobem, že vzdálenosti mezi body jsou téměř zachovalé. Mapa použitá pro vložení je minimálně Lipschitz, a lze jej dokonce považovat za ortogonální projekce.

Lema má aplikace v komprimované snímání, rozmanité učení, snížení rozměrů, a vkládání grafů. Velká část dat uložených a manipulovaných v počítačích, včetně textu a obrázků, může být reprezentována jako body ve vysokodimenzionálním prostoru (viz vektorový vesmírný model pro případ textu). Základní algoritmy pro práci s takovými daty však mají tendenci velmi rychle zapadat s rostoucí dimenzí.[1] Je proto žádoucí snížit rozměrnost údajů způsobem, který zachovává jejich příslušnou strukturu. Johnsonovo-Lindenstraussovo lema je v tomto duchu klasickým výsledkem.

Lema je také napjatá až do konstantního faktoru, tj. Existuje množina bodů velikosti m to potřebuje rozměr

aby se zachovaly vzdálenosti mezi všemi dvojicemi bodů v rámci faktoru .[2]

Lemma

Dáno , sada z body v a číslo , existuje lineární mapa takhle

pro všechny .

Vzorec lze přeskupit:

Jeden důkaz lemmatu trvá ƒ být vhodným násobkem ortogonální projekce na náhodný podprostor dimenze v a využívá fenomén koncentrace opatření.

Je zřejmé, že ortogonální projekce obecně sníží průměrnou vzdálenost mezi body, ale na lemma lze pohlížet jako na řešení relativní vzdálenosti, které se při změně měřítka nemění. Stručně řečeno, hodíte kostkami a získáte náhodnou projekci, která sníží průměrnou vzdálenost, a poté zvětšíte vzdálenosti tak, aby se průměrná vzdálenost vrátila na předchozí hodnotu. Pokud budete stále házet kostkami, najdete v polynomiálním náhodném čase projekci, pro kterou (zmenšené) vzdálenosti splňují lemma.

Alternativní prohlášení

Příbuzné lemma je distribuční JL lemma. Toto lemma uvádí, že pro libovolnou 0 <ε, δ <1/2 a kladné celé číslo d, existuje distribuce přes Rk × d ze kterého je matice A je nakreslen tak, že pro k = Ó(ε−2protokol (1 /δ)) a pro jakýkoli vektor délky jednotky XRd, platí níže uvedený nárok.[3]

Lemma JL lze získat z distribuční verze nastavením a pro pár u,proti jak V. .. tak v X. Potom JL lemma následuje spojením vázaným přes všechny takové páry.

Urychlení transformace JL

Dáno A, výpočet maticového vektorového produktu trvá Ó(kd) čas. Tam byla nějaká práce v odvození distribucí, pro které lze vektorový produkt matice vypočítat za méně než Ó(kd) čas.

Existují dvě hlavní linie práce. První, Rychlá Johnson Lindenstrauss Transformace (FJLT),[4] byl představen Ailon a Chazelle v roce 2006.Tato metoda umožňuje výpočet vektorového produktu matice v pouhých pro jakoukoli konstantu .

Dalším přístupem je vytvoření distribuce podporované maticemi, které jsou řídké.[5]Tato metoda umožňuje uchovat pouze zlomek položek v matici, což znamená, že výpočet lze provést pouze čas. Dále, pokud má vektor pouze ne-zereo záznamy, Sparse JL nějakou dobu trvá , což může být mnohem méně než čas používaný Fast JL.

Tenzorované náhodné projekce

Je možné kombinovat dvě JL matice pomocí tzv Produkt rozdělující obličej je definován jako tenzorové produkty řádků (navrhl V. Slyusar[6] v roce 1996[7][8][9][10][11] pro radar a digitální anténní pole přímo), nechte a být dvě matice Produkt rozdělující obličej je[7][8][9][10][11]

Tuto myšlenku tenzorizace použili Kasiviswanathan et al. 2010[12] pro rozdílné soukromí.

Takto definované matice JL používají méně náhodných bitů a lze je rychle použít na vektory, které mají strukturu tenzorů, kvůli následující identitě:[9]

,

kde je elementární (Hadamard ) Tyto výpočty byly použity k efektivnímu výpočtu polynomiální jádra a mnoho dalších algoritmů lineární algebry.[13]

V roce 2020[14] ukázalo se, že pokud matice jsou nezávislé nebo Gaussovy matice, kombinovaná matice splňuje distribuční JL lemma, pokud je počet řádků alespoň

.

Pro velké to je stejně dobré jako úplně náhodný Johnson-Lindenstrauss, ale odpovídající dolní mez ve stejném článku ukazuje, že tato exponenciální závislost na Je nutné obejít alternativní konstrukce JL.

Viz také

Poznámky

  1. ^ Například psaní o hledání nejbližšího souseda ve vysokodimenzionálních souborech dat, Jon Kleinberg píše: „Sofistikovanější algoritmy obvykle dosahují logaritmického času dotazu n na úkor exponenciální závislosti na dimenzi d; dokonce i průměrná případová analýza heuristiky, jako jsou stromy k-d, odhaluje exponenciální závislost na d v době dotazu. Kleinberg, Jon M. (1997), „Dva algoritmy pro hledání nejbližších sousedů ve vysokých dimenzích“, Sborník z dvacátého devátého výročního sympózia ACM o teorii práce s počítačem, STOC '97, New York, NY, USA: ACM, s. 599–608, doi:10.1145/258533.258653, ISBN  0-89791-888-6.
  2. ^ Kasper Green Larsen; Jelani Nelson (2017). Optimalita Johnson-Lindenstrauss Lemma. Sborník 58. výročního sympozia IEEE o základech informatiky (FOCS). str. 633-638. arXiv:1609.02094. doi:10.1109 / FOCS.2017.64.
  3. ^ Johnson, William B.; Lindenstrauss, Joram (1984). "Rozšíření mapování Lipschitze do Hilbertova prostoru". In Beals, Richard; Beck, Anatole; Bellow, Alexandra; et al. (eds.). Konference o moderní analýze a pravděpodobnosti (New Haven, Conn., 1982). Současná matematika. 26. Providence, RI: American Mathematical Society. str.189–206. doi:10.1090 / conm / 026/737400. ISBN  0-8218-5030-X. PAN  0737400.
  4. ^ Ailon, Nir; Chazelle, Bernard (2006). „Přibližný nejbližší soused a rychlá transformace Johnson – Lindenstrauss“. Proceedings of the 38th Annual ACM Symposium on Theory of Computing. New York: ACM Press. str. 557–563. doi:10.1145/1132516.1132597. ISBN  1-59593-134-1. PAN  2277181.
  5. ^ Kane, Daniel M .; Nelson, Jelani (2014). „Sparser Johnson-Lindenstrauss Transforms“. Deník ACM. 61 (1): 1. arXiv:1012.1577. doi:10.1145/2559902. PAN  3167920.. Předběžná verze tohoto článku byla zveřejněna v Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012.
  6. ^ Anna Esteve, Eva Boj & Josep Fortiana (2009): Interaction Terms in Distance-Based Regression, Communications in Statistics - Theory and Methods, 38:19, S. 3501 [1]
  7. ^ A b Slyusar, V. I. (27. prosince 1996). „Konečné produkty v maticích v radarových aplikacích“ (PDF). Radioelektronika a komunikační systémy. - 1998, roč. 41; Číslo 3: 50–53.
  8. ^ A b Slyusar, V. I. (1997-05-20). „Analytický model digitálního anténního pole na základě produktů dělících matice tváří“ (PDF). Proc. ICATT-97, Kyiv: 108–109.
  9. ^ A b C Slyusar, V. I. (1997-09-15). "Nové operace maticového produktu pro aplikace radarů" (PDF). Proc. Přímé a inverzní problémy teorie elektromagnetických a akustických vln (DIPED-97), Lviv.: 73–74.
  10. ^ A b Slyusar, V. I. (13. března 1998). "Rodina produktů tváře matic a její vlastnosti" (PDF). Cybernetics and Systems Analysis C / C of Kibernetika I Sistemnyi Analiz. - 1999. 35 (3): 379–384. doi:10.1007 / BF02733426.
  11. ^ A b Slyusar, V. I. (2003). "Zobecněné produkty tváře matic v modelech digitálních anténních polí s neidentickými kanály" (PDF). Radioelektronika a komunikační systémy. 46 (10): 9–17.
  12. ^ Kasiviswanathan, Shiva Prasad a kol. „Cena soukromého uvolnění kontingenčních tabulek a spektra náhodných matic s korelovanými řádky.“ Sborník čtyřicátého druhého sympózia ACM o teorii práce s počítačem. 2010.
  13. ^ Woodruff, David P. „Skicování jako nástroj pro numerickou lineární algebru.“ Theoretical Computer Science 10.1-2 (2014): 1-157.
  14. ^ Ahle, Thomas; Kapralov, Michael; Knudsen, Jakob; Pagh, Rasmus; Velingker, Ameya; Woodruff, David; Zandieh, Amir (2020). Nezapomenutelné skicování vysoce polynomiálních jader. ACM-SIAM Symposium on Discrete Algorithms. Sdružení pro výpočetní techniku. doi:10.1137/1.9781611975994.9.

Další čtení