Вчера мы объявили о масштабном обновлении Яндекс.Карт — на них появились подробные схемы большинства стран мира. За этим проектом стоит не просто нанесение на карту новых объектов, но прежде всего технологическая основа, которая позволяет хранить, быстро обрабатывать и обновлять эти данные. В Яндекс.Картах вообще немало интересных технологий, и сегодня мы хотим рассказать об одной из них — технологии построения маршрутов.
Десять-пятнадцать лет назад в бардачке каждого водителя лежал атлас дорог. Он и был главным помощником при планировании маршрута. Сейчас вместо атласа люди всё чаще открывают электронные карты и мобильные приложения. И умные алгоритмы сами строят для человека наилучший маршрут. Яндекс помогает людям планировать поездки на сервисе maps.yandex.ru, в мобильных приложениях Навигатор и Яндекс.Карты. Технология построения маршрута везде одна и та же, различаются только интерфейсы.
Главные составляющие маршрутизации — это дорожный граф и алгоритм, который рассчитывает маршрут.
Что такое граф
Дорожный граф — это сетка дорог. Она состоит из множества фрагментов, которые состыкованы между собой. Например, дорожный граф города Саратова (население — около 840 тысяч человек) состоит из 7592 фрагментов. Каждый из них несёт информацию о своём участке дороги: географические координаты, направление движения, средняя скорость, с которой машины обычно едут на этом участке, и другие параметры. Каждый фрагмент содержит также данные о том, как он стыкуется с соседними участками — есть ли в этом месте поворот направо или налево, можно ли там развернуться в обратную сторону или разрешается ехать только прямо.
Само собой, дорожный граф нельзя сделать раз и навсегда. Транспортная система города имеет обыкновение меняться. Появляются новые дороги и развязки, меняется направление движения. А там, где ещё недавно был поворот, может висеть «кирпич». Чтобы не отставать от жизни, Яндекс регулярно обновляет данные.
Во-первых, постоянно обрабатываются сообщения о неточностях в графе, которые пользователи присылают с помощью мобильных Яндекс.Карт, Навигатора и веб-сервиса Яндекс.Карты. С этими сообщениями работают эксперты Яндекса, которые используют также открытые источники информации о транспортной системе (например, сайты местных администраций).
Во-вторых, для определения неточностей на карте дорог существует специальная система. Она фиксирует все случаи, когда данные о движении машин, которые анонимно передают водители, не совпадают с имеющейся сеткой дорог. Если это не случайный нарушитель, который выехал на газон или развернулся в неположенном месте, возможно, на этом участке изменилась схема движения. Все такие случаи разбираются, и потом изменения вносятся в граф.
Дорожный граф хранится на серверах Яндекса в нескольких экземплярах — если какой-то из серверов будет временно недоступен, маршрутизация все равно будет работать.
алгоритму Дейкстры. С его помощью система вычисляет самый быстрый вариант проезда — исходя из длины каждого отрезка графа и скорости движения на этом участке. Если пользователь строит маршрут проезда без учёта пробок, то алгоритм использует среднюю скорость движения на участке. А если пользователь хочет знать, как быстрее всего добраться до места с учётом ситуации на дороге, то алгоритм задействует данные о текущей ситуации на дороге.
Как это происходит, можно разобрать на примере. Представим, что нужно проложить маршрут из точки А в точку B. Алгоритм начинает методично перебирать все возможные варианты. Первым делом он прокладывает маршрут на один шаг (фрагмент графа) во все стороны от точки А. И затем вычисляет, сколько времени потребуется на преодоление этих участков (тут все просто — расстояние делится на скорость). Дальше он выбирает точку, до которой удалось бы добраться быстрее всего. Это точка С.
Затем алгоритм строит маршрут ещё на один шаг — во все стороны от точки С. И снова анализирует, в какую из точек можно было бы попасть быстрее всего. На этот раз это точка D. На следующем шаге алгоритм будет строить маршрут уже от неё.
Продолжая в том же духе, маршрутизатор находит вариант проезда, который оказывается самым коротким по времени.
Особая тема — дворы. Как известно, сквозной проезд через дворы запрещён. Кроме того, на петляния по дворам зачастую уходит больше времени, чем на проезд по прямой. Чтобы сервис не строил маршруты через дворы, за них начисляются дополнительные минуты (они не влияют на время в пути, которое видит пользователь). Поэтому в большинстве случаев алгоритм выбирает другие варианты проезда — они занимают меньше времени. Однако если конечная точка маршрута находится во дворе, алгоритму в любом случае придётся туда «въехать».
Построение маршрута происходит очень быстро. Пока вы читаете эти несколько абзацев, сервис уже несколько раз успел бы оплести паутиной маршрутов всю Россию. Чтобы добиться такой скорости, всю карту автоматически поделили на множество областей, для каждой из которых можно посчитать оптимальные варианты её пересечения. Такой областью может быть, например, небольшой городок, через который проходит всего одна междугородняя трасса — въехать и выехать из города можно только по ней. Это значит, что Яндекс может заранее рассчитать оптимальный вариант проезда через этот город.
Если на пути пользователя лежат несколько таких областей, Яндекс просто складывает маршрут из уже готовых кусочков.
Всевозможные варианты проезда внутри каждой области и между ними Яндекс строит заранее — при каждом обновлении графа. Дальше, когда пользователь просит построить маршрут, сервис просто вытаскивает его из памяти. Правда, это срабатывает, только если человеку нужен маршрут без учёта пробок — заранее построенные маршруты рассчитаны на основе средней скорости движения, которая заложена в графе. Если же пользователь хочет построить маршрут с учетом ситуации на дороге и внутри области в данный момент есть пробки, Яндекс построит для него маршрут заново.
На Яндекс.Картах появилась подробная карта мира. За этим коротким предложением стоит полтора года упорной работы всей команды сервиса, обработка невероятного объёма данных, перевод миллионов географических названий. За всё время существования Яндекс.Карт нам не приходилось делать ничего подобного. Эта работа была для нас чем-то вроде полной пересборки летящего самолёта.
В процессе работы над мировой картой мы полностью переписали ядро Яндекс.Карт. Благодаря этому у нас появилась возможность внедрить единый дизайн, а также инфраструктура для быстрой публикации обновлений. Теперь вносить изменения и исправлять неточности на Яндекс.Картах стало гораздо проще. Наши собственные карты России, Белоруссии, Украины и Казахстана будут обновляться ежемесячно, а карты других стран мира, основанные на данных компании Navteq, — каждые три месяца.
На мировой карте можно увидеть подробные схемы большинства стран. Наиболее проработаны карты России, Украины, Белоруссии и Казахстана, а также Европы и Северной Америки — на них есть подробная дорожная сеть, все основные улицы и дома. Кроме того, Яндекс.Карты позволяют строить автомобильные маршруты внутри стран и между ними. Так что вы легко сможете узнать, как на машине добраться, например, из Лондона в Брюссель.
Названия зарубежных городов и популярных туристических мест на Яндекс.Картах подписаны на понятном пользователю языке. Для посетителей из русскоязычных стран — на русском, для пользователей из других стран — латиницей. Чтобы продублировать топонимы на русском, нужно было перевести с 37 языков названия 7 127 063 объектов, расположенных в 237 странах. Для этого нам потребовалось перенести правила транскрибирования для 37 языков (плюс различные варианты и диалекты) в понятный компьютеру вид и тщательно проверить результаты перевода. Подробнее о том, как мы решали задачу автоматизации перевода топонимов, читайте в блоге Яндекса на Хабрахабре.
Карты всех стран и городов выполнены в едином дизайне — мы подробно рассказывали о нем в блоге на примере Москвы. Мировая карта доступна и в веб-версии, и в мобильных приложениях Яндекс.Карт. Кроме того, мировую карту можно попробовать в новом интерфейсе, запущенном совсем недавно в режиме бета-версии.
Мария Орлова, руководитель отдела геоинформационных данных
В Яндексе, как и в других крупных компаниях, очень много разных подразделений. Большие и маленькие, всем известные и такие, о работе которых пользователи сервисов Яндекса задумываются редко. Одно из таких подразделений — служба разработки технической документации.
Техническая документация — это инструкция или справочник, объясняющий, как работать с сервисом или как он устроен. Вы наверняка сталкивались с технической документацией — если не в разделе «Помощь» на Яндексе, то в виде инструкции к стиральной машине. От понятности и грамотности технической документации зависит удобство работы со многими сервисами. Например, документация позволяет владельцам магазинов узнать, как правильно зарегистрировать свой магазин на Яндекс.Маркете, а клиентам Яндекс.Директа помогает правильно составить текст рекламного объявления.
Кроме «Помощи» для пользователей у Яндекса есть документация для разработчиков и других технических специалистов – описания технологий, руководства и справочники по использованию API (программных интерфейсов) сервисов Яндекса. Например, документация на технологию БЭМ или API Карт. Также много внутренней документации, предназначенной для сотрудников Яндекса. Без нее вся информация хранилась бы только в голове у людей, и им пришлось бы бесконечно рассказывать всем заинтересованным, как протекает тот или иной процесс или как правильно реализовать ту или иную функцию.
Служба разработки технической документации существует в Яндексе с сентября 2006 года. Это одно из постоянно развивающихся подразделений. Сейчас в нашей службе работает уже 25 технических писателей. Четверо специализируются на написании инструкций для пользователей, пятнадцать – на разработке документации для разработчиков, а остальные делают и то, и другое.
В этом году мы выступали на конференции YaC с рассказом о нашей работе. Когда мы готовили этот доклад, нам пришла в голову идея провести конкурс для технических писателей. В качестве конкурсного задания мы решили предложить переработать какой-нибудь широко известный документ. Перебрали тексты законов, кодексов, правил и остановились на Правилах дорожного движения. ПДД, как и все правовые документы, написаны сложным языком, который больше подходит для однозначной трактовки в судебных разбирательствах, хотя должны быть понятны миллионам людей. Поэтому задание по переработке статьи ПДД как нельзя лучше позволяет техническому писателю применить свои профессиональные навыки в новой области.
Полученные работы оценивались по тем же критериям, которые мы используем при проверке своей документации:
Структура. В хорошо организованном документе легко искать нужную информацию.
Язык изложения. Справочники и руководства не читаются как романы. В технических текстах важно ясно и коротко донести смысл. В идеале каждое предложение должно быть понятно с первого прочтения.
Полнота. Важно не потерять нужную информацию. При этом не стоит путать полноту с избыточностью.
Точность. Информация должна быть изложена фактически точно и технически грамотно.
Полезность для целевой аудитории. Документ обязан отвечать на вопросы тех пользователей, для которых он предназначен.
Первое место заняла Наталья Воронцова из Москвы. Второе место разделили Инна Якименко из Санкт-Петербурга и Егор Абраменко из Барнаула. Работы Инны и Егора очень разные, и каждая хороша по-своему, поэтому мы решили присудить второе место обоим участникам.
Выполненные работы мы не публикуем. Но авторы вольны сделать это сами на любых площадках.
Светлана Каюшина, руководитель службы разработки технической документации
Яндекс.Карты научились понимать человеческий язык. Теперь с ними можно общаться как с друзьями и знакомыми: не проставлять точки маршрута, а просто спрашивать в поиске [как добраться от улицы Вавилова до Киевского вокзала]. Точно так же можно находить нужные перекрёстки, например [пересечение Каширского шоссе и МКАД].
По поисковому запросу Яндекс.Карты определяют, что пользователь хочет построить маршрут, после чего выделяют названия географических объектов. Эти названия они затем автоматически подставляют в поля начальной и конечной точки на вкладке «Маршруты».
Кстати, подсказывать дорогу умеет и обычный поиск Яндекса. На запрос [какие автобусы едут от метро Калужская до Херсонской улицы] появится колдунщик Маршрутов с заполненными полями.
Умения современных компьютеров оказались бы полной неожиданностью для людей, живших 50 лет назад. В тогдашней фантастике простые роботы работали слугами, а самые сложные, уникальные, занимались высшей математикой. Роботы представлялись человекоподобными, и такие способности, как умение сохранять равновесие, ориентироваться в окружающем мире, понимать обращенную к ним речь, считались само собой разумеющимися. Но попытки построить подобные системы показали, что на самом деле эти навыки очень сложны, и как их повторить, не совсем понятно. Сейчас высшей математикой способен заниматься телефон в вашем кармане (например, с помощью одного из этих приложений), а вот слуг что-то не видно. Вы ежедневно пользуетесь услугами Великого Всемирного Информатория, что в старой фантастике разрешалось лишь лицам со спецдоступом (ох уж этот XX век), но в ресторане вас по-прежнему обслуживает человек.
Школьное образование, к сожалению, не успевает за развитием нашей отрасли, и потому создает в головах большей части людей не очень корректную картину. У них возникает популярное заблуждение, согласно которому компьютеры не способны чему-либо учиться и делают только то, на что запрограммированы — тупо, но быстро и старательно. На самом деле это давно не так. Создавать программы, способные анализировать данные, обобщать их, делать выводы и учиться таким образом чему-то новому для себя, мы умеем уже десятки лет, и с каждым годом всё лучше и лучше. Этому посвящена обширная дисциплина: машинное обучение, и она давно не является каким-то тайным знанием, доступным лишь избранным. Соответствующие методы и теории уже разработаны до такой степени, что им можно обучать, например, талантливых студентов. При Яндексе уже несколько лет работает целое учебное заведение — Школа анализа данных, — большая часть курсов которого посвящена именно таким методам. В начале октября этого года Яндекс провёл конференцию, на которую приехали ведущие исследователи в этой области из многих стран мира.
Не стоит думать, что машинное обучение — что-то экзотическое, используемое только в детекторах Большого адронного коллайдера (хотя, честно говоря, там оно тоже используется). Вовсе нет.
Каждый раз, задавая запрос в Яндексе, вы пользуетесь плодами машинного обучения. Вы, наверное, замечали, что количество найденного почти по любому запросу огромно: сотни тысяч, часто — миллионы результатов. Большая часть из них неинтересные, бесполезные, лишь случайно упоминают слова запроса или вообще являются спамом. Для ответа на ваш запрос нужно мгновенно отобрать из всех найденных результатов десятку лучших. Написать программу, которая делает это с приемлемым качеством, не под силу никакому программисту-человеку. Десять результатов по вашему запросу отобраны при помощи формул, полученных в ходе машинного обучения. С помощью созданной у нас технологии Матрикснет Яндекс обучает на кластере FML сотни таких формул в год.
Каждый раз, когда входящее письмо с предложением увеличить грудь, взять дешёвый кредит или посмотреть новый вирус попадает в папку «Спам», вы пользуетесь машиннообученным классификатором. Вы пользуетесь результатами машинного обучения каждый раз, когда диктуете голосовые команды своему телефону или навигатору, когда смотрите прогноз пробок на следующий час, когда загружаете картинку, чтобы поискать похожие в системе «Сибирь» и во многих других ситуациях. В день пользователь Яндекса, сам о том не подозревая, сталкивается с машинным обучением десятки раз.
О том, как устроено машинное обучение, рассказать в одной записи в блоге невозможно. В конце концов, не зря на эту тему пишут тома и собирают международные научные конференции. Но об отдельных интересных фактах рассказать всё же стоит.
Методы машинного обучения, исторически изобретённые первыми, были попытками скопировать природу: так называемые «нейронные сети» имитировали работу нейронов коры головного мозга (сейчас мы знаем, что имитировали неверно, но это не мешало им добиваться определенных успехов), появившиеся чуть позже «генетические алгоритмы» — эволюцию по Дарвину и менделевскую генетику. Эти попытки были чем-то похожи на самолёт с чертежей Леонардо да Винчи, машущий перепончатыми крыльями. Как современные самолёты не похожи на летучих мышей, так и методы машинного обучения, применяемые в XXI веке, чаще не являются бионическими.
Математическая основа современного машинного обучения, заложенная, в том числе, нашими соотечественниками Владимиром Вапником и Алексеем Червоненкисом, довольно сложна, но можно попытаться описать «на пальцах» то, как работают алгоритмы, использующие эту математику. Например, мы хотим научить компьютер определять, изображён ли на фотографии человек. Для этого мы берём очень много фотографий и вручную раскладываем на две стопки: в одну фотографии людей, в другую всё остальное — пейзажи, натюрморты, автомобили, животные, абстракции. Компьютер, получивший эти две стопки, сравнивает фотографии и выявляет характерные признаки изображения человека.
На первом шаге алгоритм берёт самый простой признак, выдающий результат, хоть как-то похожий на нужный. В данном случае он начинает считать, что человек — это всё, что похоже на вертикальный тёмный прямоугольник пропорцией примерно 4:1. Этот «метод», при всём его шокирующем идиотизме, неплохо отличает людей от кошек, автомобилей, домов и деревьев, еды в инстаграме и многих других объектов. На втором шаге алгоритм смотрит на ошибки первого шага: например, Джа-Джа Бинкс и платяной шкаф моей бабушки ошибочно сочтены людьми, а Обеликс и Саша Грей ошибочно сочтены объектами, непохожими на людей. Снова выбирается самый простой признак, но на этот раз такой, который обращает повышенное внимание на ошибки первого и, по возможности, исправляет их. У совокупности двух признаков ошибок будет уже меньше, и Обеликса он распознает правильно. Но ошибки всё ещё будут. Можно приступать к третьему шагу. Чем больше проходит шагов, тем больше признаков можно учесть, и через несколько сотен шагов полученный «определитель человека», обращающий внимание только на яркость прямоугольных областей, уже хорошо справляется с работой.
Такой процесс является основой известного алгоритма AdaBoost, широко используемого в компьютерном зрении. В таком изложении этот алгоритм выглядит просто, но дьявол, как всегда, в деталях. Что лучше выбирать: чуть более простой, но хуже работающий признак, или наоборот? Как именно записать условие «обращай повышенное внимание на ошибки предыдущих шагов»? На каком шаге остановиться? Как правильно комбинировать найденные признаки?
Интересно, что, хотя ответ на эти вопросы найден опытным путем, никто и по сей день не может в точности объяснить, почему именно те решения, которые используются в AdaBoost, работают лучше прочих вариантов. На прошедшей конференции Школы анализа данных Яндекса сам автор алгоритма, Роберт Шапире, рассказывал о различных подходах к этой проблеме, но даже ему исчерпывающее объяснение неизвестно. А было бы здорово его найти: строгое математическое объяснение, скорее всего, позволит усовершенствовать и этот метод, и многие другие.
Другой докладчик конференции, Ян Лекан, рассказывал о технике, известной под названием «свёрточные нейронные сети» (convolutional neural networks). Технику эту он изобрел давным-давно, примерно четверть века назад, и неуклонно совершенствует с тех пор; учёные вообще живут в вечности, и им в ней хорошо. Свёрточные нейронные сети интересны своей близостью к природе (даже если зрительная кора млекопитающих устроена по-другому, она вполне могла бы быть и такой), огромной скоростью распознавания образов, но главное в них, конечно, те замечательные результаты, которых можно добиться с их помощью. Ян Лекан прямо с кафедры показывал мгновенное распознавание компьютером разных предметов: наводил на них по очереди камеру ноутбука, и тот уверенно опознавал пульт управления, микрофон, дисплей, докладчика и прочие предметы. Потом прямо на лету, за пару секунд и пару кадров, обучил его отличать себя от случайного человека из зала. Если продолжать сравнение бионических методов с летательными аппаратами да Винчи, получается, что орнитоптеры отлично летают и успешно конкурируют с самолётами.
Демонстрировался на конференции и короткий документальный фильм о том, как мобильный робот, похожий на Валли из одноименного мультфильма, но конструируемый по заказу американских военных, при помощи одной картинки с камеры (без участия человека) уверенно чувствует себя в настоящем лесу, объезжая на скорости деревья и прочие препятствия, а также солдат людей. Непонятно, почему это всё до сих пор не засекретили и совершенно спокойно рассказывают в России со всеми подробностями. Видимо, дело в том, что на дворе уже не ХХ век.
В общем, конференция получилась замечательная, и надеюсь, что не последняя. Машинное обучение активно работает над слегка запоздавшим светлым будущим. Если развитие человеческой (и компьютерной) мысли и дальше пойдет теми же темпами, то на нашем веку мы наконец дождемся настоящих роботов, именно таких, которых нам обещали когда-то давным-давно.
Андрей Плахов, руководитель службы функциональности поиска
