On Linear Separability of the MNIST Handwritten Digits Dataset

이 논문은 MNIST 손글씨 숫자 데이터셋이 선형적으로 분리 가능한지에 대한 기존 논쟁을 해소하기 위해, 학습 및 테스트 집합의 쌍별 및 원대다 (one-vs-rest) 분리 가능성을 체계적으로 실증 분석한 결과를 보고합니다.

핵심

이 논문은 머신러닝의 가장 유명한 '시험지'인 MNIST(손글씨 숫자 데이터) 가 정말로 선 (Straight line) 하나로 모든 숫자를 깔끔하게 나눌 수 있는지, 아니면 그보다 훨씬 복잡한 일이 필요한지 확인한 연구입니다.

쉽게 말해, "손글씨 숫자 0 부터 9 까지, 한 번에 그은 직선으로 완벽하게 분류할 수 있을까?" 라는 질문에 대해 과학적으로 답을 찾은 이야기입니다.

이 연구의 핵심 내용을 일상적인 비유로 설명해 드릴게요.

---

1. 연구의 배경: "선으로 나눌 수 있을까?"

상상해 보세요. 흰 종이에 검은색으로 쓴 숫자 0, 1, 2... 9 가 섞여 있습니다. 우리는 이 종이를 한 번의 직선으로 자르면, 왼쪽에는 '0'만 있고 오른쪽에는 '1'만 남을 수 있을까요?

• 선형 분리 (Linear Separability): 데이터가 한 번의 직선 (또는 평면) 으로 깔끔하게 나뉘는 상태.
• 문제: MNIST 데이터는 7 만 장이나 되는 방대한 양이고, 숫자마다 손글씨 스타일이 다릅니다. 그래서 "분리될까?"에 대해 의견이 갈렸습니다. 어떤 이는 "너무 쉬워서 분리되겠지"라고 하고, 어떤 이는 "아니야, 너무 복잡해서 안 돼"라고 했습니다.

이 논문은 이 논란을 컴퓨터로 직접 실험해 보며 명확하게 결론을 내렸습니다.

2. 실험 방법: "완벽한 분리사"를 찾다

연구진은 컴퓨터에게 "이 숫자들과 저 숫자들을 완벽하게 한 줄로 나누어 봐"라고 시켰습니다.

• 비유: 마치 거대한 파티에 10 개의 다른 반 (0 반~9 반) 학생들이 섞여 있을 때, **한 명의 경비원 (직선)**이 "너희는 왼쪽으로, 너희는 오른쪽으로"라고 외치며 완벽하게 갈라놓을 수 있는지 확인하는 것과 같습니다.
• 도구: 연구진은 'CVXPY'라는 강력한 수학 도구를 사용했습니다. 이 도구는 "가능하면"이 아니라 "정말로 가능한가?"를 수학적으로 증명합니다.

3. 실험 결과: 상황에 따라 다르다!

연구진은 세 가지 상황을 테스트했습니다.

상황 A: 두 숫자끼리만 비교할 때 (Pairwise)

• 상황: "0 반 학생들"과 "1 반 학생들"만 모아서 한 줄로 나눌 수 있을까?
• 결과:
  • 성공: 0, 1, 6 같은 숫자는 다른 어떤 숫자와도 한 줄로 깔끔하게 나뉩니다. (예: 0 과 1 은 아주 다릅니다.)
  • 실패: 2 와 3, 3 과 8, 5 와 8 처럼 모양이 비슷한 숫자끼리는 한 줄로 나눌 수 없습니다. 마치 2 와 3 이 서로 손을 잡고 엉켜서 한 줄로 갈라놓을 수 없는 상황과 같습니다.
  • 특이점: **테스트 세트 (시험지)**는 샘플 수가 적어서 우연히 모든 숫자 쌍이 분리 가능한 것으로 나왔습니다. 하지만 이는 실제 능력을 증명하는 것이 아니라, "샘플이 적어서 우연히 잘 된 것"일 뿐입니다.

상황 B: 한 숫자 vs 나머지 9 개 (One-vs-Rest)

• 상황: "0 반 학생들"은 나머지 9 개 반 (1~9) 전체와 한 줄로 나눌 수 있을까?
• 결과: 절대 불가능합니다.
  • 훈련 데이터 (학습용) 에서는 어떤 숫자를 골라도 나머지 9 개와 완벽하게 나눌 수 있는 직선은 존재하지 않았습니다.
  • 비유: 0 반 학생을 나머지 9 개 반 학생들로부터 한 줄로 가려내려 하면, 0 과 아주 비슷한 6 이나 8 이 끼어들어와서 선을 무너뜨립니다.

4. 결론: "MNIST 는 분리 가능한가?"에 대한 정답

이 논문의 결론은 매우 흥미롭습니다. "상황에 따라 다릅니다" 라고 말하지만, 더 정확히는 다음과 같습니다.

