최소각 회귀

통계 수치해석 최적설계 마지막 수정: 2026-08-11 04:38:41

1. 개요[편집]

최소각 회귀 Least Angle Regression (LARS)
제안	Efron, Hastie, Johnstone, Tibshirani (2004, Ann. Statist.)
핵심 동작	활성 변수들과 같은 각을 이루는 방향으로 등속 전진
멈추는 순간	비활성 변수 하나가 잔차와의 상관에서 동률이 될 때
라쏘 수정	계수가 0을 통과하면 그 변수를 활성집합에서 제거
결과	조각별 선형 라쏘 경로 전체를 정확히 산출
자유도	k단계 추정량의 자유도 ≈ k (활성 변수 개수)

최소각 회귀(LARS)는 잔차와 가장 상관이 큰 변수 쪽으로 계수를 조금씩 밀되, 활성 변수들 전부와 정확히 같은 각을 이루는 방향으로만 전진하는 변수 선택 회귀 절차다. 에프론·하스티·존스톤·팁시라니가 2004년에 발표했고, 발표되자마자 “전진 선택과 전진 단계적 선택 사이의 잃어버린 고리”라는 평을 들었다.

LARS 자체보다 유명한 것은 그 부산물이다. 딱 한 줄짜리 수정(“계수가 0을 지나면 그 변수를 활성집합에서 뺀다”)을 넣으면 라쏘의 정규화 경로 전체를 정확히, 최소제곱 한 번과 같은 차수의 비용으로 얻는다. 그때까지 라쏘는 $\lambda$ 하나마다 이차계획법을 새로 푸는 물건이었으므로, 이 결과는 $\ell_1$ 정규화를 실용 도구로 끌어올린 사건이었다.¹

2. 전진 선택과 전진 단계적 선택 사이[편집]

LARS의 자리는 두 고전 절차를 놓고 봐야 보인다. 표준화된 설계행렬 $X$ 와 중심화된 $y$ , 현재 잔차 $r = y - X\beta$ 를 기준으로 한다.

전진 선택(forward selection). 잔차와 상관이 가장 큰 변수를 고르고, 그 변수(들)에 대해 최소제곱까지 끝까지 간다. 빠르지만 지나치게 탐욕적이다. 한 변수에 계수를 몰아준 탓에 그와 상관된 다른 좋은 변수들이 영영 배제된다.
전진 단계적 선택(forward stagewise). 역시 상관이 가장 큰 변수를 고르되, 아주 작은 $\varepsilon$ 만큼만 밀고 다시 상관을 계산한다. 결과는 훨씬 겸손하고 예측 성능도 좋지만, $\varepsilon$ 을 작게 잡을수록 반복이 수천·수만 번으로 늘어난다.

LARS의 관찰은 이것이다. 전진 단계적 절차에서 $\varepsilon\to0$ 극한을 취하면 계수가 움직이는 방향과 “다음 변수가 합류하는 지점”이 닫힌 형태로 계산된다. 그러니 $\varepsilon$ 씩 기어갈 필요 없이 그 지점까지 한 번에 점프하면 된다. 절차는 다음과 같다.

$\beta=0$ , $r=y$ 에서 시작. $|x_j^\top r|$ 이 최대인 변수 $j_1$ 을 활성집합 $A$ 에 넣는다.
$\beta_{j_1}$ 을 $\mathrm{sign}(x_{j_1}^\top r)$ 방향으로 키운다. 그러면 $|x_{j_1}^\top r|$ 이 줄어든다.
어떤 비활성 변수 $j_2$ 의 $|x_{j_2}^\top r|$ 이 $|x_{j_1}^\top r|$ 과 같아지는 순간 멈추고 $j_2$ 를 $A$ 에 넣는다.
이제 $x_{j_1}, x_{j_2}$ 양쪽과 같은 각을 이루는 방향으로 전진한다. 그러면 두 상관이 나란히 같은 속도로 줄어들어 동률이 유지된다.
세 번째 변수가 동률이 될 때까지 진행하고, 방향을 다시 계산한다. 이하 반복.

즉 LARS는 활성 변수들의 상관 크기를 항상 같게 유지하면서 그 공통 값을 0을 향해 끌어내리는 절차다. 라쏘의 KKT 조건 — “활성 변수는 잔차와의 상관이 전부 정확히 $\lambda$ ” — 과 문장 하나 차이도 안 난다는 것이 눈에 띈다면, 이미 뒤 절의 결론을 절반쯤 본 셈이다.

3. 등각 방향[편집]

“같은 각”을 실제로 계산하는 것이 알고리즘의 유일한 선형대수다. 활성집합 $A$ , 각 활성 변수의 현재 상관 부호 $s_j$ 에 대해 부호를 흡수한 $X_A = (\dots\, s_j x_j\, \dots)$ 와 $G_A = X_A^\top X_A$ 를 두고

