نويز در داده كاوي

نويز و نحوه رويکرد با آن در داده کاوي

دانشجوي کارشناسي ارشد

رشته مهندسي کامپيوتر-هوش مصنوعي

دانشگاه صنعتي امير کبير(پلي تکنيک تهران)

 

چکيده

در اين تحقيق ايده اي براي داده کاوي در مورد پايگاه‌هاي داده نويزي که ممکن است توسط
سيستم‌هاي آموزش ماشين ساخته شده باشد توضيح داده مي شود. همچنين روشهايي براي تخمين توزيع احتمال پيوسته بدون نويز در حالتي که نويز مشاهده مي شود. و همچنين احتمال شرطي ، که مي تواند با استفاده از نمونه‌هاي آماري و آناليز خطا تخمين زده شود بررسي مي شود  و همچنين آزمايشات مختلفي براي تست اين ايده‌ها ارائه شده است توضيح داده مي شود.

در قسمت بعد الگوريتمهايي براي آموزش نويزي از جمله الگوريتم PAC ارائه مي گردد و در مورد توسعه آن نيز بحث مي شود که تحت دو الگوريتم يادگيري ضعيف و قوي که قابل تعميم به يکديگر هستند مورد بررسي قرار مي گيرد.

در نهايت کاربردي از داده کاوي در محيط نويزي از جمله روشهايي داده کاوي در محيطهای نويزی برای از بين بردن نويز در صفحات وب بحث مي گردد.

1- مقدمه

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

در اکثر اين روشها فرض بر اين است که پايگاه داده‌هاي موجود در ابعاد مناسب مي باشد و نسبتاً بدون نويز مي باشد. يعني شرايط ايده آل براي داده کاوي کاملاً مهيا مي باشد البته گاهي اوقات که داده‌ها داراي نويز مي بود پاکسازي داده‌ها نيز براي حذف يا تصحيح بخشهاي نسبتاً کوچکي از اطلاعات که داراي مقادير اشتباه مي باشد يا داده‌هايي که داراي تناقض هستند بکار مي رفت. بعبارت ديگر در برخورد با داده‌هاي خطا و يا ناقص آن داده‌ها حذف مي گرديد و آموزش با بعقيه داده‌هاي موجود بکار گرفته مي شد که البته اين روش مناسب نيست زيرا ممکن است داده‌هاي حذف شده داده‌هاي مهمي باشد و تاثير زيادي در آموزش صحيح داشته باشد يا اينکه حتي داده‌هاي باقيمانده در اثر حذف داده‌هاي اشتباه به قدر کافي براي آموزش مناسب نباشد. البته مشکل بزرگتر آن است که برخي پايگاه‌هاي داده شامل داده‌هايي مي باشد که به صورت ذاتي داراي نويز مي باشد و قابل پاکسازي نمي باشد که يک مثال خوب از اين مفاهيم ، پايگاه دادههايي است که توسط يکي (يا بيشتر) از الگوريتمهاي يادگيري ماشين ساخته شده است. بنابراين بسيار مهم است که بتوان تاثير نويز بر داده کاوي را درک کرد و آموزش را بر مبناي داده‌هاي اشتباه نيز به نحو صحيح انجام داد.

بسياري از ايده‌هاي موجود در مورد داده کاوي بر مبناي اعمال تکنيک‌هاي بدون ناظر آموزش به داده‌هاي خيلي بزرگ براي کشف دانش ، الگوها و قوانين مي باشد.

مشکل عمومي يادگيري بدون ناظر استنتاج و يا حدس زدن جزئيات توزيع احتمال پيوسته
مي باشد .

متغير تصادفي X و نمونه‌هاي حاصل از N مشاهده در نظر گرفته مي شود () و با توجه به اين تعريف ، هدف آموزشهاي بدون نظارت بصورت تعريف جزئيات مفيد چگالي پيوسته P(x) تعريف مي شود.

در اين بخش ارتباط بين توزيع احتمال پيوسته که از خروجي پردازش نويزي بدست آمده در مقابل توزيع در محيطهاي عاري از نويز بررسي مي شود. بنابراين اميد است که بتوان ايده‌هاي عمومي و همچنين يکسري
محدوديت‌ها را براي حصول دانش از داده‌هاي نويزي بدست آورد و اهميت اصلي بر روي داده‌هاي نويزي بدست آمده از الگوريتمهاي يادگيري مي باشد.

2- مدلها و ايده‌ها

