Difference between revisions of "Fundamental theorems"

From Research management course
Jump to: navigation, search
 
(48 intermediate revisions by 2 users not shown)
Line 1: Line 1:
−
Fundamental theorems of Machine learning
+
{{#seo:
 +
|title=Fundamental Theorems of Machine Learning
 +
|titlemode=replace
 +
|keywords=Fundamental theorems of Machine Learning
 +
|description=The course Fundamental Theorems of Machine Learning studies techniques and practice of theorem formulations and proofs in machine learning.
 +
}}
 +
==Fundamental theorems of Machine Learning with proofs==
  
−
Фундаментальные теоремы машинного обучения
+
The goal of the course is to boost the quality of bachelor's and master's thesis works; to make the results of student scientific research well-founded. The course studies techniques and practice of theorem formulations and proofs in machine learning.  
−
1. Причины: Теорема - краткое сообщение о наиболее важных результатах области.
 
−
2. Теорема делает область математической в силу общности и строгости.
 
−
3. теоремы лежат в основе математики, они также играют центральную роль в её эстетике
 
−
4. Основная теорема линейной алгебры - не нужна (но нужна в контексте СВД) https://www.engineering.iastate.edu/~julied/classes/CE570/Notes/strangpaper.pdf
 
−
5. Основная теорема статистики - нужна.
 
−
6. Должна быть показана связь между различными областями машинного обучения
 
−
7. Вероятность, обоснованность, порождение и выбор, корректность по Адамару, снижение размерности, сходимость алгоритмов
 
  
−
{{Main|Численные методы обучения по прецедентам (практика, В.В. Стрижов)}}
+
Why one needs to convey an important message, a scientific result as a theorem?
−
{{TOCright}}
+
# Theorems are the most important messages in the field of research.  
−
==Мотивация и план курса==
+
# Theorems present results in the language of mathematics by generality and rigor.
 +
# Theorems are at the heart of mathematics and play a central role in its aesthetics.
  
−
Цель курса — повысить качество студенческих научных работ на кафедре, сделать статьи и дипломные работы более обоснованными, изучить технику и практику формулировок доказательства теорем в области машинного обучения. Результат курса - теоретически обоснованные сообщения дипломных работ бакалавра.
+
Theorems present the message immediately and leave reasoning after. The direct narration puts reason first and the results after that.
 +
* How does direct narration transform into fast narration?
 +
* How to find, state, and prove theorems in our work?
  
