بازیابی پاسخ

تغییرات
ارزیابی شرح مسئله و کارهای مرتبط

بسم الله الرحمن الرحیم

۱. مقدمه

امروزه فضای وب امکانات زیادی را برای یافتن پاسخ پرسش های گوناگون کاربران در زمینه های مختلف فراهم کرده . یکی از روش های کارآمد و پرطرفدار ، استفاده از سایت های پرسش و پاسخ است ؛ بدین صورت که کاربر سوال موردنظر خود را مطرح کرده و بقیه افراد می توانند به آن پاسخ دهند . همچنین کاربر می تواند جواب سوال خود را از میان سوال و جواب هایی که در گذشته مطرح شده اند به دست بیاورد .از نمونه‌های بسیار موفق این نوع سایت‌ها stack overflow می‌باشد.

سایت های پرسش و پاسخ

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

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

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

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

در تمام روش هایی که در زیر به آنها اشاره شده است ، بایستی ابتدا سوال کاربر و همچنین مجموعه سوال ها و پاسخ ها به صورت قابل استفاده ای ذخیره شوند ؛ بدین منظور ابتدا هر سوال یا جواب را به صورت مجموعه ای از کلمات در می آوریم و سپس کلمات توقف (stop word) را از بین آنها حذف کرده و با استفاده از تابع porter stemmer به جای هر کلمه ، ریشه ی آن را قرار می دهیم . در نتیجه به ازای هر سوال مطرح شده از طرف کاربر و همچنین هر سوال یا جواب در پایگاه داده ، مجموعه ای از ریشه های کلمات موجود در آنها را در اختیار داریم .

امروزه متداول ترین روش هایی که برای بازیابی پاسخ ( Q&A retrieval) وجود دارد ، براساس bag-of-words) BOW) می باشد . BOW مدل ساده ای است که در پردازش زبان های طبیعی و بازیابی اطلاعات به کار می رود . در این مدل به متن به صورت کیسه ای پر از کلمات نگاه می شود ، بدون توجه به دستور زبان و یا ترتیب کلمات ، اما تعداد دفعات تکرار هر کلمه ( فرکانس ) حائز اهمیت است .
از جمله مدل های از جنس BOW که در مساله بازیابی پاسخ به کار می روند دو مدل مختلف بازیابی از طریق وزن دهی الفاظ ، tf-idf و BM25 می باشند که در ادامه به اختصار توضیح داده خواهند شد .

  • روش term frequency-inverse document frequency) Tf-idf)

در این روش ، Tf-idf در واقع یک آمار عددی است که نشان می دهد هر کلمه موجود در یک سند ، در میان مجموعه ای از اسناد چه قدر اهمیت دارد . این مقدار معمولا به عنوان فاکتور وزنی در بازیابی اطلاعات به کار می رود .

مقدارtf در ساده ترین حالت نشان دهنده ی فرکانس خام یک کلمه(t) در یک سند(d) است (تعداد دفعات رخداد کلمه در سند ).

tf(t,d)=0.5+\frac { 0.5\quad \times \quad f(t,d) }{ max\{ f(w,d)\quad :\quad w\in d\} }

مقدار idf نیز نشان دهنده این است که چه مقدار اطلاعات درباره یک سند(D) ،توسط یک کلمه فراهم می شود یعنی کلمه در سند بارها تکرار شده یا به ندرت .(N تعداد اسناد را نشان می دهد .)

idf(t,D)=\log { \frac { N }{ \left| d\in D\quad :\quad t\in d \right| } }

حاصلضرب این دو مقدار معیاری فراهم می کند که میزان اهمیت یک کلمه (وزن هر کلمه) را مشخص می کند .

tfidf(t,d,D)=tf(t,d)\times idf(t,D)

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

  • روش Best Match) BM25)

روش BM25 یک نیز الگوی وزنی است که در واقع از همان tf-idf مشتق شده و فقط فرمول متفاوتی دارد ، روند کلی حل مساله همانند روش قبلی است . فرمول آن برای امتیاز یک کلمه در یک سند صورت زیر است .

score(D,Q)=\sum _{ i=1 }^{ n }{ idf({ q }_{ i })\cdot \frac { f({ q }_{ i },D)\cdot ({ k }_{ 1 }+1) }{ f({ q }_{ i },D)\quad +\quad { k }_{ 1 }.(1-b+b.\frac { \left| D \right| }{ avgdl } ) } }

در اکثر موارد (بدون بهینه سازی های خاص):

b=0.75

