Примечание переводчика: Мы довольно часто пишем об алгоритмической торговле (вот, например, список литературы по этой теме и соответствующие аналитические материалы) и API для создания торговых роботов, сегодня же речь пойдет непосредственно об алгоритмах, которые можно использовать для анализа различных данных (в том числе на финансовом рынке). Материал является адаптированным переводом статьи американского раработчика и аналитика Рэя Ли.

Сегодня я постараюсь объяснить простыми словами принципы работы 10 самых эффективных data mining-алгоритмов, которые описаны в этом докладе.

Когда вы узнаете, что они собой представляют, как работают, что делают и где применяются, я надеюсь, что вы используете эту статью в качестве отправной точки для дальнейшего изучения принципов data mining.

Не так давно передо мною встала задача закодировать переписку пользователей. Целью задачи было пересылать уже закодированную строку от пользователя А пользователю Б. Строка кодируется и декодируется с помощью ключа, который известен обоим. Подразумевается, что сообщение от пользователя А отсылается на сервер пользователю Б, где пользователь Б его и забирает. Чтобы избежать получение данных в случае получения сообщения третьим лицом путем перехвата сообщения, либо доступа к серверу, где оно хранится, функцию было решено организовать на JavaScript, что дает возможность пользователям отсылать закодированную строку прямо из окна браузера.

Бегло пробежавшись по некоторым способом шифрования, я решил написать собственный алгоритм. Суть алгоритма было решено свести к тому, чтобы перемешивать каждый отдельный символ в неким уникальным значением смешанным с ключом, причем так, чтобы значение, которое будет смешивать данные символы было уникальным и формировалось из заданного пароля или ключа. Творческой идеей для написания именно такого алгоритма послужил шифр Эль-Гамаля, метод преобразования Punycode и Base64. На нобелевскую премию я не претендую, но тем не менее решил поделиться собственным творением и…

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

Формулировка

Есть большая база текстов (сотни тысяч текстов). Длины текстов примерно одинаковые, около 250 символов, язык — английский. Некоторые из текстов отредактированы (исправлены опечатки, расставлены запятые и т.п.); таким образом в базе оказывается как оригинальный текст, так и его исправленная копия. Таких пар не очень много, скажем не более 1%. Задача: найти все такие пары.

О чем речь

В данном посте я бы хотел описать часть системы времени выполнения (RTS — RunTime System в дальнейшем) компилятора DVMH. Рассматриваемая часть, как видно из заголовка, относится к обработке пользовательских массивов на GPU, а именно, их автоматическая трансформация или реорганизация в памяти ускорителя. Данные преобразования делаются для эффективного доступа к памяти GPU в вычислительных циклах. Что такое DVMH, как можно подстраиваться под вычисления и почему это делается автоматически — описано далее.

Понятие энтропии в середине XX века ввёл Клод Шеннон. Её можно интуитивно описать как «среднее количестве битов информации в одном значении случайной величины». Но её нельзя применить к индивидуальным объектам (скажем, к тексту романа или ДНК) — где нет ансамбля многих однородных объектов, нет и случайных величин.



В середине 1960-х годов разным людям (Колмогоров, Соломонов, Левин, Чейтин) стало понятно, что можно определять количество информации (сложность) индивидуального объекта как минимальную длину программы, которая этот объект порождает (при естественных ограничениях на язык программирования). Возникла алгоритмическая теория информации, которая оказалась связанной с разными областями: от философских вопросов оснований теории вероятностей (когда мы отвергаем статистические гипотезы?) до комбинаторики (неравенства, связывающие размеры множеств и их проекций) и теории вычислимости.

Лекцию, которую мы выбрали для вас сегодня, читал на факультете компьютерных наук Вышки известный математик Александр Шень. Когда-то он под руководством Владимира Успенского, ученика Колмогорова, защитил диссертацию «Алгоритмические варианты понятия энтропии».

Введение

Алгоритм четно-нечетной сортировки слиянием (odd-even mergesort) был разработан Бэтчером в 1968 году. Алгоритм не слишком популярный и не слишком известный. Однако он достаточно легко параллелится и его реализация не слишком сложна. Лично я узнал о нем когда разбирался с MPI и увидел тестовое задание на coursera: написать сортировку Бэтчера.

Перевод поста Джона Маклуна "Droste Effect with Mathematica". Код, приведенный в статье, можно скачать в конце поста.
Выражаю огромную благодарность Кириллу Гузенко за помощь в переводе.

---

Эффект Дросте (wiki) представляет собой рекурсивное включение изображением самого в себя. Название происходит от какао-порошка Droste, который в 1904 году продавался в упаковке, на которой была изображена медсестра, которая держала коробку, на которой была медсестра, ну и так далее. Самая простая реализация — отмасштабировать и трансформировать изображение, а затем поместить его на свою немодифицированную точную копию, затем начать процесс снова. Взгляните на демонстрацию, в которой используется оригинальные иллюстрации упаковки Droste. Однако значительно более интересных результатов можно достичь, если использовать теорию функций ко́мплексного переменного (ТФКП). Эшер М. К. был первым, кто популяризировал идею конформных отображений применительно к изображениям, однако с помощью компьютеров мы легко можем реализовать эту идею на фотографиях для получения чего-то подобного:

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

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

Постановка задачи

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

Перевод поста Matthias Odisio "Seeing Skin with Mathematica".
Скачать файл, содержащий текст статьи, интерактивные модели и весь код, приведенный в статье, можно здесь.
Выражаю огромную благодарность Кириллу Гузенко за помощь в переводе.

---

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

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

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

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



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

Введение

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

Код предназначен для Python 3, хотя должен идти и на Python 2.

Для начала – напомню определение:

F_n= F_n-1+ F_n-2

и F₁= F₂=1.

По долгу службы мне часто нужно находить все пересечения между текстами (например, все цитаты из одного текста в другом). Я достаточно долго искал стандартное решение, которое бы позволило бы это делать, но найти его мне так и не удалось — обычно решается какая-то совсем или немного другая задача. Например, класс SequenceMatcher из difflib в стандартной библиотеке Питона находит самую длинную общую подпоследовательность в двух последовательностях hashable элементов, а потом рекурсивно повторяет поиск слева и справа от нее. Если в одном из текстов будет более короткая подпоследовательность, которая содержится внутри уже найденной (например, если кусок длинной цитаты где-то был повторен еще раз), он ее пропустит. Кроме того, когда я загнал в него «Войну и мир» и «Анну Каренину» в виде списков слов и попросил для начала найти самую длинную подпоследовательность, он задумался на семь минут; когда я попросил все совпадающие блоки, он ушел и не вернулся (в документации обещают среднее линейное время, но что-то в прозе Льва Толстого, по-видимому, вызывает к жизни worst-case квадратичное).

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

Привет, Хабр!

Мы в HumanFactorLabs парсим адреса в особо крупных размерах. Наши продукты упрощают ввод контактных данных и работу с ними.

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

Недавно на Хабре нас попросили привести примеры необычных адресов, в связи с чем и написана эта статья.

В воскресенье 14 июня прошел отборочный раунд RCC 2015. За звание финалиста RCC 2015 сразились 604 программиста, прошедших квалификацию в предыдущих трех раундах. Хотя бы одно правильное решение прислали 324 участника. А теперь герои раунда! Петр Митричев занял первую строчку турнирной таблицы, первым решив задачи B (Разбиение на команды) и F (Освещение сцены) за 20:32 и 1:31:41. Геннадий Короткевич идет вторым — он первым за 2 минуты и 30 секунд решил задачу A (Игра со строками) и раньше всех справился с задачей D (Декартовы деревья) за 14:16. Makoto Soejima из Японии — третий, судя по всему перед решением он переводил условия задач через онлайн-переводчик. Михаил Пядёркин первый решил задачу C (Карта) за 51 минуту и 4 секунды. Егор Куликов первым решил задачу E (Аллея) за 1 час 5 минут и 49 секунд. По итогам отборочного раунда в финал вышли 50 участников. 19 сентября в Финале определится сильнейший программист года! Все участники отборочного раунда получат онлайн-сертификаты, а 200 лучших из них получат футболки RCC 2015.

В одном из моих проектов, который был связан с компьютерным зрением, возникла задача сортировки большого массива чисел (около 100 млн. элементов). Код сортировки должен был выполняться как можно быстрее, причем с возможностью исполнения на нескольких процессорах, и желательно на GPU. Сортировка реализованная в стандартной библиотеке C++ не подходила: она основана на алгоритме Quick Sort, который на данный момент не поддается массивному распараллеливанию на GPU. Поиск других способов привел к алгоритму Radix Sort, но в найденных источниках описывалась реализация требующая большого расхода памяти, точнее памяти требовалось: (количество элементов массива) * (размер radix массива). Для массива 100 млн. элементов и radix массиве размером 256 элементов памяти потребовалось бы 25.6 Гб, мало реальное требование, на текущий момент развития вычислительной техники. Но для распараллеливания вычислений алгоритм Radix Sort подходит неплохо, собственно поэтому автор попытался доработать этот способ, чтобы уменьшить расход памяти до приемлемых значений.

Компьютерные игры про танки являются одними из самых популярных в game-индустрии. История подобных игр насчитывает десятки лет, но популярность их не угасает. Тема танков и танковых сражений получает развитие не только в компьютерных играх, но и является предметом соревновательного процесса в программировании. Например, в 2012 году проходили соревнования по программированию Russian AI Cup — CodeTanks. Участникам предлагалось разработать искусственный интеллект управления танком. Спустя несколько лет подобное соревнование повторилось. Организатором выступила компания National Instruments, которая ежегодно проводит олимпиады по программированию в среде LabVIEW среди студентов и молодых ученых. Участникам олимпиады 2015 года предлагалось разработать алгоритм для автономного управления танком средствами LabVIEW (представление об этой среде программирования можете получить по ссылке: «LabVIEW — первое знакомство»). Данная статья посвящена описанию алгоритма танка-победителя от команды LabVIEWPortal.

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

Многие Android-устройства используют процессоры с несколькими вычислительными ядрами, поэтому в отрасли разработки мобильных приложений всё более важным становится умение создавать многопоточные программы. Компания Intel предлагает ценный инструментарий для разработки «параллельных» приложений – он называется Intel Threading Building Blocks (Intel TBB). По существу, Intel TBB представляет собой кросс-платформенную библиотеку шаблонов для создания параллельных программ. Она позволяет создавать и синхронизировать потоки данных, оставляя за кадром детали архитектуры и позволяя вам работать на высоком уровне абстрагирования. Intel TBB поддерживает все архитектуры. Что касается ОС Android, то следует использовать версию 4.3 и выше.

Привет, Хабр!

А давайте поговорим про одну из легенд Амазона — книгу «Elements of Programming Interviews: The Insiders' Guide».