Школа анализа данных воронцов
Обновлено: 02.07.2024
Кстати, похожие задачи будут в этом году на вступительном экзамене в ШАД, где для людей с опытом в ИТ мы придумали новый трек, который поможет им улучшить свои знания математики.
1. В ряд выложены пять красных, пять синих и пять зеленых шаров. С какой вероятностью никакие два синих шара не лежат рядом?
Например, так: сначала расположим красные и зелёные шары (надо выбрать из десяти пять мест, в которых будут красные), после чего пять синих шаров надо положить не более, чем по одному, в одиннадцать промежутков между красными и зелёными шарами, а также слева и справа (то есть выбрать пять мест из одиннадцати).
Задачи по алгоритмам очень хороши тем, что они проверяют не только умение понятно описать некую процедуру, но и объяснить, почему она работает.
Если граф — дерево, то бракованное реле находится перед первой (от источника тока) не горящей лампочкой. Если есть циклы, то можно выключить все рёбра и запустить аналог поиска в глубину.
3. Докажите, что среди шести человек обязательно найдутся трое попарно знакомых или трое попарно незнакомых.
Задачи на графы, особенно если количество вершин небольшое, чаще всего стараются свести к разбору случаев. Важно, чтобы вы смогли внимательно разобрать их и при этом не запутаться.
- четное число, гласная буква;
- нечетное число, что угодно.
И не подходят карточки вида:
5. Докажите, что равносторонний треугольник нельзя покрыть двумя меньшими равносторонними треугольниками.
Задачка на геометрическую интуицию: надо понять, что ни один из меньших треугольников не может покрыть сразу две вершины. После этого становится ясно: чтобы покрыть все три вершины, нужно хотя бы три треугольника. А вообще тут зарыто непростое утверждение о диаметре треугольника, но его можно не доказывать.
6. Квадратная матрица такова, что след tr(AX) = 0 для любой матрицы X того же размера, имеющей нулевой след (след матрицы — сумма элементов на главной диагонали).
Докажите, что матрица является скалярной (т. е. имеет вид λE для некоторого λ, где E — единичная матрица).
Таким образом, встретив подобную задачу, стоит сначала взять какие-нибудь конкретные (и желательно очень простые) матрицы X с нулевым следом и попробовать понять, что же нам дает условие tr(AX) = 0. В качестве таких матриц удобно взять матричные единицы (и матрицы, у которых на диагонали все нули, кроме двух элементов, равных 1 и (-1).
Собственно говоря, на этом задача и закончится: из условий tr(AX) = 0, которые вы распишете для таких матриц, сразу будет следовать ответ.
Когда-то мы публиковали на Хабре курс по машинному обучению от Константина Воронцова из Школы анализа данных. Нам тогда предлагали сделать из этого полноценный курс с домашними заданиями и разместить его на Курсере.
Сооснователь Coursera Дафна Коллер в офисе Яндекса
Курс продлится семь недель. Это означает, что по сравнению с ШАДовским двухсеместровым курсом он будет заметно упрощен. Однако в эти семь недель мы попытались вместить только то, что точно пригодится на практике, и какие-то базовые вещи, которые нельзя не знать. В итоге получился идеальный русскоязычный курс для первого знакомства с машинным обучением.
Под катом можно прочитать подробнее обо всех авторах курса и узнать его примерное содержание.
О преподавателях
Лектор курса – Константин Воронцов. Константин Вячеславович много лет преподает основы машинного обучения студентам ШАД, Вышки, МФТИ и МГУ.
Практическую часть курса подготовили Петр Ромов, Анна Козлова и Евгений Соколов, который также читает несколько лекций. Все трое работают в Яндексе (Женя и Петя в Yandex Data Factory, Аня — в отделе машинного перевода) и применяют машинное обучение в своей ежедневной деятельности. Ребята в курсе происходящего в области анализа данных и постарались подготовить задания так, чтобы их выполнение принесло максимальную пользу слушателям курса.
Программа
1. Знакомство с анализом данных и машинным обучением.
В этом модуле мы расскажем о задачах, которые решает машинное обучение, определим базовый набор понятий и введем необходимые обозначения. Также мы расскажем про основные библиотеки языка Python для работы с данными (NumPy, Pandas, Scikit-Learn), которые понадобятся для выполнения практических заданий на протяжении всего курса.
2. Логические методы классификации.
Логические методы делают классификацию объектов на основе простых правил, благодаря чему являются интерпретируемыми и легкими в реализации. При объединении в композицию логические модели позволяют решать многие задачи с высоким качеством. В этом модуле мы изучим основной класс логических алгоритмов — решающие деревья. Также мы поговорим про объединение деревьев в композицию, называемую случайным лесом.
3. Метрические методы классификации.
Метрические методы проводят классификацию на основе сходства, благодаря чему могут работать на данных со сложной структурой — главное, чтобы между объектами можно было измерить расстояние. Мы изучим метод k ближайших соседей, а также способ его обобщения на задачи регрессии с помощью ядерного сглаживания.
4. Линейные методы классификации.
Линейные модели — один из наиболее изученных классов алгоритмов в машинном обучении. Они легко масштабируются и широко применяются для работы с большими данными. В этом модуле мы изучим метод стохастического градиента для настойки линейных классификаторов, познакомимся с регуляризацией и обсудим некоторые тонкости работы с линейными методами.
5. Метод опорных векторов и логистическая регрессия.
Линейные методы имеют несколько очень важных подвидов, о которых пойдет речь в этом модуле. Метод опорных векторов максимизирует отступы объектов, что тесно связано с минимизацией вероятности переобучения. При этом он позволяет очень легко перейти к построению нелинейной разделяющей поверхности благодаря ядровому переходу. Логистическая регрессия позволяет оценивать вероятности принадлежности классам, что оказывается полезным во многих прикладных задачах.
6. Метрики качества классификации.
В машинном обучении существует большое количество метрик качества, каждая из которых имеет свою прикладную интерпретацию и направлена на измерение конкретного свойства решения. В этом модуле мы обсудим, какие бывают метрики качества бинарной и многоклассовой классификации, а также рассмотрим способы сведения многоклассовых задач к двухклассовым.
8. Понижение размерности и метод главных компонент.
В прикладных задачах часто возникает потребность в уменьшении количества признаков — например, для ускорения работы моделей. В этом модуле мы обсудим подходы к отбору признаков, а также изучим метод главных компонент, один из самых популярных методов понижения размерности.
9. Композиции алгоритмов.
Объединение большого числа моделей в композицию может значительно улучшить итоговое качество за счет того, что отдельные модели будут исправлять ошибки друг друга. В этом модуле мы обсудим основные понятия и постановки задач, связанные с композициями, и обсудим один из наиболее распространенных способов их построения — градиентный бустинг.
10. Нейронные сети.
Нейронные сети позволяют находить сложные нелинейные разделяющие поверхности, благодаря чему широко используются в таких трудных задачах, как распознавание изображений и речи. В этом модуле мы изучим многослойные нейронные сети и их настройку с помощью метода обратного распространения ошибки. Также мы поговорим о глубоких нейросетях, их архитектурах и особенностях.
12. Частичное обучение.
Под частичным обучение понимается задача, находящаяся между обучением с учителем и кластеризацией: дана выборка, в которой значение целевой переменной известно лишь для части объектов. Такие ситуации встречаются, когда разметка объектов является дорогой операцией, но при этом достаточно дешево можно подсчитать признаки для объектов. В этом модуле мы обсудим отличия частичного обучения от рассмотренных ранее постановок, и разберем несколько подходов к решению.
13. Машинное обучение в прикладных задачах
В этом модуле мы подведем итоги курса, вспомним основные этапы решения задачи анализа данных. Также мы разберем несколько задач из прикладных областей, чтобы подготовиться к выполнению финального проекта.
Школа анализа данных – двухгодичная программа обучения от Яндекса. Основной упор в ней делается на данные и методы работы с ними. В небольшом обзоре мы разберём плюсы и минусы учёбы в ШАД.
Как поступить?
Итак, ШАД – полноценное обучение на протяжении двух лет, с нагрузкой по 30 часов в неделю. Обучение бесплатное, но сначала требуется пройти онлайн-тестирование, затем экзамен и собеседование в филиалах ШАД.
Как и в университете, здесь есть возможность платного поступления, но для этого нужно хорошо показать себя на собеседовании. Стоит учёба 150 000 рублей в семестр. Если закончить семестр на хорошо и отлично, цена уменьшится наполовину. А если два раза подряд закончить хорошистом или отличником, обучение станет бесплатным.
Онлайн-тестирование – обычное заполнение анкеты с тестовыми вариантами задач. После него есть два варианта: для москвичей следует прибыть в отделение ШАД и сдать экзамен по математике, алгоритмам, а затем по программированию и основам анализа данных. Заочники или учащиеся в региональных отделениях сдают онлайн-экзамен.
В конце пройдёт собеседование – очный экзамен по тому же программированию, математике и алгоритмам.
Все задачи выбираются в рамках общей программы (в документе даже указаны все необходимые книги для подготовки). Кстати, у нас есть статья, полностью посвящённая подготовке к поступлению в ШАД.
В 2020 году появился вариант поступления для тех, кто уже давно в программировании. В этом случае потребуется вместо математики продемонстрировать умение программировать, а также участие в проектах, различных статьях и прочем.
Кому это нужно?
Во-первых, выпускники получают диплом о профессиональной переподготовке. Во-вторых, любовь к Data Science и желание глубоко-глубоко нырнуть в эту отрасль. При этом, если вас интересует чистая научная теория, то место найдётся – регулярные семинары и различные исследовательские проекты.
В целом, целевую аудиторию можно описать так: хочется попасть в сферу Data Science, сделать это максимально эффективно и интересно. К тому же, обучение проходит по вечерам.
ШАД: Плюсы обучения
ШАД: Минусы обучения
- Вечерняя программа. Если ваша жизнь уже загружена, то добавлять к ней вечерние курсы – стрелять себе в ногу. При этом, обучение действительно интенсивное и требует внимательности.
- Серьёзная нагрузка. Так как здесь учат анализировать, то мозги будут работать на полную катушку. А то потребуется их перегружать их. Следует заранее прокачать выносливость и… умение отдыхать.
🏈 Rugby: Optimise CocoaPods project | Swifty Finch
Do you have problems while working on a huge project with a large number of pods in Xcode? Maybe endless indexing…
Статья является логическим продолжением моей последней публикации, в конце которой рассказывается о том как я получил возможность стать вольнослушателем в Школе Анализа Данных в Екатеринбурге и изучать Алгоритмы и Структуры Данных.
В этой статье я расскажу о том как готовился к обучению, что происходило на первом семестре и как всегда поделюсь своими впечатлениями. Я постараюсь следовать Кодексу чести студента ШАД в своем рассказе и не выдать ничего лишнего.
Для кого эта статья?
Скорее для тех, кому интересны алгоритмы, структуры данных, обучение и ШАД. Также для тех кто не знает как к этому всему подступиться. Я не рассчитываю, что смогу заинтересовать других людей. Но если вам понравились прошлые статьи, прочтите и эту.
Начало обучения было запланировано на сентябрь 2017 года, и у меня было около двух месяцев на подготовку. Может показаться странным, а зачем готовиться к обучению? Курс Алгоритмы и Структуры Данных предполагает, что студент уже знает базовые алгоритмы и структуры данных, а также “много разной математики”. Но это явно не про меня.
Также мне заранее сказали, что скорее всего вся практика будет сдаваться на языке программирования C++. Я немного изучал язык С на первом курсе университета лет 10 назад, а из С++ знал только cin и cout. Этого явно было достаточно, чтобы успешно завалить этот курс.
Я решил начать свою подготовку с общих теоретических знаний и выбрал для этого книгу “Алгоритмы” Санджой Дасгупта, Христос Пападимитриу, Умеш Вазирани. Не только потому, что мне понравились фамилии авторов, но и по рекомендациям это была самая простая книга об алгоритмах. Я бегло прочитал её за неделю. Книга оказалась очень полезной по разным причинам. К примеру, на меня снизошло прозрение в операциях по модулю.
Затем я начал смотреть различные видеолекции, в частности и старые лекции ШАД на YouTube. На это ушло много времени, я часто пересматривал одно и тоже пытаясь понять хоть что-то. Хочу признаться, это было очень тяжело. Чувствовалась нехватка знаний. Со временем я понял — пора переходить к практике так как я стал забывать, что смотрел в самом начале.
В качестве практики я решил разобрать и написать простые структуры данных и алгоритмы на Swift. Мне очень помог Swift Algorithm Club. Для мотивации я решил каждый день что-то выкладывать на Github в свой репозиторий специально созданный для этих целей.
После этого я наткнулся на статью на Habrahabr и понял, что курс “Основы разработки на C++: белый пояс” мне идеально подходит. Курс рассчитан на 5 недель, но у меня было только две. Этого оказалось вполне достаточно, если ударно учиться по выходным и после работы.
Как выяснилось позже всё это мне очень сильно пригодилось, без этого я скорее всего не сдал бы даже первую домашнюю работу.
В середине сентября я пошел на первый семинар в университет. Пропуска у меня еще не было и я кое-как объяснил охраннику что я пришел учиться в школу. Мне нужно было попасть в аудиторию 611. Я заблудился, и начал всех спрашивать как пройти. Мне попадались студенты, которые или не говорят на русском или говорили мне — это на 6 этаже. Но я то уже пробовал подниматься на самый верх и знал, что в этом здании всего 4 этажа…
С горем пополам я нашел нужную аудиторию. Вторым моим удивлением стало то, что в ней было около 50 человек и казалось что все уже знали друг друга, кроме меня. Позже я понял, что этот курс преподается не только для студентов ШАД, но и для магистрантов МатМеха. На последние семинары приходило всего человек 10.
На первом семинаре рассказали, что все обучение состоит из видеолекций, семинаров и домашних заданий. Видеолекции и семинары не обязательны. Всё это можно было пропускать на свой страх и риск.
Также рассказали сколько балов нужно получить на зачет/хорошо/отлично. Что балы дают в основном за решение задач и рассказ решения на семинаре у доски. Также очень важны review-задачи.
Задания выдаются комплектами по несколько задач, за каждую своя оценка в балах. У каждого комплекта свой срок сдачи, до которого необходимо получить положительный результат от системы тестирования. Также необходимо описать решение задачи в PDF, оценить её сложность по времени и памяти, и доказать что алгоритм корректен и конечен.
Основной язык на котором нужно было сдавать был С++. Система тестирования также жёстко проверяла стиль кода. Нельзя было использовать однобуквенные переменные, даже в циклах. Никаких using namespace std, ограничения на ширину строк, пробелы вместо табуляции и тп. На каждую задачу прогонялось около 100 тестов, которые были закрыты. Система сообщает только номер проваленного теста.
Задачи условно можно поделить на три типа. Offline задачи — когда ваше решение практически не проверяется до окончания срока сдачи, и только после этого прогоняются все тесты без возможности внести исправления. Review задачи — когда код проверяется преподавателем, а также возможно необходимо описать алгоритм в уже объявленном интерфейсе с различными особенностями C++. И простые задачи, которые можно было отправлять на тестирование до 100 попыток.
В целом на каждую задачу я тратил около 10 часов, ближе к концу я справлялся по шустрее. Конечно всё зависит от конкретной задачи, но в целом почти все они были довольно сложными (для меня). В эти часы я также включаю просмотр видео и разбор теории. Семинары это ещё минус 3–4 часа свободного времени в неделю, если учитывать дорогу.
Так как я iOS разработчик все задачи я решал в Xcode. На мой взгляд это бесконечно удобная среда разработки, в которой приятно писать любой код (и почти не падает, да).
Я пересмотрел огромное количество лекций ШАД за разные годы, видео на YouTube из различных летних школ, зарубежных институтов (Princeton, Massachusetts, Harvard, etc.), и вот этого замечательного парня. В совокупности всё оказалось очень полезным.
Для написание теории в PDF я выбрал приложение Bear. Ограничений на формат не было, главное описать алгоритм, сложность и объяснить что он конечен и корректен. А в Bear просто приятно делать заметки.
Я не пропустил ни одного семинара. К сожалению, один семинар совпал с iOSParty, но таинственным образом преподаватель его отменил. В конце семестра я даже пару раз объяснял решения задач у доски с мелом, как настоящий школьник.
Кроме этого на семинарах рассказывали о устройстве памяти, об алгоритмах применяемых в базах данных, о сжатии различных данных и тп. В целом мне очень понравилось посещать семинары, в своё время когда я учился всё казалось очень скучным и такого желания не было.
Когда я не смог вовремя решить одну из задач мне было очень интересно узнать как её решили другие. Я почти бегом бежал на семинар и всё равно умудрился опоздать как раз на 10–15 минут, за которые и была рассказана моя задача. Очень порадовало, что преподаватель просто взял и объяснил мне её после занятия. Правда я всё равно не понял. Ничего. Позже я разобрался с ней дома.
В итоге я смог решить 21 задачу из 24. Сдал 3 review и написал 21 PDF с теорией. Были ещё дополнительные небольшие задачи и одна очень сложная задача, которую не решал никто и мы её даже не разбирали. Этого с не плохим запасом хватило на отлично.
Сложно сказать сколько времени я потратил на обучение, но думаю очень и очень много. Я очень рад, что у меня было это время благодаря гибкому графику и удаленной работе. Также очень здорово, что я получил возможность бесплатно обучаться на этом курсе благодаря Яндекс.
Хочется заметить, что ШАД это школа только по своим размерам. На самом деле учиться в ней приходится исключительно самостоятельно, иначе вы обречены на провал. В практических задачах часто требуется фантазия чтобы увидеть определенную структуру или алгоритм. Это не просто задачи по типу “Напишите сортировку”, как я изначально ожидал. Было действительно сложно и мне всё понравилось.
Очень частый вопрос: “А тебе это всё пригодиться хотя бы?”. В моей работе скорее всего нет, это маловероятно. Я считаю, что это основы которые просто полезно знать любому программисту. Computer Science, расширение кругозора и всё вот это. Сейчас я перетаскиваю кнопки в iOS, а чем захочу заниматься в будущем неизвестно.
Это конец первого семестра, а я отправляюсь на второй) Обещали графы для взрослых. Не уверен, что смогу уделять также много времени и в целом потяну обучение. Я обязательно поделюсь новыми впечатлениями о втором семестре уже этим летом! Но, это не точно.
Надеюсь моя статья была вам полезна, или хотя бы интересна. Или может вы улыбнусь пока читали. Чуть-чуть. Нет…? А я вот ещё схему сделал:
Пол года спустя. Сначала я планировал написать новую статью, но материала получилось не очень много. Я не могу рассказывать детали, описание задач. Поэтому… 🙄
Зимой перед вторым семестром вышел новый курс по С++. На этот раз жёлтый пояс. Я с удовольствием его прошел и считаю, что он оказался очень полезным для прохождения ревью по одной из задач второго семестра. Нужно было написать сложный алгоритм в рамках уже подготовленного интерфейса на 2000+ строк. Да, это жёстко)
Во время обучения мы изучали различные строковые алгоритмы, контекстно-свободные грамматики и алгоритмы на графах. Семинары были в самом конце семестра. Когда они проходили я уже и не мог вспомнить как решал часть задач)) но я не оставил попытки выступлений у доски.
В целом учиться было сложнее чем на первом семестре, но я втянулся и смог решить 17 задач из 20. Сдал все ревью. В этот раз было сложнее оценивать алгоритмы при написании теории в pdf. Часть мне возвращали на доработку и я не всегда сразу мог понять в чем же проблема. В конечном итоге я получил отлично ☺️🎉
На этом всё) Если у вас есть вопросы — пишите. В ближайшее время я планирую искать возможности применения новых знаний на практике. Но, это не точно. Также вскоре я планирую новую экспериментальную статью про алгоритмы, Swift и всё вот это. 😱
Читайте также: