विरल शब्दकोश अधिगम: Difference between revisions

From Vigyanwiki
No edit summary
No edit summary
Line 3: Line 3:
'''विरल शब्दकोश अधिगम''' (जिसे विरल संकेतन या एसडीएल के रूप में भी जाना जाता है) एक प्रतिनिधिता सीखने का तरीका है जिसका उद्देश्य निविष्ट आँकड़े की विरल प्रतिनिधिता की खोज करना होता है, जो मूल तत्वों के रूप में एक रैखिक संयोजन और वे मूल तत्व खुद के रूप में होते हैं। इन तत्वों को परम्परागत रूप से परमाणु कहा जाता है और वे एक शब्दकोश बनाते हैं। शब्दकोश में परमाणुओं को  [[ऑर्थोगोनल आधार|लंबकोणीय आधार]] पर होने की आवश्यकता नहीं होती है, और ये एक अति-पूर्ण विस्तरित आकृति हो सकते हैं। यह समस्या व्यवस्था यह भी अनुमति देता है कि प्रतिनिधित संकेत की आयामिता प्रतिमित संकेत की आयामिता से अधिक हो। उपरोक्त दो गुणों से स्थापित होता है कि ऐसे प्रतिमानु के बनने का कारण लगता है जो एक ही संकेत की विभिन्न प्रतिनिधिताओं की अनुमति देते हैं, लेकिन उन प्रतिनिधिताओं की विरलता और प्रतिनिधिता की लचीलाता में सुधार प्रदान करते हैं।
'''विरल शब्दकोश अधिगम''' (जिसे विरल संकेतन या एसडीएल के रूप में भी जाना जाता है) एक प्रतिनिधिता सीखने का तरीका है जिसका उद्देश्य निविष्ट आँकड़े की विरल प्रतिनिधिता की खोज करना होता है, जो मूल तत्वों के रूप में एक रैखिक संयोजन और वे मूल तत्व खुद के रूप में होते हैं। इन तत्वों को परम्परागत रूप से परमाणु कहा जाता है और वे एक शब्दकोश बनाते हैं। शब्दकोश में परमाणुओं को  [[ऑर्थोगोनल आधार|लंबकोणीय आधार]] पर होने की आवश्यकता नहीं होती है, और ये एक अति-पूर्ण विस्तरित आकृति हो सकते हैं। यह समस्या व्यवस्था यह भी अनुमति देता है कि प्रतिनिधित संकेत की आयामिता प्रतिमित संकेत की आयामिता से अधिक हो। उपरोक्त दो गुणों से स्थापित होता है कि ऐसे प्रतिमानु के बनने का कारण लगता है जो एक ही संकेत की विभिन्न प्रतिनिधिताओं की अनुमति देते हैं, लेकिन उन प्रतिनिधिताओं की विरलता और प्रतिनिधिता की लचीलाता में सुधार प्रदान करते हैं।


विरल शब्दकोश सीखने का सबसे महत्वपूर्ण अनुप्रयोगों में से एक संकुचित अनुभव या  संकेत पुनर्प्राप्ति के क्षेत्र में है। '''संपीड़ित''' संवेदन में, एक उच्च-आयामी संकेत को केवल कुछ रैखिक मापों के साथ पुनर्प्राप्त किया जा सकता है, परंतु संकेत विरल या लगभग विरल हो। चूंकि सभी संकेत इस विरलता की स्थिति को संतुष्ट नहीं करते हैं, इसलिए उस संकेत का विरल प्रतिनिधित्व ढूंढना बहुत महत्वपूर्ण है जैसे [[तरंगिका परिवर्तन]] या रेखापुंज आव्यूह की दिशात्मक ढाल। एक बार जब आव्यूह या उच्च आयामी सदिश को एक विरल स्थान पर स्थानांतरित कर दिया जाता है, तो संकेत को पुनर्प्राप्त करने के लिए आधार खोज, कोसैंप<ref>{{Cite journal|last1=Needell|first1=D.|last2=Tropp|first2=J.A.|title=CoSaMP: Iterative signal recovery from incomplete and inaccurate samples|journal=Applied and Computational Harmonic Analysis|volume=26|issue=3|pages=301–321|doi=10.1016/j.acha.2008.07.002|year=2009|arxiv=0803.2392}}</ref> या तेज़ गैर-पुनरावृत्त कलन विधि<ref>Lotfi, M.; Vidyasagar, M."[[arxiv:1708.03608|A Fast Non-iterative Algorithm for Compressive Sensing Using Binary Measurement Matrices]]"</ref> जैसे विभिन्न पुनर्प्राप्ति कलन विधि का उपयोग किया जा सकता है।
विरल शब्दकोश सीखने का सबसे महत्वपूर्ण अनुप्रयोगों में से एक संकुचित अनुभव या  संकेत पुनर्प्राप्ति के क्षेत्र में है। संक्षिप्त संवेदन में, एक उच्च-आयामी संकेत को कुछ ही रैखिक मापों के साथ पुनर्प्राप्त किया जा सकता है, प्रायः जब संकेत विरल या लगभग विरल हो। यह सत्य है कि सभी संकेत इस विरलता की स्थिति को संतुष्ट नहीं करते हैं, इसलिए उस संकेत की विरल प्रतिनिधि की खोज करना महत्वपूर्ण है, जैसे कि [[तरंगिका परिवर्तन]] या रेखापुंज आव्यूह की दिशात्मक ढाल। एक बार जब किसी आव्यूह या उच्च आयामी सदिश को विरल स्थान पर स्थानांतरित किया जाता है, विभिन्न पुनर्प्राप्ति कलन विधि जैसे कि आधार अनुसरण, कोसैंप<ref>{{Cite journal|last1=Needell|first1=D.|last2=Tropp|first2=J.A.|title=CoSaMP: Iterative signal recovery from incomplete and inaccurate samples|journal=Applied and Computational Harmonic Analysis|volume=26|issue=3|pages=301–321|doi=10.1016/j.acha.2008.07.002|year=2009|arxiv=0803.2392}}</ref> या त्वरित गैर-आवर्ती कलन विधि<ref>Lotfi, M.; Vidyasagar, M."[[arxiv:1708.03608|A Fast Non-iterative Algorithm for Compressive Sensing Using Binary Measurement Matrices]]"</ref> का उपयोग संकेत को पुनर्प्राप्त करने के लिए किया जा सकता है।


