Алгоритмы *

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



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

В этой публикации я расскажу о том, как можно находить похожие документы с помощью MinHash + Locality Sensitive Hashing. Описание LHS и Minhash в «Википедии» изобилует ужасающим количеством формул. На самом деле все довольно просто.

Привет!

29 июля, в очередной, уже седьмой раз, в Санкт-Петербурге откроется ежегодная Летняя школа Microsoft Research. На этот раз тема школы – машинное обучение и интеллект. В программу школы включены лекции и семинары ученых мирового уровня из ведущих университетов со всего мира, в том числе из России, а также исследователей Microsoft Research. Руководитель школы – Эвелин Виегас, директор направления «семантические вычисления» Microsoft Research Redmond. Подробности под катом.

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

История компьютерных наук в целом сводится к тому, что учёные пытаются понять, как работает человеческий мозг, и воссоздать нечто аналогичное по своим возможностям. Как именно учёные его исследуют? Представим, что в XXI веке на Землю прилетают инопланетяне, никогда не видевшие привычных нам компьютеров, и пытаются исследовать устройство такого компьютера. Скорее всего, они начнут с измерения напряжений на проводниках, и обнаружат, что данные передаются в двоичном виде: точное значение напряжения не важно, важно только его наличие либо отсутствие. Затем, возможно, они поймут, что все электронные схемы составлены из одинаковых «логических вентилей», у которых есть вход и выход, и сигнал внутри схемы всегда передаётся в одном направлении. Если инопланетяне достаточно сообразительные, то они смогут разобраться, как работают комбинационные схемы — одних их достаточно, чтобы построить сравнительно сложные вычислительные устройства. Может быть, инопланетяне разгадают роль тактового сигнала и обратной связи; но вряд ли они смогут, изучая современный процессор, распознать в нём фон-неймановскую архитектуру с общей памятью, счётчиком команд, набором регистров и т.п. Дело в том, что по итогам сорока лет погони за производительностью в процессорах появилась целая иерархия «памятей» с хитроумными протоколами синхронизации между ними; несколько параллельных конвейеров, снабжённых предсказателями переходов, так что понятие «счётчика команд» фактически теряет смысл; с каждой командой связано собственное содержимое регистров, и т.д. Для реализации микропроцессора достаточно нескольких тысяч транзисторов; чтобы его производительность достигла привычного нам уровня, требуются сотни миллионов. Смысл этого примера в том, что для ответа на вопрос «как работает компьютер?» не нужно разбираться в работе сотен миллионов транзисторов: они лишь заслоняют собой простую идею, лежащую в основе архитектуры наших ЭВМ.

Моделирование нейронов

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



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

Подъем, овощи!

Все, кто еще не, срочно идем и регистрируемся на курс CS188.1x — «Artificial Intelligence». Курс стартовал 6.2.2015 и уже доступны материалы второй недели (первая проходится за три часа — она вводная). Оправдание принимается только одно — «не понимаю по-английски». В этом случае идешь и начинаешь учить английский!

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

Начитавшись статей про [все что угодно] на JavaScript в 30 строк кода, я подумал: чем я хуже? Не найдя в перечне своих недостатков пункт «написание плохого кода», решил сделать что-нибудь интересное.

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

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

Для сторонников принципа «меньше знаешь — крепче спишь» предлагается cсылка на JSFiddle (управление стрелочками).

     Ранее на Хабре была опубликована работа автора об инварианте числа (здесь). Еще ранее в работе [1] приводятся сведения об оригинальной концепции моделирования натурального ряда чисел и отдельного числа с целью установления свойств, слабо зависящих или вообще не зависящих от разрядности чисел. Ранее не приводились теоремы для доказательства истинности положений, которые используются автором в работах. Анализ комментариев к работам показал насколько недоверчиво читательская аудитория относится к подобным работам и утверждениям.

Рекомендательные (они же рекомендационные) системы уже около 20 лет используются в e-commerce. Самые успешные примеры мы можем видеть у гигантов Amazon и Taobao. Но как же быть с offline ритейлом? Применимы ли к нему эти существующие рекомендательные системы? И есть ли альтернатива?

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

Нестандартное решение нашлось сразу — старый, добрый и проверенный алгоритм Apriori. Хотите узнать как использовать парный анализ по-новому? Добро пожаловать под кат.

Мотивации пост.



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

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

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

