В машинном обучении , особенность хешировании , также известное как хеширования трюк (по аналогии с трюком ядра ), является быстрым и пространственно-эффективным способом векторизации функций , то есть превращение произвольных функций в индексы в векторе или матрице. [1] [2] Он работает, применяя хеш-функцию к функциям и напрямую используя их хеш-значения в качестве индексов, а не просматривая индексы в ассоциативном массиве . Этот трюк часто приписывают Вайнбергеру и др., Но существует гораздо более раннее описание этого метода, опубликованное Джоном Муди в 1989 г. [2] [1]
Мотивирующий пример
В типичной задаче классификации документов входными данными для алгоритма машинного обучения (как во время обучения, так и во время классификации) является свободный текст. На основе этого создается представление пакета слов (BOW): отдельные токены извлекаются и подсчитываются, и каждый отдельный токен в обучающем наборе определяет функцию (независимую переменную) каждого из документов как в обучающем, так и в тестовом наборе.
Однако алгоритмы машинного обучения обычно определяются в терминах числовых векторов. Таким образом, набор слов для набора документов рассматривается как матрица термин-документ, где каждая строка представляет собой отдельный документ, а каждый столбец представляет собой отдельную характеристику / слово; запись i , j в такой матрице фиксирует частоту (или вес) j -го термина словаря в документе i . (Альтернативное соглашение меняет местами строки и столбцы матрицы, но это различие несущественно.) Как правило, эти векторы чрезвычайно редки - согласно закону Ципфа .
Общий подход заключается в создании во время обучения или до этого словарного представления словарного запаса обучающего набора и его использования для сопоставления слов с индексами. Хеш-таблицы и попытки - общие кандидаты для реализации словаря. Например, три документа
- Джон любит смотреть фильмы.
- Мэри тоже любит фильмы.
- Джон тоже любит футбол.
можно преобразовать, используя словарь
Срок | Индекс |
---|---|
Джон | 1 |
нравится | 2 |
к | 3 |
смотреть | 4 |
кино | 5 |
Мэри | 6 |
тоже | 7 |
также | 8 |
футбол | 9 |
к матрице терминов-документов
(Пунктуация была удалена, как это обычно бывает при классификации и кластеризации документов.)
Проблема с этим процессом заключается в том, что такие словари занимают большой объем дискового пространства и увеличиваются в размере по мере роста обучающего набора. [3] Напротив, если словарный запас остается неизменным и не увеличивается с ростом обучающего набора, злоумышленник может попытаться изобрести новые слова или орфографические ошибки, которых нет в сохраненном словаре, чтобы обойти фильтр, изученный машиной. Эта трудность является причиной того, что хеширование функций было опробовано для фильтрации спама в Yahoo! Исследования . [4]
Обратите внимание, что трюк с хешированием не ограничивается классификацией текста и аналогичными задачами на уровне документа, но может применяться к любой проблеме, которая включает большое (возможно, неограниченное) количество функций.
Векторизация функций с использованием хеширования
Вместо поддержки словаря векторизатор функций, использующий трюк хеширования, может построить вектор заранее определенной длины, применив хеш-функцию h к функциям (например, словам), затем используя хеш-значения непосредственно в качестве индексов функций и обновив результирующий вектор по этим индексам. Здесь мы предполагаем, что этот признак на самом деле означает вектор признаков.
Функция hashing_vectorizer ( функции : массив из строки , N : целое число ) : х : = новый вектор [ N ] для F в особенности : ч : = хеш ( е ) х [ ч мод N ] + = 1 обратных х
Таким образом, если нашим вектором признаков является ["кошка", "собака", "кошка"], а хеш-функция - если это "кот" и если это "собака". Возьмем размер выходного вектора признаков ( N ) равным 4. Затем выведите x будет [0,2,1,0]. Было предложено использовать вторую, однобитовую выходную хеш-функцию ξ для определения знака значения обновления, чтобы противодействовать эффекту хеш-коллизий . [2] Если такая хеш-функция используется, алгоритм становится
Функция hashing_vectorizer ( функции : массив из строки , N : целое число ) : х : = новый вектор [ N ] для F в особенности : ч : = хеш ( ф ) IDX : = ч мод N , если ξ ( е ) == 1 : х [ idx ] + = 1 else : x [ idx ] - = 1 вернуть x
Вышеупомянутый псевдокод фактически преобразует каждую выборку в вектор. Оптимизированная версия вместо этого будет генерировать только поток пар ( h , ξ ) и позволить алгоритмам обучения и прогнозирования потреблять такие потоки; линейная модель может быть реализована в виде одного хэша - таблице , представляющей вектор коэффициентов.
Характеристики
ξ ( е ₁) | ξ ( е ₂) | Конечное значение, ξ ( f ₁) + ξ ( f ₂) |
---|---|---|
-1 | -1 | -2 |
-1 | 1 | 0 |
1 | -1 | 0 |
1 | 1 | 2 |
Когда вторая хеш-функция ξ используется для определения знака значения функции, ожидаемое среднее значение каждого столбца в выходном массиве становится равным нулю, поскольку ξ приводит к отмене некоторых коллизий. [2] Например, предположим, что входные данные содержат две символьные функции f ₁ и f ₂, которые сталкиваются друг с другом, но не с какими-либо другими функциями в том же входном файле; тогда есть четыре возможности, которые, если мы не делаем предположений относительно ξ , имеют равную вероятность, как указано в таблице справа.
В этом примере существует 50% -ная вероятность того, что хэш-коллизия прекратится. Можно использовать несколько хеш-функций, чтобы еще больше снизить риск коллизий. [5]
Кроме того, если φ - это преобразование, реализованное с помощью хеш-трюка со знаком хеширования ξ (т.е. φ ( x ) - это вектор признаков, созданный для выборки x ), то внутренние продукты в хешированном пространстве несмещены:
где математическое ожидание берется по хеш-функции φ . [2] Можно проверить, что- положительное полуопределенное ядро . [2] [6]
Расширения и вариации
Недавняя работа расширяет уловку хеширования до контролируемых отображений слов в индексы [7], которые явно учатся избегать коллизий важных терминов.
Приложения и практическая производительность
Ганчев и Дредзе показали, что в приложениях классификации текста со случайными хэш-функциями и несколькими десятками тысяч столбцов в выходных векторах хеширование признаков не обязательно должно отрицательно влиять на производительность классификации даже без хэш-функции со знаком. [3] Weinberger et al. применили свой вариант хеширования к проблеме фильтрации спама , сформулировав это как многозадачную задачу обучения, где входные функции являются парами (пользователь, функция), так что один вектор параметров захватывает фильтры спама для каждого пользователя, а также глобальный фильтр для нескольких сотен тысяч пользователей и обнаружил, что точность фильтра повысилась. [2]
Реализации
Реализации трюка хеширования представлены в:
- Apache Mahout [5]
- Генсим [8]
- scikit-learn [9]
- софия-мл [10]
- Ваупал Ваббит
- Apache Spark [11]
- R [12]
- TensorFlow [13]
Смотрите также
- Фильтр Блума
- Счетчик мин. Эскиз
- Закон кучи
- Хеширование с учетом местоположения
- MinHash
Рекомендации
- ^ a b Муди, Джон (1989). «Быстрое обучение в иерархиях с несколькими разрешениями» (PDF) . Достижения в системах обработки нейронной информации .
- ^ Б с д е е г Килиан Вайнбергер; Анирбан Дасгупта; Джон Лэнгфорд; Алекс Смола; Джош Аттенберг (2009). Хеширование функций для крупномасштабного многозадачного обучения (PDF) . Proc. ICML.
- ^ а б К. Ганчев; М. Дредзе (2008). Небольшие статистические модели путем случайного смешивания признаков (PDF) . Proc. ACL08 Семинар HLT по обработке мобильных языков.
- ^ Джош Аттенберг; Килиан Вайнбергер; Алекс Смола; Анирбан Дасгупта; Мартин Зинкевич (2009). «Совместная фильтрация спама с помощью хеш-метода» . Вирусный бюллетень .
- ^ а б Оуэн, Шон; Анил, Робин; Даннинг, Тед; Фридман, Эллен (2012). Махауты в действии . Укомплектование персоналом. С. 261–265.
- ^ Shi, Q .; Петтерсон Дж .; Dror G .; Langford J .; Смола А .; Strehl A .; Вишванатан В. (2009). Хеш-ядра . АИСТАТС.
- ^ Bai, B .; Вестон Дж .; Grangier D .; Collobert R .; Садамаса К .; Qi Y .; Chapelle O .; Вайнбергер К. (2009). Контролируемое семантическое индексирование (PDF) . CIKM. С. 187–196.
- ^ "gensim: corpora.hashdictionary - Построение сопоставления идентификатора слова <->" . Radimrehurek.com . Проверено 13 февраля 2014 .
- ^ «4.1. Извлечение функций - документация scikit-learn 0.14» . Scikit-learn.org . Проверено 13 февраля 2014 .
- ^ «sofia-ml - Набор быстрых инкрементальных алгоритмов для машинного обучения. Включает методы для обучения моделей классификации и ранжирования с использованием Pegasos SVM, SGD-SVM, ROMMA, пассивно-агрессивного персептрона, персептрона с полями и логистической регрессии» . Проверено 13 февраля 2014 .
- ^ «Хеширование TF» . Проверено 4 сентября 2015 года .
Сопоставляет последовательность терминов с их частотами терминов, используя трюк хеширования.
- ^ «FeatureHashing: создает матрицу модели с помощью хеширования функций с помощью интерфейса формул» .
- ^ "tf.keras.preprocessing.text.hashing_trick - TensorFlow Core v2.0.1" . Проверено 29 апреля 2020 .
Преобразует текст в последовательность индексов в хэш-пространстве фиксированного размера.
Внешние ссылки
- Хеширование представлений для машинного обучения на веб-сайте Джона Лэнгфорда
- Что такое «хеш-трюк»? - MetaOptimize Q + A