مدل شرطی محدود

مدل شرطی محدود (CCM)  یک چارچوب یادگیری ماشین و استنتاج است که یادگیری مدلهای مشروط (احتمالی یا افتراقی) را با محدودیتهای اعلامی تقویت می کند. این محدودیت می تواند به عنوان روشی برای ادغام دانش قبلی بیانگر در مدل و تعصب تکالیف انجام شده توسط مدل آموخته شده برای ارضای این محدودیت ها مورد استفاده قرار گیرد. این چارچوب می تواند برای حمایت از تصمیمات در یک فضای خروجی رسا و در عین حال مدولار بودن و قابلیت اجرا بودن آموزش و استنباط را حفظ کند.

مدل هایی از این نوع اخیراً توجه زیادی را در جامعه پردازش زبان طبیعی (NLP) جلب کرده اند. فرمول بندی مشکلات به عنوان مشکلات بهینه سازی محدود نسبت به خروجی مدل های آموخته شده دارای چندین مزیت است. به شما این امکان را می دهد تا با ایجاد فرصتی برای ترکیب دانش خاص دامنه به عنوان محدودیت های جهانی با استفاده از زبان مرتبه اول ، روی مدل سازی مشکلات تمرکز کنید. با استفاده از این چارچوب اعلامی ، توسعه دهنده از مهندسی ویژگی سطح پایین در حالی که خواص خاص دامنه مشکل را گرفته و نتیجه گیری دقیق را تضمین می کند ، آزاد می کند. از منظر یادگیری ماشینی امکان جدا کردن مرحله تولید مدل (یادگیری) از مرحله استنتاج محدود را فراهم می کند ، بنابراین به ساده سازی مرحله یادگیری در حالی که کیفیت راه حل ها را بهبود می بخشد کمک می کند. به عنوان مثال ، در مورد تولید جملات فشرده ، به جای تکیه بر یک مدل زبان برای حفظ بیشترین استفاده از n گرم در جمله ، می توان از قیدهایی استفاده کرد تا اگر اصلاح کننده ای در جمله فشرده نگه داشته می شود ، موضوع نیز حفظ خواهد شد.

 انگیزه 
تصمیم گیری در بسیاری از حوزه ها (مانند پردازش زبان طبیعی و مشکلات بینایی رایانه) اغلب شامل اختصاص مقادیر به مجموعه ای از متغیرهای وابسته به هم است که در آن ساختار وابستگی بیانی می تواند چه امکاناتی را تحت تأثیر قرار دهد یا حتی آنها را تعیین کند. این تنظیمات نه تنها برای مشکلات یادگیری ساختاری مانند برچسب زدن نقش معنایی ، بلکه برای مواردی که نیاز به استفاده از چندین مولفه از پیش آموخته شده مانند خلاصه کردن ، متن و جواب سوالات قابل استفاده است. در همه این موارد ، طبیعی است که مسئله تصمیم گیری را به عنوان یک مسئله بهینه سازی محدود ، با یک تابع هدف که از مدل های آموخته شده ، محدود به محدودیت های خاص دامنه یا مسئله تشکیل شده است ، فرموله کنید.

مدل های مشروط محدود یک چارچوب یادگیری و استنتاج را تشکیل می دهند که یادگیری مدل های مشروط (احتمالی یا افتراقی) را با محدودیت های اعلامی (به عنوان مثال با استفاده از نمایش مرتبه اول نوشته شده) به عنوان راهی برای حمایت از تصمیمات در یک فضای خروجی رسا با افزایش حفظ می کند. مدولار بودن و قابلیت انعطاف پذیری آموزش و استنباط. این محدودیت ها می توانند محدودیت های سخت را بیان کنند ، برخی از واگذاری ها را کاملاً منع کرده و یا محدودیت های نرم را برای مجازات های غیر محتمل مجازات کنند. در بیشتر برنامه های این چارچوب در NLP ، به شرح زیر ،Dan Roth and Wen-tau Yih, "A Linear Programming Formulation for Global Inference in Natural Language Tasks."  CoNLL, (2004). از برنامه نویسی خطی صحیح (ILP) به عنوان چارچوب استنتاج استفاده شده است ، اگرچه الگوریتم های دیگری را می توان برای آن منظور استفاده کرد.

 دفاع رسمی 
