موجودیت‌های نام‌دار در زبان به مجموعه‌ای از اسامی مانند نام افراد، سازمان‌ها، مکان‌ها، و... می‌باشد. شناسایی موجودیت‌های نام‌دار در متن مسئله پیدا کردن این موجودیت‌ها از متن خام و همچنین شناسایی نوع موجودیت است.

برای مثال:
آدولف بورن، طراح، کاریکاتوریست و نقاش در شهر بودجویس از جمهوری چک به دنیا آمد.

آدولف B-PERSON
بورن I-PERSON
،
کاریکاتوریست
و
نقاش
در
شهر
بودجویس B-LOCATION
از
جمهوری B-LOCATION
چک I-LOCATION
به
دنیا
آمد
.

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

• این پروژه توسط یک بنگاه تجاری تعریف شده است و اگر به خوبی انجام شود، مورد حمایت قرار می‌گیرد.

۱. مقدمه

موجودیتهای نامدار در متن به عباراتی گفته می شود که حاوی اسامی اشخاص، سازمانها و یا مکانها باشند[1].در سامانه های تشخیص موجودیتهای اسمی عمومی بیشتر به سمت پیدا نمودن اسامی اشخاص، مکانها و سازمانهایی که در یک متن معمولی خبری ذکر شده است، تمرکز می شود.اولین مرحله در اغلب کاربردهای استخراج اطلاعات از متن ¹، تشخیص و دسته بندی موجودیتهای نامدار در یک متن است. به این عملیات تشخیص موجودیتهای نامدار ² اطلاق میشود[2].
در واقع مساله تشخیص موجودیت های نامدار در متن عموما به دو زیر مساله تشخیص و دسته بندی موجودیت ها تقسیم می شود :
1.اسامی خاصی که تشخیص داده می شوند.
2.قالبی که برای دسته بندی آنها به کار میرود که وابسته به نوع کاربرد آن خواهد بود.

نیاز به شناسایی موجودیتهای نامدار، در دنیای امروز که عصر ارتباطات و اطلاعات است رو به رشد میباشد. شناسایی موجودیتهای نامدار برای جستجوهای معنادار، ترجمه ی خودکار، استخراج خودکار مفاهیم متن، کشف ارجاعات درمتن و بسیاری دیگر از زمینه های مربوط به پردازش زبان های طبیعی³ کاربرد دارد[3].کاربردهای دیگری برای تشخیص موجودیت های نامدار تعریف گردیده است:

• طبقه بندی متون ⁴ : یک سیستم طبقه بندی کننده می تواند به جای اینکه ویژگی های خود را از کل متن استخراج کند ابتدا توسط NER اسامی را از متن استخراج کرده و سپس طبقه بندی را بر اساس این اسامی انجام دهد.استفاده از NER دقت طبقه بندی را تا حد قابل توجیهی افزایش می دهد.

• سیستم پرسش و پاسخ ⁵ : پاسخ بسیاری از سوالات یک متن مانند کی؟ کجا؟چه زمانی؟ چه مقدار ؟ و ... در اسامی حاضر در متن قرار دارد که می توان آنها را توسط یک سیستم NER از متن استخراج کرد.

• خلاصه سازی متون⁶ :داده های به دست آمده از یک سیستم NER شامل اطلاعات کلی از یک متن می باشد که در خلاصه سازی متون بسیار مفید است.

• بهینه کردن جستجو: زمانی که ما یک کلمه را جستجو می کنیم با توجه به فرم و نقش آن نتایج متفاوتی به دست می آید .به طور مثال اگر "استاد یوسفی " را جستجو کنیم منظورمان اسم شخص است و نتایجی مانند "خیابان استاد یوسفی" که اسم مکان است غیرمفید هستند.[11]

۲. کارهای مرتبط

در سال های اخیر سیستم های تشخیص واستخراج خودکار واحدهای اسمی به یکی از محدوده های پر طرفدار تحقیقاتی تبدیل شده است. این سیستم ها را می توان به سه دسته تقسیم بندی کرد:
1-روش های مبتنی بر قوانین که به صورت دستی مشخص شده اند ⁷
2- سیستم ها ی مبتنی بر یادگیری ماشینی⁸
3- سیستم های که ترکیبی از دو روش قبل هستند.[10]

