피쳐 해싱

머신러닝에서 해싱 트릭(커널 트릭과 유사하게)이라고도 하는 피쳐 해싱은 피쳐를 벡터나 매트릭스의 지수로 바꾸는 빠르고 공간 효율적인 방법이다.^[1][2]그것은 연관 배열에서 지수를 찾는 것이 아니라 형상에 해시함수를 적용하고 그 해시 값을 직접 지수로 사용하여 작동한다.이러한 수법은 흔히 와인버거 외 연구진에 기인하는 경우가 많지만, 1989년 존 무디스가 발표한 이 방법에 대한 훨씬 이전의 서술이 존재한다.^[2][1]

동기부여 사례

일반적인 문서 분류 과제에서 기계 학습 알고리즘(학습과 분류 모두 중)에 대한 입력은 자유 텍스트다.이를 통해 단어(BOW) 표현 한 봉지가 구성되는데, 개별 토큰을 추출하여 계수하고, 교육 세트에서 각각의 구별되는 토큰은 교육 세트와 시험 세트 모두에서 각 문서의 특징(독립 변수)을 정의한다.

그러나 기계 학습 알고리즘은 일반적으로 숫자 벡터 단위로 정의된다.따라서 문서 집합의 단어 봉지는 각 행이 단일 문서인 용어 문서 행렬로 간주되며, 각 열은 단일 특징/단어인 경우, 이러한 행렬의 항목 i, j는 문서 i에 있는 어휘의 j번째 기간의 빈도(또는 가중치)를 캡처한다.(대체 협약은 ma의 행과 열을 교환한다.trix, 그러나 이 차이는 중요하지 않다.)일반적으로 이러한 벡터는 극히 희박하다. Zipf의 법칙에 따르면.

공통적인 접근방식은 학습 시간이나 그 이전에 훈련 집합의 어휘에 대한 사전 표현을 구성하고, 그것을 사용하여 단어를 지수에 매핑하는 것이다.해시 테이블과 시도는 사전 구현을 위한 일반적인 후보들이다.예: 세 가지 문서

• 존은 영화 보는 것을 좋아한다.
• Mary도 영화를 좋아한다.
• 존은 또한 축구를 좋아한다.

사전을 사용하여 변환할 수 있다.

용어집합까지

${\displaystyle{\begin{pmatrix}{\textrm{존}}&{\textrm{ 좋아한다}}&{\textrm{에}}&{\textrm{ 보}}&{\textrm{영화}}&{\textrm{메리}}&{\textrm{너무}}&{\textrm{또한}}&{\textrm{축구}}\\1&, 1&, 1&, 1&, 1&, 0&, 0&, 0&, 0\\0&, 1&, 0&, 0&, 1&, 1&, 1&, 0&, 0\\1&, 1&, 0&, 0&, 0&.앰프, 0&, 0&, 1&, 1\end{pmatrix}}}$

(문서 분류 및 클러스터링에서 흔히 볼 수 있듯이 형식은 제거되었다.)

이런 과정의 문제는 이런 사전이 많은 저장공간을 차지해 훈련 세트가 커질수록 크기가 커진다는 점이다.^[3]반대로 어휘가 고정되어 있고 늘어나는 훈련 세트로 증가하지 않는다면, 적수는 기계 학습 필터를 우회하기 위해 저장된 어휘에 없는 새로운 단어나 오자를 발명하려고 할 수 있다.이러한 어려움은 야후에서 기능 해싱이 스팸 필터링에 시도된 이유다. 연구하다.^[4]

해싱 트릭은 문서 수준에서 텍스트 분류 및 유사한 작업에만 국한되는 것이 아니라 많은 수의 기능(아마도 무한)을 수반하는 모든 문제에 적용할 수 있다는 점에 유의하십시오.

해싱 트릭을 이용한 피쳐 벡터화

해싱 트릭을 사용하는 피쳐 벡터라이저는 사전을 유지하는 대신 피쳐(예: 단어)에 해시함수 h를 적용하여 미리 정의된 길이의 벡터를 구축한 다음, 해시 값을 피쳐 인덱스로 직접 사용하고 그 지수에서 결과 벡터를 업데이트할 수 있다.여기서는 형상이 실제로 형상 벡터를 의미한다고 가정한다.

 기능을 하다 해싱_파쇄기(특징들 : 배열하다 의 끈을 매다, N : 정수의):      x := 새로운 벡터[N]      을 위해 f 에 특징들:          h := 해시하다(f)          x[h 모드의 N] += 1      돌아오다 x 

