Алгоритмы *

Представьте себе набор данных, состоящий из некоторого количества наблюдений. У каждого наблюдения имеется N признаков. Если преобразовать все эти признаки в их числовое представление, то можно будет сказать, что каждое из наблюдений — это точка в N‑мерном пространстве.

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

Это — реальное явление. По мере роста N, при условии, что всё остальное не меняется, объём части N‑мерного пространства, содержащий наблюдения, тоже, в некотором смысле, увеличивается (или, как минимум, увеличивается количество степеней свободы). Увеличиваются и евклидовы расстояния между наблюдениями. Группа точек становится всё более разреженной структурой. Это — геометрическая база для такого понятия, как «проклятие размерности». Подобные изменения в данных влияют на поведение моделей и на приёмы работы, применяемые к наборам данных.

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

После месяца напряженной работы мы выпустили новую версию Savant (0.2.4), с новыми функциями и примерами использования.

Savant — это фреймворк компьютерного зрения с открытым исходным кодом для создания приложений компьютерного зрения на базе нейронных сетей, работающий на стеке Nvidia. Он упрощает разработку динамических, отказоустойчивых конвейеров видео‑аналитики, использующих рекомендованные Nvidia инструменты для центров обработки данных и граничных ускорителей.

Savant построен на базе DeepStream и предоставляет высокоуровневый уровень абстракции для быстрой разработки конвейеров компьютерного зрения на базе Nvidia DeepStream.

ПЛИС-культ привет, хабрунити!

Задумывались ли вы когда-нибудь над тем, что может быть общего у банковской карточки, IMEI телефона и вагона РЖД? В этой статье вы найдете ответ на этот вопрос и увидите его реализацию для ПЛИС.

Создаем олимпиадную задачу от начала и до конца: использование системы Polygon на реальном примере. Подходит как для новичков, так и для тех, кто уже имеет опыт, но все ещё пишет тесты сам и не знаком с FreeMarker.

В данной статье исследуется метод оценки параметров систем дифференциальных уравнений на основе неточных наблюдений. Автор проводит численный эксперимент с использованием языка программирования Scala для оценки реальных результатов и более подробного изучения предложенного алгоритма. Алгоритм оценки параметров включает подготовку данных, генерацию неточных наблюдений, использование численных методов для решения системы уравнений и оценку приближенных значений параметров. Эксперимент проводятся на системе Лоренца, и результаты оценки параметров сравниваются с реальными значениями. Заключение статьи делает выводы о применимости метода и его эффективности при оценке параметров систем дифференциальных уравнений на основе неточных наблюдений.

Всем привет! Меня зовут Алексей Староверов, работаю научным сотрудником в AIRI и в составе нашей команды (вместе с Кириллом Муравьевым, Татьяной Земсковой, Дмитрием Юдиным и Александром Пановым) мы выиграли соревнование Habitat Challenge, которое проводилось в рамках крупнейшей конференции по компьютерному зрению CVPR 2023. Мы смогли эффективнее других команд научить робота навигироваться до целевых объектов в новых помещениях с использованием только RGB-D камеры, датчика GPS и компаса. Сейчас это является очень важной задачей при создании роботов-помощников, выполняющих задачи по инструкциям на естественном языке. В этой заметке я расскажу, как это у нас получилось.

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

С тех пор у меня накопилось более 400 решённых задач на LeetCode. Теперь я уверена, что такие платформы как LeetCode, HackerRank или CodeWars, при правильном подходе, способны поднять профессиональные навыки любого разработчика на новый уровень.

В данной статье рассматривается создание расширяемого алгоритма строкового калькулятора, который позволяет пользователю самостоятельно определять операции и константы, с которыми работает калькулятор. Основная цель статьи - предоставить описание процесса разработки и реализации такого алгоритма, а также продемонстрировать его гибкость и возможности для настройки под индивидуальные нужды пользователей.

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

В данной статье рассмотрим способ процедурной генерации подземелий, с помощью рекурсивную функцию на Godot 4.1.

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

Привет! Меня зовут Глеб Рыжаков, я научный сотрудник Сколтеха. Я занимаюсь математикой, а точнее, линейной алгеброй, и её приложениями к практическим задачам. Сегодня я расскажу вам о нашем исследовании, которое может помочь справиться с проблемой проклятия размерности, которая возникает во множестве статистических задач, включая машинное обучение.

Понятие «проклятие размерности» появилось в середине прошлого века в пионерской работе Ричарда Беллмана, посвященной методам решения сложных задач путём разбиения их на более простые подзадачи. Сегодня оно понимается в более общем смысле, а именно как экспоненциальный — O(n^d) — рост количества необходимых данных и, как следствие, количества памяти, необходимой для их хранения, с ростом размерности пространства d. Когда задачу можно свести к работе с многомерными массивами в общем случае комплексных чисел, удобно говорить о d-мерных тензорах и использовать достижения мультилинейной алгебры. Хорошая новость заключается в том, что там существует такая процедура, как тензорное разложение, которое в ряде случаев может помочь преодолеть проклятие размерности.

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

Меня зовут Андрей Цыган - я не программист, я смотрю на технологии ИИ с точки зрения человека, кто знает что хочет, но не имеет навыков это сделать через код.

Я протестировал новый плагин Code Interpreter на реальных задачах в бизнесе и остался приятно удивлён.

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

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

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

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

Есть вот такая, вроде бы, простая задача на литкоде: Дано три числа total - сколько у вас есть денег, cost1, cost2 - цены двух товаров. Надо подсчитать, сколько всего существует различных способов купить сколько-то этих двух товаров, не выходя из бюджета (значение имеет только общее количество покупок). Иными словами, сколько существет целых неотрицательных пар (x, y), таких что x*cost1+y*cost2 <= total . Например, имея товары ценами {5, 10} и 20 денег на руках, есть 9 способов потратить деньги: 0, 5, 5+5, 5+5+5, 5+5+5+5, 10, 10+5, 10+5+5, 10+10.

Она там даже помечена как medium и вообще в одну строчку решается, но это если допускать безумно медленное решение за O(total / max(cost1, cost2)) , т.е линейное от входных чисел. А сможете ли вы решить ее сильно быстрее - за O(log(max(cost1, cost2))) ? В этом случае задачка становится вполне себе hard и требует много математики и аккуратности. Если интересно решение - добро пожаловать под кат. Буду рад любым альтернативным решениям. Может кто-то сможет додуматься до похожего решения проще.

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