سیستمهای توسعه یافته بر پایه یادگیری برای NERC به سه دسته تقسیم میشوند :
1.یادگیری با نظارت⁹ : یادگیری با نظارت، نیاز به حجم زیادی از متون حاشیه نویسی شده است و از تکنیک هایی نظیر درخت تصمیم گیری و مدل استفاده می کند. این روش مناسب برای مدل مخفی مارکوف¹⁰ و سیستمهای وابسته به دامنه است.
2.یادگیری نیمه نظارت¹¹ : در یادگیری نیمه نظارت از مجموعهای از کلمات نمونه برای یادگیری استفاده میشود (مثل مجموعهای از نام کتابها). این روش ها ابتدا سعی در یافتن موجودیتهای نمونه در متون کرده و سپس با توجه به ساختار متن در بر دارنده کلمات، بدنبال سایر موجودیتهایی از آن نوع میگردد.
3.یادگیری بی نظارت¹² :یادگیری بدون نظارت، با استفاده از منابع لغوی و الگوهای لغوی و محاسبات آماری به شناسایی میپردازد. به عبارتی تکنیک معمول برای یادگیری بدون نظارت بر پایه دسته بندی موجودیتها است.[3]

روش مبتنی بر قوانین
رهیافت های مبتنی بر قوانین، روی استخراج نام با استفاده از تعداد زیادی از مجموعه قوانین ساخته شده به صورت دستی تمرکز نموده اند . به طور کلی این سیستم ها مجموعه ای از الگوها هستند که از مشخصه ها ی گرامری (مانند ادات سخن) ،نحوی ( مانند تقدم کلمات) و املایی ( مانند بزرگ و کوچک بودن حروف ) در کنار ترکیبی از لغت نامه استفاده می کنند.
این نوع از مدل ها برای دامنه های خاص نتایج بهتری را حاصل کرده اند و توانایی تشخیص واحدهای پیچیده ای را دارند که روش های مبتنی بر یادگیری ماشین به سختی می توانند آنها را تشخیص دهند .
به هر حال روش های مبتنی بر قوانین مشکل غیر قابل حمل بودن و نیز کمبود قابلیت اطمینان را دارند. علاوه بر آن هزینه های بالای ایجاد قوانین نیز به مشکلات این روش اضافه می شود حتی اگر تغییر کوچکی در داده های ما ایجاد شود این هزینه افزایش می یابد . این نوع رهیافت اغلب منحصر به زبان یا حوزه خاص می شوند و نمی توانند به طرز مناسبی با زبان و حوزه ها ی جدید منطبق شوند.[6]
روشهای اولیه ای که برای کشف موجودیتهای نامدار پیشنهاد می شد بیشتر مبتنی بر قانون بود، در حالی که امروزه اکثر کارها به سمت استفاده از روشهای یادگیری پیش میرود.
در زبان فارسی با توجه به عدم وجود پیکره های برچسب خورده با برچسب های معنایی یا طبقات نامدار و همچنین دردسترس نبودن واژگان های کاملی چون وردنت ¹³به ناچار باید تمرکز بیشتر بر روش های مبتنی بر قاعده باشد. چون در زبان فارسی همچون زبان انگلیسی امکان درک موجودیت نامدار با توجه به بزرگی حرف اول کلمات وجود ندارد،پس بجای آن برای بهبود سیستم از برچسبگذاریهای نحوی و مجموعهای از اسامی خاص مانند مجموعه اسامی مناطق، افراد، روزهای هفته، واحدهای پولی، عناوین و... استفاده میشود.[3]

معماری سیستم مبتنی بر قوانین
سیستم NER معرفی شده در این قسمت از سه بخش اصلی : پیش پردازش، تشخیص و برچسب زنی و پالایش تولید نتیجه تشکیل شده است.

در این سیستم پس از دریافت متن، با ورودی مورد پذیرش سیستم تطبیق داده میشود، واحدهای خاص شناسایی شده و برچسب POS زده میشود. بعد از این سپس بر روی آن برچسب گذاری نحوی، با توجه به ترکیبهای اعداد، کلمات و علامات به شناسایی اولیه اعداد و برچسب گذاریهای معنایی پرداخته می شود و برچسب گذاری ثانویهای از نامهای خاص مکمل این مرحله است. در انتهای مرحله پیش پردازش، با استفاده از ساختار واژگانی اسامی خاص، سعی در شناخت این واژگان مستقل از متن میشود.
در مرحله ی شناسایی، با توجه به نحوهی چیدمان واژگان درمتن و الگوهای موجود برای هر مقوله، موجودیتهای نامدار شناخته شده و مرز آنها با توجه به تکرارها و برچسب نحوی و معنایی کلمات مشخص میشود. در انتها با حذف خطاها و تکرارهای شناخته شده، هر موجودیت در مقوله ی مناسب خود دسته بندی شده و خروجی با برچسب گذاری معنایی موجودیتهای نامدار با عنوان مقوله ای که در آن قرار می گیرند تولید می شود.[3]

