Markov random field
ભૌતિકશાસ્ત્ર અને સંભાવનાના ક્ષેત્રમાં, માર્કોવ રેન્ડમ ફિલ્ડ (એમ. આર. એફ.), માર્કોવ નેટવર્ક અથવા દિશાહીન ગ્રાફિકલ મોડેલ એ દિશાહીન આલેખ દ્વારા વર્ણવેલ માર્કોવ ગુણધર્મ ધરાવતા યાદૃચ્છિક ચલોનો સમૂહ છે. બીજા શબ્દોમાં કહીએ તો, રેન્ડમ ક્ષેત્રને માર્કોવ રેન્ડમ ક્ષેત્ર કહેવામાં આવે છે જો તે માર્કોવ ગુણધર્મોને સંતોષે છે. આ ખ્યાલ શેરિંગ્ટન-કિર્કપેટ્રિક મોડેલમાંથી ઉદ્ભવે છે. માર્કોવ નેટવર્ક અથવા એમ. આર. એફ. તેના અવલંબનની રજૂઆતમાં બાયેસિયન નેટવર્ક જેવું જ છે; તફાવત એ છે કે બાયેસિયન નેટવર્ક નિર્દેશિત અને ચક્રીય છે, જ્યારે માર્કોવ નેટવર્ક દિશાહીન છે અને ચક્રીય હોઈ શકે છે. આમ, માર્કોવ નેટવર્ક અમુક અવલંબનોનું પ્રતિનિધિત્વ કરી શકે છે જે બાયેસિયન નેટવર્ક કરી શકતું નથી (જેમ કે ચક્રીય અવલંબન); બીજી તરફ, તે અમુક અવલંબનોનું પ્રતિનિધિત્વ કરી શકતું નથી જે બાયેસિયન નેટવર્ક કરી શકે છે (જેમ કે પ્રેરિત અવલંબન). માર્કોવ રેન્ડમ ક્ષેત્રનો અંતર્ગત આલેખ મર્યાદિત અથવા અનંત હોઈ શકે છે. જ્યારે રેન્ડમ ચલની સંયુક્ત સંભાવના ઘનતા સખત રીતે હકારાત્મક હોય છે, ત્યારે તેને ગિબ્સ રેન્ડમ ક્ષેત્ર તરીકે પણ ઓળખવામાં આવે છે, કારણ કે, હેમર્સલી-ક્લિફોર્ડ પ્રમેય અનુસાર, તે પછી યોગ્ય (સ્થાનિક રીતે વ્યાખ્યાયિત) ઊર્જા કાર્ય માટે ગિબ્સ માપ દ્વારા રજૂ કરી શકાય છે. પ્રોટોટાઇપિકલ માર્કોવ રેન્ડમ ફિલ્ડ એ ઇઝિંગ મોડેલ છે; ખરેખર, માર્કોવ રેન્ડમ ફિલ્ડ ઇઝિંગ મોડેલ માટે સામાન્ય સેટિંગ તરીકે રજૂ કરવામાં આવ્યું હતું. આર્ટિફિશિયલ ઇન્ટેલિજન્સના ક્ષેત્રમાં, માર્કોવ રેન્ડમ ફિલ્ડનો ઉપયોગ ઇમેજ પ્રોસેસિંગ અને કમ્પ્યુટર વિઝનમાં વિવિધ નીચલાથી મધ્યમ સ્તરના કાર્યોનું મોડેલ બનાવવા માટે થાય છે. વ્યાખ્યા દિશાહીન આલેખને જોતાં, માર્કોવ રેન્ડમ ક્ષેત્ર દ્વારા અનુક્રમિત રેન્ડમ ચલોનો સમૂહ જો તેઓ સ્થાનિક માર્કોવ ગુણધર્મોને સંતુષ્ટ કરે તોઃ જોડી મુજબ માર્કોવ ગુણધર્મઃ કોઈપણ બે બિન-સંલગ્ન ચલ શરતી રીતે અન્ય તમામ ચલને ધ્યાનમાં રાખીને સ્વતંત્ર હોય છેઃ સ્થાનિક માર્કોવ ગુણધર્મઃ એક ચલ તેના પડોશીઓને આપવામાં આવેલા અન્ય તમામ ચલથી શરતી રીતે સ્વતંત્ર હોય છેઃ પડોશીઓનો સમૂહ ક્યાં છે, અને તેનો બંધ પડોશી છે. વૈશ્વિક માર્કોવ ગુણધર્મઃ વેરિયેબલ્સના કોઈપણ બે સબસેટ્સ શરતી રીતે સ્વતંત્ર હોય છે, જેમાં એક અલગ સબસેટ આપવામાં આવે છેઃ જ્યાં નોડથી નોડ સુધીનો દરેક માર્ગ પસાર થાય છે. વૈશ્વિક માર્કોવ મિલકત સ્થાનિક માર્કોવ મિલકત કરતાં વધુ મજબૂત છે, જે બદલામાં જોડીની મિલકત કરતાં વધુ મજબૂત છે. જો કે, ઉપરોક્ત ત્રણ માર્કોવ ગુણધર્મો હકારાત્મક વિતરણ માટે સમકક્ષ છે (જે સંકળાયેલ ચલ માટે માત્ર બિન-શૂન્ય સંભાવનાઓ સોંપે છે). ત્રણ માર્કોવ ગુણધર્મો વચ્ચેનો સંબંધ નીચેની રચનામાં ખાસ કરીને સ્પષ્ટ છેઃ જોડી મુજબઃ કોઈપણ સમાન અથવા અડીને ન હોય તેવા માટે, સ્થાનિકઃ કોઈપણ માટે અને તેમાં ન હોય અથવા તેની નજીક ન હોય. વૈશ્વિકઃ કોઈ પણ આંતરછેદ અથવા અડીને ન હોય તે માટે,. ક્લીક ફેક્ટરાઇઝેશન કારણ કે મનસ્વી સંભાવના વિતરણનો માર્કોવ ગુણધર્મ સ્થાપિત કરવો મુશ્કેલ હોઈ શકે છે, માર્કોવ રેન્ડમ ક્ષેત્રોનો સામાન્ય રીતે ઉપયોગમાં લેવાતો વર્ગ તે છે જેને ગ્રાફના જૂથો અનુસાર ફેક્ટરાઇઝ કરી શકાય છે. રેન્ડમ વેરિયેબલના સમૂહને જોતાં, ચોક્કસ ક્ષેત્ર રૂપરેખાંકનની સંભાવના હોવી જોઈએ-એટલે કે, રેન્ડમ વેરિયેબલ ચોક્કસ મૂલ્ય પર લે છે તે શોધવાની સંભાવના છે. કારણ કે તે એક સમૂહ છે, તેની સંભાવના સંયુક્ત વિતરણના સંદર્ભમાં લેવામાં આવે છે તે સમજવું જોઈએ. જો આ સંયુક્ત ઘનતાને આના જૂથો પર ફેક્ટરાઇઝ કરી શકાય તો તેના સંદર્ભમાં માર્કોવ રેન્ડમ ક્ષેત્ર રચાય છે. અહીં, જૂથોનો સમૂહ છે. જો માત્ર મહત્તમ જૂથોનો ઉપયોગ કરવામાં આવે તો વ્યાખ્યા સમકક્ષ છે. વિધેયોને કેટલીકવાર પરિબળ સંભવિત અથવા ક્લીક સંભવિત તરીકે ઓળખવામાં આવે છે. નોંધ લો, જોકે, વિરોધાભાસી પરિભાષા ઉપયોગમાં છેઃ સંભવિત શબ્દ ઘણીવાર તેના લઘુગણક પર લાગુ થાય છે. આનું કારણ એ છે કે, આંકડાકીય મિકેનિક્સમાં, રૂપરેખાંકનની સંભવિત ઊર્જા તરીકે સીધું અર્થઘટન છે. કેટલાક એમ. આર. એફ. ફેક્ટરાઇઝ થતા નથીઃ એક સરળ ઉદાહરણ કેટલીક અનંત ઊર્જાઓ સાથે 4 ગાંઠોના ચક્ર પર બનાવી શકાય છે, એટલે કે. શૂન્ય સંભાવનાઓનું રૂપરેખાંકન, ભલે એક, વધુ યોગ્ય રીતે, અનંત ઊર્જાને સંપૂર્ણ આલેખ પર કાર્ય કરવાની મંજૂરી આપે. જો નીચેની શરતોમાંથી ઓછામાં ઓછી એક શરત પૂર્ણ થાય તો એમ. આર. એફ. નું ફેક્ટરાઇઝ થાય છેઃ ઘનતા હકારાત્મક છે (હેમર્સલી-ક્લિફોર્ડ પ્રમેય દ્વારા) ગ્રાફ કોર્ડલ છે (બાયેસિયન નેટવર્કની સમકક્ષતા દ્વારા) જ્યારે આવા ફેક્ટરાઇઝેશન અસ્તિત્વમાં હોય, ત્યારે નેટવર્ક માટે ફેક્ટર ગ્રાફ બનાવવો શક્ય છે. એક્સપોનેન્શલ ફેમિલી કોઈપણ પોઝિટિવ માર્કોવ રેન્ડમ ફિલ્ડને ફીચર ફંક્શન્સ સાથે કેનોનિકલ સ્વરૂપમાં એક્સપોનેન્શલ ફેમિલી તરીકે લખી શકાય છે જેમ કે ફુલ-જોઇન્ટ ડિસ્ટ્રિબ્યુશનને લખી શકાય છે જ્યાં નોટેશન ફક્ત ફિલ્ડ કન્ફિગરેશન પર ડોટ પ્રોડક્ટ છે, અને Z એ પાર્ટીશન ફંક્શન છેઃ અહીં, તમામ નેટવર્કના રેન્ડમ વેરિયેબલ્સ માટે મૂલ્યોની તમામ સંભવિત સોંપણીઓનો સમૂહ સૂચવે છે. સામાન્ય રીતે, લક્ષણ કાર્યોને એવી રીતે વ્યાખ્યાયિત કરવામાં આવે છે કે તેઓ જૂથની ગોઠવણીના સૂચકાંકો હોય, એટલે કે. જો k-th જૂથના i-th સંભવિત રૂપરેખાંકનને અનુરૂપ હોય અને અન્યથા 0. આ મોડેલ ઉપર આપેલા ક્લીક ફેક્ટરાઇઝેશન મોડેલની સમકક્ષ છે, જો તે ક્લીકની મુખ્યતા છે, અને લક્ષણનું વજન અનુરૂપ ક્લીક ફેક્ટરના લઘુગણકને અનુરૂપ છે, એટલે કે. , k-th જૂથનું i-th શક્ય રૂપરેખાંકન ક્યાં છે, એટલે કે. જૂથના ક્ષેત્રમાં i-th મૂલ્ય. સંભાવના પી ને ઘણીવાર ગિબ્સ માપ કહેવામાં આવે છે. લોજિસ્ટિક મોડેલ તરીકે માર્કોવ ક્ષેત્રની આ અભિવ્યક્તિ ત્યારે જ શક્ય છે જ્યારે તમામ જૂથ પરિબળો બિન-શૂન્ય હોય, એટલે કે. જો તેમાંથી કોઈ પણ તત્વને 0 ની સંભાવના સોંપવામાં ન આવે. આ મેટ્રિક્સ બીજગણિતમાંથી તકનીકોને લાગુ કરવાની મંજૂરી આપે છે, દા. ત. કે મેટ્રિક્સનું ટ્રેસ એ નિર્ધારકનું લોગ છે, જેમાં ગ્રાફના ઇન્સિડેન્સ મેટ્રિક્સમાંથી ઉદ્ભવતા ગ્રાફની મેટ્રિક્સ રજૂઆત છે. પાર્ટીશન ફંક્શન ઝેડનું મહત્વ એ છે કે આંકડાકીય મિકેનિક્સના ઘણા ખ્યાલો, જેમ કે એન્ટ્રોપી, સીધા માર્કોવ નેટવર્કના કિસ્સામાં સામાન્ય બને છે, અને તેથી સાહજિક સમજણ મેળવી શકાય છે. વધુમાં, પાર્ટીશન ફંક્શન સમસ્યાના ઉકેલ માટે વિવિધ પદ્ધતિઓ લાગુ કરવાની મંજૂરી આપે છેઃ એક અથવા વધુ રેન્ડમ ચલ સાથે પ્રેરક બળ જોડી શકાય છે, અને આ વિક્ષેપના જવાબમાં નેટવર્કની પ્રતિક્રિયાનું અન્વેષણ કરી શકાય છે. આમ, ઉદાહરણ તરીકે, ગ્રાફના દરેક શિરોબિંદુ v માટે, વિભાજન કાર્યમાં ડ્રાઇવિંગ શબ્દ Jv ઉમેરી શકાય છેઃ Jv ના સંદર્ભમાં ઔપચારિક રીતે તફાવત કરવાથી શિરોબિંદુ v સાથે સંકળાયેલ રેન્ડમ ચલ Xv નું અપેક્ષિત મૂલ્ય મળે છેઃ સહસંબંધ કાર્યોની ગણતરી એ જ રીતે કરવામાં આવે છે; બે-બિંદુ સહસંબંધ છેઃ કમનસીબે, લોજિસ્ટિક માર્કોવ નેટવર્કની સંભાવના બહિર્મુખ હોવા છતાં, મોડેલની સંભાવનાની સંભાવના અથવા ઢાળનું મૂલ્યાંકન કરવા માટે મોડેલમાં અનુમાન જરૂરી છે, જે સામાન્ય રીતે ગણતરીત્મક રીતે અશક્ય છે (નીચે 'અનુમાન' જુઓ). ઉદાહરણો ગૌસીયન એક બહુપરીમાણીય સામાન્ય વિતરણ ગ્રાફના સંદર્ભમાં માર્કોવ રેન્ડમ ક્ષેત્ર બનાવે છે જો ગુમ થયેલ ધાર ચોકસાઇ મેટ્રિક્સ (વ્યસ્ત સહપ્રસરણ મેટ્રિક્સ) પર શૂન્યને અનુરૂપ હોયઃ જેમ કે અનુમાન બાયેસિયન નેટવર્કની જેમ, કોઈ પણ વ્યક્તિ માર્કોવ રેન્ડમ ક્ષેત્રમાં ગાંઠોના અન્ય સમૂહને આપવામાં આવેલા મૂલ્યોના સમૂહના શરતી વિતરણની ગણતરી કરી શકે છે, જેમાં તમામ સંભવિત સોંપણીઓનો સરવાળો કરી શકાય છે; આને ચોક્કસ અનુમાન કહેવામાં આવે છે. જો કે, ચોક્કસ અનુમાન એ #P-પૂર્ણ સમસ્યા છે, અને આમ સામાન્ય કિસ્સામાં ગણતરીત્મક રીતે જટિલ છે. માર્કોવ સાંકળ મોન્ટે કાર્લો અને લૂપી માન્યતા પ્રચાર જેવી અંદાજિત તકનીકો વ્યવહારમાં ઘણીવાર વધુ શક્ય છે. એમ. આર. એફ. ના કેટલાક ચોક્કસ પેટા વર્ગો, જેમ કે વૃક્ષો (જુઓ ચૌ-લિઉ વૃક્ષ), બહુપદી-સમયના અનુમાન અલ્ગોરિધમ્સ ધરાવે છે; આવા પેટા વર્ગોની શોધ એ એક સક્રિય સંશોધન વિષય છે. એમ. આર. એફ. ના પેટા વર્ગો પણ છે જે કાર્યક્ષમ એમ. એ. પી., અથવા મોટે ભાગે સોંપણી, અનુમાનની મંજૂરી આપે છે; આના ઉદાહરણોમાં સહયોગી નેટવર્કનો સમાવેશ થાય છે. અન્ય રસપ્રદ પેટા-વર્ગ એ વિઘટનક્ષમ નમૂનાઓમાંથી એક છે (જ્યારે આલેખ કોર્ડલ હોય છે): એમ. એલ. ઇ. માટે બંધ સ્વરૂપ હોવાથી, સેંકડો ચલ માટે સુસંગત માળખું શોધવું શક્ય છે. શરતી રેન્ડમ ક્ષેત્રો માર્કોવ રેન્ડમ ક્ષેત્રનો એક નોંધપાત્ર પ્રકાર શરતી રેન્ડમ ક્ષેત્ર છે, જેમાં દરેક રેન્ડમ ચલને વૈશ્વિક અવલોકનોના સમૂહ પર પણ શરતી કરી શકાય છે. આ મોડેલમાં, દરેક કાર્ય એ તમામ સોંપણીઓમાંથી ક્લીક k અને બિન-નકારાત્મક વાસ્તવિક સંખ્યાઓ માટેના અવલોકનો બંનેનું મેપિંગ છે. માર્કોવ નેટવર્કનું આ સ્વરૂપ ભેદભાવપૂર્ણ વર્ગીકરણોના ઉત્પાદન માટે વધુ યોગ્ય હોઈ શકે છે, જે અવલોકનો પર વિતરણનું મોડેલ નથી કરતા. સી. આર. એફ. ની દરખાસ્ત જ્હોન ડી. લેફર્ટી, એન્ડ્રુ મેકકલમ અને ફર્નાન્ડો સી. એન. દ્વારા કરવામાં આવી હતી. 2001માં પરેરા. વિવિધ એપ્લિકેશનો માર્કોવ રેન્ડમ ક્ષેત્રો કમ્પ્યુટર ગ્રાફિક્સથી લઈને કમ્પ્યુટર વિઝન, મશીન લર્નિંગ અથવા કોમ્પ્યુટેશનલ બાયોલોજી અને માહિતી પુનઃપ્રાપ્તિ સુધીના વિવિધ ક્ષેત્રોમાં એપ્લિકેશન શોધે છે. એમ. આર. એફ. નો ઉપયોગ ઇમેજ પ્રોસેસિંગમાં ટેક્સચર બનાવવા માટે થાય છે કારણ કે તેનો ઉપયોગ લવચીક અને સ્ટોકેસ્ટિક ઇમેજ મોડલ બનાવવા માટે થઈ શકે છે. ઇમેજ મોડેલિંગમાં, કાર્ય આપેલ ઇમેજનું યોગ્ય તીવ્રતા વિતરણ શોધવાનું છે, જ્યાં યોગ્યતા કાર્યના પ્રકાર પર આધાર રાખે છે અને એમ. આર. એફ. ઇમેજ અને ટેક્સચર સંશ્લેષણ, ઇમેજ કમ્પ્રેશન અને રિસ્ટોરેશન, ઇમેજ સેગમેન્ટેશન, 2ડી છબીઓમાંથી 3ડી ઇમેજ અનુમાન, ઇમેજ રજિસ્ટ્રેશન, ટેક્સચર સંશ્લેષણ, સુપર-રિઝોલ્યુશન, સ્ટીરિયો મેચિંગ અને માહિતી પુનઃપ્રાપ્તિ માટે ઉપયોગમાં લેવા માટે પૂરતા લવચીક હોય છે. તેનો ઉપયોગ વિવિધ કોમ્પ્યુટર દ્રષ્ટિ સમસ્યાઓને ઉકેલવા માટે થઈ શકે છે જેને ઊર્જા લઘુતમ સમસ્યાઓ અથવા સમસ્યાઓ તરીકે રજૂ કરી શકાય છે જ્યાં માર્કોવ રેન્ડમ ફિલ્ડ ફ્રેમવર્કની અંદર, પ્રદેશની શ્રેણીની આગાહી કરવા માટે ભેદભાવપૂર્ણ સુવિધાઓના સમૂહનો ઉપયોગ કરીને વિવિધ પ્રદેશોને અલગ પાડવા પડે છે. માર્કોવ રેન્ડમ ક્ષેત્રો ઇઝિંગ મોડેલ પર સામાન્યીકરણ હતા અને ત્યારથી, સંયુક્ત ઓપ્ટિમાઇઝેશન અને નેટવર્કમાં વ્યાપકપણે ઉપયોગમાં લેવાય છે. આ પણ જુઓ કન્સ્ટ્રેન્ટ કમ્પોઝિટ ગ્રાફ ગ્રાફ ગ્રાફિકલ મોડેલ ડિપેન્ડન્સી નેટવર્ક (ગ્રાફિકલ મોડેલ) હેમર્સલી-ક્લિફોર્ડ થીયરમ હોપફિલ્ડ નેટવર્ક ઇન્ટરેક્ટિંગ પાર્ટિકલ સિસ્ટમ આઇસિંગ મોડેલ લોગ-લિનિયર એનાલિસિસ માર્કોવ ચેઇન માર્કોવ લોજિક નેટવર્ક મેક્સિમમ એન્ટ્રોપી મેથડ સ્ટોકેસ્ટિક સેલ્યુલર ઓટોમેટન રેફરન્સ ગ્રાફિકલ મોડલ્સ