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

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

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

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

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

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

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

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

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

В прошлой статье мы подробно описали алгоритм распознавания номеров (ссылка), который заключается в получении текстового представления на заранее подготовленном изображении, содержащем рамку с номером + небольшие отступы для удобства распознавания. Мы лишь вскользь упомянули, что для выделения областей, где содержатся номера, использовался метод Виолы-Джонса. Данный метод уже описывался на хабре (ссылка, ссылка, ссылка, ссылка). Сегодня мы проиллюстрируем наглядно то, как он работает и коснёмся ранее необсужденных аспектов + в качестве бонуса будет показано, как подготовить вырезанные картинки с номерами на платформе iOS для последующего получения уже текстового представления номера.

Статья рассчитана на людей, которые знакомятся со средой Visual Studio и пытаются компилировать в ней свои Си++-проекты. В незнакомой среде всё кажется странным и непонятным. Особенно новичков раздражает файл stdafx.h, из-за которого возникают странные ошибки во время компиляции. Очень часто всё заканчивается тем, что новичок долгое время везде старательно отключает Precompiled Headers. Чтобы помочь людям разобраться что к чему, и была написана эта статья.

Эта статья — краткий пересказ невероятно интересного доклада Скотта Майерса для тех, у кого нет 70 минут на весь доклад, но есть 7 минут на основные тезисы.

Некоторые люди, которые не пишут на С++, а лишь слышали об этом языке, задаются вопросом: «Почему вообще кто-то пишет на C++?». Но есть люди, которые используют С++ каждый день, и вот эти люди задаются вопросом: «А действительно, почему я пишу на этом языке?».

Но ведь действительно, должна быть какая-то причина, по которой люди пишут программы на С++. Давайте вернемся в начало 90-ых, когда проходила стандартизация С++. Была предложена масса идей. Предложений было столько и они были настолько разные, что мне запомнилась цитата Джима Вальдо, который тогда работал в комитете по стандартизации: «Каждый, предлагающий добавить что-то в С++ должен приложить к заявке свою почку. Тогда никто не предложит больше двух идей, а к выбору этих двух он подойдёт невероятно ответственно.»

Язык, который был бы получен в результате принятия всех предложений, выходил слишком сложным и тогда Бьёрн Страуструп сказал «А помните Ваза?». Никто, кроме людей из Швеции, не понял о чём речь. Ваза был огромным боевым кораблём, построенным в Швеции в 1625 году. Основным принципом постройки корабля было «А почему бы нам не добавить сюда ещё и вот такую фичу?». Многие из идей исходили непосредственно от короля, в частности он лично утверждал размеры корабля. Также на Ваза по указаниям свыше требовалось нацепить огромное количество элементов украшения, резьбы, большое количество пушек и т.д. А королю ведь не откажешь. Итог был закономерным — из-за ошибок в конструировании Ваза затонул в первом же рейсе, едва выйдя из бухты.

В очередном обзоре наиболее интересных материалов, посвященных теме анализа данных и машинного обучения, достаточно большое внимание уделено популярному набору алгоритмов машинного обучения Deep Learning и его практическому применению. Несколько статей посвящено тому какие есть пути для собственного развития как специалиста по анализу данных и машинному обучению. Также несколько статей касаются такой темы как Data Engineering и рассматривают такие популярные продукты как Cassandra и Apache Kafka. Но начинается данный выпуск с обзора стартующих в ближайшее онлайн-курсов, связанных с темой анализа данных и машинного обучения.

Читая главу «Двоичные деревья» из книги Джона Монгана Programming Interviews Exposed я задумался о том, как чаще всего рекурсию объясняют начинающим программистам: через сортировку, обход двоичного дерева, построение последовательности Фибоначчи и т.д. Неужели нельзя найти пример поинтереснее? Из закоулков сознания вырвался Лисп, который по своей природе неотделим от понятия рекурсии. Более того, небольшой интерпретатор Лиспа — отличный пример для исследования рекурсии.

Каким же будет минимальный интерпретатор Лиспа, написанный на Питоне? К моему удивлению, решение уложилось в семь строк! Свою роль в этом сыграла как выразительность Питона, так и красота и незамысловатость Лиспа.

Введение

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

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

Отметим, что приводимые подходы применимы не только к текстам, а вообще к любым объектам, которые можно представить в виде символьных последовательностей, например, какие-нибудь макромолекулы (ДНК, РНК, протеины) из генетики. Всего мы рассмотрим 4 метода:

1. Признаковое описание.
2. Попарное наложение (выравнивание) текстов.
3. Формирование профиля и скрытой марковской модели.
4. Представление фрагментами.

Итак, приступим.

«В 1997 году Deep Blue обыграл в шахматы Каспарова.
В 2011 Watson обставил чемпионов Jeopardy.
Сможет ли ваш алгоритм в 2013 году отличить Бобика от Пушистика?»

Эта картинка и предисловие — из челленджа на Kaggle, который проходил осенью прошлого года. Забегая вперед, на последний вопрос вполне можно ответить «да» — десятка лидеров справилась с заданием на 98.8%, что на удивление впечатляет.

