Хеширование функций

В машинном обучении хеширование признаков , также известное как трюк хеширования (по аналогии с трюком ядра ), представляет собой быстрый и экономичный способ векторизации признаков , т. е. превращения произвольных признаков в индексы в векторе или матрице. Он работает путем применения хеш-функции к объектам и использования их хеш-значений в качестве индексов напрямую (после операции по модулю), а не поиска индексов в ассоциативном массиве . Помимо использования для кодирования нечисловых значений, хеширование признаков также можно использовать для уменьшения размерности .

Этот трюк часто приписывают Вайнбергеру и др. (2009), но существует гораздо более раннее описание этого метода, опубликованное Джоном Муди в 1989 году.

Мотивация

Мотивирующий пример

В типичной задаче классификации документов входными данными для алгоритма машинного обучения (как во время обучения, так и во время классификации) является произвольный текст. На основе этого мешок слов создается представление « » (BOW): отдельные токены извлекаются и подсчитываются, и каждый отдельный токен в обучающем наборе определяет особенность (независимую переменную) каждого из документов как в обучающем, так и в тестовом наборах.

Однако алгоритмы машинного обучения обычно определяются в терминах числовых векторов. Таким образом, пакеты слов для набора документов рассматриваются как матрица терминов-документов, где каждая строка представляет собой отдельный документ, а каждый столбец представляет собой отдельный признак/слово; запись i , j в такой матрице фиксирует частоту (или вес) j -го термина словаря в документе i . (Альтернативное соглашение меняет местами строки и столбцы матрицы, но эта разница несущественна.) Обычно эти векторы чрезвычайно редки — согласно закону Ципфа .

Обычный подход состоит в том, чтобы во время обучения или до него создать словарное представление словаря обучающего набора и использовать его для сопоставления слов с индексами. Хэш-таблицы и попытки являются распространенными кандидатами на реализацию словаря. Например, три документа

• Джон любит смотреть фильмы.
• Мэри тоже любит кино.
• Джон также любит футбол.

можно преобразовать, используя словарь

Срок	Индекс
Джон	1
любит	2
к	3
смотреть	4
фильмы	5
Мэри	6
слишком	7
также	8
футбол	9

к матрице термин-документ

${\begin{pmatrix}{\textrm {John}}&{\textrm {likes}}&{\textrm {to}}&{\textrm {watch}}&{\textrm {movies}}&{\textrm {Mary}}&{\textrm {too}}&{\textrm {also}}&{\textrm {football}}\\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}}$

(Пунктуация была удалена, как это обычно бывает при классификации и кластеризации документов.)

Проблема этого процесса в том, что такие словари занимают большой объем памяти и увеличиваются в размерах по мере роста обучающего набора. Напротив, если словарный запас остается фиксированным и не увеличивается с ростом обучающего набора, злоумышленник может попытаться изобрести новые слова или орфографические ошибки, которых нет в сохраненном словаре, чтобы обойти фильтр машинного обучения. Чтобы решить эту проблему, Yahoo! Исследователи попытались использовать хеширование функций для своих спам-фильтров.

Обратите внимание, что трюк с хешированием не ограничивается классификацией текста и аналогичными задачами на уровне документа, но может быть применен к любой задаче, включающей большое (возможно, неограниченное) количество функций.

Математическая мотивация

Математически токен — это элемент $t$ в конечном (или счетно бесконечном) множестве $T$. Предположим, нам нужно обработать только конечный корпус, тогда мы можем поместить все токены, появляющиеся в корпусе, в $T$, это означает, что $T$ конечно. Однако предположим, что мы хотим обработать все возможные слова, состоящие из английских букв, тогда $T$ счетно бесконечно.

Большинство нейронных сетей могут работать только с реальными векторными входными данными, поэтому нам необходимо создать «словарную» функцию. $\phi :T\to \mathbb {R} ^{n}$.

