Diffusion map
પ્રસરણ નકશા એ કોઇફમેન અને લાફોન દ્વારા રજૂ કરાયેલ પરિમાણીય ઘટાડો અથવા લક્ષણ નિષ્કર્ષણ અલ્ગોરિધમ છે જે યુક્લિડિયન અવકાશ (ઘણીવાર નિમ્ન-પરિમાણીય) માં સેટ કરેલા ડેટાના એમ્બેડિંગ્સના પરિવારની ગણતરી કરે છે, જેના કોઓર્ડિનેટ્સની ગણતરી ડેટા પર પ્રસરણ સંચાલકના આઈગનવેક્ટર્સ અને આઈગનવેલ્યુઝમાંથી કરી શકાય છે. જડિત જગ્યામાં બિંદુઓ વચ્ચેનું યુક્લિડિયન અંતર તે બિંદુઓ પર કેન્દ્રિત સંભાવના વિતરણો વચ્ચેનું "પ્રસરણ અંતર" બરાબર છે. મુખ્ય ઘટક વિશ્લેષણ (પી. સી. એ.) જેવી રેખીય પરિમાણીયતા ઘટાડવાની પદ્ધતિઓથી અલગ, પ્રસરણ નકશા બિનરેખીય પરિમાણીયતા ઘટાડવાની પદ્ધતિઓના પરિવારનો એક ભાગ છે જે અંતર્ગત મેનીફોલ્ડની શોધ પર ધ્યાન કેન્દ્રિત કરે છે જેમાંથી ડેટાનું નમૂના લેવામાં આવ્યું છે. વિવિધ સ્કેલ પર સ્થાનિક સમાનતાઓને એકીકૃત કરીને, પ્રસરણ નકશા ડેટા-સેટનું વૈશ્વિક વર્ણન આપે છે. અન્ય પદ્ધતિઓની સરખામણીમાં, પ્રસરણ નકશાનું અલ્ગોરિધમ ઘોંઘાટની વિક્ષેપ માટે મજબૂત છે અને ગણતરીત્મક રીતે સસ્તું છે. પ્રસરણ નકશાની વ્યાખ્યા નીચેના અને પ્રસરણ નકશાને ચાર તબક્કામાં વ્યાખ્યાયિત કરી શકાય છે. જોડાણ પ્રસરણ નકશા ગરમીના પ્રસરણ અને રેન્ડમ વોક માર્કોવ સાંકળ વચ્ચેના સંબંધનો ઉપયોગ કરે છે. મૂળભૂત અવલોકન એ છે કે જો આપણે માહિતી પર અવ્યવસ્થિત રીતે ચાલીએ, તો નજીકના માહિતી-બિંદુ પર ચાલવું એ દૂરના બીજા સ્થળે ચાલવા કરતાં વધુ શક્યતા છે. ચાલો એક માપ જગ્યા હોઈએ, જ્યાં ડેટા સેટ છે અને તેના પરના બિંદુઓના વિતરણને રજૂ કરે છે. આના આધારે, બે ડેટા પોઇન્ટ અને વચ્ચેની જોડાણને રેન્ડમ વોકના એક પગલાથી બીજા પગલા સુધી ચાલવાની સંભાવના તરીકે વ્યાખ્યાયિત કરી શકાય છે. સામાન્ય રીતે, આ સંભાવના બે બિંદુઓના કર્નલ કાર્યની દ્રષ્ટિએ સ્પષ્ટ કરવામાં આવે છેઃ ઉદાહરણ તરીકે, લોકપ્રિય ગૌસીયન કર્નલઃ વધુ સામાન્ય રીતે, કર્નલ કાર્યમાં નીચેના ગુણધર્મો હોય છે (સપ્રમાણ હોય છે) (હકારાત્મકતા જાળવી રાખે છે). કર્નલ ડેટા-સેટની સ્થાનિક ભૂમિતિની પૂર્વ વ્યાખ્યા બનાવે છે. આપેલ કર્નલ ડેટા સેટની ચોક્કસ સુવિધાને કેપ્ચર કરશે, તેથી તેની પસંદગી એ એપ્લિકેશન દ્વારા સંચાલિત થવી જોઈએ જે વ્યક્તિના મનમાં છે. મુખ્ય ઘટક વિશ્લેષણ જેવી પદ્ધતિઓ સાથે આ એક મોટો તફાવત છે, જ્યાં તમામ ડેટા બિંદુઓ વચ્ચેના સહસંબંધોને એક જ સમયે ધ્યાનમાં લેવામાં આવે છે. આપેલ, આપણે પછી રિવર્સિબલ ડિસ્ક્રીટ-ટાઇમ માર્કોવ સાંકળ બનાવી શકીએ છીએ (સામાન્ય ગ્રાફ લેપલેસિયન બાંધકામ તરીકે ઓળખાતી પ્રક્રિયા): અને વ્યાખ્યાયિત કરી શકીએ છીએઃ જો કે નવા સામાન્યકૃત કર્નલને સમપ્રમાણ ગુણધર્મનો વારસો મળતો નથી, તેમ છતાં તે હકારાત્મકતા-જાળવણી ગુણધર્મનો વારસો મેળવે છે અને સંરક્ષણ ગુણધર્મ મેળવે છેઃ પ્રસરણ પ્રક્રિયા આપણે માર્કોવ સાંકળ () નો સંક્રમણ મેટ્રિક્સ બનાવી શકીએ છીએ. બીજા શબ્દોમાં કહીએ તો, એક-પગલાની સંક્રમણ સંભાવનાને રજૂ કરે છે, અને ટી-પગલાનું સંક્રમણ મેટ્રિક્સ આપે છે. આપણે પ્રસરણ મેટ્રિક્સને વ્યાખ્યાયિત કરીએ છીએ (તે ગ્રાફ લેપલેસિયન મેટ્રિક્સનું સંસ્કરણ પણ છે) આપણે પછી નવા કર્નલને અથવા તેની સમકક્ષ વ્યાખ્યાયિત કરીએ છીએ, જ્યાં D એક કર્ણ મેટ્રિક્સ છે અને આપણે આ નવા કર્નલમાં ગ્રાફ લેપલેસિયન સામાન્યીકરણ લાગુ કરીએ છીએઃ જ્યાં એક કર્ણ મેટ્રિક્સ છે અને પ્રસરણ માળખાના મુખ્ય વિચારોમાંનો એક એ છે કે સાંકળને સમયસર આગળ ચલાવવી (મોટી અને મોટી શક્તિઓ લેવી) મોટા અને મોટા સ્કેલ (પ્રસરણ પ્રક્રિયા) પરની ભૌમિતિક રચના દર્શાવે છે. ખાસ કરીને, ડેટા સેટમાં ક્લસ્ટરની કલ્પનાને એવા પ્રદેશ તરીકે માપવામાં આવે છે જેમાં આ પ્રદેશમાંથી બહાર નીકળવાની સંભાવના ઓછી હોય છે (ચોક્કસ સમય t ની અંદર). તેથી, ટી માત્ર સમય પરિમાણ તરીકે જ કામ કરતું નથી, પરંતુ તેમાં સ્કેલ પરિમાણની બેવડી ભૂમિકા પણ છે. મેટ્રિક્સની ઇગેનડેકમ્પોઝિશન ઉપજ આપે છે જ્યાં અને અને અનુક્રમે બાયોર્થોગોનલ જમણા અને ડાબા આઇગેનવેક્ટર્સના આઇગેનવેલ્યુઝનો ક્રમ છે. આઈગન વેલ્યુઓના સ્પેક્ટ્રમના ક્ષયને કારણે, આ રકમમાં આપેલ સાપેક્ષ ચોકસાઈ પ્રાપ્ત કરવા માટે માત્ર થોડા શબ્દો જરૂરી છે. પરિમાણ α અને પ્રસરણ સંચાલક નોર્મલાઇઝેશન પગલું સામેલ કરવાનું કારણ પ્રસરણના અનંત સંક્રમણ પર ડેટા બિંદુ ઘનતાના પ્રભાવને ટ્યુન કરવાનું છે. કેટલીક એપ્લિકેશનોમાં, ડેટાનું સેમ્પલિંગ સામાન્ય રીતે આપણે વર્ણવવામાં રસ ધરાવીએ છીએ તે મેનીફોલ્ડની ભૂમિતિ સાથે સંબંધિત નથી. આ કિસ્સામાં, આપણે સેટ કરી શકીએ છીએ અને પ્રસરણ ઓપરેટર લાપ્લાસ-બેલ્ટ્રામી ઓપરેટરનો અંદાજ કાઢે છે. પછી આપણે બિંદુઓના વિતરણને ધ્યાનમાં લીધા વિના ડેટા સેટની રીમાનિયન ભૂમિતિને પુનઃપ્રાપ્ત કરીએ છીએ. સ્ટોકેસ્ટિક વિભેદક સમીકરણોની પ્રણાલીના બિંદુ વિતરણની લાંબા ગાળાની વર્તણૂકનું વર્ણન કરવા માટે, આપણે તેનો ઉપયોગ કરી શકીએ છીએ અને પરિણામી માર્કોવ સાંકળ ફોકર-પ્લાન્ક પ્રસરણની અંદાજ આપે છે. સાથે, તે ક્લાસિકલ ગ્રાફ લેપલેસિયન નોર્મલાઇઝેશનમાં ઘટાડો કરે છે. પ્રસરણ અંતર બે બિંદુઓ વચ્ચેના સમયે પ્રસરણ અંતરને તેમની વચ્ચેના જોડાણ સાથે નિરીક્ષણ અવકાશમાં બે બિંદુઓની સમાનતા તરીકે માપી શકાય છે. તે માર્કોવ સાંકળનું સ્થિર વિતરણ ક્યાં છે તેના દ્વારા આપવામાં આવે છે, જે પ્રથમ ડાબા આઈગનવેક્ટર દ્વારા આપવામાં આવે છે. સ્પષ્ટ રીતેઃ સહજ ભાવે, નાના હોય છે જો ત્યાં મોટી સંખ્યામાં ટૂંકા માર્ગો જોડાયેલા હોય અને. આપણી અગાઉની ચર્ચાના આધારે પ્રસરણ અંતર સાથે સંકળાયેલી ઘણી રસપ્રદ લાક્ષણિકતાઓ છે જે સ્કેલ પરિમાણ તરીકે પણ કામ કરે છેઃ જો બિંદુઓ ગ્રાફમાં ખૂબ જોડાયેલા હોય તો તે આપેલ સ્કેલ (દ્વારા નિર્દિષ્ટ) ની નજીક હોય છે, તેથી ક્લસ્ટરની વિભાવના પર ભાર મૂકે છે. આ અંતર ઘોંઘાટ માટે મજબૂત છે, કારણ કે બે બિંદુઓ વચ્ચેનું અંતર બિંદુઓ વચ્ચેના લંબાઈના તમામ સંભવિત માર્ગો પર આધારિત છે. મશીન લર્નિંગના દૃષ્ટિકોણથી, અંતર તેની સાથે જોડાયેલા તમામ પુરાવાઓને ધ્યાનમાં લે છે, જેનાથી આપણે નિષ્કર્ષ પર આવી શકીએ છીએ કે આ અંતર બહુમતી પ્રાધાન્ય પર આધારિત અનુમાન અલ્ગોરિધમ્સની રચના માટે યોગ્ય છે. પ્રસરણ પ્રક્રિયા અને નિમ્ન-પરિમાણીય એમ્બેડિંગ પ્રસરણ અંતરની ગણતરી આઈગનવેક્ટર્સનો ઉપયોગ કરીને કરી શકાય છે તેથી આઈગનવેક્ટર્સનો ઉપયોગ ડેટા માટે કોઓર્ડિનેટ્સના નવા સમૂહ તરીકે થઈ શકે છે. પ્રસરણ નકશાને આ રીતે વ્યાખ્યાયિત કરવામાં આવે છેઃ વર્ણપટના ક્ષયને કારણે, તે માત્ર પ્રથમ k આઈગનવેક્ટર્સ અને આઈગનવેલ્યુઝનો ઉપયોગ કરવા માટે પૂરતું છે. આમ આપણે મૂળ માહિતીમાંથી કે-પરિમાણીય જગ્યામાં પ્રસરણ નકશો મેળવીએ છીએ જે મૂળ જગ્યામાં જડિત છે. તેમાં સાબિત થયું છે કે તેથી પ્રસરણ કોઓર્ડિનેટ્સમાં યુક્લિડિયન અંતર પ્રસરણ અંતરની અંદાજ આપે છે. અલ્ગોરિધમ પ્રસરણ નકશાનું મૂળભૂત અલ્ગોરિધમ માળખું આ પ્રમાણે છેઃ પગલું 1. સમાનતા મેટ્રિક્સ એલ. પગલું 2 આપવામાં આવ્યું છે. પરિમાણ અનુસાર મેટ્રિક્સને સામાન્ય બનાવોઃ. પગલું 3. સામાન્યીકૃત મેટ્રિક્સ બનાવો. પગલું 4. k સૌથી મોટા આઈગનવેલ્યુ અને અનુરૂપ આઈગનવેક્ટર્સની ગણતરી કરો. પગલું 5. એમ્બેડિંગ મેળવવા માટે પ્રસરણ નકશાનો ઉપયોગ કરો. પેપરમાં અરજી નેડલર એટ અલ. ફોકર-પ્લાન્ક સમીકરણ દ્વારા પ્રેરિત પ્રસરણનું પુનઃઉત્પાદન કરતી કર્નલની રચના કેવી રીતે કરવી તે દર્શાવ્યું. તેઓએ એ પણ સમજાવ્યું કે, જ્યારે ડેટા અંદાજે મેનીફોલ્ડ હોય, ત્યારે લેપલેસ-બેલ્ટ્રામી ઓપરેટરના અંદાજની ગણતરી કરીને આ મેનીફોલ્ડની ભૂમિતિને પુનઃપ્રાપ્ત કરી શકાય છે. આ ગણતરી બિંદુઓના વિતરણ માટે સંપૂર્ણપણે અસંવેદનશીલ છે અને તેથી આંકડાશાસ્ત્ર અને ડેટાની ભૂમિતિને અલગ પાડે છે. પ્રસરણ નકશા ડેટા-સેટનું વૈશ્વિક વર્ણન આપે છે, તેથી તેઓ ડેટા એમ્બેડ કરેલા મેનીફોલ્ડમાં નમૂના બિંદુઓની જોડી વચ્ચેના અંતરને માપી શકે છે. પ્રસરણ નકશા પર આધારિત એપ્લિકેશનોમાં ચહેરાની ઓળખ, વર્ણપટ ક્લસ્ટરિંગ, છબીઓની ઓછી પરિમાણીય રજૂઆત, છબી વિભાજન, 3D મોડેલ વિભાજન, સ્પીકર ચકાસણી અને ઓળખ, મેનીફોલ્ડ્સ પર નમૂના, વિસંગતતા શોધ, છબી પેઇન્ટિંગ, બ્રેઇન રેસ્ટિંગ સ્ટેટ નેટવર્ક સંસ્થાને જાહેર કરવી વગેરેનો સમાવેશ થાય છે. વધુમાં, પ્રસરણ નકશાના માળખાને ઉત્પાદક રીતે જટિલ નેટવર્ક સુધી વિસ્તૃત કરવામાં આવ્યું છે, જે નેટવર્કની કાર્યાત્મક સંસ્થાને દર્શાવે છે જે શુદ્ધ ટોપોલોજિકલ અથવા માળખાકીયથી અલગ છે. બિનરેખીય પરિમાણીયતા ઘટાડો સ્પેક્ટ્રલ ક્લસ્ટરિંગ સંદર્ભો મશીન લર્નિંગ અલ્ગોરિધમ્સ પણ જુઓ.