Информация о том, что Windows 10 собирает данные о пользователях, не нова. Еще в 2014 году компания Microsoft опубликовала заявление о конфиденциальности, из которого следует, что на ее серверы может передаваться информация об использованных программах, устройстве и сетях, в которых они работают. Эти данные могут объединяться с идентификатором пользователя (учетная запись Microsoft), также собирается информация об адресе электронной почты, предпочтениях, интересах местоположении, и многом другом.

Чешское издание Aeronet.cz опубликовало расследование неназванного ИТ-специалиста, который решил отследить активность Windows 10 по сбору данных. В ходе исследования использовались следующие инструменты: программа Destroy Windows 10 Spying, блокирующая передачу данных на серверы Microsoft, PRTG Network Monitor, Windows Resource Monitor и Wireshark. По мнению исследователя, Windows 10 — больше похожа на терминал по сбору данных, чем на операционную систему.

Генератор случайных чисел во многом подобен сексу: когда он хорош — это прекрасно, когда он плох, все равно приятно (Джордж Марсалья, 1984)

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

unsigned long long BasicRandGenerator() {
    unsigned long long randomVariable;
    // some magic here
    ...
    return randomVariable;
}

и что этот генератор достаточно быстрый. Я имею ввиду, что дешевле сгенерировать с десяток случайных чисел, нежели чем посчитать логарифм или возвести в степень одно из них. Это могут быть стандартные генераторы: std::rand(), rand в MATLAB, Java.util.Random и т.д. Но имейте ввиду, что подобные генераторы редко подходят для серьезной работы. Зачастую они проваливают разные статистические тесты. А также, помните, что вы полностью зависите от них и лучше использовать свой собственный генератор, чтобы иметь представление о его работе.

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


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

Равномерное распределение

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







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

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

Вот уже как неделю английская версия the art of command line висит в секции trending на Github. Для себя я нашел этот материал невероятно полезным и решил помочь сообществу его переводом на русский язык. В переводе наверняка есть несколько недоработок, поэтому милости прошу слать пулл-реквесты мне сюда или автору оригинальной работы Joshua Levy вот сюда. (Если PR отправите мне, то я после того, как пересмотрю изменения отправлю их в мастер-бранч Джоша). Отдельное спасибо jtraub за помощь и исправление опечаток.

кадр из фильма Миссия Невыполнима II

Эта история началась пару месяцев назад, в первый день рождения моего сына. На мой телефон пришло СМС-сообщение с поздравлением и пожеланиями от неизвестного номера. Думаю, если бы это был мой день рождения мне бы хватило наглости отправить в ответ, не совсем культурное, по моему мнению, «Спасибо, а Вы кто?». Однако день рождения не мой, а узнать кто передаёт поздравления было интересно.

Первый успех

Было решено попробовать следующий вариант:

• Добавить неизвестный номер в адресную книгу телефона;
• Зайти по очереди в приложения, привязанные к номеру (Viber, WhatsApp);
• Открыть новый чат с вновь созданным контактом и по фотографии определить отправителя.

Мне повезло и в моём случае в списке контактов Viber рядом с вновь созданным контактом появилась миниатюра фотографии, по которой я, не открывая её целиком, распознал отправителя и удовлетворенный проведенным «расследованием» написал смс с благодарностью за поздравления.

Сразу же за секундным промежутком эйфории от удачного поиска в голове появилась идея перебором по списку номеров мобильных операторов составить базу [номер_телефона => фото]. А еще через секунду идея пропустить эти фотографии через систему распознавания лиц и связать с другими открытыми данными, например, фотографиями из социальных сетей.

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

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

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

Давным-давно, когда диоды были ещё вакуумными, J. В. Johnson впервые наблюдал мерцательный эффект в токе электронных ламп, который он так и назвал – мерцательным или фликкер-шумом. Прошло ровно 90 лет с тех пор, а фликкер-шум продолжают обнаруживать в самых разнообразных системах – от полупроводниковых приборов до разлива рек, от физики до социологии, но объяснить природу его происхождения так никто и не смог.

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



Всё начинается и заканчивается антенной:



Антенна, кроме, собственно, зеркала и облучающей системы, имеет в своём составе волноводные тракты, МШУ и (по варианту) систему автосопровождения, антиобледенения, осушки волноводного тракта. Осторожно, трафик.

В то время пока я собирался на ланч, мой ко-воркер Дейв окликнул меня: «Хэй, Алекс, а ты не хочешь заниматься улучшениями навыков своего программирования?». Я задумался. Это было интересное предложение, но я склонялся ответить отказом: «Сейчас я занимаюсь развитем навыков говорения на языках, дружище!». Ладно, шучу. Утро началось с того, что я добрался до почты и заполучил в руки копеечный китайский Кубик, случайно заказанный на али. К обеду я проштудировал мануал сборки и обновил мышечную память, а к вечеру пришло осознание, что я наигрался. Будущее кубика было ясным: он будет пылиться на полке, раз или два в неделю может быть я буду его собирать, чтобы привести мысли в порядок или отвлечься, но не более того. Соревнование в механической скорости сборки? Non merci, уж лучше скворечники делать…

