[Algorithm] IRLS(Iteratively Reweighted Least Squares)

IRLS(Iteratively Reweighted Least Squares)

IRLS는 최소제곱법(Least Squares)를 일반화하여, 반복적으로 가중치를 조정하면서 최적의 회귀 계수를 추정하는 알고리즘입니다. 여러 회귀 문제에서 사용되며 GLM에서 모델 적합과정에 주요하게 사용됩니다.

1. Objective of IRLS

• 회귀 계수 추정 문제
  • GLM에서 $\beta$를 추정하려면, 가능도함수(Likelihood)를 최대화해야한다.
  • 일반적으로 로그가능도 함수를 직접 최적화하는 것은 어렵다.

💡

IRLS는 이 복잡한 문제를 반복적인 WLS(Weighted Least Squares) 문제로 변환하여 효율적으로 해결합니다.

2. Basic Idea of IRLS

최소제곱법의 일반화.

1. 최소제곱법(OLS):
   • 선형회귀에서 우리는 잔차(Residual)의 제곱합을 최소화하는 것을 목표로 합니다.
   • $$
     argmin_{\beta} \sum_{i}^n\big(y_i - X_i\beta\big)^2
     $$
2. 가중최소제곱법(WLS):
   • 잔차에 가중치를 부여하여 특정 데이터 포인트의 영향력을 조정합니다.
   • $$
     argmin_{\beta} \sum_{i}^nw_i\big(y_i - X_i\beta\big)^2
     $$
   • $w_i$는 각 관측치의 중요도를 나타내는 가중치
3. IRLS:
   • 가중치를 고정하지 않고, 반복적으로 데이터에 따라 가중치를 동적으로 조정합니다.

3. IRLS Algorithm

Step 1. 초기화

• 회귀 계수 $\beta$를 초기값으로 설정합니다.
• Linear Predictor $\eta$를 계산합니다.
• $\eta = X\beta$
• 연결함수 $g(\cdot)$와 그 역함수를 구합니다.

Step 2. 기댓값 계산

• 종속변수의 기댓값 $\mu$를 계산합니다.
  • $\mu$는 종속변수의 예측값
  • $g$는 종속변수의 분포에 따라 결정
• $\mu = g^{-1}(\eta)$

Step 3. 가중치 행렬 계산

• 분포의 특성에 따라 가중치를 동적으로 계산합니다.
  • $W = \text{diag}\bigg(\dfrac{\partial \mu}{\partial \eta}\cdot\dfrac{1}{\text{var(Y)}}\bigg)$
  • $\dfrac{\partial \mu}{\partial \eta}$ : 연결함수의 미분
  • $\text{Var(Y)}$ : 종속 변수의 분산

Step 4. 잔차 계산

• IRLS는 잔차를 업데이트하여 잔여 정보를 반영합니다
• $z = \eta + W^{-1}(Y-\mu)$
• $z$ : Working Residual, 현재 모델이 설명하지 못한 데이터를 보정합니다.

Step 5. WLS 적용

• 가중최소제곱법을 사용하여 새로운 계수를 계산합니다.
  • 새로운 계수 행렬 $\beta^{(t+1)}$을 계산합니다.
• $\beta^{(t+1)} = (X^TWX)^{-1}X^TWz$

Step 6. 수렴 조건 확인

• 반복적으로 $\beta$를 업데이트하며, 다음 조건을 만족하면 종료합니다.
• $||\beta^{(t+1)} - \beta^{(t)}|| <\epsilon$

Newton-Rapson 방법

• IRLS는 뉴런랩슨 방법을 기반으로 작동합니다.
• 로그가능도 함수 \ell(\beta) 를 최대화하기 위해 2차 테일러 전개를 사용합니다.
• $\beta^{(t+1)} = \beta^{(t)} - \left[ H(\beta^{(t)}) \right]^{-1} g(\beta^{(t)})$

• $g(\beta)$ : 로그가능도의 1차 미분(그래디언트).
• $H(\beta)$ : 로그가능도의 2차 미분(헤시안 행렬).

IRLS와의 연결

• 뉴턴-랩슨 방법의 업데이트 공식을 가중 최소제곱 문제로 변환한 것이 IRLS.
• 가중 행렬 W 는 헤시안 행렬의 근사치로 사용됩니다.

구현 예시

import numpy as np

# 샘플 데이터
X = np.array([[1, 0.5], [1, 2.3], [1, 1.8]])  # 독립 변수 (설정값)
y = np.array([0, 1, 1])                       # 종속 변수 (관측값)

# 초기값 설정
beta = np.zeros(X.shape[1])  # 초기 회귀 계수
max_iter = 10                # 최대 반복 횟수
tol = 1e-6                   # 수렴 기준

# IRLS 반복 과정
for _ in range(max_iter):
    eta = np.dot(X, beta)                # 선형 예측기
    mu = 1 / (1 + np.exp(-eta))          # 로지스틱 함수 (예측값)
    W = np.diag(mu * (1 - mu))           # 가중치 행렬
    z = eta + np.dot(np.linalg.inv(W), y - mu)  # 작업 잔차
    beta_new = np.linalg.inv(X.T @ W @ X