Divide-and-conquer random sketched kernel ridge regression for large-scale data analysis^†

2020, 31

1)

15–23

대용량 자료의 분석을 위한 분할정복 랜덤스케치 커널 능형회귀

^†

ᄀ

ᅡᆼ종경

¹

²

1고려대학교 통계학과 · ²한국뉴욕주립대학교 응용수학통계학과

ᄌ ᅥ

ᆸᄉ ᅮ 2019ᄂ ᅧ ᆫ 10ᄋ ᅯ ᆯ 11ᄋ ᅵ ᆯ, ᄉ ᅮᄌ ᅥ ᆼ 2019ᄂ ᅧ ᆫ 11ᄋ ᅯ ᆯ 4ᄋ ᅵ ᆯ, ᄀ ᅦᄌ ᅢ ᄒ ᅪ ᆨᄌ ᅥ ᆼ 2019ᄂ ᅧ ᆫ 11ᄋ ᅯ ᆯ 7ᄋ ᅵ ᆯ

요 약

ᄏ

ᅥᄂ ᅥ ᆯ ᄂ ᅳ ᆼᄒ ᅧ ᆼᄒ ᅬᄀ ᅱ (kernel ridge regression; KRR)ᄂ ᅳ ᆫ ᄌ ᅢᄉ ᅢ ᆼᄉ ᅥ ᆼ ᄏ ᅥᄂ ᅥ ᆯ ᄒ ᅵ ᆯᄇ ᅥᄐ ᅳ ᄀ ᅩ ᆼ ᄀ ᅡ ᆫᄋ ᅦᄉ ᅥ ᄇ ᅵᄆ ᅩᄉ ᅮᄌ ᅥ ᆨ ᄒ ᅬᄀ ᅱ ᄒ ᅡ

ᆷᄉ ᅮᄅ ᅳ ᆯ ᄎ ᅮᄌ ᅥ ᆼᄒ ᅡᄂ ᅳ ᆫ ᄃ ᅢᄑ ᅭᄌ ᅥ ᆨᄋ ᅵ ᆫ ᄀ ᅵᄇ ᅥ ᆸᄋ ᅳᄅ ᅩ ᄃ ᅡᄋ ᅣ ᆼᄒ ᅡ ᆫ ᄐ ᅩ ᆼ ᄀ ᅨ ᄇ ᅮ ᆫᄉ ᅥ ᆨᄋ ᅦ ᄒ ᅪ ᆯᄋ ᅭ ᆼ ᄃ ᅬᄀ ᅩ ᄋ ᅵ ᆻᄃ ᅡ. ᄏ ᅳᄀ ᅵᄀ ᅡ nᄋ ᅵ ᆫ ᄌ ᅡᄅ ᅭᄋ ᅦᄉ ᅥᄋ ᅴ ᄋ ᅵ ᆯᄇ ᅡ ᆫ ᄌ

ᅥ ᆨᄋ ᅵ ᆫ KRRᄋ ᅴ ᄀ ᅮᄒ ᅧ ᆫᄋ ᅦ ᄑ ᅵ ᆯᄋ ᅭᄒ ᅡ ᆫ ᄀ ᅨᄉ ᅡ ᆫ ᄆ ᅵ ᆾ ᄌ ᅥᄌ ᅡ ᆼ ᄇ ᅵᄋ ᅭ ᆼᄋ ᅳ ᆫ ᄀ ᅡ ᆨᄀ ᅡ ᆨ O(n

), O(n

)ᄋ ᅵᄆ ᅧ, ᄃ ᅢᄋ ᅭ ᆼ ᄅ ᅣ ᆼ ᄌ ᅡᄅ ᅭᄋ ᅪ ᄀ ᅡ ᇀᄋ ᅵ nᄋ ᅵ ᄆ