{ k }_{ 1 }\in \left\{ 1.2,2 \right\}

  • روش دیگری که برای بازیابی پاسخ بررسی شده [3] شبیه روش های BOW می باشد اما تا حدودی بهبود یافته تر می باشد . در این روش ابتدا هر سوال (چه کوئری چه سوال های موجود در پایگاه داده ) تحلیل می شود به طوری که سه مساله در مورد آن مشخص شود :
    نوع جواب : مکان ، تاریخ و ...
    تمرکز سوال : کلمه ای که معمولا در نزدیکی لفظ استفهامی (چرا ، چگونه و ...) قرار می گیرد .
    موجودیت های نامدار : نام مکان ها ، افراد و ...
    پس از مشخص کردن این سه مورد درباره ی هر سوال نوبت به بازیابی اطلاعات (پاسخ) می رسد . در این مرحله برای هر سوال موجود در آرشیو یک امتیاز محاسبه می شود (با در نظر گرفتن مشخصات سوال مطرح شده و سوال آرشیو شده) . این امتیاز (فاکتور وزنی) با اختصاص یک ضریب به هر یک از سه مشخصه ،با توجه به میزان اهمیت هر کدام ، محاسبه می شود . ضریب 2 برای موجودیت های نامدار و ضریب 1 برای تمرکز و نوع .

در سه روش ای که در بالا به آنها اشاره شد ، به هر کلمه به صورت جداگانه نگاه می شود . از آنجایی که کاربران اکثرا سوال های کوتاهی مطرح می کنند ، تعداد کمی کلمه برای پیدا کردن سوال مناسب در اختیار سیستم قرار می گیرد که باعث می شود در اکثر موارد جواب های کافی و درست ارائه نشوند . توسط این مدل ها رخداد همزمان کلمات (word co-occurance) ( یعنی دو یا چند کلمه که معنای یکسانی دارند اما از لحاظ ظاهری متفاوتند ) یا زمینه اطلاعاتی به اشتراک گذاشته شده (context shared info) مناسبی برای اندازه گیری تشابه به صورت کارامد ارائه نمی شود . به همین دلیل برای بازیابی پاسخ مناسب نیستند .برای حل این محدودیت ها از مدل های ترجمه (translation model) استفاده می شود تا ارتباطات معنایی کلمات و عبارات به دست بیاید . در زیر توضیح مختصری از برخی از این نوع روش ها داده می شود .

  • در یکی از روش ها [4] ، از ویکی پدیا (wikipedia) به عنوان مجموعه دانش جهانی برای حل مساله بازیابی پاسخ استفاده می شود . به دلیل ویژگی هایی از قبیل : پوشش دادن مفاهیم به طور گسترده ، اطلاعات معنایی غنی و مضامین به روز . آنچه در این روش بررسی می شود فقط تشابه سوال کاربر به سوالهای آرشیو است و در مورد پاسخ ها کاری انجام نمی شود .

این روش دو مرحله اصلی دارد :

  1. ساختن یک مجموعه اطلاعاتی بر پایه ی روابط معنایی استخراج شده از ویکی پدیا :
    در این مرحله مجموعه ی اطلاعاتی قابل استفاده و ساده ای ساخته می شود که ارتباط مفاهیم ، بر پایه دانش ساختاری ویکی پدیا از طریق آن به دست میاد . مواردی از جمله ترادف(synonymy) ، تعدد معانی (polysemy) ،اشتقاق (hypernymy) و شرکت پذیری (associative relation) در این مجموعه لحاظ می شوند . یعنی این مجموعه به ازای هر کلمه ، تعدادی کلمه مرتبط را در نظر می گیرد (به جای اینکه فقط همان کلمه معیار پیدا کردن سوال های کاندیدا باشد) .
    به عنوان مثال :
    کلمه ی به کار رفته در کوئری :"big"
    کلمات مرتبط به کار رفته در سوالها : "large , size ,huge "

2 . استفاده مفید از مجموعه ساخته شده برای بازیابی پاسخ
در این مرحله بایستی سوال کاربر و همچنین مجموعه سوال ها و پاسخ ها به صورت قابل استفاده ذخیره شوند تا به ازای هر سوال ، ریشه های کلمات آن را در اختیار داشته باشیم (در ابتدای روش ها توضیح داده شد).

برای به دست آوردن امتیاز نهایی برای هر سوال از پیش مطرح شده (d) برای سوال کاربر (q) از فرمول زیر استفاده می کنیم:

Score(q,d)=\alpha { S }_{ cate }(q,d)+\beta { S }_{ sac }(q,d)+\gamma { S }_{ term }(q,d)

\alpha +\beta +\gamma =1

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

برای به دست آوردن{ S }_{ term }(q,d) با استفاده از روش tf-idf به ازای هر کوئری و هر سوال موجود در آرشیو یک بردار درست می کنیم و با تابع زیر که معیاری برای اندازه گیری شباهت دو بردار است ، مقادیر را به ازای هر کوئری و هر سوال به دست می آوریم :

{ S }_{ term }(q,d)=\frac { \left< q,d \right> }{ { \left\| q \right\| }^{ 2 }.{ \left\| d \right\| }^{ 2 } }

