Variable selection in reproducing kernel Hilbert space using random sketch method^†

2020, 31

4)

501–511

랜덤 스케치 기법을 활용한 재생성 커널 힐버트 공간에서의 변수선택

^†

ᄀ

ᅡᆼ종경

¹

²

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

ᄌ ᅥ

ᆸᄉ ᅮ 2020ᄂ ᅧ ᆫ 5ᄋ ᅯ ᆯ 20ᄋ ᅵ ᆯ, ᄉ ᅮᄌ ᅥ ᆼ 2020ᄂ ᅧ ᆫ 6ᄋ ᅯ ᆯ 23ᄋ ᅵ ᆯ, ᄀ ᅦᄌ ᅢ ᄒ ᅪ ᆨᄌ ᅥ ᆼ 2020ᄂ ᅧ ᆫ 7ᄋ ᅯ ᆯ 5ᄋ ᅵ ᆯ

요 약

ᄏ

ᅥᄂ ᅥ ᆯ ᄂ ᅳ ᆼᄒ ᅧ ᆼᄒ ᅬᄀ ᅱ (kernel ridge regression; KRR)ᄂ ᅳ ᆫ ᄒ ᅬᄀ ᅱᄒ ᅡ ᆷᄉ ᅮᄅ ᅳ ᆯ ᄌ ᅢᄉ ᅢ ᆼᄉ ᅥ ᆼ ᄏ ᅥᄂ ᅥ ᆯ ᄒ ᅵ ᆯᄇ ᅥᄐ ᅳ ᄀ ᅩ ᆼ ᄀ ᅡ ᆫ (repro- ducing kernel Hilbert space; RKHS)ᄋ ᅦᄉ ᅥ ᄎ ᅮᄌ ᅥ ᆼᄒ ᅡᄂ ᅳ ᆫ ᄇ ᅵᄆ ᅩᄉ ᅮᄌ ᅥ ᆨ ᄎ ᅮᄌ ᅥ ᆼ ᄀ ᅵᄇ ᅥ ᆸᄋ ᅳᄅ ᅩ, ᄆ ᅧ ᆼᄉ ᅵᄌ ᅥ ᆨ ᄆ ᅩᄒ ᅧ ᆼ ᄀ ᅡᄌ ᅥ ᆼᄋ ᅳ ᆯ ᄋ

ᅭᄀ ᅮᄒ ᅡᄌ ᅵ ᄋ ᅡ ᆭᄂ ᅳ ᆫ ᄌ ᅡ ᆼᄌ ᅥ ᆷᄋ ᅵ ᄋ ᅵ ᆻᄃ ᅡ. ᄋ ᅵᄅ ᅥᄒ ᅡ ᆫ RKHSᄒ ᅡᄋ ᅦᄉ ᅥ ᄀ ᅵᄋ ᅮ ᆯ ᄀ ᅵ ᄇ ᅦ ᆨᄐ ᅥᄃ ᅳ ᆯᄋ ᅳ ᆯ ᄒ ᅡ ᆨᄉ ᅳ ᆸ ᄒ ᅡ ᆷᄋ ᅳ ᆯ ᄐ ᅩ ᆼ ᄒ ᅢ ᄇ ᅧ ᆫᄉ ᅮ ᄉ ᅥ ᆫᄐ ᅢ ᆨᄋ ᅳ ᆯ ᄒ ᅡ ᄂ

ᅳ ᆫ ᄇ ᅡ ᆼᄇ ᅥ ᆸᄅ ᅩ ᆫ ᄋ ᅵ ᄀ ᅢᄇ ᅡ ᆯ ᄃ ᅬ ᆫ ᄇ ᅡ ᄋ ᅵ ᆻᄃ ᅡ. ᄀ ᅳᄅ ᅥᄂ ᅡ ᄌ ᅡᄅ ᅭᄋ ᅴ ᄏ ᅳᄀ ᅵᄋ ᅪ ᄇ ᅧ ᆫᄉ ᅮᄋ ᅴ ᄉ ᅮᄀ ᅡ ᄆ ᅢᄋ ᅮ ᄏ ᅳ ᆫ ᄀ ᅧ ᆼᄋ ᅮ, ᄆ ᅡ ᆭᄋ ᅳ ᆫ ᄀ ᅨᄉ ᅡ ᆫᄇ ᅵᄋ ᅭ ᆼᄋ ᅳ ᆯ ᄋ ᅭ ᄀ