هدف پيدا کردن يک رابطه کلي بين توزيع احتمال متغيرهاي پايگاه داده بدست آمده از داده‌هاي نويزي در مقايسه با حالتي است که داده‌ها به صورت مقادير صحيح و بدون نويز وجود دارد. در اين ايده يک مجموعه از داده‌هاي اصلي و واقعي تحت عنوان يک بردار تصادفي X که از توزيع احتمال D مشتق شده است تعريف مي گردد ، همچنين يک تابع تعريف مي گردد که اين تابع در واقع بردار تصادفي را به يک مفهوم بهتر که نشان دهنده داده‌ها به صورت صحيح مي باشد مي نگارد :  در واقع با اين کار يک حالتي از داده‌ها که به صورت فرضي فاقد نويز در نظر گرفته مي شود تعريف مي گردد .

همچنين يک تابع ديگر نيز تعريف مي گردد.  و  دو جداسازي متفاوت از مقدار نويز در سيستم مي باشد. البته  در واقع يک تخمين از تابع هدف  در نظر گرفته مي شود يا به عبارت کلي اين مطلب را مي توان بدين صورت مطرح کرد که  تابعي است که مي تواند طي پردازشي خاص مقدار معيني نويز به سيستم اضافه نمايد ( يعني  ).

2-1- حالت عمومي

در حالت عمومي يک ترکيب عطفي از متغيرهاي که به صورت تصادفي ايجاد شده اند در نظر گرفته مي شود که به صورت  نشان داده مي شود . اين رابطه براي داده‌هاي نويزي نيز به صورت قابل تعريف است که در واقع در اين رابطهp  يک تبديل ساده براي ايجاد داده‌هاي نويزي مي باشد.

و با استفاده از تئوري مجموع احتماات به رابطه زير مي رسيم :

(رابطه 1)

که براي اين رابطه مي باشد.

با توجه به مطالب گفته شده هدف تخمين احتمال شرطي بر مبناي داده‌هاي نمونه از پايگاه داده با استفاده از يک روش آماري مناسب مي باشد ( يعني استفاده از يکي از روشهاي bootstrap يا    cross-alidation يا غيره). به عنوان مثال اگر پايگاه داده‌ها از الگوريتم‌هاي يادگيري ماشين نتيجه شده باشد اين کميتها با استفاده از يک الگوريتم cross-alidation بر روي داده‌هاي آموزشي تخمين زده مي شود. طبق تعريف داده‌هاي آموزشي از تعدادي نمونه‌هاي درستC  حاصل مي آيد. در قسمت بعد مي توان جدول احتمال براي نمايش فرکانس (تعداد تکرار)  نسبي  و  به ازاي هر تبديل P ساخت که اين جدول با مقايسه خروجي الگوريتم‌هاي يادگيري برروي داده‌هاي آموزشي حاصل مي شود.

با ميانگين گيري از نتايج حاصل ازجدول فرکانس که از هر يک از نمونه‌هاي آموزشي تست ايجاد شده است يک تخمين براي احتمال شرطي بدست مي آيد :

(رابطه 2)

همچنين احتمال پيوسته نيز به صورت مستقل از پايگاه داده به صورت زير نشان داده مي شود:

(رابطه 3)

بنابراين مي توان يک تخمين براي  به شکل کميت‌هاي نمونه‌ها استنتاج کرد :

(رابطه 4)

چون اين تخمين از يکسري از داده‌هاي محدود بدست آمده است بنابراين احتمال خطا وجود دارد بنابراين بهتر است با يک روش استاندارد مناسب خطا محاسبه شود بنابراين واريانس  براي احتمال تخمين زده شده به صورت زير محاسبه مي گردد:

(رابطه 5)

که در اين رابطه  و  به ترتيب واريانس نمونه‌هاي نمايش داده شده در   و  مي باشد.

آناليزهاي انجام شده در بالا داراي يک محدوده خاص از مقادير مي باشند که باعث مي شود بتوان يک تخمين دقيق از احتمال شرطي را داشت که اين امر مي تواند باعث بروز مشکل گردد زيرا نياز به وجود نمونه‌هاي مناسب قابل مشاهده هم براي داده‌هاي نويزي و هم داده‌هاي صحيح مي باشد که البته داه‌هاي نويزي نيز بايد به خوبي داده‌هاي صحيح باشد . بنابراين بايد يک تعداد مناسبي نمونه که بتواند دقت قابل قبولي را ارائه دهد انتخاب کرد .

