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

۱. مقدمه

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

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

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

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

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

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

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

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

   

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

۳. آزمایش ها

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

که در آن 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 توئیت به عنوان داده‌ی آزمایشی و بقیه‌ی داده‌ها به عنوان داده‌ی آموزشی استفاده شده‌اند.
برای ارزیابی از سه معیار دقت⁷،فراخوانی⁸ و معیار F⁹ استفاده شده است که هر کدام به صورت زیر محاسبه می‌شوند:

که در آن‌ها 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

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

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

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

هم‌چنین می‌توان مجموعه داده را روی ابزاری چون Langid نیز آزمایش کرد. پس از آزمایش مجموعه‌ داده‌ی آزمایشی، معیارهای ارزیابی به صورت زیر خواهند بود: [8]

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

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

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

به نظر می‌رسد یکی از بزرگ‌ترین چالش‌ها در این پروژه، تهیه‌ی مجموعه داده‌ی کافی از توئیت‌ها است.(در این راستا تلاش انجام شد. نمونه کد نوشته شده برای تهیه‌ی داده با استفاده از 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

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

• Evaluating language identification performance

• Deep Learning for Supervised Language Identification for Short and Long Texts!

• tweetLID dataset

• پروژه در گیت‌هاب