пятница, 11 ноября 2016 г.

Матричные операции

Урок: Матричные операции

Транскрибация урока: [БЕЗ_ЗВУКА] В это видео мы поговорим о том, какие операции можно вводить над матрицами. В прошлый раз мы уже разобрались с вами, как умножать матрицу на вектор. А именно: мы можем умножать матрицу размера m × n на вектор-столбец размера n × 1. Для этого мы домножаем каждый элемент i-той строки на соответствующий элемент вектора и складываем. В итоге получаем i-тый элемент вектора-результата. Получаем мы на выходе вектор размера m × 1. Обратите внимание, мы могли умножать матрицу на вектор только в том случае, если число столбцов в матрице совпадало с длиной вектора. Иначе операция была не определена. Давайте теперь поговорим о том, как ввести более общую операцию — умножение матрицы на матрицу. Она будет возможна только в том случае, если число столбцов в первой матрице совпадает с числом строк во второй матрице. Иначе эта операция будет не определена, делать её будет невозможно. Итак. Пусть есть две матрицы — A и B. Матрица A имеет размер m × n, а матрица B имеет размер n × k. Результатом будет матрица C размера m × k. То есть строк в ней будет столько же, сколько в первой матрице, а столбцов столько же, сколько во второй. Чтобы перемножить матрицы A и B и получить C, мы делаем следующее: i-тый j-тый элемент матрицы C получается поэлементным умножением i-той строки матрицы A на j-тый столбец матрицы B, что затем складывается. Именно так и получается матрица C. Давайте разберём пример. Пусть есть две матрицы, первая имеет размер 3 × 2, вторая 2 × 3. Результатом будет матрица размера 3 × 3. Давайте получим её элемент с индексами 1, 1. Для этого нам понадобится первая строка матрицы A и первый столбец матрицы B. Перемножаем их. Получаем 1 * 1 + 2 * 0. Значит, элемент с индексами 1, 1 матрицы C будет равен 1. Посчитаем элемент с индексами 1, 2. Для этого мы умножаем 1 на 0 и 2 на 0 и складываем. Получаем 0. Чтобы получить элемент с индексами 1, 3, умножаем 1 на 0, прибавляем 2 * 2, получаем 4. Наконец, чтобы получить элемент с индексом 2, 1, умножаем 0 на 1, 1 на 0, получаем 0. И так далее. У вас, наверное, уже возник вопрос: почему мы ввели операцию умножения матриц именно так? Эта формула не кажется интуитивной, она не приходит в голову в первую очередь. Но, оказывается, у неё есть довольно понятный глубокий смысл. Давайте попробуем его понять. Мы уже выясняли, что матрица, по сути, задаёт линейное преобразование, линейную функцию из одного векторного пространства в другое. То есть, по сути, она принимает на вход один вектор и возвращает другой, уже другой разрядности. Например, матрица A может задавать преобразование из пространства V в пространство W, а матрица B — задавать преобразование из пространства W в пространство T. Поскольку это функции, можем определить их композицию, B от A, то есть сначала к вектору из пространства V применяем преобразование A, потом преобразование B, и в итоге вектор из пространства V переходит в пространство T. При этом оказывается, если мы перемножим матрицы B и A, то полученное произведение BA будет как раз задавать преобразование из пространства V в пространство T, ровно то преобразование, которое является композицией B и A. Это одна из главных причин, почему умножение вводится именно так. Есть ещё одна причина. Представьте, что у нас есть некоторая система линейных уравнений Ax = b. Например, это может быть задача поиска линейного классификатора для предсказания возникновения рака. В этом случае в строках A записаны пациенты, для каждого пациента известно, какие мутации имеют место в его геноме, а в B записан правильный ответ: возникнет рак через 5 лет или не возникнет. Тогда x — это веса, с которыми складываются индикаторы наличия мутации в геноме, и получается некоторый ответ. При этом, на самом деле, x может тоже выражаться через другой вектор z, то есть может иметь место уравнение x = Bz. Откуда оно может быть? Оно может задавать некоторые дополнительные ограничения. Например, что две определённые мутации должны носить одинаковый вклад в принятие решения, то есть должны иметь одинаковый вес. Это всё можно отрегулировать матрицей B. В итоге получается, что нужно решать систему вида A*(Bz) = b. Так вот. Оказывается, что если мы поставим выражение для вектора x, то есть x = Bz, в первое уравнение, раскроем скобки, сгруппируем и получим уравнение относительно z, то мы получим систему с матрицей, которая будет равняться произведению A и B. То есть мы ввели умножение так, чтоб можно было подставлять одну систему линейных уравнений в другую, и при этом всё сохранялось. Хорошо. Давайте поговорим о более простых операциях — сложение и умножение на число. Здесь всё гораздо более интуитивно. Чтобы сложить две матрицы, мы должны убедиться, что они имеют одинаковый размер. То есть обе имеют размерность m × n, иначе сложение не определено. Складываем мы поэлементно. То есть i-тый j-тый элемент матрицы C суммы A и B будет равняться aij + bij. Всё очень просто. То же самое касается умножения на число. Чтобы умножить матрицу b на некоторое число α, просто умножаем на α каждый элемент. То есть cij — результат — будет равен α * bij. Наконец, поговорим о такой операции, как транспонирование. Мы будем с ней сталкиваться довольно часто. Для этого нам понадобится понятие главной диагонали. Пусть есть некая матрица A размера 4 × 3. Главной диагональю называются все её элементы, у которых первый индекс равен второму, то есть все элементы вида aii. В нашем случае, это будет элемент (1, 1), (2, 2) и (3, 3), которые имеют значения 1, 3 и 0. Это действительно диагональ. Транспонирование — это, по сути, поворот относительно главной диагонали. Матрица A размера m × n превращается в матрицу A транспонированное размера n × m. Кстати, A транспонированное обозначается как A с верхним индексом T. Иными словами, i-тый j-тый элемент транспонированной матрицы равен j-тому i-тому элементу исходной матрицы. Ещё можно интерпретировать это так, что строки исходной матрицы становятся столбцами транспонированной матрицы. Вернёмся к нашему примеру. Матрица размера 4 × 3 становится матрицей 3 × 4, при этом главная диагональ 1, 3, 0 остаётся на своём месте, а всё остальное поворачивается относительно неё. То есть, например, столбец 1, 2, 2 ,5 (первый столбец) становится первой строкой 1, 2, 2, 5. И так далее. Итак. Что мы узнали? Умножение матриц — это довольно хитрая операция, которая при этом имеет довольно глубокий смысл. Например, она соответствует композиции двух линейных преобразований или соответствует постановке в систему линейных уравнений вектора, который тоже выражается как матрица умножить на вектор. При этом сложение и умножение для матриц (умножение на константу) определяется интуитивно, просто поэлементно. Также мы изучили с вами транспонирование — это операция, которая меняет строки и столбцы матрицы местами. В следующем видео мы поговорим о том, что такое ранг и определитель.