1. 완벽한 분리 (선형 분리) 는 불가능합니다: 우리가 머신러닝을 배울 때 사용하는 **전체 학습 데이터 (Training Set)**를 기준으로 하면, 어떤 숫자도 나머지 9 개와 완벽하게 한 줄로 나눌 수 없습니다. 즉, "MNIST 는 선형적으로 분리되지 않는다"는 말이 맞습니다.
2. 왜 그렇게 복잡할까? 숫자 2 와 3 이나 5 와 8 처럼 손글씨 스타일이 너무 비슷해서, 단순한 직선으로는 구별할 수 없는 '꼬인 매듭'들이 있기 때문입니다.
3. 우리가 왜 잘 분류할 수 있을까? 우리가 MNIST 에서 99% 이상의 정확도를 내는 이유는 **단순한 직선 (선형 모델)**만 쓰는 게 아니라, 곡선을 그리거나 **깊은 신경망 (딥러닝)**을 써서 복잡한 모양을 이해하기 때문입니다.

5. 요약: 일상적인 비유로 정리

• MNIST 데이터 = 10 개의 다른 반 학생들이 섞여 있는 거대한 교실.
• 선형 분리 = 교실 중앙에 한 번의 직선을 그어 반을 나누는 것.
• 연구 결과:
  • 0 반 vs 1 반만 보면? 직선으로 나눌 수 있음. (쉬움)
  • 2 반 vs 3 반만 보면? 직선으로 나눌 수 없음. (매우 어려움, 서로 섞임)
  • 0 반 vs (나머지 9 반 전체)? 직선으로 나눌 수 없음. (불가능)

결론적으로:
"MNIST 는 단순한 직선 하나로 모든 숫자를 완벽하게 분류할 수 있는 데이터가 아닙니다." 이 논문은 이 사실을 수학적으로 증명하여, 머신러닝을 공부할 때 **"왜 우리는 단순한 선만으로는 안 되고, 더 복잡한 모델 (딥러닝) 이 필요한가?"**에 대한 근본적인 이유를 알려주었습니다.

이 연구는 "MNIST 는 쉽다"는 오해를 깨뜨리고, 데이터의 복잡성을 정확히 이해하는 데 중요한 기준이 되었습니다.

기술 요약

MNIST 손글씨 숫자 데이터셋의 선형 분할 가능성에 대한 기술적 요약

본 논문은 1990 년대 후반 Yann LeCun 등에 의해 개발된 MNIST 데이터셋이 **선형 분할 가능 (Linearly Separable)**한지 여부에 대한 명확한 실증적 분석을 제시합니다. 오랫동안 논쟁의 대상이 되어온 이 질문에 대해, 저자는 훈련 세트, 테스트 세트, 그리고 두 세트를 결합한 전체 데이터셋에 대해 쌍별 (Pairwise) 및 일대다 (One-vs-Rest) 분할 가능성 실험을 수행하여 결론을 내렸습니다.

1. 문제 제기 (Problem)

MNIST 데이터셋은 패턴 인식 및 이미지 분류 모델 평가의 표준 벤치마크로 널리 사용되지만, 데이터셋이 선형 분할 가능한지에 대한 명확한 답은 오랫동안 부재했습니다.

• 모순된 주장: 과학적 문헌과 비공식적 출처 간에 "MNIST 는 선형 분할 가능하다"는 주장과 "선형 분할 불가능하다"는 주장이 혼재되어 있습니다.
• 선행 연구의 한계: 일부 연구는 특정 숫자 쌍 (예: 0 대 9) 만을 테스트하거나, 축소된 데이터셋을 사용하거나, 분할 가능성을 직접적으로 증명하지 못했습니다.
• 핵심 질문: 70,000 개의 28x28 픽셀 회색조 이미지 (10 개 클래스) 로 구성된 MNIST 데이터는 단일 선형 결정 경계 (Separating Hyperplane) 로 완전히 분리될 수 있는가?

2. 방법론 (Methodology)

저자는 선형 분할 가능성을 판단하기 위해 선형 계획법 (Linear Programming, LP) 기반의 접근 방식을 채택했습니다.

• 수학적 모델링:
  • 주어진 데이터 $\{x_i\}$와 레이블 $y_i \in \{-1, 1\}$에 대해, $w^T x_i + b \ge 1$ (양수 클래스) 및 $w^T x_i + b \le -1$ (음수 클래스) 을 만족하는 가중치 벡터 $w$와 편향 $b$가 존재하는지 확인하는 **실현 가능성 문제 (Feasibility Problem)**로 정의했습니다.
  • 목적 함수는 상수 (0) 로 설정하여, 해가 존재하는지 여부만 판단하도록 구성했습니다.
• 도구 및 환경:
  • CVXPY (버전 1.6.7): 오픈 소스 볼록 최적화 라이브러리를 사용하여 문제를 모델링하고 해결했습니다.
  • 솔버: CLARABEL 솔버를 자동으로 선택하여 사용했습니다.
  • 하드웨어: Google Colab 환경 (T4 GPU, Intel Xeon CPU) 에서 실행되었으나, 사용된 CVXPY 버전의 제한으로 GPU 가속은 적용되지 않았습니다.
