Skip to article frontmatterSkip to article content
Site not loading correctly?

This may be due to an incorrect BASE_URL configuration. See the MyST Documentation for reference.

روش کرنل (ترفند کرنل)

English · فارسی

1. مقدمه

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

روش کرنل (که اغلب ترفند کرنل نامیده می‌شود) راهی توانمند برای به‌کارگیری الگوریتم‌های خطی روی دادهٔ ناخطی می‌دهد. ایدهٔ اصلی نگاشت داده به فضای ویژگی (F\mathcal{F}) با ابعاد بالاتر است که در آن داده خطی‌جداپذیر می‌شود یا مدل‌سازی خطی‌اش آسان‌تر است. «ترفند» این است که این نگاشت را می‌توان به‌صورت ضمنی با یک تابع کرنل انجام داد، بدون آنکه هرگز نیاز باشد مختصات نقطه‌های داده در فضای ویژگی پرابعاد (و شاید بی‌نهایت‌بعد) صریحاً حساب شود. این کار بار محاسباتی نگاشت صریح را دور می‌زند.

توجه: ترفند کرنل، که با نام‌های روش کرنل یا ماشین‌های کرنلی هم شناخته می‌شود، دسته‌ای از الگوریتم‌ها برای تحلیل الگو است که در آن‌ها از دسته‌بندهای خطی برای حل مسئله‌های ناخطی استفاده می‌شود. این روش‌ها با کرنل‌سازی فرق دارند؛ آن یکی تکنیکی برای طراحی الگوریتم‌های کارآمد است که کارآمدی‌اش را از یک مرحلهٔ پیش‌پردازش می‌گیرد که در آن ورودی الگوریتم با ورودی کوچک‌تری به نام «کرنل» جایگزین می‌شود.

2. محدودیت‌های مدل‌های خطی

یک مسئلهٔ دسته‌بندی دودویی را در نظر بگیرید. مدل خطی می‌کوشد ابرصفحه‌ای بیابد که نقطه‌های دادهٔ دسته‌های مختلف را جدا کند.

اگر چنین ابرصفحهٔ جداکننده‌ای وجود داشته باشد، داده خطی‌جداپذیر نامیده می‌شود. ولی اگر داده ساختار ناخطی داشته باشد، مثل مسئلهٔ کلاسیک XOR یا دایره‌های هم‌مرکز، هیچ ابرصفحهٔ واحدی نمی‌تواند دسته‌ها را در فضای ورودی اصلی درست جدا کند.

3. نگاشت ویژگی

برای سر و کار داشتن با دادهٔ ناخطی، می‌توانیم داده را به فضای ویژگی تازه و پرابعادتری ببریم که در آن شاید خطی‌جداپذیر شود. این کار با یک تابع نگاشت انجام می‌شود که با ϕ\phi نشان می‌دهیم:

ϕ:X→F\phi: \mathcal{X} \to \mathcal{F}

4. ترفند کرنل

توان روش کرنل در این مشاهده نهفته است که بسیاری از الگوریتم‌های خطی را می‌توان چنان صورت‌بندی کرد که فقط به ضرب داخلی میان نقطه‌های داده (xiTxj\mathbf{x}_i^T \mathbf{x}_j) نیاز داشته باشند. نمونه‌ها: پرسپترون (در صورت دوگان)، رگرسیون لجستیک (صورت دوگان)، PCA و ماشین‌های بردار پشتیبان.

اگر از نگاشت ویژگی ϕ\phi استفاده کنیم، این الگوریتم‌ها باید ضرب داخلی را در فضای ویژگی پرابعاد حساب کنند: ϕ(xi)Tϕ(xj)\phi(\mathbf{x}_i)^T \phi(\mathbf{x}_j). حساب کردن صریح ϕ(x)\phi(\mathbf{x}) می‌تواند از نظر محاسباتی بسیار پرهزینه باشد، به‌ویژه اگر F\mathcal{F} ابعاد بسیار بالا یا بی‌نهایت داشته باشد.

ترفند کرنل این محاسبهٔ صریح را دور می‌زند. یک تابع کرنل KK تعریف می‌کنیم که ضرب داخلی را در فضای ویژگی مستقیماً از بردارهای ورودی اصلی حساب می‌کند:

K(x,z)=ϕ(x)Tϕ(z)K(\mathbf{x}, \mathbf{z}) = \phi(\mathbf{x})^T \phi(\mathbf{z})

