Stability (learning theory)
استحکام، جسے الگورتھمک استحکام بھی کہا جاتا ہے، کمپیوٹیشنل لرننگ تھیوری میں ایک تصور ہے کہ کس طرح مشین لرننگ الگورتھم آؤٹ پٹ کو اس کے ان پٹ میں چھوٹی پریشانیوں کے ساتھ تبدیل کیا جاتا ہے۔ ایک مستحکم لرننگ الگورتھم وہ ہے جس کے لیے ٹریننگ ڈیٹا میں قدرے ترمیم کرنے پر پیشن گوئی زیادہ تبدیل نہیں ہوتی ہے۔ مثال کے طور پر، ایک مشین لرننگ الگورتھم پر غور کریں جسے حروف تہجی کے ہاتھ سے لکھے ہوئے حروف کو پہچاننے کے لیے تربیت دی جا رہی ہے، ہاتھ سے لکھے ہوئے حروف کی 1000 مثالوں اور ان کے لیبلز ("A" سے "Z") کو تربیتی سیٹ کے طور پر استعمال کرتے ہوئے۔ اس تربیتی سیٹ میں ترمیم کرنے کا ایک طریقہ یہ ہے کہ ایک مثال چھوڑی جائے، تاکہ ہاتھ سے لکھے ہوئے خطوط اور ان کے لیبل کی صرف 999 مثالیں دستیاب ہوں۔ ایک مستحکم لرننگ الگورتھم 1000-عنصر اور 999-عنصر ٹریننگ سیٹ دونوں کے ساتھ ایک جیسی درجہ بندی تیار کرے گا۔ زبان سیکھنے سے لے کر طبیعیات اور انجینئرنگ میں الٹا مسائل تک، سیکھنے کے کئی قسم کے مسائل کے لیے استحکام کا مطالعہ کیا جا سکتا ہے، کیونکہ یہ سیکھی جانے والی معلومات کی قسم کے بجائے سیکھنے کے عمل کی خاصیت ہے۔ استحکام کے مطالعہ نے 2000 کی دہائی میں کمپیوٹیشنل لرننگ تھیوری میں اہمیت حاصل کی جب یہ ظاہر کیا گیا کہ اس کا تعلق عمومی کاری سے ہے۔ یہ دکھایا گیا کہ سیکھنے کے الگورتھم کی بڑی کلاسوں کے لیے، خاص طور پر تجرباتی رسک منیمائزیشن الگورتھم، کچھ قسم کے استحکام اچھی عمومی کاری کو یقینی بناتے ہیں۔ مشین لرننگ سسٹم کو ڈیزائن کرنے کا ایک مرکزی مقصد اس بات کی ضمانت دینا ہے کہ سیکھنے کا الگورتھم ان میں سے ایک محدود تعداد پر تربیت حاصل کرنے کے بعد نئی مثالوں کو عام کرے گا، یا درست طریقے سے انجام دے گا۔ 1990 کی دہائی میں، زیر نگرانی سیکھنے کے الگورتھم کے لیے عمومی حدود حاصل کرنے میں سنگ میل طے کیے گئے۔ عمومی کاری کو ثابت کرنے کے لیے تاریخی طور پر استعمال ہونے والی تکنیک یہ ظاہر کرنے کے لیے تھی کہ ایک الگورتھم مستقل تھا، تجرباتی مقداروں کی یکساں کنورجنس خصوصیات کو ان کے ذرائع کے مطابق استعمال کرتے ہوئے۔ اس تکنیک کا استعمال تجرباتی رسک منیمائزیشن (ای آر ایم) الگورتھم کی بڑی کلاس کے لیے عمومی حدود حاصل کرنے کے لیے کیا گیا تھا۔ ای آر ایم الگورتھم وہ ہوتا ہے جو کسی مفروضے کی جگہ سے اس طرح حل کا انتخاب کرتا ہے کہ ٹریننگ سیٹ پر تجرباتی غلطی کو کم سے کم کیا جا سکے۔ ایک عام نتیجہ، جسے ولادیمیر ویپنک نے ای آر ایم بائنری درجہ بندی کے الگورتھم کے لیے ثابت کیا ہے، یہ ہے کہ کسی بھی ٹارگٹ فنکشن اور ان پٹ ڈسٹری بیوشن کے لیے، وی سی طول و عرض کے ساتھ کوئی بھی مفروضہ جگہ، اور تربیتی مثالیں، الگورتھم مستقل ہے اور ایک تربیتی غلطی پیدا کرے گا جو زیادہ سے زیادہ (پلس لوگرتھمک عوامل) حقیقی غلطی سے ہے۔ نتیجہ کو بعد میں فنکشن کلاسوں کے ساتھ تقریبا-ای آر ایم الگورتھم تک بڑھا دیا گیا جس میں منفرد منیمائزر نہیں ہوتے ہیں۔ ویپنک کے کام نے، وی سی تھیوری کے نام سے جانا جانے والا استعمال کرتے ہوئے، سیکھنے کے الگورتھم کی عمومی کاری اور سیکھے جانے والے افعال کے مفروضے کی خصوصیات کے درمیان تعلق قائم کیا۔ تاہم، ان نتائج کا اطلاق الگورتھم پر نہیں کیا جا سکا جس میں غیر محدود وی سی طول و عرض کے مفروضے کی جگہیں ہوں۔ دوسرے الفاظ میں، ان نتائج کا اطلاق اس وقت نہیں کیا جا سکا جب سیکھی جانے والی معلومات میں ایسی پیچیدگی تھی جس کی پیمائش کرنا بہت زیادہ تھا۔ کچھ آسان ترین مشین لرننگ الگورتھم-مثال کے طور پر، رجعت کے لیے-غیر محدود وی سی طول و عرض کے ساتھ مفروضے کی جگہیں ہیں۔ ایک اور مثال زبان سیکھنے کے الگورتھم ہیں جو من مانی لمبائی کے جملے تیار کر سکتے ہیں۔ استحکام کا تجزیہ 2000 کی دہائی میں کمپیوٹیشنل لرننگ تھیوری کے لیے تیار کیا گیا تھا اور یہ عمومی حدود حاصل کرنے کا ایک متبادل طریقہ ہے۔ الگورتھم کا استحکام مفروضے کی جگہ کی براہ راست خاصیت کے بجائے سیکھنے کے عمل کی ایک خاصیت ہے، اور اس کا اندازہ الگورتھم میں کیا جا سکتا ہے جس میں مفروضے کی جگہیں غیر محدود یا غیر متعین وی سی طول و عرض کے ساتھ ہوتی ہیں جیسے کہ قریب ترین پڑوسی۔ ایک مستحکم لرننگ الگورتھم وہ ہے جس کے لیے سیکھے ہوئے فنکشن میں زیادہ تبدیلی نہیں آتی ہے جب ٹریننگ سیٹ میں قدرے ترمیم کی جاتی ہے، مثال کے طور پر ایک مثال چھوڑ کر۔ لیو ون آؤٹ ایرر کی پیمائش کراس ویلڈیشن لیو ون آؤٹ (CVloo) الگورتھم میں لاس فنکشن کے حوالے سے لرننگ الگورتھم کے استحکام کا اندازہ کرنے کے لیے استعمال کی جاتی ہے۔ اس طرح، استحکام کا تجزیہ مشین لرننگ پر حساسیت کے تجزیے کا اطلاق ہے۔ کلاسک نتائج کا خلاصہ ابتدائی 1900 کی دہائی-سیکھنے کے نظریہ میں استحکام کو سب سے پہلے سیکھنے کے نقشے کے تسلسل کے لحاظ سے بیان کیا گیا تھا، جس کا سراغ آندرے نیکولائیوچ تیکھونوف سے ملتا ہے۔ 1979-ڈیوروئے اور ویگنر نے مشاہدہ کیا کہ الگورتھم کا لییو ون آؤٹ رویے کا تعلق نمونے میں ہونے والی چھوٹی تبدیلیوں کے لیے اس کی حساسیت سے ہے۔ 1999-کیرنز اور رون نے محدود وی سی طول و عرض اور استحکام کے درمیان ایک تعلق دریافت کیا۔ 2002-ایک تاریخی مقالے میں، بوسکیوٹ اور ایلیسیف نے سیکھنے کے الگورتھم کے یکساں مفروضے کے استحکام کے تصور کی تجویز پیش کی اور یہ ظاہر کیا کہ اس سے کم عمومی غلطی کا اشارہ ملتا ہے۔ یکساں مفروضہ استحکام، تاہم، ایک مضبوط حالت ہے جو الگورتھم کی بڑی کلاسوں پر لاگو نہیں ہوتی ہے، بشمول ای آر ایم الگورتھم جس میں صرف دو افعال کی مفروضہ جگہ ہوتی ہے۔ 2002-کوٹن اور نیاگی نے استحکام کی کئی کمزور شکلوں کے لیے عمومی حدود فراہم کر کے بوسکیوٹ اور ایلیسیف کے نتائج کو بڑھایا جسے وہ تقریبا ہر جگہ استحکام کہتے ہیں۔ مزید برآں، انہوں نے ممکنہ طور پر تقریبا درست (پی اے سی) ترتیب میں ای آر ایم الگورتھم میں استحکام اور مستقل مزاجی کے درمیان تعلق قائم کرنے کے لیے ایک ابتدائی قدم اٹھایا۔ 2004-پوگیو اور دیگر۔ استحکام اور ای آر ایم کی مستقل مزاجی کے درمیان ایک عمومی تعلق ثابت ہوا۔ انہوں نے لیو-ون-آؤٹ-اسٹیبلٹی کی ایک شماریاتی شکل کی تجویز پیش کی جسے انہوں نے CVEEEloo استحکام کہا، اور یہ ظاہر کیا کہ یہ a) باؤنڈڈ لاس کلاسوں میں جنرلائزیشن کے لیے کافی ہے، اور b) ERM الگورتھم کی مستقل مزاجی (اور اس طرح جنرلائزیشن) کے لیے ضروری اور کافی ہے۔ مخصوص نقصان کے افعال جیسے مربع نقصان، مطلق قیمت اور بائنری درجہ بندی کا نقصان۔ 2010-شیلو شوارٹز اور دیگر۔ مفروضے کی جگہ اور نقصان کی کلاس کے درمیان پیچیدہ تعلقات کی وجہ سے ویپنک کے اصل نتائج کے ساتھ مسائل کو دیکھا گیا۔ وہ استحکام کے تصورات پر تبادلہ خیال کرتے ہیں جو مختلف نقصان کی کلاسوں اور مختلف قسم کے سیکھنے، نگرانی اور غیر نگرانی پر قبضہ کرتے ہیں۔ 2016-مورٹز ہارٹ اور دیگر۔ مفروضے پر کچھ مفروضے اور ماڈل کو اپ ڈیٹ کرنے کے لیے ہر مثال کو استعمال کرنے کی تعداد کے پیش نظر میلان کے نزول کا ثابت شدہ استحکام۔ ابتدائی تعریفیں ہم سیکھنے کے الگورتھم ٹریننگ سیٹوں سے متعلق کئی اصطلاحات کی وضاحت کرتے ہیں، تاکہ ہم پھر متعدد طریقوں سے استحکام کی وضاحت کر سکیں اور میدان سے نظریات پیش کر سکیں۔ ایک مشین لرننگ الگورتھم، جسے لرننگ میپ بھی کہا جاتا ہے، ایک ٹریننگ ڈیٹا سیٹ کا نقشہ بناتا ہے، جو کہ لیبل شدہ مثالوں کا ایک مجموعہ ہے، ایک فنکشن پر، جہاں سے اور تربیتی مثالوں کی ایک ہی جگہ پر ہے۔ افعال کا انتخاب افعال کی ایک مفروضہ جگہ سے کیا جاتا ہے جسے کہا جاتا ہے۔ ٹریننگ سیٹ جس سے ایک الگورتھم سیکھتا ہے اس کی تعریف اس طرح کی جاتی ہے اور اس کا سائز تیار کیا جاتا ہے یعنی ڈی۔ کسی نامعلوم تقسیم D سے۔ اس طرح، سیکھنے کے نقشے کی تعریف ایک نقشہ سازی کے طور پر کی گئی ہے، جس میں ایک تربیتی سیٹ کو ایک فنکشن پر نقشہ بنایا گیا ہے۔ یہاں، ہم صرف تعیناتی الگورتھم پر غور کرتے ہیں جہاں کے حوالے سے ہم آہنگی ہے، یعنی۔ یہ ٹریننگ سیٹ میں عناصر کی ترتیب پر منحصر نہیں ہے۔ مزید برآں، ہم فرض کرتے ہیں کہ تمام افعال قابل پیمائش ہیں اور تمام سیٹ قابل گنتی ہیں۔ اس کے بعد کسی مثال کے حوالے سے مفروضے کے نقصان کی تعریف اس طرح کی جاتی ہے۔ کی تجرباتی غلطی ہے۔ اصل غلطی یہ ہے کہ سائز m کا ایک ٹریننگ سیٹ S دیا گیا ہے، ہم تمام i = 1.، m کے لیے، ترمیم شدہ ٹریننگ سیٹ کو مندرجہ ذیل طریقے سے بنائیں گے: i-th عنصر کو ہٹانے سے استحکام کی تعریف ایک الگورتھم میں مفروضہ استحکام β ہوتا ہے نقصان فنکشن V کے حوالے سے اگر مندرجہ ذیل ہوتا ہے: پوائنٹ کے لحاظ سے مفروضہ استحکام ایک الگورتھم میں نقصان فنکشن V کے حوالے سے پوائنٹ کے لحاظ سے مفروضہ استحکام β ہوتا ہے اگر مندرجہ ذیل ہوتا ہے: غلطی استحکام ایک الگورتھم میں نقصان فنکشن V کے حوالے سے غلطی استحکام β ہوتا ہے اگر مندرجہ ذیل ہوتا ہے: یکساں استحکام ایک الگورتھم میں نقصان فنکشن V کے حوالے سے یکساں استحکام β ہوتا ہے اگر مندرجہ ذیل ہوتا ہے: ایک امکان: لیو-ون-آؤٹ کراس-ویلیڈیشن (CVloo) استحکام ایک الگورتھم میں لاس فنکشن V کے حوالے سے CVloo استحکام β ہوتا ہے اگر مندرجہ ذیل ہوتا ہے: (CVloo) استحکام کی تعریف پوائنٹ وائز-مفروضہ استحکام کے برابر ہے جو پہلے دیکھا گیا تھا۔ متوقع-چھوڑو-ایک-باہر غلطی () استحکام ایک الگورتھم میں استحکام ہوتا ہے اگر ہر n کے لیے a اور ایسا موجود ہو کہ:، کلاسک تھیوریمز کے لیے صفر کے ساتھ اور جانے کے لیے باسکیٹ اور ایلیسیف سے (02): محدود نقصان کے ساتھ سمیٹرک لرننگ الگورتھم کے لیے، اگر الگورتھم میں اوپر کی امکانی تعریف کے ساتھ یکساں استحکام ہے، تو الگورتھم عام ہوجاتا ہے۔ یکساں استحکام ایک مضبوط حالت ہے جو تمام الگورتھم کے ذریعہ پورا نہیں ہوتا ہے لیکن حیرت انگیز طور پر، ریگولرائزیشن الگورتھم کے بڑے اور اہم طبقے کے ذریعہ پورا ہوتا ہے۔ عمومی باؤنڈ مضمون میں دیا گیا ہے۔ مکھرجی اور دیگر کی طرف سے۔ (06): باؤنڈڈ لاس کے ساتھ سمیٹرک لرننگ الگورتھم کے لیے، اگر الگورتھم میں لیو-ون-آؤٹ کراس-ویلیڈیشن (CVloo) اسٹیبلٹی اور متوقع-لیو-ون-آؤٹ ایرر () اسٹیبلٹی دونوں ہیں جیسا کہ اوپر بیان کیا گیا ہے، تو الگورتھم عام ہوتا ہے۔ عام کرنے کے لیے صرف کوئی بھی شرط کافی نہیں ہے۔ تاہم، دونوں مل کر عمومی کاری کو یقینی بناتے ہیں (جبکہ اس کے برعکس درست نہیں ہے)۔ ای آر ایم الگورتھم کے لیے خاص طور پر (مربع نقصان کے لیے کہیں)، لییو-ون-آؤٹ کراس-ویلیڈیشن (سی وی لو) استحکام مستقل مزاجی اور عمومی کاری کے لیے ضروری اور کافی دونوں ہے۔ یہ لرننگ تھیوری کی بنیادوں کے لیے ایک اہم نتیجہ ہے، کیونکہ یہ ظاہر کرتا ہے کہ الگورتھم کی دو پہلے سے غیر متعلقہ خصوصیات، استحکام اور مستقل مزاجی، ای آر ایم (اور کچھ نقصان کے افعال) کے مساوی ہیں۔ عمومی باؤنڈ مضمون میں دیا گیا ہے۔ الگورتھم جو مستحکم ہیں یہ الگورتھم کی ایک فہرست ہے جو مستحکم دکھائی گئی ہے، اور وہ مضمون جہاں متعلقہ عمومی حدود فراہم کی گئی ہیں۔ {0-1} نقصان فنکشن کے ساتھ لکیری رجعت k-NN درجہ بندی۔ ایک باؤنڈڈ دانا کے ساتھ ویکٹر مشین (ایس وی ایم) کی درجہ بندی کو سپورٹ کریں اور جہاں ری پروڈکشن دانا ہلبرٹ اسپیس میں ریگولیرائزر ایک معیار ہے۔ ایک بڑی باقاعدگی مستقل اچھی استحکام کی طرف لے جاتی ہے۔ سافٹ مارجن ایس وی ایم کی درجہ بندی۔ باقاعدگی سے کم سے کم مربع رجعت۔ درجہ بندی کے لیے کم از کم رشتہ دار اینٹروپی الگورتھم۔ ریگریسرز کی تعداد میں اضافے کے ساتھ بیگنگ ریگولرائزرز کا ایک ورژن۔ ملٹی کلاس ایس وی ایم کی درجہ بندی۔ تیکھونوف ریگولرائزیشن کے ساتھ سیکھنے کے تمام الگورتھم یکساں استحکام کے معیار کو پورا کرتے ہیں اور اس طرح عمومی ہیں۔ حوالہ جات مزید پڑھنا S.Kutin اور P.Niyogi.Almost-everywhere الگورتھمک استحکام اور عمومی کاری کی غلطی۔ پروک میں۔ یو اے آئی 18، 2002 کے ایس رخلن، ایس مکھرجی، اور ٹی پوگیو۔ استحکام کے نتیجے میں سیکھنے کا نظریہ سامنے آتا ہے۔ تجزیہ اور ایپلی کیشنز، 3 (4): 397-419، 2005 V. N. ویپنک۔ شماریاتی سیکھنے کے نظریہ کی نوعیت۔ سپرنگر، 1995 ویپنک، وی۔، شماریاتی سیکھنے کا نظریہ۔ ولی، نیویارک، 1998 پوگجیو، ٹی۔، ریفکن، آر۔، مکھرجی، ایس۔ اور نیاگی، پی۔، "لرننگ تھیوری: پیشن گوئی کے لیے عمومی حالات"، نیچر، جلد۔ 428، 419-422، 2004 آندرے ایلیسیف، تھیوڈورس ایوجینیؤ، ماسمیلیانو پونٹل، اسٹیبلٹی آف رینڈمائزڈ لرننگ الگورتھمز، جرنل آف مشین لرننگ ریسرچ 6، 55-79، 2010 ایلیسیف، اے پونٹل، ایم۔، لیو-ون آؤٹ ایرر اینڈ اسٹیبلٹی آف لرننگ الگورتھمز ود ایپلی کیشنز، نیٹو سائنس سیریز سب سیریز III کمپیوٹر اینڈ سسٹمز سائنسز، 2003، VOL 190، صفحات 111-130 شیلیو شوارٹز، S.، شمیر، O.، سریبرو، N.، سریدھرن، K.