Детерминированная нейросеть на конечных группах: эксперимент с XOR

Введение: проблема недетерминизма

Попробуйте запустить обучение простой PyTorch модели 10 раз на одних и тех же данных:

import torch
import torch.nn as nn

# Одна и та же архитектура
model = nn.Sequential(
    nn.Linear(2, 4),
    nn.ReLU(),
    nn.Linear(4, 2)
)

# 10 запусков с разными seed
for seed in range(10):
    torch.manual_seed(seed)
    train(model, train_data)
    acc = evaluate(model, test_data)
    print(f"Run {seed}: accuracy={acc:.2%}")

# Output:
# Run 0: accuracy=95.2%  ← Разные результаты!
# Run 1: accuracy=96.8%
# Run 2: accuracy=94.5%
# ...

Для исследований и экспериментов это нормально — контролируем через random seed. Но что если нужна 100% воспроизводимость?

• Медицинская диагностика (FDA certification)

• Автономный транспорт (safety-critical systems)

• Финансовые системы (audit trail)

• Научные эксперименты (reproducibility crisis)

В этих областях «почти воспроизводимо» = «неприемлемо».

Идея: конечные группы вместо ℝ

Что если заменить вещественные числа на конечные циклические группы?

Классический подход:

• Веса: W ∈ ℝⁿ (континуум, бесконечно)

• Активация: σ(x) = 1/(1 + e⁻ˣ) (floating point)

• Оптимизация: SGD с градиентами

Алгебраический подход:

• Веса: W ∈ Zₙ = {0, 1, …, n-1} (конечно!)

• Активация: step(x) = (x + 1) mod n (целые числа)

• Оптимизация: exhaustive search (перебор)

Преимущества

✅ Детерминизм 100% — нет random seed, нет floating point errors

✅ Формальная верификация — конечное пространство → exhaustive проверка

✅ Глобальный оптимум — exhaustive search гарантирует лучшее решение

✅ Компактность — маленькие модели (< 1 MB)

Компромиссы

⚠️ Ограниченная выразительность — не все функции можно выразить в Zₙ

⚠️ Масштабируемость — exhaustive search работает только на малых задачах

⚠️ Нет SOTA — proof-of-concept, не замена PyTorch

Реализация: YANTRA

Назвал проект YANTRA (Yet Another Neural Theory via Rational Algebra).

Основная идея: AFSM нейрон

Нейрон = автомат (Automaton) на конечной алгебраической структуре:

class AFSMNeuron:
    def __init__(self, n: int):
        self.n = n  # Размер циклической группы Zₙ
    
    def step(self, state):
        """Детерминированный переход состояния
        
        Формула: step(o, x, i, j) = (o', x', i', j')
        где:
            o' = (o + 1) mod n      # Орбита
            x' = (x * i) mod n      # Внутреннее состояние
            i' = i                  # Вход не меняется
            j' = (j * o') mod n     # Выход
        """
        o, x, i, j = state
        return (
            (o + 1) % self.n,
            (x * i) % self.n,
            i,
            (j * ((o + 1) % self.n)) % self.n
        )

Ключевое свойство: Детерминизм — одинаковый вход → одинаковый выход (всегда!).

Обучение: exhaustive search

Вместо градиентного спуска — полный перебор в сжатом пространстве:

def train(self, X, y):
    """Exhaustive search в пространстве кандидатов"""
    best_accuracy = 0.0
    best_params = None
    
    # Генерируем все кандидаты (в сжатом пространстве)
    candidates = self.generate_candidates()  # ~64 кандидата для XOR
    
    # Проверяем каждого
    for params in candidates:
        accuracy = self.evaluate(params, X, y)
        if accuracy > best_accuracy:
            best_accuracy = accuracy
            best_params = params
    
    self.params = best_params  # Гарантированно лучший!
    return best_params

Для XOR: Пространство поиска = 2⁶ = 64 кандидата. Это exhaustive проверяется за ~0.15 секунды.

Сжатие через автоморфизмы

Наивный exhaustive search: 2¹⁶ = 65536 кандидатов для функции {0,1}² → {0,1}.

Оптимизация: Используем группу автоморфизмов Aut(K) для компрессии пространства.

Фактор-пространство Q = K / Aut(K) содержит только уникальные классы эквивалентности.

Коэффициент сжатия: r ≈ 12 (для типичных конфигураций).

Итого: 65536 / 12 ≈ 5461 → дальнейшее сжатие → ~64 кандидата.

Эксперименты

Setup

# Установка
git clone https://github.com/yantra-ml/yantra.git
cd yantra
pip install -e .

# Запуск примеров
python examples/01_xor_demo.py
python examples/02_determinism_test.py

Эксперимент 1: XOR классификация

Задача: XOR — классическая нелинейная задача, не решаемая линейным классификатором.

from yantra import AFSMClassifier
from yantra.datasets import generate_xor_dataset

# Данные
X_train, y_train = generate_xor_dataset(n_samples=40)
X_test, y_test = generate_xor_dataset(n_samples=20)

# Обучение
clf = AFSMClassifier(k_vec=(2, 4), activation='vortex_step')
clf.train(X_train, y_train)

# Тестирование
accuracy = clf.evaluate(X_test, y_test)
print(f"XOR accuracy: {accuracy:.1%}")

Результат:

Candidates evaluated: 64
Method: Exhaustive search (deterministic)
XOR accuracy: 100.0%

