Алгоритмы *

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

Вводная

Тем из нас, кому приходится тратить полчаса-час на путешествие из Москвы в Москву, приходится искать, чем занять и разогреть ещё не до конца проснувшийся мозг. Кто-то читает, кто-то кидает птичек, кто-то решает математические головоломки. Например, классическая задачка: среди шести цифр автобусного билета расставить скобки и операторы так, чтобы получилось число 100. Бывает так, что ну никак не удаётся найти решение, и конкретная задачка не отпускает весь оставшийся день. Поневоле задумаешься над алгоритмом.
Решение «в лоб» подстановкой скобок и операторов и проверка на каком-нибудь математическом движке не устраивало, генетические алгоритмы, по которым я с ума схожу, не подходили из-за склонности скапливаться в локальных экстремумах. В итоге задача свелась к перебору всех возможных двоичных деревьев с заданным числом листьев (для шести их ровно 42).

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



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

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

Свои вопросы пишите в комментарии, ибо уже определились со вторым постом.

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



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

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

Сначала немного статистики для того, чтобы показать важность настоящего исследования. Около 50% пользователей нашей системы регистрируются с привязкой аккаунтов социальных сетей vkontakte (VK) и facebook (FB). Причем из зарегистрированных через социальные сети 71% приходится на VK и 29% на FB.

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

Практически каждая новость от DARPA, связанная с роботами и искусственным интеллектом, неизбежно сопровождается набившими оскомину комментариями про Скайнет. Но на этот раз они будут на удивление уместны. Новая исследовательская программа Агентства посвящена вероятностному программированию для решения продвинутых задач машинного обучения (Probabilistic Programming for Advanced Machine Learning или PPAML). По словам руководителя программы Кэтлин Фишер, DARPA намерено ни много ни мало «Сделать для машинного обучения то, что появление языков высокого уровня 50 лет назад сделало для программирования в целом».

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

Введение

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

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

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

1. Основы

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

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

На мой взгляд вышло довольно сумбурно, но многим понравилось. Вот примерный план лекции:

• Что такое информатика и computer science?
• Что такое алгоритм?
• Лучшие решения обычно не очевидны
• Машина Тьюринга и фундаментальные ограничения копьютеров
• Что такое простые и сложные задачи?
• Задача Коммивояжера
• Почему языки программирования не похожи на человеческие языки?

Видео разбито на две части (один, два). Чтобы пропустить введение – начинайте смотреть с 2:56.

Часть 1:

Несколько дней назад на xkcd.com был опубликован комикс о неэффективных методах сортировки. Alt-текст к нему рассказывал о сортировке методом StackSort, который заключается в том, чтобы скачать со StackOverflow блоки кода, которые можно найти по запросу «сортировать список» и запускать один за другим, пока не найдётся работоспособный вариант. Бред? Ещё бы не бред! Встречайте на Гитхабе реализацию StackSort на JavaScript.

Одному из коллег понадобилось вывести число с ведущими нулями, чтобы получилось вот такое:

1       => 001
23      => 023
456     => 456
7.89    => 007.89
12345.6 => 12345.6

В его случае требовалось иметь минимум три цифры в целой части. Мы с другим коллегой крепко призадумались, как ему помочь… Через 10 минут накидали десяток вариантов, естественно, сравнивая, чей быстрее. В конце концов нашли быстрое решение, но нам этого показалось мало. «Давай, у кого короче!» В итоге полдня мы провели с пользой, остановившись на достаточно лаконичном варианте. Но в сердце тлеет огонёк надежды, что удастся сэкономить ещё пару байт драгоценного дискового пространства.

В большинстве современных языков программисту уже не нужно заботиться о числах, с которыми процессор непосредственно манипулировать не может. Где-то, как в Python или Haskell, поддержка длинных целочисленных типов встроена прямо в ядро языка, где-то, как в Java или C#, реализована в виде отдельных классов. Но в стандартной библиотеке языка C++ длинные числа до сих пор не поддерживаются. Поэтому я решил написать её сам.

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

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

Введение

