काउंट स्केच

स्केच गणना एक प्रकार की आयाम में कमी है | जो सांख्यिकी, मशीन लर्निंग और एल्गोरिदम में विशेष रूप से उत्तम है। इसका आविष्कार मोसेस चारिकर, केविन चेन और मार्टिन फ़राच-कोल्टन द्वारा किया गया था | धाराओं की आवृत्ति क्षणों का अनुमान लगाने के लिए एलोन, द्वारा मटियास और ज़ेजेडी द्वारा एम्स स्केच को गति देने के प्रयास में है।

स्केच लगभग जॉन मूडी द्वारा फ़ीचर हैशिंग एल्गोरिथम के समान है | किन्तु कम निर्भरता वाले हैश फलन के उपयोग में भिन्न है | जो इसे और अधिक व्यावहारिक बनाता है। अभी भी सफलता की उच्च संभावना होने के लिए, माध्य चाल का उपयोग माध्य के अतिरिक्त एकाधिक गणना रेखाचित्रों को एकत्र करने के लिए किया जाता है।

ये गुण तंत्रिका नेटवर्क में स्पष्ट कर्नेल विधियों, बिलिनियर पूल (कंप्यूटर विज्ञान) के उपयोग की अनुमति देते हैं और कई संख्यात्मक रैखिक बीजगणित एल्गोरिदम में आधारशिला हैं।

गणितीय परिभाषा

1. स्थिरांक $w$ और $t$ के लिए (बाद में परिभाषित किया जाएगा) स्वतंत्र रूप से $d=2t+1$ यादृच्छिक हैश फ़ंक्शन$h_{1},\dots ,h_{d}$ और $s_{1},\dots ,s_{d}$ चुनें | ऐसा है कि $h_{i}:[n]\to [w]$ और $s_{i}:[n]\to \{\pm 1\}$. यह आवश्यक है कि जिस हैश परिवार से $h_{i}$ और $s_{i}$ जोड़ीदार स्वतंत्र चुने जाते हैं।

2. प्रत्येक वस्तु के लिए $q_{i}$ स्ट्रीम में, जोड़ें $s_{j}(q_{i})$ तक $h_{j}(q_{i})$ वें बकेट $j$ वें हैश है |

इस प्रक्रिया के अंत में, $wd$ संस $(C_{ij})$ होता है | जहाँ

$C_{i,j}=\sum _{h_{i}(k)=j}s_{i}(k).$

$q$s की संख्या का अनुमान लगाने के लिए निम्न मान की गणना की जाती है |

$r_{q}={\text{median}}_{i=1}^{d}\,s_{i}(q)\cdot C_{i,h_{i}(q)}.$

मान $s_{i}(q)\cdot C_{i,h_{i}(q)}$ धारा में $q$ कितनी बार प्रकट हुआ है, इसका निष्पक्ष अनुमान है।

अनुमान $r_{q}$ का प्रसरण $O(\mathrm {min} \{m_{1}^{2}/w^{2},m_{2}^{2}/w\})$, जहां $m_{1}$ धारा की लंबाई है और $m_{2}^{2}$ $\sum _{q}(\sum _{i}[q_{i}=q])^{2}$ है |

इसके अतिरिक्त $r_{q}$ की प्रायिकता $1-e^{-O(t)}$ के साथ, वास्तविक मान से $2m_{2}/{\sqrt {w}}$ से अधिक नहीं होने की गारंटी है |

सदिश सूत्रीकरण

वैकल्पिक रूप से गणना-स्केच को गैर-रैखिक पुनर्निर्माण फलन के साथ रेखीय मानचित्रण के रूप में देखा जा सकता है।

माना $M^{(i\in [d])}\in \{-1,0,1\}^{w\times n}$, का संग्रह हो $d=2t+1$ आव्यूह, द्वारा परिभाषित है |

$M_{h_{i}(j),j}^{(i)}=s_{i}(j)$

के लिए $j\in [w]$ और 0 हर जगह।

फिर एक सदिश $v\in \mathbb {R} ^{n}$ को $C^{(i)}=M^{(i)}v\in \mathbb {R} ^{w}$। $v$ का पुनर्निर्माण करने के लिए हम $v_{j}^{*}={\text{median}}_{i}C_{j}^{(i)}s_{i}(j)$ लेते हैं। यदि हम $m_{1}=\|v\|_{1}$ और $m_{2}=\|v\|_{2}$ लेते हैं तो यह वही गारंटी देता है | जैसा ऊपर कहा गया है |

टेन्सर स्केच से संबंध

दो सदिशो के बाहरी उत्पाद का गणना स्केच प्रोजेक्शन दो कंपोनेंट गणना स्केच के कनवल्शन के समान है।

गणना स्केच सदिश कनवल्शन की गणना करता है |

$C^{(1)}x\ast C^{(2)}x^{T}$, where and are independent count sketch matrices.

फाम और पाघ दिखाएँ कि यह $C(x\otimes x^{T})$ समान है | वैक्टर के बाहरी उत्पाद का गिनती रेखाचित्र $C$ , जहाँ $\otimes$ क्रोनकर उत्पाद को दर्शाता है।

तेजी से फूरियर रूपांतरण का उपयोग गिनती रेखाचित्रों के तेजी से कनवल्शन करने के लिए किया जा सकता है।

फेस-स्प्लिटिंग उत्पाद का उपयोग करके ऐसी संरचनाओं की गणना सामान्य आव्यूह की तुलना में बहुत तेजी से की जा सकती है।

यह भी देखें

• गणना-मिन स्केच
• टेन्सरस्केच

अग्रिम पठन

• Faisal M. Algashaam; Kien Nguyen; Mohamed Alkanhal; Vinod Chandran; Wageeh Boles. "Multispectral Periocular Classification WithMultimodal Compact Multi-Linear Pooling" [1]. IEEE Access, Vol. 5. 2017.
• Ahle, Thomas; Knudsen, Jakob (2019-09-03). "Almost Optimal Tensor Sketch". ResearchGate. Retrieved 2020-07-11.