Markov random field
طبیعیات اور امکان کے شعبے میں، مارکوف بے ترتیب فیلڈ (ایم آر ایف)، مارکوف نیٹ ورک یا غیر ہدایت شدہ گرافیکل ماڈل بے ترتیب متغیرات کا ایک مجموعہ ہے جس میں مارکوف پراپرٹی ہوتی ہے جسے غیر ہدایت شدہ گراف کے ذریعے بیان کیا جاتا ہے۔ دوسرے لفظوں میں، ایک بے ترتیب فیلڈ کو مارکوف بے ترتیب فیلڈ کہا جاتا ہے اگر یہ مارکوف کی خصوصیات کو مطمئن کرتا ہے۔ یہ تصور شیرنگٹن-کرک پیٹرک ماڈل سے نکلا ہے۔ مارکوف نیٹ ورک یا ایم آر ایف انحصار کی نمائندگی میں بیسیئن نیٹ ورک سے ملتا جلتا ہے۔ فرق یہ ہے کہ بیسیئن نیٹ ورک ڈائریکٹڈ اور ایسائکلک ہیں، جبکہ مارکوف نیٹ ورک غیر ڈائریکٹڈ ہیں اور چکور ہو سکتے ہیں۔ اس طرح، ایک مارکوف نیٹ ورک کچھ انحصار کی نمائندگی کر سکتا ہے جو بیسیئن نیٹ ورک نہیں کر سکتا (جیسے چکور انحصار) ؛ دوسری طرف، یہ کچھ انحصار کی نمائندگی نہیں کر سکتا جو بیسیئن نیٹ ورک کر سکتا ہے (جیسے محرک انحصار)۔ مارکوف بے ترتیب فیلڈ کا بنیادی گراف محدود یا لامحدود ہو سکتا ہے۔ جب بے ترتیب متغیرات کی مشترکہ امکانی کثافت سختی سے مثبت ہوتی ہے، تو اسے گبز بے ترتیب فیلڈ بھی کہا جاتا ہے، کیونکہ، ہیمرسلی-کلفورڈ تھیوریم کے مطابق، اس کی نمائندگی گبز پیمائش کے ذریعے ایک مناسب (مقامی طور پر متعین) توانائی فنکشن کے لیے کی جا سکتی ہے۔ پروٹوٹائپکل مارکوف بے ترتیب فیلڈ آئزنگ ماڈل ہے ؛ درحقیقت، مارکوف بے ترتیب فیلڈ کو آئزنگ ماڈل کے لیے عمومی ترتیب کے طور پر متعارف کرایا گیا تھا۔ مصنوعی ذہانت کے شعبے میں، ایک مارکوف بے ترتیب فیلڈ کا استعمال امیج پروسیسنگ اور کمپیوٹر وژن میں مختلف نچلے سے درمیانی درجے کے کاموں کو ماڈل کرنے کے لیے کیا جاتا ہے۔ تعریف ایک غیر ہدایت شدہ گراف کو دیکھتے ہوئے، بے ترتیب متغیرات کا ایک مجموعہ جسے مارکوف بے ترتیب فیلڈ کی شکل میں اس حوالے سے ترتیب دیا جاتا ہے کہ آیا وہ مقامی مارکوف خصوصیات کو مطمئن کرتے ہیں: جوڑی کے لحاظ سے مارکوف پراپرٹی: کوئی بھی دو غیر ملحقہ متغیرات دیگر تمام متغیرات کو دیکھتے ہوئے مشروط طور پر آزاد ہیں: مقامی مارکوف پراپرٹی: ایک متغیر اپنے پڑوسیوں کو دیکھتے ہوئے دیگر تمام متغیرات سے مشروط طور پر آزاد ہے: پڑوسیوں کا مجموعہ کہاں ہے، اور اس کا بند پڑوس ہے۔ گلوبل مارکوف پراپرٹی: متغیرات کے کوئی بھی دو ذیلی سیٹ مشروط طور پر آزاد ہوتے ہیں کیونکہ ایک علیحدہ ذیلی سیٹ ہوتا ہے: جہاں نوڈ سے نوڈ تک کا ہر راستہ گزرتا ہے۔ گلوبل مارکوف پراپرٹی لوکل مارکوف پراپرٹی سے زیادہ مضبوط ہے، جو بدلے میں پیئر وائز پراپرٹی سے زیادہ مضبوط ہے۔ تاہم، مندرجہ بالا تین مارکوف خصوصیات مثبت تقسیم کے لیے مساوی ہیں (وہ جو متعلقہ متغیرات کو صرف غیر صفر امکانات تفویض کرتے ہیں)۔ تین مارکوف خصوصیات کے درمیان تعلق مندرجہ ذیل تشکیل میں خاص طور پر واضح ہے: جوڑی کے لحاظ سے: کسی بھی غیر مساوی یا ملحقہ کے لیے،۔ مقامی: کسی کے لیے اور اس پر مشتمل یا اس سے متصل نہیں۔ گلوبل: کسی بھی غیر متصل یا ملحقہ کے لیے،۔ چونکہ صوابدیدی امکان کی تقسیم کی مارکوف خاصیت کو قائم کرنا مشکل ہو سکتا ہے، مارکوف بے ترتیب فیلڈز کی عام طور پر استعمال ہونے والی کلاس وہ ہیں جنہیں گراف کے کلکس کے مطابق فیکٹرائز کیا جا سکتا ہے۔ بے ترتیب متغیرات کے ایک سیٹ کو دیکھتے ہوئے، کسی خاص فیلڈ کنفیگریشن کا امکان ہونے دیں-یعنی، یہ تلاش کرنے کا امکان ہے کہ بے ترتیب متغیرات مخصوص قدر پر قبضہ کرتے ہیں۔ کیونکہ یہ ایک سیٹ ہے، اس کے امکانات کو مشترکہ تقسیم کے حوالے سے سمجھا جانا چاہیے۔ اگر اس مشترکہ کثافت کو اس کے کلکس پر فیکٹرائز کیا جا سکتا ہے تو اس کے حوالے سے مارکوف بے ترتیب فیلڈ بناتا ہے۔ یہاں، کے گروہوں کا مجموعہ ہے۔ تعریف مساوی ہے اگر صرف زیادہ سے زیادہ کلکس استعمال کیے جائیں۔ افعال کو بعض اوقات فیکٹر پوٹینشل یا کلک پوٹینشل کہا جاتا ہے۔ نوٹ، تاہم، متضاد اصطلاحات استعمال میں ہیں: لفظ پوٹینشل اکثر کے لوگارتھم پر لاگو ہوتا ہے۔ اس کی وجہ یہ ہے کہ شماریاتی میکانکس میں، کسی ترتیب کی ممکنہ توانائی کے طور پر براہ راست تشریح ہوتی ہے۔ کچھ ایم آر ایف فیکٹرائز نہیں کرتے: ایک سادہ سی مثال کچھ لامحدود توانائیوں کے ساتھ 4 نوڈس کے چکر پر بنائی جا سکتی ہے، یعنی۔ صفر امکانات کی ترتیبات، یہاں تک کہ اگر ایک، زیادہ مناسب طریقے سے، لامحدود توانائیوں کو مکمل گراف پر عمل کرنے کی اجازت دیتا ہے۔ ایم آر ایف کا فیکٹرائز اگر درج ذیل شرائط میں سے کم از کم ایک شرط پوری ہو جائے: کثافت مثبت ہے (ہیمرسلی-کلفورڈ تھیوریم کے مطابق) گراف کورڈل ہے (بیسیئن نیٹ ورک کے مساوی ہونے کے لحاظ سے) جب اس طرح کی فیکٹرائزیشن موجود ہوتی ہے، تو نیٹ ورک کے لیے فیکٹر گراف بنانا ممکن ہوتا ہے۔ ایکسپونینشیل فیملی کسی بھی مثبت مارکوف بے ترتیب فیلڈ کو خصوصیت کے افعال کے ساتھ کینونکل شکل میں ایکسپونینشیل فیملی کے طور پر لکھا جا سکتا ہے تاکہ مکمل مشترکہ تقسیم کو اس طرح لکھا جا سکے جہاں نوٹیشن محض فیلڈ کنفیگریشن پر ڈاٹ پروڈکٹ ہے، اور Z پارٹیشن فنکشن ہے: یہاں، نیٹ ورک کے تمام بے ترتیب متغیرات کے لیے اقدار کی تمام ممکنہ تفویض کے سیٹ کی نشاندہی کرتا ہے۔ عام طور پر، خصوصیت کے افعال کی وضاحت اس طرح کی جاتی ہے کہ وہ گروہ کی ترتیب کے اشارے ہوتے ہیں، یعنی۔ اگر k-th کلک کی i-th ممکنہ ترتیب سے مطابقت رکھتا ہے اور 0 بصورت دیگر۔ یہ ماڈل اوپر دیئے گئے کلک فیکٹرائزیشن ماڈل کے مساوی ہے، اگر کلک کی بنیادی حیثیت ہے، اور کسی خصوصیت کا وزن متعلقہ کلک فیکٹر کے لوگارتھم سے مطابقت رکھتا ہے، یعنی۔ ، k-th گروہ کی i-th ممکنہ ترتیب کہاں ہے، یعنی۔ کلک کے ڈومین میں i-th ویلیو۔ امکان P کو اکثر گبز پیمائش کہا جاتا ہے۔ لاجسٹک ماڈل کے طور پر مارکوف فیلڈ کا یہ اظہار صرف اس صورت میں ممکن ہے جب تمام کلک عوامل غیر صفر ہوں، یعنی۔ اگر کے عناصر میں سے کسی کو بھی 0 کا امکان تفویض نہیں کیا گیا ہے۔ یہ میٹرکس الجبرا کی تکنیکوں کو لاگو کرنے کی اجازت دیتا ہے، جیسے۔ کہ ایک میٹرکس کا سراغ تعین کنندہ کا لاگ ہے، جس میں گراف کے واقعات میٹرکس سے پیدا ہونے والے گراف کی میٹرکس نمائندگی ہوتی ہے۔ پارٹیشن فنکشن Z کی اہمیت یہ ہے کہ شماریاتی میکانکس کے بہت سے تصورات، جیسے کہ اینٹروپی، براہ راست مارکوف نیٹ ورک کے معاملے میں عام ہوتے ہیں، اور اس طرح ایک بدیہی تفہیم حاصل کی جا سکتی ہے۔ اس کے علاوہ، پارٹیشن فنکشن مسئلہ کے حل پر متغیر طریقوں کو لاگو کرنے کی اجازت دیتا ہے: کوئی بھی ایک یا زیادہ بے ترتیب متغیرات پر محرک قوت لگا سکتا ہے، اور اس خلل کے جواب میں نیٹ ورک کے رد عمل کو تلاش کر سکتا ہے۔ اس طرح، مثال کے طور پر، گراف کے ہر ورٹیکس v کے لیے، پارٹیشن فنکشن میں ایک ڈرائیونگ ٹرم Jv شامل کیا جا سکتا ہے: Jv کے حوالے سے رسمی طور پر تفریق کرنے سے ورٹیکس v سے وابستہ بے ترتیب متغیر Xv کی متوقع قیمت ملتی ہے: ارتباط افعال کا حساب بھی اسی طرح کیا جاتا ہے۔ دو نکاتی ارتباط یہ ہے: بدقسمتی سے، اگرچہ لاجسٹک مارکوف نیٹ ورک کا امکان کنویکس ہے، کسی ماڈل کے امکان کے امکان یا میلان کا اندازہ کرنے کے لیے ماڈل میں تخمینہ کی ضرورت ہوتی ہے، جو عام طور پر کمپیوٹیشنل طور پر ناقابل عمل ہے (نیچے 'تخمینہ' دیکھیں)۔ مثال کے طور پر گوسیئن ایک ملٹی ویریٹ نارمل ڈسٹری بیوشن گراف کے حوالے سے مارکوف بے ترتیب فیلڈ تشکیل دیتی ہے اگر گمشدہ کنارے صحت سے متعلق میٹرکس (الٹا کوویرینس میٹرکس) پر صفر سے مطابقت رکھتے ہیں: اس طرح کہ اندازہ جیسا کہ بیسیئن نیٹ ورک میں ہوتا ہے، کوئی بھی مارکوف بے ترتیب فیلڈ میں نوڈس کے دوسرے سیٹ کو دی گئی اقدار کے ایک سیٹ کی مشروط تقسیم کا حساب مارکوف بے ترتیب فیلڈ میں تمام ممکنہ تفویض کا خلاصہ کرکے کر سکتا ہے۔ اسے عین مطابق تخمینہ کہا جاتا ہے۔ تاہم، عین مطابق اندازہ ایک #P-مکمل مسئلہ ہے، اور اس طرح عام صورت میں کمپیوٹیشنل طور پر ناقابل تلافی ہے۔ قریب قریب تکنیکیں جیسے مارکوف چین مونٹی کارلو اور پاگل عقیدے کی تشہیر اکثر عملی طور پر زیادہ قابل عمل ہوتی ہیں۔ ایم آر ایف کے کچھ مخصوص ذیلی طبقات، جیسے کہ درخت (چو-لیو درخت دیکھیں)، میں کثیر الجہتی وقت کے تخمینے کے الگورتھم ہوتے ہیں۔ اس طرح کے ذیلی طبقات کو دریافت کرنا ایک فعال تحقیقی موضوع ہے۔ ایم آر ایف کی ذیلی کلاسیں بھی ہیں جو موثر ایم اے پی، یا ممکنہ طور پر تفویض، تخمینہ کی اجازت دیتی ہیں۔ ان کی مثالوں میں ایسوسی ایٹیو نیٹ ورک شامل ہیں۔ ایک اور دلچسپ ذیلی کلاس سڑنے کے قابل ماڈلز میں سے ایک ہے (جب گراف کورڈل ہوتا ہے): ایم ایل ای کے لیے ایک بند شکل ہونے کی وجہ سے، سینکڑوں متغیرات کے لیے ایک مستقل ڈھانچہ دریافت کرنا ممکن ہے۔ مشروط بے ترتیب فیلڈز مارکوف بے ترتیب فیلڈ کا ایک قابل ذکر متغیر ایک مشروط بے ترتیب فیلڈ ہے، جس میں ہر بے ترتیب متغیر کو عالمی مشاہدات کے ایک سیٹ پر بھی مشروط کیا جا سکتا ہے۔ اس ماڈل میں، ہر فنکشن تمام اسائنمنٹس سے لے کر کلک k اور غیر منفی حقیقی نمبروں کے مشاہدات دونوں کی نقشہ سازی ہے۔ مارکوف نیٹ ورک کی یہ شکل امتیازی درجہ بندی پیدا کرنے کے لیے زیادہ موزوں ہو سکتی ہے، جو مشاہدات پر تقسیم کا نمونہ نہیں بناتے ہیں۔ سی آر ایف کی تجویز جان ڈی لافریٹی، اینڈریو میک کولم اور فرنینڈو سی این نے پیش کی تھی۔ 2001 میں پیریرا۔ مختلف ایپلی کیشنز مارکوف بے ترتیب فیلڈز کمپیوٹر گرافکس سے لے کر کمپیوٹر وژن، مشین لرننگ یا کمپیوٹیشنل بائیولوجی، اور معلومات کی بازیافت تک مختلف شعبوں میں درخواست تلاش کرتے ہیں۔ ایم آر ایف کا استعمال امیج پروسیسنگ میں بناوٹ پیدا کرنے کے لیے کیا جاتا ہے کیونکہ ان کا استعمال لچکدار اور غیر معمولی امیج ماڈل تیار کرنے کے لیے کیا جا سکتا ہے۔ امیج ماڈلنگ میں، کام کسی دی گئی تصویر کی مناسب شدت کی تقسیم کو تلاش کرنا ہے، جہاں مناسبیت کا انحصار کام کی قسم پر ہوتا ہے اور ایم آر ایف اتنے لچکدار ہوتے ہیں کہ انہیں امیج اور ٹیکسٹچر کی ترکیب، امیج کمپریشن اور بحالی، امیج سیگمنٹشن، 2 ڈی امیجز سے تھری ڈی امیج انفریشن، امیج رجسٹریشن، ٹیکسٹچر سنتھسیس، سپر ریزولوشن، سٹیریو میچنگ اور معلومات کی بازیافت کے لیے استعمال کیا جا سکتا ہے۔ ان کا استعمال کمپیوٹر وژن کے مختلف مسائل کو حل کرنے کے لیے کیا جا سکتا ہے جنہیں توانائی کو کم کرنے کے مسائل یا مسائل کے طور پر پیش کیا جا سکتا ہے جہاں خطے کے زمرے کی پیش گوئی کے لیے مارکوف بے ترتیب فیلڈ فریم ورک کے اندر امتیازی خصوصیات کے ایک سیٹ کا استعمال کرتے ہوئے مختلف علاقوں کو ممتاز کرنا پڑتا ہے۔ مارکوف بے ترتیب فیلڈز آئزنگ ماڈل پر ایک عمومی تھے اور اس کے بعد سے، مشترکہ اصلاح اور نیٹ ورک میں بڑے پیمانے پر استعمال ہوتے رہے ہیں۔ مزید دیکھیں رکاوٹ جامع گراف گرافیکل ماڈل انحصار نیٹ ورک (گرافیکل ماڈل) ہیمرسلی-کلفورڈ تھیوریم ہاپ فیلڈ نیٹ ورک انٹرایکٹنگ پارٹیکل سسٹم آئزنگ ماڈل لاگ لکیری تجزیہ مارکوف چین مارکوف منطق نیٹ ورک زیادہ سے زیادہ اینٹروپی طریقہ اسٹوچسٹک سیلولر آٹومیٹن حوالہ جات گرافیکل ماڈل