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

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

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

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

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

 

چکيده

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

در قسمت بعد الگوريتمهايي براي آموزش نويزي از جمله الگوريتم 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شرح داده مي شود.

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