An Efficient Newton Algorithm for Nonnegative Matrix Factorization with the Kullback-Leibler Divergence

기술 요약: 쿨백-라이블러 발산을 사용하는 비음수 행렬 분해를 위한 효율적인 뉴턴 알고리즘

문제 정의
비음수 행렬 분해(NMF)는 비음수 행렬 $V$를 두 개의 저계수 비음수 인자 $W$와 $H$의 곱($V \approx WH$)으로 근사한다. 데이터가 포아송 분포를 따르는 경우(단어-문서 행렬이나 광자 계수 이미지와 같은 카운트 데이터셋에서 흔함), 쿨백-라이블러(KL) 발산이 적절한 손실 함수가 된다. 결과적으로 발생하는 (NMF-KL) 최적화 문제는 $W$와 $H$에 대해 결합하여 볼 때 비볼록(non-convex)이지만, 각각에 대해서는 볼록(convex)하다.

기존의 최첨단 (NMF-KL) 알고리즘들은 주로 Majorization-Minimization (MM) 프레임워크에 의존한다. 이러한 방법들은 손실 함수의 분리 가능한 상한(separable upper-bound, majorant)을 최소화하여 다중 곱 업데이트(Multiplicative Updates, MU) 알고리즘과 같은 업데이트 규칙을 도출한다. 이러한 방식은 반복당 $O(MNR)$의 효율성을 갖지만, 저자들은 이 접근 방식이 서로게이트 함수(surrogate function)의 조밀함(tightness) 측면에서 이론적 한계에 도வில했다는 점을 주장한다.

방법론
제안된 접근 방식인 KL-HALS는 분리 가능한 서로게이트 패러다임에서 벗어나 손실 함수의 **2차 테일러 전개(second-order Taylor expansion)**를 활용한다. 이는 결과적으로 비분리적인 이차(non-separable quadratic) 서로게이트를 생성한다. 해결된 핵심 과제는 다음과 같다:

1. 비음수 제약 조건: 일반적인 수렴 보장을 결여한 비용이 많이 드는 투영 뉴턴 단계(projected Newton steps)나 활성 집합(active-set) 방법을 사용하지 않고 제약 조건을 처리하는 것.
2. 효율적인 최소화: 비분리적인 이차 서로게이트를 효율적으로 최소화하는 것.
3. 단계 크기 선택: KL 발산에 적용되지 않는 리프시츠 매끄러움(Lipschitz smoothness) 가정에 의존하지 않고 수렴을 보장하는 단계 크기를 선택하는 것.

저자들은 단계 크기 선택과 수렴 보장을 위해 자기 공액 함수(self-concordant functions)(Tran-Dinh et al. [22]) 프레임워크를 활용한다. 그들은 (NNKL) 하위 문제가 자기 공곡성을 가짐을 증명하며, 이를 통해 특정 단계 크기($\alpha_k = 1/(1+\lambda_k)$)를 가진 감쇄 뉴턴 단계(damped Newton steps)를 사용하여 손실 감소를 보장할 수 있음을 보여준다.

비음수 제약 조건 하에서 발생하는 비분리 이차 서로 gate를 최소화하기 위해, 논문은 GHALS라 명명된 **계층적 교대 최소 제곱법(Hierarchical Alternating Least Squares, HALS)**의 일반화된 형태를 제안한다.

• GHALS: 단일 스칼라 항목이나 분리 가능한 합을 구하는 대신, GHALS는 $H$의 각 열마다 서로 다른 헤시안 행렬을 갖는 다변량 이차식의 합을 푼다. 이 알고리즘은 이차 항의 특정한 구조로부터 유도된 폐쇄형 표현식을 사용하여 $H$의 행들을 순환적으로 업데이트한다.
• 알고리즘 구조: 전체 알고리즘은 $H$와 $W$를 번갈아 업데이트한다. 각 인자 업데이트 시, 1차 계수($A$)와 2차 계수($T$)를 계산하고, GHALS를 사용하여 서로게이트 문제를 풀며, 단계 크기를 적용한다.
• 복잡도: 반복당 복잡도는 텐서 $T$(헤시안 근사치) 계산에 의해 지배되는 $O(MNR^2)$이다. 이는 $O(MNR)$ 복잡도를 갖는 분리 가능한 MM 방법보다 높지만, 저자들은 이 트레이드오프가 유리하다고 주장한다.
• 희소 구현: 대규모 희소 데이터셋을 위해, 저자들은 $WH$행렬을 형성하지 않고$nnz(V)$에 의존하도록 복잡도를 줄인 희소 버전을 구현하였다.