शब्दकोश सीखने का एक प्रमुख सिद्धांत यह है कि शब्दकोश का अनुमान  निविष्ट आँकड़ा से लगाया जाना चाहिए। विरल शब्दकोश सीखने के तरीकों का उद्भव इस तथ्य से प्रेरित था कि [[ संकेत आगे बढ़ाना |संकेत संसाधन]] में कोई सामान्यता यथासंभव कम घटकों का उपयोग करके निविष्ट आँकड़ा का प्रतिनिधित्व करना चाहता है। इस दृष्टिकोण से पहले सामान्य अभ्यास पूर्वनिर्धारित शब्दकोशों (जैसे फूरियर या तरंगिका रूपांतरण ) का उपयोग करना था। हालाँकि, कुछ उदाहरण में एक शब्दकोश जिसे निविष्ट आँकड़ा को उपयुक्त करने के लिए प्रशिक्षित किया जाता है, विरलता में बहुत सुधार कर सकता है, जिसमें आँकड़े अपघटन, संपीड़न और विश्लेषण में अनुप्रयोग होते हैं और इसका उपयोग [[छवि]] निरूपण और वर्गीकरण, [[वीडियो]] और श्रव्य प्रसंस्करण के क्षेत्र में किया गया है। विरलता और अतिपूर्ण शब्दकोशों का छवि संपीड़न, छवि संलयन और चित्रकारी में व्यापक अनुप्रयोग है।
शब्दकोश सीखने के एक मुख्य सिद्धांतों में से एक यह है कि शब्दकोश को निविष्ट आँकड़ा से निष्कर्षित किया जाना चाहिए। विरल शब्दकोश सीखने के तरीकों के उद्भव इस तथ्य से प्रेरित था कि [[ संकेत आगे बढ़ाना |संकेत संसाधन]] में कोई सामान्यता यथासंभव कम घटकों का उपयोग करके निविष्ट आँकड़ा का प्रतिनिधित्व करना चाहता है। इस दृष्टिकोण से पहले सामान्य अभ्यास पूर्वनिर्धारित शब्दकोशों का उपयोग किया जाता था (जैसे फूरियर या तरंगिका रूपांतरण )हालाँकि, कुछ उदाहरण में एक ऐसा शब्दकोश जो निविष्ट आँकड़ा के अनुसार प्रशिक्षित होता है, विरलता में बहुत सुधार कर सकता है, जिसमें आँकड़े अपघटन, संकुचन और विश्लेषण में उपयोग होता हैं और इसका उपयोग [[छवि]] निरूपण और वर्गीकरण, [[वीडियो]] और श्रव्य प्रसंस्करण के क्षेत्रों में उपयोग किया गया है। विरलता और अतिपूर्ण शब्दकोशों का छवि संकुचन, छवि संयोजन और चित्रकारी में विशिष्ट अनुप्रयोग होते हैं।
   [[File:Dic_learning.jpg|thumb|शब्दकोष अधिगम द्वारा प्रतिरूप डीनोइज़िंग]]
   [[File:Dic_learning.jpg|thumb|शब्दकोष अधिगम द्वारा प्रतिरूप डीनोइज़िंग]]