Аннотация
Люди — это самые важные объекты слежения в системах видеонаблюдения. Тем не менее, слежение за человеком само по себе не дает достаточной информации об его мотивах, намерениях, желаниях и т.п. В этой работе мы представляем новую и надежную систему для автоматической оценки возраста с помощью технологий компьютерного зрения. Она использует глобальные особенности лица, полученные на основе комбинирования вейвлетов Габора и сохранение ортогональности локальных проекций Orthogonal Locality Preserving Projections, OLPP). Кроме того, система способна оценивать возраст по изображениям в реальном времени. Это означает, что предлагаемая система имеет больший потенциал по сравнению с другими полуавтоматическими системами. Результаты, полученные в процессе применения предлагаемого подхода, могут позволить получить более ясное понимание алгоритмов в области оценки возраста, необходимых для разработки приложений, актуальных для реального применения.
Ключевые слова: вейвлеты Габора, изображение лица, оценка возраста, метод опорных векторов (Support Vector Machine, SVM).

Однажды я писал на Хабр про различные технологии получения 3D изображения с одной камеры. Заканчивал я ту статью словами: «Сам я, правда, до сих пор не сталкивался ни с одной из этих камер, что жалко и досадно».
И вот, внезапно, не прошло и года, Intel проводит в Москве семинар и хакатон по новому поколению своих 3D камер (Intel RealSense). Любопытство взыграло: мы с коллегой записались на мероприятие. Как выяснилось, не зря. Хакатон мы выиграли и получили Developer-версию камеры, которую теперь мучаем.



В статье рассказывается о двух вещах:

1. Про камеру, её плюсы и недостатки; что с помощью нее можно сделать, а для каких задач она не годится.
2. Про концепцию, которую мы предложили на хакатоне и за которую получили первое место.

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

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

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

Всем привет! Меня зовут Сергей Макеев, и я технический директор в проекте Skyforge в команде Allods Team, игровой студии Mail.Ru Group. Мне хотелось бы рассказать про технологии рендеринга, которые мы используем для создания графики в Skyforge. Расскажу немного о задачах, которые стояли перед нами при разработке Skyforge с точки зрения программиста. У нас свой собственный движок. Разрабатывать свою технологию дорого и сложно, но дело в том, что на момент запуска игры (три года назад) не было технологии, которая могла бы удовлетворить всем нашим запросам. И нам пришлось самим создать движок с нуля.

Перевод поста Майкла Тротта (Michael Trott), «Constructing Crossword Arrays Faster».
Скачать перевод в виде документа Mathematica, который содержит весь код использованный в статье, можно здесь.

В главе 6 моей книги Mathematica GuideBook for Programming, в качестве примера работы со списками я обсудил то, как построить массив, представляющий собой кроссворд. Хотя этот пример был хорош для демонстрации продвинутой работы со списками, тем не менее, использование списков не является оптимальным путем построения массива кроссворда. Сложность добавления нового слова в массив с уже размещенными n-1 словами составляла для этого алгоритма , таким образом общая сложность составления массива кроссворда из n слов становилась равной .

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

Привет, Хабр!

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

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

1) Этот генератор не претендует на реалистичность, и писал я его для того, чтобы сгенерировать уникальные текстуры для сотни маленьких шариков, которые занимают 10% экрана и к тому же прикрыты облаками.
2) Чисто технический момент: я пишу на C# под Unity3d, так что думать о том, как выводить в изображение с приемлимой скоростью вам придется самим, для каждого языка и платформы свои способы.

В мае прошлого года сотрудники лаборатории глубокого обучения Гугла и учёные из двух американских университетов опубликовали исследование «Intriguing properties of neural networks». Статья о нём вольно пересказывалась здесь на Хабре, и само исследование также критиковалось специалистом из ABBYY.

Гугловцы в результате своих исследований разочаровались в способностях нейронов сети распутывать признаки входных данных и стали склоняться к мысли, что нейронные сети не распутывают семантически значимые признаки по отдельным структурным элементам, а хранят их во всей сети в целом как в голограмме. В нижней части иллюстрации к этой статье чёрно-белыми я привёл карты активации 29, 31 и 33-его нейронов сети, которую обучил рисовать картинку. То, что тушка птицы без головы и крыльев, изображаемая для примера 29-ым нейроном, покажется людям семантически значимым признаком гугловцы считают всего лишь ошибкой интерпретации наблюдателя.

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

Задача Datawiz.io: провести кластеризацию клиентов программы лояльности в ритейле.

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

Целью кластеризации является получение новых знаний. Это как “найти клад в собственном подвале”.

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