Ситуацию, как всегда, спасли мысли об автоматизации. После недолгого изучения я узнал рекогнисцировку. Для начала, число Бога уже давно найдено и равно 20. Правда задача сборки от этого не упрощается, т.к. использовать граф кратчайших путей для всех возможных конфигураций кубика не очень спортивно и немножко накладно по ресурсам. Алгоритм Бога предполагает под собой некое разумное количество использованной памяти, и в то же время обязан обеспечить минимально возможное число модификаций. Так вот, такого алгоритма еще нет. Есть ряд алгоритмов, позволяющих заметно ускорить сборку по сравнению с традиционными шаблонными методоми, но повторять кем-то уже проложенный (математически) путь мне показалось скучным. Если кому интересно, вот хороший анализ Далее есть традиционные шаблонные методы. Идея здесь в послойной сборке снизу вверх с использованием формул. Формула — последовательность модификаций Кубика, приводящая к таким-то целевым модификациям, и таким-то побочным. Соответственно, побочные модификации почти всегда падают на еще не собранные слои. Различаются шаблонные методы уровнем детализации шаблонов. Всякого рода спидкуберы знают все мыслимые шаблоны для большого количества частных случаев, что позволяет отыграть лишнюю 0.1 секунду с каждой модификации на соревнованиях. Пример, на что еще можно потратить жизнь.

Итак, я постепенно формировал для себя задачу. В итоге, формулируется она так: за кратчайшее реальное время необходимо написать решалку для Кубика Рубика.

Что мы знаем о Кубике? Число его состояний описывается как

(8! × 3^7) × (12! × 2^11)/2 = 43 252 003 274 489 856 000

.

последняя редакция статьи доступна на сайте makeloft.xyz

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

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

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


В последние несколько лет интенсивно развивается новое направлении в теории восстановления изображений — слепая обратная свертка (Blind Deconvolution). Появилось достаточно много работ по этой теме, и начинается активное коммерческое использование результатов.
Многие из вас помнят конференцию Adobe MAX 2011, на которой они как раз показали работу одного из алгоритмов Blind Deconvolution: Исправление смазанных фотографий в новой версии Photoshop
В этой статье я хочу подробнее рассказать — как же работает эта удивительная технология, а также показать практическую реализацию SmartDeblur, который теперь тоже имеет в своем распоряжении этот алгоритм.
Внимание, под катом много картинок!

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

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

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

Ниже показан результат обработки реального размытого изображения (не с синтетическим размытием). Исходное изображение было получено камерой Canon 500D с объективом EF 85mm/1.8. Фокусировка была выставлена вручную, чтобы получить размытие. Как видно, текст совершенно не читается, лишь угадывается диалоговое окно Windows 7.



И вот результат обработки:



Практически весь текст читается достаточно хорошо, хотя и появились некоторые характерные искажения.

Под катом подробное описание проблем деконволюции, способов их решения, а также множество примеров и сравнений. Осторожно, много картинок!

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

Почему же для устранения смаза и расфокусировки практически ничего нету (unsharp mask не в счет) – может быть это в принципе невозможно? На самом деле возможно – соответствующий математический аппарат начал разрабатываться примерно 70 лет назад, но, как и для многих других алгоритмов обработки изображений, все это нашло широкое применение только в недавнее время. Вот, в качестве демонстрации вау-эффекта, пара картинок:



Я не стал использовать замученную Лену, а нашел свою фотку Венеции. Правое изображение честно получено из левого, причем без использования ухищрений типа 48-битного формата (в этом случае будет 100% восстановление исходного изображения) – слева самый обычный PNG, размытый искусственно. Результат впечатляет… но на практике не все так просто. Под катом подробный обзор теории и практические результаты.
Осторожно, много картинок в формате PNG!

Я уже частично говорил о работе с FITS-файлами в Octave. Теперь расскажу о применении этого математического пакета для обработки конкретных данных, а именно: для вычисления центра вращения звездного поля по набору снимков, полученных с определенным интервалом.

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

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

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

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

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

Ввиду того, что база данных, построенная в посте, формировалась за некоторое время до публикации, а именно 26 апреля 2015 г., посты, опубликованные на Хабрахабре после этой даты (а также, возможно, новые хабы) в данном посте не рассматривались.

S3D: No pain IS gain

Эта статья — четвертая в цикле “Почему от 3D болит голова”. Раньше мы говорили про проблемы кинооборудования, был сделан краткий обзор проблем контента, и детально разобрана ситуация с, пожалуй, самой болезненной проблемой — перепутанными ракурсами. Продолжаем выполнять обещания и рассказывать подробнее про то, что было кратко проанонсировано ранее. Сегодня будут ответы на вопросы: Почему один и тот же фильм в кинотеатре трехмерен, а на телевизоре нет? В каких диапазонах вообще изменяется видимая глубина фильмов? Как изменяется в среднем видимая глубина фильмов по годам? Что можно сделать, если вы сидите в кинотеатре, фильм “плосковат”, а вы хотите большей видимой глубины? Можно вообще ли изменить видимую глубину и сделать “плоский” фильм “более трехмерным”? Ведь это так хочется! И, наконец, как “изменяют параллакс” телевизоры и плееры?

В процессе работы над диалоговой системой (http://habrahabr.ru/post/235763/) мы столкнулись с непреодолимой, на первый взгляд, проблемой – в реальных, боевых условиях работы, производительность системы ASR оказывалась значительно ниже ожидаемой. Одним из компонентов, сказывающимся на производительности, неизменно оказывался шум на заднем фоне, принимающий самые разнообразные формы. Особенно неприятными для ASR в наших экспериментах были трудно-нейтрализуемые шум городской улицы и шум массовых скоплений людей.

Стало ясно, что проблему придется решить, или реальной ценности от голосовой системы просто не будет.