Рубрика «Алгоритмы» - 78

Машинное зрение vs интуиция человека: алгоритмы нарушения работы программ распознавания объектов - 1

Логика машин безупречна, они не совершают ошибок, если их алгоритм работает исправно и заданные параметры соответствуют необходимым стандартам. Попросите машину выбрать маршрут от точки А в точку Б, и она построит самый оптимальный, учитывая расстояние, расход топлива, наличие заправок и т.д. Это чистый расчет. Машина не скажет: «Поедем по этой дороге, я чувствую этот маршрут лучше». Может машины и лучше нас в скорости расчетов, но интуиция по-прежнему остается одним из наших козырей. Человечество потратило десятки лет на то, чтобы создать машину, подобную мозгу человека. Но так ли много между ними общего? Сегодня мы рассмотрим исследование, в котором ученые, усомнившись в непревзойденности машинного «зрения» на базе свёрточных нейронных сетей, провели эксперимент по одурачиванию системы распознавания объектов посредством алгоритма, задачей которого было создание «подставных» изображений. Насколько удачной была диверсионная деятельность алгоритма, справлялись ли люди с распознаванием лучше машины и что это исследование привнесет в будущее данной технологии? Ответы найдем в докладе ученых. Поехали.Читать полностью »

Мат слоном и конём. Треугольники Делетана - 1

Для дилетантов в теме матования слоном и конём всегда к услугам TWIX.

Суровые же профи, которым интересен хардкор, действуют по рецепту Делетана.
Читать полностью »

TL;DR: Четыре года назад я покинул Google с идеей нового инструмента для мониторинга серверов. Идея состояла в том, чтобы объединить в одну службу обычно изолированные функции сбора и анализа логов, сбора метрик, оповещений и панели мониторинга. Один из принципов — сервис должен быть действительно быстрым, обеспечивая девопсам лёгкую, интерактивную, приятную работу. Это требует обработки наборов данных по несколько гигабайт за доли секунды, не выходя за рамки бюджета. Существующие инструменты для работы с логами часто медленные и неуклюжие, поэтому мы столкнулись с хорошей задачей: грамотно разработать инструмент, чтобы дать пользователям новые ощущения от работы.

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

SNA Hackathon 2019: усложняем архитектуру — упрощаем признаки - 1

В этой статье я расскажу про свое решение текстовой части задачи SNA Hackathon 2019. Какие-то из предложенных идей будут полезны участникам очной части хакатона, которая пройдет в московском офисе Mail.ru Group с 30 марта по 1 апреля. Кроме того, этот рассказ может быть интересен и читателям, решающим практические задачи машинного обучения. Так как я не могу претендовать на призы (я работаю в Одноклассниках), я постарался предложить наиболее простое, но при этом эффективное и интересное решение.

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

13 апреля в Санкт-Петербурге и 20 апреля в Москве будет проведен семинар CLRium #5, целиком и полностью посвященный подсистемам ядра CoreCLR и .NET Framework.

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

10 докладов. Исключительно про ядро. 6 из них — только про подсистему управления памятью.

Не надо думать о памяти, говорили они… Семинар CLRium #5: Garbage Collector - 1
Читать полностью »

Доброго времени суток!

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

+БОНУС: как включать классы друг в друга в C++