Часть: Линейная алгебра. Матрицы

Модуль: Библиотеки Python и линейная алгебра

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

Курс: Математика и Python для анализа данных

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

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

В этом курсе вы познакомитесь с фундаментальными математическими понятиями, необходимыми для анализа данных, и получите начальный навык программирования на Python. Курс состоит из двух больших частей. Первая часть курса – практическая, она посвящена языку программирования Python. Вы познакомитесь с синтаксисом и идеологией языка, научитесь писать простые программы. Также вы узнаете о библиотеках, которые часто применяются на практике для анализе данных, например, NumPy, SciPy, Matplotlib и Pandas. Вторая часть курса посвящена таким разделам математики как линейная алгебра, математический анализ, методы оптимизации и теория вероятностей. При этом, упор делается на разъяснение математических понятий и их применение на практике, а не на вывод сложных формул и доказательство теорем.

Программа:
  • Введение
  • Знакомство с курсом
  • Python, уровень 0
  • Знакомство с синтаксисом Python
  • Производная и её применения
  • Немного обсуждений
  • Библиотеки Python и линейная алгебра
  • Библиотеки NumPy, Matplotlib, SciPy, Pandas
  • Линейная алгебра. Векторы
  • Линейная алгебра. Матрицы
  • Оптимизация и матричные разложения
  • Градиент и оптимизация гладких функций
  • Оптимизация негладких функций
  • Матричные разложения
  • Случайность
  • Вероятность и случайные величины
  • Статистики
  • Бонусный урок
