استخراج اطلاعات با استفاده از یادگیری نیمه‌نظارتی

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

یکی از راه‌های پاسخ به این مساله، گسترش دانسته‌ها توسط ماشین است. مثلا اگر ما *اسم ۲۰ بازیکن فوتبال* را بدانیم، می‌توانیم از آنها برای پیدا کردن نام بقیه استفاده کنیم. سپس می‌توانیم نام‌هایی را که فکر می‌کنیم به درستی استخراج شده‌اند را هم به دانسته‌های اولیه اضافه کنیم و اینطوری الگوهای جدیدی را برای استخراج بدست بیاوریم. به این ترتیب اگرچه داده‌های آموزشی اولیه کم باشد، می‌توانیم مرحله به مرحله روی داده‌های بیشتری آموزش ببینیم. این روش به خودراه‌اندازی[^Bootstrapping] معروف است که یکی از انواع یادگیری نیمه‌نظارتی[^Semi-Supervised Learning] به حساب می‌آید.

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

# مقدمه
**یادگیری نیمه نظارتی چیست؟**
همانطور که از اسم آن مشخص است روشی میان یادگیری نظارتی و یادگیری غیر نظارتی می‌باشد. در این روش بعضی از داده‌ها دارای بچسب بوده و بعضی نیز برچسب ندارند. به علت اینکه در خیلی از برنامه‌های کاربردی عملیات برچسب گذاری هزینه‌بر و زمان‌بر می‌باشد. برای اینکه کارایی را افزایش داده و از کل توان خود در حل مسئله برای بهبود بیشتر استفاده کنیم می‌توان از داده‌های بدون برچسب نیز استفاده نمود. در یادگیری نیمه‌نظارتی هدف یافتن روش‌هایی است که با استفاده از داده‌های بدون برچسب و داده‌های برچسب‌دار به حل مسئله پرداخته و کارایی را نسبت به قبل افزایش دهند[4].

