Алгоритмы *

Пару месяцев назад я рассказывал о приближенных результатах в задаче о сворачивании РНК. Напомню требуется свернуть вироидный рибозим NC_003540 организма Chrysanthemum chlorotic mottle viroid, третичная структура которого неизвестна.

И вот оно свершилось — рибозим свернулся ! (В нем образованы все имеющиеся водородные связи)

Смотрим его конечное состояние, а под катом еще его траекторию сворачивания, а также подводим итоги.

Вместо вступления

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

Введение

Обычно данный материал приводится с обилием формул и рассчитан больше на математиков. Я постараюсь расписать его наиболее доступно на простых численных примерах с точки зрения применения этого метода в микроэлектронике на аппаратном уровне. В численных примерах для наглядности будет использоваться значение p = 11.

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

Положим, что нам требуется выполнить умножение следующего вида: res = (a*b) mod p, где
0 <= a < p
0 <= b < p
p – простое число.
mod p – операция нахождения остатка по модулю.
И выполнить его надо на низком уровне, где нет как таковой операции умножения и операции взятия остатка от деления или же они реализуются достаточно сложно (например, в электронном устройстве).

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

Например, год назад калифорнийский город Санта-Крус первым в мире внедрил математическую модель расчёта вероятности преступлений, которая каждый день составляет новый маршрут для патрульных машин, основываясь на статистике преступлений по улицам. Учитываются день недели, время суток, наличие/отсутствие футбольных матчей по ТВ и другие факторы.

Исследователь из Бирмингемского университета Мирко Мусолези (Mirco Musolesi) применил совершенно другой подход. Его метод основан не на статистике, а на оперативных данных из сетей сотовой связи. Мусолези начал с того, что научил алгоритм с высокой степенью вероятности прогнозировать перемещения каждого абонента: он даже выиграл конкурс Nokia Mobile Data, наиболее точно предсказав перемещения 25-ти добровольцев по сигналам их телефонов, истории звонков и текстовым сообщениям. Иногда алгоритм прогнозирует координаты пользователя с точностью до 20 м².

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

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

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

Это перевод и форма повествования от первого лица сохранена. Автор — Бен Бойтер, бакалавр информационных технологий в Университете Чарльза Стерта (CSU).


Большинство людей не в курсе, но моей диссертацией была программа для чтения текста с изображения. Я думал, что, если смогу получить высокий уровень распознавания, то это можно будет использовать для улучшения результатов поиска. Мой отличный советник доктор Гао Джунбин предложил мне написать диссертацию на эту тему. Наконец-то я нашел время написать эту статью и здесь я постараюсь рассказать о всем том, что узнал. Если бы только было что-то подобное, когда я только начинал…

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

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

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

Пока я тут излагал мысль она несколько растеклась по статьям

1. Модель функционального разделения сознания и бессознательного. Введение
2. Модель проявления сознания или ИНС без эффекта забывания
3. Проблема «двух и более учителей». Первые штрихи
4. Обучение с подкреплением на нейронных сетях. Теория

казалось аудитория имеет нужные знания, все таки у нас цвет общества — программисты :) Но увы… последний опрос показал, что далеко не все программисты в курсе ИИ-проблематики. А хамоватые студенты набежавшие на эти статьи в комментариях — еще не доучились.

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

Недавно на хабре появилась неплохая статья про вычисление N-ного числа фибоначи за O(log N) арифметических операций. Разумный вопрос, всплывший в комментариях, был: «зачем это может пригодиться на практике». Само по себе вычисление N-ого числа фибоначи может и не очень интересно, однако подход с матрицами, использованный в статье, на практике может применяться для гораздо более широкого круга задач.

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

loop 1000000000
  loop 1000000000
    loop 1000000000
      a += 1
      b += a
    end
  end
end
end

Незамедлительно выведет a = 1000000000000000000000000000, b = 500000000000000000000000000500000000000000000000000000, несмотря на то, что если бы программа выполнялась наивно, интерпретатору необходимо было бы выполнить октиллион операций.

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

