CS229 Weighted Least Squares, Logistic regression, Newton's Method | Lecture 3

모든 강의 자료와 영상은 공개된 해당 링크들을 통해서 학습하고 있다.

강의자료: https://cs229.stanford.edu/syllabus-spring2022.html

강의 영상: https://www.youtube.com/playlist?list=PLoROMvodv4rNyWOpJg_Yh4NSqI4Z4vOYy

3강 슬라이드: https://drive.google.com/file/d/1G7vMGP2OE4Qd-MT6Uc1cffg_pYeD77aq/view

 

---

 

 

1. 선형회귀 확률적 해석

 

선형회귀에서 오차(Error)를 '제곱'해서 최소화하는 이유

 

선형회귀에서는 실제값 $ y $가 예측값 $ \theta^T x $에 오차항 $ \epsilon $이 더해진 형태라고 본다.

$ y = \theta^T x + \epsilon $

여기서 $ \epsilon $은 모델이 설명하지 못한 요인이나 랜덤 노이즈를 의미한다. 즉, i번째 데이터에 대해 오차는 다음과 같이 쓸 수 있다.

$ \epsilon^{(i)} = y^{(i)} - \theta^T x^{(i)} $

만약 오차를 단순히 더하면 양수 오차와 음수 오차가 서로 상쇄될 수 있다. 그래서 오차의 크기를 제대로 반영하기 위해 오차를 제곱한다.

$ \left(y^{(i)} - \theta^T x^{(i)}\right)^2 $

오차를 제곱하면 모든 오차가 양수가 되고, 큰 오차에는 더 큰 벌점이 주어진다. 따라서 선형회귀에서는 전체 데이터에 대한 제곱 오차의 합을 최소화하는 방향으로 $ \theta $를 찾는다.

$ \frac{1}{2}\sum_{i=1}^{n}\left(y^{(i)} - \theta^T x^{(i)}\right)^2 $

이 방식은 단순히 오차 상쇄를 막기 위한 계산 트릭만은 아니다. 선형회귀에서는 보통 오차항이 평균 0을 중심으로 독립적으로 분포한다고 가정한다.

$ \epsilon^{(i)} \sim \mathcal{N}(0, \sigma^2) $

이는 작은 오차는 자주 발생하고, 큰 오차는 상대적으로 드물게 발생한다는 직관과 잘 맞는다. 이 가정에 따르면 $ x^{(i)} $가 주어졌을 때 $ y^{(i)} $는 평균이 $ \theta^T x^{(i)} $인 정규분포를 따른다.

$ y^{(i)} \mid x^{(i)};\theta \sim \mathcal{N}(\theta^T x^{(i)}, \sigma^2) $

이제 주어진 데이터를 가장 그럴듯하게 설명하는 $ \theta $를 찾기 위해 likelihood를 최대화하면, 결과적으로 제곱 오차의 합을 최소화하는 문제와 같아진다.

$ \arg\max_\theta L(\theta) = \arg\min_\theta \frac{1}{2}\sum_{i=1}^{n}\left(y^{(i)} - \theta^T x^{(i)}\right)^2 $

따라서 선형회귀에서 오차를 제곱해 최소화하는 것은 오차가 정규분포를 따른다는 확률적 가정에서 자연스럽게 나오는 방법이다.

 

2.  Classification

집값을 예측하는 '회귀(Regression)'와 달리,

'분류(Classification)'는 데이터가 어느 카테고리에 속하는지(예: 스팸 메일인가 아닌가, 종양이 악성인가 양성인가)를 맞추는 문제이다.

$ y \in \{0, 1\} $

$ h_\theta(x) = \theta^T x $

하지만 선형 회귀는 분류 문제에 적합하지 않다.  
첫째, 예측값이 0보다 작거나 1보다 커질 수 있기 때문에 확률로 해석하기 어렵다.  
둘째, 일부 극단적인 데이터에 의해 직선이 크게 흔들리면 분류 기준도 같이 바뀔 수 있다.

따라서 분류 문제에서는 예측값을 0과 1 사이로 제한할 수 있는 새로운 모델이 필요하다.

3. Logistic Regression and Sigmoid

로지스틱 회귀(Logistic Regression)는 이름에는 회귀가 들어가지만, 실제로는 이진 분류를 위한 모델이다.  
핵심 아이디어는 선형 결합 $ \theta^T x $를 그대로 출력하지 않고, 시그모이드 함수에 통과시키는 것이다.

시그모이드 함수

$ g(z) = \frac{1}{1 + e^{-z}} $

어떤 실수 $ z $가 들어와도 결과를 항상 0과 1 사이의 값으로 바꾼다.

$ z \to \infty $ 이면 $ g(z) \to 1 $

$ z = 0 $ 이면 $ g(z) = 0.5 $

$ z \to -\infty $ 이면 $ g(z) \to 0 $

 

따라서 로지스틱 회귀의 예측 함수는 다음과 같이 정의된다.

$ h_\theta(x) = g(\theta^T x) = \frac{1}{1 + e^{-\theta^T x}} $

이 값은 입력 $ x $가 positive class, 즉 $ y = 1 $에 속할 확률로 해석할 수 있다.

