Алгоритмы *

В пятничном номере NY Times опубликована статья о значительных успехах, который демонстрируют в последние годы разработчики алгоритмов для самообучаемых нейросетей. В глубоких структурах есть несколько скрытых слоёв, которые традиционно тяжело было обучать. Но всё изменилось с использованием стека из машин Больцмана (RBM) для предварительной тренировки. После этого можно удобно перенастраивать веса, применяя метод обратного распространения ошибки (backpropagation). Плюс появление быстрых GPU — всё это привело к существенному прогрессу, который мы наблюдаем в последние годы.

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

Прошло уже больше года после завершения конкурса "Интернет-математика: Яндекс.Карты", но нас до сих пор спрашивают об алгоритме, который принёс нам победу в этом конкурсе. Узнав о том, что недавно Яндекс объявил о старте очередной "Интернет-математики", мы решили поделиться опытом нашего прошлогоднего участия и описать наш подход. Разработанный алгоритм смог с точностью 99.44% правильно определить лишние изображения в сериях панорамных снимков, например, как здесь:



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

Исходный код нашего решения доступен на github (C++ с использованием OpenCV).

Доброго времени суток, уважаемые читатели.
Многие из вас наверняка знают о том, что на протяжении нескольких лет NIST проводил конкурс среди хеш-функций с целью принятия нового стандарта SHA-3. И в этом году награда нашла своего героя. Новый стандарт был благополучно принят.
Ну а раз стандарт уже принят, самое время посмотреть что же он из себя представляет.
И тихим, субботним вечером, я обложившись мануалами открыв в браузере google.com начал свое небольшое исследование.

Обычно мы пишем про хостинги, в частности про зарубежный shared хостинг в США. Но чтобы писать, нужно иметь аналитические данные под рукой. Вот как раз тут требуется помощь Google Docs, если файл получится предположительно меньше 400 000 строк.

За несколько месяцев работы с таблицами Google пришлось много раз анализировать посредством формул разного рода данные. Как и ожидалось — то, что можно было решить в MS Excel, можно реализовать и в Google таблицах. Но многочисленные попытки решить проблемы с помощью любимого поисковика приводили только к новым вопросам и почти к нулевым ответам.
Посему, было решено облегчить жизни другим и прославить себя.

Кратко о главном

Для того чтоб Excel, либо spreadsheet (таблица Google) поняли что написанное — это формула, необходимо поставить знак "=" в строку формул (Рисунок 1).


Рисунок 1
Далее, начинаем писать формулу с клавиатуры либо выделяем мышкой те ячейки, с которыми мы собираемся работать.

Инженеры из Массачусетского технологического института под руководством Муриель Медард (Muriel Médard) уже много лет ведут разработку расширения TCP/NC для протокола TCP, с помощью которого можно сохранить максимальную скорость передачи данных в сетях с потерями пакетов. В первую очередь, TCP/NC планируют применять в беспроводных сетях WiFi, где потери пакетов обычно составляют 2-5%, а временами до 10%. Наконец-то дошло дело до реальных экспериментов.

Во время первых полевых испытаний TCP/NC в локальной WiFi-сети общежития МТИ (потеря пакетов 2%) средняя скорость передачи данных по WiFi выросла с 1 Мбит/с до 16 Мбит/с. Тест в поезде на большой скорости (потеря пакетов 5%) показал увеличение скорости WiFi с 0,5 Мбит/с до 13,5 Мбит/с. Это вполне совпадает с теоретическими расчётами.

Всем привет! В сентябре прошла международная олимпиада по программированию, IOI 2012. И мы, сборная России, на неё весьма успешно съездили, как вы могли видеть.

Я — Макс Ахмедов. Мне предложили поделиться с общественностью, что представляют собой подобные соревнования и какие задачи нам приходится решать. Я расскажу о последней задаче второго тура «Jousting Tournament». Английский вариант условия можно найти здесь. К слову, это наиболее простая из трёх задач в тот день :-)

Легенда

В задаче идёт речь о церемонии обручения герцога Лодовико Сфорца, наместника Милана, и герцогини Беатриче д’Эсте, произошедшей в 1491. Организовывать празднества и управлять культурной программой герцог пригласил своего хорошего друга Леонардо да Винчи, который ему предложил, в частности, устроить шикарный рыцарский турнир.

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

Такая вот захватывающая история.

Об экспериментах с компьютерной голографией писалось неоднократно. [1, 2, 3] Мне эта тема просто любопытна. Я как-то экспериментировал с бит-реверсивной перестановкой (bit-reversal permutation) изображений и случайно обнаружил голографические свойства. Но обо всем по порядку.

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

Недавно Реймонд Чен завершил серию постов, начатую ещё полтора года назад, и посвящённую управлению виртуальной памятью безо всякой поддержки со стороны процессора: Windows до версии 3.0 включительно поддерживала реальный режим 8086. В этом режиме трансляция адреса из «виртуального» (видимого программе) в физический (выдаваемый на системную шину) осуществляется бесхитростным сложением сегмента и смещения — никакой «проверки доступа», никаких «недопустимых адресов». Все адреса доступны всем. При этом в Windows могли одновременно работать несколько программ и не мешать друг другу; Windows могла перемещать их сегменты в памяти, выгружать неиспользуемые, и по мере необходимости подгружать назад, возможно — по другим адресам.

