میدان تصادفی شرطی

میدان تصادفی شرطی (به انگلیسی: Conditional Random Field)، یک مدل آماری است که در یادگیری ماشین کاربرد دارد. کاربرد اصلی آن در یادگیری ساختاریافته (به انگلیسی: Structured Learning) است. [1]

تعریف

فرض کنیم دو دسته متغیر داریم ${\displaystyle {\boldsymbol {X}}}$ و ${\displaystyle {\boldsymbol {Y}}}$. در نظر بگیریم گرافی داریم ${\displaystyle G=(V,E)}$ که متغیرها روی آن تعریف شده اند، یعنی ${\displaystyle {\boldsymbol {Y}}=({\boldsymbol {Y}}_{v})_{v\in V}}$. زوج ${\displaystyle ({\boldsymbol {X}},{\boldsymbol {Y}})}$ یک میدان تصادفی است که دارای ویژگی مارکوف مقابل است: ${\displaystyle p({\boldsymbol {Y}}_{v}|{\boldsymbol {X}},{\boldsymbol {Y}}_{w},w\neq v)=p({\boldsymbol {Y}}_{v}|{\boldsymbol {X}},{\boldsymbol {Y}}_{w},w\sim v)}$ که ${\displaystyle {\mathit {w}}\sim v}$ به معنی آن است که ${\displaystyle w}$ و ${\displaystyle v}$ در همسایگی هم قرار دارند.

استنتاج

در حالت کلی استنتاج روی میدان تصادفی شرطی بسیار شبیه به میدان تصادفی مارکفی و از لحاظ محاسباتی دشوار است. اما به ازای بعضی شرایط خاص می‌توان آن‌ها را به صورت ساده تری حل کرد:

• اگر گراف بدون حلقه باشد در اینصورت الگوریتم‌های message passing جواب درست را بدست می دهند. در حالت خاص اگر گراف، زنجیره باشد، الگوریتم forward-backward و الگوریتم ویتربی جواب درست را بدست می دهند.
• در حالتی که گراف دارای پتانسیل‌های دو-دویی باشد، الگوریتم برش کمینه جواب بهینه را بدست می دهد.

در صورتی که جواب دقیق غیرممکن باشد، راه حل‌های تقریبی می‌توانند کمک کنند:

• Loopy belief propagation
• Alpha expansion
• Mean field inference یا یادگیری بیزی تغییراتی
• Linear programming relaxations

یادگیری مدل

پارامترهای مدل، مثلاً ${\displaystyle \theta }$ معمولاً با درست نمایی بیشینه برای ${\displaystyle p(Y_{i}|X_{i};\theta )}$ یاد گرفته می‌شوند. در صورتی که همه ی متغیرها دارای توزیعی نمایی باشند و همه ی آن‌ها مشاهده شوند، مسئله ی بهینه‌سازی (ریاضیات) مورد نظر محدب خواهد بود.

همچنین ببینید

• مدل گرافی
• میدان تصادفی مارکفی
• مدل مارکوف بیشینه آنتروپی

منابع

1. Lafferty, J., McCallum, A., Pereira, F. (2001). "Conditional random fields: Probabilistic models for segmenting and labeling sequence data" (PDF). Proc. 18th International Conf. on Machine Learning. Morgan Kaufmann. pp. 282–289. Archived from the original (PDF) on 7 June 2013. Retrieved 11 March 2013.

مطالعه ی بیشتر

• McCallum, A.: Efficiently inducing features of conditional random fields. In: Proc. 19th Conference on Uncertainty in Artificial Intelligence. (2003)

• Wallach, H.M.: Conditional random fields: An introduction. Technical report MS-CIS-04-21, University of Pennsylvania (2004)
• Sutton, C., McCallum, A.: An Introduction to Conditional Random Fields for Relational Learning. In "Introduction to Statistical Relational Learning". Edited by Lise Getoor and Ben Taskar. MIT Press. (2006) Online PDF
• Klinger, R., Tomanek, K.: Classical Probabilistic Models and Conditional Random Fields. Algorithm Engineering Report TR07-2-013, Department of Computer Science, Dortmund University of Technology, December 2007. ISSN 1864-4503. Online PDF