Алгоритмы *

Расскажем о том, как устроен поиск похожих треков среди всех аудиозаписей ВКонтакте.

Зачем всё это надо?

У нас действительно много музыки. Много — это больше 400 миллионов треков, которые весят примерно 4 ПБ. Если загрузить всю музыку из ВКонтакте на 64 ГБ айфоны, и положить их друг на друга, получится башня выше Эйфелевой. Каждый день в эту стопку нужно добавлять еще 25 айфонов — или 150 тысяч новых аудиозаписей объёмом 1.5 ТБ.

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

Если научиться достаточно точно находить одинаковые (или очень похожие) аудиозаписи, можно применять это с пользой, например:

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

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

Без высшей математики мы бы лишились алгоритма Шора для факторизации целых чисел в квантовых компьютерах, калибровочной теории Янга-Миллса для построения Стандартной модели в физике элементарных частиц, интегрального преобразования Радона для медицинской и геофизической томографии, моделей эпидемиологии, анализов рисков в страховании, моделей стохастического ценообразования финансовых производных, шифрования RSA, дифференциальных уравнений Навье-Стокса для прогнозирования изменений движения жидкостей и всего климата, всех инженерных разработок от теории автоматического управления до методов нахождения оптимальных решений и еще миллиона других вещей, о которых даже не задумываемся.

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

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

Распознавание автомобильных номеров до сих пор является самым продаваемым решением на основе компьютерного зрения. Сотни, если не тысячи продуктов конкурируют на этом рынке уже на протяжении 20-25 лет. Отчасти поэтому сверточные нейронные сети (CNN) не бьют прежние алгоритмические подходы на рынке.

Но опыт последних лет говорит, что алгоритмы CNN позволяют делать надежные и гибкие для применения решения. Есть и еще одно удобство: при таком подходе всегда можно улучшить надежность решения на порядок после реального внедрения за счет переобучения. Кроме того, такие алгоритмы отлично реализуются на GPU (графических модулях), которые значительно эффективней с точки зрения потребления электроэнергии, чем обычные процессоры. А платформа Jetson TX от NVidia так просто потребляет очень мало по меркам современных вычислителей. Наглядное «энергетическое превосходство»:

Больше года назад, когда я работал антиспамщиком в Mail.Ru Group, на меня накатило, и я написал про эксперименты с malloc. В то время я в свое удовольствие помогал проводить семинары по АКОСу на ФИВТе МФТИ, и шла тема про аллокацию памяти. Тема большая и очень интересная, при этом охватывает как низкий уровень ядра, так и вполне себе алгоритмоемкие структуры. Во всех учебниках написано, что одна из основных проблем динамического распределения памяти — это ее непредсказуемость. Как говорится, знал бы прикуп — жил бы в Сочи. Если бы оракул заранее рассказал весь план по которому будет выделяться и освобождаться память, то можно было составить оптимальную стратегию, минимизирующую фрагментацию кучи, пиковое потребление памяти и т.д. Отсюда пошла возня с ручными аллокаторами. В процессе раздумий я натолкнулся на отсутствие инструментов логирования malloc() и free(). Пришлось их написать! Как раз про это была статья (а ещe я изучал macOS). Были запланированы две части, однако жизнь круто повернулась и стало не до malloc(). Итак, пора восстановить справедливость и реализовать обещанное: ударить глубоким обучением по предсказанию работы с кучей.

Внутри:

• Совершенствуем libtracemalloc, перехватчик malloc().
• Строим LSTM на Keras — глубокую рекуррентную сеть.
• Обучаем модель на примере работы реального приложения (vcmi/vcmi — а вы думали, причем здесь Heroes III?).
• Удивляемся неожиданно хорошим результатам.
• Фантазируем про практическое применение технологии.
• Исходники.

Интересно? Добро пожаловать под кат.

Сегодня будем рисовать геометрические фракталы, которым уделяют незаслуженно мало внимания. А между тем, тут каждый фрактал — маленький шедевр, поражающий воображение!


Дальше много картинок и gif-анимация. Но прежде, чем переходить под кат, посмотрите на картинку выше и скажите, что на ней нарисовано?

(Полный исходный код лежит тут)

Сидя на пятичасовом занятии по химии, я часто скользил взглядом по таблице Менделеева, висящей на стене. Чтобы скоротать время, я начал искать слова, которые мог бы написать, используя лишь обозначения элементов из таблицы. Например: ScAlEs, FeArS, ErAsURe, WAsTe, PoInTlEsSnEsS, MoISTeN, SAlMoN, PuFFInEsS.

Затем я подумал, какое самое длинное слово можно составить (мне удалось подобрать TiNTiNNaBULaTiONS), поэтому я решил написать программу на Python, которая искала бы слова, состоящие из обозначений химических элементов. Она должна была получать слово и возвращать все его возможные варианты преобразования в наборы химических элементов:

• Вход: Amputations
• Выход: AmPuTaTiONS, AmPUTaTiONS

Всем привет! Настало время пополнить наш с вами алгоритмический арсенал.

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

UPD 01.2022: С февраля 2022 г. ML-курс ODS на русском возрождается под руководством Петра Ермакова couatl. Для русскоязычной аудитории это предпочтительный вариант (c этими статьями на Хабре – в подкрепление), англоговорящим рекомендуется mlcourse.ai в режиме самостоятельного прохождения.

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

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

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