ᅢᄋ ᅮ ᄏ ᅳ ᆫ ᄀ ᅧ ᆼᄋ ᅮ ᄀ ᅳ ᄒ ᅪ ᆯᄋ ᅭ ᆼᄉ ᅥ ᆼᄋ ᅵ ᄆ ᅢᄋ ᅮ ᄌ ᅦᄒ ᅡ ᆫᄃ ᅬ ᆫ ᄃ ᅡ. ᄋ ᅵᄅ ᅥᄒ ᅡ ᆫ ᄆ ᅮ ᆫ ᄌ ᅦᄅ ᅳ ᆯ ᄒ ᅢᄀ ᅧ ᆯᄒ ᅡᄀ ᅵ ᄋ ᅱᄒ ᅢ ᄇ ᅮ ᆫ ᄒ ᅡ ᆯᄌ ᅥ ᆼᄇ ᅩ ᆨ KRR, ᄅ ᅢ ᆫᄃ ᅥ ᆷᄉ ᅳᄏ ᅦᄎ ᅵ KRRᄀ ᅪ ᄀ ᅡ ᇀᄋ ᅳ ᆫ ᄀ ᅵᄇ ᅥ ᆸᄃ ᅳ ᆯ ᄋ ᅵ ᄀ ᅢᄇ ᅡ ᆯᄃ ᅬᄋ ᅥ ᆻᄃ ᅡ. ᄇ ᅩ ᆫ ᄋ ᅧ ᆫᄀ ᅮᄋ ᅦᄉ ᅥᄂ ᅳ ᆫ ᄃ ᅢᄋ ᅭ ᆼ ᄅ ᅣ ᆼ ᄌ ᅡᄅ ᅭᄋ ᅦᄉ ᅥᄋ ᅴ KRRᄋ ᅦ ᄒ ᅪ ᆯᄋ ᅭ ᆼᄃ ᅬ ᆫ ᄇ ᅮ ᆫ ᄒ ᅡ ᆯᄌ ᅥ ᆼᄇ ᅩ ᆨ ᄀ ᅵᄇ ᅥ ᆸ ᄀ

ᅪ ᄅ ᅢ ᆫᄃ ᅥ ᆷᄉ ᅳᄏ ᅦᄎ ᅵ ᄀ ᅵᄇ ᅥ ᆸᄋ ᅳ ᆯ ᄀ ᅧ ᆯᄒ ᅡ ᆸᄒ ᅡᄋ ᅧ ᄉ ᅢᄅ ᅩᄋ ᅮ ᆫ ᄏ ᅥᄂ ᅥ ᆯ ᄂ ᅳ ᆼᄒ ᅧ ᆼᄒ ᅬᄀ ᅱ ᄇ ᅡ ᆼᄇ ᅥ ᆸᄋ ᅳ ᆯ ᄌ ᅦᄋ ᅡ ᆫᄒ ᅡᄋ ᅧ ᆻᄃ ᅡ. ᄌ ᅦᄋ ᅡ ᆫ ᄃ ᅬ ᆫ ᄇ ᅡ ᆼᄇ ᅥ ᆸᄋ ᅳ ᆫ ᄀ ᅵᄌ ᅩ ᆫ ᄋ ᅴ ᄇ ᅮ ᆫ ᄒ ᅡ

ᆯᄌ ᅥ ᆼᄇ ᅩ ᆨ KRRᄋ ᅵᄂ ᅡ ᄅ ᅢ ᆫᄃ ᅥ ᆷᄉ ᅳᄏ ᅦᄎ ᅵ KRRᄇ ᅩᄃ ᅡ ᄌ ᅡ ᆨᄋ ᅳ ᆫ ᄀ ᅨᄉ ᅡ ᆫ ᄆ ᅵ ᆾ ᄌ ᅥᄌ ᅡ ᆼ ᄇ ᅵᄋ ᅭ ᆼᄋ ᅳ ᆯ ᄀ ᅡᄌ ᅵ ᆫᄃ ᅡ. ᄆ ᅩᄋ ᅴᄉ ᅵ ᆯᄒ ᅥ ᆷ ᄆ ᅵ ᆾ ᄉ ᅵ ᆯᄌ ᅦ ᄌ ᅡᄅ ᅭᄋ ᅴ ᄇ

