काउंट स्केच: Difference between revisions
From Vigyanwiki
No edit summary |
No edit summary |
||
| Line 2: | Line 2: | ||
{{Machine learning bar}} | {{Machine learning bar}} | ||
स्केच गणना एक प्रकार की [[आयामीता में कमी|आयाम में कमी]] है | जो सांख्यिकी, [[ यंत्र अधिगम | मशीन लर्निंग]] और [[एल्गोरिदम]] में विशेष रूप से उत्तम है।<ref>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.</ref><ref>{{Cite web |last1=Ahle |first1=Thomas |last2=Knudsen |first2=Jakob |date=2019-09-03 |title=लगभग इष्टतम टेंसर स्केच|url=https://www.researchgate.net/publication/335617805 |access-date=2020-07-11 |website=[[ResearchGate]]}}</ref> द्वारा इसका आविष्कार किया गया था| मोसेस चारिकर, केविन चेन और मार्टिन फ़राच-कोल्टन <ref>Charikar, Moses, Kevin Chen, and Martin Farach-Colton. "Finding frequent items in data streams." International Colloquium on Automata, Languages, and Programming. Springer, Berlin, Heidelberg, 2002.</ref> धाराओं की आवृत्ति क्षणों का अनुमान लगाने के लिए एलोन, मटियास और ज़ेजेडी द्वारा [[ एम्स स्केच ]] को गति देने के प्रयास में है।<ref>Alon, Noga, Yossi Matias, and Mario Szegedy. "The space complexity of approximating the frequency moments." Journal of Computer and system sciences 58.1 (1999): 137-147.</ref> | |||
द्वारा इसका आविष्कार किया गया था | |||
स्केच लगभग जॉन मूडी द्वारा [[फ़ीचर हैशिंग]] एल्गोरिथम के समान है |<ref>Moody, John. "Fast learning in multi-resolution hierarchies." Advances in neural information processing systems. 1989.</ref> किन्तु कम निर्भरता वाले हैश फलन के उपयोग में भिन्न है | जो इसे और अधिक व्यावहारिक बनाता है। अभी भी सफलता की उच्च संभावना होने के लिए, माध्य चाल का उपयोग माध्य के अतिरिक्त एकाधिक गणना रेखाचित्रों को एकत्र करने के लिए किया जाता है। | |||
स्केच लगभग जॉन मूडी द्वारा [[फ़ीचर हैशिंग]] एल्गोरिथम के समान है | |||
अभी भी सफलता की उच्च संभावना होने के लिए, माध्य चाल का उपयोग माध्य के | |||
ये गुण [[तंत्रिका नेटवर्क]] में स्पष्ट कर्नेल विधियों, बिलिनियर [[पूल (कंप्यूटर विज्ञान)]] के उपयोग की अनुमति देते हैं और कई संख्यात्मक रैखिक बीजगणित एल्गोरिदम में आधारशिला हैं।<ref name="woodruff">Woodruff, David P. "Sketching as a Tool for Numerical Linear Algebra." Theoretical Computer Science 10.1-2 (2014): 1–157.</ref> | ये गुण [[तंत्रिका नेटवर्क]] में स्पष्ट कर्नेल विधियों, बिलिनियर [[पूल (कंप्यूटर विज्ञान)]] के उपयोग की अनुमति देते हैं और कई संख्यात्मक रैखिक बीजगणित एल्गोरिदम में आधारशिला हैं।<ref name="woodruff">Woodruff, David P. "Sketching as a Tool for Numerical Linear Algebra." Theoretical Computer Science 10.1-2 (2014): 1–157.</ref> | ||
| Line 13: | Line 11: | ||
== गणितीय परिभाषा == | == गणितीय परिभाषा == | ||
1. स्थिरांक | 1. स्थिरांक <math>w</math> और <math>t</math> के लिए (बाद में परिभाषित किया जाएगा) स्वतंत्र रूप से <math>d=2t+1</math> यादृच्छिक हैश फ़ंक्शन<math>h_1, \dots, h_d</math> और <math>s_1,\dots,s_d</math> चुनें | ऐसा है कि <math>h_i : [n] \to [w]</math> और | ||
<math>h_1, \dots, h_d</math> और <math>s_1,\dots,s_d</math> ऐसा है कि | <math>s_i : [n] \to \{\pm 1\}</math>. यह आवश्यक है कि जिस हैश परिवार से <math>h_i</math> और <math>s_i</math> जोड़ीदार स्वतंत्र चुने जाते हैं। | ||
<math>h_i : [n] \to [w]</math> और | |||
<math>s_i : [n] \to \{\pm 1\}</math>. | |||
यह आवश्यक है कि जिस हैश परिवार से <math>h_i</math> और <math>s_i</math> जोड़ीदार स्वतंत्र चुने जाते हैं। | |||
2. प्रत्येक वस्तु के लिए <math>q_i</math> स्ट्रीम में, जोड़ें <math>s_j(q_i)</math> तक <math>h_j(q_i)</math>वें | 2. प्रत्येक वस्तु के लिए <math>q_i</math> स्ट्रीम में, जोड़ें <math>s_j(q_i)</math> तक <math>h_j(q_i)</math> वें बकेट <math>j</math> वें हैश है | | ||
इस प्रक्रिया के अंत में, <math>wd</math> संस <math>(C_{ij})</math> होता है | जहाँ | |||
:<math>C_{i,j} = \sum_{h_i(k)=j}s_i(k).</math> | :<math>C_{i,j} = \sum_{h_i(k)=j}s_i(k).</math> | ||
<math>q</math>s की संख्या का अनुमान लगाने के लिए निम्न मान की गणना की जाती है | | |||
:<math>r_q = \text{median}_{i=1}^d\, s_i(q)\cdot C_{i, h_i(q)}.</math> | :<math>r_q = \text{median}_{i=1}^d\, s_i(q)\cdot C_{i, h_i(q)}.</math> | ||
मान <math>s_i(q)\cdot C_{i, h_i(q)}</math> धारा में <math>q</math> कितनी बार प्रकट हुआ है, इसका निष्पक्ष अनुमान है। | |||
अनुमान <math>r_q</math> | अनुमान <math>r_q</math> का प्रसरण <math>O(\mathrm{min}\{m_1^2/w^2, m_2^2/w\})</math>, जहां <math>m_1</math> धारा की लंबाई है और <math>m_2^2</math> <math>\sum_q (\sum_i [q_i=q])^2</math> है |<ref>Larsen, Kasper Green, Rasmus Pagh, and Jakub Tětek. "CountSketches, Feature Hashing and the Median of Three." International Conference on Machine Learning. PMLR, 2021.</ref> | ||
<math>m_1</math> धारा की लंबाई है और <math>m_2^2</math> | |||
=== | इसके अतिरिक्त <math>r_q</math> की प्रायिकता <math>1-e^{-O(t)}</math> के साथ, वास्तविक मान से <math>2m_2/\sqrt{w}</math> से अधिक नहीं होने की गारंटी है | | ||
वैकल्पिक रूप से | |||
=== सदिश सूत्रीकरण === | |||
वैकल्पिक रूप से गणना-स्केच को गैर-रैखिक पुनर्निर्माण फलन के साथ रेखीय मानचित्रण के रूप में देखा जा सकता है। | |||
माना <math>M^{(i\in[d])}\in\{-1,0,1\}^{w \times n}</math>, का संग्रह हो <math>d=2t+1</math> आव्यूह, द्वारा परिभाषित है | | |||
:<math>M^{(i)}_{h_i(j),j} = s_i(j)</math> | :<math>M^{(i)}_{h_i(j),j} = s_i(j)</math> | ||
के लिए <math>j\in[w]</math> और 0 हर जगह। | के लिए <math>j\in[w]</math> और 0 हर जगह। | ||
फिर | फिर एक सदिश <math>v\in\mathbb{R}^n</math> को <math>C^{(i)} = M^{(i)} v \in \mathbb{R}^w</math>। <math>v</math> का पुनर्निर्माण करने के लिए हम <math>v^*_j = \text{median}_i C^{(i)}_j s_i(j)</math> लेते हैं। यदि हम <math>m_1=\|v\|_1</math> और <math>m_2=\|v\|_2</math> लेते हैं तो यह वही गारंटी देता है | जैसा ऊपर कहा गया है | | ||
== टेन्सर स्केच से संबंध == | == टेन्सर स्केच से संबंध == | ||
दो | दो सदिशो के [[बाहरी उत्पाद]] का गणना स्केच प्रोजेक्शन दो कंपोनेंट गणना स्केच के [[कनवल्शन]] के समान है। | ||
गणना स्केच सदिश कनवल्शन की गणना करता है | | |||
<math>C^{(1)}x \ast C^{(2)}x^T</math>, | <math>C^{(1)}x \ast C^{(2)}x^T</math>, where and are independent count sketch matrices. | ||
फाम और पाघ<ref name="ninh">{{cite conference | फाम और पाघ<ref name="ninh">{{cite conference | ||
| Line 59: | Line 54: | ||
| conference = SIGKDD international conference on Knowledge discovery and data mining | | conference = SIGKDD international conference on Knowledge discovery and data mining | ||
|doi = 10.1145/2487575.2487591}} | |doi = 10.1145/2487575.2487591}} | ||
</ref> दिखाएँ कि यह | </ref> दिखाएँ कि यह <math>C(x \otimes x^T)</math> समान है | वैक्टर के बाहरी उत्पाद का गिनती रेखाचित्र <math>C</math> , जहाँ <math> \otimes </math> [[क्रोनकर उत्पाद]] को दर्शाता है। | ||
तेजी से फूरियर रूपांतरण का उपयोग गिनती रेखाचित्रों के तेजी से कनवल्शन करने के लिए किया जा सकता है। | तेजी से फूरियर रूपांतरण का उपयोग गिनती रेखाचित्रों के तेजी से कनवल्शन करने के लिए किया जा सकता है। | ||
फेस-स्प्लिटिंग उत्पाद का उपयोग करके<ref>{{Cite journal|last=Slyusar|first=V. I. |title=रडार अनुप्रयोगों में मेट्रिसेस में अंतिम उत्पाद|url=http://slyusar.kiev.ua/en/IZV_1998_3.pdf|journal=Radioelectronics and Communications Systems |year=1998 |volume=41 |issue=3|pages=50–53}}</ref><ref>{{Cite journal|last=Slyusar|first=V. I.|date=1997-05-20|title=फेस-स्प्लिटिंग मैट्रिक्स उत्पादों के आधार पर डिजिटल एंटीना सरणी का विश्लेषणात्मक मॉडल।|url=http://slyusar.kiev.ua/ICATT97.pdf|journal=Proc. ICATT-97, Kyiv|pages=108–109}}</ref><ref>{{Cite journal|last=Slyusar|first=V. I.|date=March 13, 1998|title=मैट्रिसेस और उसके गुणों के फेस प्रोडक्ट्स का एक परिवार|url=http://slyusar.kiev.ua/FACE.pdf|journal=Cybernetics and Systems Analysis C/C of Kibernetika I Sistemnyi Analiz.- 1999.|volume=35|issue=3|pages=379–384|doi=10.1007/BF02733426|s2cid=119661450 }}</ref> ऐसी संरचनाओं की गणना सामान्य आव्यूह की तुलना में बहुत तेजी से की जा सकती है। | |||
== यह भी देखें == | == यह भी देखें == | ||
* | * गणना-मिन स्केच | ||
* [[Tensorsketch]] | * [[Tensorsketch|टेन्सरस्केच]] | ||
==संदर्भ== | ==संदर्भ== | ||
Revision as of 13:19, 17 May 2023
| Part of a series on |
| Machine learning and data mining |
|---|
 |
स्केच गणना एक प्रकार की आयाम में कमी है | जो सांख्यिकी, मशीन लर्निंग और एल्गोरिदम में विशेष रूप से उत्तम है।[1][2] द्वारा इसका आविष्कार किया गया था| मोसेस चारिकर, केविन चेन और मार्टिन फ़राच-कोल्टन [3] धाराओं की आवृत्ति क्षणों का अनुमान लगाने के लिए एलोन, मटियास और ज़ेजेडी द्वारा एम्स स्केच को गति देने के प्रयास में है।[4]
स्केच लगभग जॉन मूडी द्वारा फ़ीचर हैशिंग एल्गोरिथम के समान है |[5] किन्तु कम निर्भरता वाले हैश फलन के उपयोग में भिन्न है | जो इसे और अधिक व्यावहारिक बनाता है। अभी भी सफलता की उच्च संभावना होने के लिए, माध्य चाल का उपयोग माध्य के अतिरिक्त एकाधिक गणना रेखाचित्रों को एकत्र करने के लिए किया जाता है।
ये गुण तंत्रिका नेटवर्क में स्पष्ट कर्नेल विधियों, बिलिनियर पूल (कंप्यूटर विज्ञान) के उपयोग की अनुमति देते हैं और कई संख्यात्मक रैखिक बीजगणित एल्गोरिदम में आधारशिला हैं।[6]
ये गुण तंत्रिका नेटवर्क में स्पष्ट कर्नेल विधियों, बिलिनियर पूल (कंप्यूटर विज्ञान)
गणितीय परिभाषा
1. स्थिरांक और के लिए (बाद में परिभाषित किया जाएगा) स्वतंत्र रूप से यादृच्छिक हैश फ़ंक्शन और चुनें | ऐसा है कि और . यह आवश्यक है कि जिस हैश परिवार से और जोड़ीदार स्वतंत्र चुने जाते हैं।
2. प्रत्येक वस्तु के लिए स्ट्रीम में, जोड़ें तक वें बकेट वें हैश है |
इस प्रक्रिया के अंत में, संस होता है | जहाँ
s की संख्या का अनुमान लगाने के लिए निम्न मान की गणना की जाती है |
मान धारा में कितनी बार प्रकट हुआ है, इसका निष्पक्ष अनुमान है।
अनुमान का प्रसरण , जहां धारा की लंबाई है और है |[7]
इसके अतिरिक्त की प्रायिकता के साथ, वास्तविक मान से से अधिक नहीं होने की गारंटी है |
सदिश सूत्रीकरण
वैकल्पिक रूप से गणना-स्केच को गैर-रैखिक पुनर्निर्माण फलन के साथ रेखीय मानचित्रण के रूप में देखा जा सकता है।
माना , का संग्रह हो आव्यूह, द्वारा परिभाषित है |
के लिए और 0 हर जगह।
फिर एक सदिश को । का पुनर्निर्माण करने के लिए हम लेते हैं। यदि हम और लेते हैं तो यह वही गारंटी देता है | जैसा ऊपर कहा गया है |
टेन्सर स्केच से संबंध
दो सदिशो के बाहरी उत्पाद का गणना स्केच प्रोजेक्शन दो कंपोनेंट गणना स्केच के कनवल्शन के समान है।
गणना स्केच सदिश कनवल्शन की गणना करता है |
, where and are independent count sketch matrices.
फाम और पाघ[8] दिखाएँ कि यह समान है | वैक्टर के बाहरी उत्पाद का गिनती रेखाचित्र , जहाँ क्रोनकर उत्पाद को दर्शाता है।
तेजी से फूरियर रूपांतरण का उपयोग गिनती रेखाचित्रों के तेजी से कनवल्शन करने के लिए किया जा सकता है।
फेस-स्प्लिटिंग उत्पाद का उपयोग करके[9][10][11] ऐसी संरचनाओं की गणना सामान्य आव्यूह की तुलना में बहुत तेजी से की जा सकती है।
यह भी देखें
- गणना-मिन स्केच
- टेन्सरस्केच
संदर्भ
- ↑ 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). "लगभग इष्टतम टेंसर स्केच". ResearchGate. Retrieved 2020-07-11.
- ↑ Charikar, Moses, Kevin Chen, and Martin Farach-Colton. "Finding frequent items in data streams." International Colloquium on Automata, Languages, and Programming. Springer, Berlin, Heidelberg, 2002.
- ↑ Alon, Noga, Yossi Matias, and Mario Szegedy. "The space complexity of approximating the frequency moments." Journal of Computer and system sciences 58.1 (1999): 137-147.
- ↑ Moody, John. "Fast learning in multi-resolution hierarchies." Advances in neural information processing systems. 1989.
- ↑ Woodruff, David P. "Sketching as a Tool for Numerical Linear Algebra." Theoretical Computer Science 10.1-2 (2014): 1–157.
- ↑ Larsen, Kasper Green, Rasmus Pagh, and Jakub Tětek. "CountSketches, Feature Hashing and the Median of Three." International Conference on Machine Learning. PMLR, 2021.
- ↑ Ninh, Pham; Pagh, Rasmus (2013). Fast and scalable polynomial kernels via explicit feature maps. SIGKDD international conference on Knowledge discovery and data mining. Association for Computing Machinery. doi:10.1145/2487575.2487591.
- ↑ Slyusar, V. I. (1998). "रडार अनुप्रयोगों में मेट्रिसेस में अंतिम उत्पाद" (PDF). Radioelectronics and Communications Systems. 41 (3): 50–53.
- ↑ Slyusar, V. I. (1997-05-20). "फेस-स्प्लिटिंग मैट्रिक्स उत्पादों के आधार पर डिजिटल एंटीना सरणी का विश्लेषणात्मक मॉडल।" (PDF). Proc. ICATT-97, Kyiv: 108–109.
- ↑ Slyusar, V. I. (March 13, 1998). "मैट्रिसेस और उसके गुणों के फेस प्रोडक्ट्स का एक परिवार" (PDF). Cybernetics and Systems Analysis C/C of Kibernetika I Sistemnyi Analiz.- 1999. 35 (3): 379–384. doi:10.1007/BF02733426. S2CID 119661450.
अग्रिम पठन
- 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.