با استفاده ار تئوري يادگيري محاسباتي مي توان يک حد بالا براي تعداد نمونه‌ها محاسبه کرد که اين حد مقداري است که اگر ارضا شود مي توان به يک دقت خوب دست يافت . با فرض آنکه هريک از مثالهاي آموزشي مي تواند بعنوان يک دنباله برنولي مستقل در نظر گرفته شود مي توان يک محدوده چرنف براي احتمال ثبت کرد که از اختلاف تخمين  و احتمال شرطي صحيح  بوسيله يک مقدار ثابت حاصل مي آيد :

(رابطه 6)

که در اين رابطه m برابر تعداد مثالهايي است که براي تخمين  مورد استفاده قرار
مي گيرد. به دليل اينکه مجموع تعداد تبديلها ( جايگشتها ) از طريق  بدست
مي آيد احتمال اينکه اختلاف هر يک از تخمينها با مقدار صحيح بيشتر از مقدار  باشد از رابطه زير محاسبه
مي شود:

(رابطه 7)

بنابراين تعداد نمونه‌هايي که لازم است تا بتوان مقدار را به طور ثابت نگاه داشت محدود
مي شود با :

(رابطه 8)

و در حالتي که متغير‌ها باينري به صورت  وجود دارد رابطه زير تعريف مي شود :

(رابطه 9)

بنابراين تعداد مثالهاي آموزشي به صورت خطي با تعداد متغيرها در قوانين ربطي رشد مي کند. به عنوان مثال اگر احتمال 95% باشد و دقت هر تخمين شرطي 1/0 باشد آنگاه داريم:

و بنابراين براي N‌هاي کوچک دست کم يکصد تا دويست مثال آموزشي لازم است.

مثال 1 : در يک مثال ساده يک حالت باينري براي بصورت  در نظر گرفته مي شود و تحت تبديل نويز خطي  متغير  حاصل مي آيد. در اين حالت X يک مجموعه بزرگ از داده‌هاي پايگاه داده D مي باشد. در اين حالت پايگاه دادهD  به دو مجموعه گسسته  تقسيم مي شود که اشتراک اين دو مجموعه تهي مي باشد. مجموعه بعنوان مجموعه تست / آموزش بکار گرفته مي شود و بايد مقادير صحيح  با استفاده از يک پردازش قابل اطمينان برچسب گزاري گردد. مجموعه هم شامل باقيمانده پايگاه داده که برچسب گزاري نشده است مي باشد. در اين حالت رابطه (1) به صورت زير نمايش داده مي شود:

(رابطه 10)

احتمال شرطي در طول فاز آموزش با ارزيابي کارايي آموزش دهنده بر روي مجموعه تست با مقايسه تناسب بين  تخمين زده مي شود. جدول فرکانس براي خروجيهاي ممکن در جدول زير نشان داده مي شود:

جدول 1 . جدول احتمال

سپس مي توان احتمال شرطي تخميني را از فرکانس مشاهده شده محاسبه کرد :

(رابطه 11)

با استفاده از روال cross-validation مي توان توانايي نمونه‌ها و خطاي استاندارد را براي
کميت‌هاي توضيح داده شده در بالا تخمين زد. احتمال‌هاي  را مي توان با استفاده از آموزش دهنده اي با تعداد زيادي مثالهاي برچسب گزاري نشده و مشاهده فرکانس دقت براي مقادير  تخمين زد.

در حالت کلي مجموعه نمونه‌هايي که براي آموزش و تست استفاده مي شود خيلي کمتر از تعداد نمونه‌هايي است که  برچسب گزاري نشده است يعني . بنابراين مي توان يک خطاي آماري را براي تخمين احتمال شرطي فرض کرد که با توجه به رابطه (5) براي  به صورت زير تعريف مي شود:

(رابطه 12)

مثال 2 :  در اين حالت دو متغير تصادفي باينري  Aو B و بخشهاي نويزي آن در نظر گرفته
مي شود ، در اين حالت توزيع احتمال پيوسته ( بصورت صحيح ) بصورت کميت‌هاي قابل مشاهده نوشته مي شود:

شکل پيشرفت در اين مثال بسيار شبيه به مثال قبل مي باشد. در اين حالت احتمال شرطي با ارزيابي کارايي آموزش دهنده بر روي نمونه‌هاي تست و استفاده از جدول وابستگي پيچيده تخمين زده مي شود. تخمين‌هاي و غيره با استفاده از تعليم دهنده بر روي پايگاه داده اي که به صورت کامل شامل نمونه‌هاي برچسب گزاري نشده است حاصل مي آيد. مقدار  با توجه به رابطه (4) و ميزان تخمين خطا نيز با استفاده از ساختار (5) تعيين مي گردد.