ᅮ ᆫᄉ ᅥ ᆨᄋ ᅳ ᆯ ᄐ ᅩ ᆼ ᄒ ᅢ ᄌ ᅦᄋ ᅡ ᆫ ᄇ ᅡ ᆼᄇ ᅥ ᆸᄋ ᅴ ᄉ ᅥ ᆼᄂ ᅳ ᆼ ᄆ ᅵ ᆾ ᄋ ᅲᄋ ᅭ ᆼᄉ ᅥ ᆼᄋ ᅳ ᆯ ᄒ ᅪ ᆨ ᄋ ᅵ ᆫᄒ ᅡᄋ ᅧ ᆻᄃ ᅡ.

ᄌ

ᅮᄋ ᅭᄋ ᅭ ᆼ ᄋ ᅥ: ᄅ ᅢ ᆫᄃ ᅥ ᆷᄉ ᅳᄏ ᅦᄎ ᅵ, ᄇ ᅮ ᆫ ᄒ ᅡ ᆯᄌ ᅥ ᆼᄇ ᅩ ᆨ, ᄏ ᅥᄂ ᅥ ᆯ ᄂ ᅳ ᆼᄒ ᅧ ᆼᄒ ᅬᄀ ᅱ.

1. 서론 ᄇ

ᅡᆫ응변수 Y ∈ R와 공변량 X ∈ R^p로 이루어진 자료 {(x1, y1), ..., (xn, yn)}에 대한 회귀모형 Y = f (X) + ϵ을고려하자. 여기서 오차항 ϵ은평균이 0인 정규분포를따른다고 가정하자. 비모수 회귀함수 ᄋ

ᅴ 추정은 통계학의 고전적 문제 중하나로 무한차원의 회귀함수 f를추정하기 위해 f를어떤 함수 공 가

ᆫ으로 국한시키는지에 따라 다양한 종류의 추정방법이 연구되어왔으며, 이에 대한 내용은 Gyorfi 등 (2002), Wasserman (2006) 등에 잘 정리되어 있다. 이 가운데 대표적인 방법 중하나는 f 를양의 준 저

ᆼ부호 (positive semidefinite) 커널함수 K : R^p× R^p→ R에 의해 만들어지는재생성 커널 힐버트 공 ᄀ

ᅡᆫ (reproducing kernel Hilbert space; RKHS)에 제약시키는것이며, RKHS기반 방법들에 대한 추정 ᄋ

ᅩ차의 한계에 대해 많은연구가 진행되어왔다 (Koltchinskii, 2006; Mendelson, 2002; van de Geer, 2000). 이러한 가정 하에서, f의 힐버트 노름 (norm)의 제곱을벌점항으로 하고 반응변수와 회귀함수 f의 차이에 대한 제곱합을최소화 함을 통해 회귀함수 f를추정할 수 있으며, 이 방법을커널 능형회귀 (kernel ridge regression; KRR)이라고 한다. 균일화 모수가 적절히 선택되었을 때, KRR추정량은 다 ᄋ

ᅣᆼ한 클래스의 커널에 대해 최소극대화 (minimax) 예측오차를가짐이 알려져 있으며 (Yang 등, 2017) ᄀ

ᅳ 유용성을바탕으로 널리 이용되고 있다 (Hastie 등, 2001).

†