И все-таки — откуда вообще берется такая постановка вопроса? Почему задачи на классификацию, которые легко решает четырехлетний ребенок, долгое время были (и до сих пор остаются) не по зубам программам? Почему распознавать предметы окружающего мира сложнее, чем играть в шахматы? Что такое deep learning и почему в публикациях о нем с пугающим постоянством фигурируют котики? Давайте поговорим об этом.

Сразу раскрою мысль, вынесенную в заголовок. Использование потоков (также именуемых нити, треды, англ. threads) и средств прямой манипуляции ими (создание, уничтожение, синхронизация) для написания параллельных приложений оказывает столь же пагубное влияние на сложность алгоритмов, качество кода и скорость его отладки, какое вносило использование оператора Goto в последовательных программах.
Как когда-то программисты отказались от неструктурированных переходов, нам необходимо отказаться от прямого использования потоков сейчас и в будущем. И так же, как каждый из нас использует структурные блоки вместо Goto, вместо потоков должны использоваться структуры, построенные поверх них. Благо, все инструменты для этого появились во вполне традиционных языках.
^{Автор фото: Rainer Zenz}

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

UPD: в текст внесены некоторые изменения с целью сделать его более понятным. Смысловая составляющая осталась прежней.

Вступление

Возможно, у этой системы найдутся приложения не только
в роли логического исчисления. (Алонзо Чёрч, 1932)

Вообще говоря, лямбда-исчисление не относится к предметам, которые «должен знать каждый уважающий себя программист». Это такая теоретическая штука, изучение которой необходимо, когда вы собираетесь заняться исследованием систем типов или хотите создать свой функциональный язык программирования. Тем не менее, если у вас есть желание разобраться в том, что лежит в основе Haskell, ML и им подобных, «сдвинуть точку сборки» на написание кода или просто расширить свой кругозор, то прошу под кат.

Новогодние каникулы – хорошее время не только для отдыха, но и для самообразования. Можно отвлечься от повседневных задач и посвятить несколько дней тому, чтобы научиться чему-нибудь новому, что будет помогать вам весь год (а может и не один). Поэтому мы решили в эти выходные опубликовать серию постов с лекциями курсов первого семестра Школы анализа данных.

Сегодня — о самом важном. Современный анализ данных без него представить невозможно. В рамках курса рассматриваются основные задачи обучения по прецедентам: классификация, кластеризация, регрессия, понижение размерности. Изучаются методы их решения, как классические, так и новые, созданные за последние 10–15 лет. Упор делается на глубокое понимание математических основ, взаимосвязей, достоинств и ограничений рассматриваемых методов. Отдельные теоремы приводятся с доказательствами.



Читает курс лекций Константин Вячеславович Воронцов, старший научный сотрудник Вычислительного центра РАН. Заместитель директора по науке ЗАО «Форексис». Заместитель заведующего кафедрой «Интеллектуальные системы» ФУПМ МФТИ. Доцент кафедры «Математические методы прогнозирования» ВМиК МГУ. Эксперт компании «Яндекс». Доктор физико-математических наук.

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

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

Сбалансированное дерево поиска является фундаментом для многих современных алгоритмов. На страницах книг по Computer Science вы найдете описания красно-черных, AVL-, B- и многих других сбалансированных деревьев. Но является ли перманентная сбалансированность тем Святым Граалем, за которым следует гоняться?

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

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

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

Это статья попытка показать, что сила функциональных языков и в первую очередь Хаскеля — это в том числе и силе функторов и монад.

В первой части нашей статьи мы рассказали о том, каким образом можно получить простую программу “Hello World”, которая запускается без операционной системы и печатает сообщение на экран.

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

! ВАЖНО!: Все дальнейшие действия могут успешно осуществляться только после успешного прохождения всех 6-ти шагов описанных в первой части статьи).

С каждым новом поколением процессоры Intel вбирают в себя все больше технологий и функций. Некоторые из них у всех на слуху (кто, например, не знает про гипертрединг?), о существовании других большинство неспециалистов даже не догадываются. Откроем всем хорошо известную базу знаний по продуктам Intel Automated Relational Knowledge Base (ARK) и выберем там какой-нибудь процессор. Мы увидим здоровенный список функций и технологий — что скрывается за их таинственными маркетинговыми наименованиями? Предлагаем углубиться в вопрос, обращая особое внимание на мало известные технологии — наверняка, там найдется много интересного.

Университет Иннополис объявляет о начале конкурса среди студентов 3-5 курсов ведущих вузов России и зарубежья в области ИТ. Победители конкурса – группа студентов численностью 30-40 человек получат целевой грант на обучение по этой программе.

Праздничная неделя подходит к концу, но мы продолжаем публиковать лекции от Школы анализа данных Яндекса для тех, кто хочет провести время с пользой. Сегодня очередь курса, важность которого в наше время сложно переоценить – «Параллельные и распределенные вычисления».

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



Лекции читает Олег Викторович Сухорослов, старший научный сотрудник Центра грид-технологий и распределенных вычислений ИСА РАН. Доцент кафедры распределенных вычислений ФИВТ МФТИ. Кандидат технических наук.