اگر تابعی KK بیابیم که این ضرب داخلی را کارآمد حساب کند بدون آنکه نخست ϕ(x)\phi(\mathbf{x}) و ϕ(z)\phi(\mathbf{z}) را حساب کنیم، می‌توانیم از آن در الگوریتم خطی‌مان استفاده کنیم. کافی است هر ضرب داخلی xiTxj\mathbf{x}_i^T \mathbf{x}_j را با مقدار کرنل K(xi,xj)K(\mathbf{x}_i, \mathbf{x}_j) جایگزین کنیم.

این به ما اجازه می‌دهد عملاً در فضای ویژگی پرابعاد F\mathcal{F} کار کنیم و در همان حال محاسبات را فقط در فضای ورودی اصلی X\mathcal{X} انجام دهیم.

تصویری از نگاشت ϕ\phi و تابع کرنل kk.

5. الگوریتم‌هایی که از کرنل استفاده می‌کنند

هر الگوریتمی که تنها برحسب ضرب داخلی میان نمونه‌های ورودی بیان شود، به‌طور بالقوه «کرنلی‌شدنی» است.

6. تابع‌های کرنل رایج

چند تابع کرنل استاندارد وجود دارد که هر کدام متناظر با نگاشت ویژگی متفاوتی است.

7. قضیهٔ مرسر: چه زمانی K کرنل معتبر است؟

هر تابع K(x,z)K(\mathbf{x}, \mathbf{z}) را نمی‌توان به‌عنوان ضرب داخلی ϕ(x)Tϕ(z)\phi(\mathbf{x})^T \phi(\mathbf{z}) در فضایی ویژگی (به‌ویژه فضای هیلبرت) تفسیر کرد. قضیهٔ مرسر شرط معتبر بودن یک تابع به‌عنوان کرنل را می‌دهد.

تعریف: ماتریس گرام

با مجموعه‌دادهٔ {x1,…,xn}\{\mathbf{x}_1, \dots, \mathbf{x}_n\} و نگاشت ویژگی ϕ\phi که هر نقطهٔ داده را به فضایی با ضرب داخلی (احتمالاً بی‌نهایت‌بعد) می‌برد، ماتریس گرام K\mathbf{K} ماتریسی n×nn \times n است که درایهٔ (i,j)(i, j) آن ضرب داخلی نمایش‌های ویژگی است:

Kij=⟨ϕ(xi),ϕ(xj)⟩\mathbf{K}_{ij} = \langle \phi(\mathbf{x}_i), \phi(\mathbf{x}_j) \rangle

رابطه با تابع کرنل

تابع کرنل KK دقیقاً همین ضرب داخلی تعریف می‌شود:

K(xi,xj)=⟨ϕ(xi),ϕ(xj)⟩K(\mathbf{x}_i, \mathbf{x}_j) = \langle \phi(\mathbf{x}_i), \phi(\mathbf{x}_j) \rangle

بنابراین درایه‌های ماتریس گرام را می‌توان به‌طور هم‌ارز چنین نوشت:

Kij=⟨ϕ(xi),ϕ(xj)⟩=K(xi,xj)\mathbf{K}_{ij} = \langle \phi(\mathbf{x}_i), \phi(\mathbf{x}_j) \rangle = K(\mathbf{x}_i, \mathbf{x}_j)

تعریف: ماتریس مثبت نیمه‌معین (PSD) ماتریس متقارن K\mathbf{K} مثبت نیمه‌معین است اگر برای هر بردار ناصفر c∈Rn\mathbf{c} \in \mathbb{R}^n:

cTKc≥0\mathbf{c}^T \mathbf{K} \mathbf{c} \ge 0

قضیهٔ مرسر (ساده‌شده): X\mathcal{X} را زیرمجموعه‌ای فشرده از Rp\mathbb{R}^p بگیرید. تابع پیوسته و متقارن K:X×X→RK: \mathcal{X} \times \mathcal{X} \to \mathbb{R} کرنل معتبر است (یعنی نگاشتی ϕ\phi به فضای هیلبرت وجود دارد چنان که K(x,z)=⟨ϕ(x),ϕ(z)⟩K(\mathbf{x}, \mathbf{z}) = \langle \phi(\mathbf{x}), \phi(\mathbf{z}) \rangle) اگر و تنها اگر ماتریس گرام K\mathbf{K} برای هر مجموعهٔ متناهی از نقطه‌های {x1,…,xn}\{\mathbf{x}_1, \dots, \mathbf{x}_n\} برگرفته از X\mathcal{X} مثبت نیمه‌معین باشد.

