# 해싱 트릭## 개요

**해싱 트**(Hashing Trick)은 기 학습 및 데이터 과학 분야 고차원의 범주형 데이터를 효율적으로 처리하기 위한 기술이다. 특히 자연어 처리(NLP)나 대규모 범주형 피처를 다룰 때, 원-핫 인코딩(Oneot Encoding)과 같은 전통적인 인코 방식이 메모리와 계산 자원을 과도하게 소모하는 문제를 해결하기 위해 제안되었다. 해싱 트릭은 해시 함수를 사용하여 범주형 변수를 고정된 크기의 벡터 공간에 매핑함으로써, 메모리 사용량을 줄이고 실시간 데이터 처리를 가능하게 한다.

이 기법은 특히 스트리밍 데이터 처리나 대규모 데이터셋에서 유용하며, **Vowpal Wabbit**과 같은 고속 온라인 학습 알고리즘에서 널리 사용된다.

---

## 원리

### 범주형 데이터의 문제

범주형 변수는 특정한 값의 집합을 가지며, 예를 들어 단어, 사용자 ID, 제품 카테고리 등이 있다. 이를 기계 학습 모델에 입력하기 위해 일반적으로 **원-핫 인코딩**을 사용한다. 그러나 범주 수가 매우 클 경우(예: 100만 개의 단어), 원-핫 인코딩은 차원이 매우 높은 희소 벡터를 생성하게 되어 다음과 같은 문제가 발생한다:

- 메모리 사용량 급증
- 학습 속도 저하
- 차원의 저주(Curse of Dimensionality)

### 해싱 트릭의 해결 방식

해싱 트릭은 이러한 문제를 해결하기 위해 **해시 함수**(Hash Function)를 활용한다. 구체적인 절차는 다음과 같다:

1. 각 범주형 값(예: 단어 "apple")에 대해 해시 함수를 적용하여 고정된 정수 범위 내의 인덱스를 얻는다.
2. 이 인덱스를 기반으로 고정된 크기의 벡터(예: 10,000차원)의 해당 위치에 값을 추가(보통 1 또는 가중치)한다.
3. 결과적으로, 입력의 차원은 고정되며, 메모리 사용이 예측 가능해진다.

예를 들어, 해시 함수 `h("apple") = 123`이고, 벡터 크기를 1000으로 설정했다면, 123번 인덱스에 1을 설정한다.

```python
import hashlib

def hash_feature(feature, num_features=1000):
    return int(hashlib.md5(feature.encode()).hexdigest(), 16) % num_features

# 예시
print(hash_feature("apple", 1000))  # 예: 123
print(hash_feature("banana", 1000)) # 예: 456
```

---

## 장점과 단점

### 장점

| 장점 | 설명 |
|------|------|
| **메모리 효율성** | 고정된 차원을 사용하므로 메모리 사용량이 예측 가능하고 제한된다. |
| **사전 지식 불필요** | 전체 범주 집합을 미리 알 필요 없으며, 스트리밍 데이터에 적합하다. |
| **빠른 처리 속도** | 해시 함수는 계산이 빠르며, 실시간 처리에 유리하다. |
| **확장성** | 대규모 데이터셋이나 무제한 범주에도 적용 가능하다. |

### 단점

| 단점 | 설명 |
|------|------|
| **해시 충돌**(Hash Collision) | 서로 다른 입력이 동일한 해시 값을 가져 벡터의 동일한 위치에 매핑될 수 있다. 이는 정보 손실이나 노이즈를 유발할 수 있다. |
| **역변환 불가능** | 해싱은 일방향 함수이므로, 인코딩된 벡터에서 원래 값을 복원할 수 없다. |
| **성능 저하 가능성** | 충돌이 심할 경우 모델 정확도가 떨어질 수 있다. |

---

## 응용 분야

### 자연어 처리 (NLP)

해싱 트릭은 문서 분류, 감성 분석, 토픽 모델링 등에서 단어를 벡터로 변환할 때 유용하다. TF-IDF나 카운트 벡터화 전처리 단계에서 해싱을 사용하면, 어휘 사전을 저장하지 않고도 고차원 피처 공간을 구성할 수 있다.

### 추천 시스템

사용자 ID, 아이템 ID, 태그 등의 범주형 피처를 처리할 때 해싱 트릭을 적용하여 임베딩 공간을 효율적으로 구성할 수 있다.

### 온라인 학습

Vowpal Wabbit, Apache Spark MLlib 등에서는 해싱 트릭을 기반으로 실시간 데이터를 처리하며, 모델을 지속적으로 업데이트한다.

---

## 파라미터 선택

해싱 트릭의 성능은 다음과 같은 파라미터에 크게 영향을 받는다:

- **벡터 차원**(num_features): 너무 작으면 충돌 증가, 너무 크면 메모리 낭비. 일반적으로 2^16 ~ 2^20 사이 사용.
- **해시 함수**: `MD5`, `SHA-1`, `MurmurHash` 등 충돌 확률이 낮고 계산이 빠른 함수 선호.
- **피처 조합**: 여러 피처를 조합해 해싱할 수 있으며, 이는 상호작용 효과를 포착하는 데 도움이 된다.

---

## 관련 기술

- **피처 해싱**(Feature Hashing): 해싱 트릭의 또 다른 이름.
- **임베딩**(Embedding): 딥러닝에서 사용하는 고차원 범주를 저차원 밀집 벡터로 매핑하는 기법. 해싱 트릭과 달리 학습을 통해 매핑을 최적화한다.
- **부트스트랩 샘플링**, **온라인 학습**: 해싱 트릭과 함께 대규모 데이터 처리 파이프라인에서 활용된다.

---

## 참고 자료

- Weinberger, K., Dasgupta, A., Langford, J., Smola, A., & Attenberg, J. (2009). [Feature Hashing for Large Scale Multitask Learning](https://arxiv.org/abs/0902.2206). *ICML*.
- Wikipedia: [Feature hashing](https://en.wikipedia.org/wiki/Feature_hashing)
- Vowpal Wabbit 공식 문서: [https://github.com/VowpalWabbit/vowpal_wabbit](https://github.com/VowpalWabbit/vowpal_wabbit)

해싱 트릭은 대용량 데이터 환경에서 실용적인 솔루션을 제공하며, 오늘날의 스케일러블 머신러닝 시스템 설계에 중요한 역할을 하고 있다.