روش کرنل

روش‌های کرنل یک کلاس قدرتمند از الگوریتم‌ها هستند که در یادگیری ماشین برای تحلیل الگو استفاده می‌شوند. آن‌ها به طور ویژه در حل مسائل غیرخطی با استفاده از طبقه‌بندی کننده‌های خطی موثر هستند. معروف ترین و پرکاربردترین الگوریتم در این کلاس، ماشین بردار پشتیبان است.

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

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

در الگوریتم‌های یادگیری ماشین سنتی، داده‌های خام باید قبل از استفاده برای تجزیه و تحلیل به شکل بردارهای ویژگی نمایش داده شوند. این فرآیند می‌تواند پیچیده و زمان‌بر باشد. با این حال، روش‌های کرنل رویکرد متفاوتی را ارائه می‌دهند و به جای تبدیل صریح داده‌ها، به یک تابع کرنل مشخص شده نیاز دارند.

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

با وجود این مزایا، روش‌های کرنل می‌توانند برای مجموعه داده‌های بزرگ، از نظر محاسباتی کند باشند. با این حال، تکنیک‌های پردازش موازی می‌توانند با توزیع محاسبات در چندین پردازنده یا ماشین به کاهش این مشکل کمک کنند.

الگوریتم‌هایی که می‌توانند از تکنیک کرنل استفاده کنند معمولا در روابط آن‌ها داشتن ضرب داخلی بین داده‌های ورودی برای محاسبات کافی است. به عنوان نمونه الگوریتم پرسپترون (perceptron) ٬ ماشین بردار پشتیبان (svm) و تحلیل مولفه‌های اصلی (PCA) می‌توانند از تکنیک کرنل برای انجام الگوریتم در بعد فضای کرنل استفاده کنند.

مقدمه‌ای بر ریاضی در تکنیک کرنل

برای ماشین بردار پشتیبانی که $\varphi$ آن به شکل زیر تعریف شود: $\varphi ([a_{1},a_{2}])=[a_{1},a_{2},{a_{1}}^{2}+{a_{2}}^{2}]$ تابع کرنلی به شکل زیر دارد: $k(x,y)=x.y+{\lVert x\rVert }^{2}{\lVert y\rVert }^{2}$ که در آن نقاط به یک فضای 3 بعدی نگاشت می‌شوند که در آن می‌توان یک ابر صفحه جداکننده را به راحتی پیدا کرد.