اثبات: اگر KK کرنل باشد   ⟹  \implies ماتریس گرام PSD است فرض کنید K(x,z)=ϕ(x)Tϕ(z)K(\mathbf{x}, \mathbf{z}) = \phi(\mathbf{x})^T \phi(\mathbf{z}) برای نگاشتی ϕ\phi. {x1,…,xn}\{\mathbf{x}_1, \dots, \mathbf{x}_n\} هر مجموعه‌ای از نقطه‌ها و K\mathbf{K} ماتریس گرام متناظر (Kij=ϕ(xi)Tϕ(xj)\mathbf{K}_{ij} = \phi(\mathbf{x}_i)^T \phi(\mathbf{x}_j)) باشد. برای هر بردار c=(c1,…,cn)T∈Rn\mathbf{c} = (c_1, \dots, c_n)^T \in \mathbb{R}^n، صورت درجه‌دوم را در نظر بگیرید:

cTKc=∑i=1n∑j=1ncicjKij\mathbf{c}^T \mathbf{K} \mathbf{c} = \sum_{i=1}^n \sum_{j=1}^n c_i c_j \mathbf{K}_{ij}

Kij=ϕ(xi)Tϕ(xj)\mathbf{K}_{ij} = \phi(\mathbf{x}_i)^T \phi(\mathbf{x}_j) را جای‌گذاری کنید:

cTKc=∑i=1n∑j=1ncicj(ϕ(xi)Tϕ(xj))\mathbf{c}^T \mathbf{K} \mathbf{c} = \sum_{i=1}^n \sum_{j=1}^n c_i c_j (\phi(\mathbf{x}_i)^T \phi(\mathbf{x}_j))

جمله‌ها را بازآرایی کنید:

cTKc=∑i=1nciϕ(xi)T(∑j=1ncjϕ(xj))\mathbf{c}^T \mathbf{K} \mathbf{c} = \sum_{i=1}^n c_i \phi(\mathbf{x}_i)^T \left( \sum_{j=1}^n c_j \phi(\mathbf{x}_j) \right)
cTKc=(∑i=1nciϕ(xi))T(∑j=1ncjϕ(xj))\mathbf{c}^T \mathbf{K} \mathbf{c} = \left( \sum_{i=1}^n c_i \phi(\mathbf{x}_i) \right)^T \left( \sum_{j=1}^n c_j \phi(\mathbf{x}_j) \right)

بگذارید v=∑i=1nciϕ(xi)\mathbf{v} = \sum_{i=1}^n c_i \phi(\mathbf{x}_i). این برداری در فضای ویژگی F\mathcal{F} است. عبارت چنین می‌شود:

cTKc=vTv=∥v∥2\mathbf{c}^T \mathbf{K} \mathbf{c} = \mathbf{v}^T \mathbf{v} = \|\mathbf{v}\|^2

چون مربع نُرم اقلیدسی (یا مربع نُرم در فضای هیلبرت) هر بردار همیشه نامنفی است، داریم:

cTKc=∥∑i=1nciϕ(xi)∥2≥0\mathbf{c}^T \mathbf{K} \mathbf{c} = \left\| \sum_{i=1}^n c_i \phi(\mathbf{x}_i) \right\|^2 \ge 0

پس ماتریس گرام K\mathbf{K} مثبت نیمه‌معین است.

جهت دیگر قضیهٔ مرسر (اینکه هر تابع KK که ماتریس‌های گرام PSD تولید کند متناظر با یک نگاشت ویژگی ϕ\phi است) اثبات پیچیده‌تری دارد ولی تضمین می‌کند که تابع‌هایی مثل کرنل گاوسی یا چندجمله‌ای معتبرند.

پیامدها: قضیهٔ مرسر بنیادی است چون می‌گوید کدام تابع‌های KK را می‌توانیم به‌طور قانونی به‌عنوان کرنل در الگوریتم‌هایمان به کار ببریم. لازم نیست ϕ\phi را صریحاً بیابیم؛ فقط باید شرط مثبت نیمه‌معین بودن KK را بررسی کنیم. در عمل اغلب از کرنل‌های شناخته‌شده (خطی، چندجمله‌ای، RBF) استفاده می‌کنیم که می‌دانیم شرط مرسر را برآورده می‌کنند. همچنین می‌توان از کرنل‌های معتبر موجود کرنل‌های معتبر تازه ساخت (مثلاً جمع یا ضرب کرنل‌های معتبر هم کرنل معتبر است).

8. تفسیرها و عملیات دیگر در فضای ویژگی (با کرنل)

