ماخذ:
لکیری رجعت ڈیٹا کے تجزیہ سے متعلق بہت سے شعبوں کے لیے بنیادی الگورتھم میں سے ایک ہے۔ اس کی وجہ واضح ہے۔ یہ ایک بہت ہی آسان اور قابل فہم الگورتھم ہے، جس نے کئی دسیوں، اگر سینکڑوں نہیں تو سالوں سے اس کے وسیع پیمانے پر استعمال میں حصہ ڈالا ہے۔ خیال یہ ہے کہ ہم دوسرے متغیرات کے سیٹ پر ایک متغیر کی لکیری انحصار فرض کرتے ہیں، اور پھر اس انحصار کو بحال کرنے کی کوشش کرتے ہیں۔
لیکن یہ مضمون عملی مسائل کو حل کرنے کے لیے لکیری رجعت کے استعمال کے بارے میں نہیں ہے۔ یہاں ہم اس کی بازیابی کے لیے تقسیم شدہ الگورتھم کے نفاذ کی دلچسپ خصوصیات پر غور کریں گے، جن کا سامنا ہمیں مشین لرننگ ماڈیول لکھتے وقت ہوا تھا۔ . تھوڑا سا بنیادی ریاضی، مشین لرننگ، اور تقسیم شدہ کمپیوٹنگ آپ کو یہ معلوم کرنے میں مدد کر سکتی ہے کہ لکیری رجعت کیسے انجام دی جائے یہاں تک کہ جب آپ کا ڈیٹا ہزاروں نوڈس میں تقسیم ہو۔
اس کے بارے میں کیا ہے؟
ہمیں لکیری انحصار کو بحال کرنے کے کام کا سامنا ہے۔ ان پٹ ڈیٹا کے طور پر، قیاس شدہ آزاد متغیر کے ویکٹرز کا ایک سیٹ دیا جاتا ہے، جن میں سے ہر ایک منحصر متغیر کی ایک خاص قدر سے منسلک ہوتا ہے۔ اس ڈیٹا کو دو میٹرکس کی شکل میں پیش کیا جا سکتا ہے:
اب، چونکہ انحصار فرض کیا جاتا ہے، اور لکیری بھی، اس لیے ہم اپنے مفروضے کو میٹرکس کی پیداوار کی شکل میں لکھیں گے (ریکارڈنگ کو آسان بنانے کے لیے، یہاں اور نیچے یہ فرض کیا جاتا ہے کہ مساوات کی آزاد اصطلاح کے پیچھے چھپی ہوئی ہے) ، اور میٹرکس کا آخری کالم اکائیوں پر مشتمل ہے):
لکیری مساوات کے نظام کی طرح لگتا ہے، ہے نا؟ ایسا لگتا ہے، لیکن زیادہ تر امکان ہے کہ مساوات کے اس طرح کے نظام کا کوئی حل نہیں ہوگا۔ اس کی وجہ شور ہے، جو تقریباً کسی بھی حقیقی ڈیٹا میں موجود ہوتا ہے۔ ایک اور وجہ لکیری انحصار کی کمی ہو سکتی ہے، جس کا مقابلہ اضافی متغیرات کو متعارف کروا کر کیا جا سکتا ہے جو غیر خطوطی طور پر اصل پر انحصار کرتے ہیں۔ درج ذیل مثال پر غور کریں:
ماخذ:
یہ لکیری رجعت کی ایک سادہ مثال ہے جو ایک متغیر (محور کے ساتھ) کے تعلق کو ظاہر کرتی ہے۔ ) دوسرے متغیر سے (محور کے ساتھ )۔ اس مثال کے مطابق لکیری مساوات کے نظام کو حل کرنے کے لیے، تمام پوائنٹس کا بالکل ایک ہی سیدھی لائن پر ہونا چاہیے۔ لیکن یہ سچ نہیں ہے۔ لیکن وہ شور کی وجہ سے بالکل ایک ہی سیدھی لائن پر جھوٹ نہیں بولتے ہیں (یا اس وجہ سے کہ لکیری تعلق کا مفروضہ غلط تھا)۔ اس طرح، حقیقی ڈیٹا سے لکیری تعلق کو بحال کرنے کے لیے، عام طور پر ایک اور مفروضہ متعارف کروانا ضروری ہوتا ہے: ان پٹ ڈیٹا میں شور ہوتا ہے اور یہ شور ہوتا ہے۔ . آپ شور کی تقسیم کی دیگر اقسام کے بارے میں قیاس آرائیاں کر سکتے ہیں، لیکن زیادہ تر معاملات میں یہ عام تقسیم ہے جسے سمجھا جاتا ہے، جس پر مزید بات کی جائے گی۔
زیادہ سے زیادہ امکان کا طریقہ
لہذا، ہم نے بے ترتیب عام طور پر تقسیم شدہ شور کی موجودگی کو فرض کیا. ایسی حالت میں کیا کیا جائے؟ اس معاملے کے لیے ریاضی میں موجود ہے اور وسیع پیمانے پر استعمال ہوتا ہے۔ . مختصر یہ کہ اس کا جوہر انتخاب میں مضمر ہے۔ اور اس کے بعد کی زیادہ سے زیادہ۔
ہم عام شور کے ساتھ ڈیٹا سے ایک لکیری تعلق کو بحال کرنے پر واپس آتے ہیں۔ نوٹ کریں کہ فرض شدہ لکیری رشتہ ریاضیاتی توقع ہے۔ موجودہ عام تقسیم۔ ایک ہی وقت میں، امکان ہے کہ قابل مشاہدہ کی موجودگی سے مشروط ایک یا دوسری قدر لیتا ہے۔ ، مندرجہ ذیل کے طور پر:
آئیے اب اس کی جگہ متبادل بنائیں и ہمیں جن متغیرات کی ضرورت ہے وہ ہیں:
جو کچھ باقی ہے وہ ویکٹر کو تلاش کرنا ہے۔ ، جس پر یہ امکان زیادہ سے زیادہ ہے۔ اس طرح کے فنکشن کو زیادہ سے زیادہ کرنے کے لیے، پہلے اس کا لوگارتھم لینا آسان ہے (فنکشن کا لوگارتھم اسی نقطہ پر زیادہ سے زیادہ تک پہنچ جائے گا جیسے فنکشن خود):
جو، بدلے میں، درج ذیل فنکشن کو کم سے کم کرنے پر آتا ہے:
ویسے اس کو طریقہ کہتے ہیں۔ . اکثر مذکورہ بالا تمام باتوں کو چھوڑ دیا جاتا ہے اور یہ طریقہ صرف استعمال کیا جاتا ہے۔
کیو آر سڑنا
مندرجہ بالا فنکشن کا کم از کم اس نقطہ کو تلاش کر کے پایا جا سکتا ہے جس پر اس فنکشن کا گریڈینٹ صفر ہے۔ اور میلان اس طرح لکھا جائے گا:
کم از کم مربع کے طریقہ کار میں استعمال ہونے والے minimization کے مسئلے کو حل کرنے کے لیے ایک میٹرکس طریقہ ہے۔ اس سلسلے میں، ہم مساوات کو میٹرکس کی شکل میں دوبارہ لکھتے ہیں:
تو ہم میٹرکس کو گلتے ہیں۔ میٹرک تک и اور تبدیلیوں کا ایک سلسلہ انجام دیں (کیو آر ڈیکمپوزیشن الگورتھم خود یہاں پر غور نہیں کیا جائے گا، صرف ہاتھ میں کام کے سلسلے میں اس کا استعمال):
میٹرکس آرتھوگونل ہے. یہ ہمیں کام سے چھٹکارا حاصل کرنے کی اجازت دیتا ہے :
اور اگر آپ بدل دیں گے۔ پر ، پھر یہ کام کرے گا . یہ سمجھتے ہوئے کہ ایک اوپری مثلث میٹرکس ہے، یہ اس طرح لگتا ہے:
اس کو متبادل طریقہ سے حل کیا جا سکتا ہے۔ عنصر کے طور پر واقع ہے ، پچھلا عنصر کے طور پر واقع ہے اور وغیرہ.
یہاں یہ بات قابل غور ہے کہ QR سڑن کے استعمال کی وجہ سے نتیجے میں پیدا ہونے والے الگورتھم کی پیچیدگی . مزید برآں، اس حقیقت کے باوجود کہ میٹرکس ضرب آپریشن اچھی طرح سے متوازی ہے، اس الگورتھم کا ایک موثر تقسیم شدہ ورژن لکھنا ممکن نہیں ہے۔
تدریجی نزول
جب کسی فنکشن کو کم سے کم کرنے کے بارے میں بات کرتے ہو، تو یہ ہمیشہ یاد رکھنے کے قابل ہے (اسٹاکسٹک) گریڈینٹ ڈیسنٹ کا طریقہ۔ یہ ایک سادہ اور موثر مائنسائزیشن طریقہ ہے جس کی بنیاد پر ایک نقطہ پر کسی فنکشن کے گریڈینٹ کا بار بار حساب لگانا اور پھر اسے گریڈینٹ کے مخالف سمت میں منتقل کرنا ہے۔ اس طرح کا ہر قدم حل کو کم سے کم کے قریب لاتا ہے۔ میلان اب بھی ایک جیسا لگتا ہے:
یہ طریقہ گریڈینٹ آپریٹر کی لکیری خصوصیات کی وجہ سے اچھی طرح سے متوازی اور تقسیم بھی ہے۔ نوٹ کریں کہ مندرجہ بالا فارمولے میں، جمع کے نشان کے تحت آزاد اصطلاحات ہیں۔ دوسرے الفاظ میں، ہم تمام اشاریہ جات کے لیے میلان کو آزادانہ طور پر شمار کر سکتے ہیں۔ پہلے سے , اس کے متوازی طور پر، کے ساتھ انڈیکس کے لیے گریڈینٹ کا حساب لگائیں۔ پر . پھر نتیجے میں گریڈینٹ شامل کریں۔ اضافے کا نتیجہ وہی ہوگا جیسا کہ ہم نے فوری طور پر پہلے سے لے کر . اس طرح، اگر اعداد و شمار کو اعداد و شمار کے کئی ٹکڑوں میں تقسیم کیا جاتا ہے، تو ہر ٹکڑے پر میلان کو آزادانہ طور پر شمار کیا جا سکتا ہے، اور پھر حتمی نتیجہ حاصل کرنے کے لیے ان حسابات کے نتائج کا خلاصہ کیا جا سکتا ہے:
نفاذ کے نقطہ نظر سے، یہ تمثیل کے مطابق ہے۔ . تدریجی نزول کے ہر قدم پر، ہر ڈیٹا نوڈ کو ایک ٹاسک بھیجا جاتا ہے تاکہ گریڈینٹ کا حساب لگایا جا سکے، پھر کیلکولیشن شدہ گریڈینٹ کو ایک ساتھ جمع کیا جاتا ہے، اور ان کی رقم کا نتیجہ نتیجہ کو بہتر بنانے کے لیے استعمال کیا جاتا ہے۔
نفاذ میں آسانی اور MapReduce تمثیل میں عمل کرنے کی صلاحیت کے باوجود، تدریجی نزول میں بھی اپنی خامیاں ہیں۔ خاص طور پر، کنورجنسی حاصل کرنے کے لیے درکار اقدامات کی تعداد دیگر زیادہ مخصوص طریقوں کے مقابلے میں نمایاں طور پر زیادہ ہے۔
LSQR
مسئلہ کو حل کرنے کا ایک اور طریقہ ہے، جو لکیری رجعت کو بحال کرنے اور لکیری مساوات کے نظام کو حل کرنے کے لیے موزوں ہے۔ اس کی اہم خصوصیت یہ ہے کہ یہ میٹرکس طریقوں کے فوائد اور ایک تکراری نقطہ نظر کو یکجا کرتا ہے۔ اس طریقہ کے نفاذ دونوں لائبریریوں میں پایا جا سکتا ہے ، اور میں . اس طریقہ کار کی تفصیل یہاں نہیں دی جائے گی (یہ مضمون میں پایا جا سکتا ہے )۔ اس کے بجائے، تقسیم شدہ ماحول میں LSQR کو عمل میں لانے کے لیے ایک نقطہ نظر کا مظاہرہ کیا جائے گا۔
LSQR طریقہ پر مبنی ہے۔ . یہ ایک تکراری طریقہ کار ہے، ہر تکرار مندرجہ ذیل مراحل پر مشتمل ہے:
لیکن اگر ہم فرض کریں کہ میٹرکس افقی طور پر تقسیم کیا جاتا ہے، پھر ہر تکرار کو دو MapReduce مراحل کے طور پر پیش کیا جا سکتا ہے۔ اس طرح، ہر تکرار کے دوران ڈیٹا کی منتقلی کو کم سے کم کرنا ممکن ہے (صرف ویکٹر جن کی لمبائی نامعلوم افراد کی تعداد کے برابر ہے):
یہ وہ نقطہ نظر ہے جو لکیری رجعت کو لاگو کرتے وقت استعمال کیا جاتا ہے۔ .
حاصل يہ ہوا
بہت سے لکیری ریگریشن ریکوری الگورتھم ہیں، لیکن ان سب کو تمام حالات میں لاگو نہیں کیا جا سکتا۔ اس لیے چھوٹے ڈیٹا سیٹس پر درست حل کے لیے QR سڑنا بہترین ہے۔ تدریجی نزول لاگو کرنا آسان ہے اور آپ کو فوری طور پر ایک تخمینی حل تلاش کرنے کی اجازت دیتا ہے۔ اور LSQR پچھلے دو الگورتھم کی بہترین خصوصیات کو یکجا کرتا ہے، چونکہ اسے تقسیم کیا جا سکتا ہے، یہ تدریجی نزول کے مقابلے میں تیزی سے اکٹھا ہوتا ہے، اور QR کے سڑنے کے برعکس، الگورتھم کو جلد روکنے کی اجازت دیتا ہے، تاکہ ایک تخمینی حل تلاش کیا جا سکے۔
ماخذ: www.habr.com