ᅮᄒ ᅡᄋ ᅧ ᄀ ᅳ ᄒ ᅪ ᆯᄋ ᅭ ᆼᄉ ᅥ ᆼᄋ ᅦ ᄒ ᅡ ᆫᄀ ᅨᄀ ᅡ ᄋ ᅵ ᆻᄃ ᅡ. ᄒ ᅡ ᆫᄑ ᅧ ᆫ ᄋ ᅵ ᆯᄇ ᅡ ᆫᄌ ᅥ ᆨᄋ ᅵ ᆫ KRRᄋ ᅦᄉ ᅥ ᄀ ᅨᄉ ᅡ ᆫᄇ ᅵᄋ ᅭ ᆼᄋ ᅳ ᆯ ᄌ ᅮ ᆯ ᄋ ᅵᄀ ᅵ ᄋ ᅱᄒ ᅡᄋ ᅧ ᄏ ᅥᄂ ᅥ ᆯ ᄒ ᅢ ᆼᄅ ᅧ ᆯᄋ ᅳ ᆯ m ᄎ ᅡᄋ ᅯ ᆫ ᄅ ᅢ ᆫᄃ ᅥ ᆷ ᄉ ᅳᄏ ᅦᄎ ᅵ ᄒ ᅢ ᆼᄅ ᅧ ᆯᄋ ᅳ ᆯ ᄋ ᅵᄋ ᅭ ᆼ ᄒ ᅡᄋ ᅧ ᄀ ᅳ ᆫ ᄉ ᅡ ᄉ ᅵᄏ ᅵᄂ ᅳ ᆫ ᄀ ᅵᄇ ᅥ ᆸᄋ ᅵ ᄀ ᅢᄇ ᅡ ᆯ ᄃ ᅬ ᆫ ᄇ ᅡ ᄋ ᅵ ᆻᄃ ᅡ. ᄇ ᅩ ᆫ ᄋ ᅧ ᆫᄀ ᅮᄋ ᅦᄉ ᅥᄂ ᅳ ᆫ RKHS ᄋ ᅦ ᄉ

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

ᅴᄉ ᅵ ᆯᄒ ᅥ ᆷ ᄆ ᅵ ᆾ ᄉ ᅵ ᆯᄌ ᅦ ᄉ ᅡᄅ ᅨ ᄇ ᅮ ᆫᄉ ᅥ ᆨᄋ ᅳ ᆯ ᄐ ᅩ ᆼ ᄒ ᅢ ᄒ ᅪ ᆨ ᄋ ᅵ ᆫᄒ ᅡᄋ ᅧ ᆻᄃ ᅡ.

ᄌ

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

1. 서론 ᄀ

ᅵ술의 급속한 발전은고차원데이터 분석과 같은현대 통계 기법에 대한 수요 증가로 이어졌다. 일반 ᄌ

ᅥᆨ으로 고차원적 데이터를 분석하는데 있어 소수의 변수만이 의미있는정보를제공하며 다른변수들은 ᄌ

ᅡ

ᆸ음으로 간주한다. 따라서 의미있는변수만을 식별하는것은고차원데이터 분석의 주요 목표 중하나 ᄋ

ᅵ며 의학 (Kim 등, 2016),사회과학 (Min과 Choi, 2016) 그리고 경제학 (Smith 등, 2019) 등많은 실 ᄌ

ᅦ 문제의 응용에활용되었다. 이에 다양한 형태의 모형에 대한 가정 하에 많은변수 선택 기법이 개발 ᄃ

ᅬ었다.

ᄉ

ᅥᆫ형 모형의 가정 하에서는벌점화 회귀 모형이 변수 선택에서 널리 이용되었으며, LASSO (Tibshi- rani, 1996), SCAD (Fan과 Li, 2001), elastic net (Zou와 Hastie, 2003), 적응적 LASSO (Zou, 2006) 등 ᄋ

ᅵ 개발되었다. 이러한 방법들은최소제곱 손실함수에 벌점화를연관시킴으로써 회귀함수의 희박한 표 ᄒ

ᅧᆫ을유도하며, 해당 회귀 계수가 0인지에 따라 변수 선택으로 이어진다. 보다 가정을완화시킨 비모수 ᄌ

ᅥᆨ 가법 모형의 가정에서도 다양한 방법들이 개발되어왔다 (Huang과 Yang, 2004; Lin과 Zhang, 2006;

Huang 등, 2010). 이와 같은방법들은그 뛰어난 성능에도 불구하고 실제 모형이 선형성 또는가법성이

†

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

1

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

2

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

ᅭᄉ ᅮ. E-mail: myoungshic.jhun@stonybrook.edu

ᄅ

ᅡ는가정을 충족시키지 못할 경우에는그 효용성이 저하되며, 변수들의 일반적인 영향들을반영하지 못 ᄒ

ᅡ게된다.

ᄋ

