Обработка и анализ данных физического эксперимента 2020/2021


Обработка и анализ данных физического эксперимента 2020/2021

Текущая успеваемость

Онлайн-составляющая: Version Control with Git

На время дистанционных занятий мы занимаемся в Teams:

Практические задания

Лекции

15.01 “Анализ алгоритмов”

Выяснили, что алгоритм - это математический объект, который подвержен формальному анализу. Среди всего остального нас интересует алгоритмическая сложность: зависимость времени исполнения (количества шагов, количества операций) от характерного размера входных данных. Обнаружилось, что разные алгоритмы могут решать одну и ту же задачу, но при этом иметь разную сложность. Обнаружилось, что иногда можно даже доказать теорему о существовании/несуществовании алгоритмов для той или иной задачи. Например, все (существующие и еще не придуманные) алгоритмы сортировки использующие сравнения обладают асимптотиками O(N logN) или хуже; или NP-полные задачи не разрешимы за O(N^p) (если P!=NP). Узнали, что лучшая асимптотика не всегда значит быстрее на практике, например алгоритм умножения матриц Коперсмита-Винограда).

22.01 “Структуры данных”

Обнаружили, что наивный алгоритм кросс-идентификации двух астрономических каталогов по координатам работает порядка сотен лет для каталогов из миллиарда записей. Опечалившись, мы решили изучить структуры данных (вектора, списки, деревья, хеш-таблицы) и алгоритмическую сложность типовых операций с ними (поиск, вставка, удаление, …). Познакомились с АВЛ деревьями: сбалансированными бинарными деревьями поиска.

29.01 “Структуры данных - II”

Разобрались с АВЛ деревьями. Посмотрели как можно обобщить бинарное дерево поиска для индексации многомерного пространства на примере Kd-деревьев. Узнали, что если для какого-то типа данных можно предложить хеш-функцию, то эти данные можно сложить в хеш-таблицу и искать из в среднем за константное время.

Немного поговорили про разные форматы данных, про устройство хранения данных в СУБД. Познакомились с понятием о реляционной алгебре.

5.02 “Анализ главных компонент”

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

Немного поговорили про статетстические свойста линейной оценки наименьших квадратов.

12.02 “Методы оптимизации - I”

Вспомнили определения глобального и локального минимумов функции, определение выпуклой функции. Сформулировали разные варианты задачи оптимизации: безусловной, условной, выпуклой, и т.п. Сформулировали разные варианты классификации алгоритмов оптимизации: по количеству требуемых данных (без производной, с производной, со второй производной), по сходимости (к стационарной точке 1 порядка, или 2 порядка), по скорости работы (линейная сходимость, квадратичная). Разобрали два простейших алгоритма: градиентный спуск и метод Ньютона.

19.02 “Методы оптимизации - II”

Познакомились с задачей оптимизации с ограничениями (задача математического программирования). Сформулировали критерии и признаки её решения. Изучили методы построения алгоритмов решения таких задач: штрафных (барьерных) функций и проекции градиента (на примере алгоритма поиска неотрицательного решения линейной задачи наименьших квадратов (NNLS)).

26.02 “Методы оптимизации - III”

Познакомились с методом Метрополиса, который позволяет генерировать выборку случайных векторов с известным распределением. Познакомились с методом имитации отжига, который получается если в методе Метрополиса постепенно снижать параметр “температура”.

Упомянули некорректные задачи, плохо обусловленные задачи, регуляризацию.

05.03 “Методы оптимизации - IV”

Познакомились с методом сопряженных градиентов, методами доверительных областей (trust region method), методом стохастического градиентого спуска.

09.04 “Метод максимального правдоподобия”

Познакомились с методом максимального правдоподобия и EM-алгоритмом.

Семинары

15.01

Приветливый тест.

22.01

Разбирали приветливый тест и вспоминали numpy.

29.01

Считали число различных слов в текстовом файле. Читали и писали CSV и netCDF файлики.

5.02

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

12.02

Разбирали метод градиентного спуска и метод Гаусса-Ньютона.

19.02

Разбирали алгоритм NNLS. Коррелировали содержание озона в атмосфере с активностью Солнца.

26.02

Попробовали метод “Truncated SVD” для взаимодействия с плохо обусловленными задачами линейных наименьших квадратов.

Писали самостоятельную по методу имитации отжига.

05.03

Разбирали домашнее задание с использованием готовых функций оптимизации из пакета scipy.

09.04

Разбирали EM-алгоритм.

Дополнительные материалы к курсу

Python

Install Python

Remember to use Python 3, 3.5 and later is good enough in 2019. You can check python version typing in console python3 --version or import sys; print(sys.version) in Python itself

All platforms

  • Anaconda Python distribution is a good choice for scientific Python programming on every platform. It includes a lot of pre-compiled numerical and scientific packages and conda package manager where you can find even more packages, like astropy or scikit-learn
  • Official Python distribution: good on Windows or macOS, when you like to build your environment from scratch.

macOS

Instead of official Python distribution I recommend to use Homebrew package manager, type brew install python

Linux

Probably you already have Python 3, check its version before start. If you haven’t use your Linus package manager to install

Source code editors for Python

  • IDLE: a simple Python source code editor. It is a part of Python standard library, so if you have Python, you probably have IDLE
  • Visual Studio Code (do not be confused with Visual Studio, they are two different products): a powerful source code editor
  • Spyder: the scientific Python development environment
  • PyCharm: a powerful Python IDE (integrated development environment). PyCharm is closed source product, but Community edition is free to use and every student and professor can ask for a free professional version

Git