Eskizni hisoblash - Count sketch - Wikipedia

Eskizni hisoblash ning bir turi o'lchovni kamaytirish bu ayniqsa samarali statistika, mashinada o'rganish va algoritmlar.[1][2]Uni Musa Charikar, Kevin Chen va Martin Farax-Kolton ixtiro qilgan[3] tezlashtirish uchun AMS Sketch Oqimlarning chastotali momentlarini yaqinlashtirish uchun Alon, Matias va Szegedi tomonidan.[4]

Eskiz deyarli o'xshash Xususiyatni xashlash John Moody algoritmi,[5] ammo xash funktsiyalarini past bog'liqlik bilan ishlatishda farq qiladi, bu esa uni yanada amaliy qiladi. Muvaffaqiyat ehtimoli hali ham yuqori bo'lishi uchun o'rtacha hiyla-nayrang o'rtacha emas, balki bir nechta hisoblash eskizlarini yig'ish uchun ishlatiladi.

Ushbu xususiyatlar aniq foydalanishga imkon beradi yadro usullari, bilinear hovuzlash yilda asab tarmoqlari va ko'plab raqamli chiziqli algebra algoritmlarida poydevor hisoblanadi.[6]

Matematik ta'rif

1. Konstantalar uchun va (keyinroq aniqlanishi kerak) mustaqil ravishda tanlang tasodifiy xash funktsiyalari va shu kabi va.Bundan xash oilalar kerak va juftlikdan mustaqil ravishda tanlanadi.

2. Har bir buyum uchun oqimga qo'shing uchun ning chelaki xash.

Ushbu jarayon oxirida, bunga ega so'm qayerda

Sonini taxmin qilish uchun s quyidagi qiymatni hisoblaydi:

Tensor eskiziga aloqadorlik

Ning hisoblash eskiz proektsiyasi tashqi mahsulot ikki vektorning tenglamasi konversiya ikki komponentli hisoblash eskizlari.

Sanoq chizmasi vektorni hisoblab chiqadi konversiya

, qayerda va mustaqil hisoblash eskiz matritsalari.

Fam va Pag[7] bu teng ekanligini ko'rsating - hisoblash eskizi ning tashqi mahsulot vektorlarning soni, qaerda bildiradi Kronecker mahsuloti.

Hisoblash eskizlarini tez konvolyutsiyasini bajarish uchun tez Fourier konvertatsiyasi. Yordamida yuzni ajratuvchi mahsulot[8][9][10] Bunday struktura oddiy matritsalarga qaraganda ancha tezroq hisoblab chiqilgan.

Shuningdek qarang

Adabiyotlar

  1. ^ Faysal M. Algashaam; Kien Nguyen; Mohamed Alkanhal; Vinod Chandran; Wageeh Boles. "Multimpektral periokulyar tasniflash bilan multimodal ixcham ko'p chiziqli hovuzlash" [1]. IEEE Access, Jild 5. 2017 yil.
  2. ^ Ahli, Tomas; Knudsen, Yakob (2019-09-03). "Tensorning deyarli optimal chizmasi". Tadqiqot darvozasi. Olingan 2020-07-11.
  3. ^ Charikar, Musa, Kevin Chen va Martin Farax-Kolton. "Ma'lumot oqimlarida tez-tez elementlarni topish." Avtomatika, tillar va dasturlash bo'yicha xalqaro kollokvium. Springer, Berlin, Heidelberg, 2002 yil.
  4. ^ Alon, Noga, Yossi Matias va Mario Szegedi. "Chastotali momentlarni yaqinlashtirishning kosmik murakkabligi." Kompyuter va tizim fanlari jurnali 58.1 (1999): 137-147.
  5. ^ Mudi, Jon. "Ko'p qarorli ierarxiyalarda tezkor o'rganish". Asabli axborotni qayta ishlash tizimidagi yutuqlar. 1989 yil.
  6. ^ Woodruff, David P. "Raqamli chiziqli algebra vositasi sifatida eskiz". Nazariy informatika 10.1-2 (2014): 1-157.
  7. ^ Ninx, Fam; Rasmus, Pagh (2013). Aniq xususiyat xaritalari orqali tezkor va miqyosli polinom yadrolari. Bilimlarni kashf qilish va ma'lumotlarni qazib olish bo'yicha SIGKDD xalqaro konferentsiyasi. Hisoblash texnikasi assotsiatsiyasi. doi:10.1145/2487575.2487591.
  8. ^ Slyusar, V. I. (1998). "Radar qo'llanmalaridagi matritsalardagi so'nggi mahsulotlar" (PDF). Radioelektronika va aloqa tizimlari. 41 (3): 50–53.
  9. ^ Slyusar, V. I. (1997-05-20). "Matritsa yuzini ajratuvchi mahsulotlar asosida raqamli antenna massivining analitik modeli" (PDF). Proc. ICATT-97, Kiyev: 108–109.
  10. ^ Slyusar, V. I. (1998 yil 13 mart). "Matritsalardan yuz mahsulotlari va uning xususiyatlari" oilasi (PDF). Kibernetika I Sistemnyi Analiz-ning kibernetika va tizim tahlili. / 1999. 35 (3): 379–384. doi:10.1007 / BF02733426.

Qo'shimcha o'qish

  • Faysal M. Algashaam; Kien Nguyen; Mohamed Alkanhal; Vinod Chandran; Wageeh Boles. "Multimpektal ixcham ko'p chiziqli hovuz bilan periokulyar tasniflash" [1]. IEEE Access, Jild 5. 2017 yil.
  • Ahli, Tomas; Knudsen, Yakob (2019-09-03). "Tensorning deyarli optimal chizmasi". Tadqiqot darvozasi. Olingan 2020-07-11.