선형 구분 가능(linearly separable)은 주어진 데이터 집합을 하나의 초평면(선형 결정 경계)으로 완전히 구분할 수 있는지를 나타내는 개념으로, 주로 패턴 인식, 머신러닝, 신경망 이론 등에서 사용된다. 두 클래스(또는 그 이상의 클래스를 이진 구분으로 변환한 경우)의 점들이 n‑차원 특징 공간에서 서로 다른 두 반공간에 완전히 나뉘어 있으면, 그 데이터 집합은 선형 구분 가능하다고 한다.
1. 수학적 정의
- 특징 공간 : $ \mathbb{R}^d $ 로 표현되는 d 차원 실수 공간.
- 데이터 집합 : $ {(\mathbf{x}i, y_i)}{i=1}^{N} $ , 여기서 $ \mathbf{x}_i \in \mathbb{R}^d $ 은 특징 벡터, $ y_i \in {-1, +1} $ 은 클래스 레이블.
- 선형 결정 함수 :
$$ f(\mathbf{x}) = \mathbf{w}^\top \mathbf{x} + b $$ 여기서 $ \mathbf{w} \in \mathbb{R}^d $ 은 가중치 벡터, $ b \in \mathbb{R} $ 은 편향(바이어스)이다. - 선형 구분 가능 조건 :
$$ y_i \bigl(\mathbf{w}^\top \mathbf{x}_i + b\bigr) > 0 \quad \forall i = 1,\dots,N $$ 위 부등식이 만족되는 $(\mathbf{w}, b)$ 가 존재하면 데이터는 선형 구분 가능하다.
2. 기하학적 해석
- 초평면 : 위의 식 $ \mathbf{w}^\top \mathbf{x} + b = 0 $ 로 정의되는 차원 $d-1$ 의 평면.
- 반공간 : 초평면의 양쪽에 존재하는 두 개의 반공간. 클래스 ‘+1’은 한쪽 반공간, ‘-1’은 반대쪽 반공간에 위치한다.
- 마진 : 두 클래스 사이 가장 가까운 점과 초평면 사이의 거리. 마진이 양수이면 선형 구분이 가능하고, 마진이 0이면 경계에 데이터가 놓여 있다.
3. 주요 알고리즘과 연관성
| 알고리즘·모델 | 선형 구분 가능 여부와 관계 |
|---|---|
| 퍼셉트론(Perceptron) | 퍼셉트론 학습 규칙은 선형 구분 가능한 경우에만 가중치가 수렴한다. |
| 서포트 벡터 머신(SVM) | 선형 SVM은 마진을 최대화하는 초평면을 찾으며, 데이터가 선형 구분 가능하면 마진이 양수이다. 비선형 데이터는 커널 트릭을 이용해 고차원으로 매핑한다. |
| 로지스틱 회귀 | 선형 결정 경계를 가정하지만, 확률적 해석을 제공한다. 선형 구분 가능하지 않아도 최적화가 가능하지만 정확도는 감소할 수 있다. |
| K-최근접 이웃(KNN) | 비선형 모델이지만, 데이터가 선형 구분 가능하면 KNN 역시 높은 정확도를 보인다. |
4. 선형 구분 가능성 검증 방법
- 퍼셉트론 학습 시 수렴 확인
- 학습 반복이 일정 횟수 이내에 수렴(오류가 0)하면 선형 구분 가능.
- 선형 프로그램(LP) 혹은 이차계획법(QP) 활용
- 마진을 최대화하는 SVM 최적화 문제를 풀어 마진이 양수인지 확인.
- 시각화 (2‑차원 혹은 3‑차원 데이터)
- 데이터 포인트와 초평면을 직접 그려 구분 상태를 눈으로 검증.
- 핵심 정리 : Farkas’ Lemma 혹은 Separating Hyperplane Theorem을 이용한 이론적 증명.
5. 예시
| 사례 | 특징 공간 차원 | 구분 가능 여부 | 설명 |
|---|---|---|---|
| XOR 문제 | 2차원 | 불가능 | 두 클래스가 교차하여 선형 초평면으로 구분할 수 없음. |
| 두 원형 클러스터 (동일 반지름) | 2차원 | 가능 (원점 기준) | 원점 기준에 따라 선형 초평면(직선)으로 구분 가능. |
| MNIST 숫자 0 vs 1 | 784차원 (픽셀) | 실제는 불가능 (복잡한 패턴) | 비선형 변환(커널 SVM, CNN 등) 필요. |
6. 한계와 확장
- 비선형 데이터 : 선형 구분이 불가능한 경우, 커널 트릭, 다층 퍼셉트론(MLP), 컨볼루션 신경망(CNN) 등 비선형 모델이 필요.
- 노이즈와 오버랩 : 실제 데이터는 라벨 오류, 중첩 영역 등을 포함하여 완전한 선형 구분이 어려울 수 있다. 이때는 소프트 마진(SVM) 혹은 정규화(regularization) 기법을 적용한다.
- 고차원 현상 : 차원이 매우 높아질수록(특히 “고차원 희소 데이터”) 선형 구분 가능성이 높아질 수 있다(예: 텍스트 분류에서의 bag‑of‑words 모델).
7. 관련 용어
- 선형 결정 경계 (Linear Decision Boundary)
- 초평면 (Hyperplane)
- 마진 (Margin)
- 소프트 마진 SVM (Soft‑margin SVM)
- 커널 트릭 (Kernel Trick)
- 선형 독립성 (Linear Independence)
8. 참고 문헌 및 학술 자료
- Rosenblatt, F. (1958). The Perceptron: A Theory of Statistical Learning. Psychological Review.
- Vapnik, V. (1995). The Nature of Statistical Learning Theory. Springer.
- Bishop, C. M. (2006). Pattern Recognition and Machine Learning. Springer.
- Haykin, S. (2008). Neural Networks and Learning Machines. 3rd ed., Pearson.
- H. D. C. (1998). Convex Optimization – Chapter on separating hyperplanes.
요약
선형 구분 가능성은 데이터가 하나의 초평면으로 완전히 나뉘어지는지를 판단하는 근본적인 개념으로, 퍼셉트론과 선형 SVM 같은 고전적인 머신러닝 알고리즘의 이론적 기반을 제공한다. 하지만 실세계 데이터는 대체로 비선형성을 포함하고 있기 때문에, 선형 구분 가능 여부를 정확히 파악하고 필요에 따라 비선형 확장 기법을 적용하는 것이 핵심적인 단계가 된다.