ᅵ에 Yang 등 (2016)은 재생성 커널 힐버트 공간 (reproducing kernel Hilbert space; RKHS)에서 ᄒ

ᅬ귀함수의 기울기 (gradient) 함수를 학습함을 통해 유의한 변수를선택할 것을제안하였다. 이 방법 ᄋ

ᅳ

ᆫ기존의 기울기 함수의 추정에관한 연구 (Mukherjee와 Zhou, 2006; Ye와 Xie, 2012)의 결과에 그룹 LASSO 벌점함수 (Yuan과 Lin, 2006; Wang과 Leng, 2008)의 아이디어를결합해 기울기 함수를추정 ᄒ

ᅡᆷ과 동시에 변수 선택을 동시에 수행한다. 이 방법이 갖는주요 장점은선형성 또는가법성같은모형의 ᄀ

ᅮ체적인 형태에관한 가정을요구하지 않기 때문에 변수들이 회귀 함수에 미치는다양한 영향들을 포 ᄎ

ᅡ

ᆨ한다는것이다. 또한 RKHS하에서의 함수 추정에 주로 사용되는 RKHS노름 (norm) 형태의 벌점함 ᄉ

ᅮ 대신에 그룹 LASSO 형태의 벌점함수를적용하여, 유의하지 않은변수에 해당하는기울기 벡터의 계 ᄉ

ᅮ들을 효과적으로 축소 추정할 수 있으며, 블록좌표하강법 (blockwise coordinate descent) 알고리즘 (Yang과 Zhou, 2015)을 통해 효과적인 추정이 가능하다. 그러나 분석하고자 하는자료의 크기 n과 변 ᄉ

ᅮ의 수 p가 매우큰경우, D번의 반복계산을 통해 O(n²p²D)의 계산 비용을요구하게 되므로, 대용량 (large-scale)자료의 분석에서의활용에는어려움이 있다.

ᄒ

ᅡᆫ편 일반적인 커널 능형회귀 (kernel ridge regression)에서도 대용량 자료의 분석을 위한 다양한 ᄀ

ᅵ법들이 개발되어 왔다. 자료의 크기가 n인 대용량 자료에 대해 Zhang 등(2015)은 자료를 t개로 이

ᆷ의 분할하여 각 k (k = 1, ..., t)에 대해 커널 능형회귀를 추정하고, 추정한 함수들의 평균값을 최 ᄌ

ᅩ

ᆼ 추정 함수로 하는 분할정복 (divide-and-conquer) KRR을 제안하였으며 이를 위한 계산 비용으 ᄅ

ᅩ O(n³/t²)을 요구한다. 또한 Yang 등 (2017)은 랜덤 스케치 방법을 활용하여 n차원 커널행렬을 m(≪ n)차원 부분공간으로 사영시켜 커널 능형회귀의 추정과정을 수행하는 랜덤 스케치 KRR (ran- dom sketched KRR)을제안하였으며, 계산비용으로 O(m³)을가진다. 이 두 방법의 장점을결합하여 Kang과 Jhun (2020)은 분할정복 랜덤 스케치 KRR을제안하여 계산비용으로 l < m에 대해 O(tl³+ ln²/t)을가짐을보였다.

ᄋ

ᅵ러한 기존의 연구 결과들을살펴보고 보완하여 본연구에서는고차원자료의 효율적인 분석을위한 RKHS기반 변수선택 기법을제안하고자 한다. 제안방법은기존의 RKHS에서의 기울기 학습기법에 비 ᄒ

ᅢ 보다 작은계산 비용을가지면서도 예측정확성 측면에서 유사한 성능을보여준다. 본 논문의 구성 ᄋ

ᅳ

ᆫ다음과 같다. 먼저 2절에서는커널 능형회귀에 대해 간략하게 소개하고, 기존방법인 랜덤 스케치 커 ᄋ

ᅦ널 능형회귀와 RKHS에서의 기울기 학습기법을소개하였다. 3절에서는 랜덤 스케치 기법을활용한 RKHS에서의 기울기 학습기법을 제안하였으며, 4절에서는 제안된방법의 유용성을모의실험 및 실제 ᄉ

ᅡ례 분석을 통해확인하였다.

2. RKHS에서의 커널 회귀 방법론 보

ᆫ연구에서 제안하는고차원자료의 효율적인 분석을위한 RKHS기반 변수선택 기법의 공식화에 앞 ᄉ

ᅥ 이 장에서는커널 능형회귀에 대해 알아보고, 제안방법의근간이 되는기존연구인 랜덤 스케치 커널 ᄂ

ᅳᆼ형회귀 그리고 RKHS기반 변수선택 기법에 대해 간략히 소개하고자 한다.

2.1. 커널 능형회귀 후

