선형분리성

유클리드 기하학에서 선형 분리성은 두 점 세트의 특성이다. 이것은 한 점 세트는 파란색으로, 다른 점 세트는 빨간색으로 생각함으로써 2차원(유클리드 평면)에서 가장 쉽게 시각화된다. 이 두 세트는 선의 한 쪽에 파란색 점이 모두 있고 다른 쪽에 빨간색 점이 모두 있는 평면에 최소한 하나의 선이 있으면 선형적으로 분리할 수 있다. 이 사상은 선이 하이퍼플레인(hyperplane)으로 대체되면 즉시 고차원 유클리드 공간에 일반화된다.

한 쌍의 집합이 선형적으로 분리 가능한지 여부를 판단하고 분리 하이퍼플레인(있는 경우)을 찾는 문제는 여러 영역에서 문제가 발생한다. 통계와 머신러닝에서 특정 유형의 데이터를 분류하는 것은 이 개념을 바탕으로 한 좋은 알고리즘이 존재하는 문제다.

수학적 정의

$X{\displaystyle {}_{}}$ ${\displaystyle {0\mathrm{}}_{}}$ ${\$과 ${\displaystyle {X\mathrm{}}_{}}$ 1 ${\$}을 n차원 유클리드 공간에서 두 점 세트로 한다$$. 만약 존재하는 그리고 X0{\displaystyle X_{0}}과 X1{\displaystyle X_{1}}1차원적으로만 분리 가능한 n+1실수를 w1, w2,.., wn, k{\displaystyle w_{1},w_{2},..,w_{n},k}, 그러한 모든 포인트=∈ X0{\displaystylex\in X_{0}}가 ∑ 나는 갈1nwix 나는입니다.;k${\displaystyle \sum _{i=1}^{n}w_{i}x_{i}>k}$ and every point ${\displaystyle x\in X_{1}}$ satisfies ${\displaystyle \sum _{i=1}^{n}w_{i}x_{i}<k}$, where ${\displaystyle x_{i}}$ is the ${\displaystyle i}$-th component of ${\displaystyle x}$.

동등하게, 두 세트는 각각의 볼록한 선체가 분리되었을 때 정확하게 선형적으로 분리될 수 있다(협업적으로, 겹치지 않는다).^{[citation needed]}

예

두 등급의 비협착점 3개('+'와 '-')는 항상 2차원에서 선형적으로 분리할 수 있다. 이는 다음 그림의 세 가지 예에 의해 설명된다(모든 '+' 경우는 표시되지 않지만, 모든 '-' 사례와 유사하다).

그러나 4개의 점, 즉 3개의 콜린어가 없는 모든 세트가 2차원에서 선형적으로 분리될 수 있는 것은 아니다. 다음 예제는 두 개의 직선이 필요하므로 선형적으로 분리할 수 없다.

시준되고 "+ ⋅⋅⋅ - ⋅⋅⋅ +" 형태의 세 지점도 선형적으로 분리할 수 없다는 점에 유의하십시오.

n개 변수에서 부울 함수의 선형 분리성

n개의 변수에 있는 부울 함수는 n개의 차원에서 부울 하이퍼큐브의 각 정점에 0 또는 1의 할당으로 생각할 수 있다. 이것은 정점을 자연스럽게 두 세트로 나눈다. 부울 함수는 이 두 점 세트가 선형적으로 분리될 수 있다면 선형적으로 분리할 수 있다고 한다. 고유 부울함수의 수는 $2{\displaystyle {\mathrm{}}^{}}$ ${\displaystyle {{2n}^{}}^{}}$ ${\$이며, 여기서 n은 함수에 전달된 변수 수입니다.^[1]

각 차원에^[2] 선형 분리 가능한 부울 함수 수(OEIS에서 순차 A000609)

변수 수	부울 함수	선형 분리 가능한 부울 함수
2	16	14
3	256	104
4	65536	1882
5	4294967296	94572
6	18446744073709552000	15028134
7	3.402823669 ×10^38	8378070864
8	1.157920892 ×10^77	17561539552946
9	1.340780792 ×10^154	144130531453121108

서포트 벡터 머신

데이터 분류는 기계학습에서 공통적인 작업이다. 각각 두 세트 중 하나에 속하는 일부 데이터 포인트가 주어진다고 가정하고, 우리는 새로운 데이터 포인트의 설정을 결정하는 모델을 만들고자 한다. 서포트 벡터 머신의 경우 데이터 포인트를 p-차원 벡터(p-1)로 보고, (p - 1)차원 하이퍼플레인(hyperplane)으로 그런 포인트를 분리할 수 있는지 알고 싶다. 이것을 선형 분류기라고 한다. 데이터를 분류(분리)할 수 있는 하이퍼플레인이 많다. 최고의 하이퍼플레인으로서 한 가지 합리적인 선택은 두 세트 사이의 가장 큰 분리 또는 마진을 나타내는 것이다. 그래서 우리는 하이퍼플레인으로부터 양쪽에서 가장 가까운 데이터 지점까지의 거리가 극대화되도록 하이퍼플레인(hyperplane)을 선택한다. 그러한 하이퍼플레인(hyperplane)이 존재할 경우, 최대 마진 하이퍼플레인(maximum-margin hyperplane)으로 알려져 있으며, 이 하이퍼플레인이 정의하는 선형 분류기는 최대 마진 분류기로 알려져 있다.

좀 더 공식적으로, 일부 교육 데이터 $D{\displaystyle \mathcal{}}$ ${\$ 폼의 n개 포인트 집합

${\displaystyle {\mathbf {x} _{i},y_{i}}\mid \mathb {x} _{i}\in \\{r}}\in \{-1,1\}\}\i}\{i=1}^{n}}}}}}}}}}$

