काउंट स्केच

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

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

ये गुण तंत्रिका नेटवर्क में स्पष्ट कर्नेल विधियों, बिलिनियर पूल (कंप्यूटर विज्ञान)

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

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$निम्नलिखित मान की गणना करता है:

$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}$ से अधिक कभी नहीं होने की गारंटी है $2m_{2}/{\sqrt {w}}$ सही मूल्य से दूर, संभावना के साथ $1-e^{-O(t)}$.

वेक्टर सूत्रीकरण

वैकल्पिक रूप से काउंट-स्केच को गैर-रैखिक पुनर्निर्माण समारोह के साथ रेखीय मानचित्रण के रूप में देखा जा सकता है। होने देना $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}$, कहाँ $C^{(1)}$ और $C^{(2)}$ स्वतंत्र गणना स्केच मेट्रिसेस हैं।

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

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

यह भी देखें

• काउंट-मिन स्केच
• Tensorsketch

अग्रिम पठन

• 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.