понедельник, 7 ноября 2016 г.

Линейная независимость

Урок: Линейная независимость

Транскрибация урока: [БЕЗ_ЗВУКА] В этом видео мы поговорим о линейной независимости. Это очень важное понятие при работе с векторами. В прошлых видео мы не один раз рассматривали пример с магазинами, когда мы хотим предсказать прибыль каждого из магазинов в следующем месяце. Допустим, у нас есть 100 магазинов, каждый из которых описывается десятью признаками, десятью числами. Тогда мы можем составить таблицу размера 100 x 10, где каждая строка будет соответствовать признаковому описанию одного магазина, а каждый столбец — набору значений одного признака на всех магазинах. Раньше в качестве векторов мы рассматривали строки этой таблицы, то есть каждый вектор являлся признаковым описанием одного магазина. В этом видео ситуация будет противоположная: в качестве векторов будем рассматривать столбцы этой таблицы. То есть один вектор будет содержать значение одного признака на всех магазинах. Что, если вектор первого признака равен вектору второго признака, умноженного на 1000? Это может означать, что и первый, и второй признаки — это суммарный вес товаров, которые завезут в магазин в следующем месяце. Но при этом первый признак равен этому весу в граммах, а второй — в килограммах. Понятно, что это избыточная информация. Нам не нужно знать значения этого признака и в одной, и в другой единице измерения. Достаточно знать лишь одно из этого. Вот второй пример. Представьте, что третий признак равен среднему значению четвёртого и пятого признаков. Это может означать, что четвёртый признак — это прибыль магазина в прошлом месяце. Пятый признак — прибыль в позапрошлом месяце. Тогда значение третьего признака имеет смысл средней прибыли магазина за последние два месяца. Это снова избыточная информация. Эта ситуация, в которой один вектор выражается как сумма с коэффициентами других векторов, называется линейной зависимостью. Линейная зависимость — это довольно плохо. Дело в том, что она приводит к избыточности информации. Мы храним те векторы, которые на самом деле выражаются через остальные довольно простым способом. Также мы тратим дополнительные ресурсы на хранение лишней информации. Тоже не очень хорошо: приводит к лишним денежным затратам. Также линейная зависимость вредит некоторым методам машинного обучения, например линейным. Об этом мы будем говорить в следующих занятиях. Дадим формальное определение. Пусть дан набор векторов x1, ..., xn. xi-тая — это один вектор, значение признаков, значение одного признака на всех объектах. Эти векторы линейно зависимы, если существуют такие числа β1, ..., βn, что хотя бы одно из них... хотя бы один из них не равен нулю, и при этом сумма векторов с этими коэффициентами равна нулю. Кстати, обратите внимание: в этом уравнении слева стоит сумма с коэффициентами векторов, то есть это тоже вектор, значит и справа должен стоять вектор из всех нулей, который мы просто обозначаем нулем, как и вещественное число. Можно дать немного альтернативное определение линейной зависимости. Возьмём вектор, в нашем примере это i‐тый вектор, при котором коэффициент не равен нулю. Перенесём этот вектор в другую часть равенства, поделим на коэффициент βi-тая, переобозначим коэффициенты и получим аналогичное определение: система векторов линейно зависимая, если один из них выражается через все остальные. Обратите внимание на одну особенность этого определения. Если один из векторов нулевой, то все они будут сразу линейно зависимы. Дело в том, что мы можем взять коэффициент перед нулевым вектором равным единице, при остальных векторах коэффициенты — ноль, и определение линейной зависимости будет выполнено. Это вполне логично: если один из векторов нулевой, он не содержит в себе никакой информации, сразу система становится избыточной. Опеределение линейной независимости дать просто. Система векторов линейно независимая, если для неё не выполнено определение линейной зависимости. Или, что то же самое, уравнение β1 * х1 + β2 * х2 +... + βn * xn равно нулю только в том случае, если все коэффициенты β1, β2, ..., βn равны нулю. Это и есть опеределение линейной независимости. Рассмотрим простой пример. Пусть дано три вектора из евклидова пространства R3, то есть векторы длины три. Первый из них имеет вид (2, 1, 2), второй — (4, 2, 4), третий — (1, 2, 3). Если мы возьмём первый вектор, умножим его на два и вычтем второй вектор, то получим нулевой вектор. Это значит, что эта система векторов линейно зависима. А что будет, если мы заменим первую координату во втором векторе с четвёрки на пятёрку? Оказывается, система станет линейно независимой. Но как это можно было понять? Есть два способа. Первый из них — это метод Гаусса, который позволяет привести систему векторов к такому виду, в котором будет очевидно — она является линейно зависимой или линейно независимой. Но мы не будем его изучать, потому что есть гораздо более простой способ: вычислить ранг системы векторов, например, на компьютере. Об этом будем говорить в следующих видео этого урока. Напоследок поговорим о ещё одном важном понятии, которое вытекает из линейной независимости — это размерность. Пусть дано некоторое векторное пространство V. Максимальное число линейно независимых векторов в нём и называется размерностью этого пространства и обозначается как dim V. Например, для евклидова пространства Rn размерность равняется как раз таки n, то есть длине вектора в нём. Это легко показать. Представьте себе систему векторов e1, e2, ..., en, где вектор ei имеет следующий вид: в нём ровно одна координата — i‐тая — равна единице, а все остальные координаты равны нулю. Эти векторы линейно независимы, но при этом любой другой вектор в Rn выражается линейно через них. Такой набор векторов, через который выражается любой другой вектор, называется базисом векторного пространства. Итак, что мы узнали? Понятие линейной зависимости позволяет выявлять избыточность информации в системе векторов. Векторы линейно зависимы, если один из них выражается через все остальные. При этом установить факт линейной зависимости или независимости можно, вычислив ранг системы векторов. Также мы ввели понятие размерности векторного пространства — это максимальное число линейно независимых векторов в нём.

Часть: Линейная алгебра. Векторы

Модуль: Библиотеки 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