ترفند کرنل نه‌تنها به ما اجازه می‌دهد الگوریتم‌ها را به‌صورت ضمنی در فضای ویژگی F\mathcal{F} اجرا کنیم، بلکه امکان می‌دهد برخی ویژگی‌های مربوط به داده را در آن فضا بفهمیم و حساب کنیم، همه بدون نیاز به مختصات صریح ϕ(x)\phi(\mathbf{x}).

مقدار کرنل به‌عنوان شباهت:

همان‌طور که پیش‌تر گفتیم، تابع کرنل K(x,z)=ϕ(x)Tϕ(z)K(\mathbf{x}, \mathbf{z}) = \phi(\mathbf{x})^T \phi(\mathbf{z}) ضرب داخلی میان بردارهای ویژگی ϕ(x)\phi(\mathbf{x}) و ϕ(z)\phi(\mathbf{z}) را نشان می‌دهد. در فضای اقلیدسی (و فضاهای هیلبرت)، ضرب داخلی با زاویهٔ میان بردارها نسبت نزدیک دارد. ضرب داخلی بزرگ‌تر و مثبت یعنی بردارها در جهت‌های مشابه‌اند، که شباهت بیشتر را نشان می‌دهد. بنابراین مقدار کرنل K(x,z)K(\mathbf{x}, \mathbf{z}) را می‌توان سنجهٔ شباهت میان نقطه‌های اصلی x\mathbf{x} و z\mathbf{z} پس از نگاشت به فضای ویژگی F\mathcal{F} دانست. همین تفسیر بنیاد خوب کار کردن کرنل‌ها در الگوریتم‌هایی مثل SVM (یافتن نقطه‌های شبیه بردارهای پشتیبان) یا خوشه‌بندی (گروه کردن نقطه‌های شبیه) است. کرنل‌های مختلف تلقی‌های مختلفی از شباهت را می‌گیرند.

نُرم یک نقطه در فضای ویژگی:

مربع نُرم اقلیدسی (یا مربع طول) نقطهٔ نگاشت‌شدهٔ ϕ(x)\phi(\mathbf{x}) در فضای ویژگی را می‌توان با تابع کرنل حساب کرد. یادآوری می‌کنیم مربع نُرم یک بردار ضرب داخلی آن با خودش است:

∥ϕ(x)∥2=ϕ(x)Tϕ(x)\|\phi(\mathbf{x})\|^2 = \phi(\mathbf{x})^T \phi(\mathbf{x})

با تعریف کرنل، این به‌سادگی چنین است:

∥ϕ(x)∥2=K(x,x)\|\phi(\mathbf{x})\|^2 = K(\mathbf{x}, \mathbf{x})

پس درایه‌های قطری ماتریس گرام K\mathbf{K} مربع نُرم نقطه‌های داده در فضای ویژگی را می‌دهند. این مثلاً وقتی لازم است نقطه‌ها را در F\mathcal{F} نرمال کنیم سودمند است.

میانگین در فضای ویژگی:

با مجموعه‌دادهٔ {x1,x2,...,xn}\{\mathbf{x}_1, \mathbf{x}_2, ..., \mathbf{x}_n\}، میانگین نمایش‌هایشان در فضای ویژگی چنین است:

mϕ=1n∑i=1nϕ(xi)\mathbf{m}_\phi = \frac{1}{n} \sum_{i=1}^n \phi(\mathbf{x}_i)

هرچند معمولاً نمی‌توانیم mϕ\mathbf{m}_\phi را مستقیماً حساب یا نگه داریم (چون در F\mathcal{F} زندگی می‌کند)، می‌توانیم ضرب داخلی‌اش با هر نقطهٔ نگاشت‌شدهٔ ϕ(x)\phi(\mathbf{x}) را با کرنل حساب کنیم:

ϕ(x)Tmϕ=ϕ(x)T(1n∑j=1nϕ(xj))=1n∑j=1nϕ(x)Tϕ(xj)=1n∑j=1nK(x,xj)\phi(\mathbf{x})^T \mathbf{m}_\phi = \phi(\mathbf{x})^T \left( \frac{1}{n} \sum_{j=1}^n \phi(\mathbf{x}_j) \right) = \frac{1}{n} \sum_{j=1}^n \phi(\mathbf{x})^T \phi(\mathbf{x}_j) = \frac{1}{n} \sum_{j=1}^n K(\mathbf{x}, \mathbf{x}_j)

به‌همین‌ترتیب مربع نُرم بردار میانگین را هم می‌توان حساب کرد:

∥mϕ∥2=mϕTmϕ=(1n∑i=1nϕ(xi))T(1n∑j=1nϕ(xj))=1n2∑i=1n∑j=1nϕ(xi)Tϕ(xj)=1n2∑i=1n∑j=1nK(xi,xj)\|\mathbf{m}_\phi\|^2 = \mathbf{m}_\phi^T \mathbf{m}_\phi = \left( \frac{1}{n} \sum_{i=1}^n \phi(\mathbf{x}_i) \right)^T \left( \frac{1}{n} \sum_{j=1}^n \phi(\mathbf{x}_j) \right) = \frac{1}{n^2} \sum_{i=1}^n \sum_{j=1}^n \phi(\mathbf{x}_i)^T \phi(\mathbf{x}_j) = \frac{1}{n^2} \sum_{i=1}^n \sum_{j=1}^n K(\mathbf{x}_i, \mathbf{x}_j)

این توانایی کار کردن با میانگین به‌صورت ضمنی برای الگوریتم‌هایی مثل PCA کرنلی که به مرکز کردن داده در فضای ویژگی نیاز دارند حیاتی است.

فاصلهٔ میان نقطه‌ها:

فاصلهٔ ϕ(xi)\phi(\textbf{x}_i) و ϕ(xj)\phi(\textbf{x}_{j}) چنین است

∥ϕ(xi)−ϕ(xj)∥2=∥ϕ(xi)∥2+∥ϕ(xj)∥2−2ϕ(xi)Tϕ(xj)=K(xi,xi)+K(xj,xj)−2K(xi,xj)\|\phi(\textbf{x}_i) -\phi(\textbf{x}_{j})\|^2 = \|\phi(\textbf{x}_i)\|^2 + \|\phi(\textbf{x}_{j})\|^2 - 2 \phi(\textbf{x}_i)^T\phi(\textbf{x}_{j})\\ = K(\textbf{x}_i,\textbf{x}_i) + K (\textbf{x}_{j}, \textbf{x}_{j}) - 2 K(\textbf{x}_i,\textbf{x}_{j})

که یعنی

∥ϕ(xi)−ϕ(xj)∥=K(xi,xi)+K(xj,xj)−2K(xi,xj)\|\phi(\textbf{x}_i) -\phi(\textbf{x}_{j})\| = \sqrt{K(\textbf{x}_i,\textbf{x}_i) + K (\textbf{x}_{j}, \textbf{x}_{j}) - 2 K(\textbf{x}_i,\textbf{x}_{j})}

واریانس کل در فضای ویژگی:

واریانس کل داده در فضای ویژگی پخش‌شدگی نقطه‌های ϕ(xi)\phi(\mathbf{x}_i) حول میانگینشان mϕ\mathbf{m}_\phi را می‌سنجد. معمولاً به‌صورت میانگین مربع فاصله از میانگین تعریف می‌شود:

Varϕ=1n∑i=1n∥ϕ(xi)−mϕ∥2\text{Var}_\phi = \frac{1}{n} \sum_{i=1}^n \|\phi(\mathbf{x}_i) - \mathbf{m}_\phi\|^2

می‌توانیم این را با کرنل حساب کنیم. با بسط نُرم:

∥ϕ(xi)−mϕ∥2=∥ϕ(xi)∥2−2ϕ(xi)Tmϕ+∥mϕ∥2\|\phi(\mathbf{x}_i) - \mathbf{m}_\phi\|^2 = \|\phi(\mathbf{x}_i)\|^2 - 2 \phi(\mathbf{x}_i)^T \mathbf{m}_\phi + \|\mathbf{m}_\phi\|^2

حالا بیان‌های کرنلی را که بالا یافتیم جای‌گذاری کنید:

∥ϕ(xi)−mϕ∥2=K(xi,xi)−2n∑j=1nK(xi,xj)+1n2∑k=1n∑l=1nK(xk,xl)\|\phi(\mathbf{x}_i) - \mathbf{m}_\phi\|^2 = K(\mathbf{x}_i, \mathbf{x}_i) - \frac{2}{n} \sum_{j=1}^n K(\mathbf{x}_i, \mathbf{x}_j) + \frac{1}{n^2} \sum_{k=1}^n \sum_{l=1}^n K(\mathbf{x}_k, \mathbf{x}_l)

جمع روی ii و تقسیم بر nn واریانس کل را می‌دهد که کاملاً از مقدارهای کرنل K(xi,xj)K(\mathbf{x}_i, \mathbf{x}_j) حساب‌شدنی است. این محاسبه در PCA کرنلی مرکزی است.

نرمال‌سازی داده در فضای ویژگی:

بعضی وقت‌ها نرمال کردن نقطه‌های داده در فضای ویژگی مطلوب است. دو نوع رایج نرمال‌سازی:

ϕ~(xi)=ϕ(xi)−mϕ\tilde{\phi}(\mathbf{x}_i) = \phi(\mathbf{x}_i) - \mathbf{m}_\phi.

هرچند ϕ~(xi)\tilde{\phi}(\mathbf{x}_i) را صریح حساب نمی‌کنیم، می‌توانیم ماتریس کرنل K~\mathbf{\tilde{K}} متناظر با این نقطه‌های مرکزشده را از ماتریس کرنل اصلی K\mathbf{K} حساب کنیم. این عملیات عملاً داده را در F\mathcal{F} مرکز می‌کند. فرمول ماتریس کرنل مرکزشدهٔ K~\mathbf{\tilde{K}} که در آن K~ij=ϕ~(xi)Tϕ~(xj)\tilde{K}_{ij} = \tilde{\phi}(\mathbf{x}_i)^T \tilde{\phi}(\mathbf{x}_j) چنین است: K~=K−1nK−K1n+1nK1n\mathbf{\tilde{K}} = \mathbf{K} - \mathbf{1}_n \mathbf{K} - \mathbf{K} \mathbf{1}_n + \mathbf{1}_n \mathbf{K} \mathbf{1}_n، که 1n\mathbf{1}_n ماتریسی n×nn \times n است با همهٔ درایه‌های برابر 1/n1/n. این دقیقاً همان گام مرکز کردن است که در PCA کرنلی استفاده می‌شود.

9. مزایا و معایب ترفند کرنل

مزایا:

  1. توان مدل‌سازی ناخطی: کرنل‌ها به الگوریتم‌های خطی اجازه می‌دهند رابطه‌ها و مرزهای تصمیم پیچیدهٔ ناخطی را بدون تغییر خود الگوریتم اصلی مدل کنند.

  2. کارایی محاسباتی: حساب کردن صریح بردارهای ویژگی ϕ(x)\phi(\mathbf{x}) که ممکن است ابعاد بسیار بالا یا بی‌نهایت داشته باشند دور زده می‌شود. محاسبات در بُعد فضای ورودی اصلی می‌مانند و هنگام حساب کردن ماتریس گرام فقط به تعداد نقطه‌های داده بستگی دارند.

  3. پیمانه‌ای بودن: با تغییر تابع کرنل (مثلاً از چندجمله‌ای به RBF) می‌توان به‌سادگی میان نوع‌های مختلف ناخطی‌بودن جابه‌جا شد.

  4. کار با دادهٔ غیربرداری: کرنل‌ها را می‌توان برای نوع‌های داده‌ای تعریف کرد که طبیعتاً به‌صورت بردار با اندازهٔ ثابت نمایش داده نمی‌شوند، مثل رشته‌ها، گراف‌ها یا تصویرها، تا زمانی که تابع شباهت معناداری (که شرط مرسر را برآورده کند) تعریف‌شدنی باشد.

معایب:

  1. هزینهٔ محاسباتی با مجموعه‌دادهٔ بزرگ: حساب کردن و نگه داشتن ماتریس گرام K\mathbf{K} زمان O(n2d)O(n^2 d) یا O(n2)O(n^2) (بسته به پیچیدگی کرنل) و حافظهٔ O(n2)O(n^2) می‌گیرد، که nn تعداد نمونه‌ها و dd بُعد اصلی است. این برای nn بسیار بزرگ ناممکن می‌شود. الگوریتم‌هایی که از کرنل استفاده می‌کنند معمولاً پیچیدگی‌ای در حدود n2n^2 یا n3n^3 دارند.

  2. انتخاب کرنل و ابرپارامترها: کارایی به‌شدت به انتخاب تابع کرنل (مثلاً خطی، RBF، چندجمله‌ای) و ابرپارامترهایش (مثلاً γ\gamma برای RBF و dd و cc برای چندجمله‌ای) حساس است. این اغلب تنظیم دقیق با روش‌هایی مثل اعتبارسنجی متقاطع می‌خواهد.

  3. تفسیرپذیری: هرچند مرز تصمیم در فضای ویژگی خطی است، مرز متناظر در فضای ورودی اصلی می‌تواند بسیار پیچیده و به‌سختی تفسیرپذیر باشد. از تفسیر ضریب‌های یک مدل خطی ساده روراست‌تر نیست.

جمع‌بندی