Когда $T$ конечен, имеет размер $|T|=m\leq n$, то мы можем использовать горячее кодирование , чтобы сопоставить его с $\mathbb {R} ^{n}$. Сначала произвольно перечислим $T=\{t_{1},t_{2},..,t_{m}\}$, затем определите $\phi (t_{i})=e_{i}$. Другими словами, мы присваиваем уникальный индекс $i$ каждому токену, затем сопоставьте токен с индексом $i$ к единичному базисному вектору $e_{i}$.

Горячее кодирование легко интерпретировать, но оно требует поддержания произвольного перечисления $T$. Учитывая токен $t\in T$, чтобы вычислить $\phi (t)$, нам необходимо узнать индекс $i$ токена $t$. Таким образом, для реализации $\phi$ эффективно, нам нужна быстро вычисляемая биекция $h:T\to \{1,...,m\}$, тогда мы имеем $\phi (t)=e_{h(t)}$.

На самом деле, мы можем немного смягчить требования: достаточно иметь быстродействующую инъекцию. $h:T\to \{1,...,n\}$, затем используйте $\phi (t)=e_{h(t)}$.

На практике не существует простого способа построить эффективную инъекцию. $h:T\to \{1,...,n\}$. Однако нам нужна не строгая инъекция, а лишь приблизительная инъекция. То есть, когда $t\neq t'$, нам, вероятно, следует иметь $h(t)\neq h(t')$, так что, наверное $\phi (t)\neq \phi (t')$.

На данный момент мы только что уточнили, что $h$ должна быть хеш-функция. Таким образом, мы приходим к идее хеширования признаков.

Алгоритмы

Хеширование функций (Вайнбергер и др., 2009 г.)

Базовый алгоритм хеширования признаков, представленный в (Weinberger et al. 2009). определяется следующим образом.

Во-первых, указываются две хэш-функции: хэш ядра $h:T\to \{1,2,...,n\}$и знак хеша $\zeta :T\to \{-1,+1\}$. Далее определяется функция хеширования признаков: $$\phi :T\to \mathbb {R} ^{n},\quad \phi (t)=\zeta (t)e_{h(t)}$$Наконец, расширите эту функцию хеширования на строки токенов с помощью $$\phi :T^{*}\to \mathbb {R} ^{n},\quad \phi (t_{1},...,t_{k})=\sum _{j=1}^{k}\phi (t_{j})$$где $T^{*}$ — это набор всех конечных строк, состоящих из токенов в $T$.

Эквивалентно, $$\phi (t_{1},...,t_{k})=\sum _{j=1}^{k}\zeta (t_{j})e_{h(t_{j})}=\sum _{i=1}^{n}\left(\sum _{j:h(t_{j})=i}\zeta (t_{j})\right)e_{i}$$

Геометрические свойства

Мы хотим сказать кое-что о геометрическом свойстве $\phi$, но $T$, сам по себе является просто набором токенов, мы не можем навязать ему геометрическую структуру, кроме дискретной топологии, которая порождается дискретной метрикой . Чтобы было красивее, поднимем его на $T\to \mathbb {R} ^{T}$, и поднимите $\phi$ от $\phi :T\to \mathbb {R} ^{n}$ к $\phi :\mathbb {R} ^{T}\to \mathbb {R} ^{n}$ по линейному расширению: $$\phi ((x_{t})_{t\in T})=\sum _{t\in T}x_{t}\zeta (t)e_{h(t)}=\sum _{i=1}^{n}\left(\sum _{t:h(t)=i}x_{t}\zeta (t)\right)e_{i}$$Там бесконечная сумма, с которой надо разобраться сразу. По сути, есть только два способа обработки бесконечностей. Можно ввести метрику, а затем принять ее завершение , чтобы разрешить правильные бесконечные суммы, или можно потребовать, чтобы ничто на самом деле не было бесконечным, а только потенциально . Здесь мы идем по пути потенциальной бесконечности, ограничивая $\mathbb {R} ^{T}$ содержать только векторы с конечной поддержкой : $\forall (x_{t})_{t\in T}\in \mathbb {R} ^{T}$, только конечное число записей $(x_{t})_{t\in T}$ ненулевые.

Определите внутренний продукт на $\mathbb {R} ^{T}$ очевидным образом: $$\langle e_{t},e_{t'}\rangle ={\begin{cases}1,{\text{ if }}t=t',\\0,{\text{ else.}}\end{cases}}\quad \langle x,x'\rangle =\sum _{t,t'\in T}x_{t}x_{t'}\langle e_{t},e_{t'}\rangle$$В качестве примечания, если $T$ бесконечно, то внутреннее пространство произведения $\mathbb {R} ^{T}$ не является полным . Его завершение приведет нас к гильбертовому пространству , которое допускает корректные бесконечные суммы.

