Хеширование функций - Википедия - 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 |
-1 | 1 | 0 |
1 | -1 | 0 |
1 | 1 | 2 |
Когда вторая хеш-функция ξ используется для определения знака значения функции, ожидал иметь в виду каждого столбца в выходном массиве становится равным нулю, потому что ξ приводит к отмене некоторых коллизий.[2] Например, предположим, что вход содержит две символьные функции ж₁ и ж₂ которые сталкиваются друг с другом, но не с другими объектами в одном и том же входе; то есть четыре возможности, которые, если мы не будем делать никаких предположений относительно ξ, имеют равную вероятность, как указано в таблице справа.
В этом примере существует 50% -ная вероятность того, что конфликт хеша будет отменен. Можно использовать несколько хэш-функций для дальнейшего снижения риска коллизий.[5]
Кроме того, если φ это преобразование, реализованное с помощью хеш-трюка со знаковым хешем ξ (т.е. φ(Икс) - вектор признаков, созданный для образца Икс), тогда внутренние продукты в хешированном пространстве беспристрастны:
где ожидание берется из функции хеширования φ.[2] Можно проверить, что это положительный полуопределенный ядро.[2][6]
Расширения и вариации
Недавняя работа расширяет уловку хеширования на контролируемые сопоставления слов в индексы,[7]которые явным образом учатся избегать столкновений важных терминов.
Приложения и практическая производительность
Ганчев и Дредзе показали, что в приложениях классификации текста со случайными хэш-функциями и несколькими десятками тысяч столбцов в выходных векторах хеширование функций не обязательно должно отрицательно влиять на производительность классификации даже без хеш-функции со знаком.[3]Weinberger et al. применили свой вариант хеширования к проблеме фильтрация спама, формулируя это как многозадачное обучение проблема, когда входные функции представляют собой пары (пользователь, функция), так что один вектор параметров захватывает спам-фильтры для каждого пользователя, а также глобальный фильтр для нескольких сотен тысяч пользователей, и обнаружено, что точность фильтра повысилась.[2]
Реализации
Реализации трюка хеширования представлены в:
- Apache Mahout[5]
- Gensim[8]
- scikit-learn[9]
- София-мл[10]
- Ваупал Ваббит
- Apache Spark[11]
- р[12]
- TensorFlow[13]
Смотрите также
Рекомендации
- ^ а б Муди, Джон (1989). «Быстрое обучение в иерархиях с несколькими разрешениями» (PDF). Достижения в системах обработки нейронной информации.
- ^ а б c d е ж грамм Килиан Вайнбергер; Анирбан Дасгупта; Джон Лэнгфорд; Алекс Смола; Джош Аттенберг (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 .; Sadamasa K .; Qi Y .; Chapelle O .; Вайнбергер К. (2009). Контролируемое семантическое индексирование (PDF). CIKM. С. 187–196.
- ^ "gensim: corpora.hashdictionary - Построение сопоставления идентификатора слова <->". Radimrehurek.com. Получено 2014-02-13.
- ^ «4.1. Извлечение функций - документация scikit-learn 0.14». Scikit-learn.org. Получено 2014-02-13.
- ^ "sofia-ml - Набор быстрых инкрементальных алгоритмов для машинного обучения. Включает методы для обучения моделей классификации и ранжирования с использованием Pegasos SVM, SGD-SVM, ROMMA, пассивно-агрессивного персептрона, персептрона с полями и логистической регрессии". Получено 2014-02-13.
- ^ «Хеширование TF». Получено 4 сентября 2015.
Сопоставляет последовательность терминов с их частотами, используя трюк хеширования.
- ^ «FeatureHashing: создает матрицу модели посредством хеширования функций с помощью интерфейса формул».
- ^ "tf.keras.preprocessing.text.hashing_trick - TensorFlow Core v2.0.1". Получено 2020-04-29.
Преобразует текст в последовательность индексов в хэш-пространстве фиксированного размера.
внешняя ссылка
- Хеширование представлений для машинного обучения на сайте Джона Лэнгфорда
- Что такое "хеш-трюк"? - MetaOptimize Q + A