An algorithmic framework for the optimization of deep neural networks architectures and hyperparameters

Авторы показывают, что задачу NAS(Neural Architecture Search) можно разбить на 2 подзадачи - определение структуры (поиск самого DAG - пространство 𝒜) и поиск гиперпараметров (поиск операций в узлах DAG - пространство гиперпараметров Λ⁢(a)). В итоге пространство поиска раскладывается в произведение пространств - Ω=(𝒜×{Λ⁢(a),a∈𝒜}), где a - это архитектура. Далее используется процедура NAS на основе эволюционного элгоритма. Применяется для поиска DNN для задачи предсказания временных рядов.

https://arxiv.org/pdf/2303.12797.pdf

https://arxiv.org/abs/2305.02023 В классическом покере есть 4-мерная сфера.

We examine the complexity of the ``Texas Hold'em'' variant of poker from a topological perspective. We show that there exists a natural simplicial complex governing the multi-way winning probabilities between various hands, and that this simplicial complex contains 4-dimensional spheres as induced subcomplexes. We deduce that evaluating the strength of a pair of cards in Texas Hold'em is an intricate problem, and that even the notion of who is bluffing against whom is ill-defined in some situations.

Towards Universal Fake Image Detectors that Generalize Across Generative Models

Авторы решают задачу распознавания фейковых примеров. Используют ViT из CLIP для извлечения признаков из (фейковых/реальных изображениях), затем тренируют обычный log-reg на бинарную классификацию на фичах. Их решение обобщается на разные домены: обучили на данных с генеративной модели ProGAN, и полученный классификатор работает на данных с других доменов (т.е. генеративных моделях - другие GAN: StyleGAN, BigGAN итд и диффузионных моделях). Применение преобученного ViT из CLIP работает лучше, чем файнтюнинг обычного ViT на классификацию.

https://arxiv.org/pdf/2302.10174.pdf

AttentionViz: A Global View of Transformer Attention

