Classification

선형 분류에 대해서 배울 것.

선형회귀와 연결해보는 것도 재밌는 포인트가 될 거다

 

Classification (분류)

무엇인지 분류하는 문제예

수학적으로는 출력값 y는 유한한 집합 (예: 고양이, 개, 새 등) 중 하나

→ y ∈ 𝒴 (𝒴는 고정된 종류 집합)

 

반면, Regression (회귀)는 숫자를 예측하는 문제

비트코인 가격 그래프

→ 주어진 날짜에 따라 비트코인의 가격(숫자)을 예측하는 게 회귀 문제

 

선형 분류에서 대표적인 것은 Binary Classification 임.

Binary Classification (이진 분류)

분류 중에서도 딱 두 개만 분류하는 문제를 이진 분류

ex. 이메일이 스팸인지 아닌지, 사진이 강아지인지 고양이인지

 

중간에 있는 선이 결정 경계(decision boundary)

파란 점: 1번 클래스 (예: 강아지)

빨간 점: -1번 클래스 (예: 고양이)

 

0, -1 손실은 말 그대로 내가 분류를 데이터 포인트에 대해서 할 때 내가 정답을 맞혔는지, 못 맞혔는지를 카운팅 하는 함수

=> Linear Classifiers (선형 분류기)

우리가 쓸 모델은 직선 기반, 결과가 0보다 크면 +1, 작으면 -1로 판단한다.

 

Assumption: Linearly Separable

완벽하게 나눌 수 있는 직선이 반드시 존재한다고 가정함. 즉 100%로 정답을 맞추는 분류기가 하나는 존재한다

그래서 loss가 0인 모델이 존재한다는 뜻.

정말 딱 고양이와 강아지를 선 하나로 정확히 나눌 수 있다면, 완벽한 분류기 (loss = 0) 가 존재하는 상황

 

Perceptron이란?

Rosenblatt이 만든 머신러닝 알고리즘

주어진 데이터를 보고 두 개의 클래스로 분류하는 모델을 학습하는 것.

입력 데이터를 하나씩 보면서 예측해보고 틀렸을 때만 학습률을 조금씩 수정(업데이트)

 

Perceptron 장단점

1. 수렴(converge)함

선형으로 분리 가능한 경우, 언젠가는 틀리지 않게 됨

즉, 잘 나누는 선을 언젠가는 찾아낸다.

2. 엄청 간단함

수식도 어렵지 않고 계산도 가벼움

 

단점은 해결 불가능한 경우엔 멈추지 않음

선형으로 나눌 수 없는 데이터에서는 계속 틀리고, 계속 업데이트하면서 무한 반복

그리고 결국에는 수렴을 하는지, 무한 반복하는지를 미리 알 수 있는 방법이 없음.

이 알고리즘만 가지고는 '이 문제는 안 되는구나' 를 알아낼 방법이 없음

 

또 다른 해결법은 Linear Programming (선형계획법)을 이용한 분류가 있음.

얘는 아무 목적도 없음 (minimize 0) 그리고 모든 데이터를 잘 분류하기만 하면 된다 가 목표임.

 

xᵢ는 입력 데이터 (예: 사진에서 추출된 숫자 벡터)

yᵢ는 정답 레이블 (+1 또는 -1)

a와 b는 우리가 찾고 싶은 분류 직선의 기울기와 절편인데, 데이터가 선형으로 분리 가능한지 판단한다.

만약 해결 불가능하면 알려줌!

퍼셉트론은 끝없이 돌기만 하는데, 이건 "해가 없다"고 알려준다.

 

그러나 단점은 존재하는 정답 중에 어떤걸 줄지 모른다.

해가 여러개 나오는 경우 어떤 걸 선택해야 하는지에 대한 명확한 기준이 없다.

해가 여러 개라면?

지금 빨간 x와 파란점을 나누는 직선 2개가 있음.

검정색 선

초록색 점선

→ 둘 다 데이터를 정확하게 분류하지만, 위치가 다르다.

즉, "조건을 만족하는 직선"이 하나가 아닐 수도 있다는 뜻

 

yᵢ 값

🔴 빨간 점	×	클래스 1 (예: 음성, 고양이 등)	-1
🔵 파란 점	●	클래스 2 (예: 양성, 강아지 등)	+1

이럴 때는 마진을 계산해서 선택하자!

Margin은 분류 직선과 가장 가까운 데이터 간의 거리 마진이 크면,

직선과 데이터 사이 여유 공간이 많음 작은 흔들림에도 잘 견딘다.(더 튼튼한 모델)

반면 마진이 작으면, 분류 경계가 너무 빡빡하고 작은 노이즈에도 잘못 분류될 수 있다.

검정색 선, 초록색 선 모두 데이터를 잘 나누지만 검정색 선이 더 마진이 큼 (가까운 점과의 거리 넓음)

그래서 더 튼튼하고 안정적인 분류기는 검정색이다.

 

반면, 초록색 선은 빨간 점들에는 가깝지만 조금만 흔들면 오답이 나올 수 있다.

그런데 검정색 선은 양쪽 클래스 모두에게서 거리를 확보해서,

데이터가 좀 변하더라도 여전히 잘 분리할 가능성이 높음

 

이러한 Margin을 최대화하는 분류기를 찾는 문제를 Support Vector Machine (SVM) 이라고 흔히 부름.

SVM의 목표: 마진이 가장 넓은 선을 찾아라!

수식의 의미 : 모든 점이 직선으로부터 최소한 1만큼 떨어져 있으면서, 그 중에서도 가장 넓은 마진(‖a‖ 작음)을 가지는 직선을 찾자.

 