**چه زمانی باید از یادگیری نیمه نظارتی استفاده کرد؟**
پرسش اصلی در زمینه یادگیری نیمه نظارتی این است که اصولا تحت چه شرایطی باید از این روش استفاده کرد. به عبارتی در چه مسائلی و یا روی چه مجموعه داده‌هایی استفاده از این روش منجر به بهبود عملکرد عامل یادگیرنده یا جداساز می‌شود. یا بطور کلی‌تر آیا استفاده از داده‌های بدون بچسب واقعا می‌تواند کارایی را بهبود بخشد. نگاهی به حجم مقلات ارائه شده در این زمینه نشان می‌دهد پاسخ مثبت است، اما یک شرط اساسی وجود دارد و آن هم اینکه باید توزیع نمونه‌ها که به کمک داده‌های بدون برچسب برآورد می‌شود، مناسب مسئله جداسازی باشد. در حقیقت داده‌های بدون برچسب کمک می‌کند تا دانش اولیه درمورد توزیع داده‌ها کسب شود.
به بیان دقیق‌تر ، در صورتی استفاده از داده‌های بدو ن برچسب مفید واقع خواهد شد، که دانش بدست آمده از داده‌های بدون برچسب درمورد توزیع داده‌ها (p(x، حاوی اطلاعات مفیدی برای استنتاج درمورد (p(y|x باشد. اگر این موضوع در یک مسئله خاص برقرار نباشد، روش نیمه‌نظارتی کمکی در بهبود تعمیم پذیری جداساز نخواهد داشت، حتی ممکن است داده‌های بدون برچسب با اطلاعات نادرستی که درمورد توزیع داده‌ها می‌دهند، موجب افزایش خطای جداسازی شوند. بر این اساس واضح است برای استفاده از روش‌های نیمه‌نظارتی، پیش‌فرض‌های بخصوصی باید برقرار باشد که این پیش‌فرض‌ها همان دانش پیشین هستند. همان طور که گفته شد استفاده از داده‌های بدون برچسب درحقیقت معادل با یادگیری توزیع داده‌ها است، و هر فرآیند یادگیری برای همگرا شدن نیازمند یک دانش پیشین است[5].
پیش فرض‌ها:
• پیش فرض همواری در یارگیری نیمه نظارتی[^The semi supervised smoothness assumption] : اگر دو نقطه x1 و x2 در یک منطقه با چگالی بالا نزدیک به هم باشند، برچسب‌های متناظر آن‌ها یعنی y1 و y2 هم باید نزدیک باشند.
• پیش فرض خوشه[^The Cluster Assumption] : داده‌های موجود در یک خوشه احتمالا برچسب‌های مشابهی دارند.
• پیش فرض خمینه[^The Manifold Assumption] : ( درفضای ورودی با بعد بالا) داده‌ها (تقریبا) روی یک خمینه با بعد پایین‌تر قرار دارند و تابع جداساز روی خمینه داده‌ها هموار است.
روش های یارگیری نیمه نظارتی[7]:
Constrained Clustering
Distance Metric Learning
Manifold Methods in Vision
Sparsity based Learning
Active Learning

**استخراج اطلاعات** 
استخراج اطلاعات به منظور تبدیل متن به اطلاعات قابل استفاده از منظر ماشین است. رویه مرسوم در پژوهش‌های دیرین مرتبط با این موضوع مبتنی بر اهداف از پیش تعیین شده بوده است. یعنی ماشین باید نوع خاصی از اطلاعات را که احتمالا به اشکال مشخصی نیز در متن بیان می‌شوند، استخراج می‌کرده. << استخراج هدفمند اطلاعات>> عنوان مناسبی برای این نحوه نگاه به مسئله به نظر می‌رسد. مثلا استخراج زمان و مکان برگزاری مسابقات را می‌توان یک استخراج هدفمند دانست که معمولا باید روی دامنه مشخصی از متن‌ها انجام  گیرد.
وقتی استخراج اطلاعات را به صورت یک مسئله باناظر تعریف می‌کنیم، در واقع استخراج هدفمند را برگزیده‌ایم. یعنی فرض می‌کنیم که اطلاعات مشخصی برای استخراج، توسط انسان مشخص شده‌اند و حالا ماشین باید این داده‌ها را یاد بگیرد تا بتواند از متون جدید نیز داده‌های مورد نظر را استخراج کند. اگرچه الزامی وجود ندارد که مجبور به انتخاب رابطه یا روابطی محدود باشیم، نوع نزدیک شدن ما به مسئله عملا منجر به این محدودیت می‌شود. از روش های استخراج هدفمند اطلاعات می‌توان به روش‌های مبتنی بر قاعده که در سامانه هایی از قبیل YAGO  و DBpedia استفاده شده است نام برد[9,10]. در این سامانه‌ها با استفاده از قواعد دست ساز، انبوه اطلاعات ساخت یافته موجود در ویکی پدیا و یا وردنت استخراج می‌شوند. روش دیگر استخراج هدفمند اطلاعات، استفاده از مدل‌های گرافی است. برای نمونه استخراج ویژگی‌های مقاله از میان سربرگ و ارجاع‌ها به شکل یک مسئله پیش بینی ساختار تعریف و حل شده است[11]. روش دیگر استخراج اطلاعات استفاده از توابع کرنل است که برای این کار تعریف شده و مورد استفاده قرار گرفته‌اند. برای نمونه استفاده از تجزیه کم عمق جمله برای تشخیص رابطه اشخاص و نهادها و همچنین مکان سازمان‌ها بررسی شده‌است[12].


# کارهای مرتبط
**سامانه (NELL(Never Ending Lanquage Learning:  **
سامانه NELL برای پر کردن شکل ساده شده‌ای از یک هستان شناسی ایجاد شده است. در واقع این سامانه قرار نیست رابطه یا نوع جدیدی کشف کند و فقط برای پیدا کردن نمونه‌ها ایجاد شده است. همچنین این سامانه با هدف ایجاد هم افزایی در استخراج اطلاعات طراحی شده است. یعنی قرار است ماشین از اطلاعات استخراج شده برای بهبود کیفیت استخراج استفاده کند. NELL برای رسیدن به این هدف، اطلاعات را با روش‌های مختلف استخراج می‌کند و سپس به سازگاری میان آن‌ها می‌اندیشد. حاصل این فرایند افزوده شدن نمونه‌های مطمئن به هستان شناسی اولیه است که در عمل منجر به بهبود کیفیت استخراج می‌شود[1] .
*منابع استخراج اطلاعات*
دو نوع اطلاع مورد هدف این سامانه هستند که با تعداد آرگومان‌ها از هم تفکیک می‌شنود. نمونه‌هایی از یک نوع مثل اسامی شهرها تنها یک آرگومان دارند و روابط میان دو نوع مثل عضو بودن یک بازیکن در یک تیم، که دو آرگومان دارد. این سامانه با مجموعه‌ای از این نوع و رابطه‌های از پیش تعریف شده شروع به کار می‌کند و سعی می‌کند الگوهای وقوع این مفاهیم را در متن یاد بگیرید. توصیف این سامانه از الگو به شکل‌های زیر انجام می‌شود:
   			•	الگوهای متنی که بر اساس برچسب اجزای سخن واژه‌ها تعریف می‌شوند. مثل: <<شهر الف>> و یا <<روابط تجاری میان الف و ب >>
   •	الگوهای متون ساخت یافته در قالب صفحات وب که بر اساس حروف تعریف می‌شوند و برای استخراج اطلاعات جدول‌ها و لیست‌ها طراحی شده‌اند. مثلا برای یک صفه خاص، الگوی(option) X (/option)  ممکن است لیستی از شهرها را استخراج کند.
   •	الگوهای تصریفی واژه‌ها که به صورت ویژگی به یک ابزار رده‌بند معرفی می‌شوند. برای نمونه پایان یافتن واژه با <<ایسم>> می‌تواند نشانگر یک مکتب فکری باشد.
   •	گزاره‌های شرطی که میان روابط برقرار هستند. این گزاره‌ها مستقیما از متن خارج نمی‌شوند و فقط برقرار بودن آن‌ها میان روابط بررسی می‌شود. مثلا << حضور یک بازیکن در جام جهانی>> به معنی <<بازیکن فوتبال>> بودن اوست.
*سازگاری میان اطلاعات استخراج شده*
در این سامانه همه‌ی اطلاعات به صورت یکپارچه‌ای فهمیده می‌شند، اگرچه از منابع مختلف استخراج شده باشند. سازگاری میان اطلاعات استخراج شده با این روش‌ها مورد بررسی قرار می‌گیرد:
   •	برقرار بودن رابطه انحصاری میان دو اطلاع به معنی نفی تعلق نمونه به هر دو رابطه است. مثلا نام شهر و نام ورزش رابطه‌ی انحصاری دارند، اما یک شهروند می‌تواند یک بازیکن فوتبال هم باشد. این روابط بخشی از ورودی‌های سامانه هستند و یادگرفتن آن‌ها مورد بحث نیست.
   •	آرگومان‌های یک رابطه معمولا نوع مشخصی دارند و این نوع قابل ارزیابی است. مثلا رابطه <<عضویت یک بازیکن در یک تیم>> دو آرگومان دارد که نوع هر دو مشخص است و امکان ندارد که یک شهر در یک تیم عضو باشد.
   •	وجود توافق میان ابزارهای رده‌بند نیز قابل بررسی است. مثلا وقتی این که الگوهای متنی و الگوهای مبتنی بر ساختار هر دو یک خروجی را تایید کنند، نشان دهنده صحت آن است.
این سامانه مجمعی از ابزارهای رده بند برای استخراج اطلاعات را به کار می‌گیرد و خروجی‌های آن یا مبتنی بر یک ابزار با اطمینان بالا و نتیجه‌ی اجماع چند ابزار با اطمینان پایین است. اگرچه شکل اجرا شده‌ی این سامانه با تعامل مختصر انسان، دقت اطلاعات را بهتر می‌کند[1].
**سامانه Snowball:**
از روش (DIPRE(Dual Iterative Pattern Expansionشروع می کنیم که به نوعی مبنی کار Snowball است. این روش را میتوان تقریبا بدیهی ترین شکل فرایند خود راه اندازی برای استخراج اطلاعات دانست. گفتیم که در این روش‌ها سامانه با تعداد داده‌ی ورودی آغاز به کار می‌کند، بنابراین DIPRE با جستجوی داده‌های ورودی سعی می‌کند، الگوی وقوع آن‌ها را کشف کند. برای این منظور، هر داده با ویژگی‌های << ترتیب وقوع آرگومان‌ها، آدرس وقوع، متن چپ، متن وسط و متن راست>> توصیف می‌شود. این توصیف امکان استخراج الگوهای مختلف را در آدرس‌های مختلف وب و با انطباق متن‌های اطراف آرگومان ها فراهم می‌کند.  همچنین  در این روش از یک عبارت با قاعده هم برای توصیف آرگومان‌ها استفاده می‌شود، تا از خطاهای واضح جلوگیری شود. سامانه Snowball هم تقریبا چنین عمکردی دارد و سعی کرده است این روش را بهتر انجام دهد. قواعد استخراج این سامانه با استفاده از تشخیص اسامی موجودیت‌ها تقویت شده‌است. تغییر دیگر افزودن احتمال وقوع به هرکدام از واژه‌های زمینه مربوط به قاعده است و برای محاسبه آن‌ها از تکرارهای مختلف نمونه‌ها استفاده می‌کند. حلقه‌ی تکرار این سامانه نیز مطابق دیگر نمونه‌های خود راه انداز، با جمع آوری داده‌ی مطمئن برای بهتر یادگرفتن الگو عمل می‌کند[6,2].
**استخراج اطلاعات با استفاده از یادگیری نیمه نظارتی دوگانه[^Coupled Semi-Supervised Learning for Information Extraction]**
یادگیری ماشین برای استخراج نوع‌ها و روابط از متن های ساخت یافته و غیرساخت یافته مفید و مناسب است. آموزش این روابط و نوع‌ها نیاز به نمونه‌های برچسب دار زیادی دارد که هزینه‌ی بدست ‌آوردن‌ آن‌‌ها زیاد است. در این مقاله برای آموزش از یادگیری نیمه نظارتی استفاده می‌کنیم به صورتی که از تعدادی نمونه‌ی برچسب دار و تعداد زیادی از اسناد بدون برچسب که از وب بدست آمده استفاده می‌کنیم که این ها  به عنوان ورودی در الگوریتم هایی که در ادامه معرفی می شوند  استفاده شده است . این مقاله چند راه را معرفی می‌کند که در آن‌ها آموزش نیمه نظارتی استخراج کننده نوع[^Categories extractors] و استخراج کننده رابطه[^Relations extractors] می‌تواند همراه هم استفاده شود[8].
به سه روش می توان آموزش استخراج کننده‌های نوع و رابطه را با هم به کاربرد[8]:
	1.روش اول محدودیت روی خروجی ها:
	اگر دو تابع fa : X → Ya  و fb : X → Yb را داشته باشیم و محدودیت روی ya و yb  را به ازای ورودی x بدانیم می توانیم fa و fb را طوری بدست آوریم که این محدودیت ها را ارضا کند.
	2.روش دوم محدودیت‌های ترکیبی:
ا	گر دو تابع f1 : X1 → Y1  و f2 : X1 ×  X2 → Y2 را داشته باشیم   ممکن است به ازای جفت y1 و y2  به ازای یک X1  و هر X2 ای محدودیتی وجود داشته باشد که با توجه به آن توانیم f1 و f2 را طوری بدست آوریم که این محدودیت ها را ارضا کند.
3.روش سوم Multi-view-agreement constraints:
اگر تابع f : X → Y   را داشته باشیم  و بتوانیم X را دو قسمت کنیم به نحوی که بتوانیم بنویسیم  <X = <X1 ,X2 و فرض کنیم هردوی آن‌ها Y را نتیجه بدهند  ما می تواینم f1 : X1 → Y و          f2 : X2 → Y را یادبگیریم.
در این مقاله تابع یاد می‌گیرد که نوع ها و روابط را استخراج کند و برای یادگیری از روش‌های زیر استفاده می‌کند[8]:
+ روش اول: انحصار متقابل 
+ روش دوم:Relation Argument type Checking
+ روش سوم : Unstructured and Semi-structured Text Features
در این مقاله برای یادگیری از الگوریتم های زیر استفاده شده است، که در آن‌‌ها فرض شده که مشکل لغات هم معنی و ابهام وجود ندارد:
+ Coupled Pattern Learner
![](http://upload7.ir/imgs/2014-12/02512804673940711402.png)
+ Coupled SEAL
![](http://upload7.ir/imgs/2014-12/10824822240753039590.png)

 


# آزمایش‌ها
همانطور که می دانیم در مسائل ساختن دسته بند[^classifier] که به صورت نیمه ناظر کار می کند دیتا ست از دو سری مجموعه نمونه تشکیل شده است:
1-مجموعه نمونه هایی که کلاس مربوط به آنها نیز مشخص می باشد یعنی در دیتا ست آمده که هر کدام از نمونه های مربوط به این مجموعه مربوط به کدام کلاس می باشد. 
2-مجموعه نمونه هایی که کلاس مربوط به آنها مشخص نمی باشد یعنی در دیتا ست موجود کلاس مربوط به هر کدام از نمونه های مربوط به این مجموعه مشخص نیست. 
در پیاده سازی با استفاده از نرم افزار متلب، این پروژه می تواند علاوه بر دیتا ست های نیمه ناظر می تواند با استفاده از تابع Make_Dataset از دیتا ست های کاملا با ناظر نیز استفاده کند.این تابع به این صورت عمل می کند که به عنوان ورودی آدرس دیتا ست با ناظر ، نسبت نمونه های تست به نمونه های یادگیری و نسبت نمونه های یادگیری بدون ناظر به نمونه های با ناظر را دریافت نموده و در خروجی به ما سه مجموع نمونه که برای تست و یادگیری و نمونه های یادگیری بدون کلاس مشخص شده ارائه میکند. که پیاده سازی این تابع در قسمت کدها موجود می‌باشد.
بعد از آماده سازی دیتاست کلاسیفایر ما توسط گام های زیر ساخته خواهد شد:
**1-ساخت دسته بند اولیه :**

برای ساخت دسته بند اولیه از تابع S3VMاستفاده می‌کنیم. روند ساختن دسته بند Semi-Supervise SVM ما به این صورت است که در ابتدا و با استفاده از مجموعه آموزش که از فراخوانی تابع Make_Dataset بدست آوردیم یا به صورت جداگانه داریم باید دسته بند اولیه SVM را بسازیم.باید توجه داشت که برای آموزش این دسته بند ما از معدود نمونه های با کلاس مشخص استفاده خواهیم کرد نه از کلیه نمونه های موجود در دیتاست اولیه. و چون در فرآیند ساخت دسته بند اولیه فقط تعداد محدودی از نمونه ها شرکت خواهند کرد بنابراین این امکان وجود دارد که دقت دسته بند تولید شده ما بسیار پایین باشد.

بعد از بدست آوردن دسته بند پایه به این صورت عمل می کنیم که در نمونه هایی که برای آموزش داریم اما کلاس آنها مشخص نمی باشد (Unlabled)به دسته بند ساخته شده از مرحله قبل خواهیم داد تا آنها را کلاسبندی کند.

**2-بروزرسانی دسته بند و بدست آوردن دسته بند نهایی :**

بعد از بدست آودرن برچسب کلاس تمامی نمونه های آموزشی و با استفاده از این برچسب ها به ترکیب دو دیتا ست Training و Unlabled می پردازیم . برای این کار مراحل زیر را انجام می دهیم:
1.دسته بند اولیه را می سازیم
2.برچسب کلاس تمامی نمونه های آموزشی را به استفاده از دسته بند اولیه بدست می آوریم
3.دیتا ست Unlabled را به انتهای Training اضافه می کنیم
4.بردار Unlables رابه انتهای بردار TrainLables اضافه میکنیم.
با استفاده از دیتا ست جدید بدست آمده یک دسته بند جدید می سازیم و با استفاده از آن دوباره برچسب کلاس تمامی نمونه های آموزشی که کلاس نا مشخص دارند را بدست می آوریم. باید در نظر داشت که چون دسته بند ما تغییر کرده لزوما جوابی که برای برچسب کلاس تمامی نمونه های آموزشی با کلاس نامشخص تولید می کند با دسته بند قبلی یکسان نسیت. 

باید توجه داشت که ما برای پایان دادن فاز آموزش نیاز به یک آستانه[^ Threshold] داریم که با استفاده از فرمول زیر آن را محاسبه می‌کنیم:

![توضیح تصویر](https://boute.s3.amazonaws.com/117-Untitled.png)**3-تست دسته بند ساخته شده :**
در این پروژه دسته بند اولیه دقت 0.5785را داشت ولی دسته بند نهایی به دقت 0.8667 رسیده است.
برای مشاهده کدها می توانید از لینکی که در قسمت پیوندهای مفید است استفاده کنید.
# کارهای آینده

# مراجع
[1] Carlson, Andrew, et al. "Toward an Architecture for Never-Ending Language Learning." AAAI. Vol. 5. 2010.
[2] Agichtein, Eugene, and Luis Gravano. "Snowball: Extracting relations from large plain-text collections." Proceedings of the fifth ACM conference on Digital libraries. ACM, 2000.
[3] Zhu, Jun, et al. "StatSnowball: a statistical approach to extracting entity relationships." Proceedings of the 18th international conference on World wide web. ACM, 2009.
[4] Xiaojin Zhu and Andrew B. Goldberg. Introduction to Semi-Supervised Learning. Morgan & Claypool, 2009.
[5]Oliver Chapell،  Bernhard Schölkopf and Alexander Zien. Semi-Supervised Learning. Massachusetts Institute of Technology2006
[6] Sergey Brin. Extracting Patterns and Relations from the World Wide Web. In WebDB Workshopat 6th International Conference on Extending Database Technology, pages 172–183, 1998.
[7] X. Zhu. Semi-supervised learning literature survey. Technical Report 1530, Department of Computer Sciences, University of Wisconsin, Madison, 2005.
[8] Andrew Carlson, Justin Betteridge, Richard C. Wang, Estevam R. Hruschka Jr, Tom M. Mitchell. Coupled Semi-Supervised Learning for Information Extraction, 2010
[9] J. Hoffart, F. M. Suchanek, K. Berberich, and G. Weikum, “YAGO2: A spatially and temporally enhanced knowledge base from Wikipedia,” Artif. Intell., vol. 194, pp. 28–61, Jan. 2013. 
[10]S. Auer, C. Bizer, G. Kobilarov, and J. Lehmann, “Dbpedia: A nucleus for a web of open data,” Semant. Web, 2007. 
[11] F. Peng and A. Mccallum, “Accurate Information Extraction from Research Papers using 
Conditional Random Fields,” 2003. 
[12] D. Zelenko, C. Aone, and A. Richardella, “Kernel methods for relation extraction,” J. Mach. Learn. …, vol. 3, pp. 1083–1106, 2003. 
[13] Li Cunhe,Wu Chenggang. “A New Semi-Supervised Support Vector Machine Learning Algorithm Based on Active Learning” 2010 2nd International Conference on Future Computer and Communication V 3 Pages 638-641







# پیوندهای مفید
+ [علیرضا نوریان، "استخراج آزاد اطلاعات"، سمینار کارشناسی ارشد، دانشگاه علم و صنعت ایران، تهران، ۱۳۹۱.](https://dl.dropboxusercontent.com/u/90405495/seminar.pdf)
+ [پایگاه دانشی که به روش نیمه‌نظارتی ساخته شده](http://rtw.ml.cmu.edu)
+ [لینک پروژه در گیت هاب](https://github.com/hamid227/codes.git)