ترفند کرنل یک مفهوم اساسی در روش‌های کرنل است و از محاسبات بردن داده به بعد بالاتر جلوگیری می‌کند. این تکنیک، الگوریتم‌های یادگیری خطی را قادر می‌سازد تا توابع غیرخطی یا مرزهای تصمیم را مدیریت کنند. در این تکنیک، به ازای هر $\mathbf {x}$ و $\mathbf {x'}$ در فضای ورودی ${\mathcal {X}}$

توابع خاصی مثل

$k(\mathbf {x} ,\mathbf {x'} )$ را می‌توان به عنوان یک ضرب داخلی در فضای ${\mathcal {V}}$ بیان کرد.به تابع $k\colon {\mathcal {X}}\times {\mathcal {X}}\to \mathbb {R}$ یک تابع کرنل می‌گویند.

به طور ساده‌تر اگر تابع $\varphi \colon {\mathcal {X}}\to {\mathcal {V}}$ یک تابع در نظر بگیرید که هر $\mathbf {x}$ را به یک فضای دیگر می‌برد. تابع کرنل را می‌توان به صورت زیر بیان کرد:

$k(\mathbf {x} ,\mathbf {x'} )=\langle \varphi (\mathbf {x} ),\varphi (\mathbf {x'} )\rangle$

هر تابعی به عنوان یک تابع کرنل قابل‌ قبول نیست و قانون مرسر تابع‌های موردقبول $k(\mathbf {x} ,\mathbf {x'} )$ را تعیین می‌کند. این قانون بیان می‌کند یک تابع در صورتی یک کرنل معتبر است که ماتریس گِرم دیتا‌های ما یک ماتریس نیمه مثبت معین باشد. به این معنا که به ازای داده‌های $\{\mathbf {x} _{1},\dotsc ,\mathbf {x} _{n}\}$ ماتریس گرم را به صورت $K_{ij}=k(\mathbf {x} _{i},\mathbf {x} _{j})$ تعریف می‌کنیم. در صورتی که این ماتریس نیمه‌ مثبت معین باشد کرنل تعریف شده معتبر است.

توضیح غیررسمی بر روش کرنل

در یک روش کرنل معمولی، داده‌های آموزشی شامل جفت ورودی و برچسب‌های مربوطه هستند که به صورت

$(x_{i},y_{i})$ نشان داده می‌شوند. در اینجا $\mathbf {x} _{i}$ نمایانگر ویژگی‌های ورودی است (مثلاً مقادیر پیکسل در یک تصویر)، و $y_{i}$ نشان‌دهنده برچسب مربوطه (مثلاً برچسب کلاس تصویر) است. روش‌های هسته به جای یادگیری مجموعه‌ای از پارامترهای ثابت برای ویژگی‌ها، وزن $w_{i}$ را برای هر مثال آموزشی $\left(\mathbf {x} _{i},y_{i}\right)$ یاد می‌گیرند.

همانطور که می‌دانید برای پیش‌بینی ورودی‌های بدون برچسب، روش‌های کرنل از یک تابع شباهت استفاده می‌کنند که به عنوان کرنل نیز شناخته می‌شود که با $k\left(\mathbf {x} _{i},\mathbf {x} ^{\prime }\right)$ نشان داده می‌شود. این تابع شباهت بین ورودی بدون برچسب $\mathbf {x} ^{\prime }$ و هر یک از ورودی‌های آموزشی $\mathbf {x} _{i}$ را اندازه‌گیری می‌کند. تابع شباهت یک امتیاز شباهت بین دو ورودی را محاسبه می‌کند و یک نتیجه با ارزش واقعی را برمی‌گرداند.

طبقه‌بندی‌کننده دوتایی با استفاده از روش کرنل، برچسب ${\hat {y}}$ را برای ورودی جدیدی که برچسب ندارد $\mathbf {x} ^{\prime }$ را با توجه به مثبت یا منفی بودن علامت حاصل از جمع وزن‌دار شباهت‌ها پیش‌بینی می‌کند. وزن‌های $w_{i}$ ، توسط الگوریتم یادگیری بر اساس مثال‌های آموزشی تعیین می‌شوند. برچسب پیش بینی شده به صورت زیر محاسبه می‌شود:

${\hat {y}}=\operatorname {sgn} \sum _{i=1}^{n}w_{i}y_{i}k\left(\mathbf {x} _{i},\mathbf {x} ^{\prime }\right)$

در این معادله، ${\hat {y}}$ نشان‌دهنده برچسب پیش‌بینی‌شده برای ورودی بدون برچسب $\mathbf {x} ^{\prime }$ . تابع کرنل، $k:{\mathcal {X}}\times {\mathcal {X}}\rightarrow \mathbb {R}$ ، مسئول اندازه‌گیری شباهت بین هر جفت ورودی $\mathbf {x} ,\mathbf {x} ^{\prime }\in {\mathcal {X}}$ است. محدوده‌ی مجموع‌ها روی $n$ مثال‌ برچسب‌گذاری شده ${(\mathbf {x} _{i},y_{i})}_{i=1}^{n}$ در مجموعه داده آموزشی، با $y_{i}\in \{{-1,+1}\}$ است. نشان دهنده برچسب‌های کلاس است. وزن‌ها، $w_{i}$ ، وزن‌های مرتبط با هر مثال آموزشی هستند که توسط الگوریتم یادگیری تعیین می‌شوند. تابع علامت، $sgn$ ، مثبت یا منفی بودن طبقه‌بندی پیش‌بینی‌شده ${\hat {y}}$ را تعیین می‌کند.

کاربردها

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

در زمینه بیوانفورماتیک، روش‌های کرنل سهم قابل توجهی داشته اند. بیوانفورماتیک شامل تجزیه و تحلیل داده‌های بیولوژیکی مانند توالی‌های DNA، ساختارهای پروتئینی و پروفایل‌های بیان ژن است. روش‌های کرنل با موفقیت در کارهایی مانند طبقه‌بندی توالی DNA، که در آن شباهت بین توالی‌ها با استفاده از توابع هسته محاسبه می‌شود، استفاده شده‌اند. با ثبت الگوها و روابط زیربنایی در توالی‌های DNA، طبقه‌بندی‌کننده‌های مبتنی بر هسته می‌توانند به طور دقیق توالی‌ها را در دسته‌های مختلف طبقه‌بندی کنند و به تجزیه و تحلیل ژنوم و تشخیص بیماری کمک کنند. علاوه بر این، شیمی‌انفورماتیک، که بر تجزیه و تحلیل داده‌های شیمیایی تمرکز دارد، از روش‌های کرنل بهره برده است. رویکردهای مبتنی بر هسته در کارهایی مانند پیش‌بینی ویژگی‌های مولکولی، غربالگری مجازی و طراحی دارو مورد استفاده قرار گرفته‌اند که تجزیه و تحلیل کارآمد و دقیق ترکیبات شیمیایی را ممکن می‌سازد.

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

چند نمونه کرنل

• کرنل خطی

کرنل خطی یک تابع کرنل ساده و پرکاربرد است. که در این روش، ضرب داخلی بین بردارهای ویژگی ورودی محاسبه می‌کند و در نتیجه روابط خطی بین نقاط داده را ثبت می‌کند.

فرمول کرنل خطی به صورت زیر است:

$k(\mathbf {x} ,\mathbf {x} ^{\prime })=\mathbf {x} ^{\top }\mathbf {x} ^{\prime }$

در اینجا، $\mathbf {x} ,\mathbf {x} ^{\prime }$ بردارهای ویژگی ورودی را نشان می‌دهند. هسته خطی اساساً شباهت بین دو بردار را با حاصل ضرب نقطه‌ای آنها اندازه گیری می‌کند. به ویژه زمانی مفید است که داده‌ها را بتوان به خوبی با یک مرز تصمیم گیری خطی از هم جدا کرد.

• کرنل چندجمله‌ای

کرنل چند جمله‌ای، یک کرنل غیرخطی است که می‌تواند روابط پیچیده‌تری را بین نقاط داده ثبت کند. در اینجا، یکتابع چند جمله ای را بر حاصل ضرب نقطه ای بردارهای ویژگی اعمال می‌کند، که اجازه می‌دهد تا مرزهای تصمیم غیرخطی را تعیین کند.

فرمول کرنل چند جمله‌ای:

$k(\mathbf {x} ,\mathbf {x} ^{\prime })=(\gamma \mathbf {x} ^{\top }\mathbf {x} ^{\prime }+r)^{d}$

در این فرمول $r,d,\gamma$ ابرپارامترهای کرنل چند جمله ای هستند. $\gamma$ تأثیر حاصلضرب نقطه‌ای را کنترل می‌کند، $r$ یک جمله ثابت اختیاری است، و $d$ نشان‌دهنده درجه چند جمله‌ای است. با تنظیم این ابرپارامترها، کرنل چند جمله‌ای می‌تواند درجات مختلفی از غیرخطی بودن را در داده‌ها ثبت کند.

• کرنل گاوسی

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

فرمول کرنل گاوسی به صورت زیر است:

$k(\mathbf {x} ,\mathbf {x} ^{\prime })=\exp \left(-{\frac {|\mathbf {x} -\mathbf {x} ^{\prime }|^{2}}{2\sigma ^{2}}}\right)$

در این فرمول، $\mathbf {x}$ و $\mathbf {x} ^{\prime }$ بردارهای ویژگی هستند و $\sigma$ یک ابرپارامتر است که عرض کرنل را کنترل می‌کند. هسته گاوسی شباهت بیشتری (یعنی مقدار کرنل بزرگتر) به نقاط داده‌ای که به یکدیگر نزدیکتر هستند و شباهت کمتری را به نقاطی که از هم دورتر هستند اختصاص می‌دهد. این می‌تواند روابط پیچیده و غیرخطی بین نقاط داده را ثبت کند و معمولاً در برنامه‌هایی مانند تشخیص تصویر و خوشه‌بندی استفاده می‌شود.