Алгоритмы *

Привет, Хабр, давно не виделись. В этом посте мне хотелось бы рассказать о таком относительно новом понятии в машинном обучении, как transfer learning. Так как я не нашел какого-либо устоявшегося перевода этого термина, то и в названии поста фигурирует хоть и другой, но близкий по смыслу термин, который как бы является биологической предпосылкой к формализации теории передачи знаний от одной модели к другой. Итак, план такой: для начала рассмотрим биологические предпосылки; после коснемся отличия transfer learning от очень похожей идеи предобучения глубокой нейронной сети; а в конце обсудим реальную задачу семантического хеширования изображений. Для этого мы не будем скромничать и возьмем глубокую (19 слоев) сверточную нейросеть победителей конкурса imagenet 2014 года в разделе «локализация и классификация» (Visual Geometry Group, University of Oxford), сделаем ей небольшую трепанацию, извлечем часть слоев и используем их в своих целях. Поехали.

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

Под катом краткий обзор метода выделения гармоник из произвольного сигнала с помощью цифрового гетеродинирования, и немного особой, Фурье-магии.

Это последняя, на сегодняшний день, статья из цикла про внутреннее устройство конкурентных ассоциативных контейнеров. В предыдущих статьях рассматривались hash map, был построен алгоритм lock-free ordered list и контейнеры на его основе. За бортом остался один важный тип структур данных — деревья. Пришло время немного рассказать и о них.

Исследования, посвященные алгоритмам конкурентных деревьев, не требующих внешней синхронизации доступа к ним, начались довольно давно — в 70-х годах прошлого века, — и были инициированы развитием СУБД, поэтому касались в основном оптимизации страничных деревьев (B-tree и его модификации).

Развитие lock-free подхода в начале 2000-х не прошло мимо алгоритмов деревьев, но лишь недавно, в 2010-х годах, появилось множество действительно интересных работ по конкурентным деревьям. Алгоритмы деревьев довольно сложны, поэтому исследователям потребовалось время — порядка 10 лет — на их lock-free/non-blocking адаптацию. В данной статье мы рассмотрим самый простой случай — обычное бинарное дерево, даже не самобалансирующееся.

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

В этом посте я расскажу, почему так получилось: чего мы не смогли предвидеть, когда придумывали первую версию ПО Яндекс.Диска, и как создавали новую.



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

Каждый университет сталкивается с тем, что на некоторые темы в городе невозможно найти преподавателя, который бы являлся в этой теме специалистом. Один из вариантов решить эту проблему состоит в том, чтобы поручить подготовить курс на эту тему какому-нибудь из имеющихся преподавателей, который не является специалистом в этой области. Мы в Акадеическом университете стараемся пойти другим путем — пригласить специалиста для чтения курса. В прошлом году мы поучаствовали в конкурсе фонда Династия “приглашенный профессор”. Мы подали две заявки и обе выиграли, а также два наших преподавателя были приглашены в Уральский и Казанский федеральные университеты. В сентябре 2014 года Александр Охотин из университета Турку прочитал курс Формальные грамматики. А 18 марта начнет читать курс “Комбинаторика слов и ее приложения” профессор Уральского федерального университета Арсений Михайлович Шур. Мы приняли решение сделать этот курс полностью открытым для всех и провести его в рамках Computer Science клуба, нашего постоянного партнера.

Арсений Михайлович — активный исследователь в области комбинаторики слов, поэтому курс обещает быть очень интересным. Первое занятие состоится в среду 18 марта в 18-30 в Мраморном зале ПОМИ РАН (Санкт-Петербург, наб. реки Фонтанки д. 27), вход свободный, регистрация не требуется.

Подробное описание курса и расписание: тут.

Краткое описание курса

Предисловие

В 2013 году с целью популяризации робототехники в России и создания среды программистов и инженеров, ориентированных на данную тематику компания КРОК (г.Москва) организовала конкурс «Летающие роботы». Наша команда «iKar» (3 человека из Барнаула и 1 из Москвы) участвовала в 2013 году (конкурс «Улететь и вернуться») и 2014 году («Догнать и перегнать Крок») не победила, но добилась неплохих результатов.

