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

۱. مقدمه

آیا اگر یک جمله یا جملاتی داشته‌باشیم، می توانیم به سادگی زبان آن را تخشیص دهیم؟ آیا اگر یک زبان را تا حد خوبی بلد نباشیم و توانایی مکالمه یا حتی فهم آن را نداشته‌باشیم می‌توانیم جملات آن زبان را از جملات زبان مشابهی تشخیص دهیم؟ واقعیت این است که تشخیص زبان یک عبارت در زبانی خاص احتیاج به فهم آن زبان ندارد(بلکه می‌توان آن را به‌وسیله‌ی دسترسی به یک دیتاست خوب تشخیص داد!).
اهمیت مسئله از آنجایی مشخص می‌شود که قبل از هر پردازشِ زبانی شامل pars کردن، index کردن و حتی مراحل بعدی شامل کاوش معنایی متن مثلا تشخیص عواطف یا علایق از روی یک متن (مثلا یک توئیت)، ابتدا لازم است زبان متن تشخیص داده‌شود. معمولا این کار توسط کارشناس انجام می‌شود اما مطلوب، شناسایی زبان متن بدون نیاز به کارشناس است. در اینجا سعی داریم مسئله‌ی تشخیص زبان متن توئیت‌ها را که نمودی از مسئله‌ی تشخیص زبان متن است، حل کنیم.

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

چندین روش برای تشخیص زبان یک متن ارائه شده‏‌است که به اختصار از آن‌ها نام می‌بریم:

  1. براساس رشته‌های یکتای هر زبان1 :
    در هر زبان یک سری دنباله رشته‌ای خاص همان زبان وجود دارد که می‌تواند توسط یک کارشناس مشخص شده‌باشد یا از روی داده‌های آموزشی به‌دست‌آید. از اشکالات این روش این است که رشته‌های خیلی کوتاه با آن که خیلی راحت به‌دست‌می‌آیند، کمتر درستی تشخیص زبان متن مورد نظر را تضمین می‌کنند.(احتمال وجود رشته‌های کوتاه در سایر زبان‌ها زیاد است.) از طرفی هر چه طول رشته بیشتر باشد، با اطمینان بیش‍تری می‌توان زبان متن را تشخیص داد اما به همان نسبت رشته‌های یکتای طولانی در هر زبان کمیاب‌ترند.

  2. روش کلمات متواتر در هر زبان2 :
    روش قابل استفاده دیگر برای تشخیص زبان یک متن بررسی کلمات متواتر هر زبان بر اساس داده‌های برچسب‌گذاری‌شده است.البته این روش اگر tokenization در یک زبان سخت باشد روش خوبی نخواهد بود.[1]

  3. روش3 ساخت مدل N-gram:
    روش دیگر، تشخیص زبان با استفاده از مدل‌های زبانی بر پایه N-gram می باشد. N-gram در واقع قطعات N کارکتری از متن هستند. برای مثال رشته‌ی data دارای N-gram های زیر خواهد بود:
    unigrams: ,d,a,t,a,
    bigrams: d,da,at,ta,a
    trigrams: da,dat,ata,ta
    quadgrams: dat,data,ata
    5-grams: data,data
    6-grams: data

نمونه‌ای از دسته‌بندی یک رشته بر پایه N-gram ها (تصویر 1)[2]

در این روش رشته‌ها tokenize می‌شوند و از این token ها N-gram ها تولید می‌شوند. سپس بر اساس تواتر و تکرارشان مرتب شده و پرتکرارترین N-gram ها مدل زبانی ما ار خواهند ساخت. در نهایت با به‌دست‌آوردن فاصله‌ی مدل زبان مورد نظرمان نسبت به مدل‌های زبانی به‌دست‌آمده از داده‌های آموزشی زبان متن مورد نظر را پیش‌بینی می‌کنیم. [3]