ᄋ ᅵ ᄂ ᅩ ᆫᄆ ᅮ ᆫᄋ ᅳ ᆫ 2018ᄂ ᅧ ᆫᄃ ᅩ ᄌ ᅥ ᆼᄇ ᅮ(ᄀ ᅭᄋ ᅲ ᆨ ᄇ ᅮ)ᄋ ᅴ ᄌ ᅢᄋ ᅯ ᆫ ᄋ ᅳᄅ ᅩ ᄒ ᅡ ᆫᄀ ᅮ ᆨᄋ ᅧ ᆫᄀ ᅮᄌ ᅢᄃ ᅡ ᆫᄋ ᅴ ᄌ ᅵᄋ ᅯ ᆫᄋ ᅳ ᆯ ᄇ ᅡ ᆮᄋ ᅡ ᄉ ᅮᄒ ᅢ ᆼᄃ ᅬ ᆫ ᄀ ᅵᄎ ᅩᄋ ᅧ ᆫᄀ ᅮᄉ ᅡᄋ ᅥ ᆸᄋ ᅵ ᆷ (NRF- 2018R1D1A1B07047654).

1

(02841) ᄉ ᅥᄋ ᅮ ᆯᄐ ᅳ ᆨᄇ ᅧ ᆯᄉ ᅵ ᄉ ᅥ ᆼᄇ ᅮ ᆨ ᄀ ᅮ ᄋ ᅡ ᆫᄋ ᅡ ᆷᄅ ᅩ 145 ᄀ ᅩᄅ ᅧᄃ ᅢᄒ ᅡ ᆨᄀ ᅭ ᄐ ᅩ ᆼ ᄀ ᅨᄒ ᅡ ᆨᄀ ᅪ, ᄃ ᅢᄒ ᅡ ᆨᄋ ᅯ ᆫᄉ ᅢ ᆼ.

2

ᄀ ᅭᄉ ᅵ ᆫᄌ ᅥᄌ ᅡ : (21985) ᄋ ᅵ ᆫᄎ ᅥ ᆫᄀ ᅪ ᆼᄋ ᅧ ᆨᄉ ᅵ ᄋ ᅧ ᆫᄉ ᅮᄀ ᅮ ᄉ ᅩ ᆼ ᄃ ᅩ1ᄃ ᅩ ᆼ ᄉ ᅩ ᆼ ᄃ ᅩᄆ ᅮ ᆫ ᄒ ᅪᄅ ᅩ 119, ᄒ ᅡ ᆫᄀ ᅮ ᆨ ᄂ ᅲᄋ ᅭ ᆨ ᄌ ᅮᄅ ᅵ ᆸᄃ ᅢᄒ ᅡ ᆨᄀ ᅭ ᄋ ᅳ ᆼᄋ ᅭ ᆼ ᄉ ᅮᄒ ᅡ ᆨᄐ ᅩ ᆼ ᄀ ᅨᄒ ᅡ ᆨᄀ ᅪ, ᄀ

ᅭᄉ ᅮ. E-mail: [email protected]

ᄋ

ᅵ러한 매력적인 통계적 특성에도 불구하고, 대용량 (large-scale) 자료의 분석에 있어 KRR 방법을 지

ᆨ접 적용하기에는어려움이 따른다. 크기가 n인 자료에서의 일반적인 KRR의 구현에 필요한 계산 및 ᄌ

ᅥ장 비용은 각각 O(n³), O(n²) 이며, 대용량 자료와 같이 n이 매우 큰 경우 이는 엄두도 못 낼 정 ᄃ

ᅩ의 큰규모이다. 따라서 KRR 추정치의근사적 계산을 활용하여 높은계산비용을피함과 동시에 통 ᄀ

ᅨ적 최소극대화 예측 오차의 측면에서의 최적성을유지하는방법론의 개발은 필수적이며 그 중요성이 ᄂ

ᅡ

ᆯ로 증가하고 있다. Zhang 등(2015)은크기가 n인 자료를 t개로 임의 분할하여 각 k(k = 1, ..., t)에 ᄃ

ᅢ해 KRR 추정량을 계산하고, 이들의 평균을 최종 추정량으로 하는 분할정복 (divide-and-conquer) KRR을제안하였다. 분할정복 KRR은계산 및 저장 비용으로 각각 O(n³/t²), O(n²/t²)을가진다. 또 ᄒ

