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

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

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

تعریف[ویرایش]

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

استنتاج[ویرایش]

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

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

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

یادگیری مدل[ویرایش]

پارامترهای مدل، مثلا \theta معمولا با درست نمایی بیشینه برای 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". Proc. 18th International Conf. on Machine Learning. Morgan Kaufmann. pp. 282–289. 

مطالعه ی بیشتر[ویرایش]

  • 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