Алгоритмы *

Привет! Меня зовут Константин Яковлев, я научный работник и вот уже более 15 лет я занимаюсь методами планирования траектории. Когда речь идет о том, чтобы построить траекторию для одного агента, то задачу зачастую сводят к поиску пути на графе, а для этого в свою очередь обычно используют алгоритм A* или какие‑то из его многочисленных модификаций. Если же агентов много, они перемещаются в рабочем пространстве одновременно, то задача (внезапно) становится несколько более сложной и применить напрямую A* не получится. Вернее получится, но лишь для небольшого числа агентов (проклятье размерности, куда деваться). Тем не менее для централизованного случая, т. е. для случая, когда есть один (мощный) вычислитель, с которым связаны все агенты и который всё про всех знает, решить задачу много‑агентного планирования можно достаточно эффективно. Можно даже находить оптимальные решения для умеренного количества агентов за относительное приемлемое время (например, порядка 1 секунды на современном десктопном PC для 30–50 агентов).

Если же говорить о децентрализованном случае, т. е. о том случае, когда агентам необходимо действовать индивидуально (например, нет устойчивой связи с центральным контроллером), опираясь лишь на собственные (локальные) наблюдения и опыт, то с хорошими решениями задачи становится гораздо сложнее. Когда я говорю «хорошие решения», я имею в виду прежде всего такие алгоритмы, которые бы давали стройные теоретические гарантии в общем случае. Хотя бы гарантии того, что каждый агент дойдёт (за конечное время) до своей цели. Тем не менее, задача интересная и специалисты из индустрии и академии её пытаются решать.

В этом посте я расскажу о наших свежих наработках в этой области, а именно о гибридном методе, которые сочетает в себе принципы классического эвристического поиска (A*) и обучения с подкреплением (PPO). Метод получился неплохим, превосходящим многие современные аналоги по результатам экспериментов, а соответствующая статья была принята на The 38th AAAI Conference on Artificial Intelligence (пока доступен только препринт). Это одна из топовых академических конференций по искусственному интеллекту, которая в этом (2024) году проходила в Канаде (спойлер: я сам визу получить не успел, но моим коллегам и со‑авторам, кто имел ранее выданные Канадские визы, удалось принять личное участие и достойно представить нашу науку на мировом уровне).

Адаптация алгоритма Дейкстры для расчёта кратчайших путей в IP-сетях.

Для сетевиков, программистов и интересующихся.

Линейный дискриминантный анализ (Linear Discriminant Analysis или LDA) — алгоритм классификации и понижения размерности, позволяющий производить разделение классов наилучшим образом. Основная идея LDA заключается в предположении о многомерном нормальном распределении признаков внутри классов и поиске их линейного преобразования, которое максимизирует межклассовую дисперсию и минимизирует внутриклассовую. Другими словами, объекты разных классов должны иметь нормальное распределение и располагаться как можно дальше друг от друга, а одного класса — как можно ближе.

Наивный байесовский классификатор (Naive Bayes classifier) — вероятностный классификатор на основе формулы Байеса со строгим (наивным) предположением о независимости признаков между собой при заданном классе, что сильно упрощает задачу классификации из-за оценки одномерных вероятностных плотностей вместо одной многомерной.

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

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

Генерация столбцов - подход к решению задач смешанного линейного программирования (MIP) с большим кол-вом переменных или столбцов.

В статье представил теоретическую предпосылку, схему алгоритма и python реализацию подхода. В практической части рассмотрел решение двух задач: задача планирования расписания и задача раскроя.

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

Российская компания «Криптонит» представила на «РусКрипто’2024» криптографический механизм «Кодиеум». Он устойчив ко всем известным атакам и останется стойким даже в случае появления мощного квантового компьютера.

К-ближайших соседей (K-Nearest Neighbors или просто KNN) — алгоритм классификации и регрессии, основанный на гипотезе компактности, которая предполагает, что расположенные близко друг к другу объекты в пространстве признаков имеют схожие значения целевой переменной или принадлежат к одному классу.

Дерево решений CART (Classification and Regressoin Tree) — алгоритм классификации и регрессии, основанный на бинарном дереве и являющийся фундаментальным компонентом случайного леса и бустингов, которые входят в число самых мощных алгоритмов машинного обучения на сегодняшний день. Деревья также могут быть не бинарными в зависимости от реализации. К другим популярным реализациям решающего дерева относятся следующие: ID3, C4.5, C5.0.

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

Привет! Меня зовут Василий Землянов, я занимаюсь разработкой ML-инфраструктуры. Несколько лет я проработал в команде, которая делает споттер — специальную маленькую нейросетевую модельку, которая живёт в умных колонках Яндекса и ждёт от пользователя слова «Алиса». Одной из моих задач в этой команде была квантизация моделей. На пользовательских устройствах мало ресурсов, и мы решили, что за счёт квантизации сможем их сэкономить — так в итоге и вышло.