Так мне указали, что для задачи классификации — нейронные сети (обучение с учителем), генетические алгоритмы (обучение без учителя) — задача кластеризации, а еще есть обучение с подкреплением (Q-обучение) — как задача агента, который бродит и что-то делает. И вот такими шаблонами многие и судят.

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

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

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

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

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

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

В комментариях к статьям N-е число Фибоначчи за O(log N) и Еще один алгоритм вычисления чисел Фибоначчи указывалось на тот факт, что уже 100-е число Фибоначчи не помещается в 4 байта, а в «длинной» арифметике скорость выполнения умножения резко просядет. Более того, были предположения, что примитивное сложение может оказаться быстрее. Я решил сравнить 2 алгоритма — простое сложение и алгоритм с логарифмическим количеством операций — и написал тестовую программу на С. Для «длинной» арифметики использовал библиотеку GMP.

Перед прочтением статьи, решил попробовать придумать свой алгоритм c асимптотикой O(log N). Времени понадобилось не очень много. Ниже описание идеи и пример на С++.

Читая статью об устройстве на работу в ABBYY, встретил в ней упоминание задачи:

быстро – за O( log N ) арифметических операций над числами – найти N-е число Фибоначчи

Я задумался над ней и понял, что сходу в голову приходят только решения, работающие за время O(N). Однако позже решение было найдено.

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

PyBrain — одна из лучших Python библиотек для изучения и реализации большого количества разнообразных алгоритмов связанных с нейронными сетями. Являет собой удачный пример совмещения компактного синтаксиса Python с хорошей реализацией большого набора различных алгоритмов из области машинного интеллекта.

Предназначен для:

• Исследователей — предоставляет единообразную среду для реализации различных алгоритмов, избавляя от потребности в использовании десятков различных библиотек. Позволяет сосредоточится на самом алгоритме а не особенностях его реализации.
• Студентов — с использованием PyBrain удобно реализовать домашнее задание, курсовой проект или вычисления в дипломной работе. Гибкость архитектуры позволяет удобно реализовывать разнообразные сложные методы, структуры и топологии.
• Лекторов — обучение методам Machine Learning было одной из основных целей при создании библиотеки. Авторы будут рады, если результаты их труда помогут в подготовке грамотных студентов и специалистов.
• Разработчиков — проект Open Source, поэтому новым разработчикам всегда рады.

Делаю тут проект и возникла вот какая проблема. Получаю данные с АЦП (дельта-сигма) микросхемы в которую встроен контроллер и фильтр, но этот фильтр имеет довольно убогую АЧХ, в итоге идёт завал по ВЧ от 60Гц и далее. Выглядит это примерно так:


Т.е. такая неравномерность АЧХ нас явно не устраивает (не проходит по техническим требованиям), правда есть возможность повысить частоту дискретизации с 250Гц до 500Гц, чтобы выровнять АЧХ, однако тогда увеличивается объём данных который ещё нужно будет усреднять, что скажется на производительности (проект на STM32F103VE) системы в целом и на общем потреблении энергии (батарейное питание). Но есть и другой путь.

Вступление

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

Начнем с взаимного расположения точки относительно прямой, луча и отрезка.

Что будет, если генератор случайных фигур соединить с детектором лиц? Способен ли эволюционный алгоритм путём случайных мутаций сгенерировать человеческое лицо? Разработчик программы Pareidoloop отвечает на этот вопрос утвердительно (генератор протестирован только в Chrome 21).


^{(с) spiritedflow}

Здравствуйте, Хабравчане! Я бы хотел посвятить эту статью интересным и забавным задачам по информатике и математике.

Немного истории

Я являюсь студентом 4 курса математического факультета. Скажу Вам — я очень горжусь, что буду как математиком, так и программистом. Как сказал мне мой декан-программист:«Без математики — это программист с потолком». Так вот, каждый год на протяжении 7 лет мой вуз, а точнее факультет проводит открытую олимпиаду по математике и информатике, за что ему огромное спасибо. Принять в олимпиаде участия могут все: от школьников до студентов (вообще, главное собрать команду хоть из своих соседей).