مقوله بندی برچسب های معنایی
موجودیتهای نامدار در مقوله های مختلفی دسته بندی میشوند. این مقوله ها میتوانند بسته به هدف سیستم تشخیص اسامی نامدار، در طیفی از زمینه های تخصصی چون تشخیص و ... تا زمین های عامی چون نام «DNA» اسامی بیماریها و افراد یا سازمانها رده بندی شوند. در این طبقه بندی هر مقوله ی کلی هم میتواند به زیر مقوله های جزئی تر تقسیم شود. یک موجودیت نامدار میتواند در هر رده از سلسله مراتب بالا قرار گیرد. هر چه در عمق پایینتر، برچسب معنایی آن دقیقتر است.[3]

• مرحله پیش پردازش

پس از دریافت متن ورودی و پیش از انجام هر گونه عملیاتی شناسایی بر روی متن، ابتدا واحدهای خاص چون URL شناسایی می شوند و سپس پردازشهای اولیه مورد نیاز برروی متن، اجرا می شوند. این پردازش ها شامل قطعه بندی و تحلیل ساختواژی احتمالی جهت آماده سازی متن برای ورود به پیمانه برچسب زن مقوله نحوی ارتقاء یافته است. همچنین برچسبهای معنایی اولیه، برای اعداد و ترکیب آنها با علامات اطراف و نیز ساخت شناسی کلمات خاص، در این مرحله زده میشود تا در مرحله تشخیص، اصلاح و تکمیل شوند.همچنین این قسمت شامل مراحل زیر است :
1- استخراج واحدهای خاص
برخی از واحدهای متنی لازم است به همان شکل وارد شده در متن و بدون هیچ پردازش یا تغییر شکلی استخراج شوند. از جمله این واحدها می توان به آدرس صفحات وب URL یا آدرس نامه های الکترونیکی اشاره نمود چون ایجاد فاصله در این موارد امکان تشخیص را پایین می آورد.
2- قطعه بندی و برچسب گذاری مقوله نحوی ارتقاء یافته
پس از استخراج واحدهای خاص برای عمل قطعه بندی، کلیه عملیات لازم اعم از جدا کردن کلمات چسبیده، برداشتن فاصله ها و نیم فاصله های اضافه، چسباندن کلمات جدا را سیستم انجام میدهد.
بعد از این پردازشهای اولیه، متن حاصل به برچسب زن مقوله نحوی می شو دکه متن را بر اساس مجموعهای از نوع برچسب¹⁴برچسب گذاری می کند.
3- برچسب زنی اعداد
در سیستم شناسایی موجودیت های نامدار، علاوه بر برچسب زنی معمول نیاز به برچسب های پیشرفته تری نیز هست که بر اساس ترکیب برچسب های قبلی بدست می آیند. در جدول زیر برچسبهای بکار رفته در این مرحله آورده شده است.[3]