ᅡᆫ Yang 등 (2017)은 n차원커널행렬을 m × n 랜덤스케치 행렬 S를이용하여 m(≪ n)차원부분공간 ᄋ

ᅳ로 사영시켜 계산하는 랜덤스케치 KRR (random sketched KRR)을제안하였다. 랜덤스케치 방법을 ᄋ

ᅵ용한근사 KRR 추정치는 m차원이차계획법의 해를구함으로써 얻을수 있으며, 계산 및 저장비용으 ᄅ

ᅩ 각각 O(m³), O(m²)을가진다.

ᄋ

ᅵ러한 기존의 연구 결과들을보완하여 본연구에서는대용량 자료의 분석을위한 KRR 방법에관해 ᄉ

ᅡ

ᆯ펴보고, 이들을결합하여 분할정복 랜덤스케치 커널 능형회귀 (divide-and-conquer random sketched kernel ridge regression)방법을제안하고자 한다. 제안 방법은 분할 수 t 및 사영 차원m이 적절히 선 태

ᆨ되었을때, 기존의 분할정복 KRR이나 랜덤스케치 KRR보다 작은계산 비용을가지면서도 예측정확 서

ᆼ 측면에서 유사한 성능을보여준다. 본 논문의 구성은다음과 같다. 먼저 2절에서는커널 능형회귀에 ᄃ

ᅢ해 간략하게 설명하고, 기존방법인 분할정복기법을이용한 커널 능형회귀 방법과 랜덤스케치 커널 ᄂ

ᅳᆼ형회귀를소개하였다. 3절에서는 분할정복 랜덤스케치 커널 능형회귀를제안하였으며, 4절에서는제 ᄋ

ᅡᆫ된방법의 유용성을모의실험과 실제 자료에 적용한 분석 결과를나타내었다.

2. 대용량 자료의 분석을 위한 커널 능형회귀 방법 ᄋ

ᅵ 장에서는 본 논문에서의 제안 방법의 공식화에 앞서 커널 능형회귀 방법 및 분할정복기법에 의한 ᄏ

ᅥ널 능형회귀, 그리고 랜덤스케치 방법을이용한 커널 능형회귀에 대해 간략히 소개하고자 한다.

2.1. 커널 능형회귀 ᄏ

ᅳ기가 n인 자료 {(x¹, y1), ..., (xn, yn)}가 주어졌을때 평균제곱오차 Ef (X) − Y )²를최소화하 느

ᆫ함수를추정하는 문제를 생각해보자. 이 때 최적의 함수는 조건부 기댓값 f^∗ := E [Y |X = x]임이 ᄌ

ᅡ

ᆯ 알려져 있다. 미지의 함수 f의 함수 공간은무한 차원이므로 아무런 제약 없이 최적화 함수 f^∗를구 ᄒ

ᅡ는 것은 불가능하며, 이를추정하기 위해서는 f^∗가 특정한 형태를 가진다는 가정이 필요하다. 이를 ᄋ

ᅱ한 대표적인 방법 중하나가 f^∗를양의 준정부호 커널 함수 K : R^p× R^p→ R에 의해 만들어지는재 새

ᆼ성 커널 힐버트 공간 (reproducing kernel Hilbert space; RKHS)에 속한다고 가정하는것이다. 이러 ᄒ

ᅡᆫ 가정 하에서 커널 능형회귀는

f := arg minˆ

f ∈H

1 2n

n

X

i=1

(yi− f (xi))²+ λ ∥f ∥²_H (2.1)

ᄋ

ᅪ 같이 최소제곱 손실함수와 힐버트 노름 (norm) ∥f ∥_H =√

< f, f >H의 제곱을벌점 (penalty)으로 ᄒ

ᅡ여 이들의 합을최소화하는형태로 표현되며, 여기서 λ > 0은 균일화 모수 (regularization parame- ter)이다. 잘 알려진 representer 정리에 의해 (2.1)의 해는적절한 ˆw1, ..., ˆwn∈ R에 대하여