Confusion Matrix:
[[10,  0]
 [ 0, 10]]

100% accuracy на нелинейной задаче без градиентов!

Эксперимент 2: Детерминизм (10 runs)

Запускаем обучение 10 раз на одинаковых данных:

# 10 запусков
for run in range(1, 11):
    clf = AFSMClassifier(k_vec=(2, 4))
    clf.train(X_train, y_train)
    predictions = [clf.predict(x) for x in X_test]
    print(f"Run {run}: {predictions[:5]} ...")

Результат:

Run  1: [0, 1, 0, 1, 1] ... accuracy=100.0%
Run  2: [0, 1, 0, 1, 1] ... accuracy=100.0%
...
Run 10: [0, 1, 0, 1, 1] ... accuracy=100.0%

Unique prediction patterns: 1/10
Unique accuracy values: 1/10

✅ DETERMINISM VERIFIED!

Все 10 runs → абсолютно идентичные результаты!

Никакого random seed не нужно — система детерминирована по определению.

Сравнение с PyTorch

Запустил аналогичный тест с простой PyTorch MLP:

Ключевое отличие: Не accuracy (оба решают XOR), а гарантии детерминизма.

Верификация

Exhaustive проверка алгебраических свойств:

from yantra.verification import verify_all

results = verify_all(clf)
print(f"Checks: {results['passed']}/{results['total']}")
# Output: 3072/3072 PASS ✓

Что проверяется:

✓ Ассоциативность: (a ⊗ b) ⊗ c = a ⊗ (b ⊗ c) для всех a, b, c ∈ Zₙ ✓ Эквивариантность: step(σ(s)) = σ(step(s)) для всех автоморфизмов σ ✓ Периодичность: stepʳ(x) = x для коэффициента сжатия r ✓ Замкнутость: a ⊗ b ∈ Zₙ для всех a, b

Метод: Exhaustive enumeration — проверяем ВСЕ комбинации элементов.

Для классических нейросетей такая верификация невозможна (бесконечное пространство ℝⁿ).

Ограничения (честно!)

✅ Работает

• XOR (нелинейная задача)

• Two Blobs (линейная классификация)

• Простые binary/multiclass задачи

• Малые датасеты (< 1000 samples)

❌ Не работает (пока)

• MNIST 28×28 (exhaustive search не масштабируется)

• CIFAR-10, ImageNet (слишком большие)

• Регрессия с непрерывными выходами

• Большие датасеты (> 10K samples)

🎯 Это proof-of-concept, не замена PyTorch!

Выбор между:

Классический ML (PyTorch/TensorFlow):

• ✅ Масштабируется на любые задачи

• ✅ SOTA результаты

• ✅ Большое комьюнити

• ❌ Недетерминизм

• ❌ Нет формальных гарантий

YANTRA (Algebraic ML):

• ✅ 100% детерминизм

• ✅ Формальная верификация

• ✅ Математические гарантии

• ❌ Ограниченная выразительность

• ❌ Не масштабируется

Вывод: Используйте YANTRA для критических систем, где нужна верификация. Для production ML — PyTorch/TensorFlow.

Где это может быть полезно?

1. Критические системы с сертификацией

   • Medical devices (FDA approval)

   • Automotive (ISO 26262)

   • Aerospace (DO-178C)

   • Требуется formal verification

2. Embedded ML

   • FPGA реализация (детерминизм на железе)

   • Микроконтроллеры (real-time гарантии)

   • IoT устройства (компактные модели)

3. Научные исследования

   • 100% воспроизводимость экспериментов

   • Reproducibility crisis в ML

   • Честное сравнение алгоритмов

4. Обучение основам ML

   • Прозрачная архитектура (нет «магии»)

   • Понимание exhaustive search

   • Алгебраический взгляд на ML

Открытые вопросы

Что удалось:

• ✅ Доказать жизнеспособность подхода

• ✅ Решить XOR exhaustive search-ом

• ✅ Получить 100% детерминизм

• ✅ Реализовать формальную верификацию

Что не получилось (пока):

• ❌ Масштабировать на MNIST 28×28

• ❌ Обогнать PyTorch по accuracy

• ❌ Сделать универсальный метод

Направления развития:

• 🔬 Гибридные архитектуры (YANTRA + PyTorch)?

• 🔬 Аппаратная реализация на FPGA?

• 🔬 Улучшение exhaustive search (pruning)?

Заключение

YANTRA — это proof-of-concept детерминированного ML на конечных группах.

Главный результат: Доказал, что можно:

• Решить нелинейную задачу (XOR) без градиентов

• Получить 100% детерминизм (10/10 runs identical)

• Формально верифицировать все свойства (3072 checks PASS)

Практическое применение: Ограничено пока toy-задачами, но принцип работает.

Призыв: Если вам интересна тема algebraic ML, формальной верификации или детерминизма — welcome к сотрудничеству!

Ссылки

• GitHub: yantra-ml/yantra

• Примеры: examples/

• Документация: docs/

# Попробовать самостоятельно
git clone https://github.com/yantra-ml/yantra.git
cd yantra
pip install -e .
python examples/01_xor_demo.py

Вопросы и обратная связь приветствуются!

Буду рад обсуждению в комментариях или через GitHub Issues.

P.S. Да, я понимаю, что это не замена PyTorch. Это исследование альтернативного подхода к ML через алгебру. Если хотя бы один человек заинтересуется темой формальной верификации в ML — я доволен :)