따라서 우리의 형상 벡터가 ["cat","dog","cat"이고 해시함수가 $h{\displaystyle }$ ${\displaystyle s}$ ${\displaystyle h(}$ ${\displaystyle {}_{}}$ ${\displaystyle f_{}}$)${\displaystyle }$= 1 ${\displaystyle hash(x_{f}}}=1}$인 ${\displaystyle {경우}_{}}$ x$$f {\$displaystyle x_{$f$$}}}는 "cat"이고$$$$ $2{\displaystyle {}_{}}$ ${\displaystystyle$ }은 "2}이다$.$출력 피쳐 벡터 치수를 선택하자(N)은 4가 된다.그러면 출력 x는 [0,2,1,0]이 될 것이다.해시 충돌의 영향에 대항하기 위해 업데이트 값의 기호를 결정하는 데 두 번째 단일 비트 출력 해시 함수 ξ을 사용할 것을 제안하였다.^[2]그러한 해시함수를 사용하면 알고리즘은

 기능을 하다 해싱_파쇄기(특징들 : 배열하다 의 끈을 매다, N : 정수의):      x := 새로운 벡터[N]      을 위해 f 에 특징들:          h := 해시하다(f)          idx := h 모드의 N          만일 ξ(f) == 1:              x[idx] += 1          다른:              x[idx] -= 1      돌아오다 x 

위의 가성소드는 실제로 각 표본을 벡터로 변환한다.대신에 최적화된 버전은 (h,h) 쌍의 스트림을 생성하고 학습과 예측 알고리즘이 그러한 스트림을 소비하게 할 것이다. 그러면 선형 모델은 계수 벡터를 나타내는 단일 해시 테이블로 구현될 수 있다.

특성.

두 번째 해시함수 ξ을 사용하여 형상의 값 부호를 결정하면, ξ로 인해 일부 충돌이 취소되기 때문에 출력 배열의 각 열의 기대 평균은 0이 된다.^[2]예를 들어, 입력에 서로 충돌하는 두 가지 상징적 특징 f₁과 f₂이 있지만 동일한 입력의 다른 특징과 충돌하지 않는다고 가정하면, about에 대해 가정을 하지 않으면 오른쪽 표에 열거된 것과 같이 동일한 확률을 갖는 네 가지 가능성이 있다.

이 예에서 해시 충돌은 상쇄될 확률이 50%이다.여러 해시함수를 사용하여 충돌 위험을 더욱 줄일 수 있다.^[5]

더욱이 φ이 기호 해시 ξ(즉, φ(x)는 표본 x에 대해 생성된 형상 벡터)로 해싱 트릭에 의해 구현되는 변환이라면 해시 공간의 내부 제품은 다음과 같이 편향되지 않는다.

${\displaystyle \mathb {E}[\langle \varphi (x),\varphi (x')\angle ]=\langle x,x'\angle }$

해싱 함수 φ에 대한 기대치가 있는 경우.^[2]${\displaystyle }$ (${\displaystyle x}$) ,${\displaystyle {}^{}}$ ( x ${\displaystyle {\prime }^{}}$ )$($ {\$displaystyle \langle$ \langle $\varphi (x),\varphi (x')\angle }}$이(가) 양의 반확정성 커널임을 확인할 수 있다.^[2][6]

확장 및 변형

최근의 연구는 해싱 트릭을 단어에서 지수로 감독하는 매핑으로 확장하는데,^[7] 해싱 트릭은 중요한 용어의 충돌을 피하기 위해 명백하게 학습된다.

애플리케이션 및 실제 성능

간체프와 준설주는 무작위 해시함수와 출력 벡터에 수만 개의 열이 있는 텍스트 분류 어플리케이션에서 형상 해시는 서명된 해시함수가 없어도 분류 성능에 악영향을 미칠 필요가 없다는 것을 보여주었다.^[3]Weinberger 등에서는 해싱의 변형을 스팸 필터링 문제에 적용하여 이것을 입력 기능이 쌍(사용자, 기능)인 다중 작업 학습 문제로서 형성하여 사용자별 단일 파라미터 벡터가 수십만 명의 글로벌 필터뿐만 아니라 사용자별 스팸 필터를 캡처하도록 하고, 해싱의 정확도를 알아냈다.필터가 올라갔다.^[2]

구현

해싱 트릭의 구현은 다음과 같다.

• 아파치 마후트^[5]
• 겐심^[8]
• 스키키트^[9]
• 소피아-ml^[10]
• 서약팔 와빗
• 아파치 스파크^[11]
• R^[12]
• 텐서플로우^[13]
• 다스크-ML^[14]

참고 항목

• 블룸 필터
• 카운트-최소 스케치
• 힙스 법칙
• 지역감응 해싱
• 민해시

참조

외부 링크

• John Langford의 웹사이트에 기계 학습을 위한 해싱 표현
• "해싱 트릭"이란? - MetaOptimize Q+A