Привет, Хабр! Меня зовут Илья Котов, я Data Scientist в Сбере, участник профессионального сообщества NTA. Эта статья — первая часть небольшого цикла, посвящённого алгоритмам вложения вершин графа в векторное пространство. Сегодня расскажу об алгоритмах, основанных на матричных факторизациях. В качестве примера в статье используется занимательная задача поиска сообществ в графе. Что же, приступим!
Алгоритмы *
Все об алгоритмах
Новости
Задача коммивояжера (TSP) точное решение — метод динамического программирования
Задача коммивояжёра – одна из интереснейших подзадач комбинаторной оптимизации. Впервые мне пришлось с ней столкнуться, работая над логистической системой торгового предприятия.
Решение методом грубой силы не подходило из-за вычислительной сложности. Была предпринята попытка реализовать метод ветвления и границ с отсечением в глубину. В целом, подход себя оправдывал, но иногда при некоторых специфических входных данных алгоритм выдавал решение далёкое от оптимального.
Типичный маршрут доставки товара предприятия состоял из пары десятков точек, изредка доходящий до 25-26. Матрица расстояний рассчитывалась с помощью алгоритма Дейкстры. Дальше нужно было выбрать оптимальный маршрут из возможных.
“Вам курицу или рыбу?” – Рекомендательная система на “Своем Родном” знает ответ
Привет, Хабр!
Меня зовут Павел Дудукин, руководитель Data Science команды в Центре развития финансовых технологий Россельхозбанка.
Сегодня мы хотим продолжить цикл статей статей про решенные нами Data Science задачи и рассказать о построении и внедрении рекомендательной системы в одну из наших платформ по продаже фермерских продуктов “Свое Родное”.
А узнать из каких этапов, с какими особенностями мы столкнулись при разработке решения и как мы использовали рецепты для наших рекомендаций можно узнать ниже.
Алгоритм поиска цепочки друзей для пользователей соцсети
Будучи студентом, я решил в качестве курсовой разработать бота для поиска цепочки друзей для соцсети. Мне это показалось достаточно интересным, начал поиск информации на эту тему. В итоге я наткнулся на статью о теория шести рукопожатий, там была описана идея двунаправленного поиска, что показалось мне самым лучшим решением для такой задачи. Вот только никакого алгоритма и его реализации я не обнаружил, поэтому решил разработать свой вариант алгоритма. Теперь же хочу поделиться алгоритмом, который мне удалось разработать.
Генерация API сайта на основе заданных пользователем функций
Основная идея
Идея достаточно простая: в определенной директории задаётся API функция в виде файла php которая возвращает анонимную функцию. Функции могут быть четырех типов: Put (изменение значений), Get (кеширование до изменения зависимостей), LifeTime (кеширование по времени), Direct (прямой вызов). При этом в функциях типа Get кешируют своё значения до вызова соответствующего значения Put.
Видеоаналитика на взрывоопасном заводе площадью в 700 футбольных полей
Есть распространённый стереотип, будто на заводах надо каски детектировать или даже огонь. Но ведь идея в том, чтобы стремиться не допустить огня и всяких происшествий, а не фотографировать их. Поэтому на практике мы стараемся детектировать то, что происходит до того, как что-то подтечёт, задымится, загорится или пойдёт не по плану.
Меня зовут Щемелинин Вадим, я четыре года работаю в сфере цифровизации промышленности в компании «СИБУР Диджитал». Моя основная задача — развитие Индустрии 4.0 в холдинге. Одним из продуктов моего направления является видеоаналитика. Сегодня я расскажу про сложности, с которым сталкиваются Python-разработчики, внедряя машинное зрение в нефтехимическую индустрию.
Исследователи показывают, что кубиты могут быть такими же безопасными, как и биты
Новый результат показывает, что квантовая информация теоретически может быть защищена от ошибок точно так же, как и классическая информация.
О том, как алгоритм Дейкстры реализовывал и некоторых его применениях
Приветствую Вас, хабровчане!
В статье поговорим о всем известном алгоритме Дейкстры для поиска кратчайших путей между вершинами взвешенного графа, а также о том, как с помощью данного алгоритма найти оптимальный путь между двумя заданными точками на поверхности и обойти препятствия в лабиринте.
Улучшаем маршруты обхода на складе силами веб-программиста и математики
Сразу к сути: есть склад, где все бизнес-процессы уже отлажены и в целом всех всё устраивает. Ничего, что даст рост в 30%, сделать уже невозможно, но хочется. Поставлена цель: оптимизировать маршрут, по которому идёт сборщик товаров, чтобы товар собирался быстрее. Результат 2-3% роста вполне устроит. Ограничения:
- останавливать работу склада для экспериментов нельзя
- денег — кроме зарплаты — не выделим
- специалистов в этой области не имеется — свободен только веб-программист, да и тот без профильного образования
- закончить нужно не то, чтобы ещё вчера, но через две недели точно.
Статью можно считать продолжением темы наглядного применения известных алгоритмов где-нибудь в промышленности. В этот раз в работу вступает алгоритм k-ближайших соседей.
Для прочтения знать сам алгоритм k-ближайших соседей не требуется — он очень простой и станет ясен ещё в ходе прочтения. Он чем-то похож на теорему Пифагора, только на стероидах.
Как построить прогноз спроса и не потерять голову
Всем привет! Представьте себе ситуацию: ваша уютная маленькая команда Data Science занимается прогнозированием спроса для пары десятков дарксторов с помощью какого-нибудь коробочного Prophet. И в один прекрасный день к вам приходит бизнес. Бизнес садится, закидывает ногу на ногу, закуривает сигару и говорит:
«Мы хотим максимально автоматизировать закупки. Нам нужно, чтобы вы умели строить прогноз по всем товарам, старым и новым, для всех дарксторов, старых и новых. А их будет много, их будут сотни, тысячи, миллионы. А ещё у нас будет миллион видов скидок и разные типы ценообразования, и ещё куча промо-механик и конкурсов интересных. Мы хотим, чтобы прогноз обязательно адекватно на всё это реагировал». (с) Типичный Бизнес
Хорошо, думаем мы, кажется, что это звучит нетрудно…
С этой задачи начинается моя история о прогнозе спроса в Самокате. Меня зовут Мария Суртаева, я Data Scientist и расскажу о концепции прогноза спроса, его практических задачах и роли градиентного бустинга.
API для Инвестиций, или Как написать торгового робота
На связи команда Тинькофф Инвестиций. В этой статье разберем, как клиенты с минимальными навыками программирования создают торговых роботов. Базой будет API брокера Тинькофф Инвестиций — Tinkoff Invest API. Добро пожаловать на борт!
Программная генерация костюма на основе биологических параметров человека
Предупреждение! Эта публикация сыра, как воды мирового океана!
!Эта публикация - размышление, публикация концепт!
Идея передать внутреннее состояние человека, волнует меня(подозреваю что и других людей). Это можно реализовать через творчество, музыку, живопись, литературу, танец, слово. Но любой из этих жанров имеет свой порог вхождения.
Также, далеко не всегда можно доступно обозначить себя через вышеперечисленное.
Одежда, один из доступных способов показать себя.
Используем нейросеть для генерации стихов в стиле «Евгения Онегина»
Мне нравится концепция, согласно которой речь – это, в первую очередь, не способ коммуникации, а отражение сознания. В таком случае стихи - это отражение красоты сознания. Но сможет ли нейросеть сгенерировать стихотворения, похожие на рукотворные? Давайте попробуем сделать такой алгоритм.
Шаг 1 – выбираем архитектуру
Тренд последних лет в обработке естественных языков (NLP) - использование нейронных сетей. А если смотреть более узко, то - нейронных сетей архитектуры «трансформер», включающих блок внимания «attention». Суть подхода в том, чтобы использовать при кодировке как в энкодере эмбединга (вектор признаков на выходе слоя нейронной сети), так и в декодере, механизм «attention», позволяющий учитывать взаимосвязь между словами и «фокусировать внимание» нейронной сети только на контексте, имеющем значение для слова.
Одной из архитектур на основе трансформеров является ruBERT, его и возьмем. Но для чистоты эксперимента попробуем также использовать и более старый подход, а именно LSTM нейронную сеть.
Мой личный опыт восстановления старых фотографий с помощью нейросетей
Мой скромный опыт запуска нейросетей на ноутбуке для восстановления старых фотографий.
Истории
Применение расстояния Левенштейна с целью оптимизации работы склада
Активно изучаем различные алгоритмы? Читаем про поиск k-ближайших соседей, задачу о рюкзаке, всякие алгоритмы сортировки, поиска и т. п.? А часто читаем примеры их практического внедрения на каком-нибудь предприятии? Такие истории встречаются реже, чем даже обзоры книг по этим же алгоритмам.
Предлагаю всем вместе начать исправлять эту ситуацию и приглашаю почитать о том, как на промышленном складе применяли — внезапно! — алгоритм Левенштейна (способ нечёткого сравнения строк).
Значительная часть нюансов спрятана под спойлеры, чтобы не отвлекать от сути статьи, а также не отпугивать маленьких. Обычно такие статьи становятся очень длинными, но мне удалось уместиться примерно в 3200 слов.
Для понимания статьи читателю хватит самого поверхностного умения чуть-чуть читать код си-подобного синтаксиса. Познания в области работы склада не обязательны. Почитать про расстояние Левенштейна по ссылке выше желательно.
Сферический БПЛА в воздухе
Представьте, что вы решили сконструировать воздушный шар. И пусть даже не в натуральную величину, а уменьшенную модель – но главное, чтобы летала!!! С чего начать, как подступиться к этой задаче?
Раз задача инженерная, начать нужно с математики и физики. В нашем случае с того, чтобы разобраться, почему воздушный шар летает, и какие силы при этом на него действуют.
Пришло время программистов-самоучек
И почему к нам стоит присоединиться
Миф
Среди комментариев к одному из постов с рекламой моей книги «The Self-Taught Programmer» («Computer Science для программиста-самоучки. Все что нужно знать о структурах данных и алгоритмах») был и такой: «Хочу научиться программировать, но слышал, что в компаниях не воспринимают всерьез программистов без академической степени». К сожалению, это распространенное убеждение, и к счастью – неверное.
Как математика помогает логистике быть точнее. Опыт ПГК
Цифровые алгоритмы помогают решать реальные бизнес-задачи в самых разных сферах. Логистика — не исключение. Главные инструменты логиста — вовсе не карта, линейка и калькулятор, а сложные IT-системы, которые основаны на математическом моделировании и алгоритмах искусственного интеллекта. Эксперты в этой области ориентируются в цифровых продуктах, умеют их использовать и извлекать выгоду для компании. Почему? Потому что основная задача логиста – экономия. Он критически оценивает существующие процессы и предлагает способы их оптимизации. Ольга Умнова, Product Owner ПГК, и Дмитрий Алимин, руководитель направления в управлении развития цифровых продуктов компании, рассказывают, как оператор использует математический подход в бизнесе.
Как подготовиться к собеседованию в Samsung Advanced Computing Lab
Я работаю проектировщиком аппаратного блока графического процессора в телефонах Samsung, в рамках совместного проекта с AMD. Сейчас наш менеджмент расширяет команду и поощряет инженеров распостранять информацию о новых позициях среди своих знакомых. Я решил написать это пост для более широкой аудитории, так как множество людей, способных пройти интервью на RTL или DV позицию - больше, чем множество моих знакомых. Если вы сможете прислать мне ответ на задачку в моем посте вместе с вашим резюме, я перешлю его нанимающему менеджеру и рекрутеру нашей группы (в комментах прошу ответ не писать). Если резюме им понравится, вам нужно будет пройти стандартное собеседование на несколько часов, с несколькими инженерами, у каждого из которых свой набор задачек.
Также я покажу материалы, по которым можно готовиться к собеседованию, особенно если вы студент или у вас ограниченный опыт в микроэлектронной промышлености.
Что делать, если твой временной ряд растёт вширь
Привет, Хабр! Есть мнение, что прогнозирование временных рядов - сложная задача. Но не будем расстраиваться, ведь есть и плюсы - существует ещё большое количество задач, когда рядов сразу несколько, и такие задачи ещё сложнее! Когда начинаем сравнивать, понимаем, что прогнозировать одномерные временные ряды не так уж и сложно. А вот что делать с ситуацией, когда временной ряд обрастает параллельно идущими с ним последовательностями других параметров (многомерный ряд), какие методы и алгоритмы использовать, и что делать, если задача прогнозировать такие ряды есть, а опыта не очень много (спойлер - используйте AutoML, а пока он работает восполните пробел прочитав пару статей по теме), разбираем под катом.
Что такое временной ряд
Если начинать совсем издалека, то это последовательность значений, упорядоченная по времени. Во временных рядах есть закономерность: текущие значения ряда связаны с предыдущими. Если такого свойства у ряда нет, то поздравляем (или не поздравляем), вы имеете дело с процессом, который прогнозировать классическими (и не очень) моделями не выйдет, в таком случае стоит смотреть в сторону Марковских процессов.
Простенькая картинка ниже иллюстрирует описанное выше свойство, - этого бэкграунда для продолжения чтения поста достаточно (Рисунок 1).
Вклад авторов
-
alizar 2691.5 -
ZlodeiBaal 1426.0 -
agorkov 1345.0 -
Fil 1280.0 -
Leono 1086.0 -
YUVladimir 1037.0 -
valemak 1014.0 -
mephistopheies 996.0 -
haqreu 958.0 -
Zalina 922.0