ترفند کرنل تکنیکی ریاضی و توانمند است که به الگوریتم‌های خطی (به‌ویژه آن‌هایی که فقط به ضرب داخلی تکیه دارند) اجازه می‌دهد به‌صورت ضمنی در فضای ویژگی پرابعاد F\mathcal{F} کار کنند. با تعریف تابع کرنل K(x,z)=ϕ(x)Tϕ(z)K(\mathbf{x}, \mathbf{z}) = \phi(\mathbf{x})^T \phi(\mathbf{z})، ضرب‌های داخلی در الگوریتم اصلی را با مقدارهای کرنل جایگزین می‌کنیم. این کار محاسبهٔ بالقوه پرهزینهٔ نگاشت ویژگی ϕ\phi را دور می‌زند و در همان حال اثر نگاشت داده به فضایی را می‌دهد که در آن شاید خطی‌جداپذیر باشد یا الگوهای خطی پدید آیند. جنبه‌های کلیدی:

10. خوشه‌بندی k-means کرنلی

مرور: الگوریتم استاندارد k-means

k-means الگوریتم خوشه‌بندی پرکاربردی است که مجموعه‌داده را با کمینه کردن مجموع مربع فاصله‌های هر نقطه از مرکز خوشهٔ تخصیص‌یافته‌اش به kk خوشه افراز می‌کند.

گام‌های الگوریتم:

  1. مقداردهی اولیه: تصادفی kk مرکز اولیه μ1,…,μk\boldsymbol{\mu}_1, \ldots, \boldsymbol{\mu}_k برگزینید.

  2. گام تخصیص: هر نقطهٔ دادهٔ xj\mathbf{x}_j را به نزدیک‌ترین مرکز تخصیص دهید: i∗=arg⁡min⁡i{∥xj−μi∥2} i^* = \arg\min_{i} \left\{ \|\mathbf{x}_j - \boldsymbol{\mu}_i\|^2 \right\}

  3. گام به‌روزرسانی: هر مرکز را به‌عنوان میانگین نقطه‌های تخصیص‌یافته به آن دوباره حساب کنید: μi=1∣Ci∣∑xj∈Cixj \boldsymbol{\mu}_i = \frac{1}{|C_i|} \sum_{\mathbf{x}_j \in C_i} \mathbf{x}_j

  4. تکرار گام‌های 2 و 3 تا همگرایی (یعنی وقتی تخصیص‌ها دیگر عوض نشوند یا مرکزها پایدار شوند).

تابع هدف:

SSE(C)=∑i=1k∑xj∈Ci∥xj−μi∥2SSE(\mathcal{C}) = \sum_{i=1}^{k} \sum_{\mathbf{x}_j \in C_i} \|\mathbf{x}_j - \boldsymbol{\mu}_i\|^2

محدودیت: k-means فقط می‌تواند خوشه‌های جدا‌شده با مرزهای خطی را بیابد. وقتی خوشه‌ها ساختار ناخطی دارند شکست می‌خورد.


k-means کرنلی: انگیزه

برای غلبه بر محدودیت خطی‌بودن، k-means کرنلی از ترفند کرنل استفاده می‌کند تا داده را به‌صورت ضمنی به فضای ویژگی پرابعادتری ببرد که در آن خوشه‌ها شاید خطی‌جداپذیر شوند.


الگوریتم k-means کرنلی

تعریف‌ها:

فاصله در فضای ویژگی: مربع فاصلهٔ یک نقطه تا مرکز یک خوشه در فضای ویژگی را می‌توان فقط با مقدارهای کرنل حساب کرد:

∥ϕ(xj)−μiϕ∥2=K(xj,xj)−2ni∑xa∈CiK(xa,xj)+1ni2∑xa,xb∈CiK(xa,xb)\|\phi(\mathbf{x}_j) - \boldsymbol{\mu}_i^\phi\|^2 = K(\mathbf{x}_j, \mathbf{x}_j) - \frac{2}{n_i} \sum_{\mathbf{x}_a \in C_i} K(\mathbf{x}_a, \mathbf{x}_j) + \frac{1}{n_i^2} \sum_{\mathbf{x}_a, \mathbf{x}_b \in C_i} K(\mathbf{x}_a, \mathbf{x}_b)