مرحله شناسایی موجودیت و برچسب معنایی آن
پس از مرحله پیش پردازش نوبت به شناسایی موجودیت های نامدار با استفاده از متن برچسب گذاری شده میرسد. در این مرحله ابتدا موجودیت های اسمی ها با استفاده از روشهای بکار برده شده که در ادامه مطرح شده اند حدس زده می شوند، سپس صحت موجودیت های اسمی و نوعشان که حدس زده شده بررسی می شود و نهایتًا مشخص میشود.
برای تشخیص یک کلمه در متنش، می توان از الگو استفاده کرد. در این سیستم نیز توجه به الگویی که هر کلمه در آن قرار گرفته به عنوان مبنای تشخیص بکار میرود. الگوها به صورت مجموعهای از کلمات و برچسبهایی هستند که در متن بدنبال هم میآیند.
الگوها به طور عام به صورت << دسته >> و یا << دسته >> ظاهر می شوند. در الگوی اول یک موجودیت یک کلمه ای و در الگوی دوم جایگاه یک موجودیت چند کلمه ایست.
مثلا «دولت » برای برای نام کشور و« نهاد* » نام یک نهاد بکار و میرود. در اینصورت عباراتی مثل "...دولت ایران.." و یا "...نهاد نمایندگی مقام معظم رهبری در دانشگاه ها..." با این الگوها مطابقت خواهند کرد.
مجموعًا در این سیستم، جستجو برای تشخیص موجودیت نامدار با کمک الگوها به این صورت انجام میگیرد که برای تک- تک عناصر برچسب گذاری شده در متن (با در نظر داشتن ضمایر چسبیده به کلمات و نیز ادات جمع)، هم برای خود کلمه وهم برای برچسب آن بررسی میشود که آیا در هیچ یک از الگوها صدق میکنند یا نه و به این ترتیب مجموعهای از اسامی خاص و نوع آنها (که عنوان مقوله هر الگو است) مشخص می شود.[3]

مرحله پالایش و تولید خروجی نهایی
پس از کشف موجودیتها و اعمال برچسب معنایی به آنها، سیستم وارد مرحله پردازش نهایی میشود. در این مرحله با توجه به ساختار سلسله مراتبی سیستم، موجودیتهای نامدار تکرار شده در یک مقوله و یا در مقوله های سطح پایینتر (گره فرزند) کشف شده و حذف میشوند. همچنین موجودیتهایی که درون موجودیتی دیگر قرار گرفته اند با توجه به مکان آنها در متن شناسایی و حذف میگردند. مثلا « انجمن شرکتهای بازرگانان نمونه » ممکن است « بازرگانان نمونه » را از مقوله شرکت ببیند ، در حالی که « شرکت بازرگانان نمونه>> از مقوله انجمن ، موجودیت خاص مورد نظر است. پس سیستم با مشاهده چنین شرایطی موجودیت نامدار تکرار شده در موجودیت نامدار دیگر را حذف میکند. نهایتًا مجموعه موجودیتهای شناسایی شده در مقوله مناسبشان دسته بندی شده و خروجی با برچسبهای معنایی تولید میشود.
این سیستم قابل استفاده به عنوان مکملی برای کاربردهایی از قبیل برچسبگذاریهای نحوی، استخراج اطلاعات و درک مطلب و خلاصه سازی ماشین میباشد.[3]

روش های مبتنی بر یادگیری ماشین
در سیستم های مبتنی بر یادگیری ماشینی ،هدف از رهیافت تشخیص واحدهای اسمی تبدیل مساله تشخیص به مساله دسته بندی است و از یک مدل آماری دسته بندی برای حل این مساله استفاده می شود.در این روش مدل به دنبال تشخیص الگوها و یافتن رابطه ی آنها با متن و ساختن یک مدل آماری و الگوریتم یادگیری ماشین است.
این سیستم ها نام ها را یافته و آن ها را بر اساس مدل به دست آمده با استفاده از روش های یادگیری ماشین به کلاس های از پیش تعیین شده مانند اشخاص ، مکان ها ، زمان ها و ... تقسیم می کند.
این مدل یادگیری، یادگیری با ناظر است یعنی سیستم با استفاده از یک مجموعه از مثال های برچسب گذاری شده ،دسته بندی را یاد می گیرد.
در این روش ابتدا سامانه به وسیله ی پیکره ای از داده های آموزشی که به صورت دستی و به وسیله ی انسان برچسب گذاری¹⁵ شده اند آموزش دیده، با یادگیری از طریق این داده ها به تشخیص خودکار اسامی خاص در متن می پردازد، که در بخش ویژگی های سندی اشاره شد.
برای برچسب زنی داده ی آموزشی از روش برچسبزنی شروع-داخل- خارج ¹⁶ استفاده میشود. در این روش، برای تشخیص موجودیتهای اسمی، کلمات متن را تک تک برچسب زنی می نماییم[1].
روش های با ناظر به داده های برچسب گذاری شده برای ساخت یک مدل آماری نیاز دارند. برخلاف رهیافت های مبتنی بر قوانین ، روش های یادگیری ماشین به راحتی به حوزه ها و زبان های دیگر منتقل می شوند. [6]