A_A = \bigl(\mathbf{1}^\top G_A^{-1}\mathbf{1}\bigr)^{-1/2}, \qquad w_A = A_A\,G_A^{-1}\mathbf{1}, \qquad u_A = X_A w_A

로 잡으면 $\|u_A\|_2 = 1$ 이고

X_A^\top u_A = A_A\,\mathbf{1}

이 된다. 마지막 식이 정확히 등각(equiangular) 조건이다 — 단위벡터 $u_A$ 가 활성 변수 전부와 똑같은 내적 $A_A$ 를 갖는다. 활성 변수가 하나뿐이면 $u_A = s_{j}x_{j}$ 로, 그냥 그 변수 방향이다.

전진 거리도 닫힌 형태로 나온다. 현재 공통 상관 크기를 $\hat C$ , 비활성 변수의 상관을 $c_j = x_j^\top r$ , $a_j = x_j^\top u_A$ 라 하면 다음 합류 지점은

\hat\gamma = \min_{j\notin A}{}^{+}\left\{\frac{\hat C - c_j}{A_A - a_j},\ \frac{\hat C + c_j}{A_A + a_j}\right\}

이다( $\min^{+}$ 는 양수인 것들 중 최솟값). 분자는 “지금 상관 차이”, 분모는 “그 차이가 줄어드는 속도”이므로, 나눗셈 한 번이 곧 도달 시간이다. 전체 절차의 비용은 $G_A^{-1}$ 를 촐레스키 인수의 갱신·격하로 유지하면 $p$ 개 변수 최소제곱 한 번과 같은 차수( $p<n$ 일 때 대략 $O(p^3 + np^2)$ )로 끝난다. 경로 전체를 얻는 값이 점 하나 푸는 값과 같다는 것이 당시 사람들을 놀라게 한 지점이다.

4. 라쏘 수정 한 줄[편집]

위 절차를 그대로 돌리면 계수는 한 번 활성화된 뒤 계속 같은 방향으로 커지기만 한다. 그런데 라쏘 경로에서는 활성 변수의 계수가 0을 통과하며 지지집합에서 빠지는 일이 실제로 일어난다. 상관이 강한 변수 무리가 있을 때 흔하다.

수정은 정말 한 줄이다.

전진 도중 어떤 활성 계수 $\beta_j$ 가 0에 도달하면( $\tilde\gamma_j = -\beta_j/d_j$ 가 $\hat\gamma$ 보다 먼저 오면), 거기서 멈추고 $j$ 를 활성집합에서 제거한 뒤 방향을 다시 계산한다.

여기서 $d_j$ 는 방향벡터의 $j$ 성분( $s_j w_{A,j}$ )이다. 이 한 줄을 넣은 LARS가 만드는 경로가 라쏘 경로와 정확히 일치한다는 것이 논문의 핵심 정리다. 증명의 골자는 부호 일관성이다 — 라쏘 KKT 조건은 활성 변수에서 $x_j^\top r = \lambda\,\mathrm{sign}(\beta_j)$ 를 요구하는데, 계수의 부호와 상관의 부호가 어긋나는 순간이 바로 계수가 0을 지나는 순간이므로, 그때 변수를 빼 주면 KKT가 경로 전체에서 유지된다.

비슷한 방식으로 부호 제약을 한 겹 더 걸면(방향이 활성 변수들의 음이 아닌 결합이 되도록 강제) 전진 단계적 절차의 $\varepsilon\to0$ 극한도 재현된다. 그래서 LARS는 하나의 뼈대에 수정 두 개로 세 절차를 모두 낳는다 — 순수 LARS, 라쏘, 전진 단계적. 이 통일성이 논문이 토론 40쪽을 달고 나온 이유다.

5. 조각별 선형 경로와 자유도[편집]

라쏘 목적함수는 이차 손실 + 조각별 선형 벌점이므로 해 $\hat\beta(\lambda)$ 는 $\lambda$ 에 대해 조각별 선형이다. 꺾이는 지점(knot)은 활성집합이 하나 늘거나 주는 순간뿐이다. LARS가 하는 일은 정확히 그 꺾임점들을 순서대로 계산하는 것이고, 그래서 이 계열을 호모토피 방법이라고도 부른다(오스본-프레스넬-털랙 2000이 라쏘에 대해 독립적으로 같은 구조를 발견했다).

경로가 유한 번에 끝난다는 것은 좋은 소식이지만, 꺾임의 개수가 항상 작다는 뜻은 아니다. 통상적인 데이터에서는 꺾임 수가 $\min(n,p)$ 근처지만, 계수가 활성집합에 들락날락을 반복하도록 설계행렬을 꾸미면 꺾임 수가 $p$ 에 지수적으로 늘어나는 구성이 존재한다는 것이 알려져 있다(Mairal-Yu 2012). 최악 사례가 나쁘다는 것과 평균적으로 빠르다는 것이 공존하는, 심플렉스법과 비슷한 상황이다.