گام‌های الگوریتم:

  1. مقداردهی اولیه: تصادفی نقطه‌ها را به kk خوشه تخصیص دهید.

  2. برای هر خوشهٔ CiC_i و هر نقطهٔ xj\mathbf{x}_j:

    • حساب کنید:

      • sqnormi=1ni2∑xa,xb∈CiK(xa,xb)\text{sqnorm}_i = \frac{1}{n_i^2} \sum_{\mathbf{x}_a, \mathbf{x}_b \in C_i} K(\mathbf{x}_a, \mathbf{x}_b)

      • avgji=1ni∑xa∈CiK(xa,xj)\text{avg}_{ji} = \frac{1}{n_i} \sum_{\mathbf{x}_a \in C_i} K(\mathbf{x}_a, \mathbf{x}_j)

    • فاصله را حساب کنید: d(xj,Ci)=sqnormi−2⋅avgjid(\mathbf{x}_j, C_i) = \text{sqnorm}_i - 2 \cdot \text{avg}_{ji}

  3. گام تخصیص: هر نقطه را به خوشه‌ای با کمترین d(xj,Ci)d(\mathbf{x}_j, C_i) تخصیص دهید.

  4. تکرار گام‌های 2 و 3 تا همگرایی.

تابع هدف در فضای کرنل:

min⁡C  SSE(C)=∑i=1k∑xj∈Ci∥ϕ(xj)−μiϕ∥2\min_{\mathcal{C}} \; SSE(\mathcal{C}) = \sum_{i=1}^k \sum_{\mathbf{x}_j \in C_i} \|\phi(\mathbf{x}_j) - \boldsymbol{\mu}_i^\phi\|^2

نکته‌ها


مثال: کرنل گاوسی

با کرنل گاوسی (RBF):

K(xi,xj)=exp⁡(−∥xi−xj∥22σ2)K(\mathbf{x}_i, \mathbf{x}_j) = \exp\left(-\frac{\|\mathbf{x}_i - \mathbf{x}_j\|^2}{2\sigma^2}\right)

k-means کرنلی می‌تواند خوشه‌های هم‌مرکز یا خوشه‌هایی را که به‌صورت ناخطی جداپذیرند از هم جدا کند.


تمرین‌ها

  1. x=(x1,x2)∈R2\mathbf{x} = (x_1, x_2) \in \mathbb{R}^2 و K(x,z)=(1+x⊤z)2K(\mathbf{x}, \mathbf{z}) = (1 + \mathbf{x}^\top \mathbf{z})^2 را بگیرید. نگاشت ویژگی صریح ϕ\phi را بیابید که K(x,z)=ϕ(x)⊤ϕ(z)K(\mathbf{x}, \mathbf{z}) = \phi(\mathbf{x})^\top \phi(\mathbf{z}) را برآورده کند و بُعد فضای ویژگی را بشمارید.

  2. نشان دهید کرنل گاوسی K(x,z)=exp⁡(−∥x−z∥2/2σ2)K(\mathbf{x},\mathbf{z}) = \exp(-\|\mathbf{x}-\mathbf{z}\|^2 / 2\sigma^2) متناظر با فضای ویژگی بی‌نهایت‌بعد است، با بسط دادنش با سری تیلور ete^t و شناسایی ضریب‌ها.

  3. با قضیهٔ مرسر تعیین کنید کدام‌یک از K(x,z)=∥x−z∥K(\mathbf{x},\mathbf{z}) = \|\mathbf{x}-\mathbf{z}\|، K(x,z)=(x⊤z)3K(\mathbf{x},\mathbf{z}) = (\mathbf{x}^\top\mathbf{z})^3 و K(x,z)=x⊤z−1K(\mathbf{x},\mathbf{z}) = \mathbf{x}^\top \mathbf{z} - 1 کرنل معتبرند. برای نامعتبرها مجموعهٔ متناهی از نقطه‌ها را نشان دهید که ماتریس گرامشان مقدار ویژهٔ منفی دارد.

  4. ریج کرنلی معادلهٔ (K+λI)α=y(K + \lambda I)\alpha = y را حل می‌کند. نشان دهید وقتی λ→0\lambda \to 0 و KK وارون‌پذیر است این کار داده را درون‌یابی می‌کند، و توضیح دهید چرا σ\sigma بزرگ در کرنل RBF جواب را هموارتر می‌کند (راهنما: به ماتریس گرام نگاه کنید).

  5. k-means کرنلی را از اتحاد SSE الگوریتم استاندارد استنتاج کنید و بررسی کنید که با کرنل خطی هر فرمول به به‌روزرسانی معمول k-means فرو می‌کاهد.

  6. هزینهٔ ترفند کرنل همان ماتریس گرام n×nn \times n است. حافظهٔ لازم برای n=105n = 10^5 با ذخیره در float64 را برآورد کنید و توضیح دهید ترفند کرنل واقعاً کدام بخش الگوریتم (محاسبه، ذخیره یا هر دو) را صرفه‌جویی می‌کند.


منابع