Алгоритмы *

Содержание:

1. Поиск и анализ цветового пространства оптимального для построения выделяющихся объектов на заданном классе изображений
2. Определение доминирующих признаков классификации и разработка математической модели изображений мимики"
3. Синтез оптимального алгоритма распознавания мимики
4. Реализация и апробация алгоритма распознавания мимики
5. Создание тестовой базы данных изображений губ пользователей в различных состояниях для увеличения точности работы системы
6. Поиск оптимальной аудио-системы распознавания речи на базе открытого исходного кода
7. Поиск оптимальной системы аудио распознавания речи с закрытым исходным кодом, но имеющими открытые API, для возможности интеграции
8. Эксперимент интеграции видео расширения в систему аудио-распознавания речи с протоколом испытаний

Цели

Определить наиболее оптимальный алгоритм для последующей его реализации и апробации в решении распознавания мимики.

Задачи

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

Тема

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

• Низкое разрешение и высокий уровень шумов (характерно для большинства фронтальных VGA камер смартфонов и ПК);
• Невысокие производительные требования мобильных устройств и компьютеров для обсчитывания данных с частотой 25 кадров в секунду;
• Высокая скорость работы (для обработки видео в режиме онлайн).

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

Представим схему работы обработки и последующего анализа изображения в виде таблицы (рис.1). При этом на данном этапе исследования нам следует определить столбец, который мы для простоты перекрасили в синий цвет – то есть выбрать оптимальный алгоритм распознавания матрицы:



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

Это перевод моей публикации на английском языке.

Интернет полон статьями, заметками, блогами и успешными историями применения машинного обучения (machine learning, ML) для решения практических задач. Кто-то использует его для пользы и просто поднять настроение, как эта картинка:



Правда, человеку, не являющемуся экспертом в этих областях, подчас не так просто подобраться к существующему инструментарию. Есть, безусловно, хорошие и относительно быстрые пути к практическому машинному обучению, например, Python-библиотека scikit. Кстати, этот проект содержит код, написанный в команде SkyNet (автору довелось быть её лидирующим участником) и иллюстрирующий простоту взаимодействия с библиотекой. Если вы Java разработчик, есть пара хороших инструментов: Weka и Apache Mahout. Обе библиотеки универсальны с точки зрения применимости к конкретной задаче: от рекомендательных систем до классификации текстов. Существует инструментарий и более заточенный под текстовое машинное обучение: Mallet и набор библиотек Stanford. Есть и менее известные библиотеки, как Java-ML.

В этом посте мы сфокусируемся на библиотеке Weka и сделаем проект-заготовку или проект-шаблон для текстового машинного обучения на конкретном примере: задача распознавания тональности или сентимента (sentiment analysis, sentiment detection). Несмотря на всё это, проект полностью рабочий и даже под commercial-friendly лицензией (сама Weka под GPL 3.0), т.е. при большом желании вы можете даже применить код в своих проектах.

Несмотря на огромную популярность аппарата графических моделей для решения задачи структурной классификации, задача настройки их параметров по обучающей выборке долгое время оставалась открытой. В своем докладе Дмитрий Ветров, рассказал об обобщении метода опорных векторов и некоторых особенностях его применения для настройки параметров графических моделей. Дмитрий – руководитель группы Байесовских методов, доцент ВМК МГУ и преподаватель в ШАДе.

Видеозапись доклада.

План доклада:

• Байесовские методы в машинном обучении.
• Задачи с взаимозависимыми скрытыми переменными.
• Вероятностные графические модели
• Метод опорных векторов и его обобщение для настройки параметров графических моделей.

Сама концепция машинного обучения довольно несложная – это, если говорить образно, поиск взаимосвязей в данных. Данные представляются в классической постановке набором объектов, взятых из одной и той же генеральной совокупности, у каждого объекта есть наблюдаемые переменные, есть скрытые переменные. Наблюдаемые переменные (дальше будем их обозначать X) часто называются признаками, соответственно, скрытые переменные (T) — это те, которые подлежат определению. Для того, чтобы эту взаимосвязь между наблюдаемыми и скрытыми переменными установить, предполагается, что у нас есть обучающая выборка, т.е. набор объектов, для которых известны и наблюдаемые и скрытые компоненты. Глядя на нее, мы пытаемся настроить некоторые решающие правила, которые нам позволят в дальнейшем, когда мы видим набор признаков, оценить скрытые компоненты. Процедура обучения приблизительно выглядит следующим образом: фиксируется множество допустимых решающих правил, которые как правило задаются с помощью весов (W), а дальше каким-то образом в ходе обучения эти веса настраиваются. Тут же с неизбежностью возникает проблема переобучения, если у нас слишком богатое семейство допустимых решающих правил, то в процессе обучения мы легко можем выйти на случай, когда для обучающей выборки мы прекрасно прогнозируем ее скрытую компоненту, а вот для новых объектов прогноз оказывается плохой. Исследователями в области машинного обучения было потрачено немало лет и усилий для того, чтобы эту проблему снять с повестки дня. В настоящее время, кажется, что худо-бедно это удалось.

Доброго времени суток.

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