−
[http://bit.ly/MLTh_21 Короткая ссылка bit.ly/MLTh_21]
+
This course shows both narration styles. It refers to our educational study and our work experience:
−
===Каждое занятие курса===
+
# Educational mimic progression
−
# Доклад лектора — одна из фундаментальных теорем (40' = 30' + 10' обсуждение)
+
#* Definition <math>\to</math> (Axiom set)  <math>\to</math> Theorem  <math>\to</math> Proof <math>\to</math> Corollaries <math>\to</math> Examples <math>\to</math> Impact to applications
−
# Два студенческих доклада (20'=15'+5' обсуждение)
+
# Scientific discovery progression
 +
#* Application problems <math>\to</math> Problem generalisations  <math>\to</math>  Useful algebraic platform <math>\to</math>  Definitions <math>\to</math> Axiom set
 +
So in our practice, we mimic the first part of the progression, then learn to discover patterns and formulate theorems. The theoretical talks give us a series of good examples.
  
−
===Каждый студент делает два доклада===
+
==Theorems==
−
# С теоремой взятой из литературы, по которой выполняется дипломная работа
+
# Fundamental theorem of linear algebra [https://www.engineering.iastate.edu/~julied/classes/CE570/Notes/strangpaper.pdf S]
−
# С собственной теоремой, обосновывающей решение, предлагаемое в дипломное работе
+
# Singular values decomposition and spectral theorem [https://en.wikipedia.org/wiki/Spectral_theorem W]
 +
# Gauss–Markov-(Aitken) theorem [https://en.wikipedia.org/wiki/Gauss–Markov_theorem W]
 +
# Principal component analysis [https://en.wikipedia.org/wiki/Principal_component_analysis W]
 +
# Karhunen–Loève theorem [https://en.wikipedia.org/wiki/Karhunen–Loève_theorem W]
 +
# Kolmogorov–Arnold representation theorem [https://en.wikipedia.org/wiki/Kolmogorov–Arnold_representation_theorem W]
 +
# Universal approximation theorem by Cybenko [https://en.wikipedia.org/wiki/Universal_approximation_theorem W]
 +
# Deep neural network theorem [https://github.com/MarkPotanin/GeneticOpt/blob/master/Potanin2019NNStructure_APX.pdf Mark]
 +
# Inverse function theorem and Jacobian [https://en.wikipedia.org/wiki/Inverse_function_theorem W]
 +
# No free lunch theorem by Wolpert [https://en.wikipedia.org/wiki/No_free_lunch_theorem W]
 +
# RKHS by Aronszajn and Mercer's theorem [https://en.wikipedia.org/wiki/Mercer%27s_theorem W]
 +
# Representer theorem by Schölkopf, Herbrich, and Smola [https://en.wikipedia.org/wiki/Representer_theorem W]
 +
# Convolution theorem (FT, convolution, correlation with CNN examples) [https://en.wikipedia.org/wiki/Convolution_theorem W]
 +
# Fourier inversion theorem [https://en.wikipedia.org/wiki/Fourier_inversion_theorem W]
 +
# Wiener–Khinchin theorem about autocorrelation and spectral decomposition [https://en.wikipedia.org/wiki/Wiener–Khinchin_theorem W]
 +
# Parseval's theorem (and uniform, non-uniform convergence) [https://en.wikipedia.org/wiki/Parseval%27s_theorem W]
 +
# Probably approximately correct learning with the theorem about compression means learnability
 +
# Bernstein–von Mises theorem [https://en.wikipedia.org/wiki/Bernstein–von_Mises_theorem W]
 +
# Holland's schema theorem [https://en.wikipedia.org/wiki/Holland%27s_schema_theorem W]
 +
# Variational approximation
 +
# Convergence of random variables and Kloek's theorem [https://en.wikipedia.org/wiki/Big_O_in_probability_notation W]
 +
# Exponential family of distributions and Nelder's theorem
 +
# Multi-armed bandit theorem
 +
# Copulas and Sklar's theorem [https://en.wikipedia.org/wiki/Copula_(probability_theory) W]
 +
# Boosting theorem Freud, Shapire, 1996, 1995
 +
# Bootstrap theorem (statistical estimations): Ergodic theorem
  
−
===Приветствуются!===
+
===Each class contains===
−
* Варианты собственных формулировок и доказательств
+
# A lecturer's talk on one of fundamental theorems (<math>40' = 30' + 10'</math> discussion)
−
* Значимые высказывания ведущих исследователей, оформленные в виде теорем (пример изложения Кристофера Бишопа)
+
# Two students' talks  (each <math>20' = 15' + 5'</math> discussion)
  
−
===План изложения материала===
+
===Each student delivers two talks===
−
# Введение: основное сообщение теоремы в понятном (не обязательно строгом) изложении
+
# On a theorem, which is formulated in a paper from the list of student thesis work's references
−
# Вводная часть: определение терминов и сведения, необходимые для изложения (обозначения можно использовать авторские или [ссылка на обозначения Б.А.С.])
+
# On a theorem, which is formulated and proved by the student
−
# Формулировка и доказательство теоремы в '''строгом''' изложении (но можно отходить от авторского варианта, если это нужно для ясности)
 
−
# Значимость теоремы: ссылки или обзор методов и приложений, иллюстрирующих теорему
 
  
−
===Оформление===
+
===It is welcome to===
−
* В виде страницы текста, [https://drive.google.com/file/d/17AcostCAVSKfgK52MAelsSy_dC-sxDR4/view?usp=sharing пример], [https://www.overleaf.com/read/wsmczggkzpgj шаблон]
+
* Make variants of our formulations and proofs
−
* Слайды приветствуются, но необязательны
+
* Re-formulate significant messages of researchers and formulate these messages as theorems
−
* Очень приветствуются поясняющие рисунки, диаграммы, графики (можно от руки)
 
  
−
===Материалы курса===
+
===Plan of the talk===
−
* Проект на GitHub для загрузки докладов [https://github.com/Intelligent-Systems-Phystech/FundamentalTheoremsML  Intelligent-Systems-Phystech/FundamentalTheoremsML]
+
# Introduction: the main message briefly
−
** В папку группы 674 загрузить pdf, tex, fig с именем файла
+
# If necessary (it could be introduced during the talk)
−
** Surname2021Literature, Surname2021Research,
+
## Axiom sets
−
* Канал Youtube [https://www.youtube.com/channel/UC90B3Y_FbBRrRQk5TCiKgSA Machine Learning]
+
## Definitions
−
* Ссылка на сессию Zoom m1p.org/go_zoom
+
## Algebraic structures
 +
## Notations
 +
# Theorem formulation and exact proof
 +
## The author's variant of the proof could be ameliorated
 +
# Corollaries
 +
# Theorem significance and applications
  
−
===Оценивание===
+
===Typography===
−
* Доклад и материалы к нему 0-4 балла (по результатам сравнения работ)
+
* As one (or two) text page [https://drive.google.com/file/d/17AcostCAVSKfgK52MAelsSy_dC-sxDR4/view?usp=sharing example], [https://www.overleaf.com/read/wsmczggkzpgj template to download]
−
* Не по расписанию делим на два
+
* Please
−
* Экзамен 2 балла
+
** set the font size <math>\geqslant 14</math>pt
 +
** include plots, diagrams, freehand drawings
  
−
==Расписание докладов==
+
===The organization===
−
{|class="wikitable"
+
* GitHub project to upload your text [https://github.com/Intelligent-Systems-Phystech/FundamentalTheoremsML  Intelligent-Systems-Phystech/FundamentalTheoremsML] to the group folder upload the pdf, tex, fig files named as Surname2021Literature, Surname2021Research
 +
* See the Youtube channel [https://www.youtube.com/channel/UC90B3Y_FbBRrRQk5TCiKgSA Machine Learning]
 +
* Spring semester, Wednesdays 14:30 at Zoom m1p.org/go_zoom
 +
 
 +
===Scoring===
 +
* Talks and text 0-4 points, according to comparison
 +
* Out-of-schedule drops a half
 +
* The exam 2 points: schemes of proof of various theorems
 +
** time-limit test (as Physics state exam) and discussion
 +
** theorem formulation and poof scheme are hand-written
 +
** two random theorems from the list below, 10 min to write the text
 +
 
 +
==Theorem types==
 +
<!--* Должна быть показана связь между различными областями машинного обучения
 +
* Вероятность, обоснованность, порождение и выбор, корректность по Адамару, снижение размерности, сходимость алгоритмов -->
 +
* Uniqueness, existence
 +
* Universality
 +
* Convergence <!--[https://www.youtube.com/watch?v=Ajar_6MAOLw] -->
 +
<!--Поточечно
 +
**Равномерно
 +
**По мере
 +
**Почти всюду
 +
**По распределению
 +
**По вероятности
 +
**По Чезаро, Борделю, Пуассона, Эйлеру
 +
**Абсолютная
 +
**Условная
 +
**В среднем L1, среднеквадратичном L2
 +
**Сильная, слабая
 +
*Оценки
 +
**Точечная
 +
**Не точечная
 +
**Состоятельная
 +
**Несмещенная
 +
**Эффективная
 +
**Omitted-variable bias
 +
* Almost sure, almost everywhere
 +
-->
 +
* Complexity
 +
* Properties of estimations
 +
* Bounds
 +
 
 +
==Schedule==
 +
Spring semester 2021
 +
===Student talks===
 +
{|class = "wikitable"
 
|-
 
|-
−
! Докладчик
+
! Speaker
−
! Литература
+
! References
−
! Диплом
 
 
|-
 
|-
−
|Бишук Антон
+
| Bishuk Anton
−
|17.2 [https://github.com/ApostolAnt/Projects/blob/master/______.pdf link]
+
| 17.2 [https://github.com/ApostolAnt/Projects/blob/master/______.pdf link]
−
|31.3 link
 
 
|-
 
|-
−
|Вайсер Кирилл 

+
| Weiser Kirill
−
|17.2 [https://github.com/Nerkan78/IntelligentSystems/blob/main/Diploma/VayserKirill2020/MatheronRule.pdf link]
+
| 17.2 [https://github.com/Nerkan78/IntelligentSystems/blob/main/Diploma/VayserKirill2020/MatheronRule.pdf link], [https://github.com/Nerkan78/IntelligentSystems/blob/main/Diploma/VayserKirill2020/ErrorAnalysis.pdf link]
−
|31.3 [https://github.com/Nerkan78/IntelligentSystems/blob/main/Diploma/VayserKirill2020/ErrorAnalysis.pdf link]
 
 
|-
 
|-
−
|Гребенькова Ольга 

+
| Grebenkova Olga
−
|24.2 [https://github.com/Intelligent-Systems-Phystech/Grebenkova-BS-Thesis/raw/main/ELBo.pdf link]
+
| 24.2 [https://github.com/Intelligent-Systems-Phystech/Grebenkova-BS-Thesis/raw/main/ELBo.pdf link]
−
|7.4 link
 
 
|-
 
|-
−
|Гунаев Руслан
+
| Gunaev Ruslan
−
|24.2 [https://github.com/Gunaev/Gunaev_BS-thesis/blob/main/th_diplom.pdf link]
+
| 24.2 [https://github.com/Gunaev/Gunaev_BS-thesis/blob/main/th_diplom.pdf link]
−
|7.4 link

 
 
|-
 
|-
−
|Жолобов Владимир 

+
| Zholobov Vladimir
−
|3.3 [https://github.com/Intelligent-Systems-Phystech/Zholobov-BS-Thesis/blob/main/Zholobov_thesis.pdf link]
+
| 3.3 [https://github.com/Intelligent-Systems-Phystech/Zholobov-BS-Thesis/blob/main/Zholobov_thesis.pdf link]
−
|14.4 link
 
 
|-
 
|-
−
|Исламов Рустем
+
| Islamov Rustem
−
|3.3 [https://github.com/Intelligent-Systems-Phystech/Islamov-BS-Thesis/blob/main/Fundamental%20theorems%20on%20Machine%20Learning/First%20report/Stochastic%20Newton%20method.pdf link]
+
| 3.3 [https://github.com/Intelligent-Systems-Phystech/Islamov-BS-Thesis/blob/main/Fundamental%20theorems%20on%20Machine%20Learning/First%20report/Stochastic%20Newton%20method.pdf link]
−
|14.4 link
 
 
|-
 
|-
−
|Панкратов Виктор  

+
| Pankratov Victor
−
|10.3 [https://github.com/Intelligent-Systems-Phystech/Pankratov_BS_Thesis/blob/main/link1.pdf link]
+
| 10.3 [https://github.com/Intelligent-Systems-Phystech/Pankratov_BS_Thesis/blob/main/link1.pdf link]
−
|21.4 link
 
 
|-
 
|-
−
|Савельев Николай
+
| Savelyev Nikolay
−
|10.3 [https://github.com/Intelligent-Systems-Phystech/Savelev-BS-Thesis/raw/main/Prediction_Learning_and_Games-%D1%81%D1%82%D1%80%D0%B0%D0%BD%D0%B8%D1%86%D1%8B-18-21.pdf link]
+
| 10.3 [https://github.com/Intelligent-Systems-Phystech/Savelev-BS-Thesis/raw/main/Prediction_Learning_and_Games-B-18-21.pdf link]
−
|21.4 link
 
 
|-
 
|-
−
|Филатов Андрей
+
| Filatov Andrey
−
|10.3 [https://github.com/Intelligent-Systems-Phystech/Filatov-BS-Thesis/blob/main/Fundamental%20Theorems/Theorem.pdf link]
+
| 10.3 [https://github.com/Intelligent-Systems-Phystech/Filatov-BS-Thesis/blob/main/Fundamental%20Theorems/Theorem.pdf link]
−
|21.4 link
 
 
|-
 
|-
−
|Филиппова Анастасия 

+
| Filippova Anastasia
−
|17.3 link
+
| 17.3 link
−
|28.4 link
 
 
|-
 
|-
−
|Харь Александра 

+
| Khar Alexandra
−
|17.3 [https://github.com/Intelligent-Systems-Phystech/Khar-BS-Thesis/blob/main/otchet_1.pdf link]
+
| 17.3 [https://github.com/Intelligent-Systems-Phystech/Khar-BS-Thesis/blob/main/otchet_1.pdf link]
−
|28.4 link
 
 
|-
 
|-
−
|Христолюбов Максим
+
| Khristolyubov Maxim
−
|24.3 [https://github.com/Intelligent-Systems-Phystech/Khristolyubov-BS-Thesis/blob/main/paper/Proof_of_the_theorem.pdf link]
+
| 24.3 [https://github.com/Intelligent-Systems-Phystech/Khristolyubov-BS-Thesis/blob/main/paper/Proof_of_the_theorem.pdf link]
−
|5.5 link
 
 
|-
 
|-
−
|Шокоров Вячеслав 

+
| Shokorov Vyacheslav
−
|24.3 [https://github.com/Intelligent-Systems-Phystech/Shokorov-BS-Thesis/blob/main/report/VKR_Theorem.pdf link]
+
| 24.3 [https://github.com/Intelligent-Systems-Phystech/Shokorov-BS-Thesis/blob/main/report/VKR_Theorem.pdf link]
−
|5.5 link
 
 
|-
 
|-
 
|}
 
|}
  
−
==Lecture topics==
+
===Invited talks===
−
 
 
−
# Singular values decomposition and spectral theorem [https://en.wikipedia.org/wiki/Spectral_theorem W]
 
−
# Gauss–Markov-(Aitken) theorem [https://en.wikipedia.org/wiki/Gauss–Markov_theorem W]
 
−
# Principal component analysis [https://en.wikipedia.org/wiki/Principal_component_analysis W]
 
−
# Karhunen–Loève theorem [https://en.wikipedia.org/wiki/Karhunen–Loève_theorem W]
 
−
# Kolmogorov–Arnold representation theorem [https://en.wikipedia.org/wiki/Kolmogorov–Arnold_representation_theorem W]
 
−
# Universal approximation theorem by Cybenko [https://en.wikipedia.org/wiki/Universal_approximation_theorem W]
 
−
# Deep neural network theorem
 
−
# No free lunch theorem by Wolpert [https://en.wikipedia.org/wiki/No_free_lunch_theorem W]
 
−
# RKHS by Aronszajn and Mercer's theorem [https://en.wikipedia.org/wiki/Mercer%27s_theorem W]
 
−
# Representer theorem by Schölkopf, Herbrich, and Smola [https://en.wikipedia.org/wiki/Representer_theorem W]
 
−
# Convolution theorem (FT, convolution, correlation with CNN examples) [https://en.wikipedia.org/wiki/Convolution_theorem W]
 
−
# Fourier inversion theorem [https://en.wikipedia.org/wiki/Fourier_inversion_theorem W]
 
−
# Wiener–Khinchin theorem about autocorrelation and spectral decomposition [https://en.wikipedia.org/wiki/Wiener–Khinchin_theorem W]
 
−
# Parseval's theorem (and uniform, non-uniform convergence) [https://en.wikipedia.org/wiki/Parseval%27s_theorem W]
 
−
# Probably approximately correct learning with the theorem about compression means learnability
 
−
# Bernstein–von Mises theorem [https://en.wikipedia.org/wiki/Bernstein–von_Mises_theorem W]
 
−
# Holland's schema theorem [https://en.wikipedia.org/wiki/Holland%27s_schema_theorem W]
 
−
# Variational approximation
 
−
# Convergence of random variables and Kloek's theorem [https://en.wikipedia.org/wiki/Big_O_in_probability_notation W]
 
−
# Exponential family of distributions and Nelder's theorem
 
−
# Multi-armed bandit theorem
 
−
# Copulas and Sklar's theorem [https://en.wikipedia.org/wiki/Copula_(probability_theory) W]
 
−
 
 
−
== Talks ==
 
−
# Three works by Greg Yang [https://arxiv.org/pdf/1910.12478.pdf arXiv:1910.12478], [https://arxiv.org/pdf/2006.14548 arXiv:2006.14548], [https://arxiv.org/pdf/2009.10685.pdf arXiv:2009.10685] [https://www.youtube.com/watch?v=kc9ll6B-xVU&list=PLt1IfGj6-_-ewBQJDVMJOJNlW5AbY6D3p&index=4&fbclid=IwAR3kIUQZWsh9j_Xp2TYb5ZmcsH7nFDIpCuRnmeoxoRJyPuxKvFyxTRI3ypY Youtube Rus]
 
−
# Theorems on flows by Johann Brehmera and Kyle Cranmera [https://arxiv.org/pdf/2003.13913v2.pdf arXiv:2003.13913v2]
 
−
 
 
−
==Расписание лекций==
 
 
{|class="wikitable"
 
{|class="wikitable"
 
|-
 
|-
−
! Дата  
+
<!--! Дата  
−
! Тема
+
! Тема-->
−
! Лектор
+
! Speaker
−
! Ссылки
+
! Link
 
|-
 
|-
−
|10 февраля
+
<!--|10 февраля
−
|Вводное занятие (и Основная теорема статистики)
+
|Вводное занятие (и Основная теорема статистики)-->
−
|Стрижов, Потанин
+
| Strijov, Potanin
−
|[https://drive.google.com/file/d/17AcostCAVSKfgK52MAelsSy_dC-sxDR4/view?usp=sharing link]
+
|10.2 [https://drive.google.com/file/d/17AcostCAVSKfgK52MAelsSy_dC-sxDR4/view?usp=sharing link]
 
|-
 
|-
−
|17 февраля
+
<!--|17 февраля
−
|Теорема сходимости перцептрона Ф.Розенблатта, Блока, Джозефа, Кестена
+
|Теорема сходимости перцептрона Ф.Розенблатта, Блока, Джозефа, Кестена-->
−
|Марк Потанин
+
| Mark Potanin
−
|[https://drive.google.com/file/d/1Pu8mvexKkO45ED4MWSH-sZDusNNTgMpC/view?usp=sharing link]
+
|17.2 [https://drive.google.com/file/d/1Pu8mvexKkO45ED4MWSH-sZDusNNTgMpC/view?usp=sharing link]
 
|-
 
|-
−
|24 февраля
+
<!--|24 февраля
−
|Теоремы Колмогорова и Арнольда, теорема об универсальном аппроксиматоре Цыбенко, теорема о глубоких нейросетях  
+
|Теоремы Колмогорова и Арнольда, теорема об универсальном аппроксиматоре Цыбенко, теорема о глубоких нейросетях -->
−
|Марк Потанин
+
|Mark Potanin
−
|[https://drive.google.com/file/d/1Thm73TYyLXhoHNA_4uhyFB9Im26Ctjxp/view?usp=sharing link]
+
|24.2 [https://drive.google.com/file/d/1Thm73TYyLXhoHNA_4uhyFB9Im26Ctjxp/view?usp=sharing link]
 
|-
 
|-
−
|10 марта
+
<!--|10 марта
−
|[[Media:BershteinFonMises.pdf|Берштейн - фон Мизес]]
+
|[[Media:BershteinFonMises.pdf|Берштейн - фон Мизес]]-->
−
|Андрей Грабовой
+
|Andriy Grabovyi
−
|[[Media:BershteinFonMises.pdf|link]]
+
|10.3 [http://www.machinelearning.ru/wiki/images/3/33/BershteinFonMises.pdf link]
 
|-
 
|-
−
|17 марта
+
<!--|17 марта
−
|[[Media:BershteinFonMises.pdf|Берштейн - фон Мизес]] (продолжение)
+
|[[Media:BershteinFonMises.pdf|Берштейн - фон Мизес]] (продолжение)-->
−
|Андрей Грабовой
+
|Andriy Grabovyi
−
|[[Media:BershteinFonMises.pdf|link]]
+
|17.3 [http://www.machinelearning.ru/wiki/images/3/33/BershteinFonMises.pdf link]
 
|-
 
|-
−
|24 марта  
+
<!--|24 марта  
−
|[[Media:PAC_learning_compress.pdf|РАС обучаемость, теорема о том, что сжатие предполагает обучаемость]]
+
|[[Media:PAC_learning_compress.pdf|РАС обучаемость, теорема о том, что сжатие предполагает обучаемость]]-->
−
|Андрей Грабовой
+
|Andriy Grabovyi
−
|[[Media:PAC_learning_compress.pdf|link]]
+
|24.3 [http://www.machinelearning.ru/wiki/images/b/ba/PAC_learning_compress.pdf link]
 
|-
 
|-
−
|31 марта   
+
<!--|31 марта   
−
|Сходимость про вероятности при выборе моделей
+
|Сходимость про вероятности при выборе моделей-->
−
|Марк Потанин
+
|Mark Potanin
−
|[https://drive.google.com/file/d/1-rtOJtjivRs0TwOga8-MLaBEzCcUyD0H/view?usp=sharing link]
+
|31.3 [https://drive.google.com/file/d/1-rtOJtjivRs0TwOga8-MLaBEzCcUyD0H/view?usp=sharing link]
 
|-
 
|-
−
|7 апреля  
+
<!--|7 апреля  
−
|Теорема о минимальной длине описания <!--Метрические пространства: RKHS Аронжайн, теорема Мерсера-->
+
|Теорема о минимальной длине описания Метрические пространства: RKHS Аронжайн, теорема Мерсера
−
|Олег Бахтеев <!--Алексей Гончаров-->
+
|Oleg Bakhteev
−
| link
+
|7.4 link
 
|-
 
|-
 
|14 апреля  
 
|14 апреля  
 
|Теорема о свертке (Фурье, свертка, автокорреляция) с примерами сверточных сетей  
 
|Теорема о свертке (Фурье, свертка, автокорреляция) с примерами сверточных сетей  
−
|Филипп Никитин
+
|Philipp Nikitin
−
| link
+
|14.4 link
 
|-
 
|-
 
|21 апреля
 
|21 апреля
 
|Representer theorem, Schölkopf, Herbrich, and Smola  
 
|Representer theorem, Schölkopf, Herbrich, and Smola  
−
|Андрей Грабовой
+
|Andriy Grabovyi
−
| link
+
|21.4 link
 
|-
 
|-
 
|28 апреля
 
|28 апреля
 
|Обратная теорема Фурье, теорема Парсеваля (равномерная и неравномерная сходимость)
 
|Обратная теорема Фурье, теорема Парсеваля (равномерная и неравномерная сходимость)
−
|Филипп Никитин
+
|Philipp Nikitin
−
| link
+
|28.4 link
 
|-
 
|-
−
|5 мая  
+
5 мая  
 
|Вариационная аппроксимация, теорема о байесовском выборе моделей
 
|Вариационная аппроксимация, теорема о байесовском выборе моделей
−
|Олег Бахтеев
+
|Oleg Bakhteev
−
| link
+
|5.5 link
 
|-
 
|-
−
|12 мая  
+
12 мая  
 
|Разбор и обсуждение письменных работ: теоремы их доказательства (входящие в диплом)
 
|Разбор и обсуждение письменных работ: теоремы их доказательства (входящие в диплом)
−
|Потанин, Стрижов
+
| Potanin, Strijov
−
|  
+
|12.5 Discussion
 
|-
 
|-
−
|26 мая  
+
26 мая  
 
|Экзамен: схемы доказательства различных теорем (тест на время, как в гос по физике, и обсуждение)
 
|Экзамен: схемы доказательства различных теорем (тест на время, как в гос по физике, и обсуждение)
−
|Потанин, Адуенко, Бахтеев
+
|Potanin, Aduenko, Bakhteev
−
|  
+
|26.5 Exam
 
|-
 
|-
−
|
+
 
 
|Теорема о бесплатных обедах в машинном обучении, Волперт
 
|Теорема о бесплатных обедах в машинном обучении, Волперт
 
|Радослав Нейчев  
 
|Радослав Нейчев  
Line 229: Line 262:
 
|Радослав Нейчев  
 
|Радослав Нейчев  
 
|  
 
|  
−
|-
+
|--->
 
|}
 
|}
 +
 +
===Out of schedule ===
 +
# Three works by Greg Yang [https://arxiv.org/pdf/1910.12478.pdf arXiv:1910.12478], [https://arxiv.org/pdf/2006.14548 arXiv:2006.14548], [https://arxiv.org/pdf/2009.10685.pdf arXiv:2009.10685] [https://www.youtube.com/watch?v=kc9ll6B-xVU&list=PLt1IfGj6-_-ewBQJDVMJOJNlW5AbY6D3p&index=4&fbclid=IwAR3kIUQZWsh9j_Xp2TYb5ZmcsH7nFDIpCuRnmeoxoRJyPuxKvFyxTRI3ypY Youtube Rus]
 +
# Theorems on flows by Johann Brehmera and Kyle Cranmera [https://arxiv.org/pdf/2003.13913v2.pdf arXiv:2003.13913v2]
  
 
==References==
 
==References==
 +
 +
# Mathematical statistics by A.A. Borovkov, 1998
 +
# [https://www.di.ens.fr/~fbach/ltfp_book.pdf Learning Theory from First Principles] by Francis Bach, 2021 <!--https://www.di.ens.fr/~fbach/learning_theory_class/index.html-->
 +
# [https://cs.uwaterloo.ca/~y328yu/classics/kernel.pdf Theoretical foundations of potential function method in pattern recognition] by M. A. Aizerman, E. M. Braverman, and L. I. Rozonoer // Avtomatica i Telemekhanica, 1964. Vol. 25, pp. 917-936.
 +
<!-- Айзерман М.А., Браверман Э.М., Розоноэр Л.И. Метод потенциальных функций в теории обучения машин, 1970 (глава про сходимость)-->
 +
 
===Proof techniques===
 
===Proof techniques===
 
# [https://www.birmingham.ac.uk/Documents/college-eps/college/stem/Student-Summer-Education-Internships/Proof-and-Reasoning.pdf Proofs and Mathematical Reasoning by Agata Stefanowicz, 2014]
 
# [https://www.birmingham.ac.uk/Documents/college-eps/college/stem/Student-Summer-Education-Internships/Proof-and-Reasoning.pdf Proofs and Mathematical Reasoning by Agata Stefanowicz, 2014]
−
# Mathematical statistics by A.A. Borovkov, 1998
 
 
# The nuts and bolts of proofs by Antonella Cupillari, 2013
 
# The nuts and bolts of proofs by Antonella Cupillari, 2013
 +
# Theorems, Corollaries, Lemmas, and Methods of Proof by Richard J. Rossi, 1956
 +
#  Problem Books in Mathematics by P.R. Halmos (editor), 1990
 +
# Les contre-exemples en mathématique par Bertrand Hauchecorne, 2007
 
# [http://fulviofrisone.com/attachments/article/452/Kolmogorov%20And%20Mathematical%20Logic.pdf Kolmogorov and Mathematical Logic] by Vladimir A. Uspensky // The Journal of Symbolic Logic, Vol. 57, No. 2 (Jun., 1992), 385-412.  
 
# [http://fulviofrisone.com/attachments/article/452/Kolmogorov%20And%20Mathematical%20Logic.pdf Kolmogorov and Mathematical Logic] by Vladimir A. Uspensky // The Journal of Symbolic Logic, Vol. 57, No. 2 (Jun., 1992), 385-412.  
 
# [http://www.vixri.com/d/Uspenskij%20V.A.%20_Chto%20takoe%20aksiomaticheskij%20metod.pdf Что такое аксиоматический метод?] В.А. Успенский, 2001
 
# [http://www.vixri.com/d/Uspenskij%20V.A.%20_Chto%20takoe%20aksiomaticheskij%20metod.pdf Что такое аксиоматический метод?] В.А. Успенский, 2001
 
# [http://lpcs.math.msu.su/~zolin/ax/pdf/2015_Axiomatic_method_Zolin_Lectures.pdf Аксиоматический метод]. Е.Е. Золин, 2015
 
# [http://lpcs.math.msu.su/~zolin/ax/pdf/2015_Axiomatic_method_Zolin_Lectures.pdf Аксиоматический метод]. Е.Е. Золин, 2015
−
# Айзерман М.А., Браверман Э.М., Розоноэр Л.И. Метод потенциальных функций в теории обучения машин, 1970 (глава про сходимость)
 
  
 
===Methodology===
 
===Methodology===
Line 249: Line 293:
 
# [https://mathvault.ca/math-glossary/ The definitive glossary of higher mathematical jargon] by Math Vault, 2015
 
# [https://mathvault.ca/math-glossary/ The definitive glossary of higher mathematical jargon] by Math Vault, 2015
 
# The definitive guide to learning higher mathematics: 10 principles to mathematical transcendence by Math Vault, 2020
 
# The definitive guide to learning higher mathematics: 10 principles to mathematical transcendence by Math Vault, 2020
 +
# [https://en.wikipedia.org/wiki/List_of_mathematical_jargon List of mathematical jargon] on Wikipedia
 
# [https://cs9.pikabu.ru/post_img/big/2018/05/21/9/1526915408141416733.jpg Пикабу. Типичные методы доказательства, 2018] (если вы чувствуете, что несет не туда)
 
# [https://cs9.pikabu.ru/post_img/big/2018/05/21/9/1526915408141416733.jpg Пикабу. Типичные методы доказательства, 2018] (если вы чувствуете, что несет не туда)

Latest revision as of 22:20, 11 February 2024

Fundamental theorems of Machine Learning with proofs

The goal of the course is to boost the quality of bachelor's and master's thesis works; to make the results of student scientific research well-founded. The course studies techniques and practice of theorem formulations and proofs in machine learning.

Why one needs to convey an important message, a scientific result as a theorem?

  1. Theorems are the most important messages in the field of research.
  2. Theorems present results in the language of mathematics by generality and rigor.
  3. Theorems are at the heart of mathematics and play a central role in its aesthetics.

Theorems present the message immediately and leave reasoning after. The direct narration puts reason first and the results after that.

  • How does direct narration transform into fast narration?
  • How to find, state, and prove theorems in our work?

This course shows both narration styles. It refers to our educational study and our work experience:

  1. Educational mimic progression
    • Definition \(\to\) (Axiom set) \(\to\) Theorem \(\to\) Proof \(\to\) Corollaries \(\to\) Examples \(\to\) Impact to applications
  2. Scientific discovery progression
    • Application problems \(\to\) Problem generalisations \(\to\) Useful algebraic platform \(\to\) Definitions \(\to\) Axiom set

So in our practice, we mimic the first part of the progression, then learn to discover patterns and formulate theorems. The theoretical talks give us a series of good examples.

Theorems

  1. Fundamental theorem of linear algebra S
  2. Singular values decomposition and spectral theorem W
  3. Gauss–Markov-(Aitken) theorem W
  4. Principal component analysis W
  5. Karhunen–Loève theorem W
  6. Kolmogorov–Arnold representation theorem W
  7. Universal approximation theorem by Cybenko W
  8. Deep neural network theorem Mark
  9. Inverse function theorem and Jacobian W
  10. No free lunch theorem by Wolpert W
  11. RKHS by Aronszajn and Mercer's theorem W
  12. Representer theorem by Schölkopf, Herbrich, and Smola W
  13. Convolution theorem (FT, convolution, correlation with CNN examples) W
  14. Fourier inversion theorem W
  15. Wiener–Khinchin theorem about autocorrelation and spectral decomposition W
  16. Parseval's theorem (and uniform, non-uniform convergence) W
  17. Probably approximately correct learning with the theorem about compression means learnability
  18. Bernstein–von Mises theorem W
  19. Holland's schema theorem W
  20. Variational approximation
  21. Convergence of random variables and Kloek's theorem W
  22. Exponential family of distributions and Nelder's theorem
  23. Multi-armed bandit theorem
  24. Copulas and Sklar's theorem W
  25. Boosting theorem Freud, Shapire, 1996, 1995
  26. Bootstrap theorem (statistical estimations): Ergodic theorem

Each class contains

  1. A lecturer's talk on one of fundamental theorems (\(40' = 30' + 10'\) discussion)
  2. Two students' talks (each \(20' = 15' + 5'\) discussion)

Each student delivers two talks

  1. On a theorem, which is formulated in a paper from the list of student thesis work's references
  2. On a theorem, which is formulated and proved by the student

It is welcome to

  • Make variants of our formulations and proofs
  • Re-formulate significant messages of researchers and formulate these messages as theorems

Plan of the talk

  1. Introduction: the main message briefly
  2. If necessary (it could be introduced during the talk)
    1. Axiom sets
    2. Definitions
    3. Algebraic structures
    4. Notations
  3. Theorem formulation and exact proof
    1. The author's variant of the proof could be ameliorated
  4. Corollaries
  5. Theorem significance and applications

Typography

  • As one (or two) text page example, template to download
  • Please
    • set the font size \(\geqslant 14\)pt
    • include plots, diagrams, freehand drawings

The organization

Scoring

  • Talks and text 0-4 points, according to comparison
  • Out-of-schedule drops a half
  • The exam 2 points: schemes of proof of various theorems
    • time-limit test (as Physics state exam) and discussion
    • theorem formulation and poof scheme are hand-written
    • two random theorems from the list below, 10 min to write the text

Theorem types

  • Uniqueness, existence
  • Universality
  • Convergence
  • Complexity
  • Properties of estimations
  • Bounds

Schedule

Spring semester 2021

Student talks

Speaker References
Bishuk Anton 17.2 link
Weiser Kirill 17.2 link, link
Grebenkova Olga 24.2 link
Gunaev Ruslan 24.2 link
Zholobov Vladimir 3.3 link
Islamov Rustem 3.3 link
Pankratov Victor 10.3 link
Savelyev Nikolay 10.3 link
Filatov Andrey 10.3 link
Filippova Anastasia 17.3 link
Khar Alexandra 17.3 link
Khristolyubov Maxim 24.3 link
Shokorov Vyacheslav 24.3 link

Invited talks

Speaker Link
Strijov, Potanin 10.2 link
Mark Potanin 17.2 link
Mark Potanin 24.2 link
Andriy Grabovyi 10.3 link
Andriy Grabovyi 17.3 link
Andriy Grabovyi 24.3 link
Mark Potanin 31.3 link

Out of schedule

  1. Three works by Greg Yang arXiv:1910.12478, arXiv:2006.14548, arXiv:2009.10685 Youtube Rus
  2. Theorems on flows by Johann Brehmera and Kyle Cranmera arXiv:2003.13913v2

References

  1. Mathematical statistics by A.A. Borovkov, 1998
  2. Learning Theory from First Principles by Francis Bach, 2021
  3. Theoretical foundations of potential function method in pattern recognition by M. A. Aizerman, E. M. Braverman, and L. I. Rozonoer // Avtomatica i Telemekhanica, 1964. Vol. 25, pp. 917-936.

Proof techniques

  1. Proofs and Mathematical Reasoning by Agata Stefanowicz, 2014
  2. The nuts and bolts of proofs by Antonella Cupillari, 2013
  3. Theorems, Corollaries, Lemmas, and Methods of Proof by Richard J. Rossi, 1956
  4. Problem Books in Mathematics by P.R. Halmos (editor), 1990
  5. Les contre-exemples en mathématique par Bertrand Hauchecorne, 2007
  6. Kolmogorov and Mathematical Logic by Vladimir A. Uspensky // The Journal of Symbolic Logic, Vol. 57, No. 2 (Jun., 1992), 385-412.
  7. Что такое аксиоматический метод? В.А. Успенский, 2001
  8. Аксиоматический метод. Е.Е. Золин, 2015

Methodology

  1. Introduction to Metamathematics by Stephen Cole Kleene, 1950
  2. Science and Method by Henry Poincare, 1908
  3. A Summary of Scientific Method by Peter Kosso, 2011
  4. Being a Researcher: An Informatics Perspective by Carlo Ghezzi, 2020
  5. The definitive glossary of higher mathematical jargon by Math Vault, 2015
  6. The definitive guide to learning higher mathematics: 10 principles to mathematical transcendence by Math Vault, 2020
  7. List of mathematical jargon on Wikipedia
  8. Пикабу. Типичные методы доказательства, 2018 (если вы чувствуете, что несет не туда)
Retrieved from ‘https://m1p.org/index.php?title=Fundamental_theorems&oldid=1395’