Иерархия Хомского
https://arxiv.org/abs/2207.02098
We demonstrate that grouping tasks according to the Chomsky hierarchy allows us to forecast whether certain architectures will be able to generalize to out-of-distribution inputs. This includes negative results where even extensive amounts of data and training time never lead to any non-trivial generalization, despite models having sufficient capacity to fit the training data perfectly. Our results show that, for our subset of tasks, RNNs and Transformers fail to generalize on non-regular tasks, LSTMs can solve regular and counter-language tasks, and only networks augmented with structured memory (such as a stack or memory tape) can successfully generalize on context-free and context-sensitive tasks.
(читаю открытые давным-давно вкладки, чтобы уж закрыть связанный с ними гештальт)
Контекстно-зависимые грамматики встречаются в некоторых естественных языках (в некоторых африканских языках вопрос имеет двойную структуру утверждения: сперва даётся утверждение, потом оно повторяется с небольшим изменением, что и создаёт вопрос). Алгол-68, а вслед за ним и некоторые другие языки наподобие Си, может быть полностью описан контекстно-зависимой грамматикой.
https://ru.wikipedia.org/wiki/%D0%93%D1%80%D0%B0%D0%BC%D0%BC%D0%B0%D1%82%D0%B8%D0%BA%D0%B0_%D0%B2%D0%B0%D0%BD_%D0%92%D0%B5%D0%B9%D0%BD%D0%B3%D0%B0%D0%B0%D1%80%D0%B4%D0%B5%D0%BD%D0%B0#%D0%9F%D1%80%D0%B8%D0%BC%D0%B5%D1%80%D1%8B_%D0%B8%D0%B7_ALGOL_68
https://thesz.livejournal.com/1556893.html
Всё это может нам намекнуть, смогут ли трансформаторы "понимать" языки программирования. Намёк выглядит, как "не смогут, в принципе не могут."
Языки программирования часто включают в себя возможность иметь "сбалансированные переупорядоченные скобки": каждому открытию файла должно соответствовать его закрытие, но закрытия могут быть переставлены. "Открыть 1, открыть 2, закрыть 1, закрыть 2" эквивалентно "открыть 1, открыть 2, закрыть 2, закрыть 1" с точностью до проверки кода ошибки, который никто не делает.
Я подозреваю, прикидывая реализацию сего на обобщённой монаде состояния, что тут мы вторгаемся в область языков типа 0, которые порождают завершающиеся вычисления машины Тьюринга.
Это позволяет мне заключить, что "понимание языков программирования" удел символьных вычислений, а не нейронных моделей. Последним мы всегда сможем предъявить программу, на которую стека не хватит, в типичных нейронках со стеком он ограничен.
We demonstrate that grouping tasks according to the Chomsky hierarchy allows us to forecast whether certain architectures will be able to generalize to out-of-distribution inputs. This includes negative results where even extensive amounts of data and training time never lead to any non-trivial generalization, despite models having sufficient capacity to fit the training data perfectly. Our results show that, for our subset of tasks, RNNs and Transformers fail to generalize on non-regular tasks, LSTMs can solve regular and counter-language tasks, and only networks augmented with structured memory (such as a stack or memory tape) can successfully generalize on context-free and context-sensitive tasks.
(читаю открытые давным-давно вкладки, чтобы уж закрыть связанный с ними гештальт)
Контекстно-зависимые грамматики встречаются в некоторых естественных языках (в некоторых африканских языках вопрос имеет двойную структуру утверждения: сперва даётся утверждение, потом оно повторяется с небольшим изменением, что и создаёт вопрос). Алгол-68, а вслед за ним и некоторые другие языки наподобие Си, может быть полностью описан контекстно-зависимой грамматикой.
https://ru.wikipedia.org/wiki/%D0%93%D1%80%D0%B0%D0%BC%D0%BC%D0%B0%D1%82%D0%B8%D0%BA%D0%B0_%D0%B2%D0%B0%D0%BD_%D0%92%D0%B5%D0%B9%D0%BD%D0%B3%D0%B0%D0%B0%D1%80%D0%B4%D0%B5%D0%BD%D0%B0#%D0%9F%D1%80%D0%B8%D0%BC%D0%B5%D1%80%D1%8B_%D0%B8%D0%B7_ALGOL_68
https://thesz.livejournal.com/1556893.html
Всё это может нам намекнуть, смогут ли трансформаторы "понимать" языки программирования. Намёк выглядит, как "не смогут, в принципе не могут."
Языки программирования часто включают в себя возможность иметь "сбалансированные переупорядоченные скобки": каждому открытию файла должно соответствовать его закрытие, но закрытия могут быть переставлены. "Открыть 1, открыть 2, закрыть 1, закрыть 2" эквивалентно "открыть 1, открыть 2, закрыть 2, закрыть 1" с точностью до проверки кода ошибки, который никто не делает.
Я подозреваю, прикидывая реализацию сего на обобщённой монаде состояния, что тут мы вторгаемся в область языков типа 0, которые порождают завершающиеся вычисления машины Тьюринга.
Это позволяет мне заключить, что "понимание языков программирования" удел символьных вычислений, а не нейронных моделей. Последним мы всегда сможем предъявить программу, на которую стека не хватит, в типичных нейронках со стеком он ограничен.