[CV] Least-Median of Squares Estimation (LMedS)

Least-Median of Squares (LMedS) 추정법

• P. J. Rousseeuw가 제안한 강건 회귀 분석 (robust regression) 기법.
• LMedS는 이상치(outliers)에 대해 매우 강인한 특성을 가짐: 데이터 내 Outlier(이상치)의 비율이 매우 높을 때도 안정적인 regression 결과를 제공.

---

LMedS의 정의

LMedS는 다음과 같은 최적화 문제(Optimization Problem)로 정의됨:

$$
\hat{\theta} = \underset{\theta}{\text{argmin}}  [\text{median}_i^m ||\textbf{r}_i||^2]
$$

where:

• $\hat{\theta}$: 최적의 regression model parameter 추정치
• $\|\mathbf{r}_i\| = \|y_i - f(x_i; \theta)\|$: 잔차(residual), 즉 실제 값과 예측 값의 차이
• $\text{median}_i^m$: 모든 잔차의 제곱값 중 중앙값(median)을 찾는 것

---

LMedS의 Key Idea

• 잔차의 제곱값 중 중앙값(median)을 최소화하는 파라미터 $\theta$를 찾는 것이 목표임.
• 즉, 전체 데이터 포인트 중 절반 이하가 이상치일 경우 median은 outlier에 영향을 받지 않으므로,
• 모델의 파라미터 추정이 이상치에 매우 강건(robust).

---

LMedS의 특성 및 직관적 이해

1. 이상치(outliers)에 대한 강건성
   • Median보다 큰 값들(즉, 상위 50%의 잔차 값들)은 중앙값을 결정하는 데만 영향을 미칠 뿐, 모델 파라미터를 구하는 데에는 사용되지 않음.
   • 예를 들어, 데이터 중 절반이 이상치라 하더라도, LMedS는 나머지 절반의 정상 데이터에 기반하여 모델을 구축할 수 있습니다.
   • 이로 인해, LMedS는 Breakdown Point가 50%에 이름.

Breakdown Point란:
모델이 이상치에 의해 왜곡되지 않고 정확하게 추정할 수 있는 최대 이상치 비율을 의미.
Breakdown Point가 50%라는 것은, 데이터의 절반이 이상치여도 여전히 정확한 모델을 만들 수 있다는 의미임.

2. Sorting에 기반한 Median 계산의 높은 계산 복잡도
   • 중앙값(median)을 찾기 위해 잔차 제곱값을 정렬(sorting)해야 하므로, 계산 비용이 큼.
   • 데이터가 많을수록 중앙값을 찾기 위한 정렬 과정에 계산비용이 커짐.
     • $O(n \log n)$의 시간 복잡도.
     • 고차원 데이터에서는 더욱 계산 부담이 커짐.

---

LMedS와 기존 Least Squares (LS) 회귀 비교

특성	Least Squares (LS)	Least-Median of Squares (LMedS)
목적 함수	잔차 제곱합의 최소화	잔차 제곱값의 median 최소화
이상치에 대한 민감도	민감함 (이상치에 취약, Breakdown Point=0%)	매우 강건 (Breakdown Point = 50%)
계산 복잡도	$O(n)$	$O(n \log n)$ (median 계산 시)
적합한 데이터	이상치가 거의 없는 경우	이상치가 많은 경우

---

직관적인 예시

1. Least Squares (LS):
   • 잔차 제곱합을 최소화하므로, 큰 잔차(이상치)의 영향이 매우 큼.
   • 이상치가 몇 개만 있어도 모델이 왜곡될 수 있음.
2. Least-Median of Squares (LMedS):
   • 잔차 제곱값의 중앙값(median)만 고려하므로, 잔차가 큰 이상치들이 모델에 거의 영향을 미치지 않음.
   • 데이터의 절반 이상이 이상치가 아니면, 나머지 정상 데이터를 기반으로 정확한 모델 추정 가능.

---

LMedS를 사용할 때의 주의 사항

• 계산 비용이 높으므로, 데이터의 크기가 큰 경우나 실시간 처리가 필요한 경우에는 비효율적일 수 있음.
• 이상치가 적고, 데이터가 클린한 경우에는 Least Squares 방식이 더 효율적임.
• 이상치가 많을 것으로 예상되거나, 데이터의 신뢰도가 낮은 경우 LMedS가 매우 효과적.

Outlier가 많을 경우 RANSAC과 더불어 많이 사용되는 기법이 바로 LMedS 임.

---

관련자료

P. J. Rousseeuw, Least Median of Squares Regression, Journal of the American Statistical Association, Vol.79, pp.871-880

https://www.eecs.yorku.ca/course_archive/2012-13/F/6338/lectures/LeastMedianOfSquares.pdf

LeastMedianOfSquares.pdf

4.61MB

 

 

2022.04.28 - [Programming/ML] - [Fitting] Ordinary Least Squares : OLS, 최소자승법

[Fitting] Ordinary Least Squares : OLS, 최소자승법

 

2024.11.25 - [Programming/DIP] - [Math] Maximum Likelihood Estimator: M-Estimator

[Math] Maximum Likelihood Estimator: M-Estimator

 

2024.06.13 - [Programming/ML] - [ML] RANdom SAmple Consensus (RANSAC)

[ML] RANdom SAmple Consensus (RANSAC)

---