تقریب هندسی با کمک هسته ها

http://www.cs.duke.edu/~pankaj/publications/slides/core-set.pdf

نمونه گیری تصادفی تقریبی از ورودی را به ما می دهد و ممکن است گاهی به ما تقریب ویژگی که لازم داریم را هم بدهد اما وقتی این طور نباشد، می توانیم از مفهومی به نام هسته (coreset) استفاده کنیم که به طور خاص برای این تعریف شده است که تقریب یک ویژگی خاص را به ما بدهد.

اپسیلون کرنل: اگر به جای فضای دکارتی از فضای قطبی (مجموعه ای از جهت ها) استفاده کنیم به هسته ی به دست آمده اپسیلون کرنل می گویند.

مجموعه چاق خاصیت اپسیلون کرنل را حفظ می کند.

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

مقیاسهای گستره نقاط قابل اعتماد: توابعی هستند که هر ضریب دلخواهی از ضریب تقریب اولیه را برای هر اپسیلون کرنل بدهند.

مثال از مقیاس های قابل اعتماد: طول، عرض و ...

مثال از مقیاس های غیرقابل اعتماد: عرض کوچکترین زوج ابرکره شامل همه ی نقاط

به دست آوردن مقیاس های قابل اعتماد: ضریب تقریب را به ضریب داده شده تقسیم کرده و برای ضریب تقریب جدید جواب را به دست می آوریم!

به دست آوردن مقیاسهای غیر قابل اعتماد: می توانیم با خطی سازی بسیاری از توابع را به توابع خطی تصویر کنیم و ارتباط بین توابع خطی و نقاط را به دست بیاوریم.

برای مساله ها و کاربردها به اسلاید مراجعه کنید.