== समस्या कथन ==
== समस्या कथन ==
निविष्ट आँकड़ा समुच्चय दिया गया <math>X = [x_1, ..., x_K], x_i \in \mathbb{R}^d</math> हम एक शब्दकोश खोजना चाहते हैं <math>\mathbf{D} \in \mathbb{R}^{d \times n}: D = [d_1, ..., d_n]</math> और एक प्रतिनिधित्व <math>R = [r_1,...,r_K], r_i \in \mathbb{R}^n</math> ऐसे कि दोनों <math>\|X-\mathbf{D}R\|^2_F</math> कम से कम किया गया है और प्रतिनिधित्व <math>r_i</math> अति विरल हैं. इसे निम्नलिखित [[अनुकूलन समस्या]] के रूप में तैयार किया जा सकता है:
दिए गए निविष्ट आँकड़ा समुच्चय <math>X = [x_1, ..., x_K], x_i \in \mathbb{R}^d</math> है,हमें एक शब्दकोश ढूंढना चाहिए <math>\mathbf{D} \in \mathbb{R}^{d \times n}: D = [d_1, ..., d_n]</math> और एक प्रतिनिधिता <math>R = [r_1,...,r_K], r_i \in \mathbb{R}^n</math> की आवश्यकता है, जिसके साथ दोनों <math>\|X-\mathbf{D}R\|^2_F</math> को कम किया जा सकता है और प्रतिनिधिताएँ <math>r_i</math> अति विरल होती हैं। यह निम्नलिखित [[अनुकूलन समस्या]] के रूप में सूचित किया जा सकता है:


<math>\underset{\mathbf{D} \in \mathcal{C}, r_i \in \mathbb{R}^n}{\text{argmin}} \sum_{i=1}^K\|x_i-\mathbf{D}r_i\|_2^2+\lambda \|r_i\|_0</math>, कहाँ <math>\mathcal{C} \equiv \{\mathbf{D} \in \mathbb{R}^{d \times n}: \|d_i\|_2 \leq 1 \,\, \forall i =1,...,n \}</math>, <math>\lambda>0</math>
<math>\underset{\mathbf{D} \in \mathcal{C}, r_i \in \mathbb{R}^n}{\text{argmin}} \sum_{i=1}^K\|x_i-\mathbf{D}r_i\|_2^2+\lambda \|r_i\|_0</math>, कहाँ <math>\mathcal{C} \equiv \{\mathbf{D} \in \mathbb{R}^{d \times n}: \|d_i\|_2 \leq 1 \,\, \forall i =1,...,n \}</math>, <math>\lambda>0</math>


<math>\mathcal{C}</math> अंकुश लगाना आवश्यक है <math>\mathbf{D}</math> ताकि इसके परमाणु मनमाने ढंग से कम (लेकिन गैर-शून्य) मूल्यों की अनुमति देकर मनमाने ढंग से उच्च मूल्यों तक न पहुंचें <math>r_i</math>.<math>\lambda</math> विरलता और न्यूनीकरण त्रुटि के बीच व्यापार को नियंत्रित करता है।
संकेत दीवारण <math>\mathcal{C}</math> की आवश्यकता होती है <math>\mathbf{D}</math> ताकि वे अणु स्वेच्छाचारी उच्च मानों तक न पहुँच सकें, जिससे कि वे स्वेच्छाचारी कम मानों (लेकिन गैर-शून्य) की अनुमति दें, जैसे कि <math>r_i</math>.<math>\lambda</math> विरलता और न्यूनतमीकरण त्रुटि के बीच संघटन के निर्धारण को नियंत्रित करता है।


उपरोक्त न्यूनतमकरण समस्या ℓ<sub>0</sub> "मानदंड" के कारण उत्तल नहीं है और इस समस्या को हल करना एनपी-दृढ़ है।<ref>A. M. Tillmann, "[[doi:10.1109/LSP.2014.2345761|On the Computational Intractability of Exact and Approximate Dictionary Learning]]", IEEE Signal Processing Letters 22(1), 2015: 45–49.</ref> कुछ मामलों में ''L''<sup>1</sup>-मानदंड विरलता सुनिश्चित करने के लिए जाना जाता है<ref>{{Cite journal|title = For most large underdetermined systems of linear equations the minimal 𝓁1-norm solution is also the sparsest solution|journal = Communications on Pure and Applied Mathematics|date = 2006-06-01|issn = 1097-0312|pages = 797–829|volume = 59|issue = 6|doi = 10.1002/cpa.20132|first = David L.|last = Donoho| s2cid=8510060 }}</ref> और इसलिए उपरोक्त प्रत्येक चर के संबंध में एक [[उत्तल अनुकूलन]] समस्या बन जाती है <math>\mathbf{D}</math> और <math>\mathbf{R}</math> जब दूसरा स्थिर हो, लेकिन यह संयुक्त रूप से उत्तल नहीं होता है <math>(\mathbf{D}, \mathbf{R})</math>.
उपरोक्त न्यूनतमकरण समस्या ℓ<sub>0</sub> "मानदंड" के कारण उत्तल नहीं है और इस समस्या को हल करना एनपी-दृढ़ है।<ref>A. M. Tillmann, "[[doi:10.1109/LSP.2014.2345761|On the Computational Intractability of Exact and Approximate Dictionary Learning]]", IEEE Signal Processing Letters 22(1), 2015: 45–49.</ref> कुछ मामलों में ''L''<sup>1</sup>-मानदंड विरलता सुनिश्चित करने के लिए जाना जाता है<ref>{{Cite journal|title = For most large underdetermined systems of linear equations the minimal 𝓁1-norm solution is also the sparsest solution|journal = Communications on Pure and Applied Mathematics|date = 2006-06-01|issn = 1097-0312|pages = 797–829|volume = 59|issue = 6|doi = 10.1002/cpa.20132|first = David L.|last = Donoho| s2cid=8510060 }}</ref> और इसलिए उपरोक्त प्रत्येक चर के संबंध में एक [[उत्तल अनुकूलन]] समस्या बन जाती है <math>\mathbf{D}</math> और <math>\mathbf{R}</math> जब दूसरा स्थिर हो, लेकिन यह संयुक्त रूप से उत्तल नहीं होता है <math>(\mathbf{D}, \mathbf{R})</math>.