이 문제는 Convex Optimization (볼록 최적화) 문제

해가 존재하면 반드시 전역 최적해(global minimum)를 찾을 수 있다.

또한, 이 문제는 QCQP (Quadratically Constrained Quadratic Program)라는 수학 구조에 속한다.
Quadratical은 이차 제곱함수임. 즉, Linear Programming 이 쉬웠던 것처럼 애도 쉽게 계산할 수 있다. 

 

장점은 만약 데이터를 나눌 수 없다면, 이 문제는 '해 없음'이라고 정확하게 알려준다.

 

그래서 데이터가 선형적으로 분리 되지 않아서 이 데이터를 올바르게 분리하는 직선이 세상에 존재하지 않는 경우엔 어떻게 해야할까?

사진을 보면 빨간 점과 파란 점이 완벽히 분리되지 않음. 즉, 어떤 직선을 그어도 틀린 점이 생긴다.

문제 발생:

기존 SVM은 yᵢ(a⋅xᵢ + b) ≥ 1을 무조건 만족해야 하므로, 위와 같은 상황에서는 해가 없음!

= 모델이 학습 자체를 못 함.

 

완벽하게 나누는 건 불가능하니, 조금 틀리는 걸 허용하되

그만큼 penalty을 줘서 너무 많이 틀리진 않게 하자!

고양이/개 데이터가 섞여 있는 상황에서, 완벽 분리는 못 하지만 마진도 유지하고

오답은 패널티를 줘서 통제하는 모델을 만들 수 있다.

 

ξᵢ: 슬랙 변수 (마진을 얼마나 침범했는지 측정)

C: 오차에 대한 패널티

C ↑: 오차를 거의 허용하지 않음 (하드하게)

C ↓: 오차를 관대하게 허용함 (유연하게)

 

ξᵢ가 0이면 가장 좋음. 분류가 잘못 분류된 경우엔 그나마 ξᵢ를 적게 사용해야하는 조건을 뒤에 추가하는 수식임

Hinge Loss란? y = max(0, 1 - x)

간단히 말하면 "예측한 값이 1보다 작으면 손실이 생긴다" 라는 뜻임.

 

예를 들어서, 어떤 학생이 시험을 봤는데 0.8점 받았다.

1점에 못 미쳤으니까 손실(loss)이 0.2만큼 생김

그런데 어떤 학생이 1.5점을 받았다면? → 잘한 거니까 손실은 0!

정답과 예측값이 같고 충분히 margin(여유) 있으면 loss = 0

틀리거나 margin이 부족하면 손실 발생

 

왼쪽은 C값이 크고, 오른쪽은 C값이 작음.

이 데이터는 애초에 빨간색과 파란색을 완전히 분류 할 수 없는 데이터임.

C값이 크다고 하면 ξ에 해당하는 넘어 가는 데이터들에 대해서 ξ값을 가장 작게 만들려고 노력 하다 보니 이러한 선이 나온 것임.

그렇지만 대부분의 데이터를 올바르게 표현 하기에는 적절하지 않긴 함.

 

반대로 이상치가 발생 하더라도 나머지 전체 대부분의 데이터의 초점을 맞춘 적당한 C를 사용하면

왼쪽보다는 조금 더 빨간색과 파란색을 나누기에 적합해 보임. 반면에 빨간색 x는 그만큼 이상치가 선으로부터 멀어지게 됨.

 

그래서 이 Hinge Loss를 사용하면 더 간단하게 손실 함수를 표현할 수 있다.

 

Kernel

앞에서는 직선(Linear decision boundary) 으로 데이터를 분리하는 경우였는데,

현실에서는 이렇게 데이터가 직선으로는 못 나눠지는 경우가 많음.

🔵 파란 점: 클래스 A

❌ 빨간 점: 클래스 B

라고 할 때, 직선으로는 절대 분리 불가능함.

그래서 나온 해결책이

그렇다면 공간을 바꾸면 나눌 수 있지 않을까?

→ 그냥 x₁, x₂만 쓰지 말고, x₁², x₂², x₁x₂ 같은 복잡한 특징(특성) 도 추가해서 새로운 공간에서 직선으로 나눠보자!

 

우리가 원래 보던 벡터는:

x = (x₁, x₂)

그런데 이제 feature space를 확장해서 이렇게 바꿈:

x̃ = (x₁, x₂, x₁², x₂², x₁·x₂)

이렇게 하면 원래의 복잡한 곡선을 고차원 공간에서는 직선으로 표현할 수 있다.

 

만약에 커널을 더 많이 추가해주고 더 많은 표현 가능성을 보장 하고자 노력 한다면과 적합이 발생할 수도 있음.

Perceptron Algorithm

가장 단순한 분류 알고리즘. 사용하는 손실: 0-1 loss

(예측 틀리면 1, 맞추면 0)

문제점: 미분 불가능

→ Gradient Descent 같은 최적화 알고리즘 사용 불가

 

SVM (Support Vector Machine)

마찬가지로 0-1 loss 사용

문제점은 미분 불가

오직 경계에 가까운 점들만 신경 씀 (Support Vector만)

 

Soft-margin SVM

현실에서는 완벽하게 나뉘는 경우가 드물기 때문에 (해가 없는 경우)

좀 틀려도 괜찮게 유연하게 margin을 허용함.

이때 사용하는 게 Hinge Loss

이건 미분 가능하고, Convex Optimization(볼록 최적화) 으로 풀 수 있음

→ 머신러닝에서 아주 중요한 성질!