Počítat skicu - Count sketch - Wikipedia

Počítat skicu je typ snížení rozměrů to je zvláště efektivní v statistika, strojové učení a algoritmy.^[1][2]To bylo vynalezeno Mosesem Charikarem, Kevinem Chenem a Martinem Farach-Coltonem^[3] ve snaze urychlit AMS Sketch Alon, Matias a Szegedy pro aproximaci frekvenčních momentů proudů.^[4]

Skica je téměř totožná s Hashování funkcí algoritmus John Moody,^[5] ale liší se v použití hash funkcí s nízkou závislostí, což je činí praktičtějším. Aby byla stále vysoká pravděpodobnost úspěchu, střední trik se používá k agregaci více náčrtů počtu, spíše než průměr.

Tyto vlastnosti umožňují použití pro explicitní metody jádra, bilineární sdružování v neuronové sítě a je základním kamenem mnoha numerických algoritmů lineární algebry.^[6]

Matematická definice

1. Pro konstanty ${ displaystyle w}$ a ${ displaystyle d}$ (bude definováno později) nezávisle zvolit ${ displaystyle 2d}$ náhodné hash funkce${ displaystyle h_ {1}, tečky, h_ {d}}$ a ${ displaystyle s_ {1}, dots, s_ {d}}$ takhle${ displaystyle h_ {i}: [n] až [w]}$ a${ displaystyle s_ {i}: [n] do { pm 1 }}$Je nutné, aby hash rodiny, ze kterých ${ displaystyle h_ {i}}$ a ${ displaystyle s_ {i}}$ jsou vybrány být párově nezávislé.

2. Pro každou položku ${ displaystyle q_ {i}}$ ve streamu přidat ${ displaystyle s_ {j} (q_ {i})}$ do ${ displaystyle h_ {j} (q_ {i})}$th vědro ${ displaystyle j}$th hash.

Na konci tohoto procesu jeden má ${ displaystyle wd}$ částky ${ displaystyle (C_ {ij})}$ kde

${ displaystyle C_ {ij} = součet _ {h_ {i} (k) = j} s_ {i} (k).}$

Odhadnout počet ${ displaystyle q}$s one vypočítá následující hodnotu:

${ displaystyle { text {median}} _ {i} , s_ {i} (q) cdot C_ {i, h_ {i} (q)}.}$

Vztah k tenzoru skica

Počítá se projekce náčrtu vnější produkt dvou vektorů je ekvivalentní s konvoluce dvou náčrtů počtu komponent.

Náčrt počtu počítá vektor konvoluce

${ displaystyle C ^ {(1)} x ast C ^ {(2)} x ^ {T}}$, kde ${ displaystyle C ^ {(1)}}$ a ${ displaystyle C ^ {(2)}}$ jsou nezávislé matice počtu skic.

Pham a Pagh^[7] ukázat, že se to rovná ${ displaystyle C (x otimes x ^ {T})}$ - počet skica ${ displaystyle C}$ z vnější produkt vektorů, kde ${ displaystyle otimes}$ označuje Produkt Kronecker.

K rychlé konvoluci počtu skic lze použít rychlá Fourierova transformace.Pomocí produkt rozdělující obličej^[8][9][10] taková struktura se počítala mnohem rychleji než normální matice.

Viz také

• Count – min skica
• Tensorsketch

Reference

Další čtení

• Faisal M. Algashaam; Kien Nguyen; Mohamed Alkanhal; Vinod Chandran; Wageeh Boles. „Multispektrální periokulární klasifikace s multimodálním kompaktním vícelineárním sdružováním“ [1]. Přístup IEEE, Sv. 5. 2017.
• Ahle, Thomas; Knudsen, Jakob (03.09.2019). „Téměř optimální náčrt tenzoru“. Researchgate. Citováno 2020-07-11.