جداسازی خطی

جداسازی خطی در هندسه اقلیدسی، یک ویژگی از یک جفت مجموعه از نقاط است. این مسئله به راحتی در دو بعد ( صفحه اقلیدسی ) با استفاده از یک سری نقاط به عنوان آبی رنگی و سری دیگر به عنوان رنگ قرمز رنگ مجسم می شود. این دو مجموعه به صورت خطی قابل تفکیک هستند اما زمانی که حداقل یک خط در صفحه وجود داشته باشد که تمام نقاط آبی در یکطرف خط و نقاط قرمز در طرف دیگر آن وجود داشته باشد. اگر هایپرپلن جایگزین خط شود، این ایده بلافاصله به فضاهای بزرگ اقلیدسی تعمیم داده می شود. در واقع مسئله تعیین این موضوع است که آیا یک جفت از مجموعه ها به صورت خطی قابل تفکیک هستند و اگر در چند ناحیه ایجاد شوند، یک هایپرپلن جداکننده را می یابند؟ در آمار و یادگیری ماشین، طبقه بندی انواع داده ها یک مسئله است که برای آن ها الگوریتم های مناسبی وجود دارد.
فرض کنید X 0 و X 1 دو مجموعه نقاط در فضای اقلیدسی n بعدی باشند؛ بنابراین X 0 و X 1 جداسازی خطی هستند هر گاه n + 1 عدد صحیح w 1 , w 2 , . . , w n , k وجود داشته باشند که برای هر نقطه x ∈ X 0 داشته باشیم ∑ i = 1 n w i x i > k و برای هر x ∈ X 1 داشته باشیم ∑ i = 1 n w i x i < k جایی که x i ، iامین جز از x است.
دو مجموعه از نقاط به طور خطی تفکیک پذیر هستند، اگر و تنها اگر پوش محدب این دو مجموعه از نقاط با یکدیگر اشتراک نداشته باشند.
سه نقطه غیر هم خطی در دو کلاس ( + و - ) همیشه در دو بعد خطی قابل جدا شدن است. این مسئله با سه مثال در شکل زیر نشان داده می شود:
با این حال، تمام مجموعه ای از چهار نقطه، بدون سه هم خطی، در دو بعد خطی قابل جدا شدن نیستند. مثال زیر به دو خط مستقیم نیاز دارد پس قابل تفکیک به صورت خطی نیست:
یک تابع بولی می تواند مقادیر ۰ یا ۱ را به هر راس یک ابر مکعب بولی در ابعاد n اختصاص دهد. راس ها با تقسیم طبیعی به دو دسته تقسیم می شوند. اگر این دو مجموعه از نقاط خطی جدا باشند، تابع بولی به صورت خطی جدا می شود.
طبقه بندی آماری یک کار متداول در یادگیری ماشین است. فرض کنید برخی از نقاط داده، که هر کدام متعلق به یکی از دو مجموعه هستند، داده شده اند و ما می خواهیم مدلی را ایجاد کنیم که تصمیم گیری کند کدام یک از این دو مجموعه داده خواهدشد. در مورد ماشین های بردار پشتیبان، یک نقطه داده به عنوان بردار p بعدی مشاهده می شود؛ و ما می خواهیم بدانیم که آیا می توانیم این نقاط را با صفحه ( p - ۱ ) بعدی ابر مکعب جدا کنیم یا نه. این مسئله را طبقه بندی کننده خطی می گویند. هایپرپلن های زیادی وجود دارند که ممکن است اطلاعات را ( جداگانه ) طبقه بندی کنند. یک انتخاب معقول به عنوان بهترین هایپرپلن، این است که نشان دهنده بزرگترین جدایی یا حاشیه بین دو مجموعه باشد؛ بنابراین ما هایپرپلن را انتخاب کردیم تا فاصله از آن به نزدیک ترین نقطه داده در هر طرف به حداکثر برسد. اگر چندین هایپرپلن موجود باشد آن را صفحه ابرماکزیمم حاشیه می گویند و طبقه بندی کننده خطی تعریف شده به عنوان یک طبقه بندی کننده حداکثر حاشیه شناخته می شود.