• Подсветка синтаксиса
• Использование отступов
• Вертикальное выравнивание

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

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

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

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

Привет, Хабр! Мой сегодняшний пост по программированию графики будет не таким объемным, как предыдущие. Почти в любом сложном деле иногда есть место несерьезному, и сегодня мы будем рендерить котиков. Точнее я хочу рассказать о реализации алгоритма рендеринга меха Shells and Fins (SAF) традиционно для Direct3D 11 и OpenGL 4. За подробностями прошу под кат.

Итак, у Вас есть какой-то поток данных. Большой такой поток. Или уже готовый набор. И хочется определить какие-то его характеристики. Алгоритм определения минимального и максимального значения могут придумать даже не программисты. Вычисление среднего уже чуть сложнее, но тоже не представляет никаких трудностей — знай подсчитывай себе сумму да инкрементируй счетчик на каждое новое значение. Среднеквадратичное отклонение — все то же самое, только числа другие. А как насчет медианы?

Для тех, кто забыл, что это такое, напоминаю — медиана (50-й перцентиль) выборки данных — это такое значение, которое делит эту выборку пополам — данные из одной половины имеют значение не меньше медианы, а из второй — не больше. Ценность её заключается в том, что её значение не зависит от величины случайных всплесков, которые могут очень сильно повлиять на среднее.

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

Есть такая интересная задача — построение 3D структуры по набору изображений (фотографий) — Structure from Motion. Как её можно решить? После некоторых размышлений приходит на ум такой алгоритм. Найдём на всех изображениях характерные особенности (точки), сопоставим их друг с другом и триангуляцией найдём их трёхмерные координаты. Тут правда есть проблема — неизвестно положение камер при съёмке. Можно ли их найти? Вроде можно. Действительно, пусть у нас N точек на кадре и M кадров. Тогда неизвестных будет 3 * N (трёхмерные координаты точек) + 6 * (M — 1) (координаты камер (вместо 6 может стоять другое число, но сути это не меняет)). Уравнений же у нас 2 * M * N (у каждой точки на каждом изображении есть две координаты). Выходит, что уже для двух изображений и 6 точек задачка разрешима. Под катом описание принципиальной схемы решения задачи SfM (по возможности без формул — но со ссылками для вдумчивого изучения).

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

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

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

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

Играл я только в World of Tanks (и то давно забросил, так и не докачавшись до 10 уровня) поэтому и решил все провернуть именно с танками. Сразу скажу, вся разработка, за исключением отладки производилась на linux, код выполняемый на ПК написан на питоне. Да он медленный и код показывать мне стыдно, поэтому обойдемся без него.

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

Помните эти задачи «при помощи циркуля и линейки постройте...»? Вот здесь можно поупражняться в таких построениях.

20 уровней построены по принципу «от простого к сложному». Предыдущие достижения (к примеру, умение строить равносторонний треугольник) на следующих уровнях доступны уже в виде инструментов.

Прошёл всё, правда на последнем уровне пришлось немного повозиться с касательными к окружностям.

Аннотация

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

Предыстория

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

Специалист по дата-майнингу и визуализации данных Майк Босток (Mike Bostock) опубликовал великолепную подборку с визуализацией различных алгоритмов.

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

Проще говоря, зрение помогает нам думать.

Число Бейкона

Немного истории, Кевин Бейкон американский актёр сыгравший во множествах фильмам, в 1994 отметил что актёры, с которыми он снимался, работали со всеми голливудскими (и не только) актёрами. Общественность тут же отреагировала и создала игру “назвать имя актёра и связать его с Кевином Бейконом”. Корпорация добра даже встроила игру в свой поисковик, например Число Бейкона для актёра Джона Траволты равно 2 (Джон снимался с Оливией Ньютон-Джон в фильме Бриолин, она же, в свою очередь, сыграла с Кевином Бейконом в фильме “У нее будет ребенок”).

А теперь давайте поговорим о том, как эту игру можно представить, и как можно вычислить число Бейкона при помощи графа.

Гипотетически предположим, что вы сумели доказать равенство P=NP. Что же теперь нужно сделать для обретения господства над целым миром?

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

        Принцип работы этих алгоритмов похож: мы анализируем реакцию пользователей (feedback) на предыдущие записи и пытаемся прогнозировать его реакцию на текущие события. Если реакция «положительная», событие попадает в ленту, если «отрицательная» — не попадает.

Один хороший человек захотел сделать электронную книгу под iOS, коллекцию афоризмов. Фразы вылетают случайно, данные предоставлены в формате комма сепарейтед валью. С флешкой и устным ТЗ он пришел к другу-программисту. Программист оценил примерный объем работы

• Конвертируем данные в sqlite;
• Заводим три UIView (левый, правый и центральный);
• В каждый UIView добавляем UITextView и UILabel;
• Обрабатываем нажатие touchesBegin для листания афоризмов вправо-влево;
• Добавляем кнопку — показать случайный афоризм.
• Добавляем закладки.
• Получаем 1000 долларов США

Работы на 2 дня, программист согласился.
Однако в ТЗ было еще одно условие — при случайном выборе афоризма по экрану должен кататься игральный кубик. Самый обыкновенный, из шести граней.