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

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



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

Структура сети

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

В комментариях к статье Алгоритмическая неразрешимость – это не препятствие для алгоритмического ИИ я высказался, в свете того, что

Почему-то все зациклились на задачах NP. Но никто почему то не ставит задачи БЫСТРЕЕ решать задачи класса P (вплоть до мгновенного ответа)

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

В статье же говорилось о теоретической проблеме алгоритмической неразрешимости на примере задачи останова.

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

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

Но все по порядку.

Введение

Всем привет, пишу данный топик как логическое продолжение данной статьи о максимальном потоке минимальной стоимости, в конце которой был затронут алгоритм Дейксты. Соглашусь с автором, что описание и различные реализации алгоритма можно найти без проблем, и «колесо» я не изобретаю, но тем не менее опишу здесь практическую реализацию на языке C#. Кстати отмечу, что использую LINQ, так что для работы необходим NET 3.5.

UPDНаконец-то подчистил код :)

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

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

Начало

Данный код представляет реализацию алгоритма на взвешенном неориентированном графе. Рассмотрим реализацию этого алгоритма.
Объектами данного алгоритма являются три класса:
• Apoint – класс, реализующий вершину графа
• Rebro – класс, реализующий ребро графа
• DekstraAlgoritm – класс, реализующий алгоритм Дейкстры.
Рассмотрим подробнее данные классы и самые важные методы.
APoint
Данный класс содержит в себе 5 полей:
•public float ValueMetka { get; set; } данное поле отвечает за хранение значений метки данной вершины. В программе под бесконечностью берется очень большое число, например 99999.
•public string Name { get; set; } – имя метки. Данное поле необходимо лишь для выведения удобно читаемого результата.
•public bool IsChecked { get; set; } – означает помечена метка или нет
•public APoint predPoint { get; set; } – «предок» точки, т.е. та точка которая является предком текущей в кратчайшем маршруте.
•public object SomeObj { get; set; } – некий объект
Каких-либо значимых методов данный класс не содержит.
Rebro
Данный класс содержит 3 поля:
•public APoint FirstPoint { get; set; } – начальная вершина ребра
•public APoint SecondPoint { get; set; } – конечная вершина ребра
•public float Value { get; set; } – весовой коэффициент.
Каких-либо значимых методов данный класс не содержит.
DekstraAlgorim
Данный класс представляет собой граф и реализацию алгоритма Дейкстры. Содержит 2 поля:
•public APoint[] points { get; set; } – массив вершин
•public Rebro[] rebra { get; set; }- массив ребер
Таким образом, эти 2 массива отражают граф. Рассмотрим методы:
•private APoint GetAnotherUncheckedPoint()
Данный метод возвращает очередную неотмеченную вершину, наименее удаленную, согласно алгоритму.
•public void OneStep(APoint beginpoint)
Данный метод делает один шаг алгоритма для заданной точке.
•private IEnumerable Pred(APoint currpoint)
Данный метод ищет соседей для заданной точки и возвращает коллекцию точек.
•public string MinPath(APoint begin,APoint end)
Данный метод возвращает кратчайший путь, найденный в алгоритме от начальной точке до конечной. Этот метод используется для наглядного отображения пути
•public void AlgoritmRun(APoint beginp)
Данный метод запускает алгоритм и принимает в качестве входа начальную точку.
Все основные методы описаны, представим процесс работы алгоритма в целом на рис.1. Основной метод OneStep представлен на рисунке 2.

Рис.1. Работа алгоритма в целом

Рис.2. Работа метода OneStep

Код

Наконец, рассмотрим сам код. В каждом классе написал подробные комментарии.

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

Питер Стоун — доцент Техасского университета в Остине, специалист по искусственному интеллекту и многоагентным системам занимается моделированием дорожного движения с учетом широкого распространения автомобилей под управлением компьютера. Стоун считает, что машины-роботы способны сделать транспортную систему намного более эффективной. “Каждым перекрёстком — говорит Стоун — должен управлять автономный интеллектуальный агент, регулирующий режим движения каждого автомобиля индивидуально, а не светофор, запрещающий или разрешающий движение всего потока”.

Привет всем Хабражителям, кто интересуется вопросами искусственного интеллекта! Всех с Прошедшими праздниками! Пора двигаться дальше.

В конце прошлого года я закончил перевод последней версии документа о «Hierarchical Temporal Memory» (HTM), который теперь можно найти рядом с оригиналом на сайте Numenta.com.

Что это такое и зачем оно все? Это последняя разработка весьма небезысвестного Джеффа Хокинса сотоварищи, моделирующая работу отдельных слоев коры головного мозга. Эта штуковина позволяет (если не накосячить все сделать правильно) выделять из входного потока данных сходные события, их последовательности, проводить их распознавание и предсказание. Всех, кого интересуют подробности, милости прошу под хабракат.

В мае 2008 года мы обсуждали новую компьютерную игру Fold.it, которую разработали учёные из Вашингтонского университета (США). Программа представляет собой модель сворачивания белков в трёхмерные конструкции. Геймер должен попытаться сделать это наиболее удачным образом, работая с настоящими протеинами. Результаты отправляются в центр обработки, где их проверяют на суперкомпьютере.



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