Описание преподавателя:
  • Евгений Рябенко — кандидат физико-математических наук, доцент кафедры "Интеллектуальные системы" ФУПМ МФТИ, Data Scientist Фабрики данных Яндекса. Соавтор и преподаватель курса "Прикладной статистический анализ данных", который читается в МФТИ, МГУ и ВШЭ. Занимается анализом данных, био- и нейроинформатикой, кормит синиц.
  • Евгений Соколов — руководитель группы анализа неструктурированных данных в Yandex Data Factory. Окончил факультет ВМК МГУ в 2013 году, сейчас пишет диссертацию про матричные разложения в аспирантуре там же. Ведет практические занятия по машинному обучению на ВМК МГУ и читает лекции на ФКН ВШЭ. Преподаватель Школы Анализа Данных Яндекса.
  • Виктор Кантор – старший преподаватель кафедры “Алгоритмы и технологии программирования” ФИВТ МФТИ, руководитель исследовательской группы Yandex Data Factory. Ведет лекции и семинары в МФТИ на кафедрах “Алгоритмы и технологии программирования”, “Анализ данных”, “Банковские информационные технологии”, “Компьютерная лингвистика” и “Распознавание изображений и обработка текстов”.
  • Эмели Драль – преподаватель ШАД и руководитель исследовательской группы Yandex Data Factory. Окончила РУДН, факультет физико-математических и естественных наук, кафедра “Информационные технологии”. Разрабатывала учебные материалы и вела такие курсы как “Технологии разработки программных систем”, “Объектно-ориентированный подход к разработке программных систем”, “Методы интеллектуального поиска”. В МФТИ ведет семинары курса "Машинное обучение" на ФИВТ, кафедра “Алгоритмы и технологии программирования”.
Категория: Наука о данных

Описание категории: На специализациях и курсах по науке о данных преподаются основы интерпретации данных, проведения различных видов анализа, понимания и представления практических выводов. Начинающие и продолжающие учащиеся освоят такие темы, как качественный и количественный анализ данных, инструменты и методы манипулирования данными, а также алгоритмы машинного обучения.

Тематика: Анализ данных

Материал:



Список литературы

Линейная алгебра
Виктор Кантор:
  • Ильин, Ким. Линейная алгебра и аналитическая геометрия (1998) — МГУ.
  • Умнов. Аналитическая геометрия и линейная алгебра (2011) — МФТИ.
Евгений Рябенко:
  • Деммель. Вычислительная линейная алгебра. Теория и приложения (2001) — понятный кусок про матричные разложения.
Математический анализ
Виктор Кантор:
  • Ильин, Позняк, Основы математического анализа (2005) — МГУ.
  • Тер-Крикоров, Шабунин. Курс математического анализа (2001) — МФТИ, много примеров.
  • Иванов. Лекции по математическому анализу (2000) — МФТИ, очень короткое, но полное изложение.
Методы оптимизации
Евгений Рябенко:
  • Нестеров. Методы выпуклой оптимизации (2010) — математически строгое введение в оптимизацию от живого классика.
  • Boyd, Vandenberghe. Convex Optimization (2004) — идеальная книга по классической оптимизации, много интересных постановок задач.
  • Schneider, Kirkpatrick. Stochastic Optimization (2006) — стохастическая оптимизация во всём многообразии.
