Forwarded from Sergey Kucherenko
любопытный набор. Если кому-то, как и мне, стали интересны детали про синтетическую теорию веросятности, вот немножко:
- https://etda.libraries.psu.edu/files/final_submissions/20192
- http://tobiasfritz.science/2019/cps_workshop/slides/simpson.pdf
- https://www.youtube.com/watch?v=XtsBsLM9ofk
- https://etda.libraries.psu.edu/files/final_submissions/20192
- http://tobiasfritz.science/2019/cps_workshop/slides/simpson.pdf
- https://www.youtube.com/watch?v=XtsBsLM9ofk
Pen and paper exercises in machine learning
https://arxiv.org/abs/2206.13446
https://github.com/michaelgutmann/ml-pen-and-paper-exercises
https://arxiv.org/abs/2206.13446
https://github.com/michaelgutmann/ml-pen-and-paper-exercises
👍1👎1
Forwarded from AlexTCH
https://unsound-workshop.org/
A workshop at SPLASH 2022 about unsoundness in specifications, systems or expectations. CFP is open till 2022-09-01 (but no formal publication).
Expecting lots of Rust folks. 😁
A workshop at SPLASH 2022 about unsoundness in specifications, systems or expectations. CFP is open till 2022-09-01 (but no formal publication).
Expecting lots of Rust folks. 😁
👍1👎1🤣1
Forwarded from Covalue
Papayannopoulos, [2020] "Unrealistic Models for Realistic Computations: How Idealisations Help Represent Mathematical Structures and Found Scientific Computing"
Научные вычисления (scientific computing / computational science), т.е. общие техники для всех вычислительных ветвей эмпирических наук, можно разделить на символьные и численные методы, в статье идёт речь о последних. Т.к. численные методы работают с непрерывными значениями (действительными/комплексными числами и их обобщениями), появляются вопросы сходимости, устойчивости и вычислимости алгоритмов над плавающей арифметикой (в частности проблема накопления ошибок округления). Для изучения этих вопросов нужен математический фреймворк вычислений над несчетными множествами, из наиболее популярных это BSS model (aka Real-RAM) и computable analysis (aka Type Two Effectivity), причем друг с другом они несовместимы. Статья посвящена разбору этих двух подходов.
CA/TTE - более фундаментальная и "низкоуровневая" теория, это разновидность матанализа, где сохраняется классическая теория, но дополнительно учитываются вычислительные представления объектов через бесконечные аппроксимации. Как правило, это делается через работу с некоторыми разновидностями машин Тюринга (с оракулом или более сложной машинерией репрезентаций). Её появление можно отследить к трудам Бореля, Банаха и Тюринга 1910-30х годов, где рассматривались вычислимые подмножества R (эта идея получила развитие в Марковской школе конструктивизма/синтетической вычислимости). Более поздние подходы ("Хагенская школа") перешли к рассмотрению всего R (ключевая идея TTE). В этой модели вычислимые функции должны быть непрерывными - как следствие, мы теряем возможность полноценно использовать "точечные" функции сравнения и округления (ср. https://twitter.com/andrejbauer/status/1400172747930718209).
BSS - модель вычислений с идеализированной RAM-машиной, способной хранить в памяти произвольные числа (в т.ч. и точные значения действительных) и мгновенно производить арифметические операции над ними. Тут не возникает проблем с разрывными функциями, но усложняется работа с функциями алгебраическими и трансцендентными (с которыми нет проблемы у CA), начиная с банальных квадратных корней.
Какой же фреймворк предпочтителен? BSS менее реалистична и хуже подходит для работы с ошибками округления и плохо обусловленными функциями, но тем не менее довольно популярна - она моделирует устойчивые алгоритмы (т.е. не вносит собственных ошибок) и позволяет работать с оценкой их сложности. Также BSS ближе к алгоритмам плавающей арифметики в том, что имеет фиксированную стоимость операций (в отличии от CA, где стоимость зависит от входа). С другой стороны, CA подходит для более глубоких вопросов вычислимости (в т.ч., например, квантовой) и работы с "плохо ведущими себя" функциями, но создает больше проблем при анализе стоимости и работе с хорошо изученными численными алгоритмами.
В конце статья проводит аналогию с физическими моделями, облегчающими работу за счет нереалистичных упрощений, например, плавающие числа можно рассматривать как аналог экспериментальных значений - т.е., классическая и вычислительная математики живут в разных реальностях.
#realnumbers
Научные вычисления (scientific computing / computational science), т.е. общие техники для всех вычислительных ветвей эмпирических наук, можно разделить на символьные и численные методы, в статье идёт речь о последних. Т.к. численные методы работают с непрерывными значениями (действительными/комплексными числами и их обобщениями), появляются вопросы сходимости, устойчивости и вычислимости алгоритмов над плавающей арифметикой (в частности проблема накопления ошибок округления). Для изучения этих вопросов нужен математический фреймворк вычислений над несчетными множествами, из наиболее популярных это BSS model (aka Real-RAM) и computable analysis (aka Type Two Effectivity), причем друг с другом они несовместимы. Статья посвящена разбору этих двух подходов.
CA/TTE - более фундаментальная и "низкоуровневая" теория, это разновидность матанализа, где сохраняется классическая теория, но дополнительно учитываются вычислительные представления объектов через бесконечные аппроксимации. Как правило, это делается через работу с некоторыми разновидностями машин Тюринга (с оракулом или более сложной машинерией репрезентаций). Её появление можно отследить к трудам Бореля, Банаха и Тюринга 1910-30х годов, где рассматривались вычислимые подмножества R (эта идея получила развитие в Марковской школе конструктивизма/синтетической вычислимости). Более поздние подходы ("Хагенская школа") перешли к рассмотрению всего R (ключевая идея TTE). В этой модели вычислимые функции должны быть непрерывными - как следствие, мы теряем возможность полноценно использовать "точечные" функции сравнения и округления (ср. https://twitter.com/andrejbauer/status/1400172747930718209).
BSS - модель вычислений с идеализированной RAM-машиной, способной хранить в памяти произвольные числа (в т.ч. и точные значения действительных) и мгновенно производить арифметические операции над ними. Тут не возникает проблем с разрывными функциями, но усложняется работа с функциями алгебраическими и трансцендентными (с которыми нет проблемы у CA), начиная с банальных квадратных корней.
Какой же фреймворк предпочтителен? BSS менее реалистична и хуже подходит для работы с ошибками округления и плохо обусловленными функциями, но тем не менее довольно популярна - она моделирует устойчивые алгоритмы (т.е. не вносит собственных ошибок) и позволяет работать с оценкой их сложности. Также BSS ближе к алгоритмам плавающей арифметики в том, что имеет фиксированную стоимость операций (в отличии от CA, где стоимость зависит от входа). С другой стороны, CA подходит для более глубоких вопросов вычислимости (в т.ч., например, квантовой) и работы с "плохо ведущими себя" функциями, но создает больше проблем при анализе стоимости и работе с хорошо изученными численными алгоритмами.
В конце статья проводит аналогию с физическими моделями, облегчающими работу за счет нереалистичных упрощений, например, плавающие числа можно рассматривать как аналог экспериментальных значений - т.е., классическая и вычислительная математики живут в разных реальностях.
#realnumbers
Wikipedia
Computational science
field concerned with constructing mathematical models and quantitative analysis techniques and using computers to analyze and solve scientific problems
👍2🤯1
Tomorrow July 8, on International Congress of Mathematicians (https://www.mathunion.org/icm/icm-2022/virtual-icm-2022-program-sections) will be a Computer Science session in room 1:
* The Mathematics of Hiding Secrets in Software
* Algorithmic aspects of discrepancy theory
* Beyond Linear Algebra
* A Mathematical Perspective on Machine Learning
Virtual attendance is possible (check the page).
* The Mathematics of Hiding Secrets in Software
* Algorithmic aspects of discrepancy theory
* Beyond Linear Algebra
* A Mathematical Perspective on Machine Learning
Virtual attendance is possible (check the page).
Forwarded from AlexTCH
http://aitp-conference.org/2022/
Apparently, there's an annual conference on all things AI and Mechanised Theorem Proving (automatic, interactive and their integration). Topics cover everything from mining archives of formal proofs to proving correctness of ML algorithms to AGI applications.
This year's speaker lineup is insane from Ben Goertzel and Stephen Wolfram to Kevin Buzzard and Talia Ringer.
Apparently, there's an annual conference on all things AI and Mechanised Theorem Proving (automatic, interactive and their integration). Topics cover everything from mining archives of formal proofs to proving correctness of ML algorithms to AGI applications.
This year's speaker lineup is insane from Ben Goertzel and Stephen Wolfram to Kevin Buzzard and Talia Ringer.
Forwarded from Alex Gryzlov
https://www.amazon.com/gp/product/052103311X Appel, [1992] "Compiling with Continuations"
https://slang.soe.ucsc.edu/cormac/papers/pldi93.pdf Flanagan, Sabry, Duba, Felleisen, [1993] "The Essence of Compiling with Continuations"
https://www.microsoft.com/en-us/research/wp-content/uploads/2007/10/compilingwithcontinuationscontinued.pdf Kennedy, [2007] "Compiling with Continuations, Continued"
https://www.microsoft.com/en-us/research/wp-content/uploads/2016/11/join-points-pldi17.pdf Maurer, Downen, Ariola, Jones, [2017] "Compiling without Continuations"
https://www.cs.purdue.edu/homes/rompf/papers/cong-icfp19.pdf Cong, Osvald, Essertel, Rompf, [2019] "Compiling with Continuations, or without? Whatever"
https://williamjbowman.com/downloads/wjb-paper-anf-sigma.pdf Bowman, Ahmed, [2019] "Compiling Dependent Types Without Continuations"
https://dl.acm.org/doi/pdf/10.1145/3485491 Paraskevopoulou, Grover, [2021] "Compiling with Continuations, Correctly"
https://slang.soe.ucsc.edu/cormac/papers/pldi93.pdf Flanagan, Sabry, Duba, Felleisen, [1993] "The Essence of Compiling with Continuations"
https://www.microsoft.com/en-us/research/wp-content/uploads/2007/10/compilingwithcontinuationscontinued.pdf Kennedy, [2007] "Compiling with Continuations, Continued"
https://www.microsoft.com/en-us/research/wp-content/uploads/2016/11/join-points-pldi17.pdf Maurer, Downen, Ariola, Jones, [2017] "Compiling without Continuations"
https://www.cs.purdue.edu/homes/rompf/papers/cong-icfp19.pdf Cong, Osvald, Essertel, Rompf, [2019] "Compiling with Continuations, or without? Whatever"
https://williamjbowman.com/downloads/wjb-paper-anf-sigma.pdf Bowman, Ahmed, [2019] "Compiling Dependent Types Without Continuations"
https://dl.acm.org/doi/pdf/10.1145/3485491 Paraskevopoulou, Grover, [2021] "Compiling with Continuations, Correctly"
🤯2😱1🤩1
Why Adjunctions Matter
• For the average programmer, adjunctions are (if known)
more respected than loved.
• However, they are key to explaining many things we do as
programmers.
• I will try to show how practical adjunctions are by revealing
their ”chemistry” in action.
https://www4.di.uminho.pt/~jno/ps/wadt22sl.pdf
• For the average programmer, adjunctions are (if known)
more respected than loved.
• However, they are key to explaining many things we do as
programmers.
• I will try to show how practical adjunctions are by revealing
their ”chemistry” in action.
https://www4.di.uminho.pt/~jno/ps/wadt22sl.pdf
👍1
A Note on the Under-Appreciated For-Loop
Jose N. Oliveira, 2020
https://www4.di.uminho.pt/~jno/ps/haslabtr202010.pdf
Excerpts:
> Just remove two letters from the word “foldr“‘ and you get “for”
<...>
> It is well known that, in the case of lists, foldr comes with its “left”-version foldl, which has the same functionality and implements foldr more efficiently under some mild conditions. What about for? Danvy [1] shows that a “left”-version of for exists
Jose N. Oliveira, 2020
https://www4.di.uminho.pt/~jno/ps/haslabtr202010.pdf
Excerpts:
> Just remove two letters from the word “foldr“‘ and you get “for”
<...>
> It is well known that, in the case of lists, foldr comes with its “left”-version foldl, which has the same functionality and implements foldr more efficiently under some mild conditions. What about for? Danvy [1] shows that a “left”-version of for exists
How Isabelle emerged from the trends of the 1980s
https://lawrencecpaulson.github.io/2022/07/13/Isabelle_influences.html
https://lawrencecpaulson.github.io/2022/07/13/Isabelle_influences.html
👍2
Hygienic Macro Technology (PDF, 2020), by William D Clinger and Mitchell Wand. “In this paper, we summarize that early history with greater focus on hygienic macros, and continue the story by describing the further development, adoption, and influence of hygienic and partially hygienic macro technology in Scheme.”
https://dl.acm.org/doi/pdf/10.1145/3386330
https://dl.acm.org/doi/pdf/10.1145/3386330
ML 2021: A metalanguage for multi-phase modularity, by Sterling and Harper (2021)
https://www.youtube.com/watch?v=5kWS-umBA7k
https://www.youtube.com/watch?v=5kWS-umBA7k
YouTube
ML 2021: A metalanguage for multi-phase modularity
Jonathan Sterling and Robert Harper
Type abstraction, the phase distinction, and computational effects all play an important role in the design and implementation of ML-style module systems. We propose a simple type theoretic metalanguage φML for multi-phase…
Type abstraction, the phase distinction, and computational effects all play an important role in the design and implementation of ML-style module systems. We propose a simple type theoretic metalanguage φML for multi-phase…
Programming Language Semantics: It’s Easy As 1, 2, 3
by Graham Hutton, 2021
comment: INTRODUCTORY ARTICLE
http://www.cs.nott.ac.uk/~pszgmh/123.pdf
by Graham Hutton, 2021
comment: INTRODUCTORY ARTICLE
http://www.cs.nott.ac.uk/~pszgmh/123.pdf
👍1
‘do’ Unchained: Embracing Local Imperativity in a Purely Functional Language (Functional Pearl)
S. Ullrich, L. de Moura, 2022
https://leanprover.github.io/papers/do.pdf
S. Ullrich, L. de Moura, 2022
https://leanprover.github.io/papers/do.pdf
Software eco-design: investigating and reducing the energy consumption of software
by Zakaria Ournani, 2022
https://tel.archives-ouvertes.fr/tel-03554712/document
by Zakaria Ournani, 2022
https://tel.archives-ouvertes.fr/tel-03554712/document
🤔2
We’ve just released a major milestone of Unison, version M4
Anyone can now self-publish code to http://share.unison-lang.org
<...>
We just launched our code-hosting platform!
It's like Github, but has hyperlinked syntax-highlighted code and docs from day one
https://twitter.com/unisonweb/status/1547953084394979329
Anyone can now self-publish code to http://share.unison-lang.org
<...>
We just launched our code-hosting platform!
It's like Github, but has hyperlinked syntax-highlighted code and docs from day one
https://twitter.com/unisonweb/status/1547953084394979329
🎉2🤔1
ICYMI. Led by @clayrat https://www.tg-me.com/covalue/58
Telegram
Ковэлью
Bornat, [2009] "Separation logic and concurrency"
Программирование это комбинация механических вычислений и формальной логики. Как правило, каждый новый формализм используется программистами для увеличения объема выразимых программ, а не корректности (насчет…
Программирование это комбинация механических вычислений и формальной логики. Как правило, каждый новый формализм используется программистами для увеличения объема выразимых программ, а не корректности (насчет…
👍1
John Baez завел канал на ютубе, https://www.youtube.com/playlist?list=PLuAO-1XXEh0ZiJlRKz7EuODAdIOjC5-1l
YouTube
John Baez: talks - YouTube
🤔3🤯1