حال بایستی کلمات استخراج شده از سوال ها به مفاهیم ویکی نگاشت شوند . برای این کار بایستی فهرستی بسازیم که شامل عبارات مفاهیم ویکی پدیا ، مترادف ها و ... موجود در مجموعه اطلاعاتی ویکی باشد . بر اساس این فهرست عبارات ساخته شده ، عبارات کاندیدا می توانند از صفحه وب به دست بیایند.

برای محاسبه { S }_{ cate }(q,d) بایستی این مساله را درنظر بگیریم که مجموعه اطلاعاتی ساخته شده از روی ویکی پدیا به صورت یک گراف غیر حلقه ای است که هر مفهوم موردنظر ما به یک یا چند سطح از این گراف مربوط می شود ، یعنی ممکن است در چند سطح مفاهیم مرتبط با آن موجود باشند .(سطوح پایین تر که به مفهوم موردنظر نزدیک ترند ، موثرتر می باشند .) هر مفهوم مرتبط به مفهوم c به صورت { cate}_{ c}(q,d) مشخص می شود .

\begin{matrix} { S }_{ cate }(q,d)=\frac { \left< { Cate }_{ q },{ Cate }_{ d } \right> }{ { \left\| { Cate }_{ q } \right\| }^{ 2 }.{ \left\| { Cate }_{ d } \right\| }^{ 2 } } \end{matrix}

برای قسمت آخر نیز بایستی { S }_{ sac}(q,d) محاسبه شود . که مربوط به مترادف ها و مفاهیم شرکت پذیر می باشد که کمک می کنند تا مفاهیم مرتبط بیشتری شامل شوند (بر پراکندگی داده غلبه می شود ) .

\begin{matrix} { S }_{ sac }(q,d)=\frac { \left< { Sac }_{ q },{ Sac }_{ d } \right> }{ { \left\| { Sac }_{ q } \right\| }^{ 2 }.{ \left\| { Sac }_{ d } \right\| }^{ 2 } } \end{matrix}

  • روش دیگری که در این زمینه بررسی شده است [1] و [2] ، به شرح زیر است .در این روش با استفاده از مجموعه داده ای (dataset) که شامل جفت های سوال و جواب می باشد ، سه مجموعه از کلمات به صورت زیر ایجاد می شود :

    Q=\{ (q_{ 1 },{ a }_{ 1 }),({ q }_{ 2 },{ a }_{ 2 }),...\}

    Q=\{ q_{ 1\quad },{ q }_{ 2\quad },...\}

    A=\{ a_{ 1\quad },{ a }_{ 2\quad },...\}

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

توجه : (به دلیل پیچیده بودن فرمول ها و نیاز به توضیح در مورد عناصر به کار رفته در آنها ، از آوردنشان در بخش های بعدی خودداری می کنیم . در صورت تمایل به مقاله [1] یا [2] مراجعه کنید ).

برای بخش سوال : از ترکیب IBM Model 1 و مدل زبانی احتمالات کوئری(query liklihood language model) ، استفاده شده و فرمولی بهینه به دست می آید.

برای بخش جواب : از مدل زبانی احتمالات کوئری استفاده می شود .

مورد دیگری که در این مقاله روی آن کار شده است ، یادگیری احتمالات ترجمه کلمه به کلمه است . یعنی سوال را به عنوان یک زبان و جواب را به عنوان یک زبان دیگر در نظر گرفته و سعی می شود ترجمه ای از طرف سوال در طرف جواب پیدا شود و یادگیری صورت بگیرد . به عنوان مثال زمانی که در طرف سوال کلمه ی "Everst" می آید در طرف دیگر (به عنوان ترجمه ) می توان احتمال مشاهده ی کلمات "highest" ، "mountain " و یا ... را داشت .

۳. آزمایش و نتایج

در فازهای بعدی تکمیل خواهد شد

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

در فازهای بعدی تکمیل خواهد شد

۵. مراجع

  1. Jeon, Jiwoon. Searching question and answer archives. ProQuest, 2007.

  2. Xue, Xiaobing, Jiwoon Jeon, and W. Bruce Croft. "Retrieval models for question and answer archives." Proceedings of the 31st annual international ACM SIGIR conference on Research and development in information retrieval. ACM, 2008.

  3. Rodrigo, Álvaro, et al. "A Question Answering System based on Information Retrieval and Validation." CLEF (Notebook Papers/LABs/Workshops). 2010.

  4. Guangyou Zhou, Yang Liu, Fang Liu, Daojian Zeng, and Jun Zhao. "Improving Question Retrieval in Community Question Answering Using World Knowledge."Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence

۶. لینک‌های مفید

محسن ایمانی

شما هدف از این فاز را که شرح مسئله و همچنین بررسی کارهای مرتبط برای حل این مسئله بود را به خوبی محقق نموده‌اید.
اما نکته‌ای که بهتر بود بیشتر به ان توجه کنید. قرار دادن ارجاع‌ها برای هرکدام از کارهای مرتبط می‌باشد به نحوی که خواننده برای مطالعه بیشتر هر کدام از این روش‌ها بتواند به مرجع مربوطه رجوع داشته باشد.