معماری سیستم تشخیص موجودیت های نامدار مبتنی بر یادگیری ماشین
شکل زیر معماری این سیستم را نشان می دهد :

مراحل شناسایی و طبقه بندی اسامی یک متن عبارتند از :
1 – یک متن با ورودی به سیستم ارائه می شود مانند جمله ی " حسن شنبه به تهران می رود."
2 – با استفاده از یک نشان گذار کلمات در متن ورودی از یکدیگر جدا می شوند.(حسن/شنبه/به/تهران/می رود)
3-با استفاده از برچسب زن دستوری نقش دستوری هر کلمه مشخص می شود(حسن/اسم | شنبه/اسم | به/حرف | تهران/اسم | می رود/فعل)
4 – با استفاده از برچسب دستوری کلمات ، اسامی شناسایی شده و از بقیه کلمات متن جدا می شوند.(حسن/شنبه/تهران)
5 –برای هر یک از اسامی بردار ویژگی لازم استخراج می شود.
6 – با استفاده از یک طبقه بند آماری ، اسامی در طبقات مربوطه طبقه بندی می شوند.

مراحل یک تا چهار مانند روش با قاعده است که توضیح داده شد.در اینجا مراحل استخراج ویژگی و طبقه بندی را توضیح می دهیم.
در مرحله استخراج برای هر یک از اسامی بردار ویژگی لازم استخراج می شود که این ویژگی ها شامل ویژگی های نویسه ای و ویژگی های دیگری که از کل متون آموزشی بدست آمده استفاده می شود.
سپس این بردارهای ویژگی به طبقه بند آماری داده می شود تا اسامی مکان و افراد از اسامی عمومی استخراج گردند.
برای آموزش سیستم خود هر اسم را به عنوان یک داده ی ورودی در نظر گرفته وبرای هر اسم با توجه به برچسب هایی که در این مجموعه داده برای آن در نظر گرفته شده یک سری ویژگی هایی را مشخص می کنیم.بعضی از ویژگی ها را هم که مربوط به خود کلمه است،می توان با استفاده از یک سری از الگوریتم های پردازش زبان بدست آورد.
برای هر اسم می توان ویژگی هایی از قبیل :
1.نقش دستوری کلمه قبل
2.نقش دستوری کلمه بعد
3.طول کلمه
4.جمع یا مفرد بودن
5.وجود پسوندهایی که باعث تولید اسم مکان می شوند مثل گاه ،خانه،آبادو..
6.وجود پسوندهایی که در اغلب موارد باعث تولید اسم خاص می شوند مثل پور،زاده،نژاد و...
7.وجود "ی" نسبی در آخر کلمه
8.درصد حضور کلمه در کل متون آموزشی به صورت اسم مکان
9.درصد حضور کلمه در کل متون آموزشی به صورت اسم خاص افراد[7]
طبقه بندی اسامی
پس از اینکه ویژگی های لازم برای آموزش سیستم استخراج شد در این مرحله با استفاده از طبقه بندی کننده ،داده های خود را طبقه بندی می کنیم.
ماشین بردار پشتیبان ¹⁷
هدف تشخیص واحدهای اسمی این است که مساله ی شناسایی را به مساله ی دسته بندی یا کلاس بندی تبدیل کند و یک مدل آماری کلاس بندی را برای حل آن به کار گیرد. رهیافت استفاده از ماشین پشتیبان برای بهتر کردن این کلاس بندی استفاده می شود.
ماشین بردار پشتیبان یکی از روش های یادگیری ماشین با ناظر معروف برای کلاس بندی دو تایی در طیف وسیعی از مجموعه داده ها است.ماشین بردار پشتیبان بهترین پاسخ را در مواقعی که مجموعه داده ها پراکنده هستند و یا هنگامی که مجموعه آموزشی کوچک است تولید می کند و با استفاده از توسعه های مختلف از این الگوریتم می توان برای مسائل با چند کلاس نیز به کار رود.
برای حل یک مسئله کلاس بندی با استفاده از یک الگوریتم با ناظر ، همواره ماشین با استفاده از یک مجموعه آموزشی که در آن کلاس هر مورد مشخص است آموزش می بیند. برای هر ماشین بردار پشتیبان ، دو مجموعه داده وجود دارد که در آن ماشین با استفاده از مجموعه داده ی آموزشی این داده ها را بر اساس خصیصه هایشان کلاس بندی می کند.
با توجه به شکل زیر یک ماشین بردار پشتیبان می آموزد که چگونه یک ابر صفحه را برای جداسازی دو کلاس مختلف با بیشترین حاشیه بیابد.