نمونه‌ای از محاسبه‌ی فاصله‌ی زبان از مدل‌های به‌دست‌آمده(تصویر 2)[4]

  1. روش4 ساخت مدل N-gram برپایه گراف:
    در این مدل بین هر دو شی (مثلا بین دو کلمه) یک یال وجود دارد که نشان‌دهنده‌ی توالی آن دو خواهد بود. برای مثال دو عبارت is this a test در زبان انگلیسی و is dit een test در زبان هلندی را در نظر می‌گیریم. در این صورت تصویر زیر نشان‌دهنده گراف این دو عبارت خواهدبود.

    گراف حاصل با استفاده از trigrams (تصویر 3)

این مدل بر اساس احتمال و آمار کلاسیک ساخته خواهد شد و بر اساس روابط موجود در یک مدل حاصل از زبان‌های موجود در داده‌های آموزشی زبان یک متن جدید قابل پیش‌بینی خواهد بود.[5]

۳. آزمایش ها

برای حل این مسئله از الگوریتم روش ساخت مدل N-gram استفاده می‌کنیم. در مرحله‌ی اول سعی می‌شود عباراتی از متن توئیت‌ها که نباید تاثیری در تشخیص زبان داشته‌باشند، از آن‌ها حذف شوند. برای مثال لینک‌ها و ... . کد این فرایند به صورت جداگانه نوشته شده تا تنها یک بار روی مجموعه داده‌ی آموزشی اجرا شود. و در آن علاوه بر لینک‌ها، رشته‌های آغاز شده با @ (که قبل از نام‌های کاربری و برای مخاطب قرار دادن افراد استفاده می‌شوند5) و # (برچسب‌ها6) از متن توئیت‌ها حذف خواهندشد. چرا که زبان این رشته‌ها لزوماً با زبان اصلی توئیت یکسان نیست.
همچنین در این مرحله علائم نگارشی و اعداد حذف و تمامی حروف بزرگ متون، به حرف کوچک تبدیل می‌شوند.
در مرحله‌ی بعد با توجه به داده‌های آموزشی‌مان مدل N-gram داده‌های دارای برچسب انگلیسی را تهیه می‌کنیم. به این‌صورت که ابتدا تمامی N-gram های موجود در داده‌های آموزشی را به دست آورده و بر اساس تواتر آن‌ها را مرتب می‌کنیم. سپس تعداد مشخصی از متواترترین N-gramها مدل را تشکیل می‌دهند.
قبل از پردازش روی هر توئیت جدید (که هدف‌مان تعیین زبان آن است) مرحله‌ی پیش‌پردازش (شامل حذف رشته‌های غیرمرتبط با زبان توئیت) را روی آن اجرا می‌کنیم. در مرحله‌‌ی بعدی برای آن تمامی N-gram ها را به دست آورده و بر اساس تواترشان در یک مرتب و تعداد مشخصی از پرتکرارترین‌ها را انتخاب می‌کنیم. سپس به‌ازای هر عنصر در لیست N-gram های توئیت مورد نظر، فاصله‌ی جایگاه عنصر را در دو لیست به‌دست‌می‌آوریم. فاصله‌ی توئیت مورد نظر از مدل زبان انگلیسی به صورت زیر محاسبه می‌شود:

OutOfPlaceMeasure / L_{1}*L_{2}

که در آن OutOfPlaceMeasure در واقع مجموع فواصل جایگاه هر عنصر در دو لیست (تصویر 2)، و مخرج حاصل‌ضرب طول دو لیست می‌باشد. در این‌جا اگر فاصله‌ی توئیت مورد نظر از مدل زبان انگلیسی کوچک‌تر از حدی باشد زبان آن توئیت را انگلیسی پیش‌بینی می‌کنیم. بهترین حد مورد نظر طی آزمایش‌ها و با آزمون و خطا، 9 به دست آمد. دقت‌های به‌دست‌آمده از آزمایش‌های انجام شده در N=4 به صورت زیر می باشد:

حد مورد نظر recall precision F measure
6 0.1875 0.091 0.122
9 0.1875 0.2727 0.222
12 0.0625 0.25 0.1
15 0.25 0.085 0.127
18 0.25 0.053 0.089
21 0.3125 0.0555 0.094
24 0.3125 0.045 0.079
27 0.4375 0.052 0.093
30 0.4375 0.045 0.081
33 1 0.05 0.1
36 1 0.053 0.1009

نمودار معیارهای دقت در حدهای مختلف

همان‌طور که می‌بینیم از زمانی که عدد مورد نظر را برابر 33 قرار دهیم، معیار recall برابر یک خواهد شد که بهترین حالت آن خواهدبود. اما هر چه عدد را بالاتر ببریم می‌بینیم که معیار precision بالا نمی‌رود. در واقع در این زمان سیستم، زبان همه‌ی توئیت‌های به زبان انگلیسی را به درستی تشخیص می‌دهد اما علاوه بر آن، زبان تعدادی توئیت غیرانگلیسی را نیز به اشتباه انگلیسی تشخیص می‌دهد؛ که این اتفاق ناشی از بالا بردن عدد است. به صورت کلی ما ملزم به ایجاد مصالحه بین این دو هستیم (مگر در موارد خاصی که وابسته به کاربرد یکی از آن دو دارای اهمیت باشد). معیار F measure در واقع معیاری است که هر دو معیار قبل را دربرمی‌گیرد. بنابراین با توجه به معیار F، عدد 9 بهترین حد برای سقف فاصله‌ی مدل زبانی با زبان انگلیسی می‌باشد.

پیاده‌سازی این الگوریتم به زبان پایتون از این‌طریق قابل دسترسی می‌باشد. برای آموزش و ارزیابی کد در این مرحله، از مجموعه داده‌ی tweetLID استفاده شده‌است که شامل حدود 35 هزار توئیت برچسب‌زده‌شده می‌باشد. از این مجموعه داده 300 توئیت به عنوان داده‌ی آزمایشی و بقیه‌ی داده‌ها به عنوان داده‌ی آموزشی استفاده شده‌اند.
برای ارزیابی از سه معیار دقت7،فراخوانی8 و معیار F9 استفاده شده است که هر کدام به صورت زیر محاسبه می‌شوند:

Recall = TP / (TP+FN)
Precision = TP / (TP+FP)
F = 2*Precision*Recall / (Precision+Recall)

که در آن‌ها P نمایان‌گر برچسب انگلیسی و N نمایان‌گر برچسب غیرانگلیسی است. همچنین T و F به ترتیب موارد پیش‌بینی‌شده به زبان انگلیسی و غیرانگلیسی و مجاورت حروف نماد اشتراک آن‌هاست.
آزمایش برای N-gram های مختلف شامل {1,2,3,4,5} = N انجام شده و نتایج آن به صورت زیر می‌باشد.

N recall precision F measure
1 0.25 0.0615 0.0987
2 0.1875 0.1764 0.1818
3 0.1875 0.25 0.2142
4 0.1875 0.2727 0.2222
5 0.125 0.2222 0.19
6 0.125 0.3333 0.1818

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

نمودار معیارهای ارزیابی در N های مختلف

در این آزمایش‌ها احتمالا به‌دلیل کافی نبودن داده‌های آموزشی به دقت‌های چندان بالایی دست نیافتیم.با این حال به نظر می‌رسد الگوریتم برای 4=N نسبتاً نتایج بهتری دارد.هم‌چنین با استفاده از مجموعه‌ی داده‌های بزرگ‌تر احتمالا نتایج بهتری حاصل خواهدشد.[6]

برای مقایسه می‌توان مجموعه داده را روی ابزارهای آماده‌ای چون ماژول Langdetect در پایتون آزمایش کرد. پس از آزمایش مجموعه داده آزمایشی خواهیم دید که معیارهای ارزیابی به صورت زیر خواهند بود:[7]