(Интересно, всегдашние холиворщики «это была графическая оболочка, а не операционная система» в курсе об этих её необычайных способностях?)

Немецкий учёный Штефан Рафлер создал интересную модификацию «Жизни» — клеточного автомата, придуманного в 1970 году Джоном Конвеем, в которой вместо дискретной прямоугольной сетки жизнь развивается в непрерывной среде. «Клетки» в ней имеют форму дисков, планеры могут летать в любых направлениях и водить хороводы — получается совершенно завораживающая картина.



Вот слайд-шоу с кратким описанием алгоритма, документ с более глубоким погружением в детали и исходники.

В комментариях к моему предыдущему посту «Игра «Жизнь» и моделирование естественного отбора» первое же, что предложили, — добавить скрещивание, чтобы новая клетка получала не копию генома одного родителя, а смесь от нескольких. Я подозревал, что итог это не изменит. Но, покрутив в голове идею, заинтересовался: ведь так можно получить модель не просто естественного отбора, а уже полноценной эволюции. Благо, реализовать это было не сложно. Так что встречайте: «Жизнь», теперь со скрещиванием и мутациями.

Ну да, ещё и с мутациями. Моделировать, так моделировать.

Подробности, как водится, под катом.

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

Вот так выглядит 700:


По расположению точек несложно заметить, что всего их здесь 7*5*5*2*2.

Далее описание того, как это работает.

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

Я задумался об игре «Жизнь», которую на Хабре не так давно вспоминали. Мне стало обидно за несчастные клетки, которые живут и умирают в зависимости от одних только начальных условий, и ничего сами для своего выживания сделать не могут. В результате я придумал расширение для правил игры, с которым можно моделировать не только изменение численности популяции, но и естественный отбор внутри неё.

Самые нетерпеливые сразу могут посмотреть, что получилось, а остальных прошу под кат за рассказом.

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


Затем, чтобы помогать водителям непосредственно во время движения, мы добавили в мобильные Яндекс.Карты (и, как следствие, в Яндекс.Навигатор) автоматическое перестроение маршрута. Приложения научились адаптировать маршрут при каждом заметном изменении ситуации в городе.

Собрав на десктопе и в мобильном информацию про «сейчас», мы перешли к решению вопроса «а как будет потом?»:


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



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

Представляю вашему вниманию заключительную статью из трилогии «Восстановление расфокусированных и смазанных изображений». Первые две вызвали заметный интерес — область, действительно, интересная. В этой части я рассмотрю семейство методов, которые дают лучшее качество, по сравнении со стандартным Винеровским фильтром — это методы, основанные на Total Variaton prior.
Также по традиции я выложил новую версию SmartDeblur (вместе с исходниками в open-source) в которой реализовал этот метод. Итоговое качество получилось на уровне коммерческих аналогов типа Topaz InFocus. Вот пример обработки реального изображения с очень большим размытием:

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

История вопроса

Заказчик разрабатывает динамические музыкальные фонтанные комплексы, которые управляются через dmx контроллеры по сценарию. Редактор сценариев он сделал самостоятельно. Но на практике создавать сценарии оказалось неудобным, потому что для того, чтобы видеть как получается нужно иметь целиком построенный и запущенный фонтан. Кроме того, если вдруг дизайнеру хореографу захотелось добавить дополнительные сопла для фонтана — то этого сделать уже практически невозможно. Поэтому заказчик захотел обзавестись модулем для моделирования фонтанов, чтобы хореограф мог без настоящего фонтана разрабатывать сценарии. В целом у меня вышло что-то в таком духе: вот видео того что было смоделировано Hawaii50.wmv, а вот то, что вышло в реале после конструирования фонтана: H5OClip.wmv

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

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

Предлагаю ознакомиться с принципом работы алгоритма Диффи – Хеллмана в замечательном видео от Art of the Problem в моем переводе.

Тема префиксных деревьев поиска уже неколько раз поднималась на хабре. Здесь, например, кратко описывается, что такое префиксное дерево и зачем оно нужно, и рассматриваются основные операции над такими деревьями (поиск, вставка, удаление). К сожалению, ничего при этом не говорится про реализацию. В этом недавнем посте рассматривается «питонья библиотека datrie», являющаяся Cython-оберткой библиотеки libdatrie. По последней ссылке имеется хорошее описание реализации частично сжатых префиксных деревьев в виде детерминированных конечных автоматов (с использованием массивов). Я решил внести свои пять копеек в эту тему, рассмотрев реализацию на языке С++ префиксных деревьев с помощью указателей. Кроме того, была и еще одна цель — сравнить между собой поиск строк с помощью сбалансированного двоичного дерева поиска (АВЛ-дерево) и сжатого префиксного дерева.

Фильтр размытия по гауссу (широко известный “gaussian blur” в фотошопе) достаточно часто применяется сам по себе или как часть других алгоритмов обработки изображений. Далее будет описан метод, позволяющий получать размытие со скоростью, не зависящей от радиуса размытия, используя фильтры с бесконечной импульсной характеристикой.

На Хабре и в сети часто начали появляться статьи, посвященные уязвимостям генераторов случайных чисел. Данная тема крайне обширна и является одной из основных в криптографии. Под катом находится описание случайных чисел от A до Z. Статья является результатом свободного перевода цикла статей из одного западного блога и личных дополнений автора. Основная цель — получить feedback и поделиться знаниями.