f (·) =ˆ

n

X

i=1

ˆ

wiK(·, xi) (2.2)

ᄋ

ᅴ 형태로 표현될수 있다. (2.2)를이용하여 벡터-행렬 형태로 (2.1)을다시 나타내면,

ˆ

w = arg min

w∈Rⁿ

 1

2nw^TK²w −1

nw^TKy + λw^TKw



(2.3) ᄀ

ᅪ 같으며 여기서 K는 (i, j)원소로 Kij= K(xi, xj)를갖는커널 행렬이다. (2.3)의 형태는 n차원2차 ᄀ

ᅨ획법으로 QR분해 등을 통해 O(n³)의 계산 비용으로 풀수 있다. 하지만 자료의 크기 n이 매우큰경 ᄋ

ᅮ에, 계산비용O(n³)과 커널행렬 K를저장하기 위한 공간 O(n²)은 실제 적용하는데 있어큰어려움 ᄋ

ᅵ 따른다.

2.2. 분할정복 커널 능형회귀 커

ᆷ퓨터 과학에서 많이 사용하는 분할정복알고리즘은주어진 문제를소문제로 분할한 후 각각의 소문 ᄌ

ᅦ를 해결한 결과를이용하여 전체 문제를해결하는기법을 말한다. Zhang 등(2015)이 제안한 분할정 ᄇ

ᅩ

ᆨ기법에 의한 커널 능형회귀는자료를 동일한 크기로 임의로 나눈후 각각에 대해 KRR 추정량을구 ᄒ

ᅡᆫ 다음이들의 산술평균을최종적인 추정량으로 정하는기법이다. 구체적인 알고리즘은다음과 같다.

알고리즘 1 분할정복커널 능형회귀

[단계 1] 크기가 n인 자료 {(x¹, y1), ..., (xn, yn)}를서로 배반인 t개의 동일한 크기(n/t)의 부분 지

ᆸ합 G1, ..., Gt로 나눈다.

[단계 2] 각각의 i = 1, 2, ..., t에 대하여 다음과 같이 국소적 KRR 추정량을계산한다.

fˆi:= arg min

f ∈H

1

|Gi| X

(x,y)∈G_i

(yi− f (xi))²+ λ ∥f ∥²_H (2.4)

ᄋ

ᅧ기서 |Gi|는부분집합 Gi의 원소의 개수이다.

[단계 3] t개의 국소적 KRR 추정량들을평균하여 ¯f =¹_t

t

P

i=1

fˆi를최종추정량으로 정한다.

(2.4)의 실질적인 계산은 (2.3)과 같이 이루어지며, 추정하고자 하는모수 w가 R^n/t에 속하게된다.

ᄄ

ᅡ라서 국소적 KRR 추정량은 (n/t)-차원의 이차 계획법에 의해 구해지고, 이러한 계산을 t번 반복하므 ᄅ

ᅩ 최종추정량 ¯f 를구하는데에 드는계산 비용과 저장 공간은각각 O(n³/t²)와 O(n²/t²)이다.

2.3. 랜덤스케치 커널 능형회귀 ᄅ

ᅢᆫ덤스케치 또는 랜덤 사영(projection)은고차원자료를저차원에서 다루기 위해 이용되는대표적인 ᄎ

ᅡ원 축약 방법이다. Yang 등(2017)은 랜덤스케치 기법을이용하여, n차원의 커널 행렬의 행공간과 열 ᄀ

ᅩ

ᆼ간을 랜덤하게 선택된 l(≪ n)차원의 부분 공간으로 사영하여근사시키는방법을제안했다. 이를 위 ᄒ

ᅢ (2.3)에서의 원래의 모수 w ∈ Rⁿ가 Rⁿ의 l차원부분 공간 R^l에 속한다고 가정하자. 랜덤스케치 행 려

ᆯ S ∈ R^l×n와 l차원벡터 v에 대해 w = S^Tv로 두고 (2.3)에 대입하면, (2.3)은