Feature Hashing for Large Scale Multitask Learning

제목: Feature Hashing for Large Scale Multitask Learning

저자: Weinberger et al.

출처: Yahoo! Research

원문: https://arxiv.org/pdf/0902.2206.pdf

일시: 2010.02.27

요약

Hashing trick을 소개하고, multi-task learning에 적용함

Paper Abstract. 

Empirical evidence suggests that hashing is an effective strategy for dimensionality reduction and practical nonparametric estimation. In this paper we provide exponential tail bounds for feature hashing and show that the interaction between random subspaces is negligible with high probability. We demonstrate the feasibility of this approach with experimental results for a new use case — multitask learning with hundreds of thousands of tasks.

생각

 원래는 지금 하고 있는 업무 때문에 Hashing Trick이 세부 내용을 확인하기 위해서 다시 읽었지만, 해싱트릭의 기본은 매우 간단하고 중간에 나열한 여러 속성이나 증명은 굳이 더 자세히 알 필요가 없지만 (수식과 이론을 바탕으로 새로운 이론을 도출해서 논문을 쓸 계획이 없기 때문에), 후반부 (Application)에 소개된 Multitask learning에 적용한 부분에서 현재 팀내에서 진행하는 다른 업무에 도움이 될 인사이트를 얻었기 때문에 이 논문을 소개합니다.

 해싱트릭 Hashing Trick은 이름에서 유추할 수 있듯이 해싱과 트릭으로 나눠서 생각할 수 있다. 먼저 해싱은 보통 y = f(x), 즉 인풋 x를 넣으면 아웃풋 y가 나오는 함수로 생각하면 된다. 우리의 관념에서 1:1 매핑의 아름다운 함수를 기대하지만, 보통 해싱함수는 N:1의 형태를 띈다. 그래서 abstract에 언급됐듯이 dimension reduction이 가능하다. 해싱을 사용하면 N차원의 데이터를 d차원 (d << N)의 데이터로 축소한다고 보면 된다. 이런 N:1 함수의 문제점은 다수의 원 데이터가 하나의 (또는 작은 수의) bin으로 매핑돼서 충돌이 발생할 가능성이 있다. 그럼에도 불구하고 차원을 축소함으로써 얻는 이득이 많기 때문에 해싱이 (computationally) 효과적이다. 해싱충돌 (collision)을 최소화하는 차원 d나 해싱함수를 선택하는 것이 중요하고, 때로는 다수의 해싱을 사용해서 충돌을 최대한 방어할 수도 있다. 보통 수십만에서 수천만 이상의 데이터를 수백, 수천 차원으로 줄이기 때문에 2~3개 이상의 해싱을 사용하면 충돌을 거의 막으면서 원래 데이터의 속성을 유지할 수있다.

 두번째로 trick은 흔히 SVM (Support Vector Machine)으로 알려진 Kernel machines에서 말하는 (Kernel) trick의 그것과 동일하다. 즉, 원래 데이터 또는 변형된 데이터가 무엇이냐를 명시적으로 보지 않고, 두 개의 벡터 (또는 변형된 벡터)의 관계 (보통은 유사도)만을 계산하면 된다. 즉, 커널머신에서 커널이란 보통 유사도의 다른 의미로 사용되는데, x1과 x2의 유사도를 계산하기 위해서 <phi(x1), phi(x2)>처럼 phi함수로 차원을 확장하고 그 둘 사이의 연산으로 구하는 것이 (쉽게 말해서) 커널 트릭이다. 그런데 해싱트릭은 앞서 해싱이 차원을 축소하는 기술이라 설명했듯이, 커널트릭과 반대로 차원을 축소해서 원래 유사도를 구하는 방식이라고 보면 된다. 수백만 차원의 데이터 x1과 x2 간의 유사도를 구하는 것이 아니라, 축소된 수십/수백 차원의 데이터 x1'와 x2' 간의 유사도를 구하는 것이다.

 앞서 해싱충돌도 언급했지만, 문제는 원래 데이터 간의 유사도 (OS = Sim(x1, x2))와 축소된 데이터 간의 유사도 (RS = Sim(x1', x2'))가 완전히 같지는 않다는 점이다. 하지만, OS와 RS 간의 차이가 별로 크지 않다는 것 (|OS - RS| < e)을 설명해주는  Johnson–Lindenstrauss lemma (https://en.wikipedia.org/wiki/Johnson%E2%80%93Lindenstrauss_lemma)라는 이론이 있다. 하지만, 통상적으로 e의 범위가 매우 적을 것으로 기대하겠지만, 실은 0에서 1사이라는 점이 함정이다. 하지만, 앞서 말했듯이 여러 개의 해싱을 사용하는 등으로 충분히 회피 가능하다. 데이터의 차원을 축소하는 방식으로 아주 간단한 Random Projection이라는 것이 있는데, 해싱트릭은 랜덤프로젝션의 아주 특수한 케이스지만 랜덤프로젝션보다 더 나은 속성을 갖고 있다. 연산이 예측가능 (일관적)이고, sparse 데이터의 sparsity를 어느 정도 유지시켜주고, 또 함수로 연산이 되므로 프로젝션 매트릭스를 저장해둘 필요가 없다는 점 등이다.

Multitask learning은 좀 일반적인 개념이다. 간단히 말해서 하나의 식으로 여러 개의 태스트를 동시에 처리하도록 학습시키는 것이라 보면 된다. 개인화 추천에서 개개인별로 특화된 추천식을 학습시켜주는 것이 맞지만, 이렇게 되면 수백만, 수천만개의 식을 학습시켜줘야 한다. 이는 비효율적이기 때문에 하나의 추천식이 모든 개인 및 아이템별로 다른 값을 예측하도록 학습시킨다. 보통 유저 피쳐와 아이템 피쳐 간의 Cartesian Production (Conjunction)을 취해서 피쳐 수를 늘려서 하나의 예측식을 만드는 것이 보통이다. 그런데 만약 유저피쳐가 1,000개이고, 아이템 피쳐가 1,000개라면 카테시안 피쳐는 1,000,000차원이 된다. 그래서 야후나 크리테오에서 광고추천 로직에 앞서 설명한 해싱트릭으로 차원을 축소해서 사용하고 있다.

이런 (개인화된) 멀티태스크 런닝의 기본 철학은 공유할 수 있는 데이터를 공유하고, 개별 속성은 별도로 반영한다는 것이다. ... 좀더 깊게 들어가면 Transfer learning까지 들어가야 하는데, 트랜스퍼러닝은 다음 기회에...