Теперь у нас есть пространство внутреннего продукта с достаточной структурой для описания геометрии функции хеширования признаков. $\phi :\mathbb {R} ^{T}\to \mathbb {R} ^{n}$.

Во-первых, мы можем понять, почему $h$ называется « хешем ядра »: он позволяет нам определить ядро $K:T\times T\to \mathbb {R}$ к $$K(t,t')=\langle e_{h(t)},e_{h(t')}\rangle$$На языке «трюка ядра» $K$ это ядро, созданное «картой функций» $$\varphi :T\to \mathbb {R} ^{n},\quad \varphi (t)=e_{h(t)}$$Обратите внимание, что это не та карта объектов, которую мы использовали. $\phi (t)=\zeta (t)e_{h(t)}$. На самом деле мы использовали другое ядро $K_{\zeta }:T\times T\to \mathbb {R}$, определяемый $$K_{\zeta }(t,t')=\langle \zeta (t)e_{h(t)},\zeta (t')e_{h(t')}\rangle$$Преимущество увеличения хеша ядра $h$ с двоичным хешем $\zeta$ является следующая теорема, которая утверждает, что $\phi$ является изометрией «в среднем».

Теорема (интуитивно сформулированная) — Если двоичный хэш $\zeta$ является несмещенным (это означает, что он принимает значение $-1,+1$ с равной вероятностью), тогда $\phi :\mathbb {R} ^{T}\to \mathbb {R} ^{n}$ представляет собой изометрию в ожидании: $$\mathbb {E} [\langle \phi (x),\phi (x')\rangle ]=\langle x,x'\rangle .$$

Доказательство

По линейности ожидания, $$\mathbb {E} [\langle \phi (x),\phi (x')\rangle ]=\sum _{t,t'\in T}(x_{t}x'_{t'})\cdot \mathbb {E} [\zeta (t)\zeta (t')]\cdot \langle e_{h(t)},e_{h(t')}\rangle$$Сейчас, $\mathbb {E} [\zeta (t)\zeta (t')]={\begin{cases}1\quad {\text{ if }}t=t'\\0\quad {\text{ if }}t\neq t'\\\end{cases}}$, поскольку мы предположили $\zeta$ является беспристрастным. Итак, мы продолжаем $$\mathbb {E} [\langle \phi (x),\phi (x')\rangle ]=\sum _{t\in T}(x_{t}x'_{t})\langle e_{h(t)},e_{h(t)}\rangle =\langle x,x'\rangle$$

Приведенное выше утверждение и доказательство интерпретируют двоичную хеш-функцию. $\zeta$ не как детерминированная функция типа $T\to \{-1,+1\}$, но как случайный двоичный вектор $\{-1,+1\}^{T}$ с несмещенными записями, что означает, что $Pr(\zeta (t)=+1)=Pr(\zeta (t)=-1)={\frac {1}{2}}$ для любого $t\in T$.

Это хорошая интуитивная картина, хотя и не строгая. Строгое утверждение и доказательство см.

Реализация псевдокода

Вместо ведения словаря векторизатор объектов, использующий прием хеширования, может построить вектор заранее определенной длины, применяя хэш-функцию h к объектам (например, словам), затем используя хеш-значения непосредственно в качестве индексов объектов и обновляя их. результирующий вектор по этим индексам. Здесь мы предполагаем, что признак на самом деле означает вектор признаков.

 function hashing_vectorizer(features : array of string, N : integer):
     x := new vector[N]
     for f in features:
         h := hash(f)
         x[h mod N] += 1
     return x

Таким образом, если наш вектор признаков ["кошка","собака","кошка"] и хеш-функция $h(x_{f})=1$ если $x_{f}$ это «кошка» и $2$ если $x_{f}$ это «собака». Возьмем размерность выходного вектора признаков ( N ) равно 4. Затем выведите x будет [0,2,1,0]. Было предложено использовать вторую однобитовую выходную хэш-функцию ξ для определения знака значения обновления, чтобы противостоять эффекту хеш-коллизий . Если используется такая хэш-функция, алгоритм становится

 function hashing_vectorizer(features : array of string, N : integer):
     x := new vector[N]
     for f in features:
         h := hash(f)
         idx := h mod N
         if ξ(f) == 1:
             x[idx] += 1
         else:
             x[idx] -= 1
     return x

Приведенный выше псевдокод фактически преобразует каждую выборку в вектор. Вместо этого оптимизированная версия будет генерировать только поток $(h,\zeta )$ пары и позвольте алгоритмам обучения и прогнозирования использовать такие потоки; линейная модель затем может быть реализована как одна хеш-таблица, представляющая вектор коэффициентов.

Расширения и вариации

Хеширование изученных функций

Хеширование функций обычно страдает от коллизий хэшей, что означает, что существуют пары разных токенов с одним и тем же хешем: $t\neq t',\phi (t)=\phi (t')=v$. Тогда модель машинного обучения, обученная на словах с хешированными признаками, будет с трудом различать $t$ и $t'$, в основном потому, что $v$ является многозначным .

Если $t'$ случается редко, то снижение производительности невелико, поскольку модель всегда может просто игнорировать редкий случай и делать вид, что все $v$ означает $t$. Однако если оба являются общими, то деградация может быть серьезной.

Чтобы справиться с этим, можно обучить контролируемые функции хеширования, которые позволяют избежать сопоставления общих токенов с одними и теми же векторами признаков.

Применение и практическое применение

Ганчев и Дредзе показали, что в приложениях классификации текста со случайными хеш-функциями и несколькими десятками тысяч столбцов в выходных векторах хеширование признаков не должно оказывать отрицательного влияния на производительность классификации, даже без знаковой хеш-функции.

Вайнбергер и др. (2009) применили свою версию хеширования функций для многозадачного обучения и, в частности, для фильтрации спама , где входные функции представляют собой пары (пользователь, функция), так что один вектор параметров фиксирует спам-фильтры для каждого пользователя, а также глобальные фильтр для нескольких сотен тысяч пользователей и обнаружил, что точность фильтра возросла.

Чен и др. (2015) объединили идею хеширования признаков и разреженной матрицы для создания «виртуальных матриц»: больших матриц с небольшими требованиями к хранению. Идея состоит в том, чтобы рассматривать матрицу $M\in \mathbb {R} ^{n\times n}$ как словарь, с ключами в $n\times n$и значения в $\mathbb {R}$. Затем, как обычно в хешированных словарях, можно использовать хеш-функцию $h:\mathbb {N} \times \mathbb {N} \to m$и, таким образом, представить матрицу в виде вектора в $\mathbb {R} ^{m}$, независимо от того, насколько большой $n$ является. Используя виртуальные матрицы, они создали HashedNets — большие нейронные сети, занимающие лишь небольшой объем памяти.

Реализации

Реализации трюка хеширования присутствуют в:

• Апач-махут
• Генерал
• scikit-learn
• София-мл
• Вовпал Ваббит
• Апач Спарк
• Р
• ТензорФлоу
• Даск-МЛ

См. также

• Фильтр Блума – структура данных для приблизительного членства в наборе
• Эскиз «Счет-мин» - Вероятностная структура данных в информатике
• Закон Кучи - эвристика для определения отдельных слов в документе
• Хеширование с учетом локальности - алгоритмический метод с использованием хеширования.
• MinHash — техника интеллектуального анализа данных

Внешние ссылки

• Хеширование представлений для машинного обучения на сайте Джона Лэнгфорда
• Что такое «хэш-трюк»? - Метаоптимизация вопросов и ответов