А Вы когда-нибудь задумывались, за что мы платим, пользуясь такси?

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

Корректирующие (или помехоустойчивые) коды — это коды, которые могут обнаружить и, если повезёт, исправить ошибки, возникшие при передаче данных. Даже если вы ничего не слышали о них, то наверняка встречали аббревиатуру CRC в списке файлов в ZIP-архиве или даже надпись ECC на планке памяти. А кто-то, может быть, задумывался, как так получается, что если поцарапать DVD-диск, то данные всё равно считываются без ошибок. Конечно, если царапина не в сантиметр толщиной и не разрезала диск пополам.

Как нетрудно догадаться, ко всему этому причастны корректирующие коды. Собственно, ECC так и расшифровывается — «error-correcting code», то есть «код, исправляющий ошибки». А CRC — это один из алгоритмов, обнаруживающих ошибки в данных. Исправить он их не может, но часто это и не требуется.

Давайте же разберёмся, что это такое.

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

Внимание! Много текста и мало картинок. Я постарался всё объяснить, но без карандаша и бумаги текст может показаться немного запутанным.

Чтобы сходу понимать материалы об инфраструктуре открытых ключей, сетевой безопасности и HTTPS, нужно знать основы криптографической теории. Один из самых быстрых способов изучить их — посмотреть или прочитать лекцию Владимира ivlad Иванова. Владимир — известный специалист по сетям и системам их защиты. Он долгое время работал в Яндексе, был одним из руководителей нашего департамента эксплуатации.


Мы впервые публикуем эту лекцию вместе с расшифровкой. Начнём с первой части. Под катом вы найдёте текст и часть слайдов.

Псевдотонирование: обзор

Про сегодняшнюю тему для программирования графики — псевдотонирование (дизеринг, псевдосмешение цветов) — я получаю много писем, что может показаться удивительным. Вы можете подумать, что псевдотонирование — это не то, чем программисты должны заниматься в 2012 году. Разве псевдосмешение — не артефакт история технологий, архаизм времён, когда дисплей с 16 миллионами цветов программистам и пользователям мог только сниться? Почему я пишу статью о псевдотонировании в эпоху, когда дешевые мобильные телефоны работают с великолепием 32-битной графики?

На самом деле псевдотонирование по-прежнему остаётся уникальным методом не только по практическим соображениям (например, подготовка полноцветного изображения для печати на чёрно-белом принтере), но и по художественным. Дизеринг также находит применение в веб-дизайне, где этот полезный метод используется для сокращения числа цветов изображения, что уменьшает размер файла (и трафик) без ущерба для качества. Он также используется при уменьшении цифровых фотографий в формате RAW в 48 или 64 бита на пиксель до RGB в 24 бита на пиксель для редактирования.

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

До:



После:



Заинтригованы? Но обо всем по порядку.

t-SNE

t-SNE — это очень популярный алгоритм, который позволяет снижать размерность ваших данных, чтобы их было проще визуализировать. Этот алгоритм может свернуть сотни измерений к всего двум, сохраняя при этом важные отношения между данными: чем ближе объекты располагаются в исходном пространстве, тем меньше расстояние между этими объектами в пространстве сокращенной размерности. t-SNE неплохо работает на маленьких и средних реальных наборах данных и не требует большого количества настроек гиперпараметров. Другими словами, если взять 100 000 точек и пропустить их через эту волшебный черный ящик, на выходе мы получим красивый график рассеяния.

Введение

Почему псевдо-3d?

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

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

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

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

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

Сразу оговорюсь, что данный текст — это не сухая выжимка основных идей с красивыми графиками и обилием технических терминов (такой текст называется научной статьей и я его обязательно напишу, но потом, когда нам заплатят призовые $20000, а то, не дай бог, начнутся разговоры про лицензию, авторские права и прочее.) (UPD: https://arxiv.org/abs/1706.06169). К моему сожалению, пока устаканиваются все детали, мы не можем поделиться кодом, который написали под эту задачу, так как хотим получить деньги. Как всё утрясётся — обязательно займемся этим вопросом. (UPD: https://github.com/ternaus/kaggle_dstl_submission)

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

Недавно закончилось соревнование по машинному обучению Dstl Satellite Imagery Feature Detection в котором приняло участие аж трое сотрудников Avito. Я хочу поделиться опытом участия от своего лица и рассказать о решении.

Я с удовольствием погрузился в изучение исходного кода Quake World и изложил в статье всё, что я понял. Надеюсь, это поможет желающим разобраться. Эта статья разделена на четыре части:

• Архитектура
• Сеть
• Прогнозирование
• Визуализация

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

UPD 01.2022: С февраля 2022 г. ML-курс ODS на русском возрождается под руководством Петра Ермакова couatl. Для русскоязычной аудитории это предпочтительный вариант (c этими статьями на Хабре – в подкрепление), англоговорящим рекомендуется mlcourse.ai в режиме самостоятельного прохождения.

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

В начале марта в американском городе Кона завершилась встреча международной рабочей группы WG21 по стандартизации C++ в которой участвовали сотрудники Яндекса.

Заседания, как обычно, занимали целый день плюс дополнительно заседала подгруппа по работе с числами.

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