के-एसवीडी

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

के-एसवीडी एल्गोरिदम

के-एसवीडी, के-साधनों का विशेष प्रकार का सामान्यीकरण होता है, जो इस प्रकार है।

के-मीन्स क्लस्टरिंग को विरल प्रतिनिधित्व की विधि के रूप में भी माना जा सकता है। अर्थात्, डेटा नमूनों का प्रतिनिधित्व करने के लिए सर्वोत्तम संभव कोडबुक खोजना $\{y_{i}\}_{i=1}^{M}$ निकटतम खोज द्वारा, हल करके

$\quad \min \limits _{D,X}\{\|Y-DX\|_{F}^{2}\}\qquad {\text{subject to }}\forall i,x_{i}=e_{k}{\text{ for some }}k.$

जो लगभग सामान्तर होते है

$\quad \min \limits _{D,X}\{\|Y-DX\|_{F}^{2}\}\qquad {\text{subject to }}\quad \forall i,\|x_{i}\|_{0}=1$

जो कि के-मीन्स होता है जो "वज़न" की अनुमति देता है।

अक्षर एफ फ्रोबेनियस मानदंड को दर्शाता है। इस प्रकार विरल प्रतिनिधित्व शब्द $x_{i}=e_{k}$ शब्दकोश में केवल परमाणु (स्तंभ) का उपयोग करने के लिए के-मीन्स एल्गोरिदम $D$ क्रियान्वित करता है। इस बाधा को कम करने के लिए, के-एसवीडी एल्गोरिदम $D$ का लक्ष्य सिग्नल को परमाणुओं के रैखिक संयोजन के रूप में प्रस्तुत करना है।

के-एसवीडी एल्गोरिदम के-मीन्स एल्गोरिदम के निर्माण प्रवाह का अनुसरण करता है। चूँकि, के-साधनों के विपरीत, परमाणुओं के रैखिक संयोजन को प्राप्त करने के लिए $D$, बाधा के विरल पद को शिथिल कर दिया गया है जिससे कि प्रत्येक स्तंभ की गैर-शून्य प्रविष्टियों की संख्या $x_{i}$ 1 से अधिक होती है, किन्तु संख्या $T_{0}$ से कम हो सकता है।

तब, वस्तुनिष्ठ फलन बन जाता है।

$\quad \min \limits _{D,X}\{\|Y-DX\|_{F}^{2}\}\qquad {\text{subject to }}\quad \forall i\;,\|x_{i}\|_{0}\leq T_{0}.$

या किसी अन्य वस्तुनिष्ठ रूप में

$\quad \min \limits _{D,X}\sum _{i}\|x_{i}\|_{0}\qquad {\text{subject to }}\quad \forall i\;,\|Y-DX\|_{F}^{2}\leq \epsilon .$

के-एसवीडी एल्गोरिथम में, $D$ पहला निश्चित और सर्वोत्तम गुणांक आव्युह होता है, जिसमे $X$ पाया जाता है। वास्तव में इष्टतम खोजने के रूप में $X$ कठिन होता है, अतः हम सन्निकटन खोज पद्धति का उपयोग करते हैं। इस प्रकार ओएमपी जैसे किसी भी एल्गोरिदम, ऑर्थोगोनल मिलान खोज का उपयोग गुणांक की गणना के लिए किया जा सकता है, जब तक कि यह गैर-शून्य प्रविष्टियों की निश्चित और पूर्व निर्धारित संख्या $T_{0}$ के साथ समाधान प्रदान कर सकता है।

विरल कोडिंग कार्य के पश्चात्, अगला कार्य उत्तम शब्दकोश $D$ की खोज करना है। चूँकि, समय में संपूर्ण शब्दकोश खोजना असंभव होता है, इसलिए प्रक्रिया शब्दकोश के केवल स्तंभ $D$ को अद्यतन करने की है, अतः प्रत्येक बार, ठीक करते समय $X$ का अद्यतन $k$-वें स्तंभ को दंड अवधि के रूप में फिर से लिखकर किया जाता है।

