Optimistic knowledge gradient
આંકડામાં આશાવાદી જ્ઞાન ઢાળ એ 2013માં શી ચેન, કિહાંગ લિન અને ડેંગયોંગ ઝોઉ દ્વારા પ્રસ્તાવિત અંદાજિત નીતિ છે. આ નીતિ દ્વિસંગી/બહુ-વર્ગના ભીડ લેબલિંગમાં શ્રેષ્ઠ કમ્પ્યુટિંગ બજેટ ફાળવણી સમસ્યાના મોટા કદની ગણતરીત્મક રીતે જટિલતાના પડકારને ઉકેલવા માટે બનાવવામાં આવી છે જ્યાં ભીડમાંથી દરેક લેબલની ચોક્કસ કિંમત હોય છે. પ્રેરણા શ્રેષ્ઠ કમ્પ્યુટિંગ બજેટ ફાળવણી સમસ્યાને બાયેસિયન માર્કોવ નિર્ણય પ્રક્રિયા (એમડીપી) તરીકે ઘડવામાં આવી છે અને તેને ડાયનેમિક પ્રોગ્રામિંગ (ડી. પી.) અલ્ગોરિધમનો ઉપયોગ કરીને હલ કરવામાં આવે છે જ્યાં ડાયનેમિક પ્રોગ્રામિંગ (ડી. પી.) અલ્ગોરિધમનો કોમ્પ્યુટેશનલ રીતે અવ્યવસ્થિત ઉકેલ લાવવા માટે ઓપ્ટિમિસ્ટિક નોલેજ ગ્રેડિયન્ટ નીતિનો ઉપયોગ કરવામાં આવે છે. ક્રાઉડસોર્સિંગમાં બજેટ ફાળવણીના મુદ્દાને ધ્યાનમાં લો. આપણે જે ખાસ ક્રાઉડસોર્સિંગ સમસ્યાને ધ્યાનમાં લઈએ છીએ તે ક્રાઉડ લેબલિંગ છે. ક્રાઉડ લેબલિંગ એ મોટી માત્રામાં લેબલિંગ કાર્યો છે જે મશીન દ્વારા ઉકેલવા મુશ્કેલ છે, મનુષ્ય દ્વારા ઉકેલવા માટે સરળ બને છે, પછી આપણે વિતરિત વાતાવરણમાં અવ્યવસ્થિત લોકોના અજાણ્યા જૂથને આઉટસોર્સ કરીએ છીએ. કાર્યપદ્ધતિ અમે આ લેબલિંગ કાર્યોને પૂર્ણ કરવા માંગીએ છીએ આશા છે કે તે ભીડની શક્તિ પર આધાર રાખે છે. ઉદાહરણ તરીકે, ધારો કે આપણે ચિત્રમાંના લોકો અનુસાર ચિત્રને ઓળખવા માંગીએ છીએ કે તે પુખ્ત છે કે નહીં, આ એક બર્નૌલી લેબલિંગ સમસ્યા છે, અને આપણે બધા એક કે બે સેકન્ડમાં કરી શકીએ છીએ, આ મનુષ્ય માટે એક સરળ કાર્ય છે. જો કે, જો આપણી પાસે આ પ્રકારના હજારો ચિત્રો છે, તો હવે આ સરળ કાર્ય નથી. તેથી જ આપણે આને ઝડપી બનાવવા માટે ક્રાઉડસોર્સિંગ માળખા પર આધાર રાખવાની જરૂર છે. આના ક્રાઉડસોર્સિંગ માળખામાં બે પગલાઓનો સમાવેશ થાય છે. પહેલું પગલું, આપણે વસ્તુઓ માટે ભીડમાંથી ગતિશીલ રીતે ખરીદી કરીએ છીએ. બીજી બાજુએ, આ એક ગતિશીલ પ્રક્રિયા છે. અમે આ ચિત્ર ફક્ત દરેકને મોકલતા નથી અને અમે દરેક પ્રતિસાદ પર ધ્યાન કેન્દ્રિત કરીએ છીએ, તેના બદલે, અમે આ માત્રામાં કરીએ છીએ. અમે નક્કી કરવા જઈ રહ્યા છીએ કે અમે તેને આગામીમાં કયું ચિત્ર મોકલીશું, અને આગામી ભીડમાં અમે કયા કામદારને ભાડે રાખીશું. તેના અથવા તેણીના ઐતિહાસિક લેબલિંગ પરિણામો અનુસાર. અને દરેક ચિત્ર બહુવિધ કામદારોને મોકલી શકાય છે અને દરેક કામદાર વિવિધ ચિત્રો પર પણ કામ કરી શકે છે. પછી આપણે વિવિધ ચિત્રો માટે પૂરતી સંખ્યામાં લેબલો એકત્રિત કર્યા પછી, આપણે બીજા પગલા પર જઈએ છીએ જ્યાં આપણે એકત્રિત કરેલા લેબલોના આધારે દરેક ચિત્રના સાચા લેબલનું અનુમાન લગાવવા માંગીએ છીએ. તેથી આપણે અનુમાન કરી શકીએ તેવી ઘણી રીતો છે. દાખલા તરીકે, આપણે આ કરી શકીએ તે સૌથી સરળ છે માત્ર બહુમતી મત. સમસ્યા એ છે કે મફત ભોજન નહીં, આપણે કામદારને તે અથવા તેણી પ્રદાન કરે છે તે દરેક લેબલ માટે ચૂકવણી કરવી પડે છે અને આપણી પાસે માત્ર મર્યાદિત પ્રોજેક્ટ બજેટ છે. તો સવાલ એ છે કે મર્યાદિત બજેટને સ્માર્ટ રીતે કેવી રીતે ખર્ચવું. પડકારો ગણિતનું નમૂના દર્શાવતા પહેલા પેપરમાં ઉલ્લેખ કરવામાં આવ્યો છે કે આપણે કેવા પ્રકારના પડકારોનો સામનો કરી રહ્યા છીએ. પડકાર 1 સૌ પ્રથમ, વસ્તુઓને લેબલની ગણતરી કરવામાં મુશ્કેલીનું એક અલગ સ્તર હોય છે, અગાઉના ઉદાહરણમાં, કેટલાક ચિત્રોનું વર્ગીકરણ કરવું સરળ છે. આ કિસ્સામાં, તમે સામાન્ય રીતે ભીડમાંથી ખૂબ સુસંગત લેબલ જોશો. જો કે, જો કેટલાક ચિત્રો અસ્પષ્ટ હોય, તો લોકો એકબીજા સાથે અસંમત થઈ શકે છે જેના પરિણામે અત્યંત અસંગત લેબલિંગ થઈ શકે છે. તેથી આપણે આ અસ્પષ્ટ કાર્ય પર વધુ સંસાધનો ફાળવી શકીએ છીએ. પડકાર 2 અને આપણી પાસે ઘણીવાર બીજી મુશ્કેલી એ હોય છે કે કામદાર સંપૂર્ણ નથી, કેટલીકવાર આ કામદાર જવાબદાર નથી, તેઓ માત્ર રેન્ડમ લેબલ પ્રદાન કરે છે, તેથી, અલબત્ત, અમે આ વિશ્વસનીય કામદારો પર અમારું બજેટ ખર્ચ નહીં કરીએ. હવે સમસ્યા એ છે કે ચિત્રોની મુશ્કેલી અને કામદારની વિશ્વસનીયતા જે આપણે શરૂઆતમાં સંપૂર્ણપણે અજાણ હતા. અમે પ્રક્રિયા દરમિયાન જ તેમનો અંદાજ લગાવી શકીએ છીએ. તેથી, આપણે સ્વાભાવિક રીતે સંશોધન અને શોષણનો સામનો કરી રહ્યા છીએ, અને અમારું લક્ષ્ય યોગ્ય રીતે નાણાં ખર્ચવા માટે વાજબી સારી નીતિ આપવાનું છે-અંતિમ અનુમાનિત લેબલોની એકંદર ચોકસાઈને મહત્તમ કરવી. ગાણિતિક મોડેલ માટે, આપણી પાસે K વસ્તુઓ છે, અને કુલ બજેટ T છે અને આપણે ધારીએ છીએ કે દરેક લેબલની કિંમત 1 છે તેથી આપણી પાસે આખરે T લેબલ હશે. આપણે ધારીએ છીએ કે દરેક વસ્તુનું સાચું લેબલ છે જે હકારાત્મક કે નકારાત્મક છે, આ દ્વિપદી કિસ્સાઓ અને આપણે બહુવિધ વર્ગ, લેબલિંગ કેસો સુધી વિસ્તૃત કરી શકીએ છીએ, આ એક એકવચન વિચાર છે. અને સકારાત્મક સમૂહને વસ્તુઓના સમૂહ તરીકે વ્યાખ્યાયિત કરવામાં આવે છે જેનું સાચું લેબલ સકારાત્મક હોય છે. અને 0 અને 1 ની વચ્ચેની દરેક વસ્તુ માટે સોફ્ટ-લેબલને પણ વ્યાખ્યાયિત કર્યું છે, અને અમે સંપૂર્ણ કામદારોના જૂથમાંથી અવ્યવસ્થિત રીતે પસંદ કરાયેલા સભ્ય દ્વારા સકારાત્મક તરીકે લેબલ થવાની અંતર્ગત સંભાવના તરીકે વ્યાખ્યાયિત કરીએ છીએ. આ પ્રથમ કિસ્સામાં, આપણે ધારીએ છીએ કે દરેક કામદાર સંપૂર્ણ છે, તેનો અર્થ એ છે કે તેઓ બધા વિશ્વસનીય છે, પરંતુ સંપૂર્ણ હોવાનો અર્થ એ નથી કે આ કાર્યકર સમાન જવાબ અથવા સાચો જવાબ આપે છે. તેનો અર્થ એ છે કે તેઓ તેમના મનમાં શ્રેષ્ઠ જવાબ શોધવાનો શ્રેષ્ઠ પ્રયાસ કરશે, અને ધારો કે દરેક વ્યક્તિ સંપૂર્ણ કાર્યકર છે, માત્ર અવ્યવસ્થિત રીતે તેમાંથી એકને પસંદ કર્યો છે, અને સંભાવના સાથે, આપણે એક વ્યક્તિ મેળવીશું જે માને છે કે આ એક સકારાત્મક છે. આ રીતે આપણે સમજાવીએ છીએ. તેથી આપણે ધારીએ છીએ કે લેબલ બર્નૌલી () માંથી દોરવામાં આવ્યું છે, અને તે સાચા લેબલ સાથે સુસંગત હોવું જોઈએ, જેનો અર્થ એ છે કે જો આ વસ્તુ સાચા હકારાત્મક લેબલ સાથે હકારાત્મક હોય તો જ તે 0.5 થી વધારે અથવા સમાન હોય. તેથી અમારું લક્ષ્ય H *, હકારાત્મક વસ્તુઓનો સમૂહ શીખવાનું છે. બીજા શબ્દોમાં કહીએ તો, આપણે મહત્તમ કરવા માટે એકત્રિત લેબલોના આધારે અનુમાનિત હકારાત્મક સમૂહ H બનાવવા માંગીએ છીએઃ તેને આ રીતે પણ લખી શકાય છેઃ પગલું 1: બાયેસિયન નિર્ણય પ્રક્રિયા બાયેસિયન માળખું બતાવતા પહેલા, આપણે આવર્તન અભિગમને બદલે બાયેસિયન કેમ પસંદ કરીએ છીએ તેનો ઉલ્લેખ કરવા માટે પેપર એક ઉદાહરણનો ઉપયોગ કરે છે, જેમ કે આપણે સોફ્ટ-લેબલ પર પૂર્વ વિતરણના કેટલાક પશ્ચાદવર્તી પ્રસ્તાવ કરી શકીએ છીએ. આપણે ધારીએ છીએ કે દરેક અગાઉ જાણીતા બીટા પરથી દોરવામાં આવ્યું છેઃ અને મેટ્રિક્સઃ તેથી આપણે જાણીએ છીએ કે બીટાનો બર્નૌલી કોન્જુગેટ, તેથી એકવાર આપણે આઇટમ i માટે નવું લેબલ મેળવીએ, પછી આપણે પશ્ચાદવર્તી વિતરણને અપડેટ કરવા જઈશું, બીટા વિતરણ આના દ્વારાઃ લેબલ પર આધાર રાખીને હકારાત્મક કે નકારાત્મક છે. અહીં ઉચ્ચ સ્તરની સમગ્ર પ્રક્રિયા છે, આપણી પાસે ટી સ્ટેજ છે. અને વર્તમાન તબક્કામાં આપણે મેટ્રિક્સ S જોઈએ છીએ, જે તમામ માટે પશ્ચાદવર્તી વિતરણ માહિતીનો સારાંશ આપે છે. અને લેબલ હકારાત્મક કે નકારાત્મક છે તેના આધારે, આપણે લેબલ મેળવવા માટે એક મેટ્રિક્સ ઉમેરીએ છીએઃ સૌથી ઉપર, આ આખું માળખું છે. પગલું 2: હકારાત્મક સમૂહ પર અનુમાન જ્યારે ટી લેબલો એકત્રિત કરવામાં આવે છે, ત્યારે આપણે સેન્ટ દ્વારા આપવામાં આવેલા પશ્ચાદવર્તી વિતરણના આધારે હકારાત્મક સમૂહ Ht વિશે અનુમાન કરી શકીએ છીએ. શ્રેષ્ઠ ઉકેલ શું છે તે જાણ્યા પછી, કાગળ દર્શાવે છે કે શ્રેષ્ઠ મૂલ્ય શું છે. શ્રેષ્ઠ કાર્યમાં પ્લગ કરો, આ કાર્ય માત્ર એક જ કાર્ય છે જે હકારાત્મક અને નકારાત્મક હોવાની શરતી સંભાવના વચ્ચે મોટા કાર્યને પસંદ કરે છે. એકવાર આપણે આઇટમ i માટે વધુ એક લેબલ મેળવી લઈએ, પછી આપણે આ મૂલ્ય વચ્ચે તફાવત લઈએ છીએ, આપણે નવું લેબલ મેળવીએ તે પહેલાં અને પછી, આપણે જોઈ શકીએ છીએ કે આ શરતી સંભાવના ખરેખર નીચે પ્રમાણે સરળ થઈ શકે છેઃ સકારાત્મક વસ્તુ માત્ર બીટા પશ્ચાદવર્તી પર આધાર રાખે છે, તેથી, જો બીટા વિતરણ કાર્યના પરિમાણનું કાર્ય a અને b હોય, તો આ ચોક્કસ વસ્તુ માટે વધુ એક લેબલ તરીકે, આપણે પશ્ચાદવર્તી કાર્યને બે વાર બદલીએ છીએ, તેથી આ બધી વસ્તુઓને 1 સિવાય રદ કરી શકાય છે, તેથી આ સંપૂર્ણ ચોકસાઈ માટેનો ફેરફાર છે અને આપણે તબક્કાવાર પુરસ્કાર તરીકે વ્યાખ્યાયિત કરીએ છીએઃ વધુ એક નમૂના દ્વારા અનુમાનની ચોકસાઈમાં સુધારો. અલબત્ત આ લેબલનું બે હકારાત્મક મૂલ્ય છે, આપણને સકારાત્મક લેબલ અથવા નકારાત્મક લેબલ મળે છે, આ બંને માટે સરેરાશ લો, અપેક્ષિત પુરસ્કાર મેળવો. આપણે ફક્ત લેબલ કરવા માટે વસ્તુને પસંદ કરીએ છીએ જેથી નોલેજ ગ્રેડિયન્ટનો ઉપયોગ કરીને અપેક્ષિત પુરસ્કાર મહત્તમ થાયઃ તે બહુવિધ વસ્તુઓ છે, ચાલો આપણે કેવી રીતે સંબંધોને તોડી શકીએ. જો આપણે નિર્ધારિત રીતે ટાઇ તોડીએ, જેનો અર્થ છે કે આપણે સૌથી નાનો સૂચકાંક પસંદ કરીએ છીએ. આપણી પાસે એક સમસ્યા હશે કારણ કે આ સુસંગત નથી જેનો અર્થ છે કે સકારાત્મક તબક્કો સાચા સકારાત્મક તબક્કામાં એકરૂપ થતો નથી. તેથી આપણે સંબંધોને અવ્યવસ્થિત રીતે તોડવાનો પણ પ્રયાસ કરી શકીએ છીએ, તે કામ કરે છે, જો કે, આપણે જોશું કે પ્રદર્શન લગભગ સમાન નમૂના જેવું છે, તે શ્રેષ્ઠ પુરસ્કાર છે. લેખકની નીતિ એક પ્રકારની વધુ લોભી છે, એકવાર પુરસ્કારના તબક્કામાં સરેરાશ પસંદ કરવાને બદલે, આપણે ખરેખર મોટા એકની ગણતરી કરી શકીએ છીએ, બે તબક્કાના સંભવિત પુરસ્કારની મહત્તમ, તેથી આશાવાદી જ્ઞાન ઢાળઃ અને આપણે આશાવાદી જ્ઞાન ઢાળ હેઠળ જાણીએ છીએ, અંતિમ અનુમાનની ચોકસાઈ 100% માં એકરૂપ થાય છે. ઉપર દરેક કામદાર સંપૂર્ણ છે તેના પર આધારિત છે, જો કે, વ્યવહારમાં, કામદારો હંમેશા જવાબદાર હોતા નથી. તેથી જો અપૂર્ણ કામદારોમાં, આપણે K વસ્તુઓને ધારીએ છીએ,. એક સંપૂર્ણ કાર્યકર દ્વારા વસ્તુને સકારાત્મક તરીકે લેબલ કરવાની સંભાવના. એમ કામદારો, એક સંપૂર્ણ કાર્યકર તરીકે સમાન લેબલ આપતા કાર્યકરની સંભાવના. કાર્યકરથી વસ્તુ સુધી લેબલનું વિતરણઃ અને ક્રિયાની જગ્યા એ છે કે જ્યાં, લેબલ મેટ્રિક્સઃ તેની ગણતરી કરવી મુશ્કેલ છે, તેથી આપણે સંદર્ભો ગાણિતિક ઓપ્ટિમાઇઝેશન માર્કોવ પ્રક્રિયાઓની વેરિયેશનલ બાયેસિયન પદ્ધતિઓનો ઉપયોગ કરી શકીએ છીએ.