Алгоритмы *

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

Коротко об алгоритме

Основная идеология для алгоритма была составлена в нескольких характеристиках:

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

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

Здравствуйте, дорогие читатели. Сегодня мы публикуем внеочередной перевод — это будет обзорная статья блистательного Ноэля Уэлша о принципах вероятностного программирования. Статья публикуется по заявкам читателей, которые задают нашему блогу все более высокую планку — и это, безусловно, здорово!

Всем привет! В этой статье речь пойдет о реализации быстрого преобразования Фурье в формате с плавающей точкой на ПЛИС. Будут показаны основные особенности разработки ядра от самой первой стадии до готового конфигурируемого IP-ядра. В частности, будет проведено сравнение с готовыми ядрами фирмы Xilinx, показаны преимущества и недостатки тех или иных вариантов реализации. В статье будет рассказано о главной особенности ядра БПФ и ОБПФ — об отсутствии необходимости переводить данные в натуральный порядок после БПФ и ОБПФ для их совместной связки. В этой статье я постараюсь отразить всё тонкости реализации проекта под названием FP23FFTK, приведу реальные примеры использования готового ядра. Проект написан на языке VHDL и заточен под FPGA фирмы Xilinx последних семейств.

От экрана дизайнера к экрану игрока

Карты разрабатывались дизайнером уровней в 2D с помощью редактора Doom Editor (DoomED). LINEDEFS описывали замкнутые секторы (SECTORS в исходном коде), а третье измерение (высота) указывалась посекторно. Первый уровень Doom E1M1 выглядит так:



После завершения работы над картой она нарезается методом двоичного разбиения пространства (Binary Space Partitioning, BSP). LINEDEF рекурсивно выбирались и их плоскости превращались в секущие плоскости. То есть LINEDEF разрезались на сегменты (SEGS) до тех пор, пока не оставались только выпуклые подсектора (SSECTOR в коде).

Интересный факт: И DoomED, и iBSP писались на… Objective-C на рабочих станциях NextStep. Пятнадцать лет спустя тот же язык почти в той же операционной системе выполняет игру на мобильном устройстве! [прим. пер.: в 2010 году Doom вышел на iPhone] Я немного поработал веб-археологом и мне удалось найти исходный код idbsp. На него стоит посмотреть.

Всё началось с того, что жена захотела повесить кормушку для птиц. Идея мне понравилась, но сразу захотелось оптимизировать. Световой день зимой короткий — сидеть днём и смотреть на кормушку времени нет. Значит нужно больше Computer Vision!



Идея была простой: прилетает птичка — вжуууух — она оказывается на телефоне. Осталось придумать как это сделать и реализовать.
В статье:

• Запуск Caffe на Raspberry Pi B+ (давно хотел это сделать)
• Построение системы сбора данных
• Выбор нейронной сети, оптимизация архитектуры, обучение
• Оборачивание, выбор и приделывание интерфейса

Все исходники открыты + описан полный порядок развёртывания получившейся конструкции.

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



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

«Дело было вечером, делать было нечего» — именно так родилась идея сделать вью с возможностью зума, распределяющую юзеров по рангам в зависимости от кол-ва их очков. Так как до этого я не имел опыта в создании собственных вьюшек такого уровня, задача показалась мне интересной и достаточно простой для начинающего… но, *ох*, как же я ошибался.

В статье я расскажу о том, с какими проблемами мне пришлось столкнутся как со стороны Android SDK, так и со стороны задачи (алгоритма кластеризации). Основная задача статьи – не научить делать так называемыми “custom view”, а показать проблемы, которые могут возникнуть при их создании.

Тема будет интересна тем из вас, кто имеет мало (или не имеет вовсе) опыта в создании чего-то подобного, а также тем, кто хочет словить лулзов с автора в сто первый раз уверовать в «гибкость» Android SDK.

Измерение пропускной способности узких мест по времени двойного прохода пакета

По всем параметрам, сегодняшний интернет не может перемещать данные так быстро, как должен. Большинство пользователей сотовой связи в мире испытывают задержки от нескольких секунд до нескольких минут: публичные точки WiFi в аэропортах и на конференциях ещё хуже. Физикам и климатологам нужно обмениваться петабайтами данных с коллегами по всему миру, но они сталкиваются с тем, что их тщательно продуманная многогигабитная инфраструктура часто выдаёт всего несколько мегабит в секунду на трансконтинентальных линиях. [6]

Эти проблемы возникли из-за выбора архитектуры, который был сделан при создании системы регулирования заторов TCP в 80-е годы — тогда потерю пакетов решили интерпретировать как «затор». [13] Эквивалентность этих понятий была справедливой для того времени, но только из-за ограничений технологии, а не по определению. Когда NIC (контроллеры сетевых интерфейсов) модернизировали с мегабитных до гигабитных скоростей, а микросхемы памяти — с килобайт до гигабайт, до связь между потерей пакетов и заторами стала менее очевидной.

В современном TCP регулирование заторов по потере пакетов — даже в наиболее совершенной технологии такого рода CUBIC [11] — основная причина этих проблем. Если буферы узких мест слишком большие, то система регулирования заторов по потере пакетов держит их полными, вызывая излишнюю сетевую буферизацию. Если буферы слишком маленькие, то система регулирования заторов по потере пакетов неверно интерпретирует потерю пакета как сигнал затора, что ведёт к снижению пропускной способности. Решение этих проблем требует альтернативы регулированию заторов по потере пакетов. Для нахождения этой альтернативы следует разобраться, где и как возникают заторы.

