Уважаемые коллеги, тех, кому интересна математика и машинное обучение, наши коллеги приглашают принять в неформальном проекте.
Минимальное требование - Вы знакомы с Питоном, и у Вас есть несколько часов свободного времени в неделю. (Альтернативно - можно не знать Питон, но хорошо знать теорию групп.) Цель проекта - применить машинное обучение к теории групп. Результат проекта - написание статьи в хорошем журнале. Другим бонусом будет являться - работа под руководством опытных специалистов в области машинного обучения и приобретение навыков по современным методам нейронных сетей, Reinforcement Learning и т.д.
Примерный список направлений
1) Задача поиска короткого пути на графах Кэли (сборка кубика - аналог Каггл Санта23 - но для произвольных групп)
2) Оценки диаметра ("числа бога") для графов (то есть расстояние между самыми дальними точками на графах)
3) Бенчмарк эмбедингов графов на основе математических результатов о графах
4) Многое другое, что тесно связано - случайные блуждания, гипотеза Ловаса о обязательном существовании гамильтонова пути на любом графе Кэли,
Если Вам интересно участие - напишите @alexander_v_c (Александр Червов), чат для обсуждений тут .
Проект осуществляется при участии опытных специалистов (и многие ведут телеграм каналы):
Александр Червов (к.ф.-м.н. 25 лет math&DS )
Кирилл Хоружий (ex-Физтех, Max Planck Institute of Quantum Optics )
Андрей Лукьяненко (Kaggle Grandmaster, 11 лет в IT &DS )
Александр Абрамов (Kaggle Master, SberDevices, 10 лет в DS )
Павел Снопов (ИППИ РАН )
Владимир Шитов (Helmholtz Munich )
Сергей Нечаев (д.ф.-м.н., directeur de recherche au CNRS-Universite Paris-Saclay )
Минимальное требование - Вы знакомы с Питоном, и у Вас есть несколько часов свободного времени в неделю. (Альтернативно - можно не знать Питон, но хорошо знать теорию групп.) Цель проекта - применить машинное обучение к теории групп. Результат проекта - написание статьи в хорошем журнале. Другим бонусом будет являться - работа под руководством опытных специалистов в области машинного обучения и приобретение навыков по современным методам нейронных сетей, Reinforcement Learning и т.д.
Примерный список направлений
1) Задача поиска короткого пути на графах Кэли (сборка кубика - аналог Каггл Санта23 - но для произвольных групп)
2) Оценки диаметра ("числа бога") для графов (то есть расстояние между самыми дальними точками на графах)
3) Бенчмарк эмбедингов графов на основе математических результатов о графах
4) Многое другое, что тесно связано - случайные блуждания, гипотеза Ловаса о обязательном существовании гамильтонова пути на любом графе Кэли,
Если Вам интересно участие - напишите @alexander_v_c (Александр Червов), чат для обсуждений тут .
Проект осуществляется при участии опытных специалистов (и многие ведут телеграм каналы):
Александр Червов (к.ф.-м.н. 25 лет math&DS )
Кирилл Хоружий (ex-Физтех, Max Planck Institute of Quantum Optics )
Андрей Лукьяненко (Kaggle Grandmaster, 11 лет в IT &DS )
Александр Абрамов (Kaggle Master, SberDevices, 10 лет в DS )
Павел Снопов (ИППИ РАН )
Владимир Шитов (Helmholtz Munich )
Сергей Нечаев (д.ф.-м.н., directeur de recherche au CNRS-Universite Paris-Saclay )
Telegram
(sci)Berloga Всех Наук и Технологий
Мультидисциплинарный канал о науке и технологиях.
Data Science, Bioinformatics, Biology, Mathematics, Physics, IT, Computer Science.
@sberlogabio био и дата сайнс
@sberlogasci математика, физика и ДС
https://www.youtube.com/c/SciBerloga
Data Science, Bioinformatics, Biology, Mathematics, Physics, IT, Computer Science.
@sberlogabio био и дата сайнс
@sberlogasci математика, физика и ДС
https://www.youtube.com/c/SciBerloga
Fourier Features Let Networks Learn
High Frequency Functions in Low Dimensional Domains
https://arxiv.org/abs/2006.10739
Статья 2020 года с нипса, которая объясняет, почему же позиционные эмбединги трансформеров хорошо работают именно в таком странном виде эмбедингов из синусов и косинусов (но не только).
Основная мысль: если подавать время, позиции, координаты - т.е. числа или вектора низкой размерности - как есть, то сетка даже на обучающей выборке не может выучить высокочастотные компоненты целевой функции. А если преобразовать их в вектора высокой размерности, лежащие на гиперсфере, частным случаем чего являются позиционные эмбединги, то подобной проблемы не возникает. Такое преобразование авторы и называют fourier features. Пишут, что идея статьи пришла при работе над NERF'ом.
Общий вид изучаемых эмбедингов позиций, времени, 2d и 3d координат:
f_feat(p) =(a1*cos(2Pi*<w1, p>), a1*sin (2Pi*<w1, p>), ..., a_d *cos(2Pi*<wd, p>), a_d*sin(2Pi*<wd, p>)).
Что с ними делают:
1) пытаются теоретически объяснить, почему подобное преобразование работает лучше, чем подавать данные нейросетке в исходном виде.
2) пытаются определить качественное влияние параметров a_i, w_i на получающееся решение
3) проводят мотивирующие эксперименты
Теоретическое объяснение:
Через neural tangent kernel в несколько шагов:
1) Пусть k_ntk - это neural tangent kernel, соответствующей данной нейросети. Введем матрицу K, состояющую из значений этого ядра на обучающей выборке:
K_ij = k_ntk(xi, xj)
err_t - ошибка сетки на обучающей выборке с learning rate lr на шаге обучения t - может быть аппроксимирована с помощью выражения, использующего матрицу K:
|err_t| ~= e^(-lr *K*t) * y_t,
где y_t - вектор/матрица значений целевой функции на обучающей выборке
y_t: y_t[I] =y(x_i)
2) матрица K неотрицательно определена, поэтому можно использовать разложение K=QDQ^T, где Q ортонормированная матрица собственных векторов, а D - диагональная и D_ii>= 0:
Q^T*(err_t) ~=e^(-lr *D*t)Q^T
и
[Q^T*(err_t)]_i ~=e^(-lr *l_i*t)Q^T
3) Получается, что скорость сходимости ошибки на обучающей выборке зависит от спектра матрицы K. Если собственные значения сильно отличаются друг от друга, то разные компоненты ошибки будут сходиться с разной скоростью. А если матрица плохо обусловлена, т.е. есть собственные значения близкие к нулю, то соответствующие компоненты ошибки не сойдутся к нулю фактически никогда
4) Если же элементы обучающей выборки x_i расположены на гиперсфере, то (по другому результату)
k_ntk(x_i, x_j) =k_ntk'(<x_i, x_j>).
Для fourier features
norm(f_feat(x_i)) =const,
<f_feat(x_i), f_feat(x_j)>=h(x_i-x_j),
поэтому
k_ntk(f_feat(x_i), f_feat(x_j)) =k_ntk'(h(x_i-x_j)),
Т.е. neural tangent kernel зависит только от разности аргументов.
5) Из-за предыдущего равенства матрица K для выборки, преобразованной f_feat, будет матрицей стационарного ядра, и (видимо) подобная симметрия обеспечивает "хороший" спектр. В частности, K_ii =K_jj.
Пункты 3 и 5 дают нужные утверждения.
Также есть видео с красивой презентацией и наглядными визуализациями: https://youtu.be/nVA6K6Sn2S4?si=bhu-XmE-Ejk1Bhvz
и блогпост с неформальными поясениями https://bmild.github.io/fourfeat/
High Frequency Functions in Low Dimensional Domains
https://arxiv.org/abs/2006.10739
Статья 2020 года с нипса, которая объясняет, почему же позиционные эмбединги трансформеров хорошо работают именно в таком странном виде эмбедингов из синусов и косинусов (но не только).
Основная мысль: если подавать время, позиции, координаты - т.е. числа или вектора низкой размерности - как есть, то сетка даже на обучающей выборке не может выучить высокочастотные компоненты целевой функции. А если преобразовать их в вектора высокой размерности, лежащие на гиперсфере, частным случаем чего являются позиционные эмбединги, то подобной проблемы не возникает. Такое преобразование авторы и называют fourier features. Пишут, что идея статьи пришла при работе над NERF'ом.
Общий вид изучаемых эмбедингов позиций, времени, 2d и 3d координат:
f_feat(p) =(a1*cos(2Pi*<w1, p>), a1*sin (2Pi*<w1, p>), ..., a_d *cos(2Pi*<wd, p>), a_d*sin(2Pi*<wd, p>)).
Что с ними делают:
1) пытаются теоретически объяснить, почему подобное преобразование работает лучше, чем подавать данные нейросетке в исходном виде.
2) пытаются определить качественное влияние параметров a_i, w_i на получающееся решение
3) проводят мотивирующие эксперименты
Теоретическое объяснение:
Через neural tangent kernel в несколько шагов:
1) Пусть k_ntk - это neural tangent kernel, соответствующей данной нейросети. Введем матрицу K, состояющую из значений этого ядра на обучающей выборке:
K_ij = k_ntk(xi, xj)
err_t - ошибка сетки на обучающей выборке с learning rate lr на шаге обучения t - может быть аппроксимирована с помощью выражения, использующего матрицу K:
|err_t| ~= e^(-lr *K*t) * y_t,
где y_t - вектор/матрица значений целевой функции на обучающей выборке
y_t: y_t[I] =y(x_i)
2) матрица K неотрицательно определена, поэтому можно использовать разложение K=QDQ^T, где Q ортонормированная матрица собственных векторов, а D - диагональная и D_ii>= 0:
Q^T*(err_t) ~=e^(-lr *D*t)Q^T
и
[Q^T*(err_t)]_i ~=e^(-lr *l_i*t)Q^T
3) Получается, что скорость сходимости ошибки на обучающей выборке зависит от спектра матрицы K. Если собственные значения сильно отличаются друг от друга, то разные компоненты ошибки будут сходиться с разной скоростью. А если матрица плохо обусловлена, т.е. есть собственные значения близкие к нулю, то соответствующие компоненты ошибки не сойдутся к нулю фактически никогда
4) Если же элементы обучающей выборки x_i расположены на гиперсфере, то (по другому результату)
k_ntk(x_i, x_j) =k_ntk'(<x_i, x_j>).
Для fourier features
norm(f_feat(x_i)) =const,
<f_feat(x_i), f_feat(x_j)>=h(x_i-x_j),
поэтому
k_ntk(f_feat(x_i), f_feat(x_j)) =k_ntk'(h(x_i-x_j)),
Т.е. neural tangent kernel зависит только от разности аргументов.
5) Из-за предыдущего равенства матрица K для выборки, преобразованной f_feat, будет матрицей стационарного ядра, и (видимо) подобная симметрия обеспечивает "хороший" спектр. В частности, K_ii =K_jj.
Пункты 3 и 5 дают нужные утверждения.
Также есть видео с красивой презентацией и наглядными визуализациями: https://youtu.be/nVA6K6Sn2S4?si=bhu-XmE-Ejk1Bhvz
и блогпост с неформальными поясениями https://bmild.github.io/fourfeat/
arXiv.org
Fourier Features Let Networks Learn High Frequency Functions in...
We show that passing input points through a simple Fourier feature mapping enables a multilayer perceptron (MLP) to learn high-frequency functions in low-dimensional problem domains. These results...
а) Сравнение матрицы K для neural tangent kernel для 1d координат и их преобразования в fourier features. Видно что для исходных координат матрица K должна иметь много маленьких собственных значений, а для преобразованных на диагонали все хорошо
б) влияние параметров эмбедингов aj =(1/j)^p, wj=j на получающееся ядро одномерной свертки k_ntk'. Наглядно можно представить, что ответ нейросетки это взвешенное среднее с весами k_ntk'(x_i-x_j). Можно прикинуть, какие параметры приведут к недообучению, какие а переобучения, а какие самый раз.
б) влияние параметров эмбедингов aj =(1/j)^p, wj=j на получающееся ядро одномерной свертки k_ntk'. Наглядно можно представить, что ответ нейросетки это взвешенное среднее с весами k_ntk'(x_i-x_j). Можно прикинуть, какие параметры приведут к недообучению, какие а переобучения, а какие самый раз.
Эксперимент, на котором проверяют скорость сходимости низких, средних и высоких частот модельной целевой функции в зависимости от параметров fourier features a_j=1/j^p, w_j =j при изменении параметра p. Параметр p фактически регулирует размерность эмбединга.
Видно, что в исходном виде выучиваются только очень низкие частоты. При низкой фактической размерности высокие частоты тоже плохо выучиваются, а чем выше p, тем более высоких частот, вплоть до переобучения.
Видно, что в исходном виде выучиваются только очень низкие частоты. При низкой фактической размерности высокие частоты тоже плохо выучиваются, а чем выше p, тем более высоких частот, вплоть до переобучения.
This media is not supported in your browser
VIEW IN TELEGRAM
Как сходится регрессия без эмбедингов координат в фурье фичи и с фурье фичами
Forwarded from Data Funk
Желание разложить что-угодно по группам на основе схожести - естественная черта человека, но задача кластеризации данных, почти всегда как плохое ТЗ для дизайнера - делай красиво, а не красиво не делай. Какой алгоритм кластеризации хороший, а какой плохой если сравнивать результат их работы не с чем? Джон Клейнберг из Корнеллского университета в 2002 году сформулировал три критерия хорошего алгоритма кластеризации:
- Масштабная инвариантность. Если все расстояния между точками умножить на положительное число, это не должно менять результат работы хорошего алгоритма.
- Насыщенность/разнообразие. Хороший алгоритм способен создать любую произвольную комбинацию разбиения входных данных.
- Согласованность. Если уменьшаем внутрикластерные расстояния и/или увеличиваем межкластерные, алгоритм должен возвращать то же разбиение на кластеры.
- Масштабная инвариантность. Если все расстояния между точками умножить на положительное число, это не должно менять результат работы хорошего алгоритма.
- Насыщенность/разнообразие. Хороший алгоритм способен создать любую произвольную комбинацию разбиения входных данных.
- Согласованность. Если уменьшаем внутрикластерные расстояния и/или увеличиваем межкластерные, алгоритм должен возвращать то же разбиение на кластеры.
Forwarded from Data Funk
В своей работе "Теорема о невозможности кластеризации" Клейнберг доказывает что никакой алгоритм кластеризации не может удовлетворять одновременно трем названным условиям. Масштабная инвариантность нарушается когда для определения принадлежности точки к кластеру используются относительные расстояния с заданным порогом. Насыщенность нарушается, если заранее фиксируется количество кластеров. Согласованность нарушается когда для объединения точек в кластеры используются абсолютные расстояния не превышающие некоторый порог. С другой стороны указанные критерии это субъективное представление о красивом/полезном разбиении множества на группы, с которым необязательно соглашаться. Максимально понятно, без математики, теорема описана тут.
Forwarded from Math and ML stuff
В середине июля в Лондоне прошла летняя школа, для аспирантов и пост-доков - LOGML (London Geometry and Machine Learning). Тематика школы - применение методов геометрии и топологии в глубинном обучении, организатор Imperial College London. В 2021 и 2022 годах она была онлайн, в этом году все сделали очно. Направление школы идеально совпадает с темой моей диссертации, я участвовал в школе во все прошлые итерации, и в этот раз решил провести незабываемую неделю в Лондоне, работая над релевантным мне проектом. Структура школы включает лекции приглашенных спикеров, командные работы над проектами под руководством менторов (профессора, постдоки) и презентации результатов, всё мероприятие проходило в самом Imperial College. Из интересных, запомнившихся проектов были следующие:
Stability or Collapse: Topological Properties of Deep Autoencoders (2021) - применения ТДА для исследования внутренних представлений автоэнкодеров
Pretraining GNN with ELECTRA (2021) - предварительное обучение GNN для задач хим-информатики, но с применением техники предобучения ELECTRA, используемой в NLP
Platonic CNNs (2021) - применение CNN для сигналов со сложной геометрической структурой, например климатические особенности на поверхности Земли (сфере, которую предлагается приблизить икосаэдром - получается архитектура Icosahedral CNNs). Platonic - потому что икосаэдр платоническое тело.
Characterizing generalization and adversarial robustness for set networks (2022) - по мотивам этой статьи, ментором был проф Толга Бирдал; проект по улучшению его подхода для предсказания обобщающей способности CNN на основе геометрии траектории пространства весов в процессе обучения. В этом году среди постерной сессии на школе была работа, которая критиковала статью Толги.
Geometric tools for investigating loss landscapes of deep neural networks (2022) - анализ геометрических свойства ландшафта функции потерь
On the Geometry of Relative Representations (2024) - улучшение подхода к вычислению без дополнительного дообучения новых внутренних представлений нейросеток для более эффективного их последующего использования.
Powerful Graph Neural Networks for Relational Databases (2024) - применение GNN для реляционных графов (k-partite graph), построенных по реляционным базам данных.
Self-supervised learning for Topological Neural Networks (2024) - разработка Self-supervised learning режима обучения для топологических GNN (более подробно про них в этом посте). Отдельное подробное описание этого проекта будет у Паши на канале.
Это далеко не полный список проектов. Как правило, по завершению проектов на школе команды пишут статьи. Впечатлений и новых знакомств море, все подавайтесь на след год тоже. Прикладываю фото со школы
Stability or Collapse: Topological Properties of Deep Autoencoders (2021) - применения ТДА для исследования внутренних представлений автоэнкодеров
Pretraining GNN with ELECTRA (2021) - предварительное обучение GNN для задач хим-информатики, но с применением техники предобучения ELECTRA, используемой в NLP
Platonic CNNs (2021) - применение CNN для сигналов со сложной геометрической структурой, например климатические особенности на поверхности Земли (сфере, которую предлагается приблизить икосаэдром - получается архитектура Icosahedral CNNs). Platonic - потому что икосаэдр платоническое тело.
Characterizing generalization and adversarial robustness for set networks (2022) - по мотивам этой статьи, ментором был проф Толга Бирдал; проект по улучшению его подхода для предсказания обобщающей способности CNN на основе геометрии траектории пространства весов в процессе обучения. В этом году среди постерной сессии на школе была работа, которая критиковала статью Толги.
Geometric tools for investigating loss landscapes of deep neural networks (2022) - анализ геометрических свойства ландшафта функции потерь
On the Geometry of Relative Representations (2024) - улучшение подхода к вычислению без дополнительного дообучения новых внутренних представлений нейросеток для более эффективного их последующего использования.
Powerful Graph Neural Networks for Relational Databases (2024) - применение GNN для реляционных графов (k-partite graph), построенных по реляционным базам данных.
Self-supervised learning for Topological Neural Networks (2024) - разработка Self-supervised learning режима обучения для топологических GNN (более подробно про них в этом посте). Отдельное подробное описание этого проекта будет у Паши на канале.
Это далеко не полный список проектов. Как правило, по завершению проектов на школе команды пишут статьи. Впечатлений и новых знакомств море, все подавайтесь на след год тоже. Прикладываю фото со школы
Forwarded from Math and ML stuff
Недавно прошла ICLR 2024. Собрал запоминающиеся и важные статьи по интересным мне темам.
Knowledge Graph Reasoning and Question Answering - рассуждение и генерация ответов на графах знаний.
1. Reasoning on Graphs: Faithful and Interpretable Large Language Model Reasoning - ответим на вопрос "Кто ребенок Алисы?". Сначала на стадии планирования генерируем LLMкой путь отношений z = {marry to → father of}, затем накладываем его на граф знаний wz = (Alice) marry to → (Bob) father of → (Charlie), из структуры графа получаем ответ Charlie. Т.е. в каком-то смысле паттерн-матчинг. LLM знает про структуру графа и через Planning optimization учится создавать все более релевантные пути отношений.
LLM и все, что в них обитает:
1. Unveiling the Pitfalls of Knowledge Editing for Large Language Models - авторы исследуют проблемы, возникающие в процессе редактирования знаний внутри LLM, более подробно в прошлом посте. Из-за запутанной структуры знаний внутри LLM после редактирования появляются необратимые изменения (метастазы), отражающиеся на множество других сопряженных знаний. Даже если измененный факт отредактировать обратно, то на последствия исходного изменения это не повлияет. Еще рассматриваются логические противоречивые хирургий знаний и их следствия. Тема очень важная в контексте Safety AI.
2. The Geometry of Truth: Emergent Linear Structure in Large Language Model Representations of True/False Datasets - геометрия правды и лжи. По моему мнению, самая интересная статья на конфе. Авторы показывают, что истинные и ложные утверждения образуют разделимые линейные структуры во внутренних представлениях LLM
World Modeling - задача изучения богатого представления, которое учитывает динамику среды, что позволяет агенту прогнозировать будущие состояния и последствия своих действий. Классическое поле тестирования агентов - Minecraft.
1. Mastering Memory Tasks with World Models - продолжение и развитие идеи DreamerV3, В Статье улучшает структуру памяти агента из DreamerV3 и позволяет учитывать более долгосрочные зависимости в Модели Мира, может предсказывать на большее кол-во шагов вперед.
На свободную тематику:
1. Talk like a graph: Encoding graphs for large language models - идея крайне простая, но любопытная: как можно энкодить графы внутрь LLM? Спойлер: если в промпте граф описываешь не просто перечислением вершин и ребер: "G граф с нодами 0...8, и ребрами: (0,1),(0,2)…(7,8).", а через структуру отношений в терминах Игры Престолов: "G граф взаимоотношений разных персонажей Ned, Cat, Daenerys...Jaime. В этом графе: Ned and Cat дружат...Cersei and Jaime дружат.", то LLM лучше воспринимает граф, и может больше про него сказать всякой чисто графовой инфы, типа сколько компонент связности, какая степень вершины итд. Всего Тестировалось 9 способов промптить граф.
2. Interpreting CLIP's Image Representation via Text-Based Decomposition - интерпретация внутренней структуры ViT из CLIP. Авторы определяют, какая голова ViT за какой смысловой аспект отвечает. То, что на головах происходит диверсефикация фичей, т.е. разные головы смотрят на разные объекты и уровни абстракции - это известно еще со статьи, где саму архитектуру ViT предлагали, но в данной работе конкретизируется, какая голова отвечает за форму, какая за цвета, итд. Статья - существенный вклад в explainable AI.
3. ULTRA Towards Foundation Models for Knowledge Graph Reasoning - предлагается архитектура фундаментальной модели GNN. Более подробно в этом посте.
4. Neural Network Expressive Power Analysis Via Manifold Topology - оценивается верхняя граница длины FC сети в терминах топологической сложности (сумма чисел Бетти) обучающих данных. В статье все строго доказывается, и это была бы очень хорошая работа, если бы не ограничение на размерность многообразия = 3, но мб это хороший старт для обобщения на произвольную размерность. Ну и все оценки, завязанные на сумму чисел Бетти для облаков точек тоже достаточно спекулятивные. Статья реджектнута.
Knowledge Graph Reasoning and Question Answering - рассуждение и генерация ответов на графах знаний.
1. Reasoning on Graphs: Faithful and Interpretable Large Language Model Reasoning - ответим на вопрос "Кто ребенок Алисы?". Сначала на стадии планирования генерируем LLMкой путь отношений z = {marry to → father of}, затем накладываем его на граф знаний wz = (Alice) marry to → (Bob) father of → (Charlie), из структуры графа получаем ответ Charlie. Т.е. в каком-то смысле паттерн-матчинг. LLM знает про структуру графа и через Planning optimization учится создавать все более релевантные пути отношений.
LLM и все, что в них обитает:
1. Unveiling the Pitfalls of Knowledge Editing for Large Language Models - авторы исследуют проблемы, возникающие в процессе редактирования знаний внутри LLM, более подробно в прошлом посте. Из-за запутанной структуры знаний внутри LLM после редактирования появляются необратимые изменения (метастазы), отражающиеся на множество других сопряженных знаний. Даже если измененный факт отредактировать обратно, то на последствия исходного изменения это не повлияет. Еще рассматриваются логические противоречивые хирургий знаний и их следствия. Тема очень важная в контексте Safety AI.
2. The Geometry of Truth: Emergent Linear Structure in Large Language Model Representations of True/False Datasets - геометрия правды и лжи. По моему мнению, самая интересная статья на конфе. Авторы показывают, что истинные и ложные утверждения образуют разделимые линейные структуры во внутренних представлениях LLM
World Modeling - задача изучения богатого представления, которое учитывает динамику среды, что позволяет агенту прогнозировать будущие состояния и последствия своих действий. Классическое поле тестирования агентов - Minecraft.
1. Mastering Memory Tasks with World Models - продолжение и развитие идеи DreamerV3, В Статье улучшает структуру памяти агента из DreamerV3 и позволяет учитывать более долгосрочные зависимости в Модели Мира, может предсказывать на большее кол-во шагов вперед.
На свободную тематику:
1. Talk like a graph: Encoding graphs for large language models - идея крайне простая, но любопытная: как можно энкодить графы внутрь LLM? Спойлер: если в промпте граф описываешь не просто перечислением вершин и ребер: "G граф с нодами 0...8, и ребрами: (0,1),(0,2)…(7,8).", а через структуру отношений в терминах Игры Престолов: "G граф взаимоотношений разных персонажей Ned, Cat, Daenerys...Jaime. В этом графе: Ned and Cat дружат...Cersei and Jaime дружат.", то LLM лучше воспринимает граф, и может больше про него сказать всякой чисто графовой инфы, типа сколько компонент связности, какая степень вершины итд. Всего Тестировалось 9 способов промптить граф.
2. Interpreting CLIP's Image Representation via Text-Based Decomposition - интерпретация внутренней структуры ViT из CLIP. Авторы определяют, какая голова ViT за какой смысловой аспект отвечает. То, что на головах происходит диверсефикация фичей, т.е. разные головы смотрят на разные объекты и уровни абстракции - это известно еще со статьи, где саму архитектуру ViT предлагали, но в данной работе конкретизируется, какая голова отвечает за форму, какая за цвета, итд. Статья - существенный вклад в explainable AI.
3. ULTRA Towards Foundation Models for Knowledge Graph Reasoning - предлагается архитектура фундаментальной модели GNN. Более подробно в этом посте.
4. Neural Network Expressive Power Analysis Via Manifold Topology - оценивается верхняя граница длины FC сети в терминах топологической сложности (сумма чисел Бетти) обучающих данных. В статье все строго доказывается, и это была бы очень хорошая работа, если бы не ограничение на размерность многообразия = 3, но мб это хороший старт для обобщения на произвольную размерность. Ну и все оценки, завязанные на сумму чисел Бетти для облаков точек тоже достаточно спекулятивные. Статья реджектнута.
Forwarded from КПД
Hydra: Bidirectional State Space Models Through Generalized Matrix Mixers
[Статья][Код]
Современные нейронные сети, обрабатывающие пространственно-временные данные различной природы будь то текст 📝, изображения 📷, аудио 🎵 и видео 📹 так или иначе обладают механизмом перемешивания каналов (channel mixing), обрабатывающим независимо признаки для каждого элемента последовательности, и механизмом обработки последовательности (sequence mixing), использования взаимосвязей между элементами.
В сегодняшнем рассказе речь пойдет про sequence mixing.
Существуют разнообразные опции sequence mixing. Операция смешивания может не зависеть от входа, как например свертка или обучаемая матрица L x L (L - длина последовательности) в MLP-Mixer, S4 и H3 state-space модели, или зависеть - attention механизм в трансформерах или Mamba (Selective State Spaces).
Кроме того, разные механизмы обладают разной сложностью от длины последовательности. Sequence mixing в Attention или MLP-Mixer требует квадратичного по длине последовательности числа элементарных операций с плавающей точкой (FLOPs), так как используют матричную операцию довольно общего вида. Sequence mixers, обладающие некоторой структурой (низкоранговые, Toeplitz матрицы, DFT, бабочки) позволяют добиваться субквадратичной сложности (обычно с некоторой просадкой в качестве).
И sequence mixing может быть как причинным (causal attention, большинство SSM, в частности, модная нынче Mamba 🐍), где текущий элемент последовательности может смотреть только в прошлое, и двунаправленным (как в masked language modelling, и большинстве задач с ViTами), где элементы последовательности могут изменять свое состояние, как глядя как на прошлые, так и на будущие токены.
И задача, которую, перед собой ставят авторы в данной работе - получение эффективного механизма двунаправленного sequence mixing, такого, чтобы он был с одной стороны субквадратичным (в идеале линейным по длине последовательности) и в то же время выразительным.
[Статья][Код]
Современные нейронные сети, обрабатывающие пространственно-временные данные различной природы будь то текст 📝, изображения 📷, аудио 🎵 и видео 📹 так или иначе обладают механизмом перемешивания каналов (channel mixing), обрабатывающим независимо признаки для каждого элемента последовательности, и механизмом обработки последовательности (sequence mixing), использования взаимосвязей между элементами.
В сегодняшнем рассказе речь пойдет про sequence mixing.
Существуют разнообразные опции sequence mixing. Операция смешивания может не зависеть от входа, как например свертка или обучаемая матрица L x L (L - длина последовательности) в MLP-Mixer, S4 и H3 state-space модели, или зависеть - attention механизм в трансформерах или Mamba (Selective State Spaces).
Кроме того, разные механизмы обладают разной сложностью от длины последовательности. Sequence mixing в Attention или MLP-Mixer требует квадратичного по длине последовательности числа элементарных операций с плавающей точкой (FLOPs), так как используют матричную операцию довольно общего вида. Sequence mixers, обладающие некоторой структурой (низкоранговые, Toeplitz матрицы, DFT, бабочки) позволяют добиваться субквадратичной сложности (обычно с некоторой просадкой в качестве).
И sequence mixing может быть как причинным (causal attention, большинство SSM, в частности, модная нынче Mamba 🐍), где текущий элемент последовательности может смотреть только в прошлое, и двунаправленным (как в masked language modelling, и большинстве задач с ViTами), где элементы последовательности могут изменять свое состояние, как глядя как на прошлые, так и на будущие токены.
И задача, которую, перед собой ставят авторы в данной работе - получение эффективного механизма двунаправленного sequence mixing, такого, чтобы он был с одной стороны субквадратичным (в идеале линейным по длине последовательности) и в то же время выразительным.
Forwarded from КПД
Метод
Общий фреймворк выглядит следующим образом:
▶️ Функция преобразования данных
▶️ Функция конструкции смешивающей матрицы
▶️ Результат sequence mixing имеет вид
Далее авторы вводят термин Sequence Aligned Matrices (SAM, еще один… 🥱) означающий, что матрица смешивания зависит от входных данных. Такие sequece миксеры хороши с одной стороны тем, что более адаптивно подстраиваются под входы, и, кроме того, работают с последовательностями разной длины.
Авторы рассматривают разные механизмы из литературы:
⭐️ MLP-Mixer, S4, H3, Monarch, Vandermonde и Cauchy миксеры - не SAM
⭐️ Attention, Linear Attention, S6, SSD - SAM
Потому хороший двунаправленный sequence mixer должен быть SAM, и представлять собой некоторую структурированную матрицу. В частности, предлагаются способы сделать Vandermonde и Cauchy миксеры зависящими от входов, но основной упор делается на прокачку SSD (не твердотельного жесткого диска, а механизма в Mamba-2!) под двунаправленность.
Напомним, что SSD во второй мамбе является полуразложимыми (semi-separable) матрицей - каждый блок является низкоранговой матрицей. Для двунаправленности можно было бы чередовать слои SSD (один бегущий слева направо, другой справа налево), но здесь предлагают использование одной матрицы смешивания, такой что любой ее блок в верхне-треугольной и нижне-треугольной части является низкоранговой матрицей. Иначе говоря, получается нечто типа суммы исходной SSD из Mamba-2 (нижнетреугольной матрицы) и транспонированной по длине последовательности (верхнетреугольной матрицы) и диагональной части. Такие матрицы называют квазиразложимыми (QS). Данная модификация требует всего пары дополнительных строчек в реализации по сравнению с исходным SSD слоем (
Называют гидрой, потому что много голов, как в SSD, и звучит красиво 😹.
Эксперименты
Метод валидируют на задаче Masked Language Modelling, где в качестве бейзлайнов берется BERT, обученный по рецепту от MosaicML, и иные варианты sequence mixerов из литературы. Для оценки качества моделей смотрят на валидационную кросс-энтропию на C4 (на train set которого обучают) и точность на бенчах из GLUE. Все модели имеют размер порядка 70M параметров (несколько меньше, чем BERT-Base), так что хрен вам SOTA на LMSYS. Hydra модели глубже трансформеров примерно в 2️⃣ раза при примерно том же числе параметров.
SAM модели стабильно опережают свои не SAM версии (Toeplitz, Cauchy, Vandermonde с параметрами, зависящими от входа, заметно точнее версии с обучаемыми, не зависящими). Hydra (естесна), лучше всех, и на втором месте любимый нами трансформер. Однако, памятуя о недавнем результате MobileLLM, где более глубокие и тонкие трансформеры, оказываются лучше по качеству более коротких и жирных при том же числе параметров, задаешься вопросом - можно ли устранить разрыв в качестве за счет изменения конфигурации трансформера 🤔?
Исходная Mamba-2 не очень сильна в MLM, так как умеет обрабатывать информацию только в одном направлении, и предложенный способ (Hydra) лучше вариантов с суммой, конкатенацией, и перемножением результатов двух мамб-2.
Далее метод проверяют на задаче классификации ImageNet-1k, где обучают модели размера порядка ViT-Base (87-91M параметров) и Hydra опережает ViT-B, Hyena и S4. Однако, ViT бейзлайн вызывает вопросы, ибо согласно их результатам ViT-B имеет top-1 точность 78.8%, а его EMA 80.6%, в то время, как c рецептом обучения из Swin, на который они ссылаются (унаследованный в свою очередь из DeiT) выдает 81.8% (их лучший результат 81.6%)
Общий фреймворк выглядит следующим образом:
▶️ Функция преобразования данных
f_X (X - входные данные)▶️ Функция конструкции смешивающей матрицы
f_M L x L, которая может быть постоянной или зависеть от входов▶️ Результат sequence mixing имеет вид
f_M(f_X (X))Далее авторы вводят термин Sequence Aligned Matrices (SAM, еще один… 🥱) означающий, что матрица смешивания зависит от входных данных. Такие sequece миксеры хороши с одной стороны тем, что более адаптивно подстраиваются под входы, и, кроме того, работают с последовательностями разной длины.
Авторы рассматривают разные механизмы из литературы:
⭐️ MLP-Mixer, S4, H3, Monarch, Vandermonde и Cauchy миксеры - не SAM
⭐️ Attention, Linear Attention, S6, SSD - SAM
Потому хороший двунаправленный sequence mixer должен быть SAM, и представлять собой некоторую структурированную матрицу. В частности, предлагаются способы сделать Vandermonde и Cauchy миксеры зависящими от входов, но основной упор делается на прокачку SSD (не твердотельного жесткого диска, а механизма в Mamba-2!) под двунаправленность.
Напомним, что SSD во второй мамбе является полуразложимыми (semi-separable) матрицей - каждый блок является низкоранговой матрицей. Для двунаправленности можно было бы чередовать слои SSD (один бегущий слева направо, другой справа налево), но здесь предлагают использование одной матрицы смешивания, такой что любой ее блок в верхне-треугольной и нижне-треугольной части является низкоранговой матрицей. Иначе говоря, получается нечто типа суммы исходной SSD из Mamba-2 (нижнетреугольной матрицы) и транспонированной по длине последовательности (верхнетреугольной матрицы) и диагональной части. Такие матрицы называют квазиразложимыми (QS). Данная модификация требует всего пары дополнительных строчек в реализации по сравнению с исходным SSD слоем (
shift - сдвиг на один элемент, flip - разворот последовательности задом наперед, DX - диагональная добавка). QS(X) = shift(SS(X)) + flip(shift(SS(flip(X)))) + DXНазывают гидрой, потому что много голов, как в SSD, и звучит красиво 😹.
Эксперименты
Метод валидируют на задаче Masked Language Modelling, где в качестве бейзлайнов берется BERT, обученный по рецепту от MosaicML, и иные варианты sequence mixerов из литературы. Для оценки качества моделей смотрят на валидационную кросс-энтропию на C4 (на train set которого обучают) и точность на бенчах из GLUE. Все модели имеют размер порядка 70M параметров (несколько меньше, чем BERT-Base), так что хрен вам SOTA на LMSYS. Hydra модели глубже трансформеров примерно в 2️⃣ раза при примерно том же числе параметров.
SAM модели стабильно опережают свои не SAM версии (Toeplitz, Cauchy, Vandermonde с параметрами, зависящими от входа, заметно точнее версии с обучаемыми, не зависящими). Hydra (естесна), лучше всех, и на втором месте любимый нами трансформер. Однако, памятуя о недавнем результате MobileLLM, где более глубокие и тонкие трансформеры, оказываются лучше по качеству более коротких и жирных при том же числе параметров, задаешься вопросом - можно ли устранить разрыв в качестве за счет изменения конфигурации трансформера 🤔?
Исходная Mamba-2 не очень сильна в MLM, так как умеет обрабатывать информацию только в одном направлении, и предложенный способ (Hydra) лучше вариантов с суммой, конкатенацией, и перемножением результатов двух мамб-2.
Далее метод проверяют на задаче классификации ImageNet-1k, где обучают модели размера порядка ViT-Base (87-91M параметров) и Hydra опережает ViT-B, Hyena и S4. Однако, ViT бейзлайн вызывает вопросы, ибо согласно их результатам ViT-B имеет top-1 точность 78.8%, а его EMA 80.6%, в то время, как c рецептом обучения из Swin, на который они ссылаются (унаследованный в свою очередь из DeiT) выдает 81.8% (их лучший результат 81.6%)
Forwarded from Small Data Science for Russian Adventurers
2023_bookWTD_Dyakonov_27.pdf
6.3 MB
#книга
Каждая книга — кража у собственной жизни. // Марина Цветаева
И ещё одна моя книжка... когда-то я придумал игру для студентов "Что здесь изображено?". В последний год довольно много взаимодействовал со школьниками, им она тоже "зашла", как и учителям. Меня спросили, есть ли какой-то сборник заданий по этой игре... пришлось его срочно составить.
Каждая книга — кража у собственной жизни. // Марина Цветаева
И ещё одна моя книжка... когда-то я придумал игру для студентов "Что здесь изображено?". В последний год довольно много взаимодействовал со школьниками, им она тоже "зашла", как и учителям. Меня спросили, есть ли какой-то сборник заданий по этой игре... пришлось его срочно составить.
Forwarded from (sci)Berloga Всех Наук и Технологий
🚀 @SBERLOGASCI webinar on mathematics and data science:
👨🔬 Sergei Gukov "What makes math problems hard for reinforcement learning: a case study"
⌚️ 19 September, Thursday 19.00 Moscow time
Add to Google Calendar
Can AI solve hard and interesting research-level math problems? While there is no mathematical definition of what makes a mathematical problem hard or interesting, we can provisionally define such problems as those that are well known to an average professional mathematician and have remained open for N years. The larger the value of N, the harder the problem. Using examples from combinatorial group theory and low-dimensional topology, in this talk I will explain that solving such hard long-standing math problems holds enormous potential for AI algorithm development, providing a natural path toward Artificial General Intelligence (AGI).
The talk is based on a recent paper: https://arxiv.org/abs/2408.15332
О докладчике: Сергей Гуков - профессор КалТех, выпускник МФТИ и Принстона, один из наиболее известных специалистов по теории струн и математической физике, в последние годы занимающийся применением методов Reinforcement Leaning к задачам математики и физики.
Zoom link will be in @sberlogabig just before start. Video records: https://www.youtube.com/c/SciBerloga and in telegram: https://t.me/sberlogasci/19688 - subscribe !
Анонс на твиттер:
https://x.com/sberloga/status/1835702457260765359
Ваши лайки и репосты - очень welcome !
👨🔬 Sergei Gukov "What makes math problems hard for reinforcement learning: a case study"
⌚️ 19 September, Thursday 19.00 Moscow time
Add to Google Calendar
Can AI solve hard and interesting research-level math problems? While there is no mathematical definition of what makes a mathematical problem hard or interesting, we can provisionally define such problems as those that are well known to an average professional mathematician and have remained open for N years. The larger the value of N, the harder the problem. Using examples from combinatorial group theory and low-dimensional topology, in this talk I will explain that solving such hard long-standing math problems holds enormous potential for AI algorithm development, providing a natural path toward Artificial General Intelligence (AGI).
The talk is based on a recent paper: https://arxiv.org/abs/2408.15332
О докладчике: Сергей Гуков - профессор КалТех, выпускник МФТИ и Принстона, один из наиболее известных специалистов по теории струн и математической физике, в последние годы занимающийся применением методов Reinforcement Leaning к задачам математики и физики.
Zoom link will be in @sberlogabig just before start. Video records: https://www.youtube.com/c/SciBerloga and in telegram: https://t.me/sberlogasci/19688 - subscribe !
Анонс на твиттер:
https://x.com/sberloga/status/1835702457260765359
Ваши лайки и репосты - очень welcome !