در روش استفاده از ماشین بردار پشتیبان ،ابتدا داده های موجود به دو قسمت داده های آموزشی و داده های آزمون تقسیم می شوند. در قدم بعدی ،مجموعه خصیصه ها انتخاب می شوند.در انتخاب مجموعه خصیصه یا ویژگی ، اغلب ویژگی هایی انتخاب می شوند که مختص آن زبان هستند مثل :اطلاعات لغوی وابسته به فرهنگ لغت ،حروف پسوند و پیشوند ،اطلاعات واحد اسمی که در گذشته آمده اند، کلاس های واحد اسمی ممکن و...
در بعضی موارد هم می توان از خصیصه های مستقل از زبان مانند : کلمه ی اول جمله بودن،شامل رقم بودن،حاوی رقم و ویرگول بودن و ...
در روش استفاده از ماشین بردار پشتیبان ، بعد از انتخاب ویژگی ها ، کلمات را در یک فضای n بعدی که n تعداد ویژگی ها است قرار می دهند و سپس فضا را تقسیم بندی می کنند. البته لزومی ندارد که تقسیم کننده ی فضا لزوما یک ابرصفحه باشد و با استفاده از ماشین هسته ای¹⁸به جای ماشین بردار پشتیبان می توان از یک تقسیم کننده ی غیر خطی استفاده نمود.
از این روش بر روی زبان هندی که به یک سری از ویژگی های زبان فارسی نزدیک است انجام شد که نتایج قابل قبولی داشت.[6]

مدل مخفی مارکوف
مدل مخفی مارکوف در اواخر دهه 1960 میلادی معرفی گردید و در حال حاظر به سرعت در حال گسترش دامنه کاربرد ها می باشد.دو دلیل مهم برای این مسئله وجود دارد ; اول اینکه این مدل از لحاظ ساخنار ریاضی بسیار قدرتمند است و به همین دلیل مبانی بسیاری از کاربردها را شکل داده است.
در مدل مارکف معمولی، هر حالت متناظر با یک رویداد قابل مشاهده است اما در مدل مخفی مارکف مشاهدات توابع احتمالاتی از حالت ها هستند.در این صورت مدل حاصل یک مدل تصادفی با یک فرایند تصادفی است و تنها توسط مجموعه ای از فرآیندهای تصادفی که دنباله مشاهدات را تولید می کند قابل مشاهده است.اطلاق کلمه ی مخفی به این دلیل است که درباره مسائلی صحبت می کنیم که طریقه انجام آن ها از دید ما پنهان است و البته ماهیت ماهیت آماری دارد.
در شکل زیر معماری مدل مخفی مارکف نشان داده شده است.هر شکل بیضی بیانگر یک مقدار متغیر تصادفی است.x_t مقدار تصادفی است که مقدار تغییر پذیرش در واحد زمان مخفی است و y_t مقدار تصادفی است که مقدار پذیرش در زمان t قابل مشاهده است.

