Stochastic variance reduction
(سٹوچسٹک) تغیرات میں کمی افعال کو کم سے کم کرنے کے لیے ایک الگورتھمک نقطہ نظر ہے جسے محدود جملوں میں تقسیم کیا جا سکتا ہے۔ محدود رقم کے ڈھانچے کا استحصال کرکے، تغیرات میں کمی کی تکنیکیں ہم آہنگی کی شرحوں کو حاصل کرنے کے قابل ہوتی ہیں جو ان طریقوں سے حاصل کرنا ناممکن ہے جو مقصد کو ایک لامحدود رقم کے طور پر مانتے ہیں، جیسا کہ کلاسیکی اسٹوچسٹک تخمینہ ترتیب میں ہوتا ہے۔ متغیرات میں کمی کے طریقوں کو وسیع پیمانے پر ٹریننگ مشین لرننگ ماڈلز جیسے لاجسٹک ریگریشن اور سپورٹ ویکٹر مشینوں کے لیے استعمال کیا جاتا ہے کیونکہ ان مسائل میں محدود رقم کی ساخت اور یکساں کنڈیشنگ ہوتی ہے جو انہیں تغیرات میں کمی کے لیے مثالی امیدوار بناتی ہے۔ ایک فنکشن کو محدود رقم کا ڈھانچہ سمجھا جاتا ہے اگر اسے خلاصہ یا اوسط میں تقسیم کیا جا سکتا ہے: جہاں ہر ایک کی فنکشن ویلیو اور مشتق سے آزادانہ طور پر پوچھ گچھ کی جا سکتی ہے۔ اگرچہ تغیرات میں کمی کے طریقوں کو کسی بھی مثبت اور کسی بھی ڈھانچے کے لیے لاگو کیا جا سکتا ہے، لیکن ان کی سازگار نظریاتی اور عملی خصوصیات اس وقت پیدا ہوتی ہیں جب ہر ایک کی حالت کی تعداد کے مقابلے میں بڑی ہوتی ہیں، اور جب ان میں ایک جیسی (لیکن ضروری نہیں کہ ایک جیسی) لپشٹز کی نرمی اور مضبوط کنویکسٹی کے مستقل ہوتے ہیں۔ محدود رقم کی ساخت کا موازنہ اسٹوکاسٹک تخمینہ ترتیب سے کیا جانا چاہیے جو اس فارم کے افعال سے متعلق ہے جو بے ترتیب متغیر پر منحصر فنکشن کی متوقع قیمت ہے۔ کسی بھی محدود رقم کے مسئلے کو اسٹاکسٹک اپروکسیمیشن الگورتھم کا استعمال کرتے ہوئے بہتر بنایا جا سکتا ہے۔ تیز رفتار کنورجنس تیز رفتار کے بغیر سٹوچسٹک تغیر میں کمی کے طریقے درستگی کے اندر ایک منیما تلاش کرنے کے قابل ہوتے ہیں، یعنی۔ ترتیب کے متعدد مراحل میں: مراحل کی تعداد صرف لوگرتھمک طور پر مطلوبہ درستگی کی سطح پر منحصر ہوتی ہے، اسٹوکاسٹک تخمینہ فریم ورک کے برعکس، جہاں مطلوبہ مراحل کی تعداد مطلوبہ درستگی کے تناسب سے بڑھتی ہے۔ صرف ایک سٹوچسٹک گریڈینٹ استعمال کرنے کے باوجود، گریڈینٹ نزول سے کم قیمت پر، سٹوچسٹک تغیرات میں کمی کے طریقے گریڈینٹ نزول کے طریقہ کار کی شرح کی طرح تقریبا اتنی ہی تیزی سے یکجا ہوتے ہیں۔ اسٹاکسٹک تغیرات میں کمی کے فریم ورک میں تیز رفتار طریقے اور بھی تیز ارتکاز کی شرح حاصل کرتے ہیں، جس میں درستگی تک پہنچنے کے لیے صرف اقدامات کی ضرورت ہوتی ہے، ممکنہ طور پر غیر تیز رفتار طریقوں سے زیادہ تیز۔ کم پیچیدگی کی حدود۔ محدود رقم کی کلاس کے لیے یہ ثابت کریں کہ یہ شرح ہموار مضبوط کنویکس مسائل کے لیے سب سے تیز ممکن ہے۔ متغیرات میں کمی کے نقطہ نظر 3 اہم زمروں میں آتے ہیں: ٹیبل ایوریج کے طریقے، فل گریڈینٹ سنیپ شاٹ کے طریقے اور دوہری طریقے۔ ہر زمرے میں کنویکس، غیر ہموار، اور غیر کنویکس مسائل سے نمٹنے کے لیے بنائے گئے طریقے شامل ہیں، جن میں سے ہر ایک ہائپر پیرامیٹر کی ترتیبات اور دیگر الگورتھمک تفصیلات میں مختلف ہے۔ ساگا طریقہ کار میں، پروٹوٹائپکل ٹیبل ایوریجنگ اپروچ، سائز کی ایک ٹیبل کو برقرار رکھا جاتا ہے جس میں ہر اصطلاح کے لیے آخری میلان کا مشاہدہ ہوتا ہے، جس کی ہم نشاندہی کرتے ہیں۔ ہر مرحلے پر، ایک انڈیکس کا نمونہ لیا جاتا ہے، اور ایک نیا میلان شمار کیا جاتا ہے۔ تکرار کے ساتھ اپ ڈیٹ کیا جاتا ہے: اور بعد میں ٹیبل انٹری کے ساتھ اپ ڈیٹ کیا جاتا ہے۔ ایس اے جی اے اپنی سادگی، آسانی سے موافقت پذیر نظریہ اور بہترین کارکردگی کی وجہ سے تغیرات میں کمی کے مقبول ترین طریقوں میں سے ایک ہے۔ یہ ایس اے جی طریقہ کار کا جانشین ہے، جس سے اس کی لچک اور کارکردگی میں بہتری آتی ہے۔ ایس وی آر جی اسٹاکسٹک ویریئنس ریڈیسڈ گریڈینٹ میتھڈ (ایس وی آر جی)، پروٹو ٹائپکل سنیپ شاٹ میتھڈ، اسی طرح کی اپ ڈیٹ کا استعمال کرتا ہے سوائے ٹیبل کی اوسط استعمال کرنے کے اس کے کہ یہ ایک مکمل گریڈینٹ کا استعمال کرتا ہے جس کا باقاعدہ وقفوں پر سنیپ شاٹ پوائنٹ پر دوبارہ جائزہ لیا جاتا ہے۔ اپ ڈیٹ بن جاتا ہے: اس نقطہ نظر کے لیے فی قدم دو سٹوچسٹک گریڈینٹ تشخیص کی ضرورت ہوتی ہے، ایک کا حساب لگانے کے لیے اور ایک کا حساب لگانے کے لیے جہاں-جیسا کہ ٹیبل اوسط نقطہ نظر کو صرف ایک کی ضرورت ہوتی ہے۔ زیادہ کمپیوٹیشنل لاگت کے باوجود، ایس وی آر جی مقبول ہے کیونکہ اس کا سادہ کنورجنس تھیوری نئی اصلاح کی ترتیبات کے لیے انتہائی موافقت پذیر ہے۔ اس میں ٹیبلولر اوسط طریقوں کے مقابلے میں اسٹوریج کی ضروریات بھی کم ہیں، جو اسے بہت سی ترتیبات میں لاگو کرتی ہیں جہاں ٹیبلولر طریقے استعمال نہیں کیے جا سکتے ہیں۔ ایس ڈی سی اے مقصد کی دوہری نمائندگی کا استحصال ایک اور تغیرات میں کمی کے نقطہ نظر کی طرف لے جاتا ہے جو خاص طور پر محدود مجموعوں کے لیے موزوں ہے جہاں ہر اصطلاح کا ایک ڈھانچہ ہوتا ہے جو کنویکس کنجوگیٹ یا اس کے پراکسیمل آپریٹر کی کمپیوٹنگ کو قابل عمل بناتا ہے۔ معیاری ایس ڈی سی اے طریقہ محدود رقم پر غور کرتا ہے جس میں عام محدود رقم کی ترتیب کے مقابلے میں اضافی ڈھانچہ ہوتا ہے: جہاں ہر ایک 1 جہتی ہوتا ہے اور ہر ایک ڈیٹا پوائنٹ سے وابستہ ہوتا ہے۔ ایس ڈی سی اے دوہرے مسئلے کو حل کرتا ہے: ایک سٹوچسٹک کوآرڈینیٹ چڑھائی کے طریقہ کار کے ذریعے، جہاں ہر مرحلے پر مقصد کو بے ترتیب طور پر منتخب کردہ کوآرڈینیٹ کے حوالے سے بہتر بنایا جاتا ہے، جس سے دیگر تمام کوآرڈینیٹس یکساں رہ جاتے ہیں۔ ایک لگ بھگ ابتدائی حل کو ان اقدار سے بازیافت کیا جا سکتا ہے: یہ طریقہ مرحلہ سائز کے پیرامیٹر کی وضاحت کرنے کی ضرورت سے گریز کرتے ہوئے، دوسرے سٹوچسٹک تغیرات کو کم کرنے والے طریقوں سے ہم آہنگی کی اسی طرح کی نظریاتی شرح حاصل کرتا ہے۔ یہ عملی طور پر تیز ہوتا ہے جب بڑا ہوتا ہے، لیکن دوسرے طریقوں کے مقابلے میں نمایاں طور پر سست ہوتا ہے جب چھوٹا ہوتا ہے۔ تیز رفتار نقطہ نظر تیز رفتار تغیرات میں کمی کے طریقے مندرجہ بالا معیاری طریقوں پر بنائے گئے ہیں۔ ابتدائی نقطہ نظر تقریبا یا بالکل کنورجنس کو تیز کرنے کے لیے پراکسیمل آپریٹرز کا استعمال کرتے ہیں۔ اتپریرک فریم ورک تقریبا ایک پراکسیمل آپریٹر کو حل کرنے کے لیے اوپر دیے گئے کسی بھی معیاری طریقے کو اندرونی اصلاح کار کے طور پر استعمال کرتا ہے: جس کے بعد یہ اگلے کا تعین کرنے کے لیے ایک ایکسٹراپولیشن مرحلہ استعمال کرتا ہے: اتپریرک طریقہ کی لچک اور سادگی اسے ایک مقبول بنیادی نقطہ نظر بناتی ہے۔ یہ تیز رفتار طریقوں کے درمیان ہم آہنگی کی زیادہ سے زیادہ شرح حاصل نہیں کرتا ہے، یہ ہائپر پیرامیٹرز میں لاگ فیکٹر تک ممکنہ طور پر سست ہوتا ہے۔ ایک تیز رفتار طریقہ حاصل کرنے کے لیے پوائنٹ-ایس اے جی اے پراکسیمل آپریشنز کو براہ راست شرائط پر بھی لاگو کیا جا سکتا ہے۔ پوائنٹ-ساگا طریقہ ساگا میں گریڈینٹ آپریشنز کی جگہ پراکسیمل آپریٹر کی تشخیص کرتا ہے، جس کے نتیجے میں ایک آسان، براہ راست ایکسلریشن طریقہ ہوتا ہے: ہر مرحلے کے بعد ٹیبل اپ ڈیٹ انجام دیا جاتا ہے۔ یہاں چھٹی اصطلاح کے لیے پراکسیمل آپریٹر کے طور پر بیان کیا گیا ہے: دوسرے معروف تیز رفتار طریقوں کے برعکس، پوائنٹ-ایس اے جی اے کو مراحل کے درمیان برقرار رکھنے کے لیے صرف ایک تکراری ترتیب کی ضرورت ہوتی ہے، اور اس میں صرف ایک ٹیون ایبل پیرامیٹر ہونے کا فائدہ ہوتا ہے۔ یہ اضافی لاگ عوامل کے بغیر مضبوطی سے کنویکس محدود-رقم کو کم کرنے کے لیے کنورجنس کی زیادہ سے زیادہ تیز رفتار شرح حاصل کرتا ہے۔ یہ بھی دیکھیں کہ اسٹوچسٹک گریڈینٹ ڈیسنٹ کوآرڈینیٹ ڈیسنٹ آن لائن مشین لرننگ پراکسیمل آپریٹر اسٹوچسٹک آپٹیمائزیشن اسٹوچسٹک اپروکسیمیشن حوالہ جات اسٹوچسٹک آپٹیمائزیشن گریڈینٹ طریقے مشین لرننگ الگورتھم کنویکس آپٹیمائزیشن