3- آزمايش

در اين بخش توضيحاتي راجع به آزمايشاتي که بر روي داده‌ها براي تعيين قابل اجرا بودن و همچنين کارايي ايده‌هاي بيان شده ، ارائه شده است و نتايج بررسي شده است. در اين عمل و آزمايش با دو نمونه داده شبيه سازي شده ، به ترتيب با يک و دو متغير تصادفي ، بررسي انجام مي شود .

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

3-1- يک متغير : در اولين آزمايش اثر نويز بر روي توزيع احتمال متغير‌هاي تصادفي باينري ساده بررسي مي شود. براي توليد داده‌هاي شبيه سازي شده تکنيک مونت کارلو(Monte Carlo) روي مدلهاي احتمال اعمال مي شود. ابتدا هر نمونه از متغيرهاي تصادفي C مطابق با مدل برنولي ساخته مي شود:

سپس نويز مطابق با توزيع احتمال ، به هر يک از نمونه‌ها اعمال مي گردد:

که در اين رابطه  احتمال اين که نمونه‌هاي مثبت با گرفتن ضربه اي به نمونه منفي تبديل گردد مي باشد و  احتمال اينکه نمونه‌هاي منفي با گرفتن ضربه اي به نمونه‌هاي مثبت تبديل گردد مي باشد.

در طول فاز آموزش نمونه‌ها توليد مي شود و نمونه‌هاي در مقابل  مقايسه مي شود تا بتوان جدول وابستگي را توليدکرد. چندين اجراي آزمايش براي شبيه سازي پردازشcross-validation اعمال مي شود . براي تخمين احتمال شرطي نيز از رابطه (11) استفاده مي شود.

در طول فاز تخمين از مدل بالا براي توليد نمونه‌ها استفاده مي شود. براي اين داده‌ها فرکانس  براي مشخص کردن تخمين  و  نشان داده مي شود. تخمين نهايي  بوسيله
رابطه‌هاي (10) و (12) محاسبه مي شود.

در اينجا مقادير مختلفي به  اعمال مي شود و ميزان  اختلاف بين احتمال صحيح ، احتمال مشاهده شده ، و احتمال تخميني مقايسه مي شود.

نتايج کلي در شکل 1 نشان داده شده است که در اين نمايش  مي باشد . پنجاه نمونه آموزشي در طول مجموع پنچ آزمايش مستقل توليد شده است. براي فاز تخمين5000 نمونه توليد مي شود. همانطور که در شکل مشاهده مي شود با توجه به مدل (10) مي توان يک تخمين دقيقي از احتمال صحيح در طول يک گستره وسيع از نرخ خطا بدست آورد .

شکل1 . تخمين احتمال براي  (با  ساخته شده است) و  (با  ساخته شده است) بصورت تابعي از نرخ خطا . احتمال صحيح  با نقطه چين نشان داده شده است.

 

3-1- دو متغير : در آزمايش دوم اثر نويز بر توزيع احتمال پيوسته براي دو متغير تصادفي باينري وابسته A و B بررسي مي شود. در اينجا نيز دوباره از تکنيک مونت کارلو با مدل احتمال ساده استفاده مي شود که A مطابق زير توليد مي شود:

و B با استفاده از روابط زير توليد مي شود:

که در اين روابط پارامتر  درجه وابستگي مي باشد. اگر  باشد B با توزيع  کاملاً مستقل از A مي باشد. اگر  باشد آنگاه B کاملاً وابسته به A مي باشد. و اگر  باشد بصورت افزايشي ميزان وابستگي A افزايش مي يابد و احتمال پيوسته صحيح بدين صورت بدست مي آيد

ميزان خطاي وارد به سيستم  مطابق احتمال شرطي بصورت زير است

و

اين آزمايش شبيه به مطالب گفته شده در حالت يک متغير مي باشد . احتمال پيوسته صحيح با استفاده از رابطه (13) تخمين زده مي شود و نتايج شامل مقادير مختلفي از  مي باشد .

نتايج کلي در شکل 2 نشان داده شده است که در اين نمايش  مي باشد. پنجاه نمونه آموزشي در طول پنج آزمايش مختلف توليد شده است و براي فاز تخمين مانند قسمت آخر بخش قبل 5000 نمونه توليد شده است.

