Рубрика «Алгоритмы» - 84

Пишем XGBoost с нуля — часть 2: градиентный бустинг - 1

Всем привет!

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

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

Пишем XGBoost с нуля — часть 2: градиентный бустинг - 2
Читать полностью »

image

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

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

Читать полностью »

image

Физик Лев Ландау играл в ментальную игру с советскими номерами[1]. Таблички имели форму двух цифр, тире, еще двух цифр и некоторых букв.

Правила игры

Его игра заключалась в том, чтобы применять математические операторы к числам по обе стороны от тире, чтобы тире можно было заменить на знак равенства. Например, если взять номерной знак 44-74, одним из решений будет

4! + 4 = 7 * 4

Обратите внимание, что мы можем вставить операторы, такие как !, + и *, но не добавляя цифр.

Есть ли решение для каждого возможного номерного знака? Это зависит от того, какие операторы вы разрешаете использовать.

Вы можете тривиализировать игру, применив операцию дробной части { x } к обеим сторонам, поскольку дробная часть целого числа равна нулю. Вы можете запретить оператор дробной части на том основании, что это явно не математическая операция старшей школы, или просто запретить ее, потому что она делает игру неинтересной.Читать полностью »

Пишем XGBoost с нуля — часть 1: деревья решений - 1

Привет!

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

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

Пишем XGBoost с нуля — часть 1: деревья решений - 2
Читать полностью »

В предыдущем туториале мы научились создавать и перемещать простые фигуры с помощью функций расстояний со знаком. В этой статье мы научимся комбинировать несколько фигур для создания более сложных полей расстояний. Большинству описанных здесь техник я научился из библиотеки функций расстояний со знаком на glsl, которую можно найти здесь (http://mercury.sexy/hg_sdf). Также существует несколько способов комбинирования фигур, которые я здесь не рассматриваю.

Комбинирование Signed Distance Fields в 2D - 1

Подготовка

Для визуализации полей расстояний со знаком (signed distance fields, SDF) мы будем использовать одну простую конфигурацию, а затем применим к ней операторы. Для отображения полей расстояний в ней будет использоваться визуализация линий расстояний из первого туториала. Ради упрощения мы будем задавать все параметры за исключением параметров визуализации в коде, но вы можете заменить любое значение свойством, чтобы сделать его настраиваемым.
Читать полностью »

Зачем нужна низкоуровневая оптимизация на Эльбрусе или как ускорить распознающую систему в полтора раза - 1

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

В качестве распознающей системы была рассмотрена система распознавания объектов живописи “в неконтролируемых условиях методом с обучением по одному примеру” [1]. Эта система строит описание изображения на основе особых точек и их дескрипторов, по которому выполняет поиск в индексированной базе картин. Мы проанализировали производительность данной системы и выделили наиболее времязатратную низкоуровневую часть алгоритма, который затем оптимизировали с помощью инструментов платформы Эльбрус.

Читать полностью »

О чём речь

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

Пост сопровождался весьма компактной и эффективной реализацией фильтра на C. Однако судя по комментариям, физический смысл этого кода, а равно и всей статьи, для кого-то остался туманным. Что ж, признаем честно: фильтр Маджвика — самый замысловатый из группы фильтров, основанных в общем-то на очень простых и элегантных принципах. Эти принципы я и рассмотрю в своём посте. Кода здесь не будет. Мой пост — не рассказ о какой-то конкретной реализации алгоритма оценивания ориентации, а скорее приглашение к изобретению собственных вариаций на заданную тему, которых может быть очень много.

image
Читать полностью »

Прелюдия

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

Часто работают с т.н. разреженными матрицами — теми, у которых нулей на порядки больше остальных значений. Такое, например, неизбежно, если имеешь дело с уравнениями в частных производных или с какими-нибудь другими процессами, в которых возникающие элементы в определяющих линейных соотношениях связаны лишь с «соседями». Вот возможный пример разреженной матрицы для известного в классической физике одномерного уравнения Пуассона $-phi^{''}=f$ на равномерной сетке (да, пока в ней нулей не так много, но при измельчении сетки их будет будь здоров!):

$begin{pmatrix}2 & -1 & 0 & 0 & 0\ -1 & 2 & -1 & 0 & 0\ 0 & -1 & 2 & -1 & 0 \ 0 & 0 & -1 & 2 & -1 \ 0 & 0 & 0 & -1 & 2end{pmatrix}$

Противоположные им матрицы — те, в которых на количество нулей не обращают внимания и учитывают все компоненты без исключения, — называют плотными.
Читать полностью »

Вступление

В данной статье я расскажу об известном алгоритме Хаффмана, а также о его применении в сжатии данных.

В результате напишем простенький архиватор. Об этом уже была статья на Хабре, но без практической реализации. Теоретический материал текущего поста взят из книги Роберта Лафоре «Data Structures and Algorithms in Java». Итак, все под кат!
Читать полностью »

Реверс-инжиниринг. История. Моя - 1

Всем привет,

На этот раз статья будет не технической (хотя в ней и будут попадаться какие-то технические термины/моменты), а скорее автобиографической, если так можно выразиться. Эта статья о том, как я докатился до такой жизни пришёл в реверс-инжиниринг, что читал, чем интересовался, где применял, и т.д. И, я почему-то уверен, что моя история будет иметь множество отличий от твоей. Поехали...Читать полностью »


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js