ترفند کرنل و قضیه‌ی مرسر

ترفند کرنل

داده‌ای که در فضای اصلی جدایی‌پذیر خطی نیست، ممکن است بعد از یک نگاشت غیرخطی $\phi(x)$ به فضای بزرگ‌تر جدایی‌پذیر شود. ولی ساختن صریح $\phi(x)$ می‌تواند خیلی پرهزینه یا حتی ناممکن باشد.

چون دوگان SVM فقط به ضرب داخلی نیاز دارد، کافی است $x_i^\top x_j$ را با یک کرنل عوض کنیم:

مثال در $\mathbb R^2$: با $\phi(x) = (x_1^2,\ \sqrt2\,x_1x_2,\ x_2^2)$ داریم

یعنی ضرب داخلی در فضای ویژگی را با یک ضرب داخلی ساده در فضای اصلی و یک توان دو حساب کردیم. طبقه‌بند هم به شکل $f(x) = \sum_i \alpha_i y_i\, k(x_i, x) + b$ درمی‌آید.

کرنل‌های رایج

• خطی: $k(x,z) = x^\top z$
• چندجمله‌ای: $k(x,z) = (x^\top z + c)^p$ با $c \ge 0$
• گاوسی (RBF): $k(x,z) = \exp\!\big(-\gamma\|x - z\|^2\big)$ با $\gamma > 0$

فضای ویژگی کرنل RBF بی‌نهایت‌بعدی است. با این حال محاسبه‌ی آن فقط به فاصله‌ی دو نقطه نیاز دارد.

پارامتر $\gamma$ تعیین می‌کند اثر هر نقطه تا چه فاصله‌ای می‌رسد:

• $\gamma$ بزرگ: کرنل خیلی باریک است، هر نقطه فقط همسایگی کوچک خودش را می‌بیند و مرز تصمیم پرپیچ‌وخم می‌شود (خطر بیش‌برازش).
• $\gamma$ کوچک: کرنل پهن و مرز تصمیم صاف‌تر است (خطر کم‌برازش).

در عمل $\gamma$ و $C$ (درس بعد) را با هم و با اعتبارسنجی متقابل تنظیم می‌کنیم.

چه تابعی کرنل معتبر است؟

هر تابع دومتغیره‌ای کرنل نیست. شرط لازم و کافی (برای وجود یک $\phi$ در یک فضای هیلبرت) این است که $k$ متقارن و مثبت نیمه‌معین باشد: برای هر مجموعه‌ی متناهی از نقاط، ماتریس گرام $K_{ij} = k(x_i, x_j)$ مثبت نیمه‌معین باشد. قضیه‌ی مرسر (برای کرنل پیوسته روی دامنه‌ی فشرده) نسخه‌ی پیوسته‌ی همین نتیجه است و می‌گوید چنین کرنلی بسط $k(x,z) = \sum_m \lambda_m \psi_m(x)\psi_m(z)$ با $\lambda_m \ge 0$ دارد.

پیامد ساده: $k(x,x) \ge 0$ و $k(x,z)^2 \le k(x,x)\,k(z,z)$ (نامساوی کوشی-شوارتز).

ساختن کرنل جدید از کرنل‌های معتبر $k_1, k_2$:

• $k_1 + k_2$ و $c\,k_1$ با $c > 0$
• $k_1 \cdot k_2$
• $\exp(k_1)$ و $g(x)\,k_1(x,z)\,g(z)$ برای هر تابع $g$

ولی $k_1 - k_2$ لزوماً کرنل معتبر نیست.