자유도 결과가 여기서 나온다. 에프론 등은 스타인의 불편 위험 추정(SURE)을 써서, LARS를 $k$ 단계 돌린 추정량의 유효 자유도가 정확히 $k$ 라는 것을 보였다(직교 설계, 그리고 이른바 양의 원뿔 조건 아래). 라쏘 경로에 대해서는 조금 뒤에 더 강한 결과가 나왔다 — 일반 설계행렬에서도

\mathrm{df}\bigl(\hat\mu(\lambda)\bigr) = \mathbb{E}\bigl[\,|A(\lambda)|\,\bigr]

즉 0이 아닌 계수 개수의 기댓값이 곧 자유도다(Zou-Hastie-Tibshirani 2007). 축소를 하는데도 자유도가 “선택된 변수 수”와 같다는 것은 처음 보면 반직관적이다. 변수 선택으로 자유도를 더 쓰는 것과 축소로 자유도를 되돌려받는 것이 정확히 상쇄되기 때문이며, 이 결과 덕분에 경로 위에서 $C_p$ 나 아카이케 정보기준 같은 정보 기준을 곧바로 계산할 수 있다.²

6. 지금도 쓰나 — 좌표하강과의 분업[편집]

2004년의 왕좌는 오래가지 않았다. glmnet이 좌표 하강법 + 웜스타트 + 활성집합으로 훨씬 빨라졌고, 특히 $p$ 가 수만을 넘어가는 문제에서는 비교가 되지 않는다. LARS는 스텝마다 $G_A^{-1}$ 를 유지해야 하는데, 활성집합이 커지면 이 갱신 비용이 제곱으로 늘고 수치적으로도 예민하다. 동률이 여럿 생기거나 열이 거의 종속인 경우 촐레스키 갱신이 무너지는 것이 LARS 구현자의 단골 악몽이다.

그래도 LARS가 사라지지 않은 이유가 있다.

정확한 경로가 필요할 때. 좌표 하강은 격자 위 유한개 $\lambda$ 에서의 근사해를 준다. LARS는 꺾임점 전부를 정확히 준다. 경로의 미세 구조를 봐야 하는 이론·진단 작업에서는 이쪽이다.
자유도와 선택 후 추론. 위의 df 결과, 그리고 그 뒤에 나온 조건부 추론(선택 사건을 다면체로 기술하고 절단 정규분포를 쓰는 방식) 전부가 경로의 조각별 선형 구조 위에 서 있다. LARS는 그 구조를 명시적으로 들고 다닌다.
작고 조밀한 문제. $p$ 가 수백 이하면 LARS 한 번이 격자 100개짜리 좌표 하강보다 빠른 경우가 흔하다. scikit-learn이 lars_path·LassoLarsIC를 유지하는 이유.
개념적 가치. “활성 변수의 상관을 같게 유지하며 임계값을 내린다”는 그림은 $\ell_1$ 정규화가 실제로 무엇을 하는지에 대한 가장 좋은 직관이다. 소프트 임계화 공식만 외운 사람과 이 그림을 아는 사람의 차이는 상관이 심한 데이터에서 갈린다.

한편 $\ell_2$ 항이 섞인 엘라스틱 넷 경로도 같은 방식으로 조각별 선형이며, 증강 데이터 트릭으로 라쏘 문제가 되므로 LARS-EN이라는 이름으로 그대로 돌릴 수 있다. 조각별 선형성이 유지되는 한 호모토피 접근은 계속 통한다 — 반대로 로지스틱 회귀처럼 손실이 이차가 아니면 경로가 더 이상 조각별 선형이 아니라 이 계보 전체가 무너지고, 그 순간 좌표 하강이 유일한 선택지가 된다.³

7. 관련 문서[편집]

논문 제목이 “Least Angle Regression”인데 약자를 LARS로 쓴 것은 라쏘(LASSO)와 스테이지와이즈(Stagewise)의 S를 붙여 둔 것이라고 저자들이 밝혔다. 하나의 알고리즘이 세 절차를 낳는다는 주장을 약자에까지 심어 놓은 셈. 통계학자들의 작명 집착은 라쏘 이래 일관된다. ↩
이 자유도 결과를 “그러니 라쏘로 변수 고른 다음 그 개수를 모수 개수로 넣어 AIC를 계산하면 된다”로 읽으면 안 된다. 성립하는 것은 경로 위 고정된 $\lambda$ 에 대한 기댓값이고, $\lambda$ 자체를 데이터로 고르는 순간 또 다른 선택 비용이 생긴다. 통계에서 “공짜로 보이는 결과”는 대개 조건절 안에 값이 적혀 있다. ↩
그래서 “경로가 조각별 선형인가”는 단순한 미적 관심사가 아니라 알고리즘 계보를 가르는 분수령이다. 손실이 이차이고 벌점이 조각별 선형이면 호모토피가 통하고, 어느 한쪽이라도 깨지면 격자 + 웜스타트로 돌아가야 한다. SVM의 정규화 경로가 조각별 선형이라 같은 트릭이 통한 것도 힌지 손실이 조각별 선형이었기 때문이다. ↩