• 실험 설계:
  1. 쌍별 (Pairwise) 분할: 10 개의 숫자 중 2 개를 선택하여 서로 분리 가능한지 확인 (총 45 가지 조합).
  2. 일대다 (One-vs-Rest) 분할: 특정 숫자 1 개를 양수 클래스로, 나머지 9 개 숫자를 모두 음수 클래스로 설정하여 분리 가능한지 확인 (총 10 가지 경우).
  3. 데이터셋 구분: 훈련 세트 (60,000 개), 테스트 세트 (10,000 개), 그리고 두 세트를 합친 전체 데이터셋 (70,000 개) 에 대해 각각 실험을 수행했습니다.

3. 주요 결과 (Key Results)

3.1 쌍별 (Pairwise) 선형 분할 가능성

• 훈련 세트:
  • 분할 가능: 숫자 0, 1, 6 은 다른 모든 숫자와 쌍별 비교에서 선형 분할이 가능했습니다.
  • 분할 불가: 7 개의 숫자 쌍 (2-3, 2-8, 3-5, 3-8, 4-9, 5-8, 7-9) 은 선형 분할이 불가능했습니다. 특히 숫자 8 은 2, 3, 5 와의 비교에서 분할이 불가능하여 가장 구별하기 어려운 숫자로 나타났습니다.
• 테스트 세트:
  • 모든 숫자 쌍 (45 가지 조합) 이 선형 분할 가능했습니다. 이는 테스트 세트의 샘플 크기가 상대적으로 작아 (각 클래스 약 1,000 개) 분할이 용이했기 때문입니다.
• 결합 세트 (훈련 + 테스트):
  • 훈련 세트의 결과와 동일하게, 일부 숫자 쌍은 분할 불가능했습니다. 이는 훈련 데이터로 학습된 선형 결정 경계가 테스트 데이터에서도 완벽하게 작동할 수 있음을 시사합니다.

3.2 일대다 (One-vs-Rest) 선형 분할 가능성

• 훈련 세트:
  • 모든 숫자 (0~9) 에 대해 분할 불가능했습니다. 즉, 어떤 한 숫자를 나머지 9 개 숫자 전체와 선형으로 분리하는 것은 불가능합니다.
  • 특히, 쌍별 실험에서 분할 가능했던 0, 1, 6 도 일대다 상황에서는 분할이 불가능함이 확인되었습니다.
• 테스트 세트:
  • 일부 숫자 (0, 1, 2, 3, 4, 6, 7) 는 일대다 분할이 가능했으나, 이는 작은 샘플 크기로 인한 결과로 보이며 훈련 세트의 비선형성으로 인해 전체 데이터셋의 특성을 대표한다고 보기 어렵습니다.

3.3 성능 (Execution Time)

• 쌍별 테스트: 훈련 세트 기준 분할 가능한 경우 6.413.6 초, 불가능한 경우 15.924.7 초 소요.
• 일대다 테스트: 훈련 세트 기준 89~209 초 소요 (데이터 양 증가로 인해 시간 증가).
• 비교: Zhong et al. [6] 의 이전 연구 결과 (Matlab 환경) 와 비교 시, CVXPY 를 사용한 본 연구는 약 4~8 배 빠른 성능을 보였습니다.

4. 주요 기여 및 결론 (Contributions & Conclusions)

주요 기여

1. 포괄적 실증 분석: MNIST 데이터셋의 선형 분할 가능성에 대해 쌍별 및 일대다, 훈련/테스트/결합 세트를 모두 아우르는 체계적인 실험을 수행했습니다.
2. 명확한 결론 도출: 기존의 모호한 주장들을 반박하고, 데이터셋의 구성 (훈련 vs 테스트) 과 비교 방식 (쌍별 vs 일대다) 에 따라 결과가 달라짐을 명확히 증명했습니다.
3. 벤치마크 제공: CVXPY 를 활용한 효율적인 실험 방법론과 실행 시간 데이터를 제공하여 향후 연구의 기준 (Baseline) 을 마련했습니다.

결론

• "MNIST 는 선형 분할 가능하다"는 주장은 틀렸습니다: 전체 데이터셋 (훈련 세트 포함) 을 기준으로 볼 때, 특히 일대다 (One-vs-Rest) 관점에서는 전체적으로 선형 분할 불가능합니다.
• "MNIST 는 선형 분할 불가능하다"는 주장도 절대적이지 않습니다: 테스트 세트의 경우 쌍별 (Pairwise) 비교에서는 완전히 선형 분할 가능합니다.
• 최종 요약:
  • 훈련 세트 (및 전체 데이터셋): 일대다 분할 불가 (Non-separable).
  • 테스트 세트: 쌍별 분할 가능 (Separable).
  • 의미: MNIST 데이터셋은 복잡한 구조를 가지고 있어 (특히 8, 2, 3, 5 등 유사한 숫자 간), 단일 선형 결정 경계로 모든 클래스를 구분하는 것은 불가능하지만, 특정 조건 (작은 샘플, 특정 쌍 비교) 하에서는 분할이 가능할 수 있음을 보여줍니다.

이 연구는 머신러닝 모델 설계 시 선형 모델의 한계를 이해하고, 비선형 모델 (CNN 등) 이 왜 MNIST 에서 높은 성능을 보이는지에 대한 이론적 근거를 제공합니다.