$\|Y-DX\|_{F}^{2}=\left\|Y-\sum _{j=1}^{K}d_{j}x_{j}^{\text{T}}\right\|_{F}^{2}=\left\|\left(Y-\sum _{j\neq k}d_{j}x_{j}^{\text{T}}\right)-d_{k}x_{k}^{\text{T}}\right\|_{F}^{2}=\|E_{k}-d_{k}x_{k}^{\text{T}}\|_{F}^{2}$

जहाँ $x_{k}^{\text{T}}$ एक्स की के-वीं पंक्ति को दर्शाता है।

गुणन विघटित करके $DX$ के योग में $K$ रैंक 1 आव्युह, हम दूसरे को मान सकते हैं। इस प्रकार $K-1$ शर्तों को निश्चित माना जाता है, और $k$-वह अज्ञात रहता है। इस चरण के पश्चात्, हम न्यूनतमकरण समस्या को अनुमानित रूप से हल कर सकते हैं जिससे कि $E_{k}$ ए के साथ शब्द $rank-1$ आव्युह एकवचन मूल्य अपघटन का उपयोग कर सकते है, अतः फिर $d_{k}$ इसके साथ अद्यतन करते है। चूँकि, सदिश का नया समाधान $x_{k}^{\text{T}}$ इसके भरे जाने की अधिक संभावना होती है, जिससे कि विरलता बाधा क्रियान्वित नहीं की गई है।

इस समस्या को $\omega _{k}$ जैसा ठीक करने के लिए परिभाषित करते है।

$\omega _{k}=\{i\mid 1\leq i\leq N,x_{k}^{\text{T}}(i)\neq 0\},$

जो उदाहरणों की ओर संकेत करता है $\{y_{i}\}_{i=1}^{N}$ जो परमाणु का उपयोग करता है $d_{k}$ (की प्रविष्टियाँ भी $x_{i}$ शून्येतर होती है)। फिर, परिभाषित करते है $\Omega _{k}$ आकार के आव्युह के रूप में $N\times |\omega _{k}|$, पर $(i,\omega _{k}(i)){\text{th}}$ वालों के साथ प्रविष्टियाँ और शून्य अन्यथा गुणा करते समय ${\tilde {x}}_{k}^{\text{T}}=x_{k}^{\text{T}}\Omega _{k}$ करते है, इससे पंक्ति सदिश $x_{k}^{\text{T}}$ शून्य प्रविष्टियों को त्यागकर सिकुड़ जाता है। इसी प्रकार, गुणन ${\tilde {Y}}_{k}=Y\Omega _{k}$ उन उदाहरणों का उपसमूह होता है जो वर्तमान में उपयोग किए जा रहे हैं जो $d_{k}$ परमाणु पर भी वैसा ही असर ${\tilde {E}}_{k}=E_{k}\Omega _{k}$ देखने को मिल सकता है।

तबी जैसा कि पहले उल्लेख किया गया है वह न्यूनतमकरण समस्या बन जाती है।

$\|E_{k}\Omega _{k}-d_{k}x_{k}^{\text{T}}\Omega _{k}\|_{F}^{2}=\|{\tilde {E}}_{k}-d_{k}{\tilde {x}}_{k}^{\text{T}}\|_{F}^{2}$

सामान्यतः सीधे एसवीडी का उपयोग करके किया जा सकता है। इस प्रकार एसवीडी ${\tilde {E}}_{k}$ में $U\Delta V^{\text{T}}$ विघटित हो जाता है। इसके लिए समाधान $d_{k}$ यू का पहला स्तंभ होता है, अतः गुणांक सदिश ${\tilde {x}}_{k}^{\text{T}}$ के पहले स्तंभ के रूप में $V\times \Delta (1,1)$ होता है। इस प्रकार संपूर्ण शब्दकोश को अद्यतन करने के पश्चात्, प्रक्रिया फिर एक्स को पुनरावृत्तीय रूप से हल करने, फिर पुनरावृत्तीय रूप से d को हल करने की ओर मुड़ जाती है।

सीमाएँ

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

यह भी देखें

• विरल सन्निकटन
• विलक्षण मान अपघटन
• आव्युह मानदंड
• के-तात्पर्य क्लस्टरिंग
• निम्न-श्रेणी सन्निकटन