Recall = 0.62
Precision = 0.77
F Measure = 0.69

هم‌چنین می‌توان مجموعه داده را روی ابزاری چون Langid نیز آزمایش کرد. پس از آزمایش مجموعه‌ داده‌ی آزمایشی، معیارهای ارزیابی به صورت زیر خواهند بود: [8]
Recall = 0.56
Precision = 0.64
F Measure = 0.6

در صورتی که ابتدا پیش‌پردازش سیستم خودمان را روی مجموعه داده‌ی آزمایشی اعمال کنیم خواهیم دید که دقت به‌دست‌آمده از این ابزار پیشرفت چشم‌گیری خواهدداشت:
Recall = 0.81
Precision = 0.72
F Measure = 0.76

که این مسئله نشان‌گر چالش موجود در داده‌های مربوط به توئیتر و نیاز محسوس این داده به پیش‌پردازش و حذف کارکترهای اضافی می‌باشد.

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

به نظر می‌رسد یکی از بزرگ‌ترین چالش‌ها در این پروژه، تهیه‌ی مجموعه داده‌ی کافی از توئیت‌ها است.(در این راستا تلاش انجام شد. نمونه کد نوشته شده برای تهیه‌ی داده با استفاده از API توئیتر در این لینک قابل مشاهده است.[9]) در صورت افزایش داده‌ها سیستم، یادگیری و در نتیجه پیش‌بینی بهتری خواهدداشت. بنابراین اولین کار افزایش داده‌ها خواهد بود.
نکته‌ی دیگر آن‌که در این پروژه، مسئله‌ی مطرح شده تنها تشخیص توئیت‌های انگلیسی از توئیت‌های غیرانگلیسی بود که البته می‌توان سیستم‌ را به تشخیص چندین زبان نیز تعمیم داد.
همچنین برای اعتبارسنجیِ روش به کار رفته، می‌توان از انواع روش‌های ارزیابی از جمله hold out،K-fold cross validation و ... نیز بهره برد و به ازای هر کدام دقت را با اعتبار بیشتری محاسبه نمود.

۵. منابع و مراجع

[1] M.Martino, R.Paulsen, Natural language determination using partial words. US Pat. 6216102B1,1996
[2] www.slideshare.net/shuyo/language-detection-library-for-java
[3] William B. CAVNAR, John M.TRENKLE, N-Gram-Based Text Categorization,In Proceedings of SDAIR-94, 3rd Annual Symposium on Document Analysis and Information Retrieval , 1994
[4] Tomáš ÖLVECKÝ,N-Gram Based Statistics Aimed at Language Identification
[5] Erik TROMP ,Mykola PECHENIZKIY, Graph-based n-gram language identification on short texts, Proc. 20th Machine Learning conference of Belgium and The Netherlands, 2011
[6] Iosu Mendizabal , Jeroni Carandell ,Daniel Horowitz, TweetSafa: Tweet language identification
[7] langdetect in python
[8] langid in python
[9] tweepy documentation

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


  1. Unique character strings

  2. Frequent Words Method

  3. N-gram Method

  4. Graph-based N-gram Method

  5. Mentions

  6. Hashtags

  7. Precision

  8. Recall

  9. F measure

محسن ایمانی

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

محسن ایمانی