===शब्दकोश के गुण ===
===शब्दकोश के गुण ===
शब्दकोष <math>\mathbf{D}</math> ऊपर परिभाषित "अपूर्ण" हो सकता है यदि <math>n < d</math> या स्थिति में "अपूर्ण" <math>n>d</math> उत्तरार्द्ध एक विरल शब्दकोश सीखने की समस्या के लिए एक विशिष्ट धारणा है। संपूर्ण शब्दकोश की स्थिति प्रतिनिधित्वात्मक दृष्टिकोण से कोई सुधार प्रदान नहीं करता है और इसलिए इस पर विचार नहीं किया जाता है।
उपर वर्णित शब्दकोश <math>\mathbf{D}</math> "अपूर्ण" हो सकता है यदि <math>n < d</math> या स्थिति में "अपूर्ण" <math>n>d</math> उत्तरार्द्ध एक विरल शब्दकोश सीखने की समस्या के लिए एक विशिष्ट धारणा है। संपूर्ण शब्दकोश की स्थिति प्रतिनिधानिक दृष्टिकोण से कोई सुधार प्रदान नहीं करता है और इसलिए इसलिए इसे विचार में नहीं लिया जाता है।


अपूर्ण शब्दकोश उस व्यवस्था का प्रतिनिधित्व करते हैं जिसमें वास्तविक निविष्ट आँकड़ा निम्न-आयामी स्थान में होता है। यह स्थिति [[आयामीता में कमी]] और प्रमुख घटक विश्लेषण जैसी तकनीकों से दृढ़ता से संबंधित है जिसके लिए परमाणुओं की आवश्यकता होती है <math>d_1,...,d_n</math>  लंबकोणीय होना। कुशल आयामीता में कमी के लिए इन उप-स्थानों का चुनाव महत्वपूर्ण है, लेकिन यह साधारण नहीं है। और शब्दकोश प्रतिनिधित्व के आधार पर आयामीता में कमी को आंकड़े विश्लेषण या वर्गीकरण जैसे विशिष्ट कार्यों को संबोधित करने के लिए बढ़ाया जा सकता है। हालाँकि, उनका मुख्य नकारात्मक पक्ष परमाणुओं की पसंद को सीमित करना है।
अपूर्ण शब्दकोश उस व्यवस्था को प्रतिनिधित करते हैं जिसमें वास्तविक निविष्ट आँकड़ा का अवस्थित होता है एक निम्न-आयामी स्थान में। यह स्थिति [[आयामीता में कमी|आयामीता घटन]] और प्रमुख घटक विश्लेषण जैसी तकनीकों से दृढ़ता रूप से संबंधित होता है जोकि अणु <math>d_1,...,d_n</math>  को लंबकोणीय होने की आवश्यकता होती है। इन उपशवकों की चयन सरल नहीं होता, लेकिन कुशल आयामी घटन के लिए महत्वपूर्ण होता है। और शब्दकोश प्रतिनिधिता पर आधारित आयामी घटन को आंकड़े विश्लेषण या वर्गीकरण जैसे विशिष्ट कार्यों को को पता करने के लिए विस्तारित किया जा सकता है। हालाँकि, उनका मुख्य दुष्प्रभाव अणु की चयन की सीमा होती है।


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


एक पूर्ण शब्दकोश जो संकेत के विरल प्रतिनिधित्व की अनुमति देता है वह एक प्रसिद्ध रूपांतर आव्यूह(तरंगिका रूपांतर, फूरियर रूपांतर) हो सकता है या इसे तैयार किया जा सकता है ताकि इसके तत्वों को इस तरह से बदला जा सके कि यह दिए गए संकेत को सबसे अच्छे तरीके से प्रस्तुत करता है। सीखे गए शब्दकोष पूर्वनिर्धारित परिवर्तन आव्यूह की तुलना में विरल समाधान देने में सक्षम हैं।
एक पूर्ण संघट शब्दकोश जिसमें संकेत की विरल प्रतिनिधि होने की अनुमति होती है, एक प्रसिद्ध परिवर्तन आव्यूह(तरंगिका रूपांतर, फूरियर रूपांतर) हो सकता है या ऐसा सूत्र बनाया जा सकता है जिससे कि उसके तत्व ऐसे बदल जाते हैं कि वह दिए गए संकेत को श्रेष्ठ तरीके से विरल रूप में प्रतिनिधित करें। सीखे गए शब्दकोष पूर्वनिर्धारित परिवर्तन आव्यूह की तुलना में विरल समाधान प्रदान करने की क्षमता रखते हैं।


== कलन विधि ==
== कलन विधि ==

Revision as of 18:21, 9 August 2023

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