$ h_\theta(x) = P(y = 1 \mid x; \theta) $

$ 1 - h_\theta(x) = P(y = 0 \mid x; \theta) $

그래서 일반적으로 다음 기준으로 분류한다.

$ h_\theta(x) \ge 0.5 \Rightarrow y = 1 $

$ h_\theta(x) < 0.5 \Rightarrow y = 0 $

 

모델의 파라미터 $ \theta $는 주어진 데이터를 가장 그럴듯하게 설명하도록 찾는다.  
이를 위해 하나의 데이터에 대한 확률을 다음처럼 쓸 수 있다.

$ P(y \mid x; \theta) = \left(h_\theta(x)\right)^y \left(1 - h_\theta(x)\right)^{1-y} $

이 식은 $ y=1 $이면 $ h_\theta(x) $만 남고, $ y=0 $이면 $ 1-h_\theta(x) $만 남도록 만든 표현이다.

전체 데이터에 대해 likelihood를 만들고 로그를 취하면 로그 우도 함수가 된다.

$ \ell(\theta) = \sum_{i=1}^{n} \left[ y^{(i)}\log h_\theta(x^{(i)}) + (1-y^{(i)})\log(1-h_\theta(x^{(i)})) \right] $

로지스틱 회귀는 이 로그 우도 함수가 최대가 되도록 $ \theta $를 학습한다.  
반대로 이 식에 마이너스를 붙여 최소화하면 Cross-Entropy Loss 또는 Log Loss가 된다.

 

4. Newton's method

로지스틱 회귀에서는 로그 우도 함수 $ L(\theta) $가 최대가 되는 파라미터 $ \theta $를 찾아야한다.

$ \theta \in \mathbb{R}^d $

$ L: \mathbb{R}^d \to \mathbb{R} $

즉, $ \theta $는 하나의 숫자가 아니라 $ d $차원 벡터이고, 로그 우도 함수 $ L(\theta) $는 그 벡터를 입력받아 하나의 실수 값을 출력한다.

최댓값이 되는 지점에서는 기울기가 0이 된다.

$ \nabla_\theta L(\theta) = 0 $

따라서 뉴턴 메서드는 로그 우도 함수 자체를 바로 푸는 것이 아니라, 그 기울기 함수의 근을 찾는 방식으로 이해할 수 있다.

$ F(\theta) = \nabla_\theta L(\theta) $

$ F(\theta) = 0 $

1차원에서 뉴턴 메서드는 다음과 같이 쓴다.

$ \theta^{(t+1)} = \theta^{(t)} - \frac{f(\theta^{(t)})}{f'(\theta^{(t)})} $

여기서 $ f(\theta) = L'(\theta) $로 두면,

$ \theta^{(t+1)} = \theta^{(t)} - \frac{L'(\theta^{(t)})}{L''(\theta^{(t)})} $

이 된다.

이를 다차원으로 확장하면, 1차 미분은 그래디언트 벡터가 되고 2차 미분은 헤시안 행렬이 된다.

$ \nabla_\theta L(\theta) \in \mathbb{R}^d $

$ H(\theta) = \nabla_\theta^2 L(\theta) \in \mathbb{R}^{d \times d} $

따라서 다차원 Newton Method의 업데이트 식은 다음과 같다.

$ \theta^{(t+1)} = \theta^{(t)} - H(\theta^{(t)})^{-1}\nabla_\theta L(\theta^{(t)}) $

같은 식을 이동량 $ \Delta^{(t)} $로 쓰면 더 직관적이다.

$ H(\theta^{(t)})\Delta^{(t)} = \nabla_\theta L(\theta^{(t)}) $

$ \theta^{(t+1)} = \theta^{(t)} - \Delta^{(t)} $

즉, 뉴턴 메서드는 현재 지점에서 그래디언트와 헤시안 정보를 이용해 “얼마나 이동해야 기울기가 0에 가까워질지”를 계산한다.

이 방법은 Gradient Descent보다 빠르게 수렴할 수 있다. 하지만 파라미터가 $ d $개라면 매 반복마다 $ d \times d $ 크기의 헤시안 행렬을 계산해야 하고, 역행렬 계산도 필요하다.

$ H(\theta) \in \mathbb{R}^{d \times d} $

$ H(\theta)^{-1} $

역행렬 계산 비용은 대략 $ O(d^3) $이므로, 파라미터 수가 적은 고전적인 통계 모델에서는 유용하지만, 

파라미터가 매우 많은 현대 딥러닝 모델에서는 직접 사용하기 어렵다. (2022)

 

Rough Companion

 

Method	Per iteration	Compute	Steps to Error
SGD	1 data point	$ \Theta(d) $	$ \epsilon $: $ O(\epsilon^{-2}) $
Mini-batch Gradient Descent	$ b $ data points	$ \Theta(bd) $	$ \epsilon $: between SGD and Batch GD
Batch Gradient Descent	$ n $ data points	$ \Theta(nd) $	$ \theta^{(t+1)} = \theta^{(t)} - \alpha \nabla J(\theta^{(t)}) $
Newton's Method	$ n $ data points	$ \Omega(nd^2) $	$ \epsilon $: $ O(\log\log(1/\epsilon)) $