شکل 2. تخمين احتمال براي  (با  ساخته شده است) و  (با  ساخته شده است) بصورت تابعي از نرخ خطا . احتمال صحيح  با نقطه چين نشان داده شده است.

 

3-3- داده‌هاي دنياي واقعي : در اين آزمايش داده‌هاي نويزي با استفاده از الگوريتم يادگيري درخت تصميم C4.5 ايجاد مي شود. براي داده‌هاي خام از پايگاه داده adult و شامل 48842 نمونه از داده‌ها مي باشد که مربوط به اطلاعات آماري مربوط به درآمد‌هاي مربوط به هر شخص مي باشد ، استفاده مي شود. کل اين داده‌ها به دو مجموعه 32561 نمونه برچسب گزاري نشده براي فاز تخمين و 16281 نمونه برچسب گزاري شده براي آموزش و تست تقسيم مي شود. همچنين 16281 نمونه برچسب گزاري شده در آينده به سه بخش طبق cross-validation  تقسيم مي شود.

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

که در اين رابطه‌ها متغير A ، سطح بيشترين آموزش دست يافته شده مي باشد و B سطح درآمد را براي هر شخص نشان مي دهد.  هدف تخمين توزيع احتمال پيوسته  براي هر زوج  مي باشد .

در هر مرحله از روال cross-validation  10854 نمونه آموزشي براي تعليم آموزش دهنده درخت تصميم “A-Type” و “B-Type” ، و 5427 نمونه تست براي تخمين دقت طبقه بندي و احتمال شرطي ( يعني همان  ) مورد استفاده قرار مي گيرد. براي آموزش دهنده “A-Type” نرخ خطاي طبقه بندي حدود 50% و براي آموزش دهنده “B-Type” در حدود 16% مي باشد.

در طول روال تخمين دو نوع درخت تصميم براي طبقه بندي 32651 نمونه‌ها ي باقيمانده جهت توليد تخمين احتمال پيوسته براي مشاهدات نويزي  مورد استفاده قرار مي گيرد. با استفاده از رابطه‌هاي (4) و (5) مقادير براي هر يک از 10 زوج ممکن  ( در جدول 2 توضيح داده شده )  تخمين زده مي شود.

جدول 2. نتايج C4.5.

در شکل 3 احتمالات پيوسته مختلف اندازه گيري شده به ازاي هر زوج در آزمايش نشان داده شده است. در بيشتر حالات مقدار محاسبه شده براي  سازش بهتري با مقادير اصلي نسبت به مقادير مشاهده شده  دارا مي باشد.

شکل 3. نتايج ساخت داده‌ها با استفاده از درخت تصميم.

 

در جدول 2 هر جفت از  به همراه درصد خطاي اندازه گيري شده  بين مقادير صحيح و احتمال پيوسته مشاهده شده ( تخمين زده شده ) مشاهده مي شود.

4- کارهاي وابسته

در گذشته روشهاي مختلفي از ياد گيري با نظارت در حضور داده‌هاي آموزشي نويزي آموزش داده شده است و هدف اکثر اين روشها بر مبناي اعمال مدلهاي مختلف نويز و بررسي مفاهيم کلي آموزش‌ها روي اين داده‌هاي نويزي مي باشد و اکثر اين آموزشها از مدلهاي احتمال تقريباً درست و يا ديگر روشهاي تئوري تعليم محاسباتي استفاده مي کند. در اين زمينه گاهي يک حد آستانه تعريف مي کنند که اين حد آستانه در واقع ميزان خطاي قابل تحمل مي باشد يا حتي مي توان يک مقدار حداقل براي نمونه‌هاي نويزي مشخص کرد که در واقع اين ميزان حداقل نمونه‌هاي نويزي لازم براي رسيدن به نرخ خطاي گرفته شده مي باشد.

در ادامه مدلهايي براي آموزشهاي نويزي ارائه خواهد شد.

5- مدل آموزش نويزي

از آنجائيکه معرفي احتمال Valiant يک مدل يادگيري تقريبا صحيح مي باشد مدل يادگيري PAC يکي از
جالب ترين و بهترين مدل‌هاي يادگيري ماشين است .

