تشخیص زبان متن

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

# مقدمه

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

# کارهای مرتبط

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

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

3. روش[^N-gram Method] ساخت مدل 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]](https://boute.s3.amazonaws.com/252-p3.PNG)
	
در این روش رشته‌ها tokenize می‌شوند و از این token ها N-gram ها تولید می‌شوند. سپس بر اساس تواتر و تکرارشان مرتب شده و پرتکرارترین N-gram ها مدل زبانی ما ار خواهند ساخت. در نهایت با به‌دست‌آوردن فاصله‌ی مدل زبان مورد نظرمان نسبت به مدل‌های زبانی به‌دست‌آمده از داده‌های آموزشی زبان متن مورد نظر را پیش‌بینی می‌کنیم. [3] 

![نمونه‌ای از محاسبه‌ی فاصله‌ی زبان از مدل‌های به‌دست‌آمده(تصویر 2)[4]](https://boute.s3.amazonaws.com/252-p4.PNG)

4. روش[^Graph-based N-gram Method] ساخت مدل N-gram برپایه گراف:
در این مدل بین هر دو شی (مثلا بین دو کلمه) یک یال وجود دارد که نشان‌دهنده‌ی توالی آن دو  خواهد بود. برای مثال دو عبارت is this a test در زبان انگلیسی و is dit een test در زبان هلندی را در نظر می‌گیریم. در این صورت تصویر زیر نشان‌دهنده گراف این دو عبارت خواهدبود.
![گراف حاصل با استفاده از  trigrams (تصویر 3) ](https://boute.s3.amazonaws.com/252-Capture.PNG)

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

# آزمایش ها

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

$$OutOfPlaceMeasure / L_{1}*L_{2}$$

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

پیاده‌سازی این الگوریتم به زبان پایتون از [این‌طریق](https://github.com/saminfatehir/tweet_language_identification) قابل دسترسی می‌باشد. برای آموزش و ارزیابی کد در این مرحله، از مجموعه داده‌ی [tweetLID](http://komunitatea.elhuyar.eus/tweetlid/resources/#Downloads) استفاده شده‌است که شامل حدود 35 هزار توئیت برچسب‌زده‌شده می‌باشد. از این مجموعه داده 300 توئیت به عنوان داده‌ی آزمایشی و بقیه‌ی داده‌ها به عنوان داده‌ی آموزشی استفاده شده‌اند.
برای ارزیابی از سه معیار دقت[^Precision]،فراخوانی[^Recall] و معیار F[^F measure] استفاده شده است که هر کدام به صورت زیر محاسبه می‌شوند:

$$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 انجام شده و نتایج آن به صورت زیر می‌باشد.

![](https://boute.s3.amazonaws.com/252-table2.PNG)

![نمودار معیارهای ارزیابی در N های مختلف](https://boute.s3.amazonaws.com/252-nemodar.PNG)
در این آزمایش‌ها احتمالا به‌دلیل کافی نبودن داده‌های آموزشی به دقت‌های چندان بالایی دست نیافتیم.با این حال به نظر می‌رسد الگوریتم برای 4=N نسبتاً نتایج بهتری دارد.هم‌چنین با استفاده از مجموعه‌ی داده‌های بزرگ‌تر احتمالا نتایج بهتری حاصل خواهدشد.[6]
# کارهای آینده 
بهترین حد مورد نظر طی آزمایش‌ها و با آزمون و خطا، 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 |

![نمودار معیارهای دقت در حدهای مختلف](https://boute.s3.amazonaws.com/252-had_nemoodar.PNG)
همان‌طور که می‌بینیم از زمانی که عدد مورد نظر را برابر 33 قرار دهیم، معیار recall برابر یک خواهد شد که بهترین حالت آن خواهدبود. اما هر چه عدد را بالاتر ببریم می‌بینیم که معیار precision بالا نمی‌رود. در واقع در این زمان سیستم، زبان همه‌ی توئیت‌های به زبان انگلیسی را به درستی تشخیص می‌دهد اما علاوه بر آن، زبان تعدادی توئیت غیرانگلیسی را نیز به اشتباه انگلیسی تشخیص می‌دهد؛ که این اتفاق ناشی از بالا بردن عدد است. به صورت کلی ما ملزم به ایجاد مصالحه بین این دو هستیم (مگر در موارد خاصی که وابسته به کاربرد یکی از آن دو دارای اهمیت باشد). معیار F measure در واقع معیاری است که هر دو معیار قبل را دربرمی‌گیرد. بنابراین با توجه به معیار F، عدد 9 بهترین حد برای سقف فاصله‌ی مدل زبانی با زبان انگلیسی می‌باشد.

پیاده‌سازی این الگوریتم به زبان پایتون از [این‌طریق](https://github.com/saminfatehir/tweet_language_identification) قابل دسترسی می‌باشد. برای آموزش و ارزیابی کد در این مرحله، از مجموعه داده‌ی [tweetLID](http://komunitatea.elhuyar.eus/tweetlid/resources/#Downloads) استفاده شده‌است که شامل حدود 35 هزار توئیت برچسب‌زده‌شده می‌باشد. از این مجموعه داده 300 توئیت به عنوان داده‌ی آزمایشی و بقیه‌ی داده‌ها به عنوان داده‌ی آموزشی استفاده شده‌اند.
برای ارزیابی از سه معیار دقت[^Precision]،فراخوانی[^Recall] و معیار F[^F measure] استفاده شده است که هر کدام به صورت زیر محاسبه می‌شوند:

$$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 های مختلف](https://boute.s3.amazonaws.com/252-nemodar.PNG)
در این آزمایش‌ها احتمالا به‌دلیل کافی نبودن داده‌های آموزشی به دقت‌های چندان بالایی دست نیافتیم.با این حال به نظر می‌رسد الگوریتم برای 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 توئیتر در [این لینک](https://github.com/saminfatehir/tweet_language_identification/blob/master/getdata.py) قابل مشاهده است.[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](https://pypi.python.org/pypi/langdetect)
[8] [langid in python](https://pypi.python.org/pypi/langid/1.0dev)
[9] [tweepy documentation](http://tweepy.readthedocs.io/en/v3.5.0/)

# پیوندهای مفید
+ [ Evaluating language identification performance](https://blog.twitter.com/engineering/en_us/a/2015/evaluating-language-identification-performance.html)
+ [Deep Learning for Supervised Language Identification for Short and Long Texts!](https://medium.com/@amarbudhiraja/supervised-language-identification-for-short-and-long-texts-with-code-626f9c78c47c)
+ [tweetLID dataset](http://komunitatea.elhuyar.eus/tweetlid/resources/#Downloads)
+ [پروژه در گیت‌هاب](https://github.com/saminfatehir/tweet_language_identification)