Алгоритмы *

Всем привет! Этим летом мы с командой участвовали в летней школе 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. Его можно задействовать в разных аспектах, включая анализ данных, обнаружение мошенничества, прогнозирование рисков и оптимизацию процессов. Алгоритмы машинного обучения могут обрабатывать и анализировать огромные объёмы данных, выявлять скрытые зависимости и аномалии, что помогает аудиторам принимать более обоснованные и точные решения. Далее мы рассмотрим различные типы задач машинного обучения, которые могут быть применены в аудите.

Привет, Хабр! Всем давно известно, что мы в Smart Engines занимаемся компьютерной томографией (КТ) и развиваем Smart Tomo Engine (STE) - программу для томографической реконструкции и визуализации.

Результирующее томографическое изображение в КТ получается с использованием вычислительно затратных алгоритмов реконструкции, которые применяются к набору зарегистрированных двумерных рентгеновских изображений. Однако сегодня мы хотим рассказать не об алгоритмах КТ, а о том как можно попытаться обойтись без них, но все же увидеть объемное реконструированное изображение внутренней структуры изучаемого объекта. В статье мы расскажем, как с помощью правильно выбранных двумерных проекций построить в голове человека трехмерное изображение. А исходить мы будем из физических принципов восприятия человеком объемных изображений. Картинки прилагаются! По ним можно не только убедиться, что теория работает, но и вспомнить детство со стереопарами и анаглифом. Запасайтесь попкорном и 3D очками. Приятного прочтения.

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

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

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