Diffusion map
ڈفیوژن میپس ایک جہتی کمی یا خصوصیت نکالنے کا الگورتھم ہے جسے کوفمین اور لافون نے متعارف کرایا ہے جو یوکلڈین اسپیس (اکثر کم جہتی) میں سیٹ کردہ ڈیٹا کے سرایت کے ایک خاندان کا حساب لگاتا ہے جس کے نقاط کو ڈیٹا پر ڈفیوژن آپریٹر کے آئجین ویکٹرز اور آئجین ویلیوز سے شمار کیا جاسکتا ہے۔ سرایت شدہ جگہ میں پوائنٹس کے درمیان یوکلڈین فاصلہ ان پوائنٹس پر مرکوز امکانات کی تقسیم کے درمیان "پھیلاؤ کے فاصلے" کے برابر ہے۔ لکیری جہت میں کمی کے طریقوں جیسے پرنسپل جزو تجزیہ (پی سی اے) سے مختلف، بازی کے نقشے غیر لکیری جہت میں کمی کے طریقوں کے خاندان کا حصہ ہیں جو اس بنیادی کئی گنا کو دریافت کرنے پر توجہ مرکوز کرتے ہیں جس سے ڈیٹا کا نمونہ لیا گیا ہے۔ مختلف پیمانوں پر مقامی مماثلتوں کو مربوط کرکے، پھیلاؤ کے نقشے ڈیٹا سیٹ کی عالمی وضاحت دیتے ہیں۔ دوسرے طریقوں کے مقابلے میں، ڈفیوژن میپ الگورتھم شور میں خلل ڈالنے کے لیے مضبوط اور کمپیوٹیشنل طور پر سستا ہے۔ پھیلاؤ کے نقشوں کی تعریف مندرجہ ذیل اور پھیلاؤ کے نقشوں کو چار مراحل میں بیان کیا جا سکتا ہے۔ کنیکٹیویٹی ڈفیوژن نقشے گرمی کے پھیلاؤ اور بے ترتیب واک مارکوف چین کے درمیان تعلقات کا استحصال کرتے ہیں۔ بنیادی مشاہدہ یہ ہے کہ اگر ہم ڈیٹا پر بے ترتیب چہل قدمی کرتے ہیں، تو قریبی ڈیٹا پوائنٹ پر چلنا دوسرے دور جانے سے زیادہ امکان ہے۔ ایک پیمائش کی جگہ ہونے دیں، جہاں ڈیٹا سیٹ ہے اور پوائنٹس کی تقسیم کی نمائندگی کرتا ہے۔ اس کی بنیاد پر، دو ڈیٹا پوائنٹس کے درمیان رابطے، اور، کو بے ترتیب چہل قدمی کے ایک مرحلے میں چلنے کے امکان کے طور پر بیان کیا جا سکتا ہے۔ عام طور پر، اس امکان کی وضاحت دو نکات کے دانا فنکشن کے لحاظ سے کی جاتی ہے: مثال کے طور پر، مقبول گوسیائی دانا: زیادہ عام طور پر، دانا فنکشن میں درج ذیل خصوصیات ہوتی ہیں (ہم آہنگ ہے) (مثبتیت کا تحفظ ہے)۔ دانا ڈیٹا سیٹ کی مقامی جیومیٹری کی سابقہ تعریف تشکیل دیتا ہے۔ چونکہ دیا ہوا دانا ڈیٹا سیٹ کی ایک مخصوص خصوصیت پر قبضہ کرے گا، اس لیے اس کے انتخاب کی رہنمائی اس ایپلی کیشن کے ذریعے کی جانی چاہیے جو کسی کے ذہن میں ہے۔ یہ پرنسپل جزو تجزیہ جیسے طریقوں کے ساتھ ایک بڑا فرق ہے، جہاں تمام ڈیٹا پوائنٹس کے درمیان ارتباط کو ایک ہی وقت میں مدنظر رکھا جاتا ہے۔ دی گئی ہے، اس کے بعد ہم ایک ریورسیبل ڈسکرٹ ٹائم مارکوف چین بنا سکتے ہیں (ایک عمل جسے نارملائزڈ گراف لیپلاسیئن کنسٹرکشن کے نام سے جانا جاتا ہے): اور اس کی وضاحت کرتے ہیں: اگرچہ نیا نارملائزڈ دانا سمیٹرک پراپرٹی کے وارث نہیں ہوتا ہے، لیکن یہ مثبتیت کو محفوظ رکھنے والی پراپرٹی کے وارث ہوتا ہے اور تحفظ کی پراپرٹی حاصل کرتا ہے: پھیلاؤ کا عمل اس سے ہم مارکوف چین () کا ٹرانزیشن میٹرکس بنا سکتے ہیں۔ دوسرے لفظوں میں، ایک قدم سے منتقلی کے امکان کی نمائندگی کرتا ہے، اور ٹی مرحلہ منتقلی میٹرکس دیتا ہے۔ ہم پھیلاؤ میٹرکس کی وضاحت کرتے ہیں (یہ گراف لیپلاسیئن میٹرکس کا ایک ورژن بھی ہے) پھر ہم نئے دانا یا اس کے مساوی طور پر وضاحت کرتے ہیں، جہاں D ایک اخترن میٹرکس ہے اور ہم اس نئے دانا پر گراف لیپلاسیئن نارملائزیشن کا اطلاق کرتے ہیں: جہاں ایک اخترن میٹرکس ہے اور پھیلاؤ فریم ورک کا ایک اہم خیال یہ ہے کہ زنجیر کو وقت کے ساتھ آگے چلانا (کی بڑی اور بڑی طاقتوں کو لینا) بڑے اور بڑے پیمانے پر (پھیلاؤ کے عمل) کی ہندسی ساخت کو ظاہر کرتا ہے۔ خاص طور پر، ڈیٹا سیٹ میں کلسٹر کے تصور کو ایک ایسے خطے کے طور پر شمار کیا جاتا ہے جس میں اس خطے سے فرار ہونے کا امکان کم ہوتا ہے (ایک مخصوص وقت t کے اندر)۔ لہذا، t نہ صرف وقت کے پیرامیٹر کے طور پر کام کرتا ہے، بلکہ اس میں پیمانے کے پیرامیٹر کا دوہرا کردار بھی ہے۔ میٹرکس کی ایجینڈی کمپوزیشن سے پتہ چلتا ہے کہ بالترتیب بائیو آرتھوگنل دائیں اور بائیں ایجین ویکٹر اور اور کے ایجین ویلیوز کی ترتیب کہاں ہے۔ آئجین ویلیوز کے سپیکٹرم کے ختم ہونے کی وجہ سے، اس رقم میں دی گئی متعلقہ درستگی کو حاصل کرنے کے لیے صرف چند اصطلاحات ضروری ہیں۔ پیرامیٹر α اور ڈفیوژن آپریٹر شامل نارملائزیشن مرحلے کو متعارف کرانے کی وجہ پھیلاؤ کی لامحدود منتقلی پر ڈیٹا پوائنٹ کثافت کے اثر کو ٹیون کرنا ہے۔ کچھ ایپلی کیشنز میں، ڈیٹا کے نمونے لینے کا تعلق عام طور پر کئی گنا کی جیومیٹری سے نہیں ہوتا ہے جسے ہم بیان کرنے میں دلچسپی رکھتے ہیں۔ اس صورت میں، ہم سیٹ کر سکتے ہیں اور ڈفیوژن آپریٹر لیپلیس-بیلٹرامی آپریٹر کا تخمینہ لگاتا ہے۔ اس کے بعد ہم پوائنٹس کی تقسیم سے قطع نظر ڈیٹا سیٹ کی ریمینیئن جیومیٹری کو بازیافت کرتے ہیں۔ سٹاکسٹک تفریقی مساوات کے نظام کے نقطہ تقسیم کے طویل مدتی رویے کو بیان کرنے کے لیے، ہم استعمال کر سکتے ہیں اور اس کے نتیجے میں مارکوف سلسلہ فوکر-پلانک پھیلاؤ کا تخمینہ لگاتا ہے۔ اس کے ساتھ، یہ کلاسیکی گراف لیپلاسیئن نارملائزیشن تک کم ہو جاتا ہے۔ پھیلاؤ کا فاصلہ دو نکات کے درمیان وقت پر پھیلاؤ کے فاصلے کو مشاہدے کی جگہ میں دو نکات کی مماثلت اور ان کے درمیان رابطے کے طور پر ماپا جا سکتا ہے۔ یہ اس طرح دیا جاتا ہے کہ مارکوف سلسلہ کی ساکن تقسیم کہاں ہے، جو کے پہلے بائیں آئجین ویکٹر کے ذریعہ دی گئی ہے۔ واضح طور پر: بدیہی طور پر، چھوٹا ہے اگر منسلک کرنے والے مختصر راستوں کی ایک بڑی تعداد ہے اور. پھیلاؤ کے فاصلے سے وابستہ کئی دلچسپ خصوصیات ہیں، جو ہماری پچھلی بحث پر مبنی ہیں جو پیمانے کے پیرامیٹر کے طور پر بھی کام کرتی ہیں: پوائنٹس ایک دیئے گئے پیمانے پر قریب ہوتے ہیں (جیسا کہ بیان کیا گیا ہے) اگر وہ گراف میں انتہائی جڑے ہوئے ہیں، لہذا اس تصور پر زور دیتے ہیں۔ ایک کلسٹر۔ یہ فاصلہ شور کے لیے مضبوط ہے، کیونکہ دو پوائنٹس کے درمیان فاصلہ پوائنٹس کے درمیان لمبائی کے تمام ممکنہ راستوں پر منحصر ہوتا ہے۔ مشین لرننگ کے نقطہ نظر سے، فاصلہ اس سے منسلک تمام شواہد کو مدنظر رکھتا ہے، جس سے ہمیں یہ نتیجہ اخذ کرنے میں مدد ملتی ہے کہ یہ فاصلہ اکثریت کی اہمیت پر مبنی تخمینہ الگورتھم کے ڈیزائن کے لیے موزوں ہے۔ پھیلاؤ کا عمل اور کم جہتی سرایت پھیلاؤ کے فاصلے کا حساب آئجین ویکٹروں کا استعمال کرتے ہوئے کیا جا سکتا ہے تو آئجین ویکٹروں کو ڈیٹا کے لیے نقاط کے ایک نئے سیٹ کے طور پر استعمال کیا جا سکتا ہے۔ پھیلاؤ کے نقشے کی تعریف اس طرح کی گئی ہے: سپیکٹرم کے گرنے کی وجہ سے، یہ صرف پہلے k آئجین ویکٹرز اور آئجین ویلیوز کا استعمال کرنے کے لیے کافی ہے۔ اس طرح ہم اصل ڈیٹا سے کے-جہتی جگہ پر پھیلاؤ کا نقشہ حاصل کرتے ہیں جو اصل جگہ میں سرایت کرتا ہے۔ اس میں یہ ثابت ہوتا ہے کہ اس طرح پھیلاؤ کے نقاط میں یوکلڈین فاصلہ پھیلاؤ کے فاصلے کا تخمینہ لگاتا ہے۔ الگورتھم بازی کے نقشے کا بنیادی الگورتھم فریم ورک اس طرح ہے: مرحلہ 1۔ مماثلت میٹرکس ایل کو دیکھتے ہوئے۔ مرحلہ 2۔ میٹرکس کو پیرامیٹر کے مطابق نارمل کریں:۔ مرحلہ 3. نارملائزڈ میٹرکس بنائیں۔ مرحلہ 4. کے سب سے بڑے آئجن ویلیوز اور متعلقہ آئجن ویکٹرز کا حساب لگائیں۔ مرحلہ 5۔ سرایت حاصل کرنے کے لیے پھیلاؤ کا نقشہ استعمال کریں۔ کاغذ میں درخواست نیڈلر اور دیگر۔ اس نے دکھایا کہ کس طرح ایک دانا ڈیزائن کیا جاتا ہے جو فوکر-پلانک مساوات سے پیدا ہونے والے پھیلاؤ کو دوبارہ پیش کرتا ہے۔ انہوں نے یہ بھی وضاحت کی کہ، جب اعداد و شمار کا تخمینہ کئی گنا ہوتا ہے، تو کوئی بھی لیپلیس-بیلٹرامی آپریٹر کے تخمینے کا حساب لگا کر اس کئی گنا کی جیومیٹری کو بازیافت کر سکتا ہے۔ یہ حساب پوائنٹس کی تقسیم کے لیے مکمل طور پر غیر حساس ہے اور اس لیے اعداد و شمار اور اعداد و شمار کی جیومیٹری کی علیحدگی فراہم کرتا ہے۔ چونکہ پھیلاؤ کے نقشے ڈیٹا سیٹ کی عالمی وضاحت دیتے ہیں، اس لیے وہ نمونے کے نکات کے جوڑوں کے درمیان فاصلے کی پیمائش کئی گنا کر سکتے ہیں جس میں ڈیٹا سرایت کیا گیا ہے۔ بازی کے نقشوں پر مبنی ایپلی کیشنز میں چہرے کی شناخت، سپیکٹرم کلسٹرنگ، تصاویر کی کم جہتی نمائندگی، امیج سیگمنٹشن، تھری ڈی ماڈل سیگمنٹشن، اسپیکر کی تصدیق اور شناخت، کئی گنا نمونے لینا، بے ضابطگی کا پتہ لگانا، امیج پینٹنگ، برین ریسٹنگ اسٹیٹ نیٹ ورک تنظیم کو ظاہر کرنا وغیرہ شامل ہیں۔ مزید برآں، پھیلاؤ کے نقشوں کے فریم ورک کو پیداواری طور پر پیچیدہ نیٹ ورکس تک بڑھایا گیا ہے، جس سے نیٹ ورکس کی ایک فعال تنظیم کا انکشاف ہوتا ہے جو خالص طور پر ٹپوولوجیکل یا ساختی سے مختلف ہے۔ غیر لکیری جہت میں کمی سپیکٹرم کلسٹرنگ حوالہ جات مشین لرننگ الگورتھم بھی دیکھیں۔