विरल शब्दकोश सीखने का सबसे महत्वपूर्ण अनुप्रयोगों में से एक संकुचित अनुभव या संकेत पुनर्प्राप्ति के क्षेत्र में है। संक्षिप्त संवेदन में, एक उच्च-आयामी संकेत को कुछ ही रैखिक मापों के साथ पुनर्प्राप्त किया जा सकता है, प्रायः जब संकेत विरल या लगभग विरल हो। यह सत्य है कि सभी संकेत इस विरलता की स्थिति को संतुष्ट नहीं करते हैं, इसलिए उस संकेत की विरल प्रतिनिधि की खोज करना महत्वपूर्ण है, जैसे कि तरंगिका परिवर्तन या रेखापुंज आव्यूह की दिशात्मक ढाल। एक बार जब किसी आव्यूह या उच्च आयामी सदिश को विरल स्थान पर स्थानांतरित किया जाता है, विभिन्न पुनर्प्राप्ति कलन विधि जैसे कि आधार अनुसरण, कोसैंप[1] या त्वरित गैर-आवर्ती कलन विधि[2] का उपयोग संकेत को पुनर्प्राप्त करने के लिए किया जा सकता है।

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

शब्दकोष अधिगम द्वारा प्रतिरूप डीनोइज़िंग

समस्या कथन

दिए गए निविष्ट आँकड़ा समुच्चय है,हमें एक शब्दकोश ढूंढना चाहिए और एक प्रतिनिधिता की आवश्यकता है, जिसके साथ दोनों को कम किया जा सकता है और प्रतिनिधिताएँ अति विरल होती हैं। यह निम्नलिखित अनुकूलन समस्या के रूप में सूचित किया जा सकता है:

, कहाँ ,

संकेत दीवारण की आवश्यकता होती है ताकि वे अणु स्वेच्छाचारी उच्च मानों तक न पहुँच सकें, जिससे कि वे स्वेच्छाचारी कम मानों (लेकिन गैर-शून्य) की अनुमति दें, जैसे कि . विरलता और न्यूनतमीकरण त्रुटि के बीच संघटन के निर्धारण को नियंत्रित करता है।

उपरोक्त न्यूनतमकरण समस्या ℓ0 "मानदंड" के कारण उत्तल नहीं है और इस समस्या को हल करना एनपी-दृढ़ है।[3] कुछ मामलों में L1-मानदंड विरलता सुनिश्चित करने के लिए जाना जाता है[4] और इसलिए उपरोक्त प्रत्येक चर के संबंध में एक उत्तल अनुकूलन समस्या बन जाती है और जब दूसरा स्थिर हो, लेकिन यह संयुक्त रूप से उत्तल नहीं होता है .

शब्दकोश के गुण

उपर वर्णित शब्दकोश "अपूर्ण" हो सकता है यदि या स्थिति में "अपूर्ण" उत्तरार्द्ध एक विरल शब्दकोश सीखने की समस्या के लिए एक विशिष्ट धारणा है। संपूर्ण शब्दकोश की स्थिति प्रतिनिधानिक दृष्टिकोण से कोई सुधार प्रदान नहीं करता है और इसलिए इसलिए इसे विचार में नहीं लिया जाता है।

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

विपरीत संघट शब्दकोश, हालांकि, अणु को लंबकोणीय होने की आवश्यकता नहीं होती है (वे कभी भी एक आधार (रैखिक बीजगणित) नहीं होते हैं) इसलिए अधिक लचीले शब्दकोशों और समृद्ध आंकड़े प्रतिनिधिता की अनुमति देते है।

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

कलन विधि

जैसा कि ऊपर वर्णित अनुकूलन समस्या को शब्दकोश या विरल कूटलेखन के संबंध में उत्तल समस्या के रूप में हल किया जा सकता है, जबकि दोनों में से एक को ठीक किया गया है, अधिकांश कलन विधि एक और फिर दूसरे को पुनरावृत्त रूप से अद्यतनीकरण करने के विचार पर आधारित हैं।

इष्टतम विरल कूटलेखन खोजने की समस्या किसी दिए गए शब्दकोश के साथ को विरल सन्निकटन (या कभी-कभी केवल विरल कूटलेखन समस्या) के रूप में जाना जाता है। इसे हल करने के लिए कई कलन विधि विकसित किए गए हैं (जैसे मिलान खोज और लैस्सो (सांख्यिकी)) और नीचे वर्णित कलन विधि में सम्मिलित किए गए हैं।

इष्टतम दिशाओं की विधि (एमओडी)

इष्टतम दिशाओं की विधि (या एमओडी) विरल शब्दकोश सीखने की समस्या से निपटने के लिए शुरू की गई पहली विधियों में से एक थी।[5] इसका मूल विचार प्रतिनिधित्व सदिश के गैर-शून्य घटकों की सीमित संख्या के अधीन न्यूनतमकरण समस्या को हल करना है:

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

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

के-एसवीडी

के-एसवीडी एक कलन विधि है जो शब्दकोश के परमाणुओं को एक-एक करके अद्यतन करने के लिए अपने मूल में एसवीडी करता और मूल रूप से K- साधनो का सामान्यीकरण है। यह लागू करता है कि निविष्ट आँकड़ा का प्रत्येक तत्व से अधिक नहीं के रैखिक संयोजन द्वारा कूटलेखन किया गया है तत्व एक तरह से आधुनिक दृष्टिकोण के समान हैं:

इस कलन विधि का सार सबसे पहले शब्दकोश को ठीक करना, सर्वोत्तम संभव खोजना है उपरोक्त बाधा के तहत (लंबकोणीय मिलान अनुसरण का उपयोग करके) और फिर शब्दकोश के परमाणुओं को पुनरावृत्त रूप से अद्यतन करें निम्नलिखित तरीके से:

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

प्रसंभाव्य प्रवणता अवरोहण

इस समस्या को हल करने के लिए कोई व्यक्ति पुनरावृत्ती प्रक्षेपण के साथ व्यापक प्रसंभाव्य प्रवणता अवरोहण विधि भी लागू कर सकता है।[6][7] इस पद्धति का विचार पहले क्रम के प्रसंभाव्य प्रवणता का उपयोग करके शब्दकोश को अद्यतन करना और इसे बाधा समुच्चय पर परियोजना करना है . i-वें पुनरावृत्ति पर होने वाला चरण इस अभिव्यक्ति द्वारा वर्णित है:

, कहाँ का एक यादृच्छिक उपसमुच्चय है और एक क्रमिक कदम है.

लैग्रेंज दोहरी विधि

दोहरी लैग्रेन्जियन समस्या को हल करने पर आधारित एक कलन विधि शब्दकोश के लिए हल करने का एक कुशल तरीका प्रदान करता है जिसमें विरलता फलन से प्रेरित कोई जटिलता नहीं होती है।[8] निम्नलिखित लैग्रेंजियन पर विचार करें:

, कहाँ परमाणुओं के मानदंड पर एक बाधा है और विकर्ण आव्यूह बनाने वाले तथाकथित दोहरे चर हैं .

न्यूनतमकरण के बाद हम लैग्रेंज दोहरे के लिए एक विश्लेषणात्मक अभिव्यक्ति प्रदान कर सकते हैं :

.

अनुकूलन विधियों में से एक को दोहरे के मूल्य पर लागू करने के बाद (जैसे कि न्यूटन की विधि या संयुग्म प्रवणता) हमें इसका मूल्य मिलता है :

दोहरे चर की मात्रा के कारण इस समस्या को हल करना कम अभिकलनात्मक कठिन है प्रारंभिक समस्या में चरों की मात्रा से कई गुना कम है।

लैसो

इस दृष्टिकोण में, अनुकूलन समस्या इस प्रकार तैयार की गई है:

, कहाँ LASSO के पुनर्निर्माण में अनुमत त्रुटि है।

इसका एक अनुमान मिलता है समाधान सदिश में L1-मानदंड बाधा के अधीन न्यूनतम वर्ग त्रुटि को न्यूनतम करके, इस प्रकार तैयार किया गया है:

, कहाँ विरलता और पुनर्निर्माण त्रुटि के बीच व्यापार-बंद को नियंत्रित करता है। यह वैश्विक इष्टतम समाधान देता है।[9] विरल कूटलेखन के लिए लाइन – आरुढ़ शब्दकोश अधिगम भी देखें

प्राचलिक प्रशिक्षण विधियाँ

प्राचलिक प्रशिक्षण विधियों का उद्देश्य दोनों दुनियाओं के सर्वश्रेष्ठ को सम्मिलित करना है - विश्लेषणात्मक रूप से निर्मित शब्दकोशों और सीखे गए शब्दकोशों का क्षेत्र।[10] यह अधिक शक्तिशाली सामान्यीकृत शब्दकोशों के निर्माण की अनुमति देता है जिन्हें संभावित रूप से मनमाने आकार के संकेतों के स्थितियो पर लागू किया जा सकता है। उल्लेखनीय दृष्टिकोणों में सम्मिलित हैं:

  • अनुवाद-अपरिवर्तनीय शब्दकोश।[11] ये शब्दकोष परिमित आकार के संकेत यथेच्छ के लिए निर्मित शब्दकोष से उत्पन्न परमाणुओं के अनुवादों से बने हैं। यह परिणामी शब्दकोश को मनमाने आकार के संकेत के लिए एक प्रतिनिधित्व प्रदान करने की अनुमति देता है।
  • बहुस्तरीय शब्दकोश।[12] यह विधि एक ऐसे शब्दकोश के निर्माण पर केंद्रित है जो विरलता में सुधार के लिए अलग-अलग पैमाने के शब्दकोशों से बना है।
  • विरल शब्दकोश।[13] यह विधि न केवल विरल प्रतिनिधित्व प्रदान करने पर केंद्रित है बल्कि एक विरल शब्दकोश का निर्माण भी करती है जिसे अभिव्यक्ति द्वारा लागू किया जाता है जहाँ कुछ पूर्व-परिभाषित विश्लेषणात्मक शब्दकोष है जिसमें वांछनीय गुण हैं जैसे तेज़ गणना और एक विरल आव्यूह है। इस तरह का सूत्रीकरण विरल दृष्टिकोणों के लचीलेपन के साथ विश्लेषणात्मक शब्दकोशों के तेजी से कार्यान्वयन को सीधे संयोजित करने की अनुमति देता है।

