جداسازی خطی

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

تعریف ریاضی

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

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

مثال‌ها

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

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

تفکیک خطی توابع بولی در N متغیر

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

Number of linearly separable Boolean functions in each dimension

Number of variables	Linearly separable Boolean functions
۲	۱۴
۳	۱۰۴
۴	۱۸۸۲
۵	۹۴۵۷۲
۶	۱۵۰۲۸۱۳۴
۷	۸۳۷۸۰۷۰۸۶۴
۸	۱۷۵۶۱۵۳۹۵۵۲۹۴۶
۹	۱۴۴۱۳۰۵۳۱۴۵۳۱۲۱۱۰۸

ماشین‌های بردار پشتیبانی

طبقه‌بندی آماری یک کار متداول در یادگیری ماشین است. فرض کنید برخی از نقاط داده، که هر کدام متعلق به یکی از دو مجموعه هستند، داده شده‌اند و ما می‌خواهیم مدلی را ایجاد کنیم که تصمیم‌گیری کند کدام یک از این دو مجموعه داده‌خواهدشد. در مورد ماشین‌های بردار پشتیبان، یک نقطه داده به عنوان بردار 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