Фонетические ключи, хеширование с учетом местоположения
Это проблема нахождения приблизительных совпадений строки в заданном словаре строк.
Давайте посмотрим пример. Мы хотим найти Jonahtan в словаре чистых имен людей. На самом деле мы имеем в виду, что хотим найти приблизительные совпадения, приняв во внимание орфографические ошибки или другие отклонения. Что мы подразумеваем под «другими вариантами»? В нашем примере мы действительно хотим найти имена в словаре, которые являются правдоподобными альтернативными выражениями имени, неявно присутствующими во входной строке. Сюда входят не только орфографические ошибки, но и никнеймы. Он также может включать почетные обращения, такие как мистер, мисс,…
Поиск может дать Jonathan в словаре как совпадение с Jonahtan. Мы узнаем как о том, что последнее является орфографической ошибкой, так и в процессе находим его правильное написание.
Общий подход
Распространенным способом решения этой проблемы является вызов нечеткого сопоставления в качестве метода черного ящика. Нечеткое сопоставление вводит две строки и вычисляет оценку вероятности того, что они являются выражениями одной и той же сущности. Нечеткие сопоставители подробно описаны в [1].
Простой способ сделать это — взять входную строку, нечетко сопоставить ее с каждой строкой в словаре, ранжировать совпадения с наивысшим результатом в верхней части списка, а затем каким-то образом решить, какое из совпадений занимает первое место ( если есть) достаточно хорошо совпадают с входной строкой.
Этот подход может быть довольно медленным, когда словарь большой. Даже когда это не очень медленно, у нас могут быть строгие требования к времени работы, например, для поиска совпадений в режиме реального времени.
Сокращение области поиска
В этом посте мы сосредоточимся на проблеме сокращения пространства поиска, чтобы свести к минимуму количество нечетких совпадений, которые необходимо выполнить. Сокращение, конечно, зависит от входной строки.
Мы обсудим несколько методов сокращения, в частности те, которые основаны на фонетических ключах, и те, которые основаны на хешировании с учетом местоположения. Мы проиллюстрируем их на одном рабочем примере: поиск нечетких совпадений строки в (большом) словаре имен.
Каковы компромиссы?
Цель состоит в том, чтобы максимально сократить пространство, не теряя ни одного истинного совпадения. Поскольку этот идеал невозможно гарантировать, на практике ищется подходящий компромисс между производительностью (используемой в смысле времени выполнения) и отзывом (процентом истинных совпадений, которые обнаруживаются после сокращения). Хотя точность явно не проявляется в компромиссе, она может проявляться косвенно. Это связано с тем, что более низкая точность потенциально приводит к большему количеству результатов, т. е. к недостаточной обрезке. Ввиду этого замена «производительности» подходящей метрикой, которая количественно определяет сокращение, кажется привлекательной. В конечном счете размер списка результатов влияет на производительность.
Фонетические ключи
Фонетический ключ, полученный из строки, пытается сохранить произношение строки. Рассмотрим Джозефа и Джозефа. Они звучат одинаково. Таким образом, они должны иметь один и тот же фонетический ключ.
Фонетический ключ хорош для сокращения пространства поиска, когда мы ищем строки, которые звучат похоже. Вместо того, чтобы искать строки с похожим звучанием, мы просто ищем все строки, фонетический ключ которых совпадает со строкой запроса.
Двумя популярными методами генерации фонетических ключей являются Soundex и Metaphone. Метафон считается лучшим. Поэтому мы сосредоточимся на нем здесь.
Ниже приведены некоторые пары имен с одинаковым ключом Метафона. Это взято из [1].
Steven, Stephen → STFN, John, Jon → JN, Cathy, Kathy → K0
Это говорит о том, что обрезка по ключу Metaphone будет хорошо работать в нашем случае использования. Чтобы найти похожие по звучанию имена.
Конечно, будут ложные срабатывания. Например, Джек и Джейк имеют один и тот же ключ метафона, JK. Это не обязательно является проблемой во время обрезки, так как фильтрация ложных срабатываний является обязанностью нечеткого сопоставления. Было бы проблемой, если бы процент ложноположительных результатов был настолько высок, что обрезка оказалась бы неэффективной. К счастью, это не относится к клавишам Metaphone.
Отлично, использование подходящего фонетического ключа эффективно для поиска имен в словаре, которые звучат как входная строка. Но обычно это не все, что мы хотим найти. Мы также что бы найти имена с орфографическими ошибками в них, например. Сравните Richard и Rihcard. Ясно, что они должны совпадать, так как несоответствие объясняется одним распространенным типом ошибки: перестановкой соседних букв. Тем не менее, они не звучат имя. Действительно, мы видим, что их ключи Metaphone разные, RXRT и RKRT соответственно. Разница в ключах возникает из-за того, что выделенные жирным шрифтом области в двух именах произносятся по-разному.
Таким образом, даже в нашем примере недостаточно использовать фонетические ключи для обрезки.
Хэш-ключи
От обсуждения до этого момента мы можем абстрагироваться от проблемы обрезки следующим образом. Определите хеш-функцию для данной вселенной (в нашем случае имен людей), которая имеет следующие свойства:
- Он должен достаточно сократить область поиска. Хотя это неформальное описание, его легко эмпирически сопоставить или формализовать.
- Повторяемость должна быть почти 100 %. То есть две строки имени, считающиеся совпадением, почти наверняка должны иметь одинаковое значение хеш-функции.
Фонетические ключи представляют собой особые типы хеш-функций. Более широкое распространение на хеш-функции открывает дверь шире.
Ну, это все очень хорошо, но нам еще нужно выяснить, как частный случай, как обрезать при наличии ошибок транспонирования в строках имен.
Техника, которую мы обсудим далее, предлагает заманчивые возможности в этом отношении.
Хеширование с учетом местоположения
Рассмотрим наше особое требование.
Two first-name strings deemed a match should almost certainly have the same hash value.
Теперь рассмотрим следующее, определяющее утверждение хеширования с учетом местоположения.
Map items to hashes so that similar items have the same hash value with high probability.
Есть ли совпадение? (Каламбур.) Да. Как указано ниже.
Two first-name strings deemed a match ⇐⇒ similar items almost certainly ⇐⇒ high probability
Большой. У нас до сих пор нет конкретного решения нашей проблемы. Потерпите еще немного.
Битовая выборка
Рассмотрим бинарные векторы длины n. Выберите определенный параметр i. Для n-битового вектора x задайте h_i(x) = x_и. Эта хэш-функция просто выбирает i-й бит x.
Это семейство h_1, …, h_n хэш-функций обладает интригующим (и привлекательным) свойством: для любых двух двоичных векторов xи y, если мы выберем случайную хэш-функцию h_i, тем более похожи x и y тем более вероятно, что h_i(x) равно h_i (г).
Хорошо, это непрозрачно. Давайте сломаем это. Во-первых, как мы определяем сходство здесь? Мы определим его как долю n битов, в которых оба вектора имеют одинаковое значение. Таким образом, 1101 и 1100 имеют сходство ¾, поскольку 3 из 4 битов в двух векторах имеют одинаковое значение. (Эти биты выделены жирным шрифтом.)
Далее, давайте построим интуицию на экстремальных примерах. Рассмотрим x=y=1001. Ясно, что h_i(x) равно h_i( y) для каждого i в диапазоне от 1 до 4. Это просто означает, что в крайнем случае, когда оба вектора идентичны, свойство будет сохраняться «чрезвычайно», что означает, что независимо от того, какой выбрана хеш-функция, ее значения в двух векторах обязательно будут одинаковыми.
Точно так же мы можем видеть, что когда x и y максимально разнесены, т.е. 1001 против 0110, каждая из хеш-функций обязательно будет иметь разные значения.
Теперь рассмотрим случай «где-то посередине». В иллюстративных целях переставьте размеры таким образом, чтобы первые d биты x и y были одинаковыми, а остальные отличались. Ниже приведен пример
101111101001 101111110110
Здесь n = 12, d = 7, одинаковые биты выделены жирным шрифтом, а разные — курсивом.
Теперь давайте случайным образом выберем измерение i от 1 до 12. Вероятность того, что x_i и y_ i имеют одинаковое значение d/n, что в точности соответствует значению сходства x и y (как мы его определили).
Использование выборки битов для сокращения области поиска
Вооружившись тем, что мы уже знаем о битовой выборке, давайте воспользуемся ею, чтобы сократить пространство поиска.
Во-первых, мы хотим более точно определить нашу задачу обрезки. Пусть D обозначает набор двоичных векторов длины n, а x один вектор того же типа. Мы хотим эффективно находить векторы в D, наиболее похожие на x, используя функцию подобия, определенную в предыдущем разделе.
Содержимое предыдущего раздела предлагает следующий способ определения хеш-ключа с помощью выборки битов. Здесь y — двоичный вектор длины n.
key(y)
Sample i uniformly at random from {1, 2, …, n}
return (i,y_i)
Обратите внимание, что key(.) — это рандомизированная процедура. При каждом вызове key(.) размерность, чей бит должен быть выбран, выбирается случайным образом.
Используя этот механизм ключей, мы берем каждый вектор d в D и хешируем его до его ключа key(d).
Теперь мы готовы найти соседей в D любого нового входного вектора x.
neighbors(x) key_of_x = key(x) Return all vectors in D whose key is key_of_x
Насколько хорошо это работает? Давайте разработаем пример. Скажем, n = 2, а D содержит 11. Рассмотрим вызов neighbors(11). Найдет ли 11? Не обязательно. Почему нет? Поскольку число 11 в D было проиндексировано под ключом (i, 1). Впоследствии в вызове neighbors(11) он искался по ключу (j, 1). Хотя i и j находятся в {1, 2}, они не обязательно равны из-за рандомизации в функции key(.).
О, это нехорошо. Что мы можем сделать?
Несколько ключей во время поиска
Во время поиска мы могли бы сгенерировать несколько ключей и агрегировать все связанные с ними векторы. Это потенциально увеличивает вероятность того, что желаемый вектор находится в наборе возвращаемых результатов. Мы платим одну цену — тратим больше времени на поиск. Потенциально большая цена, которую мы платим, заключается в том, что количество результатов может значительно увеличиться. В этом случае нам может потребоваться больше времени на их постобработку. Подробнее об этих двух пунктах позже.
Один разумный способ сделать это заключается в следующем. Определите функцию multi_key(y, m), которая вызывает key(y) m раз, собирает векторы, полученные в результате поиска каждого ключа, и возвращает их в виде набора.
Используйте ключ(y), чтобы индексировать вектор. Используйте multi_key(y, m) для поиска его соседей.
Насколько хорошо мы можем ожидать, что это сработает? Каким должен быть m? Давайте посмотрим на этот вопрос с точки зрения отзыва, который мы определим как вероятность того, что индексированный вектор находится в наборе результатов последующего поиска самого себя. Интуитивно понятно, что отзыв должен увеличиваться по мере увеличения m. (Как и время поиска.)
Для любого фиксированного n мы можем легко количественно определить отзыв как функцию от m. Пусть i обозначает измерение, используемое при индексации вектора y. Пусть j обозначает измерение, выбранное во время любого последующего вызова key(y). Вероятность того, что i и j различаются, равна (n-1)/n, поскольку существует n возможные значения j и все, кроме одного, отличаются от i. Вероятность того, что каждый из j в m вызывает key(y), сделанный при попытке lookup y отличается от is таким образом ((n-1)/n)^m. Таким образом, вероятность того, что по крайней мере один из j равен i, т. е. отзыву, равна
1 — ((n-1)/n)^m (R1)
Для n = 20 давайте рассчитаем отзыв для различных m, используя (R1).
m 1 2 10 20 50 100 recall 0.05 0.0975 0.4 0.64 0.92 0.994
Это показывает, что для достижения почти 100% отзыва m должно быть значительно больше, чем n. Это правдоподобно. Случайная выборка с заменой по своей сути немного неэффективна, поскольку один и тот же ключ может быть выбран несколько раз. Что ж, вместо того, чтобы использовать multi_key(y, m), почему бы нам просто не перечислить все 20 ключей один за другим.
Поиск n ключей
Итак, теперь мы узнали, что достаточно найти n ключей, чтобы получить 100% отзыв.
Достаточно ли этого? Не так быстро. Нам также необходимо учитывать размер набора результатов, так как он может быть большим, когда просматривается так много ключей.
Давайте проанализируем следующий сценарий. Скажем, D содержит 1^n, и мы последовательно выполняем его поиск. Рассмотрим вектор y в D, в котором есть d единиц. Теперь рассмотрим результирующий набор соседей (1^n). При перечислении 1^n соседей мы будем искать для каждого i в диапазоне от 1 до n векторы в D проиндексирован под значением 1. Затем объедините их все.
Если y был проиндексирован по i так, что y_i равен 1, он будет находиться в соседях(1 ^н). Вероятность этого составляет d/n. Это связано с тем, что в n имеется d битов со значением 1, а при индексировании случайным образом выбирается один бит из n для индексации.
Скажем, D содержит m_d таких векторов. Мы можем ожидать, что m_d*d/n из них попадут в результирующий набор соседи(1^n).
Теперь предположим, что d мало, скажем, 4, а n намного больше, скажем, 20. Кроме того, предположим, что D содержит много векторов с d единиц в них, то есть m_d большое. Это правдоподобно, поскольку во Вселенной существует «20 таких векторов на выбор 4». Поскольку d мало, разумно ожидать, что большинство, если не все, являются ложными срабатываниями относительно 1^n. Поскольку m_d велико, многие из этих ложных срабатываний попадут в набор результатов.
Наш анализ выше относится к 1^n. Можем ли мы обобщить это? Заменим 1^n на любой n-битовый вектор x. Пусть yв D имеет d общих битов с x, т. е. подобие S(x,y) равно d/n. Вероятность того, что y попадет в результирующий набор соседей(x), по-прежнему равна d. /н. Таким образом, если таких векторов m_d y, как и раньше, можно ожидать m_d*d/n, чтобы попасть в набор результатов. Поскольку d мало, это, вероятно, ложные срабатывания относительно x. Если m_d велико, в результирующем наборе их много.
Подводя итог, можно сказать, что поиск всех измерений n в любом векторе x действительно может дать много результатов, если D содержит множество векторов с небольшим сходством с х. Это проблема, когда большинство этих результатов являются ложноположительными, что вполне вероятно.
Итак, что еще мы можем попробовать?
Образец без замены
Как и прежде, давайте сэмплируем размер m раз. В отличие от предыдущего, давайте попробуем без замены. Это эквивалентно выбору случайного подмножества измерений m из n.
Что это нам дает? Больше гибкости. Установка для m значения n дает нам случай «поиска по всем измерениям». Выбор m меньше, чем n, позволяет нам найти компромисс между отзывом и размером возвращаемого набора результатов.
Вспомнить как функцию от m
Рассмотрим y в D, который мы ищем через некоторое время после того, как он был проиндексирован. Какова вероятность того, что искомый набор результатов содержит y? Это m/n, вероятность того, что измерения m, случайно выбранные во время поиска, включают измерение, для которого y был проиндексирован.
Что это говорит нам? Напомним, уменьшается линейно с m. Конечно, вы хотели бы только снизить m, то есть заплатить цену уменьшенного отзыва, только если вы получили что-то взамен, в частности, количество результатов также значительно уменьшилось. Давайте проанализируем это дальше.
Ожидаемый размер набора результатов
Мы повторим анализ, проведенный в предыдущем разделе, для этого сценария. Для самодостаточности мы пропишем все с нуля. Части, которые отличаются от предыдущего анализа, выделены жирным шрифтом.
Скажем, D содержит 1^n, и мы последовательно выполняем его поиск. Рассмотрим вектор y в D, в котором есть d единиц. Теперь рассмотрим результирующий набор соседей (1^n). При перечислении 1^n соседей мы будем искать,для каждого из m битов, выбранных случайным образом (с заменой) из n бит, векторы в D индексируются под значением 1 для бита выборки. Затем объедините их все.
Если y был проиндексирован битом i таким образом, что y_i равно 1 и i — один из битов m, отобранных во время поиска в соседях (1^n), y будет быть среди соседей(1^n). Вероятность того, что y_i равно 1, равна d/n. Вероятность того, что i является одним из m битов, отобранных во время поиска в соседях (1^n), равна m /н. Таким образом, общая вероятность равна (d/n)*(m/n).
Подводя итог, можно сказать, что путем выборки m битов с заменой во время поиска, связанного с вычислением соседей(1^n), вероятность повторного вызова 1^n равен m/n, а ожидаемый размер результирующего набора равен m_d*(d/n)*(m/n).
Индексирование по нескольким ключам
До сих пор мы использовали только несколько ключей во время поиска. Что, если мы также используем этот механизм во время индексации? Точнее, для целочисленного параметра mI от 1 до n при индексировании x мы выбираем mI бит с заменой с 1 на n и индексом x под каждым.
Используя тот же механизм поиска, что и раньше, вероятность отзыва будет увеличиваться по мере увеличения mI. Как и ожидаемый размер набора результатов.
Уточнение поиска
Чтобы попытаться компенсировать увеличение ожидаемого размера набора результатов по мере увеличения mI, мы могли бы ввести параметр, назовем его kL, чтобы сделать условие поиска более строгий.
К этому моменту вектор включается в набор результатов, если его находит какой-либо из поисковых запросов, специфичных для битов. С параметром kL мы могли бы включить его в набор результатов только в том случае, если его найдет не менее kL поисковых запросов, специфичных для битов.
Итак, это усложняет нашу логику агрегирования, которая теперь должна включать некоторую фильтрацию. Мы не можем просто накапливать все найденные векторы, дедуплицируя их по пути. Мы также должны гарантировать, что найденный вектор находится по крайней мере в kL наборов результатов, зависящих от битов.
Оставляя в стороне сложность логики агрегирования и фильтрации, интуитивно этот механизм, кажется, имеет потенциал для предоставления нам большего контроля над компромиссами.
В этом посте мы остановимся на этом. Количественный анализ этой ситуации, которая теперь параметризована параметрами n, d, m, mI и kL пугает.
От побитовой выборки к полиномиальной выборке
Механизм выборки битов распространяется на юниверс, определенный как D1 X D2 X … X Dn. Здесь каждое «измерение» i имеет конечный набор связанных с ним значений Di. Различные измерения могут иметь разные наборы значений. Статистики и специалисты по данным могут рассматривать это как пространство, определенное набором n категориальных переменных, каждая из которых имеет свой собственный набор значений.
Мы включаем этот абзац в этот пост из-за его эвристической ценности. Он предлагает второй механизм индексации и поиска на основе LSH в полиномиальном пространстве, прямой. Также можно использовать механизм побитовой выборки; сначала требуется преобразовать эту вселенную в бинарную. В то время как существует естественный способ преобразования полиномиального пространства в двоичное с использованием так называемого горячего кодирования, менее ясно, как сравниваются точность и полнота LSH, основанные на двух разных кодировках — одном прямом и одном двоичном. .
Дополнительная литература
