А вот второй туториал мне понравился гораздо больше. У него и страничка есть: https://acl2024.ivia.ch/
Краткое изложение без доказательств (на уд, мне бы денёк разобраться):
- Элмановские (простые) рекуррентные сети с произвольной точностью и неограниченным количеством шагов вычислений полны по Тьюрингу (статья 1992 года). Короче, они крутые, но не в физической реальности.
- Простые рекуррентные сети с единичной ступенчатой функцией активации эквивалентны детерменированным конечным автоматам (ссылаются на самих Мак-Каллока и Питтса, и иногда на неопубликованную докторскую диссертацию Минского, но в целом это и самому доказуемо, как минимум в одну сторону). Короче, они не очень крутые, зато хотя бы существуют.
- Утверждение выше расширяемо на языковые модели на основе RNN и взвешенные конечные автоматы (ссылка).
- LSTM могут эмулировать считающие машины. Это такой специфический класс, который пересекает всю иерархию (ссылка). Это... забавно?
- AC0 — класс сложности, в который входят булевы схемы константной глубины, полиномиального размера, с неограниченным числом входов и поддержкой только AND, OR и NOT гейтов (NOT только на входах). TC0 — как AC0, только с поддержкой мажоритарных элементов. При определенных модификациях внимания трансформерные энкодеры лежат в AC0 (ссылка) или TC0 (ссылка). Классы эти довольно специфическим образом отображются на стандартную иерархию Хомского, поэтому оценить крутость не представляется возможным.
- Chain-of-thought внезапно значительно увеличивает вычислительную крутость трансформеров. При произвольной точности, неограниченном числе выходов и определенном виде внимания, трансформерные декодеры тоже полны по Тюрингу (=тоже крутые, и тоже не в физической реальности).
Зачем всё это кому-то нужно? Всегда приятно знать, какие задачи принципиально нерешаемы вашей моделью.
Краткое изложение без доказательств (на уд, мне бы денёк разобраться):
- Элмановские (простые) рекуррентные сети с произвольной точностью и неограниченным количеством шагов вычислений полны по Тьюрингу (статья 1992 года). Короче, они крутые, но не в физической реальности.
- Простые рекуррентные сети с единичной ступенчатой функцией активации эквивалентны детерменированным конечным автоматам (ссылаются на самих Мак-Каллока и Питтса, и иногда на неопубликованную докторскую диссертацию Минского, но в целом это и самому доказуемо, как минимум в одну сторону). Короче, они не очень крутые, зато хотя бы существуют.
- Утверждение выше расширяемо на языковые модели на основе RNN и взвешенные конечные автоматы (ссылка).
- LSTM могут эмулировать считающие машины. Это такой специфический класс, который пересекает всю иерархию (ссылка). Это... забавно?
- AC0 — класс сложности, в который входят булевы схемы константной глубины, полиномиального размера, с неограниченным числом входов и поддержкой только AND, OR и NOT гейтов (NOT только на входах). TC0 — как AC0, только с поддержкой мажоритарных элементов. При определенных модификациях внимания трансформерные энкодеры лежат в AC0 (ссылка) или TC0 (ссылка). Классы эти довольно специфическим образом отображются на стандартную иерархию Хомского, поэтому оценить крутость не представляется возможным.
- Chain-of-thought внезапно значительно увеличивает вычислительную крутость трансформеров. При произвольной точности, неограниченном числе выходов и определенном виде внимания, трансформерные декодеры тоже полны по Тюрингу (=тоже крутые, и тоже не в физической реальности).
Зачем всё это кому-то нужно? Всегда приятно знать, какие задачи принципиально нерешаемы вашей моделью.