مدل مخفی مارکف با پارامترهای زیر تعریف می شود:
N : (تعداد حالات (متناهی
M : تعداد خروجی های ممکن
A : ماتریس گذار حالت
B : توزیع های احتمالاتی برای خروجی های ممکن در حالت
P : توزیع احتمالاتی حالات اولیه.
مدل مخفی مارکف مانند روش های دیگر یادگیری ماشین در تشخیص واحدهای اسمی به کار می رود.یکی از کاربرد های اصلی مدل مخفی مارکف تشخیص محتمل ترین دنباله از حالت های مخفی با استفاده از الگوریتم ویتربای¹⁹ است.
از لحاظ ساختار داخلی ، مدل مخفی مارکف سعی دارد با محاسبه ی پارامترهای داخلی یک توالی( برای مساله ما جملات)را برچسب گذاری کند.
با در نظر گرفتن برچسب ها به عنوان حالت های مدل مارکف می توانیم این موقعیت را با استفاده از الگوریتم ویتربای تخمین بزنیم و مشکل کلیدی این است که چگونه مدل مخفی را با استفاده از داده های آموزشی بسازیم.در استفاده از این روش فرض می شود داده های آموزشی کافی هستند و ما به تعدادی از گذارهای بین برچسسب های ادات سخن دست یافته ایم تا مدل (X,Y,A,B,P ) را بسازیم که در آن X وy به ترتیب کلمات و برچسب ها هستند.

استفاده از مدل مخفی مارکف در بسیاری موارد به نتایج خوب و قابل قبولی منجر شده است.[6]

۳. آزمایش‌ها

برای پیاده سازی این پژوهش از نرم افزار pythone استفاده شده است که برای پردازش متن کاربرد مناسبی دارد.خروجی این مسئله به این صورت است که شما هر جمله یا عبارتی را که به برنامه می دهید اسامی خاص رو مشخص می کند و همچنین خروجی را به صورت BOI برچسب میزنیم. برچسب زنی BIO به این شکل است که هر کلمه در متن دارای برچسبیست . برچسب B به معنای شروع حوزه ی مورد نظر شماست ، I یعنی کلمه داخل حوزه مورد نظر قرار دارد وO یعنی کلمه داخل حوزه مورد نظر نیست. مانند نمونه ی زیر :

آدولف B-PERSON
بورن I-PERSON
کاریکاتوریست
و O
نقاش O
درO
شهرO
بودجویس B-LOCATION
ازO
جمهوری B-LOCATION
چک I-LOCATION
بهO
دنیاO
آمدO
برای انجام ای پروژه در phython باید ار کتابخانه NLTK استفاده شود. این کتابخانه خودش شامل یکسری برچسب زن است . ما در ابتدا برای کار خود ازSequential Taggerهای این کتابخانه استفاده کردیم . ما توابع Ngram این برچسب زن را توسط داده های فارسی که به صورت دستی برچسب خورده بودند آموزش دادیم.دیتای این پروژه شامل تعداد زیادی از جملات به همراه برچسب های آن است که مقداری را برای آموزش برچسب زن و مقداری را برای تست کارایی آن به کار میبریم.
برچسب زن ساخته شده، از سه برچسب زن UnigramTagger , BigramTagger, TrigramTagger به صورت ترکیبی استفاده می کند . نحوه ی کار یک NgramTagger به این صورت است که در وقت آموزش دیدن هر توکن را به همراه n-1 برچسب قبلیش نگهداری می کند سپس در هنگام برچسب زدن برای هر توکن با بررسی برچسب های قبلیش برچسب مناسب را به آن اختصاص می دهد. بدیهیست UnigramTagger تنها توکن را نگهداری می کند وهنگام برچسب زدن اگر توکنی دید که در هنگام آموزش دیده بود ، همان برچسب را به آن اختصاص می دهد. وگرنه برچسب NONE را به آن می دهد.
تابع برجسب زنی که ساختیم ابتدا متن را توسط DefaultTagger برچسب می زند سپس از UnigramTagger استفاده می کند و سپس نتایج را به ترتیب توسط BigramTagger و TrigramTagger بهبود می بخشد.
برنامه فایل داده های فارسی را دریافت می کند ، داده های آزمایشی و آموزشی را جدا می کند ،مثلا در شکل زیر دیتاست ما در یک فایل متنی قرار دارد که با اجرای برنامه، داده ی آموزشی آن به صورت زیر جدا می شود:(چون دیتاست اصلی خیلی بزرگ است از یک دیتا ست کوچک در این شکل استفاده شده است تا روند اجرای برنامه مشاهده شود.)

در شکل بالا یک دیتاست کوچک رو مشاهده می کنید که داده های آموزشی آن به صورت زیر بدست می آیند:

برچسب زن ها توسط دا ده های آموزشی آموزش می بینند و سپس هر متنی که به آن داده شود را برچسب زنی می کنند و در فایل دیگری می نویسند.که در آخر متن ورودی به همان شکل ذکر شده برچسب زنی می شود.

برای ارزیابی کار از تابع خود evaluate خود nltk استفاده شد. نحوه کار این تابع به این صورت است که یک متن برچسب خورده را دریافت می کند ، برچسبهای آن را حذف می کند و خودش دوباره آن را توسط برچسب زن خودمان برچسب می زند سپس با مقایسه این دو(متن ورودی و متن برچسب خورده) ، امتیاز دقت برچسب زن به دست می آید.که درباره راه حل پیاده سازی شده 91% بود .
نحوه ی اجرای این کد به این صورت است که ابتدا داده ها را از دیتاست می خواند و سپس داده های آموزشی و تست را در قالب دو فایل متنی دخیره می کند.
سپس به کمک داده های آموزشی برچسب زن را آموزش می دهد. پس از آموزش برچسب زن، داده های تست به ادامه ی برنامه داده می شود که برای اندازه گیری دقت ابتدا برچسب های داده های تست از آن جدا می شود و در یک فایل دیگر قرار می گیرد سپس داده های خام را به برچسب زن می دهیم تا آن ها را برچسب بزند و در نهایت این برچسب ها را با برچسب های اولیه مقایسه می کنیم و دقت را بدست می آوریم.
کد این پروژه را از اینجا می توانید مشاهده کنید:کد

بهبود
تابع برچسب زنی که ساختیم ابتدا متن را توسط DefaultTagger برچسب می زند سپس از UnigramTagger استفاده می کند و سپس نتایج را به ترتیب توسط BigramTagger و TrigramTagger بهبود می بخشد.برای بهبود ترتیب های این سه Tagger اجرا شد که حداکثر دقت% 92.1 شد. سپس از یک Tagger دیگر به نام RegExpTagger استفاده شد.در اینجا بر اساس دستور بان فارسی یک سری قوانین تعریف می کنیم که در شناسایی نوع کلمات به ما کمک می کند .این قوانین بر اساس قوانین پیشوندی و پسوندی در زبان فارسی است که با توجه به شناخت زبان فاسی این قوانین رو تعریف می کنیم.مثلا در قانون (r'.*آباد$', 'B-LOC'), هر کلمه ای که درای پسوند "آباد" باشد به عنوان اسم مکان تعریف می شود.در شکل زیر چند نمونه از این قوانین رو مشاهده می کنید :

اما در استفاده از این Tagger یک سری مشکل وجود دارد که به دستور زبان فارسی بر می گردد.زبان فارسی عموما ساختاریافته نیست در نتیجه تعریف الگوهایی بر اساس پسوند ها کار مشکلی است.ترکیب های مختلفی از این Tagger و قبلی ها استفاده شد که بهترین حالت بعد از defaultTagger بود که دقت در نهایت به %92.6 رسید. لینک کد:کد
لینک داده:مجموعه داده

۴. کارهای آینده

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

۵. مراجع

[1] Erik, F., Tjong, K. S., & Fien, D. M. (2003). Introduction to the CoNLL-2003 Shared Task: Language-
Independent Named Entity Recognition. CoNLL-2003 (p. 6). CNTS - Language Technology Group University of Antwerp.
[2] Jurafsky, Daniel, and James H. Martin. 2009. Speech and Language Processing: An Introduction to Natural Language Processing, Speech Recognition, and Computational Linguistics. 2nd edition. Prentice-Hall.
[3] پونه سادات مرتضوی، مهرنوش شمس فرد، "شناسایی موجودیت های نام دار در متون فارسی"، پانزدهمین کنفرانس بین المللی سالانه انجمن کامپیوتر ایران، 1388
[4] Nadeau, David, and Satoshi Sekine. "A survey of named entity recognition and classification." Lingvisticae Investigationes 30.1 (2007): 3-26.

[5] محمدمهدی حاجی،مدل سازی آماری زبان فارسی ،بهار 1384
[6]مجید عسگری بیدهندی،ساخت چهارچوبی برای استخراج خودکار نام از متن،پایان نامه مقطع کارشناسی ارشد،شهریور1390
[7]سیدعبدالحمید اصفهانی،سیدراحتی قوچانی،نادر جهانگیری ،سیستم شناسایی و طبقه بندی اسامی در متون فارسی،1389

۶. پیوندهای مفید

• تشخیص موجودیت‌های نام‌دار، پروژه درس هوش مصنوعی نیمسال دوم ۸۹-۸۸ دانشگاه علم و صنعت

• تشخیص موجودیت‌های اسمی در متن، پروژه درس هوش مصنوعی نیمسال اول ۹۲-۹۱ دانشگاه علم و صنعت

• سیستم شناسایی و طبقه بندی اسامی در متون فارسی

• پردازش زبان فارسی در پایتون

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

• Named Entity Recognition with NLTK

• Stanford Named Entity Recognizer(NER)
  [این پیاده سازی متعلق به خانم هدی علی گودرز می باشد و بنده جاهایی از کد را تغیر داده ام.]