Хеширование функций - Feature hashing - Wikipedia

В машинное обучение, хеширование функций, также известный как трюк с хешированием (по аналогии с трюк с ядром ), это быстрый и экономичный способ векторизации Особенности, т.е. превращение произвольных признаков в индексы вектора или матрицы.^[1]^[2] Он работает, применяя хэш-функция к функциям и напрямую использовать их хеш-значения в качестве индексов, а не искать индексы в ассоциативный массив. Этот трюк часто приписывают Вайнбергеру и др., Но существует гораздо более раннее описание этого метода, опубликованное Джоном Муди в 1989 году.^[2]^[1]

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

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

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

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

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

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

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

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

{ displaystyle { begin {pmatrix} { textrm {John}} & { textrm {like}} & { textrm {to}} & { textrm {watch}} & { textrm {movies}} & { textrm {Mary}} & { textrm {too}} & { textrm {also}} & { textrm {football}} 1 & 1 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 0 & 1 & 0 & 0 & 1 & 1 & 1 & 1 & 0 & 0 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1} end} {pmatrix

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

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

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

Векторизация функций с использованием хеш-трюка

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

 функция hashing_vectorizer(Особенности : множество из нить, N : целое число):     Икс := новый вектор[N]     за ж в Особенности:         час := хэш(ж)         Икс[час мод N] += 1     возвращаться Икс

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

 функция hashing_vectorizer(Особенности : множество из нить, N : целое число):     Икс := новый вектор[N]     за ж в Особенности:         час := хэш(ж)         idx := час мод N         если ξ(ж) == 1:             Икс[idx] += 1         еще:             Икс[idx] -= 1     возвращаться Икс

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

Характеристики

ξ(ж₁)	ξ(ж₂)	Конечное значение, ξ(ж₁) + ξ(ж₂)
-1	-1	-2
-1	1	0
1	-1	0
1	1	2

Когда вторая хеш-функция ξ используется для определения знака значения функции, ожидал иметь в виду каждого столбца в выходном массиве становится равным нулю, потому что ξ приводит к отмене некоторых коллизий.^[2] Например, предположим, что вход содержит две символьные функции ж₁ и ж₂ которые сталкиваются друг с другом, но не с другими объектами в одном и том же входе; то есть четыре возможности, которые, если мы не будем делать никаких предположений относительно ξ, имеют равную вероятность, как указано в таблице справа.

В этом примере существует 50% -ная вероятность того, что конфликт хеша будет отменен. Можно использовать несколько хэш-функций для дальнейшего снижения риска коллизий.^[5]

Кроме того, если φ это преобразование, реализованное с помощью хеш-трюка со знаковым хешем ξ (т.е. φ(Икс) - вектор признаков, созданный для образца Икс), тогда внутренние продукты в хешированном пространстве беспристрастны:

{ Displaystyle mathbb {E} [ langle varphi (x), varphi (x ') rangle] = langle x, x' rangle}

где ожидание берется из функции хеширования φ.^[2] Можно проверить, что ${ Displaystyle langle varphi (х), varphi (x ') rangle}$ это положительный полуопределенный ядро.^[2]^[6]

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

Недавняя работа расширяет уловку хеширования на контролируемые сопоставления слов в индексы,^[7]которые явным образом учатся избегать столкновений важных терминов.

Приложения и практическая производительность

Ганчев и Дредзе показали, что в приложениях классификации текста со случайными хэш-функциями и несколькими десятками тысяч столбцов в выходных векторах хеширование функций не обязательно должно отрицательно влиять на производительность классификации даже без хеш-функции со знаком.^[3]Weinberger et al. применили свой вариант хеширования к проблеме фильтрация спама, формулируя это как многозадачное обучение проблема, когда входные функции представляют собой пары (пользователь, функция), так что один вектор параметров захватывает спам-фильтры для каждого пользователя, а также глобальный фильтр для нескольких сотен тысяч пользователей, и обнаружено, что точность фильтра повысилась.^[2]

Реализации

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

Смотрите также

внешняя ссылка

Хеширование представлений для машинного обучения на сайте Джона Лэнгфорда
Что такое "хеш-трюк"? - MetaOptimize Q + A

[Moody-1] а ^б Муди, Джон (1989). «Быстрое обучение в иерархиях с несколькими разрешениями» (PDF). Достижения в системах обработки нейронной информации.

[Weinberger-2] а ^б ^c ^d ^е ^ж ^грамм Килиан Вайнбергер; Анирбан Дасгупта; Джон Лэнгфорд; Алекс Смола; Джош Аттенберг (2009). Хеширование функций для крупномасштабного многозадачного обучения (PDF). Proc. ICML.

[mobilenlp-3] а ^б К. Ганчев; М. Дредзе (2008). Небольшие статистические модели путем случайного смешивания признаков (PDF). Proc. ACL08 Семинар HLT по обработке мобильных языков.

[4] Джош Аттенберг; Килиан Вайнбергер; Алекс Смола; Анирбан Дасгупта; Мартин Зинкевич (2009). "Совместная фильтрация спама с помощью хеш-метода". Бюллетень вирусов.

[mahout-5] а ^б Оуэн, Шон; Анил, Робин; Даннинг, Тед; Фридман, Эллен (2012). Махауты в действии. Мэннинг. С. 261–265.

[6] Shi, Q .; Петтерсон Дж .; Dror G .; Langford J .; Смола А .; Strehl A .; Вишванатан В. (2009). Хеш-ядра. АИСТАТС.

[7] Bai, B .; Вестон Дж .; Grangier D .; Collobert R .; Sadamasa K .; Qi Y .; Chapelle O .; Вайнбергер К. (2009). Контролируемое семантическое индексирование (PDF). CIKM. С. 187–196.

[8] "gensim: corpora.hashdictionary - Построение сопоставления идентификатора слова <->". Radimrehurek.com. Получено 2014-02-13.

[9] «4.1. Извлечение функций - документация scikit-learn 0.14». Scikit-learn.org. Получено 2014-02-13.

[10] "sofia-ml - Набор быстрых инкрементальных алгоритмов для машинного обучения. Включает методы для обучения моделей классификации и ранжирования с использованием Pegasos SVM, SGD-SVM, ROMMA, пассивно-агрессивного персептрона, персептрона с полями и логистической регрессии". Получено 2014-02-13.

[11] «Хеширование TF». Получено 4 сентября 2015. Сопоставляет последовательность терминов с их частотами, используя трюк хеширования.

[12] «FeatureHashing: создает матрицу модели посредством хеширования функций с помощью интерфейса формул».

[13] "tf.keras.preprocessing.text.hashing_trick - TensorFlow Core v2.0.1". Получено 2020-04-29. Преобразует текст в последовательность индексов в хэш-пространстве фиксированного размера.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]