Хеширование признаков hashing trick

Обновлено: 05.07.2024

в этой статье описывается компонент, входящий в Машинное обучение Azure designer.

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

Функции хэширования функций, предоставляемые в этом компоненте, основаны на платформе нимбусмл. Дополнительные сведения см. в описании класса NgramHash.

Общие сведения о хэшировании признаков

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

Например, возьмем ряд простых предложений, таких как эти, и укажем для них оценку тональности. Предположим, что вы хотите использовать этот текст для построения модели.

Пользовательский текст	Мнение
Мне понравилась эта книга	3
Эта книга отвратительная	1
Эта книга была отличной	3
Я люблю книги	2

На внутреннем уровне компонент хэширования компонентов создает словарь n-грамм. Например, список биграмм для этого набора данных будет выглядеть примерно так:

Термин (биграммы)	Частота
Эта книга	3
Мне понравилась	1
Книга отвратительна	1
Я люблю	1

Размер N-грамм контролируется с помощью свойства N-граммы. При выборе биграмм также вычисляются униграммы. Словарь также будет включать в себя следующие термины:

Термин (униграммы)	Частота
книга	3
I	3
книги	1
была	1

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

Например, после хэширования столбцы признаков могут выглядеть примерно так:

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

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

Настройка компонента хэширования компонентов

Добавьте компонент хэширования компонентов в конвейер в конструкторе.

Подключите набор данных, содержащий текст, который необходимо проанализировать.

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

В качестве целевых столбцов задайте текстовые столбцы, которые необходимо преобразовать в хэшированные признаки. Помните о следующем:

Столбцы должны принадлежать к строковому типу данных.

Выбор нескольких текстовых столбцов может значительно повлиять на размерность признаков. Например, число столбцов для 10-разрядного хэша варьируется от 1024 для одного столбца до 2048 для двух столбцов.

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

Битовый размер по умолчанию равен 10. Для многих проблем этого значения достаточно. Чтобы избежать конфликтов, может потребоваться больше пространства. Это зависит от размера словаря N-грамм в обучающем тексте.

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

Например, если ввести 3, будут созданы униграммы, биграммы и триграммы.

Результаты

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

Имя столбца 1	Тип столбца 2
USERTEXT	Столбец исходных данных
SENTIMENT	Столбец исходных данных
USERTEXT — хэш-признак 1	Столбец хэшированного признака
USERTEXT — хэш-признак 2	Столбец хэшированного признака
USERTEXT — хэш-признак N	Столбец хэшированного признака
USERTEXT — хэш-признак 1024	Столбец хэшированного признака

После создания преобразованного набора данных его можно использовать в качестве входных данных для компонента «обучение модели».

Обзор учебника

Этот урок разделен на 4 части; они есть:

Разделите слова с помощью text_to_word_sequence.
Кодирование с помощью one_hot.
Хэш-кодирование с помощью hashing_trick.
API Tokenizer

Разделить слова с помощью text_to_word_sequence

Хороший первый шаг при работе с текстом - разбить его на слова.

Слова называются токенами, а процесс разбиения текста на токены называется токенизацией.

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

По умолчанию эта функция автоматически делает 3 вещи:

Вы можете изменить любое из этих значений по умолчанию, передав аргументы функции.

Ниже приведен пример использования функции text_to_word_sequence () для разделения документа (в данном случае простой строки) на список слов.

При выполнении примера создается массив, содержащий все слова в документе. Список слов печатается для ознакомления.

Это хороший первый шаг, но перед началом работы с текстом необходима дополнительная предварительная обработка.

Кодирование с one_hot

Распространено представлять документ как последовательность целочисленных значений, где каждое слово в документе представлено как уникальное целое число.

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

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

Как и в случае с функцией text_to_word_sequence () в предыдущем разделе, функция one_hot () делает текст строчными, отфильтровывает знаки препинания и разделяет слова на основе пробелов.

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

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

Мы можем поместить это вместе с функцией one_hot () и одним горячим кодированием слов в документе. Полный пример приведен ниже.

Размер словарного запаса увеличен на треть, чтобы минимизировать коллизии при хешировании слов.

При выполнении примера сначала печатается размер словаря как 8. Кодированный документ затем печатается как массив целочисленных слов.

Хеширование с помощью hashing_trick

Ограничение целочисленных и базовых кодировок состоит в том, что они должны поддерживать словарный запас слов и их отображение на целые числа.

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

Керас обеспечиваетфункция hashing_trick ()который маркирует, а затем целочисленно кодирует документ, как функция one_hot (). Это обеспечивает большую гибкость, позволяя вам указывать хеш-функцию как «hash» (по умолчанию) или другие хеш-функции, такие как встроенная функция md5 или ваша собственная функция.

Ниже приведен пример целочисленного кодирования документа с использованием хэш-функции md5.

При выполнении примера печатается размер словаря и целочисленного документа.

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

API Tokenizer

До сих пор мы рассматривали одноразовые удобные методы для подготовки текста с помощью Keras.

Keras предоставляет более сложный API для подготовки текста, который можно подогнать и использовать повторно для подготовки нескольких текстовых документов. Это может быть предпочтительным подходом для крупных проектов.

Керас обеспечиваетКласс токенизаторадля подготовки текстовых документов для глубокого изучения. Tokenizer должен быть сконструирован и затем помещен либо в необработанные текстовые документы, либо в целочисленные текстовые документы.