Зачем это вообще надо? В науке и около нее очень часто возникает задача предсказания какого-то неизвестного параметра объекта исходя из известных параметров этого объекта (предикторов) и большого набора похожих объектов, так называемой учебной выборки. Пример. Вот мы выбираем на базаре яблоко. Его можно описать такими предикторами: красность, вес, количество червяков. Но как потребителей нас интересует вкус, измеренный в попугаях по пятибалльной шкале. Из жизненного опыта нам известно, что вкус с приличной точностью равен 5*красность+2*вес-7*количество червяков. Вот про поиск такого рода зависимостей мы и побеседуем. Чтобы обучение пошло легче, попробуем предсказать вес девушки исходя из ее 90/60/90 и роста.

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

Автоматическое определение категорий для веб-страниц из RSS-лент

Обычная схема добавления веб-страниц (вернее, ссылок на них) в Surfingbird такова: при добавлении новой ссылки пользователь должен указать до трёх категорий, к которым принадлежит эта ссылка. Понятно, что в такой ситуации задача автоматического определения категорий не стоит. Однако, кроме ручного добавления, ссылки попадают в базу и из RSS-потоков, которые предоставляют многие популярные сайты. Поскольку ссылок, поступающих через RSS-потоки, очень много, зачастую модераторы (а в этом случае именно они вынуждены проставлять категории) просто не справляются с таким объёмом. Возникает задача создания интеллектуальной системы автоматической классификации по категориям. Для ряда сайтов (например, lenta.ru или sueta.ru) категории можно вытащить непосредственно из rss-xml и вручную привязать к нашим внутренним категориям:

В настоящей заметке я расскажу о том, как можно построить систему оптического распознавания структурной информации, опираясь на алгоритмы, применяющиеся в обработке изображений и их реализации в рамках библиотеки OpenCV. За описанием системы стоит активно развивающийся open source проект Imago OCR, который может быть непосредственно полезен в распознавании химических структур, однако в заметке я не буду говорить о химии, а затрону более общие вопросы, решение которых поможет в распознавании структурированной информации различного рода, например таблицы или графики.

QR код — это монохромная картинка, на которой некоторые устройства (например смартфон со специальным приложением) распознают текст. Этим текстом может быть не только простая фраза, но и, хоть это и не входит в официальную спецификацию, ссылка, номер телефона или визитная карточка. Такие коды чаще всего используют, чтобы закодировать ссылку и распечатать её на плакате или визитке.

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

За основу этой статьи взят цикл статей «QR Code Demystified» Джейсона Брауна (Jason Brown). В этих статьях опущено много нюансов, что вызвало у меня некоторые проблемы. Все эти нюансы учтены и упомянуты здесь.

В данной статье представлен алгоритм распознавания пола, обладающий точностью 93.1% [1]. Статья не требует каких-либо предварительных знаний в области обработки изображений или машинного обучения. После прочтения статьи читатель будет в состоянии выполнить рассмотренный алгоритм самостоятельно.

Строительство Саграда Фамилия началось в 1882 году, а позже в этом году строительство возглавил знаменитый архитектор Антонио Гауди́, который заложил основы ставшей теперь знаменитой на весь мир церкви Барселоны. Гауди посвятил Саграда Фамилия многие годы и спустя 130 лет храм считается одним их самых потрясающих и уникальных строений на Земле. Хотя за прошедшее время строительство так и не было завершено.

Намедни прочел интересную статью про рейтинги. В качестве практического руководства ее не рекомендую использовать (почему смотрите в комментариях к ней), однако, чтиво интересное и натолкнуло меня на одну мысль.
Допустим у нас есть рейтинг от 1 до 5. И некоторые оценки накручены, некоторые пользователи наобум поставили. Как отфильтровать зерна от плевел?

Итак, тема рейтинговых систем продолжает будоражить умы хабрапользователей. Появляются всё новые и новые схемы, формулы, тесты. И каждый раз всё сводится к одному и тому же вопросу: как совместить среднюю оценку пользователей с нашей уверенностью в этой оценке. Например, если один фильм получил 80 положительных и 20 отрицательных голосов, а другой — 9 положительных и 1 отрицательный, то какой из фильмов лучше? Не претендуя на создание новой универсальной рейтинговой системы, я всё же предложу один из возможных подходов к решению именно этого вопроса.