Fundamental theorems

Fundamental theorems of Machine learning BS-4 MIPT course

Фундаментальные теоремы машинного обучения 1. Причины: Теорема - краткое сообщение о наиболее важных результатах области. 2. Теорема делает область математической в силу общности и строгости. 3. теоремы лежат в основе математики, они также играют центральную роль в её эстетике 4. Основная теорема линейной алгебры - не нужна (но нужна в контексте СВД) https://www.engineering.iastate.edu/~julied/classes/CE570/Notes/strangpaper.pdf 5. Основная теорема статистики - нужна. 6. Должна быть показана связь между различными областями машинного обучения 7. Вероятность, обоснованность, порождение и выбор, корректность по Адамару, снижение размерности, сходимость алгоритмов

How direct narration transform to fast narration?

How to find, state and prove theorems in your work?

Motivation and syllabus

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

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

Each lesson 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 own formulations and proofs
• Re-formulate significant messages of researchers and formulate these messages as theorems

Plan of a 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 \(\geq 14\)pt
  • include plots, diagrams, freehand drawings

The organization

• GitHub project to upload your text Intelligent-Systems-Phystech/FundamentalTheoremsML
  • to the group folder upload the pdf, tex, fig files named as
  • Surname2021Literature, Surname2021Research,
• See the Youtube channel 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

Student talks schedule

Speaker	References	Thesis work
Bishuk Anton	17.2 link	31.3 link
Weiser Kirill	17.2 link	31.3 link
Grebenkova Olga	24.2 link	7.4 link
Gunaev Ruslan	24.2 link	7.4 link
Zholobov Vladimir	3.3 link	14.4 link
Islamov Rustem	3.3 link	14.4 link
Pankratov Victor	10.3 link	21.4 link
Savelyev Nikolay	10.3 link	21.4 link
Filatov Andrey	10.3 link	21.4 link
Filippova Anastasia	17.3 link	28.4 link
Khar Alexandra	17.3 link	28.4 link
Khristolyubov Maxim	24.3 link	5.5 link
Shokorov Vyacheslav	24.3 link	5.5 link

Lecture topics

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

Theorem types

• Существование и единственность (NN)
• Универсальность
• Сходимость[1]
  • Поточечно
  • Равномерно
  • По мере
  • Почти всюду
  • По распределению
  • По вероятности
  • По Чезаро, Борделю, Пуассона, Эйлеру
  • Абсолютная
  • Условная
  • В среднем L1, среднеквадратичном L2
  • Сильная, слабая
• Оценки
  • Точечная
  • Не точечная
  • Состоятельная
  • Несмещенная
  • Эффективная
  • Omitted-variable bias
• almost sure, almost everywhere

Talks

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

Расписание лекций

Дата	Тема	Лектор	Ссылки
10 февраля	Вводное занятие (и Основная теорема статистики)	Стрижов, Потанин	link
17 февраля	Теорема сходимости перцептрона Ф.Розенблатта, Блока, Джозефа, Кестена	Марк Потанин	link
24 февраля	Теоремы Колмогорова и Арнольда, теорема об универсальном аппроксиматоре Цыбенко, теорема о глубоких нейросетях	Марк Потанин	link
10 марта	Берштейн - фон Мизес	Андрей Грабовой	link
17 марта	Берштейн - фон Мизес (продолжение)	Андрей Грабовой	link
24 марта	РАС обучаемость, теорема о том, что сжатие предполагает обучаемость	Андрей Грабовой	link
31 марта	Сходимость про вероятности при выборе моделей	Марк Потанин	link
7 апреля	Теорема о минимальной длине описания	Олег Бахтеев	link
14 апреля	Теорема о свертке (Фурье, свертка, автокорреляция) с примерами сверточных сетей	Филипп Никитин	link
21 апреля	Representer theorem, Schölkopf, Herbrich, and Smola	Андрей Грабовой	link
28 апреля	Обратная теорема Фурье, теорема Парсеваля (равномерная и неравномерная сходимость)	Филипп Никитин	link
5 мая	Вариационная аппроксимация, теорема о байесовском выборе моделей	Олег Бахтеев	link
12 мая	Разбор и обсуждение письменных работ: теоремы их доказательства (входящие в диплом)	Потанин, Стрижов
26 мая	Экзамен: схемы доказательства различных теорем (тест на время, как в гос по физике, и обсуждение)	Потанин, Адуенко, Бахтеев
	Теорема о бесплатных обедах в машинном обучении, Волперт	Радослав Нейчев
	Теорема схем, Холланд	Радослав Нейчев

References

1. Mathematical statistics by A.A. Borovkov, 1998
2. Learning Theory from First Principles by Francis Bach, 2021
3. Айзерман М.А., Браверман Э.М., Розоноэр Л.И. Метод потенциальных функций в теории обучения машин, 1970 (глава про сходимость)

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 (если вы чувствуете, что несет не туда)