Потом я перешёл в команду YandexGPT. Вместо маленьких моделей я стал работать с очень крупными. Мне стало интересно, как устроена квантизация больших языковых моделей (LLM). Ещё меня очень впечатляли истории, где люди берут гигантские нейросети, квантизируют в 4 бита и умудряются запускать их на ноутбуках. Я решил разобраться, как это делается, и собрал материал на доклад для коллег и друзей. А потом пришла мысль поделиться знаниями с более широкой аудиторией, оформив их в статью. Так я и оказался на Хабре :)

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

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

Мир, в котором мы с вами живём и который непосредственно ощущаем, является объёмным: расположение любой точки в нём можно описать тремя координатами, и этот факт элементарно зашит в нашу природу. Чем больше “понимания” система искусственного интеллекта будет иметь относительно истинной сущности вещей, включая их расположение, форму и объем, тем легче она будет справляться с задачами, которые до сих пор мог выполнять только человек. 

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

Продолжаем публикацию лекций по предмету "Управление в технических системах". Кафедра "Ядерные энергетические установки" МГТУ им. Н.Э. Баумана. Автор: Олег Степанович Козлов.

1. Введение в теорию автоматического управления.2. Математическое описание систем автоматического управления 2.1 — 2.3, 2.3 — 2.8, 2.9 — 2.13. 

3. Частотные характеристики звеньев и систем автоматического управления регулирования. 3.1. Амплитудно-фазовая частотная характеристика: годограф, АФЧХ, ЛАХ, ФЧХ. 3.2. Типовые звенья систем автоматического управления регулирования. Классификация типовых звеньев. Простейшие типовые звенья. 3.3. Апериодическое звено 1–го порядка инерционное звено. На примере входной камеры ядерного реактора. 3.4. Апериодическое звено 2-го порядка. 3.5. Колебательное звено. 3.6. Инерционно-дифференцирующее звено. 3.7. Форсирующее звено.  3.8. Инерционно-интегрирующее звено (интегрирующее звено с замедлением). 3.9. Изодромное звено (изодром). 3.10 Минимально-фазовые и не минимально-фазовые звенья. 3.11 Математическая модель кинетики нейтронов в «точечном» реакторе «нулевой» мощности. 

4. Структурные преобразования систем автоматического регулирования.

5. Передаточные функции и уравнения динамики замкнутых систем автоматического регулирования (САР).

6. Устойчивость систем автоматического регулирования. 6.1 Понятие об устойчивости САР. Теорема Ляпунова. 6.2 Необходимые условия устойчивости линейных и линеаризованных САР. 6.3 Алгебраический критерий устойчивости Гурвица. 6.4 Частотный критерий устойчивости Михайлова. 6.5 Критерий Найквиста.

Следующим мощным алгоритмом машинного обучения является AdaBoost (adaptive boosting), в основе которого лежит концепция бустинга, когда слабые базовые модели последовательно объединяются в одну сильную, исправляя ошибки предшественников.

В AdaBoost в качестве базовой модели используется пень решений (могут использоваться другие модели) — дерево с небольшой глубиной, которому присваивается вектор весов размера N, каждое значение которого соответствует определённому значению y_train и изначально равно 1 / N, где N — количество образцов в обучающей выборке. Каждый следующий пень обучается с учётом весов, рассчитанных на основе ошибок предыдущего прогноза. Также для каждого обученного пня отдельно рассчитывается вес, используемый для оценки важности итоговых прогнозов.

На сегодняшний день градиентный бустинг (gradient boosting machine) является одним из основных production-решений при работе с табличными, неоднородными данными, поскольку обладает высокой производительностью и точностью, а если быть точнее, то его модификации, речь о которых пойдёт чуть позже.

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

Всем привет, Меня зовут Богдан Печёнкин. Я соавтор Симулятора ML на Karpov.Courses и фаундер AI Dating Copilot стартапа Adam.

Только что Мне на глаза попалась одна новость от компании Extropic с новостями из мира квантовых компьютеров, которую Мне захотелось перевести и прокомментировать.

Extropic - лаборатория, разрабатывающая квантовые вычисления и алгоритмы искусственного интеллекта на их основе.

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

Привет, Хабр! Меня зовут Сергей Прилуцкий, я руковожу отделом исследований компании MixBytes. Мы занимаемся аудитами безопасности смарт-контрактов и исследованиями в области блокчейн-технологий. В числе прочего занимаемся и направлением zero-knowledge. Эта статья подготовлена по мотивам моего доклада на Highload про zkSNARKs. Это одна из самых горячих тем в современной криптографии. Они используются для обеспечения приватности и масштабируемости в децентрализованных системах. Поговорим, как масштабировать криптографические системы, какие проблемы существуют у снарк-алгоритмов и зачем они нужны.

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

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