1. С чего все началось или условия конкурса

Будучи по профессии программистом 1С, нередко приходится пользоваться форумом forum.mista.ru. Один из моих друзей-коллег первым заметил объявление на тему «Кому лимон» и предложил участвовать.

Условия конкурса выглядели заманчиво: необходимо было построить или купить летающего робота и научить его перемещаться/ ориентироваться в помещении-полигоне, автоматически взлетать и садиться и распознавать посадочные маркеры. Срок на всю работу 1 год, а приз — 1 миллион рублей.



Имелся опыт построения вертолетов и квадрокоптеров, как для хобби, так и для профессионального применения в аэрофотосъемке. Было много вопросов по поводу различных настроек, ПИД коэффициентов, кода и алгоритмов полетных контроллеров. Используя мотивацию конкурса, можно было глубоко во всем разобраться.

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

На Хабре недавно была опубликована статья «Перевод времени в деньги и обратно». В дальнейшем я буду именовать её исходной, ибо отталкиваться буду в основном от высказанных там идей. Так вот, в той статье есть много моментов, которые хочется поправить. Данная статья задумывалась как статья-ответ.

Из этой статьи вы узнаете, что распознавание даже коротких звуковых фрагментов в зашумленной записи — вполне решаемая задача, а прототип так вообще реализуется за 30 строчек кода на Python. Мы увидим, как тут помогает преобразование Фурье, и наглядно посмотрим, как работает алгоритм поиска и сопоставления отпечатков. Статья будет полезна, если вы сами хотите написать подобную систему, или вам интересно, как она может быть устроена.

В предыдущих статьях (раз, два) мы рассматривали классический hash map с хеш-таблицей и списком коллизий. Был построен lock-free ordered list, который послужил нам основой для lock-free hash map.
К сожалению, списки характеризуются линейной сложностью поиска O(N), где N — число элементов в списке, так что наш алгоритм lock-free ordered list сам по себе представляет небольшой интерес при больших N.
Или все же представляет?..

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

Я решил представить на суд уважаемого хабрасообщества свою разработку — метод фрагментарного сжатия видеопотока. Особенностью предлагаемого метода является полное соответствие сжатого видеопотока исходному, то есть метод осуществляет сжатие без потерь.

Привет!

Как мы писали ранее, 29 июля в Санкт-Петербурге в седьмой раз откроется ежегодная Летняя школа Microsoft Research по машинному обучению.
Обычно следующий за открывающим постом пост пишут, когда известны докладчики, но тут я не смог удержаться.



Школа получила поддержку ACM Europe! На ней выступит докладчик от ACM, и все участники получат статус профессионального члена ассоциации (ACM Professional Membership) и доступ к цифровой библиотеке (ACM Digital Library) на один год. В один из вечеров ассоциация организует вечеринку (beer party) для участников школы. Для нас это большая радость — подобное происходит впервые, и докладчик от АСМ, который знают все как старейшую ИТ-организацию — ценность для слушателей.

Напоминаем, что регистрироваться надо все еще здесь.

У меня есть сайт со статьями схожей тематики. На сайте было две проблемы: спамерские сообщения и дубликаты статей, причём дубликаты часто являлись не точными копиями.

Данный пост повествует о том, как я решил эти проблемы.

Дано:

• общее количество статей 140 000;
• количество спама: примерно 16%;
• количество не чётких дубликатов: примерно 63%;

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

Пройдем по следам C++ 2015 Russia далее.
В предыдущей статье мы рассмотрели алгоритм для lock-free ordered list и на его основе сделали простейший lock-free hash map. У этого hash map есть недостаток: размер хеш-таблицы постоянен и не может быть изменен в процессе роста числа элементов в контейнере. Это не представляет проблемы, если мы заранее примерно представляем требуемый объем контейнера. А если нет?

