جای خالی را پر کنید

0. تعریف کوتاه مسئله

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

1. مقدمه

حتما گاهی برای شما نیز اتفاق افتاده که جمله ای مدنظر شماست اما ذهن شما در ساختن یک کلمه از آن جمله کار نمیکند! یا اینکه مشغول یادگیری زبان جدیدی هستید و میخواهید بدانید برای یک جمله چه نوع کلمه ای ( قید، صفت، فعل و ...) در یک جایگاه خاص مناسب است، یا مشغول خواندن یک متن از یک کتاب قدیمی هستید و یک یا چند کلمه از آن جمله ناخواناست و از قضا درک مفهوم آن جمله برای شما اهمیت ویژه ای دارد. در آنجا شما میتوانید با استفاده از این نرم افزار کلمه مدنظر خود را با توجه به سایر کلمات و ساختار آن جمله پیدا کنید. این نرم افزار از قابلیت خودیادگیری با توجه به جملاتی که کاربر وارد کرده و کلمه موردنظر خود را پیدا نموده است دارا میباشد و برای شروع اولیه از یک دیتاست به حجم 1.5 گیگابایت بهره میبرد. تعیین ساختار جمله با توجه به نوع کلمات موجود در آن جمله تشخیص داده میشوند. پس ما به ابزارهای پردازش متن و الگوریتم های ویژه ای نیازمندیم.

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

مراحل پیش پردازشی:

الگوریتم پورتر (porter)
اکثر کلماتی که ما در زبان استفاده میکنیم مشتق کلماتی معمولا 3 حرفی به نام ریشه آن کلمه هستند. اگر کمی بازتر به این مسئله نگاه کنیم متوجه میشویم که بسیاری از کلمات را میتوان در یک مجموعه معنایی قرار داد. مثلا کلمات "همسایه" ، "همسایگی" ، "همسایگان" و ... همه تقریبا یک مفهوم را به شنونده منتقل میکنند و از آنجا که بررسی تک تک کلمات زبان کاری بسیار طولانی و درواقع ناممکن است، پس ما باید الگوریتمی داشته باشیم که تا حدی بتواند این کلمات را در یک قالب قرار دهد. الگوریتمی که کلمات زبان انگلیسی را stem میکند و ریشه آنها را برمیگرداند الگوریتم porter است. نمونه ای از کار الگوریتم porter در زیر نشان داده شده است.


بد نیست نگاهی به متون نوشته شده درمورد ریشه یاب های فارسی بیندازیم. ریشه یاب فارسی شبیه همان الگوریتم porter است. هر دوی آنها بر اساس ریخت شناسی کلمات و در نتیجه بر تکیه بر پیشوند کلمات پایه گذاری شده اند. البته به دلیل تفاوتهای زبان فارسی و انگلیسی تفاوتهایی در ریشه یاب‌های آنها وجود دارد. مثلا اینکه در زبان فارسی مصوتها نوشته نمیشوند اماتلفظ میشوند. نکته دیگری که وجود دارد در زبان فارسی حداقلی برای تعداد حروف ریشه یک کلمه درنظر گرفته شده است (حداقل 3 حرف). [1] [نظر نویسنده: البته این نظریه در برخی موارد میتواند اشتباه باشد. مثلا ریشه کلمه‌ی "روان" کلمه‌ی "رو" است که 2 حرف دارد.] این هم بخشی از DFA مربوط به ریشه یابی کلمات فارسی
DFA for Farsi Stemmer

ترتیب بندی کلمات با n-Gram
ترتیب کلمات نقش مهمی را در ساختار جمله بازی میکند. [2] n-Gramها نمایش آماری کلمات در یک دیتاست هستند به طوریکه درصد احتمال آمدن کلمه‌ی nام را بر حسب n-1 کلمه‌ی قبلی تعیین میکند. تحقیقات و آزمایشات بر روی n-Grams نشان داده هنگامی که n برابر 3 باشد الگوریتم در حالت بهینه خود قرار میگیرد. [3]

پیش بینی با روش Multinomial Naive Bayes
این روش از همان قانون بیز معروف الهام گرفته شده که احتمال آمدن کلمه ای در جمله را بیان میکند[4]:

P(T|G_i) = \frac {P(G_i)P(T|G_i)}{P(T)}

