Хеширование функций - Википедия - Feature hashing

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

где ожидание берется из функции хеширования φ.[2] Можно проверить, что это положительный полуопределенный ядро.[2][6]

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

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

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

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

Реализации

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

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

Рекомендации

  1. ^ а б Муди, Джон (1989). «Быстрое обучение в иерархиях с несколькими разрешениями» (PDF). Достижения в системах обработки нейронной информации.
  2. ^ а б c d е ж грамм Килиан Вайнбергер; Анирбан Дасгупта; Джон Лэнгфорд; Алекс Смола; Джош Аттенберг (2009). Хеширование функций для крупномасштабного многозадачного обучения (PDF). Proc. ICML.
  3. ^ а б К. Ганчев; М. Дредзе (2008). Небольшие статистические модели путем случайного смешивания признаков (PDF). Proc. ACL08 Семинар HLT по обработке мобильных языков.
  4. ^ Джош Аттенберг; Килиан Вайнбергер; Алекс Смола; Анирбан Дасгупта; Мартин Зинкевич (2009). "Совместная фильтрация спама с помощью хеш-метода". Бюллетень вирусов.
  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. Преобразует текст в последовательность индексов в хэш-пространстве фиксированного размера.

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