Optimistic knowledge gradient
اعداد و شمار میں پر امید علم کا میلان ایک تخمینہ پالیسی ہے جو 2013 میں ژی چن، کیہانگ لن اور ڈینگیونگ چاؤ نے تجویز کی تھی۔ یہ پالیسی بائنری/ملٹی کلاس ہجوم لیبلنگ میں زیادہ سے زیادہ کمپیوٹنگ بجٹ مختص کرنے کے مسئلے کے بڑے سائز کے کمپیوٹیشنل طور پر ناقابل حل چیلنج کو حل کرنے کے لیے بنائی گئی ہے جہاں ہجوم کے ہر لیبل کی ایک خاص قیمت ہوتی ہے۔ موٹیویشن زیادہ سے زیادہ کمپیوٹنگ بجٹ مختص کرنے کا مسئلہ بایسیئن مارکوف فیصلہ عمل (ایم ڈی پی) کے طور پر وضع کیا گیا ہے اور اسے متحرک پروگرامنگ (ڈی پی) الگورتھم کا استعمال کرتے ہوئے حل کیا جاتا ہے جہاں متحرک پروگرامنگ (ڈی پی) الگورتھم کے کمپیوٹیشنل طور پر ناقابل تلافی کو حل کرنے کے لیے آپٹیمسٹک نالج گریڈینٹ پالیسی کا استعمال کیا جاتا ہے۔ کراؤڈ سورسنگ میں بجٹ مختص کرنے کے مسئلے پر غور کریں۔ خاص طور پر ہجوم سورسنگ کا مسئلہ جس پر ہم غور کر رہے ہیں وہ ہجوم لیبلنگ ہے۔ کراؤڈ لیبلنگ لیبلنگ کے کاموں کی ایک بڑی مقدار ہے جسے مشین کے ذریعے حل کرنا مشکل ہے، انسانوں کے ذریعے حل کرنا آسان ہو جاتا ہے، پھر ہم صرف تقسیم شدہ ماحول میں بے ترتیب لوگوں کے ایک نامعلوم گروپ کو آؤٹ سورس کرتے ہیں۔ طریقہ کار ہم اس لیبلنگ کے کاموں کو ختم کرنا چاہتے ہیں امید ہے کہ ہجوم کی طاقت پر انحصار کریں۔ مثال کے طور پر، فرض کریں کہ ہم تصویر میں موجود لوگوں کے مطابق کسی تصویر کی شناخت کرنا چاہتے ہیں کہ وہ بالغ ہے یا نہیں، یہ برنولی لیبلنگ کا مسئلہ ہے، اور ہم سب ایک یا دو سیکنڈ میں کر سکتے ہیں، یہ انسان کے لیے ایک آسان کام ہے۔ تاہم، اگر ہمارے پاس اس طرح کی دسیوں ہزار تصاویر ہیں، تو یہ اب آسان کام نہیں ہے۔ اس لیے ہمیں اسے تیز کرنے کے لیے کراؤڈ سورسنگ فریم ورک پر انحصار کرنے کی ضرورت ہے۔ اس کا کراؤڈ سورسنگ فریم ورک دو مراحل پر مشتمل ہے۔ پہلا قدم، ہم صرف اشیاء کے لیے ہجوم سے متحرک طور پر حاصل کرتے ہیں۔ دوسری طرف، یہ متحرک طریقہ کار ہے۔ ہم یہ تصویر صرف سب کو نہیں بھیجتے اور ہم ہر جواب پر توجہ مرکوز کرتے ہیں، اس کے بجائے، ہم یہ مقدار میں کرتے ہیں۔ ہم فیصلہ کرنے جا رہے ہیں کہ ہم اسے اگلے میں کون سی تصویر بھیجیں گے، اور اگلے میں ہم ہجوم میں کس کارکن کی خدمات حاصل کرنے جا رہے ہیں۔ اس کے تاریخی لیبلنگ کے نتائج کے مطابق۔ اور ہر تصویر کو متعدد کارکنوں کو بھیجا جا سکتا ہے اور ہر کارکن مختلف تصاویر پر بھی کام کر سکتا ہے۔ پھر مختلف تصویر کے لیے کافی تعداد میں لیبل جمع کرنے کے بعد، ہم دوسرے مراحل پر جاتے ہیں جہاں ہم جمع کردہ لیبل کی بنیاد پر ہر تصویر کے حقیقی لیبل کا اندازہ لگانا چاہتے ہیں۔ لہذا متعدد طریقے ہیں جن سے ہم اندازہ لگا سکتے ہیں۔ مثال کے طور پر، سب سے آسان کام جو ہم کر سکتے ہیں وہ ہے صرف اکثریت کا ووٹ۔ مسئلہ یہ ہے کہ مفت دوپہر کا کھانا نہیں، ہمیں کارکن کو اس کے فراہم کردہ ہر لیبل کے لیے ادائیگی کرنی پڑتی ہے اور ہمارے پاس صرف ایک محدود پروجیکٹ بجٹ ہے۔ تو سوال یہ ہے کہ محدود بجٹ کو ہوشیار طریقے سے کیسے خرچ کیا جائے۔ چیلنجز ریاضی کا نمونہ دکھانے سے پہلے، مقالے میں بتایا گیا ہے کہ ہمیں کس قسم کے چیلنجوں کا سامنا ہے۔ چیلنج 1 سب سے پہلے، اشیاء کو لیبل کا حساب لگانے میں مختلف سطح کی دشواری ہوتی ہے، پچھلی مثال میں، کچھ تصویروں کی درجہ بندی کرنا آسان ہے۔ اس صورت میں، آپ کو عام طور پر ہجوم سے بہت مستقل لیبل نظر آئیں گے۔ تاہم، اگر کچھ تصاویر مبہم ہیں، تو لوگ ایک دوسرے سے اختلاف کر سکتے ہیں جس کے نتیجے میں انتہائی متضاد لیبلنگ ہو سکتی ہے۔ لہذا ہم اس مبہم کام پر مزید وسائل مختص کر سکتے ہیں۔ چیلنج 2 اور ایک اور مشکل جو ہمیں اکثر درپیش ہوتی ہے وہ یہ ہے کہ کارکن کامل نہیں ہوتا، بعض اوقات یہ کارکن ذمہ دار نہیں ہوتا، وہ صرف بے ترتیب لیبل فراہم کرتے ہیں، اس لیے یقینا ہم اپنا بجٹ اس قابل اعتماد کارکن پر خرچ نہیں کریں گے۔ اب مسئلہ تصویروں کی دشواری اور کارکن کی وشوسنییتا دونوں ہیں جن سے ہم شروع میں بالکل ناواقف تھے۔ ہم صرف طریقہ کار کے دوران ان کا اندازہ لگا سکتے ہیں۔ لہذا، ہم فطری طور پر ایکسپلوریشن اور استحصال کا سامنا کر رہے ہیں، اور ہمارا مقصد صحیح طریقے سے پیسہ خرچ کرنے کے لیے ایک معقول اچھی پالیسی دینا ہے-حتمی قیاس شدہ لیبلز کی مجموعی درستگی کو زیادہ سے زیادہ کرنا۔ ریاضیاتی ماڈل کے لیے، ہمارے پاس K آئٹمز ہیں، اور کل بجٹ T ہے اور ہم فرض کرتے ہیں کہ ہر لیبل کی قیمت 1 ہے لہذا ہم آخر کار T لیبل حاصل کرنے جا رہے ہیں۔ ہم فرض کرتے ہیں کہ ہر آئٹم کا حقیقی لیبل ہے جو مثبت یا منفی ہے، یہ بائنومیل کیس اور ہم متعدد کلاس، لیبلنگ کیسوں تک بڑھا سکتے ہیں، یہ ایک واحد خیال ہے۔ اور مثبت سیٹ کو آئٹمز کے سیٹ کے طور پر بیان کیا جاتا ہے جس کا حقیقی لیبل مثبت ہوتا ہے۔ اور ایک سافٹ لیبل کی بھی وضاحت کی، ہر آئٹم کے لیے جس کی تعداد 0 اور 1 کے درمیان ہے، اور ہم کامل کارکنوں کے گروپ سے تصادفی طور پر منتخب کردہ ممبر کے ذریعے مثبت کے طور پر لیبل کیے جانے کے بنیادی امکان کے طور پر بیان کرتے ہیں۔ اس پہلی صورت میں، ہم فرض کرتے ہیں کہ ہر کارکن کامل ہے، اس کا مطلب ہے کہ وہ سب قابل اعتماد ہیں، لیکن کامل ہونے کا مطلب یہ نہیں ہے کہ یہ کارکن ایک ہی جواب یا صحیح جواب دیتا ہے۔ اس کا صرف یہ مطلب ہے کہ وہ اپنے ذہن میں بہترین جواب تلاش کرنے کی پوری کوشش کریں گے، اور فرض کریں کہ ہر کوئی کامل کارکن ہے، صرف تصادفی طور پر ان میں سے ایک کو منتخب کیا، اور امکان کے ساتھ، ہمیں ایک ایسا لڑکا ملے گا جو یقین کرے کہ یہ مثبت ہے۔ اس طرح ہم وضاحت کرتے ہیں۔ لہذا ہم فرض کرتے ہیں کہ ایک لیبل برنولی () سے تیار کیا گیا ہے، اور اسے حقیقی لیبل کے مطابق ہونا چاہیے، جس کا مطلب ہے کہ 0.0 سے بڑا یا اس کے برابر ہے اگر اور صرف اس صورت میں جب یہ آئٹم حقیقی مثبت لیبل کے ساتھ مثبت ہو۔ لہذا ہمارا مقصد H *، مثبت آئٹمز کا مجموعہ سیکھنا ہے۔ دوسرے لفظوں میں، ہم زیادہ سے زیادہ کرنے کے لیے جمع شدہ لیبلز کی بنیاد پر ایک قیاس شدہ مثبت سیٹ H بنانا چاہتے ہیں: اسے اس طرح بھی لکھا جا سکتا ہے: مرحلہ 1: بایسیئن فیصلہ کا عمل بایسیئن فریم ورک کو دکھانے سے پہلے، کاغذ ایک مثال استعمال کرتا ہے کہ ہم فریکوئنسی اپروچ کے بجائے بایسیئن کا انتخاب کیوں کرتے ہیں، جیسے کہ ہم سافٹ لیبل پر پہلے کی تقسیم کے کچھ پوسٹر کی تجویز کر سکتے ہیں۔ ہم فرض کرتے ہیں کہ ہر ایک پہلے سے معلوم بیٹا سے تیار کیا گیا ہے: اور میٹرکس: لہذا ہم جانتے ہیں کہ بیٹا کا برنولی کنجوگیٹ، لہذا ایک بار جب ہمیں آئٹم i کے لیے نیا لیبل مل جاتا ہے، تو ہم پوسٹر ڈسٹری بیوشن کو اپ ڈیٹ کرنے جا رہے ہیں، بیٹا ڈسٹری بیوشن اس طرح: لیبل پر منحصر ہے کہ مثبت یا منفی ہے۔ یہاں اعلی سطح کا پورا طریقہ کار ہے، ہمارے پاس ٹی مرحلہ ہے۔ اور موجودہ مرحلے میں ہم میٹرکس S کو دیکھتے ہیں، جس میں تمام کے لیے پوسٹریر ڈسٹری بیوشن کی معلومات کا خلاصہ کیا گیا ہے۔ اور اس پر منحصر ہے کہ لیبل مثبت یا منفی کیا ہے، ہم لیبل حاصل کرنے کے لیے ایک میٹرکس شامل کرتے ہیں: سب سے بڑھ کر، یہ پورا فریم ورک ہے۔ مرحلہ 2: مثبت سیٹ پر اندازہ جب ٹی لیبل جمع کیے جاتے ہیں، تو ہم سینٹ کی طرف سے دی گئی پوسٹر ڈسٹری بیوشن کی بنیاد پر مثبت سیٹ ایچ ٹی کے بارے میں اندازہ لگا سکتے ہیں۔ یہ جاننے کے بعد کہ بہترین حل کیا ہے، پھر کاغذ دکھاتا ہے کہ بہترین قیمت کیا ہے۔ بہترین فنکشن میں پلگ کریں، یہ فنکشن صرف ایک واحد فنکشن ہے جو مثبت ہونے اور منفی ہونے کے مشروط امکان کے درمیان بڑے فنکشن کا انتخاب کرتا ہے۔ ایک بار جب ہم آئٹم i کے لیے ایک اور لیبل حاصل کر لیتے ہیں، تو ہم اس قدر کے درمیان فرق کرتے ہیں، نیا لیبل حاصل کرنے سے پہلے اور بعد میں، ہم دیکھ سکتے ہیں کہ یہ مشروط امکان دراصل مندرجہ ذیل طور پر آسان ہو سکتا ہے: مثبت آئٹم کا مثبت ہونا صرف بیٹا پوسٹرئیر پر منحصر ہے، لہذا، اگر صرف بیٹا ڈسٹری بیوشن فنکشن کے پیرامیٹر کا فنکشن a اور b ہے، اس مخصوص آئٹم کے لیے ایک اور لیبل کے طور پر، ہم پوسٹرئیر فنکشن کو دوگنا تبدیل کرتے ہیں، لہذا 1 کے علاوہ ان تمام آئٹمز کو منسوخ کیا جا سکتا ہے، لہذا یہ پوری درستگی کے لیے تبدیلی ہے اور ہم نے مرحلہ وار انعام کے طور پر تعریف کی ہے: ایک اور نمونے سے تخمینہ کی درستگی کو بہتر بنائیں۔ یقینا اس لیبل کی دو مثبت قدر ہیں، ہمیں مثبت لیبل یا منفی لیبل ملتا ہے، ان دونوں کے لیے اوسط لیتے ہیں، متوقع انعام حاصل کرتے ہیں۔ ہم صرف لیبل والی چیز کا انتخاب اس طرح کرتے ہیں کہ نالج گریڈینٹ کا استعمال کرتے ہوئے متوقع انعام کو زیادہ سے زیادہ کیا جائے: وہ متعدد آئٹمز ہیں، ہمیں بتائیں کہ ہم تعلقات کو کیسے توڑتے ہیں۔ اگر ہم ٹائی کو تعیناتی طور پر توڑتے ہیں، جس کا مطلب ہے کہ ہم سب سے چھوٹے انڈیکس کا انتخاب کرتے ہیں۔ ہمیں ایک مسئلہ درپیش ہونے والا ہے کیونکہ یہ مستقل نہیں ہے جس کا مطلب ہے کہ مثبت مرحلہ حقیقی مثبت مرحلے میں تبدیل نہیں ہوتا ہے۔ لہذا ہم بے ترتیب طور پر تعلقات کو توڑنے کی بھی کوشش کر سکتے ہیں، یہ کام کرتا ہے، تاہم، ہم دیکھیں گے کہ کارکردگی تقریبا یکساں نمونے لینے کی طرح ہے، بہترین انعام ہے۔ مصنف کی پالیسی ایک طرح سے زیادہ لالچی ہے، ایک بار انعام کے مرحلے میں اوسط کا انتخاب کرنے کے بجائے، ہم اصل میں بڑے کا حساب لگا سکتے ہیں، دو مرحلے کے ممکنہ انعام کا زیادہ سے زیادہ، لہذا پر امید علم میلان: اور ہم پر امید علم میلان کے تحت جانتے ہیں، حتمی تخمینہ کی درستگی 100% میں ضم ہو جاتی ہے۔ اوپر اس بات پر مبنی ہے کہ ہر کارکن کامل ہے، تاہم عملی طور پر کارکن ہمیشہ ذمہ دار نہیں ہوتے ہیں۔ لہذا اگر نامکمل کارکنوں میں، ہم K آئٹمز کو فرض کرتے ہیں،۔ ایک کامل کارکن کے ذریعہ آئٹم کو مثبت کے طور پر لیبل کیے جانے کا امکان۔ ایم کارکنان، ایک کامل کارکن کے طور پر ایک ہی لیبل دینے والے کارکن کا امکان۔ کارکن سے آئٹم میں لیبل کی تقسیم: اور عمل کی جگہ وہ ہے جہاں، لیبل میٹرکس: اس کا حساب لگانا مشکل ہے، لہذا ہم حوالہ جات ریاضیاتی اصلاح مارکوف کے عمل کے متغیر بایسیائی طریقے استعمال کر سکتے ہیں۔