주요 기여

1. 분리 가능한 Majorant의 이론적 한계: 저자들은 MU 알고리즘에서 사용되는 분리 가능한 상한이 NNKL 손실에 대한 가장 조밀한 전역 분리 가능 majorant임을 증명한다. 이는 더 나은 성능을 달기 위해 분리 가능한 서로게이트에서 벗어나야 함을 이론적으로 정당화한다.
2. MU Burg의 하위 최적성: 저자들은 MU Burg 알고리즘(Bauschke et al. [17] 기반)이 MU보다 더 느슨한 상한을 사용함을 이론적으로 입증하며, 이것이 경험적으로 관찰되는 열등한 성능의 이유임을 설명한다.
3. 효율적인 비분리 최소화: 논문은 HALS의 일반화인 GHALS를 도입하여, 기존 NMF-KL 문헌에서 효율적으로 해결되지 않았던 비분리 이차 서로게이트를 비음수 제약 조건 하에서 효율적으로 최소화한다.
4. 수렴 보장: 자기 공곡성 성질을 활용함으로써, 저자들은 감쇄 뉴턴 단계를 사용하여 증명 가능한 수렴 보장을 갖는 버전의 알고리즘(KL-HALS-descent)을 제공한다.
5. 초기화 전략: 초기 인자들의 행과 열을 최적으로 스케일링하기 위해 Sinkhorn 알고리즘을 사용하는 것을 제안하며, 이를 통해 시작점이 이차 수렴의 영역(basin of quadratic convergence)에 가깝도록 보장한다.

실험 결과
저자들은 다양한 데이터셋에 대해 KL-HALS 및 그 감쇄 변형을 최첨단 알고리즘들(MU, SN, CCD, AmSOM, AMUSOM, FPA, HALS)과 비교 평가하였다:

• 오디오: MAPS 데이터셋에서 KL-HALS는 가장 낮은 손실값에 수렴했으나, 높은 랭크에서는 $R^2$ 복잡도로 인해 MU보다 느렸다. 두 번째 오디오 샘플에서는 KL-HALS가 다른 모든 모델을 능가했다.
• 이미지: 얼굴 및 초분광 데이터셋에서 HALS(Frobenius 손실에 최적화됨)가 놀랍게도 가장 좋은 성능을 보였는데, 이는 가우시안 모델과 포아송 모델이 이러한 특정 유형의 데이터에 대해 동등할 수 있음을 시사한다. KL-HALS는 두 번째로 우수한 성능을 보였으며, 일관되게 MU와 CCD를 능가했다.
• 문서: 대규모 희소 카운트 데이터인 CLUTO 및 Verb 데이터셋에서, KL-HALS는 다양한 상대 오차에 대해 가장 낮은 최종 손실값을 달성하며 MU와 CCD를 크게 앞질렀다. 그러나 랭크 $R$이 증가함에 따라 수렴 속도가 저하되었는데, 이는 높은 계산 복잡도와 일치한다.
• 합성 데이터: 저계수 및 전계수 합성 데이터셋 모두에서 KL-HALS는 일관되게 가장 좋은 손실값으로 수렴했으며, 특히 노이즈가 있는 설정에서 다른 방법들을 능가하는 경우가 많았다.

의의 및 주장
본 논문은 분리 가능한 상한에 대한 개선의 여지가 고갈되었으므로, **비분리 서로게이트(non-separable surrogates)**를 탐구하는 것이 NMF-KL의 진전을 위해 필수적이라고 주장한다. 제안된 방법은 비음수 제약 조건 하에서 2차 테일러 전개를 최소화하는 것이 가능하다는 것을 입증한다.

저자들은 자신들의 $O(MNR^2)$ 방법이 $O(MNR)$ 1차 방법들과 비교했을 때 경쟁력이 있고 종종 더 우수하지만, 계산 비용이 매우 높은 랭크 문제에서는 여전히 장벽이 될 수 있음을 겸허히 언급한다. 그들은 향-후 연구가 헤시안을 근사(quasi-Newton 접근법)하거나 외삽 업데이트(extrapolated updates)를 탐구하여, 2차 방법의 정확도와 1차 알고리즘의 속도 사이의 간극을 메울 수 있는 방향으로 진행될 수 있다고 제안한다. 이 연구는 자기 공곡성과 GHALS와 같은 특화된 솔버를 통해 2차 정보를 올바르게 처리할 때, 추가적인 계산 투자를 정당화할 만큼 높은 품질의 반복값(iterates)을 얻을 수 있음을 확립한다.