Sequential minimal optimization
سیکوینشیل منمل آپٹیمائزیشن (ایس ایم او) سپورٹ ویکٹر مشینوں (ایس وی ایم) کی تربیت کے دوران پیدا ہونے والے کواڈریٹک پروگرامنگ (کیو پی) کے مسئلے کو حل کرنے کے لیے ایک الگورتھم ہے۔ اسے جان پلیٹ نے 1998 میں مائیکروسافٹ ریسرچ میں ایجاد کیا تھا۔ ایس ایم او وسیع پیمانے پر سپورٹ ویکٹر مشینوں کی تربیت کے لیے استعمال ہوتا ہے اور اسے مقبول ایل آئی بی ایس وی ایم ٹول کے ذریعے لاگو کیا جاتا ہے۔ 1998 میں ایس ایم او الگورتھم کی اشاعت نے ایس وی ایم کمیونٹی میں بہت جوش و خروش پیدا کیا ہے، کیونکہ ایس وی ایم کی تربیت کے لیے پہلے سے دستیاب طریقے بہت زیادہ پیچیدہ تھے اور مہنگے تھرڈ پارٹی کیو پی سولورز کی ضرورت تھی۔ اصلاح کا مسئلہ ڈیٹا سیٹ (x1، y1)،.، (xn، yn) کے ساتھ بائنری درجہ بندی کے مسئلے پر غور کریں، جہاں xi ایک ان پٹ ویکٹر ہے اور اس سے مطابقت رکھنے والا بائنری لیبل ہے۔ سافٹ مارجن سپورٹ ویکٹر مشین کو کواڈریٹک پروگرامنگ کے مسئلے کو حل کرکے تربیت دی جاتی ہے، جس کا اظہار دوہری شکل میں اس طرح کیا جاتا ہے: اس کے تابع: جہاں C ایک SVM ہائپر پیرامیٹر ہے اور K (xi، xj) دانا فنکشن ہے، دونوں صارف کے ذریعہ فراہم کردہ ہیں ؛ اور متغیرات لگرینج ملٹی پلیئرز ہیں۔ الگورتھم ایس ایم او اوپر بیان کردہ اصلاح کے مسئلے کو حل کرنے کے لیے ایک تکراری الگورتھم ہے۔ ایس ایم او اس مسئلے کو چھوٹے سے چھوٹے ممکنہ ذیلی مسائل کے سلسلے میں تقسیم کرتا ہے، جنہیں پھر تجزیاتی طور پر حل کیا جاتا ہے۔ لیگرینج ملٹی پلیئرز پر مشتمل لکیری مساوات کی رکاوٹ کی وجہ سے، سب سے چھوٹے ممکنہ مسئلے میں ایسے دو ملٹی پلیئرز شامل ہوتے ہیں۔ پھر، کسی بھی دو ضرب کے لیے اور، رکاوٹوں کو کم کر دیا جاتا ہے: اور اس کم شدہ مسئلے کو تجزیاتی طور پر حل کیا جا سکتا ہے: کسی کو کم از کم ایک جہتی کواڈریٹک فنکشن تلاش کرنے کی ضرورت ہے۔ مساوات کی رکاوٹ میں باقی شرائط پر رقم کا منفی ہے، جو ہر تکرار میں طے ہوتا ہے۔ الگورتھم مندرجہ ذیل طریقے سے آگے بڑھتا ہے: ایک لگرینج ضرب تلاش کریں جو اصلاح کے مسئلے کے لیے کروش-کوہن-ٹکر (کے کے ٹی) شرائط کی خلاف ورزی کرتا ہے۔ دوسرا ضرب منتخب کریں اور جوڑے کو بہتر بنائیں۔ کنورجنس تک مراحل 1 اور 2 کو دہرائیں۔ جب تمام لگرینج ملٹی پلیئرز کے کے ٹی شرائط کو پورا کرتے ہیں (صارف کی طرف سے متعین رواداری کے اندر)، تو مسئلہ حل ہو جاتا ہے۔ اگرچہ اس الگورتھم کو کنورج کرنے کی ضمانت دی گئی ہے، لیکن ہیورسٹکس کا استعمال ضرب کے جوڑے کو منتخب کرنے کے لیے کیا جاتا ہے تاکہ کنورجنس کی شرح کو تیز کیا جا سکے۔ یہ بڑے ڈیٹا سیٹوں کے لیے اہم ہے کیونکہ اور کے لیے ممکنہ انتخاب موجود ہیں۔ متعلقہ کام ایس وی ایم سیکھنے کے بڑے مسائل کو چھوٹے اصلاحاتی کاموں کے سلسلے میں تقسیم کرنے کا پہلا طریقہ برنہارڈ بوسر، اسابیل گیوون، ولادیمیر ویپنک نے تجویز کیا تھا۔ اسے "چنکنگ الگورتھم" کے نام سے جانا جاتا ہے۔ الگورتھم ڈیٹا کے بے ترتیب ذیلی سیٹ سے شروع ہوتا ہے، اس مسئلے کو حل کرتا ہے، اور بار بار ایسی مثالیں شامل کرتا ہے جو بہتر حالات کی خلاف ورزی کرتی ہیں۔ اس الگورتھم کا ایک نقصان یہ ہے کہ ایس وی کی تعداد کے ساتھ کیو پی کے مسائل کو حل کرنا ضروری ہے۔ حقیقی دنیا کے غیر معمولی ڈیٹا سیٹوں پر، ایس ایم او چنکنگ الگورتھم سے 1000 گنا زیادہ تیز ہو سکتا ہے۔ 1997 میں، ای اوسونا، آر فرینڈ، اور ایف گیروسی نے ایک نظریہ ثابت کیا جو ایس وی ایم کے لیے کیو پی الگورتھم کا ایک مکمل نیا سیٹ تجویز کرتا ہے۔ اس نظریہ کی وجہ سے ایک بڑے کیو پی مسئلے کو چھوٹے کیو پی ذیلی مسائل کے سلسلے میں تقسیم کیا جا سکتا ہے۔ کیو پی ذیلی مسائل کا ایک سلسلہ جو ہمیشہ کروش-کوہن-ٹکر (کے کے ٹی) شرائط کی کم از کم ایک خلاف ورزی کرنے والے کو شامل کرتا ہے اس بات کی ضمانت دیتا ہے۔ چنکنگ الگورتھم تھیوریم کی شرائط کی پابندی کرتا ہے، اور اس لیے یکجا ہو جائے گا۔ ایس ایم او الگورتھم کو اوسونا الگورتھم کا ایک خاص معاملہ سمجھا جا سکتا ہے، جہاں اصلاح کا سائز دو ہے اور دونوں لگرینج ملٹی پلائرز کو ہر مرحلے پر نئے ملٹی پلائرز سے تبدیل کیا جاتا ہے جو اچھے ہیورسٹکس کے ذریعے منتخب کیے جاتے ہیں۔ ایس ایم او الگورتھم کا قریب سے تعلق اصلاح کے الگورتھم کے ایک خاندان سے ہے جسے بریگ مین میتھڈز یا رو ایکشن میتھڈز کہتے ہیں۔ یہ طریقے لکیری رکاوٹوں کے ساتھ کنویکس پروگرامنگ کے مسائل کو حل کرتے ہیں۔ وہ تکراری طریقے ہیں جہاں ہر قدم موجودہ ابتدائی نقطہ کو ہر رکاوٹ پر پیش کرتا ہے۔ کرنل پرسیپٹرون حوالہ جات آپٹیمائزیشن الگورتھم اور طریقے سپورٹ ویکٹر مشینیں بھی دیکھیں۔