همین که توانسته‌اید روی مجموعه داده واقعی پیاده‌سازی اولیه داشته باشید و این پیاده‌سازی را ارزیابی کرده‌اید، هدف این فاز را محقق کرده‌اید.
اما دقت‌های مدل پیاده‌سازی شده برای شما نیاز به بهبود دارد که ان‌شاءالله در فاز آینده تلاش خود را برای بهبود دقت مدل و یا پیاده‌سازی روش‌های باکیفیت‌تر انجام داده و نتایج را ارتقاء دهید.
در متن اشاره نکرده‌اید حد معیار فاصله (که ۹ قرار داده شده است) را چگونه بدست آورده‌اید. می‌توانستید با انجام مجموعه‌ای از آزمایش‌ها و ترسیم نمودار (مانند آن‌جه که برای پیدا کردن مقدار بهینه پارامتر N در ngram صورت گرفت) دلیل تعیین عدد ۹ به عنوان معیار را شرح بدهید.
همچنین بهتر بود به جای این که فقط برای یک زبان فاصله ngram ها را محاسبه کرده و آن را با حد معیار مقایسه کنید، برای چندین زبان مدل Ngram را تولید کرده، این فاصله را برای همه آن‌ها محاسبه نموده و زبانی که به دارای کم‌ترین فاصله است را به عنوان زبان متن تشخیص داده می‌شد.
در پیاده‌سازی نیاز به مراحل پیرایش و پیش‌پردازش بیشتری روی متن احساس می‌شود. برای مثال در N=4 پر تکرار ترین رشته رشته‌ای حاوی یک جای خالی و سه علامت دلار پشت سر هم است و بسیاری از رشته‌های پرتکرار حاوی کاراکترهای غیر مجاز نظیر فاصله, $, ', ! و ... هستند که در مرحله پیش‌پردازش این کاراکترها باید از جمله حذف شوند و یا این که همه کاراکترها به صورت کوچک (lowercase) تبدیل شوند تا نتایج بهتری داشته باشید.
همچنین بهتر بود منبع روش و پیاده‌سازی مربوط به آن را هم در متن خود ذکر می‌کردید.
برای فاز آینده و برای ارتقاء دقت مدل می‌توانید روی مجموعه داده‌های متنی زبان انگلیسی بزرگ‌تر مدل خود را آموزش دهید که در بهبود دقت تاثیر خواهد داشت.
همچنین می‌توانید از مدل‌های زبانی (Language model) برای آموزش استفاده کنید که در صورت آموزش روی یک مجموعه داده بزرگ، می‌تواند نتایج را بهبود دهند. برای آشنایی با مدل‌های زبانی می‌توانید این منبع را مطالعه کنید و برای پیاده‌سازی هم می‌توانید از کتابخانه NLTK استفاده کنید.
همچنین بهتر است برای فاز آینده مقایسه‌ای روی ابزارهای آماده تشخیص زبان مانند cld2 و Langid هم داشته و روی مجموعه داده مربوطه آن‌ها را نیز ارزیابی کنید.

رد شده

سلام
مطالب مناسبی در مورد این موضوع و حل این مسأله بیان کرده اید.
بهتر است نتایج آزمایش در بخش نتایج ذکر شود.
نموداری که رسم کرده اید،نتایج را بهتر نمایش می دهد.
سعی کنید قواعد نشانه گذاری مثل ویرگول و خطاهای املایی خود را برطرف نمایید.
بهتر است در فاز بعدی،دقت آزمایش خود را بهبود ببخشید.

تایید شده

در کل خوب بود ولی بهتر بود چند مورد صحیح و همین طور چند موردی که پیاده سازی شما به اشتباه تشخیص داده است هم آورده می شد اما بخش مقدمه و کارهای مرتبط خوب بود.

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

سلام خسته نباشید پیاده‌سازیتون خیلی ساده و قابل فهم بود که به نظر من نکته‌ی مثبتی بود، فقط اگر سعی می‌کردید با الگوریتم‌های بیشتری پیاده‌سازی کنید شاید بهتر می‌شد.
خسته نباشید

محسن ایمانی
تایید شده

باسلام
برای نوشتن فرمولها بهتر بود از سینتکس مناسب استفاده میکردید تا به فرم مناسب ریاضی نمایش داده شوند.
در این فاز با توجه به زمانی که داشتید وقت کمی گذاشته و پیشرفت کمی نسبت به فاز قبل داشتید بهتر بود قویتر عمل کنید و مشکلات موجود را رفع و دقت را بالاتر ببرید.