در يک نمونه از مدل يادگيري PAC ،به ياد گيرنده وظيفه تعيين تخمين نزديک از يک مقدار ناشناخته بين {0,1} با تابع هدف  محول مي شود. به يادگيرنده اجازه دسترسي به يک نمونه اوراکل و پارامتري مطمئن و دقيق داده
مي شود. وقتي که به اوراکل دسترسي پيدا مي کند ، يک نمونه با توجه به توزيع D ايجاد مي کند و يک نمونه همراه با برچسبش با توجه به F بر مي گرداند .

نرخ خطاي خروجي فرضي يادگيرنده ، احتمالي است که يک نمونه انتخاب شده با توجه به D توسط فرضيه ،
اشتباهاً برچسب گذاري شده است.

ياد گيرنده نياز به توليد فرضيه اي دارد با درجه اطمينان بالا دارد که نرخ خطاي آن کمتر از پارامتر دقت باشد تا بتوان از آن در يادگيريهاي نويزي استفاده کرد. در حالت کلي دو معيار پيچيدگي مدل PAC ، پيچيدگي نمونه اي و زماني مي باشد. الگوريتم‌هاي يادگيريPAC  ، براي بسياري از کلاس‌هاي توابع ايجاد شدند و در بيشتر مواقع اطمينان ودقت مورد نظر را فراهم مي آورد بنابراين اين مدل يک مدل يادگيري محبوب مي باشد.

مدل يادگيري توضيح داده شده در بالا ، اغلب از آن به عنوان مدل يادگيري قوي به آن ياد مي شود. چون الگوريتم يادگيري ممکن است نياز به ايجاد خروجي فرضي اختياري دقيق با توجه به پارامتر دقت داشته باشد ، نوع ديگر که مدل يادگيري ضعيف نام دارد ارائه شده است که اين مدل مانند مدل يادگيري قوي است به جز اينکه هيچ پارامتر  دقتي براي آن وجود ندارد و نياز به محاسبه پارامتر دقت نمي باشد و در اين حالت خروجي فرضيه تنها کافي است که نرخ خطاي کمتر از 1/2 داشته باشد به عبارت ديگر خروجي يک الگوريتم يادگيري ضعيف فقط نياز به تخميني دارد که اين تخمين در حدود حدس تصادفي مي باشد (اين مقدار تخمين بهتر از تخمين تصادفي مي باشد) که البته داراي مقياس بهتري نسبت به آن مي باشد.

يک نتيجه پايه اي و تعجب انگيز ابتدا توسط Schapire  به دست آمد و سپس توسط Freund اثبات شد و آن اينکه هر الگوريتم ضعيف کارآمد مي تواند با اعمال يکسري روشها به يک الگوريتم قوي کارآمد تبديل شود بنابراين مي توان ابتدا از يک الگوريتم ضعيف استفاده کرد که ساخت و يادگيري آن ساده مي باشد و در نهايت آن را به يک الگوريتم قوي کارآمد تبديل کرد. يک نقطه بحراني در مدل PAC اين است که داده اي که بايد به يادگيرنده نشان داده شود بايد بدون نويز باشد. در حقيقت اکثر الگوريتم‌هاي يادگيري استاندارد PAC ، اگر نمونه‌هاي برچسب گذاري شده داراي نويز باشند رد مي شوند.

دو مدل معروف نويز براي تحقيقات تئوري و عملي ، تقسيم بندي مدل نويز معرفي شده توسط Larid و  Angulin و مدل خطاي بدخيم ارائه شده توسط LI و Kearns مي باشد.

در مدل طبقه بندي نويز، هر نمونه دريافت شده توسط کاربر به صورت تصادفي ، اشتباهاً برچسب گذاري مي شود  در مدل خطاي بدخيم ، يک رقابت با احتمال ثابت اجازه تعويض نمونه برچسب گذاري شده با نمونه انتخاب شده  برچسب گذاري شده توسط يادگيرنده داده مي شود.

درحاليکه تعداد محدودي از الگوريتم‌هاي PAC اي که ُطبقه بندي نويز را تحمل مي کردند ايجاد شده بودند هيچ کار اساسي براي يادگيري موثر با وجود طبقه بندي نويز تا زمانيکه Keans مدل پرس وجو (درخواستي) آماري (SQ) را معرفي کرد ، صورت نگرفته بود.

در مدل SQ ، نمونه اوراکل استاندارد PAC با اوراکل آماري جايگزين مي شود . الگوريتم SQ ، اوراکل جديد را براي مقادير آماري مختلف بر روي توزيع نمونه‌هاي برچسب گذاري شده مختلف مورد درخواست قرار مي دهد و سپس اوراکل آمارهاي درخواست شده را با خطاي اضافي مشخص برمي گرداند.

