جداسازی خطی
جداسازی خطی در هندسه اقلیدسی، یک ویژگی از یک جفت مجموعه از نقاط است. این مسئله به راحتی در دو بعد (صفحه اقلیدسی) با استفاده از یک سری نقاط به عنوان آبی رنگی و سری دیگر به عنوان رنگ قرمز رنگ مجسم می‌شود. این دو مجموعه به صورت خطی قابل‌تفکیک هستند اما زمانی که حداقل یک خط در صفحه وجود داشته باشد که تمام نقاط آبی در یکطرف خط و نقاط قرمز در طرف دیگر آن وجود داشته باشد. اگر هایپرپلن جایگزین خط شود، این ایده بلافاصله به فضاهای بزرگ اقلیدسی تعمیم داده می‌شود. در واقع مسئله تعیین این موضوع است که آیا یک جفت از مجموعه‌ها به صورت خطی قابل‌تفکیک هستند و اگر در چند ناحیه ایجاد شوند، یک هایپرپلن جداکننده را می‌یابند؟ در آمار و یادگیری ماشین، طبقه‌بندی انواع داده‌ها یک مسئله است که برای آن‌ها الگوریتم‌های مناسبی وجود دارد.
فرض کنید formula_1و formula_2دو مجموعه نقاط در فضای اقلیدسی formula_3بعدی باشند؛ بنابراین formula_1و formula_2جداسازی خطی هستند هر گاه formula_6عدد صحیح formula_7وجود داشته باشند که برای هر نقطه formula_8داشته باشیم formula_9و برای هر formula_10داشته باشیم formula_11جایی که formula_12، iامین جز از x است.
به طورکلی دو مجموعه به‌طور خطی قابل‌تفکیک نیستند وقتی که پوش محدب آن‌ها، مجموعه‌های مجزا است. (به صورت محاوره ای، همپوشانی ندارند)
سه نقطه غیر هم‌خطی در دو کلاس (+ و -) همیشه در دو بعد خطی قابل جدا شدن است. این مسئله با سه مثال در شکل زیر نشان داده می‌شود:
با این حال، تمام مجموعه ای از چهار نقطه، بدون سه هم‌خطی، در دو بعد خطی قابل جدا شدن نیستند. مثال زیر به دو خط مستقیم نیاز دارد پس قابل‌تفکیک به صورت خطی نیست: یک تابع بولی می‌تواند مقادیر ۰ یا ۱ را به هر راس یک ابر مکعب بولی در ابعاد n اختصاص دهد. راس‌ها با تقسیم طبیعی به دو دسته تقسیم می‌شوند. اگر این دو مجموعه از نقاط خطی جدا باشند، تابع بولی به صورت خطی جدا می‌شود. طبقه‌بندی آماری یک کار متداول در یادگیری ماشین است. فرض کنید برخی از نقاط داده، که هر کدام متعلق به یکی از دو مجموعه هستند، داده شده‌اند و ما می‌خواهیم مدلی را ایجاد کنیم که تصمیم‌گیری کند کدام یک از این دو مجموعه داده‌خواهدشد. در مورد ماشین‌های بردار پشتیبان، یک نقطه داده به عنوان بردار p بعدی مشاهده می‌شود؛ و ما می‌خواهیم بدانیم که آیا می‌توانیم این نقاط را با صفحه (p - ۱) بعدی ابر مکعب جدا کنیم یا نه. این مسئله را طبقه‌بندی‌کننده خطی می‌گویند. هایپرپلن‌های زیادی وجود دارند که ممکن است اطلاعات را (جداگانه) طبقه‌بندی کنند. یک انتخاب معقول به عنوان بهترین هایپرپلن، این است که نشان‌دهنده بزرگترین جدایی یا حاشیه بین دو مجموعه باشد؛ بنابراین ما هایپرپلن را انتخاب کردیم تا فاصله از آن به نزدیک‌ترین نقطه داده در هر طرف به حداکثر برسد. اگر چندین هایپرپلن موجود باشد آن را صفحه ابرماکزیمم حاشیه می‌گویند و طبقه‌بندی‌کننده خطی تعریف‌شده به عنوان یک طبقه‌بندی‌کننده حداکثر حاشیه شناخته می‌شود.
با توجه به برخی داده‌های آموزشی، formula_13یک مجموعه از n نقطه مختلف به شکل زیر است:
formula_14
جایی که formula_15۱ یا -۱ است و هر formula_16یک بردار حقیقی p بعدی است. ما می‌خواهیم ابر صفحه با بیش‌ترین حاشیه را پیدا کنیم که نقاط را به دو دسته formula_17و formula_18تقسیم می‌کند. هر هایپر پلن را می‌توان به صورت مجموعه ای از x به صورت زیر نوشت:
formula_19
جایی که formula_20در واقع ضرب نقطه‌ای و formula_21بردار نرمال هایپرپلن است. پارامتر formula_22مقدار افست از مبدأ در امتداد بردار نرمال formula_21را تعیین می‌کند. اگر داده‌های آموزشی به صورت خطی قابل‌تفکیک باشند، ما می‌توانیم دو هایپرپلن را به گونه‌ای انتخاب کنیم که داده‌ها را جدا کنند و هیچ نقطه بین آن‌ها وجود نداشته باشد.https://en.wikipedia.org/wiki/Linear_separability