Наталия Ефремова погружает публику в специфику практического использования нейросетей. Это — расшифровка доклада Highload++.

Добрый день, меня зовут Наталия Ефремова, и я research scientist в компании NtechLab. Сегодня я буду рассказывать про виды нейронных сетей и их применение.

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

Первая часть моего доклада будет направлена тем, кто незнаком с нейронными сетями. Я занимаюсь непосредственно deep learning. В этой области я работаю более 10 лет. Хотя она появилась чуть меньше, чем десятилетие назад, раньше были некие зачатки нейронных сетей, которые были похожи на систему deep learning.

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

Введение

Давно хотел написать про мифы о CAP теореме, но как-то все не доходили руки. Однако, почитав очередной опус, схватился за голову и решил разложить все по полочкам, чтобы в мозгах возникла стройная картина.

Событие, когда какая-то статья вызывает бурю эмоций, — крайне редкое. Первый раз такое возникло, когда я прочитал про chained replication. Меня пытались убедить, что это мощный подход и что это лучшее, что могло произойти с консистентной репликацией. Я сейчас не буду приводить доводы, почему это плохо работает, а просто приведу говорящую цитату из статьи Chain Replication metadata management:

Split brain management is a thorny problem. The method presented here is one based on pragmatics. If it doesn’t work, there isn’t a serious worry, because Machi’s first serious use case all require only AP Mode. If we end up falling back to “use Riak Ensemble” or “use ZooKeeper”, then perhaps that’s fine enough.

В моем вольном пересказе это означает примерно следующее: "У нас тут есть некий алгоритм. Мы не знаем, будет ли он работать правильно или нет. Да нам это и не важно". Хотя бы честно, сэкономило кучу времени, спасибо авторам.

И тут, значит, попадается на глаза статья: Spanner, TrueTime & The CAP Theorem. Её мы разберем по полочкам ближе к концу, вооружившись понятиями и знаниями. А перед этим разберем самые распространенные мифы, связанные с CAP теоремой.

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

Здравствуйте, коллеги! Это блог открытой русскоговорящей дата саентологической ложи. Нас уже легион, точнее 2500+ человек в слаке. За полтора года мы нагенерили 800к+ сообщений (ради этого слак выделил нам корпоративный аккаунт). Наши люди есть везде и, может, даже в вашей организации. Если вы интересуетесь машинным обучением, но по каким-то причинам не знаете про Open Data Science, то возможно вы в курсе мероприятий, которые организовывает сообщество. Самым масштабным из них является DataFest, который проходил недавно в офисе Mail.Ru Group, за два дня его посетило 1700 человек. Мы растем, наши ложи открываются в городах России, а также в Нью-Йорке, Дубае и даже во Львове, да, мы не воюем, а иногда даже и употребляем горячительные напитки вместе. И да, мы некоммерческая организация, наша цель — просвещение. Мы делаем все ради искусства. (пс: на фотографии вы можете наблюдать заседание ложи в одном из тайных храмов в Москве).

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

Часть первая — Affinity Propagation
Часть вторая — DBSCAN
Часть третья — кластеризация временных рядов
Часть четвёртая — Self-Organizing Maps (SOM)
Часть пятая — Growing Neural Gas (GNG)

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

Когда я изучал обработку аудиосигналов, мой мозг начал проводить аналогии с процедурным генерированием карт. В статье излагаются принципы, связывающие обработку сигналов с генерированием карт. Не думаю, что открыл что-то новое, но некоторые выводы были для меня в новинку, поэтому я решил записать их и поделиться с читателями. Я рассматриваю только простые темы (частоту, амплитуду, цвета шума, использование шума) и не затрагиваю другие темы (дискретные и непрерывные функции, фильтры FIR/IIR, быстрое преобразование Фурье, комплексные числа). Математика статьи в основном связана с синусоидами.

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

Привет, Хабр! Под катом пойдёт речь о реализации свёрточной нейронной сети архитектуры InceptionV3 с использованием фреймворка Keras. Статью я решил написать после ознакомления с туториалом "Построение мощных моделей классификации с использованием небольшого количества данных". С одобрения автора туториала я немного изменил содержание своей статьи. В отличие от предложенной автором нейронной сети VGG16, мы будем обучать гугловскую глубокую нейронную сеть Inception V3, которая уже предустановлена в Keras.

Вы научитесь:

1. Импортировать нейронную сеть Inception V3 из библиотеки Keras;
2. Настраивать сеть: загружать веса, изменять верхнюю часть модели (fc-layers), таким образом, приспосабливая модель под бинарную классификацию;
3. Проводить тонкую настройку нижнего свёрточного слоя нейронной сети;
4. Применять аугментацию данных при помощи ImageDataGenerator;
5. Обучать сеть по частям для экономии ресурсов и времени;
6. Оценивать работу модели.

При написании статьи я ставил перед собой задачу представить максимально практичный материал, который раскроет некоторые интересные возможности фреймворка Keras.

Привет, Хаброжители! Мы решили опубликовать отрывок из книги «Алгоритмы: разработка и применение. Классика Computers Science». Задачи SAT и 3-SAT. Допустим, имеется множество X из n булевых переменных x1, ..., xn; каждая переменная может принимать значение 0 или 1 (эквиваленты false и true). Литералом по X называется одна из переменных xi или ее отрицание. Наконец, условием называется обычная дизъюнкция литералов

Задача классификации хорошо известна: требуется отнести произвольный объект из некоторой выборки к одному или нескольким классам из заранее определенного множества классов.