جداسازی خطی

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

## تعریف ریاضی
فرض کنید X_{0}و X_{1}دو مجموعه نقاط در فضای اقلیدسی nبعدی باشند؛ بنابراین X_{0}و X_{1}جداسازی خطی هستند هر گاه n+1عدد صحیح w_{1}, w_{2},..,w_{n}, kوجود داشته باشند که برای هر نقطه x \in X_{0}داشته باشیم \sum^{n}_{i=1} w_{i}x_{i} > kو برای هر x \in X_{1}داشته باشیم \sum^{n}_{i=1} w_{i}x_{i} جایی که x_{i}، iامین جز از x است.

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

## مثال‌ها
سه نقطه غیر هم‌خطی در دو کلاس (+ و -) همیشه در دو بعد خطی قابل جدا شدن است. این مسئله با سه مثال در شکل زیر نشان داده می‌شود:

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

## تفکیک خطی توابع بولی در N متغیر
یک تابع بولی می‌تواند مقادیر ۰ یا ۱ را به هر راس یک ابر مکعب بولی در ابعاد n اختصاص دهد. راس‌ها با تقسیم طبیعی به دو دسته تقسیم می‌شوند. اگر این دو مجموعه از نقاط خطی جدا باشند، تابع بولی به صورت خطی جدا می‌شود.

## ماشین‌های بردار پشتیبانی
طبقه‌بندی آماری یک کار متداول در یادگیری ماشین است. فرض کنید برخی از نقاط داده، که هر کدام متعلق به یکی از دو مجموعه هستند، داده شده‌اند و ما می‌خواهیم مدلی را ایجاد کنیم که تصمیم‌گیری کند کدام یک از این دو مجموعه داده‌خواهدشد. در مورد ماشین‌های بردار پشتیبان، یک نقطه داده به عنوان بردار p بعدی مشاهده می‌شود؛ و ما می‌خواهیم بدانیم که آیا می‌توانیم این نقاط را با صفحه (p - ۱) بعدی ابر مکعب جدا کنیم یا نه. این مسئله را طبقه‌بندی‌کننده خطی می‌گویند. هایپرپلن‌های زیادی وجود دارند که ممکن است اطلاعات را (جداگانه) طبقه‌بندی کنند. یک انتخاب معقول به عنوان بهترین هایپرپلن، این است که نشان‌دهنده بزرگترین جدایی یا حاشیه بین دو مجموعه باشد؛ بنابراین ما هایپرپلن را انتخاب کردیم تا فاصله از آن به نزدیک‌ترین نقطه داده در هر طرف به حداکثر برسد. اگر چندین هایپرپلن موجود باشد آن را صفحه ابرماکزیمم حاشیه می‌گویند و طبقه‌بندی‌کننده خطی تعریف‌شده به عنوان یک طبقه‌بندی‌کننده حداکثر حاشیه شناخته می‌شود.

با توجه به برخی داده‌های آموزشی، \mathcal{D}یک مجموعه از n نقطه مختلف به شکل زیر است:

\mathcal{D} = \left\{ (\mathbf{x}_i, y_i)\mid\mathbf{x}_i \in \mathbb{R}^p,\, y_i \in \{-1,1\}\right\}_{i=1}^n

جایی که y_i۱ یا -۱ است و هر x_iیک بردار حقیقی p بعدی است. ما می‌خواهیم ابر صفحه با بیش‌ترین حاشیه را پیدا کنیم که نقاط را به دو دسته y=1و y=-1تقسیم می‌کند. هر هایپر پلن را می‌توان به صورت مجموعه ای از x به صورت زیر نوشت:

\mathbf{w}\cdot\mathbf{x} - b=0,

جایی که \cdotدر واقع ضرب نقطه‌ای و {\mathbf{w}}بردار نرمال هایپرپلن است. پارامتر \tfrac{b}{\|\mathbf{w}\|}مقدار افست از مبدأ در امتداد بردار نرمال {\mathbf{w}}را تعیین می‌کند. اگر داده‌های آموزشی به صورت خطی قابل‌تفکیک باشند، ما می‌توانیم دو هایپرپلن را به گونه‌ای انتخاب کنیم که داده‌ها را جدا کنند و هیچ نقطه بین آن‌ها وجود نداشته باشد.

## جستارهای وابسته
* پرسپترون
* بعد VC

## منابع

* https://engineering.purdue.edu/ChanGroup/ECE595/files/Lecture06_separable.pdf
* https://en.wikipedia.org/wiki/Linear_separability

رده:آنالیز محدب
رده:مقاله‌های ایجادشده توسط ایجادگر
رده:هندسه
رده:یادگیری ماشین