AdaBoost
اڈا بوسٹ، جو اڈاپٹو بوسٹنگ کے لیے مختصر ہے، ایک شماریاتی درجہ بندی میٹا الگورتھم ہے جسے 1995 میں یوو فرونڈ اور رابرٹ شیپائر نے وضع کیا تھا، جنہوں نے اپنے کام کے لیے 2003 کا گوڈل انعام جیتا تھا۔ اسے کارکردگی کو بہتر بنانے کے لیے سیکھنے کے الگورتھم کی بہت سی دوسری اقسام کے ساتھ مل کر استعمال کیا جا سکتا ہے۔ سیکھنے کے دوسرے الگورتھم ('کمزور سیکھنے والے') کی پیداوار کو ایک وزنی رقم میں ملایا جاتا ہے جو بڑھے ہوئے درجہ بندی کے حتمی نتیجہ کی نمائندگی کرتا ہے۔ عام طور پر، اڈابوسٹ کو بائنری درجہ بندی کے لیے پیش کیا جاتا ہے، حالانکہ اسے حقیقی لائن پر متعدد کلاسوں یا پابند وقفوں کے لیے عام کیا جا سکتا ہے۔ اڈا بوسٹ اس لحاظ سے موافقت پذیر ہے کہ بعد میں کمزور سیکھنے والوں کو ان مثالوں کے حق میں تبدیل کیا جاتا ہے جو پچھلے درجہ بندی کرنے والوں کے ذریعہ غلط درجہ بندی کی جاتی ہیں۔ کچھ مسائل میں یہ سیکھنے کے دوسرے الگورتھم کے مقابلے میں زیادہ فٹ ہونے والے مسئلے کے لیے کم حساس ہو سکتا ہے۔ انفرادی سیکھنے والے کمزور ہو سکتے ہیں، لیکن جب تک کہ ہر ایک کی کارکردگی بے ترتیب اندازے لگانے سے قدرے بہتر ہو، حتمی نمونہ ایک مضبوط سیکھنے والے میں ضم ہونے کے لیے ثابت ہو سکتا ہے۔ اگرچہ اڈابووسٹ عام طور پر کمزور بنیادی سیکھنے والوں (جیسے فیصلہ کرنے والے اسٹمپ) کو یکجا کرنے کے لیے استعمال کیا جاتا ہے، لیکن یہ دکھایا گیا ہے کہ یہ مضبوط بنیادی سیکھنے والوں (جیسے گہرے فیصلہ کرنے والے درخت) کو بھی مؤثر طریقے سے جوڑ سکتا ہے، اور اس سے بھی زیادہ درست ماڈل تیار کرتا ہے۔ سیکھنے کا ہر الگورتھم کچھ مسائل کی اقسام کو دوسروں کے مقابلے میں بہتر طریقے سے فٹ کرتا ہے، اور عام طور پر ڈیٹا سیٹ پر زیادہ سے زیادہ کارکردگی حاصل کرنے سے پہلے ایڈجسٹ کرنے کے لیے بہت سے مختلف پیرامیٹرز اور ترتیبات ہوتے ہیں۔ اڈا بوسٹ (کمزور سیکھنے والوں کے طور پر فیصلہ کن درختوں کے ساتھ) کو اکثر بہترین آؤٹ آف دی باکس درجہ بندی کہا جاتا ہے۔ جب فیصلہ ٹری سیکھنے کے ساتھ استعمال کیا جاتا ہے، تو اڈابوسٹ الگورتھم کے ہر مرحلے پر ہر تربیتی نمونے کی متعلقہ 'سختی' کے بارے میں جمع کی گئی معلومات کو درخت اگانے والے الگورتھم میں اس طرح کھلایا جاتا ہے کہ بعد کے درخت مشکل سے درجہ بندی کرنے والی مثالوں پر توجہ مرکوز کرتے ہیں۔ اڈا بوسٹ کی تربیت سے مراد ایک بوسٹڈ کلاسیفائر کی تربیت کا ایک خاص طریقہ ہے۔ بوسٹڈ کلاسیفائر اس فارم کا درجہ بندی کرنے والا ہوتا ہے جہاں ہر ایک کمزور سیکھنے والا ہوتا ہے جو کسی شے کو ان پٹ کے طور پر لیتا ہے اور شے کی کلاس کی نشاندہی کرنے والی قدر واپس کرتا ہے۔ مثال کے طور پر، دو درجے کے مسئلے میں، کمزور سیکھنے والے کے آؤٹ پٹ کی علامت پیش گوئی شدہ آبجیکٹ کلاس کی شناخت کرتی ہے اور مطلق قدر اس درجہ بندی میں اعتماد دیتی ہے۔ اسی طرح،-th درجہ بندی مثبت ہے اگر نمونہ مثبت کلاس میں ہے اور بصورت دیگر منفی ہے۔ ہر کمزور سیکھنے والا ایک آؤٹ پٹ مفروضہ تیار کرتا ہے جو تربیتی سیٹ میں ہر نمونے کے لیے پیش گوئی طے کرتا ہے۔ ہر تکرار پر، ایک کمزور سیکھنے والے کا انتخاب کیا جاتا ہے اور اسے ایک گتانک اس طرح تفویض کیا جاتا ہے کہ نتیجے میں-مرحلے کے فروغ شدہ درجہ بندی کی کل تربیتی غلطی کو کم سے کم کیا جائے۔ یہاں فروغ شدہ درجہ بندی ہے جو تربیت کے پچھلے مرحلے تک بنائی گئی ہے اور کمزور سیکھنے والا ہے جس پر حتمی درجہ بندی کے علاوہ غور کیا جا رہا ہے۔ وزن تربیتی عمل کے ہر تکرار پر، تربیتی سیٹ میں ہر نمونے کو اس نمونے پر موجودہ غلطی کے برابر وزن تفویض کیا جاتا ہے۔ ان وزنوں کو کمزور سیکھنے والے کی تربیت میں استعمال کیا جا سکتا ہے۔ مثال کے طور پر، فیصلہ کن درخت اگائے جا سکتے ہیں جو بڑے وزن والے نمونوں کے سیٹ کو تقسیم کرنے کے حق میں ہیں۔ مشتق یہ مشتق روجاس (2009) کی پیروی کرتا ہے: فرض کریں کہ ہمارے پاس ایک ڈیٹا سیٹ ہے جہاں ہر آئٹم کا ایک وابستہ کلاس ہے، اور کمزور درجہ بندی کا ایک سیٹ ہے جس میں سے ہر ایک آئٹم کے لیے درجہ بندی کرتا ہے۔ - th تکرار کے بعد ہمارا بڑھا ہوا درجہ بندی فارم کے کمزور درجہ بندی کا ایک لکیری مجموعہ ہے:، جہاں کلاس کی علامت ہوگی۔ - th تکرار میں ہم ایک اور کمزور درجہ بندی کو ایک اور وزن کے ساتھ شامل کرکے اسے بہتر بوسٹڈ درجہ بندی تک بڑھانا چاہتے ہیں: لہذا یہ طے کرنا باقی ہے کہ کون سا کمزور درجہ بندی بہترین انتخاب ہے، اور اس کا وزن کیا ہونا چاہیے۔ ہم کی کل غلطی کو ہر ڈیٹا پوائنٹ پر اس کے ایکسپونینشل نقصان کے مجموعے کے طور پر بیان کرتے ہیں، جو مندرجہ ذیل ہے: لیٹنگ اور فار، ہمارے پاس ہے: ہم اس خلاصہ کو ان ڈیٹا پوائنٹس کے درمیان تقسیم کر سکتے ہیں جن کی صحیح درجہ بندی (اس طرح) کی گئی ہے اور جن کی غلط درجہ بندی کی گئی ہے (اس طرح): چونکہ اس مساوات کے دائیں طرف کا واحد حصہ جس پر منحصر ہے، ہم دیکھتے ہیں کہ کم سے کم وہ ہے جو [فرض کرتے ہوئے] کم سے کم کرتا ہے، یعنی۔ کمزور درجہ بندی سب سے کم وزن کی غلطی کے ساتھ (وزن کے ساتھ)۔ مطلوبہ وزن کا تعین کرنے کے لیے جو ہم نے ابھی طے کیا ہے اس کے ساتھ کم سے کم ہوتا ہے، ہم فرق کرتے ہیں: خوش قسمتی سے کم سے کم اس وقت ہوتا ہے جب اسے صفر پر سیٹ کرتے ہیں، پھر پیداوار کے لیے حل کرتے ہیں: ہم کمزور درجہ بندی کے وزن کی غلطی کی شرح کا حساب لگاتے ہیں، لہذا یہ اس کے بعد ہوتا ہے: جو منفی لاگٹ فنکشن ہے جسے 0.0 سے ضرب دی جاتی ہے۔ ایک فنکشن کے طور پر کے کنویکسٹی کی وجہ سے، یہ نیا اظہار نقصان فنکشن کا عالمی کم از کم دیتا ہے۔ نوٹ: یہ مشتق صرف اس وقت لاگو ہوتا ہے، حالانکہ یہ دوسرے معاملات میں ایک اچھا ابتدائی اندازہ ہو سکتا ہے، جیسے کہ جب کمزور سیکھنے والا متعصبانہ () ہو، اس کے کئی پتے () ہوں یا کوئی اور فنکشن ہو۔ اس طرح ہم نے اڈابوسٹ الگورتھم اخذ کیا ہے: ہر تکرار پر، درجہ بندی کا انتخاب کریں، جو کل وزن کی غلطی کو کم سے کم کرتا ہے، غلطی کی شرح کا حساب لگانے کے لیے اس کا استعمال کریں، وزن کا حساب لگانے کے لیے اس کا استعمال کریں، اور آخر میں اس کا استعمال بڑھا ہوا درجہ بندی کو بہتر بنانے کے لیے کریں۔ بوسٹنگ کی شماریاتی تفہیم لکیری رجعت کی ایک شکل ہے جس میں ہر نمونے کی خصوصیات کچھ کمزور سیکھنے والے کے نتائج پر لاگو ہوتی ہیں۔ اگرچہ رجعت عمومی کاری کے نقصان کے بغیر زیادہ سے زیادہ درست طریقے سے فٹ ہونے کی کوشش کرتی ہے، عام طور پر کم سے کم مربع غلطی کا استعمال کرتے ہوئے، جبکہ اڈابوسٹ ایرر فنکشن اس حقیقت کو مدنظر رکھتا ہے کہ صرف حتمی نتیجہ کی علامت استعمال کی جاتی ہے، اس طرح غلطی میں اضافہ کیے بغیر 1 سے کہیں زیادہ بڑی ہو سکتی ہے۔ تاہم، جیسے جیسے نمونے کی غلطی میں تیزی سے اضافہ ہوتا جاتا ہے۔ اس کے نتیجے میں آؤٹ لیئرز کو زیادہ وزن تفویض کیا جاتا ہے۔ ایکسپونینشل ایرر فنکشن کے انتخاب کی ایک خصوصیت یہ ہے کہ حتمی اضافی ماڈل کی غلطی ہر مرحلے کی غلطی کا نتیجہ ہے، یعنی۔ اس طرح یہ دیکھا جا سکتا ہے کہ اڈابوسٹ الگورتھم میں وزن کی اپ ڈیٹ ہر مرحلے کے بعد غلطی کا دوبارہ حساب لگانے کے برابر ہے۔ لاس فنکشن کے انتخاب میں بہت زیادہ لچک کی اجازت ہے۔ جب تک نقصان کا فنکشن مونوٹونک اور مسلسل تفریق پذیر ہے، درجہ بندی کرنے والا ہمیشہ صاف حل کی طرف بڑھتا ہے۔ ژانگ (2004) کم سے کم مربعوں پر مبنی نقصان فنکشن فراہم کرتا ہے، ایک ترمیم شدہ ہیوبر نقصان فنکشن: یہ فنکشن 1 یا-1 کے قریب کے لیے لاجٹ بوسٹ سے زیادہ اچھی طرح سے برتاؤ کرتا ہے، غیر تبدیل شدہ کم سے کم مربعوں کے برعکس 'حد سے زیادہ اعتماد' کی پیش گوئیوں () کو سزا نہیں دیتا ہے، اور صرف 1 سے زیادہ اعتماد کے ساتھ غلط درجہ بندی کے نمونوں کو لکیری طور پر سزا دیتا ہے، جیسا کہ چوتھائی یا تیزی سے ہوتا ہے، اور اس طرح آؤٹ لیئر کے اثرات کے لیے کم حساس ہے۔ گریڈینٹ ڈیسنٹ کے طور پر فروغ دینا بوسٹنگ کو افعال کے کنویکس سیٹ پر کنویکس لاس فنکشن کو کم سے کم کرنے کے طور پر دیکھا جا سکتا ہے۔ خاص طور پر، اڈابوسٹ کے ذریعہ کم سے کم ہونے والا نقصان ایکسپونینشل نقصان ہے، جبکہ لاجٹک بوسٹ لاجسٹک ریگریشن انجام دیتا ہے، کم سے کم کرتا ہے۔ گریڈیئنٹ ڈیسنٹ اینالاجی میں، ہر ٹریننگ پوائنٹ کے لیے کلاسیفائر کی آؤٹ پٹ کو n-جہتی جگہ میں ایک نقطہ سمجھا جاتا ہے، جہاں ہر محور ٹریننگ نمونے سے مطابقت رکھتا ہے، ہر کمزور سیکھنے والا مقررہ واقفیت اور لمبائی کے ویکٹر سے مطابقت رکھتا ہے، اور ہدف تک پہنچنا ہے (یا کسی بھی خطے میں جہاں نقصان کی تقریب کی قیمت اس مقام پر قدر سے کم ہے)، کم ترین مراحل میں۔ اس طرح اڈابوسٹ الگورتھم یا تو کاچی (تیز ترین میلان کے ساتھ تلاش کریں، ٹیسٹ کی غلطی کو کم سے کم کرنے کا انتخاب کریں) یا نیوٹن (کچھ ٹارگٹ پوائنٹ کا انتخاب کریں، جو اس نقطہ کے قریب لاتا ہے) ٹریننگ ایرر کی اصلاح انجام دیتے ہیں۔ مثال الگورتھم (ڈسکریٹ اڈابوسٹ) کے ساتھ: نمونے مطلوبہ آؤٹ پٹ ابتدائی وزن کو ایرر فنکشن کمزور سیکھنے والوں کے لیے سیٹ کیا گیا ہے۔ ان کے لیے: منتخب کریں: کمزور سیکھنے والے کو تلاش کریں جو کم سے کم ہو، غلط درجہ بندی والے پوائنٹس کے لیے وزن کی رقم کی غلطی انسمبل میں اضافہ کا انتخاب کریں: وزن کو اپ ڈیٹ کریں: کیونکہ ری نارملائز کرنے میں ایسا ہو کہ (نوٹ: یہ ہر مرحلے پر دکھایا جا سکتا ہے، جو نئے وزن کے حساب کو آسان بنا سکتا ہے۔) متغیرات اصلی اڈا بوسٹ فیصلہ کے درختوں کی پیداوار ایک کلاس امکانات کا تخمینہ ہے، امکان جو مثبت کلاس میں ہے۔ فریڈمین، ہاسٹی اور تبشیرانی کچھ فکسڈ (عام طور پر ویٹڈ لیسٹ اسکوائرز ایرر کا استعمال کرتے ہوئے منتخب کیا جاتا ہے) کے لیے ایک تجزیاتی کم سے کم حاصل کرتے ہیں: اس طرح، پورے درخت کی پیداوار کو کسی مقررہ قیمت سے ضرب دینے کے بجائے، ہر لیف نوڈ کو اس کی پچھلی قیمت کے آدھے لاگٹ ٹرانسفارم آؤٹ پٹ میں تبدیل کر دیا جاتا ہے۔ لاجٹ بوسٹ لاجٹ بوسٹ اڈابوسٹ طریقہ کار میں قائم شدہ لاجسٹک رجعت کی تکنیکوں کے اطلاق کی نمائندگی کرتا ہے۔ Y کے حوالے سے غلطی کو کم سے کم کرنے کے بجائے، کمزور سیکھنے والوں کو (وزن والے کم سے کم مربع) غلطی کو کم کرنے کے لیے منتخب کیا جاتا ہے جہاں اس مرحلے پر لاگ-لیکلی ہڈ ایرر کے کم سے کم کرنے والے کا نیوٹن-رافسن تخمینہ ہے، اور کمزور سیکھنے والے کو سیکھنے والے کے طور پر منتخب کیا جاتا ہے جو وزن والے کم سے کم مربعوں سے بہترین انداز میں اندازہ کرتا ہے۔ جیسے جیسے p 1 یا 0 کے قریب آتا ہے، کی قدر بہت چھوٹی ہو جاتی ہے اور Z اصطلاح، جو غلط درجہ بند نمونوں کے لیے بڑی ہے، مشین کی صحت سے متعلق گول کی غلطیوں کی وجہ سے عددی طور پر غیر مستحکم ہو سکتی ہے۔ اس پر Z کی مطلق قیمت اور W Gentle AdaBoost کی کم از کم قیمت پر کچھ حد نافذ کرکے قابو پایا جاسکتا ہے جبکہ پچھلے فروغ دینے والے الگورتھم لالچ سے انتخاب کرتے ہیں، ہر مرحلے پر مجموعی ٹیسٹ کی غلطی کو زیادہ سے زیادہ کم کرتے ہیں، GentleBoost ایک باؤنڈ اسٹیپ سائز پیش کرتا ہے۔ کم کرنے کے لیے منتخب کیا جاتا ہے، اور کوئی مزید گتانک لاگو نہیں کیا جاتا ہے۔ اس طرح، اس صورت میں جہاں ایک کمزور سیکھنے والا درجہ بندی کی کامل کارکردگی کا مظاہرہ کرتا ہے، جنٹل بوسٹ بالکل برابر کا انتخاب کرتا ہے، جبکہ اسٹپیسٹ ڈیسنٹ الگورتھم سیٹ کرنے کی کوشش کرتے ہیں۔ جنٹل بوسٹ کی اچھی کارکردگی کے بارے میں تجرباتی مشاہدات شیپائر اور سنگر کے اس بیان کی پشت پناہی کرتے دکھائی دیتے ہیں کہ زیادہ سے زیادہ بڑی اقدار کی اجازت دینے سے عمومی کارکردگی خراب ہو سکتی ہے۔ ارلی ٹرمینیشن بوسٹڈ کلاسیفائیرز کی پروسیسنگ کو تیز کرنے کے لیے ایک تکنیک، ارلی ٹرمینیشن سے مراد صرف ہر ممکنہ شے کی حتمی درجہ بندی کی زیادہ سے زیادہ تہوں کے ساتھ جانچ کرنا ہے جو کچھ اعتماد کی حد کو پورا کرنے کے لیے ضروری ہے، ایسے معاملات کے لیے حساب کو تیز کرنا جہاں شے کی کلاس کا آسانی سے تعین کیا جا سکتا ہے۔ ایسی ہی ایک اسکیم وائیولا اور جونز کی طرف سے متعارف کرایا گیا آبجیکٹ ڈٹیکشن فریم ورک ہے: مثبت سے نمایاں طور پر زیادہ منفی نمونوں والی ایپلی کیشن میں، علیحدہ بوسٹ کلاسیفائرز کا ایک جھرن تربیت یافتہ ہوتا ہے، ہر مرحلے کی آؤٹ پٹ اس طرح متعصبانہ ہوتی ہے کہ مثبت نمونوں کے کچھ قابل قبول چھوٹے حصے کو منفی کے طور پر غلط لیبل کیا جاتا ہے، اور ہر مرحلے کے بعد منفی کے طور پر نشان زد تمام نمونوں کو خارج کر دیا جاتا ہے۔ اگر 50 ٪ منفی نمونوں کو ہر مرحلے سے فلٹر کیا جاتا ہے، تو صرف بہت کم تعداد میں اشیاء پورے درجہ بندی سے گزر جائیں گی، جس سے کمپیوٹیشن کی کوشش کم ہو جائے گی۔ اس کے بعد سے اس طریقہ کو عام کیا گیا ہے، جس میں کچھ مطلوبہ غلط مثبت اور غلط منفی شرح حاصل کرنے کے لیے ہر مرحلے پر زیادہ سے زیادہ حد کا انتخاب کرنے کے لیے ایک فارمولا فراہم کیا گیا ہے۔ اعداد و شمار کے میدان میں، جہاں اڈابووسٹ کا اطلاق عام طور پر اعتدال پسند جہت کے مسائل پر کیا جاتا ہے، ابتدائی روک تھام کو اوورفٹنگ کو کم کرنے کی حکمت عملی کے طور پر استعمال کیا جاتا ہے۔ نمونوں کے توثیق سیٹ کو تربیتی سیٹ سے الگ کیا جاتا ہے، تربیت کے لیے استعمال ہونے والے نمونوں پر درجہ بندی کرنے والے کی کارکردگی کا موازنہ توثیق کے نمونوں پر کارکردگی سے کیا جاتا ہے، اور اگر توثیق کے نمونے پر کارکردگی میں کمی نظر آتی ہے تو تربیت ختم کر دی جاتی ہے یہاں تک کہ جب تربیتی سیٹ پر کارکردگی میں بہتری آتی رہتی ہے۔ مکمل طور پر اصلاحی الگورتھم اڈابوسٹ کے تیز ترین نزول ورژن کے لیے، جہاں ٹیسٹ کی غلطی کو کم کرنے کے لیے ہر پرت ٹی پر منتخب کیا جاتا ہے، اگلی پرت کو پرت ٹی سے زیادہ سے زیادہ آزاد کہا جاتا ہے: کمزور سیکھنے والے ٹی + 1 کا انتخاب کرنے کا امکان نہیں ہے جو سیکھنے والے ٹی سے ملتا جلتا ہے۔ تاہم، اس بات کا امکان باقی ہے کہ ٹی + 1 کسی دوسری سابقہ پرت سے ملتی جلتی معلومات پیدا کرے۔ مکمل طور پر اصلاحی الگورتھم، جیسے کہ ایل پی بوسٹ، ہر مرحلے کے بعد ہر گتانک کی قدر کو بہتر بناتے ہیں، تاکہ شامل کی گئی نئی پرتیں ہمیشہ ہر پچھلی پرت سے زیادہ سے زیادہ آزاد ہوں۔ یہ بیک فٹنگ، لکیری پروگرامنگ یا کسی اور طریقے سے پورا کیا جا سکتا ہے۔ کٹائی کٹائی ناقص کارکردگی کا مظاہرہ کرنے والے کمزور درجہ بندی کرنے والوں کو ہٹانے کا عمل ہے تاکہ بہتر درجہ بندی کرنے والے کی یادداشت اور عمل درآمد کے وقت کی لاگت کو بہتر بنایا جا سکے۔ سب سے آسان طریقے، جو مکمل طور پر اصلاحی تربیت کے ساتھ مل کر خاص طور پر موثر ہو سکتے ہیں، وزن-یا مارجن-ٹرمنگ ہیں: جب کچھ کمزور درجہ بندی کا گتانک، یا کل ٹیسٹ کی غلطی میں حصہ، ایک خاص حد سے نیچے گر جاتا ہے، تو درجہ بندی کو چھوڑ دیا جاتا ہے۔ مارگینیانٹو اور ڈائیٹٹریچ نے تراشنے کے لیے ایک متبادل معیار تجویز کیا: کمزور درجہ بندی کا انتخاب اس طرح کیا جانا چاہیے کہ ملبوسات کا تنوع زیادہ سے زیادہ ہو۔ اگر دو کمزور سیکھنے والے ایک جیسے نتائج پیدا کرتے ہیں، تو ان میں سے ایک کو ہٹا کر اور باقی کمزور سیکھنے والے کے گتانک کو بڑھا کر کارکردگی کو بہتر بنایا جا سکتا ہے۔ بوٹسٹریپ ایگریگیٹنگ کوبوسٹنگ براؤن بوسٹ گریڈینٹ بوسٹنگ حوالہ جات مزید پڑھنے کے لیے یواو فرائنڈ اور رابرٹ E.Schapire کا اصل مقالہ بھی دیکھیں جہاں اڈابسٹ کو پہلی بار متعارف کرایا گیا ہے۔ بوسٹنگ الگورتھم کی مارجن وضاحت پر۔ مارجن کے بارے میں شک پر بوسٹنگ کی وضاحت۔ درجہ بندی الگورتھم انسمبل لرننگ