На данный момент на графах с количеством вершин $> 40$ сходимость GOLEM деградирует: #69. Методы поиска графов с доступам к градиенту целевой функции, например NOTEARS, работают с заметно большими графами.
Один из вариантов преодоления этой проблемы — использовать непрямые кодировки в эволюции: особи представляются не как графы непосредственно, а как что-то, раскодирующееся в них. Статья, упомянутая в #100, утверждает, что такие кодировки стоит искать среди expressive encodings. При специализации задачи для графов возникает несколько вариантов. По сравнению с прямыми кодировками им свойственны:
модуляризуемость. Переиспользование блоков внутри графа, то есть поиск в пространстве графов с низкой Колмогоровской сложностью: при больших графах точное (aka оптимальное) решение обычно искать смысла не имеет и зачастую оно не модуляризуемо, но в реальных задачах очень часто существует достаточно хорошее модуляризуемое решение.
полигены — на одну и ту же часть фенотипа влияют разные части генома → нейтральность (позволяет безнаказанно накапливать мутации, которые не проявляются, но могут оказаться полезными при смене среды — эффект «canalization»),
плейотропия — один и тот же ген влияет на многие части фенотипа → модулярность (позволяет компактно и реюзабельно кодировать фенотип).
Создание графа делится на две части — генерация объекта простой структуры (строки/матрицы) из грамматики и преобразование его в желаемое представление (в данном случае — в граф).
Отличаются об обычных грамматик тем, что раскрытие происходит не в произвольном порядке, а по итерациям — сначала раскрываются нетерминалы, сгенерированные раньше.
Можно парсить дерево из строки, а можно генерировать матрицу смежности графа, как в «Designing neural networks using genetic algorithms with graph generation system».
Простой подход, но очень много проблем.
Гиперграфовые грамматики
На каждом шаге вывода имеется гиперграф с рёбрами, помеченными метками-нетерминалами, которые заменяются на гиперграфы с входными и выходными узлами. При этом сопоставление узлов вставляемого графа и вершин, инцидентных ребру, при эволюции осмысленно производить на основе soft matching по эволюционирующим меткам (см. статью):
Graph Design by Graph Grammar Evolution, 2007
↑↑↑ здесь отдельно поддерживается пулл правил, отдельно грамматики — его подмножества.
Коэволюция компонентов и методов их комбинации
Популяции:
Блоки (в случае NAS — несколько слоёв)
Глобальная структура с ссылками на блоки
Это частный случай грамматики, где глобальный терминал раскрывается в структуру с нетерминалами-ссылками на блоки, которые уже раскрываются в сами блоки, но применяются хитрые мутации к правой части правил.
Evolving Deep Neural Networks, Risto Miikkulainen, 2023
Клеточные кодировки
Граф представляется деревом программы особого вида, которое «исполняется» клетками в процессе эмбриогенеза. Когда программа клетки завершается, она превращается в вершину графа. К этому дереву уже применяются «простые» мутации.
Обладают привлекательными теоретическими свойствами:
полнота (с разными наборами инструкций клеток для разных классов графов)
замкнутость (аналогично)
компактность
модулярность
частный случай грамматики
В частности, для многих классов графов можно подобрать набор разрешённых операций в клетках, чтобы выполнялась полнота и замкнутость для конкретной задачи. Соответственно, можно автоматически генерировать кодировку для произвольного объекта GraphRequirements и каких-то graph verifier-ов, а значит мутации не будут выводить из искомого класса графов.
Кажется, можно доказать, что клеточные кодировки являются expressive encodings в смысле статьи из #100.
На данный момент фокус направлен на них.
Статья, где впервые ввели клеточные кодировки:
Neural Network Synthesis Using Cellular Encoding and the Genetic Algorithm, Gruau, 1994
XC-NAS: A New Cellular Encoding Approach for Neural Architecture Search of Multi-path Convolutional Neural Networks, 2023
Ищут макро-архитектуру из существующих building-блоков (convolution, resNet и Inception). Процесс эволюции занимает один GPU-day.
Используют клеточную кодировку: вводят инструкции клеток с различением матери и ребёнка при делении и регистры у каждого: глубина (путь по слоям максимально длины) и ширина (количество свёрток в слое). Эти операции по-разному изменяют эти значения у ребёнка, у матери сохраняется. Могут быть как последовательные, так и параллельные.
Мутация: классическая для GP: смена поддерева какой-то ноды на случайное какого-то размера.
Кроссовер: аналогично — смена случайных поддеревьев, получая 2 отпрыска.
Селекция: турнирная с тюныящимся размером турнира.
GANы
TODO
Эволюция в пространстве embedding-ов?
Эволюция весов части GAN?!
На данный момент — ведутся эксперименты, после чего, в случае успеха — буде внедрять в GOLEM.
Реализовано MVP, проверена замкнутость и полнота в разных подпространствах DAGов: с 1 или многими истоками и стоками, получен прирост скорость сходимости по правнению с обычным DEAP.
Текущие задачи:
[x] Доказать или опровергнуть утверждение, что клеточная кодировка — expressive (в зависимости от подмножества операторов).
(TODO: улучшить асимптотику?)
[x] Получить теоретический результат о лучшей скорости сходимости клеточных кодировок по сравнению с прямыми на некотором классе задач.
[x] Двухуровневые (то есть вложенность раскрытия правил — 2) Гиперграфовые грамматики
[x] Большее количество уровней вложенности и разнообразие блоков
Подобрать для разных классов графов оптимальное подмножество операторов (tree-DAG; DAG, разделяемый на слои, где связи только если $|\mathrm{layer}_i - \mathrm{layer}_j| \leq d$, прочих часто встречающихся классов).
Добавить поддержку параметров, ассоциированных с вершинами и рёбрами.
Представлять операторы в вершинах как векторы того, какие операции производятся и над чем. Это позволит решить задачу поиска подмножества операторов эволюцией, а также структурировать код.
В процессе разработка идей:
Поддержать набор операций и правил применения для обеспечения полноты и замкнутости в DAGах, ограниченных прозвольными GraphRequirements и GraphAdvisor.
За счёт регистров, soft матчинга или рандома попробовать выделять какую-то часть связей ноды (сид рандома/метки тогда, вероятно, будут храниться в геноме).
При генерации дерева кодировки и мутациях вершины устанавливаются в случайную инструкцию клеточной кодировки, изменяющую окрестность клетки-вершины: она может обрезать связи, может добавлять вершину (по-разному связанную с этой и наследующую/отбирающую связи материнской клетки). Всего таких инструкций ≈20 штук.
Tracking issue for this research direction.
На данный момент на графах с количеством вершин $> 40$ сходимость GOLEM деградирует: #69. Методы поиска графов с доступам к градиенту целевой функции, например NOTEARS, работают с заметно большими графами. Один из вариантов преодоления этой проблемы — использовать непрямые кодировки в эволюции: особи представляются не как графы непосредственно, а как что-то, раскодирующееся в них. Статья, упомянутая в #100, утверждает, что такие кодировки стоит искать среди expressive encodings. При специализации задачи для графов возникает несколько вариантов. По сравнению с прямыми кодировками им свойственны:
L-systems
https://en.wikipedia.org/wiki/L-system
Создание графа делится на две части — генерация объекта простой структуры (строки/матрицы) из грамматики и преобразование его в желаемое представление (в данном случае — в граф). Отличаются об обычных грамматик тем, что раскрытие происходит не в произвольном порядке, а по итерациям — сначала раскрываются нетерминалы, сгенерированные раньше.
Можно парсить дерево из строки, а можно генерировать матрицу смежности графа, как в «Designing neural networks using genetic algorithms with graph generation system».
Простой подход, но очень много проблем.
Гиперграфовые грамматики
На каждом шаге вывода имеется гиперграф с рёбрами, помеченными метками-нетерминалами, которые заменяются на гиперграфы с входными и выходными узлами. При этом сопоставление узлов вставляемого графа и вершин, инцидентных ребру, при эволюции осмысленно производить на основе soft matching по эволюционирующим меткам (см. статью):
Graph Design by Graph Grammar Evolution, 2007 ↑↑↑ здесь отдельно поддерживается пулл правил, отдельно грамматики — его подмножества.
Коэволюция компонентов и методов их комбинации
Популяции:
Это частный случай грамматики, где глобальный терминал раскрывается в структуру с нетерминалами-ссылками на блоки, которые уже раскрываются в сами блоки, но применяются хитрые мутации к правой части правил.
Evolving Deep Neural Networks, Risto Miikkulainen, 2023
Клеточные кодировки
Граф представляется деревом программы особого вида, которое «исполняется» клетками в процессе эмбриогенеза. Когда программа клетки завершается, она превращается в вершину графа. К этому дереву уже применяются «простые» мутации.
Обладают привлекательными теоретическими свойствами:
В частности, для многих классов графов можно подобрать набор разрешённых операций в клетках, чтобы выполнялась полнота и замкнутость для конкретной задачи. Соответственно, можно автоматически генерировать кодировку для произвольного объекта
GraphRequirementsи каких-то graph verifier-ов, а значит мутации не будут выводить из искомого класса графов.Кажется, можно доказать, что клеточные кодировки являются expressive encodings в смысле статьи из #100.
На данный момент фокус направлен на них.
XC-NAS: A New Cellular Encoding Approach for Neural Architecture Search of Multi-path Convolutional Neural Networks, 2023 Ищут макро-архитектуру из существующих building-блоков (convolution, resNet и Inception). Процесс эволюции занимает один GPU-day.
Используют клеточную кодировку: вводят инструкции клеток с различением матери и ребёнка при делении и регистры у каждого: глубина (путь по слоям максимально длины) и ширина (количество свёрток в слое). Эти операции по-разному изменяют эти значения у ребёнка, у матери сохраняется. Могут быть как последовательные, так и параллельные.
Мутация: классическая для GP: смена поддерева какой-то ноды на случайное какого-то размера. Кроссовер: аналогично — смена случайных поддеревьев, получая 2 отпрыска. Селекция: турнирная с тюныящимся размером турнира.
GANы
TODO
Эволюция в пространстве embedding-ов? Эволюция весов части GAN?!
Graph Learning for Combinatorial Optimization: A Survey of State-of-the-Art: https://arxiv.org/pdf/2008.12646.pdf
Бенчмарки, процесс разработки
На данный момент — ведутся эксперименты, после чего, в случае успеха — буде внедрять в GOLEM.
Реализовано MVP, проверена замкнутость и полнота в разных подпространствах DAGов: с 1 или многими истоками и стоками, получен прирост скорость сходимости по правнению с обычным DEAP.
Текущие задачи:
В процессе разработка идей:
GraphRequirementsиGraphAdvisor.При генерации дерева кодировки и мутациях вершины устанавливаются в случайную инструкцию клеточной кодировки, изменяющую окрестность клетки-вершины: она может обрезать связи, может добавлять вершину (по-разному связанную с этой и наследующую/отбирающую связи материнской клетки). Всего таких инструкций ≈20 штук.
Также планируется тестирование на NAS Bench.