После подбора токенизатор предоставляет 4 атрибута, которые вы можете использовать для запроса того, что вы узнали о ваших документах:

word_counts: Словарь слов и их количество.
word_docs: Словарь слов и сколько документов каждый появился в.
word_index: Словарь слов и их уникально назначенных целых чисел.
DOCUMENT_COUNT: Целое число от общего числа документов, которые были использованы для размещения токенизатора.

После того, как Tokenizer будет помещен в тренировочные данные, его можно использовать для кодирования документов в поездах или тестовых наборах данных.

Функция text_to_matrix () в Tokenizer может использоваться для создания одного вектора на каждый документ, предоставленный для каждого ввода. Длина векторов - это общий объем словарного запаса.

Эта функция предоставляет набор стандартных схем кодирования текста модели пакета слов, которые могут быть предоставлены через аргумент mode функции.

Доступные режимы включают в себя:

«двоичный‘: Присутствует или нет каждое слово в документе. Это по умолчанию.
«подсчитывать‘: Количество каждого слова в документе.
«tfidf‘: Текстовая обратная оценка частоты документа (TF-IDF) для каждого слова в документе.
«частота‘: Частота каждого слова в виде соотношения слов в каждом документе.

Мы можем соединить все это с проработанным примером.

Выполнение примера подходит для Tokenizer с 5 небольшими документами. Детали подходящего Tokenizer напечатаны. Затем 5 документов кодируются с использованием подсчета слов.

Каждый документ кодируется как 9-элементный вектор с одной позицией для каждого слова и выбранным значением схемы кодирования для каждой позиции слова. В этом случае используется простой режим подсчета слов.

Дальнейшее чтение

Этот раздел предоставляет больше ресурсов по этой теме, если вы хотите углубиться.

Резюме

В этом руководстве вы узнали, как использовать API Keras для подготовки текстовых данных к углубленному изучению.

В частности, вы узнали:

Об удобных методах, которые можно использовать для быстрой подготовки текстовых данных.
API Tokenizer, который можно использовать для данных обучения и использовать для кодирования документов обучения, проверки и тестирования.
Диапазон из 4 различных схем кодирования документов, предлагаемых Tokenizer API.

У вас есть вопросы?
Задайте свои вопросы в комментариях ниже, и я сделаю все возможное, чтобы ответить.

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

Содержание

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

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

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

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

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

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

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

в матрицу терминологического документа

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

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

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

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

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

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

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

Свойства

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

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

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

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

где математическое ожидание берется по хеш-функции φ . Можно проверить, что это положительное полуопределенное ядро . ⟨ φ ( Икс ) , φ ( Икс ′ ) ⟩

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

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

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

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

Хеш — это какая-то функция, сопоставляющая объектам какого-то множества числовые значения из ограниченного промежутка.

Быстро считается — за линейное от размера объекта время;
Имеет не очень большие значения — влезающие в 64 бита;
«Детерминировано-случайная» — если хеш может принимать $n$ различных значений, то вероятность того, что хеши от двух случайных объектов совпадут, равна примерно $\frac$.

Обычно хеш-функция не является взаимно однозначной: одному хешу может соответствовать много объектов. Такие функции называют сюръективными.

Для некоторых задач удобнее работать с хешами, чем с самими объектами. Пусть даны $n$ строк длины $m$, и нас просят $q$ раз проверять произвольные две на равенство. Вместо наивной проверки за $O(q \cdot n \cdot m)$, мы можем посчитать хеши всех строк, сохранить, и во время ответа на запрос сравнивать два числа, а не две строки.

Применения в реальной жизни

Чек-суммы. Простой и быстрый способ проверить целостность большого передаваемого файла — посчитать хеш-функцию на стороне отправителя и на стороне получателя и сравнить.
Хеш-таблица. Класс unordered_set из STL можно реализовать так: заведём $n$ изначально пустых односвязных списков. Возьмем какую-нибудь хеш-функцию $f$ с областью значений $[0, n)$. При обработке .insert(x) мы будем добавлять элемент $x$ в $f(x)$-тый список. При ответе на .find(x) мы будем проверять, лежит ли $x$-тый элемент в $f(x)$-том списке. Благодаря «равномерности» хеш-функции, после $k$ добавлений ожидаемое количество сравнений будет равно $\frac$ = $O(1)$ при правильном выборе $n$.
Мемоизация. В динамическом программировании нам иногда надо работать с состояниями, которые непонятно как кодировать, чтобы «разгладить» в массив. Пример: шахматные позиции. В таком случае нужно писать динамику рекурсивно и хранить подсчитанные значения в хеш-таблице, а для идентификации состояния использовать его хеш.
Проверка на изоморфизм. Если нам нужно проверить, что какие-нибудь сложные структуры (например, деревья) совпадают, то мы можем придумать для них хеш-функцию и сравнивать их хеши аналогично примеру со строками.
Криптография. Правильнее и безопаснее хранить хеши паролей в базе данных вместо самих паролей — хеш-функцию нельзя однозначно восстановить.
Поиск в многомерных пространствах. Детерминированный поиск ближайшей точки среди $m$ точек в $n$-мерном пространстве быстро не решается. Однако можно придумать хеш-функцию, присваивающую лежащим рядом элементам одинаковые хеши, и делать поиск только среди элементов с тем же хешом, что у запроса.

Хешируемые объекты могут быть самыми разными: строки, изображения, графы, шахматные позиции, просто битовые файлы.

Читайте также: