Алгоритмы *

Здравствуйте, читатели Хабра! Решил активнее вкатываться в DS (хотя уже больше года в "теме" и даже нет ни одной публикации, ужас) и написать первую статью на Хабре.

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

Можно ли напечатать трассировщик на визитной карточке?
Как реализовать преломление и отражение света?

Узнаем в этой статье ?

Привет! Меня зовут Константин Яковлев, я научный работник и вот уже более 15 лет я занимаюсь методами планирования траектории. Часто эта задача сводится к поиску пути на графе, для чего обычно используется алгоритм эвристического поиска A*. Этот алгоритм был предложен в 60-х годах XX века и с тех пор используется повсеместно. Скорее всего, юнит вашей любимой RTS бежит по карте с помощью той или иной вариации A*. Точно так же, под капотом беспилотного авто вы, наверняка, найдёте A*, хотя там, конечно, не только он.

A* — это хороший алгоритм, но его вычислительная эффективность сильно зависит от эвристической функции, которую должен задать разработчик. Основная проблема стандартных эвристик заключается в том, что они не учитывают расположение препятствий на карте и ведут поиск буквально напролом, тратя на это ресурсы (итерации поиска). Почему бы нам не воспользоваться современными нейросетями для решения этой проблемы, а именно попросить нейросеть посмотреть на карту и подсказать поиску как лучше обходить препятствия, чтобы быстрее (за меньшее число итераций) найти нужный путь?

Этот текст посвящен как самому алгоритму A*, так и попыткам повысить его эффективность с помощью методов искусственного интеллекта. Заодно я расскажу о том, какие новшества в этом направлении придумали мы с коллегами: научная статья на эту тему опубликована в сборнике конференции AAAI 2023.

Привет, Хабр! Как ты уже знаешь, в Smart Engines мы разрабатываем томографическое программное обеспечение. Компьютерная томография (КТ) – это неинвазивный метод исследования внутренних особенностей предмета. На сегодняшний день КТ является одним из основных томографических методов исследования внутренних органов человека, также КТ это перспективный инструмент для контроля качества в промышленности.

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

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

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

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

В этой статье мы добавим в наш рейтрейсер поддержку отражения и преломления света. Приятного чтения!

Предыдущая глава

Другим преимуществом трассировки лучей является то, что, расширяя идею распространения лучей, мы можем очень легко имитировать такие эффекты, как отражение и преломление, которые удобны при моделировании стеклянных материалов или зеркальных поверхностей. В статье 1979 года, озаглавленной "Улучшенная модель освещения для затененного дисплея", Тернер Уиттед был первым, кто описал, как расширить алгоритм трассировки лучей Аппеля для более продвинутого рендеринга. Идея Уиттеда расширила модель испускания лучей Аппелем, включив в нее расчеты отражения и преломления.

Предыдущая глава

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

for (int j = 0; j < imageHeight; ++j) {
for (int i = 0; i < imageWidth; ++i) {
// вычисляем направление основного луча
Ray primRay;

...

Какую рекламу показать пользователю, красную или синюю?

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

Но как узнать, какой из баннеров имеет наибольший уровень кликабельности?

Чаще всего для ответа на этот вопрос используется A/B-тестирование. Группа пользователей разделяется пополам, и первой части показывают один баннер, а второй — другой. После этого можно вычислить уровень кликабельности и выбрать лучший из вариантов.

Предположим, что в конце A/B-тестирования у вас получились следующие результаты:

Сегодня мы хотим поделиться новостью для всех, кто занимается анализом данных в области лингвистики и машинного обучения. Яндекс выкладывает в открытый доступ крупнейший русскоязычный датасет отзывов об организациях, опубликованных на Яндекс Картах. Это 500 тысяч отзывов со всей России с января по июль 2023 года.

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

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

Феномен из прошлой статьи, описанный Ибн аль-Хайсамом, объясняет, почему мы видим объекты. На основе его наблюдений можно сделать два интересных замечания: во-первых, без света мы ничего не можем видеть, а во-вторых, без объектов в нашем окружении мы не можем видеть свет. Если бы мы путешествовали в межгалактическом пространстве, именно это обычно и происходило бы. Если вокруг нас нет материи, мы не можем видеть ничего, кроме темноты, даже несмотря на то, что фотоны потенциально движутся через это пространство (конечно, если бы фотоны были, они должны были бы откуда-то взяться. И если бы вы посмотрели на них прямо, если бы они попали вам в глаза, вы бы увидели изображение объекта, от которого они отразились или испустились).

Введение в трассировку лучей: простой метод создания 3D-изображений
Часть 1 - как создается изображение?

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

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

Это вторая статья из серии статей про устройство движков поиска по регулярным выражениям от одного из авторов библиотеки регулярных выражений RE2. Статья датируется 2009 годом, но не потеряла своей актуальности. Перевод первой статьи можной прочитать здесь.

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

Так же в статье приведена любопытнейшая историческая справка и особенности реализации POSIX.

Об ошибка, опечатках и неточностях большая просьба сообщать.

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

Об алгебре кортежей (АК) и ее использовании для логико-семантического анализа было рассказано в моей статье в Хабре. В комментариях к статье предлагалось обратить внимание на функцию SELECT в языке SQL, которая соответствует операции Selection (Выборка) в реляционной алгебре. Эта операцию можно рассматривать как один из вариантов математической модели вопроса.

Предлагаемый здесь вариант смысла вопроса заключается в том, что в вопросе заданы некоторые ограничения (область знания, ситуация, значения некоторых атрибутов и т.д.), которые требуется использовать для того, чтобы найти или вычислить значение определенного атрибута или проверить правильность заданных в вопросе соотношений. Эта семантика применима к восполняющим вопросам типа «Что?», «Где?», «Когда?», к уточняющим вопросам типа «Верно ли, что А?» и к ИЛИ-вопросам типа «Что правильно: А или Б?». Назовем такие вопросы ограничительными. Их можно считать вариантами известной в искусственном интеллекте задачи удовлетворения ограничений.

С целью автоматизации процесса подбора гиперпараметров автором данной статьи разработан алгоритм Helena.4.0. Конечной целью является создание автоматической системы построения моделей (auto-ML), которая бы подбирала гиперпараметры за минимальное время.

С помощью алгоритма Helena.4.0 можно подбирать гиперпараметры для моделей градиентного бустинга, нейросетей, и более того – для генетических алгоритмов. Автор считает, что алгоритмы Helena могут заменить в генетических алгоритмах генеративную часть – т.е. уйти от биологических аналогий, заменив псевдобиологическую генерацию признаков путем процедур «скрещивания» и «мутаций» на генерацию с помощью указанных алгоритмов.

Для поиска максимума функции алгоритм Helena.4.0 использует только ее значения, и  не используют первые и последующие производные. Таким образом, этот алгоритм не требуют ни дифференцируемости, ни непрерывности максимизируемой функции.

Сравнение алгоритма Helena.4.0 с наиболее популярными конкурентами (Optuna, HyperOpt, RandomSearch) показывает его высокую конкурентоспособность.

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

Ниже в статье приведено подробное описание алгоритма Helena.4.0 и результаты сравнительных тестов с алгоритмами-конкурентами.

Есть такая занимательная структура данных, описанная в статье Russ Cox — sparse map.

Она используется, например, в недрах компилятора Go. А ещё в некоторых пакетах его стандартной библиотеки.

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

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

Привет, Хабр! На связи Егор Гершевский и Никита Горбачёв, участники профессионального сообщества NTA.

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

Сегодня почти каждая крупная технологическая компания внедряет машинное обучение (ML) в аудит. Вот, например, как оно применяется в Facebook и Amazon. Его можно задействовать в разных аспектах, включая анализ данных, обнаружение мошенничества, прогнозирование рисков и оптимизацию процессов. Алгоритмы машинного обучения могут обрабатывать и анализировать огромные объёмы данных, выявлять скрытые зависимости и аномалии, что помогает аудиторам принимать более обоснованные и точные решения. Далее мы рассмотрим различные типы задач машинного обучения, которые могут быть применены в аудите.