선형 구분 가능
선형 구분 가능(線形區分可能, linearly separable)은 다차원 공간에 분포한 두 집단의 점들이 하나의 초평면(hyperplane)으로 완전히 분리될 수 있는 성질을 의미한다. 이 개념은 유클리드 기하학에서 비롯되었으며, 통계학과 기계학습 분야에서 특히 중요한 의미를 가진다.
정의
2차원 유클리드 평면을 예로 들면, 두 집단의 점들이 각각 파란색과 빨간색으로 구분되어 있을 때, 하나의 직선을 그어 모든 파란색 점이 직선의 한쪽에, 모든 빨간색 점이 반대쪽에 놓이게 할 수 있다면 이 두 집단은 선형 구분 가능하다고 한다. 이 개념은 고차원 공간으로 일반화되는데, 이 경우 직선 대신 초평면(hyperplane)을 사용한다.
수학적으로 표현하면, d차원 유클리드 공간 ℝ^d에 속하는 두 점집합 X와 Y가 있다고 할 때, X의 모든 점이 wᵀx + k > 0을 만족하고 Y의 모든 점이 wᵀy + k < 0을 만족하는 법선벡터 w와 스칼라 오프셋 k가 존재한다면, X와 Y는 선형 구분 가능하다고 정의한다. 여기서 wᵀz + k = 0이 분리 초평면을 나타낸다.
또한, 두 집합이 선형 구분 가능하다는 것은 두 집합의 볼록 껍질(convex hull)이 서로 겹치지 않는다는 것과 동치이다.
기계학습에서의 의의
선형 구분 가능성은 기계학습의 분류 문제에서 핵심적인 판단 기준이 된다. 데이터가 선형 구분 가능하면 선형 분류기(linear classifier)만으로도 두 클래스를 완전히 분리할 수 있지만, 그렇지 않은 경우에는 비선형 구조가 필요하다.
대표적인 예로 XOR 문제가 있다. XOR 함수의 입력값을 2차원 평면에 배치하면, 이 문제는 하나의 직선으로 두 클래스를 분리할 수 없다. 이는 단층 퍼셉트론이 XOR 문제를 해결하지 못하는 이유로 잘 알려져 있으며, 이 한계를 극복하기 위해 다층 퍼셉트론과 같은 비선형 모델이 도입되었다.
서포트 벡터 머신과의 관계
서포트 벡터 머신(SVM)에서도 선형 구분 가능성의 개념이 중요하게 사용된다. 데이터가 선형 구분 가능한 경우, 두 클래스를 분리하는 초평면 중에서 두 집합 사이의 마진(margin)을 최대화하는 최대 마진 초평면(maximum-margin hyperplane)을 찾는 것이 목표가 된다. 이렇게 찾은 선형 분류기를 최대 마진 분류기라고 한다.
부울 함수와의 관계
선형 구분 가능성은 부울 함수의 성질을 분석하는 데에도 적용된다. n변수 부울 함수는 n차원 부울 하이퍼큐브의 각 꼭짓점에 0 또는 1의 값을 할당한 것으로 볼 수 있으며, 이 할당에 따라 꼭짓점들이 두 집합으로 나뉜다. 이 두 집합이 선형 구분 가능하면 해당 부울 함수를 선형 구분 가능하다고 하며, 이러한 함수는 선형 임계 논리(linear threshold logic) 또는 퍼셉트론이라고도 불린다.
모든 부울 함수가 선형 구분 가능한 것은 아니다. 예를 들어 2변수 부울 함수 16개 중 14개만이 선형 구분 가능하며, 3변수 부울 함수 256개 중에는 104개만이 선형 구분 가능하다. n = 9까지의 경우에 대해서만 선형 구분 가능한 부울 함수의 정확한 개수가 알려져 있다. 주어진 부울 함수가 선형 구분 가능한지 판정하는 문제는 일반적으로 계산 복잡도가 높은 것으로 알려져 있다.
참고 문헌
- Boyd, Stephen; Vandenberghe, Lieven (2004). Convex Optimization. Cambridge University Press.
- Russell, Stuart J.; Norvig, Peter (2016). Artificial Intelligence: A Modern Approach (3rd ed.). Boston.
- Muroga, Saburo (1971). Threshold Logic and Its Applications. Wiley-Interscience.
- Šíma, Jiří; Orponen, Pekka (2003). "General-Purpose Computation with Neural Networks: A Survey of Complexity Theoretic Results". Neural Computation.