लाइन – आरुढ़ शब्दकोश अधिगम (LASSO दृष्टिकोण)

विरल शब्दकोश सीखने के कई सामान्य दृष्टिकोण इस तथ्य पर निर्भर करते हैं कि संपूर्ण निविष्ट आँकड़ा कलन विधि के लिए (या कम से कम एक बड़ा पर्याप्त प्रशिक्षण आंकड़ा समुच्चय) उपलब्ध है। हालाँकि, वास्तविक दुनिया के परिदृश्य में ऐसा नहीं हो सकता है क्योंकि निविष्ट आँकड़ा का आकार इसे स्मृतिमें उपयुक्त करने के लिए बहुत बड़ा हो सकता है। दूसरी स्थिति जहां यह धारणा नहीं बनाई जा सकती वह तब है जब निविष्ट आँकड़ा एक वर्ग के रूप में आता है। ऐसे मामले लाइन – आरुढ़ शिक्षण के अध्ययन के क्षेत्र में हैं जो अनिवार्य रूप से नए आँकड़े बिंदुओं पर निदर्श को पुनरावृत्त रूप से अद्यतन करने का सुझाव देता है उपलब्ध हो रहा है।

एक शब्दकोश को लाइन – आरुढ़ तरीके से निम्नलिखित तरीके से सीखा जा सकता है:[14]

  1. के लिए
  2. एक नया प्रतिरूप बनाएं
  3. न्यूनतम-कोण प्रतिगमन का उपयोग करके एक विरल कूटलेखन ढूंढें:
  4. खण्डक समन्वय दृष्टिकोण का उपयोग करके शब्दकोश अद्यतन करें:

यह विधि हमें धीरे-धीरे शब्दकोश को अद्यतन करने की अनुमति देती है क्योंकि नया आँकड़े विरल प्रतिनिधित्व सीखने के लिए उपलब्ध हो जाता है और आंकड़ा समुच्चय(जिसका आकार अधिकतर बड़ा होता है) को संग्रहीत करने के लिए आवश्यक स्मृति की मात्रा को बहुत कम करने में मदद करता है।

अनुप्रयोग

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

इसमें ऐसे गुण भी हैं जो संकेत को दर्शाने के लिए उपयोगी हैं क्योंकि सामान्यता कोई निविष्ट संकेत के सार्थक भाग को विरल तरीके से प्रस्तुत करने के लिए एक शब्दकोश सीख सकता है लेकिन निविष्ट में रव का विरल प्रतिनिधित्व बहुत कम होगा।[15]

विरल शब्दकोश शिक्षण को विभिन्न छवि, वीडियो और श्रव्य प्रसंस्करण कार्यों के साथ-साथ बनावट संश्लेषण [16] और अनपर्यवेक्षित गुच्छन पर सफलतापूर्वक लागू किया गया है।।[17] बैग- का- शब्द निदर्श के साथ मूल्यांकन में,[18][19] उद्देश्य श्रेणी पहचान कार्यों पर अन्य कूटलेखन दृष्टिकोणों से बेहतर प्रदर्शन करने के लिए विरल कूटलेखन को अनुभवजन्य रूप से पाया गया था।

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

यह भी देखें

