[고차원 데이터분석] Group Lasso (with Group MCP, SCAD)

 많은 회귀 문제들에서 설명변수들은 완전히 분리되는 것이 아니라 변수들이 하나의 공통 요인으로 묶일 수 있는 경우가 종종 있다. 예를 들어 범주형 변수를 지시 함수(Indicator function)을 통해 더미 변수(Dummy variable)로 나타내면 생성된 여러 변수들은 하나의 공통 요인으로 묶일 수 있다. 연속형 변수 역시 사전적으로 변수들의 그룹 정보를 알고 있다면 이 정보를 이용하지 않을 이유는 없다. 실제로 데이터가 그룹구조를 가지고 있을 때 그 정보를 활용해 더 높은 수준의 예측 성능을 낼 수 있다. 또한 변수 선택 관점에서 개별 변수를 선택하는 것이 아니라 변수들의 집합인 그룹을 선택하면, 진보적인(liberal) 결과와 함께 조금 더 해석적인 모형을 만들 수 있다.

---

 노테이션 먼저 정의하자. 선형 모형을 다음처럼 나타낸다.

$$y = X \boldsymbol{\beta} + \epsilon = \sum_{j=1}^{J}X_{j} \boldsymbol{\beta}_{j} + \epsilon $$

$X$는 $n \times d_{j}$행렬, $\beta_{j} \in \mathbb{R}^{d_{j}}$이다. 여기서 $d_{j}$는 $j$번째 그룹내에 변수들의 수 이다. 디자인 행렬 X를 총 J개로 나눴을 뿐이다. 여기서 하나의 변수는 하나의 그룹에만 속해야한다는 사실에 주의하자. 만약 변수가 여려 그룹에 속할 수 있다면 겹쳐진 그룹 구조를 다루는 문제로 넘어가야 한다.

---

 Group LASSO의 solution $\hat{\beta}(\lambda)$는 다음의 목적함수를 최소화하여 얻어진다.

$$\frac{1}{2n}||y-\sum_{j=1}^{J}X_{j} \boldsymbol{\beta}_{j}||^{2} + \lambda \sum_{j=1}^{J} \sqrt{d_{j}}||\boldsymbol{\beta}_{j}||_{R_{j}} \tag{1}$$

 

 LASSO의 penalty 함수는 $|\beta_{j}|$의 규모를 규제했다면, group LASSO는 $||\boldsymbol{\beta}_{j}||_{2}$의 규모를 규제한다. 여기서 $R_{j}$는 임의의 positive definite matrix이다. $R_{j}$를 어떻게 선택해야할까? 그룹 내 standardization을 통해 $R_{j}$의 선택은 크게 문제가 되지 않는다. 삼각행렬(upper triangular matrix) $U_{j}$를 사용해 $R_{j}=U_{j}^{T}U_{j}$로 나타낼 수 있다.(Cholesky decomposition) $\tilde{X}_{j}=X_{j}U_{j}^{-1}$와 $\boldsymbol{b}_{j} = U_{j}\boldsymbol{\beta}_{j}$라 하면, (1)의 목적함수는 다음과 같이 쓸 수 있다.

$$\frac{1}{2n}||y-\sum_{j=1}^{J}\tilde{X}_{j} \boldsymbol{b}_{j}||^{2} + \lambda \sum_{j=1}^{J} \sqrt{d_{j}}||\boldsymbol{b}_{j}||_{2} \tag{2}$$

즉, $R_{j}$의 선택의 문제는 최적화 전 단계에서 그룹 내 standardization을 함으로써 해결된다. 또한 일반성을 잃지 않고 group LASSO의 목적함수는 (2)로 가정해도 된다. 여기서 $X_{j}^{T} X_{j}=I$이지만 $j \neq k$에 대해 $X_{j}$와 $X_{k}$는 orthogonal 하지 않다는 사실에 주의하자.

---

 다음으로 group LASSO의 최적화가 어떻게 진행되는지 알아보자. 모든 $d_{j}=1$이라면 group LASSO와 LASSO가 동일해진다는 사실로부터 이 둘의 최적화 과정이 유사함을 눈치챌 수 있다. LASSO 최적화할 때 사용하는 Coordinate Descent Algorithm을 상기해보면 X가 orthogonal일 때 univariate solution은 closed form으로 나타낼 수 있고, 모든 파라미터를 순회하며 univariate solution을 찾는 과정을 반복하면 LASSO의 solution을 찾을 수 있다. group LASSO역시 비슷하다. 대신 group LASSO는 X가 orthogonal할 때, univariate solution의 closed form 대신 $\hat{\boldsymbol{\beta}}_{j}$의 closed form을 사용한다. $\hat{\boldsymbol{\beta}}_{j}$의 solution은 다음의 정리를 참고하자.

 이제 최적화할 준비를 모두 마쳤다. group LASSO의 목적함수 역시 convex이기에 CD를 통해 찾은 해는 global minimum을 보장한다. 그룹 단위로 최적화가 진행되기에 다음 알고리즘을 특별히 Blockwise Coordinate Descent라고 부른다.

 MCP와 SCAD를 최적화할 때 LASSO의 CD과정에서 soft thresholding을 firm이나 scad thresholding으로 바꾸기만 하면 됐다. group단위에서도 마찬가지다. 위의 thresholding operator를 바꾸면 group MCP와 group SCAD의 최적화 알고리즘이 된다.