Алгоритмы *

Динамическое ценообразование является современным подходом к ценообразованию в ритейле. Оно напрямую связано с моделированием спроса, что позволяет проводить оптимизацию цен на будущий период. В этой задаче популярным решением является использование машинного обучения, однако, есть мнение, что Reinforcement Learning (а именно, многорукие бандиты), способны выступить сильной альтернативой моделям ML для динамического ценообразования. Но так ли это на самом деле? Попробуем разобраться в этой статье, держа в уме практические аспекты.

Откройте почти любую реализацию перевода чисел из арабской системы в римскую и вы почти со 100% вероятностью увидите там знаменитые дифтонги "CM" (900), "CD" (400) и так далее. И поначалу кажется, что без них не обойтись. Но это не так!

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

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

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

Всем привет!

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

Всё дальнейшей вылилось в эту статью.

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

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

Идея проекта

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

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

Головоломка относится к классу так называемых «бильярдных задач», изучаемых в области динамических систем. Решение текущей задачи принадлежит профессору математики университета Джонса Хопкинса Эмили Рил.

Рассмотрим квадратную комнату в плоскости XY, и пусть A («ассасин») и T («цель») — две произвольные, но фиксированные точки внутри комнаты. Предположим, что комната схожа по физическим характеристикам с бильярдным столом, так что любой «выстрел» А рикошетит от стен, причём угол падения равен углу отражения. Можно ли заблокировать любой возможный «выстрел» А в Т, разместив конечное количество аналогичных по свойствам точек («телохранителей») в комнате?

Планирование — это сложный процесс, в котором мы сначала создаем образ наилучшего будущего, а затем выполняем поиск наиболее эффективного и удобного для нас пути к его достижению. Однако тенденция такова, что зачастую планы создаются для успокоения. При этом случайности отводится очень важная, но скорее негативная роль — оправдывать то, что оправдывать не следует. Сколько раз вам доводилось слышать, что невозможно учесть все возможные случайные факторы? Или что-то вроде: "Человек предполагает, а Бог располагает"? Было бы неразумно верить, что любые проблемы, которые может вызывать случайность, возможно решить с помощью прикладной математики. При этом нам все равно необходимо максимально четко понимать роль и влияние случайность в наших планах, чтобы не оправдывать ей потом все наши неудачи.

Всем привет! Меня зовут Артём Важенцев, я аспирант в Сколтехе и младший научный сотрудник AIRI. Я работаю в группе под руководством Александра Панченко и Артёма Шелманова. Мы занимаемся исследованием и разработкой новых методов оценивания неопределенности для языковых моделей. Этим летом мы представили две статьи на конференции ACL 2023. В одной из них мы описали новый гибридный метод оценивания неопределенности для задачи выборочной классификации текстов для данных с неоднозначными примерами — его внедрение поможет нейросетям лучше находить токсичность в комментариях или угадывать тональность сообщений. В этом тексте я бы хотел рассказать подробнее о нашем методе и процессе его разработки.

В иерархических структурах регулярно возникает потребность определить ближайшего общего предка в дереве, он же наименьший общий предок (Lowest (Least) Common Ancestor).

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

В прошлых частях мы рассмотрели семейство квантовых гейтов: Инвертор, C-NOT, Адамара, инверсия фазы. Но, согласитесь, как-то не похожи они на привычные нам гейты классических компьютеров: AND, OR, XOR, NOT. Ну, ладно, с NOT это я хватил лишку, NOT это вполне тоже самое, что квантовый инвертор, который мы рассмотрели самым первым гейтом в прошлых частях.

А как быть с остальными? Можем ли мы как-то сделать, к примеру, квантовый AND?
И да, и нет. Как вы помните из второй части, квантовая операция обязана обладать двумя важными свойствами:

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

• свойство сохранения нормы, которое заключается в том, что сумма вероятностей всех возможных состояний должна быть 1. А значит сумма квадратов всех амплитуд должна быть 1.

Как вы, может, помните с первым свойством я в прошлых частях приврал. На самом деле, свойство обратимости заключается в том, что для каждой квантовой операции существует обратная квантовая операция, которую можно вычислить из исходной определенными математическими действиями. Нам просто до сих пор везло, что обратные операции для гейтов Адамара, инвертора, C-NOT и инверсии фазы являлись теми же самыми операциями. Поэтому я и приврал тогда, что обратимость операции, примененная дважды возвращает в исходное состояние. Нет, забудьте, это неправда. Теперь обратимость сформулируем следующим образом.

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

Привет, Хабр! Когда заходет речь о поиске кратчайшего пути между двумя вершинами выбор обычно ложится на Дейкстре или Беллмана-Форда, однако есть ещё один алгоритм, который может сработать быстрее Беллмана, но не "сломается" на графах с отрицательными рёбрами.

Приятного чтения!

Хороший автомобильный маршрут из точки А в точку Б должен, с одной стороны, быть кратчайшим, а с другой — удобным для водителя. Как правильно вычислить время в пути мы уже рассказали, теперь — об удобстве маршрутов: что это такое, как его измерить и как мы его повышали.

Некоторые оптимальные алгоритмы, оказывается, можно вывести из неоптимальных, пользуясь эквивалентными преобразованиями алгоритма. Бёрд и Меертенс разработали формализм, который устанавливает свойства функций высшего порядка map, fold, scan, позволяющие преобразовывать алгоритмы в эквивалентные. (См. также на Вики). Ниже представлен вольный перевод статьи Бёрда.

Рассмотрим задачу поиска максимальной суммы сегмента массива. Эту задачу можно переформулировать в виде математически точного ответа:

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

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

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

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

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

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

Исследователи давно задавались вопросом, неизбежен ли этот компромисс. Неужели невозможно быстро найти выход, не забыв дорогу?