Теория вероятностей и статистика
Евгений Соколов:
  • Dekking, Kraaikamp, Lopuhaa, Meester. A Modern Introduction to Probability and Statistics, Understanding Why and How (2005) — доступная книга, описывающая базовые понятия, теоремы и методы; разбирается очень много примеров, тесно связанных с задачами машинного обучения и анализа данных.
Виктор Кантор:
  • Лагутин. Наглядная математическая статистика (2007) — в основном статистика, но есть и небольшое введение в теорию вероятностей. Стоит читать, кроме глав про классификацию и анализ данных, там изложение не слишком современно.
  • Чжун, АитСахлиа. Элементарный курс теории вероятностей. Стохастические процессы и финансовая математика (2007) — очень простое изложение.
  • Отличные лекции с мехмата Новосибирского Государственного Университета: http://www.nsu.ru/mmf/tvims/chernova/tv/tv_nsu07.pdf — теория вероятностей, http://www.nsu.ru/mmf/tvims/chernova/ms/ms_nsu07.pdf — математическая статистика.
Евгений Рябенко:
  • Diez, Barr, Çetinkaya-Rundel, Dorazio. Advanced High School Statistics (2015) — вводная книга, программа соответствует типичному курсу Statistics 101 хорошего западного университета.
  • DasGupta. Probability for Statistics and Machine Learning: Fundamentals and Advanced Topics (2011) — для смелого читателя, рассматриваются в том числе достаточно высокоуровневые методы.
Python
Эмели Драль:
  • Классические руководства по Python: https://docs.python.org/2/tutorial/ (2.7), https://docs.python.org/3/tutorial/(3.5)
  • Reitz. The Hitchhiker’s Guide to Python http://docs.python-guide.org/en/latest/ — довольно полное руководство, в котором рассматриваются вопросы от установки, работы с виртуальным окружением и работы в различных IDE до основных структур языка с примерами кода.
  • Google python class https://developers.google.com/edu/python/ — небольшой бесплатный онлайн-курс по Python для слушателей с минимальным опытом программирования.
Книги, для тех, кому захочется основательно изучить Python:
  • Lutz. Learning Python (2013) — с этой книги можно начинать изучение, она покрывает все основные структуры языка.
  • Lutz. Python Pocket Reference (2015) — подробный справочник.
Конспекты
https://drive.google.com/open?id=0B4sIH7qjgc24cVh0aTNnMEM0eXc

Интересные ресурсы
Ресурсы по материалам 1 недели:
Здесь http://bit.ly/29hALFk вы можете узнать, какие языки программирования сегодня являются самыми востребованным. Интересно, какое место в рейтинге занимает python?

Многие часто спрашивают, почему мы выбрали для специализации python, а не R? Мы подошли к выбору со всей ответственностью, рассмотрели плюсы и минусы обоих вариантов и остановились на python, в первую очередь, из-за простоты изучения, читаемости кода и универсальности языка. Здесь вы можете почитать статью о сравнении языков python и R http://bit.ly/29lkL5z

Ресурсы по материалам 2 недели:
На второй неделе курса Вам предстоит знакомство с библиотекой Pandas для работы с данными в виде таблиц, SciPy и NumPy для работы со статистикой, линейной алгеброй, оптимизационными задачами, а также Matplotlib для визуализации данных. Эти библиотеки очень функциональны, просты для изучения и популярны в мире анализа данных. Они настолько широко распространены, что часто можно встретить их использование для вот таких необычных задач: Python и красивые ножки http://bit.ly/2an3FTt

Занятное дополнение к материалам второй недели:
  • Знакомство с Python, Numpy, Scipy, Matplotlib http://bit.ly/2a4yd06
  • Курс Делфтского Технического Университета про Python и его использование в научных вычислениях http://bit.ly/29GCt4J
Ресурсы по материалам 4 недели:
Статистика — важный инструмент познания, дающий нам механизм порождения новых знаний из наблюдений за окружающим миром. Научиться им пользоваться может быть непросто; если материал лекций покажется Вам сложным, посмотрите, как понятия статистики объясняются на котиках http://bit.ly/29T53jd или в танце http://bit.ly/29PH9l5