Хабрахабр

[Перевод] Обнаружен универсальный метод сортировки сложной информации

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

Дан набор сведений и новая точка, и требуется найти, к какой точке из уже существующих она окажется ближайшей? Это пример задачи поиска "ближайшего соседа", которую широко изучают в информатике. Такой вопрос возникает во множестве повседневных ситуаций в таких областях, как исследование генома, поиск картинок и рекомендации на Spotify.

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

«Это первый результат, охватывающий большой набор пространств при помощи единой алгоритмической техники», — сказал Пётр Индик, специалист по информатике из Массачусетского технологического института, влиятельная фигура в области разработок, связанных с этой задачей.

Разница расстояний

Мы так крепко привязаны к единственному способу определения расстояния, что легко упустить из виду возможность существования других способов. Обычно мы измеряем расстояние, как евклидово – как прямую линию между двумя точками. Однако есть ситуации, в которых больше смысла имеют другие определения. К примеру, манхэттенское расстояние заставляет вас делать повороты на 90 градусов, будто перемещаясь по прямоугольной сети дорог. Чтобы измерить такое расстояние, которое по прямой могло бы равняться 5 километрам, вам может потребоваться пересечь город в одном направлении на 3 км, а потом в другом – на 4.

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

Возьмём, к примеру, два генома. Существуют десятки метрик расстояний, каждая из которых подходит к какой-то определенной задаче. Дистанция редактирования между двумя последовательностями генома – это количество добавлений, удалений, вставок и замен, необходимых для превращения одной из них в другую. Биологи сравнивают их, используя "расстояние Левенштейна", или дистанцию редактирования.

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


Александр Андони

Квадратура круга

Стандартный подход к поиску ближайшего соседа – разделить существующие данные на подгруппы. Если, допустим, ваши данные описывают расположение коров на пастбище, то вы можете заключить каждую из них в круг. Потом поместим на луг новую корову и зададим вопрос: в какой из кругов она попадает? Практически гарантировано, что ближайший сосед новой коровы окажется в том же самом круге.

Разделим круги на подкруги, разделим эти ячейки дальше, и так далее. Затем повторим процесс. Эта существующая точка и будет вашим ближайшим соседом. В итоге найдётся ячейка всего с двумя точками: существующей и новой.

Внизу – использование расширяющего графа
Вверху – разделение данных на ячейки.

«Мы хотим, чтобы в этих ячейках ближние точки чаще оказывались в одном диске друг с другом, а далёкие – редко», — сказал Илья Разенштейн, специалист по информатике из Microsoft Research, соавтор новой работы, в которой также участвовали Александр Андони из Колумбийского Университета, Ассаф Наор из Принстона, Александр Николов из Университета Торонто и Эрик Вайнгартен из Колумбийского университета. Алгоритмы рисуют ячейки, хорошие алгоритмы рисуют их быстро и хорошо – то есть так, чтобы не оказалось ситуации, в которой новая корова попадает в круг, а её ближайший сосед оказывается в другом круге.

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

Вместо этого программисты рисуют ячейки при помощи "локально чувствительного хеширования", впервые описанного Индиком и Радживом Мотвани в 1998. Для многомерных данных, у которых одна точка может определяться сотнями или тысячами значений, диаграммы Вороного требуют слишком больших вычислительных мощностей. Поэтому они работают быстрее, но менее точно – вместо того, чтобы находить точного ближайшего соседа, они гарантируют нахождение точки, находящейся не дальше заданного расстояния от реального ближайшего соседа. ЛЧХ-алгоритмы рисуют ячейки случайным образом. Это можно представить себе, как рекомендацию фильма от Netflix, которая не идеальна, но достаточно хороша.

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

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

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


Илья Разенштейн

Неожиданный результат

В новой работе учёные отказались от поиска специальных алгоритмов. Вместо этого они задали более широкий вопрос: что мешает разработать алгоритм на определённой метрике расстояний?

Экспандер — это особый вид графа, набора точек, соединённых рёбрами. Они решили, что виной тому неприятная ситуация, связанная с расширяющим графом, или экспандером. Расстояние между двумя точками графа – это минимальное количество линий, необходимых для того, чтобы пройти из одной точки в другую. У графов есть своя метрика расстояния. Если, к примеру, у Джулиан Мур есть френд, у которого есть френд, у которого во френдах состоит Кевин Бэйкон, тогда расстояние от Мур до Бэйкона равняется трём. Можно представить себе граф, представляющий собой связи между людьми в соцсети, и тогда расстояние между людьми будет равно количеству разделяющих их связей.

Он обладает высокой связностью, то есть две точки нельзя разъединить, не разрезав несколько рёбер. Экспандер – особый тип графов, у которого есть два, на первый взгляд, противоречащих друг другу свойства. Из-за этого большая часть точек находится далеко друг от друга. В то же время большая часть точек соединена с очень малым количеством других.

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

«Любой способ разрезания экспандера на две части требует разрезания множества рёбер, что разделяет много близко расположенных вершин», — сказал Вайнгартен, соавтор работы.

Но они хотели доказать, что такие алгоритмы невозможно построить для множества других метрик расстояний – метрик, при поиске хороших алгоритмов для которых специалисты по информатике зашли в тупик. К лету 2016 года Андони, Ниоколов, Разенштейн и Ванйгартен знали, что для экспандеров нельзя придумать хорошего алгоритма поиска ближайшего соседа.

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


Эрик Вайнгартен

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

«Мы попросили Ассафа помочь нам с этим утверждением, а он доказал обратное», — сказал Андони.

Опираясь на доказательства Наора, учёные последовали по следующей логической цепочке: если экспандеры не встраиваются в метрику расстояний, тогда должен быть хороший способ разбивать их на ячейки (поскольку, как они доказали, единственной преградой для этого служат свойства экспандеров). Наор доказал, что экспандеры не встраиваются в большой класс метрик расстояний, известных, как "нормированные пространства" (куда входят и такие метрики, как евклидово и манхэттенское пространство). Поэтому должен существовать хороший алгоритм поиска ближайшего соседа – даже если его ещё пока никто не нашёл.

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

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

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

«Это упорядоченный метод разработки алгоритмов поиска ближайшего соседа в любой из нужных вам метрик расстояний», — сказал Вайнгартен.

Теги
Показать больше

Похожие статьи

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

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Кнопка «Наверх»
Закрыть