در این پروژه الگوریتمی را پیادهسازی میکنیم که قادر به تشخیص توئیتهای به زبان انگلیسی از بین مجموعه توئیتها به زبانهای مختلف باشد.
۱. مقدمه
آیا اگر یک جمله یا جملاتی داشتهباشیم، می توانیم به سادگی زبان آن را تخشیص دهیم؟ آیا اگر یک زبان را تا حد خوبی بلد نباشیم و توانایی مکالمه یا حتی فهم آن را نداشتهباشیم میتوانیم جملات آن زبان را از جملات زبان مشابهی تشخیص دهیم؟ واقعیت این است که تشخیص زبان یک عبارت در زبانی خاص احتیاج به فهم آن زبان ندارد(بلکه میتوان آن را بهوسیلهی دسترسی به یک دیتاست خوب تشخیص داد!).
اهمیت مسئله از آنجایی مشخص میشود که قبل از هر پردازشِ زبانی شامل 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]
روش4 ساخت مدل N-gram برپایه گراف:
در این مدل بین هر دو شی (مثلا بین دو کلمه) یک یال وجود دارد که نشاندهندهی توالی آن دو خواهد بود. برای مثال دو عبارت is this a test در زبان انگلیسی و is dit een test در زبان هلندی را در نظر میگیریم. در این صورت تصویر زیر نشاندهنده گراف این دو عبارت خواهدبود.
این مدل بر اساس احتمال و آمار کلاسیک ساخته خواهد شد و بر اساس روابط موجود در یک مدل حاصل از زبانهای موجود در دادههای آموزشی زبان یک متن جدید قابل پیشبینی خواهد بود.[5]
۳. آزمایش ها
برای حل این مسئله از الگوریتم روش ساخت مدل N-gram استفاده میکنیم. در مرحلهی اول سعی میشود عباراتی از متن توئیتها که نباید تاثیری در تشخیص زبان داشتهباشند، از آنها حذف شوند. برای مثال لینکها و ... . کد این فرایند به صورت جداگانه نوشته شده تا تنها یک بار روی مجموعه دادهی آموزشی اجرا شود. و در آن علاوه بر لینکها، رشتههای آغاز شده با @ (که قبل از نامهای کاربری و برای مخاطب قرار دادن افراد استفاده میشوند5) و # (برچسبها6) از متن توئیتها حذف خواهندشد. چرا که زبان این رشتهها لزوماً با زبان اصلی توئیت یکسان نیست.
در مرحلهی بعد با توجه به دادههای آموزشیمان مدل N-gram دادههای دارای برچسب انگلیسی را تهیه میکنیم. به اینصورت که ابتدا تمامی N-gram های موجود در دادههای آموزشی را به دست آورده و بر اساس تواتر آنها را مرتب میکنیم. سپس تعداد مشخصی از متواترترین N-gramها مدل را تشکیل میدهند.
قبل از پردازش روی هر توئیت جدید (که هدفمان تعیین زبان آن است) مرحلهی پیشپردازش (شامل حذف رشتههای غیرمرتبط با زبان توئیت) را روی آن اجرا میکنیم. در مرحلهی بعدی برای آن تمامی N-gram ها را به دست آورده و بر اساس تواترشان در یک مرتب و تعداد مشخصی از پرتکرارترینها را انتخاب میکنیم. سپس بهازای هر عنصر در لیست N-gram های توئیت مورد نظر، فاصلهی جایگاه عنصر را در دو لیست بهدستمیآوریم. فاصلهی توئیت مورد نظر از مدل زبان انگلیسی به صورت زیر محاسبه میشود:
که در آن OutOfPlaceMeasure در واقع مجموع فواصل جایگاه هر عنصر در دو لیست (تصویر 2)، و مخرج حاصلضرب طول دو لیست میباشد. در اینجا اگر فاصلهی توئیت مورد نظر از مدل زبان انگلیسی کوچکتر از حدی باشد زبان آن توئیت را انگلیسی پیشبینی میکنیم. (بهترین حد مورد نظر طی آزمایشها و با آزمون و خطا، 9 به دست آمد.)
پیادهسازی این الگوریتم به زبان پایتون از اینطریق قابل دسترسی میباشد. برای آموزش و ارزیابی کد در این مرحله، از مجموعه دادهی tweetLID استفاده شدهاست که شامل حدود 35 هزار توئیت برچسبزدهشده میباشد. از این مجموعه داده 300 توئیت به عنوان دادهی آزمایشی و بقیهی دادهها به عنوان دادهی آموزشی استفاده شدهاند.
برای ارزیابی از سه معیار دقت7،فراخوانی8 و معیار F9 استفاده شده است که هر کدام به صورت زیر محاسبه میشوند:
که در آنها P نمایانگر برچسب انگلیسی و N نمایانگر برچسب غیرانگلیسی است. همچنین T و F به ترتیب موارد پیشبینیشده به زبان انگلیسی و غیرانگلیسی و مجاورت حروف نماد اشتراک آنهاست.
آزمایش برای N-gram های مختلف شامل {1,2,3,4,5} = N انجام شده و نتایج آن به صورت زیر میباشد.
در این آزمایشها احتمالا بهدلیل کافی نبودن دادههای آموزشی به دقتهای چندان بالایی دست نیافتیم.با این حال به نظر میرسد الگوریتم برای 4=N نسبتاً نتایج بهتری دارد.همچنین با استفاده از مجموعهی دادههای بزرگتر احتمالا نتایج بهتری حاصل خواهدشد.[6]
۴. کارهای آینده
۵. منابع و مراجع
[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
۶. پیوندهای مفید
Unique character strings
Frequent Words Method
N-gram Method
Graph-based N-gram Method
Mentions
Precision
Recall
F measure