Вероятностные алгоритмы: Вероятно, это работает (ЧАСТЬ 2)

1 Star2 Stars (1 votes, average: 5,00 out of 5)
Загрузка...

Мы продолжаем знакомство с вероятностными моделями. Первая часть статьи была посвящена алгоритму HyperLogLog (являющемуся наследником LogLog). Сегодня речь пойдет о других вероятностных алгоритмах, в частности, Bimodal Multicast.

Задача поиска ближайшего соседа

Задача поиска ближайшего соседа (nearest neighbor search) заключается в поиске похожих элементов в некотором наборе элементов. Сюда можно отнести, например, поиск похожих книг, аудиозаписей, товаров, фотографий, видео. Для решения этой задачи необходимо ответить на два вопроса: что означает понятие «похожие элементы», и как их найти?

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

One is still what one is going to cease to be and already what one is going to become. One lives one’s death, one dies one’s life.

JeanPaul Sartre

Если подсчитать, сколько раз каждое слово встречается в этой «книге», мы получим в результате мешок слов (bag of words):

{ already: 1, and: 1, be: 1, become: 1, cease: 1, death: 1, die: 1, going: 2, is: 3, life: 1, lives: 1, one: 7, still: 1, to: 3, what: 2 }

Это лишь один из вариантов извлечения признаков. Вместо этого можно извлечь пары слов:

{ already_what: 1, and_already: 1, be_and: 1, become_one: 1, cease_to: 1, death_one: 1, ... }

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

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

Существует множество технологий для оценки сходства, но все они сталкиваются с одинаковыми проблемами, причиной которых является проклятие размерности (curse of dimensionality). Проклятие размерности – это ряд явлений, имеющих место при работе с данными очень большой размерности. Эти явления возникают в результате того, что с ростом размерности объем пространства возрастает экспоненциально. Соответственно возрастает и количество ресурсов, необходимое для вычисления евклидова расстояния или косинусного коэффициента. Подобные операции над векторами большой размерности требуют очень много времени.

Представляем вам еще один вероятностный алгоритм: LSH (locality-sensitive hashing, локально-чувствительное хеширование). Идея LSH противоположна идее традиционного хеширования. При традиционном хешировании два входных значения, являющиеся похожими, но не одинаковыми, должны давать на выходе существенно различные результаты. В рамках концепции LSH похожие входные значения должны давать похожие выходные значения, имеющие значительно меньшую размерность. На практике с помощью LSH я преобразовывал 1000000-мерные векторы в 512-битные хеши, и это давало хорошие результаты.

Очевидно, что если вектор большой размерности преобразуется в маленький хеш, часть данных теряется. Здесь на помощь приходит вероятность.

Существует ряд различных способов, позволяющих сгенерировать LSH-хеш. Рассмотренный ниже вариант является одним из простейших.

Допустим, мы имеем корпус книжных текстов. Мы уже извлекли словарь, содержащий 100000 слов. Следовательно, вектор признаков для каждой книги будет иметь размерность 100000. Предположим, что мы решили создать 256-битную LSH-функцию. Для этого сгенерируем 256 абсолютно случайных 100000-мерных векторов. Эти случайные векторы являются основой нашей LSH-функции.

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

Выполняя описанные действия, мы аппроксимируем угол входного вектора в векторном пространстве. Следовательно, мы можем оценить косинусный коэффициент двух любых хешей, сгенерированных данной LSH-функцией. Косинусный коэффициент двух книг будет пропорционален расстоянию Хэмминга (Hamming distance) между их LSH-хешами.

Надежная передача сообщений

Надежная передача сообщений большому количеству узлов в сети, которой свойственны задержки и потери (т.е. в Интернете), – сложная задача. По сути именно эту задачу и должны были решить сотрудники компании Fastly, чтобы создать систему мгновенной очистки кеша (instant purging system). В качестве логичного решения можно предложить систему с единым центральным сервером, который рассылает сообщения всем серверам. Однако такая схема имеет серьезные недостатки. Если центральный сервер выходит из строя, под вопросом оказывается надежность всей системы.

Существуют ли альтернативные решения? На первый взгляд, кажется, что задачу можно решить с помощью атомарной передачи (atomic broadcast). Однако одним из принципов атомарной передачи является свойство полного порядка (total order). Суть это свойства заключается в том, что если мы отправляем два сообщения (A и B), то каждый сервер получает их в том же порядке, в котором они были отправлены. Хотя это свойство полезно для некоторых приложений, его результатом является проблема блокирования очереди первым элементом (head-of-line blocking). То есть, если сообщение A должно быть получено перед сообщением B, но один из серверов по какой-то причине не может принять сообщение A, тогда ни один из серверов не сможет получить сообщение B, пока оставшийся сервер не получит сообщение A. В случае конкретного приложения для Fastly порядок не имеет значения, а потенциальные дополнительные задержки, связанные с блокированием очереди, неприемлемы.

Мы продолжали поиск альтернативы и в итоге остановились на многофазном протоколе Bimodal Multicast, который позволяет с высокой надежностью вероятностно передавать сообщения между серверами. Первая фаза заключается в ненадежной передаче сообщения от одного узла ко всем другим. Механизм этой передачи не имеет существенного значения: можно использовать, например, IP-мультикаст, если он доступен. Важно лишь, чтобы сообщения были отправлены всем серверам как можно быстрее, даже если существует вероятность их потери в пути.

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

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

Версия данной системы, являющаяся ядром нашей системы очистки кеша, настроена таким образом, что вероятность полной потери сообщения астрономически мала – около 10-312%. В текущем состоянии наша система может потерять по причине вероятностного характера алгоритма лишь одно сообщение за 3×10300 лет. Другими словами, это более чем достаточная надежность.

Многие задачи, которые трудно решить точно, достаточно просто решаются с помощью вероятностных алгоритмов. Согласованное хеширование (consistent hashing) часто применяется для балансировки нагрузки и в распределенных базах данных. Алгоритм Mincut может быть использован для решения задач в области сетевой маршрутизации. Фильтры Блума (Bloom filter) присутствуют во многих СУБД и сетевых приложениях. Алгоритм быстрой сортировки (quicksort) на сегодняшний день является стандартом. Даже обычные хеш-таблицы, на самом деле, являются вероятностными. В своей повседневной работе программист постоянно имеет дело с вероятностными алгоритмами и структурами данных. Обычно они незаметны, потому что просто работают.

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

Автор публикации

не в сети 13 часов

Лариса Шурига

Комментарии: 16Публикации: 883Регистрация: 05-06-2014

Вам также может понравиться

2 комментария

  1. Игорь:

    Спасибо за Ваш труд! с удовольствием читаю, очень интересно!

     

Добавить комментарий

Ваш e-mail не будет опубликован.

закрыть

Поделиться

Отправить на почту
закрыть

Вход

закрыть

Регистрация

+ =
Авторизация
*
*

Login form protected by Login LockDown.


Регистрация
*
*
*
*
Генерация пароля