Transformer models are revolutionizing machine learning, but their inner workings remain mysterious. In this work, we present a new visualization technique designed to help researchers understand the self-attention mechanism in transformers that allows these models to learn rich, contextual relationships between elements of a sequence. The main idea behind our method is to visualize a joint embedding of the query and key vectors used by transformer models to compute attention. Unlike previous attention visualization techniques, our approach enables the analysis of global patterns across multiple input sequences. We create an interactive visualization tool, AttentionViz (demo: http://attentionviz.com), based on these joint query-key embeddings, and use it to study attention mechanisms in both language and vision transformers. We demonstrate the utility of our approach in improving model understanding and offering new insights about query-key interactions through several application scenarios and expert feedback

Architectures of Topological Deep Learning: A Survey on Topological Neural Networks

The natural world is full of complex systems characterized by intricate relations between their components: from social interactions between individuals in a social network to electrostatic interactions between atoms in a protein. Topological Deep Learning (TDL) provides a comprehensive framework to process and extract knowledge from data associated with these systems, such as predicting the social community to which an individual belongs or predicting whether a protein can be a reasonable target for drug development. TDL has demonstrated theoretical and practical advantages that hold the promise of breaking ground in the applied sciences and beyond. However, the rapid growth of the TDL literature has also led to a lack of unification in notation and language across Topological Neural Network (TNN) architectures. This presents a real obstacle for building upon existing works and for deploying TNNs to new real-world problems. To address this issue, we provide an accessible introduction to TDL, and compare the recently published TNNs using a unified mathematical and graphical notation. Through an intuitive and critical review of the emerging field of TDL, we extract valuable insights into current challenges and exciting opportunities for future development.

https://arxiv.org/pdf/2304.10031.pdf

Data Topology-Dependent Upper Bounds of Neural Network Widths

Our primary contribution is to introduce data topology-dependent upper bounds on the network width. Specifically, we first show that a three-layer neural network, applying a ReLU activation function and max pooling, can be designed to approximate an indicator function over a compact set, one that is encompassed by a tight convex polytope. This is then extended to a simplicial complex, deriving width upper bounds based on its topological structure. Further, we calculate upper bounds in relation to the Betti numbers of select topological spaces. Finally, we prove the universal approximation property of three-layer ReLU networks using our topological approach. We also verify that gradient descent converges to the network structure proposed in our study.

https://arxiv.org/pdf/2305.16375.pdf

Riemannian Geometry of Symmetric Positive Definite Matrices via Cholesky Decomposition

We present a new Riemannian metric, termed Log-Cholesky metric, on the manifold of symmetric positive definite (SPD) matrices via Cholesky decomposition. We first construct a Lie group structure and a bi-invariant metric on Cholesky space, the collection of lower triangular matrices whose diagonal elements are all positive. Such group structure and metric are then pushed forward to the space of SPD matrices via the inverse of Cholesky decomposition that is a bijective map between Cholesky space and SPD matrix space. This new Riemannian metric and Lie group structure fully circumvent swelling effect, in the sense that the determinant of the Fréchet average of a set of SPD matrices under the presented metric, called Log-Cholesky average, is between the minimum and the maximum of the determinants of the original SPD matrices. Comparing to existing metrics such as the affine-invariant metric and Log-Euclidean metric, the presented metric is simpler, more computationally efficient and numerically stabler. In particular, parallel transport along geodesics under Log-Cholesky metric is given in a closed and easy-to-compute form.

Data Analysis with the Riemannian Geometry of Symmetric Positive-Definite Matrices
http://www.ipam.ucla.edu/abstract/?tid=15457&pcode=GLWS3

Neural Networks are Decision Trees

In this manunoscript, we show that any neural network with any activation function can be represented as a decision tree. The representation is equivalence and not an approximation, thus keeping the accuracy of the neural network exactly as is. We believe that this work provides better understanding of neural networks and paves the way to tackle their black-box nature. We share equivalent trees of some neural networks and show that besides providing interpretability, tree representation can also achieve some computational advantages for small networks. The analysis holds both for fully connected and convolutional networks, which may or may not also include skip connections and/or normalizations.

https://www.youtube.com/watch?v=_okxGdHM5b8

Применение GPT-2 для генерации элементов из пересечения нормальных замыканий: prompt и masking подходы

Applying language models to algebraic topology: generating simplicial cycles using multi-labeling in Wu's formula

Computing homotopy groups of spheres has long been a fundamental objective in algebraic topology. Various theoretical and algorithmic approaches have been developed to tackle this problem. In this paper we take a step towards the goal of comprehending the group-theoretic structure of the generators of these homotopy groups by leveraging the power of machine learning. Specifically, in the simplicial group setting of Wu's formula, we reformulate the problem of generating simplicial cycles as a problem of sampling from the intersection of algorithmic datasets related to Dyck languages. We present and evaluate language modelling approaches that employ multi-label information for input sequences, along with the necessary group-theoretic toolkit and non-neural baselines.

Asynchronous Algorithmic Alignment with Cocycles, среди авторов Petar Velickovic

Предлагается теоретическое обоснование дизайна архитектуры графовой нейронной сети (GNN ) c полностью асинхронным вычислением (update и aggregation) состояний узлов. Для того, что бы имплементировать такую архитектуру, операция обновления и агрегации должна удовлетворять некоторым условиям: быть коммутативным моноидом и быть идемпотентной. Авторы называют такие функции - 1-коциклы. Кода и экспериментов нет.

https://arxiv.org/pdf/2306.15632.pdf

Топологические графовые нейронные сети TGNN - это обобщение классических GNN на случай, когда данные имеют богатую топологическую информацию. Такие сети обучаются аналогично GNN через message passing, но с учетом того, что данные могут содержать не только ребра и вершины, но и более высокоразмерные подструктуры, а отношения между подструктурами сложнее. Кратко упомянем основные типы архитектур TGNN:

1. Simplicial Complexes (SC) TGNN: в отличии от GNN допускается не только вершины и ребра, но и симплексы более высоких размерностей. Примеры архитектур: SNN, Hodge Laplacian, SCCONV.

2. Cellular Complexes (CC) TGNN: обобщение SC на случай, когда клетки не ограничиваются симплексами и могут содержать более 3-х узлов. За счет этих дополнений архитектура CC более выразительная. Примеры: CXNs, Cell attention networks

3. Hypergraphs: обобщение графов, которое позволяет соединять ребрами произвольные подмножства вершин. Более подробно про это написал Paul Snopov в посте о нашем с ним участии в ICML челендже, где мы реализовали архитектуры HyperSage и HyperGat.

4. Combinatorial complexes (CCCs): обобщают клеточные и гиперграфы, позволяют также реализовывать тип отношений часть-целое. Higher-Order Attention Networks (HOAN)

5*. Отдельно стоят Neural Sheaf Diffusion - GNN на основе клеточных пучков.

TGNN уже давно применяются для анализа молекул, социальных сетей, графов цитирования и для многих других задач, где просто GNN могут справляться не очень успешно из-за слабой выразительной силы. Более подробно это объясняется в "A Survey on The Expressive Power of Graph Neural Networks".

Готовые имплементации архитектур TGNN удобно представлены в фреймворке TopoModelX. А также недавно вышел тех-репорт по ICML 2023 Topological Deep Learning Challenge, в котором предлагалось сделать контрибьюшн в TopoModelX.

Автор канала теперь живет в Японии. Фото, истории про местную специфику и стримы с улиц Токио можно найти в лайв-канале https://news.1rj.ru/str/junkyard_goi_jin

Подробно остановимся на проблеме доказательства теорем и на существующих системах формальных верификаций.

С развитием математики, усложнением и появлением новых ответвлений, мы наблюдаем очень беспокойные тенденции: из-за слишком «глубокой и специфичной» теории и подходов к доказательству, научное сообщество просто не может проверить многие результаты. Ручная проверка работы сравнялась по сложности с написанием работы. В итоге современная математика наполнена непроверенными теоремами, и это пирамида продолжает расти. Например, в результатах Воеводского, за которые он получил Филдсовскую премию, уже впоследствии были найдены серьезные ошибки, ситуация закончилась благополучно, потому что спустя много лет Воеводский таки смог исправить ошибки - но сам случай симптоматичный. Никто не мог проверить почти 10 лет доказательство abc-гипотезы японским математиком Матидзуки, его док-во на 600 страниц остаётся в подвешенном состоянии до сих пор, не смотря на принятие работы в журнал. Аналогичная проблема была с проверкой доказательство теоремы Ферма на 100 страниц от Эндрю Уайлса.

Как избежать этих проблем? Правильно - автоматизировать и делегировать компьютеру проверку доказательств. Но для этого нужно записывать док-ва в понятном машине формате, для этого и были созданы такие языки формальных верификаций как Lean v4, Agda, Isabelle, Idris, а так же Coq (Воеводский осмыслял его теоретические основания). Если доказательство записано корректно, то система быстро его проверит. Эти системы включают библиотеки, содержащие модули, в них определяются мат концепции, которые переопределяются через другие модули с более базовыми понятиями, получается некоторое вложение абстракций. Актуальная проблема в том, что пакетов и модулей внутри языков для записи доказательств для современной математики на данный момент недостаточно. При этом уже существует множество формализаций известных классических теорем, Фриком Вейдиком отслеживался прогресс в формализации 100 величайших теорем - на данный момент 99% сделано, осталась лишь Великая теорема Ферма.

Ниже пример записи на языке Isabell базовой леммы из геометрии о Сумме углов треугольника. Здесь представлено доказательство этой теоремы из модуля Triangle.

lemma angle_sum_triangle:
  assumes "a ≠ b ∨ b ≠ c ∨ a ≠ c"
  shows   "angle c a b + angle a b c + angle b c a = pi"

ML в настоящий момент даёт новый виток развитию автоматических доказательств. Помимо модели Llemmа, за последние годы появилось много исследований в области пруверов: Например, модель ASTactic обученная на датасете CoqGym, успешно предлагает тактики доказательств в виде абстрактных синтаксических деревьев (AST). Система TRAIL c помощью RL ищет оптимальную стратегию доказательства теорем. GPT-f генерирует доказательства на языке Metamath, а недавняя работа HyperTree Proof Search предлагает модель превосходящую по точности GPT-f и обученную на Lean v4.