با توجه به مجموعه ای از توابع ویژگی ∅i(x.y) و یک مجموعه محدودیت Ci(x.y) ، تعریف شده بر روی یک ساختار ورودی x∈X و یک ساختار خروجی y∈Y ، یک مدل شرطی محدودیت با دو بردار وزن ، w و £ مشخص می شود ، و به عنوان راه حل مشکل بهینه سازی زیر تعریف می شود :

هر محدودیت £ یک نقشه بولی است که نشان می دهد اگر انتساب مشترک £ یک محدودیت را نقض کند و £ مجازاتی است که برای نقض محدودیت اعمال شده است. محدودیت هایی که یک مجازات نامحدود برای آنها تعیین شده است به عنوان محدودیت های سخت شناخته می شوند و نشان دهنده انتصاب های غیرممکن برای مسئله بهینه سازی است.

 نمونه/الگو های آموزشی 

 یادگیری مدل های محلی و جهانی 
تابع هدف مورد استفاده توسط CCM ها می تواند به چندین روش تجزیه و یاد گرفته شود ، از آموزش مشترک کامل مدل همراه با محدودیت ها تا جدا کردن کامل یادگیری و مرحله استنتاج. در حالت دوم ، چندین مدل محلی به طور مستقل آموخته می شوند و وابستگی بین این مدل ها فقط در زمان تصمیم گیری از طریق یک فرایند تصمیم گیری جهانی در نظر گرفته می شود. مزایای هر روش در که دو الگوی آموزشی را مطالعه می کند بحث شده است: (1) مدل های محلی: L + I (یادگیری + استنتاج) و (2) مدل جهانی: IBT (آموزش مبتنی بر استنتاج) ، و هر دو را از لحاظ تئوری نشان می دهد و از نظر تجربی اینکه در حالی که IBT (آموزش مشترک) در حد نهایی است ، تحت برخی شرایط (اساساً "اجزای خوب") L + I می تواند تعمیم بهتری داشته باشد.Vasin Punyakanok and Dan Roth and Wen-Tau Yih and Dav Zimak, "Learning and Inference over Constrained Output."  IJCAI, (2005).

توانایی CCM در ترکیب مدل های محلی به ویژه در مواردی که یادگیری مشترک از نظر محاسباتی غیرقابل حل است یا داده های آموزش برای یادگیری مشترک در دسترس نیست ، بسیار مفید است. این انعطاف پذیری ، CCM را از سایر چارچوب های یادگیری متمایز می کند که همچنین اطلاعات آماری را با محدودیت های اعلامی مانند شبکه منطقی مارکوف ، که بر آموزش مشترک تأکید دارند ، ترکیب می کند.

 سی سی ام تحت نظارت کم 
سی سی ام می تواند با استفاده از دانش دامنه (بیان شده به عنوان محدودیت) برای ایجاد یادگیری ، به کاهش نظارت کمک کند. این موقعیت ها در و مطالعه شدند. این کارها آموزش یادگیری محدودیت های نیمه نظارت شده را نشان می دهد و نشان می دهد که با تلفیق دانش دامنه ، عملکرد مدل شناخته شده به طور قابل توجهی بهبود می یابد.Ming-Wei Chang and Lev Ratinov and Dan Roth, "Guiding Semi-Supervision with Constraint-Driven Learning."  ACL, (2007)..Ming-Wei Chang and Lev Ratinov and Dan Roth, "Constraints as Prior Knowledge."  ICML Workshop on Prior Knowledge for Text and Language Processing, (2008).

 یادگیری از ارائه های نهفته 