여기서 y는_i 1 ${\displaystyle {}_{}}$ -1이며, 점 x $i{\displaystyle {\mathbf{}}_{}}$ ${\$이(가) 속하는$$ 세트를 나타낸다. 각 $x{\displaystyle {\mathbf{}}_{}}$ ${\displaystyle {}_{}}$ ${\$는 p-차원 실제 벡터다$$. ${\displaystyle {yi}_{}}$= ${\displaystyle 1}$ ${\displaystyle y_{i}=1$}을$($를) $갖는{\displaystyle {}_{}}$ 점을 y${\displaystyle {}_{}}$= -${\displaystyle 1}$ ${\displaystyle y_{i}-1$}을$($를) 갖는 점과 나누는$$ 최대 마진 하이퍼플레인을 찾고자 한다. 모든 하이퍼플레인은 $x{\displaystyle \mathbf{}}$ ${\$ {$x}}$을(으)를 만족하는 점 집합으로 기록할 수 있다$.$

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

여기서 $⋅{\displaystyle \cdot }$은(는) 도트 제품을 나타내고$$ w ${\$은(필수 정규화되지는 않음) 하이퍼플레인에 대한 정규 벡터를 $나타낸다{\displaystyle \mathbf{}}$. 매개 변수 $b{\displaystyle \frac{}{}}$ ${\displaystyle \frac{\Vert }{}}$ ${\displaystyle \frac{w\mathbf{}}{}}$ ${\displaystyle \frac{\Vert }{}}$ ${\$은(는) 정상 벡터 $w{\displaystyle \mathbf{}}$ ${\$을(를) 따라 원점에서 하이퍼 평면의 오프셋을 결정한다$.$

훈련 데이터가 선형적으로 분리될 수 있는 경우, 우리는 두 개의 하이퍼플레인을 그들이 데이터를 분리하고 그 사이에 포인트가 없는 방식으로 선택하고 나서 그들의 거리를 최대화하도록 할 수 있다.

참고 항목

• 하이퍼플레인 분리 정리
• 키르흐베르거의 정리
• 퍼셉트론
• Vapnik-Chervonenkis 치수

참조