از آنجايي که فراخوانيهاي آماري اوراکل مي تواند با گرفتن نمونه‌هاي بزرگ و مناسبي از يک نمونه oracle با احتمال بالايي شبيه سازي شود ، مي توان اين اوراکل جديد را به عنوان واسطي که روش استفاده از نمونه‌هاي برچسب گذاري شده را محدود مي کند ، در نظر گرفت.

دو معيار پيچيدگي الگوريتم‌هايSQ ، پيچيدگي پرس وجو که برابر بيشترين تعداد آمارهاي موردنياز است و پيچيدگي تحمل که کمترين خطاي اضافي مورد نياز است مي باشد. پيچيدگيهاي نمونه اي و زماني شبيه سازي الگوريتم‌هاي SQ در مدل PAC بصورت مستقيم تحت تاثير اين معيارها قرار مي گيرد. بنابراين تمايل بر آن است که اين معيارها تا حد امکان محدود شوند.

Kearns دو خاصيت مهمSQ را نشان داد: اولاً او نشان داد که تقريبا هر الگوريتم يادگيريPAC  مي تواند در مدل SQ پخش شود (قرار گيرد) و سپس نتيجه گرفت که مدل SQ تقريباً يک مدل عمومي است به عبارتي عمومي بودن آن باعث مي شود تا محدوديت کمي بر روي الگوريتم‌هاي يادگيري ايجاد کند. ثانيا او نشان داد که فراخواني‌هاي اوراکل مي تواند با احتمال بسيار بالايي توسط روالي که نمونه‌هاي بزرگي از طبقه بندي نويز اوراکل بيرون
مي کشد ، شبيه سازي شود.

نتيجه اين دو خاصيت اين است که تقريبا هر مدل يادگيريPAC  مي تواند به الگوريتمي تبديل شود که مي تواند طبقه بندي نويز را تحمل کند.

Decatur نشان داد که فراخواني‌هاي اوراکل آماري مي تواند توسط روالي که نمونه‌هاي بزرگ را از اوراکل با خطاي بدخيم خارج مي کند با احتمال بالايي شبيه سازي شود.

در حالي که li و kearns  قبلاً يک تکنيک عمومي براي تبديل الگوريتم يادگيري PAC به الگوريتمي که مقدار کمي از خطاي بدخيم را تحمل مي کند نشان داده بودند ، باز هم به کارگيري SQ در بعضي از شرايط نتايج بهتري را ارائه مي داد.

با اينکه توابعي که با وجود نويز قابل يادگيري هستند گسترش يافتند ، تکنيک KEARNS کاهش مناسبي از مدل يادگيريPAC به مدل يادگيري SQ ايجاد نکرد در حقيقت چنين کاهشي نمي تواند وجود داشته باشد: در حالي که کلاسهاي تابعي توازن در PAC قابل يادگيري هستند،keanrs  نشان داد که اين کلاسها در مدل SQ قابل يادگيري نيستند.

تکنيک KEANRS براي تبديل الگوريتم‌هاي PAC به SQ شامل قوانين عمومي کمي است بنابراين هر الگوريتم PAC بايد آزمايش شود و به تنهايي به الگوريتم SQ تبديل شود بدين صورت که براي هر الگوريتم PAC روشهاي مختلف تست مي شود و روشي خاص اتخاذ مي گردد (يک روش کلي براي کل الگوريتمها وجود ندارد). بنابراين
نمي توان حد بالاي عمومي براي پيچيدگي الگوريتم يادگيري SQ  از حد بالاي پيچيدگي الگوريتم يادگيري PAC بدست آورد.

نتيجه اين واقعيت اين است که حدود بالايي براي پيچيدگي زماني و نمونه اي الگوريتم‌هاي  PACبا وجود نويز بصورت مستقيم نمي تواند بدست آيد.

حدود الگوريتم يادگيريSQ  و PAC را با وجود نويز با استفاده ازنتايج زير بدست مي آيد. الگوريتم يادگيريSQ ضعيف را به روشي مانند الگوريتم يادگيري PAC ضعيف تعريف مي شود و سپس نشان داده مي شود اين امر که دقت الگوريتم‌هاي SQ ضعيف را ارتقا داد تا الگوريتم‌هاي قوي SQ به دست آيد امکان پذير است. بنابر اين نشان داده مي شود که الگوريتمهاي يادگيري SQ ضعيف هم ارز الگوريتمهايSQ  قوي هستند. براي اين منظور از تکنيک ارتقا اکثريت که با وجود وابستگي اش بر روي پارامترهاي دقت ، بهينه است استفاده مي شود.