Группа учёных под руководством Милана Стояновича (Milan Stojanovic) из Колумбийского университета сконструировали из молекулы ДНК четырёхногого робота, способного перемещаться самостоятельно по заданному маршруту. Во время опытов паукообразный механизм самостоятельно сделал около 50 шагов, переместившись на расстояние 100 нанометров (раньше ни один наноробот не мог сделать больше трёх шагов).



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

Привет, username!

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

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

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

Доброго времени суток, хабражители!
Мне очень нравятся барочные элементы. В очередной раз встретив подобный узор на одном из сайтов, представил, как бы он чудесно смотрелся в анимации, картинка бы ожила. Тем более с приходом html5 оживление должно стать гораздо проще в реализации. Но как по точкам нарисовать кривую? Тут как раз кстати вспомнилась кривая Безье!

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

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

Сервер IIS 7 и предыдущие версии содержали встроенную функциональность, которая позволяла администраторам разрешить или запретить доступ к серверу для определенных IP-адресов (или их диапазонов). Когда IP-адрес блокировался, любой HTTP-клиент с таким IP получал в ответ на запрос к серверу HTTP-ошибку "403.6 Forbidden". Этот функционал позволял администраторам настроить доступ к их серверу на основе активности, которую они могли проанализировать по логам сервера. Тем не менее, это был ручной процесс. Даже при том, что управление функциями могло настраиваться через скрипты для определения подозрительных пользователей с помощью анализа логов утилитами типа Microsoft's LogParser, все равно требовалось много ручной работы.

Решение

В IIS 8 встроенная функциональность была расширена для того, чтобы предложить следующие функции:

• Динамическая фильтрация IP-адресов, которая позволяет администраторам настроить их сервер на блокировку IP-адресов, которые создают слишком много запросов к серверу;
• Фильтрация IP-адресов теперь позволяет администраторам указать поведение сервера во время блокировки IP-адреса, так что запросы от злоумышленников могут быть прерваны сервером, вместо того, чтобы возвращать клиенту HTTP 403.6;
• Фильтрация по IP теперь поддерживает функцию прокси-режима, которая позволяет блокировать адреса не только по IP-адресу клиента, который получает сервер, но и по полученным значениям HTTP-заголовков x-forwarded-for.

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

Если вас интересует ответ на этот вопрос, альтернативная реализация на TypeScript и не пугает чтение кода, то прошу под кат.

На днях мистер Дуб принял мой первый pull request с примером в Three.js, и на радостях я решился написать о нём хабропост. Если вам вдруг захочется написать трёхмерный платформер на Three.js, но вы не особо представляете себе, как это сделать, этот пример — для вас:

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

Наверно многие в курсе, что у JS достаточно ограниченно реализовано ООП. Одних уровень ООП в JS устраивает, другие не видят необходимости придерживаться правил ООП, другие без ООП не могут писать код. Тут мы попробуем без холивара разобраться в некоторых ньансах перехода с JS на TS.

О мотивации перехода мы поговорим в заключении статьи и скорее для тех, кто понимает важность качества кода. Но пару слов все же скажем вначале. Когда Вы делаете небольшой тестовый код, с неясным коммерческим статусом — то вряд ли вы будите этот код прилизывать. А ООП это хороший способ прилизать код, это не сколько не влияет на функциональность вашего кода, даже наоборот, часто задерживает быстрое написание тех фич, которые вы решили сделать. Иногда даже страдает производительность. Но наверное каждый знает тот уровень, когда ему самому уже сложно разобраться в своем коде, тогда вы начинаете его просматривать и время от времени подумывать о рефакторинге. Если ваш язык интерпретируемый, без строгой типизации и не достаточно хорошо поддерживает ООП, то вы этот момент будет оттягивать долго — но я рекоммендую все же об этом задуматься. Если ваш язык JS — хорошим вариантом будет его перевести на TS, вы ничего не потяряете это уж точно. Но есть некоторые сложности, из-за которых в процессе перевода вы можете засомневаться в правильности такого решения.

Изометрия — вещь, стара как компьютерные игры.
Сейчас пришло время, когда интернет и игры стали совмещаться в браузере (flash не в счет).
Примеров браузерных игр много, большая часть из них казуалки, но для гиков более интересны жанры action, RTS и RPG, а для разработчиков — их реализация.



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

Под катом я расскажу:

1. Как рисовать изометрическую матрицу
2. Как нарисовать fullscreen изометрическую матрицу

Это совсем краткий пост о причинах возникновения Deadlock

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

«Deadlock found when trying to get lock; try restarting transaction»

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

Друзья, ничего умнее этого заголовка не придумал, так что небольшая предыстория.
Как и все программисты, я не мог не услышать про новый язык Swift, на который тут же посыпались разнообразные «хелловорлды»-обучалки. Однако, простые с виду приложения создаются (на мой WPF-ный взгляд) как-то уж слишком сложно даже после введения «упрощённого» языка. Это действительно необходимая сложность или их можно создавать как-то попроще? Наткнулся на вот такой пример iOS-приложения (что-то вроде браузера приложений в аппсторе) и решил создать его полный аналог на «родном» WPF'е. Цель — сравнить сложность разработки и возможно кто-то поделится более простым методом для iOS (если он есть). Обилия скринов не будет, зато кода — … да и его, в общем-то, кот наплакал. Итак,