Рубрика «Алгоритмы» - 235

Привет! Сегодня я хочу обзорно пройтись по нескольким задачам времен рассвета информатики aka Сomputer Science, которые относятся к неразрешимым.

Что такое неразрешимая задача? Наверное, стоило бы начать с иерархии Хомского — регулярные, контекстно-свободные, контекстно-зависимые, рекурсивно-перечислимые языки, — а уже потом перейти к тому, что лежит за её пределами, но, честно, это не слишком весело. Я не буду давать ни формальных определений, ни доказательств. У вас не получится поддержать научный диспут, но ввернуть умную фразу в компании — вполне. Если вас это устраивает — прошу под кат.
Читать полностью »

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

Эта статья является продолжением в цикле статей по модели квантовых вычислений, поэтому если начать читать её без ознакомления с предыдущими статьями цикла, что-то может показаться непонятным. Так что читателя, который впервые набрёл на эти мои заметки, я отправляю к первым статьям: 1, 2, 3, 4, 5.

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

Читать полностью »

Цели:

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

Задачи:

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

Введение

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

1. Алгоритмы распознавания человеческого лица:

1.1 Алгоритмы, основанные на деформируемой модели.

Деформируемая модель (deformable template model) – это шаблон некоторой формы (для двумерного случая — открытая либо замкнутая кривая, для трехмерного — поверхность). Наложенный на изображение, шаблон деформируется под воздействием различных сил, внутренних (определенных для каждого конкретного шаблона) и внешних (определенных изображением, на которое наложен шаблон) — модель меняет свою форму, подстраиваясь под входные данные [1]. Исходная грубая модель губ деформируется под действием силовых полей, заданных входным изображением (Рис.1).
image
Основное преимущество над традиционными методами поиска, такими как преобразование Хафа (Hough transform [2]), в которых шаблон для поиска задается жестко, заключается в том, что деформируемые модели в процессе работы могут менять свою форму, позволяя более гибко осуществлять поиск объекта [3].

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

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

Цели

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

Задачи:

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

Тема

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

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

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

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

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

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

image

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

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

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

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

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

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

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

Всем доброго времени суток!

В этом небольшом посте я продолжу тему, которую поднимал в своих старых двух постах
Часть 1
Часть 2

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

Так что добро пожаловать под хабракат
Читать полностью »

Всё, дождался!

Меня взяли учиться в Computer Science Center. Чуть больше месяца я провел в напряженном состоянии ожидания, каждый день с надеждой просматривая почту. И вчера я наконец получил заветное письмо. Чертовски радостная весть и очень нужная.

Про CSC я узнал довольно давно, пару лет назад точно. Тогда еще мои мысли были тесно связаны с Академическим Университетом, и я даже попытался поступить туда в магистратуру, но мимо. Мыслей поступить в центр почему-то у меня тогда не возникло. Ну да ладно.
В этом году я созрел. Причем довольно рано (как мне казалось): набор должны были открыть в апреле, а я начал обдумывать это дело где-то в феврале. Посмотрев по диагонали примеры вступительных заданий и посчитав, что месяца мне вполне хватит на подготовку — забыл про это всё и сконцентировался на подаче заявки на участие в GSoC 2014. Туда не попал и тут же вспомнил про CSC. Вспомнил, как оказалось, несколько позновато.
Читать полностью »

Автоматическое выравнивание кода

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

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

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

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

Читать полностью »

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

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


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js