Посмотришь на любую программу обучения по IT-специальности, и тут же увидишь дисциплину «Дискретная математика» (возможно, под другим названием), обычно для перво- или второкурсников. И её наличие вполне разумно, поскольку дискретная математика и непрерывная математика (представленная на первом курсе институтов с незапамятных времён математическим анализом) — две грани единой Математики, — красивой, могучей науки.

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

Ну хорошо, математикам всё математическое интересно. А зачем дискретная математика программисту?

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

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

Мне оказали честь — пригласили выступить на первой конференции C++ 2015 Russia 27-28 февраля. Я был насколько наглым, что запросил 2 часа на выступление вместо положенного одного и заявил тему, наиболее меня интересующую — конкурентные ассоциативные контейнеры. Это hash set/map и деревья. Организатор sermp пошел навстречу, за что ему большое спасибо.
Как подготовиться ко столь ответственному испытанию выступлению? Первое — нарисовать презентацию, то есть кучу картинок, желательно близко к теме. Но надо ещё и два часа озвучивать картинки, — как все это запомнить? Как избежать глубокомысленных «ээээмммм», «здесь мы видим», «на этом слайде показано», несвязных прыжков повествования и прочих вещей, характеризующих выступающего c не очень хорошей стороны в части владения родным языком (это я про русский, с C++ я разобрался быстро — никакого кода в презентации, только картинки)?
Конечно, надо записать свои мысли, глядя на слайды. А если что-то написано, то не худо бы и опубликовать. А если публиковать, — то на хабре.
Итак, по следам C++ 2015 Russia! Авторское изложение, надеюсь, без авторского косноязычия, без купюр и с отступлениями по теме, написанное до наступления события, в нескольких частях.

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

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

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

Привет ребят, давайте для начала проверим вашу память. Итак:

«На море на океане есть остров, на том острове дуб стоит, под дубом сундук зарыт, в сундуке — заяц, в зайце — утка, в утке — яйцо» в яйце игла — смерть Кощея!

А теперь, внимание, вопрос — как это формализовать?
Как приатачить к яйцу иголку и какова временная сложность детача смертии моей. Как перенести сказку в быль, как это выглядит на B-деревьях и почему на самом деле нет разницы между 2D и 1D.
А было все так: давным давно, в неком царстве, некотором государстве, на одном сервисе с шейрингом геолокации очень захотелось Иванушке Дурачку на уровне ЧПУ разделить Москву(/RU/MOW/) и Область(/RU/MOS/). И вообще навести порядок, чтобы все лежало по полочкам красиво и по алфавиту. Но не получалось ему сокровища свои посчитать, и аккуратно разложить. А Василису, хоть и дурак, к сбережениям не пускал.
Но решение было найдено.
Совсем недалеко над каким-то златом успешно чах Чахлик, еще и смерть он свою прятал по науке.
И если задача определения региональной (точнее полигональной) принадлежности некой иголки к некому сундуку выходит за рамки данной статьи, то нам ничто не мешает погрузиться в глубины зайца и посмотреть как он устроен на табличном уровне.
PS: и не спрашивайте почему зайца.

Добрый день! Полтора года назад моей команде пришлось протестировать Java Swing приложение, которое могло иметь разные визуализации, натянутые на общий процесс. Статей тогда по этой теме было немного, конкретные решения отсутствовали вообще. TestComplete и прочие скриптовые технологии (да простят меня сторонники TestComplete) использовать не хотелось, так как приложение должно иметь гибкую архитектуру, расширяемую и изменяемую в рамках Agile процесса.

Сутки поиска в Google, анализ десятков примеров и технологий привели меня к двум возможным вариантам:

• Fest
• Jemmy

Не погружаясь в глубины глубин сравнения, я выбрал Fest библиотеку. С её помощью и, конечно, Junit, Mockito мы начали тестировать наше приложение. Об этом и расскажу ниже.