Привет! Эта статья — прямое продолжение статьи Искусство парсинга или DOM собственными руками, где мы разобрали HTML-документ и построили на его основе абстрактное синтаксическое дерево (AST) с доступом к любому элементу через индексацию при помощи лишь стандартной библиотеки C++, проще говоря, научились самостоятельно парсить XML-подобные штуки. Напомню, что процесс парсинга, или синтаксического анализа/разбора состоит из двух этапов: лексического разбора (разбора текста на токены) и построения AST. Если первый мы рассмотрели очень подробно, с примерами и исходниками, то описание второго похоже на пустую куколку бабочки, у которой есть только оболочка, а прекрасное содержимое автор извлёк перед публикацией. На то была причина, для HTML построить дерево действительно просто, нужно всего 4 класса: пустой тег, блок, текстовый узел и корень документа, наследуемый от блока. Сегодня мы оставим такую простоту позади и построим дерево, где свойства элементов, и пустых, и блочных, будут содержаться не в атрибутах тегов, а непосредственно в классах, а для этого классов придётся создать много. Действительно много. Строить будем не из простых известных языков разметки, а создадим свой, с правилами, показанными на изображении под катом. Плюс в конце ещё переведём, или, говоря правильнее, транслитируем документ с предыдущей статьёй, размеченной нашим языком, в HTML, а в качестве бонуса я отвечу начинающим программистам C++ на тривиальный, но труднонаходимый вопрос: как включать классы «друг в друга»?
Читать полностью »

Новый алгоритм в 200 раз ускоряет автоматическое проектирование нейросетей - 1

ProxylessNAS напрямую оптимизирует архитектуры нейронных сетей для конкретной задачи и оборудования, что позволяет значительно увеличить производительность по сравнению с предыдущими прокси-подходами. На наборе данных ImageNet нейросеть проектируется за 200 GPU-часов (в 200−378 раз быстрее аналогов), а автоматически спроектированная модель CNN для мобильных устройств достигает того же уровня точности, что и MobileNetV2 1.4, работая в 1,8 раза быстрее.

Исследователи из Массачусетского технологического института разработали эффективный алгоритм для автоматического дизайна высокопроизводительных нейросетей для конкретного аппаратного обеспечения, пишет издание MIT News.

Алгоритмы для автоматического проектирования систем машинного обучения — новая область исследований в сфере ИИ. Такая техника называется «поиск нейронной архитектуры (neural architecture search, NAS) и считается трудной вычислительной задачей.
Читать полностью »

Примечание. Сокращенный перевод, скорее пересказ своими словами.
UPD: как отметили в комментариях, примеры не идеальны. Автор не ищет лучшее решение задачи, его цель объяснить сложность алгоритмов «на пальцах».

Big O нотация нужна для описания сложности алгоритмов. Для этого используется понятие времени. Тема для многих пугающая, программисты избегающие разговоров о «времени порядка N» обычное дело.

Если вы способны оценить код в терминах Big O, скорее всего вас считают «умным парнем». И скорее всего вы пройдете ваше следующее собеседование. Вас не остановит вопрос можно ли уменьшить сложность какого-нибудь куска кода до n log n против n^2.

Структуры данных

Выбор структуры данных зависит от конкретной задачи: от вида данных и алгоритма их обработки. Разнообразные структуры данных (в .NET или Java или Elixir) создавались под определенные типы алгоритмов.

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

Здесь мы будем использовать только массивы чисел (прямо как на собеседовании). Примеры на JavaScript.
Читать полностью »

Первый программируемый компьютер на ДНК - 1
Экспериментальный протокол и реализация алгоритма сортировки на программируемом ДНК-компьютере

Учёные давно ведут эксперименты с хранением информации в ДНК и с обработкой этой информации. Например, учёные из Вашингтонского университета и Microsoft недавно построили «первый в мире DNA-винчестер» (фото). Эта конструкция способна впервые обеспечить запись и считывание информации в ДНК-хранилище без участия человека. Весьма значительное достижение, если учесть, что в ДНК можно записывать информацию с плотностью 2,2 петабайта на грамм. ДНК — компактный контейнер с плотностью записи в тысячи раз больше, чем у существующих носителей.

Однако у всех существующих ДНК-систем есть проблема: всё это уникальные проприетарные разработки, у которых напрочь отсутствует какая бы ни было гибкость. Если сравнить с кремниевой техникой, то каждая группа исследователей с нуля разрабатывает новую архитектуру компьютера, для которого нужно писать новый софт. Но ситуация может измениться благодаря первому программируемому ДНК-компьютеру, разработанному в Калифорнийском университете в Дейвисе (UC Davis), Калифорнийского технологического института и Университета Мейнут.
Читать полностью »


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js