ᆫ련자료 (xⁱ, yi); i = 1, ..., n가 알려지지 않은 어떤 결합 분포로부터 추출한 독립 표본이라고 하자.

ᄋ

ᅧ기서 xi = (xi1, ..., xip)^T ∈ R^p 는 p차원 공변량, yi ∈ R은반응변수이다. 다음과 같은회귀 모형을 ᄀ

ᅩ려하자.

y = f^∗(x) + ϵ,

ᄋ

ᅧ기서 E(ϵ|x) = 0, V ar(ϵ|x) = σ², x = (x⁽¹⁾, ..., x^(p))^T 이며, f^∗는두 번 미분가능한 참 회귀 함수이 ᄃ

ᅡ. 편의상 오차항 ϵ은평균이 0인 정규분포를따른다고 가정하자. 이러한 자료를 분석하는데 있어서 ᄋ

ᅴ 주된 관심사는평균제곱오차

E(f (x) − Y )²

(2.1) ᄅ

ᅳᆯ 최소화하는 함수를 추정하는 것이다. 이 때 (2.1)을 최소화하는 최적의 함수는 조건부 기댓값 E [Y |x]임을 보일 수 있다. 여기서 함수 f^∗가 될 수 있는 후보는 무한히 많으므로, 아무런 제약 없 ᄋ

ᅵ f^∗를추정하는것은 불가능하다. 따라서 통계학에서는 f^∗의 추정량에 대한 후보로 특정한 형태를가 저

ᆼ하는데, 선형 모형 f^∗(x) = x^Tβ,가법 모형 f^∗(x) = g1(x⁽¹⁾) + · · · gp(x^(p))이 이에 대한 대표적인 ᄋ

ᅨ이다. 그러나 많은경우 실제 f^∗는이러한 가정을 충족시키지 못하므로, f^∗가 속하는함수 공간에 대 ᄒ

ᅡᆫ 보다 완화된 가정이 요구된다. 최근 가장 각광받는방법 중하나는 f^∗의 함수 공간을 양의 준정부 ᄒ

ᅩ (positive semidefinite) 커널함수 K : R^p× R^p → R에 의해 만들어지는 재생성 커널 힐버트 공간 (reproducing kernel Hilbert space; RKHS)으로 제약시키는것이며, RKHS 기반 방법론에 대해 많은 ᄋ

ᅧᆫ구가 진행되어왔다 (Koltchinskii, 2006; Mendelson, 2002; Van de Geer, 2000). 이와 같이 함수 공 ᄀ

ᅡᆫ을 RKHS로 제약시켰을때, 참 회귀 함수 f^∗를 f := argminˆ

f ∈H

(1 n

n

X

i=1

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

(2.2)

ᄋ

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

< f, f >H의 제곱을벌점 함수로 하여 이 ᄃ

ᅮ 항의 합을 최소화하는함수 ˆf 을추정하는 방법을커널 능형회귀 (kernel ridge regression; KRR)이 ᄅ

ᅡ고 한다.

ᄋ

ᅧ기서 λn > 0은 조율모수 (tuning parameter)이다. 표현 정리 (representer theorem; Wahba, 1999)에 의해 (2.2)의 해는어떤 ˆw1, ..., ˆwn∈ R에 대하여

f (·) =ˆ

n

X

i=1

ˆ

wiK(·, xi) (2.3)

ᄋ

ᅴ 형태로 표현된다. (2.3)을이용하여 (2.2)를 벡터-행렬 형태로 재표현하면,

ˆ

w = argmin

w∈Rⁿ

 1

nw^TK²w −2

nw^TKy + λnw^TKw



(2.4) ᄀ

ᅪ 같으며 여기서 K는커널행렬으로 (i, j)원소로 Kij = K(xi, xj)를 갖는다. (2.4)는 n차원 이차 계 회

ᆨ법 (quadratic programming)으로 일반적인 QR분해 등을 통해 O(n³)의 계산 비용으로 ˆw를구할 수 이

ᆻ다.

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

ᅢᆫ덤 스케치 또는 랜덤 사영 (projection)은유클리드 공간에있는 일련의 자료의 차원을 줄이는데 사 ᄋ

ᅭ

ᆼ되는대표적인 차원 축약 기법이다. Yang 등 (2017)은 랜덤 스케치 기법을이용하여, 대용량 자료에 ᄉ

ᅥ 효율적인 커널 능형회귀의 계산을 위해 n차원의 커널 행렬 K의 행공간과 열공간을 랜덤하게 선택 되

ᆫ m(≪ n)차원의 부분 공간으로 사영하여근사시킨후 계산하는방법을 제안했다. 이를위해 (2.4)에