고급 주제

고급 주제 (Advanced Topics)

머신러닝 라이브러리 개발자를 위한 고급 최적화 기법들을 정리한 문서예요. L-BFGS, 가중 최소제곱(weighted least squares) 정규방정식 해법, 그리고 반복 재가중 최소제곱(IRLS)의 원리와 MLlib에서의 구현을 확인해 볼게요. 다소 수학적인 내용이 많지만 차근차근 설명해 드릴게요.

출처: 문서

본문

선형 메서드의 최적화 (개발자용)
Limited-memory BFGS (L-BFGS)
가중 최소제곱을 위한 정규방정식 해법 (Normal equation solver for weighted least squares)
반복 재가중 최소제곱 (Iteratively reweighted least squares, IRLS)

선형 메서드의 최적화 (개발자용) (Optimization of linear methods (developer))

Limited-memory BFGS (L-BFGS)

L-BFGS는 $\min_{\wv \in\R^d} \; f(\wv)$ 형태의 최적화 문제를 풀기 위한 준뉴턴(quasi-Newton) 방법 계열의 최적화 알고리즘이에요. L-BFGS 방법은 목적 함수의 2차 편미분을 계산하지 않고도 Hessian 행렬을 근사하므로, 국소적으로 목적 함수를 2차식으로 근사해요. Hessian 행렬은 이전 기울기 평가들을 이용해 근사되므로, Newton 방법에서 Hessian 행렬을 명시적으로 계산할 때와 달리 수직 확장성(훈련 피처 수) 문제가 없어요. 그 결과 L-BFGS는 다른 1차 최적화 기법들에 비해 더 빠른 수렴을 보이는 경우가 많아요.

OWL-QN(Orthant-Wise Limited-memory Quasi-Newton)은 L-BFGS의 확장으로, L1 및 elastic net 정규화를 효과적으로 처리할 수 있어요.

L-BFGS는 LinearRegression, LogisticRegression, AFTSurvivalRegression 그리고 MultilayerPerceptronClassifier의 솔버로 사용돼요.

MLlib의 L-BFGS 솔버는 breeze의 해당 구현을 호출해요.

가중 최소제곱을 위한 정규방정식 해법 (Normal equation solver for weighted least squares)

MLlib는 WeightedLeastSquares로 가중 최소제곱(weighted least squares)을 위한 정규방정식 해법을 구현해요.

$n$개의 가중 관측치 $(w_i, a_i, b_i)$가 주어졌을 때:

$w_i$: i번째 관측치의 가중치
$a_i$: i번째 관측치의 피처 벡터
$b_i$: i번째 관측치의 레이블

각 관측치의 피처 수는 $m$이에요. 다음의 가중 최소제곱 수식을 사용해요:

\[
\min_{\mathbf{x}}\frac{1}{2} \sum_{i=1}^n \frac{w_i(\mathbf{a}_i^T \mathbf{x} -b_i)^2}{\sum_{k=1}^n w_k} + \frac{\lambda}{\delta}\left[\frac{1}{2}(1 - \alpha)\sum_{j=1}^m(\sigma_j x_j)^2 + \alpha\sum_{j=1}^m |\sigma_j x_j|\right]
\]

여기서 $\lambda$는 정규화 파라미터, $\alpha$는 elastic-net 혼합 파라미터, $\delta$는 레이블의 모집단 표준편차, 그리고 $\sigma_j$는 j번째 피처 컬럼의 모집단 표준편차예요.

이 목적 함수는 문제를 푸는 데 필요한 통계치를 모으기 위해 데이터를 한 번만 스캔해도 돼요. $n \times m$ 데이터 행렬에 대해 이 통계치들은 $O(m^2)$ 저장 공간만 필요하므로, $m$(피처 수)이 상대적으로 작을 때 단일 머신에 저장할 수 있어요. 이후 단일 머신에서 직접 Cholesky 분해나 반복 최적화 프로그램 같은 로컬 방법으로 정규방정식을 풀 수 있어요.

Spark MLlib는 현재 정규방정식을 위한 두 가지 솔버를 지원해요: Cholesky 분해와 준뉴턴 방법(L-BFGS/OWL-QN)이에요. Cholesky 분해는 양의 정부호(positive definite) 공분산 행렬(즉, 데이터 행렬의 컬럼들이 선형 독립)에 의존하며, 이 조건이 위반되면 실패해요. 준뉴턴 방법은 공분산 행렬이 양의 정부호가 아닐 때도 합리적인 해를 제공할 수 있으므로, 정규방정식 해법은 이런 경우 준뉴턴 방법으로 폴백(fallback)할 수 있어요. 이 폴백은 현재 LinearRegression과 GeneralizedLinearRegression 추정기에서 항상 활성화돼 있어요.

WeightedLeastSquares는 L1, L2, elastic-net 정규화를 지원하며 정규화와 표준화(standardization)를 켜거나 끄는 옵션을 제공해요. L1 정규화를 적용하지 않는 경우(즉, $\alpha = 0$)에는 해석적 해(analytical solution)가 존재하므로 Cholesky나 준뉴턴 솔버 중 하나를 사용할 수 있어요. $\alpha > 0$일 때는 해석적 해가 존재하지 않으므로 준뉴턴 솔버로 계수를 반복적으로 찾아요.

정규방정식 접근을 효율적으로 만들기 위해 WeightedLeastSquares는 피처 수가 4096을 넘지 않아야 해요. 더 큰 문제에는 L-BFGS를 사용하세요.

반복 재가중 최소제곱 (Iteratively reweighted least squares, IRLS)

MLlib는 IterativelyReweightedLeastSquares로 반복 재가중 최소제곱(IRLS)을 구현해요. 일반화 선형 모델(GLM)의 최대우도추정치(maximum likelihood estimates)를 찾거나, 강건 회귀(robust regression)에서 M-estimator를 찾는 등 다양한 최적화 문제에 사용할 수 있어요. 자세한 내용은 Iteratively Reweighted Least Squares for Maximum Likelihood Estimation, and some Robust and Resistant Alternatives를 참고하세요.

다음 과정을 반복하며 특정 최적화 문제를 풀어요:

현재 해에서 목적 함수를 선형화하고 해당 가중치를 갱신해요.
WeightedLeastSquares로 가중 최소제곱(WLS) 문제를 풀어요.
수렴할 때까지 위 단계를 반복해요.

각 반복에서 WeightedLeastSquares로 가중 최소제곱(WLS) 문제를 푸는 것이 포함되므로, 이것 역시 피처 수가 4096을 넘지 않아야 해요. 현재 IRLS는 GeneralizedLinearRegression의 기본 솔버로 사용돼요.