سی سی ام ها همچنین در چارچوب های یادگیری پنهان ، جایی که مشکل یادگیری از طریق یک لایه نمایشی پنهان تعریف شده است ، استفاده شده اند. از آنجا که مفهوم نمایش صحیح ذاتاً بد تعریف شده است ، هیچ داده ای با برچسب استاندارد طلایی در مورد عظم ارائه در دسترس یاد گیرنده نیست. شناسایی ارائه یادگیری صحیح (یا بهینه) به عنوان یک فرایند پیش بینی ساختار یافته مشاهده می شود و بنابراین به عنوان CCM مدل سازی می شود. این مشکل در چندین مقاله ، هم در تنظیمات تحت نظارت و هم بدون نظارت ، پوشش داده شده است. در همه موارد تحقیقات نشان داد که مدل سازی صریح وابستگی متقابل بین تصمیمات ارائه از طریق محدودیت ها منجر به بهبود عملکرد می شود.Ming-Wei Chang and Dan Goldwasser and Dan Roth and Vivek Srikumar, "Discriminative Learning over Constrained Latent Representations."  NAACL, (2010).Ming-Wei Chang Dan Goldwasser Dan Roth and Yuancheng Tu, "Unsupervised Constraint Driven Learning For Transliteration Discovery." NAACL, (2009).

 برنامه ریزی خطی عدد صحیح برای برنامه های کاربردی پردازش زبان طبیعی 
مزایای فرمول اعلامی CCM و در دسترس بودن حلال های خارج از چارچوب منجر شده به طیف گسترده ای از وظایف پردازش زبان طبیعی در چارچوب ، از جمله برچسب زدن نقش معنایی ، تجزیه نحوی ، قطعنامه هسته ، جمع بندی ، ترجمه نویسی ، تولید زبان طبیعی و استخراج اطلاعات مشترک.Vasin Punyakanok, Dan Roth, Wen-tau Yih and Dav Zimak, "Semantic Role Labeling via Integer Linear Programming Inference."  COLING, (2004). Kenji Sagae and Yusuke Miyao and Jun’ichi Tsujii, "HPSG Parsing with Shallow Dependency Constraints." ACL, (2007). Pascal Denis and Jason Baldridge, "Joint Determination of Anaphoricity and Coreference Resolution using Integer Programming."  NAACL-HLT, (2007). James Clarke and Mirella Lapata, "Global Inference for Sentence Compression: An Integer Linear Programming Approach."  Journal of Artificial Intelligence Research (JAIR), (2008).Katja Filippova and Michael Strube, "Dependency Tree Based Sentence Compression." INLG, (2008).Katja Filippova and Michael Strube, "Sentence Fusion via Dependency Graph Compression." EMNLP, (2008). Dan Goldwasser and Dan Roth, "Transliteration as Constrained Optimization."  EMNLP, (2008). Dan Roth and Wen-tau Yih, "A Linear Programming Formulation for Global Inference in Natural Language Tasks."  CoNLL, (2004).Regina Barzilay and Mirrela Lapata, "Aggregation via Set Partitioning for Natural Language Generation." NAACL, (2006).Yejin Choi and Eric Breck and Claire Cardie, "Joint Extraction of Entities and Relations for Opinion Recognition." EMNLP, (2006).

در بیشتر این آثار برای حل مسئله تصمیم گیری از یک حلگر برنامه نویسی خطی عدد صحیح (ILP) استفاده می شود. اگرچه از نظر تئوریک حل یک برنامه خطی عدد صحیح در اندازه مسئله تصمیم گیری نمایی است ، اما در عمل با استفاده از پیشرفته ترین حل کننده ها و تکنیک های تقریبی استنباط می توان مشکلات مقیاس بزرگ را به طور کارآمد حل کرد.

مزیت کلیدی استفاده از حلگر ILP برای حل مسئله بهینه سازی تعریف شده توسط یک مدل شرطی محدود ، فرمول اعلامی است که به عنوان ورودی برای حل کننده ILP ، متشکل از یک تابع هدف خطی و یک مجموعه محدودیت های خطی استفاده میشود.

 منابع 
 CCM Tutorial Predicting Structures in NLP: Constrained Conditional Models and Integer Linear Programming in NLP 

 پیوند به بیرون 
 University of Illinois Cognitive Computation Group 
 Workshop on Integer Linear Programming for Natural Language Processing, NAACL-2009

رده:پیش‌بینی ساختاری
رده:ویکی‌سازی رباتیک
رده:یادگیری ماشین