संदर्भ

  1. Needell, D.; Tropp, J.A. (2009). "CoSaMP: Iterative signal recovery from incomplete and inaccurate samples". Applied and Computational Harmonic Analysis. 26 (3): 301–321. arXiv:0803.2392. doi:10.1016/j.acha.2008.07.002.
  2. Lotfi, M.; Vidyasagar, M."A Fast Non-iterative Algorithm for Compressive Sensing Using Binary Measurement Matrices"
  3. A. M. Tillmann, "On the Computational Intractability of Exact and Approximate Dictionary Learning", IEEE Signal Processing Letters 22(1), 2015: 45–49.
  4. Donoho, David L. (2006-06-01). "For most large underdetermined systems of linear equations the minimal 𝓁1-norm solution is also the sparsest solution". Communications on Pure and Applied Mathematics. 59 (6): 797–829. doi:10.1002/cpa.20132. ISSN 1097-0312. S2CID 8510060.
  5. Engan, K.; Aase, S.O.; Hakon Husoy, J. (1999-01-01). "Method of optimal directions for frame design". 1999 IEEE International Conference on Acoustics, Speech, and Signal Processing. Proceedings. ICASSP99 (Cat. No.99CH36258). Vol. 5. pp. 2443–2446 vol.5. doi:10.1109/ICASSP.1999.760624. ISBN 978-0-7803-5041-0. S2CID 33097614.
  6. Aharon, Michal; Elad, Michael (2008). "छवि-हस्ताक्षर-शब्दकोश का उपयोग करके छवि सामग्री की विरल और निरर्थक मॉडलिंग". SIAM Journal on Imaging Sciences. 1 (3): 228–247. CiteSeerX 10.1.1.298.6982. doi:10.1137/07070156x.
  7. Pintér, János D. (2000-01-01). Yair Censor and Stavros A. Zenios, Parallel Optimization — Theory, Algorithms, and Applications. Oxford University Press, New York/Oxford, 1997, xxviii+539 pages. (US $ 85.00). pp. 107–108. doi:10.1023/A:1008311628080. ISBN 978-0-19-510062-4. ISSN 0925-5001. S2CID 22475558. {{cite book}}: |journal= ignored (help)
  8. Lee, Honglak, et al. "Efficient sparse coding algorithms." Advances in neural information processing systems. 2006.
  9. Kumar, Abhay; Kataria, Saurabh. "उत्तल अनुकूलन का उपयोग करके छवि प्रसंस्करण में शब्दकोश शिक्षण आधारित अनुप्रयोग" (PDF).
  10. Rubinstein, R.; Bruckstein, A.M.; Elad, M. (2010-06-01). "विरल प्रतिनिधित्व मॉडलिंग के लिए शब्दकोश". Proceedings of the IEEE. 98 (6): 1045–1057. CiteSeerX 10.1.1.160.527. doi:10.1109/JPROC.2010.2040551. ISSN 0018-9219. S2CID 2176046.
  11. Engan, Kjersti; Skretting, Karl; Husøy, John H\a akon (2007-01-01). "विरल सिग्नल प्रतिनिधित्व के लिए इटरेटिव एलएस-आधारित डिक्शनरी लर्निंग एल्गोरिदम का परिवार, आईएलएस-डीएलए". Digit. Signal Process. 17 (1): 32–49. doi:10.1016/j.dsp.2006.02.002. ISSN 1051-2004.
  12. Mairal, J.; Sapiro, G.; Elad, M. (2008-01-01). "छवि और वीडियो पुनर्स्थापन के लिए मल्टीस्केल विरल अभ्यावेदन सीखना". Multiscale Modeling & Simulation. 7 (1): 214–241. CiteSeerX 10.1.1.95.6239. doi:10.1137/070697653. ISSN 1540-3459.
  13. Rubinstein, R.; Zibulevsky, M.; Elad, M. (2010-03-01). "Double Sparsity: Learning Sparse Dictionaries for Sparse Signal Approximation". IEEE Transactions on Signal Processing. 58 (3): 1553–1564. Bibcode:2010ITSP...58.1553R. CiteSeerX 10.1.1.183.992. doi:10.1109/TSP.2009.2036477. ISSN 1053-587X. S2CID 7193037.
  14. Mairal, Julien; Bach, Francis; Ponce, Jean; Sapiro, Guillermo (2010-03-01). "मैट्रिक्स फ़ैक्टराइज़ेशन और विरल कोडिंग के लिए ऑनलाइन शिक्षण". J. Mach. Learn. Res. 11: 19–60. arXiv:0908.0050. Bibcode:2009arXiv0908.0050M. ISSN 1532-4435.
  15. Aharon, M, M Elad, and A Bruckstein. 2006. "K-SVD: An Algorithm for Designing Overcomplete Dictionaries for Sparse Representation." Signal Processing, IEEE Transactions on 54 (11): 4311-4322
  16. Peyré, Gabriel (2008-11-06). "बनावट की विरल मॉडलिंग" (PDF). Journal of Mathematical Imaging and Vision. 34 (1): 17–31. doi:10.1007/s10851-008-0120-3. ISSN 0924-9907. S2CID 15994546.
  17. Ramirez, Ignacio; Sprechmann, Pablo; Sapiro, Guillermo (2010-01-01). "Classification and clustering via dictionary learning with structured incoherence and shared features". 2010 IEEE Computer Society Conference on Computer Vision and Pattern Recognition. Los Alamitos, CA, USA: IEEE Computer Society. pp. 3501–3508. doi:10.1109/CVPR.2010.5539964. ISBN 978-1-4244-6984-0. S2CID 206591234.
  18. Koniusz, Piotr; Yan, Fei; Mikolajczyk, Krystian (2013-05-01). "विज़ुअल कॉन्सेप्ट डिटेक्शन में मध्य-स्तरीय फीचर कोडिंग दृष्टिकोण और पूलिंग रणनीतियों की तुलना". Computer Vision and Image Understanding. 117 (5): 479–492. CiteSeerX 10.1.1.377.3979. doi:10.1016/j.cviu.2012.10.010. ISSN 1077-3142.
  19. Koniusz, Piotr; Yan, Fei; Gosselin, Philippe Henri; Mikolajczyk, Krystian (2017-02-24). "Higher-order occurrence pooling for bags-of-words: Visual concept detection" (PDF). IEEE Transactions on Pattern Analysis and Machine Intelligence. 39 (2): 313–326. doi:10.1109/TPAMI.2016.2545667. hdl:10044/1/39814. ISSN 0162-8828. PMID 27019477.
  20. AlMatouq, Ali; LalegKirati, TaousMeriem; Novara, Carlo; Ivana, Rabbone; Vincent, Tyrone (2019-03-15). "सतत ग्लूकोज मॉनिटर्स का उपयोग करके ग्लूकोज फ्लक्स का विरल पुनर्निर्माण". IEEE/ACM Transactions on Computational Biology and Bioinformatics. 17 (5): 1797–1809. doi:10.1109/TCBB.2019.2905198. hdl:10754/655914. ISSN 1545-5963. PMID 30892232. S2CID 84185121.