روش (TF (Term Frequency و (IDF (Invert Document Frequency نیز دو روشی هستند که میتوان به کمک آنها به تعداد کلمات پرتکرار در اسناد و تعداد کلمات پرتکرار در یک سند و یک سری اطلاعات دیگر دست یافت. تکیه بر این امر و این اطلاعات آماری ممکن است ما را به پاسخ صحیح نزدیک کند اما قطعا جواب مسئله ما نخواهد بود. برای بهبود پیش بینی انجام شده باید از سیستم های دانش لغوی و معنایی کلمات یک زبان بهره جوییم.[5]
این هم فلوچارت یک الگوریتم دیگر[6] که دیدنش خالی از لطف نیست:

فلوچارت

طی تحقیقات و جستجوهایی که انجام شد، بهترین و نزدیک ترین پروژه به موضوع پروژه من وب سایتی به نام phraseup با آدرس www.phraseup.com میباشد. همانطور که در ادامه تصاویری از این سایت مشاهده میکنید تحت یک textbox جمله ای از کاربر گرفته میشود که حداقل حاوی 2 کلمه مشخص شده است. سپس با گذاشتن علامت ستاره (*) به جای کلمات جاافتاده تمامی پیشنهادهای سایت برای پرکردن جای خالی به کاربر نشان داده میشود.[6]
هدف اصلی این سایت همانطور که در توضیحاتش گفته شده کمک به افرادیست که کلمه ای به اصطلاح "نوک زبانشان است" اما آن را فراموش کرده اند. همچنین برای کسانی که میخواهند انگلیسی را به عنوان زبان دوم خودشان (ESL) انتخاب کنند میتواند مفید باشد.
نمونه ای از حدس کلمه جاافتاده در سایت مذکور

نمونه ای دیگر

3. آزمایش ها

لینک پروژه در سایت گیت هاب:

آدرس پروژه در گیت

چالش‌ها:

ابتدا لازم دانستم درمورد چالش‌های نه چندان کوچکی که در طی فرآیند به آنها برخوردم را بازگو کنم. مهمترین چالش انتخاب زبان مورد بررسی بود که از بین دو زبان فارسی و انگلیسی زبان انگلیسی را غلی‌رغم مزایایی که زبان فارسی داشت (مثلا نبودن نمونه مشابه و ...) به دلایل زیر برگزیدم:

  1. وجود داده‌های بسیار بیشتر برای جملات انگلیسی، با این که داده‌های زیادی برای زبان فارسی مانند "پیکره بی‌جن‌خان" یا مجموعه‌ی بزرگ دیگری که کلمات فارسی و تعداد تکرار آنها در آن بود وجود داشتند.

  2. وجود ابزارهای کارآمدتر برای پردازش زبان، البته ابتدا که تصمیم من به کار روی زبان فارسی بود ماژول "هضم" را برای پایتون درنظرگرفتم که به دلیل مشکلاتی از قبیل نصب نشدن ماژول libwapiti و ... قادر به کارکردن با آن نبودم و تصمیم به کار روی زبان انگلیسی و استفاده از ماژول nltk گرفتم.

  3. وجود گرامر قالب‌بندی شده‌تر برای زبان انگلیسی که قدرت تشخیص یک کلمه با توجه به کلمات قبل و بعد آن را به من میداد.

توضیحات:

در اینجا در دو بخش به توضیح روند انجام پروژه میپردازم.
قابل ذکر است که در اصل این پروژه شامل دوقسمت پردازشی است. جمله وارد شده دقیقا مانند یک جمله معمولی‌ست و برنامه ابتدا با توجه به ساختار جمله باید مکان کلمه‌ی جاافتاده را تشخیص دهد، که این قسمت در این فاز پروژه پیاده‌سازی نشده است و تشخیص جای خالی با علامت "$" که کاربر به جای جای خالی قرار میدهد تشخیص داده میشود. قسمت دوم نیز حدس کلمه درست برای آن جای خالیست که با توجه به مجموعه داده‌های گردآوری شده انجام میشود.

داده ها:

یک مجموعه بسیار بزرگ به حجم 4 گیگابایت به عنوان مجموعه train که از وبسایت معرفی شده دریافت کردم، شامل جملات بسیار زیاد به زبان انگلیسی.`

روش انجام آزمایش:

ابتدا جمله‌ی گرفته شده از کاربر را با استفاده از تابع word_tokenize از ماژول nltk جدا کرده و سپس با استفاده از تابع دیگری از این ماژول به نام pos_tag واژه‌های برگردانده شده در مرحله قبل را برچسب‌گذاری می‌کنیم. همانطور که گفته شد کلمه جاافتاده با علامت "$" مشخص شده است. با نوشتن توابعی هرچند بسیار ناقص، سعی در پیداکردن برچسب کلمه‌ی جاافتاده داشتم، که این کار را با استفاده از قوانینی همچون دو کلمه که میانشان and یا or باشد هم برچسب هستند یا اینکه قید بعد از فعل یا صفت قبل از اسم می‌آیند انجام دادم. سپس زمانی که برچسب کلمه‌ جاافتاده مشخص شد با استفاده از تابع Compare از ماژول ngram جمله‌ی گرفته شده از کاربر را با حدود 9000 جمله از دیتاستی که درموردش صحبت شد مقایسه میکنیم. سپس نتیجه را مرتب کرده و 10 جمله‌ی نزدیک به جمله‌ی دریافتی را برمیگردانیم و نقشی از آن جمله‌ها که مساوی با نقش کلمه جاافتاده ما باشد برمیگردانیم. نمونه‌ای از خروجی برنامه را میتوانید در زیر ببینید:

نمونه‌ی خروجی

درصد دقت

برای محاسبه درصد دقت برنامه نوشته شده در فاز دوم پروژه 10 جمله متفاوت مثال زده شد و با توجه به جملات معقولی که در 20 جمله اول خروجی پیدا می‌شد درصد دقت هر مرحله را محاسبه کردم. لازم به ذکر است منظور از جملات معقول جملاتی است که در زبان انگلیسی حداقل یک مکالمه برای آن وجود داشته باشد. به عبارت دیگر این جمله از نظر لغوی، نحوی و معنایی درست باشد.
نتایج به دست آمده به شرح زیر است:

                           |      شماره آزمایش      |      دقت به درصد     |
                           | :------------------:  | :-------------------: |
                           |           35          |             1         |
                           |           45          |             2         |
                           |           30          |             3         |
                           |           30          |             4         |
                           |           50          |             5         |
                           |           40          |             6         |
                           |           00          |             7         |
                           |           25          |             8         |
                           |           20          |             9         |
                        |           40          |             10        |
                           |           35          |             11        |

نمونه شماره 7 نقش کلمه به کلی اشتباه حدس زده شده بود و هیچکدام از جواب‌ها معقول نبودند. بدون در نظر گرفتن این نمونه درصد دقت برنامه از گرفتن میانگین این درصدها بجز نمونه 7 برابر با 35.5 درصد محاسبه شد. (درصد دقت با درنظر گرفتن نمونه 7 برابر با 32 درصد می‌باشد) شایان ذکر است به دلیل تحلیل شخصی از جملات حاصل از برنامه ممکن است درصد دقت بدست آمده در هر مرحله با خطا محاسبه شده باشد که سعی کردم برای اینکه دقت، بیش از میزان دقت واقعی محاسبه نشود انتخاب جملات معقول را سختگیرانه انجام بدهم.
همانطور که در پاراگراف اول بخش توضیحات گفته شد، جای کلمه خالی با استفاده از یک «$» مشخص می‌شود. یکی از اقدامات صورت گرفته در فاز تکمیل پروژه رفع این مشکل است که برنامه با توجه به ساختار جمله نقش و مکان کلمه‌ی جاافتاده را مشخص کند. طبیعی است که با انجام این کار بخاطر خطایی که در این مرحله بوجود می‌آید درصد دقت برنامه کم می‌شود. برای آزمایش این نکته جدول درصد دقت را دوباره با همان جملاتی که قبلا وارد کردم تشکیل می‌دهم. با این تفاوت که جمله وارد شده مانند یک جمله معمولی فاقد علامت است.

                           |      شماره آزمایش      |      دقت به درصد     |
                           | :------------------:  | :-------------------: |
                           |           45          |             1         |
                           |           10          |             2         |
                           |           35          |             3         |
                           |           30          |             4         |
                           |           35          |             5         |
                           |           35          |             6         |
                           |           05          |             7         |
                           |           25          |             8         |
                           |           00          |             9         |
                           |           30          |             10        |

همانطور که مشاهده می‌شود در برخی نمونه‌ها تعداد جواب‌های درست همانند حالت قبلیست. این حالاتی است که مکان کلمه‌ی جاافتاده درست تشخیص داده شده است و در نمونه‌های 2، 7 و 9 به دلیل تشخیص اشتباه مکان کلمه جملات معقول در بین جملات خروجی به سختی قابل پیداکردن بودند. پس می‌توان از دید دیگری نیز این دقت را محاسبه کرد. به طور میانگین از هر 10 جمله 7 جمله تشخیص درست وجود دارد. پس برنامه در تشخیص مکان کلمه دارای 70 درصد دقت می‌باشد. از طرفی محاسبه کردیم دقت برنامه در حالتی که مکان کلمه مشخص بود تقریبا برابر 35 درصد بود. پس انتظار داریم به صورت تئوری دقت برنامه برابر با

35 * 0.7 = 24.5
محاسبه میشود. از طرفی از تحلیل جدول به دست آمده درصد دقت برابر با 25 درصد خواهد بود که به عدد به دست آمده از محاسبه تئوری بسیار نزدیک است.
در قسمت بعد با اضافه کردن چند تابع به بخش پردازش زبان برنامه توانستم سطح دقت برنامه را به سطح دقت قبلی (همان 35 درصد) برسانم که با وجود عدم تغییر در سطح دقت کلی برنامه، اضافه کردن قدرت تشخیص کلمه‌ی جاافتاده با دقت 70 درصد، ویژگی مهمی بود که به دست آمد. جدول حاصل از آزمایش این قسمت در زیر آمده است:

                          |      شماره آزمایش      |      دقت به درصد     |
                          | :------------------:  | :-------------------: |
                          |           35          |             1         |
                          |           35          |             2         |
                          |           30          |             3         |
                          |           35          |             4         |
                          |           35          |             5         |
                          |           30          |             6         |
                          |           35          |             7         |
                          |           45          |             8         |
                          |           25          |             9         |
                          |           40          |             10        |

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

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

5. مراجع

[1] Kazem Taghva, Russel Beckley, Mohammad Sadeh; "A Stemming Algorithm for the Farsi Language"; Iformation Science Research Institute; Unversity of Nevada; Las Vegas; 2003
[2] Richard G.Freedman and Jingyi Guo; University of Massachusetts Amherst
William H.Turkett, Jr. and V.Paul Pauca; wake forest university
[3] Lesher, Moulton and Higginbotham; 1999
[4] Kevyn Collins-Thompson and Jamie Callen; "A Language Modeling Approach to Predicting Reading Difficulty"; Language Technologies Institute; Carnegie Mellon University 2001
[5] Masood Ghayoomi, Saeedeh Momtazi; "An OverView on the Existing Language Models for Prediction System as Writing Assistant Tools; Stanford University
[6] Masood Ghayoomi, Seyyed Mostafa Assi; "Word Prediction in a Running Text: A Statistical Language Modeling for the Persian Language" ; institute for Humanities and Cultural Studies, Tehran
[7] Website: www.phraseup.com
[8] Ciprian Chelba,Tomas Mikolov, Mike Schuster, Qi Ge, Thorsten Brants, Phillipp Koehn, Tony Robinson; "One billion Word Benchmark for Measuring Progress in Statistical Language Modeling"; "GOOGLE" ; University of Edinburgh

محسن ایمانی

کار شما در این فاز در کل قابل قبول است. اما نقاط ضعفی هم دارد که باید برای فازهای آینده آن‌ها را مرتفع سازید:

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

  • مراجع شما مقداری قدیمی می‌باشد، همچنین مراجع را اصلا درست ارجاع ندادید. مثلا ارجاع دوم شما اصلا نام ندارد.

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

  • آوردن یک فلوچارت بدون این که توضیحی در مورد مراحل و روش مورد استفاده آن بدهید کار چندان جالبی نیست.

  • خواننده متن در نهایت متوجه نمی‌شود که زبان هدف شما فارسی است و یا انگلیسی؟

بسیار عالی بود ، فقط نکاتی که به نظرم رسید به روند انجام پروژه کمک میکنه رو اشاره میکنم:
1- به نظرم اگر از کلمات انگلیسی کمتر استفاده کنید و بجای آن معادل فارسی را به کار ببرید و در پا نویس معادل انگلیسی آن را بنویسید بهتر بود.
2-اگر سعی بشه متن رسمی تر بشه بهتره و بیشتر شبیه مقاله میشه .
3-در مورد نمونه خروجی اگر یک بررسی انجام میشد و درصد جواب های درست و نادرست گزارش میشد بهتر بود.
موفق باشید .

تایید شده

خسته نباشید عرض میکنم خدمتتون.
پروژتون رو مطالعه کردم و چند نکته بنظرم رسید :
۱- بهتر بود یک مسیر رو در پیش میگرفتید و از اول روی زبان انگلیسی کار میکردید با این حال تلاش شما قابل تقدیر است .
۲- من یک مقدار جست و جو کردم در مورد موضوعتون . در حال حاضر سریع ترین و کارآمد ترین روش پیاده سازی استفاده از روش های الهام گرفته از یادگیری عمیق هست . پیشنهاد میکنم به طور مثال یک نگاه به وبلاگ http://www.yseam.com/blog/WV.html بندازین و مراجع انگلیسی رو بررسی بکنید.
۳- در صورتی که از کورپوس ۴ گیگابایتی استفاده کردید احتمالا امکان رقابت با موتور گوگل رو دارید . پیشنهاد میکنم یه مقدار دیتا ست رو کوچیک کنید.

آرزوی موفقیت در فاز بعدی

محسن ایمانی

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

رد شده

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

محسن ایمانی

در این فاز از پروژه از شما انتظار می‌رفت که تلاش بیشتری برای بهبود نتایج خود، نظیر استفاده از سایر روش‌ها، انجام دهید.
همچنین انتظار می‌رفت که کد پیاده‌سازی خود را با توضیحات بیشتری تکمیل نمایید.

اما در کل ارزیابی و گزارش نتایج شما و همچنین تلاشی که برای بهبود پیاده‌سازی انجام داده‌ای انتظار ما را در این فاز محقق نموده است.

موفق باشید