در مدلSQ  مانند مدل PAC نتايج ارتقا اين اجازه را مي دهد که حد بالايي را براي اکثر پيچيدگيها بدست آورد و خصوصاً مي توان حدود بالايي را با توجه به  بر روي تعداد پرس و جو‌ها بصورت  ،بعد فضاي جستجو بصورت  و معکوس مينيمم تحمل بصورت  بدست آورد. بعلاوه نشان داده
مي شود که اين حدود بالاي عمومي با استفاده از شرح يک کلاس از مسائل يادگيري بهينه هستند. حد پايين
پرس و جو‌ها را با   و معکوس مينيمم تحمل را با بدست مي آيد. در اينجا d بعد کلاس تابعي مي باشد.

پيچيدگيهاي الگوريتم‌هاي SQ در ارتباط با پيچيدگي الگوريتم‌هاي SQ شبيه سازي شده ، با مدل‌هاي نويز مختلف پيچيدگي تحمل نويز الگوريتم‌هايPAC را تعيين مي کند.

Kearns حدود عمومي را براي مينيمم پيچيدگي الگوريتم‌هاي SQ بدست آورد. بعد حدود پاييني خاصي را مانند حدود عمومي که Kearns به دست آورد بدست مي آيد. نتايج ارتقا يک تکنيک عمومي براي ساختن الگوريتم‌هاي SQ که با توجه به اين حدود بهينه هستند را تامين مي کند. الگوريتم‌هاي يادگيري PAC اي که توسط شبيه سازي الگوريتم‌هاي SQ بهينه به دست آمدند با وجو نويز در مقايسه با حدود پاييني شناخته شده براي الگوريتم‌هاي يادگيري PAC ، کارامد نيستند.

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

در اين صورت شبيه سازي اصلي Kearns با  کپي‌هاي مختلفي از الگوريتمSQ  را اجرا
مي شود و نتايج اين اجراها را براي بدست آوردن خروجي پردازش مي شود.

نشان داده مي شود که اين فاکتور انشعاب تا  مي تواند کاهش يابد بنابر اين پيچيدگي زماني شبيه سازي شده کاهش مي يابد.

پيچيدگي شبيه سازي الگوريتمSQ  را با وجود نويز و خطا با ارائه يک مدل طبيعي متفاوتي از  SQ مي توان بهبود بخشيد.

در مدل SQ با خطاي نسبي اجازه داده مي شود که الگوريتم‌هاي SQ ، پرس و جوهاي آماري که تخمين آنها در خطاي نسبي مورد نياز است را مورد پذيرش قرار دهند. همچنين نشان داده مي شود که يک کلاس با خطاي نسبي پرس و جوهاي آماري قابل يادگيري است اگر و تنها اگر با خطاهاي مضاعف پرس و جوهاي آماري قابل يادگيري باشد.

حدهاي عمومي بر روي پيچيدگي خطاي نسبي  الگوريتم SQ در نظر گرفته مي شود و نشان داده مي شود که بسياري از الگوريتم‌هاي يادگيري مي توانند به صورت طبيعي با خطاي نسبي کارآمدي با استفاده از الگوريتم SQ نوشته شود. سپس شبيه سازي‌هايي از خطاي نسبي الگوريتم SQ با وجود نويز و بدون وجود نويز انجام مي شود. اين شبيه سازيها بدون وجود نويز و يا با وجود خطاهاي بدخيم نسبت به شبيه سازيهاي خطاهاي مضاعف الگوريتم‌هاي SQ کار آمدتر هستند.

در آخر نشان داده مي شود که شبيه سازيهاي الگوريتم‌هايSQ بدون وجود نويز در طبقه بندي نويز و با وجود خطاهاي بدخيم مي توانند تغيير يابند تا کلاس بزرگتري از پرس و جوهاي آماري را شامل شوند و همچنين نشان داده مي شود که شبيه سازي ما مي تواند پرس و جوهاي آماري با ميزان واقعي را شامل شوند. بقيه کارها به صورت زير است.

در بخش2-2  مدل‌هاي يادگيري را به صورت رسمي تعريف مي شود و در بخش 2-3 نتايج ارتقا مدل  PACشرح داده مي شود.

لينك دريافت فايل اصلي

پیام بگذارید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *

thirty seven + = forty four